implementation.tex

Section~\ref{sec:appr} discusses about the behavioural watchpoint and how they are important for debugging RCU based applications.
%our mechanism for implementing watchpoint for memory operations. We also described the details of shadow memory \& meta-information and how it can is used for tracking rcu synchronization primitive. 
This section describes about the implementation and the policies we used for tracking RCU primitives.

The design of our system, using Granary, is based on the consideration that it interposes at the kernel/module interface. While implementing our system we found that most of the  RCU primitives are defined as macro and inline functions~\cite{PaulEdwardMcKenneyPhD} which gets embedded into binary module. Granary being a DBI tool doesn’t know when one of these rcu interface function gets called. To handle this we annotated RCU primitives that gives a callbacks to kernel wrapper when these primitives is used. This is particularly helpful since it provided the infrastructure to track the usage of rcu primitive and update the contextual information. It is then used to check the violation of RCU rules and possible bugs. The different memory access policies we used to check the violation of RCU usage are as follows:

%The design of our system, using Granary, is based on the consideration that  
%One of the important challenge while implementing our system was most of the RCU primitives are defined as macro and inline functions~\cite{PaulEdwardMcKenneyPhD} which gets embedded into binary module. Granary being a DBI tool doesn’t know when one of these rcu interface function gets called. To handle this we annotated RCU primitives that gives a callbacks to kernel wrapper on its uses. This was particularly helpful since it provided the infrastructure to track the usage of rcu primitive and update the meta-information. The updated meta-information is then used to check the violation of RCU rules and possible bugs. The section below discusses the different memory access policy rcu protected data should follow and how meta-information is used to enforce them: 

\begin{enumerate}
\item[i)] \emph{Access of RCU protected data inside read critical section} To ensure the access of RCU protected data inside read critical section, the per-thread generation number should be even.% our system checks for the following policies: %uses thread and watchpoint \emph{generation number}.%. Before any memory read at watchpoint addresses our system checks both thread \& watchpoint \emph{Generation number} and ensures the following:
%	\begin {itemize}
%		\item[i)] Per-thread \emph{generation number} should be even to ensure the access of memory inside read critical section. %(\texttt{current\_thread\_info()$\rightarrow$spill\_slot[0]\%2 == 0})
		%\item[ii)] Per-object \emph{generation number} should be even and equal to thread \emph{generation number}. (\emph{meta$\rightarrow$thread\_info$\rightarrow$gen\_nums[n] == current\_thread\_info()$\rightarrow$spill\_slot[0]}) 
%		\item[iii)] For recursive use of read critical section, per-object \emph{generation number} should be equal to the sum of thread \emph{generation number} and number of open read critical section. (\emph{meta$\rightarrow$thread\_info$\rightarrow$gen\_nums[n]== (current\_thread\_info()$\rightarrow$spill\_slot[0]+ current\_thread\_info()$\rightarrow$spill\_slot[0])})
%	\end{itemize}	  
\item[ii)] \emph{Recursive use of read critical section} Recursive use of read critical section is identified by counting the number of \texttt{rcu\_read\_lock} \& \texttt{rcu\_read\_unlock}. we use thread local slot to count these primitive and ensures that there is no mismatch.
\item[iii)] \emph{ Reference of RCU protected data inside its own critical section} This policy ensures that the access of RCU pointer happens in its own critical section. Our system checks it based on per-thread and per-object generation number. For non-recursive read critical section, per-object generation number should be even and equal to thread generation number and for recursive use of read critical section, per-object generation number should be equal to the sum of thread generation number and number of open read critical section.
\item[iv)] \emph{Access of RCU protected data using rcu dereference} The access of RCU protected data is allowed using \texttt{rcu\_dereference} inside read critical section. To check the direct access of rcu protected data we encode the pointer aliasing information in meta-data and the source watchpoint is changed to alias watchpoint inside \texttt{rcu\_dereference} wrapper. This allows us to check if the access of RCU protected data is happening with directly or through an alias pointer.
\item[v)] \emph{Allocated memory should not be visible to other thread before publish} To ensure the access of allocated memory by its own thread before it gets published, we maintain the thread ID in meta-information and any modification or update at the memory address is verified before its publish.
\end{enumerate}

Our implementation makes the assumption that Granary is having full control of kernel memory allocators and can identify and add watchpoint on RCU protected data but this is not true.% and One of the important consideration during implementation is we need to make changes in the memory allocator to identify when the rcu protected data get allocated. 
However we implemented our system with rcutorture module as the target. Rcutorture module allocates rcu protected data from a separate memory pool and it maintains a free-list for garbage collecting the freed pointers. We made some changes in rcutorture module and kernel wrapper to ensure that kernel wrapper receives a callback whenever memory allocation happens from this pool and garbage collector free these memory and adds it to free list. %We consider these changes are minor and can be done for debugging the incorrect usage of RCU. 

We used non-canonical addresses to implement watchpoint. %These addresses get generated from the actual memory address and the shadow memory index storing meta-information. 
Our system uses binary instrumentation to find such addresses and fixes it to get the correct address before doing memory operations. As mentioned in section~\ref{sec:appr} we are using Granary, a comprehensive kernel module instrumentation framework, which only rewrites the kernel module code and loses control when non-module code executes. This makes it possible that any of these addresses can leak to the kernel which when get accessed causes general protection fault. To handle such cases our system takes control of interrupt handler and gives a callback in case of general protection fault. This callbacks checks for any such watched addresses in registers \& stack and fixes them before doing \texttt{iret}. The callback also prevents call to kernel general-protection fault which intern  prevents the overhead of kernel general protection fault handler. We tested our changes with different module like \texttt{e1000} and \texttt{ext3} but with rcutorture module we did not encountered any such case.% of leaking these addresses to kernel.