libstdc++-v3/doc/html/manual/bitmap_allocator.html

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