Deep Dive: Pointer, Heap, and Valgrind Mechanics

This page is optional reading. The Week 5 lessons (Pointer Basics through Valgrind) tell you what rules to follow for pointers, heap allocation, and leak-free Lab 6 submissions. This page tells you what the machine and the allocator actually do underneath, so the rules stop being arbitrary and start being obvious.

For the ELF/loader/stack-frame level below this, see Deep Dive: The C Machine Model. For the named exploits that the six bug classes produce in shipping software, see Deep Dive: C Memory Safety.

Nothing here is required for Lab 6, Quiz 2, or the final. It is for the part of your brain that asks “but what actually happens when I call malloc?”

A pointer is eight bytes on the stack

On the lab machines (Linux x86-64), every pointer is 8 bytes wide, regardless of what it points to. That includes char *, int *, double *, struct Node *, void *, and int **. A pointer variable declared inside a function lives in its function’s stack frame, exactly like any other local.

When you write

int *p = malloc(sizeof(int));

three things happen in order.

1. The stack frame for the current function already has an 8-byte slot reserved for p. It was allocated by adjusting the stack pointer when the frame was built.
2. malloc(4) runs, finds 4 bytes somewhere in the heap, and returns the address of those bytes.
3. That address is written into the 8-byte slot on the stack.

stack frame                         heap
+-----------------+                 +-----------+
|  p : 0x1a2b3c40 |  ------------>  |  (4 bytes)|
+-----------------+                 +-----------+

The arrow is the value p contains: the numeric address of the heap block. &p is a different address (the slot on the stack). *p reads the four bytes at 0x1a2b3c40.

This picture is why free(p); p = NULL; matters. free takes the value in p (the heap address) and returns the block to the allocator. free cannot touch p itself, because C passed free the value, not the slot. If you do not write p = NULL; afterward, the slot still holds 0x1a2b3c40 and any future *p reads a block that no longer belongs to you.

Why pointer variables on the stack can be uninitialized

When a function is entered, its stack frame is built by moving the stack pointer. No code runs to zero the frame. Whatever bytes were there from the previous function call are still there. An uninitialized int *p; local holds those leftover bytes, which look like a valid pointer address. Dereferencing such a pointer is undefined behavior; reads sometimes succeed (by landing on a mapped page), sometimes crash (by landing on an unmapped one), and sometimes silently corrupt an unrelated variable.

Global and static pointers are different. The OS zeroes the .bss segment before main runs, so global int *p; is guaranteed to be NULL at startup.

What malloc actually asks the OS for

malloc does not go to the kernel every time you call it. That would be catastrophically slow. Instead, each process owns an arena: a large region of memory the C library manages internally. malloc carves out a block from the arena; free returns the block to the arena. Only when the arena runs out does the C library ask the kernel for more.

There are two ways the library extends the arena. Both are Linux system calls.

brk / sbrk: extend the data segment

The original Unix interface: the kernel tracks a program break, which is the current top of the data segment. brk(addr) raises the break to addr, growing the heap by the difference. sbrk(n) grows it by n bytes and returns the old break. The resulting memory is contiguous with whatever was already mapped at the top of the data segment.

.data / .bss   [HEAP  -- -- --]   (unmapped)
              ^              ^
              start        break

For small allocations (a few KB at most), glibc’s ptmalloc extends the arena by calling sbrk occasionally, then carves out individual malloc blocks from the extension.

mmap: allocate a fresh virtual region

For large allocations (the glibc threshold is typically 128 KB), malloc bypasses the arena entirely and asks the kernel directly: mmap(NULL, size, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0). The kernel picks a fresh virtual region, backs it with zero-filled pages on demand, and returns the starting address. When you free an mmap-backed block, malloc calls munmap to hand those pages back to the kernel directly.

That is why calloc of a large size is effectively free on Linux: the kernel already zeroes MAP_ANONYMOUS pages, so calloc does not need to memset the result. For small callocs from the arena, the library does run memset because the arena’s bytes are whatever the previous tenant left.

Virtual versus physical memory

The addresses you see in &x and in malloc returns are virtual. The kernel maintains a per-process page table that maps virtual pages to physical pages. When your program writes to a page, the kernel either finds an existing physical page backing it or allocates a fresh one and updates the page table. This is why allocating a huge mmap region is cheap: no physical memory is consumed until you actually write to the pages.

ASLR (Address Space Layout Randomization) makes the kernel pick different virtual starting addresses for the stack, heap, and shared libraries on every run. That is why printf("%p\n", &x); produces a different number each time you invoke your program.

The free list and why free(NULL) is safe

