文章

安全内存（SMR）回收常用方法

汇总安全内存（SMR）回收中的常用方法与适用场景，作为后续内容扩展的占位文章。

发表于
作者 xzxz
16 分钟阅读
安全内存（SMR）回收常用方法

安全回收常见机制：

  • epoch-based reclamation
  • hazard pointers
  • RCU（Quiescent-State-Based Reclamation？）
  • 引用计数

EBR：

核心思想

通过将时间划分为若干“纪元（epoch）”，线程在进入临界区时声明自己所处的纪元，待回收对象被标记为某一旧纪元后，只有当系统中所有线程都已推进到更新的纪元，才能安全地释放这些对象，从而保证没有线程仍在访问它们。

用 epoch 判断某块内存是否仍可能被访问。

系统维护一个全局递增的 epoch，每个线程在进入临界区时记录自己当前观察到的 epoch。当一个对象被删除时，记录它被删除时的 epoch（记为 retire_epoch）。

只有当：

所有线程都已经离开或进入了比 retire_epoch 更新的 epoch

时，才能安全回收该对象。

实现

每个线程本地维护：

  • local_epoch：线程当前观察到的 epoch（在进入临界区时更新）
  • active：是否处于临界区（是否可能访问共享结构）
  • retire_list[3]：按 epoch 分类的待回收对象

全局共享：

  • global_epoch
  • 所有线程的：
    • local_epoch
    • active
  • 线程注册表（所有可能访问该数据结构的线程集合）

注意，上述提到的每个线程本地维护的虽然是“线程本地变量”，但必须对其他线程可见（通常是原子变量或至少具备可见性保证）

临界区管理

每个线程进入临界区（尝试访问共享的、使用EBR保护的数据结构）前要执行：

1
2
3

thread.active = true
thread.local_epoch = global_epoch
memory_barrier()

表示线程在全局范围内注册 “我可能访问属于当前 epoch 的数据”

线程退出临界区（一轮连续的读操作完成）时执行：

1

thread.active = false

表示 “我不再持有任何旧数据引用”

删除节点（retire）

对受到 EBR 保护的共享数据结构中的节点的删除分为2步：

  1. 逻辑删除：从数据结构中移除节点（例如通过原子修改指针的方式将节点树中摘除，EBR不管如何实现逻辑删除或安全的指针修改，EBR只管内存回收相关的问题）
  2. 延迟回收登记：
    1
2

     node.retire_epoch = global_epoch
 将 node 加入 retire_list[global_epoch]

到目前为止，这个被删除的节点还不能被物理释放。

推进 global_epoch

推进操作可以由任意线程触发（通常是写线程），但需要满足条件：

1
2
3

对于所有线程 T：
    如果 T.active == true 且 T.local_epoch != global_epoch：
        不允许推进

可以理解为严格保证：没有线程仍停留在旧 epoch 的临界区中

推进操作具体做的事：

1

global_epoch = (global_epoch + 1) % 3

 回收节点

始终可以安全回收：

1

retire_list[(global_epoch + 1) % 3]

因为这些节点已经“跨越了两个 epoch”

具体解释EBR里面的“3”：

至少需要 3 个 epoch，才能区分：当前使用、刚删除、可安全回收

假设只有两个线程A和B，有一个共享内存对象X

t1：线程A进入 epoch = 0

1
2

A.local_epoch = 0
A.active = true

t2：线程B删除节点 X

1

X.retire_epoch = 0

此时显然不能回收X，因为 A 可能还在访问 X

t3：线程B离开临界区，并且尝试推进全局epoch。这时线程A状态 active，local_epoch=0; 线程B状态 inactive, local_epoch=0; global_epoch也是0，满足推进全局epoch的条件。线程B可以合法地将global_epoch设置为1。

此时也显然不能回收X，因为A仍然在访问X，A并没有离开临界区！ 必须注意的是，EBR机制里，global epoch能从LastValue推进到LastValue+1并不意味着当前没有活跃的且local epoch等于LastValue的线程存在（建议回顾global epoch的推进条件）。

但是，在线程A退出临界区之前，全局epoch一定不会被递增。因为任何再次尝试递增全局epoch的操作都会发现线程A的状态是active，且持有local_epoch=0，然而线程A的local_epoch 0 不等于当前的全局epoch 1。

什么时候可以回收X? -> global_epoch = 2的时候。

t4: 线程 A 离开临界区，不再访问 X

此时再次尝试推进全局epoch，就会发现线程A和B都inactive，显然可以推进。一旦global_epoch推进到2，就能保证不会有任何active且持有local epoch为0的线程存在了。此时释放X就是安全的。

因此，EBR机制里，global epoch 能从 LastValue 推进到 LastValue+1 意味着当前没有活跃的且local epoch等于 LastValue-1 的任何线程存在

切记：EBR在global epoch=x的时候只能安全释放retire epoch=x-2的对象

hazard pointers

核心思想

在无锁或者细粒度锁数据结构里，每个线程公开声明自己“正在访问的节点”（hazard pointers），从而让其他线程在回收内存前先检查这些声明，确保不会释放仍然在被访问的对象，进而实现安全的内存回收。

