Garden of John

实验整理2

70分钟阅读

基本原理概述

物理内存管理

在计算机系统的最底层，物理内存由一系列具有实际地址的存储单元构成。每个内存单元都拥有唯一的物理地址，CPU通过地址总线直接发送这些物理地址来访问内存数据。在简单系统中，程序指令中的内存地址（如MOV [0x80200000], %eax）会直接被CPU当作物理地址发送到内存总线上，这种方式实现了最直接的内存访问。

然而，当多个程序需要共享内存空间时，这种直接访问物理地址的方式会面临严重问题。首先，如果内核和用户程序都试图访问相同的物理地址（如0x80200000），就会产生冲突，导致数据被意外修改或破坏。更重要的是，这种内存管理方式对内存连续性有着苛刻的要求——每个程序都需要获得连续的内存空间才能运行。

由于程序对连续内存空间的需求，物理内存很容易产生碎片化问题。即使系统中总的空闲内存容量足够，但如果这些空闲内存分散成多个不连续的小块，程序仍然可能因为找不到足够的连续空间而无法运行。这种对连续性的强烈依赖，使得简单物理内存管理在复杂系统中难以有效工作。

那么如何消除这种影响呢？大家显然可以想象得到，我们可以通过让用户程序访问的0x80200000和内核访问的0x80200000不是一个地址来解决这个问题。但是如果我们只有一块内存，那么为了创造两个不同的地址空间，我们可以引入一个”翻译“机制：程序使用的地址需要经过一步”翻译“才能变成真正的内存的物理地址。这个”翻译“过程，我们可以用一个”词典“实现。通过这个”词典“给出翻译之前的地址，可以在词典里查找翻译后的地址。而对每个程序往往都有着唯一的一本”词典“，而它能使用的内存也就只有他的”词典“所包含的。

”词典“是否对能使用的每个字节都进行翻译？我们可以想象，存储每个字节翻译的结果至少需要一个字节，那么使用1MB的内存将至少需要构造1MB的”词典“，这效率太低了。观察到，一个程序使用内存的数量级通常远大于字节，至少以KB为单位（所以上古时代的人说的是”640K对每个人都够了“而不是”640B对每个人都够了”）。那么我们可以考虑，把连续的很多字节合在一起翻译，让他们翻译前后的数值之差相同，这就是“页”。

物理地址和虚拟地址

在本次实验中，我们使用的是RISCV的sv39页表机制，每个页的大小是4KB，也就是4096个字节。通过之前的介绍，相信大家对物理地址和虚拟地址有了一个初步的认识了，页表就是那个“词典”，里面有程序使用的虚拟页号到实际内存的物理页号的对应关系，但并不是所有的虚拟页都有对应的物理页。虚拟页可能的数目远大于物理页的数目，而且一个程序在运行时，一般不会拥有所有物理页的使用权，只会占用部分物理页，这些物理页再通过页表映射到虚拟地址空间中。

分页机制的一个重要优势在于，它带来了地址管理的灵活性。程序员只需要面对一个连续的虚拟地址空间，而不需要关心底层物理内存是否连续。不同程序使用的虚拟地址空间可以相同，但通过页表映射到不同的物理地址，避免了冲突。操作系统还可以通过修改页表，方便地实现内存共享、隔离和换页。

在sv39中，定义物理地址(Physical Address)有 56位，而虚拟地址(Virtual Address) 有 39位。实际使用的时候，一个虚拟地址要占用 64位，只有低 39位有效，我们规定 63−39 位的值必须等于第 38 位的值（大家可以将它类比为有符号整数），否则会认为该虚拟地址不合法，在访问时会产生异常。不论是物理地址还是虚拟地址，我们都可以认为，最后12位表示的是页内偏移，也就是这个地址在它所在页帧的什么位置（同一个位置的物理地址和虚拟地址的页内偏移相同）。除了最后12位，前面的部分表示的是物理页号或者虚拟页号。

实验执行流程概述

本次实验主要完成ucore内核对物理内存的管理工作。我们要对ucore进行相关拓展，修改ucore总控函数kern_init的代码。

kernel在后续执行中能够探测出的物理内存情况进行物理内存管理初始化工作。其次，我们修改了entry.S中的kern_entry函数。kern_entry函数的主要任务是设置虚拟内存管理，将三级页表的物理地址和Sv39模式位写入satp寄存器，以建立内核的虚拟内存空间，为之后建立分页机制的过程做一个准备。完成这些工作后，才调用kern_init函数。

kern_init函数在完成一些输出后，将进入物理内存管理初始化的工作，即调用pmm_init函数完成物理内存的管理。接着是执行中断和异常相关的初始化工作，即调用idt_init函数。

为了完成物理内存管理，这里首先需要探测可用的物理内存资源；了解到物理内存位于什么地方，有多大之后，就以固定页面大小来划分整个物理内存空间，并准备以此为最小内存分配单位来管理整个物理内存，管理在内核运行过程中每页内存，设定其可用状态（free的，used的，还是reserved的），这其实就对应了我们在课本上讲到的连续内存分配概念和原理的具体实现；接着ucore就要建立页表，启动分页机制，让CPU的MMU把预先建立好的页表中的页表项读入到TLB中，根据页表项描述的虚拟页（Page）与物理页帧（Page Frame）的对应关系完成CPU对内存的读、写和执行操作。这一部分其实就对应了我们在课上讲到内存映射、页表、多级页表等概念和原理的具体实现。

ucore在实现上述技术时，需要解决两个关键问题：

  • 如何建立虚拟地址和物理地址之间的联系
  • 如何在现有ucore的基础上实现物理内存页分配算法

接下来将进一步分析完成lab2主要注意的关键问题和涉及的关键数据结构。

以页为单位管理物理内存

页表项

一个页表项是用来描述一个虚拟页号如何映射到物理页号的。如果一个虚拟页号通过某种手段找到了一个页表项，并通过读取上面的物理页号完成映射，那么我们称这个虚拟页号通过该页表项完成映射。而我们的”词典“（页表）存储在内存里，由若干个格式固定的”词条“也就是页表项（PTE, Page Table Entry）组成。显然我们需要给词典的每个词条约定一个固定的格式（包括每个词条的大小，含义），这样查起来才方便。

那么在sv39的一个页表项占据8字节（64位），那么页表项结构是这样的：

63-5453-2827-1918-109-876543210
ReservedPPN[2]PPN[1]PPN[0]RSWDAGUXWRV
102699211111111

我们可以看到 sv39 里面的一个页表项大小为 64 位 8 字节。其中第 53-10 位共44位为一个物理页号，表示这个虚拟页号映射到的物理页号。后面的第 9-0 位共10位则描述映射的状态信息。

