Cómo escribir una máquina virtual (2022)

 (jmeiners.com)
3 puntos por GN⁺ 2024-12-28 | 1 comentarios | Compartir por WhatsApp
  • Para entender el funcionamiento interno de una computadora y cómo se ejecutan los lenguajes de programación, se implementa desde cero una VM basada en C de unas 250 líneas que ejecuta programas en assembly sobre la arquitectura educativa LC-3
  • El objetivo de implementación es un pequeño modelo de computadora con 65,536 ubicaciones de memoria de 16 bits, 10 registros, 16 opcodes, flags de condición, trap routines y registros mapeados en memoria
  • El loop de ejecución funciona con una estructura fetch-decode-execute: lee la instrucción apuntada por PC, lo incrementa, interpreta el opcode y ejecuta instrucciones como ADD, LDI, BR, JMP y TRAP
  • La carga de programas lee el primer origin de 16 bits del archivo objeto para ubicarlo en memoria y hace byte swap del formato big-endian de LC-3 para ajustarlo al formato little-endian usado por la mayoría de las computadoras modernas
  • La entrada de teclado y la salida de consola se manejan con trap routines y los registros mapeados en memoria KBSR/KBDR; en Unix/macOS y Windows se requiere código distinto para el buffering de entrada de la terminal

Objetivos y supuestos del tutorial

  • Sigue el proceso de implementar directamente una máquina virtual LC-3 para ejecutar programas en lenguaje assembly
  • El código final tiene unas 250 líneas en C, y se ofrecen lc3.c para Unix y lc3-win.c para Windows
  • Los conocimientos previos necesarios son lectura básica de C o C++ y aritmética binaria
  • El código completo está en el repo de GitHub, y el tutorial en sí está en formato de literate program, por lo que los bloques de código se entrelazan para crear el código fuente final

Qué hace una máquina virtual

  • Una VM es un programa que se comporta como una CPU y algunos componentes de hardware
    • Realiza operaciones aritméticas
    • Lee y escribe memoria
    • Interactúa con dispositivos de I/O
    • Entiende su propio lenguaje de máquina y ejecuta programas
  • Según el propósito de la VM, puede reproducir fielmente hardware real o proporcionar una nueva arquitectura virtual para facilitar el desarrollo de software
  • La JVM es un caso representativo de una VM que ofrece una plataforma de ejecución estándar; en dispositivos donde la JVM está implementada, se pueden ejecutar programas Java, Kotlin y Clojure sin modificaciones
  • La ejecución aislada también es un uso importante de las VM
    • En la recolección de basura, la VM puede observar la pila y las referencias de memoria desde fuera del programa en ejecución
    • Los smart contracts de Ethereum se ejecutan dentro de una VM que no puede acceder al sistema de archivos, la red, el disco, etc.

Componentes de la arquitectura LC-3

  • El objetivo de implementación es LC-3, usado en cursos universitarios de arquitectura de computadoras y assembly
  • La memoria de LC-3 tiene 65,536 ubicaciones, y cada una almacena un valor de 16 bits
    • La capacidad total de almacenamiento es 128 KB
    • En la implementación en C se representa como un arreglo uint16_t memory[MEMORY_MAX]
  • Hay un total de 10 registros
    • R0~R7: 8 registros de propósito general
    • PC: dirección de memoria de la próxima instrucción a ejecutar
    • COND: flag de condición del resultado del cálculo anterior
  • Todas las instrucciones de LC-3 son de 16 bits, y los 4 bits de la izquierda son el opcode
    • Se definen 16 opcodes
    • Incluyen OP_BR, OP_ADD, OP_LD, OP_ST, OP_JSR, OP_AND, OP_LDR, OP_STR, OP_RTI, OP_NOT, OP_LDI, OP_STI, OP_JMP, OP_RES, OP_LEA y OP_TRAP
  • Los flags de condición indican el signo del resultado del cálculo anterior
    • FL_POS: positivo
    • FL_ZRO: 0
    • FL_NEG: negativo

