MIT 6.S081 教材第八章内容 -- 文件系统 -- 01

// kernel/param.h
#define MAXOPBLOCKS  10  // max # of blocks any FS op writes
#define NBUF         (MAXOPBLOCKS*3)  // size of disk block cache

// kernel/bio.c
struct {
  // 保护buffer pool同一时刻只有一个内核线程访问
  struct spinlock lock;
  // buf数组 --- 大小为30
  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.
  // 已分配buf串接而成的链表,按照最近最常使用进行排序
  struct buf head;
} bcache;

// kernel/bio.c

void
binit(void)
{
  struct buf *b;
  // 初始化buffer pool的锁资源
  initlock(&bcache.lock, "bcache");

  // Create linked list of buffers
  // 创建buf双向链表
  bcache.head.prev = &bcache.head;
  bcache.head.next = &bcache.head;
  // 组装buf链表,头插法
  for(b = bcache.buf; b < bcache.buf+NBUF; b++){
    b->next = bcache.head.next;
    b->prev = &bcache.head;
    // 初始化单个buf的锁资源
    initsleeplock(&b->lock, "buffer");
    bcache.head.next->prev = b;
    bcache.head.next = b;
  }
}

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

// kernel/buf.h
struct buf {
  int valid;   // has data been read from disk? 数据是否已经从磁盘读取到buf cache中
  int disk;    // does disk "own" buf?
  uint dev;
  uint blockno;  // block编号
  struct sleeplock lock; 
  uint refcnt;  // 引用计数
  struct buf *prev; // LRU cache list 
  struct buf *next;
  uchar data[BSIZE];  // 数据缓冲区,大小为一个Block
};

// Return a locked buf with the contents of the indicated block.
struct buf*
bread(uint dev, uint blockno)
{
  struct buf *b;
  // 根据设备号和块号获取对应的buf
  b = bget(dev, blockno);
  // 如果当前buf还没有从磁盘读取,那么就进行读取
  if(!b->valid) {
    // 从磁盘读取block块内容到buf
    virtio_disk_rw(b, 0);
    b->valid = 1;
  }
  return b;
}

// 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;
  //锁住Buffer Cache,确保同一时刻只有一个内核线程能够操作
  acquire(&bcache.lock);

  // Is the block already cached?
  // 当前block是否已经被缓存在了buffer cache中
  for(b = bcache.head.next; b != &bcache.head; b = b->next){
    // 设备号和磁盘号是否一致
    if(b->dev == dev && b->blockno == blockno){
      // 引用计数+1
      b->refcnt++;
      // 释放buf cache锁,获取buf锁--如果获取失败,就在当前锁上睡眠
      // 使用buf期间,对应内核线程需要持有锁
      release(&bcache.lock);
      acquiresleep(&b->lock);
      return b;
    }
  }

  // Not cached.
  // Recycle the least recently used (LRU) unused buffer.
  // buf cache没有换成,那么使用LRU算法进行淘汰
  for(b = bcache.head.prev; b != &bcache.head; b = b->prev){
    // 只淘汰引用计数为0的buf
    if(b->refcnt == 0) {
      b->dev = dev;
      b->blockno = blockno;
      b->valid = 0;
      b->refcnt = 1;
      release(&bcache.lock);
      acquiresleep(&b->lock);
      return b;
    }
  }
  //buf cache中全部都是
  panic("bget: no buffers");
}

// Write b's contents to disk.  Must be locked.
void
bwrite(struct buf *b)
{
  // 首先获取到对于buf的lock
  if(!holdingsleep(&b->lock))
    panic("bwrite");
  // 将block写入磁盘
  virtio_disk_rw(b, 1);
}

// Release a locked buffer.
// Move to the head of the most-recently-used list.
void
brelse(struct buf *b)
{
  // 首先拿到buf对应的lock
  if(!holdingsleep(&b->lock))
    panic("brelse");
  // 释放buf对应的lock
  releasesleep(&b->lock);
  // 获取buf cache的锁 
  acquire(&bcache.lock);
  // 引用计数减一,判断是否完全被释放了
  b->refcnt--;
  if (b->refcnt == 0) {
    // no one is waiting for it.
    // 将当前buf移动到LRU列表开头
    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);
}

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

 //1. 开启日志事务
 begin_op();
 //2. 不断记录日志数据--暂时保存再内存中
 ...
 bp = bread(...);
 bp->data[...] = ...;
 log_write(bp);
 ...
 //3.提交本次日志事务
 end_op();

// kernel/param.h 
#define MAXOPBLOCKS  10  // max # of blocks any FS op writes  
#define LOGSIZE      (MAXOPBLOCKS*3)  // max data blocks in on-disk log 

//  kernel/log.c
//  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;

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

// Caller has modified b->data and is done with the buffer.
// Record the block number and pin in the cache by increasing refcnt.
// commit()/write_log() will do the disk write.
//
// log_write() replaces bwrite(); a typical use is:
//   bp = bread(...)
//   modify bp->data[]
//   log_write(bp)
//   brelse(bp)
void
log_write(struct buf *b)
{
  int i;
  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");

  acquire(&log.lock);
  for (i = 0; i < log.lh.n; i++) {
    if (log.lh.block[i] == b->blockno)   // log absorbtion
      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);
}

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

