简易文件系统

要实现一个完整的批处理系统, 我们还需要向系统提供多个程序. 我们之前把程序以文件的形式存放在ramdisk之中, 但如果程序的数量增加之后, 我们就要知道哪个程序在ramdisk的什么位置. 我们的ramdisk已经提供了读写接口, 使得我们可以很方便地访问某一个位置的内容, 这对Nanos-lite来说貌似没什么困难的地方; 另一方面, 用户程序也需要处理数据, 它们处理的数据也可能会组织成文件, 那么对用户程序来说, 它怎么知道文件位于ramdisk的哪一个位置呢? 更何况文件会动态地增删, 用户程序并不知情. 这说明, 把ramdisk的读写接口直接提供给用户程序来使用是不可行的. 操作系统还需要在存储介质的驱动程序之上为用户程序提供一种更高级的抽象, 那就是文件.

文件的本质就是字节序列, 另外还由一些额外的属性构成. 在这里, 我们先讨论普通意义上的文件. 这样, 那些额外的属性就维护了文件到ramdisk存储位置的映射. 为了管理这些映射, 同时向上层提供文件操作的接口, 我们需要在Nanos-lite中实现一个文件系统.

不要被"文件系统"四个字吓到了, 我们对文件系统的需求并不是那么复杂, 因此我们可以定义一个简易文件系统sfs(Simple File System):

• 每个文件的大小是固定的
• 写文件时不允许超过原有文件的大小
• 文件的数量是固定的, 不能创建新文件
• 没有目录

既然文件的数量和大小都是固定的, 我们自然可以把每一个文件分别固定在ramdisk中的某一个位置. 这些简化的特性大大降低了文件系统的实现难度. 当然, 真实的文件系统远远比sfs复杂.

我们约定文件从ramdisk的最开始一个挨着一个地存放:

0
+-------------+---------+----------+-----------+--
|    file0    |  file1  |  ......  |   filen   |
+-------------+---------+----------+-----------+--
 \           / \       /            \         /
  +  size0  +   +size1+              + sizen +

为了记录ramdisk中各个文件的名字和大小, 我们还需要一张"文件记录表". Nanos-lite的Makefile已经提供了维护这些信息的脚本, 先对nanos-lite/Makefile作如下修改:

--- nanos-lite/Makefile
+++ nanos-lite/Makefile
@@ -1,2 +1,2 @@
-#HAS_NAVY = 1
+HAS_NAVY = 1
 RAMDISK_FILE = build/ramdisk.img

然后运行make ARCH=$ISA-nemu update就会自动编译Navy中的程序, 并把navy-apps/fsimg/目录下的所有内容整合成ramdisk镜像navy-apps/build/ramdisk.img, 同时生成这个ramdisk镜像的文件记录表navy-apps/build/ramdisk.h, Nanos-lite的Makefile会通过软连接把它们链接到项目中.

"文件记录表"其实是一个数组, 数组的每个元素都是一个结构体:

typedef struct {
  char *name;         // 文件名
  size_t size;        // 文件大小
  size_t disk_offset;  // 文件在ramdisk中的偏移
} Finfo;

在sfs中, 这三项信息都是固定不变的. 其中的文件名和我们平常使用的习惯不太一样: 由于sfs没有目录, 我们把目录分隔符/也认为是文件名的一部分, 例如/bin/hello是一个完整的文件名. 这种做法其实也隐含了目录的层次结构, 对于文件数量不多的情况, 这种做法既简单又奏效.

有了这些信息, 就已经可以实现最基本的文件读写操作了:

size_t read(const char *filename, void *buf, size_t len);
size_t write(const char *filename, const void *buf, size_t len);

但在真实的操作系统中, 这种直接用文件名来作为读写操作参数的做法却有所缺陷. 例如, 我们在用less工具浏览文件的时候:

cat file | less

