xv6-九

前言

这篇博客研究xv6的文件系统机制

文件系统总览

文件系统是用来管理持久型数据的子系统。
由于其需要解决很多问题，所以其抽象层次非常复杂，如下所示

另一方面，文件系统也被称为on-disk data structure，其需要在磁盘中以一定的数据结构进行组织，从而可以让操作系统高效的将文件系统导出到磁盘或从磁盘导入到内存中，如下所示

Disk Layer

设计

Disk Layer用于抽象对磁盘的读写
一般情况下，操作系统通过对磁盘的端口寄存器进行读写，从而完成对磁盘状态的控制和数据的读写。这也就是驱动

由于现实中有各种各样的磁盘，从而需要各种各样的驱动程序。为了隐藏这些实现细节，则通过Disk Layer将其抽象成统一的接口，即名称相同的函数指针
在驱动初始化时，将这些指针覆盖为驱动自己的函数。之后调用这些统一的接口，则相当于直接调用这些驱动的函数，从而将不同的驱动实现统一为了相同的接口

实现

由于目前xv6仅仅涉及到QEMU的virtio disk设备，因此其仅仅实现了位于kernel/virtio_disk.c的该设备的驱动函数virtio_disk_rw()，并将其当做Disk Layer的接口

即当xv6需要读、写磁盘时，其会调用virtio_disk_rw()函数完成

Buffer Cache Layer

设计

由于磁盘读、写速度相比较内存访问慢很多，因此操作系统会缓存频繁访问的磁盘的block，从而避免每次重新从磁盘中缓慢的读取数据

而为了保证正确性，操作系统需要确保任何时候，操作系统中任何磁盘的block有至多一个cache；任何一个block的cache同时被至多一个进程访问。这些可以通过xv6-八介绍的锁机制实现

一般情况下，操作系统中使用固定数量的buffer来缓存磁盘的block。当操作系统访问不在cache中的block时，其可能需要覆盖掉其他的buffer。为了尽可能减少读取磁盘的次数，每次选择覆盖掉Least Recently Used的buffer进行覆盖，因为一般Least Recently Used的buffer，也是最不可能再被重复使用的buffer

实现

结构体

xv6使用位于kernel/buf.h的struct buf结构体表示每一个buffer，如下所示

// kernel/fs.h
#define BSIZE 1024  // block size

// kernel/buf.h
struct buf {
  int valid;   // has data been read from disk?
  int disk;    // does disk "own" buf?
  uint dev;
  uint blockno;
  struct sleeplock lock;
  uint refcnt;
  struct buf *prev; // LRU cache list
  struct buf *next;
  uchar data[BSIZE];
};

xv6使用位于kernel/bio.c的bcache结构，抽象整个Buffer Cache Layer, 如下所示。

// kernel/bio.c
struct {
  struct spinlock lock;
  struct buf buf[NBUF];

  // Linked list of all buffers, through prev/next.
  // Sorted by how recently the buffer was used.
  // head.next is most recent, head.prev is least.
  struct buf head;
} bcache;

其中，xv6将Buffer Cache Layer中所有buffer通过静态数组的形式定义，并通过buffer的prev字段和next字段组织成双向链表。其中bcache.head的next方向是Less Recently Used的buffer(即bcache.head.next是Most Recently Used)；而prev恰恰相反，是More Recently Used(即bcache.head.prev是Least Recently Used)

bget()

Buffer Cache Layer中最重要的两个函数就是位于kernel/bio.c的bget()和brelse()

其中，bget()，顾名思义，会从Buffer Cache Layer中申请一个指定设备的指定block的buffer。这里有几点需要特别注意

