Lins のアルゴリズム - 参照カウントと 4 色逐次マーク&スキャンの合わせ技

メモリから動的に確保したいくつもの領域が相互に参照関係を持つ場合に、どこからも参照されていない領域を判定して空きスペースに戻すやりかたには大きくわけて、参照カウント方式とトレース方式の2種類があります。参照カウント方式は参照されている領域の個数を表しており、これがゼロになったときに空きスペースに戻します。トレース方式は、生存している領域から辿ることができる領域にマークをつけてマークがついてない領域を空きスペースに戻します。それぞれ一長一短があり、参照カウント方式は領域が不要になった瞬間に空きスペースに戻せるのに対して、循環参照になっている領域を開放することができません。トレース方式は循環参照を開放できるのに対して、マークをつけてから空き領域を順に走査するのに時間がかかります。素朴に使うと両方とも弱点が目立つため、それぞれ弱点をカバーするために、いくつものアルゴリズムが生み出されてきました。1992 年に発表された Lins のアルゴリズムもその一つです。

⇒ Rafael D. Lins, Cyclic reference counting with lazy mark-scan, Information Processing Letters 44(4) 1992

Lins のアルゴリズムは、参照カウント方式と 4 色逐次マーク&スキャン方式を組み合わせたものです。参照カウント方式で参照を手放した領域を小さなコントロール・セットに記録しておき、コントロール・セットがあふれるごとに逐次的にマーク&スイープをおこなっていきます。マークとスキャンの起点は両方共コントロール・セットに登録済みの領域だけなので、マシン・スタック等から領域へのポインタを調べる必要がありませんし、ヒープ領域を横断的にスイープすることもありません。3 色逐次マーキングに似ていますが、決定的な相違点は、コントロール・セットから領域を一つずつとりだして、一つずつそれを起点にしたマーク&スキャンをおこなっていくことです。

もちろん逐次マーキング方式の一種であるため、ライトバリアが必須です。といっても、参照カウント方式では参照付け換え時に参照カウンタ更新が必須のため、そこにライトバリアを加えれば良いだけです。コントロール・セットに登録されたときに、逐次マーキングの対象は紫色に色分けされており、ライトバリアは逐次マークの対象から外すために黒色にします。

逐次マーク&スキャンは 3 パスからなります。まずコントロール・セットから一つとりだした領域から辿れる領域を 1 パス目ですべて灰色にします。灰色にする際に参照カウンタを下げます。2 パス目で、灰色に塗った領域の中で参照カウンタがゼロでない領域から辿れる範囲を黒色に塗ります。黒色にする際に参照カウンタを上げます。そうでない領域を白色に塗ります。このとき、白色から黒色に戻るときもあります。3 パス目で、白色のままの領域をすべて黒色に塗って空きスペースへ戻します。

領域は 4 色の状態を行き来します。

  1. 黒色 - 生存が確実な領域、フリー領域、割り当て直後の領域を含みます。
  2. 紫色 - 逐次マークの対象になっている領域です。3 色逐次マーキングの灰色に相当します。
  3. 灰色 - 1 パス目で辿れる領域です。
  4. 白色 - 1 パスの後に生存している領域から辿れなかった領域です。生存領域は黒色に戻ります。

Ruby で書いた Lins アルゴリズムのおもちゃです。

