Patch bitmap allocator.

Tue Mar 9 08:59:00 GMT 2004

This patch includes.

1. The bitmap_allcator.h file.
2. Modified 4 test-suite files to include bitmap_allocator.
3. Added 2 test-suite files: 
	(a). map_mt_find.cc=>Issues multithreaded finds on a 	map/multimap
	(b). list_sort_search.cc=>Repeatedly inserts, searches and sorts 	a
list data structure.

Also attached is the documentation for the bitmap_allocator file.

The documentation is the best I could come up with, but there may be
place for improvement, and I'd be welcome to change.

-- 
	-Dhruv Matani.
http://www.geocities.com/dhruvbird/

Proud to be a Vegetarian.
http://www.vegetarianstarterkit.com/
http://www.vegkids.com/vegkids/index.html
-------------- next part --------------
A non-text attachment was scrubbed...
Name: patch.bitmap_allocator
Type: text/x-patch
Size: 49082 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/libstdc++/attachments/20040309/d29a7f16/attachment.bin>
-------------- next part --------------
			BITMAPPED ALLOCATOR
			===================

---------------------------------------------------------------------

As this name suggests, this allocator uses a bit-map to keep track of
the used and unused memory locations for it's 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.

Data Layout:
============

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(unsigned int). 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 unsigned int has 32-bits
and Maximum use of these can be made with such a figure.

Consider a block of size 32 ints.
In memory, it would look like this:

---------------------------------------------------------------------
|   136   |    0    | 4294967295 |      Data-> Space for 32-ints    |
---------------------------------------------------------------------

The first Columns 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 + 4 + 32*4 = 140 bytes, but the first 4
bytes are an addition by the Free List Store, so the Bitmap Allocator
sees only 136 bytes. These first 4 bytes about which the bitmapped
allocator is not aware hold the value 136.

What do the remaining values represent?
---------------------------------------

The 2nd 4 in the expression is the sizeof(unsigned int) 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 4 is size of the bitmap itself, which is the size of 32-bits,
which is 4-bytes, or 1 X sizeof(unsigned int).

What is this Free List Store?
-----------------------------

The Free List Store (referred to as FLS for the remaining part of this
document) is 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 it's 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 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.  

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

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

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

--------------------------------------------------------------------

The macro __GTHREADS decides whether to use Mutex Protection around
every allocation/deallocation. This needs to be defined if you intend
using the bitmapped allocator from multiple threads. If not, then you
would be better off un-defining it because it would unnecessarily hamper
performance by causing unnecessary Locking/Unlocking.

--------------------------------------------------------------------

How does the allocate function Work?
------------------------------------

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:

1. Checks to see whether the 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.

2. Is there a free block anywhere after the current block right upto
   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.

3. Is there any block in whatever region of memory that we own free?
   This is done by checking (a) The use count for each super block,
   and if that fails then (b) 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).

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:
	 (a). Gets more memory from the Global Free List of the
	      Required size.
	 (b). Adjusts the size for the next call to itself.
	 (c). Writes the appropriate headers in the bit-maps.
	 (d). Sets the use count for that super-block just allocated
	      to 0 (zero).
	 (e). 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.

-------------------------------------------------------------------------

How does the deallocate function work?
--------------------------------------

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:

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

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

--------------------------------------------------------------------

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. 

1. Constant time access for the bitmap themselves, since no kind of
look up will be needed to find the correct bitmap list or it's
equivalent.

2. 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 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(unsigned
int)*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.