\section{Checkpoint-based recovery}
\label{sec:device}

\toolshort\  is built around checkpoint-based
recovery. While checkpointing and restoring memory state is simple
using techniques such as transactional memory or copy-on-write, it has
not previously been possible to capture the state of a device.
Without this, restoring memory state will lead to a driver that is
inconsistent with respect to its device, believing incorrectly that it
has performed an action or is operating in a different mode. We first
describe device state checkpointing, which is the basis of
\toolshort's recovery mechanism. We then describe how \toolshort\
uses device checkpoints to recover in case of a failure.

\begin{figure*}
\centering
\includegraphics[keepaspectratio=true,width=6in]{figures/pdf/combo2.pdf}
\caption{\small \bf Our device state checkpointing mechanism refactors
  code from existing suspend-resume routines to create checkpoint
  and restore for drivers as shown in Figure (a).  The checkpoint routine only stores a
  consistent device snapshot to memory while the restore loads the
  saved state and re-initializes the device. Figures (b) and (c) show
  checkpoint and restore routines in the rtl8139 driver.  }
\label{fig:suspendtocheckpoint}
\vspace{-0.2in}
\end{figure*}

\subsection{Device state checkpointing}

%Restart-replay based driver recovery is slow. The primary delay comes from probing the device 
%all over again which cold boots the device and performs the initialization steps as shown 
%%in Figure~\ref{fig:devicestartup}. For example, during initialization a network driver 
%probes for the device, verifies EEPROM contents, tests the device, and registers the 
%device with the kernel. We instead explore how device checkpoints can be provided. 


To be useful, a device checkpoint mechanism  should fulfill the following goals:

\begin{enumerate}
\item {\em Lightweight.} There should be no continuous monitoring or long-latency operations.
%
\item {\em Broad.} The mechanism must work with a wide range of
  devices/drivers, including those with unique behavior.
%
\item {\em Consistent.} Drivers are often invoked on multiple threads,
  and checkpoints must be a consistent view of device state.
\end{enumerate}

We identified the suspend/resume code already present in many drivers
as having much of the functionality needed to implement checkpoint and
restore.  We next describe how power management for drivers works, and
then describe how to reuse the functionality for driver recovery with
checkpoints.



\subsubsection{Suspend/Resume Background}

\ignore{
\begin{figure}
\centering
\includegraphics[keepaspectratio=true,width=3in]{figures/pdf/state-figures.pdf}
\caption{\small \bf The power state transitions of a device during suspend-resume
and during device state checkpointing.
Not all states are shown.}
\label{fig:suspendtocheckpoint}
\vspace{-0.2in}
\end{figure}
}

Modern operating systems can dynamically reduce their power
consumption to provide a hot {\em standby} mode, also called {\em
  suspend to RAM}, which disables processors and devices but leaves
state in memory. One major component of reducing power is to disable
devices. Thus, operating systems direct devices to switch to a
low-power state when the system goes into standby mode. The behavior
of devices is specified by the ACPI specification for the platform and
by buses, such as PCI and USB.

In order to transition quickly between standby and full-power mode,
drivers implement a power-management interface to save device state
before entering standby mode, and to restore device state when leaving
standby mode~\cite{corbet05,windows:pm-drivers:msdn}. These operations
must be quick to allow fast transitions. The system-wide
suspend-to-RAM mechanism saves the memory state of the driver, and the
driver is responsible for saving and restoring any volatile device
state. Drivers implement a power management interface with methods to save
and restore state.  For example, Linux PCI devices implement these two
methods:
\begin{center}
\begin{tabular}{|l|}
\hline
\small	
\codesm{int  (*suspend) (struct pci\_dev *dev,} \\
\codesm{\ \ \ \ \ pm\_message\_t state);}\\
\hline
\codesm{int  (*resume) (struct pci\_dev *dev); }\\
\hline
\end{tabular}
\end{center}

When saving device state to memory, the driver may invoke the bus to
save bus configuration data, as well as explicitly save the contents
of select device registers that are not captured by the configuration
state. The driver then instructs the device to suspend itself. Simple
devices that have no state simply disable the device.

