Chaque runtime de langage doit répondre à une question : qui nettoie la mémoire ? Dans FLIN, la réponse est un ramasse-miettes mark-and-sweep écrit en 731 lignes de Rust.
La Session 011, le lendemain de la construction du coeur de la VM, a été entièrement dédiée à la mémoire. La VM pouvait exécuter de l'arithmétique, pousser et dépiler des valeurs, appeler des fonctions et sauter. Mais chaque chaîne créée, chaque liste construite, chaque entité instanciée -- tout cela fuyait. Les objets allaient sur le tas et n'en ressortaient jamais. Exécutez une boucle qui crée mille chaînes, et vous avez mille chaînes qui consomment de la mémoire pour toujours.
Cela devait cesser. Cet article couvre comment nous avons conçu le tas, implémenté la collecte mark-and-sweep, géré les cas limites délicats (références transitives, fermetures, cycles) et vérifié le tout avec 22 tests ciblés.
L'architecture du tas
Le tas est un vecteur plat d'objets optionnels :
rustpub struct Heap {
objects: Vec<Option<HeapObject>>,
free_list: Vec<usize>,
bytes_allocated: usize,
gc_threshold: usize,
}Chaque emplacement dans objects est soit Some(HeapObject) soit None (libéré). La free_list suit quels emplacements sont disponibles pour réutilisation. Quand la VM alloue un nouvel objet, elle vérifie d'abord la liste libre. S'il y a un emplacement libre, elle le réutilise. Sinon, elle pousse une nouvelle entrée sur le vecteur.
Cette conception évite le surcoût d'un allocateur traditionnel (malloc/free) pour chaque objet. Au lieu de cela, le tas grandit de manière monotone, et les emplacements libérés sont recyclés. Le compromis est que le vecteur du tas peut contenir des trous (emplacements libérés entre des objets vivants), mais c'est acceptable parce que nous n'itérons jamais le tas dans les chemins chauds -- nous accédons aux objets uniquement par leur ObjectId, qui est un index dans le vecteur.
Le type ObjectId est un wrapper newtype autour de usize :
rust#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub struct ObjectId(pub usize);Quand la VM pousse Value::Object(ObjectId(42)) sur la pile, cela signifie « l'objet à l'index 42 du tas ». Le déréférencement est une seule opération d'index de tableau -- O(1) sans poursuite de pointeur, sans indirection, sans miss de cache au-delà de l'accès initial au tableau.
Allocation
L'allocation d'un objet suit un chemin simple :
rustimpl Heap {
pub fn alloc(&mut self, data: ObjectData) -> ObjectId {
let size = data.estimated_size();
let header = ObjectHeader {
type_tag: data.type_tag(),
marked: false,
size: size as u32,
};
let object = HeapObject { header, data };
let id = if let Some(slot) = self.free_list.pop() {
self.objects[slot] = Some(object);
ObjectId(slot)
} else {
let slot = self.objects.len();
self.objects.push(Some(object));
ObjectId(slot)
};
self.bytes_allocated += size;
id
}
}La liste libre est une pile LIFO. Dépiler depuis la fin est O(1). Cela signifie que les emplacements récemment libérés sont réutilisés en premier, ce qui a un avantage subtil pour la localité de cache : les objets récemment libérés ont été récemment accédés, donc leur région mémoire est probablement encore dans le cache du CPU.
Des helpers d'allocation typés enveloppent le alloc générique :
rustpub fn alloc_string(&mut self, s: String) -> ObjectId {
self.alloc(ObjectData::String(s))
}
pub fn alloc_list(&mut self, items: Vec<Value>) -> ObjectId {
self.alloc(ObjectData::List(items))
}
pub fn alloc_map(&mut self, entries: HashMap<String, Value>) -> ObjectId {
self.alloc(ObjectData::Map(entries))
}Chacun retourne un ObjectId que la VM stocke sur la pile ou dans une variable. L'appelant ne voit jamais un pointeur brut. Le système de propriété de Rust garantit que chaque ObjectId réfère à un emplacement valide dans le vecteur du tas (ou un emplacement qui a été libéré, que le GC gère).
Le ramasse-miettes
FLIN utilise mark-and-sweep, l'algorithme de GC correct le plus simple. Il fonctionne en deux phases :
- Mark : en partant d'un ensemble de racines (valeurs définitivement vivantes), traverser tous les objets atteignables et définir leur bit
marked. - Sweep : parcourir l'ensemble du tas. Tout objet non marqué est un déchet -- libérer son emplacement et l'ajouter à la liste libre.
Racines
L'ensemble des racines est tout ce que le programme peut actuellement atteindre :
- Chaque valeur sur la pile d'opérandes
- Chaque variable globale
- Chaque variable locale dans chaque cadre d'appel actif
Si une valeur est sur la pile, elle est vivante. Si une valeur est dans une globale, elle est vivante. Si une valeur est dans une variable locale d'une fonction en cours d'exécution (ou en attente du retour d'un appelé), elle est vivante. Tout le reste est un déchet.
Marquage
rustfn mark_roots(&mut self, stack: &[Value], globals: &HashMap<String, Value>,
frames: &[CallFrame]) {
// Marquer depuis la pile
for value in stack {
if let Value::Object(id) = value {
self.mark_object(*id);
}
}
// Marquer depuis les globales
for value in globals.values() {
if let Value::Object(id) = value {
self.mark_object(*id);
}
}
// Marquer depuis les locales des cadres d'appel
for frame in frames {
for value in &frame.locals {
if let Value::Object(id) = value {
self.mark_object(*id);
}
}
}
}
fn mark_object(&mut self, id: ObjectId) {
if let Some(ref mut obj) = self.objects[id.0] {
if obj.header.marked {
return; // Déjà visité -- protection contre les cycles
}
obj.header.marked = true;
// Marquer récursivement les objets référencés
match &obj.data {
ObjectData::List(items) => {
let items_clone: Vec<Value> = items.clone();
for item in &items_clone {
if let Value::Object(child_id) = item {
self.mark_object(*child_id);
}
}
}
ObjectData::Map(entries) => {
let values_clone: Vec<Value> = entries.values().cloned().collect();
for val in &values_clone {
if let Value::Object(child_id) = val {
self.mark_object(*child_id);
}
}
}
ObjectData::Closure(closure) => {
for captured in &closure.captures.clone() {
if let Value::Object(child_id) = captured {
self.mark_object(*child_id);
}
}
}
ObjectData::Entity(entity) => {
let fields_clone: Vec<Value> = entity.fields.values().cloned().collect();
for val in &fields_clone {
if let Value::Object(child_id) = val {
self.mark_object(*child_id);
}
}
}
_ => {} // String, Function, NativeFunction, Iterator -- pas d'objets enfants
}
}
}La fonction mark_object est récursive. Quand elle marque une liste, elle marque aussi chaque objet dans cette liste. Quand elle marque une map, elle marque chaque valeur objet dans cette map. Quand elle marque une fermeture, elle marque chaque valeur capturée. Quand elle marque une entité, elle marque chaque valeur de champ. Cela garantit que la fermeture transitive complète des objets atteignables est marquée.
La vérification if obj.header.marked { return; } en haut est critique pour la gestion des cycles. Si l'objet A contient une référence à l'objet B, et l'objet B contient une référence à l'objet A, l'approche récursive naïve bouclerait indéfiniment. Le bit marqué casse le cycle : la deuxième visite à un objet déjà marqué retourne immédiatement.
Remarquez le clonage. Nous clonons les éléments de liste, les valeurs de map, les captures de fermetures et les champs d'entités avant d'itérer. C'est parce que mark_object prend &mut self (elle doit muter le bit marked), mais itérer sur les enfants d'un objet nécessite un accès &self pour lire les données de l'objet. Le borrow checker de Rust interdit de détenir simultanément &self et &mut self. Le pattern clone-d'abord résout ce conflit au prix d'une allocation temporaire pendant le GC.
C'est l'un des endroits où le modèle de propriété de Rust ajoute de la friction à l'implémentation du GC. En C, on ferait juste un cast pour enlever le const. En Rust, on clone. Le clone est correct par construction -- pas de course aux données, pas d'utilisation après libération -- mais il n'est pas gratuit. Pour un GC de production, nous optimiserions cela avec du code unsafe ou une structure de données différente. Pour l'instant, la correction compte plus que la vitesse.
Balayage
rustfn sweep(&mut self) {
for i in 0..self.objects.len() {
if let Some(ref mut obj) = self.objects[i] {
if obj.header.marked {
obj.header.marked = false; // Réinitialiser pour la prochaine collecte
} else {
// Déchet -- récupérer
self.bytes_allocated -= obj.header.size as usize;
self.objects[i] = None;
self.free_list.push(i);
}
}
}
}Le balayage parcourt chaque emplacement du tas. Les objets marqués survivent -- leur bit de marquage est effacé pour le prochain cycle de collecte. Les objets non marqués sont libérés : leur emplacement est mis à None, leur taille est soustraite de bytes_allocated, et leur index est poussé sur la liste libre.
Après le balayage, chaque objet vivant a marked: false, et la liste libre contient les indices de tous les emplacements libérés. La prochaine allocation réutilisera ces emplacements avant de faire grandir le tas.
Quand collecter
Le GC ne s'exécute pas à chaque allocation. Ce serait catastrophiquement lent. Au lieu de cela, il s'exécute quand bytes_allocated dépasse gc_threshold :
rustpub fn should_collect(&self) -> bool {
self.bytes_allocated >= self.gc_threshold
}Le seuil par défaut est 1 Mo. Après chaque collecte, le seuil est défini à deux fois le bytes_allocated courant. Cette stratégie adaptative signifie que les programmes avec de petits tas collectent rarement (le seuil grandit lentement), tandis que les programmes avec de grands tas collectent proportionnellement (le seuil grandit avec le tas).
La VM vérifie should_collect() après chaque allocation et déclenche une collecte si nécessaire. Cela garantit que le tas ne grandit jamais de manière non bornée, tout en assurant que le GC ne s'exécute pas plus souvent que nécessaire.
Interning de chaînes
Les chaînes méritent une attention spéciale parce qu'elles sont l'objet alloué sur le tas le plus courant dans la plupart des programmes. Noms de variables, noms de champs d'entités, noms de types, texte orienté utilisateur -- tous sont des chaînes.
Le pool de constantes de FLIN fournit déjà une forme d'interning de chaînes : les littéraux de chaîne qui apparaissent dans le code source sont stockés une fois dans le pool de constantes et référencés par index. Quand la VM charge une chaîne constante, elle n'alloue pas un nouvel objet sur le tas -- elle récupère la chaîne déjà allouée du pool.
Cela signifie que l'expression name = "Thales" n'alloue pas une nouvelle chaîne à chaque exécution. La chaîne "Thales" existe une fois dans le pool de constantes, et la variable globale name contient un Value::Object(ObjectId) pointant vers elle.
Les opérations de chaîne à l'exécution (concat, replace, upper, lower) créent de nouvelles chaînes sur le tas, et celles-ci sont sujettes au ramasse-miettes. Mais les chaînes du pool de constantes sont des racines -- elles sont toujours atteignables et jamais collectées.
Cycle de vie des entités
Les entités sont le type de données principal de FLIN -- elles représentent des objets du domaine avec des champs, des versions et des horodatages :
rustpub struct EntityInstance {
pub entity_type: String,
pub id: u64,
pub fields: HashMap<String, Value>,
pub version: u64,
pub created_at: DateTime<Utc>,
pub updated_at: DateTime<Utc>,
}Les champs d'une entité peuvent contenir n'importe quel Value, y compris des références Object vers d'autres objets du tas. Quand le GC marque une entité, il doit aussi marquer chaque objet dans ses champs. Si une entité a un champ address dont la valeur est une chaîne, cette chaîne doit survivre à la collecte aussi longtemps que l'entité est vivante.
Ce marquage transitif est ce qui rend le GC correct. Sans lui, l'entité survivrait mais son champ chaîne serait collecté, laissant un ObjectId pendant qui pointe vers un emplacement libéré du tas. L'accès suivant lirait des données poubelle ou paniquerait.
Le borrow checker et le GC : leçons apprises
Implémenter un ramasse-miettes en Rust est un exercice de négociation avec le borrow checker. La tension fondamentale est la suivante : le GC doit lire le tas (pour trouver les références) et écrire le tas (pour définir les bits de marquage et libérer les objets) en même temps.
Dans la Session 011, nous avons rencontré ce conflit directement. L'opération d'entité QueryAll devait itérer sur le magasin d'entités tout en allouant de nouveaux objets liste sur le tas :
rust// Ceci ne compile PAS :
let entities = self.entity_store.get(&type_name).unwrap();
for entity in entities.values() {
let obj_id = self.heap.alloc_entity(entity.clone()); // conflit &mut self
list.push(Value::Object(obj_id));
}La correction était le pattern clone-d'abord : collecter les données nécessaires dans une variable locale, puis opérer sur la copie :
rustlet entity_clones: Vec<EntityInstance> = self.entity_store
.get(&type_name)
.map(|store| store.values().cloned().collect())
.unwrap_or_default();
for entity in entity_clones {
let obj_id = self.heap.alloc_entity(entity);
list.push(Value::Object(obj_id));
}Ce pattern réapparaît dans toute la VM partout où le GC interagit avec des données vivantes. Ce n'est pas élégant. C'est correct. Et dans un runtime de langage où la correction signifie « les programmes de vos utilisateurs ne plantent pas avec une utilisation après libération », correct est ce qui compte.
Couverture de tests
Le GC a été testé avec 22 tests dédiés couvrant chaque type de racine et chaque cas limite :
- Allocation de base : les chaînes, listes, maps s'allouent correctement et retournent des valeurs
ObjectIdvalides. - Réutilisation de la liste libre : après collecte, les emplacements libérés sont réutilisés par les allocations suivantes.
- Racines de pile : les objets atteignables depuis la pile survivent à la collecte.
- Racines globales : les objets atteignables depuis les variables globales survivent à la collecte.
- Racines locales de cadres : les objets atteignables depuis les locales des cadres d'appel survivent à la collecte.
- Racines primitives : les valeurs primitives (
Int,Float,Bool) sur la pile n'interfèrent pas avec la collecte. - Références transitives : une liste contenant une chaîne -- les deux survivent si la liste est atteignable.
- Captures de fermetures : les objets capturés par les fermetures survivent aussi longtemps que la fermeture est vivante.
- Champs d'entités : les objets stockés dans les champs d'entités survivent aussi longtemps que l'entité est vivante.
- Sources d'itérateurs : la collection supportant un itérateur survit pendant l'itération.
- Valeurs de maps : les valeurs objet dans les maps survivent aussi longtemps que la map est vivante.
- Structures profondément imbriquées : une liste de maps de listes de chaînes -- l'arbre entier survit si la racine est atteignable.
- Cycles : l'objet A référence B, B référence A -- les deux survivent si l'un est atteignable, et aucun ne cause de récursion infinie dans le marqueur.
- Collectes multiples : exécuter le GC plusieurs fois ne corrompt pas le tas et ne perd pas d'objets vivants.
Ces tests n'ont pas été écrits après coup. Ils ont été écrits en parallèle avec l'implémentation, par un sous-agent, assurant que le GC était correct dès sa création.
Caractéristiques de performance
L'algorithme mark-and-sweep a des caractéristiques de performance bien connues :
- Phase de marquage : O(L), où L est le nombre d'objets vivants. Le marqueur visite chaque objet atteignable exactement une fois.
- Phase de balayage : O(H), où H est la taille totale du tas. Le balayeur visite chaque emplacement, y compris les libérés.
- Temps de pause : la collecte entière est stop-the-world -- la VM s'arrête pendant que le GC s'exécute.
- Débit : entre les collectes, l'allocation est O(1) (dépilage de la liste libre ou push du vecteur).
Pour les charges de travail cibles de FLIN -- des applications web avec un état modéré -- ces caractéristiques sont acceptables. Une application FLIN typique pourrait avoir quelques centaines d'objets vivants (entités, liaisons de vues, chaînes en cache). Le GC s'exécute en microsecondes.
Si FLIN devait un jour gérer des millions d'objets, nous passerions à un collecteur générationnel ou un marqueur incrémental. Mais l'optimisation prématurée du GC serait un effort gaspillé. L'implémentation actuelle est correcte, testée et assez rapide.
Ce que 731 lignes nous ont apporté
Après la Session 011, la VM avait un système de gestion de mémoire complet : allocation avec recyclage de liste libre, collecte mark-and-sweep avec marquage transitif, gestion des cycles, seuils adaptatifs et 22 tests prouvant que tout est correct.
Le tas grandirait au fur et à mesure de l'exécution du programme, et le GC récupérerait périodiquement les objets morts. Chaînes, listes, maps, entités, fermetures -- tout cela pouvait être créé et détruit en toute sécurité. Pas de fuites. Pas de pointeurs pendants. Pas d'utilisation après libération.
Le prochain défi était de faire fonctionner ces fermetures. Les fonctions d'ordre supérieur -- map, filter, reduce -- ont besoin de capturer des variables de leur portée englobante et de les transporter avec elles. C'est le sujet du prochain article.
Ceci est la partie 22 de la série « Comment nous avons construit FLIN », documentant comment un CEO à Abidjan et un CTO IA ont construit un langage de programmation à partir de zéro.
Prochain : [23] Fermetures et fonctions d'ordre supérieur dans la VM -- comment les upvalues et la sémantique de capture rendent map, filter et reduce possibles.