Recovering Device Drivers

Recovering Device Drivers
Michael M. Swift, Muthukaruppan Annamalai, Brian N. Bershad, and Henry M. Levy
Department of Computer Science and Engineering
University of Washington
Seattle, WA 98195 USA
{mikesw,muthu,bershad,levy}@cs.washington.edu
Abstract
Earlier failure-isolation systems within the kernel
were designed to prevent driver failures from corrupting
This paper presents a new mechanism that enables applications
the kernel itself [33]. In these systems, the kernel unloads
to run correctly when device drivers fail. Because device drivers
are the principal failing component in most systems, reducing
a failed driver and then restarts it from a safe initial state.
driver-induced failures greatly improves overall reliability. Ear-
While isolation techniques can reduce the frequency of
lier work has shown that an operating system can survive driver
system crashes, applications using the failed driver can
failures [33], but the applications that depend on them cannot.
still crash. These failures occur because the driver loses
Thus, while operating system reliability was greatly improved,
application state when it restarts, causing applications to
application reliability generally was not.
receive erroneous results. Most applications are unpre-
To remedy this situation, we introduce a new operating sys-
pared to cope with this. Rather, they reﬂect the conven-
tem mechanism called a shadow driver. A shadow driver mon-
tional failure model: drivers and the operating system ei-
itors device drivers and transparently recovers from driver fail-
ther fail together or not at all.
ures. Moreover, it assumes the role of the failed driver during
This paper presents a new mechanism, called a
recovery. In this way, applications using the failed driver, as
shadow driver, that improves overall system reliability
well as the kernel itself, continue to function as expected.
We implemented shadow drivers for the Linux operating
by concealing a driver’s failure from its clients while re-
system and tested them on over a dozen device drivers. Our re-
covering from the failure. During normal operation, the
sults show that applications and the OS can indeed survive the
shadow tracks the state of the real driver by monitoring all
failure of a variety of device drivers. Moreover, shadow drivers
communication between the kernel and the driver. When
impose minimal performance overhead. Lastly, they can be in-
a failure occurs, the shadow inserts itself temporarily in
troduced with only modest changes to the OS kernel and with
place of the failed driver, servicing requests on its behalf.
no changes at all to existing device drivers.
While shielding the kernel and applications from the fail-
ure, the shadow driver restores the failed driver to a state
1
Introduction
where it can resume processing requests.
Our design for shadow drivers reﬂects four principles:
Improving reliability is one of the greatest challenges for
commodity operating systems. System failures are com-
1. Device driver failures should be concealed from the
monplace and costly across all domains: in the home,
driver’s clients. If the operating system and applica-
in the server room, and in embedded systems, where the
tions using a driver cannot detect that it has failed,
existence of the OS itself is invisible. At the low end,
they are unlikely to fail themselves.
failures lead to user frustration and lost sales. At the high
2. Recovery logic should be centralized in a single sub-
end, an hour of downtime from a system failure can result
system. We want to consolidate recovery knowledge
in losses in the millions [16].
in a small number of components to simplify the im-
Most of these system failures are caused by the oper-
plementation.
ating system’s device drivers. Failed drivers cause 85%
of Windows XP crashes [30], while Linux drivers have
3. Driver recovery logic should be generic. The in-
seven times the bug rate of other kernel code [14]. A
creased reliability offered by driver recovery should
failed driver typically causes the application, the OS ker-
not be offset by potentially destabilizing changes to
nel, or both to crash or stop functioning as expected.
the tens of thousands of existing drivers. There-
Hence, preventing driver-induced failures improves over-
fore, the architecture must enable a single shadow
all system reliability.
driver to handle recovery for a large number of de-
vice drivers.

4. Recovery services should have low overhead when
and more importantly, the shadow is not a replica of the
not needed. The recovery system should impose rel-
device driver: it implements only the services needed to
atively little overhead for the common case (that is,
manage recovery of the failed driver and to shield appli-
when drivers are operating normally).
cations from the recovery. For this reason, the shadow is
typically much simpler than the driver it shadows.
Overall, these design principles are intended to minimize
Another common recovery approach is to restart ap-
the cost required to make and use shadow drivers while
plications after a failure.
Many systems periodically
maximizing their value in existing commodity operating
checkpoint application state [26, 27, 29], while others
systems.
combine checkpoints with logs [2, 5, 31]. These sys-
We implemented the shadow driver architecture for
tems transparently restart failed applications from their
sound, network, and IDE storage drivers on a version
last checkpoint (possibly on another machine) and re-
of the Linux operating system. Our results show that
play the log if one is present. Shadow drivers take a
shadow drivers: (1) mask device driver failures from ap-
similar approach by replaying a log of requests made to
plications, allowing applications to run normally during
drivers. Recent work has shown that this approach is
and after a driver failure, (2) impose minimal perfor-
limited when recovering from application faults: appli-
mance overhead, (3) require no changes to existing ap-
cations often become corrupted before they fail; hence,
plications and device drivers, and (4) integrate easily into
their logs or checkpoints may also be corrupted [10, 25].
an existing operating system.
Shadow drivers reduce this potential by logging only a
This paper describes the design, implementation and
small subset of requests. Furthermore, application bugs
performance of shadow drivers. The following section re-
tend to be deterministic and recur after the application is
views general approaches to protecting applications from
restarted [11]. Driver faults, in contrast, often cause tran-
system faults. Section 3 describes device drivers and the
sient failures because of the complexities of the kernel
shadow driver design and components. Section 4 presents
execution environment [34].
the structure of shadow drivers and the mechanisms re-
Another approach is simply to reboot the failed com-
quired to implement them in Linux. Section 5 presents
ponent, for example, unloading and reloading failed ker-
experiments that evaluate the performance, effectiveness,
nel extensions, such as device drivers [33]. Rebooting
and complexity of shadow drivers. The ﬁnal section sum-
has been proposed as a general strategy for building high-
marizes our work.
availability software [9]. However, rebooting forces ap-
plications to handle the failure, for example, reinitializing
2
Related Work
state that has been lost by the rebooted component. Few
This section describes previous research on recovery
existing applications do this [9], and those that do not
strategies and mechanisms. The importance of recovery
share the fate of the failed driver. Shadow drivers trans-
has long been known in the database community, where
parently restore driver state lost in the reboot, invisibly to
transactions [19] prevent data corruption and allow ap-
applications.
plications to manage failure. More recently, the need for
Shadow drivers rely on device driver isolation to
failure recovery has moved from specialized applications
prevent failed drivers from corrupting the OS or ap-
and systems to the more general arena of commodity sys-
plications. Isolation can be provided in various ways.
tems [28].
Vino [32] encapsulates extensions using software fault
A general approach to recovery is to run application
isolation [35] and uses transactions to repair kernel state
replicas on two machines, a primary and a backup. All
after a failure. Nooks [33] and Palladium [13] isolate ex-
inputs to the primary are mirrored to the backup. After
tensions in protection domains enforced by virtual mem-
a failure of the primary, the backup machine takes over
ory hardware. Microkernels [23, 38, 39] and their deriva-
to provide service. The replication can be performed
tives [15, 17, 20] force isolation by executing extensions
by the hardware [21], at the hardware-software inter-
in user mode.
face [8], at the system call interface [2, 5, 7], or at a mes-
Rather than concealing driver failures, these systems
sage passing or application interface [4]. Shadow drivers
all reﬂect a revealing strategy, one in which the applica-
similarly replicate all communication between the ker-
tion or user is made aware of the failure. The OS typi-
nel and device driver (the primary), sending copies to the
cally returns an error code, telling the application that a
shadow driver (the backup). If the driver fails, the shadow
system call failed, but little else (e.g., it does not indicate
takes over temporarily until the driver recovers. How-
which component failed or how the failure occurred). The
ever, shadows differ from typical replication schemes in
burden of recovery then rests on the application, which
several ways. First, because our goal is to tolerate only
must decide what steps to take to continue executing. As
driver failures, not hardware failures, both the shadow
previously mentioned, most applications cannot handle
and the “real” driver run on the same machine. Second,
the failure of device drivers [37], since driver faults typ-

