xv6におけるfilesystemのLayer(下層編)

はじめに

xv6におけるfilesystemの構造についてまとめたい。xv6ではext2とかではなく、もう少し簡素な独自filesystemを採用している1。

今回は、filesystemのデータ構造及び、下図のlayerの下三層つまり、"disk layer", "buffer cache layer", "Logging layer"を説明したい。

f:id:knknkn11626:20190712161422p:plain
Reference[1] ch.6より

Reference

Layer

"Logging Layer"は"Buffer Cache Layer"と"Disk Layer"のあとに説明する。

Buffer Cache layer(diskとmemoryのインターフェース)

まずは、diskとmemoryのそもそもの話から。

diskは本棚、memoryは机に例えられるが、実際に作業する場合は、本棚(disk)の中にある本(sector)を取り出し、机(memory)の上で読むだろう。

xv6 OSでも似たようなことをやっている：

  1. diskからデータ転送を行うbread or bwrite関数を開始
  2. diskのどの位置のデータを取りたいかを指定する
  3. コマンド(read or write)を指定する(実際にはいろいろコマンドの種類がある)
  4. 実際にdiskからデータを取り、memory内の((struct buf*)buf)->dataにこのデータを格納する：
    • readの場合: insl(0x1f0, buf->data, BSIZE/4); ideintr内
    • writeの場合: outsl(0x1f0, buf->data, BSIZE/4); idestart内

この処理を経て、CPU(本棚の例で言う人間に当たる)がmemory内のデータ(b->data)を用いることができる。struct bufのことをbuffer cacheという。 中身は以下の通り：

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

// bio.c
struct {
  struct spinlock lock;
  struct buf buf[NBUF];

  // Linked list of all buffers, through prev/next.
  // head.next is most recently used.
  struct buf head;
} bcache;

struct bufの中身は複雑だが、uchar data[BSIZE];(生データ)とuint blockno;(disk内のデータの場所)の情報が重要。

buffer cache については、このbufferを滞留させずに、できるだけすぐに別のところで使いたいので、 buf->dataの内容を別の構造体に移す。例えば、readsb関数はsuper blockの内容を取得する関数なのだが、diskからsuper blockの内容をbuf->dataに読み取った後、すぐにsuper blockの構造体にmoveしている：

// fs.c
// Read the super block.
void
readsb(int dev, struct superblock *sb)
{
  struct buf *bp;

  bp = bread(dev, 1);
  memmove(sb, bp->data, sizeof(*sb));
  brelse(bp); // decrement refcount of buffer and do free if necessary
}

Note) bcache自体はin-memoryにあることに注意すること。bcacheのbuf->dataにはdisk(から読み取った/に書き取るべき)生データが格納されている。作業するとき(CPUがinstructionを実行するとき)はdisk上(本棚の場所で)ではなく、すべて机の上(memory上)で行うことに留意しよう。

disk layer

こっちはdiskからmemoryへの転送方法を扱うlayer。

diskのデータ転送方法はいろいろあるが、xv6では最も初期の方法2であるPIO modeを用いている。これはCPUの処理能力(x86のinやoutのinstruction)を用いたデータ転送の方法である。(他に、他のやつ(DMA controllerなど)に任せて、CPUはデータ転送の開始と終了をinterruptとして受け取るような転送の方法もあり、こっちのほうが転送速度速いがinterrupt処理が複雑になる)

diskのread/writeはbread/bwriteが担っている。実は、diskのwriteに関してはlogging layer(下から3つめのlayer; log_write関数)が絡んでくるため、結構複雑なのだが、どちらにしろ、diskに書き込む直接の関数はbwriteのみなので、本節ではbwriteの解説に終始する。log_write関数については、logging layerの節で説明したい。

bread

bread関数は以下のようになっている：

struct buf*
bread(uint dev, uint blockno)
{
  struct buf *b;

  b = bget(dev, blockno);
  // if buf is new(from iget)
  if((b->flags & B_VALID) == 0) {
    iderw(b);
  }
  return b;
}

breadについては、bget関数でstruct bufを取得する必要があるが、buffer cache(bcache)の中にすでに使用しているものがないかどうかを探す(b->dev == dev && b->blockno == blockno)。この場合、bget関数で得られるstruct buf bのb->flags & B_VALIDは真になるので、このbufferを返せば良い。

もしcacheが存在していなければ、誰も使用していない[b->refcnt == 0]、(&diskに書き込む必要のない[(b->flags & B_DIRTY) == 0]) bufferを探し、このbufferがdiskとsyncしていないflag(b->flags = 0;)を立てる。その後、syncする必要があるため、iderw関数を実行する。

