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");
// 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 `Id`s with the Wrong `Slab`
`Slab` does NOT check that `Id`s used to access previously-allocated values
came from the current `Slab` instance (as opposed to a different `Slab`
instance). Using `Id`s 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:
```rust
pub struct GenerationalId {
id: wasmtime_slab::Id,
generation: u32,
}
struct GenerationalEntry {
value: T,
generation: u32,
}
pub struct GenerationalSlab {
slab: wasmtime_slab::Slab>,
generation: u32,
}
impl GenerationalSlab {
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;
}
}
```