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-NS Stylesheets V1.78.1" /><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="bitmap_allocator.html" title="Chapter��21.��The bitmap_allocator" /><link rel="prev" href="bitmap_allocator.html" title="Chapter��21.��The bitmap_allocator" /><link rel="next" href="policy_data_structures.html" title="Chapter��22.��Policy-Based Data Structures" /></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="bitmap_allocator.html">Prev</a>��</td><th width="60%" align="center">Chapter��21.��The bitmap_allocator</th><td width="20%" align="right">��<a accesskey="n" href="policy_data_structures.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.bitmap.impl"></a>Implementation</h2></div></div></div><div class="section"><div class="titlepage"><div><div><h3 class="title"><a id="bitmap.impl.free_list_store"></a>Free List Store</h3></div></div></div><p> 3 The Free List Store (referred to as FLS for the remaining part of this 4 document) is the Global memory pool that is shared by all instances of 5 the bitmapped allocator instantiated for any type. This maintains a 6 sorted order of all free memory blocks given back to it by the 7 bitmapped allocator, and is also responsible for giving memory to the 8 bitmapped allocator when it asks for more. 9 </p><p> 10 Internally, there is a Free List threshold which indicates the 11 Maximum number of free lists that the FLS can hold internally 12 (cache). Currently, this value is set at 64. So, if there are 13 more than 64 free lists coming in, then some of them will be given 14 back to the OS using operator delete so that at any given time the 15 Free List's size does not exceed 64 entries. This is done because 16 a Binary Search is used to locate an entry in a free list when a 17 request for memory comes along. Thus, the run-time complexity of 18 the search would go up given an increasing size, for 64 entries 19 however, lg(64) == 6 comparisons are enough to locate the correct 20 free list if it exists. 21 </p><p> 22 Suppose the free list size has reached its threshold, then the 23 largest block from among those in the list and the new block will 24 be selected and given back to the OS. This is done because it 25 reduces external fragmentation, and allows the OS to use the 26 larger blocks later in an orderly fashion, possibly merging them 27 later. Also, on some systems, large blocks are obtained via calls 28 to mmap, so giving them back to free system resources becomes most 29 important. 30 </p><p> 31 The function _S_should_i_give decides the policy that determines 32 whether the current block of memory should be given to the 33 allocator for the request that it has made. That's because we may 34 not always have exact fits for the memory size that the allocator 35 requests. We do this mainly to prevent external fragmentation at 36 the cost of a little internal fragmentation. Now, the value of 37 this internal fragmentation has to be decided by this function. I 38 can see 3 possibilities right now. Please add more as and when you 39 find better strategies. 40 </p><div class="orderedlist"><ol class="orderedlist" type="1"><li class="listitem"><p>Equal size check. Return true only when the 2 blocks are of equal 41size.</p></li><li class="listitem"><p>Difference Threshold: Return true only when the _block_size is 42greater than or equal to the _required_size, and if the _BS is > _RS 43by a difference of less than some THRESHOLD value, then return true, 44else return false. </p></li><li class="listitem"><p>Percentage Threshold. Return true only when the _block_size is 45greater than or equal to the _required_size, and if the _BS is > _RS 46by a percentage of less than some THRESHOLD value, then return true, 47else return false.</p></li></ol></div><p> 48 Currently, (3) is being used with a value of 36% Maximum wastage per 49 Super Block. 50 </p></div><div class="section"><div class="titlepage"><div><div><h3 class="title"><a id="bitmap.impl.super_block"></a>Super Block</h3></div></div></div><p> 51 A super block is the block of memory acquired from the FLS from 52 which the bitmap allocator carves out memory for single objects 53 and satisfies the user's requests. These super blocks come in 54 sizes that are powers of 2 and multiples of 32 55 (_Bits_Per_Block). Yes both at the same time! That's because the 56 next super block acquired will be 2 times the previous one, and 57 also all super blocks have to be multiples of the _Bits_Per_Block 58 value. 59 </p><p> 60 How does it interact with the free list store? 61 </p><p> 62 The super block is contained in the FLS, and the FLS is responsible for 63 getting / returning Super Bocks to and from the OS using operator new 64 as defined by the C++ standard. 65 </p></div><div class="section"><div class="titlepage"><div><div><h3 class="title"><a id="bitmap.impl.super_block_data"></a>Super Block Data Layout</h3></div></div></div><p> 66 Each Super Block will be of some size that is a multiple of the 67 number of Bits Per Block. Typically, this value is chosen as 68 Bits_Per_Byte x sizeof(size_t). On an x86 system, this gives the 69 figure 8 x 4 = 32. Thus, each Super Block will be of size 32 70 x Some_Value. This Some_Value is sizeof(value_type). For now, let 71 it be called 'K'. Thus, finally, Super Block size is 32 x K bytes. 72 </p><p> 73 This value of 32 has been chosen because each size_t has 32-bits 74 and Maximum use of these can be made with such a figure. 75 </p><p> 76 Consider a block of size 64 ints. In memory, it would look like this: 77 (assume a 32-bit system where, size_t is a 32-bit entity). 78 </p><div class="table"><a id="table.bitmap_alloc"></a><p class="title"><strong>Table��21.1.��Bitmap Allocator Memory Map</strong></p><div class="table-contents"><table summary="Bitmap Allocator Memory Map" border="1"><colgroup><col align="left" class="c1" /><col align="left" class="c2" /><col align="left" class="c3" /><col align="left" class="c4" /><col align="left" class="c5" /></colgroup><tbody><tr><td align="left">268</td><td align="left">0</td><td align="left">4294967295</td><td align="left">4294967295</td><td align="left">Data -> Space for 64 ints</td></tr></tbody></table></div></div><br class="table-break" /><p> 79 The first Column(268) represents the size of the Block in bytes as 80 seen by the Bitmap Allocator. Internally, a global free list is 81 used to keep track of the free blocks used and given back by the 82 bitmap allocator. It is this Free List Store that is responsible 83 for writing and managing this information. Actually the number of 84 bytes allocated in this case would be: 4 + 4 + (4x2) + (64x4) = 85 272 bytes, but the first 4 bytes are an addition by the Free List 86 Store, so the Bitmap Allocator sees only 268 bytes. These first 4 87 bytes about which the bitmapped allocator is not aware hold the 88 value 268. 89 </p><p> 90 What do the remaining values represent?</p><p> 91 The 2nd 4 in the expression is the sizeof(size_t) because the 92 Bitmapped Allocator maintains a used count for each Super Block, 93 which is initially set to 0 (as indicated in the diagram). This is 94 incremented every time a block is removed from this super block 95 (allocated), and decremented whenever it is given back. So, when 96 the used count falls to 0, the whole super block will be given 97 back to the Free List Store. 98 </p><p> 99 The value 4294967295 represents the integer corresponding to the bit 100 representation of all bits set: 11111111111111111111111111111111. 101 </p><p> 102 The 3rd 4x2 is size of the bitmap itself, which is the size of 32-bits 103 x 2, 104 which is 8-bytes, or 2 x sizeof(size_t). 105 </p></div><div class="section"><div class="titlepage"><div><div><h3 class="title"><a id="bitmap.impl.max_wasted"></a>Maximum Wasted Percentage</h3></div></div></div><p> 106 This has nothing to do with the algorithm per-se, 107 only with some vales that must be chosen correctly to ensure that the 108 allocator performs well in a real word scenario, and maintains a good 109 balance between the memory consumption and the allocation/deallocation 110 speed. 111 </p><p> 112 The formula for calculating the maximum wastage as a percentage: 113 </p><p> 114(32 x k + 1) / (2 x (32 x k + 1 + 32 x c)) x 100. 115 </p><p> 116 where k is the constant overhead per node (e.g., for list, it is 117 8 bytes, and for map it is 12 bytes) and c is the size of the 118 base type on which the map/list is instantiated. Thus, suppose the 119 type1 is int and type2 is double, they are related by the relation 120 sizeof(double) == 2*sizeof(int). Thus, all types must have this 121 double size relation for this formula to work properly. 122 </p><p> 123 Plugging-in: For List: k = 8 and c = 4 (int and double), we get: 124 33.376% 125 </p><p> 126For map/multimap: k = 12, and c = 4 (int and double), we get: 37.524% 127 </p><p> 128 Thus, knowing these values, and based on the sizeof(value_type), we may 129 create a function that returns the Max_Wastage_Percentage for us to use. 130 </p></div><div class="section"><div class="titlepage"><div><div><h3 class="title"><a id="bitmap.impl.allocate"></a><code class="function">allocate</code></h3></div></div></div><p> 131 The allocate function is specialized for single object allocation 132 ONLY. Thus, ONLY if n == 1, will the bitmap_allocator's 133 specialized algorithm be used. Otherwise, the request is satisfied 134 directly by calling operator new. 135 </p><p> 136 Suppose n == 1, then the allocator does the following: 137 </p><div class="orderedlist"><ol class="orderedlist" type="1"><li class="listitem"><p> 138 Checks to see whether a free block exists somewhere in a region 139 of memory close to the last satisfied request. If so, then that 140 block is marked as allocated in the bit map and given to the 141 user. If not, then (2) is executed. 142 </p></li><li class="listitem"><p> 143 Is there a free block anywhere after the current block right 144 up to the end of the memory that we have? If so, that block is 145 found, and the same procedure is applied as above, and 146 returned to the user. If not, then (3) is executed. 147 </p></li><li class="listitem"><p> 148 Is there any block in whatever region of memory that we own 149 free? This is done by checking 150 </p><div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "><li class="listitem"><p> 151 The use count for each super block, and if that fails then 152 </p></li><li class="listitem"><p> 153 The individual bit-maps for each super block. 154 </p></li></ul></div><p> 155 Note: Here we are never touching any of the memory that the 156 user will be given, and we are confining all memory accesses 157 to a small region of memory! This helps reduce cache 158 misses. If this succeeds then we apply the same procedure on 159 that bit-map as (1), and return that block of memory to the 160 user. However, if this process fails, then we resort to (4). 161 </p></li><li class="listitem"><p> 162 This process involves Refilling the internal exponentially 163 growing memory pool. The said effect is achieved by calling 164 _S_refill_pool which does the following: 165 </p><div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "><li class="listitem"><p> 166 Gets more memory from the Global Free List of the Required 167 size. 168 </p></li><li class="listitem"><p> 169 Adjusts the size for the next call to itself. 170 </p></li><li class="listitem"><p> 171 Writes the appropriate headers in the bit-maps. 172 </p></li><li class="listitem"><p> 173 Sets the use count for that super-block just allocated to 0 174 (zero). 175 </p></li><li class="listitem"><p> 176 All of the above accounts to maintaining the basic invariant 177 for the allocator. If the invariant is maintained, we are 178 sure that all is well. Now, the same process is applied on 179 the newly acquired free blocks, which are dispatched 180 accordingly. 181 </p></li></ul></div></li></ol></div><p> 182Thus, you can clearly see that the allocate function is nothing but a 183combination of the next-fit and first-fit algorithm optimized ONLY for 184single object allocations. 185</p></div><div class="section"><div class="titlepage"><div><div><h3 class="title"><a id="bitmap.impl.deallocate"></a><code class="function">deallocate</code></h3></div></div></div><p> 186 The deallocate function again is specialized for single objects ONLY. 187 For all n belonging to > 1, the operator delete is called without 188 further ado, and the deallocate function returns. 189 </p><p> 190 However for n == 1, a series of steps are performed: 191 </p><div class="orderedlist"><ol class="orderedlist" type="1"><li class="listitem"><p> 192 We first need to locate that super-block which holds the memory 193 location given to us by the user. For that purpose, we maintain 194 a static variable _S_last_dealloc_index, which holds the index 195 into the vector of block pairs which indicates the index of the 196 last super-block from which memory was freed. We use this 197 strategy in the hope that the user will deallocate memory in a 198 region close to what he/she deallocated the last time around. If 199 the check for belongs_to succeeds, then we determine the bit-map 200 for the given pointer, and locate the index into that bit-map, 201 and mark that bit as free by setting it. 202 </p></li><li class="listitem"><p> 203 If the _S_last_dealloc_index does not point to the memory block 204 that we're looking for, then we do a linear search on the block 205 stored in the vector of Block Pairs. This vector in code is 206 called _S_mem_blocks. When the corresponding super-block is 207 found, we apply the same procedure as we did for (1) to mark the 208 block as free in the bit-map. 209 </p></li></ol></div><p> 210 Now, whenever a block is freed, the use count of that particular 211 super block goes down by 1. When this use count hits 0, we remove 212 that super block from the list of all valid super blocks stored in 213 the vector. While doing this, we also make sure that the basic 214 invariant is maintained by making sure that _S_last_request and 215 _S_last_dealloc_index point to valid locations within the vector. 216 </p></div><div class="section"><div class="titlepage"><div><div><h3 class="title"><a id="bitmap.impl.questions"></a>Questions</h3></div></div></div><div class="section"><div class="titlepage"><div><div><h4 class="title"><a id="bitmap.impl.question.1"></a>1</h4></div></div></div><p> 217Q1) The "Data Layout" section is 218cryptic. I have no idea of what you are trying to say. Layout of what? 219The free-list? Each bitmap? The Super Block? 220 </p><p> 221 The layout of a Super Block of a given 222size. In the example, a super block of size 32 x 1 is taken. The 223general formula for calculating the size of a super block is 22432 x sizeof(value_type) x 2^n, where n ranges from 0 to 32 for 32-bit 225systems. 226 </p></div><div class="section"><div class="titlepage"><div><div><h4 class="title"><a id="bitmap.impl.question.2"></a>2</h4></div></div></div><p> 227 And since I just mentioned the 228term `each bitmap', what in the world is meant by it? What does each 229bitmap manage? How does it relate to the super block? Is the Super 230Block a bitmap as well? 231 </p><p> 232 Each bitmap is part of a Super Block which is made up of 3 parts 233 as I have mentioned earlier. Re-iterating, 1. The use count, 234 2. The bit-map for that Super Block. 3. The actual memory that 235 will be eventually given to the user. Each bitmap is a multiple 236 of 32 in size. If there are 32 x (2^3) blocks of single objects 237 to be given, there will be '32 x (2^3)' bits present. Each 32 238 bits managing the allocated / free status for 32 blocks. Since 239 each size_t contains 32-bits, one size_t can manage up to 32 240 blocks' status. Each bit-map is made up of a number of size_t, 241 whose exact number for a super-block of a given size I have just 242 mentioned. 243 </p></div><div class="section"><div class="titlepage"><div><div><h4 class="title"><a id="bitmap.impl.question.3"></a>3</h4></div></div></div><p> 244 How do the allocate and deallocate functions work in regard to 245 bitmaps? 246 </p><p> 247 The allocate and deallocate functions manipulate the bitmaps and 248 have nothing to do with the memory that is given to the user. As 249 I have earlier mentioned, a 1 in the bitmap's bit field 250 indicates free, while a 0 indicates allocated. This lets us 251 check 32 bits at a time to check whether there is at lease one 252 free block in those 32 blocks by testing for equality with 253 (0). Now, the allocate function will given a memory block find 254 the corresponding bit in the bitmap, and will reset it (i.e., 255 make it re-set (0)). And when the deallocate function is called, 256 it will again set that bit after locating it to indicate that 257 that particular block corresponding to this bit in the bit-map 258 is not being used by anyone, and may be used to satisfy future 259 requests. 260 </p><p> 261 e.g.: Consider a bit-map of 64-bits as represented below: 262 1111111111111111111111111111111111111111111111111111111111111111 263 </p><p> 264 Now, when the first request for allocation of a single object 265 comes along, the first block in address order is returned. And 266 since the bit-maps in the reverse order to that of the address 267 order, the last bit (LSB if the bit-map is considered as a 268 binary word of 64-bits) is re-set to 0. 269 </p><p> 270 The bit-map now looks like this: 271 1111111111111111111111111111111111111111111111111111111111111110 272 </p></div></div><div class="section"><div class="titlepage"><div><div><h3 class="title"><a id="bitmap.impl.locality"></a>Locality</h3></div></div></div><p> 273 Another issue would be whether to keep the all bitmaps in a 274 separate area in memory, or to keep them near the actual blocks 275 that will be given out or allocated for the client. After some 276 testing, I've decided to keep these bitmaps close to the actual 277 blocks. This will help in 2 ways. 278 </p><div class="orderedlist"><ol class="orderedlist" type="1"><li class="listitem"><p>Constant time access for the bitmap themselves, since no kind of 279look up will be needed to find the correct bitmap list or its 280equivalent.</p></li><li class="listitem"><p>And also this would preserve the cache as far as possible.</p></li></ol></div><p> 281 So in effect, this kind of an allocator might prove beneficial from a 282 purely cache point of view. But this allocator has been made to try and 283 roll out the defects of the node_allocator, wherein the nodes get 284 skewed about in memory, if they are not returned in the exact reverse 285 order or in the same order in which they were allocated. Also, the 286 new_allocator's book keeping overhead is too much for small objects and 287 single object allocations, though it preserves the locality of blocks 288 very well when they are returned back to the allocator. 289 </p></div><div class="section"><div class="titlepage"><div><div><h3 class="title"><a id="bitmap.impl.grow_policy"></a>Overhead and Grow Policy</h3></div></div></div><p> 290 Expected overhead per block would be 1 bit in memory. Also, once 291 the address of the free list has been found, the cost for 292 allocation/deallocation would be negligible, and is supposed to be 293 constant time. For these very reasons, it is very important to 294 minimize the linear time costs, which include finding a free list 295 with a free block while allocating, and finding the corresponding 296 free list for a block while deallocating. Therefore, I have 297 decided that the growth of the internal pool for this allocator 298 will be exponential as compared to linear for 299 node_allocator. There, linear time works well, because we are 300 mainly concerned with speed of allocation/deallocation and memory 301 consumption, whereas here, the allocation/deallocation part does 302 have some linear/logarithmic complexity components in it. Thus, to 303 try and minimize them would be a good thing to do at the cost of a 304 little bit of memory. 305 </p><p> 306 Another thing to be noted is the pool size will double every time 307 the internal pool gets exhausted, and all the free blocks have 308 been given away. The initial size of the pool would be 309 sizeof(size_t) x 8 which is the number of bits in an integer, 310 which can fit exactly in a CPU register. Hence, the term given is 311 exponential growth of the internal pool. 312 </p></div></div><div class="navfooter"><hr /><table width="100%" summary="Navigation footer"><tr><td width="40%" align="left"><a accesskey="p" href="bitmap_allocator.html">Prev</a>��</td><td width="20%" align="center"><a accesskey="u" href="bitmap_allocator.html">Up</a></td><td width="40%" align="right">��<a accesskey="n" href="policy_data_structures.html">Next</a></td></tr><tr><td width="40%" align="left" valign="top">Chapter��21.��The bitmap_allocator��</td><td width="20%" align="center"><a accesskey="h" href="../index.html">Home</a></td><td width="40%" align="right" valign="top">��Chapter��22.��Policy-Based Data Structures</td></tr></table></div></body></html>