\batchmode
\documentclass[10pt,twocolumn]{book}



\usepackage{lscape}
\usepackage{epsfig}
\usepackage{subfigure}
\usepackage{url}
\usepackage{graphics}
\usepackage{enumerate}
\usepackage{ifthen}
\usepackage{listings}
\lstset{basicstyle=\ttfamily }
\usepackage[bookmarks=true,bookmarksnumbered=true]{hyperref}



\newcounter{quickquizctr} 

\chapter{#2}
	\label{#1}
	\setcounter{quickquizctr}{0}
\refstepcounter{quickquizctr}
	\textbf{Quick Quiz \thechapter .\arabic{quickquizctr}:}


\chapter{Answers to Quick Quizzes}
	\label{chp:Answers to Quick Quizzes}
	~ \\
	%




%
\renewcommand{\QuickQuizAnswerChapter}{\ref{#1}}
	\setcounter{quickquizctr}{0}
	\section{#2}


\refstepcounter{quickquizctr} ~ \\~ \\
	\textbf{Quick Quiz \ref{#1}.\arabic{quickquizctr}:} #1 ~ \\



\begin{enumerate}
	%
\item	Section~\ref{sec:intro:What Makes Parallel Programming Hard?}
	(``What Makes Parallel Programming Hard?'')
	on page~\pageref{sec:intro:What Makes Parallel Programming Hard?}
	originally appeared in a Portland State University Technical Report~\cite{PaulEMcKenney2009ProgrammingHard}.
\item	Section~\ref{sec:defer:RCU Fundamentals}
	(``RCU Fundamentals'')
	on page~\pageref{sec:defer:RCU Fundamentals}
	originally appeared in Linux Weekly News~\cite{PaulEMcKenney2007WhatIsRCUFundamentally}.
\item	Section~\ref{sec:defer:RCU Usage}
	(``RCU Usage'')
	on page~\pageref{sec:defer:RCU Usage}
	originally appeared in Linux Weekly News~\cite{PaulEMcKenney2008WhatIsRCUUsage}.
\item	Section~\ref{sec:defer:RCU Linux-Kernel API}
	(``RCU Linux-Kernel API'')
	on page~\pageref{sec:defer:RCU Linux-Kernel API}
	originally appeared in Linux Weekly News~\cite{PaulEMcKenney2008WhatIsRCUAPI}.
\item	Section~\ref{sec:app:whymb:Memory-Barrier Instructions For Specific CPUs}
	(``Memory-Barrier Instructions For Specific CPUs'')
	on page~\pageref{sec:app:whymb:Memory-Barrier Instructions For Specific CPUs}
	originally appeared in Linux Journal~\cite{PaulMcKenney2005i,PaulMcKenney2005j}.
\item	Section~\ref{app:rcuimpl:Sleepable RCU Implementation}
	(``Sleepable RCU Implementation'')
	on page~\pageref{app:rcuimpl:Sleepable RCU Implementation}
	originally appeared in Linux Weekly News~\cite{PaulEMcKenney2006c}.
\item	Section~\ref{app:rcuimpl:rcutree:Hierarchical RCU Overview}
	(``Hierarchical RCU Overview'')
	on page~\pageref{app:rcuimpl:rcutree:Hierarchical RCU Overview}
	originally appeared in Linux Weekly News~\cite{PaulEMcKenney2008HierarchicalRCU}.
\item	Section~\ref{app:rcuimpl:Preemptible RCU}
	(``Preemptible RCU'')
	on page~\pageref{app:rcuimpl:Preemptible RCU}
	originally appeared in Linux Weekly News~\cite{PaulEMcKenney2007PreemptibleRCU}.
\item	Appendix~\ref{app:formal:Formal Verification}
	(``Formal Verification'')
	on page~\pageref{app:formal:Formal Verification}
	originally appeared in Linux Weekly News~\cite{PaulEMcKenney2007QRCUspin,PaulEMcKenney2008dynticksRCU}.
	\end{enumerate}


\begin{enumerate}
	%
\item	Figure~\ref{fig:cpu:CPU Performance at its Best}
	(p~\pageref{fig:cpu:CPU Performance at its Best})
	by Melissa McKenney.
\item	Figure~\ref{fig:cpu:CPUs Old and New}
	(p~\pageref{fig:cpu:CPUs Old and New})
	by Melissa McKenney.
\item	Figure~\ref{fig:cpu:CPU Meets a Pipeline Flush}
	(p~\pageref{fig:cpu:CPU Meets a Pipeline Flush})
	by Melissa McKenney.
\item	Figure~\ref{fig:cpu:CPU Meets a Memory Reference}
	(p~\pageref{fig:cpu:CPU Meets a Memory Reference})
	by Melissa McKenney.
\item	Figure~\ref{fig:cpu:CPU Meets an Atomic Operation}
	(p~\pageref{fig:cpu:CPU Meets an Atomic Operation})
	by Melissa McKenney.
\item	Figure~\ref{fig:cpu:CPU Meets a Memory Barrier}
	(p~\pageref{fig:cpu:CPU Meets a Memory Barrier})
	by Melissa McKenney.
\item	Figure~\ref{fig:cpu:CPU Meets a Cache Miss}
	(p~\pageref{fig:cpu:CPU Meets a Cache Miss})
	by Melissa McKenney.
\item	Figure~\ref{fig:cpu:CPU Waits for I/O Completion}
	(p~\pageref{fig:cpu:CPU Waits for I/O Completion})
	by Melissa McKenney.
\item	Figure~\ref{fig:SMPdesign:Dining Philosophers Problem}
	(p~\pageref{fig:SMPdesign:Dining Philosophers Problem})
	by Kornilios Kourtis.
\item	Figure~\ref{fig:SMPdesign:Dining Philosophers Problem, Textbook Solution}
	(p~\pageref{fig:SMPdesign:Dining Philosophers Problem, Textbook Solution})
	by Kornilios Kourtis.
\item	Figure~\ref{fig:SMPdesign:Dining Philosophers Problem, Partitioned}
	(p~\pageref{fig:SMPdesign:Dining Philosophers Problem, Partitioned})
	by Kornilios Kourtis.
\item	Figure~\ref{fig:SMPdesign:Lock Contention}
	(p~\pageref{fig:SMPdesign:Lock Contention})
	by Melissa McKenney.
\item	Figure~\ref{fig:SMPdesign:Data Locking}
	(p~\pageref{fig:SMPdesign:Data Locking})
	by Melissa McKenney.
\item	Figure~\ref{fig:SMPdesign:Data and Skew}
	(p~\pageref{fig:SMPdesign:Data and Skew})
	by Melissa McKenney.
\item	Figure~\ref{fig:advsync:CPUs Can Do Things Out of Order}
	(p~\pageref{fig:advsync:CPUs Can Do Things Out of Order})
	by Melissa McKenney.
\item	Figure~\ref{fig:advsync:Abstract Memory Access Model}
	(p~\pageref{fig:advsync:Abstract Memory Access Model})
	by David Howells.
\item	Figure~\ref{fig:advsync:Write Barrier Ordering Semantics}
	(p~\pageref{fig:advsync:Write Barrier Ordering Semantics})
	by David Howells.
\item	Figure~\ref{fig:advsync:Data Dependency Barrier Omitted}
	(p~\pageref{fig:advsync:Data Dependency Barrier Omitted})
	by David Howells.
\item	Figure~\ref{fig:advsync:Data Dependency Barrier Supplied}
	(p~\pageref{fig:advsync:Data Dependency Barrier Supplied})
	by David Howells.
\item	Figure~\ref{fig:advsync:Read Barrier Needed}
	(p~\pageref{fig:advsync:Read Barrier Needed})
	by David Howells.
\item	Figure~\ref{fig:advsync:Read Barrier Supplied}
	(p~\pageref{fig:advsync:Read Barrier Supplied})
	by David Howells.
\item	Figure~\ref{fig:advsync:Read Barrier Supplied, Double Load}
	(p~\pageref{fig:advsync:Read Barrier Supplied, Double Load})
	by David Howells.
\item	Figure~\ref{fig:advsync:Read Barrier Supplied, Take Two}
	(p~\pageref{fig:advsync:Read Barrier Supplied, Take Two})
	by David Howells.
\item	Figure~\ref{fig:advsync:Speculative Load}
	(p~\pageref{fig:advsync:Speculative Load})
	by David Howells.
\item	Figure~\ref{fig:advsync:Speculative Loads and Barrier}
	(p~\pageref{fig:advsync:Speculative Loads and Barrier})
	by David Howells.
\item	Figure~\ref{fig:advsync:Speculative Loads Cancelled by Barrier}
	(p~\pageref{fig:advsync:Speculative Loads Cancelled by Barrier})
	by David Howells.
\item	Figure~\ref{fig:advsync:Memory Architecture}
	(p~\pageref{fig:advsync:Memory Architecture})
	by David Howells.
\item	Figure~\ref{fig:advsync:Split Caches}
	(p~\pageref{fig:advsync:Split Caches})
	by David Howells.
\item	Figure~\ref{fig:easy:Shaving the Mandelbrot Set}
	(p~\pageref{fig:easy:Shaving the Mandelbrot Set})
	by Melissa McKenney.
\item	Figure~\ref{fig:app:whymb:Half Memory Barrier}
	(p~\pageref{fig:app:whymb:Half Memory Barrier})
	by Melissa McKenney.
\item	Figure~\ref{fig:app:rcuimpl:srcu:Sleeping While RCU Reading Considered Harmful}
	(p~\pageref{fig:app:rcuimpl:srcu:Sleeping While RCU Reading Considered Harmful})
	by Melissa McKenney.
\item	Figure~\ref{fig:SMPdesign:Dining Philosophers Problem, Fully Partitioned}
	(p~\pageref{fig:SMPdesign:Dining Philosophers Problem, Fully Partitioned})
	by Kornilios Kourtis.
	\end{enumerate}


\item	#1~\ref{#2} (``#3'') on page~\pageref{#2}
		originally appeared in #4~\cite{#5}.


\item	#1~\ref{#2}--\ref{#3} (``#4'')
		on pages~\pageref{#2}--\pageref{#2}
		originally appeared in #5~\cite{#6}.


\item	#1~\ref{#2} (p~\pageref{#2}) by #3.




\usepackage[dvips]{color}


\pagecolor[gray]{.7}

\usepackage[]{inputenc}



\makeatletter

\makeatletter
\count@=\the\catcode`\_ \catcode`\_=8 
\newenvironment{tex2html_wrap}{}{}%
\catcode`\<=12\catcode`\_=\count@
\newcommand{\providedcommand}[1]{\expandafter\providecommand\csname #1\endcsname}%
\newcommand{\renewedcommand}[1]{\expandafter\providecommand\csname #1\endcsname{}%
  \expandafter\renewcommand\csname #1\endcsname}%
\newcommand{\newedenvironment}[1]{\newenvironment{#1}{}{}\renewenvironment{#1}}%
\let\newedcommand\renewedcommand
\let\renewedenvironment\newedenvironment
\makeatother
\let\mathon=$
\let\mathoff=$
\ifx\AtBeginDocument\undefined \newcommand{\AtBeginDocument}[1]{}\fi
\newbox\sizebox
\setlength{\hoffset}{0pt}\setlength{\voffset}{0pt}
\addtolength{\textheight}{\footskip}\setlength{\footskip}{0pt}
\addtolength{\textheight}{\topmargin}\setlength{\topmargin}{0pt}
\addtolength{\textheight}{\headheight}\setlength{\headheight}{0pt}
\addtolength{\textheight}{\headsep}\setlength{\headsep}{0pt}
\setlength{\textwidth}{349pt}
\newwrite\lthtmlwrite
\makeatletter
\let\realnormalsize=\normalsize
\global\topskip=2sp
\def\preveqno{}\let\real@float=\@float \let\realend@float=\end@float
\def\@float{\let\@savefreelist\@freelist\real@float}
\def\liih@math{\ifmmode$\else\bad@math\fi}
\def\end@float{\realend@float\global\let\@freelist\@savefreelist}
\let\real@dbflt=\@dbflt \let\end@dblfloat=\end@float
\let\@largefloatcheck=\relax
\let\if@boxedmulticols=\iftrue
\def\@dbflt{\let\@savefreelist\@freelist\real@dbflt}
\def\adjustnormalsize{\def\normalsize{\mathsurround=0pt \realnormalsize
 \parindent=0pt\abovedisplayskip=0pt\belowdisplayskip=0pt}%
 \def\phantompar{\csname par\endcsname}\normalsize}%
\def\lthtmltypeout#1{{\let\protect\string \immediate\write\lthtmlwrite{#1}}}%
\newcommand\lthtmlhboxmathA{\adjustnormalsize\setbox\sizebox=\hbox\bgroup\kern.05em }%
\newcommand\lthtmlhboxmathB{\adjustnormalsize\setbox\sizebox=\hbox to\hsize\bgroup\hfill }%
\newcommand\lthtmlvboxmathA{\adjustnormalsize\setbox\sizebox=\vbox\bgroup %
 \let\ifinner=\iffalse \let\)\liih@math }%
\newcommand\lthtmlboxmathZ{\@next\next\@currlist{}{\def\next{\voidb@x}}%
 \expandafter\box\next\egroup}%
\newcommand\lthtmlmathtype[1]{\gdef\lthtmlmathenv{#1}}%
\newcommand\lthtmllogmath{\dimen0\ht\sizebox \advance\dimen0\dp\sizebox
  \ifdim\dimen0>.95\vsize
   \lthtmltypeout{%
*** image for \lthtmlmathenv\space is too tall at \the\dimen0, reducing to .95 vsize ***}%
   \ht\sizebox.95\vsize \dp\sizebox\z@ \fi
  \lthtmltypeout{l2hSize %
:\lthtmlmathenv:\the\ht\sizebox::\the\dp\sizebox::\the\wd\sizebox.\preveqno}}%
\newcommand\lthtmlfigureA[1]{\let\@savefreelist\@freelist
       \lthtmlmathtype{#1}\lthtmlvboxmathA}%
\newcommand\lthtmlpictureA{\bgroup\catcode`\_=8 \lthtmlpictureB}%
\newcommand\lthtmlpictureB[1]{\lthtmlmathtype{#1}\egroup
       \let\@savefreelist\@freelist \lthtmlhboxmathB}%
\newcommand\lthtmlpictureZ[1]{\hfill\lthtmlfigureZ}%
\newcommand\lthtmlfigureZ{\lthtmlboxmathZ\lthtmllogmath\copy\sizebox
       \global\let\@freelist\@savefreelist}%
\newcommand\lthtmldisplayA{\bgroup\catcode`\_=8 \lthtmldisplayAi}%
\newcommand\lthtmldisplayAi[1]{\lthtmlmathtype{#1}\egroup\lthtmlvboxmathA}%
\newcommand\lthtmldisplayB[1]{\edef\preveqno{(\theequation)}%
  \lthtmldisplayA{#1}\let\@eqnnum\relax}%
\newcommand\lthtmldisplayZ{\lthtmlboxmathZ\lthtmllogmath\lthtmlsetmath}%
\newcommand\lthtmlinlinemathA{\bgroup\catcode`\_=8 \lthtmlinlinemathB}
\newcommand\lthtmlinlinemathB[1]{\lthtmlmathtype{#1}\egroup\lthtmlhboxmathA
  \vrule height1.5ex width0pt }%
\newcommand\lthtmlinlineA{\bgroup\catcode`\_=8 \lthtmlinlineB}%
\newcommand\lthtmlinlineB[1]{\lthtmlmathtype{#1}\egroup\lthtmlhboxmathA}%
\newcommand\lthtmlinlineZ{\egroup\expandafter\ifdim\dp\sizebox>0pt %
  \expandafter\centerinlinemath\fi\lthtmllogmath\lthtmlsetinline}
\newcommand\lthtmlinlinemathZ{\egroup\expandafter\ifdim\dp\sizebox>0pt %
  \expandafter\centerinlinemath\fi\lthtmllogmath\lthtmlsetmath}
\newcommand\lthtmlindisplaymathZ{\egroup %
  \centerinlinemath\lthtmllogmath\lthtmlsetmath}
\def\lthtmlsetinline{\hbox{\vrule width.1em \vtop{\vbox{%
  \kern.1em\copy\sizebox}\ifdim\dp\sizebox>0pt\kern.1em\else\kern.3pt\fi
  \ifdim\hsize>\wd\sizebox \hrule depth1pt\fi}}}
\def\lthtmlsetmath{\hbox{\vrule width.1em\kern-.05em\vtop{\vbox{%
  \kern.1em\kern0.8 pt\hbox{\hglue.17em\copy\sizebox\hglue0.8 pt}}\kern.3pt%
  \ifdim\dp\sizebox>0pt\kern.1em\fi \kern0.8 pt%
  \ifdim\hsize>\wd\sizebox \hrule depth1pt\fi}}}
\def\centerinlinemath{%
  \dimen1=\ifdim\ht\sizebox<\dp\sizebox \dp\sizebox\else\ht\sizebox\fi
  \advance\dimen1by.5pt \vrule width0pt height\dimen1 depth\dimen1 
 \dp\sizebox=\dimen1\ht\sizebox=\dimen1\relax}

\def\lthtmlcheckvsize{\ifdim\ht\sizebox<\vsize 
  \ifdim\wd\sizebox<\hsize\expandafter\hfill\fi \expandafter\vfill
  \else\expandafter\vss\fi}%
\providecommand{\selectlanguage}[1]{}%
\makeatletter \tracingstats = 1 


\begin{document}
\pagestyle{empty}\thispagestyle{empty}\lthtmltypeout{}%
\lthtmltypeout{latex2htmlLength hsize=\the\hsize}\lthtmltypeout{}%
\lthtmltypeout{latex2htmlLength vsize=\the\vsize}\lthtmltypeout{}%
\lthtmltypeout{latex2htmlLength hoffset=\the\hoffset}\lthtmltypeout{}%
\lthtmltypeout{latex2htmlLength voffset=\the\voffset}\lthtmltypeout{}%
\lthtmltypeout{latex2htmlLength topmargin=\the\topmargin}\lthtmltypeout{}%
\lthtmltypeout{latex2htmlLength topskip=\the\topskip}\lthtmltypeout{}%
\lthtmltypeout{latex2htmlLength headheight=\the\headheight}\lthtmltypeout{}%
\lthtmltypeout{latex2htmlLength headsep=\the\headsep}\lthtmltypeout{}%
\lthtmltypeout{latex2htmlLength parskip=\the\parskip}\lthtmltypeout{}%
\lthtmltypeout{latex2htmlLength oddsidemargin=\the\oddsidemargin}\lthtmltypeout{}%
\makeatletter
\if@twoside\lthtmltypeout{latex2htmlLength evensidemargin=\the\evensidemargin}%
\else\lthtmltypeout{latex2htmlLength evensidemargin=\the\oddsidemargin}\fi%
\lthtmltypeout{}%
\makeatother
\setcounter{page}{1}
\onecolumn

% !!! IMAGES START HERE !!!

\setcounter{quickquizctr}{0}
\refstepcounter{quickquizctr}
\setcounter{quickquizctr}{0}
\refstepcounter{quickquizctr}
\stepcounter{chapter}
\stepcounter{chapter}
\stepcounter{section}
\setcounter{topnumber}{3}
\setcounter{bottomnumber}{2}
\setcounter{totalnumber}{5}
\setcounter{dbltopnumber}{3}


\setlength{\textheight}{8.25in}%

\setlength{\textheight}{8.25in}


\setlength{\textwidth}{6.5in}%

\setlength{\textwidth}{6.5in}


\setlength{\columnsep}{0.25in}%

\setlength{\columnsep}{0.25in}


\newboolean{inbook}%

\setcounter{secnumdepth}{3}
\setboolean{inbook}{true}
\stepcounter{chapter}
\stepcounter{section}
\stepcounter{section}
\stepcounter{subsection}
{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap549}%
\resizebox{3in}{!}{\includegraphics{SMPdesign/clockfreq}}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsection}
{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap577}%
\resizebox{3in}{!}{\includegraphics{SMPdesign/mipsperbuck}}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsection}
{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap601}%
\resizebox{3in}{!}{\includegraphics{intro/PPGrelation}}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap609}%
\resizebox{3in}{!}{\includegraphics{intro/Generality}}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{section}
\stepcounter{subsection}
\stepcounter{subsection}
\stepcounter{subsection}
\stepcounter{section}
{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap675}%
\resizebox{3in}{!}{\includegraphics{intro/FourTaskCategories}}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsection}
\stepcounter{subsection}
\stepcounter{subsection}
\stepcounter{subsection}
\stepcounter{subsection}
{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap723}%
\resizebox{3in}{!}{\includegraphics{intro/FourTaskOrder}}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsection}
\stepcounter{section}
\stepcounter{subsection}
\stepcounter{subsection}
\stepcounter{chapter}
\stepcounter{section}
{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap900}%
\resizebox{3in}{!}{\includegraphics{cartoons/trackmeet}}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsection}
{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap910}%
\resizebox{3in}{!}{\includegraphics{cartoons/whippersnapper}}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap920}%
\resizebox{3in}{!}{\includegraphics{cartoons/pipeline}}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsection}
{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap936}%
\resizebox{3in}{!}{\includegraphics{cartoons/ref}}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsection}
{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap950}%
\resizebox{3in}{!}{\includegraphics{cartoons/atomic}}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsection}
{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap972}%
\resizebox{3in}{!}{\includegraphics{cartoons/barrier}}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsection}
{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap982}%
\resizebox{3in}{!}{\includegraphics{cartoons/tollbooth}}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsection}
{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap992}%
\resizebox{3in}{!}{\includegraphics{cartoons/PhoneBooth}}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{section}
\stepcounter{subsection}
{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap1051}%
\resizebox{3in}{!}{\includegraphics{cpu/SystemArch}}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsection}
\stepcounter{section}
\stepcounter{subsection}
{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap1146}%
\resizebox{3in}{!}{\includegraphics{cpu/3DI}}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsection}
\stepcounter{subsection}
\stepcounter{subsection}
\stepcounter{section}
\stepcounter{chapter}
\stepcounter{section}
{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap1702}%
\resizebox{3in}{!}{\includegraphics{toolsoftrade/shellparallel}}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{section}
\stepcounter{subsection}
{\newpage\clearpage
\lthtmlfigureA{figure1258}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 pid = fork();
  2 if (pid == 0) {
  3   /* child */
  4 } else if (pid < 0) {
  5   /* parent, upon error */
  6   perror("fork");
  7   exit(-1);
  8 } else {
  9   /* parent, pid == child ID */
 10 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlfigureA{figure1275}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 void waitall(void)
  2 {
  3   int pid;
  4   int status;
  5 
  6   for (;;) {
  7     pid = wait(&status);
  8     if (pid == -1) {
  9       if (errno == ECHILD)
 10         break;
 11       perror("wait");
 12       exit(-1);
 13     }
 14   }
 15 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlfigureA{figure1296}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 int x = 0;
  2 int pid;
  3 
  4 pid = fork();
  5 if (pid == 0) { /* child */
  6   x = 1;
  7   printf("Child process set x=1\n");
  8   exit(0);
  9 }
 10 if (pid < 0) { /* parent, upon error */
 11   perror("fork");
 12   exit(-1);
 13 }
 14 waitall();
 15 printf("Parent process sees x=%d\n", x);
\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsection}
{\newpage\clearpage
\lthtmlfigureA{figure1321}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 int x = 0;
  2 
  3 void *mythread(void *arg)
  4 {
  5   x = 1;
  6   printf("Child process set x=1\n");
  7   return NULL;
  8 }
  9 
 10 int main(int argc, char *argv[])
 11 {
 12   pthread_t tid;
 13   void *vp;
 14 
 15   if (pthread_create(&tid, NULL, mythread, NULL) != 0) {
 16     perror("pthread_create");
 17     exit(-1);
 18   }
 19   if (pthread_join(tid, &vp) != 0) {
 20     perror("pthread_join");
 21     exit(-1);
 22   }
 23   printf("Parent process sees x=%d\n", x);
 24   return 0;
 25 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsection}
{\newpage\clearpage
\lthtmlfigureA{figure1371}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 pthread_mutex_t lock_a = PTHREAD_MUTEX_INITIALIZER;
  2 pthread_mutex_t lock_b = PTHREAD_MUTEX_INITIALIZER;
  3 int x = 0;
  4 
  5 void *lock_reader(void *arg)
  6 {
  7   int i;
  8   int newx = -1;
  9   int oldx = -1;
 10   pthread_mutex_t *pmlp = (pthread_mutex_t *)arg;
 11 
 12   if (pthread_mutex_lock(pmlp) != 0) {
 13     perror("lock_reader:pthread_mutex_lock");
 14     exit(-1);
 15   }
 16   for (i = 0; i < 100; i++) {
 17     newx = ACCESS_ONCE(x);
 18     if (newx != oldx) {
 19       printf("lock_reader(): x = %d\n", newx);
 20     }
 21     oldx = newx;
 22     poll(NULL, 0, 1);
 23   }
 24   if (pthread_mutex_unlock(pmlp) != 0) {
 25     perror("lock_reader:pthread_mutex_unlock");
 26     exit(-1);
 27   }
 28   return NULL;
 29 }
 30 
 31 void *lock_writer(void *arg)
 32 {
 33   int i;
 34   pthread_mutex_t *pmlp = (pthread_mutex_t *)arg;
 35 
 36   if (pthread_mutex_lock(pmlp) != 0) {
 37     perror("lock_reader:pthread_mutex_lock");
 38     exit(-1);
 39   }
 40   for (i = 0; i < 3; i++) {
 41     ACCESS_ONCE(x)++;
 42     poll(NULL, 0, 5);
 43   }
 44   if (pthread_mutex_unlock(pmlp) != 0) {
 45     perror("lock_reader:pthread_mutex_unlock");
 46     exit(-1);
 47   }
 48   return NULL;
 49 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlfigureA{figure1410}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1   printf("Creating two threads using same lock:\n");
  2   if (pthread_create(&tid1, NULL,
  3                      lock_reader, &lock_a) != 0) {
  4     perror("pthread_create");
  5     exit(-1);
  6   }
  7   if (pthread_create(&tid2, NULL,
  8                      lock_writer, &lock_a) != 0) {
  9     perror("pthread_create");
 10     exit(-1);
 11   }
 12   if (pthread_join(tid1, &vp) != 0) {
 13     perror("pthread_join");
 14     exit(-1);
 15   }
 16   if (pthread_join(tid2, &vp) != 0) {
 17     perror("pthread_join");
 18     exit(-1);
 19   }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlfigureA{figure1435}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1   printf("Creating two threads w/different locks:\n");
  2   x = 0;
  3   if (pthread_create(&tid1, NULL,
  4                      lock_reader, &lock_a) != 0) {
  5     perror("pthread_create");
  6     exit(-1);
  7   }
  8   if (pthread_create(&tid2, NULL,
  9                      lock_writer, &lock_b) != 0) {
 10     perror("pthread_create");
 11     exit(-1);
 12   }
 13   if (pthread_join(tid1, &vp) != 0) {
 14     perror("pthread_join");
 15     exit(-1);
 16   }
 17   if (pthread_join(tid2, &vp) != 0) {
 18     perror("pthread_join");
 19     exit(-1);
 20   }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsection}
{\newpage\clearpage
\lthtmlfigureA{figure1481}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 pthread_rwlock_t rwl = PTHREAD_RWLOCK_INITIALIZER;
  2 int holdtime = 0;
  3 int thinktime = 0;
  4 long long *readcounts;
  5 int nreadersrunning = 0;
  6 
  7 #define GOFLAG_INIT 0
  8 #define GOFLAG_RUN  1
  9 #define GOFLAG_STOP 2
 10 char goflag = GOFLAG_INIT;
 11 
 12 void *reader(void *arg)
 13 {
 14   int i;
 15   long long loopcnt = 0;
 16   long me = (long)arg;
 17 
 18   __sync_fetch_and_add(&nreadersrunning, 1);
 19   while (ACCESS_ONCE(goflag) == GOFLAG_INIT) {
 20     continue;
 21   }
 22   while (ACCESS_ONCE(goflag) == GOFLAG_RUN) {
 23     if (pthread_rwlock_rdlock(&rwl) != 0) {
 24       perror("pthread_rwlock_rdlock");
 25       exit(-1);
 26     }
 27     for (i = 1; i < holdtime; i++) {
 28       barrier();
 29     }
 30     if (pthread_rwlock_unlock(&rwl) != 0) {
 31       perror("pthread_rwlock_unlock");
 32       exit(-1);
 33     }
 34     for (i = 1; i < thinktime; i++) {
 35       barrier();
 36     }
 37     loopcnt++;
 38   }
 39   readcounts[me] = loopcnt;
 40   return NULL;
 41 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap1896}%
\resizebox{3in}{!}{\includegraphics{CodeSamples/toolsoftrade/rwlockscale}}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmldisplayA{displaymath1516}%
\begin{displaymath}
	\frac{L_N}{N L_1}
\end{displaymath}%
\lthtmldisplayZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlinlinemathA{tex2html_wrap_inline1680}%
$N$%
\lthtmlinlinemathZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlinlinemathA{tex2html_wrap_inline1682}%
$L_N$%
\lthtmlinlinemathZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlinlinemathA{tex2html_wrap_inline1686}%
$L_1$%
\lthtmlinlinemathZ
\lthtmlcheckvsize\clearpage}

\stepcounter{section}
\stepcounter{section}
\stepcounter{section}
\stepcounter{chapter}
\stepcounter{section}
{\newpage\clearpage
\lthtmlfigureA{figure1984}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 long counter = 0;
  2 
  3 void inc_count(void)
  4 {
  5   counter++;
  6 }
  7 
  8 long read_count(void)
  9 {
 10   return counter;
 11 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlfigureA{figure1998}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 atomic_t counter = ATOMIC_INIT(0);
  2 
  3 void inc_count(void)
  4 {
  5   atomic_inc(&counter);
  6 }
  7 
  8 long read_count(void)
  9 {
 10   return atomic_read(&counter);
 11 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap2889}%
\resizebox{3in}{!}{\includegraphics{CodeSamples/count/atomic}}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlinlinemathA{tex2html_wrap_inline2819}%
$y=1$%
\lthtmlinlinemathZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap2909}%
\resizebox{3in}{!}{\includegraphics{count/GlobalInc}}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{section}
\stepcounter{subsection}
\stepcounter{subsection}
{\newpage\clearpage
\lthtmlfigureA{figure2046}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 DEFINE_PER_THREAD(long, counter);
  2 
  3 void inc_count(void)
  4 {
  5   __get_thread_var(counter)++;
  6 }
  7 
  8 long read_count(void)
  9 {
 10   int t;
 11   long sum = 0;
 12 
 13   for_each_thread(t)
 14     sum += per_thread(counter, t);
 15   return sum;
 16 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap2969}%
\resizebox{3in}{!}{\includegraphics{count/PerThreadInc}}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsection}
{\newpage\clearpage
\lthtmlfigureA{figure2089}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 DEFINE_PER_THREAD(atomic_t, counter);
  2 atomic_t global_count;
  3 int stopflag;
  4 
  5 void inc_count(void)
  6 {
  7   atomic_inc(&__get_thread_var(counter));
  8 }
  9 
 10 unsigned long read_count(void)
 11 {
 12   return atomic_read(&global_count);
 13 }
 14 
 15 void *eventual(void *arg)
 16 {
 17   int t;
 18   int sum;
 19 
 20   while (stopflag < 3) {
 21     sum = 0;
 22     for_each_thread(t)
 23       sum += atomic_xchg(&per_thread(counter, t), 0);
 24     atomic_add(sum, &global_count);
 25     poll(NULL, 0, 1);
 26     if (stopflag) {
 27       smp_mb();
 28       stopflag++;
 29     }
 30   }
 31   return NULL;
 32 }
 33 
 34 void count_init(void)
 35 {
 36   thread_id_t tid;
 37 
 38   if (pthread_create(&tid, NULL, eventual, NULL) != 0) {
 39     perror("count_init:pthread_create");
 40     exit(-1);
 41   }
 42 }
 43 
 44 void count_cleanup(void)
 45 {
 46   stopflag = 1;
 47   while (stopflag < 3)
 48     poll(NULL, 0, 1);
 49   smp_mb();
 50 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsection}
{\newpage\clearpage
\lthtmlfigureA{figure2124}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 long __thread counter = 0;
  2 long *counterp[NR_THREADS] = { NULL };
  3 long finalcount = 0;
  4 DEFINE_SPINLOCK(final_mutex);
  5 
  6 void inc_count(void)
  7 {
  8   counter++;
  9 }
 10 
 11 long read_count(void)
 12 {
 13   int t;
 14   long sum;
 15 
 16   spin_lock(&final_mutex);
 17   sum = finalcount;
 18   for_each_thread(t)
 19     if (counterp[t] != NULL)
 20       sum += *counterp[t];
 21   spin_unlock(&final_mutex);
 22   return sum;
 23 }
 24 
 25 void count_register_thread(void)
 26 {
 27   int idx = smp_thread_id();
 28 
 29   spin_lock(&final_mutex);
 30   counterp[idx] = 
 31   spin_unlock(&final_mutex);
 32 }
 33 
 34 void count_unregister_thread(int nthreadsexpected)
 35 {
 36   int idx = smp_thread_id();
 37 
 38   spin_lock(&final_mutex);
 39   finalcount += counter;
 40   counterp[idx] = NULL;
 41   spin_unlock(&final_mutex);
 42 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsection}
\stepcounter{section}
\stepcounter{subsection}
\stepcounter{subsection}
{\newpage\clearpage
\lthtmlfigureA{figure2185}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 unsigned long __thread counter = 0;
  2 unsigned long __thread countermax = 0;
  3 unsigned long globalcountmax = 10000;
  4 unsigned long globalcount = 0;
  5 unsigned long globalreserve = 0;
  6 unsigned long *counterp[NR_THREADS] = { NULL };
  7 DEFINE_SPINLOCK(gblcnt_mutex);\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap3085}%
\resizebox{3in}{!}{\includegraphics{count/count_lim}}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlfigureA{figure2223}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 int add_count(unsigned long delta)
  2 {
  3   if (countermax - counter >= delta) {
  4     counter += delta;
  5     return 1;
  6   }
  7   spin_lock(&gblcnt_mutex);
  8   globalize_count();
  9   if (globalcountmax -
 10       globalcount - globalreserve < delta) {
 11     spin_unlock(&gblcnt_mutex);
 12     return 0;
 13   }
 14   globalcount += delta;
 15   balance_count();
 16   spin_unlock(&gblcnt_mutex);
 17   return 1;
 18 }
 19 
 20 int sub_count(unsigned long delta)
 21 {
 22   if (counter >= delta) {
 23     counter -= delta;
 24     return 1;
 25   }
 26   spin_lock(&gblcnt_mutex);
 27   globalize_count();
 28   if (globalcount < delta) {
 29     spin_unlock(&gblcnt_mutex);
 30     return 0;
 31   }
 32   globalcount -= delta;
 33   balance_count();
 34   spin_unlock(&gblcnt_mutex);
 35   return 1;
 36 }
 37 
 38 unsigned long read_count(void)
 39 {
 40   int t;
 41   unsigned long sum;
 42 
 43   spin_lock(&gblcnt_mutex);
 44   sum = globalcount;
 45   for_each_thread(t)
 46     if (counterp[t] != NULL)
 47       sum += *counterp[t];
 48   spin_unlock(&gblcnt_mutex);
 49   return sum;
 50 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlfigureA{figure2302}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 static void globalize_count(void)
  2 {
  3   globalcount += counter;
  4   counter = 0;
  5   globalreserve -= countermax;
  6   countermax = 0;
  7 }
  8 
  9 static void balance_count(void)
 10 {
 11   countermax = globalcountmax -
 12                globalcount - globalreserve;
 13   countermax /= num_online_threads();
 14   globalreserve += countermax;
 15   counter = countermax / 2;
 16   if (counter > globalcount)
 17     counter = globalcount;
 18   globalcount -= counter;
 19 }
 20 
 21 void count_register_thread(void)
 22 {
 23   int idx = smp_thread_id();
 24 
 25   spin_lock(&gblcnt_mutex);
 26   counterp[idx] = 
 27   spin_unlock(&gblcnt_mutex);
 28 }
 29 
 30 void count_unregister_thread(int nthreadsexpected)
 31 {
 32   int idx = smp_thread_id();
 33 
 34   spin_lock(&gblcnt_mutex);
 35   globalize_count();
 36   counterp[idx] = NULL;
 37   spin_unlock(&gblcnt_mutex);
 38 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsection}
\stepcounter{subsection}
{\newpage\clearpage
\lthtmlfigureA{figure2362}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 unsigned long __thread counter = 0;
  2 unsigned long __thread countermax = 0;
  3 unsigned long globalcountmax = 10000;
  4 unsigned long globalcount = 0;
  5 unsigned long globalreserve = 0;
  6 unsigned long *counterp[NR_THREADS] = { NULL };
  7 DEFINE_SPINLOCK(gblcnt_mutex);
  8 #define MAX_COUNTERMAX 100\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlfigureA{figure2368}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 static void balance_count(void)
  2 {
  3   countermax = globalcountmax - globalcount - globalreserve;
  4   countermax /= num_online_threads();
  5   if (countermax > MAX_COUNTERMAX)
  6     countermax = MAX_COUNTERMAX;
  7   globalreserve += countermax;
  8   counter = countermax / 2;
  9   if (counter > globalcount)
 10     counter = globalcount;
 11   globalcount -= counter;
 12 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsection}
\stepcounter{section}
\stepcounter{subsection}
{\newpage\clearpage
\lthtmlfigureA{figure2398}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 atomic_t __thread counterandmax = ATOMIC_INIT(0);
  2 unsigned long globalcountmax = 10000;
  3 unsigned long globalcount = 0;
  4 unsigned long globalreserve = 0;
  5 atomic_t *counterp[NR_THREADS] = { NULL };
  6 DEFINE_SPINLOCK(gblcnt_mutex);
  7 #define CM_BITS (sizeof(atomic_t) * 4)
  8 #define MAX_COUNTERMAX ((1 << CM_BITS) - 1)
  9 
 10 static void
 11 split_counterandmax_int(int cami, int *c, int *cm)
 12 {
 13   *c = (cami >> CM_BITS) & MAX_COUNTERMAX;
 14   *cm = cami & MAX_COUNTERMAX;
 15 }
 16 
 17 static void
 18 split_counterandmax(atomic_t *cam, int *old,
 19                     int *c, int *cm)
 20 {
 21   unsigned int cami = atomic_read(cam);
 22 
 23   *old = cami;
 24   split_counterandmax_int(cami, c, cm);
 25 }
 26 
 27 static int merge_counterandmax(int c, int cm)
 28 {
 29   unsigned int cami;
 30 
 31   cami = (c << CM_BITS) | cm;
 32   return ((int)cami);
 33 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlfigureA{figure2453}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 int add_count(unsigned long delta)
  2 {
  3   int c;
  4   int cm;
  5   int old;
  6   int new;
  7 
  8   do {
  9     split_counterandmax(&counterandmax, &old, &c, &cm);
 10     if (delta > MAX_COUNTERMAX || c + delta > cm)
 11       goto slowpath;
 12     new = merge_counterandmax(c + delta, cm);
 13   } while (atomic_cmpxchg(&counterandmax,
 14                           old, new) != old);
 15   return 1;
 16 slowpath:
 17   spin_lock(&gblcnt_mutex);
 18   globalize_count();
 19   if (globalcountmax - globalcount -
 20       globalreserve < delta) {
 21     flush_local_count();
 22     if (globalcountmax - globalcount -
 23         globalreserve < delta) {
 24       spin_unlock(&gblcnt_mutex);
 25       return 0;
 26     }
 27   }
 28   globalcount += delta;
 29   balance_count();
 30   spin_unlock(&gblcnt_mutex);
 31   return 1;
 32 }
 33 
 34 int sub_count(unsigned long delta)
 35 {
 36   int c;
 37   int cm;
 38   int old;
 39   int new;
 40 
 41   do {
 42     split_counterandmax(&counterandmax, &old, &c, &cm);
 43     if (delta > c)
 44       goto slowpath;
 45     new = merge_counterandmax(c - delta, cm);
 46   } while (atomic_cmpxchg(&counterandmax,
 47                           old, new) != old);
 48   return 1;
 49 slowpath:
 50   spin_lock(&gblcnt_mutex);
 51   globalize_count();
 52   if (globalcount < delta) {
 53     flush_local_count();
 54     if (globalcount < delta) {
 55       spin_unlock(&gblcnt_mutex);
 56       return 0;
 57     }
 58   }
 59   globalcount -= delta;
 60   balance_count();
 61   spin_unlock(&gblcnt_mutex);
 62   return 1;
 63 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlfigureA{figure2503}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 unsigned long read_count(void)
  2 {
  3   int c;
  4   int cm;
  5   int old;
  6   int t;
  7   unsigned long sum;
  8 
  9   spin_lock(&gblcnt_mutex);
 10   sum = globalcount;
 11   for_each_thread(t)
 12     if (counterp[t] != NULL) {
 13       split_counterandmax(counterp[t], &old, &c, &cm);
 14       sum += c;
 15     }
 16   spin_unlock(&gblcnt_mutex);
 17   return sum;
 18 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlfigureA{figure2515}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 static void globalize_count(void)
  2 {
  3   int c;
  4   int cm;
  5   int old;
  6 
  7   split_counterandmax(&counterandmax, &old, &c, &cm);
  8   globalcount += c;
  9   globalreserve -= cm;
 10   old = merge_counterandmax(0, 0);
 11   atomic_set(&counterandmax, old);
 12 }
 13 
 14 static void flush_local_count(void)
 15 {
 16   int c;
 17   int cm;
 18   int old;
 19   int t;
 20   int zero;
 21 
 22   if (globalreserve == 0)
 23     return;
 24   zero = merge_counterandmax(0, 0);
 25   for_each_thread(t)
 26     if (counterp[t] != NULL) {
 27       old = atomic_xchg(counterp[t], zero);
 28       split_counterandmax_int(old, &c, &cm);
 29       globalcount += c;
 30       globalreserve -= cm;
 31     }
 32 }
 33 
 34 static void balance_count(void)
 35 {
 36   int c;
 37   int cm;
 38   int old;
 39   unsigned long limit;
 40 
 41   limit = globalcountmax - globalcount - globalreserve;
 42   limit /= num_online_threads();
 43   if (limit > MAX_COUNTERMAX)
 44     cm = MAX_COUNTERMAX;
 45   else
 46     cm = limit;
 47   globalreserve += cm;
 48   c = cm / 2;
 49   if (c > globalcount)
 50     c = globalcount;
 51   globalcount -= c;
 52   old = merge_counterandmax(c, cm);
 53   atomic_set(&counterandmax, old);
 54 }
 55 
 56 void count_register_thread(void)
 57 {
 58   int idx = smp_thread_id();
 59 
 60   spin_lock(&gblcnt_mutex);
 61   counterp[idx] = 
 62   spin_unlock(&gblcnt_mutex);
 63 }
 64 
 65 void count_unregister_thread(int nthreadsexpected)
 66 {
 67   int idx = smp_thread_id();
 68 
 69   spin_lock(&gblcnt_mutex);
 70   globalize_count();
 71   counterp[idx] = NULL;
 72   spin_unlock(&gblcnt_mutex);
 73 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsection}
\stepcounter{subsection}
{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap3289}%
\resizebox{2in}{!}{\includegraphics{count/sig-theft}}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsection}
{\newpage\clearpage
\lthtmlfigureA{figure2606}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 #define THEFT_IDLE  0
  2 #define THEFT_REQ   1
  3 #define THEFT_ACK   2
  4 #define THEFT_READY 3
  5 
  6 int __thread theft = THEFT_IDLE;
  7 int __thread counting = 0;
  8 unsigned long __thread counter = 0;
  9 unsigned long __thread countermax = 0;
 10 unsigned long globalcountmax = 10000;
 11 unsigned long globalcount = 0;
 12 unsigned long globalreserve = 0;
 13 unsigned long *counterp[NR_THREADS] = { NULL };
 14 unsigned long *countermaxp[NR_THREADS] = { NULL };
 15 int *theftp[NR_THREADS] = { NULL };
 16 DEFINE_SPINLOCK(gblcnt_mutex);
 17 #define MAX_COUNTERMAX 100\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlfigureA{figure2616}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 static void globalize_count(void)
  2 {
  3   globalcount += counter;
  4   counter = 0;
  5   globalreserve -= countermax;
  6   countermax = 0;
  7 }
  8 
  9 static void flush_local_count_sig(int unused)
 10 {
 11   if (ACCESS_ONCE(theft) != THEFT_REQ)
 12     return;
 13   smp_mb();
 14   ACCESS_ONCE(theft) = THEFT_ACK;
 15   if (!counting) {
 16     ACCESS_ONCE(theft) = THEFT_READY;
 17   }
 18   smp_mb();
 19 }
 20 
 21 static void flush_local_count(void)
 22 {
 23   int t;
 24   thread_id_t tid;
 25 
 26   for_each_tid(t, tid)
 27     if (theftp[t] != NULL) {
 28       if (*countermaxp[t] == 0) {
 29         ACCESS_ONCE(*theftp[t]) = THEFT_READY;
 30         continue;
 31       }
 32       ACCESS_ONCE(*theftp[t]) = THEFT_REQ;
 33       pthread_kill(tid, SIGUSR1);
 34     }
 35   for_each_tid(t, tid) {
 36     if (theftp[t] == NULL)
 37       continue;
 38     while (ACCESS_ONCE(*theftp[t]) != THEFT_READY) {
 39       poll(NULL, 0, 1);
 40       if (ACCESS_ONCE(*theftp[t]) == THEFT_REQ)
 41         pthread_kill(tid, SIGUSR1);
 42     }
 43     globalcount += *counterp[t];
 44     *counterp[t] = 0;
 45     globalreserve -= *countermaxp[t];
 46     *countermaxp[t] = 0;
 47     ACCESS_ONCE(*theftp[t]) = THEFT_IDLE;
 48   }
 49 }
 50 
 51 static void balance_count(void)
 52 {
 53   countermax = globalcountmax -
 54     globalcount - globalreserve;
 55   countermax /= num_online_threads();
 56   if (countermax > MAX_COUNTERMAX)
 57     countermax = MAX_COUNTERMAX;
 58   globalreserve += countermax;
 59   counter = countermax / 2;
 60   if (counter > globalcount)
 61     counter = globalcount;
 62   globalcount -= counter;
 63 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlfigureA{figure2655}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 int add_count(unsigned long delta)
  2 {
  3   int fastpath = 0;
  4 
  5   counting = 1;
  6   barrier();
  7   if (countermax - counter >= delta &&
  8       ACCESS_ONCE(theft) <= THEFT_REQ) {
  9     counter += delta;
 10     fastpath = 1;
 11   }
 12   barrier();
 13   counting = 0;
 14   barrier();
 15   if (ACCESS_ONCE(theft) == THEFT_ACK) {
 16     smp_mb();
 17     ACCESS_ONCE(theft) = THEFT_READY;
 18   }
 19   if (fastpath)
 20     return 1;
 21   spin_lock(&gblcnt_mutex);
 22   globalize_count();
 23   if (globalcountmax - globalcount -
 24       globalreserve < delta) {
 25     flush_local_count();
 26     if (globalcountmax - globalcount -
 27         globalreserve < delta) {
 28       spin_unlock(&gblcnt_mutex);
 29       return 0;
 30     }
 31   }
 32   globalcount += delta;
 33   balance_count();
 34   spin_unlock(&gblcnt_mutex);
 35   return 1;
 36 }
 37 
 38 int sub_count(unsigned long delta)
 39 {
 40   int fastpath = 0;
 41 
 42   counting = 1;
 43   barrier();
 44   if (counter >= delta &&
 45       ACCESS_ONCE(theft) <= THEFT_REQ) {
 46     counter -= delta;
 47     fastpath = 1;
 48   }
 49   barrier();
 50   counting = 0;
 51   barrier();
 52   if (ACCESS_ONCE(theft) == THEFT_ACK) {
 53     smp_mb();
 54     ACCESS_ONCE(theft) = THEFT_READY;
 55   }
 56   if (fastpath)
 57     return 1;
 58   spin_lock(&gblcnt_mutex);
 59   globalize_count();
 60   if (globalcount < delta) {
 61     flush_local_count();
 62     if (globalcount < delta) {
 63       spin_unlock(&gblcnt_mutex);
 64       return 0;
 65     }
 66   }
 67   globalcount -= delta;
 68   balance_count();
 69   spin_unlock(&gblcnt_mutex);
 70   return 1;
 71 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlfigureA{figure2668}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 unsigned long read_count(void)
  2 {
  3   int t;
  4   unsigned long sum;
  5 
  6   spin_lock(&gblcnt_mutex);
  7   sum = globalcount;
  8   for_each_thread(t)
  9     if (counterp[t] != NULL)
 10       sum += *counterp[t];
 11   spin_unlock(&gblcnt_mutex);
 12   return sum;
 13 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlfigureA{figure2679}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 void count_init(void)
  2 {
  3   struct sigaction sa;
  4 
  5   sa.sa_handler = flush_local_count_sig;
  6   sigemptyset(&sa.sa_mask);
  7   sa.sa_flags = 0;
  8   if (sigaction(SIGUSR1, &sa, NULL) != 0) {
  9     perror("sigaction");
 10     exit(-1);
 11   }
 12 }
 13 
 14 void count_register_thread(void)
 15 {
 16   int idx = smp_thread_id();
 17 
 18   spin_lock(&gblcnt_mutex);
 19   counterp[idx] = 
 20   countermaxp[idx] = 
 21   theftp[idx] = 
 22   spin_unlock(&gblcnt_mutex);
 23 }
 24 
 25 void count_unregister_thread(int nthreadsexpected)
 26 {
 27   int idx = smp_thread_id();
 28 
 29   spin_lock(&gblcnt_mutex);
 30   globalize_count();
 31   counterp[idx] = NULL;
 32   countermaxp[idx] = NULL;
 33   theftp[idx] = NULL;
 34   spin_unlock(&gblcnt_mutex);
 35 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsection}
\stepcounter{section}
\stepcounter{section}
\stepcounter{chapter}
\stepcounter{section}
\stepcounter{subsection}
{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap23440}%
\includegraphics[scale=.7]{SMPdesign/DiningPhilosopher5}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap23444}%
\includegraphics[scale=.7]{SMPdesign/DiningPhilosopher5TB}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap23448}%
\includegraphics[scale=.7]{SMPdesign/DiningPhilosopher4part-b}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsection}
\stepcounter{subsubsection}
{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap3721}%
\resizebox{3in}{!}{\includegraphics{SMPdesign/lockdeq}}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsubsection}
{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap3731}%
\resizebox{3in}{!}{\includegraphics{SMPdesign/lockdeqpair}}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsubsection}
{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap3751}%
\resizebox{3in}{!}{\includegraphics{SMPdesign/lockdeqhash}}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap3759}%
\resizebox{3in}{!}{\includegraphics{SMPdesign/lockdeqhash1R}}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap3769}%
\resizebox{1.5in}{!}{\includegraphics{SMPdesign/lockdeqhashlots}}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlfigureA{figure3600}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 struct pdeq {
  2   spinlock_t llock;
  3   int lidx;
  4   spinlock_t rlock;
  5   int ridx;
  6   struct deq bkt[DEQ_N_BKTS];
  7 };\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlfigureA{figure3608}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 struct element *pdeq_dequeue_l(struct pdeq *d)
  2 {
  3   struct element *e;
  4   int i;
  5
  6   spin_lock(&d->llock);
  7   i = moveright(d->lidx);
  8   e = deq_dequeue_l(&d->bkt[i]);
  9   if (e != NULL)
 10     d->lidx = i;
 11   spin_unlock(&d->llock);
 12   return e;
 13 }
 14
 15 void pdeq_enqueue_l(struct element *e, struct pdeq *d)
 16 {
 17   int i;
 18
 19   spin_lock(&d->llock);
 20   i = d->lidx;
 21   deq_enqueue_l(e, &d->bkt[i]);
 22   d->lidx = moveleft(d->lidx);
 23   spin_unlock(&d->llock);
 24 }
 25
 26 struct element *pdeq_dequeue_r(struct pdeq *d)
 27 {
 28   struct element *e;
 29   int i;
 30
 31   spin_lock(&d->rlock);
 32   i = moveleft(d->ridx);
 33   e = deq_dequeue_r(&d->bkt[i]);
 34   if (e != NULL)
 35     d->ridx = i;
 36   spin_unlock(&d->rlock);
 37   return e;
 38 }
 39
 40 void pdeq_enqueue_r(struct element *e, struct pdeq *d)
 41 {
 42   int i;
 43
 44   spin_lock(&d->rlock);
 45   i = d->ridx;
 46   deq_enqueue_r(e, &d->bkt[i]);
 47   d->ridx = moveright(d->lidx);
 48   spin_unlock(&d->rlock);
 49 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsubsection}
{\newpage\clearpage
\lthtmlfigureA{figure3628}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 struct list_head *pdeq_dequeue_l(struct pdeq *d)
  2 {
  3   struct list_head *e;
  4   int i;
  5
  6   spin_lock(&d->llock);
  7   e = deq_dequeue_l(&d->ldeq);
  8   if (e == NULL) {
  9     spin_lock(&d->rlock);
 10     e = deq_dequeue_l(&d->rdeq);
 11     list_splice_init(&d->rdeq.chain, &d->ldeq.chain);
 12     spin_unlock(&d->rlock);
 13   }
 14   spin_unlock(&d->llock);
 15   return e;
 16 }
 17
 18 struct list_head *pdeq_dequeue_r(struct pdeq *d)
 19 {
 20   struct list_head *e;
 21   int i;
 22
 23   spin_lock(&d->rlock);
 24   e = deq_dequeue_r(&d->rdeq);
 25   if (e == NULL) {
 26     spin_unlock(&d->rlock);
 27     spin_lock(&d->llock);
 28     spin_lock(&d->rlock);
 29     e = deq_dequeue_r(&d->rdeq);
 30     if (e == NULL) {
 31       e = deq_dequeue_r(&d->ldeq);
 32       list_splice_init(&d->ldeq.chain, &d->rdeq.chain);
 33     }
 34     spin_unlock(&d->llock);
 35   }
 36   spin_unlock(&d->rlock);
 37   return e;
 38 }
 39
 40 void pdeq_enqueue_l(struct list_head *e, struct pdeq *d)
 41 {
 42   int i;
 43
 44   spin_lock(&d->llock);
 45   deq_enqueue_l(e, &d->ldeq);
 46   spin_unlock(&d->llock);
 47 }
 48
 49 void pdeq_enqueue_r(struct list_head *e, struct pdeq *d)
 50 {
 51   int i;
 52
 53   spin_lock(&d->rlock);
 54   deq_enqueue_r(e, &d->rdeq);
 55   spin_unlock(&d->rlock);
 56 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsubsection}
\stepcounter{subsection}
\stepcounter{section}
\stepcounter{section}
{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap23501}%
\includegraphics{SMPdesign/LockGranularity}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsection}
{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap4295}%
\resizebox{3in}{!}{\includegraphics{SMPdesign/CPUvsEnet}}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlfigureA{figure3911}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 struct hash_table
  2 {
  3   long nbuckets;
  4   struct node **buckets;
  5 };
  6
  7 typedef struct node {
  8   unsigned long key;
  9   struct node *next;
 10 } node_t;
 11
 12 int hash_search(struct hash_table *h, long key)
 13 {
 14   struct node *cur;
 15
 16   cur = h->buckets[key % h->nbuckets];
 17   while (cur != NULL) {
 18     if (cur->key >= key) {
 19       return (cur->key == key);
 20     }
 21     cur = cur->next;
 22   }
 23   return 0;
 24 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsection}
{\newpage\clearpage
\lthtmlfigureA{figure3923}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 spinlock_t hash_lock;
  2
  3 struct hash_table
  4 {
  5   long nbuckets;
  6   struct node **buckets;
  7 };
  8
  9 typedef struct node {
 10   unsigned long key;
 11   struct node *next;
 12 } node_t;
 13
 14 int hash_search(struct hash_table *h, long key)
 15 {
 16   struct node *cur;
 17   int retval;
 18
 19   spin_lock(&hash_lock);
 20   cur = h->buckets[key % h->nbuckets];
 21   while (cur != NULL) {
 22     if (cur->key >= key) {
 23       retval = (cur->key == key);
 24       spin_unlock(&hash_lock);
 25       return retval;
 26     }
 27     cur = cur->next;
 28   }
 29   spin_unlock(&hash_lock);
 30   return 0;
 31 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap4331}%
\resizebox{3in}{!}{\includegraphics{cartoons/OneFighting}}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsection}
{\newpage\clearpage
\lthtmlfigureA{figure3942}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 struct hash_table
  2 {
  3   long nbuckets;
  4   struct bucket **buckets;
  5 };
  6
  7 struct bucket {
  8   spinlock_t bucket_lock;
  9   node_t *list_head;
 10 };
 11
 12 typedef struct node {
 13   unsigned long key;
 14   struct node *next;
 15 } node_t;
 16
 17 int hash_search(struct hash_table *h, long key)
 18 {
 19   struct bucket *bp;
 20   struct node *cur;
 21   int retval;
 22
 23   bp = h->buckets[key % h->nbuckets];
 24   spin_lock(&bp->bucket_lock);
 25   cur = bp->list_head;
 26   while (cur != NULL) {
 27     if (cur->key >= key) {
 28       retval = (cur->key == key);
 29       spin_unlock(&bp->hash_lock);
 30       return retval;
 31     }
 32     cur = cur->next;
 33   }
 34   spin_unlock(&bp->hash_lock);
 35   return 0;
 36 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap4349}%
\resizebox{3in}{!}{\includegraphics{cartoons/ManyHappy}}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap4357}%
\resizebox{3in}{!}{\includegraphics{cartoons/ManyFighting}}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsection}
\stepcounter{subsection}
{\newpage\clearpage
\lthtmlinlinemathA{tex2html_wrap_inline4213}%
$\lambda$%
\lthtmlinlinemathZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlinlinemathA{tex2html_wrap_inline4215}%
$\mu$%
\lthtmlinlinemathZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmldisplayA{displaymath3985}%
\begin{displaymath}
	\lambda = n \lambda_0
\end{displaymath}%
\lthtmldisplayZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlinlinemathA{tex2html_wrap_inline4231}%
$n$%
\lthtmlinlinemathZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlinlinemathA{tex2html_wrap_inline4233}%
$\lambda_0$%
\lthtmlinlinemathZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlinlinemathA{tex2html_wrap_inline4235}%
$1 / \lambda_0$%
\lthtmlinlinemathZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmldisplayA{displaymath3987}%
\begin{displaymath}
	T = \frac{1}{\mu - \lambda}
\end{displaymath}%
\lthtmldisplayZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmldisplayA{displaymath3991}%
\begin{displaymath}
	T = \frac{1}{\mu - n \lambda_0}
\end{displaymath}%
\lthtmldisplayZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmldisplayA{displaymath3995}%
\begin{displaymath}
	e = \frac{1 / \lambda_0}{T + 1 / \lambda_0}
\end{displaymath}%
\lthtmldisplayZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlinlinemathA{tex2html_wrap_inline4239}%
$T$%
\lthtmlinlinemathZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmldisplayA{displaymath3999}%
\begin{displaymath}
	e = \frac{\frac{\mu}{\lambda_0} - n}{\frac{\mu}{\lambda_0} - (n - 1)}
\end{displaymath}%
\lthtmldisplayZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlinlinemathA{tex2html_wrap_inline4241}%
$\mu / \lambda_0$%
\lthtmlinlinemathZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlinlinemathA{tex2html_wrap_inline4243}%
$f$%
\lthtmlinlinemathZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmldisplayA{displaymath4005}%
\begin{displaymath}
	e = \frac{f - n}{f - (n - 1)}
\end{displaymath}%
\lthtmldisplayZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap4419}%
\resizebox{3in}{!}{\includegraphics{SMPdesign/synceff}}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlinlinemathA{tex2html_wrap_inline4245}%
$e$%
\lthtmlinlinemathZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlinlinemathA{tex2html_wrap_inline4251}%
$f=10$%
\lthtmlinlinemathZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlinlinemathA{tex2html_wrap_inline4253}%
$f=100$%
\lthtmlinlinemathZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap4429}%
\resizebox{3in}{!}{\includegraphics{SMPdesign/matmuleff}}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{section}
{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap23583}%
\includegraphics{SMPdesign/ParallelFastpath}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsection}
{\newpage\clearpage
\lthtmlfigureA{figure4061}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 rwlock_t hash_lock;
  2
  3 struct hash_table
  4 {
  5   long nbuckets;
  6   struct node **buckets;
  7 };
  8
  9 typedef struct node {
 10   unsigned long key;
 11   struct node *next;
 12 } node_t;
 13
 14 int hash_search(struct hash_table *h, long key)
 15 {
 16   struct node *cur;
 17   int retval;
 18
 19   read_lock(&hash_lock);
 20   cur = h->buckets[key % h->nbuckets];
 21   while (cur != NULL) {
 22     if (cur->key >= key) {
 23       retval = (cur->key == key);
 24       read_unlock(&hash_lock);
 25       return retval;
 26     }
 27     cur = cur->next;
 28   }
 29   read_unlock(&hash_lock);
 30   return 0;
 31 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsection}
{\newpage\clearpage
\lthtmlfigureA{figure4072}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 struct hash_table
  2 {
  3   long nbuckets;
  4   struct bucket **buckets;
  5 };
  6
  7 struct bucket {
  8   spinlock_t bucket_lock;
  9   node_t *list_head;
 10 };
 11
 12 typedef struct node {
 13   spinlock_t node_lock;
 14   unsigned long key;
 15   struct node *next;
 16 } node_t;
 17
 18 int hash_search(struct hash_table *h, long key)
 19 {
 20   struct bucket *bp;
 21   struct node *cur;
 22   int retval;
 23
 24   bp = h->buckets[key % h->nbuckets];
 25   spin_lock(&bp->bucket_lock);
 26   cur = bp->list_head;
 27   while (cur != NULL) {
 28     if (cur->key >= key) {
 29       spin_lock(&cur->node_lock);
 30       spin_unlock(&bp->bucket_lock);
 31       retval = (cur->key == key);
 32       spin_unlock(&cur->node_lock);
 33       return retval;
 34     }
 35     cur = cur->next;
 36   }
 37   spin_unlock(&bp->bucket_lock);
 38   return 0;
 39 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsection}
\stepcounter{subsubsection}
\stepcounter{subsubsection}
{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap4503}%
\resizebox{3in}{!}{\includegraphics{SMPdesign/allocatorcache}}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsubsection}
{\newpage\clearpage
\lthtmlfigureA{figure4113}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 #define TARGET_POOL_SIZE 3
  2 #define GLOBAL_POOL_SIZE 40
  3
  4 struct globalmempool {
  5   spinlock_t mutex;
  6   int cur;
  7   struct memblock *pool[GLOBAL_POOL_SIZE];
  8 } globalmem;
  9
 10 struct percpumempool {
 11   int cur;
 12   struct memblock *pool[2 * TARGET_POOL_SIZE];
 13 };
 14
 15 DEFINE_PER_THREAD(struct percpumempool, percpumem);\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap4523}%
\resizebox{3in}{!}{\includegraphics{SMPdesign/AllocatorPool}}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsubsection}
{\newpage\clearpage
\lthtmlfigureA{figure4138}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 struct memblock *memblock_alloc(void)
  2 {
  3   int i;
  4   struct memblock *p;
  5   struct percpumempool *pcpp;
  6
  7   pcpp = &__get_thread_var(percpumem);
  8   if (pcpp->cur < 0) {
  9     spin_lock(&globalmem.mutex);
 10     for (i = 0; i < TARGET_POOL_SIZE &&
 11                 globalmem.cur >= 0; i++) {
 12       pcpp->pool[i] = globalmem.pool[globalmem.cur];
 13       globalmem.pool[globalmem.cur--] = NULL;
 14     }
 15     pcpp->cur = i - 1;
 16     spin_unlock(&globalmem.mutex);
 17   }
 18   if (pcpp->cur >= 0) {
 19     p = pcpp->pool[pcpp->cur];
 20     pcpp->pool[pcpp->cur--] = NULL;
 21     return p;
 22   }
 23   return NULL;
 24 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsubsection}
{\newpage\clearpage
\lthtmlfigureA{figure4146}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 void memblock_free(struct memblock *p)
  2 {
  3   int i;
  4   struct percpumempool *pcpp;
  5
  6   pcpp = &__get_thread_var(percpumem);
  7   if (pcpp->cur >= 2 * TARGET_POOL_SIZE - 1) {
  8     spin_lock(&globalmem.mutex);
  9     for (i = pcpp->cur; i >= TARGET_POOL_SIZE; i--) {
 10       globalmem.pool[++globalmem.cur] = pcpp->pool[i];
 11       pcpp->pool[i] = NULL;
 12     }
 13     pcpp->cur = i;
 14     spin_unlock(&globalmem.mutex);
 15   }
 16   pcpp->pool[++pcpp->cur] = p;
 17 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsubsection}
{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap4563}%
\resizebox{3in}{!}{\includegraphics{SMPdesign/smpalloc}}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsubsection}
\stepcounter{section}
\stepcounter{chapter}
{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap4728}%
\resizebox{3in}{!}{\includegraphics{locking/LockingTheSlob}}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap4734}%
\resizebox{3in}{!}{\includegraphics{locking/LockingTheHero}}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{section}
\stepcounter{subsection}
{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap4750}%
\resizebox{3in}{!}{\includegraphics{locking/DeadlockCycle}}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlfigureA{figure4646}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 spin_lock(&lock2);
  2 layer_2_processing(pkt);
  3 nextlayer = layer_1(pkt);
  4 spin_lock(&nextlayer->lock1);
  5 layer_1_processing(pkt);
  6 spin_unlock(&lock2);
  7 spin_unlock(&nextlayer->lock1);\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlfigureA{figure4653}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 retry:
  2   spin_lock(&lock2);
  3   layer_2_processing(pkt);
  4   nextlayer = layer_1(pkt);
  5   if (!spin_trylock(&nextlayer->lock1)) {
  6     spin_unlock(&lock2);
  7     spin_lock(&nextlayer->lock1);
  8     spin_lock((&lock2);
  9     if (layer_1(pkt) != nextlayer) {
 10       spin_unlock(&nextlayer->lock1);
 11       spin_unlock((&lock2);
 12       goto retry;
 13     }
 14   }
 15   layer_1_processing(pkt);
 16 spin_unlock(&lock2);
 17 spin_unlock(&nextlayer->lock1);\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsection}
{\newpage\clearpage
\lthtmlfigureA{figure4675}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 void thread1(void)
  2 {
  3 retry:
  4   spin_lock(&lock1);
  5   do_one_thing();
  6   if (!spin_trylock(&lock2)) {
  7     spin_unlock(&lock1);
  8     goto retry;
  9   }
 10   do_another_thing();
 11   spin_unlock(&lock2);
 12   spin_unlock(&lock1);
 13 }
 14 
 15 void thread2(void)
 16 {
 17 retry:
 18   spin_lock(&lock2);
 19   do_a_third_thing();
 20   if (!spin_trylock(&lock1)) {
 21     spin_unlock(&lock2);
 22     goto retry;
 23   }
 24   do_a_fourth_thing();
 25   spin_unlock(&lock1);
 26   spin_unlock(&lock2);
 27 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsection}
\stepcounter{subsection}
\stepcounter{section}
\stepcounter{subsection}
\stepcounter{subsection}
\stepcounter{subsection}
\stepcounter{section}
{\newpage\clearpage
\lthtmlfigureA{figure4838}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 int delete(int key)
  2 {
  3   int b;
  4   struct element *p;
  5
  6   b = hashfunction(key);
  7   p = hashtable[b];
  8   if (p == NULL || p->key != key)
  9     return 0;
 10   spin_lock(&p->lock);
 11   hashtable[b] = NULL;
 12   spin_unlock(&p->lock);
 13   kfree(p);
 14   return 1;
 15 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlfigureA{figure4853}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 int delete(int key)
  2 {
  3   int b;
  4   struct element *p;
  5   spinlock_t *sp;
  6
  7   b = hashfunction(key);
  8   sp = &locktable[b];
  9   spin_lock(sp);
 10   p = hashtable[b];
 11   if (p == NULL || p->key != key) {
 12     spin_unlock(sp);
 13     return 0;
 14   }
 15   hashtable[b] = NULL;
 16   spin_unlock(sp);
 17   kfree(p);
 18   return 1;
 19 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{chapter}
\stepcounter{chapter}
\stepcounter{section}
\stepcounter{section}
\stepcounter{subsection}
\stepcounter{subsubsection}
{\newpage\clearpage
\lthtmlfigureA{figure4953}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 struct sref {
  2   int refcount;
  3 };
  4
  5 void sref_init(struct sref *sref)
  6 {
  7   sref->refcount = 1;
  8 }
  9
 10 void sref_get(struct sref *sref)
 11 {
 12   sref->refcount++;
 13 }
 14
 15 int sref_put(struct sref *sref,
 16              void (*release)(struct sref *sref))
 17 {
 18   WARN_ON(release == NULL);
 19   WARN_ON(release == (void (*)(struct sref *))kfree);
 20
 21   if (--sref->refcount == 0) {
 22     release(sref);
 23     return 1;
 24   }
 25   return 0;
 26 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsubsection}
{\newpage\clearpage
\lthtmlfigureA{figure4966}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 struct kref {
  2   atomic_t refcount;
  3 };
  4
  5 void kref_init(struct kref *kref)
  6 {
  7   atomic_set(&kref->refcount,1);
  8 }
  9
 10 void kref_get(struct kref *kref)
 11 {
 12   WARN_ON(!atomic_read(&kref->refcount));
 13   atomic_inc(&kref->refcount);
 14 }
 15
 16 int kref_put(struct kref *kref,
 17              void (*release)(struct kref *kref))
 18 {
 19   WARN_ON(release == NULL);
 20   WARN_ON(release == (void (*)(struct kref *))kfree);
 21
 22   if ((atomic_read(&kref->refcount) == 1) ||
 23       (atomic_dec_and_test(&kref->refcount))) {
 24     release(kref);
 25     return 1;
 26   }
 27   return 0;
 28 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsubsection}
{\newpage\clearpage
\lthtmlfigureA{figure4996}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 static inline
  2 struct dst_entry * dst_clone(struct dst_entry * dst)
  3 {
  4   if (dst)
  5     atomic_inc(&dst->__refcnt);
  6   return dst;
  7 }
  8
  9 static inline
 10 void dst_release(struct dst_entry * dst)
 11 {
 12   if (dst) {
 13     WARN_ON(atomic_read(&dst->__refcnt) < 1);
 14     smp_mb__before_atomic_dec();
 15     atomic_dec(&dst->__refcnt);
 16   }
 17 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsubsection}
{\newpage\clearpage
\lthtmlfigureA{figure5020}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 struct file *fget(unsigned int fd)
  2 {
  3   struct file *file;
  4   struct files_struct *files = current->files;
  5
  6   rcu_read_lock();
  7   file = fcheck_files(files, fd);
  8   if (file) {
  9     if (!atomic_inc_not_zero(&file->f_count)) {
 10       rcu_read_unlock();
 11       return NULL;
 12     }
 13   }
 14   rcu_read_unlock();
 15   return file;
 16 }
 17
 18 struct file *
 19 fcheck_files(struct files_struct *files, unsigned int fd)
 20 {
 21   struct file * file = NULL;
 22   struct fdtable *fdt = rcu_dereference((files)->fdt);
 23
 24   if (fd < fdt->max_fds)
 25     file = rcu_dereference(fdt->fd[fd]);
 26   return file;
 27 }
 28
 29 void fput(struct file *file)
 30 {
 31   if (atomic_dec_and_test(&file->f_count))
 32     call_rcu(&file->f_u.fu_rcuhead, file_free_rcu);
 33 }
 34
 35 static void file_free_rcu(struct rcu_head *head)
 36 {
 37   struct file *f;
 38
 39   f = container_of(head, struct file, f_u.fu_rcuhead);
 40   kmem_cache_free(filp_cachep, f);
 41 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsection}
\stepcounter{subsection}
\stepcounter{section}
\stepcounter{subsection}
\stepcounter{subsubsection}
{\newpage\clearpage
\lthtmlfigureA{figure5249}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 struct foo {
  2   int a;
  3   int b;
  4   int c;
  5 };
  6 struct foo *gp = NULL;
  7
  8 /* . . . */
  9
 10 p = kmalloc(sizeof(*p), GFP_KERNEL);
 11 p->a = 1;
 12 p->b = 2;
 13 p->c = 3;
 14 gp = p;\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap5623}%
\resizebox{3in}{!}{\includegraphics{defer/Linux_list}}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap5629}%
\resizebox{3in}{!}{\includegraphics{defer/Linux_list_abbr}}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlfigureA{figure5333}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 struct foo {
  2   struct list_head *list;
  3   int a;
  4   int b;
  5   int c;
  6 };
  7 LIST_HEAD(head);
  8
  9 /* . . . */
 10
 11 p = kmalloc(sizeof(*p), GFP_KERNEL);
 12 p->a = 1;
 13 p->b = 2;
 14 p->c = 3;
 15 list_add_rcu(&p->list, &head);\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap5669}%
\resizebox{3in}{!}{\includegraphics{defer/Linux_hlist}}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlfigureA{figure5366}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 struct foo {
  2   struct hlist_node *list;
  3   int a;
  4   int b;
  5   int c;
  6 };
  7 HLIST_HEAD(head);
  8
  9 /* . . . */
 10
 11 p = kmalloc(sizeof(*p), GFP_KERNEL);
 12 p->a = 1;
 13 p->b = 2;
 14 p->c = 3;
 15 hlist_add_head_rcu(&p->list, &head);\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsubsection}
{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap5725}%
\resizebox{3in}{!}{\includegraphics{defer/GracePeriodGood}}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlfigureA{figure5435}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 struct foo {
  2   struct list_head *list;
  3   int a;
  4   int b;
  5   int c;
  6 };
  7 LIST_HEAD(head);
  8
  9 /* . . . */
 10
 11 p = search(head, key);
 12 if (p == NULL) {
 13   /* Take appropriate action, unlock, and return. */
 14 }
 15 q = kmalloc(sizeof(*p), GFP_KERNEL);
 16 *q = *p;
 17 q->b = 2;
 18 q->c = 3;
 19 list_replace_rcu(&p->list, &q->list);
 20 synchronize_rcu();
 21 kfree(p);\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsubsection}
\stepcounter{paragraph}
{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap5771}%
\resizebox{3in}{!}{\includegraphics{defer/RCUDeletion}}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{paragraph}
{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap5791}%
\resizebox{2.7in}{!}{\includegraphics{defer/RCUReplacement}}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{paragraph}
\stepcounter{subsubsection}
\stepcounter{subsection}
\stepcounter{subsubsection}
\stepcounter{paragraph}
{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap6134}%
\resizebox{3in}{!}{\includegraphics{defer/rwlockRCUperf}}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap6148}%
\resizebox{3in}{!}{\includegraphics{defer/rwlockRCUperfPREEMPT}}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap6156}%
\resizebox{3in}{!}{\includegraphics{defer/rwlockRCUperfwtPREEMPT}}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{paragraph}
\stepcounter{paragraph}
\stepcounter{paragraph}
{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap6200}%
\resizebox{3in}{!}{\includegraphics{defer/rwlockRCUupdate}}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{paragraph}
\stepcounter{paragraph}
\stepcounter{paragraph}
{\newpage\clearpage
\lthtmlfigureA{figurestar5961}%
\begin{figure*}{ \scriptsize\centering
\begin{verbatim}

 1 struct el {                           1 struct el {
 2   struct list_head lp;                2   struct list_head lp;
 3   long key;                           3   long key;
 4   spinlock_t mutex;                   4   spinlock_t mutex;
 5   int data;                           5   int data;
 6   /* Other data fields */             6   /* Other data fields */
 7 };                                    7 };
 8 DEFINE_RWLOCK(listmutex);             8 DEFINE_SPINLOCK(listmutex);
 9 LIST_HEAD(head);                      9 LIST_HEAD(head);\end{verbatim}

}

\end{figure*}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlfigureA{figurestar5967}%
\begin{figure*}{ \scriptsize\centering
\begin{verbatim}

 1 int search(long key, int *result)     1 int search(long key, int *result)
 2 {                                     2 {
 3   struct el *p;                       3   struct el *p;
 4                                       4
 5   read_lock(&listmutex);              5   rcu_read_lock();
 6   list_for_each_entry(p, &head, lp) { 6   list_for_each_entry_rcu(p, &head, lp) {
 7     if (p->key == key) {              7     if (p->key == key) {
 8       *result = p->data;              8       *result = p->data;
 9       read_unlock(&listmutex);        9       rcu_read_unlock();
10       return 1;                      10       return 1;
11     }                                11     }
12   }                                  12   }
13   read_unlock(&listmutex);           13   rcu_read_unlock();
14   return 0;                          14   return 0;
15 }                                    15 }\end{verbatim}

}

\end{figure*}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlfigureA{figurestar5973}%
\begin{figure*}{ \scriptsize\centering
\begin{verbatim}

 1 int delete(long key)                  1 int delete(long key)
 2 {                                     2 {
 3   struct el *p;                       3   struct el *p;
 4                                       4
 5   write_lock(&listmutex);             5   spin_lock(&listmutex);
 6   list_for_each_entry(p, &head, lp) { 6   list_for_each_entry(p, &head, lp) {
 7     if (p->key == key) {              7     if (p->key == key) {
 8       list_del(&p->lp);               8       list_del_rcu(&p->lp);
 9       write_unlock(&listmutex);       9       spin_unlock(&listmutex);
                                        10       synchronize_rcu();
10       kfree(p);                      11       kfree(p);
11       return 1;                      12       return 1;
12     }                                13     }
13   }                                  14   }
14   write_unlock(&listmutex);          15   spin_unlock(&listmutex);
15   return 0;                          16   return 0;
16 }                                    17 }\end{verbatim}

}

\end{figure*}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsubsection}
{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap6278}%
\resizebox{3in}{!}{\includegraphics{defer/refRCUperfPREEMPT}}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap6290}%
\resizebox{3in}{!}{\includegraphics{defer/refRCUperfwtPREEMPT}}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsubsection}
\stepcounter{subsubsection}
\stepcounter{subsubsection}
{\newpage\clearpage
\lthtmlfigureA{figure6041}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 int delete(int key)
  2 {
  3   struct element *p;
  4   int b;
  5   5
  6   b = hashfunction(key);
  7   rcu_read_lock();
  8   p = rcu_dereference(hashtable[b]);
  9   if (p == NULL || p->key != key) {
 10     rcu_read_unlock();
 11     return 0;
 12   }
 13   spin_lock(&p->lock);
 14   if (hashtable[b] == p && p->key == key) {
 15     rcu_read_unlock();
 16     hashtable[b] = NULL;
 17     spin_unlock(&p->lock);
 18     synchronize_rcu();
 19     kfree(p);
 20     return 1;
 21   }
 22   spin_unlock(&p->lock);
 23   rcu_read_unlock();
 24   return 0;
 25 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsubsection}
\stepcounter{subsubsection}
{\newpage\clearpage
\lthtmlfigureA{figure6078}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 struct profile_buffer {
  2   long size;
  3   atomic_t entry[0];
  4 };
  5 static struct profile_buffer *buf = NULL;
  6
  7 void nmi_profile(unsigned long pcvalue)
  8 {
  9   struct profile_buffer *p = rcu_dereference(buf);
 10
 11   if (p == NULL)
 12     return;
 13   if (pcvalue >= p->size)
 14     return;
 15   atomic_inc(&p->entry[pcvalue]);
 16 }
 17
 18 void nmi_stop(void)
 19 {
 20   struct profile_buffer *p = buf;
 21
 22   if (p == NULL)
 23     return;
 24   rcu_assign_pointer(buf, NULL);
 25   synchronize_sched();
 26   kfree(p);
 27 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsubsection}
\stepcounter{subsection}
\stepcounter{subsubsection}
\stepcounter{subsubsection}
\stepcounter{subsubsection}
{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap6783}%
\resizebox{3in}{!}{\includegraphics{defer/RCUenvAPI}}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsubsection}
\stepcounter{subsection}
\stepcounter{subsubsection}
{\newpage\clearpage
\lthtmlfigureA{figure6812}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 static void rcu_read_lock(void)
  2 {
  3   spin_lock(&rcu_gp_lock);
  4 }
  5
  6 static void rcu_read_unlock(void)
  7 {
  8   spin_unlock(&rcu_gp_lock);
  9 }
 10
 11 void synchronize_rcu(void)
 12 {
 13   spin_lock(&rcu_gp_lock);
 14   spin_unlock(&rcu_gp_lock);
 15 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsubsection}
{\newpage\clearpage
\lthtmlfigureA{figure6837}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 static void rcu_read_lock(void)
  2 {
  3   spin_lock(&__get_thread_var(rcu_gp_lock));
  4 }
  5
  6 static void rcu_read_unlock(void)
  7 {
  8   spin_unlock(&__get_thread_var(rcu_gp_lock));
  9 }
 10
 11 void synchronize_rcu(void)
 12 {
 13   int t;
 14
 15   for_each_running_thread(t) {
 16     spin_lock(&per_thread(rcu_gp_lock, t));
 17     spin_unlock(&per_thread(rcu_gp_lock, t));
 18   }
 19 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsubsection}
{\newpage\clearpage
\lthtmlfigureA{figure6864}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 atomic_t rcu_refcnt;
  2
  3 static void rcu_read_lock(void)
  4 {
  5   atomic_inc(&rcu_refcnt);
  6   smp_mb();
  7 }
  8
  9 static void rcu_read_unlock(void)
 10 {
 11   smp_mb();
 12   atomic_dec(&rcu_refcnt);
 13 }
 14
 15 void synchronize_rcu(void)
 16 {
 17   smp_mb();
 18   while (atomic_read(&rcu_refcnt) != 0) {
 19     poll(NULL, 0, 10);
 20   }
 21   smp_mb();
 22 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsubsection}
{\newpage\clearpage
\lthtmlfigureA{figure6904}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 DEFINE_SPINLOCK(rcu_gp_lock);
  2 atomic_t rcu_refcnt[2];
  3 atomic_t rcu_idx;
  4 DEFINE_PER_THREAD(int, rcu_nesting);
  5 DEFINE_PER_THREAD(int, rcu_read_idx);\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlfigureA{figure6910}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 static void rcu_read_lock(void)
  2 {
  3   int i;
  4   int n;
  5
  6   n = __get_thread_var(rcu_nesting);
  7   if (n == 0) {
  8     i = atomic_read(&rcu_idx);
  9     __get_thread_var(rcu_read_idx) = i;
 10     atomic_inc(&rcu_refcnt[i]);
 11   }
 12   __get_thread_var(rcu_nesting) = n + 1;
 13   smp_mb();
 14 }
 15
 16 static void rcu_read_unlock(void)
 17 {
 18   int i;
 19   int n;
 20
 21   smp_mb();
 22   n = __get_thread_var(rcu_nesting);
 23   if (n == 1) {
 24      i = __get_thread_var(rcu_read_idx);
 25     atomic_dec(&rcu_refcnt[i]);
 26   }
 27   __get_thread_var(rcu_nesting) = n - 1;
 28 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlfigureA{figure6949}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 void synchronize_rcu(void)
  2 {
  3   int i;
  4
  5   smp_mb();
  6   spin_lock(&rcu_gp_lock);
  7   i = atomic_read(&rcu_idx);
  8   atomic_set(&rcu_idx, !i);
  9   smp_mb();
 10   while (atomic_read(&rcu_refcnt[i]) != 0) {
 11     poll(NULL, 0, 10);
 12   }
 13   smp_mb();
 14   atomic_set(&rcu_idx, i);
 15   smp_mb();
 16   while (atomic_read(&rcu_refcnt[!i]) != 0) {
 17     poll(NULL, 0, 10);
 18   }
 19   spin_unlock(&rcu_gp_lock);
 20   smp_mb();
 21 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsubsection}
{\newpage\clearpage
\lthtmlfigureA{figure6990}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 DEFINE_SPINLOCK(rcu_gp_lock);
  2 DEFINE_PER_THREAD(int [2], rcu_refcnt);
  3 atomic_t rcu_idx;
  4 DEFINE_PER_THREAD(int, rcu_nesting);
  5 DEFINE_PER_THREAD(int, rcu_read_idx);\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlfigureA{figure6996}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 static void rcu_read_lock(void)
  2 {
  3   int i;
  4   int n;
  5
  6   n = __get_thread_var(rcu_nesting);
  7   if (n == 0) {
  8     i = atomic_read(&rcu_idx);
  9     __get_thread_var(rcu_read_idx) = i;
 10     __get_thread_var(rcu_refcnt)[i]++;
 11   }
 12   __get_thread_var(rcu_nesting) = n + 1;
 13   smp_mb();
 14 }
 15
 16 static void rcu_read_unlock(void)
 17 {
 18   int i;
 19   int n;
 20
 21   smp_mb();
 22   n = __get_thread_var(rcu_nesting);
 23   if (n == 1) {
 24      i = __get_thread_var(rcu_read_idx);
 25     __get_thread_var(rcu_refcnt)[i]--;
 26   }
 27   __get_thread_var(rcu_nesting) = n - 1;
 28 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlfigureA{figure7014}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 static void flip_counter_and_wait(int i)
  2 {
  3   int t;
  4
  5   atomic_set(&rcu_idx, !i);
  6   smp_mb();
  7   for_each_thread(t) {
  8     while (per_thread(rcu_refcnt, t)[i] != 0) {
  9       poll(NULL, 0, 10);
 10     }
 11   }
 12   smp_mb();
 13 }
 14
 15 void synchronize_rcu(void)
 16 {
 17   int i;
 18
 19   smp_mb();
 20   spin_lock(&rcu_gp_lock);
 21   i = atomic_read(&rcu_idx);
 22   flip_counter_and_wait(i);
 23   flip_counter_and_wait(!i);
 24   spin_unlock(&rcu_gp_lock);
 25   smp_mb();
 26 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlinlinemathA{tex2html_wrap_inline7334}%
$2N$%
\lthtmlinlinemathZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsubsection}
{\newpage\clearpage
\lthtmlfigureA{figure7039}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 DEFINE_SPINLOCK(rcu_gp_lock);
  2 DEFINE_PER_THREAD(int [2], rcu_refcnt);
  3 long rcu_idx;
  4 DEFINE_PER_THREAD(int, rcu_nesting);
  5 DEFINE_PER_THREAD(int, rcu_read_idx);\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlfigureA{figure7045}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 static void rcu_read_lock(void)
  2 {
  3   int i;
  4   int n;
  5
  6   n = __get_thread_var(rcu_nesting);
  7   if (n == 0) {
  8     i = ACCESS_ONCE(rcu_idx) & 0x1;
  9     __get_thread_var(rcu_read_idx) = i;
 10     __get_thread_var(rcu_refcnt)[i]++;
 11   }
 12   __get_thread_var(rcu_nesting) = n + 1;
 13   smp_mb();
 14 }
 15
 16 static void rcu_read_unlock(void)
 17 {
 18   int i;
 19   int n;
 20
 21   smp_mb();
 22   n = __get_thread_var(rcu_nesting);
 23   if (n == 1) {
 24      i = __get_thread_var(rcu_read_idx);
 25     __get_thread_var(rcu_refcnt)[i]--;
 26   }
 27   __get_thread_var(rcu_nesting) = n - 1;
 28 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlfigureA{figure7064}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 static void flip_counter_and_wait(int ctr)
  2 {
  3   int i;
  4   int t;
  5
  6   ACCESS_ONCE(rcu_idx) = ctr + 1;
  7   i = ctr & 0x1;
  8   smp_mb();
  9   for_each_thread(t) {
 10     while (per_thread(rcu_refcnt, t)[i] != 0) {
 11       poll(NULL, 0, 10);
 12     }
 13   }
 14   smp_mb();
 15 }
 16
 17 void synchronize_rcu(void)
 18 {
 19   int ctr;
 20   int oldctr;
 21
 22   smp_mb();
 23   oldctr = ACCESS_ONCE(rcu_idx);
 24   smp_mb();
 25   spin_lock(&rcu_gp_lock);
 26   ctr = ACCESS_ONCE(rcu_idx);
 27   if (ctr - oldctr >= 3) {
 28     spin_unlock(&rcu_gp_lock);
 29     smp_mb();
 30     return;
 31   }
 32   flip_counter_and_wait(ctr);
 33   if (ctr - oldctr < 2)
 34     flip_counter_and_wait(ctr + 1);
 35   spin_unlock(&rcu_gp_lock);
 36   smp_mb();
 37 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlinlinemathA{tex2html_wrap_inline7336}%
$O\left(1\right)$%
\lthtmlinlinemathZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsubsection}
{\newpage\clearpage
\lthtmlfigureA{figure7106}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 DEFINE_SPINLOCK(rcu_gp_lock);
  2 long rcu_gp_ctr = 0;
  3 DEFINE_PER_THREAD(long, rcu_reader_gp);
  4 DEFINE_PER_THREAD(long, rcu_reader_gp_snap);\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlfigureA{figure7112}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 static void rcu_read_lock(void)
  2 {
  3   __get_thread_var(rcu_reader_gp) = rcu_gp_ctr + 1;
  4   smp_mb();
  5 }
  6
  7 static void rcu_read_unlock(void)
  8 {
  9   smp_mb();
 10   __get_thread_var(rcu_reader_gp) = rcu_gp_ctr;
 11 }
 12
 13 void synchronize_rcu(void)
 14 {
 15   int t;
 16
 17   smp_mb();
 18   spin_lock(&rcu_gp_lock);
 19   rcu_gp_ctr += 2;
 20   smp_mb();
 21   for_each_thread(t) {
 22     while ((per_thread(rcu_reader_gp, t) & 0x1) &&
 23            ((per_thread(rcu_reader_gp, t) -
 24              rcu_gp_ctr) < 0)) {
 25       poll(NULL, 0, 10);
 26     }
 27   }
 28   spin_unlock(&rcu_gp_lock);
 29   smp_mb();
 30 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsubsection}
{\newpage\clearpage
\lthtmlfigureA{figure7164}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 DEFINE_SPINLOCK(rcu_gp_lock);
  2 #define RCU_GP_CTR_SHIFT 7
  3 #define RCU_GP_CTR_BOTTOM_BIT (1 << RCU_GP_CTR_SHIFT)
  4 #define RCU_GP_CTR_NEST_MASK (RCU_GP_CTR_BOTTOM_BIT - 1)
  5 long rcu_gp_ctr = 0;
  6 DEFINE_PER_THREAD(long, rcu_reader_gp);\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlfigureA{figure7170}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 static void rcu_read_lock(void)
  2 {
  3   long tmp;
  4   long *rrgp;
  5
  6   rrgp = &__get_thread_var(rcu_reader_gp);
  7   tmp = *rrgp;
  8   if ((tmp & RCU_GP_CTR_NEST_MASK) == 0)
  9     tmp = rcu_gp_ctr;
 10   tmp++;
 11   *rrgp = tmp;
 12   smp_mb();
 13 }
 14
 15 static void rcu_read_unlock(void)
 16 {
 17   long tmp;
 18
 19   smp_mb();
 20   __get_thread_var(rcu_reader_gp)--;
 21 }
 22
 23 void synchronize_rcu(void)
 24 {
 25   int t;
 26
 27   smp_mb();
 28   spin_lock(&rcu_gp_lock);
 29   rcu_gp_ctr += RCU_GP_CTR_BOTTOM_BIT;
 30   smp_mb();
 31   for_each_thread(t) {
 32     while (rcu_gp_ongoing(t) &&
 33            ((per_thread(rcu_reader_gp, t) -
 34              rcu_gp_ctr) < 0)) {
 35       poll(NULL, 0, 10);
 36     }
 37   }
 38   spin_unlock(&rcu_gp_lock);
 39   smp_mb();
 40 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsubsection}
{\newpage\clearpage
\lthtmlfigureA{figure7228}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 DEFINE_SPINLOCK(rcu_gp_lock);
  2 long rcu_gp_ctr = 0;
  3 DEFINE_PER_THREAD(long, rcu_reader_qs_gp);\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlfigureA{figure7234}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 static void rcu_read_lock(void)
  2 {
  3 }
  4
  5 static void rcu_read_unlock(void)
  6 {
  7 }
  8
  9 rcu_quiescent_state(void)
 10 {
 11   smp_mb();
 12   __get_thread_var(rcu_reader_qs_gp) =
 13     ACCESS_ONCE(rcu_gp_ctr) + 1;
 14   smp_mb();
 15 }
 16
 17 static void rcu_thread_offline(void)
 18 {
 19   smp_mb();
 20   __get_thread_var(rcu_reader_qs_gp) =
 21     ACCESS_ONCE(rcu_gp_ctr);
 22   smp_mb();
 23 }
 24
 25 static void rcu_thread_online(void)
 26 {
 27   rcu_quiescent_state();
 28 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlfigureA{figure7277}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 void synchronize_rcu(void)
  2 {
  3   int t;
  4
  5   smp_mb();
  6   spin_lock(&rcu_gp_lock);
  7   rcu_gp_ctr += 2;
  8   smp_mb();
  9   for_each_thread(t) {
 10     while (rcu_gp_ongoing(t) &&
 11            ((per_thread(rcu_reader_qs_gp, t) -
 12              rcu_gp_ctr) < 0)) {
 13       poll(NULL, 0, 10);
 14     }
 15   }
 16   spin_unlock(&rcu_gp_lock);
 17   smp_mb();
 18 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsubsection}
\stepcounter{subsection}
\stepcounter{chapter}
\stepcounter{section}
\stepcounter{subsection}
\stepcounter{subsection}
{\newpage\clearpage
\lthtmlfigureA{figure7817}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 struct countarray {
  2   unsigned long total;
  3   unsigned long *counterp[NR_THREADS];
  4 };
  5 
  6 long __thread counter = 0;
  7 struct countarray *countarrayp = NULL;
  8 DEFINE_SPINLOCK(final_mutex);
  9 
 10 void inc_count(void)
 11 {
 12   counter++;
 13 }
 14 
 15 long read_count(void)
 16 {
 17   struct countarray *cap;
 18   unsigned long sum;
 19   int t;
 20 
 21   rcu_read_lock();
 22   cap = rcu_dereference(countarrayp);
 23   sum = cap->total;
 24   for_each_thread(t)
 25     if (cap->counterp[t] != NULL)
 26       sum += *cap->counterp[t];
 27   rcu_read_unlock();
 28   return sum;
 29 }
 30 
 31 void count_init(void)
 32 {
 33   countarrayp = malloc(sizeof(*countarrayp));
 34   if (countarrayp == NULL) {
 35     fprintf(stderr, "Out of memory\n");
 36     exit(-1);
 37   }
 38   memset(countarrayp, '\0', sizeof(*countarrayp));
 39 }
 40 
 41 void count_register_thread(void)
 42 {
 43   int idx = smp_thread_id();
 44 
 45   spin_lock(&final_mutex);
 46   countarrayp->counterp[idx] = 
 47   spin_unlock(&final_mutex);
 48 }
 49 
 50 void count_unregister_thread(int nthreadsexpected)
 51 {
 52   struct countarray *cap;
 53   struct countarray *capold;
 54   int idx = smp_thread_id();
 55 
 56   cap = malloc(sizeof(*countarrayp));
 57   if (cap == NULL) {
 58     fprintf(stderr, "Out of memory\n");
 59     exit(-1);
 60   }
 61   spin_lock(&final_mutex);
 62   *cap = *countarrayp;
 63   cap->total += counter;
 64   cap->counterp[idx] = NULL;
 65   capold = countarrayp;
 66   rcu_assign_pointer(countarrayp, cap);
 67   spin_unlock(&final_mutex);
 68   synchronize_rcu();
 69   free(capold);
 70 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsection}
\stepcounter{section}
\stepcounter{chapter}
\stepcounter{section}
\stepcounter{section}
\stepcounter{section}
\stepcounter{section}
\stepcounter{section}
\stepcounter{section}
\stepcounter{section}
\stepcounter{chapter}
\stepcounter{section}
\stepcounter{section}
\stepcounter{section}
\stepcounter{section}
\stepcounter{section}
\stepcounter{section}
\stepcounter{chapter}
\stepcounter{section}
\stepcounter{section}
\stepcounter{subsection}
{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap9088}%
\resizebox{3in}{!}{\includegraphics{appendix/whymb/cacheSC}}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap9096}%
\resizebox{3in}{2in}{\includegraphics{cartoons/CPU_toon_outoforder_colored}}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsection}
{\newpage\clearpage
\lthtmlfigureA{figure8120}%
\begin{figure}{ \centering
\begin{verbatim}

  1 thread0(void)
  2 {
  3   A = 1;
  4   smp_wmb();
  5   B = 1;
  6 }
  7
  8 thread1(void)
  9 {
 10   while (B != 1)
 11     continue;
 12   barrier();
 13   C = 1;
 14 }
 15
 16 thread2(void)
 17 {
 18   while (C != 1)
 19     continue;
 20   smp_mb();
 21   assert(A != 0);
 22 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsection}
{\newpage\clearpage
\lthtmlfigureA{figure8147}%
\begin{figure}{ \centering
\begin{verbatim}

  1 state.variable = mycpu;
  2 lasttb = oldtb = firsttb = gettb();
  3 while (state.variable == mycpu) {
  4   lasttb = oldtb;
  5   oldtb = gettb();
  6   if (lasttb - firsttb > 1000)
  7     break;
  8 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap9152}%
\resizebox{3in}{!}{\includegraphics{advsync/MoreThanOneValue}}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsection}
\stepcounter{subsubsection}
\stepcounter{subsubsection}
\stepcounter{subsubsection}
\stepcounter{subsubsection}
\stepcounter{paragraph}
\stepcounter{paragraph}
\stepcounter{paragraph}
\stepcounter{subsubsection}
\stepcounter{paragraph}
\stepcounter{paragraph}
\stepcounter{subsubsection}
\stepcounter{paragraph}
\stepcounter{paragraph}
\stepcounter{paragraph}
\stepcounter{subsubsection}
\stepcounter{subsection}
\stepcounter{subsection}
\stepcounter{subsection}
{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap24401}%
\includegraphics{advsync/AbstractMemoryAccessModel}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlinlinemathA{tex2html_wrap_inline9032}%
$\rightarrow$%
\lthtmlinlinemathZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsection}
\stepcounter{subsection}
\stepcounter{subsection}
\stepcounter{subsubsection}
\stepcounter{paragraph}
{\newpage\clearpage
\lthtmlinlinemathA{tex2html_wrap_inline9060}%
$\dagger$%
\lthtmlinlinemathZ
\lthtmlcheckvsize\clearpage}

\stepcounter{paragraph}
\stepcounter{paragraph}
\stepcounter{paragraph}
\stepcounter{subsubsection}
\stepcounter{paragraph}
\stepcounter{paragraph}
\stepcounter{subsubsection}
\stepcounter{subsubsection}
\stepcounter{subsubsection}
\stepcounter{subsubsection}
{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap24606}%
\includegraphics{advsync/MemoryBarrierPairing}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsubsection}
{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap24615}%
\includegraphics{advsync/WriteBarrierOrdering}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap24634}%
\includegraphics{advsync/DataDependencyNeeded}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap24655}%
\includegraphics{advsync/DataDependencySupplied}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap24672}%
\includegraphics{advsync/ReadBarrierNeeded}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap24691}%
\includegraphics{advsync/ReadBarrierSupplied}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap24712}%
\includegraphics{advsync/ReadBarrierSupplied1}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap24716}%
\includegraphics{advsync/ReadBarrierSupplied2}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsubsection}
{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap24732}%
\includegraphics{advsync/SpeculativeLoad}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap24749}%
\includegraphics{advsync/SpeculativeLoadBarrier}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap24753}%
\includegraphics{advsync/SpeculativeLoadBarrierCancel}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsection}
\stepcounter{subsection}
\stepcounter{subsubsection}
\stepcounter{paragraph}
\stepcounter{paragraph}
\stepcounter{paragraph}
\stepcounter{paragraph}
\stepcounter{subsection}
{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap24826}%
\includegraphics{advsync/MemoryArchitecture}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsubsection}
{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap24831}%
\includegraphics{advsync/SplitCache}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsection}
\stepcounter{section}
\stepcounter{subsection}
\stepcounter{subsection}
\stepcounter{subsection}
\stepcounter{subsection}
\stepcounter{chapter}
\stepcounter{section}
\stepcounter{section}
{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap10030}%
\resizebox{3in}{!}{\includegraphics{easy/Mandel_zoom_00_mandelbrot_set}}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlinlinemathA{tex2html_wrap_inline10002}%
$N-1$%
\lthtmlinlinemathZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap10082}%
\resizebox{3in}{!}{\includegraphics{cartoons/ShavingTheMandelbrotSet}}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{chapter}
\stepcounter{chapter}
\stepcounter{section}
\stepcounter{subsection}
\stepcounter{subsection}
\stepcounter{subsection}
\stepcounter{subsection}
\stepcounter{subsection}
\stepcounter{subsection}
\stepcounter{subsection}
\stepcounter{subsection}
\stepcounter{subsection}
\stepcounter{subsection}
\stepcounter{subsection}
\stepcounter{subsection}
\stepcounter{subsection}
\stepcounter{subsection}
\stepcounter{section}
\stepcounter{section}
\appendix
\stepcounter{chapter}
\stepcounter{section}
{\newpage\clearpage
\lthtmlfigureA{figure10510}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 /* WARNING: BUGGY CODE. */
  2 void *producer(void *ignored)
  3 {
  4   int i = 0;
  5
  6   producer_ready = 1;
  7   while (!goflag)
  8     sched_yield();
  9   while (goflag) {
 10     ss.t = dgettimeofday();
 11     ss.a = ss.c + 1;
 12     ss.b = ss.a + 1;
 13     ss.c = ss.b + 1;
 14     i++;
 15   }
 16   printf("producer exiting: %d samples\n", i);
 17   producer_done = 1;
 18   return (NULL);
 19 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlfigureA{figure10516}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 /* WARNING: BUGGY CODE. */
  2 void *consumer(void *ignored)
  3 {
  4   struct snapshot_consumer curssc;
  5   int i = 0;
  6   int j = 0;
  7
  8   consumer_ready = 1;
  9   while (ss.t == 0.0) {
 10     sched_yield();
 11   }
 12   while (goflag) {
 13     curssc.tc = dgettimeofday();
 14     curssc.t = ss.t;
 15     curssc.a = ss.a;
 16     curssc.b = ss.b;
 17     curssc.c = ss.c;
 18     curssc.sequence = curseq;
 19     curssc.iserror = 0;
 20     if ((curssc.t > curssc.tc) ||
 21         modgreater(ssc[i].a, curssc.a) ||
 22         modgreater(ssc[i].b, curssc.b) ||
 23         modgreater(ssc[i].c, curssc.c) ||
 24         modgreater(curssc.a, ssc[i].a + maxdelta) ||
 25         modgreater(curssc.b, ssc[i].b + maxdelta) ||
 26         modgreater(curssc.c, ssc[i].c + maxdelta)) {
 27       i++;
 28       curssc.iserror = 1;
 29     } else if (ssc[i].iserror)
 30       i++;
 31     ssc[i] = curssc;
 32     curseq++;
 33     if (i + 1 >= NSNAPS)
 34       break;
 35   }
 36   printf("consumer exited, collected %d items of %d\n",
 37          i, curseq);
 38   if (ssc[0].iserror)
 39     printf("0/%d: %.6f %.6f (%.3f) %d %d %d\n",
 40            ssc[0].sequence, ssc[j].t, ssc[j].tc,
 41            (ssc[j].tc - ssc[j].t) * 1000000,
 42            ssc[j].a, ssc[j].b, ssc[j].c);
 43   for (j = 0; j <= i; j++)
 44     if (ssc[j].iserror)
 45       printf("%d: %.6f (%.3f) %d %d %d\n",
 46              ssc[j].sequence,
 47              ssc[j].t, (ssc[j].tc - ssc[j].t) * 1000000,
 48              ssc[j].a - ssc[j - 1].a,
 49              ssc[j].b - ssc[j - 1].b,
 50              ssc[j].c - ssc[j - 1].c);
 51   consumer_done = 1;
 52 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap24953}%
\includegraphics{appendix/questions/after}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{chapter}
\stepcounter{section}
\stepcounter{subsection}
\stepcounter{section}
{\newpage\clearpage
\lthtmlfigureA{figurestar10660}%
\begin{figure*}{ \scriptsize
\begin{verbatim}

int smp_thread_id(void)
thread_id_t create_thread(void *(*func)(void *), void *arg)
for_each_thread(t)
for_each_running_thread(t)
void *wait_thread(thread_id_t tid)
void wait_all_threads(void)\end{verbatim}

}

\end{figure*}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsection}
\stepcounter{subsection}
\stepcounter{subsection}
\stepcounter{subsection}
\stepcounter{subsection}
\stepcounter{subsection}
\stepcounter{subsection}
{\newpage\clearpage
\lthtmlfigureA{figure10700}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 void *thread_test(void *arg)
  2 {
  3   int myarg = (int)arg;
  4
  5   printf("child thread %d: smp_thread_id() = %d\n",
  6          myarg, smp_thread_id());
  7   return NULL;
  8 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlfigureA{figure10710}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 int main(int argc, char *argv[])
  2 {
  3   int i;
  4   int nkids = 1;
  5
  6   smp_init();
  7   if (argc > 1) {
  8     nkids = strtoul(argv[1], NULL, 0);
  9     if (nkids > NR_THREADS) {
 10       fprintf(stderr, "nkids=%d too big, max=%d\n",
 11         nkids, NR_THREADS);
 12       usage(argv[0]);
 13     }
 14   }
 15   printf("Parent spawning %d threads.\n", nkids);
 16   for (i = 0; i < nkids; i++)
 17     create_thread(thread_test, (void *)i);
 18   wait_all_threads();
 19   printf("All threads completed.\n", nkids);
 20   exit(0);
 21 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{section}
{\newpage\clearpage
\lthtmlfigureA{figure10719}%
\begin{figure}{ \scriptsize
\begin{verbatim}

void spin_lock_init(spinlock_t *sp);
void spin_lock(spinlock_t *sp);
int spin_trylock(spinlock_t *sp);
void spin_unlock(spinlock_t *sp);\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsection}
\stepcounter{subsection}
\stepcounter{subsection}
\stepcounter{subsection}
\stepcounter{subsection}
\stepcounter{section}
{\newpage\clearpage
\lthtmlfigureA{figure10757}%
\begin{figure}{ \scriptsize
\begin{verbatim}

DEFINE_PER_THREAD(type, name)
DECLARE_PER_THREAD(type, name)
per_thread(name, thread)
__get_thread_var(name)
init_per_thread(name, v)\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsection}
\stepcounter{subsection}
\stepcounter{subsection}
\stepcounter{subsection}
\stepcounter{subsection}
\stepcounter{subsection}
\stepcounter{section}
\stepcounter{chapter}
\stepcounter{section}
{\newpage\clearpage
\lthtmlfigureA{figure11046}%
\begin{figure}\begin{center}
\small
\begin{picture}(170,170)(0,0)
\par
% Addresses
\par
\put(0,0){\makebox(20,10){\tt0xF}}
	\put(0,10){\makebox(20,10){\tt0xE}}
	\put(0,20){\makebox(20,10){\tt0xD}}
	\put(0,30){\makebox(20,10){\tt0xC}}
	\put(0,40){\makebox(20,10){\tt0xB}}
	\put(0,50){\makebox(20,10){\tt0xA}}
	\put(0,60){\makebox(20,10){\tt0x9}}
	\put(0,70){\makebox(20,10){\tt0x8}}
	\put(0,80){\makebox(20,10){\tt0x7}}
	\put(0,90){\makebox(20,10){\tt0x6}}
	\put(0,100){\makebox(20,10){\tt0x5}}
	\put(0,110){\makebox(20,10){\tt0x4}}
	\put(0,120){\makebox(20,10){\tt0x3}}
	\put(0,130){\makebox(20,10){\tt0x2}}
	\put(0,140){\makebox(20,10){\tt0x1}}
	\put(0,150){\makebox(20,10){\tt0x0}}
\par
% Way 0
\par
\put(20,163){\makebox(80,10){Way 0}}
	\put(20,0){\framebox{(}80,10){\tt }}
	\put(20,10){\framebox{(}80,10){\tt0x12345E00}}
	\put(20,20){\framebox{(}80,10){\tt0x12345D00}}
	\put(20,30){\framebox{(}80,10){\tt0x12345C00}}
	\put(20,40){\framebox{(}80,10){\tt0x12345B00}}
	\put(20,50){\framebox{(}80,10){\tt0x12345A00}}
	\put(20,60){\framebox{(}80,10){\tt0x12345900}}
	\put(20,70){\framebox{(}80,10){\tt0x12345800}}
	\put(20,80){\framebox{(}80,10){\tt0x12345700}}
	\put(20,90){\framebox{(}80,10){\tt0x12345600}}
	\put(20,100){\framebox{(}80,10){\tt0x12345500}}
	\put(20,110){\framebox{(}80,10){\tt0x12345400}}
	\put(20,120){\framebox{(}80,10){\tt0x12345300}}
	\put(20,130){\framebox{(}80,10){\tt0x12345200}}
	\put(20,140){\framebox{(}80,10){\tt0x12345100}}
	\put(20,150){\framebox{(}80,10){\tt0x12345000}}
\par
% Way 1
\par
\put(100,163){\makebox(80,10){Way 1}}
	\put(100,0){\framebox{(}80,10){\tt }}
	\put(100,10){\framebox{(}80,10){\tt0x43210E00}}
	\put(100,20){\framebox{(}80,10){\tt }}
	\put(100,30){\framebox{(}80,10){\tt }}
	\put(100,40){\framebox{(}80,10){\tt }}
	\put(100,50){\framebox{(}80,10){\tt }}
	\put(100,60){\framebox{(}80,10){\tt }}
	\put(100,70){\framebox{(}80,10){\tt }}
	\put(100,80){\framebox{(}80,10){\tt }}
	\put(100,90){\framebox{(}80,10){\tt }}
	\put(100,100){\framebox{(}80,10){\tt }}
	\put(100,110){\framebox{(}80,10){\tt }}
	\put(100,120){\framebox{(}80,10){\tt }}
	\put(100,130){\framebox{(}80,10){\tt }}
	\put(100,140){\framebox{(}80,10){\tt }}
	\put(100,150){\framebox{(}80,10){\tt }}
\end{picture}
\end{center}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{section}
\stepcounter{subsection}
\stepcounter{subsection}
\stepcounter{subsection}
{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap25044}%
\includegraphics{appendix/whymb/MESI}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsection}
\stepcounter{section}
{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap25139}%
\includegraphics{appendix/whymb/cacheSCwrite}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsection}
{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap12142}%
\resizebox{3in}{!}{\includegraphics{appendix/whymb/cacheSB}}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsection}
{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap12164}%
\resizebox{3in}{!}{\includegraphics{appendix/whymb/cacheSBf}}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsection}
\stepcounter{section}
\stepcounter{subsection}
\stepcounter{subsection}
{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap12214}%
\resizebox{3in}{!}{\includegraphics{appendix/whymb/cacheSBfIQ}}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsection}
\stepcounter{section}
\stepcounter{section}
\stepcounter{subsection}
{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap12290}%
\resizebox{3in}{!}{\includegraphics{appendix/whymb/hostileordering}}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsection}
\stepcounter{subsection}
\stepcounter{subsection}
\stepcounter{section}
{\newpage\clearpage
\lthtmlpictureA{picture11457}%
\begin{picture}(6,185)(0,0)
		\rotatebox{90}{Loads Reordered After Loads?}
\end{picture}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlpictureA{picture11461}%
\begin{picture}(6,185)(0,0)
		\rotatebox{90}{Loads Reordered After Stores?}
\end{picture}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlpictureA{picture11465}%
\begin{picture}(6,185)(0,0)
		\rotatebox{90}{Stores Reordered After Stores?}
\end{picture}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlpictureA{picture11469}%
\begin{picture}(6,185)(0,0)
		\rotatebox{90}{Stores Reordered After Loads?}
\end{picture}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlpictureA{picture11473}%
\begin{picture}(6,185)(0,0)
		\rotatebox{90}{Atomic Instructions Reordered With Loads?}
\end{picture}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlpictureA{picture11477}%
\begin{picture}(6,185)(0,0)
		\rotatebox{90}{Atomic Instructions Reordered With Stores?}
\end{picture}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlpictureA{picture11481}%
\begin{picture}(6,185)(0,0)
		\rotatebox{90}{Dependent Loads Reordered?}
\end{picture}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlpictureA{picture11485}%
\begin{picture}(6,185)(0,0)
		\rotatebox{90}{Incoherent Instruction Cache/Pipeline?}
\end{picture}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlinlineA{tex2html_nomath_inline12382}%
\textregistered%
\lthtmlinlineZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsection}
{\newpage\clearpage
\lthtmlfigureA{figure11518}%
\begin{figure}{\tt\scriptsize
\begin{verbatim}

  1 struct el *insert(long key, long data)
  2 {
  3     struct el *p;
  4     p = kmalloc(sizeof(*p), GFP_ATOMIC);
  5     spin_lock(&mutex);
  6     p->next = head.next;
  7     p->key = key;
  8     p->data = data;
  9     smp_wmb();
 10     head.next = p;
 11     spin_unlock(&mutex);
 12 }
 13
 14 struct el *search(long key)
 15 {
 16     struct el *p;
 17     p = head.next;
 18     while (p != &head) {
 19         /* BUG ON ALPHA!!! */
 20         if (p->key == key) {
 21             return (p);
 22         }
 23         p = p->next;
 24     };
 25     return (NULL);
 26 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlfigureA{figure11530}%
\begin{figure}\begin{center}
\begin{picture}(213,160)(0,25)
\par
% First CPU
\par
\put(0,50){\framebox{(}90,20)[c]{(w)mb Sequencing}}
	\put(0,70){\framebox{(}45,50)[l]{}}
	\put(0,102){\makebox(45,1)[c]{Cache}}
	\put(0,90){\makebox(45,1)[c]{Bank 0}}
	\put(45,70){\framebox{(}45,50)[l]{}}
	\put(45,102){\makebox(45,1)[c]{Cache}}
	\put(45,90){\makebox(45,1)[c]{Bank 1}}
	\put(0,120){\framebox{(}90,20)[c]{(r)mb Sequencing}}
	\put(0,140){\framebox{(}90,20)[c]{Writing CPU Core}}
\par
% Second CPU
\par
\put(120,50){\framebox{(}90,20)[c]{(w)mb Sequencing}}
	\put(120,70){\framebox{(}45,50)[l]{}}
	\put(120,102){\makebox(45,1)[c]{Cache}}
	\put(120,90){\makebox(45,1)[c]{Bank 0}}
	\put(165,70){\framebox{(}45,50)[l]{}}
	\put(165,102){\makebox(45,1)[c]{Cache}}
	\put(165,90){\makebox(45,1)[c]{Bank 1}}
	\put(120,120){\framebox{(}90,20)[c]{(r)mb Sequencing}}
	\put(120,140){\framebox{(}90,20)[c]{Reading CPU Core}}
\par
% Interconnection "network"
\par
\put(45,50){\line(0,-1){25}}
	\put(45,25){\line(1,0){120}}
	\put(165,25){\vector(0,1){25}}
	\put(45,25){\makebox(120,20)[c]{Interconnect}}
\end{picture}
\end{center}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlfigureA{figure11565}%
\begin{figure}{\tt\scriptsize
\begin{verbatim}

  1 struct el *insert(long key, long data)
  2 {
  3     struct el *p;
  4     p = kmalloc(sizeof(*p), GFP_ATOMIC);
  5     spin_lock(&mutex);
  6     p->next = head.next;
  7     p->key = key;
  8     p->data = data;
  9     smp_wmb();
 10     head.next = p;
 11     spin_unlock(&mutex);
 12 }
 13
 14 struct el *search(long key)
 15 {
 16     struct el *p;
 17     p = head.next;
 18     while (p != &head) {
 19         smp_read_barrier_depends();
 20         if (p->key == key) {
 21             return (p);
 22         }
 23         p = p->next;
 24     };
 25     return (NULL);
 26 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsection}
\stepcounter{subsection}
\stepcounter{subsection}
{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap12588}%
\resizebox{3in}{2in}{\includegraphics{cartoons/LD,ACQ}}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsection}
\stepcounter{subsection}
\stepcounter{subsection}
\stepcounter{subsection}
\stepcounter{subsection}
\stepcounter{section}
\stepcounter{section}
\stepcounter{chapter}
\stepcounter{section}
{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap13178}%
\resizebox{3in}{!}{\includegraphics{cartoons/RCUCallbacks}}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsection}
\stepcounter{subsubsection}
\stepcounter{subsubsection}
\stepcounter{subsection}
{\newpage\clearpage
\lthtmlfigureA{figure12922}%
\begin{figure}{ \scriptsize
\begin{verbatim}

int init_srcu_struct(struct srcu_struct *sp);
void cleanup_srcu_struct(struct srcu_struct *sp);
int srcu_read_lock(struct srcu_struct *sp);
void srcu_read_unlock(struct srcu_struct *sp, int idx);
void synchronize_srcu(struct srcu_struct *sp);
long srcu_batches_completed(struct srcu_struct *sp);\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsubsection}
\stepcounter{subsubsection}
\stepcounter{subsubsection}
\stepcounter{subsubsection}
{\newpage\clearpage
\lthtmlfigureA{figure13015}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 int readside(void)
  2 {
  3   int idx;
  4
  5   rcu_read_lock();
  6   if (nomoresrcu) {
  7     rcu_read_unlock();
  8     return -EINVAL;
  9   }
 10   idx = srcu_read_lock(&ss);
 11   rcu_read_unlock();
 12   /* SRCU read-side critical section. */
 13   srcu_read_unlock(&ss, idx);
 14   return 0;
 15 }
 16
 17 void cleanup(void)
 18 {
 19   nomoresrcu = 1;
 20   synchronize_rcu();
 21   synchronize_srcu(&ss);
 22   cleanup_srcu_struct(&ss);
 23 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsection}
\stepcounter{subsubsection}
{\newpage\clearpage
\lthtmlfigureA{figure13049}%
\begin{figure}{ \scriptsize
\begin{verbatim}

 1 struct srcu_struct_array {
 2   int c[2];
 3 };
 4 struct srcu_struct {
 5   int completed;
 6   struct srcu_struct_array *per_cpu_ref;
 7   struct mutex mutex;
 8 };\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap25484}%
\includegraphics{appendix/rcuimpl/srcuds}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsubsection}
{\newpage\clearpage
\lthtmlfigureA{figure13069}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 int init_srcu_struct(struct srcu_struct *sp)
  2 {
  3   sp->completed = 0;
  4   mutex_init(&sp->mutex);
  5   sp->per_cpu_ref =
  6     alloc_percpu(struct srcu_struct_array);
  7   return (sp->per_cpu_ref ? 0 : -ENOMEM);
  8 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlfigureA{figure13089}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 int srcu_readers_active_idx(struct srcu_struct *sp,
  2                             int idx)
  3 {
  4   int cpu;
  5   int sum;
  6
  7   sum = 0;
  8   for_each_possible_cpu(cpu)
  9     sum += per_cpu_ptr(sp->per_cpu_ref, cpu)->c[idx];
 10   return sum;
 11 }
 12
 13 int srcu_readers_active(struct srcu_struct *sp)
 14 {
 15   return srcu_readers_active_idx(sp, 0) +
 16          srcu_readers_active_idx(sp, 1);
 17 }
 18
 19 void cleanup_srcu_struct(struct srcu_struct *sp)
 20 {
 21   int sum;
 22
 23   sum = srcu_readers_active(sp);
 24   WARN_ON(sum);
 25   if (sum != 0)
 26     return;
 27   free_percpu(sp->per_cpu_ref);
 28   sp->per_cpu_ref = NULL;
 29 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsubsection}
{\newpage\clearpage
\lthtmlfigureA{figure13109}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 int srcu_read_lock(struct srcu_struct *sp)
  2 {
  3   int idx;
  4
  5   preempt_disable();
  6   idx = sp->completed & 0x1;
  7   barrier();
  8   per_cpu_ptr(sp->per_cpu_ref,
  9               smp_processor_id())->c[idx]++;
 10   srcu_barrier();
 11   preempt_enable();
 12   return idx;
 13 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlfigureA{figure13122}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 void srcu_read_unlock(struct srcu_struct *sp, int idx)
  2 {
  3   preempt_disable();
  4   srcu_barrier();
  5   per_cpu_ptr(sp->per_cpu_ref,
  6               smp_processor_id())->c[idx]--;
  7   preempt_enable();
  8 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsubsection}
{\newpage\clearpage
\lthtmlfigureA{figure13147}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 void synchronize_srcu(struct srcu_struct *sp)
  2 {
  3   int idx;
  4
  5   idx = sp->completed;
  6   mutex_lock(&sp->mutex);
  7   if ((sp->completed - idx) >= 2) {
  8     mutex_unlock(&sp->mutex);
  9     return;
 10   }
 11   synchronize_sched();
 12   idx = sp->completed & 0x1;
 13   sp->completed++;
 14   synchronize_sched();
 15   while (srcu_readers_active_idx(sp, idx))
 16     schedule_timeout_interruptible(1);
 17   synchronize_sched();
 18   mutex_unlock(&sp->mutex);
 19 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsection}
\stepcounter{section}
\stepcounter{subsection}
\stepcounter{subsection}
{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap13916}%
\resizebox{3in}{!}{\includegraphics{appendix/rcuimpl/FlatClassicRCU}}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsection}
\stepcounter{subsection}
{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap13940}%
\resizebox{3in}{!}{\includegraphics{appendix/rcuimpl/TreeClassicRCU}}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap13950}%
\resizebox{3in}{!}{\includegraphics{appendix/rcuimpl/TreeMapping}}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap13958}%
\resizebox{3in}{!}{\includegraphics{appendix/rcuimpl/TreeClassicRCUGP}}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap13966}%
\resizebox{3in}{!}{\includegraphics{appendix/rcuimpl/BigTreeClassicRCU}}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap13988}%
\resizebox{3in}{!}{\includegraphics{appendix/rcuimpl/BigTreeClassicRCUBH}}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsection}
{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap14010}%
\resizebox{3in}{!}{\includegraphics{appendix/rcuimpl/BigTreeClassicRCUBHdyntick}}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsection}
{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap14022}%
\resizebox{3in}{!}{\includegraphics{appendix/rcuimpl/GenericRCUStateMachine}}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap14034}%
\resizebox{3in}{!}{\includegraphics{appendix/rcuimpl/TreeRCUStateMachine}}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsection}
\stepcounter{subsubsection}
\stepcounter{subsubsection}
\stepcounter{subsubsection}
\stepcounter{subsubsection}
\stepcounter{subsubsection}
\stepcounter{subsubsection}
\stepcounter{subsubsection}
\stepcounter{subsubsection}
\stepcounter{subsubsection}
\stepcounter{subsubsection}
\stepcounter{subsection}
\stepcounter{subsection}
\stepcounter{section}
\stepcounter{subsection}
\stepcounter{subsubsection}
\stepcounter{subsubsection}
\stepcounter{subsubsection}
\stepcounter{subsubsection}
\stepcounter{subsubsection}
{\newpage\clearpage
\lthtmlfigureA{figurestar14631}%
\begin{figure*}{
\begin{verbatim}

  1 #define MAX_RCU_LVLS    3
  2 #define RCU_FANOUT      (CONFIG_RCU_FANOUT)
  3 #define RCU_FANOUT_SQ   (RCU_FANOUT * RCU_FANOUT)
  4 #define RCU_FANOUT_CUBE (RCU_FANOUT_SQ * RCU_FANOUT)
  5
  6 #if NR_CPUS <= RCU_FANOUT
  7 #  define NUM_RCU_LVLS  1
  8 #  define NUM_RCU_LVL_0 1
  9 #  define NUM_RCU_LVL_1 (NR_CPUS)
 10 #  define NUM_RCU_LVL_2 0
 11 #  define NUM_RCU_LVL_3 0
 12 #elif NR_CPUS <= RCU_FANOUT_SQ
 13 #  define NUM_RCU_LVLS  2
 14 #  define NUM_RCU_LVL_0 1
 15 #  define NUM_RCU_LVL_1 (((NR_CPUS) + RCU_FANOUT - 1) / RCU_FANOUT)
 16 #  define NUM_RCU_LVL_2 (NR_CPUS)
 17 #  define NUM_RCU_LVL_3 0
 18 #elif NR_CPUS <= RCU_FANOUT_CUBE
 19 #  define NUM_RCU_LVLS  3
 20 #  define NUM_RCU_LVL_0 1
 21 #  define NUM_RCU_LVL_1 (((NR_CPUS) + RCU_FANOUT_SQ - 1) / RCU_FANOUT_SQ)
 22 #  define NUM_RCU_LVL_2 (((NR_CPUS) + (RCU_FANOUT) - 1) / (RCU_FANOUT))
 23 #  define NUM_RCU_LVL_3 NR_CPUS
 24 #else
 25 # error "CONFIG_RCU_FANOUT insufficient for NR_CPUS"
 26 #endif /* #if (NR_CPUS) <= RCU_FANOUT */
 27
 28 #define RCU_SUM (NUM_RCU_LVL_0 + NUM_RCU_LVL_1 + NUM_RCU_LVL_2 + NUM_RCU_LVL_3)
 29 #define NUM_RCU_NODES (RCU_SUM - NR_CPUS)\end{verbatim}

}

\end{figure*}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsection}
\stepcounter{subsubsection}
{\newpage\clearpage
\lthtmlfigureA{figure14685}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 void __rcu_read_lock(void)
  2 {
  3   preempt_disable();
  4   __acquire(RCU);
  5   rcu_read_acquire();
  6 }
  7
  8 void __rcu_read_unlock(void)
  9 {
 10   rcu_read_release();
 11   __release(RCU);
 12   preempt_enable();
 13 }
 14
 15 void __rcu_read_lock_bh(void)
 16 {
 17   local_bh_disable();
 18   __acquire(RCU_BH);
 19   rcu_read_acquire();
 20 }
 21
 22 void __rcu_read_unlock_bh(void)
 23 {
 24   rcu_read_release();
 25   __release(RCU_BH);
 26   local_bh_enable();
 27 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsubsection}
{\newpage\clearpage
\lthtmlfigureA{figure14704}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 static void
  2 __call_rcu(struct rcu_head *head,
  3            void (*func)(struct rcu_head *rcu),
  4            struct rcu_state *rsp)
  5 {
  6   unsigned long flags;
  7   struct rcu_data *rdp;
  8
  9   head->func = func;
 10   head->next = NULL;
 11   smp_mb();
 12   local_irq_save(flags);
 13   rdp = rsp->rda[smp_processor_id()];
 14   rcu_process_gp_end(rsp, rdp);
 15   check_for_new_grace_period(rsp, rdp);
 16   *rdp->nxttail[RCU_NEXT_TAIL] = head;
 17   rdp->nxttail[RCU_NEXT_TAIL] = &head->next;
 18   if (ACCESS_ONCE(rsp->completed) ==
 19       ACCESS_ONCE(rsp->gpnum)) {
 20     unsigned long nestflag;
 21     struct rcu_node *rnp_root = rcu_get_root(rsp);
 22
 23     spin_lock_irqsave(&rnp_root->lock, nestflag);
 24     rcu_start_gp(rsp, nestflag);
 25   }
 26   if (unlikely(++rdp->qlen > qhimark)) {
 27     rdp->blimit = LONG_MAX;
 28     force_quiescent_state(rsp, 0);
 29   } else if ((long)(ACCESS_ONCE(rsp->jiffies_force_qs) -
 30                     jiffies) < 0 ||
 31              (rdp->n_rcu_pending_force_qs -
 32               rdp->n_rcu_pending) < 0)
 33     force_quiescent_state(rsp, 1);
 34   local_irq_restore(flags);
 35 }
 36
 37 void call_rcu(struct rcu_head *head,
 38               void (*func)(struct rcu_head *rcu))
 39 {
 40   __call_rcu(head, func, &rcu_state);
 41 }
 42
 43 void call_rcu_bh(struct rcu_head *head,
 44                  void (*func)(struct rcu_head *rcu))
 45 {
 46   __call_rcu(head, func, &rcu_bh_state);
 47 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsubsection}
{\newpage\clearpage
\lthtmlfigureA{figure14737}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 static int __rcu_pending(struct rcu_state *rsp,
  2                          struct rcu_data *rdp)
  3 {
  4   rdp->n_rcu_pending++;
  5
  6   check_cpu_stall(rsp, rdp);
  7   if (rdp->qs_pending)
  8     return 1;
  9   if (cpu_has_callbacks_ready_to_invoke(rdp))
 10     return 1;
 11   if (cpu_needs_another_gp(rsp, rdp))
 12     return 1;
 13   if (ACCESS_ONCE(rsp->completed) != rdp->completed)
 14     return 1;
 15   if (ACCESS_ONCE(rsp->gpnum) != rdp->gpnum)
 16     return 1;
 17   if (ACCESS_ONCE(rsp->completed) !=
 18       ACCESS_ONCE(rsp->gpnum) &&
 19       ((long)(ACCESS_ONCE(rsp->jiffies_force_qs) -
 20               jiffies) < 0 ||
 21        (rdp->n_rcu_pending_force_qs -
 22         rdp->n_rcu_pending) < 0))
 23     return 1;
 24   return 0;
 25 }
 26
 27 int rcu_pending(int cpu)
 28 {
 29   return __rcu_pending(&rcu_state,
 30                        &per_cpu(rcu_data, cpu)) ||
 31          __rcu_pending(&rcu_bh_state,
 32                        &per_cpu(rcu_bh_data, cpu));
 33 }
 34
 35 void rcu_check_callbacks(int cpu, int user)
 36 {
 37   if (user ||
 38       (idle_cpu(cpu) && !in_softirq() &&
 39        hardirq_count() <= (1 << HARDIRQ_SHIFT))) {
 40     rcu_qsctr_inc(cpu);
 41     rcu_bh_qsctr_inc(cpu);
 42   } else if (!in_softirq()) {
 43     rcu_bh_qsctr_inc(cpu);
 44   }
 45   raise_softirq(RCU_SOFTIRQ);
 46 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsubsection}
{\newpage\clearpage
\lthtmlfigureA{figure14774}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 static void
  2 __rcu_process_callbacks(struct rcu_state *rsp,
  3                         struct rcu_data *rdp)
  4 {
  5   unsigned long flags;
  6
  7   if ((long)(ACCESS_ONCE(rsp->jiffies_force_qs) -
  8              jiffies) < 0 ||
  9       (rdp->n_rcu_pending_force_qs -
 10        rdp->n_rcu_pending) < 0)
 11     force_quiescent_state(rsp, 1);
 12   rcu_process_gp_end(rsp, rdp);
 13   rcu_check_quiescent_state(rsp, rdp);
 14   if (cpu_needs_another_gp(rsp, rdp)) {
 15     spin_lock_irqsave(&rcu_get_root(rsp)->lock, flags);
 16     rcu_start_gp(rsp, flags);
 17   }
 18   rcu_do_batch(rdp);
 19 }
 20
 21 static void
 22 rcu_process_callbacks(struct softirq_action *unused)
 23 {
 24   smp_mb();
 25   __rcu_process_callbacks(&rcu_state,
 26                           &__get_cpu_var(rcu_data));
 27   __rcu_process_callbacks(&rcu_bh_state,
 28                           &__get_cpu_var(rcu_bh_data));
 29   smp_mb();
 30 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsubsection}
{\newpage\clearpage
\lthtmlfigureA{figure14806}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 int rcu_needs_cpu(int cpu)
  2 {
  3   return per_cpu(rcu_data, cpu).nxtlist ||
  4          per_cpu(rcu_bh_data, cpu).nxtlist;
  5 }
  6
  7 static int __cpuinit
  8 rcu_cpu_notify(struct notifier_block *self,
  9                unsigned long action, void *hcpu)
 10 {
 11   long cpu = (long)hcpu;
 12
 13   switch (action) {
 14   case CPU_UP_PREPARE:
 15   case CPU_UP_PREPARE_FROZEN:
 16     rcu_online_cpu(cpu);
 17     break;
 18   case CPU_DEAD:
 19   case CPU_DEAD_FROZEN:
 20   case CPU_UP_CANCELED:
 21   case CPU_UP_CANCELED_FROZEN:
 22     rcu_offline_cpu(cpu);
 23     break;
 24   default:
 25     break;
 26   }
 27   return NOTIFY_OK;
 28 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsection}
{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap16031}%
\resizebox{6in}{!}{\includegraphics{appendix/rcuimpl/RCUTreeInit}}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsubsection}
{\newpage\clearpage
\lthtmlfigureA{figure14860}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 #ifdef CONFIG_RCU_FANOUT_EXACT
  2 static void __init
  3 rcu_init_levelspread(struct rcu_state *rsp)
  4 {
  5   int i;
  6
  7   for (i = NUM_RCU_LVLS - 1; i >= 0; i--)
  8     rsp->levelspread[i] = CONFIG_RCU_FANOUT;
  9 }
 10 #else
 11 static void __init
 12 rcu_init_levelspread(struct rcu_state *rsp)
 13 {
 14   int ccur;
 15   int cprv;
 16   int i;
 17
 18   cprv = NR_CPUS;
 19   for (i = NUM_RCU_LVLS - 1; i >= 0; i--) {
 20     ccur = rsp->levelcnt[i];
 21     rsp->levelspread[i] = (cprv + ccur - 1) / ccur;
 22     cprv = ccur;
 23   }
 24 }
 25 #endif\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsubsection}
{\newpage\clearpage
\lthtmlfigureA{figure14891}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 static void __init rcu_init_one(struct rcu_state *rsp)
  2 {
  3   int cpustride = 1;
  4   int i;
  5   int j;
  6   struct rcu_node *rnp;
  7
  8   for (i = 1; i < NUM_RCU_LVLS; i++)
  9     rsp->level[i] = rsp->level[i - 1] +
 10                     rsp->levelcnt[i - 1];
 11   rcu_init_levelspread(rsp);
 12   for (i = NUM_RCU_LVLS - 1; i >= 0; i--) {
 13     cpustride *= rsp->levelspread[i];
 14     rnp = rsp->level[i];
 15     for (j = 0; j < rsp->levelcnt[i]; j++, rnp++) {
 16       spin_lock_init(&rnp->lock);
 17       rnp->qsmask = 0;
 18       rnp->qsmaskinit = 0;
 19       rnp->grplo = j * cpustride;
 20       rnp->grphi = (j + 1) * cpustride - 1;
 21       if (rnp->grphi >= NR_CPUS)
 22         rnp->grphi = NR_CPUS - 1;
 23       if (i == 0) {
 24         rnp->grpnum = 0;
 25         rnp->grpmask = 0;
 26         rnp->parent = NULL;
 27       } else {
 28         rnp->grpnum = j % rsp->levelspread[i - 1];
 29         rnp->grpmask = 1UL << rnp->grpnum;
 30         rnp->parent = rsp->level[i - 1] +
 31                 j / rsp->levelspread[i - 1];
 32       }
 33       rnp->level = i;
 34     }
 35   }
 36 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsubsection}
{\newpage\clearpage
\lthtmlfigureA{figure14939}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 #define RCU_DATA_PTR_INIT(rsp, rcu_data) \
  2 do { \
  3   rnp = (rsp)->level[NUM_RCU_LVLS - 1]; \
  4   j = 0; \
  5   for_each_possible_cpu(i) { \
  6     if (i > rnp[j].grphi) \
  7       j++; \
  8     per_cpu(rcu_data, i).mynode = &rnp[j]; \
  9     (rsp)->rda[i] = &per_cpu(rcu_data, i); \
 10   } \
 11 } while (0)
 12
 13 void __init __rcu_init(void)
 14 {
 15   int i;
 16   int j;
 17   struct rcu_node *rnp;
 18
 19   rcu_init_one(&rcu_state);
 20   RCU_DATA_PTR_INIT(&rcu_state, rcu_data);
 21   rcu_init_one(&rcu_bh_state);
 22   RCU_DATA_PTR_INIT(&rcu_bh_state, rcu_bh_data);
 23
 24   for_each_online_cpu(i)
 25     rcu_cpu_notify(&rcu_nb, CPU_UP_PREPARE,
 26                    (void *)(long)i);
 27   register_cpu_notifier(&rcu_nb);
 28 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsection}
\stepcounter{subsubsection}
{\newpage\clearpage
\lthtmlfigureA{figure14996}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 static void
  2 rcu_init_percpu_data(int cpu, struct rcu_state *rsp)
  3 {
  4   unsigned long flags;
  5   int i;
  6   long lastcomp;
  7   unsigned long mask;
  8   struct rcu_data *rdp = rsp->rda[cpu];
  9   struct rcu_node *rnp = rcu_get_root(rsp);
 10
 11   spin_lock_irqsave(&rnp->lock, flags);
 12   lastcomp = rsp->completed;
 13   rdp->completed = lastcomp;
 14   rdp->gpnum = lastcomp;
 15   rdp->passed_quiesc = 0;
 16   rdp->qs_pending = 1;
 17   rdp->beenonline = 1;
 18   rdp->passed_quiesc_completed = lastcomp - 1;
 19   rdp->grpmask = 1UL << (cpu - rdp->mynode->grplo);
 20   rdp->nxtlist = NULL;
 21   for (i = 0; i < RCU_NEXT_SIZE; i++)
 22     rdp->nxttail[i] = &rdp->nxtlist;
 23   rdp->qlen = 0;
 24   rdp->blimit = blimit;
 25 #ifdef CONFIG_NO_HZ
 26   rdp->dynticks = &per_cpu(rcu_dynticks, cpu);
 27 #endif /* #ifdef CONFIG_NO_HZ */
 28   rdp->cpu = cpu;
 29   spin_unlock(&rnp->lock);
 30   spin_lock(&rsp->onofflock);
 31   rnp = rdp->mynode;
 32   mask = rdp->grpmask;
 33   do {
 34     spin_lock(&rnp->lock);
 35     rnp->qsmaskinit |= mask;
 36     mask = rnp->grpmask;
 37     spin_unlock(&rnp->lock);
 38     rnp = rnp->parent;
 39   } while (rnp != NULL && !(rnp->qsmaskinit & mask));
 40   spin_unlock(&rsp->onofflock);
 41   cpu_quiet(cpu, rsp, rdp, lastcomp);
 42   local_irq_restore(flags);
 43 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsubsection}
{\newpage\clearpage
\lthtmlfigureA{figure15031}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 static void __cpuinit rcu_online_cpu(int cpu)
  2 {
  3 #ifdef CONFIG_NO_HZ
  4   struct rcu_dynticks *rdtp;
  5
  6   rdtp = &per_cpu(rcu_dynticks, cpu);
  7   rdtp->dynticks_nesting = 1;
  8   rdtp->dynticks |= 1;
  9   rdtp->dynticks_nmi = (rdtp->dynticks_nmi + 1) & ~0x1;
 10 #endif /* #ifdef CONFIG_NO_HZ */
 11   rcu_init_percpu_data(cpu, &rcu_state);
 12   rcu_init_percpu_data(cpu, &rcu_bh_state);
 13   open_softirq(RCU_SOFTIRQ, rcu_process_callbacks);
 14 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsubsection}
{\newpage\clearpage
\lthtmlfigureA{figure15051}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 static void
  2 __rcu_offline_cpu(int cpu, struct rcu_state *rsp)
  3 {
  4   int i;
  5   unsigned long flags;
  6   long lastcomp;
  7   unsigned long mask;
  8   struct rcu_data *rdp = rsp->rda[cpu];
  9   struct rcu_data *rdp_me;
 10   struct rcu_node *rnp;
 11
 12   spin_lock_irqsave(&rsp->onofflock, flags);
 13   rnp = rdp->mynode;
 14   mask = rdp->grpmask;
 15   do {
 16     spin_lock(&rnp->lock);
 17     rnp->qsmaskinit &= ~mask;
 18     if (rnp->qsmaskinit != 0) {
 19       spin_unlock(&rnp->lock);
 20       break;
 21     }
 22     mask = rnp->grpmask;
 23     spin_unlock(&rnp->lock);
 24     rnp = rnp->parent;
 25   } while (rnp != NULL);
 26   lastcomp = rsp->completed;
 27   spin_unlock(&rsp->onofflock);
 28   cpu_quiet(cpu, rsp, rdp, lastcomp);
 29   rdp_me = rsp->rda[smp_processor_id()];
 30   if (rdp->nxtlist != NULL) {
 31     *rdp_me->nxttail[RCU_NEXT_TAIL] = rdp->nxtlist;
 32     rdp_me->nxttail[RCU_NEXT_TAIL] =
 33         rdp->nxttail[RCU_NEXT_TAIL];
 34     rdp->nxtlist = NULL;
 35     for (i = 0; i < RCU_NEXT_SIZE; i++)
 36       rdp->nxttail[i] = &rdp->nxtlist;
 37     rdp_me->qlen += rdp->qlen;
 38     rdp->qlen = 0;
 39   }
 40   local_irq_restore(flags);
 41 }
 42
 43 static void rcu_offline_cpu(int cpu)
 44 {
 45   __rcu_offline_cpu(cpu, &rcu_state);
 46   __rcu_offline_cpu(cpu, &rcu_bh_state);
 47 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsection}
{\newpage\clearpage
\lthtmlfigureA{figure15120}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 long rcu_batches_completed(void)
  2 {
  3   return rcu_state.completed;
  4 }
  5
  6 long rcu_batches_completed_bh(void)
  7 {
  8   return rcu_bh_state.completed;
  9 }
 10
 11 static int
 12 cpu_has_callbacks_ready_to_invoke(struct rcu_data *rdp)
 13 {
 14   return &rdp->nxtlist != rdp->nxttail[RCU_DONE_TAIL];
 15 }
 16
 17 static int
 18 cpu_needs_another_gp(struct rcu_state *rsp,
 19                      struct rcu_data *rdp)
 20 {
 21   return *rdp->nxttail[RCU_DONE_TAIL] &&
 22          ACCESS_ONCE(rsp->completed) ==
 23          ACCESS_ONCE(rsp->gpnum);
 24 }
 25
 26 static struct rcu_node
 27 *rcu_get_root(struct rcu_state *rsp)
 28 {
 29   return &rsp->node[0];
 30 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsection}
\stepcounter{subsubsection}
{\newpage\clearpage
\lthtmlfigureA{figure15147}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 static void note_new_gpnum(struct rcu_state *rsp,
  2                            struct rcu_data *rdp)
  3 {
  4   rdp->qs_pending = 1;
  5   rdp->passed_quiesc = 0;
  6   rdp->gpnum = rsp->gpnum;
  7   rdp->n_rcu_pending_force_qs = rdp->n_rcu_pending +
  8               RCU_JIFFIES_TILL_FORCE_QS;
  9 }
 10
 11 static int
 12 check_for_new_grace_period(struct rcu_state *rsp,
 13                            struct rcu_data *rdp)
 14 {
 15   unsigned long flags;
 16   int ret = 0;
 17
 18   local_irq_save(flags);
 19   if (rdp->gpnum != rsp->gpnum) {
 20     note_new_gpnum(rsp, rdp);
 21     ret = 1;
 22   }
 23   local_irq_restore(flags);
 24   return ret;
 25 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsubsection}
{\newpage\clearpage
\lthtmlfigureA{figure15172}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 static void
  2 rcu_process_gp_end(struct rcu_state *rsp,
  3                    struct rcu_data *rdp)
  4 {
  5   long completed_snap;
  6   unsigned long flags;
  7
  8   local_irq_save(flags);
  9   completed_snap = ACCESS_ONCE(rsp->completed);
 10   if (rdp->completed != completed_snap) {
 11     rdp->nxttail[RCU_DONE_TAIL] =
 12         rdp->nxttail[RCU_WAIT_TAIL];
 13     rdp->nxttail[RCU_WAIT_TAIL] =
 14         rdp->nxttail[RCU_NEXT_READY_TAIL];
 15     rdp->nxttail[RCU_NEXT_READY_TAIL] =
 16         rdp->nxttail[RCU_NEXT_TAIL];
 17     rdp->completed = completed_snap;
 18   }
 19   local_irq_restore(flags);
 20 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap16247}%
\resizebox{3in}{!}{\includegraphics{appendix/rcuimpl/AdvanceRCUCallbacks}}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsubsection}
{\newpage\clearpage
\lthtmlfigureA{figure15201}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 static void
  2 rcu_start_gp(struct rcu_state *rsp, unsigned long flags)
  3   __releases(rcu_get_root(rsp)->lock)
  4 {
  5   struct rcu_data *rdp = rsp->rda[smp_processor_id()];
  6   struct rcu_node *rnp = rcu_get_root(rsp);
  7   struct rcu_node *rnp_cur;
  8   struct rcu_node *rnp_end;
  9
 10   if (!cpu_needs_another_gp(rsp, rdp)) {
 11     spin_unlock_irqrestore(&rnp->lock, flags);
 12     return;
 13   }
 14   rsp->gpnum++;
 15   rsp->signaled = RCU_GP_INIT;
 16   rsp->jiffies_force_qs = jiffies +
 17       RCU_JIFFIES_TILL_FORCE_QS;
 18   rdp->n_rcu_pending_force_qs = rdp->n_rcu_pending +
 19       RCU_JIFFIES_TILL_FORCE_QS;
 20   record_gp_stall_check_time(rsp);
 21   dyntick_record_completed(rsp, rsp->completed - 1);
 22   note_new_gpnum(rsp, rdp);
 23   rdp->nxttail[RCU_NEXT_READY_TAIL] =
 24       rdp->nxttail[RCU_NEXT_TAIL];
 25   rdp->nxttail[RCU_WAIT_TAIL] =
 26       rdp->nxttail[RCU_NEXT_TAIL];
 27   if (NUM_RCU_NODES == 1) {
 28     rnp->qsmask = rnp->qsmaskinit;
 29     spin_unlock_irqrestore(&rnp->lock, flags);
 30     return;
 31   }
 32   spin_unlock(&rnp->lock);
 33   spin_lock(&rsp->onofflock);
 34   rnp_end = rsp->level[NUM_RCU_LVLS - 1];
 35   rnp_cur = &rsp->node[0];
 36   for (; rnp_cur < rnp_end; rnp_cur++)
 37     rnp_cur->qsmask = rnp_cur->qsmaskinit;
 38   rnp_end = &rsp->node[NUM_RCU_NODES];
 39   rnp_cur = rsp->level[NUM_RCU_LVLS - 1];
 40   for (; rnp_cur < rnp_end; rnp_cur++) {
 41     spin_lock(&rnp_cur->lock);
 42     rnp_cur->qsmask = rnp_cur->qsmaskinit;
 43     spin_unlock(&rnp_cur->lock);
 44   }
 45   rsp->signaled = RCU_SIGNAL_INIT;
 46   spin_unlock_irqrestore(&rsp->onofflock, flags);
 47 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsubsection}
{\newpage\clearpage
\lthtmlfigureA{figure15281}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 void rcu_qsctr_inc(int cpu)
  2 {
  3   struct rcu_data *rdp = &per_cpu(rcu_data, cpu);
  4   rdp->passed_quiesc = 1;
  5   rdp->passed_quiesc_completed = rdp->completed;
  6 }
  7
  8 void rcu_bh_qsctr_inc(int cpu)
  9 {
 10   struct rcu_data *rdp = &per_cpu(rcu_bh_data, cpu);
 11   rdp->passed_quiesc = 1;
 12   rdp->passed_quiesc_completed = rdp->completed;
 13 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlfigureA{figure15300}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 static void
  2 rcu_check_quiescent_state(struct rcu_state *rsp,
  3                           struct rcu_data *rdp)
  4 {
  5   if (check_for_new_grace_period(rsp, rdp))
  6     return;
  7   if (!rdp->qs_pending)
  8     return;
  9   if (!rdp->passed_quiesc)
 10     return;
 11   cpu_quiet(rdp->cpu, rsp, rdp,
 12             rdp->passed_quiesc_completed);
 13 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlfigureA{figure15317}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 static void
  2 cpu_quiet(int cpu, struct rcu_state *rsp,
  3           struct rcu_data *rdp, long lastcomp)
  4 {
  5   unsigned long flags;
  6   unsigned long mask;
  7   struct rcu_node *rnp;
  8
  9   rnp = rdp->mynode;
 10   spin_lock_irqsave(&rnp->lock, flags);
 11   if (lastcomp != ACCESS_ONCE(rsp->completed)) {
 12     rdp->passed_quiesc = 0;
 13     spin_unlock_irqrestore(&rnp->lock, flags);
 14     return;
 15   }
 16   mask = rdp->grpmask;
 17   if ((rnp->qsmask & mask) == 0) {
 18     spin_unlock_irqrestore(&rnp->lock, flags);
 19   } else {
 20     rdp->qs_pending = 0;
 21     rdp = rsp->rda[smp_processor_id()];
 22     rdp->nxttail[RCU_NEXT_READY_TAIL] =
 23         rdp->nxttail[RCU_NEXT_TAIL];
 24     cpu_quiet_msk(mask, rsp, rnp, flags);
 25   }
 26 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlfigureA{figure15336}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 static void
  2 cpu_quiet_msk(unsigned long mask, struct rcu_state *rsp,
  3               struct rcu_node *rnp, unsigned long flags)
  4   __releases(rnp->lock)
  5 {
  6   for (;;) {
  7     if (!(rnp->qsmask & mask)) {
  8       spin_unlock_irqrestore(&rnp->lock, flags);
  9       return;
 10     }
 11     rnp->qsmask &= ~mask;
 12     if (rnp->qsmask != 0) {
 13       spin_unlock_irqrestore(&rnp->lock, flags);
 14       return;
 15     }
 16     mask = rnp->grpmask;
 17     if (rnp->parent == NULL) {
 18       break;
 19     }
 20     spin_unlock_irqrestore(&rnp->lock, flags);
 21     rnp = rnp->parent;
 22     spin_lock_irqsave(&rnp->lock, flags);
 23   }
 24   rsp->completed = rsp->gpnum;
 25   rcu_process_gp_end(rsp, rsp->rda[smp_processor_id()]);
 26   rcu_start_gp(rsp, flags);
 27 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap16365}%
\resizebox{6in}{!}{\includegraphics{appendix/rcuimpl/RCUTreeQSScan}}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlfigureA{figure15384}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 static void rcu_do_batch(struct rcu_data *rdp)
  2 {
  3   unsigned long flags;
  4   struct rcu_head *next, *list, **tail;
  5   int count;
  6
  7   if (!cpu_has_callbacks_ready_to_invoke(rdp))
  8     return;
  9   local_irq_save(flags);
 10   list = rdp->nxtlist;
 11   rdp->nxtlist = *rdp->nxttail[RCU_DONE_TAIL];
 12   *rdp->nxttail[RCU_DONE_TAIL] = NULL;
 13   tail = rdp->nxttail[RCU_DONE_TAIL];
 14   for (count = RCU_NEXT_SIZE - 1; count >= 0; count--)
 15     if (rdp->nxttail[count] ==
 16         rdp->nxttail[RCU_DONE_TAIL])
 17       rdp->nxttail[count] = &rdp->nxtlist;
 18   local_irq_restore(flags);
 19   count = 0;
 20   while (list) {
 21     next = list->next;
 22     prefetch(next);
 23     list->func(list);
 24     list = next;
 25     if (++count >= rdp->blimit)
 26       break;
 27   }
 28   local_irq_save(flags);
 29   rdp->qlen -= count;
 30   if (list != NULL) {
 31     *tail = rdp->nxtlist;
 32     rdp->nxtlist = list;
 33     for (count = 0; count < RCU_NEXT_SIZE; count++)
 34       if (&rdp->nxtlist == rdp->nxttail[count])
 35         rdp->nxttail[count] = tail;
 36       else
 37         break;
 38   }
 39   if (rdp->blimit == LONG_MAX && rdp->qlen <= qlowmark)
 40     rdp->blimit = blimit;
 41   local_irq_restore(flags);
 42   if (cpu_has_callbacks_ready_to_invoke(rdp))
 43     raise_softirq(RCU_SOFTIRQ);
 44 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsection}
\stepcounter{subsubsection}
{\newpage\clearpage
\lthtmlfigureA{figure15412}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 void rcu_enter_nohz(void)
  2 {
  3   unsigned long flags;
  4   struct rcu_dynticks *rdtp;
  5
  6   smp_mb();
  7   local_irq_save(flags);
  8   rdtp = &__get_cpu_var(rcu_dynticks);
  9   rdtp->dynticks++;
 10   rdtp->dynticks_nesting--;
 11   local_irq_restore(flags);
 12 }
 13
 14 void rcu_exit_nohz(void)
 15 {
 16   unsigned long flags;
 17   struct rcu_dynticks *rdtp;
 18
 19   local_irq_save(flags);
 20   rdtp = &__get_cpu_var(rcu_dynticks);
 21   rdtp->dynticks++;
 22   rdtp->dynticks_nesting++;
 23   local_irq_restore(flags);
 24   smp_mb();
 25 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsubsection}
{\newpage\clearpage
\lthtmlfigureA{figure15433}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 void rcu_nmi_enter(void)
  2 {
  3   struct rcu_dynticks *rdtp;
  4
  5   rdtp = &__get_cpu_var(rcu_dynticks);
  6   if (rdtp->dynticks & 0x1)
  7     return;
  8   rdtp->dynticks_nmi++;
  9   smp_mb();
 10 }
 11
 12 void rcu_nmi_exit(void)
 13 {
 14   struct rcu_dynticks *rdtp;
 15
 16   rdtp = &__get_cpu_var(rcu_dynticks);
 17   if (rdtp->dynticks & 0x1)
 18     return;
 19   smp_mb();
 20   rdtp->dynticks_nmi++;\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsubsection}
{\newpage\clearpage
\lthtmlfigureA{figure15454}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 void rcu_irq_enter(void)
  2 {
  3   struct rcu_dynticks *rdtp;
  4
  5   rdtp = &__get_cpu_var(rcu_dynticks);
  6   if (rdtp->dynticks_nesting++)
  7     return;
  8   rdtp->dynticks++;
  9   smp_mb();
 10 }
 11
 12 void rcu_irq_exit(void)
 13 {
 14   struct rcu_dynticks *rdtp;
 15
 16   rdtp = &__get_cpu_var(rcu_dynticks);
 17   if (--rdtp->dynticks_nesting)
 18     return;
 19   smp_mb();
 20   rdtp->dynticks++;
 21   if (__get_cpu_var(rcu_data).nxtlist ||
 22       __get_cpu_var(rcu_bh_data).nxtlist)
 23     set_need_resched();
 24 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsubsection}
{\newpage\clearpage
\lthtmlfigureA{figure15479}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 static int
  2 dyntick_save_progress_counter(struct rcu_data *rdp)
  3 {
  4   int ret;
  5   int snap;
  6   int snap_nmi;
  7
  8   snap = rdp->dynticks->dynticks;
  9   snap_nmi = rdp->dynticks->dynticks_nmi;
 10   smp_mb();
 11   rdp->dynticks_snap = snap;
 12   rdp->dynticks_nmi_snap = snap_nmi;
 13   ret = ((snap & 0x1) == 0) && ((snap_nmi & 0x1) == 0);
 14   if (ret)
 15     rdp->dynticks_fqs++;
 16   return ret;
 17 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlfigureA{figure15505}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 static int
  2 rcu_implicit_dynticks_qs(struct rcu_data *rdp)
  3 {
  4   long curr;
  5   long curr_nmi;
  6   long snap;
  7   long snap_nmi;
  8
  9   curr = rdp->dynticks->dynticks;
 10   snap = rdp->dynticks_snap;
 11   curr_nmi = rdp->dynticks->dynticks_nmi;
 12   snap_nmi = rdp->dynticks_nmi_snap;
 13   smp_mb();
 14   if ((curr != snap || (curr & 0x1) == 0) &&
 15       (curr_nmi != snap_nmi || (curr_nmi & 0x1) == 0)) {
 16     rdp->dynticks_fqs++;
 17     return 1;
 18   }
 19   return rcu_implicit_offline_qs(rdp);
 20 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsection}
\stepcounter{subsubsection}
{\newpage\clearpage
\lthtmlfigureA{figure15545}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 static void
  2 dyntick_record_completed(struct rcu_state *rsp,
  3                          long comp)
  4 {
  5   rsp->dynticks_completed = comp;
  6 }
  7
  8 static long
  9 dyntick_recall_completed(struct rcu_state *rsp)
 10 {
 11   return rsp->dynticks_completed;
 12 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsubsection}
{\newpage\clearpage
\lthtmlfigureA{figure15564}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 static int rcu_implicit_offline_qs(struct rcu_data *rdp)
  2 {
  3   if (cpu_is_offline(rdp->cpu)) {
  4     rdp->offline_fqs++;
  5     return 1;
  6   }
  7   if (rdp->cpu != smp_processor_id())
  8     smp_send_reschedule(rdp->cpu);
  9   else
 10     set_need_resched();
 11   rdp->resched_ipi++;
 12   return 0;
 13 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsubsection}
{\newpage\clearpage
\lthtmlfigureA{figure15577}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 static int
  2 rcu_process_dyntick(struct rcu_state *rsp,
  3                     long lastcomp,
  4                     int (*f)(struct rcu_data *))
  5 {
  6   unsigned long bit;
  7   int cpu;
  8   unsigned long flags;
  9   unsigned long mask;
 10   struct rcu_node *rnp_cur;
 11   struct rcu_node *rnp_end;
 12
 13   rnp_cur = rsp->level[NUM_RCU_LVLS - 1];
 14   rnp_end = &rsp->node[NUM_RCU_NODES];
 15   for (; rnp_cur < rnp_end; rnp_cur++) {
 16     mask = 0;
 17     spin_lock_irqsave(&rnp_cur->lock, flags);
 18     if (rsp->completed != lastcomp) {
 19       spin_unlock_irqrestore(&rnp_cur->lock, flags);
 20       return 1;
 21     }
 22     if (rnp_cur->qsmask == 0) {
 23       spin_unlock_irqrestore(&rnp_cur->lock, flags);
 24       continue;
 25     }
 26     cpu = rnp_cur->grplo;
 27     bit = 1;
 28     for (; cpu <= rnp_cur->grphi; cpu++, bit <<= 1) {
 29       if ((rnp_cur->qsmask & bit) != 0 &&
 30           f(rsp->rda[cpu]))
 31         mask |= bit;
 32     }
 33     if (mask != 0 && rsp->completed == lastcomp) {
 34       cpu_quiet_msk(mask, rsp, rnp_cur, flags);
 35       continue;
 36     }
 37     spin_unlock_irqrestore(&rnp_cur->lock, flags);
 38   }
 39   return 0;
 40 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap16521}%
\resizebox{6in}{!}{\includegraphics{appendix/rcuimpl/RCUTreeLeafScan}}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsubsection}
{\newpage\clearpage
\lthtmlfigureA{figure15622}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 static void
  2 force_quiescent_state(struct rcu_state *rsp, int relaxed)
  3 {
  4   unsigned long flags;
  5   long lastcomp;
  6   struct rcu_data *rdp = rsp->rda[smp_processor_id()];
  7   struct rcu_node *rnp = rcu_get_root(rsp);
  8   u8 signaled;
  9
 10   if (ACCESS_ONCE(rsp->completed) ==
 11       ACCESS_ONCE(rsp->gpnum))
 12     return;
 13   if (!spin_trylock_irqsave(&rsp->fqslock, flags)) {
 14     rsp->n_force_qs_lh++;
 15     return;
 16   }
 17   if (relaxed &&
 18       (long)(rsp->jiffies_force_qs - jiffies) >= 0 &&
 19       (rdp->n_rcu_pending_force_qs -
 20        rdp->n_rcu_pending) >= 0)
 21     goto unlock_ret;
 22   rsp->n_force_qs++;
 23   spin_lock(&rnp->lock);
 24   lastcomp = rsp->completed;
 25   signaled = rsp->signaled;
 26   rsp->jiffies_force_qs =
 27     jiffies + RCU_JIFFIES_TILL_FORCE_QS;
 28   rdp->n_rcu_pending_force_qs =
 29     rdp->n_rcu_pending +
 30     RCU_JIFFIES_TILL_FORCE_QS;
 31   if (lastcomp == rsp->gpnum) {
 32     rsp->n_force_qs_ngp++;
 33     spin_unlock(&rnp->lock);
 34     goto unlock_ret;
 35   }
 36   spin_unlock(&rnp->lock);
 37   switch (signaled) {
 38   case RCU_GP_INIT:
 39     break;
 40   case RCU_SAVE_DYNTICK:
 41     if (RCU_SIGNAL_INIT != RCU_SAVE_DYNTICK)
 42       break;
 43     if (rcu_process_dyntick(rsp, lastcomp,
 44           dyntick_save_progress_counter))
 45       goto unlock_ret;
 46     spin_lock(&rnp->lock);
 47     if (lastcomp == rsp->completed) {
 48       rsp->signaled = RCU_FORCE_QS;
 49       dyntick_record_completed(rsp, lastcomp);
 50     }
 51     spin_unlock(&rnp->lock);
 52     break;
 53   case RCU_FORCE_QS:
 54     if (rcu_process_dyntick(rsp,
 55           dyntick_recall_completed(rsp),
 56           rcu_implicit_dynticks_qs))
 57       goto unlock_ret;
 58     break;
 59   }
 60 unlock_ret:
 61   spin_unlock_irqrestore(&rsp->fqslock, flags);
 62 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsection}
{\newpage\clearpage
\lthtmlfigureA{figure15680}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 static void
  2 record_gp_stall_check_time(struct rcu_state *rsp)
  3 {
  4   rsp->gp_start = jiffies;
  5   rsp->jiffies_stall =
  6       jiffies + RCU_SECONDS_TILL_STALL_CHECK;
  7 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlfigureA{figure15688}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 static void
  2 check_cpu_stall(struct rcu_state *rsp,
  3                 struct rcu_data *rdp)
  4 {
  5   long delta;
  6   struct rcu_node *rnp;
  7
  8   delta = jiffies - rsp->jiffies_stall;
  9   rnp = rdp->mynode;
 10   if ((rnp->qsmask & rdp->grpmask) && delta >= 0) {
 11     print_cpu_stall(rsp);
 12   } else if (rsp->gpnum != rsp->completed &&
 13        delta >= RCU_STALL_RAT_DELAY) {
 14     print_other_cpu_stall(rsp);
 15   }
 16 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlfigureA{figure15704}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 static void print_cpu_stall(struct rcu_state *rsp)
  2 {
  3   unsigned long flags;
  4   struct rcu_node *rnp = rcu_get_root(rsp);
  5
  6   printk(KERN_ERR
  7          "INFO: RCU detected CPU %d stall "
  8          "(t=%lu jiffies)\n",
  9     smp_processor_id(),
 10     jiffies - rsp->gp_start);
 11   dump_stack();
 12   spin_lock_irqsave(&rnp->lock, flags);
 13   if ((long)(jiffies - rsp->jiffies_stall) >= 0)
 14     rsp->jiffies_stall =
 15       jiffies + RCU_SECONDS_TILL_STALL_RECHECK;
 16   spin_unlock_irqrestore(&rnp->lock, flags);
 17   set_need_resched();
 18 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlfigureA{figure15715}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 static void print_other_cpu_stall(struct rcu_state *rsp)
  2 {
  3   int cpu;
  4   long delta;
  5   unsigned long flags;
  6   struct rcu_node *rnp = rcu_get_root(rsp);
  7   struct rcu_node *rnp_cur;
  8   struct rcu_node *rnp_end;
  9
 10   rnp_cur = rsp->level[NUM_RCU_LVLS - 1];
 11   rnp_end = &rsp->node[NUM_RCU_NODES];
 12   spin_lock_irqsave(&rnp->lock, flags);
 13   delta = jiffies - rsp->jiffies_stall;
 14   if (delta < RCU_STALL_RAT_DELAY ||
 15       rsp->gpnum == rsp->completed) {
 16     spin_unlock_irqrestore(&rnp->lock, flags);
 17     return;
 18   }
 19   rsp->jiffies_stall = jiffies +
 20       RCU_SECONDS_TILL_STALL_RECHECK;
 21   spin_unlock_irqrestore(&rnp->lock, flags);
 22   printk(KERN_ERR "INFO: RCU detected CPU stalls:");
 23   for (; rnp_cur < rnp_end; rnp_cur++) {
 24     if (rnp_cur->qsmask == 0)
 25       continue;
 26     cpu = 0;
 27     for (; cpu <= rnp_cur->grphi - rnp_cur->grplo; cpu++)
 28       if (rnp_cur->qsmask & (1UL << cpu))
 29         printk(" %d", rnp_cur->grplo + cpu);
 30   }
 31   printk(" (detected by %d, t=%ld jiffies)\n",
 32          smp_processor_id(),
 33          (long)(jiffies - rsp->gp_start));
 34   force_quiescent_state(rsp, 0);
 35 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsection}
\stepcounter{section}
\stepcounter{subsection}
{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap17165}%
\resizebox{3in}{!}{\includegraphics{appendix/rcuimpl/GracePeriodBad}}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap17175}%
\resizebox{3in}{!}{\includegraphics{appendix/rcuimpl/GracePeriodGood}}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsection}
\stepcounter{subsubsection}
{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap17189}%
\resizebox{3in}{!}{\includegraphics{appendix/rcuimpl/RCUpreemptListsCompare}}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap17199}%
\resizebox{3in}{!}{\includegraphics{appendix/rcuimpl/RCUpreemptCounterFlip}}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsubsection}
\stepcounter{paragraph}
\stepcounter{paragraph}
{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap17239}%
\resizebox{1.5in}{!}{\includegraphics{appendix/rcuimpl/RCUpreemptLists}}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{paragraph}
\stepcounter{paragraph}
\stepcounter{paragraph}
\stepcounter{paragraph}
\stepcounter{subsubsection}
\stepcounter{paragraph}
{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap17281}%
\resizebox{3in}{!}{\includegraphics{appendix/rcuimpl/RCUpreemptStates}}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap17289}%
\resizebox{3in}{!}{\includegraphics{appendix/rcuimpl/RCUpreemptTimeline}}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{paragraph}
{\newpage\clearpage
\lthtmlfigureA{figure16854}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 void rcu_check_callbacks(int cpu, int user)
  2 {
  3   unsigned long flags;
  4   struct rcu_data *rdp = RCU_DATA_CPU(cpu);
  5
  6   rcu_check_mb(cpu);
  7   if (rcu_ctrlblk.completed == rdp->completed)
  8     rcu_try_flip();
  9   spin_lock_irqsave(&rdp->lock, flags);
 10   RCU_TRACE_RDP(rcupreempt_trace_check_callbacks, rdp);
 11   __rcu_advance_callbacks(rdp);
 12   spin_unlock_irqrestore(&rdp->lock, flags);
 13 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlfigureA{figure16866}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 static void rcu_check_mb(int cpu)
  2 {
  3   if (per_cpu(rcu_mb_flag, cpu) == rcu_mb_needed) {
  4     smp_mb();
  5     per_cpu(rcu_mb_flag, cpu) = rcu_mb_done;
  6   }
  7 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlfigureA{figure16875}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 static void rcu_try_flip(void)
  2 {
  3   unsigned long flags;
  4
  5   RCU_TRACE_ME(rcupreempt_trace_try_flip_1);
  6   if (!spin_trylock_irqsave(&rcu_ctrlblk.fliplock, flags)) {
  7     RCU_TRACE_ME(rcupreempt_trace_try_flip_e1);
  8     return;
  9   }
 10   switch (rcu_try_flip_state) {
 11   case rcu_try_flip_idle_state:
 12     if (rcu_try_flip_idle())
 13       rcu_try_flip_state = rcu_try_flip_waitack_state;
 14     break;
 15   case rcu_try_flip_waitack_state:
 16     if (rcu_try_flip_waitack())
 17       rcu_try_flip_state = rcu_try_flip_waitzero_state;
 18     break;
 19   case rcu_try_flip_waitzero_state:
 20     if (rcu_try_flip_waitzero())
 21       rcu_try_flip_state = rcu_try_flip_waitmb_state;
 22     break;
 23   case rcu_try_flip_waitmb_state:
 24     if (rcu_try_flip_waitmb())
 25       rcu_try_flip_state = rcu_try_flip_idle_state;
 26   }
 27   spin_unlock_irqrestore(&rcu_ctrlblk.fliplock, flags);
 28 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlfigureA{figure16884}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 static int rcu_try_flip_idle(void)
  2 {
  3   int cpu;
  4
  5   RCU_TRACE_ME(rcupreempt_trace_try_flip_i1);
  6   if (!rcu_pending(smp_processor_id())) {
  7     RCU_TRACE_ME(rcupreempt_trace_try_flip_ie1);
  8     return 0;
  9   }
 10   RCU_TRACE_ME(rcupreempt_trace_try_flip_g1);
 11   rcu_ctrlblk.completed++;
 12   smp_mb();
 13   for_each_cpu_mask(cpu, rcu_cpu_online_map)
 14     per_cpu(rcu_flip_flag, cpu) = rcu_flipped;
 15   return 1;
 16 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlfigureA{figure16893}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 static int rcu_try_flip_waitack(void)
  2 {
  3   int cpu;
  4
  5   RCU_TRACE_ME(rcupreempt_trace_try_flip_a1);
  6   for_each_cpu_mask(cpu, rcu_cpu_online_map)
  7     if (per_cpu(rcu_flip_flag, cpu) != rcu_flip_seen) {
  8       RCU_TRACE_ME(rcupreempt_trace_try_flip_ae1);
  9       return 0;
 10     }
 11   smp_mb();
 12   RCU_TRACE_ME(rcupreempt_trace_try_flip_a2);
 13   return 1;
 14 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlfigureA{figure16904}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 static int rcu_try_flip_waitzero(void)
  2 {
  3   int cpu;
  4   int lastidx = !(rcu_ctrlblk.completed & 0x1);
  5   int sum = 0;
  6
  7   RCU_TRACE_ME(rcupreempt_trace_try_flip_z1);
  8   for_each_possible_cpu(cpu)
  9     sum += per_cpu(rcu_flipctr, cpu)[lastidx];
 10   if (sum != 0) {
 11     RCU_TRACE_ME(rcupreempt_trace_try_flip_ze1);
 12     return 0;
 13   }
 14   smp_mb();
 15   for_each_cpu_mask(cpu, rcu_cpu_online_map)
 16     per_cpu(rcu_mb_flag, cpu) = rcu_mb_needed;
 17   RCU_TRACE_ME(rcupreempt_trace_try_flip_z2);
 18   return 1;
 19 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlfigureA{figure16913}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 static int rcu_try_flip_waitmb(void)
  2 {
  3   int cpu;
  4
  5   RCU_TRACE_ME(rcupreempt_trace_try_flip_m1);
  6   for_each_cpu_mask(cpu, rcu_cpu_online_map)
  7     if (per_cpu(rcu_mb_flag, cpu) != rcu_mb_done) {
  8       RCU_TRACE_ME(rcupreempt_trace_try_flip_me1);
  9       return 0;
 10     }
 11   smp_mb();
 12   RCU_TRACE_ME(rcupreempt_trace_try_flip_m2);
 13   return 1;
 14 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlfigureA{figure16921}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 static void __rcu_advance_callbacks(struct rcu_data *rdp)
  2 {
  3   int cpu;
  4   int i;
  5   int wlc = 0;
  6
  7   if (rdp->completed != rcu_ctrlblk.completed) {
  8     if (rdp->waitlist[GP_STAGES - 1] != NULL) {
  9       *rdp->donetail = rdp->waitlist[GP_STAGES - 1];
 10       rdp->donetail = rdp->waittail[GP_STAGES - 1];
 11       RCU_TRACE_RDP(rcupreempt_trace_move2done, rdp);
 12     }
 13     for (i = GP_STAGES - 2; i >= 0; i--) {
 14       if (rdp->waitlist[i] != NULL) {
 15         rdp->waitlist[i + 1] = rdp->waitlist[i];
 16         rdp->waittail[i + 1] = rdp->waittail[i];
 17         wlc++;
 18       } else {
 19         rdp->waitlist[i + 1] = NULL;
 20         rdp->waittail[i + 1] =
 21           &rdp->waitlist[i + 1];
 22       }
 23     }
 24     if (rdp->nextlist != NULL) {
 25       rdp->waitlist[0] = rdp->nextlist;
 26       rdp->waittail[0] = rdp->nexttail;
 27       wlc++;
 28       rdp->nextlist = NULL;
 29       rdp->nexttail = &rdp->nextlist;
 30       RCU_TRACE_RDP(rcupreempt_trace_move2wait, rdp);
 31     } else {
 32       rdp->waitlist[0] = NULL;
 33       rdp->waittail[0] = &rdp->waitlist[0];
 34     }
 35     rdp->waitlistcount = wlc;
 36     rdp->completed = rcu_ctrlblk.completed;
 37   }
 38   cpu = raw_smp_processor_id();
 39   if (per_cpu(rcu_flip_flag, cpu) == rcu_flipped) {
 40     smp_mb();
 41     per_cpu(rcu_flip_flag, cpu) = rcu_flip_seen;
 42     smp_mb();
 43   }
 44 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsubsection}
\stepcounter{paragraph}
{\newpage\clearpage
\lthtmlfigureA{figure16940}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 void __rcu_read_lock(void)
  2 {
  3   int idx;
  4   struct task_struct *t = current;
  5   int nesting;
  6
  7   nesting = ACCESS_ONCE(t->rcu_read_lock_nesting);
  8   if (nesting != 0) {
  9     t->rcu_read_lock_nesting = nesting + 1;
 10   } else {
 11     unsigned long flags;
 12
 13     local_irq_save(flags);
 14     idx = ACCESS_ONCE(rcu_ctrlblk.completed) & 0x1;
 15     ACCESS_ONCE(__get_cpu_var(rcu_flipctr)[idx])++;
 16     ACCESS_ONCE(t->rcu_read_lock_nesting) = nesting + 1;
 17     ACCESS_ONCE(t->rcu_flipctr_idx) = idx;
 18     local_irq_restore(flags);
 19   }
 20 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{paragraph}
{\newpage\clearpage
\lthtmlfigureA{figure16989}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 void __rcu_read_unlock(void)
  2 {
  3   int idx;
  4   struct task_struct *t = current;
  5   int nesting;
  6
  7   nesting = ACCESS_ONCE(t->rcu_read_lock_nesting);
  8   if (nesting > 1) {
  9     t->rcu_read_lock_nesting = nesting - 1;
 10   } else {
 11     unsigned long flags;
 12
 13     local_irq_save(flags);
 14     idx = ACCESS_ONCE(t->rcu_flipctr_idx);
 15     ACCESS_ONCE(t->rcu_read_lock_nesting) = nesting - 1;
 16     ACCESS_ONCE(__get_cpu_var(rcu_flipctr)[idx])--;
 17     local_irq_restore(flags);
 18   }
 19 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{paragraph}
{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap17433}%
\resizebox{3in}{!}{\includegraphics{appendix/rcuimpl/RCUrt-MBwaste}}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap17441}%
\resizebox{3in}{!}{\includegraphics{appendix/rcuimpl/RCUrt-MBnowaste}}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsection}
\stepcounter{subsubsection}
\stepcounter{subsubsection}
{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap17463}%
\resizebox{3in}{!}{\includegraphics{appendix/rcuimpl/RCUpreemptValidation}}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsubsection}
\stepcounter{chapter}
\stepcounter{section}
\stepcounter{section}
{\newpage\clearpage
\lthtmlfigureA{figure17517}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 #define NUMPROCS 2
  2
  3 byte counter = 0;
  4 byte progress[NUMPROCS];
  5
  6 proctype incrementer(byte me)
  7 {
  8   int temp;
  9
 10   temp = counter;
 11   counter = temp + 1;
 12   progress[me] = 1;
 13 }
 14
 15 init {
 16   int i = 0;
 17   int sum = 0;
 18
 19   atomic {
 20     i = 0;
 21     do
 22     :: i < NUMPROCS ->
 23       progress[i] = 0;
 24       run incrementer(i);
 25       i++
 26     :: i >= NUMPROCS -> break
 27     od;
 28   }
 29   atomic {
 30     i = 0;
 31     sum = 0;
 32     do
 33     :: i < NUMPROCS ->
 34       sum = sum + progress[i];
 35       i++
 36     :: i >= NUMPROCS -> break
 37     od;
 38     assert(sum < NUMPROCS || counter == NUMPROCS)
 39   }
 40 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlfigureA{figure17537}%
\begin{figure}{ \scriptsize
\begin{verbatim}

pan: assertion violated ((sum<2)||(counter==2)) (at depth 20)
pan: wrote increment.spin.trail
(Spin Version 4.2.5 -- 2 April 2005)
Warning: Search not completed
        + Partial Order Reduction

Full statespace search for:
        never claim             - (none specified)
        assertion violations    +
        cycle checks            - (disabled by -DSAFETY)
        invalid end states      +

State-vector 40 byte, depth reached 22, errors: 1
      45 states, stored
      13 states, matched
      58 transitions (= stored+matched)
      51 atomic steps
hash conflicts: 0 (resolved)

2.622  memory usage (Mbyte)\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlfigureA{figurestar17553}%
\begin{figure*}{ \scriptsize
\begin{verbatim}

Starting :init: with pid 0
 1: proc 0 (:init:) line 20 "increment.spin" (state 1) [i = 0]
 2: proc 0 (:init:) line 22 "increment.spin" (state 2) [((i<2))]
 2: proc 0 (:init:) line 23 "increment.spin" (state 3) [progress[i] = 0]
Starting incrementer with pid 1
 3: proc 0 (:init:) line 24 "increment.spin" (state 4) [(run incrementer(i))]
 3: proc 0 (:init:) line 25 "increment.spin" (state 5) [i = (i+1)]
 4: proc 0 (:init:) line 22 "increment.spin" (state 2) [((i<2))]
 4: proc 0 (:init:) line 23 "increment.spin" (state 3) [progress[i] = 0]
Starting incrementer with pid 2
 5: proc 0 (:init:) line 24 "increment.spin" (state 4) [(run incrementer(i))]
 5: proc 0 (:init:) line 25 "increment.spin" (state 5) [i = (i+1)]
 6: proc 0 (:init:) line 26 "increment.spin" (state 6) [((i>=2))]
 7: proc 0 (:init:) line 21 "increment.spin" (state 10) [break]
 8: proc 2 (incrementer) line 10 "increment.spin" (state 1) [temp = counter]
 9: proc 1 (incrementer) line 10 "increment.spin" (state 1) [temp = counter]
10: proc 2 (incrementer) line 11 "increment.spin" (state 2) [counter = (temp+1)]
11: proc 2 (incrementer) line 12 "increment.spin" (state 3) [progress[me] = 1]
12: proc 2 terminates
13: proc 1 (incrementer) line 11 "increment.spin" (state 2) [counter = (temp+1)]
14: proc 1 (incrementer) line 12 "increment.spin" (state 3) [progress[me] = 1]
15: proc 1 terminates
16: proc 0 (:init:) line 30 "increment.spin" (state 12)	[i = 0]
16: proc 0 (:init:) line 31 "increment.spin" (state 13)	[sum = 0]
17: proc 0 (:init:) line 33 "increment.spin" (state 14)	[((i<2))]
17: proc 0 (:init:) line 34 "increment.spin" (state 15)	[sum = (sum+progress[i])]
17: proc 0 (:init:) line 35 "increment.spin" (state 16)	[i = (i+1)]
18: proc 0 (:init:) line 33 "increment.spin" (state 14)	[((i<2))]
18: proc 0 (:init:) line 34 "increment.spin" (state 15)	[sum = (sum+progress[i])]
18: proc 0 (:init:) line 35 "increment.spin" (state 16)	[i = (i+1)]
19: proc 0 (:init:) line 36 "increment.spin" (state 17)	[((i>=2))]
20: proc 0 (:init:) line 32 "increment.spin" (state 21)	[break]
spin: line  38 "increment.spin", Error: assertion violated
spin: text of failed assertion: assert(((sum<2)||(counter==2)))
 21:	proc  0 (:init:) line  38 "increment.spin" (state 22)	[assert(((sum<2)||(counter==2)))]
spin: trail ends after 21 steps
#processes: 1
                counter = 1
                progress[0] = 1
                progress[1] = 1
21: proc 0 (:init:) line 40 "increment.spin" (state 24) <valid end state>
3 processes created\end{verbatim}

}

\end{figure*}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{section}
{\newpage\clearpage
\lthtmlfigureA{figure17562}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 proctype incrementer(byte me)
  2 {
  3   int temp;
  4
  5   atomic {
  6     temp = counter;
  7     counter = temp + 1;
  8   }
  9   progress[me] = 1;
 10 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlfigureA{figure17568}%
\begin{figure}{ \scriptsize
\begin{verbatim}

(Spin Version 4.2.5 -- 2 April 2005)
        + Partial Order Reduction

Full statespace search for:
        never claim             - (none specified)
        assertion violations    +
        cycle checks            - (disabled by -DSAFETY)
        invalid end states      +

State-vector 40 byte, depth reached 20, errors: 0
      52 states, stored
      21 states, matched
      73 transitions (= stored+matched)
      66 atomic steps
hash conflicts: 0 (resolved)

2.622   memory usage (Mbyte)

unreached in proctype incrementer
        (0 of 5 states)
unreached in proctype :init:
        (0 of 24 states)\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsection}
\stepcounter{section}
\stepcounter{subsection}
\stepcounter{subsection}
{\newpage\clearpage
\lthtmlfigureA{figure17642}%
\begin{figure}{ % \scriptsize
\begin{verbatim}

  1 i = 0;
  2 sum = 0;
  3 do
  4 :: i < N_QRCU_READERS ->
  5   sum = sum + (readerstart[i] == 1 &&
  6     readerprogress[i] == 1);
  7   i++
  8 :: i >= N_QRCU_READERS ->
  9   assert(sum == 0);
 10   break
 11 od\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlfigureA{figure17648}%
\begin{figure}{ % \scriptsize
\begin{verbatim}

  1 atomic {
  2   i = 0;
  3   sum = 0;
  4   do
  5   :: i < N_QRCU_READERS ->
  6     sum = sum + (readerstart[i] == 1 &&
  7       readerprogress[i] == 1);
  8     i++
  9   :: i >= N_QRCU_READERS ->
 10     assert(sum == 0);
 11     break
 12   od
 13 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{section}
{\newpage\clearpage
\lthtmlfigureA{figure17661}%
\begin{figure}{ % \scriptsize
\begin{verbatim}

  1 #define spin_lock(mutex) \
  2   do \
  3   :: 1 -> atomic { \
  4       if \
  5       :: mutex == 0 -> \
  6         mutex = 1; \
  7         break \
  8       :: else -> skip \
  9       fi \
 10     } \
 11   od
 12
 13 #define spin_unlock(mutex) \
 14   mutex = 0\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlfigureA{figure17674}%
\begin{figure}{ % \scriptsize
\begin{verbatim}

  1 #include "lock.h"
  2
  3 #define N_LOCKERS 3
  4
  5 bit mutex = 0;
  6 bit havelock[N_LOCKERS];
  7 int sum;
  8
  9 proctype locker(byte me)
 10 {
 11   do
 12   :: 1 ->
 13     spin_lock(mutex);
 14     havelock[me] = 1;
 15     havelock[me] = 0;
 16     spin_unlock(mutex)
 17   od
 18 }
 19
 20 init {
 21   int i = 0;
 22   int j;
 23
 24 end:  do
 25   :: i < N_LOCKERS ->
 26     havelock[i] = 0;
 27     run locker(i);
 28     i++
 29   :: i >= N_LOCKERS ->
 30     sum = 0;
 31     j = 0;
 32     atomic {
 33       do
 34       :: j < N_LOCKERS ->
 35         sum = sum + havelock[j];
 36         j = j + 1
 37       :: j >= N_LOCKERS ->
 38         break
 39       od
 40     }
 41     assert(sum <= 1);
 42     break
 43   od
 44 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlfigureA{figure17691}%
\begin{figure}{ \scriptsize
\begin{verbatim}

(Spin Version 4.2.5 -- 2 April 2005)
        + Partial Order Reduction

Full statespace search for:
        never claim             - (none specified)
        assertion violations    +
        cycle checks            - (disabled by -DSAFETY)
        invalid end states      +

State-vector 40 byte, depth reached 357, errors: 0
     564 states, stored
     929 states, matched
    1493 transitions (= stored+matched)
     368 atomic steps
hash conflicts: 0 (resolved)

2.622   memory usage (Mbyte)

unreached in proctype locker
        line 18, state 20, "-end-"
        (1 of 20 states)
unreached in proctype :init:
        (0 of 22 states)\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{section}
{\newpage\clearpage
\lthtmlfigureA{figure17734}%
\begin{figure}{ % \scriptsize
\begin{verbatim}

  1 #include "lock.h"
  2
  3 #define N_QRCU_READERS 2
  4 #define N_QRCU_UPDATERS 2
  5
  6 bit idx = 0;
  7 byte ctr[2];
  8 byte readerprogress[N_QRCU_READERS];
  9 bit mutex = 0;\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlfigureA{figure17749}%
\begin{figure}{ % \scriptsize
\begin{verbatim}

  1 proctype qrcu_reader(byte me)
  2 {
  3   int myidx;
  4
  5   do
  6   :: 1 ->
  7     myidx = idx;
  8     atomic {
  9       if
 10       :: ctr[myidx] > 0 ->
 11         ctr[myidx]++;
 12         break
 13       :: else -> skip
 14       fi
 15     }
 16   od;
 17   readerprogress[me] = 1;
 18   readerprogress[me] = 2;
 19   atomic { ctr[myidx]-- }
 20 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlfigureA{figure17759}%
\begin{figure}{ % \scriptsize
\begin{verbatim}

  1 #define sum_unordered \
  2   atomic { \
  3     do \
  4     :: 1 -> \
  5       sum = ctr[0]; \
  6       i = 1; \
  7       break \
  8     :: 1 -> \
  9       sum = ctr[1]; \
 10       i = 0; \
 11       break \
 12     od; \
 13   } \
 14   sum = sum + ctr[i]\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlfigureA{figure17770}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 proctype qrcu_updater(byte me)
  2 {
  3   int i;
  4   byte readerstart[N_QRCU_READERS];
  5   int sum;
  6
  7   do
  8   :: 1 ->
  9
 10     /* Snapshot reader state. */
 11
 12     atomic {
 13       i = 0;
 14       do
 15       :: i < N_QRCU_READERS ->
 16         readerstart[i] = readerprogress[i];
 17         i++
 18       :: i >= N_QRCU_READERS ->
 19         break
 20       od
 21     }
 22
 23     sum_unordered;
 24     if
 25     :: sum <= 1 -> sum_unordered
 26     :: else -> skip
 27     fi;
 28     if
 29     :: sum > 1 ->
 30       spin_lock(mutex);
 31       atomic { ctr[!idx]++ }
 32       idx = !idx;
 33       atomic { ctr[!idx]-- }
 34       do
 35       :: ctr[!idx] > 0 -> skip
 36       :: ctr[!idx] == 0 -> break
 37       od;
 38       spin_unlock(mutex);
 39     :: else -> skip
 40     fi;
 41
 42     /* Verify reader progress. */
 43
 44     atomic {
 45       i = 0;
 46       sum = 0;
 47       do
 48       :: i < N_QRCU_READERS ->
 49         sum = sum + (readerstart[i] == 1 &&
 50                readerprogress[i] == 1);
 51         i++
 52       :: i >= N_QRCU_READERS ->
 53         assert(sum == 0);
 54         break
 55       od
 56     }
 57   od
 58 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlfigureA{figure17788}%
\begin{figure}{ % \scriptsize
\begin{verbatim}

  1 init {
  2   int i;
  3
  4   atomic {
  5     ctr[idx] = 1;
  6     ctr[!idx] = 0;
  7     i = 0;
  8     do
  9     :: i < N_QRCU_READERS ->
 10       readerprogress[i] = 0;
 11       run qrcu_reader(i);
 12       i++
 13     :: i >= N_QRCU_READERS -> break
 14     od;
 15     i = 0;
 16     do
 17     :: i < N_QRCU_UPDATERS ->
 18       run qrcu_updater(i);
 19       i++
 20     :: i >= N_QRCU_UPDATERS -> break
 21     od
 22   }
 23 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsection}
\stepcounter{subsection}
\stepcounter{subsection}
\stepcounter{subsection}
\stepcounter{subsection}
\stepcounter{section}
\stepcounter{subsection}
\stepcounter{subsubsection}
\stepcounter{subsubsection}
\stepcounter{subsubsection}
\stepcounter{subsection}
\stepcounter{subsubsection}
\stepcounter{subsubsection}
\stepcounter{subsubsection}
\stepcounter{subsubsection}
\stepcounter{subsubsection}
\stepcounter{subsubsection}
\stepcounter{subsubsection}
\stepcounter{subsection}
{\newpage\clearpage
\lthtmlfigureA{figure18533}%
\begin{figure}{ \scriptsize
\begin{verbatim}

 static inline void rcu_enter_nohz(void)
 {
+       mb();
        __get_cpu_var(dynticks_progress_counter)++;
-       mb();
 }

 static inline void rcu_exit_nohz(void)
 {
-       mb();
        __get_cpu_var(dynticks_progress_counter)++;
+       mb();
 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlfigureA{figure18539}%
\begin{figure}{ \scriptsize
\begin{verbatim}

-       if ((curr - snap) > 2 || (snap & 0x1) == 0)
+       if ((curr - snap) > 2 || (curr & 0x1) == 0)\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{section}
\stepcounter{subsection}
{\newpage\clearpage
\lthtmlfigureA{figure18565}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 struct rcu_dynticks {
  2   int dynticks_nesting;
  3   int dynticks;
  4   int dynticks_nmi;
  5 };
  6
  7 struct rcu_data {
  8   ...
  9   int dynticks_snap;
 10   int dynticks_nmi_snap;
 11   ...
 12 };\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsection}
{\newpage\clearpage
\lthtmlfigureA{figure18595}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 void rcu_enter_nohz(void)
  2 {
  3   unsigned long flags;
  4   struct rcu_dynticks *rdtp;
  5
  6   smp_mb();
  7   local_irq_save(flags);
  8   rdtp = &__get_cpu_var(rcu_dynticks);
  9   rdtp->dynticks++;
 10   rdtp->dynticks_nesting--;
 11   WARN_ON_RATELIMIT(rdtp->dynticks & 0x1, &rcu_rs);
 12   local_irq_restore(flags);
 13 }
 14
 15 void rcu_exit_nohz(void)
 16 {
 17   unsigned long flags;
 18   struct rcu_dynticks *rdtp;
 19
 20   local_irq_save(flags);
 21   rdtp = &__get_cpu_var(rcu_dynticks);
 22   rdtp->dynticks++;
 23   rdtp->dynticks_nesting++;
 24   WARN_ON_RATELIMIT(!(rdtp->dynticks & 0x1), &rcu_rs);
 25   local_irq_restore(flags);
 26   smp_mb();
 27 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsection}
{\newpage\clearpage
\lthtmlfigureA{figure18612}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 void rcu_nmi_enter(void)
  2 {
  3   struct rcu_dynticks *rdtp;
  4
  5   rdtp = &__get_cpu_var(rcu_dynticks);
  6   if (rdtp->dynticks & 0x1)
  7     return;
  8   rdtp->dynticks_nmi++;
  9   WARN_ON_RATELIMIT(!(rdtp->dynticks_nmi & 0x1),
 10                     &rcu_rs);
 11   smp_mb();
 12 }
 13
 14 void rcu_nmi_exit(void)
 15 {
 16   struct rcu_dynticks *rdtp;
 17
 18   rdtp = &__get_cpu_var(rcu_dynticks);
 19   if (rdtp->dynticks & 0x1)
 20     return;
 21   smp_mb();
 22   rdtp->dynticks_nmi++;
 23   WARN_ON_RATELIMIT(rdtp->dynticks_nmi & 0x1, &rcu_rs);
 24 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsection}
{\newpage\clearpage
\lthtmlfigureA{figure18629}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 void rcu_irq_enter(void)
  2 {
  3   struct rcu_dynticks *rdtp;
  4
  5   rdtp = &__get_cpu_var(rcu_dynticks);
  6   if (rdtp->dynticks_nesting++)
  7     return;
  8   rdtp->dynticks++;
  9   WARN_ON_RATELIMIT(!(rdtp->dynticks & 0x1), &rcu_rs);
 10   smp_mb();
 11 }
 12
 13 void rcu_irq_exit(void)
 14 {
 15   struct rcu_dynticks *rdtp;
 16
 17   rdtp = &__get_cpu_var(rcu_dynticks);
 18   if (--rdtp->dynticks_nesting)
 19     return;
 20   smp_mb();
 21   rdtp->dynticks++;
 22   WARN_ON_RATELIMIT(rdtp->dynticks & 0x1, &rcu_rs);
 23   if (__get_cpu_var(rcu_data).nxtlist ||
 24       __get_cpu_var(rcu_bh_data).nxtlist)
 25     set_need_resched();
 26 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsection}
{\newpage\clearpage
\lthtmlfigureA{figure18648}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 static int
  2 dyntick_save_progress_counter(struct rcu_data *rdp)
  3 {
  4   int ret;
  5   int snap;
  6   int snap_nmi;
  7
  8   snap = rdp->dynticks->dynticks;
  9   snap_nmi = rdp->dynticks->dynticks_nmi;
 10   smp_mb();
 11   rdp->dynticks_snap = snap;
 12   rdp->dynticks_nmi_snap = snap_nmi;
 13   ret = ((snap & 0x1) == 0) && ((snap_nmi & 0x1) == 0);
 14   if (ret)
 15     rdp->dynticks_fqs++;
 16   return ret;
 17 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlfigureA{figure18662}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 static int
  2 rcu_implicit_dynticks_qs(struct rcu_data *rdp)
  3 {
  4   long curr;
  5   long curr_nmi;
  6   long snap;
  7   long snap_nmi;
  8
  9   curr = rdp->dynticks->dynticks;
 10   snap = rdp->dynticks_snap;
 11   curr_nmi = rdp->dynticks->dynticks_nmi;
 12   snap_nmi = rdp->dynticks_nmi_snap;
 13   smp_mb();
 14   if ((curr != snap || (curr & 0x1) == 0) &&
 15       (curr_nmi != snap_nmi || (curr_nmi & 0x1) == 0)) {
 16     rdp->dynticks_fqs++;
 17     return 1;
 18   }
 19   return rcu_implicit_offline_qs(rdp);
 20 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsection}
\stepcounter{section}
\stepcounter{chapter}
\stepcounter{section}
\stepcounter{section}
\stepcounter{section}
\stepcounter{section}
{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap21734}%
\resizebox{3in}{!}{\includegraphics{count/GlobalTreeInc}}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlinlinemathA{tex2html_wrap_inline21484}%
$O(log N)$%
\lthtmlinlinemathZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlinlinemathA{tex2html_wrap_inline21488}%
$O(N)$%
\lthtmlinlinemathZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlfigureA{figure19582}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 long __thread counter = 0;
  2 long *counterp[NR_THREADS] = { NULL };
  3 int finalthreadcount = 0;
  4 DEFINE_SPINLOCK(final_mutex);
  5 
  6 void inc_count(void)
  7 {
  8   counter++;
  9 }
 10 
 11 long read_count(void)
 12 {
 13   int t;
 14   long sum = 0;
 15 
 16   for_each_thread(t)
 17     if (counterp[t] != NULL)
 18       sum += *counterp[t];
 19   return sum;
 20 }
 21 
 22 void count_init(void)
 23 {
 24 }
 25 
 26 void count_register_thread(void)
 27 {
 28   counterp[smp_thread_id()] = 
 29 }
 30 
 31 void count_unregister_thread(int nthreadsexpected)
 32 {
 33   spin_lock(&final_mutex);
 34   finalthreadcount++;
 35   spin_unlock(&final_mutex);
 36   while (finalthreadcount < nthreadsexpected)
 37     poll(NULL, 0, 1);
 38 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{section}
{\newpage\clearpage
\lthtmlpictureA{tex2html_wrap26086}%
\includegraphics[scale=.7]{SMPdesign/DiningPhilosopher5PEM}%
\lthtmlpictureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlinlinemathA{tex2html_wrap_inline21490}%
$m+2sn$%
\lthtmlinlinemathZ
\lthtmlcheckvsize\clearpage}

\stepcounter{section}
\stepcounter{section}
{\newpage\clearpage
\lthtmlfigureA{figure19943}%
\begin{figure}{ \centering
\begin{verbatim}

  1 spin_lock(&mylock);
  2 p = search(head, key);
  3 if (p == NULL)
  4   spin_unlock(&mylock);
  5 else {
  6   list_del_rcu(&p->list);
  7   spin_unlock(&mylock);
  8   synchronize_rcu();
  9   kfree(p);
 10 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlfigureA{figure20035}%
\begin{figure}{ \tt\scriptsize
\begin{verbatim}

  1 struct profile_buffer {
  2   long size;
  3   atomic_t entry[0];
  4 };
  5 static struct profile_buffer *buf = NULL;
  6
  7 void nmi_profile(unsigned long pcvalue)
  8 {
  9   struct profile_buffer *p;
 10
 11   rcu_read_lock();
 12   p = rcu_dereference(buf);
 13   if (p == NULL) {
 14     rcu_read_unlock();
 15     return;
 16   }
 17   if (pcvalue >= p->size) {
 18     rcu_read_unlock();
 19     return;
 20   }
 21   atomic_inc(&p->entry[pcvalue]);
 22   rcu_read_unlock();
 23 }
 24
 25 void nmi_stop(void)
 26 {
 27   struct profile_buffer *p = buf;
 28
 29   if (p == NULL)
 30     return;
 31   rcu_assign_pointer(buf, NULL);
 32   synchronize_rcu();
 33   kfree(p);
 34 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlfigureA{figure20100}%
\begin{figure}{ \centering
\begin{verbatim}

  1 idx = srcu_read_lock(&ssa);
  2 synchronize_srcu(&ssb);
  3 srcu_read_unlock(&ssa, idx);
  4
  5 /* . . . */
  6
  7 idx = srcu_read_lock(&ssb);
  8 synchronize_srcu(&ssa);
  9 srcu_read_unlock(&ssb, idx);\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlfigureA{figure20126}%
\begin{figure}{ \centering
\begin{verbatim}

  1 rcu_read_lock();
  2 preempt_disable();
  3 p = rcu_dereference(global_pointer);
  4
  5 /* . . . */
  6
  7 preempt_enable();
  8 rcu_read_unlock();\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlfigureA{figure20136}%
\begin{figure}{ \scriptsize
\begin{verbatim}

  1 void foo(void)
  2 {
  3   spin_lock(&my_lock);
  4   rcu_read_lock();
  5   do_something();
  6   rcu_read_unlock();
  7   do_something_else();
  8   spin_unlock(&my_lock);
  9 }
 10
 11 void bar(void)
 12 {
 13   rcu_read_lock();
 14   spin_lock(&my_lock);
 15   do_some_other_thing();
 16   spin_unlock(&my_lock);
 17   do_whatever();
 18   rcu_read_unlock();
 19 }\end{verbatim}

}

\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{section}
{\newpage\clearpage
\lthtmldisplayA{displaymath20404}%
\begin{displaymath}
	\epsilon = \frac{T_r R_i}{2}
	\end{displaymath}%
\lthtmldisplayZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlinlinemathA{tex2html_wrap_inline21500}%
$\epsilon$%
\lthtmlinlinemathZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlinlinemathA{tex2html_wrap_inline21502}%
$T_r$%
\lthtmlinlinemathZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlinlinemathA{tex2html_wrap_inline21504}%
$R_i$%
\lthtmlinlinemathZ
\lthtmlcheckvsize\clearpage}

\stepcounter{section}
\stepcounter{section}
{\newpage\clearpage
\lthtmlinlinemathA{tex2html_wrap_inline21512}%
$2N+1$%
\lthtmlinlinemathZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlinlinemathA{tex2html_wrap_inline21514}%
$N+1$%
\lthtmlinlinemathZ
\lthtmlcheckvsize\clearpage}

\stepcounter{section}
\stepcounter{section}
\stepcounter{section}
\stepcounter{section}
\stepcounter{section}
\stepcounter{section}
\stepcounter{chapter}
\stepcounter{chapter}
\stepcounter{section}
\stepcounter{section}
\stepcounter{section}
\stepcounter{section}
\stepcounter{section}
\stepcounter{section}

\end{document}
