gc

Garbage collection bertugas untuk melepaskan memori objek yang tidak lagi digunakan, membebaskan ruang untuk objek lain. Meskipun terdengar sederhana, implementasinya sangat kompleks. Sejarah garbage collection sudah ada selama beberapa dekade, sejak pertama kali diadopsi oleh bahasa Lisp pada tahun 1960-an. Python dan Objective-C yang kita kenal menggunakan mekanisme GC reference counting, sedangkan Java dan C# menggunakan generational collection. Saat ini, garbage collection dapat dikategorikan menjadi beberapa jenis berdasarkan algoritma:

• Reference counting: Setiap objek menghitung berapa kali direferensikan, ketika hitungan mencapai 0, objek akan di回收
• Mark-sweep: Menandai objek aktif, kemudian回收 objek yang tidak ditandai
• Copying: Menyalin objek aktif ke memori baru,回收 semua objek di memori lama
• Mark-compact: Versi upgrade dari mark-sweep, memindahkan objek aktif ke头部 heap untuk memudahkan manajemen

Berdasarkan cara aplikasi, dapat dibagi menjadi:

• Global collection:回收 semua sampah sekaligus
• Generational collection: Membagi objek berdasarkan waktu hidup, menggunakan algoritma berbeda
• Incremental collection: Setiap kali hanya melakukan garbage collection lokal

TIP

Kunjungi The Journey of Go's Garbage Collector untuk membaca artikel asli dalam bahasa Inggris dan pelajari lebih lanjut tentang sejarah garbage collection Go

Saat pertama kali dirilis, mekanisme garbage collection Go sangat sederhana, hanya menggunakan algoritma mark-sweep, dengan STW (Stop The World, mengacu pada jeda program karena garbage collection) mencapai beberapa detik atau lebih. Menyadari masalah ini, tim Go mulai memperbaiki algoritma garbage collection. Antara versi go1.0 hingga go1.8, mereka mencoba banyak pendekatan:

1. Read barrier concurrent copying GC: Biaya read barrier memiliki banyak ketidakpastian,方案 ini dibatalkan
2. Request-Oriented Collector (ROC): Memerlukan write barrier selalu aktif, memperlambat eksekusi dan waktu kompilasi
3. Generational collection: Efisiensi generational collection di Go tidak tinggi, karena compiler Go cenderung mengalokasikan objek baru di stack, objek yang bertahan lama di heap, sehingga sebagian besar objek generasi baru di回收 langsung oleh stack.
4. Card marking tanpa write barrier: Menggantikan biaya write barrier dengan biaya hashing, memerlukan dukungan hardware

Akhirnya tim Go memilih kombinasi tri-color concurrent marking + write barrier, dan terus memperbaikinya di versi berikutnya, pendekatan ini masih digunakan hingga sekarang. Serangkaian gambar berikut menunjukkan perubahan latency GC dari go1.4 hingga go1.9.

Saat artikel ini ditulis, versi terbaru Go hampir mencapai go1.23, bagi Go saat ini performa GC bukan lagi masalah, latency GC sebagian besar di bawah 100 mikrodetik, memenuhi kebutuhan sebagian besar skenario bisnis.

Secara keseluruhan, garbage collection di Go dapat dibagi menjadi beberapa tahap:

• Scan stage: Mengumpulkan objek root dari stack dan variabel global
• Mark stage: Memberi warna pada objek
• Mark termination stage: Menyelesaikan pekerjaan akhir, menutup barrier
• Sweep stage: Melepaskan dan回收 memori objek sampah

Konsep

Dalam dokumentasi dan artikel resmi, mungkin muncul beberapa konsep berikut, berikut penjelasan singkat:

• Mutator: Istilah untuk program pengguna, di Go mengacu pada kode pengguna
• Collector: Program yang bertanggung jawab untuk garbage collection, di Go adalah runtime
• Finalizer: Kode yang bertanggung jawab untuk回收 dan membersihkan memori objek setelah marking selesai
• Controller: Mengacu pada variabel global runtime.gcController, tipenya gcControllerState, mengimplementasikan pacing algorithm, bertanggung jawab untuk menentukan kapan melakukan garbage collection dan berapa banyak pekerjaan.
• Limiter: Mengacu pada runtime.gcCPULimiter, bertanggung jawab untuk mencegah penggunaan CPU terlalu tinggi saat garbage collection yang mempengaruhi program pengguna

