借り初めのひみつきち

仮ブログです。

QOI 画像ビューワーつくった

最近 QOI (Quite OK Image Format) という新しい画像形式が登場しました。

QOI — The Quite OK Image Format

PDF1 ページに収まる単純な仕様でエンコーダーデコーダーもC言語で数百行と単純で高速ですが、PNGよりやや圧縮率が悪い程度というトレードオフがなかなか優秀なフォーマットです。

アルゴリズム上、写真などの自然画よりもイラスト画像に効果があり、デコーダーの軽さも考慮するとアセット画像に向いてそうです。

さて、新しい画像形式が生まれた時に問題となるのが、サポートするソフトが少ない問題です。

QOI 形式の画像は本格的な画像編集はあまり求められておらず、内容の確認とフォーマットの変換ができれば十分だと思います。 公式サイトにはいくつかツールが紹介されていますが、動作環境が微妙だったりビルドがうまく通らなかったりしてぼくの環境では簡単に使えるツールがありませんでした。

幸い Rust のライブラリはすでにいくつか提供されているようなので WebAssembly でラッピングしてウェブアプリにしてみました。

https://nerry.jp/image-viewer/

github.com

構造としては IMG タグで読み込んだ画像を Canvas に描画する簡単なウェブアプリに QOI フォーマットの入出力機能を追加した感じです。 この方法だと PNG の入出力はブラウザに任せればいいので相互変換が簡単に実装できます。

これで QOI 画像の表示や変換が簡単にできるようになりました。

ちなみに myos の最新版でも QOI 形式に対応していて一部の画像リソースは QOI 形式になっています。

誰も教えてくれない AMD64 と Intel64 の違い (ページング編)

Intel64 は AMD64 を参考に実装したので、9割以上のアプリケーションにおいて概ね互換性があります。 一方、船頭多くしてなんとやら、両社の政治的な思惑などが絡んで意図的に非互換になっている部分があったり、細部の互換性をとることができていない部分があったりします。

AMD64 と Intel64 の代表的な差異は色々なところでまとめられているのですぐ見つけることができますが、中には一般に知られていない差異もあります。

以前 EFER.LMA の差異を発見したことがありましたが、今回新しい差異を発見したのでここにまとめます。

neriring.hatenablog.jp

事件編

myos は、現代では Intel64 PC の方が手に入りやすいので Intel64 機で開発されてきました。 そして、ある程度動くようになってきたので家にあった唯一の AMD64 機でも動作確認をすることにしました。

普段使ってないマシンなので埃を落としていざ電源オン、 BIOS のかっこいいロゴが表示された後で myos を起動しているメッセージが一瞬表示されましたが、すぐに暗転して次の瞬間また BIOS のかっこいいロゴが表示されました。

これは起動時に何か問題が起きて強制再起動しているようですね・・・。

犯人さがし

OS を開発している初期の段階では何か設定を間違って例外が発生することが稀によくあります。 一方、そもそも例外処理がうまく動いてないのでそのまま CPU がシャットダウン状態になって再起動してしまうケースが非常によくあります。

このような場合、どうやってデバッグすればいいでしょうか?

答えは簡単、まずは適当なところに無限ループを仕込んで起動テスト。 無事に動作が止まれば無限ループのところまでは動いてるので OK、 無限ループする前に再起動したらループより前に問題があることがわかります。 そして、無限ループを仕込む場所を少しずつ移動しながら起動テストを繰り返すことで問題が起きている場所を絞り込むことができます。

これで、カーネルの序盤にページングを初期化してる部分が怪しいところまでは絞れました。

他の機種では動いているのでページ設定の大枠に問題はないはずです。 しかし、実際にはページ設定で問題が起きています。 このような場合、ページングの拡張属性の使い方が正しくない可能性が高いです。

システム起動時には RECURSIVE PAGE TABLE AREA (ページテーブル操作用に再帰しているページテーブル領域) と DIRECT MAPPING AREA (物理メモリに直接アクセスするための領域) の設定を行っています。

ここで怪しい拡張属性を考えてみると、どちらもシステム全体からアクセスする領域なので GLOBAL 属性を付与していました。 *1 試しに GLOBAL を設定していたビットを0に変えてビルドしてみます。なんと、起動しました。

