前言

• 本篇是關於 MIT 6.S081-2020-Lab9(File System) 的實現；
• 如果內容上發現有什麼問題請不要吝嗇您的鍵盤。

準備工作

Logging Layer

在文件系統中的 Crash 可能是由文件系統操作過程中發生了電力故障（突然斷電）或內核 Panic 引起的。因為文件系統存儲在持久層，Crash 之後不希望重啓後我們的持久性數據處於不一致或不正確的狀態（例如 inode 指向的 data blocks 是空的；或者在 bitmap block 分配了 data blocks 但沒有 inode 去引用它們），因此這裏就需要 Crash Recovry。

磁盤寫操作是我們所關心的，而我們不關心磁盤讀操作，因為那對我們的持久性數據的正確性沒有任何危害。所以之後提及文件系統操作，我們都會默認是磁盤寫操作。提及 xv6 代碼，我們都會默認那是相應概念的實現，實現與抽象概念有出入是件很正常的事，所以請前後對照着看。

xv6 從數據庫相關技術中借鑑了事務(Transaction) 和日誌(Log) 這兩個重要的抽象概念。

事務

事務的一個重要性質就是原子性，我們可以將一組磁盤寫操作執行順序封裝抽象成一個事務，來保證它要麼全部執行，要麼全部不執行。並且我們假設，位於磁盤的文件系統中，單個的 block 或 sector 的寫是一個原子性操作。

在實現中，我在這裏為事務的概念給出另一側面的解釋：給定一系列磁盤寫操作，在其中插入 n 個 commit 操作（不要在始末插入），就可以將一系列文件系統操作劃分為 n 個事務，分別是事務 1~ 事務 n。而事務 n 之後發生的所有文件系統操作，我們不稱它為一個事務，因為沒有以 commit 操作收尾。由此可以看到，定界事務的唯一標誌，就是看有沒有 commit 操作。

在 xv6 中，我們約定一個文件系統調用就是一個事務，具體地，在系統調用後為事務的開始，在系統調用返回前是事務的結束。這一點我們可以在 kernel/sysfile.c 中的 sys_open() 這個系統調用中清晰得看到相應的代碼，begin_op() 代表事務的開始，它會做一些事務相關的初始化工作以及一些邊界檢查；end_op() 代表事務的結束，由它來執行 commit 操作。更多的源碼部分解析放到下一個部分中，這一部分更多是概念的介紹。

值得一提的是，為了支持文件系統操作的併發性，xv6 允許多個系統調用封裝成一個事務，這在 begin_op() 和 end_op() 的邊界檢查中都有體現。

日誌

Crash recovery 的原理就是通過先前在日誌中記錄的事務，將其重新執行一遍來達成。所以日誌是一個基於事務的持久層技術。不難想象，所有的文件系統操作必須先在日誌中留有相應的記錄，然後才能真正地寫到文件系統中去，不然一旦出現 crash 這些操作都沒有記錄就無法恢復了。是的，我們會將磁盤劃分成兩個部分，一個部分就是我們熟知的文件系統，另一個部分則是日誌，這一點對理解日誌實現很重要。

日誌在磁盤中的結構很簡單，它包括了一個 header block，和緊隨其後的 logged blocks 列表。logged blocks 是文件系統中的 blocks 的拷貝。為什麼要拷貝這些 blocks，因為日誌需要保存事務開始到結束期間執行的一系列的文件系統操作所涉及的文件系統的 blocks，從而 crash recovery。header block 包含日誌的一些元信息，包括 logged blocks 的數量，和每個 logged block 所對應的文件系統 block 的塊號。header block 和 logged blocks 中的信息（加粗的這三個）組合起來就是完備地表示一個完整的事務（日誌裏最多存儲一個事務的信息），內核可以只依靠這些信息就能把 crash 發生之前的事務完整地再執行一次，從而實現 crash recovery。

Log Design

這一部分會打開源碼來看看日誌是如何存儲事務的，由於內存中會有磁盤數據結構相應的拷貝，所以為了區分開到底是內存中的數據結構還是磁盤中的數據結構，在有必要時，我會在其前加上定語，如磁盤中的日誌、內存中的日誌。

xv6 的日誌系統是依次靠以下三個事務相關操作來運行的（以下函數均在 kernel/log.c 文件下有定義）：

