# Lab 7: MM

负责助教：[肖德](mailto:dxiao21@m.fudan.edu.cn)

本次实验为初步了解一些用户态程序的内存管理功能。包括修改程序堆的大小、Lazy Allocation 和 Copy on Write。

## 1. 基础知识

### 1.1. ELF格式和段

ELF 是一种用于二进制文件、可执行文件等文件的文件格式，是 Linux 的主要可执行文件格式。ELF 格式将可执行文件分成几个不同的`section`，一个程序主要由 `anonymous` 段和 `file-backed` 段组成：

* **`anonymous`段**：执行时才会创建的段，可执行文件本身不包含，比如`bss`（减少文件大小）、`stack`（执行时才能确定其中的内容）。
* **`file-backed` 段**：可执行文件本身就拥有的段，比如`text`（可执行文件的代码段）、`data`（已初始化的数据段）。

其中从 `text` 到 `stack`，对应的虚拟地址一般是逐渐增加的（见下图）。我们可以通过 `size` 命令查看一个可执行文件的各个段的大小。

<figure><img src="https://16109260-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F0Ys7ueu56dsZqVUfbMN7%2Fuploads%2FOSdjmYVqUCU1QmzCjF4s%2F12181733417620_.pic.jpg?alt=media&#x26;token=db308f8c-9cf0-4b70-857a-d8cd4dfc1900" alt=""><figcaption></figcaption></figure>

我们实验中同样采用段（`struct section`对应于上图中的`vm_area_struct`）的数据结构来标识一个可执行文件在执行时拥有的各类段的信息。

### 1.2. 虚拟内存

虚拟内存机制有如下特性：

* **隔离性**：虚拟内存使得操作系统可以为每个应用程序提供属于它们自己的地址空间，所以一个应用程序不可能有意或者无意的修改另一个应用程序的内存数据，我们在进行本次实验时也需要保证这一点。
* **抽象性**：进程运行时用虚拟地址，而内核会定义从虚拟地址到物理地址的映射关系，因此进程的运行就无需关注和管理对应的物理内存，这是我们这节课要讨论的许多有趣功能的基础。
* **灵活性**：目前的内存映射都是静态的，即我们初次配置完页表后，以后不会再修改页表中映射关系。前面我们提到，AArch64 存在多张页表，分别用于不同的异常级别：
  * 内核态映射：即内核使用的页表。此页表已硬编码在框架代码中（`aarch64/kernel_pt.c`），后续也不会再修改。
  * 用户态映射：在先前的实验中，我们针特定测试（如 `userproc` 中的 `loop`）手动设置了用户页表，确保不会出现 Page Fault。

可以发现，前面的实验中，我们的（用户）页表都是静态的，即设置完成后不会在进程的生命周期内动态修改。然而，经过理论课的学习我们知道，许多重要的内存管理机制（如 Lazy Allocation，Copy on Write，Demand Paging 等）都依用户页表的动态更新。我们需要通过 Page Fault，引导内核更新页表，动态调整用户态进程的地址映射，提高系统内存的灵活性

{% hint style="info" %}
我们可以通过 `(h)top` 指令查看进程以及内存的使用情况（比如在 `top` 命令中，`VIRT` 表示的是虚拟内存地址空间的大小，`RES` 是实际占用的内存数量），我们发现进程的虚拟地址往往比他们拥有的多，倘若直接把所有的进程的虚拟地址都分配物理页的话，会大幅度降低内存利用率，这是动态分配内存的一个重要优点。
{% endhint %}

### 1.3. Page Fault

顾名思义，Page Fault 就是让用户进程在执行时触发异常，陷入到内核态进行处理，从而让内核动态地管理内存，而当内核处理 Page Fault 时，可能会用到如下信息：

* 引起 Page Fault 的内存地址（`far` 寄存器）
* 引起 Page Fault 的原因类型（`esr` 寄存器）
* 引起 Page Fault 程序计数器值（`elr` 寄存器）

借助 Page Fault，我们能够实现如下几个功能：

* Lazy Allocation
* Copy on Write
* Demand Paging (Final Lab)

#### Lazy Allocation

C语言中动态内存分配的基本函数是 `malloc`，在 Linux 上，`malloc` 实现通常会根据需要选择使用 `brk/sbrk` 或 `mmap` （涉及分配较大的块，映射文件或设备）系统调用来分配内存。这里我们主要关注 `sbrk` 系统调用。

```c
uint64
sys_sbrk(void)
{
  uint64 addr;
  int n;

  argint(0, &n);
  addr = myproc()->sz;
  if(growproc(n) < 0)
    return -1;
  return addr;
}
```