GLOBAL 属性は i386 よりも後 (P6 世代) になって追加された属性で、 CR4 レジスタの PGE ビットを有効にしないと使えません。 そこで、 CR4 レジスタの設定が間違っているかと思いブートローダーで明示的に CR4.PGE ビットを立てるコードを追加してみました。

しかし、予想に反してこの修正を加えても起動しませんでした。

Global ビットが絡んでいることは明白なのに、これは一体どういうことでしょうか。

解決編

では、分厚いマニュアルを開いて確認してみましょう。

Global ビットはページテーブルエントリの bit8 に存在します。

f:id:neriring16:20210925180451p:plain

AMD64 では PML4E の bit8 は Must be Zero と定義されています。

f:id:neriring16:20210925180544p:plain

一方、 Intel64 では PML4E の bit8 は Ignored と定義されています。

f:id:neriring16:20210925180639p:plain

もっと詳しくマニュアルを見てみると、 Global Page 属性は PTE, PDE, PDPTE のみでサポートされ、 PML4E ではサポートされていないことがわかります。

f:id:neriring16:20210925180809p:plain

また、 PML4E 以外でも Global ビットが実際に有効になるのは最下位レベルページテーブルエントリ (4KBページなら PTE、2MBページなら PDE) のみで、それ以外のレベルのページテーブルエントリ内の Global ビットは無視されます。

f:id:neriring16:20210925182349p:plain

つまり、 PML4E の Global に相当するビットはもともと存在しないビットなので PML4E に Global ビットを設定しようとしているコードがそもそも間違いです。 両者の仕様の違いにより、 Intel64 では無視され、 AMD64 では不正なビットでページフォルトが発生するという現象が起きていました。

このように PTE, PDE, PDPTE, PML4E は基本的な考え方やビット配置は概ね共通していますが、微妙にサポートされている機能に差異があります。 また、 Intel64 では無視されても AMD64 では厳しくチェックされるといった具合に、両者の細かい挙動は異なるようです。

後日談

PML4E に Global ビットを設定していたコードを修正して無事起動するようになりました。

しかし、起動しても USB をうまく認識せず myos を操作することができませんでした。 Windows を起動してデバイスマネージャで確認してみると、なんと USB デバイスは全部 EHCI に繋がっていました。解散。

*1:追記: Recursive Area に Global を設定すると CR3 フラッシュで消せなくなってめんどくさいことになるのでそもそも使うべきではないと思います。

Compound Device と Composite Device

Compound と Composite の違い、わかりますか?

このふたつの単語、綴りも似ていますが意味も似ていて、ニュアンスの違いを説明しろと言われると正直ちょっと自信がないです。

USB 規格には Compound DeviceComposite Device という2種類の用語が存在していてそれぞれ別の意味を持ちます。

Compound Device

Compound Device は一言で言うと USB ハブを内蔵したデバイスで、 USB ハブとセットになったキーボードやドックなどが該当します。

Compound Device は物理的にはひとつのデバイスですが、内部的には USB HUB とそれにぶら下がった複数のデバイスとして USB バスのツリー上で認識され、それぞれの内蔵デバイスは独立した USB アドレスを持ちます。

Compound Device は USB ハブの Hub Descriptor 内の wHubCharacteristics にある2ビット目のフラグで判別することができます。

f:id:neriring16:20210920224040p:plain

このビットが1の場合、単純に独立した USB ハブではなく、 Hub Descriptor の後半の方にある DeviceRemovable で non-removable と指定されたビットに該当するポートにあるデバイスとまとめた Compound Device ということになります。

f:id:neriring16:20210920224050p:plain

Composite Device

Composite Device は一言で言うと複数の機能 (Interface) を持った USB デバイスで、トラックパッドと一体化したキーボードなどが該当します。 ちなみに、これにさらに USB ハブが付いてる場合は Compound Device でありかつ Composite Device ということになります。

Composite Device は USB バス上でも単一のアドレスを持った単一のデバイスとして認識され、複数の Interface で複数の機能を提供します。

HID と Composite Device

ここから先はちょっと複雑な話になりますが、キーボードやマウスは USB HID という規格のデバイスになります。

