MIT 6.S081 操作系统课程系列9 File System

https://pdos.csail.mit.edu/6.828/2020/labs/fs.html
本次实验需要读xv6手册第8章。看相关kernel代码。
理解文件系统的原理并实现一些相关功能(大文件和symbolic links软链接)。

文件系统的作用就是存储和管理数据。通常文件可供多个用户和程序共享。

xv6支持类unix的文件、目录、路径，把数据存在虚拟磁盘上。

做文件系统需要面临一些挑战
1. 需要一个树型结构来描述文件和目录。记录数据的归属、每个文件的内容、磁盘占用情况。
2. 需要支持崩溃后的恢复。比如执行某些事务时突然断电，重启后必须还能正常工作。
3. 多个进程可能会同时操作同个文件
4. 访问磁盘比访问内存慢了几个数量级，必须有cache机制。

概览

xv6文件系统分为七层。从下往上看。

文件系统必须规划好inode和block怎么存在磁盘上。xv6把磁盘分成几个部分。

      | boot | super | log | inodes | bitmap | data |
block    0       1      2      ...........

block 0(保存boot信息)是不用的。
block 1是superblock。保存文件系统的整体信息：总block数量，inode数量，log里的block数量。
block 2存log。
接着是inodes，每个block存数个inode。
bitmap保存block的使用状态。
实际的数据block。每个block要么是空的(bitmap里标注为空闲)，要么存了文件或目录的内容。

superblock存一个单独的程序(mkfs)，用来创建一个初始的文件系统。

Buffer cache层

两个功能
1. 对block做并发管理，保证一个block只有一个副本在内存里，而且同一时刻最多只能有一个kernel线程在使用这个副本。
2. 缓存常用的block。这样不用每次读磁盘。

buffer cache提供bread和bwrite接口。分别时读写block。
一个kernel线程使用完buffer后必须用brelse进行释放。
buffer cache用对每个buffer都做一个sleep锁来保证同一时刻只有一个线程在使用同一个buffer。
bread会返回一个已锁定的buffer。brelse释放锁。

buffer cache用固定数量的buffer来保存磁盘block。当文件系统请求一个不存在于cache的block时，可能发生回收。
会回收最久没使用的block来给新的block用(假设越久没用意味着再次使用的概率越小)。

Logging层

文件系统一个有趣的点是可防灾。当一个操作包含多个写时，如果一部分写之后，系统崩溃，那么此时文件系统的一致性就会出现问题。
比如宕机发生在删除文件期间。可能会造成：1.indode包含了一个标记为free的block。2.遗留一个分配了但无主的block。
后者情况稍好，前者在机器重启后可能造成严重问题。
重启后，kernel可能把这个free的block分配给其他文件，造成两个文件包含了同一个block，可相互篡改。

xv6的system call不会直接写磁盘。它把所有写操作做成一个log，需要执行时写一个commit命令到这个log，这时system call才实际执行这些写操作。完成后把log删除。

如果系统崩溃、重启，在执行任何进程之前，检查log。
如果log标记了commit，执行log里的写操作。
如果没标记commit，直接忽略。
最后把log删除。

Log 设计

log存在superblock里。包含一个header(头block)和后续的block(成为logged blocks)。
header包含一串编号，即logged blocks的编号。和logged blocks的计数。
这个计数如果是0，说明log里没有事务(transaction)。否则说明存在已commit的事务。
xv6在事务commit之后写header，不是之前。把logged block复制到文件系统后把计数置0。
commit之后崩溃会导致非0的计数。

在可能崩溃的环境下，一系列的写操作必须时原子的。为了让不同的进程并发执行，logging系统能把多个system call的写操作放进一个事务里。
这样一个commit可能涵盖多个system call。为了防止一个system call被分割到多个事务，logging系统只会在没有文件相关的system call处于运行状态时才会commit。

多个事务同时commit称作group commit。这样能减少磁盘操作，因为分摊了固定的commit开销。
还有可能更快速的执行写操作，磁盘只需旋转一次就可完成。
xv6的虚拟驱动不支持这种批量操作，但文件系统是支持的。

xv6用磁盘上固定的空间存log。事务里的写block总数b必须在这个空间范围之内。
这样有两个后果：
1. 任何一个system call的写操作不能超出空间范围。
这对于多数system call没影响。除了write和unlink，会写大量block。

2. 一个大文件的写可能会写很多block，和bitmap block，和一个inode。unlink一个大文件可能会写多个block和一个inode。
   xv6的system call会把一个大的写操作分成小的写操作，放进log里。unlink不会造成这个问题。

其他后果是logging系统不会允许一个system call开始运行除非能确认它的写操作能放进log的剩余空间。

Inode层

