Trap-and-Emulate and Binary Translation
The Popek-Goldberg
theorem told us when a machine can be virtualized. This lesson is about
how: the concrete machinery a VMM uses to run a whole guest operating system on real hardware
while staying in complete control. There are three historic techniques, and every hypervisor you will
ever meet is built from one or more of them — trap-and-emulate (the textbook ideal),
binary translation (VMware's answer to x86's leaks), and
paravirtualization (Xen's answer). By the end you'll understand why x86 needed such
cleverness before the hardware caught up.
The ideal: trap-and-emulate
Recall the plan. The VMM runs the guest — kernel and all — de-privileged, below the
ring 0 it thinks it owns. Now the CPU does the policing for free:
- An innocuous guest instruction (arithmetic, a register move, a branch) runs
directly on the real CPU at full native speed. No VMM involvement whatsoever — this is
where the "performance" property is earned.
- A privileged instruction (the guest kernel trying to load a page-table base, mask
interrupts, or touch a device) executes in the wrong mode, so the hardware raises a fault: a
trap. Control jumps to the VMM.
- The VMM decodes the faulting instruction, emulates its effect on the
virtual machine's state (updates a shadow of the guest's control registers, virtual interrupt
flag, virtual devices), advances the guest program counter, and resumes the guest.
The guest never notices: from its point of view the privileged instruction "just worked". This
trap→emulate→resume loop is the beating heart of a classical VMM. It is exactly limited direct execution,
lifted from processes to an entire OS. Trace the loop below.
The loop, drawn
The important economics: only the trap edges cost anything. If a workload almost never executes
privileged instructions, it runs at nearly native speed. A syscall-heavy or interrupt-heavy kernel
workload, though, can trap thousands of times a second, and each trap is a full mode-switch round trip
into the VMM — this is the tax trap-and-emulate must pay, and the reason later hardware works so hard to
make traps cheap.
Why the ideal breaks on x86
Trap-and-emulate has one non-negotiable prerequisite: every sensitive instruction must trap. On
classic x86 that is false — there are 17 sensitive-but-unprivileged instructions (recall
\texttt{popf}, \texttt{sgdt},
\texttt{smsw}). A de-privileged guest that executes
\texttt{popf} to disable interrupts gets no trap; the
interrupt-flag write is silently dropped. The VMM never finds out, the virtual machine's state drifts
out of sync with what the guest believes, and eventually the guest crashes or misbehaves. Pure
trap-and-emulate simply cannot run an unmodified x86 guest. Two very different rescues emerged.
Rescue 1 — VMware's dynamic binary translation
VMware's insight (1998–99): don't wait for a trap that will never come — rewrite the dangerous
code before it runs. The VMM contains a just-in-time binary translator. As the
guest kernel is about to execute a block of code, the translator scans it and produces a safe,
functionally-equivalent version:
- Innocuous instructions are copied through essentially identical (translation is
"mostly the identity") so they still run native.
- Each sensitive instruction — trapping or not — is replaced by a safe sequence: usually a
call into the VMM (a "callout") that emulates the intended effect on virtual state.
The silent leaks are caught because the translator can see them in the code, even though the
hardware wouldn't.
- Translated blocks are stored in a translation cache and chained together, so a hot
block is translated once and then re-executed straight from the cache — amortising the
translation cost across millions of executions. This is the same trick a JIT compiler uses.
Crucially only guest kernel (ring 0) code needs translating; unprivileged
guest user code has no sensitive instructions and runs native, untranslated. So a
user-space-bound workload sees almost no overhead, while kernel-bound code pays for translation. VMware's
translator was so good that on many workloads binary translation actually beat the first
generation of hardware virtualization, because a translated \texttt{popf} is
an inline callout, whereas a hardware trap was a slow VM-exit.
Rescue 2 — Xen's paravirtualization
Xen (Cambridge, 2003) took the opposite philosophy: if the problem is that the guest issues instructions
the VMM can't safely intercept, then change the guest so it never issues them. In
paravirtualization (PV) the guest OS is ported to a slightly different,
virtualization-friendly interface. Where the guest kernel used to execute a privileged instruction, it
now makes an explicit hypercall — a deliberate, well-defined call down into the
hypervisor (the VM analogue of a syscall). "Load this page table", "update this PTE", "mask my virtual
interrupts" all become clean API calls rather than trapped instructions.
- Pro: no traps to catch, no code to translate — the guest cooperates. Xen PV
delivered near-native performance on the un-virtualizable x86 of its day, and let the guest
batch many page-table updates into one hypercall (far cheaper than one trap each).
- Con: the guest OS must be modified and recompiled. That is fine for
open-source Linux/BSD (Xen upstreamed a PV port) but impossible for a closed guest like older Windows.
Paravirtualization trades transparency for speed.
The paravirtual idea never died — even today, "unmodified" guests on modern hardware still use
paravirtual drivers (virtio) for fast I/O, which you'll meet in the
I/O
virtualization lesson. The lesson: even a leaky ISA can be virtualized if you are willing to
translate the binary (VMware) or rewrite the guest (Xen).
Counting the traps
Let's make the trap tax concrete. A workload issues a stream of instructions; some fraction are
privileged. Under pure trap-and-emulate, each privileged instruction is a costly trap. Binary
translation replaces those with cheaper inline callouts, and a translation cache means each unique kernel
block is only translated once. The simulation compares the total cost.
// Cost of running a kernel-heavy workload three ways. Costs in (illustrative) cycles.
const TRAP = 1500; // a full trap/mode-switch round trip into the VMM
const CALLOUT = 300; // a binary-translation inline call into the VMM
const XLATE = 4000; // one-time cost to translate a unique block
const NATIVE = 1; // an innocuous instruction
const totalInsns = 1_000_000;
const privFrac = 0.03; // 3% of executed insns are privileged/sensitive
const priv = Math.round(totalInsns * privFrac);
const uniqueBlocks = 800; // distinct kernel code blocks that get executed
// Pure trap-and-emulate: every privileged insn traps (assume no silent leaks for the model).
const teCost = (totalInsns - priv) * NATIVE + priv * TRAP;
// Binary translation: each privileged insn becomes a callout; translate each unique block once.
const btCost = (totalInsns - priv) * NATIVE + priv * CALLOUT + uniqueBlocks * XLATE;
console.log(`executed instructions : ${totalInsns.toLocaleString()}`);
console.log(`privileged/sensitive : ${priv.toLocaleString()} (${privFrac * 100}%)`);
console.log(`trap-and-emulate cost : ${teCost.toLocaleString()} cycles`);
console.log(`binary-translate cost : ${btCost.toLocaleString()} cycles`);
console.log(`speedup of BT over T&E: ${(teCost / btCost).toFixed(2)}x`);
console.log("\n=> when privileged ops are frequent, cheap inline callouts beat expensive traps —");
console.log(" exactly why VMware's translator out-ran first-gen hardware traps on kernel-heavy loads.");
The three techniques, side by side
| Technique | Guest modified? | How sensitive ops are handled | Real system | Catch |
|---|
| Trap-and-emulate | no | they trap; VMM emulates | IBM VM/370 | needs sensitive ⊆ privileged (fails on x86) |
| Binary translation | no (unmodified) | translator rewrites them to VMM callouts, cached | VMware Workstation / ESX | translation overhead; complex engine |
| Paravirtualization | yes (ported) | guest issues explicit hypercalls instead | Xen (PV mode) | can't run closed/unmodifiable guests |
It sounds terrifying — a VMM editing another OS's machine code as it runs. The safety comes from three
disciplines. First, translation is overwhelmingly the identity: the translator changes only the
handful of sensitive instructions and control-flow that leaves a block, so the guest's logic is
preserved instruction-for-instruction. Second, the guest never executes its own kernel code
directly — it only ever runs the translated copy out of the translation cache, so there is no way
to "sneak past" the translator. Third, self-modifying guest code (and pages the guest writes to that
hold translated code) is caught by write-protecting those pages, so the cache is invalidated and
re-translated. It is precisely the same set of tricks a modern JavaScript JIT uses to safely run
untrusted code faster than an interpreter.
A frequent muddle: hearing "the VMM emulates the instruction" and picturing a slow software CPU
interpreting the whole guest, one instruction at a time (like QEMU's pure interpreter). That is
not what trap-and-emulate or binary translation do. The overwhelming majority of guest
instructions run natively on the real CPU; only the rare sensitive ones are emulated in
software. "Emulate" applies to those individual leaking/privileged instructions, not to the guest as a
whole. If the VMM interpreted everything it would satisfy fidelity and safety but violate
performance — and by Popek-Goldberg's definition it would no longer be a virtual machine monitor
at all, just an emulator.
The design law
- Trap-and-emulate: run the guest de-privileged; privileged instructions trap and
the VMM emulates them. Clean and fast — but only works if every sensitive instruction traps.
- Binary translation: a JIT in the VMM rewrites guest kernel code, turning sensitive
instructions (even non-trapping ones) into VMM callouts; a translation cache amortises the cost. Runs
unmodified guests on a leaky ISA (VMware).
- Paravirtualization: modify the guest OS to replace privileged instructions with
explicit hypercalls. Near-native speed and batching — but the guest must be recompiled, so
no closed guests (Xen PV).
Where next
Software heroics kept x86 virtualization alive for a decade. Then Intel and AMD did the honest thing and
fixed the CPU. Next:
hardware-assisted
virtualization — VT-x and AMD-V — which added a real hypervisor mode and made textbook
trap-and-emulate work again, this time in silicon.