一个没有尽头的无尽循环:圣杯虫的故事

曾几何时,GBA推出了一款名为Hello Kitty Collection:Miracle Fashion Maker的游戏。这是一款可爱的游戏,它基于著名的Sanrio Hello Kitty系列游戏,由Imagineer开发。但是以一个貌似纯真的名字为幌子是一个阴险的问题。由于某些原因,这个简单的游戏无法在任何GBA模拟器上运行。但是,仅凭这一点还不足以将该问题称为圣杯的虫子。像圣杯的所有错误一样,该错误本身也完全令人困惑。解释很简单:在开始游戏的顺序中的某个时刻,它陷入了一个永不退出的循环,等待从内存中读取某个不存在的特定值。尽管许多游戏中都有类似的错误,例如,塞尔达传说:便帽(上限),它们依靠读取无效内存地址引起的特殊行为。但是这个周期似乎违反了这种行为。尽管如此,该游戏还是在真实设备上运行的。此外,在冷重启后将保存内容加载到Sonic Pinball Party中时,发生了完全相同的错误。这些无效的内存地址的期望会以某种方式错误吗?但是,如果是这样,怎么办?


但这是非法的,对吗?


等一下-如果您尝试访问无效的内存,那么游戏只需要崩溃即可,对吧?一个悬而未决的运行,段错误,或者一些其他错误应该发生。对?

好吧,它更像是。但事实并非如此。至少不在GBA上。

在GBA中使用的ARM处理器的体系结构中,此错误状态称为数据中止,仅当您尝试访问未为其分配读取权限1内存管理器时,才会发生这种错误状态。发生数据中止时,处理器完成其工作并转到异常向量分配给数据中止异常。然后,操作系统可以选择以下解决方案之一:终止当前进程,分配页面错误内存,让该进程处理这种情况,例如某些仿真器JIT使用“ fastmem”执行该操作,或执行一些其他操作。

GBA如何处理数据中止?数据中止的异常向量条目位于GBA控制台的引导ROM中(或在BIOS中也称为它)。如果GBA遇到数据中止,则它将尝试转到DACS 2处理程序如果存在,则发生阻塞。没有商业游戏具有DACS处理程​​序。那么,为什么这个游戏没有冻结呢?一切都非常简单-GBA从不产生数据中止。它没有内存管理器(MMU)(甚至没有DS中的内存保护单元),因此它可以继续工作并读取无效的内存。

内存总线进入现场。



什么是无效内存?她看起来如何?这是主要障碍。这是一个困难的情况:代码读取的内容在很大程度上取决于CPU最近的工作,或者更确切地说,取决于内存总线最近的工作。简而言之,当访问无效的内存时,CPU读取内存总线上的最后一个内容。要了解由此产生的后果,您需要了解一些有关内存总线及其工作原理的知识。

内存总线是将CPU连接到平台的所有内存组件的电子电路的一部分。在GBA上,有几个设备连接到内存总线:工作RAM,视频内存和盒带总线。当CPU尝试访问内存时,它会告诉内存总线需要访问哪个地址,然后激活与该地址对应的组件。然后,该组件将值放在总线上的该地址上,这可能需要花费3个周期,然后CPU才能最终从总线上读取该值。对于GBA,如果没有设备与该地址相关联,则不会将任何值写入总线,并且CPU会读取总线上最后放置的任何值情况可能以不同的方式变化,例如,如果读取是16位的,并且CPU尝试执行32位读取,但是通常,它始终是总线中的值。开发人员将此功能称为“开放总线”。先前,我写了它如何影响其他游戏

好吧,似乎一切看起来都还不错...对吗?


这样就可以缓存最后的内存访问吗?然后再带回来?在一般情况下,此方法会起作用,但存在一定的困难。首先,您需要确保所有内存访问操作的顺序正确。这比听起来要复杂得多,因为CPU用每条指令访问内存以获取管道中的下一条指令。实际上,在一般情况下,卡在总线中的内存是最后收到的指令。这将简化流程,因为您只需要获取最后一个预先选择的值即可。但是由于最后一个预选值仅取决于我们当前从内存执行的位置,因此它应该始终相同。即使接收到的地址在无效时发生了变化,您将始终获得相同的记忆。

嗯...停下来。但是该循环存在,如果预先选择此值,则不能退出。那么发生了什么?如果他不断收到以下说明,那么这些操作之间会发生什么?我试图在测试ROM上运行这种无限循环,以检查例如值是否变坏。如果该值最近没有更新,但是在每条指令中都更新了该值,则肯定会发生这种情况,因此它没有时间被破坏。我的测试从未离开循环。尽管我完全重新创建了游戏周期,但我做了一些与这些游戏不同的事情。我做错什么了?

神奇宝贝翡翠和ACE,仅在铁上存在


时光倒流,2020年1月。当时在Sonic Pinball Party上的错误报告大约有三年半的时间。在其他模拟器中,他享誉多年。我用完了工作理论。在本月底,昵称为merrp的用户加入了mGBA模拟器的Discord社区,并表示PokémonEmerald有一个新的任意代码执行故障(ACE),该故障仅在硬件上起作用。而且,这种故障很可能会由速动员使用,他们可能想练习模拟器。显然,此错误已成为解决该错误的诱人目标,尽管如果我在0.8.0版之前发现它会更好。我开始研究故障并确认对merrp的观察,即它仅适用于硬件。在我尝试过的所有模拟器中,游戏都挂有黑屏。但是merrp告诉我,它挂在循环中从无效内存中读取,并且我意识到很可能我无法在不久的将来修复该错误。这也是同样的错误。

