Source-linked AI summary
CHERI-D Reincarnate: efficient multicore CHERI temporal memory safety through allocation reincarnation (draft version)
Yuecheng Wang, Jonathan Woodruff, Simon W. Moore
TL;DR
CHERI-D’s finite-width IDs can force memory quarantine when exhausted, limiting efficient temporal safety. Reinc decouples exhausted-ID quarantine from memory reuse through allocation reincarnation and coherent decentralized ID caching, reducing sweeping and quarantine overhead with low runtime cost across evaluated workloads.
Problem
CHERI-D’s finite-width generation IDs can become exhausted, forcing allocation memory into quarantine and limiting scalable temporal safety for larger objects and multicore systems.
Method
Reinc dynamically assigns new IDs to exhausted allocation slots, quarantines and later reclaims old IDs, and synchronizes private ObjID buffers using lightweight coherence mechanisms.
Results
1.7% average runtime overhead for SPEC CPU2006 INT, 0.7% for SQLite, and 0.3% for PARSEC, while substantially reducing sweeps and memory quarantine.
Takeaways & Limitations
Reinc enables immediate memory reuse while preserving strict temporal safety and extending decentralized CHERI protection to multicore, large-object workloads.
Takeaways & Limitations
Reinc currently protects heap allocations at the libc allocator layer, leaving kernel allocators and application-specific nested allocators for future work.
Abstract
from arXiv · showhide
We propose CHERI-D Reincarnate (Reinc), an architectural extension to CHERI for scalable and efficient temporal memory safety. Prior work CHERI-D has a finite-width generation ID stored at a fixed location, requiring an object to be quarantined when its ID is exhausted. Reinc further provides use-after-free mitigation while permitting immediate freed memory reuse for objects through allocation reincarnation: rather than quarantining an allocation slot upon ID exhaustion, Reinc dynamically assigns a new ID to that slot when its current ID is exhausted. Exhausted IDs are quarantined and later reclaimed, while the underlying memory remains available for immediate reuse. By quarantining IDs rather than memory, Reinc enables continuous reuse of memory in the common case, substantially reducing both memory-sweep frequency and quarantine memory overhead. Reinc further introduces coherent ID caching while retaining a fully decentralized ID organization. Temporal metadata remains colocated with the memory it protects, preserving locality while avoiding centralized metadata structures. To support multicore execution, Reinc connects physical coherence events to the virtually addressed ObjID buffer using lightweight reverse-map and filter-based mechanisms. We implement Reinc as a hardware-software co-design spanning CHERI-Toooba (superscalar FPGA softcore), QEMU, LLVM/Clang and CheriBSD. Across our evaluated workloads, Reinc substantially reduces memory-sweep frequency and memory quarantine while incurring low performance and hardware overhead.
1 Introduction
Reinc addresses the cost and scalability limits of CHERI temporal safety by quarantining exhausted IDs instead of allocation memory, enabling immediate reuse while supporting larger objects and multicore coherence. Across evaluated workloads, it reduces sweeping and quarantine overhead with low runtime cost.
- Prior limitations: CHERI-D statically associates finite-width IDs with allocation slots, forcing memory quarantine on ID exhaustion and disproportionately affecting large objects.Reinc instead dynamically assigns new IDs while quarantining exhausted IDs independently of their allocations.
- Motivation and contribution: Reinc quarantines exhausted IDs and reincarnates allocation slots under new IDs, allowing memory to remain immediately reusable until ID reclamation completes.This decouples ID exhaustion from memory quarantine and can avoid memory quarantine when reclamation finishes before available ID locations are exhausted.
- Contribution: Reinc extends ID-based temporal protection from objects smaller than 4 KiB to objects up to 1 GiB and adds lightweight coherence mechanisms for private ObjID buffers.The coherence mechanisms reuse existing cache-coherence invalidation and L1-replacement events.
- Evaluation: 1.7% average runtime overhead for SPEC CPU2006 INT, 0.7% for SQLite, and 0.3% for PARSEC, while SQLite requires 0 sweeps versus 267 under Cornucopia Reloaded.The reported evaluation also finds substantially reduced sweeping and memory quarantine overhead.
2 Background
CHERI supplies decentralized spatial protection, while prior temporal mechanisms use metadata validation, quarantine, or centralized validity tables. CHERI-D’s cached temporal metadata creates a multicore coherence problem because physical coherence events cannot directly identify virtually addressed ObjID-buffer entries.
- Cornucopia Reloaded: Cornucopia Reloaded delays reuse until revocation sweeps remove dangling capabilities, causing performance and memory overhead and lacking strict protection between deallocation and reuse.Its quarantine mechanism avoids metadata lookup on common-case accesses but postpones memory reuse.
- Prior temporal safety: Picasso centralizes object validity in a global bit-vector table, whereas CHERI-D distributes counters inline with allocations for greater scalability and metadata efficiency.Both validate metadata on memory access and invalidate capabilities to freed objects.
- CHERI-D: CHERI-D places allocation metadata inline and compares each capability’s ObjID with the corresponding memory ObjID, preserving decentralized temporal validation.Its finite-width generation IDs invalidate prior capabilities when advanced on deallocation, but exhaustion eventually triggers memory quarantine.
- Temporal metadata buffer: Private ObjID buffers are not naturally synchronized by conventional physical-address coherence, so a remote core may retain a stale ID after another core updates memory metadata.Virtual aliases further prevent a simple one-to-one mapping between coherence addresses and ObjID-buffer entries.
3 System and threat model
Reinc strengthens temporal safety against use-after-free and use-after-reallocation while retaining Cornucopia Reloaded’s user-space software topology and trust model. Its stated scope is user-space heap allocations; kernel and stack memory remain future work.
- Threat model: Reinc immediately revokes freed-object capabilities through ID checks, protecting against both use-after-free and use-after-reallocation.Unlike delayed reuse, the ID mechanism traps dereferences of dangling capabilities immediately on free.
- Trust model and software topology: Reinc retains MRS and the allocator as user-space components, with MRS managing metadata through allocator capabilities outside application-accessible bounds.The design requires no new privileged instructions while maintaining ID integrity in application code.
- Scope boundary: Reinc focuses on user-space heap temporal safety, leaving kernel and stack memory protection for future work.
4 Reinc Design
Reinc extends CHERI-D with dynamic allocation reincarnation, paired ID locations, strict coherent ID buffering, and ID-placement modes for objects up to 1 GiB. Its colocated metadata preserves spatial locality and avoids centralized metadata contention.
- Allocation reincarnation: Allocation reincarnation dynamically associates multiple IDs with an allocation slot, quarantining exhausted IDs while keeping the underlying memory reusable.The paired IDLOC encoding supports continuous reuse of allocation slots in the common case.
- Coherent ID buffering: Reinc specifies strict coherence for buffered IDs without fence instructions by reusing cache-coherence invalidation and L1-replacement events.The design targets private ObjID buffers while retaining decentralized ID management.
- Large-object ID design: Six additional ID modes and a new IDLOC encoding extend object-ID support beyond 4 KiB to larger objects spanning multiple pages.Modes 2–7 use progressively coarser alignment as supported object size increases.
- Metadata organization: Top-relative ID locations place metadata immediately beyond the capability top, often in unused allocation-slot space, while preserving locality between objects and temporal metadata.This organization avoids separate shadow memory and additional cache or TLB pressure from distant metadata lookups.
Concurrency-friendly ID placement.
Reinc separates ID exhaustion from memory quarantine by reincarnating allocation slots under new IDs, while extending ID-based protection to objects up to 1 GiB. Its top-relative placement modes preserve ID locations as capability bounds narrow, with exceptionally large allocations handled through unmapping.
- Allocations beyond 1 GiB are immediately unmapped on deallocation, using page-level virtual-memory protection instead of ID-based reuse.The approach targets exceptionally large allocations that are rare in measured workloads.
- Reincarnated allocation slots remain immediately reusable when their current IDs exhaust, while exhausted IDs are quarantined and later reclaimed after sweeping.Memory quarantine is needed only after all IDs associated with a slot are exhausted.
- ID quarantine reduces quarantine-induced memory pressure by allowing memory to remain in use indefinitely in long-running, allocation-intensive workloads.
- Modes 2–7 use progressively coarser top-relative ID-placement granularities to support allocations up to 1 GiB with a five-bit displacement.The granularities range from 1 KiB through 32 MiB.
- As object size increases, top-relative modes locate IDs relative to the capability upper bound, while modes 0 and 1 retain CHERI-D placement schemes for small objects.
- Reinc preserves the original ID location during bounds narrowing by incrementing IDLOC[4:0] when the reduced top crosses mode-specific granularity boundaries.IDLOC[5] remains unchanged, so reincarnation selection is independent of bound narrowing.
4.6 Coherence-Aware ID Management
Reinc keeps private ObjID buffers coherent by connecting physical cache-coherence events to virtually addressed entries without changing the timing-critical lookup path. It offers reverse-map precision or lower-cost Bloom-filter invalidation, both reusing existing L1 events.
- Stale private ObjID entries could validate revoked capabilities after another core updates an object’s ID, so subsequent accesses must observe the updated value.
- Reinc reuses coherence invalidations and local L1 replacements to connect physical events with the virtually addressed ObjID buffer without new coherence protocol changes.
- The reverse-map design selectively invalidates affected virtual ObjID entries, while aliasing physical lines conservatively flush both the ObjID buffer and reverse-map state.
- Algorithm 1 reconstructs ID addresses from the access address, capability top, ID mode, and IDLOC, using mode-specific granularity for larger objects.The reconstruction aligns addresses down to the relevant granularity.
- The Bloom-style filter ignores events that cannot affect cached IDs and conservatively flushes the ObjID buffer on possible matches.False positives are safe but cause unnecessary flushes.
5 Reinc Implementations
Reinc integrates allocation reincarnation, ID-level quarantine and reclamation, large-allocation unmapping, and coherent ObjID buffering across the CHERI software and hardware stack. Its coherence designs trade invalidation precision against hardware cost while preserving correctness through conservative replacement handling.
- On deallocation, Reinc increments the object ID to revoke freed capabilities and immediately returns the allocation slot for reuse, reincarnating it when the current ID is exhausted.
- When an ID reaches terminal value 254, Reinc marks it as 255, quarantines only that ID if another remains available, and accounts for its allocation size toward the virtual quarantine threshold.
- The revoker invalidates capabilities associated with exhausted IDs during a sweep, after which Reinc resets quarantined ID locations for future reincarnations.
- Allocations of at least 1 GiB are returned to the operating system with pages_unmap() on deallocation, providing use-after-free mitigation through removed virtual-memory mappings.
- The Bloom-filter design uses less hardware but may flush the entire ObjID buffer, whereas the reverse map uses more memory resources to normally invalidate only affected entries.
- Conservative invalidation on local L1 replacement preserves correctness but can introduce extra ObjID-buffer misses and ID accesses when eviction reflects cache pressure rather than modification.
6 Evaluation
Reinc is evaluated as a complete CHERI hardware-software co-design for hardware cost, temporal safety, performance, and quarantine behavior. Across these dimensions, it provides temporal-safety enforcement with low coherence and performance overhead while reducing sweeps and memory quarantine.
- Hardware and multicore coherence: Both coherence designs introduce limited FPGA resource overhead, while the reverse map increases LUT-memory use by 23.06% and avoids adding logic to the timing-critical ObjID lookup path.The reverse map selectively invalidates affected entries; the filter uses less hardware but may conservatively flush the entire buffer on false positives.
- Temporal safety: Reinc detected and trapped all 416 Juliet use-after-free vulnerabilities, passed all 1636 double-free tests, and rejected all four executable MSET cases involving access between deallocation and reuse.Both FPGA and QEMU prototypes executed all provided CWE-416 good cases; Reinc rejected four MSET cases that existing revocation did not cover.
- Performance: 1.7% average runtime overhead for Reinc across SPEC CPU2006 INT, while filter and reverse-map coherence add 3.2% and 2.5% average overheads, respectively.Reinc reduces overhead particularly for allocation-intensive workloads and substantially lowers DRAM traffic relative to Cornucopia Reloaded.
- Performance: 0.7% average SQLite overhead versus 4.3% for Cornucopia Reloaded, with maximum overhead reduced from 22.6% to 2.1%.The benchmark exercises allocation sizes beyond CHERI-D’s 4 KiB limit; filter and reverse-map configurations report 0.9% and 1.2% average overheads.
- Quarantine and sweep behavior: 267 memory sweeps for Cornucopia Reloaded versus 1 for Reinc, or 0 without ID-sweep reclamation, while quarantine events fall from 221K and 146K to 90.Reinc also reduces peak quarantine occupancy because reincarnated allocation slots do not consume quarantined memory.
- Hardware and multicore coherence: Reinc maintains low overhead when moving from one to two threads, and the filter-based design performs comparably to the more precise reverse map.The evaluation uses a two-core FPGA system with private L1 caches and a shared last-level cache.
7 Related work
Reinc builds on CHERI temporal-safety designs by invalidating objects through per-allocation IDs while preserving immediate memory reuse and decentralized metadata. It targets the scalability, reuse, and sweep limitations of prior approaches.
- 7 Related work: Unlike Cornucopia Reloaded and PoisonCap, Reinc combines strict use-after-free mitigation with immediate freed-memory reuse.Cornucopia Reloaded delays reallocation until sweeping, whereas PoisonCap improves quarantine efficiency without enabling immediate reuse.
- 7 Related work: Reinc uses per-allocation IDs to invalidate an entire object with one write, while reclaiming exhausted IDs without quarantining the underlying memory.This contrasts with memory-tagging approaches that limit reuse or require updating tags throughout large objects.
- 7 Related work: Figure 5 measures both average and maximum quarantine overhead as percentages of allocated memory across evaluated workloads.Average overhead is time-weighted, while Max-Q is measured at peak quarantine occupancy; SPEC CPU2006 uses reference inputs.
- 7 Related work: Reinc avoids centralized temporal metadata, retaining decentralized organization to improve scalability and locality for multicore systems.Centralized tables can introduce scaling, locality, address-translation, TLB, and metadata-cache costs.
- 7 Related work: Picasso uses a 21-bit capability color but centralized metadata, whereas Reinc requires 17 capability bits for decentralized metadata storage.Picasso’s smaller color fields would increase color reuse and revocation pressure.
8 Future work
The current Reinc implementation protects only libc-layer heap allocations and incurs wrapper overhead because software support sits outside the underlying allocator. Future work therefore targets broader allocator coverage and native allocator integration.
- 8 Future work: Reinc currently protects heap allocations at the libc allocator layer, leaving kernel and application-specific nested allocators as future extension targets.The paper identifies scalable protection across multiple allocation layers as an important direction.
- 8 Future work: The MRS wrapper adds allocation and deallocation overhead by recovering underlying allocations and metadata to locate and update object IDs.A Reinc-aware allocator could perform ID management directly using metadata already available on critical paths.
9 Conclusion
Reinc decouples temporal-identity reuse from memory reuse, reducing quarantine and sweep costs while supporting cross-core ID synchronization. The conclusion presents this as a scalable temporal-safety approach for multicore CHERI systems.
- 9 Conclusion: Allocation reincarnation lets exhausted allocation slots receive new ID locations instead of entering memory quarantine, while exhausted IDs are handled separately.This mechanism supports immediate reuse of the underlying allocation slot.
- 9 Conclusion: Reinc combines efficient cross-core ID synchronization with multicore temporal-safety support while preserving CHERI’s decentralized architecture.The conclusion positions the design for application- and server-class CHERI systems.
A SPEC DRAM traffic overhead
Figure 6 reports SPEC CPU2006 integer DRAM traffic overhead for Cornucopia Reloaded and Reinc relative to baseline CHERI without revocation.
- A SPEC DRAM traffic overhead: Figure 6 compares SPEC CPU2006 INT DRAM traffic overhead for Cornucopia Reloaded and Reinc against baseline CHERI without revocation.The supplied passage identifies the compared systems and baseline but does not report numerical outcomes.