1.概览

xv6的文件系统由7层组成,首先就是最下面的硬件层,cache层在上面通过缓存硬件块来实现操作系统同步地访问硬盘块(这样可以降低操作系统访问硬盘块的时间),并且可以进行简单的同步管理,这样子可以保证只有一个进程同时访问一个硬盘块.记录层让更高层次的程序在在一次处理中能够处理多个硬件块,保证这些硬件块是同步处理的(要么都不处理,要么都处理).inode层负责描述文件,其中一个文件对应着一个inode,这个inode存储着许多文件的信息.其中inode层负责存储文件的控制信息,其中有一个索引负责带领文件找到索引本身.文件目录层负责实现具体的文件目录.路经名层负责完善文件树.这样可以根据文件的路径取访问文件了.文件描述器层负责完善许多UNIX抽象文件接口,负责给用户程序提供文件系统相关的系统调用.

image-20220326161104594

硬盘把数据按照硬盘扇区为单位连续地存放在磁盘中,每一个磁盘扇区大小是512字节.其中第0块是第一个512字节.第1块是第513-1024字节,以此类推.xv6操作系统维护一个buf结构体.存储在这个结构体的数据可能和磁盘实际存储的数据不一样.有一种可能就是数据写进buf结构体,但还是没有写进磁盘块.(类似于cache,cache也有脏数据嘛)

还需要注意的是,在操作系统中,磁盘块的大小一般是磁盘扇区大小的两倍.所以说在xv6中我们认为一块就是两个扇区,就是1024字节.到后面我们逻辑上认为一块就是两个扇区,1024字节.

#define BSIZE 1024  // block size
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];
};

一个文件系统必须有一个计划,就是哪些磁盘块存放控制文件总体信息的inode,哪些磁盘块存放具体的文件.在这里,xv6把磁盘分成了几个部分,第0块是boot块,这里面存放着引导操作系统的代码.第1块又被称为“超级块”,超级块中存放了关于整个文件系统的原数据(包括文件系统所有块的数量,inode的数量,还有文件块的数量).从2后面就是记录,接着就是inode,接着就是bit map(这个bitmap可以帮助我们确定哪些块已经被使用了),最后就是存放的文件块.

2.buffer cache层.

buffer cache层有两个作用,第一个是同步,在内存中只有一个磁盘块的拷贝,还有就是只有一个进程能够访问这个磁盘块的拷贝.第二个作用就是可以把比较常用的磁盘块放入缓存区里面,这样可以加快进程读写磁盘的速度.

buffer cache层主要提供了两个API,分别是bread()和bwrite().

bread()负责获取一个块的存储在内存中的副本,我们之后的读写操作就是在内存中的副本进行的.bwirte()就负责把内存中副本写入到磁盘中.总的来说是read()操作把磁盘中信息读取到内存,write就是把内存中的信息写入到磁盘.在最后我们要调用brelease来释放这个内存块的锁.总之bread()返回了一个带锁的buffer,brelease就负责把这个锁释放掉.

因为这个本质上也是一个cache.当操作系统要求访问一个不再buffer的磁盘块,它就需要淘汰,淘汰就选用最久未使用算法即可.

2.1 Cache层重要数据结构定义

buf数据结构定义。valid字段表示该buf中是否存储了有效内容;字段disk的意思是缓冲区的内容已经被提交到了磁盘,这可能会改变缓冲区(如,把磁盘中的数据写到data,这个类似于cache的脏位,代表这个是不是在cache中写过);devblockno标识该buf存储的磁盘块设备和扇区号;data则是buf实际缓存的内容;而prevnext就代表一个双向链表.其中refcnt代表这个块是不是可用的,或者代表这个buf链接了多少个磁盘块.

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];
};

bcache数据结构定义。bcache用于管理所有的buffer,将所有的buf用双链表进行连接,head是链表头,不存储实际的buf。所有的代码访问bcache是访问head,并不会访问buf数组.我们了解过用硬件实现的cache,但是这是第一次遇见用软件实现的cache.

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;

2.2 Cache层的函数定义

binit()函数:初始化bcache,把所有的buf使用双链表进行连接。

void
binit(void)
{
  struct buf *b;

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

  // Create linked list of buffers
  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;
  }
}

bget()函数:

bget函数首先获取bcache.lock,至多扫描两遍双链表,第一遍从前到后,如果磁盘块已经缓存至buf中,则在第一遍循环之后就会返回该buf;否则执行第二次反向扫描,寻找目前未使用的buf,将buf的必要字段进行标记之后返回该buf。

