Commentary: malloc-arena

A 256-byte arena with four 56-byte allocations in it. Free all four, so that every byte in the arena is free, then ask for 96 — and watch it fail. Whether it fails depends on the order you freed in, and on one direction a pointer cannot go. A study guide for arena.py.

cd malloc-arena
python3 demo.py           # the aha (§6), about a second
python3 test_arena.py     # pins every number this page claims
python3 demo.py --census  # adds §7.4's 986,580-trace sweep, ~75 seconds

1. Orientation

This toy is an allocator: one fixed bytearray, an 8-byte header in front of every block, splitting on malloc and merging on free. It has policy knobs for the fit rule, for who gets merged and when, for the splitting threshold, and for boundary tags — and the whole page is about which of those knobs is load-bearing.

The shortest version of the result, in five lines of Python:

from arena import Arena
a = Arena(256)                        # 256 bytes, all free
p = [a.malloc(56) for _ in range(4)]  # 4 x (56 + 8) = 256: exactly full
for i in (0, 1, 2, 3):                # give every single byte back
    a.free(p[i])
a.malloc(96)                          # OutOfMemory: no block for 96 bytes

Nothing is allocated. a.stats()["free_bytes"] is 256. The request is 96. It raises.

By the end you should be able to:

• lay out a heap as headers and payloads in one flat array, and find any block's neighbours by arithmetic rather than by a pointer;
• say why an allocator can walk forward over the heap for free and cannot walk backward at all, and what that costs;
• predict which free orders leave an arena usable and which leave it in pieces — and know that exactly one of the 24 orders here is fatal, and that it is the one a for loop produces;
• explain why the fit policy (first / best / worst) is the wrong knob for this failure and the right knob for a different one;
• read glibc's PREV_INUSE bit and know from experience what goes wrong without it, because the toy shows you the crash.

2. The problem this mechanism exists to solve

malloc(n) has to hand back n bytes that are contiguous and that nobody else is using. That one word, contiguous, is the whole difficulty. A filesystem can scatter a file across any free blocks it likes and fix it up with an index; an allocator hands out a raw pointer, so the bytes have to be next to each other and stay where they are for as long as the caller holds that pointer.

So the allocator's real job is not bookkeeping, it is keeping large runs of free bytes in existence. Everything in the design is in tension about how:

• Splitting is necessary and it is how you lose. A 256-byte free block serving a 56-byte request has to be cut, or you waste 200 bytes. Every cut makes two smaller things out of one bigger thing, permanently, unless something puts them back.
• Merging is the only repair, and it is only ever local. When a block is freed, the allocator knows about that block. Whether its neighbours are free is a question about this instant, not about the future — and a block freed a microsecond later doesn't get a second chance to merge with it.
• Metadata competes with payload. Every byte spent on a header, a footer or a pointer is a byte the caller can't have. This toy spends 8 bytes a block, and §6.6 shows what a 4-byte footer costs on the same trace.
• Free has to be fast. free() is called as often as malloc, usually in a hurry, and it has no idea what the program is going to ask for next. Every check it performs is paid on every deallocation forever.

OSTEP's chapter on free-space management puts the failure this creates in one sentence: "Although all of the memory is free, it is chopped up into pieces, thus appearing as a fragmented memory despite not being one." This toy is 214 lines built to produce exactly that sentence, on purpose, from a free order you would never suspect.

3. Background you need

The two that carry the result are coalescing and the direction problem behind boundary tags. Everything else on this page is the setting. If you take one idea away, take this one: coalescing is an operation on a moment, not on a set. The set of blocks freed is identical in every run below; only the moments differ.

4. The mental model

A block is a header plus its payload, and the next block starts immediately after it. That is the entire data structure — there is no free list, no tree and no side table:

Two sentences to carry away. Merging happens at free time, and only with neighbours that are already free at that instant. And a heap you can only walk forward is a heap you can only merge forward, which turns "free your objects in the order you created them" — the most natural loop in programming — into the one order that merges nothing.

5. Reading the source

214 lines, one class. Read it in this order.

5.1 The header, and why blocks() is the whole navigation system

    def blocks(self):
        """Every block, front to back. `off + total` is the next header --
        the only navigation an 8-byte header can offer."""
        off = 0
        while off < self.size:
            total, flags = self._hdr(off)
            yield off, total, bool(flags & FREE)
            off += total

