xv6源码阅读体验

 

一、介绍


这篇文章纪录下我学习 xv6 文件系统(以后简称xv6fs)的过程,先导篇: xv6: 文件系统(一)

xv6fs 算是整个 xv6 源码中的重头戏,整个文件系统很抽象,对于我这种 Unix 小白,头一次阅读这种代码十分的懵。经过反复阅读,终于领悟到了一点其中的奥妙。

下面是 xv6fs 逻辑上的分层图:

+------------------+
|  File Descriptor |
+------------------+
|     Pathname     |
+------------------+
|     Directory    |
+------------------+
|      Inode       |
+------------------+
|     Logging      |
+------------------+
|   Buffer Cache   |
+------------------+
|       Disk       |
+------------------+

为了方便理解,首先给出一个范例。这个例子是一个文件树在磁盘上的分布情况:

/
+----+  f1
|
+----+  f2
|
+----+  f3
|
+----+  f4
|
+----+  f5
|
+----+  d1
|       +----+  f6
|       |
|       +----+  f7
+-----+ d2
|       +----+  f8
|       |
|       +----+  f9
|       |
|       +----+  f10
+----+  d3
|       +----+  f11
|       |
|       +----+  f12
|       |
|       +----+  f13
|       |
|       +----+  f14

结合 mkfs.c 和源码中提供的有关文件的常量可以画出这个文件结构的磁盘布局图:

标记 D 和 F 分别表示 directory 或者 file,结构为 dinode(大小为64B)。一般一个 F-dinode 会占用多个 data block。一个 D-dinode 基本上占用一个 data block 就够了。如上图中,根目录(/)所对应的第 0 个 data block 中装有 10 个 struct dirent。它们分别是:

.
..
f1
f2
f3
f4
f5
d1
d2
d3

这样我们就能对文件系统有一个整体对认识。

 

二、Disk


xv6 中磁盘驱动主要由 ide.c 文件实现。这个文件下有以下变量和函数:

static struct spinlock idelock;
static struct buf *idequeue;
static int havedisk1;

static int idewait(int checkerr);
static void idestart(struct buf *b);
void iderw(struct buf *b);
void ideintr(void);
void ideinit(void);

其中暴露给 buffer cache 层的是函数 iderw()。此函数发起对磁盘的读写 idestart()。因为磁盘操作很耗时,随即进入睡眠状态:

void
iderw(struct buf *b)
{
  ...
  if(idequeue == b)
    idestart(b);
  while((b->flags & (B_VALID|B_DIRTY)) != B_VALID){
    sleep(b, &idelock);
  }
  ...
}

等到磁盘的读写完成后,会收到一个来自磁盘控制器的中断 T_IRQ0 + IRQ_IDE,然后进入 ideintr() 函数:

void
ideintr(void)
{
  ...
  if(!(b->flags & B_DIRTY) && idewait(1) >= 0)
    insl(0x1f0, b->data, BSIZE/4);

  b->flags |= B_VALID;
  b->flags &= ~B_DIRTY;
  wakeup(b);

  if(idequeue != 0)
    idestart(idequeue);
  ...
}

处理来自磁盘的中断,对应队列中第一个buffer,要么是磁盘控制器上有新的数据,需要读取,要么是告诉 OS 之前的写操作已经完成,这取决于前面 iderw()-> idestart() 执行的写操作还是读操作。执行完 wakeup(b) 后,唤醒在 iderw() 中睡眠的进程,整个 buffer 的操作结束。

通过中断的方式,可以让等待磁盘操作的进程睡眠,让出处理器。这是一种比较有效的方式。可是这个进程还是会阻塞在 iderw() 函数。

 

三、Buffer Cache


这一层唯一操作的数据结构是:

struct {
  struct spinlock lock;
  struct buf buf[NBUF];

  struct buf head;
} bcache;


首先 buffer cache 通过 binit() 函数初始化:

void
binit(void)
{
  struct buf *b;

  initlock(&bcache.lock, "bcache");

  bcache.head.prev = &bcache.head;
  bcache.head.next = &bcache.head;
  for(b = bcache.buf; b < bcache.buf+NBUF; b++){
    b->next = bcache.head.next;
    b->prev = &bcache.head;
    initsleeplock(&b->lock, "buffer");
    bcache.head.next->prev = b;
    bcache.head.next = b;
  }
}

它将 bcache.buf 初始化成一个双向链表,这个双向链表实现了 LRU 算法,只需知道 bcache.head 是最常使用的 buffer。

这一层暴露给 log 层的函数有三个:

struct buf* bread(uint dev, uint blockno);
void bwrite(struct buf *b);
void brelse(struct buf *b);

