% 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}