Why this matters: the whole problem reduces to one design question — when aligned_free receives a bare pointer, where does the information it needs live? Answer that cleanly and the code is ten lines. Answer it with a lookup table and you've quietly rebuilt a worse problem. This lesson makes the choice, states the invariants, and buries the alternatives properly.

The shape of the trick

malloc gives you an address you don't control, aligned only to 8. The caller wants an address aligned to, say, 64. You cannot move what malloc returned — but you can return a different address inside the block malloc gave you. So:

1. Over-allocate. Ask malloc for more than the caller wants — enough extra that somewhere inside the block there is guaranteed to be a properly aligned address with room for the payload after it, and room for a little bookkeeping before it.
2. Round up. Compute the first address past the bookkeeping point that satisfies the alignment.
3. Stash. Immediately below the address you hand out, store the original pointer malloc returned.

aligned_free then does the only thing it can: step back one pointer-width from the address it was given, read the stashed original, and pass that to free. The forcing requirement is satisfied because the information travels with the allocation itself — the aligned pointer is the key to its own bookkeeping.

How much to over-allocate

The budget must cover the worst case, and stating it precisely is part of the answer:

request = size + alignment - 1 + sizeof(void*)

alignment - 1     worst-case distance from an arbitrary address
                  to the next aligned one
sizeof(void*)     the stash slot for the original pointer

Two subtleties earn interview credit. First, the stash must sit below the aligned address, so the round-up has to start from raw + sizeof(void*) — the first byte that leaves room for the slot — not from raw itself. Second, alignment is a power of two at least 8, and sizeof(void*) is 8, so the stash slot itself always lands on a properly aligned, safely readable address. Say both; they're the difference between the idea and the design.

The invariants

- the returned pointer P satisfies P % alignment == 0
- the original malloc pointer is stored at P - sizeof(void*), always
- original <= P - sizeof(void*), and P + size fits inside the
  malloc'd block (the over-allocation guarantees both)
- aligned_free(P) frees exactly the block malloc returned — nothing
  else, nothing twice
- the layer holds NO state outside the blocks themselves

That last line is a design decision disguised as an invariant, and it's worth naming as such: all bookkeeping is intrusive — it lives inside the allocation it describes. No table, no registry, no lock.

What we rejected, and why

A side table (aligned pointer → original pointer). It works on paper: keep a map, insert on alloc, look up on free. But the map is shared mutable state, which our contract explicitly forbids — and for good reason: every aligned_malloc and aligned_free on every thread would now contend on one structure, so the "thin layer" acquires a lock the base allocator never asked for. It also has to allocate its own nodes, raising the awkward question of who allocates for the allocator's helper. The stash gets the same information for eight bytes and zero contention. This is the no-shared-state principle applied at the decision, not recited.

Retry until malloc returns something aligned. Call malloc, check alignment, free and retry on failure. Nondeterministic latency, unbounded in the worst case, and it still needs bookkeeping the moment it over-allocates as a fallback. Interviewers occasionally float it as bait; the one-word rebuttal is "unbounded."

Padding without a stash — recompute on free. Could aligned_free re-derive the original pointer arithmetically? No: the distance from the original to the aligned address depends on where malloc's block happened to land, which is precisely the information free-time no longer has. Something must be written down; the only question was where, and "next to the data it describes" beats "in a global structure" on every axis we care about.