\section{Fine-Grained Isolation}
\label{sec:odft}

Isolation ensures that the driver and kernel state changes made by a request are not
propagated if the request fails. 
We need the following properties from an isolation mechanism:

\begin{enumerate}
\item{\em Transactional execution}: We need to execute the driver
  entry points in a transactional fashion to keep a clean copy of all
  data modified by the driver.

\item {\em Memory safety and fault detection}: We need to ensure a
  driver cannot corrupt the kernel or other threads in the driver and
  provide mechanisms that detect when a driver has failed.

\item {\em Synchronization}: Threads executing in the driver need to
  synchronize with other threads to ensure they do not corrupt shared
  state in the kernel, driver, or device.
\end{enumerate}

To  achieve  these  goals,  we rely  on  well-understood  compile-time
software  fault  isolation (SFI)~\cite{wahbe93}.   As  a driver  entry
point operates  on data shared  with the rest  of the driver,  the SFI
mechanism must allow  access to such data but  prevent its corruption.
\toolshort\ therefore  executes isolated code on a  {\em minimal copy}
of the driver  and kernel, which is a copy of  data referenced from an
entry point  but not  entire structures. For example, when a network 
driver issues an ioctl to update its transmit ring parameters, FGFT 
uses points-to analysis and pre-determines the fields an entry point can access,
such as {\tt netdev$\rightarrow$priv$\rightarrow$tx\_ring} 
and {\tt netdev$\rightarrow$priv$\rightarrow$rx\_ring}, and will only 
generate marshaling code to copy in/out only these fields to reduce 
the generated code and the unnecessary copying of unused fields.  
If  the entry point  does not
fail, \toolshort\ merges the copy back into the real driver and kernel
structures.  On a  failure,  the  copy is  discarded.  In effect, FGFT
executes the suspect  entry point as a transaction  using lazy version
management~\cite{larus-rajwar:transactional-memory:book:2006}.  

%\fixme{
%"Can the authors provide an example of the kinds of structures that were touched and which fields were copied, as opposed to the entire structure?"}


However, not all data can be copied.  Structures shared with the
device, such as network transmit and receive rings, cannot be copied
because the device will not share the copied structure.  Instead,
\toolshort\ grants suspect code direct read and/or write access to
these structures and relies on device-state checkpointing to restore
these structures following a failure. Furthermore, driver code used
for recovery cannot be isolated and must be trusted.


\begin{figure}
\centering
\includegraphics[keepaspectratio=true,width=3in]{figures/pdf/isolation.pdf}

\caption{\small \bf FGFT replicates driver
  entry points into a normal driver and an {\em SFI driver
    module}. A runtime support module provides communication
  and recovery support.}

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

We implemented \toolshort\ for the Linux 2.6.29
kernel. Figure~\ref{fig:isolation} shows the components of \toolshort.
We describe how \toolshort\ provides isolation, communicates with
isolated code, and detects failures.



\subsection{Software Fault Isolation}

As \toolshort\ targets open-source Linux device drivers, we implement SFI
using a source-code rewriting tool called {\em \toolshort\ Isolator}
written using CIL~\cite{nmr+02}. It generates isolation code into the
driver and produces communication code, described below, for
communicating with the isolated code.

Isolator generates an additional driver module called the {\em SFI
  module} that contains a copy of all suspect entry points and all driver
functions transitively called from those functions, instrumented for
SFI. In addition, Isolator generates a new version of the driver that
invokes the SFI module entry points. At the top of the existing entry
points, Isolator inserts a test to see whether to execute normally or
in isolation, and if so invokes the SFI module. 

The decision to invoke a given entry point in isolation can be
made in one of three ways.  First, a developer can use the attribute
{\tt \_\_attribute\_\_((isolate))} to manually specify which
functions to isolate. This causes the function to always execute
with isolation. Second, \toolshort\ can {\em automatically} use any
static analysis tool to identify buggy code and which entry
points are affected. These entry points are then always executed with
isolation. Finally, the decision can be made at run time. A fault
management system, such as the Solaris Fault management
Daemon~\cite{solaris:fma:website}, can call into the SFI module and specify
which functions to execute with isolation. Furthermore, it 
can register a function pointer at run time that takes the
same arguments as the suspicious function and returns a decision of whether
to isolate or not.

