🥇QEMU.js: agora para valer e com WASM

Há muito tempo, por diversão, decidi provar a reversibilidade do processo e aprender a gerar JavaScript (mais especificamente, Asm.js) a partir de código de máquina. Para o experimento, escolhi QEMU, e algum tempo depois, escrevi um artigo no Habr. Nos comentários, me sugeriram adaptar o projeto para WebAssembly, e abandonar um projeto quase finalizado não parecia uma boa ideia... O trabalho continuava, mas muito devagar, e, recentemente, aquele artigo recebeu perguntas do tipo 'E como tudo terminou?'. Em minha resposta detalhada, ouvi 'Isso merece um artigo'. Bem, se merece, haverá um artigo. Talvez seja útil para alguém. Nele, o leitor descobrirá alguns fatos sobre a estrutura dos backends de geração de código do QEMU, assim como como escrever um compilador Just-in-Time para aplicações web. comentário Como já aprendi a portar QEMU para JavaScript de forma 'mais ou menos', desta vez decidi fazer as coisas corretamente e não repetir os erros do passado.

Tarefas

Erro número um: ramificar da versão point release

Meu primeiro erro foi criar uma ramificação da versão upstream 2.4.1. Naquele momento, parecia uma boa ideia: se há uma versão point release, deve ser mais estável que a 2.4 simples, e ainda mais do que a ramificação

. E como eu planejava adicionar uma quantidade considerável de meus próprios bugs, os bugs alheios realmente não eram necessários. Assim, provavelmente, aconteceu. Mas aqui está o problema: o QEMU não para, e em algum momento até anunciaram uma otimização do código gerado de cerca de 10%. "Aham, vou integrar agora", pensei, e acabei desapontado. Aqui, é necessário fazer uma pausa: devido à natureza de thread única do QEMU.js e ao fato de que o QEMU original não prevê a ausência de multithreading (ou seja, ele se preocupa com a possibilidade de vários caminhos de código não relacionados operarem simultaneamente, e não apenas 'usar todos os núcleos'), as principais funções de threads tiveram que ser 'invertidas' para permitir chamadas externas. Isso criou alguns problemas naturais durante a fusão. No entanto, o fato de que algumas alterações da ramificação master, da qual eu tentava mesclar meu código, também foram escolhidas a dedo na versão point release (o que significa que, provavelmente, também foram para minha ramificação) não ajudou muito na conveniência. masterNo geral, decidi que o protótipo ainda fazia sentido ser descartado, desmontado e construir uma nova versão do zero com algo mais atualizado e agora já com

Erro número dois: metodologia TLP master.

Ошибка номер два: ТЛП-методология

Na essência, isso não é bem um erro, na verdade — apenas uma particularidade da criação do projeto em condições de total desconhecimento sobre "para onde e como avançar?", e mesmo "vamos conseguir chegar lá?". Nessas condições, programação feita de qualquer jeito , era uma opção justificada, mas, claro, não queria repetir isso sem necessidade. Desta vez, queria fazer da maneira certa: commits atômicos, mudanças de código conscientes (e não "juntar caracteres aleatórios até compilar (com avisos)", como alguém um dia disse Linus Torvalds, se acreditar na Wikiquotes) e assim por diante.

Erro número três: não saber nadar e se jogar na água

Disso eu ainda não me livrei completamente, mas agora decidi não seguir o caminho da menor resistência e fazer "como um adulto", ou seja, escrever meu próprio backend TCG do zero, para não ter que dizer depois "Sim, isso, claro, é lento, mas não posso controlar tudo — TCI foi feito assim…". Além disso, inicialmente parecia uma solução óbvia, uma vez que eu gero código binário. Como se diz, "Juntei Gent,umas não o certo": o código é, claro, binário, mas o controle não pode ser passado assim, ele precisa ser explicitamente empurrado para o navegador para compilação, resultando em um objeto do mundo JS que ainda precisa ser salvo em algum lugar. No entanto, em arquiteturas RISC normais, pelo que entendo, a situação típica é a necessidade de limpar o cache de instruções para o código regenerado — se isso não é exatamente o que precisamos, é, de qualquer forma, parecido. Além disso, da minha tentativa anterior, aprendi que o controle não é passado para o meio do bloco de tradução, então o bytecode, interpretado a partir de qualquer deslocamento, não é de particular necessidade, e podemos simplesmente gerar por função no TB.

