第二章：批处理系统

• 什么是批处理系统?
  • 将多个程序同时输入计算机中，计算机能够自动处理这多个程序，一个程序完成后自动加载另一个程序。
  • 但是批处理系统存在问题，例如当前程序出错会导致后续程序暂停。
  • 为了解决批处理系统的问题引入了特权机制。
• 什么是特权机制？
  • 需要一个系统来处理程序出错的情况，当程序出错时可以去运行下一个程序。

1. 特权级机制

特权级机制能够保证程序出错不会影响到 OS 运行，但是单凭软件无法实现特权级机制，还需要 CPU 的帮助。

此前将 OS 编译为一个可执行文件会出现应用程序出错导致操作系统不可用。接下来会对应用程序做如下限制：

1. 应用程序不能访问任意地址空间。
2. 应用程序不能执行可能破坏计算机系统的指令。
3. 应用程序碰到不能执行的指令需要寻求 OS 的帮助，能够同 OS 进行交互。

• 如何实现特权机制？

  • CPU 执行的指令进行了分类，应用程序对于的指令是一个级别，而操作系统对应的指令是另一个级别。
  • CPU 设置两个不同安全等级的执行环境，分为用户态和内核态。用户态的级别低于内核他。
  • CPU 执行指令时会检查特权级别，如果在用户态执行内核态特权指令会产生异常。

• 存在问题？

  • 例如应用程序在使用函数调用时，若采用 call 和 ret 指令会直接绕过硬件的特权级保护检查。
  • 解决方案是设计新的机器指令，即 ecall 和 eret 。二者具有从用户态切换到内核态的能力。
  • OS 还需要提供相应的功能，例如 OS 需要提供执行 eret 前准备和恢复用户态程序上下文的能力。
  • 其次 在应用程序调用 ecall 指令后，能够检查应用程序的系统调用参数，确保参数不会破坏操作系统。
  • 此外可以使用 ecall 和 eret 来提高当前的权限级别，例如从用户态转为内核态。

x86 和 RISC-V 设计了多达 4 种特权级，而对于一般的操作系统而言，其实只要两种特权级就够了。一般而言，级别越大，能力越强。

RISC-V 分为机器模式 (M, Machine)、虚拟监督模式 (H, Hypervisor)、监督模式 (S, Supervisor)、用户/应用模式 (U, User/Application)。在CPU硬件层面，除了M模式必须存在外，其它模式可以不存在。

在 RISC-V 架构上的引导加载程序一般运行在 M 模式上、OS 运行在 S 模式下、应用程序运行在 U 模式上。

RISC-V 架构中，只有 M 模式是必须实现的，剩下的按需选择。

• 简单的嵌入式应用只需要实现 M 模式；
• 带有一定保护能力的嵌入式系统需要实现 M/U 模式；
• 复杂的多任务系统则需要实现 M/S/U 模式。
• 到目前为止，(Hypervisor, H)模式的特权规范还没完全制定好，所以本书不会涉及。

此前的 OS 和应用程序均运行在 S 模式下，后续需要区分 M/S/U 。其中应用程序运行在 U 模式下，OS 内核运行在 S 模式下，本章将其实现为一个简单的批处理系统、而第一章的 bootloader – RustSBI 运行在 M 模式下。

OS 负责处理应用程序出错导致的问题，处理的过程会存在特权级别的切换。在 RISC-V 架构中，这种与常规控制流（顺序、循环、分支、函数调用）不同的 异常控制流 (ECF, Exception Control Flow) 被称为 异常（Exception） ，是 RISC-V 语境下的 Trap 种类之一。

用户态转为内核态可以分为两类：

1. 用户态为获得内核态 OS 的功能而执行的特殊指令。
2. 用户态在执行某条指令期间产生错误并被 CPU 检测到，根据类型分为 16 种异常。

• 什么是陷入 或 trap 类指令？

  • 应用程序故意转为内核态、有意为之。
  • 执行 ebreak 这条指令之后就会触发断点陷入异常；

• ecall

• 什么是 SBI、ABI

  • M 模式软件 SEE 和 S 模式的内核之间的接口被称为 监督模式二进制接口 (Supervisor Binary Interface, SBI)，
  • 而内核和 U 模式的应用程序之间的接口被称为 应用程序二进制接口 (Application Binary Interface, ABI)，也叫做系统调用 (syscall, System Call) 。
  • 被叫做二进制接口是因为和程序语言的内部调用不同，而是一种机器/汇编指令的接口。
  • 之间的调用不受普通的函数调用控制流，而是陷入异常控制流，过程中伴随着 CPU 特权级别的改变。