off += total is the toy's only pointer arithmetic and its only structural claim: the heap is a sequence of blocks with no gaps, so the byte after a block is the next block's header. Everything else — the free list, the fit search, coalescing — is written on top of this one generator.

Notice what the generator cannot do: it cannot start in the middle, and it cannot go backwards. Given an offset you cannot find the previous block without starting again from zero. That asymmetry is not an artifact of Python; it is what an 8-byte header is, and §5.4 is the whole toy paying for it.

5.2 malloc — the split, and the remainder that isn't worth having

    def malloc(self, nbytes):
        need = nbytes + self.overhead
        off = self._find(need)
        if off is None and self.consolidate_on_fail:
            self.consolidate()
            off = self._find(need)
        if off is None:
            raise OutOfMemory("no block for %d bytes" % nbytes)
        total, _ = self._hdr(off)
        rest = total - need
        if rest >= self.overhead + self.split_min:
            # Split. The remainder is written FIRST: marking the allocated
            # block clears the remainder's PREV_FREE, which is only correct
            # if the remainder's header already exists.
            self._mark(off + need, rest, True, prev_free=False)
            self._mark(off, need, False)
        else:
            # Too small to be a block of its own: the request keeps the
            # slack. Internal fragmentation, deliberately.
            self._mark(off, total, False)
        return off + HEADER

Three decisions in twenty lines.

need = nbytes + self.overhead is where the header stops being free. Ask for 96 and you are really asking for 104 contiguous bytes, and §6.1's whole result is the gap between those two numbers and 64.

rest >= self.overhead + self.split_min is the splitting threshold. With split_min = 0 it still refuses to split off a remainder that couldn't hold a header, because such a remainder would be a block with nowhere to write its own size — not a policy, an impossibility. Everything above that floor is policy, and §7.5 measures it: on this toy's trace family, raising the threshold never helps and eventually costs 114,840 traces.

return off + HEADER is the toy's model of a pointer. Real malloc returns an address; this returns an integer offset into self.mem, and free subtracts the same 8 to get back to the header. That subtraction is why a real free(p) needs no search to find the block metadata, and why writing one byte before a returned pointer corrupts the heap rather than a value.

5.3 free — the forward merge, which is the cheap direction

    def free(self, ptr):
        off = ptr - HEADER
        total, _ = self._hdr(off)
        self._mark(off, total, True)
        if self.coalesce == "none":
            return
        nxt = off + total                      # forward: one addition
        if nxt < self.size:
            ntotal, nflags = self._hdr(nxt)
            if nflags & FREE:
                total += ntotal
                self._mark(off, total, True)
        if self.coalesce == "both":
            prev = self._prev(off)             # backward: the hard direction
            if prev is not None:
                ptotal, _ = self._hdr(prev)
                self._mark(prev, ptotal + total, True)

This is the load-bearing function, and the load-bearing part of it is the if nflags & FREE in the forward branch. That condition is a question about right now: is my successor free at this instant? If it is, the two become one block. If it isn't, nothing is recorded — no "merge me later" note, no pending list — and when the successor is freed a moment later it asks the same question about its successor and never looks back at us.

That is why the default coalesce="forward" is not a strawman. It is what you get from the data structure above, and it is enough to keep an arena healthy under the free orders most code produces. It is defeated by exactly one thing: freeing in ascending address order, where the answer to is my successor free? is no, every time, by construction.

The counterfactual is in §6.2 and it is unusually clean: replace the whole forward branch with nothing (coalesce="none") and the resulting 256-byte arena is byte-identical. On the trace that fails, the coalescing code runs four times and changes nothing.

5.4 _prev — the direction that costs, in two currencies

    def _prev(self, off):
        """The physically previous block, if it is free. A header-only heap
        cannot answer this in less than a walk from byte 0; a footer answers
        it in one read, but ONLY if PREV_FREE says those 4 bytes are a
        footer and not the tail of somebody's payload.
        """
        if off == 0:
            return None
        if self.boundary_tags:
            if not self._hdr(off)[1] & PREV_FREE:
                return None
            ptotal, = struct.unpack_from("<I", self.mem, off - FOOTER)
            return off - ptotal
        prev = None
        for o, total, free in self.blocks():
            if o == off:
                return prev
            prev = o if free else None
        return None

