作者：字节游戏中台客户端团队 – 潘风

引言

前文Unity3D托管堆BoehmGC算法学习-内存分配篇论述了GC内存分配的相关机制，本文主要分析一下BoehmGC算法中垃圾回收的具体实现机制。

流程概述

首先BoehmGC算法提供了垃圾回收的入口API，GC_gcollect，GC_gcollect会调用GC_try_to_collect_general，GC_try_to_collect_general再调用GC_try_to_collect_inner开始，如下：

void GC_CALL GC_gcollect(void)
{
    (void)GC_try_to_collect_general(0, FALSE);
    ...
}

GC_bool GC_try_to_collect_general(GC_stop_func stop_func, GC_bool force_unmap GC_ATTR_UNUSED) 
{
    ...
    ENTER_GC();
    //调用GC_try_to_collect_inner开始GC
    result = GC_try_to_collect_inner(stop_func != 0?stop_func:GC_default_stop_func);
    EXIT_GC();
    ...
}
复制代码

GC_try_to_collect_inner方法开始真正的GC操作，下面是代码和主要步骤：

GC_INNER GC_bool GC_try_to_collect_inner(GC_stop_func stop_func)
{
    ...
    //控制停止
    if (GC_dont_gc || (*stop_func)()) return FALSE;
    //抛出事件
    if (GC_on_collection_event) GC_on_collection_event(GC_EVENT_START);
    ...
    //清空标记位
    GC_clear_marks();
    ...
    //开始追踪内存节点，标记“引用”标记位
    if (!GC_stopped_mark(stop_func)) {
        ...
    }
    //结束标记，开始回收没有被引用的内存节点
    GC_finish_collection();
    ...
    //抛出事件
    if (GC_on_collection_event) GC_on_collection_event(GC_EVENT_END);
}
复制代码

首先，解释一下“对象内存节点” 的概念，即前文介绍的分配给上层的对象内存块。例如，一个对象节点分配16字节，一个hblk内存块的大小是4096字节，可以等分成256个对象节点，提供给上层使用。对于小内存（小于2048字节），内存节点从ok_freelist中取出，按照16字节内存对齐，大小分类共有128种。对于大内存（大于2048字节），直接从hblkfreelist中取出。对象内存节点的大小记录在Header数据结构的hb_sz字段中。

GC主要分为两个阶段：

第一阶段：标记（Mark）阶段，这个阶段首先重置内存节点的标记位，然后从内存的根节点开始遍历扫描内存空间，将托管堆上被引用的内存节点标记为“引用”。
第二阶段：回收（Reclaim）阶段，这个阶段遍历托管堆上的所有内存节点，然后将未标记为“引用”的内存节点进行回收。

除此之外，GC还提供了一个事件机制，用于通知外界GC的阶段和状态。状态定义如下：

typedef enum {
    GC_EVENT_START, //开始GC
    GC_EVENT_MARK_START, //开始标记
    GC_EVENT_MARK_END,  //结束标记
    GC_EVENT_RECLAIM_START, //开始回收
    GC_EVENT_RECLAIM_END, //回收结束
    GC_EVENT_END //GC结束
    ...
}
复制代码

外界可以设置事件的回调方法，如下：

void GC_CALL GC_set_on_collection_event(GC_on_collection_event_proc fn)
{
    ...
    GC_on_collection_event = fn;
    ...
}
复制代码

GC的过程中，会在各个阶段调用GC_on_collection_event方法通知。

托管堆内存布局

在介绍垃圾回收流程之前，首先介绍一下托管堆内存的布局和结构。

如前文所述，hblk内存块是Boehm算法在托管堆中进行内存分配的基础单位，无论大内存还是小内存，所有对象节点都是在hblk的基础上分配的。在分配一个hblk内存块的时候，会创建相应的header信息，header信息创建之后，被加入到全局数组_top_index中：

struct GC_arrays {
    ...
    bottom_index *_top_index[TOP_SZ];
};

typedef struct bi {
    hdr * index[BOTTOM_SZ]; //存储Header信息的数据结构
    structbi * asc_link; //升序排列
    structbi * desc_link; //降序排列
    word key; //key，前42位高地址
    # ifdef HASH_TL
        structbi * hash_link;
    # endif
} bottom_index;
复制代码

其中bottomIdex结构是数组的元素，里面存放了具体的header信息，关于存储header信息的逻辑，步骤如下：

