advcal20161210 の編集

* 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まで管理できることになります。

//-ここでFAT16においてクラスタサイズ32バイトというのを考えましょう。え？512バイトじゃないの？と思うかもしれませんが、ええ、32バイトです。16バイトでもないです。
//-そもそも512バイトなんていうのは過去の伝統の成り行きで決まったもので、あまり必然性がありません。だから没。・・・また16バイトなんていうのはビットに直したら128ビットで、これは中途半端です。256ビットのほうがきりがいいです。256というのは、((2^2)^2)^2です。
//-いやもっと細かい単位で、1バイト単位にすべきだという意見もあるかと思いますが、そんな小さい単位で管理しても今度は管理コストばかりかかっていまいち得しないので、やっぱり32バイトくらいがちょうどよいと思います。
//-さて、32バイトのクラスタを46080個集めると1440KBになります。FAT16で46080個のクラスタを管理しようとすると、90KBを要します。1440KBを管理するために90KBも管理領域だけで使ってしまうというのはなんかバランスが悪いように思いますが、それでも6.25%です。まあ許容範囲です。・・・特に、これによって512バイト未満のファイルについて無駄を少なく管理できるようになるので、結局は得かもしれません。
//--仮に1バイト単位で管理した場合、FAT16では64KBまでしか管理できないのに、管理領域は128KBも必要ということになります。これはディスク領域の66%が管理領域に食われるということなので、非常に残念だと思います。ということで、管理単位を小さくすればいいってものでもないのです。

//-32バイトのクラスタの場合、FAT16の限界では、2MBまで管理できることになります。

** (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が裏方で頑張ります。

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

//-それぞれのファイルがどこに入れられるのかは、ファイルサイズで決まります。2MB未満ならレベル0です。2MB以上で512MB未満ならレベル1です。512MB以上で128GB未満ならレベル2です。
//-仮にちょうど512MBよりも1バイトだけ大きなファイルがあったとしましょう。これはFAT16レベル2に割り当てられて、クラスタサイズ2MBなので、514MBを割り当てられることになります。これは約2MBが無駄になってもったいないわけですが、しかしそれでも2MBなんて512MBから見れば0.39%です。

** (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 の空きマスはだいぶ少なくなってきました。全部うまったらいいなー。

* こめんと欄
#comment

タイムスタンプを変更しない