1 <section xmlns="http://docbook.org/ns/docbook" version="5.0"
2 xml:id="manual.ext.allocator.bitmap" xreflabel="bitmap_allocator">
3 <?dbhtml filename="bitmap_allocator.html"?>
5 <info><title>bitmap_allocator</title>
21 <section xml:id="allocator.bitmap.design"><info><title>Design</title></info>
25 As this name suggests, this allocator uses a bit-map to keep track
26 of the used and unused memory locations for it's book-keeping
30 This allocator will make use of 1 single bit to keep track of
31 whether it has been allocated or not. A bit 1 indicates free,
32 while 0 indicates allocated. This has been done so that you can
33 easily check a collection of bits for a free block. This kind of
34 Bitmapped strategy works best for single object allocations, and
35 with the STL type parameterized allocators, we do not need to
36 choose any size for the block which will be represented by a
37 single bit. This will be the size of the parameter around which
38 the allocator has been parameterized. Thus, close to optimal
39 performance will result. Hence, this should be used for node based
40 containers which call the allocate function with an argument of 1.
44 The bitmapped allocator's internal pool is exponentially growing.
45 Meaning that internally, the blocks acquired from the Free List
46 Store will double every time the bitmapped allocator runs out of
51 The macro <literal>__GTHREADS</literal> decides whether to use
52 Mutex Protection around every allocation/deallocation. The state
53 of the macro is picked up automatically from the gthr abstraction
59 <section xml:id="allocator.bitmap.impl"><info><title>Implementation</title></info>
62 <section xml:id="bitmap.impl.free_list_store" xreflabel="Free List Store"><info><title>Free List Store</title></info>
66 The Free List Store (referred to as FLS for the remaining part of this
67 document) is the Global memory pool that is shared by all instances of
68 the bitmapped allocator instantiated for any type. This maintains a
69 sorted order of all free memory blocks given back to it by the
70 bitmapped allocator, and is also responsible for giving memory to the
71 bitmapped allocator when it asks for more.
74 Internally, there is a Free List threshold which indicates the
75 Maximum number of free lists that the FLS can hold internally
76 (cache). Currently, this value is set at 64. So, if there are
77 more than 64 free lists coming in, then some of them will be given
78 back to the OS using operator delete so that at any given time the
79 Free List's size does not exceed 64 entries. This is done because
80 a Binary Search is used to locate an entry in a free list when a
81 request for memory comes along. Thus, the run-time complexity of
82 the search would go up given an increasing size, for 64 entries
83 however, lg(64) == 6 comparisons are enough to locate the correct
84 free list if it exists.
87 Suppose the free list size has reached it's threshold, then the
88 largest block from among those in the list and the new block will
89 be selected and given back to the OS. This is done because it
90 reduces external fragmentation, and allows the OS to use the
91 larger blocks later in an orderly fashion, possibly merging them
92 later. Also, on some systems, large blocks are obtained via calls
93 to mmap, so giving them back to free system resources becomes most
97 The function _S_should_i_give decides the policy that determines
98 whether the current block of memory should be given to the
99 allocator for the request that it has made. That's because we may
100 not always have exact fits for the memory size that the allocator
101 requests. We do this mainly to prevent external fragmentation at
102 the cost of a little internal fragmentation. Now, the value of
103 this internal fragmentation has to be decided by this function. I
104 can see 3 possibilities right now. Please add more as and when you
105 find better strategies.
109 <listitem><para>Equal size check. Return true only when the 2 blocks are of equal
110 size.</para></listitem>
111 <listitem><para>Difference Threshold: Return true only when the _block_size is
112 greater than or equal to the _required_size, and if the _BS is > _RS
113 by a difference of less than some THRESHOLD value, then return true,
114 else return false. </para></listitem>
115 <listitem><para>Percentage Threshold. Return true only when the _block_size is
116 greater than or equal to the _required_size, and if the _BS is > _RS
117 by a percentage of less than some THRESHOLD value, then return true,
118 else return false.</para></listitem>
122 Currently, (3) is being used with a value of 36% Maximum wastage per
127 <section xml:id="bitmap.impl.super_block" xreflabel="Super Block"><info><title>Super Block</title></info>
131 A super block is the block of memory acquired from the FLS from
132 which the bitmap allocator carves out memory for single objects
133 and satisfies the user's requests. These super blocks come in
134 sizes that are powers of 2 and multiples of 32
135 (_Bits_Per_Block). Yes both at the same time! That's because the
136 next super block acquired will be 2 times the previous one, and
137 also all super blocks have to be multiples of the _Bits_Per_Block
141 How does it interact with the free list store?
144 The super block is contained in the FLS, and the FLS is responsible for
145 getting / returning Super Bocks to and from the OS using operator new
146 as defined by the C++ standard.
150 <section xml:id="bitmap.impl.super_block_data" xreflabel="Super Block Data"><info><title>Super Block Data Layout</title></info>
153 Each Super Block will be of some size that is a multiple of the
154 number of Bits Per Block. Typically, this value is chosen as
155 Bits_Per_Byte x sizeof(size_t). On an x86 system, this gives the
156 figure 8 x 4 = 32. Thus, each Super Block will be of size 32
157 x Some_Value. This Some_Value is sizeof(value_type). For now, let
158 it be called 'K'. Thus, finally, Super Block size is 32 x K bytes.
161 This value of 32 has been chosen because each size_t has 32-bits
162 and Maximum use of these can be made with such a figure.
165 Consider a block of size 64 ints. In memory, it would look like this:
166 (assume a 32-bit system where, size_t is a 32-bit entity).
170 <title>Bitmap Allocator Memory Map</title>
172 <tgroup cols="5" align="left" colsep="1" rowsep="1">
173 <colspec colname="c1"/>
174 <colspec colname="c2"/>
175 <colspec colname="c3"/>
176 <colspec colname="c4"/>
177 <colspec colname="c5"/>
183 <entry>4294967295</entry>
184 <entry>4294967295</entry>
185 <entry>Data -> Space for 64 ints</entry>
192 The first Column(268) represents the size of the Block in bytes as
193 seen by the Bitmap Allocator. Internally, a global free list is
194 used to keep track of the free blocks used and given back by the
195 bitmap allocator. It is this Free List Store that is responsible
196 for writing and managing this information. Actually the number of
197 bytes allocated in this case would be: 4 + 4 + (4x2) + (64x4) =
198 272 bytes, but the first 4 bytes are an addition by the Free List
199 Store, so the Bitmap Allocator sees only 268 bytes. These first 4
200 bytes about which the bitmapped allocator is not aware hold the
205 What do the remaining values represent?</para>
207 The 2nd 4 in the expression is the sizeof(size_t) because the
208 Bitmapped Allocator maintains a used count for each Super Block,
209 which is initially set to 0 (as indicated in the diagram). This is
210 incremented every time a block is removed from this super block
211 (allocated), and decremented whenever it is given back. So, when
212 the used count falls to 0, the whole super block will be given
213 back to the Free List Store.
216 The value 4294967295 represents the integer corresponding to the bit
217 representation of all bits set: 11111111111111111111111111111111.
220 The 3rd 4x2 is size of the bitmap itself, which is the size of 32-bits
222 which is 8-bytes, or 2 x sizeof(size_t).
226 <section xml:id="bitmap.impl.max_wasted" xreflabel="Max Wasted Percentage"><info><title>Maximum Wasted Percentage</title></info>
230 This has nothing to do with the algorithm per-se,
231 only with some vales that must be chosen correctly to ensure that the
232 allocator performs well in a real word scenario, and maintains a good
233 balance between the memory consumption and the allocation/deallocation
237 The formula for calculating the maximum wastage as a percentage:
241 (32 x k + 1) / (2 x (32 x k + 1 + 32 x c)) x 100.
245 where k is the constant overhead per node (e.g., for list, it is
246 8 bytes, and for map it is 12 bytes) and c is the size of the
247 base type on which the map/list is instantiated. Thus, suppose the
248 type1 is int and type2 is double, they are related by the relation
249 sizeof(double) == 2*sizeof(int). Thus, all types must have this
250 double size relation for this formula to work properly.
253 Plugging-in: For List: k = 8 and c = 4 (int and double), we get:
258 For map/multimap: k = 12, and c = 4 (int and double), we get: 37.524%
261 Thus, knowing these values, and based on the sizeof(value_type), we may
262 create a function that returns the Max_Wastage_Percentage for us to use.
267 <section xml:id="bitmap.impl.allocate" xreflabel="Allocate"><info><title><function>allocate</function></title></info>
271 The allocate function is specialized for single object allocation
272 ONLY. Thus, ONLY if n == 1, will the bitmap_allocator's
273 specialized algorithm be used. Otherwise, the request is satisfied
274 directly by calling operator new.
277 Suppose n == 1, then the allocator does the following:
282 Checks to see whether a free block exists somewhere in a region
283 of memory close to the last satisfied request. If so, then that
284 block is marked as allocated in the bit map and given to the
285 user. If not, then (2) is executed.
290 Is there a free block anywhere after the current block right
291 up to the end of the memory that we have? If so, that block is
292 found, and the same procedure is applied as above, and
293 returned to the user. If not, then (3) is executed.
298 Is there any block in whatever region of memory that we own
299 free? This is done by checking
304 The use count for each super block, and if that fails then
309 The individual bit-maps for each super block.
315 Note: Here we are never touching any of the memory that the
316 user will be given, and we are confining all memory accesses
317 to a small region of memory! This helps reduce cache
318 misses. If this succeeds then we apply the same procedure on
319 that bit-map as (1), and return that block of memory to the
320 user. However, if this process fails, then we resort to (4).
325 This process involves Refilling the internal exponentially
326 growing memory pool. The said effect is achieved by calling
327 _S_refill_pool which does the following:
332 Gets more memory from the Global Free List of the Required
338 Adjusts the size for the next call to itself.
343 Writes the appropriate headers in the bit-maps.
348 Sets the use count for that super-block just allocated to 0
354 All of the above accounts to maintaining the basic invariant
355 for the allocator. If the invariant is maintained, we are
356 sure that all is well. Now, the same process is applied on
357 the newly acquired free blocks, which are dispatched
366 Thus, you can clearly see that the allocate function is nothing but a
367 combination of the next-fit and first-fit algorithm optimized ONLY for
368 single object allocations.
373 <section xml:id="bitmap.impl.deallocate" xreflabel="Deallocate"><info><title><function>deallocate</function></title></info>
376 The deallocate function again is specialized for single objects ONLY.
377 For all n belonging to > 1, the operator delete is called without
378 further ado, and the deallocate function returns.
381 However for n == 1, a series of steps are performed:
386 We first need to locate that super-block which holds the memory
387 location given to us by the user. For that purpose, we maintain
388 a static variable _S_last_dealloc_index, which holds the index
389 into the vector of block pairs which indicates the index of the
390 last super-block from which memory was freed. We use this
391 strategy in the hope that the user will deallocate memory in a
392 region close to what he/she deallocated the last time around. If
393 the check for belongs_to succeeds, then we determine the bit-map
394 for the given pointer, and locate the index into that bit-map,
395 and mark that bit as free by setting it.
398 If the _S_last_dealloc_index does not point to the memory block
399 that we're looking for, then we do a linear search on the block
400 stored in the vector of Block Pairs. This vector in code is
401 called _S_mem_blocks. When the corresponding super-block is
402 found, we apply the same procedure as we did for (1) to mark the
403 block as free in the bit-map.
408 Now, whenever a block is freed, the use count of that particular
409 super block goes down by 1. When this use count hits 0, we remove
410 that super block from the list of all valid super blocks stored in
411 the vector. While doing this, we also make sure that the basic
412 invariant is maintained by making sure that _S_last_request and
413 _S_last_dealloc_index point to valid locations within the vector.
417 <section xml:id="bitmap.impl.questions" xreflabel="Questions"><info><title>Questions</title></info>
420 <section xml:id="bitmap.impl.question.1" xreflabel="Question 1"><info><title>1</title></info>
423 Q1) The "Data Layout" section is
424 cryptic. I have no idea of what you are trying to say. Layout of what?
425 The free-list? Each bitmap? The Super Block?
428 The layout of a Super Block of a given
429 size. In the example, a super block of size 32 x 1 is taken. The
430 general formula for calculating the size of a super block is
431 32 x sizeof(value_type) x 2^n, where n ranges from 0 to 32 for 32-bit
436 <section xml:id="bitmap.impl.question.2" xreflabel="Question 2"><info><title>2</title></info>
439 And since I just mentioned the
440 term `each bitmap', what in the world is meant by it? What does each
441 bitmap manage? How does it relate to the super block? Is the Super
442 Block a bitmap as well?
445 Each bitmap is part of a Super Block which is made up of 3 parts
446 as I have mentioned earlier. Re-iterating, 1. The use count,
447 2. The bit-map for that Super Block. 3. The actual memory that
448 will be eventually given to the user. Each bitmap is a multiple
449 of 32 in size. If there are 32 x (2^3) blocks of single objects
450 to be given, there will be '32 x (2^3)' bits present. Each 32
451 bits managing the allocated / free status for 32 blocks. Since
452 each size_t contains 32-bits, one size_t can manage up to 32
453 blocks' status. Each bit-map is made up of a number of size_t,
454 whose exact number for a super-block of a given size I have just
459 <section xml:id="bitmap.impl.question.3" xreflabel="Question 3"><info><title>3</title></info>
462 How do the allocate and deallocate functions work in regard to
466 The allocate and deallocate functions manipulate the bitmaps and
467 have nothing to do with the memory that is given to the user. As
468 I have earlier mentioned, a 1 in the bitmap's bit field
469 indicates free, while a 0 indicates allocated. This lets us
470 check 32 bits at a time to check whether there is at lease one
471 free block in those 32 blocks by testing for equality with
472 (0). Now, the allocate function will given a memory block find
473 the corresponding bit in the bitmap, and will reset it (i.e.,
474 make it re-set (0)). And when the deallocate function is called,
475 it will again set that bit after locating it to indicate that
476 that particular block corresponding to this bit in the bit-map
477 is not being used by anyone, and may be used to satisfy future
481 e.g.: Consider a bit-map of 64-bits as represented below:
482 1111111111111111111111111111111111111111111111111111111111111111
486 Now, when the first request for allocation of a single object
487 comes along, the first block in address order is returned. And
488 since the bit-maps in the reverse order to that of the address
489 order, the last bit (LSB if the bit-map is considered as a
490 binary word of 64-bits) is re-set to 0.
494 The bit-map now looks like this:
495 1111111111111111111111111111111111111111111111111111111111111110
500 <section xml:id="bitmap.impl.locality" xreflabel="Locality"><info><title>Locality</title></info>
503 Another issue would be whether to keep the all bitmaps in a
504 separate area in memory, or to keep them near the actual blocks
505 that will be given out or allocated for the client. After some
506 testing, I've decided to keep these bitmaps close to the actual
507 blocks. This will help in 2 ways.
511 <listitem><para>Constant time access for the bitmap themselves, since no kind of
512 look up will be needed to find the correct bitmap list or it's
513 equivalent.</para></listitem>
514 <listitem><para>And also this would preserve the cache as far as possible.</para></listitem>
518 So in effect, this kind of an allocator might prove beneficial from a
519 purely cache point of view. But this allocator has been made to try and
520 roll out the defects of the node_allocator, wherein the nodes get
521 skewed about in memory, if they are not returned in the exact reverse
522 order or in the same order in which they were allocated. Also, the
523 new_allocator's book keeping overhead is too much for small objects and
524 single object allocations, though it preserves the locality of blocks
525 very well when they are returned back to the allocator.
529 <section xml:id="bitmap.impl.grow_policy" xreflabel="Grow Policy"><info><title>Overhead and Grow Policy</title></info>
532 Expected overhead per block would be 1 bit in memory. Also, once
533 the address of the free list has been found, the cost for
534 allocation/deallocation would be negligible, and is supposed to be
535 constant time. For these very reasons, it is very important to
536 minimize the linear time costs, which include finding a free list
537 with a free block while allocating, and finding the corresponding
538 free list for a block while deallocating. Therefore, I have
539 decided that the growth of the internal pool for this allocator
540 will be exponential as compared to linear for
541 node_allocator. There, linear time works well, because we are
542 mainly concerned with speed of allocation/deallocation and memory
543 consumption, whereas here, the allocation/deallocation part does
544 have some linear/logarithmic complexity components in it. Thus, to
545 try and minimize them would be a good thing to do at the cost of a
546 little bit of memory.
550 Another thing to be noted is the pool size will double every time
551 the internal pool gets exhausted, and all the free blocks have
552 been given away. The initial size of the pool would be
553 sizeof(size_t) x 8 which is the number of bits in an integer,
554 which can fit exactly in a CPU register. Hence, the term given is
555 exponential growth of the internal pool.
OSDN Git Service
