Malloc Lab · Writing malloc by Hand¶
Verified locally
./mdriver -V → 97 / 100 (util 57 + throughput 40), averaging 95% utilization over 11 traces.
The course's toughest assignment: implement mm_malloc, mm_free, and mm_realloc from scratch on a raw heap from mem_sbrk. Every byte of metadata and every wasted gap is counted.
The assignment
You manage a single contiguous heap that only grows (via mem_sbrk). You must provide:
mm_init— set up the empty heap,mm_malloc(size)— return an 8-byte-aligned block with room forsizepayload bytes,mm_free(ptr)— release a block,mm_realloc(ptr, size)— resize while preserving the old contents.
The grader scores two quantities that pull in opposite directions:
- Utilization — payload bytes actually requested ÷ peak heap size. Rewards small metadata and tight packing.
- Throughput — operations per second. Rewards fast searches and cheap bookkeeping.
Push utilization and you add splitting, coalescing, and search work that hurts throughput. Push throughput and you leak internal fragmentation. The design is about balancing the two.
From one list to twelve¶
This allocator is the sixth shape the code took, not the first. Each redesign fixed the specific pain the previous one exposed — and each left a visible fossil in the final source. The route:
1 · Implicit free list. The textbook baseline: every block carries a header and footer, and the fit search walks every block in the heap, allocated or not. Correct in an afternoon, and hopeless on throughput — on allocation-heavy traces the search wades through thousands of blocks that were never candidates.
implicit -- the fit search visits EVERY block, allocated or not:
[A][A][F][A][F][A][A][F][A][F] one list = the whole heap
explicit -- free blocks thread a list through their own payloads:
[F] <-> [F] <-> [F] allocated blocks never visited
2 · Explicit, doubly linked. Free blocks recycle their first two payload words as prev/next links, so the search touches only genuine candidates and free becomes an O(1) LIFO insert. The price moves to the edges: with NULL at both ends, insert and remove fracture into empty-list, head, middle, and tail cases — four flavors of two-pointer surgery, each a segfault in waiting.
3 · Close the ring. Make the list circular: the last block links back to the first. Ends stop existing, so end-handling stops existing — a removal in the middle is the same splice as anywhere else. Two special cases survive: the empty list, and removing the very block the head pointer names.
NULL-ended NULL <- [F] <-> [F] <-> [F] -> NULL
circular .--> [F] <-> [F] <-> [F] <--.
'---------------------------'
sentinel .--> [S] <-> [F] <-> [F] <--.
'---------------------------'
4 · Plant a sentinel. The classic finisher: a permanent dummy node [S] that always sits in the ring. "Empty" becomes "the sentinel alone," the head never moves, and insert/remove collapse into two unconditional pointer splices. Zero branches, textbook-pretty.
5 · Segregate by size. One list still fits badly as the heap fills: either wade past piles of too-small blocks, or take the first oversized one and bleed utilization. Splitting free blocks into 12 geometric size classes shrinks every search to blocks that could plausibly fit. Under the sentinel pattern, that means twelve rings — and twelve sentinels.
6 · Fire the sentinels, keep the rings. Two facts gang up on those dummies. Malloclab allows only scalar globals — no global arrays or structs — so the whole apparatus must live inside the heap, where every byte counts against utilization. And a sentinel needs two words (prev + next) where a bare head pointer needs one: 12 × 8 = 96 bytes against 12 × 4 = 48. So the final code mem_sbrks a 48-byte array of one-word class heads as the heap's very first bytes, and the dummies go. The branches the sentinels had erased walk right back in — the empty-class check in insert_node, the head hand-off in remove_node — two predictable compares, bought for half the metadata. The rings themselves stayed: the circular links in today's code are the sentinel era's fossil.
Design at a glance¶
| Decision | Choice here | Buys us |
|---|---|---|
| Free-block organization | Segregated explicit free lists, 12 classes | Search only size-relevant free blocks, never allocated ones |
| Allocated-block metadata | Footer-less (header only) | 4 fewer overhead bytes per live block |
| Free-list links | One 32-bit word each, in the free payload | 16-byte minimum free block |
| Coalescing | Immediate, on every free | No deferred-fragmentation bookkeeping |
| Fit policy | First class containing a fit, best fit within it | Tighter than first-fit, with class-local scans |
| Realloc | Reuse adjacent space before allocating a replacement | Avoids most malloc-copy-free cycles |
The constants that anchor everything:
#define WSIZE 4 /* word = header/footer size */
#define DSIZE 8 /* double word = alignment */
#define CHUNKSIZE (1<<6) /* heap is extended 64 bytes at a time */
#define CLASSNUM 12 /* number of size classes */
Block anatomy¶
Every block starts with a one-word (4-byte) header. Because sizes are always a multiple of 8, the low three bits are free real estate for flags — here two of them are used:
bit: 31 ........................ 3 2 1 0
+-----------------------------+----+----+----+
| block size | 0 | PA | A |
+-----------------------------+----+----+----+
A (bit 0) = is THIS block allocated?
PA (bit 1) = is the PREVIOUS block allocated?
That PA (previous-allocated) bit is the linchpin of the whole design — more on it in a moment. The header is decoded with three tiny macros:
#define GET_SIZE(p) (GET(p) & ~0x7) // (1)
#define GET_ALLOC(p) (GET(p) & 0x1) // (2)
#define GET_PREV_ALLOC(p) (GET(p) & 0x2) // (3)
- Mask off the three flag bits to recover the size.
- Bit 0: is this block allocated?
- Bit 1: is the previous (adjacent, lower-address) block allocated? Reading this is what lets us skip the previous block's footer.
An allocated block carries nothing but the header and the payload. A free block is richer: it reuses the first two payload words as list links, and keeps a footer (a copy of the header) at its tail:
Allocated block Free block (not to scale)
+------------------+ <- header +------------------+ <- header
| size | PA | 1 | | size | PA | 0 |
+------------------+ <- bp +------------------+ <- bp
| | | prev free ptr | (4 bytes)
| payload | +------------------+
| | | next free ptr | (4 bytes)
| | +------------------+
| | | free payload* |
+------------------+ +------------------+
no footer! | size | PA | 0 | <- footer
+------------------+
* absent from a minimum 16-byte free block
Why the links are one word
A free block must hold a header + two links + a footer, so link width sets the minimum block size: 4 + 4 + 4 + 4 = 16 bytes. The driver builds with -m32, where a pointer is naturally 4 bytes — and the link macros pin that layout down explicitly by storing every link as an unsigned int:
#define GET_PTR(p) ((char *)(uintptr_t)GET(p)) // read one word -> pointer
#define PUT_PTR(p, val) (PUT((p), (unsigned int)(uintptr_t)(val)))
Under -m32 the casts are a no-op; on a 64-bit rebuild they become genuine truncation, which stays safe only while every heap address fits in 32 bits. Either way the layout — and the 16-byte minimum — holds, where native 8-byte links would push it to 24.
Navigation between neighbors is pure pointer arithmetic off the size in the header (and, for the previous block, its footer):
#define HDRP(bp) ((char *)(bp) - WSIZE)
#define FTRP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE)
#define NEXT_BLKP(bp) ((char *)(bp) + GET_SIZE((char *)(bp) - WSIZE))
#define PREV_BLKP(bp) ((char *)(bp) - GET_SIZE((char *)(bp) - DSIZE)) // (1)
PREV_BLKPreads the previous block's footer (bp - DSIZE) to learn its size. This only works if the previous block has a footer — i.e. if it is free. That's exactly the case in which we need it, which is what makes the next optimization safe.
Footer-less allocated blocks¶
The classic CS:APP allocator gives every block a footer so that, when freeing block B, we can look at B's left neighbor's footer to decide whether to coalesce backward. Footers on allocated blocks are pure overhead, though — 4 bytes lost on every live object.
The fix is the PA bit. Each block's header already records whether its left neighbor is allocated. So:
- To coalesce backward, check
GET_PREV_ALLOC— no footer read needed. - Only when the neighbor turns out to be free do we consult its footer (via
PREV_BLKP), and free blocks still carry one.
The result: allocated blocks drop their footer entirely (4-byte overhead → header only), while the backward-coalescing machinery keeps working. The one obligation is discipline: every path that allocates or frees a block must update the PA bit of the following block. For example, mm_free clears the next block's PA bit:
PUT(HDRP(NEXT_BLKP(bp)),
PACK(GET_SIZE(HDRP(NEXT_BLKP(bp))), GET_ALLOC(HDRP(NEXT_BLKP(bp))))); // (1)
- Rewrites the next header with its own size and alloc bit, but without the
0x2flag — signalling "the block before me is now free."
Segregated free lists¶
Free blocks are bucketed into 12 size classes, each an independent circular doubly-linked list. The 12 head pointers live in a small array carved from the very front of the heap — they can't be a C global, because the lab allows only scalar globals:
if ((seg_free_lists = mem_sbrk(CLASSNUM * WSIZE)) == (void *)-1)
return -1;
for (i = 0; i < CLASSNUM; i++) SET_SEG_HEAD(i, NULL);
seg_free_lists (12 heads)
+----------+
| class 0 | --> NULL
| class 1 | --> F1 (ring shown below)
| class 2 | --> NULL
| ... |
| class 11 | --> NULL
+----------+
class 1 ring:
F3.next -> F1
.-----------------------.
v |
[F1] <-> [F2] <-> [F3]
| ^
'-----------------------'
F1.prev -> F3
A request's class is chosen from its size. The index grows geometrically — each class covers roughly double the size range of the one before, and class 11 is a catch-all:
static size_t find_index(size_t asize) {
size_t index, count = 0;
if (asize <= 2*DSIZE) return 0; // (1)
index = (asize - WSIZE - 1) >> 4; // (2)
while (index && count < (CLASSNUM-1)) { // (3)
index >>= 1;
count += 1;
}
return count;
}
- The smallest blocks (16 bytes) all land in class 0.
- Scale the size down into a coarse bucket number.
- Count how many halvings reduce it to zero — i.e.
⌊log2⌋— capped at 11. Bigger blocks climb to higher classes.
| Class | Holds blocks of (bytes) |
|---|---|
| 0 | 16 |
| 1 | 24 – 32 |
| 2 | 40 – 64 |
| 3 | 72 – 128 |
| ... | roughly doubling each step |
| 11 | everything larger (catch-all) |
Rounding payloads for reuse¶
Before sizing a block, small and medium payloads are rounded up to the next power of two (between 16 and 512). Two allocations that round to the same class become perfectly interchangeable later, which cuts fragmentation over a long run of malloc/free:
static size_t round_payload(size_t size) {
size_t rounded = 16;
if (size <= 16) return size;
while (rounded < size && rounded < 512) rounded <<= 1;
if (rounded >= size && rounded <= 512) return rounded;
return size; // (1)
}
- Very large requests (> 512) are left exactly as asked — rounding them would waste too much.
Insert, remove, and the fit search¶
Insertion is LIFO at the head of the class list (the just-freed block is the likeliest to still be warm in cache). find_fit starts at the request's class and scans each non-empty ring in turn. If a class has no adequate block, it climbs to the next; once a class yields one or more fits, it keeps the smallest and stops. Each scan is linear in that ring's length, but allocated blocks are never visited:
static void *find_fit(size_t asize) {
size_t minSize, index = find_index(asize);
char *ptr = NULL;
while (index < CLASSNUM && ptr == NULL) {
char *bp = SEG_HEAD(index);
if (bp == NULL) { index++; continue; } // (1)
do {
if (asize <= GET_SIZE(HDRP(bp))) { // (2)
if (ptr == NULL || GET_SIZE(HDRP(bp)) < minSize) {
ptr = bp;
minSize = GET_SIZE(HDRP(ptr));
}
}
bp = NEXT_FBLKP(bp);
} while (bp != SEG_HEAD(index)); // (3)
index++;
}
return ptr; // NULL => must extend the heap
}
- Empty class? Climb to the next one immediately.
- Track the tightest block seen so far in this class.
- The list is circular, so we stop once we loop back to the head.
Placement and splitting¶
Once a fit is found, place marks it allocated and — if the leftover is at least one minimum block (16 bytes) — splits it, returning the tail to the free lists:
static void place(void *bp, size_t asize) {
size_t csize = GET_SIZE(HDRP(bp));
if ((csize - asize) >= (2*DSIZE)) { // splittable
remove_node(bp);
PUT(HDRP(bp), PACK(asize, GET_PREV_ALLOC(HDRP(bp)) | 0x1));
PUT(HDRP(NEXT_BLKP(bp)), PACK(csize-asize, 0x2)); // (1)
PUT(FTRP(NEXT_BLKP(bp)), PACK(csize-asize, 0x2));
insert_node(NEXT_BLKP(bp));
} else { // use whole block
remove_node(bp);
PUT(HDRP(bp), PACK(csize, GET_PREV_ALLOC(HDRP(bp)) | 0x1));
bp = NEXT_BLKP(bp);
PUT(HDRP(bp), PACK(GET_SIZE(HDRP(bp)), GET_ALLOC(HDRP(bp)) | 0x2)); // (2)
}
}
- The remainder's header gets
PA = 1(its new left neighbor — the block we just allocated — is allocated) and stays free, so it also gets a footer. - No split: the following block's
PAbit is set, because its left neighbor is now allocated. KeepingPAhonest on both paths is what makes the footer-less scheme correct.
Coalescing — immediate, four cases¶
Freeing merges with adjacent free blocks right away. The PA bit and the next block's alloc bit give four cases:
-
① prev alloc · next alloc
Nothing to merge — just insert the block into its class.
-
② prev alloc · next free
Absorb the next block:
size += next, rewrite header + footer. -
③ prev free · next alloc
Absorb backward into the previous block; the merged block starts at
PREV_BLKP(bp). -
④ prev free · next free
Swallow both neighbors into one block spanning all three.
static void *coalesce(void *bp) {
size_t prev_alloc = GET_PREV_ALLOC(HDRP(bp)); // (1)
size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp)));
size_t size = GET_SIZE(HDRP(bp));
if (prev_alloc && next_alloc) { // case 1
insert_node(bp);
return bp;
} else if (prev_alloc && !next_alloc) { // case 2
remove_node(NEXT_BLKP(bp));
size += GET_SIZE(HDRP(NEXT_BLKP(bp)));
PUT(HDRP(bp), PACK(size, 0x2));
PUT(FTRP(bp), PACK(size, 0x2));
} else if (!prev_alloc && next_alloc) { // case 3
remove_node(PREV_BLKP(bp));
size += GET_SIZE(HDRP(PREV_BLKP(bp)));
PUT(FTRP(bp), PACK(size, GET_PREV_ALLOC(HDRP(PREV_BLKP(bp)))));
PUT(HDRP(PREV_BLKP(bp)), PACK(size, GET_PREV_ALLOC(HDRP(PREV_BLKP(bp)))));
bp = PREV_BLKP(bp);
} else { // case 4
remove_node(PREV_BLKP(bp));
remove_node(NEXT_BLKP(bp));
size += GET_SIZE(HDRP(PREV_BLKP(bp))) + GET_SIZE(HDRP(NEXT_BLKP(bp)));
PUT(HDRP(PREV_BLKP(bp)), PACK(size, GET_PREV_ALLOC(HDRP(PREV_BLKP(bp)))));
PUT(FTRP(NEXT_BLKP(bp)), PACK(size, GET_PREV_ALLOC(HDRP(PREV_BLKP(bp)))));
bp = PREV_BLKP(bp);
}
insert_node(bp); // (2)
return bp;
}
- Both neighbor-states come essentially for free: the previous one from this header's
PAbit, the next one from the adjacent header — no linear scan. - In every merging case the enlarged block is re-inserted once, into whichever class its new (larger) size selects.
Because free blocks are always merged on the spot, the heap never accumulates runs of tiny adjacent free blocks — the source of most fragmentation.
Realloc: grow in place before copying¶
The naive realloc is "malloc a new block, memcpy, free the old." This implementation first tries to reuse the current block or its neighbors. Growing at the heap end or into the next block leaves the payload in place; using the previous block requires memmove, but still avoids allocating a separate replacement. A fresh malloc-copy-free cycle is the final fallback.
realloc(bp, size)
|
+- asize <= bsize ............... keep block in place
| `- remainder >= 16 B ......... split off the tail
|
+- must grow -- try, in order:
+- bp is the last block ....... mem_sbrk the shortage, extend in place
+- next free hits heap end,
| but is still too small ...... absorb next + sbrk the rest
+- next free, room to split ... absorb next, leave the remainder free
+- next free, just enough ..... absorb the whole next block
+- prev free & big enough ..... memmove into prev, absorb it
+- both neighbors free enough . memmove into prev, absorb both
`- none of the above .......... malloc + memcpy + free (fallback)
Two touches make this pay off:
-
Slack on growth. Before rounding, the request is padded by
size >> 4(≈ 6 %). A program that grows a buffer in a loop then finds the next realloc already fits, avoiding a cascade of copies: -
The heap-end shortcut. If the block being grown is the last real block (its "next" is the epilogue, size 0), we simply
mem_sbrkthe exact shortfall and stretch the block — no search, no copy:if (GET_SIZE(HDRP(NEXT_BLKP(bp))) == 0) { // (1) if (mem_sbrk(asize - bsize) == (void *)-1) return NULL; PUT(HDRP(bp), PACK(asize, GET_PREV_ALLOC(HDRP(bp)) | 0x1)); PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 0x3)); // (2) return bp; }- A zero-size next header is the epilogue:
bpsits at the top of the heap. - Re-lay the epilogue immediately after the grown block, with
PA = 1.
- A zero-size next header is the epilogue:
When a neighbor is used, the code is deliberately stricter than the 16-byte structural minimum: it splits only when the remainder is at least 4·DSIZE = 32 bytes. A 16- or 24-byte remainder would be legal, but absorbing it trades a little internal slack for fewer small free-list nodes. Shrinking the current block still uses the ordinary 16-byte threshold shown above; the 32-byte rule applies only to neighbor-assisted growth. When no adjacent path can satisfy the request, the code falls through to malloc-copy-free and copies at most the old payload's worth of bytes.