丁稚な日々

◆slapのGC紹介(前編) - Garbage Collection Advent Calendar

_ Garbage Collection Advent Calendarとか、どー考えても書くやつ数えるほどしかいねーだろ、とか呆れちゃう企画だと思うわけですが、中村一族のよしみとか、俺GarbageCollect.jpとかいうドメイン使っちゃってるじゃんとか、まあそんなこんなの縁もあるので、一口噛んでみることにしました。

_ 俺らが話をするとどーしても話題がRuby(MRI)に偏っちゃうわけですが、ここは敢えて全く別のGC実装を取り扱おう、とか要らんことを思い立ってしまったので、今回はslapという言語処理系のGC実装について書いてみることにします。
こんな誰も知らない言語のGCを解説しても誰得? って感じだけど、まあ、たまにはこういうどうでもいいものを取り扱ってみてもいいんじゃね?

◆slapとは

_ slapとは、毎年4月1日にちょっとずつ更新版がリリースされるらしい、作りかけの言語とその処理系です。
大まかに言って、rubyとECMAScriptを足して2**16で割ったような言語、らしいです。

_ slapはC言語系の記法のプロトタイプベースのスクリプト言語であり、ということは必然的にECMAScriptに似てしまっているわけですが、そこに敢えてクラスベースの皮をかぶせて普通に使う分にはクラスベースのオブジェクト指向言語として扱えることを目指しています...たぶん。
実際には、作者はRubyはそれなりに知ってるけどECMAScriptはよく知らないらしく、ECMAScriptとの類似性は前述のような基本性格の一致に由来するものであり、その内部実装やクラスライブラリの目指しているものはむしろRubyの影響を強く受けているようです。

_ ま、今回はslap自体の紹介は目的じゃないので、詳しくは公式サイトを眺めてください。

◆slapのGC

_ よせばいいのに、slapではわざわざオリジナルのGCを実装して利用しています。
作者によると、Boehm GCの使い方がよく分からなかったのでやむなくせっかくだから自前で作ってみようかと思って、という程度の浅い理由で独自実装が採用されたそうです。
特徴は...GCにおいて何が特徴になるのかよく分かりませんが、slapのGCはとりあえずexactなGCらしいです。
また、incremental GCとか世代別GCみたいなややこしい機構を伴わないシンプルかつコンパクトなmark&sweep GCらしいので、考えようによっては読みやすい、と言えるのではないでしょうか。

_ では、早速slapのGCの実装を眺めてみましょう。
今回は、本日時点での最新版であるrevision 314を使用します。
いちいちここにコードは貼らないので、適宜ソースコードを参照してください。

◆ヒープ構造

_ まず、GCの前提となる、ヒープの構造について理解しましょう。
gc.cの66行目から怪しい英語モドキで簡単な説明が書かれています。
これによると、

• まずmmap(2)を利用してOSから2MBのメモリ領域を確保する。これをarenaと呼ぶ。
• arenaを、32bit環境の場合4KBずつ、64bit環境の場合8KBずつに切り裂く。この切り裂かれた個々の断片をdrawer(引き出し)と呼ぶ。
• drawerを束ねたものをcabinet(戸棚)と呼ぶ。
• drawerの中にはcase(容器)と呼ばれるメモリ断片が入っている。caseの大きさは様々だが、同じcabinetの中のcaseは全て同じ大きさである。
• 1KBより大きいメモリを確保する場合はこのヒープ構造は利用しない。

...ということらしいです。

_ 96行目から、実際にcabinetを幾つか用意しています。
cabinetは前述の説明から分かるように、内包するcaseの大きさごとに用意されるわけですが、sizeof(sl_obj_t)用、4byte用(32bit環境のみ)、8byte用、16byte用、...、1024byte(=1KB)用、のcabinetがそれぞれ用意されます。
sl_obj_t型というのはslapのオブジェクトを表現する型で、ずばり32bit環境では12byte、64bit環境では24byteです。
slapのオブジェクトはここから確保されるので、おそらく一番よく使われるcabinetはこれになるはずです。
その他のcabinetは、非オブジェクトな何かのためにメモリを確保しようとした場合に使用されます。