In addition to producing the SFI driver code, Isolator produces
communication code that invokes the SFI driver and copies in the
minimal driver and kernel state needed by the suspect entry points,
copies out any changes made by the SFI driver, and initiates recovery
following a detected failure. Isolator manages resource allocation,
synchronization and I/O across the two copies. Isolator only detects
memory failures. For other failures, such as arithmetic exceptions,
we trap processor exceptions and check if they originate from SFI
module.


Isolator uses CIL's memory tracking module~\cite{nmr+02} to instrument
all memory references in the driver.  It inserts a call to our
\codesm{memcheck} function that verifies the target of a load/store is
valid. If not, it detects a failure and invokes the recovery
mechanism. The \codesm{memcheck} routine consults a {\em range table} to
verify memory references and provide fine-grained memory protection by
only allowing access to driver and kernel data as identified at
compile time. This table contains the addresses and lengths of copied
data structures and buffers shared with the device. The range table is
created on every invocation of a suspect entry point and flushed
on return.

We do not add all local variables to the range table because we trust
the compiler to generate correct code for moving variables between
registers and the stack. However, if the driver ever takes the address
of a local variable, or creates an array as a local variable, then
Isolator adds a call in the instrumented SFI driver to add the
variable's address and length to the range table and remove it from
the range table when the variable goes out of scope. Similarly, we
trust the compiler to produce valid control transfers and do not
instrument branch or call instructions.


\subsubsection{Communication Code for Entry Points}


\toolshort\ Isolator generates {\em stub code} to invoke suspect entry
points that copies data into and out of the driver. Similar to RPC stubs,
these stubs create a copy of the parameters passed to the suspect
code, but also copy any driver or kernel global variables it
uses. When the suspect entry point completes, stub code copies
modified data structures and return values back to the regular driver
and kernel in the current thread. An alternative approach would be to rely on
transactional-memory techniques to dynamically create a copy of data
as it is referenced, which may have lower copying costs but higher
run-time costs~\cite{birgisson:tx-inspect:ccs:2008}.


Isolator automatically identifies the minimal data needed for an entry
point through static analysis. This data includes the structure fields from
parameters referenced by the entry point or functions it calls plus
fields of global variables referenced. As they copy data, stubs update
the range table with the address and length of each object. For
objects that cannot be copied (such as those shared with the device),
stubs fill in the existing address of the field, its length, and
whether the entry point needs read, write, or read/write access.

If suspect code  invokes the kernel, Isolator generates stubs
for kernel functions that copy parameters to the kernel and copies
kernel return values back to suspect code. The SFI driver may pass in
fields from its parameters to the kernel as arguments. To avoid
creating a new copy of these fields, as would be done by RPC,
\toolshort\ maintains an {\em object tracker} that maps the address of
kernel and regular driver objects to the address of objects in the SFI
driver. Stub code consults the object tracker when calling into the
kernel to determine whether arguments refer to a new or existing
object. If an object exists, stubs copy the argument back to the
existing object and otherwise temporarily allocate a new object. To
support recovery, stubs may generate a {\em compensation entry} in a
{\em kernel undo log}. This log records operations that must be
reversed on failure, such as freeing memory allocations.

The stub code must know the layout of data structures and whether data
is shared with the driver in order to correctly copy data. As driver
code often contains ambiguous data structures such as \codesm{void *}
pointers or list pointers (\eg, \codesm{struct list\_head}), we
rely on programmer-provided annotations to disambiguate such
code~\cite{zca+06}. These annotations also declare which structure
fields or parameters are shared with the device and should not be
copied. In Section~\ref{sec:evaluation}, we evaluate the difficulty
of providing annotations.

Some driver functions trigger synchronous callbacks. For example, the
\codesm{pci\_register\_driver} function causes a callback on the same
thread to the driver's \codesm{probe} function. \toolshort\ treats the
callback as a {\em nested transaction}: it causes another isolated
call operating on a second copy of the data. 

\subsubsection{Resource Access from SFI module}
Some resources cannot be copied into the driver because they attach
additional semantics or behavior to memory.

\paragraph{I/O memory.}
\noindent Driver entry points may communicate with the device by writing to I/O
memory. Stubs grant the SFI driver read/write access to
memory-mapped I/O regions and memory shared with the device via
\codesm{dma\_alloc\_coherent}. Isolator identifies these regions
with annotations and creates stubs that grant drivers  direct
read/write  access. 

%SFI threads also re-synchronize with device
%(usually accomplished by sleeping for the device) since the SFI
%thread accesses the device directly and any changes are immediately
%visible. -- we mention this below

