情報科学実験II資料 (8)
Garbage Collection

田浦

19/11/98

Garbage Collection (GC)の概要

GCの行なうべきことは単純で, GCが終了した後も必要とされるオブジェクトを 保存しつつ, そうでないオブジェクトが占める領域をこれからのメモリ割当の ために再利用できるようにすることである.(注)

「GCが終了した後も必要とされるオブジェクト」を正確に求めることは明らかに決 定不能なので, ほとんどのGCは以下の条件から「到達可能」と証明できるオブ ジェクトを保存し, そうでないものをゴミとみなす.(注)

つまり, スタックやレジスタを根とした, グラフのtraverseを行なうのがGCで ある.

したがってGCのための基本的な要請は, GC開始時にレジスタ上にある各wordや オブジェクト中の各wordがポインタか否か判断できること, およびあるポイン タが与えられた時にそのポインタが指す範囲(つまりオブジェクトの先頭と末 尾)がわかることである. 具体的にいえば,

  1. GC起動時における各生きているregister上のwordがポインタか否かが判 断できる.
  2. あるポインタが与えられた時, そのポインタが指すオブジェクトの先頭 が発見できる.
  3. あるポインタが与えられた時, そのポインタが指すオブジェクトの末尾 が発見できる.
  4. あるオブジェクトが与えられた時, オブジェクト内の各wordがポインタ であるか否かが判断できる

前提作り

上の条件は, 我々のシステムでは以下のように満たされている.

ヒープオブジェクトのformatについて

上のtag wordについて, 少し詳しく述べておく. あるオブジェクトの先頭アド レスaが与えられた時, その手前の2 machine word (= 1 Min-Scheme\ word)をそのレコードの先頭および大きさを知るためのtagとして余分に割り当てる. つまり, Min-Scheme の

(cons x y)
によって作られる実際のレコードのformatは, のようになる. そして, 図のT1は, 他のどんなMin-Scheme データの下位 wordとも識別可能なtagをつけておく. 具体的には, 下位2 bitとして10 を用いてさらに, 論理値や空リストと衝突しないためのtagをつける.

これによってあるポインタrが与えられた時に, (rref r -1), (rref r -2)と順にtag wordを示すデータが登場するまで読んでいけば, 先 頭が発見できる. そして, そのtag wordのうちの上位wordにそのオブジェクト の大きさを書いておけば, そのオブジェクトの末尾が発見できる.

スタックオブジェクトに関しては, 末尾は常に一定であり, 先頭はGC開始時 のレジスタに入っているので, tag wordは必要ない.

抽象的なGarbage Collection Algorithm

GCにはmarkingまたはcopyingというデータ構造による区別から, generational GC, incremental GCなど, 様々な種類があるが, およそどんな GCにも共通する事項がある.

Tri-color Abstraction

GCのアルゴリズムを, 以下のようにオブジェクトに「色を塗っていく」プロセ スと見るとわかりやすい.

まだGCに発見されていないオブジェクト
灰色
GCに発見されたが, まだ「直接」白オブジェクトを指している かも知れないオブジェクト
GCに発見され, かつ指しているオブジェクトはすべて黒か灰色

およそどんなGCも以下のように動作する.
すべてのオブジェクトを白にする;
レジスタ, スタックなどのルートオブジェクトを灰色にする;
while (灰色オブジェクトが存在する) {
   g = 一つ灰色オブジェクトを取り出す;
   g が直接指す白オブジェクトを灰色に塗る;
   g を黒に塗る;
}
基本的なこととして, まずオブジェクトの色は時間とともに濃くなっていくこ とは見やすい. そしてGCが保っているinvariantは,
黒 → 白のポインタは存在しない
ということで, GC終了時に灰色が存在しないため, GC終了時には黒が直接指す オブジェクトは黒だけになる.

これと,

ルートオブジェクトは初期状態で灰色
という条件から, GC終了時には,
ルートオブジェクトは黒 and 黒が指すのは黒
というわけで, 黒オブジェクトだけがルートオブジェクトから到達可能なオブ ジェクトということがわかる.

したがってGCを設計するのにも必要な操作は,

Copying GC

