When to split a free block in a C memory allocator

Split a free block only when the request fits and the leftover space can hold a complete, usable free block. If your sizes include headers and padding, the rule is S >= need followed by S - need >= M, where S is the old block span, need is the aligned allocation span, and M is the minimum valid free-block span. Otherwise, allocate the whole block and keep its original recorded span.
This article uses the byte-offset model from how to write a small memory allocator in C: a fixed arena, an implicit list, and positive-size byte allocations. It explains the split decision, not a drop-in malloc implementation.
Define the minimum free block before deciding when to split
A remainder is another block, not just unused payload. It needs its own metadata and enough space to satisfy your allocator’s smallest supported request.
Use these quantities consistently:
A: chosen positive alignment, in C bytes.P: header footprint, rounded up to a multiple ofA.S: existing block’s total span, including its header.need: total span required for this request.M: minimum total span of a valid free block.
For an implicit list with no footer or free-list links in the payload, supporting requests as small as one byte:
need = round_up(P + n, A)
M = round_up(P + 1, A)
The stored header representation must fit inside P. Its footprint is not necessarily sizeof the logical header struct: C structs can contain padding, and the payload must meet your chosen alignment. See aligning the payload and the next block for that layout calculation.
If you store free-list pointers inside free payloads, or add boundary-tag footers, recompute M to fit the complete free-block format. Do not copy a minimum from an allocator with different metadata. These free-list lecture notes explain how alignment and free-block metadata determine minimum block size.
One extra requested byte can change the split decision
Choose A = 16, P = 16, and an existing free block of span S = 128. These are teaching dimensions, not guarantees about a C implementation. The minimum free-block span is M = round_up(17, 16) = 32.
For an 80-byte request:
need = round_up(16 + 80, 16) = 96.- The remainder is
128 - 96 = 32bytes: exactly the minimum. - Split into an allocated block
[0, 96)and a free block[96, 128). - The remainder’s header occupies
[96, 112); its usable byte space is[112, 128).
For an 81-byte request, need rounds up to 112. The 16-byte remainder could hold the header footprint but no payload, so do not split. Keep one allocated block of span 128. Its requested payload occupies [16, 97) and its unused tail occupies [97, 128): 31 bytes of internal slack, including alignment padding.
The cover diagram uses the same byte scale for both cases. A failed split does not make the trailing bytes disappear; they remain inside the allocated block.
Other boundaries worth checking for this 128-byte block:
- A 1-byte request needs 32 bytes and leaves a 96-byte free block.
- A 112-byte request needs all 128 bytes: an exact fit, with no split.
- A 113-byte request needs 144 bytes, so this block does not fit. Do not subtract to calculate a remainder.
Use >= M, not > M. A remainder exactly equal to the minimum is valid.
Calculate the request span without unsigned overflow
This C function handles the sizing calculation for the model above. It deliberately rejects zero-size requests; that is this allocator’s policy, not a description of every system malloc. It uses modulo-based rounding, so it does not require power-of-two alignment.
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
static bool span_for(
size_t n, size_t P,
size_t A, size_t *out)
{
if (n == 0 || A == 0)
return false;
if (P % A != 0)
return false;
if (n > SIZE_MAX - P)
return false;
size_t x = P + n;
size_t r = x % A;
size_t pad = r ? A - r : 0;
if (x > SIZE_MAX - pad)
return false;
*out = x + pad;
return true;
}
Pass a valid output pointer and an aligned header footprint P. On failure, do not use the output’s previous contents as a new allocation size. The first overflow check protects P + n; the second protects rounding up. A wrapped size could otherwise make an enormous request appear to fit a small block.
After sizing succeeds, make the decision in this order:
if S < need:
this block does not fit
else:
remainder = S - need
if remainder >= M:
allocate span need
create free span remainder
else:
allocate span S
Check the fit before subtracting: size_t subtraction wraps if need > S. Also prefer this subtraction-based threshold to an unchecked S >= need + M, whose addition can overflow.
Preserve the old block’s physical extent
Suppose the selected block starts at offset b. Before modifying metadata, validate that it is free, that its span is aligned and at least M, and that S <= N - b within the arena of size N. Validate the offset and available header bytes before reading metadata or forming pointers.
When splitting, save the old span, then create:
- An allocated header at
bwith spanneed. - A free header at
b + needwith spanS - need.
Both spans are multiples of A, so the new block start stays aligned. The accounting identity is need + remainder == S; the next block after the pair must still start at b + S.
When not splitting, change the allocation state but leave the span as S. Recording only need would make traversal treat the unusable tail as another block. That is a layout corruption, not merely wasted space.
If you use an explicit free list, the remainder must also be inserted into that index, and the allocated block removed. Physical spans alone do not repair list links.
Test the threshold, not just successful allocation
Append this test driver to the C function above and compile with a C11 compiler, for example cc -std=c11 sizing.c -o sizing. Run ./sizing without disabling assertions.
#include <assert.h>
#include <stdio.h>
int main(void)
{
const size_t P = 16, A = 16;
const size_t S = 128;
size_t M, need;
assert(span_for(1, P, A, &M));
assert(M == 32);
assert(span_for(80, P, A,
&need));
assert(need == 96);
assert(S - need == M);
assert(span_for(81, P, A,
&need));
assert(need == 112);
assert(S - need < M);
assert(span_for(112, P, A,
&need));
assert(need == S);
assert(span_for(113, P, A,
&need));
assert(need > S);
assert(!span_for(0, P, A,
&need));
assert(!span_for(SIZE_MAX,
P, A, &need));
assert(!span_for(SIZE_MAX - P,
P, A, &need));
puts("split tests passed");
}
These tests check sizing and threshold arithmetic; they do not test metadata writes. In the allocator itself, also assert that a split produces two valid blocks whose spans sum to the old span. For a no-split allocation, confirm that the old span is unchanged. Put another block immediately after the selected block and verify that neither path changes its start or header.
Heapcraft’s free first-lesson preview offers a smaller related exercise: implement align_offset and arena_take to reserve aligned slices in a 64-byte arena, then run seven C tests without registering. Try the free lesson; guest code and completion are unsaved, and registration is needed only to save work and continue. The lesson teaches aligned starts and bounds checks, not block splitting. The full guided allocator course is separate and unavailable, with no launch date; join its waitlist for updates.
