gc

A coleta de lixo tem a função de liberar memória de objetos não utilizados, liberando espaço para outros objetos. Embora seja uma descrição simples, sua implementação é bastante complexa. O desenvolvimento da coleta de lixo já tem décadas, desde a linguagem Lisp dos anos 60 que adotou pela primeira vez o mecanismo de coleta de lixo. Como sabemos, Python e Objective-C usam principalmente contagem de referência, enquanto Java e C# usam coleta geracional.

Atualmente, em relação aos algoritmos de coleta, podemos dividir nas seguintes categorias principais:

• Contagem de referência: Cada objeto registra quantas vezes é referenciado; quando a contagem é 0, é回收
• Marcação-varredura: Marca objetos ativos e回收 objetos não marcados
• Algoritmo de cópia: Copia objetos ativos para nova memória e回收 toda memória antiga
• Marcação-compressão: Versão aprimorada da marcação-varredura, move objetos ativos para o início do heap para facilitar gerenciamento

Em termos de aplicação, pode ser dividido nas seguintes categorias:

• Coleta global: Recicla todo lixo de uma vez
• Coleta geracional: Divide objetos por tempo de vida e usa diferentes algoritmos
• Coleta incremental: Realiza coleta de lixo parcial a cada vez

TIP

Visite The Journey of Go's Garbage Collector para ler o artigo original em inglês e saber mais sobre a história da coleta de lixo do Go

Quando foi lançado, o mecanismo de coleta de lixo do Go era muito simples, apenas com algoritmo básico de marcação-varredura, e o STW (Stop The World, pausa do programa devido à coleta de lixo) chegava a vários segundos ou mais. Percebendo este problema, a equipe do Go começou a melhorar o algoritmo. Entre as versões go1.0 e go1.8, eles tentaram muitas abordagens:

1. GC de cópia concorrente com barreira de leitura: A sobrecarga da barreira de leitura tem muitas incertezas, então esta abordagem foi cancelada
2. Coletor orientado a demanda (ROC): Requer barreira de escrita sempre ativa, reduzindo velocidade de execução e tempo de compilação
3. Coleta geracional: A eficiência no Go não era alta, pois o compilador tende a alocar novos objetos na stack e objetos de longa duração no heap, então a maioria dos objetos da nova geração seria回收 diretamente pela stack
4. Marcação de cartões sem barreira de escrita: Substitui custo da barreira de escrita por custo de hash, requer hardware específico

Finalmente, a equipe do Go escolheu a combinação de marcação concorrente tricromática + barreira de escrita, continuamente melhorando e otimizando em versões subsequentes, abordagem que é usada até hoje. O conjunto de imagens abaixo mostra a variação de latência de GC do go1.4 ao go1.9.

Ao escrever este artigo, a versão mais recente do Go está prestes a chegar ao go1.23. Para o Go atual, o desempenho do GC já não é mais um problema; a latência do GC na maioria dos casos é inferior a 100 microssegundos, atendendo à maioria dos cenários de negócios.

Em geral, a coleta de lixo no Go pode ser dividida nas seguintes fases:

• Fase de varredura: Coleta objetos raiz da stack e variáveis globais
• Fase de marcação: Colore os objetos
• Fase de término de marcação: Processa trabalho de encerramento, fecha barreiras
• Fase de回收: Libera e回收 memória de objetos lixo

Conceitos

Na documentação e artigos oficiais podem aparecer os seguintes conceitos, explicados abaixo:

• Mutator (atribuidor): Termo que se refere ao programa do usuário; no Go, refere-se ao código do usuário
• Collector (coletor): Refere-se ao programa responsável pela coleta de lixo; no Go, é o runtime
• Finalizer (finalizador): Código responsável por回收 e liberar memória de objetos após conclusão da marcação-varredura
• Controller (controlador): Refere-se à variável global runtime.gcController, do tipo gcControllerState, que implementa algoritmo de pacing, responsável por determinar quando realizar coleta de lixo e quanto trabalho executar
• Limiter (limitador): Refere-se a runtime.gcCPULimiter, responsável por prevenir uso excessivo de CPU durante coleta de lixo afetando o programa do usuário

