Valgrind — detecting memory errors: Worked examples

Before anything, a picture of the vocabulary. A malloc hands you a block — a contiguous strip of heap bytes (see Stack vs Heap). Every byte in that strip carries two invisible tags Memcheck maintains:

Look at the strip above. Green = A-bit set (you may touch it). The hatching = V-bit undefined (the byte is addressable but holds garbage — you may touch it, but the value is meaningless until you write it). Red = A-bit clear (touching it is an error). Every example below is just "which coloured region did the code poke, and how?"

The scenario matrix

Every Memcheck bug is one cell of this table. The Direction column is the geometric "which side of the block" axis (the sign, our "quadrant" here); the Kind column is which of the three questions failed.

#	Cell class	Concrete trigger	Question failed
1	Overflow — past the end (positive side)	`a[N]` on an N-element array	A-bit
2	Underflow — before the start (negative side)	`a[-1]`	A-bit
3	Use-after-free (touch a red block)	read `*p` after `free(p)`	A-bit
4	Double free (free red twice)	`free(p); free(p);`	A-bit (freelist)
5	Uninitialised value used in control flow	`if (*p)` on unwritten heap	V-bit
6	Uninitialised value merely copied (the no-error case)	`int y = x;` unused	none (V travels)
7	Zero / degenerate: `malloc(0)`, `free(NULL)`	boundary allocation sizes	none / defined
8	Leak — definitely lost	overwrite the only pointer	Leak
9	Leak — indirectly lost	lose a struct that owned children	Leak
10	Leak — still reachable (the harmless case)	global pointer left unfreed	Leak (benign)
11	Real-world word problem	a parser that forgets one branch	mixed
12	Exam twist	why `-O2` hides the bug	tooling

The two "no-error" cells (6, 7, 10-benign) matter as much as the red ones: you must know when Valgrind stays silent on purpose, or you'll chase ghosts.

Example 1 — Overflow past the end (Cell 1, positive side)

Forecast: guess the byte offset the bad write lands on before reading on.

Count the block's bytes. 5 * sizeof(int) with sizeof(int) = 4 gives $5 \times 4 = 20$ bytes, offsets $0$ through $19$ . Why this step? The A-bits are set exactly on $[0, 20)$ — everything else on that side is red.
Locate a[5]. Index $5$ means byte offset $5 \times 4 = 20$ , writing 4 bytes: offsets $20, 21, 22, 23$ . Why this step? Offset $20$ is the first byte past the block — the very first red byte on the positive side.
Check the A-bits. $A [20] = 0 \Rightarrow$ Invalid write of size 4. Why this step? The parent's rule: access OK $⟺$ every touched byte is accessible. Byte 20 isn't.

Valgrind prints: Address 0x... is 0 bytes after a block of size 20 alloc'd.

Verify: offset $= 5 \times 4 = 20$ ; block size $= 5 \times 4 = 20$ ; gap $= 20 - 20 = 0$ bytes after. ✓

Example 2 — Underflow before the start (Cell 2, negative side)

Forecast: which byte does a[-1] write, and is it before or after?

Compute the offset. Index $- 1$ → byte offset $- 1 \times 4 = - 4$ , i.e. offsets $- 4, - 3, - 2, - 1$ . Why this step? Negative index walks backwards — the mirror image of Example 1. Many students forget this whole quadrant exists.
Check A-bits. Bytes at offset $- 4.. - 1$ are before the block, A-bit $= 0$ → Invalid write of size 4. Why this step? Same rule, opposite direction; Memcheck guards both edges (see figure).

Valgrind prints: Address 0x... is 4 bytes before a block of size 20 alloc'd.

Verify: offset $= - 1 \times 4 = - 4$ ; magnitude $= ∣ - 4∣ = 4$ bytes before the block. ✓

Example 3 — Use-after-free (Cell 3, touching red)

Forecast: you wrote a defined value first — does that make the read safe?

