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文件系统分为七层。从下往上看。

功能

file descriptor

unix的很多资源都抽象成fd(管道、设备、文件等等)

pathname

提供路径支持

directory

特殊的inode。内容是一批目录或文件。

inode

提供独立的文件,每个文件表述为一个incode,有唯一的编号,有一个或多个block保存文件内容。

logging

可让上层把几个更新block的操作打包成事务,这样这些操作就是原子的,可解决崩溃时数据不一致的问题。

buffer cache

缓存disk block。保证一个block在同一时刻最多只有一个kernel进程在对其操作。

disk

读写虚拟硬盘上的block

文件系统必须规划好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提供breadbwrite接口。分别时读写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,就会从内存中去除。
igetiput获取和释放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也可能出现多次,在一个进程的文件列表甚至不同的进程中。这些情况可能是由dupfork等导致。
每个打开的文件都有引用计数。

所有打开的文件也会存在全局的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变成256x256的二级block。
即改成11个direct block,1个256的block数组和一个256256的二级block。
一共存11 + 256 + 256
256 = 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;
     }

总结

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

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