UNIX 6th code reading - ファイルシステム概要

はじめに

今回からUNIX v6のファイルシステムを見ていきます。

いきなりLions本18章を読み解いていくのは難しいと感じたので、まずはファイルシステムの概要をまとめてみました。

今回はブロックデバイス上での処理を中心にまとめていきます。次回はコアメモリ中での処理をまとめようと思っています。

ブロックデバイス

ブロックデバイスの先頭#0はブートプログラムなどに使われます。

次の#1はsuper blockと呼ばれるブロックで、そのデバイスの情報が含まれます。filsys構造体(5561行目)を参考にしてください。

その後の#2〜#n+1まではinodeで占められます。inodeはファイルの情報を持ったデータで、ファイルサイズやパーミッションや更新日時、対応したファイルデータのアドレスなどを持ちます。後述しますが、ファイル名は持っていません。

また、i_numberとして、inode自体のナンバーを持っており、これはブロックデバイス中のアドレスと一対一に対応します。(アドレスからi_numberが決まるので、i_number自体はブロックデバイス中には記録されません。)

inodeが持っているデータは5605行目で定義されているinode構造体を参照してください。5659行目で定義されているinode構造体はコアメモリ中での定義ですのでご注意を。

inodeは32bytesで、1ブロック(512bytes)中16個のinodeが存在します。なので、あるi_number = iのinodeが存在するブロックは(i+31)/16で表され、ブロック中のアドレスは32*((i+31)%16)で表されます。

inodeからファイルデータへのアドレスマッピング

ユーザマニュアルのFILE SYSTEM(V)に詳しく書かれているのでご覧ください。

マッピングは大きくわけで三種類あります。

• 直接参照
• 間接参照
• 二重間接参照

上から順に扱えるファイルサイズが大きくなります。

直接参照

直接参照は、inodeのflags 010000(large fileかどうかのフラグ)が0のときに適用されます。

ファイル中のアクセスしたいバイトオフセットNを512で割り、それをbとする。(large fileでないときは)bが7以下のはずであり、inodeのaddr[b]に該当のデバイスブロックNoが格納されています。

直接参照で扱える最大のファイルサイズは512 x 8 = 4,096bytes = 4KB??

間接参照

間接参照はinodeのflags 010000が1の時に適用され、かつ、上記bを256で割った値が6以下である場合に適用されます。

bを256で割った値をiとすると、inodeのaddr[i]には間接参照ブロックのアドレスが格納されています。(間接参照ブロックは、デバイスのinodeのエリアとファイルデータのエリアどっちに格納されているんだろう。inodeのエリア？？)

このようなコメントを頂きました。間接参照ブロックはデータエリアにあるようです。

Nを割ったあまりから、間接参照ブロックの中のオフセットが決まり、そこにはデバイスのブロックNoが格納されています。

間接参照で扱える最大のファイルサイズは512 x 256 x 7 = 917,504bytes = 896KB??

二重間接参照

二重間接参照はinodeのflags 010000が1の時、かつ、上記iが7であるときに適用されます。

inodeのaddr[7]には間接参照ブロックの先頭アドレスが格納されています。そして、その間接参照ブロックのそれぞれのデータは、二重間接参照ブロックのアドレスを指しています。

二重間接参照で扱える最大のファイルサイズは512 x 256 x 256 = 33,554,432bytes = 32MBなのですが、ファイルの大きさが24bitsで保存されているため、実質は16,777,216bytes = 12MBまでしか扱えないようです。

さらに、このようなコメントを頂きました。確かにディスク自体のサイズ上限も考慮しないといけませんね。ディスク自体に32MBの制限があるので、addr[0]〜addr[7]全てで二重間接参照を使う必要がなく、addr[7]からのみ二重間接参照を使う設計になっているのかもしれません。

さらにさらに、このようなコメントを頂きました。

二重間接参照を使っているとき(addr[7]=1のとき)でも、addr[0-6]の間接参照を使っているようです。

このように思っていたのですが、二重間接参照単体で扱えるmax sizeが32MBということみたいです。

上記三種の参照方法を絵でまとめて描くとこんな感じです。

このマッピングはbmap( )(6415行目)で処理され、ユーザプロセスレベルで直接意識することはないと思います。

ディレクトリ

各ファイルはファイルのパス名でアクセスできるようになっています。パス名からinodeを取得できます。パス名からinodeへの変換はnamei( )(7518行目)で処理されます。

ファイル郡はルートディレクトリを頂点とした木構造で表されます。ディレクトリは配下にファイルを持てます。各ディレクトリ・ファイルのアクセス許可がないとアクセスできません(パーミッション)。

(本当はリンク(シンボリックリンク、ハードリンク)があるので、純粋な木構造ではなく、下から上へたどるパスも存在しています。)

そして、頂いたコメントを再掲。

各ディレクトリはファイル名とinumber(inodeの番号)の対応関係を表したテーブルを持っています。こんな感じに。

name	inumber
.	16
..	44
fuga	60
hoge	80
homu	122

ディレクトリがそのinode(inumber)を表すファイル名を持っているだけで、ファイルデータやinode自体はファイル名を持っていないことに注意してください。

また、上記のnamei( )は、ルートから、もしくはカレントディレクトリを起点として、パス名の最初から1要素ずつinodeを取得し、ディレクトリの中を見ては該当のinodeを取得し、さらにその中を見て……と繰り返して目的のファイル・ディレクトリのinodeを取得します。

終わりに

今回はブロックデバイス上の処理を中心としたファイルシステムについてまとめてみました。次回はコアメモリ中での処理を中心としたまとめを書く予定です。その後、Lions本の18章以降を読み解いて行こうと思っています。

superblockやマウントの話やinode・ファイルデータブロックの割り当てアルゴリズムについても話した方がよかったのかもしれませんが、それらはLions本の該当する章で触れますのでしばしお待ちを。