¿Por qué blanco/gris/negro en GC?

Question

Estoy implementando la recolección de elementos no utilizados en un lenguaje de scripting simple API en el que estoy trabajando y he estado leyendo sobre diversas implementaciones de la recolección de elementos no utilizados. Las API como Lua utilizan marcas y barridos con listas blancas, grises y negras.

El problema es que parece que no puedo encontrar una explicación de por qué hay tales listas y por qué se ponen en estos colores específicos.

En mi implementación actual y trivial, simplemente uso estados "muertos" o "vivos". En el barrido, los objetos muertos se eliminan. Estoy usando el montón nativo, así que no estoy moviéndome en mi GC.

lo estoy escribiendo en C.

// Performs a full garbage collection 
void GorCollect(GorContext *ctx) 
{ 
    Value *v, *end; 
    Collectable *c, *n; 

    // mark stack references 
    end = ctx->stack + ctx->stackTop + 1; 
    v = ctx->stack; 
    while(v != end) 
    { 
     if (gvisgc(v) && v->v.gc) // mark if a collectable obj 
      Mark(v->v.gc); 
     v = v++; 
    } 

    // mark global references 
    if (ctx->global) 
     Mark((Collectable *)ctx->global); // ctx->global is a collectable obj 

    // perform sweep 
    c = ctx->gchead; // full list of collectable objs 
    ctx->gchead = 0; 
    while(c) { 
     n = c->next;  
     // destroy unmarked collectable 
     if (!c->marked) 
      FreeCollectable(ctx, c); 

     // rebuild gc list (singly-linked) 
     else 
     { 
      c->marked = 0; 
      if (!ctx->gchead) 
       c->next = 0; 
      else 
       c->next = ctx->gchead; 
      ctx->gchead = c; 
     } 
     c = n; 
    } 
} 

Answer 1

gris significa "vivo pero no explorado": no todos los descendientes de un bloque gris se han marcado como negro todavía. El color gris es necesario en un incremental basurero-colector. Ayuda a un GC de marcaje y barrido a continuar con lo que estaba haciendo la próxima vez que tenga la oportunidad de marcar un poco.

Si su GC no es incremental, puede parecer que no necesita necesariamente el color gris: simplemente siempre puede recurse en todos los elementos secundarios de cualquier bloque vivo que encuentre. Sin embargo, otro problema más sutil es que este ingenuo algoritmo recursivo no incremental puede desbordar la pila. Un color gris también ayuda al permitir almacenar información sobre qué visitar a continuación en el montón, en lugar de la pila.

Aunque utilice el color gris para este propósito, no le impide guardar un búfer de bloques que aún deben visitarse para mayor eficiencia. La única diferencia con la implementación recursiva ingenua es que deja de actualizar el búfer cuando ya está lleno, y escanea el montón de forma lineal para objetos grises si el búfer se vacía después de estar lleno.

Answer 2

En primer lugar, son conjuntos, no listas y cada objeto en el montón es en cualquier momento en exactamente uno de los conjuntos.

En segundo lugar, en cualquier marca & implementación de barrido que se están utilizando, pero pueden ser implícita. No proporciona la implementación para Mark, pero en esa función mueve sus objetos en sus conjuntos.

Aquí es la implementación de la fase de la marca de mi recolector de basura:

/* Initally, the white set contains all objects, the black and 
    grey sets are empty. */ 
stack *st = m->mark_stack; 
/* First all roots are added to the gray set. */ 
for (size_t i = 0; i < m->roots->used; i++) { 
    ptr p = m->roots->array[i]; 
    if (p != 0) { 
     /* Mark the root and move it to the gray set. */ 
     AT(p) |= 1; 
     st_push(st, p); 
    } 
} 
while (st->used) { 
    /* Think of popping the object from the mark stack as moving 
     it from the gray to the black set. */ 
    ptr p = st_pop(st); 
    P_FOR_EACH_CHILD(p, { 
     if (!GET_MARK(p_child)) { 
      /* Then mark each non-black child and move it to the 
       gray set. */ 
      AT(p_child) |= 1; 
      st_push(st, p_child); 
     } 
    }); 
} 
/* When control has reached this point, the gray set is empty and 
    the whole heap has been divided into black (marked) and white 
    (condemned) objects. */ 

Podríamos utilizar en su lugar las estructuras de datos explícitos para las tres series. Pero para una marca stop-the-world & sweep gc, esta implementación es mucho más eficiente.