bookstack

实验手册

介绍

这个实验,会实现spawn,这个库可以加载和运行磁盘可执行文件。你也可以在控制台上运行shell。这些特征需要一个文件系统,这个实验也会介绍简单的读写文件系统

开始

跟之前一样,切换到lab5分支,然后merge

主要的几个文件需要了解一下:

  • fs/fs.c 在磁盘上操作文件系统的代码
  • fs/bc.c 构建在用户级别错误处理工具之上的简单区域缓存
  • fs/ide.c 最小基于PIO(non-interrupt-driven)IDE驱动代码
  • fs/serv.c 使用文件系统进程间通信的文件服务器
  • lib/fd.c 实现类UNIX系统的文件描述符
  • lib/file.c 磁盘文件类型的驱动,实现了作为系统IPC的客户端
  • lib/console.c 控制台输入输出类型驱动
  • lib/spawn.c spawn库调用的骨架代码

实验要求

没有什么必要看

文件系统预备知识

这个文件系统比大多数真实的文件系统(包括xv6 UNIX)更简单,但是也足够提供一些基本特征:在一个分层的目录结构中,创建,读,写和删除文件

我们正在开发一个单一用户的操作系统,这提供了足够的保护来获取bug,但是没有足够的多用户操作的保护。因此,文件系统也不支持UNIX观念的文件归属和权限。我们的文件系统也不支持硬链接,软链接,时间戳和特殊设备文件

磁盘文件系统结构

大多数UNIX文件系统把可用的磁盘空间划分成两种主要的区域类型:节点区域(inode)和数据区域(data)。UNIX文件系统分配一个inode给每个文件;文件的inode保存了文件重要的元数据,比如stat属性指向了数据块。数据区域被分为更大的数据块(通常是8KB或更大),数据块里面保存了文件数据和目录元数据。目录入口包含文件名称和节点指针;一个文件也可以说是硬链接的,如果文件系统中多个目录入口指向那个文件节点。因为我们的文件系统不支持硬链接,因此我们可以进一步简单化:我们的文件系统不使用节点,而是用描述文件的文件入口来保存所有文件的元数据

文件和目录是由一系列的数据块组成的,就像虚拟地址空间能够分散在整个物理内存一样,文件和目录也可以分散到整个磁盘。文件系统环境隐藏了数据块结构的细节,提供了读和写字节的接口。文件系统环境在内部处理对目录的所有修改。我们的文件系统允许用户环境去读取目录元数据,意味着用户环境能自己执行目录扫描操作,而不是必须依赖于额外的系统调用。这个目录扫描方法的缺点是让应用程序依赖于目录元数据格式,这让不修改应用程序的同时,修改文件系统内部结构变得困难,这也是现代UNIX不太推荐的做法

扇区和数据块

大多数磁盘读写都是以字节为单位而不是以扇区为单位。在JOS中,每个扇区是512字节。文件系统实际上分配和使用磁盘存储是一块为单位的。注意两个术语的区别:扇区大小是磁盘硬件属性,而块大小是操作系统使用磁盘的方式。一个文件系统块大小必须是扇区大小的倍数

UNIX的xv6文件系统使用一个块大小是512字节,与磁盘扇区大小是一致的。因为现在存储空间获取更加便宜同时以更大的单位管理磁盘也很有效,所以大多数现代文件系统使用一个更大的块大小。我们的文件系统数据块使用4096个字节,有效映射处理器页面大小

超级块

文件系统通常在磁盘的"easy-to-find"位置(比如开始或结束位置)保留固定的磁盘块来保存描述文件系统属性的元数据,比如块大小,磁盘大小,需要查找根目录的任何元数据,上次安装文件系统时间,上次检查错误的文件系统时间等等。这些特殊块称为超级块(superblocks)

我们的文件系统只有一个超级块,在磁盘上总是为数据块1。它的结构定义在inc/fs.hstruct Super。数据块0通常保留为引导程序和分区表,所以文件系统通常不使用第一个磁盘块。很多真正的文件系统保留多个超级块,以便于其中一个异常了或者磁盘区域损坏,其他超级块仍然可以使用

文件元数据

