无锁化编程场景下的垃圾回收机制（一）

之前的一篇Blog里介绍了无锁化编程场景下需要垃圾回收机制，我称之为确定型垃圾回收机制（GC），这是相对Java的GC而言。 Java的GC什么时候回收内存，这对开发者来说是不确定也不可预知的。而无锁化编程场景下的内存回收，是确定并可预知的，同时对开发者来说也是透明的，即开发者不用关心无锁化编程场景下的垃圾回收。确定型GC最大的好处是，对性能的开销很小，这也是相对Java的GC而言。为什么确定型GC性能好？原因很简单，因为确定型GC只处理无锁化编程场景下的内存回收，所以考虑的情况少很多，而Java的GC要处理各种场景下的内存回收，显然Java的GC要复杂得多。套用第一性原理，简单的东西，才能效率高，性能好。

此外，在之前的Blog里也提到，通常情况下开发者自行管理内存并不复杂，但是无锁化编程场景是个例外。因为没有锁，无锁化编程无法保证共享数据在某个时刻只被一个线程独享，因此在无锁化编程场景下，某个线程不能在消费完共享数据里的某个对象后马上delete以回收其内存。不然的话，一个线程把一个共享对象delete了，如果另一个线程仍然持有该对象的指针，那这个指针就变成野指针了，一旦访问野指针会导致程序崩溃。于是，在无锁化编程场景下，确定型GC帮助开发者回收内存，同时确定型GC也对开发者透明，让开发者无需关心何时内存被回收。有了确定型GC的帮助，用C、C++这类没有GC的语言进行无锁化编程的难度大大降低。

一种确定型GC算法Epoch-based Memory Reclaimation（EB）

下面介绍一种比较常见的确定型GC的算法，Epoch-based Memory Reclaimation（简称EB）。 EB核心要解决的问题是，什么时候才能安全的回收内存，即确保待回收的对象不会被任何线程访问时，才可以安全回收。如果采用引用计数的方式来跟踪每个对象是否还被线程在访问，这种方式成本太高，而且效率太差。 EB的做法是把待回收对象分成不同的阶段，不着急马上回收每个可以被安全回收的对象，而是批量按阶段回收。这是一种以空间换时间的做法，不马上回收每个可以被安全回收的对象，降低了回收内存对性能的影响，但也占用了更多的内存。

EB定义了三个阶段，分别为阶段0、阶段1、阶段2，同时EB给每个待回收对象都标识其所处阶段。 EB在三个阶段之间单向轮转，或从阶段0进入阶段1，或从阶段1进入阶段2，或从阶段2回到阶段0，循环往复。同时EB定义了阶段跨越的条件，条件满足才能从当前阶段转到到下个阶段。

EB定义这三个阶段，以及阶段跨越的条件，是为了保证可以安全批量回收内存。EB保证可以安全回收当前阶段的两个阶段前的待回收对象。比如EB当前处于阶段2，则EB可以安全回收阶段0的对象；再比如EB当前处于阶段0，则EB可以安全回收阶段1的对象。为什么EB可以安全回收处于当前阶段的两个阶段前的对象？下面先用一段代码描述EB的使用场景，然后再介绍EB如何安全回收内存。

Epoch-based Memory Reclaimation（EB）的用法

还是沿用之前Blog里介绍的无锁化堆栈的例子。无锁化堆栈被多个线程共享，栈顶节点是被多个线程共享的对象。某个线程调用无锁化堆栈的出栈方法取出栈顶节点并消费后，并不能马上delete这个栈顶节点以回收该节点的内存，因为无法保证没有其他线程也在访问该栈顶节点，即无法保证没有其他线程也在调用出栈方法——读取该栈顶节点的指针并准备修改新的栈顶节点为该栈顶节点的的下一节点。下面的代码片段采用EB来管理待回收栈顶节点，EB的做法是不着急马上回收栈顶节点的内存，先保存下来后续再批量回收。

struct Node {
    void* data;
    std::atomic< Node * > next;
};

std::atomic<Node *> top; // 栈顶
top.store( nullptr ); // 初始化栈顶为空指针

bool push( Node* new_node ) {
    // 标识当前线程要修改共享数据
    EB::enter();

    while ( true ) {
        Node * cur_top = top.load();
        new_node->next.store( cur_top );
        
        // CAS调用修改栈顶
        if ( top.compare_exchange_weak(
                cur_top, new_node )) {
            break; // 修改栈顶成功
        }
    }

    // 结束修改共享数据
    EB::leave();
    return true;
}

Node * pop() {
    // 标识当前线程要修改共享数据
    EB::enter();

    while ( true ) {
        Node * cur_top = top.load();
        if ( cur_top == nullptr ) {
            break; // 堆栈为空
        }
        Node * next = cur_top->next.load();
        
        // CAS调用修改栈顶
        if ( top.compare_exchange_weak(
                cur_top, next )) {
            // 出栈节点指针传给EB由其后续回收
            EB::add( cur_top );
            break; // 修改栈顶成功
        }
    }

    // 结束修改共享数据
    EB::leave();
    return cur_top;
}