// 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)
{
  struct buf *b;

  acquire(&bcache.lock);

  // Is the block already cached?
  for(b = bcache.head.next; b != &bcache.head; b = b->next){
    if(b->dev == dev && b->blockno == blockno){ // assume that b->refcnt != 0
      b->refcnt++;
      release(&bcache.lock);
      acquiresleep(&b->lock);
      return b;
    }
  }

  // Not cached; recycle an unused buffer.
  for(b = bcache.head.prev; b != &bcache.head; b = b->prev){
    // bcache.head is 
    if(b->refcnt == 0 && (b->flags & B_DIRTY) == 0) {
      b->dev = dev;
      b->blockno = blockno;
      b->flags = 0; // buf is not synced with disk data, so B_VALID should be off
      b->refcnt = 1;
      release(&bcache.lock);
      acquiresleep(&b->lock);
      return b;
    }
  }
  panic("bget: no buffers");
}

iderwでは大体の場合idestartが呼ばれることになり、その後、以下のようになる：

詳しくはRefference[2]を参照のこと。(diskのI/O mapped I/Oのregisterの詳細まで書くの大変なので)

bwrite

bwriteは以下のような形である：

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

breadと違って、buffer cacheに書き込む処理がない。これは、Logging layerのlog_writeで行われているのだが、Logging Layerの節で紹介しよう。

さて、bwrite関数はiderw -> idestart のあと、以下のように処理される：

詳しくはRefference[2]を参照のこと。

ここで大きなポイントなのが、bread と bwriteとはデータ転送処理を行うタイミングに関して非対称であるということだ：

  • breadではinterrupt handler(ideintr関数)内部でデータ転送処理(insl(0x1f0, b->data, BSIZE/4);)を行う。つまり、interrupt handlerが終了する頃には、データ転送処理はすでに終わっているということだ：
void
ideintr(void)
{
  struct buf *b;

  // First queued buffer is the active request.
  acquire(&idelock);

  // skip

  /* read data */
  if(!(b->flags & B_DIRTY) && idewait(1) >= 0)
    insl(0x1f0, b->data, BSIZE/4);

  // Wake process waiting for this buf.
  b->flags |= B_VALID;
  b->flags &= ~B_DIRTY;
  wakeup(b);

  // skip

  release(&idelock);
}
  • bwriteではデータ転送が完了した後(つまりoutsl(0x1f0, b->data, BSIZE/4);が完了したら)、interruptが呼ばれる
// Start the request for b.  Caller must hold idelock.
static void
idestart(struct buf *b)
{
  if(b == 0)
    panic("idestart");
  if(b->blockno >= FSSIZE)
    panic("incorrect blockno");
  int sector_per_block =  BSIZE/SECTOR_SIZE;
  int sector = b->blockno * sector_per_block;
  int read_cmd = (sector_per_block == 1) ? IDE_CMD_READ :  IDE_CMD_RDMUL;
  int write_cmd = (sector_per_block == 1) ? IDE_CMD_WRITE : IDE_CMD_WRMUL;

  if (sector_per_block > 7) panic("idestart");

  idewait(0);
  outb(0x3f6, 0);  // generate interrupt
  outb(0x1f2, sector_per_block);  // number of sectors
  outb(0x1f3, sector & 0xff);
  outb(0x1f4, (sector >> 8) & 0xff);
  outb(0x1f5, (sector >> 16) & 0xff);
  outb(0x1f6, 0xe0 | ((b->dev&1)<<4) | ((sector>>24)&0x0f));
  if(b->flags & B_DIRTY){
    outb(0x1f7, write_cmd); // request WRITE_SECTOR(S) command to disk
    outsl(0x1f0, b->data, BSIZE/4); /* write data */
    // In WRITE request, interrupt handler occurs HERE!!
  } else {
    outb(0x1f7, read_cmd); // request READ_SECTOR(S) command to disk
    // In READ request, interrupt handler occurs HERE!!
  }
}

Logging Layer

Logging layerはdisk書き込みの整合性を保つためのlayerである。もう少し詳しく言うと、disk書き込み時のtransactionを実装したlayerである。

例えば、

  1. read
  2. write
  3. read
  4. write

ということをする関数があったとする( e.g) sys_mkdirはcreate関数にてwriteを2回以上行っている)。 この場合、1~4番目は最初から最後まで処理されることを期待している。そうでなければ、整合性を保てなくなる恐れがある。

例えば3番目が終了した直後に(電源が落ちるとかで)diskが動作しなくなったとする。この場合、4番目をやり残しているため、OSを再度起動させようとしても、disk内のデータが不整合をおこし、予期せぬ結果を招く可能性がある。

