无锁数据结构需要多少个ABA标记位？

Question

在无锁数据结构中，解决ABA问题的一个流行方案是使用额外单调递增标签对指针进行标记。

 struct aba {
      void *ptr;
      uint32_t tag;
 };

然而，这种方法存在问题。它非常缓慢并且具有巨大的缓存问题。如果我放弃标签字段，我可以获得两倍的加速。但这是不安全的吗？

因此，我接下来尝试为64位平台准备的东西将位数填入ptr字段中。

struct aba {
    uintptr __ptr;
};
uint32_t get_tag(struct aba aba) { return aba.__ptr >> 48U; }

但是有人告诉我，标签只使用16位是不安全的。我的新计划是使用指针对齐到高速缓存行来增加更多的标签位，但我想知道这是否可行。

如果这个计划行不通，我的下一个计划是使用Linux的MAP_32BITmmap标志来分配数据，这样我只需要32位指针空间。

在无锁数据结构中，ABA标记需要多少位？

- Molossus Spondee

---

我知道你开始使用单调递增的标签分配策略，我承认我对这个问题不是很了解，但一般来说，一个便宜的哈希函数（比如超对数分布的数字桶）不会导致标签冲突吗？ - bright-star

@bright-star 我曾考虑过使用哈希函数，但我无法构建一个好的理由来证明使用哈希函数比仅仅递增标签更好。不过这确实是一个非常有趣的想法。 - Molly Stewart-Gallus

Answer 1

实际上安全的标记位数可以根据抢占时间和指针修改频率进行估算。提醒一下，ABA问题发生在线程使用比较并交换读取它想要更改的值时，被抢占，当它恢复时，指针的实际值恰好等于线程之前读取的值。因此，尽管其他线程可能在抢占期间对数据结构进行了修改，但比较并交换操作仍可能成功。添加单调递增的标记的想法是使每个指针修改唯一。为了成功，增量必须在修改线程可能被抢占的时间内产生唯一的标记值；即为了保证正确性，在整个抢占时间内标记不能环绕。假设抢占持续一个操作系统调度时间片，通常为几十到几百毫秒。现代系统上CAS的延迟为几十到几百纳秒。所以粗略的最坏情况估计是，当线程被抢占时可能有数百万个指针修改，因此标记中应该有20多位，以避免环绕。实际上，可以根据已知的CAS操作频率为特定的实际用例作出更好的估计。还需要更准确地估计最坏情况下的抢占时间；例如，被更高优先级作业抢占的低优先级线程可能会遇到更长的抢占时间。

- Alexey Kukanov

---

就主观而言，我认为使用备用地址位来作为标记值的方法相当脆弱，而且不太可移植和不具备未来性（例如，如果未来的处理器代数将使用超过48位的内存寻址），因此在实际使用中是危险的。 - Alexey Kukanov

Answer 2

根据这篇论文，Hazard Pointers: Safe Memory Reclamation for Lock-Free Objects (IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL. 15, NO. 6, JUNE 2004 p. 491) ，博士Maged M. Michael指出，在真正的无锁场景中，标记位的大小应该设计成不可能出现环绕情况（我理解为可能有N个线程运行，并且每个线程都可以访问结构体，因此至少需要N + 1种不同状态的标记）。请参考http://web.cecs.pdx.edu/~walpole/class/cs510/papers/11.pdf。

6.1.1 IBM ABA-Prevention Tags

最早和最简单的无锁节点重用方法是标签（更新计数器）方法，该方法是在IBM System 370上介绍CAS文档时引入的[11]。它要求将标签与每个目标进行ABA问题比较操作的位置相关联。通过在写入相关位置的值时增加标签，比较操作（例如CAS）可以确定自上次由同一线程访问以来是否已写入该位置，从而防止ABA问题。 该方法要求标签包含足够的位数，以使在任何单个无锁尝试执行期间不可能完全绕回。该方法非常高效，并允许立即重用已退役的节点。

- osgx

---

不能保证其他线程只修改一次值，因此我认为基于线程数的任何限制都不安全。 - Alexey Kukanov

这篇论文列出了条件。你有其他条件不同的论文吗？ - osgx

所述条件正确，但我解释方式不同。特别是，“执行任何单个无锁尝试”的时间包括线程被抢占的时间，而其他线程在此期间可能会执行多个操作。我已经撰写了一份答案来澄清这一点。 - Alexey Kukanov

Answer 3

根据您的数据结构，您可以从指针中窃取一些额外的位。例如，如果对象是64字节并始终对齐在64字节边界上，则每个指针的低6位可用于标记（但这可能是您已经为新计划建议的内容）。

另一个选择是使用对象的索引而不是指针。

如果是连续的对象，那么当然只需要一个数组或向量的索引。在堆上分配对象的列表或树的情况下，您可以使用自定义分配器，并在分配的块中使用索引。

对于例如17M个对象，您只需要24位，留下40位供标记使用。

这将需要一些（小型和快速的）额外计算来获得地址，但如果对齐方式是2的幂，则只需要移位和加法。

- Danny_ds