该篇内容为原博客博文，原上传于2023年1月18日。

Sealed Class和Sealed Interface是 kotlin 引入的全新特性。在初学 kotlin 时，我就一直没有掌握其用法，甚至到现在也不能在该用的时候立刻想到。

本篇文章主要总结Sealed Class的基本概念和常见用法。

什么是 Sealed

jetbrains 对 Sealed Class/Interface 的介绍如下：

Sealed classes and interfaces represent restricted class hierarchies that provide more control over inheritance. All direct subclasses of a sealed class are known at compile time. No other subclasses may appear outside a module within which the sealed class is defined. For example, third-party clients can’t extend your sealed class in their code. Thus, each instance of a sealed class has a type from a limited set that is known when this class is compiled.

The same works for sealed interfaces and their implementations: once a module with a sealed interface is compiled, no new implementations can appear.

In some sense, sealed classes are similar to enum classes: the set of values for an enum type is also restricted, but each enum constant exists only as a single instance, whereas a subclass of a sealed class can have multiple instances, each with its own state.

从以上介绍可以大致总结出 Sealed Class/Interface 有如下特性：

• 表示受限的类层次结构，并可以对继承提供更多的控制

• 密封类的子类在编译期即被确定为一个有限的集合内，不可扩展

• 密封类的子类只能位于定义了该密封类的包中

• 密封类的子类可以有多个实例

介绍中还提到，sealed class 和 enum class 在某种意义上是类似的，实际上，sealed class 诞生的重要原因之一正是为了克服 enum class 在某些场合下的局限性，也即上述特性的第一点和第四点。我们知道，枚举类有两个特性，在某些场合下是优点，但在另外一些场合下却可能成为缺点：

• 每个枚举类型只能有一个实例（称为枚举常量）

• 各枚举常量只能使用相同类型的属性

1
2
3
4
5

enum class Drink(val id: Int) {
    Milk(1),
    Coffee(2),
    Water(3)
}

在如上我们创建的枚举类中，各子类（Milk，Coffee，Water）无论有多少对象，都只能有一个实例（即单例的枚举常量），且其属性均只能为枚举类中定义的 Int 类型。

而密封类则取消了以上限制，允许密封类的子类具有多个实例，且各子类可以定义自己的属性。

1
2
3
4
5
6

sealed class Drink {
    // 这里直接在定义块内定义子类
    class Milk(val id: Int): Drink()
    class Coffee(val id: Double): Drink()
    class Water(val id: String): Drink()
}

如上，密封类允许各子类具有不同类型的属性，只需要在子类的主构造函数中声明即可。需要注意的是，密封类在继承上的写法与抽象类区别较大，反而更加类似于一般的抽象类。实际上，密封类正是抽象的，不能直接生成实例，且可以具有抽象成员。因此，密封类可以像上述写法一样定义继承自密封类的子类，也可以用object直接定义子类对象，也可以再用sealed class，即密封类继承密封类，实现更加细粒度的类层次结构。

各子类允许有多个不同状态的实例：

1
2
3
4

val milk1 = Drink.Milk(1)
val milk2 = Drink.Milk(2)
println(milk1.id)
println(milk2.id)

上述特性的第二点意义在于，密封类对运行时的扩展是封闭的。程序在编译时，即可通过继承关系确认密封类的全部子类，由此产生了密封类一个非常实用的用处，在写 when 语句时不需要添加 else 分支，因为全部可能的分支在编译时即可确定，没有其他情况：

1
2
3
4
5

fun test(drink: Drink) = when (drink) {
    is Drink.Milk -> println("milk")
    is Drink.Coffee -> println("coffee")
    is Drink.Water -> println("water")
}

上述特性的第三点意义在于，限制了密封类的作用空间，并且随着 kotlin 版本的更迭越来越宽松：从只能在 sealed class 内，到 1.1 支持同一文件内，到 1.5 支持同一包下。

怎么用 Sealed

kotlin 初学者往往会把sealed class当做enum class用，但enum class具有很明显的适用场景，这么做是不合适的。比如，你仅需要一系列相同类型的单例，且不需要任何额外描述，也不需要特殊的函数，那么用枚举就足够了，比如在我的《设计模式之状态模式》中，各状态有统一的处理方法，用枚举来表示。

在 Android 开发中， sealed class有如下一些使用场景：

• 列表有不同类型的子项（文字、图片），用密封类表示列表的 item

• 封装网络请求中成功（含有任意类型的请求数据）和失败（含有失败信息，如异常）返回的数据

• 使用object达到与枚举类似的效果（虽然在 google 的官方示例都出现了这种用法，但还是不推荐。为什么不直接用枚举呢？）

• 其他一切不满足枚举的应用场景，但需要与枚举类似效果，可以考虑用密封类

关于 Sealed Interface

以上都在讨论sealed class，而sealed interface作为 kotlin1.5 中登场的新特性，也值得说道说道。

密封接口进一步补足了密封类和枚举类的一些不足之处，如枚举类编译后继承自Enum，由于单继承不能再继承其他类，此时可以用密封接口，对枚举类做进一步划分。当然直接用嵌套密封类也未尝不可。

该篇内容为原博客博文，原上传于2021年11月29日。

前言

kotlin是一款十分灵活而又强大的语言。合理地运用kotlin的一些特性，可以极大地提高代码可读性和质量，提高效率。下面我们就来说一说kotlin中的scope function。

域函数

我们主要介绍let, also, with, run, apply这五种常用的域函数。

(1)let

先上let函数的源码：

1
2
3
4
5
6

public inline fun <T, R> T.let(block: (T) -> R): R {
    contract {
        callsInPlace(block, InvocationKind.EXACTLY_ONCE)
    }
    return block(this)
}

从源码我们可以看出，首先，let是对调用者的扩展函数。其次，let函数接收一个lambda表达式block作为唯一参数，且将调用者本身作为参数传给了lambda。而在函数的内部，首先使用contract进行约束，向编译器表明这个lambda只会执行一次（EXACTLY_ONCE），接着就是调用lambda并返回其返回值。
进而，我们可以得出如下结论：

1. 由于let函数将调用者作为lambda的参数，因而在let闭包内，可以用it指代调用者；
2. let函数是具有返回值的，且其返回值应为lambda表达式中的最后一行/return语句。

随之，我们可以得到let函数的作用：

1. 在明确某一对象实例在一定范围内需要使用时，可以对其调用let，再用it指代；
2. （常用）对某一可能为空的对象进行统一判空的处理。

这里对作用二作一些解释。对于一个可能为空的对象object，如果不使用let，每次调用其方法或属性时，都要加上?或者!!，以及类似if not null的判空逻辑。但如果使用let，代码就将简化为如下的形式：

1
2
3
4

object?.let {
    it.doSomething()
    it.id = 0
}

以上代码表示，只有当object不为空时，才会执行let中的逻辑，且由于判空交给了object后的?符来处理，let内部不再需要任何多余的判空。如此以来，判空就变得优雅了许多。

(2)also

先上also函数的源码：

1
2
3
4
5
6
7

public inline fun <T> T.also(block: (T) -> Unit): T {
    contract {
        callsInPlace(block, InvocationKind.EXACTLY_ONCE)
    }
    block(this)
    return this
}

从源码可见，also函数的实现思路与let类似，都是对调用者的扩展，都是将调用者作为参数传给lambda，都使用contract进行调用约束，都会在内部执行lambda。但有如下不同：lambda没有返回值，而从return语句看，also返回的是调用者本身。
进而，我们可以得出如下结论：

1. also函数的应用场景与let相同；
2. also函数返回值为调用者本身。

(3)with

先上with函数的源码：

1
2
3
4
5
6

public inline fun <T, R> with(receiver: T, block: T.() -> R): R {
    contract {
        callsInPlace(block, InvocationKind.EXACTLY_ONCE)
    }
    return receiver.block()
}

虽然源码的整体风格和之前两者类似，但其使用方法却截然不同。首先，with是一个通用的扩展函数，其有两个参数：receiver，和一个lambda。注意这里lambda的参数是T.()，它表明将这个lambda函数作为同为类型T的receiver的一个扩展函数，从而能被receiver所调用。进而，我们可以得出如下结论：

1. 由于with内部是通过扩展函数使得receiver去调用lambda，因而可以在lambda的闭包内部直接访问receiver的public方法/属性。（即没有it等间接指代值）
2. with函数是具有返回值的。从源码的return语句可以看出，其返回的是lambda表达式的最后一行/return语句。

随之，我们可以得到with函数的作用：
在需要多次调用某一对象的方法或属性时，可以将该对象传给with，再在with内部处理相应逻辑。这样写可以避免多次重复地写该对象。
举个栗子：当我们想写一个alertDialog时，需要先创建builder，对builder进行一系列配置，再调用builder的create()方法返回一条alertDialog。有了with后，我们可以这样写：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

private lateinit var alertDialog: AlertDialog

...

val builder = AlertDialog.Builder(activity)
alertDialog = with (builder) {
    val alertView = layoutInflater.inflate(R.layout.dialog_confirm, null, false)
    setView(alertView)
    setNegativeButton("取消") { dialog, which ->
        Toast.makeText(activity, "已取消", Toast.LENGTH_SHORT).show()
    }
    setPositiveButton("确定") { dialog, which ->
        run {
            bill?.let { it1 -> viewModel.deleteBill(it1) }
            activity?.onBackPressed()
        }
    }
    create()
}

是不是简洁了许多？

(4)run

还是先上源码：

1
2
3
4
5
6
7
8
9
10
11
12
13

public inline fun <R> run(block: () -> R): R {
    contract {
        callsInPlace(block, InvocationKind.EXACTLY_ONCE)
    }
    return block()
}

public inline fun <T, R> T.run(block: T.() -> R): R {
    contract {
        callsInPlace(block, InvocationKind.EXACTLY_ONCE)
    }
    return block()
}

run有点类似let和with的结合体，继承了两者各自的优点，因而使用场景十分广泛：首先，它像let一样是对调用者的扩展，因而可以统一判空处理；其次，它又像with一样，传入lambda的是T.()，表明它可以像with一样在闭包内直接访问方法/属性。最后，它返回的是lambda的返回值。

(5)apply

上源码。。。

1
2
3
4
5
6
7

public inline fun <T> T.apply(block: T.() -> Unit): T {
    contract {
        callsInPlace(block, InvocationKind.EXACTLY_ONCE)
    }
    block()
    return this
}

不难看出，apply和run类似于also和let的关系，使用场景类似，只是返回值有差异。
而由于apply返回的是调用者本身，因而它十分适合用来做变量的初始化。

总结

作者纯kotlin小白，如有疏漏与错误，敬请大佬指正！

该篇内容为原博客博文，原上传于2022年4月30日。

话说从寒假开始半摸半读《CS:APP》，但是一直没有写Lab。都说9个Lab是全书的精华，因此深感有必要做一下，所以前阵子抽空先把DataLab做了。虽说是第一个（据说也是最简单的）Lab，却也做的磕磕绊绊，深感自己码力不足。总之最后是完成了，还是写篇博客记录一下，也方便自己日后review。

1分题

1分题基本都是签到题，难度不大。

bitXor

1
2
3
4
5
6
7
8
9
10

/* 
 * bitXor - x^y using only ~ and & 
 *   Example: bitXor(4, 5) = 1
 *   Legal ops: ~ &
 *   Max ops: 14
 *   Rating: 1
 */
