🕠 🚙 👼🏻 Ein endloser Kreislauf, der nicht war: die Geschichte des Heiligen Grals 🚙 👨‍👩‍👦 💊

Es war einmal ein Spiel für GBA namens Hello Kitty Collection: Miracle Fashion Maker. Es war ein süßes Spiel, das auf dem berühmten Sanrio Hello Kitty-Franchise basiert und von Imagineer entwickelt wurde. Aber unter dem Deckmantel eines scheinbar unschuldigen Namens war dies ein heimtückisches Problem. Aus irgendeinem Grund lief dieses einfache Spiel auf keinem GBA-Emulator. Dies allein würde jedoch nicht ausreichen, um das Problem als Fehler des Heiligen Grals zu bezeichnen. Wie alle Käfer des Heiligen Grals war dieser Käfer selbst völlig verwirrend. Die Erklärung war einfach: Irgendwann in der Startsequenz des Spiels fiel es in einen Zyklus, aus dem es nie herauskam , und wartete darauf, dass ein bestimmter Wert aus einem Speicher gelesen wurde, den es nicht gibt . Obwohl es in vielen Spielen ähnliche Fehler gibt, zum Beispiel im beliebten IntroDie Legende von Zelda: The Minish Cap , sie beruhen auf speziellem Verhalten, das durch das Lesen ungültiger Speicheradressen verursacht wird. Aber dieser Zyklus schien ein solches Verhalten zu verletzen. Trotzdem funktionierte das Spiel mit realer Ausrüstung. Darüber hinaus trat beim Laden eines Speichers in die Sonic Pinball Party nach einem Kaltstart genau derselbe Fehler auf. Könnte die Erwartung dieser ungültigen Speicheradressen irgendwie falsch sein? Aber wenn ja, wie?

Aber das ist illegal, oder?

Warten Sie eine Minute - wenn Sie versuchen, auf ungültigen Speicher zuzugreifen, muss das Spiel nur abstürzen, oder? Ein ungelöster Vorgang, ein Segfault oder ein anderer Fehler sollte auftreten . Recht?

Nun, es ist eher wie Ja. Aber nicht wirklich. Zumindest nicht auf der GBA.

In der Architektur der ARM-Prozessoren, die in GBA verwendet wurden, wird dieser fehlerhafte Status als Datenabbruch bezeichnet und tritt nur auf, wenn Sie versuchen, auf Speicher zuzugreifen, für den der Speichermanager keine Leseberechtigung ¹ zugewiesen hat . Wenn ein Datenabbruch auftritt, schließt der Prozessor seine Arbeit ab und wechselt zum AusnahmevektorAusnahmen für Datenabbruch zugewiesen. Dann kann das Betriebssystem eine der Lösungen auswählen: Beenden Sie den aktuellen Prozess, weisen Sie einen Seitenfehlerspeicher zu , lassen Sie den Prozess die Situation behandeln, wie es einige Emulatoren JIT mit „fastmem“ tun, oder führen Sie andere Aktionen aus.

Wie geht der GBA mit Datenabbruch um? Der Ausnahmevektoreintrag für den Datenabbruch befindet sich im Boot-ROM der GBA-Konsole (oder, wie er auch genannt wird, im BIOS). Wenn der GBA auf einen Datenabbruch stößt, versucht er, zum DACS ^2- Handler zu wechselnWenn es existiert, tritt andernfalls eine Blockierung auf. Kein kommerzielles Spiel hat DACS-Handler. Warum friert dieses Spiel nicht ein? Alles ist sehr einfach - GBA generiert niemals einen Datenabbruch. Es verfügt nicht über einen Speichermanager (MMU) (oder sogar eine Speicherschutzeinheit wie in DS), funktioniert also einfach weiter und liest ungültigen Speicher aus.

Der Speicherbus betritt die Szene.

Was ist ein ungültiger Speicher im Allgemeinen? Wie sieht sie aus? Dies ist der Hauptgrund. Dies ist eine schwierige Situation: Was der Code liest, hängt stark davon ab, was die CPU kürzlich oder genauer gesagt, was der Speicherbus kürzlich getan hat . Kurz gesagt, beim Zugriff auf einen ungültigen Speicher liest die CPU, was der letzte auf dem Speicherbus war. Um zu verstehen, was daraus folgt, müssen Sie ein wenig über den Speicherbus und dessen Funktionsweise lernen.

