\begin{slide}{}
\vspace*{1in}
\begin{center}
\large\bf
Mach~3.0 IPC Internals
\end{center}
\vspace*{1in}
\begin{center}
Richard P. Draves
\end{center}
\vfill
\end{slide}

\begin{slide}{}
\pagetitle{Outline}
\begin{itemize}
\item Review
\item Modules
\item Control flow
\item Data structures
\end{itemize}
\vfill
\end{slide}

\begin{slide}{}
\pagetitle{Mach IPC Abstractions}

Message
{\small\begin{itemize}
\item Fixed-length header
\item Variable amount of typed data
\end{itemize}}

Port
{\small\begin{itemize}
\item Protected communication channel
\item Accessed via capabilities (port rights)
\end{itemize}}

Port set
{\small\begin{itemize}
\item Receive from multiple ports
\end{itemize}}
\vfill
\end{slide}

\begin{slide}{}
\pagetitle{Messages}

Message header:
\begin{itemize}
\item Destination, reply ports
\item Message size, id
\end{itemize}

Message body:
\begin{itemize}
\item Can hold port rights
\item Can hold out-of-line memory
\end{itemize}
\vfill
\end{slide}

\begin{slide}{}
\pagetitle{Ports}

Protected message queues.

Tasks have a port name space.

\begin{itemize}
\item Receive rights
\item Send rights
\item Send-once rights
\item Dead names
\item Port sets
\end{itemize}
\vfill
\end{slide}

\begin{slide}{}
\pagetitle{Port Sets}

\begin{itemize}
\item Allow a server to receive messages from multiple ports
\item Port may not belong to two port sets
\item Can't receive from a port in a port set
\item Ports and port sets share name space
\end{itemize}
\vfill
\end{slide}

\begin{slide}{}
\pagetitle{Modules}
\vfill
\centerline{\psfig{figure=modules.ps}}
\vfill
\end{slide}

\begin{slide}{}
\pagetitle{Sending Messages}
\vfill
\centerline{\psfig{figure=msgsend.ps}}
\vfill
\end{slide}

\begin{slide}{}
\pagetitle{Receiving Messages}
\vfill
\centerline{\psfig{figure=msgreceive.ps}}
\vfill
\end{slide}

\begin{slide}{}
\pagetitle{Combined Send/Receive}
\vspace*{-0.4in}
\centerline{\psfig{figure=msgrpc.ps}}
\vfill
\end{slide}

\begin{slide}{}
\pagetitle{Data Structures}
\vfill
\centerline{\psfig{figure=structures.ps}}
\vfill
\end{slide}

\begin{slide}{}
\pagetitle{Enabling Interface Features}

Interface and implementation designed together.

\begin{itemize}
\item Send-once rights:\\
Reverse lookup not as important
\item Dead names:\\
Make reuse of names feasible\\
Lazy port deallocation
\end{itemize}
\vfill
\end{slide}

\begin{slide}{}
\pagetitle{Important Operations}

\begin{itemize}
\item Given space and name, find port
\item Given space and port, find name
\item Allocate name
\item Deallocate name
\item Destroy space
\item Destroy port
\end{itemize}
\vfill
\end{slide}

\begin{slide}{}
\pagetitle{IPC Space}

Represents a task's port name space.

Hybrid data structure:
\begin{itemize}
\item Table --- 16 byte entries
\item Splay tree --- 32 byte entries
\end{itemize}

Table grown dynamically to minimize space.
\vfill
\end{slide}

\begin{slide}{}
\pagetitle{Tables}

{\small\begin{itemize}
\item 8 bits --- generation number \\
      1 bit --- collision \\
      1 bit --- compatibility \\
      1 bit --- msg-accepted request \\
      5 bits --- type \\
      16 bits --- send right references
\item object pointer
\item next-free index or dead-name request index
\item reverse-hash index
\end{itemize}}
\vspace*{0.5in}
{\small\begin{tabular}{r|l|r|r|r|} \cline{2-5}
	& type	& object	& next	& hash	\\ \cline{2-5}
0	& free	&		& 7	& 3	\\ \cline{2-5}
1	& recv	& {\tt 80174cf4}&	&	\\ \cline{2-5}
2	& recv	& {\tt 80178480}&	&	\\ \cline{2-5}
3	& send	& {\tt 80178400}&	& 5	\\ \cline{2-5}
4	& recv	& {\tt 80178510}&	&	\\ \cline{2-5}
5	& send	& {\tt 801784d0}&	& 6	\\ \cline{2-5}
6	& send	& {\tt 8013cb54}&	&	\\ \cline{2-5}
7	& free	&		& 0	&	\\ \cline{2-5}
\end{tabular}}
\vfill
\end{slide}

\begin{slide}{}
\pagetitle{Splay Trees}

Self-adjusting binary search trees.
{\small\begin{itemize}
\item Space efficient: two pointers per entry.
\item Amortized logarithmic time.
\item Recursion not needed.
\end{itemize}}

Important operations:
{\small\begin{itemize}
\item Lookup, insert, delete.
\item Split, join, traversal.
\end{itemize}}

Extra fields:
{\small\begin{itemize}
\item Left and right child pointers
\item Space and name
\end{itemize}}
\vfill
\end{slide}

\begin{slide}{}
\pagetitle{Splaying}
\vfill
\centerline{\psfig{figure=splay.ps}}
\vfill
\end{slide}

\begin{slide}{}
\pagetitle{Garbage Collection}
Reference counts
\begin{itemize}
\item Objects (ports and port sets)
\item Spaces
\end{itemize}

Port rights, messages hold references

Alive/dead indication for atomicity
\vfill
\end{slide}

\begin{slide}{}
\pagetitle{Message Circularity}
\vfill
\centerline{\psfig{figure=circular.ps}}
\vfill
\end{slide}

\begin{slide}{}
\pagetitle{Circularity Detection}

Loops might develop when messages carrying receive rights are queued.

Solution:
\begin{itemize}
\item Ports in transit reference the port to which they are queued.
\item Detect circularities in {\tt ipc_kmsg_copyin}.
\item Destroy messages in {\tt ipc_mqueue_send}.
\item Use global lock to lock multiple ports.
\end{itemize}
\vfill
\end{slide}

\begin{slide}{}
\pagetitle{Locks}
\begin{itemize}
\item Simple locks only
\item No interrupt protection
\item Read/write macros for spaces
\item Memory allocation difficult
\item Lookup functions \\
      Action functions
\end{itemize}
\end{slide}

\begin{slide}{}
\pagetitle{Lock Hierarchy}
\vfill
\centerline{\psfig{figure=locks.ps}}
\vfill
\end{slide}

\begin{slide}{}
\pagetitle{Message Buffers}
\begin{itemize}
\item Unbounded size
\item {\tt kalloc}, {\tt kfree}
\item Per-processor cache
\begin{itemize}
\item No locking
\item 256 byte buffers
\end{itemize}
\end{itemize}
\vfill
\end{slide}

\begin{slide}{}
\pagetitle{Resource Exhaustion}

No panics.

No quotas.

Problems during message receive.
\vfill
\end{slide}

\begin{slide}{}
\pagetitle{Recursion Avoidance}

Destroying a receive right destroys the queued messages.

Destroying a message destroys the rights it carries.

Solution:
\begin{itemize}
\item Recursive algorithm, except
\item Curtail recursion with queue of messages.
\end{itemize}

Splay tree lookup, traverse
\vfill
\end{slide}
