Atomic Reference Counting

Siler picture Siler · Jul 6, 2015 · Viewed 8.6k times · Source

I'm trying to understand exactly how thread-safe, atomic reference counting works, for example as with std::shared_ptr. I mean, the basic concept is simple, but I'm really confused about how the decref plus delete avoids race conditions.

This tutorial from Boost demonstrates how an atomic thread-safe reference counting system can be implemented using the Boost atomic library (or the C++11 atomic library).

#include <boost/intrusive_ptr.hpp>
#include <boost/atomic.hpp>

class X {
public:
  typedef boost::intrusive_ptr<X> pointer;
  X() : refcount_(0) {}

private:
  mutable boost::atomic<int> refcount_;
  friend void intrusive_ptr_add_ref(const X * x)
  {
    x->refcount_.fetch_add(1, boost::memory_order_relaxed);
  }
  friend void intrusive_ptr_release(const X * x)
  {
    if (x->refcount_.fetch_sub(1, boost::memory_order_release) == 1) {
      boost::atomic_thread_fence(boost::memory_order_acquire);
      delete x;
    }
  }
};

Okay, so I get the general idea. But I don't understand why the following scenario is NOT possible:

Say the refcount is currently 1.

  1. Thread A: atomically decrefs the refcount to 0.
  2. Thread B: atomically increfs the refcount to 1.
  3. Thread A: calls delete on the managed object pointer.
  4. Thread B: sees the refcount as 1, accesses the managed object pointer... SEGFAULT!

I can't understand what prevents this scenario from occurring, since there is nothing preventing a data race from between the time the refcount reaches 0, and the object is deleted. Decrefing the refcount and calling delete are two separate, non-atomic operations. So how is this possible without a lock?

Answer

MikeMB picture MikeMB · Jul 6, 2015

You probably overestimate the threadsafety a shared_ptr provides.

The essence of atomic ref counting is to ensure that if two different instances of a shared_ptr (that are managing the same object) are accessed/modified, there will be no race condition. However, shared_ptr doesn't ensure thread safety, if two threads access the same shared_ptr object (and one of them is a write). One example would be e.g. if one thread dereferences the pointer, while the other resets it.
So about the only thing shared_ptr gurantees is that there will be no double delete and no leak as long as there is no race on a single instance of a shared_ptr (It also doesn't make accesses to the object it points to threadsafe)

As a result, also creating a copy of a shared_ptr is only safe, if there is no other thread that could delete/reset it at the same time (you could also say, it is not internally synchronized). This is the scenario you describe.

To repeat it once more: Accessing a single shared_ptr instance from multiple threads where one of those accesses is a write to the pointer is still a race condition.

If you want to e.g. copy a std::shared_ptrin a threadsafe manner, you have to ensure that all loads and stores happen via std::atomic_... operations which are specialized for shared_ptr.