◆メモリの確保

_ では、ヒープ構造を理解したところで、slap内部でどのようにメモリ確保が行われるのか、コードを追っていきましょう。

_ 任意のサイズのメモリを確保するsl_mallocという関数もあるのですが、話を単純化するために、slapオブジェクトを確保する専用関数sl_obj_allocから眺めていくことにします。どうせslapオブジェクト以外はGC対象じゃないですしね。
gc.cの809行目からをご覧ください。小さい関数ですね。
エラー処理とかを無視すると、819行目で内部関数allocを呼んでメモリを確保し、820行目〜822行目で初期化、823行目でslap_register_living_listなる関数を呼んでおしまいです。
とりあえず、alloc関数呼び出しの引数(当然ながらサイズ指定です)が0であることに注目して下さい。

_ では、続いてalloc関数の実装を見てみましょう(598行目〜)。
実はalloc関数はサイズ0を特別な値とみなし、604行目からのif文にあるようにsizeof(sl_obj_t)がサイズとして指定されたとみなした上で0番のcabinetを使用します。
なおそれ以外のサイズの場合はelse節にあるようにそのサイズを満たす大きさのcaseを持ったcabinetを探します。
cabinetが見つからなければgc_malloc関数を呼び出して処理を終了しますが(617行目)、この関数は結局Cライブラリ関数malloc(3)の呼び出しになります。

_ さて、無事にcabinetが見つかったら、今度はcabinetの中から未使用のcaseを探します(621行目〜)。
先に説明したように、cabinetには複数のdrawerが入っています。
for文でそのdrawerを順次見ていき、drawer内の未使用caseを発見した時点で探索を終了します。
未使用caseの探索は、search_free_bmp関数の呼び出し(625行目)によって行われます。
この名前から想像できるわけですが、どうやら小生意気にもビットマップ方式で未使用のcaseを管理しているようですね。
無事に見つかったら、該当caseの使用中ビットをセットし(626行目)た上で、見つかったcaseを指すポインタを返しています(627行目)。

_ 念のためsearch_free_bmp関数も見てみましょう(525行目〜)。
これも短いですが、肝はcount_bits関数の呼び出しとその引数のようです(533行目)。
count_bits関数は138行目からですが、どうやら引数の値の中の立っているビットの数を数えているようです(なぜこのコードでそれが実現できるかは考えてみてください)。
では、ビットマップを表す値であるxに対してx & (~x - 1)などという謎の演算をした結果の値をcount_bits関数に渡してなんで「index of the first zero bit」が得られるのか、ですが...作者によると「忘れた」そうなので、ちょっと考えてみましょう。

_ まず、適当な8bitの数値「00110111」を例にとります。
LSBをビット0とすると、ビット3、ビット6、ビット7が0なわけですが、ここでは「3」という結果が欲しいわけです。
そこで、x & (~x - 1)を計算してみると、まず~xは「11001000」で、そこから1を引くと「11000111」になります。
次に元の「00110111」と&を計算すると「00000111」になります。
で、立っているビットの数を数えると...おお、見事に3になりますね。
他の値でも試してみてもらうと分かりますが、実はx & (~x - 1)という演算は、x中の0である最下位のビット以上のビットを0に、それより下のビットを1にするのです。
なので、後は1になっているビットの数を数えると、それが元の数(x)内の0である最下位のビットの位置を示すわけです。
面白いですねえ。

