The Memory Hierarchy - Cache, RAM and Virtual Memory

11.0 What this chapter gives you#

1. You will be able to draw the whole memory ladder, from registers down to tape, with real sizes, real waiting times and real prices.
2. You will be able to define temporal and spatial locality and show, with a measured number, why reading an array the wrong way is about nine times slower on the same machine.
3. You will be able to read a memory stick’s label, say what DDR5-6000 CL30 means, and work out its true delay in nanoseconds by hand.
4. You will be able to trace a physical address into channel, rank, bank, row and column, and say why memory delay is a spread of values, not one value.
5. You will be able to translate a real 64-bit virtual address into a physical one, step by step, through four levels of page table.
6. You will be able to tell a minor page fault from a major one and from an invalid one, and give the cost of each in nanoseconds.
7. You will be able to read a real process memory map and name every region in it, including where a memory leak would show up.
8. You will be able to make three specific code changes that gave measured speed-ups of 9.0 times, 8.2 times and 3.5 times on the machine used to write this chapter.

11.1 Why a hierarchy exists at all#

PLAIN11.1.1 in simple words#

1. A computer needs to remember things. Some things it needs right now, some in a moment, some next year.
2. If we could buy one kind of memory that was huge, instant and cheap, there would be no chapter here. We cannot.
3. Memory that answers in under a nanosecond (a billionth of a second) is very expensive per byte and takes a lot of chip space.
4. So engineers build a ladder. Tiny and instant at the top. Huge and slow at the bottom.
5. Almost everything in this chapter is one idea repeated: guess what will be needed soon, and move it up the ladder before it is asked for.

PLAIN11.1.2 a picture in your head#

1. Think of a student studying at a desk.
2. In your hand is one pen. That is a register. You can use it with no delay.
3. On the desk are three open books. That is cache. Reaching one takes a second.
4. On the shelf behind you are two hundred books. That is main memory. You must stand up and walk over.
5. In the university library are two million books. That is the disk. You must walk across campus and wait at a counter.
6. Nobody carries two million books to their desk. Nobody studies with an empty desk either. You keep the right small set close.

Where this comparison breaks: the student decides what to fetch. In a computer the hardware guesses, automatically, with no help from the program. Also, a book on the shelf is still one book. In a computer the same data can exist in four places at once, and keeping those copies agreeing is a real problem that Chapter 10 dealt with under the name cache coherence.

PLAIN11.1.3 a worked example#

1. Take one real machine: the virtual server used to measure every benchmark in this chapter. It runs an Intel Xeon at 2.1 GHz.
2. One clock tick at 2.1 GHz lasts about 0.48 nanoseconds.
3. We measured how long one random memory read takes, for different amounts of data being walked over. Each read had to finish before the next one started, so no overlapping could hide the delay.

4. So the same instruction, load from memory, took anywhere from 1.79 to 179.76 nanoseconds. A factor of 100, decided entirely by where the data was. ### 11.1.4 PLAIN - what is really happening inside

5. Two different physical things are being traded off. Cost per bit, and time to answer.

6. Fast memory uses a circuit called SRAM, which needs six transistors to hold one bit. It holds its value as long as power is on, and answers in one or two clock ticks.

7. Main memory uses DRAM, which needs one transistor and one tiny capacitor per bit. Far smaller, far cheaper per bit.

8. But the DRAM capacitor leaks. Every cell must be read and rewritten thousands of times a second, which is called refresh, and reading it is destructive, so it must be written back.

9. Spinning disks and tape store magnetic patterns, and something physical has to move before you get an answer. Movement is measured in milliseconds. ### 11.1.5 TECHNICAL - the engineer’s version

10. The full ladder, with figures accurate for a mid-2026 desktop or small server. Prices are retail per gigabyte and are unusually high because of the 2025 to 2026 memory shortage.

2. The same ladder priced. Figures dated August 2026, taken from public price trackers. Treat them as approximate and expect them to move.

3. The 2025 to 2026 price situation is worth stating plainly, because it is recent and it distorts every rule of thumb. TrendForce reported DDR5 spot prices rising 307 percent between September and November 2025, driven by AI datacentre demand. A 32 GB DDR5 kit that sold near 95 USD before the shortage was 380 to 589 USD in August 2026.
4. Established fact: the shortage happened and prices roughly doubled to quadrupled. Active forecast, not fact: several analysts expect no meaningful relief before late 2027. Treat that as a prediction.
5. The classic scaling rule, sometimes called the memory wall, is that CPU speed improved far faster than DRAM latency for about thirty years. DRAM bandwidth improved greatly. DRAM latency barely improved at all. Section 11.3 gives the numbers that prove it.
6. Tools that show you the real ladder on your own machine: lscpu and getconf -a on Linux, sysctl -a | grep cache on macOS, and the free Intel Memory Latency Checker for detailed per-level figures.

  smaller, faster, dearer per byte
        ^
        |   registers      < 1 ns      bytes
        |   L1 cache       ~ 1 ns      tens of KB
        |   L2 cache       ~ 5 ns      a few MB
        |   L3 cache       ~ 40 ns     tens of MB
        |   DRAM           ~ 90 ns     tens of GB
        |   NVMe SSD       ~ 60 us     terabytes
        |   hard disk      ~ 8 ms      tens of TB
        v   tape           ~ 60 s      petabytes
  bigger, slower, cheaper per byte

WORDS11.1.6 remember these#

1. Memory hierarchy — the ladder of stores — a multi-level storage system trading capacity against access latency.
2. Latency — the waiting time before data arrives — time from request issue to first data return, measured in cycles or nanoseconds.
3. SRAM — fast memory that needs power — static random access memory, typically a six-transistor cell, no refresh needed.
4. DRAM — cheap main memory — dynamic random access memory, one transistor and one capacitor per cell, requires periodic refresh.
5. Memory wall — CPUs got fast, memory did not — the growing gap between processor cycle time and DRAM access latency.

11.2 Locality: why the whole idea works#

PLAIN11.2.1 in simple words#

1. The ladder only helps if we can guess what a program will want next.
2. Luckily, programs are extremely predictable in two specific ways.
3. First: if a program used something a moment ago, it will very likely use it again soon. That is called temporal locality, meaning locality in time.
4. Second: if a program used something, it will very likely use the thing sitting right next to it. That is spatial locality, meaning locality in space.
5. Because of these two habits, a small fast store holding recently used data and its neighbours will satisfy most requests.
6. Locality is not a law. It is a very strong statistical habit of real code. Code that breaks it runs slowly, and the machine cannot help you.

PLAIN11.2.2 a picture in your head#

1. Picture a cook in a kitchen with a small counter next to the stove.
2. Temporal locality: the salt gets used every two minutes, so it stays on the counter all evening.
3. Spatial locality: when the cook fetches the tin of tomatoes from the store cupboard, they carry the whole tray it sits on, because the other tins on that tray will probably be needed too.
4. Carrying the whole tray is exactly what a computer does. It never fetches one byte from memory. It fetches a fixed-size block, normally 64 bytes, called a cache line.
5. If the cook only ever needs one tin from each of fifty different trays, carrying trays is pure waste, and the evening goes badly.

Where this comparison breaks: the cook knows the recipe in advance. The hardware does not know your program. It uses fixed rules, mainly “keep what was just used” and “fetch the neighbours”. Modern chips also add a prefetcher that spots simple patterns such as “every 64 bytes forward”, but it is a pattern detector, not a mind reader.

PLAIN11.2.3 a worked example#

1. Here is the demonstration everybody should do once. A square grid of numbers, added up two different ways.
2. In C, a two-dimensional array is stored row by row. The whole first row sits in memory, then the whole second row, and so on. That is called row-major order and it is part of the C language definition.
3. Both read exactly the same 16,777,216 numbers and produce the same answer.

double a[4096][4096];          /* 128 MB of doubles */

/* version 1: along the rows, memory order */
for (i = 0; i < 4096; i++)
    for (j = 0; j < 4096; j++)
        s1 += a[i][j];

/* version 2: down the columns, jumping 32 KB each step */
for (j = 0; j < 4096; j++)
    for (i = 0; i < 4096; i++)
        s2 += a[i][j];

4. Measured on the 2.1 GHz Xeon used for this chapter, compiled with gcc -O2, three runs each.

5. So the column version was about nine to ten times slower, on the same data, in the same program, with the same compiler flags.

6. Why. Each row is 4096 doubles, which is 32,768 bytes. Stepping down a column moves 32,768 bytes at a time.

7. A cache line is 64 bytes and holds 8 doubles. Walking a row uses all 8 of them before moving on, so one memory fetch serves 8 additions.

8. Walking a column uses 1 of the 8 and throws the rest away, so it needs 8 times as many fetches. It also touches a new 4 KB page every single step, which wrecks address translation as well. Section 11.6 explains that part. ### 11.2.4 PLAIN - what is really happening inside

9. When the CPU asks for an address, the cache checks whether the 64-byte block containing it is already held.

10. If it is there, that is a hit. If it is not, that is a miss, and the whole 64-byte block is fetched from the level below, and something already in the cache is thrown out to make room.

11. Row order: byte 0 misses, and the fetch brings bytes 0 to 63. The next seven reads all hit. One miss buys eight uses.

12. Column order: byte 0 misses and brings bytes 0 to 63, but the program’s next read is 32,768 bytes away, so the other 63 bytes are never touched before being evicted. Every read is a miss.