int bitXor(int x, int y) {
  return ~(~(~x&y)&~(x&~y));
}

只使用位与和位非实现位或，运用De Morgan’s laws就行了。

tmin

1
2
3
4
5
6
7
8
9

/* 
 * tmin - return minimum two's complement integer 
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 4
 *   Rating: 1
 */
int tmin(void) {
  return 0x1 << 31;
}

返回补码表示的最小数，即0x8000_8000，也即int类型能表示的最小数，也没有什么好说的。

2分题

开始有些技巧性的操作出现了。

isTmax

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

/*
 * isTmax - returns 1 if x is the maximum, two's complement number,
 *     and 0 otherwise 
 *   Legal ops: ! ~ & ^ | +
 *   Max ops: 10
 *   Rating: 1
 */
int isTmax(int x) {
  int i = x + 1; // Tmin,1000...
  x = x + i; // -1,1111...
  x = ~x; // 0,0000...
  i = !i; // exclude x=0xffff...
  x = x + i; // exclude x=0xffff...
  return !x;
}

要求如果x是补码表示的最大数就返回1，否则返回0。
那么我们首先要能识别出补码最大数，并且能将其转化为0x1作为结果。显然0x7fff_ffff就是补码最大数，如何利用允许使用的运算符将其转化为0x1呢？这里就比较tricky了。我们可以取x + 1 + x，如果x是0x7fff_ffff时，将得到0xffff_ffff，即全1。对全1取位反即可得到0，再对0取逻辑非就能得到0x1了。
但这里有一个容易忽略的情形，即当x为0xffff_ffff时，由于溢出，x + 1 + x也能得到同样的结果（我是在btest时才发现这个特例），所以需要排除这个情形，使得只有当x=0x7fff_ffff时才能返回0x1。为此，我们可以不着急对0取逻辑非，而是先再对原来的x+1取逻辑非，再加给取位反后的x + 1 + x。当x为0x7fff_ffff时，这一步多出的操作不会对结果造成任何影响，因为此时x + 1取非后得到的是0，加个0显然不会有影响；但对于x为0xffff_ffff时，x + 1取非后得到的是1，加回去后得到1，再取逻辑非时就变成了0，从而排除了这个例外。

allOddBits

1
2
3
4
5
6
7
8
9
10
11
12
13
14

/* 
 * allOddBits - return 1 if all odd-numbered bits in word set to 1
 *   where bits are numbered from 0 (least significant) to 31 (most significant)
 *   Examples allOddBits(0xFFFFFFFD) = 0, allOddBits(0xAAAAAAAA) = 1
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 12
 *   Rating: 2
 */
int allOddBits(int x) {
  int mask = 0xAA + (0xAA << 8);
  mask = mask + (mask << 16); // mask = 0xAAAAAAAA
  x = mask & x;
  return !(~x & mask);
}

从0开始计位，若x所有奇数位都为1则返回1，否则返回0。
如何提取x的奇数位呢？显然用一个奇数位为1，偶数位为0的mask就行了，但我们不能直接用int mask = 0xAAAAAAAA构造出这个掩码，因为Lab要求整数实验的代码最多使用8位常数，如0xAA，所以我们首先要用0xAA产生0xAAAAAAAA，方法有很多，这里就不再赘述。再用这个mask与x位与，即可在结果的奇数位上对应得到x的奇数位。如何判定x的奇数位是否全为1呢？我们很容易想到如果如此，那么x位反后再与mask位与，应当得到全0，因为一个是奇数位全0，偶数位全1，另一个是奇数位全1，偶数位全0，没有一位是相等的。再对结果取逻辑非就能得到1。而对于不满足的x，检验可知经同样的运算，最终都会得到0。

negate

1
2
3
4
5
6
7
8
9
10

/* 
 * negate - return -x 
 *   Example: negate(1) = -1.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 5
 *   Rating: 2
 */
int negate(int x) {
  return ~x + 0x1;
}

返回x的相反数。只要对补码表示有基本了解，这题应该都是秒过，不再赘述。

3分题

难度更大了。。。

isAsciiDigit

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

/* 
 * isAsciiDigit - return 1 if 0x30 <= x <= 0x39 (ASCII codes for characters '0' to '9')
 *   Example: isAsciiDigit(0x35) = 1.
 *            isAsciiDigit(0x3a) = 0.
 *            isAsciiDigit(0x05) = 0.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 15
 *   Rating: 3
 */
int isAsciiDigit(int x) {
  // 考察如何使用位运算比较大小->不能直接用算术运算符，但思路依然是可以比较符号位->用位运算凑出符号位改变的临界数
  int sign = 0x1 << 31;
  int compH = ~(sign | 0x39); // 当与小于等于0x39的数相加后，符号位为0；当与大于0x39的数相加后，符号位变为1
  int compL = ~0x30; // 当与大于0x30的数相加后，符号位为0；当与小于等于0x30的数相加后，符号位变为1
  int sign_1 = ((compH + x) & sign) >> 31; // 当符号位为0时，得到sign_1为全0；当符号位为1时，得到sign_1为全1
  int sign_2 = ((compL + x + 0x1) & sign) >> 31; // 这里需要额外加个1，因为当x=0x30时，符号位仍为1，需要加1进位使其变为0.且加1不会对0x30之后的数的结果产生影响
  return !(sign_1 | sign_2); // 这里要用逻辑非来实现或非，因为最后要求的是返回0/1，而sign_1/2位或后仍是32位全0/1整数
}

若x是0~9数字的ASCII码表示，则返回1，否则返回0。
只要我们能比较x同0x30和0x39的大小就行了。如何用位运算比较两个数之间的大小呢？（我不道啊？看了别人的写法才懂）有一种比较tricky的处理方式，虽然这题不给用减法，但我们可以借鉴类似的想法，即自己构造出会使得符号位改变的临界数，再看符号位就行了。具体思路可以看代码注释。

conditional

1
2
3
4
5
6
7
8
9
10
11
12

/* 
 * conditional - same as x ? y : z 
 *   Example: conditional(2,4,5) = 4
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 16
 *   Rating: 3
 */
int conditional(int x, int y, int z) {
  int flag = !!x;
  int mask = ~flag + 1;
  return (y & mask) + (z & ~mask);
}

这里的难点在于如何从x的位级表示获取其一位布尔值，使用逻辑非即可。第一次逻辑非会把0转化为1，非0转化为0，第二次逻辑非会还原为原逻辑值，所以需要2次逻辑非。但我们不能直接用这个一位布尔值，因为要实现选择操作，用一位只能保留原输入的一位，显然是不对的，故还需经一步得到全1和全0，再做与操作。

isLessOrEqual

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

/* 
 * isLessOrEqual - if x <= y  then return 1, else return 0 
 *   Example: isLessOrEqual(4,5) = 1.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 24
 *   Rating: 3
 */
int isLessOrEqual(int x, int y) {
  int sign = 0x1 << 31;
  int sign_x = x & sign;
  int sign_y = y & sign;
  int sign_inequal = ((sign_x ^ sign_y) >> 31) & 0x1; // sign_inequal为0x1，表示符号不同；为0则表示符号相同
  int sign_diff = (y + ~x + 0x1) & sign; // y - x 的差值符号，当为0x1<<32时表示y<x，当为全0时表示y>=x。 有错误：当x为负，y为正时有可能溢出，因而不可靠。只有当符号相同时才可靠
  int same_res = !sign_diff;// 符号相同时的结果
  int diff_res = !sign_y;//符号不同时的结果，当y为正数时返回值就为1，否则返回0
  return (sign_inequal & diff_res) + (!sign_inequal & same_res);//符号不同时，即sign_equal为1时，返回diff_res；否则返回same_res
}

比较x,y大小，返回比较结果。
第一眼看，我们也许会想用isAsciiDigit的思路做这题，但这是不行的。因为上一题我们只考虑0x30~0x39这一正数小区间，而现在我们需要考虑整个实数域。用相同的方法处理y为负数时会出现问题。
这时就要回退到一般运算思路，即符号不同正数为大，符号相同看差值符号即可。获取差值时，这里不能直接用’-‘，故用补码方式。
x,y和y-x的符号不难获得，但难点在于如何通过位运算在符号不同时正确选择正的那一个数，思路可参见代码注释。

4分题

这几位更是重量级。

logicalNeg

1
2
3
4
5
6
7
8
9
10
11

/* 
 * logicalNeg - implement the ! operator, using all of 
 *              the legal operators except !
 *   Examples: logicalNeg(3) = 0, logicalNeg(0) = 1
 *   Legal ops: ~ & ^ | + << >>
 *   Max ops: 12
 *   Rating: 4 
 */
int logicalNeg(int x) {
  return ((x | (~x + 1)) >> 31) + 1;
}

实现逻辑非运算符。要做出这题，首先需要清楚C语言中的右移对于有符号数是算术右移，以及整数中的1000…0000表示最小数而不是表示负零。其次，还是要想办法将位级表示的x的信息用一个比特表示出来，之前我们都是用!!，但这题就是需要我们实现!，故得采取新的思路。想到对于0来说，其原码和补码都是0x0000，符号位相或仍为0；而对于非0数，其源码和补码的符号位必然互补，从而相或时为1，进而就可以区分0和非0数了。最终要求是求反，故再加1即可。
真正实现起来，一行代码即可搞定，但背后的思考过程不是那么容易，你得想到0和非0数各自相反数符号位的差异，才能做出这题。

howManyBits

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

/* howManyBits - return the minimum number of bits required to represent x in
 *             two's complement
 *  Examples: howManyBits(12) = 5
 *            howManyBits(298) = 10
 *            howManyBits(-5) = 4
 *            howManyBits(0)  = 1
 *            howManyBits(-1) = 1
 *            howManyBits(0x80000000) = 32
 *  Legal ops: ! ~ & ^ | + << >>
 *  Max ops: 90
 *  Rating: 4
 */
int howManyBits(int x) {
  int b16, b8, b4, b2, b1, b0; // 必须提前声明，否则dlc检查时会报错
  int sign = x >> 31; // 提取符号位，sign为全1或全0
  x = (sign & ~x) | (~sign & x); // 这一步是为了方便处理负数。对负数取反，将找0转化为找1，这样对于正负数就可以统一处理了
  //经上一行操作后，x符号位总为0，故算术右移不会造成影响
  b16 = !!(x >> 16) << 4; //考察高16位是否有1，若有，b16得16，否则得0，至少需要16位。
  x = x >> b16; //若高16位有1，则将x右移16位。对于b16=16，此为向左缩小搜索范围；对于b16=0，此为向右增大搜索范围
  b8 = !!(x >> 8) << 3; //考察高8位是否有1，若有，b16得8，否则得0，至少需要位数再加8位
  x = x >> b8; //继续缩小范围，考察高4位。下面以此类推。
  b4 = !!(x >> 4) << 2;
  x = x >> b4;
  b2 = !!(x >> 2) << 1;
  x = x >> b2;
  b1 = !!(x >> 1);
  b0 = x >> b1; // 最高两位是11时，所需位数还得加1
  return b16 + b8 + b4 + b2 + b1 + b0 + 1; // 符号位必定占一位
}

