Stack vs Heap in C

The idea: two places for data, two lifetimes

A C program keeps its data in two places. The stack holds the local variables of the functions that are running right now. The heap holds blocks the program asked for with malloc. They differ in one question: when does the memory go away? A local goes away when its function returns. A heap block stays until someone calls free.

The page runs small C programs one line at a time on a model of x86-64 Linux with glibc (gcc -O0, ASLR off, so the addresses are the ones gdb shows). The left column is the source. The middle column is the stack, with high addresses at the top. The right column is the heap. A pointer is a line from the stack slot that holds it to the block it points to.

The stack: frames, rsp and rbp

Each thread has its own stack. The main thread's stack starts near the top of the address space and grows down. The register rsp points at its lowest used byte. A call works like this:

1. The caller puts the arguments in registers (rdi, rsi, … in the System V ABI).
2. call pushes the return address: where to continue in the caller.
3. The callee's prologue pushes the caller's rbp and sets rbp = rsp. rbp is the fixed base of the new frame: locals are at rbp-8, rbp-16, …
4. sub rsp, N reserves the space for all locals at once. N is rounded up so rsp stays 16-byte aligned.

Returning is leave; ret: rsp and rbp move back and the CPU jumps to the return address. Nothing is erased. The old frame is just below rsp now (grey on the canvas), and the next call at the same depth reuses the same addresses. That is why a new local that you do not initialise shows the old value ("garbage"). Program 1 calls square twice: the second frame lands on exactly the same bytes.

The same frames on a simpler machine, instruction by instruction, with jal, jr $ra and the MIPS rules for preserved and nonpreserved registers: MIPS Procedure Calls.

Stack allocation costs one subtraction, and freeing costs nothing. The price is the lifetime: a local cannot outlive its function, and the stack is small (8 MiB for the main thread by default, ulimit -s).

The heap: malloc is a library, not a system call

malloc is ordinary code in glibc. It gets big pieces of memory from the kernel now and then, and cuts them into blocks, called chunks:

• A chunk is an 8-byte size field followed by the user's bytes. malloc returns the address 16 bytes after the chunk's start. The size is the request + 8, rounded up to 16, at least 32: malloc(16) and malloc(24) both use a 0x20 chunk, malloc(100) a 0x70 chunk. The lowest bit of the size field, PREV_INUSE, says whether the chunk before it is in use, so 0x21 means "32 bytes, previous in use".
• The first malloc in a process creates the heap: one brk system call moves the end of the data segment up by 132 KiB. glibc puts its own tcache_perthread_struct (0x290 bytes) first, which is why the first pointer you get is 0x5555555592a0. The rest is the top chunk.
• New chunks are cut from the start of the top chunk. When it runs out, brk grows the heap again, by the shortfall + 128 KiB (M_TOP_PAD).
• free usually does not give memory back to the kernel. It puts the chunk in a bin so the next malloc of that size can reuse it. The first stop is the tcache: one list per size, at most 7 chunks, last freed = first reused. Small chunks that do not fit in the tcache go to a fastbin. Larger ones go to the unsorted bin, merged with free neighbours or with the top chunk.
• Requests of 128 KiB or more (M_MMAP_THRESHOLD) skip the heap: each gets its own mmap, and free calls munmap. After such a free, glibc raises the threshold to that size (program 7).

A free chunk is reused for glibc's own bookkeeping. Its first 8 bytes become the fd pointer to the next free chunk, stored as (address >> 12) ^ next (safe-linking, glibc 2.32+). A tcache chunk also gets a key in its next 8 bytes. Program 2 builds a three-node list and frees it: watch p->next get overwritten by the key, and the tcache list come out in reverse order.

A pointer is a value on the stack

