gc

ガベージコレクションの役割は、使用されていないオブジェクトメモリを解放し、他のオブジェクトにスペースを空けることです。このシンプルな説明ですが、その実装は非常に複雑です。ガベージコレクションの発展の歴史は数十年あり、最も早いのは 1960 年代の Lisp 言語で初めてガベージコレクションメカニズムが採用されました。私たちが知っている Python、Objective-C の主な GC メカニズムは参照カウントで、Java、C# は世代別回収を採用しています。今日において、ガベージコレクションは回収アルゴリズムから見ると、概ね以下のいくつかのカテゴリーに分類できます。

参照カウント：各オブジェクトが自身への参照回数を記録し、カウントが 0 になったときに回収します
マーク＆スイープ：アクティブなオブジェクトにマークを付け、マークされていないオブジェクトを回収します
コピーアルゴリズム：アクティブなオブジェクトを新しいメモリにコピーし、古いメモリ内のすべてのオブジェクトを回収してゴミ回収の目的を達成します
マーク＆コンパクト：マーク＆スイープのアップグレード版で、回収時にアクティブなオブジェクトをヒープの先頭に移動して管理しやすくします

適用方法から見ると、以下のいくつかのカテゴリーに分類できます。

グローバル回収：一度にすべてのゴミを回収します
世代別回収：オブジェクトの生存時間に応じて異なる世代に分け、異なる回収アルゴリズムを採用します
増分回収：毎回局所的なガベージコレクションのみを実行します

TIP

The Journey of Go's Garbage Collector で英語の原文を読んで、Go ガベージコレクションの歴史について詳しく知ることができます。

リリース当初、Go のガベージコレクションメカニズムは非常に単純で、シンプルなマーク＆スイープアルゴリズムのみでした。ガベージコレクションによる STW（Stop The World、プログラム全体の一時停止を指す）は数秒、あるいはそれ以上にも達しました。この問題に気づいた Go チームはガベージコレクションアルゴリズムの改善に着手し、go1.0 から go1.8 バージョンまでの間に、彼らは多くの試みを行いました。

読み取りバリア並行コピー GC：読み取りバリアのオーバーヘッドには多くの不確実性があり、この方案はキャンセルされました
リクエスト指向コレクター（ROC）：常に書き込みバリアを有効にする必要があり、実行速度を低下させ、コンパイル時間を引き下げました
世代別回収：Go における世代別回収の効率は高くありませんでした。Go のコンパイラは新しいオブジェクトをスタックに割り当て、長期間存在するオブジェクトをヒープに割り当てる傾向があるため、新生代オブジェクトのほとんどはスタックによって直接回収されました。
書き込みバリアなしのカードマーク：ハッシュ散列コストを使用して書き込みバリアのコストを代替し、ハードウェアのサポートが必要

最終的に Go チームは 3 色並行マーク + 書き込みバリアの組み合わせを選択し、後続のバージョンで継続的に改善と最適化を行いました。このアプローチは現在まで継続して使用されています。以下の図のグループは go1.4 から go1.9 までの GC 遅延の変化を示しています。

本記事作成時点で、Go の最新バージョンは go1.23 に近づいています。現在の Go にとって、GC パフォーマンスはもはや問題ではなく、現在の GC 遅延はほとんどの場合 100 マイクロ秒未満で、ほとんどのビジネスシーンのニーズを満たしています。

総じて、Go におけるガベージコレクションは以下のいくつかの段階に分けることができます。

スキャン段階：スタックとグローバル変数からルートオブジェクトを収集します
マーク段階：オブジェクトに色を付けます
マーク終了段階：後処理を処理し、バリアを閉じます
回収段階：ゴミオブジェクトのメモリを解放して回収します

概念

公式ドキュメントや記事で以下のいくつかの概念が表示される可能性があります。以下で簡単に説明します。

ミューテーター（mutator）：用語的な表現で、ユーザープログラムを指し、Go ではユーザーコードを指します
コレクター（collector）：ガベージコレクションを担当するプログラムを指し、Go ではランタイムがガベージコレクションを担当します
ファイナライザー（finalizer）：マーク＆スキャン作業完了後、オブジェクトメモリの回収・解放・クリーンアップを担当するコードを指します
コントローラー：runtime.gcController グローバル変数を指し、その型は gcControllerState で、後者がペースメーカーアルゴリズムを実装し、ガベージコレクションのタイミングと作業量の確認を担当します。
リミッター：runtime.gcCPULimiter を指し、ガベージコレクション時に CPU 使用率が高くなりすぎてユーザープログラムに影響を与えるのを防ぐ役割を果たします。

トリガー

func gcStart(trigger gcTrigger)

ガベージコレクションは runtime.gcStart 関数によって開始され、パラメータ runtime.gcTrigger 構造体を受け取ります。これには GC トリガーの理由、現在の時間、およびこれが何回目の GC かが含まれます。

type gcTrigger struct {
    kind gcTriggerKind
    now  int64  // gcTriggerTime: current time
    n    uint32 // gcTriggerCycle: cycle number to start
}

gcTriggerKind には以下のオプション値があります。

const (
  // gcTriggerHeap indicates that a cycle should be started when
  // the heap size reaches the trigger heap size computed by the
  // controller.
  gcTriggerHeap gcTriggerKind = iota

  // gcTriggerTime indicates that a cycle should be started when
  // it's been more than forcegcperiod nanoseconds since the
  // previous GC cycle.
  gcTriggerTime

  // gcTriggerCycle indicates that a cycle should be started if
  // we have not yet started cycle number gcTrigger.n (relative
  // to work.cycles).
  gcTriggerCycle
)

