Cosas raras que aprendí al escribir un emulador x86

• Al reescribir en C++ un emulador de CPU para Time Travel Debugging, x86/amd64 obligó a manejar el mismo comportamiento de forma distinta según la codificación, los prefijos y el modo de ejecución
• Hay muchas representaciones alternativas que afectan el rendimiento y la depuración, como la codificación de un solo byte CC de int 3, la forma corta de ADD EAX, imm o los prefijos REX sin efecto
• Instrucciones como INC/DEC, CMPXCHG8B/CMPXCHG16B y shift/rotate manejan las flags de maneras poco intuitivas, lo que puede llevar fácilmente a bugs en el emulador
• El shift count no se aplica tal cual según el tamaño del operando, sino que se enmascara; por eso shr eax,20h no pone en cero un registro de 32 bits, sino que mantiene el valor
• Los segmentos todavía se usan para acceder al TEB en Windows de 32 y 64 bits, y las diferencias en el significado de FS/GS y en cómo se determina la base afectan directamente la implementación de desensambladores y emuladores

---

Reglas detalladas de x86 reveladas al reescribir el emulador de TTD

• Un componente de Time Travel Debugging es un emulador de CPU que registra toda la ejecución de un proceso a nivel de instrucciones
• El emulador de la primera versión, iDNA, estaba escrito casi por completo en ensamblador y era rápido, pero era difícil de mantener y extender
• En la segunda versión se reescribió en C++ la parte de emulación y, después, la mayor parte del resto, con el objetivo de tener una base de código más manejable manteniendo gran parte del rendimiento de la versión en ensamblador
• Para crear un emulador de CPU hay que reproducir todos los detalles del comportamiento del CPU; incluso reglas familiares para quienes tienen experiencia con x86 se vuelven a verificar durante la implementación real

Codificaciones x86 que expresan la misma instrucción de varias formas

• x86 puede expresar la misma instrucción con varias secuencias de bytes
• int 3 también se codifica como CD 03, pero puede codificarse como CC de un solo byte
  • Como se usa para breakpoints de software, permite poner un breakpoint incluso en la posición de una instrucción al final de una página de memoria cuando la página siguiente no está mapeada
• También hay codificaciones alternativas para hacer más cortos los casos comunes
  • add eax, imm puede expresarse de forma corta como 05cccccccc
  • Para sumar el mismo valor a ECX, se necesita 1 byte más, como en 81c1cccccccc
• Que EAX se llame “Accumulator register” no es solo una convención: también produce una diferencia real de codificación, y las instrucciones cortas pueden favorecer el rendimiento al reducir los datos que hay que mover desde la memoria principal y el uso de la caché de instrucciones
• Los compiladores pueden aprovechar estas codificaciones cortas cuando es posible

Prefijos y límite de longitud de instrucción de 15 bytes

• Las instrucciones x86 pueden tener bytes de prefijo que modifican su comportamiento
• El prefijo REX, común en código de 64 bits, se usa para acceder a un rango más amplio de registros que en código de 32 bits
• El CPU acepta incluso prefijos REX que no tienen efecto
  • 4004cc es una forma con un byte REX delante de add al,0CCh de 8 bits, pero en este caso REX no tiene ningún efecto
  • Aunque se agreguen dos prefijos REX, el CPU puede ejecutarlo, y varios desensambladores, incluido WinDbg, pueden confundirse con esto
• En CPUs compatibles con x86, la longitud actual de una instrucción tiene un límite estricto de 15 bytes
  • Las instrucciones de más de 15 bytes se consideran inválidas y generan una excepción
  • En CPUs antiguas también hay otros límites para los prefijos, y algunos prefijos, como LOCK, tienen condiciones más estrictas para poder usarse

Interpretación que cambia según el tamaño de dirección y el modo

• El prefijo Address override puede hacer que en modo de 64 bits se referencie una dirección de 32 bits
  • 488d0424 es lea rax,[rsp]
  • 67488d0424 es lea rax,[esp] por el prefijo 0x67
• En código de 32 bits, Address override cambia el modo de dirección a una dirección de 16 bits
• Incluso la misma secuencia de bytes requiere conocer el tamaño de operando y de dirección por defecto del segmento de código para desensamblarse o interpretarse correctamente
  • 8b0424 en modo de 32 bits es mov eax,dword ptr [esp]
  • 8b0424 en modo de 64 bits es mov eax,dword ptr [rsp]
• El rango 40~4F, usado en x86 para INC reg y DEC reg, se usa en x64 como bytes de prefijo REX
  • En modo de 32 bits, 48 03 04 24 se interpreta como dos instrucciones: dec eax y add eax,dword ptr [esp]
  • En modo de 64 bits, 48030424 se interpreta como una sola instrucción: add rax,qword ptr [rsp]
