并行编程中的内存回收Hazard Pointer

接上篇使用RCU技术实现读写线程无锁，在没有GC机制的语言中，要实现Lock free的算法，就免不了要自己处理内存回收的问题。

Hazard Pointer是另一种处理这个问题的算法，而且相比起来不但简单，功能也很强大。锁无关的数据结构与Hazard指针中讲得很好，Wikipedia Hazard pointer也描述得比较清楚，所以我这里就不讲那么细了。

一个简单的实现可以参考我的github haz_ptr.c

原理

基本原理无非也是读线程对指针进行标识，指针(指向的内存)要释放时都会缓存起来延迟到确认没有读线程了才对其真正释放。

<Lock-Free Data Structures with Hazard Pointers>中的描述：

Each reader thread owns a single-writer/multi-reader shared pointer called “hazard pointer.” When a reader thread assigns the address of a map to its hazard pointer, it is basically announcing to other threads (writers), “I am reading this map. You can replace it if you want, but don’t change its contents and certainly keep your deleteing hands off it.”

关键的结构包括：Hazard pointer、Thread Free list

Hazard pointer：一个读线程要使用一个指针时，就会创建一个Hazard pointer包装这个指针。一个Hazard pointer会被一个线程写，多个线程读。

struct HazardPointer {
        void *real_ptr; // 包装的指针
        ... // 不同的实现有不同的成员
    };

    void func() {
        HazardPointer *hp = accquire(_real_ptr);
        ... // use _real_ptr
        release(hp);
    }

Thread Free List：每个线程都有一个这样的列表，保存着将要释放的指针列表，这个列表仅对应的线程读写

void defer_free(void *ptr) {
        _free_list.push_back(ptr);
    }

当某个线程要尝试释放Free List中的指针时，例如指针ptr，就检查所有其他线程使用的Hazard pointer，检查是否存在包装了ptr的Hazard pointer，如果没有则说明没有读线程正在使用ptr，可以安全释放ptr。

void gc() {
        for(ptr in _free_list) {
            conflict = false
            for (hp in _all_hazard_pointers) {
                if (hp->_real_ptr == ptr) {
                    confilict = true
                    break
                }
            }
            if (!conflict)
                delete ptr
        }
    }

以上，其实就是Hazard Pointer的主要内容。

Hazard Pointer的管理

上面的代码中没有提到_all_hazard_pointers及accquire的具体实现，这就是Hazard Pointer的管理问题。

《锁无关的数据结构与Hazard指针》文中创建了一个Lock free的链表来表示这个全局的Hazard Pointer List。每个Hazard Pointer有一个成员标识其是否可用。这个List中也就保存了已经被使用的Hazard Pointer集合和未被使用的Hazard Pointer集合，当所有Hazard Pointer都被使用时，就会新分配一个加进这个List。当读线程不使用指针时，需要归还Hazard Pointer，直接设置可用成员标识即可。要gc()时，就直接遍历这个List。

要实现一个Lock free的链表，并且仅需要实现头插入，还是非常简单的。本身Hazard Pointer标识某个指针时，都是用了后立即标识，所以这个实现直接支持了动态线程，支持线程的挂起等。

在nbds项目中也有一个Hazard Pointer的实现，相对要弱一点。它为每个线程都设置了自己的Hazard Pointer池，写线程要释放指针时，就访问所有其他线程的Hazard Pointer池。

typedef struct haz_local {
        // Free List
        pending_t *pending; // to be freed
        int pending_size;
        int pending_count;

        // Hazard Pointer 池，动态和静态两种
        haz_t static_haz[STATIC_HAZ_PER_THREAD];

        haz_t **dynamic;
        int dynamic_size;
        int dynamic_count;

    } __attribute__ ((aligned(CACHE_LINE_SIZE))) haz_local_t;

    static haz_local_t haz_local_[MAX_NUM_THREADS] = {};

每个线程当然就涉及到haz_local_索引(ID)的分配，就像使用RCU技术实现读写线程无锁中的一样。这个实现为了支持线程动态创建，就需要一套线程ID的重用机制，相对复杂多了。

附录

最后，附上一些并行编程中的一些概念。

Lock Free & Wait Free

常常看到Lock Free和Wait Free的概念，这些概念用于衡量一个系统或者说一段代码的并行级别，并行级别可参考并行编程——并发级别。总之Wait Free是一个比Lock Free更牛逼的级别。

我自己的理解，例如《锁无关的数据结构与Hazard指针》中实现的Hazard Pointer链表就可以说是Lock Free的，注意它在插入新元素到链表头时，因为使用CAS，总免不了一个busy loop，有这个特征的情况下就算是Lock Free，虽然没锁，但某个线程的执行情况也受其他线程的影响。

相对而言，Wait Free则是每个线程的执行都是独立的，例如《锁无关的数据结构与Hazard指针》中的Scan函数。“每个线程的执行时间都不依赖于其它任何线程的行为”

锁无关(Lock-Free)意味着系统中总存在某个线程能够得以继续执行；而等待无关(Wait-Free)则是一个更强的条件，它意味着所有线程都能往下进行。

ABA问题

在实现Lock Free算法的过程中，总是要使用CAS原语的，而CAS就会带来ABA问题。

在进行CAS操作的时候，因为在更改V之前，CAS主要询问“V的值是否仍然为A”，所以在第一次读取V之后以及对V执行CAS操作之前，如果将值从A改为B，然后再改回A，会使基于CAS的算法混乱。在这种情况下，CAS操作会成功。这类问题称为ABA问题。

Wiki Hazard Pointer提到了一个ABA问题的好例子：在一个Lock free的栈实现中，现在要出栈，栈里的元素是[A, B, C]，head指向栈顶，那么就有compare_and_swap(target=&head, newvalue=B, expected=A)。但是在这个操作中，其他线程把AB都出栈，且删除了B，又把A压入栈中，即[A, C]。那么前一个线程的compare_and_swap能够成功，此时head指向了一个已经被删除的B。stackoverflow上也有个例子Real-world examples for ABA in multithreading