$ cd linux-2.6/drivers/lguest
$ cat README
Welcome, friend reader, to lguest.

Lguest is an adventure, with you, the reader, as Hero.  I can't think of many
5000-line projects which offer both such capability and glimpses of future
potential; it is an exciting time to be delving into the source!

But be warned; this is an arduous journey of several hours or more!  And as we
know, all true Heroes are driven by a Noble Goal.  Thus I offer a Beer (or
equivalent) to anyone I meet who has completed this documentation.

So get comfortable and keep your wits about you (both quick and humorous).
Along your way to the Noble Goal, you will also gain masterly insight into
lguest, and hypervisors and x86 virtualization in general.

Our Quest is in seven parts: (best read with C highlighting turned on)

I) Preparation
	- In which our potential hero is flown quickly over the landscape for a
	  taste of its scope.  Suitable for the armchair coders and other such
	  persons of faint constitution.

II) Guest
	- Where we encounter the first tantalising wisps of code, and come to
	  understand the details of the life of a Guest kernel.

III) Drivers
	- Whereby the Guest finds its voice and become useful, and our
	  understanding of the Guest is completed.

IV) Launcher
	- Where we trace back to the creation of the Guest, and thus begin our
	  understanding of the Host.

V) Host
	- Where we master the Host code, through a long and tortuous journey.
	  Indeed, it is here that our hero is tested in the Bit of Despair.

VI) Switcher
	- Where our understanding of the intertwined nature of Guests and Hosts
	  is completed.

VII) Mastery
	- Where our fully fledged hero grapples with the Great Question:
	  "What next?"

make Preparation!
Rusty Russell.

$ make Preparation!
[ arch/x86/lguest/boot.c ]
/*
 * A hypervisor allows multiple Operating Systems to run on a single machine.
 * To quote David Wheeler: "Any problem in computer science can be solved with
 * another layer of indirection."
 *
 * We keep things simple in two ways.  First, we start with a normal Linux
 * kernel and insert a module (lg.ko) which allows us to run other Linux
 * kernels the same way we'd run processes.  We call the first kernel the Host,
 * and the others the Guests.  The program which sets up and configures Guests
 * (such as the example in Documentation/lguest/lguest.c) is called the
 * Launcher.
 *
 * Secondly, we only run specially modified Guests, not normal kernels.  When
 * you set CONFIG_LGUEST to 'y' or 'm', this automatically sets
 * CONFIG_LGUEST_GUEST=y, which compiles this file into the kernel so it knows
 * how to be a Guest.  This means that you can use the same kernel you boot
 * normally (ie. as a Host) as a Guest.
 *
 * These Guests know that they cannot do privileged operations, such as disable
 * interrupts, and that they have to ask the Host to do such things explicitly.
 * This file consists of all the replacements for such low-level native
 * hardware operations: these special Guest versions call the Host.
 *
 * So how does the kernel know it's a Guest?  The Guest starts at a special
 * entry point marked with a magic string, which sets up a few things then
 * calls here.  We replace the native functions various "paravirt" structures
 * with our Guest versions, then boot like normal. */

[ drivers/lguest/lguest_device.c ]
/* Lguest guests use a very simple method to describe devices.  It's a
 * series of device descriptors contained just above the top of normal
 * memory.
 *
 * We use the standard "virtio" device infrastructure, which provides us with a
 * console, a network and a block driver.  Each one expects some configuration
 * information and a "virtqueue" mechanism to send and receive data. */

[ Documentation/lguest/lguest.c ]
/* This is the Launcher code, a simple program which lays out the
 * "physical" memory for the new Guest by mapping the kernel image and the
 * virtual devices, then reads repeatedly from /dev/lguest to run the Guest.
*/

[ drivers/lguest/lguest_user.c ]
/* This contains all the /dev/lguest code, whereby the userspace launcher
 * controls and communicates with the Guest.  For example, the first write will
 * tell us the Guest's memory layout, pagetable, entry point and kernel address
 * offset.  A read will run the Guest until something happens, such as a signal
 * or the Guest doing a NOTIFY out to the Launcher. */

[ drivers/lguest/core.c ]
/* This contains run_guest() which actually calls into the Host<->Guest
 * Switcher and analyzes the return, such as determining if the Guest wants the
 * Host to do something.  This file also contains useful helper routines, and a
 * couple of non-obvious setup and teardown pieces which were implemented after
 * days of debugging pain. */

[ drivers/lguest/hypercalls.c ]
/* Just as userspace programs request kernel operations through a system
 * call, the Guest requests Host operations through a "hypercall".  You might
 * notice this nomenclature doesn't really follow any logic, but the name has
 * been around for long enough that we're stuck with it.  As you'd expect, this
 * code is basically a one big switch statement. */

[ drivers/lguest/segments.c ]
/* The x86 architecture has segments, which involve a table of descriptors
 * which can be used to do funky things with virtual address interpretation.
 * We originally used to use segments so the Guest couldn't alter the
 * Guest<->Host Switcher, and then we had to trim Guest segments, and restore
 * for userspace per-thread segments, but trim again for on userspace->kernel
 * transitions...  This nightmarish creation was contained within this file,
 * where we knew not to tread without heavy armament and a change of underwear.
 *
 * In these modern times, the segment handling code consists of simple sanity
 * checks, and the worst you'll experience reading this code is butterfly-rash
 * from frolicking through its parklike serenity. */

[ drivers/lguest/page_tables.c ]
/* The pagetable code, on the other hand, still shows the scars of
 * previous encounters.  It's functional, and as neat as it can be in the
 * circumstances, but be wary, for these things are subtle and break easily.
 * The Guest provides a virtual to physical mapping, but we can neither trust
 * it nor use it: we verify and convert it here to point the hardware to the
 * actual Guest pages when running the Guest. */

[ drivers/lguest/interrupts_and_traps.c ]
/* Interrupts (traps) are complicated enough to earn their own file.
 * There are three classes of interrupts:
 *
 * 1) Real hardware interrupts which occur while we're running the Guest,
 * 2) Interrupts for virtual devices attached to the Guest, and
 * 3) Traps and faults from the Guest.
 *
 * Real hardware interrupts must be delivered to the Host, not the Guest.
 * Virtual interrupts must be delivered to the Guest, but we make them look
 * just like real hardware would deliver them.  Traps from the Guest can be set
 * up to go directly back into the Guest, but sometimes the Host wants to see
 * them first, so we also have a way of "reflecting" them into the Guest as if
 * they had been delivered to it directly. */

[ drivers/lguest/x86/switcher_32.S ]
/* This is the Switcher: code which sits at 0xFFC00000 to do the low-level
 * Guest<->Host switch.  It is as simple as it can be made, but it's naturally
 * very specific to x86.
 *
 * You have now completed Preparation.  If this has whet your appetite; if you
 * are feeling invigorated and refreshed then the next, more challenging stage
 * can be found in "make Guest". */

$ make Guest
[ arch/x86/lguest/boot.c ]
/* Welcome to the Guest!
 *
 * The Guest in our tale is a simple creature: identical to the Host but
 * behaving in simplified but equivalent ways.  In particular, the Guest is the
 * same kernel as the Host (or at least, built from the same source code). */

[ arch/x86/lguest/i386_head.S ]
/* This is where we begin: head.S notes that the boot header's platform
 * type field is "1" (lguest), so calls us here.
 *
 * WARNING: be very careful here!  We're running at addresses equal to physical
 * addesses (around 0), not above PAGE_OFFSET as most code expectes
 * (eg. 0xC0000000).  Jumps are relative, so they're OK, but we can't touch any
 * data.
 *
 * The .section line puts this code in .init.text so it will be discarded after
 * boot. */
.section .init.text, "ax", @progbits
ENTRY(lguest_entry)
	/* We make the "initialization" hypercall now to tell the Host about
	 * us, and also find out where it put our page tables. */
	movl $LHCALL_LGUEST_INIT, %eax
	movl $lguest_data - __PAGE_OFFSET, %edx
	int $LGUEST_TRAP_ENTRY

	/* The Host put the toplevel pagetable in lguest_data.pgdir.  The movsl
	 * instruction uses %esi implicitly as the source for the copy we'
	 * about to do. */
	movl lguest_data - __PAGE_OFFSET + LGUEST_DATA_pgdir, %esi

	/* Copy first 32 entries of page directory to __PAGE_OFFSET entries.
	 * This means the first 128M of kernel memory will be mapped at
	 * PAGE_OFFSET where the kernel expects to run.  This will get it far
	 * enough through boot to switch to its own pagetables. */
	movl $32, %ecx
	movl %esi, %edi
	addl $((__PAGE_OFFSET >> 22) * 4), %edi
	rep
	movsl

	/* Set up the initial stack so we can run C code. */
	movl $(init_thread_union+THREAD_SIZE),%esp

	/* Jumps are relative, and we're running __PAGE_OFFSET too low at the
	 * moment. */
	jmp lguest_init+__PAGE_OFFSET

[ arch/x86/lguest/boot.c ]
/* Once we get to lguest_init(), we know we're a Guest.  The pv_ops
 * structures in the kernel provide points for (almost) every routine we have
 * to override to avoid privileged instructions. */
