🗄️ Memory & Caches

3.1 Memory is the bottleneck

Processors got fast by making arithmetic cheap, parallel, and deeply pipelined. Memory did not keep up at the same rate. That mismatch is the old memory wall: if the core can retire useful work every cycle but the data it needs arrives hundreds of cycles later, the machine is no longer governed by how quickly it can add, compare, or shift. It is governed by whether the next load hits nearby storage or has to travel out to DRAM.

From first principles, a CPU instruction that uses data has two separate problems. The execution unit must perform the operation, and the operands must be present. A register-to-register integer add is usually a tiny event: on a multi-GHz x86-64 core, it is comfortably below 1 ns and can often be overlapped. A load that hits in L1 data cache is still close to the core, typically only a few cycles. A load that misses the private caches and waits for main memory is different in kind: roughly ~100 ns is a useful order-of-magnitude number, which is hundreds of cycles on a modern server CPU. The exact value depends on core, clock, DDR generation, NUMA placement, contention, and whether prefetchers help.

That ratio matters more than either number. If L1 is the desk in front of you, DRAM is not the next drawer; it is another building. While an out-of-order core can hide some misses with independent work, pointer chasing, descriptor walks, hash-table probes, and unpredictable packet metadata often create dependency chains. The next address is not known until the previous load completes, so the core cannot simply run ahead.

Networking code makes the cost visible. At 100 Gb/s, minimum Ethernet frames arrive on the wire about every ~7 ns; at higher rates the budget is smaller. One cold cache miss can therefore cost more time than the per-packet budget of an entire fast path. A driver receive loop that touches a descriptor, packet buffer, socket state, timestamp state, and queue metadata may execute only a modest number of instructions, yet lose because those instructions name scattered cache lines. DMA adds another wrinkle: the NIC and CPU communicate through memory, so ownership, visibility, cache coherence, and ordering are part of the performance contract, not academic details.

This chapter starts with the hierarchy because the hierarchy is the machine you are really programming: registers, L1, L2, shared last-level cache, DRAM, page tables, TLBs, and sometimes remote NUMA memory. C gives you objects and pointers; the hardware pays in cache lines, translations, coherence messages, and ordering constraints. Good low-level code is not just code with fewer instructions. It is code whose data is where the core needs it, when it needs it.

Sources

• Wulf and McKee, "Hitting the Memory Wall: Implications of the Obvious"
• AMD, Software Optimization Guide for the AMD Zen4 Microarchitecture
• Intel 64 and IA-32 Architectures Optimization Reference Manual
• Ulrich Drepper, "What Every Programmer Should Know About Memory"

3.2 The memory hierarchy and its latencies

The memory hierarchy is a trade: as storage gets farther from the execution core, it gets larger and cheaper per byte, but slower to reach and usually narrower per consumer. A register operand is already inside the core. A load that hits L1d still feels like instruction execution. A load that goes to DRAM is different: the core may wait for hundreds of cycles unless independent work is ready.

At a few GHz, one clock cycle is a fraction of a nanosecond. A 3.5 GHz cycle is about 0.29 ns; 100 ns is about 350 cycles. Exact numbers change with microarchitecture, clock, access pattern, contention, power state, and dependence chains, but the ladder is stable:

• Registers: effectively 0 ns extra memory latency; common integer operations are 1 to a few cycles.
• L1 cache: roughly ~1 ns, often 4-5 cycles load-to-use; capacity is typically tens of KiB per core.
• L2 cache: roughly a few ns, often around ~10-20 cycles; capacity is commonly hundreds of KiB to 1 MiB per core.
• L3 / last-level cache: roughly a dozen-plus ns, often tens of cycles; capacity is many MiB, shared by several cores or a socket.
• DRAM: roughly ~60-100 ns for an unloaded random access; capacity is GiB to TiB.
• NVMe SSD: roughly tens of microseconds for a small random read; sequential bandwidth is GB/s scale.
• Spinning disk: roughly milliseconds for a seek; sequential bandwidth is hundreds of MB/s scale.

Registers. Registers are the top because instructions name them directly. rax, xmm0, and vector registers are not fetched through a memory bus. Their capacity is tiny: architectural integer registers are measured in a few dozen values, and the physical register files behind renaming are still small on the scale of data structures.

L1 and L2. The first data cache is small because it must serve the load/store machinery every cycle. On a recent AMD server core such as Zen 4 EPYC, the L1d is 32 KiB per core and the private L2 is commonly 1 MiB; AMD's optimization material gives 4-5 cycle integer load-to-use latency for L1d and no less than 14 cycles for L2. A loop whose working set lives in L1 can look compute-bound. Push it into L2, and each dependent access is several times more expensive.

L3 / last-level cache. The last-level cache is much larger and slower. A Zen 4 EPYC chiplet has 32 MiB of L3 shared by up to eight cores, with some configurations providing more via stacked cache. A hit here is still dramatically better than DRAM, but it is no longer near the execution units. Think tens of cycles, not a handful. If a pointer-heavy data structure spills beyond this level, the cost changes again.

Main memory. DRAM is huge compared with caches and has impressive aggregate bandwidth: a modern server socket with many DDR5 channels can deliver hundreds of GB/s on streaming workloads. But bandwidth is not latency. A single dependent cache miss waits for one answer. In a cold linked-list walk, the next address is unknown until the current load returns, so the loop may become one DRAM round trip per node. At ~80 ns each, a few thousand misses are visible.