13. On top of that, the hardware prefetcher watches the address stream. A forward walk with a small constant step is exactly the pattern it detects, so it starts fetching the next lines before they are asked for. Row order gets that free help. Column order, jumping 32 KB, usually does not. ### 11.2.5 TECHNICAL - the engineer’s version

14. Denning formalized locality as the working set model in 1968, defining the working set W(t, T) as the set of pages referenced in the last T units of virtual time. It remains the standard framework for replacement policy.

15. Effective access time with a two-level model: T_eff = h * T_fast + (1 - h) * T_slow, where h is the hit rate.

16. Put real figures in. With L1 at 1.79 ns, DRAM at 143 ns and a 95 percent hit rate: 0.95 * 1.79 + 0.05 * 143 = 8.85 ns. At 99 percent it is 3.20 ns. At 99.9 percent it is 1.93 ns. The tail dominates, which is why hit rate is quoted to two decimal places.

17. Cache line size is 64 bytes on essentially all x86-64 and on Apple silicon the L1 line is 64 bytes with a 128-byte L2 line. Verify with getconf LEVEL1_DCACHE_LINESIZE on Linux or sysctl hw.cachelinesize on macOS.

18. Row-major storage for multidimensional arrays is a standard, fixed by the C and C++ language definitions. Column-major is the standard in Fortran, MATLAB, R and Julia. NumPy defaults to row-major but supports both through the order argument, so the same loop can be fast or slow depending on how the array was created.

19. The measured 9.0x to 10.4x ratio above is specific to this machine, this array size and this compiler. On a machine with a larger L3 and a smaller array the ratio shrinks toward 1. On a machine with slower DRAM it grows. Do not quote a single universal number.

20. Measure it rather than guess. On Linux:

perf stat -e cache-references,cache-misses,\
LLC-load-misses,dTLB-load-misses ./program

On macOS, use Instruments with the Counters template, or xcrun xctrace.

WORDS11.2.6 remember these#

1. Temporal locality — used once, used again soon — the probability that a referenced address is referenced again within a short interval.
2. Spatial locality — neighbours get used together — the probability that addresses near a referenced address are referenced soon.
3. Cache line — the block that always moves together — the minimum unit of transfer between cache levels, 64 bytes on x86-64 and Arm.
4. Working set — what a program is using just now — the set of pages referenced in a sliding time window, from Denning 1968.
5. Prefetcher — the hardware guesser — a unit that detects address stride patterns and issues loads before the demand request.

11.3 RAM modules in the real world#

PLAIN11.3.1 in simple words#

1. Main memory comes on a green stick you push into a slot on the motherboard. The stick is called a DIMM, short for dual in-line memory module.
2. Laptops use a shorter version called a SO-DIMM, where SO means small outline.
3. A group of chips that answers as one unit is called a rank. A stick can have one rank or two, and a two-rank stick has chips on both sides, or stacked.
4. The motherboard has a small number of paths to memory, called channels. Two channels means two separate roads, not a wider road.
5. Filling both channels roughly doubles how much data per second you can move. It does not shorten the wait for a single item.
6. A label like DDR5-6000 CL30 tells you two things: how many transfers per second, and how many clock ticks you wait for the first one.

PLAIN11.3.2 a picture in your head#

1. Think of a warehouse with numbered aisles, shelves and boxes.
2. A channel is a whole loading dock with its own truck. Two channels means two docks working at the same time.
3. A rank is one full team of workers. Two ranks means two teams that share the dock and take turns, so while one team is putting a pallet away, the other can be fetching.
4. A bank is an aisle. Only one shelf per aisle can be pulled out at a time, but different aisles can be busy at once.
5. A row is one shelf. When a worker pulls a shelf out, it sits on the trolley, and taking more boxes off the same shelf is quick.
6. Adding a second dock doubles throughput. It does not make one single box arrive any sooner. That is the difference between bandwidth and latency, and it is the single most misunderstood thing about RAM.

Where this comparison breaks: shelves in a real warehouse do not forget their contents. DRAM rows do. Reading a row destroys it and it must be written back, and every row must be refreshed every 32 or 64 milliseconds or the data fades away. There is no warehouse equivalent of that.

PLAIN11.3.3 a worked example#

1. Take a common 2026 desktop kit: 2 sticks of 16 GB DDR5-6000, timings written as 30-36-36-76.
2. Those four numbers are, in order, CL, tRCD, tRP and tRAS, all counted in clock ticks.
3. DDR5-6000 means 6000 million transfers per second. DDR means double data rate: data moves on both the rise and the fall of the clock.
4. So the clock itself runs at 3000 MHz, which is 3000 million ticks a second.
5. CL30 means 30 ticks of waiting. 30 x 0.3333 = 10.0 nanoseconds.
6. The general formula, worth memorizing:

true latency in ns = CL * 2000 / data rate in MT/s

7. Now the shock. Apply the same formula across twenty-five years.

8. Transfer rate went up about 60 times. The wait for the first byte went from 22.5 ns to about 10 ns, roughly a factor of two, in twenty-five years.
9. Bandwidth for the kit: 6000 MT/s x 8 bytes per transfer = 48 GB/s per stick. Two sticks in two channels = 96 GB/s.

PLAIN11.3.4 what is really happening inside#

1. A DDR5 stick is 64 data wires wide, but DDR5 splits them into two independent halves of 32 wires each, called sub-channels. DDR4 did not do this.
2. A burst moves 16 transfers in a row on DDR5. On a 32-wire sub-channel that is 16 x 4 bytes = 64 bytes, which is exactly one cache line. The design was chosen to match.
3. Ranks matter because a rank cannot do two things at once. With two ranks the controller can be closing a row on one while reading from the other, which raises useful throughput by roughly 5 to 15 percent in practice.
4. XMP and EXPO are little profiles stored in a small chip on the stick. They tell the motherboard “you may run me at 6000 with these timings”, which is faster than the guaranteed baseline the standard defines.
5. ECC memory adds extra chips holding check bits. If one bit flips, from a cosmic ray or a marginal cell, the controller repairs it and carries on and logs it. If two bits flip, it detects the error and halts rather than returning wrong data.

TECHNICAL11.3.5 the engineer’s version#

1. DDR generations, with JEDEC standard numbers and publication years.

2. JESD79-5C was published on 17 April 2024. Besides extending timings to 8800 MT/s it added PRAC, per-row activation counting, which counts activations at wordline granularity so the system can react to rowhammer-style attacks. It also deprecated PASR, partial array self refresh, on security grounds.
3. DDR5 structural changes against DDR4: two 32-bit sub-channels instead of one 64-bit channel, 32 banks in 8 bank groups instead of 16 banks in 4 groups, 16n prefetch and burst length 16 instead of 8n and BL8, on-die ECC as standard, and the voltage regulator moved onto the module as a PMIC fed from 5 V.
4. On-die ECC is not the same as module ECC. On-die ECC protects the internal DRAM array only. It does not protect the bus between module and CPU. A non-ECC DDR5 stick has on-die ECC and is still not an ECC module.
5. Module ECC is SECDED: single error correct, double error detect. It widens the module from 64 to 72 data bits, 8 check bits per 64 data bits. Linux reports corrected and uncorrected counts through EDAC, readable under /sys/devices/system/edac/mc/ or with edac-util -v.
6. XMP is an Intel convention, not a JEDEC standard. XMP 3.0 arrived with DDR5 in 2021 and provides five profile slots, three vendor-written and two user-writable. EXPO, AMD Extended Profiles for Overclocking, was announced in 2022 alongside Socket AM5 and Ryzen 7000. Both write into the module’s SPD, serial presence detect, chip. Running either is technically operating the part outside its JEDEC-guaranteed bin.
7. LPDDR is a separate family for phones and thin laptops, physically soldered rather than socketed, with lower voltage and aggressive power-down states. JEDEC published the first LPDDR6 standard on 10 July 2025, specifying 10,667 to 14,400 MT/s and a new arrangement of four 24-bit sub-channels, in place of DDR5’s two 32-bit sub-channels, for lower latency and more concurrency.
8. HBM, high bandwidth memory, stacks DRAM dies vertically and connects them with through-silicon vias to a very wide, short bus. JEDEC released JESD270-4, the HBM4 standard, on 16 April 2025: a 2048-bit interface, up to 8 Gb/s per pin, up to 2 TB/s per stack, 32 channels with 2 pseudo-channels each, 4-high to 16-high stacks, and up to 64 GB per stack using 32 Gb dies.
9. CXL, Compute Express Link, adds a third option: memory on the far side of a PCIe-style link. CXL 1.0 and 2.0 built on PCIe 5.0 in 2019 and 2020, CXL 3.0 on PCIe 6.0 in 2022, with 3.1 in 2023 and 3.2 in 2024. Type 3 devices are memory expanders. They add capacity and cost roughly 150 to 250 ns extra latency, so they sit between DRAM and SSD on the ladder.
10. Inspect real modules: sudo dmidecode -t memory on Linux, sudo decode-dimms for raw SPD contents, and system_profiler SPMemoryDataType on macOS.

WORDS11.3.6 remember these#

1. DIMM — the memory stick — dual in-line memory module, a 64-bit-wide printed circuit board carrying DRAM devices.
2. Rank — one full team of chips — a set of DRAM devices sharing a chip-select and responding together to form the full data width.
3. Channel — one road to memory — an independent memory controller port with its own command and data bus.
4. CAS latency — ticks of waiting for the first byte — column address strobe delay in clock cycles, from column command to first data.
5. ECC — memory that repairs itself — error correcting code memory, normally SECDED using 8 check bits per 64 data bits.
6. HBM — memory stacked on the GPU package — high bandwidth memory, a 1024 or 2048-bit stacked DRAM connected by through-silicon vias.