ically crash the system. When a driver failure occurs,
OS Kernel
these systems expose the failure to the application, which
Kernel Interface
may then fail. By impersonating device drivers during
recovery, shadow drivers conceal errors caused by driver
failures and thereby protect applications.
Sound Driver
Several systems have narrowed the scope of recovery
Class Interface
to focus on a speciﬁc subsystem or component. For ex-
Sound Card
ample, the Rio ﬁle cache [12] provides high performance
Device Driver
by isolating a single system component, the ﬁle cache,
from kernel failures. Phoenix [3] provides transparent
recovery after the failure of a single problematic compo-
Sound Card
nent type, database connections in multi-tier applications.
Similarly, our shadow driver research focuses on recov-
ery for a single OS component type, the device driver,
Figure 1: A sample device driver. The device driver exports
which is the leading cause of OS failure. By abandoning
the services deﬁned by the device’s class interface and im-
general-purpose recovery, we transparently resolve a ma-
ports services from the kernel’s interface.
jor cause of application and OS failure while maintaining
a low runtime overhead.
portion of request processing. Device drivers may crash
in response to (1) the stream of requests from the kernel,
3
Device
Drivers
and
Shadow
Driver
both conﬁguration and I/O, (2) messages to and from the
Design
device, and (3) the kernel environment, which may raise
A device driver is a kernel-mode software component that
or lower power states, swap pages of memory, and inter-
provides an interface between the OS and a hardware de-
rupt the driver at arbitrary times. A driver bug triggered
vice1. The driver converts requests from the kernel into
solely by a sequence of conﬁguration or I/O requests is
requests to the hardware. Drivers rely on two interfaces:
called a deterministic failure. No generic recovery tech-
the interface that drivers export to the kernel that provides
nique can transparently recover from this type of bug, be-
access to the device, and the kernel interface that drivers
cause any attempt to complete an offending request may
import from the operating system. For example, Figure 1
trigger the bug [11]. In contrast, transient failures are
shows the kernel calling into a sound driver to play a tone;
triggered by additional inputs from the device or the op-
in response, the sound driver converts the request into a
erating system and occur infrequently.
sequence of I/O instructions that direct the sound card to
A driver failure that is detected and stopped by the
emit sound.
system before any OS, device, or application state is af-
In practice, most device drivers are members of a
fected is termed fail-stop. More insidious failures may
class, which is deﬁned by its interface. For example,
corrupt the system or application and never be detected.
all network drivers obey the same kernel-driver interface,
The system’s response to failure determines whether a
and all sound-card drivers obey the same kernel-driver
failure is fail-stop. For example, a system that detects
interface. This class orientation simpliﬁes the introduc-
and prevents accidental writes to kernel data structures
tion of new drivers into the operating system, since no
exhibits fail-stop behavior for such a bug, whereas one
OS changes are required to accommodate them.
that allows corruption does not.
In addition to processing I/O requests, drivers also
Appropriate OS techniques can ensure that drivers ex-
handle conﬁguration requests. Applications may conﬁg-
ecute in a fail-stop fashion [32, 33, 36]. For example, in
ure the device, for example, by setting the bandwidth of a
earlier work we described Nooks [33], a kernel reliability
network card or the volume for a sound card. Conﬁgura-
subsystem that executes each driver within its own in-
tion requests may change both driver and device behavior
kernel protection domain. Nooks detects faults through
for future I/O requests.
memory protection violations, excessive CPU usage, and
certain bad parameters passed to the kernel. When Nooks
3.1
Driver Faults
detects a failure, it stops execution within the driver’s pro-
tection domain and triggers a recovery process. We re-
Most drivers fail due to bugs that result from unexpected
ported that Nooks was able to detect approximately 75%
inputs or events [34]. For example, a driver may corrupt
of failures in synthetic fault-injection tests [33].
a data structure if an interrupt arrives during a sensitive
Shadow drivers can recover only from failures that are
1
both transient and fail-stop. Deterministic failures may
This paper uses the terms “device driver” and “driver” interchange-
ably; similarly, we use the terms “shadow driver” and “shadow” inter-
recur when the driver recovers, again causing a failure.
changeably.

In contrast, transient failures are triggered by environ-
Once the driver has restarted, the active-mode shadow
mental factors that are unlikely to persist during recov-
reintegrates the driver into the system. It re-establishes
ery. In practice, many drivers experience transient fail-
any application conﬁguration state downloaded into the
ures, caused by the complexities of the kernel execution
driver and then resumes pending requests.
environment (e.g. asynchrony, interrupts, locking proto-
A shadow driver is a “class driver,” aware of the in-
cols, and virtual memory) [1], which are difﬁcult to ﬁnd
terface to the drivers it shadows but not of their imple-
and ﬁx. Deterministic driver failures, in contrast, are
mentations. A single shadow driver implementation can
more easily found and ﬁxed in the testing phase of de-
recover from a failure of any driver in the class. The class
velopment because the failures are repeatable [18]. Re-
orientation has three key implications. First, an operat-
coverable failures must also be fail-stop, because shadow
ing system can leverage a few implementations of shadow
drivers conceal failures from the system and applications.
drivers to recover from failures in a large number of de-
Hence, shadow drivers require a reliability subsystem to
vice drivers. Second, implementing a shadow driver does
detect and stop failures before they are visible to applica-
not require a detailed understanding of the internals of the
tions or the operating system. Although shadow drivers
drivers it shadows. Rather, it requires only an understand-
may use any mechanism that provides these services, our
ing of those drivers’ interactions with the kernel. Finally,
implementation uses Nooks.
if a new driver is loaded into the kernel, no new shadow
driver is required as long as a shadow for that class al-
3.2
Shadow Drivers
ready exists. For example, if a new network interface card
and driver are inserted into a PC, the existing network
A shadow driver is a kernel agent that improves relia-
shadow driver can shadow the new driver without change.
bility for a single device driver. It compensates for and
Similarly, drivers can be patched or updated without re-
recovers from a driver that has failed. When a driver
quiring changes to their shadows. Shadow updating is
fails, its shadow restores the driver to a functioning state
required only to respond to a change in the kernel-driver
in which it can process I/O requests made before the fail-
programming interface.
ure. While the driver recovers, the shadow driver services
its requests.
3.3
Taps
Shadow drivers execute in one of two modes: pas-
sive or active.
In passive mode, used during normal
As we have seen, a shadow driver monitors communi-
(non-faulting) operation, the shadow driver monitors all
cation between a functioning driver and the kernel and
communication between the kernel and the device driver
impersonates one component to the other during failure
it shadows. This monitoring is achieved via replicated
and recovery. These activities are made possible by a
procedure calls: a kernel call to a device driver func-
new mechanism, called a tap. Conceptually, a tap is a
tion causes an automatic, identical call to a correspond-
T-junction placed between the kernel and its drivers. It
ing shadow driver function. Similarly, a driver call to a
can be set to replicate calls during passive mode and redi-
kernel function causes an automatic, identical call to a
rect them during recovery.
corresponding shadow driver function. These passive-
A tap operates in passive or active mode, correspond-
mode calls are transparent to the device driver and the
ing to the state of the shadow driver attached to it. During
kernel. They are not intended to provide any service to
passive-mode operation, the tap: (1) invokes the original
either party and exist only to track the state of the driver
driver, then (2) invokes the shadow driver with the pa-
as necessary for recovery.
rameters and results of the call. This operation is shown
In active mode, which occurs during recovery from a
in Figure 2.
failure, the shadow driver performs two functions. First,
On failure, the tap switches to active mode, shown in
it “impersonates” the failed driver, intercepting and re-
Figure 3. In this mode, it: (1) terminates all communica-
sponding to calls from the kernel. Therefore, the ker-
tion between the driver and kernel, and (2) redirects all in-
nel and higher-level applications continue operating in as
vocations to their corresponding interface in the shadow.
normal a fashion as possible. Second, the shadow driver
In active mode, both the kernel and the recovering device
impersonates the kernel to restart the failed driver, inter-
driver interact only with the shadow driver. Following
cepting and responding to calls from the restarted driver
recovery, the tap returns to its passive-mode state.
to the kernel. In other words, in active mode the shadow
Taps depend on the ability to dynamically dispatch all
driver looks like the kernel to the driver and like the driver
communication between the driver and the OS. Conse-
to the kernel. Only the shadow driver is aware of the de-
quently, all communication into and out of a driver be-
ception. This approach hides recovery details from the
ing shadowed must be explicit, such as through a proce-
driver, which is unaware that it is being restarted by a
dure call or a message. Most drivers operate this way,
shadow driver after a failure.
but some do not and cannot be shadowed. For example,

