Visual walkthrough — Valgrind — detecting memory errors

We assume nothing. If a word like "heap" or "pointer" appears, we draw it first.

Step 1 — What is a byte of memory, and what does it mean to "access" it?

WHAT. A computer's memory is a long row of numbered boxes. Each box holds exactly one byte (a number from 0 to 255). Each box has an address — its position number in the row. That's all "memory" is: numbered boxes in a line.

To access a box means either to read it (look at the number inside) or write it (put a new number in). A program does millions of these per second.

WHY draw this first. Every Valgrind concept — addressability, validity, leaks — is a rule about these boxes. If the boxes aren't concrete in your head, nothing later will be.

PICTURE. Below, the gray strip is raw memory. We highlight one region your program will "own" after it asks for space.

Step 2 — The heap, and what malloc(20) actually does

WHAT. The heap is a big pool of those boxes that your program can request at runtime. The request is malloc(20): "please reserve me 20 consecutive boxes." malloc hands back the address of the first box — a pointer. See malloc and free.

WHY this tool and not a plain variable. A plain variable lives on the stack and disappears when its function returns. When you need memory whose size or lifetime you decide while running, you must ask the heap. That freedom is exactly why heap bugs exist — nobody hands the boxes back for you.

PICTURE. Twenty boxes turn from "not yours" (gray) to "yours" (blue). Above them we now start drawing the two rows of shadow bits Memcheck secretly keeps.

Step 3 — The access-legality rule (the one check behind "Invalid write")

WHAT. Before every read or write, Memcheck asks a single yes/no question: are all the boxes I'm about to touch marked $A=1$?

WHY this exact rule. The hardware never asks this — it will happily write box number 999. The whole point of Valgrind is to insert this missing question. It is a decision procedure, not a formula: given an access, output OK or ERROR.

PICTURE. An access is an arrow landing on a run of boxes. Green arrow = every box under it has $A=1$ (allowed). Red arrow = at least one box has $A=0$ (forbidden → error).

Step 4 — Watching the overflow a[5] = 42 go wrong

WHAT. We reserved 20 bytes = room for 5 ints (each int is 4 boxes). Valid indices are a[0]…a[4]. The code writes a[5].

An index is turned into an address like this: $\text{address of }a[k]=\underset{\text{first box}}{\underbrace{a}}+\underset{\text{index}}{\underbrace{k}}\times \underset{\text{bytes per int}}{\underbrace{4}}$

So a[5] sits at byte $5\times 4=20$ — the very first box past the reserved 20. That box has $A=0$.

WHY it's caught here and not by the compiler. The compiler only checks types, not whether index 5 fits. The CPU only checks nothing. Memcheck's Step-3 rule is the first and only guard: it sees a size-4 write landing on boxes 20–23, all with $A=0$, and fires.

PICTURE. The write arrow (size 4) overhangs the blue block by exactly 4 red boxes.

Step 5 — A different wrongness: using an undefined value (V-bits)

WHAT. Now a program that never leaves its box: it mallocs one int and immediately does if (*p == 0). The box is $A=1$ (yours, no illegal touch) — but you never wrote it, so $V=\text{undef}$.

WHY two bit-kinds are needed. "Am I allowed here?" (A) and "Is what's here meaningful?" (V) are genuinely different questions. Reading garbage is legal as long as you don't let it change what your program does. So Memcheck lets undefined bits travel silently — until they reach a decision (a branch), where garbage would make the program behave unpredictably. See Undefined Behaviour in C.

PICTURE. The value flows: copy is fine (V-bit rides along), but the if diamond is where the alarm rings.

Step 6 — free, and why freed boxes stay quarantined

WHAT. free(p) tells Memcheck to set $A=0$ across the whole block — "you may no longer touch this." Crucially the boxes are not returned to malloc right away; they sit in a quarantine freelist.

WHY quarantine. If free recycled the boxes instantly, the next malloc might hand the same boxes back with $A=1$ again — and a lingering pointer reading them (a use-after-free) would land on legal memory and slip through. Keeping $A=0$ for a while preserves the crime scene.

PICTURE. Block flips blue→red on free, then waits in a "quarantine" holding pen; a stale read arrow now lands on red.

Step 7 — Leaks: the exit-time pointer hunt

WHAT. When main returns, Memcheck does one final sweep: starting from all still-live pointers (globals, stack, registers), it follows them into the heap and marks every block it can reach. Any block nobody can reach was leaked.

WHY a scan and not a counter. A block leaks the instant the last pointer to it is overwritten — but that moment is invisible while running. Only at exit can Memcheck take a full census of who-still-points-where. This is a mark-and-sweep, like a garbage collector's reachability pass.

PICTURE. Two blocks; a pointer moved from the first to the second. The first has no arrow into it → unreachable → "definitely lost".

Step 8 — Edge & degenerate cases (so no scenario surprises you)

WHAT/WHY/PICTURE, all in one figure — the corners that break naive intuition:

1. malloc(0) — reserves 0 boxes. malloc may return a non-NULL pointer, but any access through it is $A=0$ → Invalid. Nothing is yours.
2. free(NULL) — legal and defined to do nothing. No error.
3. Double free — second free hits an already-quarantined block → "Invalid free / delete".
4. Off-by-one read (a[5] read, not write) — same $A=0$ box → "Invalid read of size 4". Reads count too.
5. Copying an undefined value (int y = *p; without a branch) — no error yet; the $V=\text{undef}$ bit simply copies into y. The alarm waits for a decision.

The one-picture summary

Everything above is one loop: before each access, check A; propagate V; at exit, sweep for leaks.

Flashcards