Como criar uma máquina virtual (2022)

• Para entender o funcionamento interno dos computadores e como linguagens de programação são executadas, foi implementada do zero uma VM em C com cerca de 250 linhas que executa programas em assembly sobre a arquitetura educacional LC-3
• O alvo da implementação é um pequeno modelo de computador com 65.536 posições de memória de 16 bits, 10 registradores, 16 opcodes, flags de condição, trap routines e registradores mapeados em memória
• O loop de execução funciona em uma estrutura fetch-decode-execute: lê a instrução apontada pelo PC, incrementa-o, interpreta o opcode e executa instruções como ADD, LDI, BR, JMP e TRAP
• O carregamento de programas lê o primeiro origin de 16 bits do arquivo objeto, coloca o programa na memória e faz byte swap do formato big-endian do LC-3 para adequá-lo ao formato little-endian usado pela maioria dos computadores modernos
• Entrada de teclado e saída no console são tratadas por trap routines e pelos registradores mapeados em memória KBSR/KBDR, exigindo código diferente de bufferização de entrada do terminal para Unix/macOS e Windows

---

Objetivos e pressupostos do tutorial

• Acompanhar o processo de implementar diretamente uma máquina virtual LC-3 para executar programas em linguagem assembly
• O código final tem cerca de 250 linhas em C, com lc3.c para Unix e lc3-win.c para Windows
• Os conhecimentos prévios necessários são leitura básica de C ou C++ e aritmética binária
• O código completo está no repositório do GitHub, e o tutorial em si está no formato de literate program, em que blocos de código são combinados para formar o código-fonte final

O que uma máquina virtual faz

• Uma VM é um programa que se comporta como uma CPU e alguns componentes de hardware
  • Executa operações aritméticas
  • Lê e escreve na memória
  • Interage com dispositivos de I/O
  • Entende sua própria linguagem de máquina e executa programas
• Dependendo do objetivo da VM, ela pode reproduzir fielmente o hardware real ou oferecer uma nova arquitetura virtual para facilitar o desenvolvimento de software
• A JVM é um exemplo representativo de VM que oferece uma plataforma padrão de execução; em dispositivos com uma JVM implementada, programas em Java, Kotlin e Clojure podem rodar sem modificações
• Execução isolada também é um uso importante de VMs
  • Em garbage collection, a VM consegue observar a pilha e as referências de memória fora do programa em execução
  • Smart contracts do Ethereum são executados dentro de uma VM que não permite acesso ao sistema de arquivos, à rede, ao disco etc.

Componentes da arquitetura LC-3

• O alvo da implementação é o LC-3, usado no ensino universitário de arquitetura de computadores e assembly
• A memória do LC-3 tem 65.536 posições, e cada posição armazena um valor de 16 bits
  • A capacidade total de armazenamento é de 128 KB
  • Na implementação em C, ela é representada por um array uint16_t memory[MEMORY_MAX]
• Há um total de 10 registradores
  • R0~R7: 8 registradores de uso geral
  • PC: endereço de memória da próxima instrução a executar
  • COND: flag de condição do resultado do cálculo anterior
• Todas as instruções do LC-3 têm 16 bits, e os 4 bits à esquerda são o opcode
  • São definidos 16 opcodes
  • Incluem 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 e OP_TRAP
• As flags de condição indicam o sinal do resultado do cálculo anterior
  • FL_POS: positivo
  • FL_ZRO: 0
  • FL_NEG: negativo

Assembly e linguagem de máquina

• O que a VM LC-3 realmente executa não é o assembly legível por humanos, mas sim um array de instruções de máquina de 16 bits
• O assembler converte o assembly LC-3 escrito em texto em instruções binárias de 16 bits
• O exemplo Hello World segue este fluxo
  • .ORIG x3000: especifica o endereço de memória em que o programa será carregado
  • LEA R0, HELLO_STR: carrega o endereço da string em R0
  • PUTS: imprime a string apontada por R0
  • HALT: interrompe o programa
  • .STRINGZ "Hello World!": armazena os dados da string dentro do programa
• .ORIG e .STRINGZ não são instruções da CPU, mas diretivas do assembler
• Condições e repetições são implementadas com instruções de desvio próximas de goto, como BRn LOOP

Procedimento central do loop de execução