OS Kernel
requests for the driver’s services are redirected to an ap-
propriately prepared shadow driver. The shadow manager
Kernel Interface
then initiates the shadow driver’s recovery sequence to
restore the driver. When recovery ends, the shadow man-
ager returns the shadow driver and taps to passive-mode
Taps
operation so the driver can resume service.
Shadow
Sound Driver
Copies
Class Interface
Sound
Driver
3.5
Summary
Sound Driver
Class Interface
Our design simpliﬁes the development and integration of
Kernel
Interface
shadow drivers into existing systems. Each shadow driver
Sound Card
Device Driver
is a single module written with knowledge of the behav-
ior (interface) of a class of device drivers, allowing it to
conceal a driver failure and restart the driver after a fault.
Sound Card
A shadow driver, normally passive, monitors communi-
cation between the kernel and the driver. It becomes an
active proxy when a driver fails and then manages its re-
Figure 2: A sample shadow driver operating in passive
covery.
mode. Taps inserted between the kernel and sound driver
ensure that all communication between the two is passively
monitored by the shadow driver.
4
Shadow Driver Implementation
This section describes the implementation of shadow
OS Kernel
drivers in the Linux operating system [6]. We have imple-
Kernel Interface
mented shadow drivers for three classes of device drivers:
sound card drivers, network interface drivers, and IDE
storage drivers.
Taps
Shadow
Sound Driver
4.1
General Infrastructure
Class Interface
Sound
Driver
All shadow drivers rely on a generic service infrastructure
Sound Driver
that provides three functions. An isolation service pre-
Kernel
Class Interface
vents driver errors from corrupting the kernel by stopping
Interface
Sound Card
a driver on detecting a failure. A transparent redirection
Device Driver
mechanism implements the taps required for transparent
shadowing and recovery. Lastly, an object tracking ser-
vice tracks kernel resources created or held by the driver
Sound Card
so as to facilitate recovery.
Our shadow driver implementation uses Nooks to pro-
Figure 3: A sample shadow driver operating in active mode.
vide these functions. Through its fault isolation subsys-
The taps redirect communication between the kernel and
tem, Nooks [33] isolates drivers within separate kernel
the failed driver directly to the shadow driver.
protection domains. The domains use memory protec-
tion to trap driver faults and ensure the integrity of kernel
memory. Nooks interposes proxy procedures on all com-
kernel video drivers often communicate with usermode
munication between the device driver and kernel. We in-
applications through shared memory regions [22].
sert our tap code into these Nooks proxies to replicate
and redirect communication. Finally, Nooks tracks ker-
3.4
The Shadow Manager
nel objects used by drivers to perform garbage collection
Recovery is supervised by the shadow manager, which is
of kernel resources during recovery.
a kernel agent that interfaces with and controls all shadow
Our implementation adds a shadow manager to the
drivers. The shadow manager instantiates new shadow
Linux operating system. In addition to receiving failure
drivers and injects taps into the call interfaces between
notiﬁcations from Nooks, the shadow manager handles
the device driver and kernel. It also receives notiﬁca-
the initial installation of shadow drivers. In coordina-
tion from the fault-isolation subsystem that a driver has
tion with the kernel’s module loader, which provides the
stopped due to a failure.
driver’s class, the shadow manager creates a new shadow
When a driver fails, the shadow manager transitions
driver instance for a driver. Because a single shadow
its taps and shadow driver to active mode. In this mode,
driver services a class of device drivers, there may be

stop assumption to preserve persistent state (e.g., on disk)
Applications
from corruption. It can restore transient state (state that
Linux Kernel
is lost when the device resets) if it can force the device’s
Recovery Subsystem
clients to recreate that state, for example, by redrawing
Shadow Driver
Driver
Device
Shadow Driver
Shadow Manager
Shadow Driver
the contents of a frame buffer.
Driver
Device
Lastly, the shadow tracks all kernel objects that the
Driver
Device
driver allocated or received from the kernel. These ob-
Nooks Fault Isolation Subsystem
jects would otherwise be lost when the driver fails, caus-
Driver
Device
Protection
Taps
Object
Domains
ing a memory leak. For example, the shadow must record
Proxies
Table
all timer callbacks registered and all hardware resources
owned, such as interrupt lines and I/O memory regions.
Figure 4: The Linux operating system with several device
In many cases, passive-mode calls do no work and the
drivers and the driver recovery subsystem. New code com-
shadow returns immediately to the caller. For example,
ponents include the taps, the shadow manager and a set of
the dominant calls to a sound-card driver are read and
shadow drivers, all built on top of the Nooks driver fault
write, which record or play sound. In passive mode,
isolation subsystem.
the shadow driver implements these calls as no-ops, since
there is no need to copy the real-time sound data ﬂowing
through the device driver. For an ioctl call, however,
several instances of a shadow driver executing if there
the sound-card shadow driver logs the command and data
is more than one driver of a class present. The new in-
for the connection. Similarly, the shadow driver for an
stance shares the same code with all other instances of
IDE disk does little or no work in passive mode, since the
that shadow driver class.
kernel and disk driver handle all I/O and request queu-
Figure 4 shows the driver recovery subsystem, which
ing. Finally, for the network shadow driver, much of the
contains the Nooks fault isolation subsystem, the shadow
work is already performed by the Nooks object-tracking
manager, and a set of shadow drivers, each of which can
system, which keeps references to outstanding packets.
monitor one or more device drivers.
4.3
Active-Mode Recovery
4.2
Passive-Mode Monitoring
A driver typically fails by generating an illegal memory
In passive mode, a shadow driver records several types
reference or passing an invalid parameter across a ker-
of information.
First, it tracks requests made to the
nel interface. The kernel-level failure detector notices the
driver, enabling pending requests to execute correctly af-
failure and invokes the shadow manager, which locates
ter recovery. For connection-oriented drivers, the shadow
the appropriate shadow driver and directs it to recover the
driver records the state of each active connection, such as
failed driver. The three steps of recovery are: (1) stop-
offset or positioning information. For request-oriented
ping the failed driver, (2) reinitializing the driver from a
drivers, the shadow driver maintains a log of pending
clean state, and (3) transferring relevant shadow driver
commands and arguments. An entry remains in the log
state into the new driver.
until the corresponding request has been handled.
The shadow driver also records conﬁguration and
4.3.1
Stopping the Failed Driver
driver parameters that the kernel passes into the driver.
During recovery, the shadow uses this information to act
The shadow manager begins recovery by informing the
in the driver’s place, returning the same information that
responsible shadow driver that a failure has occurred. It
was passed in previously. This information also assists in
also switches the taps, isolating the kernel and driver from
reconﬁguring the driver to its pre-failure state when it is
one another’s subsequent activity during recovery. Af-
restarted. For example, the shadow sound driver keeps a
ter this point, the tap redirects all kernel requests to the
log of ioctl calls (command numbers and arguments)
shadow until recovery is complete.
that conﬁgure the driver. This log makes it possible to:
Informed of the failure, the shadow driver ﬁrst dis-
(1) act as the device driver by remembering the sound
ables execution of the failed driver. It also disables the
formats it supports, and (2) recover the driver by reset-
hardware device to prevent it from interfering with the OS
ting properties, such as the volume and sound format in
while not under driver control. For example, the shadow
use.
disables the driver’s interrupt request line. Otherwise, the
The shadow driver maintains only the conﬁguration
device may continuously interrupt the kernel and prevent
of the driver in its log. For stateful devices, such as frame
recovery. On hardware platforms with I/O memory map-
buffers or storage devices, it does not create a copy of the
ping, the shadow also removes the device’s I/O mappings
device state. Instead, a shadow driver depends on the fail-
to prevent DMAs into kernel memory.

