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 に規定があり、おおざっぱに言うと

  • NIC の MAC アドレス + タイムスタンプ
  • ハッシュ関数(NIC の MAC アドレス + タイムスタンプ)
  • 乱数 (pseudo-random UUID とも)
  • Guid

のどれかである*1。ちなみに、どの手法で生成されたのかは、UUID の先頭の方のビットで分かるようにもなっている。

mono のソースコードの流れ

で、mono での Guid の生成の流れを追っかけてみたのだが、以下に概要を示す。上から順にコードの流れで、付加されているソースコードは mono の svn head へのものである。

  1. static Guid.NewGuid()
  2. static RandomNumberGenerator.Create()
  3. static CryptoConfig.CreateFromName(string)
  4. RNGCryptoServiceProvider.GetBytes(byte[])
  5. RngOpen(), RngInitialize(byte), RngGetBytes(IntPtr, byte)

以下では、それぞれについて気になった点などをハイライトしてみた・・・つもりが、実際にはほとんど順をおった解説になってしまった。これだから現実逃避でコードを読むのは(ry

各論の前に: 長くなってしまったので概略

  1. Guid.NewGuid() は、RNGCryptoServiceProvider の乱数を使っているだけ
    • pseudo-random UUID が生成される。
  2. RNGCryptoServiceProvider は、Win32 環境なら CAPI をラップするだけ
  3. 非 Win32 環境の RNGCryptoServiceProvider は、以下を順に試して使えるやつを使う
    1. /dev/urandom
    2. /dev/random
    3. EGD な Unix ソケット: MONO_EGD_SOCKET 環境変数が接続先

メモ: 自分への宿題 (= 読んだはいいが分からなかった点)

  • mono のクラスライブラリ実装で、static readonly による singleton よりも、lock + if なシングルトンが用いられているのはなぜなのでしょう
  • mono が libuuid を使わずに独自実装したのはなぜなのでしょう
  • 非 Win32 環境の場合、RNGCryptoServiceProvider が AppDomain 単位で lock するのに対して、ファイルデスクリプタはプロセス内で一つ、とスレッドセーフ性*2に問題があるように見えるのは、実際どうなのでしょう

*1:正確には他にもあったりするが、どうでもいいので続きは RFC で。

*2:AppDomain セーフ性？

*3:にしても、パフォーマンス上のオーバーヘッドが小さくない気がするのだがどうなのだろう。

続きを読む

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 は

  1. pointers to methods (first cache)
  2. 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。

ただし、現状では全ての関連コードを洗ったわけではないので、所によってはまだ読んでいないものがある。

自分への宿題 (= 不明な点)

  • CreateDelegate_internal の中身を見てみる
  • static なメソッドでありながら、Delegate.m_target が非 null になる条件を明らかにする
    • たぶん拡張メソッドの関係だとおもうのだけど。
  • mono_marshal_get_runtime_invoke の中身やその先も見てみる

ソースコードの流れ

具体的には、Delegate.DynamicInvoke を起点に、以下のようにコードを探索し、DynamicInvoke がどんなものかを見てみた。なお件のバグの原因だけを見るならば後半だけで十分である。

  1. Delegate.DynamicInvoke(params object[])
  2. Delegate.DynamicInvokeImpl (object[])
  3. Invoke(Object, Object[])
  4. MonoMethod.Invoke(Object, BindingFlags, Binder, Object[], ClutureInfo)
  5. ves_icall_InternalInvoke(...)
  6. mono_runtime_invoke_array(...)
  7. mono_runtime_invoke(...)
  8. default_mono_runtime_invoke(...)
  9. static MonoInvokeFunc default_mono_runtime_invoke
  10. mono_jit_runtime_invoke(...)
  11. mono_marshal_get_runtime_invoke(...)

これらは、大まかには以下のようになっている。

  1. 各種前処理をしながら関数呼び出しが深くなってゆく
    • 過程で DynamicInvoke や Invoke、Activator.CreateInstance などや、さらには通常のメソッド呼び出しが合流してゆく
  2. 最終的には　default_mono_runtime_invoke に行き着く
    • あらゆるメソッド・コンストラクタの呼び出しがここにたどり着く
  3. 通常の JIT を使っている場合、これは mono_jit_runtime_invoke に相当する
  4. mono_jit_runtime_invoke では、以下の二つに分けて IL を生成 + コンパイルする (例外もある)
    1. 呼び出す対象のメソッドそのもの
    2. 呼び出す対象を呼び出すための各種処理
  5. 上で得られた二つ(コンパイル済み)を使うことで、コンパイル済みのメソッドを呼び出す、という処理を実現している

以下に、各部を読み解いた過程のメモ(?)を示す。

*1:英語がとっても不安だ・・・というか駄目そうな予感がひしひしと・・・

*2:see: デスクリムゾン - Wikipedia

*3:そこにコードがあるから

続きを読む