__init void lguest_init(void)
{
	/* We're under lguest, paravirt is enabled, and we're running at
	 * privilege level 1, not 0 as normal. */
	pv_info.name = "lguest";
	pv_info.paravirt_enabled = 1;
	pv_info.kernel_rpl = 1;

	/* We set up all the lguest overrides for sensitive operations.  These
	 * are detailed with the operations themselves. */

	/* interrupt-related operations */
	pv_irq_ops.init_IRQ = lguest_init_IRQ;
	pv_irq_ops.save_fl = save_fl;
	pv_irq_ops.restore_fl = restore_fl;
	pv_irq_ops.irq_disable = irq_disable;
	pv_irq_ops.irq_enable = irq_enable;
	pv_irq_ops.safe_halt = lguest_safe_halt;

	/* init-time operations */
	pv_init_ops.memory_setup = lguest_memory_setup;
	pv_init_ops.patch = lguest_patch;

	/* Intercepts of various cpu instructions */
	pv_cpu_ops.load_gdt = lguest_load_gdt;
	pv_cpu_ops.cpuid = lguest_cpuid;
	pv_cpu_ops.load_idt = lguest_load_idt;
	pv_cpu_ops.iret = lguest_iret;
	pv_cpu_ops.load_esp0 = lguest_load_esp0;
	pv_cpu_ops.load_tr_desc = lguest_load_tr_desc;
	pv_cpu_ops.set_ldt = lguest_set_ldt;
	pv_cpu_ops.load_tls = lguest_load_tls;
	pv_cpu_ops.set_debugreg = lguest_set_debugreg;
	pv_cpu_ops.clts = lguest_clts;
	pv_cpu_ops.read_cr0 = lguest_read_cr0;
	pv_cpu_ops.write_cr0 = lguest_write_cr0;
	pv_cpu_ops.read_cr4 = lguest_read_cr4;
	pv_cpu_ops.write_cr4 = lguest_write_cr4;
	pv_cpu_ops.write_gdt_entry = lguest_write_gdt_entry;
	pv_cpu_ops.write_idt_entry = lguest_write_idt_entry;
	pv_cpu_ops.wbinvd = lguest_wbinvd;
	pv_cpu_ops.lazy_mode.enter = paravirt_enter_lazy_cpu;
	pv_cpu_ops.lazy_mode.leave = lguest_leave_lazy_mode;

	/* pagetable management */
	pv_mmu_ops.write_cr3 = lguest_write_cr3;
	pv_mmu_ops.flush_tlb_user = lguest_flush_tlb_user;
	pv_mmu_ops.flush_tlb_single = lguest_flush_tlb_single;
	pv_mmu_ops.flush_tlb_kernel = lguest_flush_tlb_kernel;
	pv_mmu_ops.set_pte = lguest_set_pte;
	pv_mmu_ops.set_pte_at = lguest_set_pte_at;
	pv_mmu_ops.set_pmd = lguest_set_pmd;
	pv_mmu_ops.read_cr2 = lguest_read_cr2;
	pv_mmu_ops.read_cr3 = lguest_read_cr3;
	pv_mmu_ops.lazy_mode.enter = paravirt_enter_lazy_mmu;
	pv_mmu_ops.lazy_mode.leave = lguest_leave_lazy_mode;

#ifdef CONFIG_X86_LOCAL_APIC
	/* apic read/write intercepts */
	pv_apic_ops.apic_write = lguest_apic_write;
	pv_apic_ops.apic_write_atomic = lguest_apic_write;
	pv_apic_ops.apic_read = lguest_apic_read;
#endif

	/* time operations */
	pv_time_ops.get_wallclock = lguest_get_wallclock;
	pv_time_ops.time_init = lguest_time_init;

	/* Now is a good time to look at the implementations of these functions
	 * before returning to the rest of lguest_init(). */

[ include/asm-x86/lguest_hcall.h ]
/* First, how does our Guest contact the Host to ask for privileged
 * operations?  There are two ways: the direct way is to make a "hypercall",
 * to make requests of the Host Itself.
 *
 * Our hypercall mechanism uses the highest unused trap code (traps 32 and
 * above are used by real hardware interrupts).  Fifteen hypercalls are
 * available: the hypercall number is put in the %eax register, and the
 * arguments (when required) are placed in %edx, %ebx and %ecx.  If a return
 * value makes sense, it's returned in %eax.
 *
 * Grossly invalid calls result in Sudden Death at the hands of the vengeful
 * Host, rather than returning failure.  This reflects Winston Churchill's
 * definition of a gentleman: "someone who is only rude intentionally". */
static inline unsigned long
hcall(unsigned long call,
      unsigned long arg1, unsigned long arg2, unsigned long arg3)
{
	/* "int" is the Intel instruction to trigger a trap. */
	asm volatile("int $" __stringify(LGUEST_TRAP_ENTRY)
		       /* The call in %eax (aka "a") might be overwritten */
		     : "=a"(call)
		       /* The arguments are in %eax, %edx, %ebx & %ecx */
		     : "a"(call), "d"(arg1), "b"(arg2), "c"(arg3)
		       /* "memory" means this might write somewhere in memory.
			* This isn't true for all calls, but it's safe to tell
			* gcc that it might happen so it doesn't get clever. */
		     : "memory");
	return call;
}


[ include/linux/lguest.h ]
/* The second method of communicating with the Host is to via "struct
 * lguest_data".  Once the Guest's initialization hypercall tells the Host where
 * this is, the Guest and Host both publish information in it. */

[ arch/x86/lguest/boot.c ]
/*
 * After that diversion we return to our first native-instruction
 * replacements: four functions for interrupt control.
 *
 * The simplest way of implementing these would be to have "turn interrupts
 * off" and "turn interrupts on" hypercalls.  Unfortunately, this is too slow:
 * these are by far the most commonly called functions of those we override.
 *
 * So instead we keep an "irq_enabled" field inside our "struct lguest_data",
 * which the Guest can update with a single instruction.  The Host knows to
 * check there when it wants to deliver an interrupt.
 */

/* save_flags() is expected to return the processor state (ie. "eflags").  The
 * eflags word contains all kind of stuff, but in practice Linux only cares
 * about the interrupt flag.  Our "save_flags()" just returns that. */
static unsigned long save_fl(void)
{
	return lguest_data.irq_enabled;
}

/* restore_flags() just sets the flags back to the value given. */
static void restore_fl(unsigned long flags)
{
	lguest_data.irq_enabled = flags;
}

/* Interrupts go off... */
static void irq_disable(void)
{
	lguest_data.irq_enabled = 0;
}

/* Interrupts go on... */
static void irq_enable(void)
{
	lguest_data.irq_enabled = X86_EFLAGS_IF;
}


/*
 * The Interrupt Descriptor Table (IDT).
 *
 * The IDT tells the processor what to do when an interrupt comes in.  Each
 * entry in the table is a 64-bit descriptor: this holds the privilege level,
 * address of the handler, and... well, who cares?  The Guest just asks the
 * Host to make the change anyway, because the Host controls the real IDT.
 */
static void lguest_write_idt_entry(struct desc_struct *dt,
				   int entrynum, u32 low, u32 high)
{
	/* Keep the local copy up to date. */
	write_dt_entry(dt, entrynum, low, high);
	/* Tell Host about this new entry. */
	hcall(LHCALL_LOAD_IDT_ENTRY, entrynum, low, high);
}

/* Changing to a different IDT is very rare: we keep the IDT up-to-date every
 * time it is written, so we can simply loop through all entries and tell the
 * Host about them. */
static void lguest_load_idt(const struct Xgt_desc_struct *desc)
{
	unsigned int i;
	struct desc_struct *idt = (void *)desc->address;

	for (i = 0; i < (desc->size+1)/8; i++)
		hcall(LHCALL_LOAD_IDT_ENTRY, i, idt[i].a, idt[i].b);
}

/*
 * The Global Descriptor Table.
 *
 * The Intel architecture defines another table, called the Global Descriptor
 * Table (GDT).  You tell the CPU where it is (and its size) using the "lgdt"
 * instruction, and then several other instructions refer to entries in the
 * table.  There are three entries which the Switcher needs, so the Host simply
 * controls the entire thing and the Guest asks it to make changes using the
 * LOAD_GDT hypercall.
 *
 * This is the opposite of the IDT code where we have a LOAD_IDT_ENTRY
 * hypercall and use that repeatedly to load a new IDT.  I don't think it
 * really matters, but wouldn't it be nice if they were the same?
 */
static void lguest_load_gdt(const struct Xgt_desc_struct *desc)
{
	BUG_ON((desc->size+1)/8 != GDT_ENTRIES);
	hcall(LHCALL_LOAD_GDT, __pa(desc->address), GDT_ENTRIES, 0);
}

/* For a single GDT entry which changes, we do the lazy thing: alter our GDT,
 * then tell the Host to reload the entire thing.  This operation is so rare
 * that this naive implementation is reasonable. */
static void lguest_write_gdt_entry(struct desc_struct *dt,
				   int entrynum, u32 low, u32 high)
{
	write_dt_entry(dt, entrynum, low, high);
	hcall(LHCALL_LOAD_GDT, __pa(dt), GDT_ENTRIES, 0);
}

/* OK, I lied.  There are three "thread local storage" GDT entries which change
 * on every context switch (these three entries are how glibc implements
 * __thread variables).  So we have a hypercall specifically for this case. */
static void lguest_load_tls(struct thread_struct *t, unsigned int cpu)
{
	/* There's one problem which normal hardware doesn't have: the Host
	 * can't handle us removing entries we're currently using.  So we clear
	 * the GS register here: if it's needed it'll be reloaded anyway. */
	loadsegment(gs, 0);
	lazy_hcall(LHCALL_LOAD_TLS, __pa(&t->tls_array), cpu, 0);
}

/* Notice the lazy_hcall() above, rather than hcall().  This is our first
 * real optimization trick!
 *
 * When lazy_mode is set, it means we're allowed to defer all hypercalls and do
 * them as a batch when lazy_mode is eventually turned off.  Because hypercalls
 * are reasonably expensive, batching them up makes sense.  For example, a
 * large munmap might update dozens of page table entries: that code calls
 * paravirt_enter_lazy_mmu(), does the dozen updates, then calls
 * lguest_leave_lazy_mode().
 *
 * So, when we're in lazy mode, we call async_hcall() to store the call for
 * future processing. */
static void lazy_hcall(unsigned long call,
		       unsigned long arg1,
		       unsigned long arg2,
		       unsigned long arg3)
{
	if (paravirt_get_lazy_mode() == PARAVIRT_LAZY_NONE)
		hcall(call, arg1, arg2, arg3);
	else
		async_hcall(call, arg1, arg2, arg3);
}

/* When lazy mode is turned off reset the per-cpu lazy mode variable and then
 * issue a hypercall to flush any stored calls. */
static void lguest_leave_lazy_mode(void)
{
	paravirt_leave_lazy(paravirt_get_lazy_mode());
	hcall(LHCALL_FLUSH_ASYNC, 0, 0, 0);
}

/* async_hcall() is pretty simple: I'm quite proud of it really.  We have a
 * ring buffer of stored hypercalls which the Host will run though next time we
 * do a normal hypercall.  Each entry in the ring has 4 slots for the hypercall
 * arguments, and a "hcall_status" word which is 0 if the call is ready to go,
 * and 255 once the Host has finished with it.
 *
 * If we come around to a slot which hasn't been finished, then the table is
 * full and we just make the hypercall directly.  This has the nice side
 * effect of causing the Host to run all the stored calls in the ring buffer
 * which empties it for next time! */
static void async_hcall(unsigned long call, unsigned long arg1,
			unsigned long arg2, unsigned long arg3)
{
	/* Note: This code assumes we're uniprocessor. */
	static unsigned int next_call;
	unsigned long flags;

	/* Disable interrupts if not already disabled: we don't want an
	 * interrupt handler making a hypercall while we're already doing
	 * one! */
	local_irq_save(flags);
	if (lguest_data.hcall_status[next_call] != 0xFF) {
		/* Table full, so do normal hcall which will flush table. */
		hcall(call, arg1, arg2, arg3);
	} else {
		lguest_data.hcalls[next_call].arg0 = call;
		lguest_data.hcalls[next_call].arg1 = arg1;
		lguest_data.hcalls[next_call].arg2 = arg2;
		lguest_data.hcalls[next_call].arg3 = arg3;
		/* Arguments must all be written before we mark it to go */
		wmb();
		lguest_data.hcall_status[next_call] = 0;
		if (++next_call == LHCALL_RING_SIZE)
			next_call = 0;
	}
	local_irq_restore(flags);
}

/* That's enough excitement for now, back to ploughing through each of
 * the different pv_ops structures (we're about 1/3 of the way through).
 *
 * This is the Local Descriptor Table, another weird Intel thingy.  Linux only
 * uses this for some strange applications like Wine.  We don't do anything
 * here, so they'll get an informative and friendly Segmentation Fault. */
static void lguest_set_ldt(const void *addr, unsigned entries)
{
}

/* This loads a GDT entry into the "Task Register": that entry points to a
 * structure called the Task State Segment.  Some comments scattered though the
 * kernel code indicate that this used for task switching in ages past, along
 * with blood sacrifice and astrology.
 *
 * Now there's nothing interesting in here that we don't get told elsewhere.
 * But the native version uses the "ltr" instruction, which makes the Host
 * complain to the Guest about a Segmentation Fault and it'll oops.  So we
 * override the native version with a do-nothing version. */
static void lguest_load_tr_desc(void)
{
}

/* The "cpuid" instruction is a way of querying both the CPU identity
 * (manufacturer, model, etc) and its features.  It was introduced before the
 * Pentium in 1993 and keeps getting extended by both Intel and AMD.  As you
 * might imagine, after a decade and a half this treatment, it is now a giant
 * ball of hair.  Its entry in the current Intel manual runs to 28 pages.
 *
 * This instruction even it has its own Wikipedia entry.  The Wikipedia entry
 * has been translated into 4 languages.  I am not making this up!
 *
 * We could get funky here and identify ourselves as "GenuineLguest", but
 * instead we just use the real "cpuid" instruction.  Then I pretty much turned
 * off feature bits until the Guest booted.  (Don't say that: you'll damage
 * lguest sales!)  Shut up, inner voice!  (Hey, just pointing out that this is
 * hardly future proof.)  Noone's listening!  They don't like you anyway,
 * parenthetic weirdo!
 *
 * Replacing the cpuid so we can turn features off is great for the kernel, but
 * anyone (including userspace) can just use the raw "cpuid" instruction and
 * the Host won't even notice since it isn't privileged.  So we try not to get
 * too worked up about it. */
static void lguest_cpuid(unsigned int *eax, unsigned int *ebx,
			 unsigned int *ecx, unsigned int *edx)
{
	int function = *eax;

	native_cpuid(eax, ebx, ecx, edx);
	switch (function) {
	case 1:	/* Basic feature request. */
		/* We only allow kernel to see SSE3, CMPXCHG16B and SSSE3 */
		*ecx &= 0x00002201;
		/* SSE, SSE2, FXSR, MMX, CMOV, CMPXCHG8B, FPU. */
		*edx &= 0x07808101;
		/* The Host can do a nice optimization if it knows that the
		 * kernel mappings (addresses above 0xC0000000 or whatever
		 * PAGE_OFFSET is set to) haven't changed.  But Linux calls
		 * flush_tlb_user() for both user and kernel mappings unless
		 * the Page Global Enable (PGE) feature bit is set. */
		*edx |= 0x00002000;
		break;
	case 0x80000000:
		/* Futureproof this a little: if they ask how much extended
		 * processor information there is, limit it to known fields. */
		if (*eax > 0x80000008)
			*eax = 0x80000008;
		break;
	}
}

/* Intel has four control registers, imaginatively named cr0, cr2, cr3 and cr4.
 * I assume there's a cr1, but it hasn't bothered us yet, so we'll not bother
 * it.  The Host needs to know when the Guest wants to change them, so we have
 * a whole series of functions like read_cr0() and write_cr0().
 *
 * We start with cr0.  cr0 allows you to turn on and off all kinds of basic
 * features, but Linux only really cares about one: the horrifically-named Task
 * Switched (TS) bit at bit 3 (ie. 8)
 *
 * What does the TS bit do?  Well, it causes the CPU to trap (interrupt 7) if
 * the floating point unit is used.  Which allows us to restore FPU state
 * lazily after a task switch, and Linux uses that gratefully, but wouldn't a
 * name like "FPUTRAP bit" be a little less cryptic?
 *
 * We store cr0 (and cr3) locally, because the Host never changes it.  The
 * Guest sometimes wants to read it and we'd prefer not to bother the Host
 * unnecessarily. */
static unsigned long current_cr0, current_cr3;
static void lguest_write_cr0(unsigned long val)
{
	lazy_hcall(LHCALL_TS, val & X86_CR0_TS, 0, 0);
	current_cr0 = val;
}

static unsigned long lguest_read_cr0(void)
{
	return current_cr0;
}

/* Intel provided a special instruction to clear the TS bit for people too cool
 * to use write_cr0() to do it.  This "clts" instruction is faster, because all
 * the vowels have been optimized out. */
static void lguest_clts(void)
{
	lazy_hcall(LHCALL_TS, 0, 0, 0);
	current_cr0 &= ~X86_CR0_TS;
}

/* cr2 is the virtual address of the last page fault, which the Guest only ever
 * reads.  The Host kindly writes this into our "struct lguest_data", so we
 * just read it out of there. */
static unsigned long lguest_read_cr2(void)
{
	return lguest_data.cr2;
}

/* cr3 is the current toplevel pagetable page: the principle is the same as
 * cr0.  Keep a local copy, and tell the Host when it changes. */
static void lguest_write_cr3(unsigned long cr3)
{
	lazy_hcall(LHCALL_NEW_PGTABLE, cr3, 0, 0);
	current_cr3 = cr3;
}

static unsigned long lguest_read_cr3(void)
{
	return current_cr3;
}

/* cr4 is used to enable and disable PGE, but we don't care. */
static unsigned long lguest_read_cr4(void)
{
	return 0;
}

static void lguest_write_cr4(unsigned long val)
{
}

/*
 * Page Table Handling.
 *
 * Now would be a good time to take a rest and grab a coffee or similarly
 * relaxing stimulant.  The easy parts are behind us, and the trek gradually
 * winds uphill from here.
 *
 * Quick refresher: memory is divided into "pages" of 4096 bytes each.  The CPU
 * maps virtual addresses to physical addresses using "page tables".  We could
 * use one huge index of 1 million entries: each address is 4 bytes, so that's
 * 1024 pages just to hold the page tables.   But since most virtual addresses
 * are unused, we use a two level index which saves space.  The cr3 register
 * contains the physical address of the top level "page directory" page, which
 * contains physical addresses of up to 1024 second-level pages.  Each of these
 * second level pages contains up to 1024 physical addresses of actual pages,
 * or Page Table Entries (PTEs).
 *
 * Here's a diagram, where arrows indicate physical addresses:
 *
 * cr3 ---> +---------+
 *	    |  	   --------->+---------+
 *	    |	      |	     | PADDR1  |
 *	  Top-level   |	     | PADDR2  |
 *	  (PMD) page  |	     | 	       |
 *	    |	      |	   Lower-level |
 *	    |	      |	   (PTE) page  |
 *	    |	      |	     |	       |
 *	      ....    	     	 ....
 *
 * So to convert a virtual address to a physical address, we look up the top
 * level, which points us to the second level, which gives us the physical
 * address of that page.  If the top level entry was not present, or the second
 * level entry was not present, then the virtual address is invalid (we
 * say "the page was not mapped").
 *
 * Put another way, a 32-bit virtual address is divided up like so:
 *
 *  1 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 * |<---- 10 bits ---->|<---- 10 bits ---->|<------ 12 bits ------>|
 *    Index into top     Index into second      Offset within page
 *  page directory page    pagetable page
 *
 * The kernel spends a lot of time changing both the top-level page directory
 * and lower-level pagetable pages.  The Guest doesn't know physical addresses,
 * so while it maintains these page tables exactly like normal, it also needs
 * to keep the Host informed whenever it makes a change: the Host will create
 * the real page tables based on the Guests'.
 */

/* The Guest calls this to set a second-level entry (pte), ie. to map a page
 * into a process' address space.  We set the entry then tell the Host the
 * toplevel and address this corresponds to.  The Guest uses one pagetable per
 * process, so we need to tell the Host which one we're changing (mm->pgd). */
static void lguest_set_pte_at(struct mm_struct *mm, unsigned long addr,
			      pte_t *ptep, pte_t pteval)
{
	*ptep = pteval;
	lazy_hcall(LHCALL_SET_PTE, __pa(mm->pgd), addr, pteval.pte_low);
}

/* The Guest calls this to set a top-level entry.  Again, we set the entry then
 * tell the Host which top-level page we changed, and the index of the entry we
 * changed. */
static void lguest_set_pmd(pmd_t *pmdp, pmd_t pmdval)
{
	*pmdp = pmdval;
	lazy_hcall(LHCALL_SET_PMD, __pa(pmdp)&PAGE_MASK,
		   (__pa(pmdp)&(PAGE_SIZE-1))/4, 0);
}

/* There are a couple of legacy places where the kernel sets a PTE, but we
 * don't know the top level any more.  This is useless for us, since we don't
 * know which pagetable is changing or what address, so we just tell the Host
 * to forget all of them.  Fortunately, this is very rare.
 *
 * ... except in early boot when the kernel sets up the initial pagetables,
 * which makes booting astonishingly slow.  So we don't even tell the Host
 * anything changed until we've done the first page table switch. */
static void lguest_set_pte(pte_t *ptep, pte_t pteval)
{
	*ptep = pteval;
	/* Don't bother with hypercall before initial setup. */
	if (current_cr3)
		lazy_hcall(LHCALL_FLUSH_TLB, 1, 0, 0);
}

/* Unfortunately for Lguest, the pv_mmu_ops for page tables were based on
 * native page table operations.  On native hardware you can set a new page
 * table entry whenever you want, but if you want to remove one you have to do
 * a TLB flush (a TLB is a little cache of page table entries kept by the CPU).
 *
 * So the lguest_set_pte_at() and lguest_set_pmd() functions above are only
 * called when a valid entry is written, not when it's removed (ie. marked not
 * present).  Instead, this is where we come when the Guest wants to remove a
 * page table entry: we tell the Host to set that entry to 0 (ie. the present
 * bit is zero). */
static void lguest_flush_tlb_single(unsigned long addr)
{
	/* Simply set it to zero: if it was not, it will fault back in. */
	lazy_hcall(LHCALL_SET_PTE, current_cr3, addr, 0);
}

/* This is what happens after the Guest has removed a large number of entries.
 * This tells the Host that any of the page table entries for userspace might
 * have changed, ie. virtual addresses below PAGE_OFFSET. */
static void lguest_flush_tlb_user(void)
{
	lazy_hcall(LHCALL_FLUSH_TLB, 0, 0, 0);
}

/* This is called when the kernel page tables have changed.  That's not very
 * common (unless the Guest is using highmem, which makes the Guest extremely
 * slow), so it's worth separating this from the user flushing above. */
static void lguest_flush_tlb_kernel(void)
{
	lazy_hcall(LHCALL_FLUSH_TLB, 1, 0, 0);
}

/*
 * The Unadvanced Programmable Interrupt Controller.
 *
 * This is an attempt to implement the simplest possible interrupt controller.
 * I spent some time looking though routines like set_irq_chip_and_handler,
 * set_irq_chip_and_handler_name, set_irq_chip_data and set_phasers_to_stun and
 * I *think* this is as simple as it gets.
 *
 * We can tell the Host what interrupts we want blocked ready for using the
 * lguest_data.interrupts bitmap, so disabling (aka "masking") them is as
 * simple as setting a bit.  We don't actually "ack" interrupts as such, we
 * just mask and unmask them.  I wonder if we should be cleverer?
 */
static void disable_lguest_irq(unsigned int irq)
{
	set_bit(irq, lguest_data.blocked_interrupts);
}

static void enable_lguest_irq(unsigned int irq)
{
	clear_bit(irq, lguest_data.blocked_interrupts);
}

/* This structure describes the lguest IRQ controller. */
static struct irq_chip lguest_irq_controller = {
	.name		= "lguest",
	.mask		= disable_lguest_irq,
	.mask_ack	= disable_lguest_irq,
	.unmask		= enable_lguest_irq,
};

/* This sets up the Interrupt Descriptor Table (IDT) entry for each hardware
 * interrupt (except 128, which is used for system calls), and then tells the
 * Linux infrastructure that each interrupt is controlled by our level-based
 * lguest interrupt controller. */
static void __init lguest_init_IRQ(void)
{
	unsigned int i;

	for (i = 0; i < LGUEST_IRQS; i++) {
		int vector = FIRST_EXTERNAL_VECTOR + i;
		if (vector != SYSCALL_VECTOR) {
			set_intr_gate(vector, interrupt[i]);
			set_irq_chip_and_handler(i, &lguest_irq_controller,
						 handle_level_irq);
		}
	}
	/* This call is required to set up for 4k stacks, where we have
	 * separate stacks for hard and soft interrupts. */
	irq_ctx_init(smp_processor_id());
}

/*
 * Time.
 *
 * It would be far better for everyone if the Guest had its own clock, but
 * until then the Host gives us the time on every interrupt.
 */
static unsigned long lguest_get_wallclock(void)
{
	return lguest_data.time.tv_sec;
}

static cycle_t lguest_clock_read(void)
{
	unsigned long sec, nsec;

	/* If the Host tells the TSC speed, we can trust that. */
	if (lguest_data.tsc_khz)
		return native_read_tsc();

	/* If we can't use the TSC, we read the time value written by the Host.
	 * Since it's in two parts (seconds and nanoseconds), we risk reading
	 * it just as it's changing from 99 & 0.999999999 to 100 and 0, and
	 * getting 99 and 0.  As Linux tends to come apart under the stress of
	 * time travel, we must be careful: */
	do {
		/* First we read the seconds part. */
		sec = lguest_data.time.tv_sec;
		/* This read memory barrier tells the compiler and the CPU that
		 * this can't be reordered: we have to complete the above
		 * before going on. */
		rmb();
		/* Now we read the nanoseconds part. */
		nsec = lguest_data.time.tv_nsec;
		/* Make sure we've done that. */
		rmb();
		/* Now if the seconds part has changed, try again. */
	} while (unlikely(lguest_data.time.tv_sec != sec));

	/* Our non-TSC clock is in real nanoseconds. */
	return sec*1000000000ULL + nsec;
}

/* This is what we tell the kernel is our clocksource.  */
static struct clocksource lguest_clock = {
	.name		= "lguest",
	.rating		= 400,
	.read		= lguest_clock_read,
	.mask		= CLOCKSOURCE_MASK(64),
	.mult		= 1 << 22,
	.shift		= 22,
	.flags		= CLOCK_SOURCE_IS_CONTINUOUS,
};

/* The "scheduler clock" is just our real clock, adjusted to start at zero */
static unsigned long long lguest_sched_clock(void)
{
	return cyc2ns(&lguest_clock, lguest_clock_read() - clock_base);
}

/* We also need a "struct clock_event_device": Linux asks us to set it to go
 * off some time in the future.  Actually, James Morris figured all this out, I
 * just applied the patch. */
static int lguest_clockevent_set_next_event(unsigned long delta,
                                           struct clock_event_device *evt)
{
	if (delta < LG_CLOCK_MIN_DELTA) {
		if (printk_ratelimit())
			printk(KERN_DEBUG "%s: small delta %lu ns\n",
			       __FUNCTION__, delta);
		return -ETIME;
	}
	hcall(LHCALL_SET_CLOCKEVENT, delta, 0, 0);
	return 0;
}

static void lguest_clockevent_set_mode(enum clock_event_mode mode,
                                      struct clock_event_device *evt)
{
	switch (mode) {
	case CLOCK_EVT_MODE_UNUSED:
	case CLOCK_EVT_MODE_SHUTDOWN:
		/* A 0 argument shuts the clock down. */
		hcall(LHCALL_SET_CLOCKEVENT, 0, 0, 0);
		break;
	case CLOCK_EVT_MODE_ONESHOT:
		/* This is what we expect. */
		break;
	case CLOCK_EVT_MODE_PERIODIC:
		BUG();
	case CLOCK_EVT_MODE_RESUME:
		break;
	}
}

/* This describes our primitive timer chip. */
static struct clock_event_device lguest_clockevent = {
	.name                   = "lguest",
	.features               = CLOCK_EVT_FEAT_ONESHOT,
	.set_next_event         = lguest_clockevent_set_next_event,
	.set_mode               = lguest_clockevent_set_mode,
	.rating                 = INT_MAX,
	.mult                   = 1,
	.shift                  = 0,
	.min_delta_ns           = LG_CLOCK_MIN_DELTA,
	.max_delta_ns           = LG_CLOCK_MAX_DELTA,
};

/* This is the Guest timer interrupt handler (hardware interrupt 0).  We just
 * call the clockevent infrastructure and it does whatever needs doing. */
static void lguest_time_irq(unsigned int irq, struct irq_desc *desc)
{
	unsigned long flags;

	/* Don't interrupt us while this is running. */
	local_irq_save(flags);
	lguest_clockevent.event_handler(&lguest_clockevent);
	local_irq_restore(flags);
}

/* At some point in the boot process, we get asked to set up our timing
 * infrastructure.  The kernel doesn't expect timer interrupts before this, but
 * we cleverly initialized the "blocked_interrupts" field of "struct
 * lguest_data" so that timer interrupts were blocked until now. */
static void lguest_time_init(void)
{
	/* Set up the timer interrupt (0) to go to our simple timer routine */
	set_irq_handler(0, lguest_time_irq);

	/* Our clock structure looks like arch/x86/kernel/tsc_32.c if we can
	 * use the TSC, otherwise it's a dumb nanosecond-resolution clock.
	 * Either way, the "rating" is set so high that it's always chosen over
	 * any other clocksource. */
	if (lguest_data.tsc_khz)
		lguest_clock.mult = clocksource_khz2mult(lguest_data.tsc_khz,
							 lguest_clock.shift);
	clock_base = lguest_clock_read();
	clocksource_register(&lguest_clock);

	/* Now we've set up our clock, we can use it as the scheduler clock */
	pv_time_ops.sched_clock = lguest_sched_clock;

	/* We can't set cpumask in the initializer: damn C limitations!  Set it
	 * here and register our timer device. */
	lguest_clockevent.cpumask = cpumask_of_cpu(0);
	clockevents_register_device(&lguest_clockevent);

	/* Finally, we unblock the timer interrupt. */
	enable_lguest_irq(0);
}

/*
 * Miscellaneous bits and pieces.
 *
 * Here is an oddball collection of functions which the Guest needs for things
 * to work.  They're pretty simple.
 */

/* The Guest needs to tell the Host what stack it expects traps to use.  For
 * native hardware, this is part of the Task State Segment mentioned above in
 * lguest_load_tr_desc(), but to help hypervisors there's this special call.
 *
 * We tell the Host the segment we want to use (__KERNEL_DS is the kernel data
 * segment), the privilege level (we're privilege level 1, the Host is 0 and
 * will not tolerate us trying to use that), the stack pointer, and the number
 * of pages in the stack. */
static void lguest_load_esp0(struct tss_struct *tss,
				     struct thread_struct *thread)
{
	lazy_hcall(LHCALL_SET_STACK, __KERNEL_DS|0x1, thread->esp0,
		   THREAD_SIZE/PAGE_SIZE);
}

/* Let's just say, I wouldn't do debugging under a Guest. */
static void lguest_set_debugreg(int regno, unsigned long value)
{
	/* FIXME: Implement */
}

/* There are times when the kernel wants to make sure that no memory writes are
 * caught in the cache (that they've all reached real hardware devices).  This
 * doesn't matter for the Guest which has virtual hardware.
 *
 * On the Pentium 4 and above, cpuid() indicates that the Cache Line Flush
 * (clflush) instruction is available and the kernel uses that.  Otherwise, it
 * uses the older "Write Back and Invalidate Cache" (wbinvd) instruction.
 * Unlike clflush, wbinvd can only be run at privilege level 0.  So we can
 * ignore clflush, but replace wbinvd.
 */
static void lguest_wbinvd(void)
{
}

/* If the Guest expects to have an Advanced Programmable Interrupt Controller,
 * we play dumb by ignoring writes and returning 0 for reads.  So it's no
 * longer Programmable nor Controlling anything, and I don't think 8 lines of
 * code qualifies for Advanced.  It will also never interrupt anything.  It
 * does, however, allow us to get through the Linux boot code. */
#ifdef CONFIG_X86_LOCAL_APIC
static void lguest_apic_write(unsigned long reg, unsigned long v)
{
}

static unsigned long lguest_apic_read(unsigned long reg)
{
	return 0;
}
#endif

/* STOP!  Until an interrupt comes in. */
static void lguest_safe_halt(void)
{
	hcall(LHCALL_HALT, 0, 0, 0);
}

/* Perhaps CRASH isn't the best name for this hypercall, but we use it to get a
 * message out when we're crashing as well as elegant termination like powering
 * off.
 *
 * Note that the Host always prefers that the Guest speak in physical addresses
 * rather than virtual addresses, so we use __pa() here. */
static void lguest_power_off(void)
{
	hcall(LHCALL_CRASH, __pa("Power down"), 0, 0);
}

/*
 * Panicing.
 *
 * Don't.  But if you did, this is what happens.
 */
static int lguest_panic(struct notifier_block *nb, unsigned long l, void *p)
{
	hcall(LHCALL_CRASH, __pa(p), 0, 0);
	/* The hcall won't return, but to keep gcc happy, we're "done". */
	return NOTIFY_DONE;
}

static struct notifier_block paniced = {
	.notifier_call = lguest_panic
};

/* Setting up memory is fairly easy. */
static __init char *lguest_memory_setup(void)
{
	/* We do this here and not earlier because lockcheck barfs if we do it
	 * before start_kernel() */
	atomic_notifier_chain_register(&panic_notifier_list, &paniced);

	/* The Linux bootloader header contains an "e820" memory map: the
	 * Launcher populated the first entry with our memory limit. */
	add_memory_region(boot_params.e820_map[0].addr,
			  boot_params.e820_map[0].size,
			  boot_params.e820_map[0].type);

	/* This string is for the boot messages. */
	return "LGUEST";
}

/* We will eventually use the virtio console device to produce console output,
 * but before that is set up we use LHCALL_NOTIFY on normal memory to produce
 * console output. */
static __init int early_put_chars(u32 vtermno, const char *buf, int count)
{
	char scratch[17];
	unsigned int len = count;

	/* We use a nul-terminated string, so we have to make a copy.  Icky,
	 * huh? */
	if (len > sizeof(scratch) - 1)
		len = sizeof(scratch) - 1;
	scratch[len] = '\0';
	memcpy(scratch, buf, len);
	hcall(LHCALL_NOTIFY, __pa(scratch), 0, 0);

	/* This routine returns the number of bytes actually written. */
	return len;
}

[ arch/x86/lguest/i386_head.S ]
/* There is one final paravirt_op that the Guest implements, and glancing
 * at it you can see why I left it to last.  It's *cool*!  It's in *assembler*!
 *
 * The "iret" instruction is used to return from an interrupt or trap.  The
 * stack looks like this:
 *   old address
 *   old code segment & privilege level
 *   old processor flags ("eflags")
 *
 * The "iret" instruction pops those values off the stack and restores them all
 * at once.  The only problem is that eflags includes the Interrupt Flag which
 * the Guest can't change: the CPU will simply ignore it when we do an "iret".
 * So we have to copy eflags from the stack to lguest_data.irq_enabled before
 * we do the "iret".
 *
 * There are two problems with this: firstly, we need to use a register to do
 * the copy and secondly, the whole thing needs to be atomic.  The first
 * problem is easy to solve: push %eax on the stack so we can use it, and then
 * restore it at the end just before the real "iret".
 *
 * The second is harder: copying eflags to lguest_data.irq_enabled will turn
 * interrupts on before we're finished, so we could be interrupted before we
 * return to userspace or wherever.  Our solution to this is to surround the
 * code with lguest_noirq_start: and lguest_noirq_end: labels.  We tell the
 * Host that it is *never* to interrupt us there, even if interrupts seem to be
 * enabled. */
ENTRY(lguest_iret)
	pushl	%eax
	movl	12(%esp), %eax
lguest_noirq_start:
	/* Note the %ss: segment prefix here.  Normal data accesses use the
	 * "ds" segment, but that will have already been restored for whatever
	 * we're returning to (such as userspace): we can't trust it.  The %ss:
	 * prefix makes sure we use the stack segment, which is still valid. */
	movl	%eax,%ss:lguest_data+LGUEST_DATA_irq_enabled
	popl	%eax
	iret
lguest_noirq_end:

[ arch/x86/lguest/boot.c ]
/*
 * Patching (Powerfully Placating Performance Pedants)
 *
 * We have already seen that pv_ops structures let us replace simple
 * native instructions with calls to the appropriate back end all throughout
 * the kernel.  This allows the same kernel to run as a Guest and as a native
 * kernel, but it's slow because of all the indirect branches.
 *
 * Remember that David Wheeler quote about "Any problem in computer science can
 * be solved with another layer of indirection"?  The rest of that quote is
 * "... But that usually will create another problem."  This is the first of
 * those problems.
 *
 * Our current solution is to allow the paravirt back end to optionally patch
 * over the indirect calls to replace them with something more efficient.  We
 * patch the four most commonly called functions: disable interrupts, enable
 * interrupts, restore interrupts and save interrupts.  We usually have 6 or 10
 * bytes to patch into: the Guest versions of these operations are small enough
 * that we can fit comfortably.
 *
 * First we need assembly templates of each of the patchable Guest operations,
 * and these are in lguest_asm.S. */

[ arch/x86/lguest/i386_head.S ]
/* We create a macro which puts the assembler code between lgstart_ and
 * lgend_ markers.  These templates are put in the .text section: they can't be
 * discarded after boot as we may need to patch modules, too. */
.text
#define LGUEST_PATCH(name, insns...)			\
	lgstart_##name:	insns; lgend_##name:;		\
	.globl lgstart_##name; .globl lgend_##name

LGUEST_PATCH(cli, movl $0, lguest_data+LGUEST_DATA_irq_enabled)
LGUEST_PATCH(sti, movl $X86_EFLAGS_IF, lguest_data+LGUEST_DATA_irq_enabled)
LGUEST_PATCH(popf, movl %eax, lguest_data+LGUEST_DATA_irq_enabled)
LGUEST_PATCH(pushf, movl lguest_data+LGUEST_DATA_irq_enabled, %eax)


[ arch/x86/lguest/boot.c ]
/* We construct a table from the assembler templates: */
static const struct lguest_insns
{
	const char *start, *end;
} lguest_insns[] = {
	[PARAVIRT_PATCH(pv_irq_ops.irq_disable)] = { lgstart_cli, lgend_cli },
	[PARAVIRT_PATCH(pv_irq_ops.irq_enable)] = { lgstart_sti, lgend_sti },
	[PARAVIRT_PATCH(pv_irq_ops.restore_fl)] = { lgstart_popf, lgend_popf },
	[PARAVIRT_PATCH(pv_irq_ops.save_fl)] = { lgstart_pushf, lgend_pushf },
};

/* Now our patch routine is fairly simple (based on the native one in
 * paravirt.c).  If we have a replacement, we copy it in and return how much of
 * the available space we used. */
static unsigned lguest_patch(u8 type, u16 clobber, void *ibuf,
			     unsigned long addr, unsigned len)
{
	unsigned int insn_len;

	/* Don't do anything special if we don't have a replacement */
	if (type >= ARRAY_SIZE(lguest_insns) || !lguest_insns[type].start)
		return paravirt_patch_default(type, clobber, ibuf, addr, len);

	insn_len = lguest_insns[type].end - lguest_insns[type].start;

	/* Similarly if we can't fit replacement (shouldn't happen, but let's
	 * be thorough). */
	if (len < insn_len)
		return paravirt_patch_default(type, clobber, ibuf, addr, len);

	/* Copy in our instructions. */
	memcpy(ibuf, lguest_insns[type].start, insn_len);
	return insn_len;
}

	/* Now we've seen all the paravirt_ops, we return to
	 * lguest_init() where the rest of the fairly chaotic boot setup
	 * occurs. */

	/* The native boot code sets up initial page tables immediately after
	 * the kernel itself, and sets init_pg_tables_end so they're not
	 * clobbered.  The Launcher places our initial pagetables somewhere at
	 * the top of our physical memory, so we don't need extra space: set
	 * init_pg_tables_end to the end of the kernel. */
	init_pg_tables_end = __pa(pg0);

	/* Load the %fs segment register (the per-cpu segment register) with
	 * the normal data segment to get through booting. */
	asm volatile ("mov %0, %%fs" : : "r" (__KERNEL_DS) : "memory");

	/* The Host uses the top of the Guest's virtual address space for the
	 * Host<->Guest Switcher, and it tells us how big that is in
	 * lguest_data.reserve_mem, set up on the LGUEST_INIT hypercall. */
	reserve_top_address(lguest_data.reserve_mem);

	/* If we don't initialize the lock dependency checker now, it crashes
	 * paravirt_disable_iospace. */
	lockdep_init();

	/* The IDE code spends about 3 seconds probing for disks: if we reserve
	 * all the I/O ports up front it can't get them and so doesn't probe.
	 * Other device drivers are similar (but less severe).  This cuts the
	 * kernel boot time on my machine from 4.1 seconds to 0.45 seconds. */
	paravirt_disable_iospace();

	/* This is messy CPU setup stuff which the native boot code does before
	 * start_kernel, so we have to do, too: */
	cpu_detect(&new_cpu_data);
	/* head.S usually sets up the first capability word, so do it here. */
	new_cpu_data.x86_capability[0] = cpuid_edx(1);

	/* Math is always hard! */
	new_cpu_data.hard_math = 1;

#ifdef CONFIG_X86_MCE
	mce_disabled = 1;
#endif
#ifdef CONFIG_ACPI
	acpi_disabled = 1;
	acpi_ht = 0;
#endif

	/* We set the perferred console to "hvc".  This is the "hypervisor
	 * virtual console" driver written by the PowerPC people, which we also
	 * adapted for lguest's use. */
	add_preferred_console("hvc", 0, NULL);

	/* Register our very early console. */
	virtio_cons_early_init(early_put_chars);

	/* Last of all, we set the power management poweroff hook to point to
	 * the Guest routine to power off. */
	pm_power_off = lguest_power_off;

	/* Now we're set up, call start_kernel() in init/main.c and we proceed
	 * to boot as normal.  It never returns. */
	start_kernel();
}
/*
 * This marks the end of stage II of our journey, The Guest.
 *
 * It is now time for us to explore the layer of virtual drivers and complete
 * our understanding of the Guest in "make Drivers".
 */

$ make Drivers
[ include/linux/lguest_launcher.h ]
/*
 * Drivers
 *
 * The Guest needs devices to do anything useful.  Since we don't let it touch
 * real devices (think of the damage it could do!) we provide virtual devices.
 * We could emulate a PCI bus with various devices on it, but that is a fairly
 * complex burden for the Host and suboptimal for the Guest, so we have our own
 * simple lguest bus and we use "virtio" drivers.  These drivers need a set of
 * routines from us which will actually do the virtual I/O, but they handle all
 * the net/block/console stuff themselves.  This means that if we want to add
 * a new device, we simply need to write a new virtio driver and create support
 * for it in the Launcher: this code won't need to change.
 *
 * Devices are described by a simplified ID, a status byte, and some "config"
 * bytes which describe this device's configuration.  This is placed by the
 * Launcher just above the top of physical memory:
 */
struct lguest_device_desc {
	/* The device type: console, network, disk etc.  Type 0 terminates. */
	__u8 type;
	/* The number of bytes of the config array. */
	__u8 config_len;
	/* A status byte, written by the Guest. */
	__u8 status;
	__u8 config[0];
};

[ drivers/lguest/lguest_device.c ]
/* Each lguest device is just a virtio device plus a pointer to its entry
 * in the lguest_devices page. */
struct lguest_device {
	struct virtio_device vdev;

	/* The entry in the lguest_devices page for this device. */
	struct lguest_device_desc *desc;
};

/* Since the virtio infrastructure hands us a pointer to the virtio_device all
 * the time, it helps to have a curt macro to get a pointer to the struct
 * lguest_device it's enclosed in.  */
#define to_lgdev(vdev) container_of(vdev, struct lguest_device, vdev)

/* Fairly early in boot, lguest_devices_init() is called to set up the
 * lguest device infrastructure.  We check that we are a Guest by checking
 * pv_info.name: there are other ways of checking, but this seems most
 * obvious to me.
 *
 * So we can access the "struct lguest_device_desc"s easily, we map that memory
 * and store the pointer in the global "lguest_devices".  Then we register a
 * root device from which all our devices will hang (this seems to be the
 * correct sysfs incantation).
 *
 * Finally we call scan_devices() which adds all the devices found in the
 * lguest_devices page. */
static int __init lguest_devices_init(void)
{
	if (strcmp(pv_info.name, "lguest") != 0)
		return 0;

	if (device_register(&lguest_root) != 0)
		panic("Could not register lguest root");

	/* Devices are in a single page above top of "normal" mem */
	lguest_devices = lguest_map(max_pfn<<PAGE_SHIFT, 1);

	scan_devices();
	return 0;
}
/* We do this after core stuff, but before the drivers. */
postcore_initcall(lguest_devices_init);

/* scan_devices() simply iterates through the device page.  The type 0 is
 * reserved to mean "end of devices". */
static void scan_devices(void)
{
	unsigned int i;
	struct lguest_device_desc *d;

	/* We start at the page beginning, and skip over each entry. */
	for (i = 0; i < PAGE_SIZE; i += sizeof(*d) + d->config_len) {
		d = lguest_devices + i;

		/* Once we hit a zero, stop. */
		if (d->type == 0)
			break;

		add_lguest_device(d);
	}
}

/* This is the core of the lguest bus: actually adding a new device.
 * It's a separate function because it's neater that way, and because an
 * earlier version of the code supported hotplug and unplug.  They were removed
 * early on because they were never used.
 *
 * As Andrew Tridgell says, "Untested code is buggy code".
 *
 * It's worth reading this carefully: we start with a pointer to the new device
 * descriptor in the "lguest_devices" page. */
static void add_lguest_device(struct lguest_device_desc *d)
{
	struct lguest_device *ldev;

	/* Start with zeroed memory; Linux's device layer seems to count on
	 * it. */
	ldev = kzalloc(sizeof(*ldev), GFP_KERNEL);
	if (!ldev) {
		printk(KERN_EMERG "Cannot allocate lguest dev %u\n",
		       dev_index++);
		return;
	}

	/* This devices' parent is the lguest/ dir. */
	ldev->vdev.dev.parent = &lguest_root;
	/* We have a unique device index thanks to the dev_index counter. */
	ldev->vdev.index = dev_index++;
	/* The device type comes straight from the descriptor.  There's also a
	 * device vendor field in the virtio_device struct, which we leave as
	 * 0. */
	ldev->vdev.id.device = d->type;
	/* We have a simple set of routines for querying the device's
	 * configuration information and setting its status. */
	ldev->vdev.config = &lguest_config_ops;
	/* And we remember the device's descriptor for lguest_config_ops. */
	ldev->desc = d;

	/* register_virtio_device() sets up the generic fields for the struct
	 * virtio_device and calls device_register().  This makes the bus
	 * infrastructure look for a matching driver. */
	if (register_virtio_device(&ldev->vdev) != 0) {
		printk(KERN_ERR "Failed to register lguest device %u\n",
		       ldev->vdev.index);
		kfree(ldev);
	}
}

/*
 * Device configurations
 *
 * The configuration information for a device consists of a series of fields.
 * We don't really care what they are: the Launcher set them up, and the driver
 * will look at them during setup.
 *
 * For us these fields come immediately after that device's descriptor in the
 * lguest_devices page.
 *
 * Each field starts with a "type" byte, a "length" byte, then that number of
 * bytes of configuration information.  The device descriptor tells us the
 * total configuration length so we know when we've reached the last field. */

/* type + length bytes */
#define FHDR_LEN 2

/* This finds the first field of a given type for a device's configuration. */
static void *lg_find(struct virtio_device *vdev, u8 type, unsigned int *len)
{
	struct lguest_device_desc *desc = to_lgdev(vdev)->desc;
	int i;

	for (i = 0; i < desc->config_len; i += FHDR_LEN + desc->config[i+1]) {
		if (desc->config[i] == type) {
			/* Mark it used, so Host can know we looked at it, and
			 * also so we won't find the same one twice. */
			desc->config[i] |= 0x80;
			/* Remember, the second byte is the length. */
			*len = desc->config[i+1];
			/* We return a pointer to the field header. */
			return desc->config + i;
		}
	}

	/* Not found: return NULL for failure. */
	return NULL;
}

/* Once they've found a field, getting a copy of it is easy. */
static void lg_get(struct virtio_device *vdev, void *token,
		   void *buf, unsigned len)
{
	/* Check they didn't ask for more than the length of the field! */
	BUG_ON(len > ((u8 *)token)[1]);
	memcpy(buf, token + FHDR_LEN, len);
}