Storage. SSDs and disks are part of the broader hierarchy, but not the one a core traverses for an ordinary load instruction. They matter because software tries to keep active data in DRAM. A small NVMe read in ~20-100 us is hundreds of times slower than DRAM; a disk seek around ~10 ms is five orders of magnitude slower.

The bandwidth story follows the same shape, with an important caveat. L1 can deliver many bytes per cycle, L2 less, and L3 less again. DRAM can deliver enormous aggregate bandwidth across channels and cores, but an individual core sees a smaller stream rate, and random dependent loads see latency rather than bandwidth.

For low-level networking code, these magnitudes are not academic. At high packet rates, a packet's CPU budget can be only tens or hundreds of nanoseconds. A DRAM miss can cost more than the wire time of a minimum Ethernet frame on a fast link. Descriptor rings, completion queues, packet metadata, and DMA buffers often live in DRAM, but the fast path wants per-packet control state to stay hot. Touching an unexpected cold structure can wreck tail latency even if the average looks fine.

The practical rule is simple: capacity increases downward, latency increases downward, and bandwidth per immediate consumer generally decreases downward. Code whose hot working set fits in registers and cache can be an order of magnitude faster than code that repeatedly waits on DRAM. When misses are unavoidable, performance depends on whether independent work can overlap them. The later details explain how to influence that outcome; the first step is to feel the size of the ladder.

Sources

• Latency Numbers Everyone Should Know
• 5th Gen AMD EPYC Processor Architecture
• What Every Programmer Should Know About Memory, Part 1
• Agner Fog optimization manuals

3.3 How caches are organized

A cache stores memory in cache lines: fixed-size blocks copied from the next level. The usual line size on mainstream x86-64 cores is 64 B, and many modern Arm cores also use 64 B lines, though this is a microarchitecture property rather than a law of the ISA. Moving a block instead of a byte is worthwhile because memory is physically fetched and buffered in chunks, and because nearby bytes are often touched soon after the first byte. The line is therefore both the unit of allocation and, usually, eviction and write-back.

Think of a cache as an array of line slots, each holding data plus metadata such as a valid bit, a tag, and often a dirty bit. The core question is: given an address, which slots could contain the line, and how cheaply can the cache check them? Hardware answers by splitting the address into three fields:

offset_bits = log2(line_size)
set_index_bits = log2(number_of_sets)
tag_bits = address_bits - set_index_bits - offset_bits

With a 64 B line, the low 6 address bits are the offset, selecting a byte within the line. If the cache has S sets, the next log2(S) bits are the index, selecting one set. The remaining high bits are the tag, proving which memory line is actually present in that set. A hit occurs only if one candidate way in the indexed set has valid == 1 and a matching tag; otherwise the access misses and the line must be supplied from a lower level.

The simplest organization is direct-mapped. Each address maps to exactly one slot: one set, one way. This is fast and cheap because there is only one tag to read and compare, but two hot addresses with the same index cannot coexist even if the rest of the cache is empty. At the other extreme, a fully associative cache lets any line occupy any slot. That minimizes placement conflicts, but every lookup must search many tags, which is expensive in area, power, and access time.

Real CPU caches mostly use the middle ground: N-way set associativity. The index chooses one set, and that set contains N possible line slots called ways. The tags for all N ways are compared in parallel. A 32 KiB, 8-way L1 data cache with 64 B lines has:

lines = 32 * 1024 / 64      // 512 total lines
sets  = 512 / 8             // 64 sets
offset = 6 bits             // 64 B line
index  = 6 bits             // 64 sets
tag    = remaining high bits

That shape is a realistic x86-64 L1 data-cache example: Intel documents many Core-family L1 data caches as 32 KB, 8-way, with 64-byte lines. Recent Arm cores commonly use configurable L1 data caches such as 32 KiB or 64 KiB, also with 64 B lines, but associativity and size vary. The arithmetic is what matters: capacity is sets * ways * line_size.

This mapping detail leaks into low-level performance work. A DMA descriptor ring or packet buffer layout that straddles two cache lines can make one logical object require two line fills or two dirty evictions. Aligning hot descriptors, doorbells, and per-packet metadata to 64 B boundaries is not magic; it is simply respecting the unit the cache moves. Similarly, two unrelated hot arrays separated by an unfortunate power-of-two stride may repeatedly land in the same small group of sets, producing conflict misses in a packet-processing loop even when the total working set looks small.

Stores add another policy choice. In a write-through cache, a store updates the cache and immediately pushes the write to the next level. This is conceptually simple, but it creates more lower-level traffic. In a write-back cache, a store updates only the cached line and sets its dirty bit. The modified line is written to the next level later, usually when it is evicted. This saves bandwidth when software writes the same line several times, but the cache must remember which lines are dirty. Modern CPU data caches are normally write-back. They are also normally write-allocate: on a store miss, the cache first brings the line in, then modifies it. The alternative is no-write-allocate, also called write-around, where a store miss bypasses allocation and writes to the lower level instead.