11.4 The memory controller#

PLAIN11.4.1 in simple words#

1. Something has to turn “read address 4,297,318,416” into the right electrical commands on the right wires. That thing is the memory controller.
2. Today it is inside the processor itself, on the same piece of silicon. That change alone removed a large chunk of memory delay.
3. The controller takes an address and splits it into pieces: which channel, which rank, which bank, which row, which column.
4. It also keeps a queue of pending requests and is allowed to serve them out of order, choosing whichever one it can answer fastest.
5. So memory latency is not a number. It is a spread of numbers.

PLAIN11.4.2 a picture in your head#

1. Back to the warehouse. A worker has one shelf pulled out onto the trolley at a time, per aisle.
2. If your box is on the shelf already out, you get it fast. That is a row buffer hit.
3. If the wrong shelf is out, they must push it back in before pulling yours. Slowest. That is a row buffer conflict.
4. The supervisor sees twenty orders at once and deliberately serves all the orders for the shelf already out, before switching. That is scheduling.
5. This is why the same order can take one, two or three times as long, depending purely on what came before it.

Where this comparison breaks: the supervisor cannot delay an order forever. Real controllers have fairness and starvation limits, and they must interrupt everything periodically for refresh, which has no warehouse equivalent. ### 11.4.3 PLAIN - a worked example

1. Take DDR5-6000 with timings 30-36-36-76. Convert to nanoseconds first.
2. CL 30 ticks = 10.0 ns. tRCD 36 ticks = 12.0 ns. tRP 36 ticks = 12.0 ns.
3. Now three cases for one read, at the DRAM chip itself.

4. So the chip alone can answer in 10 ns or 34 ns for identical instructions.

5. Which is why the measured figure in section 11.1 was 143 ns and not 10 ns. Most of the delay is not in the DRAM chip at all. ### 11.4.4 PLAIN - what is really happening inside

6. The controller receives a physical address, for example 0x0001_62B8_D010, and chops the bits into fields. A rough example layout for a two-channel DDR5 system, from the top of the address downward: row bits, then bank group and bank bits, then rank, then channel, then column, then the byte offset inside the burst.

7. The exact chopping is an implementation detail, different on every CPU family, and often deliberately scrambled by XOR-ing bits together.

8. Why scrambled: if consecutive cache lines all landed in the same bank, a simple sequential walk would hit one bank over and over and get no parallelism. Interleaving spreads consecutive lines across channels and banks so they can be served at once.

9. Having chosen a bank, the controller issues ACTIVATE with a row address. That copies the whole row, typically 8 or 16 kilobits, into the sense amplifiers, which form the row buffer.

10. If it needs a different row in that bank, it must first issue PRECHARGE, which writes the buffer back into the cells and clears the sense amps.

11. The scheduler picks among queued requests. The classic policy is FR-FCFS, first-ready first-come-first-served: prefer any request that hits an open row, otherwise take the oldest.

TECHNICAL11.4.5 the engineer’s version#

1. History. AMD integrated the memory controller onto the CPU die with the Athlon 64, launched September 2003. Intel followed with Nehalem in November 2008, retiring the front-side bus. Before that, every memory access crossed a separate northbridge chip.
2. Consequence: memory latency became a property of the CPU, and multi-socket machines became NUMA, non-uniform memory access, where local DRAM is faster than DRAM attached to another socket. Typical remote penalty is 1.4x to 2.2x on latency. Inspect with numactl --hardware and lstopo.
3. Key DDR timing parameters, and what each one blocks.

4. Row buffer hit rate on real workloads is commonly 20 to 60 percent for general code, and much higher for streaming loops. It is a first-order term in memory performance, and it is why address interleaving schemes are tuned so carefully.
5. Latency is a distribution. On a loaded server, measured DRAM read latency commonly runs 75 ns at the median and 300 ns or worse at the 99th percentile, because queueing delay grows sharply as utilization approaches the bandwidth limit. This follows ordinary queueing theory: as utilization goes to 1, queue length goes to infinity.
6. Tools: Intel Memory Latency Checker prints a full loaded-latency curve. perf stat -e uncore_imc/cas_count_read/ gives DRAM traffic on Intel. pcm-memory from Intel PCM shows per-channel bandwidth live. On AMD, use amd_uprof.
7. Rowhammer is the security consequence of all this. Repeatedly activating one row disturbs charge in neighbours, and since the 2014 Kim et al. paper it has been a real attack. Mitigations include target row refresh, and from JESD79-5C in 2024, PRAC.

WORDS11.4.6 remember these#

1. Memory controller — the part that talks to the sticks — the integrated circuit block that translates addresses into DRAM commands and schedules them.
2. Row buffer — the shelf currently pulled out — the sense amplifier array holding one open DRAM row, typically 1 to 2 KB per device.
3. Row hit — asking for something already open — a column access to the currently activated row, costing only tCL.
4. Bank conflict — the wrong row is open — an access requiring precharge then activate before the column read, costing tRP + tRCD + tCL.
5. NUMA — some memory is further away — non-uniform memory access, where latency depends on which socket owns the DRAM.

11.5 The address space#

PLAIN11.5.1 in simple words#

1. An address is just a number that names a location. Nothing more.
2. If addresses are 64 bits, there are about 18.4 quintillion of them.
3. Every program believes it has the whole range to itself, starting near zero, with nobody else in it. That belief is a carefully maintained lie.
4. The addresses a program uses are virtual addresses. They are private invented numbers.
5. The addresses on the actual wires to the memory sticks are physical addresses. There is exactly one set of those in the machine.
6. This is why one program cannot read another’s data by guessing. Its numbers simply do not refer to the same places.

PLAIN11.5.2 a picture in your head#

1. Think of a large office building where every company has its own internal room numbering: Room 1, Room 2, Room 3.
2. Three companies all have a Room 1. They are three different physical rooms.
3. At every door there is a translator holding a small book: “for this company, Room 1 means B4-102”.
4. If a company asks for Room 9 and the book has no entry, the translator refuses to open anything and reports it.
5. Two companies can share a meeting room by both having book entries pointing at the same physical room. That is shared memory.

Where this comparison breaks: the translation happens billions of times a second, in hardware, in about a nanosecond when cached. And the book is not one book but a tree of books, which is section 11.6. ### 11.5.3 PLAIN - a worked example

1. Run two copies of the same program at the same time. Print the address of a variable in each.
2. Either way, neither number is a real place in the memory sticks.
3. Here are the real virtual addresses printed by a small test program on the Linux machine used for this chapter.

big heap block  at 0x7f19b4bff010
small heap block at 0x55a23da282a0

4. The big block sits high, around 0x7f19…, because a large allocation is served by a fresh mapping in the middle of the address space.

5. The small block sits lower, around 0x55a2…, in the classic heap area just above the program’s own code. ### 11.5.4 PLAIN - what is really happening inside

6. Nothing in the CPU has 64 real address wires going to memory. That would be both useless and expensive.

7. Current x86-64 processors implement 48 bits of virtual address, extended to 57 bits on newer server parts. The rest of the bits are required to be copies of the top implemented bit.

8. An address obeying that rule is called canonical. A non-canonical address causes a fault immediately, before any translation is attempted.

9. So the usable space splits into two lumps: one at the very bottom starting at zero, and one at the very top ending at all ones. The vast middle is a hole.

10. The machine used for this chapter reports 52 bits of physical address and 57 bits of virtual address, which you can read with lscpu. ### 11.5.5 TECHNICAL - the engineer’s version

11. x86-64 canonical form is a standard, defined by the architecture. With 48-bit addressing, bits 48 to 63 must all equal bit 47. With LA57 enabled, bits 57 to 63 must all equal bit 56.

12. Address space sizes:

3. Intel published the 5-level paging specification in 2016, submitting Linux patches on 8 December 2016. Support landed in Linux 4.14 and was enabled by default in Linux 5.5. Hardware support arrived with Ice Lake server parts, and AMD supports it on EPYC 9004 and 8004 and Threadripper PRO 7000 WX. It is switched on by bit 12 of CR4, named LA57.
4. Standard Linux x86-64 split with 4-level paging:

5. That gives 128 TiB to user space and 128 TiB to the kernel. With LA57 both become 64 PiB. A process only gets the larger space if it explicitly asks, by passing an mmap hint above 47 bits, so that old programs storing tag bits in the top of pointers do not break. That compatibility hack is a real and current design decision, not history.
6. Observe the layout of any Linux process with cat /proc/PID/maps. On macOS use vmmap PID. On Windows use VMMap from Sysinternals.

The honest version: “programs never see physical addresses” is a simplification. The kernel routinely works with them, drivers must hand real physical addresses to devices doing direct memory access, and many small embedded microcontrollers have no MMU at all, so every address is physical. The accurate statement is that user-space code on a general-purpose operating system with an MMU sees only virtual addresses.

WORDS11.5.6 remember these#

1. Address — a number naming a location — an index into an address space, 64 bits wide on modern general-purpose CPUs.
2. Virtual address — the private number a program uses — the address produced by the program, subject to MMU translation.
3. Physical address — the real number on the wires — the address presented to the memory controller after translation.
4. Canonical address — an address with a legal top half — one whose unused high bits are sign-extended copies of the highest implemented bit.
5. LA57 — the switch for 57-bit addressing — CR4 bit 12, enabling 5-level paging and a 128 PiB virtual space.

