Skip to main content
Be Bitwise

The Heap

The Stack & The Heap · Memory & Systems track

6 min read

Part ofSystems Programming Companion, week 11

In this module

Memory on Demand

The heap is the region of memory used for dynamic allocation: memory your program asks for at runtime, when it has no idea up front how much it'll actually need. Storing user input of unknown length? Reading a file of unknown size? Building a data structure that grows and shrinks? That memory comes from the heap.

Allocating and Freeing

In C, the standard functions for heap management are:

  • malloc(size) - requests a block of the given size in bytes, returns a pointer to it
  • free(ptr) - releases a previously allocated block back to the heap

Other languages have equivalents. C++ has new/delete, Rust has Box::new, and garbage-collected languages like Java and Python free things for you automatically. Underneath, they're all poking the same heap.

Key Concept

The heap provides dynamic memory allocation at runtime. Programs request memory with functions like malloc and release it with free. Unlike the stack, heap memory persists until explicitly freed (or the process ends).

How the Heap Allocator Works

When your program calls malloc, nothing talks to the hardware directly. A heap allocator (part of the C runtime library) manages a pool of memory and keeps data structures tracking which blocks are free and which are in use. Ask for memory, and the allocator hunts for a suitable free block, marks it as used, and hands you back a pointer. Free it, and the block goes back into the available pile.

The pool itself has to come from the operating system. On Linux, glibc's allocator grows the main heap with the brk system call, which nudges the end of the program's data segment upwards. Very large requests (128 KiB and up by default) skip the heap and get their own pages straight from mmap, which are handed back to the kernel the moment you free them.

Worked Example: Three Allocations and a Free

Here's a short program that makes the allocator's habits visible:

c
char *a = malloc(24);
char *b = malloc(24);
char *c = malloc(24);
printf("a=%p b=%p c=%p\n", a, b, c);
free(b);
char *d = malloc(24);
printf("d=%p\n", d);

On 64-bit Linux with glibc, a typical run prints something like:

text
a=0x5555555592a0 b=0x5555555592c0 c=0x5555555592e0
d=0x5555555592c0

The three blocks sit 0x20 (32) bytes apart, even though each request was for 24. The extra 8 bytes hold a small header in front of each block, recording its size. (glibc's chunk header is formally 16 bytes, but the first 8 of them overlap the end of the previous chunk while that chunk is in use, so each allocation really costs 8. Memory Allocator Internals unpicks that trick.) The allocator also rounds every chunk to a multiple of 16; here 24 + 8 is already 32, so nothing gets added. That header is invisible to your code but it's right there in memory next to your data. Keep that in mind for later.

Then d comes back with exactly the address b used to have. The allocator kept the freed 32-byte chunk on a list and handed it straight back out to the next request of the same size. In glibc that list is the tcache, a small per-thread cache of recently freed chunks sorted by size, and it's the first place both malloc and free look. It's fast and sensible, and it's also the mechanism behind use-after-free attacks: if anything still holds the old pointer b, it now points into d's data.

Predict: what if the last request were malloc(200) instead of malloc(24)?

d would almost certainly get a new address past c. The freed chunk is only 32 bytes, too small for 200, so the allocator carves a fresh chunk from the top of the heap instead. The 32-byte hole stays free, waiting for a request that fits.

Here's the worked example as a program you can run. On glibc it also asks malloc_usable_size how many bytes each block really gives you:

Try itChange SIZE to 20, then to 25, and watch the gap and the usable size.
C (GCC 9.2.0)

With SIZE at 24 you should see 32-byte gaps, a usable size of 24 and d landing on b. At 20 nothing moves: the chunk is still 32 bytes, and the 4 bytes you didn't ask for are the internal fragmentation coming up next. At 25 the chunk jumps to 48 bytes and the usable size to 40. To check your answer to the question above, make only d's request bigger, say malloc(200).

Fragmentation

Over time, as blocks are allocated and freed in different orders, the heap develops fragmentation: many small gaps of free memory scattered between used blocks. Total free space might be plentiful, yet no single gap is large enough for a new allocation. Plenty of empty seats in the theatre, just no two of them next to each other.

TypeDescription
External fragmentationFree memory exists but is split into small, non-contiguous pieces
Internal fragmentationAllocated blocks are slightly larger than requested, wasting space inside the block

The 32-byte hole left by b in the worked example is external fragmentation if nothing small comes along to fill it. Its 24-byte requests happen to show no internal fragmentation at all: 24 bytes of data plus the 8-byte header fill the 32-byte chunk exactly. Those 8 bytes are metadata overhead, a separate cost. Ask for 20 bytes instead and you still get a 32-byte chunk, and the 4 unused bytes inside it are internal fragmentation.

Why the Heap Is Slower Than the Stack

Stack allocation is a single pointer adjustment. Heap allocation has to search free lists, split or merge blocks, and update bookkeeping. Freeing has similar overhead. On top of all that, heap-allocated data is scattered across memory, which destroys cache locality. The heap is flexible and powerful, and you pay for that flexibility every time you call malloc.