Two implementations of one question, and they cost in different currencies.

The heap walk (the last five lines) costs time: it re-derives the whole block sequence from byte 0 to find out what is immediately behind off. It costs no memory at all, which is why it is the toy's default answer to "coalesce backwards too".

The footer costs memory: 4 bytes per block, reserved whether or not the block is ever freed, in exchange for one subtraction. §6.6 prices both, and the shapes are exact — n²/2 + 9n/2 − 3 header reads for the walk against 6n − 4 for the footer.

The line to stare at is prev = o if free else None. It is not an optimisation; it is the definition of adjacency. Drop the else None and _prev returns the nearest earlier free block instead of the adjacent one — which sounds almost the same and is memory corruption. §7.1 has the run: a live 56-byte allocation ends up inside a free block, gets handed to a second caller, and both of them write to it.

The if not self._hdr(off)[1] & PREV_FREE: return None guard is the same idea in the footer world, and it is the one glibc spells PREV_INUSE. Its comment in malloc.c is worth having in front of you when you read §6.6: "If prev_inuse is set for any given chunk, then you CANNOT determine the size of the previous chunk, and might even get a memory addressing fault when trying to do so."

5.5 consolidate — the same repair, paid later

    def consolidate(self):
        """Deferred coalescing: one forward sweep merging every run of free
        blocks. Needs no footer, and no free order can defeat it -- but it
        costs a full heap walk, so it is paid on failure, not on every free.
        """
        off = 0
        while off < self.size:
            total, flags = self._hdr(off)
            if flags & FREE:
                nxt = off + total
                while nxt < self.size:
                    ntotal, nflags = self._hdr(nxt)
                    if not nflags & FREE:
                        break
                    total += ntotal
                    nxt += ntotal
                self._mark(off, total, True)
            off += total

This is the third answer, and the interesting one: it only ever walks forward, like free does, but because it walks the whole heap at once it sees runs of free blocks rather than one neighbour. Order cannot defeat it, because by the time it runs there is no order left — just a snapshot.

malloc calls it (line 112) only when a request has already failed, which is the trade: nothing is paid on the fast path, and the arena is allowed to sit in the fragmented state indefinitely as long as nobody asks for anything large. That is precisely the bargain glibc struck with fastbins for two decades, and §8 has what happened to it.

6. The demo, and what it proves

python3 demo.py. Sections A–G below are its real output, in order.

6.1 The headline

The arithmetic, so that no number here is unexplained:

• Each allocation is 56 payload + 8 header = 64 bytes, and 4 × 64 = 256, so the four allocations fill the arena exactly with nothing left over.
• Freeing all four returns 256 of 256 bytes — 100%, with no live allocation anywhere in the arena. Both runs agree on this.
• Ascending order merges nothing (§6.2), so the largest free block is 64 bytes, holding a payload of 64 − 8 = 56.
• malloc(96) asks for 96 + 8 = 104 contiguous bytes. 104 > 64, so _find returns None for all four blocks and the request raises.
• Descending order merges every time, so the arena is one block of 256, payload 248, and 104 ≤ 256 fits with 152 bytes to spare.

The two runs differ in nothing except the order of four free calls. The allocations are the same, the sizes are the same, the set of freed blocks is the same, and the total free bytes are the same.

6.2 The counterfactual: the coalescing code is inert on the failing trace

coalesce="none" returns from free before the merge branch ever runs (line 152). coalesce="forward" runs it four times. The two 256-byte bytearrays compare equal — not equivalent, equal, headers and flags and all.

This is what "merging is local" means, made checkable: an allocator with coalescing and an allocator without it are the same allocator under an ascending free order. Whatever fixes this failure, it cannot be a better merge at free time; it has to be a merge that looks somewhere else (§6.5).

6.3 One of 24 — and it is the one your for loop writes

The rule behind the whole table is one line of arithmetic. A request of n bytes needs n + 8 contiguous bytes, and the only runs available are multiples of 64, so it needs a run of k = ⌈(n + 8) / 64⌉ blocks.

