QEMU.js: agora a sério e com WASM

Era uma vez, por uma questão de riso, decidi provar a reversibilidade do processo e aprender a gerar JavaScript (ou melhor, Asm.js) a partir do código da máquina. QEMU foi escolhido para o experimento; algum tempo depois, um artigo foi escrito sobre Habr. Nos comentários, fui aconselhado a refazer o projeto no WebAssembly, e eu mesmo não estava com vontade de deixar o projeto quase concluído ... O trabalho continuou, mas muito lentamente, e agora, nesse artigo, um comentário apareceu no tópico "Então, como ele terminou?". Para minha resposta detalhada, ouvi "Ele puxa um artigo". Bem, se puxar, haverá um artigo. Talvez alguém venha a calhar. A partir disso, o leitor aprende alguns fatos sobre a geração de códigos do QEMU para o back-end do dispositivo, bem como como escrever um compilador Just-in-Time para um aplicativo da web.

As tarefas

Desde que eu já aprendi como "portar" o QEMU para JavaScript, desta vez foi decidido fazê-lo com sabedoria e não repetir erros antigos.

Número de vezes do erro: ramificação do ponto

Meu primeiro erro foi ramificar minha versão da versão upstream 2.4.1. Então me pareceu uma boa idéia: se a liberação de pontos existe, provavelmente é mais estável do que um simples 2.4 e, mais ainda, um ramo master . E como eu planejava adicionar uma boa quantidade de meus erros, não precisava de estranhos. Então provavelmente aconteceu. Mas aqui está a má sorte: o QEMU não fica parado e, em algum momento, eles até anunciaram a otimização do código percentual gerado em 10. "Sim, agora estou congelando", pensei e interrompeu . Aqui, devemos fazer uma digressão: devido à natureza de thread único do QEMU.js e ao fato de o QEMU original não implicar a ausência de multithreading (ou seja, é fundamental que ele possa operar vários caminhos de código não relacionados ao mesmo tempo, e não apenas "conectar todos os kernels"), as principais funções dos threads teve que "sair" para poder ligar de fora. Isso criou alguns problemas naturais de fusão. No entanto, o fato de que algumas das alterações do ramo master , com as quais tentei mesclar meu código, também foram escolhidas na versão point point (e, portanto, no meu ramo), provavelmente também não adicionariam conveniência.

Em geral, eu decidi que de qualquer maneira o protótipo faz sentido jogar fora desmonte as peças e construa uma nova versão do zero com base em algo mais atual e agora do master .

Erro número dois: metodologia TLP

De fato, isso não é um erro, em geral - é apenas uma característica da criação de um projeto nas condições de completo mal-entendido de "para onde e como mudar?". E, em geral, "chegaremos lá?". Nessas condições, a programação era uma opção justificável, mas, é claro, eu absolutamente não queria repeti-la desnecessariamente. Desta vez, eu queria fazer isso com sabedoria: confirmações atômicas, alterações deliberadas de código (e não "agrupar caracteres aleatórios até compilar (com avisos)"), como Linus Torvalds disse sobre alguém, se você acredita no Wikitatnik), etc.

Erro número três: não conhecer o vau para entrar na água

Ainda não me livrei completamente disso, mas agora decidi não seguir o caminho de menor resistência e fazê-lo "de maneira adulta", ou seja, escrevo meu backend do TCG do zero para não dizer mais tarde: "Sim, é Claro, devagar, mas não consigo controlar tudo - o TCI está escrito assim ... ". Além disso, inicialmente isso parecia uma solução óbvia, pois eu estava gerando código binário . Como diz o ditado, "eu coletei Ghent, mas não esse": o código é, obviamente, binário, mas o controle não pode ser transferido para ele exatamente assim - ele precisa ser explicitamente empurrado para o navegador para compilação, resultando em um determinado objeto do mundo JS, que ainda precisa salvar em algum lugar. No entanto, em normal Arquiteturas RISC, como eu a entendo, uma situação típica é a necessidade de liberar explicitamente o cache de instruções para o código regenerado - se não é isso que precisamos, então, pelo menos, está próximo. Além disso, na minha última tentativa, aprendi que o controle não parece ser transferido para o meio do bloco de conversão; portanto, não precisamos realmente do bytecode interpretado de qualquer deslocamento, e podemos simplesmente gerar por função no TB.