以上是 xv6 中 `sbrk`的实现，其中调用了 `growproc` 函数，直接分配给应用程序需要的物理内存。

直接分配会导致大量内存的的浪费，更好的做法是只增加段的 `size`，等到进程执行到对应地址时会触发 Page Fault，这时我们再调用 `kalloc_page` 申请物理页，并根据出错的虚拟地址（需要的信息）建立映射。

{% hint style="info" %}
虚拟内存中提到的**抽象性**：每个应用程序都觉得自己占有了全部的硬件资源（但实际上并不是），而且应用程序来说很难预测自己需要多少内存，所以通常来说，应用程序倾向于申请多于自己所需要的内存。
{% endhint %}

#### Copy on Write (Zero Fill On Demand)

我们先从一个比较简单的例子入手。我们知道，`BSS` 段包含了未被初始化或者初始化为 `0` 的全局变量。为了节省空间，可执行文件一般不包含这个其中的内容，只在其被执行时，内核才创建对应的内容。

`BSS` 段初始的内容全部为 `0`，同时每个进程又有 `BSS` 段，因此不难想到一个优化点：在物理内存中，分配一个 page，page 内容全是0，然后让所有虚拟地址空间的全 `0` 的 page 都映射到这一个物理 page 上，这样至少在程序启动的时候分配时节省大量的物理内存分配。

还记得之前提到的隔离性吗？不同进程的 `BSS` 段实际上是不能完全共享的，因此要注意不能写，也就是说对应的页表项必须设置为只读；因此，当进程尝试往 `BSS` 段写入数据时，会触发 Page Fault，此时我们应该如何处理？

> 创建一个新的 page，将其内容设置为 `0`，并重新执行指令（当然还要把页表项设为可读写）

当然有所得必有所失，不足之处在于每次写入都触发 Page Fault，而 Page Fault 涉及用户态和内核态的交互，试想一下原本只用配置 `BSS` 段一遍，如果运气不好的话， `BSS` 段中每页都要触发 Page Fault，这样的效率是很低的。

#### Copy on Write (Fork)

另外一种写时复制的应用场景，那就是 fork 时的 Copy on Write。

{% hint style="info" %}
当 shell 处理指令时，它会通过 fork 创建一个子进程。该子进程执行的第一件事情就是调用 `exec` 运行一些其他程序，而 `exec` 做的第一件事情就是丢弃自身地址空间，取而代之的是一个包含了要执行的文件的地址空间。
{% endhint %}

当我们用 fork 创建子进程时，可以不立刻创建、分配并拷贝内容到新的物理内存，而是先共享父进程的物理内存空间。

和 Zero Fill On Demand 的场景同样，一旦一个进程往对应的页面写入时应该怎么办？

> 创建一个新的 page，复制之前的内容，并重新执行指令（当然还要把页表项设为可读写）

当一个进程退出时需要怎么处理？

> 进程退出时会释放其所有的页面，但是，实际上该页面本身可能不能直接释放，因为其可能正在被多个进程使用，因此我们需要对 page 进行引用计数，当我们释放虚拟内存时，我们将 page 的引用数减 `1`，如果引用数等于 `0`，此时我们才能释放对应的物理内存。

```c
struct page {
    atomic_t count;
};
struct pages[page_total]; // 根据页面的物理地址找到所属的页面

kalloc_page: refcnt = 1
kfree_page: refcnt -= 1
```

## 2. 实验内容

有关的结构体：

```c
struct page {
    RefCount ref;
};
```

对于每个页面，我们记录它的引用数。当且仅当引用数为 `0` 时，页面应该被释放。

```c
struct section {
    u64 flags;
    u64 begin, end; // [begin, end)
    ListNode stnode;
};
```

对于程序的每个段，我们将它的起始地址、结束地址和 flags 记录在结构体中。

```c
struct pgdir {
    PTEntriesPtr pt;
    SpinLock lock;
    ListNode section_head;
}
```

然后将每个段的结构体以链表的形式连接起来，保存在进程的 `pgdir` 中。这样我们就能知道每个进程的每个段的区间。

所有的 Flags 如下：

```c
#define ST_FILE  1                  // File-backed
#define ST_SWAP  (1<<1)             // Unused, 如果你想写swap可以用
#define ST_RO    (1<<2)             // Read-only
#define ST_HEAP  (1<<3)             // Section is heap
#define ST_TEXT  (ST_FILE | ST_RO)  // Section is text
#define ST_DATA  ST_FILE            // Section is data
#define ST_BSS   ST_FILE            // Section is bss
```