• n = 96 → 104 → k = 2. Only the fully ascending order contains no run of 2, so 1 of 24 fails. Every other permutation frees some block after its predecessor at least once, and one merge is enough.
• n = 121 → 129 → k = 3. Seven orders produce a run of 3 or more, so 17 of 24 fail. The seven are (0,3,2,1) (2,1,0,3) (2,1,3,0) (2,3,1,0) (3,0,2,1) (3,2,0,1) (3,2,1,0).
• n = 200 → 208 → k = 4, which needs the whole arena, and only (3,2,1,0) produces it: 23 of 24 fail.
• n = 56 → 64 → k = 1, so nothing can fail: 0 of 24.

So the failing case at 96 bytes is a knife edge — and the edge is exactly where real code stands. The order (0, 1, 2, 3) is what you get from for p in allocated: free(p), from draining a queue front to back, from tearing down a linked list you built by appending, and from any pool released in creation order. It is not an unlucky permutation; it is the default one.

Widen the arena and the knife edge becomes a plateau — six 32-byte allocations in 240 bytes, all 720 orders:

Same arithmetic: blocks are 40 bytes here, so a 96-byte request needs ⌈104/40⌉ = 3 in a row, and 48.5% of all possible free orders cannot provide it.

6.4 The knob everyone argues about does nothing here

First fit, best fit and worst fit are three answers to which of the fitting blocks to use. In the failing arena, the set of fitting blocks is empty — _find skips every block on total < need (line 135) before the policy is ever consulted. Three policies, one empty set, one answer.

The second half of the transcript is the control that makes this a finding rather than a tautology: given three holes of 64, 32 and 128 bytes, the same malloc(24) lands in a different one under each policy, splitting the 64-byte hole, exactly filling the 32-byte one, or carving the 128-byte one. The knob works. It is just not connected to this failure. §7.4 measures how much it is connected to any failure.

6.5 What does fix it, and what each fix costs

The cost unit is header reads — every _hdr call, counted by the toy itself (self.reads, line 75). It is deterministic, which wall-clock time would not be, and it is the operation a real allocator pays for in cache misses.

Three fixes, three shapes:

• Merge backwards as well (23 reads at free time, up from 11). Pays on every free, forever, whether or not fragmentation was ever going to matter. That is 12 extra reads to fix an arena that four different requests would not have noticed.
• Merge backwards with a footer (25 reads). More reads than the heap walk at n = 4, because maintaining PREV_FREE costs a read per write and the walk over four blocks is short. §6.6 is where this inverts.
• Defer everything (8 reads at free time — the cheapest of all, since free returns before the merge branch — and 12 on the failing malloc). The fragmented arena is repaired at the exact moment somebody needs it repaired, and never otherwise.

Nothing here is free, and none of the three dominates. That is the design space, in four rows.

6.6 Boundary tags: the price, the payoff, and the crash

Both columns have exact closed forms, checked against all five rows in test_arena.py: the heap walk costs n²/2 + 9n/2 − 3 header reads and the footer costs 6n − 4. At n = 4 the footer wins by 13%; at n = 64 it wins by 6.1×, and the gap grows without limit. This is the entire argument for boundary tags, and it is why Knuth's trick survived into every serious allocator: free must not be O(heap).

The price is paid in bytes, on the toy's own trace:

4 × (56 + 12) = 272 > 256. The fourth allocation has 256 − 3 × 68 = 52 bytes left, which holds a payload of 52 − 12 = 40, and 56 > 40. The fix that guarantees the arena can always be defragmented is the fix that costs you an allocation.

And then the trap. Write the footer as the obvious thing — the 4 bytes below a header are the previous block's size, so read them — and the demo's NaiveFooter subclass shows what happens on the very first free:

Read the failure carefully, because it is the reason a bit exists in every production allocator. Sixteen 32-byte blocks fill a 512-byte arena; the last one starts at offset 480. Freeing it newest-first means the block below it is still allocated, so the 4 bytes at 476 are not a footer at all — they are the tail of somebody's payload, here all zeros. ptotal = 0, so prev = 480 − 0 = 480, so the block's predecessor is itself. It merges with itself into a 64-byte block whose footer would live at 480 + 64 − 4 = 540, in a 512-byte arena, and Python refuses.

