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

Question

一般来说，C++ 中最广为人知的引用计数智能指针类实现，包括标准 std::shared_ptr，都使用原子引用计数，但不提供对相同智能指针的原子访问ptr 实例。换句话说，多个线程可以安全地操作指向同一个共享对象的单独 shared_ptr 个实例，但是多个线程不能安全地 read/write 相同 shared_ptr 实例而不提供某种同步，例如互斥体或其他。

一个名为“atomic_shared_ptr”的 shared_ptr 的原子版本 proposed, and preliminary implementations 已经存在。据推测，atomic_shared_ptr 可以很容易地用自旋锁或互斥锁实现，但无锁实现也是可能的。

研究了其中一些实现后，有一点很明显：实现无锁 std::shared_ptr 非常困难，似乎需要如此多的 compare_and_exchange 操作，以至于让我怀疑是否简单的自旋锁可以获得更好的性能。

实现无锁引用计数指针如此困难的主要原因是读取共享控制块（或共享对象本身，如果我们谈论的是侵入式共享指针），并修改引用计数。

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

所以一般来说，会采用各种复杂的策略来创建无锁版本。 implementation here 看起来像是使用了双引用计数策略，其中有 "local" 个引用来计算并发访问 shared_ptr 实例的线程数，然后 "shared" 或者"global" 引用计算指向共享对象的 shared_ptr 实例的数量。

考虑到所有这些复杂性，我真的很惊讶地发现一篇来自 2004 的 Dr. Dobbs 文章（在 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 专门用于构造现有共享指针的副本，声明该副本的引用。

Dobbs 博士的文章将释放引用的操作描述为首先将源共享指针对象中共享计数器的地址与函数本地的空指针进行原子交换；然后自动递减计数器；然后测试减量的结果是否为零。这个操作顺序很重要：你说，"The address of the shared object may never change and the LL/SC could succeed - but how does this help us if another thread has deallocated the shared object in the mean time?" - 但这永远不会发生，因为如果不首先发生交换，对象将永远不会被释放，这给了我们一种方法观察地址的变化。

aIandF 测试输入时计数器地址是否为空。

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

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

该算法假定一个高度一致的内存模型（所有线程总是按程序顺序看到彼此读写的影响）——即使在那些支持 ll/sc 的现代架构上也不一定如此。

编辑：考虑一下，算法也显然假设从曾经有效的内存地址读取总是安全的（例如，没有MMU/protection; 或者，算法坏了):

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)

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

Lock-free Reference counting and C++ smart pointers

c++

smart-pointers

atomic

c++11