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,
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.
+--------+--------------+---------+-------------+ | 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 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.
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 ;)
not every type wants to live at any address. they call it alignment .
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.
[ 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.
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.
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.
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 .
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.
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:
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.
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.
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.
+--------+--------+ | 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.
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.
Hacker NewsJuly 20, 20269 min read4 views