cat工具希望把文件内容写到less工具的标准输入中, 但我们却无法用文件名来标识less工具的标准输入! 实际上, 操作系统中确实存在不少"没有名字"的文件. 为了统一管理它们, 我们希望通过一个编号来表示文件, 这个编号就是文件描述符(file descriptor). 一个文件描述符对应一个正在打开的文件, 由操作系统来维护文件描述符到具体文件的映射. 于是我们很自然地通过open()系统调用来打开一个文件, 并返回相应的文件描述符

int open(const char *pathname, int flags, int mode);

在Nanos-lite中, 由于sfs的文件数目是固定的, 我们可以简单地把文件记录表的下标作为相应文件的文件描述符返回给用户程序. 在这以后, 所有文件操作都通过文件描述符来标识文件:

size_t read(int fd, void *buf, size_t len);
size_t write(int fd, const void *buf, size_t len);
int close(int fd);

另外, 我们也不希望每次读写操作都需要从头开始. 于是我们需要为每一个已经打开的文件引入偏移量属性open_offset, 来记录目前文件操作的位置. 每次对文件读写了多少个字节, 偏移量就前进多少.

偏移量可以通过lseek()系统调用来调整, 从而可以对文件中的任意位置进行读写:

size_t lseek(int fd, size_t offset, int whence);

为了方便用户程序进行标准输入输出, 操作系统准备了三个默认的文件描述符:

#define FD_STDIN 0
#define FD_STDOUT 1
#define FD_STDERR 2

它们分别对应标准输入stdin, 标准输出stdout和标准错误stderr. 我们经常使用的printf, 最终会调用write(FD_STDOUT, buf, len)进行输出; 而scanf将会通过调用read(FD_STDIN, buf, len)进行读入.

nanos-lite/src/fs.c中定义的file_table会包含nanos-lite/src/files.h, 其中前面还有3个特殊的文件: stdin, stdout和stderr的占位表项, 它们只是为了保证sfs和约定的标准输入输出的文件描述符保持一致, 例如根据约定stdout的文件描述符是1, 而我们添加了三个占位表项之后, 文件记录表中的1号下标也就不会分配给其它的普通文件了.

根据以上信息, 我们就可以在文件系统中实现以下的文件操作了:

int fs_open(const char *pathname, int flags, int mode);
size_t fs_read(int fd, void *buf, size_t len);
size_t fs_write(int fd, const void *buf, size_t len);
size_t fs_lseek(int fd, size_t offset, int whence);
int fs_close(int fd);

这些文件操作实际上是相应的系统调用在内核中的实现. 你可以通过 man 查阅它们的功能, 例如

man 2 open

其中2表示查阅和系统调用相关的manual page. 实现这些文件操作的时候注意以下几点:

• 由于sfs中每一个文件都是固定的, 不会产生新文件, 因此"fs_open()没有找到pathname所指示的文件"属于异常情况, 你需要使用assertion终止程序运行.
• 为了简化实现, 我们允许所有用户程序都可以对所有已存在的文件进行读写, 这样以后, 我们在实现fs_open()的时候就可以忽略flags和mode了.
• 使用ramdisk_read()和ramdisk_write()来进行文件的真正读写.
• 由于文件的大小是固定的, 在实现fs_read(), fs_write()和fs_lseek()的时候, 注意偏移量不要越过文件的边界.
• 除了写入stdout和stderr之外(用putch()输出到串口), 其余对于stdin, stdout和stderr这三个特殊文件的操作可以直接忽略.
• 由于sfs没有维护文件打开的状态, fs_close()可以直接返回0, 表示总是关闭成功.

最后你还需要在Nanos-lite和Navy的libos中添加相应的系统调用, 来调用相应的文件操作.

一切皆文件

AM中的IOE向我们展现了程序进行输入输出的需求. 那么在Nanos-lite上, 如果用户程序想访问设备, 要怎么办呢? 一种最直接的方式, 就是让操作系统为每个设备单独提供一个系统调用, 用户程序通过这些系统调用, 就可以直接使用相应的功能了. 然而这种做法却存在不少问题:

• 首先, 设备的类型五花八门, 其功能更是数不胜数, 要为它们分别实现系统调用来给用户程序提供接口, 本身就已经缺乏可行性了;
• 此外, 由于设备的功能差别较大, 若提供的接口不能统一, 程序和设备之间的交互就会变得困难. 所以我们需要有一种方式对设备的功能进行抽象, 向用户程序提供统一的接口.

我们之前提到, 文件的本质就是字节序列. 事实上, 计算机系统中到处都是字节序列(如果只是无序的字节集合, 计算机要如何处理?), 我们可以轻松地举出很多例子:

• 内存是以字节编址的, 天然就是一个字节序列, 因而我们之前使用的ramdisk作为字节序列也更加显而易见了
• 管道(shell命令中的|)是一种先进先出的字节序列, 本质上它是内存中的一个队列缓冲区
• 磁盘也可以看成一个字节序列: 我们可以为磁盘上的每一个字节进行编号, 例如第x柱面第y磁头第z扇区中的第n字节, 把磁盘上的所有字节按照编号的大小进行排列, 便得到了一个字节序列
• socket(网络套接字)也是一种字节序列, 它有一个缓冲区, 负责存放接收到的网络数据包, 上层应用将socket中的内容看做是字节序列, 并通过一些特殊的文件操作来处理它们. 我们在PA2中介绍了DiffTest, 如果你RTFSC, 就会发现其中的qemu-diff就是通过socket与QEMU进行通信的, 而操作socket的方式就是fgetc()和fputc()
• 操作系统的一些信息可以以字节序列的方式暴露给用户, 例如CPU的配置信息
• 操作系统提供的一些特殊的功能, 如随机数生成器, 也可以看成一个无穷长的字节序列
• 甚至一些非存储类型的硬件也可以看成是字节序列: 我们在键盘上按顺序敲入按键的编码形成了一个字节序列, 显示器上每一个像素的内容按照其顺序也可以看做是字节序列...

既然文件就是字节序列, 那很自然地, 上面这些五花八门的字节序列应该都可以看成文件. Unix就是这样做的, 因此有"一切皆文件"(Everything is a file)的说法. 这种做法最直观的好处就是为不同的事物提供了统一的接口: 我们可以使用文件的接口来操作计算机上的一切, 而不必对它们进行详细的区分: 例如 navy-apps/Makefile的ramdisk规则通过管道把各个shell工具的输入输出连起来, 生成文件记录表

wc -c $(FSIMG_FILES) | grep -v 'total$$' | sed -e 's+ ./fsimg+ +' |
  awk -v sum=0 '{print "\x7b\x22" $$2 "\x22\x2c " $$1 "\x2c " sum "\x7d\x2c";sum += $$1}' >> $(RAMDISK_H)

以十六进制的方式查看磁盘上的内容

head -c 512 /dev/sda | hd

查看CPU是否有Spectre漏洞

cat /proc/cpuinfo | grep 'spectre'

甚至我们在PA2中提供的"小星星"示例音频, 也是通过简单的文件操作暴力拼接而成的

cat Do.ogg Do.ogg So.ogg So.ogg La.ogg La.ogg So.ogg > little-star.ogg

而

#include "/dev/urandom"

则会将urandom设备中的内容包含到源文件中: 由于urandom设备是一个长度无穷的字节序列, 提交一个包含上述内容的程序源文件将会令一些检测功能不强的Online Judge平台直接崩溃.

"一切皆文件"的抽象使得我们可以通过标准工具很容易完成一些在Windows下不易完成的工作, 这其实体现了Unix哲学的部分内容: 每个程序采用文本文件作为输入输出, 这样可以使程序之间易于合作. GNU/Linux继承自Unix, 也自然继承了这种优秀的特性. 为了向用户程序提供统一的抽象, Nanos-lite也尝试将IOE抽象成文件.

虚拟文件系统

为了实现一切皆文件的思想, 我们之前实现的文件操作就需要进行扩展了: 我们不仅需要对普通文件进行读写, 还需要支持各种"特殊文件"的操作. 至于扩展的方式, 你是再熟悉不过的了, 那就是抽象!

