c++ - 无锁引用计数和 C++ 智能指针

Question

通常，最广为人知的 C++ 中引用计数智能 ptr 类的实现，包括标准 std::shared_ptr ，使用原子引用计数，但不提供对同一个智能 ptr 实例的原子访问。换句话说，多个线程可以安全地运行在单独的 shared_ptr 上。指向同一个共享对象的实例，但多个线程不能安全地读/写同一个实例 shared_ptr实例而不提供某种同步，例如互斥锁或其他什么。
shared_ptr 的原子版本名为“atomic_shared_ptr”已被 proposed ，初步implementations已经存在。大概，atomic_shared_ptr可以使用自旋锁或互斥锁轻松实现，但无锁实现也是可能的。

在研究了其中的一些实现之后，一件事很明显:实现无锁 std::shared_ptr很难，而且好像需要这么多compare_and_exchange操作让我怀疑一个简单的自旋锁是否会获得更好的性能。

实现无锁引用计数指针如此困难的主要原因是因为读取共享控制块(或共享对象本身，如果我们谈论的是侵入性共享指针)之间始终存在竞争，并修改引用计数。

换句话说，您甚至无法安全地读取引用计数，因为您永远不知道其他线程何时释放了引用计数所在的内存。

因此，通常会采用各种复杂的策略来创建无锁版本。 implementation here看起来它使用了双引用计数策略，其中有“本地”引用计算并发访问 shared_ptr 的线程数。实例，然后是“共享”或“全局”引用，它们计算指向共享对象的 shared_ptr 实例的数量。

考虑到所有这些复杂性，我真的很惊讶地发现 Dobbs 博士的一篇文章，从 2004 年开始(比 C++11 原子更早)，它似乎漫不经心地解决了整个问题:

http://www.drdobbs.com/atomic-reference-counting-pointers/184401888

看起来作者声称能够以某种方式:

"... [read] the pointer to the counter, increments the counter, and returns the pointer—all in such a manner that no other threads can cause an incorrect result"

但我真的不明白他实际实现这一点的方式。他正在使用(非可移植)PowerPC 指令(LL/SC 原语 lwarx 和 stwcx)来实现这一点。

执行此操作的相关代码被他称为“aIandF”(原子增量和获取)，他将其定义为:

addr aIandF(addr r1){
  addr tmp;int c;
  do{
    do{
      tmp = *r1;
      if(!tmp)break;
      c = lwarx(tmp);
    }while(tmp != *r1);
  }while(tmp && !stwcx(tmp,c+1));
  return tmp;
};

显然，addr是指向拥有引用计数变量的共享对象的指针类型。

我的问题是 :, 这是否只能与支持 LL/SC 操作的架构有关？用 cmpxchg 似乎是不可能的.其次，这究竟是如何工作的？我现在已经阅读了几次这段代码，我无法真正理解发生了什么。我懂什么LL/SC原语做，我只是无法理解代码。

我能理解的最好的是 addr r1是指向共享对象的指针的地址，也是指向引用计数的指针的地址(我猜这意味着引用计数变量需要是定义共享对象的 struct 的第一个成员)。然后他取消引用 addr (获取共享对象的实际地址)。然后，他链接加载了存储在tmp 中的地址的值。 ，并将结果存储在 c 中.这是计数器值。然后，他有条件地将增加的值(如果 tmp 发生变化，这将失败)存储回 tmp。 .

我不明白的是这是如何工作的。共享对象的地址可能永远不会改变并且 LL/SC 可能会成功 - 但是如果另一个线程同时释放了共享对象，这对我们有什么帮助？

Answer 1

addr aIandF(addr r1) {
  addr tmp;
  int c;
  do {
    do {
      // r1 holds the address of the address
      // of the refcount
      tmp = *r1;       // grab the address of the refcount
      if (!tmp) break; // if it's null, bail

      // read current refcount
      // and acquire reservation
      c = lwarx(tmp);

      // now we hold the reservation,
      // check to see if another thread
      // has changed the shared block address
    } while (tmp != *r1); // if so, start over

    // if the store succeeds we know we held
    // the reservation throughout
  } while (tmp && !stwcx(tmp, c+1));
  return tmp;
};

请注意 aIandF在构造现有共享指针的拷贝时专门使用，声明对拷贝的引用。

Dr Dobbs 的文章描述了释放引用的操作，首先将源共享指针对象中的共享计数器的地址与函数本地的空指针进行原子交换；然后以原子方式递减计数器；然后测试以查看递减的结果是否为零。这个操作顺序很重要:你说，“共享对象的地址可能永远不会改变，LL/SC 可能会成功 - 但是如果另一个线程同时释放了共享对象，这对我们有什么帮助？” - 但这永远不会发生，因为如果没有首先发生交换，对象永远不会被释放，这给了我们一种观察地址变化的方法。
aIandF测试计数器地址在进入时为空。

如果发生在 lwarx 之前，它可以发现地址变为空。 ，因为一旦它有保留，它就会显式地测试这个。

如果递减线程中的交换发生在 lwarx 之后，我们实际上并不关心:如果 stwcx在 aIandF成功，我们知道递减线程将看到新的引用计数而不破坏对象，我们可以继续知道我们已经声明了对它的引用；而如果另一个线程成功地先减少计数器，我们将失去我们的保留，存储将失败，我们将在下一次循环迭代中检测到对象的破坏。

该算法假设了一个高度一致的内存模型(所有线程总是按照程序顺序看到彼此读取和写入的影响)——即使在那些支持 ll/sc 的现代体系结构上也不一定如此。

编辑:考虑一下，该算法显然还假设从曾经有效的内存地址读取总是安全的(例如，没有 MMU/保护；或者，算法被破坏):

if (!tmp) break;

// another thread could, at this point, do its swap, 
// decrement *and* destroy the object tmp points to
// before we get to do anything else

c = lwarx(tmp); 

// if that happened, we'll detect this fact and do nothing with c
// but ONLY if the lwarx doesn't trap 
// (due to the memory tmp points to 
// getting unmapped when the other thread frees the object)