Slab allocator

Deep dive

How it works

In: an allocation request for one object type or size class; a free of a slot or handle · Out: a pointer or generational key; the slot returned to the free list · State: slabs cut into equal slots, a free list threaded through the free slots, optional per-CPU magazines · Cost: O(1) alloc and free, order of 5-20 ns.

1. A cache per object type (or size class) owns slabs; each slab is cut into slab_size / object_size slots.
2. Free slots form a singly linked list: the first word of each free slot stores the next free slot.
3. Alloc: pop the head of the current slab's free list; if empty, take a partial slab, else allocate a new slab.
4. Free: find the owning slab (page metadata from the address), push the slot onto its free list. A fully free slab can be returned to the page allocator.
5. Per-CPU layer: each CPU has a private slab or "magazine" of free objects, so the common path takes no lock; only refill/flush touches shared lists.
6. Coloring: start objects at different cache-line offsets in different slabs so hot fields of many objects don't map to the same cache sets.

slab (4 KB page, 64 B objects → 64 slots)
[obj][free→7][obj][obj][obj][obj][obj][free→12]...    head = 1
alloc → returns slot 1, head = 7      free(slot 3) → slot 3 stores 7, head = 3

Code

User-space slab with generational keys: insert/remove are O(1), and a stale key can't reach a reused slot.

#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub struct Key { idx: u32, gen: u32 }

enum Slot<T> { Occupied { gen: u32, val: T }, Vacant { gen: u32, next_free: u32 } }

const NONE: u32 = u32::MAX;

pub struct Slab<T> { slots: Vec<Slot<T>>, free_head: u32, len: usize }

impl<T> Slab<T> {
    pub fn with_capacity(n: usize) -> Self { Slab { slots: Vec::with_capacity(n), free_head: NONE, len: 0 } }

    pub fn insert(&mut self, val: T) -> Key {
        self.len += 1;
        if self.free_head != NONE {
            let idx = self.free_head;
            let slot = &mut self.slots[idx as usize];
            let Slot::Vacant { gen, next_free } = *slot else { unreachable!("free list corrupt") };
            self.free_head = next_free;
            *slot = Slot::Occupied { gen, val };
            return Key { idx, gen };
        }
        let idx = self.slots.len() as u32;
        assert!(idx != NONE, "slab full");
        self.slots.push(Slot::Occupied { gen: 0, val });
        Key { idx, gen: 0 }
    }

    pub fn get(&self, k: Key) -> Option<&T> {
        match self.slots.get(k.idx as usize)? {
            Slot::Occupied { gen, val } if *gen == k.gen => Some(val),
            _ => None,
        }
    }

    pub fn get_mut(&mut self, k: Key) -> Option<&mut T> {
        match self.slots.get_mut(k.idx as usize)? {
            Slot::Occupied { gen, val } if *gen == k.gen => Some(val),
            _ => None,
        }
    }

    pub fn remove(&mut self, k: Key) -> Option<T> {
        let slot = self.slots.get_mut(k.idx as usize)?;
        if !matches!(slot, Slot::Occupied { gen, .. } if *gen == k.gen) { return None; }
        // Bump the generation so every outstanding copy of `k` is now dead.
        let vacant = Slot::Vacant { gen: k.gen.wrapping_add(1), next_free: self.free_head };
        let Slot::Occupied { val, .. } = std::mem::replace(slot, vacant) else { unreachable!() };
        self.free_head = k.idx;                 // LIFO: the most recently freed slot is cache-hot
        self.len -= 1;
        Some(val)
    }

    pub fn len(&self) -> usize { self.len }
}

fn main() {
    let mut s = Slab::with_capacity(1024);
    let a = s.insert("conn-a");
    let b = s.insert("conn-b");
    assert_eq!(s.remove(a), Some("conn-a"));
    let c = s.insert("conn-c");                 // reuses a's slot...
    assert_eq!(s.get(a), None);                 // ...but the stale key is rejected
    assert_eq!((s.get(b), s.get(c)), (Some(&"conn-b"), Some(&"conn-c")));
}