Assembly y lenguaje de máquina

  • Lo que realmente ejecuta la VM LC-3 no es assembly legible por humanos, sino un arreglo de instrucciones de máquina de 16 bits
  • El ensamblador convierte el assembly LC-3 escrito en texto en instrucciones binarias de 16 bits
  • El ejemplo Hello World tiene el siguiente flujo
    • .ORIG x3000: especifica la dirección de memoria donde se cargará el programa
    • LEA R0, HELLO_STR: carga la dirección de la cadena en R0
    • PUTS: imprime la cadena apuntada por R0
    • HALT: detiene el programa
    • .STRINGZ "Hello World!": almacena los datos de la cadena dentro del programa
  • .ORIG y .STRINGZ no son instrucciones de CPU, sino directivas del ensamblador
  • Las condiciones y repeticiones se implementan con instrucciones de bifurcación cercanas a goto, como BRn LOOP

Procedimiento central del loop de ejecución

  • La ejecución de la VM repite el mismo procedimiento
    • Lee la instrucción desde la dirección del registro PC
    • Incrementa PC
    • Obtiene el opcode de los 4 bits superiores de la instrucción
    • Ejecuta el código de implementación correspondiente al opcode
    • Vuelve a leer la siguiente instrucción
  • La dirección inicial predeterminada es 0x3000
  • Algunas instrucciones cambian directamente el PC para saltar el flujo de ejecución
    • Gracias a las instrucciones de bifurcación y salto, se pueden realizar loops y ejecuciones condicionales incluso con una estructura que simplemente incrementa PC
  • El loop main llama al código de manejo por opcode con switch (op)
    • Maneja OP_ADD, OP_AND, OP_NOT, OP_BR, OP_JMP, OP_JSR, OP_LD, OP_LDI, OP_LDR, OP_LEA, OP_ST, OP_STI, OP_STR y OP_TRAP
    • OP_RES y OP_RTI son opcodes no usados y pueden manejarse con abort()

Cómo se implementan las instrucciones

  • ADD suma dos valores, guarda el resultado en el registro destino y actualiza los flags de condición
  • ADD tiene dos modos
    • Modo registro: lee el segundo operando desde otro registro
    • Modo inmediato: lee el segundo operando desde los 5 bits inferiores de la instrucción, imm5
  • Los valores más cortos que 16 bits, como imm5, deben extenderse a un valor de 16 bits mediante sign extension
    • Los positivos se rellenan con 0
    • Los negativos se rellenan con 1 para preservar el valor original
  • Las instrucciones que escriben valores en registros actualizan R_COND con update_flags
    • Si el valor es 0, FL_ZRO
    • Si el bit más significativo es 1, FL_NEG
    • En cualquier otro caso, FL_POS
  • LDI es la instrucción “load indirect”
    • Aplica sign extension al PCoffset9 de la instrucción
    • Lo suma al PC actual para obtener una dirección de memoria
    • Usa el valor almacenado en esa ubicación nuevamente como dirección para leer el dato final
    • Guarda el valor leído en el registro destino y actualiza los flags de condición

Conjunto principal de instrucciones

  • Operaciones aritméticas y de bits
    • ADD: suma
    • AND: AND bit a bit
    • NOT: NOT bit a bit
  • Flujo de control
    • BR: mueve el PC comparando los flags de condición con los bits de condición de la instrucción
    • JMP: establece el PC con el valor del registro especificado
    • RET: aunque en la especificación es una palabra clave separada, es un caso especial de JMP
    • JSR, JSRR: guardan el PC actual en R7 y saltan a la ubicación de la subrutina
  • Lectura de memoria
    • LD: lee desde una dirección con offset respecto de PC
    • LDI: sigue una dirección indirecta una vez más y lee
    • LDR: lee desde una dirección calculada con base register y offset
    • LEA: guarda la dirección efectiva en sí en un registro
  • Escritura de memoria
    • ST: guarda en una dirección con offset respecto de PC
    • STI: sigue una dirección indirecta y guarda
    • STR: guarda en una dirección calculada con base register y offset

