Choses étranges apprises en écrivant un émulateur x86

• En réécrivant en C++ un émulateur CPU pour le Time Travel Debugging, on découvre que sur x86/amd64, un même comportement doit être traité différemment selon l’encodage, les préfixes et le mode d’exécution
• int 3 a un encodage sur un seul octet, CC, il existe une forme courte pour ADD EAX, imm, et des préfixes REX sans effet : autant de représentations alternatives qui influencent les performances et le débogage
• INC/DEC, CMPXCHG8B/CMPXCHG16B et les instructions de décalage/rotation gèrent les drapeaux d’une façon contre-intuitive, ce qui peut facilement mener à des bugs d’émulateur
• Le shift count n’est pas appliqué tel quel à la taille de l’opérande : il est masqué. Ainsi, shr eax,20h ne met pas un registre 32 bits à 0, mais conserve la valeur
• La segmentation est toujours utilisée pour accéder au TEB sous Windows 32 et 64 bits, et les différences de sens entre FS/GS ainsi que de détermination de leur base ont un impact direct sur l’implémentation des désassembleurs et des émulateurs

---

Règles de détail du x86 révélées par la réécriture de l’émulateur TTD

• Un des composants de Time Travel Debugging est un émulateur CPU qui enregistre l’exécution complète d’un processus au niveau instruction
• La première version, l’émulateur d’iDNA, était presque entièrement écrite en assembleur, donc rapide, mais difficile à maintenir et à faire évoluer
• Dans la deuxième version, la partie émulation ainsi que la plupart des autres composants ont été réécrits en C++, avec pour objectif de conserver l’essentiel des performances de la version assembleur tout en obtenant une base de code plus facile à gérer
• Construire un émulateur CPU impose de reproduire sans faute les détails du comportement du processeur, et même des règles familières aux habitués du x86 doivent être revérifiées au moment de l’implémentation

Les encodages x86 permettent plusieurs représentations d’une même instruction

• En x86, une même instruction peut être représentée par plusieurs séquences d’octets
• int 3 peut être encodé en CD 03, mais aussi sous la forme mono-octet CC
  • Comme il est utilisé pour les points d’arrêt logiciels, cela permet de placer un breakpoint même sur une instruction située à la fin d’une page mémoire dont la page suivante n’est pas mappée
• Il existe aussi des encodages alternatifs plus courts pour les cas fréquents
  • add eax, imm peut être écrit plus brièvement comme 05cccccccc
  • Pour ajouter la même valeur à ECX, il faut un octet de plus, par exemple 81c1cccccccc
• Si EAX est appelé « Accumulator register », ce n’est pas seulement une convention : cela se traduit réellement dans l’encodage, et des instructions plus courtes peuvent améliorer les performances en réduisant à la fois les données à charger depuis la mémoire principale et l’usage du cache d’instructions
• Les compilateurs peuvent exploiter ces encodages courts lorsqu’ils sont disponibles

Préfixes et limite de longueur de 15 octets par instruction

• Les instructions x86 peuvent avoir des octets de préfixe qui modifient leur comportement
• En code 64 bits, le préfixe REX, très courant, sert à accéder à un ensemble de registres plus large qu’en code 32 bits
• Le CPU accepte aussi des préfixes REX sans effet
  • 4004cc est une forme où un octet REX précède add al,0CCh sur 8 bits, mais ici le REX n’a aucun effet
  • Le CPU peut même exécuter deux préfixes REX d’affilée, ce qui peut perturber plusieurs désassembleurs, y compris WinDbg
• Sur les CPU compatibles x86, la longueur maximale d’une instruction est une limite matérielle de 15 octets
  • Toute instruction dépassant 15 octets est considérée comme invalide et provoque une exception
  • Les anciens CPU avaient aussi d’autres limitations sur les préfixes, et certains préfixes comme LOCK sont soumis à des conditions d’usage plus strictes

Une interprétation qui change selon la taille d’adresse et le mode

• Le préfixe d’override d’adresse permet, en mode 64 bits, de référencer une adresse 32 bits
  • 488d0424 correspond à lea rax,[rsp]
  • 67488d0424 devient lea rax,[esp] à cause du préfixe 0x67
