操作系统 - 临时草稿

发表于 分类于 阅读次数：

操作系统(临时草稿)

包含: OSTEP, rCore-tutorial-guide 等

暂时集中在一篇文章里, 以后有需要再分章节记录

这篇博客不会讲解的特别详细, 因为本人在读文档做 lab 的过程中比较痛苦()

环境配置

由于我已经有了一个 Fedora40 和一个 Arch Linux 的环境, 所以系统开发环境直接跳了

这一系列 lab 本质上是要求用 Rust 完成 lab 要求实现的功能, 通过 rustc 交叉编译到 riscv64gc-unknown-none-elf (一般情况下是 x86_64-unknown-linux-gnu), 通过 rust-objcopy 提取出 bin, 然后放到 qemu-system-riscv64 模拟器进行模拟.

QEMU 最好装 7.0.0 或以上的, 从源码编译安装的话需要注意以下依赖, 部分发行版的依赖可以在 Running 64- and 32-bit RISC-V Linux on QEMU — RISC-V - Getting Started Guide 找到, Arch 用户可以通过 pacman -U 或者 downgrade 装旧版的, 也可以自行搜罗依赖包然后从源代码编译, 这里不再赘述

构建一个能跑但仅仅能跑的操作系统

根据 OSTEP 的说法, 操作系统的主要三个任务部分在于: 虚拟化, 并发, 可持久化

  • 虚拟化主要表现在:
    • 对内存的抽象: 每个进程有自己的虚拟地址空间, 造成每个进程独占一个主存的假象(学过 CSAPP 可以回忆一下第九章, 博客还在补)
    • 对 CPU 的虚拟化: 主要表现在操作系统内核对各个任务的调度, 使得每个任务产生独占 CPU 的假象(这就是一种并发)
    • 对外设设备的虚拟化等等
  • 并发主要表现在:
    • 进程概念的抽象和实现, 进程间通信
    • 多线程的实现
  • 可持久化主要涉及文件系统

而形式上, 操作系统是一个二进制文件或二进制文件镜像, 被 bootloader 加载进内存的特定位置, 驻留在内存中的特定代码, 这些代码负责一些加载应用程序(简单来说就是把可执行文件加载到内存), 管理资源(设备/文件)并提供访问的任务, 这些任务以系统调用(syscall)的形式暴露给应用程序, 只是系统调用函数比较敏感特殊, 下面会仔细介绍.

那么我们的任务就比较明确了:

  • 先设计一个基本的能把应用程序加载到内存的功能 (当然因为现在内核没有任何调度能力也没有让应用程序启动其他应用程序的必要(这依赖进程的实现), 所以我们暂时不需要设计 execve 系统调用)
  • 实现标准输出能力 (实际上标准输出就是调用系统调用 write, 目标为 1 (标准输入))
  • 实现退出程序的能力 (exit 系统调用)

我们不能再依赖的

在 CSAPP3e第七章(链接) | Amiriox’s Storage 的博客中我们有说 C 程序的启动流程: execve 系统调用, loader 加载可执行文件到内存, _start 执行一些初始化工作, 调用 __libc_start_main, 最后调用用户的 main 函数

但这是一个用户应用程序的启动流程, 我们写操作系统的肯定是没有这些东西了: execve 是操作系统提供的系统调用, 我们要在很久后才能实现, loader 本身就是操作系统的代码, _start 位于 ctrl.o 而 __lib_start_main 位于 libc.so, 这一串东西里面我们一个有的都没有, 甚至更坏的是, 我们不能再依赖 Rust 的 std crate, 因为我们处于裸机平台.

有条件要上，没有条件创造条件也要上。——王进喜, 1963

对于 Rust std 的缺失, 我们可以用 core 代替, 它包含了 Rust 的相当一部分核心机制, 我们将会在后面见到 core::slice::from_raw_parts 的重要作用;
对于操作系统的执行入口我们暂且按下不表, 只需要知道我们需要显式告诉编译器我们暂时没有 main 函数

1
2
#![no_std]
#![no_main]