Finally, a set may already be full when a missed line needs to enter it. The cache must choose a victim way. The clean mathematical policy is least recently used: evict the line whose last access is oldest. True LRU becomes costly as associativity rises because the hardware must maintain detailed ordering among ways on every access. Many real caches therefore approximate it with pseudo-LRU schemes, including tree-based encodings, or use random or pseudo-random replacement. Larger modern caches may use more adaptive policies that try to distinguish streaming lines from lines likely to be reused. The exact policy is usually microarchitecture-specific and not always public. What is architecturally visible to performance is the consequence: an evicted clean line can simply be discarded, while an evicted dirty line consumes real write-back bandwidth on the path toward memory.

Sources

• Intel 64 and IA-32 Architectures Optimization Reference Manual
• Arm Cortex-A78 L1 memory system
• What Every Programmer Should Know About Memory
• CMU 15-213 Cache Memories lecture notes

3.4 Locality, layout, and prefetching

Caches work because programs are not random. Most useful code has locality: after touching one address, it tends to touch the same address again soon, or it tends to touch nearby addresses soon. Temporal locality is reuse over time: a byte touched now is likely to be touched again soon. Spatial locality is reuse over address space: bytes near the one just used are likely to be used soon. This is why the cache line matters. A load that misses fills a whole line, not one byte. On modern x86-64 cores, and on many common Arm application cores, that line is commonly 64 bytes. The next integer in an array may already have ridden in with the miss you just paid for.

The most cache-friendly data structure is often the boring one: contiguous memory walked in order. An array scan gives the machine a stream of adjacent lines, each mostly useful. A linked list, tree of heap nodes, or hash table of pointers has the opposite shape. Each node may live on a different line, and useful fields may occupy only a few bytes. The CPU pays the miss cost, but most of the fetched line is padding, next pointers, or cold fields.

This is the practical reason behind array-of-structs versus struct-of-arrays. In an AoS layout, packet[i].len, packet[i].flow_hash, packet[i].flags, and the rest of the record live together. That is natural when a loop consumes a whole record. But if a hot loop only tests flow_hash and flags, AoS wastes line bandwidth on payload pointers, timestamps, and other cold fields. A SoA layout stores flow_hash[] and flags[] densely, so each line contains many useful values; it also gives vector instructions a simpler stream. SoA makes cross-record scans better; AoS can be better when the unit of work is the whole object. Field ordering is the middle ground: put fields used together near each other, keep hot prefixes compact, and keep the working set small enough for the target cache.

Prefetching starts a miss before the load that needs the data. Hardware prefetchers watch recent accesses and, on modern CPUs, recognize streams and many constant-stride patterns. A loop over a[i] is easy: after a few misses the prefetcher can fetch later lines before demand loads reach them. A stride such as a[i * 16] is still predictable, though it uses less of each line. A pointer chase is harder because the next address is not known until the current node arrives.

Software prefetch exposes the same idea to code. On x86, the data-prefetch hints are PREFETCHT0, PREFETCHT1, PREFETCHT2, and PREFETCHNTA: roughly, fetch with high temporal locality into nearer cache levels, lower locality into farther levels, or non-temporal intent for data not expected to be reused. In C/C++ compiled by GCC or Clang, the usual interface is __builtin_prefetch(addr, rw, locality), where rw says read or write intent and locality is 0 to 3.

That hint is non-binding. It may generate a target prefetch instruction, it may be ignored by the hardware, and it does not make an invalid pointer safe to dereference. It is most useful when software knows the future address early but the hardware prefetcher cannot infer it: prefetch node N+k while processing node N, or prefetch the next descriptor or packet header. It is also easy to make worse: too near and the data still misses; too far and it is evicted before use; too much and you waste bandwidth. For regular linear scans, trust the hardware until measurement says otherwise.

The bad patterns destroy locality or exceed the cache's ability to remember it. Random access over a working set larger than cache turns nearly every access into a miss. Large strides waste spatial locality: if you read one int every 64 bytes, each line contributes one word and the rest is dead traffic. Large power-of-two strides can be worse because they may map to the same small subset of cache sets, causing conflict misses even when total data size looks acceptable.

Two-dimensional arrays add the classic example. C stores a[row][col] in row-major order, so walking the inner column index streams through memory. Walking down a column jumps by the row width each access. For a large matrix that can mean one useful element per fetched line, poor prefetching, and many misses. The first fix is loop interchange: make the innermost loop follow memory order. The next fix is blocking, or tiling: operate on a small rectangle that fits in cache and reuse it while it is hot.

In low-level networking code these choices show up directly. A packet classifier may lay out per-packet metadata as SoA so the hot path streams through lengths, hashes, and flags without dragging cold bookkeeping through L1. Per-core fast-path structures stay compact because a structure that fits in L1 or L2 differs from one that reaches DRAM. Coherence and false sharing matter too, but they are separate problems.

Sources

• Intel 64 and IA-32 Architectures Optimization Reference Manual
• GCC documentation: Other Built-in Functions, `__builtin_prefetch`
• Arm Neoverse E1 Core Technical Reference Manual: Components
• Ulrich Drepper, What Every Programmer Should Know About Memory

3.5 Virtual memory and paging

The cache discussions so far assumed that an address names a byte of memory. On a modern general-purpose machine, that is only half true. The address in a C pointer is a virtual address in the process's private address space. DRAM is selected by physical addresses. Hardware translates from virtual to physical on every instruction fetch, load, and store.

This indirection solves three problems. First, it gives isolation: one process cannot normally name another process's memory. Second, it gives relocation: the same program can run wherever its pages reside in RAM. Third, it gives the illusion of a large, mostly contiguous private memory image, even when the real machine is fragmented, shared, or partly backed by storage.

