物理内存页分配算法实现
物理内存页分配算法实现
如果要在ucore中实现连续物理内存分配算法，则需要考虑的事情比较多，相对课本上的物理内存分配算法描述要复杂不少。下面介绍一下如果要实现一个FirstFit内存分配算法的大致流程。
lab2的第一部分是完成first_fit的分配算法。原理FirstFit内存分配算法上很简单，但要在ucore中实现，需要充分了解和利用ucore已有的数据结构和相关操作、关键的一些全局变量等。
关键数据结构和变量
first_fit分配算法需要维护一个查找有序（地址按从小到大排列）空闲块（以页为最小单位的连续地址空间）的数据结构，而双向链表是一个很好的选择。
libs/list.h定义了可挂接任意元素的通用双向链表结构和对应的操作，所以需要了解如何使用这个文件提供的各种函数，从而可以完成对双向链表的初始化/插入/删除等。
kern/mm/memlayout.h中定义了一个 free_area_t 数据结构，包含成员结构
list_entry_t free_list; // the list header 空闲块双向链表的头
unsigned int nr_free; // # of free pages in this free list 空闲块的总数（以页为单位）
显然，我们可以通过此数据结构来完成对空闲块的管理。而default_pmm.c中定义的free_area变量就是干这个事情的。
kern/mm/pmm.h中定义了一个通用的分配算法的函数列表，用pmm_manager 表示。其中init函数就是用来初始化free_area变量的, first_fit分配算法可直接重用default_init函数的实现。init_memmap函数需要根据现有的内存情况构建空闲块列表的初始状态。何时应该执行这个函数呢？
通过分析代码，可以知道：
kern_init --> pmm_init-->page_init-->init_memmap--> pmm_manager->init_memmap
所以，default_init_memmap需要根据page_init函数中传递过来的参数（某个连续地址的空闲块的起始页，页个数）来建立一个连续内存空闲块的双向链表。这里有一个假定page_init函数是按地址从小到大的顺序传来的连续内存空闲块的。链表头是free_area.free_list，链表项是Page数据结构的base->page_link。这样我们就依靠Page数据结构中的成员变量page_link形成了连续内存空闲块列表。
设计实现
default_init_memmap函数将根据每个物理页帧的情况来建立空闲页链表，且空闲页块应该是根据地址高低形成一个有序链表。根据上述变量的定义，default_init_memmap可大致实现如下：
default_init_memmap(struct Page *base, size_t n) {
struct Page *p = base;
for (; p != base + n; p ++) {
p->flags = p->property = 0;
set_page_ref(p, 0);
}
base->property = n;
SetPageProperty(base);
nr_free += n;
list_add(&free_list, &(base->page_link));
}
如果要分配一个页，那要考虑哪些呢？这里就需要考虑实现default_alloc_pages函数，注意参数n表示要分配n个页。另外，需要注意实现时尽量多考虑一些边界情况，这样确保软件的鲁棒性。比如
if (n > nr_free) {
return NULL;
}
这样可以确保分配不会超出范围。也可加一些 assert函数，在有错误出现时，能够迅速发现。比如 n应该大于0，我们就可以加上
assert(n \> 0);
这样在n<=0的情况下，ucore会迅速报错。firstfit需要从空闲链表头开始查找最小的地址，通过list_next找到下一个空闲块元素，通过le2page宏可以由链表元素获得对应的Page指针p。通过p->property可以了解此空闲块的大小。如果>=n，这就找到了！如果<n，则list_next，继续查找。直到list_next== &free_list，这表示找完了一遍了。找到后，就要从新组织空闲块，然后把找到的page返回。所以default_alloc_pages可大致实现如下：
static struct Page *
default_alloc_pages(size_t n) {
if (n > nr_free) {
return NULL;
}
struct Page *page = NULL;
list_entry_t *le = &free_list;
while ((le = list_next(le)) != &free_list) {
struct Page *p = le2page(le, page_link);
if (p->property >= n) {
page = p;
break;
}
}
if (page != NULL) {
list_del(&(page->page_link));
if (page->property > n) {
struct Page *p = page + n;
p->property = page->property - n;
list_add(&free_list, &(p->page_link));
}
nr_free -= n;
ClearPageProperty(page);
}
return page;
}
default_free_pages函数的实现其实是default_alloc_pages的逆过程，不过需要考虑空闲块的合并问题。这里就不再细讲了。注意，上诉代码只是参考设计，不是完整的正确设计。更详细的说明位于lab2/kernel/mm/default_pmm.c的注释中。希望同学能够顺利完成本实验的第一部分。