Acionamento

func gcStart(trigger gcTrigger)

A coleta de lixo é iniciada pela função runtime.gcStart, que recebe apenas o parâmetro runtime.gcTrigger, uma estrutura que contém o motivo do acionamento do GC, tempo atual e qual rodada de GC é esta.

type gcTrigger struct {
    kind gcTriggerKind
    now  int64  // gcTriggerTime: tempo atual
    n    uint32 // gcTriggerCycle: número do ciclo para iniciar
}

Onde gcTriggerKind tem os seguintes valores opcionais:

const (
  // gcTriggerHeap indica que um ciclo deve ser iniciado quando
  // o tamanho do heap atinge o tamanho de gatilho do heap calculado pelo
  // controlador.
  gcTriggerHeap gcTriggerKind = iota

  // gcTriggerTime indica que um ciclo deve ser iniciado quando
  // passou mais que forcegcperiod nanosegundos desde o
  // ciclo de GC anterior.
  gcTriggerTime

  // gcTriggerCycle indica que um ciclo deve ser iniciado se
  // ainda não iniciamos o ciclo número gcTrigger.n (relativo
  // a work.cycles).
  gcTriggerCycle
)

Em resumo, há três momentos de acionamento da coleta de lixo:

• Ao criar novo objeto: Ao alocar memória na função runtime.mallocgc, se for detectado que a memória do heap atingiu o limiar (geralmente o dobro do GC anterior, este valor também é ajustado pelo algoritmo de pacing), inicia-se a coleta de lixo

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

• Acionamento forçado periódico: O Go inicia uma goroutine separada em runtime para executar a função runtime.forcegchelper; se não houver coleta de lixo por muito tempo, ela força o início do GC. Este tempo é determinado pela constante runtime.forcegcperiod, cujo valor é 2 minutos. Também no monitor de sistema é feita verificação periódica se é necessário forçar GC

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

  func sysmon() {
      ...
    for {
          ...
      // verifica se precisamos forçar um 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)
      }
    }
  }

• Acionamento manual: Através da função runtime.GC, o usuário pode acionar manualmente a coleta de lixo

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

TIP

Interessados podem visitar Go Gc Pacer Re-Design para ler o artigo original em inglês, que explica o design e melhorias do algoritmo de pacing (pacing algorithm) para acionamento do GC. Por ser conteúdo bastante complexo envolvendo muitas fórmulas matemáticas, não será detalhado no texto principal.

Marcação

Atualmente, o algoritmo de GC do Go ainda é marcação seguida de varredura, mas sua implementação não é mais tão simples como antes.

Marcação-Varredura

Começando pelo algoritmo mais simples de marcação-varredura: na memória, as relações de referência entre objetos formam um grafo, e o trabalho de coleta de lixo ocorre neste grafo, dividido em duas fases:

• Fase de marcação: A partir dos nós raiz (normalmente variáveis na stack, objetos ativos de variáveis globais etc.), percorre-se cada nó alcançável, marcando-o como objeto ativo, até percorrer todos os nós alcançáveis
• Fase de varredura: Percorre-se todos os objetos no heap,回收 objetos não marcados, liberando ou reutilizando seu espaço de memória

Durante o processo de回收, a estrutura do grafo de objetos não pode ser alterada, então é necessário parar todo o programa, ou seja, STW, e só continuar executando após conclusão da回收. As desvantagens deste algoritmo são:

• Gera fragmentação de memória (devido ao gerenciamento de memória estilo TCMalloc do Go, o impacto da fragmentação não é grande)
• Na fase de marcação, varre-se todos os objetos do heap
• Causa STW, pausando todo o programa, e o tempo não é curto

Marcação Tricromática

Para melhorar a eficiência, o Go adotou o clássico algoritmo de marcação tricromática. As três cores são preto, cinza e branco:

• Preto: Objeto já访问 durante marcação, e todos os objetos que referencia diretamente também foram访问，representando objetos ativos
• Cinza: Objeto já访问 durante marcação, mas os objetos que referencia diretamente não foram todos访问; quando todos forem访问，torna-se preto, representando objetos ativos
• Branco: Objeto nunca访问 durante marcação; após访问，torna-se cinza, representando possível objeto lixo

No início do trabalho de marcação tricromática, há apenas objetos cinza e branco; todos os objetos raiz são cinza, e outros objetos são brancos, conforme mostrado abaixo:

A cada rodada de marcação, começa-se pelos objetos cinza, marcando-os como pretos (indicando objetos ativos), depois marca-se como cinza todos os objetos diretamente referenciados pelos objetos pretos; o restante é branco. Neste momento, há objetos das três cores.

Repete-se os passos acima até restarem apenas objetos pretos e brancos. Quando o conjunto de objetos cinza estiver vazio, representa o fim da marcação, conforme abaixo:

Após conclusão da marcação, na fase de varredura basta liberar a memória dos objetos brancos.

Invariância

O algoritmo de marcação tricromática em si não permite marcação concorrente (programa executando enquanto marca). Se a estrutura do grafo de objetos mudar durante marcação, pode causar duas situações:

• Marcação excessiva: Após objeto ser marcado como preto, o programa do usuário remove todas as referências a ele; deveria ser branco e ser回收
• Marcação insuficiente: Após objeto ser marcado como branco, outros objetos do usuário passam a referenciá-lo; deveria ser preto e não ser回收

O primeiro caso é aceitável, pois objetos não limpos podem ser tratados na próxima rodada de回收. Mas o segundo caso é inaceitável: liberar erroneamente memória de objeto em uso causaria erro grave no programa, problema que deve ser evitado.

O conceito de invariância tricromática vem do artigo 《Barrier Techniques for Incremental Tracing》 publicado por Pekka P. Pirinen em 1998, referindo-se a duas invariâncias de cor durante marcação concorrente:

• Forte invariância tricromática: Objetos pretos não podem referenciar diretamente objetos brancos
• Fraca invariância tricromática: Quando objeto preto referencia diretamente objeto branco, deve haver outro objeto cinza que possa direta ou indiretamente访问 este objeto branco, chamado de protegido pelo objeto cinza

Para a forte invariância tricromática: sabendo que o objeto preto 3 já foi访问 e seus objetos filhos também foram访问 e marcados como cinza, se o programa do usuário concorrentemente adicionar nova referência ao objeto branco 7 no objeto preto 3, normalmente o objeto branco 7 deveria ser marcado como cinza, mas como o objeto preto 3 já foi访问，o objeto 7 não será访问，permanecendo sempre branco e sendo erroneamente limpo.

Para a fraca invariância tricromática: é similar à forte invariância, pois o objeto cinza pode direta ou indiretamente访问 o objeto branco; durante marcação subsequente, eventualmente será marcado como cinza, evitando limpeza errônea.

Através da invariância, garante-se que objetos não serão limpos erroneamente durante marcação, assegurando correção do trabalho de marcação em condições concorrentes, permitindo que marcação tricromática funcione concorrentemente, melhorando significativamente a eficiência comparado ao algoritmo marcação-varredura. Para garantir invariância tricromática em condições concorrentes, a chave está na tecnologia de barreiras.

Trabalho de Marcação

Na fase de varredura do GC, há uma variável global runtime.gcphase para indicar o estado do GC, com os seguintes valores:

• _GCoff: Trabalho de marcação não iniciado
• _GCmark: Trabalho de marcação iniciado
• _GCmarktermination: Trabalho de marcação prestes a terminar

Quando o trabalho de marcação inicia, o estado de runtime.gcphase é _GCmark, e a execução é feita pela função runtime.gcDrain, onde o parâmetro runtime.gcWork é um buffer pool que armazena ponteiros de objetos a serem rastreados.

func gcDrain(gcw *gcWork, flags gcDrainFlags)

Durante o trabalho, tenta-se obter ponteiros rastreáveis do buffer pool; se houver, chama-se a função runtime.scanobject para continuar a tarefa de varredura, cuja função é varrer continuamente objetos no buffer, marcando-os como pretos.

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

