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