advcal20161210 のバックアップ(No.7)

バックアップ一覧
差分を表示
現在との差分を表示
ソースを表示
advcal20161210 へ行く。
- 1 (2016-12-09 (金) 23:23:02)
- 2 (2016-12-10 (土) 00:05:33)
- 3 (2016-12-10 (土) 08:41:11)
- 4 (2016-12-10 (土) 11:58:10)
- 5 (2016-12-10 (土) 19:20:59)
- 6 (2016-12-12 (月) 18:11:35)
- 7 (2016-12-14 (水) 13:59:08)

FAT16を発展させてみる

(by K, 2016.12.10)

↑

(0)

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

なんか最近アドベントカレンダばかり書いている気がする・・・。
正直なところネタ切れなので、ちょっとした思い付きを書きます。

お、12/10が埋まった！じゃあ、12/15の候補にします。

↑

(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領域のサイズが大きくなりすぎるという問題があります。最大で16GBになりえます。これに対してFAT16なら128KBが上限です（クラスタサイズに関わらず）。
そこで、クラスタサイズを一気に256倍にして128KBにしてみます。これだとFAT16でも8GBまで管理できます。・・・それでも足りなければさらに256倍します。
FAT16レベル0 クラスタサイズ512バイト最大容量32MB
FAT16レベル1 クラスタサイズ128KB 最大容量8GB
FAT16レベル2 クラスタサイズ32MB 最大容量2TB
クラスタサイズ128KBはまだ許せるとして（いやでも許しがたいけど）、クラスタサイズ32MBはちょっとひどい気がします。10バイトのファイルでも32MBを消費してしまいます。かといって最大容量が32MBとか8GBで我慢するというのも苦しいです。
そこで思いついたのですが、FAT16レベル1の中にはFAT16レベル0を内包することができる、というのはどうでしょうか。・・・つまり、FAT16レベル1は最大で8GBあるので、この中にFAT16レベル0を最大で256個入れられるわけです。同じく、FAT16レベル2の中にはFAT16レベル1を内包できます。
どのレベルのFAT16に入っていてもユーザは特に意識することもなく、普通にopenできてreadもwriteもできます。そこはOSががんばるのです。ただし従来のopenとは異なり、open時に想定ファイルサイズ上限を教えてやる必要はあります。それが分からないとどのレベルにおくかを決められないからです。

それぞれのファイルがどこに入れられるのかは、ファイルサイズで決まります。32MB未満ならレベル0です。32MB以上で8GB未満ならレベル1です。8GB以上で2TB未満ならレベル2です。
仮にちょうど32MBよりも1バイトだけ大きなファイルがあったとしましょう。これはFAT16レベル1に割り当てられて、クラスタサイズ128KBなので、32.125MBを割り当てられることになります。これは約128KBが無駄になってもったいないわけですが、しかしそれでも128KBなんて32MBから見れば0.39%です。
もしFAT16レベル2しかないときに1234バイトのファイルを保存する必要が生じたら、まずはFAT16レベル2の中にFAT16レベル1を作り、さらにその中にFAT16レベル0を作り、その中にその1234バイトのファイルを置くわけです。そうやってOSが裏方で頑張ります。

↑

(3)

こんなことしなくても、FAT32でいいじゃないかと思うかもしれません。FAT32ならクラスタサイズが512バイトでも2TBまで管理できてシンプルです。たしかにFAT領域のサイズは16GBになりますが、2TBからみれば16GBは0.78%でしかないので、これは問題じゃないです。
ポイントは、FATを小さく保つことです。FATを全部オンメモリに置けるかどうかは処理の単純化を考えると大きな差です。だから128KBで収まるFAT16は素晴らしいです。どんなに大きなファイルでもこの128KBの中をたどるだけでOKなのです。しかしFATを階層化しなければ、最大容量が極端に小さいか、もしくはクラスタサイズが大きくなって小さなファイルで無駄ばかりになるか、それが避けられません。だから階層化するのです。
複数のファイルを開く場合、もしかしたら所属FATが異なるかもしれません。その場合はFATも複数オンメモリに置く必要が出てきます。それでも同時に開くファイルの数より多くのFATが必要になることはないので、たかが知れています。

この階層FAT16にも問題があります。それは空き領域を速く探すにはどうするかということです。たとえば総容量が2TBでFAT16レベル2を使っているときに、中には複数のFAT16レベル1があり、さらにその中に多数のFAT16レベル0があるでしょう。もし1234バイトのファイルをこのディスクに入れようとなったら、レベル0の中から空きを探さなければいけません。そこがむずかしいです。うまい方法を考えなければいけません。

少し考えました。ディスクのどこかにFAT16の一覧があればよさそうです。そのディスク内にどのレベルのFAT16がどこにあるのか。空きはいくつなのか。たぶん32バイトもあれば1つのFATは記述できるでしょう。32KBくらいの領域があれば1024個のFATは登録できそうです。
もし2TBの中をレベル0のFAT16だけで管理するとすると、FAT16は全部で65536個必要になります。これだけの個数のFAT16を管理するとなると、2MBくらいの領域が必要そうです。

↑

(4)

デジタルカメラはたいてい1MBくらいのファイルを生成すると思われます。だったら、FAT16レベル1だけで十分です（最大容量が8GBってちょっと小さいかなあ）。でももし8GBまでしか対応しないでいいのなら、デジタルカメラはかなり簡単にファイル管理ができるのではないかと思われます。8GBを超えるにしても、上記のFAT16の一覧を使う程度なら難しいことはなさそうです。

いつか機会があったらもっときちんと設計してみようと思います。

↑

(5)

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

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

FAT16レベル0	クラスタサイズ512バイト	最大容量32MB
FAT16レベル1	クラスタサイズ128KB	最大容量8GB
FAT16レベル2	クラスタサイズ32MB	最大容量2TB