1 <?xml version="1.0" encoding="ISO-8859-1"?>
3 PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
4 "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
6 <html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
8 <meta name="AUTHOR" content="Stefan Olsson <stefan@xapa.se>" />
9 <meta name="KEYWORDS" content="c++, libstdc++, g++, allocator, memory" />
10 <meta name="DESCRIPTION" content="Allocators and allocation" />
11 <meta name="GENERATOR" content="emacs and ten fingers" />
12 <title>A fixed-size, multi-thread optimized allocator</title>
13 <link rel="StyleSheet" href="../lib3styles.css" type="text/css" />
14 <link rel="Start" href="../documentation.html" type="text/html"
15 title="GNU C++ Standard Library" />
16 <link rel="Bookmark" href="howto.html" type="text/html" title="Extensions" />
17 <link rel="Copyright" href="../17_intro/license.html" type="text/html" />
21 <h1 class="centered"><a name="top">A fixed-size, multi-thread optimized allocator</a></h1>
23 <p class="fineprint"><em>
24 The latest version of this document is always available at
25 <a href="http://gcc.gnu.org/onlinedocs/libstdc++/ext/mt_allocator.html">
26 http://gcc.gnu.org/onlinedocs/libstdc++/ext/mt_allocator.html</a>.
30 To the <a href="http://gcc.gnu.org/libstdc++/">libstdc++ homepage</a>.
33 <!-- ####################################################### -->
36 <a name="intro">Introduction</a>
39 <p> The mt allocator [hereinafter referred to simply as "the
40 allocator"] is a fixed size (power of two) allocator that was
41 initially developed specifically to suit the needs of multi threaded
42 applications [hereinafter referred to as an MT application]. Over time
43 the allocator has evolved and been improved in many ways, in
44 particular it now also does a good job in single threaded applications
45 [hereinafter referred to as a ST application]. (Note: In this
46 document, when referring to single threaded applications this also
47 includes applications that are compiled with gcc without thread
48 support enabled. This is accomplished using ifdef's on
49 __GTHREADS). This allocator is tunable, very flexible, and capable of
54 The aim of this document is to describe - from an application point of
55 view - the "inner workings" of the allocator.
59 <a name="design">Design Overview</a>
62 <p> There are three general components to the allocator: a datum
63 describing the characteristics of the memory pool, a policy class
64 containing this pool that links instantiation types to common or
65 individual pools, and a class inheriting from the policy class that is
69 <p>The datum describing pools characteristics is
72 template<bool _Thread>
75 <p> This class is parametrized on thread support, and is explicitly
76 specialized for both multiple threads (with <code>bool==true</code>)
77 and single threads (via <code>bool==false</code>.) It is possible to
78 use a custom pool datum instead of the default class that is provided.
81 <p> There are two distinct policy classes, each of which can be used
82 with either type of underlying pool datum.
86 template<bool _Thread>
87 struct __common_pool_policy
89 template<typename _Tp, bool _Thread>
90 struct __per_type_pool_policy
93 <p> The first policy, <code>__common_pool_policy</code>, implements a
94 common pool. This means that allocators that are instantiated with
95 different types, say <code>char</code> and <code>long</code> will both
96 use the same pool. This is the default policy.
99 <p> The second policy, <code>__per_type_pool_policy</code>, implements
100 a separate pool for each instantiating type. Thus, <code>char</code>
101 and <code>long</code> will use separate pools. This allows per-type
102 tuning, for instance.
105 <p> Putting this all together, the actual allocator class is
108 template<typename _Tp, typename _Poolp = __default_policy>
109 class __mt_alloc : public __mt_alloc_base<_Tp>, _Poolp
111 <p> This class has the interface required for standard library allocator
112 classes, namely member functions <code>allocate</code> and
113 <code>deallocate</code>, plus others.
117 <a name="init">Tunable parameters</a>
120 <p>Certain allocation parameters can be modified, or tuned. There
121 exists a nested <code>struct __pool_base::_Tune</code> that contains all
122 these parameters, which include settings for
126 <li>Maximum bytes before calling <code>::operator new</code> directly</li>
127 <li>Minimum bytes</li>
128 <li>Size of underlying global allocations</li>
129 <li>Maximum number of supported threads</li>
130 <li>Migration of deallocations to the global free list</li>
131 <li>Shunt for global <code>new</code> and <code>delete</code></li>
133 <p>Adjusting parameters for a given instance of an allocator can only
134 happen before any allocations take place, when the allocator itself is
135 initialized. For instance:
138 #include <ext/mt_allocator.h>
148 typedef pod value_type;
149 typedef __gnu_cxx::__mt_alloc<value_type> allocator_type;
150 typedef __gnu_cxx::__pool_base::_Tune tune_type;
153 tune_type t_opt(16, 5120, 32, 5120, 20, 10, false);
154 tune_type t_single(16, 5120, 32, 5120, 1, 10, false);
157 t = allocator_type::_M_get_options();
158 allocator_type::_M_set_options(t_opt);
159 t = allocator_type::_M_get_options();
162 allocator_type::pointer p1 = a.allocate(128);
163 allocator_type::pointer p2 = a.allocate(5128);
165 a.deallocate(p1, 128);
166 a.deallocate(p2, 5128);
173 <a name="init">Initialization</a>
177 The static variables (pointers to freelists, tuning parameters etc)
178 are initialized as above, or are set to the global defaults.
182 The very first allocate() call will always call the
183 _S_initialize_once() function. In order to make sure that this
184 function is called exactly once we make use of a __gthread_once call
185 in MT applications and check a static bool (_S_init) in ST
190 The _S_initialize() function:
191 - If the GLIBCXX_FORCE_NEW environment variable is set, it sets the bool
192 _S_force_new to true and then returns. This will cause subsequent calls to
193 allocate() to return memory directly from a new() call, and deallocate will
194 only do a delete() call.
198 - If the GLIBCXX_FORCE_NEW environment variable is not set, both ST and MT
200 - Calculate the number of bins needed. A bin is a specific power of two size
201 of bytes. I.e., by default the allocator will deal with requests of up to
202 128 bytes (or whatever the value of _S_max_bytes is when _S_init() is
203 called). This means that there will be bins of the following sizes
204 (in bytes): 1, 2, 4, 8, 16, 32, 64, 128.
206 - Create the _S_binmap array. All requests are rounded up to the next
207 "large enough" bin. I.e., a request for 29 bytes will cause a block from
208 the "32 byte bin" to be returned to the application. The purpose of
209 _S_binmap is to speed up the process of finding out which bin to use.
210 I.e., the value of _S_binmap[ 29 ] is initialized to 5 (bin 5 = 32 bytes).
213 - Create the _S_bin array. This array consists of bin_records. There will be
214 as many bin_records in this array as the number of bins that we calculated
215 earlier. I.e., if _S_max_bytes = 128 there will be 8 entries.
216 Each bin_record is then initialized:
217 - bin_record->first = An array of pointers to block_records. There will be
218 as many block_records pointers as there are maximum number of threads
219 (in a ST application there is only 1 thread, in a MT application there
221 This holds the pointer to the first free block for each thread in this
222 bin. I.e., if we would like to know where the first free block of size 32
223 for thread number 3 is we would look this up by: _S_bin[ 5 ].first[ 3 ]
225 The above created block_record pointers members are now initialized to
226 their initial values. I.e. _S_bin[ n ].first[ n ] = NULL;
230 - Additionally a MT application will:
231 - Create a list of free thread id's. The pointer to the first entry
232 is stored in _S_thread_freelist_first. The reason for this approach is
233 that the __gthread_self() call will not return a value that corresponds to
234 the maximum number of threads allowed but rather a process id number or
235 something else. So what we do is that we create a list of thread_records.
236 This list is _S_max_threads long and each entry holds a size_t thread_id
237 which is initialized to 1, 2, 3, 4, 5 and so on up to _S_max_threads.
238 Each time a thread calls allocate() or deallocate() we call
239 _S_get_thread_id() which looks at the value of _S_thread_key which is a
240 thread local storage pointer. If this is NULL we know that this is a newly
241 created thread and we pop the first entry from this list and saves the
242 pointer to this record in the _S_thread_key variable. The next time
243 we will get the pointer to the thread_record back and we use the
244 thread_record->thread_id as identification. I.e., the first thread that
245 calls allocate will get the first record in this list and thus be thread
246 number 1 and will then find the pointer to its first free 32 byte block
247 in _S_bin[ 5 ].first[ 1 ]
248 When we create the _S_thread_key we also define a destructor
249 (_S_thread_key_destr) which means that when the thread dies, this
250 thread_record is returned to the front of this list and the thread id
251 can then be reused if a new thread is created.
252 This list is protected by a mutex (_S_thread_freelist_mutex) which is only
253 locked when records are removed/added to the list.
256 - Initialize the free and used counters of each bin_record:
257 - bin_record->free = An array of size_t. This keeps track of the number
258 of blocks on a specific thread's freelist in each bin. I.e., if a thread
259 has 12 32-byte blocks on it's freelists and allocates one of these, this
260 counter would be decreased to 11.
262 - bin_record->used = An array of size_t. This keeps track of the number
263 of blocks currently in use of this size by this thread. I.e., if a thread
264 has made 678 requests (and no deallocations...) of 32-byte blocks this
265 counter will read 678.
267 The above created arrays are now initialized with their initial values.
268 I.e. _S_bin[ n ].free[ n ] = 0;
271 - Initialize the mutex of each bin_record: The bin_record->mutex
272 is used to protect the global freelist. This concept of a global
273 freelist is explained in more detail in the section "A multi
274 threaded example", but basically this mutex is locked whenever a
275 block of memory is retrieved or returned to the global freelist
276 for this specific bin. This only occurs when a number of blocks
277 are grabbed from the global list to a thread specific list or when
278 a thread decides to return some blocks to the global freelist.
281 <p> Notes about deallocation. This allocator does not explicitly
282 release memory. Because of this, memory debugging programs like
283 valgrind or purify may notice leaks: sorry about this
284 inconvenience. Operating systems will reclaim allocated memory at
285 program termination anyway. If sidestepping this kind of noise is
286 desired, there are three options: use an allocator, like
287 <code>new_allocator</code> that releases memory while debugging, use
288 GLIBCXX_FORCE_NEW to bypass the allocator's internal pools, or use a
289 custom pool datum that releases resources on destruction.</p>
291 <p>On systems with the function <code>__cxa_atexit</code>, the
292 allocator can be forced to free all memory allocated before program
293 termination with the member function
294 <code>__pool_type::_M_destroy</code>. However, because this member
295 function relies on the precise and exactly-conforming ordering of
296 static destructors, including those of a static local
297 <code>__pool</code> object, it should not be used, ever, on systems
298 that don't have the necessary underlying support. In addition, in
299 practice, forcing deallocation can be tricky, as it requires the
300 <code>__pool</code> object to be fully-constructed before the object
301 that uses it is fully constructed. For most (but not all) STL
302 containers, this works, as an instance of the allocator is constructed
303 as part of a container's constructor. However, this assumption is
304 implementation-specific, and subject to change. For an example of a
305 pool that frees memory, see the following
306 <a href="http://gcc.gnu.org/viewcvs/trunk/libstdc%2B%2B-v3/testsuite/ext/mt_allocator/deallocate_local-6.cc?view=markup">
311 <a name="st_example">A single threaded example (and a primer for the multi threaded example!)</a>
315 Let's start by describing how the data on a freelist is laid out in memory.
316 This is the first two blocks in freelist for thread id 3 in bin 3 (8 bytes):
320 | next* ---------|--+ (_S_bin[ 3 ].first[ 3 ] points here)
330 | DATA | | (A pointer to here is what is returned to the
331 | | | the application when needed)
340 | next* |<-+ (If next == NULL it's the last one on the list)
362 With this in mind we simplify things a bit for a while and say that there is
363 only one thread (a ST application). In this case all operations are made to
364 what is referred to as the global pool - thread id 0 (No thread may be
365 assigned this id since they span from 1 to _S_max_threads in a MT application).
368 When the application requests memory (calling allocate()) we first look at the
369 requested size and if this is > _S_max_bytes we call new() directly and return.
372 If the requested size is within limits we start by finding out from which
373 bin we should serve this request by looking in _S_binmap.
376 A quick look at _S_bin[ bin ].first[ 0 ] tells us if there are any blocks of
377 this size on the freelist (0). If this is not NULL - fine, just remove the
378 block that _S_bin[ bin ].first[ 0 ] points to from the list,
379 update _S_bin[ bin ].first[ 0 ] and return a pointer to that blocks data.
382 If the freelist is empty (the pointer is NULL) we must get memory from the
383 system and build us a freelist within this memory. All requests for new memory
384 is made in chunks of _S_chunk_size. Knowing the size of a block_record and
385 the bytes that this bin stores we then calculate how many blocks we can create
386 within this chunk, build the list, remove the first block, update the pointer
387 (_S_bin[ bin ].first[ 0 ]) and return a pointer to that blocks data.
391 Deallocation is equally simple; the pointer is casted back to a block_record
392 pointer, lookup which bin to use based on the size, add the block to the front
393 of the global freelist and update the pointer as needed
394 (_S_bin[ bin ].first[ 0 ]).
398 The decision to add deallocated blocks to the front of the freelist was made
399 after a set of performance measurements that showed that this is roughly 10%
400 faster than maintaining a set of "last pointers" as well.
404 <a name="mt_example">A multi threaded example</a>
408 In the ST example we never used the thread_id variable present in each block.
409 Let's start by explaining the purpose of this in a MT application.
413 The concept of "ownership" was introduced since many MT applications
414 allocate and deallocate memory to shared containers from different
415 threads (such as a cache shared amongst all threads). This introduces
416 a problem if the allocator only returns memory to the current threads
417 freelist (I.e., there might be one thread doing all the allocation and
418 thus obtaining ever more memory from the system and another thread
419 that is getting a longer and longer freelist - this will in the end
420 consume all available memory).
424 Each time a block is moved from the global list (where ownership is
425 irrelevant), to a threads freelist (or when a new freelist is built
426 from a chunk directly onto a threads freelist or when a deallocation
427 occurs on a block which was not allocated by the same thread id as the
428 one doing the deallocation) the thread id is set to the current one.
432 What's the use? Well, when a deallocation occurs we can now look at
433 the thread id and find out if it was allocated by another thread id
434 and decrease the used counter of that thread instead, thus keeping the
435 free and used counters correct. And keeping the free and used counters
436 corrects is very important since the relationship between these two
437 variables decides if memory should be returned to the global pool or
438 not when a deallocation occurs.
442 When the application requests memory (calling allocate()) we first
443 look at the requested size and if this is > _S_max_bytes we call new()
448 If the requested size is within limits we start by finding out from which
449 bin we should serve this request by looking in _S_binmap.
453 A call to _S_get_thread_id() returns the thread id for the calling thread
454 (and if no value has been set in _S_thread_key, a new id is assigned and
459 A quick look at _S_bin[ bin ].first[ thread_id ] tells us if there are
460 any blocks of this size on the current threads freelist. If this is
461 not NULL - fine, just remove the block that _S_bin[ bin ].first[
462 thread_id ] points to from the list, update _S_bin[ bin ].first[
463 thread_id ], update the free and used counters and return a pointer to
468 If the freelist is empty (the pointer is NULL) we start by looking at
469 the global freelist (0). If there are blocks available on the global
470 freelist we lock this bins mutex and move up to block_count (the
471 number of blocks of this bins size that will fit into a _S_chunk_size)
472 or until end of list - whatever comes first - to the current threads
473 freelist and at the same time change the thread_id ownership and
474 update the counters and pointers. When the bins mutex has been
475 unlocked, we remove the block that _S_bin[ bin ].first[ thread_id ]
476 points to from the list, update _S_bin[ bin ].first[ thread_id ],
477 update the free and used counters, and return a pointer to that blocks
482 The reason that the number of blocks moved to the current threads
483 freelist is limited to block_count is to minimize the chance that a
484 subsequent deallocate() call will return the excess blocks to the
485 global freelist (based on the _S_freelist_headroom calculation, see
490 However if there isn't any memory on the global pool we need to get
491 memory from the system - this is done in exactly the same way as in a
492 single threaded application with one major difference; the list built
493 in the newly allocated memory (of _S_chunk_size size) is added to the
494 current threads freelist instead of to the global.
498 The basic process of a deallocation call is simple: always add the
499 block to the front of the current threads freelist and update the
500 counters and pointers (as described earlier with the specific check of
501 ownership that causes the used counter of the thread that originally
502 allocated the block to be decreased instead of the current threads
507 And here comes the free and used counters to service. Each time a
508 deallocation() call is made, the length of the current threads
509 freelist is compared to the amount memory in use by this thread.
513 Let's go back to the example of an application that has one thread
514 that does all the allocations and one that deallocates. Both these
515 threads use say 516 32-byte blocks that was allocated during thread
516 creation for example. Their used counters will both say 516 at this
517 point. The allocation thread now grabs 1000 32-byte blocks and puts
518 them in a shared container. The used counter for this thread is now
523 The deallocation thread now deallocates 500 of these blocks. For each
524 deallocation made the used counter of the allocating thread is
525 decreased and the freelist of the deallocation thread gets longer and
526 longer. But the calculation made in deallocate() will limit the length
527 of the freelist in the deallocation thread to _S_freelist_headroom %
528 of it's used counter. In this case, when the freelist (given that the
529 _S_freelist_headroom is at it's default value of 10%) exceeds 52
530 (516/10) blocks will be returned to the global pool where the
531 allocating thread may pick them up and reuse them.
535 In order to reduce lock contention (since this requires this bins
536 mutex to be locked) this operation is also made in chunks of blocks
537 (just like when chunks of blocks are moved from the global freelist to
538 a threads freelist mentioned above). The "formula" used can probably
539 be improved to further reduce the risk of blocks being "bounced back
540 and forth" between freelists.
544 <p>Return <a href="#top">to the top of the page</a> or
545 <a href="http://gcc.gnu.org/libstdc++/">to the libstdc++ homepage</a>.
549 <!-- ####################################################### -->
552 <p class="fineprint"><em>
553 See <a href="../17_intro/license.html">license.html</a> for copying conditions.
554 Comments and suggestions are welcome, and may be sent to
555 <a href="mailto:libstdc++@gcc.gnu.org">the libstdc++ mailing list</a>.
OSDN Git Service