総じて、ガベージコレクションのトリガータイミングには 3 つあります。

新しいオブジェクト作成時：runtime.mallocgc を呼び出してメモリを割り当てる際、ヒープメモリが閾値（一般的には前回の GC 時の 2 倍、この値はペースメーカーアルゴリズムによって調整されます）に達したことが検出されると、ガベージコレクションが開始されます。
go
```
func mallocgc(size uintptr, typ *_type, needzero bool) unsafe.Pointer {
    ...
  if shouldhelpgc {
    if t := (gcTrigger{kind: gcTriggerHeap}); t.test() {
      gcStart(t)
    }
  }
    ...
}
```

定期的強制トリガー：Go は実行時に別のゴルーチンを起動して runtime.forcegchelper 関数を実行します。長時間ガベージコレクションが実行されていない場合、強制的に GC を開始します。この時間は runtime.forcegcperiod 定数によって決定され、その値は 2 分です。同時に、システム監視ゴルーチンでも定期的に強制 GC が必要かどうかをチェックします。

func forcegchelper() {
  for {
        ...
    gcStart(gcTrigger{kind: gcTriggerTime, now: nanotime()})
        ...
  }
}

func sysmon() {
    ...
  for {
        ...
    // check if we need to force a GC
    if t := (gcTrigger{kind: gcTriggerTime, now: now}); t.test() && forcegc.idle.Load() {
      lock(&forcegc.lock)
      forcegc.idle.Store(false)
      var list gList
      list.push(forcegc.g)
      injectglist(&list)
      unlock(&forcegc.lock)
    }
  }
}

手動トリガー：runtime.GC 関数を通じて、ユーザーは手動でガベージコレクションをトリガーできます。
go
```
func GC() {
    ...
  n := work.cycles.Load()
  gcStart(gcTrigger{kind: gcTriggerCycle, n: n + 1})
    ...
}
```

TIP

興味のある方は Go Gc Pacer Re-Design で英語の原文を読んで、GC トリガーのペースメーカーアルゴリズム（pacing algorithm）の設計理念と改善について詳しく知ることができます。内容が非常に複雑で多くの数式が含まれているため、本文では詳しく説明しません。

マーク

現在の Go の GC アルゴリズムは依然としてマーク後にクリアするというステップですが、その実装は以前ほどシンプルではありません。

マーク＆スイープ

まず最もシンプルなマーク＆スイープアルゴリズムから始めましょう。メモリ内では、オブジェクト間の参照関係がグラフを構成し、ガベージコレクションの作業はこのグラフ上で実行され、作業は 2 つの段階に分かれます。

マーク段階：ルートノード（ルートノードは通常、スタック上の変数、グローバル変数などのアクティブなオブジェクト）から開始し、到達可能なすべてのノードを順次走査し、アクティブなオブジェクトとしてマークします。到達可能なすべてのノードの走査が完了するまで続けます。
クリア段階：ヒープ内のすべてのオブジェクトを走査し、マークされていないオブジェクトを回収し、そのメモリスペースを解放または再利用します。

回収プロセス中、オブジェクトグラフの構造は変更できません。そのため、プログラム全体を停止する必要があります。つまり STW です。回収完了後にのみ実行を再開できます。このアルゴリズムの欠点は時間がかかることで、プログラムの実行効率に较大的影響を与えます。これは初期バージョンの Go で使用されたマークアルゴリズムで、その欠点は比較的明確です。

メモリフラグメントが発生します（Go の TCMalloc 式のメモリ管理方式のため、フラグメント問題の影響は大きくありません）
マーク段階でヒープのすべてのオブジェクトをスキャンします
STW を引き起こし、プログラム全体を一時停止し、時間も短くありません

3 色マーク

効率を改善するために、Go は古典的な 3 色マークアルゴリズムを採用しました。いわゆる 3 色とは、黒・灰・白の 3 色を指します。

黒：マークプロセス中にオブジェクトがアクセス済みで、直接参照するオブジェクトもすべてアクセス済みであることを示し、アクティブなオブジェクトを表します
灰：マークプロセス中にオブジェクトがアクセス済みですが、直接参照するオブジェクトがすべてアクセスされたわけではありません。すべてアクセスされると黒に変わります。アクティブなオブジェクトを表します
白：マークプロセス中に一度もアクセスされておらず、アクセス後に灰色になります。ゴミオブジェクトである可能性があります。

3 色マーク作業開始時、フィールドには灰色と白色のオブジェクトのみが存在し、すべてのルートオブジェクトは灰色で、他のオブジェクトは白色です。

各マークラウンド開始時、まず灰色オブジェクトから開始し、灰色オブジェクトを黒色にマークしてアクティブなオブジェクトであることを示し、次に黒色オブジェクトが直接参照するすべてのオブジェクトを灰色にマークします。残りは白色で、此时フィールドには黒・白・灰の 3 色が存在します。

上記のステップを繰り返し、フィールドに黒色と白色オブジェクトのみになるまで続けます。灰色オブジェクトの集合が空になると、マーク終了を表します。

マーク終了後、クリア段階では白色集合内のオブジェクトのメモリを解放するだけです。

不変性

3 色マーク法自体は並行マーク（プログラムが実行しながらマークする）を行えません。マーク時にオブジェクトグラフの構造が変更されると、2 つの状況が発生する可能性があります。

