操作系统实验二：存储管理（分析XV6分页存储地址变换）

一、实验目的

二、具体任务安排

1.理解XV6内核源码

2.修改XV6内核源码

一、实验目的

分析XV6教学系统分页存储地址变换的实现

二、具体任务安排

1.理解XV6内核源码

（1）阅读学习通资料中的XV6 guide book第一、第二章或自行查阅相关资料，了解XV6系统初始化阶段内存的分配以及分页式内存管理的实现。

①英特尔分页体系结构

分页是比分段粒度更细的内存空间划分机制，开启分页机制后，处理器必须通过页管理机制才能将线性地址转换成物理地址。分页机制会将线性地址空间和物理地址空间都划分成固定大小的页面（通常是4KB），并通过MMU维护一套页转换表结构，完成线性地址空间页面到物理地址页面的映射和转换。

1)4KB页面的线性地址转换

在使用4KB页面的情况下，32-bit分页模式使用两级页表：页目录表PDT（Page Directory Table）和页表PT（Page Table）。

2)4MB页面的线性地址转换

4MB页面映射相对于4KB页面，本质上是减少了一级页表的转换，线性地址的高10位用于索引页目录表项，此时的页目录表项指向4MB的物理页面；线性地址剩余位作为4MB页面内的偏移。

②英特尔分页体系结构在xv6中的应用

页表是操作系统控制内存含义的机制。它允许xv6把一块物理内存映射到不同进程的地址空间，并保护进程各自的内存。页表提供的对物理内存的间接访问催生了很多技巧。xv6 主要使用页表来创建多个地址空间并保护内存。它也使用了几个简单的页表技巧：把一块内存（内核）映射到不同地址空间，在一个地址空间中映射同一块内存多次（每个用户页也映射到内核管理的物理内存），使用一个未映射的页给用户栈设定边界。

1)页表硬件

x86指令（包括用户与内核）操作虚拟地址。机器的RAM，或者叫物理内存，通过物理地址索引。x86页表硬件把这两种地址联系起来，把一个虚拟地址映射到一个物理地址。

x86页表逻辑上来说是一个2^20(1048576)个页表入口(page table entries,PTEs)的数组。每个PTE包含一个20位的物理页号码(physical page number,PPN)和一些标志位。页表硬件使用虚拟地址的高20位作为索引在页表中寻找一个PTE，然后把虚拟地址的高20位替换为PTE中的PPN。页表硬件把虚拟地址的低12位原封不动的拷贝到翻译后到物理地址。因此页表让操作系统以4096(2^12)字节对齐的块的粒度来控制虚拟地址到物理地址的翻译。这一个块就是一个页。

如图3所示，实际的翻译分为2步。页表以2级的树形结构保存在物理内存上。树根是一个4096字节的页目录(page directory)，包含1024个关联到页表页(page table pages)的类似PTE的入口。每个页表页是一个包含1024个32位PTE的数组。页表硬件使用虚拟地址的高10位选择一个页目录入口。如果页目录入口存在，页表硬件使用虚拟地址接下来的10位从页目录入口代表的页表页里选择一个PTE。如果页目录入口或者PTE不存在，页表硬件产生一个错误。通常情况下大量的虚拟地址是没有进行映射的，这个两级结构允许页表删除整个页表页。

XV6总共拥有128MB的内存，内存地址从0x80000000开始，到0x88000000结束。内核程序本身占用一部分内存，而剩余部分则由内核以按需的方式管理。实际被管理的内存空间由多个4KB的页面组成。

每个PTE都包含标志位来告诉页表硬件相关的虚拟地址允许被怎样使用。PTE_P指出PTE是否存在：如果它没有设置，那么对这个页的引用会引起错误（也就是不被允许）。PTE_W控制指令是否能写入本页；如果没有设置，那么只能读取数据或者取指令。PTE_U控制用户程序能否使用这个页；如果此位清除，则只有内核可用使用这个页。图3展示了所有标志位的用法。标志位和所有其他页表硬件相关的数据结构定义在mmu.h(0700)。