/* Setting the contents is also trivial. */
static void lg_set(struct virtio_device *vdev, void *token,
		   const void *buf, unsigned len)
{
	BUG_ON(len > ((u8 *)token)[1]);
	memcpy(token + FHDR_LEN, buf, len);
}

/* The operations to get and set the status word just access the status field
 * of the device descriptor. */
static u8 lg_get_status(struct virtio_device *vdev)
{
	return to_lgdev(vdev)->desc->status;
}

static void lg_set_status(struct virtio_device *vdev, u8 status)
{
	to_lgdev(vdev)->desc->status = status;
}

/*
 * Virtqueues
 *
 * The other piece of infrastructure virtio needs is a "virtqueue": a way of
 * the Guest device registering buffers for the other side to read from or
 * write into (ie. send and receive buffers).  Each device can have multiple
 * virtqueues: for example the console driver uses one queue for sending and
 * another for receiving.
 *
 * Fortunately for us, a very fast shared-memory-plus-descriptors virtqueue
 * already exists in virtio_ring.c.  We just need to connect it up.
 *
 * We start with the information we need to keep about each virtqueue.
 */

[ include/linux/lguest_launcher.h ]
/* This is how we expect the device configuration field for a virtqueue
 * (type VIRTIO_CONFIG_F_VIRTQUEUE) to be laid out: */
struct lguest_vqconfig {
	/* The number of entries in the virtio_ring */
	__u16 num;
	/* The interrupt we get when something happens. */
	__u16 irq;
	/* The page number of the virtio ring for this device. */
	__u32 pfn;
};


[ drivers/lguest/lguest_device.c ]
/* This is the information we remember about each virtqueue. */
struct lguest_vq_info
{
	/* A copy of the information contained in the device config. */
	struct lguest_vqconfig config;

	/* The address where we mapped the virtio ring, so we can unmap it. */
	void *pages;
};

/* When the virtio_ring code wants to prod the Host, it calls us here and we
 * make a hypercall.  We hand the page number of the virtqueue so the Host
 * knows which virtqueue we're talking about. */
static void lg_notify(struct virtqueue *vq)
{
	/* We store our virtqueue information in the "priv" pointer of the
	 * virtqueue structure. */
	struct lguest_vq_info *lvq = vq->priv;

	hcall(LHCALL_NOTIFY, lvq->config.pfn << PAGE_SHIFT, 0, 0);
}

/* This routine finds the first virtqueue described in the configuration of
 * this device and sets it up.
 *
 * This is kind of an ugly duckling.  It'd be nicer to have a standard
 * representation of a virtqueue in the configuration space, but it seems that
 * everyone wants to do it differently.  The KVM coders want the Guest to
 * allocate its own pages and tell the Host where they are, but for lguest it's
 * simpler for the Host to simply tell us where the pages are.
 *
 * So we provide devices with a "find virtqueue and set it up" function. */
static struct virtqueue *lg_find_vq(struct virtio_device *vdev,
				    bool (*callback)(struct virtqueue *vq))
{
	struct lguest_vq_info *lvq;
	struct virtqueue *vq;
	unsigned int len;
	void *token;
	int err;

	/* Look for a field of the correct type to mark a virtqueue.  Note that
	 * if this succeeds, then the type will be changed so it won't be found
	 * again, and future lg_find_vq() calls will find the next
	 * virtqueue (if any). */
	token = vdev->config->find(vdev, VIRTIO_CONFIG_F_VIRTQUEUE, &len);
	if (!token)
		return ERR_PTR(-ENOENT);

	lvq = kmalloc(sizeof(*lvq), GFP_KERNEL);
	if (!lvq)
		return ERR_PTR(-ENOMEM);

	/* Note: we could use a configuration space inside here, just like we
	 * do for the device.  This would allow expansion in future, because
	 * our configuration system is designed to be expansible.  But this is
	 * way easier. */
	if (len != sizeof(lvq->config)) {
		dev_err(&vdev->dev, "Unexpected virtio config len %u\n", len);
		err = -EIO;
		goto free_lvq;
	}
	/* Make a copy of the "struct lguest_vqconfig" field.  We need a copy
	 * because the config space might not be aligned correctly. */
	vdev->config->get(vdev, token, &lvq->config, sizeof(lvq->config));

	/* Figure out how many pages the ring will take, and map that memory */
	lvq->pages = lguest_map((unsigned long)lvq->config.pfn << PAGE_SHIFT,
				DIV_ROUND_UP(vring_size(lvq->config.num,
							PAGE_SIZE),
					     PAGE_SIZE));
	if (!lvq->pages) {
		err = -ENOMEM;
		goto free_lvq;
	}

	/* OK, tell virtio_ring.c to set up a virtqueue now we know its size
	 * and we've got a pointer to its pages. */
	vq = vring_new_virtqueue(lvq->config.num, vdev, lvq->pages,
				 lg_notify, callback);
	if (!vq) {
		err = -ENOMEM;
		goto unmap;
	}

	/* Tell the interrupt for this virtqueue to go to the virtio_ring
	 * interrupt handler. */
	/* FIXME: We used to have a flag for the Host to tell us we could use
	 * the interrupt as a source of randomness: it'd be nice to have that
	 * back.. */
	err = request_irq(lvq->config.irq, vring_interrupt, IRQF_SHARED,
			  vdev->dev.bus_id, vq);
	if (err)
		goto destroy_vring;

	/* Last of all we hook up our 'struct lguest_vq_info" to the
	 * virtqueue's priv pointer. */
	vq->priv = lvq;
	return vq;

destroy_vring:
	vring_del_virtqueue(vq);
unmap:
	lguest_unmap(lvq->pages);
free_lvq:
	kfree(lvq);
	return ERR_PTR(err);
}


/* At this point in the journey we used to now wade through the lguest
 * devices themselves: net, block and console.  Since they're all now virtio
 * devices rather than lguest-specific, I've decided to ignore them.  Mostly,
 * they're kind of boring.  But this does mean you'll never experience the
 * thrill of reading the forbidden love scene buried deep in the block driver.
 *
 * "make Launcher" beckons, where we answer questions like "Where do Guests
 * come from?", and "What do you do when someone asks for optimization?". */

$ make Launcher
[ drivers/lguest/lguest_user.c ]
/*
 * Welcome to our journey through the Launcher!
 *
 * The Launcher is the Host userspace program which sets up, runs and services
 * the Guest.  In fact, many comments in the Drivers which refer to "the Host"
 * doing things are inaccurate: the Launcher does all the device handling for
 * the Guest, but the Guest can't know that.
 *
 * Just to confuse you: to the Host kernel, the Launcher *is* the Guest and we
 * shall see more of that later.
 *
 * We begin our understanding with the Host kernel interface which the Launcher
 * uses: reading and writing a character device called /dev/lguest.  All the
 * work happens in the read(), write() and close() routines: */
static struct file_operations lguest_fops = {
	.owner	 = THIS_MODULE,
	.release = close,
	.write	 = write,
	.read	 = read,
};

/* This is a textbook example of a "misc" character device.  Populate a "struct
 * miscdevice" and register it with misc_register(). */
static struct miscdevice lguest_dev = {
	.minor	= MISC_DYNAMIC_MINOR,
	.name	= "lguest",
	.fops	= &lguest_fops,
};

int __init lguest_device_init(void)
{
	return misc_register(&lguest_dev);
}

void __exit lguest_device_remove(void)
{
	misc_deregister(&lguest_dev);
}

/* The first operation the Launcher does must be a write.  All writes
 * start with an unsigned long number: for the first write this must be
 * LHREQ_INITIALIZE to set up the Guest.  After that the Launcher can use
 * writes of other values to send interrupts. */
static ssize_t write(struct file *file, const char __user *in,
		     size_t size, loff_t *off)
{
	/* Once the guest is initialized, we hold the "struct lguest" in the
	 * file private data. */
	struct lguest *lg = file->private_data;
	const unsigned long __user *input = (const unsigned long __user *)in;
	unsigned long req;

	if (get_user(req, input) != 0)
		return -EFAULT;
	input++;

	/* If you haven't initialized, you must do that first. */
	if (req != LHREQ_INITIALIZE && !lg)
		return -EINVAL;

	/* Once the Guest is dead, all you can do is read() why it died. */
	if (lg && lg->dead)
		return -ENOENT;

	/* If you're not the task which owns the Guest, you can only break */
	if (lg && current != lg->tsk && req != LHREQ_BREAK)
		return -EPERM;

	switch (req) {
	case LHREQ_INITIALIZE:
		return initialize(file, input);
	case LHREQ_IRQ:
		return user_send_irq(lg, input);
	case LHREQ_BREAK:
		return break_guest_out(lg, input);
	default:
		return -EINVAL;
	}
}

/* The initialization write supplies 4 pointer sized (32 or 64 bit)
 * values (in addition to the LHREQ_INITIALIZE value).  These are:
 *
 * base: The start of the Guest-physical memory inside the Launcher memory.
 *
 * pfnlimit: The highest (Guest-physical) page number the Guest should be
 * allowed to access.  The Guest memory lives inside the Launcher, so it sets
 * this to ensure the Guest can only reach its own memory.
 *
 * pgdir: The (Guest-physical) address of the top of the initial Guest
 * pagetables (which are set up by the Launcher).
 *
 * start: The first instruction to execute ("eip" in x86-speak).
 */
static int initialize(struct file *file, const unsigned long __user *input)
{
	/* "struct lguest" contains everything we (the Host) know about a
	 * Guest. */
	struct lguest *lg;
	int err;
	unsigned long args[4];

	/* We grab the Big Lguest lock, which protects against multiple
	 * simultaneous initializations. */
	mutex_lock(&lguest_lock);
	/* You can't initialize twice!  Close the device and start again... */
	if (file->private_data) {
		err = -EBUSY;
		goto unlock;
	}

	if (copy_from_user(args, input, sizeof(args)) != 0) {
		err = -EFAULT;
		goto unlock;
	}

	lg = kzalloc(sizeof(*lg), GFP_KERNEL);
	if (!lg) {
		err = -ENOMEM;
		goto unlock;
	}

	/* Populate the easy fields of our "struct lguest" */
	lg->mem_base = (void __user *)(long)args[0];
	lg->pfn_limit = args[1];

	/* We need a complete page for the Guest registers: they are accessible
	 * to the Guest and we can only grant it access to whole pages. */
	lg->regs_page = get_zeroed_page(GFP_KERNEL);
	if (!lg->regs_page) {
		err = -ENOMEM;
		goto release_guest;
	}
	/* We actually put the registers at the bottom of the page. */
	lg->regs = (void *)lg->regs_page + PAGE_SIZE - sizeof(*lg->regs);

	/* Initialize the Guest's shadow page tables, using the toplevel
	 * address the Launcher gave us.  This allocates memory, so can
	 * fail. */
	err = init_guest_pagetable(lg, args[2]);
	if (err)
		goto free_regs;

	/* Now we initialize the Guest's registers, handing it the start
	 * address. */
	lguest_arch_setup_regs(lg, args[3]);

	/* The timer for lguest's clock needs initialization. */
	init_clockdev(lg);

	/* We keep a pointer to the Launcher task (ie. current task) for when
	 * other Guests want to wake this one (inter-Guest I/O). */
	lg->tsk = current;
	/* We need to keep a pointer to the Launcher's memory map, because if
	 * the Launcher dies we need to clean it up.  If we don't keep a
	 * reference, it is destroyed before close() is called. */
	lg->mm = get_task_mm(lg->tsk);

	/* Initialize the queue for the waker to wait on */
	init_waitqueue_head(&lg->break_wq);

	/* We remember which CPU's pages this Guest used last, for optimization
	 * when the same Guest runs on the same CPU twice. */
	lg->last_pages = NULL;

	/* We keep our "struct lguest" in the file's private_data. */
	file->private_data = lg;

	mutex_unlock(&lguest_lock);

	/* And because this is a write() call, we return the length used. */
	return sizeof(args);

free_regs:
	free_page(lg->regs_page);
release_guest:
	kfree(lg);
unlock:
	mutex_unlock(&lguest_lock);
	return err;
}

[ drivers/lguest/x86/core.c ]
/* lguest_arch_setup_regs()
 *
 * Most of the Guest's registers are left alone: we used get_zeroed_page() to
 * allocate the structure, so they will be 0. */
void lguest_arch_setup_regs(struct lguest *lg, unsigned long start)
{
	struct lguest_regs *regs = lg->regs;

	/* There are four "segment" registers which the Guest needs to boot:
	 * The "code segment" register (cs) refers to the kernel code segment
	 * __KERNEL_CS, and the "data", "extra" and "stack" segment registers
	 * refer to the kernel data segment __KERNEL_DS.
	 *
	 * The privilege level is packed into the lower bits.  The Guest runs
	 * at privilege level 1 (GUEST_PL).*/
	regs->ds = regs->es = regs->ss = __KERNEL_DS|GUEST_PL;
	regs->cs = __KERNEL_CS|GUEST_PL;

	/* The "eflags" register contains miscellaneous flags.  Bit 1 (0x002)
	 * is supposed to always be "1".  Bit 9 (0x200) controls whether
	 * interrupts are enabled.  We always leave interrupts enabled while
	 * running the Guest. */
	regs->eflags = X86_EFLAGS_IF | 0x2;

	/* The "Extended Instruction Pointer" register says where the Guest is
	 * running. */
	regs->eip = start;

	/* %esi points to our boot information, at physical address 0, so don't
	 * touch it. */

	/* There are a couple of GDT entries the Guest expects when first
	 * booting. */
	setup_guest_gdt(lg);
}

[ drivers/lguest/lg.h ]
/*
 * Let's step aside for the moment, to study one important routine that's used
 * widely in the Host code.
 *
 * There are many cases where the Guest can do something invalid, like pass crap
 * to a hypercall.  Since only the Guest kernel can make hypercalls, it's quite
 * acceptable to simply terminate the Guest and give the Launcher a nicely
 * formatted reason.  It's also simpler for the Guest itself, which doesn't
 * need to check most hypercalls for "success"; if you're still running, it
 * succeeded.
 *
 * Once this is called, the Guest will never run again, so most Host code can
 * call this then continue as if nothing had happened.  This means many
 * functions don't have to explicitly return an error code, which keeps the
 * code simple.
 *
 * It also means that this can be called more than once: only the first one is
 * remembered.  The only trick is that we still need to kill the Guest even if
 * we can't allocate memory to store the reason.  Linux has a neat way of
 * packing error codes into invalid pointers, so we use that here.
 *
 * Like any macro which uses an "if", it is safely wrapped in a run-once "do {
 * } while(0)".
 */
#define kill_guest(lg, fmt...)					\
do {								\
	if (!(lg)->dead) {					\
		(lg)->dead = kasprintf(GFP_ATOMIC, fmt);	\
		if (!(lg)->dead)				\
			(lg)->dead = ERR_PTR(-ENOMEM);		\
	}							\
} while(0)
/* (End of aside) */

[ drivers/lguest/lguest_user.c ]
/* Once our Guest is initialized, the Launcher makes it run by reading
 * from /dev/lguest. */
static ssize_t read(struct file *file, char __user *user, size_t size,loff_t*o)
{
	struct lguest *lg = file->private_data;

	/* You must write LHREQ_INITIALIZE first! */
	if (!lg)
		return -EINVAL;

	/* If you're not the task which owns the Guest, go away. */
	if (current != lg->tsk)
		return -EPERM;

	/* If the guest is already dead, we indicate why */
	if (lg->dead) {
		size_t len;

		/* lg->dead either contains an error code, or a string. */
		if (IS_ERR(lg->dead))
			return PTR_ERR(lg->dead);

		/* We can only return as much as the buffer they read with. */
		len = min(size, strlen(lg->dead)+1);
		if (copy_to_user(user, lg->dead, len) != 0)
			return -EFAULT;
		return len;
	}

	/* If we returned from read() last time because the Guest notified,
	 * clear the flag. */
	if (lg->pending_notify)
		lg->pending_notify = 0;

	/* Run the Guest until something interesting happens. */
	return run_guest(lg, (unsigned long __user *)user);
}

/* Sending an interrupt is done by writing LHREQ_IRQ and an interrupt
 * number to /dev/lguest. */
static int user_send_irq(struct lguest *lg, const unsigned long __user *input)
{
	unsigned long irq;

	if (get_user(irq, input) != 0)
		return -EFAULT;
	if (irq >= LGUEST_IRQS)
		return -EINVAL;
	/* Next time the Guest runs, the core code will see if it can deliver
	 * this interrupt. */
	set_bit(irq, lg->irqs_pending);
	return 0;
}

/* When something happens, the Waker process needs a way to stop the
 * kernel running the Guest and return to the Launcher.  So the Waker writes
 * LHREQ_BREAK and the value "1" to /dev/lguest to do this.  Once the Launcher
 * has done whatever needs attention, it writes LHREQ_BREAK and "0" to release
 * the Waker. */
static int break_guest_out(struct lguest *lg, const unsigned long __user *input)
{
	unsigned long on;

	/* Fetch whether they're turning break on or off. */
	if (get_user(on, input) != 0)
		return -EFAULT;

	if (on) {
		lg->break_out = 1;
		/* Pop it out of the Guest (may be running on different CPU) */
		wake_up_process(lg->tsk);
		/* Wait for them to reset it */
		return wait_event_interruptible(lg->break_wq, !lg->break_out);
	} else {
		lg->break_out = 0;
		wake_up(&lg->break_wq);
		return 0;
	}
}

/* The final piece of interface code is the close() routine.  It reverses
 * everything done in initialize().  This is usually called because the
 * Launcher exited.
 *
 * Note that the close routine returns 0 or a negative error number: it can't
 * really fail, but it can whine.  I blame Sun for this wart, and K&R C for
 * letting them do it. */

[ Documentation/lguest/lguest.c ]
/* The Launcher code itself takes us out into userspace, that scary place
 * where pointers run wild and free!  Unfortunately, like most userspace
 * programs, it's quite boring (which is why everyone likes to hack on the
 * kernel!).  Perhaps if you make up an Lguest Drinking Game at this point, it
 * will get you through this section.  Or, maybe not.
 *
 * The Launcher sets up a big chunk of memory to be the Guest's "physical"
 * memory and stores it in "guest_base".  In other words, Guest physical ==
 * Launcher virtual with an offset.
 *
 * This can be tough to get your head around, but usually it just means that we
 * use these trivial conversion functions when the Guest gives us it's
 * "physical" addresses: */
static void *from_guest_phys(unsigned long addr)
{
	return guest_base + addr;
}

static unsigned long to_guest_phys(const void *addr)
{
	return (addr - guest_base);
}

/* The main routine is where the real work begins: */
int main(int argc, char *argv[])
{
	/* Memory, top-level pagetable, code startpoint and size of the
	 * (optional) initrd. */
	unsigned long mem = 0, pgdir, start, initrd_size = 0;
	/* Two temporaries and the /dev/lguest file descriptor. */
	int i, c, lguest_fd;
	/* The boot information for the Guest. */
	struct boot_params *boot;
	/* If they specify an initrd file to load. */
	const char *initrd_name = NULL;

	/* First we initialize the device list.  Since console and network
	 * device receive input from a file descriptor, we keep an fdset
	 * (infds) and the maximum fd number (max_infd) with the head of the
	 * list.  We also keep a pointer to the last device, for easy appending
	 * to the list.  Finally, we keep the next interrupt number to hand out
	 * (1: remember that 0 is used by the timer). */
	FD_ZERO(&devices.infds);
	devices.max_infd = -1;
	devices.lastdev = &devices.dev;
	devices.next_irq = 1;

	/* We need to know how much memory so we can set up the device
	 * descriptor and memory pages for the devices as we parse the command
	 * line.  So we quickly look through the arguments to find the amount
	 * of memory now. */
	for (i = 1; i < argc; i++) {
		if (argv[i][0] != '-') {
			mem = atoi(argv[i]) * 1024 * 1024;
			/* We start by mapping anonymous pages over all of
			 * guest-physical memory range.  This fills it with 0,
			 * and ensures that the Guest won't be killed when it
			 * tries to access it. */
			guest_base = map_zeroed_pages(mem / getpagesize()
						      + DEVICE_PAGES);
			guest_limit = mem;
			guest_max = mem + DEVICE_PAGES*getpagesize();
			devices.descpage = get_pages(1);
			break;
		}
	}

	/* The options are fairly straight-forward */
	while ((c = getopt_long(argc, argv, "v", opts, NULL)) != EOF) {
		switch (c) {
		case 'v':
			verbose = true;
			break;
		case 't':
			setup_tun_net(optarg);
			break;
		case 'b':
			setup_block_file(optarg);
			break;
		case 'i':
			initrd_name = optarg;
			break;
		default:
			warnx("Unknown argument %s", argv[optind]);
			usage();
		}
	}
	/* After the other arguments we expect memory and kernel image name,
	 * followed by command line arguments for the kernel. */
	if (optind + 2 > argc)
		usage();

	verbose("Guest base is at %p\n", guest_base);

	/* We always have a console device */
	setup_console();

	/* Now we load the kernel */
	start = load_kernel(open_or_die(argv[optind+1], O_RDONLY));

	/* Boot information is stashed at physical address 0 */
	boot = from_guest_phys(0);

	/* Map the initrd image if requested (at top of physical memory) */
	if (initrd_name) {
		initrd_size = load_initrd(initrd_name, mem);
		/* These are the location in the Linux boot header where the
		 * start and size of the initrd are expected to be found. */
		boot->hdr.ramdisk_image = mem - initrd_size;
		boot->hdr.ramdisk_size = initrd_size;
		/* The bootloader type 0xFF means "unknown"; that's OK. */
		boot->hdr.type_of_loader = 0xFF;
	}

	/* Set up the initial linear pagetables, starting below the initrd. */
	pgdir = setup_pagetables(mem, initrd_size);

	/* The Linux boot header contains an "E820" memory map: ours is a
	 * simple, single region. */
	boot->e820_entries = 1;
	boot->e820_map[0] = ((struct e820entry) { 0, mem, E820_RAM });
	/* The boot header contains a command line pointer: we put the command
	 * line after the boot header. */
	boot->hdr.cmd_line_ptr = to_guest_phys(boot + 1);
	/* We use a simple helper to copy the arguments separated by spaces. */
	concat((char *)(boot + 1), argv+optind+2);

	/* Boot protocol version: 2.07 supports the fields for lguest. */
	boot->hdr.version = 0x207;

	/* The hardware_subarch value of "1" tells the Guest it's an lguest. */
	boot->hdr.hardware_subarch = 1;

	/* Tell the entry path not to try to reload segment registers. */
	boot->hdr.loadflags |= KEEP_SEGMENTS;

	/* We tell the kernel to initialize the Guest: this returns the open
	 * /dev/lguest file descriptor. */
	lguest_fd = tell_kernel(pgdir, start);

	/* We fork off a child process, which wakes the Launcher whenever one
	 * of the input file descriptors needs attention.  Otherwise we would
	 * run the Guest until it tries to output something. */
	waker_fd = setup_waker(lguest_fd);

	/* Finally, run the Guest.  This doesn't return. */
	run_guest(lguest_fd);
}


/* We can ignore the 38 include files we need for this program, but I do
 * want to draw attention to the use of kernel-style types.
 *
 * As Linus said, "C is a Spartan language, and so should your naming be."  I
 * like these abbreviations, so we define them here.  Note that u64 is always
 * unsigned long long, which works on all Linux systems: this means that we can
 * use %llu in printf for any u64. */
typedef unsigned long long u64;
typedef uint32_t u32;
typedef uint16_t u16;
typedef uint8_t u8;


/* verbose is both a global flag and a macro.  The C preprocessor allows
 * this, and although I wouldn't recommend it, it works quite nicely here. */
static bool verbose;
#define verbose(args...) \
	do { if (verbose) printf(args); } while(0)


/*
 * Loading the Kernel.
 *
 * We start with couple of simple helper routines.  open_or_die() avoids
 * error-checking code cluttering the callers: */
static int open_or_die(const char *name, int flags)
{
	int fd = open(name, flags);
	if (fd < 0)
		err(1, "Failed to open %s", name);
	return fd;
}

/* map_zeroed_pages() takes a number of pages. */
static void *map_zeroed_pages(unsigned int num)
{
	int fd = open_or_die("/dev/zero", O_RDONLY);
	void *addr;

	/* We use a private mapping (ie. if we write to the page, it will be
	 * copied). */
	addr = mmap(NULL, getpagesize() * num,
		    PROT_READ|PROT_WRITE|PROT_EXEC, MAP_PRIVATE, fd, 0);
	if (addr == MAP_FAILED)
		err(1, "Mmaping %u pages of /dev/zero", num);

	return addr;
}

/* Get some more pages for a device. */
static void *get_pages(unsigned int num)
{
	void *addr = from_guest_phys(guest_limit);

	guest_limit += num * getpagesize();
	if (guest_limit > guest_max)
		errx(1, "Not enough memory for devices");
	return addr;
}

/* This routine is used to load the kernel or initrd.  It tries mmap, but if
 * that fails (Plan 9's kernel file isn't nicely aligned on page boundaries),
 * it falls back to reading the memory in. */
static void map_at(int fd, void *addr, unsigned long offset, unsigned long len)
{
	ssize_t r;

	/* We map writable even though for some segments are marked read-only.
	 * The kernel really wants to be writable: it patches its own
	 * instructions.
	 *
	 * MAP_PRIVATE means that the page won't be copied until a write is
	 * done to it.  This allows us to share untouched memory between
	 * Guests. */
	if (mmap(addr, len, PROT_READ|PROT_WRITE|PROT_EXEC,
		 MAP_FIXED|MAP_PRIVATE, fd, offset) != MAP_FAILED)
		return;

	/* pread does a seek and a read in one shot: saves a few lines. */
	r = pread(fd, addr, len, offset);
	if (r != len)
		err(1, "Reading offset %lu len %lu gave %zi", offset, len, r);
}

/* This routine takes an open vmlinux image, which is in ELF, and maps it into
 * the Guest memory.  ELF = Embedded Linking Format, which is the format used
 * by all modern binaries on Linux including the kernel.
 *
 * The ELF headers give *two* addresses: a physical address, and a virtual
 * address.  We use the physical address; the Guest will map itself to the
 * virtual address.
 *
 * We return the starting address. */
static unsigned long map_elf(int elf_fd, const Elf32_Ehdr *ehdr)
{
	Elf32_Phdr phdr[ehdr->e_phnum];
	unsigned int i;

	/* Sanity checks on the main ELF header: an x86 executable with a
	 * reasonable number of correctly-sized program headers. */
	if (ehdr->e_type != ET_EXEC
	    || ehdr->e_machine != EM_386
	    || ehdr->e_phentsize != sizeof(Elf32_Phdr)
	    || ehdr->e_phnum < 1 || ehdr->e_phnum > 65536U/sizeof(Elf32_Phdr))
		errx(1, "Malformed elf header");

	/* An ELF executable contains an ELF header and a number of "program"
	 * headers which indicate which parts ("segments") of the program to
	 * load where. */

	/* We read in all the program headers at once: */
	if (lseek(elf_fd, ehdr->e_phoff, SEEK_SET) < 0)
		err(1, "Seeking to program headers");
	if (read(elf_fd, phdr, sizeof(phdr)) != sizeof(phdr))
		err(1, "Reading program headers");

	/* Try all the headers: there are usually only three.  A read-only one,
	 * a read-write one, and a "note" section which isn't loadable. */
	for (i = 0; i < ehdr->e_phnum; i++) {
		/* If this isn't a loadable segment, we ignore it */
		if (phdr[i].p_type != PT_LOAD)
			continue;

		verbose("Section %i: size %i addr %p\n",
			i, phdr[i].p_memsz, (void *)phdr[i].p_paddr);

		/* We map this section of the file at its physical address. */
		map_at(elf_fd, from_guest_phys(phdr[i].p_paddr),
		       phdr[i].p_offset, phdr[i].p_filesz);
	}

	/* The entry point is given in the ELF header. */
	return ehdr->e_entry;
}

/* Loading the kernel is easy when it's a "vmlinux", but most kernels
 * come wrapped up in the self-decompressing "bzImage" format.  With a little
 * work, we can load those, too. */
static unsigned long load_kernel(int fd)
{
	Elf32_Ehdr hdr;

	/* Read in the first few bytes. */
	if (read(fd, &hdr, sizeof(hdr)) != sizeof(hdr))
		err(1, "Reading kernel");

	/* If it's an ELF file, it starts with "\177ELF" */
	if (memcmp(hdr.e_ident, ELFMAG, SELFMAG) == 0)
		return map_elf(fd, &hdr);

	/* Otherwise we assume it's a bzImage, and try to unpack it */
	return load_bzimage(fd);
}

/* This is a trivial little helper to align pages.  Andi Kleen hated it because
 * it calls getpagesize() twice: "it's dumb code."
 *
 * Kernel guys get really het up about optimization, even when it's not
 * necessary.  I leave this code as a reaction against that. */