HID 規格は人間と機械の間にある全てのデバイスを定義しようとしたとても壮大な規格で、キーボードやマウス以外にもさまざまなカテゴリのデバイスが定義されています。 そして、 HID に対応したデバイスはレポートと Usage によってさまざまな機能を提供しています。 そのため、 HID デバイスは HID という単一の Interface だけでも複数の機能を提供するものがあります。

よくあるキーボードで通常の文字キー以外に、電源関係、マルチメディア操作、その他のショートカットなどに対応しているものがあります。 実はこれらのキーは HID 規格上では別々の Usage として定義されています。

ほとんどの USB キーボードは HID Boot キーボードというクラスに属していて、いくつか定型の決まり事があります。 そして、 HID Boot キーボードクラスの仕様だけでは先述のようなキーは仲間外れになってしまうので、キーボードと別の HID Interface として定義してる場合と、キーボードを含めてごちゃ混ぜの独自の汎用 HID デバイスとして定義している場合があります。

このようなデバイスWindows PC に接続してデバイスマネージャを見てみると、複数の謎の HID デバイスとして認識されることがありますが、先述のように単一の Interface の場合と複数の Interface に分かれている本当の意味での Composite Device の場合があります。

HID デバイスはレポートの自由度が高すぎる反面、複雑すぎて単一機能のデバイスなのか複数機能のデバイスなのかを判断するのがとても難しいです。 HID デバイスの場合は Interface が1つでも本質的には Composite Device とあまり変わらないということがわかるかと思います。

余談ですが、 HID デバイスには実際には提供していない機能を含んだ定型文のようなレポートディスクリプタを返すデバイスが時々存在します。 おそらくいくつかの機能をまとめた便利チップみたいなものがあってそれをカスタマイズして使っているんだと思いますが、キーボードの形をしていないのにキーボードの定義が含まれていたり、マウスの機能がないのにマウスの定義が含まれていたり、どこにも存在しないキーの定義が含まれていることがあるのでレポートディスクリプタをあまり信用してはいけないかも知れません。

今月の myos

このシリーズ、ほぼ月1になっていたのでタイトルを変更します。

SIMD と Lazy FPU save / restore

CPU の高速化はいくつかの歴史を経て、近年の CPU は「ひとつの命令で多数のデータを処理する」命令をサポートしています。 これを一般に SIMD (Single Instruction, Multiple Data) と言います。 画像処理などは大量のデータに対して同じ手順を繰り返す操作が多いため SIMD 命令が効果的です。

初期の x86 プロセッサには SIMD 命令がありませんでしたが、現代の x86 プロセッサには SSE という拡張機能SIMD に対応しています。 SSE は専用のレジスタを使うので、コンテキストスイッチの際に正しく退避処理を行わないと他のスレッドとレジスタの内容が混ざってしまいます。 SSE は長い x86 の歴史の中では比較的後期に新設された機能であり、通常の処理において大抵の場合 SSE は必須ではありません。

このような経緯のため SSE など x86SIMD 機能はデフォルトで無効になっていて、 OS 側で機能を有効にしないとアプリ側から自由に使えないようになっています。*1

また、大量のデータを扱う性質上、 SIMDレジスタは汎用レジスタに比べて容量も多く退避のコストが上昇します。 基本的な処理ではほとんど使わない上に汎用レジスタより容量の多い SSE レジスタコンテキストスイッチのたびに退避処理を行うと性能低下の恐れがあります。

そこで昔の人は考えました。

コンテキストスイッチのたびに一旦 SIMD ユニットを無効化し、実際に SIMD 命令を実行しようとしたら例外でトラップし、例外が発生するまでレジスタの退避復元処理を遅延させることで SIMD 命令を使わないスレッドにおけるコンテキストスイッチのオーバーヘッドを減らそう。 いわゆる Lazy FPU context switch や Lazy FPU save/restore などと呼ばれる高速化技法です。

しかし、時が経つとこの高速化技法はあまり役に立たなくなってきました。

  • SSE が普及し、昔は汎用命令で処理していた何気ない処理(2つのまとまった 64bit 値をコピーする場合など)にも SSE を使うコンパイラが出てきた。
  • マルチコアが普及してコンテキストスイッチの際に同じ CPU に復元されるとは限らなくなり、レジスタの退避・復元を遅延する効果が薄れた。
  • Lazy FPU save/restore と投機実行を併用したセキュリティ攻撃が発見された。
  • SIMD レジスタの退避・復元処理の速度ペナルティは Intel も認識しており、 AVX 以降では負荷を軽減する新命令が追加された。

