| blob | 72727114ac640b50a6af9e9ad1bac732d368b05b |
2 <!DOCTYPE html
3 PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
7 <head>
18 </head>
19 <body>
24 The latest version of this document is always available at
26 http://gcc.gnu.org/onlinedocs/libstdc++/ext/mt_allocator.html</a>.
27 </em></p>
29 <p><em>
31 </em></p>
33 <!-- ####################################################### -->
34 <hr />
37 </h3>
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, one of the
44 being that 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 __GTHREADS)
49 </p>
51 <p>
52 The aim of this document is to describe - from a application point of
53 view - the "inner workings" of the allocator.
54 </p>
59 </h3>
61 <p>
62 The static variables (pointers to freelists, tuning parameters etc)
63 are initialized to their default values at file scope, i.e.:
64 </p>
66 <pre>
69 </pre>
71 <p>
72 The very first allocate() call will always call the _S_init() function.
73 In order to make sure that this function is called exactly once we make use
74 of a __gthread_once (with _S_once_mt and _S_init as arguments) call in MT
75 applications and check a static bool (_S_initialized) in ST applications.
76 </p>
78 <p>
79 The _S_init() function:
80 - If the GLIBCXX_FORCE_NEW environment variable is set, it sets the bool
81 _S_force_new to true and then returns. This will cause subsequent calls to
82 allocate() to return memory directly from a new() call, and deallocate will
83 only do a delete() call.
84 </p>
86 <p>
87 - If the GLIBCXX_FORCE_NEW environment variable is not set, both ST and MT
88 applications will:
89 - Calculate the number of bins needed. A bin is a specific power of two size
90 of bytes. I.e., by default the allocator will deal with requests of up to
91 128 bytes (or whatever the value of _S_max_bytes is when _S_init() is
92 called). This means that there will be bins of the following sizes
95 - Create the _S_binmap array. All requests are rounded up to the next
97 the "32 byte bin" to be returned to the application. The purpose of
98 _S_binmap is to speed up the process of finding out which bin to use.
100 </p>
101 <p>
102 - Create the _S_bin array. This array consists of bin_records. There will be
103 as many bin_records in this array as the number of bins that we calculated
105 Each bin_record is then initialized:
106 - bin_record->first = An array of pointers to block_records. There will be
107 as many block_records pointers as there are maximum number of threads
108 (in a ST application there is only 1 thread, in a MT application there
109 are _S_max_threads).
110 This holds the pointer to the first free block for each thread in this
111 bin. I.e., if we would like to know where the first free block of size 32
114 The above created block_record pointers members are now initialized to
115 their initial values. I.e. _S_bin[ n ].first[ n ] = NULL;
116 </p>
118 <p>
119 - Additionally a MT application will:
120 - Create a list of free thread id's. The pointer to the first entry
121 is stored in _S_thread_freelist_first. The reason for this approach is
122 that the __gthread_self() call will not return a value that corresponds to
123 the maximum number of threads allowed but rather a process id number or
124 something else. So what we do is that we create a list of thread_records.
125 This list is _S_max_threads long and each entry holds a size_t thread_id
127 Each time a thread calls allocate() or deallocate() we call
128 _S_get_thread_id() which looks at the value of _S_thread_key which is a
129 thread local storage pointer. If this is NULL we know that this is a newly
130 created thread and we pop the first entry from this list and saves the
131 pointer to this record in the _S_thread_key variable. The next time
132 we will get the pointer to the thread_record back and we use the
133 thread_record->thread_id as identification. I.e., the first thread that
134 calls allocate will get the first record in this list and thus be thread
137 When we create the _S_thread_key we also define a destructor
138 (_S_thread_key_destr) which means that when the thread dies, this
139 thread_record is returned to the front of this list and the thread id
140 can then be reused if a new thread is created.
141 This list is protected by a mutex (_S_thread_freelist_mutex) which is only
142 locked when records are removed/added to the list.
143 </p>
144 <p>
145 - Initialize the free and used counters of each bin_record:
146 - bin_record->free = An array of size_t. This keeps track of the number
147 of blocks on a specific thread's freelist in each bin. I.e., if a thread
148 has 12 32-byte blocks on it's freelists and allocates one of these, this
149 counter would be decreased to 11.
151 - bin_record->used = An array of size_t. This keeps track of the number
152 of blocks currently in use of this size by this thread. I.e., if a thread
154 counter will read 678.
156 The above created arrays are now initialized with their initial values.
157 I.e. _S_bin[ n ].free[ n ] = 0;
158 </p>
159 <p>
160 - Initialize the mutex of each bin_record:
161 The bin_record->mutex is used to protect the global freelist. This concept
162 of a global freelist is explained in more detail in the section
163 "A multi threaded example", but basically this mutex is locked whenever
164 a block of memory is retrieved or returned to the global freelist for this
165 specific bin. This only occurs when a number of blocks are grabbed from the
166 global list to a thread specific list or when a thread decides to return
167 some blocks to the global freelist.
168 </p>
171 <a name="st_example">A single threaded example (and a primer for the multi threaded example!)</a>
172 </h3>
174 <p>
175 Let's start by describing how the data on a freelist is laid out in memory.
177 </p>
178 <pre>
179 +----------------+
181 | | |
182 | | |
183 | | |
184 +----------------+ |
185 | thread_id = 3 | |
186 | | |
187 | | |
188 | | |
189 +----------------+ |
190 | DATA | | (A pointer to here is what is returned to the
191 | | | the application when needed)
192 | | |
193 | | |
194 | | |
195 | | |
196 | | |
197 | | |
198 +----------------+ |
199 +----------------+ |
200 | next* |<-+ (If next == NULL it's the last one on the list)
201 | |
202 | |
203 | |
204 +----------------+
205 | thread_id = 3 |
206 | |
207 | |
208 | |
209 +----------------+
210 | DATA |
211 | |
212 | |
213 | |
214 | |
215 | |
216 | |
217 | |
218 +----------------+
219 </pre>
221 <p>
222 With this in mind we simplify things a bit for a while and say that there is
223 only one thread (a ST application). In this case all operations are made to
224 what is referred to as the global pool - thread id 0 (No thread may be
225 assigned this id since they span from 1 to _S_max_threads in a MT application).
226 </p>
227 <p>
228 When the application requests memory (calling allocate()) we first look at the
229 requested size and if this is > _S_max_bytes we call new() directly and return.
230 </p>
231 <p>
232 If the requested size is within limits we start by finding out from which
233 bin we should serve this request by looking in _S_binmap.
234 </p>
235 <p>
236 A quick look at _S_bin[ bin ].first[ 0 ] tells us if there are any blocks of
237 this size on the freelist (0). If this is not NULL - fine, just remove the
238 block that _S_bin[ bin ].first[ 0 ] points to from the list,
239 update _S_bin[ bin ].first[ 0 ] and return a pointer to that blocks data.
240 </p>
241 <p>
242 If the freelist is empty (the pointer is NULL) we must get memory from the
243 system and build us a freelist within this memory. All requests for new memory
244 is made in chunks of _S_chunk_size. Knowing the size of a block_record and
245 the bytes that this bin stores we then calculate how many blocks we can create
246 within this chunk, build the list, remove the first block, update the pointer
247 (_S_bin[ bin ].first[ 0 ]) and return a pointer to that blocks data.
248 </p>
250 <p>
251 Deallocation is equally simple; the pointer is casted back to a block_record
252 pointer, lookup which bin to use based on the size, add the block to the front
253 of the global freelist and update the pointer as needed
254 (_S_bin[ bin ].first[ 0 ]).
255 </p>
257 <p>
258 The decision to add deallocated blocks to the front of the freelist was made
259 after a set of performance measurements that showed that this is roughly 10%
260 faster than maintaining a set of "last pointers" as well.
261 </p>
265 </h3>
267 <p>
268 In the ST example we never used the thread_id variable present in each block.
269 Let's start by explaining the purpose of this in a MT application.
270 </p>
272 <p>
273 The concept of "ownership" was introduced since many MT applications
274 allocate and deallocate memory to shared containers from different
275 threads (such as a cache shared amongst all threads). This introduces
276 a problem if the allocator only returns memory to the current threads
277 freelist (I.e., there might be one thread doing all the allocation and
278 thus obtaining ever more memory from the system and another thread
279 that is getting a longer and longer freelist - this will in the end
280 consume all available memory).
281 </p>
283 <p>
284 Each time a block is moved from the global list (where ownership is
285 irrelevant), to a threads freelist (or when a new freelist is built
286 from a chunk directly onto a threads freelist or when a deallocation
287 occurs on a block which was not allocated by the same thread id as the
288 one doing the deallocation) the thread id is set to the current one.
289 </p>
291 <p>
292 What's the use? Well, when a deallocation occurs we can now look at
293 the thread id and find out if it was allocated by another thread id
294 and decrease the used counter of that thread instead, thus keeping the
295 free and used counters correct. And keeping the free and used counters
296 corrects is very important since the relationship between these two
297 variables decides if memory should be returned to the global pool or
298 not when a deallocation occurs.
299 </p>
301 <p>
302 When the application requests memory (calling allocate()) we first
303 look at the requested size and if this is > _S_max_bytes we call new()
304 directly and return.
305 </p>
307 <p>
308 If the requested size is within limits we start by finding out from which
309 bin we should serve this request by looking in _S_binmap.
310 </p>
312 <p>
313 A call to _S_get_thread_id() returns the thread id for the calling thread
314 (and if no value has been set in _S_thread_key, a new id is assigned and
315 returned).
316 </p>
318 <p>
319 A quick look at _S_bin[ bin ].first[ thread_id ] tells us if there are
320 any blocks of this size on the current threads freelist. If this is
321 not NULL - fine, just remove the block that _S_bin[ bin ].first[
322 thread_id ] points to from the list, update _S_bin[ bin ].first[
323 thread_id ], update the free and used counters and return a pointer to
324 that blocks data.
325 </p>
327 <p>
328 If the freelist is empty (the pointer is NULL) we start by looking at
329 the global freelist (0). If there are blocks available on the global
330 freelist we lock this bins mutex and move up to block_count (the
331 number of blocks of this bins size that will fit into a _S_chunk_size)
332 or until end of list - whatever comes first - to the current threads
333 freelist and at the same time change the thread_id ownership and
334 update the counters and pointers. When the bins mutex has been
335 unlocked, we remove the block that _S_bin[ bin ].first[ thread_id ]
336 points to from the list, update _S_bin[ bin ].first[ thread_id ],
337 update the free and used counters, and return a pointer to that blocks
338 data.
339 </p>
341 <p>
342 The reason that the number of blocks moved to the current threads
343 freelist is limited to block_count is to minimize the chance that a
344 subsequent deallocate() call will return the excess blocks to the
345 global freelist (based on the _S_freelist_headroom calculation, see
346 below).
347 </p>
349 <p>
350 However if there isn't any memory on the global pool we need to get
351 memory from the system - this is done in exactly the same way as in a
352 single threaded application with one major difference; the list built
353 in the newly allocated memory (of _S_chunk_size size) is added to the
354 current threads freelist instead of to the global.
355 </p>
357 <p>
358 The basic process of a deallocation call is simple: always add the
359 block to the front of the current threads freelist and update the
360 counters and pointers (as described earlier with the specific check of
361 ownership that causes the used counter of the thread that originally
362 allocated the block to be decreased instead of the current threads
363 counter).
364 </p>
366 <p>
367 And here comes the free and used counters to service. Each time a
368 deallocation() call is made, the length of the current threads
369 freelist is compared to the amount memory in use by this thread.
370 </p>
372 <p>
373 Let's go back to the example of an application that has one thread
374 that does all the allocations and one that deallocates. Both these
375 threads use say 516 32-byte blocks that was allocated during thread
376 creation for example. Their used counters will both say 516 at this
377 point. The allocation thread now grabs 1000 32-byte blocks and puts
378 them in a shared container. The used counter for this thread is now
379 1516.
380 </p>
382 <p>
383 The deallocation thread now deallocates 500 of these blocks. For each
384 deallocation made the used counter of the allocating thread is
385 decreased and the freelist of the deallocation thread gets longer and
386 longer. But the calculation made in deallocate() will limit the length
387 of the freelist in the deallocation thread to _S_freelist_headroom %
388 of it's used counter. In this case, when the freelist (given that the
391 allocating thread may pick them up and reuse them.
392 </p>
394 <p>
395 In order to reduce lock contention (since this requires this bins
396 mutex to be locked) this operation is also made in chunks of blocks
397 (just like when chunks of blocks are moved from the global freelist to
398 a threads freelist mentioned above). The "formula" used can probably
399 be improved to further reduce the risk of blocks being "bounced back
400 and forth" between freelists.
401 </p>
403 <hr />
406 </p>
409 <!-- ####################################################### -->
411 <hr />
414 Comments and suggestions are welcome, and may be sent to
416 </em></p>
419 </body>
420 </html>