Caching Strategies for Heterogeneous Memory Hierarchies

Every server built on CXL, HBM-attached compute, or a NUMA topology with more than two distance classes now runs on memory that is not one thing. It is several pools, at several latencies, at several price points, and the kernel’s job is to make a workload behave as if it were running on the fast pool alone. That illusion is maintained by a caching strategy: which bytes live in the expensive, low-latency tier right now, and how the system decides when that answer should change.

This is not page cache in the “cache disk contents in RAM” sense that most engineers learn first. It’s memory-tiering: DRAM near a socket, CXL-attached DRAM one hop away, and increasingly HBM stacked on the compute die itself, all managed as a single address space with an internal promotion/demotion economy. The mechanism is deceptively close to the pieces we’ve already taken apart in this series — the thermal_pressure single-writer/multi-reader discipline from the power-management article, the TOCTOU hazards from HMM page migration, and the batching model from disaggregated-memory data movement all reappear here, because tiering sits at the intersection of all three problems: it’s a scheduler-adjacent decision, it’s a page-migration mechanism, and it’s a data-movement pipeline.

We’ll build a working, from-scratch model of a promotion/demotion controller — the same shape as the kernel’s node-demotion logic — and validate it the way this series always does: strict warnings, ThreadSanitizer, AddressSanitizer/UBSan, and Valgrind, with every bug the tools actually found left in the record.

Linux’s memory model assumed rough uniformity for a long time. NUMA support (2.6-era) was the first crack: numactl, mbind(2), and the zonelist fallback order acknowledged that “far” memory existed, but the kernel’s default policy was still “avoid it,” not “manage it as a tier.” Hot-page migration existed almost by accident, via automatic NUMA balancing (task_numa_fault), which moves pages toward the CPU accessing them — a scheduler-driven heuristic, not a capacity-driven one.

The real shift came from two directions converging. First, persistent memory (NVDIMM, Optane) forced the kernel to treat a byte-addressable tier with meaningfully different latency as first-class, via dax/kmem hot-add of PMEM capacity as a NUMA node. Second, and more recently, CXL 2.0/3.0 memory expanders made “add a slower memory node at runtime over a fabric link” a mainstream deployment pattern rather than a persistent-memory niche. The kernel’s answer, landing across 5.x and 6.x, is explicit tiered-memory support: node_demotion[] rankings, struct memory_tier, and reclaim paths that demote cold pages to a slower tier instead of only ever writing them to swap. HBM-as-cache and HBM-as-a-node are the mirror image at the fast end of the same problem.

It’s worth being precise about why “just use NUMA balancing” was never a sufficient answer on its own. Automatic NUMA balancing exists to solve a locality problem: a task and the memory it touches most should end up on the same node, and the mechanism is fundamentally task-centric — it samples hint faults generated when a thread touches memory it doesn’t currently have local, and either migrates the memory toward the thread or the thread toward the memory. Tiering is a capacity-and-cost-centric problem instead: even a task pinned to a single node might have a working set larger than that node’s fast-tier capacity, in which case no amount of locality migration helps — some pages simply have to live in the slower tier, and the question becomes which ones. The two mechanisms coexist in the kernel today and, as Section 4 covers, actively interact with (and occasionally fight) each other.

The ACPI HMAT (Heterogeneous Memory Attribute Table), standardized specifically to let firmware describe relative latency and bandwidth between initiator/target node pairs, is what finally gave the kernel a principled way to build node_demotion[] at boot instead of relying on hand-tuned NUMA distance heuristics that predate the idea of intentionally slower memory tiers existing at all. Before HMAT, “distance” in numactl --hardware output described interconnect topology for locality purposes; it was never designed to express “this node is 3x slower and that’s expected, rank it as a demotion target,” and retrofitting that meaning onto SLIT (System Locality Information Table) distances was a stopgap at best.

The problem has three parts, and all three are load-bearing:

Classification. You cannot promote or demote what you cannot rank. The kernel needs a cheap, continuous signal for “how hot is this page” without turning every memory access into an instrumented event. PTE accessed bits, sampled periodically, are the classic mechanism; DAMON generalizes this into region-based sampling with configurable granularity — instead of tracking every page individually (expensive at scale), it groups adjacent addresses into regions and tracks access frequency per region, splitting and merging regions adaptively as access patterns shift. The tradeoff is resolution versus overhead: coarse regions under-promote genuinely hot sub-ranges, fine regions burn CPU cycles and memory on bookkeeping that dwarfs the pages being tracked.

