Design a Memory Allocator

Understanding the problem

Almost every program you have ever written called malloc, directly or through a language runtime, and almost none of them stopped to ask what happened next. Intel wants the engineers who did. This is the most Intel-characteristic design question there is: build the thing that sits under new and delete. It shows up for the senior systems roles near the metal: drivers, compilers, performance work. Intel ships a scalable allocator of its own inside its threading library, and the people who work close to the hardware are expected to know what a heap allocator actually does with the bytes.

Watch how this round runs, because it is different from a web design loop. There is no capacity math and no box diagram of services. The interviewer wants data structures and pointer arithmetic, over a memory layout you can draw. Expect them to say "design it" and then, a few minutes in, "okay, write the header struct" or "sketch malloc for me." Expect that pivot from architecture into live code. You should be able to put the block layout on the board, then turn it into a C struct, then walk one allocation through it byte by byte.

The Intel angle

Asking you to build malloc is Intel checking whether you understand the machine or just rent it. A candidate who has only ever consumed allocators reaches for vague words: "it grabs some memory and gives it back." A candidate who has written low-level systems code reaches for headers, then alignment, then coalescing, without being prompted, and that fluency is the signal the round is built to find. Intel's own threading library ships a scalable allocator, so this is home turf for the interviewer, and they know the failure modes cold. If you have written an allocator, a pool, a slab cache in real code, say so early. It reframes the whole conversation from "can this person reason about memory" to "let us compare notes."

Functional requirements

The functional core is two calls, and their contract is unforgiving. malloc(size) returns a pointer to at least size usable bytes, or a null pointer if it cannot. free(ptr) returns a block that a previous malloc handed out. That is the whole surface, and its smallness is deceptive. The hard part is the invariant behind them. The region has to stay partitioned into blocks owned by exactly one caller or by nobody. No byte is ever double-booked, and no freed byte is ever lost.

Non-functional requirements

Judge an allocator on four promises, in this order. Correctness comes first and it is absolute. Hand the same bytes to two callers, or lose a freed block so it can never be reused, and nothing else matters. Alignment is the second, and it is also non-negotiable. On most hardware an unaligned access to a wider type is a crash or a silent slowdown. So a returned pointer has to be aligned for anything the caller might put there. Only after those two do the graded trade-offs begin. Fragmentation, how much of the region you waste on overhead and unusable gaps, is where most of the design conversation lives. Speed is the fourth: the two calls sit on a hot path in real programs, so a full heap scan per allocation is a non-starter.

Two of those four pull against each other, and naming that pull early is the senior move. You can drive fragmentation down by searching harder for the tightest possible fit and by keeping meticulous bookkeeping, but every extra byte of metadata and every extra step of search costs you speed. You can go fast by grabbing the first block that fits and keeping the bookkeeping thin, but that leaves the heap messier. The whole design is a set of choices along that line. Correctness and alignment are fixed; fragmentation and speed are the dials.

• Correctness: absolute. every live block is owned by exactly one caller; every freed block returns to the pool and stays findable. One double-booked byte is a corruption bug, not a performance regression, so this is never traded away.
• Alignment: also non-negotiable. returned pointers are aligned for any type the caller stores, 16 bytes on a typical 64-bit target. Miss it and a wide load faults or slows down, so the allocator over-allocates a little to guarantee it.
• Fragmentation: the main dial. the gap between what callers asked for and what the region actually holds. Split blocks to give back the extra, coalesce neighbors to rebuild big holes. This is where most of the round is spent.
• Speed: close to constant. malloc and free run on a hot path, so scanning every block per call is out. A free list, and later size classes, keep the common case near O(1) instead of O(number of blocks).

One number motivates everything below, so derive it now rather than asserting it. Say the header on each block is 8 bytes and a caller asks for 100 bytes. You round the request up to keep the next block aligned, then add the header, then carve out a block noticeably larger than 100. If instead a caller asks for 1 byte, the header and the minimum block size dwarf the request, and you have spent dozens of bytes to hand back one. That gap between requested and consumed is fragmentation made concrete, and the block layout is where you either keep it small or let it run away. So start there.