我们对之前实现的文件操作API的语义进行扩展, 让它们可以支持任意文件(包括"特殊文件")的操作:

int fs_open(const char *pathname, int flags, int mode);
size_t fs_read(int fd, void *buf, size_t len);
size_t fs_write(int fd, const void *buf, size_t len);
size_t fs_lseek(int fd, size_t offset, int whence);
int fs_close(int fd);

这组扩展语义之后的API有一个酷炫的名字, 叫VFS(虚拟文件系统). 既然有虚拟文件系统, 那相应地也应该有"真实文件系统", 这里所谓的真实文件系统, 其实是指具体如何操作某一类文件. 比如在Nanos-lite上, 普通文件通过ramdisk的API进行操作; 在真实的操作系统上, 真实文件系统的种类更是数不胜数: 比如熟悉Windows的你应该知道管理普通文件的NTFS, 目前在GNU/Linux上比较流行的则是EXT4; 至于特殊文件的种类就更多了, 于是相应地有procfs, tmpfs, devfs, sysfs, initramfs... 这些不同的真实文件系统, 它们都分别实现了这些文件的具体操作方式.

所以, VFS其实是对不同种类的真实文件系统的抽象, 它用一组API来描述了这些真实文件系统的抽象行为, 屏蔽了真实文件系统之间的差异, 上层模块(比如系统调用处理函数)不必关心当前操作的文件具体是什么类型, 只要调用这一组API即可完成相应的文件操作. 有了VFS的概念, 要添加一个真实文件系统就非常容易了: 只要把真实文件系统的访问方式包装成VFS的API, 上层模块无需修改任何代码, 就能支持一个新的真实文件系统了.

在Nanos-lite中, 实现VFS的关键就是Finfo结构体中的两个读写函数指针:

typedef struct {
  char *name;         // 文件名
  size_t size;        // 文件大小
  size_t disk_offset;  // 文件在ramdisk中的偏移
  ReadFn read;        // 读函数指针
  WriteFn write;      // 写函数指针
} Finfo;

其中ReadFn和WriteFn分别是两种函数指针, 它们用于指向真正进行读写的函数, 并返回成功读写的字节数. 有了这两个函数指针, 我们只需要在文件记录表中对不同的文件设置不同的读写函数, 就可以通过f->read()和f->write()的方式来调用具体的读写函数了.

不过在Nanos-lite中, 由于特殊文件的数量很少, 我们约定, 当上述的函数指针为NULL时, 表示相应文件是一个普通文件, 通过ramdisk的API来进行文件的读写, 这样我们就不需要为大多数的普通文件显式指定ramdisk的读写函数了.

我们把文件看成字节序列, 大部分字节序列都是"静止"的, 例如对于ramdisk和磁盘上的文件, 如果我们不对它们进行修改, 它们就会一直位于同一个地方, 这样的字节序列具有"位置"的概念; 但有一些特殊的字节序列并不是这样, 例如键入按键的字节序列是"流动"的, 被读出之后就不存在了, 这样的字节序列中的字节之间只有顺序关系, 但无法编号, 因此它们没有"位置"的概念. 属于前者的文件支持lseek操作, 存储这些文件的设备称为"块设备"; 而属于后者的文件则不支持lseek操作, 相应的设备称为"字符设备". 真实的操作系统还会对lseek操作进行抽象, 我们在Nanos-lite中进行了简化, 就不实现这一抽象了.

操作系统之上的IOE

有了VFS, 要把IOE抽象成文件就非常简单了.

首先当然是来看最简单的输出设备: 串口. 在Nanos-lite中, stdout和stderr都会输出到串口. 之前你可能会通过判断fd是否为1或2, 来决定sys_write()是否写入到串口. 现在有了VFS, 我们就不需要让系统调用处理函数关心这些特殊文件的情况了: 我们只需要在nanos-lite/src/device.c中实现serial_write(), 然后在文件记录表中设置相应的写函数, 就可以实现上述功能了. 由于串口是一个字符设备, 对应的字节序列没有"位置"的概念, 因此serial_write()中的offset参数可以忽略. 另外Nanos-lite也不打算支持stdin的读入, 因此在文件记录表中设置相应的报错函数即可.