• A execução da VM repete o mesmo procedimento
  • Lê a instrução no endereço do registrador PC
  • Incrementa o PC
  • Obtém o opcode a partir dos 4 bits superiores da instrução
  • Executa o código de implementação correspondente ao opcode
  • Lê novamente a próxima instrução
• O endereço inicial padrão é 0x3000
• Algumas instruções alteram diretamente o PC, fazendo o fluxo de execução saltar
  • Graças às instruções de desvio e salto, loops e execução condicional são possíveis mesmo em uma estrutura que simplesmente incrementa o PC
• O loop de main chama o código de tratamento por opcode com switch (op)
  • Trata 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 e OP_TRAP
  • OP_RES e OP_RTI são opcodes não usados e podem ser tratados com abort()

Como as instruções são implementadas

• ADD soma dois valores, armazena o resultado no registrador de destino e atualiza as flags de condição
• ADD tem dois modos
  • Modo registrador: lê o segundo operando de outro registrador
  • Modo imediato: lê o segundo operando dos 5 bits inferiores da instrução, imm5
• Valores mais curtos que 16 bits, como imm5, precisam ser expandidos para 16 bits por sign extension
  • Números positivos são preenchidos com 0
  • Números negativos são preenchidos com 1 para preservar o valor original
• Instruções que escrevem valores em registradores atualizam R_COND com update_flags
  • Se o valor for 0, FL_ZRO
  • Se o bit mais significativo for 1, FL_NEG
  • Caso contrário, FL_POS
• LDI é uma instrução de “load indirect”
  • Faz sign extension do PCoffset9 da instrução
  • Soma-o ao PC atual para obter um endereço de memória
  • Usa o valor armazenado nessa posição novamente como endereço para ler o dado final
  • Armazena o valor lido no registrador de destino e atualiza as flags de condição

Principais conjuntos de instruções

• Operações aritméticas e de bits
  • ADD: adição
  • AND: AND bit a bit
  • NOT: NOT bit a bit
• Fluxo de controle
  • BR: move o PC comparando as flags de condição com os bits de condição da instrução
  • JMP: define o PC como o valor do registrador especificado
  • RET: embora seja uma palavra-chave separada na especificação, é um caso especial de JMP
  • JSR, JSRR: salvam o PC atual em R7 e saltam para a posição da sub-rotina
• Leitura de memória
  • LD: lê a partir de um endereço com offset relativo ao PC
  • LDI: segue mais um nível de endereço indireto e lê
  • LDR: lê a partir de um endereço calculado com base register e offset
  • LEA: armazena no registrador o próprio endereço efetivo
• Escrita de memória
  • ST: armazena em um endereço com offset relativo ao PC
  • STI: segue o endereço indireto e armazena
  • STR: armazena em um endereço calculado com base register e offset

Trap routines e I/O

• O LC-3 oferece trap routines para tarefas comuns e acesso a dispositivos de I/O
• Uma trap routine pode ser vista como o sistema operacional ou a API do LC-3
• Os trap codes são definidos assim
  • TRAP_GETC = 0x20: entrada de caractere pelo teclado, sem eco no terminal
  • TRAP_OUT = 0x21: saída de caractere
  • TRAP_PUTS = 0x22: saída de word string
  • TRAP_IN = 0x23: entrada de caractere e eco no terminal
  • TRAP_PUTSP = 0x24: saída de byte string
  • TRAP_HALT = 0x25: interrupção do programa
• No simulador oficial do LC-3, as trap routines são escritas em assembly, mas nesta VM elas são implementadas como funções C
• PUTS imprime caracteres a partir do endereço armazenado em R0 até encontrar x0000
  • Strings do LC-3 não armazenam um caractere por byte como strings em C, mas um caractere por posição de memória
  • Como cada posição de memória tem 16 bits, a saída em C converte para char antes de imprimir
• O trap HALT imprime "HALT", altera a flag de execução para 0 e encerra o loop da VM

Carregamento da imagem do programa

• Ao converter um programa assembly LC-3 para linguagem de máquina, é gerado um arquivo contendo um array de instruções e dados
• Os primeiros 16 bits do arquivo objeto são o origin, que indica onde colocar o programa na memória
• O loader lê primeiro o origin e copia o restante dos dados para a memória a partir desse endereço
• Programas LC-3 usam o formato big-endian
  • Como a maioria dos computadores modernos é little-endian, aplica-se swap16 a cada uint16_t carregado
  • Em computadores big-endian, como Macs PPC antigos, o swap não deve ser feito