当然, 我们还需要提供 panic 的语义项, 详见 Core-Tutorial-Guide-2025S 文档. 我们尽可能不偏离介绍操作系统的核心部分

操作系统的入口在哪?

详细说一下操作系统(甚至是计算机)的启动流程:

  1. UEFI 固件进行自检, 看看有没有什么坏了, 没什么好说的
  2. UEFI 读取引导设备列表(比如装系统时的 liveCD, 或者硬盘, 读取 MBR (BIOS) 或 EFI 分区 (UEFI), 将 bootloader (引导加载程序) 加载到内存中并执行(例如你看到的 grub 页面)
  3. Bootloader 读取自身配置文件, 列出可选的操作系统, 然后加载内核. 对于 Linux 来讲, 就是执行 linux /boot/vmlinuz ... 加载内核, 执行initrd初始化 initramfs, 然后使用 UEFI 机制跳转到操作系统内核的入口点(其实还会释放自身)
  4. 操作系统执行一些必要的任务初始化自己, 即我们通常理解的开机(挂载目录, 启动守护进程). 对于 Linux 来说, 入口点在 arch/x86/boot/header.S 中的 _start位置

当然这是一个相当简化过的流程, 我们尽可能不偏离介绍操作系统的核心部分.

所以我们知道我们的操作系统入口在 _start 位置, 但是具体要怎么做? 我们要写汇编吗? 不, 我们可以通过链接器脚本来安排内存空间布局, 我们要自己确定 .text 段 .data 段等的地址, 前后布局, 对齐等. 链接器脚本的语法不要求掌握, 但要知道他是用来做什么的.

显然 _start 应该在 .text 段的初始位置. ENTRY(_start) 可以规定入口点. 但是这些东西具体的位置在哪呢? 我们知道怎样安排 .text .rodata .data .bss 的相对位置, 但不知道绝对位置(也就是说我们缺一个 BASE_ADDRESS). 回顾计算器的启动流程, 我们发现是 bootloader 跳转到操作系统入口的. 而在我们的实验中, RustSBI 起到 bootloader 的作用, 而它要求我们把入口点设在 0x80200000. (当然 RustSBI 还提供了更多的操作机器的接口)

我们还需要初始化栈空间布局, 在 entry.asm 中初始化栈指针, 然后让 _start 直接调用 rust_main 函数, 这也就是我们通常理解下的 main 函数了, 则我们写的操作系统的 main.rs 大概是这样的:

1
2
3
4
5
6
7
8
9
10
 #![no_std]
 #![no_main]
 
// 初始化内存布局
core::arch::global_asm!(include_str!("entry.asm"));

#[no_mangle]
pub fn rust_main() -> ! {
    // Hello World!
}

#[no_mangle] 用于函数名不被混淆, 否则链接器会找不到 rust_main. 链接器脚本 linker.ld 提供给编译器, 不需要再代码中体现.

理论上, 我们现在就有了一个可以在 RISC-V 架构上的裸机环境运行的纯粹的操作系统, 没有任何用, 我们甚至不知道怎么写 Hello World(因为暂时还没 println! 宏), 甚至这个操作系统不能够正常退出!

1
2
3
4
5
6
7
8
9
# 编译生成ELF格式的执行文件
$ cargo build --release
 Compiling os v0.1.0 (/media/chyyuu/ca8c7ba6-51b7-41fc-8430-e29e31e5328f/thecode/rust/os_kernel_lab/os)
  Finished release [optimized] target(s) in 0.15s
# 把ELF执行文件转成bianary文件
$ rust-objcopy --binary-architecture=riscv64 target/riscv64gc-unknown-none-elf/release/os --strip-all -O binary target/riscv64gc-unknown-none-elf/release/os.bin

# 在 QEMU 上运行, 参数都比较好理解
$ qemu-system-riscv64 -machine virt -nographic -bios ../bootloader/rustsbi-qemu.bin -device loader,file=target/riscv64gc-unknown-none-elf/release/os.bin,addr=0x80200000

实现正常退出

从这里开始, 我们就要提供系统调用. 也许你看到这篇文章时我已经补完了 CSAPP 第八章的博客, 不然你就只能自己翻书了解一下内核态与用户态以及 Trap 是什么了. 我开玩笑的, 因为这里面有一些术语不通用.

指令执行的环境有三种

  • 最高权限的机器级别(M), RustSBI 在这个环境下
  • 次高权限的, 内核态或特权级别(Kernel Mode 或 Supervisor Mode), 操作系统内核在这个环境下
  • 用户态(U), 用户程序所在位置

操作系统要做的就是封装, 管理和组织起来 RustSBI 提供的及其底层的接口为 syscall, 暴露给用户程序(当然具体实现上 syscall 不一定全都是在调用 RustSBI, 也有可能直接在内核态操作内存, 总之通过 syscall trap 进内核态是操作系统从驻留内存静止到真正被执行的转换), 这里面有五个点:

  1. 操作系统调用 RustSBI 的方式是通过汇编指令 ecall 对应的 sbi_call id (实际叫 EID/EID), 这个过程在内核态下, 当然也有 crate::sbi:: 封装好的以供使用
  2. 用户调用操作系统提供的系统调用是通过汇编指令 ecall 对应的 syscall id, 这个过程在用户态下, 会 Trap 进内核进行处理, 内核解析 syscall id 并作出对应相应.
  3. Trap 可以理解为”用户程序在路上走着走着想要访问一些超出自己权限的东西, 就像一脚踩空掉到陷阱 Trap 进内核了一样”, Trap 的过程会保存上下文(寄存器等), 等从内核态回用户态时会恢复上下文. 仔细感受 Trap 这个词, 是不是读音上就很有感觉?
  4. 细分权限的意义在于: 你不能指望用户程序都是善意的, 即使是善意的也不能假定其开发者是全知全能的, 因此把敏感操作交给操作系统是安全考虑
  5. Rust 调用汇编指令是通过 core::arch::asm! 或 global_asm!, 我们上面已经见到了.

注意这个 arch 是 architecture 而不是 Arch Linux (?)

目前我们先试试不封装系统调用, 单独调用 sbi_call 用于退出:

1
2
3
4
5
6
7
8
9
10
fn sbi_call(which: usize, arg0: usize, arg1: usize, arg2: usize) -> usize {
 let mut ret;
  unsafe {
      core::arch::asm!(
          "ecall",
...
pub fn shutdown() -> ! {
    sbi_call(SBI_SHUTDOWN, 0, 0, 0);
    panic!("It should shutdown!");
}

! 返回值表示函数是发散函数 永不返回.

要为你的用户做些什么

我们实现两个系统调用 sys_write 和 sys_exit

1
2
fn sys_write(fd: usize, buf: *const u8, len: usize) -> isize;
fn sys_exit(xstate: usize) -> !;

sys_write 系统调用会封装 RustSBI crate::sbi::console_putchar, 当然还利用了 Rust 的宏和 fmt 等使其更易用.

我们还需要给用户一个通用的 syscall 来实现系统调用:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/// write syscall
const SYSCALL_WRITE: usize = 64;
/// exit syscall
const SYSCALL_EXIT: usize = 93;

fn syscall(id: usize, args: [usize; 3]) -> isize {
    match syscall_id {
        SYSCALL_WRITE => sys_write(args[0], args[1] as *const u8, args[2]),
        SYSCALL_EXIT => sys_exit(args[0] as i32),
        // SYSCALL_YIELD => sys_yield(),
        // SYSCALL_GET_TIME => sys_get_time(args[0] as *mut TimeVal, args[1]),
        // SYSCALL_TRACE => sys_trace(args[0], args[1], args[2]),
        _ => panic!("Unsupported syscall_id: {}", syscall_id),
    }
}

sys_write/sys_exit 将会封装为 write/exit, 就像标准库一样提供给用户程序.

跑点什么?

我们之前说了实际上操作系统加载程序的最核心部分就是把应用程序可执行文件加载到内存. 由于我们想一切从简(没错, 当你阅读到这时还远远不能称作入门), 所以我们先只是把应用程序静态地放到内存的特定位置: 这种情况下算是把应用程序作为内核的一部分了——有没有感觉什么不对? 之前不是说应用程序在用户态吗? 这就暴露了另一个问题: 我们只是实现了系统调用, 但 Trap 的过程没有任何控制!

我们将首先说如何把应用程序放入内存, 再介绍 Trap 过程

把应用程序静态地放入内存:

1
core::arch::global_asm!(include_str!("link_app.S"));

link_app.S 和 entry.S 类似, 就是把应用程序的起始和终止位置标注, 设置内存布局并通过 .incbin 引入二进制文件, 还要开个数组记录一下各个程序的位置暴露给我们的操作系统使用(与汇编交互的过程可以自行搜索, 大概就是 extern "C" { fn symbol(); } 这样):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
    .align 3
    .section .data
    .global _num_app
 _num_app:
    .quad 3
    .quad app_0_start
    .quad app_1_start

    .section .data
    .global app_0_start
    .global app_0_end
app_0_start:
    .incbin "../user/target/riscv64gc-unknown-none-elf/release/hello_world.bin"
app_0_end:
	...

操作系统中则是:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
extern "C" {
	fn _num_app();
}
let num_app_ptr = _num_app as usize as *const usize;
let num_app = num_app_ptr.read_volatile();
let mut app_start: [usize; MAX_APP_NUM + 1] = [0; MAX_APP_NUM + 1];
let app_start_raw: &[usize] =
	core::slice::from_raw_parts(num_app_ptr.add(1), num_app + 1);
app_start[..=num_app].copy_from_slice(app_start_raw);
AppManager {
	num_app,
	current_app: 0,
	app_start,
}
...
    if app_id >= self.num_app {
        panic!("All applications completed!");
    }
    info!("[kernel] Loading app_{}", app_id);
    // clear icache
    core::arch::asm!("fence.i");
    // clear app area
    core::slice::from_raw_parts_mut(APP_BASE_ADDRESS as *mut u8, APP_SIZE_LIMIT).fill(0);
    let app_src = core::slice::from_raw_parts(
        self.app_start[app_id] as *const u8,
        self.app_start[app_id + 1] - self.app_start[app_id],
    );
    let app_dst = core::slice::from_raw_parts_mut(APP_BASE_ADDRESS as *mut u8, app_src.len());
    app_dst.copy_from_slice(app_src);

即:

  • 获取 _num_app 的位置, 并通过转换为指针读到那个位置的 num_app (应用程序数量), app_start (各个程序的起始位置), core::slice::from_raw_parts 从裸指针的一块地址获取切片, 还有 from_raw_parts_mut 获取可变切片的
  • 调用 fence.i 清理 i-cache (详见: CSAPP3e第六章(存储器层次结构) | Amiriox’s Storage)
  • 把对应应用程序起始地址和终止地址之间的内存切片复制到 APP_BASE_ADDRESS 的位置

这里我们不讨论具体的程序结构设计, 如何令程序模块化更好等. 具体代码可以参考 rCore 的实现.

实现上下文切换

上下文切换的流程:

应用程序调用系统调用 -> 硬件触发Trap -> 指令集设置寄存器(对RISC-V就是 stvec, scause 等) -> 进入内核态并跳转到 stvec 所在位置 -> 这个位置上的代码承担保存上下文和具体处理系统调用的职责 -> 恢复上下文

我们逐个击破。

CSRs

RISC-V 中和 Trap 流程相关的寄存器是 CSR (Control and Status Register)

CSR 名 该 CSR 与 Trap 相关的功能
sstatus SPP 等字段给出 Trap 发生之前 CPU 处在哪个特权级（S/U）等信息
sepc 当 Trap 是一个异常的时候，记录 Trap 发生之前执行的最后一条指令的地址
scause 描述 Trap 的原因
stval 给出 Trap 附加信息
stvec 控制 Trap 处理代码的入口地址

我们只需要通过 stvec::write(__alltraps as usize, TrapMode::Direct), 把 stvec 写入为我们 __alltraps 过程的地址

__alltraps 的实现

我们要保存寄存器, 但是问题是: 保存到哪?

C 应用程序在调用函数过程中也有保存上下文的概念, 一般是把上下文中的调用者保存寄存器保存到栈上. 但我们这里每个应用程序的栈空间暂时是重合的, 我们需要保存到别的位置, 这也就需要我们引入”内核栈”的概念. 在比较完善的操作系统中, 会在内核地址空间的高位存放不同应用程序的内核栈并且通过保护页隔开, 这里对内核栈的理解应更偏向其特性和用途: 特性是由内核态代码访问修改, 不受应用程序切换或者 Trap 影响, 用途是存放一些有以上特性的数据.

__alltraps 实际上要做的就是: 开局切换栈指针到内核栈, 把通用寄存器保存到内核栈上, 把 CSR 寄存器保存到内核栈上, 构造 TrapContext 上下文放入 a0 (相当于 x86_64 的 %rdi), 调用 trap_handler(注意等我们实现虚拟内存后就不能直接 call 了), trap_handler 用于实际处理系统调用(以及其它类型的 Trap):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#[no_mangle]
pub fn trap_handler(cx: &mut TrapContext) -> &mut TrapContext {
    let scause = scause::read();
    let stval = stval::read();
    match scause.cause() {
        Trap::Exception(Exception::UserEnvCall) => {
            cx.sepc += 4;
            cx.x[10] = syscall(cx.x[17], [cx.x[10], cx.x[11], cx.x[12]]) as usize;
        }
        Trap::Exception(Exception::StoreFault) |
        Trap::Exception(Exception::StorePageFault) => {
            println!("[kernel] PageFault in application, core dumped.");
            run_next_app();
        }
        Trap::Exception(Exception::IllegalInstruction) => {
            println!("[kernel] IllegalInstruction in application, core dumped.");
            run_next_app();
        }
        _ => {
            panic!("Unsupported trap {:?}, stval = {:#x}!", scause.cause(), stval);
        }
    }
    cx
}

__restore 的实现

别忘了还得从内核态回来. 我们用 __restore 做到这一点. 首先要把 __restore 放在 call trap_handler 的下一条地址位置, 这样从 trap_handler 返回后顺序执行到 __restore . __restore 做的事情:

  • 把内核栈保存的通用寄存器和 CSR 都恢复到寄存器中
  • 切换到用户栈
  • 调用 sret 返回用户栈

这样, 我们就实现了所谓的”批处理操作系统”!

多道程序和分时多任务

如果我们有 5000 个应用程序, 每次执行某个程序都要加载一次消耗是巨大的. 所以我们需要预先加载多个程序进入内存, 由内核调度决定运行哪个程序

如果有一个程序需要文件 I/O 操作占用大量时钟周期等待, 消耗也是巨大的. 所以我们要实现时钟中断, 一个任务执行一段时间后保存状态并切换到别的任务, 一段时间后再回来.

管理多道程序

对于多道程序的放置, 实际上只需要把写死的 APP_BASE_ADDRESS 改写为 APP_BASE_ADDRESS + app_id * APP_SIZE_LIMIT 并相应修改 load_apps 即可. 但是切换任务就比较麻烦, 从一个任务切换到另一个任务的控制流是这样的:

A 任务 -> A的时钟中断Trap控制流 -> __switch -> B的Trap控制流 (-> 其他控制流) -> __switch返回 -> 从其他控制流回到A任务

1
2
3
4
 __switch(
    current_task_cx_ptr: *mut TaskContext,
	next_task_cx_ptr: *const TaskContext
)

switch 的职责是将内核栈保存到 current_task_context, 并将下一个任务的上下文从 next_task_context 中加载到当前寄存器

当然多道程序暂时还没有时钟中断Trap (分时多任务才有), 所以切换任务的方式就是从任务主动调用 yield 系统调用申请主动暂停并切换到下一个任务.

yield 系统调用的实现单纯就是把当前任务标记为停滞然后 run next, run next 就是在当前维护的任务集合中找到下一个状态为 Ready 的然后直接 __switch.

操作系统启动加载第一个用户程序(第一次进入用户态)就是构造一个空的上下文 __switch 到第一个任务的上下文即可.

分时多任务

通过 riscv::register::time::read() 读取 mtime 寄存器的值获取时间, 设置计时器.

计时器会触发一个 SupervisorTimer 的 Trap (Trap::Interrupt(Interrupt::SupervisorTimer)), 我们可以在这个 Trap 的 handler 中实现抢占式调度: 设置下一个计时器, 暂停当前任务并且切换到下一个可用任务.

1
2
3
4
5
6
match scause.cause() {
    Trap::Interrupt(Interrupt::SupervisorTimer) => {
        set_next_trigger();
        suspend_current_and_run_next();
    }
}

当然我们还要 trap::enable_timer_interrupt(), 用来设置 sie.stie 以允许 S 模式下的时钟中断. 别忘了操作系统启动后立刻设置计时器.

还记得我们说过 RISC-V 的一些术语和 CSAPP 规定的有歧义吗?

CSAPP 认为:

  • 所有控制流的不连续处都是异常, 异常包括: 中断, Trap, 故障, 终止, 以及 Linux 下的信号机制
  • 中断: 外设异步触发的”通知”, 比如 DMA 访存完成后通知 CPU 触发中断, 这里的外设是相对 CPU 而言
  • Trap: 内核态和用户态转换的过程
  • 故障: 例如虚拟内存缺页故障

RISC-V 语境下:

  • 一些事件例如时钟中断既是中断也触发 Trap, 其实这也是符合 CSAPP 视角的: 计时器也可以算作 CPU 的外设
  • Trap::Exception 更接近故障或终止的概念, 在 RISC-V 语境下故障, 终止都会触发 Trap

chapter3 练习跟白给的一样。

地址空间的实现

好像写不完了, 摆个大纲在这:

  1. 简介: 地址空间, 虚拟内存, 页表, 多级页表, MMU TLB 简洁, 虚拟地址到物理地址的翻译(查找页表从虚拟页号翻译到物理页号的过程), SV39 分页模式
  2. 实现多级页表机制
    1. 数据类型封装定义
    2. S 特权级的内存相关 CSR: satp
    3. 物理页帧分配(分配物理内存上的物理页面并管理), 通过 core::slice::from_raw_parts_mut 引用物理页帧上的地址
    4. 多级页表存储 root_ppn 并且把子页表存入 frame
    5. 对虚拟页号的 3 个 indexes (SV39) 逐级查询多级页表(没有就创建) 获取到虚拟页号对应的页表条目
    6. 多级页表的 map 与 unmap: 把某个物理页号映射到某个虚拟页号, 通过逐级创建页表, 并在最终页表条目存储 ppn
  3. 实现内核地址空间与应用地址空间:
    1. 内核和每个应用都有自己的地址空间, 作为一个 Memory Set 数据结构
    2. 一个 Memory Set 包含一个当下地址空间的多级页表和多个逻辑段, 逻辑段用于在比页更一级的抽象上管理内存
    3. 每个 Memory Set 由 satp 中记录的 token 区分 (SV39)
    4. Memory Set 提供 映射一段虚拟地址到逻辑段中的物理帧, 以及取消映射: 对齐, 分配物理帧并纳入管理(insert), 页表把这个 (虚拟页号, 物理页号) 键值对映射进去
    5. 内核地址空间和应用地址空间的逻辑段分布, 直接根据这个分布 map 逻辑段就行
    6. 应用地址空间还要调整一下链接脚本(因为有了地址空间可以共用一个链接脚本了)
    7. 借助 xmas_elf 解析 ELF 文件然后 Memory Set 依据文件的 section 映射到逻辑段
    8. 调整一下运行程序的部分
  4. 切换/加载/执行应用程序
    1. satp token 详细说明: 硬件, OS, 操作系统职责的边界
    2. Trap 的修改:
      1. 不再只是单纯交换 sp 和 sscratch 切换内核栈和用户栈, 原本切换后指向用户栈的应该指向应用地址空间内的上下文位置
      2. sfence.vma 刷新 TLB
    3. 改进 Trap 处理这一块比较复杂, 到时候慢慢说
  5. chapter 4 实验 lab2