Trap routines e I/O

  • LC-3 ofrece trap routines para tareas comunes y acceso a dispositivos de I/O
  • Las trap routines pueden verse como el sistema operativo o la API de LC-3
  • Los trap codes se definen así
    • TRAP_GETC = 0x20: entrada de un carácter desde el teclado, sin echo en la terminal
    • TRAP_OUT = 0x21: salida de un carácter
    • TRAP_PUTS = 0x22: salida de una word string
    • TRAP_IN = 0x23: entrada de un carácter y luego echo en la terminal
    • TRAP_PUTSP = 0x24: salida de una byte string
    • TRAP_HALT = 0x25: detiene el programa
  • En el simulador oficial de LC-3, las trap routines están escritas en assembly, pero en esta VM se implementan como funciones C
  • PUTS imprime caracteres desde la dirección almacenada en R0 hasta encontrar x0000
    • Las cadenas de LC-3 no almacenan un byte por carácter como las cadenas de C, sino un carácter por ubicación de memoria
    • Como cada ubicación de memoria es de 16 bits, al imprimir en C se convierte a char
  • La trap HALT imprime "HALT", cambia el flag de ejecución a 0 y termina el loop de la VM

Carga de imágenes de programa

  • Al convertir un programa LC-3 en assembly a lenguaje de máquina, se crea un archivo con un arreglo de instrucciones y datos
  • Los primeros 16 bits del archivo objeto son el origin que indica dónde colocar el programa en memoria
  • El loader primero lee el origin y copia el resto de los datos en memoria a partir de esa dirección
  • Los programas LC-3 están en formato big-endian
    • Como la mayoría de las computadoras modernas son little-endian, se aplica swap16 a cada uint16_t cargado
    • En computadoras big-endian, como las PPC Mac antiguas, no se debe hacer el swap
  • read_image abre el archivo en modo binario, llama a read_image_file y luego cierra el archivo

Registros mapeados en memoria

  • Los registros especiales a los que no se accede mediante la tabla normal de registros se mapean a direcciones de memoria específicas
  • En LC-3 se deben implementar dos registros mapeados en memoria
    • MR_KBSR = 0xFE00: keyboard status register
    • MR_KBDR = 0xFE02: keyboard data register
  • KBSR indica si se presionó una tecla, y KBDR almacena qué tecla se presionó
  • GETC bloquea la ejecución hasta que llegue una entrada, pero KBSR y KBDR hacen polling del estado del dispositivo para que el programa pueda seguir respondiendo mientras espera entrada
  • La lectura de memoria no accede directamente al arreglo, sino que pasa por mem_read
    • Si la dirección es MR_KBSR, verifica el estado del teclado con check_key()
    • Si hay una tecla, activa el bit más significativo de KBSR y guarda el valor de getchar() en KBDR
    • Si no hay tecla, configura KBSR en 0

Manejo de terminal según la plataforma

  • Para manejar correctamente la entrada de teclado y el comportamiento de la terminal, se necesita configurar el buffering de entrada según la plataforma
  • La implementación para Linux/macOS/UNIX usa termios, select, etc.
    • Desactiva canonical mode y echo
    • Usa select para comprobar si hay entrada disponible
  • La implementación para Windows usa GetStdHandle, GetConsoleMode, SetConsoleMode, _kbhit, etc.
    • Ajusta echo y line input
    • Comprueba las teclas con WaitForSingleObject y _kbhit
  • Al iniciar el programa se llama a disable_input_buffering(), y al terminar se llama a restore_input_buffering()
  • Al recibir SIGINT, restaura la configuración de la terminal, imprime un salto de línea y termina