11.6 Virtual memory, explained slowly#

PLAIN11.6.1 in simple words#

1. The machine cannot keep a note for every single byte saying where it really lives. That table would be bigger than the memory itself.

2. So memory is cut into fixed-size blocks called pages. The usual size is 4 kilobytes, which is 4096 bytes.

3. Now the note only has to say “virtual page 17 lives in physical frame 90210”. One entry covers 4096 bytes.

4. The collection of those notes is the page table, and every process has its own.

5. The hardware unit that does the lookup is the memory management unit, or MMU. It sits between the core and the caches.

6. Looking up a table in memory on every access would be hopeless, so the MMU keeps a small very fast cache of recent translations, called the translation lookaside buffer, or TLB. ### 11.6.2 PLAIN - a picture in your head

7. Imagine a huge hotel with a million rooms and a guest list.

8. A flat guest list with one line per room would be a book of a million lines, which you would have to carry everywhere.

9. Instead the hotel uses a tree. One thin card lists the buildings. Each building has a card listing floors. Each floor has a card listing corridors. Each corridor has a card listing rooms.

10. To find a guest you read four cards. But you only need cards for parts of the hotel that actually have guests.

11. The receptionist remembers the last few guests they looked up and answers those instantly without touching any card. That is the TLB.

Where this comparison breaks: the tree is walked by hardware, in silicon, not by anyone reading. And a missing card does not mean “no such guest”. It can mean “that guest is out, fetch them from storage”, which is a page fault. ### 11.6.3 PLAIN - a worked example

1. This is a real translation, measured on the Linux machine used for this chapter by reading /proc/self/pagemap as root.
2. The virtual address was 0x7f1e1a9ff010. On x86-64 with 4-level paging, a 64-bit address is chopped like this:

 bits 63..48  must copy bit 47   (canonical check)
 bits 47..39  index into level 4 table  (PML4)
 bits 38..30  index into level 3 table  (PDPT)
 bits 29..21  index into level 2 table  (PD)
 bits 20..12  index into level 1 table  (PT)
 bits 11..0   byte offset inside the 4 KB page

3. Each index is 9 bits, so each table has 2^9 = 512 entries. Each entry is 8 bytes, so each table is exactly 512 x 8 = 4096 bytes: one page. That is not a coincidence, it is the design.
4. Chopping 0x7f1e1a9ff010 gives:

5. The walk: read entry 254 of the level 4 table to get the address of a level 3 table. Read entry 120 of that to get a level 2 table. Read entry 212 of that to get a level 1 table. Read entry 511 of that to get the frame number.
6. Physical address = frame number x 4096 + offset = 0x162B8D000 + 0x10 = 0x162B8D010.
7. Now look at the next two pages of the same allocation, which are next to each other in virtual space:

8. Three pages that are neighbours in the program’s view live in three scattered, unrelated places in the actual memory chips. ### 11.6.4 PLAIN - what is really happening inside

9. A register in the CPU holds the physical address of the top-level table. On x86-64 it is called CR3. On Arm64 it is TTBR0 and TTBR1.

10. Switching from one process to another means, at heart, writing a new value into that register. Everything the old process could reach becomes unreachable in one instruction.

11. On every memory access the MMU first asks the TLB. If the translation is there, done, no table reading at all.

12. If it is not, the hardware itself walks the tree. On x86-64 that is done by a hardware page walker, with no software involved and no interrupt.

13. Each entry it reads is 64 bits and carries more than an address. It carries flag bits: present, writable, user-accessible, accessed, dirty, and no-execute.

14. If the present bit is 0, the walker gives up and raises a page fault, which is an exception handled by the operating system. Section 11.7 covers what the operating system does next.

15. On success the translation is written into the TLB, and a few clock ticks later the data arrives. ### 11.6.5 TECHNICAL - the engineer’s version

16. Page size 4096 bytes is a convention so widespread it feels like a standard, but it is not universal. It came from the VAX-11/780 in 1978 and was carried into x86 in 1985 with the 80386. Apple silicon uses 16 KB pages on macOS and iOS. Confirm with getconf PAGE_SIZE, which prints 4096 on x86-64 Linux and 16384 on an Apple silicon Mac.

17. Historical note worth knowing: the first machine with what we now call virtual memory was the Atlas, built by a joint University of Manchester and Ferranti team led by Tom Kilburn, and inaugurated in December 1962. They called it the one-level store. It had a 16,000 word core store and a 96,000 word drum, a block size of 512 words, and a replacement policy called the learning program that estimated reuse cycles per page and evicted the one predicted to be needed furthest in the future.

18. Page table levels on x86-64:

4. Page table entry layout on x86-64, 64 bits wide:

5. TLB structure on recent parts. AMD Zen 4 has a 72-entry fully associative L1 data TLB and a 3072-entry L2 data TLB. Intel Golden Cove has a 96-entry L1 data TLB and a 2048-entry shared L2 TLB. Figures for Zen 5 were not fully published at the time of writing, so treat any specific number for it as uncertain.
6. TLB reach, meaning how much memory the TLB can cover at once, is the number that matters:

7. Measure TLB behaviour with perf stat -e dTLB-load-misses,dtlb_load_misses.walk_active ./prog on Linux. Correlate with perf stat -e page-faults.
8. Every virtual machine adds a second layer. The guest’s page tables map guest virtual to guest physical, and a second set, called extended page tables on Intel and nested page tables on AMD, maps guest physical to host physical. A full nested walk can require up to 24 memory accesses on a 4-level by 4-level system, which is why the measured latencies in this chapter, taken inside a virtual machine, are higher than bare metal.

  virtual address 0x7f1e1a9ff010
        |
        |  CR3 -> level 4 table
        +--> [254] --> level 3 table
                 +--> [120] --> level 2 table
                          +--> [212] --> level 1 table
                                   +--> [511] --> frame 0x162B8D
                                                     |
        physical address = 0x162B8D000 + 0x010 ------+
                         = 0x162B8D010

WORDS11.6.6 remember these#

1. Page — a fixed block of a program’s memory — the unit of virtual to physical mapping, normally 4 KB, or 16 KB on Apple silicon.
2. Frame — a fixed block of real memory — a physical page-sized region of DRAM, identified by a page frame number.
3. Page table — the map from pages to frames — a radix tree of 512-entry tables walked by hardware.
4. MMU — the translator — memory management unit, the hardware performing address translation and permission checks.
5. TLB — the translator’s memory of recent answers — translation lookaside buffer, a small associative cache of page table entries.
6. CR3 — where the map starts — the x86-64 control register holding the physical address of the top-level page table; TTBR0 and TTBR1 on Arm64. ## 11.7 Paging and swapping

PLAIN11.7.1 in simple words#

1. A page fault is the hardware saying “I cannot translate this address, you deal with it”. Control jumps into the operating system.
2. That is not an error. It is the normal way memory gets allocated, and there are three kinds, which you must be able to tell apart.
3. A minor fault means the data is already in RAM somewhere, and the kernel only has to write a page table entry. Fast: microseconds.
4. A major fault means the data must be read from disk first. Slow: tens to thousands of microseconds.
5. An invalid fault means the address is genuinely not yours. The program is killed, with a message like segmentation fault.
6. When RAM runs short, the kernel writes some pages out to disk and takes the RAM back. That is swapping.
7. If it has to keep bringing them straight back, the machine spends all its time moving pages and none doing work. That is thrashing, and it is why a full machine feels frozen rather than merely slow.

PLAIN11.7.2 a picture in your head#

1. Picture a small desk and a big filing cabinet behind you.
2. A document that is in the room but under a pile: you find it in a second. That is a minor fault.
3. A document in the cabinet: you stand, walk, open a drawer, search. That is a major fault, and it takes a thousand times longer.
4. Now imagine the desk holds four documents but the task needs five, and you cycle through all five over and over.
5. Every single step needs a trip to the cabinet, and you also have to file something away first to make room. You get nothing done.
6. Adding a bigger desk fixes it completely. Adding a faster cabinet barely helps.

Where this comparison breaks: the desk in a computer is also full of documents nobody asked for, kept just in case, which the kernel will silently throw away the instant they are needed. That is the page cache, and it is why “free memory” is such a misleading measurement.

PLAIN11.7.3 a worked example#

1. Here are real numbers measured for this chapter, on the same 2.1 GHz Linux virtual machine.
2. A program mapped 512 MB of anonymous memory and wrote one byte in each 4 KB page, then wrote one byte in each page again.

3. So a minor page fault cost about 100 times as much as a plain memory write.
4. 131,155 - 83 = 131,072. And 512 MB / 4 KB = 131,072. One fault per page, exactly.
5. Second experiment, showing that a promise is not memory:

at start            VmSize =    2.6 MB   VmRSS =    1.4 MB
after malloc 4 GB   VmSize = 4098.6 MB   VmRSS =    1.7 MB
after touching 1 GB VmSize = 4098.6 MB   VmRSS = 1025.7 MB
after touching 4 GB VmSize = 4098.6 MB   VmRSS = 4097.7 MB

6. Asking for 4 GB moved resident memory by 0.3 MB. The memory appeared only when it was written to.

