CARAT CAKE: replacing paging via compiler/kernel cooperation

Every program you run is handed fake memory addresses that hardware translates on every single access, and the machinery for doing that occupies about as much chip area as an L1 cache while consuming a substantial share of its energy; this work (Northwestern) asks what happens if you delete it entirely, letting programs run on real physical addresses while a compiler injects the protection checks and tracks every pointer so the kernel can still move memory around — and finds the resulting system performs about the same as paging.

Why this problem is worth solving

It helps to separate what the mechanism provides from how it provides it.

The concept that replaces the translation table is a bookkeeping one.

What people did before, and where it broke

• Make the pages bigger. Cover more memory per translation entry, so the buffer misses less often. Where it broke. Nothing, and it is genuinely effective, but it needs large runs of contiguous physical memory, which fragment. It also leaves all the translation hardware in place.
• Add more caching to the translation path. Page-walk caches, extra buffer levels, identifiers that avoid flushing on a context switch. Where it broke. Each addition is more hardware in the most timing-critical place in the machine, and the underlying trend is that workloads keep outgrowing whatever reach is provided.
• Manage memory in software, in a managed language. Runtimes have done exactly this for decades, tracking objects and references and relocating them freely. Where it broke. It only applies to programs written in languages that permit it, and it serves a different purpose than protecting arbitrary code in a general-purpose operating system.
• Trust the compiler and restrict the language. Historical machines did this, pairing physical addressing with a heavily restricted high-level language and a trusted compiler as the basis for protection. Where it broke. Restricting what programmers may write. The bet in this work is that compiler analysis has improved enough that the restriction is no longer necessary.
• Prototype the idea at user level. Earlier work by the same group implemented the tracking and checking inside a Linux process to measure what it would cost. Where it broke. It ran on top of paging rather than instead of it, so it could estimate overheads but could not build a process abstraction, handle heap expansion, defragment, or do any of the things a kernel actually has to do.
• The gap. Everyone extending paging accepts the hardware as given. Nobody had built a kernel where the compiler and the runtime jointly provide protection, mapping and movement, which is the only way to find out whether the hardware could be removed rather than merely improved.

How a system runs without address translation

The idea

Address translation does not only cost its own area and power; it constrains the cache next to it. The direct costs are substantial and well documented — translation structures occupy roughly the area of an L1 cache, are estimated at 13 to 17 percent of a core power budget, and form a thermal hot spot. But the argument that stayed with me is indirect. First-level caches are indexed using the low bits of the address, which are the same in the program and physical views, so that the cache lookup can begin before translation finishes. That trick is what makes translation fast enough to tolerate, and its price is a cap on how many sets the cache may have, imposed to prevent two program addresses that refer to one location from occupying two cache entries. Remove translation and that constraint evaporates; the authors estimate first-level caches could grow from 64 to 256 kilobytes at the same energy and timing. A mechanism whose true cost is a limit it imposes elsewhere in the system, rather than the resources it consumes directly, is the same shape of problem as the translation reach work covered elsewhere on this site, which spends its effort on the consequences of a structure rather than the structure itself.

The whole thing turns on how many checks the compiler can prove away. Placing a permission check before every load, store and call is obviously correct and obviously unaffordable, so the design lives or dies on elision. Three mechanisms do the work: static proof that an access is within bounds, which removes the check entirely; relocation of a check out of a loop using induction variable analysis, so one check covers an entire traversal; and structural arguments that certain categories need no check at all, since the kernel itself established the stack, loaded the globals and owns the heap region. What makes this credible now rather than in 1980 is the quality of the underlying analysis — the framework used combines 31 separate alias analyses to build its dependence graph, and the paper states the relationship directly, that overhead is inversely proportional to the accuracy of that graph. Better analysis is not an optimisation here, it is the mechanism. Moving a responsibility out of hardware or human hands and into compiler analysis, accepting that the result is only as good as the analysis and that the trusted base shifts accordingly, is precisely the bargain the memory-model migration work covered elsewhere on this site makes.

Without a mapping, movement stops being lazy and becomes a garbage collector. This is the deepest consequence and the paper is clear-eyed about it. Paging relocates data by editing a table, so the data need not be touched and the work can be deferred until something faults. With physical addressing there is nothing to edit: relocating an object means copying the bytes and then finding and repairing every stored reference to the old address — which is why the compiler must track escapes in the first place, and why the runtime additionally scans registers and stack slots for pointers that the register allocator put there, exactly as a conservative collector does. The paper reframes the comparison rather than conceding it: the laziness of paging is purchased with mandatory translation on every single access, which this design avoids entirely. It also inherits a problem paging does not have, external fragmentation, addressed by compaction at three nested levels. Being forced to relocate objects eagerly and repair the references, rather than redirecting through an indirection layer, makes this a policy question about when to move and how much it costs — the same question the tiered memory placement work covered elsewhere on this site confronts from the side where the indirection still exists.

Following one relocation through the runtime

The prototype treats an entire stack as one allocation rather than tracking each variable, which keeps the bookkeeping affordable and requires each stack to be one contiguous chunk that can be grown or moved as a unit.

Why it works