Ejecución y depuración de la VM

  • Un ejemplo de build de la VM es el siguiente
gcc lc3.c -o lc3-vm
  • Para ejecutarla, se pasa como argumento un archivo objeto LC-3 ensamblado
lc3-vm path/to/2048.obj
  • Los archivos objeto incluidos como ejemplo son 2048.obj y rogue.obj
  • El ejemplo 2048 se controla con las teclas WASD
  • Si el programa no funciona correctamente, es probable que haya un error en la implementación de alguna instrucción
    • Se recomienda leer el código fuente assembly de LC-3 y ejecutar paso a paso las instrucciones de la VM con un depurador
    • Si hay un punto donde no se llega a la instrucción esperada, conviene revisar nuevamente la especificación y la implementación de esa instrucción

Opcional: implementación basada en genéricos de C++

  • También se cubre como opción una técnica de implementación más corta en C++
  • Como varias instrucciones comparten tareas repetidas, como sign extension, offsets respecto de PC y cálculo de direcciones indirectas, la ejecución de instrucciones puede verse como un pipeline de pequeños pasos de procesamiento
  • Con templates de C++ y bit flags, se incluyen en tiempo de compilación solo los pasos de procesamiento necesarios para cada opcode
  • Este enfoque reduce la duplicación de código y se acerca más a cómo funciona el cableado del hardware real, donde cada paso de procesamiento ocupa espacio físico en el chip
  • Como fuente de la idea se menciona Bisqwit’s NES emulator

Recursos y contribuciones

  • atul-g contribuyó una reference card que resume el funcionamiento de todo el sistema
  • Las implementaciones en varios lenguajes están organizadas bajo el topic de GitHub lc3
    • Incluye C, C++, Go, Haskell, Java, JavaScript, Kotlin, Lua, OCaml, Python, Ruby, Rust, Swift, TypeScript, Zig, entre otros
  • Para que tu implementación aparezca en la lista, basta con agregarle el topic de GitHub lc3
  • El soporte para la plataforma Windows fue contribuido por inkydragon
  • El proyecto tiene un good first issue relacionado con pruebas de integración

Lecturas relacionadas

