12. Aligned SLAB Allocators - josehu07/hux-kernel GitHub Wiki

In the last chapter, we built a flexible heap memory allocator that takes in a dynamic size argument. In this chapter, we will build a set of slightly different kernel heap allocators called SLAB allocators. A SLAB allocator is responsible for allocating fixed-sized & aligned memory chunks ✭. For example, all page tables must be aligned to 4KiB page boundary, as required by x86 IA32 hardware. It is simpler and more efficient to have a dedicated allocator just for giving out page-sized & page-aligned memory chunks (slab nodes), one at a time. As you will see, the algorithm we use for SLAB allocation is surprisingly simple.

Main References of This Chapter

Scan through them before going forth:

Page-granularity kalloc() implementation of xv6 ✭
Free-Space Management chapter of the OSTEP book: segregated lists

Aligned Heap Memory Allocation

We still take an embedded approach to build a linked list of free slab nodes. This algorithm is really simple compared to last chapter's dynamically-sized allocator. There are no fancy policies. We just reserve a region in kernel heap for each SLAB allocator and divide it into nodes of desired granularity.

We name our SLAB allocation interfaces salloc_<granularity>() & sfree_<granularity>().

If a node is free, we interpret its start address as a next pointer, pointing to the next free node; there is a global head pointer to the head of this linked list;
At an salloc(), return the head node address to caller and set head to its next;
At an sfree(), we simply expect the caller to give back the aligned address, and we re-interpret it into a next pointer and points it to current list head, then update list head to be this node.

Generic Implementation

First, add the node struct definition @ src/memory/slabs.h:

/** Node of a SLAB free-list. */
struct slab_node {
    struct slab_node *next;
};
typedef struct slab_node slab_node_t;

Allocation with `salloc()`

We can support multiple SLAB allocators each for a different granularity (pages, inodes, etc.). The internal algorithm is generic no matter which granularity.

Code @ src/memory/slabs.c:

/**
 * Internal generic SLAB allocator. Give it a pointer to the pointer to
 * the first node of any initialized fixed-granularity free-list.
 *
 * There is no data integrity checks on magics.
 */
static uint32_t
_salloc_internal(slab_node_t **freelist)
{
    if (freelist == NULL) {
        warn("salloc: given free-list pointer is NULL");
        return 0;
    }

    slab_node_t *node = *freelist;

    /** No slab is free, time to panic. */
    if (node == NULL) {
        warn("salloc: free-list %p has no free slabs", freelist);
        return 0;
    }

    *freelist = node->next;
    return (uint32_t) node;
}

Deallocation with`sfree()`

Code @ src/memory/slabs.c:

/**
 * Internal generic SLAB deallocator. Assumes the address is valid and
 * properly-aligned to the granularity.
 */
static void
_sfree_internal(slab_node_t **freelist, void *addr)
{
    slab_node_t *node = (slab_node_t *) addr;

    /** Simply insert to the head of free-list. */
    node->next = *freelist;
    *freelist = node;
}

Allocator Initialization

Initializing a SLAB free-list is simply calling sfree() on all the nodes within the memory region. Take the page-granularity SLAB allocator as an example, we reserve the top 4MiB of kernel heap memory for it (so maximum 512 4KiB nodes).

// src/memory/slabs.h

/** Reserve kheap top 4MiB for the page slabs. */
#define PAGE_SLAB_MAX KMEM_MAX
#define PAGE_SLAB_MIN (KMEM_MAX - 0x00400000)


void page_slab_init();

uint32_t salloc_page();
void sfree_page(void *addr);

// src/memory/slabs.c

/** Page-granularity SLAB free-list. */
static uint32_t page_slab_btm;
static uint32_t page_slab_top;

static slab_node_t *page_slab_freelist;


/** Wrappers for differnet granularities. */
uint32_t
salloc_page(void)
{
    return _salloc_internal(&page_slab_freelist);
}

