El algoritmo tricolor y la barrera de escritura en Go

El Garbage Collector (GC) de Go es un recolector de basura concurrente que utiliza un algoritmo de marcado y barrido tricolor (tricolor mark-and-sweep). A diferencia de otros lenguajes que detienen completamente la ejecución de la aplicación para limpiar la memoria, Go minimiza las pausas Stop-The-World (STW) permitiendo que el “mutador” (tu código) siga ejecutándose mientras el recolector identifica qué memoria está en uso.

Para lograr esta concurrencia sin corromper la memoria, el GC clasifica los objetos en el heap en tres estados lógicos:
1. Blanco (White): Candidatos para ser liberados. Son objetos que el GC aún no ha visitado o que no han sido alcanzados desde las raíces.
2. Gris (Grey): Objetos alcanzables, pero cuyos hijos (punteros a otros objetos) aún no han sido escaneados por el GC.
3. Negro (Black): Objetos alcanzables que ya han sido completamente escaneados; el GC garantiza que un objeto negro no tiene punteros a objetos blancos.

Este sistema funciona mediante un proceso de propagación: el GC parte de las raíces (variables locales en el stack, variables globales, registros) y marca todo lo alcanzable. El diseño de este algoritmo permite que el proceso de marcado sea paralelo a la ejecución del programa. Sin embargo, esto introduce un riesgo: si tu código cambia un puntero durante el marcado (por ejemplo, moviendo un objeto blanco de un objeto gris a uno negro), el GC podría perder la referencia y liberar memoria que aún está en uso. Para evitar esto, Go implementa una barrera de escritura (write barrier): un fragmento de código generado por el compilador que se ejecuta cada vez que se modifica un puntero en el heap, asegurando que cualquier objeto movido durante el ciclo de marcado se marque como gris y no se pierda.

Este mecanismo es fundamental cuando desarrollas sistemas de alta disponibilidad y baja latencia. Si no existiera este algoritmo concurrente, las pausas de limpieza en aplicaciones con heaps de cientos de gigabytes harían que el servicio fuera impracticable. Si el algoritmo fallara o no se implementara la barrera de escritura correctamente, el resultado sería una corrupción de memoria catastrófica o un panic por acceso a memoria liberada.

package main

import (
	"fmt"
)

// Color representa el estado tricolor de un objeto en el heap.
type Color int

const (
	White Color = iota // Candidato a ser liberado
	Grey               // Alcanzable, pero hijos no escaneados
	Black              // Alcanzable y hijos escaneados
)

func (c Color) String() string {
	return [...]string{"White", "Grey", "Black"}[c]
}

// Object simula una estructura de datos en el heap.
type Object struct {
	ID       string
	Color    Color
	pointers []*Object
}

// GCSimulator simula el comportamiento del recolector de Go.
type GCSimulator struct {
	heap  []*Object
	greyStack []*Object // La lista de trabajo del GC
}

// NewGCSimulator inicializa el simulador con un conjunto de objetos.
func NewGCSimulator(objects []*Object) *GCSimulator {
	return &GCSimulator{
		heap:      objects,
		greyStack: make([]*Object, 0),
	}
}

// AddRoot simula el inicio del proceso de marcado desde las raíces (stack/globals).
func (g *GCSimulator) AddRoot(obj *Object) {
	if obj.Color == White {
		obj.Color = Grey
		g.greyStack = append(g.greyStack, obj)
	}
}

// MarkPhase simula la fase de marcado tricolor.
func (g *GCSimulator) MarkPhase() {
	for len(g.greyStack) > 0 {
		// Sacamos un objeto gris de la lista de trabajo.
		curr := g.greyStack[len(g.greyStack)-1]
		g.greyStack = g.greyStack[:len(g.greyStack)-1]

		// Escaneamos sus punteros (hijos).
		for _, child := range curr.pointers {
			if child.Color == White {
				child.Color = Grey
				g.greyStack = append(g.greyStack, child)
			}
		}
		// Una vez escaneados sus hijos, el objeto pasa a ser negro.
		curr.Color = Black
	}
}

// SweepPhase simula la fase de barrido de memoria.
func (g *GCSimulator) SweepPhase() int {
	freed := 0
	for _, obj := range g.heap {
		if obj.Color == White {
			// En un runtime real, aquí se liberaría la memoria.
			freed++
		} else {
			// Resetear color para el siguiente ciclo de GC.
			// En la realidad, los objetos negros vuelven a ser blancos en el siguiente ciclo.
			if obj.Color == Black {
				obj.Color = White
			}
		}
	}
	return freed
}