求用补码表示x至少需要几位。思路很好想，符号位必定占一位，剩下的从左往右找第一个有效位(正数是1，负数是0)，其与之后剩下的位都是需要的位。但是代码实在写不出来，就copy别人的代码了。
实际上代码的思路也很简单，就是在这串32位比特上做二分搜索（还能这样，艹），找到第一个有效位,同时统计比特数量。
这里还有一个小插曲，即使用的临时变量都必须在函数的一开始提前声明，不能在使用时才声明并初始化，否则dlc检查时会报错，说你没有声明变量。不太清楚原因。

floatScale2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

/* 
 * floatScale2 - Return bit-level equivalent of expression 2*f for
 *   floating point argument f.
 *   Both the argument and result are passed as unsigned int's, but
 *   they are to be interpreted as the bit-level representation of
 *   single-precision floating point values.
 *   When argument is NaN, return argument
 *   Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
 *   Max ops: 30
 *   Rating: 4
 */
unsigned floatScale2(unsigned uf) {
  int exp = (uf & 0x7f800000) >> 23; //exp低23位表示原数的阶码
  int sign = uf & 0x80000000; // sign最高位为原数符号位，其余位全为0
  if (exp == 255) return uf; // 无穷或NaN
  if (exp == 0) return sign | (uf << 1); // 非规格数
  if (++exp == 255) return sign | 0x7f800000; // 溢出，返回无穷大
  return (exp << 23) | (uf & 0x807fffff); // 规格数且无溢出
}

实现2*f。与前面的题相比，这题其实不难，只要认真读了书，知道浮点数的表示方法就能做出来。
若为规格数，直接阶码加1即可。但若阶码加1后变为全1，则返回的应是对应符号的无穷大。
若为非规格数，则直接左移1位并补上符号位即可。这是因为当非规格数的小数字段最高位为0时，直接左移1位仍表示为非规格数，且小数字段因左移而乘以2，自然得到了结果
当小数字段最高位为1时，左移1位会导致阶码变为0x1而成为规格数。但对规格数而言，0x1阶码与非规格数表示的指数相同，都为1-Bias。且虽然小数最高位看似丢失了，但规格数表示的尾数本身就是1+f，与非规格数的尾数f相比，相当于把最高位的1表示成十进制的0.5乘以2得到的1单独提取了出来，其余位左移自然乘以2。得益于IEEE浮点标准的这种非规格数平滑向规格数过渡的设计，我们这里处理非规格数也简单很多，不需要担心溢出。
若为无穷大和NaN，直接返回原数即可

floatFloat2Int

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

/* 
 * floatFloat2Int - Return bit-level equivalent of expression (int) f
 *   for floating point argument f.
 *   Argument is passed as unsigned int, but
 *   it is to be interpreted as the bit-level representation of a
 *   single-precision floating point value.
 *   Anything out of range (including NaN and infinity) should return
 *   0x80000000u.
 *   Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
 *   Max ops: 30
 *   Rating: 4
 */
int floatFloat2Int(unsigned uf) {
  int exp, E, tail, sign;
  if (!(uf & 0x7fffffff)) return 0; // 当uf为0，-0时，直接返回0即可。注意这个-0容易遗漏

  exp = (uf & 0x7f800000) >> 23;
  sign = uf & 0x80000000;
  tail = (uf & 0x007fffff) | 0x00800000; // 由于之后的代码会排除非规格数，故对规格数而言，真实的小数表示为尾数+1，这里与0x00800000相或就是为了加上小数点前的1

  E = exp - 127; // E表示由阶码复原得到的真实指数，注意E > 31时，必定在左移时覆盖掉符号位，所以会溢出。此时也包括了NaN和INF（E=255-127必然大于31）
  if (E > 31) return 0x80000000;
  if (E < 0) return 0; // 直观来理解，对于始终小于2的尾数，当E < 0时，相当于至少除以2，所得一定是个小于1的小数，故取0。非规格数也在这里被排除

  // 0 <= E <= 31时，依然有可能发生溢出，故需要做甄别并排除
  // 开始左移/右移。当E > 23时，说明乘法后所有小数点后的原尾数位都移到了小数点前，此时结果为一个整数，故直接左移即可。 当E < 23时， 说明乘法后仍含有小数部分，
  // 则转为Int时直接丢弃这些小数部分即可，对应的操作就是右移
  tail = (E > 23) ? tail << (E - 23) : tail >> (23 - E);
  // 原来是按位表示的1+小数，故对E>23来说，一开始乘2时会先移动小数点，故不会改变作为Int的各位数值。只有当超过23部分的E会导致数值开始乘2，即左移
  // 而对于E<23来说，无论如何都只会改变小数点而不改变数值，因而不会左移。但因为此时含有小数，故权值不是从0而是从某个负数开始，因而各位上的权值对应都会衰减，本应是右移23位来对上小数
  // 的权值，但因为有乘E次2的操作，每次乘2都会使权值对应升高1位，故会抵消E次右移操作，最终效果就是右移23-E位。同时在右移的过程中，还舍去了小数的信息。
  // 统一的解释：因为小数从左向右的权值是从-1开始的，而不是从0开始的，故对于原小数的位级表示，应首先右移23位来对上正确的权值(<<-23 or >>23)。
  // 但因为有乘E次2的操作，每次乘2都会使权值对应升高1位，故会抵消E次右移操作，最终效果就是右移23-E位(<<E-23 or >> 23-E)。同时注意在右移的过程中，还会舍去小数的信息。
  return sign ? -tail : tail; // 保留原符号
}

实现float到int强制类型转换。这题也没写出来，copy了网上代码，代码解释看注释就行。

floatPower2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

/* 
 * floatPower2 - Return bit-level equivalent of the expression 2.0^x
 *   (2.0 raised to the power x) for any 32-bit integer x.
 *
 *   The unsigned value that is returned should have the identical bit
 *   representation as the single-precision floating-point number 2.0^x.
 *   If the result is too small to be represented as a denorm, return
 *   0. If too large, return +INF.
 * 
 *   Legal ops: Any integer/unsigned operations incl. ||, &&. Also if, while 
 *   Max ops: 30 
 *   Rating: 4
 */
unsigned floatPower2(int x) {
  int exp = x + 127; // 加上bias得到位级表示的阶码
  // 阶码的范围是00000000~11111111，超出这个表示范围时，对应0(全0)和INF(0111_1111_1000_0...0)
  if (exp <= 0) return 0; // 极小数，当做0
  if (exp > 0xff) return 0x7f800000; // INF 
  return exp << 23;
}

实现2的幂次方运算。这题简单一点，首先由x加上bias得到对应浮点数的阶码。由于2的幂符号位为0，尾数也为全0，故再对阶码移位到浮点数对应的位置即可。注意要排除极小数和无穷，即超过阶码表示的数。

结果

这里有个小插曲，编译btest时提示不兼容的gcc。这是因为我的机器是x86-64，但Lab的makefile中添加了-m32参数，而我缺少在64位机器编译32位程序的库。这里可以选择修改makefile，把这个参数删去或者改为-m64，或者安装需要的库，有gcc-multilib和module-assistant。
测试结果如图。

碎碎念

从这个学期开始，我一直处于一种浑浑噩噩的状态，课内没学好，加权卷不上去，课外的知识也进度缓慢（包括但不限于CSAPP只读到了第四章，计算机视觉半熟不熟，几个月没写安卓）。最近看了许多大牛学长的博客和他们的经历分享，收获了很多，还是希望能向强者靠拢。开始做CSAPP的lab，也算是自己挣脱摆烂状态的一次尝试。希望自己能继续努力，保持学习吧！

该篇内容为原博客博文，原上传于2021年9月11日。

前言

提到Android中的消息机制，想必大家对其都不陌生。Android消息机制，一般指handler和其附加的mq及looper的运行机制与工作过程。handler常用于解决在子线程不能访问UI的问题，举一个常见的例子：我们在子线程中执行了耗时工作后，需要对UI进行更新，但又不能直接在子线程更新UI（这是因为控件在重绘前会调用checkThread()检查当前是否为主线程，以防ANR）。此时我们就可以创建handler，并将要执行的代码逻辑写入一个runnable任务中，并调用handler的post(本质上仍是调用send)或send将任务提交给主线程的消息队列中，再由主线程的looper取出这个任务，在主线程执行，如此便自然地从子线程转入主线程，实现了UI的更新。当然我们也可以直接调用Activity类的runOnUiThread()方法，道理是一样的。下面就让我们一起从源码的角度探究handler消息处理机制的原理，以及handler使用存在的一些问题。

handler的构造问题

handler有多个构造方法，我们常常用到的有以下几个：

1. 无参构造

1
2
3
4

@Deprecated
public Handler() {
    this(null, false);
}

这个构造方法已经弃用。其内部调用了另一个有参构造方法，但是传的值为null和false，让我们接下去看看：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

public Handler(@Nullable Callback callback, boolean async) {
    if (FIND_POTENTIAL_LEAKS) {
        final Class<? extends Handler> klass = getClass();
        if ((klass.isAnonymousClass() || klass.isMemberClass() || klass.isLocalClass()) &&
                (klass.getModifiers() & Modifier.STATIC) == 0) {
            Log.w(TAG, "The following Handler class should be static or leaks might occur: " +
                klass.getCanonicalName());
        }
    }

    mLooper = Looper.myLooper();
    if (mLooper == null) {
        throw new RuntimeException(
            "Can't create handler inside thread " + Thread.currentThread()
                    + " that has not called Looper.prepare()");
    }
    mQueue = mLooper.mQueue;
    mCallback = callback;
    mAsynchronous = async;
}

这里我们先解释一下这个构造方法的参数：callback是handler中定义的一个接口，用于简化构建handler的过程（可以用实现这个接口来避免自定义handler子类），下文再对这个接口做详细解释。这里传入值为null，说明我们不采用这种方式。async标志这个handler是否采用异步消息，下文再对handler的异步、普通和屏障消息作区别以及介绍同步屏障机制。这里传入false，说明我们默认采用的都是普通消息机制。
这个构造方法首先会通过FIND_POTENTIAL_LEAKS判断是否由可能存在的内存泄漏情况，如果有，则会输出日志警告我们。（不过我没有找到设置这个bool值为true的代码部分。。。）关于handler潜在的内存泄漏风险，下文会重点讨论。接着调用Looper.myLooper()尝试获取当前线程的looper。我们进入这个方法看看：

1
2
3

public static @Nullable Looper myLooper() {
    return sThreadLocal.get();
}

调用了sThreadLocal的get方法并返回。那么sThreadLocal是什么呢？找到定义如下：

static final ThreadLocal<Looper> sThreadLocal = new ThreadLocal<Looper>();

发现这是一个ThreadLocal变量。关于ThreadLocal这里不做过多介绍（计划单独写一篇博客研究一下ThreadLocal，毕竟也是一个十分重要的知识点）。这样以来就明确了：每个线程只能有最多一个looper，并且存储在threadLocal里。调用get便可以得到当前线程的looper。但是除了主线程以外（主线程的消息机制下文会重点讨论），线程默认是没有looper的，需要自己通过prepare创建。如此，get方法就有可能返回null。当返回null时，就会抛出异常。以上我们可以得出一个结论：使用无参构造方法，必须确保当前线程持有looper，否则就会导致异常抛出。因此，这个方法被废弃也就不足为奇了。相应地，google建议我们使用另一个构造方法代替：
2.

1
2
3

public Handler(@NonNull Looper looper) {
        this(looper, null, false);
    }

这个构造方法同样在内部调用了另一个构造方法：

1
2
3
4
5
6

