NJU OSLAB 速通记录
Day -9
假期搞了一堆光说不练的事情，结果眼看着 OSlab 的 HardDDL 就在眼前了，胡适之啊胡适之，你不能再坐视不理了！
于是我就这样决定开始速通我的操作系统实验（含三个大实验和三个小实验）。
不妨从第一个实验 kalloc 开始。实验要求实现一个内存分配器，允许多处理器并发申请/释放内存。分配的内存一定按照（能包含它的最小的）二的次幂对齐。
我们先考虑单线程/上把大锁的情况。
脑子里一下出现一个区间二叉树的结构，仔细想想太复杂了，原因如下。
- 逻辑太复杂了，不利于维护。
- 没法做到 in-place，即元数据结构没法随所在空间节点的分配而删除。
然后发现不必维护整棵树，只需维护所有极大未分配子树即可。发现它们一定是无交的，于是可以做到 in-place。
那么怎么常数时间拉出一个指定大小的未分配子树呢？
考虑把所有极大未分配子树按照大小分组，每个插个链表就完事了，每次先看对应大小的有没有，如果没有就递归分配一个更大一级的，把更大一级的拆成两半。
看上去非常之完美！
大约只需要定义如此数据结构：
// 最大允许分配内存 16 MiB
#define MAXSCALE 24
// In place 的数据结构
typedef struct span_t
{
uint8_t scale; // 规模
span_t *next_span; // 下一个区间
} span_t;
// 链表
span_t *span_heap[MAXSCALE + 1];
对于小到连这个数据结构都装不下的空间，我们的选择是……摆烂。我们只把空间划分到 16B 即可，小内存直接“当作”大内存来分配。
In-place 意味着分配内存后我们将丢失所有的元数据，那么还原时就会遇到很大的问题：free 只提供一个头指针，如何确定它是哪一块内存？
因此我们需要对每个分配出去的头指针记录下分配的单元的规模，以便还原。
这是个困难的事情，因为 lab 只给了 1M 的静态数据区，没法存下这么大的数组。我们只能使用动态的 Trie/Radix 树来存下这些值。
这时候又麻烦了，Trie/Radix 怎么分配新内存……？必须创建一个约 32 KB 大小的缓冲区，每次要用了递归调用 kalloc 就新分配一段空间。
在归还时，必须检查兄弟子树是否未被分配，如果未被分配的话需要归并。
现在考虑多处理器，且不能用一把大锁锁上整个链表，同时还得支持某个处理器分配的内存在另外一个处理器释放，听着就麻烦。
讲义说大于一页的内存分配是较为罕见的，所以我们令大于一页的内存全部按老办法分配。
小内存和整页内存频繁分配，我们可以考虑一次取走一个较大的 Span 给本处理器，用完了再申请；如果归还导致本处理器的空闲内存块较多较大，那么就归还。
这样就引入了一个单处理器的内存池，我们仍然可以仿照大处理器的结构同构地构造单处理器的池。
太困了，明天再说吧。
另外值得一提的是按照讲义做了一个简易的测试框架，其实就是把 pmm.c 和一些其他源文件链接起来了，并重定向了它的头文件，使得这个模块可以被直接在 linux 的运行时下调用测试。