Upon resume, drivers wake the device, optionally perform a soft reset, restore their saved
state. Since the latency of a system to respond post-resume is
critical, the initialization is lightweight compared to restarting the
driver, as it assumes the device has not changed. Similar to suspend,
simple devices may just re-enable the device without restoring state.

For a system to support standby mode, all drivers must support power
management. While not all drivers do (Linux is
notorious for incomplete support~\cite{mochel:pm-summit:lwn:2006}), it
is widely implemented by Windows and MacOS drivers, and support in Linux
drivers is improving.

The functionality provided by driver power management is very similar
to what is needed for device state checkpointing. First, it provides
the ability to save device state to memory in a way that allows
applications to continue functioning. Second, even though the device
may continue to receive power, the soft reset that occurs when
re-enabling a device ensures that any previous state is replaced by
the restored state. Finally, power management is implemented by most
commonly used drivers. However, it is not directly usable for
checkpointing: power management routines lack the ability to continue
executing after suspending a device because the device has been
disabled.

\subsubsection{Checkpoint}

%\input{sections/device-code}

Device state checkpointing is constructed from a subset of the device
suspend support already present in drivers.  
A device may have many distinct forms of state, each of which require
a different mechanism for checkpoint:
\begin{enumerate}
\item Device configuration information published through the bus
  configuration space.
\item Device registers with configuration data specific to the device.
\item Counters and statistics exported by the device and aggregated by
  the driver.
\item Addresses of memory buffers shared with the driver, such as the
  DMA ring buffers used by network drivers to send or receive packets.
\end{enumerate}
We note that a checkpoint may not actually contain the full state of
the device. Rather, it must contain {\em enough} information that
functionality can later be restored without affecting
applications. Thus, device state that can be recreated or recomputed
need not be saved. Furthermore, the checkpoint only contains the
device state. To be restored properly, it requires a consistent copy
of the driver state taken at the same time. Thus, it must be paired
with mechanisms such as transactional memory or copy-on-write to save
the driver's state.

The configuration state is the easiest to save. Most buses provide a
method to save configuration information. For example, PCI drivers in
Linux use \codesm{pci\_save\_state}, that saves a set of standard
registers and the base address registers (BARs) to memory. Each driver, 
though, must handle the remaining state, separately.

The driver explicitly saves register contents and counters in an
internal driver structure. The difference between registers and counters arises
during recovery, described below, because counter values cannot be
written back to the device. 

Memory buffers shared with the device can be recreated. As a result,
most device drivers do not include the address of these buffers in a
checkpoint. Instead, they free buffers during suspend and re-allocate
them during resume.

Figure~\ref{fig:suspendtocheckpoint}(a) diagrams the tasks performed
by suspend and resume, and shows how that code is shuffled to
create checkpoint and restore functionality. Of the suspend code,
checkpointing reuses all the functionality except detaching the device
with the kernel and suspending the device. As an example,
Figure~\ref{fig:suspendtocheckpoint}(b) shows the code to checkpoint
the 8139too driver.

It may be necessary to checkpoint a driver while it is in use.
Existing suspend routines assume the device is quiescent when the
device state is saved. Checkpoint, though, may be called at any
time. Thus, it must be synchronized with other threads using the
driver. Because device state checkpointing must be
coordinated with other mechanisms for capturing driver state, we do
not put our own synchronization code in the checkpoint routine but
re-use existing device locks in the driver. Device locks protect against conflicting configuration 
operations, or operations like resetting the device when I/O operations 
are in progress. This ensures that we do not corrupt device state 
assumed by another thread in progress when we reset device state in 
case of a failure.

\subsubsection{Restore}

The restore operation can be constructed from a mix of suspend and
resume code. Normally the resume function is invoked when the device
returns to full power and needs to be reconfigured. In the case of
a checkpoint, though, the device is already running at full
power. Thus, resume invokes the bottom half of the suspend routine to
disable the device before restoring state.

The restore operation proceeds in four steps: 
\begin{enumerate}
\item Disable the device to put it in a quiescent, known state.
\item Restore bus configuration state.
\item Re-enable the device.
\item Restore device-specific state.
\end{enumerate}