2)进程地址空间

Entry创建的页表映射了足够的空间好让内核的C代码得以运行。然而，main通过调用kvmalloc(1840)直接切换到一个新的页表，因为内核有一个更精细的计划来描述进程地址空间。

每个进程有自己单独的页表，每当xv6切换进程时它会告诉页表硬件同时切换页表。如图4所示，每个进程的虚拟内存从0开始最大可到KERBASE，让进程可以使用高达2GB内存。memlayout.h声明了xv6的内存布局，以及把虚拟地址转为物理地址的宏。

当一个进程向xv6 请求更多的内存，xv6 首先寻找空闲的物理内存页来提供存储，然后在进程的页表中增加PTE指向新的物理内存页。Xv6 设置这些PTE的PTE_U、PTE_W、PTE_P标志位。大多数进程不会使用整个用户地址空间；xv6 把未使用的PTE的PTE_P位清除。不同进程的页表把用户地址翻译到不同的物理内存页，所以每个进程的内存都是私有的。

每个进程的页表中都包含了内核运行所需的映射；这些映射都在KERBASE之上。它把虚拟地址KERBASE:KERBASE+PHYSTOP映射到0:PHYSTOP。这样做的一个原因是让内核可以使用自己的指令和数据。另一个原因是内核有时需要写入一个给定的物理内存页，比如当创建页表页时；每个物理内存页都出现在虚拟地址空间让这件事变得简单。这样安排的坏处是xv6不能使用2GB以上的物理内存。有些设备把I/O映射到0xFE00000开始的物理内存，所以xv6包含一个对它们的直接映射。Xv6 没有设置KERBASE以上的PTE的PTE_U位，所以只有内核能使用它们。

在执行系统调用或中断时，当从用户代码切换到内核代码时，让每个进程页表都包含用户内存和整个内核映射是很方便的：这样的切换不会要求切换页表。大多数时候，内核没有自己的页表；它基本上都是在借用某个进程的页表。

回顾一下，xv6保证每个进程只使用自己的内存。每个进程看它自己的内存都是从0开始的连续的虚拟地址，然而它的物理内存地址不一定连续。Xv6 只设置进程自己虚拟内存地址的PTE的PTE_U标志位。然后使用页表把虚拟地址翻译为给进程分配的物理内存页。

（2）阅读XV6系统中的mmu.h头文件，分析64行到104行定义的各种常量及define的意义，描述每一个常量和定义代表什么意义。

XV6系统中mmu.h头文件的64行到104行代码如下：

// A virtual address 'la' has a three-part structure as follows:  
//  
// +--------10------+-------10-------+---------12----------+  
// | Page Directory |   Page Table   | Offset within Page  |  
// |      Index     |      Index     |                     |  
// +----------------+----------------+---------------------+  
//  \--- PDX(va) --/ \--- PTX(va) --/  
  
// page directory index  
#define PDX(va)         (((uint)(va) >> PDXSHIFT) & 0x3FF)  
  
// page table index  
#define PTX(va)         (((uint)(va) >> PTXSHIFT) & 0x3FF)  
  
// construct virtual address from indexes and offset  
#define PGADDR(d, t, o) ((uint)((d) << PDXSHIFT | (t) << PTXSHIFT | (o)))  
  
// Page directory and page table constants.  
#define NPDENTRIES      1024    // # directory entries per page directory  
#define NPTENTRIES      1024    // # PTEs per page table  
#define PGSIZE          4096    // bytes mapped by a page  
  
#define PTXSHIFT        12      // offset of PTX in a linear address  
#define PDXSHIFT        22      // offset of PDX in a linear address  
  
#define PGROUNDUP(sz)  (((sz)+PGSIZE-1) & ~(PGSIZE-1))  
#define PGROUNDDOWN(a) (((a)) & ~(PGSIZE-1))  
  
// Page table/directory entry flags.  
#define PTE_P           0x001   // Present  
#define PTE_W           0x002   // Writeable  
#define PTE_U           0x004   // User  
#define PTE_PS          0x080   // Page Size  
  
