Overview
========

KAISER is a countermeasure against attacks on kernel address
information.  There are at least three existing, published,
approaches using the shared user/kernel mapping and hardware features
to defeat KASLR.  One approach referenced in the paper locates the
kernel by observing differences in page fault timing between
present-but-inaccessable kernel pages and non-present pages.

When the kernel is entered via syscalls, interrupts or exceptions,
page tables are switched to the full "kernel" copy.  When the
system switches back to user mode, the user/shadow copy is used.

The minimalistic kernel portion of the user page tables try to
map only what is needed to enter/exit the kernel such as the
entry/exit functions themselves and the interrupt descriptor
table (IDT).  There are a few unnecessary things that get mapped
such as the first C function when entering an interrupt (see
comments in kaiser.c).

This helps to ensure that side-channel attacks that leverage the
paging structures do not function when KAISER is enabled.  It can be
enabled by setting CONFIG_KAISER=y

Page Table Management
=====================

When KAISER is enabled, the kernel manages two sets of page
tables.  The first copy is very similar to what would be present
for a kernel without KAISER.  This includes a complete mapping of
userspace that the kernel can use for things like copy_to_user().

The second (shadow) is used when running userspace and mirrors the
mapping of userspace present in the kernel copy.  It maps a only
the kernel data needed to enter and exit the kernel.

The shadow is populated by the kaiser_add_*() functions.  Only
kernel data which has been explicity mapped will appear in the
shadow copy.  These calls are rare at runtime.

For a new userspace mapping, the kernel makes the entries in its
page tables like normal.  The only difference is when the kernel
makes entries in the top (PGD) level.  In addition to setting the
entry in the main kernel PGD, a copy if the entry is made in the
shadow PGD.

For user space mappings the kernel creates an entry in the kernel
PGD and the same entry in the shadow PGD, so the underlying page
table to which the PGD entry points is shared down to the PTE
level.  This leaves a single, shared set of userspace page tables
to manage.  One PTE to lock, one set set of accessed bits, dirty
bits, etc...

Overhead
========

Protection against side-channel attacks is important.  But,
this protection comes at a cost:

1. Increased Memory Use
  a. Each process now needs an order-1 PGD instead of order-0.
     (Consumes 4k per process).
  b. The pre-allocated second-level (p4d or pud) kernel page
     table pages cost ~1MB of additional memory at boot.  This
     is not totally wasted because some of these pages would
     have been needed eventually for normal kernel page tables
     and things in the vmalloc() area like vmemmap[].
  c. Statically-allocated structures and entry/exit text must
     be padded out to 4k (or 8k for PGDs) so they can be mapped
     into the user page tables.  This bloats the kernel image
     by ~20-30k.
  d. The shadow page tables eventually grow to map all of used
     vmalloc() space.  They can have roughly the same memory
     consumption as the vmalloc() page tables.

2. Runtime Cost
  a. CR3 manipulation to switch between the page table copies
     must be done at interrupt, syscall, and exception entry
     and exit (it can be skipped when the kernel is interrupted,
     though.)  Moves to CR3 are on the order of a hundred
     cycles, and are required every at entry and every at exit.
  b. Task stacks must be mapped/unmapped.  We need to walk
     and modify the shadow page tables at fork() and exit().
  c. Global pages are disabled.  This feature of the MMU
     allows different processes to share TLB entries mapping
     the kernel.  Losing the feature means potentially more
     TLB misses after a context switch.
  d. Process Context IDentifiers (PCID) is a CPU feature that
     allows us to skip flushing the entire TLB when switching
     page tables.  This makes switching the page tables (at
     context switch, or kernel entry/exit) cheaper.  But, on
     systems with PCID support, the context switch code must flush
     both the user and kernel entries out of the TLB, with an
     INVPCID in addition to the CR3 write.  This INVPCID is
     generally slower than a CR3 write, but still on the order of
     a hundred cycles.
  e. The shadow page tables must be populated for each new
     process.  Even without KAISER, the shared kernel mappings
     are created by copying top-level (PGD) entries into each
     new process.  But, with KAISER, there are now *two* kernel
     mappings: one in the kernel page tables that maps everything
     and one in the user/shadow page tables mapping the "minimal"
     kernel.  At fork(), a copy of the portion of the shadow PGD
     that maps the minimal kernel structures is needed in
     addition to the normal kernel PGD.
  f. In addition to the fork()-time copying, there must also
     be an update to the shadow PGD any time a set_pgd() is done
     on a PGD used to map userspace.  This ensures that the kernel
     and user/shadow copies always map the same userspace
     memory.
  g. On systems without PCID support, each CR3 write flushes
     the entire TLB.  That means that each syscall, interrupt
     or exception flushes the TLB.

Possible Future Work:
1. We can be more careful about not actually writing to CR3
   unless its value is actually changed.
2. Compress the user/shadow-mapped data to be mapped together
   underneath a single PGD entry.
3. Re-enable global pages, but use them for mappings in the
   user/shadow page tables.  This would allow the kernel to
   take advantage of TLB entries that were established from
   the user page tables.  This might speed up the entry/exit
   code or userspace since it will not have to reload all of
   its TLB entries.  However, its upside is limited by PCID
   being used.
4. Allow KAISER to enabled/disabled at runtime so folks can
   run a single kernel image.

Debugging:

Bugs in KAISER cause a few different signatures of crashes
that are worth noting here.

 * Crashes in early boot, especially around CPU bringup.  Bugs
   in the trampoline code or mappings cause these.
 * Crashes at the first interrupt.  Caused by bugs in entry_64.S,
   like screwing up a page table switch.  Also caused by
   incorrectly mapping the IRQ handler entry code.
 * Crashes at the first NMI.  The NMI code is separate from main
   interrupt handlers and can have bugs that do not affect
   normal interrupts.  Also caused by incorrectly mapping NMI
   code.  NMIs that interrupt the entry code must be very
   careful and can be the cause of crashes that show up when
   running perf.
 * Kernel crashes at the first exit to userspace.  entry_64.S
   bugs, or failing to map some of the exit code.
 * Crashes at first interrupt that interrupts userspace. The paths
   in entry_64.S that return to userspace are sometimes separate
   from the ones that return to the kernel.
 * Double faults: overflowing the kernel stack because of page
   faults upon page faults.  Caused by touching non-kaiser-mapped
   data in the entry code, or forgetting to switch to kernel
   CR3 before calling into C functions which are not kaiser-mapped.
 * Failures of the selftests/x86 code.  Usually a bug in one of the
   more obscure corners of entry_64.S
 * Userspace segfaults early in boot, sometimes manifesting
   as mount(8) failing to mount the rootfs.  These have
   tended to be TLB invalidation issues.  Usually invalidating
   the wrong PCID, or otherwise missing an invalidation.