過剰マーク：オブジェクトが黒色にマークされた後、ユーザープログラムがそのオブジェクトへのすべての参照を削除した場合、それは白色オブジェクトとしてクリアされるべきです
見逃し：オブジェクトが白色にマークされた後、ユーザープログラム内の他のオブジェクトがそのオブジェクトを参照した場合、それは黒色オブジェクトとしてクリアされるべきではありません

最初の状況は許容できます。クリアされていないオブジェクトは次のラウンドの回収で処理できるためです。しかし 2 番目の状況は許容できません。使用中のオブジェクトメモリが誤って解放されると、深刻なプログラムエラーが発生するため、これは必ず回避すべき問題です。

3 色不変性という概念は、Pekka P. Pirinen が 1998 年に発表した論文《Barrier techniques for incremental tracing》から来ており、並行マーク時のオブジェクト色の 2 つの不変性を指します。

強 3 色不変性：黒色オブジェクトは白色オブジェクトを直接参照できません
弱 3 色不変性：黒色オブジェクトが白色オブジェクトを直接参照する場合、別の灰色オブジェクトがその白色オブジェクトを直接または間接的にアクセスできる必要があります。これを灰色オブジェクトによる保護と呼びます

強 3 色不変性而言、黒色オブジェクト 3 が既にアクセス済みのオブジェクトであり、その子オブジェクトもすべてアクセスされて灰色オブジェクトにマークされていることがわかっています。此时ユーザープログラムが並行的に黒色オブジェクト 3 に白色オブジェクト 7 への新しい参照を追加した場合、通常は白色オブジェクト 7 が灰色にマークされるべきですが、黒色オブジェクト 3 が既にアクセス済みのため、オブジェクト 7 はアクセスされず、常に白色オブジェクトのままとなり、最終的に誤ってクリアされてしまいます。

弱 3 色不変性而言、実際には強 3 色不変性と同様です。灰色オブジェクトが直接または間接的にその白色オブジェクトにアクセスできるため、後続のマークプロセスで最終的に灰色オブジェクトにマークされ、誤ったクリアを回避できます。

不変性を通じて、マークプロセス中にオブジェクトが誤ってクリアされないことを保証でき、並行条件でのマーク作業の正確性を保証できます。これにより、3 色マークの並行作業が可能になり、マーク効率はマーク＆スイープアルゴリズムと比較して大幅に向上します。並行状況で 3 色不変性を保証するための鍵はバリア技術にあります。

マーク作業

GC スキャン段階では、runtime.gcphase というグローバル変数があり、GC の状態を表すために使用され、以下のオプション値があります。

_GCoff：マーク作業が未開始
_GCmark：マーク作業が開始済み
_GCmarktermination：マーク作業が終了しようとしている

マーク作業開始時、runtime.gcphase の状態は _GCmark で、マーク作業を実行するのは runtime.gcDrain 関数です。runtime.gcWork パラメータはバッファプールで、追跡するオブジェクトポインタを格納します。

func gcDrain(gcw *gcWork, flags gcDrainFlags)

作業時、バッファプールから追跡可能なポインタを取得しようとします。ある場合、runtime.scanobject 関数を呼び出してスキャン作業を継続して実行します。その役割はバッファ内のオブジェクトを継続的にスキャンし、それらを黒く染めることです。

if work.full == 0 {
    gcw.balance()
}

b := gcw.tryGetFast()
if b == 0 {
    b = gcw.tryGet()
    if b == 0 {
        // Flush the write barrier
        // buffer; this may create
        // more work.
        wbBufFlush()
        b = gcw.tryGet()
    }
}
if b == 0 {
    // Unable to get work.
    break
}
scanobject(b, gcw)

P がプリエンプトされるか STW が発生しようとする場合のみ、スキャン作業が停止します。

for !(gp.preempt && (preemptible || sched.gcwaiting.Load() || pp.runSafePointFn != 0)) {
  ...
  scanobject(b, gcw)
  ...
}

runtime.gcwork は生産者/消費者モデルを採用したキューで、このキューはスキャン待ちの灰色オブジェクトを格納する責任を負います。各プロセッサ P ローカルにもこのようなキューがあり、runtime.p.gcw フィールドに対応します。

func scanobject(b uintptr, gcw *gcWork) {
  ...
  for {
    var addr uintptr
    if hbits, addr = hbits.nextFast(); addr == 0 {
            if hbits, addr = hbits.next(); addr == 0 {
                break
            }
        }
    scanSize = addr - b + goarch.PtrSize
    obj := *(*uintptr)(unsafe.Pointer(addr))
    if obj != 0 && obj-b >= n {
      if obj, span, objIndex := findObject(obj, b, addr-b); obj != 0 {
        greyobject(obj, b, addr-b, span, gcw, objIndex)
      }
    }
  }
  gcw.bytesMarked += uint64(n)
  gcw.heapScanWork += int64(scanSize)
}

runtime.scanobject 関数はスキャン時に到達可能な白色オブジェクトを継続的に灰色にマークし、gcw.put を呼び出してローカルキューに格納します。同時に gcDrain 関数も gcw.tryget を通じて灰色オブジェクトを取得してスキャンを継続します。マークスキャンプロセスは増分的で、一度にすべてのマーク作業を完了する必要はありません。マークタスクが何らかの理由でプリエンプトされた場合、中断され、回復後にキューに残っている灰色オブジェクトに基づいてマーク作業を継続できます。