static inline unsigned long page_align(unsigned long addr)
{
	/* Add upwards and truncate downwards. */
	return ((addr + getpagesize()-1) & ~(getpagesize()-1));
}

/* A bzImage, unlike an ELF file, is not meant to be loaded.  You're
 * supposed to jump into it and it will unpack itself.  We used to have to
 * perform some hairy magic because the unpacking code scared me.
 *
 * Fortunately, Jeremy Fitzhardinge convinced me it wasn't that hard and wrote
 * a small patch to jump over the tricky bits in the Guest, so now we just read
 * the funky header so we know where in the file to load, and away we go! */
static unsigned long load_bzimage(int fd)
{
	struct boot_params boot;
	int r;
	/* Modern bzImages get loaded at 1M. */
	void *p = from_guest_phys(0x100000);

	/* Go back to the start of the file and read the header.  It should be
	 * a Linux boot header (see Documentation/i386/boot.txt) */
	lseek(fd, 0, SEEK_SET);
	read(fd, &boot, sizeof(boot));

	/* Inside the setup_hdr, we expect the magic "HdrS" */
	if (memcmp(&boot.hdr.header, "HdrS", 4) != 0)
		errx(1, "This doesn't look like a bzImage to me");

	/* Skip over the extra sectors of the header. */
	lseek(fd, (boot.hdr.setup_sects+1) * 512, SEEK_SET);

	/* Now read everything into memory. in nice big chunks. */
	while ((r = read(fd, p, 65536)) > 0)
		p += r;

	/* Finally, code32_start tells us where to enter the kernel. */
	return boot.hdr.code32_start;
}

/* An "initial ram disk" is a disk image loaded into memory along with
 * the kernel which the kernel can use to boot from without needing any
 * drivers.  Most distributions now use this as standard: the initrd contains
 * the code to load the appropriate driver modules for the current machine.
 *
 * Importantly, James Morris works for RedHat, and Fedora uses initrds for its
 * kernels.  He sent me this (and tells me when I break it). */
static unsigned long load_initrd(const char *name, unsigned long mem)
{
	int ifd;
	struct stat st;
	unsigned long len;

	ifd = open_or_die(name, O_RDONLY);
	/* fstat() is needed to get the file size. */
	if (fstat(ifd, &st) < 0)
		err(1, "fstat() on initrd '%s'", name);

	/* We map the initrd at the top of memory, but mmap wants it to be
	 * page-aligned, so we round the size up for that. */
	len = page_align(st.st_size);
	map_at(ifd, from_guest_phys(mem - len), 0, st.st_size);
	/* Once a file is mapped, you can close the file descriptor.  It's a
	 * little odd, but quite useful. */
	close(ifd);
	verbose("mapped initrd %s size=%lu @ %p\n", name, len, (void*)mem-len);

	/* We return the initrd size. */
	return len;
}

/* Once we know how much memory we have, we can construct simple linear page
 * tables which set virtual == physical which will get the Guest far enough
 * into the boot to create its own.
 *
 * We lay them out of the way, just below the initrd (which is why we need to
 * know its size). */
static unsigned long setup_pagetables(unsigned long mem,
				      unsigned long initrd_size)
{
	unsigned long *pgdir, *linear;
	unsigned int mapped_pages, i, linear_pages;
	unsigned int ptes_per_page = getpagesize()/sizeof(void *);

	mapped_pages = mem/getpagesize();

	/* Each PTE page can map ptes_per_page pages: how many do we need? */
	linear_pages = (mapped_pages + ptes_per_page-1)/ptes_per_page;

	/* We put the toplevel page directory page at the top of memory. */
	pgdir = from_guest_phys(mem) - initrd_size - getpagesize();

	/* Now we use the next linear_pages pages as pte pages */
	linear = (void *)pgdir - linear_pages*getpagesize();

	/* Linear mapping is easy: put every page's address into the mapping in
	 * order.  PAGE_PRESENT contains the flags Present, Writable and
	 * Executable. */
	for (i = 0; i < mapped_pages; i++)
		linear[i] = ((i * getpagesize()) | PAGE_PRESENT);

	/* The top level points to the linear page table pages above. */
	for (i = 0; i < mapped_pages; i += ptes_per_page) {
		pgdir[i/ptes_per_page]
			= ((to_guest_phys(linear) + i*sizeof(void *))
			   | PAGE_PRESENT);
	}

	verbose("Linear mapping of %u pages in %u pte pages at %#lx\n",
		mapped_pages, linear_pages, to_guest_phys(linear));

	/* We return the top level (guest-physical) address: the kernel needs
	 * to know where it is. */
	return to_guest_phys(pgdir);
}


/* This is where we actually tell the kernel to initialize the Guest.  We
 * saw the arguments it expects when we looked at initialize() in lguest_user.c:
 * the base of Guest "physical" memory, the top physical page to allow, the
 * top level pagetable and the entry point for the Guest. */
static int tell_kernel(unsigned long pgdir, unsigned long start)
{
	unsigned long args[] = { LHREQ_INITIALIZE,
				 (unsigned long)guest_base,
				 guest_limit / getpagesize(), pgdir, start };
	int fd;

	verbose("Guest: %p - %p (%#lx)\n",
		guest_base, guest_base + guest_limit, guest_limit);
	fd = open_or_die("/dev/lguest", O_RDWR);
	if (write(fd, args, sizeof(args)) < 0)
		err(1, "Writing to /dev/lguest");

	/* We return the /dev/lguest file descriptor to control this Guest */
	return fd;
}


/*
 * Device Setup
 *
 * All devices need a descriptor so the Guest knows it exists, and a "struct
 * device" so the Launcher can keep track of it.  We have common helper
 * routines to allocate them.
 *
 * This routine allocates a new "struct lguest_device_desc" from descriptor
 * table just above the Guest's normal memory.  It returns a pointer to that
 * descriptor. */
static struct lguest_device_desc *new_dev_desc(u16 type)
{
	struct lguest_device_desc *d;

	/* We only have one page for all the descriptors. */
	if (devices.desc_used + sizeof(*d) > getpagesize())
		errx(1, "Too many devices");

	/* We don't need to set config_len or status: page is 0 already. */
	d = (void *)devices.descpage + devices.desc_used;
	d->type = type;
	devices.desc_used += sizeof(*d);

	return d;
}

/* Each device descriptor is followed by some configuration information.
 * Each configuration field looks like: u8 type, u8 len, [... len bytes...].
 *
 * This routine adds a new field to an existing device's descriptor.  It only
 * works for the last device, but that's OK because that's how we use it. */
static void add_desc_field(struct device *dev, u8 type, u8 len, const void *c)
{
	/* This is the last descriptor, right? */
	assert(devices.descpage + devices.desc_used
	       == (u8 *)(dev->desc + 1) + dev->desc->config_len);

	/* We only have one page of device descriptions. */
	if (devices.desc_used + 2 + len > getpagesize())
		errx(1, "Too many devices");

	/* Copy in the new config header: type then length. */
	devices.descpage[devices.desc_used++] = type;
	devices.descpage[devices.desc_used++] = len;
	memcpy(devices.descpage + devices.desc_used, c, len);
	devices.desc_used += len;

	/* Update the device descriptor length: two byte head then data. */
	dev->desc->config_len += 2 + len;
}

/* This routine adds a virtqueue to a device.  We specify how many descriptors
 * the virtqueue is to have. */
static void add_virtqueue(struct device *dev, unsigned int num_descs,
			  void (*handle_output)(int fd, struct virtqueue *me))
{
	unsigned int pages;
	struct virtqueue **i, *vq = malloc(sizeof(*vq));
	void *p;

	/* First we need some pages for this virtqueue. */
	pages = (vring_size(num_descs, getpagesize()) + getpagesize() - 1)
		/ getpagesize();
	p = get_pages(pages);

	/* Initialize the virtqueue */
	vq->next = NULL;
	vq->last_avail_idx = 0;
	vq->dev = dev;

	/* Initialize the configuration. */
	vq->config.num = num_descs;
	vq->config.irq = devices.next_irq++;
	vq->config.pfn = to_guest_phys(p) / getpagesize();

	/* Initialize the vring. */
	vring_init(&vq->vring, num_descs, p, getpagesize());

	/* Add the configuration information to this device's descriptor. */
	add_desc_field(dev, VIRTIO_CONFIG_F_VIRTQUEUE,
		       sizeof(vq->config), &vq->config);

	/* Add to tail of list, so dev->vq is first vq, dev->vq->next is
	 * second.  */
	for (i = &dev->vq; *i; i = &(*i)->next);
	*i = vq;

	/* Set the routine to call when the Guest does something to this
	 * virtqueue. */
	vq->handle_output = handle_output;

	/* Set the "Don't Notify Me" flag if we don't have a handler */
	if (!handle_output)
		vq->vring.used->flags = VRING_USED_F_NO_NOTIFY;
}

/* This routine does all the creation and setup of a new device, including
 * calling new_dev_desc() to allocate the descriptor and device memory. */
static struct device *new_device(const char *name, u16 type, int fd,
				 bool (*handle_input)(int, struct device *))
{
	struct device *dev = malloc(sizeof(*dev));

	/* Append to device list.  Prepending to a single-linked list is
	 * easier, but the user expects the devices to be arranged on the bus
	 * in command-line order.  The first network device on the command line
	 * is eth0, the first block device /dev/vda, etc. */
	*devices.lastdev = dev;
	dev->next = NULL;
	devices.lastdev = &dev->next;

	/* Now we populate the fields one at a time. */
	dev->fd = fd;
	/* If we have an input handler for this file descriptor, then we add it
	 * to the device_list's fdset and maxfd. */
	if (handle_input)
		add_device_fd(dev->fd);
	dev->desc = new_dev_desc(type);
	dev->handle_input = handle_input;
	dev->name = name;
	dev->vq = NULL;
	return dev;
}

/* Our first setup routine is the console.  It's a fairly simple device, but
 * UNIX tty handling makes it uglier than it could be. */
static void setup_console(void)
{
	struct device *dev;

	/* If we can save the initial standard input settings... */
	if (tcgetattr(STDIN_FILENO, &orig_term) == 0) {
		struct termios term = orig_term;
		/* Then we turn off echo, line buffering and ^C etc.  We want a
		 * raw input stream to the Guest. */
		term.c_lflag &= ~(ISIG|ICANON|ECHO);
		tcsetattr(STDIN_FILENO, TCSANOW, &term);
		/* If we exit gracefully, the original settings will be
		 * restored so the user can see what they're typing. */
		atexit(restore_term);
	}

	dev = new_device("console", VIRTIO_ID_CONSOLE,
			 STDIN_FILENO, handle_console_input);
	/* We store the console state in dev->priv, and initialize it. */
	dev->priv = malloc(sizeof(struct console_abort));
	((struct console_abort *)dev->priv)->count = 0;

	/* The console needs two virtqueues: the input then the output.  When
	 * they put something the input queue, we make sure we're listening to
	 * stdin.  When they put something in the output queue, we write it to
	 * stdout. */
	add_virtqueue(dev, VIRTQUEUE_NUM, enable_fd);
	add_virtqueue(dev, VIRTQUEUE_NUM, handle_console_output);

	verbose("device %u: console\n", devices.device_num++);
}


/* Our network is a Host<->Guest network.  This can either use bridging or
 * routing, but the principle is the same: it uses the "tun" device to inject
 * packets into the Host as if they came in from a normal network card.  We
 * just shunt packets between the Guest and the tun device. */
static void setup_tun_net(const char *arg)
{
	struct device *dev;
	struct ifreq ifr;
	int netfd, ipfd;
	u32 ip;
	const char *br_name = NULL;
	u8 hwaddr[6];

	/* We open the /dev/net/tun device and tell it we want a tap device.  A
	 * tap device is like a tun device, only somehow different.  To tell
	 * the truth, I completely blundered my way through this code, but it
	 * works now! */
	netfd = open_or_die("/dev/net/tun", O_RDWR);
	memset(&ifr, 0, sizeof(ifr));
	ifr.ifr_flags = IFF_TAP | IFF_NO_PI;
	strcpy(ifr.ifr_name, "tap%d");
	if (ioctl(netfd, TUNSETIFF, &ifr) != 0)
		err(1, "configuring /dev/net/tun");
	/* We don't need checksums calculated for packets coming in this
	 * device: trust us! */
	ioctl(netfd, TUNSETNOCSUM, 1);

	/* First we create a new network device. */
	dev = new_device("net", VIRTIO_ID_NET, netfd, handle_tun_input);

	/* Network devices need a receive and a send queue, just like
	 * console. */
	add_virtqueue(dev, VIRTQUEUE_NUM, enable_fd);
	add_virtqueue(dev, VIRTQUEUE_NUM, handle_net_output);

	/* We need a socket to perform the magic network ioctls to bring up the
	 * tap interface, connect to the bridge etc.  Any socket will do! */
	ipfd = socket(PF_INET, SOCK_DGRAM, IPPROTO_IP);
	if (ipfd < 0)
		err(1, "opening IP socket");

	/* If the command line was --tunnet=bridge:<name> do bridging. */
	if (!strncmp(BRIDGE_PFX, arg, strlen(BRIDGE_PFX))) {
		ip = INADDR_ANY;
		br_name = arg + strlen(BRIDGE_PFX);
		add_to_bridge(ipfd, ifr.ifr_name, br_name);
	} else /* It is an IP address to set up the device with */
		ip = str2ip(arg);

	/* Set up the tun device, and get the mac address for the interface. */
	configure_device(ipfd, ifr.ifr_name, ip, hwaddr);

	/* Tell Guest what MAC address to use. */
	add_desc_field(dev, VIRTIO_CONFIG_NET_MAC_F, sizeof(hwaddr), hwaddr);

	/* We don't seed the socket any more; setup is done. */
	close(ipfd);

	verbose("device %u: tun net %u.%u.%u.%u\n",
		devices.device_num++,
		(u8)(ip>>24),(u8)(ip>>16),(u8)(ip>>8),(u8)ip);
	if (br_name)
		verbose("attached to bridge: %s\n", br_name);
}

/* Our block (disk) device should be really simple: the Guest asks for a block
 * number and we read or write that position in the file.  Unfortunately, that
 * was amazingly slow: the Guest waits until the read is finished before
 * running anything else, even if it could have been doing useful work.
 *
 * We could use async I/O, except it's reputed to suck so hard that characters
 * actually go missing from your code when you try to use it.
 *
 * So we farm the I/O out to thread, and communicate with it via a pipe. */

/* This hangs off device->priv. */
struct vblk_info
{
	/* The size of the file. */
	off64_t len;

	/* The file descriptor for the file. */
	int fd;

	/* IO thread listens on this file descriptor [0]. */
	int workpipe[2];

	/* IO thread writes to this file descriptor to mark it done, then
	 * Launcher triggers interrupt to Guest. */
	int done_fd;
};


/* This actually sets up a virtual block device. */
static void setup_block_file(const char *filename)
{
	int p[2];
	struct device *dev;
	struct vblk_info *vblk;
	void *stack;
	u64 cap;
	unsigned int val;

	/* This is the pipe the I/O thread will use to tell us I/O is done. */
	pipe(p);

	/* The device responds to return from I/O thread. */
	dev = new_device("block", VIRTIO_ID_BLOCK, p[0], handle_io_finish);

	/* The device has one virtqueue, where the Guest places requests. */
	add_virtqueue(dev, VIRTQUEUE_NUM, handle_virtblk_output);

	/* Allocate the room for our own bookkeeping */
	vblk = dev->priv = malloc(sizeof(*vblk));

	/* First we open the file and store the length. */
	vblk->fd = open_or_die(filename, O_RDWR|O_LARGEFILE);
	vblk->len = lseek64(vblk->fd, 0, SEEK_END);

	/* Tell Guest how many sectors this device has. */
	cap = cpu_to_le64(vblk->len / 512);
	add_desc_field(dev, VIRTIO_CONFIG_BLK_F_CAPACITY, sizeof(cap), &cap);

	/* Tell Guest not to put in too many descriptors at once: two are used
	 * for the in and out elements. */
	val = cpu_to_le32(VIRTQUEUE_NUM - 2);
	add_desc_field(dev, VIRTIO_CONFIG_BLK_F_SEG_MAX, sizeof(val), &val);

	/* The I/O thread writes to this end of the pipe when done. */
	vblk->done_fd = p[1];

	/* This is the second pipe, which is how we tell the I/O thread about
	 * more work. */
	pipe(vblk->workpipe);

	/* Create stack for thread and run it */
	stack = malloc(32768);
	if (clone(io_thread, stack + 32768, CLONE_VM, dev) == -1)
		err(1, "Creating clone");

	/* We don't need to keep the I/O thread's end of the pipes open. */
	close(vblk->done_fd);
	close(vblk->workpipe[0]);

	verbose("device %u: virtblock %llu sectors\n",
		devices.device_num, cap);
}
/* That's the end of device setup. */

/*
 * The Waker.
 *
 * With console, block and network devices, we can have lots of input which we
 * need to process.  We could try to tell the kernel what file descriptors to
 * watch, but handing a file descriptor mask through to the kernel is fairly
 * icky.
 *
 * Instead, we fork off a process which watches the file descriptors and writes
 * the LHREQ_BREAK command to the /dev/lguest file descriptor to tell the Host
 * stop running the Guest.  This causes the Launcher to return from the
 * /dev/lguest read with -EAGAIN, where it will write to /dev/lguest to reset
 * the LHREQ_BREAK and wake us up again.
 *
 * This, of course, is merely a different *kind* of icky.
 */
static void wake_parent(int pipefd, int lguest_fd)
{
	/* Add the pipe from the Launcher to the fdset in the device_list, so
	 * we watch it, too. */
	add_device_fd(pipefd);

	for (;;) {
		fd_set rfds = devices.infds;
		unsigned long args[] = { LHREQ_BREAK, 1 };

		/* Wait until input is ready from one of the devices. */
		select(devices.max_infd+1, &rfds, NULL, NULL, NULL);
		/* Is it a message from the Launcher? */
		if (FD_ISSET(pipefd, &rfds)) {
			int fd;
			/* If read() returns 0, it means the Launcher has
			 * exited.  We silently follow. */
			if (read(pipefd, &fd, sizeof(fd)) == 0)
				exit(0);
			/* Otherwise it's telling us to change what file
			 * descriptors we're to listen to.  Positive means
			 * listen to a new one, negative means stop
			 * listening. */
			if (fd >= 0)
				FD_SET(fd, &devices.infds);
			else
				FD_CLR(-fd - 1, &devices.infds);
		} else /* Send LHREQ_BREAK command. */
			write(lguest_fd, args, sizeof(args));
	}
}

/* This routine just sets up a pipe to the Waker process. */
static int setup_waker(int lguest_fd)
{
	int pipefd[2], child;

	/* We create a pipe to talk to the Waker, and also so it knows when the
	 * Launcher dies (and closes pipe). */
	pipe(pipefd);
	child = fork();
	if (child == -1)
		err(1, "forking");

	if (child == 0) {
		/* We are the Waker: close the "writing" end of our copy of the
		 * pipe and start waiting for input. */
		close(pipefd[1]);
		wake_parent(pipefd[0], lguest_fd);
	}
	/* Close the reading end of our copy of the pipe. */
	close(pipefd[0]);

	/* Here is the fd used to talk to the waker. */
	return pipefd[1];
}

/*
 * Device Handling.
 *
 * When the Guest gives us a buffer, it sends an array of addresses and sizes.
 * We need to make sure it's not trying to reach into the Launcher itself, so
 * we have a convenient routine which checks it and exits with an error message
 * if something funny is going on:
 */
static void *_check_pointer(unsigned long addr, unsigned int size,
			    unsigned int line)
{
	/* We have to separately check addr and addr+size, because size could
	 * be huge and addr + size might wrap around. */
	if (addr >= guest_limit || addr + size >= guest_limit)
		errx(1, "%s:%i: Invalid address %#lx", __FILE__, line, addr);
	/* We return a pointer for the caller's convenience, now we know it's
	 * safe to use. */
	return from_guest_phys(addr);
}
/* A macro which transparently hands the line number to the real function. */
#define check_pointer(addr,size) _check_pointer(addr, size, __LINE__)

/* Each buffer in the virtqueues is actually a chain of descriptors.  This
 * function returns the next descriptor in the chain, or vq->vring.num if we're
 * at the end. */
static unsigned next_desc(struct virtqueue *vq, unsigned int i)
{
	unsigned int next;

	/* If this descriptor says it doesn't chain, we're done. */
	if (!(vq->vring.desc[i].flags & VRING_DESC_F_NEXT))
		return vq->vring.num;

	/* Check they're not leading us off end of descriptors. */
	next = vq->vring.desc[i].next;
	/* Make sure compiler knows to grab that: we don't want it changing! */
	wmb();

	if (next >= vq->vring.num)
		errx(1, "Desc next is %u", next);

	return next;
}

/* This looks in the virtqueue and for the first available buffer, and converts
 * it to an iovec for convenient access.  Since descriptors consist of some
 * number of output then some number of input descriptors, it's actually two
 * iovecs, but we pack them into one and note how many of each there were.
 *
 * This function returns the descriptor number found, or vq->vring.num (which
 * is never a valid descriptor number) if none was found. */
static unsigned get_vq_desc(struct virtqueue *vq,
			    struct iovec iov[],
			    unsigned int *out_num, unsigned int *in_num)
{
	unsigned int i, head;

	/* Check it isn't doing very strange things with descriptor numbers. */
	if ((u16)(vq->vring.avail->idx - vq->last_avail_idx) > vq->vring.num)
		errx(1, "Guest moved used index from %u to %u",
		     vq->last_avail_idx, vq->vring.avail->idx);

	/* If there's nothing new since last we looked, return invalid. */
	if (vq->vring.avail->idx == vq->last_avail_idx)
		return vq->vring.num;

	/* Grab the next descriptor number they're advertising, and increment
	 * the index we've seen. */
	head = vq->vring.avail->ring[vq->last_avail_idx++ % vq->vring.num];

	/* If their number is silly, that's a fatal mistake. */
	if (head >= vq->vring.num)
		errx(1, "Guest says index %u is available", head);

	/* When we start there are none of either input nor output. */
	*out_num = *in_num = 0;

	i = head;
	do {
		/* Grab the first descriptor, and check it's OK. */
		iov[*out_num + *in_num].iov_len = vq->vring.desc[i].len;
		iov[*out_num + *in_num].iov_base
			= check_pointer(vq->vring.desc[i].addr,
					vq->vring.desc[i].len);
		/* If this is an input descriptor, increment that count. */
		if (vq->vring.desc[i].flags & VRING_DESC_F_WRITE)
			(*in_num)++;
		else {
			/* If it's an output descriptor, they're all supposed
			 * to come before any input descriptors. */
			if (*in_num)
				errx(1, "Descriptor has out after in");
			(*out_num)++;
		}

		/* If we've got too many, that implies a descriptor loop. */
		if (*out_num + *in_num > vq->vring.num)
			errx(1, "Looped descriptor");
	} while ((i = next_desc(vq, i)) != vq->vring.num);

	return head;
}

/* After we've used one of their buffers, we tell them about it.  We'll then
 * want to send them an interrupt, using trigger_irq(). */
static void add_used(struct virtqueue *vq, unsigned int head, int len)
{
	struct vring_used_elem *used;

	/* The virtqueue contains a ring of used buffers.  Get a pointer to the
	 * next entry in that used ring. */
	used = &vq->vring.used->ring[vq->vring.used->idx % vq->vring.num];
	used->id = head;
	used->len = len;
	/* Make sure buffer is written before we update index. */
	wmb();
	vq->vring.used->idx++;
}

/* This actually sends the interrupt for this virtqueue */
static void trigger_irq(int fd, struct virtqueue *vq)
{
	unsigned long buf[] = { LHREQ_IRQ, vq->config.irq };

	/* If they don't want an interrupt, don't send one. */
	if (vq->vring.avail->flags & VRING_AVAIL_F_NO_INTERRUPT)
		return;

	/* Send the Guest an interrupt tell them we used something up. */
	if (write(fd, buf, sizeof(buf)) != 0)
		err(1, "Triggering irq %i", vq->config.irq);
}

/* And here's the combo meal deal.  Supersize me! */
static void add_used_and_trigger(int fd, struct virtqueue *vq,
				 unsigned int head, int len)
{
	add_used(vq, head, len);
	trigger_irq(fd, vq);
}

/*
 * The Console
 *
 * Here is the input terminal setting we save, and the routine to restore them
 * on exit so the user gets their terminal back. */
static struct termios orig_term;
static void restore_term(void)
{
	tcsetattr(STDIN_FILENO, TCSANOW, &orig_term);
}

/* We associate some data with the console for our exit hack. */
struct console_abort
{
	/* How many times have they hit ^C? */
	int count;
	/* When did they start? */
	struct timeval start;
};

/* This is the routine which handles console input (ie. stdin). */
static bool handle_console_input(int fd, struct device *dev)
{
	int len;
	unsigned int head, in_num, out_num;
	struct iovec iov[dev->vq->vring.num];
	struct console_abort *abort = dev->priv;

	/* First we need a console buffer from the Guests's input virtqueue. */
	head = get_vq_desc(dev->vq, iov, &out_num, &in_num);

	/* If they're not ready for input, stop listening to this file
	 * descriptor.  We'll start again once they add an input buffer. */
	if (head == dev->vq->vring.num)
		return false;

	if (out_num)
		errx(1, "Output buffers in console in queue?");

	/* This is why we convert to iovecs: the readv() call uses them, and so
	 * it reads straight into the Guest's buffer. */
	len = readv(dev->fd, iov, in_num);
	if (len <= 0) {
		/* This implies that the console is closed, is /dev/null, or
		 * something went terribly wrong. */
		warnx("Failed to get console input, ignoring console.");
		/* Put the input terminal back. */
		restore_term();
		/* Remove callback from input vq, so it doesn't restart us. */
		dev->vq->handle_output = NULL;
		/* Stop listening to this fd: don't call us again. */
		return false;
	}

	/* Tell the Guest about the new input. */
	add_used_and_trigger(fd, dev->vq, head, len);

	/* Three ^C within one second?  Exit.
	 *
	 * This is such a hack, but works surprisingly well.  Each ^C has to be
	 * in a buffer by itself, so they can't be too fast.  But we check that
	 * we get three within about a second, so they can't be too slow. */
	if (len == 1 && ((char *)iov[0].iov_base)[0] == 3) {
		if (!abort->count++)
			gettimeofday(&abort->start, NULL);
		else if (abort->count == 3) {
			struct timeval now;
			gettimeofday(&now, NULL);
			if (now.tv_sec <= abort->start.tv_sec+1) {
				unsigned long args[] = { LHREQ_BREAK, 0 };
				/* Close the fd so Waker will know it has to
				 * exit. */
				close(waker_fd);
				/* Just in case waker is blocked in BREAK, send
				 * unbreak now. */
				write(fd, args, sizeof(args));
				exit(2);
			}
			abort->count = 0;
		}
	} else
		/* Any other key resets the abort counter. */
		abort->count = 0;

	/* Everything went OK! */
	return true;
}

/* Handling output for console is simple: we just get all the output buffers
 * and write them to stdout. */
static void handle_console_output(int fd, struct virtqueue *vq)
{
	unsigned int head, out, in;
	int len;
	struct iovec iov[vq->vring.num];

	/* Keep getting output buffers from the Guest until we run out. */
	while ((head = get_vq_desc(vq, iov, &out, &in)) != vq->vring.num) {
		if (in)
			errx(1, "Input buffers in output queue?");
		len = writev(STDOUT_FILENO, iov, out);
		add_used_and_trigger(fd, vq, head, len);
	}
}

/*
 * The Network
 *
 * Handling output for network is also simple: we get all the output buffers
 * and write them (ignoring the first element) to this device's file descriptor
 * (stdout). */
static void handle_net_output(int fd, struct virtqueue *vq)
{
	unsigned int head, out, in;
	int len;
	struct iovec iov[vq->vring.num];

	/* Keep getting output buffers from the Guest until we run out. */
	while ((head = get_vq_desc(vq, iov, &out, &in)) != vq->vring.num) {
		if (in)
			errx(1, "Input buffers in output queue?");
		/* Check header, but otherwise ignore it (we told the Guest we
		 * supported no features, so it shouldn't have anything
		 * interesting). */
		(void)convert(&iov[0], struct virtio_net_hdr);
		len = writev(vq->dev->fd, iov+1, out-1);
		add_used_and_trigger(fd, vq, head, len);
	}
}

/* This is where we handle a packet coming in from the tun device to our
 * Guest. */