The set-up

Core structures

Name the three things the allocator is built from before drawing anything. There are only three, and the entire design is how they fit together in memory.

The interface

The public surface is exactly two functions, and writing them down pins the contract the rest of the design has to honor. Everything else, the header, the free list, splitting, coalescing, is machinery in service of making these two correct and fast.

// The entire public surface: two calls over one region of memory.
void *my_malloc(size_t size);   // return a pointer to at least `size` usable,
                                //   16-byte-aligned bytes, or NULL if none can be found
void  my_free(void *ptr);       // return the block that `ptr` points into to the pool;
                                //   `ptr` must be a pointer a previous my_malloc handed out

The two signatures hide an asymmetry worth flagging. my_malloc is handed a size and has to go find space. my_free is handed a bare pointer with no size and no context, and it still has to figure out how big that block is and where its neighbors are. That is the reason the header exists: given only the caller's pointer, free has to recover the block's size in constant time, and it does that by looking just behind the pointer.

How the region is laid out

Picture the whole region as one row of blocks laid end to end in address order. Each block starts with a header that records its size and whether it is in use, then the payload, then a footer that mirrors the header. Some blocks are handed out to callers; the rest are free, and the free ones are threaded onto the [[queue:free list]] so the allocator can find them fast. The diagram colors the [[storage:heap region]] markers green, the allocated blocks violet, the [[queue:free blocks]] amber, and the free list head blue. Two kinds of link run through it: the solid arrows follow address order, block to physically-next block, and the dotted arrow is the free list hopping from one free block to the next.

Walk one allocation through that picture. A request arrives. The caller calls my_malloc(100). First the allocator turns 100 into a real block size: round it up so the payload stays aligned, add the header and footer, and clamp it to the minimum block size. Call the result the block the request needs.

The free list is searched. Starting from the free list head, the allocator walks the [[queue:free blocks]] looking for one at least as big as the block the request needs. The first one that fits gets used. If none fits, the allocator grows the region at the [[storage:top of heap]] and carves the new space into a block.

The block is split and handed out. The block that fit is usually bigger than needed. The allocator carves off exactly what the request needs and leaves the remainder as a smaller free block, if it is large enough to stand on its own. It flips the chosen block's header to in-use, unlinks it from the free list, and returns a pointer to its payload, the byte just past the header.

The block comes back. Later the caller calls my_free on that same pointer. The allocator steps back from the pointer to the header, marks the block free, and then looks at its physical neighbors. If the block just before or just after is also free, it merges them into one larger block so the hole does not stay fragmented, and drops the result onto the free list. That merge step, coalescing, is what keeps the region from slowly shattering into gaps too small to reuse.

// The whole allocation path, as a sketch. Each helper is a deep dive below.
void *my_malloc(size_t size) {
    if (size == 0) return NULL;
    size_t need = round_up_block(size);      // align payload, add header + footer, clamp to MIN_BLOCK
    BlockHeader *block = find_fit(need);     // walk the free list for the first block that fits
    if (block == NULL)
        block = extend_heap(need);           // no fit: grow the region via sbrk / mmap
    free_list_remove(block);
    split(block, need);                      // carve off the remainder if it is big enough to be its own block
    mark_in_use(block);
    return payload(block);                   // hand back the pointer just past the header
}

That sketch is the skeleton, and each helper in it hides a real decision. round_up_block is where alignment and header overhead live. find_fit is the free list and the fit strategy. split and coalesce are the fragmentation fight. The deep dives take them one at a time, in the order the interviewer usually pushes.

The Intel angle

