%% LyX 1.1 created this file.  For more info, see http://www.lyx.org/.
%% Do not edit unless you really know what you are doing.
\documentclass[german]{article}
\usepackage[T1]{fontenc}
\usepackage[latin1]{inputenc}
\usepackage{babel}
\setlength\parskip{\medskipamount}
\setlength\parindent{0pt}
\usepackage{graphics}
\usepackage{longtable}
\IfFileExists{url.sty}{\usepackage{url}}
                      {\newcommand{\url}{\texttt}}
\usepackage{varioref}

\makeatletter

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% LyX specific LaTeX commands.
\providecommand{\LyX}{L\kern-.1667em\lower.25em\hbox{Y}\kern-.125emX\@}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Textclass specific LaTeX commands.
 \newenvironment{lyxcode}
   {\begin{list}{}{
     \setlength{\rightmargin}{\leftmargin}
     \raggedright
     \setlength{\itemsep}{0pt}
     \setlength{\parsep}{0pt}
     \normalfont\ttfamily}%
    \item[]}
   {\end{list}}

\makeatother
\begin{document}

\title{Linux-Internals\\
 Interprozess- und Netzwerkkommunikation\\
 (Kernel 2.4)}


\author{Stephan Uhlmann <su@su2.info>}


\date{15.02.2002}

\maketitle
\vfill

Copyright 2002 Stephan Uhlmann

Permission is granted to copy, distribute and/or modify this document
under the terms of the GNU Free Documentation License, Version 1.1
or any later version published by the Free Software Foundation; with
no Invariant Sections, no Front-Cover Texts and no Back-Cover Texts.
A copy of the license is included in the section entitled \char`\"{}GNU
Free Documentation License\char`\"{}.

\newpage

\tableofcontents{}

\newpage


\section{Interprozesskommunikation\label{Interprozesskommunikation}}

\begin{verse}
\textit{Why do you insist on utilizing this primitive linguistic communication?
Your android brain is capable of so much more.}\\
\textit{-- Borg Queen, Star Trek: First Contact}
\end{verse}
Um Programmen im ''Userspace'' (ausserhalb des Kernels, normale
Prozesse) Möglichkeiten zur Synchronisation und zum Datenaustausch
zu bieten, muss das Betriebssystem verschiedene Möglichkeiten der
Interprozesskommunikation (IPC) anbieten. Dies ist unter anderem notwendig,
um Zugriffe auf gemeinsame Ressourcen zu koordinieren. Im Folgenden
die Möglichkeiten die sich unter Linux bieten.


\subsection{Primitive Kommunikation}

Man kann schon bestehende Mechanismen des Virtual File Systems (VFS)
verwenden, um sehr einfache Methoden der Interprozesskommunikation
zu realisieren. Dies ist eine sehr unelegante Methode, wird jedoch
trotzdem oft verwendet, da es leicht zu verstehen und implementieren
ist.


\subsubsection{Lock Files}

Lock files sind Dateien die von einem Prozess angelegt werden, um
anderen Prozessen zu signalisieren, dass er eine bestimmte Ressource
belegt. Die anderen Prozesse warten so lange bis das lock file wieder
verschwindet und legen dann selber wieder ein lock file an um die
Ressource zu belegen.

Diese Methode wird z.B. häufig von SMTP und POP3 Servern benutzt,
um den Zugriff auf das Mail Spool der verschiedenen Benutzer auf einem
System zu synchronisieren.

Es besteht eine 1:n Beziehung zwischen den kommunizierenden Prozessen.
Ein Prozess signalisiert durch setzen des lock files die Benutzung
der Ressource und beliebig viele Prozesse können dies abfragen. Lock
files sind nicht dazu geeignet Daten zwischen Prozessen auszutauschen.


\subsubsection{File Locks}

Das VFS bietet Möglichkeiten, Dateien durch sogenannte file locks
zu sperren. Prozesse können sich nun bei der Nutzung einer gemeinsamen
Ressource synchronisieren, indem sie ähnlich zu der Methode mit den
lock files, wo die Datei ständig neu angelegt und wieder gelöscht
wird, die eine Datei sperren und wieder entsperren. Dazu dienen die
Systemaufrufe \texttt{flock()} (4.4BSD), \texttt{lockf()} (POSIX)
und \texttt{fnctl()} (beides).

Häufig ist die gelockte Datei, die gemeinsam genutzte Ressource. Denn
z.B. ist es auch möglich, zusätzlich zur Synchronisation, auch Datenaustausch
zwischen den Prozessen zu betreiben, indem ein Prozess die Datei sperrt,
Daten in sie hineinschreibt, wieder entsperrt und der nächste Prozess
die Datei wieder sperrt, um die Daten auszulesen.

Es besteht eine 1:n Beziehung zwischen den kommunizierenden Prozessen.
Ein Prozess signalisiert durch setzen des file locks die Benutzung
der Ressource und beliebig viele Prozesse können dies abfragen. Es
können Daten beliebiger Menge über die gemeinsam benutzte Datei ausgetauscht
werden.


\subsection{Pipes}

Pipes stellen die klassische Methode der Interprozesskommunikation
unter Unix dar, da sie sehr mächtig und einfach zu benutzen sind.
Jedem dürfte eine Befehlszeile wie

\begin{lyxcode}
ls~-la~|~more
\end{lyxcode}
bekannt vorkommen. Die Shell startet die beiden Prozesse \texttt{ls}
und \texttt{more} die über eine Pipe miteinander verbunden sind. \texttt{ls}
schreibt seine Ausgabe in die Pipe und \texttt{more} liest sie daraus.
Man kann theoretisch beliebig viele Prozesse auf diese Weise ''aneinanderreihen''.

Mit dem Systemaufruf \texttt{pipe()} erzeugt man eine Pipe.

\begin{lyxcode}
\#include~<unistd.h>~\\
int~pipe(int~filedes{[}2{]});
\end{lyxcode}
Es wird ein temporärer Inode erzeugt und der Systemaufruf gibt zwei
Dateideskriptoren zurück. \texttt{filedes{[}0{]}} zum Lesen und \texttt{filedes{[}1{]}}
zum Schreiben. Auf diese Dateideskriptoren kann man wie auf eine normale
Datei mit den Systemaufrufen \texttt{read()} und \texttt{write()}
zugreifen.

Damit nun die beiden Prozesse \texttt{ls} und \texttt{more} mit einander
kommunizieren können, müssen die beiden Prozesse jeweils die Dateideskriptoren
des Ein-/Ausgabekanals der Pipe auf die Standardausgabe (Dateideskriptor
1) bzw. Standardeingabe (Dateideskriptor 0) kopieren. Dazu bedient
man sich des Systemaufrufs \texttt{dup2()}. Ausgehend von der Shell
passiert also folgendes:

\begin{enumerate}
\item Die Shell ruft \texttt{pipe()} auf und bekommt zwei Dateideskriptoren
A und B zurück.
\item Die Shell führt für die beiden Programme zweimal \texttt{fork()} aus.
\item Die Shell schliesst wieder die beiden Dateideskriptoren A und B.
\end{enumerate}
Der erste Kindprozess (für \texttt{ls}) tut folgendes:

\begin{enumerate}
\item Aufruf von \texttt{dup2(B,1)} um den schreibenden Dateideskriptor
der Pipe auf den der Standardausgabe zu kopieren
\item Schliesst die von der Shell geerbten Dateideskriptoren A und B per
\texttt{close()}.
\item Aufruf von \texttt{execve()} um das Programm \texttt{/bin/ls} auszufühen.
\end{enumerate}
Der zweite Kindprozess (für \texttt{more}) tut analog folgendes:

\begin{enumerate}
\item Aufruf von \texttt{dup2(A,0)} um den lesenden Dateideskriptor der
Pipe auf den der Standardeingabe zu kopieren.
\item Schliesst die von der Shell geerbten Dateideskriptoren A und B per
\texttt{close()}.
\item Aufruf von \texttt{execve()} um das Programm \texttt{/bin/more} auszufühen.
\end{enumerate}
Dies geschieht alles auf der Ebene der Systemaufrufe. Auf Kernelebene
werden ein VFS \texttt{inode} Objekt und zwei \texttt{file} Objekte
erzeugt (eins zum Lesen, eins zum Schreiben). Der \texttt{u} Eintrag
des \texttt{inode} Objekts verweist auf eine Struktur \texttt{pipe\_inode\_info}
{[}include/linux/pipe\_fs\_i.h{]}

\begin{lyxcode}
struct~pipe\_inode\_info~\{~\\
~~wait\_queue\_head\_t~wait;~\\
~~char~{*}base;~\\
~~unsigned~int~len;~\\
~~unsigned~int~start;~\\
~~unsigned~int~readers;~\\
~~unsigned~int~writers;~\\
~~unsigned~int~waiting\_readers;~\\
~~unsigned~int~waiting\_writers;~\\
~~unsigned~int~r\_counter;~\\
~~unsigned~int~w\_counter;~\\
\};
\end{lyxcode}
\texttt{wait} ist eine Warteschlange der Prozesse, die darauf warten
von der Pipe lesen zu können (z.B. weil gerade jemand etwas in die
Pipe schreibt). \texttt{base} enthält die Startadresse der Speicherseite
die für den Datenaustausch angelegt wurde, \texttt{start} den Startoffset
des aktuell benutzen Bereichs der Speicherseite, \texttt{len} dessen
Länge. Desweiteren gibt es noch diverse Zähler zur Synchronisation
des Zugriffs auf diesen Inode von mehreren lesenden oder schreibenden
Prozessen.

Der Zugriff auf eine Pipe kann von Prozessen im Userspace mit den
normalen \texttt{read()} und \texttt{write()} Systemaufrufen passieren.
Auf Kernelebene wird das durch die Funktionen \texttt{pipe\_read()}
und \texttt{pipe\_write()} {[}fs/pipe.c{]} realisiert. Diese kopieren
die Daten vom Userspace in die von der durch \texttt{pipe\_inode\_info}
verwalteten Speicherseite in den Kernelspace und zurück. Sie kümmern
sich auch um die Synchronisation und Fehlerbehandlung bei den verschiedensten
Kombinationen von blockierenden und nicht-blockierenden Schreib- und
Lesezugriffen.

{[}include/linux/limits.h{]} legt als Grösse für eine Pipe 4096 Bytes
fest (PIPE\_BUF), d.h. es können maximal 4 kB Daten ''am Stück''
in eine Pipe geschrieben werden. Nach POSIX Standard hat dies atomar
zu erfolgen, d.h. ein Prozess der nur bis zu dieser Anzahl an Bytes
Daten in eine Pipe schreibt, wird nicht unterbrochen und kann sicher
sein, dass die Daten originalgetreu im Speicherbereich der Pipe angekommen
sind.

Obwohl es theoretisch möglich ist, dass mehrere Prozesse den selben
Dateideskriptor der Pipe benutzen, können Daten nur in 1:1 Beziehungen
ausgetauscht werden. D.h. Daten die ein Prozess in die Pipe schreibt
können nur von einem Prozess gelesen werden.