To prepare for restarting the device driver, the shadow
state transfer depend on the device driver class. Some
garbage collects resources held by the driver. It retains
drivers are connection oriented. For these, the state con-
objects that the kernel uses to request driver services, to
sists of the state of the connections before the failure. The
ensure that the kernel does not see the driver “disappear”
shadow re-opens the connections and restores the state of
as it is restarted. The shadow releases the remaining re-
each active connection with conﬁguration calls. Other
sources.
drivers are request oriented. For these, the shadow re-
stores the state of the driver and then resubmits to the
4.3.2
Reinitializing the Driver
driver any requests that were outstanding when the driver
crashed.
The shadow driver next “reboots” the driver from a clean
As an example, for a failed sound card driver, the
state. Normally, restarting a driver requires reloading the
shadow driver resets the sound driver and all its open
driver from disk. However, we cannot assume that the
connections back to their pre-failures state. Speciﬁcally,
disk is functional during recovery. For this reason, when
the shadow scans its list of open connections and calls
creating a new shadow driver instance, the shadow man-
the open function in the driver to reopen each connec-
ager caches in the shadow instance a copy of the device
tion. The shadow then walks its log of conﬁguration com-
driver’s initial, clean data section. These sections tend to
mands and replays any commands that set driver proper-
be small. The driver’s code is kernel-read-only, so it is
ties.
not cached and can be reused from memory.
For some driver classes, the shadow cannot com-
The shadow restarts the driver by initializing the
pletely transfer its state into the driver. However, it may
driver’s state and then repeating the kernel’s driver ini-
be possible to compensate in other, perhaps less elegant,
tialization sequence. For some driver classes, such as
ways. For example, a sound driver that is recording sound
sound card drivers, this consists of a single call into the
stores the number of bytes it has recorded since the last
driver’s initialization routine. Other drivers, such as net-
reset. After recovery, the sound driver initializes this
work interface drivers, require additional calls to connect
counter to zero. Because no interface call is provided to
the driver into the network stack.
change the counter value, the shadow driver must insert
As the driver restarts, the shadow reattaches the driver
its “true” value into the return argument list whenever the
to its pre-failure kernel resources. During driver reboot,
application reads the counter to maintain the illusion that
the driver makes a number of calls into the kernel to dis-
the driver has not crashed. The shadow can do this be-
cover information about itself and to link itself into the
cause it receives control (on its replicated call) before the
kernel. For example, the driver calls the kernel to reg-
kernel returns to user space.
ister itself as a driver and to request hardware and ker-
After resetting driver and connection state, the
nel resources. The taps redirect these calls to the shadow
shadow must handle requests that were either outstanding
driver, which reconnects the driver to existing kernel data
when the driver crashed or arrived while the driver was
structures. Thus, when the driver attempts to register with
recovering. Unfortunately, shadow drivers cannot guar-
the kernel, the shadow intercepts the call and reuses the
antee exactly-once behavior for driver requests and must
existing driver registration, avoiding the allocation of a
rely on devices and higher levels of software to absorb
new one. For requests that generate callbacks, such as a
duplicate requests. For example, if a driver crashes after
request to register the driver with the PCI subsystem, the
submitting a request to a device but before notifying the
shadow emulates the kernel, making the same callbacks
kernel that the request has completed, the shadow cannot
to the driver with the same parameters. The driver also
know whether the request was actually processed. Dur-
acquires hardware resources. If these resources were pre-
ing recovery, the shadow driver has two choices: restart
viously disabled at the ﬁrst step of recovery, the shadow
in-progress requests and risk duplication, or cancel the re-
re-enables them, e.g., enabling interrupt handling for the
quest and risk lost data. For some device classes, such as
device’s interrupt line. In essence, the shadow driver ini-
disks or networks, duplication is acceptable. However,
tializes the recovering driver by calling and responding as
other classes, such as printers, may not tolerate dupli-
the kernel would when the driver starts normally.
cates. In these cases, the shadow driver cancels outstand-
ing requests, which may limit its ability to mask failures.
4.3.3
Transferring State to the New Driver
After this ﬁnal step, the driver has been reinitial-
ized, linked into the kernel, reloaded with its pre-failure
The ﬁnal recovery step restores the driver state that ex-
state, and is ready to process commands. At this point,
isted at the time of the fault, permitting it to respond to
the shadow driver notiﬁes the shadow manager, which
requests as if it had never failed. Thus, any conﬁguration
sets the taps to restore kernel-driver communication and
that either the kernel or an application had downloaded
reestablish passive-mode monitoring.
to the driver must be restored. The details of this ﬁnal

4.4
Active-Mode Proxying of Kernel Requests
drivers rely on explicit communication between the de-
vice driver and kernel. If driver-kernel communication
While a shadow driver is restoring a failed driver, it is also
takes place through an ad-hoc interface, such as shared
acting in place of the driver to conceal the failure and
memory, the shadow driver cannot monitor it. Third,
recovery from applications and the kernel. The shadow
shadow drivers assume that driver failure does not cause
driver’s response to a driver request depends on the driver
irreversible side effects. If a corrupted driver stores per-
class and request semantics. In general, the shadow will
sistent state (e.g., printing a bad check or writing bad data
take one of ﬁve actions: (1) respond with information that
on a disk), the shadow driver will not be able to correct
it has recorded, (2) silently drop the request, (3) queue the
that action.
request for later processing, (4) block the request until the
The effectiveness of shadow drivers is also limited by
driver recovers, or (5) report that the driver is busy and the
the abilities of the isolation and failure-detection subsys-
kernel or application should try again later. The choice of
tem. If this layer cannot prevent kernel corruption, then
strategy depends on the caller’s expectations of the driver.
shadow drivers cannot facilitate system recovery. In ad-
Writing a shadow driver that proxies for a failed driver
dition, if the fault-isolation subsystem does not detect a
requires knowledge of the kernel-driver interface, inter-
failure, then shadow drivers will not be properly invoked
actions, and requirements. For example, the kernel may
to perform recovery, and applications may fail. Detecting
require that some driver functions never block, while oth-
failures is difﬁcult because drivers are complex and may
ers always block. Some kernel requests are idempotent
respond to application requests in many ways. It may
(e.g., many ioctl commands), permitting duplicate re-
be impossible to detect a valid but incorrect return value;
quests to be dropped, while others return different results
for example, a sound driver may return incorrect sound
on every call (e.g., many read requests). The shadow
data when recording. As a result, no failure detector can
for a driver class uses these requirements to select the re-
detect every device driver failure. However, we support
sponse strategy.
class-based failure detectors that can detect violations of
Active proxying is simpliﬁed for driver interfaces that
a driver’s programming interface and reduce the number
support a notion of “busy.” By reporting that the device is
of undetected failures.
currently busy, shadow drivers instruct the kernel or ap-
Finally, shadow drivers may not be suitable for ap-
plication to block calls to a driver. For example, network
plications with real-time demands. During recovery, a
drivers in Linux may reject requests and turn themselves
device may be unavailable for several seconds without
off if their queues are full. The kernel then refrains from
notifying the application of a failure. These applications,
sending packets until the driver turns itself back on. Our
which should be written to tolerate failures, would be bet-
shadow network driver exploits this behavior during re-
ter served by a solution that restarts the driver but does not
covery by returning a “busy” error on calls to send pack-
perform active proxying.
ets. IDE storage drivers support a similar notion when
request queues ﬁll up. Sound drivers can report that their
4.6
Summary
buffers are temporarily full.
Our shadow sound-card driver uses a mix of all ﬁve
This section presented the details of our Linux shadow
strategies for emulating functions in its service interface.
driver implementation.
The shadow driver concept is
The shadow blocks kernel read and write requests,
straightforward: passively monitor normal operations,
which play or record sound samples, until the failed
proxy during failure, and reintegrate during recovery. Ul-
driver recovers. It processes ioctl calls itself, either by
timately, the value of shadow drivers depends on the de-
responding with information it captured or by logging the
gree to which they can be implemented correctly, efﬁ-
request to be processed later. For ioctl commands that
ciently, and easily in an operating system. The following
are idempotent, the shadow driver silently drops dupli-
section evaluates some of these questions both qualita-
cate requests. Finally, when applications query for buffer
tively and quantitatively.
space, the shadow responds that buffers are full. As a
result, many applications block themselves rather than
5
Evaluation
blocking in the shadow driver.
This section evaluates four key aspects of shadow drivers.
4.5
Limitations
1. Performance. What is the performance overhead of
As previously described, shadow drivers have limita-
shadow drivers during normal, passive-mode oper-
tions. First, shadow drivers rely on dynamic unloading
ation (i.e., in the absence of failure)? This is the
and reloading of device drivers. If a driver cannot be
dynamic cost of our mechanism.
reloaded dynamically, or will not reinitialize properly,
then a shadow cannot recover the driver. Second, shadow

