Day 92 - kmalloc() Internals¶

Overview¶

Today we completed a simplified Linux-style implementation of the kmalloc() allocation path.

Instead of allocating memory directly, kmalloc() now acts as the public kernel memory allocation interface. It selects an appropriate kmalloc cache according to the requested allocation size and delegates the actual object allocation to the SLUB allocator, which obtains memory pages from the Buddy Allocator.

This completes the simplified Linux memory allocation stack developed throughout the previous labs.

kmalloc()
    ↓
kmalloc cache lookup
    ↓
kmem_cache_alloc()
    ↓
SLUB
    ↓
Buddy Allocator
    ↓
Physical Pages

What I Learned¶

1. Why `kmalloc()` Exists¶

Linux does not require every subsystem to create its own kmem_cache.

Instead, the kernel pre-creates a set of general-purpose kmalloc caches, allowing callers to allocate small objects through a unified API.

For example:

kmalloc(5)
    ↓
kmalloc-8

kmalloc(20)
    ↓
kmalloc-32

kmalloc(100)
    ↓
kmalloc-128

This hides the underlying SLUB allocator and provides a simple allocation interface for kernel subsystems and device drivers.

2. kmalloc Cache Lookup¶

A fixed table of kmalloc caches was created during initialization.

kmalloc-8
kmalloc-16
kmalloc-32
kmalloc-64
kmalloc-128
kmalloc-256
kmalloc-512
kmalloc-1024
kmalloc-2048
kmalloc-4096

Each allocation request searches for the smallest cache capable of satisfying the requested size.

3. Relationship Between kmalloc(), SLUB, and Buddy¶

kmalloc() itself does not allocate physical memory.

Instead, it forwards allocation requests to the appropriate kmem_cache.

kmalloc()
    ↓
kmem_cache_alloc()
    ↓
SLUB
    ↓
alloc_pages()
    ↓
Buddy Allocator

The SLUB allocator manages fixed-size objects, while the Buddy Allocator supplies page-backed slab memory when additional slabs are required.

4. Zero-initialized Allocation¶

kzalloc() allocates memory through kmalloc() before clearing the allocated bytes with memset().

kcalloc() extends this behavior by allocating an array of objects while performing integer-overflow checking before computing the total allocation size.

5. GFP Allocation Policy¶

A simplified execution-context model was retained from the previous implementation.

Two allocation flags were supported:

GFP_KERNEL
GFP_ATOMIC

The simulated rules matched Linux's common behavior:

Context	GFP_KERNEL	GFP_ATOMIC
Process Context	✅	✅
IRQ Context	❌	✅

This demonstrates why sleeping allocations are not permitted inside interrupt handlers.

Implementation¶

Implemented a Linux-style kernel memory allocation frontend.

Completed:

kmalloc cache manager
kmalloc cache lookup
kmalloc()
kzalloc()
kcalloc()
kfree()
GFP allocation policy validation
Execution context simulation
Integration with the SLUB allocator
Integration with the Buddy Allocator

Labs¶

Lab 1¶

Validated kmalloc cache lookup.

Verified that allocation requests were routed to the nearest predefined kmalloc cache.

Examples:

kmalloc(5) → kmalloc-8
kmalloc(16) → kmalloc-16
kmalloc(17) → kmalloc-32
kmalloc(100) → kmalloc-128

Lab 2¶

Verified slab reuse within the same kmalloc cache.

Multiple allocation requests with different sizes mapped to the same size class and reused the same slab.

Lab 3¶

Verified object reuse after kfree().

Confirmed that freeing an object updated the bitmap correctly and that subsequent allocations reused the lowest-index free object.

Lab 4¶

Validated kzalloc() and kcalloc().

Verified:

Zero-initialized allocation
Reuse of previously freed objects
Integer-overflow detection in kcalloc()

Lab 5¶

Validated GFP allocation rules.

Confirmed that:

GFP_KERNEL succeeds in process context.
GFP_KERNEL is rejected in IRQ context.
GFP_ATOMIC succeeds in IRQ context.

Result¶

A complete simplified Linux kernel memory allocation path is now available.

kmalloc()
    ↓
kmalloc cache lookup
    ↓
kmem_cache_alloc()
    ↓
SLUB
    ↓
Buddy Allocator
    ↓
Physical Pages

The memory subsystem now closely resembles the architecture used by the Linux kernel, where kmalloc() serves as the public allocation interface while SLUB and the Buddy Allocator remain internal implementation layers.

Next¶

Next, we will continue exploring Linux kernel memory management by studying additional allocation mechanisms and their relationship with the existing kmalloc() infrastructure.