xv6源码阅读体验

 

一、File and File System


1.1 File

文件是永久存储 user/kernel 代码和数据的地方,文件通常存储在磁盘上。

文件除了在磁盘上存储文件内容,还会存一些文件的 metadata(元数据):

和一些文件操作:

大多数编程语言都会提供一些库,来完成上述操作。

1.2 Directory

多个文件通常组织在目录下,目录的内容包括一些文件和这些文件的元数据,大多数 OS 把目录当作特殊的文件。文件与目录组织起来就像一棵树,OS 可以对这棵树的深度等进行设置。

文件和目录的数据和元数据存放在磁盘或者内存中。文件的数据存放在磁盘上的 block 里,文件的元数据存放在 inode 数据结构里。一个 inode 唯一标识一个文件。使用文件时,就拷贝一份该文件的 inode(on-disk inode) 到内存中。在内存中的 inode 通常称为 in-memory inode(这是另外一个数据结构)。在 xv6 中这两个数据结构分别如下:

// 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];
};
// On-disk inode structure
struct dinode {
  short type;           // File type
  short major;          // Major device number (T_DEV only)
  short minor;          // Minor device number (T_DEV only)
  short nlink;          // Number of links to inode in file system
  uint size;            // Size of file (bytes)
  uint addrs[NDIRECT+1];   // Data block addresses
};

可以看到 inode 比 dinode 多了一些信息。在 xv6 中,in-memory inodes 保存在另一个数据结构中:

struct {
  struct spinlock lock;
  struct inode inode[NINODE]; // NINODE=50
} icache;

在 xv6 中,有一个目录项(directory entry)数据结构如下所示:

struct dirent {
  ushort inum;
  char name[DIRSIZ]; // DIRSIZ = 14
};

目录项将一个目录中的文件链接到它的 inode。也就是说,目录项存放着该目录下文件到 inode 到映射关系。目录项以什么方式存放在磁盘上,这取决于 OS 的实现。

大多数 OS 支持在不同的目录下建立目录项,并链接到同一个 inode。这样的链接方式有两种:

+-----------+     +-------+      +-----------+
| hard link |     | a.txt |<-----+ soft link |
+-----+-----+     +---+---+      +-----------+
      |               |
      |               |
      |               |
      |               v
      |           +---+---+
      +---------->| inode |
                  +-------+

软链接和硬链接的具体区别可以参考这里。这里摘录一句很经典的解释:

A file in the file system is basically a link to an inode. A hard link then just creates another file(link) with a link to the same underlying inode.

文件(这里理解为 inode 更为准确)在创建之初默认链接到它到父目录。接下来可能还会有更多到 directory entry 硬链接到这个 inode,这样一来,通过不同到文件名链接到同一个 inode。在 in-memory inode 中使用 inode.nlink 这个成员来记住链接数量。

A file is garbage collected only when (1)it is unlinked from all its parents and (2)its link count reaches zero.

注意这里 link count 不包括软链接。

1.3 Open File table

OS 里维护着两类 Open file table:

在 xv6 中他们的数据结构分别如下:

struct {
  struct spinlock lock;
  struct file file[NFILE]; // NFILE = 100
} ftable;
struct proc {
  ...
  struct file *ofile[NOFILE]; // NOFILE = 16
  ...
};

in-memory inode 中维护了一个引用计数 inode.ref 来表明有多少个 open file table entry 指向这个 inode。当 icache 已经满了,而我们还需要继续使用的时候,就选择一个 inode.ref 为 0 的 inode。

注意不要将 inode.refinode.nlink 这两个成员混淆。

Do not confuse the reference count of an in-memory inode with the link count of an inode in the directory tree.

执行 open() 函数,会在 per-process open file table 和 system-wide open file table 里各创建一个 entry。前者是一个指针 table,指向后者(注意观察二者数据结构)。

open() 函数的返回值是 per-process open file table 的 index,即 File Descriptor(fd)。正因为 fd 是 per-process open file table 的 index,所以它是进程私有的,不同进程打开同一个文件通常会返回不同的 fd。

