Coisas estranhas que aprendi ao escrever um emulador x86

• Ao reescrever em C++ um emulador de CPU para Time Travel Debugging, ficou claro que no x86/amd64 até o mesmo comportamento precisa ser tratado de forma diferente dependendo da codificação, dos prefixos e do modo de execução
• int 3 tem a codificação de byte único CC, há formas curtas como ADD EAX, imm e representações alternativas como prefixos REX sem efeito, todas com impacto em desempenho e depuração
• INC/DEC, CMPXCHG8B/CMPXCHG16B e instruções de shift/rotate tratam flags de um jeito diferente do que a intuição sugere, o que facilita a introdução de bugs no emulador
• O shift count não é aplicado diretamente no tamanho do operando, e sim mascarado; por isso shr eax,20h não zera um registrador de 32 bits, mas mantém o valor
• Segmentos ainda são usados no acesso ao TEB no Windows de 32 e 64 bits, e as diferenças de significado de FS/GS e de como o base é determinado afetam diretamente a implementação de disassemblers e emuladores

---

Reescrevendo o emulador de TTD revelou as regras detalhadas do x86

• Um dos componentes do Time Travel Debugging é um emulador de CPU que registra toda a execução do processo no nível de instrução
• O emulador da primeira versão, o iDNA, era escrito quase todo em assembly e era rápido, mas difícil de manter e expandir
• Na segunda versão, a parte de emulação e depois a maior parte do restante também foi reescrita em C++, com a meta de manter boa parte do desempenho da versão em assembly e ao mesmo tempo ter uma base de código mais fácil de administrar
• Para criar um emulador de CPU, é preciso reproduzir sem falhas os detalhes do comportamento da CPU, e até regras familiares para quem já conhece x86 acabam precisando ser verificadas de novo na implementação real

Codificações x86 que expressam a mesma instrução de várias formas

• No x86, a mesma instrução pode ser representada por várias sequências de bytes
• int 3 pode ser codificada como CD 03, mas também como o byte único CC
  • Como ela é usada como breakpoint de software, isso permite colocar um breakpoint até na posição de uma instrução no fim de uma página de memória cuja página seguinte não está mapeada
• Também existem codificações alternativas para encurtar casos comuns
  • add eax, imm pode ser representada de forma mais curta como 05cccccccc
  • Para somar o mesmo valor em ECX, é preciso 1 byte a mais, como em 81c1cccccccc
• O fato de EAX ser chamado de “Accumulator register” não é só convenção: isso gera diferenças reais de codificação, e instruções mais curtas podem melhorar o desempenho ao reduzir os dados que precisam ser trazidos da memória principal e o uso do cache de instruções
• Compiladores podem aproveitar essas codificações curtas quando possível

Prefixos e o limite de 15 bytes por instrução

• Instruções x86 podem ter bytes de prefixo que alteram seu comportamento
• O prefixo REX, comum em código de 64 bits, é usado para acessar uma faixa maior de registradores do que no código de 32 bits
• A CPU também aceita prefixos REX sem efeito
  • 4004cc é uma forma com um byte REX antes de add al,0CCh, mas nesse caso o REX não produz efeito algum
  • Mesmo com dois prefixos REX seguidos, a CPU consegue executar a instrução, e vários disassemblers, incluindo o WinDbg, podem se confundir com isso
• Em CPUs compatíveis com x86, o tamanho máximo da instrução atual tem limite rígido de 15 bytes
  • Instruções com mais de 15 bytes são tratadas como inválidas e geram exceção
  • CPUs antigas também têm outras restrições sobre prefixos, e alguns prefixos, como LOCK, têm condições de uso ainda mais rígidas

Interpretação que muda conforme tamanho de endereço e modo

• O prefixo Address override pode fazer o modo de 64 bits referenciar endereços de 32 bits
  • 488d0424 é lea rax,[rsp]
  • 67488d0424 vira lea rax,[esp] por causa do prefixo 0x67
• Em código de 32 bits, o Address override muda o modo de endereçamento para endereços de 16 bits
• A mesma sequência de bytes só pode ser disassemblada ou interpretada corretamente se forem conhecidos o tamanho padrão de operando e o tamanho de endereço do segmento de código
  • 8b0424 no modo de 32 bits é mov eax,dword ptr [esp]
  • 8b0424 no modo de 64 bits é mov eax,dword ptr [rsp]
• A faixa 40~4F, antes usada para INC reg e DEC reg no x86, é usada no x64 como REX prefix bytes
  • No modo de 32 bits, 48 03 04 24 é interpretado como duas instruções: dec eax e add eax,dword ptr [esp]
  • No modo de 64 bits, 48030424 é uma única instrução: add rax,qword ptr [rsp]