• Los diseñadores de AMD64 usaron el amplio espacio de codificación de INC/DEC para un nuevo prefijo que extendiera el conjunto de registros en modo de 64 bits, y esas instrucciones ya tenían otra codificación que admitía tanto registros como memoria

La trampa de WinDbg y INC reg en modo de 64 bits

• WinDbg siempre ensambla instrucciones como si fueran de modo de 32 bits, por lo que al intentar ensamblar INC reg en código de 64 bits se puede obtener un resultado distinto del esperado
• En el ejemplo, inc eax no se convierte en una instrucción real de incremento, sino en un prefijo REX inútil que modifica la siguiente instrucción
• Como resultado, esa secuencia de bytes se interpreta no como inc, sino como un prefijo antes de la instrucción jmp

Excepciones en el comportamiento de las flags

• INC EAX se parece a ADD EAX, 1, pero no es exactamente lo mismo
  • ADD actualiza la carry flag
  • INC no actualiza la carry flag
• Durante la implementación del emulador de TTD, esta diferencia se implementó mal al principio y se detectó con pruebas unitarias
• La mayoría de las operaciones aritméticas y lógicas establecen las flags de overflow, sign, zero, auxiliary carry, parity y carry
• CMPXCHG también establece esas flags, pero CMPXCHG8B y CMPXCHG16B modifican solo la zero flag
• Algunas instrucciones dejan parte de las flags en estado indefinido
  • Las instrucciones de shift y rotate dejan la overflow flag en estado indefinido si el shift amount es mayor que 1
  • El comportamiento real de las flags indefinidas está relacionado con la implementación interna de la operación de shift y puede variar según la arquitectura
  • Se dice que los CPUs de la familia Atom ejecutan bit shifts en la ALU de una forma más barata y lenta, lo que cambia los valores de las flags indefinidas, pero no se probó directamente

Enmascaramiento del count en las instrucciones de shift

• 66c1e810 es shr ax,10h, que desplaza AX 16 bits a la derecha
  • Como AX es un registro de 16 bits, el resultado es 0
• c1e820 es shr eax,20h y, a simple vista, parece una instrucción que desplaza EAX 32 bits a la derecha
• En realidad, el valor de EAX no cambia
  • Según el Intel SDM, el count se enmascara con 1Fh y solo se usan los 5 bits bajos de la rotación
  • Si se usa el prefijo REX.W, la máscara pasa a ser 3Fh, por lo que el valor máximo de shift es 63 bits
• Este comportamiento llegó a ser un problema real en una entrevista de Microsoft donde se preguntó por “todas las formas de limpiar un registro de 32 bits con una sola instrucción”
  • El entrevistador pensaba que se podía usar shift, pero la respuesta fue que no era posible para un registro de 32 bits

Segmentos que siguen vivos en código de 32 y 64 bits

• La memoria segmentada puede parecer una reliquia del código de 16 bits, pero todavía tiene efectos reales en código de 32 y 64 bits
• La mayoría de los sistemas operativos usan un modelo de memoria casi plano y ponen la base address de los segmentos en 0, por lo que normalmente no se nota
  • En modo de 64 bits, el CPU siempre trata la base de los segmentos CS, DS, ES y SS como 0
• Como excepción, para thread local storage se usan extra segment registers como FS o GS
• Como corrección, la base de los segmentos FS/GS también puede leerse desde código sin privilegios con las instrucciones rdfsbase, wrfsbase, rdgsbase y wrgsbase
  • Estas instrucciones están disponibles desde Ivy Bridge, es decir, desde 2012

Acceso al TEB de Windows y FS/GS

• En Windows, FS y GS se usan para referenciar el TEB (Thread Execution Block)
• La estructura TEB tiene un puntero self que apunta a la flat address del inicio de la estructura, y esa dirección también es la base del segmento correspondiente
• En procesos de 32 bits, el TEB se ubica con FS
  • GetLastError obtiene TEB.NtTib.Self desde fs:[00000018h] y luego lee LastErrorValue desde [eax+34h]
• En procesos de 64 bits, el TEB se ubica con GS
  • GetLastError lee el puntero desde gs:[30h] y toma el valor desde [rax+68h]
• Los procesos de 32 bits que se ejecutan en un OS de 64 bits tienen tanto un TEB de 32 bits como uno de 64 bits, y hay contextos útiles en los que hay que acceder a ambos TEB, como código WOW de 64 bits ejecutándose dentro de un proceso de 32 bits