1. 当前待缓存的block，可能已经在Buffer Cache Layer中被缓存；或者在被释放的某个buffer，其仍然保留该block的缓存数据，未被清除。为了尽可能减少磁盘读取次数，则优先返回这些buffer，并使用其上的数据即可。由于当前访问的block，往往之前也会被访问，则基于Least Recently Used算法，从bcache.head.next(即Most Recently Used)，沿着next方向(即Less Recently Used)遍历即可
2. 当申请到buffer后，再返回前需要获取锁，从而确保任何时候任何buffer，仅会被至多一个进程操作。如果有多个进程操作，可能会出现一个进程写；另一个进程读的情况，从而导致数据不一致

brelse()

brelse()，当xv6使用完buffer后，则xv6需要调用此函数释放buffer

为了实现减少磁盘的读、写，这里释放buffer时，需要注意如下几点：

1. 释放buffer时，仅仅释放获取的lock和计数引用，其余诸如设备号、块号和块内容等不能清除，因为后续可能会快被重新使用
2. 考虑到当前访问的块，很可能马上被继续访问，则将当前buffer移动到bcache.head.next位置(即Most Recently Used)，从而方便bget()复用这些数据

bread()/bwrite()

这里的逻辑很简单，通过Device Layer的virtio_disk_rw()，即可将磁盘的数据读入buffer；或将buffer中的数据写到磁盘中即可

需要注意的是，为了确保任何时候任何buffer被至多一个进程访问，其需要在上锁的情况下调用virtio_disk_rw()

Logging Layer

设计

Logging Layer用于文件系统的Crash Recovery

在文件系统进行一系列的磁盘写入工作时，崩溃(如突然断电等)的发生会导致磁盘数据的不一致。操作系统往往会通过Logging Layer来解决这类问题

在正式进行磁盘的写入工作前，操作系统现将计划要写入的数据以log的形式写入磁盘中。当所有的log都成功写入后，再向磁盘中写入一个特殊的commit记录，表示当前log成功写入。之后开始正式的磁盘写入工作，当操作系统完成所有的磁盘写入工作后，操作系统会清除掉瓷盘中的log，表示本次写入的完成

通过Logging Layer，即使发生Crash，在每次操作系统重启时，也能恢复文件系统的一致性。更具体地说，如果重启后，磁盘中存在特殊的commit，则根据保存的log，重新执行磁盘的写入工作。对于其余的情况，则操作系统认为要么写入工作还没开始，要么已经成功完成，并不会导致磁盘的非一致性错误，则无需处理

实现

结构体

xv6使用位于kernel/buf.c的struct log来描述Logging Layer，如下所示

// The log is a physical re-do log containing disk blocks.
// The on-disk log format:
//   header block, containing block #s for block A, B, C, ...
//   block A
//   block B
//   block C
//   ...
// Log appends are synchronous.

// Contents of the header block, used for both the on-disk header block
// and to keep track in memory of logged block# before commit.
struct logheader {
  int n;
  int block[LOGSIZE];
};

struct log {
  struct spinlock lock;
  int start;
  int size;
  int outstanding; // how many FS sys calls are executing.
  int committing;  // in commit(), please wait.
  int dev;
  struct logheader lh;
};
struct log log;

这里需要特别注意的是，由于文件系统需要在内存或磁盘上导出或加载。因此文件系统的on-disk结构和in-memory结构有极大的关联性，但是往往也有较大的不一致。因为in-memory结构除了需要包含on-disk的数据，还需要包含一些运算所需要的数据结构，诸如spinlock等的结构会出现在in-memory结构，而不会出现在on-disk结构中

begin_op()

在xv6的Logging Layer中，log的典型用法如下所示

begin_op();
...
bp = bread(...);
bp->data[...] = ...;
log_write(bp);
...
end_op();

顾名思义，位于kernel/log.c的begin_op()函数表示写磁盘的准备操作

begin_op()需要在Logging Layer中申请log空间。为此，其需要获取相关的自旋锁，从而互斥的判断相关字段即可

这里需要特别说明的是，begin_op()和end_op()之间因当包含完整的写操作，即仅仅执行这些操作，仍然能保持磁盘数据的一致性。如果一次要写入的数据特别多，则应该拆分成诸如kernel/file.c的filewrite()的多个“原子”写操作

