介绍 Hazard Pointer。

简介

Hazard Pointer类似于面向多线程的智能指针，它能够无等待地进行线程安全的 GC。在前面提到的 MS 队列中，它的 free 就可以由 HazardPointer 实现。
维护一个全局数组 HP hp[N]，其中 N 表示线程的数量。HP 看上去是 ThreadLocal 的，但实际上不是。因为虽然每个线程只能写自己的 HP，但是却可以读所有其他线程的 HP。
当需要访问某个指针时，就将这个指针赋值给自己的 HP，也就是通知别人不要释放这个指针。这里的释放被称为 reclaim 或者 deallocate，指的是销毁这个对象。
如果同时访问多个指针呢？同样可以扩展HP。比如 HazardPointer 的思维通常是在无锁队列中出现，这个场景最多也就操作一个节点的指针。而如果操作其他数据结构比如树或者图，那么一个线程可以同时访问多个指针。
每个线程维护一个私有链表，称为 retired。当该线程准备释放一个指针时，如果此时这个指针还有 reader，则不能立即 gc 掉这个指针，此时把该指针放入 retired 链表中。被 retire 的指针不再可以被新的 reader 访问了，但它仍旧可以被之前就已经指向了的 reader 访问。
当一个线程要释放某个指针时，它需要检查全局的 HP 数组。如果有一个线程的 HP 指向这个指针，则不能释放。

Why Hazard Pointer

HP 是用来实现安全地释放某个指针的。这里的安全指的是当有 reader 在读的时候，不能立即销毁该指针指向的对象。例如考虑一个线程在遍历链表，另一个线程在移除链表中的某些节点，这两个线程是不互相知晓对方的。如果在删除时，读线程已经持有了访问该节点的指针，那么这个节点就不能被立即删除。诸如此类的场景称为 Deferred Reclamation。

一些做法可以解决该问题，比如引用计数。例如可以分别维护读引用计数和写引用计数，这样当一个写在发生前，总可以先检查两个引用计数是否都是0。它的缺点是，无论是读还是写，都需要访问一个共享的用来计数的结构。也许这个结构可以借助于原子操作实现得“轻量”，但无论如何，竞争访问(contention)是少不了的。但考虑一个读多写少的场景，也就是大部分时候压根就不会写那个借助引用计数维护的对象，无论它是一个链表节点，或者是一个别的什么。那是否可以让读操作避免去访问共享对象，从而减少竞争呢？这就是 Hazard Pointer 的思想。这样各个读操作之间没有竞争。

除了 hazard pointer，还有诸如 epoch-based 或者 RCU 的做法来解决问题。

实现

本章节中会进一步研究 hp 实现的原理，并基于 folly 的实现给出一份 Rust 的实现。

基本原理

如下所示，蓝色的是读线程，紫色的是写线程。reader 在读 hp 指向的那个 x，而 writer 通过 cas 来把 x 替换成 y。每个 reader，都持有一个 harzard pointer。这里面的东西，要么是空的，要么是当前线程正在使用的 pointer。writer 会检查所有的 hp，检查里面是否包含了自己要 gc 的地址。如果有，说明现在还有 reader 访问，writer 就会 yield 掉，做一些其他的事情，等过一段时间再检查 hazard pointer。等到没有 reader 访问这个 old value 了，writer 就会销毁掉它。

对于每个对象，它所有的 reader 组成一个链表。如何保证 hp 链表的线程安全？我们不会在使用完某个 hp 后就释放它，而是通过 cas 将它设置为空。所以这些链表中的 hp 是可以被复用的。所以，在获取 hp 的时候，是有一些竞争的，但相比新分配一个 hp，或者 cas 整个链表会好很多。

这里还讲了 wait free 的实现依赖于 memory reclamation，而不是反过来。所以无法利用某种 wait free 的算法来实现 hp。

epoch 的方式更 batch 一些，也更消耗内存。因为只有在 epoch 结束之后，才能释放这个 epoch 中的所有对象。

reader 如何访问 x 呢？ reader 设置 hp，然后后面的 writer 在释放 old value 前进行检查会看到有 hp 被设置了，从而推迟销毁。
但这个方案是存在问题的，问题的实质是 hp 和 hp 保护的 ptr 的读写不是原子的。所以考虑下面的顺序，可以发现 W 在还有 R 读 old value 的时候就把 old value 销毁了，这显然是不安全的

R 读 ptr
W 更新 ptr
W 检查 hp
W 销毁 old value
R 更新 hp

