MIT 6.828 - 3. Lab 03: Allocator for xv6

Tags: MIT 6.828

实验总结

  1. 本次实验用时约两个小时，修改了 xv6 中大量恶臭代码。

测试结果：

1
2
3
4
5
6
7
8
$ make grade
alloctest:
OK (7.2s)
alloctest:
OK (5.8s) 
usertests:
OK (84.3s)
Score: 100/100

0. 实验准备

实验指导链接

上来直接：

1
2
$ cd xv6-riscv-fall19
$ git checkout alloc

实验分为两个子任务：

  1. 给 xv6 的 vfs 加上 malloc（之前是静态内存池）
  2. 修改 xv6 的 buddy allocator，通过维护一对 buddy 的 B1_is_free XOR B2_is_free 这个占用状态，节约了 ~1M 内存。

感觉是重在阅读和理解 xv6 代码，这两个 lab 代码量都很小。

1. file.c

把 filealloc() 中遍历 ftable.file 的代码和 fileclose() 相应的释放代码替换为 bd_malloc() 即可。

我的修改

2. buddy.c

这个 buddy allocator 中维护了两个 bitset ，一个存是否分裂 bd_sizes[k].split，另一个存是否已占用 bd_sizes[k].alloc。 只需要不断查找 bit_* 这组工具函数出现的位置然后替换成相应的实现即可。

重难点不在于动态 malloc/free 的部分，实际上这些代码很好改。关键在于 bd_initfree() 和 bd_initfree_pair() 部分。

因为 buddy allocator 管理内存的同时需要在内存区域头部放一些 metadata，且内核提供内存区域的长度也很可能不是对其 2^k 次方的，故需要把一些区域 mark 为 allocated 。同时这些区域对应的 buddy 可能需要被加入 free_list （bd_initfree()/bd_initfree_pair() 用来完成此工作）

根据 bd_init() 中代码：

1
2
3
4
5
6
7
8
9
10
11
// done allocating; mark the memory range [base, p) as allocated, so
// that buddy will not hand out that memory.
int meta = bd_mark_data_structures(p);

// mark the unavailable memory range [end, HEAP_SIZE) as allocated,
// so that buddy will not hand out that memory.
int unavailable = bd_mark_unavailable(end, p);
void *bd_end = bd_base+BLK_SIZE(MAXSIZE)-unavailable;

// initialize free lists for each size k
int free = bd_initfree(p, bd_end, p, end);

这些不可用内存对应的内存区间为 [begin, p) 和 [end, HEAP_SIZE)。在 bd_initfree_pair() 中特判这些内存范围，就可以把他们的 buddy 识别出来，而无需查找 bd_sizes[k].alloc 。

我的修改

知识共享许可协议 2000 - 2099 MonKey's Blog | 自豪地采用 Hexo + Pandoc + KaTeX + Highlight.js