後で詳しく述べるが, ヒープを半分にわけ, 半分が埋まったところでGCを起動 する. その時点でもともとのヒープがfromspace, もう一方の(初期状態で空 の)ヒープを, tospaceと呼ぶ. tospaceはqueueになっており, 白オブジェクト を灰色に塗るという動作は, fromspaceからtospaceの一方の端にcopyすること で達成される. 灰色オブジェクトを取り出すという操作は, tospaceのもう一 方の端からオブジェクトを取り出すことで達成される.

実装するのは単純で, heapの使用率は常に50%であるので, fragmentationを 避けるなどの考慮事項は一切必要ない. また, allocation (heap limit check)が素早く行なえる. また, GCアルゴリズム自身は途中, constantで押え られないstorageを全く必要としない.

Marking

Markingはしばしばmark and sweepとも呼ばれるが, 良いGCではsweepをlazyに 行なうなどの改良がなされており, 現代的な用語としてはあまり正しくない.

Markingはある意味ではもっと素直なもので, 各オブジェクトに1 bitのmark bit (これはオブジェクトのheader部に持つことも可能だが, 別個にbit mapを 用意するのが普通)を設け, あるオブジェクトを灰色に塗る操作はそのオブジェ クトをmarkすることで, 白でないことが即座に判定できるようにする. これと は別個に灰色オブジェクトへのポインタのみを管理するデータ構造を, 管理す る(通常はstackとして実現され, mark stackと呼ばれる). 灰色に塗る操作は mark bitをたてるとともに, mark stackに挿入することで行なう. 一般にmark stackの大きさをGC開始時に定数で予測するのは難しい.

Markingではオブジェクトをコピーしない. したがってGC終了後再利用可能な 領域はヒープ上の連続した領域とはならない. このため, allocationはfree list (利用可能な領域をlinkしたもの)を用いて行ない, かつfragmentationを 避けるための工夫が必要になる. Fragmentationを避ける一つの工夫は, サイ ズごとに割り当てる領域をかえて, 同じサイズのオブジェクトを連続した領域 に割り当てることである. こうすれば, 小さなオブジェクトに大きなオブジェ クトが邪魔されることがなくなる.

Copying GCに比べると, memory参照の特徴は良いことが多いが, allocation algorithmが複雑になる, fragmentationを避けるためにはmemoryが多く必要に なる, など, 資源の厳しいCPUには不向きな点が多い.

Incremental GC

Incremental GCはmarking中にもuserプログラムが動作を可能にするもので, これによってGCのpause timeが短くすることが可能になり, real time GCな ども可能になる.

基本的な問題点は, 上のGCのinvarinat:

黒 → 白のポインタは存在しない
が, userプログラムによって崩されてしまうことがある点である(つまりuser プログラムががヒープオブジェクトの書換えを行なうことで, 黒 → 白のポ インタが発生し得る).

このinvariantを保つための方法はいくつかあるが, 簡単にはユーザプログラ ムがポインタの書換えを行なう時に,

のどちらかを行なう.

Min-Scheme のCopying Garbage Collection

Heapの構成

Heapは図のようになっている.

Heapの解説図

二つの同sizeの領域A, Bにわかれており, 常にどちらかの領域をactive な領域と呼び, activeでない方は空である. Activeな領域の先頭(B)からある ところ(h)まではすでにobjectが割り当てられており, そこから領域の最後 (E)まではまだobjectが割り当てられていない. Allocationはhが指す場所か ら行なわれる.

GCの概要

Global変数, register, およびstackをrootとして, pointerを通してたどれる ものだけを空の領域へ移していく. 全てを移し終った時点で終りであ る. Stackは, 全体を大きな一つの生きているレコードとみなし, かつcopyは しない(freeされる領域があるわけではないのでcopyは無駄). 同様にglobal変 数やレジスタもそれ自体を一つのrecordとみなすと考えやすい.

Copying GCではヒープオブジェクトが白から灰色に変わる時, そのオブジェク トのアドレスが変化する. したがって同じオブジェクトを指す他のポインタも GCの最終時には, 黒の方を指しておくようにしなくてはならない. 具体的には,

黒オブジェクトは, 古いアドレスを指さない,
というinvariantを保つようにする. したがって, ある灰色オブジェクトを黒に塗りかえる時に, ポインタをupdate すれば良い. この操作を, ポインタのforwardingと呼ぶ.

GC中, 二つのポインタをkeepする. それらはtospace中を指している.