The unit of translation is a page. On x86-64, the normal page size is 4 KiB, so the low 12 bits of a virtual address are the byte offset within the page. The remaining high bits form the virtual page number. A page-table entry maps that virtual page to a physical page frame, and the original 12 offset bits are appended to form the physical address.

A flat array with one entry for every possible virtual page would be enormous, and most of it would describe unused address ranges. x86-64 instead uses a sparse tree of page tables. With 4-level paging, a canonical linear address uses 48 address bits: a 12-bit page offset plus four 9-bit indices. Each index selects one of 512 entries, because a 4 KiB page-table page holding 8-byte entries contains 4096 / 8 = 512 entries.

The walk is:

• CR3 contains the physical base of the top-level table
• the indices select PML4 -> PDPT -> PD -> PT
• the final PT entry maps the 4 KiB page frame

The hierarchy is the trick. If a process never touches a huge virtual region, the kernel does not allocate lower-level page-table pages for it. The address space can be large and sparse while page-table memory follows the parts actually mapped. Systems that enable 5-level paging add a PML5 above PML4; x86 names the feature LA57/la57, and it extends the virtual address width to 57 bits.

The translation is not done by compiler code or by the kernel on every load. The CPU's memory-management unit, the MMU, performs the page walk in hardware using the tables selected by CR3. The result is cached in the TLB, the cache that makes paging fast enough. The next section covers the TLB in detail; here it is enough to know what it caches.

Page-table entries are also protection records. Important bits include present, read/write, user/supervisor, NX or no-execute, accessed, and dirty. If present is clear, or if the access violates permissions, the MMU raises a page-fault exception. On x86 this is #PF, interrupt vector 14. Control transfers to the kernel's page-fault handler.

Some faults are normal. The kernel may allocate a physical page on first touch for demand paging, or copy a shared page when a process writes to a copy-on-write mapping after fork(). Those mechanisms belong mostly to the OS chapter. If the address is invalid or the access is not allowed, the kernel delivers SIGSEGV.

Page size is a tradeoff. Small pages reduce internal fragmentation: if an allocation needs only a few bytes, a 4 KiB page wastes at most the rest of that page. But small pages require more page-table entries and more TLB entries to cover the same working set. Larger pages increase TLB reach: each cached translation covers more memory.

x86-64 therefore supports huge pages as well as 4 KiB pages. A 2 MiB page is mapped by terminating the walk at the page-directory level. A 1 GiB page is mapped by terminating it at the PDPT level. These are still page translations; they simply consume fewer lower-level table pages and cover more bytes per translation.

Linux exposes huge pages in two main ways. HugeTLB pages are explicit huge pages managed through the HugeTLB subsystem, commonly used by applications that deliberately reserve and map huge-page memory. Transparent Huge Pages, or THP, are a kernel policy for backing suitable mappings with huge pages without a special application API. Explicit HugeTLB use gives more control and predictability; THP is opportunistic and depends on kernel policy and memory state.

For low-level networking work, this is not academic. A userspace ring buffer may be virtually contiguous while its 4 KiB physical frames are scattered. A NIC doing DMA cannot use a C pointer as-is; it needs physical addresses, or IOMMU-translated I/O virtual addresses. Drivers, pinned memory, scatter-gather lists, and huge-page-backed packet buffers exist because translation and physical contiguity affect what the device can touch efficiently. Kernel-bypass datapaths such as DPDK lean on pinned huge pages for this reason. The DMA and IOMMU side belongs in the Buses, Devices & DMA chapter; the key point here is that C pointers name virtual memory, not wire-visible addresses.

Sources

• Intel 64 and IA-32 Architectures Software Developer's Manuals
• AMD64 Architecture Programmer's Manual Volume 2: System Programming
• HugeTLB Pages - The Linux Kernel documentation
• Transparent Hugepage Support - The Linux Kernel documentation

3.6 The TLB and translation cost

The page tables are the authoritative map, but they are much too slow to consult on every load, store, and instruction fetch. Before the core can finish, it needs the physical page number.

The translation lookaside buffer, or TLB, is the MMU's cache of recently used virtual-to-physical page translations. A TLB entry says: for this virtual page in this address space, the physical frame and permission bits are these. On a hit, translation is fast enough for the pipeline. On a miss, hardware walks the page tables, checks permissions, fills a TLB entry, and retries.

Modern cores do not have one flat TLB. They have a small, fast first level and larger second level, often with split first-level instruction and data TLBs and a unified second-level TLB. The exact numbers are generation-dependent. A recent x86 core is commonly in the range of tens of L1 data-TLB entries for 4 KiB pages and a unified second-level TLB around 1024 to 2048+ entries. Huge-page entries are tracked separately, with fewer entries for 2 MiB and 1 GiB pages. Treat any universal TLB size as suspicious.

Reach is the key quantity. A 64 entry TLB for 4 KiB pages covers only 256 KiB; a 1536 entry second-level TLB covers 6 MiB. With 2 MiB pages, the same entry count would cover gigabytes, though actual huge-page entry counts are usually smaller. Huge pages reduce TLB pressure because one translation covers far more memory. A poll-mode driver walking descriptor rings and mbuf pools can burn cycles on translation misses. DPDK and similar data planes use 2 MiB or 1 GiB huge pages to give packet-buffer memory practical TLB reach.

