Cornucopia Reloaded: Load Barriers for CHERI Heap Temporal Safety

Use-after-free remains one of the most exploited classes of software bug, and the CHERI hardware that already blocks out-of-bounds access cannot stop it, because a pointer to freed memory is still a perfectly valid pointer; the fix is to hold freed memory aside until every pointer to it has been erased from the machine, but the erasing must somehow be atomic with respect to a program that keeps running and keeps copying pointers — the previous system watched every pointer WRITE and then froze the program to catch up, pausing it for tens of milliseconds and sometimes over a second; this paper (Cambridge, Microsoft and SRI) watches every pointer READ instead, so the program can never obtain a stale pointer and therefore never creates work the sweeper must redo, collapsing the freeze to tens of microseconds.

Why this problem is worth solving

The gap this paper closes is specific, and it helps to see why the existing protection does not reach it.

The approach has an obvious cousin, and the difference between them is what makes it tractable.

What people did before, and where it broke

• Sweep with the program stopped. CHERIvoke establishes the approach: pause the program, walk its memory, destroy every capability pointing into quarantine, resume. Correct and simple, since nothing changes underneath the sweeper.
• But the pause is the whole runtime of a sweep. Measured here on pgbench, the fully sequential version puts its 99th-percentile transaction 27 milliseconds behind the median, with a median freeze of 20 milliseconds.
• Overlap the sweep with the program, then catch up. Cornucopia adds concurrency by using a per-page trap on capability STORES: a second core sweeps while the program runs, noting which pages get written, and then the world stops only to re-sweep those. This genuinely helped, cutting pause times by 70 to 90 percent on large-heap workloads.
• But catching up is not guaranteed to converge. The program can dirty pages as fast as they are cleaned, so the residue is not reliably small and the only way to be sure of finishing is to freeze. On Morello this still means median pauses reaching 30 milliseconds, with 92 measured pauses over a second — and the authors note that adding a second concurrent pass barely helped while increasing total work.
• Colour the memory and the pointers instead. Arm’s Memory Tagging Extension and similar schemes attach a few metadata bits to memory granules and to pointer addresses, checking they match on dereference, and recolouring on reuse. Cheap and deployed at scale.
• But it is probabilistic and mostly used reactively. The colours must stay secret from an attacker who can forge pointers, and precise trapping of stores is expensive enough that production deployments track imprecisely, flagging violations for later analysis. That is a surveillance-and-patch posture rather than a deterministic fail-stop one.
• The gap. Everyone was watching the operation that CREATES the problem — writing a pointer somewhere new. Nobody had asked what happens if you watch the operation that lets the program obtain a stale pointer in the first place, which turns out to change the structure of the problem rather than its constant factors.

How watching reads removes the catch-up phase

The idea

Watch the operation that lets the problem spread, not the one that spreads it. The previous design watched capability stores, which is the natural choice: a store is what puts a stale pointer somewhere new, so tracking stores tells you exactly which pages need re-examining. The trouble is that this makes the program an adversary of the sweeper — every store creates work, the program can create work faster than the sweeper retires it, and the residue can only be bounded by freezing. Watching loads inverts the relationship completely. If the program cannot LOAD a stale capability, it cannot store one either, so anything it writes during the sweep is guaranteed clean by construction. The authors put the resulting invariant crisply: any pointer in a thread’s registers did not point into quarantine as of the last revocation, and progress is measured as pages not yet scanned. Compare the old invariant, phrased over pages marked dirty, which advances only when the world stops. Choosing the checkpoint that makes progress monotone, rather than the one that most directly names the problem, is the same shift-where-you-intervene move covered elsewhere on this site where acting at the point that generates the difficulty turns an unbounded chase into a bounded one.

Borrow forty years of collector engineering. The paper is explicit that this is not a new idea so much as a transplant. Garbage collectors faced exactly this problem — inspect every pointer while the program runs — and worked through stop-the-world, then incremental, then concurrent designs, arriving at BARRIERS on the program’s loads and stores that maintain collector invariants. Cornucopia’s page-dirty tracking is a store barrier in the style of Boehm, Demers and Shenker, and card-marking collectors. This paper adds a load barrier in the style of Appel, Ellis and Li, as shipped in Azul’s pauseless collector, whose defining invariant is that the object graph the program sees outside barrier code looks as if collection had already finished. What is new is doing it for revocation, where the task is easier because nothing must be traced, and doing it with architectural support. Notably the authors had CONJECTURED this direction in the Cornucopia paper itself and describe this work as quantitatively affirming that intuition — a rare case of a group publishing the refutation of its own approach.

