1<?xml version="1.0" encoding="UTF-8" standalone="no"?> 2<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"><html xmlns="http://www.w3.org/1999/xhtml"><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8" /><title>Implementation</title><meta name="generator" content="DocBook XSL Stylesheets Vsnapshot" /><meta name="keywords" content="ISO C++, allocator" /><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="mt_allocator.html" title="Chapter��19.��The mt_allocator" /><link rel="prev" href="mt_allocator_design.html" title="Design Issues" /><link rel="next" href="mt_allocator_ex_single.html" title="Single Thread Example" /></head><body><div class="navheader"><table width="100%" summary="Navigation header"><tr><th colspan="3" align="center">Implementation</th></tr><tr><td width="20%" align="left"><a accesskey="p" href="mt_allocator_design.html">Prev</a>��</td><th width="60%" align="center">Chapter��19.��The mt_allocator</th><td width="20%" align="right">��<a accesskey="n" href="mt_allocator_ex_single.html">Next</a></td></tr></table><hr /></div><div class="section"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a id="allocator.mt.impl"></a>Implementation</h2></div></div></div><div class="section"><div class="titlepage"><div><div><h3 class="title"><a id="allocator.mt.tune"></a>Tunable Parameters</h3></div></div></div><p>Certain allocation parameters can be modified, or tuned. There 3exists a nested <code class="code">struct __pool_base::_Tune</code> that contains all 4these parameters, which include settings for 5</p><div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "><li class="listitem"><p>Alignment</p></li><li class="listitem"><p>Maximum bytes before calling <code class="code">::operator new</code> directly</p></li><li class="listitem"><p>Minimum bytes</p></li><li class="listitem"><p>Size of underlying global allocations</p></li><li class="listitem"><p>Maximum number of supported threads</p></li><li class="listitem"><p>Migration of deallocations to the global free list</p></li><li class="listitem"><p>Shunt for global <code class="code">new</code> and <code class="code">delete</code></p></li></ul></div><p>Adjusting parameters for a given instance of an allocator can only 6happen before any allocations take place, when the allocator itself is 7initialized. For instance: 8</p><pre class="programlisting"> 9#include <ext/mt_allocator.h> 10 11struct pod 12{ 13 int i; 14 int j; 15}; 16 17int main() 18{ 19 typedef pod value_type; 20 typedef __gnu_cxx::__mt_alloc<value_type> allocator_type; 21 typedef __gnu_cxx::__pool_base::_Tune tune_type; 22 23 tune_type t_default; 24 tune_type t_opt(16, 5120, 32, 5120, 20, 10, false); 25 tune_type t_single(16, 5120, 32, 5120, 1, 10, false); 26 27 tune_type t; 28 t = allocator_type::_M_get_options(); 29 allocator_type::_M_set_options(t_opt); 30 t = allocator_type::_M_get_options(); 31 32 allocator_type a; 33 allocator_type::pointer p1 = a.allocate(128); 34 allocator_type::pointer p2 = a.allocate(5128); 35 36 a.deallocate(p1, 128); 37 a.deallocate(p2, 5128); 38 39 return 0; 40} 41</pre></div><div class="section"><div class="titlepage"><div><div><h3 class="title"><a id="allocator.mt.init"></a>Initialization</h3></div></div></div><p> 42The static variables (pointers to freelists, tuning parameters etc) 43are initialized as above, or are set to the global defaults. 44</p><p> 45The very first allocate() call will always call the 46_S_initialize_once() function. In order to make sure that this 47function is called exactly once we make use of a __gthread_once call 48in MT applications and check a static bool (_S_init) in ST 49applications. 50</p><p> 51The _S_initialize() function: 52- If the GLIBCXX_FORCE_NEW environment variable is set, it sets the bool 53 _S_force_new to true and then returns. This will cause subsequent calls to 54 allocate() to return memory directly from a new() call, and deallocate will 55 only do a delete() call. 56</p><p> 57- If the GLIBCXX_FORCE_NEW environment variable is not set, both ST and MT 58 applications will: 59 - Calculate the number of bins needed. A bin is a specific power of two size 60 of bytes. I.e., by default the allocator will deal with requests of up to 61 128 bytes (or whatever the value of _S_max_bytes is when _S_init() is 62 called). This means that there will be bins of the following sizes 63 (in bytes): 1, 2, 4, 8, 16, 32, 64, 128. 64 65 - Create the _S_binmap array. All requests are rounded up to the next 66 "large enough" bin. I.e., a request for 29 bytes will cause a block from 67 the "32 byte bin" to be returned to the application. The purpose of 68 _S_binmap is to speed up the process of finding out which bin to use. 69 I.e., the value of _S_binmap[ 29 ] is initialized to 5 (bin 5 = 32 bytes). 70</p><p> 71 - Create the _S_bin array. This array consists of bin_records. There will be 72 as many bin_records in this array as the number of bins that we calculated 73 earlier. I.e., if _S_max_bytes = 128 there will be 8 entries. 74 Each bin_record is then initialized: 75 - bin_record->first = An array of pointers to block_records. There will be 76 as many block_records pointers as there are maximum number of threads 77 (in a ST application there is only 1 thread, in a MT application there 78 are _S_max_threads). 79 This holds the pointer to the first free block for each thread in this 80 bin. I.e., if we would like to know where the first free block of size 32 81 for thread number 3 is we would look this up by: _S_bin[ 5 ].first[ 3 ] 82 83 The above created block_record pointers members are now initialized to 84 their initial values. I.e. _S_bin[ n ].first[ n ] = NULL; 85</p><p> 86- Additionally a MT application will: 87 - Create a list of free thread id's. The pointer to the first entry 88 is stored in _S_thread_freelist_first. The reason for this approach is 89 that the __gthread_self() call will not return a value that corresponds to 90 the maximum number of threads allowed but rather a process id number or 91 something else. So what we do is that we create a list of thread_records. 92 This list is _S_max_threads long and each entry holds a size_t thread_id 93 which is initialized to 1, 2, 3, 4, 5 and so on up to _S_max_threads. 94 Each time a thread calls allocate() or deallocate() we call 95 _S_get_thread_id() which looks at the value of _S_thread_key which is a 96 thread local storage pointer. If this is NULL we know that this is a newly 97 created thread and we pop the first entry from this list and saves the 98 pointer to this record in the _S_thread_key variable. The next time 99 we will get the pointer to the thread_record back and we use the 100 thread_record->thread_id as identification. I.e., the first thread that 101 calls allocate will get the first record in this list and thus be thread 102 number 1 and will then find the pointer to its first free 32 byte block 103 in _S_bin[ 5 ].first[ 1 ] 104 When we create the _S_thread_key we also define a destructor 105 (_S_thread_key_destr) which means that when the thread dies, this 106 thread_record is returned to the front of this list and the thread id 107 can then be reused if a new thread is created. 108 This list is protected by a mutex (_S_thread_freelist_mutex) which is only 109 locked when records are removed or added to the list. 110</p><p> 111 - Initialize the free and used counters of each bin_record: 112 - bin_record->free = An array of size_t. This keeps track of the number 113 of blocks on a specific thread's freelist in each bin. I.e., if a thread 114 has 12 32-byte blocks on it's freelists and allocates one of these, this 115 counter would be decreased to 11. 116 117 - bin_record->used = An array of size_t. This keeps track of the number 118 of blocks currently in use of this size by this thread. I.e., if a thread 119 has made 678 requests (and no deallocations...) of 32-byte blocks this 120 counter will read 678. 121 122 The above created arrays are now initialized with their initial values. 123 I.e. _S_bin[ n ].free[ n ] = 0; 124</p><p> 125 - Initialize the mutex of each bin_record: The bin_record->mutex 126 is used to protect the global freelist. This concept of a global 127 freelist is explained in more detail in the section "A multi 128 threaded example", but basically this mutex is locked whenever a 129 block of memory is retrieved or returned to the global freelist 130 for this specific bin. This only occurs when a number of blocks 131 are grabbed from the global list to a thread specific list or when 132 a thread decides to return some blocks to the global freelist. 133</p></div><div class="section"><div class="titlepage"><div><div><h3 class="title"><a id="allocator.mt.deallocation"></a>Deallocation Notes</h3></div></div></div><p> Notes about deallocation. This allocator does not explicitly 134release memory back to the OS, but keeps its own freelists instead. 135Because of this, memory debugging programs like 136valgrind or purify may notice leaks: sorry about this 137inconvenience. Operating systems will reclaim allocated memory at 138program termination anyway. If sidestepping this kind of noise is 139desired, there are three options: use an allocator, like 140<code class="code">new_allocator</code> that releases memory while debugging, use 141GLIBCXX_FORCE_NEW to bypass the allocator's internal pools, or use a 142custom pool datum that releases resources on destruction. 143</p><p> 144 On systems with the function <code class="code">__cxa_atexit</code>, the 145allocator can be forced to free all memory allocated before program 146termination with the member function 147<code class="code">__pool_type::_M_destroy</code>. However, because this member 148function relies on the precise and exactly-conforming ordering of 149static destructors, including those of a static local 150<code class="code">__pool</code> object, it should not be used, ever, on systems 151that don't have the necessary underlying support. In addition, in 152practice, forcing deallocation can be tricky, as it requires the 153<code class="code">__pool</code> object to be fully-constructed before the object 154that uses it is fully constructed. For most (but not all) STL 155containers, this works, as an instance of the allocator is constructed 156as part of a container's constructor. However, this assumption is 157implementation-specific, and subject to change. For an example of a 158pool that frees memory, see the following 159 <a class="link" href="http://gcc.gnu.org/viewcvs/gcc/trunk/libstdc++-v3/testsuite/ext/mt_allocator/deallocate_local-6.cc?view=markup" target="_top"> 160 example.</a> 161</p></div></div><div class="navfooter"><hr /><table width="100%" summary="Navigation footer"><tr><td width="40%" align="left"><a accesskey="p" href="mt_allocator_design.html">Prev</a>��</td><td width="20%" align="center"><a accesskey="u" href="mt_allocator.html">Up</a></td><td width="40%" align="right">��<a accesskey="n" href="mt_allocator_ex_single.html">Next</a></td></tr><tr><td width="40%" align="left" valign="top">Design Issues��</td><td width="20%" align="center"><a accesskey="h" href="../index.html">Home</a></td><td width="40%" align="right" valign="top">��Single Thread Example</td></tr></table></div></body></html>