Ext2-Dateisystem in C: mkdir, ln, rm, restore, checker

Einführung in ext2-Dateisysteme

Das ext2-Dateisystem (Second Extended Filesystem) war lange das Standard-Dateisystem vieler Linux-Distributionen. Auch heute noch ist es ein hervorragendes Lernobjekt, um die Grundlagen von Dateisystemen zu verstehen – besonders, wenn du in C arbeitest. In diesem Tutorial lernst du, wie du typische Operationen wie mkdir, ln, rm, restore und einen Dateisystem-Checker implementierst. Das Wissen ist direkt anwendbar für Assignment 4 in Csc369 und hilft dir, binäre Datenstrukturen sowie Inodes, Blockgruppen und Superblöcke zu manipulieren.

Stell dir vor, du entwickelst ein Tool, das eine virtuelle Festplatte im ext2-Format analysiert und repariert – ähnlich wie ein System-Checker in modernen Betriebssystemen. Oder du baust einen Datei-Explorer für ein Retro-Spiel, das ext2 verwendet. Aktuelle Trends wie Cloud-Speicher und Container-Dateisysteme bauen auf ähnlichen Konzepten auf. Mit diesem Tutorial legst du das Fundament.

Grundlagen: ext2-Strukturen

Bevor du loslegst, musst du die wichtigsten Datenstrukturen verstehen:

Superblock: Enthält Metadaten wie Anzahl freier Blöcke und Inodes.
Blockgruppe: Jede Gruppe hat einen eigenen Block- und Inode-Bitmap.
Inode: Repräsentiert eine Datei oder ein Verzeichnis mit Metadaten (Größe, Berechtigungen, Zeitstempel).
Directory Entry: Ein Eintrag in einem Verzeichnis, der Name und Inode-Nummer verknüpft.

Ein ext2-formatierter virtueller Datenträger ist nichts anderes als eine Datei, die diese Strukturen enthält. Du liest und schreibst direkt mit fread/fwrite auf Blockebene (meist 1024 Bytes).

ext2_mkdir: Verzeichnis anlegen

Dein Programm ext2_mkdir erhält den Pfad zu einem Datenträger und einen absoluten Pfad. Es soll das letzte Verzeichnis im Pfad erstellen.

Schritte:

Öffne die Datenträger-Datei im binären Lese-/Schreibmodus.
Lese den Superblock (Offset 1024) und die Blockgruppe-Deskriptoren.
Pars den Pfad: Überprüfe, ob alle Elternverzeichnisse existieren. Falls nicht, gib ENOENT zurück.
Prüfe, ob das Zielverzeichnis bereits existiert (dann EEXIST).
Allokiere einen neuen Inode (setze das entsprechende Bit im Inode-Bitmap).
Initialisiere den Inode: Setze i_mode auf Verzeichnis, i_links_count auf 2 (. und ..), Datumsfelder auf aktuelle Zeit.
Allokiere einen Datenblock für das Verzeichnis und schreibe die Einträge . (Inode = eigene) und .. (Inode = Elternverzeichnis).
Füge im Elternverzeichnis einen neuen Directory Entry hinzu (Name, Inode-Nummer; Einträge sind 4-Byte-aligned, Namen nicht nullterminiert).
Aktualisiere die Zähler im Superblock und Blockgruppen-Deskriptor.
Schließe die Datei.

Beispiel: Angenommen, dein Datenträger heißt disk.img und der Pfad /home/user/newdir. Wenn /home/user existiert, aber newdir nicht, wird es erstellt.

ext2_ln: Harte und symbolische Links

Mit ext2_ln erstellst du einen Link von einer Quelle zu einem Ziel. Standardmäßig ist es ein harter Link; mit der Option -s wird ein symbolischer Link erzeugt.

Harter Link

Quell-Inode muss existieren und kein Verzeichnis sein (außer mit speziellen Rechten).
Erhöhe i_links_count im Quell-Inode.
Füge im Zielverzeichnis einen neuen Directory Entry mit dem Zielnamen und derselben Inode-Nummer hinzu.

Symbolischer Link

Erstelle einen neuen Inode mit i_mode für Symlink.
Der Datenblock (oder Inode-Block bei kurzen Pfaden) enthält den Pfad der Quelle als Text.
Füge den Directory Entry im Zielverzeichnis hinzu.

Fehlerbehandlung: Wenn die Quelle nicht existiert, gib ENOENT zurück. Bei Zielkonflikten (z. B. existiert bereits) entsprechend EEXIST.

ext2_rm: Dateien und Verzeichnisse löschen

Das Löschen einer Datei oder eines Links (nicht Verzeichnis) umfasst:

Markiere den Directory Entry als gelöscht (setze inode auf 0).
Dekrementiere i_links_count im Inode.
Wenn i_links_count auf 0 fällt: Setze i_dtime auf aktuelle Zeit, markiere den Inode im Bitmap als frei, deallokiere Datenblöcke (Bitmap setzen, aber Daten nicht löschen).
Die Directory Einträge müssen nicht verschoben werden – die Lücke bleibt.