inode可以指磁盘上的文件数据(包括文件大小，数据block列表)，也可以指内存中的inode，包含磁盘inode的副本和一些其他信息。
磁盘inode是磁盘上一串连续的数据(inode block)。所有inode大小一样，所以给定一个n，很容易能取得磁盘上的第n个inode。
这个n被成为inode number或i-number。
inode可以看成一个无名的文件。

磁盘inode的c代码定义为dinode(kernel/fs.h)。
type分为文件、目录、特殊文件(设备)。type为0代表inode为未使用状态。
nlink为引用此inode的目录计数。
size为此文件的字节数。
addrs为文件包含的block编号

使用中状态的inode放在内存里。c代码定义是inode(file.h)。
处于内存中意味着有指针指向这个inode。ref就是这个计数，如果变为0，就会从内存中去除。
iget和iput获取和释放inode指针，加减引用计数。

有四种inode相关的锁或锁机制。
icache.lock保证一个inode只存在一份cache。并对ref进行保护。
inode结构体里有一个sleeplock，保证结构体数据修改的原子性。
ref如果大于0，系统会把inode放内存里，并保证这个份cache不会被同时使用。
nlink记录引用inode的目录数量。如果大于0，不会释放这个inode。

iget返回的inode指针保证是有效的，直到调用相应的iput。
iget提供inode的非排外的接入，所以可能多个指针同时指向一个inode。
文件系统的很多部分都依赖这个性质。

iget返回的inode也可能没有有效的信息。为了保证它指向一个好的磁盘inode，需要调用ilock(保证其他进程不能再锁)，再从磁盘读inode。
iunlock用来解锁。

File descriptor层

fd层实现了把多数资源都表示成一个文件。
xv6里每个进程会维护自己打开的文件列表。文件的c代码结构体为file(file.h)，包含一个inode或pipe，和一个io偏移。
open函数会创建一个新的file。如果多个进程打开同一个文件，每个file会有不同的io偏移。
同个file也可能出现多次，在一个进程的文件列表甚至不同的进程中。这些情况可能是由dup和fork等导致。
每个打开的文件都有引用计数。

所有打开的文件也会存在全局的ftable里。

看代码

先看看文件系统的大致代码框架，比较繁琐。

buf结构体

buf.h里的buf结构体对应一个block数据。buf是一个链表结构。
一个buf有一个data数组，包含BSIZE(1024)个uint，每个uint有8位可用，共有1024*8位可用。
用这个data数组表示8k个block的使用情况。

bcache

用一个全局变量bcache存所有buf(NBUF=30个)，和一个头block。用头可遍历所有buf。
main()里的binit把NBUF个buf首尾相连。并初始化相关的锁。

dinode结构体

磁盘上的inode抽象
inode的block数据存在uint addrs[NDIRECT+1]。
分为direct block和indirect block。
direc block存在addrs前12个位置。最后一个位置存indirect block数组的地址。

#define NINDIRECT (BSIZE / sizeof(uint))

NINDIRECT默认为1024/4=256
NDIRECT为12
例如：文件数据的第一个block，addrs[0]，被分配了全局的3号block（addrs[0]=3），
第二个block，addrs[1]，被分配了全局的200号block（addrs[1]=200）。

inode结构体

内存中的inode的数据结构
也包含一个和dinode一样的addrs。

icache

全局变量icache保存所有活跃的inode(NINODE=50个)。
main()里的iinit只是初始化这些inode相关的锁。

file结构体

一个文件的抽象。分为FD_PIPE, FD_INODE, FD_DEVICE三类。

ftable
全局变量ftable包含file的数组(NFILE=100个)。
main()里的fileinit只是初始化ftable的锁。

fsinit

proc.c里的fsinit只会在第一个fork后执行一次。
先readsb读superblock。superblock之前说过，包含了文件系统一些最基本的信息(fs.h)。
再initlog初始化logging系统。
recover_from_log即上述的崩溃恢复流程。

superblock结构体

文件系统的一些总体数据。比如文件系统总block数size，数据block总数nblocks，inode总数ninodes，log的block总数nlog。
这些初始化在mkfs.c里。
默认size=200000，nblocks=199930，ninodes=200，nlog=30。

一些常用函数

static uint balloc(uint dev)

分配一个空的block。
文件系统共200000个block。
一个buf有一个data数组，一共包含BPB(8k)个bit。
系统buf总数为NBUF，30个，每个包含8kbit，可以罩住200000个block。
balloc总体就是遍历所有block找一个空闲的，把它对应的bit设1。
返回的地址大致是0-200000之间的一个index。

static struct buf* bget(uint dev, uint blockno)

从dev设备根据block号读内存里的block数据。

struct buf* bread(uint dev, uint blockno)

