ucore lab2
目录
练习0：填写已有实验
使用可视化diff/mege工具meld可以轻松完成填写代码的任务。只需要注意lab 2对lab 1中的文件进行了修改，不能把lab 1中的代码照搬过去。
练习1：实现first-fit连续物理内存分配算法
物理地址空间的探查
在实现物理内存的分配之前必须先探查出当前物理内存的布局和大小，根据这些信息计算出操作系统可操控的内存大小并将其划分为等大的物理页。
物理地址空间的探查在bootloader中完成，探查出的信息存放在物理地址0x8000,,C程序使用结构体struct e80map对这些数据进行操作。
// 定义在kern/mm/memlayout.h中
struct e820map {
int nr_map; //探查到的内存块总数
struct {
uint64_t addr; //内存块的起始物理地址
uint64_t size; //内存块的大小
uint32_t type; //内存块的类型
} __attribute__((packed)) map[E820MAX];
};
物理页的初始化
探查到的内存使用物理地址描述，ucore设置了物理内存地址到虚拟内存地址的临时映射关系：
虚拟地址 = 物理地址 + 0xC0000000
ucore支持的最大物理地址空间是KMEMSIZE(0x380000000)。
空闲块以物理页（4096字节）为为单位，空闲块中的第一个物理页代表整个空闲块，每一个物理页都对应着一个记录它的结构struct Page：
struct Page {
int ref; // page frame's reference counter
uint32_t flags; // array of flags that describe the status of the page frame
unsigned int property; // the num of free block, used in first fit pm manager
list_entry_t page_link; // free list link
};
-
当
flags设置为Reserved时，该物理页被硬件保留，操作系统无法使用 -
当
flags未被设置为Reserved且未被设置为Property时，该物理页已被操作系统分配 -
当
flags未被设置为Reserved且设置为Property时，该物理页空闲 -
当物理页是空闲块的第一个物理页时，
property生效，代表该空闲块的大小（以物理页为单位）
物理页的初始化的核心在于：将探查到的物理内存与相应的Page关联起来。
物理页的初始化由kern/mm/pmm.c中的page_init()和init_memmap()完成。page_init负责确定探查到的物理内存块与对应的struct Page之间的映射关系，Page的初始化工作由init_memmap()调用内存管理器pmm_manager的init_memmap()方法完成。
page_init()的算法为：
- 遍历
memmap指针指向的结构e820map中的元素，求出其中的最高物理地址，计算出可用地址总大小 - 计算出所需的
Page结构，并顺序存放在程序的.bss段之上，形成以物理地址的PPN为索引的Page数组 - 再次遍历
e820map结构，将所有的Page设置为Reserved，调用init_memmap初始化操作系统可用的且地址在支持范围内物理内存对应的Page结构
init_memmap的算法为：
- 将所有可用的
Page的flags设置为Property，引用计数设置为0,property设置为0,初始化page_link - 空闲块的第一个物理块的
property设置为该空闲块的大小,将其加入到空闲链表末尾
default_init_memmap(struct Page *base, size_t n) {
assert(n > 0);
struct Page *p = base;
for (; p != base + n; p ++) {
// 在查找可用内存并分配struct Page数组时就已经将将全部Page设置为Reserved
// 将Page标记为可用的:清除Reserved,设置Property,并把property设置为0( 不是空闲块的第一个物理页 )
assert(PageReserved(p));
p->flags = p->property = 0;
SetPageProperty(p);
set_page_ref(p, 0);
list_init(&(p->page_link));
}
cprintf("Page address is %x\n", (uintptr_t)base);
base->property = n;
nr_free += n;
list_add(free_list.prev, &(base->page_link));
}
只有操作系统可使用的物理页使用该函数进行初始化，因此不能被使用的物理页的Page中的Reserved属性不会被修改，确保了所有的物理页都有正确的Page。
e820map结构中数组map中的内存块是从低地址从高地址排列的，设置内存块对应的Page时都是插入到链表的尾部，因此最后形成的空闲链表是从低地址到高地址的有序链表。
为了便于内存块的边界，我的实现要求空闲块中只有第一个物理页的property域不为0,其他物理页的property必须为0。
初始化完成后的物理内存布局：
+-------------+-------------+--------------+------------+------------------------+
| | e820map | | Pages | Free memory |
+-------------+-------------+--------------+------------+------------------------+
^ ^ ^ ^ ^
| | | | |
0 0x8000 .bss段结束位置(end) freemem 0x380000000
物理页的分配
设计目标：
- 能标识请求失败的原因，便于调试
- 每次分配的内存块都是空闲链表中的最低地址空闲块
- 正确处理空闲块分割、
static struct Page *
default_alloc_pages(size_t n) {
assert(n > 0);
/* There are not enough physical memory */
if (n > nr_free) {
warn("memory shortage");
return NULL;
}
struct Page *page = NULL;
struct Page *p = NULL;
list_entry_t *le = &free_list;
/* try to find empty space to allocate */
while ((le = list_next(le)) != &free_list) {
p = le2page(le, page_link);
if (p->property >= n) {
page = p;
break;
}
}
/* external fragmentation */
if (page == NULL) {
warn("external fragmentation: There are enough memory, but can't find continuous space to allocate");
return NULL;
}
unsigned int property = page->property;
/* modify pages in allocated block(except of first page)*/
p = page + 1;
for (; p < page + n; ++p) {
ClearPageProperty(p);
// property is zero, so we needn't modify it.
}
/* modify first page of allcoated block */
ClearPageProperty(page);
page->property = n;
nr_free -= n;
/*
* If block size is bigger than requested size, split it;
* */
if (property > n) {
p = page +
p->property = property - n;
list_add_after(&(page->page_link), &(p->page_link));
}
list_del(&(page->page_link));
return page;
}
物理页的回收
default_free_pages(struct Page *page, size_t n)设计目标：
- 能够正确地处理参数：当1
n超过已分配块的页数时，回收整个块;当n小于也分配块的页数时，回收n页，剩下的内存不回收;当base指向的内存块不是已分配块的起始地址时，从base开始回收 - 能够正确的合并空闲块（我的实现回收在
base块高地址的所有相邻空闲块） - 能够正确分割已分配块：
default_free_pages要求回收已分配块中的任意页，剩下的未回收的部分作为新的已分配块 - 在回收后，空闲链表仍然是有序的
思路:
- 根据
base和n合理分割欲回收的内存块 - 合并邻接与
base块的空闲块 - 将代表新空闲块的
page_link插入到有序空闲链表中
static void
default_free_pages(struct Page *base, size_t n) {
assert(n > 0);
/* if @base is not the beginning of the alloacted block which @base points in,
* change the #property filed of the allocated block.
*/
/* find the beginning of the allocated block.
* only begging page's #property fild is non-zero.
*/
struct Page *begin = base;
size_t count = 0;
for ( ; begin->property == 0; ++count, --begin) {
assert(!PageReserved(begin) && !PageProperty(begin));
}
/* If @base is not the beginning of the allocated block,
* split the allocated block into two part.
* One part is @begin to @base,
* other part is @base to the end of the original part.
*/
if (begin != base) {
base->property = begin->property - count;
begin->property = count;
}
/* If @n is bigger than the number of pages in the @base block,
* it is not an error, just free all pages in block.
*/
if (n > base->property) {
n = base->property;
}
/* If @n is smaller than the number of pages in @base block,
* split @base block into two block.
*/
else if (n < base->property) {
(base + n)->property = base->property - n;
base->property = n;
}
/* modify status information */
struct Page *p = base;
for (; p != base + n; ++p) {
assert(!PageReserved(p) && !PageProperty(p));
p->flags = 0;
SetPageProperty(p);
}
// extern struct Page *pages;
// struct Page *pages_end = pages + npage;
// unsigned int property, old_base_property = base->property;
// list_entry_t *pos = NULL; //insert new free block after @pos
// /* merge free blocks next to current freeing block */
// p = base + base->property;
// while ((p < pages_end) && PageProperty(p)) {
// property = p->property;
// pos = (p->page_link).prev;
// base->property += p->property;
// p->property = 0;
// list_del(&p->page_link);
// p += property;
// }
// /* merge free blocks before current freeing block */
// p = base - 1;
// while ((p >= pages)) {
// while (p->property == 0) {
// --p;
// if ((p < pages) || (p->property != 0)) break;
// }
// if ((p >= pages) && (p->property != 0)) {
// p->property += base->property;
// base->property = 0;
// base = p;
// pos = (p->page_link).prev;
// list_del(&p->page_link);
// }
// }
// /* There is no free blocks adjcent to @base block. */
// if (base->property == old_base_property) {
// list_entry_t *le = &free_list;
// while ((le = list_next(le)) != &free_list) {
// if (le2page(le, page_link) > base) {
// pos = le->prev;
// break;
// }
// }
// /* free list is empty or @base points to the upmost free block */
// if (le == &free_list)
// pos = free_list.prev;
// }
// list_add(pos, &base->page_link);
// nr_free += n;
/* merge adjcent free blocks */
list_entry_t *le = list_next(&free_list), *pos = free_list.prev, *merge_before_ptr = NULL;
unsigned int old_base_property = base->property;
/* merge free blocks */
while (le != &free_list) {
p = le2page(le, page_link);
/* free_list is ascending sorted, only one free block before @base block will be merged */
if ((p + p->property == base)) {
p->property += base->property;
base->property = 0;
base = p;
pos = le->prev;
merge_before_ptr = le;
list_del(le);
}
if ((base + base->property) == p) {
base->property += p->property;
p->property = 0;
pos = le->prev;
list_del(le);
}
le = list_next(le);
}
/* if there may be free blocks before @base block, try to merge them */
if (merge_before_ptr != NULL) {
le = merge_before_ptr->prev;
while (le != &free_list) {
p = le2page(le, page_link);
if (p + p->property == base) {
p->property += base->property;
base->property = 0;
base = p;
pos = le->prev;
list_del(le);
}
le = list_prev(le);
}
}
/* @pos indicate position in whith @base's page_link should insert;
* only when there are no adjcent free blocks, should we try to find insertion position
*/
if (base->property == old_base_property) {
le = list_next(&free_list);
while (le != &free_list) {
if (le2page(le, page_link) > base) {
assert((base + base->property) < le2page(le, page_link));
pos = le->prev;
break;
}
le = list_next(le);
}
}
list_add(pos, &base->page_link);
nr_free += n;
}
运行结果：
缺陷
- 空闲链表是升序的，从合并空闲块时从链表头开始遍历，最多只能够合并一个在
base块之前（低地址）的空闲块。为了将base块之前的空闲块全部合并，不得不在第一次合并后，从base块之前的空闲块向链表头遍历。 - 使用链表，分配、合并都要遍历链表，时间复杂度为O(n)。可以使用平衡二叉树替代链表，将时间复杂度降低到O(n*logn)。
default_check有bug
//风格的注释中的代码功能和下面未加注释的代码功能相同，但是注释中的代码通过查找欲回收的块相邻的Page的flags域来查找、合并空闲块。这段代码是正确的，却无法通过default_check测试。
default_check无法修改内存布局，只能临时篡改空闲链表，制造出没有可用内存或只有特定数目的可用内存的假象。当实现不通过空闲链表查找邻接空闲块时，就会“看穿”测试代码制造的假象，发现并合并空闲块、修改怕property域，测试检查对应的property时就会出错。
无法通过的default_check代码如下（之后的代码进行的是相同的检查）：
struct Page *p0 = alloc_pages(5), *p1, *p2;
assert(p0 != NULL);
assert(!PageProperty(p0));
list_entry_t free_list_store = free_list; //制造没有可用内存的假象，但是邻接空闲块仍然存在
list_init(&free_list);
assert(list_empty(&free_list));
assert(alloc_page() == NULL);
unsigned int nr_free_store = nr_free;
nr_free = 0;
free_pages(p0 + 2, 3); //只回收一部分内存。该内存块高地址处有相邻的空闲块
assert(alloc_pages(4) == NULL);
assert(PageProperty(p0 + 2) && p0[2].property == 3);
assert((p1 = alloc_pages(3)) != NULL);
assert(alloc_page() == NULL);
assert(p0 + 2 == p1);
测试用例分配了大小为5页的内存，但只回收其中第3页及之后的内存。
回收时，注释中的代码发现在欲回收的块之上（更高地址）的Page的flags被设置为PG_Property，这表明存在邻接空闲块，所以将这三页和其上的空闲块合并成了一个空闲块，p0[2]是这个新空闲块的第一页，property域被修改成新空闲块的页数。因此PageProperty(p0+2)为真，但p0[2].property == 3为假，测试失败。