xv6: mkfsの実装を読む
mkfsの実装をだいたい理解したので，xv6のファイルシステムの仕組みを中心に覚え書きとして残しておく。
ファイルシステムのブロック構造
ファイルシステムは複数のブロックで構成される。1ブロックは512バイト。
最初の1ブロックはブート用なのでfs.imgでは未使用。
次の1ブロックはsuperblockで，ファイルシステムのメタデータを格納する領域。
次の26ブロックはinodeで，struct dinodeを格納する領域。inodeの最大個数=ninodes=200なので，必要なブロック数はninodes*sizeof(struct dinode)/512+1=200*64/512+1=26と求められる。プラス1しているのは，ninodes*sizeof(struct dinode)が512未満でもブロック数が0にならないように。
次の1ブロックはbitmapで，各ブロックの使用状態を保存する領域。ビットが1なら使用済み，0なら未使用。全体のブロック数はsize=1024なので，必要なブロック数はsize/(512*8)+1=1024/(512*8)+1=1と求められる。
次の985ブロックはdataで，ファイルのデータを保存する領域。data領域のブロック数はnblocks=985と設定されている。
最後の10ブロックはlogで，ファイルシステムのジャーナリング用の領域。log領域のブロック数はnlog=10と設定されている。
合計で2+26+1+985+10=1024ブロック。
/~~ 2 ~~＼ /~ 1 ~＼ / 10 ＼
+-----+----+-------+--------+------------+-------+
| N/A | SB | inode | bitmap | data | log | TOTAL: 1024
+-----+----+-------+--------+------------+-------+
＼ 26 / ＼__ 985 __/
inodeとファイルデータの構造
inode領域はファイルのメタデータを保存する領域。ファイルのデータはdata領域に保存される。
struct dinodeのaddrsメンバにデータ保存先のブロック番号が格納されている。addrsはuint配列で，最初のNDIRECT=12個は直接参照。残りの1個は間接参照。addrsの値が0ならブロック未使用。
ファイルのデータサイズは最大で(NDIRECT+NINDIRECT)*512=(12+128)*512=70KB。
下記はMAXまでデータを書き込んだ時のファイルデータの構造。
+---------------+ +-------------+
| struct dinode | /~| BLOCK No.29 |
+---------------+ / +-------------+
| other members | / | CONTENT |
+---------------+ / +-------------+
| addrs[0]=29 |_/ +-------------+
+ - - - - - - - + /~~~~| BLOCK No.30 |
| addrs[1]=30 |_/ +-------------+
+ - - - - - - - + | CONTENT |
| ... | +-------------+
+ - - - - - - - + +-------------+
| addrs[11]=40 |_/~~~~~| BLOCK No.40 | +--------------+
+ - - - - - - - + +-------------+ /~| BLOCK No.42 |
| addrs[12]=41 | | CONTENT | / +--------------+
+---------------+~＼ +-------------+ / | CONTENT |
＼__+-------------+ / +--------------+
| BLOCK No.41 | / +--------------+
+-------------+ / /~~~~| BLOCK No.43 |
| 42 |_/ / +--------------+
+ - - - - - - + / | CONTENT |
| 43 |_/ +--------------+
+ - - - - - - + +--------------+
| ... | /~~~~~| BLOCK No.169 |
+ - - - - - - + / +--------------+
| 169 |_/ | CONTENT |
+-------------+ +--------------+
ディレクトリの構造
ディレクトリの場合はファイルデータがstruct direntの配列になっている。
下記はdirentが3つのときのディレクトリの構造。
+---------------+ +---------------+
| struct dinode | /~| BLOCK No.29 |
+---------------+ / +---------------+
| type=T_DIR | / | +-------------+-+
+---------------+ / | | struct dirent |
| other members | / | +---------------+
+---------------+ / | | inum=1 | --> inode No.1
| addrs[0]=29 |_/ | | name="." |
+ - - - - - - - + | +-------------+-+
| addrs[1]=0 | | +-------------+-+
+ - - - - - - - + | | struct dirent |
| ... | | +---------------+
+ - - - - - - - + | | inum=1 | --> inode No.1
| addrs[12]=0 | | | name=".." |
+---------------+ | +-------------+-+
| +-------------+-+
| | struct dirent |
| +---------------+
| | inum=2 | --> inode No.2
| | name="README" |
| +-------------+-+
+---------------+
mkfs.c: main関数で何をしているのか？
冒頭部分でファイルシステム全体に関わるパラメータを初期化。その後，イメージ全体をゼロ埋めして，superblockにパラメータを書き込む。
続いて，ルートディレクトリの初期化と，ドットディレクトリ（という言い方が正しいかどうかはわからないが，「.」「..」のこと）の追加を行う。
続くforループでは，引数で与えられたファイルを次々に読み込んでinodeを作成，ルートディレクトリに追加している。
最後の部分でルートディレクトリのinodeのファイルサイズをブロックサイズ単位に丸めているが，これが必要なのかどうかがちょっと疑問。
次の点に注意：mkfsはファイルイメージに次々にファイルを書き足していくだけの用途を想定して実装されているので，単純にdata領域の先頭から次々にブロックを確保するようになっている。
ファイルイメージに対してもっと色々な操作をしようとすると，ファイルの削除で使用済みブロックが断片化するので，新しくブロックを確保する際に，data領域の先頭から空きブロックが見付かるまで走査するような処理が必要になる（こうしないと，ファイルの追加削除を繰り返した際に，ブロックの確保ができなくなってしまう）。