根据header对应的hblk的内存块地址，得到一个hash值，hash值是_top_index的下标index，如果计算出的hash值相同，则进一步比较0～42位的bit值，如果相同，则认为header找到了对应的bottomIndex块，直接返回这个bottomIndex块。
如果不同，则新建一个bottomIndex块，并将其插入二级链表中。所有bottomIndex块的引用关系如下图所示，hash值相同的块用hash_link链表维护。
同时会构建一个辅助的有序链表，存储所有的bottomIndex块。这个链表是一维的，且按照一定的规则计算出hash值，根据hash值进行有序构建。这个链表把全局数组_top_index的二维结构转化为一维有序链表，方便后续的遍历。如下图：
确定了bottomIndex块之后，进一步根据hblk地址的42～64位，计算出hash值，作为bottomIndex中index数组的下标，将header信息存入存储对应位置。

综上，遍历这个链表可以找到所有hblk内存块的地址和header信息，进一步遍历hblk内存块中所有的内存节点，遍历托管堆中所有hblk内存块的逻辑如下：

void GC_apply_to_all_blocks(void (*fn)(struct hblk *h, word client_data),
              word client_data)
{
  signed_word j;
  bottom_index * index_p;
  for (index_p = GC_all_bottom_indices; index_p != 0;
     index_p = index_p -&gt; asc_link) {
    for (j = BOTTOM_SZ-1; j &gt;= 0;) {
      if (!IS_FORWARDING_ADDR_OR_NIL(index_p-&gt;index[j])) {
        if (!HBLK_IS_FREE(index_p-&gt;index[j])) {
          (*fn)((struct hblk *)(((index_p-&gt;key &lt;&lt; LOG_BOTTOM_SZ) + (word)j)
                &lt;&lt; LOG_HBLKSIZE))
        }
        j--;
       } else if (index_p-&gt;index[j] == 0) {
        j--;
       } else {
        j -= (signed_word)(index_p-&gt;index[j]);
       }
     }
   }
}
复制代码

从GC_all_bottom_indices开始遍历有序链表，得到bottomIndex块，然后进一步遍历里层的index数组中的header信息，如果这个header不是空闲状态，则参与了内存分配，将header对应的hblk地址返回给上层进一步处理。了解了这个核心结构和逻辑之后，接着分析后续的操作。

Mark阶段

Mark阶段的目的是将托管堆内存上的对象，标记为“引用”或“非引用”，便于后续回收阶段的处理。

标记位重置

首先header信息记录了对应内存块中所有“对象内存节点”是否被引用，结构如下：

//头部信息
struct hblkhdr {
    ...
    size_t hb_n_marks;//标记位个数，用于GC
    word hb_marks[MARK_BITS_SZ]; //标记为，用于GC
}
复制代码

其中，hb_n_marks表示这个hblk内存块中被“引用”的对象个数，hb_marks数组维护所有对象的引用标记位，用0和1表示“引用”和“非引用”，MARK_BITS_SZ是一个足够大的数字。例如第16个对象节点被引用，则hb_marks[15]的值是1，第17节点没有被引用，则hb_marks[16]的值是0。

首先调用GC_clear_marks方法重置所有标记位。
GC_apply_to_all_blocks如上文所述，遍历得到托管堆中所有hblk内存块的地址，找到对应的header信息。GC_clear_hdr_marks方法负责将header中关于内存节点的标记位和标记个数清0。

GC_INNER void GC_clear_marks(void)
{
    GC_apply_to_all_blocks(clear_marks_for_block, (word)0);
    ...
}

static void clear_marks_for_block(struct hblk *h, word dummy GC_ATTR_UNUSED)
{

    hdr * hhdr = HDR(h);
    ...
    GC_clear_hdr_marks(hhdr);
}

GC_INNER void GC_clear_hdr_marks(hdr *hhdr)
{
    BZERO(hhdr -&gt; hb_marks, sizeof(hhdr-&gt;hb_marks));
    ...
    hhdr -&gt; hb_n_marks = 0;
}
复制代码

Mark主要流程

重置标记信息之后，开始正式进入扫描标记的流程，GC_stopped_mark方法实现了主要逻辑：

准备工作，暂停线程，
从根节点开始扫描，包括栈内存、寄存器变量、静态数据区的内存开始遍历，判断根节点内存地址指向的内存空间是否位于一个有效的hblk内存块中。将这些有效的内存空间标记起来，并暂存到一个临时数组中。
进一步扫描临时数组中的所有对象的内存空间，判断其指向的内存空间是否位于有效的hblk内存块中，并进行标记。直到全部遍历结束。
结束标记流程，恢复线程。

