Rust Prevents Use-After-Free. This Bug Is Different

The borrow checker cannot detect stale indices. Generational arenas can.

There is a class of bug that does not crash your program. It does not trigger the borrow checker. It compiles cleanly, runs without panicking, and returns a value, just the wrong one. You hold an index into a collection, the slot that index points to gets freed and reused for something else, and your index now silently refers to an entirely different entity than the one you created it for. In C and C++, the equivalent is use-after-free, one of the most thoroughly documented vulnerability classes in software security, responsible for a significant fraction of memory-safety CVEs against browsers, OS kernels, and other C codebases over the past two decades. Rust prevents the classic form at compile time. It does not automatically prevent this quieter version, and understanding why is where arena allocators come from.

The pattern that has been building across this book

Starting from linked lists in chapter two, every data structure in this series that needed nodes referencing other nodes faced the same ownership question: who owns what? The Rust answer that keeps showing up is to trade pointers for plain integer indices into a flat Vec. Node references become usize values. Ownership questions disappear because an integer is Copy and carries no ownership obligations. Rc, RefCell, and Weak never need to appear.

The graph chapter applied this to a structure with arbitrary cycles. The LRU cache chapter applied it to a doubly linked list where a hash map and the list both needed to reference the same nodes simultaneously. Both worked cleanly. Both also quietly deferred the same problem: what happens to an index after the slot it pointed to is freed and reused?

The graph implementation never removed nodes at all. The LRU cache never reused freed slots, leaving dead space behind instead of reclaiming it. These are honest simplifications, acknowledged when they were made. Neither is viable for a system that runs for a long time: a game spawning and despawning thousands of entities across an hour, a compiler building and discarding ASTs across many files, a server handling millions of requests. Leaking every removed slot forever is not a strategy.

What an arena actually is

An arena, sometimes called a pool, is a single block of storage, in safe Rust typically just a Vec<T>, that objects are allocated from directly rather than each getting its own separate heap allocation. In its simplest form, a bump allocator, allocating a new object means writing it at the next available position and advancing an index forward: no searching for free space, no per-allocation bookkeeping. This is dramatically cheaper than a general-purpose allocator's job of tracking arbitrarily sized, arbitrarily freed blocks.

The trade that buys that speed is real. A bump arena typically gives up freeing individual objects one at a time, in exchange for freeing everything at once when the whole arena is done. A compiler pass that allocates thousands of AST nodes and then discards all of them together is an ideal use case. A game engine that allocates entities for a single frame and discards them at frame end is another. Any long-running system that needs to remove individual objects and reuse their memory is not, at least not without the additional mechanism that follows.

A plain usize index into an arena has one genuine advantage over a raw reference into a Vec: it is stable across resizes. Growing a Vec may reallocate its entire backing buffer, which is exactly why Rust's borrow checker refuses to let a reference into a collection stay alive across a mutating call. An index refers to a logical position, not a physical address. A resize can move every byte in memory without changing what index 12 means.

What an index does not protect against is staleness. If index 12 used to mean “entity A” and now means “entity B” because A was removed and B was allocated into the same slot, anything holding an old handle to A will silently get B instead. No panic. No compile error. Just wrong data.

The generational index

The fix pairs every handle with two numbers instead of one: the slot index as before, and a generation counter. Every slot in the arena also stores its own current generation, incremented each time that slot is freed and handed out again. A handle is valid only if its generation matches the slot’s current generation at lookup time. A mismatch means the handle is stale, and the arena returns None instead of silently returning the wrong entry.

#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub struct NodeId {
    index: usize,
    generation: u32,
}

struct Slot<T> {
    generation: u32,
    value: Option<T>, // None means currently free
}
pub struct Arena<T> {
    slots: Vec<Slot<T>>,
    free_list: Vec<usize>,
}

When you remove entity A from slot 12, the arena increments that slot’s generation to 2 and adds index 12 to the free list. When entity B is later allocated into slot 12, the returned handle carries (index: 12, generation: 2). Any old handle still holding (index: 12, generation: 1) is detectable as stale on the next lookup: the handle's generation does not match the slot's current generation. The arena says so explicitly.

impl<T> Arena<T> {
    pub fn get(&self, id: NodeId) -> Option<&T> {
        let slot = self.slots.get(id.index)?;
        if slot.generation != id.generation {
            return None; // stale handle — slot was freed and reused
        }
        slot.value.as_ref()
    }
}

This converts a silent logic bug into a detectable one. Every lookup that would previously have returned the wrong entity now returns None, and the caller can handle that explicitly rather than acting on corrupted data. It is the same move as Rust's compile-time borrow errors and Java's ConcurrentModificationException: making a violation loud rather than quiet.

Why production Rust code uses slotmap

The slotmap crate is the production-grade version of exactly this pattern. It provides a generational arena with a more heavily optimized implementation than a first pass would be, handles zero-sized types correctly, and offers several variants: SlotMap for the default generational behaviour, HopSlotMap for faster iteration over occupied slots, and SecondaryMap for associating additional data with the same keys without redundant storage.

use slotmap::{SlotMap, DefaultKey};

let mut sm: SlotMap<DefaultKey, &str> = SlotMap::new();
let player = sm.insert("player");
let enemy  = sm.insert("enemy");
sm.remove(enemy);
// `enemy` handle is now stale - returns None
assert_eq!(sm.get(enemy), None);
// `player` handle is still valid
assert_eq!(sm.get(player), Some(&"player"));

bumpalo solves a genuinely different problem that happens to share the word arena. It is pure bump allocation with no individual removal and no generational tracking at all, aimed at cases where a batch of allocations lives and dies together. A compiler front-end allocating every node in a single parse into a bumpalo::Bump arena and then dropping the entire arena at once pays almost no allocator overhead and frees everything in a single deallocation. There is no mechanism to remove individual nodes mid-lifetime, by design. The two crates are answers to two different questions: slotmap when you need to remove individual entries and detect stale handles; bumpalo when everything lives and dies together and allocation speed is the constraint.

Where this has shown up in real systems

Game entity component systems are the canonical use case for generational arenas, and the reason is exactly the stale-handle problem. A game spawns thousands of entities per second and despawns them constantly. Anything holding a handle to an entity, a component system, an AI behaviour tree, a physics constraint, needs to detect when that entity has been removed rather than silently operating on whatever happens to occupy the same slot now. The generational index makes this detection O(1) rather than requiring a separate alive-check lookup in a separate data structure.

Compiler AST nodes are the other common case. A compiler typically allocates all nodes for a single compilation unit into an arena and frees them together when the unit is done. The bump allocator model fits naturally: per-node allocation overhead is eliminated, cache locality across the AST is excellent because all nodes are contiguous, and the free is a single deallocation rather than one per node. The Rust compiler itself uses arena allocation internally for exactly this reason.

All code in this series is compiled and tested in the companion repository: github.com/shan305/data-structures-rust-java

This article is drawn from the final chapter of Ownership vs. Reference: Data Structures and Algorithms in Rust and Java — every structure built twice, once in Rust and once in Java, covering the stale-index problem through every chapter that defers it before this one resolves it.

For the Rust foundations this series builds on: Zero to Rust: A Systems Programmer’s Field Guide — $7 · Free 20-page sample