\paragraph{Locks.}
\noindent 
Drivers synchronize with other threads using driver spin locks and mutexes. 
Hence, SFI grants read access to driver locks and calls the locking API
to acquire/release the locks. The stub code for kernel locking routines add a
compensation entry to the kernel undo log to release the lock after a
failure. To ensure that changes made by suspect code are not seen by
the rest of the kernel, the lock stubs defer releasing driver locks until
after the entry point returns to the kernel.  Apart from driver locks, 
drivers may acquire kernel-defined locks indirectly through kernel calls.
FGFT does not expand the scope of these locks  and releases them
upon failure through compensation entries in the kernel undo log.
Drivers can also directly manipulate kernel data structures 
while holding kernel-defined locks. FGFT will not recover correctly 
for such entry points. However, this is increasingly rare in Linux and 
there is an effort to ensure that kernel data structures are not directly 
exposed to drivers.

The above mechanism protects shared structures across driver
threads.  However, the suspicious thread can also block waiting for
data to arrive on shared structures that have been copied over from
other driver threads.  Fortunately, resynchronization across driver
threads is uncommon. Using static analysis, we measure how often
driver threads wait for other threads using the Linux's {\tt
  completion} family of functions or by polling in a loop.
  
Overall, we find driver resynchronization occurs in 2.7\% of drivers
and 1.4\% of all entry points.  Most re-synchronizations occur during
communication with the device: drivers wait for a device operation to
finish and a callback sets the completion structure. In most
cases, only the completion structure responsible for device
notifications needs to be annotated.  However, complex drivers that
communicate with devices using a layered interface, such as SCSI or
WIFI, may wait for lower layers to communicate with device and
update the appropriate drivers structures with the result of the
operation. In such cases, annotations are required for completion
structures and shared device structures for the driver to work
correctly. Finally, driver threads also sleep inside loops waiting for
other threads to finish by polling reference counts or driver
structures. If these threads modify state across threads, then FGFT
will not recover correctly for this fraction of drivers/entrypoints.


%\fixme{add a paragraph in the paper describing details of FGFTâ€s handling of resynchronization:
%(1) look for how often it comes up in drivers (No. of drivers), (2) how many entry points are affected (coverage), (3) complexity of handling it, and (4) characterize why the problem occurs.}
% DRIVERS: select distinct(driverid) from driver_fns where is_event=1 and cloc=1 and driverid < 3086  and is_pm=0; 68/3085 + 17 
% EP: select  (driverid) from driver_fns where is_event=1 and cloc=1 and driverid < 3086  and is_pm=0; 258/20274 +  22
% select  (driverid) from driver_fns where cloc=1 and driverid < 3086  and is_pm=0; 20274 
%mega_internal_command

\paragraph{Memory allocation.}
Stubs for allocators invoke the kernel allocator,  add the returned
memory region to the range table and generate a compensation entry to free the
memory on failure. The newly allocated memory is not copied into the
driver because its contents do not need to be preserved. For kernel callbacks
that implicitly allocate memory an appropriate compensation entry is generated.

%\fixme{(3.1) You stub allocator will update your tracking of memory, but what
%about allocations that happen from kernel callbacks called by the
%driver?  What if these calls are deep in the call stack?}

\subsection{Failure Detection}

In addition to protecting the kernel and regular driver code from
corruption, isolation provides the primary means to detect
failures. \toolshort's SFI mechanism implements {\it spatial memory
  safety}~\cite{nagarakatte:softbound:pldi:2009}: every memory
reference must be within an object made accessible during the copy
process.  Thus, references outside the range table indicate a failure.

Stubs can detect additional failures when copying data back to the
kernel. For example, if the driver writes an invalid address into a
data structure, the copying code will dereference that address and
generate an exception. We also modified the Linux kernel exception handlers to detect
unexpected traps from the SFI driver as failures. If one occurs,
the trap handler sets the instruction pointer to the recovery routine. This is
the only change to the Linux kernel, and required 38 lines of
code.

The detection mechanisms may miss several categories of
failures. First, if the driver violates its own data structure
invariants, stubs may not detect the problem. Recent work on
identifying and verifying data structure invariants could detect these
faults~\cite{butt:sec-driver:acsac:2009}. For example, if a suspect
entry point sets a flag indicating that a field is valid but does not
set the field, then corruption will leak out of the SFI
driver. Second, the driver does not provide strong type safety, so the
driver may assign a structure field to the wrong type of data. While
this may be detected when the stub copies data, it is not
guaranteed. Finally, \toolshort\ does not enforce kernel restrictions on the
range of scalar values, such as valid packet lengths.



