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

大綱

• kernel/fs.c/bzero
• kernel/fs.c/balloc
• kernel/fs.c/bfree

在使用這幾個 function 的時候，需要確保會在 begin_op ~ end_op 之間，因為這幾個 function 都會使用到 log_write。

kernel/fs.c/bzero

// Zero a block.
static void
bzero(int dev, int bno)
{

• dev : device number，代表目前我們是使用哪一個 physical disk 或是 partition。
• bno : block number

  struct buf *bp;

  bp = bread(dev, bno);

把一個 block 從 disk hardware 讀取出來，並放到 buffer cache layer 的 struct-buf 快取起來。

  memset(bp->data, 0, BSIZE);

把這個 cache buffer 的一個 block size 的 data 清成 0。

  log_write(bp);

pin 住這個 struct-buf，避免這個 struct-buf 被回收，並等待 commit 階段才會把這個 block 寫進 VirtIO Block Device。

  brelse(bp);
}

釋放掉這個 block，也會釋放掉該 struct-buf 的 sleeplock，讓其他 process 也有機會操作這個 struct-buf。

kernel/fs.c/balloc

{ kernel/fs.h/BPB }

// Bitmap bits per block
#define BPB           (BSIZE*8)

在 xv6-riscv 作業系統裡面，每一個 Block 的 size 為 BSIZE bytes，每一個 bytes 有 8 bits，所以 BPB 才會是 BSIZE * 8 bits。

{ kernel/fs.h/BBLOCK }

// Block of free map containing bit for block b
#define BBLOCK(b, sb) ((b)/BPB + sb.bmapstart)

• b
  • 是 bitmap 裡面的 bit 的 index
  • 同時也是 block 在整個 file system 內的 index
  • 在 bitmap 裡的第 i 個 bit，代表了整個 file system 的第 i 個 block
• sb
  • super block
• sb.bmapstart
  • bitmap 的起始 block 編號

• BBLOCK : 找出某個 bitmap 裡的 bit 所屬的 block ，在 file system 中的 block 編號。

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

這個 function 會在 bitmap 裡面尋找有空閒的 block，找到後會在 bitmap 裡面相對應的 bit 標示為 1，表示這個 block 目前正在被使用。

  bp = 0;
  for(b = 0; b < sb.size; b += BPB){

這裡的 b 指的是 bitmap 裡面的第幾個 bit，每一個 bit 都會代表一個 block 是否 free / used。換言之，b 也可以代表 block 在 filesystem 內的 index。

所以 b 的最大值就是整個 file system 的大小 ( 單位為 block )。
例如說這個 filesystem 支援 16 blocks 的話，就需要有 16 個 bit 來表示每一個 block 的狀態。

    bp = bread(dev, BBLOCK(b, sb));

• BBLOCK 會找出 bitmap 裡的 b bit 會在哪一個 block 裡面。
• 把這個 block 載入到 bp 這個 buffer cache layer 的 struct-buf

    for(bi = 0; bi < BPB && b + bi < sb.size; bi++){

• 每一個 block 裡面會有 BPB 個 bits ( BSIZE * 8 )
• 遍尋每一個在這個 bitmap block 裡面的每一個 bit

      m = 1 << (bi % 8);

• m 代表 bi 在一個 bytes 裡面的 offset
• m >= 0 && m <= 7

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

假如找到了有空閒的 block，就在 bitmap 相對應的 bit 設為 1。

note :
這邊在要一個 block 的時候，需要遍尋整個 bitmap，或許把閒置的 block 的 index 變成一個 queue，或許會是比較好的選擇，或許可以把 O(N) 降到 O(1)。

kernel/fs.c/bfree

// Free a disk block.
static void
bfree(int dev, uint b)
{

b 為想要釋放出來的 block 編號，同時也是在 bitmap 裡面的位置。

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

把一個 block 釋放出來，並會在 bitmap 裡面，相對應的 bit 標示為 1。