XV6操作系统代码阅读心得(五):文件系统

2 minute read

Published:

Unix文件系统

当今的Unix文件系统(Unix File System, UFS)起源于Berkeley Fast File System。和所有的文件系统一样,Unix文件系统是以块(Block)为单位对磁盘进行读写的。一般而言,一个块的大小为512Byte或者4KB。文件系统的所有数据结构都以块为单位存储在硬盘上,一些典型的数据块包括:superblock, inode, data block, directory block and indirection block。

Superblock包含了关于整个文件系统的元信息(metadata),比如文件系统的类型、大小、状态和关于其他文件系统数据结构的信息。Superblock对文件系统是非常重要的,因此Unix文件系统的实现会保存多个Superblock的副本。

inode是Unix文件系统中用于表示文件的抽象数据结构。inode不仅是指抽象了一组硬盘上的数据的”文件”,目录和外部IO设备等也会用inode数据结构来表示。inode包含了一个文件的元信息,比如拥有者、访问权限、文件类型等等。对于一个文件系统里的所有文件,文件系统会维护一个inode列表,这个列表可能会占据一个或者多个磁盘块。

Data block用于存储实际的文件数据。一些文件系统中可能会存在用于存放目录的Directory Block和Indirection Block,但是在Unix文件系统中这些文件块都被视为数据,上层文件系统通过inode对其加以操作,他们唯一的区别是inode里记录的属性有所不同。

Xv6中的文件系统设计思想与Unix大抵相同,但是实现细节多有简化。在底层实现上,Xv6采用与Linux类似的分层实现思路,层层向上逐级封装,以便能支持多种多样的设备和IO方式。Xv6的文件系统包含了磁盘IO层、Log层、Inode层、File层和系统调用层,下面会依次介绍其实现,

Xv6中的磁盘IO

Xv6中的磁盘IO在ide.c中,这是一个基于Programmed IO的面向IDE磁盘的简单实现。一个Xv6中的磁盘读写请求用如下的数据结构表示

struct buf {
  int flags;
  uint dev;
  uint blockno;
  struct sleeplock lock;
  uint refcnt;
  struct buf *prev; // LRU cache list
  struct buf *next;
  struct buf *qnext; // disk queue
  uchar data[BSIZE];
};

其中,对IDE磁盘而言,需要关心的域是flags(DIRTY, VALID),dev(设备),blockno(磁盘块编号)和next(指向队列的下一个成员的指针).

磁盘读写实现的思路是这样的:Xv6会维护一个进程请求磁盘操作的队列(idequeue)。当进程请求磁盘读写时,请求会被加入队列,进程会进入睡眠状态(iderw())。任何时候,队列的开头表示当前正在进行的磁盘读写请求。当一个磁盘读写操作完成时,会触发一个中断,中断处理程序(ideintr())会移除队列开头的请求,唤醒队列开头请求所对应的进程。如果还有后续的请求,就会将其移到队列开头,开始处理下一个磁盘请求。

磁盘请求队列的声明如下,当然对其访问是必须加锁的。

static struct spinlock idelock;
static struct buf *idequeue;

ide.c中函数及其对应功能如下

函数名功能
idewait()等待磁盘进入空闲状态
ideinit()初始化IDE磁盘IO
idestart()开始一个磁盘读写请求
iderw()上层文件系统调用的磁盘IO接口
ideintr()当磁盘请求完成后中断处理程序会调用的函数

操作系统启动时,main()函数会调用ideinit()ide磁盘进行初始化,初始化函数中会初始化ide锁,设定磁盘中断控制,并检查是否存在第二个磁盘。

iderw()函数提供了面向顶层文件系统模块的接口。iderw()既可用于读,也可用于写,只需通过判断buf->flag里的DIRTY位和VALID位就能判断出请求是读还是写。如果请求队列为空,证明当前磁盘不是工作状态,那么就需要调用idestart()函数初始化磁盘请求队列,并设置中断。如果请求是个写请求,那么idestart()中会向磁盘发出写出数据的指令。之后,iderw()会将调用者陷入睡眠状态。

当磁盘读取或者写操作完毕时,会触发中断进入trap.c中的trap()函数,trap()函数会调用ideintr()函数处理磁盘相关的中断。在ideintr()函数中,如果当前请求是读请求,就读取目前已经在磁盘缓冲区中准备好的数据。最后,ideintr()会唤醒正在睡眠等待当前请求的进程,如果队列里还有请求,就调用idestart()来处理新的请求。

