一、 实验目的

1. 理解基于段页式内存地址的转换机制
2. 理解页表的建立和使用方法
3. 理解物理内存的管理方法

二、 实验内容

1. 了解如何发现系统中的物理内存；
2. 了解如何建立对物理内 存的初步管理，即了解连续物理内存管理;
3. 了解页表相关的操作，即如何建立页表来实现虚拟内存到物理内存之间的映射，对段页 式内存管理机制有一个比较全面的了解;

三、 实验准备

在开始练习之前首先需要进行实验的大致流程以及关键数据结构进行学习与理解；

【实验概述】

本次实验主要完成ucore内核对物理内存的管理工作。
参考ucore总控函数kern_init的代码，可以清楚地看到在调用完成物理内存初始化的pmm_init函数之前和之后，是已有lab1实验的工作。
其实lab2有些修改，ucore主要有三个方面的扩展。

• boot/bootasm.S：增加了对计算机系统中物理内存布局的探测功能；
• kern/init/entry.S：根据临时段表重新暂时建立好新的段空间，为进行分页做好准备。
• kern/mm/default_pmm.[ch]：提供基本的基于链表方法的物理内存管理（分配单位为页，即4096字节）；

首先，bootloader的工作有增加，在bootloader中，完成了对物理内存资源的探测工作，让ucore kernel在后续执行中能够基于bootloader探测出的物理内存情况进行物理内存管理初始化工作。
其次，bootloader不像lab1那样，直接调用kern_init函数，而是先调用位于lab2/kern/init/entry.S中的kern_entry函数。kern_entry函数的主要任务是为执行kern_init建立一个良好的运行环境。完成这些工作后，才调用kern_init函数。
kern_init函数在完成一些输出并对lab1实验结果的检查后，将进入物理内存管理初始化的工作，即调用pmm_init函数完成物理内存的管理，是lab2的内容。

【关键数据结构】

首先看一下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
};
typedef struct list_entry list_entry_t;
struct list_entry {
    struct list_entry *prev, *next;
};

这里使用的双向链表借鉴了linux内核的双向链表结构，链表结构不包含传统数据域data，而是在具体的数据结构中包含链表节点。在本实验中，使用如下结构对页进行总体的管理。在Default.c中含链表free_area_t的结构：

free_area_t free_area;          //global page manager
#define free_list (free_area.free_list)
#define nr_free (free_area.nr_free)
/* free_area_t - maintains a doubly linked list to record free (unused) pages */
typedef struct {
    list_entry_t free_list;         // the list header
    unsigned int nr_free;           // # of free pages in this free list
} free_area_t;

free_list是整个双向链表的头节点，同时nr_free表示空闲页的数量。
下图是整个空闲页双向链表的简易示意图（将链表和数据域隔离）

【执行流程】

内存管理相关的总体控制函数是pmm_init函数，它完成的主要工作包括：
①初始化物理内存页管理器框架pmm_manager；
②建立空闲的page链表，这样就可以分配以页（4KB）为单位的空闲内存了；
③检查物理内存页分配算法；
④为确保切换到分页机制后，代码能够正常执行，先建立一个临时二级页表；
⑤建立一一映射关系的二级页表；
⑥使能分页机制；
⑦从新设置全局段描述符表；
⑧取消临时二级页表；
⑨检查页表建立是否正确；
⑩通过自映射机制完成页表的打印输出（这部分是扩展知识）

四、 实验步骤

（一） 练习0：填写已有实验

将LAB1中完成的代码（不包含拓展练习）移植到了lab2的框架中，涉及到的文件为kern/debug/kdebug.c和kern/trap/trap.c，具体内容已在LAB1报告中进行说明，此处不再赘述；

（二） 练习1：实现 first-fit 连续物理内存分配算法

在实现first fit 内存分配算法的回收函数时，要考虑地址连续的空闲块之间的合并操作。提示:在建立空闲页块链表时，需要按照空闲页块起始地址来排序，形成一个有序的链表。

在ucore中采用面向对象编程的思想，将物理内存管理的内容抽象成若干个特定的函数，并且使用结构体pmm_manager来将这些函数的指针封装起来，使得具体使用到物理内存管理所提供的服务的时候，只需要调用已经初始化完成的pmm_manager的实例中的函数指针即可，这样就实现了将物理内存管理的具体实现与ucore其他部分隔离开来的效果。
其中，上述若干个封装在pmm_manager中的提供物理内存管理服务的函数分别如下：