1. start transaction

   • begin_op(void)

2. record operation

   • log_write(struct buf b*)

3. end transaction（end_op() 調用 commit()）

   1. commit transaction

      • write_log(void) 和 write_head(void)

   2. install transaction

      • install_trans(int recovering)

   3. clean transaction

      • write_head(void)

接下來將以文件系統調用 sys_open() 為例，來逐一介紹這些函數具體是怎麼工作的。

/* kernel/sysfile.c */

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

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

  begin_op();

  ...        // 此處省略一系列文件系統操作

  end_op();

  return fd;
}

Start Transaction

在 sys_open() 執行文件系統操作之前，它先調用了 begin_op() 來邏輯地表明一個事務的開始：

/* kernel/log.c */

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

內存的日誌是個全局共享的數據結構，因此在嘗試訪問 log 的字段前先獲取 log.lock。while 循環內部有三個分支，前兩個分支是邊界檢查，第三個分支是執行事務的初始化：

1. 檢查 log.committing

   • 要看懂這個分支的意義就要搭配 end_op() 一起看。我們不希望在內核線程 A 在執行 commit 操作期間，內核線程 B 還在往內存的日誌寫文件操作記錄。因為這時如果內核線程 A 在執行完 commit 操作之後緊接着發生了 crash，倒黴的將是內核線程 B，因為它只 commit 了一部分的文件操作，這會造成數據的不一致性。內核線程 B 所要做的（也是 begin_op() 所做的）就是在正式開始文件操作之前，先看看當前有沒有其它線程在執行 commit 操作。如果有就進入 SLEEP 狀態（commit 涉及很多的低速的磁盤操作，所以於其自旋一直佔用 CPU 不妨，不如直接 SLEEP 走掉），否則就將執行下一項分支檢查。

2. 查看新來的系統調用所產生的一系列事務性操作是否可能會溢出日誌的大小限制

   • xv6 中的日誌是有固定大小限制的，log.lh.n 代表當前已被佔用的 logged blocks 的數量，MAXOPBLOCKS 代表一個系統調用能夠記錄的最大文件系統塊數，LOGSIZE 就是日誌的大小最大值。如果當前操作有可能會使日誌大小溢出，那就 SLEEP 等待別的內核線程 commit 後清空日誌記錄。這裏有個問題就是當我係統調用 write() 一個超大的文件時，日誌永遠都不會滿足這樣的請求，因為事務遠遠超過了日誌大小上限。針對這種情況，在 kernel/file.c 下的 filewrite() 可以看到，xv6 會將一個大的 filewrite() 操作（系統調用 sys_write() 是由 filewrite() 實現的）分解成若干個小的 writei() 操作，以至於每個 writei() 操作都不會超出日誌大小上限。可能會有疑問，這不會破壞系統調用的原子性嗎？但這裏是個例外，對於系統調用 sys_write() 來説，遵循的是盡力而為策略，並不要求把所有操作都原子性地寫到磁盤中。

3. 事務初始化

   • 簡單的自增 log.outstanding，代表當前併發的文件系統操作線程多了一個。

Record Operation

當事務開始後，來看看文件系統操作是如何被記錄到內存中的日誌中的：

/* kernel/log.c */

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

原本的沒有日誌支撐的文件系統操作處的 bwrite()，現在都會被替換為 log_write()。可以看到 log_write() 做的工作非常少，主要有兩個：

1. 在內存中的日誌的 header block 中記錄下這個文件系統塊的塊號

   • 主要是做一個標記，這時候還沒有把內容拷貝到 logged block 中

2. 把這個文件系統塊 pin 在 buffer cache 中，防止被 evict 走

   • 這一步是為了之後 commit 操作服務的，因為日誌需要遵循 write ahead rule，即在 commit 之前，你需要保證所有的文件系統操作都在內存中的日誌中，不允許落盤到文件系統。否則中途發生 crash，事務將會被截斷，失去了原子性。

第 24 行的 Log absorbtion 意味着當該文件系統塊已經被記錄過了，就直接中斷這次 log_write()，因為這個文件系統操作的結果已經反映在 buffer cache 的 pin 塊中了，記錄是可以覆蓋的。

