How to write a small memory allocator in C
To write a small memory allocator in C, divide one contiguous arena into blocks, record each block’s total span and whether it is free, and walk those blocks to find space. Split a free block only when the remainder can form another valid block. On free, merge physically adjacent free blocks—not merely entries that happen to be neighbours in a list.
For a first implementation, use a fixed arena, an implicit block list and first-fit allocation. This keeps the mechanism visible: every next address follows from one checked block span. The model below uses byte offsets and byte payloads; it is not a drop-in malloc replacement.
How do you write a small memory allocator in C?
Choose these rules explicitly:
- One arena of
NC bytes; it never grows. A C byte is the unit measured bysizeof, not necessarily eight bits. - A fixed alignment
A, satisfied by the arena base and every block start. For the example,A = 16; that is an example value, not a C guarantee. - An actual metadata size
H. Round it up to a multiple ofAto get the header footprintP, the offset from block start to payload. - Positive allocation requests only. Return failure for zero, overflow or insufficient space; freeing a null handle is a no-op.
- Single-threaded use. A free operation accepts only an exact, still-live allocation returned by this allocator. Interior handles and double frees are errors.
For the simplest portable byte model, use an unsigned char arena and return payload offsets or byte pointers. Store metadata separately, or copy metadata representations with memcpy between arena bytes and a real header object. Do not cast a declared character array to a header pointer and assume alignment makes the typed access valid.
To try that byte-oriented storage method, run the completed C11 byte-arena example in your browser. It copies metadata with memcpy, preserves byte payloads and reports 14 checks, with no account or compiler setup. It demonstrates byte-oriented metadata storage—not arbitrary-object malloc, a portable wire format or the separate guest lesson.
If your goal is arbitrary typed client objects, the storage contract is more demanding. Declared objects have effective types; allocated storage has different rules. Borrowing an arena from the system allocator can supply suitably aligned storage without a declared type, but you must still reason about bounds, effective type and reuse. That is a suballocator, not an implementation of the system’s allocation primitive. See the C11 committee draft, sections 6.5 and 7.22.3, and cppreference’s explanation of objects, effective type and alignment.
The minimum block metadata is a span and a state
Each block needs two facts:
span: the total number of bytes occupied by the block, including its header footprint and all padding.is_free: whether allocation may reuse it.
The logical fields might be size_t span and a boolean state. Their physical representation is your choice; sizeof a C struct includes implementation-dependent padding. This model keeps the fields separate rather than packing a flag into size bits.
You do not need a next pointer. If a block begins at offset b, its physical successor begins at b + span. This is an implicit list: walk allocated blocks as well as free ones. Keep the arena base and size outside the blocks.
You also do not need a footer or previous pointer for correctness. A scan from the arena start can find a predecessor. Boundary tags and explicit free lists are later choices that change the cost and the minimum block size.
For this design, let the minimum usable block span be M = round_up(P + 1, A): room for the header footprint and at least one payload byte, with an aligned stride. Initialize one free block covering the arena. Choose N as a multiple of A, with N >= M.
Maintain these invariants after every operation:
- Blocks partition
[0, N)exactly: no gaps, overlaps or bytes outside the arena. - Every block start and span is a multiple of
A; every span is at leastM. - A payload begins at
b + P, and the requested bytes fit inside its block. - Each state is valid. A live allocation’s bytes are never given to another allocation.
- With immediate coalescing, no two physical neighbours are both free.
Those are the allocator’s specification. Tests should check them, not just whether one request returns success.
Walk blocks to allocate, then split only if the remainder fits
For a request of n bytes, compute need = round_up(P + n, A). Check overflow before adding or rounding. A general rounding method uses r = x % A, then adds zero if r == 0, otherwise A - r; check that addition against SIZE_MAX too.
Walk from offset zero. Read and validate each header, then choose the first free block whose span is at least need. Otherwise advance by its span. Reaching N without a fit means failure; offset N is an end marker, not another header.
In pseudocode, let read_checked validate a header and take perform the split-or-whole-block allocation described below. This is not copy-and-paste C:
b = 0
while b < N:
h = read_checked(b)
if h.free:
if h.span >= need:
take(b, need)
return payload(b + P)
b = b + h.span
return failure
Validation must establish enough remaining bytes for the metadata before reading it. Require span >= M, span % A == 0 and span <= N - b before advancing. Check integer offsets before forming pointers; do not form an invalid pointer and test it afterwards. In C, byte traversal uses character pointers, not arithmetic on void *.
Once a fit is found, calculate remainder = old_span - need:
- If
remainder >= M, write an allocated block of spanneedand a free remainder atb + need. - Otherwise, mark the entire old block allocated and retain its old span. The extra space is internal slack, not another block.
Never shrink the recorded span without writing a valid remainder. Doing so loses part of the arena during the next traversal. If you later put free-list links inside free blocks, recompute M to include them.
First fit over this implicit list takes linear time in the number of blocks in the worst case. It is a useful starting point because the traversal follows the physical layout directly, not because it is fast enough for every workload.
A checked 256-byte layout
Assume A = 16 and P = 16. The header representation fits within that footprint; these are chosen model dimensions, not a promise about a particular C struct. Then M = round_up(17, 16) = 32.
A different but common inline-header layout starts with the actual header size H, then rounds the payload offset up: P = round_up(H, A). For H = 24 bytes, request n = 13, and A = 16, the header occupies [0, 24), pre-payload padding occupies [24, 32), and the payload occupies [32, 45). Three tail-padding bytes make the total block span 48, so both the payload offset 32 and the next block boundary 48 are aligned to 16.
Open this exact header/request/alignment calculation in the live calculator. This is a layout calculation only: it assumes an already aligned block base and a header type whose alignment is satisfied, and does not by itself make arbitrary typed access valid C.
The worked 256-byte allocator below uses P = 16 as a chosen, already-rounded header footprint; it is not the H = 24 case above. Start with one free block [0, 256). A request for 33 bytes needs round_up(16 + 33, 16) = 64 bytes. Its header footprint is [0, 16), requested payload [16, 49), and tail slack [49, 64). Splitting leaves a 192-byte free block at offset 64.
A second request for 17 bytes needs round_up(16 + 17, 16) = 48 bytes. In that block, the header footprint is [64, 80), requested payload [80, 97), and tail slack [97, 112). Splitting leaves 144 free bytes at offset 112. Both remainders exceed the 32-byte minimum.
The diagram tracks the same boundaries through allocation and freeing. Labels give total block spans; pink marks the header footprint, which is included in each span.

