Systems Engineering · week 3 · station III

Emulation

Mipster as the universal machine, the price of interpretation, and self-execution.

The loop

Fetch, decode, execute, repeat. A page of C* per instruction group — and it runs every program for the machine.

        // mipster's core, in spirit
        while (1) {
          fetch();     // ir = memory[pc]
          decode();    // opcode, registers, immediate
          execute();   // one of fourteen cases
          // exceptions and timeouts stop the loop
        }
      

The machine chapter's cycle as a program. The guest's code is data in the host's memory, read one word at a time, never executed by the host's processor.

This is Turing's universal machine: one program that becomes any program when handed its description.

And it is an operating system: the guest cannot touch anything the emulator does not hand it. Isolation for free, and no self-reference.

In the terminal

Self-execution: the emulator runs its own machine code.

one guest instruction, about 2,600 on the host

        $ make emu
        ./selfie: … 85754 executed instructions …
        $ make emu-emu
        > selfie.m: … 86380 executed instructions …
        ./selfie: … 222410917 executed instructions …
      

Printing its synopsis costs selfie 85,754 instructions. Under mipster inside mipster: 86,380 for the guest, 222 million for the host, ×2,593.

The guest cannot tell: same output, same count. Semantically transparent, computationally expensive.

What the bill buys

Emulation is isolation. Everything the guest does is a read in the host.

Space

The guest's memory is an array in the host's heap. An address the guest computes is an index the emulator checks. Out of range: an exception, handled by the emulator, never by the hardware. Spatial isolation by construction.

Time

The emulator counts instructions and can stop after any number of them. A guest that loops forever costs the host exactly the instructions the host chooses to spend. Temporal isolation by construction.

Trust

Nothing the guest does reaches the host's processor. The host's own isolation is never at stake. And that is the property that virtualization gives up, on purpose, for a factor of twelve.

Emulation as the executable specification of virtualization: whatever hypster does must be indistinguishable to the guest from what mipster does. Week 6 shows that it is.

Station III

A universal machine can run any machine — so nothing general about the machines it runs can be decided.

The gift and the limit are the same fact. Because mipster runs every program, it cannot know whether the program it is running will stop, or divide by zero, or read outside its memory, before it happens. Rice's theorem, on the emulator.

So it does not try to know. It counts instructions and stops after a timeout; it checks each address as it is used; it catches the division when it occurs. Bounding, not deciding — the third sentence of week 1, and the design principle of every kernel.

Next weeks

Space: give each guest its own addresses and translate them, week 4. Time: the timer and the scheduler, week 5. Then run the guest on the real processor and see what breaks, week 6.

Assignment

self-assembler: generate code, and assemble selfie's own assembly.

Extend last week's parser with code generation: for each parsed instruction, encode it with selfie's own encode_X procedures and emit the word into the code binary, as the compiler does.
Handle the data segment as the assembly file presents it, and the entry point, so that the result is a loadable binary.
Self-assemble. ./selfie -c selfie.c -s selfie.s, then ./selfie -a selfie.s -o selfie.m, and compare with ./selfie -c selfie.c -o selfie.m. Identical bytes: a fixed point of your own.
./grader/self.py self-assembler.

What the fixed point proves

That the assembler agrees with the compiler's backend and the disassembler, on the one input that is all of selfie. Not that it is correct — the compiler class spends a week on why. Keep the assembler; week 10 hands it to a model checker.

After this week

Listen, then read.

Listen

Bach · The Well-Tempered Clavier, Book II — Sviatoslav Richter. Twenty-two years after Book I, the same twenty-four keys again, on whatever keyboard is at hand: the same specification executed on a different machine, and the music cannot tell. Emulation is semantically transparent.

Read

Virtual Machines: Versatile Platforms for Systems and Processes — Smith and Nair, 2005: emulation, binary translation and virtualization in one book, the taxonomy this class uses. And, more technical, QEMU, a Fast and Portable Dynamic Translator — Bellard, 2005: the emulator everyone runs, in seven pages; mipster is what it would be without the translation.

SE 04 · Virtual Memory →