mono Bug 463323, 475962 について調べてみた&動的なメソッド呼び出しの実装を追いかけてみた
最近 C# なコードを仕事でも使う縁に恵まれているのだが、そこで mono の Delegate.DynamicInvoke 関連で興味深いバグがあると聞いたので、調べてみた。また、せっかくなので Delegate.DynamicInvoke や MethodInfo.Invoke などに端を発するメソッド呼び出しの処理が、mono 内部でどのようにして処理されてゆくのかを追いかけてみた。
ref: Bug 463323 – Bug with delegates to dynamic methods
ref: Bug 475962 – exception thrown from CreateDelegate () when compiling Expression returning a delegate
後者(bug 475962)は前者(bug 463323)の調査過程で出た別のバグで、今(2009/03/19)は前者は Closed で後者は New 状態である。
Bug 475962 について
まず軽い方である 475962 について触れる。こちらは、以下のコードを gmcs でコンパイルするとおかしくなるという話である。
Expression<System.Func<Program, Action>> action = (d => d.testFunc); var t = action.Compile(); Program p = new Program(); // ここで System.ArgumentException: method argument length mismatch t(p);
これは、Bugzilla の Comment #4 にも書いた*1とおり、gmcs がラムダ式
d => d.testFunc
を
delegate(Program d){ return (Action)Delegate.CreateDelegate( typeof(Action), null, // ここが d になるはず ... ); }
という風に誤ってコンパイルしてしまうのが原因のようである。
ちなみに、csc.exe でコンパイルすると、.net だろうと mono だろうと動くバイナリを得られることからも、これは C# のソースコードから ExpressionTree を生成するコンパイル処理におけるバグであると分かる(と筆者は考えたので bugzilla に書いてみたのであった)。
ので、csc.exe を使うなり、手で ExpressionTree を書くなりすれば問題ないはずである。
これについては、機会があればパーサやコードジェネレータも読んでみたいとは思う。が、本題はこちらではないのである。
Bug 463323
こちらは、再現可能性が低かったりで苦労されていたようだが、要するに動的に生成した Delegate について DynamicInvoke すると、希に失敗することがあるという話である。
Bug 463323 Comment #9 の原因と解決
この Bug はすでに fixed になっているのだが、その原因については Comment #9 に記述がある。
その記述によると、mono には "invoke wrapper" なるものがあり、その invoke wrappers は
- pointers to methods (first cache)
- method signatures (second cache)
の二つでキャッシュされるそうである。
ここで、dynamic method に対する "invoke wrapper" を考える。すると、
- 元の dynamic method が free された
- ことなる signature を持つ dynamic method が same memory location に配置された
という二つを満たした時に、"invoke wrapper" の想定している method signature と、pointer to methods の指している先のメソッドの method signature が等しくなくなる。
ここで、Bug 463323 のコメントで挙げられている
- CheckMethodArguments からの ArgumentException
- ArgumentException: Can not assign a ...
- ArgumentException: method argument length mismatch
- MissingMethodException: No constructor found
らは、確かに上の説で説明が付くのである。
この説を受けて、r126958 では、dynamic method が free された際に、二つのキャッシュをクリアするようになったそうである。
r126958 で治した旨を述べている Comment #21 に
Assemblies are not unloadable, and before net 2.0, neither were methods, lots of code was written assuming this
とある通り、アセンブリやその中にある(dynamic でない)メソッドが unload されないことを前提にしていたのが、dynamic で破棄可能なメソッドという物が入ったことによるバグ、という後知恵で見ればありがちに思えるものだった、とのことである。
ちなみにこの修正は今のところ trunk にしか入っていないが、
The relevant patches have been backported to the 2.4 branch.
とあり、また
We're hoping to release Mono 2.4 RC3 as the final, so only show stopper critical / blocker bugs will be considered for fixes.
な Mono 2.4 RC 3 が 2009/03/17 に出ていることから、もうすぐ出るであろう Mono 2.4 ではこのバグは治っているはずである。
また、Mono 2.4 や svn 上のコードを使わない場合、
- 動的に Compile したコード(free されうるコード)を
- Delegate として取得して
- それを DynamicInvoke する
といった風に、動的なメソッド + ダイナミックな呼び出し という 2 条件が重ならなければ、原理的に問題にならないはずである。
せっかくだから俺はこのコードのリーディングを選ぶぜ*2
で、後知恵で見れば bugzilla の記述だけでも上記のように説明できてハイ良かったね、で済ませなくもないだろうが、ここは一丁ソースコードを追ってみるとする*3。
ただし、現状では全ての関連コードを洗ったわけではないので、所によってはまだ読んでいないものがある。
自分への宿題 (= 不明な点)
ソースコードの流れ
具体的には、Delegate.DynamicInvoke を起点に、以下のようにコードを探索し、DynamicInvoke がどんなものかを見てみた。なお件のバグの原因だけを見るならば後半だけで十分である。
- Delegate.DynamicInvoke(params object[])
- Delegate.DynamicInvokeImpl (object[])
- Invoke(Object, Object[])
- MonoMethod.Invoke(Object, BindingFlags, Binder, Object[], ClutureInfo)
- ves_icall_InternalInvoke(...)
- mono_runtime_invoke_array(...)
- mono_runtime_invoke(...)
- default_mono_runtime_invoke(...)
- static MonoInvokeFunc default_mono_runtime_invoke
- mono_jit_runtime_invoke(...)
- mono_marshal_get_runtime_invoke(...)
これらは、大まかには以下のようになっている。
- 各種前処理をしながら関数呼び出しが深くなってゆく
- 過程で DynamicInvoke や Invoke、Activator.CreateInstance などや、さらには通常のメソッド呼び出しが合流してゆく
- 最終的には default_mono_runtime_invoke に行き着く
- あらゆるメソッド・コンストラクタの呼び出しがここにたどり着く
- 通常の JIT を使っている場合、これは mono_jit_runtime_invoke に相当する
- mono_jit_runtime_invoke では、以下の二つに分けて IL を生成 + コンパイルする (例外もある)
- 呼び出す対象のメソッドそのもの
- 呼び出す対象を呼び出すための各種処理
- 上で得られた二つ(コンパイル済み)を使うことで、コンパイル済みのメソッドを呼び出す、という処理を実現している
以下に、各部を読み解いた過程のメモ(?)を示す。
mono での NewGuid と RngCryptoServiceProvider
mono において Guid.NewGuid() で Guid がどうやって生成されているのかが気になったので、せっかくソースコードが公開されていることであるし、読んでみた。
また、NewGuid の実装には後述の通り RngCryptoServiceProvider が使われているので、結果として mono における乱数生成機(RNG)の造りも調べることになったという次第。
なお、全部丁寧に解説しようとするとモチベーションが折れるので、気分に応じてのおおざっぱな解説である。
前知識
Guid とは: GUID - Wikipedia
UUID とは: UUID - Wikipedia
Wikipedia を読めば分かるが、UUID や Guid は、
- 管理するサーバーなどなしに、一つのマシンの中だけで簡潔に生成できる
- (現実的な条件下では、ほぼ間違いなく)全世界において一意
という性質があり、Microsoft 関連でないオープンソースソフトウエアなどでも、すでに陰でかなり使われている代物である。
んで、要するに便利な一意 ID なのでもっと使おうよ、と思うのだが、やはり都合の良い話をするからには実装の詳細も知りたいよね、というのがコードを読んだきっかけ。
なお、.net における System.Guid は、GUID という名前だけど実際には UUID 値ならなんでも保持できる(mono なり .net framework なりのソースコードからも分かる)。
ここで、GUID は UUID に含まれる概念で、ある特定の生成方法によって作られた UUID が Guid である。が、実際には UUID なのに Guid と呼んでしまうことも少なくないし、.net framework / mono もその一例なのである。
UUID の生成手法は RFC 4122 に規定があり、おおざっぱに言うと
のどれかである*1。ちなみに、どの手法で生成されたのかは、UUID の先頭の方のビットで分かるようにもなっている。
mono のソースコードの流れ
で、mono での Guid の生成の流れを追っかけてみたのだが、以下に概要を示す。上から順にコードの流れで、付加されているソースコードは mono の svn head へのものである。
- static Guid.NewGuid()
- static RandomNumberGenerator.Create()
- static CryptoConfig.CreateFromName(string)
- RNGCryptoServiceProvider.GetBytes(byte[])
- RngOpen(), RngInitialize(byte), RngGetBytes(IntPtr, byte)
以下では、それぞれについて気になった点などをハイライトしてみた・・・つもりが、実際にはほとんど順をおった解説になってしまった。これだから現実逃避でコードを読むのは(ry
各論の前に: 長くなってしまったので概略
メモ: 自分への宿題 (= 読んだはいいが分からなかった点)
- mono のクラスライブラリ実装で、static readonly による singleton よりも、lock + if なシングルトンが用いられているのはなぜなのでしょう
- mono が libuuid を使わずに独自実装したのはなぜなのでしょう
- 非 Win32 環境の場合、RNGCryptoServiceProvider が AppDomain 単位で lock するのに対して、ファイルデスクリプタはプロセス内で一つ、とスレッドセーフ性*2に問題があるように見えるのは、実際どうなのでしょう
- http://www.linux.or.jp/JM/html/LDP_man-pages/man7/pthreads.7.html によると、read(2) は pthread-safe なようだ。
- むしろ、こうもしつこく lock している理由が気になる。
- 使っているインターフェース(型)のスレッドセーフ性が分からないから、なのかな?*3
*1:正確には他にもあったりするが、どうでもいいので続きは RFC で。
*2:AppDomain セーフ性?
*3:にしても、パフォーマンス上のオーバーヘッドが小さくない気がするのだがどうなのだろう。
コレクション(配列など)のシャッフル
ref: ランダムソート(笑)とは - 西尾泰和のはてなダイアリー
ref: 単純で正しそうなものが正しいとは限らない - Radium Software
ネット上で、配列などのシャッフルについて検索すると、ソートの比較関数に乱数生成機を渡すとか書いてあるのが多いのでなんかどうでも良くなっていたのだが、それについて丁寧に言及しているページ(リンク先)を見つけたので weblog。
一番目のリンク先の内容はともかく、二番目のやつについてはうっかりやってしまいかねないので気をつけないと。
ちなみに、そもそもコレクションのシャッフルについて調べたのは、そのためのユーティリティを SUtlis に置いておいて、何回も書かないで良くしようと思ったため。
なお、上記の二番目のリンク先の内容を元に、IEnumerable を偏りのなくシャッフル(Knuth-Fisher-Yates shuffle algorithm)する拡張メソッドを、C# で書くと以下のようになる。
public static T[] Shuffle<T>(this IEnumerable<T> src, Random rand) { if (rand == null) rand = new Random(); var result = src.ToArray(); for (int i = result.Length - 1; i >= 1; i--) { var n = rand.Next(i + 1); var item = result[i]; result[i] = result[n]; result[n] = item; } return result; }
wikiforme もどきの補足的な機構: 親子関係の補完
ref: WikiForme 0.5 開発裏話 1 - Blog by Sadayuki Furuhashi
補完の発想は↑のリンクにある wikiforme の振る舞いとほぼ同じであるが、リンク先の方法だと(id:saiya_moebius が理解するには)いささか面倒なので、もう少し簡略化してみた。
このやりかたのポイントは、要素の親子関係の規則からグラフを構築して、要素の自動補完は単なる最短経路の探索問題だと見なしてしまう点である。
こうすることで、煩雑な手続きを使わずとも、ダイクストラ法なりを適用するだけという簡潔な方法で木構造の自動補完が出来るはずである。
例: 箇条書き
たとえば、リンク先にもある箇条書き記法を用いて例を作ると、
- 1 - 2 -- 3-1 -- 3-2 - 4
というテキストと、
- ノード: 箇条書き全体(Lv1)
- (割愛)
- ノード: 箇条書きのアイテム(Lv1)
- このノード親になれるノード: 箇条書き全体(Lv1)
- ノードの開始を検出するregex: ^\-
- ノード: 箇条書き全体(Lv2)
- このノード親になれるノード: 箇条書きのアイテム(Lv1)
- ノード: 箇条書きのアイテム(Lv2)
- このノード親になれるノード: 箇条書き全体(Lv2)
- ノードの開始を検出するregex: ^\-\-
という記法の定義が与えられた場合に、
<箇条書き全体(Lv1)> <箇条書きのアイテム(Lv1)>1</箇条書きのアイテム(Lv1)> <箇条書きのアイテム(Lv1)> 2 <箇条書き全体(Lv2)> <箇条書きのアイテム(Lv2)>3-1</箇条書きのアイテム(Lv2)> <箇条書きのアイテム(Lv2)>3-2</箇条書きのアイテム(Lv2)> </箇条書き全体(Lv2)> </箇条書きのアイテム(Lv1)> <箇条書きのアイテム(Lv1)>4</箇条書きのアイテム(Lv1)> </箇条書き全体(Lv1)>
という木構造を得ることがゴールである。ちなみに、このゴールは XHTML のリスト構造と完全に同型であったりもする。
ここで、上の例の例の箇条書きを、ノードの補完なしで処理すると、上から順に
- 箇条書きのアイテム(Lv1) (= 1)
- 箇条書きのアイテム(Lv1) (= 2)
- 箇条書きのアイテム(Lv2) (= 3-1)
- 箇条書きのアイテム(Lv2) (= 3-2)
- 箇条書きのアイテム(Lv1) (= 4)
だけが得られる。
このとき、3-1 や 3-2 の親要素である 箇条書き全体(Lv2) を補完することを考える。
最初に下準備として、例に示してある構文の定義から、要素の親子関係の制約を表すグラフを描いてみると、こうなる。
まず、箇条書きのアイテム(Lv2) が最初(3-1)に出現した時、その時点で生成済みのツリーは以下のようになるだろう。
<箇条書き全体(Lv1)> <箇条書きのアイテム(Lv1)>1</箇条書きのアイテム(Lv1)> <箇条書きのアイテム(Lv1)> 2
この時点では、また箇条書きのアイテムの 2 が出現しただけなので、このようになるはずである。
ここで、箇条書きのアイテム(Lv2) が出現したのだから、これを追加したいのだが、上記の図の通り、箇条書きのアイテム(Lv1) の子要素に 箇条書きのアイテム(Lv2) を付けることはできない。
そこで、まず上のグラフ(というかツリー)上で、生成済みの一番下の要素である 箇条書きのアイテム(Lv1) から 生成したい要素である 箇条書きのアイテム(Lv2) の親になれる要素 への最短経路を探す。すると、
という経路がある。つまり、上の図で与えられた制約を満たすように補完するには、箇条書き全体(Lv2) を間に挟めば良い。
このことから、
<箇条書き全体(Lv1)> <箇条書きのアイテム(Lv1)>1</箇条書きのアイテム(Lv1)> <箇条書きのアイテム(Lv1)> 2 <箇条書き全体(Lv2)> <箇条書きのアイテム(Lv2)>3-1
という結果を得ることが出来た。
また、先述の例について、たとえば 箇条書きのアイテムの 4 の部分はどのように処理されるのだろうか。
箇条書きのアイテムの 4 が出現したとき、その時点で生成済みのツリーは以下のようになるだろう。
<箇条書き全体(Lv1)> <箇条書きのアイテム(Lv1)>1</箇条書きのアイテム(Lv1)> <箇条書きのアイテム(Lv1)> 2 <箇条書き全体(Lv2)> <箇条書きのアイテム(Lv2)>3-1</箇条書きのアイテム(Lv2)> <箇条書きのアイテム(Lv2)>3-2
この時点では、また箇条書きのアイテムの 3-2 が出現しただけなので、このようになるはずである。
ここで、箇条書きのアイテム(Lv1) を 箇条書きのアイテム(Lv2) の子に追加しようとすると、また例の如く図に描いてある制約に反してしまう。ので、例によって図の上で親になれる要素への経路を探すと、
という経路がある。
この経路を見るに、生成済みの 箇条書きのアイテム(Lv2) と 箇条書き全体(Lv2) と 箇条書きのアイテム(Lv1) も閉じてしまえば良い。
よって、以下の結果になる。
<箇条書き全体(Lv1)> <箇条書きのアイテム(Lv1)>1</箇条書きのアイテム(Lv1)> <箇条書きのアイテム(Lv1)> 2 <箇条書き全体(Lv2)> <箇条書きのアイテム(Lv2)>3-1</箇条書きのアイテム(Lv2)> <箇条書きのアイテム(Lv2)>3-2</箇条書きのアイテム(Lv2)> </箇条書き全体(Lv2)> </箇条書きのアイテム(Lv1)> <箇条書きのアイテム(Lv1)>4
例: 箇条書きと表
また、このグラフの最短経路を用いた補完は、もう少し厄介なシチュエーションにも対応できそうである。
たとえば、上の記法の定義に「セクションの中身」と「表」の規則を追加して以下のようにしたとする。なお、セクションの中身 は箇条書きと表の親である。
- ノード: セクションの中身
- (割愛)
- ノード: 箇条書き全体(Lv1)
- このノード親になれるノード: セクションの中身
- ノード: 箇条書きのアイテム(Lv1)
- このノード親になれるノード: 箇条書き全体(Lv1)
- ノードの開始を検出するregex: ^\-
- (中略)
- ノード: 表全体
- このノード親になれるノード: セクションの中身
- ノード: 表の行
- このノード親になれるノード: 表全体
- ノードの終了を検出するregex: |$
- ノード: 表のセル
ここで、以下のテキスト
- 1 - 2 |a1|b1|c1| |a1|b2|c2|
をパースした場合、
<箇条書き全体(Lv1)> <箇条書きのアイテム(Lv1)>1</箇条書きのアイテム(Lv1)> <箇条書きのアイテム(Lv1)>2</箇条書きのアイテム(Lv1)> </箇条書き全体(Lv1)> <表全体> <表の行> <表のセル>a1</表のセル> <表のセル>b1</表のセル> <表のセル>c1</表のセル> </表の行> <表の行> <表のセル>a2</表のセル> <表のセル>b2</表のセル> <表のセル>c2</表のセル> </表の行> </表全体>
となって欲しい(ちなみにこれも XHTML の構造と一致している)。
ここで、箇条書きのアイテムの処理は先述した通りであるが、例えば箇条書きから表への切り替わり目がどのように処理されるのかを確認してみる。
まず、表のセルの a1 が出現したときには、生成済みのツリーは以下のようになっており、
<箇条書き全体(Lv1)> <箇条書きのアイテム(Lv1)>1</箇条書きのアイテム(Lv1)> <箇条書きのアイテム(Lv1)>2
この経路探索結果と、上の例での要領を併せると、
- 箇条書きのアイテム(Lv1) を閉じて
- 箇条書き全体(Lv1) を閉じて
- 表全体 を生成して
- 表の行 を生成して
- 最後に今回生成したかった 表のセル も生成
すると良いということが分かる。
あとは、表のセルや行の処理も、ほぼ同じ要領で処理してゆけばよい。
もちっと詳細に
上の例だと、例を簡潔にするためにいくつか曖昧にスルーしていた部分がある。が、それらも以下のように考えると、シンプルなまま解決できる、はずである。出来ない場合は筆者が見落としているので指摘して欲しい。
例えば、下のような、構文規則のグラフと経路探索した結果があったとする。
この時、
- 経路(矢印)がノードの上に出ている場合、そのノードを閉じる
- 経路(矢印)がノードの上から入っている場合、そのノードを補完する
- それ以外のノードについては、なにもしない
このような基準でノードを閉じたり足したりすることで、得られた経路を具体的にどのようなノードの操作に反映するのかが明確になるであろう。
それと、あるノードの親になれるノードが複数種類ある場合は、補完用の経路探索結果の長さが最も短いものを採用すれば良かろう。もし最短距離に複数あるなら、それは文法が曖昧であるので、エラーにするか、Warning を出しながらもとりあえず適当などれかにしておけばよかろう。
また、構文の「ノードの開始を検出するregex」や「ノードの終了を検出するregex」について、優先度の問題がある(例えば上の例の、表の行の終了と表のセルの終了)。この場合、
- 文字列内での一致位置がより前のものを優先
- ↑で互角なら、構文規則的により上位の要素の終了を優先 & より下位の要素の開始を優先
- ↑でも互角なら、一致した長さが長い方を優先
とすることで、優先度を解決できるのではあるまいか。
考えてみたので
ひとしきりまとめてみたところ、実現出来そうな気がしてみたので、晒してみて、実装する方向に自分を追い込んでみた。職場が無駄に忙しいのが問題だが、時には自分のコードも書かなくては。
wikiforme もどきの基本的な機構: 記法のパースと木構造(XML)の出力
思想は wikiforme と大きく変わらない。具体的には、
- 元の記法には何らかの形で、ノードの開始を明示する
- ノードの終了が明示されていない場合、適宜補完する
- 階層の一部を省略された場合、適宜補完する
- ノードの終了や階層の中間のノードの補完は、ノードの親子関係の制約に着目して行う
- 例: A の親は B、B の親は C という制約があるなら、A と C の中間を補完することが出来る
といったところ、だろう。
これを実現するためには、以下を実現すれば良さそうだ。
- 元の記法から、ノードの開始を検出する
- ノードの親子関係に関する制約を与えられるようにする
- 補完に使う
- ノードの親子関係を適切に補完する
そのためには、以下のような造りにすれば良さそうだ。
- ノードの開始を検出するための正規表現なりを、記法の定義に含めるようにする
- 親子関係の制約も記法の定義に含めるようにする
- 親子関係の補完は、親子関係のグラフをダイクストラ法なりで探索するだけ。
- 参考に: 補足的な機構: 親子関係の補完
wikiforme もどきを作るとしたら
うだうだなメモ。そういえばこのブログにうだうだなメモを書いたことはなかったような。
やりたいことの核心
以下の二つが id:saiya_moebius 的にやりたいことだったのだが、それがちょうど上の元ネタとマッチしている事に最近気がついたという次第。
ただ、id:saiya_moebius としては、マークアップ言語の理想を追求して最初の記法と最後の出力形式との完全な直交性を確保する気はなく、あくまで書く手間と変換する手間を減らしたいだけ。
何がうれしいか
といったことを楽にしたいのである。
また、それらを活用するには、記法のパース結果(XML)から何らかの有意なコンテンツを出力できると、記法を扱うためのメカニズムの存在意義が出るというものであろう。
wikiforme について
上のやりたいことは wikiforme の中の人もそういっている*2のだが、id:saiya_moebius としては以下の点も考慮したいところである。
- 特定言語に癒着しない
- 仕組みをシンプルにとどめる
前者については、構文定義などが Ruby にべったりくっついていると実際問題困るというのが理由。RPC なり stdin/out 経由の通信なりで疎に分離したいところである。具体的には、インターフェースの仕様だけがあって、処理系は任意の言語なりで書けると嬉しい。
後者は、うっかり欲を出し過ぎたり、「もしかしてこういう場合も」を考えすぎてgdgdになるぐらいなら、前述の目的にフォーカスしてできるだけシンプルにしたい、のが理由である。wikiforme が、手っ取り早く記法を扱うためには複雑に思えることもあって、この点も意識したく思うのである。
XNA な ContentProcessor を自作した場合、それをローカルエリアでない場所に置いてはいけない
XNA でカスタム ContentProcessor を作った場合、それをローカルエリアでない場所(ネットワークドライブなど)に置いてしまうと、参照設定したにも関わらず、VisualStudio のプロパティウインドウの Content Processor 欄のドロップダウンの候補に表示されないことがある。
例えば、日本語を表示するために FontDescriptionProcessor を継承した ContentProcessor を作って、それをネットワークドライブ上に置いてしまった場合、など。
なので、ContentProcessor の入っている dll なりプロジェクトなりは、ローカルな場所に置く必要がある。
この場合に限らず、マイコンピューターゾーンでない場所や、ローカルでないドライブにファイルやプロジェクトを置くと、ろくな目に遭わないことが多い・・・。