注意:在将buf返回之前,需要获取该buf的锁(buf.lock);赋值语句b->valid = 0,它确保了bread将从磁盘读取块数据,而不是错误地使用缓冲区里之前的数据。获取锁的目标是,现在只有一个进程能够访问这段cache,这是为了方便各进程进行同步.当然我们获得了我们需要的元素之后我们就可以释放bcache.lock了.

如果所有的块都是忙的,只能返回busy的信息了.我们不需要考虑同步的问题,我们设计的锁能保证同时只有一个进程访问bcache和buf结构体.同样,非零的refcnt保证了只有一个dev number.

睡眠锁保证了就算有许多个进程要访问这个块,仅仅是睡眠而已,因为有多个进程要访问这个文件是很正常的.这样子也可以保证在只有一个进程同时读写这个cache.

// Look through buffer cache for block on device dev.
// If not found, allocate a buffer.
// In either case, return locked buffer.
static struct buf*
bget(uint dev, uint blockno)
{
  struct buf *b;

  acquire(&bcache.lock);

  // Is the block already cached?
  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;
    }
  }

  // Not cached.
  // Recycle the least recently used (LRU) unused buffer.
  for(b = bcache.head.prev; b != &bcache.head; b = b->prev){
    if(b->refcnt == 0) {
      b->dev = dev;
      b->blockno = blockno;
      b->valid = 0;
      b->refcnt = 1;
      release(&bcache.lock);
      acquiresleep(&b->lock);
      return b;
    }
  }
  panic("bget: no buffers");
}

bread()函数:

  • 内部调用了bget函数,该函数保证了返回的已经获取了buf.lockbuf
  • 如果buf还没有获取有效的数据内容,则需要通过virtio_disk_rw()这个函数接口载入数据并将buf的有效位置为1.virtio_disk_rw()函数可以读取磁盘里面的信息,然后把信息传递给
  • 返回这个buf
// Return a locked buf with the contents of the indicated block.
struct buf*
bread(uint dev, uint blockno)
{
  struct buf *b;

  b = bget(dev, blockno);
  if(!b->valid) {
    virtio_disk_rw(b, 0);
    b->valid = 1;
  }
  return b;
}

bwrite()函数把buf中的数据写回磁盘,要求持有buf.lock

// Write b's contents to disk.  Must be locked.
void
bwrite(struct buf *b)
{
  if(!holdingsleep(&b->lock))
    panic("bwrite");
  virtio_disk_rw(b, 1);
}

brelse()函数:如果调用者完成了对缓冲区的操作,它必须调用brelse来释放它。

  • 首先需要判断是否持有参数buf的锁;
  • 如果持有锁则释放该buf 的锁;这样子其他进程就可以访问这个cache了.所以说综上就是一个进程获取了锁并成功进入之后,执行完brelse就可以让下一个进程接着执行.
  • 获取bcache.lock之后,将buf的引用计数refcnt减1,根据buf的引用计数是否为0来决定是否将buf调整到双链表的表头。
  • 对缓冲区的移动使得列表按照最近使用(释放)进行排序:列表里的第一个缓冲区是最近被使用的,最后一个则是最近最少被使用的。bget里的两个循环利用了这点:在最坏的情况下,扫描一个已经存在的缓冲区必须处理整个列表,当引用处于良好的位置的时候,先检查最近使用的缓冲区将减少扫描时间。通过反向扫描(跟随prev指针),对要重新使用的缓冲区的扫描查找到了最少使用的缓冲区。
// Release a locked buffer.
// Move to the head of the most-recently-used list.
void
brelse(struct buf *b)
{
  if(!holdingsleep(&b->lock))
    panic("brelse");

  releasesleep(&b->lock);

  acquire(&bcache.lock);
  b->refcnt--;
  if (b->refcnt == 0) {
    // no one is waiting for it.
    b->next->prev = b->prev;
    b->prev->next = b->next;
    b->next = bcache.head.next;
    b->prev = &bcache.head;
    bcache.head.next->prev = b;
    bcache.head.next = b;
  }
  
  release(&bcache.lock);
}

bpinbunpin用于调整引用计数refcnt.pin就是+1,unpin就是-1.

void
bpin(struct buf *b) {
  acquire(&bcache.lock);
  b->refcnt++;
  release(&bcache.lock);
}

void
bunpin(struct buf *b) {
  acquire(&bcache.lock);
  b->refcnt--;
  release(&bcache.lock);
}

 

3. Log层

前言

在文件系统的设计里最有趣的问题之一是故障恢复。许多文件系统的操作包含了多次写磁盘的操作,在一串写操作之后的崩溃使得磁盘上的文件系统处于不一致的状态。

