https://youtu.be/lNPZV9Iqo3U?si=lS1hf2ND4SS-6ELB by Daniel Anderson

幻灯片链接： https://raw.githubusercontent.com/CppCon/CppCon2023/main/Presentations/lock_free_atomic_shared_ptr_cppcon2023.pptx

共享指针是线程安全的吗？

std::shared_ptr 的控制块是线程安全的（其实也就是析构是线程安全的， https://en.cppreference.com/w/cpp/memory/shared_ptr/atomic2 中有 “Note that the control block of a shared_ptr is thread-safe…” 这句话），但是：

1. 对它指向的对象的访问不是线程安全的。
2. 对它本身的读写不是线程安全的。

这个 lecture 主要考虑第 2 点。

Daniel 提到了一种情况：如果一个共享指针正在被析构导致引用计数归零（比如给某个共享指针赋值为一个另一对象的共享指针），此时另外一个线程正复制这个共享指针，则可能会出现内存安全问题。这其实是在两个线程中未做保护地对同一个共享指针读写。大多数情况下，我们可以在线程创建的时候将共享指针拷贝给另外一个线程，避免使用同一个实例。

为什么有时候希望共享指针本身也能线程安全？

有些时候我们仍然希望多个线程访问同一个共享指针，而不是共享指针的多份拷贝。明明只要跨线程正确复制共享指针就能保证共享指针内存管理的安全性，为什么还非要使用共享指针的同一个引用呢？在无锁编程中，有一个常见场景是用原子操作和链表实现一个无锁的队列 / 栈。这时，多个消费者（以及生产者）就可能会访问相同的链表结点（比如 head）。此时，我们需要能安全地修改指针本身的值。要注意的是：共享指针只是内存管理手段，并不是 lock-free 手段。

下面是 Daniel 给出的一种无锁栈的一种错误实现，他指出问题是：std::atomic<std::shared_ptr<T>> 这个类型并不是 lock-free 的。

标准库中对共享指针的原子操作支持

参考 libstdc++ 对共享指针原子操作的支持 这一篇笔记 👀。

为什么原子共享指针很难实现为无锁？

将共享指针拷贝出来需要将其控制块计数加 1，将新的共享指针存储进去需要将旧共享指针的控制块减 1。假设出现了如图所示的情况就会有 use-after-free。为此需要让 load / store 的过程都成为原子的，即同时加载控制块指针和修改引用计数，但是引用计数在控制块里面，两者并不独立，因此无锁实现很困难。

方案 1：The split reference count

如果想要在多个线程都可能引用同样的共享指针的情况下安全地给共享指针赋值，就得给共享指针再加一层原子操作。

首先容易想到、但是不能使用的是 std::atomic<std::shared_ptr<T>>，因为这个类型不是无锁的，有造成阻塞的可能。上一节已经说过了。

然后可以考虑把控制块（control block）的指针和另外一个原子计数变量（记录 load count）合并在一起，形成新的计数控制块（counted control block），再把这个变量放在原子变量中。这个方法叫 split reference count。外部计数即这里的本地计数（这个 speech 中的说法和 C++ 并发实战中的内 / 外计数有差异），外部计数和内部计数的总和才是真正的引用数。

这个实现支持了 load() 和 store() 两个操作。给的代码是伪代码。我感觉他这里的实现像是将对象指针放在了 control_block 里面。

load() 操作：访问 load() 出来的控制块不安全，所以要先增加外部计数，由外部计数来保护内部的控制块。一旦通过 CAS 将外部计数增加后，就可以安全增加内部计数并构建返回值。最后应该减去一个刚刚增加的外部计数，但是也可能遇到控制块变化的情况，这里的处理留到 store() 操作再说明。

store() 操作：如果直接减少内部计数的话，那么可能会出现计数归零，然后控制块被回收，load() 就不能安全访问控制块了。因此需要先把外部计数加到内部计数上来再减少内部计数（因为旧控制块已经被换出来了，所以外部计数在加到内部计数上之后就被舍弃了，没必要将其置为 0）。如果其他线程正在使用这个控制块，那么这里减少计数之后计数不可能归零，因而控制块不被回收；如果其他线程没读到这个控制块，因为 exchange 操作放了一个新的控制块进去，其他线程不可能再读到旧的控制块了。

load() 操作中减少内部计数：如果在修改外部计数时发现控制块改变了，这说明有 store() 操作在中途发生，本线程刚进来时往外部计数上加的 1 个被 store() 操作加到内部计数上去了。因此，本线程应该去把旧控制块的内部计数减 1。