Ein Speicherbus ist Teil einer elektronischen Schaltung, die die CPU mit allen Speicherkomponenten der Plattform verbindet. Auf dem GBA sind mehrere Geräte an den Speicherbus angeschlossen: Arbeitsspeicher, Videospeicher und Kassettenbus. Wenn die CPU versucht, auf den Speicher zuzugreifen, teilt sie dem Speicherbus mit, auf welche Adresse sie zugreifen muss, und dann wird die dieser Adresse entsprechende Komponente aktiviert. Dann platziert die Komponente den Wert an dieser Adresse auf dem Bus, was mehrere ³ Zyklen dauern kann , und dann kann die CPU schließlich den Wert vom Bus lesen. Wenn im Fall des GBA der Adresse kein Gerät zugeordnet ist, wird kein Wert in den Bus geschrieben, und die CPU liest den zuletzt auf dem Bus platzierten Wert. Die Situation kann auf unterschiedliche Weise variieren, z. B. wenn der Lesevorgang 16-Bit war und die CPU versucht, einen 32-Bit-Lesevorgang durchzuführen. Im Allgemeinen handelt es sich jedoch immer um einen Wert vom Bus. Entwickler nennen diese Funktion "Bus öffnen". Früher habe ich geschrieben, wie es andere Spiele beeinflusst .

Nun, es scheint, dass nicht alles so schlecht aussieht ... Richtig?

Sie können also nur den letzten Speicherzugriff zwischenspeichern? Und dann wieder zurückbringen? Im allgemeinen Fall wird dieser Ansatz funktionieren, es gibt jedoch bestimmte Schwierigkeiten. Zunächst müssen Sie sicherstellen, dass alle Speicherzugriffsvorgänge in der richtigen Reihenfolge ausgeführt werden. Dies ist komplizierter als es sich anhört, da die CPU mit jedem Befehl auf den Speicher zugreift, um den nächsten Befehl in der Pipeline zu erhalten. Tatsächlich ist im allgemeinen Fall * der im Bus stecken gebliebene Speicher der letzte Befehl, der empfangen wurde. Dies vereinfacht den Vorgang, da Sie nur diesen letzten, vorausgewählten Wert erhalten müssen. Da der zuletzt vorgewählte Wert jedoch nur davon abhängt, wo er gerade aus dem Speicher ausgeführt wird, sollte er immer derselbe sein. Auch wenn sich die empfangene Adresse ändert, während sie ungültig ist,Sie erhalten immer den gleichen Speicher.

Äh ... Hör auf. Dieser Zyklus existiert jedoch und kann nicht beendet werden, wenn dieser Wert vorausgewählt ist. Also, was ist los? Wenn er ständig die folgende Anweisung erhält, was passiert dann zwischen diesen Operationen? Ich habe versucht, solche Endlosschleifen auf Test-ROMs auszuführen, um zu überprüfen, ob beispielsweise der Wert schlecht werden könnte. Dies kann definitiv passieren, wenn der Wert nicht kürzlich aktualisiert wurde, der Wert jedoch in jeder Anweisung aktualisiert wird, sodass keine Zeit für Beschädigungen bleibt. Meine Tests haben die Schleife nie verlassen. Ich habe etwas anderes gemacht als in diesen Spielen, obwohl ich den Zyklus genau neu erstellt habe. Was habe ich falsch gemacht?

Pokémon Emerald und ACE kommen nur auf Eisen vor

Schneller Vorlauf im Januar 2020. Der Fehlerbericht auf der Sonic Pinball Party war damals etwa dreieinhalb Jahre alt. In anderen Emulatoren war er viele Jahre bekannt. Ich habe keine Arbeitstheorien mehr. Ende dieses Monats ein Benutzer mit dem Spitznamen merrptrat der Discord-Community des mGBA-Emulators bei und sagte, dass Pokémon Emerald einen neuen ACE (Arbitrary Code Execution Glitch) hat, der nur auf Hardware funktioniert. Darüber hinaus wird dieser Fehler höchstwahrscheinlich von Speedrunnern verwendet, die den Emulator üben möchten. Offensichtlich ist dieser Fehler ein attraktives Ziel für die Behebung des Fehlers geworden, obwohl es besser wäre, wenn ich ihn vor Version 0.8.0 herausfinden würde. Ich begann den Fehler zu untersuchen und bestätigte die Beobachtung von merrp, dass es nur auf Hardware funktioniert. In allen Emulatoren, die ich ausprobiert habe, hing das Spiel mit einem schwarzen Bildschirm. Aber merrp teilte mir mit, dass es beim Lesen aus einem ungültigen Speicher in einer Schleife hängt, und ich erkannte, dass ich den Fehler höchstwahrscheinlich in naher Zukunft nicht beheben konnte. Dies ist wieder der gleiche Fehler.

