見出し画像

OS自作 ~ファイルシステム~

LearningHorse

前回のあらすじ

前回はStorageトレイトではハードディスクにアクセスできるようになりました。

今回はいよいよFATのファイルシステムを実装して、ファイルを扱えるようにしていきます。コミットはこれ（本来はこれ実装した直後はバグだらけですが、これはバグフ修正後のコミット）：


パーティションなどについて

ハーディスクを認識した後にOSがすべきことは、パーティションとそのファイルシステムを認識することです。ちょっとこれがまた混乱しやすいので簡単に説明します。ちなみにこういうの調べるのにBing Copilotに「~ってなに？」みたいに聞くと簡潔に教えてくれるので、僕の説明で分からないときは使ってみてください。

MBR(Master Boot Record)

これは旧式のパーティションを記述するデータ領域で、ディスク先頭にあります。MBRはBIOSでOSを起動するのに使われるので、UEFIに切り替わるにつれて使われなくなっています。特徴は：

  • パーティションの上限が2TB

  • パーティションの数は4つまで

GPT(GUID Partition Table)

こっちが最近使われてるデータ領域で、UEFIでブートします（MBRと同じくディスク先頭にある）。ちなみに、MBRに対する下位互換性があります。特徴は：

  • 最大18EBディスクまで扱える

  • パーティション数の最大数は128

  • パーティションの管理に128ビットのGUIDを使用

  • データのコピーがディスクの末尾にあるので冗長性が高い

VBR(Volume Boot Record)

PBR(Partition Boot Record)とも呼ばれます。これは上のデータ領域と異なり、各パーテションの先頭セクタにあります。MBRではブートコードを保持していましたが、GPTではブートコードは使われません。この中にMikan本で述べられているBPBがあります。

BPB(BIOS Parameter Block)

これはMikan本にも説明がありますが、補足しておくとFAT系列とNTFSのみで使われています。

ファイルシステムの認識

ファイルシステムの認識は、まずディスクのGPTを確認するところから始めます。OSがUEFIによるブートを前提としているので、MBRはあえて考慮しません。

GPTの定義

GPTの構造についてはOSdevを見てください。これ見ると下位互換性のためにPMBRなどがあるのがわかりますが、あくまで必要なのはHeaderとPartition Entryなので、これらだけを定義します。

struct PartitionTableHeader {
    signature: [u8; 8],
    revision: u32,
    header_size: u32,
    checksum: u32,
    reserved: u32,
    lba: u64,
    alternate_lba: u64,
    first_block: u64,
    last_block: u64,
    guid: [u8; 16],
    part_entry_lba: u64,
    num_entries: u32,
    entry_size: u32,
    array_checksum: u32,
}

struct PartitionEntry {
    type_guid: [u8; 16],
    part_guid: [u8; 16],
    start_lba: u64,
    end_lba: u64,
    name: [u8; 72]
}

struct GPT {
    header: PartitionTableHeader,
    entries: Vec<PartitionEntry>,
}

これを初期化したディスクから読み出して、失敗すればQEMUで起動しているように、いきなりPBRがくるものとして認識するように実装します。その処理の前に、GPTでチェックサムとして使われているCRC32について説明します。

CRC32(Cyclic Redundancy Check 32)

日本でいうと巡回冗長検査です。これも調べれば説明が見つかりますが、要は多項式にバイト単位（だと思う）で突っ込んで、足し合わせることで、ハッシュ値のようなものを生成しています。Wiki見ればわかりますが、この多項式に色々種類があります。GPTで使われているものはCRC32ですが、念の為OSdevにglibの実装を見ろと書いてあるので、gzipのDocsを見ながら実装しました。

FATの概要

まず、ファイルシステムを実装するのにもその仕様を理解する必要がありますが、完全に理解するのはそこそこ骨が折れました。結局こういうのは字面を追ってもわからん時は分かりませんが、僕なりに書いておきます。
ちなみに、僕はBing CopilotとZennとこのサイトで理解しました。

FATの構造

FATの構造をまず理解しましょう。FATはパーティションの先頭から順に、BPB、FAT、ディレクトリエントリorファイルのデータという順番で並んでいます。なぜ最後を強調したかというと僕が混乱したからなんですが、とりあえず最初から説明します。
BPBはいろんなところで解説されているので調べれば構造は簡単に出てきますが、要はFATの詳細情報をもったデータ領域です。
FATはFile Allocation Tableの略で、まさしくFATファイルシステムの中枢です。FATはクラスタチェーンを示す一次元配列です。これも大事なので強調しますが、FATはただN番目のクラスタの次のクラスタが何番目かという情報をひたすら結合した配列になっています。なので、ファイルが見つかったorディレクトリが見つかったら、このチェーンを辿ることになります。
最後にデータ部分ですが、ここにはディレクトリエントリかファイルのバイト列があります。つまり、そのクラスタがディレクトリのものならばディレクトリエントリ(32byte)の配列で、ファイルならそのデータのバイト列となっています。