バックグラウンドマーク

マーク作業は GC 開始時に直ちに実行されるわけではありません。GC トリガー直後、Go は現在のプロセッサ P の総数と同じ数のマークタスクを作成し、それらはグローバルタスクキューに追加され、マーク段階でウェイクアップされるまでスリープします。ランタイムでは、runtime.gcBgMarkStartWorkers によってタスクが割り当てられます。マークタスクは実際には runtime.gcBgMarkWorker 関数を指し、gcBgMarkWorkerCount と gomaxprocs の 2 つのランタイムグローバル変数はそれぞれ現在のワーカー数とプロセッサ P の数を表します。

func gcBgMarkStartWorkers() {
  // Background marking is performed by per-P G's. Ensure that each P has
  // a background GC G.
  //
  // Worker Gs don't exit if gomaxprocs is reduced. If it is raised
  // again, we can reuse the old workers; no need to create new workers.
  for gcBgMarkWorkerCount < gomaxprocs {
    go gcBgMarkWorker()

    notetsleepg(&work.bgMarkReady, -1)
    noteclear(&work.bgMarkReady)
    // The worker is now guaranteed to be added to the pool before
    // its P's next findRunnableGCWorker.

    gcBgMarkWorkerCount++
  }
}

ワーカー起動後、runtime.gcBgMarkWorkerNode 構造体を作成し、それをグローバルワーカープール runtime.gcBgMarkWorkerPool に追加し、runtime.gopark 関数を呼び出してゴルーチンをスリープさせます。

func gcBgMarkWorker() {
    ...
  node := new(gcBgMarkWorkerNode)
  node.gp.set(gp)
  notewakeup(&work.bgMarkReady)

  for {
    // Go to sleep until woken by
    // gcController.findRunnableGCWorker.
    gopark(func(g *g, nodep unsafe.Pointer) bool {
      node := (*gcBgMarkWorkerNode)(nodep)
      // Release this G to the pool.
      gcBgMarkWorkerPool.push(&node.node)
      // Note that at this point, the G may immediately be
      // rescheduled and may be running.
      return true
    }, unsafe.Pointer(node), waitReasonGCWorkerIdle, traceBlockSystemGoroutine, 0)
    }
    ...
}

ワーカーをウェイクアップできる状況は 2 つあります。

マーク段階にある場合、スケジューリングループは runtime.runtime.gcController.findRunnableGCWorker 関数を通じてスリープ中のワーカーをウェイクアップします
マーク段階にある場合、プロセッサ P が現在アイドル状態の場合、スケジューリングループはグローバルワーカープール gcBgMarkWorkerPool から直接使用可能なワーカーを取得しようとします

func findRunnable() (gp *g, inheritTime, tryWakeP bool) {
top:
    // Try to schedule a GC worker.
  if gcBlackenEnabled != 0 {
    gp, tnow := gcController.findRunnableGCWorker(pp, now)
    if gp != nil {
      return gp, false, true
    }
    now = tnow
  }
    ...
    // We have nothing to do.
  //
  // If we're in the GC mark phase, can safely scan and blacken objects,
  // and have work to do, run idle-time marking rather than give up the P.
  if gcBlackenEnabled != 0 && gcMarkWorkAvailable(pp) && gcController.addIdleMarkWorker() {
    node := (*gcBgMarkWorkerNode)(gcBgMarkWorkerPool.pop())
    if node != nil {
      pp.gcMarkWorkerMode = gcMarkWorkerIdleMode
      gp := node.gp.ptr()

      trace := traceAcquire()
      casgstatus(gp, _Gwaiting, _Grunnable)
      if trace.ok() {
        trace.GoUnpark(gp, 0)
        traceRelease(trace)
      }
      return gp, false, false
    }
    gcController.removeIdleMarkWorker()
  }
    ...
}

プロセッサ P には構造体中に gcMarkWorkerMode というフィールドがあり、マークタスクの実行モードを表します。以下のオプション値があります。

gcMarkWorkerNotWorker：現在のプロセッサ P がマークタスクを実行していないことを表します
gcMarkWorkerDedicatedMode：現在のプロセッサ P が専らマークタスクの実行に使用され、その間プリエンプトされないことを表します。

gcMarkWorkerFractionalMode：現在のプロセッサが GC 使用率が基準に達していない（25% が基準）ためにマークタスクを実行していることを表し、実行中はプリエンプト可能です。現在のプロセッサ P 数が 5 の場合、計算式に基づいて専用マークタスクプロセッサ P が 1 つ必要で、使用率は 20% のみで、残りの 5% の使用率を補うために FractionalMode のプロセッサ P を開始する必要があります。具体的な計算コードは以下の通りです。

func (c *gcControllerState) startCycle(markStartTime int64, procs int, trigger gcTrigger) {
  ...
  totalUtilizationGoal := float64(procs) * gcBackgroundUtilization
  dedicatedMarkWorkersNeeded := int64(totalUtilizationGoal + 0.5)
    if float64(dedicatedMarkWorkersNeeded) > totalUtilizationGoal {
        // Too many dedicated workers.
        dedicatedMarkWorkersNeeded--
    }
    c.fractionalUtilizationGoal = (totalUtilizationGoal - float64(dedicatedMarkWorkersNeeded)) / float64(procs)
    ...
}

gcMarkWorkerIdleMode：現在のプロセッサがアイドルのためにマークタスクを実行していることを表し、実行中はプリエンプト可能です。