xv6系统调用不直接写入硬盘上文件系统的数据结构。相反,它把一个描述放在磁盘上,这个描述是它在一个log里所期望的所有磁盘写操作。一旦系统调用日志记录了所有的写操作,它往磁盘上写入一个特殊的commit记录用来表示那个日志包含了一个完整的操作。那时系统调用才会把所有的写操作写入到磁盘文件系统里的数据结构中。当那些写操作都完成后,系统调用删除磁盘上的日志。

如果系统崩溃并重启,在运行任何进程之前,文件系统代码按如下描述从崩溃中恢复:如果日志被标记为包含一个完整的操作,则恢复代码把写操作复制到磁盘文件系统。如果日志不是标记为包含完整的操作,恢复代码忽略这个日志。恢复代码最后删除日志完成所有的操作。

超级块结构体定义以及磁盘布局

// Disk layout:
// [ boot block | super block | log | inode blocks |
//                                          free bit map | data blocks]
//
// mkfs computes the super block and builds an initial file system. The
// super block describes the disk layout:
struct superblock {
  uint magic;        // Must be FSMAGIC
  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
};

 

3.1 Log层结构体定义

这个数据结构和磁盘上的log区域一一对应的。磁盘上的log区域由log.start开始的连续log.sizeblock组成。第一个block即为logheader,待写磁盘块的个数记录在logheader.n中,待写磁盘块号记录在block数组中。log.dev表示该log位于哪一个磁盘(xv6实际上只有一个)。log.outstanding记录了目前有多少个进程正在并行地对磁盘进行写。

// 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;
};

3.2 Log层函数的定义

initlog函数:使用超级块中的字段初始化log。

void
initlog(int dev, struct superblock *sb)
{
  if (sizeof(struct logheader) >= BSIZE)
    panic("initlog: too big logheader");

  initlock(&log.lock, "log");
  log.start = sb->logstart;
  log.size = sb->nlog;
  log.dev = dev;
  recover_from_log();
}

recover_from_log函数,根据函数名称应该是根据之前写入磁盘的日志信息恢复磁盘数据的操作

  • 从磁盘读取log header
  • 将提交的日志写入磁盘
  • 清空日志记录
static void
recover_from_log(void)
{
  read_head();
  install_trans(1); // if committed, copy from log to disk
  log.lh.n = 0;
  write_head(); // clear the log
}

从磁盘的读取log header到内存中,位于log所在磁盘块的第一个磁盘块

// Read the log header from disk into the in-memory log header
static void
read_head(void)
{
  struct buf *buf = bread(log.dev, log.start);
  struct logheader *lh = (struct logheader *) (buf->data);
  int i;
  log.lh.n = lh->n;
  for (i = 0; i < log.lh.n; i++) {
    log.lh.block[i] = lh->block[i];
  }
  brelse(buf);
}

recovering的作用是啥?

