Transcript exoKernels.pps

Application Performance and Flexibility on
Exokernel Systems
M. F. Kaashoek, D.R. Engler, G.R.
Ganger,H.M. Briceno, R. Hunt, D.
Mazieres, T. Pinckney, R. Grimm, J.
Jannotti, K. Mackenzie
MIT LCS
Appears in SOSP 1997
Presented by: David R. Choffnes
CS 443 Advanced OS
David R. Choffnes, Spring 2005
Why Exokernels?
Application demands vary widely
– Current OSs provide high-level interfaces and
attempt to optimize for some “average-case”
workload
– Penalty for certain applications can be high
– It would be better to give these untrusted
applications direct access to hardware
2
Exokernel Architecture Overview
Goals
– Limit OS (kernel) functionality to managing protection (and
safe sharing) of hardware resources
– Allow “applications” to manage resources
• Many of these “applications” will perform management typical
of monolithic OSs – called library operating systems
(libOSes)
• Traditional applications will then link to the libOSes instead of
linking to a monolithic kernel
Claim
– Any programmer can specialize at libOS without affecting
the rest of the system
Too much responsibility in hands of app.
programmer?
3
Conventional OS user interface
User process
User process
System calls
Kernel
protects and manages
all the system resources
4
Exokernels
User process
User process
Exokernel
protects but
does not manage
system resources
5
LibOSes
User process
User process
libOS
libOS
Exokernel
6
Purpose of Paper
Proof of concept: show that exokernels can
introduce new interfaces that separate
protection from management
Show that exokernels do not limit
performance of ordinary apps
Show that apps can use exokernel to improve
performance compared to traditional kernel
7
Related Work
(“Anything you can do I can do better”)
Recast the debate over kernel architecture
– Since exokernel operates at such a low level, it is
“orthogonal” to the debate over monolithic/ukernel
– Anything done to improve performance in a
ukernel approach can and should be done in
exokernel applications
Virtual Machines
– Solve the extensibility problem, but
compartmentalize applications, which can lead to
inefficiency
Exokernels allow downloading of code
8
Exokernels in a Nutshell (1)
Exokernel principles
– Separate protection from management
• Allocation, revocation, sharing and tracking of ownership
– Expose allocation
• Allows apps to fully control what they allocate
– Expose names
• Allows apps to use physical names, eliminating overhead of
virtualization
– Expose revocation
• Allow apps to recover from revocation instead of simply killing them
– Expose information
• Allow app to know just about everything that the kernel knows
9
Exokernels in a Nutshell (2)
Kernel support for protected abstractions
– Challenge: allow high-level access control without
mandating an implementation or hindering
application control of resources
– Design techniques
• Same access control for all resources
• Binding of hardware resources as software abstractions
– Buffer cache example
• Support downloading of code for abstractions
– Allows extensibility to new forms of protection not
represented by hardware
– Abstractions reside in kernel (cheap shot at
ukernels)
10
Microkernels in a Nutshell (3)
Protected sharing
– LibOSes can trust applications not to muck with
resources provided by exokernel, but cannot trust
other libOSes that may have the same access.
• E.g., the fork problem
– Exokernel provides four mechanisms to maintain
invariants in shared abstractions
• Software regions (region can be read only through
system call)
• Hierarchically-named capabilities (protect against buggy
children)
• Wakeup predicates (protect against hanging)
• Robust critical sections (by disabling software interrupts)
– Eliminates the need for locks
– Can still lead to livelock?
11
Microkernels in a Nutshell (3)
– Optimize shared abstraction implementation
according to level of trust
• Mutual trust
– Similar to monolithic kernel programming
• Unidirectional
– Protect shared resources from untrusted side
• Mutual distrust (defensive programming)
– Worst case and rare
– Must account for all kinds of attacks/problems
12
Multiplexing Disk Storage
(or: How I Learned to Stop Worrying and Love the Exokernel)
Challenge
– Support multiple concurrent file systems without
partitioning
– Give as much control as possible to libFSes as
possible while protecting files from unauthorized
access
– Allow file systems to define arbitrary file formats
Implementation: Stable Storage System
–
–
–
–
Simple/lightweight capability for new file formats
Allow safe sharing of disk blocks among libFSes
Efficient access
Allow cache sharing while supporting invariants
13
XN (One Hack to Rule them All)
Provides
– Access to storage at level of disk blocks
– Public-readable buffer cache registry
– Free maps
Purpose is to determine the access rights of a
principal to a given disk block efficiently
Challenge: multiple file formats
Solution: UDF (untrusted deterministic
functions)
– Translate metadata from associated file format to
a language that the kernel can understand
– Stored in disk structures called templates
14
XN (continued)
UDF allows libFS to define each of its types once per
file system
– Better than separating capabilities from (meta)data blocks or
using self-descriptive blocks
Requirements for XN
– Every operation on disk data must be guarded
• Implemented at bind time (when page associated with disk
block is loaded into page table)
– Determine access rights unambiguously (use libFS’s
metadata)
– Prevent crashes from corrupting FS (no writing pointers to
uninitialized data, no freeing block until there are no pointers
to it)
15
XN (continued)
For protected sharing among libFS’s:
– Coherent caching of disk blocks (in-kernel,
systemwide protected cache registry)
– Atomic metadata updates (lock cache registry
entries)
– Well-formed updates (use libFS’s UDF)
16
XN “Disk Ordering”
Preventing FS corruption
– Use reference counting for deallocation
– Use tainted blocks to indicate pointers to
uninitialized data
• Tainted blocks cannot be written to disk
• If FS is marked “temporary” or is not connected to a FS
root, operations on tainted pages are allowed
17
XN Buffer Cache Registry
Tracks mapping and state
BCR is mapped into every app’s memory
space
XN allows libFS to determine its own
caching/backing store policies
XN allows any process to flush dirty pages to
disk (even w/o write access to such pages)
18
More XN (Because 5 slides aren’t enough)
XN Usage
– Lots of details you don’t need to know right now
C-FFS
– FFS for Xok
– Uses kernel downloading, but should use UDFs
– Demonstrates that traditional FS abstractions and
requirements can be mapped to exokernel
capabilities without “much” effort
Future work
– Wait, you haven’t tested this with more than one
FS!?
19
Xok/ExOS
(aka, worst OS name since The Hurd)
Xok safely multiplexes physical resources
– CPU: Round-robin scheduling
– Network: Dynamic packet filters
– RAM: Apps must use system call to modify page
table, but Xok allows user-level pagers
– Wakeup predicates: evaluated when an app is
about to be executed  low overhead
– Access control: hierarchically-named capabilities
20
ExOS 1.0
ExOS: libOS that supports most of the abstractions in
4.4BSD
Primary goals: simplicity and flexibility
Implemenation
– UNIX abstractions
• Most shared state is protected using Xok’s protection
mechanisms, but some simply uses shared memory
• Bogus claim of fault isolation
• Processes
– Memory mapping tricks to improve efficiency
– Fork trickiness for lazy page copying
• IPC: software regions, “directed yield”, timers, upcalls…
• File descriptors use shared memory, allow apps to install own
file functions
• Files: (already discussed) mounting done via shared memory
21
ExOS 1.0 Implemenation (cont)
Shared libraries
– ExOS maps shared libraries into address space at
load time
– Significantly reduces memory consumption for
exokernel; similar in size to normal UNIX
– No dynamic linking cost
22
Application Performance (Finally!)
Base performance of unaltered UNIX apps
linked against ExOS is comparable to
OpenBSD and FreeBSD
Some apps perform faster on ExOS due to
file system (no detailed description why)
Estimated protection cost appears to be low
23
Exploiting Extensibility (1)
Fast binary emulation allows large
improvements in simple operations (getpid)
XCP improves copy performance by a factor
of two
– Take advantage of access to hardware to perform
copy using DMA without CPU touching data
24
Exploiting Extensibility (2)
Cheetah HTTP/1.0 Server – integration with
Disk, TCP/IP stack allow significant
performance improvement
25
Exploiting Extensibility (3)
Global performance
– Weakest point, uses ridiculously unrealistic
workloads, then claims that performance is OK
– Does not seem to support RT apps
– Lots of hand-waving about deriving info for global
tuning
26
Experience
“Clear” Advantages
– Exposing kernel data structures
• Mapping into user space eliminates system call overhead
• Allows apps to come up with new ways of using info
– CPU interface
• Allows explicit control over synchronization
– Libraries
• Greatly simplifies development process by removing the
“reboot” step
Costs
– Not easy to design exokernel interfaces
– Information can be lost between interfaces
– Self paging is difficult
27
Lessons
If I have time for this, which I doubt, I’ll wing it
28
Conclusion
Exokernels are feasible!
Exokernels can be used to provide services
to unmodified apps meant for conventional
OSes!
Exokernels can actually boost performance
compared to existing popular/conventional
OSes!
Easier to develop
Open questions, but still viable.
29