How to implement atomic reference counter that does not overflow?

Question

I was thinking about reference counting based on atomic integers that would be safe from overflow. How to do it?

Please let's not focus on whether such overflow is a realistic problem or not. The task itself got my interest even if not practically important.

---

Example

Example implementation of reference counting is shown as an example in Boost.Atomic. Based on that example we can extract following sample code:

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

In addition following explanation is given

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.

EDIT >>>

It seems that Boost.Atomic documentation might be wrong here. The acq_rel might be needed after all.

At least such is the implementation of boost::shared_ptr when done using std::atomic (there are other implementations as well). See file boost/smart_ptr/detail/sp_counted_base_std_atomic.hpp.

Also Herb Sutter mentions it in his lecture C++ and Beyond 2012: Herb Sutter - atomic<> Weapons, 2 of 2 (reference counting part starts at 1:19:51). Also he seems to be discouraging use of fences in this talk.

Thanks to user 2501 for pointing that out in comments below.

<<< END EDIT

---

Initial attempts

Now the problem is that add_reference as written could (at some point) overflow. And it would do so silently. Which obviously could lead to problems when calling matched release_reference that would prematurely destroy the object. (Provided that add_reference would be then called once again to reach 1.)

I was thinking how to make add_reference detect overflow and fail gracefully without risking anything.

Comparing to 0 once we leave fetch_add will not do since between the two some other thread could call add_reference again (reaching 1) and then release_reference (erroneously destroying the object in effect).

Checking first (with load) will not help either. This way some other thread could add its own reference between our calls to load and fetch_add.

---

Is this the solution?

Then I thought that maybe we could start with load but only if then we do compare_exchange.

So first we do load and get a local value. If it is std::numeric_limits<boost::uintmax_t>::max() then we fail. add_reference cannot add another reference as all possible are already taken.

Otherwise we make another local value which is the previous local reference count plus 1.

And now we do compare_exchange providing as expected value the original local reference count (this ensures that no other thread modified reference count in the mean time) and as the desired value the incremented local reference count.

Since compare_exchange can fail we have to do this (including load) in a loop. Until it succeeds or max value is detected.

---

Some questions

1. Is such solution correct?
2. What memory ordering would be required to make it valid?
3. Which compare_exchange should be used? _weak or _strong?
4. Would it affect release_reference function?
5. Is it used in practice?

Answer 1

This question is moot. Even assuming atomic increment takes 1 CPU cycle (it does not!), on 4GHz CPU it would take half a year to wrap around 64bit integer, providing CPU does nothing else but keep incrementing.

Taking into account realities of an actual program, I find it hard to believe this is a real issue which can pester you.

Answer 2

Quick math: say uint is 32 bits, so max uint is 4G (4 billion something). Each reference/pointer is at least 4 bytes (8 if you are on a 64 bit system) so to overflow you need 16Gbytes of memory dedicated to storing references pointing to the same object, which should point to a serious deign flaw.

I would say it's not a problem today, nor in the foreseeable future.

Answer 3

The solution is correct, maybe it could be improved with one thing. Currently, if the value reaches max in the local CPU, it can be decreased by another CPU but the current CPU would still cache the old value. It would be worth doing dummy compare_exchange with the same expected and newValue to confirm the max is still there and only then throw an exception (or whatever you want).

For the rest:

It doesn't matter whether you use _weak or _strong as it will run in loop anyway and therefore the next load will get quite reliably the latest value.

For the add_reference and release_reference - who would then check whether it was really added or not? Would it throw an exception. If yes, it would work probably. But generally it's better to allow such a low level things not to fail and rather use uintptr_t for the reference counter so it could never overflow as it's big enough to cover the address space and therefore any number of objects existing at the same time.

No, it's not used in practice for the above reasons.