After free(p). The parent's rule: free sets $A [block] = 0$ and quarantines the block so it isn't reused. Why this step? Quarantine keeps the A-bit at 0 long enough to catch us; without it a fresh malloc might recolour the bytes green and hide the bug.
Read *p. Byte offset 0 now has A-bit $= 0$ → Invalid read of size 4. Why this step? It's an A-bit error — "not yours to touch" — even though the value was once defined. Defined-ness is irrelevant once you're forbidden to touch.

Valgrind prints: Invalid read of size 4 ... Address 0x... is 0 bytes inside a block of size 4 free'd.

Verify: block size $= 4$ bytes; read at offset $0$ , which is $0$ bytes inside a freed block. ✓

Example 4 — Double free (Cell 4)

Forecast: the first free succeeded — why does the second one fail?

First free(p). Block goes onto the quarantine freelist; A-bits $= 0$ . Why this step? Memcheck now remembers this block is dead.
Second free(p). Valgrind checks: is this pointer to a currently allocated block? No — it's on the freelist → Invalid free() / delete / delete[]. Why this step? Freeing an already-freed pointer corrupts the real allocator's bookkeeping (see malloc and free) — classic Undefined Behaviour in C.

Valgrind prints: Invalid free() ... Address 0x... is 0 bytes inside a block of size 4 free'd.

Verify (logical): allocated blocks after two frees $= 1 - 1 - 1 = - 1 < 0$ , impossible → second free is invalid. ✓

Example 5 — Uninitialised value in control flow (Cell 5, V-bit)

Forecast: the byte is addressable — so where's the crime?

A-bit is fine. You malloc'd it, so $A = 1$ over $[0, 4)$ — the read itself is allowed. Why this step? Rules out an A-bit report; it will be silent about addressability.
V-bit is undefined. You never wrote *p, so its V-bits say "garbage". Why this step? The comparison *p == 0 produces a result whose truth depends on garbage.
The if uses that result for control flow. Now Memcheck fires: Conditional jump or move depends on uninitialised value(s). Why this step? Memcheck lets undefined values travel silently; it only complains at the moment garbage actually changes what the program does — a branch or a syscall.

Verify (logical): the branch outcome is a function of undefined bits ⇒ program behaviour is non-deterministic ⇒ exactly the condition Memcheck flags. ✓

Example 6 — Uninitialised value merely copied (Cell 6, the NO-error case)

Forecast: we read undefined memory — surely that's a bug?

int y = *p; copies undefined V-bits into y. No error. Why this step? Copying garbage is legal in Memcheck's model — the V-bits ride along with the value into y.
y is never used in a branch, index, or output. So the garbage never influences behaviour → silent. Why this step? This is the deliberate design: flagging every copy would drown you in false positives.

Verify (logical): number of Memcheck errors here $= 0$ (no branch/output consumes undefined bits). ✓

Example 7 — Zero and degenerate inputs (Cell 7)

Forecast: can you allocate nothing? Can you free nothing?

malloc(0) returns either NULL or a unique pointer you may pass to free but not dereference (0 addressable bytes). Why this step? The block has size 0, so any *q would be "0 bytes after a block of size 0" — but we don't dereference, so no error.
free(q) is valid whether q is that zero-size block or NULL. Why this step? The C standard makes this well-defined; Memcheck agrees.
free(NULL) is explicitly a no-op by the standard. Why this step? This is the degenerate limit — the "zero input" of the free operation — and it is silent, not an error.

Verify (logical): errors $= 0$ ; both frees are standard-defined no-ops / valid. ✓

Example 8 — Definitely lost (Cell 8)

Forecast: how many blocks live? How many pointers survive to reach them?

After buf = malloc(200). The address of the 100-byte block is nowhere — the only variable holding it was overwritten. Why this step? The exit-time mark-and-sweep starts from live pointers; if none point into a block, it's unreachable.
Classify. Unreachable and no interior pointer → definitely lost: 100 bytes in 1 block. Why this step? Matches the parent's leak-rule tree exactly.
The 200 block is freed → fine.