A TLB miss is not just "one extra memory access." On ordinary four-level x86-64 paging, the page walker may have to read the PML4E, PDPTE, PDE, and PTE before it has the final frame number. With five-level paging enabled by LA57, there can be one more level. These reads are dependent: the address of the next entry is learned from the previous entry. Paging-structure entries are cacheable, and modern cores have page-walk caches, so a hot walk is far cheaper than a cold walk that misses into DRAM at every level.

Large pages help twice. They increase reach, and they shorten the walk because translation can terminate at a higher-level entry. A 2 MiB x86 page does not require the final 4 KiB PTE lookup; a 1 GiB page terminates higher still. Huge pages consume coarser physical memory, but for long-lived packet pools and rings the trade is often right.

Context switches add another problem. The same virtual address in two processes usually means two different physical pages. Older x86 systems mostly dealt with this by flushing non-global TLB entries when CR3, the page-table-root register, changed. Entries marked global with the page-table G bit could survive, useful for kernel mappings shared across address spaces.

Address-space tags fix that. x86 calls the tag a PCID, a process-context identifier associated with CR3 when PCID is enabled; architecturally it is 12 bits. Arm uses ASIDs for the same idea. A tagged TLB entry is "virtual page X for address space tag Y," allowing entries from multiple processes to coexist. x86 also provides INVPCID to invalidate by PCID and address. PCID became especially visible after KPTI/PTI mitigations for Meltdown, because switching between user and kernel page tables would otherwise make TLB flushing much more expensive.

The TLB also has a consistency problem. If the kernel changes a page-table entry, any core that has cached the old translation might keep using it. Unlike the data caches discussed next, x86 TLBs are not kept coherent by a hardware coherence protocol. The operating system must explicitly invalidate stale translations. Locally, x86 can use INVLPG for one virtual page, reload CR3 for a broader flush, or use INVPCID.

On a multicore system, invalidation becomes a TLB shootdown. If one thread unmaps memory with munmap, changes protection with mprotect, or if the kernel migrates pages, the kernel must find CPUs that might be running the affected address space and make them drop stale entries. Traditional x86 Linux does this in software with inter-processor interrupts; the remote handler performs the local invalidation and acknowledges it. That is correct, but it interrupts work on other cores and can show up as tail-latency spikes on otherwise isolated polling cores.

Architectures have been adding help. Arm has TLBI operations that can broadcast invalidation within a shareability domain. Recent AMD extensions include broadcast-style TLB invalidation instructions such as INVLPGB with synchronization support, intended to reduce some remote-CPU interrupts. The principle remains: page tables are shared memory, but cached translations are per-core microarchitectural state, and stale translations must be removed before the old mapping can be safely forgotten.

For driver and NIC work, keep hot data structures within a small number of pages. Use huge pages for hot packet memory. Avoid unnecessary mmap/munmap churn in latency-sensitive paths. Register and pin DMA buffers so mappings remain stable. A cache miss costs cycles; a TLB miss can cost a dependent walk; a shootdown can disturb cores that did not ask to be disturbed.

Sources

• Intel 64 and IA-32 Architectures Software Developer Manuals
• Linux kernel documentation: The TLB
• Arm Developer: Address Space ID
• DPDK Linux Getting Started Guide: System Requirements and Hugepages

3.7 Cache coherence

Private caches create a correctness problem. Core 0 and core 1 can both have the same physical cache line in their L1 or L2. With a write-back cache, a store does not immediately update memory; it updates one cached copy and marks that line dirty. If another core kept reading its old clean copy, the machine would no longer behave like shared memory.

Cache coherence is the hardware guarantee that, for each memory location, cores observe a single value evolving over time. A common way to state the invariant is single writer or multiple readers: at any instant, either one cache may have permission to modify the line, or several caches may have read-only copies, but not both. Coherence is about one address at a time. It is distinct from the memory ordering model, which says what order cores may observe operations to different addresses; that comes next.

Protocols enforce the invariant at cache-line granularity, normally 64 B on mainstream x86-64 systems. A small multiprocessor can use snooping: coherence controllers broadcast or observe transactions on a shared medium, so every cache can notice when a line it holds is requested or invalidated. That is simple at low core counts, but broadcast traffic does not scale well. Larger designs use directory-based coherence: a directory tracks which caches may hold a line and sends targeted messages. Real many-core CPUs often combine directory-like tracking with snoop filters, avoiding snoops when hardware can prove a cache cannot have the line.

The classic MESI protocol names four per-line states in each cache:

• Modified: this cache has the only valid copy, it has been written, and memory is stale.
• Exclusive: this cache has the only valid copy, but it is clean; memory still matches it.
• Shared: this cache has a clean read-only copy, and other caches may also have it.
• Invalid: this cache has no usable copy of the line.

The important optimization over MSI is Exclusive. If a core reads a line and no other cache has it, the line can enter Exclusive. A later store by that same core can silently change it to Modified, with no interconnect transaction, because no other cache can hold a stale copy. If the line is merely Shared, a store is not silent.

To write a shared line, the core must first obtain exclusive ownership. On ordinary write-allocate CPUs this is often called a read for ownership, or RFO: the core requests the line with intent to modify, and the coherence protocol invalidates other cached copies before the store can become globally coherent. The expensive part is not the byte store itself. It is the ownership round trip across the interconnect: directory lookup or snoop, invalidation messages, acknowledgements, and sometimes data movement from another cache.

