implementation.tex

In Section~\ref{sec:appr} we discussed 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. In this section we will describe our implementation detail, the challenges we faced and our solution for them.

One of the important challenge while implementing our system was most of the RCU primitives are defined as macro and inline functions 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 functions that gives a callbacks to kernel wrapper on the uses of RCU primitives. 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 {itemize} 
	\item \emph{Access of RCU protected data inside read critical section :} Our system checks the access of RCU protected data by using thread and watchpoint generation number. Before any memory read at watchpoint addresses our system checks both thread \& watchpoint generation number and ensures the following:
	\begin {itemize}
		\item Thread generation number should be even. (\emph{current\_thread\_info()$\rightarrow$spill\_slot[0]\%2 == 0})
		\item Watchpoint generation number should be even and equal to thread generation number. (\emph{meta$\rightarrow$thread\_info$\rightarrow$gen\_nums[n] == current\_thread\_info()$\rightarrow$spill\_slot[0]}) 
		\item Incase of recursive use of read critical section watchpoint generation number should be equal to the sum of thread 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 \emph{Recursive use of read critical section :} Recursive use of read critical section is identified by counting the number of  \emph{rcu\_read\_lock()}  \& \emph{rcu\_read\_unlock()}. Our system uses thread local slot to count these primitive and ensures that there is no mismatch.

	\item \emph{ Direct access of RCU protected data in read critical section :} Any direct access of RCU protected data inside read critical section is not allowed. To check the direct access of rcu protected data from direct access we encode the pointer aliasing information in meta-data, which is set inside \emph{rcu\_dereference()}. This allows us to check the if the access of RCU protected data is happening with direct pointer or through an alias pointer.

	\item \emph{ Reference of RCU protected data in its own read critical section :} This policy ensures the access of RCU pointer in the same critical section where it is dereferenced (\emph{rcu\_dereference}). Our system decides this based on thread and watchpoint generation number, the detail of which is mentioned previously.  

	\item \emph{ No access of allocated memory by other thread befor publish (\emph{rcu\_assign\_pointer()}):} To ensure the access of allocated memory by its own thread before it gets published, we maintain the thred id in meta-information and any modification or update at the memory address is verified before its publish.
\end{itemize}

One of the important consideration for our implementation is we need to make changes in the memory allocator to identify when the rcu protected data get allocated. We implemented our system using rcutorture as the target module. 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 when 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 operation. As mentioned in section~\ref{ref: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 to leak any of these addresses to 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 \emph{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 e1000 and making watchpoint enable but in-case of rcutorture module we did not encountered any case of leaking these addresses to kernel.