Verify: leaked bytes $= \sum unreachable sizes = 100$ ; freed cleanly $= 200$ . ✓

Example 9 — Indirectly lost (Cell 9)

Worked example Statement

struct Node { struct Node *next; };
struct Node *head = malloc(sizeof *head);   // block P
head->next = malloc(sizeof *head);          // block C, reached via P
head = NULL;                                // drop P

With sizeof(struct Node) = 8, classify both blocks.

Forecast: head is gone — but a pointer to C still exists inside P. Does that save C?

Drop P. Setting head = NULL makes block P unreachable → definitely lost, 8 bytes. Why this step? No live variable points to P.
What about C? The only pointer to C lives inside P — but P itself is lost. So C is reachable only through a lost block → indirectly lost, 8 bytes. Why this step? This is the whole point of the "indirectly lost" category: you lost the root, and everything it owned falls with it.

Verify: definitely lost $= 8$ ; indirectly lost $= 8$ ; total unreachable $= 8 + 8 = 16$ bytes. ✓

Example 10 — Still reachable, the benign case (Cell 10)

Forecast: we never free(pool) — is that a "definitely lost" bug?

At exit, pool still holds the address. A live (global) pointer points into the block. Why this step? Reachability from a global counts — the block is findable.
Classify as still reachable: 50 bytes. Not "definitely lost". Why this step? The OS reclaims it at process exit; this is the harmless leak category the parent warned you not to over-prioritise.

Verify: still-reachable bytes $= 50$ ; definitely-lost $= 0$ . ✓

Example 11 — Real-world word problem (Cell 11)

Forecast: which lines produce lost blocks?

Valid lines (7). Pointer stored in the array → reachable at exit → not definitely lost. Why this step? The array root keeps them findable.
Blank lines (3). Buffer allocated, pointer overwritten on next iteration, never stored, never freed → each unreachable. Why this step? The continue skips both storage and free, orphaning the block.
Total. $3 \times 64 = 192$ bytes definitely lost in 3 blocks. Why this step? Each blank line contributes one orphaned 64-byte block.

Verify: leaked $= 3 \times 64 = 192$ bytes in $3$ blocks; reachable $= 7 \times 64 = 448$ bytes. ✓

Example 12 — Exam twist: why `-O2` hides the bug (Cell 12)

Forecast: the bug didn't vanish — so why is the report clean?

Dead-store elimination. The optimiser sees the value written to a[5] is never read, so it deletes the store entirely. Why this step? Under Undefined Behaviour in C the compiler may assume no out-of-bounds write happens; with no observable effect, it removes the instruction.
No memory access ⇒ nothing for Memcheck to instrument. Valgrind can only check accesses that survive to run. Why this step? Memcheck watches the emitted machine code, not your source.
Fix: always debug with -O0 -g first (see Debugging with GDB), then re-audit the release build separately. Cross-check with AddressSanitizer (ASan), which instruments at compile time and can catch some cases the optimiser reshapes.

Verify (logical): eliminated accesses $= 1$ ; accesses Memcheck can see $= max (0, 1 - 1) = 0$ ⇒ zero reports. ✓

Recall Cover check: name the cell for each symptom

"Invalid read, 0 bytes inside a free'd block" ::: Cell 3, use-after-free (A-bit) "4 bytes before a block of size 20" ::: Cell 2, underflow (A-bit, negative side) "Conditional jump depends on uninitialised value" ::: Cell 5, V-bit in control flow Silent report after copying garbage into an unused variable ::: Cell 6, V-bits travel, no use "indirectly lost" 8 bytes ::: Cell 9, child reachable only through a lost parent Clean report under -O2 that fails under -O0 ::: Cell 12, dead-store elimination