_ というわけで、alloc関数に戻って、今度は未使用caseがなかった場合の処理(631行目〜)を見てみましょう。
まず、gc_realloc関数を呼び出して、新しいdrawerを確保しています(632行目)。
ちょっと紛らわしいですが、drawer内のcaseの並びはarenaから確保されますが、その管理領域であるdrawer自体は通常のOS管理下のヒープに取られる、ということになります。
続いて、get_cases関数を呼び出して、drawerの本体であるcaseの並びを確保します(631行目)。

_ get_cases関数の中身(541行目〜)を見ると、どうやらarena(先にも書きましたが大きさは2MBです)内の空きcase並び(大きさは4KBないし8KBです)がまたしてもビットマップ方式で管理されていて、空きがあればそれを返し(545〜552行目)、なければ新しいarenaをmmap(2)で確保して(555行目)その先頭を返しているようです。
arenaの管理領域自体はgc_malloc関数で確保されており(554行目)、各arena管理領域は連結リストで保持されていることが分かります。

_ case並びが確保できたのでalloc関数に戻りましょう。
ビットマップ領域を確保し(637行目)、それと同じ大きさのmarkなる領域を確保し(639行目)、drawerの先頭のcaseを返してallocは終了です。

_ 以上で、slapにおけるメモリの確保をあらかた紹介しました。
ここで説明しなかった、sl_obj_alloc関数内のslap_register_living_list関数呼び出し(823行目)の意味と、alloc関数内で確保したmark領域(639行目)の意味については、GC処理の方で説明することにします。

_ ...が、ここまでで思いのほか話が長くなってしまいました。
肝心のGC処理に辿りつきませんでしたが、続きは次回としたいと思います。
こんな誰得の話を何回にも分けて引きずるのも正直どうかと思いますが...ま、ご容赦を。

◆slapのGC紹介(後編) - Garbage Collection Advent Calendar

_ Garbage Collection Advent Calendar企画、slapのGC実装紹介の後編です。
いよいよGC処理の実体に迫ってみたいと思います。

◆GCの開始

_ 今回も、前編同様、ソースコードを適宜参照しながら話を進めていきます。なんか昨日とちょっとリビジョンが変わってますね :)

_ slapではメモリが足りなくなったとき(491・507行目)や明示的にGC開始が指示された時(835行目〜)にGCが実行されます。
その実体はgarbagecollect関数(448行目〜)ですが、デバッグ用のコードなどを無視すると、その実体は、gc_mark関数を呼んで(477行目)、gc_sweep関数を呼ぶ(480行目)、という、ほんの2行に集約されます。
前編で述べたように、slapのGCは単純なmark&sweep方式を採用しているわけですが、本当にそれしかやってませんね。
まさにシンプル。まさにコンパクト。

_ というわけで、まずはmark処理を見ていきましょう。

◆mark

_ 世の中には保守的なGCとexactなGCとが存在するわけですが、slapでは後者を採用しています。
具体的には、生きている可能性のあるオブジェクトを全部辿ることができるはずのルートを処理系がGCに提供することでexact性を担保しています。

_ そのルートの提供の方法ですが、slapには2つのルートが存在します。
一つは現在のローカル変数スコープ、もう一つはグローバルな変数(定数を含む)のスコープです。
ローカル変数スコープはframeというものに内包されていますが、このframeは新しいローカル変数スコープが生成されるたびに上に積み重ねられ、ローカル変数スコープが終わるたびに取り除かれます。
各frameは自分の下にあるframeを知っているので、これを順次辿ることにより、現在有効な全てのローカル変数スコープにアクセスすることができます。

_ しかし、実際には全てのオブジェクトがローカル変数に格納(バインド)されているわけではありません。
例えば、a = b + c * d;という文を考えると、まずc * dが実行されてその結果の値がオブジェクトとして生成され、次いでbとこれを+した値が生成され、最後に変数aに格納されます。
したがって、c * dの結果は変数に格納されることはないわけで、もしローカル変数に格納されたオブジェクトだけをmark対象にしてしまうと、bとそのオブジェクトの+の段階でGCが走ってしまった場合、あえなくこのオブジェクトは回収されてしまうことになります。

