← roadmap
week 4 · day 22

The Heap & malloc/free

Memory that outlives the stack frame

Hard 34 min 180 xp
After this you can
  • › Explain why the stack isn't enough and what the heap is for
  • › State the contract of malloc, free, calloc, and realloc precisely
  • › Describe, at a high level, how an allocator tracks free memory with chunk headers
  • › Recognize the classic heap bugs: leak, double-free, use-after-free, and why they matter

Why the stack isn't enough

Stack memory is automatic and fast, but it has a fatal limit for many jobs: it dies when its function returns (the epilogue gives the frame back — day 14). So you cannot return a pointer to a local and expect it to survive; the memory is reused immediately. You also can't easily allocate an amount you only learn at runtime, or memory that must outlive the function that created it. For those you need the heap: a large region of memory you allocate from explicitly and that lives until *you* free it.

Key idea
Stack vs heap. Stack: automatic, LIFO, freed when the function returns, tiny and fast, size mostly fixed. Heap: manual, allocate/free in any order, lives until you free it, large, and you carry the responsibility for giving it back. The heap trades convenience for control — and that control is where both power and every allocation bug come from.

The four calls, and their exact contract

  • void *malloc(size_t n)** — return a pointer to n uninitialized bytes, or NULL if it can't.
  • void *calloc(size_t count, size_t size)** — like malloc for count*size bytes, but zeroed,
  • and it checks the multiplication for overflow (safer for arrays).
  • void *realloc(void *p, size_t n)** — resize p's block to n bytes, moving/copying if needed,
  • returning the new address (day 21).
  • void free(void *p)** — return p's block to the allocator. After this, p is *dangling* — the
  • memory may be reused, so you must not touch it again.

The contract is a promise you must keep: every malloc gets exactly one free, and you never use a block after freeing it. Break that and the bugs are subtle and dangerous.

heap.cc
1int *make_range(int n) {
2    int *a = malloc(n * sizeof(int));   // heap: survives after we return
3    if (!a) return NULL;                // ALWAYS check malloc's result
4    for (int i = 0; i < n; i++) a[i] = i;
5    return a;                           // safe: heap memory outlives this function
6}
7// caller must free() the returned pointer, exactly once, when done.

Compare that to returning &local_array — which would be a bug, because the local dies at ret. Heap memory is exactly the tool for "make something here, use it elsewhere, later." The cost: the caller now *owns* that pointer and must free it. Ownership — who is responsible for the free — is the central discipline of manual memory, and thinking about it explicitly is what separates solid C from leaky C.

What the allocator does under the hood

malloc doesn't ask the OS for memory on every call — that would be far too slow. Instead the C library manages a big region and hands out chunks of it. Just before the bytes it returns to you, it keeps a small header recording the chunk's size and status; freed chunks are threaded onto free lists (glibc groups small recently-freed chunks into a fast per-thread cache called the tcache) so a later malloc of the same size can reuse one instantly.

a heap chunk (glibc, simplified)
   ┌──────────────┬───────────────────────────┐
   │  size / flags│  your bytes (what malloc   │
   │  (header)    │  returns a pointer to) ->  │
   └──────────────┴───────────────────────────┘
   ^header (metadata)     ^ the pointer you get

   free() writes bookkeeping (e.g. free-list links) INTO the
   freed chunk's user area. That's why using memory after free
   is dangerous: the allocator may have written its own data there.
Note
This is why heap *exploitation* exists: those headers and free-list pointers are metadata living right next to your data. A bug that writes past a chunk can corrupt the next chunk's header; a use-after-free can let the allocator's free-list pointer be treated as your data (or vice versa). You're seeing the terrain now; weeks 46–47 of the offensive path turn it into technique. Understand the benign mechanism first and the attacks are obvious.
Predict first
Consider: char *p = malloc(16); free(p); free(p); (a double-free), versus char *p = malloc(16); free(p); p[0] = 'x'; (a use-after-free). In plain terms, why is each dangerous even though nothing "looks" wrong?
finished reading?
Your task, you write the code

Own your memory, and prove it with valgrind

In heap.c: write make_range(n) that heap-allocates and fills an int array and returns it (checking malloc), a caller that uses and then frees it exactly once, and a realloc-based grow. Then DELIBERATELY introduce, in separate copies or #ifdef blocks, (a) a leak (forget to free), (b) a double-free, and (c) a use-after-free, and run each under valgrind to see exactly what it reports. Fix them and get a clean run. Uses only this lesson plus day 16/21.

deliverable: heap.c (+ valgrind output for the buggy and fixed versions)
build & run
$ gcc -O0 -g -Wall heap.c -o heap && ./heap
$ valgrind --leak-check=full ./heap
self-review before running
  • › You always check malloc's return for NULL
  • › The clean version has exactly one free per malloc and a clean valgrind report
  • › You saw valgrind report the leak, the double-free, and the use-after-free
  • › You can explain who 'owns' each pointer (who must free it)
stretchUse calloc for an array and explain why it's safer than malloc + a manual multiply (integer-overflow check + zeroing). Then read one freed chunk's bytes (carefully, in a throwaway program) to glimpse the free-list metadata the allocator wrote — the benign version of what heap exploits abuse.

Self-check

01Why can't you return a pointer to a local variable?
02The core contract of malloc/free is:
03What does the allocator keep just before the bytes malloc returns?
04Why is use-after-free dangerous even when the code 'looks fine'?
0/4 correct · 0/4 checked