This lab is all about fixing hidden bugs in previous labs.

I’m not joking.

0x00 Preface

Lab 5 的主要内容与文件系统有关,包括一个极简单的文件系统(大部分还不需要你来实现),用于创建新进程并执行文件系统上程序的 spawn(大部分也不需要你来实现),以及一个简单的交互式用户界面 shell (大部分仍然不需要你来实现),所以这次 lab 的内容其实比较少。但是由于在这个过程中发现了一些隐藏在之前 lab 中的 bug,所以篇幅上看应该并不会比 Lab 4 小多少。

那么,还是进入正题吧。

0x01 File System Preliminaries

我们将要在 JOS 上实现的文件系统是非常简单的文件系统,不过它已经能够支持基本的文件系统操作: creatopenreadwriteremoveclose

但是由于我们基本上在写一个不支持多用户的操作系统,所以很大一部分与用户管理和权限控制的特性将不会在这个文件系统上实现,如:权限控制、所有者。还有一些高级的文件系统特性不会被实现,如软/硬链接、文件时间戳和特殊的设备文件。

On-Disk File System Structure

我们的文件系统将以什么样的形式存储在磁盘上呢?

多数 UNIX 文件系统都将磁盘划分为两个区域:一个区域用于存储 inode, 一个区域用于存储数据。但是在这里我们为了简化(不需要实现软硬链接!),所以我们将不使用 inode,而是直接以类似树的形式存储文件系统信息。文件夹中包含指向文件或文件夹的链接(由目标的 type 决定),文件包含指向所存储的数据的块的链接。

Sectors and Blocks

多数磁盘不支持以字节为单位进行I/O,相对地,它们的 I/O 以 sector 为最小单位。在这个环境下, 1 sector = 512 Bytes 。在上层,文件系统以 block 为单位管理底层磁盘,而 block 一般是 sector 的数倍大小。在 JOS 中,为了简化实现,我们选择 1 block = 4096 Bytes = 1 page

Superblocks

文件系统通常在一个特殊的位置保存与整个文件系统有关的信息。这个位置叫做 superblock

JOS 将以一个 block 的空间来保存 superblock 。它将是 block 1,因为 block 0 一般用于保存分区表和启动信息。现代的文件系统一般会使用更多的 block 来保存 superblock

+------------------------+ <-- Block N
|  File/Dir Data Blocks  |
|                        |
|                        |
+------------------------+ <-- Block enough to hold it
|    Free Block Bitmap   |
|                        |
+------------------------+ <-- Block 2
|        Superblock      |
+------------------------+ <-- Block 1
|Boot Sector; Part. Table|
+------------------------+ <-- Block 0
     * The JOS DISK! *

0x02 The File System!

具体来说,这个文件系统我们将要实现以下的部分:

  • 块缓存 block cache 以及写回机制
  • 磁盘块的分配工作
  • 文件内偏移到磁盘块的映射
  • IPC 的基础上实现 readwriteopen

Disk Access

那么,我们首先需要一个硬盘驱动来供我们直接访问底层硬件。

这有两种方式:一是将其写进内核中,并且提供相应的系统调用来支持这个工作;另一种就是将其整个扔进一个用户环境(进程)中,并给予它做硬件 I/O 的权力,让它来管理整个文件系统以及和硬盘的交互。JOS 采用的是后一种实现。

硬盘驱动已经提供好了,我们要做的就是给对应的用户环境以 I/O 权限。具体来说,是在 env_create 的时候,检查 env_type == ENV_TYPE_FS 。注意 env_create 是内核函数,所以并不会存在用户越权问题。

The Block Cache

JOS 的块缓存利用了 x86 的虚拟内存机制。具体来说,是将整块硬盘空间映射到一块内存上,对硬盘的访问转化为对内存的访问(因此它只能支持最大 3GB 的硬盘)。当访存触发缺页时,将对应的数据从硬盘读入内存。

这个块缓存还提供了一个函数 flush_block 用于强制同步内存和硬盘的指定页面。

具体到实现上,只需要注意触发访存错误的地址不一定是对齐的,并在 flush_block 真正写回之前检查一下对应页面的 Dirty 状态,写回之后清除 Dirty 即可。

