previousupnext

3.2 List Algorithm

LeapHeap uses the allocate and free routines described here for memory allocations above 4 KB. The list algorithm acts upon the data structures presented in section 2.2 Big-Block Area Data Structure.

Almost all the material in this section concerns the allocate routine. A freeing thread need only clear the allocd flag of the descriptor corresponding to the block it is freeing. How the freer locates that descriptor is an implementation detail.

An allocating thread navigates through the descriptor list examining free blocks. Navigating the list does not involve any locked instructions. Upon finding a free block of suitable size an allocator performs a block-fit or block-split operation. If it reaches the end of the list without this having been possible, it performs a block-append operation. The allocator may perform block-coalesce operations incidentally.


3.2.1 Block Fit
3.2.2 Block Split
3.2.3 Block Append
3.2.4 Block Coalesce
3.2.5 Constraints and Invariants
3.2.6 Coping With Concurrency
3.2.7 Concurrency Example