Chapter 6: File system

四資工三
B10415028
張博雅

傳統的磁碟與檔案系統之應用中，一個分割槽就是只能夠被格式化成為一個檔案系統，所以我們可以說一個 filesystem 就是一個 partition。
但是由於新技術的利用，目前我們則稱呼一個可被掛載的資料為一個檔案系統而不是一個分割槽。

運作原理

檔案系統通常會將這兩部份的資料(較新的作業系統的檔案資料除了檔案實際內容外， 通常含有非常多的屬性)分別存放在不同的區塊：

權限與屬性放置到 inode 中
實際資料則放置到 data block 區塊中

程式流程

xv6把磁盤劃分為幾個區塊
如圖6-2所示。
第0塊存有bootloader(文件系統不使用)。
第1塊叫做超級塊；它包含了文件系統的元信息（如文件系統的總塊數，數據塊塊數，i節點數，以及日誌的塊數）。
從第2塊開始存放i節點，每一塊能夠存放多個i節點。(inodes)
接下來的塊存放空閒塊位圖。
剩下的大部分塊是數據塊，它們保存了文件和目錄的內容。
在磁盤的最後是日誌塊，它們是會話層的一部分，將在後面詳述。(log)

資料結構（註明哪一個檔案內的functions、程式裡面所使用到哪些變數及結構）

塊緩衝層(boot)

XV6將硬盤中的每個分區編號為各種塊，每塊512字節，磁盤讀寫總是以塊為單位，XV6使用結構BUF來代表磁盤塊數據在內核中的表示：

struct buf {
  int flags;
  uint dev;
  uint blockno;
  struct sleeplock lock;
  uint refcnt;
  struct buf *prev; // LRU cache list
  struct buf *next;
  struct buf *qnext; // disk queue
  uchar data[BSIZE];
};

xv6在kernel中分配了靜態數組然後通過頭buf來構成雙向鍊錶，雙向鍊錶維護著塊的使用頻率，按照最近使用的順序來組織結構能讓塊讀取更加效率。
塊緩衝層提供有binit，bget ，bread，BWRITE，brelse接口。

BWRITE將塊緩衝結構寫入磁盤

void
bwrite(struct buf *b)
{
  if(!holdingsleep(&b->lock))
    panic("bwrite");
  b->flags |= B_DIRTY;
  iderw(b);
}

brelse則減少塊的引用次數，並移動塊的位置實現LRU

// Release a locked buffer.
// Move to the head of the MRU 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);
}
//PAGEBREAK!
// Blank page.

日誌層(log)

XV6在硬盤中的日誌有一個初始快和數據塊，初始快包括一個數組，數組的值為對應數據塊的內容應該寫入文件系統中的哪一塊，初始快還有當前有效數據塊的計數。在內存中同樣要一樣的結構來存儲數據。

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

我節點(inode & dinode)

我節點分為內核我節點（inode的）和磁盤上的我節點（dinode），XV6使我節點表來緩存我節點

struct dinode {
  short type;           // File type
  short major;          // Major device number (T_DEV only)
  short minor;          // Minor device number (T_DEV only)
  short nlink;          // Number of links to inode in file system
  uint size;            // Size of file (bytes)
  uint addrs[NDIRECT+1];   // Data block addresses
};
// in-memory copy of an inode
struct inode {
  uint dev;           // Device number
  uint inum;          // Inode number
  int ref;            // Reference count
  struct sleeplock lock;
  int flags;          // I_VALID

  short type;         // copy of disk inode
  short major;
  short minor;
  short nlink;
  uint size;
  uint addrs[NDIRECT+1];
};

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

iinit

void
iinit(int dev)
{
  int i = 0;

  initlock(&icache.lock, "icache");
  for(i = 0; i < NINODE; i++) {
    initsleeplock(&icache.inode[i].lock, "inode");  //負責初始化inode
  }

  readsb(dev, &sb);
  cprintf("sb: size %d nblocks %d ninodes %d nlog %d logstart %d\
 inodestart %d bmap start %d\n", sb.size, sb.nblocks,
          sb.ninodes, sb.nlog, sb.logstart, sb.inodestart,
          sb.bmapstart);
}

ialloc

struct inode*
ialloc(uint dev, short type)
{
  int inum;
  struct buf *bp;
  struct dinode *dip;

  for(inum = 1; inum < sb.ninodes; inum++){
    bp = bread(dev, IBLOCK(inum, sb));
    dip = (struct dinode*)bp->data + inum%IPB;
    if(dip->type == 0){  // a free inode
      memset(dip, 0, sizeof(*dip));
      dip->type = type;
      log_write(bp);   // mark it allocated on the disk
      brelse(bp);
      return iget(dev, inum);//在磁盤中找到空閒我節點並返回內核我節點
    }
    brelse(bp);
  }
  panic("ialloc: no inodes");
}