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