在我们文件系统中描述文件的元数据结构定义在inc/fs.hstruct File。这个元数据包含了文件名,大小,类型(通常是文件或目录)和组成文件块指针。正如上面提到的,我们没有inodes,所以元数据保存在磁盘的目录入口。不像大多数真正的文件系统,我们使用一个File结构体来代表文件元数据。

struct Filef_direct数组包含了存储文件前10个块(NDIRECT)的块序号空间,也称为文件的直接(direct)块。对于不超过 $10*4096=40KB$ 的小文件,这意味着所有文件块的块号将直接适应File结构体本身。对于大文件,需要有位置放置文件块号的其他部分。对于大于40KB的任何文件,需要分配额外的磁盘块,称为文件非直接块(indirect),来保存 $4096/4 = 1024$ 额外块号。因此我们文件系统允许文件超过1034个块,或者略高于4MB大小。为了支持更大的文件,真正的文件系统通常支持双和多非直接块

目录与常规文件

我们文件系统的File结构体能够表示普通文件和目录;这个由结构体中type字段来区分。文件系统处理常规文件和目录是一致的,除了它不解释普通文件与数据块内容相关联,然而文件系统解释目录文件内容作为一系列的File结构体来描述子目录

文件系统的超级块包含了File结构体,保留了文件系统根目录的元数据。这个目录文件的内容是一系列描述位于文件系统根目录下文件和目录的File结构体。任何子目录可能包含更多File结构体代表子子目录等等

文件系统

这个实验的目标不是实现整个文件系统,只是实现关键组件。尤其是读取块到块缓存,然后刷新到磁盘的实现;分配磁盘块的实现;映射文件偏移到磁盘块的实现以及IPC的读写打开的操作。因为不需要实现所有文件系统,熟悉已有的代码是非常重要

磁盘访问

在我们操作系统的文件系统环境需要能访问磁盘,但是在内核中,我们没有实现任何磁盘访问功能。我们实现IDE磁盘驱动作为用户级别文件系统环境,而不是采用传统的"单体"操作系统策略(向内核添加IDE磁盘驱动,通过系统调用来访问磁盘)。仍然需要稍微修改一下内核,以便于文件系统环境有权限实现磁盘访问

只要我们依赖轮询,基于"可编程的I/O"(PIO)磁盘访问和不需要使用磁盘终端,在用户空间实现磁盘访问时非常简单的。在用户模式下,实现中断驱动的设备驱动是可能的(如lab3和lab4的内核代码),但是由于内核必须拦截设备中断并分发给正确的用户模式环境,所以实现也比较困难

x86处理器使用EFLAGSIOPL位寄存器来决定保护模式代码是否允许处理设备I/O指令,比如INOUT指令。由于我们需要访问的所有IDE磁盘寄存器都位于x86的I/O空间而不是映射的内存里,为了让文件系统访问这些寄存器,把I/O特权给文件系统环境是需要做的唯一一件事。实际上,EFLAGS寄存器的IOPL位给内核提供了一个简单的"all-or-nothing"的方法来控制用户模式是否可以访问I/O空间。在我们的案例当中,我们想文件系统环境能访问I/O空间,但是不想其他的环境访问I/O空间

进行练习1

注意GNUmakefile通过使用文件obj/kern/kernel.img作为磁盘0的镜像,obj/fs/fs.img作为磁盘1镜像来设置QEMU。这个lab,文件系统应该只使用磁盘1;磁盘0只能用作启动内核。如果你打算毁坏任意一个磁盘镜像,你需要重置他们两个,可以使用

rm obj/kern/kernel.img obj/fs/fs.img
make

或者

make clean
make

块缓存

在我们的文件系统中,我们将在处理器虚拟内存系统的帮助下,实现一个简单的缓冲区。块缓存的代码在fs/bc.c

我们的文件系统将被限制处理磁盘大小为3GB。我们保留一个大的,固定的3GB文件系统环境地址区域(从0x10000000(DISKMAP)到0xD0000000(DISKMAP+DISKMAX))作为磁盘的内存映射版本。例如磁盘块0映射到虚拟地址0x10000000开始映射,磁盘块1映射到虚拟地址0x10001000fs/bc.cdiskaddr函数实现了从磁盘块号到虚拟地址的转换