public Handler(@NonNull Looper looper, @Nullable Callback callback, boolean async) {
    mLooper = looper;
    mQueue = looper.mQueue;
    mCallback = callback;
    mAsynchronous = async;
}

可见这里直接使用了参数指定的looper，并获得了其对应的消息队列。

MQ的工作原理

现在我们有了handler对象，并且这个handler内部持有某个线程的looper和messageQueue的对象。接着，就可以调用handler的send/post方法发送消息了。由于查看源码可以知道post方法本质上还是将runnable包装成message后调用send系列方法，所以这里就直接看send系列方法。譬如调用sendMessage方法：

1
2
3

public final boolean sendMessage(@NonNull Message msg) {
    return sendMessageDelayed(msg, 0);
}

内部调用了另一个方法sendMessageDelayed。由此可见，我们也可以直接调用sendMessageDelayed并指定一个延迟时间，实现定时任务的效果。走进这个方法:

1
2
3
4
5
6

public final boolean sendMessageDelayed(@NonNull Message msg, long delayMillis) {
    if (delayMillis < 0) {
        delayMillis = 0;
    }
    return sendMessageAtTime(msg, SystemClock.uptimeMillis() + delayMillis);
}

又调用了另一个方法sendMessageAtTime。走进这个方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89

    public boolean sendMessageAtTime(@NonNull Message msg, long uptimeMillis) {
        MessageQueue queue = mQueue;
        if (queue == null) {
            RuntimeException e = new RuntimeException(
                    this + " sendMessageAtTime() called with no mQueue");
            Log.w("Looper", e.getMessage(), e);
            return false;
        }
        return enqueueMessage(queue, msg, uptimeMillis);
    }
```    
可以看见，首先方法试图获取一个消息队列，如果获取不到则会发出警告并返回false，那么消息则发送失败，不了了之。否则，接下来会调用enqueueMessage方法，走进这个方法：
```java
    private boolean enqueueMessage(@NonNull MessageQueue queue, @NonNull Message msg,
            long uptimeMillis) {
        msg.target = this;
        msg.workSourceUid = ThreadLocalWorkSource.getUid();

        if (mAsynchronous) {
            msg.setAsynchronous(true);
        }
        return queue.enqueueMessage(msg, uptimeMillis);
    }
```    
直接看最后一行，发现经过一系列方法，最终调用的是消息队列的enqueueMessage方法，也是消息队列工作较为重要的一个方法。走进这个方法：
```java
    boolean enqueueMessage(Message msg, long when) {
            if (msg.target == null) {
                throw new IllegalArgumentException("Message must have a target.");
            }

            synchronized (this) {
                if (msg.isInUse()) {
                    throw new IllegalStateException(msg + " This message is already in use.");
                }

                if (mQuitting) {
                    IllegalStateException e = new IllegalStateException(
                            msg.target + " sending message to a Handler on a dead thread");
                    Log.w(TAG, e.getMessage(), e);
                    msg.recycle();
                    return false;
                }

                msg.markInUse();
                msg.when = when;
                Message p = mMessages;
                boolean needWake;
                if (p == null || when == 0 || when < p.when) {
                    // New head, wake up the event queue if blocked.
                    msg.next = p;
                    mMessages = msg;
                    needWake = mBlocked;
                } else {
                    // Inserted within the middle of the queue.  Usually we don't have to wake
                    // up the event queue unless there is a barrier at the head of the queue
                    // and the message is the earliest asynchronous message in the queue.
                    needWake = mBlocked && p.target == null && msg.isAsynchronous();
                    Message prev;
                    for (;;) {
                        prev = p;
                        p = p.next;
                        if (p == null || when < p.when) {
                            break;
                        }
                        if (needWake && p.isAsynchronous()) {
                            needWake = false;
                        }
                    }
                    msg.next = p; // invariant: p == prev.next
                    prev.next = msg;
                }

                // We can assume mPtr != 0 because mQuitting is false.
                if (needWake) {
                    nativeWake(mPtr);
                }
            }
            return true;
        }
```        
虽然上面的代码比较长，但其实只做了一件很简单的事情：向消息队列插入当前消息。
首先，我们要了解消息队列底层采用的数据结构。虽然称作队列，其本质上只是一个普通的单链表。这点可从message类的源码印证：
```java
  ...
    // sometimes we store linked lists of these things
        @UnsupportedAppUsage
        /*package*/ Message next;
  ...

每个message对象都有一个next指针域。
enqueueMessage首先会对一些特殊情况进行处理，接着上了synchronize保证对链表的访问是线程安全的。接着分两种情况：第一次插入，唤醒阻塞的队列并创建新头，插入第一条消息，否则就尾插到链表尾部。
那么，looper是如何取出mq中的消息的呢？这里就要调用另一个方法next()了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105

Message next() {
    // Return here if the message loop has already quit and been disposed.
    // This can happen if the application tries to restart a looper after quit
    // which is not supported.
    final long ptr = mPtr;
    if (ptr == 0) {
        return null;
    }

    int pendingIdleHandlerCount = -1; // -1 only during first iteration
    int nextPollTimeoutMillis = 0;
    for (;;) {
        if (nextPollTimeoutMillis != 0) {
            Binder.flushPendingCommands();
        }

        nativePollOnce(ptr, nextPollTimeoutMillis);

        synchronized (this) {
            // Try to retrieve the next message.  Return if found.
            final long now = SystemClock.uptimeMillis();
            Message prevMsg = null;
            Message msg = mMessages;
            if (msg != null && msg.target == null) {
                // Stalled by a barrier.  Find the next asynchronous message in the queue.
                do {
                    prevMsg = msg;
                    msg = msg.next;
                } while (msg != null && !msg.isAsynchronous());
            }
            if (msg != null) {
                if (now < msg.when) {
                    // Next message is not ready.  Set a timeout to wake up when it is ready.
                    nextPollTimeoutMillis = (int) Math.min(msg.when - now, Integer.MAX_VALUE);
                } else {
                    // Got a message.
                    mBlocked = false;
                    if (prevMsg != null) {
                        prevMsg.next = msg.next;
                    } else {
                        mMessages = msg.next;
                    }
                    msg.next = null;
                    if (DEBUG) Log.v(TAG, "Returning message: " + msg);
                    msg.markInUse();
                    return msg;
                }
            } else {
                // No more messages.
                nextPollTimeoutMillis = -1;
            }

            // Process the quit message now that all pending messages have been handled.
            if (mQuitting) {
                dispose();
                return null;
            }

            // If first time idle, then get the number of idlers to run.
            // Idle handles only run if the queue is empty or if the first message
            // in the queue (possibly a barrier) is due to be handled in the future.
            if (pendingIdleHandlerCount < 0
                    && (mMessages == null || now < mMessages.when)) {
                pendingIdleHandlerCount = mIdleHandlers.size();
            }
            if (pendingIdleHandlerCount <= 0) {
                // No idle handlers to run.  Loop and wait some more.
                mBlocked = true;
                continue;
            }

            if (mPendingIdleHandlers == null) {
                mPendingIdleHandlers = new IdleHandler[Math.max(pendingIdleHandlerCount, 4)];
            }
            mPendingIdleHandlers = mIdleHandlers.toArray(mPendingIdleHandlers);
        }

        // Run the idle handlers.
        // We only ever reach this code block during the first iteration.
        for (int i = 0; i < pendingIdleHandlerCount; i++) {
            final IdleHandler idler = mPendingIdleHandlers[i];
            mPendingIdleHandlers[i] = null; // release the reference to the handler

            boolean keep = false;
            try {
                keep = idler.queueIdle();
            } catch (Throwable t) {
                Log.wtf(TAG, "IdleHandler threw exception", t);
            }

            if (!keep) {
                synchronized (this) {
                    mIdleHandlers.remove(idler);
                }
            }
        }

        // Reset the idle handler count to 0 so we do not run them again.
        pendingIdleHandlerCount = 0;

        // While calling an idle handler, a new message could have been delivered
        // so go back and look again for a pending message without waiting.
        nextPollTimeoutMillis = 0;
    }
}

这段代码中涉及到许多值得注意的地方，比如同步屏障机制的实现等。但目前我们只关心next()方法的主要作用：取出消息队列中下一个消息。核心代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

final long now = SystemClock.uptimeMillis();
Message prevMsg = null;
Message msg = mMessages;
if (msg != null && msg.target == null) {
    // Stalled by a barrier.  Find the next asynchronousmessage in the queue.
    do {
        prevMsg = msg;
        msg = msg.next;
    } while (msg != null && !msg.isAsynchronous());
}
if (msg != null) {
    if (now < msg.when) {
        // Next message is not ready.  Set a timeout to wake up when it is ready.
        nextPollTimeoutMillis = (int) Math.min(msg.when - now, Integer.MAX_VALUE);
    } else {
        // Got a message.
        mBlocked = false;
        if (prevMsg != null) {
            prevMsg.next = msg.next;
        } else {
            mMessages = msg.next;
        }
        msg.next = null;
        if (DEBUG) Log.v(TAG, "Returning message: " + msg);
        msg.markInUse();
        return msg;
    }
} else {
    // No more messages.
    nextPollTimeoutMillis = -1;
}

// Process the quit message now that all pending messages have been handled.
if (mQuitting) {
    dispose();
    return null;
}

首先获取了当前系统时间now。接着开始遍历消息队列。如果遇到屏障，则跳过普通消息寻找下一个异步消息（暂且不管）。而如果遍历到的消息的when字段大于当前时间，说明这个消息还未准备好，于是不先取出而是设置了一个唤醒时间，等到时间时再取出。否则，取出当前消息，并返回给调用者（looper）。而如果迟迟没有返回，消息队列就会设置nextPollTimeoutMillis为-1，并无限循环地阻塞下去，直到取出并返回可用的消息。最后是消息队列退出时的一些善后操作。
如此以来，消息队列的工作原理我们就大致清晰了。

Looper的工作原理

handler负责发送和接收消息，message queue负责按FIFO方式存储消息，而looper则负责无限期地从mq中取出消息并分发给handler。looper的核心方法是loop()。
我们先了解一些looper类的字段：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

@UnsupportedAppUsage
static final ThreadLocal<Looper> sThreadLocal = new ThreadLocal<Looper>();
@UnsupportedAppUsage
private static Looper sMainLooper;  // guarded by Looper.class
private static Observer sObserver;

@UnsupportedAppUsage
final MessageQueue mQueue;
final Thread mThread;
private boolean mInLoop;

@UnsupportedAppUsage
private Printer mLogging;
private long mTraceTag;

其中sThreadLocal我们已经不陌生了，用来保存不同线程的Looper对象；sMainLooper是主线程的looper，这个比较特殊。sObserver是用来处理事务的观察者（暂且不管）。mQueue用来保存消息队列，mThread是当前工作线程。mInLoop标记looper正在工作当中。mLogging是日志工具。

前面已经提到，每一个线程必须先构造looper，消息机制才能正常工作。那么我们就来看一看Looper的构造方法：

1
2
3
4

private Looper(boolean quitAllowed) {
    mQueue = new MessageQueue(quitAllowed);
    mThread = Thread.currentThread();
}

可见这里就是简单地构造了looper对应的消息队列，并保存了当前的线程对象。值得注意的是，这个唯一的构造方法是私有的，说明我们不能直接通过new获取一个looper。相反，我们需要调用prepare()方法：

1
2
3
4
5
6
7
8
9
10

public static void prepare() {
    prepare(true);
}

