- You are sharing something with others, but you don’t know it.

- Are you referring to … NTR?

0x00 Preface

稍微观看了一下后面的内容,Lab 4 在整个 6.828 当中可以说算得上是内容比较多的一次实验了。

不过这篇博客的篇幅与之前三篇相比会稍短,因为少了翻译 Intel 80386 Manual 的部分。

这次需要阅读的主要是多CPU支持的部分,也就是 APIC 的API。不过我也没读,因为懂不懂这个和实验的关系并不大,而且纯粹是硬件的API,实在是没什么意思。

所以,还是快点进入正题吧。

0x01 Part A: Multiprocessor Support & Cooperative Multitasking

所谓 *Cooperative Multitasking*,指的是一个用户环境(在现代操作系统语境下,进程)自愿地放弃自己当前占有的CPU,将它返还给内核,从而内核能够再次将CPU分配给其他的环境,基于这样的“自愿”机制而形成的多任务系统。

不过关于 Cooperative Multitasking 的实现细节先放一放,我们首先要完成多 CPU 系统的基础。

mmio_map_region

在多处理器系统中,由 L(ocal)APIC 来管理不同的CPU,在整个多 CPU 系统中分发中断,并且提供一个唯一的标识符来标志每个CPU。

一个处理器若要访问它的 LAPIC ,则需要使用 Memory-mapped I/O (MMIO)。LAPIC 的 MMIO base 在 0xFE000000 ,用起来不是特别方便,所以我们把它映射到 JOS 的 MMIOBASE 内存地址。

当然这部分并不需要我们去做,我们要做的是写一个函数 mmio_map_region,它的功能是创建一个 MMIO 映射区域,并且将映射后的地址返回。

实现上,参考之前的 boot_map_region 类似的方式来实现它就好,在申请页面时可以直接使用 boot_map_region

Application Processor Bootstrap

对称多处理器模型 当中,负责系统启动的CPU叫做 *Bootstrap Processor (BSP)*,而由 BSP 负责在操作系统初始化完毕后启动的称为 *Application Processor (AP)*。 BSP 由硬件自动选择。

Control Flow Transfer in Bootstrapping

首先,boot_aps 将启动代码 mpentry_start ~ mpentry_end 复制到 MPENTRY_PADDR 对应的内核虚拟地址位置,然后调用 LAPIC,将除了 BSP 以外的 CPU 设置到从 MPENTRY_PADDR 开始执行。注意这里使用物理地址的原因是, AP 目前为止还没有开启分页。

mpentry_start 部分的功能是,初始化各段寄存器,加载全局描述符表,进入保护模式。之后,初始化一个简单的页表,进入分页模式,然后跳转到 mp_main

mp_main 将真正的内核页表加载进 CR3 ,执行 LAPIC 初始化、用户环境初始化、中断初始化,并且将当前 CPU 设置为成功启动。

page_init Modifications

为了达到以上目的,我们需要修改 page_init,不将 MPENTRY_PADDR 的地址加入空闲页面列表。

这个就很简单,加个判断就好。

问题:

  1. MPBOOTPHYS 宏的功能是获得地址相对于 MPENTRY_ADDR 为基地址的地址。因为实际上AP都是由 MPENTRY_ADDR开始执行的,所以需要这样一个宏来正确产生 AP 需要引用的地址。

Per-CPU State & Initialization

这里的关键是,需要给每个 CPU 初始化一个单独的内核栈和初始化中断描述符表。

单独内核栈的功能是用于支持多CPU同时进入内核态,初始化中断描述符表的功能就不用赘述了。

mem_init_mp

这个函数的功能是,在 KSTACKTOP 下面给每个 CPU 分配一块大小为 KSTKSIZE 的空间,每块这种空间下面有一块 KSTKGAP 大小的未映射空间作为内存溢出保护。

我的实现是,使用 boot_map_region 进行空间分配,然后使用 page_remove 保证未映射状态。当然第二步是可以省略的,只是以防万一。

trap_init_percpu

这里的主要修改内容是,之前的 ts 全局变量不能用了,应当更换成 thiscpu->cpu_ts 。而且还要根据 cpuid 计算对应的描述符号,避免混乱。

一定要注意替换所有之前使用的可能在多 CPU 环境下出错的东西。

Big Kernel LOCK

我们的内核是在串行的环境下设计的,设计时也是按照串行执行设计的。因此,直接允许将它在多 CPU 上执行会产生严重的竞态。

为了避免这些情况,最暴力的解决方案是使用一个大内核锁,在每次陷入内核时加锁,退出内核时解锁,从而保证了内核本身是串行执行的。

以下情况需要对锁操作:

  • 在 BSP 启动其他 AP 前,加锁
  • 在初始化 AP 之后,加锁
  • 在中断从用户态陷入内核时,加锁
  • 在 env_run 回到用户态时,释放锁

如果加锁的时机不正确,则会导致死锁或者竞态。

实现的时候,只需要按照上面的时机进行加锁就好。