• read_image abre o arquivo em modo binário, chama read_image_file e depois fecha o arquivo

Registradores mapeados em memória

• Registradores especiais que não são acessados pela tabela comum de registradores são mapeados para endereços específicos de memória
• Há dois registradores mapeados em memória que precisam ser implementados no LC-3
  • MR_KBSR = 0xFE00: keyboard status register
  • MR_KBDR = 0xFE02: keyboard data register
• KBSR indica se uma tecla foi pressionada, e KBDR armazena qual tecla foi pressionada
• GETC bloqueia a execução até que entre uma entrada, mas KBSR e KBDR fazem polling do estado do dispositivo, permitindo que o programa continue respondendo enquanto aguarda entrada
• A leitura de memória não acessa diretamente o array; ela passa por mem_read
  • Se o endereço for MR_KBSR, verifica o estado do teclado com check_key()
  • Se houver uma tecla, seta o bit mais significativo de KBSR e armazena o valor de getchar() em KBDR
  • Se não houver tecla, define KBSR como 0

Tratamento de terminal por plataforma

• Para tratar corretamente entrada de teclado e comportamento do terminal, é necessário configurar a bufferização de entrada de forma específica para cada plataforma
• A implementação para Linux/macOS/UNIX usa termios, select etc.
  • Desativa o modo canônico e o eco
  • Usa select para verificar se há entrada disponível
• A implementação para Windows usa GetStdHandle, GetConsoleMode, SetConsoleMode, _kbhit etc.
  • Ajusta o eco e a entrada por linha
  • Verifica entrada de teclado com WaitForSingleObject e _kbhit
• No início do programa, chama-se disable_input_buffering(); ao encerrar, chama-se restore_input_buffering()
• Ao receber SIGINT, o programa restaura as configurações do terminal, imprime uma quebra de linha e termina

Execução e depuração da VM

• Exemplo de build da VM:

gcc lc3.c -o lc3-vm

• Para executar, passe como argumento um arquivo objeto LC-3 já montado

lc3-vm path/to/2048.obj

• Os arquivos objeto fornecidos como exemplo são 2048.obj e rogue.obj
• O exemplo 2048 é controlado pelas teclas WASD
• Se o programa não funcionar corretamente, é provável que haja erro na implementação de alguma instrução
  • Recomenda-se executar instrução por instrução no depurador da VM enquanto lê o código-fonte assembly do LC-3
  • Se houver um ponto que não desvia para a instrução esperada, confira novamente a especificação e a implementação dessa instrução

Opcional: implementação baseada em genéricos de C++

• Também é abordada, como opção, uma técnica de implementação mais curta em C++
• Como várias instruções compartilham tarefas repetidas, como sign extension, offset relativo ao PC e cálculo de endereço indireto, a execução de instruções pode ser vista como um pipeline de pequenas etapas de processamento
• Usando templates de C++ e flags de bits, apenas as etapas necessárias para cada opcode são incluídas em tempo de compilação
• Essa abordagem reduz duplicação de código e se aproxima mais da forma de fiação de hardware real, em que cada etapa de processamento ocupa espaço físico no chip
• Bisqwit’s NES emulator é mencionado como origem da ideia

Recursos e contribuições

• atul-g contribuiu com um reference card que resume o funcionamento de todo o sistema
• Implementações em várias linguagens são organizadas pelo GitHub topic lc3
  • Incluem C, C++, Go, Haskell, Java, JavaScript, Kotlin, Lua, OCaml, Python, Ruby, Rust, Swift, TypeScript, Zig etc.
• Para que sua implementação apareça na lista, basta adicionar o GitHub topic lc3
• O suporte à plataforma Windows foi contribuído por inkydragon
• O projeto tem uma good first issue relacionada a testes de integração

[GN⁺]

Opiniões do Hacker News

