断更太久，实在是最近太忙… 焦头烂额ing

核心思想

这篇文章会介绍hazard pointer，和EBR、RCU一样，也是一种安全内存回收机制(SMR，safe memory reclamation)。它可以让读线程就将正在使用的对象内存地址告知其他线程，并由写线程在合适的实际回收相应内存。其核心思想是：当一个读线程将一个对象的地址赋给它的hazard pointer时，即意味着它在向其它线程宣称：“我正在读该指针所指向的对象，如果你愿意，你可以将指针指向其他对象，但别修改我正在读的对象，当然更不要去delete这个指针。”

我们将结合实际使用来看hazard pointer的原理，假设有个读多写少的WRRMMap(Write-Rarely-Read-Many Map)，它内部有一个指向某个经典的单线程map对象（比如std::map）的指针，同时它还向外界提供了线程安全的读写接口。

不用太纠结于具体实现，下面会逐步解释为什么

template <class K, class V>
class WRRMMap {
 public:
  map<K, V>* pMap_;

  void Update(const K& k, const V& v);

  V Lookup(const K& k);
};

在用hazard pointer时，每当WRRMMap需要更新的时候，想要对它进行更新的线程就会首先复制一个pMap_所指向的对象，在新版本上做修改，然而再将pMap_指向新版本，最后在合适的时机delete掉pMap_原先所指的旧版本。这里的copy-on-write有一定性能开销，但因为WRRMMap通常是读多写少，所以是可以接受的。然而，麻烦的问题是我们怎样才能妥善地将就副本销毁掉，因为任何时候都可能有其它线程正在对它们进行读取。

数据结构

// Hazard pointer record
class HPRecType {
  HPRecType* pNext_;
  int active_;
  // Global header of the HP list
  static HPRecType* pHead_;
  // The length of the list
  static int listLen_;

 public:
  // Can be used by the thread that acquired it
  void* pHazard_;

  static HPRecType* Head() {
    return pHead_;
  }

  static HPRecType* Acquire();

  static void Release(HPRecType* p);
};

// Per-thread private variable
thread_local vector<Map<K, V>*> rlist;

要实现上面的功能，hazard pointer采取的也是延迟释放内存的方式。pHead_是一个全局链表，用来保存正在使用或者曾经被使用过的map指针，整个链表通过CAS来进行修改，pNext_指向链表的下一个节点。pHazard_就是所谓的hazard pointer，它用来给读线程保存当前读取对象的指针，如果pHazard_不为空，其他线程就无法回收pHazard_所指向对象占用的内存。此外每个线程都拥有一个退役链表rlist（在我们的实现中，这实际上就是一个vector<Map<K,V>*>），退役链表rlist负责存放该线程不再需要的，一旦其它线程也不再使用它们就可以被delete掉的指针。rlist的访问不需要被同步，它是个thread_local变量。

实现细节

读流程

V Lookup(const K& k) {
  HPRecType* pRec = HPRecType::Acquire();
  Map<K, V>* ptr;
  do {
    ptr = pMap_;
    pRec->pHazard_ = ptr;
  } while (pMap_ != ptr);

  // Save Willy
  V result = (*ptr)[k];
  // pRec can be released now, because it's not used anymore
  HPRecType::Release(pRec);
  return result;
}
  1. 每当需要从pMap_中读取数据时，先要调用HPRecType::Acquire来获取一个HPRecType并将其加入到全局链表中，此时我们获取的pRec就是当前线程所独自占用的。

  2. 接下来在while循环中，读线程不断尝试将HPRecType的pHazard_置为ptr，通过这一步来宣布当前ptr指向的对象有读线程正在使用。这里会通过不断检查pMap_和ptr是否相等，保证这几步操作过程中， ptr始终和pMap_相等。

    后面还会详细解释这个while循环的作用

  3. 之后就可以对ptr所指向对象进行读取了。(注意不是使用pMap_，因为pMap_可能又被修改过，从这个角度看ptr获取的是pMap_的一个快照版本，而不一定是最新版本)
  4. 使用完之后，需要调用HPRecType::Release。这一步会在全局链表中将之前通过Acquire申请的节点标记为过期，此后ptr指向的内存就可以被回收。