再看看进程的数据结构:

struct proc {
  ...
  // 提供给进程的是统一的 file 抽象
  struct file *ofile[NOFILE]; // NOFILE = 16
  ...
};

虽然给进程提供的是统一的 file 抽象,通过 ofile 指针指向的 file 数据结构,但是这个数据结构背后不一定都是 inode:

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

在 xv6 中,file 下面有两种类型: pipe 和 inode。因为 xv6 没有实现网络相关,所以没有 socket 类型。

通常文件系统会提供复制 fd 的操作,当一个 fd 被复制,这两个 fd 就指向同一个 ftable.file[i]。这时,使用 file.ref 这个成员来计数(注意区分 file.refinode.ref )。当某个 ftable.file[i] 的 file.ref 为 0 时,就回收这个 open file table entry。

还有一个例子就是,当父进程执行 fork() 函数的时候,会使用 dup() 函数将父进程的 proc.ofile 数组中所有元素都复制给子进程。这样它们就能操作同样的 file/pipe/socket。

下面用一张图总结一下这小结:

                   Process
              +---------------+
              | file *ofile[] |
              +--+-------+--+-+
        1:n      |       |  |
    +------------+       |  +----+
    |                    |       |
    v                    v       v
+---+--+------+------+---+---+---+--+-------+
| file |      |      |  file | file |       | ftable.file
+---+--+------+------+---+---+---+--+-------+
    | n                   |       |
    | :                   |       |
    v 1                   v       v
+---+---+            +---+-------+--+
| inode |            | socket| pipe |
+-------+            +--------------+

1.4 Mount File System

Before a file system can be used to store and retrieve data, it must be mounted.

Mounting a file system is equivalent to opening a file before reading/writing from it.

Consider a file system of a certain type present on a volume on a disk.

To start using this file system, one must provide anempty directory in the directory structure of the running system, and instruct the OS to mount the file system at this mount point in the directory tree.

Once the file system is mounted and connected to the directory tree at a certain point,processes can access and work with the files on that file system.

The OS maintains an in-memory mount table that lists all the file systems currently mounted.

Note that the first file system that holds the kernel executable is mounted at the root of the directory tree during boot time itself, so that the kernel executable can be read off the root file system during the boot process by the boot loader.

1.5 Disk Buffer Cache

操作系统将经常使用的 Disk Block 放进 Buffer Cache 中。文件系统的读写操作对象是 Buffer Cache。如果 Buffer Cache 中没有想要的数据,就让驱动去 I/O 设备中读取。I/O 设备驱动是内核与磁盘之间的接口,它通常使用最底层的 I/O 操作去读写磁盘,以及处理来自设备的中断。

但是并不是所有的文件操作都要通过文件系统。当操作系统需要高效率的磁盘读写时(如操作swap space时,或者设计数据库系统),就会绕过文件系统,读写原生的磁盘 block(不使用file system里的buffer cache)。

 

二、Layers of Abstraction in File Systems


系统调用是用户与文件系统之间的接口。现代 OS 支持很多种文件系统,例如: ext2, ext3, ext4, ZFS 等等。

为了保证系统调用的一致性,现代 OS 都支持在文件系统上面封装一层,称为 VFS(virtual file system)。

VFS 通常定义了一些抽象的对象: files,directories,inodes,superblocks。以及对这些对象的操作。

凡是支持 VFS 的文件系统也都应该定义这些相同的对象,并将实现的操作(函数指针)注册到 VPS 中。通过这种方式,即使使用的文件系统不同,用户也能使用相同的系统调用来操作文件。

+-------------+
|  user space | +
+-------------+ |
                |
+-------------+ |
|   syscall   | |
+-------------+ |
                |
+-------------+ |
|    VFS      | |
+-------------+ |
                |
+-------------+ |
| file system | |
+-------------+ |
                |
+-------------+ v
|  I/O device |
+-------------+

这种分层设计是 Unix 中文件系统的经典实现。

 

三、Design Choices for File and Directory Metadata


