C コードに付ける GC 用の静的解析注釈

解析の実行

Julia には GC の振る舞いに関して C コードを静的に解析するためのアナライザプラグインが付属します。ソースコードは src/clangsa にあり、実行するには依存する Clang のビルドが必要です。Make.user で BUILD_LLVM_CLANG 指定すれば適切なバージョンの Clang をビルドでき、USE_BINARYBUILDER_LLVM 変数を指定すればプリビルドのバイナリを利用できます。Clang を用意したら make -C src analyzegc でソースツリーに対する解析が行えます。

概要

Julia の GC は正確 (precise) なので、ガベージコレクトが発生しうる任意の時点で参照されうる任意の値に対する正しい GC ルートの情報を管理する必要があります。ガベージコレクトが発生する可能性のある場所のことをセーフポイント (safepoint) と呼びますが、この章ではセーフポイントを含む可能性のある関数呼び出しもセーフポイントと呼びます。

生成されるコードでは GC ルート配置パスが自動的にセーフポイントを処理します (詳しくは GC root に関する LLVM codegen の開発者向けドキュメントを参照してください)。しかし C コードでは、GC ルートをランタイムに手動で伝える必要があります。これは次のようにマクロで行われます:

// マクロの引数に渡されたスロットに割り当てられた値は
// この GC フレームでルートされる。
JL_GC_PUSH{1,...,6}(args...)
// サイズ n の配列 rts の要素に割り当てられた値は
// この GC フレームでルートされる。
JL_GC_PUSHARGS(rts, n)
// GC フレームをポップする。
JL_GC_POP

これらのマクロが使われるべき場所で使われなかったり、使い方を誤ったりすると、警告が発生することなくメモリが破損します。そのため必要なコードが正しい場所にマクロを持つことが非常に重要です。

そこで私たちは静的解析を使って GC に関するマクロが誤って使われていないことを確認します。この章の残りの部分はこの静的解析を概観し、Julia コードベースで必要だったサポートを説明します。

GC の不変条件

正しいコードでは次の二つの不変条件が成り立ちます:

• 全ての GC_PUSH に適切な GC_POP が対応する (実際のコードでは同じ関数のレベルで対応することを要求する)。
• 特定のセーフポイントでルートされていない値は、それよりも後で参照されてはいけない。

もちろん悪魔は細部に宿ります。特に二つ目の条件を確認するには、次の情報が必要です:

• どの関数呼び出しがセーフポイントで、どの関数呼び出しがそうでないか。
• セーフポイントでルートされている値はどれか、ルートされていない値はどれか。
• 値はいつ参照されるか。

この中で特に二番目の情報を得るには、実行時に値をルートしているとみなされるメモリ領域 (ルートされる値が格納されるメモリ領域) を知っておく必要があります。この領域には GC_PUSH マクロに渡されることで明示的に指定された領域、グローバルな領域および値、およびそれらの領域から再帰的に到達可能な領域が含まれます。

静的解析のアルゴリズム

アイデアは非常に単純ですが、実装はかなり複雑になります (大量の特殊ケースや C と C++ の細かい部分が主な原因です)。短くまとめると、ルートを行う全ての領域・ルート可能な全ての値・ルート可能な値のルート状態を変化させる任意の式 (代入・アロケートなど) を追跡し、任意のセーフポイントにおいて「シンボリック GC」を行うという処理が実装されます。シンボリック GC を行ったときに考えている領域からルートされていない値に "毒" を塗り、毒の付いた値が後から参照されたらエラーを発生させます。

Clang を使った C コードの静的アナライザはプログラムの状態を表すグラフを構築し、そのグラフにエラーの発生源がないかを探索することで動作します。このグラフの一部のノード (例えば制御フローに対するノード) は解析器自身によって生成されますが、他の部分には上述の定義を使って私たちが用意した独自の状態が含まれます。

この静的アナライザはインタープロシージャルであり、関数境界を越えた制御フローの解析が可能です。ただし完全に再帰的ではなく、ヒューリスティックを使って探索する関数呼び出しが決定されます (さらに翻訳単位をまたいだ関数呼び出しはアナライザから見えません)。今考えている問題では正しいコードの定義にコード全体の情報が関わるので、全ての関数プロトタイプにコード解析で必要となる情報を持った注釈を付ける必要があります。インタープロシージャルな静的解析をすれば分かる情報であっても、この注釈は必要です。

しかし幸いにも、インタープロシージャルな解析を使えば関数の実装に対して注釈が正しいかどうかを確認できます。

アナライザの注釈

