言語の GC 機能と参照カウント (後編-1)

ReferenceCounting GarbageCollection CycleCollector

追記: 最後の図の「C」の参照カウントが 1 ではなく 2 になっていたのを修正

次回は cycle collector の実装と、回避方法について書く予定。

言語の GC 機能と参照カウント (中編)

と 2008 年の 5 月 31 日に書き残して早 1 年と 2 ヶ月を迎えようとする中の後編です。

Cycle collector の実装方法について

Bacon らによる「Concurrent Cycle Collection in Reference Counted Systems」という論文が有名と思われる。この論文では、まず同期的な cycle collector の実装の改善について述べ、さらにそれを非同期的な方式へ拡張する方法について述べている。今回は、最初の同期的な方法のアルゴリズムについてのみ見ていく。

基本的には mark and sweep

論文には以下のような説明と pseudo-code が載っていて、この通り実装すればまあ動くようにはなっているが、これだけではすぐに背後のロジックを理解するのは難しいのではないかと思う。

3.1 Pseudocode and Explanation
We now present detailed pseudocode and an explanation of the operation of each procedure in the synchronous cycle collection algorithm.

In addition to the buffered flag, each object contains a color and a reference count. For an object T these fields are denoted buffered(T), color(T), and RC(T). In the implementation, these quantities together occupy a single word in each object.

All objects start out black. A summary of the colors used by the collector is shown in Table 1. The use of green (acyclic) objects will be discussed below.

Color Meaning
Black In use or free
Gray Possible member of cycle
White Member of garbage cycle
Purple Possible root of cycle
Green Acyclic
Red Candidate cycle undergoing computation
Orange Candidate cycle awaiting epoch boundary 
Increment(S)
  RC(S) = RC(S) + 1 
  color(S) = black

Decrement(S)
  RC(S) = RC(S) - 1
  if (RC(S) == 0)
    Release(S)
  else
    PossibleRoot(S)

Release(S)
  for T in children(S)
    Decrement(T)
  color(S) = black
  if (! buffered(S))
    Free(S)

PossibleRoot(S)
  if (color(S) != purple)
    color(S) = purple
  if (! buffered(S))
    buffered(S) = true
    append S to Roots

CollectCycles()
  MarkRoots()
  ScanRoots()
  CollectRoots()

MarkRoots()
  for S in Roots
    if (color(S) == purple)
      MarkGray(S)
    else
      buffered(S) = false
      remove S from Roots
      if (color(S) == black
          and RC(S) == 0)
        Free(S)

ScanRoots()
  for S in Roots
    Scan(S)

CollectRoots()
  for S in Roots
    remove S from Roots
    buffered(S) = false
    CollectWhite(S)

MarkGray(S)
  if (color(S) != gray)
    color(S) = gray
    for T in children(S)
      RC(T) = RC(T) - 1
      MarkGray(T)

Scan(S)
  if (color(S) == gray)
    if (RC(S) > 0)
      ScanBlack(S)
    else
      color(S) = white
      for T in children(S)
        Scan(T)

ScanBlack(S)
  color(S) = black
  for T in children(S)
    RC(T) = RC(T) + 1
    if (color(T) != black)
      ScanBlack(T)

CollectWhite(S)
  if (color(S) == white
      and ! buffered(S))
    color(S) = black
    for T in children(S)
      CollectWhite(T)
  Free(S)

特に、この色の使い方はなんぞと思うわけで、例えば黒は「使われているか解放済み」という説明があるが、一見すると何の事かよくわからない。この記事を書くにあたり、よくよくコードを眺めてみたら、オブジェクトの状態として大事なのは

a. 循環参照のルートとなりえるかどうか? (purple)
b. 循環参照を形作っているメンバーの可能性があるかどうか? (gray)
c. すでに回収対象としてマークされているかどうか? (white)

以上の 3 つだけと分かったので、色付けを下の表に従いフラグに分離して実装してみたのが次の Ruby コードだ。

a b c 色表現
× × × black
○ × × purple
× ○ × gray
○ ○ × gray
× × ○ white
○ × ○ white
× ○ ○ white
○ ○ ○ white 
require 'set'
require 'logger'

$log = Logger.new(STDOUT)

class InvalidState < Exception
end

class CycleGarbageCollector
    def initialize
        @roots = Set.new
    end

    def manage?(obj)
        @roots.include?(obj)
    end

    def add_to_roots(obj)
        @roots << obj
    end

    def collect
        $log.debug("Marking suspicious objects...")
        @roots.each do |obj|
            if obj.possible_root
                mark_suspicious(obj)
            else
                @roots.delete(obj)
                obj.free if not obj.in_use? and not obj.to_be_collected
            end
        end

        $log.debug("Marking cyclics...")
        @roots.each do |obj|
            scan(obj)
        end

        $log.debug("Reclaiming garbage...")
        @roots.each do |obj|
            @roots.delete(obj)
            reclaim(obj)
        end
    end

    def mark_suspicious(obj)
        if not obj.suspiciously_cyclic
            $log.debug("Object #{obj.id} is marked suspicious")
            obj.suspiciously_cyclic = true
            obj.children.each do |child|
                child.dec_ref
                mark_suspicious(child)
            end
        end
    end

    def scan(obj)
        if obj.suspiciously_cyclic and not obj.to_be_collected
            if obj.in_use?
                scan_still_in_use(obj)
            else
                obj.to_be_collected = true
                obj.children.each do |child|
                    scan(child)
                end
            end
        end
    end

    def scan_still_in_use(obj)
        if obj.suspiciously_cyclic
            $log.debug("Object #{obj.id} turned out to be in use")
            obj.suspiciously_cyclic = false
            obj.to_be_collected = false
            obj.possible_root = false
            obj.children.each do |child|
                child.inc_ref
                scan_still_in_use(child)
            end
        end
    end

    def reclaim(obj)
        if obj.to_be_collected
            obj.to_be_collected = false
            obj.children.each do |child|
                reclaim(child)
            end
            obj.free
        end
    end