// Address in page table or page directory entry  
#define PTE_ADDR(pte)   ((uint)(pte) & ~0xFFF)  
#define PTE_FLAGS(pte)  ((uint)(pte) &  0xFFF)  
  
#ifndef __ASSEMBLER__  
typedef uint pte_t;

1)常量定义

①PGSIZE：定义了一个页面（Page）的大小，这里是4096字节，即4KB。

②NPDENTRIES：每个页目录（Page Directory）包含的条目（Entry）数量，这里是1024。

③NPTENTRIES：每个页表（Page Table）包含的页表条目（PTE, Page Table Entry）数量，这里也是1024。

④PTXSHIFT：在线性地址（Linear Address）中，页表索引（PTX, Page Table Index）的偏移量，这里是12位。

⑤PDXSHIFT：在线性地址中，页目录索引（PDX, Page Directory Index）的偏移量，这里是22位。

2)宏定义

①PDX(va)：宏，用于从给定的虚拟地址（va）中提取页目录索引（PDX）。

②PTX(va)：宏，用于从给定的虚拟地址中提取页表索引（PTX）。

③PGADDR(d, t, o)：宏，根据给定的页目录索引（d）、页表索引（t）和页面内的偏移（o），构造出对应的虚拟地址。

④PGROUNDUP(sz)：宏，将给定的大小（sz）向上取整到最接近的页面大小的倍数。

⑤PGROUNDDOWN(a)：宏，将给定的地址（a）向下取整到最接近的页面起始地址。

3)页表/页目录条目标志

①PTE_P：页表条目存在（Present）标志。如果设置，表示页面在物理内存中。

②PTE_W：可写（Writeable）标志。如果设置，允许对该页面进行写操作。

③PTE_U：用户模式（User）标志。如果设置，允许用户模式的程序访问该页面。

④PTE_PS：页面大小（Page Size）标志。在支持大页面的系统中，这个标志指示页表条目表示的是一个大页面，而不是常规的4KB页面。

4)地址提取和标志提取

①PTE_ADDR(pte)：宏，从页表条目（pte）中提取物理地址部分。

②PTE_FLAGS(pte)：宏，从页表条目中提取标志部分。

5)类型定义

①pte_t：定义了一个名为pte_t的类型，它实际上是uint类型的一个别名，用于表示页表条目。

这些定义和常量一起工作，使得XV6系统能够正确地将虚拟地址映射到物理地址，管理内存访问权限，并支持页面大小的不同配置。这些定义还使得内存管理的实现更加清晰和模块化，提高了代码的可读性和可维护性。

（3）阅读XV6系统中的main.c文件的97行到最后的数组初始化，分析XV6系统初始化阶段的单级页表的构成与映射关系，着重分析数组中每一项数据分别对应着什么信息，存储进页表的两个0的值意味着什么。

XV6系统中的main.c文件的97行到最后的数组初始化代码如下：

// The boot page table used in entry.S and entryother.S.  
// Page directories (and page tables) must start on page boundaries,  
// hence the __aligned__ attribute.  
// PTE_PS in a page directory entry enables 4Mbyte pages.  
  
__attribute__((__aligned__(PGSIZE)))  
pde_t entrypgdir[NPDENTRIES] = {  
        // Map VA's [0, 4MB) to PA's [0, 4MB)  
        [0] = (0) | PTE_P | PTE_W | PTE_PS,  
        // Map VA's [KERNBASE, KERNBASE+4MB) to PA's [0, 4MB)  
        [KERNBASE>>PDXSHIFT] = (0) | PTE_P | PTE_W | PTE_PS,  
};  
  
//PAGEBREAK!  
// Blank page.  
//PAGEBREAK!  
// Blank page.  
//PAGEBREAK!  
// Blank page.

1)分析XV6系统初始化阶段的单级页表的构成与映射关系：

