Beitrag aus c't 10/86 Das Betriebssystem des Atari ST Directory und Fat regenerieren Frank Middel Hoffentlich haben Sie Ihre versehentlich gel”schten Files noch nicht aufgegeben, berschrieben, oder ihnen „hnlich schlimmes angetan. Schliežlich - auch wenn es einen Monat l„nger gedauert hat - haben Sie nun eine gute Chance, Ihre Daten auf Diskette wieder herzustellen. Aus der letzten Folge dieser Serie (c't 8, Seite 72 ff.) erfuhren wir einiges ber die Diskettenverwaltung unter TOS. Unter anderem wie Dateien auf Diskette gespeichert werden, und was beim L”schen einzelner Dateien genau passiert: Wirft man ein File in den Papierkorb, oder l”scht es auf Command-Ebene, besteht es danach noch immer in voller Gr”že auf Diskette - es wurde eben 'nur' logisch gel”scht. Bemerkt man zu diesem Zeitpunkt, daž die Datei eigentlich noch ben”tigt wird, so ist es mit 99 prozentiger Wahrscheinlichkeit m”glich, sie unversehrt zu entl”schen. Wird die Diskette jedoch weiterhin Schreibvorg„ngen ausgesetzt, so ist ebenfalls ziehmlich sicher, daž die Daten nun (zumindest teilweise) endgltig futsch sind - es wurde berschrieben und somit physikalisch gel”scht. Waren es zudem noch sehr wichtige Daten, empfiehlt es sich, erst einmal einen Kaffee trinken zu gehen... D I R E C T O R Y Wie wir bereits wissen, beschr„nkt sich TOS beim L”schen von Files nicht allein auf das Directory, sondern vernichtet ebenfalls die Verkettungsinformationen im FAT ("File Allocation Table") und gibt somit den vorher belegten Speicherplatz einer Datei auf Diskette wieder frei. Um zu entl”schen, mssen also die Informationen im FAT wieder hergestellt und natrlich das erste Byte des Filenamen von 0xE5 in sagen wir 0x40 ge„ndert werden. Aber alles sch”n der Reihe nach; denn um die FAT-Eintr„ge zu regenerieren, ben”tigen wir 2 Informationen: den Startcluster und die L„nge des Files. Diese Daten findet man, ebenso wie das zu „ndernde erste Byte des Filenamen, im Directory. Logischer Sektor Inhalt 00 Bootsektor 01 ... 05 FAT Nr.1 06 ... 10 FAT Nr.2 11 ... 17 Directory 18 ... 79 Datenbereich Wie Sie aus obiger Tabelle entnehmen k”nnen, belegt das Directory nach dem Bootsektor und den 2 FATs, die Sektoren 11 bis 17. Danach beginnt der Bereich, in dem die eigentlichen Daten der einzelnen Files abgelegt sind. Jeder Dateieintrag im Directory ist 32 Byte lang und umfažt folgende Informationen: - Dateiname mit Extension - Dateiattribut - Uhrzeit - Datum - Startcluster - Dateil„nge Die einzelnen Bytes eines Eintrags sind wie folgt abgelegt: Byte 0 bis 7: Hier ist der Dateiname abgelegt. Er ist maximal 8 Zeichen (Grožbuchstaben) lang, wobei das erste Byte spezielle Bedeutung hat. Steht an dieser Stelle 0x00, so handelt es sich um einen freien Directory-Eintrag. Der Wert 0x2E bedeuted, daž man es mit einem Teilverzeichnis zu tun hat, und 0xE5 markiert eine gel”schte Datei. Byte 8 bis 10: Drei Zeichen (Grožbuchstaben), die die Extension einer Datei bilden. Byte 11: Das Dateiattribut erlaubt es, weitere Informationen einer Datei zuzuordnen. Hierzu werden die einzelnen Bits wie folgt gesetzt: Bit 0: Datei hat 'Read only'-Status, d.h. sie darf nur gelesen werden. Somit ist sie softwarem„žig schreibgeschtzt. Bit 1: Datei wird nicht im Inhaltsverzeichnis angezeigt; sie ist unsichtbar. Bit 2: Datei ist eine Systemdatei und wird ebenfalls nicht angezeigt. Bit 3: Zeichenkette ist nicht der Name einer Datei, sondern die Kennzeichnung der Diskette ('Volume label'). Bit 4: Eintrag eines Teilverzeichnisses. Bit 5: Von TOS nicht benutzt. Byte 12 bis 21: Reserviert. Byte 22 bis 23: In diesen 16 Bits ist die Zeitinformation der Datei abgelegt. Die Bits 0 bis 4 enthalten die Sekunden, Bits 5 bis 10 die Minuten und die Bits 11 bis 15 schliežlich die Stunden. Byte 24 bis 25: Das Datum ist, genau wie die Zeit, eine 16 Bit-Information. Hier ist die Belegung der einzelnen Bits folgende: Bits 0 bis 4 liefern den Tag, Bits 5 bis 8 den Monat und Bits 9 bis 15 das Jahr, beginnend bei 1980. Byte 26 bis 27: Hierbei handelt es sich um den Startcluster der Datei. Wir ben”tigen diesen sp„ter unbedingt fr die Rekonstruktion der zerst”rten FAT-Eintr„ge. Byte 28 bis 31: Dieses Langwort liefert die Dateil„nge in Bytes. Diese Vielzahl von Daten, Bytes und Bits beschreibt also alle Einzelheiten einer auf Platte gespeicherten Datei. Aber keine Angst, denn wie ich bereits erw„hnte, ben”tigen wir allein das erste Byte des Dateinamen, den Startcluster und die L„nge des gel”schten Files. Da wir nun alle notwendigen Informationen zusammengetragen haben, besch„ftigen wir uns jetzt mit dem Wesentlichen - dem Entl”schen. D I E V O R G E H E N S W E I S E Wie wir wissen, ist das Verfahren mit dem TOS Cluster fr eine Datei allokiert recht simpel: Ben”tigt ein File weiteren Speicherplatz auf Diskette, so werden Cluster zugewiesen, indem sequentiell nach dem n„chsten freien Cluster, der sich im FAT finden l„žt, gesucht wird. Ist eine freie FAT-Position gefunden worden, steht dort also in den nieder- oder h”herwertigsten 12 Bits der Wert 0x000, so wird an dieser Stelle der neue Cluster eingetragen. Diese Cluster-Nummer ist dann gleichzeitig der Zeiger auf die n„chste FAT-Position, wo sich erneut eine Cluster-Nummer befindet, die wiederum ein Zeiger....und so weiter und so fort. Gehen wir also davon aus, daž Cluster fr eine Datei stets aufsteigend allokiert werden (z.B. 3,4,8,12), denn nur dann ist ein Algorithmus in der Lage die FAT-Eintr„ge automatisch und richtig zu regenerieren. Liegt der Sachverhalt anders, wurden aus irgend einem Grund die Cluster 12,4,6 und 3 allokiert, dann haben wir schlechte Karten. Die einzigste M”glichkeit, die dann noch besteht, ist per Hand die einzelnen Cluster zuzuordnen. Aber vielleicht hat man ja Glck ! Doch vergessen Sie diesen Mižstand erst einmal, denn unser Ziel ist es schliežlich, ein Programm zu erstellen, welches uns zumindest diejenigen Dateien wieder auf Diskette bringt, deren Cluster aufsteigend allokiert wurden. Im Prinzip ist das Entl”schen einer solchen Datei recht einfach: Man holt sich zun„chst den Startcluster des Files und dessen L„nge aus dem Directory. Anschliežend werden ab der ersten FAT-Position (= Starcluster+Startcluster/2) so viele freie Cluster allokiert, bis die L„nge der Datei aufgebraucht ist. Um dieses Verfahren bewerkstelligen zu k”nnen, brauchen wir jedoch noch ein paar Parameter, wie z.B. die L„nge der Cluster in Sektoren bzw. in Bytes. Da unser Programm ausschliežlich mit den Standard-Diskettenformaten des ST arbeiten soll, k”nnen wir diese Daten konstant halten, d.h. wir brauchen nicht immer wieder den BPB (Bios Parameter Block) zu befragen. Die Daten des BPB fr 80 Track single sided und double sided Laufwerke entnehmen Sie bitte der Abbildung weiter unten. E I N B E I S P I E L Die grunds„tzliche Vorgehensweise beim Entl”schen von Dateien ist Ihnen ja jetzt klar. Da jedoch bei dieser Methode Probleme auftreten k”nnen, sobald Allokierungslcken vorhanden sind, m”chte ich Ihnen das komplette und richtige Verfahren an einem Beispiel demonstrieren. Zuerst erzeugen wir mit einem Editor drei Dateien, mit folgenden L„ngen: ERSTE .DAT 26 BYTES ZWEITE.DAT 29 BYTES DRITTE.DAT 2197 BYTES Nun werden diese 3 Files hintereinander auf eine neue, frisch formatierte Diskette kopiert. Die ersten Bytes im FAT sehen anschliežend so aus: Byte: 0 1 2 3 4 5 6 7 8 9 A B Inhalt: 000000FFFFFF056000FF0F000..... Aus der letzten Folge wissen wir, daž die Datei DRITTE.DAT die Cluster 4,5 und 6 belegt. Diese merken wir uns, damit wir sp„ter wissen, ob wir richtig entl”scht haben. Jetzt l”schen wir DRITTE.DAT und schauen uns erneut die ersten FAT-Eintr„ge an: Byte: 0 1 2 3 4 5 6 7 8 9 A B Inhalt: 000000FFFFFF0000000000000..... Nun, es sind natrlich die FAT-Eintr„ge an den Positionen vernichtet worden, die Cluster des Files DRITTE.DAT enthielten. Dies waren die FAT-Positionen 6,7 und 9. Auch diese Positionen merken wir uns fr sp„ter! Um unser gel”schtes File wieder auferstehen zu lassen, nehmen wir den Startcluster und errechnen die Position des ersten FAT-Eintrags (Startcluster * 1.5 oder Startcluster + Startcluster / 2). An diese Position mssen wir dann den Zeiger auf die n„chste freie FAT-Stelle schreiben. Und zwar in die niederwertigsten 12 Bits, da die letzte Cluster-Nummer gerade war. Dieser Wert ist auch gleichzeitig der n„chste Cluster unserer Datei. Zur Auffindung der folgenden freien FAT-Position muž nun folgendes beachtet werden: - ist der Zeiger auf diese Stelle gerade ( int(FAT-Stelle / 1.5) ), so mssen die unteren 3 Nibbles auf 0x000 untersucht werden. - ist der Zeiger auf diese Stelle ungerade, so mssen die oberen 3 Nibbles auf 0x000 untersucht werden. Hat man auf diese Weise eine weitere freie Stelle im FAT aufgetrieben, tr„gt man den Wert int(Position / 1.5) in die richtigen 3 Nibbles der vorhergehenden FAT-Position ein und hat somit die Cluster-Nummer des Files errechnet. In unserem Fall w„re das die Stelle 7 im FAT. Der Zeiger auf diese Position ist demnach int(7/1.5), also 4. Diesen Wert tragen wir nun in die untersten 3 Nibbles des Wortes, das wir an Stelle 6 finden. Der erste Cluster w„re also rekonstruiert ! Aber vor aller Freude nicht vergessen, die L„nge des Files um die Anzahl der Bytes eines Clusters (1024) zu dekrementieren. Jetzt muž natrlich immer weiter so verfahren werden, bis die L„nge von DRITTE.DAT aufgebraucht, d.h. kleiner oder gleich 0 ist. In die so erhaltene letzte FAT-Position tr„gt man abschliežend, selbstverst„ndlich in die richtigen 3 Halbbytes, die Endemarkierung 0xfff ein. Abschliežend wird lediglich noch das erste Byte im Filenamen unserer Datei umge„ndert, und schon mžte DRITTE.DAT wieder in voller Pracht im Directory erscheinen und auch den alten Inhalt haben. S O N I C H T Schaut man nun erwartungsvoll ins Directory, stellt man triumphierend fest, daž die zuvor gel”schte Datei DRITTE.DAT tats„chlich wieder existiert. L„žt man sich jetzt den Inhalt anzeigen, sieht man jedoch, daž dieser nicht so ganz der alte ist. Aber warum ? Na, warum wohl ? Richtig, das Problem der Allokierungslcken ist aufgetreten und wurde von unserer Verfahrensweise nicht richtig behandelt; und zwar aus folgendem Grund: Es darf eben doch nicht jede freie FAT-Position benutzt werden ! Wie war das in unserem Beispiel ? Die Datei DRITTE.DAT hatte den Startcluster 4. Damit war die erste Position im FAT die Byte-Grenze an der Stelle 6. Die n„chste freie Stelle war 7, also trugen wir 4 in Position 6 ein. Genau das ist falsch, denn 4 * 1.5 ist 6 und nicht 7. Wir haben also einen Zeiger auf die FAT-Position 6 gerichtet, doch auf diese ist schon durch den Startcluster verwiesen! Auf der Suche nach dem n„chsten freien FAT-Eintrag, stiežen wir auf die Position 8. Daraufhin schrieben wir in Stelle 7 den Wert int(8/1.5), also 5. Dies war natrlich ebenso falsch, denn eigentlich h„tte ein Zeiger auf die Stelle 9 eingetragen werden mssen. (Wir hatten uns doch die FAT-Stellen gemerkt: 6,7 und 9) G E S C H A F F T ! Die L”sung ist einfach und auch das besprochene Verfahren muž nur um einen Punkt erweitert werden. Natrlich ist eine Clusternummer im FAT gleichzeitig auch ein Zeiger auf die n„chste benutzte FAT-Stelle. M”chte man den Zeiger auf eine solche FAT-Position errechnen, so gilt aber: zeiger = position / 1.5 + 0.5 . Jedoch muž dabei bedacht werden, daž es Zahlen gibt, die nicht durch Multiplikation von 1.5 mit einer beliebigen anderen ganzen Zahl ge- bildet werden k”nnen. (Die 8 z.B. ist eine solche Zahl !) Wir drfen also nicht den erstbesten FAT-Eintrag benutzen, sondern den ersten, der aus der Multiplikation von 1.5 mit einer ganzen Zahl gebildet werden kann. In unserem Beispiel w„re das die Position 9 gewesen (denn 6 * 1.5 ist 9 !). Somit w„re dann auch unser File DRITTE.DAT korrekt rekonstruiert worden. P R O G R A M M R E C A L L . C Das folgende Programm fhrt genau den besprochenen Arbeitsgang durch. Es ist demnach in der Lage, gel”schte Files, die von TOS aufsteigend allokiert wurden, korrekt zu entl”schen. Werden vor der ersten FAT-Stelle, die der Startcluster liefert, weitere freie FAT-Positionen gefunden, so kann der Benutzer entscheiden, ob das Entl”schen nicht, oder trotzdem durchgefhrt werden soll. Hierzu muž noch gesagt werden, daž der erste m”gliche Cluster einer Datei nicht 0 ist, sondern 2. Wieso ? Ganz einfach: Um von Cluster in logische Sektoren umzurechnen, wird die folgende Formel benutzt: (Cluster - 2) * 2 + 18 So ergibt sich Clusternummer 2 als erster logischer Sektor des Datenbereichs auf Diskette. Klar ? Demnach muž, bei der Suche nach freien FAT-Eintr„gen vor dem Startcluster, erst ab der FAT-Position 3 gesucht werden. Alles in allem braucht man schon einige Erfahrung um zu erkennen, ob eine freie FAT-Position vor dem Startcluster zur Datei ge- h”rt, oder nicht. Dazu sollten Sie sich ein paar Disketten mit gel”schten Files herstellen und ein bischen mit dem Programm rumprobieren, bevor Sie an wichtigere Daten gehen. Wichtig ist noch, daž dieses Programm keinerlei Abfragen in Bezug auf Ordner macht. Files, die in solchen Ordnern stehen k”nnen also nicht entl”scht werden. Die verwendeten GEMDOS- und BIOS-Funktionen sind die gleichen wie in der letzten Folge. Nur GEMDOS(0x00) macht eine Ausnahme; sie wird an manchen Stellen zur radikalen Terminierung des Programms verwendet. Natrlich ist das Programm kein Genuž fr diejenigen, die sich befleižigen stets strukturiert zu programmieren. Dennoch hat es den Vorteil auch von C-Novizen verstanden zu werden. A N R E G U N G E N Wie Sie sehen, k”nnte man ber das Entl”schen von Dateien B„nde schreiben. (Vielleicht ein Sonderheft oder...) Deshalb zum Schluž noch ein paar Tips: Denn was tun, wenn sich ein File in einem Ordner befindet ? Das Programm kann Ihnen hier nicht mehr weiterhelfen, also mssen Sie selbst etwas tun. Sie k”nnen dazu das Programm so umschreiben, daž Ordner erkannt werden. Ist das getan, braucht nur noch der logische Sektor errechnet zu werden, in dem sich der Eintrag des Files befindet. Dazu wird der Startcluster des Ordners in einen logischen Sektor umgerechnet (Formel steht weiter oben !). Mit dem erhaltenen Sektor wird dann ganz normal verfahren. Das heižt: Suche nach 0xe5-Byte und entl”schen. Wie das geht, mžte jetzt eigentlich klar sein.