🚀 go-pugleaf

In article <90346.130938DLV101@psuvm.psu.edu>, DLV101@psuvm.psu.edu (Dwaine VanBibber) writes:
> ... what is "coalescing"? Why is it needed? ... how is it done? 

Coalescing is the merging of adjacent free blocks of memory. Most operating
systems include memory managers that maintain a linked list of free memory
blocks (usually called the 'free list'). Each block of memory in the list
contains information about how large the block is, and a link to the next
block in the list. When the system starts up, the free list pointer points
to one large contiguous block of free memory. A request for a memory block
will return a pointer to the start of this area, and the free list pointer
will be re-adjusted to point to the memory following the allocated block.

As blocks are freed (de-allocated), they are re-inserted in the linked
list of free memory blocks. Now let's assume that all of memory has been
consumed by mallocs for 1K blocks, and then all the blocks are freed. If
the free blocks were not coalesced, and a request for a block of 2K was 
made, the operating system could not honor it (since there is a block
header between each 1K of memory). 

In order to coalesce, the system must traverse the linked list of free
memory blocks, locate all blocks which are contiguous, revise the header
in the first block to reflect the size of the coalesced blocks, and 
remove the header in the second block (by revising the header in the
first block to point to the next non-coalesced block).

This can be done either when a block is freed, when a malloc is done,
or only when a malloc is done for which there is not a large enough
free block. There are performance trade-offs for each of the above.