Capacity pressure. The fast tier is small by definition — that’s why it’s fast. Promotion is not just “move it,” it’s “move it, and evict something else, under contention from every other thread that’s also trying to promote something.” This is where naive designs quietly become O(n) or worse: if promotion decisions require scanning the entire fast-tier resident set to find an eviction candidate, and every worker thread’s hot access can trigger that scan, the “fast” tier’s management overhead can end up dominating the latency win it was supposed to provide. Real implementations amortize this with approximate LRU/LFU structures (multi-queue, clock-based) rather than exact global ranking, precisely to keep the eviction-candidate search cheap.

Consistency during migration. This is the part every kernel engineer underestimates the first time. A page being migrated has two physical locations for a brief window, and every other CPU in the system might have a stale TLB entry, a cached PTE, or literally be inside a load instruction targeting the old physical address at the exact moment the migration commits. Get this wrong and you don’t get a crash — you get intermittent, silent data corruption, because a reader reads new bytes at an old address, or old bytes at a location that’s already been repurposed for something else. Worse, this class of bug is load-dependent and interleaving-dependent: it can pass a full CI run and still corrupt data in production under a traffic pattern that happens to widen the race window, which is exactly why Section 11’s bug history matters more than any single clean test run.

Our demo isolates exactly this third part, because it’s the part sanitizers and casual testing are worst at catching.

The subsystem stack, top to bottom:

• Access tracking — mm/damon/ (DAMON) or the older NUMA-balancing hint-fault path (mm/mprotect.c‘s NUMA_HUGE_PAGE/hint-fault plumbing, task_numa_fault() in kernel/sched/fair.c). Both exist to answer “which regions are hot” without a per-access trap.

• Promotion/demotion engine — mm/migrate.c‘s migrate_pages() is the mechanical core: it isolates a page from the LRU, allocates a destination, copies content, retargets page tables via an rmap walk, and does a TLB shootdown. Tier ranking comes from node_demotion[], populated at boot from ACPI HMAT (Heterogeneous Memory Attribute Table) distance data.

• Scheduler interaction — this is the genuinely hard cross-cutting concern. NUMA balancing wants to move the task to the memory; tiering wants to move the memory to wherever it’s hot. These can fight: a demoted page can get re-promoted seconds later because the scheduler didn’t also migrate the thread that keeps touching it.

• Memory manager — struct page, zonelist, and the rmap machinery that lets migration find every PTE pointing at a physical page so it can be retargeted atomically with respect to the TLB.

• Device layer — cxl_core/cxl_mem register CXL expander capacity as dax devices, which kmem then hot-adds as ordinary (but ranked) NUMA nodes.

The core abstraction is a hotness-ranked cache with lazy, asynchronous eviction — structurally identical to a CPU cache’s LRU/LFU replacement policy, but at page granularity and running as software rather than hardware state machines. Two properties make this harder than a CPU cache:

1. The “hardware” here is other threads. A CPU’s cache controller has exclusive ownership of tag arrays. Our promotion engine competes with the very readers whose access patterns it’s trying to track, and it must publish tier changes in a way that’s safe against a reader who is mid-access at the instant of publication.

2. Eviction is not free — it’s a copy. Demoting a page means copying its contents to the slow tier before it can be reused for something else. Until that copy completes and is visible, the fast-tier physical location must remain valid for anyone still reading the old resident.

That second property is the one our demo is built to expose, because it’s exactly where a naive migration path breaks.

https://github.com/sysdr/howtech-p/tree/main/Developing_caching_strategies/tiering-lab

1. A worker touches a logical block; its access counter is incremented.

2. If the block is cold, done — no state changes.

3. If the block crosses the hot threshold and isn’t already resident in the fast tier, promotion begins.

4. If the fast tier is full, the coldest current resident is selected for eviction back to the slow tier.

5. The controller must wait for any reader still pinning the physical slot being reused, then copy bytes into the destination.

6. The {tier, pointer} pair is published atomically — never as two independent writes a reader could observe half of.

7. A reader who started before publication and is still using the old (now-stale) buffer must be prevented from having that buffer’s bytes stomped out from under it — this is the retry/pin loop on the error path in the diagram.