Round-Robin Scheduling

这里要实现一个 sched_yield 函数,功能是选择一个新的环境,然后执行它。

系统调用 sys_yield 将被分发到这个函数。实际上的功能就是放弃当前环境占有的 CPU。

实现上,sched_yield 的策略是这样的:首先,向后寻找一个可以运行(ENV_RUNNABLE )的环境。

如果没有找到,则从头开始直到当前环境寻找一个可以运行的环境。

都没找到,则判断当前环境是否可以运行,如果可以,那么就仍然运行它。

如果都不行,则进入 sched_halt ,代表无环境可运行,CPU挂起。到目前为止,挂起的CPU就无法再次使用了,当然后面我们有办法解决这个问题。

问题:

  1. 当然是内存映射在起作用。在所有环境中,内核高地址映射都是统一的。
  2. 环境结构中有个 Trapframe ,在产生中断时就已经保存进去了。

Env Creation Syscalls

既然已经实现了支持多用户环境之前的任务切换,那么我们也要有能力来创建多个用户环境。否则,任务切换就没有意义了。

接下来要实现一系列系统调用,它们是实现 Unix-style fork 的前导。

  • sys_exofork - 创建一个几乎空白的环境。它与调用它的父环境拥有相同的寄存器值,但是内存空间是完全空白的——什么映射都不存在。sys_exofork 将把刚刚创建完毕的环境设置为 ENV_NOT_RUNNABLE (显然),直到父环境将它重新设置为可运行为止。sys_exofork 将在父环境中返回子环境的 eid,子环境中返回0.
  • sys_set_env_status - 设置一个环境的状态为可运行或不可运行。注意它只能用于设置自身或自己的直接子环境。
  • sys_page_alloc - 分配一个物理页,并且映射到目标环境的指定虚拟地址处。
  • sys_page_map - 从一个环境的页表中复制一个映射到目标环境的页表中。
  • sys_page_unmap - 取消指定虚拟地址的页面映射。

这些系统调用的参数支持一个特殊环境ID值 0,指向当前环境。这个 candy 由内置函数 envid2env 提供。

实现上:

  • sys_exofork: 注意到 C 中函数的返回值保存在 eax 里就好了。非常简单。
  • sys_env_set_status: 关键在于使用 envid2env 的第三个参数检查是否能够更改目标环境。
  • sys_page_alloc: 需要检查给定的权限是否OK,以及想要映射的地址是否合法。检查完毕后,page_alloc + page_insert 一发就好。注意失败的情况下要释放那个页面。
  • sys_page_map: 其实就是检查有些繁琐而已。
  • sys_page_unmap: 这个就简单了,检查一下虚拟地址是否合法之后一发 page_remove 搞定。

0x02 Part B: CoW Fork

CoW 指的是 写时复制 (*Copy-on-Write*) 。

这个操作被广泛地应用于各类存储,包括内存、硬盘等。

写时复制的好处不用过多的说明,最常见的应用场景就是 fork + exec 素质二连,在 shell program 里被非常广泛地应用。在这种情况下,fork 如果复制整个父进程的内存空间会带来巨量的浪费,因为多数内容其实并不会使用——直接被 exec 抹掉了。当然有产生缺页中断开销等负面作用,不过实际上在大多数的应用场景下都是写时复制要更具有优势。

我们将在用户空间实现写时复制的 fork。为了实现这一功能,我们需要实现用户态的缺页处理例程。

sys_env_set_pgfault_upcall

实现上来说,检查入口点是否合法,检查是否能够操作目标环境即可。

Invoking User PGFLT Handler

Exception Stack

之前我们给用户环境在 USTACKTOP 位置分配了一个用户栈空间。不过我们现在需要一个用户异常栈,供用户态缺页异常处理例程使用。

为什么不直接使用用户栈呢?因为用户栈本身可能就是触发缺页异常的访问。而用户异常栈本身可以完全交由内核来保证它的可访问性。i.e. 在 CoW fork 的时候,将会把用户栈置为*写时复制*状态。此时对用户栈的写操作会触发缺页异常,内核拉起用户态缺页中断处理例程,但是此时如果用户态缺页中断处理例程使用用户栈,那么将无法工作。

Exception Stack Frame

首先是一个空的4字节数据,然后是 struct UTrapframe

注意如果是嵌套的缺页中断处理,新的栈应该从 tf->esp 而不是 UXSTACKTOP 开始。

发现这件事情的方法是检测 tf->espUXSTACKTOPUXSTACKTOP-PGSIZE 的关系。

page_fault_handler

实现上,将数据正确压栈后,修改 curenvespeip 值为正确的数值,然后直接 env_run 将它拉起就可以了。

User-mode PGFLT Handler Entrypoint

我们需要一个入口点来为用 C 编写的用户态缺页异常处理例程做进入前的准备,并在它退出后返回产生异常的指令位置继续执行,这样就不需要再次经过内核了。

为了达成这个目的,这个入口部分必须正确的完成用户栈和异常栈的切换和 eip 的设置工作。