介绍一下映射状态信息各位的含义：

  • RSW：两位留给 S Mode 的应用程序，我们可以用来进行拓展。
  • D：即 Dirty ，如果 D=1 ，表示从上次 D 被清零后开始算起，有虚拟地址通过这个页表项进行写入。
  • A，即 Accessed，如果 A=1 ，表示从上次 A 被清零后开始算起，有虚拟地址通过这个页表项进行读、或者写、或者取指。
  • G，即 Global，如果 G=1 表示这个页表项是”全局”的，也就是所有的地址空间（所有的页表）都包含这一项。
  • U，即 user，U为 1 表示用户态 (U Mode)的程序 可以通过该页表项进映射。在用户态运行时，也只能够通过 U=1 的页表项进行虚实地址映射。 注意，S Mode 不一定可以通过 U=1 的页表项进行映射。我们需要将 S Mode 的状态寄存器 sstatus 上的 SUM 位手动设置为 1 才可以做到这一点（通常情况不会把它置1）。否则通过 U=1 的页表项进行映射也会报出异常。另外，不论sstatus的SUM位如何取值，S Mode都不允许执行 U=1 的页面里包含的指令，这是出于安全的考虑。
  • R,W,X 为许可位，分别表示是否可读 (Readable)，可写 (Writable)，可执行 (Executable)。 以 W 这一位为例，如果 W=0 表示不可写，那么如果一条 store 的指令，它通过这个页表项完成了虚拟页号到物理页号的映射，找到了物理地址。但是仍然会报出异常，是因为这个页表项规定如果物理地址是通过它映射得到的，那么不准写入！ R,X也是同样的道理。 根据 R,W,X 取值的不同，我们可以分成下面几种类型：
XWRMeaning
000指向下一级页表的指针
001这一页只读
010保留(reserved for future use)
011这一页可读可写（不可执行）
100这一页可读可执行（不可写）
101这一页可读可执行
110保留(reserved for future use)
111这一页可读可写可执行
  • V 表示这个页表项是否合法。如果为 0 表示不合法，此时页表项其他位的值都会被忽略。

多级页表

在实际使用中显然如果只有一级页表，那么我们构建出来的虚拟地址空间还是过于有限，因此我们需要引入多级页表以实现更大规模的虚拟地址空间。

但是相比于可用的物理内存空间，我们的虚拟地址空间太大，不可能为每虚个拟内存页都分配一个页表项。可以简单计算一下，在Sv39中，因为一个页表项占据8字节（64位），而虚拟地址有39位，后12位是页内偏移，那么还剩下27位可以编码不同的虚拟页号。

如果开一个大数组Pagetable[ ], 其中Pagetable[vpn]代表虚拟页号为vpn的虚拟页对应的的页表项，我们给个2^27 的虚拟页号都分配8字节的页表项，那就是整整1 GiB的内存。但这里面其实很多虚拟地址我们没有用到，会有大片大片的页表项的标志位为0（不合法），显然我们不应该为那么多非法页表项浪费宝贵的内存空间。

因此，我们可以对页表进行“分级”，让它变成一个树状结构。也就是把很多页表项组合成一个“大页”，如果这些页表项都非法（没有对应的物理页），那么只需要用一个非法的页表项来覆盖这个大页，而不需要分别建立一大堆非法页表项。很多个大页(megapage)还可以组合起来变成大大页(gigapage!)，继而可以有更大的页，以此类推，当然肯定不是分层越多越好，因为随着层数增多，开销也会越大。

在本次实验中，我们使用的sv39权衡各方面效率，使用三级页表。有4KiB=4096字节的页，大小为2MiB= 2^21 字节的大页，和大小为1 GiB 的大大页。

原先的一个39位虚拟地址，被我们看成27位的页号和12位的页内偏移。那么在三级页表下，我们可以把它看成9位的“大大页页号”，9位的“大页页号”（也是大大页内的页内偏移），9位的“页号”（大页的页内偏移），还有12位的页内偏移。这是一个递归的过程，中间的每一级页表映射是类似的。也就是说，整个Sv39的虚拟内存空间里，有512（2的9次方）个大大页，每个大大页里有512个大页，每个大页里有512个页，每个页里有4096个字节，整个虚拟内存空间里就有512∗512∗512∗4096个字节，是512GiB的地址空间。

那么为啥是512呢？注意，4096/8 = 512，我们恰好可以在一页里放下512个页表项！

我们可以认为，Sv39的多级页表在逻辑上是一棵树，它的每个叶子节点都对应内存的一页，它的每个内部节点都对应512个更低一层的节点，而每个内部节点向更低一层节点的链接都使用内存页中的页表项进行存储。

我们可以根据图示详细理解一下：

Sv39页表的根节点会占据一页4KiB的内存，存储512个页表项（一个页表项占据8字节），分别对应512个1 GiB的大大页。虚拟地址27位页号中的高9位用来在根节点中索引页表项，找到对应的大大页（注意只有合法的页表项才是根节点的儿子，可以跳转到一个物理页号，对应树中一个“大大页”的节点）。

大大页同样是4KiB的内存存储512个页表项，对应512个2MiB的大页，虚拟地址27位页号中的中9位用来在大大页中索引页表项，找到对应的大页的物理页号（同样需要是合法的）。同理，大页的配置与根节点、大大页如出一辙，通过虚拟地址27位页号中的低9位索引大页，便可以找到虚拟地址对应的4KiB物理页，接着用12位页内偏移索引物理页来找到具体的内容。

三级和二级页表项不一定要指向下一级页表。我们知道每个一级页表项控制一个虚拟页号，即控制 4KiB 虚拟内存；每个二级页表项则控制 9 位虚拟页号，总计控制 4KiB×2^9 =2MiB 虚拟内存；每个三级页表项控制 18 位虚拟页号，总计控制 2MiB×2^9 =1GiB 虚拟内存。我们可以将二级页表项的 R,W,X 设置为不是全 0 的许可要求，那么它将与一级页表项类似，只不过可以映射一个 2MiB 的大页 (Mega Page) 。同理，也可以将三级页表项看作一个叶子，来映射一个 1GiB 的大大页(Giga Page)。

页表基址

那么在翻译的过程中，我们如何知道树状页表的根节点的物理地址呢？很多同学可能注意到了，在上面图片中出现的satp，对于RISCV架构，树状页表的根节点的物理地址一般保存在一个特殊寄存器里，就叫做satp（Supervisor Address Translation and Protection Register）。

实际上，satp里面存的不是最高级页表的起始物理地址，而是它所在的物理页号。除了物理页号，satp还包含其他信息。

63-6059-4443-0
MODE(WARL)ASID(WARL)PPN(WARL)
41644

MODE表示当前页表的模式：

  • 0000表示不使用页表，直接使用物理地址，在简单的嵌入式系统里用着很方便。
  • 1000表示sv39页表，也就是我们使用的，虚拟内存空间高达512GiB。
  • 1001表示Sv48页表，它和Sv39兼容。
  • 其他编码保留备用

ASID（address space identifier）我们目前用不到。

OS 可以在内存中为不同的应用分别建立不同虚实映射的页表，并通过修改寄存器 satp 的值指向不同的页表，从而可以修改 CPU 虚实地址映射关系及内存保护的行为。

建立快表以加快访问效率

物理内存的访问速度要比 CPU 的运行速度慢很多, 去访问一次物理内存可能需要几百个时钟周期（带来所谓的“冯诺依曼瓶颈”）。如果我们按照页表机制一步步走，将一个虚拟地址转化为物理地址需要访问 3 次物理内存，得到物理地址之后还要再访问一次物理内存，才能读到我们想要的数据。这很大程度上降低了效率。 好在，实践表明虚拟地址的访问具有时间局部性和空间局部性。

  • 时间局部性是指，被访问过一次的地址很有可能不远的将来再次被访问；
  • 空间局部性是指，如果一个地址被访问，则这个地址附近的地址很有可能在不远的将来被访问。

