Systems and hardwareDive 02 of 06
Memory, from malloc to a DRAM cell
Follow one malloc(64) all the way down: the allocator's free lists, virtual addresses and page faults, the page-table walk and the TLB, cache lines, DRAM banks, and the leaking capacitor that finally holds your bit.
- Levels
- 9
- Reading
- 50 min
- Depth
- Idea to Silicon
- Published
char *p = malloc(64);One call, one pointer, 64 bytes. Each layer below gives the same bytes a different name. This dive visits them in order.
- Your program
p = 0x5555555592a0a pointer, eight bytes in a stack frame - glibc malloc
chunk 0x555555559290, size 0x51an 80-byte chunk from tcache bin 3 - Linux kernel
[heap] 555555559000-55555557a000 rw-pa 132 KiB region grown with brk - Page tables
170 · 341 · 170 · 345 · 0x2a0four 9-bit indices and a 12-bit offset - TLB
page 0x555555559 → frame 0x1a7c3one cached translation - CPU caches
lines 0x1a7c3280 and 0x1a7c32c0the 64 bytes straddle two cache lines - DRAM
bank 1, row 0xd3e, byte 0x12a0one slice of an 8 KiB row - Capacitors
512 cellseach one leaks, so each is refreshed every 64 ms
Addresses are what glibc 2.26 to 2.41 (for example 2.39 on Ubuntu 24.04) and Linux on x86-64 produce for a small program run with address randomisation off, as under gdb. From glibc 2.42 the tcache bookkeeping is allocated lazily, so the first malloc(64) returns 0x555555559010 instead. The physical frame and the DRAM coordinates are illustrative: they differ on every machine and every run.
Every value lives somewhere
Here is a small C program. greet builds a string and hands it back to its caller, which prints it and then lets it go.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char *greet(const char *name) {
char tmp[64]; /* lives in greet's stack frame */
snprintf(tmp, sizeof tmp, "hello, %s", name);
char *out = malloc(64); /* lives until someone frees it */
if (out == NULL) return NULL;
strcpy(out, tmp);
return out; /* tmp dies here; *out does not */
}
int main(void) {
char *s = greet("ada");
puts(s);
free(s);
}Every value in it has to be stored somewhere, and each storage place comes with a rule about how long the value lives. The array tmp exists only while greet is running. The 64 bytes from malloc exist from the call until free, no matter which function is running in between. That difference, between storage tied to a function call and storage tied to nothing at all, is the reason memory management exists.
The rest of this dive follows those 64 bytes. We start with the C library function that hands them out and keep descending: the allocator's bookkeeping, the kernel's virtual memory, the hardware that translates each address, the caches that keep copies close to the core, and finally the DRAM chip where each of the 512 bits sits as a little charge on a capacitor.
Three places to put a value
A C program, and nearly any compiled program, keeps its data in three kinds of place. Each one answers the question "when does this value die?" differently.
| Static | Stack | Heap | |
|---|---|---|---|
| Examples | Globals, static locals, string literals | Local variables, arguments, return addresses | Anything from malloc, new, make, Box::new |
| Lifetime | The whole run of the program | Until the function returns | Until it is freed, by you or by a collector |
| Size known | When the program is linked | When the function is compiled, mostly | Only at run time |
| Cost to allocate | Nothing at run time | One subtraction from the stack pointer, per call | A function call and a search through free lists |
| Limit | The binary's size | 8 MiB by default for a Linux main thread (ulimit -s) | Your address space, RAM and swap |
The stack is fast because function calls nest. If main calls greet, then greet returns before main does, so their storage can be handed out and taken back in strict last-in, first-out order. A single register, the stack pointer (rsp on x86-64), marks the boundary. Calling a function moves it down to make room for a The block of stack memory for one function call: its return address, saved registers, local variables and sometimes arguments.; returning moves it back up. Nothing is searched, nothing is tracked.
That same strictness is the stack's limit. A value on the stack cannot outlive the call that created it, and the space has to be small and mostly fixed in size. Step through what happens to greet's data.
Stack grows down from 0x7fffffffffff
main
rsp, the stack pointer, is here
greet
rsp is now here
Heap managed by malloc
0x5555555592a0 64 bytes
uninitialised"hello, ada"
puts reads it here
0x5555555592a0 64 bytes
back on malloc's free list
mainstarts. Its frame on the stack has room fors, which holds whatever bytes were there before.maincallsgreet("ada"). The call pushes a return address and moves the stack pointer down to make room forgreet's locals:tmp,outand a copy ofname. Allocating a whole frame costs one subtraction.snprintfwrites"hello, ada"intotmp, which lives insidegreet's frame.malloc(64)returns 64 bytes that belong to no frame. Their address goes intoout.strcpycopies the string from the stack into the heap block.greetreturns. The stack pointer moves back up, and everything ingreet's frame,tmpincluded, is dead. The heap block is untouched, andsnow holds its address.puts(s)reads the string from the heap. This is why the heap exists: the data outlived the function that made it.free(s)hands the block back.sstill holds the address, but the bytes now belong to the allocator again. Usingsafter this is a use-after-free bug.
The stack gives you storage whose lifetime is a function call. The heap gives you storage whose lifetime you choose, and someone has to keep track of it.
char *greet(const char *name) {
char tmp[64];
snprintf(tmp, sizeof tmp, "hello, %s", name);
return tmp; /* gcc: function returns address of local variable */
}Not every language makes you pick. Go decides for you: its compiler runs escape analysis and moves anything that might outlive its function to the heap, and it starts each goroutine with a tiny stack that grows by copying (the Go concurrency dive shows that machinery). Java and Python put nearly every object on the heap and let a collector find the dead ones. Rust and C++ keep the C model but tie each heap block to an owner whose scope ends the block's life. In every case, the heap is there, and something has to manage it.
Asking for memory
In C the heap is reached through four functions from <stdlib.h>. Their contract is short, and every word of it matters.
malloc(size)returns a pointer to at leastsizebytes, suitably aligned for any built-in type, orNULLif it cannot. The bytes are not initialised. On x86-64 Linux with glibc the pointer is always a multiple of 16, the alignment ofmax_align_t.free(p)gives the block back.pmust have come from one of these functions and must not have been freed already.free(NULL)does nothing.calloc(n, size)allocatesn * sizezeroed bytes, and returnsNULLif that multiplication would overflow.realloc(p, size)resizes a block. It may grow it in place or move it: copy the contents to a new block and free the old one. After a successful call, only the returned pointer is valid.
Notice what is missing. free takes no size. You only hand back the pointer, so the allocator must be able to work out the size from the pointer alone. Also, nothing says the block is exactly size bytes. Ask glibc for 64 and malloc_usable_size(p) reports 72. Both facts fall straight out of how the allocator stores its bookkeeping, which is the next level.
The same 64 bytes in other languages
Higher-level languages hide the call, and most add a rule for when the bytes die. Underneath, the request usually lands in an allocator much like the one we are about to open, or in one the language runtime brings with it.
char *p = malloc(64); /* uninitialised, or NULL on failure */
/* ... */
free(p); /* you decide when, exactly once */auto p = std::make_unique<std::array<char, 64>>();
// operator new -> (in libstdc++) malloc
// freed by the destructor when p goes out of scopelet p: Box<[u8; 64]> = Box::new([0; 64]);
// the global allocator; on Linux, System is glibc malloc
// freed when p's owner drops it; the compiler checks no one uses it afterfunc buf() []byte {
b := make([]byte, 64) // go build -gcflags=-m: "make([]byte, 64) escapes to heap"
return b
}
// runtime.mallocgc; freed by the garbage collector once nothing points to itbyte[] p = new byte[64];
// bump-pointer allocation in this thread's TLAB, zeroed
// reclaimed by the GC; young objects are copied, not freed one by onep = bytearray(64)
# small objects (512 bytes or less) come from pymalloc, not malloc
# freed the moment its reference count drops to zero| Strategy | Who decides the block is dead | Typical bug | Cost you pay |
|---|---|---|---|
| Manual (C) | You, by calling free | Leaks, use-after-free, double free | Your attention; nothing at run time |
| Ownership (C++ RAII, Rust) | The compiler, at the end of the owner's scope | Cycles of shared pointers leak; in C++, dangling references still compile | Learning the rules; a refcount for shared owners |
| Reference counting (CPython, Swift) | The count reaching zero | Reference cycles, unless a cycle collector runs | A counter update on every copy of a reference |
| Tracing GC (Go, Java, JavaScript) | A collector that finds what is still reachable | Leaks through forgotten references; pause or CPU spikes | Extra memory headroom and collector CPU time |
A garbage collector changes who calls free, not whether memory has to be found and reused. Go's runtime, for example, has its own allocator (runtime/malloc.go) that requests memory from the kernel in large pieces and sorts small objects into size classes, much like the allocators in the next level. Java gives each thread a private buffer (a TLAB) and allocates by bumping a pointer through it, which is why new is often cheaper in Java than malloc is in C.
A slice growing
Dynamic arrays are where most programs meet the allocator in a loop. A Go slice, a C++ std::vector and a Rust Vec all keep a pointer, a length and a capacity. When an append finds the length equal to the capacity, the runtime allocates a bigger array, copies every element across and lets the old array go. Growing by a constant factor, rather than by a constant amount, keeps the average cost of an append constant.
Go's runtime.growslice doubles the capacity while it is below 256 elements, then grows by a factor that eases from 2 towards 1.25. It then rounds the byte count up to the allocator's next size class, and keeps whatever the allocator gives it. That second step is why a []int jumps from 512 to 848 elements rather than 832: 832 × 8 = 6,656 bytes, and the nearest size class is 6,784.
- Reallocations
- 0
- Bytes copied
- 0
- Final capacity
- 0
- Unused at the end
- 0
| At length | New cap | Growth rule asks for | Size class gives |
|---|
Inside an allocator
An allocator has two jobs that pull against each other. It must be fast, because programs call it millions of times per second. And it must waste little memory, because whatever it wastes, the program pays for in RAM. This level opens glibc's allocator, ptmalloc2, which is what malloc means on most Linux systems, and then compares it with jemalloc, tcmalloc and Go's runtime allocator.
A chunk: your bytes plus a header
glibc carves the heap into glibc's unit of heap memory: a size field followed by the bytes handed to you. Free chunks also store list pointers inside those bytes.. Each chunk begins with an 8-byte size field, and the pointer you receive points just past it. That is how free learns the size: it reads the 8 bytes before your pointer.
A chunk header is two 8-byte fields, prev_size and size, but an in-use chunk only pays for one of them: its prev_size field is lent to the previous chunk, which may store data there. So for malloc(64) glibc needs 64 bytes plus 8 for the size field, 72, rounded up to a multiple of 16: an 80-byte (0x50) chunk. The smallest possible chunk is 32 bytes. Here are the first bytes of our chunk after greet copies its string in, little-endian as x86-64 stores them:
- prev_sizeOnly meaningful when the previous chunk is free. Otherwise these bytes belong to the previous chunk's data.
- size and flags0x50 = 80 bytes. Bit 0 is PREV_INUSE (the chunk before is in use), bit 1 IS_MMAPPED, bit 2 NON_MAIN_ARENA.
- your 64 bytes, from p"hello, ada" and its terminating zero. The rest of the 64 bytes follow.
The sizes are always multiples of 16, so the low four bits of the size field are free for flags. The same lending works forwards: the 72 usable bytes are the chunk's 64 bytes after its size field plus the next chunk's 8-byte prev_size, which the next chunk only needs while this one is free. That is why malloc_usable_size says 72.
Bins: where freed chunks wait
When you free a chunk, glibc does not give it back to the kernel. It files it in a A list of free chunks of one size, or a range of sizes, so the allocator can find a fitting chunk without scanning the whole heap., so the next request of that size can reuse it. A free chunk's own user bytes are no longer anyone's data, so glibc stores the list pointers right there. There are several kinds of bin, tried in this order for a small request:
| Bin | Holds | Structure | Merged with neighbours? |
|---|---|---|---|
| tcache (since 2.26) | Chunks of 32 to 1,040 bytes, one bin per 16-byte size, at most 7 per bin by default | Per-thread singly linked LIFO, no lock | No |
| Fastbins | Chunks up to 128 bytes by default | Per-arena singly linked LIFO | Not until a consolidation pass |
| Small bins | Chunks under 1,024 bytes, 62 bins of one exact size each | Doubly linked FIFO | Yes, when freed |
| Unsorted bin | Recently freed chunks, any size | One doubly linked list, sorted lazily on the next malloc | Yes |
| Large bins | Bigger chunks, 63 bins covering widening size ranges | Doubly linked, kept sorted by size | Yes |
| Top chunk | The untouched end of the heap | One chunk, grown with brk | Neighbours merge into it |
Our 80-byte chunk maps to tcache bin 3: bins start at 32-byte chunks and step by 16, and (80 − 32) / 16 = 3. So a free followed by another malloc(64) on the same thread is a push and a pop on a per-thread list, a handful of instructions with no lock and no atomic operation.
One version note: the addresses in this dive are those of glibc 2.26 to 2.41, where the per-thread tcache bookkeeping (0x290 bytes) is allocated at the start of the heap before the first chunk. From 2.42 that bookkeeping is allocated lazily, so on newer systems the first malloc(64) returns 0x555555559010 instead. Chunk sizes, the size field 0x51 and the 72 usable bytes are unchanged.
Here is the start of the real path, simplified from malloc/malloc.c:
void *__libc_malloc(size_t bytes)
{
size_t tbytes = checked_request2size(bytes); /* 64 -> 80 */
size_t tc_idx = csize2tidx(tbytes); /* 80 -> bin 3 */
if (tc_idx < mp_.tcache_bins && tcache->counts[tc_idx] > 0)
return tcache_get(tc_idx); /* fast path: no lock */
arena_get(ar_ptr, bytes); /* pick and lock an arena */
victim = _int_malloc(ar_ptr, bytes); /* fastbin, small bin,
unsorted, large, top */
...
}A heap you can poke
The playground below is a 4 KiB heap that follows glibc's rules for chunk sizes, headers and the tcache, with real addresses from our program. To stay readable it folds the fastbins, small, unsorted and large bins into one coalescing free list searched for the best fit. Allocate a few blocks, free some, and watch freed chunks wait in the tcache unmerged. Then turn the tcache off, or press "Fragment the heap", and see free space break into holes.
Chunks (select one to inspect or free it)
Selected chunk
tcache bins (per thread, up to 7 chunks each)
Free list (coalesced, shared)
- Asked for
- 0 B
- Chunks in use
- 0 B
- In tcache
- 0 B
- Free-list holes
- 0 B
- Largest hole
- 0 B
- Top chunk
- 0 B
Fragmentation, the cost of saying yes
The playground shows both kinds of waste. Internal fragmentation is space inside a chunk you did not ask for: 8 bytes of a malloc(64), 15 bytes of a malloc(25). External fragmentation is free memory split into holes too small to use: after "Fragment the heap", more than 1.5 KiB is free, yet a 600-byte request cannot use any of it: the first one comes from the top chunk, and a second one fails.
No allocator can avoid fragmentation completely, because it cannot move your data (your pointers would break) and it cannot know what you will ask for next. It can only choose policies that work well for typical programs: merge neighbours, keep similar sizes together, reuse recently freed memory while it is still in cache. A copying garbage collector is the exception: it can move objects, because it can update every pointer to them, so it compacts the holes away.
Threads, arenas and caches
A single heap with a single lock would serialise every thread that allocates. ptmalloc2 (the "pt" is for pthreads) gives threads separate A complete, independent heap with its own bins, top chunk and mutex. glibc creates up to 8 per CPU core on 64-bit systems.. The main thread uses the main arena, which grows with brk. Each other thread that allocates gets an arena of its own, built in memory from mmap, until there are 8 arenas per core on 64-bit systems; after that, new threads share existing arenas, trying each one's lock in turn. On top of that, each thread has its tcache, which absorbs most small requests without touching any arena.
Thread 1 (main)
tcache 0x50: 2 · 0x110: 1
no lock
Thread 2
tcache 0x20: 7 · 0x50: 1
no lock
Thread 3
tcache empty
no lock
main_arena
fastbins, unsorted bin, 62 small bins, 63 large bins, top chunk
[heap] grown and shrunk with brk
arena 1
the same bins, its own mutex
heaps of up to 64 MiB, reserved with mmap
Other allocators make different trade-offs. The biggest difference is the size class. Instead of one chunk per request with a header, jemalloc, tcmalloc, mimalloc and Go's runtime round each small request up to one of a few dozen fixed sizes and carve whole pages into objects of just one class. With every object on a page the same size, no per-object header is needed: the allocator finds the size by looking up which page the pointer is in. You lose a little to rounding and gain speed and predictability.
| Allocator | Small objects | Thread scaling | Where you meet it |
|---|---|---|---|
| glibc ptmalloc2 | Headers on every chunk, 16-byte granularity, bins and coalescing | Per-thread tcache, multiple arenas | Default malloc on most Linux distributions |
| jemalloc | Size classes spaced four per doubling (…, 64, 80, 96, 112, 128, 160, …) in slabs with a bitmap of free slots | Thread caches, by default 4 arenas per CPU | FreeBSD's libc, many servers via LD_PRELOAD |
| tcmalloc | Size classes in spans of pages, a central free list per class | Per-CPU caches using Linux restartable sequences (the current Google version) | Google's servers, opt-in elsewhere |
| mimalloc | Size classes, with a separate free list for each page | Thread-local heaps; frees from other threads go on a separate list | Microsoft projects, opt-in elsewhere |
| Go runtime | 67 size classes up to 32 KiB, in spans of 8 KiB pages; a special allocator for tiny pointer-free objects | A cache per scheduler P (mcache), then mcentral, then mheap | Every Go program |
An allocator is a bookkeeper for one big region: it trades a little wasted space for speed, and caches freed blocks per thread so the common case never takes a lock.
Virtual memory and the page fault
The pointer 0x5555555592a0 looks like a location in RAM. It is not. Run two copies of greet with randomisation off and both get the same pointer, yet each writes its own string without disturbing the other. Every process has a private The range of addresses a process can use. On x86-64 Linux, 128 TiB for user space with 4-level paging. Each process has its own; the kernel maps each page of it to physical memory, or to nothing., and the hardware translates each address to a physical one on every access, using tables the kernel maintains.
That one level of indirection pays for a lot:
- Isolation. A process cannot even name another process's memory, so a stray pointer can crash only its own program.
- A simple picture. Every program sees a huge, mostly empty, contiguous space starting near zero, whatever the physical memory looks like.
- Laziness. The kernel can promise memory and hand it out only when a page is first touched.
- Sharing. One physical copy of libc can appear in every process, and a file can be mapped so that reading memory reads the file.
Here is the address space of our program while greet runs, roughly as /proc/self/maps would list it. It is not to scale: the empty gaps are terabytes wide.
- 0xffff800000000000
Kernel
The upper half. Mapped in every process, but only reachable in kernel mode.
- 0x0000800000000000
Non-canonical hole
With 48-bit addresses, nothing here exists. Touching it raises a general protection fault, not a page fault.
- 0x7ffffffde000s, tmp, out
[stack]
rw-pThe main thread's stack, 132 KiB to start. It grows down on demand, up to the 8 MiB limit.
- 0x7ffff7fc3000
ld-linux-x86-64.so.2, [vdso], [vvar]
r-xp ...The dynamic loader and the kernel's vDSO.
- 0x7ffff7d8a000
libc.so.6
r--p, r-xp, rw-pglibc, malloc included. Large mallocs and thread arenas are mmapped down here too.
Unmapped
Tens of terabytes of nothing. The mmap area grows down into it, the heap grows up.
- 0x555555559000p = 0x5555555592a0
[heap]
rw-pThe main arena. brk moves its top end. 0x21000 bytes after the first malloc.
- 0x555555558000
greet: .data, .bss
rw-pWritable globals.
- 0x555555556000name
greet: .rodata
r--pConstants. The literal "ada" sits at 0x555555556004.
- 0x555555555000
greet: .text
r-xpMachine code: executable, not writable.
- 0x555555554000
greet: ELF headers
r--pWhere the position-independent program was loaded.
- 0x0
Unmapped, including page 0
The bottom 64 KiB can never be mapped (vm.mmap_min_addr), so a NULL dereference always faults.
Where malloc gets its memory
The allocator gets address space from the kernel in two ways. The old one is the program break: the end of the heap region, moved with the brk system call. glibc's main arena grows this way. On its first call, malloc(64) finds an empty heap, so it asks for what it needs plus a 128 KiB pad, rounded to whole pages: 0x21000 bytes, 132 KiB.
$ strace -e trace=brk,mmap ./greet
...
brk(NULL) = 0x555555559000
brk(0x55555557a000) = 0x55555557a000
hello, adaThe other way is mmap, which asks for a fresh region anywhere in the address space. glibc uses it for thread arenas and for large requests: anything of 128 KiB or more that the free lists cannot satisfy gets its own mapping, which goes straight back to the kernel with munmap on free.
char *big = malloc(1 << 30);
mmap(NULL, 1073745920, PROT_READ|PROT_WRITE,
MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7fffb7dff000
/* 1 GiB plus one page for the chunk header; big = 0x7fffb7dff010 */Promises, not memory
Neither call gives you any RAM. They only change the kernel's list of Virtual memory area: the kernel's record of one mapped range, with its start, end, permissions and what backs it (a file, or anonymous zero-filled memory). /proc/PID/maps prints one line per VMA., the ranges the process may use. Physical memory is attached one page at a time, the first time each page is touched. This is demand paging. Allocate a gigabyte and write to part of it:
char *big = malloc(1 << 30); /* 1 GiB: glibc mmaps it */
memset(big, 1, << 20); /* write the first MiB */- Virtual size (VSZ)
- +1,024 MiB
- Resident (RSS)
- +256 MiB
- Page faults
- 65,536
- Per fault
- 4 KiB
The page fault
What attaches a page is a page fault, and despite the name it is usually not an error. When the hardware finds no valid translation for an address, it stops the instruction and jumps into the kernel. The kernel looks up the address in the VMA list. If the address is inside a VMA and the access is allowed, the fault is the kernel's cue to do its lazy work: allocate a zeroed frame, read a file page, or copy a shared page. It then returns, and the instruction runs again as if nothing happened. If the address is outside every VMA, or the access breaks the VMA's permissions, the kernel sends the process SIGSEGV.
The same mechanism gives fork its speed. A child process starts as a copy of its parent, but copying gigabytes for a child that will immediately call exec would be wasteful. So the kernel shares every page and marks it read-only, and copies a page only when one side writes to it: copy-on-write.
Parent process
[heap] 555555559000-55555557a000 rw-pPTE for page 0x555555559000
not present
frame 0x1a7c3 · present, writable, user
frame 0x1a7c3 · present, read-only, user
store to 0x555555559008
store "hello, ada" to 0x5555555592a0
still reads "hello, ada"
Physical memory
frame 0x1a7c3
all zeros"hello, ada" at +0x2a0
shared by 2
used by 1
frame 0x2b0e1
copy, then "Hello, ada"
#PF · CR2 = 0x555555559008 · error code 0x6: not present, write, user mode
#PF · CR2 = 0x5555555592a0 · error code 0x7: present, write, user mode
Kernel: address is in a writable anonymous VMA, so take a zeroed frame and map it. Return and retry the store.
Kernel: the VMA is writable but the PTE is not, so this is copy-on-write. Copy the frame, remap, retry.
Child process, after fork()
[heap] 555555559000-55555557a000 rw-pPTE for page 0x555555559000
frame 0x1a7c3 · present, read-only, user
frame 0x2b0e1 · present, writable, user
p[0] = 'H'
- The heap has just been extended with
brk. The kernel recorded a new range in the process's list of virtual memory areas, and that is all. No physical memory is assigned and the page table has no entry for this page. - malloc's first store into the region, the size field of the new top chunk at 0x555555559008, makes the MMU walk the page table. The entry is not present, so the CPU raises a page fault, exception 14. It puts the faulting address in register CR2 and pushes an error code describing the access.
- The kernel's fault handler finds the address inside a writable, anonymous VMA. The access is legal, so it takes a free frame, fills it with zeros, writes the page-table entry and returns. The CPU re-runs the store, which now succeeds. This is a minor fault: no disk was involved.
- Our
strcpyintoplands on the same page. The entry is present and writable, so there is no fault at all. Of the heap's 33 pages, only the ones something has written to have frames. fork()creates a child. Instead of copying memory, the kernel copies the page tables, points both at the same frame and clears the writable bit in both entries. The frame now has two users.- The child writes to
p[0]. Its entry is present but read-only, so the CPU faults again. Error code bit 0 is now set: the page was present, and the problem is permission. - The kernel sees a write to a writable VMA through a read-only entry, which means copy-on-write. It copies the 4 KiB to a new frame and maps it writable for the child. The parent's next write will fault too, but the kernel will see that the parent is now the frame's only user and simply make the entry writable again.
A fault that only needs a zeroed frame or an existing page from the page cache is a minor fault: it costs roughly half a microsecond to a few microseconds, mostly entering and leaving the kernel and allocating the page; zeroing the 4 KiB is a small part of it. A major fault has to wait for storage, to read a file page or bring a page back from swap, and costs anything from tens of microseconds on an NVMe drive to milliseconds on a spinning disk. /usr/bin/time -v reports both counts for any command.
WebAssembly engines turn the same machinery into a security feature: they reserve far more address space than a module's memory needs and leave the excess unmapped, so an out-of-bounds access faults instead of needing a software check. The WebAssembly dive shows how those guard pages and signal handlers fit together.
Overcommit
Because memory is promised before it is used, Linux can promise more than it has. The policy is set by vm.overcommit_memory:
| Mode | Rule | What fails, and when |
|---|---|---|
| 0, heuristic (default) | Refuse only requests that obviously cannot fit: roughly, larger than RAM plus swap | Almost every malloc succeeds; if too many promised pages get touched, the OOM killer ends a process |
| 1, always | Never refuse | Even absurd requests like malloc(1 TiB) succeed; failure comes only as OOM kills when pages are touched |
| 2, never | Total commitments may not exceed swap plus overcommit_ratio (default 50%) of RAM | malloc returns NULL up front, so programs can handle it |
So on a default Linux system, checking malloc's return value rarely catches running out of memory. The failure comes later, at a page fault, where no return value can report it. The kernel's out-of-memory killer then picks a victim, guided by each process's oom_score, and sends it SIGKILL.
Allocation reserves addresses; the first touch of each page is what costs physical memory, and the page fault is how the kernel finds out.
Walking the page table
The kernel decides what each virtual page maps to, but it is the CPU's Memory management unit: the part of the CPU that translates virtual addresses to physical ones on every memory access, using page tables and the TLB, and raises a fault when a translation is missing or not allowed. that translates on every single load and store. It needs a map from virtual page numbers to physical frame numbers. With 4 KiB pages and 48-bit addresses there are 236 virtual pages per process. A flat array with an 8-byte entry for each would take 512 GiB per process, almost all of it describing empty space.
x86-64 uses a tree instead: four levels of tables, each exactly one 4 KiB page holding 512 entries of 8 bytes. 512 entries need 9 bits of index, so a 48-bit address splits into four 9-bit indices and a 12-bit offset within the page. A table exists only where something is mapped, so a small process like ours needs only a handful of table pages.
- Register CR3 holds the physical address of the top table, the PML4 (page map level 4). The kernel reloads it on every switch to another process.
- Bits 47–39 pick an entry in the PML4, which points to a PDPT (page directory pointer table).
- Bits 38–30 pick an entry in the PDPT, which points to a page directory.
- Bits 29–21 pick an entry in the page directory, which points to a page table.
- Bits 20–12 pick the page-table entry, the PTE, which holds the physical frame. Bits 11–0 are the byte within it.
The address has 64 bits, but only 48 are translated. The other 16 must be copies of bit 47, which makes the address canonical. That rule splits the space into a lower half for user programs and an upper half for the kernel, with a vast hole between them. Type an address below, or use the presets, then step through the walk.
What is in an entry
Each 8-byte entry holds the physical frame number of the next table, or of the page itself, in bits 51–12, and uses most of the remaining bits as flags. Since frames are 4 KiB-aligned, the low 12 bits of the address are always zero and can be reused.
| Bit | Name | Meaning |
|---|---|---|
| 0 | P | Present. If clear, the CPU ignores the rest and any access faults; the kernel can use the other bits for itself, for example to remember where a page went in swap. |
| 1 | R/W | Writable. Clear for code, read-only data and copy-on-write pages. |
| 2 | U/S | User. If clear, only kernel mode may access the page. |
| 3, 4 | PWT, PCD | Caching policy: write-through, cache disable. Used for device memory. |
| 5 | A | Accessed. Set by the hardware on any access. The kernel clears and samples it to find pages nobody uses. |
| 6 | D | Dirty. Set by the hardware on a write, so the kernel knows a file page must be written back. |
| 7 | PS | Page size. In a page-directory entry, maps a 2 MiB page; in a PDPT entry, a 1 GiB page. (In a PTE, this bit selects the memory type instead.) |
| 8 | G | Global. The translation survives a CR3 reload; used for kernel pages. |
| 12–51 | Frame | Physical address of the next table or of the page, without its low 12 bits. |
| 63 | XD | Execute disable (the NX bit). Set on the heap and stack, so injected data cannot run as code. |
Permissions combine down the tree: an access is allowed only if every entry on the path allows it. That lets Linux keep its upper-level entries permissive and put the real permissions in the leaf.
Huge pages and a fifth level
The walk can stop early. If a page-directory entry has its PS bit set, it maps a 2 MiB huge page directly, and the low 21 bits of the address become the offset. A PDPT entry with PS set maps a 1 GiB page. Huge pages save a level of the walk and, more importantly, cover far more memory per TLB entry, as the next level shows. Linux offers them through transparent huge pages, which the kernel uses automatically for large, aligned anonymous regions, and through hugetlbfs, which reserves them explicitly.
48 bits give each half of the address space 128 TiB, which large servers have started to outgrow. Intel's Ice Lake server processors introduced 5-level paging (LA57), which adds a PML5 table on top, indexed by bits 56–48, for 57-bit addresses: 64 PiB per half, 128 PiB in all. Linux supports it, but by default still hands user programs addresses below the 47-bit line, because some software stores tags in the "unused" upper bits of pointers. A program gets the higher addresses only by passing mmap a hint above that line.
A virtual address is a path through a four-level tree: 9 bits per level because each table is one page of 512 entries, and 12 bits for the byte within the final page.
The TLB and the cost of a miss
The walk you just stepped through takes four dependent memory reads, each needing the previous one's result. If every load and store paid that before doing its real work, memory would be several times slower. It isn't, because the CPU caches translations in the Translation lookaside buffer: a small, fast cache of recent virtual-page-to-physical-frame translations, with their permission bits, checked on every memory access..
A TLB entry maps one virtual page number to one frame number, plus the permission bits. On every access the MMU looks up the page number. A hit gives the physical address with no added delay on a typical core. A miss starts a hardware page walk, and the entry it finds replaces an old one. Like a data cache, a TLB is split into sets and ways, and there are two levels:
| Intel Skylake, for example | 4 KiB pages | 2 MiB pages | 1 GiB pages |
|---|---|---|---|
| L1 data TLB | 64 entries, 4-way | 32 entries, 4-way | 4 entries |
| L2 shared TLB (STLB) | 1,536 entries, 12-way, shared by both sizes | 16 entries | |
Those numbers set the TLB's reach: the amount of memory it can translate without a miss. 64 entries of 4 KiB reach 256 KiB: the same as Skylake's 256 KiB L2, and far smaller than the 1 to 2 MiB L2 of newer cores. 1,536 entries reach 6 MiB. If your working set is bigger and you jump around in it, you take TLB misses on top of cache misses. The same 1,536 entries holding 2 MiB pages reach 3 GiB. Try it:
- Accesses
- 0
- TLB hit rate
- –
- Walks per 1,000 accesses
- –
- TLB reach
- 256 KiB
TLB contents: one row per set, newest way first, showing the low 5 hex digits of each virtual page number
A sequential scan barely notices the TLB: one miss per 4 KiB page, so one in 512 accesses for 8-byte elements. Random access over a large region misses almost every time with 4 KiB pages and almost never with 2 MiB pages once the region fits in the reach. That is why databases, JVMs with big heaps and virtual machine hypervisors care so much about huge pages.
Making misses cheaper
Hardware also softens the misses it cannot avoid. Page walkers read entries through the ordinary data caches, so a recently used page table is often in L1 or L2. And CPUs keep small paging-structure caches of upper-level entries: for nearby addresses, the PML4, PDPT and PD entries are the same, so a typical miss only has to fetch the final PTE.
When translations change
The TLB is a cache of the page tables, and nothing keeps it coherent automatically. When the kernel changes an entry, it must flush the stale translation, on every core that might hold it.
- Context switches load a new CR3. Without help that would empty the TLB every time. With PCIDs (process-context identifiers), each entry is tagged with a 12-bit address-space ID, so entries from several processes can coexist, and kernel pages marked global survive the switch.
- TLB shootdowns. When a multithreaded process calls
munmapormprotect, the kernel interrupts every other core running that process with an inter-processor interrupt so it flushes the entry, and waits for them all. That is why unmapping memory in a busy multithreaded program is far more expensive than mapping it.
The TLB makes translation free when it hits. Its reach, entries times page size, decides whether a big working set pays a page walk on top of every cache miss.
Cache lines, from the programmer's side
With a physical address in hand, the load goes to the caches. The mechanics of a cache, how an address splits into tag, set index and offset and how lines are found and evicted, are the subject of the microprocessor dive's cache level, which has a simulator for exactly that. This level stays on the programmer's side: what caches make fast, what they make slow, and how you can tell.
Three facts carry most of the weight. First, caches move whole lines, 64 bytes on current x86 and most Arm cores; you cannot load one byte from DRAM without bringing its 63 neighbours along. Second, the hierarchy is steep:
| Level | Typical size, per core unless noted | Typical load latency |
|---|---|---|
| L1 data | 32 to 48 KiB | 4 to 5 cycles, about 1 ns |
| L2 | 256 KiB to 2 MiB | 12 to 17 cycles |
| L3 | Tens of MiB, shared | 40 to 80 cycles |
| DRAM | Gigabytes | 80 to 120 ns, hundreds of cycles |
Third, the L1 is usually indexed with address bits that lie inside the page offset, so the cache lookup can start in parallel with the TLB lookup. A 48 KiB, 12-way L1 with 64-byte lines has 64 sets: 6 bits of line offset plus 6 bits of set index is exactly the 12-bit page offset. That constraint is one reason L1 caches grow by adding ways rather than sets.
Our 64 bytes are on two lines
glibc only promises 16-byte alignment, and our block starts at offset 0x2a0 in its page. 0x2a0 is 672, which is 10.5 lines. So the 64 bytes fill the second half of one line and the first half of the next, and the other halves belong to the chunk header and to whatever comes next.
0x1a7c32800x1a7c32c0For most data this does not matter. It matters when a structure is read on every iteration of a hot loop, and when two threads write to neighbouring data, as you'll see below.
See the hierarchy from JavaScript
Caches are invisible to the instruction set but very visible to a stopwatch. The two experiments below run real loops over typed arrays on your own machine. The first shows that the unit of transfer is the line, not the element. The second follows a chain of pointers through a working set that doubles each run; because each load needs the previous result, nothing overlaps, and the time per hop reveals which level of the hierarchy the set fits in.
The stride experiment is the reason "array of structs versus struct of arrays" matters. If a loop reads one 8-byte field from each 64-byte struct, it pays for 64 bytes and uses 8. Storing that field in its own array makes the same loop eight times cheaper in memory traffic. Hardware prefetchers help with regular strides by fetching lines before you ask, but they cannot help with pointer chasing, which is why a linked list is so much slower to walk than an array of the same values.
False sharing
Each core has its own L1 and L2, so the hardware runs a coherence protocol to keep their copies consistent. The usual family is MESI: each cached line is Modified, Exclusive, Shared or Invalid. A core may only write a line it holds in M or E, so to write a line another core has, it must first take it away and invalidate the other copy.
Coherence works per line, not per variable. Two threads that each update only their own counter will still fight if the counters share a line: every write by one core invalidates the other's copy, and the line bounces between them. That is false sharing, and it can make a parallel loop slower than a serial one.
Core 0 L1 data cache
Core 1 L1 data cache
- Increments
- 0
- L1 hits
- 0
- Lines moved between cores
- 0
struct counters { long a; long b; }; /* a and b share a line */
struct padded {
alignas(64) long a; /* C11 <stdalign.h>, or C23 */
alignas(64) long b; /* each on its own line */
};C++17 names the line size as std::hardware_destructive_interference_size, Java has the @Contended annotation, and Go code pads structs with cpu.CacheLinePad from golang.org/x/sys/cpu. Some libraries pad to 128 bytes rather than 64, because Intel's L2 prefetcher fetches lines in adjacent pairs, which can recreate the problem one line over.
Banks, rows and the row buffer
Suppose the load of p[0] misses in every cache. The core's request for line 0x1a7c3280 travels to the memory controller, which sits on the processor die, and from there over a memory channel to the DIMMs. What happens next decides whether the line arrives in 15 nanoseconds of DRAM time or 45.
How a DIMM is organised
A DDR4 channel is 64 bits wide. A typical DIMM fills it with eight chips that each have 8 data pins (the "x8" in a part number), and the eight chips always act together as a rank, receiving the same command. Inside each chip, memory is split into 16 independent banks, arranged in 4 bank groups. A bank is a grid of cells: an 8 Gbit chip has 65,536 rows of 1,024 columns per bank, 8 bits each.
Two numbers fall out of that layout. A row spans 1 KiB in each chip, so 8 KiB across the rank. And DDR4 transfers in bursts of 8, so one read moves 8 transfers × 64 bits = 64 bytes: exactly one cache line, 8 bytes from each chip.
One rank 8 chips side by side on a 64-bit channel, all given the same command
bank group 0
bank group 1
bank group 2
bank group 3
bank 1
65,536 rows × 1,024 columns × 8 bits. The highlighted row is open.
Rows, the row buffer and the three latencies
A bank cannot read a cell directly. It first has to activate a whole row, copying it into the bank's The row of sense amplifiers under a DRAM bank. Activating a row copies it there; column reads and writes then work on the copy until the row is closed with a precharge.. Only then can it read columns from that buffer. Before it can activate a different row, it must precharge, writing the open row back and resetting for the next one. So the memory controller speaks in three commands, each with its own delay:
- ACT opens a row; columns can be read tRCD later.
- RD reads a column; data appears CL (the CAS latency) later.
- PRE closes the row; the bank can be activated again tRP later.
A module labelled DDR4-3200 22-22-22 runs its clock at 1,600 MHz (0.625 ns per cycle; data moves on both edges, hence 3,200 million transfers per second, MT/s) and lists CL, tRCD and tRP in cycles: 22 cycles each, 13.75 ns each. Three cases follow:
| Case | The bank has | Commands | DDR4-3200 22-22-22 |
|---|---|---|---|
| Row hit | The right row open | RD | CL = 13.75 ns |
| Row closed | No row open | ACT, RD | tRCD + CL = 27.5 ns |
| Row conflict | A different row open | PRE, ACT, RD | tRP + tRCD + CL = 41.25 ns |
The simulator below plays these rules over different access streams. It maps physical addresses to banks the simple way, with the 8 KiB row offset in the low 13 bits, the bank in the next 4 and the row above. Real controllers hash many address bits together to spread traffic across channels, ranks and banks, and do not document how; researchers have reverse-engineered the functions for many Intel CPUs.
- Accesses
- 0
- Row hits
- 0
- Row closed
- 0
- Row conflicts
- 0
- Average latency
- –
DDR commands the controller sent, newest first
Our own two lines are the friendly case: the first read finds bank 1 closed and pays for an activation, and the second line is in the same 8 KiB row, so it is a row hit. Streaming is almost all hits. Random access is almost all conflicts. The fourth pattern, two rows of one bank in alternation, is the worst case: every access closes the row the previous one opened. Remember it; it comes back in the next level.
Controllers exploit this. They queue requests and reorder them to serve row hits first (a policy called FR-FCFS), keep rows open while hits are likely, and spread consecutive lines over banks so that one bank's activation overlaps another's data transfer.
Why latency hasn't improved
| Module | Transfer rate | CAS latency | In nanoseconds |
|---|---|---|---|
| DDR3-1600 CL11 | 1,600 MT/s | 11 cycles at 800 MHz | 13.75 ns |
| DDR4-3200 CL22 | 3,200 MT/s | 22 cycles at 1,600 MHz | 13.75 ns |
| DDR5-4800 CL40 | 4,800 MT/s | 40 cycles at 2,400 MHz | 16.7 ns |
Each generation doubles the bandwidth, but the time to get the first bit out of a row barely moves, because it is set by the physics of the cell array, not by the interface clock. DDR5 also splits each DIMM into two independent 32-bit subchannels with bursts of 16, which again delivers 64 bytes per burst. The roughly 80 to 120 ns a program sees for a cache miss is these 15 to 45 ns plus the trip through the cache hierarchy, the on-chip network and the controller's queues.
DRAM is fast at reading from a row that is already open and slow at switching rows, so the order of your accesses matters even after every cache has missed.
A bit in a leaking capacitor
At the bottom of the row buffer are the cells themselves, and each one is about as simple as a memory element can be: one transistor and one capacitor, the 1T1C cell. A charged capacitor is a 1 (in a "true" cell; some cells store the inverse), an empty one a 0. The transistor's gate is connected to a wordline that runs along the row; its other side connects to a bitline shared by every cell in the column. That simplicity is why DRAM is dense and cheap, and every quirk you met in the last level comes from it.
- Precharged. The cell's capacitor holds a 1 as a charge near the supply voltage. Both bitlines sit at half the supply voltage, and the wordline is low, so the access transistor is off and the charge is trapped.
- Activate. The controller's ACT command raises the wordline for row 0xd3e, turning on every access transistor in the row at once. The cell's charge spreads onto the bitline, whose capacitance is several times larger, so the bitline rises only a little above the midpoint.
- Sense. The sense amplifier compares the bitline with its reference and drives the difference to full swing: the bitline goes to the supply voltage, the reference to ground. Thousands of sense amplifiers do this in parallel, and together they are the bank's row buffer.
- Restore. Reading drained the capacitor, so the read was destructive. With the wordline still raised, the full-swing bitline charges the cell back up. This is why a row must stay open for a minimum time (tRAS) before it can be closed.
- Read. A column command connects a few of the sense amplifiers to the chip's data pins. Further reads of the same row only repeat this step, which is why a row hit is cheap.
- Precharge. The PRE command lowers the wordline, isolating the freshly charged cells, and equalises the bitlines back to the midpoint so the bank is ready to open another row.
Two things make this cell different from the SRAM in the caches, which uses six transistors per bit and holds its value as long as it has power. The read is destructive, so every activation ends by writing the row back. And the capacitor leaks.
Refresh
The charge on a cell drains away through the transistor and the surrounding silicon. Most cells keep their value for seconds, but the weakest ones, at high temperature, need help within tens of milliseconds. So the standard requires every row to be refreshed (activated and restored) at least every 64 ms for DDR4, and every 32 ms for DDR5.
| DDR4 | DDR5 | |
|---|---|---|
| Every row refreshed within | 64 ms (32 ms above 85 °C) | 32 ms |
| REF commands per window | 8,192 | 8,192 |
| One REF every (tREFI) | 7.8 µs | 3.9 µs |
| Rank busy per REF (tRFC, 8 Gbit die) | 350 ns | Similar; DDR5 can also refresh one bank at a time |
For DDR4, 350 ns out of every 7.8 µs is about 4.5% of the time spent unable to serve reads, and the share grows with chip capacity, because bigger chips have more rows to refresh in each REF. The leak also has a security side: cooled DRAM can keep its contents for seconds or more after power is cut, which is what "cold boot" attacks on disk-encryption keys exploit.
Rowhammer
Cells are packed so tightly that rows disturb each other. Each activation of a row slightly speeds up the leakage of cells in the rows next to it. Normally refresh restores them long before it matters. But in 2014, researchers from Carnegie Mellon and Intel showed that if a program activates the same row over and over, as fast as the chip allows, cells in the neighbouring rows can lose their charge before their next refresh. They found bit flips in most of the DDR3 modules they tested, with as few as 139,000 activations.
To activate a row repeatedly, an attacker needs exactly the access pattern from the last level's simulator: two rows in the same bank, alternating, so that every access is a row conflict. The caches would normally absorb repeated reads, so the attack flushes the lines with clflush each time, or uses access patterns that evict them. Hammering the rows on both sides of a victim row, double-sided hammering, is the most effective.
A flipped bit in someone else's data is bad. A flipped bit in a page-table entry is worse. In 2015, Google's Project Zero turned Rowhammer into a working exploit: spray memory with page tables, hammer until a bit flips in the frame number of one of your own PTEs, and that entry may now point at a page table. A process that can write its own page tables can map any physical memory, kernel included. Later work did the same from JavaScript in a browser, from Android apps, and over the network through RDMA.
Defences have been an arms race. Doubling the refresh rate halves the window but not the problem, as the 2020 chips in the model show: their threshold fell to around 10,000 activations, far below what an attacker gets in 32 ms. DDR4 chips added target row refresh, a small tracker inside the chip that refreshes the neighbours of rows it sees activated often. In 2020 the TRRespass paper showed that hammering many rows at once overwhelms the tracker. ECC memory corrects single-bit flips and detects double ones, but it too has been defeated with enough flips per word. DDR5 adds refresh management commands, and a 2024 revision of the standard adds per-row activation counters, so the chip can count activations of every row instead of sampling a few.
At the bottom, a bit is a tiny charge that leaks, disturbs its neighbours and is destroyed by every read. Everything above exists to make that look like a fast, private, reliable array of bytes.
End of Memory · 9 levels, Idea to Silicon
Where to next
Next in Systems and hardware · 03 of 06
From gcc main.c to main()
A call begins as five bytes with a hole. Follow a tiny C program through ELF objects, symbol resolution, relocation, the PLT and GOT, and the loader that makes those bytes runnable.
Practical notes
Detect false sharing with a runnable C benchmark
Compare adjacent atomic counters with cache-line-separated counters, then use perf c2c to locate contended lines when PMU access is available.