有了 1 2 步之後，我們就可以通過 header block 中的信息（logged blocks 數量以及從老到新的 logged blocks 塊號）和 bread(uint dev, uint blockno) 操作，來依次地把事務內的文件系統操作在內存中完整地復現出來了。

End Transaction

/* kernel/log.c */

// 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.committing 才會置 1，並在最後執行 commit 操作。所以一開始如果 log.committing == 1 顯然是個錯誤，因此直接 panic。否則如果當前有其它線程在執行時，我們就喚醒之前在 begin_op() 因為日誌大小不足而等待的線程。

最後在 commit 操作執行完之後，再將 log.committing 清空，喚醒之前在 begin_op() 因其它線程正在事務提交而等待的線程。我們接下來看看 commit() 是如何將 log_write() 的輸出落盤的，這裏是重點。

Commit Transaction

/* kernel/log.c */

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

commit() 內部依次四個函數調用，其中前兩個調用是完成 Commit Transaction 部分，install_trans(0) 是完成 Install Transaction 部分，最後的 write_head() 是完成 Clear Transaction 部分。

/* kernel/log.c */


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

// Write in-memory log header to disk.
// This is the true point at which the
// current transaction commits.
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);
}

1. write_log()

   • log.start 是在 mkfs/fs.c 中的 main() 中去設置 super block 的 logstart 字段來指定的，代表磁盤中的日誌的 header block 的塊號，這裏是 2。所以 write_log() 所作的，就是把之前在 log_write() 在 buffer cache 被 pin 的 block 的內容拷貝到磁盤中的日誌的 logged block 中。如果在這個時候發生 crash 了，事務將不會被恢復。

2. write_head()

   • 這裏就是將內存中的日誌的 header block 的內容拷貝到磁盤中的日誌的 header block 中。如果在這個時候發生 crash 了，事務可以被恢復。因為在上面 Logging Layer 部分有提及過，事務提交的標誌，就是磁盤中的日誌的 header block 的 count of logged block > 0。

Install Transaction

/* kernel/log.c */

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

install_trans() 所做的工作就是將磁盤中的日誌的 logged blocks 內容拷貝到對應的文件系統塊中。個人拙見，將讀取 logged blocks 的語句和拷貝內容的這兩條語句，寫在 if(recovering != 0) 的條件下效率可能會更高些，因為那些文件系統塊一直都 pin 在 buffer cache 中，直接 bwrite(dbuf) 即可。

install 時內核會遍歷所有的 logged blocks，假設 install 遍歷到一半時發生了 crash 後，重啓恢復時會不會出現錯誤。答案是並不會，因為恢復時的 install 操作會把先前的落盤記錄覆蓋掉。因此我們稱 install transaction 操作是一種冪等操作，冪等操作執行一次和執行多次的效果是一樣的，因此你可以執行任意多次 install transaction 操作。

Clear Transaction

執行 log.lh.n = 0; 語句代表清空內存中的日誌的 logged blocks。我們需要調用 write_head() 把在內存中的更新落盤到磁盤中的日誌的 header block 上。

至此一個完整的事務通過日誌落盤的流程就結束了，其中 Record Operation 和 End Transaction 是最重要的兩個步驟。

Inode Layer

Block Allocator

討論 Inode Layer 時，有個繞不開的話題就是 Block 的分配和釋放，因為文件系統系統的所有信息都放在 blocks 上面，而用一個 block 之前你總要分配它，用完後還要釋放它，否則將會出現錯誤。

磁盤中的 bitmap（位視圖）用若干個 Blocks 記錄了磁盤中所有 block 的使用情況，它首先建立了位的位置和塊號的映射關係，然後對應 bitmap 位置 1 時表示該塊號的塊已被分配，反之為空閒。當磁盤容量很大時，需要多個物理上連續的 bitmap blocks 來表示。這些連續的 bitmap blocks 將組成給一個更大的 bitmap。

/* kernel/fs.c */

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

BSIZE 是一個 block 的大小，在 xv6 中是 1024。sb.size 是 super block 中記錄的文件系統的大小，單位為 BSIZE。BPB 是 bits per block 的意思，宏展開式為 (BSIZE * 8)。也就是説一個 bitmap block 能夠管理的範圍也就 1 BPB 個 blocks。BBLOCK(b, sb) 的宏展開式為 (b/BPB + sb.bitmapstart)，意為給定一個塊號和 super block 結構體變量，就能返回在這個 super block 的描述下，目標塊號 b 是受塊號為幾的 bitmap block 管理的。