GC_stopped_mark方法的主要逻辑如下：

STATIC GC_bool GC_stopped_mark(GC_stop_func stop_func)
{
    //事件通知，暂停线程
    if (GC_on_collection_event)
        GC_on_collection_event(GC_EVENT_POST_STOP_WORLD);    
    ...
    //暂停线程
    STOP_WORLD();
    //事件通知，暂停线程
    if (GC_on_collection_event)
        GC_on_collection_event(GC_EVENT_POST_STOP_WORLD);
    ...
    //事件通知，开始扫描
    if (GC_on_collection_event)
        GC_on_collection_event(GC_EVENT_MARK_START);
    ...
    //判断gc初始化状态
    GC_initiate_gc();   
    ...
    //从根节点开始扫描追踪
    if (GC_mark_some(GC_approx_sp())) break;
    ...
    //事件通知，结束扫描
    if (GC_on_collection_event)
       GC_on_collection_event(GC_EVENT_MARK_END);
    ...
    //事件通知，开始恢复线程
    if (GC_on_collection_event)
        GC_on_collection_event(GC_EVENT_PRE_START_WORLD);
    ...
    //恢复线程
    START_WORLD();
    ...
    //事件通知，恢复线程完成
    if (GC_on_collection_event)
        GC_on_collection_event(GC_EVENT_POST_START_WORLD);
    ...
}
复制代码

下面详细介绍子阶段的实现逻辑：

线程暂停

为了准确的采集跟踪托管堆内存的瞬时状态，需要先对当前线程进行挂起。

GCThread

首先GC算法为每个线程封装了一个GC_THREAD结构，这个结构存储了线程相关的信息，包括当前的线程id、状态、栈（底部指针、顶部指针）的信息，结构如下：

 typedef struct GC_Thread_Rep {
     ...
     struct GC_Thread_Rep * next;
     pthread_t id; //线程id
     struct thread_stop_info stop_info; //线程暂停信息
     ...
     ptr_t stack_end; 
     word stack_size;
     ...
 } * GC_thread;

 struct thread_stop_info {
     ...
     ptr_t stack_ptr;  
     ...
 }
复制代码

在创建每个线程时会获取栈底部指针，而线程在处理暂停SUSPEND信号时，会将当前栈顶指针保存到GC_THREAD结构中。stop_info记录了线程暂停时刻的相关信息。全局数组GC_threads用于维护所有线程信息。

suspendAll

线程暂停的宏定义是STOP_WORLD，方法实现是GC_stop_world，内部调用GC_suspend_all暂停所有线程（除当前线程之外），主要逻辑如下

GC_INNER void GC_stop_world(void)
{
    ...
    (void)GC_suspend_all();
    ...
}

STATIC int GC_suspend_all(void)
{
    int n_live_threads = 0;
    int i;
    pthread_t self = pthread_self();
    //遍历所有线程信息
    for (i = 0; i &lt; THREAD_TABLE_SZ; i++) {
        for (p = GC_threads[i]; p != 0; p = p -&gt; next) {
            //不是当前线程
            if (!THREAD_EQUAL(p -&gt; id, self)) {
                 //过滤结束和阻塞的线程
                 if ((p -&gt; flags &amp; FINISHED) != 0) continue;
                 if (p -&gt; thread_blocked) /* Will wait */ continue;
                 ...
                 n_live_threads++;
                 ...
                 //发送suspend信号，暂停系统线程
                 result = RAISE_SIGNAL(p, GC_sig_suspend);
                 ...
            }
        }
    }
}
复制代码

因为需要当前线程来进行后续逻辑，因此会暂停当前线程之外的所有线程。同时也会过滤结束和阻塞的线程。然后发起线程中断的信号。

suspend_handler

当接收到中断信号之后，会触发GC_suspend_handler回调函数处理，再触发GC_suspend_handler_inner方法：

STATIC void GC_suspend_handler_inner(ptr_t dummy GC_ATTR_UNUSED,
                   void * context GC_ATTR_UNUSED)
{
    pthread_t self = pthread_self();
    GC_thread me;
    ...
    //找到当前线程
    me = GC_lookup_thread_async(self);
    ...
    //存储栈顶指针
    GC_store_stack_ptr(me);
    ...
 }
复制代码

暂停了线程之后，开始从根节点扫描。

内存扫描

执行GC_mark_some方法开始从根节点扫描，如下

