# Lab 1: Allocator

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

本实验中，我们将初步了解内核启动过程中对物理内存的初始化、内核启动后对物理内存的管理，并实现一个简单的物理内存分配器供后续使用。值得注意的是，从本实验开始，我们将考虑 SMP 架构下的并发问题。

## 1. 代码下载

运行以下命令进行代码的拉取与合并

```shell
# 拉取远端仓库
git fetch --all
# 提交你的更改
git add .
git commit -m "your commit message"
# 切换到新lab的分支
git checkout lab1
# 新建一个分支，用于开发
git checkout -b lab1-dev
# 引入你在上个lab的更改
git merge lab0-dev
```

如果合并发生冲突，请参考错误信息自行解决。

## 2. 物理内存管理

{% hint style="warning" %}
**注意**：相关背景知识可自行回顾 **COMP130201 计算机系统基础** 和 **COMP130191 计算机组成与体系结构** 。若本节内容难以理解，可先行跳过，随着实验的深入我们将逐步理解。
{% endhint %}

### 2.1 AArch64 地址翻译

在 AArch64 架构中，EL1 异常级别（类比于 RISC-V 的 Supervisor Mode，后文也称内核态）存在两个页表基址寄存器（`ttbr`：Translation Table Base Register）：`ttbr0_el1` 和 `ttbr1_el1`，分别用于**虚拟地址空间低地址**和**高地址**的翻译。

那么，什么地址范围称为“低地址”，什么地址范围称为“高地址”呢？这由翻译控制寄存器（`tcr`：Translation Control Register）进行配置，由其指出当虚拟地址高 X 位为 `0` 时，使用 `ttbr0_el1` 指向的页表进行翻译，当虚拟地址高 X 位为 `1` 时，使用 `ttbr1_el1` 指向的页表进行翻译。

在本实验框架中，我们将 `tcr_el1` 配置为高低地址各 `48` 位的虚拟地址空间（X = 16），即 `0x0000_0000_0000_0000` 到 `0x0000_FFFF_FFFF_FFFF` 为低地址空间，`0xFFFF_0000_0000_0000` 到 `0xFFFF_FFFF_FFFF_FFFF` 为高地址空间。

在地址翻译过程中，虚拟地址的划分如下图所示：

```
 63       48 47      39 38      30 29      21 20      12 11     0
+-----------+----------+----------+----------+----------+--------+
| FFFF/0000 | L0 index | L1 index | L2 index | L3 index | offset |
+-----------+----------+----------+----------+----------+--------+
```

在了解了上述背景知识后，你现在应该能看懂 `src/start.S` 中有关于内核页表配置的代码了。

```c
_start:
  /**
   * Set up the user and kernel page tables.
   * Higher and lower half map to same physical memory region.
   */
  adrp x9, kernel_pt_level0
  msr ttbr0_el1, x9
  msr ttbr1_el1, x9

  ldr x9, =TCR_VALUE
  msr tcr_el1, x9

  ...
```

### 2.2 内核虚拟地址

有了 AArch64 地址翻译的前置知识后，接下来我们引入内核虚拟地址的概念。

通常来说，我们会将操作系统内核配置在虚拟内存的高地址空间（也即 `0xFFFF_0000_0000_0000` 之后的虚拟地址），我们的实验框架也是如此。

{% hint style="info" %}
请回顾 `src/linker.ld` 中的内核链接地址，即

```linker-script
SECTIONS
{
	. = 0xFFFF000040000000;

	...
}
```

{% endhint %}

此外，我们在 `src/start.S` 中启用了 MMU（Memory Management Unit），这意味着我们的内核代码在访问内存时，必须使用内核虚拟地址，而不能直接使用物理地址。

为此，我们在 `src/aarch64/mmu.h` 定义了 `K2P` 和 `P2K` 两个宏，用于内核虚拟地址和物理地址的相互转换。

### 2.3 物理内存

在 `src/driver/memlayout.h` 中，给出了我们实验中内存空间的布局。

`EXTMEM` 至 `PHYSTOP` 这段物理地址内的空间即为我们的物理内存。但考虑到我们的内核代码也会置于内存中，实际可供分配的物理内存空间为 `end` 至 `PHYSTOP` 。

{% hint style="info" %}
请回顾 `src/linker.ld` 中给出的 `end` 符号，其标志着内核代码的结束地址。
{% endhint %}

为方便后续使用，我们需要将完整的物理内存切分为 `PAGE_SIZE` 大小并按 `PAGE_SIZE` 对齐的物理页，以物理页为单位管理物理内存。

