advcal20161215 のバックアップ(No.1)

バックアップ一覧
差分を表示
現在との差分を表示
ソースを表示
advcal20161215 へ行く。
- 1 (2016-12-15 (木) 17:55:00)

FAT16を発展させてみる（改訂版）

(by K, 2016.12.15)

↑

(0)

この記事は、「自作OS Advent Calendar 2016」の12/15が空欄だったので急きょ書くことにした記事です。
- http://www.adventar.org/calendars/1666

なんか最近アドベントカレンダばかり書いている気がする・・・。

↑

(1)

MS-DOSはFATと呼ばれるファイルシステムを採用していました。ここでは特にFAT16について考えてみようと思います。
FAT16はディスクを（最大で）65536個のクラスタの集合と考えて、「このクラスタを読み終わったら続きはここにあるよ」という情報を並べたものです。厳密には65536個ではないのですが、でも16ビットであるということを素直に活用すれば、最大は65536個程度にはなります。これがあるおかげでディスクの連続していない領域にもファイルを入れることができて、なかなかよくできた仕組みだと思います。

ここでFAT16においてクラスタサイズ512バイトというのを考えましょう。・・・512バイトを2880個集めると1440KBになります。FAT16で2880個のクラスタを管理しようとすると6KBを要します。1440KBを管理するために6KBも管理領域が必要というのは、要するに0.42%が犠牲になったということなので、十分にOKです。
クラスタサイズ512バイトの場合、FAT16の限界では32MBまで管理できることになります。

↑

(2)

たったの32MBしか管理できないというのは使い物になりません。そこで世間ではFAT32とかに行くわけですが、FAT32はFAT領域のサイズが大きくなりすぎて全体をオンメモリに置くという簡単なアルゴリズムが使えません。また大きなファイルではFATを何度もたどる必要があり、効率が悪いです。ちなみにFAT32ではFATのサイズは最大で16GBになりえます。これに対してFAT16なら128KBが上限です（クラスタサイズに関わらず）。
ということで、FAT16だけでどこまで頑張れるかを考えましょう。

以下はFAT16におけるクラスタサイズと最大容量の対応表です。
クラスタサイズ512バイト最大容量32MB
クラスタサイズ128KB 最大容量8GB
クラスタサイズ32MB 最大容量2TB
クラスタサイズ128KBはまだ許せるとして（いやでも許しがたいけど）、クラスタサイズ32MBはちょっとひどい気がします。10バイトのファイルでも32MBを消費してしまいます。かといって最大容量が32MBとか8GBで我慢するというのも苦しいです。
そこで1つのディスクを複数のFAT16で管理します。この領域はクラスタサイズ512バイトで、この領域はクラスタサイズ128KBで・・・といった具合です。ディスク内のどのファイルもどれか1つのFAT16にしか所属しません。
どのファイルがどのFATに属するかはOSがファイルのサイズを見て決めます。小さいファイルならクラスタサイズ512バイトに積極的に割り当てます。大きいファイルならクラスタサイズ128KBとか1MBとかのFATに割り当てます。こうすることで、「大きなクラスタに小さいファイルがポツンとおかれて効率が悪い」という状況が起きないようにできます。クラスタサイズ128KBのところに11140KBのファイルを置けば末尾のクラスタは124KBが無駄になるわけですが、それは11140KBから見れば1.1%でしかないので、十分に許容範囲です。
どのFAT16に入っていてもユーザは特に意識することもなく、普通にopenできてreadもwriteもできます。そこはOSががんばるのです。ただし従来のopenとは異なり、open時に想定ファイルサイズ上限を教えてやる必要はあります。それが分からないとどのFATにおくかを決められないからです。
この仕組みはディスクをパーティションに分けるとは違います。パーティションはディスクイメージが分かれてそれぞれにルートディレクトリができますが、私の考えている方法はルールディレクトリは一つで、ただFATだけが複数あって、ディレクトリエントリにはファイルの先頭クラスタ番号だけではなく、FAT番号も書かれるのです。

↑

(3)

複数のファイルを開く場合、それぞれのファイルの所属FATが異なるかもしれません。その場合はFATも複数オンメモリに置く必要が出てきます。それでも同時に開くファイルの数より多くのFATが必要になることはないので、たかが知れています。

これらのFAT16はディスク内で一覧があって管理されています。そのディスク内のFAT16の位置とそれによって管理される領域とクラスタサイズが明記されています。たぶん32バイトもあれば1つのFATは記述できるでしょう。だから32KBくらいの領域があれば1024個のFATは登録できそうです。
もし2TBの中をクラスタサイズ512バイトのFAT16だけで管理するとすると、FAT16は全部で65536個必要になります。これだけの個数のFAT16を管理するとなると、2MBくらいの領域が必要そうです。

もっと具体的に考えます。

struct Fat16Table { // 32バイト.
    unsigned char signature[2];
    unsigned char crusterSize; // 3:1バイト, 12:512バイト, 20:128KB, 28:32MB,...
    unsigned char reserved[9]; // とりあえずオールゼロ.
    unsigned short sizeAll, sizeFree; // クラスタの個数で書く.
    unsigned char lbaFat[8], lbaCruster[8];
};

これが連続で並んでいれば、空きのあるFATは十分に高速に探せそうです。ディレクトリエントリには、ファイルの位置を表すところに、どのFATのクラスタ番号なのかを分かるように、FATの番号も書く必要があります。だから32バイトで1ファイルという方式はもうやめましょう。それだと8.3形式の名前しか入りませんしね。
- 64バイトで1ファイルにして、以下のようにしたらどうでしょう。
```
struct Entry {
    unsigned int name[40];
    unsigned int yy, mmddhhmmss; // 8バイト.
    unsigned short cruster0, flags; unsigned int fatId; // 8バイト
    unsigned int64 size; // 8バイト.
};
```

↑

(9) おまけの余談

http://www.adventar.org/calendars/1666 の空きマスはだいぶ少なくなってきました。全部うまったらいいなー。

↑

こめんと欄

コメント	お名前	NameLink

クラスタサイズ512バイト	最大容量32MB
クラスタサイズ128KB	最大容量8GB
クラスタサイズ32MB	最大容量2TB