⏰Soft Deadline: 2024 年 4 月 7 日 23:59:59

你需要首先阅读实验须知，其中包含了代码获取方法、提交方法、如何查看提交结果等。在命令行中 git pull origin L0 下载框架代码。

1. 背景

如何为计算机硬件编程？我们的计算机硬件上可以直接运行我们编写的 C 代码，就像上课时展示的 Hello World：

#include <am.h>
#include <klib.h>

int main() {
    printf("Hello, OS World\n");
}

这个程序除了调用的库函数不同 (例如没有 stdio.h；多了 am.h) 之外，它就是一个完全符合 C 标准的普通程序，但因为没有操作系统和标准库的支持，我们需要编写所有的库函数。例如，printf 也来自我们的代码，它调用了 AbstractMachine 提供的 putch API:

void putch(char ch);

putch 会在调试终端上输出一个字符；对于 x86-qemu 平台来说，调试终端就是 QEMU 的串口。

我们使用实验框架在 bare-metal 上运行了 Hello World，这也是 “最小” 操作系统的雏形——你可以在此基础上实现任何操作系统内核。通过适当的 gdb 指令 (这次是更好用的 Python，取代了历史遗留的 gdb scripts)，我们完成配置的同时指定正确的二进制文件，调试硬件上的代码，与调试普通的程序完全没有区别。

如果希望深入了解编译的全过程，遵循 “一切都是状态机” 的原理，我们可以观察 Makefile (程序)，也可以观察它的执行，而它的执行就是一个个的命令。make log 对输出的日志做了一些简化处理，已经足够人类可读，稍加整理就能看到磁盘镜像的编译过程。你也许会感到有些吃惊：世界上所有操作系统的构建过程 (例如 Linux)，都和这个简化版类似，只是多了更多实用的特性：支持分区表、支持压缩/解压缩等。

2. 实验描述

2.1 理解框架代码

🗒️实验要求：阅读 AbstractMachine 文档

想知道为什么能用你熟悉的方式编写操作系统？阅读 AbstractMachine的文档。当然，文档很多，你不必一次看完，建立了一些基本概念后，就可以试着从样例代码出发开始编程了。另一个好消息是我们的实验框架中直接包含了 AbstractMachine 的代码并在 Makefile 中完成了配置 (RTFSC)，从而你无需额外配置/下载。

💡可选实验：实现 klib 中缺失的函数

我们课堂上演示的代码中，klib 已经被正确实现；但你的框架代码中，这部分实现是空缺的。如果你想只用 putch 打印，会使你连打印一个整数都麻烦到怀疑人生。框架中已经在 klib.h 列出了一些函数的原型供大家参考；我们不强制实现 klib 函数，但随着操作系统实验的进展，你会体会到不实现库函数的苦头。如果你对编程感到很苦恼，不妨按只实现一些简化版本的库，无需全部实现；随着实验的进展后续补齐。

klib这部分代码对你来说应该非常重要——会一直使用到这学期的最后，因此也请你非常小心地编写代码，例如编写相当多的 assertions；klib 中的 bug 会使原本就已很困难的操作系统内核调试更加令人沮丧。

2.2 在 AbstractMachine 中显示一张图片

🗒️实验要求：显示一张图片

你需要编写一个直接运行在 AbstractMachine 上 (仅仅启用 IOE 扩展，不使用其他硬件机制如中断/异常/虚拟存储/多处理器) 的程序，显示一张图片；满足：

  1. 显示一张任何图片，但能适配不同的屏幕大小。确保你的图片在 320×200 ，320x200，320×200、640×480， 640 x480， 640×480，800x600 ，800×600 等分辨率下均可以正常显示；
  2. 图片中包含不少于 10 种颜色。
  3. 程序使用的内存 (代码、静态数据总和不超过 4 MiB、堆区 heap 使用不超过 4 MiB)；
  4. 按 ESC 键后调用 halt() 退出；除此之外，按任何键程序都不应退出。
💡移植性要求

你的代码应当有一定的可移植性：同 minilabs 一样，你的程序可能运行在 32/64-bit 平台，因此你应当使用 intptr_t 或 uintptr_t 来保存指针数值。

