FAT - Dateizuordnungstabelle

« | 11 Feb 2024 | »

Das FAT Dateisystem war in den 90igern die absolute Nummer ein am PC und wurde erst nach dem Jahr 2000 mit Windows XP durch NTFS bzw durch Linux mit ext2/3 ersetzt.

Für meine Retro-PC und Disketten Experimente benötige ich ein Tool zum Auslesen der alten Datenträger, also implementiere ich mir eine FAT12/16 Reader schnell selbst.

---

Ein paar Daten und Fakten zu FAT

Auf Disketten ist FAT12 auch heute noch die Nummer 1. Weder Linux noch WinNT wagten und wagen es, hier ein anderes Dateisystem aufzuspielen.
FAT16 konnte damals Festplattenpartitionen bis knapp 2 GB bedienen und wird heute noch in kleinen SD-Karten z.B. am Mikrokontroller benutzt.
Und FAT32 haben wir fast überall im Einsatz, weil jeder USB Stick und jede übliche SD Karte damit formatiert ist, und die meisten Anwender nutzen bekanntlich genau so, wie es aus der Packung kam.

Die Idee von FAT war, dass der Datenträger in “Cluster” unterteilt wird. Auf Disketten war ein Cluster genau ein Sektor groß, doch auf größeren Medien wurden mehrere Sektoren zu einem Cluster zusammengefasst.
FAT12 hat (Wer errät es?) eine 12-bit breite Clusteradressierung und kann etwa 4000 Cluster verwalten (genau 4084, weil ein paar IDs reserviert sind). FAT16 schafft 65000 Cluster (genau 65524) und FAT32 kommt auf 268 000 000 (genau 268435444) weil nur 28 bit und noch die vollen 32 bits benutzt werden.

Ein 1-Sektor-Cluster (512 Bytes) unter FAT16 könnte nur 32 MB große Laufwerke verwalten. Mit 2-Sektor großen Clustern (1024 Bytes) verdoppelt sich das auf 64 MB, bis man mit einer Clustergröße von 64 Sektoren (32 KB) erreicht hat und damit knapp 2 GB adressieren kann.

Windows NT konnte auch 128 Sektoren (64 KB) zusammen-clustern und damit 4 GB ansprechen, doch da spielten DOS und Windows 3x/9x nicht mit. Unter DOS ist das fast logisch, weil man mit einem 64 KB großen Datenblock ein Speichersegment zum Überlaufen gebracht hätte.

FAT12 Implementierung

FAT12 ist für mich deshalb interessant, weil ich ja meine alten Toshiba Disketten auslesen möchte. Daher startete ich in der gate/tech Bibliothek ein Modul für Dateisystemstrukturen.

Im ersten Sektor (Bootsektor) einer Diskette befindet sich im “BIOS Parameter Block” (kurz BPB) eine Auflistung wichtiger Kennzahlen des Dateisystems, wie etwa Anzahl der Sektoren, Sektoren pro Cluster, Länge des Stammverzeichnisses.
Mit diesen Infos kann man später die logischen Sektorpositionen ausrechnen, um zu den Nutzdaten zu kommen.

Grundsätzlich liegen die in den Sektoren so hintereinander:

• Reservierte Sektoren
  • Bootsektor
  • Optional andere unbenutzte Sektoren
• FAT Sektoren
  • FAT-1 (Primäre FAT)
  • FAT-2 (Kopie der FAT als Backup für Reparatur)
• Stammverzeichnis Sektoren
• Cluster Sektoren
  • Dateifragmente

Daraus ergeben sich folgenden Formeln:

• first_fat_sector = bpb.reserved_sectors
• total_fat_sectors = bpb.sectors_per_fat * bpb.fat_copies
• root_dir_sectors = bpb.root_dir_entries / 32
• total_cluster_sectors = bpb.total_sectors - (bpb.reserved_sectors + total_fat_sectors + root_dir_sectors)
• total_cluster_count = total_cluster_sectors / bpb.sectors_per_cluster
• first_cluster_sector = bpb.reserved_sectors + total_fat_sectors + root_dir_sectors

Das Stammverzeichnis hat also unter FAT immer eine feste Länge und kann nicht nachträglich wachsen (außer man strukturiert den ganzen Datenträger neu).

FAT Funktionsweise

Die FAT selbst speichert für jeden Cluster eine Zahl der anzeigt, ob damit ein weiterer Cluster verknüpft ist. Es ist also eine Single-Linked-List.

Ein Dateieintrag im Stammverzeichnis (oder Unterverzeichnis) nennt den ersten Cluster einer Datei. Den kann man mal auslesen. Dann sieht man in der FAT nach, was in dessen Clusterliste steht und findet dort entweder die nächste Cluster-Nummer oder eine “Ende-Markierung”.

Die logischen Cluster-IDs 0 und 1 sowie die größten 9 am Ende sind reserviert.

• 0 bedeutet, dass ein Cluster unbenutzt ist
• ffff (also die höchste ID in FAT16) steht für “Ende”, es sind also keine weiteren Cluster mehr mit der Datei (Clusterkette) verknüpft.

Index	Inhalt	Bedeutung
#2	3	Cluster 2 verlinkt auf 3
#3	4	Cluster 3 verlinkt auf 4
#4	ffff	Ende erreicht
#5	0	Cluster ist frei
#6	ffff	Ende erreicht
#7	0	Cluster ist frei
#8	0	Cluster ist frei

Spezialfall FAT12

Während FAT16 und FAT32 einfach 16 und 32-bit Werte hintereinander in die FAT schreiben, sind bei FAT12 immer zwei Einträge in 3 Bytes verschränkt.
Die logischen Clusternummern 0x0aaa und 0x0bbb werden in FAT12 als
aa ba bb gespeichert.

Das wirkt auf den ersten Blick komisch, macht aber in der 8-bit Little-Endian-Welt von X86 total Sinn.
Liest man nämlich den 16-bit Wert von Adresse 0 und dann von Adresse 1, erhält man die Werte 0xbaaa und 0xbbba.

Jetzt braucht man den ersten nur noch mit AND 0x0fff verknüpfen und den zweiten um 4 Bits nach links verschieben und schon hat man die gewünschten Werte von 0x0aaa und 0x0bbb.

Fazit

FAT ist gar nicht so schwer.

Gut, ein paar Rechenfehler macht man am Anfang, wenn man die Cluster, die bei 2 zu zählen anfangen, dann auch genau so zum ausrechnen der Sektoren nimmt und man dann daneben liegt … aber mit einer Referenzdiskette findet man das schnell selbst heraus, fügt das -2 in die Formel ein und alles ist gut.

Spannend sind so Sachen wie, dass man Pseudo-Hardlinks erstellen konnte, wenn einfach zwei Dateieinträge auf den gleichen Start-Cluster zeigten. Das ist in FAT eigentlich nicht erlaubt, doch ich hatte sogar noch so ein alte Diskette mit einem manipulierten Inhaltsverzeichnis.

Ein großes Lob geht an Seiten wie wiki.osdev.org, die den Aufbau wunderbar bildlich dargestellt haben. So konnte ich meine selbsterstellte Erstimplementierung gegenprüfen und korrigieren.