因为我们的文件系统环境有自己的虚拟地址空间(独立于系统中所有其他环境的虚拟地址空间),文件系统环境需要做的唯一一件事就是实现文件访问,所以保留大多数文件系统环境的地址空间是合理的。由于现在的磁盘都会超过3GB,因此在32位机器上实现真正的文件系统是会很尴尬的。这样一个缓冲区管理方法可能在64位机器上也是有效的

当然,读取整个磁盘到内存会耗费很长的时间,所以我们将实现按需分野的形式,其中,我们只有在这个区域发生页面错误的时候,才在磁盘映射区域分配页面和从磁盘读取相关块。这样,我们能阻止整个磁盘都在内存中

进行练习2

fs/fs.c中的fs_init是使用块缓存的主要例子。在初始化块缓存之后,在super的全局变量里保存了指向磁盘映射区域的指针。之后,我们能从super结构体中读取,就像是从内存读取一样,我们的页面错误处理程序会在需要的时候从磁盘读取

块位图

fs_init设置了bitmap指针之后,我们可以把bitmap当作一个压缩的位数组,对应于磁盘上的每一个块。例如,block_is_free校验给定的块是否是空闲的

进行练习3

文件操作

我们在 fs/fs.c 中提供了各种函数来实现解释和管理文件结构、扫描和管理目录文件的条目以及从根遍历文件系统以解析绝对路径名所需的基本工具。阅读所有fs/fs.c的代码,确保理解

进行练习4

file_block_walkfile_get_block是文件系统的主力。例如,file_readfile_write都是上面file_get_block的调用,用于分散的块和顺序缓冲区之间的字节复制

文件系统接口

既然在文件系统环境内部有必要的功能了。我们必须让它能被其他想要使用文件系统的环境访问。因为其他环境不能直接调用文件系统环境中的函数,所以我们通过远程程序调用(RPC)来暴露文件系统环境的访问权限。一个RPC调用文件系统服务如下:

 Regular env           FS env
   +---------------+   +---------------+
   |      read     |   |   file_read   |
   |   (lib/fd.c)  |   |   (fs/fs.c)   |
...|.......|.......|...|.......^.......|...............
   |       v       |   |       |       | RPC mechanism
   |  devfile_read |   |  serve_read   |
   |  (lib/file.c) |   |  (fs/serv.c)  |
   |       |       |   |       ^       |
   |       v       |   |       |       |
   |     fsipc     |   |     serve     |
   |  (lib/file.c) |   |  (fs/serv.c)  |
   |       |       |   |       ^       |
   |       v       |   |       |       |
   |   ipc_send    |   |   ipc_recv    |
   |       |       |   |       ^       |
   +-------|-------+   +-------|-------+
           |                   |
           +-------------------+

虚线下方的所有内容只是从普通环境到文件系统环境获取读取请求的机制。最开始,read工作在任何文件描述符上且仅仅分发到合适的设备读取函数,这种情况下是指devfile_read(我们能有更多的设备类型,比如管道)。devfile_read为磁盘文件实现了read。这个和其他在lib/file.cde devfile_*函数实现了FS操作的客户端,所有的工作几乎是相同的,绑定一个请求结构体,调用fsipc发送IPC请求,然后解包返回结果。fsipc函数处理了发送请求给服务器和接收返回的基本细节

文件系统服务器代码在fs/serv.c。在server函数中循环,收到一个IPC请求时,分发这个请求给合适的处理函数,然后通过IPC发送返回结果。在一个读的例子中,serve调度到server_read,它将处理特定读取请求的IPC细节,比如解包请求结构体并最终调用file_read实际读取文件

回忆一下,JOS的IPC机制允许一个环境发送32位数字和可选择的分享一个页面。为了从客户端发送请求到服务端,我们使用32位数字来代表请求类型(文件系统服务的RPC序号,就像系统调用的序号一样),用union Fsipc来保存请求参数,最后通过IPC分享页面。在客户端一侧,我们总是在fsipbuf分享页面;在服务端一侧,我们在fsreq(0x0ffff000)映射进来的请求页面