因此，在 CPU 内部，我们使用快表 (TLB, Translation Lookaside Buffer) 来记录近期已完成的虚拟页号到物理页号的映射。由于局部性，当我们要做一个映射时，会有很大可能这个映射在近期被完成过，所以我们可以先到 TLB 里面去查一下，如果有的话我们就可以直接完成映射，而不用访问那么多次内存了。

分页机制的设计思路

建立段页式管理中需要考虑的关键问题

为了实现分页机制，需要建立好虚拟内存和物理内存的页映射关系，即正确建立三级页表。此过程涉及硬件细节，不同的地址映射关系组合，相对比较复杂。总体而言，我们需要思考如下问题：

  • 对于哪些物理内存空间需要建立页映射关系？
  • 具体的页映射关系是什么？
  • 页目录表的起始地址设置在哪里？
  • 页表的起始地址设置在哪里，需要多大空间？
  • 如何设置页目录表项的内容？
  • 如何设置页表项的内容？

实现分页机制

接下来我们就正式开始实验啦！ 首先我们要做的是内核初始化的修改，我们现在需要做的就是把原本只能直接在物理地址空间上运行的内核引入页表机制。 具体来说，我们现在想将内核代码放在虚拟地址空间中以 0xffffffffc0200000 开头的一段高地址空间中。那怎么做呢？首先我们需要将下面的参数修改一下：

// tools/kernel.ld
BASE_ADDRESS = 0xFFFFFFFFC0200000;
//之前这里是 0x80200000

我们修改了链接脚本中的起始地址。但是这样做的话，就能从物理地址空间转移到虚拟地址空间了吗？大家可以分析一下现在我们相当于是在 bootloader 的 OpenSBI 结束后的现状，这样就可以更好的理解接下来我们需要干什么：

  • 物理内存状态：OpenSBI 代码放在 [0x80000000,0x80200000) 中，内核代码放在以 0x80200000 开头的一块连续物理内存中。这个是实验一我们做完后就实现的效果。
  • CPU 状态：处于 S Mode ，寄存器 satp 的 MODE被设置为 Bare ，即无论取指还是访存我们都通过物理地址直接访问物理内存。 PC=0x80200000 指向内核的第一条指令。栈顶地址 SP 处在 OpenSBI 代码内。
  • 内核代码：这部分由于改动了链接脚本的起始地址，所以它会认为自己处在以虚拟地址 0xffffffffc0200000 开头的一段连续虚拟地址空间中，以此为依据确定代码里每个部分的地址（每一段都是从BASE_ADDRESS往后依次摆开的，所以代码里各段都会认为自己在0xffffffffc0200000之后的某个地址上，或者说编译器和链接器会把里面的符号/变量地址都对应到0xffffffffc0200000之后的某个地址上）

接下来，我们需要修改 entry.S 文件来实现内核的初始化，我们在入口点 entry.S 中所要做的事情是：将 SP 寄存器从原先指向OpenSBI 某处的栈空间，改为指向我们自己在内核的内存空间里分配的栈；同时需要跳转到函数 kern_init 中。

在之前的实验中，我们已经在 entry.S 自己分配了一块 8KiB的内存用来做启动栈：

#include <mmu.h>
#include <memlayout.h>

    .section .text,"ax",%progbits
    .globl kern_entry
kern_entry:
    la sp, bootstacktop

    tail kern_init

.section .data
    # .align 2^12
    .align PGSHIFT
    .global bootstack
bootstack:
    .space KSTACKSIZE
    .global bootstacktop
bootstacktop:

通过之前的实验大家应该都明白：符号 bootstacktop 就是我们需要的栈顶地址, 符号 kern_init 代表了我们要跳转到的地址。之前我们直接将 bootstacktop 的值给到 SP ， 再跳转到 kern_init 就行了。看上去上面的这个代码也能够实现我们想要的初始化效果，但问题在于，由于我们修改了链接脚本的起始地址，编译器和链接器认为内核开头地址为 0xffffffffc0200000，因此这两个符号会被翻译成比这个开头地址还要高的某个虚拟地址。而我们的 CPU 目前还处于 Bare 模式，会将地址都当成物理地址处理。这样，我们跳转到 kern_init， 就意味着会跳转到比0xffffffffc0200000还大的一个物理地址。但物理地址显然不可能有这么多位！这就会出现问题。

于是，我们需要想办法利用刚学的页表知识，帮内核将需要的虚拟地址空间构造出来。也就是：构建一个合适的页表，让satp指向这个页表，然后使用地址的时候都要经过这个页表的翻译，使得虚拟地址0xFFFFFFFFC0200000经过页表的翻译恰好变成0x80200000，这个地址显然就比较合适了，也就不会出错了。

理论知识告诉我们，所有的虚拟地址有一个固定的偏移量。而要想实现页表结构这个偏移量显然是不可或缺的。而虚拟地址和物理地址之间的差值就可以当成是这个偏移量。

比如内核的第一条指令，虚拟地址为 0xffffffffc0200000 ，物理地址为 0x80200000 ，因此，我们只要将虚拟地址减去 0xffffffff40000000 ，就得到了物理地址。所以当我们需要做到去访问内核里面的一个物理地址 va 时，而已知虚拟地址为 va 时，则 va 处的代码或数据就放在物理地址为 pa = va - 0xffffffff40000000 处的物理内存中，我们真正所要做的是要让 CPU 去访问 pa。因此，我们要通过恰当构造页表，来对于内核所属的虚拟地址，实现这种 va 到 pa 的映射。

还记得之前的理论介绍的内容吗？那时我们提到，将一个三级页表项的标志位 R,W,X 不设为全 0 ，可以将它变为一个叶子，从而获得大小为 1GiB 的一个大页。

我们假定内核大小不超过 1GiB，通过一个大页将虚拟地址区间[0xffffffffc0000000,0xffffffffffffffff] 映射到物理地址区间 [0x80000000,0xc0000000)，而我们只需要分配一页内存用来存放三级页表，并将其最后一个页表项(也就是对应我们使用的虚拟地址区间的页表项)进行适当设置即可。对应的代码如下所示：

#include <mmu.h>
#include <memlayout.h>

    .section .text,"ax",%progbits
    .globl kern_entry
kern_entry:
    # a0: hartid
    # a1: dtb physical address
    # save hartid and dtb address
    la t0, boot_hartid
    sd a0, 0(t0)
    la t0, boot_dtb
    sd a1, 0(t0)

    # t0 := 三级页表的虚拟地址
    lui     t0, %hi(boot_page_table_sv39)
    # t1 := 0xffffffff40000000 即虚实映射偏移量
    li      t1, 0xffffffffc0000000 - 0x80000000
    # t0 减去虚实映射偏移量 0xffffffff40000000，变为三级页表的物理地址
    sub     t0, t0, t1
    # t0 >>= 12，变为三级页表的物理页号
    srli    t0, t0, 12

    # t1 := 8 << 60，设置 satp 的 MODE 字段为 Sv39
    li      t1, 8 << 60
    # 将刚才计算出的预设三级页表物理页号附加到 satp 中
    or      t0, t0, t1
    # 将算出的 t0(即新的MODE|页表基址物理页号) 覆盖到 satp 中
    csrw    satp, t0
    # 使用 sfence.vma 指令刷新 TLB
    sfence.vma
    # 从此，我们给内核搭建出了一个完美的虚拟内存空间！
    #nop # 可能映射的位置有些bug。。插入一个nop

    # 我们在虚拟内存空间中：随意将 sp 设置为虚拟地址！
    lui sp, %hi(bootstacktop)

    # 我们在虚拟内存空间中：随意跳转到虚拟地址！
    # 跳转到 kern_init
    lui t0, %hi(kern_init)
    addi t0, t0, %lo(kern_init)
    jr t0