Trigger

func gcStart(trigger gcTrigger)

Garbage collection dimulai oleh fungsi runtime.gcStart, menerima parameter struktur runtime.gcTrigger, yang berisi alasan trigger GC, waktu saat ini, dan putaran GC ke berapa.

type gcTrigger struct {
    kind gcTriggerKind
    now  int64  // gcTriggerTime: waktu saat ini
    n    uint32 // gcTriggerCycle: nomor cycle untuk dimulai
}

gcTriggerKind memiliki beberapa nilai opsional:

const (
  // gcTriggerHeap menunjukkan cycle harus dimulai ketika
  // ukuran heap mencapai ukuran trigger yang dihitung oleh controller.
  gcTriggerHeap gcTriggerKind = iota

  // gcTriggerTime menunjukkan cycle harus dimulai ketika
  // sudah lebih dari forcegcperiod nanodetik sejak cycle GC sebelumnya.
  gcTriggerTime

  // gcTriggerCycle menunjukkan cycle harus dimulai jika
  // kita belum memulai cycle nomor gcTrigger.n (relatif
  // terhadap work.cycles).
  gcTriggerCycle
)

Secara keseluruhan, ada tiga trigger garbage collection:

• Saat membuat objek baru: Saat memanggil runtime.mallocgc untuk mengalokasikan memori, jika terdeteksi heap memory mencapai threshold (umumnya dua kali lipat dari GC sebelumnya, nilai ini juga dapat disesuaikan oleh pacing algorithm), garbage collection akan dimulai

  func mallocgc(size uintptr, typ *_type, needzero bool) unsafe.Pointer {
      ...
    if shouldhelpgc {
      if t := (gcTrigger{kind: gcTriggerHeap}); t.test() {
        gcStart(t)
      }
    }
      ...
  }

• Trigger paksa berkala: Go memulai goroutine terpisah saat runtime untuk menjalankan fungsi runtime.forcegchelper, jika tidak ada garbage collection dalam waktu lama, akan memaksa开启 GC, waktu ini ditentukan oleh konstanta runtime.forcegcperiod, nilainya 2 menit,同时 dalam sistem monitoring juga akan memeriksa secara berkala apakah perlu memaksa 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)
      }
    }
  }

• Trigger manual: Melalui fungsi runtime.GC, pengguna dapat secara manual trigger garbage collection.

  func GC() {
      ...
    n := work.cycles.Load()
    gcStart(gcTrigger{kind: gcTriggerCycle, n: n + 1})
      ...
  }

TIP

Tertarik dapat mengunjungi Go Gc Pacer Re-Design untuk membaca artikel asli dalam bahasa Inggris, yang menjelaskan desain dan perbaikan pacing algorithm untuk trigger GC, karena kontennya cukup kompleks dengan banyak formula matematika, tidak dijelaskan secara detail dalam artikel ini.

Marking

Saat ini algoritma GC Go masih menggunakan mark-then-sweep, tetapi implementasinya tidak lagi sederhana seperti sebelumnya.

Mark-Sweep

Mari mulai dari algoritma mark-sweep paling sederhana, dalam memori, referensi antar objek membentuk graph, garbage collection bekerja pada graph ini, dibagi menjadi dua tahap:

• Marking stage: Mulai dari root (root biasanya variabel di stack, variabel global, dll),遍历 setiap node yang dapat dijangkau, menandainya sebagai objek aktif, hingga遍历 semua node yang dapat dijangkau
• Sweep stage:遍历 semua objek di heap,回收 objek yang tidak ditandai, melepaskan atau menggunakan kembali ruang memorinya

Selama proses回收, struktur graph objek tidak boleh berubah, jadi program harus dihentikan, yaitu STW, baru dapat继续运行 setelah回收 selesai. Kekurangan algoritma ini adalah waktu yang lama, cukup mempengaruhi efisiensi program, ini adalah algoritma marking yang digunakan versi awal Go, kekurangannya cukup jelas:

• Menghasilkan fragmentasi memori (karena cara manajemen memori TCMalloc Go, dampak fragmentasi tidak besar)
• Selama marking stage akan scan semua objek di heap
• Menyebabkan STW, menghentikan seluruh program, dan waktunya tidak singkat

Tri-color Marking

