Trap-and-Emulate: The Popek-Goldberg Conditions and Sensitive Instructions

A guest kernel believes it owns the privilege level that can disable interrupts, install page tables, and halt the processor. The host cannot grant that belief, because the host itself needs exactly those powers. Trap-and-emulate resolves the conflict with a single move: run the guest kernel at a lower privilege level and let the hardware raise an exception whenever the guest touches something that only the real kernel may touch. The exception handler inspects the faulting instruction, performs the effect on the guest’s behalf, and resumes the guest at the next instruction.

That sketch is old and still correct, but the interesting part is not the loop. It is the question of which instructions the hardware agrees to fault on. If an instruction that reveals or changes machine state does not fault when executed at low privilege, the guest can observe the real machine and the illusion collapses. Formalising that requirement is what makes trap-and-emulate a design discipline rather than an implementation trick.

Three properties a virtual machine monitor must satisfy

Popek and Goldberg, writing in 1974 about third-generation mainframes, defined a virtual machine monitor (VMM) as a control program that provides an environment identical to the original machine, except for timing dependencies and resource availability. They then reduced the demand to three properties.

The first is equivalence: any program running under the VMM produces results indistinguishable from running on the bare machine, apart from timing and the size of memory and devices. Equivalence is about observable behaviour, not internal state, which matters because the VMM is allowed to keep the guest’s privileged registers somewhere else entirely.

The second is resource control: the VMM retains complete control of system resources. A guest must not be able to escape to real memory it does not own, or to a device another guest is using. This is the property that forbids “helpful” shortcuts such as letting the guest kernel run at the highest privilege level and trusting it.

The third is efficiency: a statistically dominant fraction of instructions must execute directly on the hardware without VMM intervention. This is the property that rules out full interpretation of the instruction stream, which would satisfy equivalence and control at a cost of one host dispatch per guest instruction.

The efficiency requirement is why the design is trap-and-emulate rather than emulate-and-emulate. The VMM only wants to be involved for instructions the guest is not entitled to execute. Everything else should run at native speed, which in the 1970s meant literally the same machine code, and today means the same machine code under hardware-assisted execution.

Sensitive instructions and the virtualization theorem

Popek and Goldberg classified instructions along two axes. An instruction is privileged if it traps when executed in user mode. An instruction is sensitive if it behaves differently depending on the privilege level or the current machine configuration, or if it changes that configuration. Sensitivity splits further into control-sensitive instructions, which alter the machine’s configuration, and behaviour-sensitive instructions, which merely read it. An instruction that is neither is innocuous, and innocuous instructions can always be executed directly.

The theorem that follows is short: an architecture is virtualizable if and only if the set of sensitive instructions is a subset of the set of privileged instructions. If every sensitive instruction already traps at low privilege, the VMM needs no other interception mechanism. Equivalence holds because the guest cannot observe a difference without executing a sensitive instruction, and every sensitive instruction reaches the VMM. Efficiency holds because all innocuous instructions run natively.

This gives a concrete test for any architecture. Take the instruction set, list the instructions that read or write privileged state, and check whether each one faults in user mode. Where the answer is yes, a classic VMM is possible. Where an instruction reads privileged state without faulting, the architecture is not virtualizable in the strict sense, and the VMM must either patch guest code or rely on a hardware feature that did not exist when the theorem was written.

The fault-decode-emulate loop

The mechanism at the centre of a classic VMM is a dispatcher that runs after every trap. The guest’s instruction pointer identifies the instruction that failed; the VMM reads the bytes at that address from guest memory, decodes enough of them to know the operation and the operand, performs the operation on the guest’s saved state, and advances the guest’s instruction pointer by the instruction’s length.

/* Runs in the host after the guest's privileged instruction faulted. */
static void emulate_guest_fault(struct guest *g)
{
    unsigned char insn[15];           /* x86 instructions are at most 15 bytes */
    size_t len = read_guest_bytes(g, g->rip, insn, sizeof insn);
    if (len == 0)
        return;                       /* fault during fetch: reinject into guest */

    switch (insn[0]) {
    case 0x9C:                        /* PUSHF: push the guest's saved flags */
        g->rsp -= 8;
        write_guest_qword(g, g->rsp, g->rflags & GUEST_VISIBLE_FLAGS);
        g->rip += 1;
        break;
    case 0x9D:                        /* POPF: load flags, ignoring privileged bits */
        g->rflags = (g->rflags & ~GUEST_VISIBLE_FLAGS)
                  | (read_guest_qword(g, g->rsp) & GUEST_VISIBLE_FLAGS);
        g->rsp += 8;
        g->rip += 1;
        break;
    default:
        inject_undef_instruction(g);  /* the guest gets the fault instead */
        break;
    }
}

