Das Minix-Dateisystem

Sein erstes Dateisystem hat Linux von Minix ``geborgt''. Dieses Minix-Dateisystem wird ``traditionell'' auch heute noch als Standard für Linux eingesetzt, es wird wenigstens theoretisch von allen Linux-Installationen unterstützt. Seine einfache Struktur macht es zum bevorzugten Objekt dieser Erklärung.

Der Massenspeicher, sei es eine Diskette oder eine Festplattenpartition, stellt sich dem Betriebssystem zuerst als eine lineare Kette gleichgroßer Blöcke dar. Typischerweise sind diese Blöcke genau ein Kilobyte, das sind 1024 Bytes, groß.

**Abbildung A.1:** Sechs Bereiche des Dateisystems
$\begin{figure} \unitlength 3.9mm \begin{picture} (32.5,4) \put(2.5,0){\begin{pi... ...\put(26,2){\makebox(2,1){Daten}} \end{picture}\par \parbox{12.9cm}{}\end{figure}$

Das Minix-Dateisystem unterteilt diese Kette in sechs Bereiche. Der Aufbau ist in Abbildung A.1 dargestellt.

Die Proportionen der Bereiche sind für ein Minix-Dateisystem auf einer 3,5-Zoll-HD-Diskette dargestellt. Der Bereich für die Daten ist dabei stark verkürzt. Bei einer Gesamtzahl von 1440 Datenblöcken werden jeweils ein Block als Bootblock, Superblock, als I-Node-Bitmap und als Datenzonen-Bitmap verwendet. Weitere 15 Blöcke enthalten die I-Nodes, der gesamte Rest steht für Daten zur Verfügung.

**Abbildung A.3:** Minix Superblock **Abbildung A.2:** Minix-I-Node

I-Nodes

Der logistische Kern des Dateisystems sind die I-Nodes (Informations-Knoten). Für jede Datei existiert eine dieser Datenstrukturen, deren zentrale Komponenten die Zeiger auf die eigentlichen Datenzonen der Datei sind. Die Datenzonen bestehen aus einer konstanten Anzahl Datenblöcke. Ebenso wie die Blöcke sind auch die Zonen wie eine Kette aneinandergereiht. Damit sind die Datenzonen über ihre Nummer adressierbar. Ein Zeiger auf eine Datenzone enthält also die Nummer der Datenzone als Adresse. Wenn ein Zeiger unbenutzt ist (zum Beispiel, weil die Datei 0 Bytes, also keine Daten enthält), ist die Adresse Null.

**Abbildung A.4:** Direkte und Indirekte Zuordnung der Datenzonen zu einer Datei

Die Datenzonen können theoretisch mehrere Blöcke groß sein, bei der normalen Konfiguration entsprechen sie genau einem Block. Damit wird für jedes angefangene Kilobyte Daten ein Zeiger benötigt.

Um die Verwaltung der Datenstruktur einfach zu halten und damit die Performance des Dateisystems zu verbessern, sind alle I-Nodes gleich groß (beim Minix-Dateisystem sind es 32 Bytes). Mit der festgelegten Größe ist zwangsläufig auch die Anzahl der Zeiger in der I-Node beschränkt. Beim Minix-Dateisystem lassen sich höchstens sieben Datenzonen direkt aus der I-Node adressieren. Weil die Beschränkung auf eine Dateigröße von 7 Kilobyte inakzeptabel ist, werden weitere Datenzonen indirekt adressiert. Dazu gibt es einen Zeiger auf einen Datenblock, der nichts anderes als Zeiger auf die eigentlichen Datenzonen enthält.

Bei der Realisierung von Zonenzeigern durch vorzeichenlose Zweibytezahlen (unsigned short) können mit einem indirekten Zeigerblock 512 Datenzonen adressiert werden, was die maximale Dateigröße auf immerhin 519 Kilobyte erhöht. Weil diese Einschränkung aber immer noch unbefriedigend ist, gibt es die doppelt indirekte Adressierung. Der doppelt indirekte Zeiger zeigt auf einen Datenblock, der nur Zeiger auf einfach indirekte Zeigerblöcke in der oben besprochenen Art enthält. Auf diese Weise lassen sich 262663 Datenzonen adressieren. Das sind über 256 Megabyte, die aber wegen der Einschränkung des Minix-Dateisystems auf 64 Megabyte Partitionen nicht ausgenutzt werden können.

Die Abbildung A.4 stellt diese Verbindung zwischen der I-Node und den Datenzonen dar.

Außer den Zeigern auf die Datenzonen enthalten die I-Nodes noch andere Informationen. Hier sind der Eigentümer und die Gruppe der Datei mit den jeweiligen Zugriffsrechten (Permissions) gespeichert, es gibt Informationen über den Dateityp, die Größe, die Anzahl der Links und das Datum der letzten Veränderung (mtime). Der Kernel liest bei jedem Zugriff eines Benutzers auf eine Datei die entsprechende I-Node und stellt fest, ob dieser Benutzer die erforderlichen Rechte für den angeforderten Zugriff hat. Nur, wenn der Zugriff erlaubt ist, wird die entsprechende Lese- oder Schreiboperation durchgeführt.

Verzeichnisse

Jeder Eintrag in ein normales Minix-Verzeichnis wird in einem 16 Byte großen Feld gespeichert. Die ersten zwei Bytes enthalten die Nummer der zur Datei gehörenden I-Node, sie sind also ein Zeiger auf eine I-Node. Die darauffolgenden vierzehn Bytes enthalten den Dateinamen. Wenn der Dateiname kürzer als vierzehn Zeichen ist, werden die restlichen Bytes durch Nullen aufgefüllt.

Eine Linux-spezifische Erweiterung des Minix-Dateisystems ermöglicht die Verwendung von Dateinamen bis zu einer Länge von 30 Zeichen, wenn das mkfs.minix-Kommando bei der Erzeugung des Dateisystems mit der entsprechenden Option (-n30) aufgerufen wurde.

Jedes Verzeichnis enthält mindestens zwei Einträge, den Punkt und den Doppelpunkt. Der Zeiger des Doppelpunkt-Verzeichnisses zeigt auf die I-Node des übergeordneten Verzeichnisses, der Eintrag mit dem einfachen Punkt zeigt auf die I-Node des Verzeichnisses selbst. Diese beiden Einträge sind nötig, um ein Verzeichnis oder eine Datei relativ vom aktuellen Verzeichnis aus benennen zu können, zum Beispiel um ein übergeordnetes Verzeichnis anzuzeigen.

Superblock und Bitmaps

Der erste Block einer Diskette oder einer Partition kann ein Programm zum Laden des Betriebssystems, den sogenannten Boot-Loader, enthalten. Deshalb heißt dieser Block Bootblock. Er wird beim Einschalten des Rechners gelesen und ausgewertet, das eigentliche Dateisystem fängt erst mit dem zweiten Block, dem Superblock, an.

Der in Abbildung A.3 dargestellte Superblock des Minix-Dateisystems enthält Daten über den Typ und den Aufbau des Dateisystems. Mit einer magischen Zahl unterscheidet das Betriebssystem die unterschiedlichen Dateisystemtypen.

Durch die Anzahl der I-Nodes und die Anzahl der Datenzonen ist die Größe des Dateisystems bestimmt.

Weitere Strukturen, die zur Verwaltung des Minix-Dateisystems verwendet werden und deren Größe im Superblock festgehalten wird, sind die sogenannten Bitmaps. Es gibt je eine Bitmap für die I-Nodes und für die Datenzonen. Jeder I-Node beziehungsweise jeder Datenzone ist ein Bit in der entsprechenden Bitmap zugeordnet. Wenn die Zone oder die I-Node benutzt ist, wird das entsprechende Bit gesetzt.

Wenn der Kernel eine freie I-Node oder eine freie Datenzone braucht, weil eine neue Datei angelegt werden soll oder eine bestehende erweitert wird, kann mit diesen Bitmaps sehr schnell die nächste freie Stelle gefunden werden.

Datenzonen und Plattenblöcke

Die Datenzonen des von Linux verwendeten Minix-Dateisystems entsprechen in ihrer Größe genau den Plattenblöcken. Deshalb ist die begriffliche Unterscheidung vielleicht etwas verwirrend, jedenfalls erscheint sie unnötig. Die interne Realisierung dieser Trennung erlaubt es aber, mehr als einen Plattenblock je Datenzone zu verwenden, indem der Superblock entsprechend verändert wird.

Auf diese Weise könnte die Beschränkung des Minix-Dateisystems auf 64 Megabyte je Partition überwunden werden. Weil aber die Veränderung der Zonengröße auf zwei oder mehr Blöcke eine Verschwendung von kostbarem Plattenplatz wäre, ist mit den neuen Linux-Dateisystemen ein anderer Weg eingeschlagen worden.

Die Anzahl der Blöcke je Datenzone ist im Superblock nicht direkt gespeichert, weil das Betriebssystem diese Zahl niemals verwendet. Stattdessen ist der Logarithmus dieser Zahl im Superblock festgehalten. Diese Zahl gibt die Anzahl der Schiebeoperationen (shifts) an, die notwendig sind, um aus einer Zonenadresse die entsprechende Blockadresse zu ermitteln.

Links

Wie bereits oben erklärt wurde, bestehen die Einträge eines Verzeichnisses aus dem Dateinamen und einem Zeiger auf die zu der Datei gehörende I-Node. Der einzige Zugang zu einer Datei wird durch die I-Node hergestellt. Dieser festgelegte Weg erlaubt es auf einfache Weise, mehrere Verzeichniseinträge für ein und dieselbe Datei zu erzeugen.

Die Verbindung einer I-Node (und der damit über die Zonenzeiger verbundenen Datei) mit einem Verzeichniseintrag wird als Link bezeichnet. Mit dem ln-Kommando ( $\to$ Seite

) kann ein solcher Link auf eine bestehende Datei erzeugt werden. Das Kommando erzeugt einfach einen neuen Eintrag im aktuellen oder einem anderen angegebenen Verzeichnis und benutzt den I-Node-Zeiger der bestehenden Datei.

Weil die I-Node Bestandteil des Dateisystems einer in sich geschlossenen Partition ist, können solche ,,harten`` Links nur innerhalb einer einzigen Partition bzw. einer einzigen Diskette erzeugt werden. Um Links über die Partitionsgrenzen hinweg zu ermöglichen, bietet Linux sogenannte symbolische Links an. Die symbolischen Links werden als spezieller Dateityp im Verzeichnis eingetragen und belegen im Fall des Minix-Dateisystems vier Datenzonen. In diesen Zonen ist der Zugriffsweg auf die Datei gespeichert. Es ist auch möglich, daß ein symbolischer Link ins Leere zeigt, zum Beispiel, wenn die Datei, auf die er zeigen sollte, gelöscht wurde.

Links auf Verzeichnisse

Zusätzliche, harte Links auf ein Verzeichnis würden die Baumstruktur der Verzeichnishierarchie zerstören und könnten leicht zu endlosen Rekursionen führen.

Die bessere, erlaubte Lösung zum Erzeugen zusätzlicher Zugänge für Verzeichnisse sind symbolische Links.