系列文章 : [6.1810] 跟著 MIT 6.1810 學習基礎作業系統觀念

大綱

• kernel/bio.c/struct bcache
• kernel/bio.c/binit
• kernel/bio.c/bget
• kernel/bio.c/bread
• kernel/bio.c/bwrite
• kernel/bio.c/brelse
• kernel/bio.c/bpin, bunpin

kernel/buf.h/struct 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];
};

• valid : 這個 struct-buf 裡面，是否已經有 disk 內的資料了 ?
  • 註 : 在這裡，我們使用 VirtIO block device 作為 disk。
• disk
  • 1 : 代表 VirtIO Block Device 還在處理跟這個 struct-buf 有關的請求
  • 0 : 代表 VirtIO Block Device 目前沒有在處理跟這個 struct-buf 有關的請求
• dev : device number，代表目前我們是使用哪一個 physical disk 或是 partition。xv6-riscv 的 root disk 的 device number 為 ROOTDEV (1)。
• blockno : 這個 struct-buf 所代表的 block number，每一個 block number 代表 BSIZE ( default is 1024 ) bytes 的資料。
• struct sleeplock lock : sleeplock，假如要不到鎖的時候，會陷入睡眠。
• refcnt : reference count，有多少 process 正在使用該 struct-buf
• struct buf *prev : doubly-linked list
• struct buf *next : doubly-linked list
• uchar data[BSIZE] : 該 struct-buf 所代表的，一個 block 的資料。BSIZE 預設為 1024 bytes。

kernel/bio.c/struct bcache

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;

• struct spinlock lock : 用以保護 bcache 的狀態。
• NBUF : 定義在 param.h，代表 struct buf 的數量。
• struct buf buf[NBUF] : struct buf 陣列，保留給 bcache 使用
• struct buf head : struct buf 本身是一個 doubly-linked list，而 struct buf head 是一個 dummy 節點，用以管理這個 doubly-linked list，以及追蹤 Most Recently Used ( MRU ) / Least Recently Used ( LRU )。
  • 這個 dummy 節點的 next 是 MRU ( 最近用到的 struct buf )
  • 這個 dummy 節點的 prev 是 LRU ( 最久沒用到的 struct buf )

kernel/bio.c/binit

void
binit(void)
{

在 kernel 開機的時候，會被呼叫一次 (只有 cpuid 為 0 的 cpu 可以呼叫)。
會初始化 buffer cache layer。

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

這個 spinlock 只准許一個 CPU 去讀取 / 修改 bcache 的資訊。

  // Create linked list of buffers
  bcache.head.prev = &bcache.head;
  bcache.head.next = &bcache.head;

初始化這個 doubly-linked list，讓 dummy 的 head 節點的 prev, next 指向自己。

  for(b = bcache.buf; b < bcache.buf+NBUF; b++){

遍尋 bcache.buf 這個 pool 裡面的每一個 struct buf。

    b->next = bcache.head.next;
    b->prev = &bcache.head;
    initsleeplock(&b->lock, "buffer");
    bcache.head.next->prev = b;
    bcache.head.next = b;
  }
}

• initsleeplock : 初始化一個 sleeplock。
  • spinlock : 假如想等待一個 spinlock，spinlock 會進入一個無窮迴圈 ( spin )，直到拿到 spinlock。
  • sleeplock : 假如想等待一個 sleeplock，會呼叫 sleep 進入睡眠。
• 把每一個在 bcache.buf 這個陣列裡面的 struct buf 插入這個 doubly linked list。

kernel/bio.c/bget