• Quando eu era adolescente, em uma aula introdutória de ciência da computação no community college, projetei um conjunto simples de instruções de CPU e criei por conta própria uma máquina virtual e um assembler para escrever e executar programas em assembly
  Foi surpreendentemente fácil, e o computador passou a parecer muito menos misterioso
  Acho que daria para aprender todas as camadas da computação desse jeito, desde o projeto de uma CPU real para FPGA até a criação de um sistema operacional simples e de programas rodando sobre ele
  Se você tirar o desempenho e a segurança exigidos pela computação moderna e tiver como meta apenas “funcionar”, essa área é inesperadamente simples

  • Parece uma aula divertida e muito parecida com https://www.nand2tetris.org/ ou com o livro Code, de Charles Petzold
  • A complexidade aumenta drasticamente no momento em que você sai de uma CPU imaginária inicial para uma CPU real de produção em massa dos primeiros tempos, como a 80286
    Se não me falha a memória, no mínimo entram segmentação de memória, modo protegido e MMU
  • Também havia um sistema desses na aula de CS 101
    Era um computador/assembler simples escrito em BASIC em um PDP, e uma das tarefas era implementar multiplicação simples fazendo somas em um loop
    Um amigo, em vez disso, alterou o programa para criar uma nova instrução MUL, e o professor não gostou nada
  • Os componentes simples em si são realmente fáceis, mas estão a centenas de camadas de distância de um resultado em nível comercial que usuários reais veem e manipulam em um computador
    Quem tem curiosidade e vontade de aprender consegue assimilar facilmente essas camadas básicas, mas isso não vale para quem quer “ganhar dinheiro rápido e ficar empregável o mais depressa possível”
  • Parece que o curso nand2tetris faz exatamente isso

• Livros recomendados:

  1. Virtual Machines: Versatile Platforms for Systems and Processes, de Smith e Nair — parece ser um livro que passa de forma abrangente pelo tema
  2. Virtual Machines, de Iain Craig — parece ser um livro mais prático sobre linguagens e máquinas virtuais
  3. Virtual Machine Design and Implementation in C/C++, de Bill Blunden — parece ser um guia prático focado em implementação
     Seria útil para todos se alguém que leu esses livros acrescentasse comentários
  • Não sei bem se esse tema é estreito o suficiente para ser apresentado em uma visão geral de um único livro
    Um emulador de Nintendo, um hipervisor usando VT-x, um sistema operacional multitarefa tradicional, o interpretador de uma nova linguagem de scripting, um otimizador de consultas SQL, um matcher de regex, um monitor de segurança que executa código não confiável de jogadores em um servidor de jogo etc. parecem ter pouquíssimas considerações em comum, mas todos são máquinas virtuais
    Até dentro do formato terminfo, que especifica sequências de escape de terminais de células de texto, há uma máquina virtual baseada em pilha
    Indo mais fundo, o que faz um computador ser computador no sentido atual é a máquina virtual, e o artigo de Turing de 1936 sobre o Entscheidungsproblem também dependia do fato de máquinas virtuais poderem imitar umas às outras

• Depois de assistir à série de CPU em protoboard do Ben Eater, tudo o que quero é projetar e emular uma CPU por conta própria
  Gostaria de conseguir encontrar tempo para sentar e projetar isso

• Acho que arquiteturas educacionais como a Brookshear Machine ou o Little Computer não se parecem em nada com arquiteturas reais e são mais do que inúteis: são prejudiciais
  Já vi alunos que fizeram aulas usando esse tipo de coisa entenderem computadores de forma mais distorcida do que pessoas que não fizeram aula nenhuma
  Para a maioria das pessoas que quer aprender um pouco sobre como o próprio computador funciona, uma aula de sistemas operacionais é melhor; e, se houver tempo para apenas um tutorial curto, recomendo “Writing my own bootloader”
  https://dev.to/frosnerd/writing-my-own-boot-loader-3mld
  Isso não quer dizer que tutoriais de “Write your own VM” sejam ruins, mas sim que, pela minha experiência, outros temas seriam mais úteis para a maioria das pessoas que fariam esse tutorial

  • Acabei de mexer com LC-3 e, no projeto atual, quero usar a LC-3 como uma máquina-alvo inadequada para aprender um pouco de recompilação dinâmica
    Você poderia explicar melhor por que a LC-3 é ruim para estudar arquitetura de computadores?
    Entendo que ela é completamente diferente de hardware real e simples demais, mas fico curioso se ela também é ruim do ponto de vista de escrever um emulador de CPU
  • Isso me lembra a antiga MIX, de Knuth
    Era uma máquina decimal do tipo que poderia ter sido criada nos anos 1960, mas que ninguém mais criaria depois dos anos 1970
    Sistemas assim podem ensinar muitos fundamentos, mas as técnicas de https://en.wikipedia.org/wiki/Hacker%27s_Delight dependem principalmente de formas comuns de representação numérica, então ficam difíceis de aprender
  • Fico curioso sobre o que especificamente você não gosta na LC-3
    Como não a conheço bem, dei uma olhada rápida na Wikipedia e, depois de ver a tirinha, esperava algo estranho, mas à primeira vista não achei tão chocante
    Parece uma mistura de s/360, um pouco de x86 e um pouquinho de ARM ou de outra arquitetura da família RISC; há muitas partes omitidas e partes estranhas, mas o objetivo parece ser chegar rapidamente a uma implementação que funcione
    Gostaria de saber o que faz você considerá-la “mais do que inútil, prejudicial” para fins educacionais
  • Recomendo usar arquiteturas de 8 bits antigas, como 6502 ou Z80
    Em muitas aulas de ciência da computação na Índia, parece que ainda usam 8086/8088
  • A LC-3 tem modos de endereçamento bem peculiares
    Em especial, é possível fazer uma carga duplamente indireta por meio de uma palavra relativa ao PC no meio
    Mesmo assim, a subtração precisa ser construída a partir da negação, e a negação precisa ser construída a partir de NOT e ADD ,,#-1
    Considerando o espaço limitado de codificação de instruções, acho que NOT d,s = XOR d,s,#-1 teria sido um uso melhor

