Scavenger

scavenger是一个后台运行的go routine ，专用于释放空闲页面，当清扫结束后，collector 会唤醒scavenger。 此外，mutator内存申请过程中如果发现堆中没有释放的内存超过一个阈值，也会执行释放空闲页面的逻辑。
释放空闲页面最小单位是物理页面，而不是golang中的页面，golang中页分配器的页面是指8KB大小且8KB对齐的内存块，如果golang所运行的系统中页面大小是16KB，那么释放空闲页面的时候就必须是页分配器中连续的且首地址16KB对齐的两个页面。
寻找可以释放的页面需要借助第二章提到的chunk中的scavenged 和 pallocBits 两个位图，之前提到一个chunk中有512个页面，位图可以用8个uint64表示。

上图以128个页面做简单示意，128个页面需要2个uint64做位图，在上图中，扫描 scavenged | pallocBits 的位图，可以发现有一个大小为6个页面的连续块（60、61、62、63、64、65）。要释放的页面肯定是没被分配且没有被释放过的，所以是 scavenged | pallocBits。
在64位位图x中快速寻找m bit 对齐且连续的bits 可以使用位运算，这里用到的位运算技巧非常的复杂。有一种位运算的算法，可以找出并标记出，比如 在0x0100a3 （高位为0忽略）这个位图寻找byte对齐的连续的8个0bit，经过计算以后，会得到0xff00ff，结果把不可能的部分全都置1，可行的部分保留0（解释：01和a3虽然对齐byte，但是不是连续的8个0bit）
下边来一步步阐释这个算法，首先，需求是m bit对齐的，所以要把位图按照m bit分组，这里先用m = 8 举例子。接下来，需要用为运算判断每一个组是不是都都是0bit，还是用x表示位图，这里为了方便书写和阅读，使用32bit位图，32bit的位图算法和64位的完全一样。( x & 0x7f7f7f7f ) + 0x7f7f7f7f 这个位运算的结果可以判断x每个分组中除了最高位其他是不是全0，首先 0x7f7f7f7f & x可以把每个分组中的最高位置0，再通过 + 0x7f7f7f7f 这个运算，如果组内除了最高位的其他位不全是0的话，就会发生溢出，这样( x & 0x7f7f7f7f ) + 0x7f7f7f7f 这个结果中溢出的组 组内的最高位就会是1。接下来再对位运算进行升级，加上对组内最高位的判断。( (0x7f7f7f7f & x ) + 0x7f7f7f7f ) | x ，对之前的结果再与 x 进行或运算，这样无论每个组内的最高非0 或者是 其他位非全0，计算出来的结果的组内的最高位都是1。当且仅当x组内是全0时候，( (0x7f7f7f7f & x ) + 0x7f7f7f7f ) | x的结果中对应的组的组内最高位才是0。然后再做一些位运算，变成 (( (0x7f7f7f7f & x ) + 0x7f7f7f7f ) | x ) | c ，这个结果中，最终每个组内除了最高位可能是0和1 ，其他的都是1，这样就可以用一个最高位是0还是1分别来表示组内全0和非全0。在这个基础上，再对这个最新的位运算公式加上一个取反运算，最终的位运算公式是 ^( (( (0x7f7f7f7f & x ) + 0x7f7f7f7f ) | x ) | c )

对于这个位运算公式，如果x是0x000100a3，计算的结果将会是 0x80008000。接下来是如何把0x80008000转化成0x00ff00ff的过程，可见，需要把仅组内最高位是1的组给全置0，其余的任何情况全组置1。对于组内最高位是1，其余都是0的bits，有一个特点，就是位运算x - ( x >> (8 - 1)) | x 的结果是全1，这个位运算公式中的 8 是组的大小，举的例子中组的大小就是8。所以最终的结果就是 ^( x - ( x >> (8 - 1)) | x )

再推广到一般情况，如果组的大小是m，m都得是2的幂次，1、2、4、8、16、32、64。对于m是1的情况，显然直接返回位图x就行了，对于2、4、16、32、64 ，mask 只需要换成 0x5555555555555555 、0x7777777777777777、0x7fff7fff7fff7fff ... 不难找出规律。

由上述算法再进行扩展，得到的算法可以应用在由多个uint64构成的位图中，能够处理uint64交界处连续的情况。