先用bget取数据，如果数据是无效的，用virtio_disk_rw磁盘读取。

struct inode* idup(struct inode *ip)

复制inode指针，引用计数加一。

void ilock(struct inode *ip)

锁定inode并读取数据

static struct inode* iget(uint dev, uint inum)

返回相应inode的内存数据。

struct inode* ialloc(uint dev, short type)

在dev设备上新建一个inode。
遍历所有inode，用bread读其底层的block数据，找一个空闲的。修改状态并返回。
#define IPB (BSIZE / sizeof(struct dinode))
IPB实际是16。

struct inode* create(char *path, short type, short major, short minor)

给定路径和类型，创建一个inode，返回指针。
先nameiparent算出目标path的上一层目录，检查是否存在同名。
ialloc分配一个inode。再做一些设置。

struct file* filealloc(void)

申请一个file数据。
在ftable找一个空位。

static int fdalloc(struct file *f)

为file申请一个fd
每个进程的ofile存有它打开的文件的fd。找一个空闲的fd，和file绑定，返回fd。

打开或创建一个文件的流程

sys_open(sysfile.c)
begin_op()，所有fs相关的system call会先调这个做同步处理。
create创建或者namei打开inode。
filealloc，fdalloc申请file和fd。
把inode和file绑定起来。
返回fd。

static uint bmap(struct inode *ip, uint bn)

返回inode自己第bn个block所对应的全局block号。如果未分配，会分配block号。
inode的uint addrs[NDIRECT+1]，有NDIRECT(12)个直接的block号，最后一个uint也是一个block号。
不同的是这个block的data(uchar data[BSIZE])存的是256个block号。
uchar是1字节，uint是4字节，BSIZE(1k)个uchar刚好存256个uint。

写文件流程

sys_write(sysfile.c)
先argfd用fd获取进程file数组里的file。
int filewrite(struct file *f, uint64 addr, int n)
把用户地址addr开始的n字节写到f。
对于FD_INODE类型，不断用writei写数据。每次循环只写几个block，因为log机制有事务容量的限制。

int writei(struct inode *ip, int user_src, uint64 src, uint off, uint n)

从地址scr开始，写n字节到inode，需要考虑offset。返回写成功的字节数。
遍历这个inode覆盖的block。按BSIZE(1k)字节来划分，每次读出对应的block数据，每次最多复制1k字节到buf的data里。

做题

1. Large files

xv6的默认文件最大是268个block，需要改造成65803个block。

看懂bmap流程，可以知道inode的addrs有12个direct block，另有1个block，里面包含256个block号。
所以默认代码一共268个block。

看bigfile.c，它每次循环写1k。默认最多只能写268，再写就报错。

跟踪一下发现报错在writei

if(off + n > MAXFILE*BSIZE)
{
    printf("xc writei err 2");
    return -1;
}

需要改造addrs。把1个direct block变成256×256的二级block。
即改成11个direct block，1个256的block数组和一个256256的二级block。
一共存11 + 256 + 256256 = 65803个block。

1. 修改宏
   NDIRECT改为11
   NINDIRECT为256不变
   MAXFILE改为(NDIRECT + NINDIRECT + NINDIRECT * NINDIRECT)

2. inode和dinode的addrs长度改为NDIRECT+2

3. 修改bmap
   仿照默认的一层block，做一个两层的block分配即可。

4. itrunc里要free新加的两层block。

5. bigfile和usertests都通过即可。

主要添加的代码：
bmap函数里if(bn < NINDIRECT)后面加个else分支实现两层block分配。

else
  {
    bn -= NINDIRECT;

    uint index_0 = NDIRECT + 1;

    // check index_0
    if((addr = ip->addrs[index_0]) == 0)
      ip->addrs[index_0] = addr = balloc(ip->dev);

    struct buf *bp_0 = bread(ip->dev, addr);

    // check index_1
    uint *data_1 = (uint*)bp_0->data;
    uint index_1 = bn / NINDIRECT;
    if((addr = data_1[index_1]) == 0)
    {
      data_1[index_1] = addr = balloc(ip->dev);
      log_write(bp_0);
    }
    brelse(bp_0);

    struct buf *bp_1 = bread(ip->dev, addr);

    // check index_2
    uint *data_2 = (uint*)bp_1->data;
    uint index_2 = bn % NINDIRECT;
    if((addr = data_2[index_2]) == 0)
    {
      data_2[index_2] = addr = balloc(ip->dev);
      log_write(bp_1);
    }

    brelse(bp_1);
    return addr;
  }

2. Symbolic links

需要实现软链接的system call

搁置

总结

文件系统代码不直观，不好看。把block等配置打印出来，实际数值结合代码理解起来更容易一些。

了解了文件系统基本原理和代码流程。