Pipes sind temporär, d.h. sie existieren nur solange einer der beteiligten
Prozesse noch existiert. Möchte man eine Pipe über die Lebensdauer
der Prozesse erhalten, nutzt man so genannte ''Named Pipes''.


\subsection{Named Pipes}

Named Pipes sind den normalen Pipes sehr ähnlich. Sie haben jedoch
einen entscheidenden Vorteil: hiermit kann eine schon existierende
Pipe von beliebigen Prozessen genutzt werden. Bei normalen Pipes müssen
dazu die Prozesse vom selben Elternprozess abstammen (um an die Dateideskriptoren
ranzukommen).

Man kann eine Named Pipe mit dem Befehl

\begin{lyxcode}
mkfifo~\textit{Name}
\end{lyxcode}
erzeugen. Aufgrund des Befehls werden Named Pipes häufig auch als
FIFOs bezeichnet. Dies ist zwar richtig, da sie nach dem FIFO (First
In First Out) Prinzip funktionieren, jedoch arbeiten die normalen
(temporären) Pipes nach dem selben Prinzip, würde also als unterscheidende
Bezeichnung nicht passen.

Um das Beispiel von oben mit Named Pipes umzusetzen tut man folgendes
(\texttt{fifo} ist die zuvor angelegte Named Pipe):

\begin{lyxcode}
ls~-la~>~fifo
\end{lyxcode}
Nun liest ein anderer Prozess die Daten aus der Named Pipe wieder
aus:

\begin{lyxcode}
more~fifo
\end{lyxcode}
Die Named Pipe existiert weiter und kann weiter benutzt werden.

Im Gegensatz zu normalen Pipes wo in einem Schritt die Pipe erzeugt
wird (ein \texttt{inode} Objekt, zwei \texttt{file} Objekte und die
Speicherseite) und gleich zum Lesen und Schreiben geöffnet ist, werden
Named Pipes von den Prozessen im Userspace geöffnet und geschlossen.
Dabei beachtet Linux, dass es möglich ist, dass eine Pipe zum Lesen
geöffnet wird bevor etwas hineingeschrieben wurde, sowie dass eine
Pipe zum Schreiben geöffnet wird bevor sie auch zum Lesen geöffnet
wurde.

Zum Anlegen einer Named Pipe bedient man sich des \texttt{mknod()}
Systemaufrufs. Auf Kernelebene passiert dort das gleiche bei beim
erzeugen einer Device Datei.

Das Lesen und Schreiben auf eine Named Pipe funktioniert auf die gleiche
Weise wie bei normalen Pipes mit den Systemaufrufen \texttt{read()}
und \texttt{write()} bzw. auf Kernelebene mit den Funktionen \texttt{pipe\_read()}
und \texttt{pipe\_write()}.

Obwohl es auch hier es möglich ist, dass mehrere Prozesse die selbe
Named Pipe benutzen, können Daten nur in 1:1 Beziehungen ausgetauscht
werden. D.h. Daten die ein Prozess in die Pipe schreibt können nur
von einem Prozess gelesen werden.


\subsection{System V IPC}

Eine der wichtigsten Varianten von Unix (neben BSD), das System V,
definierte einige der klassischen Mittel der Interprozesskommunikation:
Semaphore, Messagequeue und Shared Memory. Obwohl nicht im POSIX Standard
enthalten, unterstützt Linux diese auch. Allen dreien ist gemeinsam,
dass sie die Struktur \texttt{kern\_ipc\_perm} enthalten, in der die
Zugriffsrechte auf das IPC Objekt verwaltet.

\begin{lyxcode}
struct~kern\_ipc\_perm~\{~\\
~~key\_t~key;~~~~/{*}~Schlüssel~{*}/~\\
~~uid\_t~uid;~~~~/{*}~UID~Eigentümer~{*}/~\\
~~gid\_t~gid;~~~~/{*}~GID~Eigentümer~{*}/~\\
~~uid\_t~cuid;~~~/{*}~UID~Erzeuger~{*}/~\\
~~gid\_t~cgid;~~~/{*}~GID~Erzeuger~{*}/~\\
~~mode\_t~mode;~~/{*}~Zugriffsmodus~{*}/~\\
~~unsigned~long~seq;~~/{*}~Sequenznummer~{*}/~\\
\};
\end{lyxcode}
\texttt{key} ist eine einfache Nummer, die dynamisch beim Erstellen
des IPC Objekts erzeugt wird und das IPC Objekt eindeutig referenziert.
Die Sequenznummer wird zur Bestimmung der Objekt ID (s.u.) aus dem
\texttt{key} verwendet.

Von Bedeutung ist unter Linux weiterhin der Systemaufruf

\begin{lyxcode}
int~ipc(unsigned~int~call,~int~first,~int~second,~int~third,~void~{*}ptr,~long~fifth)
\end{lyxcode}
Dieser ist dafür zuständig die IPC Funktionen (angegeben in \texttt{call})
in Funktionsaufrufe der jeweiligen Implementierungen im Kernel umzusetzen.
Dies ist jedoch für normale Prozesse nicht sehr elegant und auch nicht
portabel (da Linux-spezifisch). Deshalb benutzt man die jeweiligen
Funktionen der C Bibliothek. Innerhalb des Kernels sind diese dann
durch jeweilige \texttt{sys\_} Aufrufe implementiert.


\subsubsection{Semaphoren}

Eine Semaphore ist im Prinzip ein Speicherbereich, dessen Wert von
mehreren Prozessen ausgelesen und geändert werden kann. Dabei ist
das Lesen und (in Abhängigkeit vom aktuellen Wert der Semaphore) Ändern
des Wertes atomar, d.h. der Vorgang wird nicht von einem anderen Prozess
unterbrochen, der evtl. zwischen dem Lese- und Schreibvorgang den
Wert nochmals ändern könnte.

System V Semaphoren erweitern dieses Modell dahingehend, dass ein
Array von Semaphoren erzeugt und durch eine einzige Operation verändert
werden kann. Mit der Funktion

\begin{lyxcode}
int~semget~(~key\_t~key,~int~nsems,~int~semflg~)
\end{lyxcode}
werden \texttt{nsems} Semaphoren mit dem Schlüssel \texttt{key} erzeugt.
Ist \texttt{key} noch nicht benutzt oder hat den besonderen Wert \texttt{IPC\_PRIVATE},
so wird ein neues Array von Semaphoren angelegt und eine \texttt{semid}
zurückgegeben, über die man Operationen auf diesem Semaphoren-Array
ausführen kann. Referenziert \texttt{key} ein bereits existierendes
Semaphoren-Array, so wird nur die damit assoziierte \texttt{semid}
zurückgegeben.

Das Semaphoren-Array hat folgende Struktur {[}include/linux/sem.h{]}:

\begin{lyxcode}
struct~sem\_array~\{~\\
~~struct~kern\_ipc\_perm~sem\_perm;~~~~~~~~/{*}~permissions~..~see~ipc.h~{*}/~\\
~~time\_t~sem\_otime;~~~~~~~~~~~~~~~~~~~~~/{*}~last~semop~time~{*}/~\\
~~time\_t~sem\_ctime;~~~~~~~~~~~~~~~~~~~~~/{*}~last~change~time~{*}/~\\
~~struct~sem~{*}sem\_base;~~~~~~~~~~~~~~~~~/{*}~ptr~to~first~semaphore~in~array~{*}/~\\
~~struct~sem\_queue~{*}sem\_pending;~~~~~~~~/{*}~pending~operations~to~be~processed~{*}/~\\
~~struct~sem\_queue~{*}{*}sem\_pending\_last;~~/{*}~last~pending~operation~{*}/~\\
~~struct~sem\_undo~{*}undo;~~~~~~~~~~~~~~~~/{*}~undo~requests~on~this~array~{*}/~\\
~~unsigned~long~sem\_nsems;~~~~~~~~~~~~~~/{*}~no.~of~semaphores~in~array~{*}/~\\
\};
\end{lyxcode}
wobei \texttt{sem} folgende Struktur ist:

\begin{lyxcode}
struct~sem~\{~\\
~~int~semval;~/{*}~current~value~{*}/~\\
~~int~sempid;~/{*}~pid~of~last~operation~{*}/~\\
\};
\end{lyxcode}
Wenn eine Operation nicht erfolgreich ausgeführt werden kann und der
Prozess blockieren darf, so wird er in die \texttt{sem\_pending} Queue
eingereiht. In dieser werden alle Prozesse und deren Operationen auf
dem Semaphoren-Array die noch auszuführen sind, gesammelt.

\begin{lyxcode}
struct~sem\_queue~\{~\\
~~struct~sem\_queue~{*}~next;~~~~~/{*}~next~entry~in~the~queue~{*}/~\\
~~struct~sem\_queue~{*}{*}~prev;~~~~/{*}~previous~entry~in~the~queue,~{*}(q->prev)~==~q~{*}/~\\
~~struct~task\_struct{*}~sleeper;~/{*}~this~process~{*}/~\\
~~struct~sem\_undo~{*}~undo;~~~~~~/{*}~undo~structure~{*}/~\\
~~int~pid;~~~~~~~~~~~~~~~~~~~~~/{*}~process~id~of~requesting~process~{*}/~\\
~~int~status;~~~~~~~~~~~~~~~~~~/{*}~completion~status~of~operation~{*}/~\\
~~struct~sem\_array~{*}~sma;~~~~~~/{*}~semaphore~array~for~operations~{*}/~\\
~~int~id;~~~~~~~~~~~~~~~~~~~~~~/{*}~internal~sem~id~{*}/~\\
~~struct~sembuf~{*}~sops;~~~~~~~~/{*}~array~of~pending~operations~{*}/~\\
~~int~nsops;~~~~~~~~~~~~~~~~~~~/{*}~number~of~operations~{*}/~\\
~~int~alter;~~~~~~~~~~~~~~~~~~~/{*}~operation~will~alter~semaphore~{*}/~\\
\};
\end{lyxcode}
System V Semaphoren erlauben es auch, dass bei Beenden eines Prozesses
Operationen auf Semaphoren rückgängig gemacht werden. Dies soll sogenannte
''deadlocks'' verhindern. Dabei belegt ein Prozess per Semaphore
eine Ressource, wird jedoch beendet bevor er die Ressource wieder
freigeben kann und alle anderen Prozesse warten vergebens darauf,
dass die Ressource durch die Semaphore wieder freigegeben wird.

Dazu verwaltet \texttt{task\_struct} eine Liste mit ''undo'' Operationen,
die auf die Semaphore angewandt werden, wenn der Prozess beendet wird.

\begin{lyxcode}
struct~sem\_undo~\{~\\
~~struct~sem\_undo~{*}~proc\_next;~/{*}~next~entry~on~this~process~{*}/

~~struct~sem\_undo~{*}~id\_next;~~~/{*}~next~entry~on~this~semaphore~set~{*}/

~~int~semid;~~~~~~~~~~~~~~~~~~~/{*}~semaphore~set~identifier~{*}/

~~short~{*}~semadj;~~~~~~~~~~~~~~/{*}~array~of~adjustments,~one~per~semaphore~{*}/

\};
\end{lyxcode}
Wird der Wert einer Semaphore verändert, so wird der negative Wert
der Änderung in dieser undo Liste gespeichert.