Chegaram e deram uma cutucada

Embora eu tenha começado a reescrever o código em julho, o empurrão mágico veio de forma sutil: normalmente, os e-mails do GitHub chegam como notificações sobre respostas em Issues e Pull requests, mas aqui, de repente uma menção em um thread Binaryen como um backend qemu no contexto de â€œOlha, ele fez algo assim, pode dizer alguma coisa”. A conversa era sobre a utilização da biblioteca relacionada ao Emscripten, Binaryen para criar WASM JIT. E eu disse que lá a licença é Apache 2.0, enquanto o QEMU como um todo é distribuído sob GPLv2, e isso não combina muito bem. De repente, descobriu-se que a licença poderia ser de alguma forma ajustada (não sei: talvez trocar, talvez licenciamento duplo, talvez outra coisa...). Isso me deixou contente, porque já havia olhado algumas vezes para o formato binário WebAssembly, e isso me deixava um pouco triste e confuso. Aqui havia uma biblioteca que poderia consumir os blocos básicos com o gráfico de transições, gerar o bytecode e até mesmo executá-lo em um interpretador, se necessário.

Depois, houve uma carta na lista de distribuição do QEMU, mas isso já está mais associado à questão: "E para quem isso realmente serve?". E, na verdade, de repente, acabou sendo útil. Pelo menos, é possível reunir algumas possibilidades de uso, se funcionar mais ou menos rápido:

executar algo educacional sem instalação
virtualização no iOS, onde, pelos rumores, o único aplicativo com permissão para geração de código em tempo real é o motor JS (e será que isso é verdade?)
demonstração de mini-OS — disquetes únicos, embarcados, várias firmwares, etc.

Características do ambiente de execução do navegador

Como já mencionei, o QEMU é baseado em multithreading, mas no navegador isso não existe. Bem, quer dizer, não existia... Primeiramente, não havia de forma alguma, depois surgiram os WebWorkers — pelo que entendi, isso é uma forma de multithreading baseada em troca de mensagens sem variáveis compartilhadas. Naturalmente, isso cria problemas significativos ao portar código existente, que se baseia em um modelo de memória compartilhada. Depois, sob pressão do público, isso foi implementado e ficou conhecido como SharedArrayBuffers. Foi gradualmente introduzido, celebraram seu lançamento em diferentes navegadores, depois comemoraram o ano novo, e então veio o Meltdown... Após isso, chegaram à conclusão de que, não importa quão ajustado seja o tempo de medida, com a memória compartilhada e a thread, que incrementa o contador, ainda assim resultaria bastante preciso. Então, as funcionalidades de multithreading com memória compartilhada foram desativadas. Parece que depois tentaram reativá-las, mas, conforme ficou claro no primeiro experimento, mesmo sem isso a vida existe, e assim, vamos tentar fazer, sem contar com multithreading.

A segunda característica é a impossibilidade de manipulações de baixo nível na pilha: não se pode simplesmente pegar, salvar o contexto atual e alternar para um novo com uma nova pilha. A pilha de chamadas é gerida pela máquina virtual JS. Qual seria o problema, uma vez que decidimos lidar completamente com os antigos threads manualmente? O fato é que a entrada e saída em bloco no QEMU é implementada através de corrotinas, e aqui precisaríamos das manipulações de baixo nível da pilha. Felizmente, o Emscripten já possui um mecanismo para operações assíncronas, até mesmo dois: Asyncify e Emterpreter. O primeiro funciona através de uma expansão significativa do código JavaScript gerado e já não é mais suportado. O segundo é o atual 'caminho correto' e funciona através da geração de bytecode para seu próprio interpretador. Funciona, claro, lentamente, mas não expande o código. O problema é que o suporte para corrotinas para esse mecanismo precisou ser contribuído manualmente (já existiam corrotinas escritas para Asyncify e havia uma implementação de API mais ou menos equivalente para Emterpreter, só precisavam ser conectadas).