The Block Bitmap

block bitmap 用于记录块的使用状况。具体来说,是将块 ID 映射到这个 bitmap 的一个位上,用于节省空间地记录块的使用状况,以便于分配新的块和回收旧的块。现代文件系统基本都使用同样的结构来记录磁盘块。

这里我们需要参考 free_block 的做法来操作 block bitmap ,以实现 alloc_block

实现上,需要注意的是清除一个位并没有设置一个位那么直观,需要稍微注意。还有一点需要注意的是,分配块之后需要写回 block bitmap

File Operations

大体上的文件操作已经提供了,但是我们需要完成从文件偏移到磁盘块的映射工作,以及访问文件时的磁盘块分配工作。具体来说,就是 file_block_walkfile_get_blockfile_block_walk 将偏移转化为文件结构体 struct File 中对应的指针,而 file_get_block 更进一步,它将直接获得对应磁盘页面。

实现上,要注意新分配磁盘页面需要初始化的问题。其他的都问题不大。

这里一开始写的时候就算忘记初始化也问题不大,因为 make grade 的时候总是会创建全空的磁盘。

但是自己的实现到底清不清真还是请注意一下(。

The File System Interface

现在我们有一个可以用的文件系统环境了。但是这还不够,我们想要让其它用户环境能够操作磁盘上的文件。对此,JOS 使用的是 IPC 进行解决。即:用户环境发送特定的 IPC 给文件系统环境,文件系统环境代为执行文件 IO 操作。

具体的 IPC 格式就不再详述(因为知道了用处也不大),server_read 函数只需要调用 openfile_lookup + file_read 即可,注意要改变 fd_offset

但是!在运行测试的时候发现了第一个来自之前 lab 的bug 。爆的是 IPC ,原因来自:

// a line of code from kern/syscall.c: sys_ipc_try_send()
if(((uintptr_t)srcva < UTOP) && ((uintptr_t)dstenv->env_ipc_dstva < UTOP)) {
    // do things like page-mapping
}

这一个判断用于检测发送的 IPC 是否包含一个页面映射,如果包含,则映射过去。

但是我一开始在 Lab 4 写的代码是错的,中间的 && 条件误写成了 || 。最终导致的问题就不用多说了吧,中间调用的内存映射函数爆 -E_INVAL 退出,导致无页面传递的 IPC 无法发送成功。

太真实了吧!测试工程师!为什么上个 Lab 的测试程序没有发现这个问题啊??

– IPC bug x1

接下来要实现的是 serve_writedevfile_writeserve_writeserve_read 类似,直接调用 openfile_lookup + file_write 来实现即可。 devfile_write 需要稍微观看一下 union Fsipc 的定义,然后设置正确的内容即可。注意这里当写出的内容多于一个 block 可以发送的内容时,有两个解决方案:一是直接返回,二是反复 IPC,直到所有需要写出的内容都成功写出为止。这里我写的是第二种。如果使用第二种的话,需要注意返回值应当是总共成功写入了多少字节。

当然在这里写完之后,运行测试程序的时候我遇到了另一个问题,就是内核无法正确判断何时将不会再有环境能够执行。出现这个问题的原因是之前做的 Challenge 修改了 IPC 体系,增加了一个 Listen 状态。

// a bunch of code copied from kern/sched.c
// scan through all envs to find if there's env have the potential to run or is running.
	for (i = 0; i < NENV; i++) {
		if ((envs[i].env_status == ENV_RUNNABLE ||
		     envs[i].env_status == ENV_RUNNING ||
		     envs[i].env_status == ENV_DYING ||
			 envs[i].env_ipc_recving ||
			 envs[i].env_ipc_listening)){
			break;
			 }
	}
// NENV means the search reaches the end. Nothing found.
	if (i == NENV) {
		cprintf("No runnable environments in the system!\n");
		while (1)
			monitor(NULL);
	}

乍一看好像没啥问题,毕竟处于 recvinglistening 的状态的用户环境都有可能重新回到执行状态。但实际上并不是这样。为什么不是这样?这个问题留给读者(笑

总之,解决方法就是注释掉 envs[i].env_ipc_recving || 这一行。在此之后,内核就可以正确发现这个问题了。

上个 Lab 的测试程序???????

– sched bug x1

0x03 Spawning Processes

与传统的 UNIX-likefork+exec 不同, JOS 采用了另外一种方式来从磁盘可执行文件创建新的用户环境,即与 Windows CreateProcess 类似的 spawnspawn 将调用 sys_exofork ,读取可执行文件内容并且设置,然后调用 sys_env_set_trapframe 来替换子环境的执行状态,使其指向特定的入口点。

至于难以实现 exec 的原因,我认为应该在如何在保持已经读入的将被执行可执行文件内容的同时无效化并初始化其他的内存空间。这在没有特定的系统调用的基础上应该是难以做到的。

这里我们需要实现 sys_env_set_trapframe 系统调用。利用 envid2env 检查环境 id 后,使用 user_mem_assert 判断参数是否有效,然后为了防止越权行为,正确地重新设置目标 trapframe 中的 CS DS ES SS 寄存器以及 eflags 寄存器。注意这里要将 IO 特权级置为0其实相当违反直观。

运行测试, BUG 又出现了。问题出在上一个 Lab 的 Challenge 身上。为了保证当一个环境先进入 ipc_recv 状态,另一个环境后进入 ipc_listen 状态时,发送环境能正确被拉起:

// a bunch of code copied from kern/sched.c: sched_yield()
	// find a runnable env
	for(int curr=prev_env_id+1;curr<NENV;curr++){
		if(envs[curr].env_status == ENV_RUNNABLE){
			env_run(envs+curr);
		}
	}
	// not found ! restart searching
	for(int curr=0;curr<=prev_env_id;curr++){
		if(envs[curr].env_status == ENV_RUNNABLE){
			env_run(envs+curr);
		}
	}
	// is there wating ipcs?
	for(int i = 0; i<NENV; i++){
		if(envs[i].env_ipc_recving == 1){
			int tmpenvx = -1;
			bool runnable = true;
			for(int j=0;j<NENV;j++){
				if(envs[j].env_ipc_listening == envs[i].env_id){
					if((envs[j].env_status == ENV_NOT_RUNNABLE) && (tmpenvx == -1)) tmpenvx = j;
					if((envs[j].env_status == ENV_RUNNING) || (envs[j].env_status == ENV_RUNNABLE)){
						runnable = false;
						break;
					}
				}
			}
			// resched succ
			if(tmpenvx != -1 && runnable){
				// do the execute stuff
			}
		}
	}
	// no possibilities. have to continue execute myself.
	if(prev_env != NULL && prev_env->env_status == ENV_RUNNING){
		env_run(prev_env);
	}

这段代码用于当一个环境被抢占或者由于等待 IPC 被退出调度(都使用的 sched_yield() )后发现下一个可执行的环境的。中间有一大片是用来得到上述的情况,并且拉起 listen 状态环境的。但是这段代码是存在问题的。它会在某些情况下导致严重的调度失败。至于是什么问题?这个问题留给读者好啦

– sched bug x2

Sharing Library State across Fork and Spawn

现在,我们试图在 forkspawn 创建的子环境和父环境之间共享文件描述符。注意文件描述符将被存储在用户内存空间。考虑我们现在的实现:当 fork() 时,这段空间将被标记为写时复制。当 spawn() 时,这段空间将被彻底清除。fork() 将导致子环境无法享有非自己打开的文件描述符,spawn() 将使新环境一开始不打开任何文件描述符。现在我们试图控制此种行为。

JOS 使用了页表项中另外一个可供系统软件使用的位,定义为 PTE_SHARE 。所有标记 PTE_SHARE 的页面将被原样映射过去。

实现上来说,我们需要遍历所有页表项,判断该项是否有 PTE_SHARE 存在,若有,则调用 sys_page_map 将其映射过去。注意权限需要利用 PTE_SYSCALL 从原页表项复制得到。

0x04 The Keyboard Interface

在让我们的 shell 工作之前,我们必须得有办法得到来自键盘的输入,并将其分发到用户环境。

之前的 monitor 要求内核一直在运行,但是这是不可能的。所以我们必须要利用中断来处理键盘输入。至于如何处理是硬件 API 问题, JOS 已经帮我们写好了。我们只需要将中断 IRQ_OFFSET+IRQ_KBDIRQ_OFFSET+IRQ_SERIAL 分发到 kbd_intr()serial_intr() 就可以自动传递到用户环境。

0x05 The Shell

终于要开始实现我们自己的 shell 了!……才怪。大部分的代码都已经是写好了的,我们需要做的仅仅是补齐输入重定向的代码。毕竟输入处理大概已经超出了这门课的范围(笑

至于如何做呢?如果你完全不了解这方面的知识……请照着输出重定向照葫芦画瓢写一个就好了。

至于有一些了解的(或者完全不了解但感到好奇的)人……如果你确实看不明白,我还是给点提示算了w

首先是 gettoken() 。它会直接把输入的下一个 token 扔进 t 里。

接下来是 dup() 。请打开你的 Linux 终端,输入 man dup2 。是的,就和它功能差不多。

这两点明白了之后,应该就能理解应该怎么做和为什么这样做了。

那么下面是重头戏(笑

这个实现了之后,运行测试,我竟然又发现了之前 lab 的两个 bug 。可以说是真实恐怖故事了。

第一个问题出在系统调用 sys_page_alloc 。出问题的原因是……我没有把新分配的页清零。话说这种问题不应该在上一个 lab 的测试里检查出来吗??

– syscall bug x1

第二个问题则又是 Challenge 的问题。(由于没有一个清真的调度器)并且为了保证 ipc_listen 状态的环境能够被高效地拉起,我在当一个环境调用了 sys_ipc_recv 系统调用时,在真正退出调度之前增加了一步遍历所有环境,找到正在 listen 当前环境的环境,将其拉起的操作。那么问题来了,当出现如下的执行序列时

[ENV 0]        LISTEN ENV 2
<----------- env 0 yield, switch to env 1
[ENV 1]        LISTEN ENV 2
<----------- env 1 yield, switch to env 2
[ENV 2]        RECV
[ENV 2]        PULL ENV 0
<----------- env 0 kick in, but before it can do anything
<----------- timer interrupt, scheduler kick in
[SCHED]        FOUND ENV 1 LISTEN ENV 2 && ENV 2 RECV
[SCHED]        PULL ENV 1
<----------- env 2 kick in
[ENV 1]        CHECK ENV 2 RECV STATE
[ENV 1]        SEND TO ENV 2
[ENV 1]        CLEAR ENV 2 RECV STATE
<----------- timer interrupt, scheduler kick in
[SCHED]        FOUND ENV 0 RUNNABLE (pulled by env 2 before, preempted by timer)
[SCHED]        PULL ENV 0
<----------- env 0 kick in
[ENV 0]        CHECK ENV 2 RECV STATE
[PANIC]        env 0 woken but found env 2 not recving.

会导致有一个 ipc_listen 状态的环境错误地被拉起。最终的解决方案是将 ipc_recv 状态变成了三个子状态,分别是 ipc_recv_waitipc_recv_halfawakeipc_recv_scheduled 。第一个状态代表调用 ipc_recv 时没有发现正在 listen 它的环境,等待调度器拉起,第二个状态是代表调用 ipc_recv 时找到并拉起了正在 listen 它的环境,第三个状态是代表已经由某次调度器执行找到并拉起了正在 listen 它的环境。

– sched bug x1

这样,shell 就可以正常执行了(大概,至少测试过了(笑

0x06 Challenge: Block Cache Eviction

其实读者在阅读前面的内容的时候应该已经注意到了,磁盘块缓存并没有换出策略。也就是说,当访问的磁盘块数目逐渐增加,到一定程度后系统将会面临 OOM 的危机。因此有必要增加换出策略。

我的实现是一种比较简单的方式,即每隔一定 block_alloc 访问次数或者当 block_alloc 无法分配新内存页时触发,扫描所有在内存中的磁盘数据,将 dirty 的页面写回,将没有标记 accessed 的页面取消映射,之后对没有取消映射的页面清除这两个标记。

确实非常简单暴力,应该性能上也不会太好的样子。不过至少我们完成了(笑

这样整个 Lab 5 就结束了。接下来就是 Lab 6 网络 和 Lab 7 了。

至于 Lab 7 我要做什么……(笑