b := gcw.tryGetFast()
if b == 0 {
    b = gcw.tryGet()
    if b == 0 {
        // Limpa o buffer
        // da barreira de escrita;
        // isso pode criar
        // mais trabalho.
        wbBufFlush()
        b = gcw.tryGet()
    }
}
if b == 0 {
    // Incapaz de obter trabalho.
    break
}
scanobject(b, gcw)

A varredura só para quando P é preemptado ou quando ocorrerá STW:

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

runtime.gcwork é uma fila que usa modelo produtor/consumidor, responsável por armazenar objetos cinza aguardando varredura. Cada processador P tem localmente tal fila, correspondendo ao 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)
}

A função runitme.scanobject marca continuamente objetos brancos alcançáveis como cinza durante varredura, depois os coloca na fila local através de gcw.put. Simultaneamente, a função gcDrain continuamente tenta obter objetos cinza através de gcw.tryget para continuar varredura. O processo de marcação-varredura é incremental, não precisando completar toda marcação de uma vez; quando a tarefa de marcação é preemptada por algum motivo, é interrompida, e ao retomar pode continuar o trabalho de marcação baseado nos objetos cinza restantes na fila.

Marcação em Segundo Plano

O trabalho de marcação não é executado imediatamente ao iniciar GC. Ao acionar GC, o Go cria tarefas de marcação em quantidade igual ao número total de processadores P atuais, que são adicionadas à fila global de tarefas e entram em dormência até serem acordadas na fase de marcação. Em runtime, a distribuição de tarefas é feita por runtime.gcBgMarkStartWorkers. A tarefa de marcação é na verdade a função runtime.gcBgMarkWorker, onde as variáveis globais de runtime gcBgMarkWorkerCount e gomaxprocs representam respectivamente o número atual de workers e o número de processadores P.

func gcBgMarkStartWorkers() {
  // Marcação em segundo plano é executada por Gs por-P. Garante que cada P tenha
  // um G de GC em segundo plano.
  //
  // Gs worker não saem se gomaxprocs for reduzido. Se for aumentado
  // novamente, podemos reutilizar workers antigos; não precisa criar novos workers.
  for gcBgMarkWorkerCount < gomaxprocs {
    go gcBgMarkWorker()

    notetsleepg(&work.bgMarkReady, -1)
    noteclear(&work.bgMarkReady)
    // O worker agora está garantido de ser adicionado ao pool antes
    // do próximo findRunnableGCWorker do P.

    gcBgMarkWorkerCount++
  }
}

Após o worker iniciar, cria uma estrutura runtime.gcBgMarkWorkerNode, adiciona-a ao pool global de workers runitme.gcBgMarkWorkerPool, depois chama a função runtime.gopark para fazer a goroutine entrar em dormência:

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

  for {
    // Vai dormir até ser acordado por
    // gcController.findRunnableGCWorker.
    gopark(func(g *g, nodep unsafe.Pointer) bool {
      node := (*gcBgMarkWorkerNode)(nodep)
      // Libera este G para o pool.
      gcBgMarkWorkerPool.push(&node.node)
      // Note que neste momento, o G pode imediatamente ser
      // reagendado e estar em execução.
      return true
    }, unsafe.Pointer(node), waitReasonGCWorkerIdle, traceBlockSystemGoroutine, 0)
    }
    ...
}

Há duas situações que podem acordar o worker:

• Durante fase de marcação, o loop de escalonamento acorda workers em dormência através da função runtime.runtime.gcController.findRunnableGCWorker
• Durante fase de marcação, se o processador P estiver ocioso, o loop de escalonamento tenta obter diretamente workers disponíveis do pool global de workers gcBgMarkWorkerPool

func findRunnable() (gp *g, inheritTime, tryWakeP bool) {
top:
    // Tenta agendar um worker GC.
  if gcBlackenEnabled != 0 {
    gp, tnow := gcController.findRunnableGCWorker(pp, now)
    if gp != nil {
      return gp, false, true
    }
    now = tnow
  }
    ...
    // Não temos nada para fazer.
  //
  // Se estivermos na fase de marcação GC, podemos seguramente varrer e enegrecer objetos,
  // e temos trabalho para fazer, executa marcação em tempo ocioso ao invés de desistir do 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()
  }
    ...
}