private static void prepare(boolean quitAllowed) {
    if (sThreadLocal.get() != null) {
        throw new RuntimeException("Only one Looper may be created per thread");
    }
    sThreadLocal.set(new Looper(quitAllowed));
}

在prepare方法中，我们会先尝试从threadLocal中获取looper，看看当前线程是否已经有looper了。如果有，将会抛出异常，以此保证每个线程只能持有最多一个looper对象。如果没有，就会构造looper并放入threadLocal中。

前面我们反复提到了主线程looper的特殊性。实际上，Looper类还提供了一个prepareMainLooper()方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145

    @Deprecated
    public static void prepareMainLooper() {
        prepare(false);
        synchronized (Looper.class) {
            if (sMainLooper != null) {
                throw new IllegalStateException("The main Looper has already been prepared.");
            }
            sMainLooper = myLooper();
        }
    }
```    
这个方法原本用于让ActivityThread创建主线程looper，但现在安卓环境会自己帮你创建，于是这个方法就被废弃了。现在，我们只需要知道主线程looper是系统自身已经创建好的，不需要自己再调用prepare方法创建。
下面我们开始介绍loop()方法。只有调用了loop()，消息循环才能真正起作用。
```java
    public static void loop() {
        final Looper me = myLooper();
        if (me == null) {
            throw new RuntimeException("No Looper; Looper.prepare() wasn't called on this thread.");
        }
        if (me.mInLoop) {
            Slog.w(TAG, "Loop again would have the queued messages be executed"
                    + " before this one completed.");
        }

        me.mInLoop = true;
        final MessageQueue queue = me.mQueue;

        // Make sure the identity of this thread is that of the local process,
        // and keep track of what that identity token actually is.
        Binder.clearCallingIdentity();
        final long ident = Binder.clearCallingIdentity();

        // Allow overriding a threshold with a system prop. e.g.
        // adb shell 'setprop log.looper.1000.main.slow 1 && stop && start'
        final int thresholdOverride =
                SystemProperties.getInt("log.looper."
                        + Process.myUid() + "."
                        + Thread.currentThread().getName()
                        + ".slow", 0);

        boolean slowDeliveryDetected = false;

        for (;;) {
            Message msg = queue.next(); // might block
            if (msg == null) {
                // No message indicates that the message queue is quitting.
                return;
            }

            // This must be in a local variable, in case a UI event sets the logger
            final Printer logging = me.mLogging;
            if (logging != null) {
                logging.println(">>>>> Dispatching to " + msg.target + " " +
                        msg.callback + ": " + msg.what);
            }
            // Make sure the observer won't change while processing a transaction.
            final Observer observer = sObserver;

            final long traceTag = me.mTraceTag;
            long slowDispatchThresholdMs = me.mSlowDispatchThresholdMs;
            long slowDeliveryThresholdMs = me.mSlowDeliveryThresholdMs;
            if (thresholdOverride > 0) {
                slowDispatchThresholdMs = thresholdOverride;
                slowDeliveryThresholdMs = thresholdOverride;
            }
            final boolean logSlowDelivery = (slowDeliveryThresholdMs > 0) && (msg.when > 0);
            final boolean logSlowDispatch = (slowDispatchThresholdMs > 0);

            final boolean needStartTime = logSlowDelivery || logSlowDispatch;
            final boolean needEndTime = logSlowDispatch;

            if (traceTag != 0 && Trace.isTagEnabled(traceTag)) {
                Trace.traceBegin(traceTag, msg.target.getTraceName(msg));
            }

            final long dispatchStart = needStartTime ? SystemClock.uptimeMillis() : 0;
            final long dispatchEnd;
            Object token = null;
            if (observer != null) {
                token = observer.messageDispatchStarting();
            }
            long origWorkSource = ThreadLocalWorkSource.setUid(msg.workSourceUid);
            try {
                msg.target.dispatchMessage(msg);
                if (observer != null) {
                    observer.messageDispatched(token, msg);
                }
                dispatchEnd = needEndTime ? SystemClock.uptimeMillis() : 0;
            } catch (Exception exception) {
                if (observer != null) {
                    observer.dispatchingThrewException(token, msg, exception);
                }
                throw exception;
            } finally {
                ThreadLocalWorkSource.restore(origWorkSource);
                if (traceTag != 0) {
                    Trace.traceEnd(traceTag);
                }
            }
            if (logSlowDelivery) {
                if (slowDeliveryDetected) {
                    if ((dispatchStart - msg.when) <= 10) {
                        Slog.w(TAG, "Drained");
                        slowDeliveryDetected = false;
                    }
                } else {
                    if (showSlowLog(slowDeliveryThresholdMs, msg.when, dispatchStart, "delivery",
                            msg)) {
                        // Once we write a slow delivery log, suppress until the queue drains.
                        slowDeliveryDetected = true;
                    }
                }
            }
            if (logSlowDispatch) {
                showSlowLog(slowDispatchThresholdMs, dispatchStart, dispatchEnd, "dispatch", msg);
            }

            if (logging != null) {
                logging.println("<<<<< Finished to " + msg.target + " " + msg.callback);
            }

            // Make sure that during the course of dispatching the
            // identity of the thread wasn't corrupted.
            final long newIdent = Binder.clearCallingIdentity();
            if (ident != newIdent) {
                Log.wtf(TAG, "Thread identity changed from 0x"
                        + Long.toHexString(ident) + " to 0x"
                        + Long.toHexString(newIdent) + " while dispatching to "
                        + msg.target.getClass().getName() + " "
                        + msg.callback + " what=" + msg.what);
            }

            msg.recycleUnchecked();
        }
    }
```java
提取出核心代码，其实loop的工作非常简单：
```java
    for (;;) {
        Message msg = queue.next(); // might block
        if (msg == null) {
            // No message indicates that the message queue is quitting.
            return;
        }
    }

就是无限循环地调用mq的next()方法，直到mq退出返回Null。什么时候mq返回null呢？当looper调用quit方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

    public void quit() {
        mQueue.quit(false);
    }
```    
会接着调用mq的quit:
```java
    void quit(boolean safe) {
        if (!mQuitAllowed) {
            throw new IllegalStateException("Main thread not allowed to quit.");
        }

        synchronized (this) {
            if (mQuitting) {
                return;
            }
            mQuitting = true;

            if (safe) {
                removeAllFutureMessagesLocked();
            } else {
                removeAllMessagesLocked();
            }

            // We can assume mPtr != 0 because mQuitting was previously false.
            nativeWake(mPtr);
        }
    }
```    
这里将消息队列的mQuitting设置为了true。再看next()中的一段代码：
```java
    // Process the quit message now that all pending messages have been handled.
    if (mQuitting) {
        dispose();
        return null;
    }

由此可见，looper调用quit时，mq就会退出。消息循环终止。
现在，我们有了looper，当Looper从mq中取出了一条消息时，就会对其进行处理：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

    msg.target.dispatchMessage(msg);
```    
其中，msg.target就是发送这条消息的对象。也就是说，当我们使用handler发送一条消息后，这条消息经过放入mq，再被looper取出，又被looper分发给了同一个handler。只不过handler对象虽然是同一个，发送和接收消息时所处的线程却不一定相同。下面我们一探handler的dispatchMessage()方法：

# Handler的工作原理
如何使用handler发送消息，已经在介绍MQ时说过了。我们主要看一看handler是如何处理Looper取出的消息的：
```java
    public void dispatchMessage(@NonNull Message msg) {
        if (msg.callback != null) {
            handleCallback(msg);
        } else {
            if (mCallback != null) {
                if (mCallback.handleMessage(msg)) {
                    return;
                }
            }
            handleMessage(msg);
        }
    }

首先会检查消息中的callback是否为空，这里callback就是通过post方式提交的runnable对象。如果不为空，进一步调用handleCallback()方法，这个方法也很简单：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

    private static void handleCallback(Message message) {
        message.callback.run();
    }
```    
就是执行runnable的run方法，完成其中的任务。
如果callback为空，会接着检查mCallback是否为空。前面我们已经介绍过，mCallback是handler内部定义的一个接口，提供了另一种使用Handler的方式：Handler handler = new Handler(Callback)，这时就会按照callback内部的处理逻辑（自己在创建时实现）来处理方法。最后，如果mCallback为空，说明处理的是普通的message。调用handleMessage(必须在创建handler时重写，默认是一个空的方法)来处理即可。
这样，我们就大致搞清楚了handler消息机制的主要工作原理，即handler,mq,looper三大件各自的作用及使用方法。handler使用简单，快捷，但也存在一个一直为人诟病的潜在问题：**内存泄露**。下面我们就来探讨handler引发内存泄露的问题和常用的解决方案。
# Handler内存泄漏
众所周知在java中，成员对象会默认隐式地持有外部类的对象。假设现在我们在MainActivity中创建了一个handler对象，那么这个handler也就持有了MainActivity的引用。现在考虑这样一种情况：如果向handler提交了一组任务，当handler还在处理任务的时候退出MainActivity会怎么样？
正常来说，MainActivity应该被回收并释放。但由于此时handler仍在处理正在进行的任务而存在，其持有MainActivity的引用，导致gc无法及时对MainActivity进行回收。如此一来，便发生了内存泄露。
通常情况下，handler的内存泄露都是暂时的，当其中的任务全部处理完毕时，内存还是会得到释放。但有问题就应该解决，以防止更大的问题产生。如何规避这种情况呢？
首先我们可以想到，将handler加上static修饰，**变成静态内部类**，这样handler就不会再隐式持有activity的引用了。但是这样，就又产生了一个问题：静态的handler无法访问activity实例，如果要用到activity的资源怎么办？
方法很简单，让handler持有外部activity的**弱引用**不就好了？弱引用会在遇到gc时被回收，这样就基本上解决了问题。
最后，我们上一个演示实例。假设现在有这样一个需求：进入app时展示欢迎界面，一段时间后跳转至另一界面。一个简单的实现是准备两个activity，用handler实现定时intent跳转。
我们采用自定义handler的方式：
```java
    static class MyHandler extends Handler {
        WeakReference<WelcomeActivity> mactivity;

        public MyHandler(@NonNull Looper looper, WelcomeActivity activity){
            super(looper);//调用父类的显式指明的构造函数
            mactivity = new WeakReference<WelcomeActivity>(activity);
        }

        @Override
        public void handleMessage(Message msg) {
            super.handleMessage(msg);

            WelcomeActivity nactivity = mactivity.get();
            if(nactivity == null)
                return ;

            switch (msg.what) {
                case 0:
                    Intent intent = new Intent(mactivity.get(), LoginActivity.class);
                    mactivity.get().startActivity(intent);
                    mactivity.get().finish();
                    break;
                default:
                    break;
            }
        }
    }

可以看到我这里就采用了static和weakReference来避免内存泄露和引用activity。创建handler实例后，在activity的onCreate()中调用handler.sendEmptyMessageDelayed(0,3000);即可实现功能。

结语

handler消息机制是android开发重要的功能，需要我们清楚其原理和实现。
这是我第一次尝试自主分析源码，因此文章中可能存在错误，以及一些理解不够深入。欢迎大佬提出问题并指正！

该篇内容为原博客博文，原上传于2021年11月27日。

一、前言 Docker是什么？

Docker takes away repetitive, mundane configuration tasks and is used throughout the development lifecycle for fast, easy and portable application development - desktop and cloud. Docker’s comprehensive end to end platform includes UIs, CLIs, APIs and security that are engineered to work together across the entire application delivery lifecycle.

