initramfs

コンピューターの神秘のひとつに、起動時にファイルシステムドライバを読み込むためにファイルシステムにアクセスしなければならないという矛盾があります。 現代の OS では起動に必要なファイルを収めた簡易ファイルシステムを RAM に展開してこれを解決します。

initrd と initramfs

この仕組みは linux などで慣例的に initrd (INITial RamDisk の略) と呼ばれています。 実際の linux には initrd と initramfs という２種類の仕組みがあって、現在では initramfs の方が一般的に使われています。

MYOS でも initrd が導入されましたが、 initrd は仮想ブロックデバイスとしてマウントするのでファイルシステムドライバが必要になってしまうという問題があります。

MYOS の initrd は FAT を選択したので FAT に由来するいくつかの問題も引きずることになりました。 起動時のファイルシステムは適当なファイル名を指定してバイト列を読み出せればいいだけなので本格的なファイルシステムの機能はほとんど必要なく、 FAT ですらオーバースペックな一方で、 FAT 特有の扱いづらさもありました。

というわけで initrd の仕組みを変えましょう。

OSZ の initramfs

最小の MEG-OS である OSZ にも独自実装の initramfs があります。

最後の方に12バイトの 8.3 形式ファイル名、 2バイトのオフセット、2バイトのサイズで合計16バイトのファイルエントリが並んでいるのがわかるかと思います。 OSZ はカーネルにファイルシステムドライバが存在せず、代わりにカーネルの後半にこのようなファイルシステムが連結されていて起動時のシェルなどを読み込んでいます。

TOE の initramfs

TOE ではブートローダーをあまり複雑にしたくないので、最初に読み込むカーネルファイルの後半に initramfs を連結したいと思います。

最初は OSZ 方式をそのまま採用しようかと検討しましたが、すぐに 64KB の壁にぶち当たることが明白ですし、古き良き 8.3 形式ファイル名の制限も現代ではちょっと厳しいです。 ということで、エントリを２倍の32バイトに広げてファイル名の制限を緩めてオフセットやサイズも4バイトに拡張して実装しました。

ブートローダーはカーネルの後半にあるアーカイブをメモリの一番最後にコピーしてカーネルを起動するときに bootinfo にアドレスを通知し、ファイルシステムマネージャの初期化時にそこにあるデータを読み込むようにします。

これで TOE にもファイルシステムが実装できました🎉

今後

MYOS のファイルシステムはインターフェースも未整備で結構微妙な感じでした。 今後はファイルシステムインターフェースを整備して TOE から MYOS に移植して、それが終わったらいよいよ TOE でもアプリ実行できるようにしたいですね。

MYOS の起動処理概要

MYOS の起動処理をかんたんに解説します。

MYOS をメインに解説しますが、 TOE は MYOS のサブセットとして開発が始まったので共通点も多いです。

Boot Loader 〜 カーネルエントリポイント

まずはブートローダーが起動します。ブートローダーの細かい動作は本質的ではないのでここでは省略します。 BIOS や UEFI から呼び出されて、ハードウェア情報収集、ビデオモードの初期化、カーネルの読み込みなどが終わったら CPU モードの初期設定をしてカーネルのエントリポイントに制御を移します。

余談ですが、 OS が起動時に自分で自分を読み込む一連の動作はコンピューター最大の神秘と矛盾であり、 「pull oneself up by one's bootstraps」という英文の靴紐 (bootstrap) が自分で自分を持ち上げるような違和感を連想したことから転じて、 コンピューターの起動を boot strap と呼ぶようになったと言われています。

ブートローダーからカーネルが起動されると、エントリポイントから System::init() が呼び出されます。

System::init()

System::init() の引数には BootInfo という構造体が渡されます。 MYOS と TOE では詳細が異なりますがどちらも起動に必要な情報が入っています。 起動後にも必要になる情報は別の場所にコピーします。

次に、 BootInfo の画面情報をもとに main_screen というスタティックなビットマップオブジェクトを作成します。 旧 MYOS のコンソール画面は main_screen の初期化後に個別の初期化が必要でしたが、 TOE のクラスと統合した現在では main_screen を初期化するだけでコンソール出力もできるようになります。

次に、 BootInfo のメモリ配置情報をもとに MemoryManager::init_first() を呼び出して最低限のメモリマネージャを初期化します。 以降、 alloc 系のクラス (Box, Vec など) が動作するようになってヒープに動的にメモリ確保できるようになります。 現在のバージョンではブートローダーが最低限のページング設定を済ませているのでメモリマネージャはページ操作しません。

次に、 MYOS は外部の ACPI ライブラリを初期化します。*1 ACPI が利用できるようになったら ACPI の情報をもとに system.cpus に CPU の個数分だけ領域を予約して Cpu::new() を呼び出してブートプロセッサの初期化します。

次に、 Arch::init() を呼び出してアーキテクチャ固有の初期化を行います。 arch 以下のクラスはアーキテクチャ固有の処理が多いのでアーキテクチャごとにかなり違います。 主な内容は CPU の初期化 (Cpu::init())、割り込みコントローラーとタイマーの初期化、 SMP の初期化等のシステムのコア部分の初期化です。 TOE(x86) の場合は 8259 PIC と 8253 PIT を各プラットフォームごとにほぼ同じ動作をするように設定します。 MYOS(x64) の場合は APIC と HPET を初期化して最後に SMP を有効にします。

最後に Scheduler::start() を呼び出してスケジューラーを開始します。 スケジューラーの初期化が終わるとメインスレッドはブートプロセッサで HLT 命令を実行し続けるだけのアイドルスレッドになります。

この段階で狭義のカーネルが動作するようになります。

System::late_init()

スケジューラーが開始すると新しいプロセス (System) で System::late_init() が起動するので以降の初期化を行います。 基本的にはここではいろんなサブシステムを初期化して最後にシェルを起動します。

まず、 MemoryManager::late_init() を呼び出して追加のメモリ管理機能を初期化します。 現在のバージョンでは最低限のメモリマネージャ機能しか実装されていないのでここでは何もしていません。

次に、 Fs::init() を呼び出してファイルシステムを初期化して起動時ファイルシステムがアクセス可能になります。 現在の TOE では未実装です。

次に、 RuntimeEnvironment::init() を呼び出し、アプリケーション実行環境をサポートするための BinaryRecognizer と Personality が利用可能になります。 現在の TOE では未実装です。

次に、 FontManager::init() を呼び出してフォントマネージャを初期化します。 初期化以前にも固定のシステムフォントは利用できますが、以降は FontDescriptor による複雑なフォントも使えるようになります。

次に、 WindowManager::init() を呼び出してウィンドウマネージャを初期化してウィンドウが使えるようになります。

次に、 HidManager::init() を呼び出して HID マネージャを初期化します。 HID マネージャはキーボードやマウスの信号をウィンドウマネージャに渡してウィンドウメッセージに変換する仲介をします。

次に、 Arch::late_init() を呼び出して機種固有の初期化の続きを実行します。 ここでキーボードやマウスなどのデバイスが使えるようになります。

ここまででいわゆるカーネルの初期化が終わります。

最後にエントリポイントから渡された関数 (main) に制御を移します。 現在はカーネルモードでシェルっぽいウィンドウを表示してユーザーと対話できるようにしています。 ここでユーザーがコンピューターを実際に操作可能な状態になります。

Cpu::init() と Cpu::new()

Cpu::init() と Cpu::new() はどちらも CPU 初期化するためのメソッドですが、役割が違います。 MYOS では IDT はシステム全体で共通ですが 、GDT はプロセッサコアごとに内容が異なります。

Cpu::init() はシステム全体の CPU 共通の初期化をします。 具体的には、 IDT の用意をしたり CPU の世代を調べて利用可能な機能を整理したりします。

Cpu::new() はマルチプロセッサのプロセッサコアごとの初期化で Cpu オブジェクトのインスタンスを返します。 具体的には、 GDT の初期化をしたりコア固有の ID を用意したりします。

Apic::init()

MYOS の Arch::init() 内で呼ばれる Apic::init() はマルチプロセッサが絡んで動作がけっこう複雑なのでここで少し詳しく解説します。

SMP の重要な用語として BSP と AP があります。 BSP (Boot Strap Processor ブートストラッププロセッサ) はシステム起動時に動作しているプロセッサコアを指します。 マルチコア環境でシングルコアの OS を起動する場合は BSP だけが動いている状態になります。 AP (Application Processor アプリケーションプロセッサ) は BSP 以外の全てのプロセッサコアを指します。

SMP は Symmetric Multiprocessing (対称型マルチプロセッサ) の略で、名前の通り全てのプロセッサが対称になります。 x86/x64 の SMP では起動時に BSP を決めるプロトコルで BSP になれなかったプロセッサコアは AP として起こされるまで待機状態になります。

SMP の動作で重要になるのが APIC (Advanced Programmable Interrupt Controller) です。名前の通り PIC よりも高度な割り込みコントローラーになります。 APIC には Local APIC と I/O APIC の２種類あります。 I/O デバイスで外部割り込み (IRQ) が発生した場合は I/O APIC で割り込みを受信して各プロセッサコアにある Local APIC に対して割り込みを分配し、 Local APIC が CPU コアに対して割り込み命令を実行させます。

I/O APIC のリダイレクトテーブルでは外部割り込みをどのプロセッサコアに対して割り込みを分配するか設定することができます。 特定のプロセッサに固定で分配したり負荷状況に応じて動的に分配することもできますが、この機能を使わないシステムも多く MYOS では全ての IRQ を BSP で処理します。

SMP 環境ではその他の割り込みとして、 IPI (Inter-Processor Interrupt プロセッサ間割り込み) と Local APIC の割り込みがあります。

SMP 環境で他のプロセッサと通信するときは Local APIC を操作して IPI というコマンドを発行します。 通常の IPI は対象のプロセッサコアに対して割り込みを発生しますが、 SMP の初期化で使う INIT IPI も Startup IPI も通常の割り込みとは異なる専用のコマンドになります。

Local APIC 割り込みにはいくつか種類があります。 MYOS で利用しているのは Local APIC タイマー割り込みです。 高精度に測定できる HPET があるのに Local APIC タイマーが必要な理由は、 Local APIC タイマー割り込みはコアごとに設定することができるのでスケジューラーのプリエンプションに利用します。

まずは ACPI の情報をもとに APIC を初期化します。*2 APIC を有効にすると割り込みがすべて APIC 経由になって PIC が誤動作するといけないので PIC の IMR には 0xFF (全て無効)に設定しておきます。

    Cpu::out8(0xA1, 0xFF);
    Cpu::out8(0x21, 0xFF);

次に LocalApic::init() を実行して BSP の Local APIC を有効化します。MSR にある IA32_APIC_BASE というレジスタに Local APIC のベースアドレス (通常は 0xFEE0_0000)、 IA32_APIC_BASE_MSR_BSP フラグ、 IA32_APIC_BASE_MSR_ENABLE フラグを書き込んで有効化しています。

unsafe fn init(base: usize) {
    LOCAL_APIC = Mmio::from_phys(base, 0x1000).ok();

    Msr::ApicBase.write(
        (base as u64 & !0xFFF) | Self::IA32_APIC_BASE_MSR_ENABLE | Self::IA32_APIC_BASE_MSR_BSP,
    );
}

次に IoApic::new() を実行して I/O APIC を初期化します。

unsafe fn new(acpi_ioapic: &acpi::platform::IoApic) -> Self {
    let mut ioapic = IoApic {
        mmio: Mmio::from_phys(acpi_ioapic.address as usize, 0x14).unwrap(),
        global_int: Irq(acpi_ioapic.global_system_interrupt_base as u8),
        entries: 0,
        id: acpi_ioapic.id,
        lock: Spinlock::new(),
    };
    let ver = ioapic.read(IoApicIndex::VER);
    ioapic.entries = 1 + (ver >> 16) as u8;
    ioapic
}

ここでは IoApic 構造体の情報を設定しているだけで I/O APIC に特にコマンドを書き込んだりしません。 バージョンレジスタに I/O APIC がサポートしている IRQ の個数 (通常は 24) があるのでそこだけ I/O APIC にアクセスしています。 I/O APIC が複数存在するシステムも存在するようですが実際に見たことがないので詳細は不明です。

これだけで APIC が使えるようになります。意外と簡単ですね。 あとは I/O APIC のリダイレクトテーブルに IRQ の情報を書き込むとその IRQ を割り込みとして受け取ることができます。

APIC が使えるようになったら Local APIC タイマーを初期化します。

    let vec_latimer = Irq(0).as_vec();
    InterruptDescriptorTable::register(
        vec_latimer,
        timer_handler as usize,
        PrivilegeLevel::Kernel,
    );
    LocalApic::clear_timer();
    LocalApic::set_timer_div(LocalApicTimerDivide::By1);
    if let Ok(hpet_info) = acpi::HpetInfo::new(System::acpi()) {
        let hpet = Hpet::new(&hpet_info);
        let magic_number = 100;
        let deadline0 = hpet.create(TimeSpec(1));
        while hpet.until(deadline0) {
            Cpu::spin_loop_hint();
        }
        let deadline1 =
            hpet.create(hpet.from_duration(Duration::from_micros(100_0000 / magic_number)));
        LocalApic::TimerInitialCount.write(u32::MAX);
        while hpet.until(deadline1) {
            Cpu::spin_loop_hint();
        }
        let count = LocalApic::TimerCurrentCount.read() as u64;
        APIC.lapic_timer_value = ((u32::MAX as u64 - count) * magic_number / 1000) as u32;
        Timer::set_timer(hpet);
    } else {
        panic!("No Reference Timer found");
    }
    LocalApic::set_timer(
        LocalApicTimerMode::Periodic,
        vec_latimer,
        APIC.lapic_timer_value,
    );

ちょっと複雑ですが、 Local APIC タイマーは実際に設定する値と割り込み間隔の設定が単純な計算で求めるのが難しいので、 HPET を使って Local APIC タイマーに設定する値を簡易測定してます。

ここまでで APIC の初期設定が終わったのでいよいよ SMP の有効化手順をはじめます。

まずは、 Startup IPI で使うためのベクタを用意します。

Startup IPI で送信するベクタは専用の特殊なベクタで、ベクタ番号を 12 ビット左シフトしたリニアアドレスのコードが呼び出されます。 仮にベクタ番号 0x01 とすると実際の初期化コードはシフトされたリニアアドレス 0x01000 になります。*3 初期化コードの中ではスタックが利用できない (=メモリ割り当て関数を呼び出せない) ので、 STACK_CHUNK_SIZE * プロセッサコア数分のスタックも先に確保しておきます。

    let sipi_vec = InterruptVector(MemoryManager::static_alloc_real().unwrap().get());
    let max_cpu = core::cmp::min(System::num_of_cpus(), MAX_CPU);
    let stack_chunk_size = STACK_CHUNK_SIZE;
    let stack_base = MemoryManager::zalloc_legacy(max_cpu * stack_chunk_size)
        .unwrap()
        .get() as *mut c_void;
    asm_apic_setup_sipi(sipi_vec, max_cpu, stack_chunk_size, stack_base);

asm_apic_setup_sipi の中では AP の初期化コードを _smp_rm_payload にあるコードブロックから Startup IPI ベクタを変換したリニアアドレスにコピーし、初期化コードで参照する BSP の情報も SMPINFO に書き込んでおきます。 EFER は BSP の値をそのまま書き込むと EFER.LMA の解釈違いでクラッシュする環境のためここでリセットしておきます。（参考: EFER.LME と EFER.LMA - 借り初めのひみつきち）

asm_apic_setup_sipi:
    push rsi
    push rdi

    movzx r11d, cl
    shl r11d, 12
    mov edi, r11d
    lea rsi, [rel _smp_rm_payload]
    mov ecx, _end_smp_rm_payload - _smp_rm_payload
    rep movsb

    mov r10d, SMPINFO
    mov [r10 + SMPINFO_MAX_CPU], edx
    mov [r10 + SMPINFO_STACK_SIZE], r8d
    mov [r10 + SMPINFO_STACK_BASE], r9
    lea edx, [r10 + SMPINFO_GDTR]
    lea rsi, [rel _minimal_GDT]
    lea edi, [rdx + 8]
    mov ecx, (_end_GDT - _minimal_GDT) / 4
    rep movsd
    mov [rdx + 2], edx
    mov word [rdx], (_end_GDT - _minimal_GDT) + 7

    mov ecx, 1
    mov [r10], ecx
    mov rdx, cr4
    mov [r10 + SMPINFO_CR4], edx
    mov rdx, cr3
    mov [r10 + SMPINFO_CR3], rdx
    sidt [r10 + SMPINFO_IDT]
    mov ecx, IA32_EFER
    rdmsr
    btr eax, EFER_LMA
    mov [r10 + SMPINFO_EFER], eax

    lea ecx, [r11 + _startup64 - _smp_rm_payload]
    mov edx, KERNEL_CS64
    mov [r10 + SMPINFO_START64], ecx
    mov [r10 + SMPINFO_START64 + 4], edx
    lea rax, [rel _ap_startup]
    mov [r10 + SMPINFO_AP_STARTUP], rax

    mov eax, r10d
    pop rdi
    pop rsi
    ret

準備が終わったら INIT IPI を全てのプロセッサに送信して 10ms 待機します。 INIT IPI はリセット信号に近いもので、 INIT を受信した AP はリアルモードで起動して SMP BIOS が Startup IPI を待機する状態になります。

    LocalApic::broadcast_init();
    let timer = Timer::new(Duration::from_millis(10));
    while timer.until() {
        Cpu::halt();
    }

LocalApic::broadcast_init() の中身はこんな感じで IPI コマンドレジスタに値を書き込んでいます。 IPI コマンドレジスタは組になっている２つの 32bit レジスタで、上位レジスタには宛先のコア ID などを設定し、下位レジスタに値を書き込むと実際にコマンド送信されます。

unsafe fn broadcast_init() {
    Self::InterruptCommandHigh.write(0);
    Self::InterruptCommand.write(0x000C4500);
}

次に Startup IPI を全てのプロセッサに送信します。 これで AP 上で OS の初期化コードが走るようになります。

    LocalApic::broadcast_startup(sipi_vec);

LocalApic::broadcast_startup() の中身もこんな感じで IPI コマンドを書き込んでいます。

unsafe fn broadcast_startup(init_vec: InterruptVector) {
    Self::InterruptCommandHigh.write(0);
    Self::InterruptCommand.write(0x000C4600 | init_vec.0 as u32);
}

Startup IPI を受信した AP は Startup IPI で指定した専用のベクタから起動します。ここで asm_apic_setup_sipi であらかじめコピーしておいた _smp_rm_payload のコードブロックが実行されます。ここからしばらくはリアルモードで、 Startup IPI を受信した複数のプロセッサが同時に実行開始するためスタックは利用できません。

まずは単純なアトミック加算で仮の CPU 番号を決めて ebp レジスタに保存します。 SMPINFO_MAX_CPU に設定したコア数より多くなった場合、そのコアは HLT で無限ループします。

_smp_rm_payload:
    cli
    xor ax, ax
    mov ds, ax
    mov ebx, SMPINFO

    mov ax, 1
    lock xadd [bx], ax
    cmp ax, [bx + SMPINFO_MAX_CPU]
    jae .fail
    jmp .core_ok
.fail:
.forever:
    hlt
    jmp short .forever

.core_ok:
    movzx ebp, ax

次に BSP からもらった SMPINFO の情報をもとに最低限の設定でロングモードを有効にします。

一時的な GDT をロードしてセグメントを初期化し、 CR0.PE をセットしてプロテクトモードに遷移し、データセグメントやスタックセグメントを設定します。 その後 BSP で保存しておいた値で CR3、CR4、EFER を設定し、最後に CR0.PG をセットしてロングモードに遷移します。

    lgdt [bx + SMPINFO_GDTR]

    mov eax, cr0
    bts eax, CR0_PE
    mov cr0, eax

    mov ax, KERNEL_SS
    mov ss, ax
    mov ds, ax
    mov es, ax
    mov fs, ax
    mov gs, ax

    mov eax, [bx + SMPINFO_CR4]
    mov cr4, eax
    mov eax, [bx + SMPINFO_CR3]
    mov cr3 ,eax

    mov ecx, IA32_EFER
    xor edx, edx
    mov eax, [bx+ SMPINFO_EFER]
    wrmsr

    mov eax, cr0
    bts eax, CR0_PG
    mov cr0, eax

最後に _startup64 にセグメント間ジャンプして 64bit モードに遷移します。 jmp far dword というのはこの時点では 16bit セグメントなので far jump も 16bit で解釈されてしまうのを 32bit の far jump として解釈するようにするおまじないです。

    jmp far dword [bx + SMPINFO_START64]

_startup64 はすぐに _ap_startup にジャンプします。 初期コードから _ap_startup に直接ジャンプしないのは、 _ap_startup が 4GB (0x1_0000_0000) を超えるリニアアドレスに存在するためセグメント間ジャンプ命令では直接遷移できず、いったん 4GB 以下のアドレスで 64bit モードに遷移しておく必要があるためです。

_startup64:
    jmp [rbx + SMPINFO_AP_STARTUP]

_ap_startup は IDT を設定し、 ebp レジスタに保存しておいた仮の CPU 番号をもとにコアごとのスタックの割り当てをした後 apic_start_ap() を呼び出します。

_ap_startup:
    lidt [rbx + SMPINFO_IDT]

    mov eax, ebp
    imul eax, [rbx + SMPINFO_STACK_SIZE]
    mov rcx, [rbx + SMPINFO_STACK_BASE]
    lea rsp, [rcx + rax]

    mov ecx, ebp
    call apic_start_ap

apic_start_ap() では LocalApic::init_ap() でローカル APIC の初期化、 Cpu::new() で CPU の初期化、 System::activate_cpu() を呼び出して CPU をアクティブにし、 TSC 同期のために BSP に再び呼び出されるまで一旦待機します。

pub unsafe extern "C" fn apic_start_ap() {
    let apic_id = GLOBALLOCK.synchronized(|| {
        let apic_id = LocalApic::init_ap();
        System::activate_cpu(Cpu::new(apic_id));

        apic_id
    });

    while AP_STALLED.load(Ordering::Relaxed) {
        Cpu::spin_loop_hint();
    }

LocalApic::init_ap() では BSP の時より処理が少し多くなっています。 MSR で APIC を有効化し、スプリアス割り込みを有効にし*4、 Local APIC タイマーを BSP と同じ設定で初期化し、最後に自分自身の APIC ID を返します。

unsafe fn init_ap() -> ProcessorId {
    Msr::ApicBase
        .write(LOCAL_APIC.as_ref().unwrap().base() as u64 | Self::IA32_APIC_BASE_MSR_ENABLE);

    let apicid = LocalApic::current_processor_id();

    LocalApic::SpuriousInterrupt.write(0x010F);

    let vec_latimer = Irq(0).as_vec();
    LocalApic::clear_timer();
    LocalApic::set_timer_div(LocalApicTimerDivide::By1);
    LocalApic::set_timer(
        LocalApicTimerMode::Periodic,
        vec_latimer,
        APIC.lapic_timer_value,
    );

    apicid
}

Cpu::new() では一時的な GDT からプロセッサ固有の GDT への切り替えを行い、 APIC ID と CPU トポロジー情報から SMT の裏コア判定 *5 をし、 Cpu 構造体を初期化して返します。 また、現在のバージョンでは SSE 非対応なのでここで CR4.OSFXSR をリセットして SSE を強制的に無効化しています。

pub(crate) unsafe fn new(apic_id: ProcessorId) -> Box<Self> {
    asm!("
        mov {0}, cr4
        btr {0}, 9
        mov cr4, {0}
        ", out(reg) _);

    let gdt = GlobalDescriptorTable::new();

    let core_type;
    if (apic_id.as_u32() & Self::shared().smt_topology) == 0 {
        core_type = ProcessorCoreType::Main;
    } else {
        core_type = ProcessorCoreType::Sub;
    }

    Box::new(Cpu {
        cpu_index: ProcessorIndex(0),
        cpu_id: apic_id,
        core_type,
        gdt,
        tsc_base: 0,
    })
}

System::activate_cpu() では System::cpus に Cpu 構造体を追加してアクティブなプロセッサコア数を更新します。

pub(crate) unsafe fn activate_cpu(new_cpu: Box<Cpu>) {
    let shared = Self::shared();
    if new_cpu.processor_type() == ProcessorCoreType::Main {
        shared.num_of_performance_cpus += 1;
    }
    shared.cpus.push(new_cpu);
}

BSP 側のコードでは全ての AP がアクティブになるまで待機し、規定の時間内に何らかのトラブルが発生してすべての CPU の初期化が正常に終わらなかった場合には panic します。

    let timer = Timer::new(Duration::from_millis(200));
    while timer.until() {
        let timer = Timer::new(Duration::from_millis(5));
        while timer.until() {
            Cpu::halt();
        }
        if System::num_of_active_cpus() == max_cpu {
            break;
        }
    }

    if System::num_of_active_cpus() != max_cpu {
        panic!("Some of application processors are not responding");
    }

正常に AP が起動できた場合、各プロセッサの初期化の順番がランダムで仮に発行した CPU 番号もバラバラになっているので、本当の APICID で並び替えます。 最後に AP_STALLED の値を false に設定して TSC 同期のために待機してるすべての CPU を再開させます。

    System::sort_cpus(|a, b| a.cpu_id.0.cmp(&b.cpu_id.0));

    for index in 0..System::num_of_active_cpus() {
        let cpu = System::cpu(index);
        CURRENT_PROCESSOR_INDEXES[cpu.cpu_id.0 as usize] = cpu.cpu_index.0 as u8;
    }

    AP_STALLED.store(false, Ordering::SeqCst);
    System::cpu_mut(0).set_tsc_base(Cpu::rdtsc());

BSP 側で AP_STALLED の値を false にすると AP 側の待機が終了して TSC の値を調整します。 TSC はコアごとにバラバラに動作していてコアが変わると値が変わるため、 set_tsc_base() でコアごとの差分を保存しておいて API から TSC を利用するときはこの値で同期を取ります。 また、 IA32_TSC_AUX MSR に現在のプロセッサ番号を書き込んで RDTSCP 命令で今動作しているプロセッサのプロセッサ番号を簡単に取得できるようにします。

    while AP_STALLED.load(Ordering::Relaxed) {
        Cpu::spin_loop_hint();
    }
    let tsc = Cpu::rdtsc();

    for index in 0..System::num_of_active_cpus() {
        let cpu = System::cpu(index);
        if cpu.cpu_id == apic_id {
            System::cpu_mut(index).set_tsc_base(tsc);
            if Cpu::has_feature_rdtscp() {
                Msr::TscAux.write(index as u64);
            }
            break;
        }
    }

ここまで準備をしたので AP はスケジュール可能になりました。 最後に割り込みを許可し、スケジューラーからスレッドを割り当てられるまで HLT 命令を実行し続けるプロセッサ固有のアイドルスレッドになります。

    sti
.loop:
    hlt
    jmp .loop

*1:この部分、将来は自作のライブラリに切り替え予定です

*2:この２つ名前が似ていて紛らわしいですね・・・

*3:余談ですが、 SMP 起動ベクタは利用可能な最も低い 0 以外のアドレスを割り当てる専用の割り当て関数があるので UEFI のメモリマップがよほど特殊な事情がない限り MYOS では 0x01 になります

*4:これが必要な理由は忘れましたが、設定しないとうまく動作しません

*5:MYOS のスケジューラーでは表コアを優先で使用し、裏コアは表コアを全て使い切るまでなるべく割り当てない方針で調整中です

スケジューラーと優先順位の逆転

MYOS のスケジューラーは SMP に対応しています。

つまり、 CPU を 100% 使おうとする重いタスクが２個あった場合、合計で 200% ほど使うことができるわけです。

これがシングルコアだったら 100% を仲良く分け合って 50% しか使うことができません。

マルチコアすごいですね。

ところで CPU を 100% 使おうとするタスクが１個だけだった場合、どうなるでしょうか？

なんと、 90% くらいで頭打ちになってそれ以上使うことができません！

実はこのような奇妙なバグが以前から放置されていたので修正します。

優先度とプリエンプション

MYOS では優先度ベースのプリエンプティブマルチタスクをサポートしています。

優先度の高いタスクはより多くの CPU 実行時間を割り当ててもらうことができますが、自分より優先度の高いタスクがキューにあったら優先度の低いタスクは優先度の高いタスクに CPU を譲るしかありません。 また、優先度が同じタスクが複数あった場合、一定時間実行した後にタイマー割り込みでスケジューラーがキューにある次のタスクを順番に実行します。 そして、他のすべてのタスクが実行キューになかった時はアイドルタスクが実行されて次の割り込みまで CPU を一時休眠させます。

優先順位の逆転 Priority Inversion

ところで、自分が一番優先度が高くて他にライバルになるタスクがいなかった場合どうなるでしょうか？

この場合も同じようにタイマー割り込みでスケジューラーが起動します。 そして、まだタスク切り替えが行われていないので自分自身はまだキューに存在しません。つまり、自分と同じ優先度のキューには誰も待っていないことになります。 そうすると、スケジューラーは次の優先度のキューを探しに行って実行可能なタスクが見つかるまでキューを探します。ここで優先順位の逆転現象が発生します。 最後に誰も見つからなかったらアイドルタスクを実行し、アイドルタスクでタイマー割り込みが発生してスケジューラーが起動した時には以前実行していたスレッドはキューに戻されているので再度実行されます。

このようにして CPU を奪い合うライバルがいないはずなのに CPU を 100% 使い切ることができません。 これが謎の 90% の正体です。

CPU を 100% 使うタスクが２つ以上ある場合はいい感じにキューにタスクが積まれてすぐに実行されるので、１つの場合よりも多くの CPU 時間を使うことができるようになっていました。

修正

というわけで、優先度の判定と次に実行するタスクを決める処理を修正して、実行キューに他に待機してるタスクがない場合はプリエンプションを抑制するようにしました。

これで、ひとつのタスクだけで CPU をほぼ 100% 使うことができるようになりました💪

３種のビットマップ

昨日の日記で何故ビットマップクラスが３種類必要になるのか少し補則します。

生ポインタと Box

旧 MYOS のビットマップは生ポインタでデータを管理していました。 これは所有権もライフタイムも Rust によって管理されておらず借用の制限もなかったので C 言語とあまり変わらない危険な状態でした。

TOE のビットマップクラスで旧 MYOS に一番近いのは、 Box でヒープに所有しているビットマップ (BoxedBitmap) です。 所有権とライフタイムを Rust が管理しているのが大きな違いです。

pub struct BoxedBitmap8<'a> {
    inner: Bitmap8<'a>,
    slice: UnsafeCell<Box<[IndexedColor]>>,
}

BoxedBitmap を直接可変借用すれば通常の描画は大抵事足りそうですが、いくつか問題があります。

可変借用

フレームバッファや他のビットマップの一部を切り取った View オブジェクトはデータをヒープに所有していないので BoxedBitmap で扱うことができません。 ウィンドウの描画などは描画する範囲だけ切り取った View を多用します。

Rust ではヒープに確保するクラスとそうではないクラスは通常明確に分かれています。 そこで、普段の描画はビットマップデータを可変借用スライスで扱うクラスを使います。基本の描画クラスになるので名前もシンプルに Bitmap にしました。

pub struct Bitmap8<'a> {
    width: usize,
    height: usize,
    stride: usize,
    slice: UnsafeCell<&'a mut [IndexedColor]>,
}

BoxedBitmap は内部に Bitmap を保持しているのでゼロコピーで借用できます。

不変借用

Rust は可変借用に対して制限が厳しい言語です。 blt のソースに使う画像などは可変借用する必要性がないので不変借用したいです。

また、ソースファイルにパターンデータを記述してそのまま blt するようなプログラムも簡単に記述したいので定数でデータを保持したいですが、 BoxedBitmap や Bitmap は内部で可変のビットマップデータを管理しているので、不変のデータを扱うことができません。

このような状況では、内部で不変スライスを借用した定数ビットマップ (ConstBitmap) を使用します。

pub struct ConstBitmap8<'a> {
    width: usize,
    height: usize,
    stride: usize,
    slice: &'a [IndexedColor],
}

BoxedBitmap や Bitmap は ConstBitmap に変換して借用できます。

いかがでしたか？

このように、状況に応じて３種類のビットマップオブジェクトを定義して使い分けることで、さまざまなケースで効率的にデータを扱うことができるようになります。

ビットマップクラス統合

近代的な OS は一部の組み込み用途をのぞくと画像処理が不可欠です。 MYOS や TOE も画像処理にそれなりの割合を割いています。

MYOS と TOE の大きな違い

MYOS の主要なターゲットは UEFI で、 UEFI では 32bit ARGB 形式が標準です。 また、近代的な画像処理は 32bit ARGB 形式で扱うことが多いので、 MYOS では 32bit ARGB で描画します。

また、 MYOS は Rust を勉強し始めて借用とライフタイムの理解が浅い頃に作り始めてとりあえずビットマップ出力できないと何も進まない状況だったため、ビットマップデータを生ポインタで管理していてあまりお行儀のいい設計ではありませんでした。

pub struct Bitmap {
    base: *mut u32,
    size: Size,
    stride: usize,
    flags: BitmapFlags,
}

一方、 TOE の主要なターゲットは古き良き BIOS 、 PC-9821、FM TOWNS と幅広くなっており、これらの機種で共通して使えて変な癖の少ないモードは 8bit インデックスカラーモードなので、 TOE は 8bit インデックスカラーで描画します *1

また、 TOE を始める頃には借用やライフタイムなどの理解がより深まっていたので、 MYOS 時代よりも Rust らしいクラス設計になっています。

pub struct Bitmap8<'a> {
    width: usize,
    height: usize,
    stride: usize,
    slice: UnsafeCell<&'a mut [IndexedColor]>,
}

TOE は基本的にほとんどの部分で MYOS のサブセットとなっていますが、以上の経緯により描画周りに関して全く互換性がありませんでした。

MYOS はアプリ実行環境で 8bit カラー対応する必要があったために別のビットマップクラスを追加し、 TOE は 8bit カラー以外の環境でも動作するように 32bit カラービットマップ描画にも対応する必要が出てきました。

同じようなクラスを何個も作るのはうんざりしますね。

ということで、これらの描画ライブラリをひとつの同じライブラリで統合したいです。 MYOS よりも TOE の方が洗練されているので TOE をベースに統合することになりました。

統合方針

設計方針として、まずは色モードに非依存の統合した抽象クラスを作り、実際のデータ保持や描画を担当する 8bit カラー用のビットマップクラスと 32bit カラー用のビットマップクラスを作ります。 MYOS では多くの場面で引き続きそのまま 32bit クラスを使用し、 TOE は基本的には抽象クラスで受け渡しをして実際に描画するときに 8bit カラーのクラスと 32bit カラーのクラスに分岐することにします。

pub enum Bitmap<'a> {
    Indexed(&'a mut Bitmap8<'a>),
    Argb32(&'a mut Bitmap32<'a>),
}

Rust らしさやパフォーマンスを考慮すると、 blt などで不変借用する Const クラス、描画用に可変借用する Mutable クラス、ウィンドウバッファなどヒープに動的確保するクラスの３種類欲しいです。 ヒープクラスは一時的に借用できますし、可変借用は不変借用に変換できますが、逆方向の変換はできません。

３色３種類で単純に９種類のクラスが必要になることがわかるかと思います。実際はもう少し複雑ですが。

９種類の似たようなクラスがバラバラに存在していると実装効率が悪いので、ある程度同じ特性を持ったクラスを Trait でまとめたり Generics を使って実装します。 また、互換性のあるクラスへのデータ変換が可能なものについては変換用のメソッドも実装します。

これらのことを続けた結果、かなりたくさんの Trait と実装になってしまいましたが、 TOE でも 32bit カラーモードで描画できるようになりました🎉

地獄の統合作業

次はこれを MYOS に移植します。

MYOS のビットマップオブジェクトは先述のように生ポインタを保持していたので、かなりの部分で借用とライフタイムの扱いを誤魔化していました。 過去の過ちを正すときが来ました。

とりあえず単純に移植しただけで100を超えるエラーメッセージの祝福を受けました。

エラーの内容は、クラス構造が変わったことによるメソッド名や型名のエラーと、借用とライフタイム違反のエラーに大別されます。 前半のエラーは対応する別の名前に置き換えれば大抵解決しますが、後者は少しずつ修正してエラーが減ってくると突然新しいエラーがどんどん生まれてきます。

Rust は借用とライフタイムの扱いがかなり厳しいので適当に設計するとコンパイルが通らず正解を見つけるまでに丸１日費やすこともあります。 とはいえ MYOS のコードを TOE に移植するときに大半の問題は解決済みなので、ひとつずつ地道に修正してついにビルドに成功しました🎉

MYOS のフォント描画クラスがちょっと特殊だったのでまだ完全に移行できていませんが、それ以外は概ね TOE と MYOS で共通の描画コードが使えるようになって保守性が上がりました。

Rust は Borrow Checker 完全理解期と 'lifetime ナンモワカラン期が定期的に繰り返しやってきて難しいですね😿

*1:より高い互換性を考慮すると 4bit カラーモードなどが視野に入ってきますが、 8bit 以下のカラーモードは機種ごとにアクセス方法が異なりコードが複雑難解になるので除外しました

アクティビティモニターの作り方

MYOS や TOE にはアクティビティモニターがあります。

これらは見せ方が若干異なりますが、定期的にスケジューラーが集計したデータをそのまま表示しているだけです。

では、スケジューラーはどのように集計しているのでしょうか？

CPU時間

スレッドの切り替えのタイミングを知っているのはカーネルのスケジューラーなので、 スケジューラーが実際にスレッドを切り替える瞬間にシステムの時間を計測すればスレッドの実行時間を測定できます。

下の例のようなタイミングでスレッド切り替えをしたとします。（実際のOSは100倍〜1000倍くらい高速に切り替えます）

時間 切り替え
0秒 起動してスレッドAを実行
5秒 スレッドA→Bに切り替え
10秒 スレッドB→Cに切り替え
20秒 スレッドC→Aに切り替え

まずはスレッドAからBに切り替わるときシステム時間が 5 - 0 = 5 秒経過していたのでスレッドAの実行時間は 5 秒、次にスレッドCに切り替わるときも 10 - 5 = 5 秒経過しているのでスレッドBの実行時間は5秒、最後にスレッドCからAに戻ってきたときは 20 - 10 = 10 秒経過していたのでスレッドCの実行時間は10秒ということがわかります。

これらのデータを累算していくことで各スレッドが消費した CPU 時間がわかります。 また、ここで測定したデータが以降のデータの基になります。

各スレッドの CPU 利用率

各スレッドの CPU 利用率は時間の経過とともに変化する値で、一定の時間内にそのスレッドが利用した CPU 利用時間の割合に等しくなります。

先述の CPU 利用時間の累積値を一定の時間ごとにリセットすると、そのスレッドが一定時間のうち実際に実行された CPU 時間がわかります。 これを % で表示したものが各スレッドの CPU 利用率になります。 MYOS や TOE では１秒ごとに集計する専用のスレッド (Statistics) があります。

システム全体の CPU 利用率とアイドル率

他のすべてのスレッドが待機状態のときに HLT 命令を実行して CPU を休ませる専用のスレッドをアイドルスレッドと言います。

アイドルスレッドが実行されている時間は CPU が休んでる時間で、アイドルスレッドが実行されていない時間は CPU が忙しい時間ということになります。 つまり、アイドルスレッド以外のスレッドの CPU 利用率の合計がシステム全体の CPU 利用率になります。

なお、システム全体の CPU 利用率とアイドルスレッドの CPU 利用率を合計すると理論上 100% になるはずですが、集計のタイミングや細かい誤差などによって若干ズレが発生します。

CPU コアごとの CPU 利用率

MYOS は SMP に対応しているのでコアごとの CPU 利用率も計測できます。

MYOS ではコアごとにコア専用のアイドルスレッドがあります。 それぞれのアイドルスレッドとコアが 1:1 で紐づいているので、各アイドルスレッドの CPU 利用率がそのままコアごとのアイドル率になり、それを 100% から引いたものがそのコアの CPU 利用率ということになります。

また、マルチコア環境ではシステム全体の CPU 利用率の合計が 100% を超えることになりますが、 MYOS のアクティビティモニターでは平均値を表示しているので 100% を超えることはありません。

CPU 利用率グラフ

以上の情報を定期的に収集してグラフを描画すれば利用率のグラフになります。

いかがでしたか？

このように集計することで、それぞれのスレッドの負荷を測定したりスケジューラーが正しくスケジューリングしているか確認することができます。

なお、 TOE は時間計測に PIT を利用しているので精度が低い (1ms) ですが、 MYOS は HPET を利用しているので TOE よりもかなり正確に (1us) 測定することができます。

CD から OS を起動する

昔の OS は CDROM で提供されていました。

TOE は標準でフロッピーから起動しますが、さいきん入手難しくなってきたので CD 起動に対応したいと思います。

ロメオとジョリエット

CDROM のファイルシステムはたくさんの規格が複雑にからんでいます。 CDROM は特定の OS に依存せず他機種間でデータ交換が容易になるよう最大公約数的な仕様が決められたので、元の最小規格では FAT の 8.3 形式よりも厳しいファイル名の制限がありました。 また、興味深い特徴としてリトルエンディアンとビッグエンディアン両方のシステムに対応するために多くのフィールドはペアで用意されています。

しかし、それでは色々不便だったので拡張規格が登場しました。 主に Windows で使われている Joliet と、 un*x 系OSで使われている Rock Ridge などが主要な拡張規格です。 また、過去には Romeo という拡張規格もあったようですが現在ではマイナーな気がします。

Joliet は Volume Descriptor 自体が標準と別に用意されてディレクトリやパステーブルも全部独自になっていること、ファイル名が UTF16 になっていることなど、 IPL では扱いにくい特徴を持っているので今回は対応しません。

El Torito

PC で CDROM から OS を起動するには El Torito という規格に従います。

El Torito では起動情報の書かれた boot.catalog というファイルが必要ですが、 mkisofs が自動的に処理してくれるので通常気にする必要はありません。 用意する必要があるのは実際に起動するファイルだけになります。

El Torito ではハードディスクエミュレーション、フロッピーエミュレーション、エミュレーションなしの３種類の起動方法があります。

フロッピーエミュレーションモードは DOS など元々 CD 起動に対応してない OS を起動するためにイメージファイルを使って仮想フロッピーを作ります。 HD エミュレーションもイメージファイルを使って仮想ディスクを作りますが、実際に使われているのを見たことはないです。 エミュレーションなしは多くの OS で使われていて直接 CD から起動できます。

今回はエミュレーションなしで行きます。 mkisofs のオプションでいうと -no-emul-boot -b cdboot.bin と指定します。

CD 起動 IPL の書き方

CDROM のセクタサイズは通常 2KB なのでエミュレーションなしの起動ファイルのサイズも 2KB になります。 フロッピーやハードディスクの 512 バイトに比べると大きいですが、そんなに複雑な処理をする余裕もないのでディスクからシステムを読み込んで実行するだけのシンプルな IPL にします。

起動してレジスタの初期値を設定したら、まずは 16 番セクタの Primary Volume Descriptor を読み出します。

ISO9660 ではなぜか Volume Descriptor の開始セクタが 16 になっていて、それ以前のセクタは通常利用しません。

Volume Descriptor は最初の1バイトが種類を指してその次に "CD001" というシグネチャがあります。シグネチャが "CD001" 以外になる規格もあります（DVD など） Primary Volume Descriptor にはルートディレクトリのディレクトリエントリが埋め込まれているので +0x009E と +0x00A6 にあるルートディレクトリの開始セクタとサイズの情報を取得します。

次に、取得した情報をもとにルートディレクトリを読み出します。

ディレクトリを読み込んだらエントリを１つずつチェックしてシステムファイルを探します。 ディレクトリエントリ自体は可変長で最初の1バイト目がエントリサイズで、ファイル名は +0x20 、開始セクタは +0x02 、ファイルサイズは +0x0A からそれぞれ見つけることができます。

システムファイルを見つけたら該当するセクタからファイルを読み込んで実行します。

これで起動しました。（フロッピー起動と同じ見た目なのでスクリーンショット省略します）

FM TOWNS

FM TOWNS も CDROM から起動することができますが、 El Torito 規格ができる前だったので仕様が違います。

ISO9660では最初の 16 セクタを使用しませんが、 FM TOWNS は最初のセクタを IPL として読み込みます。 起動時点で El Torito と読み込むファイルが全く違うので機種専用の IPL になります。

基本的な処理は PC 用と同じ流れになります。 BIOS 呼び出す部分が違う程度です。

というわけで FM TOWNS でも CD 起動できました。

UEFI

今回は対応しませんが、 UEFI で CD 起動する場合は通常のメディアと同じように /EFI/BOOT/BOOTX64.EFI にブートローダーを置いておけば同じようにたぶん起動します。

いかがでしたか？

以上のように CDROM から TOE を起動することができるようになりました。 これでフロッピーが入手できなくなっても安心できそうな気がします。