Les ramasse-miettes sont censés être invisibles : si les programmeurs (ou même les utilisateurs) les remarquent, c'est que quelque chose ne va pas. En général, ces problèmes sont des problèmes de performance, mais il peut aussi y avoir des problèmes de correction. C'est pourquoi leur mise en œuvre est un peu effrayante.Dans le cadre de mes loisirs, je travaille sur une architecture de jeu d'instructions virtuelles, principalement pour mieux comprendre la nature de l'informatique et, éventuellement, les compromis dans la conception des langages de programmation.
Le projet a été bloqué pendant plusieurs mois parce que j'étais réticent à commencer à travailler sur un ramasse-miettes, que je considère comme nécessaire pour maintenir la sécurité de la mémoire.
J'étais un peu perplexe à ce sujet, mais je pense maintenant que c'est parce que les garbage collectors sont effrayants à utiliser. Non seulement ils sont censés être largement invisibles, mais ils doivent aussi calculer une propriété hautement non-locale : le fait qu'un objet soit vivant et ne puisse pas encore être désalloué dépend de l'état des pointeurs dans tous les autres objets du tas. Les garbage collectors de qualité industrielle sont également très complexes. Tout cela semblait donc très décourageant.
Cet article tente de documenter ce que j'ai fait pour m'en sortir. La plupart des idées ci-dessous visent à rendre l'opération du ramasse-miettes plus évidente.
Qu'est-ce qui peut être fait ?
Le choix du garbage collector est important. Un ramasse-miettes semi-spatial copiant, tel que l'algorithme de Cheney, semble être un excellent point de départ. (Voir C. J. Cheney, A nonrecursive list compacting algorithm, ou sa page Wikipedia, Cheney's algorithm). Un tel ramasse-miettes peut être très petit et très simple : sans compter le code d'identification des pointeurs d'objets racines et d'analyse des objets et des piles, une implémentation fonctionnelle du ramasse-miettes ne comporte que quelques dizaines de lignes de code (voire moins s'il existe déjà du code pour dupliquer les objets).
Le ramasse-miettes copie tous les objets d'une partie fromspace à une partie tospace du tas (d'où le nom de « semispace collector »). Cela a pour effet secondaire important de garantir que toutes les adresses d'objets changent au cours d'un cycle de garbage collection. Par conséquent, toute utilisation d'un pointeur d'objet qui a été oublié et qui n'a pas été traité pendant la collecte entraîne des problèmes très évidents (généralement un plantage, mais des données erronées peuvent également en résulter).
Avec un ramasse-miettes moins gourmand en mémoire qui essaie de travailler sur place, peut-être un qui ne déplace jamais aucun objet vivant, les pointeurs non traités peuvent passer inaperçus jusqu'à ce qu'un cas de test plus complexe se présente. Avec un ramasse-miettes qui copie, il est pratiquement nécessaire d'avoir le pointeur racine, la pile et le code de balayage des objets dès le départ.
Avec un tel semispace collector, la plage d'adresses du tas précédent (ce qui était auparavant le fromspace) peut être réservée au niveau du noyau et mappée avec le flag de protection PROT_NONE, de sorte qu'un déférencement accidentel par un pointeur obsolète qui n'a pas été mis à jour dans le cycle de garbage collection précédent est très susceptible d'échouer. Cela fonctionne même si les pointeurs sont stockés à l'extérieur (probablement par accident), dans des endroits qui ne sont pas censés être analysés par le ramasse-miettes.
Dans le cas d'interfaces avec un code C développé séparément, le problème des pointeurs non suivis peut être atténué par une conception soigneuse de l'interface. L'interface C contenue dans l'implémentation de référence du langage de programmation Lua utilise une pile virtuelle sur laquelle les pointeurs d'objets sont stockés (Section 4.1, The Stack, dans Roberto Ierusalimschy et al : Lua 5.4 Reference Manual (2023)). Les pointeurs d'objets ne sont jamais exposés. Les programmeurs C utilisent les indices des slots de la pile pour les manipuler. Comparez cela à l'approche de CPython, où les pointeurs d'objets réels sont exposés aux modules d'extension C. Avec un ramasse-miettes de copie, restreindre l'accès aux pointeurs d'objets à une petite partie de la machine virtuelle semble également raisonnable.
Mon ISA virtuel contient des entiers et des valeurs à virgule flottante de taille fixe, non alloués dans le tas, à la fois comme variables locales dans les procédures et comme champs dans les objets alloués dans le tas. L'assembleur effectue une vérification de type, de sorte qu'il sait déjà si un registre contient un pointeur d'objet au début de chaque instruction. (Une instruction ne peut utiliser un registre comme entrée que si tous les chemins d'exécution qui y mènent ont un type suffisamment compatible, mais le registre lui-même n'a pas un seul type fixe pendant l'exécution de la procédure).
Au moment de l'exécution, l'interprète de la machine virtuelle n'a pas besoin d'effectuer de vérification de type car, hormis les déplacements de registre à registre, des instructions distinctes sont utilisées pour les valeurs scalaires et les valeurs de pointeur. J'avais déjà un dérouleur de pile fonctionnel (pour la gestion des exceptions), mais je ne savais pas si l'encodage des informations de la trame de la pile aux instructions pertinentes (qui peuvent déclencher le garbage collection) sous la forme de cartes de pile fonctionnait. Bien qu'il n'y ait pas encore d'interface de débogage, j'ai ajouté une implémentation très basique de vidage de pile, qui montre le contenu de la pile et, pour les pointeurs d'objets identifiés à l'aide de cartes de pile, l'en-tête de l'objet à partir du tas. La suite de tests peut alors utiliser de simples expressions régulières pour vérifier que le dump contient des pointeurs aux endroits prévus pour un ensemble de cas de tests représentatifs.
En ce qui concerne les cartes de pointeurs pour les objets alloués au tas, il est possible de faire mieux : comparer les valeurs de pointeurs provenant de l'accès explicite à l'objet avec les résultats de la procédure d'analyse de l'objet qui utilise la même méthode d'identification des pointeurs que le ramasse-miettes. (Je ne vise explicitement pas un support général de la réflexion au moment de l'exécution, il s'agit donc d'une interface de test interne uniquement).
Cette approche basée sur des données redondantes (comparaison des résultats du ramasse-miettes avec les pointeurs connus pour être présents) permet de réaliser facilement des tests de bout en bout pour le code de balayage des objets. Des tests introspectifs similaires sont possibles pour les cartes de pile s'il existe un moyen de convertir les pointeurs d'objets en entiers, en perdant la propriété du pointeur. (Contre cela, il ne s'agit que de tests internes, car exposer l'adresse des objets de cette manière encourage la manipulation directe des objets, peut-être à partir d'un code C écrit séparément).
Le ramasse-miettes ne met plus à jour ces entiers, mais l'adresse de l'objet change. Le scénario de test sait quels registres contiennent des pointeurs et s'assure que le ramasse-miettes a mis à jour ces registres (en supposant que nous ayons un ramasse-miettes copiant).
En poursuivant le thème de l'utilisation de données redondantes pour le contrôle de cohérence, il est possible de garder le tas analysable à tout moment, ou au moins à des points sûrs : en partant de l'adresse basse du tas ou d'un segment, il est possible de trouver tous les objets précédemment alloués (qu'ils soient vivants ou non). Pour chaque objet, l'adresse de l'objet suivant peut être déterminée sur la base des informations d'en-tête trouvées dans l'objet actuel. Cela signifie que les en-têtes d'objets doivent exister, mais ils sont également utiles dans d'autres contextes (par exemple pour la mise en œuvre de la répartition dynamique, ou pour les downcasts vérifiés des pointeurs de classe de base vers les pointeurs de classe dérivée).
La traversée du heap peut être utilisée pour vérifier à certains moments (par exemple, juste après le garbage collection) que le heap est cohérent, sans dépendre d'une nouvelle traversée depuis les racines. Une première phase peut construire un tableau de bits contenant des bits de set pour toutes les adresses de départ des objets du tas, et une deuxième phase de la procédure de vérification peut alors vérifier que chaque pointeur identifié est soit nul, soit pointe vers le départ d'un objet du tas précédemment identifié.
Actuellement, cette procédure de vérification est très similaire à celle du ramasse-miettes de copie de style Cheney (sans les parties de copie d'objets), mais elle peut être utilisée sans modification avec n'importe quel autre ramasse-miettes qui maintient un tas analysable, même si ce n'est qu'artificiellement (en insérant des objets factices pour combler les lacunes du tas).
Une autre chose m'a permis d'obtenir une meilleure couverture avec les tests limités que j'ai jusqu'à présent : le déclenchement d'une garbage collection à chaque allocation, ou du moins beaucoup plus fréquemment que d'habitude. (Je pense que j'ai vu cela en premier dans Hotspot, qui a plusieurs flags GCALot dans les builds de débogage). Avec un tel mode d'exécution, les tests exercent le code de garbage collection beaucoup plus lourdement.
Cela en valait-il la peine ?
Jusqu'à présent, le ramasse-miettes semble bien fonctionner, ce qui n'est pas surprenant étant donné qu'il est si simple. Les problèmes spécifiques au ramasse-miettes que j'ai rencontrés sont liés à l'heuristique de dimensionnement du tas, et à la détermination de la limite du tas à partir de laquelle la prochaine garbage collection commence. Les calculs d'adresses pour cela (et les régions de mémoire à démapper, étant donné qu'elles ne seront pas nécessaires) se sont avérés assez délicats. Il y a eu quelques problèmes d'intégration au début avec les cartes de pile parce que l'assembleur et l'implémentation de la machine virtuelle n'étaient pas tout à fait en accord sur leur encodage, mais c'était déjà visible dans les dumps de débogage de pile que j'ai ajoutés pour les tests.
Source : "Garbage collectors are scary" (Florian Weimer)
Et vous ?
Qu'en pensez-vous ?Voir aussi :
Un coprocesseur pour accélérer les ramasse-miettes, on pourrait gagner un facteur 4 en temps d'exécution sur les opérations de gestion de la mémoire Le ramasse-miettes (garbage collector) pour les programmeurs systèmes, un tutoriel de Matt Kline