Docker是一个用Go编写的开源工具，它可以将你的应用打包成一个标准格式的镜像，并且以容器的方式运行。Docker容器将一系列软件包装在一个完整的文件系统中，这个文件系统包含应用程序运行所需要的一切：代码、运行时工具、系统工具、系统依赖，几乎有任何可以安装在服务器上的东西。这些策略保证了容器内应用程序运行环境的稳定性，不会被容器外的系统环境所影响。

Docker容器的特点：

1. 轻量： 在同一台宿主机上的容器将共享系统kernel，使得它们可以迅速启动而且占用较少的内存。镜像是以分层文件系统构造的，这可以让它们共享相同的文件，使得磁盘使用率和镜像下载速度都得到较大提高。
2. 开放： Docker容器基于开放标准，使得其可以运行在各种主流Linux Distribution和Windows，以及Mac OS上。
3. 安全： 容器将各个运行的应用程序相互隔离开来，给所有的应用程序提供了一层额外的安全防护。

容器和虚拟机相比

容器和虚拟机同样具有资源隔离和分配的功能，但由于其架构的不同，容器比虚拟机更加便捷和高效。
首先是犯下傲慢之罪的虚拟机，包含用户的程序，必要的函数库和整个客户操作系统，至少也需要占用好几个GB的空间。如图所示，除了使用Hypervisor技术对硬件设施进行虚拟化外，虚拟机还多一层guest OS。
而docker容器则是在docker engine的控制和驱动下，以用户态运行，并在宿主机上互相隔离。docker直接使用硬件资源和共享内核，不和任何基础设施绑定。

容器基本概念

我们还是先回顾一波docker中的基础概念。

二、docker的基本使用

以一个精简的UNIX工具箱busybox为例

docker pull busybox
从仓库拉取latest的busybox镜像

docker images
查看本地镜像

docker rmi -f busybox
强制删除busybox镜像

docker run -it ubuntu /bin/bash
从镜像生成一个容器，分配伪终端，并采用交互模式运行，且在进入容器后执行/bin/bash

docker ps
查看所有正在运行的容器，加参数-a还可以查看停运的容器

docker start busybox
启动停止运行的容器busybox

docker stop busybox
停止正在运行的容器busybox

docker restart busybox
重启容器busybox

docker kill busybox
杀死运行中的容器busybox

docker rm -f busybox
移除容器busybox

docker pause busybox
暂停容器中所有进程

docker unpause busybox
暂停后继续容器中所有进程

docker create busybox
创建一个容器但是不启动

docker exec -it busybox /bin/bash
在正在运行的容器中执行/bin/bash这个命令
这也是进入运行中容器的一种方法

and so on……

二、Docker实现原理探究

那么，docker是如何生成这样精简而健全的一个个容器的呢？今天，我们就来研究一波其中运用到的三个主要的功能：Linux namespace, cgroups, Union File System(UFS)。下面我们一一进行探讨。

Linux namespace

本来，不同的进程是共享同一份内核资源的。要做一个通俗的类比的话，如果说每个进程是单独的一个住户，那么内核资源就好比是小区里的公共场所，大家都可以使用，且使用情况对彼此都可见。而ns的作用，就是把这样的公共场所隔离开来。但这里的隔离，说的并不是将公共场所分成几部分，交给不同的进程，而是每个进程依然有原来一样大的公共场所，公共场所中的资源和变更情况只有他自己能看到。如果他在公共场所丢了一根烟头，则只有他自己知道，其他人（进程）是感知不到的。
Linux Namespace就是这样提供了一种内核级别隔离系统资源的方法，通过将系统的全局资源放在不同的Namespace中，来实现资源隔离的目的。不同Namespace的程序，可以享有一份独立的系统资源。

namespace的API有如下3个syscall:

• clone() 创建新进程，并根据传入的系统调用参数判断那些类型的namespace被创建，并且其子进程也会包含到这些namespace中。
• unshare() 将进程移出某个namespace。
• setns() 将进程加入某个namespace。

目前Linux中提供了六类系统资源的隔离机制，分别是：

• Mount: 隔离文件系统挂载点
• UTS: 隔离主机名和域名信息
• IPC: 隔离进程间通信
• PID: 隔离进程的ID
• Network: 隔离网络资源
• User: 隔离用户和用户组的ID
• Cgroup: 隔离cgroup根目录（最新，尚未被docker采用）
  下面一一解释他们的作用：

Mount namespace

Mount Namespace用来隔离各个进程看到的挂载点视图。不同namespace的进程，看到的文件系统层次是不同的。在mount namespace中调用mount, umount等命令只会影响当前namespace内的文件系统，而对全局的文件系统是没有影响的。（事实上，docker容器内的挂载情况确实和宿主机不同。）
Mount Namespace是linux第一个实现的namespace类型，因而它的syscall参数比较特殊，是NEWNS。

但是有一点需要注意：有些时候，Mount Namespace其实并不能真正隔离挂载信息！这是因为linux中还存在一种名为Shared Subtree的机制！
引入该机制是为了消除mount ns带来的不便，比如系统新增一块磁盘，我希望所有的NS都感知到新挂载的这块磁盘，那么如果NS 之间是完全隔离的，就需要每个都执行一次挂载操作，这是非常不变的，shared subtree保证了不同的NS 之间可以共享挂载信息。
共享子树有两大核心：peer group和propagate type。

• peer group
  表示了一个或多个挂载点的集合，下面两种情况属于统一group：

通过–bind操作挂载的源挂载点和目标挂载点（前提是源目录是个挂载点）
生成新mount ns时，复制过去的挂载点之间同在一个group

• propagate type(传播属性)
  这是mount点的属性，其常见值有：

1. MS_SHARED 该挂载点的删除操作、该挂载点下子挂载点的新增和删除操作都会同步到同一group中的其他mount点，且其他同group的mount点的操作也会同步到该mount点
2. MS_PRIVATE 与1相反，不会将自己的信息共享出去，也不接受其他点的共享，从而实现真正的隔离
3. MS_SLAVE 单向的共享，自己的更新不会影响到他人，但是他人的操作会同步到自己

通过以下命令当前挂载点的传播属性：
cat /proc/self/mountinfo
可以发现所有进程默认情况下都是shared的。又因为通过系统调用clone出的namespace与父进程处在一个peer group下，所以会完全copy父进程的挂载点信息，因此子进程的挂载点也是shared。如果不注意到这点的话，创建的容器就不会真正隔绝挂载信息，且会引起一些不妙的后果。我们放在后面构建简单docker容器的实战中再说这个bug。

UTS namespace

UTS namespace主要用来nodename和domainname两个系统标识。也就是说，每个UTS Namespace被允许有自己的主机名（docker网络通信的重要基础之一）。
我们可以通过一个简单的Go语言demo来验证UTS namespace的作用：

func main() {
    cmd := exec.Command("sh")//指定新进程的初始命令
    cmd.SysProcAttr = &syscall.SysProcAttr {
        CloneFlags: syscall.CLONE_NEWUTS,
    }//设定系统调用属性
    cmd.Stdin = os.Stdin
    cmd.Stdout = os.Stdout
    cmd.Stderr = os.Stderr//设置标准输入输出

    if err := cmd.Run(); err != nil {
        log.Fatal(err)
    }//运行命令和错误处理
}

执行代码，在启动的交互式环境里，先用echo $$输出一下当前进程的PID，再用pstree -pl查看进程树，找到父进程。由于在进程目录下的ns目录包含进程的namespace信息，其中uts就对应 UTS namespace的信息。且由于ns目录下的这些文件其实都是特殊的符号链接，所以需要用readlink读取其实际指向的内容，便可以知道其UTS namespace的inode号了。于是用readlink /proc/xxxxx/ns/uts比较ns的inode，可以验证他们不在同一个UTS Namespace中。
接着，执行hostname -b chenpeng，修改当前主机名。另外启动一个shell，使用hostname命令，会发现外部的hostname并未因内部的修改而改变，证明了UTS Namespace的作用。
其他namespace的作用可以类似地验证，接下来就主要介绍他们的作用即可。

IPC Namespace

用来隔离System V IPC和POSIX message queues。

PID Namespace

用来隔离进程ID。同样一个进程在不同的PID Namespace中可以拥有不同的PID。可以通过分别在宿主机和容器内执行ps -ef验证docker对这个namespace的运用。

User Namespace

用来隔离用户的用户组ID。也就是说，一个进程的User ID和Group ID在User Namespace内外可以是不同的。比如在宿主机上的以非root用户运行创建一个User Namespace，而在namespace里面这个用户被映射为root用户。这意味着，这个进程在User Namespace里拥有root权限，但在外面却没有。从Linux Kernel 3.8开始，非root进程也可以创建User Namespace并被映射成root。

Netwoek Namespace

用来隔离网络设备、IP地址端口等网络栈。可以让每个容器拥有自己独立的虚拟网络设备，且容器内的应用可以绑定到自己的端口，使得各个Namespace内的端口不会互相冲突。且在宿主机上搭建网桥后，可以很方便地实现容器间通信。此外，通过端口映射，可以使得不同容器上的应用使用相同的端口号。

Linux Cgroups

namespace技术可以帮助构建出的容器拥有自己与外部隔离的单独的空间，但Docker是如何限制每个容器所占空间的大小，从而保证它们不会相互争抢的呢？这就要运用Cgroups技术。
Linux Cgroups（Control Groups）提供了对一组进程及其将来子进程的资源限制、控制和统计的能力，这些资源包括CPU,内存，存储，网络等。通过Cgroups，可以方便地限制某个进程的资源占用，并且实时地监控进程和统计信息。
比如可以通过cgroup限制特定进程使用特定数目的cpu核数和特定大小的内存，如果资源超限的情况下，会被暂停或者杀掉。

• 任务(task): 在cgroups中，task就是一个进程或线程。
• 控制组(control group): cgroups的资源控制是以cgroup的方式实现，cgroup指明了资源的配额限制。进程可以加入到某个cgroup，也可以迁移到另一个cgroup。
• 层级(hierarchy): cgroup有层级关系，类似树的结构，子节点的cgroup继承父cgroup的属性(资源配额、限制等)。
• 子系统(subsystem): 一个subsystem其实就是一种资源的控制器，比如memory subsystem可以控制进程内存的使用。subsystem需要加入到某个hierarchy，然后该hierarchy的所有cgroup，均受到这个subsystem的控制。
  subsystem的类别：
  • cpu: 限制进程的 cpu 使用率。
  • cpuacct 子系统，可以统计 cgroups 中的进程的 cpu 使用报告。
  • cpuset: 为cgroups中的进程分配单独的cpu节点或者内存节点。
  • memory: 限制进程的memory使用量。
  • blkio: 限制进程的块设备io。
  • devices: 控制进程能够访问某些设备。
  • net_cls: 标记cgroups中进程的网络数据包，然后可以使用tc模块（traffic control）对数据包进行控制。
  • net_prio: 限制进程网络流量的优先级。
  • huge_tlb: 限制HugeTLB的使用。
  • freezer:挂起或者恢复cgroups中的进程。
  • ns: 控制cgroups中的进程使用不同的namespace。

也就是说，cgroup是管理一组task的基本单元，其作为结点组成的树结构叫做hiierarchy。subsystem附加在hierarchy上，对其中的cgroup进行资源限制，同时子结点继承父结点的配置。