_ そこで、slapでは、ローカル変数スコープ内で生成されたオブジェクトを全部そのframeで覚えておき、仮にこの例のような一時的オブジェクトであっても、そのローカル変数スコープが有効な間は「生きている」とみなしています。
そういう意味ではslapのGCは厳密に「exactである」とは言い難いのですが、ま、安全側に倒しているということになります。
その、生成されたオブジェクトを覚えておく方法ですが、これが前回説明を省略したslap_register_living_list関数呼び出し(831行目)です。
この関数をオブジェクトを引数として呼び出すことにより、現在のframe上に用意されているリストにそのオブジェクトが登録されます。

_ では、以上を踏まえて、mark処理の実体、gc_mark関数を見ていきましょう(383行目〜)。
まずslap_get_living_list関数を呼び出して(391行目)、現在のframe内のオブジェクトのリストを取得しています。一つ目のルートですね。
slap_get_living_list関数は第1引数で対象となるframeを指定し、第2引数で渡したポインタにオブジェクトのリストを返します。
また、戻り値として、第1引数のframeの直下のframeを返します(最下位のframeが渡されたらNULLを返す)。
第1引数に0を渡した場合は、現在のframe、つまり最上位のframeが対象となります。

_ オブジェクトのリストはタプルというデータ構造になっています。
タプルというのは、いろんな定義があるかと思いますが、ここでは、単に順序のある値の並びです。ま、配列のようなものですね。
で、このリストの中身を一個ずつ取り出して(396行目)、即値オブジェクト以外はgc_mark_obj関数を呼び出してmarkしています(401行目)。
これを、最下位のframeに到達するまで繰り返しています。
単純ですね。

_ 一方、もう一つのルート、グローバルな変数のスコープですが、ここに存在するオブジェクトは全てslap_system_objsというタプルに登録されています。
というわけで、406行目からの処理でこの中身も全部舐めて、gc_mark_obj関数を使ってmarkしています(413行目)。

_ というわけで、以上で全ての生存オブジェクトがmarkできるはずです。

_ では、実際にどのようにmarkを行っているのか、gc_mark_obj関数を眺めて見ましょう(352行目〜)。
まず、find_drawer関数を使って、そのオブジェクトが所属するdrawerと、drawer内のインデックスを取得します(359行目)。
find_drawer関数の中身(160行目〜)ですが、各drawer(内のcaseの並び)は連続したメモリなので、渡されたポインタがその中にあるかどうかで単純に判定が可能です(174行目)。
gc_mark_obj関数に戻って、もし所属するdrawerが見つからなかったり(360行目)、drawer内の該当インデックスが未使用であったり(364行目)したら、それはバグなので死にます。
また、そのオブジェクトが既にmark済みであれば、何もしなくていいのでそこで処理を終了します(369〜372行目)。
さて、ここで前回説明を省略したmark領域が登場しました。
まあ、皆さん承知していただろうと思いますが、このmark領域ビットマップを利用して、オブジェクトのmarkが行われているわけです。
あとは、まず自分自身をmarkして(375行目)、自分が参照しているオブジェクトをmarkして(378〜381行目)、mark処理は終了です。

_ ところで、slapオブジェクトなるものの実体は、3つのハッシュテーブルです。
このハッシュテーブルはslotsと呼ばれており、slots内の各ペア(slot)は名前(Symbol)とその値から成り立っています。
この各々のslotこそが、ずばり、オブジェクトのインスタンス変数の実体です。
なぜslotsが3つもあるのかというのは、slapの内部構造を説明する必要が出てくるのですが、誰もslap言語自体には興味は無いだろうと思うので割愛します。そういうもんだと思ってください。

