テストスイートの美しさに導かれて

テストスイートの美しさに導かれて

去年の夏に出版した レイヴンの独立した実装です。 Uxn CPU そして
ヴァラバラ調整者。要するに、これは 架空のコンピューター クロスプラットフォームの移植性を考慮して設計されており、それを対象とするプログラムは、この仕様を実装する任意のプラットフォームで実行できます。

これが私の実装です。
猫時計のデモ:

今週初めに、親切な寄稿者が
少し
PR システムの動作を改善するために 画像ビューア。彼らはまた、システムのパフォーマンスを次のように称賛しました。

この修正により、svitlyna は uxn11 よりもほぼ 50% 高速に動作すると言えます。これは AMD64 上での動作であり、これは最適化されたアセンブリなしで動作していることを意味します。本当に感動しました！

嬉しいお言葉をいただき、PRを見直す気力が高まりました！ 2024 年の 7 月以来コードに触れていなかったので、理解するまでに少し時間がかかりました。私は以前、システムに深く没頭しながらアドホック テストを行っていました。数か月後に戻ってきたとき、コードに触れて新しい問題が発生していないと確信を持ち続けるのは困難でした。

長い週末をかけて準備をしました インフラストラクチャー この自信のなさを和らげるために、それについてお話したいと思います。その一部はテーブル ステーク (PR での CI テスト) ですが、さらにいくつかの珍しいトリック (ファジングと静的パニック防止) もあります。

彼らはCIです

これは非常に基本的なものです。プル リクエストで実行する Github Actions ジョブを設定しました。退屈させません
YAML ファイル全体ですが、典型的な一連のチェックを実行します。

• すべてのネイティブ プラットフォーム (macOS、Linux、Windows) での構築とテスト
• WebAssembly ビルドがエラーなしで完了することを確認します
• すべてのプラットフォームで Clippy を実行する
• コードが次であることを確認してください。 rustfmt クリーン

ここで二つの驚きがありました。最初に驚いたのは、Github の Windows ランナーの悲惨な状況でした。Windows ランナーは Mac や Linux ランナーよりも 10 倍近く遅かったです。

ブルースカイに文句を言う
これは一般的な問題であることが明らかになったので、ここで何か間違ったことをしているとは思いません。

2番目の驚きは、 ubuntu-24.04-arm ランナーは非常に信頼できませんでした！たとえば、これは
クリップ的なセグメンテーション違反 (?!)。ジョブの再実行は成功します – そして
aarch64-unknown-linux-gnu です
ティア1
ターゲット – だから、私はジョブランナーに過失があることにお金を注ぎます。

ARM ランナーは非常に新しく、エントリーしたばかりです。
「パブリックプレビュー」 ほんの 2 週間前だったので、そのターゲットを無効にして次に進みました。

実際のスナップショットテスト

