Quelle technique sous-jacente permet à **Go** de relocaliser l'intégralité de la pile d'une goroutine à un nouvel emplacement mémoire tout en préservant la validité de tous les pointeurs faisant référence aux données allouées sur la pile?

Réponse à la question

Historique

Les premières implémentations de Go allouaient des piles de taille fixe (1 Ko par goroutine), ce qui épuisait la mémoire avec une forte concurrence ou débordait lors de profonde récursions. Le langage a évolué des piles segmentées (morceaux liés) dans les premières versions vers la copie de piles contiguë dans Go 1.3+, afin d'améliorer la localité de cache et de simplifier la gestion des pointeurs.

Problème

Lorsqu'une goroutine épuise son segment de pile actuel, le runtime doit allouer une région mémoire plus grande et relocaliser toutes les données de pile existantes. Cette relocalisation risque d'invalider les pointeurs qui font référence aux variables de la pile, car leurs adresses mémoire changent pendant le déplacement, pouvant provoquer des corruptions mémoire ou des plantages.

Solution

Le compilateur insère un préambule de vérification de pile à chaque entrée de fonction, comparant le pointeur de pile à la page de garde. Si l'espace est insuffisant, il appelle runtime.morestack, qui alloue une nouvelle pile (généralement en doublant la taille), copie l'ancien contenu et utilise des bitmaps de pointeurs générés par le compilateur pour trouver et ajuster tous les pointeurs dans la pile qui pointent vers d'autres emplacements de pile.

Exemple de code

La fonction suivante montre comment les pointeurs vers les variables de pile restent valides même lorsque la pile grandit pendant la récursion :

func Calculate(depth int, prev *int) int {
    if depth == 0 {
        return *prev
    }
    // current est alloué sur la pile
    current := depth * 100
    
    // &current peut pointer vers l'ancienne position de la pile
    // Si la pile grandit ici, le runtime met à jour le pointeur
    return Calculate(depth-1, &current) + *prev
}

L'exécution reprend sur la nouvelle pile avec des registres mis à jour, assurant que tous les pointeurs pointent vers les bonnes nouvelles adresses.

Situation de la vie réelle

Scénario

Un moteur de correspondance financière traitant des calculs de carnet de commandes récursifs a rencontré des plantages sporadiques lors d'événements de marché à haute volatilité lorsque la profondeur de récursion a dépassé l'allocation de pile initiale de 2 Ko. Le système nécessitait une solution qui maintenait la clarté des algorithmes récursifs sans compromettre les millions de goroutines légères gérant des connexions concurrentes.

Problème

L'algorithme de correspondance utilisait une récursion profonde pour parcourir la profondeur des commandes en forme d'arbre, provoquant des paniques de débordement de pile précisément lorsque le volume des échanges atteignait son apogée. La solution devait gérer la récursion non bornée en toute sécurité sans gaspiller des gigaoctets de mémoire sur des piles grandes pré-allouées pour des goroutines majoritairement inactives.

Solution 1 : Piles fixes grandes

Pré-allouer de grandes piles pour toutes les goroutines à l'aide de debug.SetMaxStack ou en modifiant les valeurs par défaut du runtime. Avantages : Élimine complètement les frais généraux de croissance et le risque de débordement. Inconvénients : Consomme une mémoire excessive pour les gestionnaires de connexions inactifs, violant la promesse de goroutines légères et réduisant la concurrence maximale réalisable.

Solution 2 : Conversion itérative

Réécrire le parcours arborescent récursif en un algorithme itératif avec une tranche de pile allouée sur le tas explicitement pour suivre l'état de parcours. Avantages : Utilisation de mémoire prévisible et aucun risque de débordement de pile. Inconvénients : Complexité de code accrue, perte de clarté algorithmique et pression supplémentaire sur la collecte des déchets causée par les allocations fréquentes de tranches pendant le trading à fort volume.

Solution 3 : Croissance dynamique de la pile

Conserver le design récursif mais s'appuyer sur la croissance contiguë de la pile de Go, en s'assurant que le compilateur optimise les cadres de fonction avec des cartes de pointeurs précises. Avantages : Maintient une logique récursive claire, utilise la mémoire proportionnellement au besoin réel, et gère les pics de trafic automatiquement sans modifications de code. Inconvénients : Pauses de microsecondes lors de la copie de la pile, bien que celles-ci soient atténuées par de petites piles par défaut et une copie efficace.

Approche choisie

La solution 3 a été sélectionnée car le surcoût de 100 nanosecondes de la copie de la pile s'est avéré négligeable par rapport à la latence du réseau, et elle a préservé la clarté mathématique de l'algorithme de correspondance récursif. Nous avons ajouté des limites de profondeur de récursion comme garde-fou pour éviter que des boucles infinies ne consomment des piles de 1 Go.

Résultat

Le système a soutenu 50 000 calculs récursifs concurrents lors des tests de résistance du marché sans plantages. L'utilisation de la mémoire est restée sous 300 Mo pour 100 000 goroutines, et la latence p99 a augmenté de moins de 2 microsecondes lors des événements de croissance de la pile, répondant à des requis stricts de trading à haute fréquence.

Ce que les candidats manquent souvent

Pourquoi la copie de pile ne casse-t-elle pas les pointeurs vers les variables de pile lorsque la pile se déplace vers une nouvelle adresse en mémoire ?

Le runtime s'appuie sur des cartes de pile (bitmaps) générées par le compilateur pour chaque fonction. Ces cartes identifient quelles slots dans le cadre de pile contiennent des pointeurs. Pendant runtime.copystack, le runtime parcourt ces cartes, trouve chaque pointeur pointant vers l'ancienne plage de pile et le met à jour à l'offset correspondant dans la nouvelle pile. Cela garantit qu'une fois l'adresse mémoire physique changée, toutes les références restent valides et pointent vers les bons nouveaux emplacements.

Comment Go gère-t-il la croissance de la pile lors des appels CGO qui pourraient contenir des pointeurs vers des données de pile Go ?

L'exécution CGO passe toujours à la pile système (g0) avant d'entrer dans le code C. Le runtime s'assure qu'aucun pointeur de pile de goroutine n'est exposé aux fonctions C. Si la croissance de la pile se produit pendant l'exécution du code C (via une goroutine séparée), la pile C reste inchangée. Lors du retour de C à Go, le runtime repasse à la pile de goroutine (potentiellement déplacée) en utilisant le pointeur de pile mis à jour sauvegardé pendant la transition runtime.entersyscall.

Quelle est la cause de l'erreur fatale "runtime: la pile de goroutine dépasse la limite de 1000000000 octets" et comment cela diffère-t-il de la croissance normale ?

Contrairement à l'expansion de pile régulière qui copie vers une région contiguë plus grande, cette erreur se produit lorsque runtime.morestack détecte que la croissance demandée dépasserait la limite stricte (1 Go sur les systèmes 64 bits). Cela indique une récursion non bornée ou une allocation incontrôlable. Alors que la croissance normale est transparente et basée sur la copie, atteindre cette limite déclenche une panique immédiate car le runtime ne peut pas satisfaire la demande mémoire sans risquer un OOM système, et continuer l'exécution serait dangereux.