init：对物理内存管理器的初始化； init_memmap：对管理的空闲页的数据进行初始化；
alloc_pages：申请分配指定数量的物理页； free_pages: 申请释放若干指定物理页；
nr_free_pages：查询当前的空闲页总数； check: 对物理内存管理器进行测试；

查看default_pmm.c文件可以发现，最终ucore中所使用的物理内存管理器中的函数指针分别指向了default_init, default_init_memmap等若干函数，在lab中，通过对这些函数的实现进行修改来实现first-fit 连续内存分配算法；

1. default_init函数
   查看default_init中的内容，发现仅有对空闲内存块链表的初始化以及将总空闲数目置零的操作，这是与具体物理内存分配算法无关的，因此直接使用默认的函数实现即可；

list_init(&free_list);      
nr_free = 0;

2. default_init_memmp函数
   然后分析default_init_memmap函数，该函数的具体作用为对最初的一整块未被占用的物理内存空间中的每一页所对应的Page结构（用于描述这些页的状态）进行初始化，考虑到相邻的物理页对应的Page结构在内存上也是同样相邻的，因此可以直接通过第一个空闲物理页对应的Page结构加上一个偏移量的方式来访问所有的空闲的物理页的Page结构，具体初始化方式为：
   遍历所有空闲物理页的Page结构，将Page结构的描述空闲块的数目的成员变量置零（因此该成员变量只有在整个空闲块的第一个Page中才有意义），然后清空这些物理页的引用计数，然后通过设置flags的位的方式将其标记为空闲，实现代码如下：

struct Page *p = base;
for (; p != base + n; p ++) {
    assert(PageReserved(p));
    p->flags = p->property = 0;
    set_page_ref(p, 0);
    SetPageProperty(p);
}

接下来对空闲块的第一个页的Page结构进行初始化，具体实现为将其表示空闲块大小的成员变量设置为作为参数传入的空闲块大小（单位为页），然后更新存储所有空闲页数量，然后将这个空闲块插入到空闲内存块链表中（只需要将第一个Page的page_link插入即可）；具体的代码实现如下所示：

base->property = n;
nr_free += n;
list_add(&free_list, &(base->page_link));}

3. default_alloc_pages函数
   接下来考虑实现分配空闲页函数default_alloc_pages：该函数的具体功能为分配指定页数的连续空闲物理空间，并且将第一页的Page结构的指针作为结果返回；
   3.1. 首先对参数进行合法性检查，并且查询总的空闲物理页数目是否足够进行分配，
   如果不足够进行分配，直接返回NULL，表示分配失败；
   3.2. 接着从头开始遍历保存空闲物理内存块的链表(按照物理地址的从小到大顺序)，如果找 到某一个连续内存块的大小不小于当前需要的连续内存块大小，则说明可以进行成功分 配（第一个满足条件的空闲内存块），代码实现如下：

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;
    }}

3.3. 接下来考虑对获得的满足条件的空闲内存块进行处理，如果该内存块的大小大于需要的 内存大小，则将空闲内存块分裂成两块，物理地址较小的一块分配出来进行使用（大小 恰好为需要的物理内存的大小），而物理地址较大的那一块进行以下操作
①对第一个Page的page_link中property设置为原先的空闲块大小减掉分配的大小
②将这个分裂出来的空闲块插入到空闲块链表中
于此同时，对分配出去的物理内存的每一个的描述信息（即对应的Page结构）修改flags成员变量来将这些Page标记为非空闲，最后将原始空闲块在空闲块链表中删除掉，并且更新表示总空闲页数量的全局变量；最后用于表示分配到的物理内存的Page结构指针返回;