// Copy committed blocks from log to their home location
static void
install_trans(int recovering)
{
  int tail;

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

begin_op()函数:发起写请求,任何对bcache中的block进行写操作之前都需要调用这个函数。

  • 如果日志处于commit状态,则需要等待;
  • 否则判断本次写操作是否会使得transaction需要写的磁盘块超出LOGSIZE;
  • 如果没有超过则将log.outstanding字段加1;
  • 如果超过则需要等待。
// called at the start of each FS system call.
void
begin_op(void)
{
  acquire(&log.lock);
  while(1){
    if(log.committing){
      sleep(&log, &log.lock);
    } else if(log.lh.n + (log.outstanding+1)*MAXOPBLOCKS > LOGSIZE){
      // this op might exhaust log space; wait for commit.
      sleep(&log, &log.lock);
    } else {
      log.outstanding += 1;
      release(&log.lock);
      break;
    }
  }
}
  • 在结束写请求的时候调用end_op()函数,将log.outstanding字段减1;
  • 如果log.committing字段为1,表面日志处于提交状态,抛出异常;
  • 如果所有的进程都结束了写请求,则将log.committing字段以及do_commit置为1;
  • 如果do_commit为1则调用commit函数,将本轮进程写的结果写回磁盘
// called at the end of each FS system call.
// commits if this was the last outstanding operation.
void
end_op(void)
{
  int do_commit = 0;

  acquire(&log.lock);
  log.outstanding -= 1;
  if(log.committing)
    panic("log.committing");
  if(log.outstanding == 0){
    do_commit = 1;
    log.committing = 1;
  } else {
    // begin_op() may be waiting for log space,
    // and decrementing log.outstanding has decreased
    // the amount of reserved space.
    wakeup(&log);
  }
  release(&log.lock);

  if(do_commit){
    // call commit w/o holding locks, since not allowed
    // to sleep with locks.
    commit();
    acquire(&log.lock);
    log.committing = 0;
    wakeup(&log);
    release(&log.lock);
  }
}

log_write函数用于把块修改写入内存中的log

通常情况下,我们调用bread函数读取一个块,然后对块的内容进行了修改,然后调用brelse释放这个块。问题在于log怎么知道哪些块需要写回呢?得用logheader来记录,所以必须有个函数来写logheader记录块的修改,这个函数就是log_write

  • 如果是第一次修改这个块,那么执行log.lh.n++操作;
  • 当一个块在单个事务中被多次写入时,log_write会发现它,并在日志里为那个块分配相同的位置。这个优化被称为合并(absorption);
void
log_write(struct buf *b)
{
  int i;

  acquire(&log.lock);
  if (log.lh.n >= LOGSIZE || log.lh.n >= log.size - 1)
    panic("too big a transaction");
  if (log.outstanding < 1)
    panic("log_write outside of trans");

  for (i = 0; i < log.lh.n; i++) {
    if (log.lh.block[i] == b->blockno)   // log absorption
      break;
  }
  log.lh.block[i] = b->blockno;
  if (i == log.lh.n) {  // Add new block to log?
    bpin(b);
    log.lh.n++;
  }
  release(&log.lock);
}

commit函数可以分为几个阶段:

  • 把内存中需要修改的block写回磁盘的log区域(write_log)
  • 把内存中logheader写回磁盘的log区域头(write_head)
  • 把log区域的磁盘块写回到磁盘的相应位置(install_trans)
  • 把磁盘log区域头标记需要写回的block数目的位置清零log.lh.n = 0 & write_head
static void
commit()
{
  if (log.lh.n > 0) {
    write_log();     // Write modified blocks from cache to log
    write_head();    // Write header to disk -- the real commit
    install_trans(0); // Now install writes to home locations
    log.lh.n = 0;
    write_head();    // Erase the transaction from the log
  }
}
// Copy modified blocks from cache to 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); // log block
    struct buf *from = bread(log.dev, log.lh.block[tail]); // cache block
    memmove(to->data, from->data, BSIZE);
    bwrite(to);  // write the log
    brelse(from);
    brelse(to);
  }
}

 

4. inode层

磁盘上的inode被填充在一个被称为inode块的连续磁盘区域上。每个inode都是一样大小,所以给定一个编号n,很容易就找到磁盘上的第n个inode

4.1 两个分配和回收磁盘块的函数

遍历bitmap,分配或者回收block

// Allocate a zeroed disk block.
static uint
balloc(uint dev)
{
  int b, bi, m;
  struct buf *bp;

  bp = 0;
  for(b = 0; b < sb.size; b += BPB){
    bp = bread(dev, BBLOCK(b, sb));
    for(bi = 0; bi < BPB && b + bi < sb.size; bi++){
      m = 1 << (bi % 8);
      if((bp->data[bi/8] & m) == 0){  // Is block free?
        bp->data[bi/8] |= m;  // Mark block in use.
        log_write(bp);
        brelse(bp);
        bzero(dev, b + bi);
        return b + bi;
      }
    }
    brelse(bp);
  }
  panic("balloc: out of blocks");
}

// Free a disk block.
static void
bfree(int dev, uint b)
{
  struct buf *bp;
  int bi, m;

  bp = bread(dev, BBLOCK(b, sb));
  bi = b % BPB;
  m = 1 << (bi % 8);
  if((bp->data[bi/8] & m) == 0)
    panic("freeing free block");
  bp->data[bi/8] &= ~m;
  log_write(bp);
  brelse(bp);
}

4.2 inode层的数据结构定义

磁盘上 i 结点结构定义

磁盘上的inode通过struct dinode来定义。type字段区分了文件、目录、和特殊文件(设备)。如类型值为0则表示磁盘inode是空闲的。字段nlink记录了引用当前inode的目录条目的数量,用以识别这个磁盘inode和它的数据块何时应该被释放。size字段记录了文件内容的字节数。addrs数组记录了保存了文件内容的磁盘块的块号,addrs里的前NDIRECT个块被称为直接块(direct blocks);第NDIRECT+1个块记录了NINDIRECT个块的数据,它被称为间接块(indirect block)。

对数据结构中 majorminor 字段的解释:

在Unix系系统中,一切皆是文件。所有硬盘,键盘,网卡等设备都有文件来代表,对应着/dev/下面的文件。对于应用程序来说,可以像对待普通文件一样打开、关闭、读写这些设备文件。但是,这种文件名比如:/dev/sda/dev/raw/raw1都是用户空间名称,OS Kernel根本不知道这个名称代指什么。在内核空间是通过majorminor device number来区分设备的。