Dieses Mal gab mir das Erlernen von Schleifenfunktionen einen Vorteil. Dank des Pokeemerald- Dekompilierungsprojekts konnte ich leicht gezielte Änderungen an der Funktion vornehmen, um herauszufinden, wie sie es geschafft hat, aus der Schleife herauszukommen. Eine vereinfachte Version dieser Schleife sieht ungefähr so aus:

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

Die Schleife führt eine ziemlich einfache Aufgabe aus. Es gibt eine zweidimensionale Wertetabelle. In jeder Zeile dieser Spaltentabelle versucht die typeSchleife zunächst festzustellen, ob der Wert ein bestimmter Sentinel-Wert ist. Wenn ja, endet die Schleife. Andernfalls wird eine Maske auf den Wert angewendet und geprüft, ob er größer als der zu prüfende Wert ist. Ansonsten geht es den Zyklus hinunter. In einem bestimmten Fall eines Fehlers typeüberschreitet der Wert die Grenzen der Tabelle, was zum Auftreten eines ungültigen Zeigers führt. Dies bedeutet, wenn Sie versuchen, darauf zuzugreifeniAuf dieses Element dieser nicht vorhandenen Spalte wird immer auf ungültigen Speicher zugegriffen. Obwohl der Tabellenversatz mit jeder Iteration der Schleife zunimmt, bevor zum tatsächlichen Speicher zurückgekehrt wird, sind möglicherweise Hunderte Millionen Wiederholungen erforderlich. Daher ist es offensichtlich, dass er dies nicht tut. Wie kommt ein Programm aus einer Schleife heraus?

Um dies zu untersuchen, habe ich den Zyklus geändert und mir angesehen, was passieren würde, wenn ich sofort aus dem Zyklus ausbrechen würde. Alles stellte sich als recht einfach heraus: In diesem Moment arbeitete ACE sowohl an der Hardware als auch am Emulator, und nichts hing. Also habe ich stattdessen versucht, die Bildschirmfarbe auf den Wert einzustellen, den das Programm beim Verlassen der Schleife liest und einfriert, damit sich die Farbe nicht ändert. Ich habe den Code neu kompiliert und auf einem echten GBA ausgeführt. Nach ein paar Sekunden Einfrieren auf einem schwarzen Bildschirm wurde es zu einem wunderschönen blauen Farbton.

SEHR BLAU

Aber der Emulator hing immer noch auf einem schwarzen Bildschirm. Welchen Wert liest er, wenn er den zuvor empfangenen Wert liest? Stattdessen wurde es ein dunkles Türkis.

Fu.

Das heißt, das Programm, bevor es raus aus dem Zyklus verwaltet werden , mit Sicherheit mindestens einmal vergangen. Es stellte sich auch heraus, dass die Zeit, die erforderlich ist, um mit Eisen aus dem Kreislauf zu entkommen, unterschiedlich ist. Dies dauerte normalerweise 2 bis 30 Sekunden. Was ist los?

Neue Arbeitstheorie

Dann bemerkte ich den Unterschied zwischen meinem Test-ROM und dem Pokémon Emerald, als es hing. Pokémon spielte Musik. Sonic Pinball Party spielte auch Musik. Hallo Kitty hat keine Musik gespielt, aber es gab mir eine Idee. Was passiert, wenn zwischen Prefetching und Datenladen ein Interrupt auftritt? Beginnt das Programm, den Interrupt-Vektor vorab abzurufen, bevor auf den ungültigen Speicher zugegriffen wird? Ich habe schnell ein Layout für diese Situation in mGBA erstellt, Interrupts im Test-ROM aktiviert und es ist natürlich aus der Schleife geraten. Dann habe ich das gleiche Test-ROM auf Hardware ausprobiert und ... es ist nicht aus der Schleife geraten. Und so entstand die Theorie. Am Ende wurde mir etwas klar. Ich bin mir sicher, dass Sie oben ein Sternchen bemerkt haben. Ja, es kann ein Ereignis zwischen dem Vorabrufen und dem Zugreifen auf den Speicher geben.aber nur, wenn der Speicherbus zwischen dem Prefetch und dem Zugriff auf ungültigen Speicher eine Anforderung nicht an die CPU, sondern an etwas anderes sendet.