注釈の定義は src/support/analyzer_annotations.h にあります。注釈はアナライザが使われているときだけ有効になります。使われていないときプロトタイプに対する注釈は空文字列になり、関数のように使う注釈は noop になります。

JL_NOTSAFEPOINT

これはおそらく最も頻繁に使われる注釈です。どんな場合にも GC セーフポイントに到達しないことが分かっている関数に付けるべきです。一般にこの注釈が付いている関数が行えるのは算術演算・メモリアクセス・JL_NOTSAFEPOINT 注釈の付いた関数の呼び出し・別の方法でセーフポイントを持たないことが保証されている関数の呼び出しです (例えば標準 C ライブラリはセーフポイントを持たないことがアナライザにハードコードされます)。

次の使用例に示すように、この注釈が付いた関数を呼び出すときにはルートされていない値が存在しても構いません:

void jl_get_one() JL_NOTSAFEPOINT {
  return 1;
}

jl_value_t *example() {
  jl_value_t *val = jl_alloc_whatever();
  // val がルートされていないが、jl_get_one はセーフポイントでないので
  // この jl_get_one は正当となる。
  jl_get_one();
  return val;
}

JL_MAYBE_UNROOTED/JL_ROOTS_TEMPORARILY

関数の引数に注釈 JL_MAYBE_UNROOTED を付けると、その引数にルートされていない値を渡せるようになります。通常 Julia ABI は呼び出し側がルートされた値を呼び指し先に渡すことを保証しますが、一部の関数はこの ABI に従わず、ルートされていない関数も渡すことができます。ただし JL_MAYBE_UNROOTED をつけた引数が保存されることは保証されない点には注意が必要です。注釈 ROOTS_TEMPORARILY を使うと、ルートされていない値を渡せるようになるのに加えて、引数が呼び出し先に含まれるセーフポイントで保存されるというより強い保証が得られます。

なお JL_NOTSAFEPOINT は本質的に JL_MAYBE_UNROOTED/JL_ROOTS_TEMPORARILY を意味します。関数がセーフポイントを含まないとき引数がルートされているかどうかは関数の実行に関係しないためです。

また、この二つの注釈は関数を呼び出すときと関数を定義するときの両方で利用できます。呼び出し側に付けると Julia ABI の関数に通常要求される引数がルートされていなければならないという要件が撤廃され、定義に付けると引数はルートされるという暗黙の仮定がなくなります。

関数全体に二つの注釈のいずれかが適用されると、関数が持つ全ての引数にその注釈が適用されます。通常これは可変長引数関数でだけ必要になるはずです。

使用例を示します:

JL_DLLEXPORT void JL_NORETURN jl_throw(jl_value_t *e JL_MAYBE_UNROOTED);
jl_value_t *jl_alloc_error();

void example() {
  // jl_alloc_error が返す値はルートされていない。 通常これはエラーとなるが、
  // jl_throw の第一引数に付いた JL_MAYBE_UNROOTED 注釈のおかげで許される。
  jl_throw(jl_alloc_error());
}

JL_PROPAGATES_ROOT

この注釈は別の場所に保存されたルート可能なオブジェクトを返すアクセッサ関数でよく見られます。関数の引数にこの注釈が付いていると、アナライザはその引数のルート状態が関数の返り値に継承されるものとみなします。

使用例を示します:

jl_value_t *jl_svecref(jl_svec_t *t JL_PROPAGATES_ROOT, size_t i) JL_NOTSAFEPOINT;

size_t example(jl_svec_t *svec) {
  jl_value_t *val = jl_svecref(svec, 1)
  // jl_svecref の第一引数に PROPAGATES_ROOT が付いているので、
  // jl_svecref は svec の持つルート状態を val に伝播させる。
  // よってこの jl_gc_safepoint は正当となる。
  jl_gc_safepoint();
  return jl_unbox_long(val);
}

JL_ROOTING_ARGUMENT/JL_ROOTED_ARGUMENT

これは本質的に JL_PROPAGATES_ROOT の代入バージョンです。JL_ROOTING_ARGUMENT が付いた引数のフィールドに JL_ROOTED_ARGUMENT の付いた引数を代入するとき、代入元のルート状態が代入先に継承されるようになります。

使用例を示します:

void jl_svecset(void *t JL_ROOTING_ARGUMENT,
                size_t i,
                void *x JL_ROOTED_ARGUMENT) JL_NOTSAFEPOINT

