libstdc++-v3/docs/html/20_util/shared_ptr.html

   1 <?xml version="1.0" encoding="ISO-8859-1"?>
   2 <!DOCTYPE html
   3           PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
   4           "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
   5
   6 <html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
   7 <head>
   8    <meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1" />
   9    <meta name="KEYWORDS" content="HOWTO, libstdc++, GCC, g++, STL" />
  10    <meta name="DESCRIPTION" content="Notes on the shared_ptr implementation." />
  11    <title>Notes on the shared_ptr implementation.</title>
  12 <link rel="StyleSheet" href="../lib3styles.css" type="text/css" />
  13 <link rel="Start" href="../documentation.html" type="text/html"
  14   title="GNU C++ Standard Library" />
  15 <link rel="Bookmark" href="howto.html" type="text/html" title="General Utilities" />
  16 <link rel="Copyright" href="../17_intro/license.html" type="text/html" />
  17 <link rel="Help" href="../faq/index.html" type="text/html" title="F.A.Q." />
  18 </head>
  19 <body>
  20 <h1>
  21 Notes on the <code>shared_ptr</code> implementation.
  22 </h1>
  23 <em>
  24 prepared by Jonathan Wakely on November 11, 2007
  25 </em>
  26
  27 <h2>
  28 1. Abstract
  29 </h2>
  30 <p>
  31 The shared_ptr class template stores a pointer, usually obtained via new,
  32 and implements shared ownership semantics.
  33 </p>
  34
  35 <h2>
  36 2. What the standard says
  37 </h2>
  38
  39 <blockquote>
  40 20.6.6.2 - Class template shared_ptr [util.smartptr.shared]
  41 </blockquote>
  42
  43 <p>
  44 The standard deliberately doesn't require a reference-counted implementation,
  45 allowing other techniques such as a circular-linked-list.
  46 </p>
  47
  48 <p>
  49 At the time of writing the C++0x working paper doesn't mention how threads
  50 affect shared_ptr, but it is likely to follow the existing practice set by
  51 <code>boost::shared_ptr</code>.  The shared_ptr in libstdc++ is derived
  52 from Boost's, so the same rules apply.
  53 </p>
  54
  55 <h2>
  56 3. Problems with shared_ptr: TR1 vs C++0x, thread safety.
  57 </h2>
  58
  59 <p>
  60 The interface of <code>tr1::shared_ptr</code> was extended for C++0x with
  61 support for rvalue-references and the other features from N2351. As
  62 with other libstdc++ headers shared by TR1 and C++0x, boost_shared_ptr.h
  63 uses conditional compilation, based on the macros _GLIBCXX_INCLUDE_AS_CXX0X
  64 and _GLIBCXX_INCLUDE_AS_TR1, to enable and disable features.
  65 </p>
  66
  67 <p>
  68 C++0x-only features are: rvalue-ref/move support, allocator support,
  69 aliasing constructor, make_shared &amp; allocate_shared. Additionally, the
  70 constructors taking auto_ptr parameters are deprecated in C++0x mode.
  71 </p>
  72
  73 <p>
  74 The
  75 <a href="http://boost.org/libs/smart_ptr/shared_ptr.htm#ThreadSafety">Thread
  76 Safety</a> section of the Boost shared_ptr documentation says "shared_ptr
  77 objects offer the same level of thread safety as built-in types."
  78 The implementation must ensure that concurrent updates to separate shared_ptr
  79 instances are correct even when those instances share a reference count e.g.
  80 </p>
  81 <pre>
  82 shared_ptr&lt;A&gt; a(new A);
  83 shared_ptr&lt;A&gt; b(a);
  84
  85 // Thread 1     // Thread 2
  86    a.reset();      b.reset();
  87 </pre>
  88 <p>
  89 The dynamically-allocated object must be destroyed by exactly one of the
  90 threads. Weak references make things even more interesting.
  91 The shared state used to implement shared_ptr must be transparent to the
  92 user and invariants must be preserved at all times.
  93 The key pieces of shared state are the strong and weak reference counts.
  94 Updates to these need to be atomic and visible to all threads to ensure
  95 correct cleanup of the managed resource (which is, after all, shared_ptr's
  96 job!)
  97 On multi-processor systems memory synchronisation may be needed so that
  98 reference-count updates and the destruction of the managed resource are
  99 race-free.
 100 </p>
 101
 102 <p>
 103 The function <code>_Sp_counted_base::_M_add_ref_lock()</code>, called when
 104 obtaining a shared_ptr from a weak_ptr, has to test if the managed
 105 resource still exists and either increment the reference count or throw
 106 <code>std::bad_weak_ptr</code>.
 107 In a multi-threaded program there is a potential race condition if the last
 108 reference is dropped (and the managed resource destroyed) between testing
 109 the reference count and incrementing it, which could result in a shared_ptr
 110 pointing to invalid memory.
 111 </p>
 112 <p>
 113 The Boost shared_ptr (as used in GCC) features a clever lock-free algorithm
 114 to avoid the race condition, but this relies on the processor supporting
 115 an atomic <em>Compare-And-Swap</em> instruction. For other platforms there
 116 are fall-backs using mutex locks.  Boost (as of version 1.35) includes
 117 several different implementations and the preprocessor selects one based
 118 on the compiler, standard library, platform etc. For the version of
 119 shared_ptr in libstdc++ the compiler and library are fixed, which makes
 120 things much simpler: we have an atomic CAS or we don't, see Lock Policy
 121 below for details.
 122 </p>
 123
 124 <h2>
 125 4. Design and Implementation Details
 126 </h2>
 127
 128 <p>
 129 The shared_ptr code in libstdc++ was kindly donated to GCC by the Boost
 130 project and the original authors of the code. The basic design and
 131 algorithms are from Boost, the notes below describe details specific to
 132 the GCC implementation. Names have been uglified in this implementation,
 133 but the design should be recognisable to anyone familiar with the Boost
 134 1.32 shared_ptr.
 135 </p>
 136
 137 <p>
 138 The basic design is an abstract base class, <code>_Sp_counted_base</code> that
 139 does the reference-counting and calls virtual functions when the count
 140 drops to zero.
 141 Derived classes override those functions to destroy resources in a context
 142 where the correct dynamic type is known. This is an application of the
 143 technique known as type erasure.
 144 </p>
 145
 146 <h3>
 147 C++0x and TR1 Implementations
 148 </h3>
 149
 150 <p>
 151 The classes derived from <code>_Sp_counted_base</code> (see Class Hierarchy
 152 below) and <code>__shared_count</code> are implemented separately for C++0x
 153 and TR1, in <tt>bits/boost_sp_shared_count.h</tt> and
 154 <tt>tr1/boost_sp_shared_count.h</tt> respectively.  All other classes
 155 including <code>_Sp_counted_base</code> are shared by both implementations.
 156 </p>
 157
 158 <p>
 159 The TR1 implementation is considered relatively stable, so is unlikely to
 160 change unless bug fixes require it to.  If the code that is common to both
 161 C++0x and TR1 modes needs to diverge further then it might be necessary to
 162 duplicate additional classes and only make changes to the C++0x versions.
 163 </p>
 164
 165 <h3>
 166 Lock Policy
 167 </h3>
 168
 169 <p>
 170 Libstdc++ has a single <code>_Sp_counted_base</code> class, which is a
 171 template parameterized on the enum <code>__gnu_cxx::_Lock_policy</code>.
 172 The entire family of classes is parameterized on the lock policy, right up
 173 to <code>__shared_ptr</code>, <code>__weak_ptr</code> and
 174 <code>__enable_shared_from_this</code>. The actual
 175 <code>std::shared_ptr</code> class inherits from <code>__shared_ptr</code>
 176 with the lock policy parameter selected automatically based on the thread
 177 model and platform that libstdc++ is configured for, so that the best
 178 available template specialization will be used. This design is necessary
 179 because it would not be conforming for <code>std::shared_ptr</code> to have
 180 an extra template parameter, even if it had a default value.
 181 The available policies are:
 182 </p>
 183
 184 <dl>
 185 <dt><code>_S_Atomic</code></dt>
 186 <dd>
 187 Selected when GCC supports a builtin atomic compare-and-swap
 188 operation on the target processor (see
 189 <a href="http://gcc.gnu.org/onlinedocs/gcc/Atomic-Builtins.html">Atomic
 190 Builtins</a>.)
 191 The reference counts are maintained using a lock-free algorithm and GCC's
 192 atomic builtins, which provide the required memory synchronisation.
 193 </dd>
 194 <dt><code>_S_Mutex</code></dt>
 195 <dd>
 196 The _Sp_counted_base specialization for this policy contains a mutex,
 197 which is locked in add_ref_lock(). This policy is used when GCC's atomic
 198 builtins aren't available so explicit memory barriers are needed in places.
 199 </dd>
 200 <dt><code>_S_Single</code></dt>
 201 <dd>
 202 This policy uses a non-reentrant add_ref_lock() with no locking. It is
 203 used when libstdc++ is built without <em>--enable-threads</em>.
 204 </dd>
 205 </dl>
 206
 207 <p>
 208 For all three policies, reference count increments and decrements are done
 209 via the functions in <tt>&lt;ext/atomicity.h&gt;</tt>, which detect if the
 210 program is multi-threaded.
 211 If only one thread of execution exists in the program then less expensive
 212 non-atomic operations are used.
 213 </p>
 214
 215 <h3>
 216 Class Hierarchy
 217 </h3>
 218
 219 <p>
 220 A <code>shared_ptr&lt;T&gt;</code> contains a pointer of type <code>T*</code>
 221 and an object of type <code>__shared_count</code>. The shared_count contains
 222 a pointer of type <code>_Sp_counted_base*</code> which points to the object
 223 that maintains the reference-counts and destroys the managed resource.
 224 </p>
 225
 226 <dl>
 227 <dt><code>_Sp_counted_base&lt;Lp&gt;</code></dt>
 228 <dd>
 229 The base of the hierarchy is parameterized on the lock policy alone.
 230 _Sp_counted_base doesn't depend on the type of pointer being managed,
 231 it only maintains the reference counts and calls virtual functions when
 232 the counts drop to zero. The managed object is destroyed when the last
 233 strong reference is dropped, but the _Sp_counted_base itself must exist
 234 until the last weak reference is dropped.
 235 </dd>
 236 <dt><code>_Sp_counted_base_impl&lt;Ptr, Deleter, Lp&gt;</code></dt>
 237 <dd>
 238 Inherits from _Sp_counted_base and stores a pointer of type <code>Ptr</code>
 239 and a deleter of type <code>Deleter</code>.  <code>_Sp_deleter</code> is
 240 used when the user doesn't supply a custom deleter. Unlike Boost's, this
 241 default deleter is not "checked" because GCC already issues a warning if
 242 <code>delete</code> is used with an incomplete type.
 243 This is the only derived type used by <code>tr1::shared_ptr&lt;Ptr&gt;</code>
 244 and it is never used by <code>std::shared_ptr</code>, which uses one of
 245 the following types, depending on how the shared_ptr is constructed.
 246 </dd>
 247 <dt><code>_Sp_counted_ptr&lt;Ptr, Lp&gt;</code></dt>
 248 <dd>
 249 Inherits from _Sp_counted_base and stores a pointer of type <code>Ptr</code>,
 250 which is passed to <code>delete</code> when the last reference is dropped.
 251 This is the simplest form and is used when there is no custom deleter or
 252 allocator.
 253 </dd>
 254 <dt><code>_Sp_counted_deleter&lt;Ptr, Deleter, Alloc&gt;</code></dt>
 255 <dd>
 256 Inherits from _Sp_counted_ptr and adds support for custom deleter and
 257 allocator. Empty Base Optimization is used for the allocator. This class
 258 is used even when the user only provides a custom deleter, in which case
 259 <code>std::allocator</code> is used as the allocator.
 260 </dd>
 261 <dt><code>_Sp_counted_ptr_inplace&lt;Tp, Alloc, Lp&gt;</code></dt>
 262 <dd>
 263 Used by <code>allocate_shared</code> and <code>make_shared</code>.
 264 Contains aligned storage to hold an object of type <code>Tp</code>,
 265 which is constructed in-place with placement <code>new</code>.
 266 Has a variadic template constructor allowing any number of arguments to
 267 be forwarded to <code>Tp</code>'s constructor.
 268 Unlike the other _Sp_counted_* classes, this one is parameterized on the
 269 type of object, not the type of pointer; this is purely a convenience
 270 that simplifies the implementation slightly.
 271 </dd>
 272 </dl>
 273
 274 <h3>
 275 Related functions and classes
 276 </h3>
 277
 278 <dl>
 279 <dt><code>dynamic_pointer_cast</code>, <code>static_pointer_cast</code>,
 280 <code>const_pointer_cast</code></dt>
 281 <dd>
 282 As noted in N2351, these functions can be implemented non-intrusively using
 283 the alias constructor.  However the aliasing constructor is only available
 284 in C++0x mode, so in TR1 mode these casts rely on three non-standard
 285 constructors in shared_ptr and __shared_ptr.
 286 In C++0x mode these constructors and the related tag types are not needed.
 287 </dd>
 288 <dt><code>enable_shared_from_this</code></dt>
 289 <dd>
 290 The clever overload to detect a base class of type
 291 <code>enable_shared_from_this</code> comes straight from Boost.
 292 There is an extra overload for <code>__enable_shared_from_this</code> to
 293 work smoothly with <code>__shared_ptr&lt;Tp, Lp&gt;</code> using any lock
 294 policy.
 295 </dd>
 296 <dt><code>make_shared</code>, <code>allocate_shared</code></dt>
 297 <dd>
 298 <code>make_shared</code> simply forwards to <code>allocate_shared</code>
 299 with <code>std::allocator</code> as the allocator.
 300 Although these functions can be implemented non-intrusively using the
 301 alias constructor, if they have access to the implementation then it is
 302 possible to save storage and reduce the number of heap allocations. The
 303 newly constructed object and the _Sp_counted_* can be allocated in a single
 304 block and the standard says implementations are "encouraged, but not required,"
 305 to do so. This implementation provides additional non-standard constructors
 306 (selected with the type <code>_Sp_make_shared_tag</code>) which create an
 307 object of type <code>_Sp_counted_ptr_inplace</code> to hold the new object.
 308 The returned <code>shared_ptr&lt;A&gt;</code> needs to know the address of the
 309 new <code>A</code> object embedded in the <code>_Sp_counted_ptr_inplace</code>,
 310 but it has no way to access it.
 311 This implementation uses a "covert channel" to return the address of the
 312 embedded object when <code>get_deleter&lt;_Sp_make_shared_tag&gt;()</code>
 313 is called.  Users should not try to use this.
 314 As well as the extra constructors, this implementation also needs some
 315 members of _Sp_counted_deleter to be protected where they could otherwise
 316 be private.
 317 </dd>
 318 </dl>
 319
 320 <h2>
 321 5. Examples
 322 </h2>
 323
 324 <p>
 325 Examples of use can be found in the testsuite, under
 326 <tt>testsuite/tr1/2_general_utilities/shared_ptr</tt>.
 327 </p>
 328
 329 <h2>
 330 6. Unresolved Issues
 331 </h2>
 332
 333 <p>
 334 The resolution to C++ Standard Library issue <a
 335 href="http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-active.html#674">674</a>,
 336 "shared_ptr interface changes for consistency with N1856" will need to be
 337 implemented after it is accepted into the working paper. Issue <a
 338 href="http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-active.html#743">743</a>
 339 might also require changes.
 340 </p>
 341
 342 <p>
 343 The _S_single policy uses atomics when used in MT code, because it uses
 344 the same dispatcher functions that check __gthread_active_p(). This could be
 345 addressed by providing template specialisations for some members of
 346 _Sp_counted_base&lt;_S_single&gt;.
 347 </p>
 348
 349 <p>
 350 Unlike Boost, this implementation does not use separate classes for the
 351 pointer+deleter and pointer+deleter+allocator cases in C++0x mode, combining
 352 both into _Sp_counted_deleter and using std::allocator when the user doesn't
 353 specify an allocator.
 354 If it was found to be beneficial an additional class could easily be added.
 355 With the current implementation, the _Sp_counted_deleter and __shared_count
 356 constructors taking a custom deleter but no allocator are technically
 357 redundant and could be removed, changing callers to always specify an
 358 allocator. If a separate pointer+deleter class was added the __shared_count
 359 constructor would be needed, so it has been kept for now.
 360 </p>
 361
 362 <p>
 363 The hack used to get the address of the managed object from
 364 _Sp_counted_ptr_inplace::_M_get_deleter() is accessible to users. This
 365 could be prevented if get_deleter&lt;_Sp_make_shared_tag&gt;() always
 366 returned NULL, since the hack only needs to work at a lower level, not
 367 in the public API. This wouldn't be difficult, but hasn't been done since
 368 there is no danger of accidental misuse: users already know they are
 369 relying on unsupported features if they refer to implementation details
 370 such as _Sp_make_shared_tag.
 371 </p>
 372
 373 <p>
 374 tr1::_Sp_deleter could be a private member of tr1::__shared_count but it
 375 would alter the ABI.
 376 </p>
 377
 378 <p>
 379 Exposing the alias constructor in TR1 mode could simplify the *_pointer_cast
 380 functions.
 381 Constructor could be private in TR1 mode, with the cast functions as friends.
 382 </p>
 383
 384 <h2>
 385 7. Acknowledgments
 386 </h2>
 387 <p>
 388 The original authors of the Boost shared_ptr, which is really nice code
 389 to work with, Peter Dimov in particular for his help and invaluable advice
 390 on thread safety.
 391 Phillip Jordan and Paolo Carlini for the lock policy implementation.
 392 </p>
 393
 394
 395 <h2>
 396 8. Bibliography / Referenced Documents
 397 </h2>
 398
 399 <p>
 400 N2351 Improving shared_ptr for C++0x, Revision 2
 401 <a href="http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2351.htm">http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2351.htm</a>
 402 </p>
 403
 404 <p>
 405 N2456 C++ Standard Library Active Issues List (Revision R52)
 406 <a href="http://open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2456.html">http://open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2456.html</a></p>
 407 <p>
 408 N2461 Working Draft, Standard for Programming Language C++
 409 <a href="http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2461.pdf">http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2461.pdf</a>
 410 </p>
 411
 412 <p>
 413 Boost C++ Libraries documentation - shared_ptr class template
 414 <a href="http://boost.org/libs/smart_ptr/shared_ptr.htm">http://boost.org/libs/smart_ptr/shared_ptr.htm</a>
 415 </p>
 416
 417 </body>
 418 </html>
 419