这里有个疑问，如果先更新 hp，再读取 ptr 是否可行呢？这是不可行的，因为 hp 里面要填入它保护的 ptr，所以必须先取到 ptr。

因此设计下面的过程：

R 读 ptr，读到值为 ptr1。
R 更新 hp。
R 再读 ptr，确保此时读到的值还是 ptr1，此时视为 R 可以安全读 ptr 的值。否则 R 就需要加载最新的 ptr，然后重复这个过程。
W 更新 ptr。
W 检查 hp。

这样的话，如果在 2 和 3 之间有一个 writer 进行了 CAS，那么它会导致 3 读出来的 ptr 发生变化，这样 reader 就能重试。如果在 3 之后有一个 writer，那么 writer 在看到 hp 之后就会重试。

folly 的接口

本章节中，研究 folly 的接口，并尝试用 Rust 来实现一份接口。

一个类继承 hazptr_obj_base 才可以被用 hp 维护。这个 hazptr_obj_base 中有一个 retire 方法。为什么要这么做呢？其实大可以把 MyType 用 HazPtrTarget 包一层，但这样就多了一层间接，用起来不方便。就是想把 HazPtrTarget 里面的一些功能 trait 出来，让 MyType 实现。这样的话，就不需要外面包一层了。当然，后面会发现因为 Rust 中不能往 trait 里面放比如 hazptrs: LinkedList<HazPtrHolder> 之类的 field，所以作者还是包了一层。

1 2	AtomicPtr<MyType> AtomicPtr<HazPtrTarget<MyType>>

一个 retire 的对象，不再 accessible，但仍然被 hp 保护。在 reclaim 阶段，会检查该对象是否可以被删除。

另外，为什么提供一个显式的 retire 函数，而不直接在析构的时候做 retire 相关的事情。作者觉得这是一个 taste 的问题，drop(*) 有点奇怪的。

1
2
3

let old: *mut HazPtrTarget<MyType> = x.swap(new);
HazPtrTarget::retire(old); // 1
drop(*old); // 2

在访问需要保护的对象前，需要首先创建一个 hazptr_holder。holder 是 reader 实际操作的对象。holder 会检查自己是否拥有 hp，如果没有的话，会从对应的 domain 去 acquire 一个。
holder 的方法 get_protected 接受一个 AtomicPtr<T>，也就是需要保护的对象。它返回一个不可变引用，这个引用是被 hp 保护的了。

1
2
3

impl HazPtrHolder {
    fn get_protected<'a, T>(&'a mut self, &'_ AtomicPtr<T>) -> &'a T;
}

首先，无所谓这个 AtomicPtr<T> 的生命周期，因为实际是为了拿到它维护的指针。【Q】那为什么要这个 AtomicPtr 保护一下呢？这和之前说的要读两次 ptr 有关，也就是需要原子地从 ptr 上 load 出它当前的值。
其次，即使返回 &T，我们依旧需要 &mut self。这是为了避免先 get_protected a 之后又 get_protected b，这样 a 实际上就不被保护了。
最后，返回的 &T 的生命周期是和 HazPtrHolder 一致的。

如图所示，retire(x) 调用时，发现 x 还在被访问，不能直接 reclaim，所以记录到 retire 表中。retire(y) 调用的时候，发现 y 在被访问，但 x 已经不再被访问了，所以 reclaim x，然后把 y 记录在表中。

演讲者认为 folly 的 demo 存在一些疏漏。如果 V 是一个引用类型的话，则可能出现问题。

///   // Called frequently
///   U get_config(V v) {
///     hazptr_holder h = make_hazard_pointer();
///     Config* ptr = h.protect(config_);
///     /* safe to access *ptr as long as it is protected by h */
///     return ptr->get_config(v);
///     /* h dtor resets and releases the owned hazard pointer,
///        *ptr will be no longer protected by this hazard pointer */
///   }

下图列出 haz holder、haz pointer、atomic 和 haz obj 的关系。
看起来 holder 是 reader 实际操作的对象。holder 会检查自己是否拥有 hp，如果没有的话，会从对应的 domain 去 acquire 一个。

这里 non-typical 的是比如去 dfs 遍历一棵树，然后对于树的每一层都有一个 hp 来记录。这样的话，每个线程的 hp 的数量是 log(d) 而不是常数。
第二段的意思是，retire 但还没有 reclaim 的 haz ptr 的数量，和 hp 的数量是线性的。

/// Memory Usage
/// ------------
/// - The size of the metadata for the hazptr library is linear in the
///   number of threads using hazard pointers, assuming a constant
///   number of hazard pointers per thread, which is typical.
/// - The typical number of reclaimable but not yet reclaimed of
///   objects is linear in the number of hazard pointers, which
///   typically is linear in the number of threads using hazard
///   pointers.