服务端也是通过IPC发送响应。我们使用32位数字作为函数返回码。对于大多数RPC,这是他们返回的所有。FSREQ_READFSREQ_STAT也返回数据,这个仅仅写到客户端发送的请求页面。没有必要在响应IPC中返回这个页面,因为客户端最开始已经和文件系统服务端共享了这个页面。同样的,在响应中,FSREQ_OPEN共享了客户端一个新的Fd page。我们会返回所有文件描述符页面

进行练习5

进行练习6

Spawning Processes

已经给出了spawn代码,它可以创建一个新环境,从文件系统加载一个程序镜像到里面,然后启动子环境来运行这个程序。父进程继续独立于子进程执行。spawn函数表现和在UNIX中紧随在fork之后且在子进程中执行的exec一样

我们实现spawn而不是一个UNIX风格的exec,因为spawn更容易从用户空间exokernel fashion方式实现,而不需要内核的帮助。想一想为了在用户空间实现exec,你需要做什么,确定你理解了为什么它会更难

进行练习7

forkspawn的共享库状态

UNIX文件描述符是一个通用的概念,它也包含管道,控制台I/O等等。在JOS中,这些设备类型都有struct Dev关联,这是个实现对于这个设备读写的函数指针。lib/fd.c实现了通用的类UNIX文件描述符接口。每个struct Fd表明他的设备类型,lib/fd.c中的大多数函数仅仅分发操作给struct Dev中的函数

lib/fd.c在每个应用环境的地址空间中也保留了文件描述符表区域,起始于FDTABLE。这个区域为每个文件描述符保留了一个地址空间的页面大小(4KB),用户程序一次可以最多打开MAXFD(目前是32)个文件描述符。任何给定的时间,只有文件描述符正在使用时,才会被映射到特定的文件描述符表页。每个文件描述符也有一个可选的"数据页面"在起始的FILEDATA区域,这个区域,程序可以选择使用

我们想共享跨forkspawn的文件描述符状态,但是文件描述符状态保存在用户空间内存。现在,在fork函数,内存会被标记成写时复制,所以是被复制的而不是共享的。(这意味着环境不能在文件中跟踪,他们不能自己打开并且管道不能跨fork工作)。在spawn函数,内存会被留下来,不再复制。(spawn环境开始没有打开文件描述符)

我们将修改fork以便于知道由操作系统共享库使用的内存区域并且始终被共享。我们在页表入口处设置一个是否未使用的标识位,而不是硬编码的区域列表。

我们已经在inc/lib.h中定义了一个新的PTE_SHARE,在Intel和AMD的手册中,这个标识位意味着软件可以使用。我们将约定,如果页表入口有这个标识位,在forkspawn中,PTE应该直接从父进程拷贝到子进程。注意,这个和标记为写时复制不同:正如第一段描述的,我们想确保共享更新这个页面

进行练习8

键盘接口

为了让shell工作,需要一个输入的方式,QEMU已经显示了我们写到CGA和串口的输出,但是目前为止,我们只能输入内核监视器的命令。在QEMU中,在图形窗口键入输入就和从键盘输入到JOS一样,在控制台输入,在串口输出字符。kern/console.c已经包含了键盘和串口驱动,但是你需要将剩下的部分添加到系统中

进行练习9

我们已经实现了控制台输入输出文件类型,在lib/console.c中,kbd_intrserial_intr填充了一个读取缓冲然而控制台文件类型消耗缓冲区(控制台文件leasing是用来默认的stdin/stdout,除非用户重新指定了)

Shell

运行make run-icode-nox。这个会运行内核并且开始user/icodeicode执行初始化,会设置控制台文件描述符为0和1(标准输入和标准输出)。然后生成sh也就是shell。你能运行下面的命令

echo hello world | cat
cat lorem|cat
cat lorem|num
cat lorem|num|num|num|num
lsfd

注意,用户库程序cprintf直接打印到控制台,不需要使用文件描述符代码。这对于调试有用但是不太友好管道到其他程序。为了打印一个特定文件描述符(例如, 1 标准输出),使用fprintf(1, "...", ...)printf("...", ...)是打印到FD 1的简短表达。查看user/lsfd.c

进行练习10