Implement Slab Allocator for Fixed-Size Kernel Objects

Topic Overview

Objects of Fixed Size

Slab allocation caches same-sized kernel objects (dentries, inodes) to avoid repeated buddy splits. Linux keeps per-type slabs with embedded free lists carved from contiguous pages.

Slab Layout

Each slab tracks:

• object_size: power-of-two or aligned struct size
• free_list: singly linked through object slots
• in-use bitmap: optional guard against double free

For example, allocating 128 byte struct file objects from a 4 KB page yields 32 slots per slab with one page fault instead of 32 buddy round trips.

Why This Matters in Production

Bonwick's 1994 slab allocator design became Linux's SLAB and SLUB subsystems, where kmem_cache pools serve task_struct, inode, and dentry objects on every fork() and file open across a running kernel. Because slabs reuse memory without re-zeroing it, slab corruption bugs are also a favorite target for kernel exploit writers chaining a single stray write into arbitrary code execution.

Debugging Checklist

Before you call the implementation done, walk failure modes on purpose. Test empty structures, single-element edge cases, maximum concurrency, and errno paths that must not crash the program. OS code usually fails in production when happy-path tests pass but invariants break under contention or memory pressure.

Implementation Notes

Keep structures small and name fields after kernel counterparts when possible. That lets you read man pages and kernel source side by side while you work. Print observable events during development; remove noisy logs once tests pass reliably.

For This Exercise

You will build slab creation, alloc, and free with cache reuse. The task requires demonstrating that repeated alloc/free hits the hot cache without touching the buddy layer after warmup.

Your Task

Implement a slab allocator, the Linux kernel's allocator for fixed-size objects such as inodes, dentries and task structs. Each cache owns slabs, one 4 KiB page each, cut into equal object slots, and each slab keeps a free list of its slots. A slab is full, partial or empty. Allocation prefers partial slabs, which keeps memory dense. A new page is taken only when every slab is full, and empty slabs can be handed back to the page allocator under memory pressure.

Commands

Rules

• Pages come from one global allocator starting at 0x10000 and increasing by 0x1000. Pages are never reused, even after shrink.
• Which slab: the partial slab with the lowest base, else the empty slab with the lowest base, else a new slab.
• Which slot: each slab's free list is a stack (LIFO). A new slab hands out slots 0, 1, 2, … in order, and a freed slot is the next one handed out by that slab. Object k is at base + k × size.
• Errors: CMD NAME: no such cache; cache NAME: already exists; cache NAME: bad object size S (valid sizes are 8-2048); free NAME 0xADDR: not in this cache, ...: not an object boundary, or ...: double free.

Addresses print in lower-case hex with 0x.

Example

Input:

cCopy
Loading…

Output:

cCopy
Loading…

Requirements

1. Per cache, a list of slabs; per slab, a base address, an in-use count and a free-slot stack. State is derived from the in-use count.
2. free must find the slab from the address alone (base ≤ addr < base + 4096) and validate it before touching the free list.

Hidden tests cover two caches sharing the page allocator, a free that turns a full slab partial and then empty, shrink followed by new allocations (which take fresh pages), and every error.