{% hint style="info" %}
`PAGE_SIZE` 是内存页的大小，定义在 `src/aarch64/mmu.h` ，在这个头文件中，还提供了一些你可能会用到的宏定义。
{% endhint %}

## 3. 内存分配器

操作系统是内存资源的管理者，其管理内存的场景包括：

* 响应用户的 `malloc` 和 `free` 请求，分配内存给用户/释放用户不再需要的内存。也就是说，我们在用户态C语言编程中使用过的 `malloc` 和 `free`，其实质上是请求（或者说包装）了内核的内存管理逻辑。
* 响应内核本身的内存分配/释放需求。
* 管理内存与其他子系统的交互，例如 MMIO（后续实验会接触到）。
* ...

我们知道，现代计算机系统一般以一定大小的页为单位管理内存（如果以 byte 为单位管理内存，操作系统需要为每个内存地址维护一系列状态用于内存管理，造成巨量的资源消耗，因此操作系统会打包一段内存统一管理，即为页）。在本实验中，页的大小是 4096 byte。

为了响应用户的内存请求，操作系统可以将内存页分配给特定用户。然而，对于常见的内存需求而言，完整的物理页还是太大了。例如，若用户仅仅请求 1 byte 的内存，而我们以一个 4096 byte 的内存页响应此请求，这会造成其中 4095 byte 的浪费。因此，本实验中，我们将进一步实现细粒度的内存分配，以避免上述内存浪费。

{% hint style="warning" %}
**注意**：分配的内存块地址必须与大小对齐，即：

* 如果分配的内存大小是 `2` 的倍数，则地址也要是 `2` 的倍数
* 如果大小是 `4` 的倍数，地址也要是 `4` 的倍数
* 如果大小是 `8` 的倍数，则地址也要是 `8` 的倍数
* 不需要 `16` 字节以上的对齐，也即，如大小是 `16` 的倍数，则地址只需是 `8` 的倍数。
  {% endhint %}

与 C 语言中的 `free` 相同，我们实现的内存分配器不要求程序在释放内存块时告知内存块的大小。所以你需要在合适的地方保存内存块大小。

此外，我们保证框架代码或要求大家完成的代码中需要通过内存分配器分配的内存大小均在 `1 - PAGE_SIZE/2` 之间，即我们不会要求你实现大页分配。

## 4. 并发问题

本实验中，我们要求大家考虑并发安全问题。测试时，4个核会同时分配和释放内存，你编写的内存分配器必须考虑到这种情况。

如下面代码，我们希望这段代码找到处于 `AVAILABLE` 状态的元素，并将其标记为 `USING` 。

```c
for (int i = 0 ; i < N; i++) {
    if (mem[i] == AVAILABLE) {
        mem[i] = USING;
        return i;
    }
}
```

容易看出，当两个核同时执行这段代码时，可能两个核会返回同一个元素，导致重复分配。

解决并发问题的常用办法是为代码加锁，锁的设计保证同时只能有一个CPU取得锁，也就只能有 一个CPU执行锁保护下的代码。

```c
acquire_spin_lock(mem_lock);
for (int i = 0 ; i < N; i++) {
    if (mem[i] == AVAILABLE) {
        mem[i] = USING;
        return i;
    }
}
release_spin_lock(mem_lock);
```

原子操作简介：<https://gcc.gnu.org/onlinedocs/gcc/\\_005f\\_005fatomic-Builtins.html>

另一种思路是为不同CPU维护不同的数据结构

```c
for (int i = 0 ; i < N; i++) {
    if (mem[cpuid()][i] == AVAILABLE) {
        mem[cpuid()][i] = USING;
        return i;
    }
}
```

{% hint style="info" %}
上面举例用的代码与本实验并没有太大关联。
{% endhint %}

{% hint style="info" %}
**讨论**：这里我们介绍了 SMP 背景下的内存分配器的两种设计思路（1）统一内存池，但加锁保证并发安全；（2）每个核心维护自己的内存池，无需加锁。两种方案各有优缺点：