在XV6中，操作系统使用页表来管理虚拟地址到物理地址的映射。页表分为页目录（Page Directory）和页表（Page Table）两部分。页目录中的每个条目（PDE，Page Directory Entry）指向一个页表，而页表中的每个条目（PTE，Page Table Entry）则映射一个虚拟页到物理页。

2)分析数组entrypgdir中的每一项数据：

① [0] = (0) | PTE_P | PTE_W | PTE_PS：这一项是页目录表的第一个条目。它映射虚拟地址范围[0, 4MB)到物理地址范围[0, 4MB)。

② [KERNBASE>>PDXSHIFT] = (0) | PTE_P | PTE_W | PTE_PS：这一项是页目录表的第二个条目。它映射虚拟地址范围[KERNBASE, KERNBASE+4MB)到物理地址范围[0, 4MB)。

3)分析存储进页表的两个0的值意味着什么：

在xv6操作系统中，页表项（PTE）和页目录项（PDE）的存储通常包含虚拟地址到物理地址的映射信息，以及关于页面状态的一些标志位。

在上面的代码中，有两个PDE项被初始化，它们的物理地址部分都是(0)。这里的(0)值实际上指的是这些页面映射到的物理内存起始地址。

在页目录或页表中，每个条目都包含一个物理地址的部分，这个部分指明了虚拟地址空间中某个区域应该映射到物理地址空间的哪个起始地址。对于这两个特定的映射来说：

①第一个映射（entrypgdir[0]）将虚拟地址范围[0, 4MB)映射到物理地址范围[0, 4MB)。这里的(0)意味着虚拟地址0对应着物理地址0。

②第二个映射（entrypgdir[KERNBASE>>PDXSHIFT]）将虚拟地址范围[KERNBASE, KERNBASE+4MB)映射到物理地址范围[0, 4MB)。同样，这里的(0)意味着虚拟地址KERNBASE对应着物理地址0。

因此，这两个(0)值意味着这两个映射都是从各自虚拟地址空间的起始点映射到物理地址空间的起始点。在XV6的上下文中，这是一种简化，允许内核和用户空间共享物理内存的前4MB。这种设计使得内核可以直接访问物理内存的前4MB，而用户空间的前4MB也映射到相同的物理内存区域。

2.修改XV6内核源码

下载本次实验提供的三个修改版文件，main.c，entry.S，entryOther.S，替换掉xv6系统中的这三个文件。

（1）entry.S文件中新加的汇编代码将现有的单级页表改为二级页表，逐行分析这段x86汇编代码，每一行都要说明其目的与意义，每个常量、数值都要分析其含义

entry.S中新加的汇编代码如下，注释说明其目的与意义。

  #初始化页表内容  
  
  xor %esi, %esi  #将索引值复制到 %eax 寄存器