首先看 bread() 函数:

struct buf*
bread(uint dev, uint blockno)
{
  struct buf *b;
  b = bget(dev, blockno);
  if((b->flags & B_VALID) == 0) {
    iderw(b);
  }
  return b;
}

这个函数实现的关键在于 bget():

static struct buf* bget(uint dev, uint blockno)
{
  struct buf *b;
  acquire(&bcache.lock);
  for(b = bcache.head.next; b != &bcache.head; b = b->next){
    if(b->dev == dev && b->blockno == blockno){
      b->refcnt++;
      release(&bcache.lock);
      acquiresleep(&b->lock);
      return b;
    }
  }
  for(b = bcache.head.prev; b != &bcache.head; b = b->prev){
    if(b->refcnt == 0 && (b->flags & B_DIRTY) == 0) {
      b->dev = dev;
      b->blockno = blockno;
      b->flags = 0;
      b->refcnt = 1;
      release(&bcache.lock);
      acquiresleep(&b->lock);
      return b;
    }
  }
  panic("bget: no buffers");
}

这个函数遍历 bcache.buf 双向链表,先从 bcache.head 起,正向查找链表(这里利用了程序的局部性原理)。看能不能找到指定参数的 block 的缓存(第一个for循环)。如果找不到,再反向查找链表(第二个for循环),找到一个b->refcnt为0,且数据与磁盘同步 buffer,将这个 buffer 设置为新的参数,并返回。注意返回之前要对 buffer 加锁

当我们使用 bread() 拿到某个 block 的 buffer 后,有可能对其数据进行修改。修改完后,调用 bwrite() 将 buffer 中的修改写回到磁盘,最后调用 brealse(),表明对 buffer 的操作已经结束。

通常对这一层的接口有下面两种形式的调用:

+-------+      +--------+
| bread +----->+ brelse |
+-------+      +--------+

+-------+      +--------+     +--------+     +--------+
| bread +----->+ update +---->+ bwrite +---->+ brelse |
+-------+      +--------+     +--------+     +--------+

注意,获取锁的操作都隐藏在了 bread() 与 brelse() 中。调用 brelse() 后就不能再对同一个 buffer 进行操作了。

 

四、Log Layer


在 log 层,两个重要的结构是:

struct logheader {
  int n;
  int block[LOGSIZE];
};

struct log {
  struct spinlock lock;
  int start;
  int size;
  int outstanding;
  int committing;
  int dev;
  struct logheader lh;
};
struct log log;

该层暴露在外的接口有:

void begin_op(void);
void log_write(struct buf *b);
void end_op(void);
void initlog(int dev);

在 xv6 中,一个文件操作大致是如下顺序:

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

首先使用 begin_op():

void
begin_op(void)
{
  acquire(&log.lock);
  while(1){
      ...
      log.outstanding += 1;
      ...
    }
  }
}

说明即将开始对文件进行操作,在 log 区为预留一块区域(log.outstanding += 1)存放 log。然后开始对 buffer 进行修改。与 buffer cache 层概念不同的是,这里不会立刻调用 bwrite() 将修改写回磁盘快(这样就达不到log的目的了),而是使用了 log_write():

void
log_write(struct buf *b)
{
  ...
  log.lh.block[i] = b->blockno;
  ...
}

在 logheader 中记录下对哪些 block 进行了修改。然后调用 end_op(),这个函数经过一系列的判断后,最终执行 commit():

static void commit()
{
  if (log.lh.n > 0) {
    write_log();    
    write_head();   
    install_trans();
    log.lh.n = 0;
    write_head();   
  }
}

调用 write_log():

static void write_log(void)
{
  int tail;
  for (tail = 0; tail < log.lh.n; tail++) {
    struct buf *to = bread(log.dev, log.start+tail+1);
    struct buf *from = bread(log.dev, log.lh.block[tail]);
    memmove(to->data, from->data, BSIZE);
    bwrite(to);  // write the log
    brelse(from);
    brelse(to);
  }
}

先将所有的修改存放到 log 区(紧跟着logheader)。然后调用 write_head():

static void write_head(void)
{
  struct buf *buf = bread(log.dev, log.start);
  struct logheader *hb = (struct logheader *) (buf->data);
  int i;
  hb->n = log.lh.n;
  for (i = 0; i < log.lh.n; i++) {
    hb->block[i] = log.lh.block[i];
  }
  bwrite(buf);
  brelse(buf);
}

将之前记录的修改过的 block 号存进磁盘上的 logheader.block[] 中。接着调用 install_trans:

static void install_trans(void)
{
  int tail;
  for (tail = 0; tail < log.lh.n; tail++) {
    struct buf *lbuf = bread(log.dev, log.start+tail+1); 
    struct buf *dbuf = bread(log.dev, log.lh.block[tail]);
    memmove(dbuf->data, lbuf->data, BSIZE);
    bwrite(dbuf);  // write dst to disk
    brelse(lbuf);
    brelse(dbuf);
  }
}

最终将 log 中暂存的修改写入它们在磁盘上原本的地方。最后执行:

log.lh.n = 0;
write_head();

将 log 标记为空。整个过程类似于:

 

五、Inode Layer


这一层是比较复杂的,其中有两个关键的结构:

struct inode {
  uint dev;           // Device number
  uint inum;          // Inode number
  int ref;            /*表明有多少个 C 指针指向这个inode,只有这个数不为零时,
                       *inode才存在于内存中,iget()和iput()修改它
                       *这个指针来自 file descriptor,current working directory,或者exec()函数
                       */
  struct sleeplock lock; // protects everything below here
  int valid;          // inode has been read from disk?
  
  // copy of disk inode
  short type;         // File type  dinode free:0   T_DIR:1   T_FILE:2   T_DEV:3
  short major;
  short minor;
  short nlink;        /*表明有多少个 directory entry 链接到 inode,当这个数为 0 时,type也等于0*/
  uint size;
  uint addrs[NDIRECT+1];
};
// On-disk inode structure
struct dinode {
  short type;           // File type  dinode free:0   T_DIR:1   T_FILE:2   T_DEV:3
  short major;          // Major device number (T_DEV only)
  short minor;          // Minor device number (T_DEV only)
  short nlink;          /*表明有多少个 directory entry 链接到 inode,当这个数为 0 时,type也等于0*/
  uint size;            /*inode所表示文件字节数*/
  uint addrs[NDIRECT+1];   /*表明inode表示的文件内容都在哪些block中*/
};

这两个结构部分内容是相同的,dinode 被拷贝到内存存放在 inode 中。

inode 描述了一个文件,这个文件的内容通过 dinode.addrs[] 描述,它们指向 data block,其余的成员则描述了文件的元数据:

inodes 顺序的分布在磁盘上,起始位置为 superblock.startinode。与普通的 data block 一样,OS 将一些常用的 inode 存放在内存:

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

因为存在多个进程使用同一个 inode 的情况,所以 in-memory inode 的另一个作用是同步。下面来看一下 fs.c(文件系统) 中对外的接口:

// inode,主要是实现在多进程下对 inode 的同步
static struct inode* iget(uint dev, uint inum);
void iinit(int dev);
struct inode* ialloc(uint dev, short type);
void iupdate(struct inode *ip);
struct inode* idup(struct inode *ip);
void ilock(struct inode *ip);
void iunlock(struct inode *ip);
void iput(struct inode *ip);
void iunlockput(struct inode *ip);

//inode-content,这些函数对 inode 对内容进行操作
static uint bmap(struct inode *ip, uint bn);
static void itrunc(struct inode *ip);
void stati(struct inode *ip, struct stat *st);
int readi(struct inode *ip, char *dst, uint off, uint n);
int writei(struct inode *ip, char *src, uint off, uint n);

下面选择合适的顺序,对其中重要的函数依次介绍:

static struct inode* iget(uint dev, uint inum)
{
  ...
  ip = &icache.inode[i];
  if(ip->ref > 0 && ip->dev == dev && ip->inum == inum){
    ip->ref++;
    return ip;
  }
  ...
}

这个函数找到一个返回一个指定参数的 inode 指针(即返回在 icache.inode 中的位置)。inum 是 inode 在磁盘 inode 区域的序号。然后执行:

struct inode* ialloc(uint dev, short type)
{
  ...
  for(inum = 1; inum < sb.ninodes; inum++){
    bp = bread(dev, IBLOCK(inum, sb));
    dip = (struct dinode*)bp->data + inum%IPB;
    if(dip->type == 0){  
      memset(dip, 0, sizeof(*dip));
      dip->type = type;
      log_write(bp);  
      brelse(bp);
      return iget(dev, inum);
    }
    brelse(bp);
  }
  panic("ialloc: no inodes");
}

这个函数将一个磁盘空闲的 inode 标记为使用,再在 icache.inode[] 里找找到的槽与之对应。这时磁盘上的 dinode 与内存中的 inode 只是简单的建立了映射关系,它们的内容并没有联系。而且由 ialloc() 返回的 inode 指针没有加锁,并不能排它的使用。所以这时应该将 ialloc() 返回的 inode 传入 ilock() 函数:

void ilock(struct inode *ip)
{
  ...
  acquiresleep(&ip->lock);
  if(ip->valid == 0){
    bp = bread(ip->dev, IBLOCK(ip->inum, sb));
    dip = (struct dinode*)bp->data + ip->inum%IPB;
    ip->type = dip->type;
    ip->major = dip->major;
    ip->minor = dip->minor;
    ip->nlink = dip->nlink;
    ip->size = dip->size;
    memmove(ip->addrs, dip->addrs, sizeof(ip->addrs));
    ...
  }
}

这个函数首先做的就是对 inode 加锁,再将磁盘 dinode 对内容赋值给内存 inode,前提是它们已经建立了映射关系。这时就可以对 inode 对内容进行一系列的操作了。操作完后,使用 iunlock() 将 inode 上的锁释放:

void iunlock(struct inode *ip)
{
  if(ip == 0 || !holdingsleep(&ip->lock) || ip->ref < 1)
    panic("iunlock");
  releasesleep(&ip->lock);
}

最后通常执行 iput() 函数:

void iput(struct inode *ip)
{
  acquiresleep(&ip->lock);
  if(ip->valid && ip->nlink == 0){
    acquire(&icache.lock);
    int r = ip->ref;
    release(&icache.lock);
    if(r == 1){
      itrunc(ip);
      ip->type = 0;
      iupdate(ip);
      ip->valid = 0;
    }
  }
  releasesleep(&ip->lock);

  acquire(&icache.lock);
  ip->ref--;
  release(&icache.lock);
}

表明当前对 inode 对操作结束,ip->ref–。如果这时最后一个引用的指针,则需要执行 itrunc(ip) 将 ip->addrs 的内容置零。执行 iupdate(ip) 将前面对 inode 的更新写入磁盘。总结一下大致对操作流程:

  +--------+
  | ialloc |
  +---+----+
      | iget
      v
  +---+----+
  | ilock  |
  +---+----+
      |
      v
+-----+------+
|  stati     |
|  writei    |
|  readi     | 这些是对 inode 内容的操作
|   ...      |
+-----+------+
      |
      v
 +----+----+
 | iunlock |
 +----+----+
      |
      v
 +----+----+
 |  iput   |
 +---------+

下面是三个重要的函数,它们对 inode 对内容进行读写:

void stati(struct inode *ip, struct stat *st)
{
  st->dev = ip->dev;
  st->ino = ip->inum;
  st->type = ip->type;
  st->nlink = ip->nlink;
  st->size = ip->size;
}
int readi(struct inode *ip, char *dst, uint off, uint n)
{
  ...
  for(tot=0; tot<n; tot+=m, off+=m, dst+=m){
    bp = bread(ip->dev, bmap(ip, off/BSIZE));
    m = min(n - tot, BSIZE - off%BSIZE);
    memmove(dst, bp->data + off%BSIZE, m);
    brelse(bp);
  }
  ...
}
int writei(struct inode *ip, char *src, uint off, uint n)
{
  ...
  for(tot=0; tot<n; tot+=m, off+=m, src+=m){
    bp = bread(ip->dev, bmap(ip, off/BSIZE));
    m = min(n - tot, BSIZE - off%BSIZE);
    memmove(bp->data + off%BSIZE, src, m);
    log_write(bp);
    brelse(bp);
  }
  ...
}

通过 bmap() 简化 inode 多级链表的设计,传入 inode 下某个 block 号,返回此 block 的 buffer。 off 是在文件中的字节偏移量。本地变量 tot 纪录着已经读取了多少字节,n - tot 表示还剩多少字节。关键的是这条语句:

m = min(n - tot, BSIZE - off%BSIZE);

每次将剩余操作字节数与 off 到 block 右边界的大小做对比,取最小的。这样就能保证一次读取的字节数最多不超过 BSIZE。

 

六、Directory Layer


这一层操作的数据结构是:

struct dirent {
  ushort inum; // inode number
  char name[DIRSIZ]; // DIRSIZ 14 文件名
};

目录内部是一种特殊的文件,它对应的 inode.type 为 T_DIR。下面是目录层两个重要的接口:

struct inode* dirlookup(struct inode *dp, char *name, uint *poff);
int dirlink(struct inode *dp, char *name, uint inum);
struct inode*
dirlookup(struct inode *dp, char *name, uint *poff)
{
  ...
  if(dp->type != T_DIR)
    panic("dirlookup not DIR");
  for(off = 0; off < dp->size; off += sizeof(de)){
    if(readi(dp, (char*)&de, off, sizeof(de)) != sizeof(de))
      panic("dirlookup read");
    if(de.inum == 0)
      continue;
    if(namecmp(name, de.name) == 0){
      if(poff)
        *poff = off;
      inum = de.inum;
      return iget(dp->dev, inum);
    }
  }
  return 0;
}