.section .data
    # .align 2^12
    .align PGSHIFT
    .global bootstack
bootstack:
    .space KSTACKSIZE
    .global bootstacktop
bootstacktop:

.section .data
    # 由于我们要把这个页表放到一个页里面，因此必须 12 位对齐
    .align PGSHIFT
    .global boot_page_table_sv39
# 分配 4KiB 内存给预设的三级页表
boot_page_table_sv39:
    # 0xffffffff_c0000000 map to 0x80000000 (1G)
    # 前 511 个页表项均设置为 0 ，因此 V=0 ，意味着是空的(unmapped)
    .zero 8 * 511
    # 设置最后一个页表项，PPN=0x80000，标志位 VRWXAD 均为 1
    .quad (0x80000 << 10) | 0xcf # VRWXAD

    .global boot_hartid
boot_hartid:
    .quad 0
    .global boot_dtb
boot_dtb:
    .quad 0

总结一下，要进入虚拟内存访问方式，需要如下步骤：

  1. 分配页表所在内存空间并初始化页表；
  2. 设置好页基址寄存器（指向页表起始地址）；
  3. 刷新 TLB。

到现在为止，看上去复杂无比的虚拟内存空间，我们终于得以窥视一二了。

物理内存管理的设计思路

物理内存管理的实现

在管理虚拟内存之前，我们首先需要能够管理物理内存，毕竟所有虚拟内存页都要对应到物理内存页才能使用。

不妨把我们的内存管理模块划分为物理内存管理和虚拟内存管理两个模块。

物理内存管理应当为虚拟内存管理提供这样的接口：

  • 检查当前还有多少空闲的物理页，返回空闲的物理页数目
  • 给出n，尝试分配n个物理页，可以返回一个起始地址和连续的物理页数目，也可能分配一些零散的物理页，返回一个连起来的链表。
  • 给出起始地址和n，释放n个连续的物理页

在kern_init()里，我们调用一个新函数：pmm_init()，kern_init()函数我们在之前就有学习过，这里我们只是新增一个调用pmm_init()的接口。

// kern/init/init.c
int kern_init(void) {
    extern char edata[], end[];
    memset(edata, 0, end - edata);
    dtb_init();
    cons_init();  // init the console
    const char *message = "(THU.CST) os is loading ...\0";
    //cprintf("%s\n\n", message);
    cputs(message);
    print_kerninfo();
    // grade_backtrace();
    pmm_init();  // init physical memory management
    /* do nothing */
    while (1)
        ;
}

那么pmm_init()究竟是用来干什么的呢？其实pmm_init()主要就是用来主要负责初始化物理内存管理，我们可以在pmm.c文件进行初始化操作。

// kern/mm/pmm.c
/* pmm_init - initialize the physical memory management */
void pmm_init(void) {
    // We need to alloc/free the physical memory (granularity is 4KB or other size).
    // So a framework of physical memory manager (struct pmm_manager)is defined in pmm.h
    // First we should init a physical memory manager(pmm) based on the framework.
    // Then pmm can alloc/free the physical memory.
    init_pmm_manager();

    // detect physical memory space, reserve already used memory,
    // then use pmm->init_memmap to create free page list
    page_init();

    // use pmm->check to verify the correctness of the alloc/free function in a pmm
    check_alloc_page();

    extern char boot_page_table_sv39[]; //我们把汇编里定义的页表所在位置的符号声明进来
    satp_virtual = (pte_t*)boot_page_table_sv39;
    satp_physical = PADDR(satp_virtual);//然后输出页表所在的地址
    cprintf("satp virtual address: 0x%016lx\nsatp physical address: 0x%016lx\n", satp_virtual, satp_physical);
}

check_alloc_page()是对物理内存分配功能的一个测试。我们重点关注page_init()

我们在lab2增加了一些功能，方便我们编程：

  • libs/list.h：定义了通用双向链表结构以及相关的查找、插入等基本操作，这是建立基于链表方法的物理内存管理（以及其他内核功能）的基础。其他有类似双向链表需求的内核功能模块可直接使用 list.h 中定义的函数。

list.h里面实现了一个简单的双向链表。虽然接口很多，但是只要对链表熟悉，不难理解。如果理解不了，可以先去学学数据结构这门课。

// libs/list.h
struct list_entry {
    struct list_entry *prev, *next;
};

typedef struct list_entry list_entry_t;

static inline void list_init(list_entry_t *elm) __attribute__((always_inline));
static inline void list_add(list_entry_t *listelm, list_entry_t *elm) __attribute__((always_inline));
static inline void list_add_before(list_entry_t *listelm, list_entry_t *elm) __attribute__((always_inline));
static inline void list_add_after(list_entry_t *listelm, list_entry_t *elm) __attribute__((always_inline));
static inline void list_del(list_entry_t *listelm) __attribute__((always_inline));
static inline void list_del_init(list_entry_t *listelm) __attribute__((always_inline));
static inline bool list_empty(list_entry_t *list) __attribute__((always_inline));
static inline list_entry_t *list_next(list_entry_t *listelm) __attribute__((always_inline));
static inline list_entry_t *list_prev(list_entry_t *listelm) __attribute__((always_inline));
//下面两个函数仅在内部使用，不对外开放作为接口。
static inline void __list_add(list_entry_t *elm, list_entry_t *prev, list_entry_t *next) __attribute__((always_inline));
static inline void __list_del(list_entry_t *prev, list_entry_t *next) __attribute__((always_inline));

