Comment mettre en œuvre un ramasse-miettes indépendant de la plate-forme ?

Question

En gros, je suis intéressé par l'écriture d'un indépendant de la plate-forme le collecteur d'ordures dans C probablement en utilisant l'algorithme mark-and-sweep ou l'une de ses variantes courantes. Idéalement, l'interface fonctionnerait de la manière suivante :

(1) gc_alloc() alloue la mémoire

(2) gc_realloc() réaffecte la mémoire

(3) gc_run() exécute le ramasseur de déchets.

J'ai déjà jeté un coup d'œil à la libgc mais elle n'est pas indépendante de la plate-forme ; elle a juste été portée sur de nombreux systèmes différents. J'aimerais implémenter un garbage collector qui ne contienne aucun code dépendant du système. La vitesse n'est pas un énorme question.

Des suggestions ?

Answer 1

Malheureusement, il n'est pas vraiment possible de faire un vraiment Un collecteur de déchets indépendant de la plateforme en C. Une lecture stricte de la norme C permet à n'importe quel type (à l'exception de unsigned char ) pour avoir des bits pièges - des bits qui, lorsqu'ils ont une mauvaise valeur, entraînent le signalement d'une exception par le système (c'est-à-dire un comportement non défini). Lorsque vous recherchez des pointeurs dans des blocs alloués, vous n'avez aucun moyen de déterminer si un bloc de mémoire particulier contient une valeur de pointeur légale, ou s'il sera piégé dès que vous essaierez de regarder la valeur qu'il contient.

Examiner les pointeurs comme des ints n'aide pas non plus - aucun type int n'est tenu d'avoir une représentation compatible avec un pointeur. intptr_t n'est disponible que sur des compilateurs très récents, et je ne crois pas que son représentation doit également être compatible. Et les ints peuvent aussi avoir des bits pièges.

Vous ne connaissez pas non plus les exigences d'alignement des pointeurs. Sur une plate-forme où les pointeurs n'ont pas d'exigences d'alignement (c'est-à-dire qu'ils peuvent commencer à n'importe quel octet), cela signifie que vous devez vous arrêter à chaque octet, memcpy à un type de pointeur approprié, et examiner le résultat. Oh, et différents types de pointeurs peuvent également avoir des représentations différentes, ce qui est également inévitable.

Mais le plus gros problème est de trouver l'ensemble Root. Bohem GC et les autres ont tendance à scanner la pile, ainsi que les données statiques, à la recherche de pointeurs qui devraient aller dans l'ensemble Root. C'est impossible sans connaître la disposition de la mémoire du système d'exploitation. . Vous devrez donc demander à l'utilisateur de marquer explicitement les membres de l'ensemble Root, ce qui va à l'encontre de l'utilité du ramasse-miettes.

Donc, en bref, vous ne pouvez pas faire un GC en vraiment portable C. En principe, vous pouvez le faire si vous faites quelques hypothèses :

• Supposons que l'ensemble Root vous soit explicitement donné par l'utilisateur.
• Supposons qu'il n'y ait pas de bits pièges dans les représentations des pointeurs ou des int.
• Supposons que intptr_t est disponible ou supposer que tous les void * sont strictement ordonnés (c'est-à-dire que < y > fonctionne raisonnablement avec des pointeurs provenant de différents malloc ations)
• Supposez que tous les types de pointeurs de données ont une représentation compatible avec void * .
• Facultatif, mais donne un gros coup de pouce à la vitesse : coder en dur l'alignement des pointeurs (ceci est loin d'être universel, et devra être spécifique au compilateur et à la plate-forme). memcpy Il permet également de réduire le nombre de pointeurs potentiels à examiner.

Si vous faites ces hypothèses, vous devriez être en mesure d'établir un répartiteur mark-sweep conservateur. Utilisez un arbre binaire pour conserver les informations sur l'emplacement des allocations, et parcourez chaque emplacement possible de pointeur aligné dans les blocs alloués à la recherche de pointeurs. Cependant, la nécessité de fournir explicitement l'ensemble Root rendra tout cela inutile - ce sera malloc y free tout recommence, sauf que pour un certain ensemble mal défini d'objets, vous pouvez l'ignorer. Ce n'est pas exactement ce que la GC est censée fournir, mais je suppose qu'elle pourrait avoir sa place, par exemple en tant que partie d'une machine virtuelle (dans ce cas, l'ensemble Root serait dérivé des informations disponibles à la machine virtuelle).

Notez que tout ceci ne s'applique qu'aux conservateur Les GC - c'est-à-dire ceux qui travaillent à l'aveugle, en recherchant des pointeurs dans les données sans savoir où elles peuvent se trouver. Si vous travaillez sur une VM, c'est beaucoup plus facile - vous pouvez construire un type de données unifié pour toutes les allocations par la VM qui liste explicitement où les pointeurs peuvent être trouvés. Avec cela plus un ensemble de racines explicites, vous pouvez construire une GC non-conservative ; cela devrait être suffisant pour construire une VM ou un interpréteur.

Answer 2

Pour un algorithme de marquage et de balayage, tout ce que vous devez faire est de calculer quels objets sont accessibles à partir de l'ensemble Root, non ? (Cela fait un moment que je n'ai pas creusé cette question...)

Cela pourrait être géré par un graphe d'objets séparé pour les objets gérés par GC, et "tout" ce que vous auriez à faire serait d'ajouter des fonctions pour gérer correctement ce graphe chaque fois que vous allouez ou modifiez des objets gérés. Si vous ajoutez également le comptage des références pour les objets gérés, il sera plus facile de calculer lesquels sont accessibles directement à partir des références de la pile.

Il devrait probablement être possible de l'écrire de manière relativement indépendante de la plate-forme, bien que l'on puisse discuter de la question de savoir s'il s'agit d'un véritable ramasse-miettes.

Pseudocode simple pour montrer ce que j'entends par comptage de références et gestion de graphe :

some_object * pObject = gc_alloc(sizeof(some_object));
some_container * pContainer = gc_alloc(sizeof(some_container));

pContainer->pObject = pObject;
/* let the GC know that pContainer has a reference to pObject */
gc_object_reference(pContainer, pObject);

/* a new block of some kind */
{
    /* let the GC know we have a new reference for pObject */
    some_object * pReference = gc_reference(pObject); 

    /* do stuff */
    ...

    /* let the GC know that this reference is no longer used */
    gc_left_scope(pReference);
}

gc_left_scope(pObject);
gc_run(); /* should not be able to recycle anything, since there still is a live
           * reference to pContainer, and that has a reference to pObject
           */