实验目的
- 了解基于段页内存地址的转换机制
- 了解页表的建立和使用方法
- 理解物理内存管理方法
实验内容
本实验包括三个部分。首先了解如何在系统中找到物理内存；然后了解如何建立物理内存的初步管理，即连续的物理内存管理；最后了解页面相关操作，即如何建立页面，实现虚拟内存与物理内存之间的映射，全面了解页面内存管理机制。本实验实现的内存管理仍然非常基本，不涉及实际机器的优化，如 cache 的优化等。如果你有余力，试着完成扩展练习。
练习
为了实现lab2的目标，lab提供3个基本练习和2个扩展练习，需要完成实验报告。
对实验报告的要求：
- 基于markdown格式完成，以文本为主
- 在基本练习中填写所需的报告内容
- 实验完成后，请进行分析ucore_lab请在实验报告中说明您的实现与参考答案的区别
- 列出你认为本实验中重要的知识点和相应的知识点OS原则中的知识点，并简要说明你对两者的意义、关系、差异等方面的理解（实验中的知识点也可能没有相应的原则知识点）
- 列出你认为OS原理中很重要，但在实验中没有对应上的知识点
文件架构和执行过程
lab文件架构相对lab1.有一些差异。从后面可以看出，有必要存在这些差异，以便操作系统能够正常运行。下面是一个简要的描述lab执行每个文件的过程。
- 首先自然是
bios机器上电时加载的程序0xffff0在地址处，完成相关设备的初始化，读取硬盘主导风扇区域bootloader到0x7c00地址处。 - 之后，机器的控制权交给了它
bootloader，首先是bootasm.S汇编代码开始执行并完成CPU从实际模式到保护模式的转变首先需要能量A20地址线、初始化段表等lab里面完成的工作。lab不同的是，在bootasm.S中，还进行了对物理内存的探测工作，是通过bios系统调用完成。段表的建立和各段寄存器的初始化完成后，建立了C语言的运行环境，程序转移到bootmain.c中期执行。 bootmain.c::bootmain通过分析，函数功能非常单一，即将存在于硬盘风扇区域的操作系统中进行内存核读elf格式文件找到内核的入口地址，然后转入内核开始运行。lab1是一样的，区别在于这里不是直接转入kern/init/init.c相反，转入kern/init/entry.S中运行。- 在
kern/init/entry.S中间更新了之前建立的段机制，使虚拟地址可以va物理地址映射va - 0xC000000，确保操作系统能够正常运行。然后程序进入kern/init/init.c::kern_init中运行。 - 在
kern_init这里主要讨论各种设备的初始化工作pmm_init函数，即物理内存管理的初始化。 - 在
pmm_init中，首先进行了物理内存管理器（physical memory manager）初始化工作，利用之前对物理内存的探测，通过一个接一个地对所有空闲物理内存进行检测free_area链表管理对应page_init函数。 - 之后是页表的建立(对应)
boot_map_segment）函数，段机制再次更新，段页地址映射机制完成。这里的逻辑比较复杂，稍后会详细说明。
按下lab2.详细说明各文件执行的具体操作、相关功能的实现以及实现的原因。
探测物理内存
lab2的实验目的是建立物理内存的管理机制，包括连续的内存分配算法(如first fit）以及非连续的段页管理机制。然而，在实现这些管理机制之前，我们首先需要知道当前机器有多少内存可用，它们的分布是什么，以便组织和管理所有的空闲内存。因此，首先需要检测物理内存。
通过探测物理内存bios实现了中断调用bios中断调用只能在实际模式下进行，因此需要相应的工作boot/bootasm.S在实际模式转换为保护模式之前。具体的探测方法是调用参数e820h的INT 15h的bios中断。bios描述系统内存映射地址（Address Range Descriptor）格式表示系统的物理内存布局。地址描述符分为三个字段，即内存的起始地址、连续内存的大小、内存的状态或类型（可用或保留）。实际上，请查看具体细节INT 15这里不详细说明系统调用的输入和输出。以下是检测物理内存的汇编代码:
probe_memory: movl $0, 0x8000 xorl ?x, ?x movw $0x8004, %di start_probe: movl $0xE820, ?x movl $20, ?x movl $SMAP, ?x int $0x15 jnc cont movw $12345, 0x8000 jmp finish_probe cont: addw $20, %di incl 0x8000 cmpl $0, ?x jnz start_probe finish_probe: 这个代码的功能是使用它bios系统调用INT 15为了实现物理内存的检测，将返回的地址描述符放置在es:di最初的内存，这里是0x8004此外，还可以看到地址0x8000物理内存块的数量也存储在变量中，以保存检测到的物理内存块的数量0x8000在内存地址处，存储与以下结构对应的变量：
struct e820map {
int nr_map; struct {
uint64_t addr; uint64_t size; uint32_t type; } __attribute__((packed)) map[E820MAX]; }; 在kern/mm/pmm.c::page_init在函数中，物理内存的页面管理机制是通过这个结构建立的。此函数将在后面详细描述。
段映射机制首次更新
上面提到在lab2中，boot/bootmain.c::bootmain执行后，不是像lab直接跳转到1kern/init/init.c::kern_init相反，函数执行首先进入kern/init/entry.S，再入init.c::kern_init函数。实际上，这样的操作是必要的，倘若没有经过这样的转换，操作系统内核将不能正常运行。
与lab1中一样，在lab2中操作系统内核也是被加载到物理地址为0x00100000的内存区段。所不同的是，lab2中的操作系统设定了虚拟地址空间，其中内核的起始地址为0xC0100000，这点在tools/kernel.ld文件中有所体现，该链接脚本文件是用于规定链接时的输出文件在程序地址空间的布局的，当然还有其他的功能。可以看到：
...
ENTRY(kern_entry)
SECTIONS {
/* Load the kernel at this address: "." means the current address */
. = 0xC0100000;
.text : {
...
这里规定了内核的入口地址为kern_entry，即entry.S中的主函数，并且规定了操作系统是被加载到起始虚拟地址为0xC0100000的内存区段上。而操作系统被加载到的物理地址，则是由bootloader决定的。在boot/bootmain.c::bootmain中，可以看到：
...
// load each program segment (ignores ph flags)
ph = (struct proghdr *)((uintptr_t)ELFHDR + ELFHDR->e_phoff);
eph = ph + ELFHDR->e_phnum;
for (; ph < eph; ph ++) {
readseg(ph->p_va & 0xFFFFFF, ph->p_memsz, ph->p_offset);
}
// call the entry point from the ELF header
// note: does not return
((void (*)(void))(ELFHDR->e_entry & 0xFFFFFF))();
...
这里readseg函数的第一个参数，就是bootloader将内核加载到内存中的地址，由于此时建立的段表还是一对一对等映射，所以这里的加载地址就是物理地址。其中，ph->p_va就是在kernel.ld中设定的虚拟地址，所以操作系统内核实际上是被加载到起始物理地址为ph->p_va & 0xFFFFFF = 0x00100000的内存中。
从上面的讨论可以看出，lab2内核的物理地址与虚拟地址是不同的，它们之间的对应关系满足
virt addr - 0xC0000000 = phy addr
因此，如果直接从bootmain函数跳转进入内核的init.c::kern_init函数，由于此时的段机制还是对等映射，内核将不能正确得到要运行的代码与数据，此时显然是不可以运行的。所以在进入内核之前，我们首先需要在kern/entry.S中更新段机制，将虚拟地址映射到正确的与之对应的物理地址，此后才能进入内核。
需要注意的是，由于entry.S也是内核代码的一部分，因此其中涉及的内存地址都是虚拟地址，在访存时需要手动进行虚拟地址向物理地址的转化，才能访问到正确的内存空间，具体的代码如下：
#define REALLOC(x) (x - KERNBASE)
.text
.globl kern_entry
kern_entry:
# reload temperate gdt (second time) to remap all physical memory
# virtual_addr 0~4G=linear_addr&physical_addr -KERNBASE~4G-KERNBASE
lgdt REALLOC(__gdtdesc)
movl $KERNEL_DS, %eax
movw %ax, %ds
movw %ax, %es
movw %ax, %ss
ljmp $KERNEL_CS, $relocated
relocated:
# set ebp, esp
movl $0x0, %ebp
# the kernel stack region is from bootstack -- bootstacktop,
# the kernel stack size is KSTACKSIZE (8KB)defined in memlayout.h
movl $bootstacktop, %esp
# now kernel stack is ready , call the first C function
call kern_init
...
__gdt:
SEG_NULL
SEG_ASM(STA_X | STA_R, - KERNBASE, 0xFFFFFFFF) # code segment
SEG_ASM(STA_W, - KERNBASE, 0xFFFFFFFF) # data segment
__gdtdesc:
.word 0x17 # sizeof(__gdt) - 1
.long REALLOC(__gdt)
实际上，这里的REALLOC(x)宏，就是实现虚拟地址向物理地址转换的工作的。可以看到，在entry.S中，重新更新了段表，使得虚拟地址能被映射到正确的物理地址。此后，就可以毫无禁忌地直接使用虚拟地址了。
练习1：实现 first-fit 连续物理内存分配算法（需要编程）
在实现first fit内存分配算法的回收函数时，要考虑地址连续的空闲块之间的合并操作。提示:在建立空闲页块链表时，需要按照空闲页块起始地址来排序，形成一个有序的链表。可能会修改default_pmm.c中的default_init，default_init_memmap，default_alloc_pages， default_free_pages等相关函数。请仔细查看和理解default_pmm.c中的注释。
请在实验报告中简要说明你的设计实现过程。请回答如下问题：
- 你的
first fit算法是否有进一步的改进空间
空闲物理内存的页式管理
在进行对物理内存的分配与回收之前，肯定首先需要知道当前的空闲物理内存有哪些，从而才可以选择某一区段的内存进行分配啊。也就是说，首先我们是需要管理所有的空闲物理内存。通过之前的物理内存探测，我们已经可以知道哪些区域的物理内存是可用的，接下来，我们要建立页式物理内存管理机制，将物理内存组织成一个个固定大小的页帧来进行管理，并且建立起一个链表结构将这些空闲的内存块组织起来，进而实现内存的分配与回收工作。这部分的工作都是在kern/mm/pmm.c::page_init函数中实现的。
首先，需要将物理内存组织成一个个固定大小的页帧，这里页帧的大小固定为4K。为此，我们就需要知道物理内存的起始点与终止点，从而确定可以划分的页帧的数目，对于每一个物理页，都有一个与之对应的struct Page结构体与之对应，来表示该物理页的状态，如是否可用或者被操作系统保留。这部分的工作对应了page_init函数的前半部分：
/* * * struct Page - Page descriptor structures. Each Page describes one * physical page. In kern/mm/pmm.h, you can find lots of useful functions * that convert Page to other data types, such as phyical address. * */
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
};
static void
page_init(void) {
struct e820map *memmap = (struct e820map *)(0x8000 + KERNBASE);
uint64_t maxpa = 0;
cprintf("e820map:\n");
int i;
for (i = 0; i < memmap->nr_map; i ++) {
uint64_t begin = memmap->map[i].addr, end = begin + memmap->map[i].size;
cprintf(" memory: %08llx, [%08llx, %08llx], type = %d.\n",
memmap->map[i].size, begin, end - 1, memmap->map[i].type);
if (memmap->map[i].type == E820_ARM) {
if (maxpa < end && begin < KMEMSIZE) {
maxpa = end;
}
}
}
if (maxpa > KMEMSIZE) {
maxpa = KMEMSIZE;
}
extern char end[];
npage = maxpa / PGSIZE;
pages = (struct Page *)ROUNDUP((void *)end, PGSIZE);
for (i = 0; i < npage; i ++) {
SetPageReserved(pages + i);
}
uintptr_t freemem = PADDR((uintptr_t)pages + sizeof(struct Page) * npage);
...
}
关于这段代码，有一些要说明的地方：
- 可以看到，函数一开始就是获得前面
bios中断调用得到的地址描述符结构体，这里主要是利用它的信息来获得最大的物理地址maxpa，从而可以确定页面的数量。这里的KMEMSIZE宏是代表了当前机器的最大内存量。 - 程序的后半部分，就建立起了结构数组
Struct Page* pages，对于每一个物理页面，pages数组都有一项的Struct Page与之对应，并且首先将所有的页面都初始化为[保留的]，对应于SetPageReserved(pages + i);。 - 这里的全局变量
char end[]并非是在代码文件里面定义的，而是在kernel.ld中
...
/* The data segment */
.data : {
*(.data)
}
PROVIDE(edata = .);
.bss : {
*(.bss)
}
PROVIDE(end = .);
...
可见，这里的end变量是代表bss段的结束地址，也就是操作系统内核被加载到内存中的结束地址。通过设置pages = (struct Page *)ROUNDUP((void *)end, PGSIZE);，表示pages数组是被存放在内存中紧跟在操作系统内核后面，被圆整到一个页帧大小的整数倍的区域中，而后面的freemem变量则是表示存放完pages数组之后，内存中空闲的区域。这样，我们可以物理内存的结构分布图：
/* *
* Physical memory map:
*
* +---------------------------------+
* | |
* | Free Memory (*) |
* | |
* freemem -------------> +---------------------------------+
* | Struct Page *pages |
* pages ---------------> +---------------------------------+
* | Invalid Memory (*) |
* end kern ------------> +---------------------------------+
* | |
* | KERNEL |
* | |
* load addr -----------> +---------------------------------+ 0x00100000
* | |
* | |
* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~0x000000000
*
* */
在对物理内存进行分页之后，我们需要再次利用e820map的信息，找到所有空闲的页面，并将这些页面组织到一起集中进行管理，这也就是page_init后半部分进行的工作：
...
for (i = 0; i < memmap->nr_map; i ++) {
uint64_t begin = memmap->map[i].addr, end = begin + memmap->map[i].size;
cprintf("[begin, end]: [%08llx, %08llx]\n", begin, end);
if (memmap->map[i].type == E820_ARM) {
if (begin < freemem) {
begin = freemem;
}
if (end > KMEMSIZE) {
end = KMEMSIZE;
}
if (begin < end) {
begin = ROUNDUP(begin, PGSIZE);
end = ROUNDDOWN(end, PGSIZE);
if (begin < end) {
init_memmap(pa2page(begin), (end - begin) / PGSIZE);
}
}
}
}
可以看到，这里的核心函数是init_memmap，它的作用是将起始地址为begin的若干个连续的页面，保存到kern/mm/default_pmm.c中定义的free_area变量中，表示该连续页面是空闲的，可用于后续的分配操作。这个free_area变量其实非常神奇，它是类似于一种链式数组，就是说它只保存各个连续的空闲页的起始页，通过pages数组就可以轻易地访问到该起始页后面连续的空闲页面，不连续的区段的起始页之间通过一个链表来互相连接。可见，free_area的组织方式与采用的页面分配算法息息相关，比如说，倘若采用best fit算法，就应该按空闲区段从小到大的顺序来组织起始页链表，worst fit算法则恰好相反，而倘若采用first fit分配算法，就应该按照起始页的地址顺序，由小到大组织。pmm_manager中的init_memmap, alloc_pages, free_pages实现的关键，都在于维护这种有序关系。
对于我们要实现的first fit算法而言，在调用init_memmap将新的空闲页加入到free_area当中时，就需要遍历当前的起始页链表，从而找到一个合适的位置插入新的空闲页，其实现如下：
/* search for a proper positon in free_list to place new memory block*/
static void
insert2free_list(list_entry_t *elem){
list_entry_t *le = &free_list;
while((le = list_next(le)) != &free_list){
if(elem < le){
list_add_before(le, elem);
break;
}
}
if(le == &free_list) list_add_before(le, elem);
}
static void
default_init_memmap(struct Page *base, size_t n) {
assert(n > 0);
struct Page *p = base;
for (; p != base + n; p ++) {
assert(PageReserved(p));
p->flags = p->property = 0;
set_page_ref(p, 0);
}
base->property = n;
SetPageProperty(base);
nr_free += n;
cprintf("current number of free pages: %d\n", nr_free);
insert2free_list(&(base->page_link));
}
这里，我首先写了一个insert2free_list函数，来找到first fit算法中合适的插入位置，并且将新的空闲页插入其中。在default_init_memmap中，首先进行一些权限的设置，比如将当前页面设置为[可用的]，而非继续被操作系统[保留的]等，然后就调用insert2free_list将新的页面插入到合适的位置。对于参考答案给出的这个代码，是直接将新的页面插入到页表的末端，可能是老师清楚INT 15的中断调用返回的e820map地址顺序是有序的，但是我并不清楚这个事实，所以我觉得我的实现也许还更严谨？
first fit算法的实现
在建立好free_area来管理所有的空闲内存区块后，就可以着手实现first fit连续物理内存分配算法了。主要的工作其实就是实现两个函数，页面分配算法(alloc_pages)以及页面回收算法(free_pages)。
对于页面分配算法，应该按照空闲内存区块的起始地址从小到大的顺序，遍历这些内存区块，直到发现一个区块大于要分配的内存空间，则将这个区块切割，将要求的内存空间分配出去后，把剩下的空闲内存继续保存到free_area中，这其中涉及到一些标志位以及相关状态变量的修改。具体的代码如下：
static struct Page *
default_alloc_pages(size_t n) {
assert(n > 0);
if (n > nr_free) {
return NULL;
}
struct Page *page = NULL, *p;
list_entry_t *le = &free_list;
while ((le = list_next(le)) != &free_list){
p = le2page(le, page_link);
if (p->property >= n) {
page = p;
break;
}
}
if (page != NULL) {
list_del(&(page->page_link));
if (page->property > n) {
p = page + n;
p->property = page->property - n;
insert2free_list(&(p->page_link));
}
nr_free -= n;
ClearPageProperty(page);
}
return page;
}
我这里的这个实现其实是还可以改进的。可以看到，我在将剩下的空闲内存再次加入到free_area中时，调用了前面提到的insert2free_list函数，这个函数会遍历所有的空闲区块，直到发现插入的合适位置，其最坏情况与平均情况的时间复杂度都是O(n)。实际上，直接将该剩下的空闲区块插入到page后面不就可以了吗？为此只需要首先添加该剩余的空闲区块，之后再删除掉free_area中的page->page_link就可以了，实际复杂度仅为O(1)。实际上，老师给出的参考答案就是这样实现的。
对于页面回收算法，则要相对复杂。因为不仅需要将被回收的页面插入到free_area中的合适位置，还需要考虑该新加入的页面是否可以和其前后相邻的页面进行合并，从而组织成一个更大的空闲区块。我的回收算法就是这样实现的，先找到合适的位置插入新的页面，再分别检测是否可以与前后相邻的页面合并。具体的代码如下：
static void
default_free_pages(struct Page *base, size_t n) {
assert(n > 0);
struct Page *p = base, *front;
for (; p != base + n; p ++) {
assert(!PageReserved(p) && !PageProperty(p));
p->flags = 0;
set_page_ref(p, 0);
}
base->property = n;
SetPageProperty(base);
list_entry_t *le = &free_list;
while ((le = list_next(le)) != &free_list) {
p = le2page(le, page_link);
if(base < p){
list_add_before(&(p->page_link), &(base->page_link));
if(base + base->property == p){
base->property += p->property;
ClearPageProperty(p);
list_del(&(p->page_link));
}
if(list_prev(&(base->page_link)) != &free_list){
front = le2page(list_prev(&(base->page_link)), page_link);
if(front + front->property == base){
front->property += base->property;
ClearPageProperty(base);
list_del(&(base->page_link));
}
}
break;
}
}
if(le == &free_list){
list_add_before(&free_list, &(base->page_link));
if(list_prev(&(base->page_link)) != &free_list){
front = le2page(list_prev(&(base->page_link)), page_link);
if(front + front->property == base){
front->property += base->property;
ClearPageProperty(base);
list_del(&(base->page_link));
}
}
}
nr_free += n;
}
在主循环里面，我是试图查找新加入的页面的后继页面，将新的页面插入到其后继页面之前，再进行合并的检测。但如果新加入页面是被插入到free_area链表的最后，则没有这样的后继页面，同时也只有可能与它的前驱进行合并了，while循环之后就是对于这种特殊情况的处理。相对于参考答案的代码，我的版本应该是更好的，因为参考答案用了两次循环，存在大量的冗余操作，当然老师的注释也写了应该对这个代码进行优化。但是不管怎么样，我的这个代码还是存在太多冗余了，存在改进的余地（但是我懒得改了），以下简单说明以下：首先定位待插入页面的前驱front，如果le2page(front) != free_list && front + front->property == base，则更新front的信息，并且令base = front；否则插入base页面。无论哪种情况，以下再以base为基，判断后面的页面是否也可以合并。这样写性能不会更快，但是代码会简练不少。
页表的建立
我们知道，页表的本质其实就是虚拟页与物理页帧之间的地址映射关系。因此，页表的建立其实就是将两者联系起来，填写相应的页表项，从而使得操作系统通过页表可以完成从线性地址到物理地址的转化工作。
为了建立两级页表，我们首先要为页目录表分配一个页的存储空间：
// create boot_pgdir, an initial page directory(Page Directory Table, PDT)
boot_pgdir = boot_alloc_page();
对于每一个线性地址，通过其高十位来索引页目录表，可以得到唯一的页目录表项，从而得到其对应的页表的起始地址；通过其中间十位索引页表，可以得到唯一的页表项，并且进而得到该页表项所对应的物理页帧。可以看出，建立页表的关键，就是要将物理页帧的地址，填入某个线性地址所对应的页表项中，并且设置相应的权限标志位。为此，我们需要首先找到任何一个线性地址所对应的页表项，这个工作被抽象为下面的get_pte函数。
练习2：实现寻找虚拟地址对应的页表项（需要编程）
通过设置页表和对应的页表项，可建立虚拟内存地址和物理内存地址的对应关系。其中的get_pte函数是设置页表项环节中的一个重要步骤。此函数找到一个虚地址对应的二级页表项的内核虚地址，如果此二级页表项不存在，则分配一个包含此项的二级页表。本练习需要补全get_pte函数inkern/mm/pmm.c，实现其功能。请仔细查看和理解get_pte函数中的注释。get_pte函数的调用关系图如下所示：
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Wp7uCOnO-1574171371584)(images/get_pte.png)]
请在实验报告中简要说明你的设计实现过程。请回答如下问题：
- 请描述页目录项（
Page Director Entry）和页表项（Page Table Entry）中每个组成部分的含义和以及对ucore而言的潜在用处。 - 如果ucore执行过程中访问内存，出现了页访问异常，请问硬件要做哪些事情？
页目录项与页表项的结构
由于一页的大小是4K，因此虚拟地址的页偏移量为12位，其余的20位就是逻辑页号。这里的20位逻辑页号又划分为页目录表的索引和页表的索引，分别是10位。这样可以保证一个页目录表或者页表中恰好有2^10 = 1024个表项，每个表项占四个字节，一个页目录表或者页表也就是4K大小，恰好可以容纳在一页之中。
页目录表与页表的功能是一致的，都是给出某个物理地址。页目录表是给出相应的页表的物理地址，页表则是给出某个物理页帧的起始物理地址。由于一个页表的大小也恰好是一个物理页帧的大小，因此这两个地址都是相对于4K对齐的，只需要20位就可以描述。这样，页表项或者页目录表项的其余12位就可以用来表示一些控制信息，比如访问的权限是否可读或是可执行，以及该页表项是否存在。实际上，页目录项与页表项的结构如下所示：
----------------------------------
| 20bits | ... | | | |
----------------------------------
phy page number U W P (PTE_U PTE_W PTE_P)
这里的三个标志位PTE_U, PTE_W, PTE_P分别代表用户态是否可读，该物理内存也是否可写，以及该页表项是否存在。此外还有一些其他标识符，在lab2中没有出现，所以就不一一说明了。这里需要注意一下PTE_P标识位，若该标志位置一，则说明当前的表项是存在的，这意味着当前表项的各个字段都是有意义的，其前20位确实对应了某个物理页帧。这就是说，对应的物理页帧已经建立了与某个线性地址之间的映射关系；而该表项不存在则说明了索引到该表项的线性地址还没有对应到任何的物理页帧，可能等待后续的操作添加这种对应关系，特殊地，如果该表项还是一个页目录表项的话，就意味着该页目录表项还没有对应任何的页表，后续需要分配一页的存储空间来保存新建立的页表。
get_pte函数的实现
get_pte的功能是找到与一个线性地址相对应的页表项，因此get_pte的流程应该是模拟操作系统查询页目录表与页表的过程，即首先用线性地址的高10位索引页目录表，再用