This time we’re talking about the heap, but not the whole space.
A free list contains a set of elements that describe heap free space. In a 30-byte heap, where 0-9 and 20-29 blocks are occupied:
Free list before allocation
If we want 1 byte of memory, the allocator will find a free chunk of memory that’s large enough, and split it into two. The address of the first piece (20) is returned. Then the free list be like:
Free list after splitting
If a program calls free(10), the allocator will coalesce the free space. Now the free list be like:
Free list after coalescing
Most allocators store extra information in a header block, usually before the allocated memory.
Except for size, the header may contains a pointer, and a magic number for integrity check.
Thus, when a user request $N$ bytes of memory, the allocator searches for $N$+ header size.
Assume a free memory node is defined like this:
typedef struct __node_t {
int size;
struct __node_t *next;
} node_t;
Later we allocate some blocks, and the memory space is like picture in the left. sptr means the chunk to be freed later.
Allocate some blocks
Free a block
All blocks freed
When we free a block, it’s like the picture in the middle. The new free block next points to the former head, and head now points to the freed space.