👫 👩‍👩‍👦 ✋🏼 Un cycle sans fin qui n'était pas: l'histoire du bug du Saint Graal 🚩 👨🏾‍🏭 😊

Il était une fois un jeu pour GBA appelé Hello Kitty Collection: Miracle Fashion Maker. C'était un jeu mignon basé sur la célèbre franchise Sanrio Hello Kitty et développé par Imagineer. Mais sous le couvert d'un nom apparemment innocent était un problème insidieux. Pour une raison quelconque, ce jeu simple ne fonctionnait sur aucun émulateur GBA. Mais cela ne suffirait pas à lui seul à qualifier le problème d'insecte du Saint Graal. Comme tous les bogues du Saint Graal, ce bogue lui-même était complètement déroutant. L'explication était simple: à un moment donné de la séquence de lancement du jeu, il est tombé dans un cycle dont il n'est jamais sorti , en attendant qu'une certaine valeur soit lue dans une mémoire qui n'existe pas . Bien qu'il existe des bogues similaires dans de nombreux jeux, par exemple, dans l'intro populaireThe Legend of Zelda: The Minish Cap , ils s'appuient sur un comportement spécial causé par la lecture d'adresses mémoire non valides. Mais ce cycle semblait violer un tel comportement. Néanmoins, le jeu a fonctionné sur un équipement réel. De plus, le même bug s'est produit lors du chargement d'une sauvegarde dans Sonic Pinball Party après un redémarrage à froid. L'attente de ces adresses de mémoire invalides pourrait-elle être en quelque sorte erronée? Mais si oui, comment?

Mais c'est illégal, non?

Attendez une minute - si vous essayez d'accéder à une mémoire invalide, alors le jeu a juste besoin de planter, non? Une opération non résolue, une erreur de segmentation ou une autre erreur devrait se produire . Droite?

Eh bien, c'est plus comme Oui. Mais pas vraiment. Du moins pas sur la GBA.

Dans l'architecture des processeurs ARM utilisés dans GBA, cet état erroné est appelé abandon de données et se produit uniquement lorsque vous essayez d'accéder à la mémoire pour laquelle le gestionnaire de mémoire n'a pas attribué l'autorisation de lecture ¹ . Lorsque l'abandon des données se produit, le processeur termine ce qu'il faisait et passe au vecteur d'exceptionaffecté aux exceptions d'abandon des données. Ensuite, le système d'exploitation peut choisir l'une des solutions: tuer le processus en cours, affecter la mémoire de défauts de page , laisser le processus gérer la situation, comme certains émulateurs JIT le font avec «fastmem», ou effectuer d'autres actions.