具体来说，风险指针的思想可以概括为3步：

第一步：线程在访问某个共享节点前，先把该节点的地址发布到一个所有线程都能看到的位置，这个发布出来的指针就是 hazard pointer

第二步：其他线程删除节点时，不立即free，而是先进入retire list。也就是1、从数据结构中逻辑删除，但不释放物理内存，2、用一个“待回收”的集合维护这些节点

第三部：回收内存时扫描所有线程的风险指针。对于待回收的节点x，如果某个线程的风险指针还指向x，就说明还有线程正在访问它，不能free内存。如果没有任何风险指针指向x，说明没有线程还能合法访问这个节点，可以安全释放。

具体实现：

每个线程有 hazard records（危险指针槽），每个线程有若干个槽位，存放它当前保护的地址。 每个线程还有一个本线程的待回收列表，等列表积累到一定数量，会统一扫描所有线程的风险指针槽位，尝试回收对象。

风险指针与EBR的区别：

EBR的思想是线程主动声明进入某个epoch，删除节点时记录retire epoch,等所有活跃线程都进入更晚的epoch之后再回收。它保护的是某个时间段内可能被访问的所有对象，是按时间区间批量保护对象。

风险指针的思想是线程显式发布”我正在访问地址x“，回收的时候会对逐个地址进行检查，看有没有线程正在访问，它实现的是按对象地址的精确保护。

风险指针的优势是不用等线程整体推进epoch，一个阻塞的线程只会阻塞它显式保护的少数对象，更精确

风险指针的劣势是每次访问贡献节点都要发布/验证风险指针，回收时要扫描说有线程的风险指针槽，实现复杂且开销高。

RCU

RCU(Read-Copy Updata)是一种读写并发协调机制，但同时也提供了一套配合的安全内存回收机制。RCU允许读者几乎不加锁地访问旧版本数据，写者通过”复制/替换“发布新版本，并在确认所有读者离开后，再回收旧版本。

RCU适合的场景：

  • 读多写少
  • 读路径要求低开销
  • 允许读者段时间看到“旧但一致”的版本
  • 数据结构更新可以接受“先造新版本，再替换指针”

RCU包含3部分：

  • 读侧临界区 read-side critical section
    • 读者进入临界区的时候不用加互斥锁
    • 读者读到的是某个时刻可见的对象版本
    • 这个版本在临界区结束前不会被释放
    • 读者获得的是对被读取对象的生命周期安全保证，被读取的对象不一定是最新的，但是一定是“结构一致且不会被释放”的。
  • 更新/发布新版本 copy+publish
    • 写者更新数据时，通常不直接原地破坏读者可能正在读的对象，而是：1、复制旧对象，得到新对象；2、在新对象上修改；3、用一次原子发布，把共享指针从旧对象切换到新对象
    • 所以读者要么看到旧版本，要么看到新版本，但不会看到半更新状态。
  • 宽限期（grace period）后回收旧版本。
    • 宽限期的定义是：从某个时刻开始，等到”所有在那个时刻之前已经进入RCU读侧临界区的读者”都退出的这段时间。一旦一个对象在“被替换/摘除”之后，又经历了一个完整的宽限期，这个对象就可以被安全回收。

系统到底怎样知道一个 grace period 结束了？

大方向类似：

  • 系统记录“哪些线程/CPU 正在 RCU 读侧临界区里”
  • 发起 grace period 时，等待所有“旧读者”退出
  • 当所有旧读者都退出后，grace period 完成 具体实现有多种

以 Linux 内核的RCU为例

内核 RCU 的核心是：

检测每个 CPU/线程是否都经过了一个 quiescent state（静止状态）

所谓 quiescent state，指一个上下文切换点，表示：

在这个点之后，该 CPU 上之前可能执行的 RCU 读侧临界区已经结束了。

典型 quiescent state 包括：

  • 上下文切换
  • 用户态切换
  • idle
  • 某些内核边界

于是 grace period 的判断就变成：

对每个 CPU，只要它都报告自己经历过一个 quiescent state，那么旧的 RCU 读者就都结束了。

这样就避免了对每次读操作都做昂贵跟踪。

RCU和EBR的区别：

EBR 是一种基于 epoch 的安全内存回收方法。RCU 是一种更广义的并发读写协调机制；很多用户态 RCU 的底层实现可以用 EBR 风格的方法来做 grace period 检测，但 RCU 的语义和使用方式比 EBR 更宽。

引用计数

对象只要还有线程“持有引用”，就不能释放；只有当引用计数降到 0，才允许真正回收。

它的出发点非常直观：

  • 不去问“有没有线程正处于某个 epoch”
  • 不去问“有没有线程在 hazard slot 里显式保护这个地址”
  • 而是直接给对象记一本账：

“现在一共有多少活的引用指向我？”

只要账没清零，就不能 free。

db
smr rcu hazard-pointers epoch-based-reclamation memory-reclamation
本文由作者按照 CC BY 4.0 进行授权