A footer is only meaningful if the block below is free, and nothing about the footer itself can tell you whether it is. That is exactly what glibc's PREV_INUSE bit is for, and its comment reads like a description of this crash: "If that bit is clear, then the word before the current chunk size contains the previous chunk size, and can be used to find the front of the previous chunk... If prev_inuse is set for any given chunk, then you CANNOT determine the size of the previous chunk, and might even get a memory addressing fault when trying to do so."

In C there is no struct.error. The bad merge succeeds silently, the allocator hands out a block that overlaps live data, and the program crashes somewhere else entirely, later. This toy's arena is a bytearray with bounds checking, which is the only reason the bug announces itself.

6.7 The boundary condition — where the effect vanishes

The very same fragmented arena that cannot serve one 96-byte request serves four 56-byte requests without a complaint. Nothing was merged; nothing needed to be.

That is the boundary, and it is sharp: if every allocation is the same size, coalescing is unnecessary and free order is irrelevant, because any free block satisfies any request. A reader can place their own system by asking four questions:

1. Are the sizes uniform? A slab allocator, an object pool, a fixed-size page allocator, a Vec<T> arena — none of them can produce this failure, which is why they exist. This is the single biggest reason the bug is rare in practice even though it is trivial to construct.
2. Does anything ever free in bulk? A region/arena allocator that frees everything at once by resetting one pointer has no free order at all. Same immunity, different route.
3. Can the allocator move things? A compacting garbage collector fixes fragmentation by relocating live objects — the one option a C allocator cannot take, because it handed out raw pointers and cannot find them again.
4. Is the heap allowed to grow? This arena is fixed. A real malloc under pressure calls sbrk or mmap for more, which hides fragmentation as address-space growth rather than as a failed request — and the process RSS keeps rising while free() is called correctly. Fragmentation on a growable heap does not look like OutOfMemory; it looks like a leak.

Where the boundary is not. Freeing "enough" memory is not a defence: §7.3 shows the same failure with a live block still in the arena, and the 100% figure is not a threshold — it is a rhetorical extreme. The failure begins long before the arena is fully free.

7. Design decisions and roads not taken

7.1 Adjacent, not nearest — the one-word change that corrupts the heap

_prev ends with prev = o if free else None, which resets the candidate every time a used block goes by. Drop the reset — keep the last free block seen, adjacent or not — and the code still runs, still merges, and still looks right. Here it is against the demo's own trace:

Block 1 was never freed. After free(2) it is inside a 128-byte free block, because block 0 was "the previous free block" and the merge added block 2's size to it. The next malloc(120) is handed offset 8, writes 120 bytes, and walks straight through block 1's payload at offset 72 — two live pointers to the same bytes, with no error anywhere.

This is the strongest argument in the toy for why coalescing is written the awkward way it is. The merge is not "join the free blocks"; it is "join the blocks that are physically touching", and physical adjacency is the only thing that makes the arithmetic in blocks() stay true.

7.2 A heap walk instead of a free list

Every textbook allocator threads a linked list through the free blocks: the payload of a free block is unused, so the first two words can hold next and prev pointers for nothing. This toy doesn't, and _find walks all blocks including allocated ones.

It loses real performance — a free list visits only free blocks, and glibc's 128 bins mean it usually visits about one. It was rejected anyway, because a free list introduces a second structure that must agree with the headers, and the whole point of this toy is what the headers alone can and cannot express. Introducing a list would also quietly answer the toy's central question: a doubly-linked, address-ordered free list can be walked backwards, and the reader would learn nothing about why PREV_INUSE exists. OSTEP makes the same observation from the other side: "by keeping the list ordered by the address of the free space, coalescing becomes easier, and fragmentation tends to be reduced."

7.3 Why the headline uses a 100%-free arena, when it doesn't have to

100% free is theatre, and the honest version is milder: the failure needs fragmentation, not emptiness. Freeing only three of the four blocks fails identically:

The extreme was chosen because it kills the reflex the failure normally triggers. "Out of memory with 192 of 256 bytes free" invites you should free more or you need a bigger arena, and both are wrong. At 256 of 256, there is nothing left to free and no amount of extra arena would have helped — which is the only version of the demo that forces the reader to look at the free list instead of the free total.

7.4 Fit policy: the argument is real, the effect is small, the direction is settled

The census (python3 demo.py --census, about 75 seconds) plays 986,580 distinct traces — four allocations drawn from nine sizes, two of them freed, then two more requests — under each policy, with backward coalescing on so that the fit policy is the only variable:

Best fit wins, first fit is 2.28 points behind it, worst fit is 5.18 points behind best — and worst fit is the only policy that is ever the sole loser (28,579 traces where the other two both cope). The ordering matches the literature Doug Lea cites: "best-fit schemes (of various kinds and approximations) tend to produce the least fragmentation on real loads compared to other general approaches such as first-fit."

Two things worth taking from it. First, the effect is real but small — a couple of points — which is why production allocators spend their complexity budget on size-class bins rather than on fit refinement. Second, and this is the point of putting the census next to §6.4: the policy only ever changes which request fails, never whether the arena can be repaired. Not one of the 986,580 traces is rescued from a fragmented arena by a fit policy, because fit policies do not create contiguity. Only merging does.

7.5 The splitting threshold, which is a knob that only loses here

The idea behind a splitting threshold is that a tiny remainder is a liability: it is too small to satisfy anything, and it still costs a header. Refusing to create it — handing the slack to the requester instead — trades external fragmentation for internal.

On this trace family it never pays: 0, 8 and 16 are indistinguishable, 32 costs 6,107 traces and 64 costs 114,840. The reason is that the arena is small and the sizes are large relative to it, so the "wasted" remainder is usually big enough to serve the next request outright. Real allocators still enforce a floor (glibc's MINSIZE), but for the reason in §5.2 rather than this one: a block below the floor has nowhere to keep its own metadata. The knob is kept in the toy because a knob that measurably does nothing is worth knowing about — it is one of the two knobs a reader would have guessed was the fix.

7.6 No size classes, no bins, no mmap

Real allocators put free blocks in bins by size so _find is a lookup rather than a scan, and hand large requests directly to mmap so they never touch the heap at all. Both were left out for the same reason: they are about making allocation fast, and this toy is about whether allocation is possible. Bins would make _find O(1)-ish without changing a single byte of §6.1's failing arena — the same four 64-byte blocks would simply be found faster.

8. What's simplified vs. the real thing

9. Check yourself

Answer before expanding. Each answer is derivable from the source, and each was verified by running it and pinned in test_arena.py.

10. Further reading

Every link below was fetched and confirmed live when this was written (2026-07-31).

• OSTEP, chapter 17: Free-Space Management — the free chapter to read first, and the source of this page's opening quote: "Although all of the memory is free, it is chopped up into pieces, thus appearing as a fragmented memory despite not being one." Splitting, coalescing, headers and the three fit policies, in twenty pages.
• Doug Lea, A Memory Allocator — dlmalloc's design notes by its author, and the ancestor of glibc's allocator. Boundary tags in one sentence ("Chunks of memory carry around with them size information fields both before and after the chunk"), deferred coalescing, and the best-fit-versus-first-fit evidence §7.4 reproduces.
• glibc malloc/malloc.c — the real thing, readable. The chunk diagram and the PREV_INUSE paragraph near the top are §5.4 and §6.6; /* Consolidate backward. */ in _int_free_chunk is this toy's _prev with a corruption check bolted on; __libc_free's tcache_put fast path is §5.5's deferred coalescing in production. (GitHub mirror of the sourceware repository, which serves bots an interstitial.)
• mallopt(3) — the tunables, including M_MXFAST: "Fastbins are storage areas that hold deallocated blocks of memory of the same size without merging adjacent free blocks." Read it next to §8's note that the source has since removed them — a man page and an implementation disagreeing is worth seeing once.
• malloc(3) — sbrk versus mmap and the 128 kB MMAP_THRESHOLD; the answer to "why doesn't my program get OutOfMemory like the toy does".
• Fragmentation (computing) — the vocabulary, and this toy's headline at scale: "if a computer has 4 GiB of memory and 2 GiB are free, but the memory is fragmented in an alternating sequence of 1 MiB used, 1 MiB free, then a request for 1 contiguous GiB of memory cannot be satisfied even though 2 GiB total are free."
• Wilson, Johnstone, Neely & Boles, Dynamic Storage Allocation: A Survey and Critical Review — the 78-page survey behind every claim anyone makes about fit policies, and the one that established that synthetic random traces (like §7.4's) systematically mislead compared to real program behaviour. Read it if you want to know how much to trust that census.