When Intel says "design a memory allocator," they mean "design it and then write it." A pure architecture answer, boxes and arrows with no code, underdelivers here in a way it would not at a product-SD shop. The interviewer expects the collapse into implementation, so pace yourself for it. Get the layout and the free list agreed out loud. Then be ready to turn the header into a struct, and malloc into the sketch above, the moment they ask. This ties straight into the coding rounds, where pointer arithmetic and manual memory management are the dominant archetype. The allocator is the same muscle, one level up.

Potential deep dives

The rest of the score is won here. An allocator round pushes on the same four corners almost every time. Block layout and alignment. How the free blocks are organized and searched. Splitting and coalescing to fight fragmentation. And how real production allocators go faster and scale to many threads. That last corner is where the conversation ends up. It leads into the concurrency lesson, so it gets the most room.

1) The block: headers, boundary tags, alignment

Everything rides on the shape of one block, so pin it down first. A block has three parts: a header, the payload, then a footer. The caller sees only the payload and holds a pointer to its first byte. The header and footer are the allocator's private bookkeeping, sitting just before and just after the payload in memory. The header has to answer two questions in constant time from nothing but the caller's pointer: how big is this block, and is it in use? Both fit in a single machine word.

The size is the interesting part. Because every block size is a multiple of 16, the low four bits of the size are always zero, and doing nothing with four known-zero bits is a waste. So pack a flag into the lowest bit: 1 means in-use, 0 means free. To read the size, mask those low bits off; to read the flag, mask everything else off. This is the kind of bit-level packing Intel interviewers love, because it is free, and because it shows you actually think about where the bits go.

// Every block, free or in use, starts with an 8-byte header.
// Block sizes are always a multiple of 16, so the size's low 4 bits are
// always zero. We steal the lowest bit to record in-use, at no cost.
struct BlockHeader {
    size_t size_and_flags;    // (block size) | (in_use ? 1 : 0)
};
static size_t block_size(BlockHeader *h) { return h->size_and_flags & ~(size_t)0xF; }
static bool   in_use(BlockHeader *h)     { return h->size_and_flags & 1; }
// The caller's pointer is the byte just past the header.
static void *payload(BlockHeader *h)          { return (char *)h + sizeof(BlockHeader); }
static BlockHeader *header_from(void *ptr)    { return (BlockHeader *)((char *)ptr - sizeof(BlockHeader)); }

Now the footer, which is where a subtle problem gets solved. On free, you want to merge with the block physically before you, but a block has no idea how big its predecessor is. Walking from the start of the heap to find out would make free O(number of blocks), which defeats the point. The fix is Knuth's boundary tag: put a copy of the header at the end of every block too. To find the previous block, step back 8 bytes from your own header and read its footer, which tells you the previous block's size, and subtract to land on its header. Constant time, both directions. The footer is the small tax that buys O(1) coalescing.

// A boundary tag: a copy of the header at the very end of the block.
// It lets a block find the block *before* it in O(1) during coalescing.
struct BlockFooter {
    size_t size_and_flags;    // mirrors this block's header
};
// Step back one word from my header to read the previous block's footer,
// then back by that block's size to land on the previous header.
static BlockHeader *prev_by_footer(BlockHeader *h) {
    BlockFooter *prev_foot = (BlockFooter *)((char *)h - sizeof(BlockFooter));
    return (BlockHeader *)((char *)h - (prev_foot->size_and_flags & ~(size_t)0xF));
}
static BlockHeader *next_by_address(BlockHeader *h) {
    return (BlockHeader *)((char *)h + block_size(h));
}

Alignment is the last piece, and it is a correctness requirement. The caller might store a pointer, a double, or a vector type in the payload. On most hardware a wide access to an unaligned address either faults or runs slow, so the returned pointer has to be aligned to the largest type that could go there. On a 64-bit target that is 16 bytes. The allocator guarantees it by keeping every payload on a 16-byte boundary, which means rounding each request up to a multiple of 16 before adding the header and footer.

