Subversion Repositories openrisc

         xml:id="manual.ext.allocator.bitmap" xreflabel="bitmap_allocator">

      ISO C++

      allocator

    As this name suggests, this allocator uses a bit-map to keep track

    of the used and unused memory locations for its book-keeping

    purposes.

    This allocator will make use of 1 single bit to keep track of

    whether it has been allocated or not. A bit 1 indicates free,

    while 0 indicates allocated. This has been done so that you can

    easily check a collection of bits for a free block. This kind of

    Bitmapped strategy works best for single object allocations, and

    with the STL type parameterized allocators, we do not need to

    choose any size for the block which will be represented by a

    single bit. This will be the size of the parameter around which

    the allocator has been parameterized. Thus, close to optimal

    performance will result. Hence, this should be used for node based

    containers which call the allocate function with an argument of 1.

    The bitmapped allocator's internal pool is exponentially growing.

    Meaning that internally, the blocks acquired from the Free List

    Store will double every time the bitmapped allocator runs out of

    memory.

    The macro __GTHREADS decides whether to use

    Mutex Protection around every allocation/deallocation. The state

    of the macro is picked up automatically from the gthr abstraction

    layer.

    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.

    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.

    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.

    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.

  Equal size check. Return true only when the 2 blocks are of equal

size.

  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. 

  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.

    Currently, (3) is being used with a value of 36% Maximum wastage per

    Super Block.

    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.

    How does it interact with the free list store?

    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.

    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.

    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.

    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).

      
      

         
170
         

         

         

      
      

         
171
         

         

         
 
      
      

         
172
         

         

         

      
      

         
173
         

         

         

      
      

         
174
         

         

         

      
      

         
175
         

         

         

      
      

         
176
         

         

         

      
      

         
177
         

         

         

      
      

         
178
         

         

         
 
      
      

         
179
         

         

         

      
      

         
180
         

         

         
  
      
      

         
181
         

         

         
    268
      
      

         
182
         

         

         
    0
      
      

         
183
         

         

         
    4294967295
      
      

         
184
         

         

         
    4294967295
      
      

         
185
         

         

         
    Data -> Space for 64 ints
      
      

         
186
         

         

         
  
      
      

         
187
         

         

         

      
      

         
188
         

         

         

      
      

         
189
         

         

         

    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.

  What do the remaining values represent?

    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.

    The value 4294967295 represents the integer corresponding to the bit

    representation of all bits set: 11111111111111111111111111111111.

    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).

    This has nothing to do with the algorithm per-se,

    only with some vales that must be chosen correctly to ensure that the

    allocator performs well in a real word scenario, and maintains a good

    balance between the memory consumption and the allocation/deallocation

    speed.

    The formula for calculating the maximum wastage as a percentage:

(32 x k + 1) / (2 x (32 x k + 1 + 32 x c)) x 100.

    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.

    Plugging-in: For List: k = 8 and c = 4 (int and double), we get:

    33.376%

For map/multimap: k = 12, and c = 4 (int and double), we get: 37.524%

    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.

    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.

    Suppose n == 1, then the allocator does the following:

        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.

        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.

        Is there any block in whatever region of memory that we own

        free?  This is done by checking

        The use count for each super block, and if that fails then

          The individual bit-maps for each super block.

        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).

        This process involves Refilling the internal exponentially

        growing memory pool. The said effect is achieved by calling

        _S_refill_pool which does the following:

            Gets more memory from the Global Free List of the Required

            size.

      Adjusts the size for the next call to itself.

      Writes the appropriate headers in the bit-maps.

        Sets the use count for that super-block just allocated to 0

        (zero).

          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.

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.

    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.

    However for n == 1, a series of steps are performed:

      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.

      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.

    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.

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?

      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.

      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?

      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.

      How do the allocate and deallocate functions work in regard to

      bitmaps?

      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 lease 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.

      e.g.: Consider a bit-map of 64-bits as represented below:

      1111111111111111111111111111111111111111111111111111111111111111

      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 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.

      The bit-map now looks like this:

      1111111111111111111111111111111111111111111111111111111111111110

    Another issue would be whether to keep the all 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.

  Constant time access for the bitmap themselves, since no kind of

look up will be needed to find the correct bitmap list or its

equivalent.

  And also this would preserve the cache as far as possible.

    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.

    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.

    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.