1 comentarios

 
GN⁺ 2024-12-28
Opiniones de Hacker News

  • Cuando era adolescente, en una clase introductoria de ciencias de la computación en un community college, diseñé un conjunto de instrucciones de CPU simple, construí mi propia máquina virtual y ensamblador, y escribí y ejecuté programas en assembly.
    Fue sorprendentemente fácil, y las computadoras se sintieron mucho menos misteriosas.
    Creo que se podrían aprender todas las capas de la computación de esta forma, desde diseñar una CPU real para FPGA hasta escribir un sistema operativo simple y programas que corran encima.
    Si se deja de lado el rendimiento y la seguridad que exige la computación moderna, y el objetivo es simplemente “que funcione”, este campo es sorprendentemente sencillo.

    • Suena como una clase divertida, y se parece mucho a https://www.nand2tetris.org/ o al libro Code de Charles Petzold.
    • En el momento en que pasas de una CPU imaginaria inicial a una CPU real de producción temprana, como la 80286, la complejidad aumenta drásticamente.
      Si no recuerdo mal, como mínimo entran en juego la segmentación de memoria, el modo protegido y la MMU.
    • También había un sistema así en una clase de CS 101.
      Era una computadora/ensamblador simple escrito en BASIC sobre una PDP, y una de las tareas era implementar una multiplicación simple haciendo sumas con un bucle.
      En lugar de eso, un amigo modificó el programa para crear una nueva instrucción MUL, y al profesor no le gustó nada.
    • Los componentes simples en sí son realmente fáciles, pero están a cientos de capas de distancia de un resultado de nivel comercial que un usuario real ve y toca en una computadora.
      Alguien con curiosidad y ganas de aprender puede asimilar fácilmente esas capas básicas, pero no alguien que quiere “ganar dinero rápido y volverse empleable lo antes posible”.
    • El curso nand2tetris parece hacer exactamente eso.

  • Libros recomendados:

    1. Virtual Machines: Versatile Platforms for Systems and Processes, de Smith y Nair — parece un libro que recorre el tema de forma amplia.
    2. Virtual Machines, de Iain Craig — parece un libro más práctico sobre lenguajes y máquinas virtuales.
    3. Virtual Machine Design and Implementation in C/C++, de Bill Blunden — parece una guía práctica centrada en la implementación.
      Sería útil para todos que alguien que haya leído esos libros agregara sus comentarios.
    • No estoy seguro de que este tema sea lo bastante acotado como para cubrirlo en un solo libro.
      Un emulador de Nintendo, un hipervisor que usa VT-x, un sistema operativo multitarea tradicional, el intérprete de un nuevo lenguaje de scripting, un optimizador de consultas SQL, un matcher de expresiones regulares, un monitor de seguridad que ejecuta código de jugadores no confiable en un servidor de juegos, etc., parecen tener muy pocas consideraciones en común, pero todos son máquinas virtuales.
      Incluso dentro del formato terminfo, que especifica secuencias de escape de terminales de celdas de caracteres, hay una máquina virtual basada en pila.
      Si se mira a fondo, lo que hace que una computadora sea una computadora en el sentido actual es la máquina virtual, y el artículo de Turing de 1936 sobre el Entscheidungsproblem también dependía de que las máquinas virtuales pudieran imitarse entre sí.

  • Después de ver la serie de Ben Eater sobre una CPU en breadboard, lo único que quiero es diseñar y emular una CPU yo mismo.
    Ojalá pudiera encontrar tiempo para sentarme a diseñarla.

  • Creo que las arquitecturas educativas como Brookshear Machine o Little Computer no se parecen en nada a las arquitecturas reales, así que no solo son inútiles, sino dañinas.
    He visto estudiantes que tomaron clases usando esas cosas y terminaron entendiendo las computadoras de forma más distorsionada que alguien que no tomó ninguna clase.
    Para la mayoría de la gente que quiere aprender un poco sobre cómo funciona su computadora, una clase de sistemas operativos es mejor, y si incluso ahí solo hubiera tiempo para un tutorial corto, recomendaría “Writing my own bootloader”.
    https://dev.to/frosnerd/writing-my-own-boot-loader-3mld
    Esto no significa que el tutorial “Write your own VM” sea malo, sino que, según mi experiencia, para la mayoría de las personas que lo harían, otro tema les sería más útil.

    • Acabo de probar LC-3, y en mi proyecto actual quiero aprender un poco de recompilación dinámica usando LC-3 como una máquina objetivo inadecuada.
      ¿Podrías explicar más por qué LC-3 es malo para estudiar arquitectura de computadoras?
      Entiendo que es completamente distinto del hardware real y demasiado simple, pero me pregunto si también es malo desde el punto de vista de escribir un emulador de CPU.
    • Me recuerda al viejo MIX de Knuth.
      Era una máquina decimal que podría haberse construido en los años 60, pero después de los 70 nadie fabricó nada así.
      Esos sistemas pueden enseñar muchos fundamentos, pero las técnicas de https://en.wikipedia.org/wiki/Hacker%27s_Delight dependen principalmente de formas comunes de representar números, así que se vuelven difíciles de aprender.
    • Me da curiosidad qué es lo que particularmente no te gusta de LC-3.
      Como no lo conozco bien, miré Wikipedia un momento y, por el cómic, esperaba algo raro, pero a primera vista no me pareció tan impactante.
      Da la impresión de mezclar s/360, algo de x86 y un poquito de ARM u otras arquitecturas tipo RISC, y aunque hay muchas omisiones y rarezas, el objetivo parece ser llegar rápido a una implementación funcional.
      Quisiera saber qué te hace considerarlo “no solo inútil, sino dañino” para la enseñanza.
    • Recomendaría usar arquitecturas de 8 bits antiguas como 6502 o Z80.
      Parece que muchas clases de ciencias de la computación en India todavía usan 8086/8088.
    • LC-3 tiene modos de direccionamiento bastante peculiares.
      En particular, permite hacer cargas indirectas dobles mediante una palabra relativa al PC que está en medio.
      Aun así, la resta hay que construirla a partir de la negación, y la negación hay que construirla con NOT y ADD ,,#-1.
      Considerando el espacio limitado de codificación de instrucciones, creo que NOT d,s = XOR d,s,#-1 habría sido un mejor uso.

  • Si nos ponemos estrictos, esto no es una máquina virtual, sino un emulador.
    En un sentido descriptivo, el término puede aplicarse, y antes de la era de la virtualización de hardware había cierta ambigüedad, pero hoy el uso abrumadoramente más común de “Virtual Machine” se refiere a un entorno que usa funciones de virtualización de hardware como VT-x.

    • No estoy de acuerdo con que ese uso sea “abrumadoramente común”, y tampoco me parece una distinción del todo correcta.
      La JVM está ampliamente desplegada, la Ethereum VM se conoce como EVM, https://www.linuxfoundation.org/hubfs/LF%20Research/The_Stat... describe repetidamente a BPF y eBPF como “virtual machines”, y https://webassembly.org/ empieza diciendo que “WebAssembly (abreviado Wasm) es un formato de instrucciones binarias para una máquina virtual basada en pila”.
      “Máquina virtual” sigue siendo la forma más común de llamar a una máquina virtual.
      Personalmente, me gustan más expresiones como “fictive machine”, “fictious machine”, “imaginary computer” o “fantastic automaton”, pero no creo que vayan a adoptarse.
      No siempre se puede usar “emulador” en lugar de “máquina virtual”.
      Quizá se pueda llamar emulador a wasmtime, pero no es preciso llamar emulador a WebAssembly en sí; WebAssembly es la máquina virtual que wasmtime emula.
      También es común llamar máquina virtual a un emulador, y una instancia de emulador en ejecución también es una máquina virtual en otro sentido.
      También es válido llamar “máquina virtual” a un entorno de virtualización de hardware, y se superpone en cierta medida con este último significado.
      En el entorno actual, ese uso puede ser abrumadoramente común, pero no necesariamente lo es en otros ámbitos.
    • Con todo respeto, me cuesta estar de acuerdo.
      En su sentido más puro, una máquina virtual es simplemente una computadora inventada, y no implica para qué se usará ni cómo funciona.
      El artículo también pone como ejemplo la emulación de consolas clásicas, pero deja claro que, según la definición propuesta, hay muchas más máquinas virtuales posibles.
      El punto central es que una máquina virtual es un concepto abstracto y que existen muchísimos tipos.
      Simuladores, emuladores, hipervisores, etc., son todos máquinas virtuales, y también hay formas extrañas de máquinas virtuales que aún no tienen nombre.
      No lo digo con intención de ser grosero; al contrario, lo digo con respeto y porque quiero aclarar este término para quienes están aprendiendo.
    • Creo que la distinción que estás defendiendo en realidad no existe.
      “Máquina virtual” se usa comúnmente para cualquier software que ejecuta código máquina o bytecode, sin importar el motivo.
      Puede incluir virtualización, pero también se usa con frecuencia para runtimes de lenguaje, como la JVM de Java o YARV (Yet Another Ruby VM) de Ruby.
      De hecho, un ámbito donde no se oye tanto este término es la emulación, en parte porque la mayoría de los emuladores modernos se inclinan por técnicas de recompilación dinámica del software emulado, en lugar de emular un sistema completo.
    • Esto es una VM en el sentido de la JVM, es decir, Java Virtual Machine.
      Diría que Java sí cuenta como un “uso abrumadoramente común”.