7. Now put a cost on a major fault. A minor fault is about 2 microseconds. A read from an NVMe SSD is about 60 microseconds. A read from a hard disk is about 8 milliseconds.

8. So one major fault to SSD costs roughly 30 minor faults. One major fault to a hard disk costs roughly 4,000 minor faults, or about 90,000 ordinary memory writes. ### 11.7.4 PLAIN - what is really happening inside

9. When you call malloc for a large block, the C library asks the kernel for a mapping. The kernel records “this range of addresses belongs to you” in a list of regions, and stops there.

10. Your first write to that region raises a page fault. The kernel finds a free physical frame, fills it with zeros for safety, writes the page table entry, and returns to the exact instruction that faulted, which now succeeds.

11. Reading a file works the same way. The kernel keeps recently used file contents in RAM in the page cache. If your fault can be satisfied from the page cache, it is minor. If not, real disk input starts and it is major.

12. When free memory gets low, a kernel thread scans and reclaims. It has two easy sources: clean file pages, which can simply be dropped because the copy on disk is identical, and clean anonymous pages, which are rare.

13. Dirty pages must be written first. File pages go back to their file. Anonymous pages have no file, so they go to swap: a dedicated partition or a file, called the page file on Windows.

14. Before writing anything out, modern systems try compressing instead. Squeezing three pages into one costs microseconds of CPU and saves milliseconds of disk. ### 11.7.5 TECHNICAL - the engineer’s version

15. Fault taxonomy in the terms the tools use:

2. Copy-on-write faults are minor but not cheap. Measured on this machine, a process with 1 GB resident forked, and the child then wrote every page: about 16 microseconds per page, against about 2 microseconds for a plain first-touch fault. That gap is larger than on bare metal because nested paging in a virtual machine makes TLB invalidation expensive. Treat 16 microseconds as this machine’s figure, not a universal one.
3. Overcommit is a policy, not a law. Linux exposes it through /proc/sys/vm/overcommit_memory: 0 is heuristic and the default, 1 always allows, 2 enforces a strict limit set by overcommit_ratio. With the default, malloc of more memory than you have usually succeeds.
4. Memory compression, with dates:

5. macOS compressed memory was introduced in OS X 10.9 Mavericks, announced June 2013 and released October 2013, using the WKdm family of fast dictionary compressors. Typical ratio on real workloads is around 2 to 1. zswap and zram commonly use LZO or LZ4 and report similar ratios.
6. Reading memory pressure on macOS. Activity Monitor’s Memory tab shows a Memory Pressure graph, which is driven by the kernel’s own pressure state, not by free memory. Green means fine. Yellow means reclaim is working hard. Red means applications are about to be terminated. On the command line:

vm_stat 1                 # page-level counters, 4096-byte units
memory_pressure           # prints the current pressure level
top -l 1 -s 0 -n 0        # PhysMem and compressor lines
footprint -p PID          # per-process accounting, macOS 11+

7. Reading memory pressure on Linux:

free -m                   # the -/+ buffers view, and available
vmstat 1                  # watch si and so: swap in and out per s
cat /proc/meminfo         # everything, in kB
cat /proc/pressure/memory # PSI: some/full stall percentages
sar -B 1                  # pgpgin, pgpgout, majflt per second

8. On free -m, the column to trust is available, not free. On the machine used here: total 8023 MB, used 773 MB, free 6573 MB, buff/cache 910 MB, available 7249 MB. Available exceeds free because most of buff/cache can be reclaimed instantly.

9. Pressure Stall Information, added in Linux 4.20 in December 2018, is the best single signal. /proc/pressure/memory gives the percentage of time tasks were stalled waiting on memory. A full average above a few percent means real trouble, long before free memory looks alarming. ### 11.7.6 WORDS - remember these

10. Page fault — the hardware asking the kernel for help — an exception raised when translation or permission check fails.

11. Minor fault — fixable without disk — a fault resolved by mapping an existing or newly zeroed frame.

12. Major fault — needs disk input — a fault requiring a read from a file or from swap before it can be satisfied.

13. Demand paging — nothing until you touch it — allocating physical frames lazily on first access rather than at request time.

14. Page cache — file contents kept in spare RAM — the kernel cache of file pages, reclaimable on demand.

15. Swap — RAM contents parked on disk — backing store for anonymous pages; called the page file on Windows.

16. Thrashing — all paging, no progress — a state where the working set exceeds RAM and nearly every access faults. ## 11.8 Huge pages, memory protection and isolation

PLAIN11.8.1 in simple words#

1. A 4 KB page is small. A program using 64 gigabytes needs 16 million translations.

2. The translator’s fast memory, the TLB, holds only a couple of thousand. So big programs miss constantly.

3. The fix is bigger pages. On a normal PC you can have 2 megabyte pages and 1 gigabyte pages.

4. One 2 MB page replaces 512 small ones, so the same TLB now covers 512 times as much memory.

5. Separately, every page carries permission flags: may be read, may be written, may be executed as code.

6. A sane rule is that a page is never both writable and executable at once. That is called W xor X, written W^X.

7. Programs are also loaded at a different random address every run, so an attacker cannot know where anything is. That is address space layout randomization. ### 11.8.2 PLAIN - a picture in your head

8. Think of a warehouse index card system again. Small pages are like indexing every single box.

9. Huge pages are like indexing whole pallets. Far fewer cards, so the whole index fits in your pocket.

10. Permissions are like signs on a room: READ ONLY, NO ENTRY, STAFF ONLY.

11. W^X is the rule “a room may be a workshop or a library, never both”. An attacker who sneaks a fake instruction into a data room finds it cannot be executed there.

12. Randomization is renumbering all the rooms every morning. A burglar with yesterday’s map is lost.

Where this comparison breaks: the signs are checked by hardware on every single access, in parallel with the lookup, so they cost nothing. No human system can check every action for free. ### 11.8.3 PLAIN - a worked example

1. Measured on this machine: a random pointer chase over 512 MB, once with ordinary 4 KB pages and once with transparent huge pages of 2 MB.

2. The speed-up was 1.25 to 1.30 times. Not enormous, but free, on a workload the CPU was already handling as badly as possible.
3. The arithmetic behind it. A 2048-entry TLB with 4 KB pages covers 2048 x 4 KB = 8 MB. With 2 MB pages it covers 2048 x 2 MB = 4 GB.
4. Now the permission side. Read a real memory map. Note the last column of letters:

55a209398000-55a209399000 r--p   /tmp/mb/maps2
55a209399000-55a20939a000 r-xp   /tmp/mb/maps2
55a20939a000-55a20939b000 r--p   /tmp/mb/maps2
55a20939c000-55a20939d000 rw-p   /tmp/mb/maps2
55a23da28000-55a23da49000 rw-p   [heap]
7f19b8c28000-7f19b8db0000 r-xp   libc.so.6
7ffd3da2b000-7ffd3da4d000 rw-p   [stack]

5. Every single region is either r-x or rw-. Not one is rwx. That is W^X being enforced, visible in one command.

PLAIN11.8.4 what is really happening inside#

1. A huge page is not a special kind of memory. It is the page walk stopping early.

2. Normally the level 2 entry points at a level 1 table. If its page-size flag is set, the walker treats it as pointing directly at a 2 MB region and stops. One less level, one less table, one TLB entry for 2 MB.

3. There are two ways to get them. Reserved pools, where you set aside a fixed number at boot and programs must ask explicitly. And transparent huge pages, where the kernel promotes ordinary allocations automatically and quietly.

4. The no-execute flag is bit 63 of a page table entry. When set, any attempt to fetch an instruction from that page faults.

5. Isolation needs no extra machinery. Process A’s page table has entries for A’s frames. Process B’s has entries for B’s. There is no address A can name that reaches B’s memory, because a name is only meaningful through A’s own table. ### 11.8.5 TECHNICAL - the engineer’s version

6. Page sizes by architecture:

2. Apple silicon Macs and iOS devices use the 16 KB granule. getconf PAGE_SIZE returns 16384 there and 4096 on x86-64 Linux. Android has been moving apps and libraries to 16 KB page alignment since 2024 for the same reason. Support for 1 GB pages on x86-64 is reported by the pdpe1gb CPU flag in /proc/cpuinfo.
3. Two mechanisms on Linux, and they behave very differently:

# transparent huge pages: automatic, best effort
cat /sys/kernel/mm/transparent_hugepage/enabled
# prints e.g.  always [madvise] never
madvise(p, len, MADV_HUGEPAGE);   # opt in from code

# hugetlbfs: reserved, guaranteed, never swapped
echo 512 > /proc/sys/vm/nr_hugepages
grep -i huge /proc/meminfo
mmap(..., MAP_HUGETLB | MAP_HUGE_2MB, ...);

4. Where huge pages help most: large in-memory databases, JVM heaps, HPC working sets, and virtual machine guest memory, where they cut nested page walk cost sharply. Where they hurt: memory-tight desktops, workloads with many small sparse mappings, and latency-sensitive services that suffer from the kernel’s page-compaction pauses. Oracle, PostgreSQL and Redis documentation all recommend disabling transparent huge pages while using explicit hugetlb pages instead. That disagreement between “automatic is good” and “automatic causes latency spikes” is real and unresolved.
5. Protection history, with dates:

6. Fuller ASLR timeline: PaX published the first design and implementation in July 2001. OpenBSD 3.4 in 2003 was the first mainstream operating system with it on by default. Linux enabled a weak form by default from kernel 2.6.12 in June 2005. Windows Vista added it for opted-in binaries, RTM November 2006. macOS randomized system libraries in 10.5 Leopard in October 2007, extended it to all applications in 10.7 Lion in July 2011, and added kernel randomization in 10.8 Mountain Lion in July 2012.

