🤹🏽 🧠 👩🏼 Um ciclo interminável que não era: a história do inseto do Santo Graal 👩‍👧 🍳 👨🏽‍🤝‍👨🏻

Era uma vez um jogo para GBA chamado Hello Kitty Collection: Miracle Fashion Maker. Foi um jogo fofo baseado na famosa franquia Sanrio Hello Kitty e desenvolvido pela Imagineer. Mas, sob o pretexto de um nome aparentemente inocente, havia um problema insidioso. Por alguma razão, este jogo simples não foi executado em nenhum emulador de GBA. Mas isso por si só não seria suficiente para chamar o problema de inseto do Santo Graal. Como todos os insetos do Santo Graal, esse inseto em si era completamente confuso. A explicação era simples: em algum momento da sequência de lançamento do jogo, ele entrou em um ciclo do qual nunca saiu , esperando que um determinado valor fosse lido da memória que ele não existe . Embora existam erros semelhantes em muitos jogos, por exemplo, na introdução popularThe Legend of Zelda: The Minish Cap , eles contam com um comportamento especial causado pela leitura de endereços de memória inválidos. Mas esse ciclo parecia violar esse comportamento. No entanto, o jogo funcionou em equipamentos reais. Além disso, ocorreu exatamente o mesmo bug ao carregar um save no Sonic Pinball Party após uma reinicialização a frio. Poderia a expectativa desses endereços de memória inválidos de alguma forma errônea? Mas se sim, como?

Mas isso é ilegal, certo?

Espere um minuto - se você está tentando acessar a memória inválida, o jogo precisa travar, certo? Uma operação não resolvida, segfault ou algum outro erro deve ocorrer . Direita?

Bem, é mais como sim. Mas não realmente. Pelo menos não no GBA.

Na arquitetura dos processadores ARM usados no GBA, esse estado incorreto é chamado de cancelamento de dados e ocorre apenas quando você tenta acessar a memória à qual o gerenciador de memória não atribuiu a permissão de leitura ¹ . Quando ocorre a interrupção dos dados, o processador conclui o que estava fazendo e vai para o vetor de exceçãoatribuído a exceções de cancelamento de dados. Em seguida, o sistema operacional pode escolher uma das soluções: interromper o processo atual, atribuir memória de falha de página , deixar o processo lidar com a situação, como alguns emuladores JIT fazem com “fastmem” ou executar outras ações.

Como o GBA lida com a interrupção de dados? A entrada do vetor de exceção para o cancelamento de dados está localizada na ROM de inicialização do console GBA (ou, como também é chamado, no BIOS). Se o GBA encontrar um cancelamento de dados, ele tentará ir para o manipulador DACS ²se existir, ocorrerá o bloqueio. Nenhum jogo comercial possui manipuladores DACS. Então, por que esse jogo não está congelando? Tudo é muito simples - o GBA nunca gera abortamento de dados. Ele não possui um gerenciador de memória (MMU) (ou mesmo uma unidade de proteção de memória, como no DS), portanto, continua a trabalhar e lê a memória inválida.

O barramento de memória entra em cena.

O que é memória inválida em geral? Como é a aparência dela? Este é o principal obstáculo. Essa é uma situação difícil: o que o código lê depende muito do que a CPU fez recentemente ou, mais precisamente, do que o barramento de memória fez recentemente . Em resumo, ao acessar uma memória inválida, a CPU lê qual foi a última no barramento de memória. Para entender o que se segue, é necessário aprender um pouco sobre o barramento de memória e como ele funciona.

Um barramento de memória faz parte de um circuito eletrônico que conecta a CPU a todos os componentes de memória da plataforma. No GBA, vários dispositivos estão conectados ao barramento de memória: RAM de trabalho, memória de vídeo e barramento de cartucho. Quando a CPU tenta acessar a memória, informa ao barramento de memória a qual endereço ele precisa acessar e, em seguida, o componente correspondente a esse endereço é ativado. Em seguida, o componente coloca o valor nesse endereço no barramento, o que pode levar vários ³ ciclos e, em seguida, a CPU pode finalmente ler o valor do barramento. No caso do GBA, se nenhum equipamento estiver associado ao endereço, nenhum valor será gravado no barramento e a CPU lerá qualquer valor colocado por último no barramento.. A situação pode variar de maneiras diferentes, por exemplo, se a leitura for de 16 bits e a CPU tentar executar a leitura de 32 bits, mas, em geral, sempre será um valor do barramento. Os desenvolvedores chamam esse recurso de "barramento aberto". Anteriormente, escrevi como isso afeta outros jogos .

Bem, parece que tudo não parece tão ruim ... Certo?

