32 ビット版 Squeak の GC

SqueakVMstop-the-world非インクリメンタルな 2 世代 mark-sweep-compact GC を採用しています。以下、32 ビット版の GC についてのメモ。この GC は、実行速度を若干犠牲にしてでも、メモリーの消費を抑えるように作られていました。(9日、メソッド incrementalGC の名前とまぎらわしいので、インクリメンタルという表現を削ることにしました)

  1. memory の配置(アドレスの小さな方から大きい方向へ向けて)
    • | old space | young space | freeBlock | forwarding block table |
    • 新しくオブジェクトのチャンク(下記)を割り当てるときは、freeBlock の先頭から切り出します。freeBlock がチャンクのサイズに満たないときは、young space だけを対象にした incrementalGC がおこなわれ、それでも足りないときは old space と young space の両方にまたがる fullGC がおこなわれます。それでも足りないときは、memory を拡張します。
    • 直前の GC 時からオブジェクトを閾値個数以上作成すると、memory に余裕があっても強制的に GC をおこないます。
    • old space 内のオブジェクト A のフィールドに young space 内のオブジェクト Y への参照を格納すると、オブジェクト A をリメンバー・セットに登録します。リメンバー・セットは、ObjectMemory のインスタンス変数 rootTable が束縛されている配列オブジェクトを使用します。オブジェクトを二重登録しないように、リメンバー・セットへ登録済みのオブジェクトは、その baseHeader の RootBit がセットされます。
    • old space と young space の間にギャップはなく、チャンクが連続して続いていきます。
    • young space の先頭アドレスに、ObjectMemory のインスタンス変数 youngStart を束縛しています。
    • youngStart は incrementalGC の後で条件が成立したときに freeBlock の先頭アドレスに更新され、その時点で生き残っている object を old space に殿堂入りさせます。条件は、incrementalGC で生き残ったオブジェクト数がスレッショルドを越えたときか、またはリメンバー・セットがあふれかけているときです。このとき、リメンバー・セットはクリアされます。
    • fullGC をおこなうときは、youngStart を memory の先頭をさすように変更します。fullGC が終わると、youngStart は freeBlock の先頭をさすように変更されます。
    • オブジェクトは相互に直接参照され、コンパクトのときにアドレスの付け替えがおこなわれます。forwarding block table は GC のアドレスの付け替えに使う作業領域です。
  2. GC が実行されていないときのオブジェクトの内容(アドレスの小さな方から大きい方向へ向けて)
    • | sizeHeader | classHeader | baseHeader | fields | weak pointers | bytes |
    • baseHeader に MarkBit などの管理情報が格納されます。
    • sizeHeader と classHeader は省略できます。3 つの Header の LSB 2 ビットでどのヘッダが存在しているかを表し、3 つの Header の LSB 2 ビットはすべて同じパターンが格納されます。
      1. 0b00 − sizeHeader と classHeader の両方があるオブジェクトです。
      2. 0b01 − classHeader があるオブジェクトです。この場合、オブジェクトのサイズを baseHeader のビットフィールドに格納します。
      3. 0b10 − freeChunk であり、sizeHeader と classHeader は両方ともありません。baseHeader の MarkBit (MSB) を除くビットフィールドに、このチャンクのワード数を保持します。memory の最後の freeChunk が freeBlock になります。なお、mark フェーズ実行中に、field のスキャン終了アドレスを判定可能にするため、生存中のオブジェクトであるにもかかわらず、baseHeader の LSB 2 ビットを 0b10 に一時的に書き直します。
      4. 0b11 − sizeHeader と classHeader が両方ともないオブジェクトです。
    • オブジェクトの参照(oop)は baseHeader のホスト・プロセッサの論理アドレスで表します。
    • sizeHeader や classHeader が存在する場合、オブジェクトの割り当て領域の先頭論理アドレスoop よりも 4 バイト、または 8 バイト小さくなります。この先頭アドレスのことを chunk と呼びます。
    • classHeader がもし存在するときは、オブジェクトのクラスのインスタンスへの参照アドレスが入ります。存在しないときは、baseHeader の CompactClass ビットフィールドを利用します。このビットフィールドの値は、頻繁に使われるクラスの oop を格納した配列のインデックスになっています(必ず classHeader を利用するようにもできる)。
    • fields と weak pointers と bytes のそれぞれも省略できますが、順番は必ずこうなります。なお、bytes 領域には決して pointer は含まれません。これらのどれが格納されているかは、baseHeader の fmt ビットフィールドを見ればわかります。
    • fields は pointer が順に並びます。
    • pointer は参照しているオブジェクトの oop が格納されます。オブジェクトはホスト・プロセッサのワード境界から始まり、pointer の LSB 2 ビットは必ず 0b00 になります。
    • 特殊な pointer として、ワード長より 1 ビット短い 31 ビットの符号付整数を格納することができます。整数を格納する際、オブジェクトへの参照と区別するために LSB 1 ビットを 1 にします。整数値は単純に左に 1 ビット分シフトしてあるだけです。
  3. mark フェーズ
    • スキャンの起点には、Interpreter が保持するたくさんの特別な参照と、リメンバー・セット rootTable の内容と、remapBuffer の内容の 3 種類を使います。
    • remapBuffer は、GC の前後で引き続き利用したい oop を保管しておく場所で、スタックになっています。例えば、新オブジェクトを割り当てる際に、そのオブジェクトのクラス・インスタンスoop をプッシュしておきます。そして、GC の後にコンパクトで移動されて別のアドレスに更新された oop をポップして利用することができるようになっています。
    • youngStart よりも大きな oop で参照できるオブジェクトのみの MarkBit を 1 に変更します。
    • Deutsch-Schorr-Waite ポインタ反転アルゴリズムの変種を採用しています。
    • mark フェーズ中、オブジェクトの classHeader、baseHeader と pointer を持つ field は書き換えられます。mark フェーズを終了した段階で、baseHeader の MarkBit を除いて、すべてが元に復元されます。
    • オブジェクトの最後の field からアドレスが小さい方向へ順に pointer をスキャンしていきます。weak pointer と bytes は mark 対象を探すときに使いません。field 内の符号付整数もスキャン対象から外します。もし classHeader が存在するときは、それを最後にスキャンします。
    • ObjectMemory のインスタンス変数 parentField、field、child の 3 つを使い、現在辿ってきた pointer を逆に付け替えて parentField から元へ辿れるようになっています。反転リンク・リストの終端は GCTopMarker = 0x00000003 で表します。
    • parentField と反転リンクが field をさすときは LSB が 0 に、classHeader をさすときは LSB が 1 になります。
    • field をスキャン中のオブジェクトの baseHeader の LSB 2 ビットは 0b10 に差し替えられます。オブジェクトに含まれる(classHeader も含めて)すべての pointer をスキャンしおえた後に、baseHeader の LSB 2 ビットは(baseHeader のビットフィールドを参照して)元の値に復元します。
  4. sweep フェーズ
    • mark が終わると、コンパクトの前に必ず sweep フェーズをおこないます。
    • memory の先頭から全チャンクをスキャンしていき、MarkBit が 0 のチャンクを freeChunk に変更していきます。このとき、連続した freeChunk をひとまとめにして連結します。
    • MarkBit が 1 で weak pointer を持つオブジェクトを見つけると、weak pointer の参照先が生存しているかどうか確認して、生存していないときは weak pointer を nil にし、finalize シグナルを発行します。
    • 最初の freeChunk のアドレスを求めて、どこからコンパクトをおこなえば良いかを決定します。
    • sweep フェーズの終了時点で、すべての MarkBit はクリアされ、どこからも参照されていないオブジェクトはすべて freeChunk へ変更されています。
  5. compact フェーズ
    • コンパクトは、forwarding address の計算、ポインタの更新、チャンクの移動の順に進行します。
    • forwarding address の計算によって、生存しているオブジェクトのうち移動の対象になっているすべてのオブジェクトの baseHeader が書き直されます。書き直されると MarkBit が 1 になり、MarkBit と LSB 2 バイトを除くビットフィールドに、対応する forwarding block のアドレスが格納されます。forwarding block は 2 ワードで構成され、最初のワードに移動先の論理アドレスが、続くワードにオリジナルの baseHeader の内容が退避されます。
    • ポインタの更新では、mark フェーズの全起点の参照(Interpreter が保持するたくさんの特別な参照と、リメンバー・セット rootTable の内容と、remapBuffer)を移動先のアドレスに変更し、続いて memory の先頭から順に freeChunk を除くすべてのオブジェクト中の pointer、weak pointer、classHeader を移動先のアドレスに変更します。
    • 最後に、memory の先頭から、移動対象のチャンクを移動先に移し替えます。移動対象かどうかは baseHeader の MarkBit が 1 になっているかどうかで区別がつきます。移動し終えたら、チャンクごとに、forwarding block に退避しておいたオリジナルの内容から baseHeader を復元します。MarkBit もこのときクリアされます。
    • コンパクトは、forwarding block table におさまり切る分を一度におこないます。もしもおさまりきらなかったときは、まだコンパクトされていないチャンクの先頭を記録しておきます。incrementalGC のコンパクトでは、forwarding block table があふれることはないため、一度で完了しますが、fullGC のコンパクトでは一回では終わらないかもしれません。そのときは、引き続きコンパクトを繰り返して、すべてのチャンクを移動します。
    • コンパクトが終了すると、memory の先頭から freeBlock の直前まで、生存しているオブジェクトが隙間なく詰め込まれます。また、すべてのチャンクの MarkBit はクリアされており、baseHeader の内容は GC の開始前に復元されます。