La forma de determinar la base del segmento también cambia según el modo

• La configuración del CPU que determina la base address de FS y GS difiere entre el modo de 32 bits y el de 64 bits
• En modo de 32 bits, el valor real del registro de segmento referencia un segment descriptor definido en la Global Descriptor Table y la Local Descriptor Table
• En modo de 64 bits, la base se controla con dos MSR
  • FS Base, IA32_FS_BASE en el Intel SDM
  • GS Base, IA32_GS_BASE en el Intel SDM
• Por esta estructura, en modo de 64 bits el valor real del registro FS o GS no importa en sí mismo
  • Lo importante es el prefijo segment override
• En WinDbg, al depurar procesos de 32 bits, se puede usar el valor del registro FS para hacer dump del contenido del “FS segment”
• En procesos de 64 bits, el mismo método no funciona; lo que importa es el prefijo segment override más que el valor del segmento

Lecciones prácticas para quienes implementan emuladores

• Al crear un emulador x86 hay que tratar con gran detalle el comportamiento real del CPU: codificación de instrucciones, prefijos, flags, shift count y segmentos
• Muchas de estas reglas casi no sirven para escribir código común, pero se vuelven requisitos directos al implementar un emulador
• Gran parte se aprendió mediante prueba y error y mentoría; también se menciona a Darek Mihocka, con experiencia en emuladores antiguos, y emulators.com
• Si te interesan la optimización x86 y el comportamiento de bajo nivel, los recursos de Agner Fog’s website son útiles

[GN⁺]

Comentarios de Hacker News

• Como extra, BSF/BSR también tienen una peculiaridad. El Intel SDM dice que, si la entrada es 0, el valor de destino queda indefinido, pero AMD documenta que en ese caso el destino no se modifica.
  Pero glibc usa tal cual el hecho no documentado de que, también en Intel, el destino no se modifica [1]. Por eso me tomó bastante tiempo encontrar la causa del problema en mi traductor binario.
  Además, TZCNT/LZCNT son codificaciones de BSF/BSR con el prefijo F3, pero en procesadores antiguos que no soportan esta extensión el prefijo se ignora silenciosamente. Así que el mismo código se comporta distinto según la CPU, aunque al menos eso sí está documentado.
  En las codificaciones, la gente suele quejarse de los prefijos, pero personalmente no creo que sean lo peor. Son bien conocidos y están documentados hasta cierto punto. Hay peculiaridades peores. Por ejemplo, los bits de extensión REX/VEX/EVEX.RXB se ignoran si no aplican, pero en los registros de máscara k0-k7 provocan #UD. Sin embargo, si el registro está codificado en ModRM.rm, los bits de extensión vuelven a ignorarse.
  APX lleva el nivel de rarezas un paso más allá. El prefijo REX2 puede codificar registros de propósito general r16-r31, pero no xmm16-xmm31; el prefijo EVEX tiene varios layouts según el opcode, y los bits de extensión usados para los registros también cambian según el tipo de registro. Los registros XMM usan X3:B3:rm y V4:X3:idx, mientras que los registros de propósito general usan B4:B3:rm y X4:X3:idx. Ya pasó un año y todavía no termino el decodificador APX, así que no puedo dar la lista completa.
  [1]: https://sourceware.org/bugzilla/show_bug.cgi?id=31748

  • Durante el último año estuve reescribiendo de a ratos el decodificador x86 de QEMU. Al principio era trabajo necesario para agregar soporte de AVX, pero ahora solo quedan unos pocos opcodes por reescribir, y después de eso creo que soportar APX no será demasiado difícil.
    Con EVEX pienso mantener los bits crudos hasta leer el opcode e identificar la clase EVEX. Es decir, el plan es conservarlos hasta antes del inmediato, quizá hasta antes de ModRM.
    Mi decodificador se basa en gran medida en las tablas del manual, y el código en general está bien. No tiene demasiada indentación y las etapas están mayormente separadas o son fáciles de identificar. Como la salida es código JIT, no necesita ser extremadamente eficiente; está bien que sea legible. Tampoco es donde se consume la mayor parte del tiempo.
    Aun así, hay varios casos en los que el manual está mal o no cuenta toda la historia. Las tablas tampoco se actualizan desde hace años; por ejemplo, ni siquiera están las instrucciones de registros K. Parece que de aquí en adelante habrá más trabajo manual.
    El comentario superior explica un poco la situación: https://github.com/qemu/qemu/blob/59084feb256c617063e0dbe7e6...
    Como dije arriba, todavía quedan algunas instrucciones que maneja el código viejo, en particular BT/BTS/BTR/BTC. Ya escribí el código, pero aún no lo he fusionado.
  • Hay otra rareza de la época de los 486 y Pentium. BSWAP EAX convierte entre little endian y big endian, y desde el principio fue una instrucción de 32 bits.
    Pero existe el prefijo 0x66, que alterna entre modos de 16 y 32 bits. Si se aplica a BSWAP EAX, pasan cosas extrañas e indefinidas.
    En algunas arquitecturas de CPU, como en las diferencias entre Intel y AMD, el prefijo simplemente se ignoraba; en otras hacía algo que yo llamo “intercambio interno”. Por ejemplo, de los cuatro bytes guardados en EAX, los bytes 1 y 2 se intercambian.
    0x11223344 se convierte en 0x11332244.
  • Marea pensar que toda esta lógica tiene que funcionar correctamente en silicio y, encima, rápido.
    Antes x86 era el foso defensivo de Intel, pero ahora parece una carga de pesadilla que tiene que arrastrar.
  • La combinación de semántica y codificación de LZCNT se siente como un autogol. Se codifica como una instrucción BSR con un prefijo que se ignora en legacy, y para entradas distintas de cero devuelve el tamaño del operando menos el valor devuelto por la versión legacy.
    Existe una función llamada clz(), pero si LZCNT hubiera sido simplemente BSR con una semántica distinta solo para la entrada 0, parece que hacer una resta adicional en la implementación para obtener compatibilidad habría sido un costo pequeño.
  • No conozco bien este campo, pero sería interesante conectar una interfaz JTAG a una CPU x86, ejecutar instrucción por instrucción y registrar todos los valores de los registros.
    Si ejecutas el mismo programa también en una CPU emulada y verificas que el estado coincida en cada instrucción, podrías probar si el emulador imita perfectamente al hardware.