三个组件的关系：系统创建新的hierarchy后，系统中的所有进程都会加入这个hierarchy的cgroup根节点，这个根节点是由hierarchy默认创建的。一个subsystem只能附加到一个hierarchy上面，一个hierarchy可以附加多个subsystem，一个进程可以作为多个cgroup的成员，但这些cgroup必须在不同的hierarchy中；一个进程fork出子进程时，父子同属于一个cgroup，但也可以根据需要移到不同的cgroup中。
如何调用内核才能配置Cgroups呢？前面提到，hierarchy是一种树状的组织结构，kernel为了使对Cgroups的配置更加直观，是通过一个虚拟的树状文件系统来配置Cgroup的，也就是通过层级的目录来虚拟出一棵hierarchy(cgroup tree)。示例：

mkdir cgroup-test
sudo mount -t cgroup -o none, name=cgroup-test cgroup-test ./cgroup-test
ls ./cgroup-test

以上在当前目录创建一个文件夹，并挂载了一个cgroup类型的文件系统，这样就创建了一棵hierarchy。ls查看一下目录，会发现生成了一些默认的文件：

• cgroup.clone_children cpuset的subsystem会读取这个配置文件,如果这个值(默认值是0)是 1 子cgroup才会继承父cgroup的cpuset的配置

• cgroup.procs是树中当前节点cgroup中的进程组ID,现在的位置是根节点,这个文件中会有现在系统中所有进程组的ID

• notify_on_release和release_agent 会一起使用。notify_on_release 标志当这个cgroup最后一个进程退出的时候是否执行了release_agent

• release_agent 则是一个路径,通常用作进程退出后自动清理不再使用的cgroup

• task 标识该cgroup下面进程ID,如果把一个进程ID写到task文件中,便会把相应的进程加入到这个cgroup中。
  在该目录下继续创建文件夹，就是扩展子cgroup，其也会自动创建一些文件配置项。
  但是由于我们创建的这个hierarchy没有附加任何subsystem（-o 后的值为none），所以没办法对其中的cgroup限制进程资源占用。值得一提的是，各种subsystem在/sys/fs/cgroup/下有系统已经创建好的默认的hierarchy，因而很方便我们使用。(或者也可以使用-o memory)
  在/sys/fs/cgroup/memory下：

  sudo mkdir test && cd test
  sudo sh -c “echo “100m” > memory.limit_in_bytes”
  sudo sh -c “echo $$ > tasks”
  stress –vm-bytes 200m –vm-keep -m 1

以上，我们在挂载了memory子系统的hierarchy下创建了一个cgroup，并通过修改配置项对其内存资源限制（200m以下），然后使用stress进行压力测试。
使用top等命令可以发现，其内存确实被限制，验证了cgroups的限制资源的能力。
在Docker中，我们可以在启动一个容器的时候传入参数-m 100m达到这种效果，即将容器的内存占用限制在100m，这背后就是由cgroups技术实现的。Dokcer通过为每个容器创建cgroup,配置资源限制和监控。

Union File System

Union FS，是一种为linux,fressBSD,netBSD操作系统设计的，把其他文件系统联合到一个联合挂载点的文件系统服务。它使用branch把不同文件系统的文件和目录透明地覆盖，形成一个单一的文件系统。这些branch或者是ro的，或者是rw的，所以当对这个虚拟后的联合文件系统进行写操作时，系统是真正写到了一个新文件中。看起来这个虚拟后的联合文件系统可以对任何文件进行操作，但其实并没有改变原来的文件，这是因为unionfs使用了一个重要的资源管理技术——写时复制(copy-on-write)。
coW，也叫做隐式共享，是一种对可修改资源实现高效复制的资源管理技术。它的思想是，如果一个资源是重复的，但没有任何修改，这时不需要立即创建一个新的资源，这个资源可以被新旧实例共享。创建新资源只会发生在第一次写操作，也就是对资源进行修改的时候。通过这种资源共享的方式，可以显著减少未修改资源的复制所带来的消耗。

AUFS

AUFS，全称是Advanced Multi-Layerd Unification Filesystem，完全重写了早期的UnionFS 1.x，并引入了一些新的功能，比如可写分支的负载均衡。
AUFS是docker选用的第一种存储驱动，具有快速启动容器、高效利用存储和内存等优点，直到现在依然被docker支持。接下来，介绍docker是如何利用AUFS存储镜像和容器的。
我们知道，在docker中，每一个image都是由一系列read-only layer组成的。image layer的内容都存储在/var/lib/docker/aufs/diff目录下。而/var/lib/docker/aufs/layers目录则存储image layer如何堆栈这些layer的metadata。

Overlay2

Overlay2是现版本Docker默认使用的存储驱动，通常情况下，overlay2 会比AUFS性能更好，而且更加稳定，但是二者基本的存储思路都是分层。overlay2 和 AUFS 类似，它将所有目录称之为层（layer），overlay2 的目录是镜像和容器分层的基础，而把这些层统一展现到同一的目录下的过程称为联合挂载（union mount）。overlay2 把目录的下一层叫作lowerdir，上一层叫作upperdir，联合挂载后的结果叫作merged。
总体来说，overlay2 是这样储存文件的：overlay2将镜像层和容器层都放在单独的目录，并且有唯一 ID，每一层仅存储发生变化的文件，最终使用联合挂载技术将容器层和镜像层的所有文件统一挂载到容器中，使得容器中看到完整的系统文件。

接下来以overlay2为例，探究docker是如何存放镜像的。
首先从仓库拉取一个ubuntu16.04镜像，然后查看该镜像的信息：

docker pull ubuntu:16.04
观察到如下信息：

16.04: Pulling from library/ubuntu
58690f9b18fc: Pull complete 
b51569e7c507: Pull complete 
da8ef40b9eca: Pull complete 
fb15d46c38dc: Pull complete 
Digest: sha256:0f71fa8d4d2d4292c3c617fda2b36f6dabe5c8b6e34c3dc5b0d17d4e704bd39c
Status: Downloaded newer image for ubuntu:16.04

可以看到，镜像正是被分为4层拉取下来的。在/var/lib/docker/overlay2可以找到所有拉取下来的layer。此外，该目录下还有一个l目录，这里全是到各层diff之间的软链接，把一些较短的随机串软连到镜像层的 diff 文件夹下，这样做是为了避免达到mount命令参数的长度限制。
先随意查看一个镜像层的内容：diff,link,lower,work。
在这里，link 文件内容为该镜像层对应l目录中的短 ID，diff 文件夹为该镜像层的改动内容，也是被联合挂载的内容，lower 文件为该层的所有父层镜像的短 ID，规定了镜像间的层序关系。
我们可以用docker inspect来找到某个镜像的层级之间的关系：

docker image inspect ubuntu
...
"GraphDriver": {
            "Data": {
                "LowerDir": "/var/lib/docker/overlay2/ca36b188418e7d85232c6d90144380e543ec45fb4cc962bf2f45d4a823c0f9cd/diff:/var/lib/docker/overlay2/4f934d2bbd300caf92c0f00c85201053c20881c91810f32c5bef850581990acd/diff:/var/lib/docker/overlay2/579a385ff86c563d0c4c71bcc5471133b674d102de7ab38555e66ec955f5dcdb/diff",
                "MergedDir": "/var/lib/docker/overlay2/aac78f83be662b8ec26fadd30aff555f35f66453b834a1d71edd7aea83607b40/merged",
                "UpperDir": "/var/lib/docker/overlay2/aac78f83be662b8ec26fadd30aff555f35f66453b834a1d71edd7aea83607b40/diff",
                "WorkDir": "/var/lib/docker/overlay2/aac78f83be662b8ec26fadd30aff555f35f66453b834a1d71edd7aea83607b40/work"
            },
            "Name": "overlay2"
        },
...

其中 MergedDir 代表当前镜像层在 overlay2 存储下的目录，LowerDir 代表当前镜像的父层关系，使用冒号分隔，冒号最后代表该镜像的最底层。
接着启动容器，再用docker inspect查看容器的层级关系：

docker inspect ubuntu
...
"GraphDriver": {
        "Data": {
            "LowerDir": "/var/lib/docker/overlay2/f5de3e3e085c8c0a6591705d368523927ba6e3fd5434ba802a3315d6747ce00d-init/diff:/var/lib/docker/overlay2/aac78f83be662b8ec26fadd30aff555f35f66453b834a1d71edd7aea83607b40/diff:/var/lib/docker/overlay2/ca36b188418e7d85232c6d90144380e543ec45fb4cc962bf2f45d4a823c0f9cd/diff:/var/lib/docker/overlay2/4f934d2bbd300caf92c0f00c85201053c20881c91810f32c5bef850581990acd/diff:/var/lib/docker/overlay2/579a385ff86c563d0c4c71bcc5471133b674d102de7ab38555e66ec955f5dcdb/diff",
            "MergedDir": "/var/lib/docker/overlay2/f5de3e3e085c8c0a6591705d368523927ba6e3fd5434ba802a3315d6747ce00d/merged",
            "UpperDir": "/var/lib/docker/overlay2/f5de3e3e085c8c0a6591705d368523927ba6e3fd5434ba802a3315d6747ce00d/diff",
            "WorkDir": "/var/lib/docker/overlay2/f5de3e3e085c8c0a6591705d368523927ba6e3fd5434ba802a3315d6747ce00d/work"
        },
        "Name": "overlay2"
    },
...

这里MergedDir 的内容即为容器层的工作目录，LowerDir 为容器所依赖的镜像层目录。实际上，overlay2将lowerdir、upperdir、workdir联合挂载，形成最终的merged挂载点，其中lowerdir是镜像只读层，upperdir是容器可读可写层，workdir是执行涉及修改lowerdir执行copy_up操作的中转层（例如，upperdir中不存在，需要从lowerdir中进行复制，该过程暂未详细了解，遇到了再分析）。

实战：自制简单docker

明白了以上三个基本原理，实际上我们已经可以制作一个简单的小docker了！这里为了方便，还是使用AUFS作为存储。
首先，使用go的urfave/cli命令行工具，将代码改造成命令行程序：

const usage = `we make a small docker container by ourselves using basic knowledge.`

func main() {
    app := cli.NewApp()
    app.Name = "mydocker"
    app.Usage = usage

    app.Commands = []cli.Command{
        initCommand,
        runCommand,
    }

    app.Before = func(context *cli.Context) error {
        // Log as JSON instead of the default ASCII formatter.
        log.SetFormatter(&log.JSONFormatter{})

        log.SetOutput(os.Stdout)
        return nil
    }

    if err := app.Run(os.Args); err != nil {
        log.Fatal(err)
    }
}

这里我们规定了2条命令：run和init，其中run就和docker run一样是启动容器，而init是内部调用的用于初始化容器的命令。接着，我们详细定义这两条命令：

var runCommand = cli.Command{
    Name: "run",
    Usage: `Create a container with namespace and cgroups limit
            mydocker run -ti [command]`,
    Flags: []cli.Flag{
        cli.BoolFlag{
            Name:  "ti",
            Usage: "enable tty",
        },
    },
    Action: func(context *cli.Context) error {
        if len(context.Args()) < 1 {
            return fmt.Errorf("Missing container command")
        }
        var cmdArray []string
        for _, arg := range context.Args() {
            cmdArray = append(cmdArray, arg)
        }
        tty := context.Bool("ti")
        Run(tty, cmdArray)
        return nil
    },
}