Class
Driver
Device
Device Driver
Application Activity
Network
e1000
Intel Pro/1000 Gigabit Ethernet
Sound
• mp3 player (zinf) playing 128kb/s audio
(audigy driver)
• audio recorder (audacity) recording from
pcnet32
AMD PCnet32 10/100 Ethernet
microphone
3c59x
3COM 3c509b 10/100 Ethernet
• speech synthesizer (festival) reading a
e100
Intel Pro/100 Ethernet
text ﬁle
epic100
SMC EtherPower 10/100 Ethernet
• strategy game (Battle of Wesnoth)
Sound
audigy
SoundBlaster Audigy sound card
Network
• network send (netperf) over TCP/IP
emu10k1
SoundBlaster Live! sound card
(e1000 driver)
• network receive (netperf) over TCP/IP
• network ﬁle transfer (scp) of a 1GB ﬁle
sb
SoundBlaster 16 sound card
• remote window manager (vnc)
es1371
Ensoniq sound card
• network analyzer (ethereal) snifﬁng packets
cs4232
Crystal sound card
Storage
• compiler (make/gcc) compiling 788 C ﬁles
i810 audio
Intel 810 sound card
(ide-disk driver)
• encoder (LAME) converting 90 MB ﬁle .wav
Storage
ide-disk
IDE disk
to .mp3
• database (mySQL) processing the Wisconsin
ide-cd
IDE CD-ROM
Benchmark
Table 1: The three classes of shadow drivers and the Linux
Table 2: The applications used for evaluating shadow
drivers tested. We present results for the boldfaced drivers
drivers.
only, as the others behaved similarly.
5.1
Performance
2. Fault-Tolerance. Can applications that use a device
driver continue to run even after the driver fails?
To evaluate performance, we produced three OS conﬁgu-
We evaluate shadow driver recovery in the presence
rations based on the Linux 2.4.18 kernel:
of simple failures to show the beneﬁts of shadow
1. Linux-Native is the unmodiﬁed Linux kernel.
drivers compared to a system that provides failure
isolation alone.
2. Linux-Nooks is a version of Linux-Native that in-
cludes the Nooks fault isolation subsystem but no
3. Limitations. How reasonable is our assumption that
shadow drivers. When a driver fails, this system
driver failures are fail-stop? Using synthetic fault in-
restarts the driver but does not attempt to conceal
jection, we evaluate how likely it is that driver fail-
its failure.
ures are fail-stop.
3. Linux-SD is a version of Linux-Nooks that includes
4. Code size. How much code is required for shadow
our entire recovery subsystem, including the Nooks
drivers and their supporting infrastructure? We eval-
fault isolation subsystem, the shadow manager, and
uate the size and complexity of the shadow driver
our three shadow drivers.
implementation to highlight the engineering cost in-
tegrating shadow drivers into an existing system.
We selected a variety of common applications that
depend on our three device driver classes and measured
Based on a set of controlled application and driver ex-
their performance. The application names and behaviors
periments, our results show that shadow drivers: (1) im-
are shown in Table 2.
pose relatively little performance overhead, (2) keep ap-
Different applications have different performance
plications running when a driver fails, (3) are limited by
metrics of interest. For the disk and sound drivers, we ran
a system’s ability to detect that a driver has failed, and (4)
the applications shown in Table 2 and measured elapsed
can be implemented with a modest amount of code.
time. For the network driver, throughput is a more useful
The experiments were run on a 3 GHz Pentium 4 PC
metric; therefore, we ran the throughput-oriented network
with 1 GB of RAM and an 80 GB, 7200 RPM IDE disk
send and network receive benchmarks. For all drivers,
drive. We built and tested three Linux shadow drivers for
we also measured CPU utilization while the programs
three device-driver classes: network interface controller,
ran. All measurements were repeated several times and
sound card, and IDE storage device. To ensure that our
showed a variation of less than one percent.
generic shadow drivers worked consistently across device
Figure 5 shows the performance of Linux-Nooks and
driver implementations, we tested them on thirteen differ-
Linux-SD relative to Linux-Native. Figure 6 compares
ent Linux drivers, shown in Table 1. Although we present
CPU utilization for execution of the same applications
detailed results for only one driver in each class (e1000,
on the three OS versions. Both ﬁgures make clear that
audigy, and ide-disk), behavior across all drivers was sim-
shadow drivers impose only a small performance penalty
ilar.
compared to running with no isolation at all, and no
no additional penalty beyond that imposed by isolation

