| <?xml version="1.0" encoding="UTF-8" standalone="no"?> | |
| <!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 Stylesheets Vsnapshot" /><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> | |
| The Free List Store (referred to as FLS for the remaining part of this | |
| document) is the Global memory pool that is shared by all instances of | |
| the bitmapped allocator instantiated for any type. This maintains a | |
| sorted order of all free memory blocks given back to it by the | |
| bitmapped allocator, and is also responsible for giving memory to the | |
| bitmapped allocator when it asks for more. | |
| </p><p> | |
| Internally, there is a Free List threshold which indicates the | |
| Maximum number of free lists that the FLS can hold internally | |
| (cache). Currently, this value is set at 64. So, if there are | |
| more than 64 free lists coming in, then some of them will be given | |
| back to the OS using operator delete so that at any given time the | |
| Free List's size does not exceed 64 entries. This is done because | |
| a Binary Search is used to locate an entry in a free list when a | |
| request for memory comes along. Thus, the run-time complexity of | |
| the search would go up given an increasing size, for 64 entries | |
| however, lg(64) == 6 comparisons are enough to locate the correct | |
| free list if it exists. | |
| </p><p> | |
| Suppose the free list size has reached its threshold, then the | |
| largest block from among those in the list and the new block will | |
| be selected and given back to the OS. This is done because it | |
| reduces external fragmentation, and allows the OS to use the | |
| larger blocks later in an orderly fashion, possibly merging them | |
| later. Also, on some systems, large blocks are obtained via calls | |
| to mmap, so giving them back to free system resources becomes most | |
| important. | |
| </p><p> | |
| The function _S_should_i_give decides the policy that determines | |
| whether the current block of memory should be given to the | |
| allocator for the request that it has made. That's because we may | |
| not always have exact fits for the memory size that the allocator | |
| requests. We do this mainly to prevent external fragmentation at | |
| the cost of a little internal fragmentation. Now, the value of | |
| this internal fragmentation has to be decided by this function. I | |
| can see 3 possibilities right now. Please add more as and when you | |
| find better strategies. | |
| </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 | |
| size.</p></li><li class="listitem"><p>Difference Threshold: Return true only when the _block_size is | |
| greater than or equal to the _required_size, and if the _BS is > _RS | |
| by a difference of less than some THRESHOLD value, then return true, | |
| else return false. </p></li><li class="listitem"><p>Percentage Threshold. Return true only when the _block_size is | |
| greater than or equal to the _required_size, and if the _BS is > _RS | |
| by a percentage of less than some THRESHOLD value, then return true, | |
| else return false.</p></li></ol></div><p> | |
| Currently, (3) is being used with a value of 36% Maximum wastage per | |
| Super Block. | |
| </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> | |
| A super block is the block of memory acquired from the FLS from | |
| which the bitmap allocator carves out memory for single objects | |
| and satisfies the user's requests. These super blocks come in | |
| sizes that are powers of 2 and multiples of 32 | |
| (_Bits_Per_Block). Yes both at the same time! That's because the | |
| next super block acquired will be 2 times the previous one, and | |
| also all super blocks have to be multiples of the _Bits_Per_Block | |
| value. | |
| </p><p> | |
| How does it interact with the free list store? | |
| </p><p> | |
| The super block is contained in the FLS, and the FLS is responsible for | |
| getting / returning Super Bocks to and from the OS using operator new | |
| as defined by the C++ standard. | |
| </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> | |
| Each Super Block will be of some size that is a multiple of the | |
| number of Bits Per Block. Typically, this value is chosen as | |
| Bits_Per_Byte x sizeof(size_t). On an x86 system, this gives the | |
| figure 8 x 4 = 32. Thus, each Super Block will be of size 32 | |
| x Some_Value. This Some_Value is sizeof(value_type). For now, let | |
| it be called 'K'. Thus, finally, Super Block size is 32 x K bytes. | |
| </p><p> | |
| This value of 32 has been chosen because each size_t has 32-bits | |
| and Maximum use of these can be made with such a figure. | |
| </p><p> | |
| Consider a block of size 64 ints. In memory, it would look like this: | |
| (assume a 32-bit system where, size_t is a 32-bit entity). | |
| </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 class="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> | |
| The first Column(268) represents the size of the Block in bytes as | |
| seen by the Bitmap Allocator. Internally, a global free list is | |
| used to keep track of the free blocks used and given back by the | |
| bitmap allocator. It is this Free List Store that is responsible | |
| for writing and managing this information. Actually the number of | |
| bytes allocated in this case would be: 4 + 4 + (4x2) + (64x4) = | |
| 272 bytes, but the first 4 bytes are an addition by the Free List | |
| Store, so the Bitmap Allocator sees only 268 bytes. These first 4 | |
| bytes about which the bitmapped allocator is not aware hold the | |
| value 268. | |
| </p><p> | |
| What do the remaining values represent?</p><p> | |
| The 2nd 4 in the expression is the sizeof(size_t) because the | |
| Bitmapped Allocator maintains a used count for each Super Block, | |
| which is initially set to 0 (as indicated in the diagram). This is | |
| incremented every time a block is removed from this super block | |
| (allocated), and decremented whenever it is given back. So, when | |
| the used count falls to 0, the whole super block will be given | |
| back to the Free List Store. | |
| </p><p> | |
| The value 4294967295 represents the integer corresponding to the bit | |
| representation of all bits set: 11111111111111111111111111111111. | |
| </p><p> | |
| The 3rd 4x2 is size of the bitmap itself, which is the size of 32-bits | |
| x 2, | |
| which is 8-bytes, or 2 x sizeof(size_t). | |
| </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> | |
| This has nothing to do with the algorithm per-se, | |
| only with some values that must be chosen correctly to ensure that the | |
| allocator performs well in a real world scenario, and maintains a good | |
| balance between the memory consumption and the allocation/deallocation | |
| speed. | |
| </p><p> | |
| The formula for calculating the maximum wastage as a percentage: | |
| </p><p> | |
| (32 x k + 1) / (2 x (32 x k + 1 + 32 x c)) x 100. | |
| </p><p> | |
| where k is the constant overhead per node (e.g., for list, it is | |
| 8 bytes, and for map it is 12 bytes) and c is the size of the | |
| base type on which the map/list is instantiated. Thus, suppose the | |
| type1 is int and type2 is double, they are related by the relation | |
| sizeof(double) == 2*sizeof(int). Thus, all types must have this | |
| double size relation for this formula to work properly. | |
| </p><p> | |
| Plugging-in: For List: k = 8 and c = 4 (int and double), we get: | |
| 33.376% | |
| </p><p> | |
| For map/multimap: k = 12, and c = 4 (int and double), we get: 37.524% | |
| </p><p> | |
| Thus, knowing these values, and based on the sizeof(value_type), we may | |
| create a function that returns the Max_Wastage_Percentage for us to use. | |
| </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> | |
| The allocate function is specialized for single object allocation | |
| ONLY. Thus, ONLY if n == 1, will the bitmap_allocator's | |
| specialized algorithm be used. Otherwise, the request is satisfied | |
| directly by calling operator new. | |
| </p><p> | |
| Suppose n == 1, then the allocator does the following: | |
| </p><div class="orderedlist"><ol class="orderedlist" type="1"><li class="listitem"><p> | |
| Checks to see whether a free block exists somewhere in a region | |
| of memory close to the last satisfied request. If so, then that | |
| block is marked as allocated in the bit map and given to the | |
| user. If not, then (2) is executed. | |
| </p></li><li class="listitem"><p> | |
| Is there a free block anywhere after the current block right | |
| up to the end of the memory that we have? If so, that block is | |
| found, and the same procedure is applied as above, and | |
| returned to the user. If not, then (3) is executed. | |
| </p></li><li class="listitem"><p> | |
| Is there any block in whatever region of memory that we own | |
| free? This is done by checking | |
| </p><div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "><li class="listitem"><p> | |
| The use count for each super block, and if that fails then | |
| </p></li><li class="listitem"><p> | |
| The individual bit-maps for each super block. | |
| </p></li></ul></div><p> | |
| Note: Here we are never touching any of the memory that the | |
| user will be given, and we are confining all memory accesses | |
| to a small region of memory! This helps reduce cache | |
| misses. If this succeeds then we apply the same procedure on | |
| that bit-map as (1), and return that block of memory to the | |
| user. However, if this process fails, then we resort to (4). | |
| </p></li><li class="listitem"><p> | |
| This process involves Refilling the internal exponentially | |
| growing memory pool. The said effect is achieved by calling | |
| _S_refill_pool which does the following: | |
| </p><div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "><li class="listitem"><p> | |
| Gets more memory from the Global Free List of the Required | |
| size. | |
| </p></li><li class="listitem"><p> | |
| Adjusts the size for the next call to itself. | |
| </p></li><li class="listitem"><p> | |
| Writes the appropriate headers in the bit-maps. | |
| </p></li><li class="listitem"><p> | |
| Sets the use count for that super-block just allocated to 0 | |
| (zero). | |
| </p></li><li class="listitem"><p> | |
| All of the above accounts to maintaining the basic invariant | |
| for the allocator. If the invariant is maintained, we are | |
| sure that all is well. Now, the same process is applied on | |
| the newly acquired free blocks, which are dispatched | |
| accordingly. | |
| </p></li></ul></div></li></ol></div><p> | |
| Thus, you can clearly see that the allocate function is nothing but a | |
| combination of the next-fit and first-fit algorithm optimized ONLY for | |
| single object allocations. | |
| </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> | |
| The deallocate function again is specialized for single objects ONLY. | |
| For all n belonging to > 1, the operator delete is called without | |
| further ado, and the deallocate function returns. | |
| </p><p> | |
| However for n == 1, a series of steps are performed: | |
| </p><div class="orderedlist"><ol class="orderedlist" type="1"><li class="listitem"><p> | |
| We first need to locate that super-block which holds the memory | |
| location given to us by the user. For that purpose, we maintain | |
| a static variable _S_last_dealloc_index, which holds the index | |
| into the vector of block pairs which indicates the index of the | |
| last super-block from which memory was freed. We use this | |
| strategy in the hope that the user will deallocate memory in a | |
| region close to what he/she deallocated the last time around. If | |
| the check for belongs_to succeeds, then we determine the bit-map | |
| for the given pointer, and locate the index into that bit-map, | |
| and mark that bit as free by setting it. | |
| </p></li><li class="listitem"><p> | |
| If the _S_last_dealloc_index does not point to the memory block | |
| that we're looking for, then we do a linear search on the block | |
| stored in the vector of Block Pairs. This vector in code is | |
| called _S_mem_blocks. When the corresponding super-block is | |
| found, we apply the same procedure as we did for (1) to mark the | |
| block as free in the bit-map. | |
| </p></li></ol></div><p> | |
| Now, whenever a block is freed, the use count of that particular | |
| super block goes down by 1. When this use count hits 0, we remove | |
| that super block from the list of all valid super blocks stored in | |
| the vector. While doing this, we also make sure that the basic | |
| invariant is maintained by making sure that _S_last_request and | |
| _S_last_dealloc_index point to valid locations within the vector. | |
| </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> | |
| Q1) The "Data Layout" section is | |
| cryptic. I have no idea of what you are trying to say. Layout of what? | |
| The free-list? Each bitmap? The Super Block? | |
| </p><p> | |
| The layout of a Super Block of a given | |
| size. In the example, a super block of size 32 x 1 is taken. The | |
| general formula for calculating the size of a super block is | |
| 32 x sizeof(value_type) x 2^n, where n ranges from 0 to 32 for 32-bit | |
| systems. | |
| </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> | |
| And since I just mentioned the | |
| term `each bitmap', what in the world is meant by it? What does each | |
| bitmap manage? How does it relate to the super block? Is the Super | |
| Block a bitmap as well? | |
| </p><p> | |
| Each bitmap is part of a Super Block which is made up of 3 parts | |
| as I have mentioned earlier. Re-iterating, 1. The use count, | |
| 2. The bit-map for that Super Block. 3. The actual memory that | |
| will be eventually given to the user. Each bitmap is a multiple | |
| of 32 in size. If there are 32 x (2^3) blocks of single objects | |
| to be given, there will be '32 x (2^3)' bits present. Each 32 | |
| bits managing the allocated / free status for 32 blocks. Since | |
| each size_t contains 32-bits, one size_t can manage up to 32 | |
| blocks' status. Each bit-map is made up of a number of size_t, | |
| whose exact number for a super-block of a given size I have just | |
| mentioned. | |
| </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> | |
| How do the allocate and deallocate functions work in regard to | |
| bitmaps? | |
| </p><p> | |
| The allocate and deallocate functions manipulate the bitmaps and | |
| have nothing to do with the memory that is given to the user. As | |
| I have earlier mentioned, a 1 in the bitmap's bit field | |
| indicates free, while a 0 indicates allocated. This lets us | |
| check 32 bits at a time to check whether there is at least one | |
| free block in those 32 blocks by testing for equality with | |
| (0). Now, the allocate function will given a memory block find | |
| the corresponding bit in the bitmap, and will reset it (i.e., | |
| make it re-set (0)). And when the deallocate function is called, | |
| it will again set that bit after locating it to indicate that | |
| that particular block corresponding to this bit in the bit-map | |
| is not being used by anyone, and may be used to satisfy future | |
| requests. | |
| </p><p> | |
| e.g.: Consider a bit-map of 64-bits as represented below: | |
| 1111111111111111111111111111111111111111111111111111111111111111 | |
| </p><p> | |
| Now, when the first request for allocation of a single object | |
| comes along, the first block in address order is returned. And | |
| since the bit-maps are in the reverse order to that of the address | |
| order, the last bit (LSB if the bit-map is considered as a | |
| binary word of 64-bits) is re-set to 0. | |
| </p><p> | |
| The bit-map now looks like this: | |
| 1111111111111111111111111111111111111111111111111111111111111110 | |
| </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> | |
| Another issue would be whether to keep all the bitmaps in a | |
| separate area in memory, or to keep them near the actual blocks | |
| that will be given out or allocated for the client. After some | |
| testing, I've decided to keep these bitmaps close to the actual | |
| blocks. This will help in 2 ways. | |
| </p><div class="orderedlist"><ol class="orderedlist" type="1"><li class="listitem"><p>Constant time access for the bitmaps themselves, since no kind of | |
| look up will be needed to find the correct bitmap list or its | |
| equivalent.</p></li><li class="listitem"><p>And also this would preserve the cache as far as possible.</p></li></ol></div><p> | |
| So in effect, this kind of an allocator might prove beneficial from a | |
| purely cache point of view. But this allocator has been made to try and | |
| roll out the defects of the node_allocator, wherein the nodes get | |
| skewed about in memory, if they are not returned in the exact reverse | |
| order or in the same order in which they were allocated. Also, the | |
| new_allocator's book keeping overhead is too much for small objects and | |
| single object allocations, though it preserves the locality of blocks | |
| very well when they are returned back to the allocator. | |
| </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> | |
| Expected overhead per block would be 1 bit in memory. Also, once | |
| the address of the free list has been found, the cost for | |
| allocation/deallocation would be negligible, and is supposed to be | |
| constant time. For these very reasons, it is very important to | |
| minimize the linear time costs, which include finding a free list | |
| with a free block while allocating, and finding the corresponding | |
| free list for a block while deallocating. Therefore, I have | |
| decided that the growth of the internal pool for this allocator | |
| will be exponential as compared to linear for | |
| node_allocator. There, linear time works well, because we are | |
| mainly concerned with speed of allocation/deallocation and memory | |
| consumption, whereas here, the allocation/deallocation part does | |
| have some linear/logarithmic complexity components in it. Thus, to | |
| try and minimize them would be a good thing to do at the cost of a | |
| little bit of memory. | |
| </p><p> | |
| Another thing to be noted is the pool size will double every time | |
| the internal pool gets exhausted, and all the free blocks have | |
| been given away. The initial size of the pool would be | |
| sizeof(size_t) x 8 which is the number of bits in an integer, | |
| which can fit exactly in a CPU register. Hence, the term given is | |
| exponential growth of the internal pool. | |
| </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> |