7. W^X is not free in practice. Just-in-time compilers must generate code and then run it. The modern answer is dual mapping: map the same physical pages twice, once writable and once executable, and never both at the same address. Apple silicon requires this and provides pthread_jit_write_protect_np to flip a thread between write mode and execute mode.

8. Meltdown, disclosed in January 2018, broke the assumption that the user-accessible flag alone was enough, because speculative execution leaked kernel data through cache timing. The fix, kernel page table isolation, gives the kernel a separate set of page tables so kernel memory is not mapped at all while user code runs. It costs 5 to 30 percent on syscall-heavy workloads, which is why PCID, process context identifiers, matter: they let the CPU keep TLB entries across the switch instead of flushing. ### 11.8.6 WORDS - remember these

9. Huge page — one big page instead of many small — a mapping created by terminating the page walk early, 2 MB or 1 GB on x86-64.

10. TLB reach — how much memory the translator covers — TLB entry count multiplied by page size.

11. THP — automatic huge pages — transparent huge pages, kernel-managed promotion of 4 KB mappings to 2 MB.

12. NX bit — this page is data, not code — bit 63 of a page table entry marking the region non-executable.

13. W^X — never writable and executable at once — a policy that no mapping carries both PROT_WRITE and PROT_EXEC.

14. ASLR — everything moves every run — address space layout randomization, the randomizing of load addresses to defeat fixed-address exploits. ## 11.9 How a program’s memory is laid out

PLAIN11.9.1 in simple words#

1. A running program’s address space is not one blob. It is a set of regions, each with a job and a permission.
2. Text is the machine code. Readable and executable, never writable.
3. Data holds variables that start with a value, for example a counter set to 5. It is copied from the file at load time.
4. BSS holds variables that start at zero. It takes no space in the file at all, only a note saying “reserve this many zero bytes”.
5. Heap is memory you ask for while running, and give back when done.
6. Stack holds local variables and the trail of function calls. It grows and shrinks automatically as functions are entered and left.
7. Mapped regions are everything else: shared libraries, big allocations, files made to look like memory.

PLAIN11.9.2 a picture in your head#

1. Picture a long street. At the low-numbered end is a printing works that cannot be altered: the code.
2. Then a builder’s yard that grows outward as you request more land: the heap.
3. At the high-numbered end is a stack of trays. Each function call puts a new tray on top; returning takes it off. It grows toward the yard.
4. If the trays pile up so high they reach the yard, something has gone badly wrong. That is a stack overflow.

Where this comparison breaks: modern systems leave an enormous unused gap between the stack and the heap, and put a deliberately unmapped guard page just below the stack, so the two cannot silently collide. The crash is arranged in advance rather than allowed to happen.

PLAIN11.9.3 a worked example#

1. Here is the real map of a tiny C program on the Linux machine used for this chapter, printed by reading /proc/self/maps. Columns are range, permissions and what it is.

55a209398000-55a209399000 r--p   maps2      read-only data
55a209399000-55a20939a000 r-xp   maps2      the code (text)
55a20939a000-55a20939b000 r--p   maps2      constants
55a20939c000-55a20939d000 rw-p   maps2      data and BSS
55a23da28000-55a23da49000 rw-p   [heap]     small allocations
7f19b4bff000-7f19b8c00000 rw-p   (anon)     the 64 MB malloc
7f19b8c00000-7f19b8c28000 r--p   libc.so.6  library headers
7f19b8c28000-7f19b8db0000 r-xp   libc.so.6  library code
7f19b8e03000-7f19b8e05000 rw-p   libc.so.6  library variables
7f19b8ef7000-7f19b8ef9000 r-xp   [vdso]     kernel fast calls
7ffd3da2b000-7ffd3da4d000 rw-p   [stack]    the stack

2. Read the permissions. Code is r-x. Data is rw-. Nothing is rwx.

3. The heap region is only 132 KB. The 64 MB request did not go there. It got its own mapping at 0x7f19b4bff000, because glibc sends large requests straight to the kernel instead of extending the heap.

4. The stack is 0x7ffd3da2b000 to 0x7ffd3da4d000, which is 136 KB right now. It can grow down to the limit, which ulimit -s reported as 8192 KB. ### 11.9.4 PLAIN - what is really happening inside

5. malloc is a library function, not a system call. Most of the time it never talks to the kernel.

6. It keeps a pool of memory it already owns and hands out pieces from it, remembering which pieces are free in linked lists called free lists.

7. free does not return memory to the operating system. It puts the piece back on a free list, and often merges it with neighbouring free pieces.

8. That is why a program’s memory use rarely goes down after a big job finishes. The memory is free to the program, still owned from the kernel’s point of view.

9. Repeated allocate-and-free of different sizes leaves the pool full of holes. Plenty of free bytes, none of them big enough. That is fragmentation.

10. A use-after-free is keeping a pointer to something you freed. The allocator may have handed those bytes to someone else, so you now read or write their data. It is one of the most common serious security bugs.

11. Garbage collection removes the need to call free. The runtime finds objects nothing points at any more and reclaims them automatically.

TECHNICAL11.9.5 the engineer’s version#

1. Segment names as the linker uses them. In ELF: .text, .rodata, .data, .bss. Inspect with size ./prog and readelf -S ./prog on Linux, or size -m and otool -l on macOS.
2. glibc malloc is ptmalloc2, derived from Doug Lea’s dlmalloc. Key behaviours, all implementation details and all tunable:

3. Arenas exist to reduce lock contention: each thread is steered to its own arena so allocations do not serialize. Set MALLOC_ARENA_MAX to limit it, which is a common fix for containers showing surprising memory growth.
4. Alternative allocators, with origins: tcmalloc from Google in 2005, jemalloc written by Jason Evans for FreeBSD in 2006 and later used by Firefox and Facebook, and mimalloc from Microsoft Research in 2019. Swapping allocator by LD_PRELOAD alone often changes throughput by 5 to 30 percent on allocation-heavy servers.
5. Slab allocation, published by Jeff Bonwick for SunOS in a 1994 USENIX paper, caches whole pre-constructed objects of one type. Linux uses SLUB today. Inspect with slabtop or cat /proc/slabinfo. Physical pages themselves are handed out by a buddy allocator, visible in /proc/buddyinfo.
6. Fragmentation has two forms. Internal is the unused tail inside a block rounded up to a size class. External is free memory split into pieces too small to use. Size-class allocators trade a little internal fragmentation to nearly eliminate external fragmentation.
7. Detecting the classic bugs:

valgrind --leak-check=full ./prog        # leaks, invalid access
gcc -fsanitize=address,undefined ./p.c   # fast, needs rebuild
heaptrack ./prog                         # allocation profiles
leaks PID          # macOS built in
MallocStackLogging=1 ./prog   # macOS allocation traces

8. The honest version: “free never returns memory to the operating system” is not quite true. glibc will trim the top of the heap with brk when a large contiguous run at the end becomes free, and blocks that were served by mmap are unmapped on free. What is true is that blocks freed from the middle of the heap stay owned by the process.
9. Garbage collection changes the failure modes rather than removing them. Leaks become “still reachable but never used”, which no collector can fix. Use-after-free largely disappears. In exchange you get pauses, extra memory headroom, and worse locality unless the collector compacts. Java’s G1 became default in JDK 9 in 2017 and ZGC reached production readiness in JDK 15 in 2020, targeting sub-millisecond pauses; Go has run a concurrent collector with sub-millisecond pauses since Go 1.8 in 2017. Rust takes the third path: no collector, ownership checked at compile time.

WORDS11.9.6 remember these#

1. Text segment — the code — the read-only executable region loaded from the binary, mapped r-x.
2. BSS — the zero-filled variables — uninitialized static storage, reserved by the loader and absent from the file.
3. Heap — memory you ask for at run time — the region managed by the allocator through brk and mmap.
4. Stack — the trail of function calls — a downward-growing region holding frames, guarded by an unmapped page.
5. Free list — the allocator’s list of spare pieces — linked structures of reclaimed blocks, usually bucketed by size class.
6. Fragmentation — free but unusable — memory split so that no single free region satisfies a request. ## 11.10 Shared memory and mapped files

PLAIN11.10.1 in simple words#

1. Two page tables can point at the same physical frame. That is all shared memory is.

2. A file can also be attached to a range of addresses. Reading those addresses reads the file. That is a memory-mapped file.

3. Copy-on-write is the clever middle case. Two processes share a page and both see it, but the page is marked read-only.

4. The moment either one writes, the hardware faults, the kernel makes a private copy for the writer, and the two go their separate ways.

5. That is why starting a copy of a process is cheap: nothing is copied until something is changed. ### 11.10.2 PLAIN - a picture in your head

6. Think of a reference book in a shared office.

7. Everyone’s desk index says “the dictionary is in cabinet 4”. One book, many pointers to it. That is a shared library.

8. Now a rule: you may read it, but if you want to scribble in it, you must first photocopy the page you want to change and scribble on your copy.

9. A memory-mapped file is the librarian agreeing to place any page of any book onto your desk the instant you look for it, without you filling in a request slip.

Where this comparison breaks: photocopying is per page, not per book, and the granularity is exactly 4 KB. Changing one byte copies 4096.