Então você pode apenas armazenar em cache o último acesso à memória? E depois trazê-lo de volta? No caso geral, essa abordagem funcionará, mas há certas dificuldades. Primeiro, você precisa garantir que todas as operações de acesso à memória estejam na ordem correta. Isso é mais complicado do que parece, porque a CPU acessa a memória com cada instrução para obter a próxima instrução no pipeline. E, de fato, no caso geral *, a memória presa no barramento é a última instrução recebida. Isso simplifica o processo, porque você precisa obter apenas esse último valor pré-selecionado. Mas como o último valor pré-selecionado depende apenas de onde estamos executando atualmente a partir da memória, ele deve sempre ser o mesmo. Mesmo que o endereço recebido mude enquanto é inválido,você sempre terá a mesma memória.

Pare. Mas esse ciclo existe e não pode ser encerrado se esse valor estiver pré-selecionado. Então, o que está acontecendo? Se ele recebe constantemente as seguintes instruções, o que acontece entre essas operações? Tentei executar loops intermináveis em ROMs de teste para verificar se, por exemplo, o valor poderia dar errado. Definitivamente, isso pode acontecer se o valor não tiver sido atualizado recentemente, mas o valor for atualizado em cada instrução, portanto, não há tempo para ser corrompido. Meus testes nunca saíram do circuito. Eu fiz algo diferente do que nesses jogos, embora tenha recriado exatamente o ciclo. O que eu fiz errado?

Pokémon Emerald e ACE, ocorrendo apenas em ferro

Avanço rápido no tempo, em janeiro de 2020. O relatório de bugs na Sonic Pinball Party naquela época tinha cerca de três anos e meio de idade. Em outros emuladores, ele era conhecido por muitos anos. Eu fiquei sem teorias de trabalho. No final deste mês, um usuário com o apelido merrpingressou na comunidade Discord do emulador de mGBA e disse que o Pokémon Emerald tem uma nova falha arbitrária de execução de código (ACE) que funciona apenas em hardware. Além disso, essa falha provavelmente será usada pelos speedrunners, que podem querer praticar o emulador. Obviamente, esse bug se tornou um alvo atraente para corrigir o erro, embora seja melhor que eu descubra isso antes da versão 0.8.0. Comecei a pesquisar a falha e confirmei a observação do merrp de que ele só funciona em hardware. Em todos os emuladores que tentei, o jogo ficou com uma tela preta. Mas o merrp me informou que fica travando a leitura da memória inválida em um loop e percebi que provavelmente não conseguiria corrigir o erro no futuro próximo. Este é novamente o mesmo bug.

Dessa vez, aprender sobre as funções de loop me deu uma vantagem. Graças ao projeto de descompilação do pokeemerald, eu poderia facilmente fazer alterações direcionadas na função para tentar descobrir como ela conseguiu sair do circuito. Uma versão simplificada desse loop é mais ou menos assim:

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

O loop executa uma tarefa bastante simples. Existe uma tabela bidimensional de valores. Em cada linha desta tabela de colunas, o typeloop primeiro tenta determinar se o valor é um determinado valor sentinela. Nesse caso, o loop termina. Caso contrário, aplica uma máscara ao valor e verifica se é maior que o valor que está sendo verificado. Caso contrário, diminui o ciclo. Em um caso específico de falha, o valor typevai além dos limites da tabela, o que leva à aparência de um ponteiro inválido. Isso significa que quando você tenta acessariPara este elemento desta coluna inexistente, sempre acessaremos a memória inválida. Embora o deslocamento da tabela aumente a cada iteração do loop antes de retornar à memória real, ele pode precisar de centenas de milhões de repetições. Portanto, é óbvio que ele não faz. Então, como um programa sai de um loop?

Para investigar isso, mudei o ciclo e observei o que aconteceria se eu apenas interrompesse instantaneamente o ciclo. Tudo acabou sendo muito simples: nesse momento, o ACE trabalhava tanto no hardware quanto no emulador, e nada pendia. Então, em vez disso, tentei definir a cor da tela para o valor que o programa lê quando sai do loop e congela para que a cor não mude. Eu recompilei o código e o executei em um GBA real. Após alguns segundos de congelamento em uma tela preta, tornou-se um lindo tom azul.

MUITO AZUL

Mas o emulador ainda estava pendurado em uma tela preta. Que valor ele lerá se ler o valor recebido anteriormente? Em vez disso, tornou-se um turquesa escuro.

Fu.

Ou seja, o programa, antes de conseguir sair do ciclo, certamente o passou pelo menos uma vez. Descobriu-se também que o tempo necessário para escapar do ciclo com ferro varia. Isso geralmente levava 2 a 30 segundos. O que está acontecendo?

