Crate wasmtime_internal_slab

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

⚠️ Warning ⚠️: this crate is an internal-only crate for the Wasmtime project and is not intended for general use. APIs are not strictly reviewed for safety and usage outside of Wasmtime may have bugs. If you’re interested in using this feel free to file an issue on the Wasmtime repository to start a discussion about doing so, but otherwise be aware that your usage of this crate is not supported.

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

Example

use wasmtime_internal_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");

// Allocated 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_internal_slab::Id,
    generation: u32,
}

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

pub struct GenerationalSlab<T> {
    slab: wasmtime_internal_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;
    }
}

Structs

Id

An identifier for an allocated value inside a slab.

Slab

A simple, uni-typed slab arena.