• Es una persona genial. Escribir assembly se siente simple, y también me gusta su estética vertical.
  Lo más cercano que estuve a algo como el trabajo del OP fue cuando intenté hacer que un amigo que programa JS entendiera la pila y terminamos armando juntos una mini VM con una ISA pequeña: https://gist.github.com/darighost/2d880fe27510e0c90f75680bfe...
  Podríamos haber profundizado más, y a mí me habría gustado, pero creo que eso se habría alejado del objetivo educativo original. Debería escribirle para ver si todavía quiere estudiar conmigo. No es fácil: él gana mucho dinero haciendo desarrollo web muy bueno y no tiene tiempo para profundizar, mientras que yo estoy desempleado y tengo un mar casi infinito de tiempo y energía.

  • Eso también podría ser una buena excusa para que aprendas JS de tu amigo.
  • Como persona sin formación formal en el área, este código fue una buena puerta de entrada para empezar a entender cómo funcionan las cosas por dentro, y gracias a eso terminé en un viaje bastante genial y difícil por el assembly. Pienso seguir profundizando.

• Justine Tunney y su emulador también valen la pena. https://justine.lol/blinkenlights/
  La documentación ofrece un recorrido excelente sobre cómo funciona una CPU.

  • Increíble. Siempre logra impresionarme.
  • Recuerdo el nombre Tunney de alrededor de 2014, cuando vivía en la calle y andaba de un lado a otro diciendo tonterías en Twitter relacionadas con Occupy.

• La discusión anterior está aquí: https://news.ycombinator.com/item?id=34636699
  No puedo creer que ya hayan pasado 16 meses. El tiempo vuela de verdad

• No estoy muy de acuerdo con que “escribir un emulador de CPU sea la mejor forma de entender de verdad cómo funciona una CPU”
  La mejor forma es construir una CPU a nivel de compuertas, como se hace en una buena clase de ciencias de la computación. Fue muy divertido construir desde cero un ARM reducido

  • Creo que ambas cosas son útiles. Pero diseñar una CPU moderna a nivel de compuertas está fuera del alcance de la mayoría, y hay una gran brecha entre la CPU que se diseña en la universidad y una CPU que ejecuta código real
    Hacer un emulador de una CPU moderna es un desafío algo más accesible y, aunque solo funcione en parte, sigue teniendo mucho valor educativo
  • De acuerdo. Incluso un procesador básico con microcódigo, pipeline, superescalaridad, predicción de saltos, cachés L1 de datos/instrucciones y un controlador de caché L2 write-back no es poca cosa
    La mayoría de los ingenieros de software tienen una comprensión incompleta de los hazards de datos, la invalidación de caché y las detenciones del pipeline
  • Creo que ambas posturas son correctas. Conectar chips 74xx entre sí es tremendamente satisfactorio y te permite desarrollar intuición sobre el aspecto eléctrico y los compromisos internos
    Pero si empiezas a construir así una CPU que quieras usar para trabajo significativo, esos detalles empiezan a volverse menos interesantes. En ese punto, la complejidad del comportamiento y de la especificación se vuelve más interesante, y el enfoque del emulador es más manejable y permite cubrir más tipos de comportamiento
  • Estoy siguiendo Nand2Tetris y avanzando desde el nivel de compuertas; acabo de terminar el capítulo del emulador de VM y me tomó muchísimo tiempo. Ahora paso a la etapa de compilación
  • En sentido contrario, ¿de verdad vas a implementar incluso segmentación de memoria en una CPU a nivel de compuertas? Creo que para entender de verdad hacen falta ambas etapas: primero construir una CPU que funcione y luego emular una CPU real, incluidos sus defectos