major device number:可以看做是设备驱动程序,被同一设备驱动程序管理的设备有相同的major device number。这个数字实际是Kernel 中device driver table的索引。这个表保存着不同的设备驱动程序。

minor device number:代表被访问的具体设备。也就是说,Kernel根据major device number找到设备驱动程序,然后再从minor device number获得设备位置等属性。

// 下面的宏定义用于type字段,type = 0表示该dinode尚未分配
#define T_DIR     1
#define T_FILE    2
#define T_DEVICE  3
// 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
};

内存中需保存的i结点信息数据结构定义,除了从磁盘读取的inode信息,还定义了一些其他的字段。内核把活动inode的集合保存在内存中,即struct inoderef字段记录了C指针引用内存里inode的次数,当那个计数降为0的时候内核就会从内存中丢弃这个inode。igetiput函数请求和释放到一个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];
};

4.3 inode层函数定义

iget()函数

遍历itable寻找 i 结点是否已经被加载至内存中,如是则将该 i 结点的ref引用计数加1;在遍历的过程中使用empty对空的 i 结点进行保存;如果 i 结点还未被加载至内存则使用空 i 结点对需要获取的 i 结点进行保存。最后返回对应的 i 结点。

struct {
  struct spinlock lock;
  struct inode inode[NINODE];
} itable;
// Find the inode with number inum on device dev
// and return the in-memory copy. Does not lock
// the inode and does not read it from disk.
static struct inode*
iget(uint dev, uint inum)
{
  struct inode *ip, *empty;

  acquire(&itable.lock);

  // Is the inode already in the table?
  empty = 0;
  for(ip = &itable.inode[0]; ip < &itable.inode[NINODE]; ip++){
    if(ip->ref > 0 && ip->dev == dev && ip->inum == inum){
      ip->ref++;
      release(&itable.lock);
      return ip;
    }
    if(empty == 0 && ip->ref == 0)    // Remember empty slot.
      empty = ip;
  }

  // Recycle an inode entry.
  if(empty == 0)
    panic("iget: no inodes");

  ip = empty;
  ip->dev = dev;
  ip->inum = inum;
  ip->ref = 1;
  ip->valid = 0;
  release(&itable.lock);

  return ip;
}

ilock函数用于获取ip所☞的 i 结点的锁,同时如果该 i 结点的内容处于无效状态时,需要从磁盘中读取对应设备和结点号的 i 结点,把相关字段拷贝至内存 i 结点中,将该 i 结点的有效位置为1,保证 i 结点的内容是有效的。

// Inodes per block.
#define IPB           (BSIZE / sizeof(struct dinode))

// Block containing inode i
#define IBLOCK(i, sb)     ((i) / IPB + sb.inodestart)

// Lock the given inode.
// Reads the inode from disk if necessary.
void
ilock(struct inode *ip)
{
  struct buf *bp;
  struct dinode *dip;

  if(ip == 0 || ip->ref < 1)
    panic("ilock");

  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));
    brelse(bp);
    ip->valid = 1;
    if(ip->type == 0)
      panic("ilock: no type");
  }
}

iunlock() 函数:释放ip所☞的 i 结点的锁

// Unlock the given inode.
void
iunlock(struct inode *ip)
{
  if(ip == 0 || !holdingsleep(&ip->lock) || ip->ref < 1)
    panic("iunlock");

  releasesleep(&ip->lock);
}

idup()函数类似于bpiniput()函数类似于brelse函数。

iput函数判断自己是最后一个持有该inode指针、该inode的内容是有效的、该inode的引用链接数为0时,会将该inode进行删除。