O processador P tem um campo gcMarkWorkerMode na estrutura para indicar o modo de execução da tarefa de marcação, com os seguintes valores:

• gcMarkWorkerNotWorker: Indica que o processador P atual não está executando tarefa de marcação

• gcMarkWorkerDedicatedMode: Indica que o processador P atual é dedicado para execução de tarefa de marcação e não pode ser preemptado durante o período

• gcMarkWorkerFractionalMode: Indica que o processador atual está executando tarefa de marcação porque a utilização de GC não atingiu o padrão (25% é o padrão). Supondo que o número atual de processadores P seja 5, de acordo com o cálculo é necessário um processador P dedicado para marcação, mas a utilização atingiu apenas 20%, os 5% restantes precisam ser compensados por um processador P em modo FractionalMode. O código de cálculo específico é:

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

• gcMarkWorkerIdleMode: Indica que o processador atual está executando tarefa de marcação por estar ocioso, e pode ser preemptado durante execução

A equipe do Go não deseja que o GC ocupe desempenho excessivo afetando a execução normal do programa do usuário. Através destes diferentes modos de execução de marcação, é possível completar o GC sem desperdiçar desempenho ou afetar o programa do usuário. Note-se que a unidade básica de distribuição de tarefas de marcação é o processador P, então o trabalho de marcação é executado concorrentemente, com múltiplas tarefas de marcação e programa do usuário executando concorrentemente, sem interferência mútua.

Assistência de Marcação

A goroutine G tem em runtime um campo gcAssistBytes, chamado de crédito de assistência GC. Durante estado de marcação GC, quando uma goroutine tenta alocar determinado tamanho de memória, é deduzido dela crédito igual ao tamanho da memória alocada. Se o crédito for negativo neste momento, a goroutine deve auxiliar completando quantidade determinada de tarefas de varredura GC para pagar o crédito; quando o crédito for positivo, a goroutine não precisa mais completar tarefas de assistência de marcação.

A função de dedução de crédito é runtime.deductAssistCredit, chamada antes da função runtime.mallocgc alocar memória.

func deductAssistCredit(size uintptr) *g {
    var assistG *g
    if gcBlackenEnabled != 0 {
       // Cobra esta alocação da G de usuário atual.
       assistG = getg()
       if assistG.m.curg != nil {
          assistG = assistG.m.curg
       }
       // Cobra a alocação contra a G. Vamos contabilizar
       // por fragmentação interna no final de mallocgc.
       assistG.gcAssistBytes -= int64(size)

       if assistG.gcAssistBytes < 0 {
          // Esta G está em dívida. Auxilia o GC para corrigir
          // isto antes de alocar. Isto deve acontecer
          // antes de desabilitar preempção.
          gcAssistAlloc(assistG)
       }
    }
    return assistG
}

Porém, quando a goroutine completa quantidade determinada de trabalho de varredura de assistência, paga quantidade correspondente de crédito à goroutine atual. A função que realmente executa assistência de marcação é runtime.gcDrainN.

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

Como a varredura é concorrente, apenas parte do trabalho registrado é da goroutine atual; o restante do trabalho é pago a outras goroutines de acordo com a ordem da fila de assistência. Se ainda houver sobra, é adicionado ao crédito global gcController.assistBytesPerWork.

func gcFlushBgCredit(scanWork int64) {
    // Se fila estiver vazia, adiciona diretamente ao crédito global
  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
    }
  }

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

Correspondentemente, quando é necessário pagar muito crédito (alocação de memória muito grande), também se pode usar crédito global para compensar parte da dívida própria:

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

    // Usa crédito global como garantia
  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
    }
  }
    ...
}

A assistência de marcação é um meio de balanceamento em condições de alta carga: a velocidade de alocação de memória do programa do usuário é muito maior que a velocidade de marcação, realizando trabalho de marcação proporcional à memória alocada.

