A long time ago, I decided for fun to prove the reversibility of the process and learn to generate JavaScript (more specifically, Asm.js) from machine code. For the experiment, QEMU was chosen, and some time later, an article was written on Habr. In the comments, I was advised to redo the project in WebAssembly, and I really didn’t want to abandon my almost completed project... Work was progressing, but very slowly, and recently a comment appeared on that article Tasks
Since I have already learned to "somewhat" port QEMU to JavaScript, this time it was decided to do it wisely and not repeat past mistakes.
Mistake number one: diverging from the point release
My first mistake was to branch my version from the upstream version 2.4.1. At that time, it seemed like a good idea: if a point release exists, it is probably more stable than the plain 2.4, and even more so than the branch
. And since I planned to add a considerable amount of my bugs, I really didn't need someone else's. That’s how it probably turned out. But here’s the problem: QEMU doesn't stand still, and at some point, they even announced an optimization of the generated code by about 10%. "Aha, I'll just merge it now," I thought and hit a wall. Here, a side note is needed: due to the single-threaded nature of QEMU.js and the fact that the original QEMU does not assume a lack of multithreading (i.e., it is critical for it to allow simultaneous operation of several unrelated code paths, not just to "use all cores"), the main functions of threads had to be "twisted" to allow calls from outside. This created some natural problems during merging. However, the fact that some changes from the branch master, from which I was trying to merge my code, were also cherry-picked into the point release (and thus into my branch too) probably didn't make things any easier. masterIn general, I decided that it still makes sense to throw out the prototype, break it down into parts and build a new version from scratch based on something fresher and now already from
Mistake number two: TLP methodology master.
Mistake number two: TLP methodology
In essence, this isn’t really a mistake; it's just a feature of project development under conditions of complete uncertainty about "where and how to move?" and whether "we'll make it at all?" In these conditions sloppy programming was a justified option, but, of course, I really didn’t want to repeat that unnecessarily. This time, I wanted to do it right: atomic commits, deliberate code changes (rather than "stringing random characters together until it compiles (with warnings)," as Linus Torvalds once said about someone, if we believe Wikiquote), etc.
Mistake number three: diving in without knowing the water
I haven’t completely overcome this even now, but I’ve decided to avoid the path of least resistance, to do it "grown-up style," specifically, to write my own TCG backend from scratch, so later I won’t say, "Yes, it’s slow, but I can’t control everything — TCI is written that way…" Besides, it initially seemed like an obvious solution because I'm generating binary code. As they say, "I assembled Gent,at, but not that one": the code is indeed binary, but it can't just be handed over for control — it has to be explicitly shoved into the browser for compilation, resulting in some object from the JS world that still needs to be saved somewhere. However, on normal RISC architectures, as I understand it, it’s typical to have to explicitly flush the instruction cache for regenerated code — if this isn’t exactly what we need, it’s at least close. Additionally, from my previous attempt, I learned that control doesn’t seemingly transfer to the middle of the translation block, so bytecode interpreted from any offset isn’t particularly needed, and we can just generate per function on TB.
They came and kicked
Although I started rewriting the code back in July, a magical push came unexpectedly: usually, emails from GitHub come as notifications about responses to Issues and Pull requests, but this time, suddenly a mention in the thread in the context of, "He did something similar; maybe he'll say something." The discussion was about using a library related to Emscripten, to create WASM JIT. So I pointed out that your license is Apache 2.0, while QEMU as a whole is distributed under GPLv2, and they aren’t very compatible. Suddenly, it turned out that the license could be somehow adjusted (I don't know: maybe change it, maybe double licensing, maybe something else…). This, of course, pleased me because I had already been looking into WebAssembly, and I found it somewhat sad and incomprehensible. Here was a library that would consume both the basic blocks with the transition graph and output bytecode, and even launch it in the interpreter if needed.
Then there was on the QEMU mailing list, but that rather leads to the question, 'Who even needs it?'. But it turned out suddenly, it actually was needed. At the very least, one could scrape up the potential uses if it could work reasonably fast:
- running something educational without any installation
- virtualization on iOS, where, according to rumors, the only application allowed to generate code on-the-fly is the JS engine (is this true?)
- demonstrating a mini-OS — single-disk, embedded, various firmware, etc…
Features of the browser execution environment
As I mentioned, QEMU is tied to multithreading, but there isn’t any in the browser. Well, not exactly… At first, there was none, then WebWorkers appeared — as far as I understand, this is multithreading based on message passing without shared mutable variables. Naturally, this creates significant problems when porting existing code based on the shared memory model. Later, under public pressure, it was implemented under the name SharedArrayBuffers. It was gradually introduced, celebrated for its launch in various browsers, then celebrated the New Year, and then came Meltdown… After which it was concluded that regardless of how you measure time, through shared memory and a thread incrementing a counter, it will still . So they disabled multithreading with shared memory. It seems they turned it back on later, but, as became clear from the first experiment, life exists even without it, so let's try to proceed without relying on multithreading.
The second feature is the inability to perform low-level manipulations with the stack: you can't just take the current context, save it, and switch to a new one with a new stack. The call stack is managed by the JS virtual machine. One might wonder what the problem is since we've decided to manage former threads completely manually anyway? The issue is that block input/output in QEMU is implemented through coroutines, and that's where we would need low-level stack manipulations. Fortunately, Emscripten already has a mechanism for asynchronous operations, even two: and . The first one works by significantly bloating the generated JavaScript code and is no longer supported. The second one is the current "correct way" and operates by generating bytecode for its own interpreter. It runs slowly, of course, but does not bloat the code. However, support for coroutines in this mechanism had to be contributed manually (there were already coroutines written for Asyncify and there was an implementation of approximately the same API for Emterpreter, it just needed to be connected).
Currently, I haven’t managed to separate the code into that which compiles to WASM and that which is interpreted using Emterpreter, so block devices are not yet working (stay tuned for the next episodes, as they say…). So, in the end, it should turn out to be something amusingly layered like this:
- interpreted block input/output. Well, what did you really expect, an emulated NVMe with native performance? 🙂
- statically compiled main QEMU code (translator, other emulated devices, etc.)
- dynamically compiled WASM guest code
Features of the QEMU sources
As you might have guessed, the code for emulating guest architectures and the code for generating host machine instructions in QEMU are separated. In fact, it’s even more clever than that:
- there are guest architectures
- there are accelerators, namely, KVM for hardware virtualization on Linux (for compatible guest and host systems), TCG for JIT code generation anywhere. Starting from QEMU 2.9, support for the hardware virtualization standard HAXM on Windows has appeared ()
- if TCG is used instead of hardware virtualization, it has separate support for code generation for each host architecture, as well as for a universal interpreter
- ... and around all this — emulated peripherals, user interface, migration, record-replay, etc.
By the way, did you know: QEMU can emulate not only an entire computer but also a processor for a separate user process in the host kernel, which is used by, for example, AFL fuzzer for binary instrumentation. Perhaps someone would like to port this mode of QEMU to JS? 😉
Like most long-established free programs, QEMU is built using the call configure and make. Suppose you decided to add something: a TCG backend, thread implementation, or something else. Don't rush to celebrate or be horrified about the prospect of dealing with Autoconf — in fact, configure QEMU, it seems, has its own custom mechanism that is not generated from anything.
WebAssembly
So what is this thing — WebAssembly (also known as WASM)? It is a replacement for Asm.js, no longer pretending to be valid JavaScript code. On the contrary, it is purely binary and optimized, and even simply writing an integer into it isn't all that straightforward: it is stored compactly in the .
You may have heard about the relooping algorithm for Asm.js — it's the restoration of 'high-level' control flow instructions (i.e., if-then-else, loops, etc.) that JS engines are tailored to, from low-level LLVM IR, which is closer to the machine code executed by the processor. Naturally, QEMU's intermediate representation is closer to the latter. It seems like there's the bytecode, the end of the torment... and then there are blocks, if-then-else, and loops!
And this is yet another reason why Binaryen is useful: it can naturally take high-level blocks, close to what will be stored in WASM. But it can also produce code from the graph of basic blocks and transitions between them. As for what it hides behind a convenient C/C++ API for the storage format of WebAssembly, I have already mentioned.
TCG (Tiny Code Generator)
TCG the backend for the C compiler. Then it apparently could not compete with GCC, but ultimately found its place within QEMU as a code generation mechanism for the host platform. There is also a TCG backend that generates an abstract bytecode which the interpreter executes immediately, but I decided to move away from using it this time. However, the fact that QEMU already has the ability to switch to the generated TB through the function tcg_qemu_tb_exec, was very convenient for me.
To add a new TCG backend to QEMU, you need to create a subdirectory tcg/ (in this case, tcg/binaryen), and in it, two files: tcg-target.h and tcg-target.inc.c and all of this in configure. You can also place other files there, but as can be guessed from the names of these two, both will be included somewhere: one as a regular header file (it is included in tcg/tcg.h, and the other already into other files in the directories tcg, accel and not only), the other — only as a code snippet in tcg/tcg.c, yet it has access to its static functions.
Deciding that I would spend too much time on detailed investigations of how it works, I simply copied the "skeletons" of these two files from another backend implementation, honestly stating this in the license header.
File tcg-target.h primarily contains settings in the form of #define-s:
- how many registers and what width they are on the target architecture (we have as many as we want — the question is more about what will be generated into more efficient code by the browser on a 'truly target' architecture...)
- the alignment of host instructions: on x86, and in TCI, instructions are not aligned at all, I am going to place not instructions in the code buffer, but pointers to structures from the Binaryen library, so I will say: 4 bytes
- what optional instructions the backend can generate — we include everything we find in Binaryen, let the accelerator break the rest down into simpler ones.
- What is the approximate size of the TLB cache requested by the backend? The thing is, in QEMU, everything is serious: although there are helper functions that perform load/store considering the guest MMU (where would we be without it?), their translation cache is stored as a structure, which is convenient to embed directly into the translation blocks. The question is, which offset in this structure is most efficiently handled by a small and fast sequence of commands?
- Here, you can also tweak the assignment of one or two reserved registers, enable the TB call through a function, and optionally describe a couple of minor details.
inline-functions likeflush_icache_range(but this is not our case)
File tcg-target.inc.c, naturally, is usually much larger in size and contains several mandatory functions:
- initialization, which also indicates the limitations on which instruction can work with which operands. This has been shamelessly copied from another backend.
- a function that takes one internal bytecode instruction
- Auxiliary functions can also be placed here, and static functions from
tcg/tcg.c
For myself, I chose the following strategy: in the first words of the next translation block, I recorded four pointers: the start label (some value around 0xFFFFFFFF, which determined the current state of the TB), the context, the generated module, and a magic number for debugging. Initially, the label was set to 0xFFFFFFFF - n, where n — a small positive number, and with each execution through the interpreter, it increased by 1. When it reached 0xFFFFFFFE, compilation happened, the module was saved in the function table, imported into a small 'launcher', where execution transferred from tcg_qemu_tb_exec, and the module was removed from QEMU memory.
Paraphrasing the classics, "A crutch, how much in this sound has intertwined for the heart of a programmer...". Nevertheless, memory was leaking somewhere. Moreover, it was memory managed by QEMU! I had code that, upon writing the next instruction (that is, the pointer), deleted the one that was previously referenced at that location, but it didn’t help. In fact, in the simplest case, QEMU allocates memory at startup and writes the generated code there. When the buffer runs out, the code is discarded, and the next one starts to be written in its place.
After studying the code, I realized that the workaround with the magic number allowed it to avoid crashing on heap destruction by freeing something unintended on an uninitialized buffer during the first pass. But who rewrites the buffer bypassing my function afterwards? As the Emscripten developers advise, when faced with a problem, I ported the resulting code back into a native application and tested it with Mozilla Record-Replay... In the end, I understood a simple thing: for each block, memory is allocated struct TranslationBlock with its description. Guess where... Right, directly before the block in the buffer. Realizing this, I decided to stop using workarounds (at least some of them), and simply discarded the magic number, moving the remaining words into struct TranslationBlock, creating a linked list that can be quickly traversed when resetting the translation cache to free up memory.
Some workarounds remain: for instance, marked pointers in the code buffer—some of them are simply BinaryenExpressionRef, meaning they point to expressions that need to be laid out linearly in the generated basic block, some are conditions for transitions between BBs, and some specify where to transition. There are also already prepared blocks for Relooper that need to be connected based on conditions. To distinguish them, we use the assumption that all are aligned at least to four bytes, so we can safely use the lower two bits for a label, just remember to remove it when necessary. By the way, such labels are already used in QEMU to indicate the reason for exiting the TCG loop.
Using Binaryen
Modules in WebAssembly contain functions, each of which has a body that consists of expressions. Expressions include unary and binary operations, blocks composed of lists of other expressions, control flow, etc. As I mentioned earlier, control flow here is organized precisely as high-level branching, loops, function calls, etc. Arguments are passed to functions not on the stack but explicitly, just like in JS. There are global variables, but I didn't use them, so I won't discuss them.
Functions also have numbered local variables starting from zero, which can be of type: int32 / int64 / float / double. The first n local variables are the arguments passed to the function. Note that while everything here might not be very low-level in terms of control flow, integers still don’t carry the ‘signed/unsigned’ characteristic: how a number behaves depends on the operation code.
In general, Binaryen provides : you create a module, in it you create expressions—unary, binary, blocks of other expressions, control flow, etc. Then you create a function, specifying an expression as its body. If you have a low-level transition graph, as I do, the relooper component will help you. As far as I understand, high-level control flow can be used inside a block as long as it doesn’t extend beyond the block—that is, making internal branching fast path / slow path within the embedded TLB cache handler code is possible, but interfering with the ‘outer’ control flow is not. When you free the relooper, its blocks are released; when you free the module, the expressions, functions, etc., allocated in its arena.
However, if you want to interpret code on the fly without unnecessarily creating and deleting instances of the interpreter, it might make sense to move this logic into a C++ file and directly manage the entire C++ API of the library without the ready-made wrappers.
Thus, to generate code, you need to
// настроить глобальные параметры (можно поменять потом)
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);… if I forgot something—sorry, this is just to represent the scale, and the details are in the documentation.
And now the crex-fex-pex begins, something like this:
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,
// ...
}
);
// and now you have an instance!
}, buf, sz);To somehow bridge the world of QEMU and JS while quickly accessing compiled functions, an array (a table of functions for importing into the launcher) was created, where generated functions were placed. To quickly compute the index, the index of the zero word of the translation block was initially used, but later the index calculated by this formula simply started to fit into the field. struct TranslationBlock.
By the way, (currently under an unclear license) it only works well in Firefox. Chrome developers were somehow unprepared for the idea that someone would want to create over a thousand instances of WebAssembly modules, so they allocated one gigabyte of virtual address space for each...
That's all for now. There might be another article if anyone is interested. Specifically, it remains to merely get block devices to work. It might also make sense to make the compilation of WebAssembly modules asynchronous, as is customary in the world of JS, especially since there is already an interpreter that can execute everything while the native module is being prepared.
Lastly, a riddle: you compiled a binary on a 32-bit architecture, but the code through memory operations is accessing Binaryen, somewhere in the stack or elsewhere in the upper 2 GB of the 32-bit address space. The problem is that from Binaryen's perspective, this access is to a resulting address that is too large. How can this be bypassed?
In admin terms
I ultimately didn't test this, but my first thought was, "What if I set up a 32-bit Linux?" Then the upper part of the address space would be taken by the kernel. The only question is how much will be occupied: 1 or 2 GB.
In programmer terms (a practical option)
We inflate a bubble in the upper part of the address space. I myself don't understand why it works — there should be a stack there. But "we are practitioners: everything works for us, but no one knows why…". already … with Valgrind, though, it is not compatible, but fortunately Valgrind itself very effectively pushes everyone out from there 🙂
// 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));
}Perhaps someone will provide a better explanation of how my code works…
Qemu.js with JIT support: the sausage can indeed be turned back
Source: habr.com