// Increment reference count for ip.
// Returns ip to enable ip = idup(ip1) idiom.
struct inode*
idup(struct inode *ip)
{
  acquire(&itable.lock);
  ip->ref++;
  release(&itable.lock);
  return ip;
}
// Drop a reference to an in-memory inode.
// If that was the last reference, the inode table entry can
// be recycled.
// If that was the last reference and the inode has no links
// to it, free the inode (and its content) on disk.
// All calls to iput() must be inside a transaction in
// case it has to free the inode.
void
iput(struct inode *ip)
{
  acquire(&itable.lock);

  if(ip->ref == 1 && ip->valid && ip->nlink == 0){
    // inode has no links and no other references: truncate and free.

    // ip->ref == 1 means no other process can have ip locked,
    // so this acquiresleep() won't block (or deadlock).
    acquiresleep(&ip->lock);

    release(&itable.lock);

    itrunc(ip);
    ip->type = 0;
    iupdate(ip);
    ip->valid = 0;

    releasesleep(&ip->lock);

    acquire(&itable.lock);
  }

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

itrunc()函数先释放直接块,再释放间接块里所列出的那些块,最后再释放间接块自身。

// Truncate(截断) inode (discard contents).
// Caller must hold ip->lock.
void
itrunc(struct inode *ip)
{
  int i, j;
  struct buf *bp;
  uint *a;
  // 遍历前面NDIRECT个直接块,并进行释放块操作
  for(i = 0; i < NDIRECT; i++){
    if(ip->addrs[i]){
      bfree(ip->dev, ip->addrs[i]);
      ip->addrs[i] = 0;
    }
  }

  if(ip->addrs[NDIRECT]){
    bp = bread(ip->dev, ip->addrs[NDIRECT]);
    a = (uint*)bp->data;
    // 遍历后面NINDIRECT个间接块,进行释放操作
    for(j = 0; j < NINDIRECT; j++){
      if(a[j])
        bfree(ip->dev, a[j]);
    }
    brelse(bp);
    bfree(ip->dev, ip->addrs[NDIRECT]);
    ip->addrs[NDIRECT] = 0;
  }

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

bmap()函数用于返回第bn个数据块的硬盘块号,参数ip用于表示inode的指针。如果ip里没有那个块,bmap会给它分配一个。

(注:由于一个块的大小BSIZE是1024字节且NDIRECT是12,所以一个文件可以直接载入的内容为12k字节。由于NINDIRECT是256,所以读取间接块后可以载入的内容是256k字节。)

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]) == 0)
      ip->addrs[NDIRECT] = addr = balloc(ip->dev);
    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");
}

writei()函数和readi()函数

比较简单,首先检查文件偏移和写入/读取字节大小是否合法,合法后对数据进行循环拷贝.写入时,读取块,将源数据拷贝至缓冲区;读出时,读取块,将块数据拷贝至对应的区域。

// Write data to inode.
// Caller must hold ip->lock.
// If user_src==1, then src is a user virtual address;
// otherwise, src is a kernel address.
// Returns the number of bytes successfully written.
// If the return value is less than the requested n,
// there was an error of some kind.
int
writei(struct inode *ip, int user_src, uint64 src, uint off, uint n)
{
  uint tot, m;
  struct buf *bp;

  if(off > ip->size || off + n < off)
    return -1;
  if(off + n > MAXFILE*BSIZE)
    return -1;

  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);
    if(either_copyin(bp->data + (off % BSIZE), user_src, src, m) == -1) {
      brelse(bp);
      break;
    }
    log_write(bp);
    brelse(bp);
  }

  if(off > ip->size)
    ip->size = off;

  // write the i-node back to disk even if the size didn't change
  // because the loop above might have called bmap() and added a new
  // block to ip->addrs[].
  iupdate(ip);

  return tot;
}

int
readi(struct inode *ip, int user_dst, uint64 dst, uint off, uint n)
{
  uint tot, m;
  struct buf *bp;

  if(off > ip->size || off + n < off)
    return 0;
  if(off + n > ip->size)
    n = ip->size - off;

  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);
    if(either_copyout(user_dst, dst, bp->data + (off % BSIZE), m) == -1) {
      brelse(bp);
      tot = -1;
      break;
    }
    brelse(bp);
  }
  return tot;
}

4. Directory层

4.1 directory层结构体定义

inum:该目录项对应的inode号

name:该目录项的名称

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

4.2 directory层函数定义

函数dirloopup()在目录 i 结点所包含的下一层的所有文件中找到名称为name的文件目录项,首先判断inode的type是否为T_DIR (目录) ,如果不是则抛出异常;接着循环读取inode所☞的目录文件,读取每一个目录项,如果找到名字为name的目录项,则查找 该目录项指向的inode并返回该inode。

// Look for a directory entry in a directory.
// If found, set *poff to byte offset of entry.
struct inode*
dirlookup(struct inode *dp, char *name, uint *poff)
{
  uint off, inum;
  struct dirent de;

  if(dp->type != T_DIR)
    panic("dirlookup not DIR");

  for(off = 0; off < dp->size; off += sizeof(de)){
    if(readi(dp, 0, (uint64)&de, off, sizeof(de)) != sizeof(de))
      panic("dirlookup read");
    if(de.inum == 0)
      continue;
    if(namecmp(name, de.name) == 0){
      // entry matches path element
      if(poff)
        *poff = off;
      inum = de.inum;
      return iget(dp->dev, inum);
    }
  }

  return 0;
}