Ändern kann man den Wert einer Semaphore mit der Funktion

\begin{lyxcode}
int~semop~(~int~semid,~struct~sembuf~{*}sops,~unsigned~nsops~)
\end{lyxcode}
Auf das Semaphoren-Array, das durch \texttt{semid} referenziert wird,
werden \texttt{nsops} Operationen ausgeführt. Beginnend ab der Adresse
von \texttt{{*}sops} werden \texttt{nsops} Felder der Struktur \texttt{sembuf}
ausgewertet.

\begin{lyxcode}
struct~sembuf~\{~\\
~~unsigned~short~sem\_num;~/{*}~semaphore~index~in~array~{*}/~\\
~~short~sem\_op;~~~~~~~~~~~/{*}~semaphore~operation~{*}/~\\
~~short~sem\_flg;~~~~~~~~~~/{*}~operation~flags~{*}/~\\
\};
\end{lyxcode}
\texttt{sem\_num} ist der Index der zu verändernden Semaphore innerhalb
des Semaphoren-Arrays. \texttt{sem\_op} der Wert der auf den Wert
der Semaphore (\texttt{semval}) addiert wird. Über das Flag \texttt{IPC\_NOWAIT}
im Feld \texttt{sem\_flg} kann man das Blockieren des Prozesses bei
der Ausführung der Operationen verhindern. Das Flag \texttt{SEM\_UNDO}
speichert die Operation in oben beschriebener undo-Liste, damit sie
rückgängig gemacht werden kann, wenn der Prozess beendet wird.

\texttt{semop()} garantiert, dass entweder alle Operationen erfolgreich
sind oder keine davon ausgeführt wird. Eine Operation ist als ''erfolgreich''
definiert, wenn der Wert der Semaphore nach der Operation grösser
Null ist oder sowohl der aktuelle Wert der Semaphore als auch der
Wert der Operation Null sind.

Semaphoren erlauben eine n:m Kommunikationsbeziehung zwischen Prozessen.
Es können mehrere Prozesse gleichzeitig durch das Ändern der Semaphore
vielen anderen Prozessen z.B. die Belegung/Freigabe einer Ressource
signalisieren. Semaphoren eignen sich jedoch nicht für den Datenaustausch.


\subsubsection{Message queues}

Message queues, erlauben Prozessen Nachrichten zu schreiben, die von
anderen Prozessen gelesen werden können. Diese Nachrichten sind einfach
eine Folge von Bytes, können jedoch eine bestimmte Typkennzeichnung
haben. Prozesse können den Empfang von Nachrichten auf einen bestimmten
Typ einschränken. Die Grundlage der Implementierung unter Linux ist
die Struktur \texttt{msg\_queue} {[}ipc/msg.c{]}:

\begin{lyxcode}
struct~msg\_queue~\{~\\
~~struct~kern\_ipc\_perm~q\_perm;~\\
~~time\_t~q\_stime;~~~~~~~~~~/{*}~last~msgsnd~time~{*}/~\\
~~time\_t~q\_rtime;~~~~~~~~~~/{*}~last~msgrcv~time~{*}/~~\\
~~time\_t~q\_ctime;~~~~~~~~~~/{*}~last~change~time~{*}/~\\
~~unsigned~long~q\_cbytes;~~/{*}~current~number~of~bytes~on~queue~{*}/~\\
~~unsigned~long~q\_qnum;~~~~/{*}~number~of~messages~in~queue~{*}/~\\
~~unsigned~long~q\_qbytes;~~/{*}~max~number~of~bytes~on~queue~{*}/~\\
~~pid\_t~q\_lspid;~~~~~~~~~~~/{*}~pid~of~last~msgsnd~{*}/~\\
~~pid\_t~q\_lrpid;~~~~~~~~~~~/{*}~last~receive~pid~{*}/~\\
~\\
~~struct~list\_head~q\_messages;~\\
~~struct~list\_head~q\_receivers;~\\
~~struct~list\_head~q\_senders;~\\
\};
\end{lyxcode}
Es ist wieder die Struktur \texttt{kern\_ipc\_perm} enthalten, welche
die Zugriffsrechte regelt (s.o.). Neben weiteren Verwaltungsinformationen,
werden drei Listen angelegt. \texttt{q\_messages} ist die Liste der
ungelesenen Nachrichten. Sie besteht aus Elementen der Struktur \texttt{msg\_msg}.

\begin{lyxcode}
struct~msg\_msg~\{~\\
~~struct~list\_head~m\_list;~\\
~~long~m\_type;~\\
~~int~m\_ts;~~~~~/{*}~message~text~size~{*}/~\\
~~struct~msg\_msgseg{*}~next;~\\
~~/{*}~the~actual~message~follows~immediately~{*}/~\\
\};
\end{lyxcode}
\texttt{m\_type} ist der Typ der Nachricht. \texttt{m\_ts} die Grösse.
\texttt{next} weist auf den nächsten Eintrag in der message queue.

\begin{lyxcode}
struct~msg\_msgseg~\{~\\
~~struct~msg\_msgseg{*}~next;~\\
~~/{*}~the~next~part~of~the~message~follows~immediately~{*}/~\\
\};
\end{lyxcode}
Die Daten der Nachricht selber, folgen immer direkt im Anschluss an
das Feld \texttt{next}.

Die Liste \texttt{q\_receivers} der \texttt{msg\_queue} ist eine Liste
der Prozesse die auf Daten in der message queue warten. Sie besteht
aus Feldern der Struktur \texttt{msg\_receiver}:

\begin{lyxcode}
struct~msg\_receiver~\{~\\
~~struct~list\_head~r\_list;~\\
~~struct~task\_struct{*}~r\_tsk;~\\
~~int~r\_mode;~\\
~~long~r\_msgtype;~\\
~~long~r\_maxsize;~\\
~~struct~msg\_msg{*}~volatile~r\_msg;~\\
\};
\end{lyxcode}
Der Prozess selber wird in der \texttt{task\_struct{*} r\_tsk} gespeichert.
\texttt{r\_msgtype} ist der Typ der Nachricht auf die der Prozess
wartet, wobei der Wert Null bedeutet, dass der Prozess Nachrichten
jeden Typs annimmt. \texttt{r\_maxsize} ist die maximale Grösse der
Nachricht in Bytes.

Die Liste \texttt{q\_senders} der \texttt{msg\_queue} ist eine Liste
der Prozesse die darauf warten Daten in die message queue schreiben
zu können, z.B. weil die message queue voll ist. Sie besteht aus Feldern
der Struktur \texttt{msg\_}sender:

\begin{lyxcode}
struct~msg\_sender~\{~\\
~~struct~list\_head~list;~\\
~~struct~task\_struct{*}~tsk;~\\
\};
\end{lyxcode}
und diese besteht nur aus \texttt{task\_struct}'s für die jeweiligen
Prozesse.

Prozesse können mit der Funktion

\begin{lyxcode}
int~msgget~(~key\_t~key,~int~msgflg~)
\end{lyxcode}
eine message queue erzeugen. Ist \texttt{key} noch nicht benutzt oder
hat den besonderen Wert \texttt{IPC\_PRIVATE}, so wird eine neue messsage
queue angelegt und eine \texttt{msqid} zurückgegeben, über die man
Daten in die Queue schreiben oder von ihr lesen kann. Referenziert
\texttt{key} eine bereits existierendes message queue, so wird nur
die damit assoziierte \texttt{msqid} zurückgegeben.

Daten von einer message queue lesen, kann ein Prozess mit der Funktion

\begin{lyxcode}
ssize\_t~msgrcv~(~int~msqid,~struct~msgbuf~{*}msgp,~size\_t~msgsz,~long~msgtyp,~int~msgflg~)
\end{lyxcode}
\texttt{msgid} ist der von \texttt{msgget()} zurückgegebene Wert.
\texttt{msgp} ist die Adresse auf eine Struktur vom Typ \texttt{msgbuf}
in der die Daten aus der message queue kopiert werden. \texttt{msgsz}
ist die maximale Grösse der Nachricht. Ist die Nachricht grösser wird
entweder eine Fehlermeldung zurückgegeben oder wenn das Flag \texttt{MSG\_NOERROR}
in \texttt{msgflg} gesetzt ist, die Nachricht abgeschnitten und der
Rest geht verloren. \texttt{msgtyp} ist der Typ der zu empfangenden
Nachricht. Wurde eine Nachricht von einem Prozess empfangen, wird
sie aus der \texttt{q\_messages} Liste entfernt.

Daten in eine message queue senden , kann ein Prozess mit der Funktion

\begin{lyxcode}
int~msgsnd~(~int~msqid,~struct~msgbuf~{*}msgp,~size\_t~msgsz,~int~msgflg~)
\end{lyxcode}
\texttt{msgid} ist dabei wieder die ID der \texttt{message\_queue}.
\texttt{msgp} ein Zeiger auf eine Struktur \texttt{msgbuf} welche
die Daten der Nachricht von der Grösse \texttt{msgsz} enthält. Über
ein Flag \texttt{IPC\_NOWAIT} kann der Prozess in \texttt{msgflg}
signalisieren, dass er nicht blockieren möchte, wenn es im Moment
nicht möglich ist die Nachricht zu senden (z.B. weil die message queue
voll ist). Statt dessen kehrt \texttt{msgsnd()} dann gleich mit einer
Fehlermeldung zurück.

\texttt{msgbuf} hat folgende Struktur:

\begin{lyxcode}
struct~msgbuf~\{~\\
~~long~mtype;~~~~~/{*}~type~of~message~{*}/~\\
~~char~mtext{[}1{]};~~/{*}~message~text~{*}/~\\
\};
\end{lyxcode}
Message queues erlauben zwar den Zugriff von mehreren Prozessen, die
Daten können jedoch nur in 1:1 Beziehung ausgetauscht werden.


\subsubsection{Shared Memory}

Die dritte Variante der System V IPC ist das shared memory. Verschiedene
Prozesse können einen gemeinsamen Speicherbereich nutzen und durch
normale Maschinenbefehle zum Lesen und Schreiben Daten austauschen.
Es ist die schnellste Form von IPC, da es keinerlei weitere Synchronisationsmechanismen
gibt. Dies muss bei Bedarf ''von Hand'' implementiert werden (z.B.
mit den schon erwähnten Semaphoren). Die Grundlage der Implementierung
von shared memory unter Linux bildet die Struktur \texttt{shmid\_kernel}
{[}ipc/shm.c{]}:

\begin{lyxcode}
struct~shmid\_kernel~/{*}~private~to~the~kernel~{*}/~\\
\{~\\
~~struct~kern\_ipc\_perm~shm\_perm;~\\
~~struct~file~{*}~shm\_file;~\\
~~int~id;~\\
~~unsigned~long~shm\_nattch;~\\
~~unsigned~long~shm\_segsz;~\\
~~time\_t~shm\_atim;~\\
~~time\_t~shm\_dtim;~\\
~~time\_t~shm\_ctim;~\\
~~pid\_t~shm\_cprid;~\\
~~pid\_t~shm\_lprid;~\\
\};
\end{lyxcode}
Wie schon bei den anderen System V IPC Varianten werden zuerst in
\texttt{shm\_perm} die Zugriffsrechte verwaltet. \texttt{shm\_file}
ist ein Eintrag zu einer ''unlinked'' Datei im shmfs (welches meist
unter \texttt{/dev/shm} gemountet ist). ''unlinked'' bedeutet, sie
ist zwar angelegt, belegt aber keinen \texttt{inode} und ist daher
auch nicht im Filesystem sichtbar. \texttt{shm\_nattach} gibt die
Anzahl der zugreifenden (''attached'') Prozesse und \texttt{shm\_segsz}
die Segmentgrösse des Speicherbereichs aus. Danach folgen Timestamps
der letzten Attach-, Detach- und Änderungsoperation sowie die PID
des erzeugenden Prozesses und des Prozesses der zuletzt eine Operation
auf den Speicherbereich ausgeführt hat.

Analog zu den anderen System V IPC Varianten kann ein Prozess mit
der Funktion

\begin{lyxcode}
int~shmget(key\_t~key,~int~size,~int~shmflg)
\end{lyxcode}
ein neues shared memory Segment erzeugen oder sich die zu einem schon
existierenden Segment mit dem Schlüssel \texttt{key} die passende
\texttt{shmid} zurückgeben lassen.

Mit der Funktion

\begin{lyxcode}
void~{*}shmat~(~int~shmid,~const~void~{*}shmaddr,~int~shmflg~)
\end{lyxcode}
kann ein Prozess ein shared memory Segment mit der angegebenen \texttt{shmid}
seinem eigenen Datensegment zuordnen. Entweder \texttt{shmaddr} ist
0, dann wird ein beliebiger freier Speicherbereich benutzt, oder die
in \texttt{shmaddr} angegebene Adresse wird benutzt. In \texttt{shmflg}
kann man über spezielle Flags die Wahl der Speicheradresse beeinflussen
(z.B. Alignment auf eine bestimmte Blockgrösse).

Der Prozess kann nun durch Zugriff auf diesen ''virtuellen'' Speicherbereich
in seinem Datensegment auf den shared memory Bereich zugreifen. Mit
der Funktion

\begin{lyxcode}
int~shmdt~(~const~void~{*}shmaddr)
\end{lyxcode}
kann man den Zugriff wieder aufheben.

Shared memory kann von mehreren Prozessen gleichzeitig genutzt werden
und bietet daher eine n:m Kommunikationsbeziehung.


\subsubsection{ipcs und ipcrm}

Programme die System V IPC Mechanismen benutzen, können auch abstürzen.
In diesem Falle werden die von ihnen belegten IPC Ressourcen nicht
wieder freigegeben. Daher gibt es die beiden Tools \texttt{ipcs} und
\texttt{ipcrm}, um IPC Ressourcen zu verwalten. Ersteres zeigt Informationen
zu den aktuell belegten IPC Ressourcen an (soweit der Benutzer denn
die entsprechenden Zugriffsrechte hat). Ein Beispiel der Ausgabe von
\texttt{ipcs} auf einem Oracle-Server ist z.B.:

\begin{lyxcode}
han:\textasciitilde{}~\#~ipcs~\\
-{}-{}-{}-{}-{}-~Shared~Memory~Segments~-{}-{}-{}-{}-{}-{}-{}-~\\
key~~~~~~~shmid~~owner~~~perms~~bytes~~~~nattch~status~\\
0x00000000~512~~~root~~~~600~~~~1056768~~~3~~~~~~dest~\\
0x00000000~513~~~wwwrun~~600~~~~46084~~~~~3~~~~~~dest~\\
0x74b8f640~514~~~oracle~~640~~~~374599680~14~\\
0xd06f7024~515~~~oracle~~640~~~~255062016~10~\\
0x91b0e5f8~516~~~oracle~~640~~~~143319040~11~\\
-{}-{}-{}-{}-{}-~Semaphore~Arrays~-{}-{}-{}-{}-{}-{}-{}-~\\
key~~~~~~~semid~~owner~~~perms~~nsems~~status~\\
0x06999a36~1536~~oracle~~640~~~~~154~\\
0x052b3e16~3073~~oracle~~640~~~~~154~\\
0x0699aa36~4610~~oracle~~640~~~~~154~\\
-{}-{}-{}-{}-{}-~Message~Queues~-{}-{}-{}-{}-{}-{}-{}-~\\
key~~~~~~~msqid~~owner~~~perms~~used-bytes~~~messages~\\
han:\textasciitilde{}~\#
\end{lyxcode}
Mit \texttt{ipcrm} kann man nun bei Bedarf unter Angabe der jeweiligen
id die IPC Ressource wieder freigeben.

Seit Linux Kernel 2.4 sind im Verzeichnis \texttt{/proc/sysvipc/}
drei Dateien \texttt{sem}, \texttt{msg} und \texttt{shm} angelegt,
aus denen sich die gleichen Informationen wie mit \texttt{ipcs} auslesen
lassen.


\subsection{IPC mit Sockets}

Die bisher beschriebenen Möglichkeiten zur Interprozesskommunikation
beschränkten sich auf die Kommunikation von Prozessen eines Rechners.
Die Socket-Programmierschnittstelle ermöglicht es auch über Rechnergrenzen
hinweg, über ein Netzwerk zu kommunizieren. Dies wird genauer im Abschnitt
''Netzwerkkommunikation'' beschrieben (\vpageref{Netzwerkkommunikation}).

Eine spezielle Variante der Sockets, die Unix-Domain-Sockets, bieten
jedoch auch auch eine einfache Möglichkeit zur lokalen Kommunikation
innerhalb eines Rechners.

Unix-Domain-Sockets werden auf die gleiche Art und Weise erstellt
und benutzt wie Sockets zur Netzwerkkommunikation. Man muss nur \texttt{AF\_UNIX}
bzw. \texttt{AF\_LOCAL} als Adressfamilie beim \texttt{socket()} Aufruf
angeben. Dann kann man mit Hilfe der Struktur \texttt{sockaddr\_un}
einen Dateinamen angeben, der den Socket im lokalen Dateisystem repräsentiert
{[}include/linux/un.h{]}:

\begin{lyxcode}
\#define~UNIX\_PATH\_MAX~108~\\
~\\
struct~sockaddr\_un~\{~\\
~~sa\_family\_t~sun\_family;~/{*}~AF\_UNIX~{*}/~\\
~~char~sun\_path{[}UNIX\_PATH\_MAX{]};~/{*}~pathname~{*}/~\\
\};
\end{lyxcode}
Diese Struktur übergibt man dann dem \texttt{connect()} Aufruf als
\texttt{struct sockaddr{*} serv\_addr} wonach dann über den Dateideskriptor
mit den üblichen Dateioperationen auf den Socket zugegriffen werden
kann.

Auch wenn ein Socket von mehreren Prozessen genutzt werden kann, können
Daten nur in 1:1 Beziehung über einen Socket ausgetauscht werden.


\subsection{Zusammenfassung Kommunikationsbeziehungen}

\begin{longtable}{|c|c|c|}
\hline 
IPC-Art&
Beziehung&
Datenaustausch\\
\hline
\hline 
Lock files&
1:n&
nein\\
\hline
\hline 
File locks&
1:n&
ja\\
\hline
\hline 
Pipes&
1:1&
ja\\
\hline
\hline 
Named Pipes&
1:1&
ja\\
\hline
\hline 
Semaphoren&
n:m&
nein\\
\hline
\hline 
Message queues&
1:1&
ja\\
\hline
\hline 
Shared memory&
n:m&
ja\\
\hline
\hline 
Sockets&
1:n&
ja\\
\hline
\end{longtable}

\newpage


\section{Netzwerkkommunikation\label{Netzwerkkommunikation}}

\begin{verse}
\textit{Note that 120 sec is defined in the protocol as the maximum
possible RTT.}\\
\textit{I guess we'll have to use something other than TCP to talk
to the University of Mars.}\\
\textit{-- aus net/ipv4/tcp\_timer.c}
\end{verse}
Eines der Grundanforderungen an ein Betriebssystem ist es Netzwerkkommunikation
zu unterstützen. Linux, selbst nur durch das Internet so schnell verbreitet
und gewachsen, unterstützt das Internet Protocol (IP) seit ca. Version
0.96a. Die Netzwerkimplementation basiert auf 4.3 BSD Sockets mit
einigen Erweiterungen.

Wie in anderen Bereichen des Linux Kernels, wurden auch bei der Netzwerkimplementation
verschiedene Abstraktionsschichten eingeführt. Die folgende Darstellung
verdeutlicht dies:

\vspace{0.3cm}
{\centering \includegraphics{net_layers.eps} \par}
\vspace{0.3cm}

Folgend werden nun die einzelnen Schichten und ihre Implementation
im Linux-Kernel erläutert. Jede Schicht interagiert dabei mit der
Schicht über bzw. unter ihr, um die Daten zu transportieren.

Insgesamt wird darauf geachtet, dass die zu transportierenden Daten
möglichst selten kopiert werden, da dies den Netzwerk-Datendurchsatz
des Linux-Kernels entscheidend beeinflusst. Soll ein Datenpaket zwischen
zwei Programmen der beiden Rechner A und B verschickt werden, werden
diese Daten insgesamt nur viermal kopiert. Vom Userspace des Rechners
A in den Kernelbereich, von dort zum Netzwerkgerät, dann vom Netzwerkgerät
des Rechners B in dessen Kernelbereich und von dort in den Userspace
des Programms auf Rechner B.


\subsection{BSD-Socket}

Als Programmierer benutzt man die Socket-Schnittstelle die in der
C-Bibliothek zur Verfügung gestellt wird. Diese besteht aus den folgenden
Funktionen:

\begin{lyxcode}
int~socket(int~domain,~int~type,~int~protocol);

int~bind(int~sockfd,~struct~sockaddr~{*}my\_addr,~socklen\_t~addrlen);

int~listen(int~s,~int~backlog);

int~connect(int~sockfd,~const~struct~sockaddr~{*}serv\_addr,~socklen\_t~addrlen);

int~accept(int~s,~struct~sockaddr~{*}addr,~socklen\_t~{*}addrlen);

int~send(int~s,~const~void~{*}msg,~size\_t~len,~int~flags);

int~sendto(int~s,~const~void~{*}msg,~size\_t~len,~int~flags,~const~struct~sockaddr~{*}to,~socklen\_t~tolen);

int~recv(int~s,~void~{*}buf,~size\_t~len,~int~flags);

int~recvfrom(int~s,~void~{*}buf,~size\_t~len,~int~flags,~struct~sockaddr~{*}from,~socklen\_t~{*}fromlen);

int~getsockopt(int~s,~int~level,~int~optname,~void~{*}optval,~socklen\_t~{*}optlen);

