Era uma vez eu decidi por diversão provar a reversibilidade do processo e aprenda como gerar JavaScript (mais precisamente, Asm.js) a partir de código de máquina. O QEMU foi escolhido para o experimento e, algum tempo depois, um artigo foi escrito sobre Habr. Nos comentários fui aconselhado a refazer o projeto no WebAssembly, e até desistir sozinho quase terminado De alguma forma eu não queria o projeto... O trabalho estava acontecendo, mas muito devagar, e agora, recentemente apareceu aquele artigo sobre o tema “Então, como tudo acabou?” Em resposta à minha resposta detalhada, ouvi “Isso parece um artigo”. Bem, se você puder, haverá um artigo. Talvez alguém ache útil. Com ele, o leitor aprenderá alguns fatos sobre o design de back-ends de geração de código QEMU, bem como como escrever um compilador Just-in-Time para uma aplicação web.
Tarefas
Como já aprendi como “de alguma forma” portar QEMU para JavaScript, desta vez decidi fazê-lo com sabedoria e não repetir erros antigos.
Erro número um: ramificação da liberação pontual
Meu primeiro erro foi bifurcar minha versão da versão upstream 2.4.1. Então me pareceu uma boa ideia: se existe um lançamento pontual, então provavelmente é mais estável que o simples 2.4, e ainda mais o branch master. E como planejei adicionar uma boa quantidade de meus próprios bugs, não precisei dos de mais ninguém. Provavelmente foi assim que aconteceu. Mas o problema é o seguinte: o QEMU não fica parado e, em algum momento, eles até anunciaram a otimização do código gerado em 10%. “Sim, agora vou congelar”, pensei e desabei. Aqui precisamos fazer uma digressão: devido à natureza de thread único do QEMU.js e ao fato de que o QEMU original não implica a ausência de multi-threading (ou seja, a capacidade de operar simultaneamente vários caminhos de código não relacionados, e não apenas “usar todos os kernels”) é fundamental para isso, as principais funções dos threads eu tive que “desativar” para poder chamar de fora. Isso criou alguns problemas naturais durante a fusão. No entanto, o facto de algumas das alterações do ramo master, com os quais tentei mesclar meu código, também foram escolhidos a dedo no lançamento pontual (e, portanto, em meu branch) e provavelmente não teriam adicionado conveniência.
No geral, decidi que ainda faz sentido jogar fora o protótipo, desmontá-lo em peças e construir uma nova versão do zero baseada em algo mais novo e agora de master.
Erro número dois: metodologia TLP
Em essência, isso não é um erro, em geral, é apenas uma característica de criar um projeto em condições de total incompreensão tanto de “para onde e como nos mover?”, quanto em geral “chegaremos lá?” Nessas condições programação desajeitada era uma opção justificada, mas, naturalmente, não quis repeti-la desnecessariamente. Desta vez eu queria fazer isso com sabedoria: commits atômicos, mudanças conscientes de código (e não “encadear caracteres aleatórios até compilar (com avisos)”, como Linus Torvalds disse uma vez sobre alguém, de acordo com o Wikiquote), etc.
Erro número três: entrar na água sem conhecer o vau
Ainda não me livrei completamente disso, mas agora decidi não seguir o caminho de menor resistência, e fazê-lo “como um adulto”, ou seja, escrever meu backend TCG do zero, para não ter que dizer mais tarde: “Sim, é claro, lentamente, mas não posso controlar tudo - é assim que o TCI está escrito...” Além disso, esta inicialmente parecia uma solução óbvia, uma vez que Eu gero código binário. Como se costuma dizer: “Ghent reuniuу, mas não aquele”: o código é, obviamente, binário, mas o controle não pode ser simplesmente transferido para ele - ele deve ser explicitamente inserido no navegador para compilação, resultando em um determinado objeto do mundo JS, que ainda precisa ser ser salvo em algum lugar. No entanto, em arquiteturas RISC normais, pelo que entendi, uma situação típica é a necessidade de redefinir explicitamente o cache de instruções para o código regenerado - se não for isso que precisamos, então, em qualquer caso, 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 tradução, então não precisamos realmente de bytecode interpretado a partir de qualquer deslocamento, e podemos simplesmente gerá-lo a partir da função em TB .
Eles vieram e chutaram
Embora eu tenha começado a reescrever o código em julho, um golpe mágico passou despercebido: geralmente cartas do GitHub chegam como notificações sobre respostas a problemas e solicitações pull, mas aqui, de repente mencionar no tópico no contexto, “Ele fez algo assim, talvez ele diga alguma coisa”. Estávamos conversando sobre o uso da biblioteca relacionada do Emscripten para criar WASM JIT. Bem, eu disse que você tem uma licença Apache 2.0 lá, e o QEMU como um todo é distribuído sob GPLv2, e eles não são muito compatíveis. De repente, descobriu-se que uma licença pode ser consertar isso de alguma forma (Não sei: talvez mudar, talvez licenciamento duplo, talvez outra coisa...). Isso, claro, me deixou feliz, porque naquela época eu já havia olhado atentamente WebAssembly, e fiquei de alguma forma triste e incompreensível. Havia também uma biblioteca que devoraria os blocos básicos com o grafo de transição, produziria o bytecode e até rodaria no próprio interpretador, se necessário.
Então houve mais na lista de discussão do QEMU, mas isso é mais sobre a questão: “Quem precisa disso, afinal?” E isso é de repente, descobriu-se que era necessário. No mínimo, você pode reunir as seguintes possibilidades de uso, se funcionar mais ou menos rapidamente:
- lançando algo educacional sem qualquer instalação
- virtualização no iOS, onde, segundo rumores, o único aplicativo que tem direito à geração de código em tempo real é um motor JS (isso é verdade?)
- demonstração de mini-OS - disquete único, integrado, todos os tipos de firmware, etc...
Recursos de tempo de execução do navegador
Como já disse, o QEMU está vinculado ao multithreading, mas o navegador não possui. Bem, isto é, não... No começo não existia, depois apareceram os WebWorkers - pelo que entendi, isso é multithreading baseado na passagem de mensagens sem variáveis compartilhadas. Naturalmente, isso cria problemas significativos ao portar código existente com base no modelo de memória compartilhada. Depois, sob pressão pública, também foi implementado sob o nome SharedArrayBuffers. Foi introduzido gradativamente, comemoraram seu lançamento em diferentes navegadores, depois comemoraram o Ano Novo e depois Meltdown... Depois disso, chegaram à conclusão de que a medição do tempo é grosseira ou grosseira, mas com a ajuda da memória compartilhada e de um thread incrementando o contador, é tudo a mesma coisa . Portanto, desabilitamos o multithreading com memória compartilhada. Parece que mais tarde eles o ligaram novamente, mas, como ficou claro desde o primeiro experimento, há vida sem ele e, nesse caso, tentaremos fazê-lo sem depender de multithreading.
A segunda característica é a impossibilidade de manipulações de baixo nível com a pilha: você não pode simplesmente pegar, salvar o contexto atual e mudar para um novo com uma nova pilha. A pilha de chamadas é gerenciada pela máquina virtual JS. Ao que parece, qual é o problema, já que ainda decidimos gerenciar os fluxos anteriores de forma totalmente manual? O fato é que a E/S de bloco no QEMU é implementada por meio de corrotinas, e é aqui que as manipulações de pilha de baixo nível seriam úteis. Felizmente, o Emscipten já contém um mecanismo para operações assíncronas, até dois: и . O primeiro funciona com um inchaço significativo no código JavaScript gerado e não é mais compatível. A segunda é a "forma correta" atual e funciona através da geração de bytecode para o interpretador nativo. Funciona, é claro, lentamente, mas não sobrecarrega o código. É verdade que o suporte a corrotinas para esse mecanismo teve que ser contribuído de forma independente (já existiam corrotinas escritas para Asyncify e havia uma implementação aproximadamente da mesma API para Emterpreter, bastava conectá-las).
No momento ainda não consegui dividir o código em um compilado em WASM e interpretado usando Emterpreter, então dispositivos de bloco ainda não funcionam (veja na próxima série, como dizem...). Ou seja, no final você deve obter algo parecido com esta coisa engraçada em camadas:
- E/S de bloco interpretado. Bem, você realmente esperava NVMe emulado com desempenho nativo? 🙂
- Código QEMU principal compilado estaticamente (tradutor, outros dispositivos emulados, etc.)
- código convidado compilado dinamicamente no WASM
Recursos das fontes QEMU
Como você provavelmente já adivinhou, o código para emular arquiteturas convidadas e o código para gerar instruções da máquina host são separados no QEMU. Na verdade, é ainda um pouco mais complicado:
- existem arquiteturas convidadas
- tem aceleradores, ou seja, KVM para virtualização de hardware em Linux (para sistemas convidados e host compatíveis entre si), 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 ()
- se o TCG for usado e não a virtualização de hardware, ele terá suporte de geração de código separado para cada arquitetura de host, bem como para o interpretador universal
- ... e em torno de tudo isso - periféricos emulados, interface de usuário, migração, reprodução de gravação, 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 binária. Talvez alguém queira portar este modo de operação do QEMU para JS? 😉
Como a maioria dos softwares livres de longa data, o QEMU é construído através da chamada configure и make. Digamos que você decida adicionar algo: um backend TCG, implementação de thread, algo mais. Não se apresse em ficar feliz/horrorizado (sublinhe conforme apropriado) com a perspectiva de se comunicar com o Autoconf - na verdade, configure O QEMU é aparentemente auto-escrito e não é gerado a partir de nada.
Webassembly.
Então, o que é essa coisa chamada WebAssembly (também conhecida como WASM)? Este é um substituto para o Asm.js, não fingindo mais ser um código JavaScript válido. Pelo contrário, é puramente binário e otimizado, e mesmo simplesmente escrever um número inteiro nele não é muito simples: para maior compactação, ele é armazenado no formato .
Você deve ter ouvido falar sobre o algoritmo de relooping para Asm.js - esta é a restauração de instruções de controle de fluxo de “alto nível” (ou seja, if-then-else, loops, etc.), para as quais os mecanismos JS são projetados, de o LLVM IR de baixo nível, mais próximo do código de máquina executado pelo processador. Naturalmente, a representação intermédia do QEMU está mais próxima da segunda. Parece que aqui está, bytecode, o fim do tormento... E depois há blocos, if-then-else e loops!..
E esta é outra razão pela qual o Binaryen é útil: ele pode aceitar naturalmente blocos de alto nível próximos ao que seria armazenado no WASM. Mas também pode produzir código a partir de um gráfico de blocos básicos e transições entre eles. Bem, eu já disse que ele esconde o formato de armazenamento WebAssembly atrás da conveniente API C/C++.
TCG (gerador de código minúsculo)
TCG back-end para o compilador C. Então, aparentemente, ele não aguentou a concorrência com o GCC, mas no final encontrou seu lugar no QEMU como mecanismo de geração de código para a plataforma host. Há também um backend TCG que gera algum bytecode abstrato, que é imediatamente executado pelo intérprete, mas decidi evitar usá-lo desta vez. Contudo, o facto de no QEMU já ser possível viabilizar a transição para o TB gerado através da função tcg_qemu_tb_exec, acabou sendo muito útil para mim.
Para adicionar um novo backend TCG ao QEMU, você precisa criar um subdiretório tcg/<имя архитектуры> (nesse caso, tcg/binaryen) e contém dois arquivos: tcg-target.h и tcg-target.inc.c и é tudo sobre configure. Você pode colocar outros arquivos lá, mas, como você pode imaginar pelos nomes desses dois, ambos serão incluídos em algum lugar: um como um arquivo de cabeçalho normal (está incluído no tcg/tcg.h, e esse já está em outros arquivos nos diretórios tcg, accel e não só), o outro - apenas como um trecho de código em tcg/tcg.c, mas tem acesso às suas funções estáticas.
Decidindo que gastaria muito tempo em investigações detalhadas de como funciona, simplesmente copiei os “esqueletos” desses dois arquivos de outra implementação de back-end, indicando isso honestamente no cabeçalho da licença.
arquivo tcg-target.h contém principalmente configurações no formato #define-s:
- quantos registros e qual largura existem na arquitetura alvo (temos quantos quisermos, quantos quisermos - a questão é mais sobre o que será gerado em código mais eficiente pelo navegador na arquitetura “completamente alvo” ...)
- alinhamento das instruções do host: no x86, e mesmo no TCI, as instruções não estão alinhadas, mas vou 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 - incluímos tudo o que encontramos no Binaryen, deixamos o acelerador dividir o resto em instruções mais simples
- Qual é o tamanho aproximado do cache TLB solicitado pelo backend. O fato é que no QEMU tudo é sério: embora existam funções auxiliares que realizam load/store levando em consideração o MMU convidado (onde estaríamos sem ele agora?), elas salvam seu cache de tradução na forma de uma estrutura, o cujo processamento é conveniente para incorporar diretamente em blocos de transmissão. A questão é: qual deslocamento nesta estrutura é processado de forma mais eficiente por uma sequência pequena e rápida de comandos?
- aqui você pode ajustar a finalidade de um ou dois registros reservados, ativar a chamada de TB por meio de uma função e, opcionalmente, descrever alguns pequenos
inline-funções comoflush_icache_range(mas este não é o nosso caso)
arquivo tcg-target.inc.c, é claro, geralmente tem um tamanho muito maior e contém várias funções obrigatórias:
- inicialização, incluindo restrições sobre quais instruções podem operar em quais operandos. Copiado descaradamente por mim de outro backend
- função que recebe uma instrução de bytecode interno
- Você também pode colocar funções auxiliares aqui e também usar funções estáticas de
tcg/tcg.c
Para mim, escolhi a seguinte estratégia: nas primeiras palavras do próximo bloco de tradução, escrevi quatro dicas: uma marca inicial (um certo valor próximo 0xFFFFFFFF, que determinou o estado atual do TB), contexto, módulo gerado e número mágico para depuração. A princípio a marca foi colocada em 0xFFFFFFFF - nOnde n - um pequeno número positivo, e cada vez que era executado pelo intérprete aumentava em 1. Quando chegava 0xFFFFFFFE, ocorreu a compilação, o módulo foi salvo na tabela de funções, importado para um pequeno “lançador”, de onde passou a execução tcg_qemu_tb_exec, e o módulo foi removido da memória QEMU.
Parafraseando os clássicos, “Crutch, quanto está entrelaçado nesse som para o coração do proger...”. No entanto, a memória estava vazando em algum lugar. Além disso, era uma memória gerenciada pelo QEMU! Eu tinha um código que, ao escrever a próxima instrução (bem, isto é, um ponteiro), excluiu aquela cujo link estava neste local anteriormente, mas isso 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 acaba, o código é descartado e o próximo começa a ser escrito em seu lugar.
Depois de estudar o código, percebi que o truque com o número mágico me permitiu não falhar na destruição do heap, liberando algo errado em um buffer não inicializado na primeira passagem. Mas quem reescreve o buffer para ignorar minha função mais tarde? Como aconselham os desenvolvedores do Emscripten, quando me deparei com um problema, portei o código resultante de volta para o aplicativo nativo, configurei Mozilla Record-Replay nele... Em geral, no final percebi uma coisa simples: para cada bloco, a struct TranslationBlock com sua descrição. Adivinhe onde... Isso mesmo, logo antes do bloco no buffer. Percebendo isso, decidi parar de usar muletas (pelo menos algumas), e simplesmente joguei fora o número mágico e transferi as palavras restantes para struct TranslationBlock, criando uma lista vinculada individualmente que pode ser percorrida rapidamente quando o cache de tradução é redefinido e libera memória.
Algumas muletas permanecem: por exemplo, ponteiros marcados no buffer de código - alguns deles são simplesmente BinaryenExpressionRef, ou seja, olham para as expressões que precisam ser colocadas linearmente no bloco básico gerado, parte é a condição para transição entre BBs, parte é para onde ir. Pois bem, já existem blocos preparados para Relooper que precisam ser conectados de acordo com as condições. Para distingui-los, presume-se que todos estejam alinhados em pelo menos quatro bytes, portanto, você pode usar com segurança os dois bits menos significativos para o rótulo, bastando lembrar de removê-los se necessário. A propósito, tais rótulos já são usados no QEMU para indicar o motivo da saída do loop TCG.
Usando binário
Os módulos no WebAssembly contêm funções, cada uma contendo um corpo, que é 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. Os argumentos para funções não são passados na pilha, mas explicitamente, assim como em JS. Existem também variáveis globais, mas não as usei, então não vou falar sobre elas.
As funções também possuem variáveis locais, numeradas a partir de zero, do tipo: int32/int64/float/double. Neste caso, 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, os números inteiros ainda não carregam o atributo “assinado/não assinado”: o modo como o número se comporta depende do código da operação.
De modo geral, Binaryen fornece : você cria um módulo, nele criar expressões - unárias, binárias, blocos de outras expressões, fluxo de controle, etc. Então você cria uma função com uma expressão como corpo. Se você, como eu, tem um gráfico de transição de baixo nível, o componente relooper irá ajudá-lo. Pelo que entendi, é possível usar o controle de alto nível do fluxo de execução em um bloco, desde que não ultrapasse os limites do bloco - ou seja, é possível fazer caminho rápido/lento interno ramificação de caminho dentro do código de processamento de cache TLB integrado, mas não para interferir no fluxo de controle “externo”. Quando você libera um relooper, seus blocos são liberados; quando você libera um módulo, as expressões, funções, etc. alocadas a ele desaparecem arena.
No entanto, se você deseja interpretar o código dinamicamente sem criação e exclusão desnecessária de uma instância do interpretador, pode fazer sentido colocar essa lógica em um arquivo C++ e, a partir daí, gerenciar diretamente toda a API C++ da biblioteca, ignorando o ready- fez invólucros.
Então, para gerar o código que 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);... se esqueci de alguma coisa, desculpe, isso é só para representar a escala, e os detalhes estão na documentação.
E agora começa o crack-fex-pex, 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,
// ...
}
);
// и вот уже у вас есть instance!
}, buf, sz);Para conectar de alguma forma os mundos do QEMU e JS e ao mesmo tempo acessar rapidamente as funções compiladas, foi criado um array (uma tabela de funções para importação para o launcher), e as funções geradas foram colocadas lá. Para calcular rapidamente o índice, o índice do bloco de tradução de palavra zero foi inicialmente usado como tal, mas depois o índice calculado usando esta fórmula começou a simplesmente caber no campo em struct TranslationBlock.
By the way, (atualmente com uma licença obscura) só funciona bem no Firefox. Os desenvolvedores do Chrome foram de alguma forma não está pronto ao fato de que alguém iria querer criar mais de mil instâncias de módulos WebAssembly, então eles simplesmente alocaram um gigabyte de espaço de endereço virtual para cada um...
É tudo por agora. Talvez haja outro artigo se alguém estiver interessado. Ou seja, resta pelo menos apenas fazer dispositivos de bloco funcionarem. Também pode fazer sentido tornar a compilação dos módulos WebAssembly assíncrona, como é habitual no mundo JS, já que ainda existe um interpretador que pode fazer tudo isso até que o módulo nativo esteja pronto.
Finalmente um enigma: você compilou um binário em uma arquitetura de 32 bits, mas o código, por meio de operações de memória, sobe do binário, em algum lugar da pilha ou em algum outro lugar nos 2 GB superiores do espaço de endereço de 32 bits. O problema é que, do ponto de vista de Binaryen, isso significa acessar um endereço resultante muito grande. Como contornar isso?
No caminho do administrador
Acabei não testando isso, mas meu primeiro pensamento foi “E se eu instalasse o Linux de 32 bits?” Então a parte superior do espaço de endereço será ocupada pelo kernel. A única dúvida é quanto será ocupado: 1 ou 2 Gb.
À maneira de um programador (opção para profissionais)
Vamos explodir uma bolha no topo do espaço de endereço. Eu mesmo não entendo por que funciona - aí já deve haver uma pilha. Mas “somos praticantes: tudo funciona para nós, mas ninguém sabe porquê...”
// 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));
}... é verdade que não é compatível com Valgrind, mas, felizmente, o próprio Valgrind empurra todos de lá de forma muito eficaz :)
Talvez alguém dê uma explicação melhor de como funciona esse meu código...
Fonte: habr.com