• En code 32 bits, l’Address override fait basculer le mode d’adressage vers le 16 bits
• Pour désassembler ou interpréter correctement une même séquence d’octets, il faut connaître la taille d’opérande et la taille d’adresse par défaut du segment de code
  • En mode 32 bits, 8b0424 signifie mov eax,dword ptr [esp]
  • En mode 64 bits, 8b0424 signifie mov eax,dword ptr [rsp]
• La plage 40 à 4F, autrefois utilisée en x86 pour INC reg et DEC reg, sert en x64 de REX prefix bytes
  • En mode 32 bits, 48 03 04 24 est interprété comme deux instructions : dec eax puis add eax,dword ptr [esp]
  • En mode 64 bits, 48030424 est interprété comme une seule instruction : add rax,qword ptr [rsp]
• Les concepteurs d’AMD64 ont réutilisé l’espace d’encodage très large de INC/DEC pour le nouveau préfixe nécessaire à l’extension du jeu de registres en mode 64 bits, ces instructions disposant déjà d’un autre encodage couvrant à la fois registre et mémoire

Le piège de INC reg en mode 64 bits dans WinDbg

• WinDbg assemble toujours les instructions comme si elles étaient en mode 32 bits, ce qui peut produire un résultat inattendu si l’on tente d’assembler INC reg dans du code 64 bits
• Dans l’exemple, inc eax ne devient pas une vraie instruction d’incrémentation, mais un préfixe REX inutile qui modifie l’instruction suivante
• Au final, la séquence d’octets est interprétée non comme inc, mais comme un préfixe placé devant une instruction jmp

Exceptions dans le comportement des drapeaux

• INC EAX ressemble à ADD EAX, 1, mais ce n’est pas exactement la même chose
  • ADD met à jour le carry flag
  • INC ne met pas à jour le carry flag
• Lors de l’implémentation de l’émulateur TTD, cette différence avait d’abord été codée incorrectement, et des tests unitaires l’ont détectée
• La plupart des opérations arithmétiques et logiques définissent les overflow, sign, zero, auxiliary carry, parity et carry flags
• CMPXCHG définit aussi ces drapeaux, mais CMPXCHG8B et CMPXCHG16B ne modifient que le zero flag
• Certaines instructions laissent une partie des drapeaux dans un état indéfini
  • Les instructions de shift et de rotation laissent l’overflow flag indéfini quand la quantité de décalage est supérieure à 1
  • Le comportement réel des drapeaux indéfinis dépend de l’implémentation interne de l’opération de décalage et peut varier selon l’architecture
  • On raconte que les CPU de la famille Atom effectuent les bit shifts dans l’ALU d’une manière moins coûteuse et plus lente, ce qui change la valeur des drapeaux indéfinis, mais cela n’a pas été vérifié directement

Le masquage du count dans les instructions de shift

• 66c1e810 correspond à shr ax,10h et décale AX de 16 bits vers la droite
  • Comme AX est un registre 16 bits, le résultat devient 0
• c1e820 correspond à shr eax,20h, ce qui ressemble en apparence à une instruction décalant EAX de 32 bits vers la droite
• En réalité, la valeur de EAX ne change pas
  • D’après l’Intel SDM, le count est masqué par 1Fh, donc seuls les 5 bits de poids faible de la rotation sont utilisés
  • Avec le préfixe REX.W, le masque devient 3Fh, ce qui porte le décalage maximal à 63 bits
• Lors d’un entretien chez Microsoft, ce comportement a posé un vrai problème dans une question demandant « toutes les façons de remettre à zéro un registre 32 bits avec une seule instruction »
  • L’intervieweur pensait qu’un shift permettait de le faire, mais la réponse était que ce n’était pas possible sur un registre 32 bits

Des segments toujours vivants en code 32 et 64 bits

• La mémoire segmentée peut sembler être un vestige du code 16 bits, mais elle a encore des effets réels en code 32 et 64 bits
• La plupart des OS utilisent un modèle mémoire presque plat et fixent l’adresse de base des segments à 0, ce qui la rend généralement invisible au quotidien
  • En mode 64 bits, le CPU traite toujours la base des segments CS, DS, ES et SS comme étant 0