• Os projetistas do AMD64 reutilizaram esse amplo espaço de codificação de INC/DEC como novos prefixos para ampliar o conjunto de registradores no modo de 64 bits, já que essas instruções já tinham outras codificações que suportavam registradores e memória

A armadilha do INC reg no modo de 64 bits no WinDbg

• O WinDbg sempre monta instruções como se estivesse em modo de 32 bits, então tentar montar INC reg em código de 64 bits pode gerar um resultado diferente do pretendido
• No exemplo, inc eax não vira uma instrução real de incremento, e sim um prefixo REX inútil que modifica a instrução seguinte
• Como resultado, a sequência de bytes é interpretada não como inc, mas como um prefixo antes de uma instrução jmp

Exceções no comportamento das flags

• INC EAX parece ser parecido com ADD EAX, 1, mas não é exatamente a mesma coisa
  • ADD atualiza a carry flag
  • INC não atualiza a carry flag
• Durante a implementação do emulador TTD, essa diferença foi implementada de forma errada no começo e o erro foi encontrado com testes unitários
• A maioria das operações aritméticas e lógicas define as flags overflow, sign, zero, auxiliary carry, parity e carry
• CMPXCHG também define essas flags, mas CMPXCHG8B e CMPXCHG16B modificam apenas a zero flag
• Algumas instruções deixam parte das flags em estado indefinido
  • Instruções de shift e rotate deixam a overflow flag indefinida quando o shift amount é maior que 1
  • O comportamento real de flags indefinidas está ligado à implementação interna da operação de shift e pode variar entre arquiteturas
  • Há relatos de que CPUs da linha Atom executam bit shift na ALU de um jeito mais barato e mais lento, fazendo com que os valores de flags indefinidas sejam diferentes, mas isso não foi testado diretamente

Máscara no count das instruções de shift

• 66c1e810 é shr ax,10h e faz um shift à direita de 16 bits em AX
  • Como AX é um registrador de 16 bits, o resultado vira 0
• c1e820 é shr eax,20h, e na superfície parece uma instrução que desloca EAX 32 bits para a direita
• Na prática, o valor de EAX não muda
  • Segundo o Intel SDM, o count é mascarado com 1Fh, então só os 5 bits inferiores da rotação são usados
  • Com o prefixo REX.W, a máscara vira 3Fh, e o shift máximo passa a ser de 63 bits
• Em uma entrevista da Microsoft, esse comportamento apareceu numa pergunta sobre “todas as formas de limpar um registrador de 32 bits com uma única instrução”
  • O entrevistador achava que seria possível usando shift, mas a resposta foi que isso não dá para fazer em um registrador de 32 bits

Segmentos que ainda sobrevivem em código de 32 e 64 bits

• Memória segmentada pode parecer um resquício do código de 16 bits, mas ainda tem efeito real em código de 32 e 64 bits
• A maioria dos sistemas operacionais usa um modelo de memória quase flat e deixa o base address dos segmentos em 0, então isso normalmente passa despercebido
  • No modo de 64 bits, a CPU sempre trata o base dos segmentos CS, DS, ES e SS como 0
• Como exceção, thread local storage usa registradores de segmento extras como FS e GS
• Como correção, o base dos segmentos FS/GS também pode ser lido em código sem privilégio com as instruções rdfsbase, wrfsbase, rdgsbase e wrgsbase
  • Essas instruções estão disponíveis desde o Ivy Bridge, ou seja, desde 2012

Acesso ao TEB no Windows com FS/GS

• No Windows, FS e GS são usados para referenciar o TEB (Thread Execution Block)
• A estrutura TEB tem um self pointer que aponta para o endereço flat do início da estrutura, e esse endereço também é o base do respectivo segmento
• Em processos de 32 bits, o TEB fica em FS
  • GetLastError pega TEB.NtTib.Self em fs:[00000018h] e depois lê LastErrorValue em [eax+34h]
• Em processos de 64 bits, o TEB fica em GS
  • GetLastError lê o ponteiro em gs:[30h] e depois pega o valor em [rax+68h]
• Processos de 32 bits rodando em um SO de 64 bits têm tanto um TEB de 32 bits quanto um TEB de 64 bits, e há contextos úteis em que é preciso acessar ambos, como no código WOW de 64 bits executado dentro do processo de 32 bits

A forma de determinar o base do segmento também muda com o modo