static bool handle_tun_input(int fd, struct device *dev)
{
	unsigned int head, in_num, out_num;
	int len;
	struct iovec iov[dev->vq->vring.num];
	struct virtio_net_hdr *hdr;

	/* First we need a network buffer from the Guests's recv virtqueue. */
	head = get_vq_desc(dev->vq, iov, &out_num, &in_num);
	if (head == dev->vq->vring.num) {
		/* Now, it's expected that if we try to send a packet too
		 * early, the Guest won't be ready yet.  Wait until the device
		 * status says it's ready. */
		/* FIXME: Actually want DRIVER_ACTIVE here. */
		if (dev->desc->status & VIRTIO_CONFIG_S_DRIVER_OK)
			warn("network: no dma buffer!");
		/* We'll turn this back on if input buffers are registered. */
		return false;
	} else if (out_num)
		errx(1, "Output buffers in network recv queue?");

	/* First element is the header: we set it to 0 (no features). */
	hdr = convert(&iov[0], struct virtio_net_hdr);
	hdr->flags = 0;
	hdr->gso_type = VIRTIO_NET_HDR_GSO_NONE;

	/* Read the packet from the device directly into the Guest's buffer. */
	len = readv(dev->fd, iov+1, in_num-1);
	if (len <= 0)
		err(1, "reading network");

	/* Tell the Guest about the new packet. */
	add_used_and_trigger(fd, dev->vq, head, sizeof(*hdr) + len);

	verbose("tun input packet len %i [%02x %02x] (%s)\n", len,
		((u8 *)iov[1].iov_base)[0], ((u8 *)iov[1].iov_base)[1],
		head != dev->vq->vring.num ? "sent" : "discarded");

	/* All good. */
	return true;
}

/*
 * The Disk
 *
 * Remember that the block device is handled by a separate I/O thread.  We head
 * straight into the core of that thread here:
 */
static bool service_io(struct device *dev)
{
	struct vblk_info *vblk = dev->priv;
	unsigned int head, out_num, in_num, wlen;
	int ret;
	struct virtio_blk_inhdr *in;
	struct virtio_blk_outhdr *out;
	struct iovec iov[dev->vq->vring.num];
	off64_t off;

	/* See if there's a request waiting.  If not, nothing to do. */
	head = get_vq_desc(dev->vq, iov, &out_num, &in_num);
	if (head == dev->vq->vring.num)
		return false;

	/* Every block request should contain at least one output buffer
	 * (detailing the location on disk and the type of request) and one
	 * input buffer (to hold the result). */
	if (out_num == 0 || in_num == 0)
		errx(1, "Bad virtblk cmd %u out=%u in=%u",
		     head, out_num, in_num);

	out = convert(&iov[0], struct virtio_blk_outhdr);
	in = convert(&iov[out_num+in_num-1], struct virtio_blk_inhdr);
	off = out->sector * 512;

	/* The block device implements "barriers", where the Guest indicates
	 * that it wants all previous writes to occur before this write.  We
	 * don't have a way of asking our kernel to do a barrier, so we just
	 * synchronize all the data in the file.  Pretty poor, no? */
	if (out->type & VIRTIO_BLK_T_BARRIER)
		fdatasync(vblk->fd);

	/* In general the virtio block driver is allowed to try SCSI commands.
	 * It'd be nice if we supported eject, for example, but we don't. */
	if (out->type & VIRTIO_BLK_T_SCSI_CMD) {
		fprintf(stderr, "Scsi commands unsupported\n");
		in->status = VIRTIO_BLK_S_UNSUPP;
		wlen = sizeof(*in);
	} else if (out->type & VIRTIO_BLK_T_OUT) {
		/* Write */

		/* Move to the right location in the block file.  This can fail
		 * if they try to write past end. */
		if (lseek64(vblk->fd, off, SEEK_SET) != off)
			err(1, "Bad seek to sector %llu", out->sector);

		ret = writev(vblk->fd, iov+1, out_num-1);
		verbose("WRITE to sector %llu: %i\n", out->sector, ret);

		/* Grr... Now we know how long the descriptor they sent was, we
		 * make sure they didn't try to write over the end of the block
		 * file (possibly extending it). */
		if (ret > 0 && off + ret > vblk->len) {
			/* Trim it back to the correct length */
			ftruncate64(vblk->fd, vblk->len);
			/* Die, bad Guest, die. */
			errx(1, "Write past end %llu+%u", off, ret);
		}
		wlen = sizeof(*in);
		in->status = (ret >= 0 ? VIRTIO_BLK_S_OK : VIRTIO_BLK_S_IOERR);
	} else {
		/* Read */

		/* Move to the right location in the block file.  This can fail
		 * if they try to read past end. */
		if (lseek64(vblk->fd, off, SEEK_SET) != off)
			err(1, "Bad seek to sector %llu", out->sector);

		ret = readv(vblk->fd, iov+1, in_num-1);
		verbose("READ from sector %llu: %i\n", out->sector, ret);
		if (ret >= 0) {
			wlen = sizeof(*in) + ret;
			in->status = VIRTIO_BLK_S_OK;
		} else {
			wlen = sizeof(*in);
			in->status = VIRTIO_BLK_S_IOERR;
		}
	}

	/* We can't trigger an IRQ, because we're not the Launcher.  It does
	 * that when we tell it we're done. */
	add_used(dev->vq, head, wlen);
	return true;
}

/* This is the thread which actually services the I/O. */
static int io_thread(void *_dev)
{
	struct device *dev = _dev;
	struct vblk_info *vblk = dev->priv;
	char c;

	/* Close other side of workpipe so we get 0 read when main dies. */
	close(vblk->workpipe[1]);
	/* Close the other side of the done_fd pipe. */
	close(dev->fd);

	/* When this read fails, it means Launcher died, so we follow. */
	while (read(vblk->workpipe[0], &c, 1) == 1) {
		/* We acknowledge each request immediately to reduce latency,
		 * rather than waiting until we've done them all.  I haven't
		 * measured to see if it makes any difference. */
		while (service_io(dev))
			write(vblk->done_fd, &c, 1);
	}
	return 0;
}

/* Now we've seen the I/O thread, we return to the Launcher to see what happens
 * when the thread tells us it's completed some I/O. */
static bool handle_io_finish(int fd, struct device *dev)
{
	char c;

	/* If the I/O thread died, presumably it printed the error, so we
	 * simply exit. */
	if (read(dev->fd, &c, 1) != 1)
		exit(1);

	/* It did some work, so trigger the irq. */
	trigger_irq(fd, dev->vq);
	return true;
}

/* When the Guest submits some I/O, we just need to wake the I/O thread. */
static void handle_virtblk_output(int fd, struct virtqueue *vq)
{
	struct vblk_info *vblk = vq->dev->priv;
	char c = 0;

	/* Wake up I/O thread and tell it to go to work! */
	if (write(vblk->workpipe[1], &c, 1) != 1)
		/* Presumably it indicated why it died. */
		exit(1);
}

/* This is the callback attached to the network and console input
 * virtqueues: it ensures we try again, in case we stopped console or net
 * delivery because Guest didn't have any buffers. */
static void enable_fd(int fd, struct virtqueue *vq)
{
	add_device_fd(vq->dev->fd);
	/* Tell waker to listen to it again */
	write(waker_fd, &vq->dev->fd, sizeof(vq->dev->fd));
}

/* This is the generic routine we call when the Guest uses LHCALL_NOTIFY. */
static void handle_output(int fd, unsigned long addr)
{
	struct device *i;
	struct virtqueue *vq;

	/* Check each virtqueue. */
	for (i = devices.dev; i; i = i->next) {
		for (vq = i->vq; vq; vq = vq->next) {
			if (vq->config.pfn == addr/getpagesize()
			    && vq->handle_output) {
				verbose("Output to %s\n", vq->dev->name);
				vq->handle_output(fd, vq);
				return;
			}
		}
	}

	/* Early console write is done using notify on a nul-terminated string
	 * in Guest memory. */
	if (addr >= guest_limit)
		errx(1, "Bad NOTIFY %#lx", addr);

	write(STDOUT_FILENO, from_guest_phys(addr),
	      strnlen(from_guest_phys(addr), guest_limit - addr));
}

/* This is called when the Waker wakes us up: check for incoming file
 * descriptors. */
static void handle_input(int fd)
{
	/* select() wants a zeroed timeval to mean "don't wait". */
	struct timeval poll = { .tv_sec = 0, .tv_usec = 0 };

	for (;;) {
		struct device *i;
		fd_set fds = devices.infds;

		/* If nothing is ready, we're done. */
		if (select(devices.max_infd+1, &fds, NULL, NULL, &poll) == 0)
			break;

		/* Otherwise, call the device(s) which have readable
		 * file descriptors and a method of handling them.  */
		for (i = devices.dev; i; i = i->next) {
			if (i->handle_input && FD_ISSET(i->fd, &fds)) {
				int dev_fd;
				if (i->handle_input(fd, i))
					continue;

				/* If handle_input() returns false, it means we
				 * should no longer service it.  Networking and
				 * console do this when there's no input
				 * buffers to deliver into.  Console also uses
				 * it when it discovers that stdin is
				 * closed. */
				FD_CLR(i->fd, &devices.infds);
				/* Tell waker to ignore it too, by sending a
				 * negative fd number (-1, since 0 is a valid
				 * FD number). */
				dev_fd = -i->fd - 1;
				write(waker_fd, &dev_fd, sizeof(dev_fd));
			}
		}
	}
}

/* Finally we reach the core of the Launcher, which runs the Guest, serves
 * its input and output, and finally, lays it to rest. */
static void __attribute__((noreturn)) run_guest(int lguest_fd)
{
	for (;;) {
		unsigned long args[] = { LHREQ_BREAK, 0 };
		unsigned long notify_addr;
		int readval;

		/* We read from the /dev/lguest device to run the Guest. */
		readval = read(lguest_fd, &notify_addr, sizeof(notify_addr));

		/* One unsigned long means the Guest did HCALL_NOTIFY */
		if (readval == sizeof(notify_addr)) {
			verbose("Notify on address %#lx\n", notify_addr);
			handle_output(lguest_fd, notify_addr);
			continue;
		/* ENOENT means the Guest died.  Reading tells us why. */
		} else if (errno == ENOENT) {
			char reason[1024] = { 0 };
			read(lguest_fd, reason, sizeof(reason)-1);
			errx(1, "%s", reason);
		/* EAGAIN means the Waker wanted us to look at some input.
		 * Anything else means a bug or incompatible change. */
		} else if (errno != EAGAIN)
			err(1, "Running guest failed");

		/* Service input, then unset the BREAK to release the Waker. */
		handle_input(lguest_fd);
		if (write(lguest_fd, args, sizeof(args)) < 0)
			err(1, "Resetting break");
	}
}
/*
 * This is the end of the Launcher.  The good news: we are over halfway
 * through!  The bad news: the most fiendish part of the code still lies ahead
 * of us.
 *
 * Are you ready?  Take a deep breath and join me in the core of the Host, in
 * "make Host".
 */

$ make Host
[ drivers/lguest/core.c ]
/*
 * Welcome to the Host!
 *
 * By this point your brain has been tickled by the Guest code and numbed by
 * the Launcher code; prepare for it to be stretched by the Host code.  This is
 * the heart.  Let's begin at the initialization routine for the Host's lg
 * module.
 */
static int __init init(void)
{
	int err;

	/* Lguest can't run under Xen, VMI or itself.  It does Tricky Stuff. */
	if (paravirt_enabled()) {
		printk("lguest is afraid of %s\n", pv_info.name);
		return -EPERM;
	}

	/* First we put the Switcher up in very high virtual memory. */
	err = map_switcher();
	if (err)
		goto out;

	/* Now we set up the pagetable implementation for the Guests. */
	err = init_pagetables(switcher_page, SHARED_SWITCHER_PAGES);
	if (err)
		goto unmap;

	/* We might need to reserve an interrupt vector. */
	err = init_interrupts();
	if (err)
		goto free_pgtables;

	/* /dev/lguest needs to be registered. */
	err = lguest_device_init();
	if (err)
		goto free_interrupts;

	/* Finally we do some architecture-specific setup. */
	lguest_arch_host_init();

	/* All good! */
	return 0;

free_interrupts:
	free_interrupts();
free_pgtables:
	free_pagetables();
unmap:
	unmap_switcher();
out:
	return err;
}

/* Cleaning up is just the same code, backwards.  With a little French. */
static void __exit fini(void)
{
	lguest_device_remove();
	free_interrupts();
	free_pagetables();
	unmap_switcher();

	lguest_arch_host_fini();
}


/* We need to set up the Switcher at a high virtual address.  Remember the
 * Switcher is a few hundred bytes of assembler code which actually changes the
 * CPU to run the Guest, and then changes back to the Host when a trap or
 * interrupt happens.
 *
 * The Switcher code must be at the same virtual address in the Guest as the
 * Host since it will be running as the switchover occurs.
 *
 * Trying to map memory at a particular address is an unusual thing to do, so
 * it's not a simple one-liner. */
static __init int map_switcher(void)
{
	int i, err;
	struct page **pagep;

	/*
	 * Map the Switcher in to high memory.
	 *
	 * It turns out that if we choose the address 0xFFC00000 (4MB under the
	 * top virtual address), it makes setting up the page tables really
	 * easy.
	 */

	/* We allocate an array of "struct page"s.  map_vm_area() wants the
	 * pages in this form, rather than just an array of pointers. */
	switcher_page = kmalloc(sizeof(switcher_page[0])*TOTAL_SWITCHER_PAGES,
				GFP_KERNEL);
	if (!switcher_page) {
		err = -ENOMEM;
		goto out;
	}

	/* Now we actually allocate the pages.  The Guest will see these pages,
	 * so we make sure they're zeroed. */
	for (i = 0; i < TOTAL_SWITCHER_PAGES; i++) {
		unsigned long addr = get_zeroed_page(GFP_KERNEL);
		if (!addr) {
			err = -ENOMEM;
			goto free_some_pages;
		}
		switcher_page[i] = virt_to_page(addr);
	}

	/* Now we reserve the "virtual memory area" we want: 0xFFC00000
	 * (SWITCHER_ADDR).  We might not get it in theory, but in practice
	 * it's worked so far. */
	switcher_vma = __get_vm_area(TOTAL_SWITCHER_PAGES * PAGE_SIZE,
				       VM_ALLOC, SWITCHER_ADDR, VMALLOC_END);
	if (!switcher_vma) {
		err = -ENOMEM;
		printk("lguest: could not map switcher pages high\n");
		goto free_pages;
	}

	/* This code actually sets up the pages we've allocated to appear at
	 * SWITCHER_ADDR.  map_vm_area() takes the vma we allocated above, the
	 * kind of pages we're mapping (kernel pages), and a pointer to our
	 * array of struct pages.  It increments that pointer, but we don't
	 * care. */
	pagep = switcher_page;
	err = map_vm_area(switcher_vma, PAGE_KERNEL, &pagep);
	if (err) {
		printk("lguest: map_vm_area failed: %i\n", err);
		goto free_vma;
	}

	/* Now the Switcher is mapped at the right address, we can't fail!
	 * Copy in the compiled-in Switcher code (from <arch>_switcher.S). */
	memcpy(switcher_vma->addr, start_switcher_text,
	       end_switcher_text - start_switcher_text);

	printk(KERN_INFO "lguest: mapped switcher at %p\n",
	       switcher_vma->addr);
	/* And we succeeded... */
	return 0;

free_vma:
	vunmap(switcher_vma->addr);
free_pages:
	i = TOTAL_SWITCHER_PAGES;
free_some_pages:
	for (--i; i >= 0; i--)
		__free_pages(switcher_page[i], 0);
	kfree(switcher_page);
out:
	return err;
}


[ drivers/lguest/x86/core.c ]
/* Now the Switcher is mapped and every thing else is ready, we need to do
 * some more i386-specific initialization. */
void __init lguest_arch_host_init(void)
{
	int i;

	/* Most of the i386/switcher.S doesn't care that it's been moved; on
	 * Intel, jumps are relative, and it doesn't access any references to
	 * external code or data.
	 *
	 * The only exception is the interrupt handlers in switcher.S: their
	 * addresses are placed in a table (default_idt_entries), so we need to
	 * update the table with the new addresses.  switcher_offset() is a
	 * convenience function which returns the distance between the builtin
	 * switcher code and the high-mapped copy we just made. */
	for (i = 0; i < IDT_ENTRIES; i++)
		default_idt_entries[i] += switcher_offset();

	/*
	 * Set up the Switcher's per-cpu areas.
	 *
	 * Each CPU gets two pages of its own within the high-mapped region
	 * (aka. "struct lguest_pages").  Much of this can be initialized now,
	 * but some depends on what Guest we are running (which is set up in
	 * copy_in_guest_info()).
	 */
	for_each_possible_cpu(i) {
		/* lguest_pages() returns this CPU's two pages. */
		struct lguest_pages *pages = lguest_pages(i);
		/* This is a convenience pointer to make the code fit one
		 * statement to a line. */
		struct lguest_ro_state *state = &pages->state;

		/* The Global Descriptor Table: the Host has a different one
		 * for each CPU.  We keep a descriptor for the GDT which says
		 * where it is and how big it is (the size is actually the last
		 * byte, not the size, hence the "-1"). */
		state->host_gdt_desc.size = GDT_SIZE-1;
		state->host_gdt_desc.address = (long)get_cpu_gdt_table(i);

		/* All CPUs on the Host use the same Interrupt Descriptor
		 * Table, so we just use store_idt(), which gets this CPU's IDT
		 * descriptor. */
		store_idt(&state->host_idt_desc);

		/* The descriptors for the Guest's GDT and IDT can be filled
		 * out now, too.  We copy the GDT & IDT into ->guest_gdt and
		 * ->guest_idt before actually running the Guest. */
		state->guest_idt_desc.size = sizeof(state->guest_idt)-1;
		state->guest_idt_desc.address = (long)&state->guest_idt;
		state->guest_gdt_desc.size = sizeof(state->guest_gdt)-1;
		state->guest_gdt_desc.address = (long)&state->guest_gdt;

		/* We know where we want the stack to be when the Guest enters
		 * the switcher: in pages->regs.  The stack grows upwards, so
		 * we start it at the end of that structure. */
		state->guest_tss.esp0 = (long)(&pages->regs + 1);
		/* And this is the GDT entry to use for the stack: we keep a
		 * couple of special LGUEST entries. */
		state->guest_tss.ss0 = LGUEST_DS;

		/* x86 can have a finegrained bitmap which indicates what I/O
		 * ports the process can use.  We set it to the end of our
		 * structure, meaning "none". */
		state->guest_tss.io_bitmap_base = sizeof(state->guest_tss);

		/* Some GDT entries are the same across all Guests, so we can
		 * set them up now. */
		setup_default_gdt_entries(state);
		/* Most IDT entries are the same for all Guests, too.*/
		setup_default_idt_entries(state, default_idt_entries);

		/* The Host needs to be able to use the LGUEST segments on this
		 * CPU, too, so put them in the Host GDT. */
		get_cpu_gdt_table(i)[GDT_ENTRY_LGUEST_CS] = FULL_EXEC_SEGMENT;
		get_cpu_gdt_table(i)[GDT_ENTRY_LGUEST_DS] = FULL_SEGMENT;
	}

	/* In the Switcher, we want the %cs segment register to use the
	 * LGUEST_CS GDT entry: we've put that in the Host and Guest GDTs, so
	 * it will be undisturbed when we switch.  To change %cs and jump we
	 * need this structure to feed to Intel's "lcall" instruction. */
	lguest_entry.offset = (long)switch_to_guest + switcher_offset();
	lguest_entry.segment = LGUEST_CS;

	/* Finally, we need to turn off "Page Global Enable".  PGE is an
	 * optimization where page table entries are specially marked to show
	 * they never change.  The Host kernel marks all the kernel pages this
	 * way because it's always present, even when userspace is running.
	 *
	 * Lguest breaks this: unbeknownst to the rest of the Host kernel, we
	 * switch to the Guest kernel.  If you don't disable this on all CPUs,
	 * you'll get really weird bugs that you'll chase for two days.
	 *
	 * I used to turn PGE off every time we switched to the Guest and back
	 * on when we return, but that slowed the Switcher down noticibly. */

	/* We don't need the complexity of CPUs coming and going while we're
	 * doing this. */
	lock_cpu_hotplug();
	if (cpu_has_pge) { /* We have a broader idea of "global". */
		/* Remember that this was originally set (for cleanup). */
		cpu_had_pge = 1;
		/* adjust_pge is a helper function which sets or unsets the PGE
		 * bit on its CPU, depending on the argument (0 == unset). */
		on_each_cpu(adjust_pge, (void *)0, 0, 1);
		/* Turn off the feature in the global feature set. */
		clear_bit(X86_FEATURE_PGE, boot_cpu_data.x86_capability);
	}
	unlock_cpu_hotplug();
};


[ drivers/lguest/core.c ]
/* Let's jump straight to the the main loop which runs the Guest.
 * Remember, this is called by the Launcher reading /dev/lguest, and we keep
 * going around and around until something interesting happens. */
int run_guest(struct lguest *lg, unsigned long __user *user)
{
	/* We stop running once the Guest is dead. */
	while (!lg->dead) {
		/* First we run any hypercalls the Guest wants done. */
		if (lg->hcall)
			do_hypercalls(lg);

		/* It's possible the Guest did a NOTIFY hypercall to the
		 * Launcher, in which case we return from the read() now. */
		if (lg->pending_notify) {
			if (put_user(lg->pending_notify, user))
				return -EFAULT;
			return sizeof(lg->pending_notify);
		}

		/* Check for signals */
		if (signal_pending(current))
			return -ERESTARTSYS;

		/* If Waker set break_out, return to Launcher. */
		if (lg->break_out)
			return -EAGAIN;

		/* Check if there are any interrupts which can be delivered
		 * now: if so, this sets up the hander to be executed when we
		 * next run the Guest. */
		maybe_do_interrupt(lg);

		/* All long-lived kernel loops need to check with this horrible
		 * thing called the freezer.  If the Host is trying to suspend,
		 * it stops us. */
		try_to_freeze();

		/* Just make absolutely sure the Guest is still alive.  One of
		 * those hypercalls could have been fatal, for example. */
		if (lg->dead)
			break;

		/* If the Guest asked to be stopped, we sleep.  The Guest's
		 * clock timer or LHCALL_BREAK from the Waker will wake us. */
		if (lg->halted) {
			set_current_state(TASK_INTERRUPTIBLE);
			schedule();
			continue;
		}

		/* OK, now we're ready to jump into the Guest.  First we put up
		 * the "Do Not Disturb" sign: */
		local_irq_disable();

		/* Actually run the Guest until something happens. */
		lguest_arch_run_guest(lg);

		/* Now we're ready to be interrupted or moved to other CPUs */
		local_irq_enable();

		/* Now we deal with whatever happened to the Guest. */
		lguest_arch_handle_trap(lg);
	}

	/* The Guest is dead => "No such file or directory" */
	return -ENOENT;
}

/*
 * Dealing With Guest Memory.
 *
 * Before we go too much further into the Host, we need to grok the routines
 * we use to deal with Guest memory.
 *
 * When the Guest gives us (what it thinks is) a physical address, we can use
 * the normal copy_from_user() & copy_to_user() on the corresponding place in
 * the memory region allocated by the Launcher.
 *
 * But we can't trust the Guest: it might be trying to access the Launcher
 * code.  We have to check that the range is below the pfn_limit the Launcher
 * gave us.  We have to make sure that addr + len doesn't give us a false
 * positive by overflowing, too. */
int lguest_address_ok(const struct lguest *lg,
		      unsigned long addr, unsigned long len)
{
	return (addr+len) / PAGE_SIZE < lg->pfn_limit && (addr+len >= addr);
}

/* This routine copies memory from the Guest.  Here we can see how useful the
 * kill_lguest() routine we met in the Launcher can be: we return a random
 * value (all zeroes) instead of needing to return an error. */
void __lgread(struct lguest *lg, void *b, unsigned long addr, unsigned bytes)
{
	if (!lguest_address_ok(lg, addr, bytes)
	    || copy_from_user(b, lg->mem_base + addr, bytes) != 0) {
		/* copy_from_user should do this, but as we rely on it... */
		memset(b, 0, bytes);
		kill_guest(lg, "bad read address %#lx len %u", addr, bytes);
	}
}

/* This is the write (copy into guest) version. */
void __lgwrite(struct lguest *lg, unsigned long addr, const void *b,
	       unsigned bytes)
{
	if (!lguest_address_ok(lg, addr, bytes)
	    || copy_to_user(lg->mem_base + addr, b, bytes) != 0)
		kill_guest(lg, "bad write address %#lx len %u", addr, bytes);
}


[ drivers/lguest/lg.h ]
/* Using memory-copy operations like that is usually inconvient, so we
 * have the following helper macros which read and write a specific type (often
 * an unsigned long).
 *
 * This reads into a variable of the given type then returns that. */
#define lgread(lg, addr, type)						\
	({ type _v; __lgread((lg), &_v, (addr), sizeof(_v)); _v; })

/* This checks that the variable is of the given type, then writes it out. */
#define lgwrite(lg, addr, type, val)				\
	do {							\
		typecheck(type, val);				\
		__lgwrite((lg), (addr), &(val), sizeof(val));	\
	} while(0)
/* (end of memory access helper routines) */

[ drivers/lguest/x86/core.c ]
/* This is the i386-specific code to setup and run the Guest.  Interrupts
 * are disabled: we own the CPU. */
void lguest_arch_run_guest(struct lguest *lg)
{
	/* Remember the awfully-named TS bit?  If the Guest has asked to set it
	 * we set it now, so we can trap and pass that trap to the Guest if it
	 * uses the FPU. */
	if (lg->ts)
		lguest_set_ts();

	/* SYSENTER is an optimized way of doing system calls.  We can't allow
	 * it because it always jumps to privilege level 0.  A normal Guest
	 * won't try it because we don't advertise it in CPUID, but a malicious
	 * Guest (or malicious Guest userspace program) could, so we tell the
	 * CPU to disable it before running the Guest. */
	if (boot_cpu_has(X86_FEATURE_SEP))
		wrmsr(MSR_IA32_SYSENTER_CS, 0, 0);

	/* Now we actually run the Guest.  It will return when something
	 * interesting happens, and we can examine its registers to see what it
	 * was doing. */
	run_guest_once(lg, lguest_pages(raw_smp_processor_id()));

	/* Note that the "regs" pointer contains two extra entries which are
	 * not really registers: a trap number which says what interrupt or
	 * trap made the switcher code come back, and an error code which some
	 * traps set.  */

	/* If the Guest page faulted, then the cr2 register will tell us the
	 * bad virtual address.  We have to grab this now, because once we
	 * re-enable interrupts an interrupt could fault and thus overwrite
	 * cr2, or we could even move off to a different CPU. */
	if (lg->regs->trapnum == 14)
		lg->arch.last_pagefault = read_cr2();
	/* Similarly, if we took a trap because the Guest used the FPU,
	 * we have to restore the FPU it expects to see. */
	else if (lg->regs->trapnum == 7)
		math_state_restore();

	/* Restore SYSENTER if it's supposed to be on. */
	if (boot_cpu_has(X86_FEATURE_SEP))
		wrmsr(MSR_IA32_SYSENTER_CS, __KERNEL_CS, 0);
}

/* Once we've re-enabled interrupts, we look at why the Guest exited. */
void lguest_arch_handle_trap(struct lguest *lg)
{
	switch (lg->regs->trapnum) {
	case 13: /* We've intercepted a General Protection Fault. */
		/* Check if this was one of those annoying IN or OUT
		 * instructions which we need to emulate.  If so, we just go
		 * back into the Guest after we've done it. */
		if (lg->regs->errcode == 0) {
			if (emulate_insn(lg))
				return;
		}
		break;
	case 14: /* We've intercepted a Page Fault. */
		/* The Guest accessed a virtual address that wasn't mapped.
		 * This happens a lot: we don't actually set up most of the
		 * page tables for the Guest at all when we start: as it runs
		 * it asks for more and more, and we set them up as
		 * required. In this case, we don't even tell the Guest that
		 * the fault happened.
		 *
		 * The errcode tells whether this was a read or a write, and
		 * whether kernel or userspace code. */
		if (demand_page(lg, lg->arch.last_pagefault, lg->regs->errcode))
			return;

		/* OK, it's really not there (or not OK): the Guest needs to
		 * know.  We write out the cr2 value so it knows where the
		 * fault occurred.
		 *
		 * Note that if the Guest were really messed up, this could
		 * happen before it's done the LHCALL_LGUEST_INIT hypercall, so
		 * lg->lguest_data could be NULL */
		if (lg->lguest_data &&
		    put_user(lg->arch.last_pagefault, &lg->lguest_data->cr2))
			kill_guest(lg, "Writing cr2");
		break;
	case 7: /* We've intercepted a Device Not Available fault. */
		/* If the Guest doesn't want to know, we already restored the
		 * Floating Point Unit, so we just continue without telling
		 * it. */
		if (!lg->ts)
			return;
		break;
	case 32 ... 255:
		/* These values mean a real interrupt occurred, in which case
		 * the Host handler has already been run.  We just do a
		 * friendly check if another process should now be run, then
		 * return to run the Guest again */
		cond_resched();
		return;
	case LGUEST_TRAP_ENTRY:
		/* Our 'struct hcall_args' maps directly over our regs: we set
		 * up the pointer now to indicate a hypercall is pending. */
		lg->hcall = (struct hcall_args *)lg->regs;
		return;
	}

	/* We didn't handle the trap, so it needs to go to the Guest. */
	if (!deliver_trap(lg, lg->regs->trapnum))
		/* If the Guest doesn't have a handler (either it hasn't
		 * registered any yet, or it's one of the faults we don't let
		 * it handle), it dies with a cryptic error message. */
		kill_guest(lg, "unhandled trap %li at %#lx (%#lx)",
			   lg->regs->trapnum, lg->regs->eip,
			   lg->regs->trapnum == 14 ? lg->arch.last_pagefault
			   : lg->regs->errcode);
}