实现上,首先压当前的 esp(作为参数的指针使用),然后 call 中断处理例程。

返回后,首先清理参数,然后一次移除 struct UTrapframe 中不再需要使用的部分,恢复需要恢复的部分,最后执行 ret ,处理器读栈上最后的 eip 等信息进行返回。

User Library Functions

最后就是在用户的 C 库中提供用于设置缺页中断处理程序的例程了。这部分的实现较为简单,所以在此略过。

Implementing CoW Fork

现在我们已经有了足够的工具来在用户态实现写时复制的 fork 了。

整个 fork 分为三部分:forkduppagepgfault

fork 是提供给用户程序使用的,当一个环境调用它时,它将:

  1. 将调用环境的缺页中断处理例程设置为 pgfault
  2. 调用 sys_exofork 来创建子环境
  3. 将两个进程的所有 UTOP 以下的,处于可写或者 CoW 状态的页面设置为 CoW 状态。这里的顺序是有要求的,需要注意。这里 CoW 状态和普通的只读状态是有区别的,使用了页表项中 CPU 没有使用的位。这里的操作由 duppage 完成。
  4. 为子环境分配一个新的异常处理栈。
  5. 设置子环境的缺页中断处理例程。
  6. 将子环境设置为可以运行。

当父环境或者子环境触发了缺页中断后,中断处理例程将会:

  1. 检查是否是由写请求触发,检查目标页面是否是 CoW 状态。如果不是,这意味着这很可能是一次非法访问。此时,pgfault 触发一个 user panic
  2. 否则,在目标位置分配一个新的页面,然后将原先页面的内容复制进去。

实现上,需要注意的点有:

  1. 在调用 duppage 前,fork 遍历经过所有页面,必须首先检查初级页表项是否存在。
  2. duppage 必须正确设置可写/CoW页面和原只读页面在复制之后的权限。

0x03 Part C/1: Preemptive Multitasking

使用抢占式多任务机制的重要性不言而喻:它可以极大程度上简化应用程序的开发(不需要理解 yield ),并且可以有效对抗那些陷入了无限循环的程序。

有意思的是,MacOS 在 2002 年以前的版本并不支持抢占式多任务,而是要求所有的开发者在应用中周期性地放置 yield。在当时,如果你运行一个死循环程序,并不在循环体中 yield,那么整个操作系统将失去响应。

External Interrupts Mechanism

IRQ 的细节我就不在这里说了,我们只需要知道:

  1. IRQ 中断的起始位置放置在了 IRQ_OFFSET
  2. 为了简化实现,进入内核后,所有的外部设备中断将被关闭。退出后,再被打开。

实现上就是一个简单的 映射工作,就不在这里细说了。

Preemption by Clock Interrupts

这个可太简单了。直接将分发到的时钟中断调用 sched_yield 就好。

0x04 Part C/2: Inter-Process Communication

IPC in JOS

在 JOS 中,一个环境若想向另一个环境发送消息,目标环境必须首先使用 ipc_recv 进入接收状态,此时内核将会将它移除调度。接下来源环境将使用 ipc_send 发送消息。消息的内容是一个 32 位的值和一个可选的页面映射。其中 ipc_recv 是系统调用 sys_ipc_recvipc_send 是系统调用 sys_ipc_try_send 的包装。

每个环境都可以给一个已经进入接收状态的环境发送消息。

当发送一个页面映射时, sys_ipc_try_send 将负责把将要发送的页面映射到目标环境的页表中。

当产生错误(如:目标环境不在接收状态时),sys_ipc_try_send 将返回一个错误。

Implementation …?

按照惯例,接下来应该是讲实现要点的时候了,但是……

0x05 Part C/3: Challenge - Non-Loop Send

在实现中,我们发现:如果一个环境试图向另一个可能在一段时间之后进入接收状态的环境发送消息,那么它只能不断地循环执行 ipc_send ,直到发送成功为止。这显得很蠢,也是对 CPU 的一种浪费。

这里,我试图采用这样一种机制:当一个环境执行 ipc_send 后,将它移除调度;当目标环境进入接收状态后,再将源环境拉起。

具体的实现如下:

  1. 修改 struct Env ,在里面增加一个用于记录等待环境的字段。
  2. 增加一个系统调用 sys_ipc_listen,调用时记录等待环境的 id,并且将自身移除调度。
  3. 当一个环境进入接收状态时,遍历所有环境,寻找正在等待自身的环境,将首个遇到的环境拉起。
  4. 当进入内核调度过程时,检查正在监听其他环境的环境的目标环境(有点绕)是否已经进入接收,如果是的话将他拉起。
  5. 最后,在用户端 C 库函数中,首先调用 ipc_listen ,然后调用 sys_ipc_try_send

这样的实现和暴力实现相比会有些慢,猜测时间差消耗在依赖内核调度过程拉起正在等待其他环境的环境上了。

这样整个 Lab 4 就结束了。还是挺有意思的(笑