Varvara の仕様には次のものが含まれます。 Screen デバイスを使用すると、ウィンドウ内にピクセルを描画できます。全体の自動描画をサポートしているため、これは驚くほど複雑なデバイスです。
スプライト (このプラットフォームが
NESからインスピレーションを得た）。

システムを一定のサイクル数実行し、画面の状態をキャプチャして、リポジトリに保存されている正常なイメージと比較する自動テストを追加しました。画像が同一であればテストは合格し、そうでない場合は視覚的な比較で不合格となります。

システムをさらに活用するために、テストでは実行中にマウスとキーボードの操作も実行されます。最初にこれらのインタラクションを追加したとき、マウスとキーボードによってシステムの視覚的な状態が変化したため、いくつかのテストが失敗しました。これは、レンダリングの失敗を示す良いデモンストレーションであることがわかりました (クリックすると最大の解像度が表示されます)。

この状況のように、新しいイメージが実際に正しい場合は、以前の良好なイメージを削除すると、次回の実行時に再生成されます。

パニックがないことを静的に証明する

前回の記事で、VM の実装は次のとおりであると自慢しました。
パニックから完全に解放される。残念ながら、実行可能ファイルを逆アセンブルし、実装全体をスキャンして、このプロパティを手動でチェックする必要がありました。 Uxn::run。

堅牢化プロセスの一環として、次のトリックを借りました。
no-panic

コンパイル時にパニックが発生していないことを証明します。この戦略は私にとっては目新しいものでした (ただし、Rust コミュニティではよく知られていました)。そのため、それがどのようなものかを示しましょう。

#[inline(never)]
pub fn div_no_panic(data: &[u8]) {
    // Define a struct which calls a non-existent function when dropped
    struct NoPanic;
    extern "C" {
        #[link_name = "div_may_panic"]
        fn trigger() -> !;
    }
    impl ::core::ops::Drop for NoPanic {
        fn drop(&mut self) {
            unsafe {
                trigger();
            }
        }
    }

    // Build an instance of that struct
    let guard = NoPanic;

    // Perform the possibly-panicking operations
    let mut ram = UxnRam::new();
    let mut vm = Uxn::new(&mut ram, Backend::Interpreter);
    let _ = vm.reset(data);
    let pc = 0x100;
    for d in data {
        vm.stack.push(Value::Byte(*d));
        vm.ret.push(Value::Byte(*d));
    }
    vm.div(pc);

    // If we didn't panic, then forget the guard (skipping its drop function)
    core::mem::forget(guard);
}

Rust でのパニックの実行 「くつろぐ」: パニックが発生すると、すべてのオブジェクトに対してデストラクターが呼び出されます。このコードでは、 NoPanic を呼び出します extern "C" 名前付き関数 div_may_panic。残念ながら、この機能は存在しません。

通常、リンカーは外部関数を解決できないため、これはリンク時にエラーで失敗します。ただし、パニック パスがない場合は、一連の最適化が可能になります。

• パニックが起こらなければ、 core::mem::forget(guard) いつも呼ばれます
• もし私たちがいつも forget 警備員、それでは NoPanic::drop 決して呼ばれない
• もし NoPanic::drop 決して呼び出されない場合、バイナリ内に存在する必要はありません
• もし NoPanic::drop が含まれていない場合、リンクすることはありません div_may_panic

つまり、コードがパニックになる可能性があるとコンパイラーが判断した場合、これはリンカー エラーで失敗します。テストには誤検知が発生する可能性があります。コンパイラの攻撃性が低いため、最適化なしでのビルドは失敗します。そのため、これらのテストはリリース モードでのみビルドします。

の div_no_panic 関数をインスタンス化する必要があります。これを簡単なテストで行います。

#[test]
fn div() {
    let data = std::hint::black_box(&[]);
    div_no_panic(data);
}

このテストは、コンパイラーが最適化で賢くなりすぎることも防ぎます。 black_box オブジェクトを関数に組み込むことは、VM が次のコマンドで初期化される可能性があることを意味します。 任意の値 データとスタックのために。

なしで black_box、コンパイラはデータとスタックがすべてゼロであることに気づくほど賢いです。積極的なインライン化と組み合わせると、「この操作はどの状態の VM でもパニックできない」ではなく、「この操作はゼロ初期化された VM でパニックできない」というはるかに弱い条件をチェックすることになります。

例として、除算は次のように定義されます。 a.checked_div(b).unwrap_or(0)。代わりに書いたら a / b、次のような場合にパニックになる可能性があります。 b == 0。案の定、これによりリンカー エラーが発生します。

= note: ld: Undefined symbols:
    _div_may_panic, referenced from:
        raven_uxn::test::no_panic::div::no_panic::h04b990e75bc12e0c in raven_uxn-f210ab979edece52.raven_uxn.e5df65eeb70bd9b5-cgu.03.rcgu.o
        raven_uxn::test::no_panic::div::no_panic::h686d8f2cdb0db704 in raven_uxn-f210ab979edece52.raven_uxn.e5df65eeb70bd9b5-cgu.03.rcgu.o
        raven_uxn::test::no_panic::div::no_panic::h8383a3b65857da3c in raven_uxn-f210ab979edece52.raven_uxn.e5df65eeb70bd9b5-cgu.03.rcgu.o
        raven_uxn::test::no_panic::div::no_panic::h87538c337282e2a2 in raven_uxn-f210ab979edece52.raven_uxn.e5df65eeb70bd9b5-cgu.03.rcgu.o
        raven_uxn::test::no_panic::div::no_panic::hcf7507c29ba59298 in raven_uxn-f210ab979edece52.raven_uxn.e5df65eeb70bd9b5-cgu.03.rcgu.o
  clang: error: linker command failed with exit code 1 (use -v to see invocation)

決して美しいわけではありませんが、十分に機能します。カスタム リンク名によって、どの操作が失敗の原因であるかがわかるため、追跡が容易になります。

結局書いてしまった
マクロの束
すべてのオペコード関数がパニックに陥っていないことを確認します。理論的には、テストするだけで済みました
Uxn::opに基づいてオペコード関数にディスパッチします。 u8 口論;残念ながら、たとえ個々のオペコード関数がパニックに陥っていないとしても、オプティマイザは同じことを証明できませんでした。 Uxn::op。コンパイラの気まぐれに左右されるのは、このトリックの決定的な欠点です。

コンパイル時にパニックフリーのコードをチェックすることは、やや珍しいツールですが、高保証システムには役立ちます。職場では、同僚と私は
同様の戦略
組み込みシステムの重要な部分にパニックが存在しないことを主張するため。 スーパーバイザーのタスク。

ファジング

Raven の Uxn CPU 実装には 2 つの種類があります。

• ベースライン インタプリタは 100% 安全な Rust で書かれており、(上で説明したように) パニックフリーが保証されています。
• 「ネイティブ」インタプリタは、手書きアセンブリを使用して約 30% 高速に実行されます。を参照してください。 「コンパイラを倒す」 これがどのように機能するかの説明のために

これら 2 つの実装 すべき どちらも Uxn 仕様に忠実であり、同じように動作します。ただし、テストするときは、
スヴィトリーナ （画像ビューア）、それらが分岐していることがわかりました。ベースライン インタプリタは正常に機能しましたが、ネイティブ インタプリタは画像をロードできませんでした。

この失敗により、猫のサンプル画像を鑑賞できなくなりました。これは明らかに耐えられない状況です。

ベースラインとネイティブの通訳者との乖離は、私にとって常に恐れであり、すでに懸念していました。
何百行もの単体テスト
それらの間で比較します。これらの単体テストでは、単純な命令シーケンスを実行し、両方のインタプリタが同じ状態になることを確認しました。

明らかにそれらでは十分ではなかったので、より大きなハンマーを取り出しました。
cargo-fuzz

で ファズテスト、システムにランダムな入力を提供し、システムが正しく動作するかどうかを確認します。十分に高度なファジング ライブラリは、(デバッグ インフラストラクチャを使用して) 実際にコード パスを監視し、入力を賢く変更してプログラムの状態空間を完全に探索します。

私のインタプリタの場合、ランダム入力は ROM であり、バイトのスライスにすぎません。正確性チェックでは、プログラム終了後にベースライン インタプリタとネイティブ インタプリタの間でマシンの状態が比較されます。 「マシン状態」は、RAM (64 KiB)、データ、およびリターン スタック (u8 インデックスと各 256 バイト）、およびデバイス メモリ（256 バイト）。 66306 バイトはすべて同一でなければなりません。

ファザーが無限ループを発見 (そして行き詰まり) するのは簡単なので、テスト ハーネスも最大命令数に達した後に救済されます。

ファザーが次のようなケースを見つけたとき しません 一致すると、テスト ハーネスは失敗した入力を保存し、オペコード シーケンスを整形して表示します。たとえば、次のように言うかもしれません。 ADDk SFT2kr SWP2r EQU2r SWP2r LDR2kr SFT2kr 失敗する。 cargo fuzz tmin 次に、テストケースを次のように縮小します EQU2r SWP2r。

ファザーが見つかりました 3つのオペコード 通訳者が異なる結果を出した場合。最初の 2 つは、私のアセンブリ実装における単純なタイプミスでした。

--- a/raven-uxn/src/native/aarch64.s
+++ b/raven-uxn/src/native/aarch64.s
@@ -874,9 +874,9 @@
_NIP2r:
    ldrb w9, [x2, x3]
    rpop
    ldrb w10, [x2, x3]
    rpop
    strb w9, [x2, x3]
-    sub x11, x1, #1
+    sub x11, x3, #1
     and x11, x11, #0xff
-    strb w10, [x2, x31]
+    strb w10, [x2, x11]
     next

@@ -885,7 +885,7 @@
 _SWP2r:
    ldrb w11, [x2, x3]  ; get the top byte
    rpeek w12, x9, 2    ; get the second-from-top byte
    strb w11, [x2, x9]  ; do the swap!
    strb w12, [x2, x3]

     rpeek w11, x9, 1
-    rpeek w12, x10, 2
+    rpeek w12, x10, 3

     strb w11, [x2, x10]
     strb w12, [x2, x9]

しかし、3番目の矛盾は、 面白いというのは、アセンブリでは正しくても、Rust では間違っていたからです。

の SFT opcode はスタックから 1 バイトを読み取り、それを 2 つのニブル (それぞれ 4 ビット) に分割します。次に、スタックから別のバイトを読み取り、それを右にシフトし (最初のニブルによって制御されます)、次に左にシフトします (2 番目のニブルによって制御されます)。これは、2 のべき乗の除算、乗算、下位ビットのマスキングを行うための汎用命令です。

Rustでは次のように実装しました。

    #[inline]
    pub fn sft(&mut self, pc: u16) {
        let shift = self.stack.pop_byte();
        let shr = u32::from(shift & 0xF);
        let shl = u32::from(shift >> 4);
        let v = self.stack.pop_byte();
        self.stack.push(v.wrapping_shr(shr).wrapping_shl(shl));
    }

目が惹かれるかもしれません wrapping_shr そして wrapping_shl;何が問題なのか
and >>?整数をその幅を超えてシフトすることは違法であるため、これはパニックを排除するための私の戦略の一部でした。

たとえば、計算したい 1u8 ? Right to jail, right away.
15u16 >> 18?信じられないかもしれませんが、刑務所です。当社には世界最高の数値演算子がいます。 刑務所のせいで。

(衒学的に言えば、これはデバッグ ビルドではパニックになり、リリース ビルドでは未定義の動作になります。 すべき オンにする overflow-checks リリースビルドではそこでもパニックを引き起こす)

意図した動作を確認するために、リファレンス実装を調べました。

case 0x1f: /* SFT  */
    t=T;n=N;
    SET(2,-1) T = n >> (t & 0xf) > 4);
    break;

この場合、 n です Uint16、最大シフトは 15 なので、これはすべて合法です (万歳!)。さらに重要なのは、それがセマンティクスを定義することです。右シフトが 8 ビットを超える場合はゼロをシフトインし、左シフト時にオーバーフローしたビットを破棄する必要があります。

これが私です 考え とやっていた wrapping_shr そして wrapping_shl。残念ながら、これらの関数名の「ラッピング」は シフト量、シフトされた値ではありません。具体的には、シフト量が最大有効シフト量よりも大きい場合、シフト量内の無効ビットがマスクされる。

(これについて混乱しているのは私だけではありません)

判明したのは、 unbounded_shl そして unbounded_shr 望ましいセマンティクスを持っていますが、
まだ実験的で夜間のみ。それまでの間、次を使用して式を書くことができます checked シフト:

    v.checked_shr(shr).unwrap_or(0).checked_shl(shl).unwrap_or(0)

組み立て時に使用していたのは、 wすべてのオペランドに対して -size レジスタ (32 ビット) を使用しているため、すでに正しい動作をしていました。

_SFT:
    ldrb w10, [x0, x1] ; load the shift amount
    pop                ; pop the shift amount from the stack
    ldrb w11, [x0, x1] ; load the value to be shifted
    lsr w12, w10, 4    ; calculate left shift amount
    and w10, w10, #0xf ; calculate right shift amount
    lsr w11, w11, w10  ; do the right shift
    lsl w11, w11, w12  ; do the left shift
    strb w11, [x0, x1] ; write the value back
    next

これら 3 つのオペコードを修正したので、8 スレッドでファザーを 15 ～ 20 分間実行しました。私のラップトップが届きました とても暖かいしかし、それ以上の問題は見つかりませんでした。

まとめ

レイヴンについては当面の計画はありませんが、次に触るつもりなら、よりしっかりとした基礎から始めるつもりです。たとえば、ファズ テストは、私 (または他の誰か!) がテストに貢献できることを意味します。 x86-64 比較的信頼できるアセンブリ バックエンド!

ソフトウェアは決して完璧ではありませんし、1 日の時間は限られていますが、この小さなプロジェクトを厳密なエンジニアリングの縮図に磨き上げることにやりがいを感じました。堅牢で正しいシステムを作成できるツールとインフラストラクチャに感謝しています。Rust、 cargo fuzz / libFuzzer、 平 （ため息をつく) Github アクション。

私のベースライン インタプリタは現在、(1) 100% 安全な Rust で書かれており、(2) 入力に関係なくパニックにならないことが保証されており、(3) C のリファレンス実装よりも最大 50% 高速です。さらに良いことに、2/3これらのプロパティの一部はコンパイル時に保証され、CI でチェックされるため、後退することはありません。

最後に、この記事のタイトルは、
レナード・コーエンの曲への言及時間をかける価値は十分にあります。