我们会在 x86_64-qemu (64-bit) 和 x86-qemu (32-bit) 两个环境下运行，你的程序必须在两个环境下都能正确编译并运行良好。此外，AbstractMachine 假设 bare-metal 不支持浮点数指令。在 x86_64 的编译选项中，我们添加了 -mno-sse。尽管有浮点数的程序在 ARCH=native 下可以正确编译运行，但可能在其他架构下失效。这么做的目的是使 AbstractMachine 程序能运行在各种 (简化) 的处理器上。

3. 正确性标准

Online Judge 会严格按照上面的要求来评测：

  • 我们会通过 qemu 的 -m 选项限制内存的大小；使用超过规定的内存可能导致程序崩溃。同学们可以用 size 命令查看二进制文件的大小。
  • 我们会在不同的环境下 (x86-qemu 或 x86_64-qemu, native) 运行你的程序，并且可能修改屏幕的分辨率 (我们的 AbstractMachine 可能拥有和你不同的分辨率！)。
  • 我们会向你的程序发送一定数量的随机键盘事件。

没错，Online Judge 会自动运行你的程序——这意味着你也可以自动运行你的程序，实现本地的自动化测试。Online Judge 会作出如下正确性检查：

  1. 除非按 ESC 键，我们假设程序不结束；如果检测到 halt() 的调用 (包括 assert 失败，我们可能会增加一些额外的合法性检查)，将判定为错 (Runtime Error 或 Wrong Answer)；
  2. 如果按 ESC 键后程序不结束，将判定为错；
  3. 如果虚拟机或进程发生崩溃、非预期的重启等 (由 undefined behavior 导致，例如访问某非法内存可能导致异常或 CPU Reset)，则被判定为错；
  4. 其他违反 specifications 的问题，如在 ioe_init() 之前调用 io_read/io_write，将被判定为错。

此外，我们会链接我们 klib 的参考实现，因此你不必担心你的 klib 有些许问题；但你要保持 klib 库函数的行为与 libc 一致。注意 native 会链接系统本地的 glibc (而非 klib)。

4. 实验指南

☕️阅读手册

首先，AbstractMachine 的文档 是帮助你理解整个框架代码的核心。阅读它，了解到底为什么“操作系统就是一个 C 程序”；你也可以参考课程中的调试技巧。

4.1. 实现库函数

实现库函数是普通的 C 语言练习题；互联网上也有很多代码可以参考；尤其是你可以多向大语言模型提问——但我们不建议大家直接使用来自任何其他人 (包括 AI) 的代码：“照抄” 会使你失去训练的机会：如果你独立编写，很可能会遇到各种 bugs，而解决这些 bug 时，你会不断提出假设、验证假设，直到你最终把 bug 定位到一个足够小的范围能够直接解决它。在这个过程中，你会积累 “应该如何提出和验证假设” 的经验，而这些第一手经验是很难通过阅读文档 (和正确的代码) 而获得的。

当然，在你实现完以后，我们也鼓励大家阅读一些其他人实现的代码，例如 musl，如果你参考一些早期版本 (例如 v0.5.0)，再对比更新的版本，就会对库函数的实现有更深的认识。

☕️想试试 malloc?

没错。malloc/free 是实现更复杂系统极为重要的 API。你很想实现它——然后你发现 v0.5 的 malloc.c 就已经有 500 行了！接着你发现了 “__simple_malloc.c”：

void *__simple_malloc(size_t n)
{
	static uintptr_t cur, brk;
	uintptr_t base, new;
	static int lock;
	size_t align=1;

	if (n < SIZE_MAX - ALIGN)
		while (align<n && align<ALIGN)
			align += align;
	n = n + align - 1 & -align;

	LOCK(&lock);
	if (!cur) cur = brk = __brk(0)+16;
	if (n > SIZE_MAX - brk) goto fail;

	base = cur + align-1 & -align;
	if (base+n > brk) {
		new = base+n + PAGE_SIZE-1 & -PAGE_SIZE;
		if (__brk(new) != new) goto fail;
		brk = new;
	}
	cur = base+n;
	UNLOCK(&lock);

	return (void *)base;

fail:
	UNLOCK(&lock);
	errno = ENOMEM;
	return 0;
}

