hrxdev#2 Un monde, des sauvegardes, des replays, et un bug caché dans le format de sauvegarde
· Nick
Depuis la première entrée, le noyau s’est doté d’un monde où poser des choses, de fichiers pour le conserver et d’un moyen de prouver que deux exécutions concordent. Toujours pas de graphismes ni de personnages. L’essentiel de cette entrée relève de la plomberie, et une partie concerne un bug qui méritait d’être raconté.
Un monde fait de tuiles
Le monde est une grille de tuiles de 1×1 m sur des niveaux distincts, numérotés à partir de zéro. Un mur ou une porte est une tuile ; un escalier sera un lien spécial entre deux niveaux, mais les escaliers ne sont pas encore construits. En interne, le monde est un ensemble de couches plates (sol, structure, drapeaux de structure) pour toute la carte, plus une couche dérivée pour la praticabilité. La carte est suivie par chunks de 16×16 avec des compteurs de version, pour qu’un moteur de rendu ou une recherche de chemin puisse demander « cette zone a-t-elle changé ? » sans comparer les tuiles.
La taille du monde est choisie à sa création. On construit avec des commandes qui prennent un rectangle : poser un sol, un mur ou une porte sur une zone, ou les retirer. Si une partie du rectangle est bloquée, le reste est construit quand même et la commande indique ce qu’elle a ignoré. Pour l’instant, il existe trois types de tuiles intégrés : sol, mur, porte. Désormais, la carte fait partie du hash du monde et des sauvegardes. Elle est vérifiée face à un modèle de référence lent et manifestement correct, sur des milliers de commandes aléatoires.
Sauvegardes et replays
Une sauvegarde et un replay partagent un même conteneur de fichier. Il est découpé en sections étiquetées, chacune avec un type et une version, pour que de nouvelles parties du monde (personnages, besoins, relations) puissent devenir de nouvelles sections plus tard sans casser les anciens fichiers. Il y a des sommes de contrôle sur l’en-tête et le corps, le corps est compressé, et chaque taille est comparée à une limite avant toute allocation de mémoire, si bien qu’un fichier corrompu ou malveillant ne peut pas faire dévorer toute la RAM au jeu. Les types de tuiles sont stockés par nom plutôt que par numéro, pour qu’une sauvegarde continue de fonctionner si la liste des types change.
Un replay, c’est ce que je voulais depuis le début : une graine plus le journal des commandes. Pendant l’enregistrement, le noyau écrit aussi un hash de contrôle tous les 100 ticks. À la relecture, il compare au fil de l’eau le résultat de chaque commande et chaque hash de contrôle, et s’arrête au premier tick où ils divergent. Un replay retient aussi quel build du noyau l’a enregistré, si bien qu’un replay venant d’un autre build est refusé au lieu de diverger en silence.
Le noyau lui-même ne touche jamais aux fichiers : il lit et écrit des flux, et c’est le jeu qui décide où vivent les sauvegardes. Cette frontière est imposée par la même mécanique d’API interdites qu’avant.
Pas encore fait : un outil en ligne de commande qui rejoue un fichier de replay, et le côté jeu de la sauvegarde (un dossier de sauvegardes, les sauvegardes automatiques, l’écriture sûre).
Prouver que deux exécutions concordent
Le test de déterminisme lance désormais un scénario dans deux processus séparés : une graine, un script de commandes de construction (certaines volontairement invalides) et un système de test qui puise dans chaque flux aléatoire. Chaque processus l’exécute de trois façons — d’une traite, via une sauvegarde puis une restauration, et via un replay des octets enregistrés — et compare les hashes à chaque tick. Les deux processus comparent ensuite leurs hashes entre eux tous les 10 ticks.
Je l’ai cassé exprès pour m’assurer qu’il pouvait échouer. Un Random sans graine glissé dans le tick a fait passer le test au rouge. Un hash de chaîne aléatoire, que .NET initialise différemment dans chaque processus, est passé inaperçu au sein d’un seul processus et n’a été détecté qu’en comparant les deux. C’est toute la raison d’être des deux processus.
La règle que j’ai fixée : un même build du noyau doit donner les mêmes hashes sur les processeurs x64 et arm64, donc un replay enregistré sur un Mac à puce Apple doit se rejouer sur un PC Windows. Des hashes de référence figés et des exemples de fichiers de sauvegarde et de replay existent précisément pour cette vérification. La trigonométrie et les exponentielles en virgule flottante diffèrent d’une plateforme à l’autre ; elles sont donc proscrites dans tout ce qui affecte le monde, et il me faudra un remplaçant déterministe la première fois qu’un système en aura besoin. Ces fichiers de référence ne changent que délibérément : si un hash dérive, le changement doit être expliqué avant d’être accepté.
Un banc d’essai capable de dire non
Il existe maintenant un lanceur sans interface qui prend un scénario, une graine et un nombre de ticks, et produit un rapport JSON : la médiane et le 99e centile du temps par tick, le nombre d’agents, le hash du monde et le nombre d’octets alloués par tick. Le premier scénario construit une carte de 512×512 sur 16 niveaux avec environ 52 000 commandes de construction.
La référence est conservée par machine, car des temps mesurés sur un portable ne veulent rien dire sur un PC de bureau. Une régression, c’est une médiane plus de 10 % au-dessus de la référence ou un 99e centile plus de 35 % au-dessus, et seulement si la hausse dépasse 0,05 ms, puisqu’un tick presque vide se situe à la résolution du chronomètre. Un seuil vaut sur toutes les machines : zéro octet alloué par tick. Je dois être honnête sur ce que cela mesure aujourd’hui. Sans systèmes ni personnages, un tick prend environ 35 nanosecondes, donc le seuil de temps dort la plupart du temps jusqu’à l’arrivée des premiers vrais systèmes dans le jalon du déplacement. C’est le seuil d’allocation qui travaille pour l’instant.
Le test instable qui ne l’était pas
Pendant que je construisais le banc d’essai, un test du format de sauvegarde s’est mis à échouer sur certains builds alors que le noyau n’avait pas changé. Le test inverse tour à tour chaque octet d’un replay compressé et exige que le chargeur refuse chacun d’eux. Sur un build, un octet proche de la fin du fichier était accepté. Sur le build précédent, le même test passait.
Pourquoi il allait et venait : un replay porte l’identifiant du build qui l’a écrit, donc les octets compressés diffèrent d’un build à l’autre, et avec eux l’octet qui est inversé. La faille a toujours été là ; le test ne la remarquait que quand les dés tombaient de ce côté.
La faille elle-même : la somme de contrôle couvrait les données après décompression, et le décompresseur de .NET s’est révélé indulgent. Il accepte un flux qui n’annonce jamais sa fin et ignore tout ce qui suit la fin. Inverser un bit de remplissage dans le dernier octet donne un autre flux, toujours valide, qui se décompresse vers les mêmes données ; la somme de contrôle correspondait donc toujours, et un fichier endommagé se chargeait comme s’il était sain.
La correction est une nouvelle version du conteneur. La somme de contrôle couvre désormais les octets tels qu’ils sont stockés dans le fichier et est vérifiée avant la décompression, et la décompression doit se terminer exactement là où l’en-tête l’indique. Un corps vide est stocké sans compression, car le compresseur n’écrit rien pour une entrée vide. Les vérifications utilisent maintenant des flux compressés fixes qui ne dépendent pas du build, plus du fuzzing de fichiers endommagés. Les fichiers d’exemple ont été régénérés pour la nouvelle version ; les hashes du monde n’ont pas changé.
Ailleurs
Le site web, celui que vous lisez, affiche maintenant deux compteurs de visiteurs sur la page d’accueil : les visiteurs uniques depuis toujours et sur les dernières 24 heures. Ils sont calculés à partir du journal des pages du serveur web, sans JavaScript, sans cookies et sans services extérieurs. Une adresse n’est stockée que sous forme de hash salé, les robots sont filtrés d’après leur user agent, et les chiffres ont quelques minutes de retard. Plusieurs personnes derrière un même réseau comptent pour une.
La suite
Le premier jalon, le squelette du noyau, est terminé. Ensuite vient M1, la vue de construction Godot : murs, portes et pièces issus du modèle du monde, découpe des étages, une caméra qui tourne par pas de 90° et de simples cubes à la place des graphismes. Le travail dessus n’a pas encore commencé. Voir la feuille de route.