Nova teoria de trabalho

Então notei a diferença entre a ROM de teste e o Pokémon Emerald quando ele travou. Pokémon tocou música. O Sonic Pinball Party também tocou música. Hello Kitty não tocou música, mas me deu uma ideia. O que acontece se ocorrer uma interrupção entre a pré-busca e o carregamento de dados? O programa inicia a pré-busca do vetor de interrupção antes de acessar a memória inválida? Criei rapidamente um layout para essa situação no mGBA, liguei as interrupções na ROM de teste e, é claro, saiu do circuito. Depois, tentei o mesmo ROM de teste no hardware e ... ele não saiu do circuito. E assim surgiu a teoria. No final, eu percebi uma coisa. Tenho certeza de que você notou um asterisco acima. Portanto, pode haver um evento entre pré-buscar e acessar a memória,mas somente se, entre a pré-busca e o acesso à memória inválida, o barramento de memória enviar uma solicitação não à CPU, mas a outra coisa.

Eu disse que o barramento de memória é controlado pela CPU. Na maioria das vezes, isso é verdade, mas há outros equipamentos importantes que também têm acesso ao barramento de memória ignorando o processador. Esse processo é chamado de acesso direto à memória . Eu falei sobre DMA em um artigo anterior , agora não vou entrar nos princípios de seu trabalho. Se você reler o artigo, poderá notar que eu disse que a CPU principal faz uma pausa enquanto o DMA está em execução. Isso significa que enquanto o DMA estiver em execução, o valor no barramento será agora o último acesso à memória do DMA. Isso é importante principalmente se o DMA for além da memória real para uma região inválida; no entanto, duplica o último bom valor.

Há muito se sabe que, se você carregar memória inválida no DMA, obterá o último valor do DMA, mas eu o implementei no mGBA por um longo tempo e já o esqueci. Quando vi isso no código de acesso à memória inválida ao estudar o bug, algo clicou na minha cabeça. E se o valor de DMA permanecer no barramento por uma instrução? Se a primeira instrução após o DMA terminar de carregar a memória inválida antes de obter o próximo valor, em teoria, isso deve levar ao recarregamento do valor do DMA. Além disso, a reprodução de música no GBA normalmente usa DMA para transmitir a saída de áudio. Para a implementação correta disso, é necessário um emulador preciso de tato que possa bloquear a CPU no meio da execução da instrução, entre o início da instrução e o acesso à memória, e a emulação de console GBA no emulador mGBA não é precisa.E isso é algo para mim.recorda . Felizmente, consegui contornar esse problema. A solução é imperfeita, mas agora posso comparar o endereço de CPU esperado para a instrução após o DMA com o endereço de CPU atual para uma carga inválida e usar um único endereço em vez do valor pré-selecionado para esse valor de DMA.

A tão esperada decisão

Liguei as operações de DMA para o H-blank na ROM de teste e as sincronizei com o V-blank para que os tempos fossem estáveis, executei no hardware e ... desta vez funcionou! A ROM de teste constantemente saía do loop após o mesmo número de iterações quando o valor de DMA era lido no barramento. Eu tinha razão! Para a implementação correta disso no mGBA, foram necessárias várias tentativas, mas agora o programa sai do ciclo com os mesmos resultados que no hardware. Finalmente consegui um tom de azul no mGBA. Olá Kitty foi inicializado. A economia no Sonic Pinball Party ganhou.

Eu fiz isso.

Este foi provavelmente o tempo mais longo que passei em um único bug. Durante três anos, investi tanto tempo na depuração que perdi a conta e tenho certeza de que outros desenvolvedores também enfrentaram situações semelhantes em seus emuladores. Sem essa percepção, poderia ter me levado mais um ano, ou até mais, mas a tela preta, na qual nada aconteceu exceto a reprodução de música, tornou-se o dominó que levou ao colapso de todo o problema.

Agora que a solução foi encontrada, ela pode ser implementada em outros emuladores de GBA, encerrando esse bug. O bug será corrigido no mGBA 0.9.0, que, espero, será lançado este ano e já foi corrigido nas versões de teste. Você pode finalmente jogar a coleção Hello Kitty: Miracle Fashion Maker. A menos que, claro, você deseje, não cabe a mim julgá-lo.

Se você tentar executar a memória que não possui permissões de execução, isso é chamado de cancelamento de pré-busca.
DACS (abreviação de Debugging and Communication System) faz parte do kit de desenvolvimento GBA.
Esses ciclos inativos durante a leitura do barramento às vezes são chamados de estados de espera.