Go チームは GC がユーザープログラムの正常な実行に影響を与えるほど多くのパフォーマンスを占有することを望んでいません。これらの異なるモードに基づいてマーク作業を行うことで、パフォーマンスを浪費せず、ユーザープログラムに影響を与えない状況で GC を完了できます。マークタスクの基本的な割り当て単位はプロセッサ P であるため、マーク作業は並行で行われ、複数のマークタスクとユーザープログラムが並行的に実行され、互いに影響を与えません。

マークアシスト

ゴルーチン G には実行時に gcAssistBytes というフィールドがあり、これを GC アシストポイントと呼びます。GC マーク状態にある場合、ゴルーチンが若干サイズのメモリを申請しようとすると、申請メモリサイズと同じポイントが差し引かれます。此时ポイントが負の場合、そのゴルーチンは定額の GC スキャンタスクをアシストしてポイントを返済する必要があります。ポイントが正の場合、ゴルーチンはアシストマークタスクを完了する必要がなくなります。

ポイントを差し引く関数は runtime.deductAssistCredit で、runtime.mallocgc 関数がメモリを割り当てる前に呼び出されます。

func deductAssistCredit(size uintptr) *g {
    var assistG *g
    if gcBlackenEnabled != 0 {
       // Charge the current user G for this allocation.
       assistG = getg()
       if assistG.m.curg != nil {
          assistG = assistG.m.curg
       }
       // Charge the allocation against the G. We'll account
       // for internal fragmentation at the end of mallocgc.
       assistG.gcAssistBytes -= int64(size)

       if assistG.gcAssistBytes < 0 {
          // This G is in debt. Assist the GC to correct
          // this before allocating. This must happen
          // before disabling preemption.
          gcAssistAlloc(assistG)
       }
    }
    return assistG
}

しかしゴルーチンが定額のアシストスキャン作業を完了した後、定額のポイントを現在のゴルーチンに返済します。実際のアシストマークを担当する関数は runtime.gcDrainN です。

func gcAssistAlloc1(gp *g, scanWork int64) {
    ...
  gcw := &getg().m.p.ptr().gcw
    // 完了
  workDone := gcDrainN(gcw, scanWork)
  ...
  assistBytesPerWork := gcController.assistBytesPerWork.Load()
  gp.gcAssistBytes += 1 + int64(assistBytesPerWork*float64(workDone))
    ...
}

スキャンは並行的であるため、記録された作業量のうち一部のみが現在のゴルーチンのもので、残りの作業量はアシストキューの順序に基づいて他のゴルーチンに逐一支払われます。剩余がある場合、グローバルポイント gcController.assistBytesPerWork に追加されます。

func gcFlushBgCredit(scanWork int64) {
    // キューが空の場合、直接グローバルポイントに追加
  if work.assistQueue.q.empty() {
    gcController.bgScanCredit.Add(scanWork)
    return
  }

  assistBytesPerWork := gcController.assistBytesPerWork.Load()
  scanBytes := int64(float64(scanWork) * assistBytesPerWork)

  lock(&work.assistQueue.lock)
  for !work.assistQueue.q.empty() && scanBytes > 0 {
    gp := work.assistQueue.q.pop()
    if scanBytes+gp.gcAssistBytes >= 0 {
      scanBytes += gp.gcAssistBytes
      gp.gcAssistBytes = 0
      ready(gp, 0, false)
    } else {
      gp.gcAssistBytes += scanBytes
      scanBytes = 0
      work.assistQueue.q.pushBack(gp)
      break
    }
  }

    // 剩余
  if scanBytes > 0 {
    assistWorkPerByte := gcController.assistWorkPerByte.Load()
    scanWork = int64(float64(scanBytes) * assistWorkPerByte)
    gcController.bgScanCredit.Add(scanWork)
  }
  unlock(&work.assistQueue.lock)
}

対応して、返済すべきポイントが多すぎる場合（申請メモリが大きすぎる）、グローバルポイントを使用して自分の借金の一部を相殺することもできます。

func gcAssistAlloc(gp *g) {
  ...
  assistWorkPerByte := gcController.assistWorkPerByte.Load()
  assistBytesPerWork := gcController.assistBytesPerWork.Load()
  debtBytes := -gp.gcAssistBytes
  scanWork := int64(assistWorkPerByte * float64(debtBytes))
  if scanWork < gcOverAssistWork {
    scanWork = gcOverAssistWork
    debtBytes = int64(assistBytesPerWork * float64(scanWork))
  }

    // グローバルポイントで担保
  bgScanCredit := gcController.bgScanCredit.Load()
  stolen := int64(0)
  if bgScanCredit > 0 {
    if bgScanCredit < scanWork {
      stolen = bgScanCredit
      gp.gcAssistBytes += 1 + int64(assistBytesPerWork*float64(stolen))
    } else {
      stolen = scanWork
      gp.gcAssistBytes += debtBytes
    }
    gcController.bgScanCredit.Add(-stolen)

    scanWork -= stolen

    if scanWork == 0 {
      return
    }
  }
    ...
}

マークアシストは高負荷状況でのバランス手段で、ユーザープログラムがメモリを割り当てる速度がマーク速度を大幅に上回り、メモリをどれだけ割り当てても同量のマーク作業が行われます。

マーク終了

