pageexec.txt

1. Design

   The goal of PAGEEXEC is to implement the non-executable page feature using
   the paging logic of IA-32 based CPUs.

   Traditionally page protection is implemented by using the features of the
   CPU Memory Management Unit. Unfortunately IA-32 lacks the hardware support
   for execution protection, i.e., it is not possible to directly mark a page
   as executable/non-executable in the paging related structures (the page
   directory (pde) and table entries (pte)). What still makes it possible to
   implement non-executable pages is the fact that from the Pentium series on
   the Intel CPUs have a split Translation Lookaside Buffer for code and data
   (AMD CPUs have a split TLB since the K5 series however due to its
   organization it is usable for our purposes only since the K7 core based
   CPUs).

   The role of the TLB is to act as a cache for virtual/physical address
   translations that the CPU has to perform for every single memory access (be
   that instruction fetch or data read/write). Without the TLB the CPU would
   have to perform an expensive page table walk operation for every such
   memory access and obviously that would be detrimental to performance.

   The TLB operates in a simple manner: whenever the CPU wants to access a
   given virtual address, it will first check whether the TLB has a cached
   translation or not. On a TLB hit it will take the physical address directly
   from the TLB, otherwise it will perform a page table walk to look up the
   required translation and cache the result in the TLB as well (if the page
   table walk is unable to find the translation or the result is in conflict
   with the access type, e.g., a write to a read-only page, then the CPU will
   instead raise a page fault exception). Note that hardware assisted page
   table walking and automatic TLB loading are features specific to IA-32,
   other CPUs may have or need software assistance in this operation. Since
   the TLB has a finite size, sooner or later it becomes full and the CPU will
   have to purge entries to make room for new translations (on IA-32 this is
   again automatically done in hardware). Software can also purge TLB entries
   by either removing all translations (e.g., whenever a userland context
   switch happens) or those corresponding to a specific virtual address.

   As mentioned already, from the Pentium on Intel CPUs have a split TLB, that
   is, virtual/physical translations are cached in two independent TLBs
   depending on the access type: instruction fetch related memory accesses will
   load the ITLB, everything else loads the DTLB (if both kinds of accesses are
   made to a page then both TLBs will have an entry). TLB entry replacement
   works also on a per TLB basis except for the software initiated purges which
   act on both.

   The above described TLB behaviour means that software has explicit control
   over ITLB/DTLB loading: it can get notified on hardware TLB load attempts
   if it sets up the page tables so that such attempts will fail and trigger
   a page fault exception, and it can also initiate a TLB load by making the
   appropriate memory access to have the CPU walk the page tables and load one
   of the TLBs. This in turn is the key to implement non-executable pages:
   such pages can be marked either as non-present or requiring supervisor level
   access in the page tables hence userland memory accesses would raise a page
   fault. The page fault handler can then decide whether it was an instruction
   fetch attempt (by comparing the fault address to that of the instruction
   that raised the fault) or a legitimate data access. In the former case we
   will have detected an execution attempt in a non-executable page and can
   act accordingly (terminate the task), in the latter case we can just change
   the affected page table entry temporarily to allow user level access and
   have the CPU load it into the DTLB (we will of course have to restore the
   page table entry to the old state so that further page table walks will
   again raise a page fault).

   The decision between using non-present or supervisor mode page table entries
   for marking a page as non-executable comes down to performance in the end,
   the latter being less intrusive because kernel initiated data accesses to
   userland pages will not raise a page fault.

   To sum it up, PAGEEXEC as implemented in PaX overloads the meaning of the
   User/Supervisor bit in the ptes to mean the executable/non-executable status
   and also makes sure that data accesses to non-executable pages still work as
   before.


2. Implementation

   PAGEEXEC requires two sets of changes in Linux: the kernel has to be taught
   that the i386 architecture can do the proper non-executable semantics, and
   next we have to deal with the special page faults that require kernel
   assisted DTLB loading.

   The low-level definitions of the capabilities of the paging logic are in
   include/asm-i386/pgtable.h. Here we simply redefine the constants that are
   used for creating the ptes of non-executable pages. One such use of these
   constants is the protection_map[] array defined in mm/mmap.c which is
   referenced whenever the kernel sets up a pte for a userland mapping. Since
   PAGEEXEC can be disabled on a per task basis we have to modify all code
   that accesses this array so that we provide an executable pte even if it
   was not explicitly requested. Affected files include fs/exec.c (where the
   stack pages are set up), mm/mprotect.c, mm/filemap.c and mm/mmap.c. The
   changes in the latter two cooperate in a non-trivial way: do_mmap_pgoff()
   creates executable non-anonymous mappings by default and it is the job of
   generic_file_mmap() to turn it into a non-executable one (as the mapping
   turned out to be a file mapping). This logic ensures that non-anonymous
   mappings of devices remain executable regardless of PAGEEXEC. We opted for
   this approach to remain as compatible as possible (by not affecting all
   non-anonymous mappings) yet still make use of the non-executable feature
   in the most frequently encountered case.

   The kernel assisted DTLB loading logic is in the IA-32 specific page fault
   handler which in Linux is do_page_fault() in arch/i386/mm/fault.c. For
   easier code maintenance we created our own page fault entry point called
   pax_do_page_fault() which gets called first from the low-level page fault
   exception handler page_fault found in arch/i386/kernel/entry.S.

   First we verify that the given page fault is ours by checking for a userland
   fault caused by access conflict (vs. not present page). Next we pay special
   attention to faults caused by an instruction fetch since this means an
   attempt of code execution in a non-executable page. Such faults are easily
   identified by checking for a read access where the target address of the
   page fault is equal to the userland instruction pointer (which is saved by
   the CPU at the time of the fault for us). The default action is of course a
   task termination along with a log message, only EMUTRAMP when enabled can
   change it (see separate document).

   Next we prepare the mask for setting up the special pte for loading the
   DTLB and then we acquire the spinlock that guards MMU state changes (since
   we are about to cause such a change ourselves). Holding the spinlock is
   also necessary for looking up the target pte that we will modify and load
   into the DTLB. If the pte state we looked up no longer corresponds to the
   fault type then we must have raced with other MMU state changing code and
   pass down the fault to the original fault handler. It is also the time when
   we can identify (and pass down) copy-on-write page faults that have the
   same fault type but a different pte state than what is caused by the
   PAGEEXEC logic.

   Finally we change the pte to allow userland accesses to the given page then
   perform a dummy read memory access that will have the CPU page table walk
   logic load it into the DTLB and then we change the state back to be in
   supervisor mode. There is a trick in this part of the code that is worth
   a few words. If the TLB already has an entry for a given virtual/physical
   translation then initiating a memory access will not cause a page table
   walk, that is, for our DTLB loading to work we would have to ensure that
   the DTLB has no entries for our virtual address. It turns out that different
   members of the Intel IA-32 family have a different behaviour when the CPU
   raises a page fault during a page table walk (which is our case): the old
   Pentium (but not the MMX version) CPUs would still cache the translation
   if it described a present mapping but had an access conflict (which is our
   case since we have a supervisor mode pte that is accessed while executing
   in user mode) whereas newer CPUs (P6 core based ones, P4 and probably future
   CPUs as well) would not cache them at all. This means that in the second
   case we can be sure that the DTLB has no translations for our target virtual
   address and can omit a very expensive 'invlpg' instruction (it sped up the
   fast path by some 20% on a P3).