• 如何处理其他异常？

  • 如除零、无效地址访问、无效指令等，总之就是当前特权级下执行高特权级指令或访问不该访问的资源？
  • 切换为内核态，恢复错误/异常后，重新切换为低优先级软件执行，如果无法恢复就杀死或清除此应用程序避免破坏执行环境。

2. 实现应用程序

如何设计实现被批处理系统逐个加载并运行的应用程序？

主要有两点：应用程序的内存布局、应用程序发出的系统调用。

3. 实现批处理操作系统

一个程序执行完毕就将下一个要执行的应用的代码和数据加载到内存种。

• 应用是如何加载的？

  • 应用放置采用“静态绑定”的方式，而操作系统加载应用则采用“动态加载”的方式。

• 大致流程

  • 内核需要知晓应用程序的数量和位置，所以需要汇编代码 link_app.S 将应用程序放置到相应的位置上。
  • 在 src/main.rs 中引入 link_app.S 并使用 os/build.rs 当 cargo build 时自动生成来生成 link_app.S。
  • 接下来实现批处理核心组件，在 os/src/batch.rs 中

• 找到并加载应用程序二进制

  • 通过 AppManager 结构体来管理应用程序。
  • 其中分为应用数量，当前正在执行程序的下标，程序位置等信息。将 AppManager 实例化为全局变量，使得任何函数都能直接访问。
  • 但其中 current_app 表示当前执行第几个应用，随着系统运行在不断变化。可以采用 static mut 处理，但这种类型是 unsafe 不够优雅，应当尽量避免。

• 在不使用 unsafe 的前提下如何处理 static mut 类型？

• 什么是 Rust 所有权？

  • 值在某一个时刻只能绑定到一个变量上，即值的所有权属于被绑定的变量。
  • 此外变量可以将所拥有的值转移给其他变量，或者变量退出作用域后值会被销毁，对应资源被回收。

• Rust 中的可变引用和不可变引用

  • 在函数调用时 Rust 可以通过可变引用（&mut）来修改借用(Borrow)的值，而不可变引用只能读，不能写。在数据表达上，引用类型和 C 的指针一样，但在不同的是在 Rust 中需要被编译器检查。

• 生存期 （Lifetime）

  • 代码执行期间值必须持续合法的代码区域集合，简单来说就是该值第一次出现，到最后一次出现之间的区域。

• 不可变/可变引用的约束

  • 使用 & 和 &mut 来借用值的时候代码必须满足某些约束条件，不然无法通过编译。
    • 不可变/可变引用的生存期不能超出（Outlive）它们借用的值的生存期，也即：前者必须是后者的子集；
    • 同一时间，借用同一个值的不可变和可变引用不能共存；
    • 同一时间，借用同一个值的不可变引用可以存在多个，但可变引用只能存在一个。
  • 这样设计是为了内存安全，第一条为了避免引用时会出现值被提前销毁的情况，即垂悬指针（Dangling Pointer）问题。
  • 第二、三条是为了避免通过多个引用对同一个值进行的读写操作产生冲突。
  • Rust 在编译器会检查这些约束是否满足。

• 借用检查推迟到运行时

  • 对于运行时可变的值，可以将借用检查从编译器推迟到运行时，即运行时借用检查。
  • 仅仅是推迟，该检查的规则一个不少。通过调用对应数据结构提供的接口即可。
  • 通常使用 RefCell 包裹可被借用的值，随后调用 borrow 和 borrow_mut 便可发起借用并获得一个对值的不可变/可变借用的标志，它们可以像引用一样使用。
  • 为了终止借用，我们只需手动销毁这些标志或者等待它们被自动销毁。

综上，核心目的是为了不使用 unsafe ，并能够在运行时修改数据，即 Rust 中的 内部可变性 （Interior Mutability）。

• 具体修改策略

  • 使用 RefCell 来包裹 AppManager ，这样 RefCell 无需被声明为 mut ，同时被包裹的 AppManager 也能被修改。