上面的代码片段里可以看到对于入栈push()和出栈pop()这两个函数，都用EB::enter()和EB::leave()把对共享数据——无锁化堆栈的修改操作保护起来。入栈操作不产生待回收对象，出栈操作里把出栈的栈顶节点的指针传给EB::add()，由EB后续回收该节点的内存。虽然使用EB::enter()和EB::leave()有点像是访问由锁保护的临界区以修改共享数据：

enter_critical_section(); // 进入临界区

// 修改共享数据

exit_critical_section(); // 离开临界区

但是其实EB的做法和基于锁实现的临界区的做法大相径庭。下面详细介绍EB的具体实现。

Epoch-based Memory Reclaimation（EB）的实现

首先，EB维护一个全局队列，用于保存待回收对象的指针，并且EB用一个全局变量标识出当前所处的阶段（称为全局阶段），初始为阶段0。然后，EB为每个线程维护一个本地队列，用于保存该线程的待回收对象的指针，同时EB为每个线程用线程本地变量维护一份EB全局阶段的副本（称为本地阶段）。接下来每个线程把要访问共享数据进行修改的操作，都用EB::enter()和EB::leave()保护起来，并且把待回收的对象指针通过EB::add()传给EB以后续回收。 EB::enter()、EB::add()和EB::leave()的实现如下所示。

EB::enter()的操作：

如果某线程是第一次调用EB::enter()，则为该线程创建一个本地队列，用于保存该线程待回收对象的指针，并为其创建本地阶段的变量，以及是否在修改共享数据的布尔变量；
读取EB当前全局阶段，并复制给该线程的本地阶段变量；
尝试使EB的全局阶段跨越至下一阶段并尝试回收内存：
- 检查每个线程的本地阶段是否一致，即是否都处于同一阶段，如有不一致则放弃，转去执行第4步；
- 如果上面条件满足，则EB的全局阶段跨越至下个阶段，并从EB维护的全局队列中回收当前全局阶段的两个阶段前的对象的内存，然后执行第4步；
标记当前线程正在修改共享数据；

可以看出，EB::enter()负责标识某个线程正在修改共享数据，并尝试把全局阶段跨越至下个阶段并回收内存。在第3步，EB::enter()先检查阶段跨越的条件，满足条件时全局阶段进入下一个阶段，然后回收当前全局阶段的两个阶段前的对象。由此，EB回收内存的确定性指的就是调用EB::enter()会回收内存，而且EB::enter()是批量回收，即批量回收全局阶段的两个阶段前的对象。当然EB::enter()并不能保证每次被调用就一定能成功回收内存，因为要先满足阶段跨越的条件之后才能回收内存。而且为了减少内存回收对性能的影响，在具体实现EB::enter()的时候，往往是EB::enter()被调用一定次数之后才尝试执行第3步回收内存。此外要注意，如果EB::enter()成功跨越全局阶段至下个阶段，并不意味着每个线程的本地阶段也都同步到下个阶段，这要等每个线程下次调用EB::enter()完成全局阶段和本地阶段的同步。同时线程本地阶段最多落后全局阶段一个阶段，不会落后两个或更多阶段。

EB::add()的操作：

把调用EB::add()输入的待回收对象指针存入本地线程的队列（只存入非空对象指针），并标记待回收对象指针所处的阶段为当前本地阶段（不是用全局阶段标记）；
如果本地线程的队列已满，则把本地队列里的待回收对象都移到EB维护的全局队列。

可以看出，EB::add()把待回收对象的指针加入本地队列，如果本地队列已满，则把本地队列的元素移到全局队列。有一个细节要注意，EB::add()是用其所处线程的本地阶段给输入的待回收对象指针标记，而不是用全局阶段标记，其原因下文解释。

EB::leave()的操作：

标记当前线程没有在修改共享数据。

可以看出，EB::leave()比较简单，仅标记当前线程结束对共享数据的修改。

EB如何安全回收内存？

那为什么EB回收当前全局阶段的两个阶段前的对象是安全的呢？

首先，在一个线程里，待回收对象只会关联一个线程的本地阶段，不会关联多个阶段，因为线程的每个待回收对象只能传给EB::add()一次（EB::add()会为待回收对象标记当前本地阶段），不然会出现double delete。一个待回收对象在当前线程本地阶段交给EB之后，线程要么不再访问该对象，要么只能在当前本地阶段内继续访问该对象。如果线程在下个阶段还要访问该对象，那这个对象就不应该是当前阶段待回收的，而EB::add()只应该用于收集线程在当前阶段待回收的对象。因此，当一个线程处于某个阶段，这个线程不会再访问前一个阶段的待回收对象，即线程不会保留着前一个阶段的待回收对象的指针。怎么理解呢？举个例子来说明。下面是一段对无锁化堆栈执行出栈操作的线程函数代码片段：

