restore process state
プロセスの内部状態を保存して後で復元したい、ということがゲーム開発ではよくあります (いわゆる state save)。チェックポイントから再開みたいな機能の実現の他、あると開発中何かと役に立ちます。定期的に state save しつつ、気になったところがあったら巻き戻して Alcantarea の実行時コード編集で改良、という TAS みたいなやりかたが最近の私の開発スタイルです。
通常は boost::serialization とかを使って必要なデータを serialize する処理を書いてタイトル毎に実装しますが、これをもっと簡単に、汎用的に、できれば既存のプログラムに外部から適用できる形で実現する方法はないか、と夢見た方も多いんじゃないかと思います。これを実現できるかもしれない方法を思いついて、ある程度のところまで成果を出せたので経過を書き残します。
(Virtual Machine 使うのが最も確実な方法ではありますが、大げさすぎるので今回なしの方向で)
汎用 state save は、以下の 3 つを保存して復元できれば実現できそうな気がします。
- メモリの状態
- スレッドの状態
- カーネルオブジェクトの状態
メモリの状態とスレッドのレジスタの状態が完全に再現できればポインタ、プログラムカウンタ、リターンアドレスなどがそのまま有効になり、実行を再開できるはずです。ファイルや mutex などのカーネルオブジェクトも多くの場合復元が必須になるでしょう。
今回は前提として state の有効期限はプロセスの生存期間中のみとします。プロセスを再生成するところまで考慮すると厄介な障害が増えるためです。 基本戦略は対象プロセスに DLL Injection で独自のコードをねじ込み、主要な WinAPI を API hook で乗っ取って復元可能にする独自ルーチンを挟む、というものです。
- メモリの状態
メモリにはモジュール、ヒープ、ページメモリ、スタック、TLS などがあり、それぞれ別の対処が必要です。
・モジュール
メモリにマップされた exe や dll の領域です。プロセスの再生成までやる場合、これの復元が非常に難しいチャレンジになると予想されますが、今回そこは考えません。しかし global 変数や関数内 static 変数なんかはこのモジュール領域内にあるため、これらは保存＆復元が必要になります。
CreateToolhelp32Snapshot(), Module32First(), Module32Next() でロードされている全モジュールの詳細な情報を取得できます。これでモジュールの領域を取得し、VirtualQuery() で順次属性を調べて書き込み可能になってる箇所を探して保存します。
・ヒープ
malloc() や new で動的に確保される領域です。これらが確保する領域のアドレスは予測が難しく、そのままでは正確なメモリレイアウトの復元は困難です。このためちょっとしたハックが必要になります。過去に何度か触れたように、Windows の CRT の malloc() は最終的に HeapAlloc() に行き着きます。なので HeapAlloc() を乗っ取って独自のメモリ管理ルーチンに差し替えれば malloc() を復元可能にできます。
今回の例では、初期化時に巨大な領域を確保してその領域を dlmalloc で管理、保存するときはその領域をまるごと書き出しています。
・ページメモリ
VirtualAlloc() で確保された領域です。ヒープと違ってアドレス指定の確保ができるため、メモリレイアウトの復元は簡単です。
今回の例では VirtualAlloc()/VirtualFree() を hook して領域を記録し、それをまるごと保存＆復元しています。
・スタック
各スレッドのスタック領域で、関数内ローカル変数やリターンアドレスがある領域です。どちらかというとスレッドの状態に属する話です。 GetContext() でスレッドのレジスタの状態を取得でき、esp (x64 なら rsp) がそのスレッドのスタックのどこかを指しているので、そこを VirtualQuery() で調べることでベースアドレスとサイズを取得できます。あとはその領域をまるごと保存するだけです。
スレッドの巡回には CreateToolhelp32Snapshot(), Thread32First(), Thread32Next() を使います。この API は全プロセスの全スレッドを巡回するので、該当スレッドが自身のプロセスに属するかをチェックする必要がある点に注意が必要です。
・TLS
未検証。TlsAlloc() 一族を乗っ取ればなんとかできそうな気がします。fs レジスタから Thread Information Block をたどって直接保存することでも実現できるかもしれません。
- スレッドの状態
スタックの保存についてはメモリの項で触れた通りで、それ以外の状態、レジスタの内容については、GetContext() & SetContext() するだけです。意外と簡単です。
- カーネルオブジェクトの状態
ファイルとか mutex とか socket とか。厄介な部分です。
これらに関しては汎用的な対処法がなく、個別対応が必要になります。関連する API を乗っ取って状態を追跡して復元可能にするための情報を記録。HANDLE 自身も復元可能にする必要があるため、WinAPI が返した HANDLE は直接は見せず、独自に生成＆管理した復元可能な HANDLE を返して翻訳する処理を挟む必要があります。ネットワークやプロセス間通信が絡むと復元は困難を極めると予想されます…。また、DirectX の COM オブジェクトなんかも同じ対応が必要になると思われます。
https://github.com/i-saint/scribble/tree/master/RestoreProcessState
上記解説のメモリとスレッドの保存を実装して、既存プログラムへの外部からの state save & load を限定的ながら実現したのがこちら。メインスレッドのみ状態を保存、メモリはメインモジュール (exe) が扱うメモリのみ状態を保存。カーネルオブジェクトの類は未考慮。
動画は勝手に アスタブリード を実験に使わせていただいたものです。state load 後にサウンドのスレッドのストリーミング処理と思しき部分でクラッシュするという問題があり、対応が大変そうだったため、事前にデバッガでそのスレッドを止めることで強引に回避しています。真面目に対処する場合カーネルオブジェクトまで含めてきちんと面倒を見る必要がありそうです。
カーネルオブジェクトの類が未考慮なので、save -> load の間にテキスチャの破棄とかがあったら死にますし、save/load のタイミングが悪くても死にます。(mutex を lock した直後に load してしまうと dead lock が発生、など) 実用には程遠いですが、運が良ければ機能する可能性がなきにしもあらずです。
主要なカーネルオブジェクトと DirectX あたりまで対応できたら実用の域まで行けそうな気がしますが、たぶん数ヶ月を要する労力が必要な上、本当に可能かどうかも定かではないので今回はここで切り上げました。余裕がある時期が訪れたら再度真剣に検証してみたいところです。
get function by filename and line number
Alcantarea を実装するにあたって、更新する関数を最小限にするため、Visual Studio のテキストエディタの現在位置の関数を取得してその関数だけを更新する必要がありました。この ファイル名と行番号からその位置の関数を取得する という処理が無駄に奥深かったので書き残しておこうと思います。
大きく分けて 2 通りの方法があると思われます。1 つはソースファイルをパースして関数を特定する方法。もう 1 つはデバッグ情報を使ってバイナリから情報を抽出する方法です。以下は実際に検証したアプローチとそのサンプルコードです。
ちなみに、Visual Studio アドインは現在開いてるドキュメントの情報を以下のようにして取得できます。
(TextDocument が必要な情報を大体持っています。ファイルのパスしかりカーソル位置しかり)
DTE dte = (DTE)GetService(typeof(DTE)); TextDocument tdoc = dte.ActiveDocument.Object() as TextDocument;
- TextDocument.Selection.ActivePoint を使う (sample code)
アドインから Visual Studio が保持している情報を使うアプローチです。TextDocument.Selection.ActivePoint に現在位置に関連する情報が入っているのでそれを使います。最もストレートな方法で、大抵はこれで事足りると思われます。現在の Alcantarea はこの方法を用いています。
注意すべき点として、マクロで包まれてる関数とかでたまに取得できないことがあるのと、.sdf ファイル (Intellisense のデータベース) が何らかの理由で読めていない場合に例外が飛んできます。意外と万能ではないという感触です…。
また、ドキュメントに含まれるシンボル群を保持する FileCodeModel なるオブジェクトがあるのですが、こちらには罠があります。宣言が .h にあって定義が .cpp にあるシンボルは、.cpp 側の FileCodeModel には情報がありません。なぜか .h 側にだけあります。
選択範囲に含まれるシンボルを全部更新対象に加える、みたいなことを FileCodeModel に含まれる情報を巡回することで実現したかったのですが、この謎仕様により断念しました。CodeModel 関連は ここ から辿れるドキュメントが参考になります。
他には、VisualAssistX が外部にインターフェースを公開しているようなので、それを使えばより信頼性の高い情報を取得できるかもしれません (未検証)。
- dbghelp の SymEnumLines() を使う (sample code)
デバッグ情報を使うアプローチです。御存知の通り、デバッグ情報 (.pdb) には行情報が含まれています。SymEnumLines() を使うことでこの行情報を巡回できます。
簡単で信頼度も高い方法ですが、Alcantarea 実行中は実行コードは書き換えられる一方でデバッグ情報は変わらないという特殊な状況のため、編集するにつれてズレていくので使えませんでした。
- .obj のデバッグ情報を使う (sample code)
こちらもデバッグ情報を使うアプローチです。.obj ファイルにも当然デバッグ情報が含まれており、行情報もあります。このデバッグ情報をがんばって自力でパースして該当関数を見つけます。
Visual Studio 2005 以降の .obj ファイルのデバッグ情報は CV8 (Code View 8) という形式らしいのですが、これはフォーマットが非公開です。(CV4 は公開されているものの、CV8 はほとんど別物になってる様子)
しかし、誰かが独自に解析して こういうメモ を残してくれています。サンプルコードはこのメモを元に実装したもので、いい感じに機能しているように見えます。
Alcantarea は今後のリリースでこのアプローチに差し替えるかもしれません。また、このメモの情報を元にカスタムデバッガを書けば、編集後もソースコードデバッグできるようにできそうな気がするのでいずれ検証してみたいところです。
Alcantarea
C++ ソースの変更を実行中のプログラムに反映させる Visual Studio アドインをリリースしました。
Alcantarea - A Visual Studio Add-In for Runtime C++ Code Editing
これは DynamicPatcher に改良を加えつつ Visual Studio のアドイン化したもので、既存のプログラムを前準備なしに実行時編集可能にします。Edit and Continue と比べていくつか制限はあるものの、x64 でも最適化が有効なプログラムでも機能するのはゲーム開発で強力に威力を発揮するはずです。
Visual Studio 2013 が x64 の Edit and Continue に対応する、という情報が出て世界中のゲーム開発者が沸き立ち、その後実は .Net しか対応してないことが判明して世界中のゲーム開発者をガッカリの渦に巻き込んだ、という出来事がありましたが、そんな開発者たちにこのアドインが救いの手を差し伸べる…かもしれません。
このアドインを作る過程で得られた知見が色々あるので、後日書き残していこうと思います。
また、今回も告知が遅くなりましたが、冬コミ参加予定です。スペースは 3日目 (31 日) 西た-09b primitive で、予定を変更して上記アドインを 1000 円で頒布します。通常購入と同じく 1 年間のサポート&アップデートを含むライセンスキー付属です。
ここしばらく他に優先してやらないといけないことがあって atomic の開発は休眠状態です…。
それと、しばらく前に DynamicPatcher が Riot Games に採用されるという出来事がありました。
Riot Games は League of Legends のデベロッパであり、League of Legends は最大同時接続数 500 万人を超えて今世界で最も遊ばれているゲームと言われているお化けタイトルです。最も成功した Free-To-Play モデルのゲーム、として言及されることもしばしばあります。
そんなタイトルの開発を自分の黒魔術コードが支えるなんてエンジニア冥利に尽きるってもんです。
runtime member variable editing
x86 勉強会で、clang のソースコード解析機能で class の構造を得て実行時にデータを表示したり編集したりする、という話を聞いて、以前デバッグ情報を使って似たようなことをやろうとしてたのを思い出してちゃんとやってみました。
指定オブジェクトのメンバ変数を巡回して表示する例。
デバッグ情報を使って class のメンバ変数を巡回するのはこの記事やこの記事が参考になります。一見ややこしいですが、実際にやってみるとすぐ慣れます。
型情報を得るにはまず型の名前の文字列を得る必要があります。RTTI が有効であれば typeid(hoge).name() で簡単に得られますが、そうでない場合、virtual 関数を持つ class であれば vftable のシンボル名から得ることができます (実装例)。
RTTI が無効で virtual 関数もない場合は…たぶんユーザーに教えてもらうしかありません。
(追記 2013/09/27: SymEnumSymbols() とかで特定 scope の変数を巡回でき、型名も取れるため、デバッグ情報だけで typeid().name() 相当のことも可能です。実装例)
このメンバ変数巡回を WebDebugMenu に組み込んでみました。
これだけで実行時データ編集できるのはなかなか強力なんじゃないかと思います。
しかし、関数を呼ぶノードは eval の類がないと実行時自動生成は困難で、微妙に痒いところに手が届かない感もあります。可能は可能なので今後の課題です。
あとは シリアライザを自動的に生成 する、というのをやってみました。やってることは __FILE__ で自身の中身を見て特定マクロの箇所にシリアライザのコードを追記する、というものです。
他のアプローチとして、VisualC++ のコンパイラには class や struct の構造を出力するオプションがあります。(/d1reportSingleClassLayout /d1reportAllClassLayout) 型が出ないのがやや残念ですが、デバッグ情報使う以外にこういう選択肢もあります。
$ cl TestMemberNodes.cpp /d1reportSingleClassLayoutTest
class Test size(80):
+---
0 | m_i32
4 | m_f32x4
20 | m_b
| <alignment member> (size=11)
32 | __m128 m_m128
48 | m_charstr
64 | m_pair
+---また、gcc 系のツールチェインでは shinh さんが同じようなことをやっておられます (8 年前に)。
Cookie Clicker
https://github.com/i-saint/scribble/tree/master/CookieClicker
自分の時間を救うために Cookie Clicker の自動連打＆自動 golden cookie クリックツールを作りました。
自動連打は SendInput() しまくるだけですが、golden cookie 探しは結構大変で、Cookie Clicker のウィンドウを探して、GDI 系 API でスクリーンショットを得て、前回探した時から変化した部分を探して…とややこしいことをやっています。(たまに右の building ボタンをクリックしてしまいますが、これは明るくなった時 golden cookie と誤認してしまうためです)
javascript でブラウザの内部状態を得て対処できればよりスマートですが、やり方が分からず断念しました。他の自分の時間を救おうとしてる方が別の解法を編み出してくれることを期待します。
Runtime C++ Editing
x86/x64 最適化勉強会 6 で、実行時 C++ 編集の実装方法について話しました。上はその時の資料です。
私が知ってるいくつかの実装の解説と、DynamicPatcher の実装について解説しています。
あとは最初にこんなもんが必要になるゲーム屋特有の事情についてざっと解説。過去の回で暗号学者の方とかエンコーダを書いてる方の話がすごく興味深かったので、他業種の方がゲーム屋が直面してる問題に興味を持ってもらえたら幸いです。
光成さんによる x86/x64最適化勉強会6 レポート
発表後、shinh さんから SymFromName() の代わりに .map ファイルからシンボル情報を読むアイデアをいただき、実装してみたところ .obj の実行時リンクにかかる時間が大幅に短縮されました。リンクに時間がかかるのが最大の問題だったのが、これでほぼ解決できました。(ありがとうございます)
DynamicPatcher は私自身 atomic 制作で使っていて、boost::serialization で実装した state save/load 機能と組み合わせ、開発モードでゲームを起動すると一定時間置きに自動で state save、改良したい箇所が目についたら遡って一時停止して C++ コードを編集して再開、というサイクルを実現しています。
exception の時は編集するたびにゲームを再起動していたので、当時と比べると大幅な生産力 up です。
raymarching for games
demoscene の世界では近年 raymarching というレンダリング手法がよく用いられています。ポリゴンモデルは使わず、モデルデータは数式の図形としてシェーダコードの中で表現し、pixel shader で図形との距離を求めて可視化していく、というものです。
demoscene (4k/64k intro) の厳しい容量制限の中綺麗な絵を出すために生み出された手法ですが、従来のポリゴンベースの手法では難しい独特の絵を出すことができるという副次的効果があります。
raymarching の代表的な作品群
この手法は PS4 世代以降、小規模ゲーム開発チーム向けの有用なツールになるんじゃないかと考えていて、atomic では試しに背景にこの手法を用いています。以下はその過程や考察です。
まず、raymarching の基本については demoscene.jp の人たちが素晴らしい解説を書いてくれています。
http://www.demoscene.jp/?p=811
raymarching の基本的な図形の式は、iq 氏 (elevated の作者) のサイトにまとめられています。
http://www.iquilezles.org/www/articles/distfunctions/distfunctions.htm
上 2 つを知っていればとりあえず raymarching で絵を出すには十分です。
ついでに、folding や fractal など、より高次のテクニックを知りたい人は Mikael H Christensen 氏の記事が役立ちます。
http://blog.hvidtfeldts.net/index.php/2011/06/distance-estimated-3d-fractals-part-i/
また、shadertoy.com や glslsandbox.com には様々な作品が投稿されています。
atomic の背景は非常に単純で、Box の繰り返しと後処理だけで実現されています。順を追って説明すると以下の様な感じです。
1. 箱を出す & 距離と ray を march した回数に応じて適当に色を足す (WebGL で実行)
これだけだとよくわからん感じですが、XZ 軸方向の 2 次元 Box です。
ray を march した回数というのは、ray が図形に到達するまで (もしくは打ち切られるまで) にかかった step 数で、オブジェクトの輪郭スレスレを通りつつ交差しなかった場合とかに数が多くなります。この数に応じて色を足すと、4k intro でよく見るオブジェクトの輪郭付近が発光してオーラが出てるようなエフェクトを実現できます。
2. 箱を反復させる (WebGL で実行)
平面との and をとって y 方向に空間を作りつつ、折りたたみや mod() で図形を繰り返します。
3. もっと反復させる (WebGL で実行)
いい感じに見えるように調整します。
4. 箱の位置に乱数を加える (WebGL で実行)
面白く見えるようにします。乱数は位置を hash する方式です。位置をベースにした乱数を使う場合、次の step の正確な距離を予測できなくなるため、ray が図形を突き抜けるケースが出てくることに注意が必要です。(手前のちらついてる部分はそれが原因。誤魔化す方法はありそうな気がしますが、うまくいきませんでした)
5. 法線を求め、カメラ->法線の角度が浅いところを光らせる＆輪郭を光らせる (WebGL で実行)
法線は近隣 pixel の位置を求めてその勾配から推測します。普通にライティングしてもいいんですが、かっこよく見えるならそれを最優先です。
6. おなじみ光の溝エフェクト＆走査線効果 (WebGL で実行)
あとはなんでもいいのでかっこよく見えるエフェクトをぶちこみましょう
実際にやってみて得られたのは、超人的なプログラムを書かなくても見せ方次第でそれなりに綺麗に見える絵を出すことはできる、という感触でした。
しかし raymarching にも色々デメリットがあります。モデルの形状の融通の効かなさもなかなかツラいですが、一番問題になるのは、重いことだと思われます。pixel shader の中で図形との距離計算を何十回もやることになるため、図形の複雑さと描画面積に比例してすごい勢いで重くなっていきます。
demoscene の場合、容量制限の都合上シェーダレベル以上の最適化はまず行われませんが、ゲームの場合より高次の最適化を行う余地があります。pixel shader が重くなるのは不可避なので、レンダリング解像度を減らす最適化が効果大です。
この手の最適化として代表的なものに adaptive sampling という手法があります。事前に 1/4 とか 1/16 とかの解像度でレンダリングしておき、高解像度でレンダリングする際、低解像度バッファの近隣 pixel が似たような結果であればそれをそのまま使用、そうでなければ真面目に計算する、というものです。
実際に試してみた図。左: 最適化なし 中央: 最適化あり 右: 1/4 の解像度でレンダリングした領域を赤く表示。品質とのトレードオフになりますが、シーンによっては有用そうな感触です。
他にも、ある程度以上暗いところは低解像度でレンダリングするとか、縦半分の解像度でレンダリングして残り半分は前フレームの結果をインターレースで混ぜて補うとか、ゲーム向けの小細工は色々ありそうな気がします。
また、応用として、deferred 系のレンダリング手法の場合、raymarching で G Buffer だけ書き出してライティングはポリゴンモデルと一括で行う、みたいにすることもできます。raymarching で生成したヘンテコオブジェクトと通常のポリゴンモデルで一貫したライティング処理を行うことができるため、面白い効果を得られるかもしれません。
raymarching のゲームへの応用はまだ前例が少なく、自分も試行錯誤している段階で、成果らしい成果が出せたら今後も経過を書き残していく予定です。
