previousupnext

3.1 Bitmap Algorithm

LeapHeap uses the routines described here for memory allocations up to 4 KB. The bitmap algorithm operates upon the data structures that were presented in section 2.1 Compartment Area Data Structure.

The algorithm is inherently parallel and the instruction sequences in the implementation are the same for single-threaded and multithreaded operation. The two cases are described separately for allocate because the single-threaded case can be presented more concisely and readably.

Allocate

Single-threaded

  1. From the size requested (passed as parameter) determine the memory compartment from which to allocate.
  2. Find the first free (unset, zero) bit in the top-tier bitmap word.
  3. Calculate the address of the corresponding word in the bitmap tier below.
  4. Find the first free bit in the bitmap word.
  5. Repeat steps 3 and 4 until the tier-1 bitmap has been reached.
  6. Set the first free bit in the tier-1 bitmap word (BTS).
  7. Calculate the address of the memory cell corresponding to the seized bit.
  8. If the bit set in step 6 was the last remaining free bit in the tier-1 bitmap word (i.e. the word became all 1's) continue; otherwise there is nothing more do do, return the address of the memory cell to the caller.
  9. Go to the bitmap tier above, the same word as was used to navigate down.
  10. Complement the corresponding bit to '1' (BTC).
  11. If performing step 10 took the last free bit in the word, continue; otherwise the allocation is complete, return the address calculated in step 7.
  12. Repeat steps 9, 10 and 11 until (if necessary) the top tier bitmap has been processed.

Multithreaded

  1. From the size requested (passed as parameter) determine the memory compartment from which to allocate.
  2. Find the first free (unset, zero) bit in the top-tier bitmap word.
  3. Calculate the address of the corresponding word in the bitmap tier below.
  4. Find the first free bit in the bitmap word; if no free bit it means that another thread got there first, you are a contention victim.
  5. Repeat steps 3 and 4 until the tier-1 bitmap has been reached.
  6. Set the first free bit in the tier-1 bitmap word (BTS); if no free bit, you are a contention victim.
  7. Calculate the address of the memory cell corresponding to the seized bit.
  8. If the bit set in step 6 was the last remaining free bit in the tier-1 bitmap word (i.e. the word became all 1's) continue; otherwise there is nothing more do do, return the address of the memory cell to the caller.
  9. Go to the bitmap tier above, the same word as was used to navigate down.
  10. Complement the corresponding bit (BTC); normally this will set the bit, but it may be clearing it if another thread has overtaken.
  11. If performing step 10 caused a transition between at-least-one-bit-free and all-bits-set, in either sense, continue; otherwise the allocation is complete, return the address calculated in step 7.
  12. Repeat steps 9, 10 and 11 until (if necessary) the top tier bitmap has been processed.
The allocation sequence may appear complicated, but at machine level the implementation turns out to be straightforward. Navigation from one bitmap tier down to the next takes 10 Intel Pentium instructions; if navigation back up is necessary that takes 15 instructions per tier.

In a multithreaded process, a higher-tier bitmap may be momentarily inaccurate and lead an allocating thread down a blind alley. The contention victim still needs to find a free memory cell. There are any number of solutions, the simplest of which is to resort to linear search of the tier-1 bitmap.

The extra steps necessary to determine whether the memory underlying the newly-allocated cell is committed, and to invoke operating system memory management routines if it is not, are regarded as implementation details.

Free

  1. From the memory address to be freed (passed as parameter) determine the compartment within which the heap entry lies.
  2. Use the address again, this time to calculate cell number within the compartment.
  3. Navigate to the corresponding word of the tier-1 bitmap.
  4. Clear the relevant bit of the tier-1 bitmap word (BTR).
  5. If the tier-1 bitmap word was all 1's before, so that step 4 freed a bit in an otherwise full word, continue; otherwise the freeing is complete, return.
  6. Navigate to the corresponding word in the bitmap tier above
  7. Complement the relevant bit of the bitmap word (BTC).
  8. If performing step 7 caused a transition between all-bits-set and at-least-one-bit-free, in either sense, continue; otherwise the freeing is complete, return.
  9. Repeat steps 6, 7 and 8 until (if necessary) the top bitmap tier has been processed

One feature of the algorithm worthy of note is the modification of higher-tier bitmaps by complementing bits rather than by setting or clearing bits. This ensures the correctness of the algorithm despite threads passing one another. Each higher-level bitmap bit starts out as zero (free). As the program runs the bit is complemented a number of times equal to the number of full-to-not-full transitions of the corresponding word in the tier below, which starts out as not full. Therefore whenever the heap is quiescent the bit will accurately reflect the state of the word it controls. It is possible for an allocating thread, paradoxically, to clear a higher-tier bitmap bit, and for a freeing thread to set one.