Término de Marcação

Quando todos os objetos cinza alcançáveis são enegrecidos, transita-se do estado _GCmark para _GCmarktermination. Este processo é completado pela função runtime.gcMarkDone. No início, verifica se ainda há tarefas a executar:

top:

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

  gcMarkDoneFlushed = 0
  // Executa em lote todas operações de marcação interceptadas pela barreira de escrita
  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
  }

Quando não há mais tarefas globais ou locais a executar, chama-se runtime.stopTheWorldWithSema para STW, depois faz-se trabalho de encerramento:

// Desabilita assistências e workers em segundo plano. Devemos
// fazer isto antes de acordar assistências bloqueadas.
atomic.Store(&gcBlackenEnabled, 0)

// Notifica o limitador de CPU que assistências GC agora cessarão.
gcCPULimiter.startGCTransition(false, now)

// Acorda todas assistências bloqueadas. Estas executarão quando
// reiniciarmos o mundo.
gcWakeAllAssists()

// No modo STW, re-habilita goroutines de usuário. Estas serão
// enfileiradas para executar após reiniciarmos o mundo.
schedEnableUser(true)

// endCycle depende de todas estatísticas de cache gcWork serem liberadas.
// O algoritmo de término acima garantiu que até
// alocações desde a barreira irregular.
gcController.endCycle(now, int(gomaxprocs), work.userForced)

// Executa término de marcação. Isto reiniciará o mundo.
gcMarkTermination(stw)

Primeiro define-se runtime.BlackenEnabled como 0, indicando que o trabalho de marcação terminou, notifica-se o limitador que a assistência de marcação terminou, fecha-se a barreira de memória, acorda-se todas goroutines em dormência por assistência de marcação, depois re-acorda-se todas goroutines de usuário. Também coleta-se vários dados do trabalho de varredura desta rodada para ajustar o algoritmo de pacing para a próxima varredura. Após conclusão do trabalho de encerramento, chama-se a função runtime.gcSweep para limpar objetos lixo, finalmente chama-se runtime.startTheWorldWithSema para restaurar execução do programa.

Barreiras

A função da barreira de memória pode ser entendida como hook do comportamento de atribuição de objetos, executando operações designadas antes da atribuição. Este código de hook é normalmente inserido pelo compilador no código durante compilação. Como mencionado anteriormente, adição e remoção de referências de objetos em condições concorrentes durante marcação tricromática causam problemas. Como ambas são operações de escrita (remoção é atribuição de valor nulo), a barreira que as intercepta é chamada de barreira de escrita. Porém, mecanismo de barreira não é sem custo; interceptar operações de escrita de memória causa sobrecarga adicional, portanto o mecanismo de barreira só funciona no heap. Considerando complexidade de implementação e perda de desempenho, não se aplica a stack e registradores.

TIP

Para mais detalhes sobre aplicação de tecnologia de barreira no Go, visite Eliminate STW stack rescan para ler o artigo original em inglês; este artigo referencia muito deste conteúdo.

Barreira de Inserção

A barreira de inserção foi proposta por Dijkstra e satisfaz a forte invariância tricromática. Quando um objeto preto adiciona nova referência a objeto branco, a barreira de inserção intercepta esta operação, marcando o objeto branco como cinza, evitando assim que objeto preto referencie diretamente objeto branco, garantindo forte invariância tricromática, o que é bastante compreensível.

Como mencionado anteriormente, barreira de escrita não se aplica à stack. Se a relação de referência de objetos na stack mudar durante marcação concorrente, por exemplo, objeto preto na stack referencia objeto branco no heap, para garantir correção de objetos na stack, só é possível marcar todos objetos na stack como cinza novamente após término da marcação, depois varrer novamente. Isso significa que uma rodada de marcação precisa varrer o espaço da stack duas vezes, e a segunda varredura requer STW. Se existirem centenas ou milhares de stacks de goroutines no programa simultaneamente, o tempo de consumo deste processo de varredura não pode ser ignorado. De acordo com dados oficiais, o tempo de varredura novamente é de aproximadamente 10-100 milissegundos.