if (page != NULL) { // 如果寻找到了满足条件的空闲内存块
    for (struct Page *p = page; p != (page + n); ++p) {
        ClearPageProperty(p); // 将分配出去的内存页标记为非空闲
    }
    if (page->property > n) { // 如果原先找到的空闲块大小大于需要的分配内存大小，进行分裂
        struct Page *p = page + n; // 获得分裂出来的新的小空闲块的第一个页的描述信息
        p->property = page->property - n; // 更新新的空闲块的大小信息
        list_add(&(page->page_link), &(p->page_link)); // 将新空闲块插入空闲块列表中
    }
    list_del(&(page->page_link)); // 删除空闲链表中的原先的空闲块
    nr_free -= n; // 更新总空闲物理页的数量}

4. default_free_pages函数
   接下来考虑释放占用的内存块的函数default_free_pages，该函数的具体功能为释放指定的某一物理页开始的若干个连续物理页，并且完成first-fit算法中需要的若干信息的维护，具体的实现如下所示：
   4.1. 首先考虑遍历需要释放的物理页的描述信息（即对应的Page结构），对其进行更新；
   ①判断原先这些物理页是否真的被占用了，如果释放未被占用的物理页，这说明出现了异常情况；
   ②设置flags来将这些物理页标记为空闲；
   ③清空这些物理页的引用计数；

struct Page *p = base;
for (; p != (base + n); p ++) {
    assert(!PageReserved(p) && !PageProperty(p)); // 进行检查
    SetPageProperty(p); // 标记为空闲
    set_page_ref(p, 0); // 清空引用计数

接下来将这一新的空闲块插入到空闲块链表中：

base->property = n; // 设置空闲块大小
list_entry_t *le = list_next(&free_list); 
for (; le != (&free_list) && le < (&(base->page_link)); le = list_next(le)); // 寻找新的空闲块在空闲块链表中应当处于的位置
list_add_before(le, &(base->page_link)); // 将空闲块插入到链表中
nr_free += n; // 更新空闲物理页总量

最后需要对空闲块跟其相邻的空闲块（如果存在的话）进行合并，分别是检查能与前一项合并与后一项合并的操作，我的合并方式是循环遍历链表，进行空闲块相邻的判断，相邻则合并；

while (le != &free_list) {	// 迭代空闲链表中的每一个节点
        // 获得节点对应的Page结构
        p = le2page(le, page_link);
        le = list_next(le);
        if (base + base->property == p) {// 如果尾部正好能和下一个连上则合并
            base->property += p->property;
            ClearPageProperty(p);
            list_del(&(p->page_link));
        }
        else if (p + p->property == base) { // 如果头部与上一个连上则合并
            p->property += base->property;
            ClearPageProperty(base);
            base = p;
            list_del(&(p->page_link));
        }
}

5. 回答问题：你的first fit算法是否有进一步的改进空间？
   在本实验中所实现的first fit算法仍然有着相当的改进空间；
   改进方向就在于时间复杂度上，每次查询第一块符合条件的空闲内存块时，最坏情况需要找遍整个链表，这样的话时间复杂度是O（N），N表示当前的链表大小，考虑针对时间效率的优化方式如下：
   如果采用平衡二叉树结构来取代简单的链表结构来维护空闲块，其中按照中序遍历得到的空闲块序列的物理地址恰好按照从小到大排序；每个二叉树节点上维护该节点为根的子树上的最大的空闲块的大小；通过二叉树的查询算法可以查找到物理地址最小的能够满足条件的空闲地址块，然后进行删除以及新的分裂出来的空闲块的插入等操作；
   平衡二叉树每次查询符合条件的第一块物理空闲块的时间复杂度为O(log N)，对比原先的O（N）有很大进步，但是这里实现较为复杂；

（三） 练习2：实现寻找虚拟地址对应的页表项

1. get_pte函数
   本练习的要求为补全pmm.c中的get_pte函数，该函数的主要功能为根据给定的page directory以及线性地址，查询出该linear address对应的page table entry，并且根据输入参数要求判断是否创建不存在的页表；
   实现的过程：
   ①此函数的作用是向上提供一个几乎透明的操作,返回指定 linear address 对应的 page table entry.注意这个函数是单纯的获取其地址，得到 page dir 的 index是 PDX(la),于是对应的 pde 是 pgdir[PDX(la)]；
   ②考察 pde 具体的结构，高 20 位是 page table 地址.因此pgdir[PSX(la)]& ~0xFFF即可得到 page table 的物理地址，在取值之前,首先要判断存在位PTE_P， 如果存在,说明之前已经初始化过了 pd,只需计算la对应的页表项即可，如果不存在,说明当前页目录项除了 PTE_P 外都是空的。此时需要新申请一块物理内存,作为新的二级页表，但如果 create=0 的话就直接返回 NULL 就行了。

pde_t *pdep = pgdir + PDX(la); // 获取到页目录表中给定线性地址对应到的页目录项
pte_t *ptep = ((pte_t *) (KADDR(*pdep & ~0XFFF)) + PTX(la)); // 从找到的页目录项中查询到对应到的页表中的页表项，即页表基址加上线性地址的中的offset
if (*pdep & PTE_P) return ptep; // 检查查找到的页目录项是否存在，如果存在直接放回								找到的页表项即可
if (!create) return NULL; // 如果该页目录项是不存在的，并且参数要求不创建新的页表，							则直接返回
struct Page* pt = alloc_page(); // 如果需要按需创建新的页表，则请求一个物理页来存储								新创建的页表
if (pt == NULL) return NULL; // 如果物理空间不足，直接返回set_page_ref(pt, 1); // 更新								该物理页的引用计数
ptep = KADDR(page2pa(pt)); // 获取到该物理页的虚拟地址
memset(ptep, 0, PGSIZE); // 新创建的页表进行初始化
*pdep = (page2pa(pt) & ~0XFFF) | PTE_U | PTE_W | PTE_P; // 对原先的页目录项进行设							置，包括设置其对应的页表的物理地址，以及标志位
return ptep + PTX(la); // 返回线性地址对应的页目录项

2. 回答以下问题：
   2.1. 请描述页目录项（Pag Director Entry）和页表（Page Table Entry）中每个组成部分的含义和以及对ucore而言的潜在用处。
   
   
   2.1.1. PDE（页目录项）的具体组成如图所示；描述每一个组成部分的含义如下：
   前20位表示4K对齐的该PDE对应的页表起始位置（物理地址，该物理地址的高20位即PDE中的高20位，低12位为0）；
   第9-11位未被CPU使用，可保留给OS使用；
   接下来的第8位可忽略；
   第7位用于设置Page大小，0表示4KB；
   第6位恒为0；
   第5位用于表示该页是否被使用过；
   第4位设置为1则表示不对该页进行缓存；
   第3位设置是否使用write through缓存写策略；
   第2位表示该页的访问需要的特权级；
   第1位表示是否允许读写；
   第0位为该PDE的存在位；
   2.1.2. 接下来描述页表项（PTE）中的每个组成部分的含义，具体组成如图所示：
   高20位与PDE相似的，用于表示该PTE指向的物理页的物理地址；
   9-11位保留给OS使用；
   7-8位恒为0；
   第6位表示该页是否为dirty，即是否需要在swap out的时候写回外存；
   第5位表示是否被访问；
   3-4位恒为0；
   0-2位分别表示存在位、是否允许读写、访问该页需要的特权级；
   2.1.3. 潜在用处：
   可以发现无论是PTE还是TDE，都具有着一些保留的位供操作系统使用，也就是说ucore可以利用这些位来完成一些其他的内存管理相关的算法；比如可以在这些位里保存最近一段时间内该页的被访问的次数，用于辅助近似地实现虚拟内存管理中的换出策略的LRU之类的算法；也就是说这些保留位有利于OS进行功能的拓展；

2.2. 如果ucore执行过程中访问内存，出现了页访问异常，请问硬件要做哪些事情？

当ucore执行过程中出现了页访问异常，硬件需要完成的事情分别如下：
- 将发生错误的线性地址保存在cr2寄存器中;
- 在中断栈中依次压入EFLAGS，CS, EIP，以及页访问异常码error code，如果page fault是发生在用户态，则还需要先压入ss和esp，并且切换到内核栈；
- 根据中断描述符表查询到对应page fault的ISR，跳转到对应的ISR处执行，接下 来将由软件进行page fault处理；

对于大多数操作系统来说，处理页故障的方法入下：

（四） 练习3：释放某虚地址所在的页并取消对应二级页表项的映射

当释放一个包含某虚地址的物理内存页时，需要让对应此物理内存页的管理数据结构Page做相关的清除处理，使得此物理内存页成为空闲；另外还需把表示虚地址与物理地址对应关系的二级页表项清除。

1. page_remove_pte函数
   接下来具体代码实现来说明释放某虚地址所在的页并且取消PTE表项的映射的具体实现；
   ①检查页表项pte的PTE_P的值，若为0，则说明物理页不存在，此时直接返回
   ②首先将页表项的低12位清零得到物理页的起始地址，并据此得到对应的Page结构，将Page的ref字段减1，表明取消当前逻辑地址到此物理地址的映射。
   ③然后，判断Page的ref的值是否为0，若为0，则说明此时没有任何逻辑地址被映射到此物理地址，当前物理页已没有程序使用，因此调用free_page函数回收此物理页；若不为0，则说明此时仍有至少一个逻辑地址被映射到此物理地址，因此不需回收此物理页。
   ④将对应的页表项pte清零，表明此逻辑地址无对应的物理地址。
   ⑤调用tlb_invalidate函数去使能TLB中当前逻辑地址对应的条目。

assert(*ptep & PTE_P);			 // 确保传入的二级页表项是存在的
struct Page *page = pte2page(*ptep); // 获取该页表项对应的物理页对应的Page结构
page->ref --; 					// 减少该物理页的引用计数
if (!page->ref) free_page(page); 	// 如果该物理页的引用计数变成0，即不存在任何虚拟页指								向该物理页，释放该物理页
*ptep &= (~PTE_P);				 // 将PTE的存在位设置为0，表示该映射关系无效
tlb_invalidate(pgdir, la); 			// 刷新TLB，保证TLB中的缓存不会有错误的映射关系

2. 回答如下问题：
   2.1. 数据结构Page的全局变量（其实是一个数组）的每一项与页表中的页目录项和页表项有无对应关系？如果有，其对应关系是啥？
   存在对应关系；
   由于页表项中存放着对应的物理页的物理地址，因此可以通过这个物理地址来获取到对应到的Page数组的对应项，具体做法为将物理地址除以一个页的大小，然后乘上一个Page结构的大小获得偏移量，使用偏移量加上Page数组的基地址皆可以或得到对应Page项的地址；
   
   可通过该函数从页表项中得到物理page结构；

   2.2. 如果希望虚拟地址与物理地址相等，则需要如何修改lab2，完成此事？ 鼓励通过编程来具体完成这个问题。
   由于在完全启动了ucore之后，虚拟地址和线性地址相等，都等于物理地址加上0xc0000000，如果需要虚拟地址和物理地址相等，可以考虑更新gdt，更新段映射，使得virtual address = linear address - 0xc0000000，这样的话就可以实现virtual address = physical address；
   通过ld工具生成的ucore的其实虚拟地址为0xC01000000开始，而bootloader把ucore放在了起始地址为0x001000000的物理内存空间，那么首先将KERNBASE从0xC000000改为0x00000000，原因在于没有开启页地址转换前，内核逻辑地址经过一次段地址转换直接得到物理地址。

#define KERNBASE 0xC0000000
phy addr + KERNBASE = virtual addr
所以，KERNBASE = 0时，phy addr = virtual addr。

（五） 扩展练习1：在ucore中实现buddy system（未能完全完成）

Buddy System算法把系统中的可用存储空间划分为存储块(Block)来进行管理, 每个存储块的大小必须是2的n次幂(Pow(2, n)), 即1, 2, 4, 8, 16, 32, 64, 128…
参考伙伴分配器的一个极简实现， 在ucore中实现buddy system分配算法；具体的代码见附录！
5.1. 整体思想
分配器的整体思想是，通过一个数组形式的完全二叉树来监控管理内存，二叉树的节点用于标记相应内存块的使用状态，高层节点对应大的块，低层节点对应小的块，在分配和释放中我们就通过这些节点的标记属性来进行块的分离合并。如图所示，假设总大小为16单位的内存，我们就建立一个深度为5的满二叉树，根节点从数组下标[0]开始，监控大小16的块；它的左右孩子节点下标[1_{2]，监控大小8的块；第三层节点下标[3}6]监控大小4的块……依此类推。

5.2. 数据结构

这里的成员size表明管理内存的总单元数目（测试用例中是32），成员longest就是二叉树的节点标记，表明所对应的内存块的空闲单位。

5.3. 分配内存alloc
①寻找大小合适的内存块（大于等于并且最接近2的幂，比如需要27，实际分配32）
②如果找到了，分配给应用程序。
③如果没找到，分出合适的内存块。

Ⅰ对半分离出高于所需大小的空闲内存块
Ⅱ如果分到最低限度，分配这个大小。
Ⅲ回溯到步骤①（寻找合适大小的块）
Ⅳ重复该步骤直到一个合适的块

整个分配器的大小就是满二叉树节点数目，即所需管理内存单元数目的2倍。一个节点对应4个字节，longest记录了节点所对应的的内存块大小。
内存分配的alloc中，入参是分配器指针和需要分配的大小，返回值是内存块索引。alloc函数首先将size调整到2的幂大小，并检查是否超过最大限度。然后进行适配搜索，深度优先遍历，当找到对应节点后，将其longest标记为0，即分离适配的块出来，并转换为内存块索引offset返回，依据二叉树排列序号，比如内存总体大小32，我们找到节点下标[8]，内存块对应大小是4，则offset = (8+1)*4-32 = 4，那么分配内存块就从索引4开始往后4个单位。
在函数返回之前需要回溯，因为小块内存被占用，大块就不能分配了，比如下标[8]标记为0分离出来，那么其父节点下标[0]、[1]、[3]也需要相应大小的分离。将它们的longest进行折扣计算，取左右子树较大值，下标[3]取4，下标[1]取8，下标[0]取16，表明其对应的最大空闲值。

5.4. 释放内存free

上图中，首先我们假设我们一个内存块有1024K，当我们需要给A分配70K内存的时候，
①我们发现1024K的一半大于70K，然后我们就把1024K的内存分成两半，一半512K。
②然后我们发现512K的一半仍然大于70K，于是我们再把512K的内存再分成两半，一半是128K。
③此时，我们发现128K的一半小于70K，于是我们就分配为A分配128K的内存。
④后面的，B，C，D都这样，而释放内存时，则会把相邻的块一步一步地合并起来（合并也必需按分裂的逆操作进行合并）。
我们可以看见，这样的算法，用二叉树这个数据结构来实现再合适不过了。
在内存释放的free接口，我们只要传入之前分配的内存地址索引，并确保它是有效值。之后就跟alloc做反向回溯，从最后的节点开始一直往上找到longest为0的节点，即当初分配块所适配的大小和位置。
将longest恢复到原来满状态的值。继续向上回溯，检查是否存在合并的块，依据就是左右子树longest的值相加是否等于原空闲块满状态的大小，如果能够合并，就将父节点longest标记为相加的和。

5.5. 在ucore中测试
首先，我们分析ucore的执行过程；
从练习1中可知，内存的分配函数是在default_pmm.c中实现的，default_pmm.c中各个函数的定义：

该实现manager是在pmm.c中调用的：

所以实现buddy system时，要完成buddy.c和buddy.h；
buddy.h中的内容参考了default_pmm.h实现：

并且将pmm.c中的调用改为：

即调用buddy.h中的buddy_pmm_manager；
而buddy_pmm_manager是在buddy,c中实现的：

最后通过make qemu来测试结果：

测试正确；

（六） 测试

最终完成所有练习之后，可以通过make grade的所有测试，最终实验结果如下所示：
make grade：

make qemu：

可以看出上述补充代码部分正确。

五、 总结

本实验是关于物理内存管理，主要从物理内存和建立页表两个方面设计实验，首先了解了如何发现物理内存，如何建立物理内存的初步管理等等内容；了解页表的相关操作总体来说有些难，因为涉及到了很多的新数据结构，我们需要很好的理解掌握各个文件中的相关函数，才能理解实验的内涵。
通过练习1、2、3，了解了基于段页式内存地址的转换机制，页表的建立和使用方法和物理内存的管理方法。比如在练习1中直观地看到first fit算法的实现过程，尽管在理论课上学过，而且感觉理论上比较简单，但实际实现起来还是有点难度的。总体上来说，三个练习的工作量不小，而且也并不是很简单就能完成的，不过好在注释十分详细，跟着注释一步一步走，然后查阅一些相关的资料后还是能够完成的。
通过这个实验能够深入的理解段页式内存管理机制，对课本中的知识点有了深入的理解体会。总的来说，lab2的收获还是很大，而且正如实验指导书最开始说的，lab1和lab2比较困难，但通过lab1和lab2后，对计算机原理中的中断、段页表机制、特权级等的理解会更深入。对后面的学习有很大的帮助。

六、 附录

主要是buddy.c中的代码：
#include <pmm.h>
#include <list.h>
#include <string.h>
#include <default_pmm.h>
#include <buddy.h>
//来自参考资料的一些宏定义
#define LEFT_LEAF(index) ((index) * 2 + 1)
#define RIGHT_LEAF(index) ((index) * 2 + 2)
#define PARENT(index) ( ((index) + 1) / 2 - 1)

#define IS_POWER_OF_2(x) (!((x)&((x)-1)))
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define UINT32_SHR_OR(a,n) ((a)|((a)>>(n)))//右移n位

#define UINT32_MASK(a) (UINT32_SHR_OR(UINT32_SHR_OR(UINT32_SHR_OR(UINT32_SHR_OR(UINT32_SHR_OR(a,1),2),4),8),16))
//大于a的一个最小的2^k
#define UINT32_REMAINDER(a) ((a)&(UINT32_MASK(a)>>1))
#define UINT32_ROUND_DOWN(a) (UINT32_REMAINDER(a)?((a)-UINT32_REMAINDER(a)):(a))//小于a的最大的2^k

static unsigned fixsize(unsigned size) {
size |= size >> 1;
size |= size >> 2;
size |= size >> 4;
size |= size >> 8;
size |= size >> 16;
return size+1;
}

struct buddy2 {
unsigned size;//表明管理内存
unsigned longest;
};
struct buddy2 root[80000];//存放二叉树的数组，用于内存分配

free_area_t free_area;

#define free_list (free_area.free_list)
#define nr_free (free_area.nr_free)

struct allocRecord//记录分配块的信息
{
struct Page* base;
int offset;
size_t nr;//块大小
};

struct allocRecord rec[80000];//存放偏移量的数组
int nr_block;//已分配的块数

static void buddy_init()
{
list_init(&free_list);
nr_free=0;
}

//初始化二叉树上的节点
void buddy2_new( int size ) {
unsigned node_size;
int i;
nr_block=0;
if (size < 1 || !IS_POWER_OF_2(size))
return;

root[0].size = size;
node_size = size * 2;

for (i = 0; i < 2 * size - 1; ++i) {
if (IS_POWER_OF_2(i+1))
node_size /= 2;
root[i].longest = node_size;
}
return;
}

//初始化内存映射关系
static void
buddy_init_memmap(struct Page base, size_t n)
{
assert(n>0);
struct Page p=base;
for(;p!=base + n;p++)
{
assert(PageReserved§);
p->flags = 0;
p->property = 1;
set_page_ref(p, 0);
SetPageProperty§;
list_add_before(&free_list,&(p->page_link));
}
nr_free += n;
int allocpages=UINT32_ROUND_DOWN(n);
buddy2_new(allocpages);
}
//内存分配
int buddy2_alloc(struct buddy2* self, int size) {
unsigned index = 0;//节点的标号
unsigned node_size;
unsigned offset = 0;

if (self==NULL)//无法分配
return -1;

if (size <= 0)//分配不合理
size = 1;
else if (!IS_POWER_OF_2(size))//不为2的幂时，取比size更大的2的n次幂
size = fixsize(size);

if (self[index].longest < size)//可分配内存不足
return -1;

for(node_size = self->size; node_size != size; node_size /= 2 ) {
if (self[LEFT_LEAF(index)].longest >= size)
{
if(self[RIGHT_LEAF(index)].longest>=size)
{
index=self[LEFT_LEAF(index)].longest <= self[RIGHT_LEAF(index)].longest? LEFT_LEAF(index):RIGHT_LEAF(index);
//找到两个相符合的节点中内存较小的结点
}
else
{
index=LEFT_LEAF(index);
}
}
else
index = RIGHT_LEAF(index);
}

self[index].longest = 0;//标记节点为已使用
offset = (index + 1) * node_size - self->size;
while (index) {
index = PARENT(index);
self[index].longest =
MAX(self[LEFT_LEAF(index)].longest, self[RIGHT_LEAF(index)].longest);
}
//向上刷新，修改先祖结点的数值
return offset;
}

static struct Page*
buddy_alloc_pages(size_t n){
assert(n>0);
if(n>nr_free)
return NULL;
struct Page* page=NULL;
struct Page* p;
list_entry_t *le=&free_list,*len;
rec[nr_block].offset=buddy2_alloc(root,n);//记录偏移量
int i;
for(i=0;i<rec[nr_block].offset+1;i++)
le=list_next(le);
page=le2page(le,page_link);
int allocpages;
if(!IS_POWER_OF_2(n))
allocpages=fixsize(n);
else
{
allocpages=n;
}
//根据需求n得到块大小
rec[nr_block].base=page;//记录分配块首页
rec[nr_block].nr=allocpages;//记录分配的页数
nr_block++;
for(i=0;i<allocpages;i++)
{
len=list_next(le);
p=le2page(le,page_link);
ClearPageProperty§;
le=len;
}//修改每一页的状态
nr_free-=allocpages;//减去已被分配的页数
page->property=n;
return page;
}

void buddy_free_pages(struct Page* base, size_t n) {
unsigned node_size, index = 0;
unsigned left_longest, right_longest;
struct buddy2* self=root;

list_entry_t le=list_next(&free_list);
int i=0;
for(i=0;i<nr_block;i++)//找到块
{
if(rec[i].base==base)
break;
}
int offset=rec[i].offset;
int pos=i;//暂存i
i=0;
while(i<offset)
{
le=list_next(le);
i++;
}
int allocpages;
if(!IS_POWER_OF_2(n))
allocpages=fixsize(n);
else
{
allocpages=n;
}
assert(self && offset >= 0 && offset < self->size);//是否合法
node_size = 1;
index = offset + self->size - 1;
nr_free+=allocpages;//更新空闲页的数量
struct Page p;
self[index].longest = allocpages;
for(i=0;i<allocpages;i++)//回收已分配的页
{
p=le2page(le,page_link);
p->flags=0;
p->property=1;
SetPageProperty§;
le=list_next(le);
}
while (index) {//向上合并，修改先祖节点的记录值
index = PARENT(index);
node_size *= 2;

left_longest = self[LEFT_LEAF(index)].longest;
right_longest = self[RIGHT_LEAF(index)].longest;

if (left_longest + right_longest == node_size) 
  self[index].longest = node_size;
else
  self[index].longest = MAX(left_longest, right_longest);

}
for(i=pos;i<nr_block-1;i++)//清除此次的分配记录
{
rec[i]=rec[i+1];
}
nr_block–;//更新分配块数的值
}

static size_t
buddy_nr_free_pages(void) {
return nr_free;
}

//以下是一个测试函数
static void

buddy_check(void) {
struct Page *p0, *A, *B,*C,*D;
p0 = A = B = C = D =NULL;

assert((p0 = alloc_page()) != NULL);
assert((A = alloc_page()) != NULL);
assert((B = alloc_page()) != NULL);

assert(p0 != A && p0 != B && A != B);
assert(page_ref(p0) == 0 && page_ref(A) == 0 && page_ref(B) == 0);
free_page(p0);
free_page(A);
free_page(B);

A=alloc_pages(500);
B=alloc_pages(500);
cprintf("A %p\n",A);
cprintf("B %p\n",B);
free_pages(A,250);
free_pages(B,500);
free_pages(A+250,250);

p0=alloc_pages(1024);
cprintf("p0 %p\n",p0);
assert(p0 == A);
//以下是根据链接中的样例测试编写的
A=alloc_pages(70);  
B=alloc_pages(35);
assert(A+128==B);//检查是否相邻
cprintf("A %p\n",A);
cprintf("B %p\n",B);
C=alloc_pages(80);
assert(A+256==C);//检查C有没有和A重叠
cprintf("C %p\n",C);
free_pages(A,70);//释放A
cprintf("B %p\n",B);
D=alloc_pages(60);
cprintf("D %p\n",D);
assert(B+64==D);//检查B，D是否相邻
free_pages(B,35);
cprintf("D %p\n",D);
free_pages(D,60);
cprintf("C %p\n",C);
free_pages(C,80);
free_pages(p0,1000);//全部释放

}

const struct pmm_manager buddy_pmm_manager = {
.name = “buddy_pmm_manager”,
.init = buddy_init,
.init_memmap = buddy_init_memmap,
.alloc_pages = buddy_alloc_pages,
.free_pages = buddy_free_pages,
.nr_free_pages = buddy_nr_free_pages,
.check = buddy_check,
};