• Exception notable : le thread local storage utilise des registres de segment supplémentaires comme FS ou GS
• Rectificatif : la base des segments FS/GS peut être lue même depuis du code non privilégié via rdfsbase, wrfsbase, rdgsbase, wrgsbase
  • Ces instructions sont disponibles depuis Ivy Bridge, donc depuis 2012

Accès au TEB de Windows avec FS et GS

• Sous Windows, FS et GS servent à référencer le TEB (Thread Execution Block)
• La structure TEB contient un self pointer vers l’adresse plate du début de la structure, et cette adresse est aussi la base du segment concerné
• Dans les processus 32 bits, le TEB se trouve via FS
  • GetLastError récupère TEB.NtTib.Self depuis fs:[00000018h], puis lit LastErrorValue à [eax+34h]
• Dans les processus 64 bits, le TEB se trouve via GS
  • GetLastError lit un pointeur dans gs:[30h], puis récupère la valeur à [rax+68h]
• Un processus 32 bits exécuté sur un OS 64 bits possède à la fois un TEB 32 bits et un TEB 64 bits, et dans certains contextes comme le code WOW 64 bits exécuté à l’intérieur d’un processus 32 bits, il est utile d’accéder aux deux

La façon de déterminer la base d’un segment change aussi selon le mode

• La configuration CPU qui détermine l’adresse de base de FS et GS diffère entre le mode 32 bits et le mode 64 bits
• En mode 32 bits, la valeur réelle du registre de segment référence le segment descriptor défini dans la Global Descriptor Table et la Local Descriptor Table
• En mode 64 bits, la base est contrôlée par deux MSR
  • FS Base, ou IA32_FS_BASE dans l’Intel SDM
  • GS Base, ou IA32_GS_BASE dans l’Intel SDM
• À cause de cette structure, en mode 64 bits, la valeur réelle des registres FS et GS elle-même n’a pas d’importance
  • Ce qui compte, c’est le préfixe d’override de segment
• Dans WinDbg, lors du débogage d’un processus 32 bits, on peut utiliser la valeur du registre FS pour dumper le contenu du « segment FS »
• Sur un processus 64 bits, cela ne fonctionne pas de la même manière : c’est le préfixe d’override de segment qui a du sens, plus que la valeur du segment elle-même

Leçons pratiques pour les auteurs d’émulateurs

• Créer un émulateur x86 oblige à traiter très finement le comportement réel du CPU : encodage des instructions, préfixes, drapeaux, shift count, segments
• Une grande partie de ces règles est presque inutile pour écrire du code ordinaire, mais devient une exigence directe quand on implémente un émulateur
• Beaucoup de choses ont été apprises par essais-erreurs et grâce au mentorat ; l’article cite aussi Darek Mihocka, qui a une longue expérience des émulateurs, ainsi que emulators.com
• Si les optimisations x86 et le fonctionnement bas niveau vous intéressent, les ressources de Agner Fog’s website sont utiles

[GN⁺]

Commentaires sur Hacker News