• A configuração da CPU que determina o base address de FS e GS é diferente entre os modos de 32 e 64 bits
• No modo de 32 bits, o valor real do registrador de segmento aponta para um segment descriptor definido na Global Descriptor Table e na Local Descriptor Table
• No modo de 64 bits, o base é controlado por dois MSRs
  • FS Base, chamado de IA32_FS_BASE no Intel SDM
  • GS Base, chamado de IA32_GS_BASE no Intel SDM
• Por causa dessa estrutura, no modo de 64 bits o valor real dos registradores FS e GS em si não importa
  • O que importa é o prefixo de segment override
• Ao depurar um processo de 32 bits no WinDbg, é possível usar o valor do registrador FS para fazer dump do conteúdo do “FS segment”
• Em processos de 64 bits, isso não funciona da mesma forma, e o prefixo de segment override passa a ser mais relevante que o valor do segmento

Lições práticas para quem implementa emuladores

• Criar um emulador x86 exige tratar com precisão o comportamento real da CPU, incluindo codificação de instruções, prefixos, flags, shift count e segmentos
• Muitas dessas regras quase não têm utilidade para escrever código comum, mas viram exigências diretas na implementação de um emulador
• Houve muito aprendizado por tentativa e erro e por mentoria, e o texto também cita Darek Mihocka, que tem longa experiência com emuladores, além do emulators.com
• Para quem se interessa por otimização em x86 e comportamento de baixo nível, os materiais do site do Agner Fog são úteis

[GN⁺]

Comentários do Hacker News

• De quebra, BSF/BSR também têm uma esquisitice. O Intel SDM diz que, se a entrada for 0, o valor de destino fica indefinido, mas a AMD documenta que, nesse caso, o destino não é modificado
  No entanto, a glibc usa diretamente esse fato não documentado de que, na Intel, o destino também não é modificado [1]. Por causa disso, demorei bastante para encontrar a causa do problema no meu tradutor binário
  Além disso, TZCNT/LZCNT são codificações de BSF/BSR com o prefixo F3, mas em processadores antigos que não suportam essa extensão o prefixo é silenciosamente ignorado. Então o mesmo código se comporta de forma diferente dependendo da CPU, mas pelo menos isso está documentado
  Nas codificações, as pessoas costumam reclamar muito dos prefixos, mas pessoalmente não acho que isso seja o pior. Isso é bem conhecido e até certo ponto documentado. Existem esquisitices piores. Por exemplo, os bits de extensão REX/VEX/EVEX.RXB são ignorados se não se aplicarem, mas nos registradores de máscara k0-k7 eles geram #UD. Só que, quando o registrador é codificado em ModRM.rm, os bits de extensão voltam a ser ignorados
  APX eleva o nível da esquisitice em mais um degrau. O prefixo REX2 consegue codificar registradores de propósito geral r16-r31, mas não xmm16-xmm31, e o prefixo EVEX tem vários layouts dependendo do opcode, com bits de extensão usados para registradores variando conforme o tipo de registrador. Registradores XMM usam X3:B3:rm e V4:X3:idx, enquanto registradores de propósito geral usam B4:B3:rm e X4:X3:idx. Já se passou um ano e ainda não consegui terminar o decodificador de APX, então não posso dar a lista completa
  [1]: https://sourceware.org/bugzilla/show_bug.cgi?id=31748

  • Há um ano, venho reescrevendo aos poucos o decodificador x86 do QEMU. No começo isso era necessário para adicionar suporte a AVX, mas agora faltam só alguns opcodes para reescrever e, depois disso, o suporte a APX provavelmente não será tão difícil
    Minha ideia para o EVEX é preservar os bits brutos até ler o opcode e identificar a classe EVEX. Ou seja, o plano é mantê-los até antes do valor imediato, provavelmente até antes do ModRM
    Meu decodificador é basicamente baseado nas tabelas do manual, e o código no geral está razoável. A indentação não é exagerada e, na maior parte, as etapas são separadas ou fáceis de identificar. Como a saída é código JIT, não precisa ser extremamente eficiente; ser legível está ótimo. Também não é onde a maior parte do tempo é gasta
    Mesmo assim, há vários casos em que o manual está errado ou não conta a história completa. As tabelas também não são atualizadas há anos e, por exemplo, nem incluem instruções de registrador K. Daqui para frente, parece que vai haver mais trabalho manual
    O comentário no topo explica um pouco a situação: https://github.com/qemu/qemu/blob/59084feb256c617063e0dbe7e6...
    Como mencionei acima, ainda restam algumas instruções tratadas pelo código antigo, especialmente BT/BTS/BTR/BTC. O código já foi escrito, mas ainda não foi mesclado
  • Há outra esquisitice da era 486 e Pentium. BSWAP EAX converte little-endian em big-endian e vice-versa, e desde o início já era uma instrução de 32 bits
    Só que existe o prefixo 0x66, que alterna entre modos de 16 e 32 bits. Quando ele é aplicado a BSWAP EAX, acontece uma bizarrice indefinida
    Em algumas arquiteturas de CPU, como na diferença entre Intel e AMD, o prefixo era simplesmente ignorado; em outras, acontecia o que eu chamo de “troca interna”. Por exemplo, entre os quatro bytes armazenados em EAX, os bytes 1 e 2 trocavam de lugar
    0x11223344 virava 0x11332244
  • Dá arrepios pensar que toda essa lógica precisa funcionar corretamente em silício e, além disso, rápido
    Antigamente, x86 era o fosso defensivo da Intel, mas agora parece mais um peso de pesadelo que ela precisa carregar
  • A combinação de semântica e codificação de LZCNT parece gol contra. Ela é codificada como uma instrução BSR com um prefixo que é ignorado no legado, e para entradas diferentes de zero o valor de retorno é o tamanho do operando menos o valor de retorno da versão legada
    Existe uma função clz(), mas, se LZCNT fosse simplesmente um BSR com semântica diferente apenas para entrada zero, o custo de adicionar uma subtração na implementação para obter compatibilidade provavelmente teria sido pequeno
  • Não conheço bem essa área, mas seria interessante ligar uma interface JTAG a uma CPU x86, executá-la instrução por instrução e registrar os valores de todos os registradores
    Aí daria para executar o mesmo programa numa CPU emulada e verificar, a cada instrução, se o estado bate, testando se o emulador reproduz o hardware perfeitamente