FATのファイル探索処理

処理の手順通りに構造体を説明しないとこんがらがると思うので、ここでは処理の手順毎に改めて構造体の使い方を説明します。とりあえず処理を書くと、

  1. ルートディレクトリのクラスタ番号をBPBから取得する

  2. クラスタ番号から先頭のディレクトリエントリを取得し、オフセットを足しながら順番に名前を確認

  3. もしクラスタの終端まで来たら、FATのクラスタチェーンを参照して、次のクラスタを確認し、作業を続ける。

  4. ディレクトリ名が一致する（そしてFileAttributeが0x10）ディレクトリエントリを見つけたら、開始クラスタ番号を使って、再び作業2に戻る。

  5. 目的のファイルまで到達したらクラスタチェーンを使ってファイルの内容を取得する。

Mikan本だとルートディレクトリ以外無視しているので分かりにくいですが、サブディレクトリを考慮するとこうなります。しかし、まだ知る必要のあることがあります。現状ファイル名はディレクトリエントリから取得していますが、これではファイル名は8文字（拡張子3文字）に制限されてしまいます。そのためにあるのが長名エントリです。

LFN(Long File Name)

これもMikan本では無視されていますが、これやらないと不便にも程があるので実装します。ちなみにこれはFATを拡張したものなので、LFNに対応したFATをVFATと呼びます。
LFNの場合でも、普通にディレクトリエントリは存在しますが、通常のエントリの前に最大20個の長名エントリが続きます。長名エントリについてもこのサイトを見てほしいんですが、一つのエントリに13文字づつ保存されて、ファイル名の末端から順に並んでいます。

ファイル探索の実装

FATの実装は他にも色々実装していますが、とりあえずキーとなるファイル探索関数だけお見せします。

pub fn find_file(&self, full_path: &Path) -> Result<DirectoryEntry, u8> {
        let mut entry: DirectoryEntry;
        let mut dir_clus = self.bpb.root_clus;
        let mut lfn_flag = false;
        let mut lfn = String::from("");
        let mut i = 0;
        let mut name = &full_path.path[i];
        let mut buf = vec![0u8; self.bpc];
        while dir_clus != END_OF_CLUSTER_CHAIN {
            self.get_cluster(dir_clus, &mut buf);
            dir_clus = self.next_cluster(dir_clus);
            for c in 0..self.bpc as usize / size_of::<DirectoryEntry>() {
                let entry_ptr = unsafe { (buf.as_ptr() as *const DirectoryEntry).add(c) };
                unsafe { entry = *entry_ptr; }
                // Long File Name
                if entry.attr == (FATFileAttribute::LongName as u8) {
                    crate::debug!("Long File Name");
                    let lfn_entry = unsafe { *(entry_ptr as *const LFNEntry) };
                        if lfn_entry.is_end() {
                            lfn = String::new();
                        } else if lfn_entry.ord() == 1 {
                            lfn_flag = true;
                        }
                    lfn = format!("{}{}", bytes2str(&lfn_entry.get_name()), lfn);
                    continue
                // Volumen ID
                } else if entry.attr & 0x08 != 0 {
                    crate::debug!("Volume Name");
                // Directory
                } else if entry.attr & 0x10 != 0 {
                    crate::debug!("Directory");
                    if (lfn_flag && &lfn == name) || (!lfn_flag && Self::sfn_cmp(entry.name, &name)) {
                        if i == full_path.path.len()-1 {
                            return Ok(entry)
                        } else {
                            dir_clus = entry.first_cluster();
                            i += 1;
                            name = &full_path.path[i];
                            break
                        }
                    }
                // Regular File
                } else {
                    crate::debug!("Regular File");
                    if (lfn_flag && &lfn == name) || (!lfn_flag && Self::sfn_cmp(entry.name, &name)) {
                        if i == full_path.path.len()-1 {
                            return Ok(entry)
                        } else {
                            return Err(1)
                        }
                    }
                }
                if lfn_flag {lfn_flag = false}
            }
        }
        return Err(3)
    }

巨大ですが、やってることは前述した手順に則ってフォルダーを降りながら検索しています。

次回にすること

ようやくファイルシステムが使えるようになった！…はずだったんですが、なぜかうまくディスク読み込みができないことがあります。これを治すのにめちゃめちゃ時間がかかったので（この記事はファイルシステム実装してから少し後に公開してる）、次の記事はバグフィックスとその他諸々の話をしようと思います。

いいなと思ったら応援しよう！