这次,了解循环功能给了我优势。多亏了pokeemerald反编译项目,我可以轻松地对该功能进行有针对性的更改,以尝试弄清楚她如何设法摆脱困境。此循环的简化版本如下所示:

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

该循环执行一个相当简单的任务。有一个二维值表。在此列表的每一行上,type循环首先尝试确定该值是否为某个前哨值。如果是这样,循环结束。否则,它将对值应用掩码,并检查其是否大于要检查的值。否则,它会降低周期。在特殊情况下,该值type会超出表的边界,从而导致出现无效的指针。这意味着当您尝试访问i对于此不存在的列的此元素,我们将始终访问无效的内存。尽管表偏移量在返回实际内存之前随循环的每次迭代增加,但它可能需要数亿次重复。因此,很明显他没有。那么程序如何摆脱循环呢?

为了对此进行调查,我改变了周期并研究了如果我立即退出周期会发生什么情况。事实证明一切都很简单:此刻ACE在硬件和仿真器上都可以工作,没有任何问题。因此,我改为将屏幕颜色设置为程序退出循环并冻结时读取的值,以使颜色不变。我重新编译了代码,并在真实的GBA上运行了它。在黑屏上冻结几秒钟后,它变成了华丽的蓝色。


非常蓝

但模拟器仍然挂在黑屏上。如果他读取了先前收到的值,他将读取什么值?相反,它变成了暗绿色。


傅:

也就是说,程序在设法退出循环之前,肯定可以通过至少一次。结果还表明,从铁上退出循环所需要的时间有所不同。这通常需要2到30秒。到底是怎么回事?

新工作理论


然后我注意到了我的测试ROM和神奇宝贝翡翠挂起来后的区别。神奇宝贝播放音乐。音速弹球派对也演奏了音乐。凯蒂猫(Hello Kitty)没有演奏音乐,但是给了我一个主意。如果在预取和数据加载之间发生中断,会发生什么情况?程序在访问无效内存之前是否开始预取中断向量?我在mGBA中针对这种情况快速创建了一个布局,打开了测试ROM中的中断,当然它跳出了循环。然后,我在硬件上尝试了相同的测试ROM,但它并没有脱离循环。这样理论就产生了。最后,我意识到了一些事情。我确定您在上方注意到了一个星号,是的,在预取和访问内存之间可能会有一个事件,但是只有在预取和访问无效内存之间,内存总线发送的请求不是发给CPU的,而是发给其他东西的。

我说过内存总线是由CPU控制的。在大多数情况下,这是正确的,但是还有其他重要设备也可以绕过处理器访问内存总线。此过程称为直接内存访问。我在上一篇文章中谈到了DMA ,所以现在我不再讨论其工作原理。如果您重新阅读该文章,您可能会注意到我说DMA运行时主CPU暂停。这意味着在DMA运行时,总线上的值现在将是对DMA存储器的最后访问。如果DMA超出了实际内存到无效区域,则这一点尤为重要。但是,它复制了最后一个好的价值。

早就知道,如果将无效的内存加载到DMA中,则会获得最后的DMA值,但是我在mGBA中实现了很长时间,并且已经忘记了它。当我在研究Bug时在访问代码中看到无效内存的内容时,我的脑海中有些咔嗒声。如果DMA值在总线上停留了一条指令该怎么办?如果DMA之后的第一条指令在获得下一个值之前完成了对无效内存的加载,则理论上这将导致重新加载DMA值。此外,在GBA中播放音乐通常使用DMA来传输音频输出。为了正确执行此操作,需要一个精巧的仿真器,该仿真器可以在指令执行的中间(在指令开始和内存访问之间)阻塞CPU,并且mGBA仿真器中的GBA控制台仿真不是精巧的。这是我的事。回忆幸运的是,我设法解决了这个问题。解决方案并不完美,但是我现在可以将DMA之后指令的预期CPU地址与无效负载下的当前CPU地址进行比较,并使用单个地址代替该DMA值的预选值。

期待已久的决定


我在测试ROM中打开了用于H-blank的DMA操作,并将它们与V-blank同步,以使时序稳定,并在硬件上运行它,而...这一次它起作用了!从总线读取DMA值后,经过相同的迭代次数,测试ROM不断退出循环。我是正确的!为了在mGBA中正确执行此操作,需要进行几次尝试,但是现在程序退出循环,其结果与在硬件上相同。我终于在mGBA上出现了蓝色阴影。 Hello Kitty已启动。已在Sonic Pinball Party上节省了开支。

我做的。

这可能是我花在单个bug上的最长时间。三年来,我花了很多时间进行调试,以至于我不知所措,而且我确信其他开发人员的仿真器也会遇到类似情况。没有这种洞察力,可能要花我一年甚至更长的时间,但是黑屏(除了播放音乐之外什么也没发生)变成了导致整个问题崩溃的多米诺骨牌。

现在找到了解决方案,可以在其他GBA仿真器中实现该解决方案,从而结束了该错误。该错误将在mGBA 0.9.0中修复,我希望将在今年发布,并已在测试版本中修复。您终于可以开始玩Hello Kitty Collection:奇迹时装制作人了。当然,除非您愿意,否则我不是要审判您。

图片

  1. 如果您尝试执行没有执行权限的内存,这称为预取中止。
  2. DACS(调试和通信系统的简称)是GBA开发套件的一部分。
  3. 这些从总线读取的空闲周期有时称为等待状态。

All Articles