namex()函数

  • namex首先决定路径计算从哪里开始。如果路径是从斜杠开始的,计算从根目录开始;否则,就从当前目录开始;
  • skipelem来依次得到路径里的每个元素;
  • 每次循环都必须在当前inode(ip)查找name
  • 循环首先锁定ip并检查它是否是一个目录,如果不是,查找失败;
  • 如果这个调用是nameiparent并且这是最后一个路径元素,按照nameiparent的定义,循环终止;
  • 最后,使用dirlookup查找路径元素,并通过设置ip = next为下一次循环做好准备。当循环遍历完所有的路径元素退出后,namex返回ip
// 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;
}
// Paths

// 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;
}

dirlink()函数

在目录 i 结点dp中添加一个新的名字为name的目录项

// Write a new directory entry (name, inum) into the directory dp.
int
dirlink(struct inode *dp, char *name, uint inum)
{
  int off;
  struct dirent de;
  struct inode *ip;

  // Check that name is not present.
  if((ip = dirlookup(dp, name, 0)) != 0){
    iput(ip);
    return -1;
  }

  // Look for an empty dirent.
  for(off = 0; off < dp->size; off += sizeof(de)){
    if(readi(dp, 0, (uint64)&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, 0, (uint64)&de, off, sizeof(de)) != sizeof(de))
    panic("dirlink");

  return 0;
}

5. file descriptor层

5.1 file descriptor层的数据结构定义

readablewritable刻画文件的读写权限,off表示文件读写偏移;

ftable管理所有打开的文件

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
};

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

5.2 file descriptor层函数定义

filealloc扫描文件表查找未引用的文件(f->ref == 0)并返回一个新的引用。

// Allocate a file structure.
struct file*
filealloc(void)
{
  struct file *f;

  acquire(&ftable.lock);
  for(f = ftable.file; f < ftable.file + NFILE; f++){
    if(f->ref == 0){
      f->ref = 1;
      release(&ftable.lock);
      return f;
    }
  }
  release(&ftable.lock);
  return 0;
}

filedup递增引用计数。

// Increment ref count for file f.
struct file*
filedup(struct file *f)
{
  acquire(&ftable.lock);
  if(f->ref < 1)
    panic("filedup");
  f->ref++;
  release(&ftable.lock);
  return f;
}

fileclose递减引用计数。当引用计数降为0,释放底层对应的管道或inode。

// Close file f.  (Decrement ref count, close when reaches 0.)
void
fileclose(struct file *f)
{
  struct file ff;

  acquire(&ftable.lock);
  if(f->ref < 1)
    panic("fileclose");
  if(--f->ref > 0){
    release(&ftable.lock);
    return;
  }
  ff = *f;
  f->ref = 0;
  f->type = FD_NONE;
  release(&ftable.lock);

  if(ff.type == FD_PIPE){
    pipeclose(ff.pipe, ff.writable);
  } else if(ff.type == FD_INODE || ff.type == FD_DEVICE){
    begin_op();
    iput(ff.ip);
    end_op();
  }
}

filestat实现了对文件的stat操作(stat操作是文件/文件系统的详细信息显示)。它只允许操作inode,然后调用stati;最后将数据从内核拷贝至用户。

// Get metadata about file f.
// addr is a user virtual address, pointing to a struct stat.
int
filestat(struct file *f, uint64 addr)
{
  struct proc *p = myproc();
  struct stat st;
  
  if(f->type == FD_INODE || f->type == FD_DEVICE){
    ilock(f->ip);
    stati(f->ip, &st);
    iunlock(f->ip);
    if(copyout(p->pagetable, addr, (char *)&st, sizeof(st)) < 0)
      return -1;
    return 0;
  }
  return -1;
}

fileread实现了对文件的read操作。首先检查是否允许readable模式,然后把调用传递给管道或inode的实现。如果文件是一个inode,它使用I/O位移作为读操作的位移,然后增加这个位移。管道没有位移的概念。

// Read from file f.
// addr is a user virtual address.
int
fileread(struct file *f, uint64 addr, int n)
{
  int r = 0;

  if(f->readable == 0)
    return -1;

  if(f->type == FD_PIPE){
    r = piperead(f->pipe, addr, n);
  } else if(f->type == FD_DEVICE){
    if(f->major < 0 || f->major >= NDEV || !devsw[f->major].read)
      return -1;
    r = devsw[f->major].read(1, addr, n);
  } else if(f->type == FD_INODE){
    ilock(f->ip);
    if((r = readi(f->ip, 1, addr, f->off, n)) > 0)
      f->off += r;
    iunlock(f->ip);
  } else {
    panic("fileread");
  }

  return r;
}

