Lab alloc: Memory allocator

Your task is to implement a slab allocator building on the xv6 kernel page allocator. You will use the slab allocator to allocate and free file structs so that xv6 can have more open file descriptors than the existing system-wide limit NFILE. You are done if your modified kernel passes both alloctest and usertests.

physical memory management in the xv6 book

Before writing code, you should make sure you have read §3, Page Tables of the xv6 book, especially §3.4 and §3.5 on physical memory management, and studied the corresponding code.

To start the lab, update your repository and create a new branch for your solution:

$ git fetch origin
$ git checkout -b alloc origin/xv6-19au

This creates a new “alloc” branch, starting from the original xv6-riscv code, without your solution to lab util. Each lab in this course is independent, and does not depend on the solutions to previous labs.

If you feel adventurous, you may (optionally) choose to base your solutions on top of each other (e.g., use git merge to integrate changes from lab util), but this may complicate your solutions due to the interactions of the labs. Do this at your own risk!

Git allows switching between existing branches using git checkout <branch>, though you should commit any outstanding changes on one branch before switching to a different one.

The problem

xv6 has only a page allocator and cannot dynamically allocate objects smaller than a page. To work around this limitation, xv6 declares objects smaller than a page statically. For example, xv6 declares an array of file structures, an array of proc structures, and so on. As a result, the number of files the system can have open is limited by the size of the statically declared file array, which has NFILE entries (see kernel/file.c and kernel/param.h).

The solution

The solution is to adopt the slab allocator. You may also skim the original slab allocator paper by Bonwick and the SLUB allocator, currently the default slab allocator in the Linux kernel. These references will give you some high-level idea of slab allocation. You don’t need to understand the details to finish this lab.

The slab allocator builds on the page allocator and manages objects of a specific size (e.g., file structures). It maintains a number of slabs. For simplicity, we assume that a slab spans exactly one page. Each slab contains some metadata at the beginning and a number of objects after the metadata.

For allocation, the slab allocator finds a slab that is not full and allocates a free object from the slab. If all slabs are full, the slab allocator may ask the page allocator for more free slabs (via kalloc). For deallocation, the slab allocator gives an object back to the corresponding slab. If all objects within a slab are free, the slab allocator may give the slab back to the page allocator (via kfree).

The alloctest program

To help you test your implementation, we’ve provided an xv6 program called alloctest (source in user/alloctest.c). It has two tests.

The first test allocates more than NFILE file structures by creating many processes, each opening many file descriptors. The first test will fail on unmodified xv6.

The second test creates a process that allocates a few file descriptors, and fails if the memory consumed by these files is more than one page, or if the memory is not freed after the process terminates. It’s effectively a test to see how much memory the kernel is using.

When you are done, your kernel should be able to run both alloctest and usertests. That is:

$ alloctest
filetest: start
filetest: OK
memtest: start
memtest: OK
$ usertests
...
ALL TESTS PASSED
$

You may run make grade to ensure that your code passes all of the tests.

Hints

Here’s one reasonable plan of attack.

Below is an example of slab.h:

struct kmem_cache {
  uint size;
  uint align;
  /* other fields */
};

void *kmem_cache_alloc(struct kmem_cache *cache);
void kmem_cache_free(struct kmem_cache *cache, void *obj);

Below is a dummy slab.c that directly calls the page allocator:

#include "types.h"
#include "riscv.h"
#include "defs.h"
#include "slab.h"

void *kmem_cache_alloc(struct kmem_cache *cache)
{
  return kalloc();
}

void kmem_cache_free(struct kmem_cache *cache, void *obj)
{
  kfree(obj);
}

Optional challenges

Challenge: slab allocation for multiple structures

Dynamically allocate other data structures in xv6 that are statically allocated. Some require significant changes (e.g., dynamically allocating proc structures), but others are simple.

With multiple slab allocators, you may implement some slab allocator statistics like the Linux kernel’s /proc/slabinfo.

Challenge: multi-page slabs

Extend the slab allocator to support slabs with more than one page. Since the current page allocator supports single pages only, you may want to implement a buddy allocator as in the Linux kernel. Feel free to use the skeleton code in kernel/buddy.c.

This completes the lab. In the lab directory, commit your changes, type make tarball, and submit the tarball through Canvas.