1<?xml version="1.0" encoding="UTF-8" standalone="no"?> 2<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"><html xmlns="http://www.w3.org/1999/xhtml"><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8" /><title>Memory</title><meta name="generator" content="DocBook XSL Stylesheets Vsnapshot" /><meta name="keywords" content="ISO C++, library" /><meta name="keywords" content="ISO C++, runtime, library" /><link rel="home" href="../index.html" title="The GNU C++ Library" /><link rel="up" href="utilities.html" title="Chapter��6.�� Utilities" /><link rel="prev" href="pairs.html" title="Pairs" /><link rel="next" href="traits.html" title="Traits" /></head><body><div class="navheader"><table width="100%" summary="Navigation header"><tr><th colspan="3" align="center">Memory</th></tr><tr><td width="20%" align="left"><a accesskey="p" href="pairs.html">Prev</a>��</td><th width="60%" align="center">Chapter��6.�� 3 Utilities 4 5</th><td width="20%" align="right">��<a accesskey="n" href="traits.html">Next</a></td></tr></table><hr /></div><div class="section"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a id="std.util.memory"></a>Memory</h2></div></div></div><p> 6 Memory contains three general areas. First, function and operator 7 calls via <code class="function">new</code> and <code class="function">delete</code> 8 operator or member function calls. Second, allocation via 9 <code class="classname">allocator</code>. And finally, smart pointer and 10 intelligent pointer abstractions. 11 </p><div class="section"><div class="titlepage"><div><div><h3 class="title"><a id="std.util.memory.allocator"></a>Allocators</h3></div></div></div><p> 12 Memory management for Standard Library entities is encapsulated in a 13 class template called <code class="classname">allocator</code>. The 14 <code class="classname">allocator</code> abstraction is used throughout the 15 library in <code class="classname">string</code>, container classes, 16 algorithms, and parts of iostreams. This class, and base classes of 17 it, are the superset of available free store (<span class="quote">���<span class="quote">heap</span>���</span>) 18 management classes. 19</p><div class="section"><div class="titlepage"><div><div><h4 class="title"><a id="allocator.req"></a>Requirements</h4></div></div></div><p> 20 The C++ standard only gives a few directives in this area: 21 </p><div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "><li class="listitem"><p> 22 When you add elements to a container, and the container must 23 allocate more memory to hold them, the container makes the 24 request via its <span class="type">Allocator</span> template 25 parameter, which is usually aliased to 26 <span class="type">allocator_type</span>. This includes adding chars 27 to the string class, which acts as a regular STL container in 28 this respect. 29 </p></li><li class="listitem"><p> 30 The default <span class="type">Allocator</span> argument of every 31 container-of-T is <code class="classname">allocator<T></code>. 32 </p></li><li class="listitem"><p> 33 The interface of the <code class="classname">allocator<T></code> class is 34 extremely simple. It has about 20 public declarations (nested 35 typedefs, member functions, etc), but the two which concern us most 36 are: 37 </p><pre class="programlisting"> 38 T* allocate (size_type n, const void* hint = 0); 39 void deallocate (T* p, size_type n); 40 </pre><p> 41 The <code class="varname">n</code> arguments in both those 42 functions is a <span class="emphasis"><em>count</em></span> of the number of 43 <span class="type">T</span>'s to allocate space for, <span class="emphasis"><em>not their 44 total size</em></span>. 45 (This is a simplification; the real signatures use nested typedefs.) 46 </p></li><li class="listitem"><p> 47 The storage is obtained by calling <code class="function">::operator 48 new</code>, but it is unspecified when or how 49 often this function is called. The use of the 50 <code class="varname">hint</code> is unspecified, but intended as an 51 aid to locality if an implementation so 52 desires. <code class="constant">[20.4.1.1]/6</code> 53 </p></li></ul></div><p> 54 Complete details can be found in the C++ standard, look in 55 <code class="constant">[20.4 Memory]</code>. 56 </p></div><div class="section"><div class="titlepage"><div><div><h4 class="title"><a id="allocator.design_issues"></a>Design Issues</h4></div></div></div><p> 57 The easiest way of fulfilling the requirements is to call 58 <code class="function">operator new</code> each time a container needs 59 memory, and to call <code class="function">operator delete</code> each time 60 the container releases memory. This method may be <a class="link" href="http://gcc.gnu.org/ml/libstdc++/2001-05/msg00105.html" target="_top">slower</a> 61 than caching the allocations and re-using previously-allocated 62 memory, but has the advantage of working correctly across a wide 63 variety of hardware and operating systems, including large 64 clusters. The <code class="classname">__gnu_cxx::new_allocator</code> 65 implements the simple operator new and operator delete semantics, 66 while <code class="classname">__gnu_cxx::malloc_allocator</code> 67 implements much the same thing, only with the C language functions 68 <code class="function">std::malloc</code> and <code class="function">std::free</code>. 69 </p><p> 70 Another approach is to use intelligence within the allocator 71 class to cache allocations. This extra machinery can take a variety 72 of forms: a bitmap index, an index into an exponentially increasing 73 power-of-two-sized buckets, or simpler fixed-size pooling cache. 74 The cache is shared among all the containers in the program: when 75 your program's <code class="classname">std::vector<int></code> gets 76 cut in half and frees a bunch of its storage, that memory can be 77 reused by the private 78 <code class="classname">std::list<WonkyWidget></code> brought in from 79 a KDE library that you linked against. And operators 80 <code class="function">new</code> and <code class="function">delete</code> are not 81 always called to pass the memory on, either, which is a speed 82 bonus. Examples of allocators that use these techniques are 83 <code class="classname">__gnu_cxx::bitmap_allocator</code>, 84 <code class="classname">__gnu_cxx::pool_allocator</code>, and 85 <code class="classname">__gnu_cxx::__mt_alloc</code>. 86 </p><p> 87 Depending on the implementation techniques used, the underlying 88 operating system, and compilation environment, scaling caching 89 allocators can be tricky. In particular, order-of-destruction and 90 order-of-creation for memory pools may be difficult to pin down 91 with certainty, which may create problems when used with plugins 92 or loading and unloading shared objects in memory. As such, using 93 caching allocators on systems that do not support 94 <code class="function">abi::__cxa_atexit</code> is not recommended. 95 </p></div><div class="section"><div class="titlepage"><div><div><h4 class="title"><a id="allocator.impl"></a>Implementation</h4></div></div></div><div class="section"><div class="titlepage"><div><div><h5 class="title"><a id="allocator.interface"></a>Interface Design</h5></div></div></div><p> 96 The only allocator interface that 97 is supported is the standard C++ interface. As such, all STL 98 containers have been adjusted, and all external allocators have 99 been modified to support this change. 100 </p><p> 101 The class <code class="classname">allocator</code> just has typedef, 102 constructor, and rebind members. It inherits from one of the 103 high-speed extension allocators, covered below. Thus, all 104 allocation and deallocation depends on the base class. 105 </p><p> 106 The choice of base class that <code class="classname">allocator</code> 107 is derived from is fixed at the time when GCC is built, 108 and the different choices are not ABI compatible. 109</p></div><div class="section"><div class="titlepage"><div><div><h5 class="title"><a id="allocator.default"></a>Selecting Default Allocation Policy</h5></div></div></div><p> 110 It's difficult to pick an allocation strategy that will provide 111 maximum utility, without excessively penalizing some behavior. In 112 fact, it's difficult just deciding which typical actions to measure 113 for speed. 114 </p><p> 115 Three synthetic benchmarks have been created that provide data 116 that is used to compare different C++ allocators. These tests are: 117 </p><div class="orderedlist"><ol class="orderedlist" type="1"><li class="listitem"><p> 118 Insertion. 119 </p><p> 120 Over multiple iterations, various STL container 121 objects have elements inserted to some maximum amount. A variety 122 of allocators are tested. 123 Test source for <a class="link" href="http://gcc.gnu.org/viewcvs/gcc/trunk/libstdc%2B%2B-v3/testsuite/performance/23_containers/insert/sequence.cc?view=markup" target="_top">sequence</a> 124 and <a class="link" href="http://gcc.gnu.org/viewcvs/gcc/trunk/libstdc%2B%2B-v3/testsuite/performance/23_containers/insert/associative.cc?view=markup" target="_top">associative</a> 125 containers. 126 </p></li><li class="listitem"><p> 127 Insertion and erasure in a multi-threaded environment. 128 </p><p> 129 This test shows the ability of the allocator to reclaim memory 130 on a per-thread basis, as well as measuring thread contention 131 for memory resources. 132 Test source 133 <a class="link" href="http://gcc.gnu.org/viewcvs/gcc/trunk/libstdc%2B%2B-v3/testsuite/performance/23_containers/insert_erase/associative.cc?view=markup" target="_top">here</a>. 134 </p></li><li class="listitem"><p> 135 A threaded producer/consumer model. 136 </p><p> 137 Test source for 138 <a class="link" href="http://gcc.gnu.org/viewcvs/gcc/trunk/libstdc++-v3/testsuite/performance/23_containers/producer_consumer/sequence.cc?view=markup" target="_top">sequence</a> 139 and 140 <a class="link" href="http://gcc.gnu.org/viewcvs/gcc/trunk/libstdc++-v3/testsuite/performance/23_containers/producer_consumer/associative.cc?view=markup" target="_top">associative</a> 141 containers. 142 </p></li></ol></div><p> 143 Since GCC 12 the default choice for 144 <code class="classname">allocator</code> is 145 <code class="classname">std::__new_allocator</code>. 146 Before GCC 12 it was the <code class="classname">__gnu_cxx::new_allocator</code> 147 extension (which has identical behaviour). 148 </p></div><div class="section"><div class="titlepage"><div><div><h5 class="title"><a id="allocator.caching"></a>Disabling Memory Caching</h5></div></div></div><p> 149 In use, <code class="classname">allocator</code> may allocate and 150 deallocate using implementation-specific strategies and 151 heuristics. Because of this, a given call to an allocator object's 152 <code class="function">allocate</code> member function may not actually 153 call the global <code class="code">operator new</code> and a given call to 154 to the <code class="function">deallocate</code> member function may not 155 call <code class="code">operator delete</code>. 156 </p><p> 157 This can be confusing. 158 </p><p> 159 In particular, this can make debugging memory errors more 160 difficult, especially when using third-party tools like valgrind or 161 debug versions of <code class="function">new</code>. 162 </p><p> 163 There are various ways to solve this problem. One would be to use 164 a custom allocator that just called operators 165 <code class="function">new</code> and <code class="function">delete</code> 166 directly, for every allocation. (See the default allocator, 167 <code class="filename">include/ext/new_allocator.h</code>, for instance.) 168 However, that option may involve changing source code to use 169 a non-default allocator. Another option is to force the 170 default allocator to remove caching and pools, and to directly 171 allocate with every call of <code class="function">allocate</code> and 172 directly deallocate with every call of 173 <code class="function">deallocate</code>, regardless of efficiency. As it 174 turns out, this last option is also available. 175 </p><p> 176 To globally disable memory caching within the library for some of 177 the optional non-default allocators, merely set 178 <code class="constant">GLIBCXX_FORCE_NEW</code> (with any value) in the 179 system's environment before running the program. If your program 180 crashes with <code class="constant">GLIBCXX_FORCE_NEW</code> in the 181 environment, it likely means that you linked against objects 182 built against the older library (objects which might still using the 183 cached allocations...). 184 </p></div></div><div class="section"><div class="titlepage"><div><div><h4 class="title"><a id="allocator.using"></a>Using a Specific Allocator</h4></div></div></div><p> 185 You can specify different memory management schemes on a 186 per-container basis, by overriding the default 187 <span class="type">Allocator</span> template parameter. For example, an easy 188 (but non-portable) method of specifying that only <code class="function">malloc</code> or <code class="function">free</code> 189 should be used instead of the default node allocator is: 190 </p><pre class="programlisting"> 191 std::list <int, __gnu_cxx::malloc_allocator<int> > malloc_list;</pre><p> 192 Likewise, a debugging form of whichever allocator is currently in use: 193 </p><pre class="programlisting"> 194 std::deque <int, __gnu_cxx::debug_allocator<std::allocator<int> > > debug_deque; 195 </pre></div><div class="section"><div class="titlepage"><div><div><h4 class="title"><a id="allocator.custom"></a>Custom Allocators</h4></div></div></div><p> 196 Writing a portable C++ allocator would dictate that the interface 197 would look much like the one specified for 198 <code class="classname">allocator</code>. Additional member functions, but 199 not subtractions, would be permissible. 200 </p><p> 201 Probably the best place to start would be to copy one of the 202 extension allocators: say a simple one like 203 <code class="classname">new_allocator</code>. 204 </p><p> 205 Since C++11 the minimal interface require for an allocator is 206 much smaller, as <code class="classname">std::allocator_traits</code> 207 can provide default for much of the interface. 208 </p></div><div class="section"><div class="titlepage"><div><div><h4 class="title"><a id="allocator.ext"></a>Extension Allocators</h4></div></div></div><p> 209 Several other allocators are provided as part of this 210 implementation. The location of the extension allocators and their 211 names have changed, but in all cases, functionality is 212 equivalent. Starting with gcc-3.4, all extension allocators are 213 standard style. Before this point, SGI style was the norm. Because of 214 this, the number of template arguments also changed. 215 <a class="xref" href="api.html#table.extension_allocators" title="Table��B.6.��Extension Allocators">Table��B.6, ���Extension Allocators���</a> tracks the changes. 216 </p><p> 217 More details on each of these extension allocators follows. 218 </p><div class="orderedlist"><ol class="orderedlist" type="1"><li class="listitem"><p> 219 <code class="classname">new_allocator</code> 220 </p><p> 221 Simply wraps <code class="function">::operator new</code> 222 and <code class="function">::operator delete</code>. 223 </p></li><li class="listitem"><p> 224 <code class="classname">malloc_allocator</code> 225 </p><p> 226 Simply wraps <code class="function">malloc</code> and 227 <code class="function">free</code>. There is also a hook for an 228 out-of-memory handler (for 229 <code class="function">new</code>/<code class="function">delete</code> this is 230 taken care of elsewhere). 231 </p></li><li class="listitem"><p> 232 <code class="classname">debug_allocator</code> 233 </p><p> 234 A wrapper around an arbitrary allocator <code class="classname">A</code>. 235 It passes on slightly increased size requests to <code class="classname">A</code>, 236 and uses the extra memory to store size information. 237 When a pointer is passed 238 to <code class="function">deallocate()</code>, the stored size is 239 checked, and <code class="function">assert()</code> is used to 240 guarantee they match. 241 </p></li><li class="listitem"><p> 242 <code class="classname">throw_allocator</code> 243 </p><p> 244 Includes memory tracking and marking abilities as well as hooks for 245 throwing exceptions at configurable intervals (including random, 246 all, none). 247 </p></li><li class="listitem"><p> 248 <code class="classname">__pool_alloc</code> 249 </p><p> 250 A high-performance, single pool allocator. The reusable 251 memory is shared among identical instantiations of this type. 252 It calls through <code class="function">::operator new</code> to 253 obtain new memory when its lists run out. If a client 254 container requests a block larger than a certain threshold 255 size, then the pool is bypassed, and the allocate/deallocate 256 request is passed to <code class="function">::operator new</code> 257 directly. 258 </p><p> 259 For thread-enabled configurations, the pool is locked with a 260 single big lock. In some situations, this implementation detail 261 may result in severe performance degradation. 262 </p><p> 263 (Note that the GCC thread abstraction layer allows us to provide 264 safe zero-overhead stubs for the threading routines, if threads 265 were disabled at configuration time.) 266 </p></li><li class="listitem"><p> 267 <code class="classname">__mt_alloc</code> 268 </p><p> 269 A high-performance fixed-size allocator with 270 exponentially-increasing allocations. It has its own 271 <a class="link" href="mt_allocator.html" title="Chapter��19.��The mt_allocator">chapter</a> 272 in the documentation. 273 </p></li><li class="listitem"><p> 274 <code class="classname">bitmap_allocator</code> 275 </p><p> 276 A high-performance allocator that uses a bit-map to keep track 277 of the used and unused memory locations. It has its own 278 <a class="link" href="bitmap_allocator.html" title="Chapter��20.��The bitmap_allocator">chapter</a> 279 in the documentation. 280 </p></li></ol></div></div><div class="bibliography"><div class="titlepage"><div><div><h4 class="title"><a id="allocator.biblio"></a>Bibliography</h4></div></div></div><div class="biblioentry"><a id="id-1.3.4.4.4.3.9.2"></a><p><span class="citetitle"><em class="citetitle"> 281 ISO/IEC 14882:1998 Programming languages - C++ 282 </em>. </span> 283 isoc++_1998 284 <span class="pagenums">20.4 Memory. </span></p></div><div class="biblioentry"><a id="id-1.3.4.4.4.3.9.3"></a><p><span class="title"><em> 285 <a class="link" href="https://web.archive.org/web/20190622154249/http://www.drdobbs.com/the-standard-librarian-what-are-allocato/184403759" target="_top"> 286 The Standard Librarian: What Are Allocators Good For? 287 </a> 288 </em>. </span><span class="author"><span class="firstname">Matt</span> <span class="surname">Austern</span>. </span><span class="publisher"><span class="publishername"> 289 C/C++ Users Journal 290 . </span></span><span class="pubdate">2000-12. </span></p></div><div class="biblioentry"><a id="id-1.3.4.4.4.3.9.4"></a><p><span class="title"><em> 291 <a class="link" href="http://hoard.org" target="_top"> 292 The Hoard Memory Allocator 293 </a> 294 </em>. </span><span class="author"><span class="firstname">Emery</span> <span class="surname">Berger</span>. </span></p></div><div class="biblioentry"><a id="id-1.3.4.4.4.3.9.5"></a><p><span class="title"><em> 295 <a class="link" href="https://people.cs.umass.edu/~emery/pubs/berger-oopsla2002.pdf" target="_top"> 296 Reconsidering Custom Memory Allocation 297 </a> 298 </em>. </span><span class="author"><span class="firstname">Emery</span> <span class="surname">Berger</span>. </span><span class="author"><span class="firstname">Ben</span> <span class="surname">Zorn</span>. </span><span class="author"><span class="firstname">Kathryn</span> <span class="surname">McKinley</span>. </span><span class="copyright">Copyright �� 2002 OOPSLA. </span></p></div><div class="biblioentry"><a id="id-1.3.4.4.4.3.9.6"></a><p><span class="title"><em> 299 <a class="link" href="http://www.angelikalanger.com/Articles/C++Report/Allocators/Allocators.html" target="_top"> 300 Allocator Types 301 </a> 302 </em>. </span><span class="author"><span class="firstname">Klaus</span> <span class="surname">Kreft</span>. </span><span class="author"><span class="firstname">Angelika</span> <span class="surname">Langer</span>. </span><span class="publisher"><span class="publishername"> 303 C/C++ Users Journal 304 . </span></span></p></div><div class="biblioentry"><a id="id-1.3.4.4.4.3.9.7"></a><p><span class="citetitle"><em class="citetitle">The C++ Programming Language</em>. </span><span class="author"><span class="firstname">Bjarne</span> <span class="surname">Stroustrup</span>. </span><span class="copyright">Copyright �� 2000 . </span><span class="pagenums">19.4 Allocators. </span><span class="publisher"><span class="publishername"> 305 Addison Wesley 306 . </span></span></p></div><div class="biblioentry"><a id="id-1.3.4.4.4.3.9.8"></a><p><span class="citetitle"><em class="citetitle">Yalloc: A Recycling C++ Allocator</em>. </span><span class="author"><span class="firstname">Felix</span> <span class="surname">Yen</span>. </span></p></div></div></div><div class="section"><div class="titlepage"><div><div><h3 class="title"><a id="std.util.memory.auto_ptr"></a>auto_ptr</h3></div></div></div><div class="section"><div class="titlepage"><div><div><h4 class="title"><a id="auto_ptr.limitations"></a>Limitations</h4></div></div></div><p>Explaining all of the fun and delicious things that can 307 happen with misuse of the <code class="classname">auto_ptr</code> class 308 template (called <acronym class="acronym">AP</acronym> here) would take some 309 time. Suffice it to say that the use of <acronym class="acronym">AP</acronym> 310 safely in the presence of copying has some subtleties. 311 </p><p> 312 The AP class is a really 313 nifty idea for a smart pointer, but it is one of the dumbest of 314 all the smart pointers -- and that's fine. 315 </p><p> 316 AP is not meant to be a supersmart solution to all resource 317 leaks everywhere. Neither is it meant to be an effective form 318 of garbage collection (although it can help, a little bit). 319 And it can <span class="emphasis"><em>not</em></span>be used for arrays! 320 </p><p> 321 <acronym class="acronym">AP</acronym> is meant to prevent nasty leaks in the 322 presence of exceptions. That's <span class="emphasis"><em>all</em></span>. This 323 code is AP-friendly: 324 </p><pre class="programlisting"> 325 // Not a recommend naming scheme, but good for web-based FAQs. 326 typedef std::auto_ptr<MyClass> APMC; 327 328 extern function_taking_MyClass_pointer (MyClass*); 329 extern some_throwable_function (); 330 331 void func (int data) 332 { 333 APMC ap (new MyClass(data)); 334 335 some_throwable_function(); // this will throw an exception 336 337 function_taking_MyClass_pointer (ap.get()); 338 } 339 </pre><p>When an exception gets thrown, the instance of MyClass that's 340 been created on the heap will be <code class="function">delete</code>'d as the stack is 341 unwound past <code class="function">func()</code>. 342 </p><p>Changing that code as follows is not <acronym class="acronym">AP</acronym>-friendly: 343 </p><pre class="programlisting"> 344 APMC ap (new MyClass[22]); 345 </pre><p>You will get the same problems as you would without the use 346 of <acronym class="acronym">AP</acronym>: 347 </p><pre class="programlisting"> 348 char* array = new char[10]; // array new... 349 ... 350 delete array; // ...but single-object delete 351 </pre><p> 352 AP cannot tell whether the pointer you've passed at creation points 353 to one or many things. If it points to many things, you are about 354 to die. AP is trivial to write, however, so you could write your 355 own <code class="code">auto_array_ptr</code> for that situation (in fact, this has 356 been done many times; check the mailing lists, Usenet, Boost, etc). 357 </p></div><div class="section"><div class="titlepage"><div><div><h4 class="title"><a id="auto_ptr.using"></a>Use in Containers</h4></div></div></div><p> 358 </p><p>All of the <a class="link" href="containers.html" title="Chapter��9.�� Containers">containers</a> 359 described in the standard library require their contained types 360 to have, among other things, a copy constructor like this: 361 </p><pre class="programlisting"> 362 struct My_Type 363 { 364 My_Type (My_Type const&); 365 }; 366 </pre><p> 367 Note the const keyword; the object being copied shouldn't change. 368 The template class <code class="code">auto_ptr</code> (called AP here) does not 369 meet this requirement. Creating a new AP by copying an existing 370 one transfers ownership of the pointed-to object, which means that 371 the AP being copied must change, which in turn means that the 372 copy ctors of AP do not take const objects. 373 </p><p> 374 The resulting rule is simple: <span class="emphasis"><em>Never ever use a 375 container of auto_ptr objects</em></span>. The standard says that 376 <span class="quote">���<span class="quote">undefined</span>���</span> behavior is the result, but it is 377 guaranteed to be messy. 378 </p><p> 379 To prevent you from doing this to yourself, the 380 <a class="link" href="ext_compile_checks.html" title="Chapter��16.��Compile Time Checks">concept checks</a> built 381 in to this implementation will issue an error if you try to 382 compile code like this: 383 </p><pre class="programlisting"> 384 #include <vector> 385 #include <memory> 386 387 void f() 388 { 389 std::vector< std::auto_ptr<int> > vec_ap_int; 390 } 391 </pre><p> 392Should you try this with the checks enabled, you will see an error. 393 </p></div></div><div class="section"><div class="titlepage"><div><div><h3 class="title"><a id="std.util.memory.shared_ptr"></a>shared_ptr</h3></div></div></div><p> 394The shared_ptr class template stores a pointer, usually obtained via new, 395and implements shared ownership semantics. 396</p><div class="section"><div class="titlepage"><div><div><h4 class="title"><a id="shared_ptr.req"></a>Requirements</h4></div></div></div><p> 397 </p><p> 398 The standard deliberately doesn't require a reference-counted 399 implementation, allowing other techniques such as a 400 circular-linked-list. 401 </p><p> 402 </p></div><div class="section"><div class="titlepage"><div><div><h4 class="title"><a id="shared_ptr.design_issues"></a>Design Issues</h4></div></div></div><p> 403The <code class="classname">shared_ptr</code> code is kindly donated to GCC by the Boost 404project and the original authors of the code. The basic design and 405algorithms are from Boost, the notes below describe details specific to 406the GCC implementation. Names have been uglified in this implementation, 407but the design should be recognisable to anyone familiar with the Boost 4081.32 shared_ptr. 409 </p><p> 410The basic design is an abstract base class, <code class="code">_Sp_counted_base</code> that 411does the reference-counting and calls virtual functions when the count 412drops to zero. 413Derived classes override those functions to destroy resources in a context 414where the correct dynamic type is known. This is an application of the 415technique known as type erasure. 416 </p></div><div class="section"><div class="titlepage"><div><div><h4 class="title"><a id="shared_ptr.impl"></a>Implementation</h4></div></div></div><div class="section"><div class="titlepage"><div><div><h5 class="title"><a id="shared_ptr.hier"></a>Class Hierarchy</h5></div></div></div><p> 417A <code class="classname">shared_ptr<T></code> contains a pointer of 418type <span class="type">T*</span> and an object of type 419<code class="classname">__shared_count</code>. The shared_count contains a 420pointer of type <span class="type">_Sp_counted_base*</span> which points to the 421object that maintains the reference-counts and destroys the managed 422resource. 423 </p><div class="variablelist"><dl class="variablelist"><dt><span class="term"><code class="classname">_Sp_counted_base<Lp></code></span></dt><dd><p> 424The base of the hierarchy is parameterized on the lock policy (see below.) 425_Sp_counted_base doesn't depend on the type of pointer being managed, 426it only maintains the reference counts and calls virtual functions when 427the counts drop to zero. The managed object is destroyed when the last 428strong reference is dropped, but the _Sp_counted_base itself must exist 429until the last weak reference is dropped. 430 </p></dd><dt><span class="term"><code class="classname">_Sp_counted_base_impl<Ptr, Deleter, Lp></code></span></dt><dd><p> 431Inherits from _Sp_counted_base and stores a pointer of type <code class="code">Ptr</code> 432and a deleter of type <code class="code">Deleter</code>. <code class="classname">_Sp_deleter</code> is 433used when the user doesn't supply a custom deleter. Unlike Boost's, this 434default deleter is not "checked" because GCC already issues a warning if 435<code class="function">delete</code> is used with an incomplete type. 436This is the only derived type used by <code class="classname">tr1::shared_ptr<Ptr></code> 437and it is never used by <code class="classname">std::shared_ptr</code>, which uses one of 438the following types, depending on how the shared_ptr is constructed. 439 </p></dd><dt><span class="term"><code class="classname">_Sp_counted_ptr<Ptr, Lp></code></span></dt><dd><p> 440Inherits from _Sp_counted_base and stores a pointer of type <span class="type">Ptr</span>, 441which is passed to <code class="function">delete</code> when the last reference is dropped. 442This is the simplest form and is used when there is no custom deleter or 443allocator. 444 </p></dd><dt><span class="term"><code class="classname">_Sp_counted_deleter<Ptr, Deleter, Alloc></code></span></dt><dd><p> 445Inherits from _Sp_counted_ptr and adds support for custom deleter and 446allocator. Empty Base Optimization is used for the allocator. This class 447is used even when the user only provides a custom deleter, in which case 448<code class="classname">allocator</code> is used as the allocator. 449 </p></dd><dt><span class="term"><code class="classname">_Sp_counted_ptr_inplace<Tp, Alloc, Lp></code></span></dt><dd><p> 450Used by <code class="code">allocate_shared</code> and <code class="code">make_shared</code>. 451Contains aligned storage to hold an object of type <span class="type">Tp</span>, 452which is constructed in-place with placement <code class="function">new</code>. 453Has a variadic template constructor allowing any number of arguments to 454be forwarded to <span class="type">Tp</span>'s constructor. 455Unlike the other <code class="classname">_Sp_counted_*</code> classes, this one is parameterized on the 456type of object, not the type of pointer; this is purely a convenience 457that simplifies the implementation slightly. 458 </p></dd></dl></div><p> 459C++11-only features are: rvalue-ref/move support, allocator support, 460aliasing constructor, make_shared & allocate_shared. Additionally, 461the constructors taking <code class="classname">auto_ptr</code> parameters are 462deprecated in C++11 mode. 463 </p></div><div class="section"><div class="titlepage"><div><div><h5 class="title"><a id="shared_ptr.thread"></a>Thread Safety</h5></div></div></div><p> 464The 465<a class="link" href="http://www.boost.org/libs/smart_ptr/shared_ptr.htm#ThreadSafety" target="_top">Thread 466Safety</a> section of the Boost shared_ptr documentation says "shared_ptr 467objects offer the same level of thread safety as built-in types." 468The implementation must ensure that concurrent updates to separate shared_ptr 469instances are correct even when those instances share a reference count e.g. 470</p><pre class="programlisting"> 471shared_ptr<A> a(new A); 472shared_ptr<A> b(a); 473 474// Thread 1 // Thread 2 475 a.reset(); b.reset(); 476</pre><p> 477The dynamically-allocated object must be destroyed by exactly one of the 478threads. Weak references make things even more interesting. 479The shared state used to implement shared_ptr must be transparent to the 480user and invariants must be preserved at all times. 481The key pieces of shared state are the strong and weak reference counts. 482Updates to these need to be atomic and visible to all threads to ensure 483correct cleanup of the managed resource (which is, after all, shared_ptr's 484job!) 485On multi-processor systems memory synchronisation may be needed so that 486reference-count updates and the destruction of the managed resource are 487race-free. 488</p><p> 489The function <code class="function">_Sp_counted_base::_M_add_ref_lock()</code>, called when 490obtaining a shared_ptr from a weak_ptr, has to test if the managed 491resource still exists and either increment the reference count or throw 492<code class="classname">bad_weak_ptr</code>. 493In a multi-threaded program there is a potential race condition if the last 494reference is dropped (and the managed resource destroyed) between testing 495the reference count and incrementing it, which could result in a shared_ptr 496pointing to invalid memory. 497</p><p> 498The Boost shared_ptr (as used in GCC) features a clever lock-free 499algorithm to avoid the race condition, but this relies on the 500processor supporting an atomic <span class="emphasis"><em>Compare-And-Swap</em></span> 501instruction. For other platforms there are fall-backs using mutex 502locks. Boost (as of version 1.35) includes several different 503implementations and the preprocessor selects one based on the 504compiler, standard library, platform etc. For the version of 505shared_ptr in libstdc++ the compiler and library are fixed, which 506makes things much simpler: we have an atomic CAS or we don't, see Lock 507Policy below for details. 508</p></div><div class="section"><div class="titlepage"><div><div><h5 class="title"><a id="shared_ptr.policy"></a>Selecting Lock Policy</h5></div></div></div><p> 509 </p><p> 510There is a single <code class="classname">_Sp_counted_base</code> class, 511which is a template parameterized on the enum 512<span class="type">__gnu_cxx::_Lock_policy</span>. The entire family of classes is 513parameterized on the lock policy, right up to 514<code class="classname">__shared_ptr</code>, <code class="classname">__weak_ptr</code> and 515<code class="classname">__enable_shared_from_this</code>. The actual 516<code class="classname">std::shared_ptr</code> class inherits from 517<code class="classname">__shared_ptr</code> with the lock policy parameter 518selected automatically based on the thread model and platform that 519libstdc++ is configured for, so that the best available template 520specialization will be used. This design is necessary because it would 521not be conforming for <code class="classname">shared_ptr</code> to have an 522extra template parameter, even if it had a default value. The 523available policies are: 524 </p><div class="orderedlist"><ol class="orderedlist" type="1"><li class="listitem"><p> 525 <code class="constant">_S_atomic</code> 526 </p><p> 527Selected when GCC supports a builtin atomic compare-and-swap operation 528on the target processor (see <a class="link" href="http://gcc.gnu.org/onlinedocs/gcc/_005f_005fatomic-Builtins.html" target="_top">Atomic 529Builtins</a>.) The reference counts are maintained using a lock-free 530algorithm and GCC's atomic builtins, which provide the required memory 531synchronisation. 532 </p></li><li class="listitem"><p> 533 <code class="constant">_S_mutex</code> 534 </p><p> 535The _Sp_counted_base specialization for this policy contains a mutex, 536which is locked in add_ref_lock(). This policy is used when GCC's atomic 537builtins aren't available so explicit memory barriers are needed in places. 538 </p></li><li class="listitem"><p> 539 <code class="constant">_S_single</code> 540 </p><p> 541This policy uses a non-reentrant add_ref_lock() with no locking. It is 542used when libstdc++ is built without <code class="literal">--enable-threads</code>. 543 </p></li></ol></div><p> 544 For all three policies, reference count increments and 545 decrements are done via the functions in 546 <code class="filename">ext/atomicity.h</code>, which detect if the program 547 is multi-threaded. If only one thread of execution exists in 548 the program then less expensive non-atomic operations are used. 549 </p></div><div class="section"><div class="titlepage"><div><div><h5 class="title"><a id="shared_ptr.rel"></a>Related functions and classes</h5></div></div></div><div class="variablelist"><dl class="variablelist"><dt><span class="term"><code class="code">dynamic_pointer_cast</code>, <code class="code">static_pointer_cast</code>, 550<code class="code">const_pointer_cast</code></span></dt><dd><p> 551As noted in N2351, these functions can be implemented non-intrusively using 552the alias constructor. However the aliasing constructor is only available 553in C++11 mode, so in TR1 mode these casts rely on three non-standard 554constructors in shared_ptr and __shared_ptr. 555In C++11 mode these constructors and the related tag types are not needed. 556 </p></dd><dt><span class="term"><code class="code">enable_shared_from_this</code></span></dt><dd><p> 557The clever overload to detect a base class of type 558<code class="code">enable_shared_from_this</code> comes straight from Boost. 559There is an extra overload for <code class="code">__enable_shared_from_this</code> to 560work smoothly with <code class="code">__shared_ptr<Tp, Lp></code> using any lock 561policy. 562 </p></dd><dt><span class="term"><code class="code">make_shared</code>, <code class="code">allocate_shared</code></span></dt><dd><p> 563<code class="code">make_shared</code> simply forwards to <code class="code">allocate_shared</code> 564with <code class="code">std::allocator</code> as the allocator. 565Although these functions can be implemented non-intrusively using the 566alias constructor, if they have access to the implementation then it is 567possible to save storage and reduce the number of heap allocations. The 568newly constructed object and the _Sp_counted_* can be allocated in a single 569block and the standard says implementations are "encouraged, but not required," 570to do so. This implementation provides additional non-standard constructors 571(selected with the type <code class="code">_Sp_make_shared_tag</code>) which create an 572object of type <code class="code">_Sp_counted_ptr_inplace</code> to hold the new object. 573The returned <code class="code">shared_ptr<A></code> needs to know the address of the 574new <code class="code">A</code> object embedded in the <code class="code">_Sp_counted_ptr_inplace</code>, 575but it has no way to access it. 576This implementation uses a "covert channel" to return the address of the 577embedded object when <code class="code">get_deleter<_Sp_make_shared_tag>()</code> 578is called. Users should not try to use this. 579As well as the extra constructors, this implementation also needs some 580members of _Sp_counted_deleter to be protected where they could otherwise 581be private. 582 </p></dd></dl></div></div></div><div class="section"><div class="titlepage"><div><div><h4 class="title"><a id="shared_ptr.using"></a>Use</h4></div></div></div><div class="section"><div class="titlepage"><div><div><h5 class="title"><a id="shared_ptr.examples"></a>Examples</h5></div></div></div><p> 583 Examples of use can be found in the testsuite, under 584 <code class="filename">testsuite/tr1/2_general_utilities/shared_ptr</code>, 585 <code class="filename">testsuite/20_util/shared_ptr</code> 586 and 587 <code class="filename">testsuite/20_util/weak_ptr</code>. 588 </p></div><div class="section"><div class="titlepage"><div><div><h5 class="title"><a id="shared_ptr.issues"></a>Unresolved Issues</h5></div></div></div><p> 589 The <span class="emphasis"><em><code class="classname">shared_ptr</code> atomic access</em></span> 590 clause in the C++11 standard is not implemented in GCC. 591 </p><p> 592 Unlike Boost, this implementation does not use separate classes 593 for the pointer+deleter and pointer+deleter+allocator cases in 594 C++11 mode, combining both into _Sp_counted_deleter and using 595 <code class="classname">allocator</code> when the user doesn't specify 596 an allocator. If it was found to be beneficial an additional 597 class could easily be added. With the current implementation, 598 the _Sp_counted_deleter and __shared_count constructors taking a 599 custom deleter but no allocator are technically redundant and 600 could be removed, changing callers to always specify an 601 allocator. If a separate pointer+deleter class was added the 602 __shared_count constructor would be needed, so it has been kept 603 for now. 604 </p><p> 605 The hack used to get the address of the managed object from 606 <code class="function">_Sp_counted_ptr_inplace::_M_get_deleter()</code> 607 is accessible to users. This could be prevented if 608 <code class="function">get_deleter<_Sp_make_shared_tag>()</code> 609 always returned NULL, since the hack only needs to work at a 610 lower level, not in the public API. This wouldn't be difficult, 611 but hasn't been done since there is no danger of accidental 612 misuse: users already know they are relying on unsupported 613 features if they refer to implementation details such as 614 _Sp_make_shared_tag. 615 </p><p> 616 tr1::_Sp_deleter could be a private member of tr1::__shared_count but it 617 would alter the ABI. 618 </p></div></div><div class="section"><div class="titlepage"><div><div><h4 class="title"><a id="shared_ptr.ack"></a>Acknowledgments</h4></div></div></div><p> 619 The original authors of the Boost shared_ptr, which is really nice 620 code to work with, Peter Dimov in particular for his help and 621 invaluable advice on thread safety. Phillip Jordan and Paolo 622 Carlini for the lock policy implementation. 623 </p></div><div class="bibliography"><div class="titlepage"><div><div><h4 class="title"><a id="shared_ptr.biblio"></a>Bibliography</h4></div></div></div><div class="biblioentry"><a id="id-1.3.4.4.4.5.8.2"></a><p><span class="title"><em> 624 <a class="link" href="http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2351.htm" target="_top"> 625 Improving shared_ptr for C++0x, Revision 2 626 </a> 627 </em>. </span><span class="subtitle"> 628 N2351 629 . </span></p></div><div class="biblioentry"><a id="id-1.3.4.4.4.5.8.3"></a><p><span class="title"><em> 630 <a class="link" href="http://open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2456.html" target="_top"> 631 C++ Standard Library Active Issues List 632 </a> 633 </em>. </span><span class="subtitle"> 634 N2456 635 . </span></p></div><div class="biblioentry"><a id="id-1.3.4.4.4.5.8.4"></a><p><span class="title"><em> 636 <a class="link" href="http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2461.pdf" target="_top"> 637 Working Draft, Standard for Programming Language C++ 638 </a> 639 </em>. </span><span class="subtitle"> 640 N2461 641 . </span></p></div><div class="biblioentry"><a id="id-1.3.4.4.4.5.8.5"></a><p><span class="title"><em> 642 <a class="link" href="http://www.boost.org/libs/smart_ptr/shared_ptr.htm" target="_top"> 643 Boost C++ Libraries documentation, shared_ptr 644 </a> 645 </em>. </span><span class="subtitle"> 646 N2461 647 . </span></p></div></div></div></div><div class="navfooter"><hr /><table width="100%" summary="Navigation footer"><tr><td width="40%" align="left"><a accesskey="p" href="pairs.html">Prev</a>��</td><td width="20%" align="center"><a accesskey="u" href="utilities.html">Up</a></td><td width="40%" align="right">��<a accesskey="n" href="traits.html">Next</a></td></tr><tr><td width="40%" align="left" valign="top">Pairs��</td><td width="20%" align="center"><a accesskey="h" href="../index.html">Home</a></td><td width="40%" align="right" valign="top">��Traits</td></tr></table></div></body></html>