这个函数定位目录 dinode 对应的 datablock,然后从这个 datablock 中依次读取 struct dirent,将其 entry name 与目标 name 比较。如果找到,通过 iget(dp->dev, inum) 获取到这个 entry 对应的 inode。下面是 dirlink() 函数:

int dirlink(struct inode *dp, char *name, uint inum)
{
  ...
  for(off = 0; off < dp->size; off += sizeof(de)){
    if(readi(dp, (char*)&de, off, sizeof(de)) != sizeof(de))
      panic("dirlink read");
    if(de.inum == 0)
      break;
  }
  strncpy(de.name, name, DIRSIZ);
  de.inum = inum;
  if(writei(dp, (char*)&de, off, sizeof(de)) != sizeof(de))
    panic("dirlink");
  return 0;
}

在 dp 目录下,建立一个与其他目录/文件有关联的 entry。

 

六、Pathname Layer


这一层主要实现函数有两个:

static char* skipelem(char *path, char *name);
static struct inode* namex(char *path, int nameiparent, char *name);

skipelem() 完成的功能类似如下:

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

namex() 则使用 skipelem() 对路径名进行拆分,返回路径名末尾元素所对应的 inode:

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'){
      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;
}

如果执行 namex() 时缓存命中率很低,就会多次进行磁盘操作,这时 namex() 函数巧妙的将锁加在单个目录上,就能使路径中的目录搜索并行。

 

七、File Layer


这一层主要给系统调用提供支持,有一个全局的数据结构 ftable:

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

这个结构里面保存所有已经打开的文件。以下函数对其操作:

struct file* filealloc(void);
struct file* filedup(struct file *f);
void fileclose(struct file *f);
int filestat(struct file *f, struct stat *st);
int fileread(struct file *f, char *addr, int n);
int filewrite(struct file *f, char *addr, int n);

以系统调用 sys_read() 为例:

int
sys_read(void)
{
  struct file *f;
  int n;
  char *p;
  if(argfd(0, 0, &f) < 0 || argint(2, &n) < 0 || argptr(1, &p, n) < 0)
    return -1;
  return fileread(f, p, n);
}

int fileread(struct file *f, char *addr, int n)
{
  int r;
  if(f->readable == 0)
    return -1;
  if(f->type == FD_PIPE)
    return piperead(f->pipe, addr, n);
  if(f->type == FD_INODE){
    ilock(f->ip);
    if((r = readi(f->ip, addr, f->off, n)) > 0)
      f->off += r;
    iunlock(f->ip);
    return r;
  }
  panic("fileread");
}
struct file {
  enum { FD_NONE, FD_PIPE, FD_INODE } type;
  int ref;
  char readable;
  char writable;
  struct pipe *pipe;
  struct inode *ip;
  uint off;
};

fileread() 先判断文件对应的是 pipe 还是 inode,分别做处理。 如果是 inode,则使用 readi() 来读取数据,并修改 file 读取后的文件偏移量:

f->off += r;

除了全局的 ftable,每个进程中也保存了自己使用的文件信息:

struct proc {
  ...
  struct file *ofile[NOFILE];
  ...
};

proc.ofile[i] 的 index i 就是返回给用户的 File Descriptor,里面的指针指向 ftable 里的文件。最后再看一个常用的系统调用 sys_open():

int
sys_open(void)
{
  ...
  if(omode & O_CREATE){
    ip = create(path, T_FILE, 0, 0);
    ...
  } else {
    ...
  }
  if((f = filealloc()) == 0 || (fd = fdalloc(f)) < 0){
    ...
  }
  iunlock(ip);
  end_op();
  f->type = FD_INODE;
  f->ip = ip;
  f->off = 0;
  f->readable = !(omode & O_WRONLY);
  f->writable = (omode & O_WRONLY) || (omode & O_RDWR);
  return fd;
}

如果是一个新文件,create() 会在磁盘上标记一个 dinode 为使用,并返回其指针。然后使用 filealloc() 在 ftable 中分配一个 file, 最后使用 fdalloc()filealloc() 返回的 file 指针设置给进程的 proc.ofile[i],最后将 i 作为 fd 返回。

 

八、总结


以上就是 xv6 的文件系统概要。相比较 linux,xv6fs 算不上复杂,但是其分层的设计理念确实影响到了后来的一些操作系统,包括 linux。 本文的源码分析也只分析了大概。笔者会对这部分源码反复的阅读,所以本文内容随着时间会有所更新。