这依赖了硬件对 16 字节原子操作的支持（大多数情况下能支持），还有一种替代方式是使用 48 位指针和 16 位计数共用 8 字节空间来保证原子操作的支持（Folly 就是这样做的）。

方案 2：Hazard pointer（风险指针）和共享指针结合

然后 lecture 的重点是介绍 hazard pointer。Hazard pointer 有一点垃圾回收的性质，它将内存的回收延后以使得内存访问安全。Daniel 将 std::shared_ptr 和 hazard pointer 结合起来实现了原子的共享指针。要理解为什么可以这么做，就要理解方案 1 的 split reference count 中增减 load count 的本质是延迟回收。

回顾刚刚的问题：

用 hazard pointer 就能实现延迟回收。

左边代码错误的原因：hazard pointer 只保护了控制块不被释放，但是没有保护控制块里面的计数不归零。如果控制块计数归零，对象指针仍会被清理，而之后对控制块计数加 1 会导致对象诈尸：控制块仍然有效，但是保护的指针成为了野指针。方案 1 没有出现这个问题，是因为它通过增加引用计数连同控制块和内部对象一起保护了 ¹。

Daniel 用不同的原子共享指针实现无锁栈并给出了 benchmark 的结果，展示了自己的实现性能更优。

补充：介绍风险指针

使用 hazard pointer 保护对象时，不是靠控制块引用计数归零时删掉对象，而是使用 retire() 方法将指针加入到 retiring 单向链表中，随后适时调用 reclaim() 来清理不再使用的指针。相关实现：Folly 库有 hazard pointer 的实现，C++26 有头文件 <hazard_pointer>。还可以参考 https://sf-zhou.github.io/programming/hazard_pointer.html 的讲解。

这篇讲解也很有用： http://blog.kongfy.com/2017/02/hazard-pointer/ 。概括来说：

1. 每个线程都有局部的保护指针列表（正在使用、不希望其他线程删除）和退休指针列表（此线程不再需要了）。
2. 使用者想要安全使用指针，首先要用 hazard pointer 去保护装着指针的原子变量以获得裸指针值。保护完成之后再次检查原子变量装的是不是之前保护的指针，如果还是就说明保护成功，可以安全访问指针指向对象的内存。这就有点像持有了 std::weak_ptr，先尝试获取 std::shared_ptr，成功了再继续操作。2025 年 1 月 23 日：实际上是告知其他线程这个指针正在被使用，不能清理。
3. 删除者认为指针不再被需要时，将指针放在自己的退休列表中。之后以某种方式去检查退休列表中想要删除的指针是否在任意一个线程的受保护指针列表中，如果都不在就可以删除这个指针。2025 年 1 月 23 日：C++ 并发实战中是先立即检查指针是否可删除，但是也提出来一些优化手段，比如当队列长度达到 2*num_threads 的时候再去尝试回收，这样可以保证至少可以回收 num_threads 个指针。

共享指针需要在指针传递时反复修改原子引用计数，以计数值来判断指针是否被需要。Hazard pointer（风险指针）模型通过显式地调用 protect() 方法来告知协作者指针还被需要、不能被回收，使用者若有意回收也需要显式调用 retire()。

阅读代码

Daniel 在实现无锁栈时需要用 CAS，但是在 speech 中没有展示 CAS 的实现，这部分代码需要去 他分享的代码仓库 查看。这份代码重新实现了共享指针，并实现了与其配套的原子共享指针。

这个实现里，共享指针包含的裸指针用虚函数 get_ptr() 获取，这是简化实现的关键点。该代码为 get_ptr() 提供了两种实现： 将对象直接嵌入控制块（原地存放）或 将对象指针嵌入控制块，分别对应了 std::make_shared 和 shared_ptr::shared_ptr。设计虚函数 get_ptr() 的好处：

4. CAS 只需要考虑对一个原子控制块的指针做原子化的访问控制，用 std::atomic<T*> 即可，不需要硬件的 CX16 支持。
5. 只要拿到控制块就能拿到共享指针的全部信息，不需要再去获取对象指针。

为了保证解引用的高效，和 std::shared_ptr 一样，Daniel 的实现也是胖指针。尽管能通过控制块访问内部对象，parlay::smart_ptr_base（共享指针的基类）中仍有控制块指针和对象指针两部分。

思考

原子共享指针固然是好的抽象（用户无需关心内存的回收），使得很多无锁算法的实现变得简单，但是能直接用 hazard pointer 的地方（比如无锁栈 / 队列）套一层原子共享指针会不会降低效率？有没有什么原子共享指针能做到但是冒险指针做不到的事情？