Toy OS 7: Slab and kmalloc

Toy OS worklog: 1. Real mode · 2. Segmentation · 3. Paging · 4. Kernel · 5. Interrupts · 6. Buddy · 7. Slab · Source

The buddy allocator (post 6) hands out 4 KiB at a time, but a list node, a cache descriptor or a small buffer is a few dozen bytes. A slab allocator sits on top of it. It takes whole pages, cuts each into equal-size objects, and keeps one cache per object size. This post covers the slab layer (442dcfe) and kmalloc/kfree on top of it (fc88a1d), the last commit of this series.

ULK (ch. 8, “Memory Area Management”) describes Linux’s original SLAB allocator. It has cache descriptors, separate slab descriptors, per-object descriptor arrays, coloring and per-CPU caches, after Bonwick’s design for Solaris. toy-os is much smaller, and in two ways it is closer to SLUB, which replaced SLAB as Linux’s default: the slab’s bookkeeping lives in its struct page, and a free object itself holds the pointer to the next free object.

Table of Contents

• One struct page, three owners
• Caches and slabs
• Allocating and freeing objects
• kmalloc and kfree
• Watching it work
• What’s next
• References

One struct page, three owners

The slab commit adds three fields to struct page and one flag:

#define PG_reserved (1u << 0)
/* Set if it is the first page of a free block in buddy system */
#define PG_buddy (1u << 1)
/* Set on every page that is a slab, the slab fields below are valid */
#define PG_slab (1u << 2)
/* Set on the first page of a kmalloc too large for a slab, order holds its size */
#define PG_large (1u << 3)

struct page {
    uint16_t flags;
    uint16_t order;
    int32_t refcount;
    /* buddy: the free list of its order, slab: the partial list of its cache */
    struct list_head lru;
    /* PG_slab only, a slab is exactly one page so these describe the whole slab */
    struct kmem_cache *slab_cache;
    void *freelist;                 /* first free object, NULL when the slab is full */
    uint32_t inuse;                 /* objects handed out, 0 is empty, cache->objects is full */
};

The 28 bytes of struct page and who uses which field.

As my commit note says, lru is “shared” by the buddy and slab layers. A page cannot be free in the buddy system and hold objects in a slab at the same time, so the same list_head links free blocks in post 6 and partial slabs here. Linux’s struct page takes this much further, with unions of fields for every possible owner.

Caches and slabs

A cache is little more than a size and a list:

/* Example: struct kmem_cache "kmalloc-1024"
 * size = 1024, objects = 4
 * partial is a linked list whose container is struct page
 */
struct kmem_cache {
    const char *name;
    uint32_t size;
    uint32_t objects;
    /* Non-full slabs, slab = page frame here */
    struct list_head partial;
};

void kmem_cache_init(struct kmem_cache *cache, const char *name, uint32_t size, uint32_t align) {
    if (align == 0)
        align = sizeof(void *);
    ASSERT(is_pow2(align));
    ASSERT(size <= PAGE_SIZE && align <= PAGE_SIZE);

    size = ALIGN_UP(MAX(size, sizeof(void *)), align);

    cache->name = name;
    cache->size = size;
    cache->objects = PAGE_SIZE / size;
    INIT_LIST_HEAD(&cache->partial);
}

A slab is exactly one page. Every object is at least pointer-sized, because a free object stores the pointer to the next free object in its first 4 bytes. new_slab takes a page from the buddy system and threads that list through it. It walks backwards, so the list starts at object 0 and runs in address order:

/* Carve a fresh page */
static struct page *new_slab(struct kmem_cache *cache) {
    struct page *page = alloc_pages(0);
    char *base;

    if (!page)
        return NULL;

    base = page_address(page);
    page->freelist = NULL;
    /* Each slot either holds a valid obj or pointer to the next slot */
    /* As long as the slab is "partial", it's freelist is bound to point to a
     * free slot which should further point to its next free slot if possible
     */
    for (uint32_t i = cache->objects; i > 0; i--) {
        void **obj = (void **)(base + (i - 1) * cache->size);
        *obj = page->freelist;
        page->freelist = obj;
    }
    page->flags |= PG_slab;
    page->slab_cache = cache;
    page->inuse = 0;
    list_add(&page->lru, &cache->partial);
    return page;
}