Bonus -r: Wenn -r angegeben ist, darfst du auch Verzeichnisse löschen. Dann musst du rekursiv alle Inhalte entfernen. Kopiere dazu deine ext2_rm in ext2_rm_bonus.c und erweitere sie.

Denk daran: Nach dem Löschen eines Verzeichnisses musst du auch die . und .. Einträge entfernen.

ext2_restore: Gelöschte Dateien wiederherstellen

Die Wiederherstellung nutzt die Tatsache, dass gelöschte Directory Einträge nicht überschrieben werden. Suche in den „Lücken“ des Elternverzeichnisses nach Einträgen mit inode = 0 und prüfe, ob der zugehörige Inode noch gültig ist (nicht neu allokiert).

Einschränkungen:

Wenn der Inode noch von einem anderen harten Link referenziert wird (i_links_count > 0), ist er nicht wirklich gelöscht – Wiederherstellung nicht nötig.
Wenn der Inode neu belegt wurde, darfst du nicht wiederherstellen (da nicht unterscheidbar von einem alten harten Link).

Vorgehen:

Finde den Directory Entry, der den gelöschten Namen enthält (suche in allen Verzeichnisblöcken nach inode = 0 und vergleiche den Namen).
Prüfe, ob der Inode im Bitmap als frei markiert ist. Wenn nicht, brich ab.
Setze den Inode im Bitmap wieder auf belegt, setze i_dtime auf 0, und setze den Directory Entry auf die ursprüngliche Inode-Nummer.

Bonus -r für Verzeichnisse: Ähnlich wie bei rm, mit rekursiver Wiederherstellung aller enthaltenen Dateien. Erstelle eine separate ext2_restore_bonus.c.

ext2_checker: Dateisystem-Konsistenzprüfung

Dein Dateisystem-Checker durchläuft die gesamte virtuelle Festplatte und sucht nach Inkonsistenzen. Er korrigiert sie und zählt die Anzahl der Korrekturen.

Prüfungen:

Superblock und Blockgruppen-Zähler: Vergleiche die Anzahl freier Blöcke/Inodes mit den Bitmaps. Stimmen sie nicht überein, vertraue den Bitmaps und aktualisiere die Zähler. Gib eine Meldung aus: Fixed: X's Y counter was off by Z compared to the bitmap, wobei X = superblock/block group, Y = free blocks/free inodes, Z = absolute Differenz.
i_mode vs. directory entry file_type: Für jede Datei, jedes Verzeichnis und jeden Symlink: Wenn der file_type im Directory Entry nicht zum i_mode des Inodes passt, korrigiere den file_type und gib Fixed: Entry type vs inode mismatch: inode [I] aus.
Inode-Allokation: Prüfe, ob jeder Inode, der in einem Directory Entry referenziert wird, im Inode-Bitmap als belegt markiert ist. Wenn nicht, setze das Bit und aktualisiere die Zähler. Gib eine entsprechende Meldung aus.

Der Checker sollte nach allen Korrekturen die Gesamtzahl der Fixes ausgeben.

Praktische Tipps und häufige Fehler

Alignment: Directory Einträge sind 4-Byte-aligned. Berechne die Länge des Eintrags als 8 + strlen(name) und runde auf das nächste Vielfache von 4 auf.
Nicht nullterminierte Namen: Die Länge des Namens ist im name_len-Feld gespeichert. Kopiere nur so viele Zeichen.
Byte-Reihenfolge: ext2 verwendet Little-Endian. Auf einem Big-Endian-System musst du die Bytes umdrehen.
Testen: Erstelle kleine virtuelle Datenträger mit dd und formatiere sie mit mke2fs. Verwende hexdump oder debugfs zur Überprüfung.

Beispiel: ext2_mkdir in Aktion

Angenommen, du hast eine disk.img mit einem leeren Root-Verzeichnis. Dein Programm erhält den Pfad /mein_ordner. Es wird:

Den Root-Inode (Nr. 2) lesen und die Directory Einträge durchgehen – es gibt nur . und ...
Einen neuen Inode allokieren (z. B. Nr. 12).
Einen Datenblock allokieren und . (Inode 12) und .. (Inode 2) schreiben.
Im Root-Verzeichnis einen neuen Eintrag für mein_ordner mit Inode 12 hinzufügen.

So einfach ist das!

Zusammenfassung

Mit diesem Tutorial hast du die Grundlagen für die Implementierung von ext2-Operationen in C gelernt. Du kannst jetzt mkdir, ln, rm, restore und einen Dateisystem-Checker programmieren. Diese Fähigkeiten sind nicht nur für Assignment 4 nützlich, sondern auch für das Verständnis moderner Dateisysteme. Viel Erfolg!