1:  
  movl %esi, %eax  #将 %eax 寄存器中的值左移12位，得到页表项的虚拟地址基础部分
  shll $12, %eax  #将 PTE_P 和 PTE_W 标志位或运算的结果加到 %eax 寄存器中，设置页表项的属性
  orl $(PTE_P|PTE_W), %eax  #将 page_table 的物理地址加载到 %edi 寄存器中
  movl $(V2P_WO(page_table)), %edi  #将索引值复制到 %ebx 寄存器
  movl %esi, %ebx  #将 %ebx 寄存器中的值左移2位，计算页表项在 page_table 中的偏移
  shll $2, %ebx  #将偏移加到 %edi 寄存器中，得到当前页表项的物理地址
  addl %ebx, %edi  #将 %eax 寄存器中的页表项值存储到 %edi 指向的物理地址
  movl %eax, (%edi)  #增加索引值 %esi
  incl %esi  #比较 %esi 和 1024，检查是否还有更多的页表项需要初始化
  cmpl $1024, %esi  #如果 %esi 小于 1024，则跳转到 1: 标签处继续循环
  jb 1b  #初始化页目录表内容，清零 %esi 寄存器，作为页目录项的索引
  
  # 初始化页目录表内容  
  
  movl $0, %esi  #将索引值复制到 %ebx 寄存器
  movl %esi, %ebx  #将 %ebx 寄存器中的值左移2位，计算页目录项在 entrypgdir 中的偏移
  shll $2, %ebx  #将 entrypgdir 的物理地址加载到 %edi 寄存器中
  movl $(V2P_WO(entrypgdir)), %edi  #将偏移加到 %edi 寄存器中，得到当前页目录项的物理地址
  addl %ebx, %edi  #将 page_table 的物理地址存储到当前页目录项的物理地址中
  movl $(V2P_WO(page_table)), (%edi)  #设置页目录项的 PTE_P 和 PTE_W 属性
  orl $(PTE_P | PTE_W), (%edi)  #将索引值设置为 512，准备初始化第二个页目录项
  
  movl $512, %esi  #将索引值复制到 %ebx 寄存器
  movl %esi, %ebx  #将 %ebx 寄存器中的值左移2位，计算页目录项在 entrypgdir 中的偏移
  shll $2, %ebx  #将 entrypgdir 的物理地址加载到 %edi 寄存器中
  movl $(V2P_WO(entrypgdir)), %edi  #将偏移加到 %edi 寄存器中，得到当前页目录项的物理地址
  addl %ebx, %edi  #将 page_table 的物理地址存储到当前页目录项的物理地址中
  movl $(V2P_WO(page_table)), (%edi)  #设置页目录项的 PTE_P 和 PTE_W 属性
  orl $(PTE_P | PTE_W), (%edi)  #将 PTE_P 和 PTE_W 这两个标志位的或运算结果加到 %edi 寄存器所指向的内存地址

在这段代码中，首先初始化了1024个页表项，每个页表项指向一个虚拟页，并且设置了页表项的PTE_P和PTE_W属性。然后，初始化了两个页目录项，每个页目录项指向上面初始化的页表，并且也设置了页目录项的PTE_P和PTE_W属性。这样，就完成了从单级页表到二级页表的转换。

（2）在main.c中，有一个空的func()函数。在其中用c语言在5行代码以内复刻entry.S中汇编代码的操作，并描述你的思路，论证为何你的C代码与汇编代码是效果完全相同的。（注意：本任务严禁使用0以外的任何数值，所有0以外的数值应调用mmu.h等头文件中定义的常量，并说明你选择这个常量的原因。常量选择错误(如混淆PTE_T和PDE_T)将被扣分）。

entry.S中的汇编代码如下，主要功能是完成页表和页目录的初始化，为它们设置适当的物理地址和权限标志。

  #初始化页表内容  
  
  xor %esi, %esi  
1:  
  movl %esi, %eax  
  shll $12, %eax  
  orl $(PTE_P|PTE_W), %eax  
  movl $(V2P_WO(page_table)), %edi  
  movl %esi, %ebx  
  shll $2, %ebx  
  addl %ebx, %edi  
  movl %eax, (%edi)  
  incl %esi  
  cmpl $1024, %esi  
  jb 1b  
  
  # 初始化页目录表内容  
  
  movl $0, %esi  
  movl %esi, %ebx  
  shll $2, %ebx  
  movl $(V2P_WO(entrypgdir)), %edi  
  addl %ebx, %edi  
  movl $(V2P_WO(page_table)), (%edi)  
  orl $(PTE_P | PTE_W), (%edi)  
  
  movl $512, %esi  
  movl %esi, %ebx  
  shll $2, %ebx  
  movl $(V2P_WO(entrypgdir)), %edi  
  addl %ebx, %edi  
  movl $(V2P_WO(page_table)), (%edi)  
  orl $(PTE_P | PTE_W), (%edi)

1)翻译成C语言函数

根据给定的汇编代码，我将其翻译成以下的C语言函数：