The list costs no memory: free objects are unused memory anyway. Once objects are allocated and freed in random order, it no longer runs in address order:

One slab after four allocations and one free. The free list is a stack (LIFO).

Allocating and freeing objects

void *kmem_cache_alloc(struct kmem_cache *cache) {
    struct page *page;
    void **obj;

    if (list_empty(&cache->partial) && !new_slab(cache))
        return NULL;

    /* pop the head of the first partial slab's free list */
    page = list_first_entry(&cache->partial, struct page, lru);
    obj = page->freelist;
    page->freelist = *obj;
    page->inuse++;

    /* a full slab leaves the partial list, kmem_cache_free puts it back */
    if (page->inuse == cache->objects)
        /* Do not worry about losing track of full slabs, see kmem_cache_free() */
        list_del_init(&page->lru);
    return obj;
}

The cache tracks only partial slabs, the ones with at least one free object, so allocation never has to search. A full slab simply drops off the list. Nothing needs to find it until one of its objects is freed, and then the object’s address leads straight back to it: virt_to_page(obj) gives the page, and the page gives its cache.

void kmem_cache_free(struct kmem_cache *cache, void *obj) {
    struct page *page = obj_to_page(obj);

    ASSERT((page->flags & PG_slab) && page->slab_cache == cache);
    /* must be the start of an object, not a pointer into the middle of one */
    ASSERT(((uintptr_t)obj - (uintptr_t)page_address(page)) % cache->size == 0);
    /* a cheap double free check, it only catches freeing the last freed object again */
    ASSERT(page->inuse > 0 && obj != page->freelist);

    /* a full slab is about to have a free object, so it can serve allocations again */
    if (page->inuse == cache->objects)
        list_add(&page->lru, &cache->partial);

    /* push onto the free list */
    *(void **)obj = page->freelist;
    page->freelist = obj;
    page->inuse--;

    /* keep one slab even when empty, so allocating and freeing a single
     * object in a loop does not go to the buddy system every time */
    if (page->inuse == 0 && !list_is_singular(&cache->partial))
        free_slab(page);
}

Empty slabs go back to the buddy system (free_slab clears PG_slab, then calls free_pages). The exception is a cache’s last slab. Without that exception, a loop of kmalloc(32)/kfree would split and merge a buddy block on every iteration.

kmalloc and kfree

kmalloc picks one of nine caches, kmalloc-8 to kmalloc-2048, by rounding the size up to a power of two. Anything bigger goes straight to the buddy allocator:

/* index of the smallest kmalloc cache holding size bytes, 0 < size <= KMALLOC_MAX_CACHE_SIZE */
static inline uint32_t kmalloc_index(uint32_t size) {
    if (size <= (1u << KMALLOC_MIN_SHIFT))
        return 0;
    /* 32 - clz(size - 1) is log2 of size rounded up to a power of 2 */
    return 32 - __builtin_clz(size - 1) - KMALLOC_MIN_SHIFT;
}

void *kmalloc(size_t size) {
    struct page *page;
    uint32_t order;

    if (size == 0 || size > KMALLOC_MAX_SIZE)
        return NULL;
    if (size <= KMALLOC_MAX_CACHE_SIZE)
        return kmem_cache_alloc(&kmalloc_caches[kmalloc_index(size)]);

    /* too large for a slab: a buddy block of its own, its first page
     * remembers the order so kfree knows how much to give back */
    order = get_order(size);
    page = alloc_pages(order);
    if (!page)
        return NULL;
    page->flags |= PG_large;
    page->order = order;
    return page_address(page);
}

There is no kmalloc-4096. A 4 KiB object would fill a whole page, and a page is what the buddy allocator already hands out. A size of 2049 bytes still costs a whole page, which is the price of power-of-two classes. Every object is aligned to its size (up to PAGE_SIZE), since a slab starts on a page boundary and objects are packed at multiples of the size.

kfree gets only a pointer. The page’s flags say where it came from, and that is the point of PG_large. As my commit note says, it is cheap and lets kmalloc and kfree pair up:

void kfree(const void *ptr) {
    struct page *page;
    uint32_t order;

    if (!ptr)
        return;

    /* the page says which kind of kmalloc it was */
    page = obj_to_page(ptr);
    if (page->flags & PG_slab) {
        kmem_cache_free(page->slab_cache, (void *)ptr);
        return;
    }

    ASSERT((page->flags & PG_large) && ptr == page_address(page));
    order = page->order;
    page->flags &= ~PG_large;
    page->order = 0;
    free_pages(page, order);
}

The two paths through kmalloc, and how kfree finds the right one.

The checks catch a lot: a pointer below 0xC0000000 or beyond RAM, a pointer into the middle of an object, a page that is neither a slab nor a large allocation, and freeing the same object twice in a row. My commit note also records what they miss. A wrong pointer that happens to land on the start of another object passes every check, and that object is freed while someone still uses it. Linux catches that class of bug with KASAN, which keeps shadow memory to track whether each byte may be accessed.

kmem_cache_create() makes a cache for a specific object type. The struct kmem_cache itself (20 bytes) comes from kmalloc, in this case from kmalloc-32.

Watching it work

main() at fc88a1d only calls init_kmalloc(). To see the allocator at work, add a throwaway test after it (it is not part of the commit):

static void kmalloc_demo(void) {
    char *a = kmalloc(24);
    char *b = kmalloc(24);
    char *c = kmalloc(100);
    char *big = kmalloc(5000);

    printk("kmalloc(24)   = %p\n", a);
    printk("kmalloc(24)   = %p\n", b);
    printk("kmalloc(100)  = %p\n", c);
    printk("kmalloc(5000) = %p\n", big);
    kfree(b);
    printk("kfree(%p), then kmalloc(20) = %p\n", b, kmalloc(20));
}

The test’s output. Every address can be predicted from the free lists in post 6.

1. kmalloc(24) rounds up to kmalloc-32, which has no slab yet. new_slab asks for an order-0 page, and the order-0 list holds exactly one: pfn 0x500, the page left over from the loader’s tables. Object 0 is at 0xC0500000.
2. kmalloc(24) again pops object 1 from the same slab, 32 bytes later: 0xC0500020.
3. kmalloc(100) goes to kmalloc-128, which needs a new slab. The order-0 list is now empty, so the buddy allocator splits the order-1 block at 0x582. It returns 0x582 and puts 0x583 on the order-0 list. Result: 0xC0582000.
4. kmalloc(5000) is too big for a slab: get_order(5000) = 1, two pages. The order-1 list is empty after step 3, so the order-2 block at 0x584 splits into 0x584 (returned) and 0x586 (back on the order-1 list). That is the split pictured in post 6. Result: 0xC0584000, with PG_large and order = 1 on its first page.
5. kfree(b) then kmalloc(20): b goes back on the head of its slab’s free list, and the next kmalloc-32 allocation gets it right back, 0xC0500020. The most recently freed object is the most likely to still be in the CPU cache.

All of these are direct-map addresses: physical = virtual − 0xC0000000, and each allocation is physically contiguous. That is what DMA buffers and page tables need, but it is also the weakness of kmalloc. Once physical memory fragments, a large kmalloc fails even when there is plenty of free memory in total.

What’s next

That is where this series stops (fc88a1d). The commits after it give the kernel vmalloc (virtually contiguous memory built from single pages, with unmapped guard pages between areas), threads with vmalloc’ed kernel stacks, and a double-fault task gate that catches kernel stack overflows. They may become the next worklogs.

References

1. D. P. Bovet and M. Cesati, Understanding the Linux Kernel, 3rd ed., ch. 8 “Memory Management”, “Memory Area Management”: the slab allocator, cache and slab descriptors, general and specific caches, and kmalloc().
2. J. Bonwick, “The Slab Allocator: An Object-Caching Kernel Memory Allocator”, USENIX Summer 1994 Technical Conference.
3. J. Corbet, “The SLUB allocator”, LWN.net, 2007; Linux source mm/slub.c.
4. The Linux kernel documentation, Kernel Address Sanitizer (KASAN).
5. navi, 从零开始写 OS 内核 - 实现堆和 malloc, segmentfault. It builds a heap allocator instead of slabs, a useful contrast.
6. 郑钢, 《操作系统真相还原》, ch. 12 (进一步完善内核): the book’s sys_malloc, built on arenas of 16–1024-byte blocks.