related.tex

Application debugging is a necessary part of software development cycle. There
are many software, hardware and hybrid technique exists for debugging. The
importance of such debugging technique increases as the complexity of software
increases. Read Copy Update (RCU) is one of the synchronization technique which
is heavily used in the linux kernel because of its lightweight read-side
overhead. Programming of software system using RCU is complex and often lead to
bugs due to its incorrect usage. Debugging such incorrect usage of rcu
primitive is challenging as one needs to follow many rules \& assumptions to
verify its correct usage. 

\subsection{RCU debugging} There are many existing solution which are used to
analyse the incorrect usage of RCU synchronization primitive.
Sparse~\cite{sparse} is one of the existing tool which uses static analysis
method to verify the correct usage of RCU. It uses \emph{\_\_rcu} tag to
annotate the RCU protected pointers and flags traversals of RCU-protected
pointers that are not properly protected either by an RCU read-side critical
section or an update-side lock. Sparse however has a high rate of false
positives, therefore requiring more time to and effort to interpret and
validate the bugs detected. On the other hand Lockdep-RCU~\cite{PaulEMcKenney2010LockdepRCU}
doesn't have many false positives, however it does have a false negatives
where if an \emph{rcu\_dereference} happens under some other RCU critical
section, it is not raised as a bug. Lockdep-RCU is a runtime technique
as opposed to Sparse which is static.

\subsection{Watchpoint} Watchpoint is an important debugging facility that
helps developers track the memory references. Almost all the hardware
state-of-the-art processors provide support for limited hardware watchpoints.
There has been several proposal in the past on implementing software watchpoint
and some of them using methods of Dynamic Binary Instrumentation(DBI).
%makes the case for supporting an unlimited number of watchpoints. A hardware
%solution is proposed and multiple applications are described. Unlike our
%approach, the cited approach depends on specialised hardware and requires that
%applications using these watchpoints maintain their own context-specific
%information.  In , 
\paragraph{Software-based} Zhao \emph{et al.}~\cite{Zhao:2008} describe a
method of implementing an efficient and scalable DBT-based watchpoint system.
His method uses page protection and indirection through a hash table to track
watched memory. This approach does not support watching ranges of memory, nor
does it support context-specific information. Lueck \emph{et al.} \cite{PinADX}
introduce semantic watchpoints as part of the PinADX system, an extension of
the PIN DBT framework. PinADX enables interactive debugging by triggering
debugger breakpoints when semantic conditions are met. While similar in spirit
to behavioural watchpoints, semantic watchpoints do not maintain
context-specific, per-watchpoint state. Wahbe \emph{et al.}~\cite{Wahbe:1992}
also proposes the implementation of software watchpoint using code patching and
static analysis.  Another interesting approach proposed by keppel \emph{et
al.}~\cite{Keppel:93a} to use checkpoint for memory updates. However all
these approaches are valid only for userspace. 
The latest patches for MemCheck in Valgrind~\cite{Seward:2005} also introduce
support of adding watchpoint. They use a link-list to maintain the watchlist.
This puts a severe restriction on their performance.   

\paragraph{Hardware-based} Greathouse \emph{et al.}~\cite{UnlimitedWatchpoints}
propose a hardware solution that efficiently supports an unlimited number of
watchpoints. Witchel and Asanovic \cite{Mondrix} describes the implementation
of memory protection domains for the Linux kernel. Protection domains are
implemented using specialised hardware and enable fine- and coarse-grained
memory protection using a mechanism similar to hardware watchpoints. Unlike our
approach, both depend on
specialised hardware and require that applications using this hardware
separately maintain context-specific information. Suh \emph{et al.}
\cite{SecureProgramExecFlowTracking} propose a method of secure program
execution by tracking dynamic information flow. Memory tagging at the hardware
level allows their system to track tainted data as it propagates through a
running program. Behavioural watchpoints are similar insofar as a watched
address is tagged, and this tag propagates through a program.