Complexity and constants

• Alloc/free fast path: a load and a store on the free list (plus a per-CPU access in the kernel): order of 5-20 ns, comparable to the best malloc thread-cache paths and with no header.
• Memory per object above: max(size_of T, 8) + discriminant, padded to alignment; the kernel version has zero per-object overhead (metadata in struct page/slab).
• Size classes: Linux kmalloc uses powers of two (8 B to 8 KB in page-sized caches) plus 96 and 192; memcached's 1.25 growth factor wastes up to ~20 % per item, smaller factors mean more classes and more calcification.
• Objects per slab: a 4 KB slab of 64 B objects holds 64; large objects use multi-page slabs to keep waste at the slab tail small.

Efficiency

• Cost: The fast path is a load and a store on the free list: order of 5-20 ns, with no header (zero per-object overhead in the kernel). Waste is slot size minus object size; memcached's 1.25 growth factor wastes up to about 20 % per item. The bound is cache misses on reused slots, and the lock on shared lists when there is no per-CPU layer.
• Levers:
  • LIFO free list — the most recently freed slot is still cache-warm — high-churn objects.
  • Per-CPU slabs or magazines — lock-free common path (Bonwick and Adams 2001) — many cores.
  • Cache constructed objects — initialization paid once (Bonwick 1994) — costly constructors.
  • Cache-line colouring — fewer cache-set conflicts between slabs (Bonwick 1994) — hot-field-heavy objects.
  • Keep a few empty slabs — no page-allocator thrash on alloc/free oscillation — bursty workloads.
• Naive → standard → state of the art:
  • General malloc/free per object · order of 10-50 ns, a header, external fragmentation.
  • Slab with an in-slot free list · O(1), no header, internal waste only.
  • Per-CPU slabs with cmpxchg (Linux SLUB), or per-page free-list sharding (mimalloc) · lock-free fast path.

Implementation notes

• LIFO free list: reusing the most recently freed slot returns memory that is still in cache.
• Per-CPU caches/magazines: Bonwick & Adams' magazine layer and SLUB's per-CPU slabs make the common path lock-free; balance by moving whole magazines, not single objects.
• Hardening: SLUB can obfuscate in-object freelist pointers (CONFIG_SLAB_FREELIST_HARDENED) and randomize free-list order so heap exploits can't easily forge them.
• Generational keys (shown) give use-after-free detection for handles; pair with epoch-based reclamation when other threads may still be reading a slot.
• Align hot, separately-written objects to cache lines (64 B) to avoid false sharing.
• Return empty slabs lazily (keep a few) to avoid thrashing the page allocator on alloc/free oscillation.

Pitfalls

• Slab calcification (memcached): memory assigned to one size class stays there when the workload's value sizes shift; enable slab rebalancing (slab_reassign, slab_automove).
• Holding a raw pointer/index after free: it now points at a different object. Use generations or epochs.
• Many sparse slabs (one live object each) pin whole pages: fragmentation at the slab level after bursts.
• Debug options (red zones, poisoning, SLUB slub_debug) change object size and performance; don't benchmark with them on.
• One global lock around the free list: fine single-threaded, a bottleneck at high core counts.

Variants and alternatives

In production

Linux SLUB (kmem_cache_create, kmalloc; inspect with /proc/slabinfo, slabtop), Solaris/illumos kmem, FreeBSD UMA, memcached slab classes, the Rust slab crate (connection/timer storage in event loops; Tokio's I/O driver keeps its own internal slab), DPDK mempools.

Implementations

Sources

• Jeff Bonwick, The Slab Allocator: An Object-Caching Kernel Memory Allocator, USENIX Summer 1994. paper
• Jeff Bonwick, Jonathan Adams, Magazines and Vmem: Extending the Slab Allocator to Many CPUs and Arbitrary Resources, USENIX ATC 2001. paper
• Daan Leijen, Benjamin Zorn, Leonardo de Moura, Mimalloc: Free List Sharding in Action, APLAS 2019. paper · code