scanned:
これより下位のオブジェクトはすべてforwardされており, 白オブジェクトも, いかなるオブジェクトのcopy前の方も指さない.
unscanned:
scannedからunscannedのあいだのオブジェクトはcopyさ れているが, まだ, 白オブジェクトや, 他のオブジェクトのcopy前の方を指す かも知れない.

言い替えれば, tospaceの底から, scannedまでの間が黒オブジェクト, scannedからunscannedの間が, 灰色オブジェクトである. ここから, どうやっ て灰色オブジェクトを一つ取り出したり付け加えたりすれば良いかはやさしい でしょう.

[1]はGCに対する良い紹介である. その中のcopying collectionの章を参照.

References

1
Andrew W. Appel. Garbage Collection, chapter 4, pages 89-100. The MIT Press, 1991.

付録: GC in Min-Scheme のリスト(全くいい加減)

もしFIXSを使うMin-Scheme をはじめにimplementするならば, GCのアルゴリズム自 身をそれで書くことによる, 興味深いbootstrapが可能になる. いくつかのご くごくlow levelの情報収集関数を外部関数として準備しておいて, アルゴリ ズムの大部分はMin-Scheme で書くのである. もちろんGCの最中はheap割当を しないなどの考慮が必要になるが, それはcontinuationをstackに割り当てれ ば可能である.

Convention: 大文字の関数はexternalなassembly routine (Schemeで定義不 可能).

;;;
;;; Header is written just before the 0th element.
;;;

(define (record-header r)
  (record-ref r -1))

(define (set-record-header! r h)
  (record-set! r -1 h))

;;;
;;; Extrinsic function P+
;;; (P+ record nwords) returns a record pointer which is as if allocated
;;; next to the RECORD whose has NWORDS Scheme words
;;;

;;;
;;; Header word contains the following information:
;;; (1) Number of words in the record
;;; (2) A flag which tells if the record has been copied in a collection
;;; (3) A forwarding pointer, if the record has been copied
;;; We assume there are extrinsic function called
;;; RECORD-HEADER-NWORDS, RECORD-HEADER-ALREADY-COPIED?,
;;; and RECORD-HEADER-FORWARDING-POINTER, which are trivially implemented
;;; as assembly function (or CPS16 function if a parser for CPS16 is
;;; implemented)
;;;

;;;
;;; Size (number of elements) of a given record.
;;;

(define (record-nwords r)
  (RECORD-HEADER-NWORDS (record-header r)))

;;;
;;; FORWARD every element of record R
;;;

(define (forward-record-iter r i n)
  (if (= i n)
      0
      (begin
        (record-set! r i (copy-object (record-ref r i)))
        (forward-record-iter r (+ i 1) n))))

(define (forward-record r)
  (let ((n (record-nwords r)))
    (forward-record-iter r 0 n)
    (SET-SCANNED! (P+ r n))))

;;;
;;; FORWARD every element of record R
;;;

(define (forward-reg-dump-iter r i n live-reg-map)
  (if (= i n)
      0
      (begin
        (if (= 1 (LIVE-REG-MAP-REF live-reg-map i))
            (REG-DUMP-SET! r i (copy-object (REG-DUMP-REF r i))))
        (forward-reg-dump-iter r (+ i 1) n live-reg-map))))

(define (forward-reg-dump r live-reg-map)
  (forward-reg-dump-iter r 0 NREGISTERS live-reg-map))

;;;
;;; Block copy function
;;;

(define (copy-mem-iter src dest i n)
  (if (= i n)
      0
      (begin
        (record-set! dest i (record-ref src i))
        (copy-mem-iter src dest (+ i 1) n))))

(define (copy-mem src)
  (let* ((n (record-nwords src))
         (dest (MAKE-UNINITIALIZED-VECTOR n)))
    (SET-UNSCANNED! (P+ dest n))
    (copy-mem-iter src dest 0 n)))

;;;
;;; COPY, given R is a heap-allocated record
;;; ALREADY-COPIED? returns #t if header of R tells R has already been
;;; copied during this collection.
;;; (COPY-MEM R S) is an extrinsic function which just allocates S
;;; machine words and copy the contents of R to the new record, and returns
;;; the pointer to the new record.
;;;