Comment la GBA gère-t-elle les abandons de données? L'entrée du vecteur d'exception pour l'abandon des données se trouve dans la ROM de démarrage de la console GBA (ou, comme on l'appelle également, dans le BIOS). Si le GBA rencontre des données abandonnées, il essaie alors d'aller au gestionnaire DACS ²s'il existe, sinon le blocage se produit. Aucun jeu commercial ne dispose de gestionnaires DACS. Alors pourquoi ce jeu ne gèle-t-il pas? Tout est très simple - GBA ne génère jamais d'abandon de données. Il ne dispose pas d'un gestionnaire de mémoire (MMU) (ni même d'une unité de protection de la mémoire, comme dans DS), il continue donc de fonctionner et lit la mémoire invalide.

Le bus mémoire entre en scène.

Qu'est-ce que la mémoire invalide en général? Elle ressemble à quoi? C'est le principal problème. C'est une situation difficile: ce que le code lit dépend fortement de ce que le CPU a fait récemment, ou, plus précisément, de ce que le bus mémoire a fait récemment . En bref, lors de l'accès à une mémoire invalide, le CPU lit ce qui était le dernier sur le bus mémoire. Pour comprendre ce qui en découle, vous devez en apprendre un peu plus sur le bus mémoire et son fonctionnement.

Un bus mémoire fait partie d'un circuit électronique qui connecte le CPU à tous les composants mémoire de la plateforme. Sur la GBA, plusieurs périphériques sont connectés au bus mémoire: RAM de travail, mémoire vidéo et bus de cartouches. Lorsque le CPU essaie d'accéder à la mémoire, il indique au bus mémoire à quelle adresse il doit accéder, puis le composant correspondant à cette adresse est activé. Ensuite, le composant place la valeur à cette adresse sur le bus, ce qui peut prendre plusieurs ³ cycles , puis la CPU peut enfin lire la valeur sur le bus. Dans le cas de la GBA, si aucun équipement n'est associé à l'adresse, aucune valeur n'est écrite sur le bus et la CPU lit toute valeur placée en dernier sur le bus. La situation peut varier de différentes manières, par exemple, si la lecture était de 16 bits et que le CPU essaie d'effectuer une lecture de 32 bits, mais en général, ce sera toujours une valeur provenant du bus. Les développeurs appellent cette fonctionnalité «bus ouvert». Plus tôt, j'ai écrit comment cela affecte les autres jeux .

Eh bien, il semble que tout ne soit pas si mal ... non?

Vous pouvez donc simplement mettre en cache le dernier accès à la mémoire? Et puis le ramener à nouveau? Dans le cas général, cette approche fonctionnera, mais il y a certaines difficultés. Tout d'abord, vous devez vous assurer que toutes les opérations d'accès à la mémoire sont dans le bon ordre. C'est plus compliqué qu'il n'y paraît, car le CPU accède à la mémoire avec chaque instruction pour obtenir l'instruction suivante dans le pipeline. Et en fait, dans le cas général *, la mémoire coincée dans le bus est la dernière instruction reçue. Cela simplifie le processus, car vous devez obtenir uniquement cette dernière valeur présélectionnée. Mais puisque la dernière valeur présélectionnée ne dépend que de l'endroit où nous exécutons actuellement à partir de la mémoire, elle devrait toujours être la même. Même si l'adresse reçue change alors qu'elle n'est pas valide,vous obtiendrez toujours la même mémoire.

Euh ... Arrête. Mais ce cycle existe et il ne peut pas être quitté si cette valeur est présélectionnée. Alors, quoi de neuf? S'il reçoit constamment l'instruction suivante, que se passe-t-il entre ces opérations? J'ai essayé d'exécuter de telles boucles sans fin sur des ROM de test pour vérifier si, par exemple, la valeur pouvait mal tourner. Cela peut certainement se produire si la valeur n'a pas été mise à jour récemment, mais la valeur est mise à jour dans chaque instruction, de sorte qu'elle n'a pas le temps d'être corrompue. Mes tests n'ont jamais quitté la boucle. J'ai fait quelque chose de différent que dans ces jeux, même si j'ai recréé le cycle exactement. Qu'ai-je fait de mal?

Pokémon Emerald et ACE, apparaissant uniquement sur le fer

Avance rapide dans le temps, en janvier 2020. Le rapport de bogue à la Sonic Pinball Party à l'époque avait environ trois ans et demi. Dans d'autres émulateurs, il était connu depuis de nombreuses années. Je n'ai plus de théories de travail. A la fin de ce mois, un utilisateur avec le pseudo merrpa rejoint la communauté Discord de l'émulateur mGBA et a déclaré que Pokémon Emerald a un nouveau problème d'exécution de code arbitraire (ACE) qui ne fonctionne que sur le matériel. De plus, ce problème sera très probablement utilisé par les speedrunners, qui voudront peut-être pratiquer l'émulateur. De toute évidence, ce bogue est devenu une cible attrayante pour corriger l'erreur, mais il serait préférable que je le découvre avant la version 0.8.0. J'ai commencé à rechercher le problème et confirmé l'observation de merrp qu'il ne fonctionne que sur le matériel. Dans tous les émulateurs que j'ai essayés, le jeu était suspendu à un écran noir. Mais merrp m'a informé qu'il se bloque sur la lecture de la mémoire invalide dans une boucle, et j'ai réalisé que je ne pourrais probablement pas corriger l'erreur dans un proche avenir. C'est encore le même bug.

Cette fois, l'apprentissage des fonctions de bouclage m'a donné un avantage. Grâce au projet de décompilation pokeemerald, j'ai pu facilement apporter des modifications ciblées à la fonction pour essayer de comprendre comment elle a réussi à sortir de la boucle. Une version simplifiée de cette boucle ressemble à ceci:

uint16_t type = /* ... */;
for (int32_t i = 0; table[type][i] != 0xFFFF; ++i) {
	uint16_t value = table[type][i] & 0xFE00;
	if (value > 0x7E00) {
		break;
	}
	/* ... */
}

La boucle effectue une tâche assez simple. Il existe un tableau de valeurs bidimensionnel. Sur chaque ligne de cette table de colonnes, la typeboucle essaie d'abord de déterminer si la valeur est une certaine valeur sentinelle. Si c'est le cas, la boucle se termine. Sinon, il applique un masque à la valeur et vérifie si elle est supérieure à la valeur vérifiée. Sinon, ça descend le cycle. Dans un cas particulier de problème, la valeur typedépasse les limites du tableau, ce qui entraîne l'apparition d'un pointeur non valide. Cela signifie que lorsque vous essayez d'accéder àiPour cet élément de cette colonne inexistante, nous accèderons toujours à la mémoire invalide. Bien que le décalage de la table augmente à chaque itération de la boucle avant de revenir à la mémoire réelle, il peut nécessiter des centaines de millions de répétitions. Par conséquent, il est évident qu'il ne le fait pas. Alors, comment un programme sort-il d'une boucle?

Pour enquêter sur cela, j'ai changé le cycle et regardé ce qui se passerait si je sortais instantanément du cycle. Tout s'est avéré assez simple: à ce moment, ACE a travaillé à la fois sur le matériel et l'émulateur, et rien ne s'est arrêté. Au lieu de cela, j'ai essayé de définir la couleur de l'écran à la valeur que le programme lit lorsqu'il quitte la boucle et se fige afin que la couleur ne change pas. J'ai recompilé le code et l'ai exécuté sur un vrai GBA. Après quelques secondes de gel sur un écran noir, il est devenu une magnifique teinte bleue.

TRÈS BLEU

Mais l'émulateur était toujours accroché sur un écran noir. Quelle valeur lira-t-il s'il lit la valeur reçue précédemment? Au lieu de cela, il est devenu une turquoise sombre.

Fu.

C'est, le programme, avant qu'il a réussi à sortir du cycle, certainement passé au moins une fois. Il s'est également avéré que le temps nécessaire pour s'échapper du cycle sur le fer varie. Cela prenait généralement de 2 à 30 secondes. Que se passe-t-il?

Nouvelle théorie de travail

Ensuite, j'ai remarqué la différence entre ma ROM de test et le Pokémon Emerald lorsqu'elle était suspendue. Pokémon jouait de la musique. Sonic Pinball Party a également joué de la musique. Bonjour Kitty n'a pas joué de musique, mais ça m'a donné une idée. Que se passe-t-il si une interruption se produit entre la prélecture et le chargement des données? Le programme commence-t-il à extraire le vecteur d'interruption avant d'accéder à la mémoire invalide? J'ai rapidement créé une disposition pour cette situation dans mGBA, activé les interruptions dans la ROM de test et bien sûr, il est sorti de la boucle. Ensuite, j'ai essayé le même ROM de test sur le matériel et ... il n'est pas sorti de la boucle. Et donc la théorie est venue. Finalement, j'ai réalisé quelque chose. Je suis sûr que vous avez remarqué un astérisque ci-dessus, donc oui, il peut y avoir un événement entre la prélecture et l'accès à la mémoire,mais seulement si, entre la prélecture et l'accès à la mémoire invalide, le bus mémoire envoie une requête non pas au CPU, mais à autre chose.

J'ai dit que le bus mémoire est contrôlé par le CPU. Pour la plupart, cela est vrai, mais il existe d'autres équipements importants qui ont également accès au bus mémoire contournant le processeur. Ce processus est appelé accès direct à la mémoire . J'ai parlé de DMA dans un article précédent , alors maintenant je ne vais pas entrer dans les principes de son travail. Si vous relisez l'article, vous remarquerez peut-être que j'ai dit que le processeur principal se met en pause pendant l'exécution de DMA. Cela signifie que lorsque DMA est en cours d'exécution, la valeur sur le bus sera désormais le dernier accès à la mémoire DMA. Ceci est principalement important si le DMA va au-delà de la mémoire réelle vers une région invalide; cependant, il duplique la dernière bonne valeur.

On sait depuis longtemps que si vous chargez une mémoire invalide dans DMA, vous obtiendrez la dernière valeur DMA, mais je l'ai implémentée depuis longtemps dans mGBA et je l'ai déjà oubliée. Quand j'ai vu cela dans le code d'accès pour une mémoire invalide lors de l'étude du bug, quelque chose a cliqué dans ma tête. Que faire si la valeur DMA persiste sur le bus pour une instruction? Si la première instruction après que DMA a fini de charger la mémoire invalide avant qu'elle n'obtienne la valeur suivante, alors en théorie, cela devrait conduire à recharger la valeur DMA. De plus, la lecture de musique en GBA utilise généralement le DMA pour transmettre la sortie audio. Pour une implémentation correcte de cela, un émulateur tact-précis est nécessaire qui peut bloquer le CPU au milieu de l'exécution de l'instruction, entre le début de l'instruction et l'accès à la mémoire, et l'émulation de la console GBA dans l'émulateur mGBA n'est pas précise.Et c'est quelque chose pour moi.rappelle . Heureusement, j'ai réussi à contourner ce problème. La solution est imparfaite, mais je peux maintenant comparer l'adresse CPU attendue pour l'instruction après DMA avec l'adresse CPU actuelle pour une charge non valide et utiliser une seule adresse au lieu de la valeur présélectionnée pour cette valeur DMA.

La décision tant attendue

J'ai activé les opérations DMA pour H-blank dans la ROM de test et les ai synchronisées avec V-blank afin que les synchronisations soient stables, l'ai exécuté sur le matériel, et ... cette fois cela a fonctionné! La ROM de test quitte constamment la boucle après le même nombre d'itérations lorsque la valeur DMA est lue sur le bus. J'avais raison! Pour une implémentation correcte de ceci dans mGBA, plusieurs tentatives ont été nécessaires, mais maintenant le programme quitte le cycle avec les mêmes résultats que sur le matériel. J'ai finalement obtenu une nuance de bleu sur mGBA. Hello Kitty a démarré. Enregistrer à la Sonic Pinball Party a gagné.

Je l'ai fait.

Ce fut probablement le plus long temps que j'ai passé sur un seul bug. En trois ans, j'ai investi tellement de temps dans le débogage que j'ai perdu le compte, et je suis sûr que d'autres développeurs ont également fait face à des situations similaires dans leurs émulateurs. Sans cette perspicacité, cela aurait pu me prendre une autre année, voire plus, mais l'écran noir, sur lequel rien ne s'est passé, sauf pour jouer de la musique, est devenu cette tuile domino qui a conduit à l'effondrement de tout le problème.

Maintenant que la solution est trouvée, elle peut être implémentée dans d'autres émulateurs GBA, mettant fin à ce bogue. Le bogue sera corrigé dans mGBA 0.9.0, qui, je l'espère, sortira cette année et a déjà été corrigé dans les versions de test. Vous pouvez enfin jouer à Hello Kitty Collection: Miracle Fashion Maker. A moins, bien sûr, que vous ne le souhaitiez, il ne m'appartient pas de vous juger.

Si vous essayez d'exécuter de la mémoire qui n'a pas d'autorisations d'exécution, cela s'appelle abandon de la pré-lecture.
DACS (abréviation de Debugging and Communication System) fait partie du kit de développement GBA.
Ces cycles inactifs lors de la lecture du bus sont parfois appelés états d'attente.