log_write()

位于kenel/log.c的log_write()函数，将在正式执行写磁盘操作前，将要更新的block序号，写入到相关的in-memory的log数据中

这里需要特别注意的是，log_write()需要调用bpin()，增加相关block序号的buffer的引用计数，从而避免其被后续brelse()释放buffer()，导致更新内容丢失

end_op()

顾名思义，位于kernel/log.c的end_op()函数表示完成log的写入，将正式开始写磁盘操作

而写磁盘操作也分为以下几部分

1. 将此次写磁盘涉及的block数据(buffer中的更新数据)写入到磁盘的log部分
2. 将当前的in-memory的log对象(主要是log header数据)写入到on-disk的log对象中。这也是前面提到的特殊的commit内容
3. 将此次写磁盘涉及的block数据(buffer中的更新数据)写入到磁盘的data部分
4. 清空in-memory的log header，并将其写入到on-disk的log对象，彻底完成一次写磁盘操作

Inode Layer

设计

Inode Layer用来抽象文件系统中的文件项

正如前面所说的，文件系统的部分抽象层，往往包括in-memory表示和on-disk表示，而且in-memory表示往往比on-disk表示多了一些操作所需要的必须的数据结构,Inode Layer也不例外。对于on-disk的inode，其是描述一个文件或目录的大小和data block信息的数据结构；对于in-memory的inode，其就是on-disk的inode的拷贝，并且附带前面所说的内核所需要的必要结构信息

这里需要特别说明，为了减少磁盘读、写从而提高性能，操作系统会缓存inode，类似于Buffer Cache Layer——即释放inode时，仅仅减少该结构的引用计数，直到引用计数为0才最终释放inode

实现

结构体

xv6使用位于kernel/fs.h的struct dinode描述on-disk的inode；使用位于kernel/file.h的struct inode描述in-memory的inode，如下所示

// kernel/fs.h
// On-disk inode structure
struct dinode {
  short type;           // File type
  short major;          // Major device number (T_DEVICE only)
  short minor;          // Minor device number (T_DEVICE only)
  short nlink;          // Number of links to inode in file system
  uint size;            // Size of file (bytes)
  uint addrs[NDIRECT+1];   // Data block addresses
};

// kernel/file.h
// 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如何表示文件/目录项，如下图所示
。其数据在addrss1-address12和indirect所指向的data block中，但是存储的都是block块号，需要在具体的转换为block中数据才行

而xv6使用位于kernel/fs.c的icache结构描述inode缓冲，如下所示

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

iget()

在xv6中，Inode Layer的经典用法如下所示

ip = iget(dev, inum)
ilock(ip)
... example and modify ip->XXX ...
iunlock(ip)
iput(ip)

xv6使用位于kernel/fs.c的iget()函数，在inode缓冲中分配对应的inode

根据前面的分析，如果该inode已经被缓存，则添加引用计数ref即可；否则找到可以覆盖的inode缓冲，并初始化即可

需要特别注意的是，在iget()函数中并不会实际载入磁盘中的数据，仅仅初始化in-memory的inode中必要的数据结构而已

ilock()

xv6使用位于kernel/fs.c的ilock()函数，从而方便进程互斥的访问inode。一般当进程需要上锁时，则表明需要读、写资源，也就是进程会访问或更改inode数据，因此这里会将inode的on-disk数据加载到内存中，方便后续的操作

需要说明的是，这里仅仅加载inode的控制信息和部分数据信息，inode的所有数据信息都会通过bmap()函数，获取数据对应的block号，在使用bget()进行访问即可

iput()

xv6使用位于kernel/fs.c的iput()函数，释放inode，即减少inode的引用计数即可

需要特别注意的是，当inode的引用计数为0时，则表明此时对于inode表示的文件或目录操作结束，此时应当判断一下该文件是否应该被删除，即判断nlink字段是否为0，从而完成相关的删除操作即可

Directory Layer

设计