(define (copy-record r)
  (let ((h (record-header r)))
    (if (RECORD-HEADER-ALREADY-COPIED? h)
        (RECORD-HEADER-FORWARDING-POINTER h)
        (let* ((r-prime (copy-mem r)))
          ;; put forwarding pointer
          (set-record-header! 
           r (MAKE-ALREADY-COPIED-HEADER s r-prime))
          r-prime))))
          
(define (copy-object o)
  (if (HEAP-RECORD? o)          
      ;; #t if this is a heap-allocated record
      (let ((ho (record-head-offset o)))
        ;; get the head of the record, copy it, and offset it back 
        (P+ (copy-record (P+ o (- 0 ho))) ho))
      o))

;;;
;;; Forward until done
;;;

(define (forward-until-done)
  (if (eq? SCANNED UNSCANNED)
      0
      (begin
        (forward-record SCANNED)
        (forward-until-done))))

;;;
;;; Forward all frames in stack
;;;

(define (forward-stack-iter frame bottom)
  (if (eq? frame bottom)
      0
      (begin
        (forward frame)
        (forward-stack-iter 
         (P+ frame (record-nwords frame)) bottom))))

(define (forward-stack top)
  (forward-stack-iter top STACK-BOTTOM))

;;;
;;;
;;;

(define (flip-space)
  (let ((to TO-SPACE-HEAD)
        (from FROM-SPACE-HEAD))
    (SET-TO-SPACE-HEAD! from)
    (SET-FROM-SPACE-HEAD! to)))

(define (set-heap-pointers)
  (SET-HEAP-POINTER! SCANNED)
  (SET-HEAP-LIMIT-POINTER! 
   (P+ TO-SPACE-END (- QUICK-HEAP-CHECK-MAX))))

;;;
;;; GCMAIN takes three records as parameters
;;;

(define (gcmain stack-top globals reg-dump live-reg-map)
  (forward globals)
  (forward-reg-dump regs live-reg-map)
  (forward-stack stack-top)
  (SET-SCANNED! TO-SPACE-HEAD)
  (forward-until-done)
  (set-heap-pointers)
  (flip-space))

;;;
;;; GC: look like what follows.
;;; When this is invoked, general purpose registers R[0]--R[n-1] hold
;;; function parameters and register T called temporary register holds
;;; the code address from which GC is invoked and from which the
;;; computation will be restarted.
;;;
;;; We call GCMAIN after saving registers
;;;

(GC:
 ;; first save registers in a record
 (record-set! (label REG-DUMP) 0 n)
 (record-set! (label REG-DUMP) 2 R[0])
 (record-set! (label REG-DUMP) 4 R[1])
 (record-set! (label REG-DUMP) 6 R[2])
    ...
 (record-set! (label REGS) 2n R[n-1])
 ;; save continuation of GCMAIN
 (record-set! (label GCCONT) 2 T)
 ;; setup arguments 
 ;; (gcmain gcmaincont stack-top globals reg-dump live-reg-map)
 (record-ref (label GCMAIN) 0 R[0])
 (record-ref (label GCMAINCONT) 0 R[1])
 (move SP R[2])                         ; stack pointer
 (record-ref (label GLOBALS) R[4])      ; globals
 (record-ref (label REG-DUMP) R[6])     ; reg-dump
 (record-ref T -1 R[8])                 ; live-reg-map
 (jump (label GCMAIN:)))                ; jump into GAMIN

(GCMAINCONT:
 ;; restore registers
 (record-ref (label REG-DUMP) 0 n)
 (record-ref (label REG-DUMP) 2 R[0])
 (record-ref (label REG-DUMP) 4 R[1])
 (record-ref (label REG-DUMP) 6 R[2])
    ...
 (record-ref (label REG-DUMP) 2n R[n-1])
 ;; resume the invoker
 (record-ref (label GCMAINCONT) 2 T)
 (jump T))

...ために再利用できるようにすることである.
ここでオブジェクトと は我々の文脈(Min-Scheme) においてはheap, stack, または roffs命令によって割り当てられたレコードのことであるが, この資料では一 般的な用語であるオブジェクトを用いる.
...そうでないものをゴミとみなす.
MLの型システ ムを用いた, より進んだGCもこの世には存在する.
 

 

〔トップページへ〕 〔「コンパイラ演習レジュメ」のindexページへ〕
<vu@is.s.u-tokyo.ac.jp>

Last updated on 11 May, 1999