struct node *p = make(1); puts two things in memory: 16 bytes on the heap (the node), and 8 bytes on the stack (the variable p, holding the node's address). When make returns, its frame dies, but the node lives on because main still has its address. Copying p copies the address, not the node. free(p) frees the node, but it does not change p. From then on p is a dangling pointer: the canvas draws it red.

Stack vs heap

	Stack	Heap
Who allocates	the compiler: sub rsp, N in the prologue	your code: malloc (glibc), sometimes brk/mmap
Who frees	the return (leave; ret)	your code: free
Lifetime	until the function returns	until free (or exit)
Cost	one instruction, no matter the size	tens of instructions on a tcache hit; a system call when the heap grows
Size limit	8 MiB for the main thread (ulimit -s), often less for other threads	free address space and RAM (+ swap, overcommit)
Shared between threads	no, one stack per thread	yes, one heap (glibc uses several arenas to reduce lock contention)
Overhead per block	none, only alignment	8-byte header, rounding to 16, minimum 32
Fragmentation	none: always the top	free chunks between used ones
Running out	SIGSEGV (stack overflow)	malloc returns NULL (or the OOM killer)
Typical bug	returning &local, overflow	leak, use after free, double free

The classic bugs, and why each one does what it does

• Returning the address of a local (program 4). bad() returns &t. The first *p still reads 7, because nothing has reused the dead frame yet. Then square(5) puts its frame at the same address, r lands on t's slot, and *p reads 25. gcc warns (-Wreturn-local-addr). With optimisation on, it may even return NULL instead.
• Use after free (program 3). After free(a) the chunk is the head of tcache bin 0x20, so the next malloc(16) returns the same address: b == a. Writing through the old pointer a silently changes b's data. There is no crash, so the bug is hard to find.
• Double free (program 6). The second free(p) finds the tcache key in the chunk and the chunk in the bin. glibc prints free(): double free detected in tcache 2 and aborts. Older glibc had no such check: the chunk went into the list twice, and two later mallocs returned the same block.
• Memory leak (program 5). p = malloc(16) in a loop overwrites the only copy of the previous address. The old blocks are still "in use" but nothing reaches them. A leak checker walks the pointers from the stack (and globals) and reports what it cannot reach: definitely lost: 32 bytes in 2 blocks.
• Stack overflow (program 8). Each recurse frame holds a 1 MiB array. After 7 frames the 8th would reach below the 8 MiB limit. The kernel refuses to grow the stack and the process gets SIGSEGV. Program 9 asks for the same 8 MiB with malloc: eight mmaps, no problem.

Tools that catch these: gcc -fsanitize=address (AddressSanitizer: use after free, stack use after return, double free, overflows), valgrind --leak-check=full, and -Wall for the returned local address.

The playground

Pick a size and a variable, then press malloc, free or = NULL. Each press adds one line to a program and runs it. Things to try: free three 0x20 chunks and malloc 16 bytes again (LIFO reuse); free eight chunks of the same size (the 8th goes to a fastbin); malloc 1000, free it, and see it merge back into the top chunk; overwrite a pointer and press Leak Check; free the same variable twice.

See also: Stack vs Heap in Java (the same questions with references and a garbage collector), How Linux Loads a Program (where the stack and brk come from), Linux Virtual Memory (both are just mappings, filled by page faults), The Buddy Allocator (where the kernel's pages come from) and Linux Context Switch (each thread's rsp is saved and restored).

What the page leaves out

ASLR (every run would move the stack, heap and mmap addresses). Optimised code: at -O2 locals live in registers, frames often have no rbp, and leaf functions use the 128-byte red zone below rsp without moving it. Stack canaries (-fstack-protector), alloca and variable-length arrays. Several threads: each gets its own stack (pthread default 8 MiB, mapped with mmap) and glibc gives busy threads their own arenas. The small, large and sorted bins, the fastbin consolidation of big frees, and tcache refills from fastbins. Other allocators (jemalloc, tcmalloc, mimalloc) make different choices.

References

glibc wiki: Overview of Malloc (chunks, arenas, bins, tcache)

System V AMD64 ABI (calling convention, stack frame, red zone)

mallopt(3): M_MMAP_THRESHOLD, M_TRIM_THRESHOLD, M_TOP_PAD

Valgrind Memcheck: memory leak detection