Untuk meningkatkan efisiensi, Go mengadopsi algoritma tri-color marking klasik. Tri-color mengacu pada hitam, abu-abu, dan putih:

• Hitam: Objek sudah diakses selama marking, dan semua objek yang direferensikan langsung juga sudah diakses, menunjukkan objek aktif
• Abu-abu: Objek sudah diakses selama marking, tetapi objek yang direferensikan langsung belum semua diakses, setelah semua diakses akan berubah menjadi hitam, menunjukkan objek aktif
• Putih: Objek belum pernah diakses selama marking, setelah diakses akan berubah menjadi abu-abu, mungkin objek sampah

Saat tri-color marking dimulai, hanya ada objek abu-abu dan putih, semua root objek abu-abu, lainnya putih, seperti gambar berikut

Setiap putaran marking dimulai dari objek abu-abu, menandai objek abu-abu sebagai hitam, menunjukkan objek aktif, kemudian menandai semua objek yang direferensikan langsung oleh objek hitam sebagai abu-abu, sisanya putih, saat ini ada tiga warna hitam, abu-abu, dan putih.

Ulangi langkah di atas hingga hanya tersisa objek hitam dan putih, ketika kumpulan objek abu-abu kosong, menandakan marking selesai, seperti gambar berikut

Setelah marking selesai, di sweep stage cukup lepaskan memori objek putih.

Invarian

Tri-color marking sendiri tidak dapat melakukan concurrent marking (program berjalan sambil marking), jika struktur graph objek berubah selama marking, dapat menyebabkan dua situasi:

• Over-marking: Setelah objek ditandai sebagai hitam, program pengguna menghapus semua referensi ke objek tersebut, seharusnya objek putih perlu di回收
• Under-marking: Setelah objek ditandai sebagai putih, program pengguna memiliki objek lain yang mereferensikan objek tersebut, seharusnya objek hitam tidak boleh di回收

Untuk situasi pertama dapat diterima, karena objek yang tidak di清理 dapat ditangani di putaran回收 berikutnya. Tetapi situasi kedua tidak dapat diterima, memori objek yang sedang digunakan dilepaskan secara salah, akan menyebabkan error program yang serius, ini harus dihindari.

Konsep tri-color invarian berasal dari makalah 《Barrier techniques for incremental tracing》 yang diterbitkan oleh Pekka P. Pirinen pada tahun 1998, mengacu pada dua invarian warna objek saat concurrent marking:

• Strong tri-color invarian: Objek hitam tidak dapat langsung mereferensikan objek putih

• Weak tri-color invarian: Ketika objek hitam langsung mereferensikan objek putih, harus ada objek abu-abu lain yang dapat langsung atau tidak langsung mengakses objek abu-abu tersebut, disebut dilindungi oleh objek abu-abu

Untuk strong tri-color invarian, diketahui objek hitam 3 sudah diakses, dan objek anaknya juga sudah diakses dan ditandai sebagai abu-abu, jika saat ini program pengguna secara konkuren menambahkan referensi baru objek putih 7 ke objek hitam 3, normalnya objek putih 7 seharusnya ditandai sebagai abu-abu, tetapi karena objek hitam 3 sudah diakses, objek 7 tidak akan diakses, jadi selalu putih, dan akhirnya di清理 secara salah.

Untuk weak tri-color invarian, sama dengan strong tri-color invarian, karena objek abu-abu dapat langsung atau tidak langsung mengakses objek putih ini, selama marking berikutnya akhirnya akan ditandai sebagai abu-abu, sehingga menghindari di清理 secara salah.

Melalui invarian, dapat memastikan tidak ada objek yang di清理 secara salah selama marking, sehingga menjamin kebenaran pekerjaan marking dalam kondisi konkuren, sehingga tri-color marking dapat bekerja secara konkuren, dengan demikian efisiensi marking meningkat相当 banyak dibandingkan dengan algoritma mark-sweep. Untuk menjamin tri-color invarian dalam kondisi konkuren, kuncinya adalah barrier technology.

Pekerjaan Marking

Di GC scan stage, ada variabel global runtime.gcphase untuk表示 status GC, dengan nilai opsional berikut:

• _GCoff: Marking belum dimulai
• _GCmark: Marking sudah dimulai
• _GCmarktermination: Marking akan berakhir

