Writing an emulator

This is a general question, not specific to x86, 32-bit or 64-bit machines.
If I want to write code to emulate each instruction, how should the
instruction, paging, segment mechanisms be done so they are reasonable fast?
Any instruction that changes a register can invalidate any stored
associations (say in a hash table). Doing the ADD and SUB parts are easy
but the addressing is hard!
There must be some trick.

On Aug 5, 7:49*am, "Stubby" <spamt...@crayne.org> wrote:
> This is a general question, not specific to x86, 32-bit or 64-bit machines.
> If I want to write code to emulate each instruction, how should the
> instruction, paging, segment mechanisms be done so they are reasonable fast?
> Any instruction that changes a register can invalidate any stored
> associations (say in a hash table). *Doing the ADD and SUB parts are easy
> but the addressing is hard!
> There must be some trick.


Just-in-time binary recompilation/translation is probably your best
bet.

You have, however discovered one of the truths of emulation – it’s the
memory accesses and thing like flags which really clobber emulator
performance.

That being said, there are a few shortcuts you can take. For example,
the vast majority of code runs with CS, DS, ES and SS mapping the
whole 4GB from location zero, you can a separate fast set of
instruction emulation routines when that condition is true for your
(emulated) processor. If you encounter an explicit prefix, you go
back to slow mode for that instruction.

You can also use the paging mechanism of the host processor,
especially if the page size is the same, and use it to manage the
actual page translations. Then you’re basically handing the TLB
misses in your emulator like happens on most RISC processors. You’ll
have to convince the host OS to let you do some of that, of course.

On Aug 5, 5:49 am, "Stubby" <spamt...@crayne.org> wrote:
> This is a general question, not specific to x86, 32-bit or 64-bit machines.
> If I want to write code to emulate each instruction, how should the
> instruction, paging, segment mechanisms be done so they are reasonable fast?
> Any instruction that changes a register can invalidate any stored
> associations (say in a hash table). Doing the ADD and SUB parts are easy
> but the addressing is hard!
> There must be some trick.

There're a number of tricks:
1. so-called ring aliasing and ring compression on x86, where most of
the VM's code runs inside the host OS natively but never at CPL=0,
rather at CPL=1,2 and 3, which makes it possible for the host to
control the VM execution. There're a number of hacks for x86 to make
this work. The x86 architecture wasn't designed with virtualization in
mind. Only the SVM/VMX(VT) extensions finally addressed the x86
virtualization issues and even that only partially (e.g. you still
need to decode in software the instructions that touch virtualized
devices, even though the CPU has everything for that inside and that
could be made available to the virtualizing software).
2. the hardware may provide some facilities to help with the
virtualization. For example, if all privileged instructions can be
easily intercepted and emulated, that's one way. Then the hardware may
provide separate TLBs for host and guest virtual to physical address
translation. That way you can fully separate the host and guest memory
accesses and run both at native speed or very close to unless you need
to emulate some device of a VM.
3. binary translation/JIT recompilation is often possible, but just as
well often needs a number of hacks. For example, if the code modifies
itself, executes what's supposed to be data or jumps into the middle
of instructions, then there're problems to address. You obviously
can't do the translation/recompilation just once on all kinds of
architectures. Often you need to keep doing that on the fly. Otherwise
the emulation isn't fully correct.

There're a number of documents on the subject. See, for example,
http://en.wikipedia.org/wiki/X86_virtualization and the article to
which it links: http://www.floobydust.com/virtualiza...awton_1999.txt

Alex

"Stubby" <spamtrap@crayne.org> wrote in message
news:4aidnWlaJ4zB0QXVnZ2dnUVZ_o_inZ2d@comcast.com. ..
> This is a general question, not specific to x86, 32-bit or 64-bit
machines.
> If I want to write code to emulate each instruction, how should the
> instruction, paging, segment mechanisms be done so they are reasonable
fast?
> Any instruction that changes a register can invalidate any stored
> associations (say in a hash table). Doing the ADD and SUB parts are easy
> but the addressing is hard!
> There must be some trick.
>

What are your goals? It works? Speed? Accuracy? There are always a bunch
of trade-offs since emulating an instruction adds time overhead.

Do you want to spend your time creating quick emulations for little used
instructions?

If "No.", then you'll need to gather statistics on opcode frequency so you
can know which instructions are important to emulate quickly and/or
accurately. Most of this information comes from either those attempting to
detect malware code or those authoring virus code. E.g., for x86:

1) http://www.blackhat.com/presentation...S-06-Bilar.pdf
2) "Opcode Frequency Statistics" by Z0mbie (search for it...)

> trick

For most of the explantions on how professionals do this, there aren't any
"tricks" but hard, and smart work to get the instruction to emulate quickly
and accurately. A classic is DEC's FX!32 which is/was a combination of
brute force, caching tweaks, and binary translation, etc.:
http://www.realworldtech.com/page.cf...2803224105&p=2

You can locate more indepth articles on FX!32 on CiteseerX:
http://citeseerx.ist.psu.edu/


On the other hand, you can find programs which use various tricks to quickly
and accurately disassemble instructions. From such shady locations, you can
also find very good instruction emulators, such as "INTEL complex emulator"
by Methyl (search for it...). If you're interested in emulators, the
article on his emulator is worth a read despite the source...


And, of course, you can look at the code to many different types of
"emulators" which are open sourced: DOSBox, QEMU, MAME or MESS, Scitech's
x86emu, etc.


"Study of the techniques for emulation programming"
http://personals.ac.upc.edu/vmoya/docs/emuprog.pdf


Rod Pemberton