借り初めのひみつきち

仮ブログです。

今週の MYOS

さいきんの MYOS/TOE 界隈のトピックです。

WebAssembly 高速化 (fused op)

中間コード変換とスタック操作合理化によって以前に比べると結構速くなりました。 この2つの改良によって実現可能になった新しい高速化手法があります。

WebAssembly は所謂スタックマシンなので個別の命令はスタックに push/pop するだけの単純な動作を行う命令が多く、実際のコードでは定型の組み合わせがたくさん出現します。

例えばローカル変数 i1 を加算する処理は以下のようなバイトコードの組み合わせになり、 WebAssembly では似たようなバイトコードの並びがたくさん出現します。

  local.get $i    ;; ローカル変数 $i の値をスタックに push
  i32.const 1     ;: 定数 1 をスタックに push
  i32.add         ;; スタックから2つの値を pop して加算した結果をスタックに push
  local.set $i    ;; スタックの値を pop してローカル変数 $i にセット

特に i32.const の直後に i32.add が続くようなスタックに push した値をすぐに pop して加工する組み合わせはひとまとめに処理した方が無駄なメモリアクセスが減って動作効率が向上します。

インタプリタ実装では仕様書で定義されているバイトコードを1つずつ読み込んで実行することしかできませんでしたが、現在のインタプリタは一旦中間命令に変換して実行しているのでインタプリタの動作に必要な新しい中間命令を追加することができます。 そこで、いくつかの定型句に関しては統合してひとつの中間命令 (fused op) に変換し、まとめて実行することで効率化しました。

これによってベンチ上の数値もだいぶ上昇しました。 同様に頻度の高い定型句を統合していけば全体的な動作速度が向上していくと思います。

スレッドのメモリリーク

メモリ管理にはいくつかのレイヤーがありますが、ここでは主に所有権とライフタイムの話になります。

Rust では GC を使わずコンパイラが所有権とライフタイムの管理をするため参照に厳しい制限があることで有名です。 しかし、コンパイラがいくら頑張っても対応できないシチュエーションに対応するため、 RcArc というリファレンスカウントによるスマートポインタもサポートしています。

リファレンスカウント方式のメモリ管理では参照するたびに参照カウンタを1つ増やして参照を保持している全員が所有権を共有し、参照を破棄する際に参照カウンタを1つ減らして0になったら全ての参照が破棄されてオブジェクトのライフタイムが終了して解放されます。 動作が単純で循環参照以外のほとんどのユースケースをカバーできるため多くの場面で同様の手法が使われています。

MYOS ではスレッドのデータを他のスレッドから参照中にスレッドが終了してデータが迷子にならないように Arc を使用しています。

今まで終了処理をあまり真面目に考えていませんでしたが、以前からスレッドの終了時に解放処理がうまく動いていない雰囲気は察していました。 気になって調べてみると、スレッド終了しても誰かがスレッドデータを参照してカウントが0にならないため解放されていませんでした。

自分で自分を消す処理というのは実現不可能なので、 MYOS のスケジューラーは最終的にスレッドステータスの終了フラグを立ててコンテキストスイッチを実行して、コンテキストスイッチ後の後片付け処理の中で終了済みスレッドのデータを解放してもらいます。 この時点で自分で自分の参照を保持していてもスレッドが永久に再開されないので参照も永久に解放されずスレッドのメモリリークが発生します。

コンテキストスイッチをするためにはスレッドのコンテキストデータにアクセスするためにスレッドデータの参照が必要です。 通常の場合はコンテキストスイッチが終わると参照が解放されますが、スレッドが終了するときは先述のように自分自身のスレッドデータへの参照を保持したまま最期のコンテキストスイッチするので解放されません。

また、スレッドからランタイムのインスタンスを取得する Scheduler::current_personality() でも Personality の参照を保持している間はスレッドを間接的に参照して保持しているので、この中でスレッドを終了するとスレッドが解放されません。

そもそも、現在実行中のスレッド自身のスレッドデータがもしも解放されてしまったら現在のスレッドを参照する様々な機能が動作しなくなるし、次回のコンテキストスイッチも実行できずにシステムがクラッシュしてしまうので、スケジューラー内のスレッドプールがスレッドを保持していて絶対に解放されることがありません。 つまり、現在実行中のスレッドが自分自身への参照で参照カウントする必要性がありません。

ということで参照カウントしないようにスレッドの参照を取得する機能を追加しました。 これによってスレッド終了時に Drop が呼び出されるようになって単純なアプリではスレッドのメモリリークは解消されたと思います。

しかし、複雑なアプリではまだメモリリークがありました。 アプリをロードだけして実際には実行しないような実験をしてもリークすることがあったので、色々な場面に細かいメモリリークが潜んでいるようでさらに調査が必要です。

また、メモリリークとはちょっと違いますが、現在のページアロケーターはメモリを解放してもフリーリストに戻す処理が未実装なので、メモリリークを起こさないアプリでも何度も起動しているとそのうちフリーエリアが枯渇する問題があります。この辺もそのうち改良していきたいです。

メモリリーク先生の戦いはこれからだ!

MYOS のウィンドウのつくりかた

MYOS/TOE のアプリでウィンドウを作るところを少し詳しく見てみましょう。

※ 執筆時点のバージョンの TOE をもとに記述しています。まだ API 安定化してないのでバージョンごとに細かい違いがあったり MYOS と TOE の間でも微妙に違うことがあります。

アプリから WindowBuilder

まずはアプリの中で WindowBuilder のメソッドでウィンドウの情報を設定して最後に build() を呼び出すと Windowインスタンスが作られます。

    let window = WindowBuilder::new()
        .size(Size::new(200, 200))
        .bg_color(WindowColor::BLACK)
        .build("bball");

WindowBuilder の中身

myoslib::window::WindowBuilder はウィンドウの作成に必要なパラメータをまとめたビルダーパターンと呼ばれる構造体のひとつで、現在は以下のような内容になっています。

pub struct WindowBuilder {
    size: Size,
    bg_color: WindowColor,
    flag: u32,
}

ウィンドウを作るにはいろいろな情報が必要なので、 myoslib::window::WindowBuilder.build() の中で self にまとめた情報をもとに os_new_window2() を呼び出してウィンドウハンドルを取得し、ウィンドウハンドルから Windowインスタンスを作成します。

pub fn build(self, title: &str) -> Window {
    let handle = WindowHandle(os_new_window2(
        title,
        self.size.width() as usize,
        self.size.height() as usize,
        self.bg_color.0 as usize,
        self.flag as usize,
    ));
    Window { handle }
}

システムコール

myoslib::syscall::os_new_window2() の中ではパラメータの型を調整して svc6() を呼び出します。

pub fn os_new_window2(
    title: &str,
    width: usize,
    height: usize,
    bg_color: usize,
    flag: usize,
) -> usize {
    unsafe {
        svc6(
            Function::NewWindow,
            title.as_ptr() as usize,
            title.len(),
            width,
            height,
            bg_color,
            flag,
        )
    }
}

svc6myoslib::syscall の中で定義された外部関数で、 WebAssembly の外の世界の関数を呼び出すことを意味します。

#[link(wasm_import_module = "megos-canary")]
extern "C" {
    pub fn svc0(_: Function) -> usize;
    (中略)
    pub fn svc6(_: Function, _: usize, _: usize, _: usize, _: usize, _: usize, _: usize) -> usize;
}

myosabi::svc::Function::NewWindowenum6 番と定義されているので svc6 の最初の引数はコンパイル結果のバイナリでは数値 6 になります。

pub enum Function {
    (中略)
    NewWindow = 6,
    (中略)
}

壮大な茶番

実はここまでのほとんどの処理はリリースビルドでは Rust の優れた最適化によって消滅します。(デバッグビルドなら残るかもしれません) 以下のように svc6 に直接引数を渡して呼び出すようにコンパイルされて、 WindowBuilder の構造体をゴニョゴニョするくだりは通常のアプリではビルド結果に残りません。

 0000ac: 41 06                      | i32.const 6
 0000ae: 41 80 80 82 80 00          | i32.const 32768
 0000b4: 41 05                      | i32.const 5
 0000b6: 41 c8 01                   | i32.const 200
 0000b9: 41 c8 01                   | i32.const 200
 0000bc: 41 00                      | i32.const 0
 0000be: 41 00                      | i32.const 0
 0000c0: 10 80 80 80 80 00          | call 0 <_ZN7myoslib7syscall4svc617h2ba79744244edc14E>

svc6 は WebAssembly の外の世界にあるので、最終的に svc6 を呼び出す部分だけが残ります。

WebAssembly の外へ

svc6 は WebAssembly のインスタンスを作るときに kernel::rt::megos::arle::ArleBinaryLoader::load() にわたすリゾルバの中で kernel::rt::megos::arle::ArleRuntime::syscall にダイナミックリンクされます。 svc0svc6 の実体は実は全て同じです。

fn load(&mut self, blob: &[u8]) -> Result<(), ()> {
    self.loader
        .load(blob, |mod_name, name, _type_ref| match mod_name {
            ArleRuntime::MOD_NAME => match name {
                "svc0" | "svc1" | "svc2" | "svc3" | "svc4" | "svc5" | "svc6" => {
                    Ok(ArleRuntime::syscall)
                }
                _ => Err(WasmDecodeError::DynamicLinkError),
            },
            _ => Err(WasmDecodeError::DynamicLinkError),
        })
        .map_err(|_| ())
}

ArleRuntime::syscall

kernel::rt::megos::arle::ArleRuntime::syscall は第1引数として WebAssembly モジュールのインスタンス、第2引数として実際に関数呼び出しで渡された引数の配列スライスを受け取ります。

fn syscall(_: &WasmModule, params: &[WasmValue]) -> Result<WasmValue, WasmRuntimeError> {
    Scheduler::current_personality(|personality| match personality.context() {
        PersonalityContext::Arlequin(rt) => rt.dispatch_syscall(&params),
        _ => unreachable!(),
    })
    .unwrap()
}

実際の API 実装ではネイティブのハンドルとアプリ固有のハンドルを仲介したりスレッドに紐付いたデータを管理するためにコンテキスト情報が欲しいので、 kernel::task::scheduler::Scheduler::current_personality() を呼び出して kernel::rt::megos::arle::ArleRuntime のスレッドに紐付いたランタイムインスタンスを取得します。 MYOS/TOE でスレッドにランタイムのインスタンスを紐付ける仕組みを Personality と言います。 ランタイムのインスタンスが取得できたら kernel::rt::megos::arle::ArleRuntime::dispatch_syscall() を呼び出します。

また、ここでやりとりしている WasmValue というのは以下のような enum で WebAssembly のプリミティブの値を型情報と一緒にラッピングしたものです。*1 WasmValue の配列スライスを受け渡すことで実際の関数の引数がどんな型でも同様に扱うことができます。

pub enum WasmValue {
    Empty,
    I32(i32),
    I64(i64),
    F32(f32),
    F64(f64),
}

ArleRuntime::dispatch_syscall

kernel::rt::megos::arle::ArleRuntime::dispatch_syscall() の中では svc6 を呼び出した際の引数のリストをデコードして最初の値を myosabi::svc::Function 型に復元し、 match 文で一致する機能番号を探します。

fn dispatch_syscall(&mut self, params: &[WasmValue]) -> Result<WasmValue, WasmRuntimeError> {
    let mut params = ParamsDecoder::new(params);
    let memory = self.module.memory(0).ok_or(WasmRuntimeError::OutOfMemory)?;
    let func_no = params.get_u32().and_then(|v| {
        svc::Function::try_from(v).map_err(|_| WasmRuntimeError::InvalidParameter)
    })?;

    match func_no {

myosabi::svc::Function::NewWindow が一致したので、残りの引数からネイティブのウィンドウビルダーを呼び出してネイティブのウィンドウハンドルを取得し、アプリ固有のハンドルに変換して最終的に WasmValue::I32 でラッピングしてアプリに返します。

        (中略)
        svc::Function::NewWindow => {
            let title = params.get_string(memory).unwrap_or("");
            let size = params.get_size()?;
        (中略)
            let window = WindowBuilder::new(title)
                .size(size)
                .build();
        (中略)
            self.windows.insert(handle, window);
            return Ok(WasmValue::I32(handle as i32));
        }

ここまで実行してアプリケーションがウィンドウを作成してハンドルを受け取ることができました。

*1:WebAssembly MVP には i32 i64 f32 f64 の数値型と空の5種類のプリミティブ型しか存在しません

wasm ランタイムの高速化

現在の自作 wasm ランタイムはインタプリタ実行しています。

インタプリタJIT

VMエミュレーターの実装方法は大きく分けると2種類あります。 ある程度一気にターゲットの機械語に変換してしまう JIT 方式と、1命令ずつ読み込んで動作を再現するインタプリタ方式です。

インタプリタJIT に比べると明らかに実行速度が劣りますが、いくつかの合理的なメリットもあります。

  • 動作が単純で比較的簡単に実装できる
  • フットプリントが小さい
  • CPUアーキテクチャの依存が少ない

もちろん簡単に実装できるのでこの方法を選択しましたが、結果的に M1 Mac に買い替えても開発効率が落ちなかったし、 MYOS から TOE への移植も比較的スムーズにできたのでトータルではプラスだったと思います。 *1

愚直なインタプリタ

さて、そんなインタプリタ方式の自作 wasm ランタイムですがやっぱり遅いです。 そして明確に遅い理由があります。

wasm はスタックベースのバイトコードを採用しています。 例えば add 命令の動作は仕様書には以下のように定義されています。(add は2項演算命令なので binop に属します。)

f:id:neriring16:20210403235446p:plain

簡単に説明するとパラメータをスタックから pop してきて演算結果をスタックに push しなさいと書かれています。

この動作をほぼそのまま愚直に実装していたのが元の実装になります。 毎回愚直にスタックの pop と push をやってるので遅いのは当たり前です。

さらに問題があるのが分岐命令で、 wasm の分岐命令は block 系の命令でネストされたブロックに対する分岐として動作します。

f:id:neriring16:20210404002516p:plain f:id:neriring16:20210404002525p:plain

ブロックのネストを管理するためにスタックが必要になり、スタックレベルの違うところへ分岐するときはスタックレベルの調整 (unwind) も必要になります。 また、 block 命令に対する分岐はブロックの終端、 loop 命令に対する分岐はブロックの先頭に分岐するなど対象のブロックによって動作が異なり、事前検証しないとブロックの終端位置がわからないので分岐が実装できません。

これらの処理をするため分岐命令は複雑でした。 分岐命令の実装のために事前検証が必須だったのでスタックの調査も同時に行うようにしていました。

そこでひとつ気付きがあります。

事前検証の段階でスタックレベルとブロックのネスト構造がわかるので毎回愚直に操作しなくてもいいのでは?

新しい実装

というわけで、インタプリタをほぼ全面的に書き直して事前検証の段階で必要な情報をまとめた固定長の中間表現に変換してしまうことにしました。

事前検証で各命令のスタックレベルが確定するので value stack は単なる配列として利用し、 block stack は対象ブロックが確定するので廃止して分岐命令は単純に実行位置を変更するだけの命令に簡略化しました。 また、 wasm のバイトコードは LEB128 という可変長エンコードされていてパラメータの取り出しが面倒なところもあったのでそれも固定長に変換しました。

switch 文などの表現に使われる br_table は元のバイトコードに分岐先のテーブルが含まれていて非常に長い命令になるので、テーブルだけ分離して別の場所に確保するようにしました。

ある程度動くようになったので試しにいくつかアプリを実行してみたところ、ベンチの数値が2〜3倍速くなりました!

もう少し速くなりそうと思っていたので現実は厳しいようです。

次のステップ

もう少し高速化の余地はあって、実行速度とデバッグ効率を両立するために全ての命令のエラー処理を見直す必要があります。

また、以前の実装では MVP 仕様の float/double 系以外の全ての命令をサポートしていましたが、一連の変更でサンプルアプリで使われていない一部の命令が原理的に実装困難になったので上手い実装方法を模索中です。

そして、高速化を決意させるきっかけになったサンプルアプリが正しく動作しなくなったので現在調査中です。

*1:逆に言うと現在の開発環境では JIT のテスト実行できないので将来 JIT 実装する時は工夫する必要があります...

Wasm on Wasm

ついに、 WebAssembly の自作エミュレータの上で動く自作 OS の上で自作 WebAssembly ランタイムが動くようになりました 🎉

つまり Wasm on Wasm ですね٩( 'ω' )و

以下に試験的に体験版設置してるので起動してみることができます。

meg-os.org

f:id:neriring16:20210329214942p:plain

もちろん PC98 や FM TOWNS でもなんとなく動きます。

f:id:neriring16:20210329214729p:plain

f:id:neriring16:20210329223029p:plain

基本的には MYOS で実装したものを若干調整して TOE に移植しただけです。最初に移植したときは動くアプリと動かないアプリがあって、調査しようとしたら wasm ランタイムを外部ライブラリに分離して no_std の関係で今まで使えた println! が使えなくなって原因の特定に若干手間取りました。 最終的には、内部で使ってる独自スタッククラスが原因でした。

独自スタックが必要な理由は、 wasm では関数1つ呼び出すたびに複数のスタックが必要になるので個別に確保するのは効率が悪いです。 特に value stack と block stack は事前検証で必要なサイズがわかっています。 *1 そこで、いったん大きめに確保した後で独自クラスの slice として分配してスタックを作っていましたが、環境によってサイズの違う型の計算が間違っていてスタックが重複して破壊されていたようです。 この部分は unsafe な操作を含むので Rust コンパイラくんでも検出できなかったようです

ともあれ、無事に動くようになったのでそろそろ TOE も最初のマイルストーンに到達しそうです。

Wasm on Wasm って一度やってみたかったネタなので、このためだけに3ヶ月くらいがんばりましたヽ(•̀ω•́ )ゝ✧

*1:wasm では分岐命令がネストしたブロックに対して相対的に行われるので、ブロックの構造を事前検証しないと分岐先や value stack の調整ができません

initramfs

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

initrd と initramfs

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

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

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

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

OSZ の initramfs

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

f:id:neriring16:20210327210747p:plain

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

TOE の initramfs

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

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

f:id:neriring16:20210328173741p:plain

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

f:id:neriring16:20210328195447p:plain

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

今後

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

MYOS の起動処理概要

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

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

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

まずはブートローダーが起動します。ブートローダーの細かい動作は本質的ではないのでここでは省略します。 BIOSUEFI から呼び出されて、ハードウェア情報収集、ビデオモードの初期化、カーネルの読み込みなどが終わったら 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() を呼び出し、アプリケーション実行環境をサポートするための BinaryRecognizerPersonality が利用可能になります。 現在の 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 の2種類あります。 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 コマンドレジスタは組になっている2つの 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_startupIDT を設定し、 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:この2つ名前が似ていて紛らわしいですね・・・

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

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

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

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

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

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

f:id:neriring16:20210319222545p:plain

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

f:id:neriring16:20210319230604p:plain

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

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

f:id:neriring16:20210319222405p:plain

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

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

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

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

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

優先順位の逆転 Priority Inversion

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

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

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

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

修正

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

f:id:neriring16:20210319222417p:plain

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