• Pessoa muito foda. Escrever assembly parece simples, e eu também gosto da estética vertical
  A experiência mais próxima que tive de algo como o trabalho do OP foi quando tentei explicar pilha para um amigo que mexe com JS e acabamos fazendo juntos uma mini VM com uma ISA pequena: https://gist.github.com/darighost/2d880fe27510e0c90f75680bfe...
  Eu poderia ter ido mais fundo, e queria ter ido, mas aí acho que teria saído do objetivo educacional original. Acho que vou mandar mensagem para ele para ver se ainda topa estudar junto. Ele ganha muito dinheiro fazendo um desenvolvimento web muito legal e não tem tempo para se aprofundar, enquanto eu estou desempregado e tenho quase um oceano infinito de tempo e energia, então não é fácil

  • Também pode ser uma boa aproveitar isso para aprender JS com seu amigo
  • Como alguém sem formação na área, esse código foi uma boa porta de entrada para começar a entender o funcionamento interno, e acabou levando a uma jornada bem legal e difícil com assembly. Pretendo me aprofundar mais

• Vale a pena ver Justine Tunney e aquele emulador dela. https://justine.lol/blinkenlights/
  A documentação faz um excelente passeio por como a CPU funciona

  • Impressionante. Sempre me deixa admirado
  • Lembro do nome Tunney daquela época, por volta de 2014, em que ela vivia sem teto, andando de um lado para outro e postando bobagens no Twitter sobre o Occupy

• A discussão anterior está aqui: https://news.ycombinator.com/item?id=34636699
  Não dá para acreditar que já se passaram 16 meses. O tempo voa mesmo

• Não concordo muito com a ideia de que “escrever um emulador de CPU é a melhor forma de realmente entender como uma CPU funciona”
  A melhor forma é construir uma CPU no nível de portas lógicas, como se faz em um bom curso de ciência da computação. Foi muito divertido construir um ARM reduzido do zero

  • Acho que os dois são úteis. Só que projetar uma CPU moderna no nível de portas lógicas está fora do alcance da maioria das pessoas, e existe um grande abismo entre a CPU que se projeta na universidade e uma CPU que executa código real
    Construir um emulador de CPU moderna é um desafio mais acessível e, mesmo que só parte funcione, ainda tem muito valor educacional
  • Concordo. Até um processador básico com microcódigo, pipeline, superscalar, predição de desvios, caches L1 de dados/instruções e controlador de cache L2 write-back já não é nada trivial
    A maioria dos engenheiros de software tem uma compreensão incompleta de hazards de dados, invalidação de cache e stalls de pipeline
  • Acho que os dois estão certos. Montar chips 74xx é extremamente satisfatório, e dá para desenvolver uma intuição sobre os aspectos elétricos e os compromissos internos
    Mas, quando você começa a tentar construir assim uma CPU que queira usar para algo significativo, o interesse por esses detalhes começa a cair. Nessa hora, a complexidade do comportamento e da especificação passa a ser mais interessante, e a abordagem do emulador é mais manejável e cobre mais tipos de comportamento
  • Estou seguindo o Nand2Tetris e passando pelo processo de montar tudo no nível de portas lógicas; acabei de terminar o capítulo do emulador de VM, e levou muito tempo. Agora vou para a etapa de compilação
  • Por outro lado, numa CPU de nível de portas lógicas você realmente vai implementar até segmentação de memória? Acho que os dois passos são necessários para uma compreensão real: primeiro construir uma CPU funcional e depois emular uma CPU real, inclusive com os defeitos dela