GC_INNER GC_bool GC_mark_some(ptr_t cold_gc_frame)
{
    switch(GC_mark_state) {
    case MS_NONE:
        break;
    case MS_PUSH_UNCOLLECTABLE: {
        ...
        //
        GC_push_roots(FALSE, cold_gc_frame);
        GC_objects_are_marked = TRUE;
        if (GC_mark_state != MS_INVALID) {
            GC_mark_state = MS_ROOTS_PUSHED;
        }
    }
    case MS_ROOTS_PUSHED: {
        ...
        MARK_FROM_MARK_STACK();
        break;
    }
    ...
    case MS_INVALID: {
        ...
    }
    break;
}
复制代码

GC_mark_state表示当前扫描的状态，主要分为4个状态，算法根据不同状态，进行相应处理。
MS_INVALID：表示内存空间未标记，此时状态会切换到MS_PUSH_UNCOLLECTABLE状态。如图所示：

图中绿色方块表示未开始扫描的根节点内存，例如栈区内存空间。然后会从低地址向高地址，偏移1字节的方式扫描。

MS_PUSH_UNCOLLECTABLE：开始遍历内存根节点，并对根节点指向的托管堆内存节点标记为“引用”，因为这些内存节点被根节点引用，并且将这个节点存入数组。完成标记之后，此时切换到MS_ROOTS_PUSHED状态，如图所示：

从根节点内存的起始地址开始，逐渐偏移字节，判断地址指向的值是否是托管堆内存地址。例如地址是ptr，如 *ptr是托管堆内存的一个有效地址，这个托管堆内存的节点被根节点“引用”了。图中绿色表示未扫描的内存空间，蓝色表示已扫描的内存空间。全部扫描结束之后，被引用的堆内存节点全部标记为蓝色（ABCDE），未指向的全部标记为白色（将被回收的节点）。

MS_ROOTS_PUSHED：遍历之前被“引用”的托管堆内存节点，按照偏移地址的方式，判断指向的地址是否也是托管堆内存，例如节点A的地址是ptr，则判断*ptr是否是一个有效的托管堆内存节点地址，然后ptr++，扫描完A，然后将BCDE…全部扫描判断完成。

扫描完成时，托管堆内存上所有被“引用”的内存节点已经被标记出来，所有未标记的节点最终会被GC回收。完毕之后，切换到MS_NONE状态。

MS_NONE：表示扫描的全部结束，全部标记好。

将上述四个状态归为2个基本逻辑，根节点扫描和托管堆内存递归扫描，探究具体实现逻辑：

根节点扫描

根节点扫对应MS_PUSH_UNCOLLECTABLE的GC_push_roots方法，如下：

GC_INNER void GC_push_roots(GC_bool all, ptr_t cold_gc_frame GC_ATTR_UNUSED)
{
    ...
    //扫描寄存器、线程栈地址空间
    GC_push_regs_and_stack(cold_gc_frame);
    //扫描其他根节点空间
    if (GC_push_other_roots != 0) (*GC_push_other_roots)();
}

STATIC void GC_push_regs_and_stack(ptr_t cold_gc_frame)
{
    GC_with_callee_saves_pushed(GC_push_current_stack, cold_gc_frame);
}
复制代码

GC_push_all_stack_sections和GC_push_all_register_sections方法分别扫描栈和寄存器，这里就不具体展开。最终会调用GC_push_all_eager方法扫描。

GC_API void GC_CALL GC_push_all_eager(void *bottom, void *top) {
    ...
    lim = t - 1

    for (p = b; (word)p &lt;= (word)lim;
        p = (word *)(((ptr_t)p) + ALIGNMENT)) {
    REGISTER word q = *p;
    GC_PUSH_ONE_STACK(q, p);
   }
}
复制代码

lim表示空间的最大值，例如从栈底到栈顶，逐渐累加ALIGNMENT，p是当前地址，q是*p，即p指向的地址。然后调用GC_PUSH_ONE_STACK检测。

# define GC_PUSH_ONE_STACK(p, source) \
do { \
   if ((word)(p) &gt;= (word)GC_least_plausible_heap_addr \
     &amp;&amp; (word)(p) &lt; (word)GC_greatest_plausible_heap_addr) { \
     PUSH_ONE_CHECKED_STACK(p, source); \
   } \
} while (0)
复制代码

GC_least_plausible_heap_addr和GC_greatest_plausible_heap_addr记录了托管堆内存空间的最低和最高地址，在上文系统分配堆内存的时候会更新这两个值。这是一个大致的范围，如果在这个范围内，再调用GC_mark_and_push_stack方法进一步判断。

GC_INNER void GC_mark_and_push_stack(ptr_t p, ptr_t source) {
    hdr * hhdr;
    ptr_t r = p;

    PREFETCH(p);
    GET_HDR(p, hhdr);

    //能取到header信息
    if (NULL == hhdr|| (r = (ptr_t)GC_base(p)) == NULL|| (hhdr = HDR(r)) == NULL)) {
        return;
    }
    //判断空闲状态
    if (HBLK_IS_FREE(hhdr) {
        return;
    }
    ...
    //标记并加入临时数组
    PUSH_CONTENTS_HDR(r, GC_mark_stack_top, GC_mark_stack_limit,
           source, hhdr, FALSE);
}
复制代码

source对应之前根节点内存地址，变量r对应根节点指向的地址值，通过GET_HDR方法取出r对应的Header信息，如果能取到，说明r位于一个有效的hblk内存块中，进一步判断这个内存块是否空闲，如果不空闲，说明r被分配给上层作为一个有效的对象内存节点来使用，r是一个能被根节点“引用”的托管堆内存节点。

判断逻辑

由此可以总结出判断一个内存地址是否是一个有效的，被引用的托管堆内存节点的逻辑：

是否在大致范围内GC_least_plausible_heap_addr～ GC_greatest_plausible_heap_addr。
判断是否能取到header信息，因为每个hblk内存块都对应一个header信息，能取到说明地址位于hblk内存块中。
判断位于的hblk内存块是否空闲，不空闲说明这个内存块被分配给上层使用。

操作标记位

判定为能被“引用”节点之后，调用PUSH_CONTENTS_HDR方法处理这个节点。

# define PUSH_CONTENTS_HDR(current, mark_stack_top, mark_stack_limit, source, hhdr, do_offset_check) { \
    //计算内存节点位于的hblk内存块地址的偏移值
    size_t displ = HBLKDISPL(current); \
    size_t gran_displ = BYTES_TO_GRANULES(displ); \
    ...
    //将header中对应的标记位设置为1，表示这个节点被“引用”
    SET_MARK_BIT_EXIT_IF_SET(hhdr, gran_displ); \
    ...
    //增加引用个数hb_n_marks
    INCR_MARKS(hhdr); \
    ...
    //将内存节点存入临时数组中
    PUSH_OBJ(base, hhdr, mark_stack_top, mark_stack_limit); \
    ...
}
复制代码