Directory Layer是用来抽象文件系统中的目录

实际上，目录就是一种特殊的文件——其内容就是一系列的目录项序列

一般来说，每一个目录项包含目录项的名称和目录项指向的文件inode的block块号，从而可以很好的抽象目录

实现

结构

正如前面分析的，目录是一种特殊的文件，所以xv6也使用位于kernel/fs.h的struct dinode和位于kernel/file.h的struct inode进行描述

但由于目录中的数据内容都是目录项，xv6使用位于kernel/fs.h的struct dirent描述目录项

dirlookup()

Directory Layer中最重要的，即在目录中找到对应的目录项。xv6使用位于kernel/fs.c的dirlookup()来实现该功能

其逻辑也很简单，也就是以目录项的格式，依次遍历当前目录数据即可

Pathname Layer

设计

Pathname Layer用来将human-friendly的路径，转换为Machine-friendly的Inode Layer的Inode

在直白一些，就是将树状文件系统，转换为on-disk文件系统。操作系统通过迭代查找目录，从而将路径信息转换为对应的inode，方便后续操作

实现

namex()

正如前面分析的，Pathname Layer主要就是通过迭代目录，从而转化为对应文件的inode

xv6通过namex()，非常精巧的实现了该要求。其namex()函数的定义就非常巧妙，如下所示

// Look up and return the inode for a path name.
// If parent != 0, return the inode for the parent and copy the final
// path element into name, which must have room for DIRSIZ bytes.
// Must be called inside a transaction since it calls iput().
static struct inode*
namex(char *path, int nameiparent, char *name)

即如果要查找父目录，则namex()返回父目录的inode，而name则被设置为剩余的路径元素信息，方便后续的文件查找；如果要查找的是该文件，则namex()直接返回该文件的inode，而name则被设置为NULL

这个API极大的拓展了Pathname Layer的灵活性，其实现也非常巧妙，特别是skipelem()的实现，如下所示

// kernel/fs.c

// Copy the next path element from path into name.
// Return a pointer to the element following the copied one.
// The returned path has no leading slashes,
// so the caller can check *path=='\0' to see if the name is the last one.
// If no name to remove, return 0.
//
// Examples:
//   skipelem("a/bb/c", name) = "bb/c", setting name = "a"
//   skipelem("///a//bb", name) = "bb", setting name = "a"
//   skipelem("a", name) = "", setting name = "a"
//   skipelem("", name) = skipelem("////", name) = 0
//
static char*
skipelem(char *path, char *name)
{
  char *s;
  int len;

  while(*path == '/')
    path++;
  if(*path == 0)
    return 0;
  s = path;
  while(*path != '/' && *path != 0)
    path++;
  len = path - s;
  if(len >= DIRSIZ)
    memmove(name, s, DIRSIZ);
  else {
    memmove(name, s, len);
    name[len] = 0;
  }
  while(*path == '/')
    path++;
  return path;
}

// Look up and return the inode for a path name.
// If parent != 0, return the inode for the parent and copy the final
// path element into name, which must have room for DIRSIZ bytes.
// Must be called inside a transaction since it calls iput().
static struct inode*
namex(char *path, int nameiparent, char *name)
{
  struct inode *ip, *next;

  if(*path == '/')
    ip = iget(ROOTDEV, ROOTINO);
  else
    ip = idup(myproc()->cwd);

  while((path = skipelem(path, name)) != 0){
    ilock(ip);
    if(ip->type != T_DIR){
      iunlockput(ip);
      return 0;
    }
    if(nameiparent && *path == '\0'){
      // Stop one level early.
      iunlock(ip);
      return ip;
    }
    if((next = dirlookup(ip, name, 0)) == 0){
      iunlockput(ip);
      return 0;
    }
    iunlockput(ip);
    ip = next;
  }
  if(nameiparent){
    iput(ip);
    return 0;
  }
  return ip;
}

即skipelem()在迭代路径时，提供了一次迭代所需要的充足信息，所以实现的逻辑非常清晰和优雅，值得好好学习!