## **3. 任务**

{% hint style="success" %}
**任务 1**：准备用户程序堆并实现 sbrk() 系统调用
{% endhint %}

**用户程序堆：**&#x6211;们需要在初始化进程时为进程创建一个初始大小为 `0` 的堆，并将该 `section` 记录在进程的 `pgdir` 中。堆的起始地址一般取决于用户程序内存空间 layout，但由于本次实验不涉及其他段，暂时可以随意制定一个（合法的）堆的起始地址。

**`sbrk()`系统调用**：该系统调用的功能是 Set Program Break，即设置进程的堆的终止位置。

{% hint style="warning" %}
本次实验中暂不需要在`SYSCALL_TABLE`中注册该系统调用
{% endhint %}

**函数模板**：

```c
u64 sbrk(i64 size);
```

* `size`：堆大小的增加量（字节），可以为负数。
* 返回值：原来（修改前）的堆终止位置的地址，如果参数非法则返回`-1`。

**实现思路：**&#x5F53;用户程序调用 `sbrk()` 时，我们需要将堆的终止位置增加 `size`，并返回修改前的堆终止位置的地址。我们将新的堆终止位置记录在 `section` 结构体中，并通过 Lazy Allocation 的方法来实现新的页的分配。

{% hint style="success" %}
**任务 2**：实现 Lazy Allocation 和 Copy on Write。
{% endhint %}

**Lazy Allocation**

{% hint style="warning" %}
在本实验中，我们只需要关注 heap 段。其他段会在后续实验中涉及。
{% endhint %}

1. 当用户程序调用 `sbrk()` 时，我们并不需要立即将新的页分配给用户进程，只须把新的 heap 终止位置记录到对应的 `section` 结构体中即可。
2. 这样，当用户程序访问到新的 heap 时，会触发缺页异常，我们在缺页异常处理程序中，判断缺页地址是否在 heap 中，如果是，说明应当是 Lazy Allocation 的情形。（这种判断方法是否严谨？）
3. 这时分配一个新的页，将这个页分配并映射给用户进程，再返回用户进程继续执行即可。
4. 如果不是，则这是一个非法内存访问，应该杀死用户进程并报错。
5. 特别注意，`sbrk()` 不仅可以增加 heap 的大小，还可以减小heap的大小（也可以不变）。减小时应该如何处理？

**Copy on Write**

{% hint style="warning" %}
在后续实验中，我们会在创建bss段和 `fork()` 时使用 Copy on Write。
{% endhint %}

1. 我们在系统启动时分配出来一个页，将其内容初始化为全零。我们将该页指定为共享全零页，每次有进程需要创建一个全零页时，我们创建一个到共享全零页的**只读**映射即可。需要保证该页永远不会被释放。
2. 如果进程需要对全零页进行**写入**操作时，会触发缺页异常。同样地，我们可以在缺页异常处理程序中判定这是否是 Copy on Write 的情形。
3. 如果是，我们分配一个新的页，将共享全零页的内容拷贝过去（也就是将新的页全设为零），然后将新页映射给用户进程，再返回用户进程继续执行即可。
4. 如果不是，则这是一个非法内存访问，应该杀死用户进程并报错。

**相关函数**

```c
int pgfault_handler(u64 iss) {
    struct proc *p = thisproc();
    struct pgdir *pd = &p->pgdir;
    u64 addr = arch_get_far(); // Attempting to access this address caused the page fault
    // TODO:
    // 1. Find the section struct that contains the faulting address `addr`
    // 2. Check section flags to determine page fault type
    // 3. Handle the page fault accordingly
    // 4. Return to user code or kill the process
}
```

这是缺页异常处理程序，在`trap_global_handler`中，我们需要判断trap是否是缺页异常，如果是，则交由这个函数处理。

```c
void vmmap(struct pgdir *pd, u64 va, void *ka, u64 flags) {
    // TODO
    // Map virtual address 'va' to the physical address represented by kernel
    // address 'ka' in page directory 'pd', 'flags' is the flags for the page
    // table entry
}
```

在`pd`中将虚拟地址`va`映射到内核地址`ka`对应的物理地址：

```c
WARN_RESULT void *get_zero_page() {
    // TODO
    // Return the shared zero page
}
```

返回共享全零页。

{% hint style="danger" %}
**特别提醒：**&#x4FEE;改页表后需要调用`arch_tlbi_vmalle1is()`以清空 TLB 。忘记清空 TLB 将引发难排查的 BUG 。
{% endhint %}