Implementing a Slab Allocator in Rust

🧠 Implementing a Slab Allocator in Rust

A slab allocator is a memory management technique used in system-level programming where memory is pre-allocated in fixed-size chunks, often for performance and predictability. It's commonly used in kernels, embedded systems, and real-time environments where dynamic memory allocation (like Box, Vec, or Rc) may be too costly or even unavailable.

In this blog post, we'll explore how to implement a simple slab allocator in Rust using safe abstractions like Option, RefCell, and arrays.

---

🧱 Motivation

In embedded or OS-level Rust, we often cannot use the heap, or we want more control over allocations. A slab allocator helps by:

• Avoiding fragmentation
• Offering constant-time allocation/deallocation
• Reusing fixed-size memory blocks

---

🛠️ Core Idea

We simulate a heap by using a fixed-size array of Option<T>, and manage free slots with a Vec<usize> called free_list.

use std::cell::RefCell;

pub struct Slab<T, const N: usize> {
    data: RefCell<[Option<T>; N]>,
    free_list: RefCell<Vec<usize>>,
}

📦 RefCell

We use RefCell so that we can mutate the contents safely even if the Slab is held behind an immutable reference. This is a form of interior mutability.

---

🔧 Constructor

We initialize the free_list with all possible indices:

impl<T, const N: usize> Slab<T, N> {
    pub fn new() -> Self {
        Self {
            data: RefCell::new(array_init::array_init(|_| None)),
            free_list: RefCell::new((0..N).rev().collect()),
        }
    }

We use array_init crate to initialize [Option<T>; N] (because default array initialization for non-Copy types is not trivial).

---

➕ Allocate a Slot

    pub fn insert(&self, value: T) -> Option<usize> {
        let mut free = self.free_list.borrow_mut();
        if let Some(index) = free.pop() {
            self.data.borrow_mut()[index] = Some(value);
            Some(index)
        } else {
            None // Slab full
        }
    }

---

➖ Remove a Slot

    pub fn remove(&self, index: usize) -> Option<T> {
        let mut data = self.data.borrow_mut();
        if index >= N {
            return None;
        }
        if data[index].is_some() {
            let value = data[index].take();
            self.free_list.borrow_mut().push(index);
            value
        } else {
            None
        }
    }

---

📦 Access Slot

    pub fn get(&self, index: usize) -> Option<T> where T: Clone {
        if index >= N {
            return None;
        }
        self.data.borrow()[index].clone()
    }
}

---

✅ Benefits

• Safe: No unsafe used
• Fast: Constant-time allocation
• Predictable: Useful in embedded/real-time

---

💼 Real-World Use Cases

• Kernel object allocation (e.g., file descriptors, processes)
• Embedded sensor buffers
• Network packet storage
• Real-time schedulers

---

🚀 Final Thoughts

This slab allocator is intentionally simple, but demonstrates real systems principles:

• Memory reuse
• Avoiding heap allocations
• Interior mutability for shared state

Thanks for reading! 🙌

Want more like this? Follow me or reach out to talk Rust, blockchain, and low-level systems programming. 💬