現代では Lazy FPU save/restore は使わない方が良いとされています。

ここまでが SIMD を取り巻く歴史となります。

myos では SSE レジスタの退避処理による割り込みやコンテキストスイッチの速度低下への懸念から、当初カーネルのコア部分では SSE を非使用とし、 UI やアプリで必要になったら順次解放していくという方向で開発を進めていました。 しかし、現在のビルド環境ではカーネルのコア部分と UI 部分が同じバイナリに含まれているために ABI を切り替えることが難しく、完全に禁止するか、完全に解放するかという2択の状況が続いていました。

いずれは解放する予定だったし Lazy FPU save/restore のような仕組みを新しく考えるのも面倒になってきたので、試しに全てのコンテキストスイッチで SSE レジスタの退避と復帰処理を実装してみました。

方法は簡単で、元々コンテキストを保存する領域は SSE のレジスタを保存できるように準備していたので、コンテキストスイッチレジスタを切り替える部分に FXSAVEFXRSTOR を追加します。また、新しいスレッドを作成する部分で FPU や SSE の初期値を設定するコードも追加しました。

    fninit
    pxor xmm0, xmm0
    pxor xmm1, xmm1
    pxor xmm2, xmm2
    pxor xmm3, xmm3
    pxor xmm4, xmm4
    pxor xmm5, xmm5
    pxor xmm6, xmm6
    pxor xmm7, xmm7
    pxor xmm8, xmm8
    pxor xmm9, xmm9
    pxor xmm10, xmm10
    pxor xmm11, xmm11
    pxor xmm12, xmm12
    pxor xmm13, xmm13
    pxor xmm14, xmm14
    pxor xmm15, xmm15

そして画像処理で SSE の最適化を有効になるように調整すると、バイナリサイズは肥大化してしまうものの、実機では速度向上が見られました。 懸念していたほどの速度低下も起きず、 Lazy FPU save/restore のような複雑な仕組みも不要になってシンプルになり、画像処理も速くなったのでこれでいくことに決まりました。

これによって機種によってはゲームベンチのFPSが300を超えるようになりました。速いっていいですね。

Universal Serial Bus

myos は一言で言うと moe を Rust で再実装した OS です。 開発言語が違うので単純な比較はできませんが、主要な機能の再実装は完了していると思います。 最後に残った機能は USB でした。

というわけで実装しました。

f:id:neriring16:20210913160425p:plain

USB のクラスドライバは USB バスと通信して結果を変換して他のところに転送するだけのようなものが多く、単純にそのまま実装すると通信用のスレッド数がものすごく増えることになります。 同じコントローラーに対する USB コマンドは同時実行できないので排他処理が必要であること、ドライバの実行時間の大半は待ち時間であることなどを考慮すると、各ドライバがそれぞれスレッドを利用するのはあまり好ましくないので、それぞれのドライバは Rust の async 機能で並列化しています。

また、それぞれのクラスドライバは moe の時代から進化しています。

HID は moe の時代にはキーボードとマウスの最低限の機能だけをサポートした boot プロトコルしか対応していませんでした。 myos では boot プロトコルを廃止してレポートプロトコルの方を使うようになったので boot プロトコルを提供していないトラックパッドや一体型のキーボードなどもだいたい使えるようになりました。 本来の HID 規格はキーボードとマウスだけでなく人間と機器の間でやりとりをするあらゆるデバイスを取り込もうとした超巨大な規格で膨大な種類の Usage が定義されていて全て対応しようとするととても大変ですが、現在の HID ドライバは若干手抜きをしていてキーボードとマウスの入力以外の機能は考慮していません。

USB 2.0 ハブは moe の時代から対応していて起動時に刺さっているとうまくデバイスを認識できない不具合がありましたが修正されました。 USB 3.0 ハブは未対応だったので対応中ですがまだうまく動いていません。

XInput は moe の時代にはとりあえず値が読み出せるだけで使い道がありませんでした。 myos ではゲーム API からアクセスできるようになったので市販の XInput ゲームパッドを接続してゲームを操作することができます。 DirectInput 形式への対応は未定です。