8. Control returns to the caller with a byte-for-byte consistent view, no matter how the migration interleaved with the read.

The demo’s structures are a direct, minimal analogue of the real subsystem:

In the real kernel, the corresponding structures are struct page (physical residency and refcount), struct memory_tier and node_demotion[] (tier ranking), and struct damon_region (the access-frequency estimate that drives promotion decisions). The pattern our seq field encodes — publish a compound piece of state as a single atomic transition, not as independent field writes — is exactly what seqcount_t gives the kernel for structures like struct mm_struct‘s write_protect_seq, and what page-table generation counters give mmu_notifier consumers.

Two things matter at the instruction level. First, b->data and b->tier must be genuinely atomic types, not plain fields “protected” by fences around them — a fence orders atomic operations relative to each other, it does not make a concurrently-written plain load/store defined behavior. This is a distinction the C11 memory model is precise about and that our first fix attempt got wrong (see Section 11). Second, the seqlock read pattern (load seq → load fields → fence → reload seq → compare) exists specifically to avoid a full memory barrier or lock acquisition on every read, at the cost of an occasional retry — the same tradeoff seqcount_t makes for jiffies and the VDSO’s getnstimeofday path, both of which are read far more often than written.

On real hardware, the migration path also has to reckon with TLB shootdown cost: retargeting every CPU’s page table entry for a migrated page requires an IPI to every core that might have cached the old translation, which is why migration is batched and why the kernel is conservative about promoting pages that will just get demoted again next scan.

The controller’s cost model has three terms: the tracking overhead (cheap, amortized), the migration copy (a memcpy at BLOCK_SIZE granularity — in the kernel, 4 KiB or 2 MiB for THP), and the retry cost imposed on readers racing a migration in flight. Under our full workload (8 workers, 50,000 ops each, promotion interval of 20 ops — deliberately aggressive to expose races), the fixed build produces:

Total recorded accesses: 400000 (expected 400000)
Corruption events detected by readers: 0
Seqlock read retries: 162716

Retries are not free, but they are cheap relative to what they replace: a full mutex acquisition on every single memory touch. 162,716 retries against 400,000 reads (roughly 40%) sounds high, but each retry costs a few atomic loads and a fence, not a syscall or a blocking wait — this is the same bet seqcount_t makes throughout the kernel, and it holds because writers (migrations) are relatively rare compared to reads.

It’s worth comparing this against the naive alternative most engineers reach for first: taking g_migration_lock on every read, not just every migration. Measuring both variants directly (same machine, same workload):

Variant 8 workers, 400K ops 32 workers, 1.6M ops Seqlock + pin (this design) 0.048s avg 0.186s avg Full mutex on every read 0.050s avg 0.201s avg

At 8 workers the gap is within noise — worth stating plainly rather than dressing it up, since this workload’s critical section (a 256-byte compare) is small enough that mutex overhead doesn’t dominate at low contention. At 32 workers the lock-based variant is consistently ~7-8% slower, and the gap should widen further with larger block sizes or higher core counts, since the mutex fully serializes all reads across all blocks — including reads to blocks nowhere near an active migration — while the seqlock only imposes a cost on the specific block being migrated, and only for the duration of that migration. The honest takeaway: at this demo’s scale the lock-free design’s benefit is real but modest, not dramatic; its value compounds with core count and contention, which is exactly the regime real memory-tiering hardware operates in.

The other number worth watching under a real workload is the eviction spin in promote_block‘s pin-drain loop (sched_yield() until a pin count reaches zero). In this demo it resolves in microseconds because the “read” being waited on is a 256-byte comparison loop. In the kernel’s actual migration path, the equivalent wait is bounded by migrate_pages()‘s retry-with-backoff logic around page_count(), and a page pinned for an extended I/O operation can genuinely stall a migration attempt — which is one reason the kernel biases toward not migrating pages that are under active DMA or pinned for get_user_pages(), rather than waiting indefinitely.

The gauntlet, run in order:

gcc -Wall -Wextra -Werror -O2 -pthread -o tiering_fixed_gcc tiering_fixed.c
clang-18 -Wall -Wextra -Werror -O2 -pthread -o tiering_fixed_clang tiering_fixed.c
clang-18 -fsanitize=thread -O1 -g -pthread -o tf_tsan tiering_fixed.c && ./tf_tsan
clang-18 -fsanitize=address,undefined -O1 -g -pthread -o tf_asan tiering_fixed.c && ./tf_asan
valgrind --leak-check=full ./tf_vg