计算内存节点地址在hblk内存块中的偏移值，因为按照其上文所述，这个偏移值是Header信息中标记位数组hb_marks[]的下标，Header按照偏移值存储每个内存节点的标记状态信息。例如hblk内存块的地址是0x122c86900，hb_sz=16（节点大小16字节），内存节点A的地址是0x122c86920，则偏移32字节（2个gran），Header->hb_marks[1]存储A的“引用”状态标记位的值0或1。调用INCR_MARKS方法hb_n_marks加1，表示这个hblk内存块中被“引用”的节点总数。如图所示。蓝色表示被“引用”的2个内存节点，相应的hb_marks[1]和hb_marks[2]标记为1，hb_n_marks=2。

调用PUSH_OBJ，将“引用”的内存节点地址加入一个临时数组中，作为接下来的递归扫描的起点。mark_stack_top是一个数组，存放的obj是刚才扫描出的被“引用”的托管堆内存节点地址。

#define PUSH_OBJ(obj, hhdr, mark_stack_top, mark_stack_limit) \
 do { \
     ...
     mark_stack_top++; \
     ...
     mark_stack_top = GC_signal_mark_stack_overflow(mark_stack_top); \
     mark_stack_top -&gt; mse_start = (obj); \
     mark_stack_top -&gt; mse_descr.w = _descr; \
     } \
 } while (0)
复制代码

堆内存递归扫描

接下来基于遍历mark_stack_top，扫描其内存空间指向的地址值。首先通过MARK_FROM_MARK_STACK宏调用GC_mark_from方法，如下：

GC_INNER mse * GC_mark_from(mse *mark_stack_top, mse *mark_stack, mse *mark_stack_limit) 
{
    current_p = mark_stack_top -&gt; mse_start;
    descr = mark_stack_top -&gt; mse_descr.w;
    ...
    while ((word)current_p &lt;= (word)limit) {
        current = *(word *)current_p;
        ...
        if (current &gt;= (word)least_ha &amp;&amp; current &lt; (word)greatest_ha) {
            PREFETCH((ptr_t)current);
            ...
            PUSH_CONTENTS((ptr_t)current, mark_stack_top, mark_stack_limit, current_p);
        }
        current_p += ALIGNMENT;
    }
    ...
}
复制代码

