previousupnext

3.2.4 Block Coalesce

Unlike the other three operations, precisely one of which each allocator is bound to perform, block-coalesce may happen several times as a thread navigates the descriptor list, or not at all. The operation is performed whenever the thread encounters two consecutive free blocks. Coalescing becomes possible because of the actions of freeing threads, but in LeapHeap the task of coalescing freed blocks falls to allocators. Block-coalesce involves excising a block descriptor from the list and returning it to the pool of unused descriptors. A penultimate descriptor (one with a non-zero penult count) is not allowed to play the role of either block, even though it may be marked free.


The thread sets (BTS) the allocd flag in each of the two free descriptors, then overwrites the nxt field of the first with the content of the nxt field of the second. The second descriptor, which at that moment becomes unused, remains in the allocated state; the first descriptor is set free again.