/* Now we can look at each of the routines this calls, in increasing order of
 * complexity: do_hypercalls(), emulate_insn(), maybe_do_interrupt(),
 * deliver_trap() and demand_page().  After all those, we'll be ready to
 * examine the Switcher, and our philosophical understanding of the Host/Guest
 * duality will be complete. */

[ drivers/lguest/hypercalls.c ]
/*
 * Hypercalls
 *
 * Remember from the Guest, hypercalls come in two flavors: normal and
 * asynchronous.  This file handles both of types.
 */
void do_hypercalls(struct lguest *lg)
{
	/* Not initialized yet?  This hypercall must do it. */
	if (unlikely(!lg->lguest_data)) {
		/* Set up the "struct lguest_data" */
		initialize(lg);
		/* Hcall is done. */
		lg->hcall = NULL;
		return;
	}

	/* The Guest has initialized.
	 *
	 * Look in the hypercall ring for the async hypercalls: */
	do_async_hcalls(lg);

	/* If we stopped reading the hypercall ring because the Guest did a
	 * NOTIFY to the Launcher, we want to return now.  Otherwise we do
	 * the hypercall. */
	if (!lg->pending_notify) {
		do_hcall(lg, lg->hcall);
		/* Tricky point: we reset the hcall pointer to mark the
		 * hypercall as "done".  We use the hcall pointer rather than
		 * the trap number to indicate a hypercall is pending.
		 * Normally it doesn't matter: the Guest will run again and
		 * update the trap number before we come back here.
		 *
		 * However, if we are signalled or the Guest sends I/O to the
		 * Launcher, the run_guest() loop will exit without running the
		 * Guest.  When it comes back it would try to re-run the
		 * hypercall. */
		lg->hcall = NULL;
	}
}

/* This routine supplies the Guest with time: it's used for wallclock time at
 * initial boot and as a rough time source if the TSC isn't available. */
void write_timestamp(struct lguest *lg)
{
	struct timespec now;
	ktime_get_real_ts(&now);
	if (copy_to_user(&lg->lguest_data->time, &now, sizeof(struct timespec)))
		kill_guest(lg, "Writing timestamp");
}

/* This is the core hypercall routine: where the Guest gets what it wants.
 * Or gets killed.  Or, in the case of LHCALL_CRASH, both. */
static void do_hcall(struct lguest *lg, struct hcall_args *args)
{
	switch (args->arg0) {
	case LHCALL_FLUSH_ASYNC:
		/* This call does nothing, except by breaking out of the Guest
		 * it makes us process all the asynchronous hypercalls. */
		break;
	case LHCALL_LGUEST_INIT:
		/* You can't get here unless you're already initialized.  Don't
		 * do that. */
		kill_guest(lg, "already have lguest_data");
		break;
	case LHCALL_CRASH: {
		/* Crash is such a trivial hypercall that we do it in four
		 * lines right here. */
		char msg[128];
		/* If the lgread fails, it will call kill_guest() itself; the
		 * kill_guest() with the message will be ignored. */
		__lgread(lg, msg, args->arg1, sizeof(msg));
		msg[sizeof(msg)-1] = '\0';
		kill_guest(lg, "CRASH: %s", msg);
		break;
	}
	case LHCALL_FLUSH_TLB:
		/* FLUSH_TLB comes in two flavors, depending on the
		 * argument: */
		if (args->arg1)
			guest_pagetable_clear_all(lg);
		else
			guest_pagetable_flush_user(lg);
		break;

	/* All these calls simply pass the arguments through to the right
	 * routines. */
	case LHCALL_NEW_PGTABLE:
		guest_new_pagetable(lg, args->arg1);
		break;
	case LHCALL_SET_STACK:
		guest_set_stack(lg, args->arg1, args->arg2, args->arg3);
		break;
	case LHCALL_SET_PTE:
		guest_set_pte(lg, args->arg1, args->arg2, __pte(args->arg3));
		break;
	case LHCALL_SET_PMD:
		guest_set_pmd(lg, args->arg1, args->arg2);
		break;
	case LHCALL_SET_CLOCKEVENT:
		guest_set_clockevent(lg, args->arg1);
		break;
	case LHCALL_TS:
		/* This sets the TS flag, as we saw used in run_guest(). */
		lg->ts = args->arg1;
		break;
	case LHCALL_HALT:
		/* Similarly, this sets the halted flag for run_guest(). */
		lg->halted = 1;
		break;
	case LHCALL_NOTIFY:
		lg->pending_notify = args->arg1;
		break;
	default:
		/* It should be an architecture-specific hypercall. */
		if (lguest_arch_do_hcall(lg, args))
			kill_guest(lg, "Bad hypercall %li\n", args->arg0);
	}
}


[ drivers/lguest/x86/core.c ]
/* The i386-specific hypercalls simply farm out to the right functions. */
int lguest_arch_do_hcall(struct lguest *lg, struct hcall_args *args)
{
	switch (args->arg0) {
	case LHCALL_LOAD_GDT:
		load_guest_gdt(lg, args->arg1, args->arg2);
		break;
	case LHCALL_LOAD_IDT_ENTRY:
		load_guest_idt_entry(lg, args->arg1, args->arg2, args->arg3);
		break;
	case LHCALL_LOAD_TLS:
		guest_load_tls(lg, args->arg1);
		break;
	default:
		/* Bad Guest.  Bad! */
		return -EIO;
	}
	return 0;
}

[ drivers/lguest/hypercalls.c ]
/* Asynchronous hypercalls are easy: we just look in the array in the
 * Guest's "struct lguest_data" to see if any new ones are marked "ready".
 *
 * We are careful to do these in order: obviously we respect the order the
 * Guest put them in the ring, but we also promise the Guest that they will
 * happen before any normal hypercall (which is why we check this before
 * checking for a normal hcall). */
static void do_async_hcalls(struct lguest *lg)
{
	unsigned int i;
	u8 st[LHCALL_RING_SIZE];

	/* For simplicity, we copy the entire call status array in at once. */
	if (copy_from_user(&st, &lg->lguest_data->hcall_status, sizeof(st)))
		return;

	/* We process "struct lguest_data"s hcalls[] ring once. */
	for (i = 0; i < ARRAY_SIZE(st); i++) {
		struct hcall_args args;
		/* We remember where we were up to from last time.  This makes
		 * sure that the hypercalls are done in the order the Guest
		 * places them in the ring. */
		unsigned int n = lg->next_hcall;

		/* 0xFF means there's no call here (yet). */
		if (st[n] == 0xFF)
			break;

		/* OK, we have hypercall.  Increment the "next_hcall" cursor,
		 * and wrap back to 0 if we reach the end. */
		if (++lg->next_hcall == LHCALL_RING_SIZE)
			lg->next_hcall = 0;

		/* Copy the hypercall arguments into a local copy of
		 * the hcall_args struct. */
		if (copy_from_user(&args, &lg->lguest_data->hcalls[n],
				   sizeof(struct hcall_args))) {
			kill_guest(lg, "Fetching async hypercalls");
			break;
		}

		/* Do the hypercall, same as a normal one. */
		do_hcall(lg, &args);

		/* Mark the hypercall done. */
		if (put_user(0xFF, &lg->lguest_data->hcall_status[n])) {
			kill_guest(lg, "Writing result for async hypercall");
			break;
		}

		/* Stop doing hypercalls if they want to notify the Launcher:
		 * it needs to service this first. */
		if (lg->pending_notify)
			break;
	}
}

/* Last of all, we look at what happens first of all.  The very first time the
 * Guest makes a hypercall, we end up here to set things up: */
static void initialize(struct lguest *lg)
{
	/* You can't do anything until you're initialized.  The Guest knows the
	 * rules, so we're unforgiving here. */
	if (lg->hcall->arg0 != LHCALL_LGUEST_INIT) {
		kill_guest(lg, "hypercall %li before INIT", lg->hcall->arg0);
		return;
	}

	if (lguest_arch_init_hypercalls(lg))
		kill_guest(lg, "bad guest page %p", lg->lguest_data);

	/* The Guest tells us where we're not to deliver interrupts by putting
	 * the range of addresses into "struct lguest_data". */
	if (get_user(lg->noirq_start, &lg->lguest_data->noirq_start)
	    || get_user(lg->noirq_end, &lg->lguest_data->noirq_end))
		kill_guest(lg, "bad guest page %p", lg->lguest_data);

	/* We write the current time into the Guest's data page once so it can
	 * set its clock. */
	write_timestamp(lg);

	/* page_tables.c will also do some setup. */
	page_table_guest_data_init(lg);

	/* This is the one case where the above accesses might have been the
	 * first write to a Guest page.  This may have caused a copy-on-write
	 * fault, but the old page might be (read-only) in the Guest
	 * pagetable. */
	guest_pagetable_clear_all(lg);
}

[ drivers/lguest/x86/core.c ]
/* i386-specific hypercall initialization: */
int lguest_arch_init_hypercalls(struct lguest *lg)
{
	u32 tsc_speed;

	/* The pointer to the Guest's "struct lguest_data" is the only
	 * argument.  We check that address now. */
	if (!lguest_address_ok(lg, lg->hcall->arg1, sizeof(*lg->lguest_data)))
		return -EFAULT;

	/* Having checked it, we simply set lg->lguest_data to point straight
	 * into the Launcher's memory at the right place and then use
	 * copy_to_user/from_user from now on, instead of lgread/write.  I put
	 * this in to show that I'm not immune to writing stupid
	 * optimizations. */
	lg->lguest_data = lg->mem_base + lg->hcall->arg1;

	/* We insist that the Time Stamp Counter exist and doesn't change with
	 * cpu frequency.  Some devious chip manufacturers decided that TSC
	 * changes could be handled in software.  I decided that time going
	 * backwards might be good for benchmarks, but it's bad for users.
	 *
	 * We also insist that the TSC be stable: the kernel detects unreliable
	 * TSCs for its own purposes, and we use that here. */
	if (boot_cpu_has(X86_FEATURE_CONSTANT_TSC) && !check_tsc_unstable())
		tsc_speed = tsc_khz;
	else
		tsc_speed = 0;
	if (put_user(tsc_speed, &lg->lguest_data->tsc_khz))
		return -EFAULT;

	/* The interrupt code might not like the system call vector. */
	if (!check_syscall_vector(lg))
		kill_guest(lg, "bad syscall vector");

	return 0;
}

/*L:030 lguest_arch_setup_regs()
 *
 * Most of the Guest's registers are left alone: we used get_zeroed_page() to
 * allocate the structure, so they will be 0. */
void lguest_arch_setup_regs(struct lguest *lg, unsigned long start)
{
	struct lguest_regs *regs = lg->regs;

	/* There are four "segment" registers which the Guest needs to boot:
	 * The "code segment" register (cs) refers to the kernel code segment
	 * __KERNEL_CS, and the "data", "extra" and "stack" segment registers
	 * refer to the kernel data segment __KERNEL_DS.
	 *
	 * The privilege level is packed into the lower bits.  The Guest runs
	 * at privilege level 1 (GUEST_PL).*/
	regs->ds = regs->es = regs->ss = __KERNEL_DS|GUEST_PL;
	regs->cs = __KERNEL_CS|GUEST_PL;

	/* The "eflags" register contains miscellaneous flags.  Bit 1 (0x002)
	 * is supposed to always be "1".  Bit 9 (0x200) controls whether
	 * interrupts are enabled.  We always leave interrupts enabled while
	 * running the Guest. */
	regs->eflags = X86_EFLAGS_IF | 0x2;

	/* The "Extended Instruction Pointer" register says where the Guest is
	 * running. */
	regs->eip = start;

	/* %esi points to our boot information, at physical address 0, so don't
	 * touch it. */

	/* There are a couple of GDT entries the Guest expects when first
	 * booting. */
	setup_guest_gdt(lg);
}

/* Now we've examined the hypercall code; our Guest can make requests.
 * Our Guest is usually so well behaved; it never tries to do things it isn't
 * allowed to, and uses hypercalls instead.  Unfortunately, Linux's paravirtual
 * infrastructure isn't quite complete, because it doesn't contain replacements
 * for the Intel I/O instructions.  As a result, the Guest sometimes fumbles
 * across one during the boot process as it probes for various things which are
 * usually attached to a PC.
 *
 * When the Guest uses one of these instructions, we get a trap (General
 * Protection Fault) and come here.  We see if it's one of those troublesome
 * instructions and skip over it.  We return true if we did. */
static int emulate_insn(struct lguest *lg)
{
	u8 insn;
	unsigned int insnlen = 0, in = 0, shift = 0;
	/* The eip contains the *virtual* address of the Guest's instruction:
	 * guest_pa just subtracts the Guest's page_offset. */
	unsigned long physaddr = guest_pa(lg, lg->regs->eip);

	/* This must be the Guest kernel trying to do something, not userspace!
	 * The bottom two bits of the CS segment register are the privilege
	 * level. */
	if ((lg->regs->cs & 3) != GUEST_PL)
		return 0;

	/* Decoding x86 instructions is icky. */
	insn = lgread(lg, physaddr, u8);

	/* 0x66 is an "operand prefix".  It means it's using the upper 16 bits
	   of the eax register. */
	if (insn == 0x66) {
		shift = 16;
		/* The instruction is 1 byte so far, read the next byte. */
		insnlen = 1;
		insn = lgread(lg, physaddr + insnlen, u8);
	}

	/* We can ignore the lower bit for the moment and decode the 4 opcodes
	 * we need to emulate. */
	switch (insn & 0xFE) {
	case 0xE4: /* in     <next byte>,%al */
		insnlen += 2;
		in = 1;
		break;
	case 0xEC: /* in     (%dx),%al */
		insnlen += 1;
		in = 1;
		break;
	case 0xE6: /* out    %al,<next byte> */
		insnlen += 2;
		break;
	case 0xEE: /* out    %al,(%dx) */
		insnlen += 1;
		break;
	default:
		/* OK, we don't know what this is, can't emulate. */
		return 0;
	}

	/* If it was an "IN" instruction, they expect the result to be read
	 * into %eax, so we change %eax.  We always return all-ones, which
	 * traditionally means "there's nothing there". */
	if (in) {
		/* Lower bit tells is whether it's a 16 or 32 bit access */
		if (insn & 0x1)
			lg->regs->eax = 0xFFFFFFFF;
		else
			lg->regs->eax |= (0xFFFF << shift);
	}
	/* Finally, we've "done" the instruction, so move past it. */
	lg->regs->eip += insnlen;
	/* Success! */
	return 1;
}

[ drivers/lguest/interrupts_and_traps.c ]
/*
 * The Guest Clock.
 *
 * There are two sources of virtual interrupts.  We saw one in lguest_user.c:
 * the Launcher sending interrupts for virtual devices.  The other is the Guest
 * timer interrupt.
 *
 * The Guest uses the LHCALL_SET_CLOCKEVENT hypercall to tell us how long to
 * the next timer interrupt (in nanoseconds).  We use the high-resolution timer
 * infrastructure to set a callback at that time.
 *
 * 0 means "turn off the clock". */
void guest_set_clockevent(struct lguest *lg, unsigned long delta)
{
	ktime_t expires;

	if (unlikely(delta == 0)) {
		/* Clock event device is shutting down. */
		hrtimer_cancel(&lg->hrt);
		return;
	}

	/* We use wallclock time here, so the Guest might not be running for
	 * all the time between now and the timer interrupt it asked for.  This
	 * is almost always the right thing to do. */
	expires = ktime_add_ns(ktime_get_real(), delta);
	hrtimer_start(&lg->hrt, expires, HRTIMER_MODE_ABS);
}

/* This is the function called when the Guest's timer expires. */
static enum hrtimer_restart clockdev_fn(struct hrtimer *timer)
{
	struct lguest *lg = container_of(timer, struct lguest, hrt);

	/* Remember the first interrupt is the timer interrupt. */
	set_bit(0, lg->irqs_pending);
	/* If the Guest is actually stopped, we need to wake it up. */
	if (lg->halted)
		wake_up_process(lg->tsk);
	return HRTIMER_NORESTART;
}

/* This sets up the timer for this Guest. */
void init_clockdev(struct lguest *lg)
{
	hrtimer_init(&lg->hrt, CLOCK_REALTIME, HRTIMER_MODE_ABS);
	lg->hrt.function = clockdev_fn;
}

/*
 * Virtual Interrupts.
 *
 * maybe_do_interrupt() gets called before every entry to the Guest, to see if
 * we should divert the Guest to running an interrupt handler. */
void maybe_do_interrupt(struct lguest *lg)
{
	unsigned int irq;
	DECLARE_BITMAP(blk, LGUEST_IRQS);
	struct desc_struct *idt;

	/* If the Guest hasn't even initialized yet, we can do nothing. */
	if (!lg->lguest_data)
		return;

	/* Take our "irqs_pending" array and remove any interrupts the Guest
	 * wants blocked: the result ends up in "blk". */
	if (copy_from_user(&blk, lg->lguest_data->blocked_interrupts,
			   sizeof(blk)))
		return;

	bitmap_andnot(blk, lg->irqs_pending, blk, LGUEST_IRQS);

	/* Find the first interrupt. */
	irq = find_first_bit(blk, LGUEST_IRQS);
	/* None?  Nothing to do */
	if (irq >= LGUEST_IRQS)
		return;

	/* They may be in the middle of an iret, where they asked us never to
	 * deliver interrupts. */
	if (lg->regs->eip >= lg->noirq_start && lg->regs->eip < lg->noirq_end)
		return;

	/* If they're halted, interrupts restart them. */
	if (lg->halted) {
		/* Re-enable interrupts. */
		if (put_user(X86_EFLAGS_IF, &lg->lguest_data->irq_enabled))
			kill_guest(lg, "Re-enabling interrupts");
		lg->halted = 0;
	} else {
		/* Otherwise we check if they have interrupts disabled. */
		u32 irq_enabled;
		if (get_user(irq_enabled, &lg->lguest_data->irq_enabled))
			irq_enabled = 0;
		if (!irq_enabled)
			return;
	}

	/* Look at the IDT entry the Guest gave us for this interrupt.  The
	 * first 32 (FIRST_EXTERNAL_VECTOR) entries are for traps, so we skip
	 * over them. */
	idt = &lg->arch.idt[FIRST_EXTERNAL_VECTOR+irq];
	/* If they don't have a handler (yet?), we just ignore it */
	if (idt_present(idt->a, idt->b)) {
		/* OK, mark it no longer pending and deliver it. */
		clear_bit(irq, lg->irqs_pending);
		/* set_guest_interrupt() takes the interrupt descriptor and a
		 * flag to say whether this interrupt pushes an error code onto
		 * the stack as well: virtual interrupts never do. */
		set_guest_interrupt(lg, idt->a, idt->b, 0);
	}

	/* Every time we deliver an interrupt, we update the timestamp in the
	 * Guest's lguest_data struct.  It would be better for the Guest if we
	 * did this more often, but it can actually be quite slow: doing it
	 * here is a compromise which means at least it gets updated every
	 * timer interrupt. */
	write_timestamp(lg);
}


/* The set_guest_interrupt() routine actually delivers the interrupt or
 * trap.  The mechanics of delivering traps and interrupts to the Guest are the
 * same, except some traps have an "error code" which gets pushed onto the
 * stack as well: the caller tells us if this is one.
 *
 * "lo" and "hi" are the two parts of the Interrupt Descriptor Table for this
 * interrupt or trap.  It's split into two parts for traditional reasons: gcc
 * on i386 used to be frightened by 64 bit numbers.
 *
 * We set up the stack just like the CPU does for a real interrupt, so it's
 * identical for the Guest (and the standard "iret" instruction will undo
 * it). */
static void set_guest_interrupt(struct lguest *lg, u32 lo, u32 hi, int has_err)
{
	unsigned long gstack, origstack;
	u32 eflags, ss, irq_enable;
	unsigned long virtstack;

	/* There are two cases for interrupts: one where the Guest is already
	 * in the kernel, and a more complex one where the Guest is in
	 * userspace.  We check the privilege level to find out. */
	if ((lg->regs->ss&0x3) != GUEST_PL) {
		/* The Guest told us their kernel stack with the SET_STACK
		 * hypercall: both the virtual address and the segment */
		virtstack = lg->esp1;
		ss = lg->ss1;

		origstack = gstack = guest_pa(lg, virtstack);
		/* We push the old stack segment and pointer onto the new
		 * stack: when the Guest does an "iret" back from the interrupt
		 * handler the CPU will notice they're dropping privilege
		 * levels and expect these here. */
		push_guest_stack(lg, &gstack, lg->regs->ss);
		push_guest_stack(lg, &gstack, lg->regs->esp);
	} else {
		/* We're staying on the same Guest (kernel) stack. */
		virtstack = lg->regs->esp;
		ss = lg->regs->ss;

		origstack = gstack = guest_pa(lg, virtstack);
	}

	/* Remember that we never let the Guest actually disable interrupts, so
	 * the "Interrupt Flag" bit is always set.  We copy that bit from the
	 * Guest's "irq_enabled" field into the eflags word: we saw the Guest
	 * copy it back in "lguest_iret". */
	eflags = lg->regs->eflags;
	if (get_user(irq_enable, &lg->lguest_data->irq_enabled) == 0
	    && !(irq_enable & X86_EFLAGS_IF))
		eflags &= ~X86_EFLAGS_IF;

	/* An interrupt is expected to push three things on the stack: the old
	 * "eflags" word, the old code segment, and the old instruction
	 * pointer. */
	push_guest_stack(lg, &gstack, eflags);
	push_guest_stack(lg, &gstack, lg->regs->cs);
	push_guest_stack(lg, &gstack, lg->regs->eip);

	/* For the six traps which supply an error code, we push that, too. */
	if (has_err)
		push_guest_stack(lg, &gstack, lg->regs->errcode);

	/* Now we've pushed all the old state, we change the stack, the code
	 * segment and the address to execute. */
	lg->regs->ss = ss;
	lg->regs->esp = virtstack + (gstack - origstack);
	lg->regs->cs = (__KERNEL_CS|GUEST_PL);
	lg->regs->eip = idt_address(lo, hi);

	/* There are two kinds of interrupt handlers: 0xE is an "interrupt
	 * gate" which expects interrupts to be disabled on entry. */
	if (idt_type(lo, hi) == 0xE)
		if (put_user(0, &lg->lguest_data->irq_enabled))
			kill_guest(lg, "Disabling interrupts");
}

/* Now we've got the routines to deliver interrupts, delivering traps
 * like page fault is easy.  The only trick is that Intel decided that some
 * traps should have error codes: */
static int has_err(unsigned int trap)
{
	return (trap == 8 || (trap >= 10 && trap <= 14) || trap == 17);
}

/* deliver_trap() returns true if it could deliver the trap. */
int deliver_trap(struct lguest *lg, unsigned int num)
{
	/* Trap numbers are always 8 bit, but we set an impossible trap number
	 * for traps inside the Switcher, so check that here. */
	if (num >= ARRAY_SIZE(lg->arch.idt))
		return 0;

	/* Early on the Guest hasn't set the IDT entries (or maybe it put a
	 * bogus one in): if we fail here, the Guest will be killed. */
	if (!idt_present(lg->arch.idt[num].a, lg->arch.idt[num].b))
		return 0;
	set_guest_interrupt(lg, lg->arch.idt[num].a, lg->arch.idt[num].b,
			    has_err(num));
	return 1;
}

/* While we're here, dealing with delivering traps and interrupts to the
 * Guest, we might as well complete the picture: how the Guest tells us where
 * it wants them to go.  This would be simple, except making traps fast
 * requires some tricks.
 *
 * We saw the Guest setting Interrupt Descriptor Table (IDT) entries with the
 * LHCALL_LOAD_IDT_ENTRY hypercall before: that comes here. */
void load_guest_idt_entry(struct lguest *lg, unsigned int num, u32 lo, u32 hi)
{
	/* Guest never handles: NMI, doublefault, spurious interrupt or
	 * hypercall.  We ignore when it tries to set them. */
	if (num == 2 || num == 8 || num == 15 || num == LGUEST_TRAP_ENTRY)
		return;

	/* Mark the IDT as changed: next time the Guest runs we'll know we have
	 * to copy this again. */
	lg->changed |= CHANGED_IDT;

	/* Check that the Guest doesn't try to step outside the bounds. */
	if (num >= ARRAY_SIZE(lg->arch.idt))
		kill_guest(lg, "Setting idt entry %u", num);
	else
		set_trap(lg, &lg->arch.idt[num], num, lo, hi);
}

/* The default entry for each interrupt points into the Switcher routines which
 * simply return to the Host.  The run_guest() loop will then call
 * deliver_trap() to bounce it back into the Guest. */
static void default_idt_entry(struct desc_struct *idt,
			      int trap,
			      const unsigned long handler)
{
	/* A present interrupt gate. */
	u32 flags = 0x8e00;

	/* Set the privilege level on the entry for the hypercall: this allows
	 * the Guest to use the "int" instruction to trigger it. */
	if (trap == LGUEST_TRAP_ENTRY)
		flags |= (GUEST_PL << 13);

	/* Now pack it into the IDT entry in its weird format. */
	idt->a = (LGUEST_CS<<16) | (handler&0x0000FFFF);
	idt->b = (handler&0xFFFF0000) | flags;
}

/* When the Guest first starts, we put default entries into the IDT. */
void setup_default_idt_entries(struct lguest_ro_state *state,
			       const unsigned long *def)
{
	unsigned int i;

	for (i = 0; i < ARRAY_SIZE(state->guest_idt); i++)
		default_idt_entry(&state->guest_idt[i], i, def[i]);
}

/* This is the routine which actually checks the Guest's IDT entry and
 * transfers it into the entry in "struct lguest": */
static void set_trap(struct lguest *lg, struct desc_struct *trap,
		     unsigned int num, u32 lo, u32 hi)
{
	u8 type = idt_type(lo, hi);

	/* We zero-out a not-present entry */
	if (!idt_present(lo, hi)) {
		trap->a = trap->b = 0;
		return;
	}

	/* We only support interrupt and trap gates. */
	if (type != 0xE && type != 0xF)
		kill_guest(lg, "bad IDT type %i", type);

	/* We only copy the handler address, present bit, privilege level and
	 * type.  The privilege level controls where the trap can be triggered
	 * manually with an "int" instruction.  This is usually GUEST_PL,
	 * except for system calls which userspace can use. */
	trap->a = ((__KERNEL_CS|GUEST_PL)<<16) | (lo&0x0000FFFF);
	trap->b = (hi&0xFFFFEF00);
}

/* We don't use the IDT entries in the "struct lguest" directly, instead
 * we copy them into the IDT which we've set up for Guests on this CPU, just
 * before we run the Guest.  This routine does that copy. */
void copy_traps(const struct lguest *lg, struct desc_struct *idt,
		const unsigned long *def)
{
	unsigned int i;

	/* We can simply copy the direct traps, otherwise we use the default
	 * ones in the Switcher: they will return to the Host. */
	for (i = 0; i < ARRAY_SIZE(lg->arch.idt); i++) {
		/* If no Guest can ever override this trap, leave it alone. */
		if (!direct_trap(i))
			continue;

		/* Only trap gates (type 15) can go direct to the Guest.
		 * Interrupt gates (type 14) disable interrupts as they are
		 * entered, which we never let the Guest do.  Not present
		 * entries (type 0x0) also can't go direct, of course. */
		if (idt_type(lg->arch.idt[i].a, lg->arch.idt[i].b) == 0xF)
			idt[i] = lg->arch.idt[i];
		else
			/* Reset it to the default. */
			default_idt_entry(&idt[i], i, def[i]);
	}
}

/* Here's the hard part: returning to the Host every time a trap happens
 * and then calling deliver_trap() and re-entering the Guest is slow.
 * Particularly because Guest userspace system calls are traps (usually trap
 * 128).
 *
 * So we'd like to set up the IDT to tell the CPU to deliver traps directly
 * into the Guest.  This is possible, but the complexities cause the size of
 * this file to double!  However, 150 lines of code is worth writing for taking
 * system calls down from 1750ns to 270ns.  Plus, if lguest didn't do it, all
 * the other hypervisors would beat it up at lunchtime.
 *
 * This routine indicates if a particular trap number could be delivered
 * directly. */
static int direct_trap(unsigned int num)
{
	/* Hardware interrupts don't go to the Guest at all (except system
	 * call). */
	if (num >= FIRST_EXTERNAL_VECTOR && !could_be_syscall(num))
		return 0;

	/* The Host needs to see page faults (for shadow paging and to save the
	 * fault address), general protection faults (in/out emulation) and
	 * device not available (TS handling), and of course, the hypercall
	 * trap. */
	return num != 14 && num != 13 && num != 7 && num != LGUEST_TRAP_ENTRY;
}