• Sync

  • Rust 默认程序是多线程，所以提示需要标记 sync 。如果不标记 sync 的话 Rust 编译器会认为它不能被安全的在线程间共享。
  • 目前内核仅支持单核即单线程，Rust 会将变量分配在栈上作为局部变量，那么能否按照局部变量继续处理？
  • 实际上不行，后续会会增加并发，传递变量很麻烦。因此全局变量是最方便的。

• UPSafeCell

  • 在 RefCell 的基础上再封装一个 UPSafeCell 。即允许我们在单核上安全使用可变全局变量。
  • UPSafeCell 和 RefCell 一样提供内部可变性和运行时借用检查，只是更加严格。

• 使用方式

  • 访问数据时（无论读或）可以通过调用 exclusive_access 从而得到所包裹数据的独占访问权。
  • 操作完成后销毁这个标记便于下次使用。
  • 相比 RefCell ，不再允许多个读操作同时存在。

• 代码中两个 unsafe 原因

  • new 被声明为 unsafe 是因为希望创建 UPSafeCell 时不违反上述规则，即访问前先调用 exclusive_access ，访问后销毁借用。使用 new 能确保违背上述规则后 panic ，若不用 new 声明只能靠自觉。
  • 将 UPSafeCell 标记为 Sync 使得它可以作为一个全局变量，因为编译器无法确定 UPSafeCell 能否安全的在多线程间共享。加上后相当于向编译器保证。综上这样做主要是两方面因素：
    • 目前我们内核仅运行在单核上，因此无需在意任何多核引发的数据竞争/同步问题；
    • 基于 RefCell 提供了运行时借用检查功能，从而满足了 Rust 对于借用的基本约束进而保证了内存安全。

综上，使用了尽量少的 unsafe code 来实现了 AppManager 。

• 初始化 AppManager 的全局实例 APP_MANAGER

  • 找到 link_app.S 中提供的符号 _num_app 从中解析应用数量和各个应用起始地址。

• 引入 lazy_static! 宏解决初始化问题

  • 问题是全局变量在编译期需要设置一个初始值，但是有些全局变量需要在运行时才能确定初始值。
  • 手动实现很麻烦，例如将其声明为 static mut 会衍生出很多 unsafe 代码 。
  • 引入 lazy_static! 宏，借助 lazy_static! 声明了一个 AppManager 结构的名为 APP_MANAGER 的全局实例，且只有在它第一次被使用到的时候，才会进行实际的初始化工作。

借助 UPSafeCell<T> 和外部库 lazy_static! 能够以尽量少的 unsafe 代码完成可变全局变量的声明和初始化，且一旦初始化完成，在后续的使用过程中便不再触及 unsafe 代码。

• load_app

  • 此函数的具体作用是将参数 app_id 对应的应用程序的二进制镜像加载到物理内存以 0x80400000 起始的位置，这个地址是约定好的。
  • 清空内存，寻找待加载引用二进制镜像的位置并将其复制到正确位置。
  • 最后一行代码使用取指屏障指令 fence.i 保证之后的取值能够产生作用，取到最新的数据。
  • 硬件实现 fence.i 的方式不同，简单来说可以直接清空 i-cache 中所有内容或者标记其中某些内容不合法等等。
  • 这些问题在 K210 物理计算机上存在，在模拟器上没有。

• batch 子模块对外暴露出如下接口：

  • init ：调用 print_app_info 的时候第一次用到了全局变量 APP_MANAGER ，它也是在这个时候完成初始化；
  • run_next_app ：加载并运行下一个应用程序。当批处理操作系统完成初始化或者一个应用程序运行结束或出错之后会调用该函数。

4. 实现特权级的切换

下述内容主要讲解批处理系统如何同应用程序交互，完成特权级切换。

• 为什么要特权级切换？   - 因为批处理系统运行在内核态下，而应用程序运行在应用态下。   - 启动应用程序时需要初始化应用程序的用户态上下文，并能切换到用户态执行应用程序。   - 应用程序发出系统调用（Trap）后需要批处理系统接管。   - 程序执行出错时，需要批处理西戎杀死该应用并加载运行下一个应用。   - 当应用程序执行结束时，需要批处理系统加载运行下一个应用。

• 特权级切换相关的控制状态寄存器

  • CPU 通过 Trap 从用户态转为内核态。
  • Trap 用于从低级别向高级别转换，即用户态转为内核态，反之不行。
  • Trap 到内核态后，OS 就能使用与之相关的 CSR 寄存器来辅助。
  • sstatus 是 S 特权级最重要的 CSR，可以从多个方面控制 S 特权级的 CPU 行为和执行状态。