将磁盘分为固定大小的磁盘块(block),用这些 block 来存储文件的内容,那么如何知道哪些 block 存储了某个文件的内容呢?这涉及到了为文件分配 block 的原则问题,这个问题类似于为进程分配空间。分配 block 有 3 种方式:

在类 Unix OS 中,普遍采用第三种方式。这种方式里,一个文件所有 Block 指针都存储在 index node(inode)中,即 inode 存储了一个文件的所有元数据。

所以对于文件系统来说,只需保存好 inode 的 block number,就能顺着找到某个 file 所有的 block 信息。下面是 xv6 中的 inode 设计:

struct inode {
  uint dev;           
  uint inum;          
  int ref;            
  struct sleeplock lock; 
  int valid;          

  short type;         
  short major;
  short minor;
  short nlink;
  uint size;
  uint addrs[NDIRECT+1];
};

xv6 的文件系统只实现了一级 indirect:

Linux 上实现了 triple indirect:

 

四、Filesystem Consistency


一致性是文件系统中的一个重要的问题。如果需要创建一个文件,先将一个空闲的 block 标记为分配,再分配给文件 inode,且更新了指向新分配的 block 的指针,最后将 inode 指针更新到包含此文件的目录中。在这个完整的过程中,任意一个时刻发生了 crash,都会造成文件系统的不一致。

在 xv6 中,使用 log 来解决文件系统一致性问题。在以 log 为基础的文件系统下,任何对元数据的更新操作都将被封装到一个事务(A transaction is a set of updates that must be performed atomically)。例如上面提到创建文件的一系列操作,先将这些操作全部 add 进磁盘上的 log 里,然后向 log 写入一个 commit,最后将 log 中的更新 install 到真正的 data/metadata blocks。install 完成后,将 log 删除。

如果在这期间发生了 crash,恢复的原则就是:

这种 log 操作保证了文件系统的强一致性,但是也降低了部分性能。

 

五、Buffer Cache and Memory-mapped Files


通常来说,获取文件的方式有两种:

5.1、read()/write()

因为局部性原理,系统可能在一段时间内连续对一段磁盘区域进行操作。这种情况下,系统将经常访问的磁盘 block 放进内存中,保存在下面这个结构里(以xv6为例):

struct {
  struct spinlock lock;
  struct buf buf[NBUF];
  struct buf head;
} bcache;

而 buf 是带有两个指针的结构:

struct buf {
  int flags; 
  uint dev;  
  uint blockno;
  struct sleeplock lock;
  uint refcnt;
  struct buf *prev; 
  struct buf *next;
  struct buf *qnext;
  uchar data[BSIZE];
};

在初始化 bcache 的时候,将 bcache.buf 组织成一个双向链表,bcache.head 是最常使用的 buf。

执行 write() 操作,如果 block 的缓存 buf 在 bcache.buf 中,则立马返回;如果不在,就去磁盘上读取。执行 read() 操作,分为两种情况:

这取决于返回到用户程序时,写的数据是否已经体现在磁盘 block上。通常 OS 支持这两种操作。如果在乎性能,就使用异步些;如果在乎数据的安全性,就使用同步写。

5.2、mmap()

这是一种完全不同于上面的机制。操作系统将要使用的文件内容拷贝到物理内存页中,然后将这些页映射到虚拟地址空间。对虚拟地址空间的读写就转换成了对文件的读写。

当读一个内存映射文件(memory-mapped file)时,文件先被拷贝到物理内存,然后将物理内存区域映射到内核空间,而用户程序则直接读内和空间的相应区域(不用再额外的将内核空间的数据再拷贝到用户空间)。

当读一个内存映射文件(memory-mapped file)时,映射的部分与读操作一样。唯一影响性能的是映射模式:

前者映射是一个用户程序私有的,后者映射是多个用户程序共享的(共享模式下对文件的修改需对其他用户可见)。

 

六、总结


熟悉了一些理论知识后,下面继续阅读 xv6 中文件系统源码。

参考资料: