gc

La recolección de basura tiene como objetivo liberar la memoria de objetos que ya no se usan, liberando espacio para otros objetos. Aunque esta descripción es simple, su implementación es extraordinariamente compleja. El desarrollo de la recolección de basura tiene décadas de historia. El lenguaje Lisp en la década de 1960 adoptó por primera vez el mecanismo de recolección de basura. Como sabemos, Python y Objective-C utilizan principalmente el mecanismo de conteo de referencias, mientras que Java y C# utilizan la recolección generacional.

En la actualidad, los algoritmos de recolección de basura se pueden clasificar en las siguientes categorías:

Conteo de referencias: Cada objeto registra cuántas veces es referenciado. Cuando el conteo es 0, se recicla.
Mark-Sweep (Marcado y Limpieza): Marca los objetos activos y recicla los objetos no marcados.
Algoritmo de Copia: Copia los objetos activos a nueva memoria y recicla todos los objetos en la memoria antigua.
Mark-Compact (Marcado y Compactación): Versión mejorada de Mark-Sweep. Mueve los objetos activos al inicio del heap para facilitar la gestión.

Desde la perspectiva de aplicación, se pueden clasificar en:

Recolección Global: Recicla toda la basura de una vez
Recolección Generacional: Divide los objetos en diferentes generaciones según su tiempo de vida y adopta diferentes algoritmos de recolección
Recolección Incremental: Cada vez solo realiza recolección de basura local

TIP

Visite The Journey of Go's Garbage Collector para leer el artículo original en inglés y obtener más información sobre la historia de la recolección de basura en Go.

Cuando se lanzó por primera vez, el mecanismo de recolección de basura de Go era muy básico, solo con el algoritmo simple de mark-sweep. El STW (Stop The World, pausa del programa debido a la recolección de basura) podía durar varios segundos o más. Al darse cuenta de este problema, el equipo de Go comenzó a mejorar el algoritmo de recolección de basura. Entre las versiones go1.0 y go1.8, intentaron muchas ideas:

GC de Copia Concurrente con Read Barrier: La sobrecarga del read barrier tenía muchas incertidumbres, por lo que este plan fue cancelado.
Recolector Orientado a Demandas (ROC): Requería habilitar write barrier en todo momento, lo que ralentizaba la ejecución y aumentaba el tiempo de compilación.
Recolección Generacional: La eficiencia de la recolección generacional en Go no era alta, porque el compilador de Go tiende a asignar nuevos objetos en el stack y objetos de larga duración en el heap, por lo que la mayoría de los objetos de nueva generación se reciclaban directamente desde el stack.
Marking de Tarjetas sin Write Barrier: Reemplazaba el costo del write barrier con el costo de hash, requiriendo soporte de hardware.

Finalmente, el equipo de Go eligió la combinación de marcado tricromático concurrente + write barrier, y continuó mejorando y optimizando en versiones posteriores. Este enfoque se ha mantenido hasta ahora. El siguiente conjunto de gráficos muestra los cambios de latencia de GC desde go1.4 hasta go1.9.

Al escribir este artículo, la última versión de Go está a punto de llegar a go1.23. Para el Go actual, el rendimiento de GC ya no es un problema. La latencia de GC en la mayoría de los casos es inferior a 100 microsegundos, satisfaciendo las necesidades de la mayoría de los escenarios de negocio.

En general, la recolección de basura en Go se puede dividir en las siguientes etapas:

Etapa de Escaneo: Recopila objetos raíz desde el stack y variables globales
Etapa de Marcado: Colorea los objetos
Etapa de Terminación de Marcado: Maneja el trabajo posterior, cierra barriers
Etapa de Reciclaje: Libera y recicla la memoria de objetos basura

Conceptos

En la documentación oficial y artículos pueden aparecer los siguientes conceptos:

Mutator (Asignador): Término que se refiere al programa de usuario. En Go se refiere al código de usuario.
Collector (Recolector): Se refiere al programa responsable de la recolección de basura. En Go, es el runtime.
Finalizer (Finalizador): Código responsable de reciclar, liberar y limpiar la memoria de objetos después de completar el trabajo de marcado y escaneo.
Controller (Controlador): Se refiere a la variable global runtime.gcController, cuyo tipo es gcControllerState. Implementa el algoritmo de pacing y es responsable de determinar cuándo realizar la recolección de basura y cuánto trabajo ejecutar.
Limiter (Limitador): Se refiere a runtime.gcCPULimiter, responsable de prevenir que el uso de CPU sea demasiado alto durante la recolección de basura, afectando el programa de usuario.

Activación

func gcStart(trigger gcTrigger)

La recolección de basura es iniciada por la función runtime.gcStart, que solo recibe el parámetro de tipo runtime.gcTrigger. Este contiene la razón de activación del GC, la hora actual y el número de ronda de GC.

type gcTrigger struct {
    kind gcTriggerKind
    now  int64  // gcTriggerTime: hora actual
    n    uint32 // gcTriggerCycle: número de ciclo para iniciar
}

Donde gcTriggerKind tiene los siguientes valores opcionales:

const (
  // gcTriggerHeap indica que se debe iniciar un ciclo cuando
  // el tamaño del heap alcanza el tamaño de activación calculado por el
  // controlador.
  gcTriggerHeap gcTriggerKind = iota

  // gcTriggerTime indica que se debe iniciar un ciclo cuando
  // ha pasado más de forcegcperiod nanosegundos desde el
  // ciclo de GC anterior.
  gcTriggerTime

  // gcTriggerCycle indica que se debe iniciar un ciclo si
  // aún no hemos iniciado el ciclo número gcTrigger.n (relativo
  // a work.cycles).
  gcTriggerCycle
)

En resumen, hay tres momentos de activación de la recolección de basura:

Al crear un nuevo objeto: Al asignar memoria en runtime.mallocgc, si se detecta que la memoria del heap alcanza el umbral (generalmente el doble del GC anterior, este valor también se ajusta mediante el algoritmo de pacing), se inicia la recolección de basura.
go
```
func mallocgc(size uintptr, typ *_type, needzero bool) unsafe.Pointer {
    ...
  if shouldhelpgc {
    if t := (gcTrigger{kind: gcTriggerHeap}); t.test() {
      gcStart(t)
    }
  }
    ...
}
```

Activación forzada periódica: Go inicia una goroutine separada en tiempo de ejecución para ejecutar la función runtime.forcegchelper. Si no se ha realizado la recolección de basura durante mucho tiempo, forzará el inicio del GC. Este tiempo está determinado por la constante runtime.forcegcperiod, cuyo valor es 2 minutos. Al mismo tiempo, la goroutine de monitorización del sistema también verifica periódicamente si es necesario forzar el GC.

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

func sysmon() {
    ...
  for {
        ...
    // verificar si necesitamos forzar un 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)
    }
  }
}

Activación manual: A través de la función runtime.GC, los usuarios pueden activar manualmente la recolección de basura.

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

TIP

Para más información, visite Go Gc Pacer Re-Design para leer el artículo original en inglés sobre el diseño y las mejoras del algoritmo de pacing (pacing algorithm) para activar GC. Debido a que el contenido es bastante complejo e involucra demasiadas fórmulas matemáticas, no se profundiza en el texto principal.

Marcado

Hoy en día, el algoritmo de GC de Go sigue siendo marcar primero y luego limpiar, pero su implementación ya no es tan simple como antes.

Mark-Sweep

Comencemos con el algoritmo mark-sweep más simple. En la memoria, las referencias entre objetos forman un grafo. El trabajo de recolección de basura se realiza en este grafo, dividido en dos etapas:

Etapa de Marcado: Comienza desde los nodos raíz (los nodos raíz suelen ser variables en el stack, variables globales y otros objetos activos), recorre cada nodo alcanzable y los marca como objetos activos, hasta recorrer todos los nodos alcanzables.
Etapa de Limpieza: Recorre todos los objetos en el heap y recicla los objetos no marcados, liberando o reutilizando su espacio de memoria.

Durante el proceso de reciclaje, la estructura del grafo de objetos no puede cambiar, por lo que se debe detener todo el programa, es decir, STW. Solo después de completar el reciclaje se puede continuar la ejecución. La desventaja de este algoritmo es que consume mucho tiempo y afecta bastante la eficiencia de ejecución del programa. Este fue el algoritmo de marcado utilizado en las versiones tempranas de Go. Sus desventajas son obvias:

Genera fragmentación de memoria (debido a la gestión de memoria estilo TCMalloc de Go, el impacto de la fragmentación no es significativo)
Durante la etapa de marcado, escanea todos los objetos en el heap
Causa STW, pausando todo el programa, y el tiempo no es corto

Marcado Tricromático

Para mejorar la eficiencia, Go adoptó el clásico algoritmo de marcado tricromático. Los tres colores son negro, gris y blanco:

Negro: El objeto ha sido visitado durante el proceso de marcado, y todos los objetos que referencia directamente también han sido visitados. Representa objetos activos.
Gris: El objeto ha sido visitado durante el proceso de marcado, pero los objetos que referencia directamente no han sido completamente visitados. Cuando todos han sido visitados, se convierte en negro. Representa objetos activos.
Blanco: El objeto nunca ha sido visitado durante el proceso de marcado. Después de ser visitado, se convierte en gris. Representa posibles objetos basura.

Al inicio del trabajo de marcado tricromático, solo hay objetos grises y blancos. Todos los objetos raíz son grises y otros objetos son blancos, como se muestra a continuación:

En cada ronda de marcado, primero se comienza con los objetos grises. Los objetos grises se marcan como negros, indicando que son objetos activos. Luego, todos los objetos referenciados directamente por los objetos negros se marcan como grises. El resto permanece blanco. En este punto, hay tres colores en el campo:

Se repiten los pasos anteriores hasta que solo quedan objetos negros y blancos. Cuando la colección de objetos grises está vacía, significa que el marcado ha terminado:

Después del marcado, en la etapa de limpieza solo es necesario liberar la memoria de los objetos en la colección blanca.

Invariantes

El algoritmo de marcado tricromático en sí no puede realizar marcado concurrente (el programa se ejecuta y marca al mismo tiempo). Si la estructura del grafo de objetos cambia durante el marcado, esto puede causar dos situaciones:

Marcado Excesivo: Después de que un objeto se marca como negro, el programa de usuario elimina todas las referencias a ese objeto. Debería ser un objeto blanco y necesita ser limpiado.
Marcado Insuficiente: Después de que un objeto se marca como blanco, otros objetos en el programa de usuario referencian ese objeto. Debería ser un objeto negro y no debería ser limpiado.

La primera situación es aceptable, porque los objetos no limpiados pueden ser procesados en la siguiente ronda de reciclaje. Pero la segunda situación es inaceptable. La memoria de un objeto en uso se libera incorrectamente, lo que causará errores graves en el programa. Esto debe evitarse.

El concepto de Invariante Tricromático proviene del artículo 《Barrier Techniques for Incremental Tracing》 publicado por Pekka P. Pirinen en 1998. Se refiere a dos invariantes de color de objetos durante el marcado concurrente:

Invariante Tricromático Fuerte: Los objetos negros no pueden referenciar directamente objetos blancos.
Invariante Tricromático Débil: Cuando un objeto negro referencia directamente un objeto blanco, debe haber otro objeto gris que pueda acceder directa o indirectamente a ese objeto blanco, llamado protección del objeto gris.

Para el invariante tricromático fuerte, se sabe que el objeto negro 3 es un objeto que ya ha sido visitado, y sus objetos hijos también han sido visitados y marcados como objetos grises. Si en este momento el programa de usuario agrega concurrentemente una nueva referencia al objeto blanco 7 para el objeto negro 3, normalmente el objeto blanco 7 debería marcarse como gris. Pero como el objeto negro 3 ya ha sido visitado, el objeto 7 no será visitado, por lo que siempre será un objeto blanco y finalmente se limpiará incorrectamente.

Para el invariante tricromático débil, es similar al invariante tricromático fuerte. Como el objeto gris puede acceder directa o indirectamente al objeto blanco, durante el proceso de marcado posterior eventualmente se marcará como objeto gris, evitando así que se limpie incorrectamente.

A través de los invariantes, se puede asegurar que ningún objeto se limpie incorrectamente durante el proceso de marcado, garantizando así la corrección del trabajo de marcado en condiciones concurrentes. Esto permite que el marcado tricromático funcione concurrentemente, mejorando significativamente la eficiencia de marcado en comparación con el algoritmo mark-sweep. Para garantizar los invariantes tricromáticos en condiciones concurrentes, la clave está en la tecnología de barrier.

Trabajo de Marcado

Durante la etapa de escaneo de GC, hay una variable global runtime.gcphase que indica el estado del GC, con los siguientes valores opcionales:

_GCoff: El trabajo de marcado no ha comenzado
_GCmark: El trabajo de marcado ha comenzado
_GCmarktermination: El trabajo de marcado está a punto de terminar

Cuando comienza el trabajo de marcado, el estado de runtime.gcphase es _GCmark. La función que ejecuta el trabajo de marcado es runtime.gcDrain, donde el parámetro runtime.gcWork es un pool de búfer que contiene punteros de objetos a rastrear.

func gcDrain(gcw *gcWork, flags gcDrainFlags)

Durante el trabajo, intenta obtener punteros rastreables del pool de búfer. Si los hay, llama a la función runtime.scanobject para continuar con la tarea de escaneo. Su función es escanear continuamente los objetos en el búfer y marcarlos como negros.

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

b := gcw.tryGetFast()
if b == 0 {
    b = gcw.tryGet()
    if b == 0 {
        // Limpiar el búfer de write barrier
        // esto puede crear más trabajo.
        wbBufFlush()
        b = gcw.tryGet()
    }
}
if b == 0 {
    // No se puede obtener trabajo.
    break
}
scanobject(b, gcw)

El trabajo de escaneo se detiene solo cuando P es preemptado o va a ocurrir STW:

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

runtime.gcwork es una cola que adopta el modelo productor/consumidor. Esta cola es responsable de almacenar los objetos grises pendientes de escaneo. Cada procesador P tiene localmente una cola de este tipo, correspondiente al campo 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)
}

La función runtime.scanobject marca continuamente los objetos blancos alcanzables como grises durante el escaneo, luego los coloca en la cola local a través de gcw.put. Al mismo tiempo, la función gcDrain intenta continuamente obtener objetos grises a través de gcw.tryget para continuar el escaneo. El proceso de marcado y escaneo es incremental, no necesita completar todo el trabajo de marcado de una vez. Cuando la tarea de marcado es preemptada por alguna razón, se interrumpe. Cuando se reanuda, puede continuar completando el trabajo de marcado según los objetos grises restantes en la cola.

Marcado en Segundo Plano

El trabajo de marcado no se ejecuta inmediatamente al iniciar GC. Al activar GC, Go creará tantas tareas de marcado como procesadores P actuales. Se agregarán a la cola de tareas global y luego entrarán en estado de hibernación hasta ser despertadas en la etapa de marcado. En tiempo de ejecución, runtime.gcBgMarkStartWorkers realiza la distribución de tareas. La tarea de marcado se refiere realmente a la función runtime.gcBgMarkWorker, donde las variables globales de tiempo de ejecución gcBgMarkWorkerCount y gomaxprocs representan la cantidad actual de workers y la cantidad de procesadores P, respectivamente.

func gcBgMarkStartWorkers() {
  // El marcado en segundo plano es realizado por Gs por-P. Asegurar que cada P tenga
  // un G de GC en segundo plano.
  //
  // Los Gs de worker no salen si gomaxprocs se reduce. Si se eleva
  // nuevamente, podemos reutilizar los workers antiguos; no es necesario crear nuevos workers.
  for gcBgMarkWorkerCount < gomaxprocs {
    go gcBgMarkWorker()

    notetsleepg(&work.bgMarkReady, -1)
    noteclear(&work.bgMarkReady)
    // El worker ahora está garantizado para ser agregado al pool antes
    // del próximo findRunnableGCWorker del P.

    gcBgMarkWorkerCount++
  }
}

Después de que el worker se inicia, crea una estructura runtime.gcBgMarkWorkerNode, la agrega al pool global de workers runtime.gcBgMarkWorkerPool, luego llama a la función runtime.gopark para hacer que la goroutine entre en hibernación:

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

  for {
    // Ir a dormir hasta ser despertado por
    // gcController.findRunnableGCWorker.
    gopark(func(g *g, nodep unsafe.Pointer) bool {
      node := (*gcBgMarkWorkerNode)(nodep)
      // Liberar este G al pool.
      gcBgMarkWorkerPool.push(&node.node)
      // Notar que en este punto, el G puede ser inmediatamente
      // reprogramado y puede estar ejecutándose.
      return true
    }, unsafe.Pointer(node), waitReasonGCWorkerIdle, traceBlockSystemGoroutine, 0)
    }
    ...
}

Hay dos situaciones que pueden despertar al worker:

Durante la etapa de marcado, el bucle de planificación despertará al worker en hibernación a través de la función runtime.gcController.findRunnableGCWorker
Durante la etapa de marcado, si el procesador P está actualmente inactivo, el bucle de planificación intentará obtener directamente un worker disponible del pool global de workers gcBgMarkWorkerPool

func findRunnable() (gp *g, inheritTime, tryWakeP bool) {
top:
    // Intentar programar un worker de GC.
  if gcBlackenEnabled != 0 {
    gp, tnow := gcController.findRunnableGCWorker(pp, now)
    if gp != nil {
      return gp, false, true
    }
    now = tnow
  }
    ...
    // No tenemos nada que hacer.
  //
  // Si estamos en la fase de marcado de GC, podemos escanear y ennegrecer objetos de forma segura,
  // y tenemos trabajo que hacer, ejecutar marcado en tiempo inactivo en lugar de ceder el 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()
  }
    ...
}

El procesador P tiene un campo en la estructura gcMarkWorkerMode que indica el modo de ejecución de la tarea de marcado, con los siguientes valores opcionales:

gcMarkWorkerNotWorker: Indica que el procesador P actual no está ejecutando una tarea de marcado.
gcMarkWorkerDedicatedMode: Indica que el procesador P está dedicado a ejecutar tareas de marcado y no será preemptado durante este período.
gcMarkWorkerFractionalMode: Indica que el procesador está ejecutando tareas de marcado porque la utilización de GC no alcanza el estándar (25% es el estándar) y puede ser preemptado durante la ejecución. Supongamos que la cantidad actual de procesadores P es 5, según la fórmula de cálculo, en este momento se necesita un procesador P dedicado al marcado de tareas. La utilización solo alcanza el 20%, y el 5% restante de utilización requiere habilitar un procesador P en modo FractionalMode para compensar. El código de cálculo específico se muestra a continuación:
go
```
func (c *gcControllerState) startCycle(markStartTime int64, procs int, trigger gcTrigger) {
  ...
  totalUtilizationGoal := float64(procs) * gcBackgroundUtilization
  dedicatedMarkWorkersNeeded := int64(totalUtilizationGoal + 0.5)
    if float64(dedicatedMarkWorkersNeeded) > totalUtilizationGoal {
        // Demasiados workers dedicados.
        dedicatedMarkWorkersNeeded--
    }
    c.fractionalUtilizationGoal = (totalUtilizationGoal - float64(dedicatedMarkWorkersNeeded)) / float64(procs)
    ...
}
```
gcMarkWorkerIdleMode: Indica que el procesador está ejecutando tareas de marcado porque está inactivo y puede ser preemptado durante la ejecución.

El equipo de Go no quiere que GC ocupe demasiado rendimiento afectando el funcionamiento normal del programa de usuario. Realizar el trabajo de marcado según estos diferentes modos puede completar GC sin desperdiciar rendimiento ni afectar el programa de usuario. Es importante notar que la unidad básica de asignación de tareas de marcado es el procesador P, por lo que el trabajo de marcado se realiza concurrentemente. Múltiples tareas de marcado y el programa de usuario se ejecutan concurrentemente sin afectarse mutuamente.

Marcado Asistido

La goroutine G tiene un campo gcAssistBytes en tiempo de ejecución, al que llamaremos puntos de asistencia de GC. Durante el estado de marcado de GC, cuando una goroutine intenta asignar memoria de cierto tamaño, se le deducirán puntos iguales al tamaño de memoria asignado. Si los puntos son negativos en este momento, la goroutine debe ayudar a completar una cantidad cuantitativa de tareas de escaneo de GC para pagar los puntos. Cuando los puntos son positivos, la goroutine no necesita completar las tareas de marcado asistido.

La función que deduce los puntos es runtime.deductAssistCredit, que se llama antes de que la función runtime.mallocgc asigne memoria.

func deductAssistCredit(size uintptr) *g {
    var assistG *g
    if gcBlackenEnabled != 0 {
       // Cobrar al G de usuario actual por esta asignación.
       assistG = getg()
       if assistG.m.curg != nil {
          assistG = assistG.m.curg
       }
       // Cobrar la asignación contra el G. Contabilizaremos
       // la fragmentación interna al final de mallocgc.
       assistG.gcAssistBytes -= int64(size)

       if assistG.gcAssistBytes < 0 {
          // Este G está en deuda. Asistir al GC para corregir
          // esto antes de asignar. Esto debe ocurrir
          // antes de deshabilitar la preempción.
          gcAssistAlloc(assistG)
       }
    }
    return assistG
}

Sin embargo, cuando la goroutine completa una cantidad cuantitativa de trabajo de escaneo asistido, pagará una cantidad cuantitativa de puntos a la goroutine actual. La función que realmente es responsable del marcado asistido es runtime.gcDrainN.

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

Dado que el escaneo es concurrente, solo una parte del trabajo registrado es de la goroutine actual. El resto del trabajo se pagará a otras goroutines según el orden de la cola de asistencia. Si aún queda algo, se agregará a los puntos globales gcController.assistBytesPerWork.

func gcFlushBgCredit(scanWork int64) {
    // Si la cola está vacía, agregar directamente a los puntos globales
  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
    }
  }

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

Correspondientemente, cuando se necesitan pagar demasiados puntos (se asigna demasiada memoria), también se pueden usar los puntos globales para compensar parte de la deuda propia:

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

    // Usar puntos globales como garantía
  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
    }
  }
    ...
}

El marcado asistido es un medio de equilibrio en condiciones de alta carga. La velocidad a la que el programa de usuario asigna memoria es mucho mayor que la velocidad de marcado. Se realiza tanto trabajo de marcado como memoria se asigna.

Terminación de Marcado

Cuando todos los objetos grises alcanzables se han vuelto negros, se transita del estado _GCmark al estado _GCmarktermination. Este proceso es completado por la función runtime.gcMarkDone. Al inicio, verifica si aún hay tareas por ejecutar:

top:

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

  gcMarkDoneFlushed = 0
  // Ejecutar por lotes todas las operaciones de marcado interceptadas por write barrier
  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
  }

Cuando no hay tareas globales ni locales por ejecutar, llama a runtime.stopTheWorldWithSema para STW, luego realiza algunas tareas de finalización:

// Deshabilitar asistencias y workers en segundo plano. Debemos hacer
// esto antes de despertar asistencias bloqueadas.
atomic.Store(&gcBlackenEnabled, 0)

// Notificar al limitador de CPU que las asistencias de GC cesarán ahora.
gcCPULimiter.startGCTransition(false, now)

// Despertar todas las asistencias bloqueadas. Estas se ejecutarán cuando
// reiniciemos el mundo.
gcWakeAllAssists()

// En modo STW, re-habilitar goroutines de usuario. Estas se pondrán en cola
// para ejecutarse después de que reiniciemos el mundo.
schedEnableUser(true)

// endCycle depende de que todas las estadísticas de caché gcWork estén limpiadas.
// El algoritmo de terminación anterior aseguró que hasta
// asignaciones desde la barrier irregular.
gcController.endCycle(now, int(gomaxprocs), work.userForced)

// Realizar terminación de marcado. Esto reiniciará el mundo.
gcMarkTermination(stw)

Primero establece runtime.gcBlackenEnabled a 0, indicando que el trabajo de marcado ha terminado. Notifica al limitador que la asistencia de marcado ha terminado, cierra la barrera de memoria, despierta todas las goroutines en hibernación debido al marcado asistido, luego reactiva todas las goroutines de usuario. También debe recopilar varios datos del trabajo de escaneo de esta ronda para ajustar el algoritmo de pacing y prepararse para la siguiente ronda de escaneo. Después de completar las tareas de finalización, llama a la función runtime.gcSweep para limpiar objetos basura. Finalmente, llama a runtime.startTheWorldWithSema para reanudar la ejecución del programa.

Barriers

El propósito de la barrera de memoria se puede entender como hacer hook del comportamiento de asignación de objetos, realizando algunas operaciones especificadas antes de la asignación. Este código de hook generalmente se inserta en el código por el compilador durante la compilación. Como se mencionó anteriormente, agregar y eliminar referencias de objetos en condiciones concurrentes causará problemas en el marcado tricromático. Como ambas son operaciones de escritura (eliminar es asignar valor nulo), las barriers que las interceptan se denominan colectivamente write barriers. Pero el mecanismo de barrier no es sin costo. Interceptar operaciones de escritura de memoria causará sobrecarga adicional. Por lo tanto, el mecanismo de barrier solo funciona en el heap. Considerando la complejidad de implementación y la pérdida de rendimiento, no funciona para stack y registros.

TIP

Para obtener más detalles sobre la aplicación de la tecnología de barrier en Go, visite Eliminate STW stack rescan para leer el artículo original en inglés. Este artículo hace referencia a mucho de su contenido.

Insert Write Barrier

El insert write barrier fue propuesto por Dijkstra. Satisface el invariante tricromático fuerte. Cuando se agrega una nueva referencia de objeto blanco a un objeto negro, el insert write barrier interceptará esta operación y marcará el objeto blanco como gris. Esto evita que los objetos negros referencien directamente objetos blancos, garantizando el invariante tricromático fuerte. Esto es bastante fácil de entender.

Como se mencionó anteriormente, el write barrier no se aplica al stack. Si la relación de referencia de objetos de stack cambia durante el proceso de marcado concurrente, como cuando un objeto negro en el stack referencia un objeto blanco en el heap, para garantizar la corrección de los objetos de stack, solo se pueden marcar todos los objetos en el stack como objetos grises nuevamente después de que finalice el marcado. Luego se debe escanear nuevamente, lo que equivale a escanear el espacio de stack dos veces en una ronda de marcado. Y durante el segundo escaneo, se debe realizar STW. Si hay cientos o miles de stacks de goroutines coexistiendo en el programa, el tiempo consumido por este proceso de escaneo no se puede ignorar. Según los datos estadísticos oficiales, el tiempo de reescaneo es de aproximadamente 10-100 milisegundos.

Ventajas: No se requiere STW durante el escaneo

Desventajas: Se requiere un segundo escaneo del espacio de stack para garantizar la corrección, se requiere STW

Delete Write Barrier

El delete write barrier fue propuesto por Yuasa, también conocido como snapshot-at-the-beginning barrier. Este método requiere STW al inicio para tomar una instantánea de los objetos raíz y marcará todos los objetos raíz como negros y todos los objetos hijos de primer nivel como grises. De esta manera, el resto de los objetos hijos blancos estarán bajo la protección de los objetos grises. El equipo de Go no aplicó directamente el delete write barrier, sino que eligió mezclarlo con el insert write barrier. Para facilitar la comprensión posterior, aún debemos explicarlo aquí. La regla del delete write barrier para garantizar la corrección en condiciones concurrentes es: cuando se elimina una referencia a un objeto blanco desde un objeto gris o blanco, el objeto blanco se marcará directamente como gris.

Se interpreta en dos situaciones:

Eliminar referencia de objeto gris a objeto blanco: Como no se sabe si el objeto blanco está referenciado por un objeto negro aguas abajo, esto puede cortar la protección del objeto gris al objeto blanco.
Eliminar referencia de objeto blanco a objeto blanco: Como no se sabe si el objeto blanco está protegido por un objeto gris aguas arriba y si está referenciado por un objeto negro aguas abajo, esto también puede cortar la protección del objeto gris al objeto blanco.

Independientemente de la situación, el delete write barrier marcará el objeto blanco referenciado como gris. De esta manera se puede satisfacer el invariante tricromático débil. Esta es una práctica conservadora, porque las situaciones aguas arriba y aguas abajo son desconocidas. Marcarlo como gris equivale a no tratarlo más como un objeto basura. Incluso si eliminar la referencia hace que el objeto sea inalcanzable, es decir, se convierte en un objeto basura, aún se marcará como gris. Se liberará en la siguiente ronda de escaneo, lo cual es mejor que los errores de memoria causados por la limpieza incorrecta de objetos.

Ventajas: Como los objetos de stack son todos negros, no se requiere un segundo escaneo del espacio de stack

Desventajas: Se requiere STW al inicio del escaneo para tomar una instantánea de los objetos raíz en el espacio de stack

Hybrid Write Barrier

La versión go1.8 introdujo un nuevo mecanismo de barrier: hybrid write barrier, es decir, la mezcla de insert write barrier y delete write barrier, combinando las ventajas de ambos:

El insert write barrier no requiere STW para tomar una instantánea al inicio
El delete write barrier no requiere STW para escanear nuevamente el espacio de stack

A continuación se muestra el pseudocódigo proporcionado por los oficiales:

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

Explicación simple de algunos conceptos en el pseudocódigo anterior: slot es un puntero que representa una referencia a otro objeto, *slot es el objeto original, ptr es el nuevo objeto, *slot=ptr es una operación de asignación, equivalente a modificar la referencia del objeto. Asignar valor nulo es eliminar la referencia. shade() significa marcar un objeto como gris. shade(*slot) significa marcar el objeto original como gris. shade(ptr) significa marcar el nuevo objeto como gris. A continuación se muestra un diagrama de ejemplo. Supongamos que el objeto 1 originalmente referenciaba al objeto 2, luego el programa de usuario modificó la referencia para que el objeto 1 referencie al objeto 3. El hybrid write barrier capturó este comportamiento, donde *slot representa el objeto 2 y ptr representa el objeto 1.

Los oficiales resumieron el efecto del pseudocódigo anterior en una oración:

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.

Traducido, significa: cuando el hybrid write barrier intercepta una operación de escritura, marcará el objeto original como gris. Si el stack de la goroutine actual aún no ha sido escaneado, también marcará el nuevo objeto como gris.

Cuando comienza el trabajo de marcado, se debe escanear el espacio de stack para recopilar objetos raíz. En este momento, se marcarán directamente todos como negros. Durante este período, cualquier objeto recién creado también se marcará como negro para garantizar que todos los objetos en el stack sean objetos negros. Por lo tanto, current stack is grey en el pseudocódigo representa que el stack de la goroutine actual aún no ha sido escaneado. Por lo tanto, el stack de la goroutine solo tiene dos estados: todo negro o todo gris. Durante el proceso de cambio de todo gris a todo negro, se debe pausar la goroutine actual. Por lo tanto, todavía habrá STW local bajo el hybrid write barrier. Cuando el stack de la goroutine es todo negro, definitivamente se debe satisfacer el invariante tricromático fuerte, porque después del escaneo, los objetos negros en el stack solo referenciarán objetos grises. No habrá una situación en la que un objeto negro referencie directamente un objeto blanco. Por lo tanto, en este momento no se requiere insert write barrier, correspondiente al pseudocódigo:

if current stack is grey:
        shade(ptr)

Pero aún se requiere delete write barrier para satisfacer el invariante tricromático débil, es decir:

shade(*slot)

Después de completar el escaneo, como los objetos en el espacio de stack ya son todos negros, ya no es necesario escanear nuevamente el espacio de stack. Se puede ahorrar el tiempo de STW.

