xv6におけるfilesystemのLayer(下層編)
はじめに
xv6におけるfilesystemの構造についてまとめたい。xv6ではext2とかではなく、もう少し簡素な独自filesystemを採用している1。
今回は、filesystemのデータ構造及び、下図のlayerの下三層つまり、"disk layer", "buffer cache layer", "Logging layer"を説明したい。
Reference
[0] xv6のソースコード https://github.com/mit-pdos/xv6-public/tree/xv6-rev11
[1] xv6の公式の解説 https://pdos.csail.mit.edu/6.828/2018/xv6/book-rev10.pdf
[2] 改訂版 ATA(IDE)/ATAPIの徹底研究 https://www.cqpub.co.jp/hanbai/books/49/49891.htm
Layer
"Logging Layer"は"Buffer Cache Layer"と"Disk Layer"のあとに説明する。
Buffer Cache layer(diskとmemoryのインターフェース)
まずは、diskとmemoryのそもそもの話から。
diskは本棚、memoryは机に例えられるが、実際に作業する場合は、本棚(disk)の中にある本(sector)を取り出し、机(memory)の上で読むだろう。
xv6 OSでも似たようなことをやっている:
- diskからデータ転送を行うbread or bwrite関数を開始
- diskのどの位置のデータを取りたいかを指定する
- コマンド(read or write)を指定する(実際にはいろいろコマンドの種類がある)
- 実際にdiskからデータを取り、memory内の
((struct buf*)buf)->data
にこのデータを格納する:- readの場合:
insl(0x1f0, buf->data, BSIZE/4);
ideintr内 - writeの場合:
outsl(0x1f0, buf->data, BSIZE/4);
idestart内
- readの場合:
この処理を経て、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が呼ばれることになり、その後、以下のようになる:
breadの場合(xv6)
— Kenta Nakajima (@knknkn26918) June 24, 2019
0. idestart
1. nIEN(0x3f6のbit1)=0でinterrupt有効に
2. sector位置を指定
3. 0x1f0(primary)+7に0x20(READ SECTOR(S))をWrite
4. 3のあと、1の影響でinterrupt(ideintr)が発生
5. data read(interrupt handler内で)
6. buf->flagsを正常に pic.twitter.com/XaD5NOCN1l
詳しくは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 のあと、以下のように処理される:
bwriteの場合(xv6)
— Kenta Nakajima (@knknkn26918) 2019年6月24日
0. idestart
1. nIEN(0x3f6: Device Control Reg.のbit1)=0でinterrupt有効に
2. sector位置を指定
3. 0x1f0(primary)+7(offset)に0x30(WRITE SECTOR(S)) commandをWrite(Device Control Reg.)
4. data write
5. 4.のあと1の影響でinterrupt(ideintr)が発生
6. buf->flagsを正常に pic.twitter.com/e15R08ScMS
詳しくは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である。
例えば、
- read
- write
- read
- 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の処理にわりかし似ている:
- start_op
- read
- write
- read
- write
- 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の構造は以下のようになる:
- 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から読み書きされる:
struct buf *buf = bread(log.dev, log.start);
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の上層を見るときに触れることにしたい。
-
実はxv6のfile systemではfilesystemの整合性を保てるようにする機構(Logging layer; log block)が備わっている。ext2のimplementationの解説ページ( http://e2fsprogs.sourceforge.net/ext2intro.html )を見る限りはそういう機構はなさそうなので、xv6のfile systemがext2の下位互換というわけではない。↩
-
PIO転送はモード0~4まであり、数字が大きいほど最大転送レートも高いのだが、ATA(AT Attachment)-2の段階ですべてのモードをサポートしている。詳しくはReference[2]の「ATA(IDE)/ATAPIの歴史と概要」表1を参照のこと。ATA-2が1996年に定められた規格なのでPIO modeが以下にレガシーなデータ転送モードかがわかるだろう。↩
-
bget
関数はbcache内のbufferの中から未使用の(b->refcnt == 0 && (b->flags & B_DIRTY) == 0
)のbufferを選択し、再利用する処理を含む関数である。もし、B_DIRTY=0のままだと、書き込むべきデータがあるにもかかわらず、再利用によって情報が再初期化されてしまうので問題となる。↩ -
file systemの構造で説明するように、log blockの2番目以降。log blockの最初のblockはheaderの情報が格納されてる。↩
-
mkfs.cではxv6のfilesystemのblockの総数を
#define FSSIZE 1000
としているため、その場合だと、このblockは1つで収まる。なので実は、BBLOCK(b, sb)
は常にsb.bmapstart
となる。↩