PLAIN11.10.3 a worked example#

1. Measured for this chapter. A process filled 1 GB of memory, then forked.

parent RSS after filling 1 GB : 1050060 KB
child: fork returned after      15.07 ms
child RSS immediately after fork: 1049404 KB
child: after writing all 1 GB   : copy cost 4202 ms
                                = 16.0 us per 4 KB page

2. Forking a 1 GB process took 15 milliseconds, not the seconds a real 1 GB copy would need. Almost nothing was copied.
3. The child’s reported resident size was immediately about 1 GB, which looks like a copy but is not. Resident size counts shared pages in full, for both processes. This is the single biggest reason memory numbers confuse people, and section 11.11 deals with it.
4. Second measurement: the sharing of library code. /proc/self/smaps_rollup for a small program reported:

5. Resident size 1640 kB, but proportional size only 397 kB, because 1496 kB of it is shared library code counted once per sharer. The program’s genuinely private, modified memory is 108 kB.

PLAIN11.10.4 what is really happening inside#

1. mmap asks the kernel to attach a range of addresses to something: a file, or nothing at all, which is called an anonymous mapping.

2. Two flags decide the sharing behaviour. MAP_SHARED means writes go to the underlying file and are visible to everyone. MAP_PRIVATE means writes become your own copy-on-write copies and are never written back.

3. No pages are brought in at mmap time. The mapping is a note. Pages arrive on first touch, exactly as in section 11.7.

4. On fork the kernel copies the page tables, not the pages, and marks every writable private page read-only in both parent and child.

5. Any write now faults. The kernel checks that the page is a copy-on-write page, allocates a fresh frame, copies 4096 bytes, points the writer’s entry at the copy and makes it writable again.

6. For a mapped file, a write marks the page dirty. A kernel writeback thread sends dirty pages to the file later, or at msync, or at unmap. ### 11.10.5 TECHNICAL - the engineer’s version

7. The core call, with the flags that matter:

void *p = mmap(NULL, len,
               PROT_READ | PROT_WRITE,
               MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);

/* file made to look like memory */
int fd = open("big.dat", O_RDWR);
void *f = mmap(NULL, len, PROT_READ | PROT_WRITE,
               MAP_SHARED, fd, 0);
msync(f, len, MS_SYNC);      /* force it to disk */
madvise(f, len, MADV_SEQUENTIAL | MADV_WILLNEED);

2. mmap appeared in the Berkeley and Sun Unix line in the 1980s and is now POSIX. The Windows equivalents are CreateFileMapping and MapViewOfFile.

3. When mapped files win: random access to a large file, many processes reading the same file, and avoiding the copy from page cache into a user buffer. When they lose: sequential streaming, where read with a large buffer is usually faster and has predictable memory behaviour; files that may be truncated underneath you, which turns into SIGBUS; and network filesystems, where a page fault can block on the network with no error path.

4. Databases disagree publicly about this. LMDB and older MongoDB storage engines were built on mmap. The 2022 paper “Are You Sure You Want to Use MMAP in Your Database Management System” from CMU argues against it, citing loss of control over eviction, transactional safety and page fault costs. PostgreSQL and InnoDB manage their own buffer pools instead. This is a genuine, live disagreement between competent engineers.

5. Copy-on-write is why fork is cheap and why fork in a large process is still not free: page table copying is proportional to the number of mapped pages, and every subsequent write costs a fault. Measured here: 15 ms to fork 1 GB, then 16 microseconds per page written.

6. This has a famous consequence for garbage-collected and reference-counted runtimes. CPython updates a reference count on every object touched, which writes to the object header, which triggers copy-on-write. A forked CPython worker therefore un-shares memory quickly. CPython gained gc.freeze in 3.7, released 2018, partly to reduce this. ### 11.10.6 WORDS - remember these

7. mmap — attach memory to a thing — the system call mapping a file or anonymous memory into an address space.

8. Anonymous mapping — memory backed by nothing — a mapping with no file, zero filled on first touch, backed by swap if needed.

9. Copy-on-write — share until someone writes — a policy of mapping pages read-only and duplicating them on the first write fault.

10. Memory-mapped file — a file that looks like an array — file contents made accessible through ordinary loads and stores via the page cache.

11. PSS — your fair share of shared memory — proportional set size, private pages plus each shared page divided by its number of sharers.

11.11 Measuring memory for real#

PLAIN11.11.1 in simple words#

1. Ask “how much memory is this program using” and there is no single true answer. There are about six, and they all mean different things.

2. Virtual size is how much address space the program has claimed. It can be enormous and mean nothing.

3. Resident size is how much is actually in RAM right now. Closer to useful, but it counts shared things in full for every sharer.

4. Private is the part only this process has. This is the number that would actually be freed if you killed it.

5. Add up resident sizes for all processes and you will get far more than the machine has, because shared pages are counted many times. ### 11.11.2 PLAIN - a picture in your head

6. Five flatmates share one kitchen, and each has a bedroom.

7. Ask each “how much of the flat do you use” and each says “my bedroom plus the kitchen”. Add the answers and you get more than the flat.

8. Virtual size is like counting the whole building because you have a key to the front door.

9. Proportional is bedroom plus one fifth of the kitchen. The five proportional answers do add up to the flat exactly.

10. Private is just the bedroom: what is actually emptied when someone leaves.

Where this comparison breaks: the kitchen can vanish and reappear. Clean file pages are dropped and reloaded silently, so the numbers move even when nothing in the program changes. ### 11.11.3 PLAIN - a worked example

1. Real numbers from this chapter’s test program.

2. Virtual size jumped by 4096 MB the moment memory was requested. Resident size moved by 0.3 MB. Anyone monitoring virtual size would have raised a false alarm.
3. Now the sharing side, from /proc/self/smaps_rollup: Rss 1640 kB but Pss 397 kB and Private_Dirty 108 kB.
4. Rule of thumb. To answer “will this fit”, use PSS or private dirty. To answer “is this leaking”, watch private dirty over time. Ignore virtual size unless you are chasing address space exhaustion.

PLAIN11.11.4 what is really happening inside#

1. The kernel maintains, per process, a list of mappings and a count of resident pages.
2. Resident size is the count of pages currently present in physical memory, times the page size, whether shared or not.
3. To compute proportional size the kernel must, for every page, look up how many processes map it and divide. That is expensive, which is why /proc/PID/smaps is much slower to read than /proc/PID/status.
4. Dirty pages are the ones modified since being loaded. Private dirty memory is the only kind that must be written to swap before it can be reclaimed.
5. This is why a process can show 2 GB resident and yet freeing it releases only 200 MB.

TECHNICAL11.11.5 the engineer’s version#

1. The counters and where they come from:

2. Commands on Linux:

ps -o pid,vsz,rss,comm -p PID
cat /proc/PID/status | grep -E 'VmSize|VmRSS|VmSwap'
cat /proc/PID/smaps_rollup      # Pss, Private_Dirty
pmap -X PID                     # per mapping detail
smem -k -s pss                  # sorted by PSS
systemd-cgtop / cat memory.current  # cgroup v2 truth

3. On containers and cgroup v2, memory.current in the cgroup directory is the number the kernel enforces limits against, and it includes page cache charged to the group. A container killed for exceeding its limit was often killed by cache, not by the application heap. memory.stat breaks it down, and memory.high throttles before memory.max kills.
4. Commands on macOS:

vm_stat            # free, active, wired, compressed pages
top -l 1 -s 0 -n 0     # PhysMem, compressor size, swap
footprint -p PID       # Apple's authoritative per-process figure
vmmap PID              # every region, dirty and swapped columns
leaks PID              # unreachable allocations

5. Why the totals never add up, stated precisely: the sum of RSS over all processes double counts every shared page once per sharer, and omits kernel allocations such as slab, page tables and network buffers, which belong to no process. The sum of PSS plus kernel usage does reconcile with MemTotal - MemFree, to within a few percent.
6. On the machine used here, free -m reported total 8023, used 773, free 6573, buff/cache 910, available 7249. available is an estimate produced by the kernel of how much a new workload could get without swapping. It is the only number in that output worth alerting on.

WORDS11.11.6 remember these#

1. VSZ — address space claimed — virtual set size, the sum of all mapping lengths, including untouched ones.
2. RSS — pages actually in RAM — resident set size, counting shared pages in full for every process.
3. PSS — your share of the shared parts — proportional set size, private plus shared divided by sharer count.
4. USS — what freeing it would return — unique set size, the private pages of one process.
5. Available memory — what a new program could get — the kernel’s estimate of free plus reclaimable, reported by free.

11.12 Cache-friendly programming#

PLAIN11.12.1 in simple words#

1. You cannot change the memory hierarchy. You can change how your data sits in it, and that is often worth more than any algorithmic cleverness.

2. Touch memory in the order it is stored. Neighbours, not jumps.

3. Keep the things you use together next to each other, and the things you do not use out of the way.

4. Work on a chunk small enough to stay in cache, finish with it, then move on.

5. Make sure two threads never keep writing to the same 64-byte block. ### 11.12.2 PLAIN - a picture in your head

6. Think of packing a suitcase for a trip.

7. Array of structs is packing one bag per day, each with a shirt, socks, a book, a towel and a laptop charger.

8. Struct of arrays is packing one bag of shirts, one of socks, one of books. Need shirts, carry one bag.

9. Padding is leaving deliberate empty space so two people never reach into the same bag at once and knock each other’s hands.