Curiosity

以上により、現在のバージョンをもって moe から myos への移行は完全に完了したと思っています。

いつまでも名前が5月だと締まらないので、 これからは新バージョンのコードネーム「Curiosity」として次のマイルストーンに向けて開発していこうと思います。

*1:ただし、 UEFI から起動した場合は x64 UEFI の用件に SSE が含まれているので有効の状態で起動すると思います

今週の MYOS 🧚‍♀️

MYOS でも簡単なゲームを動かせそうになってきたので準備をします。

多くのゲームは画面内をキャラクターが動き回りますが、キャラクターを描画する時は背景との重ね合わせ処理が必要になりますし、キャラクターが移動するときはそれに加えて元いた場所の背景を復元しないと画面がぐちゃぐちゃになります。それらを自力で管理するのは結構大変です。

レトロゲームフレームワーク 🧚‍♀️

古き良きレトロゲーム機は CPU もメモリも貧弱でしたが、スプライト 🧚‍♀️ という機能を持っていました。 これは背景とは別に小さい画像オブジェクトを重ねることができる機能で、先述のめんどくさい重ね合わせ処理をハードウェアで処理してくれます。 この機能のため、レトロゲーム機は貧弱なCPU能力と少ないメモリでもキャラクターが画面中を動き回るゲームを実現することができました。

というわけで、 MYOS にも似たような機能を実装します。

f:id:neriring16:20210821155043p:plain

ベンチマーク用のサンプルアプリを起動するとウィンドウの中をボールが動き回ります。

ちなみに現在のゲームAPIハローワールドがこんな感じのコードになります。

#![no_main]
#![no_std]

use megoslib::game::v1::prelude::*;

#[no_mangle]
fn _start() {
    let presenter = GameWindow::new("hello", Size::new(128, 64));
    presenter
        .screen()
        .draw_string(Point::new(0, 3), 0, b"Hello, world!");
    loop {
        presenter.sync();
    }
}

f:id:neriring16:20210818025101p:plain

これに少し加えて以下のようにすると、文字がスクロールします。簡単ですね。 *1

#![no_main]
#![no_std]

use megoslib::game::v1::prelude::*;

#[no_mangle]
fn _start() {
    let presenter = GameWindow::new("hello", Size::new(128, 64));
    presenter
        .screen()
        .draw_string(Point::new(0, 3), b"Hello, world!");
    loop {
        presenter.sync();

        presenter.screen().control_mut().scroll_x -= 1;
        presenter.set_needs_display();
    }
}

ゲーム API を有効化すると、 wasm のアプリと OS の間で複数回のデータやり取りで描画が遅くなるのを防ぐため、ゲーム画面描画専用の固定メモリマップが割り当てられます。

まだ仕様は完全に確定していませんが、よくあるレトロゲーム機の画面仕様と似たような仕様となっており、解像度や色数に同じような制限があるものの、プログラムサイズ数KB〜数10KBの規模でレトロゲームが簡単に実装できることを目標にしています。 将来はもう少し制限を緩くした version 2 以降も実装できたらいいなという願いを込めて、現在実装しているゲーム API には v1 というプレフィックスをつけています。

ゲームウィンドウ高速化

ゲーム API を実装する過程で気付きがありました。

以前検証した単純な計算ループのベンチでは qemu より実機の方が1桁くらい速かったですが、スプライトのデモに FPS 表示を付けてみると、なんと qemu より実機の方が遅いです。 そして、ウィンドウを画面端に移動して描画部分を極限まで小さくすると FPS 表示が跳ね上がることを確認できます。

スプライトはウィンドウの状態に関係なく内部バッファに対して描画されますが、内部バッファからウィンドウへの描画は実際の画面の表示領域に依存します。 画面端にウィンドウを表示すると、クリッピングによってウィンドウの描画範囲が狭くなり、描画するビットマップの面積も小さくなって転送量が減ります。 画面端にウィンドウを移動してFPSが跳ね上がるということは、スプライト自体の描画よりもウィンドウの描画に時間がかかっていることになります。