/* When we make traps go directly into the Guest, we need to make sure
 * the kernel stack is valid (ie. mapped in the page tables).  Otherwise, the
 * CPU trying to deliver the trap will fault while trying to push the interrupt
 * words on the stack: this is called a double fault, and it forces us to kill
 * the Guest.
 *
 * Which is deeply unfair, because (literally!) it wasn't the Guests' fault. */
void pin_stack_pages(struct lguest *lg)
{
	unsigned int i;

	/* Depending on the CONFIG_4KSTACKS option, the Guest can have one or
	 * two pages of stack space. */
	for (i = 0; i < lg->stack_pages; i++)
		/* The stack grows *upwards*, so the address we're given is the
		 * start of the page after the kernel stack.  Subtract one to
		 * get back onto the first stack page, and keep subtracting to
		 * get to the rest of the stack pages. */
		pin_page(lg, lg->esp1 - 1 - i * PAGE_SIZE);
}

/* Direct traps also mean that we need to know whenever the Guest wants to use
 * a different kernel stack, so we can change the IDT entries to use that
 * stack.  The IDT entries expect a virtual address, so unlike most addresses
 * the Guest gives us, the "esp" (stack pointer) value here is virtual, not
 * physical.
 *
 * In Linux each process has its own kernel stack, so this happens a lot: we
 * change stacks on each context switch. */
void guest_set_stack(struct lguest *lg, u32 seg, u32 esp, unsigned int pages)
{
	/* You are not allowed have a stack segment with privilege level 0: bad
	 * Guest! */
	if ((seg & 0x3) != GUEST_PL)
		kill_guest(lg, "bad stack segment %i", seg);
	/* We only expect one or two stack pages. */
	if (pages > 2)
		kill_guest(lg, "bad stack pages %u", pages);
	/* Save where the stack is, and how many pages */
	lg->ss1 = seg;
	lg->esp1 = esp;
	lg->stack_pages = pages;
	/* Make sure the new stack pages are mapped */
	pin_stack_pages(lg);
}

/* All this reference to mapping stacks leads us neatly into the other complex
 * part of the Host: page table handling. */

[ drivers/lguest/page_tables.c ]
/*
 * The Page Table Code
 *
 * We use two-level page tables for the Guest.  If you're not entirely
 * comfortable with virtual addresses, physical addresses and page tables then
 * I recommend you review arch/x86/lguest/boot.c's "Page Table Handling" (with
 * diagrams!).
 *
 * The Guest keeps page tables, but we maintain the actual ones here: these are
 * called "shadow" page tables.  Which is a very Guest-centric name: these are
 * the real page tables the CPU uses, although we keep them up to date to
 * reflect the Guest's.  (See what I mean about weird naming?  Since when do
 * shadows reflect anything?)
 *
 * Anyway, this is the most complicated part of the Host code.  There are seven
 * parts to this:
 *  (i) Looking up a page table entry when the Guest faults,
 *  (ii) Making sure the Guest stack is mapped,
 *  (iii) Setting up a page table entry when the Guest tells us one has changed,
 *  (iv) Switching page tables,
 *  (v) Flushing (throwing away) page tables,
 *  (vi) Mapping the Switcher when the Guest is about to run,
 *  (vii) Setting up the page tables initially.
 */

/* The page table code is curly enough to need helper functions to keep it
 * clear and clean.
 *
 * There are two functions which return pointers to the shadow (aka "real")
 * page tables.
 *
 * spgd_addr() takes the virtual address and returns a pointer to the top-level
 * page directory entry (PGD) for that address.  Since we keep track of several
 * page tables, the "i" argument tells us which one we're interested in (it's
 * usually the current one). */
static pgd_t *spgd_addr(struct lguest *lg, u32 i, unsigned long vaddr)
{
	unsigned int index = pgd_index(vaddr);

	/* We kill any Guest trying to touch the Switcher addresses. */
	if (index >= SWITCHER_PGD_INDEX) {
		kill_guest(lg, "attempt to access switcher pages");
		index = 0;
	}
	/* Return a pointer index'th pgd entry for the i'th page table. */
	return &lg->pgdirs[i].pgdir[index];
}

/* This routine then takes the page directory entry returned above, which
 * contains the address of the page table entry (PTE) page.  It then returns a
 * pointer to the PTE entry for the given address. */
static pte_t *spte_addr(struct lguest *lg, pgd_t spgd, unsigned long vaddr)
{
	pte_t *page = __va(pgd_pfn(spgd) << PAGE_SHIFT);
	/* You should never call this if the PGD entry wasn't valid */
	BUG_ON(!(pgd_flags(spgd) & _PAGE_PRESENT));
	return &page[(vaddr >> PAGE_SHIFT) % PTRS_PER_PTE];
}

/* These two functions just like the above two, except they access the Guest
 * page tables.  Hence they return a Guest address. */
static unsigned long gpgd_addr(struct lguest *lg, unsigned long vaddr)
{
	unsigned int index = vaddr >> (PGDIR_SHIFT);
	return lg->pgdirs[lg->pgdidx].gpgdir + index * sizeof(pgd_t);
}

static unsigned long gpte_addr(struct lguest *lg,
			       pgd_t gpgd, unsigned long vaddr)
{
	unsigned long gpage = pgd_pfn(gpgd) << PAGE_SHIFT;
	BUG_ON(!(pgd_flags(gpgd) & _PAGE_PRESENT));
	return gpage + ((vaddr>>PAGE_SHIFT) % PTRS_PER_PTE) * sizeof(pte_t);
}

/*
 * (i) Looking up a page table entry when the Guest faults.
 *
 * We saw this call in run_guest(): when we see a page fault in the Guest, we
 * come here.  That's because we only set up the shadow page tables lazily as
 * they're needed, so we get page faults all the time and quietly fix them up
 * and return to the Guest without it knowing.
 *
 * If we fixed up the fault (ie. we mapped the address), this routine returns
 * true.  Otherwise, it was a real fault and we need to tell the Guest. */
int demand_page(struct lguest *lg, unsigned long vaddr, int errcode)
{
	pgd_t gpgd;
	pgd_t *spgd;
	unsigned long gpte_ptr;
	pte_t gpte;
	pte_t *spte;

	/* First step: get the top-level Guest page table entry. */
	gpgd = lgread(lg, gpgd_addr(lg, vaddr), pgd_t);
	/* Toplevel not present?  We can't map it in. */
	if (!(pgd_flags(gpgd) & _PAGE_PRESENT))
		return 0;

	/* Now look at the matching shadow entry. */
	spgd = spgd_addr(lg, lg->pgdidx, vaddr);
	if (!(pgd_flags(*spgd) & _PAGE_PRESENT)) {
		/* No shadow entry: allocate a new shadow PTE page. */
		unsigned long ptepage = get_zeroed_page(GFP_KERNEL);
		/* This is not really the Guest's fault, but killing it is
		 * simple for this corner case. */
		if (!ptepage) {
			kill_guest(lg, "out of memory allocating pte page");
			return 0;
		}
		/* We check that the Guest pgd is OK. */
		check_gpgd(lg, gpgd);
		/* And we copy the flags to the shadow PGD entry.  The page
		 * number in the shadow PGD is the page we just allocated. */
		*spgd = __pgd(__pa(ptepage) | pgd_flags(gpgd));
	}

	/* OK, now we look at the lower level in the Guest page table: keep its
	 * address, because we might update it later. */
	gpte_ptr = gpte_addr(lg, gpgd, vaddr);
	gpte = lgread(lg, gpte_ptr, pte_t);

	/* If this page isn't in the Guest page tables, we can't page it in. */
	if (!(pte_flags(gpte) & _PAGE_PRESENT))
		return 0;

	/* Check they're not trying to write to a page the Guest wants
	 * read-only (bit 2 of errcode == write). */
	if ((errcode & 2) && !(pte_flags(gpte) & _PAGE_RW))
		return 0;

	/* User access to a kernel-only page? (bit 3 == user access) */
	if ((errcode & 4) && !(pte_flags(gpte) & _PAGE_USER))
		return 0;

	/* Check that the Guest PTE flags are OK, and the page number is below
	 * the pfn_limit (ie. not mapping the Launcher binary). */
	check_gpte(lg, gpte);

	/* Add the _PAGE_ACCESSED and (for a write) _PAGE_DIRTY flag */
	gpte = pte_mkyoung(gpte);
	if (errcode & 2)
		gpte = pte_mkdirty(gpte);

	/* Get the pointer to the shadow PTE entry we're going to set. */
	spte = spte_addr(lg, *spgd, vaddr);
	/* If there was a valid shadow PTE entry here before, we release it.
	 * This can happen with a write to a previously read-only entry. */
	release_pte(*spte);

	/* If this is a write, we insist that the Guest page is writable (the
	 * final arg to gpte_to_spte()). */
	if (pte_dirty(gpte))
		*spte = gpte_to_spte(lg, gpte, 1);
	else
		/* If this is a read, don't set the "writable" bit in the page
		 * table entry, even if the Guest says it's writable.  That way
		 * we will come back here when a write does actually occur, so
		 * we can update the Guest's _PAGE_DIRTY flag. */
		*spte = gpte_to_spte(lg, pte_wrprotect(gpte), 0);

	/* Finally, we write the Guest PTE entry back: we've set the
	 * _PAGE_ACCESSED and maybe the _PAGE_DIRTY flags. */
	lgwrite(lg, gpte_ptr, pte_t, gpte);

	/* The fault is fixed, the page table is populated, the mapping
	 * manipulated, the result returned and the code complete.  A small
	 * delay and a trace of alliteration are the only indications the Guest
	 * has that a page fault occurred at all. */
	return 1;
}

/* Converting a Guest page table entry to a shadow (ie. real) page table
 * entry can be a little tricky.  The flags are (almost) the same, but the
 * Guest PTE contains a virtual page number: the CPU needs the real page
 * number. */
static pte_t gpte_to_spte(struct lguest *lg, pte_t gpte, int write)
{
	unsigned long pfn, base, flags;

	/* The Guest sets the global flag, because it thinks that it is using
	 * PGE.  We only told it to use PGE so it would tell us whether it was
	 * flushing a kernel mapping or a userspace mapping.  We don't actually
	 * use the global bit, so throw it away. */
	flags = (pte_flags(gpte) & ~_PAGE_GLOBAL);

	/* The Guest's pages are offset inside the Launcher. */
	base = (unsigned long)lg->mem_base / PAGE_SIZE;

	/* We need a temporary "unsigned long" variable to hold the answer from
	 * get_pfn(), because it returns 0xFFFFFFFF on failure, which wouldn't
	 * fit in spte.pfn.  get_pfn() finds the real physical number of the
	 * page, given the virtual number. */
	pfn = get_pfn(base + pte_pfn(gpte), write);
	if (pfn == -1UL) {
		kill_guest(lg, "failed to get page %lu", pte_pfn(gpte));
		/* When we destroy the Guest, we'll go through the shadow page
		 * tables and release_pte() them.  Make sure we don't think
		 * this one is valid! */
		flags = 0;
	}
	/* Now we assemble our shadow PTE from the page number and flags. */
	return pfn_pte(pfn, __pgprot(flags));
}

/* This routine takes a page number given by the Guest and converts it to
 * an actual, physical page number.  It can fail for several reasons: the
 * virtual address might not be mapped by the Launcher, the write flag is set
 * and the page is read-only, or the write flag was set and the page was
 * shared so had to be copied, but we ran out of memory.
 *
 * This holds a reference to the page, so release_pte() is careful to
 * put that back. */
static unsigned long get_pfn(unsigned long virtpfn, int write)
{
	struct page *page;
	/* This value indicates failure. */
	unsigned long ret = -1UL;

	/* get_user_pages() is a complex interface: it gets the "struct
	 * vm_area_struct" and "struct page" assocated with a range of pages.
	 * It also needs the task's mmap_sem held, and is not very quick.
	 * It returns the number of pages it got. */
	down_read(&current->mm->mmap_sem);
	if (get_user_pages(current, current->mm, virtpfn << PAGE_SHIFT,
			   1, write, 1, &page, NULL) == 1)
		ret = page_to_pfn(page);
	up_read(&current->mm->mmap_sem);
	return ret;
}

/*
 * (ii) Making sure the Guest stack is mapped.
 *
 * Remember that direct traps into the Guest need a mapped Guest kernel stack.
 * pin_stack_pages() calls us here: we could simply call demand_page(), but as
 * we've seen that logic is quite long, and usually the stack pages are already
 * mapped, so it's overkill.
 *
 * This is a quick version which answers the question: is this virtual address
 * mapped by the shadow page tables, and is it writable? */
static int page_writable(struct lguest *lg, unsigned long vaddr)
{
	pgd_t *spgd;
	unsigned long flags;

	/* Look at the current top level entry: is it present? */
	spgd = spgd_addr(lg, lg->pgdidx, vaddr);
	if (!(pgd_flags(*spgd) & _PAGE_PRESENT))
		return 0;

	/* Check the flags on the pte entry itself: it must be present and
	 * writable. */
	flags = pte_flags(*(spte_addr(lg, *spgd, vaddr)));

	return (flags & (_PAGE_PRESENT|_PAGE_RW)) == (_PAGE_PRESENT|_PAGE_RW);
}

/* So, when pin_stack_pages() asks us to pin a page, we check if it's already
 * in the page tables, and if not, we call demand_page() with error code 2
 * (meaning "write"). */
void pin_page(struct lguest *lg, unsigned long vaddr)
{
	if (!page_writable(lg, vaddr) && !demand_page(lg, vaddr, 2))
		kill_guest(lg, "bad stack page %#lx", vaddr);
}

/*
 * (iii) Setting up a page table entry when the Guest tells us one has changed.
 *
 * Just like we did in interrupts_and_traps.c, it makes sense for us to deal
 * with the other side of page tables while we're here: what happens when the
 * Guest asks for a page table to be updated?
 *
 * We already saw that demand_page() will fill in the shadow page tables when
 * needed, so we can simply remove shadow page table entries whenever the Guest
 * tells us they've changed.  When the Guest tries to use the new entry it will
 * fault and demand_page() will fix it up.
 *
 * So with that in mind here's our code to to update a (top-level) PGD entry:
 */
void guest_set_pmd(struct lguest *lg, unsigned long gpgdir, u32 idx)
{
	int pgdir;

	/* The kernel seems to try to initialize this early on: we ignore its
	 * attempts to map over the Switcher. */
	if (idx >= SWITCHER_PGD_INDEX)
		return;

	/* If they're talking about a page table we have a shadow for... */
	pgdir = find_pgdir(lg, gpgdir);
	if (pgdir < ARRAY_SIZE(lg->pgdirs))
		/* ... throw it away. */
		release_pgd(lg, lg->pgdirs[pgdir].pgdir + idx);
}

/* Updating a PTE entry is a little trickier.
 *
 * We keep track of several different page tables (the Guest uses one for each
 * process, so it makes sense to cache at least a few).  Each of these have
 * identical kernel parts: ie. every mapping above PAGE_OFFSET is the same for
 * all processes.  So when the page table above that address changes, we update
 * all the page tables, not just the current one.  This is rare.
 *
 * The benefit is that when we have to track a new page table, we can copy keep
 * all the kernel mappings.  This speeds up context switch immensely. */
void guest_set_pte(struct lguest *lg,
		   unsigned long gpgdir, unsigned long vaddr, pte_t gpte)
{
	/* Kernel mappings must be changed on all top levels.  Slow, but
	 * doesn't happen often. */
	if (vaddr >= lg->kernel_address) {
		unsigned int i;
		for (i = 0; i < ARRAY_SIZE(lg->pgdirs); i++)
			if (lg->pgdirs[i].pgdir)
				do_set_pte(lg, i, vaddr, gpte);
	} else {
		/* Is this page table one we have a shadow for? */
		int pgdir = find_pgdir(lg, gpgdir);
		if (pgdir != ARRAY_SIZE(lg->pgdirs))
			/* If so, do the update. */
			do_set_pte(lg, pgdir, vaddr, gpte);
	}
}

/* This is the routine which actually sets the page table entry for then
 * "idx"'th shadow page table.
 *
 * Normally, we can just throw out the old entry and replace it with 0: if they
 * use it demand_page() will put the new entry in.  We need to do this anyway:
 * The Guest expects _PAGE_ACCESSED to be set on its PTE the first time a page
 * is read from, and _PAGE_DIRTY when it's written to.
 *
 * But Avi Kivity pointed out that most Operating Systems (Linux included) set
 * these bits on PTEs immediately anyway.  This is done to save the CPU from
 * having to update them, but it helps us the same way: if they set
 * _PAGE_ACCESSED then we can put a read-only PTE entry in immediately, and if
 * they set _PAGE_DIRTY then we can put a writable PTE entry in immediately.
 */
static void do_set_pte(struct lguest *lg, int idx,
		       unsigned long vaddr, pte_t gpte)
{
	/* Look up the matching shadow page directory entry. */
	pgd_t *spgd = spgd_addr(lg, idx, vaddr);

	/* If the top level isn't present, there's no entry to update. */
	if (pgd_flags(*spgd) & _PAGE_PRESENT) {
		/* Otherwise, we start by releasing the existing entry. */
		pte_t *spte = spte_addr(lg, *spgd, vaddr);
		release_pte(*spte);

		/* If they're setting this entry as dirty or accessed, we might
		 * as well put that entry they've given us in now.  This shaves
		 * 10% off a copy-on-write micro-benchmark. */
		if (pte_flags(gpte) & (_PAGE_DIRTY | _PAGE_ACCESSED)) {
			check_gpte(lg, gpte);
			*spte = gpte_to_spte(lg, gpte,
					     pte_flags(gpte) & _PAGE_DIRTY);
		} else
			/* Otherwise kill it and we can demand_page() it in
			 * later. */
			*spte = __pte(0);
	}
}

/* (iv) Switching page tables
 *
 * Now we've seen all the page table setting and manipulation, let's see what
 * what happens when the Guest changes page tables (ie. changes the top-level
 * pgdir).  This occurs on almost every context switch. */
void guest_new_pagetable(struct lguest *lg, unsigned long pgtable)
{
	int newpgdir, repin = 0;

	/* Look to see if we have this one already. */
	newpgdir = find_pgdir(lg, pgtable);
	/* If not, we allocate or mug an existing one: if it's a fresh one,
	 * repin gets set to 1. */
	if (newpgdir == ARRAY_SIZE(lg->pgdirs))
		newpgdir = new_pgdir(lg, pgtable, &repin);
	/* Change the current pgd index to the new one. */
	lg->pgdidx = newpgdir;
	/* If it was completely blank, we map in the Guest kernel stack */
	if (repin)
		pin_stack_pages(lg);
}

/* And this is us, creating the new page directory.  If we really do
 * allocate a new one (and so the kernel parts are not there), we set
 * blank_pgdir. */
static unsigned int new_pgdir(struct lguest *lg,
			      unsigned long gpgdir,
			      int *blank_pgdir)
{
	unsigned int next;

	/* We pick one entry at random to throw out.  Choosing the Least
	 * Recently Used might be better, but this is easy. */
	next = random32() % ARRAY_SIZE(lg->pgdirs);
	/* If it's never been allocated at all before, try now. */
	if (!lg->pgdirs[next].pgdir) {
		lg->pgdirs[next].pgdir = (pgd_t *)get_zeroed_page(GFP_KERNEL);
		/* If the allocation fails, just keep using the one we have */
		if (!lg->pgdirs[next].pgdir)
			next = lg->pgdidx;
		else
			/* This is a blank page, so there are no kernel
			 * mappings: caller must map the stack! */
			*blank_pgdir = 1;
	}
	/* Record which Guest toplevel this shadows. */
	lg->pgdirs[next].gpgdir = gpgdir;
	/* Release all the non-kernel mappings. */
	flush_user_mappings(lg, next);

	return next;
}

/* (v) Flushing (throwing away) page tables,
 *
 * The Guest has a hypercall to throw away the page tables: it's used when a
 * large number of mappings have been changed. */
void guest_pagetable_flush_user(struct lguest *lg)
{
	/* Drop the userspace part of the current page table. */
	flush_user_mappings(lg, lg->pgdidx);
}


/* We saw flush_user_mappings() twice: once from the flush_user_mappings()
 * hypercall and once in new_pgdir() when we re-used a top-level pgdir page.
 * It simply releases every PTE page from 0 up to the Guest's kernel address. */
static void flush_user_mappings(struct lguest *lg, int idx)
{
	unsigned int i;
	/* Release every pgd entry up to the kernel's address. */
	for (i = 0; i < pgd_index(lg->kernel_address); i++)
		release_pgd(lg, lg->pgdirs[idx].pgdir + i);
}

/* If we chase down the release_pgd() code, it looks like this: */
static void release_pgd(struct lguest *lg, pgd_t *spgd)
{
	/* If the entry's not present, there's nothing to release. */
	if (pgd_flags(*spgd) & _PAGE_PRESENT) {
		unsigned int i;
		/* Converting the pfn to find the actual PTE page is easy: turn
		 * the page number into a physical address, then convert to a
		 * virtual address (easy for kernel pages like this one). */
		pte_t *ptepage = __va(pgd_pfn(*spgd) << PAGE_SHIFT);
		/* For each entry in the page, we might need to release it. */
		for (i = 0; i < PTRS_PER_PTE; i++)
			release_pte(ptepage[i]);
		/* Now we can free the page of PTEs */
		free_page((long)ptepage);
		/* And zero out the PGD entry so we never release it twice. */
		*spgd = __pgd(0);
	}
}

/* And to complete the chain, release_pte() looks like this: */
static void release_pte(pte_t pte)
{
	/* Remember that get_user_pages() took a reference to the page, in
	 * get_pfn()?  We have to put it back now. */
	if (pte_flags(pte) & _PAGE_PRESENT)
		put_page(pfn_to_page(pte_pfn(pte)));
}


/* Finally, a routine which throws away everything: all PGD entries in all
 * the shadow page tables, including the Guest's kernel mappings.  This is used
 * when we destroy the Guest. */
static void release_all_pagetables(struct lguest *lg)
{
	unsigned int i, j;

	/* Every shadow pagetable this Guest has */
	for (i = 0; i < ARRAY_SIZE(lg->pgdirs); i++)
		if (lg->pgdirs[i].pgdir)
			/* Every PGD entry except the Switcher at the top */
			for (j = 0; j < SWITCHER_PGD_INDEX; j++)
				release_pgd(lg, lg->pgdirs[i].pgdir + j);
}

/* We also throw away everything when a Guest tells us it's changed a kernel
 * mapping.  Since kernel mappings are in every page table, it's easiest to
 * throw them all away.  This traps the Guest in amber for a while as
 * everything faults back in, but it's rare. */
void guest_pagetable_clear_all(struct lguest *lg)
{
	release_all_pagetables(lg);
	/* We need the Guest kernel stack mapped again. */
	pin_stack_pages(lg);
}


/* (vi) Mapping the Switcher when the Guest is about to run.
 *
 * The Switcher and the two pages for this CPU need to be visible in the
 * Guest (and not the pages for other CPUs).  We have the appropriate PTE pages
 * for each CPU already set up, we just need to hook them in now we know which
 * Guest is about to run on this CPU. */
void map_switcher_in_guest(struct lguest *lg, struct lguest_pages *pages)
{
	pte_t *switcher_pte_page = __get_cpu_var(switcher_pte_pages);
	pgd_t switcher_pgd;
	pte_t regs_pte;

	/* Make the last PGD entry for this Guest point to the Switcher's PTE
	 * page for this CPU (with appropriate flags). */
	switcher_pgd = __pgd(__pa(switcher_pte_page) | _PAGE_KERNEL);

	lg->pgdirs[lg->pgdidx].pgdir[SWITCHER_PGD_INDEX] = switcher_pgd;

	/* We also change the Switcher PTE page.  When we're running the Guest,
	 * we want the Guest's "regs" page to appear where the first Switcher
	 * page for this CPU is.  This is an optimization: when the Switcher
	 * saves the Guest registers, it saves them into the first page of this
	 * CPU's "struct lguest_pages": if we make sure the Guest's register
	 * page is already mapped there, we don't have to copy them out
	 * again. */
	regs_pte = pfn_pte (__pa(lg->regs_page) >> PAGE_SHIFT, __pgprot(_PAGE_KERNEL));
	switcher_pte_page[(unsigned long)pages/PAGE_SIZE%PTRS_PER_PTE] = regs_pte;
}


/* (vii) Setting up the page tables initially.
 *
 * When a Guest is first created, the Launcher tells us where the toplevel of
 * its first page table is.  We set some things up here: */
int init_guest_pagetable(struct lguest *lg, unsigned long pgtable)
{
	/* We start on the first shadow page table, and give it a blank PGD
	 * page. */
	lg->pgdidx = 0;
	lg->pgdirs[lg->pgdidx].gpgdir = pgtable;
	lg->pgdirs[lg->pgdidx].pgdir = (pgd_t*)get_zeroed_page(GFP_KERNEL);
	if (!lg->pgdirs[lg->pgdidx].pgdir)
		return -ENOMEM;
	return 0;
}

/* When the Guest calls LHCALL_LGUEST_INIT we do more setup. */
void page_table_guest_data_init(struct lguest *lg)
{
	/* We get the kernel address: above this is all kernel memory. */
	if (get_user(lg->kernel_address, &lg->lguest_data->kernel_address)
	    /* We tell the Guest that it can't use the top 4MB of virtual
	     * addresses used by the Switcher. */
	    || put_user(4U*1024*1024, &lg->lguest_data->reserve_mem)
	    || put_user(lg->pgdirs[lg->pgdidx].gpgdir,&lg->lguest_data->pgdir))
		kill_guest(lg, "bad guest page %p", lg->lguest_data);

	/* In flush_user_mappings() we loop from 0 to
	 * "pgd_index(lg->kernel_address)".  This assumes it won't hit the
	 * Switcher mappings, so check that now. */
	if (pgd_index(lg->kernel_address) >= SWITCHER_PGD_INDEX)
		kill_guest(lg, "bad kernel address %#lx", lg->kernel_address);
}

/* When a Guest dies, our cleanup is fairly simple. */
void free_guest_pagetable(struct lguest *lg)
{
	unsigned int i;

	/* Throw away all page table pages. */
	release_all_pagetables(lg);
	/* Now free the top levels: free_page() can handle 0 just fine. */
	for (i = 0; i < ARRAY_SIZE(lg->pgdirs); i++)
		free_page((long)lg->pgdirs[i].pgdir);
}

/* At boot or module load time, init_pagetables() allocates and populates
 * the Switcher PTE page for each CPU. */
__init int init_pagetables(struct page **switcher_page, unsigned int pages)
{
	unsigned int i;

	for_each_possible_cpu(i) {
		switcher_pte_page(i) = (pte_t *)get_zeroed_page(GFP_KERNEL);
		if (!switcher_pte_page(i)) {
			free_switcher_pte_pages();
			return -ENOMEM;
		}
		populate_switcher_pte_page(i, switcher_page, pages);
	}
	return 0;
}


/* Setting up the Switcher PTE page for given CPU is fairly easy, given
 * the CPU number and the "struct page"s for the Switcher code itself.
 *
 * Currently the Switcher is less than a page long, so "pages" is always 1. */
static __init void populate_switcher_pte_page(unsigned int cpu,
					      struct page *switcher_page[],
					      unsigned int pages)
{
	unsigned int i;
	pte_t *pte = switcher_pte_page(cpu);

	/* The first entries are easy: they map the Switcher code. */
	for (i = 0; i < pages; i++) {
		pte[i] = mk_pte(switcher_page[i],
				__pgprot(_PAGE_PRESENT|_PAGE_ACCESSED));
	}

	/* The only other thing we map is this CPU's pair of pages. */
	i = pages + cpu*2;

	/* First page (Guest registers) is writable from the Guest */
	pte[i] = pfn_pte(page_to_pfn(switcher_page[i]),
			 __pgprot(_PAGE_PRESENT|_PAGE_ACCESSED|_PAGE_RW));

	/* The second page contains the "struct lguest_ro_state", and is
	 * read-only. */
	pte[i+1] = pfn_pte(page_to_pfn(switcher_page[i+1]),
			   __pgprot(_PAGE_PRESENT|_PAGE_ACCESSED));
}

/* We've made it through the page table code.  Perhaps our tired brains are
 * still processing the details, or perhaps we're simply glad it's over.
 *
 * If nothing else, note that all this complexity in juggling shadow page
 * tables in sync with the Guest's page tables is for one reason: for most
 * Guests this page table dance determines how bad performance will be.  This
 * is why Xen uses exotic direct Guest pagetable manipulation, and why both
 * Intel and AMD have implemented shadow page table support directly into
 * hardware.
 *
 * There is just one file remaining in the Host. */

