c++ - 如何实现不溢出的原子引用计数器？

Question

我正在考虑基于不会溢出的原子整数的引用计数。怎么做？

请不要关注这种溢出是否是一个现实问题。任务本身引起了我的兴趣，即使实际上并不重要。

---

示例

引用计数的示例实现在 Boost.Atomic 中作为示例显示。 .基于该示例，我们可以提取以下示例代码:

struct T
{
    boost::atomic<boost::uintmax_t> counter;
};

void add_reference(T* ptr)
{
    ptr->counter.fetch_add(1, boost::memory_order_relaxed);
}

void release_reference(T* ptr)
{
    if (ptr->counter.fetch_sub(1, boost::memory_order_release) == 1) {
        boost::atomic_thread_fence(boost::memory_order_acquire);
        delete ptr;
    }
}

另外给出如下解释

Increasing the reference counter can always be done with memory_order_relaxed: New references to an object can only be formed from an existing reference, and passing an existing reference from one thread to another must already provide any required synchronization.

It is important to enforce any possible access to the object in one thread (through an existing reference) to happen before deleting the object in a different thread. This is achieved by a "release" operation after dropping a reference (any access to the object through this reference must obviously happened before), and an "acquire" operation before deleting the object.

It would be possible to use memory_order_acq_rel for the fetch_sub operation, but this results in unneeded "acquire" operations when the reference counter does not yet reach zero and may impose a performance penalty.

编辑>>>

似乎Boost.Atomic此处的文档可能有误。 acq_rel毕竟可能需要。

至少boost::shared_ptr 的实现是这样的使用 std::atomic 完成后(还有其他实现)。参见文件 boost/smart_ptr/detail/sp_counted_base_std_atomic.hpp .

Herb Sutter 在他的演讲中也提到了它 C++ and Beyond 2012: Herb Sutter - atomic<> Weapons, 2 of 2 (引用计数部分从 1:19:51 开始)。此外，他似乎不鼓励在这次谈话中使用栅栏。

感谢user 2501在下面的评论中指出这一点。

<<< 结束编辑

---

初步尝试

现在的问题是add_reference所写的可能(在某些时候)溢出。而且它会默默地这样做。这显然会在调用匹配 release_reference 时导致问题那会过早地破坏物体。 (前提是 add_reference 将再次被调用以到达 1 。)

我在想如何制作add_reference检测溢出并在不冒任何风险的情况下优雅地失败。

与 0 相比一旦我们离开fetch_add不会做，因为在这两个线程之间，其他线程可以调用 add_reference再次(达到 1 )然后 release_reference (错误地破坏了有效的对象)。

首先检查(使用 load )也无济于事。这样一些其他线程可以在我们对 load 的调用之间添加自己的引用和 fetch_add .

---

这是解决方案吗？

然后我想也许我们可以从 load 开始但前提是我们这样做compare_exchange .

所以我们首先做 load并获得本地值(value)。如果是std::numeric_limits<boost::uintmax_t>::max()然后我们失败了。 add_reference无法添加其他引用，因为所有可能的都已被采用。

否则我们创建另一个本地值，即先前的本地引用计数加上1。 .

现在我们做 compare_exchange提供原始本地引用计数作为期望值(这确保没有其他线程同时修改引用计数)，并提供增加的本地引用计数作为期望值。

自 compare_exchange可能会失败，我们必须在循环中执行此操作(包括 load)。直到成功或检测到最大值。

---

一些问题

1. 这样的解是否正确？
2. 需要什么样的内存顺序才能使其有效？
3. 哪个compare_exchange应该使用？ _weak或 _strong ？
4. 会不会影响release_reference功能？
5. 在实践中使用了吗？

Answer 1

解决方案是正确的，也许可以通过一件事来改进。目前，如果该值在本地 CPU 中达到最大值，则可以通过另一个 CPU 降低该值，但当前 CPU 仍会缓存旧值。值得用相同的 expected 和 newValue 做虚拟 compare_exchange 来确认最大值仍然存在，然后才抛出异常(或其他任何你想要的)。

其余的:

无论您使用 _weak 还是 _strong 都没有关系，因为它无论如何都会循环运行，因此下一个 load 会变得相当可靠的最新值。

对于 add_reference 和 release_reference - 那么谁来检查它是否真的被添加了？它会抛出异常吗？如果是，它可能会起作用。但一般来说，最好让这样低级别的事情不会失败，而是将 uintptr_t 用作引用计数器，这样它就不会溢出，因为它足够大，可以覆盖地址空间，因此可以覆盖同时存在的任意数量的对象。

不，由于上述原因，它没有在实践中使用。