Ketika marking dimulai, status runtime.gcphase adalah _GCmark, pekerjaan marking dilakukan oleh fungsi runtime.gcDrain, parameter runtime.gcWork adalah buffer pool, menyimpan pointer objek yang akan dilacak.

func gcDrain(gcw *gcWork, flags gcDrainFlags)

Selama bekerja, akan mencoba mendapatkan pointer yang dapat dilacak dari buffer pool, jika ada akan memanggil fungsi runtime.scanobject untuk继续执行 scan task, fungsinya adalah terus scan objek di buffer, menandainya hitam.

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)

Ketika P di-preempt atau akan terjadi STW, scan pekerjaan akan berhenti

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

runtime.gcwork adalah queue yang menggunakan model producer/consumer, queue bertanggung jawab menyimpan objek abu-abu yang akan di-scan, setiap processor P lokal memiliki queue seperti ini, sesuai field 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)
}

Fungsi runitme.scanobject saat scan akan terus menandai objek putih yang reachable sebagai abu-abu, kemudian melalui panggilan gcw.put memasukkan ke queue lokal,同时 fungsi gcDrain juga akan terus melalui gcw.tryget untuk mencoba mendapatkan objek abu-abu untuk继续 scan. Proses marking scan adalah incremental, tidak perlu menyelesaikan semua marking sekaligus, ketika task marking di-preempt karena beberapa alasan akan terputus, setelah pulih dapat继续 menyelesaikan marking berdasarkan objek abu-abu yang tersisa di queue.

Background Marking

Pekerjaan marking tidak langsung dieksekusi saat GC dimulai, saat trigger GC, go akan membuat task marking dengan jumlah sama dengan processor P saat ini, akan ditambahkan ke queue task global, kemudian tidur hingga dibangunkan di mark stage. Saat runtime, oleh runtime.gcBgMarkStartWorkers untuk melakukan distribusi task, task marking sebenarnya mengacu pada fungsi runtime.gcBgMarkWorker,其中 gcBgMarkWorkerCount dan gomaxprocs dua variabel global runtime masing-masing表示 jumlah worker saat ini dan jumlah processor 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++
  }
}

Setelah worker启动, akan membuat struktur runtime.gcBgMarkWorkerNode, menambahkannya ke pool worker global runitme.gcBgMarkWorkerPool, kemudian memanggil fungsi runtime.gopark untuk membuat goroutine tidur

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)
    }
    ...
}

Ada dua situasi yang dapat membangunkan worker:

• Saat mark stage, scheduling loop akan membangunkan worker yang tidur melalui fungsi runtime.runtime.gcController.findRunnableGCWorker
• Saat mark stage, jika processor P saat ini dalam status idle, scheduling loop akan mencoba langsung mendapatkan worker yang tersedia dari pool worker global 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()
  }
    ...
}

Processor P memiliki field di struktur gcMarkWorkerMode untuk表示 mode eksekusi task marking, dengan beberapa nilai opsional berikut:

• gcMarkWorkerNotWorker: Menunjukkan processor P saat ini tidak sedang menjalankan task marking

• gcMarkWorkerDedicatedMode: Menunjukkan processor P saat ini khusus untuk menjalankan task marking, dan tidak dapat di-preempt selama periode ini.

• gcMarkWorkerFractionalMode: Menunjukkan processor menjalankan task marking karena GC utilization tidak达标 (25%达标), dapat di-preempt selama eksekusi. Misalkan jumlah processor P saat ini adalah 5, menurut perhitungan rumus saat ini memerlukan satu processor P khusus untuk marking, utilization hanya mencapai 20%, sisa 5% utilization memerlukan processor P dengan FractionalMode untuk弥补. Kode perhitungan spesifik seperti berikut

  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: Menunjukkan processor menjalankan task marking karena idle, dapat di-preempt selama eksekusi.

Tim Go tidak希望 GC mengambil terlalu banyak performa sehingga mempengaruhi program pengguna, melalui mode berbeda ini untuk marking, dapat menyelesaikan GC tanpa membuang performa atau mempengaruhi program pengguna. Dapat diperhatikan bahwa unit dasar distribusi task marking adalah processor P, jadi marking dilakukan secara konkuren, beberapa task marking dan program pengguna dieksekusi secara konkuren, tidak saling mempengaruhi.

Marking Assist