[ drivers/lguest/segments.c ]
/*
 * Segments & The Global Descriptor Table
 *
 * (That title sounds like a bad Nerdcore group.  Not to suggest that there are
 * any good Nerdcore groups, but in high school a friend of mine had a band
 * called Joe Fish and the Chips, so there are definitely worse band names).
 *
 * To refresh: the GDT is a table of 8-byte values describing segments.  Once
 * set up, these segments can be loaded into one of the 6 "segment registers".
 *
 * GDT entries are passed around as "struct desc_struct"s, which like IDT
 * entries are split into two 32-bit members, "a" and "b".  One day, someone
 * will clean that up, and be declared a Hero.  (No pressure, I'm just saying).
 *
 * Anyway, the GDT entry contains a base (the start address of the segment), a
 * limit (the size of the segment - 1), and some flags.  Sounds simple, and it
 * would be, except those zany Intel engineers decided that it was too boring
 * to put the base at one end, the limit at the other, and the flags in
 * between.  They decided to shotgun the bits at random throughout the 8 bytes,
 * like so:
 *
 * 0               16                     40       48  52  56     63
 * [ limit part 1 ][     base part 1     ][ flags ][li][fl][base ]
 *                                                  mit ags part 2
 *                                                part 2
 *
 * As a result, this file contains a certain amount of magic numeracy.  Let's
 * begin.
 */

/* There are several entries we don't let the Guest set.  The TSS entry is the
 * "Task State Segment" which controls all kinds of delicate things.  The
 * LGUEST_CS and LGUEST_DS entries are reserved for the Switcher, and the
 * the Guest can't be trusted to deal with double faults. */
static int ignored_gdt(unsigned int num)
{
	return (num == GDT_ENTRY_TSS
		|| num == GDT_ENTRY_LGUEST_CS
		|| num == GDT_ENTRY_LGUEST_DS
		|| num == GDT_ENTRY_DOUBLEFAULT_TSS);
}

/* Like the IDT, we never simply use the GDT the Guest gives us.  We keep
 * a GDT for each CPU, and copy across the Guest's entries each time we want to
 * run the Guest on that CPU.
 *
 * This routine is called at boot or modprobe time for each CPU to set up the
 * constant GDT entries: the ones which are the same no matter what Guest we're
 * running. */
void setup_default_gdt_entries(struct lguest_ro_state *state)
{
	struct desc_struct *gdt = state->guest_gdt;
	unsigned long tss = (unsigned long)&state->guest_tss;

	/* The Switcher segments are full 0-4G segments, privilege level 0 */
	gdt[GDT_ENTRY_LGUEST_CS] = FULL_EXEC_SEGMENT;
	gdt[GDT_ENTRY_LGUEST_DS] = FULL_SEGMENT;

	/* The TSS segment refers to the TSS entry for this particular CPU.
	 * Forgive the magic flags: the 0x8900 means the entry is Present, it's
	 * privilege level 0 Available 386 TSS system segment, and the 0x67
	 * means Saturn is eclipsed by Mercury in the twelfth house. */
	gdt[GDT_ENTRY_TSS].a = 0x00000067 | (tss << 16);
	gdt[GDT_ENTRY_TSS].b = 0x00008900 | (tss & 0xFF000000)
		| ((tss >> 16) & 0x000000FF);
}

/* This routine sets up the initial Guest GDT for booting.  All entries start
 * as 0 (unusable). */
void setup_guest_gdt(struct lguest *lg)
{
	/* Start with full 0-4G segments... */
	lg->arch.gdt[GDT_ENTRY_KERNEL_CS] = FULL_EXEC_SEGMENT;
	lg->arch.gdt[GDT_ENTRY_KERNEL_DS] = FULL_SEGMENT;
	/* ...except the Guest is allowed to use them, so set the privilege
	 * level appropriately in the flags. */
	lg->arch.gdt[GDT_ENTRY_KERNEL_CS].b |= (GUEST_PL << 13);
	lg->arch.gdt[GDT_ENTRY_KERNEL_DS].b |= (GUEST_PL << 13);
}

/* This is where the Guest asks us to load a new GDT (LHCALL_LOAD_GDT).
 * We copy it from the Guest and tweak the entries. */
void load_guest_gdt(struct lguest *lg, unsigned long table, u32 num)
{
	/* We assume the Guest has the same number of GDT entries as the
	 * Host, otherwise we'd have to dynamically allocate the Guest GDT. */
	if (num > ARRAY_SIZE(lg->arch.gdt))
		kill_guest(lg, "too many gdt entries %i", num);

	/* We read the whole thing in, then fix it up. */
	__lgread(lg, lg->arch.gdt, table, num * sizeof(lg->arch.gdt[0]));
	fixup_gdt_table(lg, 0, ARRAY_SIZE(lg->arch.gdt));
	/* Mark that the GDT changed so the core knows it has to copy it again,
	 * even if the Guest is run on the same CPU. */
	lg->changed |= CHANGED_GDT;
}

/* This is the fast-track version for just changing the three TLS entries.
 * Remember that this happens on every context switch, so it's worth
 * optimizing.  But wouldn't it be neater to have a single hypercall to cover
 * both cases? */
void guest_load_tls(struct lguest *lg, unsigned long gtls)
{
	struct desc_struct *tls = &lg->arch.gdt[GDT_ENTRY_TLS_MIN];

	__lgread(lg, tls, gtls, sizeof(*tls)*GDT_ENTRY_TLS_ENTRIES);
	fixup_gdt_table(lg, GDT_ENTRY_TLS_MIN, GDT_ENTRY_TLS_MAX+1);
	/* Note that just the TLS entries have changed. */
	lg->changed |= CHANGED_GDT_TLS;
}


/* Once the Guest gave us new GDT entries, we fix them up a little.  We
 * don't care if they're invalid: the worst that can happen is a General
 * Protection Fault in the Switcher when it restores a Guest segment register
 * which tries to use that entry.  Then we kill the Guest for causing such a
 * mess: the message will be "unhandled trap 256". */
static void fixup_gdt_table(struct lguest *lg, unsigned start, unsigned end)
{
	unsigned int i;

	for (i = start; i < end; i++) {
		/* We never copy these ones to real GDT, so we don't care what
		 * they say */
		if (ignored_gdt(i))
			continue;

		/* Segment descriptors contain a privilege level: the Guest is
		 * sometimes careless and leaves this as 0, even though it's
		 * running at privilege level 1.  If so, we fix it here. */
		if ((lg->arch.gdt[i].b & 0x00006000) == 0)
			lg->arch.gdt[i].b |= (GUEST_PL << 13);

		/* Each descriptor has an "accessed" bit.  If we don't set it
		 * now, the CPU will try to set it when the Guest first loads
		 * that entry into a segment register.  But the GDT isn't
		 * writable by the Guest, so bad things can happen. */
		lg->arch.gdt[i].b |= 0x00000100;
	}
}

/* When the Guest is run on a different CPU, or the GDT entries have
 * changed, copy_gdt() is called to copy the Guest's GDT entries across to this
 * CPU's GDT. */
void copy_gdt(const struct lguest *lg, struct desc_struct *gdt)
{
	unsigned int i;

	/* The default entries from setup_default_gdt_entries() are not
	 * replaced.  See ignored_gdt() above. */
	for (i = 0; i < GDT_ENTRIES; i++)
		if (!ignored_gdt(i))
			gdt[i] = lg->arch.gdt[i];
}

/* An optimization of copy_gdt(), for just the three "thead-local storage"
 * entries. */
void copy_gdt_tls(const struct lguest *lg, struct desc_struct *gdt)
{
	unsigned int i;

	for (i = GDT_ENTRY_TLS_MIN; i <= GDT_ENTRY_TLS_MAX; i++)
		gdt[i] = lg->arch.gdt[i];
}

/*
 * With this, we have finished the Host.
 *
 * Five of the seven parts of our task are complete.  You have made it through
 * the Bit of Despair (I think that's somewhere in the page table code,
 * myself).
 *
 * Next, we examine "make Switcher".  It's short, but intense.
 */

$ make Switcher
[ drivers/lguest/x86/core.c ]
/*
 * We approach the Switcher.
 *
 * Remember that each CPU has two pages which are visible to the Guest when it
 * runs on that CPU.  This has to contain the state for that Guest: we copy the
 * state in just before we run the Guest.
 *
 * Each Guest has "changed" flags which indicate what has changed in the Guest
 * since it last ran.  We saw this set in interrupts_and_traps.c and
 * segments.c.
 */
static void copy_in_guest_info(struct lguest *lg, struct lguest_pages *pages)
{
	/* Copying all this data can be quite expensive.  We usually run the
	 * same Guest we ran last time (and that Guest hasn't run anywhere else
	 * meanwhile).  If that's not the case, we pretend everything in the
	 * Guest has changed. */
	if (__get_cpu_var(last_guest) != lg || lg->last_pages != pages) {
		__get_cpu_var(last_guest) = lg;
		lg->last_pages = pages;
		lg->changed = CHANGED_ALL;
	}

	/* These copies are pretty cheap, so we do them unconditionally: */
	/* Save the current Host top-level page directory. */
	pages->state.host_cr3 = __pa(current->mm->pgd);
	/* Set up the Guest's page tables to see this CPU's pages (and no
	 * other CPU's pages). */
	map_switcher_in_guest(lg, pages);
	/* Set up the two "TSS" members which tell the CPU what stack to use
	 * for traps which do directly into the Guest (ie. traps at privilege
	 * level 1). */
	pages->state.guest_tss.esp1 = lg->esp1;
	pages->state.guest_tss.ss1 = lg->ss1;

	/* Copy direct-to-Guest trap entries. */
	if (lg->changed & CHANGED_IDT)
		copy_traps(lg, pages->state.guest_idt, default_idt_entries);

	/* Copy all GDT entries which the Guest can change. */
	if (lg->changed & CHANGED_GDT)
		copy_gdt(lg, pages->state.guest_gdt);
	/* If only the TLS entries have changed, copy them. */
	else if (lg->changed & CHANGED_GDT_TLS)
		copy_gdt_tls(lg, pages->state.guest_gdt);

	/* Mark the Guest as unchanged for next time. */
	lg->changed = 0;
}

/* Finally: the code to actually call into the Switcher to run the Guest. */
static void run_guest_once(struct lguest *lg, struct lguest_pages *pages)
{
	/* This is a dummy value we need for GCC's sake. */
	unsigned int clobber;

	/* Copy the guest-specific information into this CPU's "struct
	 * lguest_pages". */
	copy_in_guest_info(lg, pages);

	/* Set the trap number to 256 (impossible value).  If we fault while
	 * switching to the Guest (bad segment registers or bug), this will
	 * cause us to abort the Guest. */
	lg->regs->trapnum = 256;

	/* Now: we push the "eflags" register on the stack, then do an "lcall".
	 * This is how we change from using the kernel code segment to using
	 * the dedicated lguest code segment, as well as jumping into the
	 * Switcher.
	 *
	 * The lcall also pushes the old code segment (KERNEL_CS) onto the
	 * stack, then the address of this call.  This stack layout happens to
	 * exactly match the stack layout created by an interrupt... */
	asm volatile("pushf; lcall *lguest_entry"
		     /* This is how we tell GCC that %eax ("a") and %ebx ("b")
		      * are changed by this routine.  The "=" means output. */
		     : "=a"(clobber), "=b"(clobber)
		     /* %eax contains the pages pointer.  ("0" refers to the
		      * 0-th argument above, ie "a").  %ebx contains the
		      * physical address of the Guest's top-level page
		      * directory. */
		     : "0"(pages), "1"(__pa(lg->pgdirs[lg->pgdidx].pgdir))
		     /* We tell gcc that all these registers could change,
		      * which means we don't have to save and restore them in
		      * the Switcher. */
		     : "memory", "%edx", "%ecx", "%edi", "%esi");
}


[ drivers/lguest/x86/switcher_32.S ]
/*
 * Welcome to the Switcher itself!
 *
 * This file contains the low-level code which changes the CPU to run the Guest
 * code, and returns to the Host when something happens.  Understand this, and
 * you understand the heart of our journey.
 *
 * Because this is in assembler rather than C, our tale switches from prose to
 * verse.  First I tried limericks:
 *
 *	There once was an eax reg,
 *	To which our pointer was fed,
 *	It needed an add,
 *	Which asm-offsets.h had
 *	But this limerick is hurting my head.
 *
 * Next I tried haikus, but fitting the required reference to the seasons in
 * every stanza was quickly becoming tiresome:
 *
 *	The %eax reg
 *	Holds "struct lguest_pages" now:
 *	Cherry blossoms fall.
 *
 * Then I started with Heroic Verse, but the rhyming requirement leeched away
 * the content density and led to some uniquely awful oblique rhymes:
 *
 *	These constants are coming from struct offsets
 *	For use within the asm switcher text.
 *
 * Finally, I settled for something between heroic hexameter, and normal prose
 * with inappropriate linebreaks.  Anyway, it aint no Shakespeare.
 */

// Not all kernel headers work from assembler
// But these ones are needed: the ENTRY() define
// And constants extracted from struct offsets
// To avoid magic numbers and breakage:
// Should they change the compiler can't save us
// Down here in the depths of assembler code.
#include <linux/linkage.h>
#include <asm/asm-offsets.h>
#include <asm/page.h>
#include <asm/segment.h>
#include <asm/lguest.h>

// We mark the start of the code to copy
// It's placed in .text tho it's never run here
// You'll see the trick macro at the end
// Which interleaves data and text to effect.
.text
ENTRY(start_switcher_text)

// When we reach switch_to_guest we have just left
// The safe and comforting shores of C code
// %eax has the "struct lguest_pages" to use
// Where we save state and still see it from the Guest
// And %ebx holds the Guest shadow pagetable:
// Once set we have truly left Host behind.
ENTRY(switch_to_guest)
	// We told gcc all its regs could fade,
	// Clobbered by our journey into the Guest
	// We could have saved them, if we tried
	// But time is our master and cycles count.

	// Segment registers must be saved for the Host
	// We push them on the Host stack for later
	pushl	%es
	pushl	%ds
	pushl	%gs
	pushl	%fs
	// But the compiler is fickle, and heeds
	// No warning of %ebp clobbers
	// When frame pointers are used.  That register
	// Must be saved and restored or chaos strikes.
	pushl	%ebp
	// The Host's stack is done, now save it away
	// In our "struct lguest_pages" at offset
	// Distilled into asm-offsets.h
	movl	%esp, LGUEST_PAGES_host_sp(%eax)

	// All saved and there's now five steps before us:
	// Stack, GDT, IDT, TSS
	// Then last of all the page tables are flipped.

	// Yet beware that our stack pointer must be
	// Always valid lest an NMI hits
	// %edx does the duty here as we juggle
	// %eax is lguest_pages: our stack lies within.
	movl	%eax, %edx
	addl	$LGUEST_PAGES_regs, %edx
	movl	%edx, %esp

	// The Guest's GDT we so carefully
	// Placed in the "struct lguest_pages" before
	lgdt	LGUEST_PAGES_guest_gdt_desc(%eax)

	// The Guest's IDT we did partially
	// Copy to "struct lguest_pages" as well.
	lidt	LGUEST_PAGES_guest_idt_desc(%eax)

	// The TSS entry which controls traps
	// Must be loaded up with "ltr" now:
	// The GDT entry that TSS uses 
	// Changes type when we load it: damn Intel!
	// For after we switch over our page tables
	// That entry will be read-only: we'd crash.
	movl	$(GDT_ENTRY_TSS*8), %edx
	ltr	%dx

	// Look back now, before we take this last step!
	// The Host's TSS entry was also marked used;
	// Let's clear it again for our return.
	// The GDT descriptor of the Host
	// Points to the table after two "size" bytes
	movl	(LGUEST_PAGES_host_gdt_desc+2)(%eax), %edx
	// Clear "used" from type field (byte 5, bit 2)
	andb	$0xFD, (GDT_ENTRY_TSS*8 + 5)(%edx)

	// Once our page table's switched, the Guest is live!
	// The Host fades as we run this final step.
	// Our "struct lguest_pages" is now read-only.
	movl	%ebx, %cr3

	// The page table change did one tricky thing:
	// The Guest's register page has been mapped
	// Writable under our %esp (stack) --
	// We can simply pop off all Guest regs.
	popl	%eax
	popl	%ebx
	popl	%ecx
	popl	%edx
	popl	%esi
	popl	%edi
	popl	%ebp
	popl	%gs
	popl	%fs
	popl	%ds
	popl	%es

	// Near the base of the stack lurk two strange fields
	// Which we fill as we exit the Guest
	// These are the trap number and its error
	// We can simply step past them on our way.
	addl	$8, %esp

	// The last five stack slots hold return address
	// And everything needed to switch privilege
	// From Switcher's level 0 to Guest's 1,
	// And the stack where the Guest had last left it.
	// Interrupts are turned back on: we are Guest.
	iret

// We treat two paths to switch back to the Host
// Yet both must save Guest state and restore Host
// So we put the routine in a macro.
#define SWITCH_TO_HOST							\
	/* We save the Guest state: all registers first			\
	 * Laid out just as "struct lguest_regs" defines */		\
	pushl	%es;							\
	pushl	%ds;							\
	pushl	%fs;							\
	pushl	%gs;							\
	pushl	%ebp;							\
	pushl	%edi;							\
	pushl	%esi;							\
	pushl	%edx;							\
	pushl	%ecx;							\
	pushl	%ebx;							\
	pushl	%eax;							\
	/* Our stack and our code are using segments			\
	 * Set in the TSS and IDT					\
	 * Yet if we were to touch data we'd use			\
	 * Whatever data segment the Guest had.				\
	 * Load the lguest ds segment for now. */			\
	movl	$(LGUEST_DS), %eax;					\
	movl	%eax, %ds;						\
	/* So where are we?  Which CPU, which struct?			\
	 * The stack is our clue: our TSS starts			\
	 * It at the end of "struct lguest_pages".			\
	 * Or we may have stumbled while restoring			\
	 * Our Guest segment regs while in switch_to_guest,		\
	 * The fault pushed atop that part-unwound stack.		\
	 * If we round the stack down to the page start			\
	 * We're at the start of "struct lguest_pages". */		\
	movl	%esp, %eax;						\
	andl	$(~(1 << PAGE_SHIFT - 1)), %eax;			\
	/* Save our trap number: the switch will obscure it		\
	 * (In the Host the Guest regs are not mapped here)		\
	 * %ebx holds it safe for deliver_to_host */			\
	movl	LGUEST_PAGES_regs_trapnum(%eax), %ebx;			\
	/* The Host GDT, IDT and stack!					\
	 * All these lie safely hidden from the Guest:			\
	 * We must return to the Host page tables			\
	 * (Hence that was saved in struct lguest_pages) */		\
	movl	LGUEST_PAGES_host_cr3(%eax), %edx;			\
	movl	%edx, %cr3;						\
	/* As before, when we looked back at the Host			\
	 * As we left and marked TSS unused				\
	 * So must we now for the Guest left behind. */			\
	andb	$0xFD, (LGUEST_PAGES_guest_gdt+GDT_ENTRY_TSS*8+5)(%eax); \
	/* Switch to Host's GDT, IDT. */				\
	lgdt	LGUEST_PAGES_host_gdt_desc(%eax);			\
	lidt	LGUEST_PAGES_host_idt_desc(%eax);			\
	/* Restore the Host's stack where its saved regs lie */		\
	movl	LGUEST_PAGES_host_sp(%eax), %esp;			\
	/* Last the TSS: our Host is returned */			\
	movl	$(GDT_ENTRY_TSS*8), %edx;				\
	ltr	%dx;							\
	/* Restore now the regs saved right at the first. */		\
	popl	%ebp;							\
	popl	%fs;							\
	popl	%gs;							\
	popl	%ds;							\
	popl	%es

// The first path is trod when the Guest has trapped:
// (Which trap it was has been pushed on the stack).
// We need only switch back, and the Host will decode
// Why we came home, and what needs to be done.
return_to_host:
	SWITCH_TO_HOST
	iret

// We are lead to the second path like so:
// An interrupt, with some cause external
// Has ajerked us rudely from the Guest's code
// Again we must return home to the Host
deliver_to_host:
	SWITCH_TO_HOST
	// But now we must go home via that place
	// Where that interrupt was supposed to go
	// Had we not been ensconced, running the Guest.
	// Here we see the trickness of run_guest_once():
	// The Host stack is formed like an interrupt
	// With EIP, CS and EFLAGS layered.
	// Interrupt handlers end with "iret"
	// And that will take us home at long long last.

	// But first we must find the handler to call!
	// The IDT descriptor for the Host
	// Has two bytes for size, and four for address:
	// %edx will hold it for us for now.
	movl	(LGUEST_PAGES_host_idt_desc+2)(%eax), %edx
	// We now know the table address we need,
	// And saved the trap's number inside %ebx.
	// Yet the pointer to the handler is smeared
	// Across the bits of the table entry.
	// What oracle can tell us how to extract
	// From such a convoluted encoding?
	// I consulted gcc, and it gave
	// These instructions, which I gladly credit:
	leal	(%edx,%ebx,8), %eax
	movzwl	(%eax),%edx
	movl	4(%eax), %eax
	xorw	%ax, %ax
	orl	%eax, %edx
	// Now the address of the handler's in %edx
	// We call it now: its "iret" drops us home.
	jmp	*%edx

// Every interrupt can come to us here
// But we must truly tell each apart.
// They number two hundred and fifty six
// And each must land in a different spot,
// Push its number on stack, and join the stream.

// And worse, a mere six of the traps stand apart
// And push on their stack an addition:
// An error number, thirty two bits long
// So we punish the other two fifty
// And make them push a zero so they match.

// Yet two fifty six entries is long
// And all will look most the same as the last
// So we create a macro which can make
// As many entries as we need to fill.

// Note the change to .data then .text:
// We plant the address of each entry
// Into a (data) table for the Host
// To know where each Guest interrupt should go.
.macro IRQ_STUB N TARGET
	.data; .long 1f; .text; 1:
 // Trap eight, ten through fourteen and seventeen
 // Supply an error number.  Else zero.
 .if (\N <> 8) && (\N < 10 || \N > 14) && (\N <> 17)
	pushl	$0
 .endif
	pushl	$\N
	jmp	\TARGET
	ALIGN
.endm

// This macro creates numerous entries
// Using GAS macros which out-power C's.
.macro IRQ_STUBS FIRST LAST TARGET
 irq=\FIRST
 .rept \LAST-\FIRST+1
	IRQ_STUB irq \TARGET
  irq=irq+1
 .endr
.endm

// Here's the marker for our pointer table
// Laid in the data section just before
// Each macro places the address of code
// Forming an array: each one points to text
// Which handles interrupt in its turn.
.data
.global default_idt_entries
default_idt_entries:
.text
	// The first two traps go straight back to the Host
	IRQ_STUBS 0 1 return_to_host
	// We'll say nothing, yet, about NMI
	IRQ_STUB 2 handle_nmi
	// Other traps also return to the Host
	IRQ_STUBS 3 31 return_to_host
	// All interrupts go via their handlers
	IRQ_STUBS 32 127 deliver_to_host
	// 'Cept system calls coming from userspace
	// Are to go to the Guest, never the Host.
	IRQ_STUB 128 return_to_host
	IRQ_STUBS 129 255 deliver_to_host

// The NMI, what a fabulous beast
// Which swoops in and stops us no matter that
// We're suspended between heaven and hell,
// (Or more likely between the Host and Guest)
// When in it comes!  We are dazed and confused
// So we do the simplest thing which one can.
// Though we've pushed the trap number and zero
// We discard them, return, and hope we live.
handle_nmi:
	addl	$8, %esp
	iret

// We are done; all that's left is Mastery
// And "make Mastery" is a journey long
// Designed to make your fingers itch to code.

// Here ends the text, the file and poem.
ENTRY(end_switcher_text)

$ make Mastery
[ drivers/lguest/x86/core.c ]
/* There are hooks in the scheduler which we can register to tell when we
 * get kicked off the CPU (preempt_notifier_register()).  This would allow us
 * to lazily disable SYSENTER which would regain some performance, and should
 * also simplify copy_in_guest_info().  Note that we'd still need to restore
 * things when we exit to Launcher userspace, but that's fairly easy.
 *
 * The hooks were designed for KVM, but we can also put them to good use. */

[ arch/x86/lguest/boot.c ]
/* Note that we don't check for outstanding interrupts when we re-enable
 * them (or when we unmask an interrupt).  This seems to work for the moment,
 * since interrupts are rare and we'll just get the interrupt on the next timer
 * tick, but when we turn on CONFIG_NO_HZ, we should revisit this.  One way
 * would be to put the "irq_enabled" field in a page by itself, and have the
 * Host write-protect it when an interrupt comes in when irqs are disabled.
 * There will then be a page fault as soon as interrupts are re-enabled. */

[ arch/x86/lguest/i386_head.S ]
/* When the Host reflects a trap or injects an interrupt into the Guest,
 * it sets the eflags interrupt bit on the stack based on
 * lguest_data.irq_enabled, so the Guest iret logic does the right thing when
 * restoring it.  However, when the Host sets the Guest up for direct traps,
 * such as system calls, the processor is the one to push eflags onto the
 * stack, and the interrupt bit will be 1 (in reality, interrupts are always
 * enabled in the Guest).
 *
 * This turns out to be harmless: the only trap which should happen under Linux
 * with interrupts disabled is Page Fault (due to our lazy mapping of vmalloc
 * regions), which has to be reflected through the Host anyway.  If another
 * trap *does* go off when interrupts are disabled, the Guest will panic, and
 * we'll never get to this iret! */

[ drivers/lguest/interrupts_and_traps.c ]
/* The Guest has the ability to turn its interrupt gates into trap gates,
 * if it is careful.  The Host will let trap gates can go directly to the
 * Guest, but the Guest needs the interrupts atomically disabled for an
 * interrupt gate.  It can do this by pointing the trap gate at instructions
 * within noirq_start and noirq_end, where it can safely disable interrupts. */

/* The Guests do not use the sysenter (fast system call) instruction,
 * because it's hardcoded to enter privilege level 0 and so can't go direct.
 * It's about twice as fast as the older "int 0x80" system call, so it might
 * still be worthwhile to handle it in the Switcher and lcall down to the
 * Guest.  The sysenter semantics are hairy tho: search for that keyword in
 * entry.S */

[ drivers/lguest/page_tables.c ]
/* We hold reference to pages, which prevents them from being swapped.
 * It'd be nice to have a callback in the "struct mm_struct" when Linux wants
 * to swap out.  If we had this, and a shrinker callback to trim PTE pages, we
 * could probably consider launching Guests as non-root. */

/* Since we throw away all mappings when a kernel mapping changes, our
 * performance sucks for guests using highmem.  In fact, a guest with
 * PAGE_OFFSET 0xc0000000 (the default) and more than about 700MB of RAM is
 * usually slower than a Guest with less memory.
 *
 * This, of course, cannot be fixed.  It would take some kind of... well, I
 * don't know, but the term "puissant code-fu" comes to mind. */

[ Documentation/lguest/lguest.c ]
/* Inter-guest networking is an interesting area.  Simplest is to have a
 * --sharenet=<name> option which opens or creates a named pipe.  This can be
 * used to send packets to another guest in a 1:1 manner.
 *
 * More sopisticated is to use one of the tools developed for project like UML
 * to do networking.
 *
 * Faster is to do virtio bonding in kernel.  Doing this 1:1 would be
 * completely generic ("here's my vring, attach to your vring") and would work
 * for any traffic.  Of course, namespace and permissions issues need to be
 * dealt with.  A more sophisticated "multi-channel" virtio_net.c could hide
 * multiple inter-guest channels behind one interface, although it would
 * require some manner of hotplugging new virtio channels.
 *
 * Finally, we could implement a virtio network switch in the kernel. */

[ drivers/lguest/x86/switcher_32.S ]
/* Lguest64 handles NMI.  This gave me NMI envy (until I looked at their
 * code).  It's worth doing though, since it would let us use oprofile in the
 * Host when a Guest is running. */

/* Lguest is meant to be simple: my rule of thumb is that 1% more LOC must
 * gain at least 1% more performance.  Since neither LOC nor performance can be
 * measured beforehand, it generally means implementing a feature then deciding
 * if it's worth it.  And once it's implemented, who can say no?
 *
 * This is why I haven't implemented this idea myself.  I want to, but I
 * haven't.  You could, though.
 *
 * The main place where lguest performance sucks is Guest page faulting.  When
 * a Guest userspace process hits an unmapped page we switch back to the Host,
 * walk the page tables, find it's not mapped, switch back to the Guest page
 * fault handler, which calls a hypercall to set the page table entry, then
 * finally returns to userspace.  That's two round-trips.
 *
 * If we had a small walker in the Switcher, we could quickly check the Guest
 * page table and if the page isn't mapped, immediately reflect the fault back
 * into the Guest.  This means the Switcher would have to know the top of the
 * Guest page table and the page fault handler address.
 *
 * For simplicity, the Guest should only handle the case where the privilege
 * level of the fault is 3 and probably only not present or write faults.  It
 * should also detect recursive faults, and hand the original fault to the
 * Host (which is actually really easy).
 *
 * Two questions remain.  Would the performance gain outweigh the complexity?
 * And who would write the verse documenting it? */

[ Documentation/lguest/lguest.c ]
/*
 * Mastery is done: you now know everything I do.
 *
 * But surely you have seen code, features and bugs in your wanderings which
 * you now yearn to attack?  That is the real game, and I look forward to you
 * patching and forking lguest into the Your-Name-Here-visor.
 *
 * Farewell, and good coding!
 * Rusty Russell.
 */