• Most permission checks can be proven unnecessary rather than executed. A check before every access would be prohibitive → but static analysis can prove many accesses in bounds, hoist others out of loops so one check serves an entire traversal, and dismiss whole categories whose regions the kernel established itself → which is why the measured steady-state overhead comes out comparable to paging rather than catastrophic.
• The quality of the analysis directly sets the overhead. Every access the analysis cannot prove safe becomes a runtime check → so overhead is inversely proportional to how precise the dependence graph is → which is why the implementation combines 31 alias analyses, and why the authors argue the case for this approach strengthens as compiler research advances.
• Tracking escapes is what makes physical addressing survivable. Without an indirection layer, a relocated object leaves every stored pointer to it dangling → so the compiler records each place a pointer is written, giving the runtime a complete repair list → which turns relocation from impossible into merely expensive, at a cost proportional to references rather than to bytes.
• Managing at allocation granularity permits things pages cannot express. Paging protects and moves in fixed-size units → tracking individual allocations means protection follows arbitrary region boundaries and movement can happen for one object, a region, a whole process, or the kernel → and compaction can slide a region into an overlapping free chunk of any size.
• The bundle can be unpicked because only one part needed hardware. Protection is a check that some address is in some permitted set, and mapping is a question of where the kernel decided to put things → neither inherently requires translation on every access → only cheap relocation does, and paying for that eagerly with pointer repair turns out to be affordable at realistic rates.

What it costs (trade-offs and scope)

• None of the projected benefits were measured, because the hardware cannot be turned off. Paging cannot be deactivated on this architecture, so the prototype runs with identity-mapped one-gigabyte pages and still pays for having a translation buffer on the control path and for the cache constraint. The energy savings, area savings and larger first-level caches are all estimates from the literature, not results.
• The starting point was already unusual. The kernel used had identity-mapped paging from boot with no swapping and no page movement, so it had no deeply embedded assumptions to remove. The authors state plainly that they cannot speak to how hard converting a kernel that genuinely depends on paging would be.
• Compiler bugs become protection bugs. With paging, a compiler defect produces a kernel with a random bug; here it may be usable to subvert protection, because protection is what the compiler produces. The authors make this argument themselves, and offset it against removing hardware from the trusted base — where bugs are far harder to patch, as recent speculative execution vulnerabilities showed.
• Assembly must be transformed by hand and separately attested. Anything that reaches the executable without passing through the instrumenting toolchain has to be vouched for manually.
• Self-modifying code and just-in-time compilation are unsupported. The instrumentation is applied statically. The authors sketch how a dynamic version might work but did not build it.
• Encoded pointers defeat the tracking. A pointer stored in an obfuscated form, such as an exclusive-or linked list, will not be recognised as referring to its allocation. Simple arithmetic encodings can be followed through the intermediate representation; anything more complex requires the programmer to supply a decoding function, and failing that the object must be pinned and can never move.
• The library allocator was accommodated rather than redesigned. To make the comparison fair the standard allocator is used unchanged, which forces each heap to be a contiguous physical region purely to satisfy assumptions that allocator makes.
• Permissions can only be downgraded after a check succeeds. A permission change racing with an optimised check is resolved by forbidding upgrades, which the authors note is not intrinsic but is what the prototype does.
• The workload set is narrow. Nine benchmarks from two numerical suites. No server, database or web workload was attempted, because extending the process layer to support them was judged significant work.
• External fragmentation is a new problem the alternative does not have. A single physical address space means compaction is mandatory rather than optional, and a failing allocation must trigger something resembling a collection pass.

The evaluation

Check yourself

Sources

The paper is “CARAT CAKE: Replacing Paging via Compiler/Kernel Cooperation” by Brian Suchy, Souradip Ghosh, Drew Kersnar, Siyuan Chai, Zhen Huang, Aaron Nelson, Michael Cuevas, Alex Bernat, Gaurav Chaudhary, Nikos Hardavellas, Simone Campanoni and Peter Dinda, published at ASPLOS 2022, pages 98-114, DOI 10.1145/3503222.3507771. The authors are at Northwestern University, and the paper includes an artifact appendix.

This explainer is written from the full 17-page text. Everything above comes from the paper’s own sections: the introduction surveying the area, power and thermal costs of translation hardware with its cited figures, and the argument about cache indexing constraining first-level cache size; the description of the software stack including the compiler framework, whole-program bitcode aggregation, the analysis framework combining 31 alias analyses, and the properties of the host kernel including its identity-mapped boot configuration; the terminology defining allocations, frees, escapes, guards and regions, and the account of the earlier user-level prototype with its measured tracking and protection overheads and its enumerated limitations; the claimed benefits covering translation buffer removal, energy and area savings, the cache size estimate, arbitrary granularity management and the argument about patching protection bugs in software; the design covering compiler instrumentation of both kernel and user code, the categories of check that can be elided and why, the dependence on induction variable and scalar evolution analysis, the address space and region abstractions, the allocation and escape tables, the hierarchical guard optimisation, the movement hierarchy from allocations to the kernel itself, the register and stack scanning, and the three-level defragmentation scheme; the implementation aspects covering granularity, pluggable region data structures, the accommodation of the standard library allocator, the treatment of the stack as a single allocation, and the permissions race resolution; the process abstraction covering signed executables, position-independent linking, the trusted entry mechanism and the system call layer; the evaluation covering steady-state performance against two paging implementations, the migration measurement methodology with its fitted model, the pointer sparsity table, and the implementation size comparison; and the discussion of untested aspects including server workloads, dynamic compilation, garbage collection integration, virtualisation, swapping and pointer obfuscation.