そこでxv6ではLogging layerをBuffer cache layerとInode layerの間に挟むことによって、このような事態を防いでいる。方法としては、gitコマンドのstagingとcommitの処理にわりかし似ている：

  1. start_op
  2. read
  3. write
  4. read
  5. write
  6. end_op -> commit

1~5まではgitのstagingに対応する処理で、buffer cacheと他の構造体のデータとの間をread/writeする 。3,5番目はbwriteの代わりにlog_write関数を用いる：

void
log_write(struct buf *b)
{
  int i;

  // skip

  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)
    log.lh.n++;
  b->flags |= B_DIRTY; // prevent eviction
  release(&log.lock);
}

log_writeでは、変更内容自体をdiskに書き込むのではなく、どのblock numberに変更があるかをstruct log log global変数によってメモしておく。

最後のb->flags |= B_DIRTY;は、(bget関数にて)bufferがreusableでないという印をつける処理3である。こうすることで、bufferの内容(buf->data)は実際にcommitするまで残存し続ける！

Note) readに関しては、diskに変更を加えないため、仮にreadの途中でdiskがcrashしたとしても、diskが不整合になることはない。Logging layerはwrite処理でのみ考慮されるlayerである。

6番目のcommit関数で実際にdiskの指定の場所に書き込みたいデータをwriteする：

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(); // Now install writes to home locations
    log.lh.n = 0;
    write_head();    // Erase the transaction from the log
  }
}

本質的なtransactionの処理は、write_head => bwrite => iderw => idestart => outsl(0x1f0, b->data, BSIZE/4) である。write_headで、struct log logの中身(つまり、書き込むべきdiskのblock number)をdiskに書き取る。

write_log()は、書き込むべきbuffer(これはwrite_logによって、bufferの内容(buf->data)が実際にcommitするまで残存し続けるのだった！)の内容をdisk内の一時的なblock4に保存する処理である。

とりあえず、outslがatomicであることを仮定しよう。実はこれによって、transactionと書かれてある処理の前後で、diskデータの一貫性が保たれる(一貫性の保存というのは、diskがcrashしてもOSの再起動によってrecoveryできるという意味である)：

  • outsl(0x1f0, b->data, BSIZE/4)の前にdiskがcrashした -> struct log logをdiskの中身に保存していない -> recover_from_log関数(boot時の処理)は特に何もしない
 -> データは保存されていないが、diskの一貫性は保たれている。

  • outsl(0x1f0, b->data, BSIZE/4)の後でdiskがcrashした -> block numberがdisk内に保存されてる -> write_log()で書き込むべきdataが保存されているから、recover_from_log関数(boot時の処理)によって復元できる。 -> 書き込むべきデータがboot時に復元できており、diskの一貫性が保たれている。

みたいな感じ。たとえ、recover_from_log関数の途中でdiskのcrashが起こっても、write_headにて、書き込むべきdiskのblock numberがdisk内に保存されている以上問題なく、OSを再び再起動して、recover_from_log関数によってdiskを復元することができる。

Note) recover_from_log関数とcommit関数を比べてみる：

static void
recover_from_log(void)
{
  read_head();
  install_trans(); // if committed, copy from log to disk
  log.lh.n = 0;
  write_head(); // clear the log
}

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(); // Now install writes to home locations
    log.lh.n = 0;
    write_head();    // Erase the transaction from the log
  }
}

2番目のwrite_head完了後に失敗した場合、OS再起動時にrecover_from_logが呼び出されるが、read_head();はdiskに保存したstruct logの内容をreadしている処理でその後のinstall_trans();, log.lh.n = 0;, write_head()はそのままcommit関数に対応していることが見て取れる。

もし、commit関数のlog.lh.n = 0;の直後にdiskがcrashした場合でも、(diskにはその内容が残っていないので、)recover_from_log関数が同じように実行される。

Note) さて、outslがatomicであるかどうかだが、ここは本当にそうなのかいまいちわからなかった。自分が調べた限りでは、

  • outslに突入する前にidelockというspinlockが入っているので、outsl実行中に別のCPUがdiskの書き込み/読み込みを行うことはない

  • Intel SDM vol.2のouts instructionにthe processor will not execute the next instruction until the data phase of the transaction is complete とある

ので、完全にatomicというわけではなさそうだが、ほぼ問題ないとも見れる。 可能性があるとすれば、電源が落ちるなどで、outslの最中にCPUが動作しなくなり、disk書き込み自体が失敗して、diskの中身が不整合を起こすことはありそうな気がする。これはソフトウェアの問題というより、ハードウェアの問題だが...