Derive the cost by hand, because the interviewer will. Take the model above: an 8-byte header, an 8-byte footer, plus payloads aligned to 16. A caller asks for 100 bytes. Round 100 up to the next multiple of 16, which is 112. Add the 8-byte header and 8-byte footer and the block is 128 bytes. The caller wanted 100 and consumed 128, so 28 bytes, about 22 percent, went to overhead: 12 bytes to the alignment round-up and 16 to metadata. Now ask for 1 byte. Round 1 up to 16, add 16 of metadata, and you get a 32-byte block for a single requested byte, roughly 97 percent waste. Tiny allocations are murdered by fixed overhead, which is exactly why real allocators treat small sizes specially, a thread we pick up in the last deep dive.

The Intel angle

This deep dive is where the interviewer stops nodding and starts watching your hands. Pack the flag into the size's low bit, mask it back out, step a pointer back 8 bytes to reach a header from a payload. That is pointer arithmetic and bit manipulation, the two coding archetypes Intel leans on hardest, inside a design question. Get the alignment round-up right and be able to say why 16 and not 8. Draw the three parts as one labeled box and it stops being abstract. Fumbling the difference between the block size and the payload size, or forgetting that free only gets the payload pointer, is the tell that someone has read about allocators but never built one.

2) The free list: how you find a block that fits

Malloc's job reduces to one question: given a request, find a free block big enough. How you organize the free blocks decides how fast that answer comes and how much of the region you waste getting it. That is two costs at once. Walk it from the simplest organization to the one real allocators use, because that progression is exactly how the interviewer wants you to reason.

// While a block is free its payload is dead space, so the free-list
// pointers live inside the payload. Zero extra memory for the index.
struct FreeBlock {
    BlockHeader header;      // size + free bit, same as any block
    FreeBlock  *next;        // next free block in the list
    FreeBlock  *prev;        // previous free block
    // ...the rest of the payload is unused while free...
};
// This is why the minimum block size is 32 bytes on a 64-bit target:
// 8 (header) + 8 (next) + 8 (prev) + 8 (footer) must fit in the smallest block.
#define MIN_BLOCK 32
// First fit: return the first free block large enough, else grow the heap.
BlockHeader *find_fit(size_t need) {
    for (FreeBlock *b = free_head; b != NULL; b = b->next)
        if (block_size(&b->header) >= need)
            return &b->header;
    return NULL;
}

Once you have an explicit list, the fit policy is the remaining knob, and it is a genuine trade rather than a right answer. The three classic strategies each buy something and cost something.

• First fit takes the first block on the list that is large enough. It is the fastest to search because it stops early, and in practice it fragments surprisingly little, because it tends to leave the larger blocks near the end alone. It is the pragmatic default, and the sketch above uses it.
• Next fit is first fit with a roving pointer: instead of restarting at the head each time, resume the search where the last one stopped. It spreads allocations more evenly across the heap, which sounds good but usually fragments worse than first fit, because it chews through the big blocks near the front instead of leaving them intact.
• Best fit scans the whole list and takes the smallest block that still fits, leaving the tightest remainder. It wastes the least per allocation, but it pays two prices. The search is a full walk every time. And the tiny leftovers it creates are often too small for anything, so the heap fills with unusable slivers. Segregating the list by size, in the last deep dive, is how real allocators get best-fit quality without the full scan.

3) Splitting and coalescing: the fragmentation fight

A free list finds a block, but a found block is rarely the exact size requested, and blocks come back in a different order than they went out. Left alone, both facts shred the heap. Oversized blocks get handed out whole and their extra space is wasted. Freed blocks pile up as separate small holes even when they sit right next to each other. Splitting fixes the first, coalescing the second. Together they are how the allocator keeps big blocks available over a long-running process.

Take splitting first. First fit returns a 256-byte free block to satisfy a request that needs a 128-byte block. Handing over all 256 wastes 128 bytes to internal overhead. Instead, carve the block in two: a 128-byte block for the request, and a 128-byte remainder that goes back on the free list as its own block. The one rule to respect is the minimum block size. If the free block had been 144 bytes, splitting off 128 would leave a 16-byte scrap, below the 32-byte minimum, too small to hold its own header, footer, plus its free-list pointers. In that case you do not split. Hand over the whole 144 and accept 16 bytes of internal fragmentation, because a valid 144-byte block beats a valid 128-byte block plus an invalid 16-byte one.