int~setsockopt(int~s,~int~level,~int~optname,~const~void~{*}optval,~socklen\_t~optlen);
\end{lyxcode}
Erzeugt man mit \texttt{socket()} einen Socket, so gibt diese Funktion
einen Dateideskriptor zurück über den man mit den anderen Funktionen
den Socket benutzen kann. Es können auch normale I/O-Systemaufrufe
wie \texttt{write()} und \texttt{read()} benutzt werden.

Diese Socket-Funktionen werden allein durch den Systemaufruf \texttt{sys\_socketcall()}
im Kernel implementiert {[}net/socket.c{]}:

\begin{lyxcode}
asmlinkage~long~sys\_socketcall(int~call,~unsigned~long~{*}args)
\end{lyxcode}
Dies ist eine der typischen Multiplexer-Systemaufrufe. \texttt{call}
gibt an welcher Funktionsaufruf genau gemeint ist, gefolgt von der
dynamischen Liste an Parametern. \texttt{sys\_socketcall()} ruft dann
die entsprechenden \texttt{sys\_} Funktionen (z.B. \texttt{sys\_socket()})
mit den passenden Parametern auf. Diese Funktionen bilden die oberste
Schicht der Netzwerkimplementation im Linux-Kernel: die BSD-Socketschicht.

Eine der wichtigsten Strukturen innerhalb des Kernels ist die \texttt{struct
socket} {[}include/linux/net.h{]}:

\begin{lyxcode}
struct~socket~\{~\\
~~socket\_state~state;
\end{lyxcode}
Hier wird der aktuelle Zustand des Sockets gespeichert. Z.B.: \texttt{SS\_CONNECTED}
oder \texttt{SS\_UNCONNECTED} {[}include/linux/net.h{]}.

\begin{lyxcode}
~~unsigned~long~flags;
\end{lyxcode}
Flags die bestimmte Eigenschaften des Sockets beschreiben (z.B. asynchron,
nicht blockierend).

\begin{lyxcode}
~~struct~proto\_ops~{*}ops;
\end{lyxcode}
Enthält für Sockets der \texttt{AF\_INET} Adressfamilie spezifische
Operationen (als Funktionspointer).

\begin{lyxcode}
~~struct~inode~{*}inode;~\\
~~struct~fasync\_struct~{*}fasync\_list;~\\
~~struct~file~{*}file;
\end{lyxcode}
Werden für Sockets der \texttt{AF\_UNIX} Adressfamilie benötigt, um
einen Socket einer Inode/Datei im Filesystem zuzuordnen.

\begin{lyxcode}
~~struct~sock~{*}sk;
\end{lyxcode}
Unterstruktur für die \texttt{AF\_INET} Adressfamilie.

\begin{lyxcode}
~~wait\_queue\_head\_t~wait;~\\
~~short~type;
\end{lyxcode}
Gibt den Typ des Sockets an. Gültige Werte sind \texttt{SOCK\_STREAM}
(TCP), \texttt{SOCK\_DGRAM} (UDP) und \texttt{SOCK\_RAW} (IP) {[}include/asm/socket.h{]}.

\begin{lyxcode}
~~unsigned~char~passcred;

\};
\end{lyxcode}
Eine weitere wichtige Struktur ist die \texttt{struct sk\_buff} welche
zur Verwaltung einzelner Datenpakete verwendet wird ({[}include/linux/skbuff.h{]},
Auszugsweise da sehr umfangreich):

\begin{lyxcode}
struct~sk\_buff~\{~\\
~~/{*}~These~two~members~must~be~first.~{*}/~\\
~~struct~sk\_buff~{*}~next;~~~~~~~/{*}~Next~buffer~in~list~{*}/~\\
~~struct~sk\_buff~{*}~prev;~~~~~~~/{*}~Previous~buffer~in~list~{*}/~\\
~~struct~sk\_buff\_head~{*}~list;~~/{*}~List~we~are~on~{*}/~\\
~~struct~sock~{*}sk;~~~~~~~~~~~~~/{*}~Socket~we~are~owned~by~{*}/~\\
~~struct~timeval~stamp;~~~~~~~~/{*}~Time~we~arrived~{*}/~\\
~~struct~net\_device~{*}dev;~~~~~~/{*}~Device~we~arrived~on/are~leaving~by~{*}/~\\
~\\
~~/{*}~Transport~layer~header~{*}/~\\
~~union~\{~\\
~~~~struct~tcphdr~{*}th;~\\
~~~~struct~udphdr~{*}uh;~\\
~~~~struct~icmphdr~{*}icmph;~\\
~~~~struct~igmphdr~{*}igmph;~\\
~~~~struct~iphdr~{*}ipiph;~\\
~~~~struct~spxhdr~{*}spxh;~\\
~~~~unsigned~char~{*}raw;~\\
~~\}~h;~\\
~\\
~~/{*}~Network~layer~header~{*}/~\\
~~union~\{~\\
~~~~struct~iphdr~{*}iph;~\\
~~~~struct~ipv6hdr~{*}ipv6h;~\\
~~~~struct~arphdr~{*}arph;~\\
~~~~struct~ipxhdr~{*}ipxh;~\\
~~~~unsigned~char~{*}raw;~\\
~~\}~nh;~\\
~\\
~~/{*}~Link~layer~header~{*}/~\\
~~union~\{~\\
~~~~struct~ethhdr~{*}ethernet;~\\
~~~~unsigned~char~{*}raw;~\\
~~\}~mac;~\\
~\\
...~\\
~\\
~~struct~dst\_entry~{*}dst;~\\
~\\
~~unsigned~int~truesize;~~/{*}~Buffer~size~{*}/~\\
~~unsigned~char~{*}head;~~~~/{*}~Head~of~buffer~{*}/~\\
~~unsigned~char~{*}data;~~~~/{*}~Data~head~pointer~{*}/~\\
~~unsigned~char~{*}tail;~~~~/{*}~Tail~pointer~{*}/~\\
~~unsigned~char~{*}end;~~~~~/{*}~End~pointer~{*}/~\\
~\\
...~\\
~\\
\};
\end{lyxcode}
Diese Struktur verwaltet einen allgemeinen Puffer, der bei der Übertragung
von Daten zwischen den einzelnen Schichten verwendet wird. Dazu wird
unter anderem das physikalische Netzwerkgerät in einem \texttt{struct
net\_device} gespeichert über das das Paket übertragen wird. Weiterhin
werden jeweils ein Pointer auf die jeweiligen Header-Strukturen des
transport, network und link layers innerhalb des Puffers gespeichert.
\texttt{dst\_entry} ist eine Struktur die das Ziel des Pakets definiert
{[}include/net/dst.h{]}.

Die in {[}net/socket.c{]} implementierten Funktionen greifen über
den \texttt{ops} Eintrag des \texttt{struct socket} auf die spezifischen
Funktionen der INET-Socket Schicht zurück.


\subsection{INET-Socket}

Die INET-Socket-Schicht verwaltet die netzwerkspezifischen Teile des
Sockets für die \texttt{AF\_INET} Adressfamilie. Hier ist unter anderem
die Implementation der TCP/IP Protokoll-Suite in Linux festgeschrieben.
Die Struktur \texttt{struct sock} {[}include/net/sock.h{]} bildet
die Grundlage der Implementation. Da diese Struktur hier im einzelnen
zu lang und zu detailliert wäre, seien hier nur die wichtigsten Elemente
(stark gekürzt) erklärt:

\begin{lyxcode}
struct~sock~\{~\\
~\\
~~\_\_u32~daddr;~\\
~~\_\_u16~dport;~\\
~~\_\_u32~saddr;~\\
~~\_\_u16~sport;
\end{lyxcode}
Quell- und Zieladresse, sowie Portnummer.

\begin{lyxcode}
~~struct~sk\_buff\_head~receive\_queue;
\end{lyxcode}
Liste von \texttt{sk\_buff} (s.o.) Strukturen der auf den Socket ankommenden
Pakete.

\begin{lyxcode}
~~struct~sk\_buff\_head~write\_queue;
\end{lyxcode}
Liste von \texttt{sk\_buff} (s.o.) Strukturen der vom den Socket zu
sendenden Pakete.

\begin{lyxcode}
struct~proto~{*}prot;
\end{lyxcode}
Struktur mit Zeigern auf die einzelnen Funktionen der Transport-Schicht.

\begin{lyxcode}
~union~\{~\\
~~~~struct~tcp\_opt~af\_tcp;~~\\
~~~~struct~raw\_opt~tp\_raw4;~\\
~~~~struct~raw6\_opt~tp\_raw;~\\
~~~~struct~spx\_opt~af\_spx;~\\
~~\}~tp\_pinfo;
\end{lyxcode}
Struktur mit den Informationen zum jeweiligen Transport Protokoll.
Bei TCP (\texttt{struct tcp\_opt}) z.B. die Sequenznummern, diverse
Zähler (z.B. für ''slow start'' und ''congestion control''), Timestamps
und statistische Daten.

\begin{lyxcode}
~~union~\{~\\
~~~~void~{*}destruct\_hook;~\\
~~~~struct~unix\_opt~af\_unix;~\\
~~~~struct~inet\_opt~af\_inet;~\\
~~~~struct~atalk\_sock~af\_at;~\\
~~~~struct~ipx\_opt~af\_ipx;~\\
~~~~x25\_cb~{*}x25;~\\
~~~~struct~pppox\_opt~{*}pppox;~\\
~~~~struct~netlink\_opt~{*}af\_netlink;~\\
~~~~struct~atm\_vcc~{*}af\_atm;~\\
~~~~struct~irda\_sock~{*}irda;~\\
~~~~struct~wanpipe\_opt~{*}af\_wanpipe;~\\
~~~~...~\\
~~\}~protinfo;
\end{lyxcode}
Hier werden private Daten der jeweiligen Adressfamilie des benutzten
Protokolls in der ''network'' Schicht gespeichert.

\begin{lyxcode}
~~...~\\
\};
\end{lyxcode}
In {[}net/ipv4/af\_inet.c{]} sind die einzelnen Funktionen der INET
Adressfamilie implementiert. Dies sind im wesentlichen:

\begin{lyxcode}
inet\_stream\_connect(struct~socket~{*}sock,~struct~sockaddr~{*}~uaddr,~int~addr\_len,~int~flags);

