これはKAZOONの不定期日記(チラシの裏)の2017年版です.下に行くほど新しいです. 2017/1/26 とある問題の顛末 今日の記事は,自作していた Ruby の C 拡張のとある問題を解決した顛末を備忘録として記すものである. C 拡張で,あるクラスを作成していた. このクラスは,あるインスタンスAのリソースを,別のインスタンスBが参照する機能を有していた. これにより,無駄なコピーを抑制したり,インスタンスBを介して間接的にインスタンスAを破壊的に書き換えたりを可能としていた. ところで,このリソースの実体はインスタンスAが保持しているから,インスタンスBが存在する限りインスタンスAは GC にかかってはならない. これは,インスタンスBのマーク関数において,rb_gc_mark(インスタンスA) とすれば良い. 他方,Bを介したAの書き換えなどの関係から,デバッグ等の用途のために,インスタンスAからみて,誰かから参照されているかどうかも知りたかった. そのため,インスタンスAにも,インスタンスBから参照されていることを記憶するための Array を用意した. インスタンスAは,複数のオブジェクトから参照される場合があるため,そのすべてを記憶するために,コンテナが必要だったのである. この Array を,以下ではインスタンスA.referencerとよぶことにしよう. しかし,これには問題が生じる.この「誰から参照されているか」を示す referencer を,伸縮自在で便利な Ruby の Array としたため, インスタンスAのマーク関数において rb_gc_mark(referencer) とする必要がある. rb_gc_mark は再帰的に作用するため,Array の要素であるインスタンスBは,referencer から常に参照されているのである. すると,インスタンスBがもはや不要になった場合でも,インスタンスAの referencer が参照しているせいで GC に回収されなくなってしまうのである. このようなときに利用する概念に「弱い参照」があり,Ruby にも標準添付ライブラリ weakref の WeakRef クラスがある. Arrayを [WeakRef(インスタンスB)] とすることで,この referencer からインスタンスBがマークされることを抑制できるのである. しかし,これだけでは不十分で,インスタンスBが削除されても,referencer は [WeakRef(参照先はもうない)] という状態で残ってしまう. こんな「WeakRef(参照先はもうない)」がいつまでも残るのは無駄であるから,適切に除去して referencer を [] に変えたい. そのために,ObjectSpace.define_finalizer で,インスタンスBから削除されるとき, referencer から WeakRef(インスタンスB) を取り除く手続きを登録しておく,という方法がある. その実装が問題だったのである. ObjectSpace.define_finalizer で登録された手続きは,実は Ruby スクリプト本文とは非同期に実行される. すなわち,スクリプト本文を停止して,GC のマーキングが実行され,スクリプト本文の実行が再開された後, この再開されたスクリプト本文の実行に並列して GC のスイープ作業と,ObjectSpace.define_finalizer 手続きが実行されるのである. ところで,referencer は,別のインスタンスCからインスタンスAのリソースを新たに参照した場合, [WeakRef(インスタンスB), WeakRef(インスタンスC)] に書き換える必要がある. ここに,[WeakRef(インスタンスB)] を [] に書き換える処理と, [WeakRef(インスタンスB), WeakRef(インスタンスC)] に書き換える処理が衝突するおそれがあるのである. このようなケースでは,mutex を使って排他処理とするのが常道であるが,いくつか問題があった. まず,素直に排他処理を実装したところ,(恐らく)デッドロックが生じた. 恐らく,ObjectSpace.define_finalizer で登録された手続きとスクリプト本文は GVL によって排他的に処理されるが, 一つの手続きの実行中にはスレッドが切り替わらず,アトミックに処理されるようになっており,したがって, [WeakRef(インスタンスB), WeakRef(インスタンスC)] に書き換えるためのロック中に, [] に書き換える処理が走ろうとした場合にデッドロックに陥ったのだと思われる. また,mutex の処理は単純に重く,referencer を書き換える処理は比較的頻繁に行われるため,性能が大幅に低下した. しばらく(やや無自覚に)この問題を無視して走らせていたが,時々起こった原因不明の Aborted は恐らくこれによるのだろう. 更に,「referencer から WeakRef(インスタンスB) を取り除く手続き」は, referencer のサイズが膨大であるときに,とても重い処理になるという問題があった. Array の仕様ではこの取り除く処理は,「削除されない要素を含むArrayを新たに生成して置き換える」という処理であり, 本質的にサイズに比例したオーダーがかかる. また,一度に多くのオブジェクトが削除されたとき,WeakRefを一つずつ削除するという処理は極めて非効率なのである. 本質的には,GCが終わった直後のタイミングに,各 referencer をクリーンアップするとするのがよいのだろうが,そのようにはできない. これらの問題を解決するために,ObjectSpace.define_finalizer を使用せず, referencer を参照するとき,必要に応じてクリーンアップすることにした. 「referencer から WeakRef(インスタンスB) を取り除く手続き」がとてつもなく重いだけでなく, ObjectSpace.define_finalizer そのものもやや重い処理であり,実行時間が大幅に短縮された. ただ,現状では GC に連動して任意の手続きを実行する機能はないため「必要に応じて」が適切には処理されていない. 「referencer が参照されるたび」にするとやや頻度が大きすぎるし,そうしてもなおメモリリークが残る. なお,インスタンスBがインスタンスAの参照を必要としなくなった場合, GC を待たずにユーザの指示で参照を除去する仕組みを導入し,referencer が膨大になることそのものを抑制する仕組みは導入した. 2017/1/27 ObjectSpace.define_finalizer WeakRef と ObjectSpace.define_finalizer の組み合わせは http://qiita.com/umanoda/items/3ceff00aae2309e4f9ba で紹介されているが,いくつか問題がある. ObjectSpace はクラスじゃなくてモジュールだとか, ObjectSpace#define_finalizer じゃなくて ObjectSpace.define_finalizer だとかの些細な間違いもあるが, 最大の間違いはこの方法で WeakRef::RefError を抑制できるとしているところである. 昨日述べたように,Ruby の GC は lazy sweep が採用されており,finalizer の実行は,本文と非同期で行われる. すなわち,weakref の参照先が死んでから,finalizer が走って weakref が除去されるまでに, 本文側で weakref を触って WeakRef::RefError が発生する可能性がある. もう一つの不安要素はこの非同期性に伴う衝突の可能性である. 幾つか試した範囲では,明示的に排他処理しないことによるエラーは発生させられなかったが, finalizer の内部で Mutex#lock をしようとすると # が発生する.やはり finalizer はアトミックで,デッドロックの原因となるようである. ちなみに Mutex#try_lock は可能だが,ロックできるまで待機しようとすると当然デッドロックとなる. 昔は Array#each 実行中にもとの配列を変更してクラッシュさせるなどがあったようだが, その辺が改善されているためか,非同期に触ることによるクラッシュも, Ruby 側から触っている限りはあまり起こらないようである. 実行効率を考えても finalizer 側で weakref を削除するよりも, weakref を保持する側で(必要に応じて)生存性をチェックし, 死んだ weakref を削除する機構を組み込むべきであると思われる. 願わくば,sweep が一通り完了したタイミングで実行すべきコードを, ObjectSpace.define_finalizer や Kernel.#at_exit のように登録する仕組みを Ruby 側に用意してもらいたいところである. ユーザー側で現状可能な対処としては,明示的に GC.start(immediate_sweep:true) してクリーンアップしてあげることである. なお,C 側からは GC のマークフェイズをマーク関数の被呼び出しで知ることができるが, マーク関数でマーク以外のことをやるのはやはり問題があるようで,なんとも痛し痒しである. 2017/7/27 バグフィックス顛末記 Ruby の C 拡張において,Aborted(コアダンプ) とだけ表示されて死に,[BUG] すら現れないという深刻なバグを抱えていた. どう見てもメモリ管理まわりのバグであるが,GC.disable としても GC.stress=true としても挙動は変わらず, そもそもの再現性が低く,原因箇所の特定に非常に苦労していた. 今にして思えば,[BUG] が出ず,GC との関連も低そうという時点で,メモリの独自管理箇所まわりのバグであるとあたりをつけるべきであった. このバグには長い間悩まされていたが,先日再現率の高いコードを発見し,原因箇所の絞込が急速に進んだ. 絞込の過程において,二重freeかそれに類するものである可能性が高まった. 意図的に free を除去し,メモリリークを起こすと再現しないことと, 故意に二重 free を発生させると同様に [BUG] なしの Aborted で落ちることが確認されたのだ. その後,絞込を進めたところ,独自の線形リストでメモリ管理をしている部分の実行が,Aborted の必要条件であることがわかった. この箇所は結構複雑な処理を行っており,実装には大層悩んだもので,読み直すのも大変な箇所だった. その時点でバグをはらみやすいとも言えるのだが,再チェックが億劫になっていたのも事実だった. 結論から言えば,線形リストから特定のノードを解放し,新たなノードを挿入する箇所に,深刻なバグが潜んでいた. 線形リストの要素がソート済みである状態を維持するために,中間ノードを削除し,中間に新たなノードを挿入するような実装となっていた. ここで,削除箇所,挿入箇所を走査により特定してから,ノードの削除&解放,新ノードの確保&挿入という順に処理していた. ところが,削除解放するノードと,挿入箇所を示すためのマーカーノードが同一となり, 解放したメモリを読み込んで,そこに新たなノードを挿入し,そこに保存したデータを利用するというバグバグしい実装となってしまっていたのだ. この線形リストは頻繁に利用するものであり,Aborted が低確率でしか発生しなかったのは奇跡とも言える酷いバグであった. 解放したメモリを読み込んでいる時点で,すべての動作は未定義であり,「正しく二重free」となっていたのかは確認していない. 教訓としては, ・メモリ管理はやはり大変なので手を出すのは大変だ. ・[BUG] が出ないってことは Ruby と関係ないところでバグってる可能性が高い. ・読み返すのが億劫なほど複雑な箇所は,やはりバグが潜みやすい. などなど.なお,ここまで盛大なバグを仕込んだ箇所について,パフォーマンスを測っていないのはどう考えてもおかしいのでなんとかしよう. 2017/10/28 更新履歴 リンク集から一部デッドリンクを削除または Webarchive へのリンクに切り替え. ゲームリストも同様の処理.一部適当なリンク先がないのでデッドのまま. すでに申請してくる人はいなくなっているが,ランキングのスコア募集を正式に停止. また,前からまとめようと思っていたお気に入りのやる夫スレ,ニコニコ動画投稿者のリストを作成. 「このサイトについて」から辿れる. 2017/11/20 更新履歴 Firefox Quantum への自動更新が行われ,完膚なきまでに過去のものとなった拡張まとめのページを削除することにした. 時代の変遷への追従が大変なので,新バージョン向けのページは作らない. 2017/12/5 更新履歴 プレーンテキストの文字エンコーディングをすべてUTF-8に変更した. ただしアーカイブ内のテキストファイルはその限りではない.