* **锁竞争的开销**：当系统中有大量线程或进程同时发出内存请求时，方案（1）由于加锁以保证并发安全，内核的内存分配器同一时刻只能处理一个请求，其他请求需要在 `acquire_spin_lock` 处排队等待，这造成了大量的锁竞争开销。早期版本的 Glibc malloc 面临类似的问题，其在高并发内存请求场景下性能欠佳。后来，开发人员引入了 [tcache](https://sourceware.org/glibc/wiki/MallocInternals#Thread_Local_Cache_.28tcache.29)，在每个线程处维护一定的缓存，内存请求可以由这些缓存响应，而无需竞争全局内存池。这种方法从一定程度上避免了锁竞争，提高了高并发场景下的性能。
* **负载均衡**：虽然每个核心维护自己的内存池的方案极大地减少了锁竞争的开销，但我们仍需注意各核心的内存池大小是否均衡，可用内存是否充足。负载不均同样会导致内存资源利用效率降低，不利于系统的整体性能。
  {% endhint %}

## 5. 实验任务

{% hint style="success" %}
**任务 1**

我们为大家提供了一份编写好的 `main.c` 文件，请将这份文件与你的代码进行 merge，也可以直接用它替换你的代码。如果选择 merge，请确保得到的代码可以正确完成你此前所实现的数据结构初始化，并在其后让所有CPU进入 `idle_entry`。
{% endhint %}

{% hint style="success" %}
**任务 2**

请在 `kernel/mem.c` 中编写代码，完成下面函数：

* `void kinit()`：初始化内存分配器，这个函数会在内核启动时被调用（你可以在 `main.c` 中看到它）。**注意**：请勿移除其中关于`kalloc_page_cnt` 的初始化，你可以在其后添加你的初始化代码。
* `void* kalloc_page()`：分配以 `PAGE_SIZE` 对齐的 `PAGE_SIZE` 大小内存（即分配一整个物理页）。
* `void kfree_page(void*)`：释放 `kalloc_page` 分配的物理页。
  {% endhint %}

{% hint style="success" %}
**任务 3**

**借助前面实现的`kalloc_page`函数，请继续完成下面函数：**

* `void* kalloc(unsigned long long)`：使用你的分配器分配指定大小的物理内存块。我们保证所需物理内存块的大小符合内存分配器一节中的约定，也请注意其中的对齐要求。
* `void kfree(void*)`：释放 `kalloc` 分配的物理内存块。
  {% endhint %}

本实验所需的简易的内存分配器就由上述 4 个函数组成。**要求算法复杂度为** $$O(1)$$。

上述四个函数的定义已经在 `kernel/mem.c` 中给出。

{% hint style="info" %}
因为我们的测试使用 `kalloc_page` 和 `kfree_page` 中的统计代码记录分配器所用物理页的数量，因此要求大家的分配器使用上述两个函数获取内存资源。

我们保证测试时大小超过 `PAGE_SIZE / 20` 的内存块不超过$$10%$$，因此你不必过于关注物理页不够大的问题。如确有实现大页分配的需求，请与助教沟通，更新相关的统计代码。
{% endhint %}

一些可能有用的提示：

* 测试时会用4个核同时分配和释放内存，请务必关注并发安全问题。
* 也许你会用上 `common/list.h` 里提供的数据结构。
* 我们不要求在 `kfree` 中调用 `kfree_page` 释放物理页，只要保证 `kfree` 释放的内存块能被 `kalloc` 再分配即可完成要求。如果你实现了释放物理页，可以将其作为你的创新点写进报告里。

`idle_entry` 中已经编写了测试代码。如果测试通过，你将看到 `PASS` 和你的物理页用量。

物理页用量受随机因素和测试数据影响，不能完全代表大家的分配器好坏。**物理页的用量越少越好**。我们设定如下起评分标准（测试方法为连续运行三次取最小值）：

|   # Pages   | Score |
| :---------: | :---: |
| 1200 - 1400 |  100  |
| 1400 - 1500 |   90  |
| 1500 - 1600 |   80  |
| 1600 - 1700 |   70  |
|    > 1700   |   60  |

> ~~说不定页数小于1200的会有神奇的效果~~

## 6. 提交

**提交方式**：将实验报告提交到 elearning 上，格式为`学号-lab1.pdf`。

{% hint style="warning" %}
**注意**：从`lab1` 开始，用于评分的代码以实验报告提交时为准。如果需要使用新的代码版本，请重新提交实验报告。
{% endhint %}

**截止时间**：<mark style="color:red;">**9月27日23:59**</mark>

{% hint style="danger" %}
**逾期提交将扣除部分分数**

计算方式为 $$\text{score}\_{\text{final}} = \text{score} \cdot \left(1 - n \cdot 20% \right)$$，其中 $$n$$ 为迟交天数，不满一天按一天计算）。
{% endhint %}

报告中可以包括下面内容

* 代码运行效果展示
* 实现思路和创新点
* 对后续实验的建议
* 其他任何你想写的内容 (~~你甚至可以再放一只可爱猫猫~~)

报告中不应有大段代码的复制。如有使用本地环境进行实验的同学，请联系助教提交代码（提供 `git` 仓库）。使用服务器进行实验的同学，助教将在服务器上检查，无需另外提交代码。