Vantagens: Não requer STW durante varredura

Desvantagens: Requer varredura二次 do espaço da stack para garantir correção, requer STW

Barreira de Remoção

A barreira de remoção foi proposta por Yuasa, também chamada de barreira baseada em snapshot inicial, que requer STW no início para registrar snapshot de objetos raiz, e marca todos objetos raiz como pretos e todos objetos filhos de primeiro nível como cinza, assim todos outros objetos filhos brancos estarão sob proteção de objetos cinza. A equipe do Go não aplicou diretamente a barreira de remoção, mas escolheu misturá-la com a barreira de inserção. Para facilitar compreensão subsequente, ainda vamos explicá-la aqui. A regra da barreira de remoção para garantir correção em condições concorrentes é: quando remove-se referência a objeto branco de objeto cinza ou branco, marca-se diretamente o objeto branco como cinza.

Divide-se em duas situações para interpretar:

• Remover referência de objeto cinza a objeto branco: Como não se sabe se objeto branco é referenciado por objeto preto a jusante,此举 pode cortar proteção de objeto cinza a objeto branco
• Remover referência de objeto branco a objeto branco: Como não se sabe se objeto branco é protegido por objeto cinza a montante ou referenciado por objeto preto a jusante,此举 também pode cortar proteção de objeto cinza a objeto branco

Independente da situação, a barreira de remoção marca o objeto branco referenciado como cinza, assim satisfazendo a fraca invariância tricromática. Esta é uma abordagem conservadora: como as situações a montante e jusante são desconhecidas, marcá-lo como cinza significa não mais considerá-lo objeto lixo. Mesmo que após remover referência o objeto se torne inalcançável (ou seja, objeto lixo), ainda será marcado como cinza e será liberado na próxima varredura, o que é melhor que erro de memória causado por limpeza errônea de objeto.

Vantagens: Como objetos da stack são todos pretos, não requer varredura二次 do espaço da stack

Desvantagens: Requer STW no início da varredura para snapshot de objetos raiz do espaço da stack

Barreira Mista

A versão go1.8 introduziu novo mecanismo de barreira: barreira mista, combinação de barreira de inserção e barreira de remoção, combinando vantagens de ambas:

• Barreira de inserção não requer STW no início para snapshot
• Barreira de remoção não requer STW para varredura二次 do espaço da stack

Abaixo está o pseudocódigo fornecido oficialmente:

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

Explicando alguns conceitos: slot é um ponteiro representando referência a outro objeto, *slot é objeto original, ptr é novo objeto, *slot=ptr é uma operação de atribuição, equivalente a modificar referência do objeto, atribuir valor nulo é remover referência, shade() significa marcar um objeto como cinza, shade(*slot) significa marcar objeto original como cinza, shade(ptr) significa marcar novo objeto como cinza. Abaixo está um exemplo: supondo que objeto 1 originalmente referencia objeto 2, depois o programa do usuário modifica a referência fazendo objeto 1 referenciar objeto 3. A barreira mista captura este comportamento, onde *slot representa objeto 2 e ptr representa objeto 1.

Oficialmente resumiram o efeito do pseudocódigo acima em uma frase:

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.

Traduzindo: quando a barreira mista intercepta operação de escrita, marca o objeto original como cinza; se a stack da goroutine atual ainda não foi varrida, marca também o novo objeto como cinza.

Ao iniciar trabalho de marcação, é necessário varrer espaço da stack para coletar objetos raiz, marcando-os diretamente como pretos. Durante este período, qualquer novo objeto criado também é marcado como preto, garantindo que todos objetos na stack sejam pretos. Assim, current stack is grey no pseudocódigo indica que a stack da goroutine atual ainda não foi varrida, então a stack da goroutine tem apenas dois estados: toda preta ou toda cinza. Durante transição de toda cinza para toda preta, é necessário pausar a goroutine atual, então ainda haverá STW局部 sob barreira mista. Quando a stack da goroutine está toda preta, certamente satisfaz a forte invariância tricromática, pois objetos pretos na stack após varredura só referenciam objetos cinza, não existindo situação de objeto preto referenciar diretamente objeto branco, então neste momento não é necessária barreira de inserção, correspondendo ao pseudocódigo:

if current stack is grey:
        shade(ptr)

Mas ainda é necessária barreira de remoção para satisfazer fraca invariância tricromática, ou seja:

shade(*slot)

Após conclusão da varredura, como objetos do espaço da stack já estão todos pretos, não é mais necessário varrer二次 o espaço da stack, economizando tempo de STW.

Até aqui, ou seja, a partir da versão go1.8, o Go estabeleceu basicamente o framework básico de coleta de lixo. Otimizações relacionadas à coleta de lixo em versões subsequentes são todas baseadas na barreira mista. Como a maioria dos STW já foi eliminada, a latência média de coleta de lixo já reduziu para nível de microssegundos.

Cache de Coloração

Nos mecanismos de barreira mencionados anteriormente, ao interceptar operação de escrita, marca-se imediatamente a cor do objeto. Após adoção da barreira mista, como é necessário marcar tanto objeto original quanto novo objeto, o trabalho dobra, e o código inserido pelo compilador também aumenta. Para otimizar, na versão go1.10, ao realizar coloração, a barreira de escrita não marca imediatamente a cor do objeto, mas armazena objeto original e novo objeto em um pool de cache, realizando marcação em lote após acumular certa quantidade, o que é mais eficiente.

A estrutura responsável pelo cache é runtime.wbBuf, que é na verdade um array de tamanho 512.

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

Cada P tem localmente tal cache:

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

Durante trabalho de marcação, se não há objetos cinza disponíveis na fila gcw, coloca-se objetos do cache na fila 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 {
        // Limpa buffer da barreira de escrita
        wbBufFlush()
        b = gcw.tryGet()
      }
    }
    if b == 0 {
      break
    }
    scanobject(b, gcw)
  }
}

Outra situação é: durante término de marcação, também verifica-se se há objetos cinza restantes no wbBuf local de cada P:

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

    wbBufFlush1(pp)

    pp.gcw.dispose()

  })
    ...
}

Recuperação

Na coleta de lixo, a parte mais importante é como identificar objetos lixo, ou seja, trabalho de varredura e marcação. Após conclusão do trabalho de marcação, o trabalho de回收 é relativamente menos complexo, bastando回收 e liberar objetos não marcados. Este código está principalmente no arquivo runtime/mgcsweep.go. De acordo com comentários no arquivo, o algoritmo de回收 no Go é dividido em dois tipos.

Recuperação de Objetos

O trabalho de回收 de objetos ocorre na fase de término de marcação, completado por runtime.sweepone para realizar trabalho de limpeza, processo assíncrono. Durante limpeza, tenta-se encontrar objetos não marcados na unidade de memória e回收. Se toda unidade de memória não estiver marcada, toda esta unidade será回收.

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

Para algoritmo de回收 de objetos,回收 toda unidade é mais difícil, então há segundo algoritmo de回收.

Recuperação de Unidades

O trabalho de回收 de unidades é executado antes da alocação de memória, completado pelo método runtime.mheap.reclaim, que busca no heap todas unidades de memória onde todos objetos não estão marcados, depois回收 toda unidade.

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 unidade de memória, há um campo sweepgen para indicar seu estado de回收:

• mspan.sweepgen == mheap.sweepgen - 2: Esta unidade de memória precisa ser回收
• mspan.sweepgen == mheap.sweepgen - 1: Esta unidade de memória está sendo回收
• mspan.sweepgen == mheap.sweepgen: Esta unidade de memória já foi回收 e pode ser usada normalmente
• mspan.sweepgen == mheap.sweepgen + 1: Unidade de memória está no cache e precisa ser回收
• mspan.sweepgen == mheap.sweepgen + 3: Unidade de memória já foi回收 mas ainda está no cache

mheap.sweepgen aumenta com cada rodada de GC, incrementando +2 a cada vez.