看起来list.h里面定义的list_entry并没有数据域，但是，如果我们把list_entry作为其他结构体的成员，就可以利用C语言结构体内存连续布局的特点，从`list_entry的地址获得它所在的上一级结构体。

于是我们定义了可以连成链表的Page结构体和一系列对它做操作的宏。这个结构体用来管理物理内存。此时，page_link 就是 list_entry 类型的节点，它把一批 Page 串起来形成空闲链表。但是当我们在链表中遍历时，手里只有 list_entry*，要怎么拿到它对应的 Page* 呢？

这里就用到了 le2page 宏。它的作用是，给定 list_entry* le，以及 member = page_link，利用 to_struct 宏，从 le 的地址向前偏移，得到 Page 结构体的首地址，最终返回 Page*。这种技巧本质上是 “container_of” 的用法（Linux 内核里大量使用），即从结构体中的某个成员指针，反推出整个结构体指针。

// libs/defs.h

/* Return the offset of 'member' relative to the beginning of a struct type */
#define offsetof(type, member)                                      \
    ((size_t)(&((type *)0)->member))

/* *
 * to_struct - get the struct from a ptr
 * @ptr:    a struct pointer of member
 * @type:   the type of the struct this is embedded in
 * @member: the name of the member within the struct
 * */
#define to_struct(ptr, type, member)                               \
    ((type *)((char *)(ptr) - offsetof(type, member)))

// kern/mm/memlayout.h
/* *
 * 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 physical address.
 * */
struct Page {
    int ref;                 // page frame's reference counter
    uint64_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 describing the status of a page frame */
#define PG_reserved                 0       // if this bit=1: the Page is reserved for kernel, cannot be used in alloc/free_pages; otherwise, this bit=0
#define PG_property                 1       // if this bit=1: the Page is the head page of a free memory block(contains some continuous_addrress pages), and can be used in alloc_pages; if this bit=0: if the Page is the the head page of a free memory block, then this Page and the memory block is alloced. Or this Page isn't the head page.
//这几个对page操作的宏用到了atomic.h的原子操作
#define SetPageReserved(page)       set_bit(PG_reserved, &((page)->flags))
#define ClearPageReserved(page)     clear_bit(PG_reserved, &((page)->flags))
#define PageReserved(page)          test_bit(PG_reserved, &((page)->flags))
#define SetPageProperty(page)       set_bit(PG_property, &((page)->flags))
#define ClearPageProperty(page)     clear_bit(PG_property, &((page)->flags))
#define PageProperty(page)          test_bit(PG_property, &((page)->flags))

// convert list entry to page
#define le2page(le, member)                 \
    to_struct((le), struct Page, member)

/* 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;

我们知道，物理内存通常是一片 RAM ，我们可以把它看成一个以字节为单位的大数组，通过物理地址找到对应的位置进行读写。但是，物理地址并不仅仅只能访问物理内存，也可以用来访问其他的外设，因此你也可以认为物理内存也算是一种外设。

这样设计是因为：如果访问其他外设要使用不同的指令（如 x86 单独提供了in, out 指令来访问不同于内存的IO地址空间），会比较麻烦，于是很多 CPU（如 RISC-V，ARM，MIPS 等）通过 MMIO(Memory Mapped I/O) 技术将外设映射到一段物理地址，这样我们访问其他外设就和访问物理内存一样啦！

我们先不管那些外设，目前我们只关注物理内存。

物理内存探测

操作系统怎样知道物理内存所在的那段物理地址呢？在 RISC-V 中，这个一般是由 bootloader ，即 OpenSBI 来完成的。它来完成对于包括物理内存在内的各外设的扫描，将扫描结果以 DTB(Device Tree Blob) 的格式保存在物理内存中的某个地方。随后 OpenSBI 会将其地址保存在 a1 寄存器中，给我们使用。

这个扫描结果描述了所有外设的信息，当中也包括 Qemu 模拟的 RISC-V 计算机中的物理内存。

扩展 Qemu 模拟的 RISC-V virt 计算机中的物理内存

通过查看virt.c的virt_memmap[]的定义，可以了解到 Qemu 模拟的 RISC-V virt 计算机的详细物理内存布局。可以看到，整个物理内存中有不少内存空洞（即含义为unmapped的地址空间），也有很多外设特定的地址空间，现在我们看不懂没有关系，后面会慢慢涉及到。目前只需关心最后一块含义为DRAM的地址空间，这就是 OS 将要管理的 128MB 的内存空间。

起始地址终止地址含义
0x00x100QEMU VIRT_DEBUG
0x1000x1000unmapped
0x10000x12000QEMU MROM (包括 hard-coded reset vector; device tree)
0x120000x100000unmapped
0x1000000x101000QEMU VIRT_TEST
0x1010000x2000000unmapped
0x20000000x2010000QEMU VIRT_CLINT
0x20100000x3000000unmapped
0x30000000x3010000QEMU VIRT_PCIE_PIO
0x30100000xc000000unmapped
0xc0000000x10000000QEMU VIRT_PLIC
0x100000000x10000100QEMU VIRT_UART0
0x100001000x10001000unmapped
0x100010000x10002000QEMU VIRT_VIRTIO
0x100020000x20000000unmapped
0x200000000x24000000QEMU VIRT_FLASH
0x240000000x30000000unmapped
0x300000000x40000000QEMU VIRT_PCIE_ECAM
0x400000000x80000000QEMU VIRT_PCIE_MMIO
0x800000000x88000000DRAM 缺省 128MB，大小可配置

那么我们就可以很方便的从a1寄存器中读取设备树数据存储地址，在kern_entry的开头将设备树数据从a1寄存器中读取出来，并存入全局变量boot_dtb中（顺便读取了当前cpu核心号）

# kern\init\entry.S
# a0: hartid
# a1: dtb physical address
# save hartid and dtb address
la t0, boot_hartid
sd a0, 0(t0)
la t0, boot_dtb

在kern_entry部分的初始化结束，我们正式进入到kern_init之后，会执行dtb_init函数来读取设备树结构中储存的相关信息。对设备树结构感兴趣的可以点击链接了解

// kern\init\init.c
int kern_init(void) {
    extern char edata[], end[];
    // 先清零 BSS，再读取并保存 DTB 的内存信息，避免被清零覆盖（为了解释变化 正式上传时我觉得应该删去这句话）
    memset(edata, 0, end - edata);
    dtb_init();
    // 其他初始化
}
// kern\driver\dtb.c
// 保存解析出的系统物理内存信息
static uint64_t memory_base = 0;
static uint64_t memory_size = 0;

void dtb_init(void) {
    cprintf("DTB Init\n");
    cprintf("HartID: %ld\n", boot_hartid);
    cprintf("DTB Address: 0x%lx\n", boot_dtb);

    if (boot_dtb == 0) {
        cprintf("Error: DTB address is null\n");
        return;
    }

    // 转换为虚拟地址
    uintptr_t dtb_vaddr = boot_dtb + PHYSICAL_MEMORY_OFFSET;
    const struct fdt_header *header = (const struct fdt_header *)dtb_vaddr;

    // 验证DTB
    uint32_t magic = fdt32_to_cpu(header->magic);
    if (magic != 0xd00dfeed) {
        cprintf("Error: Invalid DTB magic number: 0x%x\n", magic);
        return;
    }

    // 提取内存信息
    uint64_t mem_base, mem_size;
    if (extract_memory_info(dtb_vaddr, header, &mem_base, &mem_size) == 0) {
        cprintf("Physical Memory from DTB:\n");
        cprintf("  Base: 0x%016lx\n", mem_base);
        cprintf("  Size: 0x%016lx (%ld MB)\n", mem_size, mem_size / (1024 * 1024));
        cprintf("  End:  0x%016lx\n", mem_base + mem_size - 1);
        // 保存到全局变量，供 PMM 查询
        memory_base = mem_base;
        memory_size = mem_size;
    } else {
        cprintf("Warning: Could not extract memory info from DTB\n");
    }
    cprintf("DTB init completed\n");
}

由此，我们就已经将内存的起点和大小读取到了全局变量memory_base和memory_size中，我们会在物理内存管理初始化的时候用到这些信息

// kern\mm\pmm.c
void pmm_init(void) {
    // other things
    page_init();
    // other things
}
static void page_init(void) {
    va_pa_offset = PHYSICAL_MEMORY_OFFSET;

    uint64_t mem_begin = get_memory_base();
    uint64_t mem_size  = get_memory_size();
    if (mem_size == 0) {
        panic("DTB memory info not available");
    }
    uint64_t mem_end   = mem_begin + mem_size;

    cprintf("physcial memory map:\n");
    cprintf("  memory: 0x%016lx, [0x%016lx, 0x%016lx].\n", mem_size, mem_begin,
            mem_end - 1);

    uint64_t maxpa = mem_end;

    if (maxpa > KERNTOP) {
        maxpa = KERNTOP;
    }

    extern char end[];

    npage = maxpa / PGSIZE;
    pages = (struct Page *)ROUNDUP((void *)end, PGSIZE);

    for (size_t i = 0; i < npage - nbase; i++) {
        SetPageReserved(pages + i);
    }

    uintptr_t freemem = PADDR((uintptr_t)pages + sizeof(struct Page) * (npage - nbase));

    mem_begin = ROUNDUP(freemem, PGSIZE);
    mem_end = ROUNDDOWN(mem_end, PGSIZE);
    if (freemem < mem_end) {
        init_memmap(pa2page(mem_begin), (mem_end - mem_begin) / PGSIZE);
    }
}

Qemu 规定的 DRAM 物理内存的起始物理地址为 0x80000000 。而在 Qemu 中，可以使用 -m 指定 RAM 的大小，默认是 128MiB 。因此，默认的 DRAM 物理内存地址范围就是 [0x80000000,0x88000000) 。

但是，有一部分 DRAM 空间已经被占用，不能用来存别的东西了！

  • 物理地址空间 [0x80000000,0x80200000) 被 OpenSBI 占用；
  • 物理地址空间 [0x80200000,KernelEnd) 被内核各代码与数据段占用；
  • 其实设备树扫描结果 DTB 还占用了一部分物理内存，不过我们目前只在初始化的时读取其中的内存起点和长度信息，所以之后可以将它所占用的空间用来存别的东西。

于是，我们可以用来存别的东西的物理内存的物理地址范围是：[KernelEnd, 0x88000000) 。这里的 KernelEnd 为内核代码结尾的物理地址。在 kernel.ld 中定义的 end 符号为内核代码结尾的虚拟地址。

为了管理物理内存，我们需要在内核里定义一些数据结构，来存储”当前使用了哪些物理页面，哪些物理页面没被使用“这样的信息，使用的是Page结构体。我们将一些Page结构体在内存里排列在内核后面，这要占用一些内存。而摆放这些Page结构体的物理页面，以及内核占用的物理页面，之后都无法再使用了。我们用page_init()函数给这些管理物理内存的结构体做初始化。下面是代码：

// kern/mm/pmm.h

/* *
 * PADDR - takes a kernel virtual address (an address that points above
 * KERNBASE),
 * where the machine's maximum 256MB of physical memory is mapped and returns
 * the
 * corresponding physical address.  It panics if you pass it a non-kernel
 * virtual address.
 * */
#define PADDR(kva)                                                 \
    ({                                                             \
        uintptr_t __m_kva = (uintptr_t)(kva);                      \
        if (__m_kva < KERNBASE) {                                  \
            panic("PADDR called with invalid kva %08lx", __m_kva); \
        }                                                          \
        __m_kva - va_pa_offset;                                    \
    })

/* *
 * KADDR - takes a physical address and returns the corresponding kernel virtual
 * address. It panics if you pass an invalid physical address.
 * */
/*
#define KADDR(pa)                                                \
    ({                                                           \
        uintptr_t __m_pa = (pa);                                 \
        size_t __m_ppn = PPN(__m_pa);                            \
        if (__m_ppn >= npage) {                                  \
            panic("KADDR called with invalid pa %08lx", __m_pa); \
        }                                                        \
        (void *)(__m_pa + va_pa_offset);                         \
    })
*/
extern struct Page *pages;
extern size_t npage;

// kern/mm/pmm.c

// pages指针保存的是第一个Page结构体所在的位置，也可以认为是Page结构体组成的数组的开头
// 由于C语言的特性，可以把pages作为数组名使用，pages[i]表示顺序排列的第i个结构体
struct Page *pages;
size_t npage = 0;
uint64_t va_pa_offset;
// memory starts at 0x80000000 in RISC-V
const size_t nbase = DRAM_BASE / PGSIZE;
//(npage - nbase)表示物理内存的页数

static void page_init(void) {
    va_pa_offset = PHYSICAL_MEMORY_OFFSET; //硬编码 0xFFFFFFFF40000000

    uint64_t mem_begin = KERNEL_BEGIN_PADDR;//硬编码 0x80200000
    uint64_t mem_size = PHYSICAL_MEMORY_END - KERNEL_BEGIN_PADDR;
    uint64_t mem_end = PHYSICAL_MEMORY_END; //硬编码 0x88000000

    cprintf("physcial memory map:\n");
    cprintf("  memory: 0x%016lx, [0x%016lx, 0x%016lx].\n", mem_size, mem_begin,
            mem_end - 1);

    uint64_t maxpa = mem_end;

    if (maxpa > KERNTOP) {
        maxpa = KERNTOP;
    }

    npage = maxpa / PGSIZE;

    extern char end[];
    pages = (struct Page *)ROUNDUP((void *)end, PGSIZE);
    //把pages指针指向内核所占内存空间结束后的第一页

    //一开始把所有页面都设置为保留给内核使用的，之后再设置哪些页面可以分配给其他程序
    for (size_t i = 0; i < npage - nbase; i++) {
        SetPageReserved(pages + i);//记得吗？在kern/mm/memlayout.h定义的
    }
    //从这个地方开始才是我们可以自由使用的物理内存
    uintptr_t freemem = PADDR((uintptr_t)pages + sizeof(struct Page) * (npage - nbase));
    //按照页面大小PGSIZE进行对齐, ROUNDUP, ROUNDDOWN是在libs/defs.h定义的
    mem_begin = ROUNDUP(freemem, PGSIZE);
    mem_end = ROUNDDOWN(mem_end, PGSIZE);
    if (freemem < mem_end) {
        //初始化我们可以自由使用的物理内存
        init_memmap(pa2page(mem_begin), (mem_end - mem_begin) / PGSIZE);
    }
}

在page_init()的代码里，我们调用了一个函数init_memmap(), 这和我们的另一个结构体pmm_manager有关。虽然C语言基本上不支持面向对象，但我们可以用类似面向对象的思路，把”物理内存管理“的功能集中给一个结构体。我们甚至可以让函数指针作为结构体的成员，强行在C语言里支持了”成员函数“。可以看到，我们调用的init_memmap()实际上又调用了pmm_manager的一个”成员函数“。

// kern/mm/pmm.c

// physical memory management
const struct pmm_manager *pmm_manager;


// init_memmap - call pmm->init_memmap to build Page struct for free memory
static void init_memmap(struct Page *base, size_t n) {
    pmm_manager->init_memmap(base, n);
}

// kern/mm/pmm.h
#ifndef __KERN_MM_PMM_H__
#define __KERN_MM_PMM_H__

#include <assert.h>
#include <atomic.h>
#include <defs.h>
#include <memlayout.h>
#include <mmu.h>
#include <riscv.h>

// pmm_manager is a physical memory management class. A special pmm manager -
// XXX_pmm_manager
// only needs to implement the methods in pmm_manager class, then
// XXX_pmm_manager can be used
// by ucore to manage the total physical memory space.
struct pmm_manager {
    const char *name;  // XXX_pmm_manager's name
    void (*init)(
        void);  // 初始化XXX_pmm_manager内部的数据结构（如空闲页面的链表）
    void (*init_memmap)(
        struct Page *base,
        size_t n);  //知道了可用的物理页面数目之后，进行更详细的初始化
    struct Page *(*alloc_pages)(
        size_t n);  // 分配至少n个物理页面, 根据分配算法可能返回不同的结果
    void (*free_pages)(struct Page *base, size_t n);  // free >=n pages with
                                                      // "base" addr of Page
                                                      // descriptor
                                                      // structures(memlayout.h)
    size_t (*nr_free_pages)(void);  // 返回空闲物理页面的数目
    void (*check)(void);            // 测试正确性
};

extern const struct pmm_manager *pmm_manager;

void pmm_init(void);

struct Page *alloc_pages(size_t n);
void free_pages(struct Page *base, size_t n);
size_t nr_free_pages(void); // number of free pages

#define alloc_page() alloc_pages(1)
#define free_page(page) free_pages(page, 1)

pmm_manager提供了各种接口：分配页面，释放页面，查看当前空闲页面数。但是我们好像始终没看见pmm_manager内部对这些接口的实现，其实是因为那些接口只是作为函数指针，作为pmm_manager的一部分，我们需要把那些函数指针变量赋值为真正的函数名称。

还记得最早我们在pmm_init()里首先调用了init_pmm_manager(), 在这里面我们把pmm_manager的指针赋值成&default_pmm_manager， 看起来我们在这里实现了那些接口。

// init_pmm_manager - initialize a pmm_manager instance
static void init_pmm_manager(void) {
    pmm_manager = &default_pmm_manager;
    cprintf("memory management: %s\n", pmm_manager->name);
    pmm_manager->init();
}
// alloc_pages - call pmm->alloc_pages to allocate a continuous n*PAGESIZE
// memory
struct Page *alloc_pages(size_t n) {
    // 在这里编写你的物理内存分配算法。
    // 你可以参考nr_free_pages() 函数进行设计，
    // 了解物理内存管理器的工作原理，然后在这里实现自己的分配算法。
    // 实现算法后，调用 pmm_manager->alloc_pages(n) 来分配物理内存，
    // 然后返回分配的 Page 结构指针。
}

// free_pages - call pmm->free_pages to free a continuous n*PAGESIZE memory
void free_pages(struct Page *base, size_t n) {
    // 在这里编写你的物理内存释放算法。
    // 你可以参考nr_free_pages() 函数进行设计，
    // 了解物理内存管理器的工作原理，然后在这里实现自己的释放算法。
    // 实现算法后，调用 pmm_manager->free_pages(base, n) 来释放物理内存。
}

// nr_free_pages - call pmm->nr_free_pages to get the size (nr*PAGESIZE)
// of current free memory
size_t nr_free_pages(void) {
    return pmm_manager->nr_free_pages();
}

到现在，我们距离完整的内存管理， 就只差default_pmm_manager结构体的实现了，也就是我们要在里面实现页面分配算法。

页面分配算法

我们在default_pmm.c定义了一个pmm_manager类型的结构体，并实现它的接口

// kern/mm/default_pmm.h
#ifndef __KERN_MM_DEFAULT_PMM_H__
#define  __KERN_MM_DEFAULT_PMM_H__

#include <pmm.h>

extern const struct pmm_manager default_pmm_manager;

#endif /* ! __KERN_MM_DEFAULT_PMM_H__ */

较为关键的，是一开始如何初始化所有可用页面，以及如何分配和释放页面。大家可以学习下面的代码，其实现了First Fit算法。

// kern/mm/default_pmm.c
free_area_t free_area;

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

static void
default_init(void) {
    list_init(&free_list);
    nr_free = 0;//nr_free可以理解为在这里可以使用的一个全局变量，记录可用的物理页面数
}
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;
    if (list_empty(&free_list)) {
        list_add(&free_list, &(base->page_link));
    } else {
        list_entry_t* le = &free_list;
        while ((le = list_next(le)) != &free_list) {
            struct Page* page = le2page(le, page_link);
            if (base < page) {
                list_add_before(le, &(base->page_link));
                break;
            } else if (list_next(le) == &free_list) {
                list_add(le, &(base->page_link));
            }
        }
    }
}

static struct Page *
default_alloc_pages(size_t n) {
    assert(n > 0);
    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_entry_t* prev = list_prev(&(page->page_link));
        list_del(&(page->page_link));
        if (page->property > n) {
            struct Page *p = page + n;
            p->property = page->property - n;
            SetPageProperty(p);
            list_add(prev, &(p->page_link));
        }
        nr_free -= n;
        ClearPageProperty(page);
    }
    return page;
}
static void
default_free_pages(struct Page *base, size_t n) {
    assert(n > 0);
    struct Page *p = base;
    for (; p != base + n; p ++) {
        assert(!PageReserved(p) && !PageProperty(p));
        p->flags = 0;
        set_page_ref(p, 0);
    }
    base->property = n;
    SetPageProperty(base);
    nr_free += n;

    if (list_empty(&free_list)) {
        list_add(&free_list, &(base->page_link));
    } else {
        list_entry_t* le = &free_list;
        while ((le = list_next(le)) != &free_list) {
            struct Page* page = le2page(le, page_link);
            if (base < page) {
                list_add_before(le, &(base->page_link));
                break;
            } else if (list_next(le) == &free_list) {
                list_add(le, &(base->page_link));
            }
        }
    }

    list_entry_t* le = list_prev(&(base->page_link));
    if (le != &free_list) {
        p = le2page(le, page_link);
        if (p + p->property == base) {
            p->property += base->property;
            ClearPageProperty(base);
            list_del(&(base->page_link));
            base = p;
        }
    }

    le = list_next(&(base->page_link));
    if (le != &free_list) {
        p = le2page(le, page_link);
        if (base + base->property == p) {
            base->property += p->property;
            ClearPageProperty(p);
            list_del(&(p->page_link));
        }
    }
}

const struct pmm_manager default_pmm_manager = {
    .name = "default_pmm_manager",
    .init = default_init,
    .init_memmap = default_init_memmap,
    .alloc_pages = default_alloc_pages,
    .free_pages = default_free_pages,
    .nr_free_pages = default_nr_free_pages,
    .check = default_check,
};

所谓First Fit算法就是当需要分配页面时，它会从空闲页块链表中找到第一个适合大小的空闲页块，然后进行分配。当释放页面时，它会将释放的页面添加回链表，并在必要时合并相邻的空闲页块，以最大限度地减少内存碎片。

完成页面分配算法后我们的物理内存管理算是基本实现了，接下来请同学们完成本次实验练习。

问题

根据提供的实验文档《实验整理2.md》，我将作为助教，从三个层次提出问题和解答，以检验学生对物理内存管理核心概念、实现细节和原理的理解。以下问题与解答均基于文档内容，并适当扩展。

第一部分：基础概念理解题

1. 虚拟地址与物理地址

  • 为什么引入虚拟地址？直接访问物理地址的问题？
    直接访问物理地址会导致多个程序冲突，例如内核和用户程序可能访问相同的物理地址（如0x80200000），造成数据破坏。此外，物理内存容易碎片化，程序需要连续内存空间才能运行，但碎片化后即使总内存足够，也无法分配连续空间。虚拟地址通过页表“翻译”机制，为每个程序提供独立的虚拟地址空间，避免了冲突，并允许使用不连续的物理内存，提高了灵活性和安全性。

  • sv39中虚拟地址和物理地址的页内偏移相同说明了什么？
    这表明页大小固定为4KB（4096字节），且页内偏移（低12位）在虚拟地址和物理地址中保持一致。这意味着页翻译只改变页号部分，页内偏移直接复制，要求物理页和虚拟页都必须按4KB对齐，即页起始地址是4096的倍数。

3. 页表项 (PTE)

  • V位的作用？如果V=0会发生什么？
    V位表示页表项是否合法。如果V=0，表示该虚拟页未映射到物理页，CPU访问时会触发页错误异常（page fault），操作系统需要处理该异常。

  • 如何通过R/W/X位区分PTE指向下一级页表还是物理页帧？
    根据文档中的表格，当R=0、W=0、X=0时，PTE指向下一级页表；否则，它指向一个物理页帧（如R=1表示可读，W=1表示可写，X=1表示可执行）。

  • A位和D位由谁设置？对内存管理有什么帮助？
    A位（Accessed）和D位（Dirty）由CPU硬件自动设置。A位在页被访问（读/写/取指）时设置，D位在页被写入时设置。它们帮助操作系统实现页面置换算法：A位可用于识别最近未使用的页（用于换出），D位可用于识别需要写回磁盘的脏页（减少I/O操作）。

2. 多级页表

  • 单级页表占用1 GiB如何计算？
    sv39虚拟地址有39位，其中低12位是页内偏移，因此虚拟页号有27位。每个页表项（PTE）占8字节，因此单级页表大小为 (2^{27} \times 8 = 2^{30}) 字节 = 1 GiB。

  • 多级页表如何解决空间问题？利用了程序的什么特性？
    多级页表通过树状结构只分配实际使用的页表项，而不是为所有虚拟页号分配项。它利用了程序的“局部性”特性：程序通常只使用部分虚拟地址空间，大部分虚拟页未使用，因此多级页表可以大幅减少内存占用。

  • 一个4KiB页存放多少个PTE？如何影响虚拟地址划分？
    一个4KiB页（4096字节）存放512个PTE，因为 (4096 / 8 = 512)。这决定了虚拟地址划分：9位用于第一级页表索引（(2^9=512)），9位用于第二级，9位用于第三级，12位用于页内偏移，形成9-9-9-12的结构。

4. TLB (快表)

  • 地址翻译为什么需要3次内存访问？TLB如何降低开销？
    sv39三级页表需要三次内存访问：第一级页表、第二级页表、第三级页表。TLB（Translation Lookaside Buffer）是硬件缓存，存储最近使用的虚拟页到物理页的映射。如果TLB命中，则直接获取物理地址，避免三次内存访问，大幅提高效率。

  • sfence.vma指令的作用？在哪个环节必须使用？
    sfence.vma指令用于刷新TLB，确保地址翻译使用最新的页表内容。在修改页表（如添加、删除或更新PTE）后必须使用，例如在进程切换或页表更新时，否则旧的TLB条目可能导致错误翻译。

第二部分：实现细节与代码分析题

1. 内核启动与地址空间建立 (entry.S)

  • 修改BASE_ADDRESS后原版entry.S为什么失效？CPU会跳转到哪个错误地址？
    原版entry.S直接使用虚拟地址跳转，但页表未设置时，CPU会误将虚拟地址当作物理地址访问。例如，如果BASE_ADDRESS设置为0x80200000，CPU会跳转到物理地址0x80200000，但该地址可能无有效代码，导致崩溃。

  • 如何计算boot_page_table_sv39的物理地址并写入satp？解释sub t0, t0, t1
    在entry.S中，通过la t0, boot_page_table_sv39加载虚拟地址，但需要物理地址写入satp。sub t0, t0, t1用于计算物理地址偏移，其中t0是虚拟地址，t1是虚拟地址和物理地址的偏移量（如BASE_ADDRESS），结果t0为物理地址，然后写入satp。

  • 解析boot_page_table_sv39的最后一个页表项：.quad (0x80000 << 10) | 0xcf

    • 0x80000是物理页号（PPN），表示内核起始物理地址（0x80000页）。
    • << 10是因为PPN在PTE中占据位53-10，左移10位将页号对齐到正确位置。
    • 0xcf是标志位：二进制11001111，对应V=1（合法）、R=1（可读）、W=1（可写）、X=1（可执行）、A=0、D=0等。这表示该PTE映射一个大页（1GiB），直接指向内核物理地址。

2. 物理内存管理框架 (pmm.c)

  • struct Page数组存放在物理内存的什么位置？page_init如何确定？
    struct Page数组通常存放在物理内存的末尾或开头，由page_init函数根据内存探测结果（如设备树或BIOS信息）确定。例如，从可用物理内存区域中分配一段空间来存储Page数组，并避免与内核代码冲突。

  • le2page宏如何通过list_entry_t指针找到struct Page？
    le2page宏利用“容器of”技巧：list_entry_t是struct Page的成员（如page_link），通过计算成员在结构体中的偏移量，从成员指针反推结构体起始地址。例如：#define le2page(le, member) to_struct((le), struct Page, member)，其中to_struct计算偏移。

3. First Fit 页面分配算法 (default_pmm.c)

  • default_alloc_pages中如何处理大于n的空闲块？描述拆分过程。
    当找到大于n的空闲块时，算法会拆分该块：分配n页，将剩余部分（大小原块减n）重新插入空闲链表。例如，如果空闲块有10页，需求n=3，则分配3页，剩余7页作为一个新块放回链表。

  • default_free_pages中为什么合并相邻空闲块？不合并的影响？
    合并相邻空闲块防止外部碎片化。如果不合并，空闲链表会包含多个小碎片，无法满足大块内存请求，导致分配失败即使总内存足够。

第三部分：综合与拓展思考题

1. 大页映射

  • 使用大页的好处和适用场景？
    大页（如1GiB）减少页表级数和TLB缺失率，提高地址翻译效率。适用于需要大量连续内存访问的场景，如数据库、科学计算或虚拟化，其中内存访问模式具有空间局部性。

2. 地址空间隔离

  • 进程切换时对satp寄存器的操作？
    进程切换时，操作系统将新进程的页表物理地址写入satp寄存器，并执行sfence.vma刷新TLB。这确保新进程使用自己的地址空间，实现隔离。

3. 内存管理算法权衡

  • First Fit vs Best Fit/Worst Fit的优缺点？在实验中的合理性？
    • First Fit：简单快速，但可能产生外部碎片。
    • Best Fit：减少碎片，但搜索慢。
    • Worst Fit：试图减少小碎片，但性能差。
      在实验中，First Fit合理因为实现简单，且内存需求不大，碎片问题不显著。

4. 健壮性思考

  • 设备树信息有误时page_init的表现？如何增强健壮性？
    如果设备树信息有误，page_init可能错误初始化内存，导致系统崩溃。增强健壮性的方法：
    • 添加备用内存探测机制（如BIOS调用或硬编码默认值）。
    • 验证内存范围是否合理（如检查地址是否在预期范围内）。
    • 使用内存测试（如读写测试）确认可用内存区域。

这些问题覆盖了实验的核心内容，帮助学生深入理解物理内存管理的原理和实现。作为助教，可以根据学生的回答进一步探讨细节。

关系图谱