class Lins
  def demo
    # allocate した領域は参照カウント 1、黒色になっている。
    r = allocate(); r.name = :R # ルート
    r.childs[0] = a = allocate(); a.name = :A
    a.childs[0] = b = allocate(); b.name = :B
    b.childs[0] = c = allocate(); c.name = :C
    r.childs[1] = d = allocate(); d.name = :D
    d.childs[0] = e = allocate(); e.name = :E
    printheap(' no cycle')
    update(c, 0, a)
    update(c, 1, d)
    printheap(' cycle A->B->C->A')
    update(r, 0, nil); r.childs.shift # ルートから A への参照を外す
    printheap(' unlink R->A')
    gc_control_set
  end

  # ヒープ中の生存領域を出力する。
  def printheap(c = '')
    puts '---' + c
    @heap.each do |cell|
      next if cell.name.nil?
      p [cell.refcnt, cell.color, cell.name, cell.childs.map{|c| c.name }]
    end
  end

  # 領域 forw はフリー・リストのリンクに使う。
  Cell = Struct.new(:forw, :refcnt, :color, :name, :childs)

  attr_reader :heap, :controlset, :free_list

  def initialize
    @heap = []
    @controlset = []
    @free_list = nil
    32.times do
      cell = Cell.new(nil, 0, :black, nil, []) # フリー領域は黒色
      cell.forw = @free_list
      @free_list = cell
      @heap.push cell
    end
  end

  # コントロール・セットが溢れているか?
  def controlset_full?
    @controlset.size > 8
  end

  # 領域を割り当てる。参照カウントは 1、黒色。
  def allocate
    if @free_list.nil?
      raise "memory full"
    end
    cell = @free_list
    @free_list = cell.forw
    cell.refcnt = 1
    cell
  end

  # 領域の i 番目の子の参照を s にする。
  def update(cell, i, s)
    return if cell.childs[i].equal?(s)
    release(cell.childs[i]);  # 元の子の参照カウントを下げる。
    cell.childs[i] = s
    cell.color = :black       # ライトバリア。領域は生存。
    return if s.nil?
    s.refcnt += 1             # 新しい子の参照カウントを上げる
    s.color = :black          # ライトバリア。新しい子は生存。
  end

  # 参照カウンタを下げる。
  def release(cell)
    return if cell.nil?
    cell.refcnt -= 1
    if cell.refcnt == 0       # ゼロになったので領域を開放する。
      cell.color = :black     # フリー領域は黒色。
      cell.childs.each {|c| release(c) }
      cell.name = nil
      cell.childs.clear
      cell.forw = @free_list
      @free_list = cell
    elsif cell.color != :purple  # 逐次マークの対象になってない領域
      if controlset_full?
        gc_control_set()      # コントロール・セットがあふれたときはゴミ集め
      end
      cell.color = :purple    # 逐次マークの対象にしてコントロール・セットに加える。
      @controlset.push cell
    end
  end

  # 逐次マーク&スキャンをおこなう。
  def gc_control_set
    while not @controlset.empty?
      s = @controlset.pop
      next if s.color != :purple
      gc_mark_gray(s)
      printheap(' mark_gray')
      gc_scan(s)
      printheap(' scan_gray')
      gc_collect_white(s)
      printheap(' collect_white')
    end
  end

  # 1 パス目。 s を起点に辿れる領域を灰色にする。
  def gc_mark_gray(s)
    return if s.color == :gray
    s.color = :gray
    s.childs.each do |c|
      c.refcnt -= 1    # 灰色にする際に参照カウンタを下げる。
      gc_mark_gray(c)
    end
  end

  # 2 パス目。 灰色の領域中で生存中とそうでないものに色分けする。
  def gc_scan(s)
    return if s.color != :gray
    if s.refcnt > 0
      gc_scan_black(s)    # 生存領域から辿れる範囲を黒色にする。
    else
      s.color = :white    # そうでない範囲は白色にする。
      s.childs.each {|c| gc_scan(c) }
    end
  end

  # 2 パス目の黒色マーキング。
  def gc_scan_black(s)
    s.color = :black
    s.childs.each do |c|
      c.refcnt += 1       # 黒が参照している子の参照カウンタを上げる。
      if c.color != :black
        gc_scan_black(c)
      end
    end
  end

  # 3 パス目。1 パス目で灰色にした領域中で、2 パス目で白色になった領域を開放する。
  def gc_collect_white(s)
    return if s.color != :white
    s.color = :black      # フリー領域は黒色。
    s.childs.each {|c| gc_collect_white(c) }
    s.name = nil
    s.childs.clear
    s.forw = @free_list
    @free_list = s
  end
end

Lins.new.demo