作者 | 施继成
转自《Rust Magazine 中文精选》
上次的文章介绍了无锁数据结构的内存管理机制 EBR,该机制相较于其余的内存管理机制具备更高的执行效率。然而因为理念的复杂性,EBR 的实现并不容易,为每一个无锁数据结构从头实现 EBR 也无必要,因而很天然得大家会思考将 EBR 的核心理念 epoch 抽取进去变成库,让大家可能复用。Crossbeam-epoch 是一套成熟的被大家宽泛应用的 EBR 库,本文将从实现原理局部进行较为具体的解析,并且在此过程中进行。
Guard 只是最外层的壳
如前文所述,大家个别在和 Crossbeam-epoch 进行交互时仅仅应用 guard,如下所示:
/// delete data
{let guard = epoch::pin();
guard.defer(move || mem.release());
}
/// get data for reading
{let guard = epoch::pin();
let value = map.get(&key, &guard);
/// ... Use the value
}
在读取数据的时候,guard 表演的角色仅仅是生命周期守护者,其确保获取进去的 data 援用(上述代码中的 value)生命周期肯定不长于 guard,当 guard 被销毁时,value 也肯定被销毁。删除数据过程中,guard 表演的角色要更简单一些,其负责将销毁函数注册到 defer 提早执行的队列中。至于该销毁函数何时被调用,则须要进一步深刻理解其外部实现细节。
Pin 到底做了什么
epoch::pin() 到底做了什么,官网的代码正文中给出了解释,行将以后的 thread pin 住,以便将堆上数据的指针放到栈上。该解释其实只解释了上述读取数据本分的内容,其底层执行的操作如下:
- 将以后线程注册到 Global 收集器,该注册过程每个线程仅仅做一次。
- 获取以后全局 Epoch 并设置到以后线程,示意在 pin 无效的这段时间,以后线程属于哪个 Epoch。
- 记录以后线程曾经被 pin 的次数,当次数达到肯定数量,尝试让 Global 收集器推动 Epoch 增长,回收垃圾。
- 减少 guard_count 计数,记录有多少 guard 被创立进去且还没有被销毁。
因为 pin() 能够重复调用,所以间断两次调用 epoch::pin() 也被容许。只是除了第一次调用,其余的调用都不会有任何作用,仅仅减少了 guard_count 计数。具体实现参见 internal.rs 文件中 Local struct 的 pin 办法。
这里提及的 Global 收集器负责所有资源的回收工作,其从各个线程收集须要回收的垃圾,并在适当的机会进行回收。
Epoch 推动
Epoch Number 须要不停向前迭代,在迭代的过程中,垃圾回收器将附属与老的 Epoch Number 的可回收垃圾回收掉。每次 Global 收集器想要回收垃圾时都会尝试推动 Epoch Number,满足下列条件则 Epoch Number 向前推动胜利:
- 所有注册的线程都处于以后的 Epoch,即不存在线程处于上一个 Epoch。
如果条件不满足则 Epoch 推动失败。具体实现请参见 internal.rs 文件中 Global struct 的 try_advance 办法。
垃圾回收机制
如果所有的线程都将待回收的垃圾注册到 Global 收集器,那么会呈现十分微小的竞争关系,线程越多操作越频繁则性能影响越大。为了解决共享数据结构造成的竞争,每个线程都会保护本人的垃圾回收队列,队列长度为 62(神奇的 magic number,猜想和 CPU cache line 相干)。当队列被装满时,线程会将本地的队列中的数据对立挪动到到 Global 收集器,放到收集器的垃圾链表当中。这里值得注意的是,放入链表的除了垃圾回收函数,还有该垃圾产生的 Epoch Number,该数字被用于决定是否能够回收对应的垃圾。
垃圾回收的触发点有两个,一个被动一个被动。被动的触发点为 Guard 的 flush 办法,调用该办法则会使得 Global 收集器尝试收集垃圾链表中的垃圾。被动的触发点为 Guard 的 pin 办法,即 pin 每被调用 128 次会触发一次垃圾回收。
满足下列条件的垃圾能够被回收:
- (Global Epoch Number) > ((Garbage Epoch Number) + 1),即垃圾对应的 Epoch 至多比以后 Epoch 早两个世代。
具体实现请参见 internal.rs 文件中 Global struct 的 collect 办法。
外部数据结构
其外部数据结构值得一提有两个,一个 List,一个 Queue。List 被用于治理注册的线程,Queue 被用于治理期待被回收的垃圾。这两个数据结构的共同点是被多个线程同时操作,为了高效的实现,crossbeam 没有应用 Lock 来爱护数据结构,而是实现了外部的无锁数据结构。
List
List 有新元素插入方法,插入的办法就是将新元素插入到 List 的 head 地位,实现中应用了 CAS 原子操作。在多线程同时进行插入时,同一时间只有一个可能胜利,失败的操作会取得新的 header 值进行再次尝试。
List 删除操作并不真正移除元素,而是在该元素上进行标记,最初在某次 Iteration 过程中被真正删除,该删除操作也应用了 CAS 原子操作。如果有多个线程在尝试删除同一个元素,只有一个可能胜利。如果在删除某个元素时发现其前一个元素也被标记为可被删除,则告诉 Iteration 调用方须要重头再遍历一次。当然调用方能够依据状况重头遍历,还是留给其他人来解决。
具体实现请参见 list.rs 文件。
Queue
Queue 的插入和 List 相似,区别在于插入点为 tail。Queue 的删除操作叫做 pop,从 Queue 的 head 开始弹出数据,如果弹出数据出错则阐明有其余线程也在进行弹出操作,那么须要从新应用获取 head 的地位再次尝试。
那些从 List 和 Queue 中删除的元素如何解决呢?crossbeam 采纳了自举的办法,即也放入垃圾回收队列中,期待之后的某次操作触发垃圾回收。
总结
Crossbeam-epoch 给大家提供了一个极其不便的工具,将 epoch 的实现细节暗藏在库中,裸露给用户极其简略的接口,使得大家在实现无锁数据结构时更多关注数据结构的细节,将内存回收工作交给 Crossbeam-epoch 来解决即可。