Até o momento, ainda não consegui separar o código em compilável para WASM e interpretável com Emterpreter, portanto, os dispositivos em bloco ainda não funcionam (veja nas próximas edições, como se diz...). Ou seja, no final, deve resultar em algo divertido como:

entrada e saída em bloco interpretáveis. E aí, você realmente esperava um NVMe emulado com desempenho nativo? 🙂
código principal do QEMU compilado estaticamente (tradutor, outros dispositivos emulados etc.)
código do convidado compilado dinamicamente em WASM

Características dos fontes do QEMU

Como você provavelmente já deve ter adivinhado, o código de emulação das arquiteturas convidadas e o código de geração de instruções de máquina do host no QEMU estão separados. Na verdade, é até um pouco mais complicado:

Existem arquiteturas convidadas
tem aceleradores, nomeadamente, KVM para virtualização de hardware no Linux (para sistemas convidados e host compatíveis entre si), TCG para geração de código JIT onde for necessário. A partir do QEMU 2.9, foi adicionada a suporte ao padrão de virtualização de hardware HAXM no Windows (detalhes)
se TCG é usado em vez de virtualização de hardware, ele possui suporte separado para geração de código para cada arquitetura de host, bem como para um interpretador universal.
… e em torno de tudo isso, temos a periferia emulada, a interface do usuário, migração, gravação-reprodução, etc.

Aliás, você sabia que: O QEMU pode emular não apenas um computador inteiro, mas também um processador para um processo de usuário separado no núcleo do host, o que é utilizado, por exemplo, pelo fuzzer AFL para instrumentação de binários. Talvez alguém queira portar esse modo de operação do QEMU para JS? 😉

Como a maioria dos programas livres que existem há muito tempo, o QEMU é compilado através de uma chamada. configure e makeSuponha que você decidiu adicionar algo: um backend TCG, uma implementação de threads, ou algo mais. Não se apresse em ficar animado/desesperado (marque o que for necessário) com a perspectiva de lidar com o Autoconf — na verdade, configure o QEMU, aparentemente, possui um gerador de código próprio e não é gerado a partir de nada.

WebAssembly

Então, o que é esse negócio — WebAssembly (também conhecido como WASM)? É uma substituição para o Asm.js, que agora não se finge mais de código JavaScript válido. Pelo contrário, é estritamente binário e otimizado, e até mesmo simplesmente gravar um número inteiro nele não é tão fácil: ele é armazenado em um formato compactado. LEB128.

Você pode ter ouvido falar do algoritmo de relooping para Asm.js — é a recuperação de instruções de controle de fluxo "de alto nível" (ou seja, if-then-else, loops, etc.), para as quais os motores JS são otimizados, a partir de IR LLVM de baixo nível, mais próximo do código de máquina executado pelo processador. Naturalmente, a representação intermediária do QEMU está mais próxima da segunda. Parece que temos o bytecode, o fim dos sofrimentos… E então aparecem os blocos, if-then-else e loops!...

E essa é mais uma razão pela qual o Binaryen é útil: ele, naturalmente, pode aceitar blocos de alto nível, próximos ao que será salvo em WASM. Mas também pode gerar código a partir de um grafo de blocos básicos e transições entre eles. Bem, sobre o que ele oculta sob a conveniente API C/C++ do formato de armazenamento do WebAssembly, já falei.

TCG (Tiny Code Generator)

TCG originalmente foi backend para o compilador C. Depois, aparentemente, não suportou a concorrência com o GCC, mas acabou encontrando seu lugar na composição do QEMU como um mecanismo de geração de código para a plataforma host. Também existe um backend TCG, que gera um código byte abstrato que é imediatamente executado pelo interpretador, mas decidi evitar seu uso desta vez. No entanto, o fato de que o QEMU já tem a possibilidade de incluir a transição para TB gerado através da função tcg_qemu_tb_exec, foi muito conveniente para mim.

