xv6 Bigger Files

Introduction

In this assignment you’ll increase the maximum size of an xv6 file. Currently xv6 files are limited to 140 sectors, or 71,680 bytes. This limit comes from the fact that an xv6 inode contains 12 “direct” block numbers and one “singly-indirect” block number, which refers to a block that holds up to 128 more block numbers, for a total of 12+128=140. You’ll change the xv6 file system code to support a “doubly-indirect” block in each inode, containing 128 addresses of singly-indirect blocks, each of which can contain up to 128 addresses of data blocks. The result will be that a file will be able to consist of up to 16523 sectors (or about 8.5 megabytes).

Preliminaries

Modify your Makefile’s CPUS definition so that it reads:

CPUS := 1

Add

1	QEMUEXTRA = -snapshot

right before QEMUOPTS

The above two steps speed up qemu tremendously when xv6 creates large files.

mkfs initializes the file system to have fewer than 1000 free data blocks, too few to show off the changes you’ll make. Modify param.h to set FSSIZE to:

1	#define FSSIZE 20000 // size of file system in blocks

Download big.c into your xv6 directory, add it to the UPROGS list, start up xv6, and run big. It creates as big a file as xv6 will let it, and reports the resulting size. It should say 140 sectors.

What to Look At

The format of an on-disk inode is defined by struct dinode in fs.h. You’re particularly interested in NDIRECT, NINDIRECT, MAXFILE, and the addrs[] element of struct dinode. Look here for a diagram of the standard xv6 inode.

The code that finds a file’s data on disk is in bmap() in fs.c. Have a look at it and make sure you understand what it’s doing. bmap() is called both when reading and writing a file. When writing, bmap() allocates new blocks as needed to hold file content, as well as allocating an indirect block if needed to hold block addresses.

bmap() deals with two kinds of block numbers. The bn argument is a “logical block” – a block number relative to the start of the file. The block numbers in ip->addrs[], and the argument to bread(), are disk block numbers. You can view bmap() as mapping a file’s logical block numbers into disk block numbers.

Your Job

Modify bmap() so that it implements a doubly-indirect block, in addition to direct blocks and a singly-indirect block. You’ll have to have only 11 direct blocks, rather than 12, to make room for your new doubly-indirect block; you’re not allowed to change the size of an on-disk inode. The first 11 elements of ip->addrs[] should be direct blocks; the 12th should be a singly-indirect block (just like the current one); the 13th should be your new doubly-indirect block.

You don’t have to modify xv6 to handle deletion of files with doubly-indirect blocks.

If all goes well, big will now report that it can write 16523 sectors. It will take big a few dozen seconds to finish.

Solution

在解决此问题之前，我们首先看一张图来了解xv6操作系统关于文件系统的架构和实现：

xv6文件系统将文件的结构分成了7层，从最上层的文件描述符到最底层的磁盘。

当今的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())会移除队列开头的请求，唤醒队列开头请求所对应的进程。如果还有后续的请求，就会将其移到队列开头，开始处理下一个磁盘请求。

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

1 2	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操作系统的硬盘中，依次存放了如下几个硬盘块。对这些硬盘块的索引是直接使用一个整数来进行的，

1	[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()等基本操作。