compare-and-swap · ABA · tagged pointer

CAS 与 ABA

无锁结构的全部同步都压在一条硬件指令上。它读一个字，比对期望值，相同就写入新值，整个过程对其他核不可分割。x86 的 lock cmpxchg、ARM 的 ldxr 与 stxr 配对、RISC-V 的 lr 与 sc 配对，形态不同而效果相同。

1 · compare-and-swap 的语义

compare-and-swap 接三个参数：地址、期望值、新值。当且仅当该地址当前的内容等于期望值时写入新值并返回成功，否则不写并返回失败。伪代码写出来只有三行，关键是这三行整体原子：

CAS(addr, expect, desired)：若 *addr == expect 则 *addr = desired 并返回 true，否则返回 false

Herlihy 1991 证明了 CAS 的 consensus number 是无穷，意思是任意多个线程可以用它达成一致，从而任何顺序对象都能被改写成 wait-free 的并发版本。test-and-set 的 consensus number 只有 2，读写寄存器只有 1。这条结论解释了为什么现代无锁结构清一色建在 CAS 上，而不是更简单的原语上。

2 · 缝隙与它的修补

不用 CAS 的自增分两步：x = load(c) 与 store(c, x + 1)。两步之间有一道缝隙，另一个线程可以整个挤进去。

图 2-1 · 两个线程各做一次自增的全部交错，上方可手动选择下一步走谁。可勾选换成 CAS 版本，对照六条交错的终值分布。

两线程各两步，交错共 6 条。普通 store 版本里有 4 条终值为 1：两个线程都在缝隙里读到 0，各自写回 1，一次自增被吞掉。CAS 版本的 6 条交错终值全为 2——晚到的那个线程发现 c 已不是它读到的 0，换不成，退回去重读再来。

代价是重试。失败一次多走两步，正确性判据与进展保证 §4 量过：两线程下单个线程最坏 4 步，三线程下最坏 6 步。步数随线程数增长而在有限操作下有界，这个形状就是 lock-free。

3 · ABA

CAS 比对的是值，而无锁结构真正关心的是期间有没有发生变化。多数时候两者一致，指针类型上则不然：一个地址被释放后又被分配给新对象，指针的位模式可以一模一样。

设栈自顶向下是 A、B、C，某线程执行 pop 时读到 t = A、nx = B，随后被抢占。期间另一个线程弹出 A、弹出 B，又把 A 压回去，此时栈是 A、C。第一个线程恢复，CAS(Top, A, B) 看到 Top 仍是 A，换成功——Top 指向了已被弹出并释放的 B。这就是 ABA。

图 3-1 · Treiber 栈上的 ABA 单步复现。左右两栏是两个线程的程序计数器与局部变量，中间是共享内存与节点堆，下方是已走过的交错。可一键复现那条 11 步的经典交错，也可勾选版本号观察 CAS 被拦下。

引擎里复现它需要一个细节：free list 必须按 FIFO 取用。改成 LIFO 的话，先释放 A 再释放 B，下一次分配拿到的是 B 而不是 A，Top 就回不到 A，整条经典序列走不出来。多数真实分配器的行为接近 FIFO，模型照它取。

那条 11 步的交错逐字如下，T2 的三个操作全部夹在 T1 一次 pop 的两条指令之间：

0  T1: t = load(Top) → n3
1  T1: nx = load(n3.next) → n2
2  T2: t = load(Top) → n3
3  T2: nx = load(n3.next) → n2
4  T2: CAS(Top, n3, n2) → 成功, 取出 10
5  T2: t = load(Top) → n2
6  T2: nx = load(n2.next) → n1
7  T2: CAS(Top, n2, n1) → 成功, 取出 20
8  T2: n = alloc(40) → n3(复用), t = load(Top) → n1
9  T2: CAS(Top, n1, n3) → 成功
10 T1: CAS(Top, n3, n2) → 成功, 取出 40

第 10 步之后栈的内容是 20、30：已经被取走的 20 又回来了，而 n2 处在已释放状态。穷举这个场景的全部 3945 条交错，18 条不可线性化，占千分之五。罕见是这类缺陷难查的原因，也是「跑十万次没出问题」不能当作证据的原因。

4 · 版本号与延迟回收

第一类对策是让「值相同」不再等于「没变过」。把指针与一个单调递增的 tag 打包进同一个字，CAS 比对整字，每次成功换值时 tag 加一。这就是 tagged pointer，x86-64 的 lock cmpxchg16b 可以一次比对交换 128 位，正是为它准备的；指针高位空闲的平台也可以把 tag 塞进高 16 位。

同一场景加上 tag，3945 条交错的不可线性化数从 18 降到 0。第 10 步的 CAS 此时看到的期望值是 n3#0，而 Top 已是 n3#3，整字不同，失败重来。

警示 · tag 治的是 CAS 认错，不是内存安全。同样这 3945 条交错里，有 2577 条至少读过一次已释放的节点，加不加 tag 这个数字完全不变——CAS 失败之前，load(n3.next) 已经读过那块内存了。带 GC 的语言看不到这一层，C++ 里它是一次真实的 use-after-free。第二类对策必须解决的就是它，见 Treiber 栈与内存回收。

第二类对策是延迟回收：让节点在「可能还有人正在读」的期间不被交还给分配器。地址不被复用，ABA 就无从谈起，use-after-free 也一并消失。hazard pointer 与 epoch-based reclamation 都属于这一类，代价与取舍是另一页的题目。

注 · 本页的检查器一开始只比对返回值，结果是 ABA 场景全绿。原因在于那 18 条反例的返回值全都合法：T1 弹出的 40 确实是 T2 压进去的，逐个操作看没有任何破绽，烂掉的是残留在栈里的东西。补上「顺序解释跑完的状态要与结构实际内容对上」这条收尾断言之后，18 条才现形。返回值比对与状态比对缺一不可，这一点在 Herlihy 与 Wing 的定义里本来就有，是实现时容易省掉的那一半。

5 · 参考文献

Herlihy, M. (1991). Wait-free synchronization. ACM Transactions on Programming Languages and Systems, 13(1), 124–149. consensus number 的层级出自此文。
IBM. (1983). IBM System/370 Extended Architecture, Principles of Operation. compare-and-swap 的最早规范化描述，含用 tag 计数对付 ABA 的建议。
Michael, M. M. (2004). Hazard pointers: safe memory reclamation for lock-free objects. IEEE Transactions on Parallel and Distributed Systems, 15(6), 491–504.
Dechev, D., Pirkelbauer, P., & Stroustrup, B. (2010). Understanding and effectively preventing the ABA problem in descriptor-based lock-free designs. 13th IEEE International Symposium on Object/Component/Service-Oriented Real-Time Distributed Computing, 185–192.