end

class MyObject
    attr :id
    attr_accessor :freed
    attr_accessor :to_be_collected
    attr_accessor :possible_root
    attr_accessor :suspiciously_cyclic
    attr_accessor :children

    def initialize(id)
        @id = id
        @reference_count = 1
        @freed = false
        @to_be_collected = false
        @possible_root = false
        @suspiciously_cyclic = false
        @children = []
        $log.debug("Object #{id} created")
    end

    def add_child(obj)
        obj.add_ref
        @children << obj
        $log.debug("Object #{obj.id} added to #{id}")
    end

    def free
        raise InvalidState if @freed
        $log.warn("The reference count of object #{id} is not 0; possibly a bug") if in_use?
        $log.debug("Object #{id} freed")
        @freed = true
        $freed << self
    end

    def inc_ref
        $log.debug("Incrementing reference count of object #{id}")
        @reference_count += 1
    end

    def dec_ref
        $log.debug("Decrementing reference count of object #{id}")
        @reference_count -= 1
    end

    def in_use?
        @reference_count > 0
    end

    def add_ref
        raise InvalidState if @freed
        inc_ref
        self
    end

    def del_ref
        raise InvalidState if @freed
        dec_ref
        if not in_use?
            @children.each do |child|
                child.del_ref
            end
            if not $collector.manage?(self)
                $log.debug("Freeing object #{id} as it doesn't seem to be managed by the collector")
                free
            end
        else
            @possible_root = true
            $collector.add_to_roots(self)
        end
        self
    end

    def to_s
        "Object #{id} (refcount=#{@reference_count}, freed=#{@freed}, to_be_collected=#{@to_be_collected}, possible_root=#{@possible_root}, suspiciously_cyclic=#{@suspiciously_cyclic})"
    end
end

ここでは、2 つのクラスが登場する。

  • MyObject
  • CycleGarbageCollector

MyObject というのが GC 対象となるオブジェクトを表現したオブジェクトとなっている。MyObject に対して add_ref を呼ぶと、MyObject への参照を作成したことになり、del_ref を呼ぶと、参照を削除したことになる。2 以上の参照カウントをもつオブジェクトから参照が削除されると、possible_root というフラグが立てられ、GC の roots と呼ばれるリストに追加される。roots は、GC を行うときの起点となるオブジェクトが追加されるリストだ。

ある MyObject のインスタンスから別の MyObject インスタンスへの参照は、参照する側のインスタンスの children に参照される側のインスタンス (への参照) を追加することで表現する。もちろん、ただ追加するだけでなく、参照される側の参照カウントを増やしておく必要もある。この一連の操作を行う MyObject#add_child というメソッドが用意されている。

CycleGarbageCollector は GC 本体だ。CycleGarbageCollector#collect を呼び出すことで GC が行われる。ここでの処理は次の 3 つで

  1. 最初のループで roots を元に循環参照を作っていると疑わしきオブジェクトを洗い出し、マークする (suspiciously_cyclic)。マークすると同時に当該オブジェクトの参照しているオブジェクト (children) の参照カウントを 1 つ減らしておく。
  2. 2 番目のループで、本当に循環となっていて、かつ循環の外から参照されていないものを探し、マークする (to_be_collected)。そのような循環を構成するオブジェクトは、最後の参照カウントが 1 となったままになっているので、1. の手順の後は、これらのカウントは 0 となっているはずである。
    それと同時に、疑わしいオブジェクトでカウントが 0 に達していないものをチェックする。このオブジェクトから参照されているオブジェクトはすべて生きていることになるので、それらについては、カウントを再び 1 増やし、to_be_collected フラグを元に戻す。
  3. 3 番目のループで、2. の手順で to_be_collected とマークされたオブジェクトを解放する。

となっている。

Cycle collector の動作例

以下テストコード。

$collector = CycleGarbageCollector.new
$freed = []

o1 = MyObject.new(:A)
o2 = MyObject.new(:B)
o3 = MyObject.new(:C)
o4 = MyObject.new(:D)
o5 = MyObject.new(:E)
o1.add_child(o2)
o2.add_child(o3)
o3.add_child(o1)
o4.add_child(o3)
o4.add_child(o5)
o5.add_child(o4)

# checkpoint 1

o1.del_ref
o2.del_ref
o4.del_ref
o5.del_ref

# checkpoint 2

$collector.collect

o3.del_ref

# checkpoint 3

$collector.collect

下図は「# checkpoint 1」というコメントの時点でのオブジェクト同士の参照関係と参照カウント。オブジェクトを new した時点での参照カウントは 1 となっているので、1 回 add_child を呼んだ後の子オブジェクトの参照カウントは 2 になる。
f:id:moriyoshi:20090728190215p:image

そして、「# checkpoint 2」の時点では、その前の del_ref の呼び出しにより、A B D E が roots に追加され、参照カウントが 1 つ減る。
f:id:moriyoshi:20090728190212p:image

続いて、$collector.collect の処理の経過を表したのが以下。

f:id:moriyoshi:20090728190211p:image:w200:left
f:id:moriyoshi:20090728190206p:image:w200:left
f:id:moriyoshi:20090728190205p:image:w200


$collector.collect が終わった後、C に対して del_ref を行った時点 (「# checkpoint 3」) では次のようになり、

f:id:moriyoshi:20090728213149p:image

最終的に最後の $collector.collect で全オブジェクトが回収される、というわけだ。

回避方法について

別記事で。長くなり過ぎたので。