为什么这些无锁引用计数实现没有爆炸（或者确实发生了）？

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);
     }
  }
}

首先来自David L. Detlefs 于2004 年发表的论文《无锁引用计数》，图 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是原子增量和负载。第二个来自Matopencv4 中的实现（为简洁起见进行了编辑）：

// 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是原子增量和负载。第三个来自最新版本的 GCC (10.2) 中libstdc++附带的实现（std::shared_ptr这个实现非常复杂，为了简洁起见，我对其进行了很多编辑）：

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.

}

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

• Copy：__shared_ptr默认复制构造函数copys _M_refcount，其复制构造函数_Sp_counted_base与原始构造函数共享相同的内容，并原子地递增引用计数器。
• 删除：__shared_ptr默认析构函数 destroys _M_refcount，其析构函数调用_M_release，_Sp_counted_base以原子方式递减并可能释放引用计数器。

---

无论如何，所有这一切都归结为一个问题，这是我无法理解为什么这些有效的关键（即使是那篇旧的多布斯博士文章和相关问题[我觉得答案可能在这里，但我不能看到它]对我来说提出的问题多于答案）：

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

也就是说，参考上面的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非空值但指向释放后垃圾？

我在这里缺少什么？我觉得这可能是显而易见的，也许我已经醒得太久了。特别是，libstdc++实现似乎也遵循这种模式，这一事实赋予了它大量的街头信誉；我只是无法理解细节。

Answer 1

简短的回答，你累了！

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

多线程还有两条附加规则。

1. 线程不得尝试递减计数器，除非它已经拥有引用。
2. 另外，（关键）线程不得尝试增加计数器，除非它已经拥有引用。

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

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

__gnu_cxx::__exchange_and_add_dispatch(&_M_use_count, -1)返回替换的值，因此该行的if (__gnu_cxx::__exchange_and_add_dispatch(&_M_use_count, -1)==1意思是“如果此线程交换”，1意思0是“如果此线程持有最后一个引用”。

有多种策略可确保线程不会递减或递增计数器，除非它拥有引用。但主要的一点是，确实持有引用的线程会在将其“传递”到另一个线程之前递增该引用，或者只是将其引用“交出”给另一个线程。

在对象被放置在队列中的“线程池”中，可能不确定引用被传递到哪个线程，并且需要进一步的同步（例如在队列上）以确保只有一个线程具有“共享”的“声明”参考。

我所说的“持有”是指“拥有”或“借用”。拥有意味着拥有引用的线程（将确保其最终释放），“借用”意味着实际拥有（将确保其最终释放）线程将与借用者同步，并确保在另一个线程之前不会释放它(a) 已获取引用或 (b) 不得再次访问该对象。

代码片段看起来有效（我不熟悉所有这些库的细节），但确认__exchange_and_add_dispatch返回旧值第 29 章。并发性足以让我相信这就是正在发生的事情。

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

弱引用是此模型上的一个微妙技巧，代表遵循同一模型的单独计数器。尽管可能（与std::shared_ptr使用一样std::make_shared）与主对象一起分配（new），并且虽然主对象可能在最后一个弱引用之前被破坏，deleted但当两个计数器都达到零时，并且如果在最后一个强引用时存在弱引用，则内存块会被销毁。释放弱引用被标记，表明主对象已被删除。