size_t example(jl_svec_t *svec) {
  jl_value_t *val = jl_box_long(10000);
  jl_svecset(svec, 3, val);
  // jl_svecset に付いている注釈により、
  // jl_svecset は svec のルート状態を val に伝播させる。
  // よってこの jl_gc_safepoint は正当となる。
  jl_gc_safepoint();
  return jl_unbox_long(val);
}

JL_GC_DISABLED

この注釈は関数が GC ランタイムが無効化された状態でのみ呼ばれることを表します。この種の関数は GC のスタートアップ処理を行うコードで最もよく見られます。この注釈があっても実行時の GC 有効化/無効化の呼び出しは確認されるので、嘘をついても Clang はそれを見破ることに注意してください。GC が無効化されていないときに特定の関数の処理を無効化するためにこの注釈を使うのは望ましくありません (どうしても必要なときは #ifdef __clang_analyzer__ を使ってください)。

使用例を示します:

void jl_do_magic() JL_GC_DISABLED {
  // ルートを気にせず好き勝手にアロケートする。
}

void example() {
  int en = jl_gc_enable(0);
  jl_do_magic();
  jl_gc_enable(en);
}

JL_REQUIRE_ROOTED_SLOT

この注釈が付いた引数にはルートされたスロットを渡す必要があります。言い換えると、この注釈が付いた引数に渡されたスロットへ値を代入すると自動的にルートされます。

使用例を示します:

void jl_do_processing(jl_value_t **slot JL_REQUIRE_ROOTED_SLOT) {
  *slot = jl_box_long(1);
  // 代入された値をルートするという注釈がスロットに付いているので OK
  // 注釈がなければエラーとなる。
  jl_gc_safepoint();
}

void example() {
  jl_value_t *slot = NULL;
  JL_GC_PUSH1(&slot);
  jl_do_processing(&slot);
  JL_GC_POP();
}

JL_GLOBALLY_ROOTED

この注釈は特定の値が必ずグローバルにルートされることを表します。グローバル変数の宣言に適用されたときはその変数が表す値 (配列変数に適用されたときは各要素が表す値) が、関数宣言に適用されたときはその関数の返り値が対象となります。関数に対するこの注釈はグローバルにルートされたプライベートな値を返す関数などで使います。

使用例を示します:

extern JL_DLLEXPORT jl_datatype_t *jl_any_type JL_GLOBALLY_ROOTED;
jl_ast_context_t *jl_ast_ctx(fl_context_t *fl) JL_GLOBALLY_ROOTED;

JL_ALWAYS_LEAFTYPE

この注釈は基本的に JL_GLOBALLY_ROOTED と等価ですが、対象の値が葉型となるためにグローバルにルートされる値に対して使われるべきです。葉型のルートは少し複雑です。通常そういった型は対応する TypeName の cache フィールドを通してルートされ、その TypeName はモジュールによってルートされます (つまり葉型を持つモジュールが正常な限りルートは行われます)。そのため葉型は使われるときルートされていると普通は仮定できますが、このやり方は将来変更される可能性があるので、異なる注釈を使ってグローバルにルートされる理由を分けるようにしています。

加えてアナライザは葉型のチェックを自動的に検出し、そういったパスで GC が足りなくてもエラーとみなしません。

JL_DLLEXPORT jl_value_t
*jl_apply_array_type(jl_value_t *type, size_t dim) JL_ALWAYS_LEAFTYPE;

JL_GC_PROMISE_ROOTED

これは関数スタイルの注釈です。この注釈に渡された値は全て、現在の関数のスコープでルートされるとみなされます。これは対象のプログラムがアナライザで処理できない、あるいは複雑すぎて解析できないときのための脱出ハッチです。この注釈の利用は避けるべきであり、この注釈を使わざるを得ない状況になったとしてもアナライザを改善できないかどうかを最初に考えるべきです。

void example() {
  jl_value_t *val = jl_alloc_something();
  if (何らかの条件) {
    // このプログラムと関係のない複雑な理由により、
    // val がルートされることが (偶然) 分かったなら...
    JL_GC_PROMISE_ROOTED(val);
  }
}

解析の完全性

アナライザはローカルな情報だけを解析します。特に、例えば上述の PROPAGATES_ROOT が存在することからも分かるように、アナライザはメモリの改変が必ずアナライザから見える形で行われる仮定し、呼び出された関数や並行に実行される他のスレッドでは改変は起こらないとみなします (考えに入れるとたまたま判断された関数については解析が行われます)。そのため、アナライザは問題のあるケースの一部を見過ごす可能性があります。ただ実際のコードを実行しているときにメモリが並行に書き換わることは非常に稀です。そういったケースのためにアナライザを書き換えるのは将来取り組むべき興味深いトピックと言えます。