Veio e chutou

Embora eu tenha começado a reescrever o código em julho, o pendell mágico passou despercebido: geralmente as cartas do GitHub são recebidas como notificações de respostas a solicitações de Issues e Pull e, de repente , o Binaryen como back-end do qemu no contexto diz : “Aqui está- ele fez algo assim, talvez ele diga alguma coisa. ” Tratava-se de usar a biblioteca Binaryen relacionada ao Emscripten para criar um JAS do WASM. Bem, eu disse que você tem uma licença do Apache 2.0 e o QEMU como um todo é distribuído sob a GPLv2, e eles não são muito compatíveis. De repente, descobriu-se que a licença poderia ser de alguma forma corrigida (não sei: talvez, altere, talvez o licenciamento duplo, talvez outra coisa ...). Isso, é claro, me deixou feliz, porque eu já tinha visto o Webinarembly de formato binário várias vezes naquela época e, de alguma forma, era triste e incompreensível para mim. Havia uma biblioteca aqui que devorará os blocos básicos com o gráfico de transição, emitirá o bytecode e até o lançará no intérprete, se necessário.

Havia também uma carta na lista de discussão da QEMU, mas é mais provável que a pergunta "Quem precisa disso?" E, de repente , foi necessário. No mínimo, você pode agrupar esses casos de uso se funcionar de maneira mais ou menos inteligente:

• lançando qualquer coisa ensinando sem nenhuma instalação
• virtualização no iOS, onde, segundo os rumores, o único aplicativo que tem o direito de gerar código em tempo real é o mecanismo JS (isso é verdade?)
• demonstração do mini-SO - disco único, embutido, todos os tipos de firmware, etc ...

Recursos do tempo de execução do navegador

Como eu disse, o QEMU está vinculado ao multithreading, mas não está no navegador. Bem, isto é, como não ... No começo, não estava lá, então os WebWorkers apareceram - pelo que entendi, isso é multithreading com base na passagem de mensagens sem variáveis mutuamente variáveis . Naturalmente, isso cria problemas significativos ao transportar o código existente com base em um modelo de memória compartilhada. Então, sob pressão do público, foi implementado sob o nome SharedArrayBuffers . Eles o introduziram gradualmente, comemoraram seu lançamento em diferentes navegadores, comemoraram o ano novo e depois o colapso ... Após o que chegaram à conclusão de que é rude, não rude, a medição do tempo, mas com a ajuda da memória compartilhada e um fluxo que incrementa o contador, ainda é bastante preciso . Então, eles desativaram o multithreading com memória compartilhada. Parece que eles mais tarde ligaram novamente, mas, como ficou claro desde o primeiro experimento, há vida sem ele e, nesse caso, tentaremos fazê-lo sem depender de multithreading.

O segundo recurso é a impossibilidade de manipulações de baixo nível com a pilha: você não pode simplesmente pegar, salvar o contexto atual e alternar para um novo com uma nova pilha. A pilha de chamadas é gerenciada pela máquina virtual JS. Parece, qual é o problema, já que ainda decidimos gerenciar os fluxos anteriores completamente manualmente? O fato é que o bloco de entrada e saída no QEMU é implementado através de corotinas, e aqui as manipulações de pilha de baixo nível seriam úteis para nós. Felizmente, o Emscipten já contém um mecanismo para operações assíncronas, até duas: Asyncify e Emterpreter . O primeiro funciona através do inchaço significativo do código JavaScript gerado e não é mais suportado. A segunda é a atual "maneira correta" e funciona através da geração de bytecode para seu próprio intérprete. Obviamente, funciona devagar, mas não inflaciona o código. É verdade que o suporte à corotina para esse mecanismo tinha que ser atribuído por conta própria (já havia corotinas escritas em Asyncify e havia uma implementação aproximadamente da mesma API para o Emterpreter, você só precisava conectá-las).

No momento, ainda não consegui dividir o código em compilado no WASM e interpretado usando o Emterpreter, para que os dispositivos de bloco ainda não funcionem (veja a próxima série, como se costuma dizer ...). Ou seja, no final, você deve obter algo tão engraçado em camadas:

• bloco I / O interpretado. Bem, o que você realmente esperava de um NVMe emulado com desempenho nativo? :)
• código QEMU principal compilado estaticamente (tradutor, outros dispositivos emulados etc.)
• Código de convidado compilado dinamicamente WASM

Recursos de fontes QEMU

Como você provavelmente já adivinhou, o código de emulação para arquiteturas convidadas e o código para gerar instruções da máquina host do QEMU são separados. De fato, há ainda um pouco mais complicado:

• existem arquiteturas convidadas
• existem aceleradores , a saber, o KVM para virtualização de hardware no Linux (para sistemas de convidados e hosts compatíveis), o TCG para geração de código JIT em qualquer lugar. A partir do QEMU 2.9, apareceu o suporte para o padrão de virtualização de hardware HAXM no Windows ( detalhes )
• se o TCG for usado, e não a virtualização de hardware, ele terá suporte separado para geração de código para cada arquitetura de host e para um intérprete universal
• ... e tudo mais - periféricos emulados, interface do usuário, migração, repetição de registros etc.

A propósito, você sabia: o QEMU pode emular não apenas o computador inteiro, mas também o processador para um processo de usuário separado no kernel host, que é usado, por exemplo, pelo fuzzer AFL para instrumentação de binários. Talvez alguém queira portar esse modo de operação QEMU para JS? ;)

Como a maioria dos programas gratuitos de longa data, o QEMU é construído através de uma chamada para configure e make . Suponha que você decida adicionar algo: um back-end do TCG, uma implementação de encadeamento, outra coisa. Não se apresse para se alegrar / ficar horrorizado (sublinhe conforme necessário) a perspectiva de se comunicar com o Autoconf - de fato, o configure no QEMU parece ser auto-escrito e não há nada para gerar.

Webassembly

Então, o que é isso - WebAssembly (também conhecido como WASM)? Esta é uma substituição do Asm.js, agora não mais fingindo ser um código JavaScript válido. Pelo contrário, é puramente binário e otimizado, e até mesmo escrever um número inteiro nele não é muito simples: é armazenado no formato LEB128 para compactação .

Você já deve ter ouvido falar sobre o algoritmo de recolocação do Asm.js. Essa é a restauração das instruções de controle de fluxo de execução de "alto nível" (ou seja, se-então-outro, loops etc.) sob as quais os mecanismos JS são ajustados no LLVM IR de baixo nível, mais perto do código da máquina executado pelo processador. Naturalmente, a representação intermediária do QEMU está mais próxima do segundo. Parece que aqui está, bytecode, o fim do tormento ... E então os blocos, if-then-else e loops! ..

E esse é outro motivo pelo qual o Binaryen é útil: é claro, ele pode aceitar blocos de alto nível próximos ao que será armazenado no WASM. Mas também pode produzir código a partir do gráfico de blocos base e transições entre eles. Bem, eu já disse que oculta o formato de armazenamento do WebAssembly atrás da conveniente API C / C ++.

TCG (Gerador de código minúsculo)

O TCG era originalmente um back - end para o compilador C. Então, aparentemente, não conseguiu resistir à concorrência com o GCC, mas no final encontrou seu lugar no QEMU como um mecanismo de geração de código para a plataforma host. Há também um back-end do TCG que gera algum bytecode abstrato, que é imediatamente executado pelo intérprete, mas decidi sair dessa vez. No entanto, o fato de o QEMU já ter a capacidade de permitir a transição para a TB gerada por meio da função tcg_qemu_tb_exec foi muito útil para mim.

