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