文件系统果然是内核设计中boss级别的存在，花了我大量时间。主要是对文件系统格式的解析非常繁琐，以及之前没有在sbi环境下考虑过设备中断问题，网上也没有资料，走了不少弯路。因此这一块分为两节，本节主要介绍文件系统格式的解析，本身可以独立出来作为外部程序，相当于内核文件系统的预备部分，所以是“降”第七节；下一节主要介绍块设备的处理，以及附带的命令行参数、重定向等实现。
rcore和xv6使用的都是其自创的文件系统。但是我经过权衡，决定使用ext2文件系统，好处有两个：一是这个文件系统是被广泛应用的文件系统，其家族的ext4更是Linux默认的文件系统，因此网上有大量的教程和工具，Linux更是在系统上支持它，比如使用mke2fs可以很方便的对映像文件格式化，也可以直接将映像文件挂载到某文件夹下，进行文件的创建、删除和编辑；二是相比于fat家族、ntfs等文件系统，ext2文件系统和rcore、xv6的文件系统更加接近，都是以块为单位管理，每个文件和文件夹抽象为一个inode节点，方便参考。
内核设计中整个文件系统分为4层：
先说文件节点层，和文件描述符绑定的结构体定义为FNode：
其中refcnt是引用计数，offset是读写偏移量。dnum表示该FNode对应文件系统的inode编号，dinode包含的是该FNode对应文件系统的inode中的全部信息。
ext2格式的定义可以看这个网站，讲的很详细，我这里就只介绍和实现有关的重点。首先ext2格式最小同时是默认的块大小是1024个字节。文件映像的第一个块是引导块，不放和文件系统有关的任何信息，第二个块称为超级块，存储的是整个文件系统的元信息，我们关心的有前8个字节存储的文件系统总块数和总inode数，用来在后面确定位视图大小；以及第12-19字节存储的文件系统未分配块数和未分配inode数，后面分配两者的时候需要修改这8个字节。第32-39字节存储文件系统每组的有多少块和多少inode，ext2会将整个文件系统所有的块和inode划分成一定数量的组，默认每组是8192个块，而我创建的文件映像大小只有4MiB，即4096个块，所以整个映像只有一个组，可以不关心这个属性。
下一个块描述各块组的信息，称为块组描述表。每串描述对应一个组，共32字节，我们需要关心的有0-3个字节、4-7字节和8-11字节分别记录块视图、inode视图和inode表的块地址；以及12-13字节和14-15字节记录的该组未分配的块和inode。这些都是分配和释放块和inode需要修改和查询的信息。初始化函数就是记录上面所述的这些信息：
void init_ext2() {
bcache_init();
bcache_rw(1, 12, 8, superblock, 0);
bcache_rw(1, 0, 4, &inode_cnt, 0);
bcache_rw(1, 4, 4, &block_cnt, 0);
bcache_rw(2, 0, 4, &block_bitmap_addr, 0);
bcache_rw(2, 4, 4, &inode_bitmap_addr, 0);
bcache_rw(2, 8, 4, &inode_table, 0);
bcache_rw(2, 12, 4, gdt_num, 0);
block_bitmap = bd_malloc(block_cnt / 8);
inode_bitmap = bd_malloc(inode_cnt / 8);
bcache_rw(block_bitmap_addr, 0, block_cnt / 8, block_bitmap, 0);
bcache_rw(inode_bitmap_addr, 0, inode_cnt / 8, inode_bitmap, 0);
}块缓存层暴露给文件节点层的函数读写函数是bcache_rw，参数有块号、读写位置在块里的偏移和长度、数据指针和控制读写的开关。由于对块视图和inode视图的操作比较复杂，需要对位进行处理，所以这里把整个视图都保存到内存了，每次写入就在内存中写在写回磁盘。
下一个是查找路径的函数，这里我们只处理绝对路径，具体思路就是首先置当前路径为根目录，然后不断地从路径中获得文件夹，然后在当前路径中查找，如果找到这个文件夹就把当前路径设为该文件夹的操作。到达最后一个“/”符号后，需要进行一个判断，如果这个“/”符号在最后，说明这个路径是一个文件夹，那么直接返回这个文件夹；否则，说明这个路径是文件，需要再在当前路径中查找这个文件，如果找到了，直接返回。找不到则根据当前函数的参数确定是否要创建这个文件，如果要创建，需要在磁盘上分配一个新inode，把这个inode记录到父文件夹中，再初始化这个inode，然后才返回：
char dinode[128];
FNode *inode_get(char *path, int create) {
if (path[0] != '/') return 0;
get_inode(2, dinode); int len = strlen(path);
int j = 1, inodep_num = 2;
for (int i = 1; i < len; i++) {
if (path[i] == '/') {
if (i != j) {
inodep_num = find_file(path + j, i - j, dinode);
if (! inodep_num) panic("inode_get:path not found");
get_inode(inodep_num, dinode);
}
j = i + 1;
}
}
if (j == len) {
FNode *fn = bd_malloc(sizeof(FNode)); fn->dnum = inodep_num;
memcpy(fn->dinode, dinode, 128); return fn;
}
int inode_num = find_file(path + j, len - j, dinode);
if (inode_num) get_inode(inode_num, dinode);
else {
if (! create) return 0;
inode_num = alloc_inode();
add_file(path + j, len - j, inode_num, inodep_num, dinode);
init_inode(inode_num, dinode);
}
FNode *fn = bd_malloc(sizeof(FNode)); fn->dnum = inode_num;
memcpy(fn->dinode, dinode, 128); return fn;
}其中，find_file传入当前路径的inode（dinode存储当前路径）和文件（夹）名在里面查找指定的文件（夹），返回其inode号（注意inode号一律从1开始，根目录的inode号固定为2），get_inode函数根据inode号赋值dinode，即修改当前路径。在创建文件时，注意add_file和init_inode两个函数不能反着执行，因为init_inode里会将dinode修改成刚分配的新inode，而add_file需要dinode里保存的父文件夹。
get_inode函数获得inode信息，每个inode是一个128字节的字符串，连续排放在块组描述表给出的块地址中，所以可以利用整除和取模运算根据inode编号获得inode。upd_inode用来更新inode，和get_inode几乎一样，一并给出：
void get_inode(int inode_num, char *buf) {
bcache_rw(inode_table + (inode_num - 1) * 128 / BSIZE,
((inode_num - 1) * 128) % BSIZE, 128, buf, 0);
}
void upd_inode(int inode_num, char *buf) {
bcache_rw(inode_table + (inode_num - 1) * 128 / BSIZE,
((inode_num - 1) * 128) % BSIZE, 128, buf, 1);
}从inode中可以查找该inode对应的文件或文件夹的内容，查找方法后面介绍。文件的内容自然就是其本身的内容，而文件夹的内容是连续排列的一组入口索引。每个入口索引大小不定，包含其对应的子文件（夹）的inode编号（4字节）、索引大小（2字节）、文件（夹）名长度（1字节）、类型（1字节）和文件（夹）名（不定长）。注意入口索引不能跨块，需要按4字节对齐同时存放入口索引的块内不能有空隙，所以最后一个入口索引往往会比较大以充满整个块，这时就会出现入口索引的大小大于其所有属性大小的和的情况。find_file函数就是对入口索引进行查找：
int find_file(char *s, int len, char *dinode) {
int size = TO32(dinode + 4); char *entry = bd_malloc(size);
read_inode(dinode, 0, size, entry);
for (int i = 0; i < size; i += TO16(entry + i + 4)) {
u8 l = entry[i + 6];
if (l == len) {
int f = 0;
for (int j = 0; j < l; j++)
if (entry[i + 8 + j] != s[j]) {
f = 1; break;
}
if (!f) {
int r = TO32(entry + i); bd_free(entry);
return r;
}
}
}
bd_free(entry); return 0;
}这里不能使用strcmp进行匹配，因为入口索引中文件（夹）名不一定是以0结尾。该函数也用到了read_inode函数，这个函数用来读取inode对应的文件内容，由于入口索引表是文件夹的所有内容，所以这里获取大小（inode的第四个字节开始的32位整数时文件大小）然后整个读出。这里也可以解释我们平常使用ls -l命令看到的文件夹的大小是什么含义，指的就是其入口索引表的大小。
和find_file类似的一个函数是列举文件夹下子文件（夹）的inode_list函数，这个函数目前只用来在内核开始前用来打印根目录下的内容，以后可能会扩展为系统调用：
char* inode_list(FNode *fn, int *slen) {
int size = TO32(dinode + 4); char *entry = bd_malloc(size);
read_inode(dinode, 0, size, entry); int len = 0;
for (int i = 0; i < size; i += TO16(entry + i + 4))
len += (u8)entry[i + 6] + 1;
char *s = bd_malloc(len); len = 0;
for (int i = 0; i < size; i += TO16(entry + i + 4)) {
u8 l = entry[i + 6]; memcpy(s + len, entry + i + 8, l);
s[len + l] = '\0'; len += l + 1;
}
bd_free(entry); *slen = len; return s;
} alloc_inode函数用来分配inode，分两步，第一步是在inode视图中找一个不为1的位（需要用到位运算），将它修改为1，第二步是修改超级块和块组描述表里的“未分配inode”数量，然后返回第一步找到的位对应的inode编号：
int alloc_inode() {
for (int i = 0; i < inode_cnt; i++)
if (!(inode_bitmap[i / 8] & (1 << (i % 8)))) {
inode_bitmap[i / 8] |= (1 << (i % 8));
bcache_rw(inode_bitmap_addr, 0, inode_cnt / 8, inode_bitmap, 1);
superblock[1]--; gdt_num[1]--;
bcache_rw(1, 12, 8, superblock, 1);
bcache_rw(2, 12, 4, gdt_num, 1);
return i + 1;
}
panic("alloc_inode: no free inode");
}add_file函数在指定文件夹的入口索引表中创建一个新入口索引，将文件名、大小、名字、inode号等填入索引。这里比较麻烦的就是如前所述，最后一个入口索引往往会比较大以充满整个块。如果每次创建新入口索引的时候都是直接创建在最后一个入口索引后面，那么相当于每个入口索引都要占一个块，会浪费大量空间，所以这里需要看一下最后一个入口索引在文件名后面到块末尾还有没有足够的空间装下新索引，有的话就缩小一下它的大小，然后让新索引填满剩下的空间：
void add_file(char *name, int len, int inode_num, int inodep_num, char *dinode) {
int size = TO32(dinode + 4); char *entry = bd_malloc(size);
read_inode(dinode, 0, size, entry); int i = 0;
while (i + TO16(entry + i + 4) < size) i += TO16(entry + i + 4);
u8 l = entry[i + 6]; int real_size = (8 + l + 3) / 4 * 4;
if (TO16(entry + i + 4) - real_size >= (8 + len + 3) / 4 * 4) {
TO16(entry + i + 4) = real_size;
TO32(entry + i + real_size) = inode_num;
TO16(entry + i + real_size + 4) = size - i - real_size;
entry[i + real_size + 6] = len; entry[i + real_size + 7] = 1;
memcpy(entry + i + real_size + 8, name, len);
write_inode(inodep_num, dinode, 0, size, entry);
} else {
real_size = (8 + len + 3) / 4 * 4; memset(entry, 0, real_size);
TO32(entry) = inode_num; TO16(entry + 4) = BSIZE;
entry[6] = len; entry[7] = 1; memcpy(entry + 8, name, len);
write_inode(inodep_num, dinode, size, size + real_size, entry);
}
bd_free(entry);
}这里用到了write_inode函数，这个函数会自动扩大文件大小使得所有数据都能被写到文件中。所以当新索引挤不进最后一个索引内的时候就直接把新索引写到最后一个索引后面（注意要按4字节对齐）。
init_inode就比较简单了，大部分属性都可以填成0。但值得注意的是前两个字节，存放文件类型和权限，文件类型是普通文件（8），权限设置成类似平常用的chmod 777里的777，这个777是8进制，十六进制1ff。根据这个属性的定义，高4字节是文件类型，低12字节是权限，所以这个属性应赋值为81ff：
void init_inode(int inode_num, char *dinode) {
memset(dinode, 0, 128);
TO16(dinode) = 0x81ff; TO16(dinode + 26) = 1;
upd_inode(inode_num, dinode);
}根据文件系统的设计，写文件的时候文件基本只能越写越大，因此需要清空文件的函数。其内容就是将inode的文件大小属性设置为0，然后将文件占用的块全部清空。ext2格式文件内容的组织是由零级索引、一级索引、二级索引……组成的。对于inode，其第40字节开始就是索引。共12个零级索引，1个一级索引，一个二级索引，一个三级索引。每个索引都是4字节，如果一个块为1024字节，那么共可索引的块数是12+256+256*256+256*256*256。要清除文件占用的所有块，可以递归对这些索引进行查找：
int dfs_clear(int block_num, int dep) {
if (block_num == 0) return 1;
if (dep == 0) {
free_block(block_num); return 0;
}
int *table = bd_malloc(BSIZE);
bcache_rw(block_num, 0, BSIZE, table, 0);
int f = 0;
for (int i = 0; i < BSIZE / 4; i++)
if (dfs_clear(table[i], dep - 1)) { f = 1; break; }
bd_free(table); free_block(block_num); return f;
}
void inode_clear(FNode *fn) {
TO32(fn->dinode + 4) = 0;
for (int i = 0; i < 12; i++)
if (dfs_clear(TO32(fn->dinode + 40 + i * 4), 0)) goto write;
if (dfs_clear(TO32(fn->dinode + 88), 1)) goto write;
if (dfs_clear(TO32(fn->dinode + 92), 2)) goto write;
dfs_clear(TO32(fn->dinode + 96), 3);
write:
memset(fn->dinode + 40, 0, 60); upd_inode(fn->dnum, fn->dinode);
}dep=0表示当前块号是直接存储文件内容的块。如果递归dfs_clear返回1表示接下来不用再递归后面的索引了。
关于块的分配和释放，与inode的分配类似：
int alloc_block() {
for (int i = 0; i < block_cnt; i++)
if (!(block_bitmap[i / 8] & (1 << (i % 8)))) {
block_bitmap[i / 8] |= (1 << (i % 8));
bcache_rw(block_bitmap_addr, 0, block_cnt / 8, block_bitmap, 1);
superblock[0]--; gdt_num[0]--;
bcache_rw(1, 12, 8, superblock, 1);
bcache_rw(2, 12, 4, gdt_num, 1);
char* zero = bd_malloc(BSIZE); memset(zero, 0, BSIZE);
bcache_rw(i, 0, BSIZE, zero, 1); bd_free(zero); return i;
}
panic("alloc_block: no free block");
}
void free_block(int block_no) {
if (!(block_bitmap[block_no / 8] & (1 << (block_no % 8))))
panic("free_block: block has been freed");
else {
block_bitmap[block_no / 8] &= (~(1 << (block_no % 8)));
bcache_rw(block_bitmap_addr, 0, block_cnt / 8, block_bitmap, 1);
superblock[0]++; gdt_num[0]++;
bcache_rw(1, 12, 8, superblock, 1);
bcache_rw(2, 12, 4, gdt_num, 1);
}
}接下来是inode_read和inode_write函数，注意我定义了两组函数，一组是inode_read/inode_write，另一组是read_inode/write_inode。前者供文件描述符层调用，接收的参数是FNode类型，根据FNode里的offset属性确定读写起始位置，然后调用后者，后者才是真正对inode进行操作。前者的inode_read函数还需要判断当前读的长度是否超过了文件大小，如果超过了则只读能够读的最大长度：
usize inode_read(FNode *fn, char *buf, usize len) {
if (fn->offset + len > TO32(fn->dinode + 4)) {
usize r = TO32(fn->dinode + 4) - fn->offset;
read_inode(fn->dinode, fn->offset, r, buf);
fn->offset += r; return r;
} else {
read_inode(fn->dinode, fn->offset, len, buf);
fn->offset += len; return len;
}
}
usize inode_write(FNode *fn, char *buf, usize len) {
write_inode(fn->dnum, fn->dinode, fn->offset, len, buf);
fn->offset += len; return len;
}read_inode函数就比较复杂了。重点是“找文件内容的下一个块”操作，由于我们用的文件映像比较小，所以也不会出现需要用到三级索引的超大文件，这里就忽略它了。于是我就用l0、l1、l2表示当前所在的各级索引。在函数最开始先根据读的起始位置算出l0、l1、l2的初始值，然后将读的长度切分成以块为单位，不断跳到下一个块，根据l0、l1、l2逐级找到要读的内容。下一个块的各级索引则根据各种边界判断进行计算，具体见代码：
void read_inode(char *dinode, usize st, usize len, char *buf) {
int l0, l1, l2;
find_block(dinode, st, &l0, &l1, &l2);
usize cpoff = 0; st %= BSIZE;
while (len) {
usize cplen = min(BSIZE - st, len);
if (l0 < 12) {
bcache_rw(TO32(dinode + 40 + 4 * l0), st, cplen, buf + cpoff, 0);
l0++;
} else if (l0 == 12) {
int block_no; bcache_rw(TO32(dinode + 88), l1 * 4, 4, &block_no, 0);
bcache_rw(block_no, st, cplen, buf + cpoff, 0); l1++;
if (l1 == BSIZE / 4) { l1 = 0; l0++; }
} else if (l0 == 13) {
int block_no; bcache_rw(TO32(dinode + 92), l1 * 4, 4, &block_no, 0);
bcache_rw(block_no, l2 * 4, 4, &block_no, 0);
bcache_rw(block_no, st, cplen, buf + cpoff, 0); l2++;
if (l2 == BSIZE / 4) { l2 = 0; l1++; }
if (l1 == BSIZE / 4) panic("read_inode: len too large");
} else panic("read_inode: len too large");
st = 0; len -= cplen; cpoff += cplen;
}
}find_block函数用来计算l0、l1、l2的初始值，具体也是各种条件判断：
void find_block(char *dinode, usize st, int *l0, int *l1, int *l2) {
*l0 = 0, *l1 = 0, *l2 = 0; int bn = BSIZE / 4;
if (st < BSIZE * 12) *l0 = st / BSIZE;
else if (st < BSIZE * 12 + bn * BSIZE) {
*l0 = 12; *l1 = (st - BSIZE * 12) % BSIZE;
} else if (st < BSIZE * 12 + bn * BSIZE + bn * bn * BSIZE) {
*l0 = 13; *l1 = (st - BSIZE * 12) / (bn * BSIZE);
*l2 = ((st - BSIZE * 12) % (bn * BSIZE)) / BSIZE;
} else panic("find_block: offset too large");
}write_inode在read_inode的基础上就是需要当待写的块不存在时，需要分配块并把块号填入到索引中：
void write_inode(int inode_num, char *dinode, usize st, usize len, char *buf) {
if (st + len > TO32(dinode + 4)) {
TO32(dinode + 4) = st + len;
upd_inode(inode_num, dinode);
}
int l0, l1, l2;
find_block(dinode, st, &l0, &l1, &l2);
usize cpoff = 0; st %= BSIZE;
while (len) {
usize cplen = min(BSIZE - st, len);
if (TO32(dinode + 40 + 4 * l0) == 0) {
TO32(dinode + 40 + 4 * l0) = alloc_block();
upd_inode(inode_num, dinode);
}
if (l0 < 12) {
bcache_rw(TO32(dinode + 40 + 4 * l0), st, cplen, buf + cpoff, 1); l0++;
} else if (l0 == 12) {
int block_no = get_alloc_block(TO32(dinode + 88), l1);
bcache_rw(block_no, st, cplen, buf + cpoff, 1); l1++;
if (l1 == BSIZE / 4) { l1 = 0; l0++; }
} else if (l0 == 13) {
int block_no = get_alloc_block(TO32(dinode + 92), l1);
block_no = get_alloc_block(block_no, l1);
bcache_rw(block_no, st, cplen, buf + cpoff, 1); l2++;
if (l2 == BSIZE / 4) { l2 = 0; l1++; }
if (l1 == BSIZE / 4) panic("write_inode: len too large");
} else panic("write_inode: len too large");
st = 0; len -= cplen; cpoff += cplen;
}
}当inode上的索引为空时，肯定是要分配的，不管它是零级还是一级还是其他级，分配完就更新inode。在逐级找到要写入的块时，我用get_alloc_block函数把重复操作包装起来了，主要就是如果索引中该块大于0则返回，等于0则分配新块并写到索引中：
int get_alloc_block(int now_block, int index) {
int x; bcache_rw(now_block, index * 4, 4, &x, 0);
if (!x) {
x = alloc_block(); bcache_rw(now_block, index * 4, 4, &x, 1);
}
return x;
}注意当写入的内容大于文件大小时，inode_write还要更新文件大小。
以上是文件节点层的内容，非常复杂和繁琐。其本质也就是对二进制格式文件的读写，复杂性主要在于三个方面，一个是文件系统本身的复杂性，像各类算法竞赛、考试，文件系统相关的题目一直一来都是各色”大模拟“题、”码农“题的常客，既包括对路径的字符串解析、又包括对文件树的操作，操作往往有多个种类，这就涉及状态的处理了；二是二进制格式文件的写比读要困难的多，因为读只需要关注想读的内容在哪、多大就行了，而写则需要适应整个格式的要求，除了写对应的内容，还需要修改各类元数据以满足文件格式的要求。就像我这个程序，如果只需要读取文件的话，那么和分配inode、block、创建文件相关的函数全部可以扔掉了，代码至少少掉七成；三是文件系统布局本身的复杂性，尤其是inode的多级索引那块比较繁琐。
块缓存层就比较简单了，替换策略用的是LRU算法，通过时间戳实现。具体而言，每次读写块分三步：
每次读写完一个缓存时将其时间戳置为0，每次返回时将所有已使用缓存的时间戳加1：
void bcache_rw(int blockno, int st, int len, void *data, int write) {
while (bcache_state) suspend_current_and_run_next(); bcache_state = 1;
for (int i = 0; i < NBUF; i++)
if (buf[i].occupied && buf[i].blockno == blockno) {
if (write) {
memcpy(buf[i].data + st, data, len); buf[i].modify = 1;
} else memcpy(data, buf[i].data + st, len);
buf[i].time = 0; goto updtime;
}
int mx = 0;
for (int i = 0; i < NBUF; i++)
if (!buf[i].occupied) {
buf[i].occupied = 1; buf[i].blockno = blockno;
virtio_disk_rw(buf + i, 0);
if (write) {
memcpy(buf[i].data + st, data, len); buf[i].modify = 1;
} else {
memcpy(data, buf[i].data + st, len); buf[i].modify = 0;
}
buf[i].time = 0; goto updtime;
} else if (buf[i].time > buf[mx].time) mx = i;
buf[mx].time = 0; if (buf[mx].modify) virtio_disk_rw(buf + mx, 1);
buf[mx].blockno = blockno; virtio_disk_rw(buf + mx, 0);
if (write) {
memcpy(buf[mx].data + st, data, len); buf[mx].modify = 1;
} else {
memcpy(data, buf[mx].data + st, len); buf[mx].modify = 0;
}
updtime:
for (int i = 0; i < NBUF; i++)
if (buf[i].occupied) buf[i].time++;
bcache_state = 0;
}注意这里用了一个变量bcache_state，这个变量起到的作用类似锁。为什么没有时钟中断，这里还需要用锁呢？我们知道，锁主要防止的是一个任务数据写到一半被另一个任务读取。这里主要可能导致这一点就是在virtio_disk里等待磁盘响应过程中的suspend_current_and_run_next函数切换进程。在其他地方，这个函数执行的时候并没有”数据写到一半“的情况，但这里不一样，像缓存淘汰的过程中，需要先写回缓存的原数据，然后再修改块号，再读入新数据，这涉及到多次对缓存属性的更新，同时又可能在读写磁盘的过程中被打断更新，被另一个进程读取，这就会发生错误，所以这里用了一个锁。当然由于没有时钟中断和多核处理，这个锁的状态就不需要用原子操作去修改，直接赋值就行了。
缓存层还提供了一个bcache_save函数，一次性保存所有已使用且修改过的缓存。每次close文件的时候通过这个函数来使得所有的写操作即时得到保存：
void bcache_save() {
while (bcache_state) suspend_current_and_run_next(); bcache_state = 1;
for (int i = 0; i < NBUF; i++) if (buf[i].occupied && buf[i].modify) {
virtio_disk_rw(buf + i, 1); buf[i].modify = 0;
}
bcache_state = 0;
}这两层的独立性比较强，用一个源文件把virtio_rw等函数替换成直接访问文件映像之类的函数，配上一个主程序，就可以用宿主机的编译器编译运行，方便调试，也可以独立出来作为读写ext2文件映像的工具程序。