void init_entrypgdir() {    
    pte_t *pt = (pte_t*)V2P_WO(page_table); // 将页表的虚拟地址转换为物理地址，并转换为pte_t指针    
    for (uint i = 0; i < NPTENTRIES; i++) { // 遍历页表中的每个条目    
        pt[i] = (i << PTXSHIFT) | PTE_P | PTE_W; // 设置页表条目的值：虚拟地址、存在标志和可写标志    
    }    
        
    pde_t *pd = (pde_t*)V2P_WO(entrypgdir); // 将页目录的虚拟地址转换为物理地址，并转换为pde_t指针    
    pd[PDX(V2P_WO(page_table))] = V2P_WO(page_table) | PTE_P | PTE_W; // 设置第一个页目录项：映射页表的物理地址、存在标志和可写标志    
    pd[PDX(V2P_WO(page_table) + PGSIZE * NPTENTRIES)] = V2P_WO(page_table) | PTE_P | PTE_W; // 设置第二个页目录项：映射第二个页表的物理地址、存在标志和可写标志    
}

2)思路描述

①初始化页表：遍历页表中的每个条目，并设置每个条目的地址为其对应的虚拟地址（通过左移PTXSHIFT位得到），同时设置存在标志和可写标志。

②初始化页目录：设置两个页目录项，每个项都指向同一个页表的物理地址，并设置存在标志和可写标志。第一个页目录项对应页表的起始地址，第二个页目录项对应下一个页表的起始地址（即第一个页表的结束地址加上一个页面的大小）。

3)论证为何C代码与汇编代码效果完全相同

①C代码中的pte_t *pt = (pte_t*)V2P_WO(page_table);与汇编代码中的movl $(V2P_WO(page_table)), %edi;等价，都用于获取页表的物理地址并初始化指针。

②C代码中的循环初始化页表项与汇编代码中的循环结构（从标签1:开始）在逻辑上相同，都设置了每个页表项的虚拟地址、存在标志和可写标志。

③C代码中的pde_t *pd = (pde_t*)V2P_WO(entrypgdir);与汇编代码中的movl $(V2P_WO(entrypgdir)), %edi;等价，都用于获取页目录的物理地址并初始化指针。

④C代码中的pd[PDX(V2P_WO(page_table))]和pd[PDX(V2P_WO(page_table) + PGSIZE * NPTENTRIES)]分别设置第一个和第二个页目录项，这与汇编代码中对应设置第一个和第二个页目录项的代码在逻辑上相同。它们都计算了正确的索引，并设置了正确的物理地址、存在标志和可写标志。

⑤由于C代码和汇编代码都使用了相同的常量和宏来执行地址计算、标志设置等操作，因此它们最终生成的页表和页目录内容是完全相同的。

总结：通过比较C代码和汇编代码的逻辑，可以看出它们在设置页表和页目录条目方面使用了相同的逻辑和常量。因此，可以论证C代码与汇编代码在效果上是完全相同的。

4)选择常量的原因

①NPTENTRIES 和 NPDENTRIES：这两个常量分别表示每个页表和页目录中的条目数量。在初始化页表和页目录时，需要遍历这些条目来设置它们的值。

②PGSIZE：这个常量表示每个页面的大小（以字节为单位）。在计算第二个页目录项的索引时，需要用到这个常量来确定页面的边界。

③PTXSHIFT 和 PDXSHIFT：这两个常量分别表示页表索引和页目录索引在虚拟地址中的偏移量。它们用于从虚拟地址中提取对应的索引。

④PTE_P 和 PTE_W：这两个常量是页表项的标志位，分别表示页面存在和页面可写。在初始化页表项时，需要设置这些标志位。

⑤V2P_WO：这个宏用于将虚拟地址转换为物理地址。在初始化过程中，需要使用物理地址来访问页表和页目录。

5)注意

①在设置第二个页目录项时，我使用了PGSIZE * NPTENTRIES来计算第二个页目录项应该映射的虚拟地址。这是因为每个页表管理NPTENTRIES个页面，每个页面大小为PGSIZE字节。

②由于页目录项映射的是整个页表，而不是单个页面，因此第二个页目录项对应的虚拟地址是第一个页表的结束地址加上一个页面的大小，即V2P_WO(page_table) + PGSIZE * NPTENTRIES。