すべての到達可能な灰色オブジェクトが黒く染められた後、_GCmark 状態から _GCmarktermination 状態に遷移します。このプロセスは runtime.gcMarkDone 関数によって完了されます。開始時、実行すべきタスクが残っているかどうかをチェックします。

top:

  if !(gcphase == _GCmark && work.nwait == work.nproc && !gcMarkWorkAvailable(nil)) {
    return
  }

  gcMarkDoneFlushed = 0
  // 書き込みバリアによってインターセプトされたすべてのマーク操作を一括実行
  forEachP(waitReasonGCMarkTermination, func(pp *p) {
    wbBufFlush1(pp)
    pp.gcw.dispose()
    if pp.gcw.flushedWork {
      atomic.Xadd(&gcMarkDoneFlushed, 1)
      pp.gcw.flushedWork = false
    }
  })

  if gcMarkDoneFlushed != 0 {
    goto top
  }

グローバルタスクもローカルタスクも実行する必要がなくなった後、runtime.stopTheWorldWithSema を呼び出して STW を実行し、その後いくつかの後処理を行います。

// Disable assists and background workers. We must do
// this before waking blocked assists.
atomic.Store(&gcBlackenEnabled, 0)

// Notify the CPU limiter that GC assists will now cease.
gcCPULimiter.startGCTransition(false, now)

// Wake all blocked assists. These will run when we
// start the world again.
gcWakeAllAssists()

// In STW mode, re-enable user goroutines. These will be
// queued to run after we start the world.
schedEnableUser(true)

// endCycle depends on all gcWork cache stats being flushed.
// The termination algorithm above ensured that up to
// allocations since the ragged barrier.
gcController.endCycle(now, int(gomaxprocs), work.userForced)

// Perform mark termination. This will restart the world.
gcMarkTermination(stw)

まず runtime.BlackenEnabled を 0 に設定し、マーク作業が終了したことを示し、リミッターにマークアシストが終了したことを通知し、メモリバリアを閉じ、アシストマークのためにスリープしたすべてのゴルーチンをウェイクアップし、その後すべてのユーザーゴルーチンを再ウェイクアップし、次のラウンドのスキャンのためにペースメーカーアルゴリズムを調整するために今回のスキャン作業のさまざまなデータを収集します。後処理完了後、runtime.gcSweep 関数を呼び出してゴミオブジェクトをクリーンアップし、最後に runtime.startTheWorldWithSema を呼び出してプログラムを実行再開します。

バリア

メモリバリアの役割は、オブジェクトの代入行動をフックし、代入前に指定された操作を行うことと理解できます。このフックコードは通常、コンパイル期間中にコンパイラによってコード内に挿入されます。前述の通り、3 色マークは並行状況でオブジェクト参照の追加と削除が問題を引き起こします。これらはどちらも書き込み操作（削除は空値代入）であるため、それらをインターセプトするバリアは総称して書き込みバリアと呼ばれます。しかしバリアメカニズムはコストゼロではなく、メモリ書き込み操作をインターセプトすると追加のオーバーヘッドが発生します。そのため、バリアメカニズムはヒープ上でのみ有効です。実装の複雑さとパフォーマンスの損失を考慮して、スタックとレジスタには適用されません。

TIP

Go のバリア技術の適用詳細について詳しく知りたい方は、Eliminate STW stack rescan で英語の原文を読んでください。本文は多くの内容を参考にしています。

挿入書き込みバリア

挿入書き込みバリアは Dijkstra によって提案され、強 3 色不変式を満たします。黒色オブジェクトに新しい白色オブジェクト参照が追加された場合、挿入書き込みバリアはこの操作をインターセプトし、その白色オブジェクトを灰色にマークします。これにより、黒色オブジェクトが白色オブジェクトを直接参照することを回避でき、強 3 色不変性が保証されます。これは非常に理解しやすいです。

前述の通り、書き込みバリアはスタック上では適用されません。並行マークプロセス中にスタックオブジェクトの参照関係が変化した場合、例えばスタック内の黒色オブジェクトがヒープ内の白色オブジェクトを参照した場合、スタックオブジェクトの正確性を保証するために、マーク終了後にスタック内のすべてのオブジェクトを再度灰色オブジェクトにマークし、再度スキャンする必要があります。つまり、1 ラウンドのマークでスタックスペースを 2 回スキャンする必要があり、2 回目のスキャン時には STW が必要です。プログラム中に同時に数百上千のゴルーチンスタックが存在する場合、このスキャンプロセスの時間は無視できません。公式統計データによると、再スキャンの時間は約 10-100 ミリ秒です。

利点：スキャン時に STW は不要

欠点：正確性を保証するためにスタックスペースを 2 回スキャンする必要があり、STW が必要です

削除書き込みバリア

削除書き込みバリアは Yuasa によって提案され、開始時スナップショットバリアとも呼ばれます。この方式は開始時に STW を実行してルートオブジェクトのスナップショットを記録し、すべてのルートオブジェクトを黒く、すべての一次子オブジェクトを灰色にマークします。これにより、他の白色子オブジェクトはすべて灰色オブジェクトの保護下に置かれます。Go チームは削除書き込みバリアを直接適用せず、挿入書き込みバリアと混合して使用することを選択しました。後続の理解を容易にするために、ここで説明します。削除書き込みバリアは並行条件で正確性を保証するルールは：灰色または白色オブジェクトから白色オブジェクトへの参照を削除する場合、白色オブジェクトを直接灰色にマークします。

2 つの状況に分けて解釈します。