Three details in that sketch carry most of the difficulty. The VMM must decode an instruction whose length and encoding it does not control, including prefixes and operand-size overrides. It must read and write guest memory through the guest’s own address translation, because the instruction’s operand is a guest virtual address. And it must decide what happens when that access itself faults, which is the case the simple version above punts on.

The instruction pointer update is the sharpest constraint. Some instructions fault before any architectural state changes, so the VMM can emulate and then advance. Others change part of their state and then fault, so the guest expects either a completed instruction or a clean restart. A VMM that advances the pointer after a partial execution silently skips work the guest asked for; one that does not advance re-executes a step that already took effect. Getting restart semantics right for every instruction that can fault mid-way is where trap-and-emulate implementations become large.

Where the theorem fails: x86’s non-trapping sensitive instructions

The 32-bit x86 architecture is the standard counterexample. It has four privilege levels, which looks generous, but a set of instructions read or write privileged state while running at any level. Adams and Agesen, comparing software and hardware x86 virtualization, enumerate about seventeen such instructions. Four categories explain why they matter.

POPF is the cleanest case. Executed at a privilege level below the I/O privilege level, it does not fault; it loads the flags register but silently leaves the interrupt flag unchanged. A guest kernel that disables interrupts with POPF therefore continues running with interrupts enabled, and the VMM never learns that the guest intended to mask them. The guest’s interrupt state and the guest’s belief about its interrupt state diverge.

Descriptor-table instructions behave similarly. SGDT, SIDT, and SLDT read the guest’s view of the descriptor tables, and on the original architecture they returned the real values without faulting. SMSW reads the machine status word. A guest that inspects these registers learns where the host keeps its own tables, which is both an equivalence failure and an isolation failure. Later processors added a mode bit that makes these instructions fault at low privilege, which is a hardware fix to a hardware defect.

Privilege-level queries leak through ordinary instructions. The CS selector records the current privilege level in its low two bits, and a guest can read it with a far call or a push of the code segment. If the VMM runs the guest kernel at ring 1 to keep ring 0 for itself, the guest kernel can see that it is at ring 1. The remedy is to run the guest kernel at ring 3 and the guest’s user code at ring 3 as well, which flattens the guest’s own two-level protection into one host level. That flattening is the subject of ring compression.

Segmentation limits the address space. A 32-bit guest kernel expects flat segments covering four gigabytes, and the VMM would like to use segment limits to fence the guest off from host memory. Those two uses of the same mechanism conflict, so the VMM cannot have both. On x86 the resulting technique was to keep guest page tables shadowed and to accept the cost of keeping them consistent, a cost that second-level address translation later removed.

What the trap budget buys and costs

The virtue of trap-and-emulate is that it needs no guest cooperation. An unmodified operating system image boots, because the guest never sees anything except its own state. That property made it the default for mainframe virtual machines and, decades later, for the first x86 products.

The cost is proportional to how often the guest executes a sensitive instruction. A trap that occurs once per system call is invisible. A trap that occurs on every interrupt-flag update, or on every page-table write, dominates runtime. The x86 page-table case is the worst: a guest kernel writes page-table entries constantly, and each write must be trapped, validated, and reflected into a shadow table, so the VMM ends up doing more work per mapping than the guest does.

Two escape routes exist, and they define the rest of this cluster. The guest can be modified to cooperate, replacing sensitive operations with explicit calls to the VMM, which is paravirtualization. Or the hardware can be extended so that the guest kernel runs in a mode that keeps its privilege but is still subject to interception, which is the hardware-assisted model. The first removes traps by agreement; the second removes them by changing what counts as a trap.

The failure mode common to all three is state that the guest can observe but the VMM does not model. Flags registers, descriptor caches, control registers, and model-specific registers all carry state that no instruction set reference fully documents as virtualizable. Every mismatch is a bug that appears as a guest crash, a lost interrupt, or a measurement the guest should not have been able to take. The theorem’s value is that it tells the implementer exactly where to look: any instruction whose result depends on the configuration the VMM changed, and which does not fault, is a hole.