Qemuonarm

[ldesnogu]

I decided that instead of talking of running QEMU on ARM, I would try it

I entered the project in the Beagleboard contest. Here is the summary I just
sent to the BB mailing-list.

The user mode QEMU i386 on ARM (that is a program able to run a Linux i386
program on an ARM target) has been brought back to life. A few improvements
have been done to ARM code generation.

The program has been tested both on real hardware and with QEMU ARM on
x86_64, by running nbench. On the hardware platform (140 MHz) the results
give a speed roughly similar to a 486DX@16MHz. If scaling was perfect (and
it won't), that'd mean a 486DX@60MHz on an OMAP3.

Obviously the next step is to improve speed, but given the way QEMU works
no huge speedup will be possible without heavy modifications to the dispatch
loop (about 60% of the time is spent in that loop, and only 23% in the
generated code).

Then I will turn to system mode simulation (this is the variant of QEMU that can
boot an OS), but given the current speed no miracle is to be expected.

An alternative, though probably a difficult one, would be to couple user mode
QEMU with wine. Again the speed will be an obstacle (no, WoW won't run
on this...).

Another direction could be DOS simulation to run some oldies.

To sum up: it works, but too slowly; it's optimization time

Comments and questions welcome.

 

[Exophase]

Why is a user mode emulator spending most of its time in a dispatch loop? Can you please explain the basic work flow here?

How hard do you think it will be for Wine to "just run"? It's supposed to run fully in usermode, so if it doesn't work out of the box then that'd mean there's something unsupported in qemu that it needs. Or I could be wrong, please tell me if I am. I want to know just what is necessary for a user mode emulator to run Wine.

Actually I'm curious as to what the main challenges are with a user mode only Linux to Linux only emulator that only performs x86 to ARM translation. Not to bring forth upon me seas of criticism for any hints of reinventing the wheel, but this seems like a tiny subset of what qemu intends to do and possibly not the most engaging thing in the world (IMO, much less work than writing many a console emulator that needs a recompiler, but I could be mistaken)

 

[greendots]

Great Laurent! Is it possible to benchmark qemu in Dosbox cycles?

 

[ldesnogu]

Why is a user mode emulator spending most of its time in a dispatch loop? Can you please explain the basic work flow here?

Basically the dispatch loop (I probably wrongly named it) does the following:

while (1)
   // come here through longjmp (signal handling)
   if (exception)
      do_it
   while (1)
      if (interrupt)
         do_it
      locate_next_code_to_execute (potentially flushing and generating)
      link_blocks
      execute

The problem is that basic blocks tend to be small, at least in nbench.
There probably is some work to do to expand them, but that's not trivial.
The locate_next_code_to_execute is finding the next block to execute
(ensuring CPU state hasn't changed) and if it's not found (or if state
has changed) generate code. Code generation itself takes a few percent
(which is to be expected on a benchmark).

How hard do you think it will be for Wine to "just run"? It's supposed to run fully in usermode, so if it doesn't work out of the box then that'd mean there's something unsupported in qemu that it needs. Or I could be wrong, please tell me if I am. I want to know just what is necessary for a user mode emulator to run Wine.

I don't know the inner working of Wine very well. The first difficult
point that comes to my mind is ABI handling.

Actually I'm curious as to what the main challenges are with a user mode only Linux to Linux only emulator that only performs x86 to ARM translation. Not to bring forth upon me seas of criticism for any hints of reinventing the wheel, but this seems like a tiny subset of what qemu intends to do and possibly not the most engaging thing in the world (IMO, much less work than writing many a console emulator that needs a recompiler, but I could be mistaken)

User mode is not that trivial: you have to handle memory mapping,
dispatching signals, translate syscalls (if you think all syscalls
are identical accross kernels and architectures, you're wrong) and
so on. Nothing rocket science, but even writing a console emulator
isn't rocket science. Making it efficient *is* difficult

Oh and I'm not reinventing the wheel at all here. I'm just trying
to improve something that once worked in QEMU for the fun of it.

@greendots: I can't compare QEMU to DOSBox cycles, I know
nothing about it. Perhaps compiling nbench for DOS is possible?
Anyway don't forget DOSBox contains some HW emulation that the
QEMU I used to test speed doesn't.

 

[Exophase]

while (1)
// come here through longjmp (signal handling)
if (exception)
do_it
while (1)
if (interrupt)
do_it
locate_next_code_to_execute (potentially flushing and generating)
link_blocks
execute

So the problem is that it's requiring that interrupts/exceptions occur inbetween blocks. I assume that the emulated register state is also flushed here. I don't see why interrupts can't occur natively. Yes, they might happen inbetween the state of a native instruction, but we're talking about user mode code that will virtually always be well behaved. I don't know what's even available as interrupts or exceptions to the user and not the OS - a thread that's blocking for an event to occur from a device will be wait queued until this point and the wakeup process will be transparent to the user mode process. Asynchronous events are handled through signals which shouldn't convey any low level details of the current thread's execution state. In other words, there's no real reason why the code running as a result of the interrupt, once its effect is clear to the user mode code, to know what the machine state was before the interrupt. There might be some mechanism for determining this but if so I doubt that any substantial amount of software relies on it.

So signals can be routed from signals, thread state would be handled transparently, the OS wrapper shouldn't need to be very involved in the process.

IF this approach is necessary then the appropriate way to do it is to invert it so the blocks themselves are checking for exceptions/interrupts inlined (especially in user mode code they will happen rarely).

I don't know the inner working of Wine very well. The first difficult
point that comes to my mind is ABI handling.

What is the difficulty you have in mind exactly? Here is how I would guess Wine works:

- loads Wine layer as shared object to memory somewhere
- loads Windows executable to memory, using mmap or what have you to correctly map out the address space
- scans executable code for calls to OS functions (and data section for addresses of said functions?) and replaces them with calls to the Wine layer functions
- repeats second and third step when new code is loaded (DLLs)

In a user mode emulator the resulting code that's running should appear like a normal Linux application. Obviously the Wine layer would also be translated. Depending on how shared object loading is handled by the emulator, and assuming a normal shared object load procedure is used by Wine, it might be possible to replace such a thing with native SOs where available.

User mode is not that trivial: you have to handle memory mapping,
dispatching signals, translate syscalls (if you think all syscalls
are identical accross kernels and architectures, you're wrong) and
so on. Nothing rocket science, but even writing a console emulator
isn't rocket science. Making it efficient *is* difficult

I didn't say "console emulator", I said console emulator that requires a dynamic recompiler which obviously implies efficiency requirements as well. Memory mapping can largely be handled by the OS, even if you may end up needing your own elf loader. Dispatching signals is greatly simplified by what I said above - the signal handler would basically just wrap the emulated signal directly. I've looked at qemu's syscall mapping and it's probably the worst part, but nothing exactly insurmountable, and it's more viable of a work in progress kind of thing since I'm sure many useful pieces of software don't use many syscalls.

Oh and I'm not reinventing the wheel at all here. I'm just trying
to improve something that once worked in QEMU for the fun of it.

I never said you were reinventing the wheel, I was implying that I was potentially interested in doing so by throwing out qemu. But I'd love to see how qemu works first. I hope you try to get Wine working through it.

@greendots: I can't compare QEMU to DOSBox cycles, I know
nothing about it. Perhaps compiling nbench for DOS is possible?
Anyway don't forget DOSBox contains some HW emulation that the
QEMU I used to test speed doesn't.

I'll save you the trouble and just tell you that things will be much worse in DOSBox.

 

[ldesnogu]

A quick update: I've almost doubled the speed of QEMU running on ARM; guess that should be about DX4-100 speed for nbench on OMAP3@600 MHz; I need to find time to setup my BeagleBoard to check it on something else than what I'm using

There's still room for many improvements. And these will be needed if I want to add some peripheral simulation...

 

[dflemstr]

One thing I've been wondering about (and please delete this post promptly if this is the wrong place for this) is why an executable couldn't be *statically* recompiled from x86 to ARM. Why do we have to have a dynamic recompiler and not just a static recompiler that compiles x86 code to ARM, adjusts addresses and register calls etc to suit the new architecture, then spitting out an ELF executable that can be run natively?

I can understand why this doesn't work for Windows → Linux, but from Linux x86 to Linux ARM, the two systems will have the same linking and invocation mechanisms, be call-compatible for dynamic libs etc and since both ARM and 686 are LSB machines, you don't have to do some crazy translation of certain value border cases.

I obviously don't know what I'm talking about since I'm asking this question in the first place, but my rational approach to this problem tells me that there shouldn't be an issue with static recompilation. What am I missing?

 

[rv6502]

One thing I've been wondering about (and please delete this post promptly if this is the wrong place for this) is why an executable couldn't be *statically* recompiled from x86 to ARM. Why do we have to have a dynamic recompiler and not just a static recompiler that compiles x86 code to ARM, adjusts addresses and register calls etc to suit the new architecture, then spitting out an ELF executable that can be run natively?

I can understand why this doesn't work for Windows → Linux, but from Linux x86 to Linux ARM, the two systems will have the same linking and invocation mechanisms, be call-compatible for dynamic libs etc and since both ARM and 686 are LSB machines, you don't have to do some crazy translation of certain value border cases.

I obviously don't know what I'm talking about since I'm asking this question in the first place, but my rational approach to this problem tells me that there shouldn't be an issue with static recompilation. What am I missing?

yes, it would work for statically linked executables.
but most executables on most Linux systems are dynamically linked, libraries are loaded as needed and library function calls are also linked as needed.
in effect, most x86 Linux executables are self-modifying (the LD library does the "self"-modification) so you cannot statically translate them.
you could translate them at loading time if you also pre-linked and translated all the dynamic libraries at loading time as well but I'm not sure this would be practical.
and it might fail for program that are actively using dynamically loaded libraries such as plugins.

but this whole thing is pretty pointless as most Linux executables are provided with source code so you just recompile them for ARM and that's it.

you need a x86->ARM translation because the goal of the OP is to run x86 wine which is a self-modifying application.

 

[dflemstr]

you need a x86->ARM translation because the goal of the OP is to run x86 wine which is a self-modifying application.

Thanks for the explanation, but I knew that last point already, don't worry, I'm not that technically challenged I understand that the extra Wine layer will make static recompilation impossible, now that I know how the winelibs does its magic.

I just didn't know exactly how the mechanics of dynamic linking worked under the C level (would there be a section of the executable that would serve as a lookup table for functions (pointers to pointers if you will), easily identified and thus easily dynamically changeable, letting the rest of the executable be statically recompiled? Or would the actual code calling dynamically linked code actually be changed with updated addresses? etc.) so for all I knew, static recompilation would have been possible, but now I see why it isn't.

 

[ldesnogu]

Well that wouldn't be easy for two reasons:

- deciding between code and data is a problem known to be intractable; so without human assistance one can't have correct static translation
(an example of mixed dynamic/static translation was achieved by FX!32: it collected dynamic information while running a program and based on that information was doing partial static translation off-line)

- syscall on ARM Linux and x86 Linux have enough differences that it'd require a layer anyway; I even bet that I can provide you with an i386 statically compiled program that wouldn't run on some i386 Linux machines

Anyway the end goal is not to run i386 Linux on ARM Linux. I just use that as a way to improve performance (and correctness) of QEMU on ARM.

 

[xaim00]

One thing I've been wondering about (and please delete this post promptly if this is the wrong place for this) is why an executable couldn't be *statically* recompiled from x86 to ARM. Why do we have to have a dynamic recompiler and not just a static recompiler that compiles x86 code to ARM, adjusts addresses and register calls etc to suit the new architecture, then spitting out an ELF executable that can be run natively?

I can understand why this doesn't work for Windows → Linux, but from Linux x86 to Linux ARM, the two systems will have the same linking and invocation mechanisms, be call-compatible for dynamic libs etc and since both ARM and 686 are LSB machines, you don't have to do some crazy translation of certain value border cases.

I obviously don't know what I'm talking about since I'm asking this question in the first place, but my rational approach to this problem tells me that there shouldn't be an issue with static recompilation. What am I missing?

In dynamic translation/recompilation solutions you let the program-flow guide translation. If we translate offline (program not running) it might hard separating code from data. It is not possible to guarantee that all translated code reside at same addresses as in the original binary. We are dealing with different ISA and opcode size varies between architectures an so on.

Because it's hard to know what a code does without executing it destinations of indirect jumps (jump target generated during execution) is hard to resolve and the jump target won't correlate between the original and translated code. Self modifying code and dynamic generation of code is another problem static translation can't handle.

If you combine static translation with an simple execution environment and fallback interpreter it can handle the problems above.

In dynamic translation when encountering an indirect jump we can return to the dispatcher and it will execute the correct block from the code cache. Dynamic code generation is handled implicitly, self modifying code can be handled, but is expensive.

I'm not an expert in this area and might be wrong. If that's the case i'm sure the gurus will correct me

Edit: beaten, i'm a slow typer hehe

 

[Exophase]

What I never really understand is why people want static recompilation when dynamic can produce code that's about as good most of the time, and the cost for recompiling it is relatively small and relatively one-time.

 

[dflemstr]

What I never really understand is why people want static recompilation when dynamic can produce code that's about as good most of the time, and the cost for recompiling it is relatively small and relatively one-time.

Well, it's just two different approaches to the same problem I guess. It's just that static recompilation intuitively seems to be better suited for something like this.

As I see it, these are the pros and cons of static/dynamic recompilation:
Dynamic:
+ More intelligent optimizations because you know how, when and how often code is accessed
+ You can improve optimizations by using multiple compiler sweeps while the application is running
- More difficult to cache generated code (between sessions, for example) but this kidna applies to static recompilation too
- Overhead for recompilation; you have to put more effort into creating a efficient compiler and you have to compromise instead of optimizing ( ) because of the limited headroom for the compiler.
- Refcounting, counting accesses, dynamic inlining, loop unwinding and stuff like that as mentioned in point #1 adds a lot of overhead and might not be possible to do.

Static:
+ Practically no time/resource limits for the recompilation
- No information about how the code will be used, so generated code will be suboptimal because of the halting problem etc.

So it, again: intuitively, seems to be better to use static recompilation when you'd need speed, especially when a program already is heavily optimized already (as most icc-compiled/msvc-compiled Windows programs probably are) and you because of that need to "unoptimize" the code and reoptimize it for ARM again, thus needing a lot of time for the compiler.

Wouldn't it be possible to somehow recompile a Windows program to statically link against the winelibs (+ getting it translated to ARM of course) and thus making the code static? This should be possible by interpreting the code offline, thus determining what is data and what isn't (by taking both routes of a fork etc), and where the hotspots lie and so on...

Maybe I'm just babbling, and should leave this to the experts.

PS, I rank compilation technologies in the following order, so use that to judge me:
LLVM (low level BC) > JVM (high level BC) > Compiled optimized C-ish code (one-many-one mapped code) > ASM (one-one mapped code) > Interpreted code (many-many-one mapped code) > Typing monkeys

 

[Exophase]

So it, again: intuitively, seems to be better to use static recompilation when you'd need speed, especially when a program already is heavily optimized already (as most icc-compiled/msvc-compiled Windows programs probably are) and you because of that need to "unoptimize" the code and reoptimize it for ARM again, thus needing a lot of time for the compiler.

I think a problem that you and a lot of other people have is that you're overlapping different compiler technologies. A recompiler of this nature is not a compiler, it's a binary translator. It does not have the same optimization opportunities nor associated opportunity costs that a compiler for a higher level language would. Most of the optimizations that a commercial compiler does are either machine independent or only loosely coupled to machine parameters like register set size or vector capabilities. Even when the particular machine parameters are addressed a lot of high-level information referenced is lost in the process. So you really can't "deoptimize" a good number of things and certainly shouldn't bother "reoptimize" it in the same fashion it originally was. Machine code is not like source code or even bytecode in that it really was never intended to be statically compiled into another language.

Of course I'm not saying that a recompiler has to be limited to direct opcode at a time translation and there aren't propagation optimizations, some of them to help fit a different ISA better. But most of the heavy lifting will have already been done by whatever compiled it in the first place. For something like x86 where you have more registers on ARM you don't even have to do register allocation beyond what the compiler has, and you can't really reverse and redo its register allocation because you can't track aliasing the same way a compiler can. There are probably a few instances where you can cache some stack accesses if there aren't intermediate opposing memory accesses inbetween them, but this probably doesn't win you that much in typical code. And this and other useful optimizations aren't going to cost you a lot of time complexity (nor space), neither is scheduling. It won't be a trivial amount of time, but bear in mind that with static recompilation or caching blocks you're competing against the time it takes to load the code off of non-volatile storage, which is not really trivial either.

Wouldn't it be possible to somehow recompile a Windows program to statically link against the winelibs (+ getting it translated to ARM of course) and thus making the code static? This should be possible by interpreting the code offline, thus determining what is data and what isn't (by taking both routes of a fork etc), and where the hotspots lie and so on...

Why would anyone want to do this? If you have the source code and need to recompile it then you can properly port it in the first place, which could involve using winelib (but how much really uses that?).. the amount of useful code that's so hard to port that you'd prefer recompiling it is very small. If you want to port something that's a big blob of assembly code then you'd probably be better off using a tool to convert at the assembly language, which is still higher level than machine code. Then you can hand tweak it as well.

The real point of this project is to emulate legacy x86 software where the source isn't available. The interest in anything else is very low.

PS, I rank compilation technologies in the following order, so use that to judge me:
LLVM (low level BC) > JVM (high level BC) > Compiled optimized C-ish code (one-many-one mapped code) > ASM (one-one mapped code) > Interpreted code (many-many-one mapped code) > Typing monkeys

Eh, what do you mean "rank"? In terms of what, performance? Importance? How much they impress you? But most of these things are really not at all comparable.

 

[dflemstr]

Eh, what do you mean "rank"? In terms of what, performance? Importance? How much they impress you? But most of these things are really not at all comparable.

I rank them by how often I use them and which ones I prefer (otherwise, I wouldn't have said that it's how *I* rank them, but would have linked a source instead). Of course they're not comparable (in the sense that you mean), because then they wouldn't be different categories of compilation methods (in lack of a better term) and execution models otherwise.

Obviously I need to learn more about compiler mechanics before I'll be able to intelligently make any further comments in this thread, so I'll let you continue with on-topic talk now

 

[mcobit]

With the speed of a 486 100 mhz Win95 should be runable at good speed. Maybe thats a thing, that everybody would love to see. It also would enable us to run some Diablo 1 and others. I played Diablo 1 just fine on my 486 66 mhz on win 95.

Great work and keep it Up!

 

[borgqueenx]

With the speed of a 486 100 mhz Win95 should be runable at good speed. Maybe thats a thing, that everybody would love to see. It also would enable us to run some Diablo 1 and others. I played Diablo 1 just fine on my 486 66 mhz on win 95.

Great work and keep it Up!

emulation of win95 can maby be done with BOSCHS or whatever the name was, an emulator that was ported to the psp.
But maby this project can get more

 

[cb88]

[snip]
emulation of win95 can maby be done with BOSCHS or whatever the name was, an emulator that was ported to the psp.
But maby this project can get more

Bochs is just a plain c code emu (and slow even on x86 desktops) that works on nearly any arch qemu has more optimisations although its still pretty slow on x86 if you don't have the kernel module loaded

 

[mcobit]

With the speed of a 486 100 mhz Win95 should be runable at good speed. Maybe thats a thing, that everybody would love to see. It also would enable us to run some Diablo 1 and others. I played Diablo 1 just fine on my 486 66 mhz on win 95.

Great work and keep it Up!

emulation of win95 can maby be done with BOSCHS or whatever the name was, an emulator that was ported to the psp.
But maby this project can get more

Oh, I know it can be done with BOCHS but it will be faster with Qemu and maybe will enable us to play some low spec win95 games.
Win95 on PSP was slow as hell, but with the power of a 486 100...

BTW is there a way to get some opengl emulation in QEMU?

 

[borgqueenx]

mm, i gotta say it would be cool to play the windows95 version of red alert
its the best red alert of all.