为什么这些无锁引用计数实现不会爆炸（或者它们会爆炸）？

Question

我正在努力研究 LFRC 算法，但我一直在寻找示例，其中 我假设 它们有效，但我不明白为什么。我专注于复制和删除。特别是三个都遵循相同的通用模式（伪代码）：

Copy {
  shared = source->shared;
  if (shared != null) {
     Atomically_Increment_Counter(shared);
  }
}

Delete {
  if (shared != null) {
     oldcounter = Atomically_Decrement_Counter(shared);
     if (oldcounter == value signifying all references released) {
        Deallocate(shared);
     }
  }
}

首先来自 2004 年的论文 Lock-Free Reference Counting by David L. Detlefs，图 2，第 8 页（针对格式进行了编辑）：

void LFRCCopy(SNode **v, SNode *w) {
   Snode *oldv = *v;
   if (w != null) 
      add_to_rc(w,1);
   *v = w;
   LFRCDestroy(oldv);
}

void LFRCDestroy(SNode *v) {
   if (v != null && add_to_rc(v, -1)==1) {
     LFRCDestroy(v->L);
     LFRCDestroy(v->R);
     delete v;
   }
}

其中add_to_rc是原子增量和加载。第二个来自 Mat implementation in opencv4（为简洁起见进行了编辑）：

// Line 405
Mat::Mat(const Mat& m)
    : flags(m.flags), dims(m.dims), rows(m.rows), cols(m.cols), data(m.data),
      datastart(m.datastart), dataend(m.dataend), datalimit(m.datalimit), allocator(m.allocator),
      u(m.u), size(&rows), step(0)
{
    if( u )
        CV_XADD(&u->refcount, 1);
    ...
}

// Line 551
void Mat::release()
{
    if( u && CV_XADD(&u->refcount, -1) == 1 )
        deallocate();
    u = NULL;
    ...
}

其中CV_XADD是原子增量和加载。第三个来自 the std::shared_ptr implementation that ships with libstdc++ in the most recent version of GCC (10.2)（此实现非常复杂，为简洁起见，我已对其进行了很多编辑）：

class _Sp_counted_base {

    void _M_add_ref_copy()
    { __gnu_cxx::__atomic_add_dispatch(&_M_use_count, 1); }

    // Line 161 for full implementation
    void _M_release() noexcept
    {
       _GLIBCXX_SYNCHRONIZATION_HAPPENS_BEFORE(&_M_use_count);
       if (__gnu_cxx::__exchange_and_add_dispatch(&_M_use_count, -1) == 1)
       {
          _GLIBCXX_SYNCHRONIZATION_HAPPENS_AFTER(&_M_use_count);
          _M_dispose();
          if (_Mutex_base<_Lp>::_S_need_barriers)
             __atomic_thread_fence (__ATOMIC_ACQ_REL);
          // editors note: weak pointer handling removed for brevity
          _M_destroy();
       }
    }

}

class __shared_count {

    __shared_count(const __shared_count& __r) noexcept 
        : _M_pi(__r._M_pi)
    {
        if (_M_pi != nullptr)
           _M_pi->_M_add_ref_copy();
    }
    
    ~__shared_count() noexcept
    {
        if (_M_pi != nullptr)
           _M_pi->_M_release();
    }

    _Sp_counted_base* _M_pi;

}

class __shared_ptr {

    __shared_ptr(const __shared_ptr&) noexcept = default;

    ~__shared_ptr() = default;

    element_type*   _M_ptr;         // Contained pointer.
    __shared_count  _M_refcount;    // Reference counter.

}

对最后一个的一些解释，因为它有点间接：

复制：__shared_ptr默认复制构造函数复制_M_refcount，其复制构造函数与原始复制构造函数共享相同的_Sp_counted_base，并自动递增引用计数器。
删除：__shared_ptr 默认析构函数销毁 _M_refcount，其析构函数在 _Sp_counted_base 上调用 _M_release，它自动递减并可能释放引用计数器。

无论如何，所有这些都归结为一个问题，这是我未能理解为什么这些工作的症结所在（甚至 that old Dr. Dobbs article and the related questions here on SO [I feel like the answer might be 但我看不到它] 对我提出的问题多于答案）：