灰色オブジェクトから白色オブジェクトへの参照を削除：白色オブジェクトの下流が黒色オブジェクトによって参照されているかどうかがわからないため、この行動は灰色オブジェクトによる白色オブジェクトの保護を切断する可能性があります
白色オブジェクトから白色オブジェクトへの参照を削除：白色オブジェクトの上流が灰色によって保護されているか、下流が黒色オブジェクトによって参照されているかどうかがわからないため、この行動も灰色による白色オブジェクトの保護を切断する可能性があります

どちらの状況でも、削除書き込みバリアは参照されている白色オブジェクトを灰色にマークします。これにより弱 3 色不変式を満たせます。これは保守的な做法で、上流と下流の状況が不明なため、灰色にマークすることはゴミオブジェクトと見なさなくなることを意味します。参照削除後にそのオブジェクトが到達不能になる、つまりゴミオブジェクトになる場合でも、依然として灰色にマークされます。それは次回のスキャンで解放されます。これはオブジェクトが誤ってクリアされてメモリエラーを引き起こすよりもマシです。

利点：スタックオブジェクトはすべて黒いため、スタックスペースを 2 回スキャンする必要はありません

欠点：スキャン開始時にスタックスペースのルートオブジェクトのスナップショットを記録するために STW が必要です

混合書き込みバリア

go1.8 バージョンは新しいバリアメカニズムを導入しました：混合書き込みバリア、つまり挿入書き込みバリアと削除書き込みバリアの混合で、両者の利点を組み合わせています。

挿入書き込みバリアは開始時にスナップショットを記録するために STW は不要
削除書き込みバリアはスタックスペースを 2 回スキャンするために STW は不要

以下は公式が提供する擬似コードです。

writePointer(slot, ptr):
    shade(*slot)
    if current stack is grey:
        shade(ptr)
    *slot = ptr

ここでいくつかの概念を簡単に説明します。slot はポインタで、他のオブジェクトへの参照を表し、*slot は元オブジェクト、ptr は新しいオブジェクト、*slot=ptr は代入操作で、オブジェクトの参照を変更することを意味し、空値代入は参照を削除することを意味します。shade() はオブジェクトを灰色にマークすることを表し、shade(*slot) は元オブジェクトを灰色にマークし、shade(ptr) は新しいオブジェクトを灰色にマークします。以下は例の図で、オブジェクト 1 が元々オブジェクト 2 を参照していて、ユーザープログラムが参照を変更してオブジェクト 1 がオブジェクト 3 を参照するようにした場合、混合書き込みバリアがこの行動をキャッチし、*slot はオブジェクト 2 を表し、ptr はオブジェクト 1 を表します。

公式は上記の擬似コードの役割を 1 文で要約しています。

the write barrier shades the object whose reference is being overwritten, and, if the current goroutine's stack has not yet been scanned, also shades the reference being installed.

翻訳すると、混合書き込みバリアが書き込み操作をインターセプトした場合、元オブジェクトを灰色にマークし、現在のゴルーチンスタックがまだスキャンされていない場合、新しいオブジェクトも灰色にマークします。

マーク作業開始時、ルートオブジェクトを収集するためにスタックスペースをスキャンする必要があります。此时直接すべてを黒色にマークし、この期間中に新しく作成されたオブジェクトも黒色にマークされ、スタック内のすべてが黒色オブジェクトであることが保証されます。したがって擬似コード中の current stack is grey は現在のゴルーチンスタックがまだスキャンされていないことを表します。したがってゴルーチンスタックには 2 つの状態のみ存在し、すべて黒またはすべて灰です。すべて灰からすべて黒に遷移するプロセス中は現在のゴルーチンを一時停止する必要があるため、混合書き込みバリア下でも局所的な STW が発生します。ゴルーチンスタックがすべて黒の場合、強 3 色不変式が必ず満たされます。スキャン後のスタック内の黒色オブジェクトは灰色オブジェクトのみを参照し、黒色オブジェクトが白色オブジェクトを直接参照する状況は存在しないため、此时挿入書き込みバリアは不要です。擬似コードに対応します。

if current stack is grey:
        shade(ptr)

しかし弱 3 色不変式を満たすために削除書き込みバリアが必要です。

shade(*slot)

スキャン完了後、スタックスペースのオブジェクトはすでにすべて黒色であるため、スタックスペースを 2 回スキャンする必要がなくなり、STW の時間を節約できます。

至此、go1.8 バージョン以降、Go は概ねガベージコレクションの基本フレームワークを確立しました。後続のバージョンのガベージコレクションに関する最適化もすべて混合書き込みバリアの基礎の上に構築されています。すでに大部分の STW が消除されているため、此时ガベージコレクションの平均遅延はマイクロ秒レベルに低下しています。

着色キャッシュ

前述のバリアメカニズムでは、書き込み操作をインターセプトした場合、直ちにオブジェクト色をマークしていました。混合書き込みバリア採用後、元オブジェクトと新しいオブジェクトの両方をマークする必要があるため、作業量が 2 倍になり、コンパイラが挿入するコードも増加します。最適化のため、go1.10 バージョンでは、書き込みバリアは着色時に直ちにオブジェクト色をマークせず、元オブジェクトと新しいオブジェクトをキャッシュプールに格納し、一定数量に達した後に一括でマークします。これにより効率が向上します。

キャッシュを担当する構造は runtime.wbBuf で、実際には配列で、サイズは 512 です。

type wbBuf struct {
  next uintptr
  end uintptr
  buf [wbBufEntries]uintptr
}