Ich sagte, dass der Speicherbus von der CPU gesteuert wird. Dies ist größtenteils der Fall, aber es gibt auch andere wichtige Geräte, die unter Umgehung des Prozessors Zugriff auf den Speicherbus haben. Dieser Vorgang wird als direkter Speicherzugriff bezeichnet . Ich habe in einem früheren Artikel über DMA gesprochen , daher werde ich jetzt nicht auf die Prinzipien seiner Arbeit eingehen. Wenn Sie den Artikel erneut lesen, werden Sie möglicherweise feststellen, dass die Haupt-CPU angehalten wird, während DMA ausgeführt wird. Dies bedeutet, dass während DMA ausgeführt wird, der Wert auf dem Bus jetzt der letzte Zugriff auf den DMA-Speicher ist. Dies ist hauptsächlich wichtig, wenn der DMA über den tatsächlichen Speicher hinaus in einen ungültigen Bereich übergeht. Es dupliziert jedoch den letzten guten Wert.

Es ist seit langem bekannt, dass Sie beim Laden eines ungültigen Speichers in DMA den letzten DMA-Wert erhalten, aber ich habe ihn lange in mGBA implementiert und ihn bereits vergessen. Als ich dies im Zugangscode für ungültigen Speicher sah, als ich den Fehler studierte, klickte etwas in meinem Kopf. Was ist, wenn der DMA-Wert für eine Anweisung auf dem Bus verbleibt? Wenn der erste Befehl nach DMA das Laden des ungültigen Speichers beendet, bevor er den nächsten Wert erhält, sollte dies theoretisch zum erneuten Laden des DMA-Werts führen. Darüber hinaus verwendet das Abspielen von Musik in GBA normalerweise DMA, um die Audioausgabe zu übertragen. Für die korrekte Implementierung ist ein taktgenauer Emulator erforderlich, der die CPU während der Befehlsausführung zwischen dem Start des Befehls und dem Speicherzugriff blockieren kann, und die GBA-Konsolenemulation im mGBA-Emulator ist nicht taktgenau.Und das ist etwas für mich.erinnert sich . Zum Glück konnte ich dieses Problem umgehen. Die Lösung ist unvollständig, aber ich kann jetzt die erwartete CPU-Adresse für den Befehl nach DMA mit der aktuellen CPU-Adresse für eine ungültige Last vergleichen und anstelle des vorgewählten Werts für diesen DMA-Wert eine einzelne Adresse verwenden.

Die lang erwartete Entscheidung

Ich habe die DMA-Operationen für H-Blank im Test-ROM aktiviert und sie mit V-Blank synchronisiert, damit die Timings stabil sind, habe es auf Hardware ausgeführt und ... diesmal hat es funktioniert! Das Test-ROM verließ die Schleife nach der gleichen Anzahl von Iterationen ständig, wenn der DMA-Wert vom Bus gelesen wurde. Ich lag richtig! Für die korrekte Implementierung in mGBA waren mehrere Versuche erforderlich, aber jetzt verlässt das Programm den Zyklus mit den gleichen Ergebnissen wie auf der Hardware. Ich habe endlich einen Blauton auf mGBA bekommen. Hallo Kitty hat gebootet. Das Sparen bei der Sonic Pinball Party hat sich verdient.

Ich habe es gemacht.

Dies war wahrscheinlich die längste Zeit, die ich mit einem einzelnen Fehler verbracht habe. Im Laufe von drei Jahren habe ich so viel Zeit in das Debuggen investiert, dass ich die Zählung verloren habe, und ich bin sicher, dass auch andere Entwickler in ihren Emulatoren mit ähnlichen Situationen konfrontiert waren. Ohne diese Einsicht hätte ich ein weiteres Jahr oder sogar noch länger brauchen können, aber der schwarze Bildschirm, auf dem nichts anderes passiert ist als Musik zu spielen, wurde zu der Domino-Kachel, die zum Zusammenbruch des gesamten Problems führte.

Nachdem die Lösung gefunden wurde, kann sie in anderen GBA-Emulatoren implementiert werden, wodurch dieser Fehler behoben wird. Der Fehler wird in mGBA 0.9.0 behoben, das hoffentlich in diesem Jahr veröffentlicht wird und bereits in Testversionen behoben wurde. Sie können endlich Hello Kitty Collection: Miracle Fashion Maker spielen. Es sei denn natürlich, Sie wünschen, es ist nicht meine Aufgabe, Sie zu beurteilen.

Wenn Sie versuchen, Speicher ohne Ausführungsberechtigungen auszuführen, wird dies als Prefetch-Abbruch bezeichnet.
DACS (kurz für Debugging and Communication System) ist Teil des GBA-Entwicklungskits.
Diese Leerlaufzyklen beim Lesen vom Bus werden manchmal als Wartezustände bezeichnet.