• 特权级切换

  • CPU 执行 Trap 类指令，例如 ecall 从而实现用户态转为内核态。
  • OS 处理完毕后，转为用户态，继续 ecal 下一条指令继续执行。
  • 程序切换前后需要维护上下文，例如某些寄存器值，需要将上下文保存在内存中。
  • 特权级切换一部分功能由硬件实现，另一部分功能由 OS 实现。

• 特权级切换的硬件控制机制

  • 用户态到内核态
    • sstatus 的 SPP 字段会被修改为 CPU 当前的特权级（U/S）。
    • sepc 会被修改为 Trap 处理完成后默认会执行的下一条指令的地址。
    • scause/stval 分别会被修改成这次 Trap 的原因以及相关的附加信息。
    • CPU 会跳转到 stvec 所设置的 Trap 处理入口地址，并将当前特权级设置为 S ，然后从Trap 处理入口地址处开始执行。
      • stvec 是一个 64 位的 CSR，在中断使能的情况下，保存了中断处理的入口地址。
  • 内核态到用户态，CPU 完成 Trap 处理返回时需要通过一条 S 特权级的特权指令 sret 来完成：
    • CPU 会将当前的特权级按照 sstatus 的 SPP 字段设置为 U 或者 S ；
    • CPU 会跳转到 sepc 寄存器指向的那条指令，然后继续执行。

• 用户栈与内核栈的作用，设计理念

  • 触发 Trap 后，CPU 在进入内核态处理 Trap 之前需要通过内核栈保存原始控制流的寄存器状态
  • 内核栈是由 OS 实现，应用程序运行时用到的是用户栈。
  • 区分内核栈和用户栈是为了安全，因为使用一个栈会导致应用程序读到 Trap 控制流的历史信息，例如内核函数地址，进而搞事情。
  • 在批处理系统中添加一段汇编代码，实现用户栈到内核栈切换，在内核栈上保存应用程序控制流的寄存器状态。
  • 声明两个类型 KernelStack 和 UserStack 分别表示用户栈和内核栈，都只是字节数组的简单包装。
  • 其中 USER_STACK_SIZE 和 KERNEL_STACK_SIZE 两个常数分别表示内核栈和用户栈大小，最终会以全局变量的形式实例化在批处理 OS 的 .bss 段中。
  • 随后为两个类型实现了 get_sp 方法来获取栈顶地址。在 RISC-V 中栈是向下增长的，只需返回包裹的数组的结尾地址即可。
  • 切换栈只需要将 sp 改为 get_sp 的返回值即可。

• Trap 上下文

  • 将 Trap 发生时需要保存的物理资源表示为 TrapContext ，在 Trap 发生时需要保存。
  • 其中包含三部分，分别是通用寄存器 x0~x31 ，还有 sstatus 和 sepc 。
  • 两条控制流（应用程序控制流和内核控制流）都会用到通用寄存器，虽然有些不用保存，此处直接保存了，没有刻意区分。
  • 对于 sstatus/sepc 存在 Trap 嵌套的可能，需要保存，并在 sret 之前恢复原样。

• Trap 管理

  • Trap 上下文的保存与恢复
    • 批处理操作系统初始化时需要修改 stvec 寄存器来指向正确的 Trap 处理入口点。

• Trap 分发与处理

  • 在 trap_handler 函数中完成分发和处理。

• 实现系统调用功能

• 执行应用程序

  • 批处理系统初始化完成或应用程序运行结束或出错时调用 run_next_app 函数切换到下一个应用程序。
  • 随后使用 sret、mret 等指令实现内核态转为用户态。

• 内核态转为用户态所做事情流程

  • 构造应用程序开始执行所需的 Trap 上下文；
  • 通过 __restore 函数，从刚构造的 Trap 上下文中，恢复应用程序执行的部分寄存器；
  • 设置 sepc CSR的内容为应用程序入口点 0x80400000；
  • 切换 scratch 和 sp 寄存器，设置 sp 指向应用程序用户栈；
  • 执行 sret 从 S 特权级切换到 U 特权级。

此后可以通过复用 __restore 的代码来更容易的实现上述工作。在内核栈上压入一个为启动应用程序而构造的 Trap 上下文，再通过 __restore 函数，就能让这些寄存器到达启动应用程序所需要的上下文状态。