我们可以具体看下Acquire和Release的实现：

class HPRecType {
  // ...

  // Acquires one hazard pointer
  static HPRecType* Acquire() {
    // Try to reuse a retired HP record
    HPRecType* p = pHead_;
    for (; p; p = p->pNext_) {
      if (p->active_ || !CAS(&p->active_, 0, 1)) {
        continue;
      }
      // Got one!
      return p;
    }

    // Increment the list length
    int oldLen;
    do {
      oldLen = listLen_;
    } while (!CAS(&listLen_, oldLen, oldLen + 1));

    // Allocate a new one
    HPRecType* p = new HPRecType;
    p->active_ = 1;
    p->pHazard_ = 0;

    // Push it to the front
    do {
      old = pHead_;
      p->pNext_ = old;
    } while (!CAS(&pHead_, old, p));

    return p;
  }

  // Releases a hazard pointer
  static void Release(HPRecType* p) {
    p->pHazard_ = 0;
    p->active_ = 0;
  }

  // ...
}

Acquire中就是在全局链表中寻找一个可用节点，如果没找到就新增一个节点。然后将节点标记为active，并将这个节点返回。Release就是将之前Acquire获取的节点清空，并标记为inactive。

写流程

void Update(const K& k, const V& v) {
  Map<K, V>* pNew = 0;
  do {
    Map<K, V>* pOld = pMap_;
    delete pNew;
    pNew = new Map<K, V>(*pOld);
    (*pNew)[k] = v;
  } while (!CAS(&pMap_, pOld, pNew));
  Retire(pOld);
}

写流程是典型copy-on-write，pNew = new Map<K, V>(*pOld)，然后在新版本上进行修改，最后尝试将新版本替换进pMap_。在更新成功之后，就可以调用Retire将旧版本退役，表示如果其他线程也不再使用这个过期副本之后，就可以回收对应内存。

Retire逻辑如下，每当一个写线程替换pMap_时，它会将替换下来的旧map指针放入一个thread_local链表中。直到该链表中的旧map达到一定数量的时候，写线程就会扫描读线程的hazard pointer，看看旧map列表中有哪些是与这些hazard pointer匹配的。匹配就代表仍有读线程在使用，不能回收对应内存，写线程就会仍将其保留在链表中，直到下次扫描。如果某个旧map不与任何读线程的hazard pointer匹配，那么就将其内存回收。这里的终点在于写线程在delete任何被替换下来的旧map之前须得检查其他读线程的hazard pointer所指向的map是否仍在被使用。任何一个hazard pointer指向的对象，都需要读线程显式告知不再使用这些对象之后（即上面读流程所说的Release接口），才可能会被回收内存。

template <class K, class V>
class WRRMMap {
  Map<K, V>* pMap_;

 private:
  static void Retire(Map<K, V>* pOld) {
    // put it in the retired list
    rlist.push_back(pOld);
    if (rlist.size() >= R) {
      Scan(HPRecType::Head());
    }
  }