current_p是当前内存地址的指针，current是current_p指向的内存地址，判断current是否是一个托管堆内存节点，current_p+= ALIGNMENT，逐渐偏移指针，直到地址空间被扫描完。current的判断逻辑是：

是否在大致范围内GC_least_plausible_heap_addr～ GC_greatest_plausible_heap_addr。
调用PUSH_CONTENTS方法进一步判断，逻辑如下：
```
#define PUSH_CONTENTS(current, mark_stack_top, mark_stack_limit, source) \
 do { \
     hdr * my_hhdr; \
     HC_GET_HDR(current, my_hhdr, source); /* contains "break" */ \
     PUSH_CONTENTS_HDR(current, mark_stack_top, mark_stack_limit, \
        source, my_hhdr, TRUE); \
 } while (0)
复制代码
```
- 调用HC_GET_HDR方法获取current所在的hblk内存块对应的header信息。前文提到，和GET_HDR方法不同的是，HC_GET_HDR方法会借助缓存获取header信息，如果有直接返回header，如果没有，调用HEADER_CACHE_MISS方法获取header信息，然后存入缓存，这样做，在频繁获取header信息的时候可以缩短计算时间，提升性能。如果获取不到header信息，则退出本次判断。
```
#define HC_GET_HDR(p, hhdr, source) \
{ \
 //获取缓存信息
 hdr_cache_entry * hce = HCE(p); \
 if (EXPECT(HCE_VALID_FOR(hce, p), TRUE)) { \
  HC_HIT(); \
  hhdr = hce -&gt; hce_hdr; \
 } else { \
  //没有缓存，直接获取header，存入缓存
  hhdr = HEADER_CACHE_MISS(p, hce, source); \
  //获取不到header
  if (NULL == hhdr) break; \
 } \
}
复制代码
```
- 如果获取到header信息，则认为指向的地址current也是一个托管堆内存节点，调用PUSH_CONTENTS_HDR方法对齐操作。
- PUSH_CONTENTS_HDR方法如上文所述，设置了这个节点的标记位，header-> hb_marks[index]，并且递增hb_n_marks。最后将其加入临时数组mark_stack_top中，作为下一次递归扫描的对象。

完成了一轮扫描之后，针对当前mark_stack_top数组中收集到的内存节点，按照同样的方式扫描内存地址，对其指向的地址空间进行判断。

当所有扫描结束，托管堆上的被“引用”的内存节点已经在hb_marks全部被标记为1，未“引用”的节点在之前标记位重置的时候，设置为0。GC接下来就是根据这些标记来判断进行垃圾回收的。

线程恢复

当扫描完之后，调用START_WORLD重新恢复所有线程，具体实现在GC_start_world方法中，如下：

GC_INNER void GC_start_world(void)
{
    ...
    n_live_threads = GC_restart_all();
}

