たまにはRuby Parser開発日誌以外の話ということでRipperの話をします。

先日このようなpatchを書いたのでその話です。

ちょっと前からmaster branchでfound internal inconsistencyが発生していました。具体的なlogは http://ci.rvm.jp/results/trunk-gc-asserts@ruby-sp2-docker/4501173 をみてください。このtestではbuild時にRGENGC_CHECK_MODE=2を設定することで、GCが起こるたびに内部的な不整合をチェックしています。

Ripperのテストの一環としてtest/ripper/test_files_test_2.rbというテストケースでtest/*以下のファイルを対象にRipperを走らせて例外が発生しないかをチェックしています。これにtest_pattern_matching.rbを与えたときにGC周りでなにかinconsistencyが起きるようになっていました。

なにがinconsistencyなのか

これを理解するためにはまずGCとくにRGenGC(世代別GC)についての理解が必要になります。私のGCに対する理解は"CRubyの実装時にもメモリ管理を意識しなくていい、最高！"くらいの理解だったので、より詳細に知りたい方は以下の論文やスライドをみるのがよいと思います。

世代別GC

RGenGC (Restricted Genrational GC)とはRuby 2.1で導入されたGCを高速化する仕組みです。 RubyのGCはmark & sweep GCなので、使用中のobjectをまずmarkして、そのあとでmarkされていないobjectをsweepするという流れになります。これを毎回すべてのobjectを対象に行なっていると時間がかかるので、その改善方法の1つとしてRGenGCがあります。objectは作られて短期間で使われなくなるものと、作られて長期間使われるものに分類できることが経験的に知られています。例えばweb serverでrequestを表すobjectはそのrequestをさばいたあとは使われなくなる一方、DBへのconnectionを管理するためのobjectはプロセスが起動している間は基本的にずっと生きているといった感じです。

そこでobjectを新しい世代(young)と古い世代(old)に分けて、新しい世代のみを対象とするマイナーGCと全ての世代を対象にするメジャーGCを用意し、基本はマイナーGCを実行するという方法をとることでmark & sweepの対象を減らすことができます。なお一定期間新しい世代にいたobjectは古い世代に移動します。

inconsistency

世代別GCで気をつけないといけないのはoldなobjectがyoungなobjectへの参照をもつことがあるということです。例えば以下のような2つのobjectがあったときにarray[0] = strをするとoldからyoungへの参照が発生します。この場合arrayが生きている間はstrを回収されると困ります。ではこの状態でマイナーGCが発生するとどうなるでしょうか。マイナーGCではyoungなobjectから辿れるobjectだけをmarkするのでstrが使われていないことになってしまいます¹。

array: old
str: young

この問題を解決するためにwrite barrierという仕組みが用意されています。これはあるobjectから別のobjectに参照が発生したことを記録し、GCのときに参照元のobjectも考慮してmarkするようになります。CRubyのコードにときどき出てくるRB_OBJ_WRITEやRB_OBJ_WRITTENがwrite barrier用のマクロです。このマクロにarrayとstrを渡すと、arrayがoldかつstrがyoungなときにarrayをリメンバーセットに登録します。リメンバーセットに登録されたobjectはmarkするときの起点に含まれるようになるので、これでstrがmarkされるようになり、sweepされなくなります。

found internal inconsistencyとは

inconsistencyにもいろいろ種類があるのですが、今回問題になっていたのはverify_internal_consistency_iのなかでもcheck_generation_iに関するものでした。ここではRubyの管理しているobject(parent)をiterateして、そのobjectがmarkしているobject(child)をみつけ、それらparentとchildの世代を確認します。もし

parentがold
childがyoung
parentがリメンバーセットに登録されていない

という条件をすべて満たす場合、それは上で議論したような状態であり、解放済みのobjectを触ってしまうという(発見の難しい)bugに繋がります。ということで何がおきているかを知るにはparseおよびRipperがどのようにメモリを管理しているかを知る必要があります。

parser/Ripperのメモリ管理

NODEをどうやって管理するか

parserが主に管理しているものはASTのNODEです。かつては他のobjectと同じようにGCによって管理されていたNODEですが、現在はGCの管理からは外れT_IMEMO/astというobjectがまとめて管理しています²。

具体的にはrb_ast_tがAST全体を管理するための構造体で、これはRubyのGCが管理しています。その中のnode_bufferが動的にメモリを確保しておりNODEの管理もここに含まれます。

// node.c および node.h

typedef struct rb_ast_struct {
    VALUE flags;
    node_buffer_t *node_buffer;
    rb_ast_body_t body;
} rb_ast_t;

typedef struct node_buffer_struct node_buffer_t;

struct node_buffer_struct {
    node_buffer_list_t unmarkable;
    node_buffer_list_t markable;
    struct rb_ast_local_table_link *local_tables;
    VALUE mark_hash;
    // - id (sequence number)
    // - token_type
    // - text of token
    // - location info
    // Array, whose entry is array
    VALUE tokens;
};

ちなみにNODEはRubyのobjectを参照していることがあります。例えばNODE_STRはString objectへの参照をもちます。

$ ruby --dump=p -e '"abcdefg"'

# @ NODE_SCOPE (id: 1, line: 1, location: (1,0)-(1,9))
# +- nd_tbl: (empty)
# +- nd_args:
# |   (null node)
# +- nd_body:
#     @ NODE_STR (id: 0, line: 1, location: (1,0)-(1,9))*
#     +- nd_lit: "abcdefg"

こういったNODEの場合、NODEの参照するobjectをmarkするのはT_IMEMO/astの責務です³。objectへの参照をもつNODEをmarkable、そうでないNODEをunmarkableとして分けて管理しています。 markableなNODEにobjectを渡したときはT_IMEMO/astを親としてwrite barrierを設定する必要があります。

Ripperの場合

一方でRipperの場合はunmarkableなNODEを使い、objectはmark_hashに管理させるという方針で実装しています。unmarkableなNODEは典型的にはNODE_CDECLが使われています。この場合はrb_ast_add_mark_objectがrb_hash_asetを呼ぶので、自動的にmark_hashを親としてwrite barrierが設定されます。

ここまでのまとめ

Parserの場合
- markableなNODEがobjectへの参照をもつ
- つまりT_IMEMO/astがobjectを管理している
- なのでp->astを親としてRB_OBJ_WRITEやRB_OBJ_WRITTENを呼ぶ必要がある
Ripperの場合
- unmarkableなNODEがobjectへの参照をもつ
- つまりmark_hashがobjectを管理している
- なのでmark_hashを親としてRB_OBJ_WRITEやRB_OBJ_WRITTENを呼ぶ必要がある (これはparse.y的にはadd_mark_object呼ぶことで達成される)

今回何が問題だったか

RipperのときにNODE_ARYPTNやNODE_FNDPTNといったmarkableなNODEにobjectをもたせ、p->astを親としてRB_OBJ_WRITEやRB_OBJ_WRITTENを呼んでいなかったのが問題でした。T_IMEMO/astがoldなときを考えてみましょう。add_mark_objectはmark_hashをリメンバーセットに登録しますが、p->astについてはなにもしません。この状態でGCのconsistencyのチェックが走ると

T_IMEMO/astはold
objectはyoung
T_IMEMO/astからobjectはmarkの対象

となってinconsistencyだと判定されてしまいます。実際はadd_mark_objectを呼んでいるのでmark_hashはリメンバーセットに登録され、そちらを経由してobjectがmarkされるので参照が残っているobjectが回収されるというbugにはなっていないはずです⁴。

修正はRipperの場合の実装にあわせてunmarkableなNODE(NODE_OP_CDECL)を使うように変更しました。

余談

なんでつい最近まで見つからなかったのか不思議に思う人もいるかと思います。test_files_test_2.rbが毎回対象のファイルをサンプリングしているとはいっても、pattern matchingが入ってからおおよそ4年です。これには理由があってpattern matchingは3.1までexperimentalな機能でtest_pattern_matching.rbは巨大なstringになっていたからでした。

まとめ

GCがあってもobjectがどうやって管理されているか知らないといけないことがたまにある
RubyにはいろいろなCIがあって発見の難しい問題を発見しており、すごい⁵
Ripperのメモリ管理を改善したい or してほしい...⁶

実際はstack上のobjectなどもmarkされますがここでは割愛↩
Ruby の NODE を GC から卒業させた - クックパッド開発者ブログを参照↩
mark_ast_value関数を参照↩
なのでbackportは不要なはず↩
Rubyの開発を支える技術 - クックパッド開発者ブログ参照。また ruby-trunk-changes 2023-03-28 - ruby trunk changesによると "安定版メンテナンスの時は TEST_RIPPER_RATIO=1 を指定して全ファイルを parse するようにしてテストしたりしています" とのこと↩
ふと思ったんですが、RipperのNODE/VALUE問題って、parseにもう一つsemantic value stackを追加したらNODEとVALUEを分割できて解決したりしませんかね↩