  void Scan(HPRecType* head) {
    // Stage 1: Scan hazard pointers list collecting all non-null ptrs
    vector<void*> hp;
    while (head) {
      void* p = head->pHazard_;
      if (p) {
        hp.push_back(p);
      }
      head = head->pNext_;
    }

    // Stage 2: sort the hazard pointers
    sort(hp.begin(), hp.end(), less<void*>());

    // Stage 3: Search for'em!
    vector<Map<K, V>*>::iterator i = rlist.begin();
    while (i != rlist.end()) {
      if (!binary_search(hp.begin(), hp.end(), *i) {
        // Aha!
        delete *i;
        if (&*i != &rlist.back()) {
          *i = rlist.back();
        }
        rlist.pop_back();
      } else {
        ++i;
      }
    }
  }
};

回收内存的Scan函数会进行一个差集计算的算法，即当前线程的退役链表rlist作为一个集合，其它所有线程的hazard pointer作为一个集合，求它们两个的差集。那么，这个差集的意义又是什么呢？前一个集合是当前线程所认为没有用的旧map指针，而后一个集合则代表那些正被其他线程使用着的旧map指针（即那些线程的hazard pointer所指的map），这些指针在读线程使用完之后，就会将指针进行退役。如果一个指针退役了并且没有被任何一个线程的hazard pointer所指向（也就是使用）的话，该指针所指的旧map就是可以被安全回收的的。换言之，第一个集合与第二个集合的差集正是那些可被安全delete的旧map的指针。

在进行Scan时，我们需要对rlist跟pHead这个hazard pointer链表所代表的两个集合作差集运算。换而言之：“对于rlist中的每个指针，检查它是否同位于hazard pointer链表中，如果不是，则它属于差集，即可被安全delete。”此外，为了对该算法加以优化，我们可以在行查找之前先对hazard指针链表进行排序，然后对每个退役指针在其中进行二分查找。

其中运用了一点小小的技巧来避免rlist这个vector的重排：在delete了rlist中的一个可被删除的指针之后，我们将那个指针的位置用rlist的最后一个元素来填充，然后再将实际的最后一个元素pop掉。这样做是允许的，因为rlist中的元素并不要求有序。

“细枝末节”

V Lookup(const K&k){
   HPRecType * pRec = HPRecType::Acquire();
   Map<K, V> * ptr;
   do {
      ptr = pMap_;
      pRec->pHazard_ = ptr;
   } while (pMap_ != ptr);

   // Save Willy
   V result = (*ptr)[k];
   // pRec can be released now, because it's not used anymore
   HPRecType::Release(pRec);
   return result;
}

在上面的代码中，为什么读线程需要重新检查pMap_是否等于ptr呢？考虑下面这种情况：pMap_原先指向一个map m，读线程将ptr赋为pMap_，也就是&m，接着读线程就进入了休眠（此时它还未来得及将hazard pointer指向m）。而就在它的休眠期间，一个写线程更新了pMap_，然后将pMap_原先所指的map，即m放到了退役链表中，并紧接着检查各线程的hazard pointer，由于刚才的读线程在进入休眠时还未来得及设置hazard pointer，故m被认为是可以销毁的旧map，于是被写线程销毁。而这时读线程被唤醒，将Hazard pointer赋为ptr(即&m)。如果是这样的话，一旦读线程接下来对ptr进行解引用，它就会读取到被破坏的数据或访问了未被映射的内存。如果结果发现pMap_并不等于&m的话，读线程就无法确定将m退役掉的写线程是否看到了它的hazard指针被置为&m（换句话说，是否已将m销毁）。所以此时读线程继续对m进行读取就是不安全的，所以读线程需要从头来过。

如果读线程而后发现pMap_的确指向m，那么此时从m读取就是安全的。那么，这是否意味着在两次读取pMap_之间，pMap_没有被改动过呢？不一定，在这期间pMap_可能被修改指向n，然后又指回m，但这并不要紧。要紧的是在第二次读取的时候pMap_指向m，而此时对应的hazard pointer pHazard_也已经指向它了。

void Update(const K&k, const V&v) {
   Map<K, V> * pNew = 0;
   do {
      Map<K, V> * pOld = pMap_;
      delete pNew;
      pNew = new Map<K, V>(*pOld);
      (*pNew)[k] = v;
   } while (!CAS(&pMap_, pOld, pNew));
   Retire(pOld);
}

同样，可能有多个线程会进行更新，所以更新pMap_需要使用CAS操作。如果CAS失败，需要将上一次更新的副本删除。

写在最后

但是，真的有这么简单吗？按照原始论文尝试去实现了一版hazard pointer，有不少内存泄露。想要通过sanitizer，还需要大量的改动，我们下一篇再说。

Reference

Lock-Free Data Structures with Hazard Pointers Hazard Pointers: Safe Memory Reclamation for Lock-Free Objects

You May Also Enjoy

Coroutine internals

上次研究了Fiber，这次结合C++ Coroutines TS(N4680)和folly::coro::Baton，看看Coroutine~

Jemalloc 5.3.0 internals, part 3

上一篇介绍了hpa (huge page allocator)，这一篇继续介绍物理层的另一种page allocator: pac (page allocator classic)。