10. Blocking is unpacking one bag at a time on a small table, rather than spreading all seven across the floor.

Where this comparison breaks: if you genuinely need every field of every item, array of structs is the better layout, because it fetches everything in one go. The right choice depends entirely on your access pattern, and there is no universally faster layout. ### 11.12.3 PLAIN - a worked example

1. Change one, loop order. Summing a 4096 by 4096 array of doubles, measured on the 2.1 GHz Xeon used throughout.

for (i...) for (j...) s += a[i][j];   /* 0.019 s */
for (j...) for (i...) s += a[i][j];   /* 0.187 s */

Result: 9.0 to 10.4 times faster by swapping two lines.

2. Change two, blocking. Multiplying two 1024 by 1024 matrices, plain triple loop against a version that works on 64 by 64 tiles so each tile stays in cache, both compiled with the vectorizer off so only the memory effect is being measured.

Result: 8.21 times faster, same arithmetic, same result.

3. Change three, struct of arrays. Eight million particles of 40 bytes each, summing only the x field.

Result: 3.5 to 3.6 times faster, because 10 times less data crossed the memory bus.

4. Bonus change, field order. Two structs with identical fields in different order:

struct bad  { char a; double b; char c; int d; };  /* 24 bytes */
struct good { double b; int d; char a; char c; };  /* 16 bytes */

Sorting fields from largest to smallest cut the size by a third, purely by removing padding. A million of them is 8 MB saved.

PLAIN11.12.4 what is really happening inside#

1. Every read pulls a whole 64-byte line. Your effective bandwidth is (bytes you used) divided by (bytes fetched).

2. Row-order summing uses 64 of 64. Column-order uses 8 of 64. That is the factor of eight, before prefetching and vectorization make it worse.

3. In the particle test, the struct is 40 bytes and you wanted 4 of them. So each 64-byte line delivered about 6 useful bytes. The struct-of-arrays version delivered 64 useful bytes out of 64.

4. Tiling works because a naive matrix multiply walks a whole column of the second matrix for every output element, and that column does not stay in cache. Restricting the work to a 64 by 64 tile makes the three tiles involved fit together in cache, so each loaded value is reused 64 times. ### 11.12.5 TECHNICAL - the engineer’s version

5. False sharing, measured for this chapter with two threads pinned to different cores, each doing 30 million atomic increments.

2. The honest version: with plain non-atomic increments instead of atomic ones, the same test on the same machine showed no measurable penalty, about 0.49 ns per increment either way. A core can hold the line and retire many ordinary stores per ownership transfer, so the ping-pong amortizes. Atomic read-modify-write operations must be globally visible one at a time, so ownership really does move per operation. False sharing is therefore severe for atomics, counters and locks, and often mild for plain stores. Folklore usually omits this distinction.
3. The fix, in three languages:

struct counter { _Alignas(64) long value; };

alignas(std::hardware_destructive_interference_size) long v;

#[repr(align(64))] struct Padded(AtomicU64);

4. Padding to 128 bytes rather than 64 is the safer choice on Intel parts, because the adjacent-line prefetcher can pull in the sibling line. Apple silicon uses 128-byte L2 lines. This is why C++17 provides hardware_destructive_interference_size rather than a fixed constant.
5. Alignment rules: a scalar of size N must sit at an address that is a multiple of N. sizeof a struct is rounded up to its strictest member alignment so arrays stay aligned. Order fields from widest to narrowest and the padding usually disappears. Check with pahole ./prog on Linux, which prints holes explicitly, or clang -Xclang -fdump-record-layouts.
6. A checklist that reliably finds wins, roughly in order of payoff:

7. Verify every change with counters, not intuition:

perf stat -e cycles,instructions,cache-misses,\
LLC-load-misses,dTLB-load-misses ./prog
perf c2c record ./prog && perf c2c report   # false sharing
valgrind --tool=cachegrind ./prog           # simulated, exact

WORDS11.12.6 remember these#

1. Array of structs — one bag per item — AoS, contiguous records with all fields of one object together.

2. Struct of arrays — one bag per field — SoA, parallel arrays with one field of all objects together.

3. Padding — deliberate empty bytes — filler inserted by the compiler so each field meets its alignment requirement.

4. Blocking — work on one tile at a time — loop tiling, restructuring loops so the active working set fits in a cache level.

5. False sharing — different variables, same line — performance loss when independent data shares one cache line across cores. ## 11.98 Common wrong ideas

6. Wrong: more RAM always makes a machine faster. Right: more RAM removes swapping. If you were not swapping, it changes nothing measurable. Going from 8 GB to 32 GB on a thrashing machine can feel like a new computer; going from 32 GB to 64 GB on a machine that never fills 20 GB changes nothing at all. Faster RAM helps a little; more RAM helps only if you were short.

7. Wrong: swap is bad and should be turned off. Right: swap lets the kernel evict genuinely cold anonymous pages and use that RAM for something useful. Without swap, cold pages are stuck in RAM forever and the only reclaim target left is the page cache, which often makes things worse. Gigabytes sitting in swap with si and so at zero in vmstat is healthy. Constant swap-in and swap-out at the same time is the problem, and that is thrashing, not swap.

8. Wrong: virtual memory is just the page file. Right: virtual memory is address translation. Every process gets its own map from private addresses to real frames. Paging to disk is one optional feature built on top. A machine with swap disabled still uses virtual memory for every instruction it executes.

9. Wrong: “free RAM is wasted RAM” is a myth invented by Linux fans. Right: it is literally how every modern kernel works, including Windows and macOS. Unused RAM is filled with cached file contents which are dropped instantly when a program needs the space. On the machine used here, free -m showed 6573 MB free but 7249 MB available, and the difference is exactly cache the kernel will give back for nothing.

10. Wrong: dual channel doubles memory speed. Right: it roughly doubles peak bandwidth, and does not reduce latency at all. A latency-bound program, for example one chasing pointers through a linked list, sees almost no benefit. A bandwidth-bound program, such as an integrated GPU or a large streaming copy, sees a lot.

11. Wrong: lower CAS latency always means faster memory. Right: CAS latency is in clock ticks, so it only means something alongside the clock. DDR4-3200 CL16 and DDR5-6000 CL30 both work out to 10.0 nanoseconds. Convert to nanoseconds with CL x 2000 / rate before comparing anything.

12. Wrong: if two processes have 2 GB resident each, they use 4 GB. Right: shared pages, mainly library code and copy-on-write pages after fork, are counted in full for every process. Use PSS, which divides shared pages between sharers and does add up correctly.

13. Wrong: huge pages always help. Right: they help when TLB misses dominate, which mainly means large random working sets. Measured here, transparent huge pages gave 1.3 times on a 512 MB random walk, and major database vendors recommend turning them off because the kernel’s compaction work causes latency spikes.

11.99 Chapter summary in 20 lines#

1. Fast memory is small and dear, big memory is slow and cheap, so machines build a ladder from registers down to tape.
2. Measured on one 2.1 GHz machine, one random read cost 1.79 ns from L1 and 179.76 ns from RAM: a hundredfold spread for the same instruction.
3. In August 2026, DDR5 cost about 16.20 USD per gigabyte, SSD about 0.09 USD and hard disk about 0.02 USD, after a shortage that roughly quadrupled DRAM prices from 2024 levels.
4. The ladder works only because of locality: things used recently get used again, and their neighbours get used too.
5. Reading a 4096 by 4096 array along rows rather than down columns was 9.0 to 10.4 times faster, with no change to the arithmetic.
6. Memory arrives on sticks called DIMMs, organized into channels, ranks, bank groups, banks, rows and columns.
7. Extra channels multiply bandwidth and do nothing for latency, which is the most misunderstood fact about RAM.
8. True latency in nanoseconds is CL times 2000 divided by the data rate, so DDR4-3200 CL16 and DDR5-6000 CL30 are both exactly 10.0 ns.
9. Transfer rates rose about sixtyfold in twenty-five years while first-byte latency only halved. That gap is the memory wall.
10. The memory controller now lives on the CPU die, splits addresses into channel, rank, bank, row and column, and reorders requests, so latency is a distribution rather than a number.
11. Programs use virtual addresses; only the memory controller sees physical ones; the MMU translates on every access.
12. Memory is divided into 4 KB pages, mapped by a four-level or five-level page table tree rooted in CR3, cached by the TLB.
13. A real translation measured here turned 0x7f1e1a9ff010 into physical 0x162B8D010 through indices 254, 120, 212 and 511.
14. Neighbouring virtual pages land in scattered physical frames, which is the whole point of the mechanism.
15. Page faults are normal: a minor fault cost about 2 microseconds here, against 20 nanoseconds for an ordinary write, and touching 512 MB produced exactly 131,072 of them.
16. Demand paging means asking for 4 GB moves resident memory by 0.3 MB; memory appears only when written to.
17. Huge pages of 2 MB extend TLB reach from 8 MB to 4 GB and gave a measured 1.3 times on a large random walk.
18. Isolation comes free from the page tables themselves, reinforced by W^X from 2003, ASLR from 2001, and kernel page table isolation after Meltdown in 2018.
19. Copy-on-write makes fork cheap: forking a 1 GB process took 15 ms, and copying happened only when the child wrote, at 16 microseconds per page.
20. Layout beats cleverness: loop order gave 9x, tiling gave 8.2x, struct of arrays gave 3.5x, and padding shared atomic counters gave 3x to 4x, all on the same machine, all without changing a single result.