File Descriptor Layer

设计

File Descriptor Layer用来将操作系统的各种资源(例如pipes、devies等)抽象为统一的系统接口——File Descriptor

操作系统一般会给每个进程一个独立的打开文件表，其中每一个都是资源(例如inode、device等)的包装。而这些打开文件表的表项，都被操作系统全局的文件表维护

实现

结构

xv6使用位于kernel/file.h的struct file描述File Descriptor接口，使用位于kernel/proc.h的proc->ofile描述进程的打开文件，使用位于kernel/file.c的ftable描述操作系统中所有的打开文件，如下所示

// kernel/file.h

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

// kernel/proc.h

// Per-process state
struct proc {
  struct spinlock lock;

  // p->lock must be held when using these:
  enum procstate state;        // Process state
  struct proc *parent;         // Parent process
  void *chan;                  // If non-zero, sleeping on chan
  int killed;                  // If non-zero, have been killed
  int xstate;                  // Exit status to be returned to parent's wait
  int pid;                     // Process ID

  // these are private to the process, so p->lock need not be held.
  uint64 kstack;               // Virtual address of kernel stack
  uint64 sz;                   // Size of process memory (bytes)
  pagetable_t pagetable;       // User page table
  struct trapframe *trapframe; // data page for trampoline.S
  struct context context;      // swtch() here to run process
  struct file *ofile[NOFILE];  // Open files
  struct inode *cwd;           // Current directory
  char name[16];               // Process name (debugging)
};

// kernel/file.c

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

Lab file system

本次lab用来加深对于xv6的文件系统机制的理解

Large files

要求

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 are done with this exercise when bigfile writes 65803 blocks and usertests runs successfully:

分析

如果要添加inode的doubly-indirect block的支持，则参考下图，更改所有涉及inode的data block的数据结构和操作即可

总的来说，涉及到inode的data block细节的，只有on-disk的struct dinode结构和in-memory的struct inode，相关的宏以及获取data block块号的bmap()和清空data block的itrunc()

实现

首先，我们将inode的data block布局，更改为11个direct block、1个indirect block和1个doubly indirect block，即更改struct dinode和struct inode的arrays字段，如下所示

// kernel/fs.h

#define NDIRECT     11                                //Number of direct data block
#define NINDE       1                                 //Number of indirect data entries
#define NBPIND      (BSIZE / sizeof(uint))            //Number of data block per indirect entry
#define NINDIRECT   (NINDE * NBPIND)
#define NDINDE      1                                 //Number of doubly indirect data enties
#define NINDEPDIND  (BSIZE / sizeof(uint))            //Number of indirect data entries per doubly indirect entry
#define NBPDIND     (NINDEPDIND * NBPIND)             //Number of data block per doubly indirect entry
#define NDINDIRECT  (NDINDE * NBPDIND)
#define MAXFILE     (NDIRECT + NINDIRECT + NDINDIRECT)

// On-disk inode structure
struct dinode {
  short type;           // File type
  short major;          // Major device number (T_DEVICE only)
  short minor;          // Minor device number (T_DEVICE only)
  short nlink;          // Number of links to inode in file system
  uint size;            // Size of file (bytes)
  uint addrs[NDIRECT+NINDE+NDINDE];   // Data block addresses
};


// kernel/file.h
// 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+NINDE+NDINDE];
};

其次来重构bmap()函数，其思路非常简单——由于inode的data block按照direct block、indirect block和doubly indirect block顺序排列，可以简单理解为将一维数组的下标解析为三维数组的坐标

对于direct block，其arrays数组中存储的就是data block的块号，则直接返回即可；对于indirect block，其arrays数组中存储的是direct block的块号，还需要再载入direct block块这一个步骤；类似的，对于doubly indirect block，其arrays数组中存储的时indirect block块号，还需要再载入indirect block、接着载入direct block块两个步骤，如下所示

// kernel/fs.c

