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, like parallel system. 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 is used for analysing 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. One of the demerits of using sparse as static analysis tool is its output gets heavily ridden with false positives, requiring more time and effort to interpret. Lockdep-RCU is another method which is used for analysing the incorrect usage of \emph{rcu\_derefence()}. It emits a runtime error if they gets executed outside of an RCU read-side critical section. One of the important limitation with Lockdep-RCU~\cite{PaulEMcKenney2010LockdepRCU} solution is it catches only the incorrect usage of \emph{rcu\_derefence()} and \emph{rcu\_assign\_pointer()}. 

\subsection{Software Watchpoint}
Watchpoint is an important debugging facility that helps developers track the memory references. Almost all the hardware state-of-the-art processor provides 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). Zhao~\cite{Zhao:2008} introduces a method to add software watchpoint using DynamoRIO. It uses page protection and hash lookup method to detect the watched addresses and implementation was done in user-space. However the implemented watchpoint was very efficient, the same method can not be used for kernel modules using Granary since these modules share code and data pages with the kernel and it will require instrumenting kernel. We are also using non-canonical address to implement watchpoint which we cosider will reduce the overhead of hashlookup. Wahbe~\cite{Wahbe:1992} also proposes the implementation of software watchpoint using code patching and static analysis.  Another interesting approach proposed by keppel~\cite{Keppel:93a} to use checkpoint for memory updates. But one of the important thing about all of these works is they are only valid for userspace. The latest patches of MemCheck in Valgrind~\cite{Seward:2005} also provides the support of adding watchpoint. They uses link-list to maintain the watchlist. This puts a sevear restriction on their performance.