Channels ▼
RSS

C/C++

A Base Class for Intrusively Reference-Counted Objects in C++


Concurrency

Thread-safety is a complex mission. In C++0x, it is easy to make the counter atomic. Just include the <atomic> header and have the counter a type of std::atomic_size_t. The increment and decrement operations are atomic now. Now, the ref_counter class template offers the same level of thread safety as built-in types. Simultaneous reads are fine, but beware of other access patterns, for example:

	// shared global
	intrusive_ptr<foo> ps(new foo());

	// Thread 1
	intrusive_ptr<foo> p1(ps);	// read

	// Thread 2
	ps.reset();	// write

This is a data race that breaks invariances, even though the counter is atomic. The problem is that the intrusive_ptr operations are not atomic as a whole. Here is the copy constructor of intrusive_ptr:

intrusive_ptr( intrusive_ptr const & rhs ): px( rhs.px )
    {
        if( px != 0 ) intrusive_ptr_add_ref( px );
    }

Note that the pointer and the counter are not updated atomically, so, an invalid state can be observed. Just assume the following interleave:

  • Thread 1 calls the copy constructor and performs the copy of the pointer. The invariants are broken, as the pointer was copied and the counter is not yet incremented.
  • Thread 2 resets ps. This operation decrements the counter, which drops to zero, and thus the owned object is disposed.
  • Thread 1 completes the copy construction, uses the dangling pointer, and accesses the counter. Bang! undefined behavior based on a data race.

The race cannot be avoided in ref_counter, but rather in intrusive_ptr. [AtomicRCP] provides a lock-free non-portable non-C++0x implementation for PowerPC. Boost's shared_ptr uses a spin-lock pool, intrusive_ptr can easily use a similar implementation. shared_ptr provides operations like atomic_load, atomic_store, atomic_exchange, or atomic_compare_exchange ([C++0x 20.9.10.5, N2674]). The interface of intrusive_ptr should offer these operations. A compatible interface has the advantage of easy refactoring between intrusive_ptr and shared_ptr.

Customized Disposal

The disposal of the object can be hard coded or customizable. The customization can be carried in the type (like in unique_ptr) or not (using type elimination like in shared_ptr). When it comes to intrusive reference counting, disposal gets intrusive as well. The interface of the class must expose customizable disposal or should include creation (and loosing flexibility), otherwise creation and disposal are not adhered. A clear architectural flaw. It is your choice to leave hard-coded disposal, add custom disposal in the type (maybe as in unique_ptr [C++0x 20.9.9.1] or use CRTP and empty-base-optimization for disposal), or use type elimination (using the function class template).

Alternative Implementations

A base class is not the only possibility to develop a reusable reference counter. If a reference-counting class is added as a class member, it would necessitate some member functions to reach the counter and the two free functions had to be delivered separately. This is too demanding. Another possibility is to add reference counting by deriving from the foo class:

template <class Base>
class add_ref_counter : public Base {/*…*/};

and to use it like this:

intrusive_ptr<add_ref_counter<foo> > 
  p(new add_ref_counter<foo>());

A generic implementation of add_ref_counter would make use of C++0x variadic templates and perfect forwarding. The downside of such a technique would be a broken upcast in a class hierarchy, because it adds add_ref_counter-leaves. The intrusive_ptr object holds a pointer to a add_ref_counter<foo> object, but not to a foo object. Although a foo_child may be used as a foo, an add_ref_counter<foo_child> cannot be used as an add_ref_counter<foo>. On the other hand, this technique makes it possible to add reference counting and customized disposal to classes afterwards.

Results

Intrusive reference counting may be an efficient way to manage shared resources. I presented a way to implement a reusable and easy to apply base class. However, intrusive reference counting has its downsides. Its inflexible requirements force the managed object to hold the reference counter and to know something about disposal. This is a clear flaw, as it separates creation and disposal. Intrusive reference counting can be used only with classes designed this way. Finally, the interface of intrusive_ptr must be extended to provide thread safety. I prefer shared_ptr<X> px(CreateX(), DestroyX), adhering creation with disposal. X does not have to know anything about shared_ptr, creation or disposal. Additionally, the interface of shared_ptr features thread-safe functions. Finally, shared_ptr is part of the C++0x standard library. I recommend using shared_ptr for shared ownership and unique_ptr for strict ownership. Only if you can prove that intrusive_ptr solves problems that you have with shared_ptr should you revert to intrusive_ptr. Here is the definition of the ref_counter class template for single-threaded in C++03:

template <class Derived>
class ref_counter
{
public:
	friend void intrusive_ptr_add_ref(const Derived* p)
	{
		++((const ref_counter*) p)->counter_;
	}
	friend void intrusive_ptr_release(const Derived* p)
	{
		if (--((const ref_counter*) p)->counter_ == 0)
			delete p;
	}
protected:
	ref_counter(): counter_(0) {}
	ref_counter(const ref_counter&) : counter_(0) {}
	ref_counter& operator=(const ref_counter&) { return *this; }
	~ref_counter() {};
	void swap(ref_counter&) {};
private:
	mutable unsigned long counter_;
};

References

[C++03] ISO/IEC 14882:2003: "Programming Language C++," 2003, Wiley.

[C++0x] ISO/IEC Working Draft: "Standard for Programming Language C++," 2010, http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2010/n3225.pdf.

[BoostSmartPtr] Colvin, Dawes, Adler: "Boost smart pointers", http://www.boost.org/doc/libs/1_45_0/libs/smart_ptr/smart_ptr.htm.

[BoostIntrusive] Dimov: "Boost intrusive_ptr class template", http://www.boost.org/doc/libs/1_45_0/libs/smart_ptr/intrusive_ptr.html.

[C++Templates] Vandevoorde, Josuttis: "C++ Templates – The Complete Guide," 2003, Addison-Wesley Professional.

[Counting] Meyers: "Counting Objects in C++," 1998, http://www.drdobbs.com/184403484.

[EffectiveC++] Meyers: "Effective C++," 2nd ed., 1997, Addison-Wesley Professional.

[LSP] Martin: "The Liskov Substitution Principle," 1996, http://www.objectmentor.com/resources/articles/lsp.pdf.

[TMP] Abrahams, Gurtovoy: "C++ Template Metaprogramming," 2005, Addison-Wesley Professional.

[AtomicRCP] Reinholtz: "Atomic Reference Counting Pointers," 2004, http://www.drdobbs.com/184401888.

[N2674] Dimov, Dawes: "shared_ptr atomic access," revision 1, 2008, http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2674.htm.


Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 

Video