Para adicionar um novo backend do TCG ao QEMU, é necessário criar um subdiretório tcg/< > (neste caso, tcg/binaryen ) e há dois arquivos nele: tcg-target.h tcg-target.inc.c e registre tudo isso é configure . Você pode colocar outros arquivos lá, mas, como você pode adivinhar pelos nomes desses dois, eles serão incluídos em algum lugar: um como um arquivo de cabeçalho comum (ele será incluído em tcg/tcg.h e esse já estará em outros arquivos nos diretórios tcg , accel e não apenas), o outro apenas como trecho de código em tcg/tcg.c , mas tem acesso a suas funções estáticas.

Tendo decidido que gastaria muito tempo com os procedimentos detalhados, como funciona, simplesmente copiei os "esqueletos" desses dois arquivos de outra implementação de back-end, indicando honestamente isso no cabeçalho da licença.

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

• quantos registros e qual a largura da arquitetura de destino (temos - tanto quanto queremos, existem tantos - a questão é mais do que o navegador gerará em um código mais eficiente em uma arquitetura "completamente de destino")
• alinhamento das instruções do host: no x86, e no TCI, as instruções não se alinham, mas vou colocar no buffer de código nenhuma instrução, mas ponteiros para as estruturas da biblioteca Binaryen, então direi: 4 bytes
• que instruções opcionais o back-end pode gerar - ligue tudo o que encontramos em Binaryen, deixe o acelerador dividir o resto em outros mais simples
• qual tamanho aproximado do cache TLB é solicitado pelo back-end. O fato é que, no QEMU, tudo é sério: embora existam funções auxiliares que carregam / armazenam, levando em consideração a MMU convidada (e onde agora está sem ela?), Elas salvam seu cache de tradução na forma de uma estrutura, cujo processamento é conveniente para incorporar diretamente para os blocos de tradução. A questão é: qual deslocamento nessa estrutura é tratado com mais eficiência por uma pequena e rápida sequência de comandos
• aqui você pode alterar o objetivo de um ou dois registros reservados, ativar a chamada de TB através de uma função e, opcionalmente, descrever algumas pequenas funções inline , como flush_icache_range (mas esse não é o nosso caso)

O tcg-target.inc.c , é claro, geralmente é muito maior e contém várias funções necessárias:

• inicialização, indicando, inter alia, restrições sobre quais instruções com quais operandos podem trabalhar. Copiado insolentemente por mim de outro back-end
• função que aceita uma instrução de bytecode interno
• aqui você pode colocar funções auxiliares e também aqui você pode usar funções estáticas em tcg/tcg.c

Para mim, escolhi a seguinte estratégia: nas primeiras palavras do próximo bloco de transmissão, escrevi quatro ponteiros: a marca de início (um certo valor próximo a 0xFFFFFFFF , que determinava o estado atual da TB), o contexto, o módulo gerado e o número mágico para depuração. Primeiro, o rótulo foi definido como 0xFFFFFFFF - n , onde n é um número positivo pequeno e, a cada vez que o interpretador era aumentado em 1. Quando alcançava 0xFFFFFFFE , ocorria a compilação, o módulo era armazenado na tabela de funções, importado para um pequeno "iniciador", no qual A execução deixou tcg_qemu_tb_exec e o módulo foi excluído da memória QEMU.

Parafraseando os clássicos: "Muleta, quanto proger se entrelaçou nesse som para o coração ...". No entanto, a memória estava vazando em algum lugar. E era uma memória gerenciada pelo QEMU! Eu tinha um código que, ao escrever a próxima instrução (ou seja, um ponteiro), excluiu aquela cujo link estava neste local anteriormente, mas que não ajudou. Na verdade, no caso mais simples, o QEMU aloca memória na inicialização e grava o código gerado lá. Quando o buffer termina, o código é descartado e o próximo começa a ser escrito em seu lugar.