// 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)
{

• bget 嘗試找到一個符合 blockno 以及 dev 的 struct buf。
• 假如沒有找到的話，會嘗試 allocate 一個 struct buf
• 假如成功拿到 struct buf，則會 return locked struct buf ( 已經用 acquiresleep 上了鎖的 struct buf )
• 假如都沒有成功，則會發出 panic。

  acquire(&bcache.lock);

因為這裡會在 bcache.head 的 doubly-linked list 進行搜尋，也有可能對 bcache 裡面的資料進行修改，所以需要先拿到 bcache.lock 這個 spinlock。

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

這邊會從 MRU ( most recently used ) 的 struct buf 來開始尋找有沒有符合 dev 以及 blockno 的 cache。假如有找到的話就 :

• b->refcnt++ : 新增 reference count，代表多一個 process 正在使用這個 buffer。
• release(&bcache.lock) : release global cache lock，因為我們找到相對應的 buffer 了，準備 return。
• acquiresleep(&b->lock) : 要求這個 struct buf 的 sleeplock，假如其他 process 目前正在使用這個 struct buf ( reading / writing )，這個 process 就要進入睡眠，直到可以拿到這個 sleeplock 為止。
• return 已經用 acquiresleep 上了鎖的 locked struct-buf。

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

這邊會從 bcache.head.prev，也就是 LRU ( least recently used ) 的地方開始遍尋 struct buf。假如找到沒人使用的 ( b->refcnt == 0 ) struct buf，就 :

• 把這個 struct buf 初始化，並給它新的 dev, blockno, 並將 b->valid 設為 0 ( 代表這個 struct buf 還沒有包含 disk hardware 內的資料 )
• 釋放 bcache.lock
• 嘗試拿取該 struct buf 的 sleeplock
• 回傳 locked struct-buf

假如沒有找到任何空閒的 struct buf ( 每一個 b->refcnt 都大於 0 )，則發出 panic。

kernel/bio.c/bread

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

• 呼叫 bget，嘗試拿取對應到 dev, blockno 的 struct-buf
• 假如 b->valid == 0，表示該 buffer 裡面沒有 disk hardware 裡面的資料，於是透過 virtio_disk_rw 去對 VirtIO Block Device 發出請求，去讀取 VirtIO Block Device 內的資料。讀取到資料後，就可以將 b->valid = 1 ( 表示該 struct-buf 內有 disk 的資料了! )
  • 因為這時候我們正拿著該 struct-buf 的 sleeplock，所以其他想要這個 buf 的 process 都會跑去睡覺 ( sleep )。
• 回傳擁有 disk 內資料的，locked struct-buf

kernel/bio.c/bwrite

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

把 stuct-buf 裡面的資料 flush 進去 disk hardware 裡面。

• 確保 caller 目前正拿著該 struct-buf 的 sleeplock，假如沒有的話，就直接 panic
• 呼叫 virtio_disk_rw，把這個 struct-buf 的資料寫進 disk 裡面

kernel/bio.c/brelse

// Release a locked buffer.
// Move to the head of the most-recently-used list.
void
brelse(struct buf *b)
{

當一個 process 已經不需要這個 struct-buf 的時候，就可以把這個 struct-buf 釋放掉。

  if(!holdingsleep(&b->lock))
    panic("brelse");

確認目前的 process 擁有這個 struct-buf 的 sleeplock。

  releasesleep(&b->lock);

釋放掉這個 struct-buf 的 sleeplock。
這同時會喚醒因為這個 struct-buf 而陷入睡眠的 process ( e.g. 在 bget function，有些 process 會因為 acquiresleep(&b->lock) 而陷入沉睡 )。

  acquire(&bcache.lock);
  b->refcnt--;

Q: 或許這邊也可以在 struct-buf 裡面加一個 spinlock，而不是用 bcache.lock

因為希望只有一個 process 可以修改 struct-buf 的 refcnt ( reference count )，所以先嘗試拿取 bcache.lock。

接著把 b->refcnt--，代表這個 process 不繼續使用這個 struct-buf 了。

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

假如 refcnt 降到 0，表示沒有其他 process 在使用這個 struct-buf 了。

• 這時候我們可以把 struct-buf 從 doubly-linked-list 拿出來
• 把這個 struct-buf 重新放回 doubly-linked-list 放到 bcache.head.next 的地方。

因為我們把最近使用到的 struct-buf ( Most Recently Used, MRU ) 放在 bcache.head.next 的地方，這樣子 bcache.head.prev 自然而然就會是 LRU ( Least Recently Used )。

在 bget function 才會決定要不要把這個 struct-buf free 掉 ( buf->valid = 0 )。

  release(&bcache.lock);
}

處理完了，把 bcache.lock 釋放掉。

kernel/bio.c/bpin, bunpin

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

因要只希望一個 process 可以修改 b->refcnt，所以去要 bcache.lock 這個 spinlock。
Q: 為什麼這裡要用 bcache.lock，而不是在 struct buf 裡面加一個 spinlock 呢 ?

當某個 process 沒有擁有該 struct-buf 的 sleeplock，卻又不希望這個 struct-buf 被 bget 回收掉的時候 ( 希望這個 struct-buf 可以保留在 memory 裡面 )，就可以使用 bpin。

bpin 這個 function 可以不去要 struct-buf 的 sleeplock，且讓 reference count + 1。bunpin 則是相反，直接把 reference count - 1。

為什麼要這樣做呢 ? 可能在 Logging Layer 可以學習到了。