Relative Performance
bly to CPU utilization, because there are not many cross-
Sound
Network
Storage
100
ings and not much code to slow down. For the most disk-
intensive of the IDE storage applications, the database
95
benchmark, the kernel and driver interact only 290 times
per second. However, each call into the ide-disk driver
90
results in substantial work to process a queue of disk re-
quests. The TLB-induced slowdown doubles the time
85
database spent in the driver relative to Linux-Native and
Relative Performance (%)
increases the application’s CPU utilization from 21% to
80
27%. On the other hand, the network send benchmark
transmits 45,000 packets per second, causing 45,000 do-
audio
send
main crossings.
The driver does little work for each
recorder
speech
synth.
strategy
game
network
network
receive
compiler
encoder
database
mp3 player
packet, but the overall impact is visible in Figure 6, where
Linux-Native
Linux-Nooks
Linux-SD
CPU utilization for this benchmark increases from 28%
to 57% with driver fault isolation.
Figure 5: Comparative application performance, relative
In the case the actual shadowing, we see from a com-
to Linux-Native, for three conﬁgurations. The X-axis crosses
parison of the Linux-Nooks and Linux-SD bars in Fig-
at 80%.
ures 5 and 6 that the cost is small or negligible. As noted
CPU Utilization
in Section 4.2, many passive-mode shadow-driver func-
tions are no-ops. As a result, the incremental passive-
Sound
Network
Storage
100
mode performance cost over basic fault isolation is low
or unmeasurable in many cases.
80
In summary, then, the overall performance penalty of
60
shadow drivers during failure-free operation is low, sug-
gesting that shadow drivers could be used across a wide
40
range of applications and environments.
CPU Utilization (%) 20
5.2
Fault-Tolerance
0
Regardless of performance, the crucial question for
audio
send
shadow drivers is whether an application can continue
recorder
speech
synth.
strategy
game
network
network
receive
compiler
encoder
database
mp3 player
functioning following the failure of a device driver on
Linux-Native
Linux-Nooks
Linux-SD
which it relies. To answer this question, we tested 10
applications on the three conﬁgurations, Linux-Native,
Figure 6: Absolute CPU utilization by application for three
Linux-Nooks, and Linux-SD. For the disk and sound
conﬁgurations.
drivers, we again ran the applications shown in Table 2.
Because we were interested in the response to, not per-
formance, we substituted network ﬁle copy, remote win-
alone. Across all nine applications, performance of the
dow manager, and network analyzer for the networking
system with shadow drivers averaged 99% of the system
benchmarks.
without, and was never worse than 97%.
We simulated common bugs by injecting a software
The low overhead of shadow drivers can be explained
fault into a device driver while an application using
in terms of its two constituents: fault isolation and the
that driver was running.
Because both Linux-Nooks
shadowing itself. As mentioned previously, fault isola-
and Linux-SD depend on the same isolation and failure-
tion runs each driver in its own domain, leading to over-
detection services, we differentiate their recovery capa-
head caused by domain crossings. Each domain crossing
bilities by simulating failures that are easily isolated and
takes approximately 3000 cycles, mostly to change page
detected. To generate realistic synthetic driver bugs, we
tables and execution stacks. As a side effect of chang-
analyzed patches posted to the Linux Kernel Mailing
ing page tables, the Pentium 4 processor ﬂushes the TLB,
List [24]. We found 31 patches that contained the strings
resulting in TLB misses that can noticeably slow down
“patch,” “driver,” and “crash” or “oops” (the Linux term
drivers [33].
for a kernel fault) in their subject lines. Of the 31 patches,
For example, the kernel calls the driver approximately
we identiﬁed 11 that ﬁx transient bugs (i.e., bugs that oc-
1000 times per second when running audio recorder.
cur occasionally or only after a long delay from the trig-
Each invocation executes only a small amount of code.
gering test). The most common cause of failure (three in-
As a result, isolating the sound driver adds only negligi-
stances) was a missing check for a null pointer, often with

Application Behavior
Device Driver
Application Activity
Linux-Native
Linux-Nooks
Linux-SD
√
Sound
mp3 player
CRASH
MALFUNCTION
√
(audigy driver)
audio recorder
CRASH
MALFUNCTION
√
√
speech synthesizer
CRASH
√
strategy game
CRASH
MALFUNCTION
√
√
Network
network ﬁle transfer
CRASH
√
√
(e1000 driver)
remote window manager
CRASH
√
network analyzer
CRASH
MALFUNCTION
√
IDE
compiler
CRASH
CRASH
√
(ide-disk driver)
encoder
CRASH
CRASH
√
database
CRASH
CRASH
Table 3: The observed behavior of several applications following the failure of the device drivers on which they rely. There
√
are three behaviors: a checkmark ( ) indicates that the application continued to operate normally; CRASH indicates that
the application failed completely (i.e., it terminated); MALFUNCTION indicates that the application continued to run, but
with abnormal behavior.
a secondary cause of missing or broken synchronization.
this.
We also found missing pointer initialization code (two in-
Some applications on Linux-Nooks survived the driver
stances) and bad calculations (two instances) that led to
failure but in a degraded form. For example, mp3 player,
endless loops and buffer overruns. Because these faults
audio recorder and strategy game continued running, but
are detected by Nooks, they cause fail-stop failures on
they lost their ability to input or output sound until the
Linux-Nooks and Linux-SD.
user intervened. Similarly, network analyzer, which in-
We injected a null-pointer dereference bug derived
terfaces directly with the network device driver, lost its
from these patches into our three drivers. We ensured
ability to receive packets once the driver was reloaded.
that the synthetic bug was transient by inserting the bug
A few applications continued to function properly
into uncommon execution paths, such as code that han-
after driver failure on Linux-Nooks.
One application,
dles unusual hardware conditions. These paths are rarely
speech synthesizer, includes the code to reestablish its
executed, so we accelerated the occurrence of faults by
context within an unreliable sound card driver. Two of the
also executing the bug at random intervals. The fault code
network applications survived on Linux-Nooks because
remains active in the driver during and after recovery.
they access the network device driver through kernel ser-
Table 3 shows the three application behaviors we
vices (TCP/IP and sockets) that are themselves resilient
observed.
When a driver failed, each application ei-
√
to driver failures.
ther continued to run normally ( ), failed completely
Linux-SD recovers transparently from disk driver fail-
(“CRASH”), or continued to run but behaved abnormally
ures.
Recovery is possible because the IDE storage
(“MALFUNCTION”). In the latter case, manual inter-
shadow driver instance maintains the failing driver’s ini-
vention was typically required to reset or terminate the
tial state. During recovery the shadow copies back the
program.
initial data and reuses the driver code, which is already
This table demonstrates that shadow drivers (Linux-
stored read-only in the kernel. In contrast, Linux-Nooks
SD) enable applications to continue running normally
illustrates the risk of circular dependencies from reboot-
even when device drivers fail. In contrast, all applica-
ing drivers. Following these failures, Nooks, which had
tions on Linux-Native failed when drivers failed. Most
unloaded the ide-disk driver, was then required to reload
programs running on Linux-Nooks failed or behaved ab-
the driver off the IDE disk. The circularity could only be
normally, illustrating that Nooks’ kernel-focused recov-
resolved by a system reboot. While a second (non-IDE)
ery system does not extend to applications. For example,
disk would mitigate this problem, few machines are con-
Nooks isolates the kernel from driver faults and reboots
ﬁgured this way.
(unloads, reloads, and restarts) the driver. However, it
In general, programs that directly depend on driver
lacks two key features of shadow drivers: (1) it does not
state but are unprepared to deal with its loss beneﬁt the
advance the driver to its pre-fail state, and (2) it has no
most from shadow drivers. In contrast, those that do not
component to “pinch hit” for the failed driver during re-
directly depend on driver state or are able to reconstruct
covery. As a result, Linux-Nooks handles driver failures
it when necessary beneﬁt the least. Our experience sug-
by returning an error to the application, leaving it to re-
gests that few applications are as fault-tolerant as speech
cover by itself. Unfortunately, few applications can do
synthesizer. Were future applications to be pushed in this