That cost is why a write to a shared line can be far slower than a write to a line already owned by the core. It is also the mechanism behind false sharing: two cores writing different fields in the same 64 B line repeatedly force ownership to bounce back and forth. The program is not logically sharing one variable, but the hardware coherence unit is the line. The concurrency chapter treats false sharing fully; for now, remember that line ownership, not C object identity, is what moves.

MOESI adds a fifth state, Owned. In MESI, a dirty Modified line normally has to be supplied or written back before other caches can safely share the current value. With Owned, one cache may hold a dirty shared copy while other caches hold clean shared copies. The owner supplies the up-to-date data and remains responsible for eventual write-back. This avoids updating memory merely because another core reads a dirty line. MOESI is strongly associated with AMD systems; AMD64 documentation describes MOESI states, and AMD performance tools expose events for Modified and Owned hits. Intel systems have used MESIF, where the Forward state designates one sharer to respond to later requests.

All of these state transitions ride on the processor interconnect. Inside a chip, the fabric connects cores, private caches, shared last-level-cache slices, memory controllers, and I/O agents. AMD’s modern name is Infinity Fabric; older AMD multiprocessor systems used coherent HyperTransport. Intel client and server processors have used ring interconnects, and Xeon Scalable processors moved to a mesh to reduce ring pressure at higher core counts. Across sockets, Intel used QPI and later UPI, but the same principle applies: coherence messages consume fabric latency and bandwidth.

For low-level NIC and driver work, this matters directly. A producer core that writes a descriptor and a consumer polling core that reads it transfer cache-line ownership. A completion queue updated by one core and sampled by another creates coherence traffic even if both threads stay in L1 for unrelated data. High-performance packet paths therefore make ownership obvious: descriptor rings with producer-owned and consumer-owned regions, per-queue state touched by one core, counters split per core, and hot fields aligned so independent writers do not share a line. The goal is not merely fewer cache misses; it is fewer forced ownership transfers over the on-die fabric.

Sources

• AMD64 Architecture Programmer's Manual Volume 2: System Programming
• Intel Xeon Processor Scalable Family Technical Overview
• Intel patent: Forward state for use in cache coherency in a multiprocessor system
• Sorin, Hill, and Wood: A Primer on Memory Consistency and Cache Coherence

3.8 The memory model and atomics

Cache coherence answers one narrow question: for a single memory location, the machine keeps the cores from living in permanently different realities. It does not say that another core must observe writes to different locations in the order you issued them. That gap is where the C11 and C++11 memory model lives.

Before C11 and C++11, portable C and C++ had no formal shared-memory threading model. Real programs used pthreads, intrinsics, inline assembly, and platform rules, but the language itself gave the optimizer no contract for inter-thread communication. Both compiler and hardware may reorder memory operations when the single-threaded result is unchanged. Source order is not a physical law. The memory model defines which observations are allowed when threads share memory.

The first rule is race freedom. Two evaluations conflict when they touch the same memory location and at least one modifies it. A data race occurs when conflicting evaluations run in different threads, are not both atomic, and neither happens-before the other. In C11 and C++11, a data race on non-atomic objects is undefined behavior. Once the optimizer may assume that ordinary objects are not concurrently raced, it may cache, merge, delete, or reorder ordinary loads and stores in ways that break informal reasoning.

The fix is not merely "use a naturally aligned word". An aligned word-sized load or store is often indivisible on real hardware, but that does not make the program defined or constrain compiler reordering. Shared synchronization variables must be atomic: _Atomic with <stdatomic.h> in C, and std::atomic with <atomic> in C++. GCC and Clang also expose this ordering family through __atomic builtins.

Atomic operations include loads, stores, and read-modify-write operations. A read-modify-write such as fetch_add, exchange, or compare_exchange_weak / compare_exchange_strong is a single indivisible operation: no other thread can observe it half-done, and all threads agree on that atomic object's modification order. Compare-and-swap is the primitive behind many lock-free algorithms; retry-loop discipline comes later.

Each atomic operation also carries a memory order. Stronger orders are easier to reason about because they constrain more observations; weaker orders can be cheaper in hot paths because they leave more freedom.

memory_order_seq_cst is sequentially consistent ordering, the strongest standard order and the default for ordinary C and C++ atomic operations when no explicit order is supplied. All memory_order_seq_cst operations appear in one global total order that every thread agrees on, while respecting each thread's sequencing. This is the model most people first expect: as if atomic operations happened one at a time in a universal order. It is easy to start with, but can cost latency when weaker ordering would suffice.

memory_order_release and memory_order_acquire are the workhorse pair. A release operation publishes earlier work; an acquire operation consumes that publication. When an acquire load reads the value written by a release store on the same atomic object, the store synchronizes-with the load, and the writes sequenced before the release happen-before the reads and writes sequenced after the acquire. A release store prevents earlier reads and writes from moving after it; an acquire load prevents later reads and writes from moving before it. The compiler lowers that contract to whatever the target needs.

int data;
atomic_int ready;

void producer(void) {
    data = 42;
    atomic_store_explicit(&ready, 1, memory_order_release);
}

void consumer(void) {
    while (atomic_load_explicit(&ready, memory_order_acquire) != 1) {
    }
    int x = data;
}