Goroutine G memiliki field gcAssistBytes saat runtime, disebut GC assist credit. Saat GC marking, ketika goroutine mencoba mengalokasikan beberapa ukuran memori, akan dikurangi credit dengan ukuran memori yang dialokasikan. Jika credit negatif, goroutine harus membantu menyelesaikan sejumlah task GC scan untuk melunasi credit, ketika credit positif, goroutine tidak perlu menyelesaikan task assist marking.

Fungsi untuk mengurangi credit adalah runtime.deductAssistCredit, akan dipanggil sebelum fungsi runtime.mallocgc mengalokasikan memori.

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
}

Namun ketika goroutine menyelesaikan sejumlah assist scan work, akan melunasi credit ke goroutine saat ini, fungsi yang sebenarnya负责 assist marking adalah 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))
    ...
}

Karena scan konkuren, hanya sebagian dari work yang dicatat adalah milik goroutine saat ini, sisa work akan dilunasi ke goroutine lain berdasarkan urutan assist queue, jika masih ada sisa, akan ditambahkan ke global credit 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)
}

Sesuai, ketika credit yang harus dilunasi terlalu banyak (memori yang dialokasikan terlalu besar), juga dapat menggunakan global credit untuk mengoffset sebagian utang sendiri

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
    }
  }
    ...
}

Marking assist adalah cara balancing dalam kondisi high load, kecepatan alokasi memori program pengguna jauh lebih tinggi dari kecepatan marking, alokasi berapa banyak memori melakukan berapa banyak marking work.

Mark Termination

Ketika semua objek abu-abu yang reachable sudah dihitamkan, saat ini beralih dari status _GCmark ke _GCmarktermination, proses ini diselesaikan oleh fungsi runtime.gcMarkDone. Saat dimulai, akan memeriksa apakah masih ada task yang harus dieksekusi,

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
  }

Ketika tidak ada task global dan lokal yang harus dieksekusi, memanggil runtime.stopTheWorldWithSema untuk STW, kemudian melakukan beberapa pekerjaan akhir

// 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)

Pertama set runtime.BlackenEnabled ke 0, menunjukkan marking work sudah selesai, notify limiter marking assist sudah selesai, menutup memory barrier, membangunkan semua goroutine yang tidur karena assist marking, kemudian重新唤醒 semua goroutine pengguna,还要收集本轮扫描工作的各种数据来调整 pacing algorithm 为下一轮扫描做准备, setelah pekerjaan akhir selesai, memanggil runtime.gcSweep fungsi untuk清理 objek sampah, terakhir memanggil runtime.startTheWorldWithSema untuk memulihkan program.

Barrier

Fungsi memory barrier dapat dipahami sebagai hook perilaku assignment objek, melakukan operasi tertentu sebelum assignment, kode hook ini biasanya disisipkan oleh compiler ke kode selama kompilasi. Sebelumnya disebutkan, tri-color marking dalam kondisi konkuren menambah dan menghapus referensi objek akan menyebabkan masalah, karena keduanya adalah write operation (menghapus adalah赋空值), jadi barrier untuk拦截它们 disebut write barrier. Tetapi barrier mechanism bukan tanpa biaya,拦截 memory write operation akan menyebabkan overhead tambahan, oleh karena itu barrier mechanism hanya berlaku di heap,考虑到实现复杂度和性能损耗，对于栈和寄存器则不起作用范围内。

TIP

Ingin pelajari lebih lanjut tentang detail aplikasi barrier technology Go, kunjungi Eliminate STW stack rescan untuk membaca artikel asli dalam bahasa Inggris, artikel ini mereferensi banyak kontennya.

Insertion Write Barrier

Insertion write barrier diajukan oleh Dijkstra, memenuhi strong tri-color invarian. Ketika menambahkan referensi objek putih baru ke objek hitam, insertion write barrier akan拦截 operasi ini, menandai objek putih sebagai abu-abu,这样可以避免 objek hitam langsung mereferensikan objek putih, menjamin strong tri-color invarian, ini cukup mudah dipahami.

Sebelumnya disebutkan write barrier tidak berlaku di stack, jika selama concurrent marking referensi objek stack berubah, misalnya objek hitam di stack mereferensikan objek putih di heap, jadi untuk memastikan kebenaran objek stack, hanya dapat setelah marking selesai再次 menandai semua objek di stack sebagai objek abu-abu, kemudian重新 scan一遍, sama dengan satu putaran marking harus scan stack space dua kali, dan第二次 scan 时必须 STW, jika program secara bersamaan存在成百上千个协程栈，那么这一扫描过程的耗时将不容忽视，根据官方统计的数据，重新扫描的耗时大概在 10-100 毫秒左右。

