Crabrix blog
Implement a safe Rust arena with owner identities, reusable slots and checked generations. Reject stale handles, test removal boundaries and plan persistence carefully.
· 14 min read
A project list stores documents in a vector. An asynchronous operation remembers that the selected document is at index three. The user closes that document, another document takes its place, and the operation eventually reports a result for index three. Every array access can be within bounds and every reference can obey Rust's borrow rules, yet the visible result belongs to the wrong document. Memory safety has not been violated; application identity has.
A generational handle separates the reusable position from the lifetime of its occupant. This article builds a small arena that stores values in slots, reuses empty slots and rejects handles from earlier occupants. It also gives each arena an owner identity, because a slot and generation alone cannot distinguish two independent collections. The implementation uses ordinary safe Rust and the standard library. Its purpose is to make the invariants understandable before choosing a mature arena library for a larger system.
An index promises a position in a collection under some set of mutation rules. A stable object identifier promises that a later lookup either finds the same logical object or reports that it no longer exists. Those are different promises. If your collection only appends and never removes, an index may satisfy your application's needs. If removal, compaction or asynchronous callbacks are involved, write down the mutation rules before deciding that an index is enough.
A handle in our arena contains an arena identity, a slot index and a generation. Lookup checks all three relevant conditions: the handle belongs to this arena, the index exists, and the slot still has the same generation and a live value. A missing object becomes None, which the caller can handle deliberately. There is no fallback to the new occupant, and the lookup never tries to reconstruct an object from a remembered address.
A vector may reallocate its storage when it grows. Rust's borrowing rules prevent safe code from retaining an ordinary borrowed element reference across a conflicting mutation that could invalidate it. A copied integer index has no such lifetime relationship. It remains a perfectly valid integer after the collection changes, even when its old meaning has disappeared. Solving relocation alone therefore does not solve the stale-identity problem.
Removal policies introduce further choices. Ordered removal shifts later elements, while swapping an element with the last position changes which object occupies a particular index. A slot-based arena avoids moving occupied logical positions during removal, but an empty position may later be reused. The generation is what distinguishes reuse from continuity. Think of these as separate decisions about memory location, ordering and object lifetime rather than treating every collection mutation as the same kind of instability.
Sources: Rust standard library: Vec storage and mutation operations
A new slot begins with generation zero and one live value. Removing that value makes the slot empty and advances its generation. The empty slot may then enter the free list, from which a later insertion can reuse it without changing the generation again. An earlier handle still carries the old generation, so it cannot access the new value. Each successful removal is the transition that invalidates the previous occupant's handles.
Generation exhaustion needs an explicit rule. Wrapping the largest generation back to zero could eventually make a very old handle appear current again. The example instead leaves an exhausted slot empty and permanently excludes it from the free list. A later insertion allocates another slot. This trades a theoretical amount of retained slot storage for a simple identity guarantee. The test suite forces exhaustion directly so the rule can be verified without attempting an impractical number of real removals.
Two freshly created arenas both have slot zero at generation zero. If a handle contains only those two fields, looking it up in the wrong arena could return an unrelated value. Our example allocates a process-local arena identity from an atomic counter and includes it in every handle. The counter uses a checked increment and refuses to create another arena after its identity space is exhausted; it never silently wraps into a previously issued identity.
The relaxed atomic ordering is sufficient for allocating distinct counter values. The counter does not publish the arena's contents or provide synchronization for accessing them. An arena still requires normal Rust borrowing, or a separately chosen synchronization strategy when shared across threads. Mixing those responsibilities is a common source of confusing designs: a unique number can identify an owner without making the owner's mutable data safe for concurrent access.
Save this as main.rs. A normal run demonstrates slot reuse, rejection of a stale handle, mutation through a current handle and rejection of a handle from a different arena. Compiling the same file as a test harness also runs two boundary tests. The structures intentionally keep their fields private to the module, and the arena is not given an automatic clone implementation that could accidentally duplicate its owner identity.
This is a compact learning implementation, with infallible vector allocation following the standard collection API. It does not promise recovery from every memory-allocation failure or offer persistent identifiers. Its public behavior is much narrower: under the described in-process mutation rules, a lookup never treats a replaced occupant as the original object. Keeping that promise small makes the relevant edge cases visible and leaves room to discuss the additional requirements of a production collection afterward.
use std::sync::atomic::{AtomicU64, Ordering};
static NEXT_ARENA: AtomicU64 = AtomicU64::new(1);
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
struct Handle { arena: u64, index: usize, generation: u64 }
struct Slot<T> { generation: u64, value: Option<T> }
struct Arena<T> { identity: u64, slots: Vec<Slot<T>>, free: Vec<usize> }
impl<T> Arena<T> {
fn new() -> Option<Self> {
let identity = loop {
let current = NEXT_ARENA.load(Ordering::Relaxed);
let next = current.checked_add(1)?;
if NEXT_ARENA.compare_exchange_weak(current, next,
Ordering::Relaxed, Ordering::Relaxed).is_ok() { break current; }
};
Some(Self { identity, slots: Vec::new(), free: Vec::new() })
}
fn insert(&mut self, value: T) -> Handle {
let index = if let Some(index) = self.free.pop() {
self.slots[index].value = Some(value);
index
} else {
let index = self.slots.len();
self.slots.push(Slot { generation: 0, value: Some(value) });
index
};
Handle { arena: self.identity, index, generation: self.slots[index].generation }
}
fn slot(&self, handle: Handle) -> Option<&Slot<T>> {
if handle.arena != self.identity { return None; }
self.slots.get(handle.index).filter(|slot| slot.generation == handle.generation)
}
fn get(&self, handle: Handle) -> Option<&T> { self.slot(handle)?.value.as_ref() }
fn get_mut(&mut self, handle: Handle) -> Option<&mut T> {
if handle.arena != self.identity { return None; }
let slot = self.slots.get_mut(handle.index)?;
if slot.generation != handle.generation { return None; }
slot.value.as_mut()
}
fn remove(&mut self, handle: Handle) -> Option<T> {
if handle.arena != self.identity { return None; }
let slot = self.slots.get_mut(handle.index)?;
if slot.generation != handle.generation { return None; }
let value = slot.value.take()?;
if let Some(next) = slot.generation.checked_add(1) {
slot.generation = next;
self.free.push(handle.index);
} // An exhausted generation permanently retires this slot.
Some(value)
}
}
fn main() {
let mut arena = Arena::new().unwrap();
let old = arena.insert(String::from("draft"));
assert_eq!(arena.remove(old).as_deref(), Some("draft"));
let current = arena.insert(String::from("replacement"));
assert_eq!(old.index, current.index);
assert_ne!(old.generation, current.generation);
assert!(arena.get(old).is_none());
arena.get_mut(current).unwrap().push_str(" page");
assert_eq!(arena.get(current).map(String::as_str), Some("replacement page"));
let other: Arena<String> = Arena::new().unwrap();
assert!(other.get(current).is_none());
println!("stale handles rejected: ok");
}
#[test]
fn generation_exhaustion_retires_the_slot() {
let mut arena = Arena::new().unwrap();
let first = arena.insert("last occupant");
arena.slots[first.index].generation = u64::MAX; // Test-only boundary fixture.
let final_handle = Handle { generation: u64::MAX, ..first };
assert_eq!(arena.remove(final_handle), Some("last occupant"));
assert!(arena.remove(final_handle).is_none());
let next = arena.insert("new slot");
assert_ne!(next.index, final_handle.index);
assert!(arena.get(final_handle).is_none());
}
#[test]
fn double_remove_does_not_duplicate_a_free_slot() {
let mut arena = Arena::new().unwrap();
let old = arena.insert(7);
assert_eq!(arena.remove(old), Some(7));
assert_eq!(arena.remove(old), None);
let a = arena.insert(8);
let b = arena.insert(9);
assert_ne!(a.index, b.index);
assert_eq!(arena.get(a), Some(&8));
assert_eq!(arena.get(b), Some(&9));
}The immutable lookup first compares owner identities, then uses Vec::get for a bounds-checked slot lookup. A generation comparison determines whether the handle still refers to this occupant's lifetime. Finally, the optional stored value determines whether anything is currently alive in that slot. Each failed condition returns None, and none requires an unsafe dereference. The returned reference borrows the arena in the ordinary Rust way.
Mutable lookup follows the same identity checks before returning a mutable reference. The generation does not weaken the borrow checker or permit two mutable references to the same live value. It only decides which value the caller is asking to borrow. If your application needs simultaneous mutation of two distinct handles, design a method that checks their distinctness and safely obtains disjoint slots; do not assume that having two different handle values proves they identify different live slots.
The removal method takes the value out of its slot before adding the index to the free list. A second removal with the same handle sees either a generation mismatch or an empty value and returns None. It never adds another copy of the index. This matters because duplicate free-list entries could let two subsequent insertions overwrite the same slot, even while each insertion returned what appeared to be a fresh handle.
The dedicated double-removal test checks the consequence rather than merely inspecting an internal vector length. After removing the same old handle twice, it inserts two values and verifies that they occupy distinct indices and remain independently retrievable. Tests that exercise the public identity contract are more durable than tests that mirror each line of the implementation. Internal state assertions remain useful for boundary fixtures, but they should support a behavior that an application actually relies on.
The atomic owner counter restarts when the process restarts. A serialized handle from a previous launch could therefore collide with an unrelated arena in a new process. The implementation deliberately does not derive serialization for handles or advertise them as database keys. A process-local handle is suitable for a live editor model, task registry or temporary graph, provided its owner controls the lifecycle and discards stale handles after restart.
If an object must survive launches, give it a durable domain identifier and rebuild the mapping to current handles when loading. The durable identifier might come from your document format or database, with its own uniqueness and migration rules. Do not simply serialize an array index, and do not assume that increasing the generation width solves process restarts. The owner scope, storage lifetime and external identity contract all need to agree before a handle can safely cross that boundary.
Imagine a compiler task started for a document that is later removed. Its completion event can carry the document handle and the source revision that was compiled. When the event arrives, the state owner first looks up the handle. If the document is gone or the slot has been reused, the event is discarded. If it is still the same document but the source revision changed, the application can retain historical output without presenting it as the current build result.
The two checks solve different problems. Generations reject a different occupant of reused storage; revisions reject a different snapshot of the same occupant. A current handle alone cannot tell you whether a compiler result describes the latest text. Conversely, a source hash alone does not identify which open project should receive that result. A reliable application carries both pieces of context and makes the acceptance rule explicit at the point where visible state changes.
Slots retain their positions after removal, so the arena may contain holes. A free list lets new insertions reuse those holes, but it does not automatically reduce the allocation after a temporary peak. Retired slots remain holes permanently under the exhaustion rule. For a short-lived editing session this may be entirely acceptable; a service that creates and removes objects continuously should measure high-water memory usage under its own workload.
Iteration also needs an explicit policy. Scanning the slots and selecting occupied values costs work proportional to the number of slots, not merely the number of live objects. A collection with many holes can therefore iterate slowly even when lookups remain cheap. If dense iteration is central to the application, investigate a dense arena design or a mapping between stable handles and compact storage. That extra mapping introduces invariants of its own, so choose it for measured workload needs rather than assuming one representation wins universally.
An arena can reject an edge whose target was removed, but it cannot decide what that rejection means for your graph. A dependency viewer might hide a removed target, mark the edge as unresolved, or remove incoming edges as part of the same transaction. A document editor might preserve a broken reference so the user can repair it. Those choices belong to the application's domain rather than to the storage container.
Choose the policy when designing deletion. If removing a node should also remove its incoming edges, keep enough indexing information to perform that update and test that the operation is complete before publishing the new graph. If dangling edges are permitted, make every traversal handle missing targets intentionally. Calling unwrap during traversal merely postpones the missing-object decision until it becomes a panic.
A useful fixture removes a heavily referenced node, immediately reuses its slot and then traverses the old graph. Every old edge must either be absent or explicitly unresolved; none may reach the replacement node. That test joins the arena's local guarantee to the higher-level behavior users actually see.
The owner counter uses a compare-and-exchange loop. It reads the current value, computes the next value with checked arithmetic and attempts to install that next value only if another caller has not changed the counter. A weak comparison may fail spuriously, so failure retries rather than being treated as identity exhaustion. Actual exhaustion occurs only when the checked increment has no representable result.
This loop gives distinct successful creations distinct process-local identities. It does not order unrelated writes to arena contents, which is why relaxed ordering is appropriate for this isolated counter. The arena's own values remain protected by normal ownership and borrowing. If the arena later moves behind a mutex or another state owner, that mechanism provides the relevant access ordering; the identity allocator should not silently take on that additional responsibility.
Keeping the allocator separate also makes its limits easier to document. An application that restores durable objects after restart should allocate fresh live arena identities and rebuild its durable-ID mapping. It should never advance this counter based on an untrusted serialized handle and then assume the resulting values establish authenticity or cross-launch continuity.
A useful stress test keeps a map from issued handles to expected values and generates a deterministic sequence of insertions, removals and lookups. Whenever an operation returns a handle, record the expected value. Whenever removal succeeds, move that handle into a list of known stale handles. Repeatedly sample both current and stale handles and compare the arena's answers with the map's answers. Include lookups against a second arena in the same run.
Keep the reference model simpler than the arena. It does not need a free list, generations or slot reuse; it only needs to remember which exact handles are expected to be live. Use a fixed seed for reproducibility and print the operation index on failure. Small sequences that deliberately remove and reinsert the same slot are often more revealing than millions of unrelated insertions, because they repeatedly exercise the transition the generation is meant to protect.
The implementation retires a slot when its generation cannot advance. Other designs may choose a different policy, but wrapping deserves a written justification because it weakens the freshness guarantee. Increasing the generation size makes accidental exhaustion less likely; it does not change what wrapping means. An explicit boundary test is valuable even when the production probability is tiny, because the policy belongs to the type's correctness contract.
A clear operation needs similar care. If it empties slots and resets every generation to zero while retaining the same arena identity, old handles can become valid again when positions are reused. A safe design can remove values through the ordinary invalidation path or allocate a new owner identity for the cleared arena. Decide whether clear preserves capacity, which handles it invalidates, and what happens if allocating a fresh identity is impossible. Convenience methods must preserve the same guarantees as individual insertions and removals.
A handle should not become an excuse to make every relationship global and indirect. A value that has one clear owner and never outlives that owner may be simpler as an ordinary field or a borrowed reference. Generational handles are useful when relationships must survive independent insertions and removals, when callbacks arrive later, or when graph edges need to name objects without borrowing the entire collection continuously.
Inside an arena value, continue using Rust's ordinary ownership tools. Strings and vectors own their data; references obey lifetimes; shared ownership has an explicit reason. The arena solves lookup identity, not every ownership problem in the program. Start with the smallest set of relationships that needs stable handles, document their owner scope, and leave local relationships direct. This keeps errors understandable and prevents a useful storage pattern from turning into unnecessary application-wide indirection.
For a production system, compare existing arena and slot-map libraries against a written checklist: owner scope, stale-key behavior, generation width, overflow policy, serialization, iteration cost, memory reclamation and support for obtaining disjoint mutable values. Read how a library treats keys from different collections rather than assuming every implementation includes an owner identity. A compact key representation may intentionally make a different tradeoff from this teaching example.
Then keep a small contract test suite at your integration boundary. Removing an object must invalidate its old key; reusing storage must not revive it; resetting or loading a collection must follow the documented lifetime rule; a late operation must not update a replacement object. Those tests remain valuable if the underlying library changes. The real benefit of generational handles is a precise answer to a practical question: does this lookup still name the same live object I originally meant?