filesystemの構造

さて、前章でfile systemのlayer("Disk Layer", "Buffer Cache Layer", "Logging Layer")について説明したが、具体的にdisk内にどのようなデータが入っているのかを説明していないので、その部分を述べる。

xv6におけるfilesystemの構造は以下のようになる：

f:id:knknkn11626:20190713110911p:plain
Reference[1] ch.6より

  • boot block: 一番最初のboot処理に必要なプログラムのバイナリデータが入ってる
  • super block: 後続するblockの情報が入っている
  • log block: Loggging Layerで、最初のブロックがlogheader, 2番目以降はwrite_log関数にて一時的に保存されるべきdata blockが格納されている
  • inodes (table) block: inode達の情報が入っている
  • bitmap block: data blockが使用可能かどうかを表すflag達がbitmapとして格納されている
  • data block: ファイルの内容のデータが格納されている

Note) filesystemはxv6ではmkfs.cによって作成される。fs.imgが出力イメージ。

それでは詳しく見ていくことにする。

boot block

boot blockの実体はbootの最初期のプログラムであるbootasm.Sとbootmain.cのバイナリデータなのだが、これは、 https://k-onishi.hatenablog.jp/entry/2019/05/27/223808 がわかりやすい。

もしくは、MBR(Master Boot Record)( https://ja.wikipedia.org/wiki/%E3%83%9E%E3%82%B9%E3%82%BF%E3%83%BC%E3%83%96%E3%83%BC%E3%83%88%E3%83%AC%E3%82%B3%E3%83%BC%E3%83%89 )を参照。 雰囲気的には最初のsector(512byte)でxv6カーネルの展開処理までのプログラムが埋め込まれている。

super block

superblockの内容はstruct superblock構造体にグローバル変数(struct superblock sb;)として格納される。readsb関数のstruct buf* bp = bread(dev, 1);でsuper blockの内容をbp->dataに格納し、memmoveでsbにmoveする。

struct superblock {
  uint size;         // Size of file system image (blocks)
  uint nblocks;      // Number of data blocks
  uint ninodes;      // Number of inodes.
  uint nlog;         // Number of log blocks
  uint logstart;     // Block number of first log block
  uint inodestart;   // Block number of first inode block
  uint bmapstart;    // Block number of first free map block
};

内容を見たとおり、各ブロック(log block, inodes block, bit map block, data blockの範囲の情報が書き込まれている。：

block start size(単位はblock)
log block logstart nlog(=30)
inodes(table) block inodestart ninodes(=200) / IPB(=8)(=25)
bitmap block bmapstart nblocks/(512*8[bit])(=1)
data block - 全体の残りすべて
[total] 0 nblocks(=1000)

ここでカッコの数字はmkfs.cによって定められる数字である。IPBは1 blockあたりのstruct dinodeの個数(BSIZE / sizeof(struct dinode))である。

log block

これはLogging Layerで使用されるblockで最初のblockにはlogheaderが格納されており、

struct logheader {
  int n;
  int block[LOGSIZE]; // block number
};

その次からのblockには書き込むべきdata blockが一時的なデータの格納場所として保存されている。mkfs.cでは29blocksである。

logheaderはread_head/write_headでdiskから読み書きされる：

  1. struct buf *buf = bread(log.dev, log.start);
  2. struct logheader *hb = (struct logheader *) (buf->data);

read_headの場合、更にstruct log log というglobal変数に詰め替えられる(理由はBuffer Cacheの節を参照のこと)。と言ってもstruct logはstruct logheader lh;がembedされているので、deep copyすればよいだけ。

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

write_headでは、更新されてるstruct log logをbuf->dataに書き込む。

これら2つの関数は前述の通り、Logging Layerのために存在しており、commit関数/recover_from_log関数で使われている。

inodes table block

これは、struct dinode(64byte)をentryとしたtableとなっており、superblockのinodestartから開始するblockである：

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];   // array of Data block number(NDIRECT=12)
};

inodeはfileの中身(data)に相当するもの(実際にはdataが格納されているblock number: addrs)とfile type(file or directory or special file(device file))などの情報が含まれている。

diskの1blockの大きさが512[byte]、sizeof(dinode)=64なので、1つのinode blockには、512/64=8つのinodeが格納されている。もし、tableのi番目のdinodeを抜き出したい場合、補助関数として、IBLOCKマクロが用意されている。