balloc() 的第一層循環就是遍歷所有的 bitmap block；第二層循環就是遍歷當前 bitmap block 的所有位來找出一個空閒塊。bfree() 就是給定塊號來在 bitmap 釋放它。

Dinode & Inode

inode 的一些基本概念我們已經在上一篇（指源碼窺探（5））介紹過了。這裏再深入討論一下，xv6 具體是怎麼管理和操作 inode 的。為了方便地操作 inode 對象，xv6 分別分別定義了位於磁盤的 inode（在 kernel/fs.h 下的 struct dinode）和位於內存的 inode（在 kernel/file.h 下的 struct 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];
};

struct dinode 是原原本本存儲在磁盤上的 inode 的佈局，計算 dinode 的各字段大小和正好是 64字節，可以將 dinode 直接寫到 inode block 指定位置中。而 struct inode 則是完全繼承了 dinode 的字段設置，這樣方便在磁盤讀或寫的時候，dinode 和 inode 相互之間方便來回轉化。我們主要需要關注 dinode.nlink 字段和 inode.ref 字段的語義。dinode.nlink 的數值代表在磁盤中，有多少個目錄去引用了這個 inode。當這個字段值為 0 時，內核線程會從磁盤上銷燬這個 inode，釋放它所關聯的 data blocks。inode.ref 的數值代表在內存中，有多少個 C 指針去引用了這個 inode（像 C++ 裏智能指針的實現），這裏的 C 指針引用可能來自 fd(file descriptor), cwd(current working directory)。當這裏的引用數為 0 時，內核線程就會把這個 inode 寫回到磁盤中。所以可以看到，這兩個字段的值都跟 Inode Layer 無關，而是跟 Inode Layer 的上層有關（Directory Layer, Pathname Layer 和 File Descriptor Layer）， 所以更多的情況放到介紹上層的時候再説了。

iget()

關於 inode 的操作有很多，它們都在 kennel/fs.c 文件中有定義。除了 bmap()，這些函數名基本都以字符 i 開頭或結尾。由於數量眾多，這裏就挑幾個重要來介紹：iget(), ilock(), iput(), itrunc(), iupdate(),。瞭解完這些幾個重要的函數之後，像其它的函數，如 ialloc(), readi(), writei(), bmap(), iunlock() 基本看一遍源碼實現留個印象就行。

/* kernel/fs.c */

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

// 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(&icache.lock);

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

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

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

  return ip;
}

簡單解釋一個問題：我們在做上一個實驗的時候碰到過類似的問題，內核線程它不像用户線程一樣能以字節為單位分配動態內存，所以我們當時用了一個全局的固定大小的靜態數組解決分配哈希表項的問題。這裏也是差不多的道理，雖然變量名叫 icache，但它不像 buffer cache 一樣是為了緩存 inode 從而解決訪問速度差異而開的 inode 數組，這裏只是單純地沒有動態分配 inode 的方法而選擇靜態分配而已。inode cache 和 buffer cache 都在內存，因此用緩存解決訪問速度差異的角度來解釋是不合理的。

iget() 在這裏做的工作很少，它先是去看 icache 是否有已有對應 inode，有的話返回它，沒有的話簡單初始化一下在返回。

ilock()

iget() 並沒有與磁盤做任何的交互，而是負責內存這一側的 inode 初始化工作。因此要想獲得一個真實可用的 inode，我們需要搭配另一個函數來將內存 inode 與 磁盤 inode 對應起來，它就是 ilock()：

/* kernel/fs.c */


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

在磁盤中，inode 是按照 inode number 由小到大的順序依次在 inode blocks 連續存儲的，每個 inode block 可以最多放 16（IPB = BSZIE / sizeof(struct dinode)）個 inode。因此給定 inode blocks 的起始塊號和一個目標 inode number，就可以準確定位這個 inode number 對應的 inode 在磁盤塊中的位置，這也是 IBLOCK 宏所鎖的事情。