##Buffer Cache的功能与实现

在文件系统中,Buffer Cache担任了一个磁盘与内存文件系统交互的中间层。由于对磁盘的读取是非常缓慢的,因此将最近经常访问的磁盘块缓存在内存里是很有益处的。

Xv6中Buffer Cache的实现在bio.c中,Buffer Cache的数据结构如下(rev11版本)

struct {
  struct spinlock lock;
  struct buf buf[NBUF];
  // Linked list of all buffers, through prev/next.
  // head.next is most recently used.
  struct buf head;
} bcache;

此数据结构在固定长度的数组上维护了一个由struct buf组成的双向链表,并且用一个锁来保护对Buffer Cache链表结构的访问。值得注意的是,对链表结构的访问和对一个struct buf结构的访问需要的是不同的锁。

在缓存初始化时,系统调用binit()对缓存进行初始化。binit()函数对缓存内每个元素初始化了睡眠锁,并从后往前连接成一个双向链表。一开始的时候,缓存内所有的块都是空的。

上层文件系统使用bread()bwrite()对缓存中的磁盘块进行读写。关于缓存的全部操作是在bread()bwrite()中自动完成的,不需要上层文件系统的参与。

bread()会首先调用bget()函数,bget()函数会检查请求的磁盘块是否在缓存中。如果在缓存中,那么直接返回缓存中对应的磁盘块即可。如果不在缓存中,那么需要先使用最底层的iderw()函数先将此磁盘块从磁盘加载进缓存中,再返回此磁盘块。

bget()函数的实现有一些Tricky。搜索缓存块的代码非常直接,但是在其中必须仔细考虑多进程同时访问磁盘块时的同步机制。在Xv6 rev7版本中由于没有实现睡眠锁,为了避免等待的缓冲区在等待的过程中改变了内容,必须在从锁中醒来时重新扫描磁盘缓冲区寻找合适的磁盘块,但是在rev11版本中由于实现了睡眠锁,在找到对应的缓存块时,只需释放对Buffer Cache的锁并拿到与当前缓存块有关的睡眠锁即可。

bwrite()函数直接将缓存中的数据写入磁盘。Buffer Cache层不会尝试执行任何延迟写入的操作,何时调用bwrite()写入磁盘是由上层的文件系统控制的。

上层文件系统调用brelse()函数来释放一块不再使用的冲区。brelse()函数中主要涉及的是对双向链表的操作,在此不再赘述。

Log层的功能与实现

在文件系统中添加Log层是为了能够使得文件系统能够处理诸如系统断电之类的异常情况,避免磁盘上的文件系统出现Inconsistency。Log层的实现思路是这样的,对于上层文件系统的全部磁盘操作,将其分割为一个个transaction,每个transaction都会首先将数据和其对应磁盘号写入磁盘上的Log区域,并且只有在Log区域写入全部完成后,再将Log区域的数据写入真正存储的数据区域。通过这种设计,如果在写入Log的时候断电,那么文件系统会当做这些写入不存在,如果在写入真正区域的时候断电,那么Log区域的数据可以用于恢复文件系统。如此,就可以避免文件系统中文件的损坏。

在Xv6 rev7的文件系统实现中,不允许多个进程并发地向Log层执行transaction,然而rev11的实现有所不同,允许多个进程并发地向Log层执行transaction。以下对实现细节的讨论基于rev11版本。

上层文件系统在使用log层时,必须首先调用begin_op()函数。begin_op()函数会记录一个新的transaction信息。在使用完log层后,上层系统必须调用end_op()函数。只有当没有transaction在执行时,log才会执行真正的磁盘写入。真正的磁盘写入操作在commit()函数中,可以看到commit()函数只有在end_op()结束,log.outstanding==0时才会被调用(以及开机的时刻)。commit()函数会先调用write_log()函数将缓存里的磁盘块写到磁盘上的Log区域里,并将Log Header写入到磁盘区域。只有当磁盘里存在Log Header的区域数据更新了,这一次Log更新才算完成。在Log区域更新后,commit()函数调用install_trans()完成真正的磁盘写入步骤,在这之后调用write_head()函数清空当前的Log数据。

XV6 文件系统的硬盘布局

在Xv6操作系统的硬盘中,依次存放了如下几个硬盘块。对这些硬盘块的索引是直接使用一个整数来进行的,

[boot block | super block | log | inode blocks | free bit map | data blocks]

第一个硬盘块boot block会在开机的时候被加载进内存,磁盘块编号是0。第二个superblock占据了一个硬盘块,编号是1,在Xv6中的声明如下