The consumer's acquire load reads the value written by the producer's release store. That creates the synchronizes-with edge, so the write to data happens-before the later read of data. The non-atomic data access is therefore not a data race, and the consumer may rely on seeing the published value. If ready used memory_order_relaxed, the flag itself would still be atomic, but it would not order the access to data.

For a read-modify-write that both consumes earlier publication and publishes later work, use memory_order_acq_rel, common on atomic index updates that both read old state and write new state.

memory_order_relaxed is the other essential tool. Relaxed atomic operations are still atomic, and each atomic object still has a coherent modification order of its own. What relaxed does not provide is ordering for other memory. A relaxed statistics counter is often correct: fetch_add(..., memory_order_relaxed) gives a final count without pretending that the increment publishes packet data, descriptor contents, or ownership. It is wrong when the atomic value is a flag saying ordinary memory is ready.

memory_order_consume exists in the standard as a dependency-ordered variant of acquire, but it is widely discouraged and current compilers commonly strengthen it to acquire; do not build new reasoning around it.

This vocabulary shows up in low-level networking code. A shared descriptor ring has the same shape: fill the descriptor, then release-store the ownership bit or producer index; the other side acquire-loads that indication before reading the descriptor. Choosing relaxed for counters and acquire/release for publication is a real performance lever. Device registers and MMIO are different: volatile plus device-specific ordering barriers, not the ordinary C atomics model, make those accesses meaningful.

Sources

• cppreference: std::memory_order
• cppreference: Multi-threaded executions and data races
• cppreference: C atomic operations library
• GCC manual: __atomic builtins

3.9 Memory barriers and ordering

Memory ordering has two enemies, and they are separate. The compiler may reorder, merge, duplicate, or remove memory accesses while preserving the single-threaded meaning of the C abstract machine. The CPU may then execute the emitted loads and stores in an order that is legal for the target architecture. A correct lock-free or driver protocol must constrain both when another core or device attaches meaning to access order.

A compiler barrier constrains only the compiler. In GCC-style C, asm volatile("" ::: "memory") says that unknown memory may be read or written here, so ordinary memory operations cannot be freely moved across it. Linux exposes this as barrier(). It does not drain a store buffer or signal another core. READ_ONCE(x) and WRITE_ONCE(x, v) are more targeted tools: they force a real access of the named object and prevent destructive compiler transformations such as inventing extra loads, tearing a scalar access, or caching a value in a register across a polling loop. They are not, by themselves, full inter-core ordering.

A hardware barrier constrains what other observers may see. Linux's smp_mb(), smp_rmb(), and smp_wmb() are portable SMP barriers: full, read, and write barriers for normal shared memory. smp_load_acquire() and smp_store_release() express the common one-way cases directly. In C11/C++11 terms, release prevents earlier reads and writes from moving after the publishing operation; acquire prevents later reads and writes from moving before the consuming operation; seq_cst adds a single total order among seq_cst operations. The generated instructions depend on the architecture.

The usual publish/consume pattern is the reason barriers exist:

buf->len = len;
buf->data = ptr;
smp_store_release(&ready, 1);

if (smp_load_acquire(&ready))
        use(buf->data, buf->len);

The required fact is not just "the flag becomes 1." It is "a consumer that observes the flag also observes the buffer initialization." Without that ordering edge, a weak CPU may make the flag visible before the data, or the compiler may move independent-looking accesses into the wrong shape.

x86 is comparatively strong. The model normally used for mainstream cacheable memory is x86-TSO, total store order. Loads are not reordered with loads, and stores are not reordered with stores. The important relaxation is store-to-load: a core can place a store in its store buffer and execute a later load before that store has become globally visible. That is why many acquire and release operations compile to plain loads and stores on x86, but a full store-load ordering point may need an actual fence or a locked operation. MFENCE orders prior loads and stores before later loads and stores; SFENCE orders stores, especially relevant for non-temporal stores; LFENCE orders loads and is also used for speculation control. An instruction with the LOCK prefix, such as a locked read-modify-write, acts as a full memory barrier for normal memory ordering.

ARM/AArch64 and POWER are weaker. They allow more freedom in the order in which independent loads and stores become visible, so code that "works on x86" often fails there. On AArch64, DMB is the ordinary data memory barrier: it orders memory accesses according to its domain and type options. DSB is stronger: it waits for completion of the relevant accesses before later instructions proceed, which matters for device control. ISB flushes the fetched instruction stream so later instructions execute with the effects of prior context changes. AArch64 also has acquire and release instructions such as LDAR and STLR, avoiding a separate full barrier in common cases.

POWER is also weak. sync is the heavyweight full barrier. lwsync is a cheaper ordering barrier used for many acquire/release-style data paths, but it is not a universal substitute for sync. eieio orders certain cache-inhibited and device-style accesses. isync is an instruction synchronization barrier, often paired with control dependencies or lock acquisition patterns.

Ask for a barrier when correctness depends on another observer seeing two accesses in a particular order. Shared-memory examples include publishing an initialized object, handing ownership of a queue entry to another core, releasing a lock, or checking a flag before reading associated state. Device examples are just as important. A NIC transmit path writes descriptors in DMA-coherent memory and then rings an MMIO doorbell. The device must not observe the doorbell before the descriptors are complete. After a completion interrupt or status bit, the driver may need to order reads of device-updated memory before acting on them.