/** Wrapper for different granularities. */
void
sfree_page(void *addr)
{
    if ((uint32_t) addr < page_slab_btm || (uint32_t) addr >= page_slab_top) {
        error("sfree_page: object %p is out of page slab range", addr);
        return;
    }

    if ((uint32_t) addr % PAGE_SIZE != 0) {
        error("sfree_page: object %p is not page-aligned", addr);
        return;
    }

    /** Fill with zero bytes to catch dangling pointers use. */
    memset((char *) addr, 0, PAGE_SIZE);

    _sfree_internal(&page_slab_freelist, addr);
}


/** Initializers for SLAB allocators. */
void
page_slab_init(void)
{
    page_slab_btm = PAGE_SLAB_MIN;
    page_slab_top = PAGE_SLAB_MAX;

    page_slab_freelist = NULL;

    for (uint32_t addr = page_slab_btm;
         addr < page_slab_top;
         addr += PAGE_SIZE) {
        sfree_page((char *) addr);
    }
}

Since the top 4MiB of kernel heap is occupied by the page SLAB allocator and no longer usable by the flexible heap allocator, remember to update the corresponding numbers in kheap code:

// src/memory/kheap.h

/** The region between `kheap_curr` and slab allocators is free heap. */
#define KHEAP_MAX PAGE_SLAB_MIN

// src/memory/kheap.c
...
kheap_top = KHEAP_MAX;      // Instead of KMEM_MAX.
...

When we reserve space below the page allocator for more SLAB allocators in the future, update KHEAP_MAX accordingly.

Progress So Far

Let's try allocating & freeing a bunch of page slabs! Examples @ src/kernel.c:

/** The main function that `boot.s` jumps to. */
void
kernel_main(unsigned long magic, unsigned long addr)
{
    ... // All the previous initializations...

    /** Initialize the kernel heap allocators. */
    _init_message("initializing kernel heap memory allocators");
    page_slab_init();
    kheap_init();
    _init_message_ok();
    info("kernel page SLAB list starts at %p", PAGE_SLAB_MIN);
    info("kernel flexible heap  starts at %p", kheap_curr);

    /** Executes `sti`, CPU starts taking in interrupts. */
    asm volatile ( "sti" );

    printf("\nSallocing page1...\n");
    char *block1 = (char *) salloc_page();
    printf("block 1 @ %p\n", block1);

    printf("\nSallocing page2...\n");
    char *block2 = (char *) salloc_page();
    printf("block 2 @ %p\n", block2);

    printf("\nSfreeing page1...\n");
    sfree_page(block1);

    printf("\nSallocing page3, should reuse the highest node...\n");
    char *block3 = (char *) salloc_page();
    printf("block 3 @ %p\n", block3);

    while (1)   // CPU idles with a `hlt` loop.
        asm volatile ( "hlt" );
}

This should produce a terminal window as the following after booting up:

Real operating systems use more advanced algorithms (e.g., SLOB caches, O for "pre-initialized objects").

Current repo structure:

hux-kernel
├── Makefile
├── scripts
│   ├── gdb_init
│   ├── grub.cfg
│   └── kernel.ld
├── src
│   ├── boot
│   │   ├── boot.s
│   │   ├── elf.h
│   │   └── multiboot.h
│   ├── common
│   │   ├── debug.c
│   │   ├── debug.h
│   │   ├── port.c
│   │   ├── port.h
│   │   ├── printf.c
│   │   ├── printf.h
│   │   ├── string.c
│   │   ├── string.h
│   │   ├── types.c
│   │   └── types.h
│   ├── device
│   │   ├── keyboard.c
│   │   ├── keyboard.h
│   │   ├── timer.c
│   │   └── timer.h
│   ├── display
│   │   ├── terminal.c
│   │   ├── terminal.h
│   │   └── vga.h
│   ├── interrupt
│   │   ├── idt-load.s
│   │   ├── idt.c
│   │   ├── idt.h
│   │   ├── isr-stub.s
│   │   ├── isr.c
│   │   └── isr.h
│   ├── memory
│   │   ├── gdt-load.s
│   │   ├── gdt.c
│   │   ├── gdt.h
│   │   ├── kheap.c
│   │   ├── kheap.h
│   │   ├── paging.c
│   │   ├── paging.h
│   │   ├── slabs.c
│   │   └── slabs.h
│   └── kernel.c