struct superblock {
  uint size;         // Size of file system image (blocks)
  uint nblocks;      // Number of data blocks
  uint ninodes;      // Number of inodes.
  uint nlog;         // Number of log blocks
  uint logstart;     // Block number of first log block
  uint inodestart;   // Block number of first inode block
  uint bmapstart;    // Block number of first free map block
};

Superblock中存储了文件系统有关的元信息。操作系统必须先读入Super Block才知道剩下的log块,inode块,bitmap块和datablock块的大小和位置。在Superblock之后顺序存储了多个log块、多个inode块、多个bitmap块。磁盘剩余的部分存储了data block块。

XV6中的文件

Xv6中的文件(包括目录)全部用inode数据结构加以表示,所有文件的inode都会被存储在磁盘上。系统和进程需要使用某个inode时,这个inode会被加载到inode缓存里。存储在内存里的inode会比存储在磁盘上的inode多一些运行时信息。内存里的inode数据结构声明如下。

// in-memory copy of an inode
struct inode {
  uint dev;           // Device number
  uint inum;          // Inode number
  int ref;            // Reference count
  struct sleeplock lock; // protects everything below here
  int valid;          // inode has been read from disk?

  short type;         // copy of disk inode
  short major;
  short minor;
  short nlink;
  uint size;
  uint addrs[NDIRECT+1];
};

其中,inode.type指明了这个文件的类型。Xv6中,这个类型可以是普通文件,目录,或者是特殊文件。

内核会在内存中维护一个inode缓存,缓存的数据结构声明如下

struct {
  struct spinlock lock;
  struct inode inode[NINODE];
} icache;

对于Inode节点的基本操作如下

函数名功能
iinit()读取Superblock,初始化inode相关的锁
ialloc()在磁盘上分配一个inode
iupdate()将内存里的一个inode写入磁盘
iget()获取指定inode,更新缓存
iput()对内存内一个Inode引用减1,引用为0则释放inode
ilock()获取指定inode的锁
iunlock()释放指定inode的锁
readi()往inode读数据
writei()往inode写数据
bmap()返回inode的第n个数据块的磁盘地址

一个Inode有12(NDIRECT)个直接映射的磁盘块,有128个间接映射的磁盘块,这些合计起来,Xv6系统支持的最大文件大小为140*512B=70KB。

Xv6系统中的文件描述符

Unix系统一个著名的设计哲学就是”Everything is a file”,这句话更准确地说是”Everything is a file descriptor”。上文所提的inode数据结构用于抽象文件系统中的文件和目录,而文件描述符除了抽象文件之外,还能抽象包含Pipe、Socket之类的其他IO,成为了一种通用的I/O接口。

Xv6中,一个文件的数据结构表示如下

struct file {
  enum { FD_NONE, FD_PIPE, FD_INODE } type;
  int ref; // reference count
  char readable;
  char writable;
  struct pipe *pipe;
  struct inode *ip;
  uint off;
};

从中可见,一个file数据结构既可以表示一个inode,也可以表示一个pipe。多个file数据结构可以抽象同一个inode,但是Offset可以不同。

系统所有的打开文件都在全局文件描述符表ftable中,ftable数据结构的声明如下

struct {
  struct spinlock lock;
  struct file file[NFILE];
} ftable;

从中可以看出Xv6最多支持同时打开100(NFILE)个文件,从struct proc中可以看出Xv6中每个进程最多同时可以打开16(NOFILE)个文件。

对File数据结构的基本操作包括filealloc(), filedup(), fileclose(), fileread(), filewrite()filestat()。命名风格与Unix提供的接口一致,因此从名字很容易就能看出其基本功能。

对于Inode类型的file而言,上述操作的实现依赖于inode的诸如iread()iwrite()等基本操作。

Xv6中文件相关的系统调用

利用上一层的实现,大多数系统调用的实现都是比较直接的。Xv6中支持的文件相关系统调用列表如下

名称功能
sys_link()为已有的inode创建一个新的名字
sys_unlink()为已有的inode移除一个名字,可能会移除这个inode
sys_open()打开一个指定的文件描述符
sys_mkdir()创建一个新目录
sys_mknod()创建一个新文件
sys_chdir()改变进程当前目录
sys_fstat()改变文件统计信息
sys_read()读文件描述符
sys_write()写文件描述符
sys_dup()增加文件描述符的引用

绝大多数系统调用的语义都与Unix标准相同。