memory.html revision 1.1.1.9
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 base class that <code class="classname">allocator</code> is derived from 107 may not be user-configurable. 108</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> 109 It's difficult to pick an allocation strategy that will provide 110 maximum utility, without excessively penalizing some behavior. In 111 fact, it's difficult just deciding which typical actions to measure 112 for speed. 113 </p><p> 114 Three synthetic benchmarks have been created that provide data 115 that is used to compare different C++ allocators. These tests are: 116 </p><div class="orderedlist"><ol class="orderedlist" type="1"><li class="listitem"><p> 117 Insertion. 118 </p><p> 119 Over multiple iterations, various STL container 120 objects have elements inserted to some maximum amount. A variety 121 of allocators are tested. 122 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> 123 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> 124 containers. 125 </p></li><li class="listitem"><p> 126 Insertion and erasure in a multi-threaded environment. 127 </p><p> 128 This test shows the ability of the allocator to reclaim memory 129 on a per-thread basis, as well as measuring thread contention 130 for memory resources. 131 Test source 132 <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>. 133 </p></li><li class="listitem"><p> 134 A threaded producer/consumer model. 135 </p><p> 136 Test source for 137 <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> 138 and 139 <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> 140 containers. 141 </p></li></ol></div><p> 142 The current default choice for 143 <code class="classname">allocator</code> is 144 <code class="classname">__gnu_cxx::new_allocator</code>. 145 </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> 146 In use, <code class="classname">allocator</code> may allocate and 147 deallocate using implementation-specific strategies and 148 heuristics. Because of this, a given call to an allocator object's 149 <code class="function">allocate</code> member function may not actually 150 call the global <code class="code">operator new</code> and a given call to 151 to the <code class="function">deallocate</code> member function may not 152 call <code class="code">operator delete</code>. 153 </p><p> 154 This can be confusing. 155 </p><p> 156 In particular, this can make debugging memory errors more 157 difficult, especially when using third-party tools like valgrind or 158 debug versions of <code class="function">new</code>. 159 </p><p> 160 There are various ways to solve this problem. One would be to use 161 a custom allocator that just called operators 162 <code class="function">new</code> and <code class="function">delete</code> 163 directly, for every allocation. (See the default allocator, 164 <code class="filename">include/ext/new_allocator.h</code>, for instance.) 165 However, that option may involve changing source code to use 166 a non-default allocator. Another option is to force the 167 default allocator to remove caching and pools, and to directly 168 allocate with every call of <code class="function">allocate</code> and 169 directly deallocate with every call of 170 <code class="function">deallocate</code>, regardless of efficiency. As it 171 turns out, this last option is also available. 172 </p><p> 173 To globally disable memory caching within the library for some of 174 the optional non-default allocators, merely set 175 <code class="constant">GLIBCXX_FORCE_NEW</code> (with any value) in the 176 system's environment before running the program. If your program 177 crashes with <code class="constant">GLIBCXX_FORCE_NEW</code> in the 178 environment, it likely means that you linked against objects 179 built against the older library (objects which might still using the 180 cached allocations...). 181 </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> 182 You can specify different memory management schemes on a 183 per-container basis, by overriding the default 184 <span class="type">Allocator</span> template parameter. For example, an easy 185 (but non-portable) method of specifying that only <code class="function">malloc</code> or <code class="function">free</code> 186 should be used instead of the default node allocator is: 187 </p><pre class="programlisting"> 188 std::list <int, __gnu_cxx::malloc_allocator<int> > malloc_list;</pre><p> 189 Likewise, a debugging form of whichever allocator is currently in use: 190 </p><pre class="programlisting"> 191 std::deque <int, __gnu_cxx::debug_allocator<std::allocator<int> > > debug_deque; 192 </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> 193 Writing a portable C++ allocator would dictate that the interface 194 would look much like the one specified for 195 <code class="classname">allocator</code>. Additional member functions, but 196 not subtractions, would be permissible. 197 </p><p> 198 Probably the best place to start would be to copy one of the 199 extension allocators: say a simple one like 200 <code class="classname">new_allocator</code>. 201 </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> 202 Several other allocators are provided as part of this 203 implementation. The location of the extension allocators and their 204 names have changed, but in all cases, functionality is 205 equivalent. Starting with gcc-3.4, all extension allocators are 206 standard style. Before this point, SGI style was the norm. Because of 207 this, the number of template arguments also changed. 208 <a class="xref" href="api.html#table.extension_allocators" title="Table��B.6.��Extension Allocators">Table��B.6, ���Extension Allocators���</a> tracks the changes. 209 </p><p> 210 More details on each of these extension allocators follows. 211 </p><div class="orderedlist"><ol class="orderedlist" type="1"><li class="listitem"><p> 212 <code class="classname">new_allocator</code> 213 </p><p> 214 Simply wraps <code class="function">::operator new</code> 215 and <code class="function">::operator delete</code>. 216 </p></li><li class="listitem"><p> 217 <code class="classname">malloc_allocator</code> 218 </p><p> 219 Simply wraps <code class="function">malloc</code> and 220 <code class="function">free</code>. There is also a hook for an 221 out-of-memory handler (for 222 <code class="function">new</code>/<code class="function">delete</code> this is 223 taken care of elsewhere). 224 </p></li><li class="listitem"><p> 225 <code class="classname">array_allocator</code> 226 </p><p> 227 Allows allocations of known and fixed sizes using existing 228 global or external storage allocated via construction of 229 <code class="classname">std::tr1::array</code> objects. By using this 230 allocator, fixed size containers (including 231 <code class="classname">std::string</code>) can be used without 232 instances calling <code class="function">::operator new</code> and 233 <code class="function">::operator delete</code>. This capability 234 allows the use of STL abstractions without runtime 235 complications or overhead, even in situations such as program 236 startup. For usage examples, please consult the testsuite. 237 </p></li><li class="listitem"><p> 238 <code class="classname">debug_allocator</code> 239 </p><p> 240 A wrapper around an arbitrary allocator A. It passes on 241 slightly increased size requests to A, and uses the extra 242 memory to store size information. When a pointer is passed 243 to <code class="function">deallocate()</code>, the stored size is 244 checked, and <code class="function">assert()</code> is used to 245 guarantee they match. 246 </p></li><li class="listitem"><p> 247 <code class="classname">throw_allocator</code> 248 </p><p> 249 Includes memory tracking and marking abilities as well as hooks for 250 throwing exceptions at configurable intervals (including random, 251 all, none). 252 </p></li><li class="listitem"><p> 253 <code class="classname">__pool_alloc</code> 254 </p><p> 255 A high-performance, single pool allocator. The reusable 256 memory is shared among identical instantiations of this type. 257 It calls through <code class="function">::operator new</code> to 258 obtain new memory when its lists run out. If a client 259 container requests a block larger than a certain threshold 260 size, then the pool is bypassed, and the allocate/deallocate 261 request is passed to <code class="function">::operator new</code> 262 directly. 263 </p><p> 264 Older versions of this class take a boolean template 265 parameter, called <code class="varname">thr</code>, and an integer template 266 parameter, called <code class="varname">inst</code>. 267 </p><p> 268 The <code class="varname">inst</code> number is used to track additional memory 269 pools. The point of the number is to allow multiple 270 instantiations of the classes without changing the semantics at 271 all. All three of 272 </p><pre class="programlisting"> 273 typedef __pool_alloc<true,0> normal; 274 typedef __pool_alloc<true,1> private; 275 typedef __pool_alloc<true,42> also_private; 276 </pre><p> 277 behave exactly the same way. However, the memory pool for each type 278 (and remember that different instantiations result in different types) 279 remains separate. 280 </p><p> 281 The library uses <span class="emphasis"><em>0</em></span> in all its instantiations. If you 282 wish to keep separate free lists for a particular purpose, use a 283 different number. 284 </p><p>The <code class="varname">thr</code> boolean determines whether the 285 pool should be manipulated atomically or not. When 286 <code class="varname">thr</code> = <code class="constant">true</code>, the allocator 287 is thread-safe, while <code class="varname">thr</code> = 288 <code class="constant">false</code>, is slightly faster but unsafe for 289 multiple threads. 290 </p><p> 291 For thread-enabled configurations, the pool is locked with a 292 single big lock. In some situations, this implementation detail 293 may result in severe performance degradation. 294 </p><p> 295 (Note that the GCC thread abstraction layer allows us to provide 296 safe zero-overhead stubs for the threading routines, if threads 297 were disabled at configuration time.) 298 </p></li><li class="listitem"><p> 299 <code class="classname">__mt_alloc</code> 300 </p><p> 301 A high-performance fixed-size allocator with 302 exponentially-increasing allocations. It has its own 303 <a class="link" href="mt_allocator.html" title="Chapter��20.��The mt_allocator">chapter</a> 304 in the documentation. 305 </p></li><li class="listitem"><p> 306 <code class="classname">bitmap_allocator</code> 307 </p><p> 308 A high-performance allocator that uses a bit-map to keep track 309 of the used and unused memory locations. It has its own 310 <a class="link" href="bitmap_allocator.html" title="Chapter��21.��The bitmap_allocator">chapter</a> 311 in the documentation. 312 </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"> 313 ISO/IEC 14882:1998 Programming languages - C++ 314 </em>. </span> 315 isoc++_1998 316 <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> 317 <a class="link" href="https://web.archive.org/web/20190622154249/http://www.drdobbs.com/the-standard-librarian-what-are-allocato/184403759" target="_top"> 318 The Standard Librarian: What Are Allocators Good For? 319 </a> 320 </em>. </span><span class="author"><span class="firstname">Matt</span> <span class="surname">Austern</span>. </span><span class="publisher"><span class="publishername"> 321 C/C++ Users Journal 322 . </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> 323 <a class="link" href="http://hoard.org" target="_top"> 324 The Hoard Memory Allocator 325 </a> 326 </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> 327 <a class="link" href="https://people.cs.umass.edu/~emery/pubs/berger-oopsla2002.pdf" target="_top"> 328 Reconsidering Custom Memory Allocation 329 </a> 330 </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> 331 <a class="link" href="http://www.angelikalanger.com/Articles/C++Report/Allocators/Allocators.html" target="_top"> 332 Allocator Types 333 </a> 334 </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"> 335 C/C++ Users Journal 336 . </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"> 337 Addison Wesley 338 . </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 339 happen with misuse of the <code class="classname">auto_ptr</code> class 340 template (called <acronym class="acronym">AP</acronym> here) would take some 341 time. Suffice it to say that the use of <acronym class="acronym">AP</acronym> 342 safely in the presence of copying has some subtleties. 343 </p><p> 344 The AP class is a really 345 nifty idea for a smart pointer, but it is one of the dumbest of 346 all the smart pointers -- and that's fine. 347 </p><p> 348 AP is not meant to be a supersmart solution to all resource 349 leaks everywhere. Neither is it meant to be an effective form 350 of garbage collection (although it can help, a little bit). 351 And it can <span class="emphasis"><em>not</em></span>be used for arrays! 352 </p><p> 353 <acronym class="acronym">AP</acronym> is meant to prevent nasty leaks in the 354 presence of exceptions. That's <span class="emphasis"><em>all</em></span>. This 355 code is AP-friendly: 356 </p><pre class="programlisting"> 357 // Not a recommend naming scheme, but good for web-based FAQs. 358 typedef std::auto_ptr<MyClass> APMC; 359 360 extern function_taking_MyClass_pointer (MyClass*); 361 extern some_throwable_function (); 362 363 void func (int data) 364 { 365 APMC ap (new MyClass(data)); 366 367 some_throwable_function(); // this will throw an exception 368 369 function_taking_MyClass_pointer (ap.get()); 370 } 371 </pre><p>When an exception gets thrown, the instance of MyClass that's 372 been created on the heap will be <code class="function">delete</code>'d as the stack is 373 unwound past <code class="function">func()</code>. 374 </p><p>Changing that code as follows is not <acronym class="acronym">AP</acronym>-friendly: 375 </p><pre class="programlisting"> 376 APMC ap (new MyClass[22]); 377 </pre><p>You will get the same problems as you would without the use 378 of <acronym class="acronym">AP</acronym>: 379 </p><pre class="programlisting"> 380 char* array = new char[10]; // array new... 381 ... 382 delete array; // ...but single-object delete 383 </pre><p> 384 AP cannot tell whether the pointer you've passed at creation points 385 to one or many things. If it points to many things, you are about 386 to die. AP is trivial to write, however, so you could write your 387 own <code class="code">auto_array_ptr</code> for that situation (in fact, this has 388 been done many times; check the mailing lists, Usenet, Boost, etc). 389 </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> 390 </p><p>All of the <a class="link" href="containers.html" title="Chapter��9.�� Containers">containers</a> 391 described in the standard library require their contained types 392 to have, among other things, a copy constructor like this: 393 </p><pre class="programlisting"> 394 struct My_Type 395 { 396 My_Type (My_Type const&); 397 }; 398 </pre><p> 399 Note the const keyword; the object being copied shouldn't change. 400 The template class <code class="code">auto_ptr</code> (called AP here) does not 401 meet this requirement. Creating a new AP by copying an existing 402 one transfers ownership of the pointed-to object, which means that 403 the AP being copied must change, which in turn means that the 404 copy ctors of AP do not take const objects. 405 </p><p> 406 The resulting rule is simple: <span class="emphasis"><em>Never ever use a 407 container of auto_ptr objects</em></span>. The standard says that 408 <span class="quote">���<span class="quote">undefined</span>���</span> behavior is the result, but it is 409 guaranteed to be messy. 410 </p><p> 411 To prevent you from doing this to yourself, the 412 <a class="link" href="ext_compile_checks.html" title="Chapter��16.��Compile Time Checks">concept checks</a> built 413 in to this implementation will issue an error if you try to 414 compile code like this: 415 </p><pre class="programlisting"> 416 #include <vector> 417 #include <memory> 418 419 void f() 420 { 421 std::vector< std::auto_ptr<int> > vec_ap_int; 422 } 423 </pre><p> 424Should you try this with the checks enabled, you will see an error. 425 </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> 426The shared_ptr class template stores a pointer, usually obtained via new, 427and implements shared ownership semantics. 428</p><div class="section"><div class="titlepage"><div><div><h4 class="title"><a id="shared_ptr.req"></a>Requirements</h4></div></div></div><p> 429 </p><p> 430 The standard deliberately doesn't require a reference-counted 431 implementation, allowing other techniques such as a 432 circular-linked-list. 433 </p><p> 434 </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> 435The <code class="classname">shared_ptr</code> code is kindly donated to GCC by the Boost 436project and the original authors of the code. The basic design and 437algorithms are from Boost, the notes below describe details specific to 438the GCC implementation. Names have been uglified in this implementation, 439but the design should be recognisable to anyone familiar with the Boost 4401.32 shared_ptr. 441 </p><p> 442The basic design is an abstract base class, <code class="code">_Sp_counted_base</code> that 443does the reference-counting and calls virtual functions when the count 444drops to zero. 445Derived classes override those functions to destroy resources in a context 446where the correct dynamic type is known. This is an application of the 447technique known as type erasure. 448 </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> 449A <code class="classname">shared_ptr<T></code> contains a pointer of 450type <span class="type">T*</span> and an object of type 451<code class="classname">__shared_count</code>. The shared_count contains a 452pointer of type <span class="type">_Sp_counted_base*</span> which points to the 453object that maintains the reference-counts and destroys the managed 454resource. 455 </p><div class="variablelist"><dl class="variablelist"><dt><span class="term"><code class="classname">_Sp_counted_base<Lp></code></span></dt><dd><p> 456The base of the hierarchy is parameterized on the lock policy (see below.) 457_Sp_counted_base doesn't depend on the type of pointer being managed, 458it only maintains the reference counts and calls virtual functions when 459the counts drop to zero. The managed object is destroyed when the last 460strong reference is dropped, but the _Sp_counted_base itself must exist 461until the last weak reference is dropped. 462 </p></dd><dt><span class="term"><code class="classname">_Sp_counted_base_impl<Ptr, Deleter, Lp></code></span></dt><dd><p> 463Inherits from _Sp_counted_base and stores a pointer of type <code class="code">Ptr</code> 464and a deleter of type <code class="code">Deleter</code>. <code class="classname">_Sp_deleter</code> is 465used when the user doesn't supply a custom deleter. Unlike Boost's, this 466default deleter is not "checked" because GCC already issues a warning if 467<code class="function">delete</code> is used with an incomplete type. 468This is the only derived type used by <code class="classname">tr1::shared_ptr<Ptr></code> 469and it is never used by <code class="classname">std::shared_ptr</code>, which uses one of 470the following types, depending on how the shared_ptr is constructed. 471 </p></dd><dt><span class="term"><code class="classname">_Sp_counted_ptr<Ptr, Lp></code></span></dt><dd><p> 472Inherits from _Sp_counted_base and stores a pointer of type <span class="type">Ptr</span>, 473which is passed to <code class="function">delete</code> when the last reference is dropped. 474This is the simplest form and is used when there is no custom deleter or 475allocator. 476 </p></dd><dt><span class="term"><code class="classname">_Sp_counted_deleter<Ptr, Deleter, Alloc></code></span></dt><dd><p> 477Inherits from _Sp_counted_ptr and adds support for custom deleter and 478allocator. Empty Base Optimization is used for the allocator. This class 479is used even when the user only provides a custom deleter, in which case 480<code class="classname">allocator</code> is used as the allocator. 481 </p></dd><dt><span class="term"><code class="classname">_Sp_counted_ptr_inplace<Tp, Alloc, Lp></code></span></dt><dd><p> 482Used by <code class="code">allocate_shared</code> and <code class="code">make_shared</code>. 483Contains aligned storage to hold an object of type <span class="type">Tp</span>, 484which is constructed in-place with placement <code class="function">new</code>. 485Has a variadic template constructor allowing any number of arguments to 486be forwarded to <span class="type">Tp</span>'s constructor. 487Unlike the other <code class="classname">_Sp_counted_*</code> classes, this one is parameterized on the 488type of object, not the type of pointer; this is purely a convenience 489that simplifies the implementation slightly. 490 </p></dd></dl></div><p> 491C++11-only features are: rvalue-ref/move support, allocator support, 492aliasing constructor, make_shared & allocate_shared. Additionally, 493the constructors taking <code class="classname">auto_ptr</code> parameters are 494deprecated in C++11 mode. 495 </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> 496The 497<a class="link" href="http://www.boost.org/libs/smart_ptr/shared_ptr.htm#ThreadSafety" target="_top">Thread 498Safety</a> section of the Boost shared_ptr documentation says "shared_ptr 499objects offer the same level of thread safety as built-in types." 500The implementation must ensure that concurrent updates to separate shared_ptr 501instances are correct even when those instances share a reference count e.g. 502</p><pre class="programlisting"> 503shared_ptr<A> a(new A); 504shared_ptr<A> b(a); 505 506// Thread 1 // Thread 2 507 a.reset(); b.reset(); 508</pre><p> 509The dynamically-allocated object must be destroyed by exactly one of the 510threads. Weak references make things even more interesting. 511The shared state used to implement shared_ptr must be transparent to the 512user and invariants must be preserved at all times. 513The key pieces of shared state are the strong and weak reference counts. 514Updates to these need to be atomic and visible to all threads to ensure 515correct cleanup of the managed resource (which is, after all, shared_ptr's 516job!) 517On multi-processor systems memory synchronisation may be needed so that 518reference-count updates and the destruction of the managed resource are 519race-free. 520</p><p> 521The function <code class="function">_Sp_counted_base::_M_add_ref_lock()</code>, called when 522obtaining a shared_ptr from a weak_ptr, has to test if the managed 523resource still exists and either increment the reference count or throw 524<code class="classname">bad_weak_ptr</code>. 525In a multi-threaded program there is a potential race condition if the last 526reference is dropped (and the managed resource destroyed) between testing 527the reference count and incrementing it, which could result in a shared_ptr 528pointing to invalid memory. 529</p><p> 530The Boost shared_ptr (as used in GCC) features a clever lock-free 531algorithm to avoid the race condition, but this relies on the 532processor supporting an atomic <span class="emphasis"><em>Compare-And-Swap</em></span> 533instruction. For other platforms there are fall-backs using mutex 534locks. Boost (as of version 1.35) includes several different 535implementations and the preprocessor selects one based on the 536compiler, standard library, platform etc. For the version of 537shared_ptr in libstdc++ the compiler and library are fixed, which 538makes things much simpler: we have an atomic CAS or we don't, see Lock 539Policy below for details. 540</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> 541 </p><p> 542There is a single <code class="classname">_Sp_counted_base</code> class, 543which is a template parameterized on the enum 544<span class="type">__gnu_cxx::_Lock_policy</span>. The entire family of classes is 545parameterized on the lock policy, right up to 546<code class="classname">__shared_ptr</code>, <code class="classname">__weak_ptr</code> and 547<code class="classname">__enable_shared_from_this</code>. The actual 548<code class="classname">std::shared_ptr</code> class inherits from 549<code class="classname">__shared_ptr</code> with the lock policy parameter 550selected automatically based on the thread model and platform that 551libstdc++ is configured for, so that the best available template 552specialization will be used. This design is necessary because it would 553not be conforming for <code class="classname">shared_ptr</code> to have an 554extra template parameter, even if it had a default value. The 555available policies are: 556 </p><div class="orderedlist"><ol class="orderedlist" type="1"><li class="listitem"><p> 557 <code class="constant">_S_atomic</code> 558 </p><p> 559Selected when GCC supports a builtin atomic compare-and-swap operation 560on the target processor (see <a class="link" href="http://gcc.gnu.org/onlinedocs/gcc/_005f_005fatomic-Builtins.html" target="_top">Atomic 561Builtins</a>.) The reference counts are maintained using a lock-free 562algorithm and GCC's atomic builtins, which provide the required memory 563synchronisation. 564 </p></li><li class="listitem"><p> 565 <code class="constant">_S_mutex</code> 566 </p><p> 567The _Sp_counted_base specialization for this policy contains a mutex, 568which is locked in add_ref_lock(). This policy is used when GCC's atomic 569builtins aren't available so explicit memory barriers are needed in places. 570 </p></li><li class="listitem"><p> 571 <code class="constant">_S_single</code> 572 </p><p> 573This policy uses a non-reentrant add_ref_lock() with no locking. It is 574used when libstdc++ is built without <code class="literal">--enable-threads</code>. 575 </p></li></ol></div><p> 576 For all three policies, reference count increments and 577 decrements are done via the functions in 578 <code class="filename">ext/atomicity.h</code>, which detect if the program 579 is multi-threaded. If only one thread of execution exists in 580 the program then less expensive non-atomic operations are used. 581 </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>, 582<code class="code">const_pointer_cast</code></span></dt><dd><p> 583As noted in N2351, these functions can be implemented non-intrusively using 584the alias constructor. However the aliasing constructor is only available 585in C++11 mode, so in TR1 mode these casts rely on three non-standard 586constructors in shared_ptr and __shared_ptr. 587In C++11 mode these constructors and the related tag types are not needed. 588 </p></dd><dt><span class="term"><code class="code">enable_shared_from_this</code></span></dt><dd><p> 589The clever overload to detect a base class of type 590<code class="code">enable_shared_from_this</code> comes straight from Boost. 591There is an extra overload for <code class="code">__enable_shared_from_this</code> to 592work smoothly with <code class="code">__shared_ptr<Tp, Lp></code> using any lock 593policy. 594 </p></dd><dt><span class="term"><code class="code">make_shared</code>, <code class="code">allocate_shared</code></span></dt><dd><p> 595<code class="code">make_shared</code> simply forwards to <code class="code">allocate_shared</code> 596with <code class="code">std::allocator</code> as the allocator. 597Although these functions can be implemented non-intrusively using the 598alias constructor, if they have access to the implementation then it is 599possible to save storage and reduce the number of heap allocations. The 600newly constructed object and the _Sp_counted_* can be allocated in a single 601block and the standard says implementations are "encouraged, but not required," 602to do so. This implementation provides additional non-standard constructors 603(selected with the type <code class="code">_Sp_make_shared_tag</code>) which create an 604object of type <code class="code">_Sp_counted_ptr_inplace</code> to hold the new object. 605The returned <code class="code">shared_ptr<A></code> needs to know the address of the 606new <code class="code">A</code> object embedded in the <code class="code">_Sp_counted_ptr_inplace</code>, 607but it has no way to access it. 608This implementation uses a "covert channel" to return the address of the 609embedded object when <code class="code">get_deleter<_Sp_make_shared_tag>()</code> 610is called. Users should not try to use this. 611As well as the extra constructors, this implementation also needs some 612members of _Sp_counted_deleter to be protected where they could otherwise 613be private. 614 </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> 615 Examples of use can be found in the testsuite, under 616 <code class="filename">testsuite/tr1/2_general_utilities/shared_ptr</code>, 617 <code class="filename">testsuite/20_util/shared_ptr</code> 618 and 619 <code class="filename">testsuite/20_util/weak_ptr</code>. 620 </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> 621 The <span class="emphasis"><em><code class="classname">shared_ptr</code> atomic access</em></span> 622 clause in the C++11 standard is not implemented in GCC. 623 </p><p> 624 Unlike Boost, this implementation does not use separate classes 625 for the pointer+deleter and pointer+deleter+allocator cases in 626 C++11 mode, combining both into _Sp_counted_deleter and using 627 <code class="classname">allocator</code> when the user doesn't specify 628 an allocator. If it was found to be beneficial an additional 629 class could easily be added. With the current implementation, 630 the _Sp_counted_deleter and __shared_count constructors taking a 631 custom deleter but no allocator are technically redundant and 632 could be removed, changing callers to always specify an 633 allocator. If a separate pointer+deleter class was added the 634 __shared_count constructor would be needed, so it has been kept 635 for now. 636 </p><p> 637 The hack used to get the address of the managed object from 638 <code class="function">_Sp_counted_ptr_inplace::_M_get_deleter()</code> 639 is accessible to users. This could be prevented if 640 <code class="function">get_deleter<_Sp_make_shared_tag>()</code> 641 always returned NULL, since the hack only needs to work at a 642 lower level, not in the public API. This wouldn't be difficult, 643 but hasn't been done since there is no danger of accidental 644 misuse: users already know they are relying on unsupported 645 features if they refer to implementation details such as 646 _Sp_make_shared_tag. 647 </p><p> 648 tr1::_Sp_deleter could be a private member of tr1::__shared_count but it 649 would alter the ABI. 650 </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> 651 The original authors of the Boost shared_ptr, which is really nice 652 code to work with, Peter Dimov in particular for his help and 653 invaluable advice on thread safety. Phillip Jordan and Paolo 654 Carlini for the lock policy implementation. 655 </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> 656 <a class="link" href="http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2351.htm" target="_top"> 657 Improving shared_ptr for C++0x, Revision 2 658 </a> 659 </em>. </span><span class="subtitle"> 660 N2351 661 . </span></p></div><div class="biblioentry"><a id="id-1.3.4.4.4.5.8.3"></a><p><span class="title"><em> 662 <a class="link" href="http://open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2456.html" target="_top"> 663 C++ Standard Library Active Issues List 664 </a> 665 </em>. </span><span class="subtitle"> 666 N2456 667 . </span></p></div><div class="biblioentry"><a id="id-1.3.4.4.4.5.8.4"></a><p><span class="title"><em> 668 <a class="link" href="http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2461.pdf" target="_top"> 669 Working Draft, Standard for Programming Language C++ 670 </a> 671 </em>. </span><span class="subtitle"> 672 N2461 673 . </span></p></div><div class="biblioentry"><a id="id-1.3.4.4.4.5.8.5"></a><p><span class="title"><em> 674 <a class="link" href="http://www.boost.org/libs/smart_ptr/shared_ptr.htm" target="_top"> 675 Boost C++ Libraries documentation, shared_ptr 676 </a> 677 </em>. </span><span class="subtitle"> 678 N2461 679 . </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>