// Carve the request off the front of an oversized block, leaving the
// remainder as its own free block, but only if that remainder is a legal block.
void split(BlockHeader *block, size_t need) {
    size_t extra = block_size(block) - need;
    if (extra < MIN_BLOCK) return;          // remainder too small: hand over the whole block
    set_size(block, need, /*in_use=*/true); // shrink this block to exactly what was needed
    BlockHeader *rest = next_by_address(block);
    set_size(rest, extra, /*in_use=*/false);
    free_list_insert(rest);                 // the leftover rejoins the pool
}

Coalescing is the mirror image, and it is what boundary tags were for. When a block is freed, look at the block physically before it (reached in O(1) through the predecessor's footer) and the block physically after it (reached by jumping forward by this block's size). If either neighbor is also free, merge it into the block being freed, unlinking it from the free list and summing the sizes. There are four cases, depending on which neighbors are free, and each is a small splice.

void my_free(void *ptr) {
    if (ptr == NULL) return;
    BlockHeader *block = header_from(ptr);   // step back 8 bytes to the header
    mark_free(block);
    coalesce(block);                         // merge with free neighbors, then re-list
}
// Merge with the free block before and the free block after, so two (or three)
// small holes fuse into one big one. Boundary tags make "the block before me" O(1).
void coalesce(BlockHeader *block) {
    BlockHeader *prev = prev_by_footer(block);
    BlockHeader *next = next_by_address(block);
    if (!in_use(prev)) { free_list_remove(prev); block = merge(prev, block); }
    if (!in_use(next)) { free_list_remove(next); block = merge(block, next); }
    free_list_insert(block);
}

See why coalescing matters with numbers. Suppose three 64-byte blocks sit next to each other in the region, and all three end up free. Without coalescing, the free list records three separate 64-byte blocks. A later request that needs a 128-byte block fails: there are 192 free bytes right there, but no single hole is bigger than 64. With coalescing, freeing the middle block fuses all three into one 192-byte block, and the 128-byte request sails through. Same freed memory, opposite outcome. Coalescing is the difference between a heap that stays usable and one that dissolves into gravel.

4) Fragmentation and how real allocators win

Name the two kinds of fragmentation precisely, because the interviewer will want the distinction, and they are fought with different tools. Internal fragmentation is memory inside a block that the caller was given but cannot use: the rounding-up and the header and footer. From the layout deep dive, a 100-byte request landing in a 128-byte block carries 28 bytes of internal fragmentation. External fragmentation is free memory that exists but is split into pieces each too small for the request. Think of the three 64-byte holes that cannot serve a 128-byte allocation despite 192 free bytes. Splitting and headers govern the first; coalescing and placement govern the second.

The single explicit free list you have built is correct and reasonable, but real allocators go faster and waste less, and the central idea is size classes. Instead of one list of every free block, keep many lists, one per size class: a list of 16-byte blocks, a list of 32-byte blocks, and so on, coarsening into ranges as sizes grow. This is a segregated free list. To allocate, round the request up to its class and pop the head of that class's list, which is O(1) and needs no search at all. Same-size objects cluster together, so external fragmentation drops, and the tiny-sliver problem that best-fit created disappears because you never hunt for a tight fit; the class is the fit.

Size classes trade a little internal fragmentation for a lot of speed and less external fragmentation, and that trade is almost always worth it. Rounding a 100-byte request up to a 112-byte class wastes 12 bytes. In return the allocation is a constant-time pop instead of a list walk, and the heap stays tidy because objects of the same size pack cleanly. Very large allocations skip the classes entirely and get their own region straight from the OS via mmap, so one giant request does not distort the small-block machinery. This is roughly how the well-known production allocators are built.