#define BSIZE 512  // block size
#define IPB           (BSIZE / sizeof(struct dinode)) // =8
// for inodestart member, see "super block"
#define IBLOCK(i, sb)     ((i) / IPB + sb.inodestart)

このマクロを用いると、所要のi番目のstruct dinodeをdiskからfetchすることとができる：

// ilock()
    bp = bread(ip->dev, IBLOCK(ip->inum, sb));
    struct dinode *dip = (struct dinode*)bp->data + ip->inum%IPB;

struct dinode(生inodeの情報)はすぐにstruct inode(こっちはinodeの情報を整理したffileに関する構造体)に詰め替えられる：

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]; // #define NDIRECT 12
};

Inode numberとは、diskのinode tableのindexer。

addrsのそれぞれの要素はdata block number。詳しくはdata blockの節で確認したい。

"/"(root path)は特別にinode number=ROOTINO=1となっている。path(char* 型)からinode(struct inode)を取得する際は、root pathを出発点として、dirlookup関数にて直下のinodeに降りることを繰り返す。

inodeについても、bcache(struct bufのcache)と同じようにcache機能を備えている：

struct {
  struct spinlock lock;
  // #define NINODE       50  // maximum number of active i-nodes
  struct inode inode[NINODE];
} icache;

Note) struct fileという構造体もあるが、これはopenしたfileの情報を示す構造体で、C言語で言うfile型と全く同じものである。struct inode(fileの実体情報を表す構造体)とは性質が全く異なることに注意すること。

bitmap block

これは、後続のdata blockがfreeなのか否か(2値なので1bitで表現できる)の集合。つまり、1 blockは512byteだから、512*8=4096bitで4096個のdata blockの使用可能判定が可能である。

例えば、1999番目のdata blockが使用可能かを確認したいときは、以下のようにすれば良い。

struct buf* bp = bread(dev, sb.bmapstart); // bitmap blockを取得する
int flag = bp->data[1999/8] & (1 << (1999 % 8)) // bp->dataはchar型の配列

4096個より多い数のdata blockの場合、bitmap blockは複数blockにまたがる。そういうわけで任意の番目のblockの位置(上の例だと、breadの第二引数)を決めるため、BBLOCKという補助マクロが用意されている5：

// max: sb.ninodes / IPB + sb.inod
// Bitmap bits per block
#define BPB           (BSIZE*8)

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

xv6ではbmap関数内のballoc()で使用可能なblockを線形探索し、見つかったら、block numberを返す。

data block

data blockはファイルの実体のblockで、struct inodeのaddrsがdata block numberに対応している。

inodeの読み書きはreadi/writei関数で行っている(readi, writei内部で更にdata blockが使用可能かどうか確かめるために、bmapを用いている)。

data blockの実体(inode->addrsの指示す先)はfile type(inode->type)によって異なるが、

  • T_FILEの場合は、file dataそのもの
  • T_DIRの場合は、struct direntの内容のtable(directory内に複数fileがぶら下がっているのに対応してる)
  • T_DEV(special file)の場合は、空。fileの形をとっているが、処理はdevsw[1].(read|write)関数に移譲される

となっている。

ここあたりは別記事にて、filesystem のlayerの上層を見るときに触れることにしたい。

  1. 実はxv6のfile systemではfilesystemの整合性を保てるようにする機構(Logging layer; log block)が備わっている。ext2のimplementationの解説ページ( http://e2fsprogs.sourceforge.net/ext2intro.html )を見る限りはそういう機構はなさそうなので、xv6のfile systemがext2の下位互換というわけではない。↩

  2. PIO転送はモード0~4まであり、数字が大きいほど最大転送レートも高いのだが、ATA(AT Attachment)-2の段階ですべてのモードをサポートしている。詳しくはReference[2]の「ATA(IDE)/ATAPIの歴史と概要」表1を参照のこと。ATA-2が1996年に定められた規格なのでPIO modeが以下にレガシーなデータ転送モードかがわかるだろう。↩

  3. bget関数はbcache内のbufferの中から未使用の(b->refcnt == 0 && (b->flags & B_DIRTY) == 0)のbufferを選択し、再利用する処理を含む関数である。もし、B_DIRTY=0のままだと、書き込むべきデータがあるにもかかわらず、再利用によって情報が再初期化されてしまうので問題となる。↩

  4. file systemの構造で説明するように、log blockの2番目以降。log blockの最初のblockはheaderの情報が格納されてる。↩

  5. mkfs.cではxv6のfilesystemのblockの総数を#define FSSIZE 1000としているため、その場合だと、このblockは1つで収まる。なので実は、BBLOCK(b, sb)は常にsb.bmapstartとなる。↩