上一篇文章介绍了无锁化编程场景下的一种垃圾回收机制，Epoch-based Memory Reclaimation（EB)。 本篇介绍另一种无锁化编程场景下的垃圾回收机制，Hazard Pointer（HP）。HP也是一种确定型GC。

HP的内存回收办法比较简单： 对无锁化编程场景下的每个线程，须要显式标注出该线程要竞争拜访的共享对象，即线程把要竞争拜访的对象的指针标注为危险指针（Hazard Pointer）， 拜访完结后或勾销标注该危险指针、或标注该危险指针指向的共享对象为待回收。 在回收内存时，HP判断每个待回收的共享对象是否能够平安回收，只须要查看该对象的指针是否正被某个线程标注为危险指针，如果没有就能回收，否则不能回收。 HP跟EB一样也是采纳空间换工夫的策略，并不是马上回收每个能够被回收的共享对象，而是批量回收，以缩小内存回收对程序性能的影响。

确定型GC算法Hazard Pointer（HP）

持续沿用无锁化堆栈作为例子来展现HP的用法，而后再介绍HP的细节。

Hazard Pointer（HP）的用法

采纳HP作为GC的无锁化堆栈的入栈和出栈操作实现如下所示。

struct Node {    void* data;    std::atomic< Node * > next;};std::atomic<Node *> top; // 栈顶top.store( nullptr ); // 初始化栈顶为空指针bool push( Node* new_node ) {    // 线程本地的危险指针队列里新增一个危险指针    HP * hazard_cur_top = LocalHP::new_hp();        while ( true ) {        Node * cur_top = top.load();        // 标注以后栈顶指针cur_top为危险指针        hazard_cur_top.set(cur_top);        new_node->next.store( cur_top );                // CAS调用批改栈顶        if ( top.compare_exchange_weak(                cur_top, new_node )) {            break; // 批改栈顶胜利        }    }    // 入栈操作胜利，勾销标注cur_top为危险指针    hazard_cur_top.set(nullptr);    return true;}Node * pop() {    // 线程本地的危险指针队列里新增两个危险指针    HP * hazard_cur_top = LocalHP::new_hp();    HP * hazard_next = LocalHP::new_hp();    while ( true ) {        Node * cur_top = top.load();        if ( cur_top == nullptr ) {            break; // 堆栈为空        }        // 标注以后栈顶指针cur_top为危险指针        hazard_cur_top.set(cur_top);        Node * next = cur_top->next.load();        // 标注以后栈顶的下一节点指针next为危险指针        hazard_next.set(cur_top);                // CAS调用批改栈顶        if ( top.compare_exchange_weak(                cur_top, next )) {            break; // 批改栈顶胜利        }    }    if ( cur_top != nullptr ) {        // 出栈操作胜利，标注cur_top为待回收对象        hazard_cur_top.maybe_reclaim();    } else {        // 栈为空，勾销标注cur_top为危险指针        hazard_cur_top.set(nullptr);    }    // 出栈操作完结，勾销标注next为危险指针    hazard_next.set(nullptr);    return cur_top;}

下面的实现能够看出，入栈操作和出栈操作有不同的危险指针。对于入栈操作：

  • 入栈操作只批改堆栈的以后栈顶指针，因而只须要标注一个危险指针，即以后栈顶为危险指针；
  • 入栈操作里每次循环，会更新栈顶指针，同时也要更新危险指针，即只把最新的栈顶指针标注为危险指针；
  • 入栈操作胜利后，勾销标注该危险指针，因为原栈顶节点还在堆栈里，不能被回收，即入栈操作不产生待回收对象。

对于出栈操作：

  • 出栈操作会批改堆栈的以后栈顶指针以及栈顶的下一节点指针，因而要标注两个危险指针；
  • 出栈操作里每次循环，要更新栈顶指针和栈顶的下一节点指针，同时也要更新对应的两个危险指针；
  • 如果出栈操作失败，即堆栈为空，则勾销标注这两个危险指针；
  • 如果出栈操作胜利，要标注以后栈顶指针为待回收对象，并勾销标注栈顶的下一节点指针为危险指针。

HP如何平安回收内存？

为什么HP能保障平安回收内存呢？这里咱们只思考出栈操作，因为入栈操作不波及内存回收。

假设有两个线程A和B同时调用无锁化堆栈的出栈操作，这两个线程都读取了以后栈顶指针cur_top， 这时线程A被抢占导致休眠，线程B继续执行出栈操作并胜利取出cur_top指向的栈顶节点。 线程B因为胜利执行出栈操作而标注cur_top指向的原栈顶节点为待回收对象，然而此时尚不能回收cur_top， 因为线程A还未执行结束出栈操作，即线程A标注cur_top为危险指针。 只有等线程A复原执行后，发现cur_top曾经不是最新的栈顶指针，更新了栈顶指针并更新了对应的危险指针之后，能力平安回收原栈顶节点的内存。

由此可见，HP判断共享对象是否可回收的办法和上一篇Blog里介绍的EB不一样。 EB是标注出每个线程对共享对象的拜访阶段，有点像是标注出临界区，不同的拜访阶段产生不同的待回收对象指针，而后回收处于最老阶段的待回收对象的内存； HP是标注出每个线程要批改的共享对象的指针，而不是标注出临界区，因而HP标注的粒度更细。 然而HP和EB的回收策略类似，都是批量回收。

Hazard Pointer（HP）的实现

HP的实现比拟直观，简略形容下HP的实现机制：

  • 每个线程保护一个本地队列LocalHP，用于保留线程本地标注的危险指针；
  • 再保护一个全局队列GlobalHP，用于保留待回收对象指针；
  • 每次线程调用maybe_reclaim()标注某个危险指针为待回收对象时，把该待回收对象从本地队列推送到全局队列；
  • 如果调用maybe_reclaim()推送待回收对象时，发现全局队列已满，则触发内存回收， 即一一查看全局队列里每个待回收对象是否可回收，同时回收可回收对象的内存并从全局队列中删除之。

可见HP也是确定型GC，内存回收产生在调用maybe_reclaim()且全局队列已满时。此外，LocalHP和GlobalHP要采纳无锁化队列，来保障HP的实现也是无锁的。

HP尽管比较简单直观，然而HP在内存回收时的开销比EB大， 因为HP要一一判断全局队列里每个待回收对象是否可回收，即查看每个待回收对象的指针是否有被某个线程正标注为危险指针， 如果待回收对象比拟多，而且线程也比拟多，那查看工作量会比拟大； 而EB在回收内存时，一股脑回收处于最老阶段的所有待回收对象，每个待回收对象在回收前曾经关联了其产生的阶段，回收时无需挨个查看每个待回收对象。

libcds里曾经有HP的C++实现，开发者无需自行实现HP。

作者 | 王璞