Tendo estudado o código, percebi que a muleta com número mágico nos permitia não cair na destruição da pilha, liberando algo errado no buffer não inicializado na primeira passagem. Mas quem substitui o buffer ignorando minha função posteriormente? Como os desenvolvedores do Emscripten aconselharam, tendo encontrado um problema, eu carreguei o código resultante de volta para o aplicativo nativo, coloquei o Mozilla Record-Replay nele ... Em geral, como resultado, percebi uma coisa simples: um struct TranslationBlock com sua descrição é alocado para cada bloco. Adivinhe onde ... Está certo, bem na frente do bloco, no buffer. Tendo percebido isso, decidi amarrá-lo com muletas (pelo menos algumas), e simplesmente joguei o número mágico e transferi as palavras restantes para o struct TranslationBlock , criando uma lista de vínculo único que você pode acessar rapidamente ao redefinir o cache de tradução e liberar memória.

Algumas muletas permaneceram: por exemplo, ponteiros marcados no buffer de código - alguns deles são simplesmente BinaryenExpressionRef , ou seja, eles examinam expressões que precisam ser linearmente colocadas na unidade base gerada, parte - a condição de transição entre os WBs, parte - para onde ir. Bem, já existem blocos preparados para o Relooper, que devem ser conectados de acordo com as condições. Para distinguir entre eles, é utilizado o pressuposto de que todos estão alinhados com pelo menos quatro bytes, para que você possa usar com segurança os dois bits inferiores do rótulo, basta lembrar de removê-lo, se necessário. A propósito, esses rótulos já são usados ​​no QEMU para indicar o motivo da saída do ciclo do TCG.

Usando Binaryen

Os módulos no WebAssembly contêm funções, cada uma contendo um corpo que representa uma expressão. Expressões são operações unárias e binárias, blocos constituídos por listas de outras expressões, fluxo de controle etc. Como eu já disse, o fluxo de controle aqui é organizado precisamente como ramificações de alto nível, loops, chamadas de função etc. Argumentos para funções são passados ​​não na pilha, mas explicitamente, como em JS. Existem variáveis ​​globais, mas eu não as usei, então não vou falar sobre elas.

As funções também possuem variáveis ​​locais, numeradas do zero, do tipo: int32 / int64 / float / double. As primeiras n variáveis ​​locais são os argumentos passados ​​para a função. Observe que, embora tudo aqui não seja totalmente de baixo nível em termos de fluxo de controle, mas números inteiros ainda não carregam o sinal / sinal não assinado: como o número se comportará depende do código de operação.

De um modo geral, o Binaryen fornece uma C-API simples : você cria um módulo, nele cria expressões - unárias, binárias, blocos de outras expressões, fluxo de controle etc. Então você cria uma função, cujo corpo você precisa especificar uma expressão. Se você, como eu, tiver um gráfico de transição de baixo nível, o componente relooper o ajudará. Pelo que entendi, é possível usar o controle de alto nível do fluxo de execução no bloco, desde que não ultrapasse os limites do bloco - ou seja, é possível criar uma ramificação de caminho rápido / caminho lento interno dentro do código de processamento de cache TLB interno, mas não há como interferir no fluxo de controle "externo" . Quando você libera o relooper, seus blocos são liberados, quando você libera um módulo, expressões, funções, etc., alocadas em sua arena desaparecem.

No entanto, se você deseja interpretar o código em movimento sem a criação e exclusão desnecessárias da instância do interpretador, pode fazer sentido transferir essa lógica para um arquivo C ++ e, a partir daí, controlar diretamente toda a biblioteca da API C ++, ignorando os wrappers finalizados.

Assim, para gerar o código, você precisa

 //    (  ) 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); 

… — , , — .

--, :

 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, // ... } ); //       instance! }, buf, sz); 

- QEMU JS , ( ), . , translation block, , struct TranslationBlock .

, ( ) Firefox. Chrome - , - WebAssembly, ...

. , , - . , . , WebAssembly , JS, , , .

: 32- , Binaryen, - - 2 32- . , Binaryen . ?

 // 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)); }