RT internals by tglx

14 files changed, 520 insertions, 0 deletions

diff --git a/images/BigTreeClassicRCU.png b/images/BigTreeClassicRCU.png
new file mode 100644
index 0000000..131d9dd
--- /dev/null
+++ b/images/BigTreeClassicRCU.png
diff --git a/images/GracePeriodGood.png b/images/GracePeriodGood.png
new file mode 100644
index 0000000..f6812c9
--- /dev/null
+++ b/images/GracePeriodGood.png
diff --git a/images/asource.png b/images/asource.png
new file mode 100644
index 0000000..1c6f0d4
--- /dev/null
+++ b/images/asource.png
diff --git a/images/kdirsource.png b/images/kdirsource.png
new file mode 100644
index 0000000..2dd19ec
--- /dev/null
+++ b/images/kdirsource.png
diff --git a/images/ksource.png b/images/ksource.png
new file mode 100644
index 0000000..fbc5693
--- /dev/null
+++ b/images/ksource.png
diff --git a/images/overview.png b/images/overview.png
new file mode 100644
index 0000000..ac53578
--- /dev/null
+++ b/images/overview.png
diff --git a/images/pinh.png b/images/pinh.png
new file mode 100644
index 0000000..1862002
--- /dev/null
+++ b/images/pinh.png
diff --git a/images/pinv.png b/images/pinv.png
new file mode 100644
index 0000000..902bc5f
--- /dev/null
+++ b/images/pinv.png
diff --git a/images/rtarch.png b/images/rtarch.png
new file mode 100644
index 0000000..e58ffab
--- /dev/null
+++ b/images/rtarch.png
diff --git a/images/rtkernel.png b/images/rtkernel.png
new file mode 100644
index 0000000..e2ead31
--- /dev/null
+++ b/images/rtkernel.png
diff --git a/images/rtsource.png b/images/rtsource.png
new file mode 100644
index 0000000..009e8c7
--- /dev/null
+++ b/images/rtsource.png
diff --git a/images/rwlockRCUupdate.jpg b/images/rwlockRCUupdate.jpg
new file mode 100644
index 0000000..edcedcd
--- /dev/null
+++ b/images/rwlockRCUupdate.jpg
diff --git a/realtime/rt-internals/Makefile b/realtime/rt-internals/Makefile
new file mode 100644
index 0000000..d641258
--- /dev/null
+++ b/realtime/rt-internals/Makefile
@@ -0,0 +1,9 @@
+all:
+	for pdf in `ls -1 *.tex` ; do \
+		TEXINPUTS=`pwd`/../..:.:..:$(TEXINPUTS) pdflatex $$pdf; \
+		TEXINPUTS=`pwd`/../..:.:..:$(TEXINPUTS) pdflatex $$pdf; \
+	done
+
+clean:
+	rm -f *.aux *.log *.pdf *.log *.snm *.toc *.vrb *.nav *.out
+
diff --git a/realtime/rt-internals/pres_rt-internals_en.tex b/realtime/rt-internals/pres_rt-internals_en.tex
new file mode 100644
index 0000000..baeb2e1
--- /dev/null
+++ b/realtime/rt-internals/pres_rt-internals_en.tex
@@ -0,0 +1,511 @@
+% on the following slides, include icon in the left sidebar
+\def\lximg{/usr/share/lx/icons/fueller.png}
+
+\input{configpres}
+
+\title{Linux Preempt-RT internals}
+\maketitle
+
+% stop displaying 'fueller.png' on the following slides
+\def\lximg{none}
+
+\subsection{Linux Real-Time history}
+\begin{frame}[fragile]
+\frametitle{Linux Real-Time history}
+\begin{beamerboxesrounded}[shadow=true]{First projects in the late 1990s}
+\begin{itemize}
+\item KURT - Kansas University
+\item RTAI - University of Milano
+\item RTLinux - New Mexico Tech - Soccoro, New Mexico
+\item Linux/RK - Carnegie Mellon Univeristy, Pittsburgh
+\item QLinux - University of Massachusetts
+\item DROPS - University of Dresden
+\item ...
+\end{itemize}
+\end{beamerboxesrounded}
+\end{frame}
+
+\begin{frame}[fragile]
+\frametitle{Linux Real-Time history}
+\begin{beamerboxesrounded}[shadow=true]{Approaches}
+\begin{itemize}
+\item Linux as the idle thread of a nano/micro kernel
+\item Linux with implicit Real-Time properties
+\end{itemize}
+\end{beamerboxesrounded}
+\end{frame}
+
+\begin{frame}[fragile]
+\frametitle{Linux Real-Time history}
+\begin{beamerboxesrounded}[shadow=true]{Opinion I}
+\begin{quote}
+With RTLinux, you have to split the app up into the hard realtime part
+and the rest.
+\newline
+Which is, in my opinion, the only sane way to handle hard realtime. No
+confusion about priority inversions, no crap.
+\end{quote}
+\begin{flushright}
+Linus Torvalds - 2002
+\end{flushright}
+\end{beamerboxesrounded}
+\end{frame}
+
+\begin{frame}[fragile]
+\frametitle{Linux Real-Time history}
+\begin{beamerboxesrounded}[shadow=true]{Opinion II}
+\begin{quote}
+It is impossible to turn a General Purpose Operating System Kernel
+into a Real-Time Operating System Kernel!
+\end{quote}
+\begin{flushright}
+Unknown participant of a podium discussion about Linux Real-Time - 2004
+\end{flushright}
+\end{beamerboxesrounded}
+\end{frame}
+
+\begin{frame}[fragile]
+\frametitle{Linux Real-Time history}
+\begin{beamerboxesrounded}[shadow=true]{Preempt-RT}
+\begin{itemize}
+\item Started 2004 by Ingo Molnar
+\item In kernel real-time approach
+\item Driven by mainline kernel developers
+\end{itemize}
+\end{beamerboxesrounded}
+\end{frame}
+
+\begin{frame}[fragile]
+\frametitle{Linux Real-Time history}
+\begin{beamerboxesrounded}[shadow=true]{Opinion III}
+\begin{quote}
+Controlling a laser with Linux is crazy, but everyone in this room is
+crazy in his own way. So if you want to use Linux to control an
+industrial welding laser, I have no problem with your using
+PREEMPT\_RT.
+\end{quote}
+\begin{flushright}
+Linus Torvalds - 2006
+\end{flushright}
+\end{beamerboxesrounded}
+\end{frame}
+
+\subsection{Preempt-RT goals}
+
+\begin{frame}[fragile]
+\frametitle{Preempt-RT goals}
+\begin{beamerboxesrounded}[shadow=true]{What's the goal?}
+\begin{itemize}
+\item Full Linux kernel hardware support
+\item Standard posix interface
+\item No specialized user space ABI
+\item Full reuse of existing tools
+\item Scalability
+\end{itemize}
+\end{beamerboxesrounded}
+\end{frame}
+
+\begin{frame}[fragile]
+\frametitle{Preempt-RT goals}
+\begin{beamerboxesrounded}[shadow=true]{What's the target application space?}
+\begin{itemize}
+\item The majority of Real-Time applications
+\end{itemize}
+\end{beamerboxesrounded}
+\end{frame}
+
+\subsection{Preempt-RT properties}
+\begin{frame}[fragile]
+\frametitle{Preempt-RT properties}
+\begin{beamerboxesrounded}[shadow=true]{Is it hard realtime?}
+\begin{itemize}
+\item Not by the requirement of mathematical proof
+\end{itemize}
+\end{beamerboxesrounded}
+\end{frame}
+
+\begin{frame}[fragile]
+\frametitle{Preempt-RT properties}
+\begin{beamerboxesrounded}[shadow=true]{Is mathematical proof feasible?}
+\begin{itemize}
+\item Not for complex systems
+\end{itemize}
+\end{beamerboxesrounded}
+\end{frame}
+
+\begin{frame}[fragile]
+\frametitle{Preempt-RT properties}
+\begin{beamerboxesrounded}[shadow=true]{Can it be verified?}
+\begin{itemize}
+\item Empirical verfication
+\item Open and documented testing efforts (OSADL, RedHat)
+\end{itemize}
+\end{beamerboxesrounded}
+\end{frame}
+
+\subsection{Preempt-RT technology}
+\begin{frame}[fragile]
+\frametitle{Preempt-RT technology}
+\begin{beamerboxesrounded}[shadow=true]{Why is mainline not realtime capable?}
+\begin{itemize}
+\item Hard interrupt context
+\item Soft interrupt context
+\item Interrupt disabled regions
+\item Preemption disabled regions
+\item No protection against priority inversion
+\end{itemize}
+\end{beamerboxesrounded}
+\end{frame}
+
+\begin{frame}[fragile]
+\frametitle{Preempt-RT technology}
+\begin{beamerboxesrounded}[shadow=true]{Hard interrupt context}
+\begin{itemize}
+\item Runs with interrupts disabled
+\item Executes driver interrupt handlers
+\end{itemize}
+\end{beamerboxesrounded}
+\end{frame}
+
+\begin{frame}[fragile]
+\frametitle{Preempt-RT technology}
+\begin{beamerboxesrounded}[shadow=true]{Soft interrupt context}
+\begin{itemize}
+\item Runs with preemption disabled, mostly on return from hard interrupt context
+\item Executes driver and infrastructure callbacks
+\end{itemize}
+\end{beamerboxesrounded}
+\end{frame}
+
+\begin{frame}[fragile]
+\frametitle{Preempt-RT technology}
+\begin{beamerboxesrounded}[shadow=true]{Interrupt disabled regions}
+\begin{itemize}
+\item Mostly in context of spinlocks and rwlocks
+\item Few places which require explicit interrupt disable
+\end{itemize}
+\end{beamerboxesrounded}
+\end{frame}
+
+\begin{frame}[fragile]
+\frametitle{Preempt-RT technology}
+\begin{beamerboxesrounded}[shadow=true]{Why spinlocked interrupt disabled regions}
+\begin{table}
+\begin{tabular}{ll}
+ \textbf{thread} & \textbf{interrupt}    \\
+  spin\_lock(lock); &                    \\
+  interrupt         &                    \\
+                    &  interrupt handler \\
+                    &  spin\_lock(lock); \\
+                    &  DEADLOCK!         \\
+\end{tabular}
+\end{table}
+\end{beamerboxesrounded}
+\end{frame}
+
+\begin{frame}[fragile]
+\frametitle{Preempt-RT technology}
+\begin{beamerboxesrounded}[shadow=true]{Preemption disabled regions}
+\begin{itemize}
+\item Mostly in context of spinlocks and rwlocks
+\item Also protects per cpu variables
+\item Few places which require explicit preemption disable
+\end{itemize}
+\end{beamerboxesrounded}
+\end{frame}
+
+\begin{frame}[fragile]
+\frametitle{Preempt-RT technology}
+\begin{beamerboxesrounded}[shadow=true]{Why spinlocked preempt disabled regions}
+\begin{table}
+\begin{tabular}{ll}
+ \textbf{thread A} & \textbf{thread B}  \\
+  spin\_lock(lock); &                   \\
+  preemption        &                   \\
+                    &  spin\_lock(lock);\\
+                    &  DEADLOCK!        \\
+\end{tabular}
+\end{table}
+\end{beamerboxesrounded}
+\end{frame}
+
+\begin{frame}[fragile]
+\frametitle{Preempt-RT technology}
+\begin{beamerboxesrounded}[shadow=true]{spinlocks}
+\begin{itemize}
+\item RT separates them into spinlock and raw\_spinlock
+\item raw\_spinlock in RT is identical to mainline
+\item spinlock in RT is replaced by a "'sleeping"' spinlock
+\end{itemize}
+\end{beamerboxesrounded}
+\end{frame}
+
+\begin{frame}[fragile]
+\frametitle{Preempt-RT technology}
+\begin{beamerboxesrounded}[shadow=true]{Reader/Writer locks}
+\begin{itemize}
+\item rwlock in RT is replaced by a "'sleeping"' spinlock
+\item Readercount in RT is limited to 1
+\end{itemize}
+\end{beamerboxesrounded}
+\end{frame}
+
+\begin{frame}[fragile]
+\frametitle{Preempt-RT technology}
+\begin{beamerboxesrounded}[shadow=true]{Lock replacement requires}
+\begin{itemize}
+\item Forced interrupt threading
+\item Forced soft interrupt threading
+\item Substitution of percpu constructs
+\end{itemize}
+\end{beamerboxesrounded}
+\end{frame}
+
+\begin{frame}[fragile]
+\frametitle{Preempt-RT technology}
+\begin{beamerboxesrounded}[shadow=true]{Lock replacement requires}
+Preservation of migration disable. In mainline migration is disabled by
+\begin{itemize}
+\item interrupt disable
+\item preempt disable
+\end{itemize}
+\end{beamerboxesrounded}
+\end{frame}
+
+\begin{frame}[fragile]
+\frametitle{Preempt-RT technology}
+\begin{beamerboxesrounded}[shadow=true]{Priority inversion}
+\begin{center}
+\includegraphics[scale=0.4]{images/pinv.png}
+\end{center}
+\end{beamerboxesrounded}
+\end{frame}
+
+\begin{frame}[fragile]
+\frametitle{Preempt-RT technology}
+\begin{beamerboxesrounded}[shadow=true]{Priority inheritance}
+\begin{center}
+\includegraphics[scale=0.4]{images/pinh.png}
+\end{center}
+\end{beamerboxesrounded}
+\end{frame}
+
+\begin{frame}[fragile]
+\frametitle{Preempt-RT technology}
+\begin{beamerboxesrounded}[shadow=true]{Priority inheritance}
+\begin{itemize}
+\item Kernelimplementation: rtmutex
+\item Nested lock boosting
+\item User space interface: futex (pthread\_mutex)
+\end{itemize}
+\end{beamerboxesrounded}
+\end{frame}
+
+\begin{frame}[fragile]
+\frametitle{Preempt-RT technology}
+\begin{beamerboxesrounded}[shadow=true]{Lock replacement}
+\begin{itemize}
+\item Wrapper around rtmutex
+\item Adaptive spinning for spinlocks and rwlocks
+\end{itemize}
+\end{beamerboxesrounded}
+\end{frame}
+
+\begin{frame}[fragile]
+\frametitle{Preempt-RT technology}
+\begin{beamerboxesrounded}[shadow=true]{Lock replacement}
+All locking primitives are replaced except
+\begin{itemize}
+\item raw\_spinlock
+\item semaphore
+\end{itemize}
+\end{beamerboxesrounded}
+\end{frame}
+
+\begin{frame}[fragile]
+\frametitle{Preempt-RT technology}
+\begin{beamerboxesrounded}[shadow=true]{Why are semaphores special?}
+\begin{itemize}
+\item No strict owner semantics
+\item No owner, no boosting
+\end{itemize}
+\end{beamerboxesrounded}
+\end{frame}
+
+\begin{frame}[fragile]
+\frametitle{Preempt-RT technology}
+\begin{beamerboxesrounded}[shadow=true]{Further changes}
+\begin{itemize}
+\item per cpu locks
+\item preemptible RCU
+\end{itemize}
+\end{beamerboxesrounded}
+\end{frame}
+
+\begin{frame}[fragile]
+\frametitle{Preempt-RT technology}
+\begin{beamerboxesrounded}[shadow=true]{Per CPU locks}
+Protect regions which are in mainline protected by
+\begin{itemize}
+\item preemption disable
+\item interrupt disable
+\end{itemize}
+\end{beamerboxesrounded}
+\end{frame}
+
+\begin{frame}[fragile]
+\frametitle{Preempt-RT technology}
+\begin{beamerboxesrounded}[shadow=true]{Preemptible RCU}
+What's RCU?
+\begin{itemize}
+\item Read Copy Update
+\item Scalability replacement for reader/writer locks
+\item Restricted bulk refcounting
+\item Poor mans garbage collector
+\end{itemize}
+\end{beamerboxesrounded}
+\end{frame}
+
+\begin{frame}[fragile]
+\frametitle{Preempt-RT technology}
+\begin{beamerboxesrounded}[shadow=true]{Preemptible RCU}
+What's RCU?
+\begin{center}
+\includegraphics[scale=0.4]{images/GracePeriodGood.png}
+\end{center}
+\end{beamerboxesrounded}
+\end{frame}
+
+\begin{frame}[fragile]
+\frametitle{Preempt-RT technology}
+\begin{beamerboxesrounded}[shadow=true]{Preemptible RCU}
+RCU versus rwlocks
+\begin{center}
+\includegraphics[scale=0.4]{images/rwlockRCUupdate.jpg}
+\end{center}
+\end{beamerboxesrounded}
+\end{frame}
+
+\begin{frame}[fragile]
+\frametitle{Preempt-RT technology}
+\begin{beamerboxesrounded}[shadow=true]{Preemptible RCU}
+\begin{itemize}
+\item Original RCU implementation relied on preempt disable
+\item Preemptible implementation is in mainline
+\end{itemize}
+\end{beamerboxesrounded}
+\end{frame}
+
+\subsection{Preempt-RT source impact}
+
+\begin{frame}[fragile]
+\frametitle{Preempt-RT source impact}
+\begin{beamerboxesrounded}[shadow=true]{Kernel source structure}
+\begin{center}
+\includegraphics[scale=0.35]{images/ksource.png}
+\end{center}
+\end{beamerboxesrounded}
+\end{frame}
+
+\begin{frame}[fragile]
+\frametitle{Preempt-RT source impact}
+\begin{beamerboxesrounded}[shadow=true]{Kernel source structure RT patch}
+\begin{center}
+\includegraphics[scale=0.4]{images/rtsource.png}
+\end{center}
+\end{beamerboxesrounded}
+\end{frame}
+
+\begin{frame}[fragile]
+\frametitle{Preempt-RT source impact}
+\begin{beamerboxesrounded}[shadow=true]{Architecture source structure}
+\begin{center}
+\includegraphics[scale=0.35]{images/asource.png}
+\end{center}
+\end{beamerboxesrounded}
+\end{frame}
+
+\begin{frame}[fragile]
+\frametitle{Preempt-RT source impact}
+\begin{beamerboxesrounded}[shadow=true]{Architecture source structure, RT patch}
+\begin{center}
+\includegraphics[scale=0.35]{images/rtarch.png}
+\end{center}
+\end{beamerboxesrounded}
+\end{frame}
+
+\begin{frame}[fragile]
+\frametitle{Preempt-RT source impact}
+\begin{beamerboxesrounded}[shadow=true]{Core source structure}
+\begin{center}
+\includegraphics[scale=0.35]{images/kdirsource.png}
+\end{center}
+\end{beamerboxesrounded}
+\end{frame}
+
+\begin{frame}[fragile]
+\frametitle{Preempt-RT source impact}
+\begin{beamerboxesrounded}[shadow=true]{Core source structure, RT patch}
+\begin{center}
+\includegraphics[scale=0.4]{images/rtkernel.png}
+\end{center}
+\end{beamerboxesrounded}
+\end{frame}
+
+\subsection{Preempt-RT downsides}
+
+\begin{frame}[fragile]
+\frametitle{Preempt-RT downsides}
+\begin{beamerboxesrounded}[shadow=true]{Determinism comes with a prize}
+\begin{itemize}
+\item Reduced throughput
+\item Measurable I/O performance impact
+\end{itemize}
+\end{beamerboxesrounded}
+\end{frame}
+
+\subsection{Preempt-RT influence on mainline Linux}
+
+\begin{frame}[fragile]
+\frametitle{Preempt-RT influence on mainline Linux}
+\begin{beamerboxesrounded}[shadow=true]{Most of it is upstream}
+\begin{itemize}
+\item More than 95\% of the development has been merged
+\item Only the hard to solve issues are left
+\end{itemize}
+\end{beamerboxesrounded}
+\end{frame}
+
+\begin{frame}[fragile]
+\frametitle{Preempt-RT influence on mainline Linux}
+\begin{beamerboxesrounded}[shadow=true]{What has been achieved?}
+\begin{itemize}
+\item Generic interrupt subsystem
+\item Generic timekeeping subsystem
+\item Generic timer subsystem
+\item High resolution timers
+\item NOHZ infrastructure
+\item Preemptible RCU
+\item Consolidated locking infrastructure
+\item Lock dependency validator
+\item Tracing
+\item ...
+\end{itemize}
+\end{beamerboxesrounded}
+\end{frame}
+
+\subsection{Preempt-RT and Linus Torvalds}
+
+\begin{frame}[fragile]
+\frametitle{Preempt-RT}
+\begin{beamerboxesrounded}[shadow=true]{Famous last words}
+\begin{quote}
+And yeah, I still think the hard-RT people are mostly crazy.
+\end{quote}
+\begin{flushright}
+Linus Torvalds - 2010
+\end{flushright}
+\end{beamerboxesrounded}
+\end{frame}
+
+\input{tailpres}