How does a reference-counting smart pointer's reference counting work?

Question

In other words, how does the implementation keeps track of the count?

Is there a map-like object maintained which is accessible by all the shared_ptr instances whose key is the pointer's address and value is the number of references? If I've to implement a shared_ptr, this is the first idea that's coming to my mind.

Is there a possibility for a memory leak in case of these reference-counting smart pointers? If so, how can I avoid them?

Answer 1

I've seen two different non-intrusive approaches to this:

1. The smart pointer allocates a small block of memory to contain the reference counter. Each copy of the smart pointer then receives a pointer to the actual object and a pointer to the reference count.
2. In addition to an object pointer, each smart pointer contains a previous and next pointer, thereby forming a doubly-linked list of smart pointers to a particular object. The reference count is implicit in the list. When a smart pointer is copied, it adds itself to the list. Upon destruction, each smart pointer removes itself from the list. If it's the last one in the list it then frees the referenced object as well.

If you go here and scroll to the bottom, there is an excellent diagram which explains these methods much more clearly.

Answer 2

Creating a memory leak with reference-counting smart pointers is very easy. Just create any graph-like structure of objects that has a cycle in the graph. The objects in the cycle will prevent each other from being released. This can't be resolved automatically - for example, when you create a double-link list you have to take care of never removing more than one object at a time.

Answer 3

Each smart pointer object contains a shared reference count - one for every raw pointer.

You could take a look at this article. This implementation stores these in a separate object which is copied around. You could also take a look at boost's documentation or take a look at the Wikipedia article on smart pointers.

Answer 4

No. shared_ptr just keep one additional pointer for reference counting.

When you make copy of shared_ptr object it copy pointer with count of references, increase it, and copy pointer on contained object.

Answer 5

As far as I remember, there was the problem of reference counting pointer treated in a chapter of Effective C++.

In principle, you have the "light" pointer class, containing a pointer to a class holding the reference which knows to increment/decrement reference and destroy the pointer object. That reference counting class points to the object to be referenced.

Answer 6

Many answers address the way the reference count is stored (it is stored in a shared memory for all shared_ptr that hold the same native pointer), but most elude the problem of leaks.

The easiest way of leaking memory with reference counted pointers is creating cycles. As an example, a doubly linked list where all the pointers are shared_ptr with at least two elements is guaranteed not to be deleted. Even if external pointers are freed, the internal pointers will still count, and the reference count will not reach 0. That is, at least, with the most naïve implementation.

The easiest solution to the cycle problem is mixing shared_ptr (reference counted pointers) with weak pointers that do not share the ownership of the object.

Shared pointers will share both the resource (pointer) and the additional reference_count information. When you use weak pointers, the reference count is doubled: there is a shared pointer reference count and a weak pointer reference count. The resource is released whenever the shared pointer count reaches 0, but the reference_count information is left alive until the last weak pointer is released.

In the doubly linked list, the external reference is held in a shared_ptr, while the internal links are just weak_ptr. Whenever there are no external references (shared_ptr) the elements of the list are released, deleting the weak references. At the end all weak references have been deleted and the last weak pointer to each resources frees the reference_count information.

It is less confusing than the above text seems... I'll try again later.