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?

Solution 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.

Solution 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.

Solution 3

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.

Solution 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.

Solution 5

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.

View more solutions

Comments

[curiousguy]

The linked-list approach avoids the extra allocation, but is very difficult to make "thread-safe" without a global mutex. ("thread-safe" as in "as thread-safe as a raw pointer")

[Ferruccio]

Also if you use make_shared, it may also avoid the extra allocation by putting the allocated object and instance counter in a single block of memory.

[Assimilater]

Didn't know about the linked list approach. I can see a few advantages to it over the first approach which I'm familiar with. Namely the lack of the extra "small block of memory" and the lack of need to worry about arithmetic overflow.

[Ferruccio]

@Assimilater - I don't think there's any real advantage to the linked list method. You do have to maintain the list, which has implications for thread safety and performance. Whereas the extra block allocation usually disappears if you use make_shared and everyone should be using make_shared anyway. Also if arithmetic overflow is a real possibility in this context, I suspect there are far more serious problems with the code base.

[Assimilater]

@Ferruccio that last point, I hear ya. Probably shouldn't have more than 2^16 copies of a pointer. How does make_shared remove the extra allocation for the reference counter? I'll have to try implementing both systems I guess to see how thread safety and performance are affected (I'm having a hard time seeing it off-hand)

[Ferruccio]

@Assimilater - you allocate a block big enough to hold both the object and reference count. You then store the reference count just past the last byte of the object.

[Assimilater]

@Ferruccio Oh, so the point is rather than two allocations it's one allocation, and thus less fragmented?

[underscore_d]

@Assimilater less fragmented and less CPU time calling the allocator (up to 50% less, I suppose)

[xaxxon]

@Ferruccio "everyone should be using make_shared anyway. " That's not true at all. There are numerous reasons to not use it tied to both performance and functionality.

[xaxxon]

You didn't try again later.