// Copy modified blocks from cache to log.
// 将缓存中脏的block copy一份到log block中
static void
write_log(void)
{
  int tail;
  // 遍历所有待写入磁盘块的log block
  for (tail = 0; tail < log.lh.n; tail++) {
    // 从磁盘中读取中对应的log block
    struct buf *to = bread(log.dev, log.start+tail+1); // log block
    // 从buf cache中获取脏block
    struct buf *from = bread(log.dev, log.lh.block[tail]); // cache block
    // 将数据从from copy到to
    memmove(to->data, from->data, BSIZE);
    // 将log block to写入磁盘
    bwrite(to);  // write the log
    // 递减引用计数
    brelse(from);
    brelse(to);
  }
}

// Write in-memory log header to disk.
// This is the true point at which the
// current transaction commits.
static void
write_head(void)
{
  // log block区域第一个log block是log header block
  struct buf *buf = bread(log.dev, log.start);
  struct logheader *hb = (struct logheader *) (buf->data);
  int i;
  // 将内存中保持的log header信息写入磁盘保存
  hb->n = log.lh.n;
  for (i = 0; i < log.lh.n; i++) {
    hb->block[i] = log.lh.block[i];
  }
  bwrite(buf);
  brelse(buf);
}

// Copy committed blocks from log to their home location
static void
install_trans(int recovering)
{
  int tail;
  // 将log.lh.block数组中记录的所有脏块刷到磁盘上的log block区域保存
  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);
  }
}

// A fork child's very first scheduling by scheduler()
// will swtch to forkret.
void
forkret(void)
{
  static int first = 1;

  // Still holding p->lock from scheduler.
  release(&myproc()->lock);
  //第一个用户进程运行之前的引导期间由`fsinit`调用的
  if (first) {
    // File system initialization must be run in the context of a
    // regular process (e.g., because it calls sleep), and thus cannot
    // be run from main().
    first = 0;
    fsinit(ROOTDEV);
  }

  usertrapret();
}

// Init fs
void
fsinit(int dev) {
  // 读取super block
  readsb(dev, &sb);
  if(sb.magic != FSMAGIC)
    panic("invalid file system");
  // 初始化日志系统  
  initlog(dev, &sb);
}

// there should be one superblock per disk device, but we run with
// only one device
// 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
};


// Read the super block.
static void
readsb(int dev, struct superblock *sb)
{
  struct buf *bp;
  // 读取第一个block 
  bp = bread(dev, 1);
  memmove(sb, bp->data, sizeof(*sb));
  brelse(bp);
}

void
initlog(int dev, struct superblock *sb)
{
  if (sizeof(struct logheader) >= BSIZE)
    panic("initlog: too big logheader");
  
  initlock(&log.lock, "log");
  // 从sb中获取log系统相关信息
  log.start = sb->logstart;
  log.size = sb->nlog;
  log.dev = dev;
  // 判断是否需要进行奔溃恢复过程
  recover_from_log();
}

static void
recover_from_log(void)
{
  //读取log header block到log.lh结构体中
  read_head();
  // 尝试重放已经提交的日志事务，但是对应的脏块还没有刷新到磁盘上的任务
  install_trans(1); // if committed, copy from log to disk
  log.lh.n = 0;
  // 将磁盘上log header区域中的n设置为0
  write_head(); // clear the 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);
}

 begin_op(); 
 ilock(f->ip); 
 r = writei(f->ip, ...); 
 iunlock(f->ip); 
 end_op();

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

  bp = 0;
  // 遍历所有bitmap block -- bitmap block数量随着磁盘大小而浮动
  for(b = 0; b < sb.size; b += BPB){
    // 从磁盘读取出当前bitmap block
    bp = bread(dev, BBLOCK(b, sb));
    // 遍历bitmap block中每一位
    for(bi = 0; bi < BPB && 
    // 可能当前bitmap block前面100位就足以表示完所有磁盘块了
    b + bi < sb.size; bi++){
      m = 1 << (bi % 8);
      // 位图当前位是否为0,为0表示位图处于空闲状态
      if((bp->data[bi/8] & m) == 0){  // Is block free?
        // 标记位图当前位位1,正在使用
        bp->data[bi/8] |= m;  // Mark block in use.
        // 当前位图块修改了,所以记录到log block中
        log_write(bp);
        // 引用计数减一,只保留log block中的引用计数
        brelse(bp);
        // 将当前空闲block清空为0
        bzero(dev, b + bi);
        // 返回当前空闲block的块号
        return b + bi;
      }
    }
    brelse(bp);
  }
  panic("balloc: out of blocks");
}

// Zero a block.
// 将当前空闲块从磁盘读取出来,然后清空为0,然后写入log block
static void
bzero(int dev, int bno)
{
  struct buf *bp;

  bp = bread(dev, bno);
  memset(bp->data, 0, BSIZE);
  log_write(bp);
  brelse(bp);
}

// Free a disk block.
static void
bfree(int dev, uint b)
{
  struct buf *bp;
  int bi, m;
  // 找到要free的block在哪个bitmap blocks上
  bp = bread(dev, BBLOCK(b, sb));
  bi = b % BPB;
  m = 1 << (bi % 8);
  // 设置bitmap block对应要释放的block bit位为0
  if((bp->data[bi/8] & m) == 0)
    panic("freeing free block");  
  bp->data[bi/8] &= ~m;
  // 将修改的bitmap block记录到log block中等待落盘
  log_write(bp);
  brelse(bp);
}