= Free list
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.<Operating Systems: Three Easy Pieces by Remzi H. Arpaci-Dusseau and others>[Chapter17, §17.1, free-space inventory; §17.2, “Embedding A Free List”]{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.
Back to article page
