深入解析 Hazard Pointer (下)

在前面几篇文章里，我们介绍了Hazard Pointer，一种用于lock free data structure设计中内存管理的利器，这个利器不仅思想简单，还可以用来防止ABA问题，读者诸君务必掌握。

本文作为第三部分，给出工业级代码中，实现Hazard Pointer的一些策略和需要注意的点。

Hazard Pointer管理

我们知道Hazard Pointer封装了原始指针，那么Hazard Pointer的内存和生命周期本身如何管理呢？以下是常见的策略：

1，Hazard Pointer本身的内存只分配，不释放。在stack、queue等数据结构里，需要的Hazard Pointer数量一般为1或者2，所以不释放问题不大。对于skip list这种数据结构又有遍历需求的，那么Hazard Pointer可能就不是非常适用了，可以考虑使用Epoch Based Reclamation技术。据我所知，这也是memsql使用的内存回收策略。

2，每个线程拥有、管理自己的retire list和hazard pointer list ，而不是所有线程共享一个retire list，这样可以避免维护retire list和hazard pointer list的开销，否则我们可能又得想尽脑汁去设计另外一套lock free的策略来管理这些list，先有鸡先有蛋，无穷无尽。所谓retire list就是指逻辑删除后待物理回收的指针列表。

3，每个线程负责回收自己的retire list中记录维护的内存。这样，retire list是一个线程局部的数据结构，自己写，自己读，吃自己的狗粮。

4，只有当retire list的大小（数量）达到一定的阈值时，才进行GC。这样，可以把GC的开销进行分摊，同时，应该尽可能使用Jemalloc或者TCmalloc这些高效的、带线程局部缓存的内存分配器。

acquire和release动作

所谓acquire，就是线程需要对一个资源进行访问，需要对它进行保护；所谓release，就是线程停止对资源的访问，结束对它的保护。

这两个动作基本上都是成对出现的，因此，可以封装成一个Guard。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

   struct HazardPointerRecord
    {
      HazardPointerRecord(HplfdsHazardPointer<MemoryAllocator> &manager,
                          void *p, int thread_id): manager_(manager)
      {
        p_ = p;
        thread_id_ = thread_id;
        manager.acquire(p_, thread_id_);
      }
      ~HazardPointerRecord()
      {
        manager_.release(p_, thread_id_);
      }
      HplfdsHazardPointer<MemoryAllocator> &manager_;
      void *p_;
      int thread_id_;
    };
    
    #define ACQUIRE_POINTER(p)\
  HazardPointerRecord record##p(memory_manager_, p, thread_id);