• A rigor, isso não é uma máquina virtual, mas sim um emulador
  Em sentido descritivo, o termo até pode se aplicar e, antes da era da virtualização de hardware, havia certa ambiguidade, mas hoje o uso esmagadoramente mais comum de “Virtual Machine” se refere a ambientes que usam recursos de virtualização de hardware, como VT-x

  • Não concordo que esse uso seja “esmagadoramente comum”, e também é difícil ver essa distinção como totalmente correta
    A JVM é amplamente distribuída, a Ethereum VM é chamada de EVM, https://www.linuxfoundation.org/hubfs/LF%20Research/The_Stat... também descreve repetidamente BPF e eBPF como “virtual machines”, e https://webassembly.org/ começa dizendo que “WebAssembly (abreviado como Wasm) é um formato de instruções binárias para uma máquina virtual baseada em pilha”
    “Máquina virtual” continua sendo a forma mais comum de se referir a uma máquina virtual
    Pessoalmente, gosto mais de expressões como “fictive machine”, “fictious machine”, “imaginary computer” e “fantastic automaton”, mas não acho que serão adotadas
    Nem sempre dá para usar “emulador” no lugar de “máquina virtual”
    O wasmtime talvez possa ser chamado de emulador, mas chamar o próprio WebAssembly de emulador não é preciso; WebAssembly é a máquina virtual que o wasmtime emula
    Também é comum chamar emuladores de máquinas virtuais, e uma instância de emulador em execução também é uma máquina virtual em outro sentido
    Chamar ambientes de virtualização de hardware de “máquinas virtuais” também é válido, e isso se sobrepõe em certa medida a esse último sentido
    No seu ambiente atual, esse uso pode ser esmagadoramente comum, mas isso não vale necessariamente para outros contextos
  • Com todo respeito, tenho dificuldade em concordar
    No sentido mais puro, uma máquina virtual é apenas um computador inventado, sem implicar para que será usado nem como funciona
    O texto também usa emulação de consoles clássicos como exemplo, mas, pela definição apresentada, fica claro que há muito mais máquinas virtuais possíveis
    O ponto central é que uma máquina virtual é um conceito abstrato e há muitos tipos delas
    Simuladores, emuladores, hipervisores etc. são todos máquinas virtuais, e também existem formas estranhas de máquina virtual que ainda nem receberam nome
    Não quero ser rude; pelo contrário, quero ser respeitoso e deixar esse termo claro para quem está aprendendo
  • Acho que a distinção que você está defendendo não existe de fato
    “Máquina virtual” é comumente usado para qualquer software que execute código de máquina ou bytecode, independentemente do motivo
    Pode incluir virtualização, mas também é usado com frequência para runtimes de linguagem, como a JVM do Java ou a YARV (Yet Another Ruby VM) do Ruby
    Na verdade, a área em que esse termo é menos ouvido é a emulação, em parte porque a maioria dos emuladores modernos tende a usar recompilação dinâmica do software-alvo em vez de emular o sistema inteiro
  • Este é o sentido de VM em JVM, ou seja, Java Virtual Machine
    Dá para dizer que Java se enquadra em “uso esmagadoramente comum”