Para adicionar um novo backend TCG ao QEMU, você precisa criar um subdiretório tcg/ (neste caso, tcg/binaryen), e dentro dele dois arquivos: tcg-target.h e tcg-target.inc.c e declarar tudo isso em configure. Você pode colocar outros arquivos lá, mas, como pode adivinhar pelos nomes desses dois, ambos serão incluídos em algum lugar: um como um arquivo de cabeçalho normal (ele é incluído em tcg/tcg.h, e aquele já em outros arquivos nos diretórios tcg, accel e não só), o outro — apenas como um código snippet em tcg/tcg.c, mas ele tem acesso às suas funções estáticas.

Decidindo que iria gastar muito tempo em investigações detalhadas sobre como tudo funcionava, simplesmente copiei os «esqueletos» desses dois arquivos de outra implementação de backend, indicando isso honestamente no cabeçalho da licença.

Arquivo tcg-target.h contém predominantemente configurações na forma de #define-s:

quantos registradores e qual largura há na arquitetura alvo (no nosso caso — quantos quisermos, a questão é mais sobre o que será gerado em um código mais eficiente pelo navegador na arquitetura «totalmente alvo»…)
alinhamento das instruções host: no x86, e mesmo no TCI, as instruções não são alinhadas, eu pretendo colocar no buffer de código não instruções, mas ponteiros para estruturas da biblioteca Binaryen, então direi: 4 bytes
quais instruções opcionais o backend pode gerar — vamos incluir tudo o que encontrarmos no Binaryen, o resto deixa para o acelerador dividir em mais simples.
qual é o tamanho aproximado do cache TLB que o backend requer. A questão é que no QEMU tudo é muito sério: embora existam funções auxiliares que realizam load/store considerando o MMU do convidado (como poderia ser diferente?), mas seu cache de tradução é mantido na forma de uma estrutura, cuja manipulação é conveniente de embutir diretamente nos blocos de tradução. A questão é qual deslocamento nessa estrutura é processado de forma mais eficiente por uma sequência curta e rápida de comandos.
aqui também é possível ajustar a designação de um ou dois registradores reservados, ativar a chamada TB através de uma função e opcionalmente descrever algumas pequenas funções. inline-funções como flush_icache_range (mas esse não é o nosso caso)

Arquivo tcg-target.inc.c, naturalmente, é geralmente muito maior em tamanho e contém várias funções obrigatórias:

inicialização, que também indica as restrições sobre quais instruções podem trabalhar com quais operandos. Foi descaradamente copiada de outro backend.
uma função que aceita uma instrução de bytecode interno.
aqui também é possível colocar funções auxiliares, e aqui pode-se também usar funções estáticas de tcg/tcg.c

Para mim, eu escolhi a seguinte estratégia: nas primeiras palavras de cada bloco de tradução, eu registrava quatro ponteiros: o rótulo de início (um certo valor em torno de 0xFFFFFFFF, que determinava o estado atual do TB), o contexto, o módulo gerado e um número mágico para depuração. Inicialmente, o rótulo era definido como 0xFFFFFFFF - n, onde n — um pequeno número positivo, e a cada execução através do interpretador, aumentava em 1. Quando alcançava 0xFFFFFFFE, ocorria a compilação, o módulo era salvo na tabela de funções, importada em um pequeno "iniciador", para onde a execução ia tcg_qemu_tb_exec, e o módulo era removido da memória do QEMU.

Reformulando um clássico, "Gambiarras, quão muito neste som se entrelaça para o coração do programador...". No entanto, a memória estava vazando para algum lugar. E adivinha? Era a memória controlada pelo QEMU! Eu tinha um código que, ao gravar uma nova instrução (ou seja, um ponteiro), removia aquela que estava referenciada anteriormente nesse lugar, mas isso não ajudava. Na verdade, no caso mais simples, o QEMU aloca memória no início e escreve o código gerado nela. Quando o buffer se esgota, o código é descartado e, em seu lugar, começa a ser gravado o próximo.