Each arena is organized as a free list: a linked list of blocks the allocator knows are available to hand out. Every free block carries metadata (size, next-free-pointer) in a header that sits immediately before the user-visible bytes. When you call malloc(n), the allocator walks the free list, finds a block big enough, splits it if necessary, and returns a pointer to the user bytes (just past the header).

free-block header          user bytes
[size | prev | next] ---> [  n bytes  ]
                          ^
                          what malloc returns

When you call free(p), the allocator steps back sizeof(header) bytes from p to find the header, reads the size, and re-links the block onto the free list.

Why free(NULL) is a no-op

ISO C §7.22.3.3 says explicitly: “If ptr is a null pointer, no action occurs.” Every conforming library implements this as a first check at the top of free:

void free(void *ptr) {
    if (ptr == NULL) return;
    /* ... rest of the implementation ... */
}

That check is the reason the free(p); p = NULL; discipline defuses double-free. After the assignment, a second free(p) becomes free(NULL), which returns immediately.

Why freeing a non-heap pointer corrupts

If you pass free a stack address, a string literal, or an offset into the middle of a valid block, the allocator steps back sizeof(header) bytes and reads whatever is there, interpreting it as size and next-free-pointer metadata. That “header” is not a real header; it is whatever random bytes happen to live before the pointer you passed. The allocator then re-links a “block” based on garbage metadata, corrupting the free list.

Once the free list is corrupt, future malloc calls can hand out overlapping addresses to two callers, or can walk off into garbage and crash, or can be steered by an attacker into overwriting allocator-maintained function pointers. This is the foundation of heap-exploitation primitives like House of Force and the many CVEs listed in the memory-safety deep dive.

Why double-free has the same failure mode

A double-free re-links an already-free block onto the free list a second time. The list now contains a cycle (or the block appears twice, depending on the allocator). Subsequent malloc calls hand out the same address to two different callers. Both callers write to what they think is their block; neither knows the other exists; the corruption is silent until one of them reads back something the other overwrote.

How Valgrind sees every byte

Valgrind’s memcheck tool is a dynamic binary instrumenter. It reads your compiled binary, translates each machine instruction into an intermediate representation on the fly, and recompiles it with instrumentation injected at every load, store, malloc, free, calloc, and realloc. The instrumented program runs on Valgrind’s synthetic CPU, which is why Valgrind runs your code 20–40× slower than normal.

Shadow memory

Alongside your program’s memory, Valgrind maintains shadow memory: one or two bits for every byte your program can address. The shadow bits record whether each byte is:

• DEFINED: allocated and has been written. Reads are legal.
• UNDEFINED: allocated but never written. Reads are flagged (this is what a fresh malloc block looks like).
• NOACCESS: not currently allocated. Could be outside any heap block, or inside a block that has been freed. Reads and writes are flagged.

Every load your program executes is preceded by a shadow-memory check. Every store updates the shadow bits to DEFINED. Every malloc marks the returned block’s bytes UNDEFINED (or DEFINED for calloc, because calloc zeroes first). Every free marks the block NOACCESS.

real memory:    [ 7][ 3][ 1][ 8][??][??][xx][xx]
shadow:         [ D][ D][ D][ D][ U][ U][ N][ N]

                 written       never      outside
                 bytes         written    any block

A use-after-free bug is caught because free changed the shadow bits to NOACCESS; the next dereference fails the shadow check. An uninitialized-read is caught because the block’s shadow bits are still UNDEFINED from the malloc. An out-of-bounds access is caught because the bytes past the block are NOACCESS.

The full Lab 6 command

gcc -g -O0 -Wall -Wextra -std=c99 -o lab6 cscd240Lab6.c lab6.c
valgrind --tool=memcheck --leak-check=full --show-leak-kinds=all \
         --track-origins=yes ./lab6 &> cscd240lab6val.txt

Flag by flag:

• -g: emit DWARF debug information. Without it Valgrind can print only raw addresses, not file:line pairs.
• -O0: disable optimization. The optimizer may fold, reorder, or delete stores; the mapping between source lines and instructions blurs. At -O0 the mapping is one-to-one.
• --tool=memcheck: select the memory-error detector (the default, but being explicit survives version changes).
• --leak-check=full: at program exit, scan the heap for blocks you never freed and print a stack trace for each.
• --show-leak-kinds=all: report all four leak categories (definitely, indirectly, possibly, still reachable). Without this flag, still reachable is hidden by default.
• --track-origins=yes: when an uninitialized value is read, print a second stack trace showing where the value was allocated. Slow, but essential for finding the real cause of “Conditional jump or move depends on uninitialised value(s)”.
• &>: redirect both stdout and stderr to the file. Valgrind writes to stderr; your program writes to stdout; the deliverable needs both. The POSIX equivalent is > file 2>&1.