在內核中，任意一處要想使用某個 inode 之前，都需要通過 ilock() 獲取這個 inode 的鎖，使用完後再通過 iunlock() 釋放這個 inode 鎖。

/* kernel/fs.c */

// Copy a modified in-memory inode to disk.
// Must be called after every change to an ip->xxx field
// that lives on disk, since i-node cache is write-through.
// Caller must hold ip->lock.
void
iupdate(struct inode *ip)
{
  struct buf *bp;
  struct dinode *dip;

  bp = bread(ip->dev, IBLOCK(ip->inum, sb));
  dip = (struct dinode*)bp->data + ip->inum%IPB;
  dip->type = ip->type;
  dip->major = ip->major;
  dip->minor = ip->minor;
  dip->nlink = ip->nlink;
  dip->size = ip->size;
  memmove(dip->addrs, ip->addrs, sizeof(ip->addrs));
  log_write(bp);
  brelse(bp);
}

當我們想把對內存 inode 的更新落盤時，調用 iupdate() 即可。

itrunc()

/* kernel/fs.c */

// Truncate inode (discard contents).
// Caller must hold ip->lock.
void
itrunc(struct inode *ip)
{
  int i, j;
  struct buf *bp;
  uint *a;

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

itrunc() 是從磁盤上釋放這個 inode 所關聯的所有的 data blocks。我們在上一篇介紹過，inode 的 data blocks 是一級索引分配和二級索引分配策略混合的策略，第 0~NDIRECT-1 個 data blocks 是直接 data blocks，第 NDIRECT 個 data block 是索引 data block，這個索引 data block 裏依次存有所有二級 data blocks 的 block number，就像下面這個圖演示的一樣：

因此 itrunc() 的工作流程是，先釋放 direct data blocks，再釋放 indirect data block，最後將 inode 的 size 置 0 後調用 iupdate() 將對以上 indoe 的更新落盤。

iput()

/* kernel/fs.c */

// Drop a reference to an in-memory inode.
// If that was the last reference, the inode cache 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(&icache.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(&icache.lock);

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

    releasesleep(&ip->lock);

    acquire(&icache.lock);
  }

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

iput() 會減少一個內存 inode 的引用數。當引用數減為 0，且 dinode 的鏈接數也為 0 時，iput() 就會調用 itrunc() 和 iupdate() 來釋放回收這個 inode。

其它操作

下面的幾個操作都是調用上面的基本操作來完成實現的。

1. bmap()

   • bmap() 和 itrunc() 可以説是一對互逆操作。bmap() 的作用是給定一個 inode，就返回第 bn 個 data block 的塊號。

2. iunlock()

   • 釋放先前在 ilock() 獲取的互斥鎖，當前線程放棄對內存 inode 的引用。

3. ialloc()

   • 遍歷磁盤的 inode，找到一個空閒的 inode 之後（type == 0 代表空閒），將其 type 字段設置為指定值，最後調用 iget() 在內存中分配這個 inode。

4. readi()

   • 給定一個 inode、是否為物理地址(user_dst)、內存地址(dst)、文件偏移(off) 以及讀入的字節數 n ，readi() 將從 inode 關聯的 data 的 user_dst+off 開始拷貝 n 個字節到 dst 處。

5. writei()

   • 與 readi() 是互逆操作，基本流程相似。

Directory Layer