• dlmalloc, Doug Lea's allocator, is the classic general-purpose design and the ancestor of the one in glibc. It uses boundary tags and binned free lists, essentially the segregated-list idea, and is the reference most others are measured against.
• tcmalloc, from Google, is thread-caching malloc. It gives each thread a local cache of small blocks backed by central per-size-class lists, so the common allocation touches only thread-local memory and takes no lock at all. Built for many-threaded servers.
• jemalloc, from the FreeBSD world and widely used in industry, shards the heap into multiple arenas and leans hard on size classes, tuned specifically to keep fragmentation low under heavy concurrency.
• The buddy allocator splits memory into a Premium question blocks and finds a freed block's neighbor by flipping a single address bit, which makes coalescing extremely cheap. The Linux kernel's page allocator uses it. The cost is rounding every request up to a Premium question, so internal fragmentation can approach 2x.

The last idea is the one that leads straight into the next lesson: per-thread arenas. A single global free list means every thread that allocates or frees has to take one lock, and under many threads that lock becomes the bottleneck the whole program waits on. The fix is to stop sharing. In tcmalloc, each thread gets its own cache of small blocks, so most allocations never touch shared state. In jemalloc, the heap splits into several arenas so different threads mostly hit different locks. Contention drops because threads stop stepping on each other. Making a data structure correct and fast under many threads is its own deep subject, and that is where the concurrency round goes.

The Intel angle

The concurrency turn is where Intel is really steering, so get there before you are pushed. Intel builds threading tools, and its own scalable allocator exists to solve the many-threaded case. So an interviewer will almost always follow "design an allocator" with "now make it thread-safe" or "now a hundred threads are allocating at once." Volunteer the shape of the answer. A single global lock on the free list serializes every allocation. Per-thread caches or sharded arenas fix it, so the common path takes no shared lock. You do not have to build the lock-free version on the spot. Naming per-thread arenas as the answer, and knowing why they beat one big lock, is what carries you into the thread-safe structures round that comes next.

What is expected at each level

This design has real depth, and your level sets how far down it you go before anyone asks. The three rungs climb the same axis: a mid-level engineer builds a correct allocator, a senior owns the fragmentation fight, and staff carries the real-allocator and concurrency picture.

Mid-level engineer

Reach one correct, working allocator and be able to code its core. Lay the region out as blocks with a header carrying size and an in-use bit. Thread an explicit free list through the free blocks and use first fit. Split an oversized block on malloc, and return an aligned pointer to the payload. Because this interviewer drops into code, be ready to write the header struct and the malloc sketch, and to explain why the caller's pointer sits just past the header. Coalescing on free is the piece most likely to need a nudge at this level; getting there with a hint still clears the rung. The bar is a malloc and free that are correct and aligned, and never obviously O(n) per call.

Senior engineer

Own fragmentation without being led there. Raise internal versus external fragmentation yourself, with a worked number for each, and explain why coalescing plus boundary tags is what keeps large requests serviceable over a long run. Defend the fit strategy you chose, first fit versus best fit, as a deliberate trade rather than a default, and derive the alignment and header overhead by hand. You should surface the boundary-tag trick for O(1) coalescing and the minimum-block-size constraint on your own. Clearing this rung means an allocator whose fragmentation behavior you can reason about quantitatively.

Staff and beyond

Carry the production picture end to end. Move from the single explicit list to segregated free lists and size classes, and explain the speed-for-a-little-internal-fragmentation trade they make. Name how the real allocators are built, thread caches in tcmalloc, arenas in jemalloc, boundary-tagged bins in dlmalloc, the buddy system in the kernel, and know what each optimizes. Then raise the concurrency turn without prompting. A global lock on the free list is the scaling wall, and per-thread caches or sharded arenas clear it. The lock-free and memory-ordering details follow from there. The bar here is juggling block layout, free-list organization, the fragmentation fight, and thread scalability all at once, four independent dials, while correctness and alignment stay pinned and only the rest moves.