A lightweight WebAssembly runtime that is fast, secure, and standards-compliant
//! 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
//!
//! ```
//! # fn foo() -> wasmtime_internal_core::error::Result<()> {
//! use wasmtime_internal_core::slab::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")?;
//! # Ok(())
//! # }
//! # foo().unwrap();
//! ```
//!
//! # 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
//! use wasmtime_internal_core::error::OutOfMemory;
//!
//! pub struct GenerationalId {
//! id: wasmtime_internal_core::slab::Id,
//! generation: u32,
//! }
//!
//! struct GenerationalEntry<T> {
//! value: T,
//! generation: u32,
//! }
//!
//! pub struct GenerationalSlab<T> {
//! slab: wasmtime_internal_core::slab::Slab<GenerationalEntry<T>>,
//! generation: u32,
//! }
//!
//! impl<T> GenerationalSlab<T> {
//! pub fn alloc(&mut self, value: T) -> Result<GenerationalId, OutOfMemory> {
//! let generation = self.generation;
//! let id = self.slab.alloc(GenerationalEntry { value, generation })?;
//! Ok(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;
//! }
//! }
//! ```
use crate::alloc::TryVec;
use crate::error::OutOfMemory;
use core::fmt;
use core::num::NonZeroU32;
/// An identifier for an allocated value inside a `slab`.
#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
#[repr(transparent)]
pub struct Id(EntryIndex);
impl fmt::Debug for Id {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_tuple("Id").field(&self.0.index()).finish()
}
}
impl Id {
/// Get the raw underlying representation of this `Id`.
#[inline]
pub fn into_raw(self) -> u32 {
u32::try_from(self.0.index()).unwrap()
}
/// Construct an `Id` from a value previously returned by `into_raw`, if
/// that value is well-formed.
///
/// A well-formed `Id` is not necessarily one that any slab has handed out;
/// lookups are still checked.
#[inline]
pub fn try_from_raw(raw: u32) -> Option<Self> {
let raw = usize::try_from(raw).ok()?;
if raw > Slab::<()>::MAX_CAPACITY {
return None;
}
Some(Self(EntryIndex::new(raw)))
}
}
/// A simple, uni-typed slab arena.
pub struct Slab<T> {
/// The slab's entries, each is either occupied and holding a `T` or vacant
/// and is a link the free list.
entries: TryVec<Entry<T>>,
/// The index of the first free entry in the free list.
free: Option<EntryIndex>,
/// The number of occupied entries is this slab.
len: u32,
}
impl<T> fmt::Debug for Slab<T>
where
T: fmt::Debug,
{
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_map().entries(self.iter()).finish()
}
}
enum Entry<T> {
/// An occupied entry holding a `T`.
Occupied(T),
/// A vacant entry.
Free {
/// A link in the slab's free list, pointing to the next free entry, if
/// any.
next_free: Option<EntryIndex>,
},
}
#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
#[repr(transparent)]
struct EntryIndex(NonZeroU32);
impl EntryIndex {
#[inline]
fn new(index: usize) -> Self {
assert!(index <= Slab::<()>::MAX_CAPACITY);
let x = u32::try_from(index + 1).unwrap();
Self(NonZeroU32::new(x).unwrap())
}
#[inline]
fn index(&self) -> usize {
let index = self.0.get() - 1;
usize::try_from(index).unwrap()
}
}
impl<T> Default for Slab<T> {
#[inline]
fn default() -> Self {
Self {
entries: TryVec::default(),
free: None,
len: 0,
}
}
}
impl<T> core::ops::Index<Id> for Slab<T> {
type Output = T;
#[inline]
fn index(&self, id: Id) -> &Self::Output {
self.get(id)
.expect("id from different slab or value was deallocated")
}
}
impl<T> core::ops::IndexMut<Id> for Slab<T> {
#[inline]
fn index_mut(&mut self, id: Id) -> &mut Self::Output {
self.get_mut(id)
.expect("id from different slab or value was deallocated")
}
}
impl<T> Slab<T> {
/// The maximum capacity any `Slab` can have: `u32::MAX - 1`.
pub const MAX_CAPACITY: usize = (u32::MAX - 1) as usize;
/// Construct a new, empty slab.
#[inline]
pub fn new() -> Self {
Slab::default()
}
/// Construct a new, empty slab, pre-reserving space for at least `capacity`
/// elements.
#[inline]
pub fn with_capacity(capacity: usize) -> Result<Self, OutOfMemory> {
let mut slab = Self::new();
slab.reserve(capacity)?;
Ok(slab)
}
/// Ensure that there is space for at least `additional` elements in this
/// slab.
///
/// # Panics
///
/// Panics if the new capacity exceeds `Self::MAX_CAPACITY`.
pub fn reserve(&mut self, additional: usize) -> Result<(), OutOfMemory> {
let cap = self.capacity();
let len = self.len();
assert!(cap >= len);
if cap - len >= additional {
// Already have `additional` capacity available.
return Ok(());
}
self.entries.reserve(additional)?;
// Maintain the invariant that `i <= MAX_CAPACITY` for all indices `i`
// in `self.entries`.
assert!(self.entries.capacity() <= Self::MAX_CAPACITY);
Ok(())
}
fn double_capacity(&mut self) -> Result<(), OutOfMemory> {
// Double our capacity to amortize the cost of resizing. But make sure
// we add some amount of minimum additional capacity, since doubling
// zero capacity isn't useful.
const MIN_CAPACITY: usize = 16;
let additional = core::cmp::max(self.entries.capacity(), MIN_CAPACITY);
self.reserve(additional)
}
/// What is the capacity of this slab? That is, how many entries can it
/// contain within its current underlying storage?
#[inline]
pub fn capacity(&self) -> usize {
self.entries.capacity()
}
/// How many values are currently allocated within this slab?
#[inline]
pub fn len(&self) -> usize {
usize::try_from(self.len).unwrap()
}
/// Are there zero allocated values within this slab?
#[inline]
pub fn is_empty(&self) -> bool {
self.len() == 0
}
/// Try to allocate a `T` value within this slab.
///
/// If there is no available capacity, ownership of the given value is
/// returned via `Err(value)`.
#[inline]
pub fn try_alloc(&mut self, value: T) -> Result<Id, T> {
if let Some(index) = self.try_alloc_index() {
let next_free = match self.entries[index.index()] {
Entry::Free { next_free } => next_free,
Entry::Occupied { .. } => unreachable!(),
};
self.free = next_free;
self.entries[index.index()] = Entry::Occupied(value);
self.len += 1;
Ok(Id(index))
} else {
Err(value)
}
}
#[inline]
fn try_alloc_index(&mut self) -> Option<EntryIndex> {
self.free.take().or_else(|| {
if self.entries.len() < self.entries.capacity() {
let index = EntryIndex::new(self.entries.len());
self.entries
.push(Entry::Free { next_free: None })
.expect("have capacity");
Some(index)
} else {
None
}
})
}
/// Allocate a `T` value within this slab, allocating additional underlying
/// storage if there is no available capacity.
///
/// # Panics
///
/// Panics if allocating this value requires reallocating the underlying
/// storage, and the new capacity exceeds `Slab::MAX_CAPACITY`.
#[inline]
pub fn alloc(&mut self, value: T) -> Result<Id, OutOfMemory> {
self.try_alloc(value)
.or_else(|value| self.alloc_slow(value))
}
/// Get the `Id` that will be returned for the next allocation in this slab.
#[inline]
pub fn next_id(&self) -> Id {
let index = self.free.unwrap_or_else(|| EntryIndex::new(self.len()));
Id(index)
}
#[inline(never)]
#[cold]
fn alloc_slow(&mut self, value: T) -> Result<Id, OutOfMemory> {
// Reserve additional capacity, since we didn't have space for the
// allocation.
self.double_capacity()?;
// After which the allocation will succeed.
let id = self.try_alloc(value).ok().unwrap();
Ok(id)
}
/// Get a shared borrow of the value associated with `id`.
///
/// Returns `None` if the value has since been deallocated.
///
/// If `id` comes from a different `Slab` instance, this method may return
/// `None`, or return an arbitrary value.
#[inline]
pub fn get(&self, id: Id) -> Option<&T> {
match self.entries.get(id.0.index())? {
Entry::Occupied(x) => Some(x),
Entry::Free { .. } => None,
}
}
/// Get an exclusive borrow of the value associated with `id`.
///
/// Returns `None` if the value has since been deallocated.
///
/// If `id` comes from a different `Slab` instance, this method may return
/// `None`, or return an arbitrary value.
#[inline]
pub fn get_mut(&mut self, id: Id) -> Option<&mut T> {
match self.entries.get_mut(id.0.index())? {
Entry::Occupied(x) => Some(x),
Entry::Free { .. } => None,
}
}
/// Does this slab contain an allocated value for `id`?
#[inline]
pub fn contains(&self, id: Id) -> bool {
match self.entries.get(id.0.index()) {
Some(Entry::Occupied(_)) => true,
None | Some(Entry::Free { .. }) => false,
}
}
/// Deallocate the value associated with the given `id`.
///
/// If `id` comes from a different `Slab` instance, this method may panic or
/// deallocate an arbitrary value.
#[inline]
pub fn dealloc(&mut self, id: Id) -> T {
let entry = core::mem::replace(
self.entries
.get_mut(id.0.index())
.expect("id from a different slab"),
Entry::Free { next_free: None },
);
match entry {
Entry::Free { .. } => panic!("attempt to deallocate an entry that is already vacant"),
Entry::Occupied(value) => {
let next_free = core::mem::replace(&mut self.free, Some(id.0));
self.entries[id.0.index()] = Entry::Free { next_free };
self.len -= 1;
value
}
}
}
/// Iterate over all values currently allocated within this `Slab`.
///
/// Yields pairs of an `Id` and the `Id`'s associated value.
///
/// Iteration order is undefined.
#[inline]
pub fn iter(&self) -> impl Iterator<Item = (Id, &T)> + '_ {
assert!(self.entries.len() <= Self::MAX_CAPACITY);
self.entries
.iter()
.enumerate()
.filter_map(|(i, e)| match e {
Entry::Occupied(x) => Some((Id(EntryIndex::new(i)), x)),
Entry::Free { .. } => None,
})
}
/// Mutably iterate over all values currently allocated within this `Slab`.
///
/// Yields pairs of an `Id` and the `Id`'s associated value.
///
/// Iteration order is undefined.
#[inline]
pub fn iter_mut(&mut self) -> impl Iterator<Item = (Id, &mut T)> + '_ {
assert!(self.entries.len() <= Self::MAX_CAPACITY);
self.entries
.iter_mut()
.enumerate()
.filter_map(|(i, e)| match e {
Entry::Occupied(x) => Some((Id(EntryIndex::new(i)), x)),
Entry::Free { .. } => None,
})
}
/// Iterate over and remove all entries in this slab.
///
/// The slab will be empty after calling this method.
///
/// Yields pairs of an `Id` and the `Id`'s associated value.
///
/// Iteration order is undefined.
#[inline]
pub fn drain(&mut self) -> impl Iterator<Item = (Id, T)> + '_ {
assert!(self.entries.len() <= Self::MAX_CAPACITY);
self.len = 0;
self.free = None;
self.entries
.drain(..)
.enumerate()
.filter_map(|(i, e)| match e {
Entry::Occupied(x) => Some((Id(EntryIndex::new(i)), x)),
Entry::Free { .. } => None,
})
}
/// Clear all of the values from inside this slab.
///
/// Does not deallocate internal storage.
#[inline]
pub fn clear(&mut self) {
self.len = 0;
self.free = None;
self.entries.clear();
}
}