That is why driver code distinguishes normal SMP barriers from DMA and MMIO ordering. smp_wmb() is about other CPUs. For device visibility, Linux code uses the DMA/MMIO-aware primitives and accessors appropriate to the mapping: for example, dma_wmb() or wmb() before handing descriptors to a device, mb() when both directions must be ordered, and readl()/writel() or I/O barrier helpers for MMIO rather than plain C pointer accesses. The correct primitive depends on whether the observer is another core, a DMA engine, a posted MMIO write path, or an instruction stream after changing execution context.

Sources

• Linux kernel memory barriers documentation
• Intel 64 and IA-32 Architectures Software Developer Manuals
• Arm Developer: Memory barriers and acquire-release instructions
• x86-TSO: A Rigorous and Usable Programmer's Model for x86 Multiprocessors

3.10 NUMA and remote memory

Once ordering has crossed from one core to another, the next question is physical: which memory controller owns the line, and how far away is it? On a NUMA machine, the address space is shared, but access is not uniform. A core can load from any normal RAM, yet a load served by memory attached to its own locality domain is different from one that must cross a socket-to-socket fabric and return over that shared path.

In the simple two-socket picture, each package has cores, caches, memory channels, PCIe roots, and one or more coherent links to the other package. Intel systems moved from QPI (QuickPath Interconnect) to UPI (Ultra Path Interconnect) in Xeon Scalable-era servers. AMD moved from HyperTransport-attached Opteron systems to EPYC packages built around Infinity Fabric; socket-to-socket coherent links are commonly described as xGMI. The invariant is that the interconnect is not memory. It is a narrower, contended route carrying coherence messages, remote reads and writes, interrupts, and sometimes I/O-related traffic.

Local and remote are topology terms, not C terms. The C pointer value does not say whether *p is local. The virtual address translates as usual; the physical page frame belongs to some NUMA node; the executing CPU belongs to some NUMA node; and the machine has a distance matrix. Linux exposes nodes under /sys/devices/system/node/, and numactl --hardware prints CPUs, memory sizes, and relative distances. A typical local distance is reported as 10, but remote numbers are firmware descriptions, not nanoseconds. Real latency and bandwidth depend on CPU generation, memory speed, socket count, snoop mode, BIOS topology mode, traffic mix, and line state.

As a working rule, remote DRAM is often on the order of ~1.3x to ~2x the latency of local DRAM, and remote bandwidth can fall much more sharply because inter-socket links are shared. Treat that as an engineering range, not a specification. Measure the actual platform and topology mode with the access pattern you care about.

Modern sockets can themselves be NUMA topologies. Intel SNC (Sub-NUMA Clustering) exposes multiple locality domains inside one socket by associating subsets of cores, LLC slices, and memory controllers more closely. AMD EPYC BIOSes expose NPS (Nodes Per Socket) modes such as NPS1, NPS2, and NPS4 on supported generations. A "socket" is no longer necessarily the smallest performance island; the right target may be the NUMA node nearest a PCIe root.

Linux allocation policy is lazy and page based. malloc usually reserves virtual address space; physical pages are committed when first faulted. Under the default policy, pages tend to be allocated on the node of the CPU that first touches them. This first-touch behavior helps when each worker initializes its own shard, and hurts when one initialization thread accidentally places a whole data structure on one node.

NUMA-aware placement is therefore a joint decision about threads and pages:

• bind execution with CPU affinity, for example via sched_setaffinity, pthread_setaffinity_np, taskset, or numactl --cpunodebind;
• bind or bias memory policy with mbind, set_mempolicy, numactl --membind, numactl --interleave, or libnuma calls such as numa_alloc_onnode;
• discover where code is running with getcpu or sched_getcpu, and avoid assuming a thread stayed there unless affinity or scheduler policy says so.

Migration is not free. If the scheduler moves a hot thread from node 0 to node 1, its private cache footprint is cold, its pages may remain on node 0, and ownership for written lines may move. Automatic NUMA balancing can migrate pages, but it is reactive and heuristic; it is not a substitute for deliberate placement in a dataplane, driver, database shard, or packet-processing loop.

The NIC case makes NUMA concrete. A PCIe device sits below a root complex local to a NUMA node or locality domain. Linux commonly exposes this through sysfs, for example /sys/bus/pci/devices/0000:af:00.0/numa_node, where -1 means the kernel does not know. The receive descriptor ring, completion queue, packet buffers, DMA mapping activity, interrupt target, and polling thread should normally live on CPUs and memory local to that device. If the NIC DMAs into memory attached to a remote socket, the write path crosses the interconnect. If a polling thread on another socket then reads the descriptors and packet data, the data crosses again, and coherence traffic follows cache-line ownership. At 10 Gb/s this may hide in headroom; at 100 Gb/s, 200 Gb/s, or faster, it becomes an architectural bug disguised as tail latency.

NUMA does not change the rules of caches, TLBs, atomics, or barriers. It changes the distance over which their consequences are paid. A DMA buffer on the wrong node still works, which is why the bug survives tests, but every packet pays rent to the topology. The chapter began with memory as the bottleneck; NUMA is the reminder that "memory" is not a place. It is a set of places, connected by finite links, and correct low-level performance work begins by knowing which place each byte, core, and device belongs to.

Sources

• Linux kernel NUMA memory policy documentation
• Linux man-pages: numa(3)
• Intel Xeon Processor Scalable Family technical overview
• AMD Optimizes EPYC Memory with NUMA