Make the hardware feature fit the algorithm, not the other way round. A straightforward load barrier would put a flag in every page table entry, cleared at the start of an epoch and restored as pages are cleaned. That means updating every entry TWICE per epoch, each with the address-translation invalidation traffic that implies, which for a large address space would swamp the benefit. Morello and CHERI-RISC-V instead added, specifically for this use, a comparison: each page table entry checks one of its bits against a GENERATION bit held in a per-core register. In the steady state they agree and loads proceed. Flipping the core register — one write, per core — instantly arms the barrier across the whole address space, and each entry is then updated exactly once as its page is swept. The expensive global operation becomes a local one. Replacing a sweep over metadata with a single version counter that invalidates everything at once is the same indirect-through-a-generation trick covered elsewhere on this site where bumping one number retires an entire set of stale entries without touching any of them.

Two ways to sweep a running program

that database has a heap of only 23 MiB but cycles 55 GiB through it, a ratio of freed to allocated bytes of about 2500
the largest SPEC workload has a 625 MiB heap cycling 66.9 GiB, a ratio of 110, so its quarantine fills far more slowly

Why it works

• The program can only load checked capabilities → it can only ever store checked capabilities → so pages it writes during a sweep are clean by construction and never need revisiting, which is the entire source of the old catch-up phase.
• Progress is measured as pages not yet scanned, which only decreases → the sweeper cannot be given new work by the program → so termination is guaranteed without freezing, and the freeze covers only registers and core synchronisation.
• Page table entries compare against a per-core generation bit → arming the barrier across an address space is one register write per core → so entries are touched once per epoch as pages are swept, instead of twice with invalidation traffic.
• The faulting thread sweeps its own page and re-runs the load → the program repairs memory instead of waiting for someone else to → converting a synchronous global stall into short work distributed over the pages actually touched.
• Not rescanning pages means fewer memory accesses overall → memory traffic falls to a median 87 percent of the previous design across SPEC and under half on the database → so the pause improvement costs nothing in bus bandwidth.

What it costs (trade-offs and scope)

• It needs new hardware. The generation-bit comparison in page table entries was added to Morello and CHERI-RISC-V for this purpose. The authors are direct that the result is a strict improvement only if that modest hardware support can be provided.
• Use-after-free is still possible; only use-after-reallocation is stopped. A stale pointer keeps working until the next sweep, as if the object’s lifetime were extended. What is guaranteed is that it never aliases a DIFFERENT later object. The authors argue this gap is a tolerable trade and sketch how composing with memory colouring could close it.
• Throughput is unchanged, not improved. The gRPC benchmark loses 12.82 percent of its queries per second, statistically indistinguishable from the previous design, and SPEC overheads reach 29.4 percent on the worst case. The contribution is entirely in the tail.
• The extreme tail can still misbehave. On gRPC both designs push the 99.9th percentile to roughly ten times baseline, with some transactions stalled across two whole epochs — behaviour not seen on the database workload and not fully explained.
• The comparison baseline is a re-implementation. The authors rewrote Cornucopia to share code with the new design and say plainly that what they call Cornucopia is their imperfect re-implementation, not the original software. They also list known defects around copy-on-write aliases that the benchmarks happen not to trigger.

The evaluation

Everything runs on Morello, an experimental CHERI-extended ARMv8.2 machine with four cache-coherent 2.5GHz cores and 64 GiB of memory — a real desktop-class system rather than the FPGA prototypes earlier CHERI work relied on. Four configurations are compared: the new design, a re-implementation of the previous one, that re-implementation with its concurrent phase removed to stand in for the original stop-the-world approach, and a configuration that does all the quarantine bookkeeping but never sweeps, which provides no safety at all but isolates the cost of everything except revocation itself. Cores are pinned so the application, the sweeper and the rest of the system do not contend.

Check yourself

Sources

• Cornucopia Reloaded: Load Barriers for CHERI Heap Temporal Safety (author PDF, Cambridge Computer Laboratory) — ASPLOS 2024; the full 18-page paper, read in full for this explainer.
• ACM Digital Library (DOI 10.1145/3620665.3640416) — published version.