Beyond the sanitizer gauntlet, the demo carries its own correctness oracle: every block’s canonical content is a fixed byte pattern ((uint8_t)block_id repeated), so any reader can independently verify it got a coherent view without needing a race detector to be watching at that exact moment. This matters because — as Section 11 shows in detail — some of these bugs did not reproduce under TSan’s own instrumentation until contention was cranked up, and one class of bug (stale-buffer reuse) is invisible to TSan and ASan entirely under certain interleavings; the oracle caught it when the sanitizers, that run, did not.

This is the honest record of what actually broke, in the order it broke, while building this demo. Nothing here is retrofitted or smoothed over.

Failure 1 — lost updates on the access counter. The first version used a plain long access_count incremented with count++ from multiple worker threads. ThreadSanitizer flagged it immediately:

WARNING: ThreadSanitizer: data race (pid=1276)
  Read of size 8 ... by thread T1: #0 promoter_fn tiering_buggy.c:157
  Previous write of size 8 ... by thread T2: #0 touch_block tiering_buggy.c:71
SUMMARY: ThreadSanitizer: data race tiering_buggy.c:71:20 in touch_block

At -O0 with contention deliberately increased (8 workers, promotion every 20 ops), the plain build also produced observably wrong totals: Total recorded accesses: 399483 (expected 400000) — a real lost-update, not a hypothetical one. Fix: _Atomic long with atomic_fetch_add_explicit.

Failure 2 — torn reads on the tier/pointer pair. Even after fixing the counter, the correctness oracle kept firing: Corruption events detected by readers: 5 on a run with a perfectly correct access total. The bug was structural, not a simple race TSan would flag on every run: tier was flipped to its new value one line before data was repointed, so a reader landing between those two writes would see a tier that didn’t match the buffer it was about to read. The fix was a seqlock-style publish: bump a sequence counter to odd, perform both writes, bump it back to even; readers snapshot the sequence before and after their read of the pair and retry if it moved or was caught mid-flight (odd).

Failure 3 — the seqlock alone wasn’t enough. After adding the seqlock, corruption persisted at a low but nonzero rate, with zero retries recorded — meaning the seqlock itself was never catching a torn metadata read, so the bug had to be somewhere else. The actual cause: even a reader who validates a perfectly consistent {tier, data} snapshot can still be handed a pointer into a buffer that gets reused for a different logical block while the reader is mid-comparison, because nothing tracks how long that pointer stays “in use” once the metadata check passes. This is the same reason kernel page migration takes an extra get_page() reference and checks page_count() before repurposing physical memory — a seqcount protects metadata consistency, not buffer lifetime. Fix: a per-slot pin count, incremented after seqlock validation (with a re-check to catch the pin racing the migration itself), and eviction now spins on sched_yield() until the pin count it’s about to invalidate reaches zero.

Failure 4 — the same hazard existed on the slow-tier side too. After fixing the fast-tier pin, TSan still found a live race:

WARNING: ThreadSanitizer: data race (pid=1724)
  Read of size 1 ... touch_block tiering_fixed.c:122
  Previous write of size 8 ... promote_block tiering_fixed.c:161 (memcpy)
  Location is global 'g_slow_pool'

I had only pinned the fast pool, on the assumption that each block’s slow-tier slot was exclusively its own and therefore stable. It’s not: every demotion overwrites that same slow slot with new content, so a slow-tier reader from a previous promote/demote cycle can still be mid-read when a later demotion lands. The fix is structurally identical to Failure 3 — a g_slow_pin[] array, indexed by block id, drained before any demotion memcpy.

Failure 5 — volatile is not synchronization. TSan’s last complaint was on the shutdown flag: g_stop was volatile int, toggled by the main thread and polled by the promoter. volatile only prevents the compiler from caching the value in a register across loop iterations; it makes no atomicity or ordering guarantee under the C11 memory model, and TSan correctly flagged the plain read/write as a race. Fixed by making it _Atomic int.