• He escrito emuladores rápidos para unas 12 arquitecturas que no son de juguete, y también algunos traductores JIT, pero x86 todavía me da PTSD. Nunca vi una arquitectura tan sucia. Tiene historia y razones, pero aun así es terrible

  • Estudiar la arquitectura x86 se siente como estudiar un idioma con muchas irregularidades, órganos vestigiales y sistemas de sintaxis en competencia, como el francés. Otras arquitecturas, como RISC-V o ARMv8, son mucho más coherentes
  • Si “nunca viste una arquitectura más sucia que esta”, ahí está Itanium. Cada vez que abro el manual descubro algo nuevo que me hace pensar “¿pero qué estaban pensando?”, aunque no lo esté buscando a propósito
  • Lo entiendo. Quizá tendría que haber empezado con esa desde el principio

• Hace poco implementé, como proyecto paralelo, una parte considerable de un decodificador x86-64 [1], y me sorprendió bastante cuánto se ha vuelto más complejo últimamente. Para mi propósito, Sandpile.org [2] fue realmente útil
  [1] Más precisamente, una versión x86-64 del disfilter de Fabian Giesen que hice para otro proyecto paralelo que aún no es público: https://gist.github.com/lifthrasiir/df47509caac2f065032ef72e...
  [2] https://sandpile.org/

• El desensamblador 68k que hice en la universidad fue como el momento en que Neo dice “sé kung-fu”. Era el eslabón perdido que me permitió razonar sobre el código desde los lenguajes de alto nivel hasta los transistores, y luego de vuelta hacia arriba
  Escribir un emulador completo probablemente sea un orden de magnitud más efectivo que eso. Buen artículo

  • Creo que escribir un emulador de ISA en realidad no ayuda mucho a entender cómo funciona una CPU superescalar moderna. Casi todo son optimizaciones ocultas internamente

• Parece que mi memoria estaba equivocada. Recordaba que una variante de salsa20 y el código máquina estaban originalmente en cryp.to, pero el sitio de Dan Bernstein era https://cr.yp.to/
  En la época en que en una startup evaluábamos cifrado de datos en reposo, cifrado por streaming y cosas similares, las páginas de Dan tenían varias implementaciones por chipset e ISA de destino. Estaban cross-compiladas a partir de su representación de ensamblador
  Fue interesante usar la VM y ver qué conjuntos de instrucciones se admitían a principios y mediados de los 2000. Durante las pruebas, a veces surgían problemas porque la VM afirmaba soportarlos, pero la implementación no los soportaba por completo

  • Te refieres al sitio de Dan Berstain… un momento

• Me parece interesante que aquí haya tantos comentarios sobre lo doloroso que es el ensamblador x86 en comparación con RISC. Yo tengo el problema exactamente opuesto cuando separo código nuevamente en archivos objeto
  Para este uso, analizar x86 es realmente fácil, y MIPS fue una pesadilla. Principalmente porque lo que me importa son las referencias a código y datos. x86 tiene constantes inmediatas del tamaño de un puntero, y MIPS tiene pares de reubicación HI16/LO16 que se entrelazan con el grafo de uso de registros, el flujo de código y las instrucciones de retardo de salto, causando todo tipo de problemas
  No es que esté elogiando x86

  • Sí. x86 es raro, pero las instrucciones de longitud variable, una vez desplegadas en forma de texto, en realidad se ven bien y son fáciles de entender. El problema es que puedes esconder otras instrucciones en medio de una instrucción, lo que lo vuelve inseguro
    Lo más importante que se aprende al comparar ensamblador x86 con C es que signed/unsigned deja de ser un tipo y pasa a ser una propiedad de la operación
    Sería bueno poder aprovechar las flags, y en algunas arquitecturas como PPC o armv7 es más fácil, pero x86 sobrescribe las flags con tanta facilidad que es muy difícil aprovechar sus valores