Hasta aquí, es decir, desde la versión go1.8 en adelante, Go estableció básicamente el marco básico de recolección de basura. Las optimizaciones relacionadas con la recolección de basura en versiones posteriores también se basan en el hybrid write barrier. Como ya se eliminó la mayor parte del STW, la latencia promedio de recolección de basura se ha reducido al nivel de microsegundos.

Write Buffer

En el mecanismo de barrier mencionado anteriormente, al interceptar una operación de escritura, se marca inmediatamente el color del objeto. Después de adoptar el hybrid write barrier, como se deben marcar tanto el objeto original como el nuevo objeto, la cantidad de trabajo se duplicará. Al mismo tiempo, el código insertado por el compilador también aumentará. Para optimizar, en la versión go1.10, el write barrier ya no marca inmediatamente el color del objeto al realizar la着色. En su lugar, almacena el objeto original y el nuevo objeto en un pool de búfer. Cuando se acumula cierta cantidad, se realiza el marcado por lotes. Esto es más eficiente.

La estructura responsable del búfer es runtime.wbBuf, que en realidad es un array de tamaño 512.

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

Cada P local tiene un búfer de este tipo:

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

Cuando el trabajo de marcado está en progreso, si no hay objetos grises disponibles en la cola gcw, los objetos en el búfer se colocarán en la cola local.

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 {
        // Actualizar búfer de write barrier
        wbBufFlush()
        b = gcw.tryGet()
      }
    }
    if b == 0 {
      break
    }
    scanobject(b, gcw)
  }
}

Otra situación es que cuando se termina el marcado, también se verifica si el wbBuf local de cada P tiene objetos grises restantes:

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

    wbBufFlush1(pp)

    pp.gcw.dispose()

  })
    ...
}

Reciclaje

En la recolección de basura, la parte más importante radica en cómo encontrar objetos basura, es decir, el trabajo de escaneo y marcado. Después de completar el trabajo de marcado, el trabajo de reciclaje es relativamente menos complejo. Solo necesita reciclar y liberar los objetos no marcados. Este parte del código está principalmente en el archivo runtime/mgcsweep.go. Según los comentarios en el archivo, el algoritmo de reciclaje en Go se divide en dos tipos.

Reciclaje de Objetos

El trabajo de reciclaje de objetos se realiza en la etapa de terminación de marcado, completado por runtime.sweepone. El proceso es asíncrono. Durante la limpieza, intentará buscar objetos no marcados en la unidad de memoria y luego reciclarlos. Si toda la unidad de memoria no está marcada, entonces toda esta unidad se reciclará.

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
    }
        // Intentar obtener reciclador
    if s, ok := sl.tryAcquire(s); ok {
      npages = s.npages
            // Limpiar
      if s.sweep(false) {
        mheap_.reclaimCredit.Add(npages)
      } else {
        npages = 0
      }
      break
    }
  }
  sweep.active.end(sl)
  return npages
}

Para el algoritmo de reciclaje de objetos, reciclar toda la unidad es relativamente difícil. Por lo tanto, existe un segundo algoritmo de reciclaje.

Reciclaje de Unidades

El trabajo de reciclaje de unidades se realiza antes de la asignación de memoria, completado por el método runtime.mheap.reclaim. Buscará en el heap todas las unidades de memoria donde ningún objeto está marcado, y luego reciclará toda la unidad.

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

Para la unidad de memoria, hay un campo sweepgen que indica su estado de reciclaje:

mspan.sweepgen == mheap.sweepgen - 2: Esta unidad de memoria necesita ser reciclada
mspan.sweepgen == mheap.sweepgen - 1: Esta unidad de memoria está siendo reciclada
mspan.sweepgen == mheap.sweepgen: Esta unidad de memoria ya ha sido reciclada y se puede usar normalmente
mspan.sweepgen == mheap.sweepgen + 1: La unidad de memoria está en el búfer y necesita ser reciclada
mspan.sweepgen == mheap.sweepgen + 3: La unidad de memoria ya ha sido reciclada, pero aún está en el búfer

mheap.sweepgen aumentará con cada ronda de GC, y cada vez aumentará en +2.

gc ​

Conceptos ​

Activación ​

Marcado ​

Mark-Sweep ​

Marcado Tricromático ​

Invariantes ​

Trabajo de Marcado ​

Marcado en Segundo Plano ​

Marcado Asistido ​

Terminación de Marcado ​

Barriers ​

Insert Write Barrier ​

Delete Write Barrier ​

Hybrid Write Barrier ​

Write Buffer ​

Reciclaje ​

Reciclaje de Objetos ​

Reciclaje de Unidades ​

gc