STATIC int GC_restart_all(void)
{
    ...
    pthread_t self = pthread_self();
    for (i = 0; i &lt; THREAD_TABLE_SZ; i++) {
    for (p = GC_threads[i]; p != NULL; p = p -&gt; next) {
        if (!THREAD_EQUAL(p -&gt; id, self)) {
            if ((p -&gt; flags &amp; FINISHED) != 0) continue;
            if (p -&gt; thread_blocked) continue;
            ...
            result = RAISE_SIGNAL(p, GC_sig_thr_restart);
            ...
        }
    }
}
复制代码

和GC_suspend_all方法对应，除了当前线程（以及已结束、阻塞）之外的线程进行恢复，调用RAISE_SIGNAL发送一个恢复的信号。

Reclaim阶段

扫描和标记完成后，开始对未“引用的”托管堆内存节点进行回收。逻辑在GC_finish_collection方法中触发，如下：

STATIC void GC_finish_collection(void)
{
    ...
    //检测内存泄漏逻辑
    if (GC_find_leak) {
        for (kind = 0; kind &lt; GC_n_kinds; kind++) {
            for (size = 1; size &lt;= MAXOBJGRANULES; size++) {
                q = (ptr_t)GC_obj_kinds[kind].ok_freelist[size];
                if (q != NULL)
                GC_set_fl_marks(q);
            }
        }
    //不实际回收
    GC_start_reclaim(TRUE);
    }
    ...
    //清空ok_freelist链表
    for (kind = 0; kind &lt; GC_n_kinds; kind++) {
        for (size = 1; size &lt;= MAXOBJGRANULES; size++) {
            q = (ptr_t)GC_obj_kinds[kind].ok_freelist[size];
            if (q != NULL)
            GC_clear_fl_marks(q);
        }
    }
    //开始回收
    GC_start_reclaim(FALSE);
    ...
}
复制代码

该方法首先判断，本次操作是否需要检测内存泄漏，如果是，则触发检测泄漏逻辑，检测出的泄漏内存，不实际触发回收逻辑，这块在之后分析。通过GC_clear_fl_marks将ok_freelist链表中的内存节点的标记位设置为0。接下来调用GC_start_reclaim方法开始回收。

回收逻辑

GC_start_reclaim方法的主要逻辑如下：

GC_INNER void GC_start_reclaim(GC_bool report_if_found)
{
    for (kind = 0; kind &lt; GC_n_kinds; kind++) {
        struct hblk ** rlist = GC_obj_kinds[kind].ok_reclaim_list;
        ...
        //清空ok_freelist和ok_reclaim_list
        void **lim = &amp;(GC_obj_kinds[kind].ok_freelist[MAXOBJGRANULES+1]);
        for (fop = GC_obj_kinds[kind].ok_freelist; (word)fop &lt; (word)lim; (*(word **)&amp;fop)++) {
            ...
            GC_clear_fl_links(fop);
        }
        ...
        BZERO(rlist, (MAXOBJGRANULES + 1) * sizeof(void *));
    }

    ...
    //加入ok_reclaim_list链表
    GC_apply_to_all_blocks(GC_reclaim_block, (word)report_if_found);

    ...
    //回收内存
    GC_reclaim_all((GC_stop_func)0, FALSE);
    ...
}
复制代码

在回收之前，先将ok_freelist链表中的内存节点清空，因为针对未“引用”的小内存节点（小于2048字节），回收时会将其加入ok_freelist链表中，满足后续的内存分配，因此先清空一下。
然后将ok_reclaim_list链表也清空。ok_reclaim_list是Header中的字段，是专门针对小内存节点回收设置的，回收的对象位于ok_reclaim_list中，因此需要先清空一下这个链表。
GC_apply_to_all_blocks方法遍历所有托管堆内存的hblk内存块，针对每个内存块，使用GC_reclaim_block方法预处理要回收的内存块，对于大内存直接回收，对于小内存暂时加入ok_reclaim_list链表。
GC_reclaim_all方法实际回收小内存对象。

下面对2～4分别分析。

GC_reclaim_block

GC_reclaim_block方法如下：

STATIC void GC_reclaim_block(struct hblk *hbp, word report_if_found)
{
    hdr * hhdr = HDR(hbp);
    word sz = hhdr -&gt; hb_sz; /* size of objects in current block */
    struct obj_kind * ok = &amp;GC_obj_kinds[hhdr -&gt; hb_obj_kind];
    if( sz &gt; MAXOBJBYTES ) { /* 1 big object */
    if( !mark_bit_from_hdr(hhdr, 0) ) {
        ...
        //直接释放hbp到GC_hblkfreelist链表中
        GC_freehblk(hbp);
    }
    else {
        ...
        GC_bool empty = GC_block_empty(hhdr);
        if (empty) {
            GC_freehblk(hbp);
        } else if (!GC_block_nearly_full(hhdr)) {
            struct hblk **rlh = ok -&gt; ok_reclaim_list;
            if (rlh != NULL) {
                rlh += BYTES_TO_GRANULES(sz);
                hhdr -&gt; hb_next = *rlh;
                *rlh = hbp;
            }
        }
    }
    ...
}
复制代码

分别对大内存和小内存块进行不同处理：

大内存

大内存比较特殊，因为一个大内存节点一般是由1～N个hblk内存块组成，不像小内存是由一个hblk等分成若干个小内存节点。因此，Header信息的hb_marks数组只存储一个标记位，即hb_marks[0]。

mark_bit_from_hdr(header, bit_no)用于获取header->hb_marks[bit_no]的值，如果是0，则这个大内存节点未被“引用”，调用GC_freehblk方法直接将其释放加入到GC_hblkfreelist链表中，同时把内存中的数据清空。供下次大内存分配使用。

小内存

对于小内存节点，因为提个hblk内存块上可能由若干个节点未“引用”，此时采用分情况处理的策略，有以下3种情况：

如果整个hblk为empty，即header->hb_n_marks=0，说明这个hblk内存块中没有被“引用”的内存节点，则直接释放整个内存块至GC_hblkfreelist，清空数据。
调用GC_block_nearly_full方法，判断这个hblk内存块中的节点是否大多数被“引用”，如果不是，则将这个hblk内存块加入待回收链表ok_reclaim_list，ok_reclaim_list和ok_freelist一样，提供128个链表，如图所示。根据内部等分的内存节点的大小，将hblk内存块加入相应的ok_reclaim_list中。例如hblk内部是16字节内存节点，则加入ok_reclaim_list[0]。
如果GC_block_nearly_full，则hblk内存块中大多数内存节点被“引用”，不将这个内存块加入ok_reclaim_list中。

GC_reclaim_all

GC_reclaim_all方法针对小内存对象，将刚才加入ok_reclaim_list中的所有hblk内存块进行处理，回收没有被“引用”的内存节点至ok_freelist链表中。代码逻辑如下：

GC_INNER GC_bool GC_reclaim_all(GC_stop_func stop_func, GC_bool ignore_old)
{
    ...
    for (kind = 0; kind &lt; GC_n_kinds; kind++) {
    ok = &amp;(GC_obj_kinds[kind]);
    rlp = ok -&gt; ok_reclaim_list;
    if (rlp == 0) continue;
    for (sz = 1; sz &lt;= MAXOBJGRANULES; sz++) {
      rlh = rlp + sz;
      while ((hbp = *rlh) != 0) {
        ...
        hhdr = HDR(hbp);
        *rlh = hhdr -&gt; hb_next;
        GC_reclaim_small_nonempty_block(hbp, FALSE);
      }
    }
  }
    ...
}
复制代码

遍历所有的ok_reclaim_list链表，取出hblk内存块，以及对应的header信息，调用GC_reclaim_small_nonempty_block方法处理，这里有两个参数，第一个参数传hblk内存块的地址，第二个参数report_if_found表示是否仅用于发现，不回收，这里传false，表示需要回收。方法如下：

STATIC void GC_reclaim_small_nonempty_block(struct hblk *hbp, GC_bool report_if_found)
{
  hdr *hhdr = HDR(hbp);
  word sz = hhdr -&gt; hb_sz;
  struct obj_kind * ok = &amp;GC_obj_kinds[hhdr -&gt; hb_obj_kind];
  //ok_freelist链表
  void **flh = &amp;(ok -&gt; ok_freelist[BYTES_TO_GRANULES(sz)]);
  ...

  //发现不回收
  if (report_if_found) {
    GC_reclaim_check(hbp, hhdr, sz);
  } else {
    //回收
    *flh = GC_reclaim_generic(hbp, hhdr, sz, ok -&gt; ok_init,
                 (ptr_t)(*flh), &amp;GC_bytes_found);
  }
}
复制代码

进入GC_reclaim_generic方法，再调用GC_reclaim_clear方法回收内存，主要逻辑如下：

STATIC ptr_t GC_reclaim_clear(struct hblk *hbp, hdr *hhdr, word sz,
               ptr_t list, signed_word *count)
{
    word bit_no = 0;
    word *p, *q, *plim;
    p = (word *)(hbp-&gt;hb_body);
    plim = (word *)(hbp-&gt;hb_body + HBLKSIZE - sz);

    while ((word)p &lt;= (word)plim) {
      if (mark_bit_from_hdr(hhdr, bit_no)) {
        p = (word *)((ptr_t)p + sz);
      } else {
          obj_link(p) = list;
          list = ((ptr_t)p);
          q = (word *)((ptr_t)p + sz);
          p++; /* Skip link field */
          while ((word)p &lt; (word)q) {
              *p++ = 0;
          }
     }
     bit_no += MARK_BIT_OFFSET(sz);
   }
   ...
}
复制代码

遍历hblk内存中的每个内存节点，如果mark_bit_from_hdr为1，表示被标记“引用”，不需要回收，否则将其加入list中，即ok_freelist链表。如图所示：

到此完成了所有内存节点的回收。

内存泄漏检测

除了回收逻辑，算法还可以检测内存泄漏，泄漏的对象即未被“引用”的托管堆内存节点。在GC_finish_collection方法中，还有一个检测内存泄漏的逻辑，最终也会调用GC_reclaim_small_nonempty_block方法，report_if_found传true，该逻辑只用于标记出那些未“引用”的内存节点，不实际回收他们，加入GC_leaked全局数组中。