MYOS もその先祖の MOE も、半透明のウィンドウどうしの重ね合わせ描画をサポートするために、すべてのウィンドウ描画はいったんバックバッファで合成した後で実際の画面に転送します。 MOE の時代のウィンドウは透過ウィンドウと不透明ウィンドウの2種類のウィンドウが存在し、不透明ウィンドウは高速化のために重ね合わせ処理の一部を省略して描画していました。 MYOS では基本的に全てのウィンドウに影がつくため、影の合成のために不透明ウィンドウという概念が消滅しました。*2 つまり、全てのウィンドウはその内容が不透明であったとしても毎回後ろのウィンドウを描画した後アルファブレンド合成していたのです。

それは遅くなるわけです。

ウィンドウの形が角丸が基本になって矩形ではなくなってしまったり影を描画しなくてはいけない関係上、今後も完全な不透明ウィンドウは MYOS には基本的に存在しないでしょう。 一方、ウィンドウの一部分を再描画する場合、内容が不透明であれば自分より背面のウィンドウは描画しなくて良いはずです。

というわけで、一部の条件を満たしたウィンドウの部分再描画でアルファブレンドしないようにしたところ、 qemuFPS が倍以上に跳ね上がりました。 今まで半分以上ウィンドウ再描画の時間だったということになります。

一方、実機の速度向上は限定的でした。

実機でもウィンドウを端に寄せて描画範囲を狭くすると FPS が跳ね上がるので描画が遅いことがわかりますが、メインメモリ内で完了するアルファブレンド処理はさほど負荷ではなく、実際に画面に描画する VRAM 転送する処理が一番遅いということなのでしょう。

エミュレーターは一般に実機より遅いと思われがちですが、 VRAM アクセスは特別で、エミュレーターの中からは遅い VRAM に直接アクセスできなかったり表示時の転送がいい感じに効率化されているので実機より速くなることも多いです。

*1:前半ではスプライトの話をしたいたのに、実はこのハローワールドはスプライト機能を一切使っていないことに気づいてしまいました。要望があればそのうちもう少し詳しいサンプルプログラムを作って解説するかもしれません。

*2:実際には一番後ろにあるデスクトップに相当するウィンドウはそれ以上後ろに何もないので不透明ウィンドウが完全に消滅したわけではないですが

今週の MYOS

wasm-strip

MYOS のアプリケーションは WebAssembly 形式に対応していて、現在は Rust で開発する前提でライブラリの整備を進めています。 しかしどうやら Rust で WebAssembly を生成すると Release ビルドにも関わらずバイナリにデバッグ情報のようなものが付与されているようです。 現在のアプリは数KB程度のサンプルが多いですが、実際の内容の半分以上はデバッグ情報になっていることも多いです。 このデバッグセクションは仕様がよくわからず、自作 wasm ランタイムにとっては完全にゴミ情報なので削除してサイズ節約したいです。

そこで、デバッグ情報を削除できるユーティリティーを作りました。 内容は簡単で、 wasm ファイルを読み込んでセクションを順番にパースして通常のセクションはそのままデータとして残し、 Custom セクションは実行に直接関係ないデータなので削除し、最後に残ったデータだけを結合して出力します。 wasm ファイルの構造は複数のセクションが並んでいる構造で、各セクションの中身は直接パースせずただのバイナリとして扱う場合は結構簡単に加工できます。

なお、 Custom セクションのうち、 name セクションだけはデバッグ情報ほどサイズが大きくなく残した方が有益と判断したので、現在の MYOS の Makefile では name セクションを残すオプションを指定しています。

実際のファイル内容にはおそらくリンクのために冗長な LEB128 エンコードで表現されているデータも含まれているので、その辺をパースして圧縮すればもう少しファイルを小さくできそうですが、想定される作業量の割には削減できるデータ量がそこまでないので見送りになりました。

name セクション対応

前の節で触れたように、 WebAssembly には name というカスタムセクションが存在します。 WebAssembly は全ての関数はインデックスで扱い、 export されていない関数は番号でしか判別できません。 多くの場合は高級言語コンパイルして実行するので、関数名を番号で表示されてもどの関数のことかわかりません。

しかし、 name セクションがある場合は export していなくてもシンボルの名前がわかるようになります。 ということで、実行エラーが発生した時に関数名も表示できるように対応しました。

f:id:neriring16:20210724030921p:plain

