void *p = malloc(13);
Almost all of us has seen this before when writing a safe c program. we know what this line does, atleast we know the purpose of it,
ask for 13 bytes, get 13 bytes
that’s what i thought when i started building this on a friday out of curiosity. 30 mins into it, without writing a single line of code… i knew that this almost never happens.
this simple line holds multiple interesting computations and allocations in itself under-the-hood.
for example, when I request 13 bytes.
actually reserved:
+--------+--------------+---------+-------------+
| Header | Back Pointer | Padding | User Memory |
+--------+--------------+---------+-------------+
the user memory is the only thing we are gonna use and the *p returns the start of that memory. all the others are just there… not for usage.. why is that??
i wondered the same, instead of going into theory.. let’s build a allocator and free.
the simplest possible allocator
the simplest possible allocator doesn’t even have a free(). it’s called a bump allocator - you give it a big chunk of memory upfront (an arena), and every allocation just… moves a pointer forward.
typedef struct {
uint8_t *cursor;
uint8_t *limit;
} Arena;
cursor is where the next allocation starts. limit is where the arena ends. that’s the whole design.
void *bump_alloc(Arena *a, size_t size) {
if (a->cursor + size > a->limit) return NULL; // out of memory
void *ptr = a->cursor;
a->cursor += size;
return ptr;
}
that’s it. you can only ever move forward. it’s the fastest possible allocator. but functionally, useless for anything long-running, because there’s no free(). you can only free the whole arena at once, never a single object inside it.
which raises the obvious question: if I can’t free one thing, how do I ever get those 13 bytes back?
turns out.. you can’t, not with this design. to get individual free() working, the allocator needs to remember something about every allocation it handed out. and that’s the moment metadata stops being optional.
why metadata
free(ptr) gets exactly one argument which is a pointer. if the allocator’s job is to reclaim that memory and make it reusable, it has to answer a question the caller never tells it:
how big was this allocation, and where does it actually begin?
the only way to answer that is to store the answer somewhere the allocator can find later, using nothing but ptr itself. the obvious place is right before the memory you handed out.
typedef struct {
size_t size;
} Header;
so instead of just handing back raw memory, alloc() now does this:
[ Header ][ User Memory ]
^
returned to caller
and free(ptr) walks backward:
Header *h = (Header *)ptr - 1;
// now h->size tells us how big this block was
this is the naive approach. there is more ;)
naive header vs alignment
not every type wants to live at any address. they call it alignment.
chardoesn’t care where it sits in memory. (alignment = 0)doubledoes most platforms require it to start at an address that’s a multiple of 8 (alignment = 8) …and many more for different types.
there is no strict rule that stops the program from compiling when using a different alignment. it comes where the performance may hit or crashes happen unexpectedly because of it.
so alloc() doesn’t just need to hand back a pointer. it needs to hand back a pointer that’s correctly aligned for whatever type the caller is about to store there.
which means there might be a gap between where the header ends and where the user pointer actually needs to start, and that gap is a different size every single time, depending on what alignment was requested.
the gap is what they call a padding.
[ Header ][ ...variable padding... ][ User Memory ]
and this is exactly where header = (Header *)ptr - 1 falls apart. that subtraction assumes a fixed distance from ptr back to the header. but the padding isn’t fixed, it changes per-allocation.
free() has no way of knowing how much padding was inserted for this specific pointer, so it can’t reliably walk backward to find the header anymore.
the back pointer
if the distance to the header isn’t fixed, don’t rely on distance. store a pointer to the header instead, at a position that is always fixed.
[ Header ][ ...variable padding... ][ Back Pointer ][ User Memory ]
^ always exactly sizeof(void*)
bytes before User Memory,
no matter how much padding
came before it
now free() doesn’t need to know or recompute any padding. it just does:
Header *h = *(Header **)((uint8_t *)ptr - sizeof(void*));
that slot is always sizeof(void*) bytes before the user pointer, every single time, regardless of alignment.
the header can live wherever it wants, as far away as it wants. and the back pointer just points at it.
okay but which pointer actually gets aligned
wait.. it’s not the arena’s cursor that needs aligning. it’s the user pointer, the thing you actually hand back to the caller. the arena cursor can sit wherever it lands; nobody ever dereferences it directly.
so the actual math looks like this:
candidate = header + sizeof(Header) + sizeof(void*)
padding = align(candidate, alignment)
user_ptr = candidate + padding
and the padding amount gets stored in the header too, mostly because it turned out useful for debugging and testing later, you can sanity-check user_ptr - padding lands exactly back on candidate.
internal fragmentation
once i had all this working => header, back pointer, alignment. i sat with the layout for a second:
[ Header ][ Back Pointer ][ Padding ][ User Memory ]
and the obvious question showed up:
those padding bytes between the metadata and my actual object… they’re just sitting there, unused, for the entire lifetime of the allocation. why can’t the allocator reuse them?
because the allocation has to be one contiguous block. the caller was promised N contiguous bytes starting at user_ptr, and there’s no way to describe “here’s your memory, except for these 3 bytes in the middle, those belong to something else” without breaking the entire contract of what an allocation is.
so those bytes are allocated, in the sense that they belong to this block and can’t be given to anyone else, but they’re never touched, by anyone, ever. that’s internal fragmentation where waste that exists purely because of alignment requirements, baked into every single allocation that needs padding.
how can we free the allocated memory?
in most languages like Python, Golang, there is a component inside the interpreter or the compiler itself called garbage collector which checks for the lifetime of a memory and clears out its space if it has gone out of scope or no longer used in the flow.
but in older languages like C, one has to manually free the allocated memory. there are rules to it, which require its own blog post.
so with header + back pointer sorted, free() finally becomes possible. but a bump allocator still can’t do it, because there’s no concept of reuse anywhere in it. so the design has to change shape: instead of a cursor that only moves forward,
we need a free list, a linked list of blocks that have been freed and are sitting around, available to be handed out again.
typedef struct FreeNode {
size_t size;
struct FreeNode *next;
} FreeNode;
free(ptr) finds the header (via the back pointer), and pushes it onto the front of this list:
void push_free(FreeNode *node) {
node->next = free_list;
free_list = node;
}
and alloc() now has two paths instead of one:
- walk the free list, looking for a block big enough (
search_free) - if nothing fits, fall back to the old bump-the-cursor behavior
first-fit is the simplest search strategy… take the first block that’s big enough, don’t overthink it. getting fancier (best-fit, segregated lists by size class) is a real rabbit hole, but first-fit is enough to prove the concept works.
splitting
the first version of my allocator had a pretty silly habit.
if it found a free block that was big enough, it gave away the entire thing, even if only a tiny portion was needed.
request: 8 bytes
free block:
+-------------------------------------------+
| 200 bytes |
+-------------------------------------------+
result:
+-------------------------------------------+
| all 200 bytes are occupied |
+-------------------------------------------+
the program only uses the first few bytes, but the remaining 192 bytes cannot be used by anyone else until that allocation is freed. that is wasted memory. the fix is splitting.
instead of handing over the entire block, cut it into two pieces.
before
+-------------------------------------------+
| free block |
+-------------------------------------------+
after
+------------+------------------------------+
| allocation | still free |
+------------+------------------------------+
the front becomes the allocation.
the rest goes straight back onto the free list, ready for the next request. well, that sounded easy. it wasn’t.
the first time i implemented it, i accidentally started the second block in the wrong place. i forgot that the first block’s metadata also takes up space. instead of creating the second block after the first block had completely finished, i created it slightly too early.
the bug took a while to find because the allocator was not crashing immediately. it was quietly corrupting itself.
another lesson was knowing when not to split.
suppose splitting leaves only a handful of bytes behind. that is not really another free block. it is just clutter. if the leftover is not even large enough to describe itself, there is no point keeping it around.
so sometimes it is actually better to waste a few bytes than to create a tiny block that can never be used again.
i called this limit min_split_size.
coalescing: putting the puzzle back together
well, splitting creates smaller blocks. eventually, though, the opposite problem appears.
imagine cutting a sheet of paper into lots of little pieces. even if you have plenty of paper in total, none of the pieces might be big enough for what you want. memory behaves the same way.
suppose i allocate two blocks.
+--------+--------+
| a | b |
+--------+--------+
later, both are freed.
+--------+--------+
| free a | free b |
+--------+--------+
they are sitting right next to each other in memory. together, they are large enough for a bigger allocation.
but my allocator still thinks they are two separate blocks.
so if someone asks for something larger than either one individually…
need: 32 bytes
available:
16 bytes
16 bytes
…the allocation fails, even though there is enough memory overall.
the fix is called coalescing.
it is just a fancy word for joining neighboring free blocks back together.
before
+--------+--------+
| free a | free b |
+--------+--------+
after
+-----------------+
| one big block |
+-----------------+
finding the block on the right was easy because every block knew its own size which gives the previous one’s end, but none of them know where the previous one started.
the solution was surprisingly simple.
write the size down twice. once at the beginning of the block. and again at the end.
+--------+---------+--------+
| header | data | footer |
+--------+---------+--------+
now, standing at the start of any block, i could look just behind me, read the previous block’s size from its footer, and jump directly back to its header.
only then could i merge blocks in both directions.
it was one of those moments where solving one problem meant adding even more metadata, which was the exact opposite of what i expected when i started trying to make my allocator “smaller.”
wrapping up
what started as “let me write my own malloc” quickly became a series of trade-offs. adding alignment introduced padding and down went the rabbit hole, every solution fixed one problem while introducing the next. that is probably the biggest thing i took away from this project.
…more for the curious
these didn’t make it into the main article, but they’re probably the bugs i learned the most from.
bug #1: “wait… why is this even crashing?”
after implementing splitting, everything looked fine.
then i compiled with -fsanitize=undefined.
runtime error: member access within misaligned address 0x61d000000173
for type 'struct FreeNode', which requires 8 byte alignment
my first thought was, “that makes no sense. i’m already aligning every allocation.”
turns out i was aligning the user pointer, not the remainder header.
when a large block was split, i was simply dropping a FreeNode wherever the remaining bytes happened to begin.
FreeNode *remainder =
(FreeNode *)((uint8_t *)header + sizeof(FreeNode) + needed);
sometimes that address wasn’t divisible by 8. sometimes it was. which explained why the bug only appeared occasionally.
the fix was simply to align the remainder before treating it as a FreeNode.
after that, the sanitizer was happy. for about five minutes.
bug #2: corruption 400 operations later
this one was the worst.
my stress test performed thousands of random allocations and frees. everything looked fine until, hundreds of operations later, an allocation that hadn’t even been touched suddenly became corrupted.
the cause turned out to be embarrassingly simple. i only wrote footers when freeing a block or when splitting one. ordinary allocations never got a footer.
so much later, when coalescing tried to walk backwards, it read whatever random bytes happened to be sitting where the footer should have been. those random bytes became a random block size. the random block size became a random pointer.
the fix was to every time a block’s size changes, write its footer. always!!