在 copy 操作中，是什么阻止了另一个线程对最后一个引用计数执行 delete 操作的竞争条件（可能通过共享对象的另一个视图）然后在复制操作开始和原子计数器增量开始之间释放对象——因此，根据我（错误）的理解，导致复制以增加已释放的计数器并在各处崩溃或转储核心或其他什么？

也就是说，参考上面的 opencv 实现（因为检查它实际上是我在这里开始整个迷你研究项目的原因）：

Mat::Mat(const Mat& m) : flags(m.flags), dims(m.dims), rows(m.rows), cols(m.cols), data(m.data), datastart(m.datastart), dataend(m.dataend), datalimit(m.datalimit), allocator(m.allocator), u(m.u), // <--- START OF DANGER ZONE size(&rows), step(0) { if( u ) // <--- ALMOST AT END OF DANGER ZONE CV_XADD(&u->refcount, 1); ... } void Mat::release() { if( u && CV_XADD(&u->refcount, -1) == 1 ) deallocate(); u = NULL; ... }

是什么阻止了另一个线程通过复制构造函数中标记的“危险区域”中的 m 释放最后一个引用，从而使 u 非空但指向 post -释放垃圾？

我在这里错过了什么？我觉得这可能很明显，也许我醒得太久了。特别是，libstdc++ 实现似乎也遵循这种模式，这一事实赋予了它大量的街头信誉；就是看不懂细节。

Answer 1

简答，你累了！

这是经典'reference counting model'。当一个对象被创建时，它的引用计数被初始化（通常为 1）。创建线程拥有该引用。该线程在创建新引用时可能会增加或减少该计数，当它最终达到 0 时，不存在任何引用并且对象被删除。这都是单线程的，但你的问题是关于多线程的。

多线程还有两条规则。

线程不得尝试递减计数器，除非它已经拥有一个引用。
此外，（关键）线程不得尝试增加计数器，除非它已经持有一个引用。

因此，当一个线程试图增加引用数量（在副本中）时，另一个线程试图释放对象的竞争条件永远不会发生（也绝不能发生）。

因此，如果其他线程同时在释放引用计数，而另一个线程正在增加它，则计数应始终 >=2，因为两者都必须持有引用。

__gnu_cxx::__exchange_and_add_dispatch(&_M_use_count, -1) returns 替换了 值，因此行 if (__gnu_cxx::__exchange_and_add_dispatch(&_M_use_count, -1)==1 表示“如果此线程将 1 交换为 0 意思是“如果这个线程持有最后一个引用”。

有许多策略可确保没有线程递减或递增计数器，除非它持有引用。但主要的是，一个确实持有引用的线程在 'passing' 到另一个线程之前将其递增，或者只是 'surrenders' 它对另一个线程的引用。

在 'thread pool' 对象被放置在队列中的情况下，可能无法确定将引用传递给哪个线程，并且需要进一步同步（例如在队列上）以确保只有一个线程永远'声称是 'shared' 参考。

我所说的“持有”是指“拥有”或“借用”。拥有意味着拥有引用的线程（将确保它最终被释放）并且 'borrowing' 意味着实际拥有（这将确保其最终释放）线程将与借用者同步并确保它不会被释放直到其他线程已 (a) 获取引用或 (b) 不得再次访问该对象。

代码片段似乎有效（我不熟悉所有这些库的详细信息）但确认 __exchange_and_add_dispatch returns 旧值 Chapter 29. Concurrency 足以说服我这就是正在发生的事情。

然而，这些策略的缺点是所有增加或减少计数的代码都必须符合该策略，因此如果不仔细检查引用该策略的所有点的设计和实现，我们不知道代码是否有效对象。每个都有参考吗？如果他们增加了，他们是否已经有了参考？

弱引用是该模型的一个微妙技巧，代表了一个遵循同一模型的独立计数器。尽管可能（对于使用 std::make_shared 的 std::shared_ptr 来说很常见）分配 (new) 主对象，而主对象可能在最后一个弱引用之前被破坏，内存块是 deleteded 当两个计数器都为零并且如果在释放最后一个强引用时存在弱引用，则标记弱引用以显示主对象已被删除。

为什么这些无锁引用计数实现不会爆炸（或者它们会爆炸）？

Why don't these lock-free reference counting implementations explode (or do they)?

c++

concurrency

lock-free

reference-counting