The complete sequence in text:
- After allocating 33 bytes: allocated
[0, 64), free[64, 256). - After allocating 17 bytes: allocated
[0, 64), allocated[64, 112), free[112, 256). - After freeing the first: free
[0, 64), allocated[64, 112), free[112, 256). - After freeing the second and coalescing: free
[0, 256).
The three spans are 64 + 48 + 144 = 256. Block starts 0, 64 and 112, and payload starts 16 and 80, are multiples of 16. The ranges partition the arena without overlap. For another explanation of aligning both the payload and next block, see C allocator alignment: payload and next block.
Coalesce by physical adjacency, not free-list order
Freeing the first allocation leaves 64 free bytes before a live block and 144 free bytes after it. You cannot combine those 208 bytes into one allocation: doing so would include someone else’s live payload.
For blocks starting at left and right, physical adjacency means left + left_span == right, after bounds checks. Merge only if that condition holds and both blocks are free. The new span is their sum. The right block’s former header becomes part of the merged free space; it is no longer a header visited by traversal.
A simple implementation marks the target block free, then scans the whole arena for adjacent free pairs. When a pair merges, keep the scan at the left block and examine its new successor. Advancing immediately can miss a chain of three free blocks. This full scan avoids predecessor metadata, at the cost of linear-time free.
In the example, freeing the second block allows the 64-byte and 48-byte blocks to merge into 112 bytes. That block is then adjacent to the 144-byte remainder: 112 + 144 = 256. No payload is moved, and the one surviving header remains at offset zero.
If you later add an explicit free list, its neighbours are only bookkeeping neighbours. List order can differ from address order. A list link alone is never proof that two spans touch.
Test transitions before adding optimizations
Write a heap checker that walks the arena and verifies the invariants after every allocation and free. The Carnegie Mellon malloc lab recommends consistency checks including valid block addresses, no overlapping allocations and no adjacent free blocks left uncoalesced.
Start with these cases:
- Requests of 1, 16 and 17 bytes cross a rounding boundary with the example footprint: spans 32, 32 and 48.
- A 240-byte request exactly fills the 256-byte arena; a 241-byte request fails after rounding.
- A 209-byte request needs 240 bytes, leaving only 16. Do not split; retain the whole 256-byte span.
- Free two separated blocks and confirm they remain separated; then free the block between them and confirm one merged span.
- Fill each live payload with a distinct byte pattern. Check that later allocation, freeing and header updates leave other live payloads unchanged.
- Reject overflowing size calculations before changing metadata. Exercise zero-size policy, exhaustion and invalid handles without treating undefined client behaviour as a successful allocation.
This is a fixed-capacity educational allocator. Production malloc also needs memory-source integration, workload-sensitive placement, concurrency, performance and hardening choices. The CMU allocation lecture puts first fit, splitting and coalescing in that wider context. Get the layout and state transitions right before replacing the scan with a more elaborate index.
Try a small implementation step
The live alignment lesson is a narrower first exercise than the block allocator described here: implement align_offset and arena_take to reserve aligned slices in a 64-byte arena. Run seven real C tests without registering; guest code and completion are unsaved. The lesson exercises aligned starts and bounds checks, not block headers, splitting or coalescing.
It is the free first lesson in a limited preview, not the full guided allocator course. The full course is separate, unavailable and has no launch date; join its waitlist if you want to hear about the full course.