func main() {
	// Creamos un grafo de objetos en el heap.
	// Root -> A -> B -> C
	// Root -> D
	objC := &Object{ID: "C", Color: White}
	objB := &Object{ID: "B", Color: White, pointers: []*Object{objC}}
	objA := &Object{ID: "A", Color: White, pointers: []*Object{objB}}
	objD := &Object{ID: "D", Color: White}
	
	// El objeto E es inalcanzable (Garbage).
	objE := &Object{ID: "E", Color: White}

	heap := []*Object{objA, objB, objC, objD, objE}
	sim := NewGCSimulator(heap)

	fmt.Println("--- Inicio del Ciclo de GC ---")
	
	// 1. Fase de Raíces: El stack contiene punteros a A y D.
	sim.AddRoot(objA)
	sim.AddRoot(objD)
	fmt.Println("Raíces marcadas: A y D")

	// 2. Fase de Marcado (Concurrent Mark)
	sim.MarkPhase()

	fmt.Println("\nEstado de los objetos tras el marcado:")
	for _, obj := range heap {
		fmt.Printf("Objeto %s: %s\n", obj.ID, obj.Color)
	}

	// 3. Fase de Barrido (Sweep)
	freed := sim.SweepPhase()
	fmt.Printf("\nCiclo completado. Objetos liberados: %d (Esperado: 1, el objeto E)\n", freed)
}

Desglose del funcionamiento

En el simulador anterior, podemos observar la transición de estados que el runtime de Go gestiona internamente:

1. Inicialización y Raíces: Al llamar a AddRoot(objA), simulamos que el GC identifica un puntero en el stack de una goroutine. El objeto A pasa de White a Grey. En un sistema real, esto es lo que ocurre cuando el GC escanea los registros de la CPU y el stack de las goroutines.
2. Propagación del color gris: En MarkPhase, el bucle procesa el greyStack. Cuando procesamos objA (que es gris), iteramos sobre sus pointers. El objeto objB es blanco, así que lo marcamos como gris y lo añadimos al greyStack. Una vez que terminamos con los hijos de objA, este cambia a Black.
3. El invariante de la barrera de escritura: Si mientras MarkPhase se estuviera ejecutando, tú ejecutaras objA.pointers[0] = objE, el objeto objE (que es blanco y está “lejos” en el grafo) debe ser marcado inmediatamente como gris. Si no se hiciera esto (la barrera de escritura), el GC terminaría de procesar objA y, al no haber rastreado a objE a través de objA, lo consideraría inalcanzable y lo borraría.
4. Barrido final: El método SweepPhase simplemente recorre el heap. Cualquier objeto que permanezca en White tras la fase de marcado es, por definición, inalcanzable desde las raíces. En nuestro ejemplo, objE se mantiene White porque ningún objeto alcanzable apunta a él, resultando en su liberación.

El error frecuente

Un error conceptual común es pensar que, como el GC de Go es concurrente, el programador no necesita preocuparse por la consistencia de los punteros. Esto no es cierto cuando se utiliza el paquete unsafe.

Si utilizas unsafe.Pointer para manipular direcciones de memoria de forma manual, puedes saltarte las barreras de escritura que el compilador inserta automáticamente. Por ejemplo, si modificas un puntero en una estructura de datos de forma que el runtime no pueda interceptar la operación, puedes crear un escenario donde un objeto Black apunte a un objeto White sin que el GC se entere.

// ESCENARIO DE ERROR (Conceptual)
// 1. El GC marca ObjetoA como Negro (Black).
// 2. Tu código usa unsafe para mover el puntero de un ObjetoC (White) 
//    dentro de ObjetoA.
// 3. Como no hubo una operación de asignación estándar, 
//    no se disparó la Write Barrier.
// 4. El GC termina el escaneo de ObjetoA, ve que no hay más grises,
//    y procede a limpiar todo lo que sea Blanco.
// 5. ObjetoC es eliminado, dejando a ObjetoA con un puntero corrupto (dangling pointer).

Este tipo de errores son extremadamente difíciles de depurar porque no causan un error inmediato, sino una corrupción de memoria silenciosa que suele manifestarse mucho después, como un segmentation fault aleatorio en una parte del código que parece no tener relación con el error original.

N° 171