= Minimum free-block size
The <minimum free-block size> is the smallest extent that an allocator's representation can retain as an independent free record. It depends on where the allocator stores a region's size, links and other metadata, as well as <memory alignment>. A region may contain unused <bytes> yet be too short to enter the <free list>. OSTEP demonstrates why allocator metadata must be counted: free records can be embedded inside the free regions themselves.<Operating Systems: Three Easy Pieces by Remzi H. Arpaci-Dusseau and others>[Chapter17, §17.2, “Embedding A Free List”, printed pp.6–9]{ref}
For a hypothetical allocator, let a free record need an8-<byte> size field and two8-<byte> links. Its raw metadata requires24 <bytes>. If all block lengths are multiples of16 <bytes>, its minimum independently representable size is
$$
M=16\left\lceil\frac{24}{16}\right\rceil=32\ \text{bytes}.
$$
The exact fields and sizes are illustrative. An allocator with separate metadata, a singly linked record or another block granularity can have another minimum.
Suppose the same allocator uses an8-<byte> allocated-block header. An8-<byte> payload plus that header would occupy16 <bytes> before enforcing the minimum. Reserving32 <bytes> ensures that this block can later become an independent free record. Extra allocation space of this kind contributes to <internal fragmentation>. The allocator might instead use a distinct representation for tiny blocks, so the formula is a design constraint for the stated representation rather than a universal allocation rule.
A proposed split also needs to respect the minimum. Taking80 <bytes> from a96-<byte> extent leaves16 <bytes>, an <unsplittable free-block remainder> under this layout. Giving the caller the full96-<byte> extent avoids making an invalid free record but consumes extra storage. Taking32 <bytes> would leave64, which can be retained. <Memory block coalescing> can later join adjacent returned extents, but the allocator must have a valid way to represent each extent until that happens.
Back to article page