• Au passage, BSF/BSR ont aussi leurs particularités. L’Intel SDM dit que si l’entrée vaut 0, la valeur de destination est indéfinie, tandis qu’AMD documente que, dans ce cas, la destination n’est pas modifiée.
  Or glibc s’appuie telle quelle sur le fait non documenté que, même chez Intel, la destination n’est pas modifiée [1]. À cause de cela, il m’a fallu pas mal de temps pour trouver la cause du problème dans mon traducteur binaire.
  Par ailleurs, TZCNT/LZCNT sont des encodages de BSF/BSR avec le préfixe F3 ; sur les anciens processeurs qui ne prennent pas en charge cette extension, le préfixe est silencieusement ignoré. Le même code se comporte donc différemment selon le CPU, mais au moins c’est documenté.
  Côté encodage, les gens critiquent souvent les préfixes, mais personnellement je ne trouve pas que ce soit le pire. C’est bien connu et relativement documenté. Il existe des bizarreries plus gênantes. Par exemple, les bits d’extension REX/VEX/EVEX.RXB sont ignorés lorsqu’ils ne s’appliquent pas, mais provoquent un #UD pour les registres de masque k0-k7. Pourtant, quand le registre est encodé dans ModRM.rm, les bits d’extension sont à nouveau ignorés.
  APX fait encore monter le niveau des singularités. Le préfixe REX2 peut encoder les registres généraux r16-r31, mais pas xmm16-xmm31 ; le préfixe EVEX a plusieurs agencements selon l’opcode, et les bits d’extension utilisés pour les registres changent aussi selon le type de registre. Les registres XMM utilisent X3:B3:rm et V4:X3:idx, tandis que les registres généraux utilisent B4:B3:rm et X4:X3:idx. Un an plus tard, je n’ai toujours pas terminé le décodeur APX, donc je ne peux pas donner la liste complète.
  [1]: https://sourceware.org/bugzilla/show_bug.cgi?id=31748

  • Depuis un an, je réécris par intermittence le décodeur x86 de QEMU. Au départ, c’était nécessaire pour ajouter la prise en charge d’AVX, mais il ne reste maintenant plus que quelques opcodes à réécrire, et après cela la prise en charge d’APX ne devrait pas être trop difficile.
    Pour EVEX, je compte conserver les bits bruts jusqu’à la lecture de l’opcode et l’identification de la classe EVEX. Autrement dit, l’idée est de les préserver jusqu’avant les immédiats, probablement même jusqu’avant ModRM.
    Mon décodeur repose globalement sur les tableaux du manuel, et le code est plutôt correct. L’indentation n’est pas excessive et les étapes sont pour la plupart séparées ou faciles à identifier. Comme la sortie est du code JIT, il n’a pas besoin d’être ultra-efficace ; je préfère qu’il soit lisible. Ce n’est pas non plus là que se passe l’essentiel du temps.
    Cela dit, il y a plusieurs cas où le manuel est faux ou ne dit pas tout. Les tableaux n’ont pas été mis à jour depuis des années et, par exemple, il n’y a même pas les instructions sur les registres K. À l’avenir, il faudra sans doute davantage de travail manuel.
    Le commentaire tout en haut explique un peu la situation : https://github.com/qemu/qemu/blob/59084feb256c617063e0dbe7e6...
    Comme dit plus haut, il reste encore quelques instructions gérées par l’ancien code, notamment BT/BTS/BTR/BTC. Le code est écrit, mais pas encore fusionné.
  • Il existe une autre particularité datant de l’époque des 486 et des Pentium. BSWAP EAX convertit entre little endian et big endian, et c’était dès le départ une instruction 32 bits.
    Mais il existe le préfixe 0x66, qui bascule entre les modes 16 bits et 32 bits. Si on l’applique à BSWAP EAX, il se produit quelque chose d’étrange et non défini.
    Sur certaines architectures de CPU, comme dans les différences Intel/AMD, le préfixe était simplement ignoré ; sur d’autres, il se produisait ce que j’appelle un « swap interne ». Par exemple, parmi les quatre octets stockés dans EAX, les octets 1 et 2 étaient échangés.
    0x11223344 devenait 0x11332244.
  • Quand on pense qu’il faut faire fonctionner toute cette logique correctement dans le silicium, et en plus rapidement, ça donne le vertige.
    Autrefois, x86 était le fossé défensif d’Intel ; aujourd’hui, ça ressemble plutôt à un fardeau cauchemardesque à traîner.
  • La combinaison entre la sémantique de LZCNT et son encodage ressemble à un but contre son camp. C’est encodé comme une instruction BSR avec un préfixe ignoré par les implémentations legacy, mais pour une entrée non nulle, la valeur retournée est la taille de l’opérande moins la valeur retournée par la version legacy.
    Il existe bien une fonction clz(), mais si LZCNT avait simplement été un BSR avec une sémantique différente uniquement pour l’entrée 0, le coût d’une soustraction supplémentaire dans l’implémentation pour obtenir la compatibilité aurait sans doute été modeste.
  • Je ne connais pas bien ce domaine, mais ce serait intéressant de connecter une interface JTAG à un CPU x86, d’exécuter instruction par instruction et d’enregistrer toutes les valeurs des registres.
    En exécutant le même programme sur un CPU émulé et en vérifiant à chaque instruction que l’état est identique, on pourrait tester si l’émulateur reproduit parfaitement le matériel.