// Return the disk block address of the nth block in inode ip.
// If there is no such block, bmap allocates one.
static uint
bmap(struct inode *ip, uint bn)
{
  uint addr, *a;
  struct buf *bp;

  if(bn < NDIRECT){
    if((addr = ip->addrs[bn]) == 0)
      ip->addrs[bn] = addr = balloc(ip->dev);
    return addr;
  }
  bn -= NDIRECT;

  if(bn < NINDIRECT){
    // Load indirect block, allocating if necessary.
    if((addr = ip->addrs[NDIRECT+bn/NBPIND]) == 0)
      ip->addrs[NDIRECT+bn/NBPIND] = addr = balloc(ip->dev);

    bn %= NBPIND;
    bp = bread(ip->dev, addr);
    a = (uint*)bp->data;
    if((addr = a[bn]) == 0){
      a[bn] = addr = balloc(ip->dev);
      log_write(bp);
    }
    brelse(bp);
    return addr;
  }
  bn -= NINDIRECT;

  if(bn < NDINDIRECT){
    // Load doubly indirect block, allocating if necessary.
    if((addr = ip->addrs[NDIRECT+NINDE+bn/NBPDIND]) == 0)
      ip->addrs[NDIRECT+NINDE+bn/NBPDIND] = addr = balloc(ip->dev);

    // Load indirect block, allocating if necessary.
    bn %= NBPDIND;
    bp = bread(ip->dev, addr);
    a = (uint*)bp->data;
    if((addr = a[bn/NBPIND]) == 0){
      a[bn/NBPIND] = addr = balloc(ip->dev);
      log_write(bp);
    }
    brelse(bp);

    bn %= NBPIND;
    bp = bread(ip->dev, addr);
    a = (uint*)bp->data;
    if((addr = a[bn]) == 0){
      a[bn] = addr = balloc(ip->dev);
      log_write(bp);
    }
    brelse(bp);
    return addr;
  }

  panic("bmap: out of range");
}

最后则是重构itrunc()，其依次遍历inode的direct block、indirect block和doubly indirect block，将这些block和这些block包含的data block通过bfree()释放掉即可，如下所示

// kernel/fs.c

// Truncate inode (discard contents).
// Caller must hold ip->lock.
void
itrunc(struct inode *ip)
{
  int i, j, k;
  struct buf *bp1, *bp2;
  uint *a1, *a2;

  // free direct data blocks
  for(i = 0; i < NDIRECT; i++){
    if(ip->addrs[i]){
      bfree(ip->dev, ip->addrs[i]);
      ip->addrs[i] = 0;
    }
  }

  // free indirect data blocks
  for(i = 0; i < NINDE; i++) {
    if(ip->addrs[NDIRECT+i]) {
      bp1 = bread(ip->dev, ip->addrs[NDIRECT+i]);
      a1 = (uint*)bp1->data;
      for(j = 0; j < NBPIND; j++) {
        if(a1[j])
          bfree(ip->dev, a1[j]);
      }
      brelse(bp1);
      bfree(ip->dev, ip->addrs[NDIRECT+i]);
      ip->addrs[NDIRECT+i] = 0;
    }
  }

  // free doubly indirect data blocks
  for(i = 0; i < NDINDE; i++) {
    if(ip->addrs[NDIRECT+NINDE+i]) {
      bp1 = bread(ip->dev, ip->addrs[NDIRECT+NINDE+i]);
      a1 = (uint*)bp1->data;
      for(j = 0; j < NINDEPDIND; j++) {
        if(a1[j]) {
          bp2 = bread(ip->dev, a1[j]);
          a2 = (uint*)bp2->data;
          for(k = 0; k < NBPIND; k++) {
            if(a2[k])
              bfree(ip->dev, a2[k]);
          }
          brelse(bp2);
          bfree(ip->dev, a1[j]);
        }
      }
      brelse(bp1);
      bfree(ip->dev, ip->addrs[NDIRECT+NINDE+i]);
      ip->addrs[NDIRECT+NINDE+i] = 0;
    }
  }

  ip->size = 0;
  iupdate(ip);
}