実際のバイナリ上の関数名はほとんどの場合マングルされるのでソース上の関数名と比べるとよくわからない呪文が付属したよくわからない長い名前になってしまいますが、番号だけ表示されるよりは若干わかりやすくなった気がします。

その他の細かい改良

そのほかにも WebAssembly の細かい調整をしてパフォーマンスが向上した気がしますが、ベンチに使っている qemu が時々何の前触れもなくいきなり実行速度が2〜3倍になったり戻ったりするので実際の速度がよくわからなくなってしまいました・・・

今週の MYOS

今週というタイトルなのに最後の更新何週間前だったっけ?という最近の MYOS 界隈のトピックです。

スケジューラキュー

一般にマルチタスク OS のスケジューラには実行待機中のスレッドを管理するためのキューがあります。 このキューは全てのプロセッサコアから同時に読み書きする可能性があるため非常に高度な排他制御が必要になります。

MYOS の開発初期に最も悩んだのもこのスケジューラキューの実装で、最終的に一旦自前実装を諦めて既存のわりと定評のあるらしい外部ライブラリを使うことにしました。 数ヶ月前はこれで安定して動いていたと思うのですが、最近また動作が怪しくなってきました。 しばらく動作しているとキューからデータを引き出す部分で止まって無限ループしているようです。

ロックフリーアルゴリズムというのはアトミック操作の組み合わせでデータを保証します。 当然書き込みもいくつかのアトミック操作の組み合わせを行いますが、稀にこれからデータを書き込む印をつけたまま実際の書き込みが終わる前にプリエンプションが実行され、スケジューラーが次に実行するスレッドを決めるためにキューを読み取る際に書き込み完了マークがつくまで待ち続ける、しかしそのスレッドはすでにプリエンプションされているので書き込みは永遠に完了しないという無限ループを発見しました。

キューの出し入れを割り込み禁止にすることで、キューに関するほとんどの問題は解決しました。

クリティカルな操作をするときは割り込みを禁止しましょう。

以前より安定してきたので自作のキューも使い始めてますが、やはりまだ時々止まってしまう現象を確認していて詳細不明です。

フォントレンダラと直線アルゴリズム

MYOS は現在 Hershey という簡易的なベクタフォントに対応しています。 このフォントは頂点のリストだけが提供されるので頂点の間に直線を描画するだけで簡単に利用できます。

ベクタフォントの常として、ある程度のサイズを下回るサイズで描画しようとするとあまり綺麗に描画できなくなります。 そこで今までの実装はサイズが倍のバッファに拡大描画した後で縮小して画面に描画していました。 しかし、フォントによってはあまり綺麗に描画できていませんでした。

これまで直線の描画はブレゼンハムと呼ばれる有名なアルゴリズムを利用していました。 ブレゼンハムのアルゴリズムは X が1増加するときに Y が 1 変化するかたまは変化しないのどちらかを判別して描画していくアルゴリズムで、高速に描画できる代わりに座標の変化が整数の近似値で丸められるので射線がガタガタに描画されます。

元々ガタガタの線を拡大縮小しても綺麗に描画できるはずがありません。そこで座標を小数で扱って射線も滑らかに描画できるアルゴリズムに変更しました。

以前より描画結果が良好になりました。

角丸ウィンドウ

MYOS は、その先祖となった moe の時代から角丸の矩形を描画する機能を持っていました。 そして、マウスカーソルのように矩形ではない図形を重ね合わせる機能も元々持っていました。 角丸ウィンドウを実現できそうな気がしますが、ひとつ問題がありました。影です。

MYOS のウィンドウの影は内部的にはウィンドウの矩形の周りに当たり判定のない半透明の枠線として描画する方法で実現していました。 処理が単純で高速ですが、この方法では矩形以外の影を描画できません。

そこでウィンドウ本体と別のビットマップを用意し、ウィンドウ本体のビットマップの透明度を基準にぼかしをかけて影を生成するように変更しました。

影の形が自由になったのでウィンドウの形を矩形に限定しなくても描画できるようになりました。

f:id:neriring16:20210711155418p:plain

ウィンドウの自由度が上がったので、角丸ついでにタイトルバーのデザインも少し変更してみました。

いかがでしたか?

これからも MYOS の活躍にご期待ください。