direction, software manufacturers would either need to
Fault Injection Outcomes
Sound
Network
Storage
develop custom recovery solutions on a per-application
100
78
44
96
76
38
58
basis or ﬁnd a general solution that could protect any ap-
80
plication from the failure of a kernel device driver. Cost
is a barrier to the ﬁrst approach. Shadow drivers are a
60
path to the second.
40
Application Behavior During Driver Recovery
Percent of Failures 20
Although shadow drivers can prevent application failure,
0
they are not “real” device drivers and do not provide com-
mp3 player
audio
network
network
compiler
database
recorder
file transfer
analyzer
plete device services. As a result, we often observed a
Detected
Recovered
slight timing disruption while the driver recovered. At
best, output was queued in the shadow driver. At worst,
`
Figure 7: Results of fault-injection experiments on Linux-
input was lost by the device. The length of the delay was
SD. We show (1) the percentage of failures that are automat-
primarily determined by the recovering device driver it-
ically detected by the fault isolation subsystem, and (2) the
self, which, on initialization, must ﬁrst discover, and then
percentage of failures that shadow drivers successfully re-
conﬁgure, the hardware.
covered. The total number of failures experienced by each
Few device drivers implement fast reconﬁguration,
application is shown at the top of the chart.
which can lead to brief recovery delays. For example,
the temporary loss of the e1000 network device driver
prevented applications from receiving packets for about
Non-fail-stop Failures
ﬁve seconds.2 Programs using ﬁles stored on the disk
If driver failures are not fail stop, then shadow drivers
managed by the ide-disk driver stalled for about four sec-
may not be useful. To evaluate whether device driver fail-
onds during recovery. In contrast, the normally smooth
ures are indeed fail-stop, we performed large-scale fault-
sounds produced by the audigy sound card driver were
injection tests of our drivers and applications running on
interrupted by a pause of about one-tenth of one second,
Linux-SD. For each driver and application combination,
which sounded like a slight click in the audio stream.
we ran 350 fault-injection trials.3 In total, we ran 2100
Of course, the signiﬁcance of these delays depends
trials across the three drivers and six applications. Be-
on the application. Streaming applications may become
tween trials, we reset the system and reloaded the driver.
unacceptably “jittery” during recovery. Those processing
For each trial, we injected ﬁve random errors into the
input data in real-time might become lossy. Others may
driver while the application was using it. We ensured the
simply run a few seconds longer in response to a disk
errors were transient by removing them during recovery.
that appears to be operating more sluggishly than usual.
After injection, we visually observed the impact on the
In any event, a short delay during recovery is best con-
application and the system to determine whether a fail-
sidered in light of the alternative: application and system
ure or recovery had occurred. For each driver, we tested
failure.
two applications with signiﬁcantly different usage scenar-
ios. For example, we chose one sound-playing applica-
5.3
Limits to Recovery
tion (mp3 player) and one sound-recording application
The previous section assumed that failures were fail-stop.
(audio recorder).
However, driver failures experienced in deployed systems
If we observed a failure, we then assessed the trial on
may exhibit a wider variety of behaviors. For exam-
two criteria: whether the fault was detected, and whether
ple, a driver may corrupt state in the application, ker-
the shadow driver could mask the failure and subsequent
nel, or device without being detected. In this situation,
recovery from the application. For undetected failures,
shadow drivers may not be able to recover or mask fail-
we triggered recovery manually. Note that a user may
ures from applications. This section uses fault injection
observe a failure that an application does not, for exam-
experiments in an attempt to generate faults that may not
ple, by testing the application’s responsiveness.
be fail-stop.
Figure 7 shows the results of our experiments. For
each application, we show the percentage of failures
2This driver is particularly slow at recovery. The other network
that the Nooks subsystem detected and the percentage of
drivers we tested recovered in less than a second.
failures from which shadow drivers correctly recovered.
Only 18% of the injected faults caused a visible failure.
3For details on the fault injector see [33].

Shadow Driver
Device Driver Shadowed
Class Size
Class Size
Driver Class
Lines of Code
Lines of Code
# of Drivers
Lines of Code
Sound
666
7,381 (audigy)
48
118,981
Network
198
13,577 (e1000)
190
264,500
Storage
321
5,358 (ide-disk)
8
29,000
Table 4: Size and quantity of shadows and the drivers they shadow.
In our tests, 390 failures occurred across all applica-
ures. When a failure recurs during recovery, the sequence
tions. The sytem automatically detected 65% of the fail-
of shadow driver recovery events creates a detailed re-
ures. In every one of these cases, shadow drivers were
production scenario that aids diagnosis. This record of
able to mask the failure and facilitate driver recovery. The
recovery contains the driver’s calls into the kernel, re-
system failed to detect 35% of the failures. In these cases,
quests to conﬁgure the driver, and I/O requests that were
we manually triggered recovery. Shadow drivers recov-
pending at the time of failure. This information enables a
ered from nearly all of these failures (127 out of 135).
software engineer to ﬁnd and ﬁx the offending bug more
Recovery was unsuccessful in the remaining 8 cases be-
efﬁciently.
cause either the system had crashed (5 cases) or the driver
had corrupted the application beyond the possibility of re-
5.4
Code Size
covery (3 cases). It is possible that recovery would have
The preceding sections evaluated the efﬁciency and ef-
succeeded had these failures been detected earlier with a
fectiveness of shadow drivers. This section examines the
better failure detector.
complexity of shadow drivers in terms of code size, which
Across all applications and drivers, we found three
can serve as a proxy for complexity.
major causes of undetected failure. First, the system did
Table 4 shows, for each class, the size in lines of
not detect application hangs caused by I/O requests that
code of the shadow driver for the class. For compari-
never completed. Second, the system did not detect errors
son, we show the size of the driver from the class that
in the interactions between the device and the driver, e.g.,
we tested and the total number and cumulative size of
incorrectly copying sound data to a sound card. Third,
existing Linux device drivers in that class in the 2.4.18
the system did not detect certain bad parameters, such
kernel. The total code size is an indication of the lever-
as incorrect result codes or data values. Detecting these
age gained through the shadow’s class-driver structure.
three error conditions would require that the system better
Furthermore, the table shows that a shadow driver is sig-
understand the semantics of each driver class. For exam-
niﬁcantly smaller than the device driver it shadows. For
ple, 68% of the sound driver failures with audio recorder
example, our sound-card shadow driver is only 9% of the
went undetected. This application receives data from the
size of the audigy device driver it shadows. The IDE stor-
driver in real time and is highly sensitive to driver output.
age shadow is only 6% percent of the size of the Linux
A small error or delay in the results of a driver request
ide-disk device driver.
may cause the application to stop recording or record the
The Nooks driver fault isolation subsystem we built
same sample repeatedly.
upon contains about 23,000 lines of code. In total, we
Our results demonstrate a need for class-based failure
added about 3300 lines of new code to Nooks to support
detectors that can detect violations of the driver interface
our three class drivers. Otherwise, we made no changes
to achieve high levels of reliability. However, driver fail-
to the remainder of the Linux kernel. Shadow drivers re-
ures need not be detected quickly to be fail-stop. There
quired the addition of approximately 600 lines of code for
was a signiﬁcant delay between the failure and the sub-
the shadow manager, 800 lines of common code shared
sequent manual recovery in our tests, and yet the appli-
by all shadow drivers, and another 750 lines of code for
cations survived the vast majority of undetected failures.
general utilities. Of the 177 taps we inserted, only 31
Thus, even a slow failure detector can be effective at im-
required actual code; the remainder were no-ops.
proving application reliability.
5.5
Summary
Non-transient Failures
This section examined the performance, fault-tolerance,
Shadow drivers can recover from transient failures only.
limits, and code size of shadow drivers.
Our re-
In contrast, deterministic failures may recur during recov-
sults demonstrate that: (1) the performance overhead of
ery when the shadow conﬁgures the driver. While unable
shadow drivers during normal operation is small, partic-
to recover, shadow drivers are still useful for these fail-
ularly when compared to a purely isolating system, (2)

applications that failed in any form on Linux-Native or
of the Eighth IEEE Workshop on Hot Topics in Operating
Linux-Nooks ran normally with shadow drivers, (3) the
Systems, May 2001.
reliability provided by shadow drivers is limited by the
[10] S. Chandra and P. M. Chen. How fail-stop are faulty pro-
system’s ability to detect failures, and (4) shadow drivers
grams? In Proceedings of the 28th Symposium on Fault-
are small, even relative to single device driver. Overall,
Tolerant Computing, June 1998. IEEE.
[11] S. Chandra and P. M. Chen. Whither generic recovery
these results indicate that shadow drivers have the poten-
from application faults? A fault study using open-source
tial to signiﬁcantly improve the reliability of applications
software. In Proceedings of the 2000 IEEE International
on modern operating systems with only modest cost.
Conference on Dependable Systems and Networks, June
2000.
6
Conclusions
[12] P. M. Chen, W. T. Ng, S. Chandra, C. Aycock, G. Ra-
jamani, and D. Lowell. The Rio ﬁle cache: Surviving
Improving the reliability of modern systems demands that
operating system crashes. In Proceedings of the Seventh
we increase their resilience. To this end, we designed and
ACM International Conference on Architectural Support
implemented shadow drivers, which mask device driver
for Programming Languages and Operating Systems, Oct.
failures from both the operating system and applications.
1996.
Our experience shows that shadow drivers improve
[13] T. Chiueh, G. Venkitachalam, and P. Pradhan. Integrat-
application reliability, by concealing a driver’s failure
ing segmentation and paging protection for safe, efﬁcient
while facilitating recovery. A single shadow driver can
and transparent software extensions. In Proceedings of the
enable recovery for an entire class of device drivers.
17th ACM Symposium on Operating Systems Principles,
Shadow drivers are also efﬁcient, imposing little perfor-
Dec. 1999.
mance degradation. Finally, they are transparent, requir-
[14] A. Chou, J. Yang, B. Chelf, S. Hallem, and D. Engler. An
empirical study of operating system errors. In Proceed-
ing no code changes to existing drivers.
ings of the 18th ACM Symposium on Operating Systems
Principles, Oct. 2001.
Acknowledgments
[15] D. R. Engler, M. F. Kaashoek, and J. O. Jr. Exokernel:
This work was supported in part by the National Sci-
an operating system architecture for application-level re-
ence Foundation under grants ITR-0085670 and CCR-
source management.
In Proceedings of the 15th ACM
0121341. We would also like to thank our shepherd, Peter
Symposium on Operating Systems Principles, Dec. 1995.
Chen, who provided many valuable insights.
[16] W. Feng. Making a case for efﬁcient supercomputing.
ACM Queue, 1(7), Oct. 2003.
[17] B. Ford, G. Back, G. Benson, J. Lepreau, A. Lin, and
O. Shivers. The Flux OSKit: a substrate for OS language
References
and research. In Proceedings of the 16th ACM Symposium
[1] S. Arthur.
Fault resilient drivers for Longhorn server.
on Operating Systems Principles, Oct. 1997.
Technical Report WinHec 2004 Presentation DW04012,
[18] J. Gray. Why do computers stop and what can be done
Microsoft Corporation, May 2004.
about it? Technical Report 85-7, Tandem Computers, June
[2] ¨
O. Babao˘glu. Fault-tolerant computing based on Mach. In
1985.
Proceedings of the USENIX Mach Symposium, Oct. 1990.
[19] J. Gray and A. Reuter. Transaction Processing: Concepts
[3] R. Barga, D. Lomet, and G. Weikum. Recovery guaran-
and Techniques. Morgan Kaufmann, 1993.
tees for general multi-tier applications. In International
[20] S. M. Hand. Self-paging in the Nemesis operating system.
Conference on Data Engineering, 2002. IEEE.
In Proceedings of the 3rd USENIX Symposium on Operat-
[4] J. F. Bartlett. A NonStop kernel. In Proceedings of the 8th
ing Systems Design and Implementation, Feb. 1999.
ACM Symposium on Operating Systems Principles, Dec.
[21] D. Jewett. Integrity S2: A fault-tolerant Unix platform.
1981.
In Proceedings of the 21st Symposium on Fault-Tolerant
[5] A. Borg, W. Balu, W. Graetsch, F. Herrmann, and
Computing, June 1991. IEEE.
W. Oberle. Fault tolerance under UNIX. ACM Trans-
[22] M. J. Kilgard, D. Blythe, and D. Hohn. System support
actions on Computer Systems, 7(1):1–24, Feb. 1989.
for OpenGL direct rendering. In Proceedings of Graphics
[6] D. P. Bovet and M. Cesati.
Inside the Linux Kernel.
Interface, May 1995. Canadian Human-Computer Com-
O’Reilly & Associates, 2002.
munications Society.
[7] T. C. Bressoud. TFT: A software system for application-
[23] J. Liedtke. On µ-kernel construction. In Proceedings of
transparent fault tolerance. In Proceedings of the 28th
the 15th ACM Symposium on Operating Systems Princi-
Symposium on Fault-Tolerant Computing, June 1998.
ples, Dec. 1995.
IEEE.
[24] Linux Kernel Mailing List.
Available at http:
[8] T. C. Bressoud and F. B. Schneider. Hypervisor-based
//www.uwsg.indiana.edu/hypermail/
fault tolerance. ACM Transactions on Computer Systems,
linux/kernel.
14(1):80–107, Feb. 1996.
[25] D. E. Lowell, S. Chandra, and P. M. Chen. Exploring
[9] G. Candea and A. Fox. Recursive restartability: Turning
failure transparency and the limits of generic recovery. In
the reboot sledgehammer into a scalpel. In Proceedings
Proceedings of the 4th USENIX Symposium on Operating

Systems Design and Implementation, Oct. 2000.
[26] D. E. Lowell and P. M. Chen. Discount checking: Trans-
parent, low-overhead recovery for general applications.
Technical Report CSE-TR-410-99, University of Michi-
gan, Nov. 1998.
[27] G. Muller, M. Banˆatre, N. Peyrouze, and B. Rochat.
Lessons from FTM: An experiment in design and imple-
mentation of a low-cost fault-tolerant system. IEEE Trans-
actions on Software Engineering, 45(2):332–339, June
1996.
[28] D. Patterson, A. Brown, P. Broadwell, G. Candea,
M. Chen, J. Cutler, P. Enriquez, A. Fox, E. K´yc´yman,
M. Merzbacher, D. Oppenheimer, N. Sastry, W. Tetzlaff,
J. Traupman, and N. Treuhaft. Recovery-Oriented Com-
puting (ROC): Motivation, deﬁnition, techniques, and
case studies. Technical Report CSD-02-1175, UC Berke-
ley Computer Science, Mar. 2002.
[29] J. S. Plank, M. Beck, G. Kingsley, and K. Li. Libckpt:
Transparent checkpointing under Unix. In Proceedings of
the 1995 Winter USENIX Conference, Jan. 1995.
[30] R. Short, Vice President of Windows Core Technology,
Microsoft Corp. private communication, 2003.
[31] M. Russinovich, Z. Segall, and D. Siewiorek. Applica-
tion transparent fault management in Fault Tolerant Mach.
In Proceedings of the 23rd Symposium on Fault-Tolerant
Computing, June 1993. IEEE.
[32] M. I. Seltzer, Y. Endo, C. Small, and K. A. Smith. Dealing
with disaster: Surviving misbehaved kernel extensions. In
Proceedings of the 2nd USENIX Symposium on Operating
Systems Design and Implementation, Oct. 1996.
[33] M. M. Swift, B. N. Bershad, and H. M. Levy. Improv-
ing the reliability of commodity operating systems. ACM
Transactions on Computer Systems, 22(4), Nov. 2004.
[34] V. Orgovan, Systems Crash Analyst, Windows Core OS
Group, Microsoft Corp. private communication, 2004.
[35] R. Wahbe, S. Lucco, T. E. Anderson, and S. L. Graham.
Efﬁcient software-based fault isolation. In Proceedings of
the 14th ACM Symposium on Operating Systems Princi-
ples, Dec. 1993.
[36] R. S. Wahbe and S. E. Lucco. Methods for safe and efﬁ-
cient implementation of virtual machines, June 1998. US
Patent 5,761,477.
[37] J. A. Whittaker. Software’s invisible users. IEEE Soft-
ware, 18(3):84–88, May 2001.
[38] W. A. Wulf. Reliable hardware-software architecture. In
Proceedings of the International Conference on Reliable
Software, 1975.
[39] M. Young, M. Accetta, R. Baron, W. Bolosky, D. Golub,
R. Rashid, and A. Tevanian. Mach: A new kernel founda-
tion for UNIX development. In Proceedings of the 1986
Summer USENIX Conference, June 1986.

Document Outline

Introduction
Related Work
Device Drivers and Shadow Driver Design
- Driver Faults
- Shadow Drivers
- Taps
- The Shadow Manager
- Summary
Shadow Driver Implementation
- General Infrastructure
- Passive-Mode Monitoring
- Active-Mode Recovery
  - Stopping the Failed Driver
  - Reinitializing the Driver
  - Transferring State to the New Driver
- Active-Mode Proxying of Kernel Requests
- Limitations
- Summary
Evaluation
- Performance
- Fault-Tolerance
- Limits to Recovery
- Code Size
- Summary
Conclusions