perfbook_html/ 0000755 0001750 0001750 00000000000 11672746164 013601 5 ustar paulmck paulmck perfbook_html/images.tex 0000644 0001750 0001750 00000553315 11672745743 015606 0 ustar paulmck paulmck \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)
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}
perfbook_html/img169.png 0000644 0001750 0001750 00000000330 11672746042 015312 0 ustar paulmck paulmck PNG
IHDR \q&