• C’est quelqu’un d’impressionnant. Écrire de l’assembleur me paraît simple, et j’aime aussi son esthétique en colonnes verticales.
  L’expérience qui s’est rapprochée le plus d’un travail comme celui de l’OP, c’est quand j’ai essayé d’aider un ami qui fait du JS à comprendre la pile, et qu’on a créé ensemble une mini-VM avec un petit ISA : https://gist.github.com/darighost/2d880fe27510e0c90f75680bfe...
  On aurait pu creuser davantage, et j’aurais aimé le faire, mais je pense que cela nous aurait éloignés de l’objectif pédagogique initial. Il faudrait que je recontacte cet ami pour voir s’il veut encore étudier ça ensemble. Ce n’est pas simple : lui gagne beaucoup d’argent avec du développement web sophistiqué et n’a pas le temps de creuser, tandis que moi je suis au chômage, avec ce qui ressemble à un océan presque infini de temps et d’énergie.

  • Ça pourrait aussi être l’occasion d’apprendre le JS auprès de lui.
  • En tant que non-spécialiste, ce code a été une bonne porte d’entrée pour commencer à comprendre le fonctionnement interne, et il m’a mené vers un parcours en assembleur assez passionnant et difficile. Je compte approfondir.

• Justine Tunney et son émulateur valent aussi le détour. https://justine.lol/blinkenlights/
  La documentation offre un excellent tour d’horizon de la façon dont fonctionne un CPU.

  • Impressionnant. Ça me bluffe à chaque fois.
  • Le nom Tunney me rappelle l’époque, vers 2014, où elle vivait sans domicile et errait, tout en publiant des âneries sur Twitter liées à Occupy.

• La discussion précédente est ici : https://news.ycombinator.com/item?id=34636699
  J’ai du mal à croire que 16 mois se soient déjà écoulés. Le temps passe vraiment vite.

• Je ne suis pas du tout d’accord avec l’idée selon laquelle « écrire un émulateur de CPU est la meilleure façon de vraiment comprendre le fonctionnement d’un CPU »
  La meilleure façon, c’est de construire un CPU au niveau des portes, comme on le fait dans un bon cours d’informatique. Construire un ARM réduit à partir de zéro était vraiment amusant.

  • Je pense que les deux sont utiles. Cela dit, concevoir un CPU moderne au niveau des portes est hors de portée pour la plupart des gens, et il y a un grand écart entre le CPU qu’on conçoit à l’université et un CPU qui exécute du vrai code.
    Construire un émulateur de CPU moderne est un défi un peu plus accessible, et même si seule une partie fonctionne, cela reste très formateur.
  • D’accord. Même un processeur de base avec microcode, pipeline, superscalaire, prédiction de branchement, caches L1 données/instructions et contrôleur de cache L2 en write-back, ce n’est pas rien.
    La plupart des ingénieurs logiciel ont une compréhension incomplète des aléas de données, de l’invalidation de cache et des blocages de pipeline.
  • Je pense que les deux points de vue sont justes. Relier des puces 74xx est extrêmement satisfaisant, et permet de sentir les aspects électriques et les compromis internes.
    Mais dès qu’on commence à fabriquer ainsi un CPU qu’on voudrait utiliser pour faire quelque chose de significatif, ces détails deviennent moins intéressants. À ce stade, la complexité du comportement et des spécifications devient plus intéressante, et l’approche par émulateur est plus facile à manier et couvre davantage de types de comportements.
  • Je suis Nand2Tetris et je construis progressivement au niveau des portes ; je viens de terminer le chapitre sur l’émulateur de VM, et ça m’a pris un temps fou. Maintenant, je passe à l’étape de compilation.
  • À l’inverse, allez-vous vraiment implémenter jusqu’à la segmentation mémoire dans un CPU au niveau des portes ? Je pense que les deux étapes sont nécessaires pour une vraie compréhension : d’abord construire un CPU qui fonctionne réellement, puis émuler un vrai CPU, défauts compris.