我們説 inode 通過設置它的 type 字段的值，使它即可以指向一個文件，也可以指向一個目錄。當指向一個文件時，這個 inode 關聯的 data blocks 中存放的都是這個文件的內容；當指向一個文件時，這個 inode 關聯的 data blocks 中存放的都是目錄項(struct dirent）：

/* kernel/fs.h */

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

dirent.inum 指向的是下一個 inode，沒人知道這下一個 inode 的類型到底還是一個目錄或是文件。也就是説，目錄裏面可以包含很多個文件和很多個目錄，這就像平時用 Windows 資源管理器隨便打開某個目錄查看這個目錄下的目錄項一樣：

/* kernel/fs.c */

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

dirlookup() 的作用就是給定一個 inode 和帶查詢的目錄項名稱，返回目標目錄項指向的 inode（即可能是文件也可能是目錄）。返回的 inode 即沒有上鎖，也沒和 dinode 關聯，所以可以看作是僅返回一個目標 inode number。

dirlookup() 的工作就是很簡單地遍歷讀取給定 inode 的所有目錄項，找到名字完全匹配的目錄項，最後獲取並返回目標目錄項指向的 inode。另外這個函數還有個副作用就是要設置參數 *poff 的值為目標目錄項在給定目錄的字節偏移數（假設目標目錄項是該目錄下的第 i 個目錄項，那麼 *poff = i * sizeof(struct dirent)）。

dirlink() 的作用是給定目錄 inode，在該目錄下創建一個新的目錄項（給定目錄項名稱和目錄項指向的 inode 的 inode number）。實現很簡單所以介紹略過。

Pathname Layer

Pathname Layer 提供的是路徑解析的服務，主要有兩種需求，例如當解析路徑 /a/b/c：

1. struct inode* namei(char *path)

   • namei() 會將給定 path 解析到底，因此返回 c 的 inode，這裏的 c 的類型既可以是文件可以是目錄。

2. struct inode* nameiparent(char *path, char *name)

   • nameiparent() 會將給定 path 解析到最後一個的前一個名稱，因此返回 b 的 inode，注意到這裏的 b 的類型一定是個目錄。

由於 namei() 和 nameiparent() 做的工作很相近，它們都是通過 namex() 來實現的：

/* kernel/fs.c */

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

需要注意的是，我在第 23 被運算符優先級困擾了很久，最好是改成 if(nameiparent && (*path == '\0')){ 這樣的寫法，否則容易造成誤解。

skipelem() 的作用是提取 path 的一個名字前綴作為名詞，剩餘的部分作為返回值。它內部都是字符串操作，不詳細介紹，但源碼中這個函數的註釋給出使用例：

// 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() 在返回結果前，會依次增加再減少 ip 的引用值。這是為了內核線程 A 在操作 ip 時，內核線程 B 想要刪除這個 ip。假設不去增加 ip 的引用值，又不巧 ip 是最後一級 inode（意味着 ip->nlink == 0），那麼就會去釋放掉這個 ip，這對內核線程 A 來説是個錯誤。

值得一提的是，鎖的粒度降低為了一個 inode，這得以多個線程可以併發地進行路徑檢索，前提是它們不要恰好解析同一個 inode。並且在 namex() 解析的時候，同一時刻只能獲取一個路徑上 inode 的鎖，因為如果遇到了 . 這樣的名字，會重複獲取兩次互斥鎖而造成死鎖（xv6 只能檢測重複獲取兩次自旋鎖造成的死鎖（檢測到後直接 panic），而這裏互斥鎖死鎖會直接停止運行）。

File Descriptor Layer

File Descriptor Layer 將內核的大部分資源，如 inode 和 pipe，都抽象成了文件(struct file)，並提供了一個統一的接口，如打開(filealloc() 和 filedup())、讀(fileread())、寫(filewrite())、關閉(fileclose())。

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

之所能將這些都抽象為了文件並且提供統一的操作，是因為它們都跟 I/O 相關，因此 struct file 還必須記錄 I/O offset（事實上 pipe 沒有 I/O offset 這種概念），以及其它一些屬性，如可讀可寫。

每打開一個資源都會創建這個資源的文件實例，不同文件實例都是相互獨立的，就算是同一個資源的實例，這些實例間也能有不同的 I/O offset。

內核中有一個全局的 filetable 用來保存和管理所有進程打開和關閉過的文件：

/* kernel/file.h */

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

每個進程也都有自己的局部的 filetable，用來保存和管理該進程打開過的所有文件：

/* kernel/proc.h */

// Per-process state
struct proc {
  ...
  struct file *ofile[NOFILE];  // Open files
  struct inode *cwd;           // Current directory
  ...
};

被打開的文件的文件描述符，指的就是當前進程 myproc()->ofile 裏的對應文件的索引。

實驗部分

Large files

把跟宏 NINDIRECT 有關的地方擴展一下就好了。

首先是修改下宏定義：

/* kernel/fs.h */

#define NDIRECT 11
#define NINDIRECT (BSIZE / sizeof(uint))
#define MAXFILE (NDIRECT + NINDIRECT + NINDIRECT*NINDIRECT)

既然改變了 NDIRECT 的大小，又由於實驗指導書上説不必修改 inode 關聯的 data blocks 的個數，需要再把 struct inode 和 struct dinode 這兩處 addrs 數組的大小改為 NDIRECT+2 即可。

最後 bmap() 和 itrunc() 的修改邏輯依葫蘆畫瓢描就完事了。

/* kernel/fs.c */

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

  bn -= NINDIRECT;

  if (bn < NINDIRECT*NINDIRECT) {
    if ((addr = ip->addrs[NDIRECT+1]) == 0)
      ip->addrs[NDIRECT+1] = addr = balloc(ip->dev);
    bp = bread(ip->dev, addr);
    a = (uint*)bp->data;
    if ((addr = a[bn/NINDIRECT]) == 0) {
      a[bn/NINDIRECT] = addr = balloc(ip->dev);
      log_write(bp);
    }
    brelse(bp);

    bn %= NINDIRECT;
    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");
}


void
itrunc(struct inode *ip)
{
  int i, j;
  struct buf *bp;
  uint *a;

  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;
    for(j = 0; j < NINDIRECT; j++){
      if(a[j]) {
        bfree(ip->dev, a[j]);
        a[j] = 0;
      }
    }
    brelse(bp);
    bfree(ip->dev, ip->addrs[NDIRECT]);
    ip->addrs[NDIRECT] = 0;
  }

  if (ip->addrs[NDIRECT+1]) {
    bp = bread(ip->dev, ip->addrs[NDIRECT+1]);
    a = (uint*)bp->data;
    for (j = 0; j < NINDIRECT; ++j) {
      if (a[j]) {
        int k;
        struct buf *_bp;
        uint *_a;

        _bp = bread(ip->dev, a[j]);
        _a = (uint*)_bp->data;
        for (k = 0; k < NINDIRECT; ++k) {
          if (_a[k]) {
            bfree(ip->dev, _a[k]);
            _a[k] = 0;
          }
        }
        brelse(_bp);
        bfree(ip->dev, a[j]);
        a[j] = 0;
      }
    }
    brelse(bp);
    bfree(ip->dev, ip->addrs[NDIRECT+1]);
    ip->addrs[NDIRECT+1] = 0;
  }


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

Symbolic links

符號鏈接類似於 Windows 裏的快捷方式，本質上就是個存放目標文件的絕對路徑名稱的文件：

int symlink(char *target, char *path) 中，target 就是這裏的“目標”，path 就是這裏的“起始位置”。在 user/usys.pl, user/user.h, kernel/syscall.c 和 Makefile 中添加必要的 symlink() 的系統調用代碼後，依照實驗指導書修改必要的宏以及實現即可：

/* kernel/sysfile.c */


uint64
sys_open(void)
{
  ...
  if(omode & O_CREATE){
  ...
  } else {
  ...
  }

  if (!(omode & O_NOFOLLOW) && ip->type == T_SYMLINK) {
    char path[MAXPATH];
    int depth = 0;

    while (ip->type == T_SYMLINK) {
      if (++depth == 10) {
        iunlockput(ip);
        end_op();
        return -1;
      }

      readi(ip, 0, (uint64)path, 0, MAXPATH);
      iunlockput(ip);

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

      ilock(ip);
    }
  }
  ...
}


uint64
sys_symlink(void)
{
  char path[MAXPATH], target[MAXPATH];

  if(argstr(0, target, MAXPATH) < 0 || argstr(1, path, MAXPATH) < 0){
    return -1;
  }
  
  begin_op();

  struct inode *ip;

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

  writei(ip, 0, (uint64)target, 0, MAXPATH);

  iunlockput(ip);
  end_op();

  return 0;
}

比較容易踩坑的是 writei() 和 readi() 的參數順序，注意不要填錯了。

後記

刑滿一年釋放回家了（指在學校不間斷待了將近一年，但學校寒假不讓留人迫不得已回家），不用關心學校裏那一堆破事（指 OOAD 實踐和 IoT 課設論文），開始有點時間做點自己能做的事情了。

這個實驗總的來説，做之前要看的東西理解清晰，實驗部分就可以做得很快，是一個理解準備工作部分更重要的實驗。

回頭有時間再把文件系統調用（kernel/sysfile.c 下面那一堆操作）的一些內容看看。