各 P ローカルにもこのようなキャッシュがあります。

type p struct {
    ...
  wbBuf wbBuf
    ...
}

マーク作業進行中、gcw キューに使用可能な灰色オブジェクトがない場合、キャッシュ内のオブジェクトをローカルキューに格納します。

func gcDrain(gcw *gcWork, flags gcDrainFlags) {
  for !(gp.preempt && (preemptible || sched.gcwaiting.Load() || pp.runSafePointFn != 0)) {
    if work.full == 0 {
      gcw.balance()
    }
    b := gcw.tryGetFast()
    if b == 0 {
      b = gcw.tryGet()
      if b == 0 {
        // 書き込みバリアキャッシュをフラッシュ
        wbBufFlush()
        b = gcw.tryGet()
      }
    }
    if b == 0 {
      break
    }
    scanobject(b, gcw)
  }
}

別の状況は、マーク終了時に、各 P ローカルの wbBuf に残りの灰色オブジェクトがあるかどうかをチェックすることです。

func gcMarkDone() {
    ...
  forEachP(waitReasonGCMarkTermination, func(pp *p) {

    wbBufFlush1(pp)

    pp.gcw.dispose()

  })
    ...
}

回収

ガベージコレクションにおいて、最も重要な部分はゴミオブジェクトを特定する方法、つまりスキャンマーク作業です。マーク作業完了後、回収作業はそれほど複雑ではなく、マークされていないオブジェクトを回収して解放するだけです。この部分のコードは主に runtime/mgcsweep.go ファイルにあり、ファイル内のコメントによると、Go の回収アルゴリズムは 2 種類に分けられます。

オブジェクト回収

オブジェクト回収作業はマーク終了段階で、runtime.sweepone によってクリーンアップ作業が完了し、プロセスは非同期です。クリーンアップ時、メモリユニット内でマークされていないオブジェクトを検索し、回収します。メモリユニット全体がマークされていない場合、そのユニット全体が回収されます。

func sweepone() uintptr {
  sl := sweep.active.begin()
  npages := ^uintptr(0)
  var noMoreWork bool
  for {
    s := mheap_.nextSpanForSweep()
    if s == nil {
      noMoreWork = sweep.active.markDrained()
      break
    }
    if state := s.state.get(); state != mSpanInUse {
      continue
    }
        // 回収器の取得を試みる
    if s, ok := sl.tryAcquire(s); ok {
      npages = s.npages
            // クリーンアップ
      if s.sweep(false) {
        mheap_.reclaimCredit.Add(npages)
      } else {
        npages = 0
      }
      break
    }
  }
  sweep.active.end(sl)
  return npages
}

オブジェクト回収アルゴリズム而言、ユニット全体を回収することは比較的困難です。そのため、2 番目の回収アルゴリズムがあります。

ユニット回収

ユニット回収作業はメモリ割り当て前に実行され、runtime.mheap.reclaim メソッドによって完了されます。ヒープ内ですべてのオブジェクトがマークされていないメモリユニットを検索し、ユニット全体を回収します。

func (h *mheap) reclaim(npage uintptr) {
  mp := acquirem()
  trace := traceAcquire()
  if trace.ok() {
    trace.GCSweepStart()
    traceRelease(trace)
  }
  arenas := h.sweepArenas
  locked := false
  for npage > 0 {
    if credit := h.reclaimCredit.Load(); credit > 0 {
      take := credit
      if take > npage {
        take = npage
      }
      if h.reclaimCredit.CompareAndSwap(credit, credit-take) {
        npage -= take
      }
      continue
    }

    idx := uintptr(h.reclaimIndex.Add(pagesPerReclaimerChunk) - pagesPerReclaimerChunk)
    if idx/pagesPerArena >= uintptr(len(arenas)) {
      h.reclaimIndex.Store(1 << 63)
      break
    }

    nfound := h.reclaimChunk(arenas, idx, pagesPerReclaimerChunk)
    if nfound <= npage {
      npage -= nfound
    } else {
      h.reclaimCredit.Add(nfound - npage)
      npage = 0
    }
  }

  trace = traceAcquire()
  if trace.ok() {
    trace.GCSweepDone()
    traceRelease(trace)
  }
  releasem(mp)
}

メモリユニット而言、sweepgen というフィールドがあり、その回収状態を示します。

mspan.sweepgen == mheap.sweepgen - 2：そのメモリユニットは回収が必要です
mspan.sweepgen == mheap.sweepgen - 1：そのメモリユニットは回収中です
mspan.sweepgen == mheap.sweepgen：そのメモリユニットはすでに回収済みで、正常使用可能です
mspan.sweepgen == mheap.sweepgen + 1：メモリユニットはキャッシュ内にあり、回収が必要です
mspan.sweepgen == mheap.sweepgen + 3：メモリユニットはすでに回収済みですが、依然としてキャッシュ内にあります

mheap.sweepgen は GC ラウンドとともに増加し、毎回 +2 されます。

gc ​

概念 ​

トリガー ​

マーク ​

マーク＆スイープ ​

3 色マーク ​

不変性 ​

マーク作業 ​

バックグラウンドマーク ​

マークアシスト ​

マーク終了 ​

バリア ​

挿入書き込みバリア ​

削除書き込みバリア ​

混合書き込みバリア ​

着色キャッシュ ​

回収 ​

オブジェクト回収 ​

ユニット回収 ​

gc

概念