Perché bianco/grigio/nero in GC?

Question

Sto implementando la garbage collection mark-and-sweep in una semplice API di scripting su cui sto lavorando e sto leggendo su varie implementazioni della garbage collection. API come Lua usano il mark-and-sweep con liste bianche, grigie e nere.

Il problema è che non riesco a trovare spiegazioni sul perché ci siano tali elenchi e sul perché siano inseriti in questi colori specifici.

Nella mia attuale, banale implementazione, uso semplicemente stati "morti" o "vivi". Nella spazzata, gli oggetti morti vengono cancellati. Sto usando l'heap nativo quindi non sto facendo alcun movimento nel mio GC.

sto scrivendo in 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

Grey significa "dal vivo, ma non sottoposto a scansione": non tutti i discendenti di un blocco grigio sono stati contrassegnati come nero ancora. Il colore grigio è necessario in un incrementale garbage collector. Aiuta un GC mark-and-sweep a continuare quello che stava facendo la prossima volta che ha la possibilità di fare un po 'di marcatura.

Se il tuo GC non è incrementale, potrebbe sembrare che non hai necessariamente bisogno del colore grigio: puoi semplicemente recitare sempre su tutti i bambini di qualsiasi blocco live che incontri. Tuttavia, un altro problema più sottile è che questo ingenuo algoritmo ricorsivo non incrementale può traboccare lo stack. Un colore grigio aiuta anche a memorizzare le informazioni su cosa visitare successivamente nell'heap, invece che nello stack.

Anche se si utilizza il colore grigio per questo scopo, non impedisce di mantenere un buffer di blocchi che rimangono da visitare per l'efficienza. L'unica differenza con l'implementazione ricorsiva ingenua è che si interrompe l'aggiornamento del buffer quando è già pieno e si esegue la scansione lineare dell'heap per gli oggetti grigi se il buffer si svuota dopo essere stato pieno.

Answer 2

Prima di tutto, sono insiemi, non elenchi e ogni oggetto nell'heap è in qualsiasi momento esattamente in uno dei set.

In secondo luogo, in qualsiasi contrassegno & implementazione sweep vengono utilizzati, ma potrebbero essere implicita. Non si fornisce l'implementazione per Mark, ma in quella funzione si spostano gli oggetti nei propri set.

Ecco l'attuazione per la fase di marchio della mia garbage collector:

/* 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. */ 

Potremmo invece utilizzare le strutture di dati espliciti per i tre set. Ma per uno stop-the-world mark & sweep gc, questa implementazione è molto più efficiente.