Figure~\ref{fig:suspendtocheckpoint}(c) shows the code to restore state for a simple
network driver. Of the four categories of driver state, only configuration state and saved
device registers can be reloaded. Counters, which cannot be written back to the device,
are restored by adjusting the driver's version of the counter. Typically, the driver will
read the device counter and update a copy in memory, and reset the device's counter. To
restore the device's counter state, the driver only resets the device's counter; the
in-memory copy of the counter must be saved as part of the driver's memory state.

To restore shared buffers, the driver releases existing shared buffers
after disabling the device. As part of re-enabling the device, it
recreates shared buffers and notifies the device of their new
addresses. While this slows restore, it makes checkpoint very
efficient because only irretrievable state is saved. 

Unlike suspend-resume, it may be useful to use device state
checkpointing from interrupt contexts where sleeping is not
allowed. As a result, checkpoint and restore code must convert sleeps
to busy waits (\codesm{udelay} in Linux) and use memory allocation
flags safe for interrupt context (\codesm{GFP\_ATOMIC} in Linux).

Compared to full-driver restart, resume improves performance because
it does not re-invoke device probe, often the lengthiest part of
starting a device normally.  Furthermore, drivers for newer buses such
as USB and IEEE1394 do not restart the device because the bus handles
this operation. This further reduces restore times. For PCI
devices, a further optimization is to avoid changing the power mode of
the device.   %The original suspend/resume code puts the device into the
%\dthot\ as part of suspend and returns it to the \dzi\ state during
%resume. 
However, we observed that many drivers do not require actually 
powering down the device before performing restore. For these drivers, 
restore can be sped up by skipping these unnecessary power mode changes.

\subsubsection{Discussion}

Device state checkpointing provides several benefits compared with a
logging approach to capturing driver/device state. First, it can be
invoked at any time and has no cost until invoked. Thus, it has no
overhead for infrequent uses. Second, it handles state unique to a
device, such as configuration options. Correct standby operation
demands that devices remain correctly configured across standby, and
hence drivers must already save and restore any required
state. However, device state checkpointing relies on power management
code, which may not be present in all devices. It also requires a
programmer to implement checkpoint/restore for every driver. We
evaluate these concerns in Section~\ref{sec:evaluation}.

\paragraph{Limitations.} There is a risk in utilizing a mechanism for
an unintended purpose: the driver continues running following a
checkpoint and may thus further modify the device state. In contrast,
devices are normally idle between suspend and resume. Thus, it is
possible that the state saved is insufficient to fully restore the
device to correct operation. However, the power management
specifications require drivers to fully capture device state in
software since devices can transition to an even lower power state
%(\dtcold) 
where the device is powered off.  In such cases, drivers
must be able to be restore their original state, following a full
reset. Thus, suspend must store enough information to restore from any
state. 
%For uses of checkpoint that move state across machines, such as
%virtual-machine migration, the ability to restore from fully powered
%off may be necessary as devices may be attached at different I/O
%memory addresses.

FGFT does not work with devices with persistent internal state, such as disks
and other storage devices, since restore will only restore the transient
device state and not the persistent state, such as the contents of
files. As a result, use of checkpoints must be coordinated with
higher-level recovery mechanisms, such as
Membrane~\cite{SundararamanEtAl10-Membrane}, to keep persistent data
consistent.
%{\fixme 
%We will extend our description and mention how FGFT works with disk recovery solutions 
%such as Membrane. We will also clearly mention our limitations here (like writing to 
% wrong block)}


\input{figures/checkpointuses}


\begin{figure*}
\centering
\includegraphics[keepaspectratio=true,width=6.2in]{figures/pdf/synergy.pdf}

\caption{\small \bf \toolshort\ behavior during successful and failed entry point
executions.}

\label{fig:howitworks}
 \vspace{-0.2in} 
\end{figure*}

\paragraph{Other uses for device state checkpointing.}