inet\_dgram\_connect(struct~socket~{*}sock,~struct~sockaddr~{*}~uaddr,~int~addr\_len,~int~flags);~extern~inet\_accept(struct~socket~{*}sock,

inet\_listen(struct~socket~{*}sock,~int~backlog);

inet\_accept(struct~socket~{*}sock,~struct~socket~{*}newsock,~int~flags);

inet\_recvmsg(struct~socket~{*}sock,~struct~msghdr~{*}ubuf,~int~size,~int~flags,~struct~scm\_cookie~{*}scm);

inet\_sendmsg(struct~socket~{*}sock,~struct~msghdr~{*}msg,~int~size,~struct~scm\_cookie~{*}scm);

inet\_shutdown(struct~socket~{*}sock,~int~how);

inet\_setsockopt(struct~socket~{*}sock,~int~level,~int~optname,~char~{*}optval,~int~optlen);

inet\_getsockopt(struct~socket~{*}sock,~int~level,~int~optname,~char~{*}optval,~int~{*}optlen);
\end{lyxcode}
Diese Funktionen werden von den Funktionen der BSD-Socketschicht aufgerufen
und rufen ihrerseits wieder über den \texttt{prot} Eintrag in der
\texttt{sock} Struktur die Funktionen der entsprechenden Transportschicht
(TCP/UDP) auf.

Ein Auszug aus der Struktur \texttt{struct proto} welche die Zeiger
auf diese Funktionen bereithält:

\begin{lyxcode}
struct~proto~\{~\\
~~void~({*}close)(struct~sock~{*}sk,~long~timeout);~\\
~~int~({*}connect)(struct~sock~{*}sk,~struct~sockaddr~{*}uaddr,~int~addr\_len);~\\
~~int~({*}disconnect)(struct~sock~{*}sk,~int~flags);~\\
~~struct~sock~{*}~({*}accept)~(struct~sock~{*}sk,~int~flags,~int~{*}err);~\\
~~int~({*}ioctl)(struct~sock~{*}sk,~int~cmd,~unsigned~long~arg);~\\
~~int~({*}init)(struct~sock~{*}sk);~\\
~~int~({*}destroy)(struct~sock~{*}sk);~\\
~~void~({*}shutdown)(struct~sock~{*}sk,~int~how);~\\
~~int~({*}setsockopt)(struct~sock~{*}sk,~int~level,~int~optname,~char~{*}optval,~int~optlen);~\\
~~int~({*}getsockopt)(struct~sock~{*}sk,~int~level,~int~optname,~char~{*}optval,~int~{*}option);~\\
~~int~({*}sendmsg)(struct~sock~{*}sk,~struct~msghdr~{*}msg,~int~len);~\\
~~int~({*}recvmsg)(struct~sock~{*}sk,~struct~msghdr~{*}msg,~int~len,~int~noblock,~int~flags,~int~{*}addr\_len);~\\
~~int~({*}bind)(struct~sock~{*}sk,~struct~sockaddr~{*}uaddr,~int~addr\_len);~\\
...~\\
\};


\end{lyxcode}

\subsection{TCP/UDP}

Aufgerufen durch die Funktionen der INET-Schicht erledigen die verschiedenen
TCP- und UDP-Funktionen die Arbeit für die Transport-Schicht im Netzwerkschichtenmodell. 

Von besonderer Bedeutung ist hier die Struktur \texttt{struct msghdr}
{[}include/linux/socket.h{]}

\begin{lyxcode}
struct~msghdr~\{~\\
~~void~~~~~~~~~~~~~{*}~msg\_name;~~~~~~/{*}~Socket~name~{*}/~\\
~~int~~~~~~~~~~~~~~msg\_namelen;~~~~~/{*}~Length~of~name~{*}/~\\
~~struct~iovec~~~~~{*}~msg\_iov;~~~~~~~/{*}~Data~blocks~{*}/~\\
~~\_\_kernel\_size\_t~~msg\_iovlen;~~~~~~/{*}~Number~of~blocks~{*}/~\\
~~void~~~~~~~~~~~~~{*}~msg\_control;~~~/{*}~Per~protocol~magic~(eg~BSD~file~descriptor~passing)~{*}/~\\
~~\_\_kernel\_size\_t~~msg\_controllen;~~/{*}~Length~of~cmsg~list~{*}/~\\
~~unsigned~~~~~~~~~msg\_flags;~\\
\};
\end{lyxcode}
Sie implementiert eine allgemeine ''Nachricht'' nach Art des 4.4BSD
message passing system.

Im folgenden die wichtigsten Funktionen der TCP/UDP Implementierungen.

\texttt{int udp\_connect(struct sock {*}sk, struct sockaddr {*}uaddr,
int addr\_len)} {[}net/ipv4/udp.c{]}

\texttt{int tcp\_v4\_connect(struct sock {*}sk, struct sockaddr {*}uaddr,
int addr\_len)} {[}net/ipv4/tcp\_ipv4.c{]}

\texttt{int tcp\_sendmsg(struct sock {*}sk, struct msghdr {*}msg,
int size)} {[}net/ipv4/tcp.c{]}

\texttt{int udp\_sendmsg(struct sock {*}sk, struct msghdr {*}msg,
int len)} {[}net/ipv4/udp.c{]}

\texttt{int tcp\_recvmsg(struct sock {*}sk, struct msghdr {*}msg,
int len, int nonblock, int flags, int {*}addr\_len)} {[}net/ipv4/tcp.c{]}

\texttt{int udp\_recvmsg(struct sock {*}sk, struct msghdr {*}msg,
int len, int nonblock, int flags, int {*}addr\_len)} {[}net/ipv4/udp.c{]}

Diese Funktionen verarbeiten die Nachrichten zu Paketen von \texttt{struct
sk\_buff} und rufen die entsprechenden Funktionen der IP-Schicht auf.
Bei TCP werden vorher die bekannten Features zur verbindungsorientierten
Kommunikation implementiert.


\subsection{IP}

Die IP-Schicht stellt einen allgemeinen ''Paketübermittlungsdienst''
zur Verfügung. Man übergibt ihr ein Paket und einen Adressaten und
sie kümmert sich um die Übermittlung. Es wird nicht garantiert, dass
das Paket auch ankommt. Dafür sind dann übergeordnete Schichten wie
z.B. TCP zuständig.

Als wichtigste Datenstruktur der Implementierung der IP-Schicht im
Linux Kernel ist die \texttt{struct iphdr} {[}include/linux/ip.h{]}:

\begin{lyxcode}
struct~iphdr~\{~\\
\#if~defined(\_\_LITTLE\_ENDIAN\_BITFIELD)~\\
~~\_\_u8~ihl:4,~\\
~~version:4;~\\
\#elif~defined~(\_\_BIG\_ENDIAN\_BITFIELD)~\\
~~\_\_u8~version:4,~\\
~~ihl:4;~\\
\#else~\\
\#error~\char`\"{}Please~fix~<asm/byteorder.h>\char`\"{}~\\
\#endif~\\
~~\_\_u8~tos;~\\
~~\_\_u16~tot\_len;~\\
~~\_\_u16~id;~\\
~~\_\_u16~frag\_off;~\\
~~\_\_u8~ttl;~\\
~~\_\_u8~protocol;~\\
~~\_\_u16~check;~\\
~~\_\_u32~saddr;~\\
~~\_\_u32~daddr;~\\
~~/{*}The~options~start~here.~{*}/~\\
\};
\end{lyxcode}
Man kann die Aufgaben der IP-Schicht in das Empfangen, das Weiterleiten
und Senden von IP-Paketen unterteilen. Dabei sieht der Ablauf wie
folgt aus (alles IPv4):

Empfangen:

\begin{enumerate}
\item Erhalt des Pakets\\
\\
Mit der Funktion\texttt{}~\\
\texttt{int ip\_rcv(struct sk\_buff {*}skb, struct net\_device {*}dev,
struct packet\_type {*}pt)}\\
{[}net/ipv4/ip\_input.c{]} empfängt die IP-Schickt einen Puffer \texttt{skb}
vom Netzwerkgerät \texttt{dev} der darunter liegenden Schicht.\\

\item Überprüfen des IP-Headers\\
\\
RFC 1122 konform wird in der obigen Funktion geprüft ob:\\
1. die angegebene Länge des Paktes gültig ist (mind. die Länge eines
IP Headers)\\
2. die IP-Versionsnummer korrekt ist (IPv4 == 4)\\
3. die IP Checksumme stimmt\\

\item Vergleich der Zieladresse mit der eigenen Adresse\\
\\
Ist das Paket nicht für den lokalen Rechner, dann wird es weitergeleitet.
(In Funktion\\
\texttt{ip\_rcv\_finish(struct sk\_buff {*}skb)}, Abfrage von\\
\texttt{ip\_route\_input(skb, iph->daddr, iph->saddr, iph->tos, dev)}\\
Ist es für den lokalen Rechner wird\\
\texttt{int ip\_local\_deliver(struct sk\_buff {*}skb)}~\\
aufgerufen, sonst\texttt{}~\\
\texttt{int ip\_forward(struct sk\_buff {*}skb)}\\
{[}net/ipv4/ip\_forward.c{]}\\

\item Defragmentierung des IP-Pakets\\
\\
Wurde das Paket nicht weitergeleitet, wird es per \texttt{ip\_local\_deliver()}
auf dem Host weiterverarbeitet. Ist das Paket ein IP-Fragment, wird
versucht mit Hilfe schon empfangender Pakete es zu defragmentieren.
Ist das noch nicht möglich (weil noch Fragmente fehlen), dann wird
das Paket in einer Fragmentliste gespeichert. Dies ist durch die Funktion
\texttt{struct sk\_buff {*}ip\_defrag(struct sk\_buff {*}skb)} {[}net/ipv4/ip\_fragment.c{]}
implementiert.\\

\item Übergabe des Pakets an das nächste Protokoll\\
\\
Die Funktion \texttt{ip\_rcv\_finish()} ruft die Funktion \texttt{skb->dst->input(skb)}
auf, welche vorher auf den Funktions-Zeiger der entsprechenden \texttt{input}
Funktion der höheren Transportschicht gesetzt wurde.
\end{enumerate}
Weiterleiten:

\begin{enumerate}
\item Überprüfen des \texttt{ttl} Feldes im IP-Header\\
\\
Ist der Wert kleiner oder gleich 1, wird das Paket verworfen und eine
entsprechende ICMP-Nachricht an den Absender geschickt.\\
(in \texttt{int ip\_forward(struct sk\_buff {*}skb)} {[}net/ipv4/ip\_forward.c{]})\\
Wirklich dekrementiert wird das TTL Feld erst später.\\

\item Überprüfen des Pakets auf fehlerhaftes/ungewolltes Routing\\
\\
(zum Beispiel wenn ''strict routing'' verlangt wird und das Ziel
kein Gateway ist)\\

\item Kopieren des Paket-Headers\\
\\
Da im folgenden der IP-Header verändert wird, muss der Header des
\texttt{sk\_buff} kopiert werden (copy on write, Funktion \texttt{skb\_cow()}
in {[}include/linux/skbuff.h{]}).\\

\item Setzen/Ändern von IP Optionen\\
\\
In \texttt{int ip\_forward\_finish(struct sk\_buff {*}skb)} {[}net/ipv4/ip\_forward.c{]}
Aufruf von\\
\texttt{void ip\_forward\_options(struct sk\_buff {*}skb)} {[}net/ipv4/ip\_options.c{]}\\

\item Senden\\
\\
In \texttt{int ip\_forward\_finish(struct sk\_buff {*}skb)} {[}net/ipv4/ip\_forward.c{]}
Aufruf von\\
\texttt{int ip\_send(struct sk\_buff {*}skb)} (als \texttt{static
inline} in {[}include/net/ip.h{]} implementiert).\\
Dort wird vorher überprüft ob das Paket die MTU Grösse überschritten
hat, und dann entweder per\\
\texttt{int ip\_fragment(struct sk\_buff {*}skb, int ({*}output)(struct
sk\_buff{*}))}~\\
fragmentiert oder gleich per\texttt{}~\\
\texttt{int ip\_finish\_output(struct sk\_buff {*}skb)}~\\
verschickt. (beide Funktionen implementiert in {[}net/ipv4/ip\_output.c{]})
\end{enumerate}
Senden:

\begin{enumerate}
\item Erhalt des Pakets\\
\\
(z.B. durch Aufruf der Funktion \texttt{int ip\_queue\_xmit(struct
sk\_buff {*}skb)} {[}net/ipv4/ip\_output.c{]})\\

\item Ermitteln der Ziel-Route\\
\\
Aufruf der Funktion \texttt{ip\_route\_output(\&rt, daddr, sk->saddr,
RT\_CONN\_FLAGS(sk), sk->bound\_dev\_if)} {[}include/net/route.h{]}
um das Netzwerkgerät zu ermitteln, über welches das Paket verschickt
werden soll.\\

\item Füllen des IP-Headers\\
\\
Mit Hilfe der Funktion \texttt{unsigned char {*}skb\_push(struct sk\_buff
{*}skb, unsigned int len)} {[}include/linux/skbuff.h{]} wird am Anfang
des \texttt{sk\_buff} Puffers Platz für einen IP-Header geschaffen.
Dieser wird dann mit den entsprechenden Werten wie Quell- und Ziel-Adresse
gefüllt.\\

\item Fragmentierung des IP-Pakets\\
\\
In \texttt{int ip\_queue\_xmit2(struct sk\_buff {*}skb)} wird überprüft
ob das Paket die MTU Grösse überschritten hat. Ist das der Fall, dann
wird es mit Hilfe der Funktion \texttt{int ip\_fragment(struct sk\_buff
{*}skb, int ({*}output)(struct sk\_buff{*}))} {[}net/ipv4/ip\_output.c{]}
in mehrere Teile zerlegt.\\

\item Setzen der IP-Checksumme\\
\\
Aufruf der Funktion \texttt{void ip\_send\_check(struct iphdr {*}iph)}
{[}net/ipv4/output.c{]}, welche die Checksumme berechnet und im IP-Header
einträgt.\\

\item Übergabe an das entsprechende Netzwerkgerät\\
\\
Durch den Aufruf von \texttt{skb->dst->output(skb)} wird die \texttt{dev\_queue\_xmit()}
des Netzwerkgerätes aufgerufen, welches sich dann um das Verschicken
des Paktes kümmert.\\

\end{enumerate}

\subsection{Netzwerkgeräte}

Da unterschiedliche Hardware zur Vernetzung von Rechnern eingesetzt
werden kann, gibt es in Linux eine abstrakte Schnittstelle zur Netzwerkhardware.
Dadurch können die oberen Netzwerkschichten unabhängig von der eingesetzten
Hardware implementiert werden. Die Datenstruktr \texttt{struct net\_device}
verwaltet solch ein abstraktes Netzwerkgerät {[}include/linux/netdevice.h{]}.
Diese Datenstruktur enthält neben dem Namen (z.B. eth0) und Angaben
zur Ansteuerung wie IRQ und IO-Adresse, auch Adressen wie die Broadcast-Adresse,
Hardware-Adresse (MAC-Adresse bei Ethernet-Karten) und Multicast-MAC-Adressen
sowie etliche statistische Angaben (Anzahl empfangender/gesandter
Pakete).

\texttt{struct net\_device} enthält weiterhin Pointer auf die Funktionen
mit denen man das Gerät ansprechen kann. Die wichtigsten sind:

\begin{lyxcode}
int~({*}init)(struct~net\_device~{*}dev);
\end{lyxcode}
Initialisiert der Netzwerkgerät. Setzt z.B. die Adressen.

\begin{lyxcode}
int~({*}open)(struct~net\_device~{*}dev);
\end{lyxcode}
Öffnet das Netzwerkgrät, so dass Pakete übertragen werden können

\begin{lyxcode}
int~({*}stop)(struct~net\_device~{*}dev);
\end{lyxcode}
Beendet die Übertragung von Paketen. Setzt alle Adressen auf \texttt{NULL}.

\begin{lyxcode}
int~({*}hard\_start\_xmit)~(struct~sk\_buff~{*}skb,~struct~net\_device~{*}dev);
\end{lyxcode}
Hardwareabhänige Funktion zum senden eines Pakets.

Diese Funktionen werden von den hardwareunabhägingen API Funktionen
in {[}net/core/dev.c{]} benutzt. Zum Beispiel die Funktion \texttt{void
dev\_queue\_xmit(struct sk\_buff {*}skb, struct net\_device {*}dev)}
überprüft ob das Netzwerkgerät gerade beschäftigt ist und überträgt
das Paket dann entweder sofort per \texttt{hard\_start\_xmit()} oder
trägt es in eine Liste der noch zu sendenden Pakete innerhalb des
\texttt{struct net\_device} ein.

\newpage


\section{Referenzen}

\begin{itemize}
\item ''Linux-Kernel-Programmierung'', Beck, Böhme, Dziadzka, Kunitz,
Magnus, Verworner, Addison Wesley, ISBN 3-8273-1144-6
\item ''The Linux Kernel'', David A Rusling, \url{http://www.linuxdoc.org/LDP/tlk/}
\item ''Linux Kernel 2.4 Internals'', Tigran Aivazian, \url{http://www.moses.uklinux.net/patches/lki.html}
\item ''Interprocess Communication in Unix'', John Shapley Gray, Prentice
Hall, ISBN 0-13-186891-8
\item Linux IP Networking, Glenn Herrin, \url{http://kernelnewbies.org/documents/ipnetworking/linuxipnetworking.html}
\item ''Understanding the Linux Kernel'', Daniel P. Bovet, Marco Cesati,
O'Reilly
\end{itemize}
\newpage


\section{{\scriptsize GNU Free Documentation License}}

{\scriptsize Version 1.1, March 2000}{\scriptsize \par}

{\scriptsize Copyright (C) 2000 Free Software Foundation, Inc. 59
Temple Place, Suite 330, Boston, MA 02111-1307 USA Everyone is permitted
to copy and distribute verbatim copies of this license document, but
changing it is not allowed.}{\scriptsize \par}


\subsection*{{\scriptsize Preamble}}

{\scriptsize The purpose of this License is to make a manual, textbook,
or other written document ''free'' in the sense of freedom: to assure
everyone the effective freedom to copy and redistribute it, with or
without modifying it, either commercially or noncommercially. Secondarily,
this License preserves for the author and publisher a way to get credit
for their work, while not being considered responsible for modifications
made by others.}{\scriptsize \par}

{\scriptsize This License is a kind of ''copyleft'', which means
that derivative works of the document must themselves be free in the
same sense. It complements the GNU General Public License, which is
a copyleft license designed for free software.}{\scriptsize \par}

{\scriptsize We have designed this License in order to use it for
manuals for free software, because free software needs free documentation:
a free program should come with manuals providing the same freedoms
that the software does. But this License is not limited to software
manuals; it can be used for any textual work, regardless of subject
matter or whether it is published as a printed book. We recommend
this License principally for works whose purpose is instruction or
reference.}{\scriptsize \par}


\subsection*{{\scriptsize Applicability and Definitions}}

{\scriptsize This License applies to any manual or other work that
contains a notice placed by the copyright holder saying it can be
distributed under the terms of this License. The ''Document'', below,
refers to any such manual or work. Any member of the public is a licensee,
and is addressed as ''you''.}{\scriptsize \par}

{\scriptsize A ''Modified Version'' of the Document means any work
containing the Document or a portion of it, either copied verbatim,
or with modifications and/or translated into another language.}{\scriptsize \par}

{\scriptsize A ''Secondary Section'' is a named appendix or a front-matter
section of the Document that deals exclusively with the relationship
of the publishers or authors of the Document to the Document's overall
subject (or to related matters) and contains nothing that could fall
directly within that overall subject. (For example, if the Document
is in part a textbook of mathematics, a Secondary Section may not
explain any mathematics.) The relationship could be a matter of historical
connection with the subject or with related matters, or of legal,
commercial, philosophical, ethical or political position regarding
them.}{\scriptsize \par}

{\scriptsize The ''Invariant Sections'' are certain Secondary Sections
whose titles are designated, as being those of Invariant Sections,
in the notice that says that the Document is released under this License.}{\scriptsize \par}

{\scriptsize The ''Cover Texts'' are certain short passages of text
that are listed, as Front-Cover Texts or Back-Cover Texts, in the
notice that says that the Document is released under this License.}{\scriptsize \par}

{\scriptsize A ''Transparent'' copy of the Document means a machine-readable
copy, represented in a format whose specification is available to
the general public, whose contents can be viewed and edited directly
and straightforwardly with generic text editors or (for images composed
of pixels) generic paint programs or (for drawings) some widely available
drawing editor, and that is suitable for input to text formatters
or for automatic translation to a variety of formats suitable for
input to text formatters. A copy made in an otherwise Transparent
file format whose markup has been designed to thwart or discourage
subsequent modification by readers is not Transparent. A copy that
is not ''Transparent'' is called ''Opaque''.}{\scriptsize \par}

{\scriptsize Examples of suitable formats for Transparent copies include
plain ASCII without markup, Texinfo input format, \LaTeX{} input format,
SGML or XML using a publicly available DTD, and standard-conforming
simple HTML designed for human modification. Opaque formats include
PostScript, PDF, proprietary formats that can be read and edited only
by proprietary word processors, SGML or XML for which the DTD and/or
processing tools are not generally available, and the machine-generated
HTML produced by some word processors for output purposes only.}{\scriptsize \par}

{\scriptsize The ''Title Page'' means, for a printed book, the title
page itself, plus such following pages as are needed to hold, legibly,
the material this License requires to appear in the title page. For
works in formats which do not have any title page as such, ''Title
Page'' means the text near the most prominent appearance of the work's
title, preceding the beginning of the body of the text.}{\scriptsize \par}


\subsection*{{\scriptsize Verbatim Copying}}

{\scriptsize You may copy and distribute the Document in any medium,
either commercially or noncommercially, provided that this License,
the copyright notices, and the license notice saying this License
applies to the Document are reproduced in all copies, and that you
add no other conditions whatsoever to those of this License. You may
not use technical measures to obstruct or control the reading or further
copying of the copies you make or distribute. However, you may accept
compensation in exchange for copies. If you distribute a large enough
number of copies you must also follow the conditions in section 3.}{\scriptsize \par}

{\scriptsize You may also lend copies, under the same conditions stated
above, and you may publicly display copies.}{\scriptsize \par}


\subsection*{{\scriptsize Copying in Quantity}}

{\scriptsize If you publish printed copies of the Document numbering
more than 100, and the Document's license notice requires Cover Texts,
you must enclose the copies in covers that carry, clearly and legibly,
all these Cover Texts: Front-Cover Texts on the front cover, and Back-Cover
Texts on the back cover. Both covers must also clearly and legibly
identify you as the publisher of these copies. The front cover must
present the full title with all words of the title equally prominent
and visible. You may add other material on the covers in addition.
Copying with changes limited to the covers, as long as they preserve
the title of the Document and satisfy these conditions, can be treated
as verbatim copying in other respects.}{\scriptsize \par}

{\scriptsize If the required texts for either cover are too voluminous
to fit legibly, you should put the first ones listed (as many as fit
reasonably) on the actual cover, and continue the rest onto adjacent
pages.}{\scriptsize \par}

{\scriptsize If you publish or distribute Opaque copies of the Document
numbering more than 100, you must either include a machine-readable
Transparent copy along with each Opaque copy, or state in or with
each Opaque copy a publicly-accessible computer-network location containing
a complete Transparent copy of the Document, free of added material,
which the general network-using public has access to download anonymously
at no charge using public-standard network protocols. If you use the
latter option, you must take reasonably prudent steps, when you begin
distribution of Opaque copies in quantity, to ensure that this Transparent
copy will remain thus accessible at the stated location until at least
one year after the last time you distribute an Opaque copy (directly
or through your agents or retailers) of that edition to the public.}{\scriptsize \par}

{\scriptsize It is requested, but not required, that you contact the
authors of the Document well before redistributing any large number
of copies, to give them a chance to provide you with an updated version
of the Document.}{\scriptsize \par}


\subsection*{{\scriptsize Modifications}}

{\scriptsize You may copy and distribute a Modified Version of the
Document under the conditions of sections 2 and 3 above, provided
that you release the Modified Version under precisely this License,
with the Modified Version filling the role of the Document, thus licensing
distribution and modification of the Modified Version to whoever possesses
a copy of it. In addition, you must do these things in the Modified
Version:}{\scriptsize \par}

\begin{itemize}
\item {\scriptsize Use in the Title Page (and on the covers, if any) a title
distinct from that of the Document, and from those of previous versions
(which should, if there were any, be listed in the History section
of the Document). You may use the same title as a previous version
if the original publisher of that version gives permission.}{\scriptsize \par}
\item {\scriptsize List on the Title Page, as authors, one or more persons
or entities responsible for authorship of the modifications in the
Modified Version, together with at least five of the principal authors
of the Document (all of its principal authors, if it has less than
five). }{\scriptsize \par}
\item {\scriptsize State on the Title page the name of the publisher of
the Modified Version, as the publisher. }{\scriptsize \par}
\item {\scriptsize Preserve all the copyright notices of the Document.}{\scriptsize \par}
\item {\scriptsize Add an appropriate copyright notice for your modifications
adjacent to the other copyright notices. }{\scriptsize \par}
\item {\scriptsize Include, immediately after the copyright notices, a license
notice giving the public permission to use the Modified Version under
the terms of this License, in the form shown in the Addendum below. }{\scriptsize \par}
\item {\scriptsize Preserve in that license notice the full lists of Invariant
Sections and required Cover Texts given in the Document's license
notice.}{\scriptsize \par}
\item {\scriptsize Include an unaltered copy of this License. }{\scriptsize \par}
\item {\scriptsize Preserve the section entitled ''History'', and its
title, and add to it an item stating at least the title, year, new
authors, and publisher of the Modified Version as given on the Title
Page. If there is no section entitled ''History'' in the Document,
create one stating the title, year, authors, and publisher of the
Document as given on its Title Page, then add an item describing the
Modified Version as stated in the previous sentence. }{\scriptsize \par}
\item {\scriptsize Preserve the network location, if any, given in the Document
for public access to a Transparent copy of the Document, and likewise
the network locations given in the Document for previous versions
it was based on. These may be placed in the ''History'' section.
You may omit a network location for a work that was published at least
four years before the Document itself, or if the original publisher
of the version it refers to gives permission.}{\scriptsize \par}
\item {\scriptsize In any section entitled ''Acknowledgements'' or ''Dedications'',
preserve the section's title, and preserve in the section all the
substance and tone of each of the contributor acknowledgements and/or
dedications given therein. }{\scriptsize \par}
\item {\scriptsize Preserve all the Invariant Sections of the Document,
unaltered in their text and in their titles. Section numbers or the
equivalent are not considered part of the section titles. }{\scriptsize \par}
\item {\scriptsize Delete any section entitled ''Endorsements''. Such
a section may not be included in the Modified Version. }{\scriptsize \par}
\item {\scriptsize Do not retitle any existing section as ''Endorsements''
or to conflict in title with any Invariant Section.}{\scriptsize \par}
\end{itemize}
{\scriptsize If the Modified Version includes new front-matter sections
or appendices that qualify as Secondary Sections and contain no material
copied from the Document, you may at your option designate some or
all of these sections as invariant. To do this, add their titles to
the list of Invariant Sections in the Modified Version's license notice.
These titles must be distinct from any other section titles.}{\scriptsize \par}

{\scriptsize You may add a section entitled ''Endorsements'', provided
it contains nothing but endorsements of your Modified Version by various
parties -- for example, statements of peer review or that the text
has been approved by an organization as the authoritative definition
of a standard.}{\scriptsize \par}

{\scriptsize You may add a passage of up to five words as a Front-Cover
Text, and a passage of up to 25 words as a Back-Cover Text, to the
end of the list of Cover Texts in the Modified Version. Only one passage
of Front-Cover Text and one of Back-Cover Text may be added by (or
through arrangements made by) any one entity. If the Document already
includes a cover text for the same cover, previously added by you
or by arrangement made by the same entity you are acting on behalf
of, you may not add another; but you may replace the old one, on explicit
permission from the previous publisher that added the old one.}{\scriptsize \par}

{\scriptsize The author(s) and publisher(s) of the Document do not
by this License give permission to use their names for publicity for
or to assert or imply endorsement of any Modified Version.}{\scriptsize \par}


\subsection*{{\scriptsize Combining Documents}}

{\scriptsize You may combine the Document with other documents released
under this License, under the terms defined in section 4 above for
modified versions, provided that you include in the combination all
of the Invariant Sections of all of the original documents, unmodified,
and list them all as Invariant Sections of your combined work in its
license notice.}{\scriptsize \par}

{\scriptsize The combined work need only contain one copy of this
License, and multiple identical Invariant Sections may be replaced
with a single copy. If there are multiple Invariant Sections with
the same name but different contents, make the title of each such
section unique by adding at the end of it, in parentheses, the name
of the original author or publisher of that section if known, or else
a unique number. Make the same adjustment to the section titles in
the list of Invariant Sections in the license notice of the combined
work.}{\scriptsize \par}

{\scriptsize In the combination, you must combine any sections entitled
''History'' in the various original documents, forming one section
entitled ''History''; likewise combine any sections entitled ''Acknowledgements'',
and any sections entitled ''Dedications''. You must delete all sections
entitled ''Endorsements.''}{\scriptsize \par}


\subsection*{{\scriptsize Collections of Documents}}

{\scriptsize You may make a collection consisting of the Document
and other documents released under this License, and replace the individual
copies of this License in the various documents with a single copy
that is included in the collection, provided that you follow the rules
of this License for verbatim copying of each of the documents in all
other respects.}{\scriptsize \par}

{\scriptsize You may extract a single document from such a collection,
and distribute it individually under this License, provided you insert
a copy of this License into the extracted document, and follow this
License in all other respects regarding verbatim copying of that document.}{\scriptsize \par}


\subsection*{{\scriptsize Aggregation With Independent Works}}

{\scriptsize A compilation of the Document or its derivatives with
other separate and independent documents or works, in or on a volume
of a storage or distribution medium, does not as a whole count as
a Modified Version of the Document, provided no compilation copyright
is claimed for the compilation. Such a compilation is called an ''aggregate'',
and this License does not apply to the other self-contained works
thus compiled with the Document, on account of their being thus compiled,
if they are not themselves derivative works of the Document.}{\scriptsize \par}

{\scriptsize If the Cover Text requirement of section 3 is applicable
to these copies of the Document, then if the Document is less than
one quarter of the entire aggregate, the Document's Cover Texts may
be placed on covers that surround only the Document within the aggregate.
Otherwise they must appear on covers around the whole aggregate.}{\scriptsize \par}


\subsection*{{\scriptsize Translation}}

{\scriptsize Translation is considered a kind of modification, so
you may distribute translations of the Document under the terms of
section 4. Replacing Invariant Sections with translations requires
special permission from their copyright holders, but you may include
translations of some or all Invariant Sections in addition to the
original versions of these Invariant Sections. You may include a translation
of this License provided that you also include the original English
version of this License. In case of a disagreement between the translation
and the original English version of this License, the original English
version will prevail.}{\scriptsize \par}


\subsection*{{\scriptsize Termination}}

{\scriptsize You may not copy, modify, sublicense, or distribute the
Document except as expressly provided for under this License. Any
other attempt to copy, modify, sublicense or distribute the Document
is void, and will automatically terminate your rights under this License.
However, parties who have received copies, or rights, from you under
this License will not have their licenses terminated so long as such
parties remain in full compliance.}{\scriptsize \par}


\subsection*{{\scriptsize Future Revisions of This License}}

{\scriptsize The Free Software Foundation may publish new, revised
versions of the GNU Free Documentation License from time to time.
Such new versions will be similar in spirit to the present version,
but may differ in detail to address new problems or concerns. See
Copyleft - GNU Project - Free Software Foundation (FSF) \url{http://www.gnu.org/copyleft/}.}{\scriptsize \par}

{\scriptsize Each version of the License is given a distinguishing
version number. If the Document specifies that a particular numbered
version of this License ''or any later version\char`\"{} applies
to it, you have the option of following the terms and conditions either
of that specified version or of any later version that has been published
(not as a draft) by the Free Software Foundation. If the Document
does not specify a version number of this License, you may choose
any version ever published (not as a draft) by the Free Software Foundation.}{\scriptsize \par}


\subsection*{{\scriptsize ADDENDUM: How to use this License for your documents}}

{\scriptsize To use this License in a document you have written, include
a copy of the License in the document and put the following copyright
and license notices just after the title page:}{\scriptsize \par}

\begin{quote}
{\scriptsize Copyright \copyright~ YEAR YOUR NAME. Permission is granted
to copy, distribute and/or modify this document under the terms of
the GNU Free Documentation License, Version 1.1 or any later version
published by the Free Software Foundation; with the Invariant Sections
being LIST THEIR TITLES, with the Front-Cover Texts being LIST, and
with the Back-Cover Texts being LIST. A copy of the license is included
in the section entitled ''GNU Free Documentation License''.}{\scriptsize \par}
\end{quote}
{\scriptsize If you have no Invariant Sections, write ''with no Invariant
Sections'' instead of saying which ones are invariant. If you have
no Front-Cover Texts, write ''no Front-Cover Texts'' instead of
''Front-Cover Texts being LIST''; likewise for Back-Cover Texts.}{\scriptsize \par}

{\scriptsize If your document contains nontrivial examples of program
code, we recommend releasing these examples in parallel under your
choice of free software license, such as the GNU General Public License,
to permit their use in free software.}
\end{document}