Após analisar o código, percebi que a solução com o número mágico permitia evitar falhas na manipulação da pilha, liberando algo indevido em um buffer não inicializado na primeira passagem. Mas quem reescreve o buffer contornando minha função depois? Como recomendam os desenvolvedores do Emscripten, ao me deparar com o problema, eu portei o código resultante de volta para um aplicativo nativo e o teste com o Mozilla Record-Replay... No final, entendi uma coisa simples: para cada bloco é reservado struct TranslationBlock com sua descrição. Adivinhe onde... Isso mesmo, diretamente antes do bloco no buffer. Reconhecendo isso, decidi deixar os gambiarras de lado (pelo menos algumas) e simplesmente removi o número mágico, transferindo as palavras restantes para struct TranslationBlock, criando uma lista encadeada, pela qual é possível percorrer rapidamente ao limpar o cache de tradução e liberar memória.

Algumas gambiarras permaneceram: por exemplo, ponteiros marcados no buffer de código - parte deles na verdade são BinaryenExpressionRef, ou seja, referenciam expressões que precisam ser linearmente inseridas no bloco básico gerado, alguns - a condição de transição entre os blocos básicos, e outros - para onde transitar. Além disso, já existem blocos preparados para o Relooper, que devem ser conectados com base em condições. Para diferenciá-los, presume-se que todos eles estão alinhados em pelo menos quatro bytes, portanto, é seguro usar os dois bits menos significativos como identificador, só não esqueça de removê-lo quando necessário. Aliás, esses identificadores já são utilizados no QEMU para indicar o motivo da saída do ciclo TCG.

Uso do Binaryen

Os módulos em WebAssembly contêm funções, cada uma das quais possui um corpo que representa uma expressão. Expressões são operações unárias e binárias, blocos compostos de listas de outras expressões, controle de fluxo, etc. Como já mencionei, o controle de fluxo aqui é organizado como ramificações de alto nível, ciclos, chamadas de funções, etc. Os argumentos para as funções não são passados na pilha, mas explicitamente, assim como no JS. Existem variáveis globais, mas eu não as utilizei, então não falarei sobre elas.

As funções possuem variáveis locais numeradas a partir de zero, com tipos: int32 / int64 / float / double. Vale ressaltar que as primeiras n variáveis locais são os argumentos passados para a função. Embora isso não seja totalmente de baixo nível em termos de controle de fluxo, os números inteiros ainda não possuem a característica de "sinalizado / não sinalizado": como um número se comporta depende do código da operação.

De maneira geral, o Binaryen fornece uma API C simples: você cria um módulo, neste cria expressões — unárias, binárias, blocos de outras expressões, controle de fluxo etc. Depois, você cria uma função, cujo corpo deve ser uma expressão. Se você, assim como eu, tem um gráfico de transição de baixo nível — o componente relooper pode ajudar. Pelo que entendo, é possível usar um controle de fluxo de alto nível dentro do bloco desde que não ultrapasse os limites do bloco — ou seja, é permitido fazer ramificações internas fast path / slow path dentro do código embutido de manipulação do cache TLB, mas intervir no fluxo de controle "externo" não é permitido. Ao liberar o relooper, seus blocos são liberados; ao liberar o módulo, as expressões, funções etc., alocadas em sua arena.

No entanto, se você desejar interpretar o código em tempo real sem criar e destruir instâncias do interpretador de maneira excessiva, pode ser sensato mover essa lógica para um arquivo em C++ e gerenciar diretamente toda a API C++ da biblioteca, ignorando as wrappers prontas.

Assim, para gerar código, é necessário

// настроить глобальные параметры (можно поменять потом)
BinaryenSetAPITracing(0);

BinaryenSetOptimizeLevel(3);
BinaryenSetShrinkLevel(2);

// создать модуль
BinaryenModuleRef MODULE = BinaryenModuleCreate();

// описать типы функций (как создаваемых, так и вызываемых)
helper_type  BinaryenAddFunctionType(MODULE, "helper-func", BinaryenTypeInt32(), int32_helper_args, ARRAY_SIZE(int32_helper_args));
// (int23_helper_args приоб^Wсоздаются отдельно)

// сконструировать супер-мега выражение
// ... ну тут уж вы как-нибудь сами :)

