How is the std::tr1::shared_ptr implemented?

I've been thinking about using shared pointers, and I know how to implement one myself--Don't want to do it, so I'm trying std::tr1::shared_ptr,and I have couple of questions...

How is the reference counting implemented? Does it use a doubly linked list? (Btw, I've already googled, but I can't find anything reliable.)

Are there any pitfalls for using the std::tr1::shared_ptr?

Solution 1:

shared_ptr must manage a reference counter and the carrying of a deleter functor that is deduced by the type of the object given at initialization.

The shared_ptr class typically hosts two members: a T* (that is returned by operator-> and dereferenced in operator*) and a aux* where aux is a inner abstract class that contains:

• a counter (incremented / decremented upon copy-assign / destroy)
• whatever is needed to make increment / decrement atomic (not needed if specific platform atomic INC/DEC is available)
• an abstract virtual destroy()=0;
• a virtual destructor.

Such aux class (the actual name depends on the implementation) is derived by a family of templatized classes (parametrized on the type given by the explicit constructor, say U derived from T), that add:

• a pointer to the object (same as T*, but with the actual type: this is needed to properly manage all the cases of T being a base for whatever U having multiple T in the derivation hierarchy)
• a copy of the deletor object given as deletion policy to the explicit constructor (or the default deletor just doing delete p, where p is the U* above)
• the override of the destroy method, calling the deleter functor.

A simplified sketch can be this one:

template<class T>
class shared_ptr
{
    struct aux
    {
        unsigned count;

        aux() :count(1) {}
        virtual void destroy()=0;
        virtual ~aux() {} //must be polymorphic
    };

    template<class U, class Deleter>
    struct auximpl: public aux
    {
        U* p;
        Deleter d;

        auximpl(U* pu, Deleter x) :p(pu), d(x) {}
        virtual void destroy() { d(p); } 
    };

    template<class U>
    struct default_deleter
    {
        void operator()(U* p) const { delete p; }
    };

    aux* pa;
    T* pt;

    void inc() { if(pa) interlocked_inc(pa->count); }

    void dec() 
    { 
        if(pa && !interlocked_dec(pa->count)) 
        {  pa->destroy(); delete pa; }
    }

public:

    shared_ptr() :pa(), pt() {}

    template<class U, class Deleter>
    shared_ptr(U* pu, Deleter d) :pa(new auximpl<U,Deleter>(pu,d)), pt(pu) {}

    template<class U>
    explicit shared_ptr(U* pu) :pa(new auximpl<U,default_deleter<U> >(pu,default_deleter<U>())), pt(pu) {}

    shared_ptr(const shared_ptr& s) :pa(s.pa), pt(s.pt) { inc(); }

    template<class U>
    shared_ptr(const shared_ptr<U>& s) :pa(s.pa), pt(s.pt) { inc(); }

    ~shared_ptr() { dec(); }

    shared_ptr& operator=(const shared_ptr& s)
    {
        if(this!=&s)
        {
            dec();
            pa = s.pa; pt=s.pt;
            inc();
        }        
        return *this;
    }

    T* operator->() const { return pt; }
    T& operator*() const { return *pt; }
};

Where weak_ptr interoperability is required a second counter (weak_count) is required in aux (will be incremented / decremented by weak_ptr), and delete pa must happen only when both the counters reach zero.

Solution 2:

How is the reference counting implemented?

A smart pointer implementation could be deconstructed, using policy-based class design¹, into :

• Storage Policy

• Ownership Policy

• Conversion Policy

• Checking Policy

included as template parameters. Popular ownership strategies include: deep copy, reference counting, reference linking, and destructive copy.

Reference counting tracks the number of smart pointers pointing to (owning²) the same object. When the number goes to zero, the pointee object is deleted³. The actual counter could be:

1. Shared among smart pointer objects, where each smart pointer holds a pointer to the reference counter:

2. Included only in an additional structure that adds an extra level of indirection the pointee object. Here the space overhead of holding a counter in each smart pointer is exchanged with slower access speed:

3. Contained within the pointee object itself: intrusive reference counting. The disadvantage is that the object must be constructed a priori with facilities for counting:

   

4. Finally the method in your question, reference counting using doubly linked lists is called reference linking and it:

...[1] relies on the observation that you don't really need the actual count of smart pointer objects pointing to one pointee object; you only need to detect when that count goes down to zero. This leads to the idea of keeping an "ownership list" :

The advantage of reference linking over reference counting is that the former does not use extra free store, which makes it more reliable: Creating a reference-linked smart pointer cannot fail. The disadvantage is that reference linking needs more memory for its bookkeeping (three pointers versus only one pointer plus one integer). Also, reference counting should be a bit speedier—when you copy smart pointers, only an indirection and an increment are needed. The list management is slightly more elaborate. In conclusion, you should use reference linking only when the free store is scarce. Otherwise, prefer reference counting.

Regarding your second question:

Does it (std::shared_ptr) use a doubly linked list?

All that I could find in the C++ standard was:

20.7.2.2.6 shared_ptr creation
...
7. [ Note: These functions will typically allocate more memory than sizeof(T) to allow for internal bookkeeping structures such as the reference counts. —end note ]

Which, in my opinion, excludes doubly linked lists, as they do not contain actual count.

Your third question:

Are there any pitfalls for using the std::shared_ptr?

Reference management either counting or linking is a victim of the resource leak known as cyclic reference. Let's have an object A that holds a smart pointer to an object B. Also, object B holds a smart pointer to A. These two objects form a cyclic reference; even though you don't use any of them any more, they use each other. The reference management strategy cannot detect such cyclic references, and the two objects remain allocated forever.

Because the implementation of shared_ptr uses reference counting, cyclic references are potentially a problem. A cyclic shared_ptr chain can be broken by changing the code so that one of the references is a weak_ptr. This is done by assigning values between shared pointers and weak pointers, but a weak pointer doesn't affect the reference count. If the only pointers that point to an object are weak, the object is destroyed.

^{1. Each design feature with multiple implementations if formulated as policy.}

^{2. Smart pointers similarly to pointers that point to object allocated with new, not only point to that object but also are responsible for its destruction and with the release of the memory it occupies.}

^{3. With no further problems, if no other raw pointers are used and/or point to it.}

[1] Modern C++ Design: Generic Programming and Design Patterns Applied. Andrei Alexandrescu, February 01, 2001

Solution 3:

If you want to see all the gory details, you can have a look at the boost shared_ptr implementation:

https://github.com/boostorg/smart_ptr

The reference counting seems to usually be implemented with a counter and platform specific atomic increment/decrement instructions or explicit locking with a mutex (see the atomic_count_*.hpp files in the detail namespace).

Solution 4:

Are there any pitfalls for using the std::tr1::shared_ptr?

Yes, If you create cycles in your shared memory pointers, then the memory being managed by the smart pointer will not be recycled when the last pointer goes out of scope because there are still references to the pointer (i.e., the cycles cause the reference count to not go down to zero).

For instance:

struct A
{
    std::shared_ptr<A> ptr;
};

std::shared_ptr<A> shrd_ptr_1 = std::make_shared(A());
std::shared_ptr<B> shrd_ptr_2 = std::make_shared(A());
shrd_ptr_1->ptr = shrd_ptr_2;
shrd_ptr_2->ptr = shrd_ptr_1;

Now, even if shrd_ptr_1 and shrd_ptr_2 go out of scope, the memory they are managing is not reclaimed because the ptr member of each are pointing to each other. While this is a very naive example of such a memory cycle, it can, if you use these types of pointers without any discipline, occur in a much more nefarious and hard-to-track fashion. For instance, I could see where trying to implement a circular linked-list where each next pointer is a std::shared_ptr, if you're not too careful, could result in problems.