结果

执行如下命令，完成实验测试

make GRADEFLAGS="bigfile" grade

Symbolic links

要求

You will implement the symlink(char target, char path) system call, which creates a new symbolic link at path that refers to file named by target. For further information, see the man page symlink. To test, add symlinktest to the Makefile and run it. Your solution is complete when the tests produce the following output (including usertests succeeding).

$ symlinktest
Start: test symlinks
test symlinks: ok
Start: test concurrent symlinks
test concurrent symlinks: ok
$ usertests
...
ALL TESTS PASSED
$ 

分析

由于文件系统在解析符号链接文件时，会采用和其他文件类型完全不同的方式，因此可以添加新的文件类型即可

而为了完成符号链接功能，则重构系统调用中涉及文件系统的部分，添加符号链接类型的功能支持即可

实现

首先，在xv6中添加symlink系统调用，即添加相关的系统调用号和系统调用声明，如下所示

// kernel/syscall.h

// System call numbers
#define SYS_symlink 22

// kernel/syscall.c
extern uint64 sys_symlink(void);

static uint64 (*syscalls[])(void) = {
  ...
[SYS_symlink] sys_symlink,
};

// user/user.h
int symlink(const char *target, const char *linkpath);

// user/usys.pl
entry("symlink");

其次则是实现系统调用symlink()，即完成必要的检查后，创建相关的符号链接类型的文件即可。其中根据要求，符号链接类型的文件内容是传入的路径字符串即可，如下所示

// kernel/sysfile.c

// Create a symbol file pointing to the given path
uint64
sys_symlink(void)
{
  char target[MAXPATH], linkpath[MAXPATH];
  struct inode *ip;

  if(argstr(0, target, MAXPATH) < 0 || argstr(1, linkpath, MAXPATH) < 0)
    return -1;

  begin_op();
  if((ip = create(linkpath, T_SYMLINK, 0, 0)) == 0){
    end_op();
    return -1;
  }

  // write the target to the inode
  if(writei(ip, 0, (uint64)target, 0, MAXPATH) != MAXPATH)
    panic("symlink: writei");

  iunlockput(ip);
  end_op();

  return 0;
}

下面则是添加符号链接的操作。实际上，符号链接的作用，就是路径替换，即解析该符号链接时，相当于解析其替换的文件。在具体一些，在xv6中，即解析其替换的文件的inode。因此，可以通过更改open系统调用，返回其实际指向的文件的inode即可，如下所示

// kernel/sysfile.c

uint64
sys_open(void)
{
  char path[MAXPATH];
  int fd, omode, iterate;
  struct file *f;
  struct inode *ip;
  int n;

  if((n = argstr(0, path, MAXPATH)) < 0 || argint(1, &omode) < 0)
    return -1;

  begin_op();

  if(omode & O_CREATE){
    ip = create(path, T_FILE, 0, 0);
    if(ip == 0){
      end_op();
      return -1;
    }
  } else {

    if((ip = namei(path)) == 0){
      end_op();
      return -1;
    }

    ilock(ip);

    // deal with symlink file
    if((omode & O_NOFOLLOW) == 0) {
      iterate = 0;
      while(ip->type == T_SYMLINK) {
        if((readi(ip, 0, (uint64)path, 0, MAXPATH)) != MAXPATH || iterate++ >= MAXITER) {
          iunlockput(ip);
          end_op();
          return -1;
        }

        iunlockput(ip);
        if((ip = namei(path)) == 0) {
          end_op();
          return -1;
        }
        ilock(ip);
      }
    }

    if(ip->type == T_DIR && omode != O_RDONLY){
      iunlockput(ip);
      end_op();
      return -1;
    }
  }

  ...

  iunlock(ip);
  end_op();

  return fd;
}

结果

执行如下命令，完成实验测试

make GRADEFLAGS="symlink" grade