background.tex

Programming with RCU is a completely different paradigm as compared to traditional
synchronization techniques. Similar to other techniques, the programmer must take care to clearly define
read critical sections. However, on the update side, the programmer must use another
traditional synchronization technique. We further illustrate difference with the
use of two examples.

\begin{figure}[t]
\centering
\begin{lstlisting}
rwlock_t q_lock;
global datatype *q;

f() {
	...
	rwlock_read_lock(&q_lock);
	do_something(q);
	rwlock_read_unlock(&q_lock);
	...
}
\end{lstlisting}
\caption{Using Reader Writer locks}\label{fig:rwuse}
\end{figure}

\begin{figure}[b]
\centering
\begin{lstlisting}
global datatype *q;

f() {
	dataype *p;
	...
	rcu_read_lock();
	p = rcu_dereference(q);
	do_something(p);
	rcu_read_unlock();
	...
}
\end{lstlisting}
\caption{Using RCU}\label{fig:RCUuse}
\end{figure}

Figure~\ref{fig:rwuse} shows how a
typical Reader Writer lock works. \emph{q} is the shared data which various readers
and writers wish to access. \emph{q\_lock} is used to synchronize access to \emph{q}.
First the reader locks the rwlock, \emph{q\_lock},
in the read mode. It then goes ahead an reads the data in \emph{q}. Finally once it is
done, it unlocks \emph{q\_lock}.

In contrast Figure~\ref{fig:RCUuse} gives an example of how RCU is used. \emph{q} is a global pointer
which points to some data which is protected with the use of RCU. When a reader
wishes to dereference that data, it first announces the beginning of an RCU critical
section using \emph{rcu\_read\_lock}. Then in order to derefence that data, it 
uses \emph{rcu\_dereference}. At this
point it holds a legal reference and RCU guarantees that structure will not be
reclaimed at least until this reader announces the end of the critical section.
The reader now proceeds to go ahead and use the reference it has. Finally once it
is done, it announces the end of a critical section with the use of \emph{rcu\_read\_unlock}.

The key difference to be noted is that while in the case of rwlocks, the readers
need to wait till they can lock the rwlock, RCU readers just announce the start
of a read critical section. In order to ensure that access is not interrupted,
a reference is obtained with the use of \emph{rcu\_dereference}. \emph{rcu\_dereference}
ensures that compiler optimizations which reorder access are prevented, as well
some prevent load store reordering on some architectures such as DEC Alpha.
Finally all accesses
to the shared data is through the use of \emph{p}. RCU guarantees that the data structure
will not be reclaimed till the reader announces the end of its critical section.

In order to aid further discussion, we now define two terms in context of RCU
\begin{itemize}
\item{\bf Quiescent State}: This is the state when a reader is not in an RCU read critical state.
\item{\bf Grace Period}: Any time period during which each thread has been observed in at least one quiescent state.
\end{itemize}

RCU has a list of well defined API. The most commonly used are
\begin{itemize}
\item\emph{rcu\_read\_lock}: Used to announce the beginning of a critical section.
\item\emph{rcu\_read\_unlock}: Used to announce the end of a critical section.
\item\emph{rcu\_dereference}: Used to obtain a reference to shared data
\item\emph{rcu\_assign\_pointer}: Used to announce an update.
\item\emph{synchronize\_rcu}: Used to wait till a grace period has passed.
\item\emph{call\_rcu}: Used to queue up a callback that takes place after the end of some grace period that starts in the future.
\end{itemize}


Using RCU requires careful attention from the programmer. There are some rules
and inherent assumptions while using RCU. For example, access to shared data
should only happen with a reference which has been obtained with the use of
\emph{rcu\_dereference}. This call should also happen only after an RCU read critical
section has announced. Any use of this reference obtained must be made before
this critical section ends. If a new critical section has been announced a
fresh reference must be obtained with the use of \emph{rcu\_dereference}. A quiescent
state (in some flavours of RCU) must only be announced once it has actually
taken place.~\footnote{It is also important to note that while care must be taken to announce a
quiescent state only when it has actually occured, one must not delay the announcement
of the quiescent state. Since RCU maintains multiple copies which are only reclaimed
after a grace period has occured, it serves only to increase the memory pressure on
the system.} On the update side, an update should only take place with use
of \emph{rcu\_assign\_pointer}. There are many other similar rules that must be
followed.