关于输入设备, 我们先来看看时钟. 时钟比较特殊, 大部分操作系统并没有把它抽象成一个文件, 而是直接提供一些和时钟相关的系统调用来给用户程序访问. 在Nanos-lite中, 我们也提供一个SYS_gettimeofday系统调用, 用户程序可以通过它读出当前的系统时间.

为了更好地封装IOE的功能, 我们在Navy中提供了一个叫NDL(NJU DirectMedia Layer)的多媒体库. 这个库的代码位于navy-apps/libs/libndl/NDL.c中, 但大部分的功能都没有实现. 代码中有一些和NWM_APP相关的内容, 你目前可以忽略它们, 但不要修改相关代码, 你将会在PA4的最后体验相关的功能. NDL向用户提供了一个和时钟相关的API:

// 以毫秒为单位返回系统时间
uint32_t NDL_GetTicks();

另一个输入设备是键盘, 按键信息对系统来说本质上就是到来了一个事件. 一种简单的方式是把事件以文本的形式表现出来, 我们定义以下两种事件,

• 按下按键事件, 如kd RETURN表示按下回车键
• 松开按键事件, 如ku A表示松开A键

按键名称与AM中的定义的按键名相同, 均为大写. 此外, 一个事件以换行符\n结束.

我们采用文本形式来描述事件有两个好处, 首先文本显然是一种字节序列, 这使得事件很容易抽象成文件; 此外文本方式使得用户程序可以容易可读地解析事件的内容. Nanos-lite和Navy约定, 上述事件抽象成一个特殊文件/dev/events, 它需要支持读操作, 用户程序可以从中读出按键事件, 但它不必支持lseek, 因为它是一个字符设备.

NDL向用户提供了一个和按键事件相关的API:

// 读出一条事件信息, 将其写入`buf`中, 最长写入`len`字节
// 若读出了有效的事件, 函数返回1, 否则返回0
int NDL_PollEvent(char *buf, int len);

最后是VGA, 程序为了更新屏幕, 只需要将像素信息写入VGA的显存即可. 于是, Nanos-lite需要做的, 便是把显存抽象成文件. 显存本身也是一段存储空间, 它以行优先的方式存储了将要在屏幕上显示的像素. Nanos-lite和Navy约定, 把显存抽象成文件/dev/fb(fb为frame buffer之意), 它需要支持写操作和lseek, 以便于把像素更新到屏幕的指定位置上.

NDL向用户提供了两个和绘制屏幕相关的API:

// 打开一张(*w) X (*h)的画布
// 如果*w和*h均为0, 则将系统全屏幕作为画布, 并将*w和*h分别设为系统屏幕的大小
void NDL_OpenCanvas(int *w, int *h);

// 向画布`(x, y)`坐标处绘制`w*h`的矩形图像, 并将该绘制区域同步到屏幕上
// 图像像素按行优先方式存储在`pixels`中, 每个像素用32位整数以`00RRGGBB`的方式描述颜色
void NDL_DrawRect(uint32_t *pixels, int x, int y, int w, int h);

其中"画布"是一个面向程序的概念, 程序绘图时的坐标都是针对画布来设定的, 这样程序就无需关心系统屏幕的大小, 以及需要将图像绘制到系统屏幕的哪一个位置. NDL可以根据系统屏幕大小以及画布大小, 来决定将画布"贴"到哪里, 例如贴到屏幕左上角或者居中, 从而将画布的内容写入到frame buffer中正确的位置.

NDL_DrawRect()的功能和PA2中介绍的绘图接口是非常类似的. 但为了实现它, NDL还需要知道屏幕大小的信息. Nanos-lite和Navy约定, 屏幕大小的信息通过/proc/dispinfo文件来获得, 它需要支持读操作. navy-apps/README.md中对这个文件内容的格式进行了约定, 你需要阅读它. 至于具体的屏幕大小, 你需要通过IOE的相应API来获取.