Lab: Allocator for xv6
For this lab we have replaced the page allocator in the xv6 kernel with a buddy
allocator. You will modify xv6 to use this allocator to allocate and free file
structs so that xv6 can have more open file descriptors than the
existing system-wide limit NFILE. Furthermore, you will
implement an optimization that reduces the buddy's use of memory.
You are done if your modified kernel passes both alloctest and
To start the lab, switch to the alloc branch:
$ git fetch
$ git checkout alloc
The only files you should change in this lab are kernel/buddy.c and
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 structs, 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 is to adopt the buddy allocator
from the allocator lecture, which we have
added to xv6 in kernel/buddy.c and kernel/list.c.
Your job is to further improve xv6's memory allocation in two ways:
- Modify kernel/file.c to use the
buddy allocator so that the number of file structures is limited by
memory rather than NFILE.
- The buddy allocator is space inefficient. The alloc
array has a bit for each block for each size. There is a clever
optimization that reduces the cost to only one bit for each pair of
blocks. This single bit is B1_is_free XOR B2_is_free, for a buddy
pair of blocks B1 and B2. Each time a block is allocated or
freed, you flip the bit to reflect the change. For example, if B1
and B2 are allocated, the bit will be zero and if B1 is freed the
bit changes to 1. If the bit is 1 and B2 is freed, then we know
that B1 and B2 should be merged. Saving 1/2 bit per block matters
when xv6 uses the buddy allocator for the roughly 128 Mbyte of
free memory that xv6 must manage: this optimization saves about 1
MByte of memory.
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
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 as much memory as possible, and fails
if less than a certain amount is available.
It's effectively a test to see how much memory the kernel is using.
The test will fail with the unoptimized buddy
allocator that we have given you.
When you are done, your kernel should be able to run both alloctest
and usertests. That is:
ALL TESTS PASSED
You'll want to remove line 19 in kernel/file.c, which
declares file[NFILE]. Instead, allocate struct
file in filealloc using bd_malloc.
In fileclose you will free the allocated memory. Note that
you can simplify fileclose, because ff isn't
fileclose still needs to acquire ftable.lock
because the lock protects f->ref.
bd_malloc doesn't clear the memory it returns;
instead, allocated memory starts out with whatever content
it had from its last use.
Callers should not assume that it starts out containing zeroes.
You can use bd_print to print the state of the
Compared to the lecture notes, we have
modified bd_init so that it is
called with the range of physical memory
available for allocation.
memory for the buddy data structures from that memory.
It initializes its data structures
accordingly: bd_init marks memory that is used for buddy
data structures as allocated so that it won't be
re-allocated. Furthermore, we have modified bd_init to handle
an amount of memory that isn't a power of 2 by marking unavailable memory as
allocated. Finally, we modified the buddy allocator to serialize
concurrent calls to it using a lock.
This completes the lab. Commit your changes and type make
handin in the lab directory to hand in your lab.
Dynamically allocate other data structures in xv6 that are
statically allocated. Some require significant amount of changes
(e.g., dynamically allocating proc structures), but others are