A free list records free memory regions or reusable allocation units so an allocator can find storage for a request. In a variable-size pool, a record typically needs a block's location and length. A linked implementation also stores a link to another free record; these records can occupy the free blocks themselves. The term can also describe the allocator's logical inventory when its search structure is more elaborate than one linked chain.[ref]
For an illustrative inventory of free extents of16,32 and48 bytes, a24-byte request cannot use the first extent but can use either later one, before metadata and alignment are counted. Choosing the32-byte extent leaves an8-byte remainder if split exactly. Whether that remainder can become a free-list entry depends on the minimum free-block size.
Suppose an explicitly hypothetical in-block free record needs an8-byte length field and an8-byte next-link field. Its16-byte metadata cannot fit in that8-byte remainder. The allocator can instead give the request the entire32-byte block, leaving8 bytes of internal fragmentation, or choose another layout or block. Metadata placement is therefore part of allocation capacity, rather than an afterthought.
When a block is returned, memory block coalescing can combine it with adjacent free neighbors and update the inventory. Address order can make adjacency checks convenient; other orderings can favor allocation searches. A list that contains enough total free bytes may still lack one sufficiently large extent, producing external memory fragmentation. The search policy, split rule, metadata layout and coalescing policy jointly determine which requests succeed.
New to topics? Read the docs here!