\section{Introduction}
\noindent
In most commodity operating systems, third-party driver code executes
in privileged mode. Faulty device drivers cause many reliability
issues in these systems~\cite{cyc+01,
  ryzhyk:dingo:eurosys:2009}. Hence, there has been significant
research to tolerate driver failures using programming-language and
hardware-protection techniques~\cite{Boyd-Wickizer:2010,Castro:2009,
  fhn+04, grb08, lcf+05,mczsfi11, williams08}.  These systems execute
the entire driver as a single isolated component. However, much of
this work focuses on {\em detecting} failures and {\em isolating}
drivers from the rest of the system. Few of these systems address how
to {\em restore} driver functionality beyond simply reloading the
driver, which may leave applications non-functioning.

Most driver-reliability systems do not try to restore device state and
instead completely restart failed
drivers~\cite{swift03,zca+06,herder:driver-resilience:dsn:2007},
effectively resetting device state to a known-good configuration. The
state-of-the-art mechanism for restoring driver functionality, shadow
drivers~\cite{smb+04}, logs state-changing operations at the
driver/kernel interface. Following a failure, shadow drivers restart
the driver and replay the log in order to restore internal driver and
device state.  This resets the driver and device to a state
functionally equivalent to its pre-failure state. 
This approach, complete driver isolation and logging for recovery,
poses four problems:

%% 1. Large subsystem barrier to adoption -- too hard
%% 2. May not capture all state -- not enough
%% 3. Contintuous monitoring to capture state causes perf problems if not needed on critical-path code -- too expensive
%% 4. Restart recovery can be slow -- too slow


\begin{enumerate}
\item {\em Too hard:} Shadow drivers must be written for every class
  of driver and must be updated when the interface changes. This adds
  a large body of code to the kernel requiring constant maintenance,
  which is a high barrier to adoption. Other systems require
  substantially rewriting drivers, which is also a barrier.
%
\item {\em Not enough:} Shadow drivers must encode the semantics of
  the kernel/driver interface. However, many drivers have proprietary
  commands that cannot be captured by a shadow driver common to an entire class, leading
  to incomplete recovery. Recent work showed that up to 44\% of
  drivers have non-class behavior~\cite{kadavasplos12}.
%
\item {\em Too expensive:} Shadow drivers must interpose on and log
  {\em all} invocations of a driver. Continuous monitoring imposes a
  performance cost, particularly on high-performance devices such as
  SSDs and NICs even when the critical I/O path is bug-free.

\item {\em Too slow:} Restarting a driver, the first step of log
replay, can be slow (multiple seconds) due to complex initialization
code and therefore may not be useful in latency-sensitive
environments.
\end{enumerate}

A key source of these problems is that prior systems seek {\em
completeness}: applying to {\em all} driver code at {\em all} times. 
While this reduces the per-driver cost, it pushes up both development and
runtime costs. 

%% summary of system
We developed a new driver fault tolerance mechanism to address these
shortcomings called {\em Fine-grained Fault Tolerance}
(\toolshort). Rather than isolating and recovering from the failure of
an entire driver, \toolshort\ executes a driver {\em entry point} as a
transaction and uses software fault isolation to prevent corruption
and detect failures. On entry to a driver, a stub copies
parameters to the driver code. Only if the driver executes correctly
are the results copied back. If the call faults, \toolshort\ destroys the copy to roll back driver
state and fails the call. 

In order to restore device state modified by a driver before faulting,
we developed a novel {\em device state checkpointing} mechanism that
can capture the device state. The stub captures a checkpoint before
invoking the driver, and restores the checkpoint on failure. This
mechanism leverages existing power-management code present in most
drivers, which greatly reduces the development cost of adopting
\toolshort.

%% Possible uses/benefits
\toolshort\ shifts the cost of driver fault tolerance to the faulty
code. While shadow drivers and whole-driver isolation require up-front
code for any instance of a class of drivers, \toolshort\ instead
requires small changes to the driver itself to support isolation and
implement checkpointing. Where past isolation mechanisms interpose on
{\em all} driver code and reduce its performance uniformly, \toolshort\
{\em only} imposes a cost on entry points selected for isolation. Thus,
the cost of executing a single call with fault tolerance may be higher
with \toolshort\ than other systems, but when applied only to code off the
critical path it has much {\em lower} overhead because the critical
code is left unchanged.  Thus, one possible use for \toolshort\ is to
apply it selectively to vulnerable code suspected or known to have
bugs.

The contributions of our work are:

\begin{itemize}

\item We describe Fine-Grained Fault Tolerance, a system consisting of a
static analysis and code generation tool that provides isolation by
executing each driver request on a minimal copy of required driver
state. Our system can be used to isolate specific requests and we
show from a study of published bugs that fine-grained isolation is practical
since bugs only affect 14\% of all entry points in buggy drivers.
%
\item We demonstrate a {\em novel} mechanism to create device checkpoints 
on a running system. In a study of six drivers, we show that taking a 
checkpoint is fast, averaging only 20 $\mu$s.
%
\item We show how to use checkpoints and transactional execution of
driver code to provide fast recovery and remove the permanent 
overhead of monitoring {\em all} requests.
%
\item We show that the implementation effort of \toolshort\ is small: we
  added 38 lines of code to the kernel to trap processor exceptions, and
  found that device checkpoint code can be constructed with little effort
  from power-management code present in 76\% of drivers in common
  driver classes.
\end{itemize}
%
% TODO: some result from usefulness
%
We begin with an overview of the \toolshort\ design.