Five real, sequential fixes — not one. That progression is the actual lesson: seqlocks solve metadata consistency, refcounting/pinning solves buffer lifetime, and they are not substitutes for each other.

• CXL memory-expander tiering in modern data-center fleets, where a fraction of a node’s memory footprint sits behind a CXL switch at ~2-3x local-DRAM latency, and node_demotion[] ranks it below local DRAM but above swap. Operators typically size this tier for capacity headroom (letting a host run workloads whose working set exceeds locally-installed DRAM) rather than as a performance win in itself — the win is avoiding swap-to-disk latency for the coldest fraction of a large working set, not making the hot path faster.

• HBM-as-last-level-cache on accelerator-attached CPUs, where HBM is exposed as a fast NUMA node rather than transparent hardware cache, pushing the promotion/demotion decision into software exactly like this demo. This trades hardware cache-controller simplicity for software visibility: an administrator or a workload-aware daemon can pin known-hot structures directly rather than relying on an opaque hardware LRU, at the cost of needing exactly the migration-correctness discipline this article works through.

• DAMON-driven proactive reclaim (DAMON_RECLAIM), which uses the same access-classification signal described in Section 4 to demote cold anonymous pages before memory pressure forces a more expensive synchronous reclaim. This is the “classification” half of Section 3’s problem statement running in production today, independent of whether a slower memory tier or swap is the eventual destination.

• Database buffer-pool tiering at the application layer — PostgreSQL’s shared_buffers and various embedded-KV engines increasingly implement their own hot/cold classification over a two-tier storage model (DRAM plus NVMe or DRAM plus CXL), because they can exploit domain knowledge (query patterns, index structure) that a general-purpose kernel mechanism can’t assume. These application-level tiering layers hit the identical migration-consistency hazard from Section 11 whenever a background compaction or eviction thread races a foreground query thread against the same buffer.

• Cross-referencing this series’ disaggregated-memory article: the batching DMA-descriptor model there and the migration copy here are the same operation — move bytes between tiers — viewed from the data-movement side versus the placement-policy side. The HMM/GPU page-migration article’s TOCTOU fix (sequence-counter retry plus page pinning) is, in retrospect, the exact same two-part pattern this article’s Failures 3 and 4 rediscover independently: a sequence counter alone validates metadata, and pinning is the separate mechanism required to protect the underlying buffer’s lifetime.

startup.sh —docker builds both the intentionally buggy version and the fully fixed version, runs the entire validation gauntlet, and prints the actual sanitizer/oracle output for comparison. To reproduce:

chmod +x startup.sh --docker
./startup.sh --docker

Expect to see the buggy build’s TSan race reports and nonzero corruption counts, immediately followed by the fixed build passing all four gauntlet stages with a zero-corruption oracle result across multiple repeated runs — the actual before/after evidence from Section 11, regenerated live rather than pasted from a prior run.

• Never publish more than one logically-related field as a bare sequence of independent writes if any reader can observe them mid-sequence; use a seqlock, a single atomic tagged pointer, or RCU.

• A seqlock protects metadata consistency, full stop. If the metadata points at a buffer whose lifetime isn’t otherwise pinned, you have a second, independent bug class to solve — Failures 3 and 4 are the same bug in two different pools because I initially reasoned about “the fast pool” as the special case rather than recognizing the general pattern.

• volatile is for hardware MMIO and signal handlers, not for cross-thread synchronization; reach for _Atomic or explicit fences instead, and let a race detector confirm rather than assume.

• Run correctness oracles alongside sanitizers rather than instead of them. TSan caught four of these five bugs on the runs shown, but the run that mattered for Failure 3 showed zero TSan warnings and nonzero corruption — sanitizers report what they observe in that execution, not what’s structurally possible.

• Treat eviction as “reserve, drain, then reuse,” never “reuse, then hope nobody’s still reading it.”

Heterogeneous memory tiering is a caching problem wearing kernel clothing: classify hotness cheaply, promote and evict under real capacity pressure, and — the part that actually breaks in production — keep migration invisible to every reader that might be mid-access when a page moves. The five real bugs in this article’s build history trace the exact fault line: an unsynchronized counter, a torn compound-state publish, and — the deeper lesson — a buffer-lifetime hazard that survives even a correctly-implemented seqlock, because consistency of what you’re pointed at and safety of how long that pointer stays valid are two different guarantees that must both be engineered, not one.