filewrite实现了对文件的write操作。首先检查是否允许writeable模式,然后把调用传递给管道或inode的实现。如果文件是一个inode,它使用I/O位移作为写操作的位移,然后增加这个位移。管道没有位移的概念。要记得inode函数需要调用者管理锁定。inode的锁定有一个方便的附加效果,即读写位移是自动更新的,因此同时对一个文件的多个写操作不会覆盖彼此的数据,但这些写操作可能会交错在一起。

// Write to file f.
// addr is a user virtual address.
int
filewrite(struct file *f, uint64 addr, int n)
{
  int r, ret = 0;

  if(f->writable == 0)
    return -1;

  if(f->type == FD_PIPE){
    ret = pipewrite(f->pipe, addr, n);
  } else if(f->type == FD_DEVICE){
    if(f->major < 0 || f->major >= NDEV || !devsw[f->major].write)
      return -1;
    ret = devsw[f->major].write(1, addr, n);
  } else if(f->type == FD_INODE){
    // write a few blocks at a time to avoid exceeding
    // the maximum log transaction size, including
    // i-node, indirect block, allocation blocks,
    // and 2 blocks of slop for non-aligned writes.
    // this really belongs lower down, since writei()
    // might be writing a device like the console.
    int max = ((MAXOPBLOCKS-1-1-2) / 2) * BSIZE;
    int i = 0;
    while(i < n){
      int n1 = n - i;
      if(n1 > max)
        n1 = max;

      begin_op();
      ilock(f->ip);
      if ((r = writei(f->ip, 1, addr + i, f->off, n1)) > 0)
        f->off += r;
      iunlock(f->ip);
      end_op();

      if(r != n1){
        // error from writei
        break;
      }
      i += r;
    }
    ret = (i == n ? n : -1);
  } else {
    panic("filewrite");
  }

  return ret;
}

sys_link从获取它的两个字符串参数oldnew开始。如果old存在且不是目录,递增它的ip->nlink计数。然后调用nameiparent来找到new的父目录和最终的路径元素,并创建一个新的目录条目来指向old的inode。新的上级目录必须存在且和inode在同一设备上:inode号在单独的磁盘上有唯一的意义。如果发生了这样的错误,sys_link必须回退且递减ip->nlink

// Create the path new as a link to the same inode as old.
uint64
sys_link(void)
{
  char name[DIRSIZ], new[MAXPATH], old[MAXPATH];
  struct inode *dp, *ip;

  if(argstr(0, old, MAXPATH) < 0 || argstr(1, new, MAXPATH) < 0)
    return -1;

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

  ilock(ip);
  if(ip->type == T_DIR){
    iunlockput(ip);
    end_op();
    return -1;
  }

  ip->nlink++;
  iupdate(ip);
  iunlock(ip);

  if((dp = nameiparent(new, name)) == 0)
    goto bad;
  ilock(dp);
  if(dp->dev != ip->dev || dirlink(dp, name, ip->inum) < 0){
    iunlockput(dp);
    goto bad;
  }
  iunlockput(dp);
  iput(ip);

  end_op();

  return 0;

bad:
  ilock(ip);
  ip->nlink--;
  iupdate(ip);
  iunlockput(ip);
  end_op();
  return -1;
}

……还有很多与文件相关的系统调用,不一一列举了

6. 读写操作和设备文件

file.cfile.h文件中记录了xv6的驱动

// map major device number to device functions.
struct devsw {
  int (*read)(int, uint64, int);
  int (*write)(int, uint64, int);
};

struct devsw devsw[NDEV];	// 其中NDEV = 10,xv6最多支持10种不同的驱动
#define CONSOLE 1	// xv6只实现了Console的读写

console.c种,console的读写绑定到devsw上了

void
consoleinit(void)
{
  initlock(&cons.lock, "cons");

  uartinit();

  // connect read and write system calls
  // to consoleread and consolewrite.
  devsw[CONSOLE].read = consoleread;
  devsw[CONSOLE].write = consolewrite;
}

init.c中的一段代码

  • 创建设备文件console;
  • CONSOLE(major号)绑定到console文件上;
  • 打开console。
  if(open("console", O_RDWR) < 0){
    mknod("console", CONSOLE, 0);
    open("console", O_RDWR);
  }
  dup(0);  // stdout
  dup(0);  // stderr

一个设备文件总是绑定了一个驱动函数,打开设备文件后的读写,就相当于调用相应的驱动程序

 


0 条评论

发表评论

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

隐藏