var initCommand = cli.Command{
    Name:  "init",
    Usage: "Init container process run user's process in container. Do not call it outside",
    Action: func(context *cli.Context) error {
        log.Infof("init come on")
        err := container.RunContainerInitProcess()
        return err
    },
}

其中flags规定了一些调用参数，如ti就和docker中一样，意义是启动终端和交互。action是命令真正的入口，这里先判断有无命令，再读取args将命令存入cmdArray。最后调用了Run函数：

func Run(tty bool, comArray []string) {
    parent, writePipe := container.NewParentProcess(tty)
    if parent == nil {
        log.Errorf("New parent process error")
        return
    }
    if err := parent.Start(); err != nil {
        log.Error(err)
    }
    sendInitCommand(comArray, writePipe)
    parent.Wait()
    mntURL := "/cproot/mnt/"
    rootURL := "/cproot/"
    container.DeleteWorkSpace(rootURL, mntURL)
    os.Exit(0)
}

func sendInitCommand(comArray []string, writePipe *os.File) {
    command := strings.Join(comArray, " ")
    log.Infof("command all is %s", command)
    writePipe.WriteString(command)
    writePipe.Close()
}

接着，首先调用了NewParentProcess函数，如下：

func NewParentProcess(tty bool) (*exec.Cmd, *os.File) {
    readPipe, writePipe, err := NewPipe()
    if err != nil {
        log.Errorf("New pipe error %v", err)
        return nil, nil
    }
    cmd := exec.Command("/proc/self/exe", "init")
    cmd.SysProcAttr = &syscall.SysProcAttr{
        Cloneflags: syscall.CLONE_NEWUTS | syscall.CLONE_NEWPID | syscall.CLONE_NEWNS |
            syscall.CLONE_NEWNET | syscall.CLONE_NEWIPC,
    }
    if tty {
        cmd.Stdin = os.Stdin
        cmd.Stdout = os.Stdout
        cmd.Stderr = os.Stderr
    }
    cmd.ExtraFiles = []*os.File{readPipe}
    mntURL := "/cproot/mnt/"
    rootURL := "/cproot/"
    NewWorkSpace(rootURL, mntURL)
    cmd.Dir = mntURL
    return cmd, writePipe
}

func NewPipe() (*os.File, *os.File, error) {
    read, write, err := os.Pipe()
    if err != nil {
        return nil, nil, err
    }
    return read, write, nil
}

这里先调用NewPipe创建了用于外部和容器通信的管道，接着设置了需要执行的两条命令：
/proc/self/exe 当前正在运行的进程本身的可执行文件，这就是自己调用自己，来初始化刚创建出的进程。
init 就是刚刚自定义的命令。
接着设置了系统调用属性：这里就是fork出一个新进程，且为这个进程设置了若干namespace，来与外部环境进行隔离。
由于进程的3个文件描述符已经被标准输入、输出、错误所占用，所以就通过extraFiles传入了管道读取端给子进程。接着规定了，联合文件系统最终的挂载目录和镜像、容器layer所在的目录。紧接着便调用了NewWorkSpace函数：

func NewWorkSpace(rootURL string, mntURL string) {
    CreateReadOnlyLayer(rootURL)
    CreateWriteLayer(rootURL)
    CreateMountPoint(rootURL, mntURL)
}

func CreateReadOnlyLayer(rootURL string) {
    busyboxURL := rootURL + "busybox/"
    busyboxTarURL := rootURL + "busybox.tar"
    exist, err := PathExists(busyboxURL)
    if err != nil {
        log.Infof("Fail to judge whether dir %s exists. %v", busyboxURL, err)
    }
    if exist == false {
        if err := os.Mkdir(busyboxURL, 0777); err != nil {
            log.Errorf("Mkdir dir %s error. %v", busyboxURL, err)
        }
        if _, err := exec.Command("tar", "-xvf", busyboxTarURL, "-C", busyboxURL).CombinedOutput(); err != nil {
            log.Errorf("Untar dir %s error %v", busyboxURL, err)
        }
    }
}

func CreateWriteLayer(rootURL string) {
    writeURL := rootURL + "writeLayer/"
    if err := os.Mkdir(writeURL, 0777); err != nil {
        log.Errorf("Mkdir dir %s error. %v", writeURL, err)
    }
}

func CreateMountPoint(rootURL string, mntURL string) {
    if err := os.Mkdir(mntURL, 0777); err != nil {
        log.Errorf("Mkdir dir %s error. %v", mntURL, err)
    }
    dirs := "dirs=" + rootURL + "writeLayer:" + rootURL + "busybox"
    cmd := exec.Command("mount", "-t", "aufs", "-o", dirs, "none", mntURL)
    cmd.Stdout = os.Stdout
    cmd.Stderr = os.Stderr
    if err := cmd.Run(); err != nil {
        log.Errorf("%v", err)
    }
}

这个函数分为3个部分，首先是创建镜像层（只读），接着是创建容器可写层，最后就是用AUFS的方式将容器层、可写层联合挂载到指定的mntURL下。
通过调用newparentprocess，我们就从返回值得到了这样的一条命令，并在Run函数中对其调用start函数，这才是真正开始这条命令的执行，它会首先clone出一个namespace隔离的进程，并在子进程中先调用/proc/self/exe，即其本身，接着调用我们写的init方法，进行初始化。然后便开始执行sendInitCommand函数，即将用户输入的命令读取到管道的写入端。当程序执行完毕后，会调用wait释放进程资源并退出，以及执行DeleteWorkSpace删除可写层和解挂aufs系统（相当于退出容器），这些都是后话。
生成子进程后，首先会调用自己，即启动子进程。接着子进程就会执行init命令，调用RunContainerInitProcess()。也就是说，调用这个函数时，我们已经身处namespace内的子进程了：

func RunContainerInitProcess() error {
    cmdArray := readUserCommand()
    if cmdArray == nil || len(cmdArray) == 0 {
        return fmt.Errorf("Run container get user command error, cmdArray is nil")
    }

    setUpMount()

    path, err := exec.LookPath(cmdArray[0])
    if err != nil {
        log.Errorf("Exec loop path error %v", err)
        return err
    }
    log.Infof("Find path %s", path)
    if err := syscall.Exec(path, cmdArray[0:], os.Environ()); err != nil {
        log.Errorf(err.Error())
    }
    return nil
}

func readUserCommand() []string {
    pipe := os.NewFile(uintptr(3), "pipe")
    msg, err := ioutil.ReadAll(pipe)
    if err != nil {
        log.Errorf("init read pipe error %v", err)
        return nil
    }
    msgStr := string(msg)
    return strings.Split(msgStr, " ")
}

/**
Init 挂载点
*/
func setUpMount() {
    pwd, err := os.Getwd()
    if err != nil {
        log.Errorf("Get current location error %v", err)
        return
    }
    log.Infof("Current location is %s", pwd)
    pivotRoot(pwd)

    //mount proc
    defaultMountFlags := syscall.MS_NOEXEC | syscall.MS_NOSUID | syscall.MS_NODEV
    quarantineMountFlags := syscall.MS_PRIVATE | syscall.MS_REC
    syscall.Mount("","/","", uintptr(quarantineMountFlags), "")
    syscall.Mount("proc", "/proc", "proc", uintptr(defaultMountFlags), "")

    //syscall.Mount("tmpfs", "/dev", "tmpfs", syscall.MS_NOSUID|syscall.MS_STRICTATIME, "mode=755")
}

func pivotRoot(root string) error {
    /**
    为了使当前root的老 root 和新 root 不在同一个文件系统下，我们把root重新mount了一次
    bind mount是把相同的内容换了一个挂载点的挂载方法
    */
    log.Infof("pivotroot: root is %s", root)
    if err := syscall.Mount(root, root, "bind", syscall.MS_BIND|syscall.MS_REC, ""); err != nil {
        return fmt.Errorf("Mount rootfs to itself error: %v", err)
    }
    // 创建 rootfs/.pivot_root 存储 old_root
    pivotDir := filepath.Join(root, ".pivot_root")
    if err := os.Mkdir(pivotDir, 0777); err != nil {
        return err
    }
    // pivot_root 到新的rootfs, 现在老的 old_root 是挂载在rootfs/.pivot_root
    // 挂载点现在依然可以在mount命令中看到
    if err := syscall.PivotRoot(root, pivotDir); err != nil {
        return fmt.Errorf("pivot_root %v", err)
    }
    // 修改当前的工作目录到根目录
    if err := syscall.Chdir("/"); err != nil {
        return fmt.Errorf("chdir / %v", err)
    }

    pivotDir = filepath.Join("/", ".pivot_root")
    // umount rootfs/.pivot_root
    if err := syscall.Unmount(pivotDir, syscall.MNT_DETACH); err != nil {
        return fmt.Errorf("unmount pivot_root dir %v", err)
    }
    // 删除临时文件夹
    return os.Remove(pivotDir)
}

首先是调用readCommand从管道读取用户传入的命令，并在后来识别系统环境变量并予以执行。接着调用setupMount开始一系列挂载工作。这里读取到的pwd就是指定的mntURL，也就是联合文件系统的挂载点，容器的工作目录。接着，调用pivotRoot(pwd)。众所周知，pivot_root是一个系统调用，主要功能是改变当前的rootfs。pivot_root可以将当前进程的rootfs移动到put_old文件夹，再使new_root成为新的rootfs。new_root和put_old必须不能同时存在当前root的同一个文件系统中。这个系统调用和chroot命令区别在于，前者是将整个系统切换到一个新的root目录，并移除对之前root文件系统的依赖，这样就能umount原先的rootfs。而后者只是针对某个进程，系统的其他部分依旧运行于老的root目录中。
注意！在挂载开始前，我们首先有这样的操作：

quarantineMountFlags := syscall.MS_PRIVATE | syscall.MS_REC
syscall.Mount("","/","", uintptr(quarantineMountFlags), "")

这就是开始将mount namespace时提出的，其作用相当于mount –make-rprivate /,即递归修改整个mount树的propagate type为private，这样我们在容器内的挂载操作才不会传给外部。否则在接下来挂载proc后，回到主机系统，会发现很多命令都无法使用了。这其实就是因为主机的proc被修改了，需要在主机重新mount一次proc才能恢复正常。
这之后，init命令的工作也就做完了，此时我们的容器已启动起来。

在还是懵懂的大一本科生时，曾经折腾过一台服务器部署了一个博客网站，保持过一年的更新，最终却并未坚持下去。博客废弃了，域名早已过期，服务器也停机释放了。

三年后的今天，在整理旧电脑的数据时，无意间看到了曾经写过的几篇内容。也许文笔稚嫩，也许技术力尚欠缺，却一瞬间将我带回从前，那段时光中，最勤奋好学，贪婪地汲取知识，期待着变强的自己。

果然，博客还是要做下去。当再度萌生这个想法时，这个新的站点就诞生了。为了追求快速部署，采用了Github Pages + Hexo，主题暂且还是使用了烂大街但是确实很简约耐看的Next。我会像从前一样，在这里记录自己的技术学习与实践经验，不仅为自己的反思总结，如果能帮到一些人那便更好。目前我会先对保留的老博客文章作筛选，将一部分仍有一定价值的文章搬运过来。

同时在技术之外，这个网站也会收录一些个人在平常的所感所想，无意义的念叨，以及生活的碎片。我想，人总归还是希望能留下些什么东西。