Heap Pointer Bitmap 的设计

Heap Pointer Bitmap是用来标记堆中哪些位置有指针的，依靠这个信息，可以使得垃圾回收准确高效，而不用保守的扫描所有的字。heap pointer bitmap 存储在 heapArena中的bitmap字段中，如下图所示。这个bitmap 不是 one-bit bitmap， 每个指针大小的空间会占用两个bits的位图空间，所以在amd64/linux 环境下，这个bitmap 会占用2M大小的空间。

如下图所示，每个字(一个字的大小等于指针的占用空间的大小)的2bit不是存放在一起的。连续四个字(w1,w2,w3,w4 (address of w1)%ptrSize==0)的高四位放在一起，低四位放在一起，构成一个byte。

每个字的位图的低位表示这个字里是不是存有指针，高位则有两种含义。下图中这个结构体T 占6个字的空间(48bytes) ，其中b c 都是指针，那么其对应位图中的位就要被标志成1 (绿色的部分)。可以看到，从c以后，这 个结构体中再无指针，所以bitmap[n]中c的高位是最后一个1，c以后的字(d e f)的位图的高位都是0 , 在 c之前的字的高位都是1 (除了第二个字，第二字用于debug)
heap pointer bitmap 这么设计，是为了方便标记，对于任意一个地址，golang不需要设计如何去记录某个地址里边存的是什么对象（知道是什么对象才知道哪里有指针），只需要查看 heap pointer bitmap 就能进行扫描，顺着bitmap 的低四位定位指针，高四位用于表示是否还要继续扫描下去。

每次分配对象时候，都要标记位图，根据对象的地址，找到对应的heapArena，并定位到相关的bitmap bytes，对其进行标记。golang在编译阶段，已经为每种类型生成了一个1-bit entry bit map(gcdata) ，参照gcdata就能正确标记heapArena的位图，如下图所示。

在标记位图的过程中，需要注意的是，有些对象并不完全占用一个或多个byte，有时候会与其他的对象共享一个byte ，所以不能覆盖掉其他对象的位图。除此之外，有些对象横跨两个heapArena的情况，此时标记位图的时候就要分别标记两个heapArena位图中的对应部分，golang中的实现是，先把位图放在正在分配的对象的空间中(此时对象的空间未被使用，并且足够放位图)，待标记完成后把两部分分别复制到两个heapArena中。