diff options
| author | upstream source tree <ports@midipix.org> | 2015-03-15 20:14:05 -0400 |
|---|---|---|
| committer | upstream source tree <ports@midipix.org> | 2015-03-15 20:14:05 -0400 |
| commit | 554fd8c5195424bdbcabf5de30fdc183aba391bd (patch) | |
| tree | 976dc5ab7fddf506dadce60ae936f43f58787092 /libstdc++-v3/doc/html/manual/memory.html | |
| download | cbb-gcc-4.6.4-554fd8c5195424bdbcabf5de30fdc183aba391bd.tar.bz2 cbb-gcc-4.6.4-554fd8c5195424bdbcabf5de30fdc183aba391bd.tar.xz | |
obtained gcc-4.6.4.tar.bz2 from upstream website;upstream
verified gcc-4.6.4.tar.bz2.sig;
imported gcc-4.6.4 source tree from verified upstream tarball.
downloading a git-generated archive based on the 'upstream' tag
should provide you with a source tree that is binary identical
to the one extracted from the above tarball.
if you have obtained the source via the command 'git clone',
however, do note that line-endings of files in your working
directory might differ from line-endings of the respective
files in the upstream repository.
Diffstat (limited to 'libstdc++-v3/doc/html/manual/memory.html')
| -rw-r--r-- | libstdc++-v3/doc/html/manual/memory.html | 699 |
1 files changed, 699 insertions, 0 deletions
diff --git a/libstdc++-v3/doc/html/manual/memory.html b/libstdc++-v3/doc/html/manual/memory.html new file mode 100644 index 000000000..5953539dc --- /dev/null +++ b/libstdc++-v3/doc/html/manual/memory.html @@ -0,0 +1,699 @@ +<?xml version="1.0" encoding="UTF-8" standalone="no"?> +<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN" "http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd"> +<html xmlns="http://www.w3.org/1999/xhtml"><head><title>Memory</title><meta name="generator" content="DocBook XSL-NS Stylesheets V1.76.1"/><meta name="keywords" content=" ISO C++ , library "/><link rel="home" href="../spine.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 align="left"><a accesskey="p" href="pairs.html">Prev</a> </td><th width="60%" align="center">Chapter 6. + Utilities + +</th><td 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"><a id="std.util.memory"/>Memory</h2></div></div></div><p> + Memory contains three general areas. First, function and operator + calls via <code class="function">new</code> and <code class="function">delete</code> + operator or member function calls. Second, allocation via + <code class="classname">allocator</code>. And finally, smart pointer and + intelligent pointer abstractions. + </p><div class="section" title="Allocators"><div class="titlepage"><div><div><h3 class="title"><a id="std.util.memory.allocator"/>Allocators</h3></div></div></div><p> + Memory management for Standard Library entities is encapsulated in a + class template called <code class="classname">allocator</code>. The + <code class="classname">allocator</code> abstraction is used throughout the + library in <code class="classname">string</code>, container classes, + algorithms, and parts of iostreams. This class, and base classes of + it, are the superset of available free store (<span class="quote">“<span class="quote">heap</span>”</span>) + management classes. +</p><div class="section" title="Requirements"><div class="titlepage"><div><div><h4 class="title"><a id="allocator.req"/>Requirements</h4></div></div></div><p> + The C++ standard only gives a few directives in this area: + </p><div class="itemizedlist"><ul class="itemizedlist"><li class="listitem"><p> + When you add elements to a container, and the container must + allocate more memory to hold them, the container makes the + request via its <span class="type">Allocator</span> template + parameter, which is usually aliased to + <span class="type">allocator_type</span>. This includes adding chars + to the string class, which acts as a regular STL container in + this respect. + </p></li><li class="listitem"><p> + The default <span class="type">Allocator</span> argument of every + container-of-T is <code class="classname">allocator<T></code>. + </p></li><li class="listitem"><p> + The interface of the <code class="classname">allocator<T></code> class is + extremely simple. It has about 20 public declarations (nested + typedefs, member functions, etc), but the two which concern us most + are: + </p><pre class="programlisting"> + T* allocate (size_type n, const void* hint = 0); + void deallocate (T* p, size_type n); + </pre><p> + The <code class="varname">n</code> arguments in both those + functions is a <span class="emphasis"><em>count</em></span> of the number of + <span class="type">T</span>'s to allocate space for, <span class="emphasis"><em>not their + total size</em></span>. + (This is a simplification; the real signatures use nested typedefs.) + </p></li><li class="listitem"><p> + The storage is obtained by calling <code class="function">::operator + new</code>, but it is unspecified when or how + often this function is called. The use of the + <code class="varname">hint</code> is unspecified, but intended as an + aid to locality if an implementation so + desires. <code class="constant">[20.4.1.1]/6</code> + </p></li></ul></div><p> + Complete details can be found in the C++ standard, look in + <code class="constant">[20.4 Memory]</code>. + </p></div><div class="section" title="Design Issues"><div class="titlepage"><div><div><h4 class="title"><a id="allocator.design_issues"/>Design Issues</h4></div></div></div><p> + The easiest way of fulfilling the requirements is to call + <code class="function">operator new</code> each time a container needs + memory, and to call <code class="function">operator delete</code> each time + the container releases memory. This method may be <a class="link" href="http://gcc.gnu.org/ml/libstdc++/2001-05/msg00105.html">slower</a> + than caching the allocations and re-using previously-allocated + memory, but has the advantage of working correctly across a wide + variety of hardware and operating systems, including large + clusters. The <code class="classname">__gnu_cxx::new_allocator</code> + implements the simple operator new and operator delete semantics, + while <code class="classname">__gnu_cxx::malloc_allocator</code> + implements much the same thing, only with the C language functions + <code class="function">std::malloc</code> and <code class="function">free</code>. + </p><p> + Another approach is to use intelligence within the allocator + class to cache allocations. This extra machinery can take a variety + of forms: a bitmap index, an index into an exponentially increasing + power-of-two-sized buckets, or simpler fixed-size pooling cache. + The cache is shared among all the containers in the program: when + your program's <code class="classname">std::vector<int></code> gets + cut in half and frees a bunch of its storage, that memory can be + reused by the private + <code class="classname">std::list<WonkyWidget></code> brought in from + a KDE library that you linked against. And operators + <code class="function">new</code> and <code class="function">delete</code> are not + always called to pass the memory on, either, which is a speed + bonus. Examples of allocators that use these techniques are + <code class="classname">__gnu_cxx::bitmap_allocator</code>, + <code class="classname">__gnu_cxx::pool_allocator</code>, and + <code class="classname">__gnu_cxx::__mt_alloc</code>. + </p><p> + Depending on the implementation techniques used, the underlying + operating system, and compilation environment, scaling caching + allocators can be tricky. In particular, order-of-destruction and + order-of-creation for memory pools may be difficult to pin down + with certainty, which may create problems when used with plugins + or loading and unloading shared objects in memory. As such, using + caching allocators on systems that do not support + <code class="function">abi::__cxa_atexit</code> is not recommended. + </p></div><div class="section" title="Implementation"><div class="titlepage"><div><div><h4 class="title"><a id="allocator.impl"/>Implementation</h4></div></div></div><div class="section" title="Interface Design"><div class="titlepage"><div><div><h5 class="title"><a id="id473085"/>Interface Design</h5></div></div></div><p> + The only allocator interface that + is supported is the standard C++ interface. As such, all STL + containers have been adjusted, and all external allocators have + been modified to support this change. + </p><p> + The class <code class="classname">allocator</code> just has typedef, + constructor, and rebind members. It inherits from one of the + high-speed extension allocators, covered below. Thus, all + allocation and deallocation depends on the base class. + </p><p> + The base class that <code class="classname">allocator</code> is derived from + may not be user-configurable. +</p></div><div class="section" title="Selecting Default Allocation Policy"><div class="titlepage"><div><div><h5 class="title"><a id="id473115"/>Selecting Default Allocation Policy</h5></div></div></div><p> + It's difficult to pick an allocation strategy that will provide + maximum utility, without excessively penalizing some behavior. In + fact, it's difficult just deciding which typical actions to measure + for speed. + </p><p> + Three synthetic benchmarks have been created that provide data + that is used to compare different C++ allocators. These tests are: + </p><div class="orderedlist"><ol class="orderedlist"><li class="listitem"><p> + Insertion. + </p><p> + Over multiple iterations, various STL container + objects have elements inserted to some maximum amount. A variety + of allocators are tested. + 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">sequence</a> + and <a class="link" href="http://gcc.gnu.org/viewcvs/trunk/libstdc%2B%2B-v3/testsuite/performance/23_containers/insert/associative.cc?view=markup">associative</a> + containers. + </p></li><li class="listitem"><p> + Insertion and erasure in a multi-threaded environment. + </p><p> + This test shows the ability of the allocator to reclaim memory + on a per-thread basis, as well as measuring thread contention + for memory resources. + Test source + <a class="link" href="http://gcc.gnu.org/viewcvs/trunk/libstdc%2B%2B-v3/testsuite/performance/23_containers/insert_erase/associative.cc?view=markup">here</a>. + </p></li><li class="listitem"><p> + A threaded producer/consumer model. + </p><p> + Test source for + <a class="link" href="http://gcc.gnu.org/viewcvs/trunk/libstdc++-v3/testsuite/performance/23_containers/producer_consumer/sequence.cc?view=markup">sequence</a> + and + <a class="link" href="http://gcc.gnu.org/viewcvs/trunk/libstdc++-v3/testsuite/performance/23_containers/producer_consumer/associative.cc?view=markup">associative</a> + containers. + </p></li></ol></div><p> + The current default choice for + <code class="classname">allocator</code> is + <code class="classname">__gnu_cxx::new_allocator</code>. + </p></div><div class="section" title="Disabling Memory Caching"><div class="titlepage"><div><div><h5 class="title"><a id="id473225"/>Disabling Memory Caching</h5></div></div></div><p> + In use, <code class="classname">allocator</code> may allocate and + deallocate using implementation-specified strategies and + heuristics. Because of this, every call to an allocator object's + <code class="function">allocate</code> member function may not actually + call the global operator new. This situation is also duplicated + for calls to the <code class="function">deallocate</code> member + function. + </p><p> + This can be confusing. + </p><p> + In particular, this can make debugging memory errors more + difficult, especially when using third party tools like valgrind or + debug versions of <code class="function">new</code>. + </p><p> + There are various ways to solve this problem. One would be to use + a custom allocator that just called operators + <code class="function">new</code> and <code class="function">delete</code> + directly, for every allocation. (See + <code class="filename">include/ext/new_allocator.h</code>, for instance.) + However, that option would involve changing source code to use + a non-default allocator. Another option is to force the + default allocator to remove caching and pools, and to directly + allocate with every call of <code class="function">allocate</code> and + directly deallocate with every call of + <code class="function">deallocate</code>, regardless of efficiency. As it + turns out, this last option is also available. + </p><p> + To globally disable memory caching within the library for the + default allocator, merely set + <code class="constant">GLIBCXX_FORCE_NEW</code> (with any value) in the + system's environment before running the program. If your program + crashes with <code class="constant">GLIBCXX_FORCE_NEW</code> in the + environment, it likely means that you linked against objects + built against the older library (objects which might still using the + cached allocations...). + </p></div></div><div class="section" title="Using a Specific Allocator"><div class="titlepage"><div><div><h4 class="title"><a id="allocator.using"/>Using a Specific Allocator</h4></div></div></div><p> + You can specify different memory management schemes on a + per-container basis, by overriding the default + <span class="type">Allocator</span> template parameter. For example, an easy + (but non-portable) method of specifying that only <code class="function">malloc</code> or <code class="function">free</code> + should be used instead of the default node allocator is: + </p><pre class="programlisting"> + std::list <int, __gnu_cxx::malloc_allocator<int> > malloc_list;</pre><p> + Likewise, a debugging form of whichever allocator is currently in use: + </p><pre class="programlisting"> + std::deque <int, __gnu_cxx::debug_allocator<std::allocator<int> > > debug_deque; + </pre></div><div class="section" title="Custom Allocators"><div class="titlepage"><div><div><h4 class="title"><a id="allocator.custom"/>Custom Allocators</h4></div></div></div><p> + Writing a portable C++ allocator would dictate that the interface + would look much like the one specified for + <code class="classname">allocator</code>. Additional member functions, but + not subtractions, would be permissible. + </p><p> + Probably the best place to start would be to copy one of the + extension allocators: say a simple one like + <code class="classname">new_allocator</code>. + </p></div><div class="section" title="Extension Allocators"><div class="titlepage"><div><div><h4 class="title"><a id="allocator.ext"/>Extension Allocators</h4></div></div></div><p> + Several other allocators are provided as part of this + implementation. The location of the extension allocators and their + names have changed, but in all cases, functionality is + equivalent. Starting with gcc-3.4, all extension allocators are + standard style. Before this point, SGI style was the norm. Because of + this, the number of template arguments also changed. Here's a simple + chart to track the changes. + </p><p> + More details on each of these extension allocators follows. + </p><div class="orderedlist"><ol class="orderedlist"><li class="listitem"><p> + <code class="classname">new_allocator</code> + </p><p> + Simply wraps <code class="function">::operator new</code> + and <code class="function">::operator delete</code>. + </p></li><li class="listitem"><p> + <code class="classname">malloc_allocator</code> + </p><p> + Simply wraps <code class="function">malloc</code> and + <code class="function">free</code>. There is also a hook for an + out-of-memory handler (for + <code class="function">new</code>/<code class="function">delete</code> this is + taken care of elsewhere). + </p></li><li class="listitem"><p> + <code class="classname">array_allocator</code> + </p><p> + Allows allocations of known and fixed sizes using existing + global or external storage allocated via construction of + <code class="classname">std::tr1::array</code> objects. By using this + allocator, fixed size containers (including + <code class="classname">std::string</code>) can be used without + instances calling <code class="function">::operator new</code> and + <code class="function">::operator delete</code>. This capability + allows the use of STL abstractions without runtime + complications or overhead, even in situations such as program + startup. For usage examples, please consult the testsuite. + </p></li><li class="listitem"><p> + <code class="classname">debug_allocator</code> + </p><p> + A wrapper around an arbitrary allocator A. It passes on + slightly increased size requests to A, and uses the extra + memory to store size information. When a pointer is passed + to <code class="function">deallocate()</code>, the stored size is + checked, and <code class="function">assert()</code> is used to + guarantee they match. + </p></li><li class="listitem"><p> + <code class="classname">throw_allocator</code> + </p><p> + Includes memory tracking and marking abilities as well as hooks for + throwing exceptions at configurable intervals (including random, + all, none). + </p></li><li class="listitem"><p> + <code class="classname">__pool_alloc</code> + </p><p> + A high-performance, single pool allocator. The reusable + memory is shared among identical instantiations of this type. + It calls through <code class="function">::operator new</code> to + obtain new memory when its lists run out. If a client + container requests a block larger than a certain threshold + size, then the pool is bypassed, and the allocate/deallocate + request is passed to <code class="function">::operator new</code> + directly. + </p><p> + Older versions of this class take a boolean template + parameter, called <code class="varname">thr</code>, and an integer template + parameter, called <code class="varname">inst</code>. + </p><p> + The <code class="varname">inst</code> number is used to track additional memory + pools. The point of the number is to allow multiple + instantiations of the classes without changing the semantics at + all. All three of + </p><pre class="programlisting"> + typedef __pool_alloc<true,0> normal; + typedef __pool_alloc<true,1> private; + typedef __pool_alloc<true,42> also_private; + </pre><p> + behave exactly the same way. However, the memory pool for each type + (and remember that different instantiations result in different types) + remains separate. + </p><p> + The library uses <span class="emphasis"><em>0</em></span> in all its instantiations. If you + wish to keep separate free lists for a particular purpose, use a + different number. + </p><p>The <code class="varname">thr</code> boolean determines whether the + pool should be manipulated atomically or not. When + <code class="varname">thr</code> = <code class="constant">true</code>, the allocator + is thread-safe, while <code class="varname">thr</code> = + <code class="constant">false</code>, is slightly faster but unsafe for + multiple threads. + </p><p> + For thread-enabled configurations, the pool is locked with a + single big lock. In some situations, this implementation detail + may result in severe performance degradation. + </p><p> + (Note that the GCC thread abstraction layer allows us to provide + safe zero-overhead stubs for the threading routines, if threads + were disabled at configuration time.) + </p></li><li class="listitem"><p> + <code class="classname">__mt_alloc</code> + </p><p> + A high-performance fixed-size allocator with + exponentially-increasing allocations. It has its own + documentation, found <a class="link" href="ext_allocators.html#manual.ext.allocator.mt" title="mt_allocator">here</a>. + </p></li><li class="listitem"><p> + <code class="classname">bitmap_allocator</code> + </p><p> + A high-performance allocator that uses a bit-map to keep track + of the used and unused memory locations. It has its own + documentation, found <a class="link" href="bitmap_allocator.html" title="bitmap_allocator">here</a>. + </p></li></ol></div></div><div class="bibliography" title="Bibliography"><div class="titlepage"><div><div><h4 class="title"><a id="allocator.biblio"/>Bibliography</h4></div></div></div><div class="biblioentry"><a id="id473676"/><p><span class="citetitle"><em class="citetitle"> + ISO/IEC 14882:1998 Programming languages - C++ + </em>. </span> + isoc++_1998 + <span class="pagenums">20.4 Memory. </span></p></div><div class="biblioentry"><a id="id473691"/><p><span class="biblioid"> + . </span><span class="citetitle"><em class="citetitle"> + The Standard Librarian: What Are Allocators Good For? + </em>. </span><span class="author"><span class="firstname">Matt</span> <span class="surname">Austern</span>. </span><span class="publisher"><span class="publishername"> + C/C++ Users Journal + . </span></span></p></div><div class="biblioentry"><a id="id473725"/><p><span class="biblioid"> + . </span><span class="citetitle"><em class="citetitle"> + The Hoard Memory Allocator + </em>. </span><span class="author"><span class="firstname">Emery</span> <span class="surname">Berger</span>. </span></p></div><div class="biblioentry"><a id="id473750"/><p><span class="biblioid"> + . </span><span class="citetitle"><em class="citetitle"> + Reconsidering Custom Memory Allocation + </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="id473804"/><p><span class="biblioid"> + . </span><span class="citetitle"><em class="citetitle"> + Allocator Types + </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"> + C/C++ Users Journal + . </span></span></p></div><div class="biblioentry"><a id="id473845"/><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"> + Addison Wesley + . </span></span></p></div><div class="biblioentry"><a id="id473882"/><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"/>auto_ptr</h3></div></div></div><div class="section" title="Limitations"><div class="titlepage"><div><div><h4 class="title"><a id="auto_ptr.limitations"/>Limitations</h4></div></div></div><p>Explaining all of the fun and delicious things that can + happen with misuse of the <code class="classname">auto_ptr</code> class + template (called <acronym class="acronym">AP</acronym> here) would take some + time. Suffice it to say that the use of <acronym class="acronym">AP</acronym> + safely in the presence of copying has some subtleties. + </p><p> + The AP class is a really + nifty idea for a smart pointer, but it is one of the dumbest of + all the smart pointers -- and that's fine. + </p><p> + AP is not meant to be a supersmart solution to all resource + leaks everywhere. Neither is it meant to be an effective form + of garbage collection (although it can help, a little bit). + And it can <span class="emphasis"><em>not</em></span>be used for arrays! + </p><p> + <acronym class="acronym">AP</acronym> is meant to prevent nasty leaks in the + presence of exceptions. That's <span class="emphasis"><em>all</em></span>. This + code is AP-friendly: + </p><pre class="programlisting"> + // Not a recommend naming scheme, but good for web-based FAQs. + typedef std::auto_ptr<MyClass> APMC; + + extern function_taking_MyClass_pointer (MyClass*); + extern some_throwable_function (); + + void func (int data) + { + APMC ap (new MyClass(data)); + + some_throwable_function(); // this will throw an exception + + function_taking_MyClass_pointer (ap.get()); + } + </pre><p>When an exception gets thrown, the instance of MyClass that's + been created on the heap will be <code class="function">delete</code>'d as the stack is + unwound past <code class="function">func()</code>. + </p><p>Changing that code as follows is not <acronym class="acronym">AP</acronym>-friendly: + </p><pre class="programlisting"> + APMC ap (new MyClass[22]); + </pre><p>You will get the same problems as you would without the use + of <acronym class="acronym">AP</acronym>: + </p><pre class="programlisting"> + char* array = new char[10]; // array new... + ... + delete array; // ...but single-object delete + </pre><p> + AP cannot tell whether the pointer you've passed at creation points + to one or many things. If it points to many things, you are about + to die. AP is trivial to write, however, so you could write your + own <code class="code">auto_array_ptr</code> for that situation (in fact, this has + been done many times; check the mailing lists, Usenet, Boost, etc). + </p></div><div class="section" title="Use in Containers"><div class="titlepage"><div><div><h4 class="title"><a id="auto_ptr.using"/>Use in Containers</h4></div></div></div><p> + </p><p>All of the <a class="link" href="containers.html" title="Chapter 9. Containers">containers</a> + described in the standard library require their contained types + to have, among other things, a copy constructor like this: + </p><pre class="programlisting"> + struct My_Type + { + My_Type (My_Type const&); + }; + </pre><p> + Note the const keyword; the object being copied shouldn't change. + The template class <code class="code">auto_ptr</code> (called AP here) does not + meet this requirement. Creating a new AP by copying an existing + one transfers ownership of the pointed-to object, which means that + the AP being copied must change, which in turn means that the + copy ctors of AP do not take const objects. + </p><p> + The resulting rule is simple: <span class="emphasis"><em>Never ever use a + container of auto_ptr objects</em></span>. The standard says that + <span class="quote">“<span class="quote">undefined</span>”</span> behavior is the result, but it is + guaranteed to be messy. + </p><p> + To prevent you from doing this to yourself, the + <a class="link" href="ext_compile_checks.html" title="Chapter 16. Compile Time Checks">concept checks</a> built + in to this implementation will issue an error if you try to + compile code like this: + </p><pre class="programlisting"> + #include <vector> + #include <memory> + + void f() + { + std::vector< std::auto_ptr<int> > vec_ap_int; + } + </pre><p> +Should you try this with the checks enabled, you will see an error. + </p></div></div><div class="section" title="shared_ptr"><div class="titlepage"><div><div><h3 class="title"><a id="std.util.memory.shared_ptr"/>shared_ptr</h3></div></div></div><p> +The shared_ptr class template stores a pointer, usually obtained via new, +and implements shared ownership semantics. +</p><div class="section" title="Requirements"><div class="titlepage"><div><div><h4 class="title"><a id="shared_ptr.req"/>Requirements</h4></div></div></div><p> + </p><p> + The standard deliberately doesn't require a reference-counted + implementation, allowing other techniques such as a + circular-linked-list. + </p><p> + At the time of writing the C++0x working paper doesn't mention how + threads affect shared_ptr, but it is likely to follow the existing + practice set by <code class="classname">boost::shared_ptr</code>. The + shared_ptr in libstdc++ is derived from Boost's, so the same rules + apply. + </p><p> + </p></div><div class="section" title="Design Issues"><div class="titlepage"><div><div><h4 class="title"><a id="shared_ptr.design_issues"/>Design Issues</h4></div></div></div><p> +The <code class="classname">shared_ptr</code> code is kindly donated to GCC by the Boost +project and the original authors of the code. The basic design and +algorithms are from Boost, the notes below describe details specific to +the GCC implementation. Names have been uglified in this implementation, +but the design should be recognisable to anyone familiar with the Boost +1.32 shared_ptr. + </p><p> +The basic design is an abstract base class, <code class="code">_Sp_counted_base</code> that +does the reference-counting and calls virtual functions when the count +drops to zero. +Derived classes override those functions to destroy resources in a context +where the correct dynamic type is known. This is an application of the +technique known as type erasure. + </p></div><div class="section" title="Implementation"><div class="titlepage"><div><div><h4 class="title"><a id="shared_ptr.impl"/>Implementation</h4></div></div></div><div class="section" title="Class Hierarchy"><div class="titlepage"><div><div><h5 class="title"><a id="id474243"/>Class Hierarchy</h5></div></div></div><p> +A <code class="classname">shared_ptr<T></code> contains a pointer of +type <span class="type">T*</span> and an object of type +<code class="classname">__shared_count</code>. The shared_count contains a +pointer of type <span class="type">_Sp_counted_base*</span> which points to the +object that maintains the reference-counts and destroys the managed +resource. + </p><div class="variablelist"><dl><dt><span class="term"><code class="classname">_Sp_counted_base<Lp></code></span></dt><dd><p> +The base of the hierarchy is parameterized on the lock policy (see below.) +_Sp_counted_base doesn't depend on the type of pointer being managed, +it only maintains the reference counts and calls virtual functions when +the counts drop to zero. The managed object is destroyed when the last +strong reference is dropped, but the _Sp_counted_base itself must exist +until the last weak reference is dropped. + </p></dd><dt><span class="term"><code class="classname">_Sp_counted_base_impl<Ptr, Deleter, Lp></code></span></dt><dd><p> +Inherits from _Sp_counted_base and stores a pointer of type <span class="type">Ptr</span> +and a deleter of type <code class="code">Deleter</code>. <code class="code">_Sp_deleter</code> is +used when the user doesn't supply a custom deleter. Unlike Boost's, this +default deleter is not "checked" because GCC already issues a warning if +<code class="function">delete</code> is used with an incomplete type. +This is the only derived type used by <code class="classname">shared_ptr<Ptr></code> +and it is never used by <code class="classname">shared_ptr</code>, which uses one of +the following types, depending on how the shared_ptr is constructed. + </p></dd><dt><span class="term"><code class="classname">_Sp_counted_ptr<Ptr, Lp></code></span></dt><dd><p> +Inherits from _Sp_counted_base and stores a pointer of type <span class="type">Ptr</span>, +which is passed to <code class="function">delete</code> when the last reference is dropped. +This is the simplest form and is used when there is no custom deleter or +allocator. + </p></dd><dt><span class="term"><code class="classname">_Sp_counted_deleter<Ptr, Deleter, Alloc></code></span></dt><dd><p> +Inherits from _Sp_counted_ptr and adds support for custom deleter and +allocator. Empty Base Optimization is used for the allocator. This class +is used even when the user only provides a custom deleter, in which case +<code class="classname">allocator</code> is used as the allocator. + </p></dd><dt><span class="term"><code class="classname">_Sp_counted_ptr_inplace<Tp, Alloc, Lp></code></span></dt><dd><p> +Used by <code class="code">allocate_shared</code> and <code class="code">make_shared</code>. +Contains aligned storage to hold an object of type <span class="type">Tp</span>, +which is constructed in-place with placement <code class="function">new</code>. +Has a variadic template constructor allowing any number of arguments to +be forwarded to <span class="type">Tp</span>'s constructor. +Unlike the other <code class="classname">_Sp_counted_*</code> classes, this one is parameterized on the +type of object, not the type of pointer; this is purely a convenience +that simplifies the implementation slightly. + </p></dd></dl></div></div><div class="section" title="Thread Safety"><div class="titlepage"><div><div><h5 class="title"><a id="id474421"/>Thread Safety</h5></div></div></div><p> +C++0x-only features are: rvalue-ref/move support, allocator support, +aliasing constructor, make_shared & allocate_shared. Additionally, +the constructors taking <code class="classname">auto_ptr</code> parameters are +deprecated in C++0x mode. + </p><p> +The +<a class="link" href="http://boost.org/libs/smart_ptr/shared_ptr.htm#ThreadSafety">Thread +Safety</a> section of the Boost shared_ptr documentation says "shared_ptr +objects offer the same level of thread safety as built-in types." +The implementation must ensure that concurrent updates to separate shared_ptr +instances are correct even when those instances share a reference count e.g. +</p><pre class="programlisting"> +shared_ptr<A> a(new A); +shared_ptr<A> b(a); + +// Thread 1 // Thread 2 + a.reset(); b.reset(); +</pre><p> +The dynamically-allocated object must be destroyed by exactly one of the +threads. Weak references make things even more interesting. +The shared state used to implement shared_ptr must be transparent to the +user and invariants must be preserved at all times. +The key pieces of shared state are the strong and weak reference counts. +Updates to these need to be atomic and visible to all threads to ensure +correct cleanup of the managed resource (which is, after all, shared_ptr's +job!) +On multi-processor systems memory synchronisation may be needed so that +reference-count updates and the destruction of the managed resource are +race-free. +</p><p> +The function <code class="function">_Sp_counted_base::_M_add_ref_lock()</code>, called when +obtaining a shared_ptr from a weak_ptr, has to test if the managed +resource still exists and either increment the reference count or throw +<code class="classname">bad_weak_ptr</code>. +In a multi-threaded program there is a potential race condition if the last +reference is dropped (and the managed resource destroyed) between testing +the reference count and incrementing it, which could result in a shared_ptr +pointing to invalid memory. +</p><p> +The Boost shared_ptr (as used in GCC) features a clever lock-free +algorithm to avoid the race condition, but this relies on the +processor supporting an atomic <span class="emphasis"><em>Compare-And-Swap</em></span> +instruction. For other platforms there are fall-backs using mutex +locks. Boost (as of version 1.35) includes several different +implementations and the preprocessor selects one based on the +compiler, standard library, platform etc. For the version of +shared_ptr in libstdc++ the compiler and library are fixed, which +makes things much simpler: we have an atomic CAS or we don't, see Lock +Policy below for details. +</p></div><div class="section" title="Selecting Lock Policy"><div class="titlepage"><div><div><h5 class="title"><a id="id474491"/>Selecting Lock Policy</h5></div></div></div><p> + </p><p> +There is a single <code class="classname">_Sp_counted_base</code> class, +which is a template parameterized on the enum +<span class="type">__gnu_cxx::_Lock_policy</span>. The entire family of classes is +parameterized on the lock policy, right up to +<code class="classname">__shared_ptr</code>, <code class="classname">__weak_ptr</code> and +<code class="classname">__enable_shared_from_this</code>. The actual +<code class="classname">std::shared_ptr</code> class inherits from +<code class="classname">__shared_ptr</code> with the lock policy parameter +selected automatically based on the thread model and platform that +libstdc++ is configured for, so that the best available template +specialization will be used. This design is necessary because it would +not be conforming for <code class="classname">shared_ptr</code> to have an +extra template parameter, even if it had a default value. The +available policies are: + </p><div class="orderedlist"><ol class="orderedlist"><li class="listitem"><p> + <span class="type">_S_Atomic</span> + </p><p> +Selected when GCC supports a builtin atomic compare-and-swap operation +on the target processor (see <a class="link" href="http://gcc.gnu.org/onlinedocs/gcc/Atomic-Builtins.html">Atomic +Builtins</a>.) The reference counts are maintained using a lock-free +algorithm and GCC's atomic builtins, which provide the required memory +synchronisation. + </p></li><li class="listitem"><p> + <span class="type">_S_Mutex</span> + </p><p> +The _Sp_counted_base specialization for this policy contains a mutex, +which is locked in add_ref_lock(). This policy is used when GCC's atomic +builtins aren't available so explicit memory barriers are needed in places. + </p></li><li class="listitem"><p> + <span class="type">_S_Single</span> + </p><p> +This policy uses a non-reentrant add_ref_lock() with no locking. It is +used when libstdc++ is built without <code class="literal">--enable-threads</code>. + </p></li></ol></div><p> + For all three policies, reference count increments and + decrements are done via the functions in + <code class="filename">ext/atomicity.h</code>, which detect if the program + is multi-threaded. If only one thread of execution exists in + the program then less expensive non-atomic operations are used. + </p></div><div class="section" title="Dual C++0x and TR1 Implementation"><div class="titlepage"><div><div><h5 class="title"><a id="id474613"/>Dual C++0x and TR1 Implementation</h5></div></div></div><p> +The interface of <code class="classname">tr1::shared_ptr</code> was extended for C++0x +with support for rvalue-references and the other features from N2351. +The <code class="classname">_Sp_counted_base</code> base class is implemented in +<code class="filename">tr1/boost_sp_shared_count.h</code> and is common to the TR1 +and C++0x versions of <code class="classname">shared_ptr</code>. +</p><p> +The classes derived from <code class="classname">_Sp_counted_base</code> (see Class Hierarchy +above) and <code class="classname">__shared_count</code> are implemented separately for C++0x +and TR1, in <code class="filename">bits/shared_ptr.h</code> and +<code class="filename">tr1/shared_ptr.h</code> respectively. +</p><p> +The TR1 implementation is considered relatively stable, so is unlikely to +change unless bug fixes require it. If the code that is common to both +C++0x and TR1 modes needs to diverge further then it might be necessary to +duplicate <code class="classname">_Sp_counted_base</code> and only make changes to +the C++0x version. +</p></div><div class="section" title="Related functions and classes"><div class="titlepage"><div><div><h5 class="title"><a id="id474669"/>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>, +<code class="code">const_pointer_cast</code></span></dt><dd><p> +As noted in N2351, these functions can be implemented non-intrusively using +the alias constructor. However the aliasing constructor is only available +in C++0x mode, so in TR1 mode these casts rely on three non-standard +constructors in shared_ptr and __shared_ptr. +In C++0x mode these constructors and the related tag types are not needed. + </p></dd><dt><span class="term"><code class="code">enable_shared_from_this</code></span></dt><dd><p> +The clever overload to detect a base class of type +<code class="code">enable_shared_from_this</code> comes straight from Boost. +There is an extra overload for <code class="code">__enable_shared_from_this</code> to +work smoothly with <code class="code">__shared_ptr<Tp, Lp></code> using any lock +policy. + </p></dd><dt><span class="term"><code class="code">make_shared</code>, <code class="code">allocate_shared</code></span></dt><dd><p> +<code class="code">make_shared</code> simply forwards to <code class="code">allocate_shared</code> +with <code class="code">std::allocator</code> as the allocator. +Although these functions can be implemented non-intrusively using the +alias constructor, if they have access to the implementation then it is +possible to save storage and reduce the number of heap allocations. The +newly constructed object and the _Sp_counted_* can be allocated in a single +block and the standard says implementations are "encouraged, but not required," +to do so. This implementation provides additional non-standard constructors +(selected with the type <code class="code">_Sp_make_shared_tag</code>) which create an +object of type <code class="code">_Sp_counted_ptr_inplace</code> to hold the new object. +The returned <code class="code">shared_ptr<A></code> needs to know the address of the +new <code class="code">A</code> object embedded in the <code class="code">_Sp_counted_ptr_inplace</code>, +but it has no way to access it. +This implementation uses a "covert channel" to return the address of the +embedded object when <code class="code">get_deleter<_Sp_make_shared_tag>()</code> +is called. Users should not try to use this. +As well as the extra constructors, this implementation also needs some +members of _Sp_counted_deleter to be protected where they could otherwise +be private. + </p></dd></dl></div></div></div><div class="section" title="Use"><div class="titlepage"><div><div><h4 class="title"><a id="shared_ptr.using"/>Use</h4></div></div></div><div class="section" title="Examples"><div class="titlepage"><div><div><h5 class="title"><a id="id474818"/>Examples</h5></div></div></div><p> + Examples of use can be found in the testsuite, under + <code class="filename">testsuite/tr1/2_general_utilities/shared_ptr</code>, + <code class="filename">testsuite/20_util/shared_ptr</code> + and + <code class="filename">testsuite/20_util/weak_ptr</code>. + </p></div><div class="section" title="Unresolved Issues"><div class="titlepage"><div><div><h5 class="title"><a id="id474848"/>Unresolved Issues</h5></div></div></div><p> + The <span class="emphasis"><em><code class="classname">shared_ptr</code> atomic access</em></span> + clause in the C++0x working draft is not implemented in GCC. + </p><p> + The <span class="type">_S_single</span> policy uses atomics when used in MT + code, because it uses the same dispatcher functions that check + <code class="function">__gthread_active_p()</code>. This could be + addressed by providing template specialisations for some members + of <code class="classname">_Sp_counted_base<_S_single></code>. + </p><p> + Unlike Boost, this implementation does not use separate classes + for the pointer+deleter and pointer+deleter+allocator cases in + C++0x mode, combining both into _Sp_counted_deleter and using + <code class="classname">allocator</code> when the user doesn't specify + an allocator. If it was found to be beneficial an additional + class could easily be added. With the current implementation, + the _Sp_counted_deleter and __shared_count constructors taking a + custom deleter but no allocator are technically redundant and + could be removed, changing callers to always specify an + allocator. If a separate pointer+deleter class was added the + __shared_count constructor would be needed, so it has been kept + for now. + </p><p> + The hack used to get the address of the managed object from + <code class="function">_Sp_counted_ptr_inplace::_M_get_deleter()</code> + is accessible to users. This could be prevented if + <code class="function">get_deleter<_Sp_make_shared_tag>()</code> + always returned NULL, since the hack only needs to work at a + lower level, not in the public API. This wouldn't be difficult, + but hasn't been done since there is no danger of accidental + misuse: users already know they are relying on unsupported + features if they refer to implementation details such as + _Sp_make_shared_tag. + </p><p> + tr1::_Sp_deleter could be a private member of tr1::__shared_count but it + would alter the ABI. + </p></div></div><div class="section" title="Acknowledgments"><div class="titlepage"><div><div><h4 class="title"><a id="shared_ptr.ack"/>Acknowledgments</h4></div></div></div><p> + The original authors of the Boost shared_ptr, which is really nice + code to work with, Peter Dimov in particular for his help and + invaluable advice on thread safety. Phillip Jordan and Paolo + Carlini for the lock policy implementation. + </p></div><div class="bibliography" title="Bibliography"><div class="titlepage"><div><div><h4 class="title"><a id="shared_ptr.biblio"/>Bibliography</h4></div></div></div><div class="biblioentry"><a id="id474942"/><p><span class="biblioid"> + . </span><span class="citetitle"><em class="citetitle"> + Improving shared_ptr for C++0x, Revision 2 + </em>. </span><span class="subtitle"> + N2351 + . </span></p></div><div class="biblioentry"><a id="id474963"/><p><span class="biblioid"> + . </span><span class="citetitle"><em class="citetitle"> + C++ Standard Library Active Issues List + </em>. </span><span class="subtitle"> + N2456 + . </span></p></div><div class="biblioentry"><a id="id474984"/><p><span class="biblioid"> + . </span><span class="citetitle"><em class="citetitle"> + Working Draft, Standard for Programming Language C++ + </em>. </span><span class="subtitle"> + N2461 + . </span></p></div><div class="biblioentry"><a id="id475006"/><p><span class="biblioid">shared_ptr + . </span><span class="citetitle"><em class="citetitle"> + Boost C++ Libraries documentation, shared_ptr + </em>. </span><span class="subtitle"> + N2461 + . </span></p></div></div></div></div><div class="navfooter"><hr/><table width="100%" summary="Navigation footer"><tr><td align="left"><a accesskey="p" href="pairs.html">Prev</a> </td><td align="center"><a accesskey="u" href="utilities.html">Up</a></td><td align="right"> <a accesskey="n" href="traits.html">Next</a></td></tr><tr><td align="left" valign="top">Pairs </td><td align="center"><a accesskey="h" href="../spine.html">Home</a></td><td align="right" valign="top"> Traits</td></tr></table></div></body></html> |