Why this matters: this implementation is short enough that an interviewer will read every character, and the arithmetic is the kind that looks right while being off by one slot. The defense is the same one used throughout this course's systems chapters: walk the pointer math on concrete numbers, out loud, before anyone asks.
Validation first
bool is_power_of_two(size_t a) {
return a != 0 && (a & (a - 1)) == 0;
}The idiom deserves one sentence of narration: a power of two has exactly one set bit; subtracting 1 flips that bit off and sets all bits below it, so the AND is zero only for powers of two. Callers pass alignment; the contract says you check it — so check it, and decide the failure mode (return NULL) explicitly rather than by accident.
aligned_malloc
void* aligned_malloc(size_t size, size_t alignment) {
if (!is_power_of_two(alignment) || size == 0) return NULL;
if (alignment < sizeof(void*)) alignment = sizeof(void*); // floor: 8
// worst-case room: payload + round-up slack + the stash slot
void* raw = malloc(size + alignment - 1 + sizeof(void*));
if (raw == NULL) return NULL;
uintptr_t start = (uintptr_t) raw + sizeof(void*); // leave stash room
uintptr_t aligned = (start + alignment - 1) & ~(uintptr_t)(alignment - 1);
((void**) aligned)[-1] = raw; // the stash
return (void*) aligned;
}The walk, on real numbers
Take aligned_malloc(100, 16) and suppose malloc returns 0x1003 (deliberately ugly — 8-byte-aligned malloc wouldn't return this, but the arithmetic must not care):
raw = 0x1003 start = 0x1003 + 8 = 0x100B (first byte past stash room) + 15 = 0x101A & ~0xF = 0x1010 (next 16-boundary at/after start) stash at 0x1010 - 8 = 0x1008 stores 0x1003 return 0x1010
Now verify the invariants against the numbers, the way an interviewer would: 0x1010 % 16 == 0 — aligned. The stash slot spans 0x1008 to 0x100F — entirely at or after raw, so it's inside our block. The payload runs 0x1010 to 0x1073 (100 bytes); the block runs to 0x1003 + 100 + 15 + 8 = 0x107E — payload fits with room to spare. Padding actually consumed: 0x1010 − 0x1003 = 13 bytes, under the 23-byte worst case we budgeted. Every claim checked, no hand-waving available.
One edge worth narrating: if malloc happens to return an address where start is already aligned, the mask leaves it unchanged and the stash sits directly below — the formula needs no special case, which is why it's written this way.
aligned_free
void aligned_free(void* p) {
if (p == NULL) return;
void* raw = ((void**) p)[-1]; // read the stash
free(raw);
}Three lines, and each carries contract weight. The NULL check mirrors free's own tolerance. The stash read is legal only because every pointer this function may legally receive came from aligned_malloc — which is exactly why mixing with plain free is undefined in both directions: plain free would hand malloc an address it never issued (0x1010, not 0x1003), and aligned_free on a plain-malloc'd pointer would read garbage as an address and free it. Say that failure mode; it shows the contract and the code are the same object in your head.
What you'd say about complexity
Time: O(1) over the base malloc/free — a constant handful of arithmetic operations on each side. Space: alignment − 1 + sizeof(void*) worst-case overhead per allocation, actual overhead typically less (13 bytes in our walk); state the worst case against the budget from lesson 01 — for 4096-byte alignment that's ~4 KiB per allocation, which is why huge alignments deserve the separate discussion in the next lesson.
Key takeaway
The implementation is a validation idiom, one over-allocation, one mask round-up starting past the stash slot, one stashed pointer, and a three-line free that reads it back. The grade lives in the walk: raw 0x1003, start 0x100B, aligned 0x1010, stash at 0x1008 — every invariant checked on real digits, including the mixing failure that the contract calls undefined.