下面的 Rust 代码展示了 hp 的大概使用方法。这里的 HazPtrHolder::load 类似于 get_protected。可以看到，当 HazPtrHolder 被析构后，就不再可以使用 my_x 了。

#[test]
fn feels_good() {
    let x = AtomicPtr::new(Box::into_raw(Box::new(42))); // x: AtomicPtr<i32>
    // As a reader:
    let h = HazPtrHolder::default();
    let my_x: &i32 = h.load(&x);
    drop(h);
    // invalid:
    let _ = *my_x;
    // As a writer:
    let old = x.swap(
        Box::into_raw(Box::new(9001)),
        Ordering::SeqCst,
    );
    HazPtrobject::retire(old);
}

上面的代码也有几个不尽如人意的地方：

首先是 AtomicPtr 可能接受一个 null，但我们的场景中实际要禁止 null。显然 Rust 中缺少一个 NotNullAtomicPtr 的结构。

下面就是 load 的实现。分为两部分：

尝试获得一个 hp，如果当前的 holder 尚未绑定一个 hp，就从 domain 上 acquire 一个。acquire 的实现类似从链表里面取一个可用节点，这在后面介绍。
从 AtomicPtr 中加载 ptr，放到刚才获得的 hp 里面，也就是 protect 方法。然后再从 ptr 中读一遍，确保现在读到的 ptr2 等于之前的 ptr1。

这里能够在 ptr1 == ptr2 的时候返回 ptr1，其安全性在于：

ptr1 不可能被释放，因为它此时至少受到我们刚创建的 hp 的保护。
caller 保证 AtomicPtr 非空，并且只可能通过 retire 来被释放掉。