In addition to fault tolerance, device state checkpoints have other
uses. Table~\ref{table:checkpoint-uses} lists five possible
uses. Within an operating system, checkpoints support fast
reboot after upgrading system software by restoring device state from
a checkpoint rather than reinitializing the driver. Similarly, operating 
systems using non-volatile memory to survive power 
failures~\cite{baily:nvm-os:hotos:2011,narayanan:persistence:asplos:2012}
can restart drivers from a checkpoint rather than reinitializing the
device. In virtualized settings, pass-through and virtualization-aware
devices~\cite{pcisig:iovirt} allow drivers in guest operating systems
to interact with physical hardware. Device state checkpoints enable
virtual-machine checkpoints to a pass-through
device~\cite{mahalingam:iov-dummies:vmworld:2007} and live migration,
because the device state from the source can be extracted and restored
on identical hardware at the destination. With virtual devices, the
latency of live migration can be as low as 60ms~\cite{clark2005live},
so a 2 second delay to initialize a pass-through device adds significant downtime~\cite{kadav09:shadow}.
Finally, device state checkpointing enables dynamic fault tolerance at
fine granularity as demonstrated by \toolshort. 
 
\subsection{Recovery with checkpoints}
We now describe how \toolshort\ uses isolation and device checkpoints
to perform recovery from failures. When a failure is detected, communication stubs
call a recovery routine that is responsible for restoring correct
driver operation.

\paragraph{Failure anticipation.}
To prepare for an eventual recovery, generated stubs create a device checkpoint
before invoking a suspect entry point. They invoke the
\codesm{checkpoint} routine. In addition, stubs for kernel functions 
log compensation entries to undo their effects in the kernel undo log. 
Driver state is not explicitly checkpointed; instead, suspect code operates 
on a copy of driver state as described in Section~\ref{sec:odft}. In addition, 
the stub saves its processor register state, allowing a jump right into the stub if 
the driver fails.

\paragraph{Recovery steps.}
In case a failure is detected by SFI or processor exceptions originating from a
suspect module,
the recovery routine restores driver operation 
through a sequence of steps as shown in Figure \ref{fig:howitworks}:

\begin{enumerate}
\item {\em Unwind thread.} If not already in the stub, the instruction
  pointer is set to the address of the recovery code in the entry
  point's stub, which reloads the saved registers. 
  Nested calls to drivers are logically handled as separate
  transactions, so there is no need to unwind the thread to the
  outermost entry point.
\item {\em Restore device state checkpoint.}  The stub recovery code
  calls the driver's \codesm{restore} routine to restore the device
  state.
\item {\em Free call state.} All temporary structures created for the
  suspect entry point call such as the range table, object tracker,
  and copies of kernel/driver structures are released.
\item {\em Release locks.} Any locks acquired before or during the call to
  the SFI driver are released, allowing other threads to execute.
\end{enumerate}

If a driver entry point fails, the stub returns an appropriate error
indicator, such as a NULL pointer or an error code, and relies on
higher-level code to handle the failure. As only the single entry point 
fails, this failure has little impact on applications.  All application 
state relating to the device, such as open handles, remain valid.
Furthermore, other threads in the driver continue to run as soon as
the recovery process completes and releases all acquired locks.

Compared to other driver isolation systems, the recovery process is
much simpler because only one thread is affected, so other threads
are not unwound. In addition, the driver state is left unmodified,
so it is not saved and restored. Finally, device state is restored 
quickly from a checkpoint rather than by replaying a log. Hence, we
see that checkpointing device state results in quicker and simpler 
recovery semantics for driver recovery.

\subsection{Implementation effort}

A key goal for \toolshort\ is to reduce the implementation effort to
isolate a driver.  \toolshort\ consists of minimal modifications to
the kernel exception handlers (38 lines of code), a kernel module
containing the object tracker, range table, and recovery support, and
the Isolator tool in OCaml. The module is 1,200 lines of C code, and
Isolator is 9700 lines of OCaml that implement: SFI isolation (400
lines), stub generation (7,800 lines), and static analysis of
references to parameter fields (1,500 lines). In comparison, Nooks adds
23,000 lines of {\em kernel code} (85x more than \toolshort) to
isolate and reload device drivers and shadow drivers add another 1,100
lines of code for recovery. \toolshort\ also does not require any
wrappers around the driver interface. Nooks required 14,000 lines of
manually written wrappers, which are hard to maintain as the kernel
interface changes. \toolshort's isolator tool automatically generates
similar code for stubs.



