title: How to implement atomic reference counter that does not overflow?
body: <p>I was thinking about reference counting based on atomic integers that would be safe from overflow. How to do it?</p>
  
  <p>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.</p>
  
  <hr>
  
  <p><strong>Example</strong></p>
  
  <p>Example implementation of reference counting is shown as an example in <a href="http://www.boost.org/doc/libs/1_61_0/doc/html/atomic/usage_examples.html#boost_atomic.usage_examples.example_reference_counters" rel="nofollow noreferrer">Boost.Atomic</a>. Based on that example we can extract following sample code:</p>
  
  <pre><code>struct T
  {
      boost::atomic&lt;boost::uintmax_t&gt; counter;
  };
  
  void add_reference(T* ptr)
  {
      ptr-&gt;counter.fetch_add(1, boost::memory_order_relaxed);
  }
  
  void release_reference(T* ptr)
  {
      if (ptr-&gt;counter.fetch_sub(1, boost::memory_order_release) == 1) {
          boost::atomic_thread_fence(boost::memory_order_acquire);
          delete ptr;
      }
  }
  </code></pre>
  
  <p>In addition following explanation is given</p>
  
  <blockquote>
    <p>Increasing the reference counter can always be done with <code>memory_order_relaxed</code>: 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.</p>
    
    <p>It is important to enforce any possible access to the object in one thread (through an existing reference) to <em>happen before</em> 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.</p>
    
    <p>It would be possible to use <code>memory_order_acq_rel</code> for the <code>fetch_sub</code> operation, but this results in unneeded "acquire" operations when the reference counter does not yet reach zero and may impose a performance penalty.</p>
  </blockquote>
  
  <p><strong>EDIT >>></strong></p>
  
  <p>It seems that <a href="http://www.boost.org/doc/libs/1_61_0/doc/html/atomic/usage_examples.html#boost_atomic.usage_examples.example_reference_counters" rel="nofollow noreferrer">Boost.Atomic</a> documentation might be wrong here. The <code>acq_rel</code> might be needed after all.</p>
  
  <p>At least such is the implementation of <code>boost::shared_ptr</code> when done using <code>std::atomic</code> (there are other implementations as well). See file <a href="http://www.boost.org/doc/libs/1_61_0/boost/smart_ptr/detail/sp_counted_base_std_atomic.hpp" rel="nofollow noreferrer"><code>boost/smart_ptr/detail/sp_counted_base_std_atomic.hpp</code></a>.</p>
  
  <p>Also Herb Sutter mentions it in his lecture <a href="https://channel9.msdn.com/Shows/Going+Deep/Cpp-and-Beyond-2012-Herb-Sutter-atomic-Weapons-2-of-2" rel="nofollow noreferrer">C++ and Beyond 2012: Herb Sutter - atomic&lt;> Weapons, 2 of 2</a> (reference counting part starts at 1:19:51). Also he seems to be discouraging use of fences in this talk.</p>
  
  <p>Thanks to <a href="https://stackoverflow.com/users/4082723/2501">user 2501</a> for pointing that out in comments below.</p>
  
  <p><strong>&lt;&lt;&lt; END EDIT</strong></p>
  
  <hr>
  
  <p><strong>Initial attempts</strong></p>
  
  <p>Now the problem is that <code>add_reference</code> as written could (at some point) overflow. And it would do so silently. Which obviously could lead to problems when calling matched <code>release_reference</code> that would prematurely destroy the object. (Provided that <code>add_reference</code> would be then called once again to reach <code>1</code>.)</p>
  
  <p>I was thinking how to make <code>add_reference</code> detect overflow and fail gracefully without risking anything.</p>
  
  <p>Comparing to <code>0</code> once we leave <code>fetch_add</code> will not do since between the two some other thread could call <code>add_reference</code> again (reaching <code>1</code>) and then <code>release_reference</code> (erroneously destroying the object in effect).</p>
  
  <p>Checking first (with <code>load</code>) will not help either. This way some other thread could add its own reference between our calls to <code>load</code> and <code>fetch_add</code>.</p>
  
  <hr>
  
  <p><strong>Is this the solution?</strong></p>
  
  <p>Then I thought that maybe we could start with <code>load</code> but only if then we do <code>compare_exchange</code>.</p>
  
  <p>So first we do <code>load</code> and get a local value. If it is <code>std::numeric_limits&lt;boost::uintmax_t&gt;::max()</code> then we fail. <code>add_reference</code> cannot add another reference as all possible are already taken.</p>
  
  <p>Otherwise we make another local value which is the previous local reference count plus <code>1</code>.</p>
  
  <p>And now we do <code>compare_exchange</code> 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.</p>
  
  <p>Since <code>compare_exchange</code> can fail we have to do this (including <code>load</code>) in a loop. Until it succeeds or max value is detected.</p>
  
  <hr>
  
  <p><strong>Some questions</strong></p>
  
  <ol>
  <li>Is such solution correct?</li>
  <li>What memory ordering would be required to make it valid?</li>
  <li>Which <code>compare_exchange</code> should be used? <code>_weak</code> or <code>_strong</code>?</li>
  <li>Would it affect <code>release_reference</code> function?</li>
  <li>Is it used in practice?</li>
  </ol>