• J’ai écrit des émulateurs rapides pour une douzaine d’architectures qui ne sont pas des jouets, ainsi que quelques convertisseurs JIT, mais x86 me donne encore un PTSD. Je n’ai jamais vu une architecture aussi bordélique. Il y a une histoire et des raisons, mais quand même, c’est violent.

  • Étudier l’architecture x86 donne l’impression d’étudier une langue pleine d’irrégularités, d’organes vestigiaux et de systèmes syntaxiques concurrents, comme le français par exemple. D’autres architectures comme RISC-V ou ARMv8 sont bien plus cohérentes.
  • Si tu n’as « jamais vu d’architecture plus bordélique que ça », il y a Itanium. À chaque fois que j’ouvre le manuel, je découvre, sans même chercher, un nouveau truc qui me fait me demander : « mais à quoi pensaient-ils ? »
  • Je compatis. J’aurais peut-être dû commencer par ça dès le début.

• J’ai récemment implémenté, comme projet perso, une bonne partie d’un décodeur x86-64 [1], et j’ai été assez surpris de voir à quel point c’est devenu encore plus complexe ces derniers temps. Pour mon usage, Sandpile.org [2] a été vraiment utile.
  [1] Plus précisément, une version x86-64 du disfilter de Fabian Giesen, créée pour un autre projet perso qui n’est pas encore public : https://gist.github.com/lifthrasiir/df47509caac2f065032ef72e...
  [2] https://sandpile.org/

• Le désassembleur 68k que j’ai fait à l’université a été un moment à la Neo disant « je connais le kung-fu ». C’était le chaînon manquant qui m’a permis de raisonner, depuis les langages de haut niveau jusqu’aux transistors, puis dans l’autre sens, sur le code.
  Écrire un émulateur complet doit être encore un ordre de grandeur plus efficace que ça. Bon article.

  • Je ne pense pas qu’écrire un émulateur d’ISA aide vraiment à comprendre comment fonctionnent les CPU superscalaires modernes. Presque tout est constitué d’optimisations cachées en interne.

• Ma mémoire devait me jouer des tours. Je me souvenais que les variantes de salsa20 et le code machine étaient à l’origine sur cryp.to, mais le site de Dan Bernstein était https://cr.yp.to/.
  À l’époque où, dans une startup, nous étudiions le chiffrement des données au repos, le chiffrement en streaming, etc., les pages de Dan proposaient plusieurs implémentations selon les chipsets et jeux d’instructions cibles. Elles étaient cross-compilées depuis sa représentation assembleur.
  C’était intéressant d’utiliser des VM et de voir quels jeux d’instructions étaient pris en charge au début/milieu des années 2000. Pendant les tests, il arrivait que certaines VM prétendent les prendre en charge, mais que l’implémentation ne soit pas complète, ce qui causait parfois des problèmes.

  • Tu veux sans doute parler du site de Dan Berstain… attends.

• C’est amusant de voir ici autant de gens dire à quel point l’assembleur x86 est pénible par rapport au RISC. Moi, j’ai le problème exactement inverse quand je sépare à nouveau du code en fichiers objet.
  Pour cet usage, analyser x86 est vraiment facile, tandis que MIPS a été un cauchemar. Principalement parce que ce qui m’intéresse, ce sont les références au code et aux données. x86 a des constantes immédiates de taille pointeur, tandis que MIPS a des paires de relocalisations HI16/LO16, qui s’entremêlent avec le graphe d’utilisation des registres, le flux de code et les instructions en délai de branchement, créant toutes sortes de problèmes.
  Ce n’est pas pour autant que je fais l’éloge de x86.

  • Exact. x86 est bizarre, mais les instructions de longueur variable, une fois déroulées sous forme textuelle, sont en fait agréables à lire et faciles à comprendre. Le problème, c’est qu’on peut cacher d’autres instructions au milieu d’une instruction, ce qui n’est pas sûr.
    La grande leçon quand on apprend en comparant l’assembleur x86 et le C, c’est que signé/non signé n’est plus une propriété du type, mais de l’opération.
    Ce serait bien de pouvoir exploiter les flags, et sur certaines architectures comme PPC ou armv7 c’est plus facile, mais x86 écrase les flags tellement facilement qu’il est très difficile d’en tirer parti.