pub unsafe fn load<T>(&mut self, ptr: &'_ AtomicPtr<T>) -> Option<&T>
{
    let hazptr = if let Some(hazptr) = self.0 {
        hazptr
    } else {
        let hazptr = SHARED_DOMAIN.acquire();
        self.0 = Some(hazptr);
        hazptr
    };
    let mut ptr1 = ptr.load(Ordering::SeqCst);
    loop {
        hazptr.protect(ptr1);
        let ptr2 = ptr.load(Ordering::SeqCst);
        if ptr1 == ptr2 {
            // All good -- protected
            break Some(todo!())
        } else {
            ptr1 = ptr2;
        }
    }
}

后面卡在 impl<T> HazPtrObject for T 的 domain 方法上了。这个 domain 方法要返回一个 HazPtrDomain，但写不下去了。因为无法从 trait HazPtrObject 或者任一类型 T 中去取到它被绑定的 domain。所以我们得引入一个 HazPtrObjectWrapper<T> 来保存 domain。这个 Wrapper 可以解引用为 T，还实现了 HazPtrObject。哎，所以这不是走回 AtomicPtr<HazPtrTarget<MyType>> 这样的老路了么。

这里遇到一个 Drop 相关的问题，他要把 self cast 成一个 *mut dyn Drop，这要求 HazPtrObject 的 Self 必须 impl Drop。但 Rust 又报一个 warning 说 HazPtrObject 继承一个 Drop trait 是多余的。搞到最后作者也没办法去掉这 warning，只能通过 drop_bounds 去禁用掉这个 warning。在视频的第二部分，通过用一个新的空的 trait Reclaim 替换 Drop 来解决掉那个多的 warning。毕竟我们核心只是要一个虚表。

#[allow(drop_bounds)]
pub trait HazPtrObject
where
    Self: Sized + Drop + 'static,
{
    fn domain(&self) -> &HazPtrDomain;

    unsafe fn retire(self: *mut Self) {
        if !std::mem::needs_drop::<Self>() {
            return;
        }
        unsafe { &*self }.domain().retire(self as *mut dyn Drop);
    }
}

后续引入一个 trait Deleter，给到 retire 函数，用来指定如何删除这个对象。

然后说了下，测试里面的 swap 之后，还需要 retire 才能语义上保证 old 不会再 accessible 了。borrow checker 保证了，在调用 reset 的时候，不可能持有一个 load 得到的 &T 指针。这是因为 load 和 reset 都需要 mut borrow。

下面实现 HazPtrDomain::acquire。我们遍历 domain 维护的整个链表，找到第一个 active 为 false 的节点并返回。注意 active 为 true 表示这个 node 正在被使用。如果遍历完整个链表都找不到，则需要扩容链表。这里的链表扩容挺符合直觉的，是一个经典的 loop cas，每次都想办法更新 head。如果 cas 失败，说明 head 已经被其他线程更新了，就重试一次。但是重试前要更新自己的 next 为新的 head。

bulk_reclaim 尝试 reclaim 掉所有可以被 gc 的对象。这里说一下，一个对象 retire 之后，就会从 hp 链表中被删掉，然后放到 retire 链表里。如果是这样的话，又在放到 retire 链表之前线程崩了，那么这个对象是不是泄露了？其实 retire 只会设置 hp 的 active 为 false。

如果此时 retire 被某个线程拿过去回收了，所以 retire 是 nullptr，然后又有一个新的节点要加到 retire 上，会不会导致出现两个 retire 链表？关于这个问题，看后面的实现就可以知道不会发生。他的做法并不是 swap 两个链表，而是在处理完老 retire 的 tail 后，将它的 next 设置为新 retired 链表的 head，然后再尝试更新 retire 为老 retire 的 head。结果就是

1	\| 老 retire 中尚未释放的链表的 head \| 新 retire 的 head \|

如何判断 retire 链表中的元素是可以被安全删除的呢？这里会遍历 hazptrs 链表，将遍历得到的指针全记录在 guarded_ptrs 中。我想其中一个要点是，如果一个指针被 retire 了：

那么它就不会再出现在 hazptrs 链表中，因为它不可能被新的线程所访问。
因为它还没有被 reclaim，所以也不会在 hazptrs 中出现分配在同一个位置上的另一个对象。

后面是对 Deleter 的实现。Deleter 是负责真正 reclaim 这个 ptr 的。Deleter 的作用是标记到底要 delete 什么对象。这个是通过 trait 里面的 vtable 来实现的。
第一版是这个写法。DropBox 适合用来析构从 Box 创建的对象。而 drop_in_place 应该可以在任何情况下被使用。但如果这个 ptr type 本身需要 drop 的话，可能会内存泄露。所以作者两种都提供了。

pub struct DropInPlace;
impl Deleter for DropInPlace {
    fn delete(ptr: *mut dyn Drop) {
        unsafe std::ptr::drop_in_place(ptr);
    }
}
pub struct DropBox;
impl Deleter for DropBox {
    fn delete(ptr: *mut dyn Drop) {
        let _ = Box::from_raw(ptr);
    }
}

然后可能是他觉得用一个类包一下有点丑，所以就写了下面的方案。但这样写会报错，说后面那个 fn 没有 impl Deleter。

impl Deleter for fn(*mut (dyn Drop +'static)) {
    fn delete(&self, ptr:*mut dyn Drop) {
        (*self)(ptr)
    }
}

这里的原因是，需要传一个 fat pointer，一个带虚表的 pointer 给 retire，但一个 raw function 不是 fat pointer。

下面的代码是可以过的

fn drop_box(ptr:*mut dyn Drop) {
    let _ = unsafe { Box::from_raw(ptr) };
}
static FOO: fn(*mut dyn Drop) = drop_box;

unsafe { old.retire(&FOO) };

另外，类型转换也能过

fn drop_in_place(ptr: *mut dyn Drop) {
    unsafe { std::ptr::drop_in_place(ptr) };
}

unsafe { old.retire(&(drop_in_place as fn(*mut dyn Drop))) };

在这个讲座的第二部分，介绍了原代码的几个问题：

在 reclaim 统计 ptr 数量的时候，需要过滤掉 inactive 的。这个也说明了 active 的作用，就是当一个 hp 被 retire 之后，它会被标记为 inactive，等待下一轮被拿出来复用，而不是从链表中摘出来释放掉。
在之前 HazPtrObject::reclaim 的实现中，也许 Self 不需要被 drop。但 *mut Self 可能来自于一个 Box，这个 Box 本身需要被 drop。因此不能简单判断 needs_drop 然后就跳过。
在 HazPtrDomain::bulk_reclaim 中，在没有判断 guarded_ptrs.contains(&(n.ptr as *mut u8)) 的前提下，就在前面 Box::from_raw 去获取所有权了。这个是不正确的，因为此时可能有 reader 在访问。
正确的做法应该如下所示，去获取 n 也就是解出来的一个共享的引用。
1
2
let n = unsafe { &*node };
node = n.next.get_mut():

Reference

https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2021/p1121r3.pdf
https://github.com/jonhoo/haphazard/blob/7f0d8d62e071f8bc55233a3d2437225d6282e368/src/lib.rs
Rust HazPtr 作者的第一部视频结束后的代码。