A very simple, uniformly-typed slab arena that supports deallocation and reusing deallocated entries' space.

The free list of vacant entries in the slab are stored inline in the slab's existing storage.

Example

use wasmtime_slab::{Id, Slab};

let mut slab = Slab::new();

// Insert some values into the slab.
let rza = slab.alloc("Robert Fitzgerald Diggs");
let gza = slab.alloc("Gary Grice");
let bill = slab.alloc("Bill Gates");

// Alloced elements can be accessed infallibly via indexing (and missing and
// deallocated entries will panic).
assert_eq!(slab[rza], "Robert Fitzgerald Diggs");

// Alternatively, the `get` and `get_mut` methods provide fallible lookup.
if let Some(genius) = slab.get(gza) {
    println!("The gza gza genius: {}", genius);
}
if let Some(val) = slab.get_mut(bill) {
    *val = "Bill Gates doesn't belong in this set...";
}

// We can remove values from the slab.
slab.dealloc(bill);

// Allocate a new entry.
let bill = slab.alloc("Bill Murray");

Using Ids with the Wrong Slab

Slab does NOT check that Ids used to access previously-allocated values came from the current Slab instance (as opposed to a different Slab instance). Using Ids from a different Slab is safe, but will yield an unrelated value, if any at all.

If you desire checking that an Id came from the correct Slab instance, it should be easy to layer that functionality on top of this crate by wrapping Slab and Id in types that additionally maintain a slab instance identifier.

The ABA Problem

This Slab type does NOT protect against ABA bugs, such as the following sequence:

• Value A is allocated into the slab, yielding id i.

• A is deallocated, and so i's associated entry is added to the slab's free list.

• Value B is allocated into the slab, reusing i's associated entry, yielding id i.

• The "original" id i is used to access the arena, expecting the deallocated value A, but getting the new value B.

That is, it does not detect and prevent against the memory-safe version of use-after-free bugs.

If you need to protect against ABA bugs, it should be easy to layer that functionality on top of this crate by wrapping Slab with something like the following:

pub struct GenerationalId {
    id: wasmtime_slab::Id,
    generation: u32,
}

struct GenerationalEntry<T> {
    value: T,
    generation: u32,
}

pub struct GenerationalSlab<T> {
    slab: wasmtime_slab::Slab<GenerationalEntry<T>>,
    generation: u32,
}

impl<T> GenerationalSlab<T> {
    pub fn alloc(&mut self, value: T) -> GenerationalId {
        let generation = self.generation;
        let id = self.slab.alloc(GenerationalEntry { value, generation });
        GenerationalId { id, generation }
    }

    pub fn get(&self, id: GenerationalId) -> Option<&T> {
        let entry = self.slab.get(id.id)?;

        // Check that the entry's generation matches the id's generation,
        // else we have an ABA bug. (Alternatively, return `None` instead
        // of panicking.)
        assert_eq!(id.generation, entry.generation);

        Some(&entry.value)
    }

    pub fn dealloc(&mut self, id: GenerationalId) {
        // Check that the entry's generation matches the id's generation,
        // else we have an ABA bug. (Alternatively, silently return on
        // double-free instead of panicking.)
        assert_eq!(id.generation, self.slab[id.id].generation);

        self.slab.dealloc(id.id);

        // Increment our generation whenever we deallocate so that any new
        // value placed in this same entry will have a different generation
        // and we can detect ABA bugs.
        self.generation += 1;
    }
}