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.

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

$ git fetch origin
$ git checkout -b alloc origin/xv6-21au
$ make clean

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. Note that usertests may take a while to finish, so be patient.

Hints

Here’s one reasonable plan of attack.

• Add dummy slab.h and slab.c (see code below) to kernel/, and modify Makefile to compile the source files.

• Modify kernel/file.c to use the slab allocator: replace the array struct file file[NFILE] in ftable with struct kmem_cache cache, and use kmem_cache_alloc/kmem_cache_free in filealloc/fileclose to manage file structures. This should pass the first test (filetest) of alloctest.

• The dummy slab allocator directly calls the page allocator to allocate one page for each object; for instance, allocating 10 struct file objects would consume 10 pages, wasting memory. You need to modify the dummy slab allocator to allocate smaller objects instead. The next test (memtest) of alloctest checks that your solution consumes no more than one page after opening 10 files. Feel free to design your own data structures to pass this test. For example, you may implement a free list of slabs and a free list of objects within each slab. You may find the functions provided by kernel/list.c useful.

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

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