Keuntungan: Scan tidak perlu STW

Kekurangan: Perlu二次 scan stack space untuk menjamin kebenaran, perlu STW

Deletion Write Barrier

Deletion write barrier diajukan oleh Yuasa, disebut juga snapshot-at-the-beginning barrier, cara ini perlu STW di awal untuk snapshot record root objects, dan akan menandai semua root objects hitam, semua child objects level satu abu-abu, sehingga sisa child objects putih akan berada di bawah perlindungan objek abu-abu. Tim Go tidak langsung menerapkan deletion write barrier, tetapi memilih untuk mencampurnya dengan insertion write barrier, jadi untuk memudahkan pemahaman berikutnya, di sini masih harus menjelaskannya. Deletion write barrier aturan untuk menjamin kebenaran dalam kondisi konkuren adalah: ketika menghapus referensi objek putih dari objek abu-abu atau putih, akan langsung menandai objek putih sebagai objek abu-abu.

Dibagi menjadi dua situasi untuk解读:

• Menghapus referensi objek abu-abu ke objek putih: Karena tidak tahu apakah downstream objek putih direferensikan oleh objek hitam, tindakan ini mungkin memutus perlindungan objek abu-abu ke objek putih

• Menghapus referensi objek putih ke objek putih: Karena tidak tahu apakah upstream objek putih dilindungi oleh abu-abu, apakah downstream direferensikan oleh hitam, tindakan ini juga mungkin memutus perlindungan abu-abu ke objek putih

Tidak peduli situasi mana, deletion write barrier akan menandai objek putih yang direferensikan sebagai abu-abu, dengan demikian dapat memenuhi weak tri-color invarian. Ini adalah pendekatan konservatif, karena situasi upstream dan downstream tidak diketahui, menandainya sebagai abu-abu sama dengan tidak lagi menganggapnya sebagai objek sampah, bahkan jika setelah menghapus referensi akan menyebabkan objek tidak reachable yaitu menjadi objek sampah, masih akan menandainya sebagai abu-abu, akan dilepaskan di scan putaran berikutnya, ini lebih baik daripada error memori karena objek di清理 secara salah.

Keuntungan: Karena stack objects全黑，jadi tidak perlu二次 scan stack space

Kekurangan: Di awal scan perlu STW untuk snapshot record stack space root objects

Hybrid Write Barrier

Versi go1.8 mengutip barrier mechanism baru: hybrid write barrier, yaitu campuran insertion write barrier dan deletion write barrier, menggabungkan keuntungan keduanya:

• Insertion write barrier di awal tidak perlu STW untuk snapshot
• Deletion write barrier tidak perlu STW untuk二次 scan stack space

Berikut adalah pseudocode yang diberikan resmi:

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

Penjelasan singkat tentang beberapa konsep di dalamnya,其中 slot adalah pointer,表示 referensi ke objek lain, *slot adalah objek asli, ptr adalah objek baru, *slot=ptr adalah operasi assignment, sama dengan mengubah referensi objek,赋空值 adalah menghapus referensi, shade()表示 menandai objek sebagai abu-abu, shade(*slot) adalah menandai objek asli sebagai abu-abu, shade(ptr) adalah menandai objek baru sebagai abu-abu, berikut adalah contoh gambar, anggap objek 1原来 mereferensikan objek 2, kemudian program pengguna mengubah referensi, membuat objek 1 mereferensikan objek 3, hybrid write barrier menangkap perilaku ini,其中 *slot代表的是 objek 2, ptr代表的是 objek 1.

Resmi menggunakan satu kalimat untuk概括 efek pseudocode di atas

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.

Diterjemahkan, ketika hybrid write barrier拦截 write operation, akan menandai objek asli sebagai abu-abu, jika stack goroutine saat ini belum di-scan, akan menandai objek baru juga sebagai abu-abu.

