Valgrind — detecting memory errors

WHY does this tool exist?

C gives you raw pointers and no automatic memory management. The CPU happily reads/writes any address; if you malloc(10) and write byte 11, nothing crashes immediately — you corrupt the heap and the program dies "randomly" 5000 lines later. These bugs are:

• Non-deterministic (depend on heap layout, timing).
• Silent (no compiler warning, often no crash).

WHAT it tracks (the core trick — shadow memory): For every byte of real memory, Memcheck keeps two bits of info:

• A-bits (Addressability): is this byte allowed to be accessed right now?
• V-bits (Validity/defined-ness): does this byte hold a defined value, or garbage from malloc?

HOW Memcheck reasons (derivation from first principles)

We don't have a formula here — we have a decision procedure. Let's build it.

Let address $a$ and access size $n$. For a read or write of $n$ bytes starting at $a$:

If any byte is not accessible ⇒ Invalid read/write error.

For defined-ness, V-bits propagate through operations. Starting rules:

The leak rule (mark-and-sweep at exit): at program end, Memcheck does a GC-style scan. A heap block is:

• Still reachable: a pointer to it exists somewhere → not a "lost" leak (but still unfreed).
• Definitely lost: no pointer anywhere points into it → you leaked it.
• Indirectly lost: only reachable through another lost block.
• Possibly lost: only an interior pointer points to it.

Worked Example 1 — Heap buffer overflow

#include <stdlib.h>
int main(void) {
    int *a = malloc(5 * sizeof(int)); // 20 bytes, A-bits=1, V-bits=undef
    a[5] = 42;                         // writes bytes 20..23 -> A-bits=0!
    free(a);
    return 0;
}

Run: gcc -g -O0 prog.c && valgrind --leak-check=full ./a.out

Valgrind says:

Invalid write of size 4
   at main (prog.c:4)
 Address 0x... is 0 bytes after a block of size 20 alloc'd

Worked Example 2 — Use of uninitialised value

#include <stdio.h>
#include <stdlib.h>
int main(void) {
    int *p = malloc(sizeof(int)); // V-bits = undefined
    if (*p == 0)                  // branching on undefined value!
        printf("zero\n");
    free(p);
    return 0;
}

Conditional jump or move depends on uninitialised value(s)

Worked Example 3 — Memory leak

#include <stdlib.h>
int main(void) {
    char *buf = malloc(100);
    buf = malloc(200);   // first 100-byte block now unreachable
    free(buf);           // frees the 200, leaks the 100
    return 0;
}

LEAK SUMMARY:
   definitely lost: 100 bytes in 1 blocks

Flashcards

Connections

• malloc and free — the allocations Valgrind shadows
• Pointers in C — invalid/dangling pointers are what A-bits guard
• Undefined Behaviour in C — why these bugs are silent
• Stack vs Heap — Memcheck mainly polices the heap
• AddressSanitizer (ASan) — compiler-based alternative, faster, different trade-offs
• Debugging with GDB — pair with Valgrind for root-cause analysis

Concept Map

Hinglish (regional understanding)