Citation:
Kaashoek, M.F. et al., "Application Performance and Flexibility on Exokernel
Systems", Proceedings of the 16th ACM Symposium on Operating Systems Principles,
Saint-Malo, France, October 1997, pp. 52-65.

* Summary

The exokernel operating system architecture safely gives untrusted software
efficient control over hardware and software resources by separating
management from protection. The paper evaluates the exokernel architecture
by measuring end-to-end application performance on Xok, an exokernel for 
x86-based computers, and comparing Xok's performance to the performance of
two widely used 4.4BSD UNIX systems.

* Exokernel

The goal of an exokernel is to give efficient control of resources to untrusted
applications in a secure, multi-user system. The following principles are 
followed to achieve this goal:
(1) Separate Protection from Managment - primitives are provided at the lowest
    level possible required for protection, and resource managment is limited
    to only those operations necessary for protection (allocation, revocation,
    sharing, and ownership tracking)
(2) Expose Allocation - apps allocate resource explicitly
(3) Expose Names - exokernels use physical names whenever possible
(4) Expose Revocation - revocation policies are exposed to apps, allowing them
    to choose which instance of a resource to give up
(5) Expose Information - exokernels collect data that apps cannot easily derive
    locally and share this system information

* Protected Sharing

Although libOSes can trust applications they link with, they cannot necessarily
trust other libOSes with access to the same resources. Exokernel provides four
mechanisms libOSes can use to maintain invariants in shared abstractions. 
Software regions, or areas of memory that can only be read or written through
system calls, provide sub-page protection and fault isolation. Hierarchically
named capabilities can be created on-the-fly, and must be specified explicitly
on each system call. Wakeup predicates are small kernel-downloaded functions 
that wake up processes when arbitrary conditions become true. Finally, robust
critical sections are provided and implemented by disabling software interrupts,
eliminating the need to trust other processes as required by locks.

Three levels of trust determine what optimizations can be used by the 
implementation of a shared abstraction: mutual trust, unidirectional trust, and
mutual distrust.

* Multiplexing Stable Storage

To allow libFSes to perform their own file managment, an exokernel stable
storage system must satisfy four requirements. First, creating new file formats
should be simple and lightweight. Second, the protection substrate should allow
multiple libFSes to safely share files at the raw disk block and metadata level.
Third, the storage system must be efficient, as close to raw hardware 
performance as possible. Fourth, the storage system should facilitate cache
sharing among libFSes, and allow them to easily address problems of cache
coherence, security, and concurrency.

XN, the exokernel stable storage system, provides block-level access to stable
storage, exporting a buffer cache registry as well as free maps and other
on-disk structures. Since libFSes provide their own filesystem metadata layouts
unknown to exokernel, determining access rights to disk blocks is difficult.
Thus, XN uses untrusted deterministic functions (UDFs), which are metadata
translation functions specific to each file type. UDFs are written by designers
of new file system types in a restricted language that ensures UDFs are
deterministic (output depends only on input). UDFs allow the filesystem
specific metadata to be tranformed into a format that XN understands, so that
it can provide the appropriate protection.