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