OSDN Git Service

2008-04-10 Benjamin Kosnik <bkoz@redhat.com>
[pf3gnuchains/gcc-fork.git] / libstdc++-v3 / doc / xml / manual / bitmap_allocator.xml
1 <sect1 id="manual.ext.allocator.bitmap" xreflabel="mt allocator">
2 <?dbhtml filename="bitmap_allocator.html"?>
3  
4 <sect1info>
5   <keywordset>
6     <keyword>
7       ISO C++
8     </keyword>
9     <keyword>
10       allocator
11     </keyword>
12   </keywordset>
13 </sect1info>
14
15 <title>bitmap_allocator</title>
16
17 <para>
18 </para>
19
20 <sect2 id="allocator.bitmap.design" xreflabel="allocator.bitmap.design">
21 <title>Design</title>
22
23   <para>
24     As this name suggests, this allocator uses a bit-map to keep track
25     of the used and unused memory locations for it's book-keeping
26     purposes.
27   </para>
28   <para>
29     This allocator will make use of 1 single bit to keep track of
30     whether it has been allocated or not. A bit 1 indicates free,
31     while 0 indicates allocated. This has been done so that you can
32     easily check a collection of bits for a free block. This kind of
33     Bitmapped strategy works best for single object allocations, and
34     with the STL type parameterized allocators, we do not need to
35     choose any size for the block which will be represented by a
36     single bit. This will be the size of the parameter around which
37     the allocator has been parameterized. Thus, close to optimal
38     performance will result. Hence, this should be used for node based
39     containers which call the allocate function with an argument of 1.
40   </para>
41
42   <para>
43     The bitmapped allocator's internal pool is exponentially growing.
44     Meaning that internally, the blocks acquired from the Free List
45     Store will double every time the bitmapped allocator runs out of
46     memory.
47   </para>
48
49   <para>
50     The macro <literal>__GTHREADS</literal> decides whether to use
51     Mutex Protection around every allocation/deallocation. The state
52     of the macro is picked up automatically from the gthr abstraction
53     layer.
54   </para>
55
56 </sect2>
57
58 <sect2 id="allocator.bitmap.impl" xreflabel="allocator.bitmap.impl">
59 <title>Implementation</title>
60
61 <sect3 id="bitmap.impl.free_list_store" xreflabel="Free List Store">
62   <title>Free List Store</title>
63
64   <para>
65     The Free List Store (referred to as FLS for the remaining part of this
66     document) is the Global memory pool that is shared by all instances of
67     the bitmapped allocator instantiated for any type. This maintains a
68     sorted order of all free memory blocks given back to it by the
69     bitmapped allocator, and is also responsible for giving memory to the
70     bitmapped allocator when it asks for more.
71   </para>
72   <para>
73     Internally, there is a Free List threshold which indicates the
74     Maximum number of free lists that the FLS can hold internally
75     (cache).  Currently, this value is set at 64. So, if there are
76     more than 64 free lists coming in, then some of them will be given
77     back to the OS using operator delete so that at any given time the
78     Free List's size does not exceed 64 entries. This is done because
79     a Binary Search is used to locate an entry in a free list when a
80     request for memory comes along.  Thus, the run-time complexity of
81     the search would go up given an increasing size, for 64 entries
82     however, lg(64) == 6 comparisons are enough to locate the correct
83     free list if it exists.
84   </para>  
85   <para>
86     Suppose the free list size has reached it's threshold, then the
87     largest block from among those in the list and the new block will
88     be selected and given back to the OS. This is done because it
89     reduces external fragmentation, and allows the OS to use the
90     larger blocks later in an orderly fashion, possibly merging them
91     later. Also, on some systems, large blocks are obtained via calls
92     to mmap, so giving them back to free system resources becomes most
93     important.
94   </para>
95   <para>
96     The function _S_should_i_give decides the policy that determines
97     whether the current block of memory should be given to the
98     allocator for the request that it has made. That's because we may
99     not always have exact fits for the memory size that the allocator
100     requests. We do this mainly to prevent external fragmentation at
101     the cost of a little internal fragmentation. Now, the value of
102     this internal fragmentation has to be decided by this function. I
103     can see 3 possibilities right now. Please add more as and when you
104     find better strategies.
105   </para>
106
107 <orderedlist>
108   <listitem><para>Equal size check. Return true only when the 2 blocks are of equal
109 size.</para></listitem>
110   <listitem><para>Difference Threshold: Return true only when the _block_size is
111 greater than or equal to the _required_size, and if the _BS is &gt; _RS
112 by a difference of less than some THRESHOLD value, then return true,
113 else return false. </para></listitem>
114   <listitem><para>Percentage Threshold. Return true only when the _block_size is
115 greater than or equal to the _required_size, and if the _BS is &gt; _RS
116 by a percentage of less than some THRESHOLD value, then return true,
117 else return false.</para></listitem>
118 </orderedlist>
119
120   <para>
121     Currently, (3) is being used with a value of 36% Maximum wastage per
122     Super Block.
123   </para>
124 </sect3>
125
126 <sect3 id="bitmap.impl.super_block" xreflabel="Super Block">
127   <title>Super Block</title>
128
129   <para>
130     A super block is the block of memory acquired from the FLS from
131     which the bitmap allocator carves out memory for single objects
132     and satisfies the user's requests. These super blocks come in
133     sizes that are powers of 2 and multiples of 32
134     (_Bits_Per_Block). Yes both at the same time!  That's because the
135     next super block acquired will be 2 times the previous one, and
136     also all super blocks have to be multiples of the _Bits_Per_Block
137     value.
138   </para>
139   <para>
140     How does it interact with the free list store?
141   </para>
142   <para>
143     The super block is contained in the FLS, and the FLS is responsible for
144     getting / returning Super Bocks to and from the OS using operator new
145     as defined by the C++ standard.
146   </para>
147 </sect3>
148
149 <sect3 id="bitmap.impl.super_block_data" xreflabel="Super Block Data">
150   <title>Super Block Data Layout</title>
151   <para>
152     Each Super Block will be of some size that is a multiple of the
153     number of Bits Per Block. Typically, this value is chosen as
154     Bits_Per_Byte x sizeof(size_t). On an x86 system, this gives the
155     figure 8 x 4 = 32. Thus, each Super Block will be of size 32
156     x Some_Value. This Some_Value is sizeof(value_type). For now, let
157     it be called 'K'. Thus, finally, Super Block size is 32 x K bytes.
158   </para>
159   <para>
160     This value of 32 has been chosen because each size_t has 32-bits
161     and Maximum use of these can be made with such a figure.
162   </para>
163   <para>
164     Consider a block of size 64 ints. In memory, it would look like this:
165     (assume a 32-bit system where, size_t is a 32-bit entity).
166   </para>
167
168 <table frame='all'>
169 <title>Bitmap Allocator Memory Map</title>
170 <tgroup cols='5' align='left' colsep='1' rowsep='1'>
171 <colspec colname='c1'></colspec>
172 <colspec colname='c2'></colspec>
173 <colspec colname='c3'></colspec>
174 <colspec colname='c4'></colspec>
175 <colspec colname='c5'></colspec>
176
177 <tbody>
178   <row>
179     <entry>268</entry>
180     <entry>0</entry>
181     <entry>4294967295</entry>
182     <entry>4294967295</entry>
183     <entry>Data -&gt; Space for 64 ints</entry>
184   </row>
185 </tbody>
186 </tgroup>
187 </table>
188
189   <para>
190     The first Column(268) represents the size of the Block in bytes as
191     seen by the Bitmap Allocator. Internally, a global free list is
192     used to keep track of the free blocks used and given back by the
193     bitmap allocator.  It is this Free List Store that is responsible
194     for writing and managing this information. Actually the number of
195     bytes allocated in this case would be: 4 + 4 + (4x2) + (64x4) =
196     272 bytes, but the first 4 bytes are an addition by the Free List
197     Store, so the Bitmap Allocator sees only 268 bytes. These first 4
198     bytes about which the bitmapped allocator is not aware hold the
199     value 268.
200   </para>
201
202   <para>
203   What do the remaining values represent?</para>
204   <para>
205     The 2nd 4 in the expression is the sizeof(size_t) because the
206     Bitmapped Allocator maintains a used count for each Super Block,
207     which is initially set to 0 (as indicated in the diagram). This is
208     incremented every time a block is removed from this super block
209     (allocated), and decremented whenever it is given back. So, when
210     the used count falls to 0, the whole super block will be given
211     back to the Free List Store.
212   </para>
213   <para>
214     The value 4294967295 represents the integer corresponding to the bit
215     representation of all bits set: 11111111111111111111111111111111.
216   </para>
217   <para>
218     The 3rd 4x2 is size of the bitmap itself, which is the size of 32-bits
219     x 2,
220     which is 8-bytes, or 2 x sizeof(size_t).
221   </para>
222 </sect3>
223
224 <sect3 id="bitmap.impl.max_wasted" xreflabel="Max Wasted Percentage">
225   <title>Maximum Wasted Percentage</title>
226  
227   <para>
228     This has nothing to do with the algorithm per-se,
229     only with some vales that must be chosen correctly to ensure that the
230     allocator performs well in a real word scenario, and maintains a good
231     balance between the memory consumption and the allocation/deallocation
232     speed.
233   </para>
234   <para>
235     The formula for calculating the maximum wastage as a percentage:
236   </para>
237
238   <para>
239 (32 x k + 1) / (2 x (32 x k + 1 + 32 x c)) x 100.
240   </para>
241
242   <para>
243     where k is the constant overhead per node (e.g., for list, it is
244     8 bytes, and for map it is 12 bytes) and c is the size of the
245     base type on which the map/list is instantiated. Thus, suppose the
246     type1 is int and type2 is double, they are related by the relation
247     sizeof(double) == 2*sizeof(int). Thus, all types must have this
248     double size relation for this formula to work properly.
249   </para>
250   <para>
251     Plugging-in: For List: k = 8 and c = 4 (int and double), we get:
252     33.376%
253   </para>
254
255   <para>
256 For map/multimap: k = 12, and c = 4 (int and double), we get: 37.524%
257   </para>
258   <para>
259     Thus, knowing these values, and based on the sizeof(value_type), we may
260     create a function that returns the Max_Wastage_Percentage for us to use.
261   </para>
262
263 </sect3>
264
265 <sect3 id="bitmap.impl.allocate" xreflabel="Allocate">
266   <title><function>allocate</function></title>
267
268   <para>
269     The allocate function is specialized for single object allocation
270     ONLY.  Thus, ONLY if n == 1, will the bitmap_allocator's
271     specialized algorithm be used. Otherwise, the request is satisfied
272     directly by calling operator new.
273   </para>
274   <para>
275     Suppose n == 1, then the allocator does the following:
276   </para>
277   <orderedlist>
278     <listitem>
279       <para>
280         Checks to see whether a free block exists somewhere in a region
281         of memory close to the last satisfied request. If so, then that
282         block is marked as allocated in the bit map and given to the
283         user. If not, then (2) is executed.
284     </para>
285     </listitem>
286     <listitem>
287       <para>
288         Is there a free block anywhere after the current block right
289         up to the end of the memory that we have? If so, that block is
290         found, and the same procedure is applied as above, and
291         returned to the user. If not, then (3) is executed.
292     </para>
293     </listitem>
294     <listitem>
295       <para>
296         Is there any block in whatever region of memory that we own
297         free?  This is done by checking
298       </para>
299       <itemizedlist>
300         <listitem>
301         <para>
302         The use count for each super block, and if that fails then
303         </para>
304         </listitem>
305         <listitem>
306         <para>
307           The individual bit-maps for each super block.
308         </para>
309         </listitem>
310       </itemizedlist>
311
312       <para>
313         Note: Here we are never touching any of the memory that the
314         user will be given, and we are confining all memory accesses
315         to a small region of memory! This helps reduce cache
316         misses. If this succeeds then we apply the same procedure on
317         that bit-map as (1), and return that block of memory to the
318         user. However, if this process fails, then we resort to (4).
319         </para>
320     </listitem>
321     <listitem>
322       <para>
323         This process involves Refilling the internal exponentially
324         growing memory pool. The said effect is achieved by calling
325         _S_refill_pool which does the following:
326       </para>
327       <itemizedlist>
328         <listitem>
329           <para>
330             Gets more memory from the Global Free List of the Required
331             size.  
332           </para>
333         </listitem>
334       <listitem>
335       <para>
336       Adjusts the size for the next call to itself. 
337       </para>
338       </listitem>
339       <listitem>
340       <para>
341       Writes the appropriate headers in the bit-maps.
342       </para>
343       </listitem>
344       <listitem>
345         <para>
346         Sets the use count for that super-block just allocated to 0
347         (zero).  
348       </para>
349       </listitem>
350       <listitem>
351         <para>
352           All of the above accounts to maintaining the basic invariant
353           for the allocator. If the invariant is maintained, we are
354           sure that all is well. Now, the same process is applied on
355           the newly acquired free blocks, which are dispatched
356           accordingly.  
357       </para>
358       </listitem>
359     </itemizedlist>
360     </listitem>
361 </orderedlist>
362
363 <para>
364 Thus, you can clearly see that the allocate function is nothing but a
365 combination of the next-fit and first-fit algorithm optimized ONLY for
366 single object allocations.
367 </para>
368
369 </sect3>
370
371 <sect3 id="bitmap.impl.deallocate" xreflabel="Deallocate">
372   <title><function>deallocate</function></title>
373   <para>
374     The deallocate function again is specialized for single objects ONLY.
375     For all n belonging to &gt; 1, the operator delete is called without
376     further ado, and the deallocate function returns.
377   </para>
378   <para>
379     However for n == 1, a series of steps are performed:
380   </para>
381   
382   <orderedlist>
383     <listitem><para>
384       We first need to locate that super-block which holds the memory
385       location given to us by the user. For that purpose, we maintain
386       a static variable _S_last_dealloc_index, which holds the index
387       into the vector of block pairs which indicates the index of the
388       last super-block from which memory was freed. We use this
389       strategy in the hope that the user will deallocate memory in a
390       region close to what he/she deallocated the last time around. If
391       the check for belongs_to succeeds, then we determine the bit-map
392       for the given pointer, and locate the index into that bit-map,
393       and mark that bit as free by setting it.
394     </para></listitem>
395     <listitem><para>
396       If the _S_last_dealloc_index does not point to the memory block
397       that we're looking for, then we do a linear search on the block
398       stored in the vector of Block Pairs. This vector in code is
399       called _S_mem_blocks. When the corresponding super-block is
400       found, we apply the same procedure as we did for (1) to mark the
401       block as free in the bit-map.
402     </para></listitem>
403   </orderedlist>
404
405   <para>
406     Now, whenever a block is freed, the use count of that particular
407     super block goes down by 1. When this use count hits 0, we remove
408     that super block from the list of all valid super blocks stored in
409     the vector.  While doing this, we also make sure that the basic
410     invariant is maintained by making sure that _S_last_request and
411     _S_last_dealloc_index point to valid locations within the vector.
412   </para>
413 </sect3>
414
415 <sect3 id="bitmap.impl.questions" xreflabel="Questions">
416   <title>Questions</title>
417
418   <sect4 id="bitmap.impl.question.1" xreflabel="Question 1">
419     <title>1</title>
420     <para>
421 Q1) The "Data Layout" section is
422 cryptic. I have no idea of what you are trying to say. Layout of what?
423 The free-list? Each bitmap? The Super Block?
424     </para>
425     <para>
426       The layout of a Super Block of a given
427 size. In the example, a super block of size 32 x 1 is taken. The
428 general formula for calculating the size of a super block is
429 32 x sizeof(value_type) x 2^n, where n ranges from 0 to 32 for 32-bit
430 systems.
431     </para>
432   </sect4>
433
434   <sect4 id="bitmap.impl.question.2" xreflabel="Question 2">
435     <title>2</title>
436     <para>
437       And since I just mentioned the
438 term `each bitmap', what in the world is meant by it? What does each
439 bitmap manage? How does it relate to the super block? Is the Super
440 Block a bitmap as well?
441     </para>
442     <para>
443       Each bitmap is part of a Super Block which is made up of 3 parts
444       as I have mentioned earlier.  Re-iterating, 1. The use count,
445       2. The bit-map for that Super Block. 3.  The actual memory that
446       will be eventually given to the user. Each bitmap is a multiple
447       of 32 in size. If there are 32 x (2^3) blocks of single objects
448       to be given, there will be '32 x (2^3)' bits present.  Each 32
449       bits managing the allocated / free status for 32 blocks. Since
450       each size_t contains 32-bits, one size_t can manage up to 32
451       blocks' status. Each bit-map is made up of a number of size_t,
452       whose exact number for a super-block of a given size I have just
453       mentioned.
454     </para>
455   </sect4>
456
457   <sect4 id="bitmap.impl.question.3" xreflabel="Question 3">
458     <title>3</title>
459     <para>
460       How do the allocate and deallocate functions work in regard to
461       bitmaps?
462     </para>
463     <para>
464       The allocate and deallocate functions manipulate the bitmaps and
465       have nothing to do with the memory that is given to the user. As
466       I have earlier mentioned, a 1 in the bitmap's bit field
467       indicates free, while a 0 indicates allocated. This lets us
468       check 32 bits at a time to check whether there is at lease one
469       free block in those 32 blocks by testing for equality with
470       (0). Now, the allocate function will given a memory block find
471       the corresponding bit in the bitmap, and will reset it (i.e.,
472       make it re-set (0)). And when the deallocate function is called,
473       it will again set that bit after locating it to indicate that
474       that particular block corresponding to this bit in the bit-map
475       is not being used by anyone, and may be used to satisfy future
476       requests.
477     </para>
478     <para>
479       e.g.: Consider a bit-map of 64-bits as represented below:
480       1111111111111111111111111111111111111111111111111111111111111111
481     </para>
482
483     <para>
484       Now, when the first request for allocation of a single object
485       comes along, the first block in address order is returned. And
486       since the bit-maps in the reverse order to that of the address
487       order, the last bit (LSB if the bit-map is considered as a
488       binary word of 64-bits) is re-set to 0.
489     </para>
490
491     <para>
492       The bit-map now looks like this:
493       1111111111111111111111111111111111111111111111111111111111111110
494     </para>
495   </sect4>
496 </sect3>
497
498 <sect3 id="bitmap.impl.locality" xreflabel="Locality">
499   <title>Locality</title>
500   <para>
501     Another issue would be whether to keep the all bitmaps in a
502     separate area in memory, or to keep them near the actual blocks
503     that will be given out or allocated for the client. After some
504     testing, I've decided to keep these bitmaps close to the actual
505     blocks. This will help in 2 ways.
506   </para>
507   
508   <orderedlist>
509   <listitem><para>Constant time access for the bitmap themselves, since no kind of
510 look up will be needed to find the correct bitmap list or it's
511 equivalent.</para></listitem>
512   <listitem><para>And also this would preserve the cache as far as possible.</para></listitem>
513   </orderedlist>
514
515   <para>
516     So in effect, this kind of an allocator might prove beneficial from a
517     purely cache point of view. But this allocator has been made to try and
518     roll out the defects of the node_allocator, wherein the nodes get
519     skewed about in memory, if they are not returned in the exact reverse
520     order or in the same order in which they were allocated. Also, the
521     new_allocator's book keeping overhead is too much for small objects and
522     single object allocations, though it preserves the locality of blocks
523     very well when they are returned back to the allocator.
524   </para>
525 </sect3>
526
527 <sect3 id="bitmap.impl.grow_policy" xreflabel="Grow Policy">
528   <title>Overhead and Grow Policy</title>
529   <para>
530     Expected overhead per block would be 1 bit in memory. Also, once
531     the address of the free list has been found, the cost for
532     allocation/deallocation would be negligible, and is supposed to be
533     constant time. For these very reasons, it is very important to
534     minimize the linear time costs, which include finding a free list
535     with a free block while allocating, and finding the corresponding
536     free list for a block while deallocating. Therefore, I have
537     decided that the growth of the internal pool for this allocator
538     will be exponential as compared to linear for
539     node_allocator. There, linear time works well, because we are
540     mainly concerned with speed of allocation/deallocation and memory
541     consumption, whereas here, the allocation/deallocation part does
542     have some linear/logarithmic complexity components in it. Thus, to
543     try and minimize them would be a good thing to do at the cost of a
544     little bit of memory.
545   </para>
546
547   <para>
548     Another thing to be noted is the pool size will double every time
549     the internal pool gets exhausted, and all the free blocks have
550     been given away. The initial size of the pool would be
551     sizeof(size_t) x 8 which is the number of bits in an integer,
552     which can fit exactly in a CPU register. Hence, the term given is
553     exponential growth of the internal pool.
554   </para>
555 </sect3>
556
557 </sect2>
558  
559 </sect1>