fs.c static uint balloc(uint dev) - 野良プログラマーのCS日記

fs.c
https://github.com/mit-pdos/xv6-public/blob/master/fs.c#L56

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

balloc関数は、ハードディスク上のビットマップ領域にあるbitの値を0から1へ変更します(ビットマップ領域上のbitに、あるセクタが使用中であることを記録します)

引数 dev
操作対象となるビットマップ領域が所属しているハードディスクドライブを指定します。
引数devが1の値の時は、マスタードライブを指定しています。
引数devが0の値の時は、スレイブドライブを指定しています。

戻り値 b + bi
ビットマップに使用中として記録されたセクタのセクタ番号です(ビットマップ領域において、使用中として記録されたセクタに対応するbit番号b+biです)。

ハードディスク上にあるビットマップ領域を先頭セクタから順番に読み込む
- 1セクタにおけるビットマップ領域において各bitの値を調べる
  - 1バイトにおけるビットマップ領域においてbitに設定する値を用意する
  - 1バイトにおけるビットマップ領域において使用されていないbitが見つかった場合
- 1セクタ分のビットマップ領域において使用されていないbitが見つからなかった場合
ハードディスク上にあるビットマップ領域のbit全てが使用中であることを示していた場合

ハードディスク上にあるビットマップ領域を先頭セクタから順番に読み込む

for(b = 0; b < sb.size; b += BPB){
    bp = bread(dev, BBLOCK(b, sb));

bread関数を呼び出して、ハードディスク上にあるビットマップ領域から1セクタを読み込みます(あるいは、ハードディスク上にあるビットマップ領域の1セクタに対応しているバッファを取得します)。
読み込み対象となるセクタは、セクタ番号bに対応するビットマップ領域上のbitが含まれるセクタです。
セクタ番号bに対応するビットマップ領域上のbitが含まれるセクタを読み込むために、第二引数にはBBLOCKマクロを設定します。BBLOCKマクロは、セクタ番号bに対応するビットマップ領域上のbitが含まれるセクタのセクタ番号を算出するマクロです。
各ループにおいてセクタ番号b(に対応するbit番号)の値は、0、4096、8192、、、とBPBの値だけインクリメントするので(セクタ番号bに対応するbitは、読み込み対象となるセクタにおいて常に最下位bitとなるので)、for文内におけるbread関数は、ビットマップ領域上の先頭セクタから1セクタずつ順番に読み込む処理を行うことになります。

1セクタにおけるビットマップ領域において各bitの値を調べる

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

1セクタ分のビットマップ領域において各bitの値を調べ、使用されていないbit(セクタ番号b + biのセクタが未使用状態であることを示しているbit)を探します。
biは、1セクタ分のビットマップにおけるbit番号(ビットマップ領域から1セクタを取り出した範囲内におけるbit番号。0〜4095のいずれかの値をとる)を表しています。

1バイトにおけるビットマップ領域においてbitに設定する値を用意する

m = 1 << (bi % 8);

1セクタ分のビットマップにおけるbit番号bi(セクタ番号b + biのセクタの使用状態を表しているbit番号)を、1バイト分のビットマップにおけるbit番号bi % 8(ビットマップ領域から1セクタを取り出し、その1セクタから1バイトを取り出した範囲内におけるbit番号。0〜7のいずれかの値をとる)に変換します。
そして、1バイト分のビットマップにおけるbit番号の値を1にした8bit値である 1 << (bi % 8) をmに保存します。

1バイトにおけるビットマップ領域において使用されていないbitが見つかった場合

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

bi/8を配列bp->dataにおけるインデックスとすることで、1セクタ分のビットマップにおけるbit番号biが含まれる配列の要素(1バイト分のビットマップ)を取得できます。
bp->data[bi/8]の値をmでマスク処理することにより、1バイト分のビットマップにおけるbit番号bi/8(セクタbの使用状態を表しているbit番号)の値を取り出します。
(bp->data[bi/8] & m) == 0 が真となる場合→1バイト分のビットマップにおけるbit番号bi/8(セクタbの使用状態を表しているbit番号)の値が0の場合→ビットマップ領域においてセクタbが未使用状態として記録されているbitがみつかった場合は、if文内に入ります。

bp->data[bi/8] |= m;
data[bi/8]の8bit値の内、セクタ番号bに対応するbit番号の値のみを1にします(ビットマップ領域においてセクタbを使用状態として記録します)。

log_write(bp);
log_write関数を呼び出して、バッファbpに対応しているブロック(セクタ)を、ロギングにおけるトランザクションの管理対象として登録します。

brelse(bp);
brelse関数を呼び出して、バッファbpに関わるスリープロックを解放し、他のプロセスがこのバッファを利用できるようにします。

bzero(dev, b + bi);
bzero関数を呼び出して、セクタ番号b + biのセクタを初期化します。

return b + bi;
戻り値として、
1セクタ分のビットマップにおけるbit番号bi(ビットマップ領域から1セクタを取り出した範囲内におけるbit番号。0〜4095のいずれかの値をとる)を、ビットマップ領域全体におけるbit番号b+biに変換してから、戻り値としてリターンします。

1セクタ分のビットマップ領域において使用されていないbitが見つからなかった場合

brelse(bp);

セクタ内に使用されていないbit(セクタが未使用状態であることを示しているbit)がなかった場合は、そのセクタに対応しているバッファbpに関わるスリープロックを解放し、他のプロセスがこのバッファを利用できるようにします。

ハードディスク上にあるビットマップ領域のbit全てが使用中であることを示していた場合

panic("balloc: out of blocks");

ハードディスク上にあるビットマップ領域のbit全てが使用中だった場合は(ファイルシステムで使用できるセクタが上限に達していた場合は)、panic関数を呼び出してメッセージを出力します。