// потом создать функцию
BinaryenAddFunction(MODULE, "tb_fun", tb_func_type, func_locals, FUNC_LOCALS_COUNT, expr);
BinaryenAddFunctionExport(MODULE, "tb_fun", "tb_fun");
...
BinaryenSetMemory(MODULE, (1 << 15) - 1, -1, NULL, NULL, NULL, NULL, NULL, 0, 0);
BinaryenAddMemoryImport(MODULE, NULL, "env", "memory", 0);
BinaryenAddTableImport(MODULE, NULL, "env", "tb_funcs");

// запросить валидацию и оптимизацию при желании
assert (BinaryenModuleValidate(MODULE));
BinaryenModuleOptimize(MODULE);

… Se eu esqueci de algo — desculpe, isso é apenas para dar uma ideia da escala, e os detalhes estão na documentação.

E agora começa a parte complexa, mais ou menos assim:

static char buf[1 << 20];
BinaryenModuleOptimize(MODULE);
BinaryenSetMemory(MODULE, 0, -1, NULL, NULL, NULL, NULL, NULL, 0, 0);
int sz = BinaryenModuleWrite(MODULE, buf, sizeof(buf));
BinaryenModuleDispose(MODULE);
EM_ASM({
  var module = new WebAssembly.Module(new Uint8Array(wasmMemory.buffer, $0, $1));
  var fptr = $2;
  var instance = new WebAssembly.Instance(module, {
      'env': {
          'memory': wasmMemory,
          // ...
      }
  );
  // E agora você já tem uma instance!
}, buf, sz);

Para conectar o mundo do QEMU e do JS e, ao mesmo tempo, acessar rapidamente as funções compiladas, foi criado um array (uma tabela de funções para importação no launcher), onde as funções geradas eram armazenadas. Para calcular rapidamente o índice, inicialmente foi utilizado o índice da palavra zero do bloco de tradução, mas depois o índice calculado por tal fórmula passou a ser simplesmente inserido no campo em struct TranslationBlock.

A propósito, demonstração (com licença ainda indefinida) funciona corretamente apenas no Firefox. Os desenvolvedores do Chrome estavam meio despreparados para o fato de que alguém quisesse criar mais de mil instâncias de módulos WebAssembly, por isso alocavam apenas um gigabyte de espaço de endereço virtual por cada uma...

Por enquanto, é tudo. Pode haver um novo artigo se isso interessar a alguém. A saber, resta pelo menos apenas fazer com que dispositivos de bloco funcionem. Pode ser que também faça sentido tornar a compilação de módulos WebAssembly assíncrona, como é comum no mundo do JS, já que, de qualquer forma, existe um interpretador que pode executar tudo isso enquanto o módulo nativo não está pronto.

Por último, uma charada: você compilou um binário para uma arquitetura de 32 bits, mas o código através de operações de memória acessa o Binaryen, indo para a pilha ou para algum lugar nos 2 GB superiores do espaço de endereço de 32 bits. O problema é que do ponto de vista do Binaryen isso é um acesso a um endereço resultante muito grande. Como contornar isso?

Administrativamente

Eu não testei isso no final, mas a primeira ideia foi "E se eu instalar um Linux de 32 bits?" Assim, a parte superior do espaço de endereço será ocupada pelo kernel. A única questão é quanto vai ser ocupado: 1 ou 2 GB.

Programaticamente (opção para praticantes)

Vamos inflar uma bolha na parte superior do espaço de endereço. Eu mesmo não entendo por que isso funciona — lá deveria já haver uma pilha. Mas "nós praticantes: tudo funciona, mas ninguém sabe por quê...".

// 2gbubble.c
// Usage: LD_PRELOAD=2gbubble.so <program>

#include <sys/mman.h>
#include <assert.h>

void __attribute__((constructor)) constr(void)
{
  assert(MAP_FAILED != mmap(1u >> 31, (1u >> 31) - (1u >> 20), PROT_NONE, MAP_ANONYMOUS | MAP_PRIVATE, -1, 0));
}

… não é compatível com o Valgrind, mas, felizmente, o Valgrind é muito eficiente em expulsá-los de lá 🙂

Talvez alguém ofereça uma explicação melhor de como meu código funciona...

Fonte: habr.com