while ( true ) {
    Node * pop_node = pop();
    if ( pop_node ) {
        // 消费出栈节点
        ...
    } else {
        break;
    }
}

上面的线程函数代码里用循环不停地调用无锁化堆栈的出栈操作并消费出栈节点。假定有多个线程运行上面的线程函数以并发调用出栈操作并消费栈顶节点。由上面的例子可以看出：

线程的本地阶段不停地跨越至下个阶段，因为线程循环调用出栈操作，进而循环调用EB::enter()使得线程本地阶段不停地跨越至下个阶段（出栈操作里的EB::enter()有可能改变线程的本地阶段）；
对待回收对象——非空栈顶节点的访问是从出栈操作返回后到下次调用出栈操作前结束，即对栈顶节点的访问在下次出栈操作调用EB::enter()前完成，而下次出栈有可能使线程进入下一个阶段。

可见，上面例子里对待回收对象——非空栈顶节点的访问是仅限当前本地阶段，进入下一个阶段（某次调用出栈操作使得本地阶段跨越至下一阶段）是不会再访问前一个阶段的栈顶节点。因此，对每个线程来说，当前本地阶段的前一个阶段的待回收对象是有可能被安全回收的，至少当前线程不会再访问前一个阶段的待回收对象。

其次，EB的阶段跨越条件保证了，每个线程的本地阶段要么跟全局阶段一致，要么处于全局阶段的前一阶段，不可能出现某个线程的本地阶段处于全局阶段的前两个阶段。回顾EB::enter()里第三步检查阶段跨越的条件：全局阶段跨越至下个阶段前，要求所有线程的本地阶段都一致。这就保证了线程的本地阶段最多落后全局阶段一个阶段，不会落后两个或更多阶段。前面提到，对每个线程来说，不会再访问其当前本地阶段的前一个阶段的待回收对象，如果所有线程的本地阶段都一致，处于同一个阶段，那么所有线程都不会再访问前一个阶段的待回收对象，这意味着当所有线程的本地阶段都一致，处于同一个阶段，那么前一个阶段的待回收对象的内存可以被安全回收。此外，线程的当前本地阶段最多落后全局阶段一个阶段，而且每个线程调用EB::add()回收对象时，EB::add()都用其被调用时当前本地阶段标识待回收对象，那么对于全局阶段来说，当前全局阶段的两个阶段前的待回收对象是可以被安全回收的。

EB算法的无锁化实现

EB的实现要求不能用锁，不然采用EB作为GC的无锁化编程就不是真正的无锁化。

EB的全局状态会被多个线程竞争访问并修改，可以实现无锁化：

全局队列采用无锁化队列；
全局阶段采用原子变量。

EB的线程本地状态也可以实现无锁化：

线程的本地队列的访问和修改无需加锁，因为只有本地线程访问并修改；
线程本地阶段采用原子变量，因为其他线程调用EB::enter()会检查所有线程的本地阶段是否一致；
标记当前线程的状态无需加锁，因为只有本地线程访问并修改。

不同线程并发调用EB::enter()导致的竞争主要集中在对全局阶段和全局队列的修改：

不同线程竞争修改全局阶段至下一个阶段，这并不会导致不一致状态，一方面由于全局阶段是原子变量，另一方面不同线程对全局阶段的修改都是改为下一个阶段，这是阶段跨越条件决定的；
不同线程竞争修改全局队列，回收当前全局阶段的两个阶段前的对象，由于全局队列是无锁化队列，因此也不会导致不一致状态。

类似的，不同线程并发调用EB::add()导致的竞争主要集中在对全局队列的修改：

不同线程竞争修改全局队列，把本地队列的元素加入全局队列，由于全局队列是无锁化队列，因此也不会导致不一致状态。

对EB::add()的调用不存在竞争，因为EB::add()仅修改线程本地变量。

总之，EB是无锁化编程场景的一种确定型GC：

开发者显式调用EB::enter()标识对共享数据的修改，同时EB::enter()负责回收内存；
开发者显式调用EB::add()把待回收对象传给EB以后续回收；
开发者显式调用EB::leave()标识对共享数据的修改已结束。

EB采用延迟分阶段批量回收，不见得每次调用EB::enter()一定马上回收内存，这是以空间换时间的策略，用于降低内存回收对性能的影响。相比Java的GC，其回收内存是不确定的，开发者并不会明确调用Java的某个函数以回收内存，开发者也不会显式告诉Java的GC哪些是待回收对象。因此，EB要考虑的场景相比Java的GC来说少很多，这也保证了EB对性能的影响比Java的GC小。