An extension of the MIT xv6 RISC-V teaching operating system that replaces the original page-level free-list allocator with a buddy system allocator and a slab allocator. Core kernel structures such as proc are migrated to use the slab allocator for reduced fragmentation and faster allocation.
The original xv6 kernel manages physical memory with a simple free-list that hands out one 4 KiB page at a time. This project introduces two allocators that sit on top of each other:
┌─────────────────────────────────────┐
│ Kernel consumers │
│ (proc, file, inode, pipe, …) │
├─────────────────────────────────────┤
│ Slab Allocator │
│ kmem_cache_t · kmalloc / kffree │
├─────────────────────────────────────┤
│ Buddy Allocator │
│ buddy_malloc(order) / buddy_free() │
├─────────────────────────────────────┤
│ Physical Memory (DRAM) │
└─────────────────────────────────────┘
File: kernel/buddy.c / kernel/buddy.h
The buddy allocator manages the entire physical address space available to the kernel. It supports allocations of sizes that are powers of two, ranging from 4 KiB (order 12) to 4 MiB (order 22).
- Memory is divided into a binary tree of blocks. Each block can be split into two equal-sized buddies and merged back when both are free.
- A
split_treebitmap tracks, for each parent node, whether exactly one of its two children is in use (XOR of the two children's states). This allows O(log n) coalescing on free without storing per-block state for every level. - Per-order free lists (
buckets[]) allow O(1) allocation from a given size class when a suitable free block is immediately available. - A small metadata array records the allocation order of each minimum-size block, enabling
buddy_freeto determine the original size of a pointer without the caller passing it.
| Constant | Value | Meaning |
|---|---|---|
MIN_BUDDY_ORDER |
12 | Smallest allocation: 4 KiB |
MAX_BUDDY_ORDER |
22 | Largest allocation: 4 MiB |
BLOCK_SIZE |
4096 | Bytes per minimum block |
void buddy_init (void *start, int block_num);
void *buddy_malloc (size_t block_order); // order, not bytes
void buddy_free (void *p);The original kalloc() and kfree() functions in kernel/kalloc.c are thin wrappers that delegate to buddy_malloc(12) and buddy_free() respectively, so all existing xv6 page-allocation call-sites continue to work unchanged.
File: kernel/slab.c / kernel/slab.h
The slab allocator is built on top of the buddy allocator and provides efficient, fixed-size object caches. It follows the classic Linux-slab design: a cache holds a collection of slabs, each slab is a buddy-allocated block subdivided into equally-sized objects.
empty ──alloc──▶ partial ──full alloc──▶ full
full ──free───▶ partial ──last free───▶ empty
empty ──shrink──▶ (memory returned to buddy)
- Empty slabs are kept for fast re-use before returning memory to the buddy allocator.
- Partial slabs are preferred for allocation to maximise object density before touching a new slab.
- Full slabs are tracked separately and skipped during allocation.
kmem_cache_create accepts optional ctor and dtor function pointers. The constructor is called every time an object is handed out from the cache; the destructor is called on kmem_cache_free. This is used, for example, to zero-initialise and set up the spinlock of a struct proc exactly once rather than on every allocation.
A set of 13 size caches (size-5 through size-17, covering 32 B – 128 KiB) back a kmalloc(size) / kffree(ptr) interface for ad-hoc kernel allocations where a dedicated cache is not warranted.
void kmem_init (void *space, int block_num);
kmem_cache_t *kmem_cache_create (char *name, size_t size,
void (*ctor)(void *),
void (*dtor)(void *));
void *kmem_cache_alloc (kmem_cache_t *cachep);
void kmem_cache_free (kmem_cache_t *cachep, void *objp);
int kmem_cache_shrink (kmem_cache_t *cachep);
void kmem_cache_destroy(kmem_cache_t *cachep);
void kmem_cache_info (kmem_cache_t *cachep);
int kmem_cache_error (kmem_cache_t *cachep);
void *kmalloc (size_t size);
void kffree (const void *objp);File: kernel/proc.c
The original xv6 process table is a static array of NPROC struct proc entries. In this implementation the array is replaced with:
- A
kmem_cache_t *proc_cachethat cachesstruct procobjects. - A linked list (
ptable.list) of live process structs, replacing array-indexed access. - A
proc_ctorconstructor that zeroes the struct and initialises its spinlock when the object is first allocated from the cache, avoiding repeated lock initialisation. - A soft cap (
MAX_CACHED_PROCS = 16) on the number of unusedprocobjects kept in the list; excess entries are returned to the slab cache viakmem_cache_freeduring a periodicproc_free()pass.
This means process structs are allocated on demand and their memory is returned to the slab (and ultimately the buddy pool) when no longer needed, rather than being permanently reserved for the lifetime of the kernel.
File: kernel/main.c
The old kinit() call is replaced by kmem_init(), which initialises the buddy allocator over the entire free physical memory range and then creates the size caches for kmalloc:
kmem_init((void*)PGROUNDUP((uint64)end),
(PHYSTOP - (uint64)end) / PGSIZE);File: kernel/javnitest.c
A kernel-level integration test (javnitest()) is run at boot. It exercises the slab allocator by:
- Creating a shared cache with a constructor that stamps objects with a known byte pattern (
0xA5). - Spawning 5 simulated workers, each creating its own private cache and performing 1000 allocations interleaved with shared-cache allocations.
- Verifying byte-pattern integrity on every object before freeing.
- Printing per-cache statistics (
kmem_cache_info) and destroying all caches on completion.
The project uses the standard xv6-riscv build system. You will need a RISC-V cross-compiler and QEMU.
# Build the kernel and user-space programs
make
# Run in QEMU
make qemu
# Run the automated test suite
python3 test-xv6.pyToolchain:
riscv64-unknown-elf-gcc(orriscv64-linux-gnu-gcc).
Emulator: QEMU withqemu-system-riscv64.
kernel/
├── buddy.h / buddy.c # Buddy allocator
├── slab.h / slab.c # Slab allocator + kmalloc
├── kalloc.c # kalloc/kfree now delegate to buddy
├── proc.h / proc.c # Process table using slab cache
├── main.c # Boot: kmem_init replaces kinit
└── javnitest.c # Integration test
xv6-riscv by Frans Kaashoek, Robert Morris, and Russ Cox (MIT PDOS).
Original design inspired by the Linux slab allocator and the buddy system described in Understanding the Linux Virtual Memory Manager.
See LICENSE.