First, let's outline the data structures and layouts. What we need is a base class for reference-counted objects, strong pointer layout and definitions of 2 types of pointers:
The interface we are going to implement is as follows:
Invariants and logic we are going to implement are as follows. Inner strong counter is the number of strong pointers to the object out there. Inner basic counter is the number of usual references to the object out there. When both counters drop to zero, the object is destroyed. Outer counter temporarily collects increments for the inner basic counter, which are transfered to the latter when the strong pointer is updated to point to another object (before that the object can't be destroyed anyway, because, well, there is a strong pointer to it).
Let's put it all together:
Below is the 'basic' part of implementation, I hope it's mostly evident:
And here is the 'strong' part, it's trickier, so pay attention to details (and comments):
Note that in 64-bit mode inner counters can be 32-bit and consequently combined into a single word, this can be of help if a 64-bit architecture does not support double-word atomic operations. Moreover, x86 architecture (IA-32, Intel64) supports only double-word CAS (but not XADD, XCHG), so current implementation is only lockfree on it (because of the CAS-loops); if counters are combined into a single word then the implementation will become wait-free.
Also in 64-bit mode, pointers frequently can be "compressed", for example, on Intel64/Windows it's possible to compress pointers into 39 bits, so 25 bits remain for the counter. This allows to pack strong pointer (ptr+counter) into a single word as well.
Here is an example of how strongly thread-safe reference counting can be applied to an abstract network router, it's kind of the main usage pattern:
Credits for the algorithm go to Joseph Seigh and his awesome Atomic-Ptr-Plus, Chris Thomasson and his proxy-collector, and finally to Alexander Shuvaev who invented how to make the algorithm waitfree.
I've attached the full implementation along with small single-threaded test and implementation of atomic_dword for IA-32/Intel64 below.
Home > Lockfree Algorithms > Object Life-time Management > Differential Reference Counting >