在 “实验作业” 的阶段，我们并没有做什么创新，但经过了你独立的思考，再参考他人的解决方案，就能获得很多启发。注意你可以在本地通过修改 Makefile 绕过某些 warnings，使你的程序看起来正确地在多个平台上运行；但 Online Judge 会使用我们的 Makefile 和 AbstractMachine 实现，并且可能经过一定的修改 (例如设置为不同的屏幕分辨率)。

4.2. 访问 I/O 设备

没有库函数的 C 语言程序类似于状态机，只能完成纯粹的 “计算”。TRM 中唯一能够和外界交互的手段是 putch() 在调试终端上打印字符和 halt() 终止程序。我们的硬件提供了若干 I/O 设备，AbstractMachine 可以通过 IOE 访问它们。在调用 I/O 设备之前，需要调用 ioe_init() 初始化，然后就可以用

void ioe_read (int reg, void *buf);
void ioe_write(int reg, void *buf);

两个函数访问 AbstractMachine 中的 I/O “寄存器” 了。详情请参考 AbstractMachine 文档和框架代码。在 klib-macros.h 中包含了更简化的 I/O 寄存器访问方法 io_read 和 io_write，请大家查看。用这组 API 你就可以省去手工定义变量的麻烦，例如直接

int width = io_read(AM_GPU_CONFIG).width;

到这里，大家可能会产生的一个疑问是：运行在 “裸机” 上的程序可以用哪些标准库？我们知道，libc 中相当一部分函数都调用操作系统，例如 printf, malloc 等，即便引用了 stdio.h 这样的头文件，它们的实现依然是缺失的；另一方面，我们引用了一些库的头文件，例如 stdint.h (包含诸如 int32_t 这些类型的定义)、stdarg.h 等，却可以正常工作。这是为什么？

事实上，AbstractMachine 的程序运行在 freestanding的环境下 (操作系统上的 C 程序运行在 hosted 环境下)：

The __STDC_HOSTED__ macro expands to 1 on hosted implementations, or 0 on freestanding ones. The freestanding headers are: float.h, iso646.h, limits.h, stdalign.h, stdarg.h, stdbool.h, stddef.h, stdint.h, and stdnoreturn.h. You should be familiar with these headers as they contain useful declarations you shouldn’t do yourself. GCC also comes with additional freestanding headers for CPUID, SSE and such.

这些头文件中包含了 freestanding 程序也可使用的声明。有兴趣的同学可以发现，可变参数经过预编译后生成了类似 __builtin_va_arg 的 builtin 调用，由编译器翻译成了特定的汇编代码。

4.3. 绘制一个图片

“绘制一个图片” 似乎是一个很奇怪的需求。然而，你很快也反应过来：“图片不过是计算机中保存的 01 数据”。那么我们是如何在 C 语言中保存程序运行前的数据的？答案是定义带初值的全局变量：

const char *names = {
    "Tom",
    "Jerry",
    "Spike",
    ...
};

我们只要把图片的 RGB 数值写在代码里，不就可以显示图片了吗！没错。甚至我们的 xxd 工具都帮助大家实现了这一点：

// Generated by: xxd -i /bin/ls
unsigned char _bin_ls[] = {
    0x7f, 0x45, 0x4c, 0x46, 0x02, 0x01, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x03, 0x00, 0x3e, 0x00, 0x01, 0x00, 0x00, 0x00,
    ...
    0x00, 0x00, 0x00, 0x00
};
unsigned int _bin_ls_len = 142144;

xxd 可以将任何二进制文件转换成 C/C++ 可以接受的常量数组，而且把数组的长度也固定好。因此你可以在 “kernel” 的外部准备好任何的图片数据。至于同一个图片如何 “拉伸/缩放” 到不同分辨率，这就是你需要考虑的问题了——不过这也不难，说白了你是希望将一个n×m 的矩形网格 “投影” 到一个 n′×m′ 的矩形网格上——因此最简单的方法就是在新网格上找到旧网格 “最靠近” 的那个位置对应的像素即可。