_ gc_mark_slots関数(272行目〜)では、このslotsの中身を順次確認して、値がオブジェクトの場合はまたmark処理を行います。
実際にとあるslotの値がオブジェクトかどうかは、slapの場合、名前を見ればわかるようになっています(285・345行目)。
具体的には、名前の1文字目が+か-であれば非オブジェクトです。
というわけで、それ以外の名前で、かつ、即値オブジェクトでなければgc_mark_obj関数を呼び出してmarkしています(347行目)。
非オブジェクトな値の場合でも、その中にオブジェクトを含んでいる場合がありえます。
名前の2文字目を見ればその値がどんな構造のデータかわかるようになっているので(287行目)、もし中にオブジェクトを含んでいるデータ構造の場合は、それらも順次markしています(296・309・312・328行目)。

_ 以上でmark処理は終了です。
slapの仕組みに由来する部分がちょっと説明不足でわかりにくかったかもしれませんが、それを除けば本当に順繰り走査をしてるだけの単純な内容でした。

◆sweep

_ では、今度はsweep処理の実体、gc_sweep関数を見てみましょう(417行目〜)。

_ sweepの対象となるのはslapオブジェクトのみなので、見る必要があるcabinetは0番のみです(422行目)。
このcabinet内の全drawerをfor文(425行目)で順次見ていきます。
まず、そのdrawer内の解放すべきオブジェクトのリストを生成する必要があるのですが、これは428行目からの処理で行われています。
ビットマップが複数あるのでforループになっていますが、実質的には430行目がそのリスト生成処理です。
mark領域では、markされたオブジェクトについてビットが立っています(1になっています)。
なので、それを反転(~)すると、markされなかったオブジェクトについてビットが立ちます。
これをbmp領域、つまり現在生きているオブジェクトについてビットが立っているリストと論理積(&)を取ってやると、既に使われていない、解放されるべき定めのオブジェクトのリストが出来上がります。

_ それはいいんですが、そうして得られたリストをbmp領域に代入しちゃっていますね。いいんでしょうか?
実際に不要なオブジェクトを全部殺し終わると、生きているのはmarkされていたオブジェクト、ということになります。
ということは、mark領域の値をbmp領域に書き戻してやれば、無事に生きているオブジェクトのリストが復元できるわけです。
なので、mark領域を残しておきさえすれば、ここでbmp領域を解放用のワークエリアとして使っちゃっても大丈夫なんですね。
実際のmark領域からbmp領域への書き戻し処理は440行目にあります。
また、その後でmark領域を再び初期化する必要がありますが、この処理は442行目にあります。

_ 最後に、free_drawers関数を引数0で呼び出してgc_sweep関数は終わりです(445行目)。
free_drawers関数は655行目からですが、666行目のif文によると、引数でdrawerが指定された場合はそのdrawerのみを見て、0(NULL)が渡された場合は全てのdrawerを対象にするようです。
ということを踏まえておいて、三重のfor文でやな感じですが、頭から眺めてみましょう。
まず1つ目のfor文(661行目)で全cabinetを順次頭から見ています。
続いて2つ目のfor文(663行目)でcabinet内の全drawerを見ていきます。
3つ目のfor文(670行目)は使用中caseの有無をbmp領域を見て確認するためのものですね。使用中caseがあれば即座にfor文を中断しています(671〜673行目)。
で、結局使用中caseがなかった場合(675行目)、つまりdrawerの中身が空だった場合ですが、そのdrawerのbmp領域とmark領域を解放して(677〜678行目)、free_cases関数を呼んでcase並びをarenaに返却して(679行目)、このdrawerがなくなったので以降のdrawerを詰めて(680〜683行目)めでたしめでたしです。
これをdrawer数文繰り返して、最終的にcabinetが空っぽになっちゃった場合は(687行目)、cabinetのdrawer管理領域も解放しています(689行目)。