Saat marking work dimulai, perlu scan stack space untuk mengumpulkan root objects, saat ini akan langsung menandainya semua sebagai hitam, selama periode ini objek yang dibuat baru juga ditandai sebagai hitam, menjamin semua di stack adalah objek hitam, jadi current stack is grey di pseudocode表示的是 stack goroutine saat ini belum di-scan, jadi stack goroutine hanya memiliki dua status,要么全黑要么全灰，dalam proses dari全灰变为全黑时需要暂停当前协程的，所以在混合写屏障下依然会有局部的 STW。当协程栈全黑时，此时一定满足强三色不变式，因为扫描后栈中的黑色 对象只会引用灰色对象，不会存在黑色对象直接引用白色对象的情况，所以此时不需要插入写屏障，对应伪代码

if current stack is grey:
        shade(ptr)

Tetapi masih perlu deletion write barrier untuk memenuhi weak tri-color invarian, yaitu

shade(*slot)

Setelah scan selesai, karena objek stack space sudah全黑，tidak perlu lagi二次 scan stack space, dapat menghemat waktu STW.

Hingga di sini, yaitu setelah versi go1.8, Go secara umum确立了框架 dasar garbage collection, optimisasi garbage collection di versi berikutnya juga建立在 hybrid write barrier 的基础上，由于已经消除了大部分的 STW，此时垃圾回收的平均延时已经降低到了微秒级别。

Write Buffer

Dalam barrier mechanism yang disebutkan sebelumnya, saat拦截 write operation langsung menandai warna objek, setelah mengadopsi hybrid write barrier, karena perlu menandai objek asli dan objek baru, work akan翻倍，同时 compiler yang disisipkan kode juga akan增加。Untuk optimisasi，di versi go1.10, write barrier saat menandai warna tidak akan langsung menandai warna objek, tetapi akan menyimpan objek asli dan objek baru ke buffer pool, setelah terkumpul sejumlah tertentu, kemudian melakukan batch marking,这样做效率更高。

Struktur yang负责缓存 adalah runtime.wbBuf, sebenarnya adalah array, ukuran 512.

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

Setiap P lokal memiliki buffer seperti ini

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

Saat marking work berjalan, jika queue gcw tidak memiliki objek abu-abu yang tersedia, akan memasukkan objek di buffer ke queue lokal.

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)
  }
}

Situasi lain adalah, saat mark termination, juga akan memeriksa apakah wbBuf lokal setiap P memiliki sisa objek abu-abu

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

    wbBufFlush1(pp)

    pp.gcw.dispose()

  })
    ...
}

Sweep

Dalam garbage collection, bagian terpenting adalah bagaimana menemukan objek sampah, yaitu pekerjaan scan marking, dan setelah marking work selesai, pekerjaan sweep relatif tidak terlalu kompleks, hanya perlu回收 objek yang tidak ditandai dan lepaskan. Bagian kode ini terutama di file runtime/mgcsweep.go,根据文件中注释可以得知 Go 中的回收算法分为两种。

Object Sweep

Pekerjaan object sweep akan dilakukan di mark termination stage, oleh runtime.sweepone untuk menyelesaikan pekerjaan清理, proses adalah asynchronous. Saat清理, akan mencoba mencari objek yang tidak ditandai di memory unit, kemudian回收. Jika seluruh memory unit tidak ditandai, maka seluruh unit akan di回收.

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
}

Untuk algoritma object sweep而言，回收 seluruh unit cukup sulit, jadi ada algoritma sweep kedua.

Span Sweep

Pekerjaan span sweep dilakukan sebelum alokasi memori, oleh metode runtime.mheap.reclaim untuk menyelesaikan, akan mencari semua memory unit di heap yang semua objeknya tidak ditandai, kemudian回收 seluruh unit.

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)
}

Untuk memory unit而言，ada field sweepgen untuk menunjukkan status sweep-nya

• mspan.sweepgen == mheap.sweepgen - 2: Memory unit ini perlu di-sweep
• mspan.sweepgen == mheap.sweepgen - 1: Memory unit ini sedang di-sweep
• mspan.sweepgen == mheap.sweepgen: Memory unit ini sudah di-sweep, dapat digunakan normal
• mspan.sweepgen == mheap.sweepgen + 1: Memory unit di cache, dan perlu di-sweep
• mspan.sweepgen == mheap.sweepgen + 3: Memory unit sudah di-sweep, tetapi masih di cache

mheap.sweepgen akan增加 seiring putaran GC, dan setiap kali akan +2.