• Já escrevi emuladores rápidos para umas 12 arquiteturas que não eram brinquedo, e também fiz alguns tradutores JIT, mas x86 ainda me dá PTSD. Nunca vi uma arquitetura tão bagunçada. Ela tem história e tem seus motivos, mas ainda assim é pesado

  • Estudar a arquitetura x86 é como estudar uma língua com muitas irregularidades, órgãos vestigiais e sistemas gramaticais concorrentes, como o francês. Outras arquiteturas, como RISC-V e ARMv8, são muito mais consistentes
  • Se você diz “nunca vi uma arquitetura mais bagunçada do que essa”, então existe Itanium. Toda vez que abro o manual, sempre descubro mais alguma coisa que me faz pensar “mas o que estavam pensando?” sem nem precisar procurar muito
  • Totalmente identificável. Talvez eu devesse ter começado por isso desde o início

• Recentemente implementei boa parte de um decodificador x86-64 como projeto paralelo [1], e fiquei bem surpreso com o quanto isso ficou mais complexo hoje em dia. Para os meus objetivos, Sandpile.org [2] foi realmente útil
  [1] Mais precisamente, uma versão x86-64 do disfilter de Fabian Giesen feita para outro projeto paralelo ainda não publicado: https://gist.github.com/lifthrasiir/df47509caac2f065032ef72e...
  [2] https://sandpile.org/

• O disassembler 68k que fiz na faculdade foi como o momento em que o Neo diz “eu sei kung fu”. Era o elo que faltava para ir de linguagens de alto nível até transistores e depois voltar a raciocinar sobre o código no sentido inverso
  Escrever um emulador completo parece que seria uma ordem de grandeza mais eficaz do que isso. Ótimo texto

  • Acho que escrever um emulador de ISA na verdade não ajuda muito a entender como CPUs supersescalares modernas funcionam. Quase tudo que importa ali são otimizações internas escondidas

• Pelo visto minha memória estava errada. Eu lembrava que as variantes de salsa20 e o código de máquina estavam originalmente em cryp.to, mas o site do Dan Bernstein era https://cr.yp.to/
  Na época em que, em uma startup, estávamos avaliando criptografia de dados em repouso, criptografia de streaming e afins, a página do Dan tinha várias implementações por chipset de destino e conjunto de instruções. Eram coisas compiladas de forma cruzada a partir da notação em assembly dele
  Foi interessante usar a VM para ver quais conjuntos de instruções eram suportados no começo e meados dos anos 2000. Durante os testes, às vezes surgiam problemas porque a VM dizia suportar algo, mas a implementação não era totalmente compatível

  • Você quer dizer o site do Dan Berstain... espera aí

• É curioso ver tanta gente aqui falando de como assembly x86 é doloroso em comparação com RISC. Eu tenho exatamente o problema oposto quando separo código de volta em arquivos objeto
  Para esse uso, analisar x86 é realmente fácil, e MIPS foi um pesadelo. Isso porque o que mais me importa são as referências a código e dados. No x86 existem imediatos do tamanho de ponteiro, enquanto no MIPS há pares de relocação HI16/LO16, o que se mistura com grafo de uso de registradores, fluxo de código e instruções com delay slot de desvio, gerando todo tipo de problema
  Isso não significa que eu esteja elogiando x86

  • Exato. x86 é esquisito, mas instruções de tamanho variável na verdade ficam agradáveis de ver e fáceis de entender depois que você as desmembra em texto. O problema é que isso não é seguro, porque dá para esconder outras instruções no meio de uma instrução
    A maior lição ao aprender comparando assembly x86 com C é que signed/unsigned deixa de ser propriedade do tipo e passa a ser propriedade da operação
    Seria bom conseguir aproveitar os flags; em algumas arquiteturas, como PPC ou armv7, isso é mais fácil, mas no x86 os flags são sobrescritos com facilidade demais, então é difícil demais aproveitar os valores