_ case並びのarenaへの返却処理であるfree_cases関数も見ておきましょう(568行目〜)。
ここでは、連結リストになっているarenaを頭から順次見ています(575行目〜)。
無事に引数ptrの属するarenaが見つかったら(576行目)、そのインデックスをアドレスを利用して算出して(578行目)、使用中ビットをリセットします(582行目)。
返却自体はこれで終了なのですが、ここでさらにarena内にまだ使用中のcaseがあるかどうかをbmp領域を見て確認しています(583〜587行目)。
ついさっきfree_drawers関数内で見たのと同じループですね。
で、もし空なら(588行目)、munmap(2)でarena自体をOSに返して(589行目)、連結リストを詰めて(590〜595行目)、このarenaの管理領域を解放しています(596行目)。
case並びの属するarenaが空であってもなくても、いずれにせよこれで返却処理は終了なのでreturnしちゃいますが(598行目)、もし引数で指定したcase並びがどのarenaにも所属していなければ...当然、バグですよね(602行目)。

_ 以上でsweep処理は完了...じゃ、ありませんでした。オブジェクト自体の解放処理、gc_free_obj関数の呼び出しがあったのに(436行目)、中身をまだ見ていませんね。
しかし、この関数(240行目〜)も処理自体は単純なので、さっくり見ていきましょう。

_ gc_free_obj関数は引数としてdrawerのインデックスとdrawer内のcaseのインデックスを取ります。
なので、まず最初にこれを使って実際のオブジェクト(を指すポインタ)を取得します(248行目)。
slapのオブジェクトはファイナライザを持つ場合がありますので、もしあればこいつを呼び出します(250〜254行目)。
その後、オブジェクト実体である3つのslotsをそれぞれ解放します(256〜267行目)。
最後にオブジェクトが占めていた領域を初期化して(269行目)終了です。

_ なお、各slotsの中身の解放はgc_free_slots関数の呼び出し(257・261・265行目)で行われますが、この関数の中身(190行目〜)はそれぞれの値の構造に応じた解放処理を呼び出すだけなので詳細は省略します。
なお、一部の値はその内部にslapオブジェクトを含んでいる場合がありますが、各解放処理はそれらのオブジェクトの解放自体は行っていません。
なぜかというと、そうしたオブジェクトは他のオブジェクトからはまだ参照されている可能性があるので無条件に解放はできませんし、また、仮にどのオブジェクトからも参照されていなければ、結局sweep処理の中のどこかで解放されるわけなので、いちいち中身を見る必要は結局ないためです。

◆まとめ

_ 以上、前後編の2回に渡って、slapのGC処理について駆け足で眺めてみました。
作者は何の文献も参照せずにこのGCを書き下ろした(*1)らしく、一部、一般的でない用語が使われたりもしていたかと思いますが、そうした部分とslapという言語処理系に依存した部分を除けば、全体としては、シンプルで比較的わかりやすい構造のGCだったと思います。

_ 今時、自分でGCをゼロから書き下ろす機会はそうそうないでしょうし、あったとしてもわざわざやるべきものとも思えません。
とはいえ、もしあなたが本当にGCに興味を持っているなら(こんな記事を読んでるならそうに決まっていますが)、独自のGC実装にチャレンジしてみてはいかがでしょうか。
だいじょーぶ、何の知識もなくても、簡単なGCなら、これまで見てきたように、単純な処理の積み重ねであっさり書けちゃいます。
そして、凝ったことをしたければ、そこから改良を積み重ねていけばいいのです。
凝ったことをするのに必要な知識は、実際にコードを書きながら必要に迫られてその辺の資料(ソースコードとかblogとか本とか論文とか)をつまみ食いしていけば、自然と身に付いていきます。

_ 今回の紹介を読んで「私にもGCくらい書けるかも」と皆さんに思っていただけたら幸いです。
また、「俺ならもっといいGCが書けるぜ！」と思った方は、ぜひ今すぐチャレンジしてみて下さい。

_ 以上、長々とこんな誰得な話に付き合って頂き、ありがとうございました。