Originally published by @nibblebitsArticle at version 1
A kernel heap does not have to begin with balanced trees, boundary tags, or dozens of size classes. You can build a useful first allocator from three ingredients:
- A contiguous arena of memory.
- A fixed block size.
- A byte table that records which blocks belong to each allocation.
This article builds that allocator from the raw mechanics upward. The design is conceptually based on the fixed-block table used by PeachOS, but the implementation below is written from scratch with stricter validation and a deliberately narrow scope: one heap, one arena, and clear allocation rules.
That narrow scope is valuable. Before deciding how to combine multiple memory regions, it is worth understanding exactly how one heap turns a byte count into a pointer and later reconstructs enough information to free it.
What this heap manages
The heap receives an address range that is already safe to access:
arena start arena end
| |
v v
+--------+--------+--------+--------+--- ... ----+
| block0 | block1 | block2 | block3 | |
+--------+--------+--------+--------+--- ... ----+
It does not discover physical RAM. It does not create page tables. It does not decide whether a frame belongs to a device. Those are lower-level jobs.
The heap's contract is simpler:
- Divide an accessible arena into equal blocks.
- Find adjacent free blocks for each request.
- Mark those blocks as one allocation.
- Return the address of the first block.
- Given that address later, release the entire allocation.
This separation makes the allocator testable in an ordinary program before it is linked into a kernel.
Choosing the allocation granule
We will use 4 KiB blocks:
#define HEAP_BLOCK_SIZE 4096u
Four KiB is convenient when the heap is backed by 4 KiB pages. Every returned pointer is naturally page-aligned, and allocation callbacks can operate one page at a time. The cost is internal fragmentation: a one-byte request consumes a full 4 KiB block.
That is acceptable for a first kernel heap or a page-granular backing allocator. Later, a slab or size-class allocator can sit on top and divide these blocks into smaller objects. Do not hide that tradeoff: this design favors simple bookkeeping over density for tiny allocations.
Any request is rounded upward to a whole number of blocks. For example:
request blocks used capacity
1 byte 1 4096 bytes
4096 bytes 1 4096 bytes
4097 bytes 2 8192 bytes
13000 bytes 4 16384 bytes
Rounding must be checked for integer overflow:
static bool blocks_for_size(size_t bytes, size_t *result)
{
if (!result || bytes == 0)
return false;
if (bytes > SIZE_MAX - (HEAP_BLOCK_SIZE - 1))
return false;
*result = (bytes + HEAP_BLOCK_SIZE - 1) / HEAP_BLOCK_SIZE;
return true;
}
Returning NULL for a zero-byte request keeps the core rules unambiguous.
One metadata byte per block
The allocator needs to answer two questions about every block:
- Is the block free or used?
- If it is used, does its allocation continue into the next block?
It is also helpful to mark the first block explicitly so that free() can reject pointers into the middle of an allocation.
Three flag bits are enough:
enum heap_tag {
HEAP_TAG_FREE = 0,
HEAP_TAG_USED = 1u << 0,
HEAP_TAG_HEAD = 1u << 6,
HEAP_TAG_NEXT = 1u << 7
};
The flags are combined in one uint8_t per arena block. A three-block allocation is encoded like this:
table index 0 1 2
tag USED|HEAD|NEXT USED|NEXT USED
meaning allocation middle end
starts continues
The final block has no NEXT bit. That missing bit is the end marker.
With 4 KiB blocks, the table costs one byte for every 4096 bytes of managed memory, roughly 0.024 percent. A 64 MiB arena needs 16,384 table entries, so its table occupies 16 KiB.
The heap structure
Keep the metadata separate from the arena initially. That removes the circular problem of using the heap before it exists.
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <string.h>
struct raw_heap {
uint8_t *arena;
uint8_t *tags;
size_t block_count;
size_t free_blocks;
};
arena points at block zero. tags[i] describes block i. The block count defines both arrays' logical length, while free_blocks provides a quick rejection path when a request is larger than all available space.
Initialization establishes the invariants:
bool heap_init(struct raw_heap *heap,
void *arena,
size_t arena_bytes,
uint8_t *tag_storage,
size_t tag_storage_bytes)
{
if (!heap || !arena || !tag_storage)
return false;
if (((uintptr_t)arena % HEAP_BLOCK_SIZE) != 0)
return false;
if (arena_bytes == 0 ||
(arena_bytes % HEAP_BLOCK_SIZE) != 0)
return false;
size_t blocks = arena_bytes / HEAP_BLOCK_SIZE;
if (tag_storage_bytes < blocks)
return false;
heap->arena = (uint8_t *)arena;
heap->tags = tag_storage;
heap->block_count = blocks;
heap->free_blocks = blocks;
memset(heap->tags, HEAP_TAG_FREE, blocks);
return true;
}
The function requires an exactly block-aligned arena rather than silently losing bytes at its edges. Startup code can align the proposed range before calling it.
The most important invariant is:
tag count == arena size / block size
If this relationship is wrong, the allocator can return addresses outside the arena or read beyond the table.
Finding adjacent free blocks
A request for several blocks must be physically adjacent within this arena's address sequence. A first-fit scan is the simplest policy: walk from the beginning and choose the first free run long enough for the request.
static bool find_free_run(const struct raw_heap *heap,
size_t needed,
size_t *start_out)
{
if (!heap || !start_out || needed == 0)
return false;
if (needed > heap->free_blocks)
return false;
size_t run_length = 0;
for (size_t i = 0; i < heap->block_count; i++) {
if (heap->tags[i] == HEAP_TAG_FREE) {
run_length++;
if (run_length == needed) {
*start_out = i + 1 - needed;
return true;
}
} else {
run_length = 0;
}
}
return false;
}
Notice that free_blocks cannot prove a suitable run exists. A heap may have ten free blocks scattered as ten one-block holes and still be unable to satisfy a two-block request. The counter only proves when a search would be pointless.
First-fit is an O(n) operation in the number of table entries. That is fine for a small first implementation. It also keeps free simple: clearing table entries automatically makes adjacent holes one larger run. There is no linked-list coalescing step.
Recording one allocation
Once a run has been found, build a chain in the tag table:
static void mark_allocation(struct raw_heap *heap,
size_t start,
size_t count)
{
for (size_t offset = 0; offset < count; offset++) {
uint8_t tag = HEAP_TAG_USED;
if (offset == 0)
tag |= HEAP_TAG_HEAD;
if (offset + 1 < count)
tag |= HEAP_TAG_NEXT;
heap->tags[start + offset] = tag;
}
}
The allocation function now has a short, auditable path:
void *heap_alloc(struct raw_heap *heap, size_t bytes)
{
if (!heap)
return NULL;
size_t needed;
if (!blocks_for_size(bytes, &needed))
return NULL;
size_t start;
if (!find_free_run(heap, needed, &start))
return NULL;
mark_allocation(heap, start, needed);
heap->free_blocks -= needed;
return heap->arena + (start * HEAP_BLOCK_SIZE);
}
The order is intentional:
- Validate and round the request.
- Find a run without changing state.
- Mark the complete run.
- Update accounting once.
- Convert the starting index to an address.
No public pointer is produced until the metadata represents the allocation.
Converting a pointer back to a block
Freeing is harder than allocating because the caller supplies a pointer that might be wrong. Before touching metadata, confirm that the pointer:
- is not null;
- is at or above the arena base;
- is below the arena end;
- is aligned to the block size;
- points to an entry marked as the head of a used allocation.
Use integer addresses for the checked conversion:
static bool pointer_to_block(const struct raw_heap *heap,
const void *ptr,
size_t *index_out)
{
if (!heap || !ptr || !index_out)
return false;
uintptr_t base = (uintptr_t)heap->arena;
uintptr_t address = (uintptr_t)ptr;
if (address < base)
return false;
uintptr_t offset = address - base;
size_t arena_bytes = heap->block_count * HEAP_BLOCK_SIZE;
if (offset >= arena_bytes)
return false;
if ((offset % HEAP_BLOCK_SIZE) != 0)
return false;
*index_out = (size_t)(offset / HEAP_BLOCK_SIZE);
return true;
}
The end address is exclusive. A pointer exactly one byte beyond the managed arena must fail rather than becoming an out-of-range table index.
Validate the chain before clearing it
It is tempting to clear entries while walking the NEXT bits. That can leave half an allocation freed if the table is corrupt. A safer approach first validates and measures the complete chain without mutating it.
static bool allocation_span(const struct raw_heap *heap,
size_t start,
size_t *count_out)
{
if (!heap || !count_out || start >= heap->block_count)
return false;
uint8_t first = heap->tags[start];
if ((first & (HEAP_TAG_USED | HEAP_TAG_HEAD)) !=
(HEAP_TAG_USED | HEAP_TAG_HEAD))
return false;
size_t count = 0;
for (size_t i = start; i < heap->block_count; i++) {
uint8_t tag = heap->tags[i];
if ((tag & HEAP_TAG_USED) == 0)
return false;
if (i != start && (tag & HEAP_TAG_HEAD) != 0)
return false;
count++;
if ((tag & HEAP_TAG_NEXT) == 0) {
*count_out = count;
return true;
}
}
return false;
}
If the chain reaches the end of the table while still claiming to continue, the function reports corruption. It also rejects a second head marker inside the same chain.
Now free() can be transactional at the table level:
bool heap_release(struct raw_heap *heap, void *ptr)
{
if (!heap)
return false;
size_t start;
if (!pointer_to_block(heap, ptr, &start))
return false;
size_t count;
if (!allocation_span(heap, start, &count))
return false;
memset(&heap->tags[start], HEAP_TAG_FREE, count);
heap->free_blocks += count;
return true;
}
An interior pointer fails because its tag lacks HEAP_TAG_HEAD. A second free fails because the first entry is already zero. In a debug kernel, these failures should trigger an assertion or diagnostic that includes the address and table index.
Walking through an example
Suppose the heap contains eight blocks. It starts entirely free:
index: 0 1 2 3 4 5 6 7
table: [F] [F] [F] [F] [F] [F] [F] [F]
Allocate 6,000 bytes for A. Rounding produces two blocks:
table: [UHN] [U] [F] [F] [F] [F] [F] [F]
A A
UHN means used, head, and continues. The second U is used and ends the chain.
Allocate one block for B, then three blocks for C:
table: [UHN] [U] [UH] [UHN] [UN] [U] [F] [F]
A A B C C C
Free B:
table: [UHN] [U] [F] [UHN] [UN] [U] [F] [F]
There are three free blocks in total, but there is no run of three. A three-block request must fail. A two-block request succeeds at indices 6 and 7. This is external fragmentation in its simplest form.
If A is later freed, indices 0 through 2 become one free run automatically because all three table entries are zero. The next scan sees the combined space without an explicit merge operation.
Adding zeroed allocation
A zeroed allocation can be built on the core operation:
void *heap_alloc_zeroed(struct raw_heap *heap, size_t bytes)
{
void *ptr = heap_alloc(heap, bytes);
if (!ptr)
return NULL;
memset(ptr, 0, bytes);
return ptr;
}
This clears the requested byte count. If the heap will transfer allocations between security domains, consider clearing the full rounded capacity or scrubbing blocks during free. Otherwise, padding at the end of the last block can retain old data.
For debugging, a different build can fill newly allocated blocks with a recognizable pattern and freed blocks with another. That makes uninitialized reads and use-after-free bugs easier to spot.
Where should the table live?
The cleanest bootstrap arrangement gives the heap two separate ranges:
metadata storage: [one tag per block]
data arena: [block 0][block 1][block 2]...
The table can also live at the beginning of the same large region, but its size affects where the aligned data arena begins, which in turn affects how many blocks fit. Resolve that relationship before initializing the heap:
- Estimate the block count as
region_bytes / HEAP_BLOCK_SIZE. - Reserve one metadata byte per estimated block.
- Align the address after the table upward to
HEAP_BLOCK_SIZE. - Recompute how many complete blocks fit between that address and the region end.
- Repeat until the block count stops changing.
Do this calculation in bootstrap code, not in heap_alloc(). Once initialization finishes, the heap should see a fixed table and a fixed arena.
The table must never overlap the arena it describes. Mark the metadata pages as reserved in the lower-level memory manager so another subsystem cannot hand them out.
Reallocation mechanics
realloc() is best added after allocation and free are thoroughly tested. Its cases are:
- A null old pointer behaves like a new allocation.
- A zero new size frees the old allocation and returns null.
- An unchanged block count returns the same pointer.
- A smaller request clears the trailing tags and removes
NEXTfrom the new final block. - A larger request first checks whether enough following blocks are free.
- If in-place growth is impossible, allocate elsewhere, copy, and free the old chain.
There are several traps:
- Check the table boundary before inspecting blocks after the allocation.
- Update
free_blocksexactly once. Do not let a helper change it and then change it again in the caller. - When shrinking, preserve
HEADon the first block and clearNEXTon the new last block. - When growing in place, add
NEXTto the old last block before publishing the larger allocation. - If the table stores only rounded capacity, it does not know the exact original byte request. Store requested sizes separately if exact
realloc()copy semantics matter.
That last point is important. A block chain can tell you that an allocation owns 8 KiB, but it cannot tell you whether the caller originally requested 4,100 bytes or 8,192 bytes. Minimal metadata creates a real information limit.
Locking and interrupt context
The code shown here assumes one caller at a time. On a multicore kernel, a lock must protect the search, tag updates, and counters as one operation. Unlocking between find_free_run() and mark_allocation() would let two CPUs claim the same blocks.
Choose the lock according to call context:
- If allocation can occur in interrupt context, a sleeping mutex is not sufficient.
- If the allocator can trigger page mapping or I/O, holding a spinlock across those operations is dangerous.
- If free can run concurrently with diagnostics, table inspection also needs synchronization or a snapshot scheme.
For a first heap, the simplest safe rule is often to prohibit allocation from interrupt context and use one lock around the complete operation. Optimize only after measuring contention.
Test the table, not only the returned pointers
A good test suite creates a small arena and inspects every tag after each operation. Cover at least:
- one-byte, exact-block, and block-plus-one requests;
- zero-byte and overflow-sized requests;
- filling the entire arena;
- allocation failure with enough total free blocks but no large enough run;
- freeing the first and last allocations;
- rejection of unaligned, out-of-range, interior, and double-free pointers;
- corrupted chains that end in a free entry or run beyond the table;
- reuse of a recently freed run;
- counter consistency after every success and failure.
Add a validator that walks the entire table and recomputes the number of free blocks. In a debug build, compare that value with heap->free_blocks after each mutation.
Property-based stress testing is especially effective: randomly allocate and free records, keep the live pointers in a separate test-side list, and verify that live ranges never overlap. Run the same sequence against arenas of only a few dozen blocks so fragmentation and exhaustion occur frequently.
Limits of the design
This allocator is intentionally simple:
- Allocation is O(n) because first-fit scans the table.
- A 4 KiB granule wastes space for small objects.
- Adjacent virtual blocks must come from one contiguous arena.
- The byte table records capacity, not the caller's exact requested size.
- One global lock will eventually become a scalability bottleneck.
None of these limits makes the design useless. It makes the design legible. The heap is a strong bootstrap allocator, a page-granular kernel allocator, or a backing source for a small-object allocator.
Natural improvements include:
- remembering the last successful scan position;
- maintaining free-run summaries;
- placing slabs or size-class caches above the heap;
- adding guard pages around selected large allocations;
- recording requested sizes and allocation sites;
- returning unused pages to the virtual-memory layer under pressure.
Managing several arenas is a separate policy layer. Get one heap's range checks, chains, counters, locking, and failure behavior correct before adding routing between heaps.
The core idea
A raw heap only needs a trustworthy mapping between table indexes and arena addresses:
address = arena_start + (block_index * block_size)
block_index = (address - arena_start) / block_size
Everything else protects that mapping:
- alignment makes the conversions exact;
- bounds checks keep indexes inside the table;
HEADrejects interior pointers;NEXTrecords allocation length;- a first-fit scan finds contiguous capacity;
- counters summarize state without replacing the table as the source of truth.
Build those mechanics carefully and the result is already a real heap. More sophisticated allocators improve speed, density, and scalability, but they do not replace the need for precise ownership and validated metadata.