What memcheck does not cover

Memcheck is a heap oracle. It does not see stack-array overflows, global-array overflows, integer overflows in arithmetic, data races, or format-string mismatches. Those need other sanitizers:

• -fsanitize=address (AddressSanitizer, ASan): stack + heap + global bounds, use-after-return, use-after-scope. Faster than Valgrind (2–3× slowdown), requires a recompile, cannot be used alongside Valgrind.
• -fsanitize=undefined (UBSan): signed overflow, shift out of range, null deref, and every other ISO-C-defined undefined behavior.
• -fsanitize=thread (ThreadSanitizer, TSan): data races in multithreaded code.
• Compile warnings (-Wall -Wextra -Wformat): format-string mismatches, implicit-function-declaration, dead stores.

A Lab 6 submission only needs Valgrind clean. A production C codebase runs -fsanitize=address,undefined in CI on every commit and treats Valgrind as the periodic deeper check.

The six bug classes, with code

Each of the six classic memory-safety bugs has a minimal code sketch below. These are the shapes Valgrind reports against. The memory-safety deep dive shows the real-world CVEs built on each pattern.

1. Memory leak (CWE-401)

int *p = malloc(sizeof *p);
if (p == NULL) return 1;
*p = 42;
return 0;      /* no free(p). Block is still allocated at exit. */

Valgrind output: definitely lost: 4 bytes in 1 blocks. Fix: free(p); before every return path.

2. Use-after-free (CWE-416, MITRE Top-25 #4)

int *p = malloc(sizeof *p);
*p = 42;
free(p);
printf("%d\n", *p);    /* reads bytes that no longer belong to us */

Valgrind output: Invalid read of size 4 ... Address 0x... is 0 bytes inside a block of size 4 free'd. Fix: free(p); p = NULL; and stop using p after.

3. Double-free (CWE-415)

int *p = malloc(sizeof *p);
free(p);
free(p);               /* corrupts the free list */

Valgrind output: Invalid free(). Modern glibc may also print double free detected in tcache 2 and abort. Fix: set p = NULL; after every free; the second free(p) becomes free(NULL), a no-op.

4. Out-of-bounds read (CWE-125, MITRE Top-25 #7)

int *arr = malloc(4 * sizeof *arr);
/* arr[0..3] are valid */
int x = arr[4];        /* reads the byte past the end */

Valgrind output: Invalid read of size 4 ... Address 0x... is 0 bytes after a block of size 16 alloc'd. Fix: bounds-check the index. Every function that takes a pointer and walks it also takes a length.

5. Out-of-bounds write (CWE-787, MITRE Top-25 #1)

char *buf = malloc(8);
strcpy(buf, "hello, world");   /* 13 bytes into an 8-byte buffer */

Valgrind output: Invalid write of size 1. Fix: size the buffer to the actual string length plus one for the terminator, or use strncpy/snprintf with explicit bounds.

6. Integer overflow at allocation (CWE-190)

size_t n = /* untrusted input */;
int *p = malloc(n * sizeof *p);    /* multiplication can wrap */
for (size_t i = 0; i < n; i++) p[i] = 0;   /* OOB writes follow */

Valgrind does not catch this. The multiplication succeeds in wrapping to a small value; malloc succeeds in returning a small allocation; the subsequent loop is where the OOB writes show up. Fix: use calloc(n, sizeof *p) (the library checks overflow internally) or bound-check n against SIZE_MAX / sizeof *p before the malloc.

Which tool catches which

Valgrind and AddressSanitizer each catch five of the six. Neither catches integer overflow at allocation; that one needs UndefinedBehaviorSanitizer or a manual bounds check.

Takeaways

• A pointer variable is 8 bytes holding a virtual address. The pointer and the thing it points to live in two different places; free can only reach the thing, never the pointer itself.
• malloc and free talk to an in-process arena, not the kernel. The arena extends via sbrk (small) or mmap (large). The kernel’s MMU and page tables make virtual addresses look contiguous to you.
• The free list is a linked structure in heap metadata. Corrupting it (bad free, double free, overflow into an adjacent header) is how shipping software becomes remote code execution.
• Valgrind shadows every byte and flags every illegal access. It catches five of the six classical bug classes; AddressSanitizer catches the same five faster but requires a recompile; integer overflow at allocation needs a separate tool.
• The disciplines from the lessons (sizeof *p, calloc for untrusted sizes, tmp-idiom for realloc, free(p); p = NULL;) are not conventions. They are the minimum set that makes the mechanics above behave.

For the exploit stories that the six bug classes produced in real software, continue to Deep Dive: C Memory Safety.