12. Feb 2024
Lesedauer 8 Min.
FAT12-Dateisystem
Das eigene Betriebssystem, Teil 15
Ein vollständiger FAT12-Treiber wird implementiert.
dotnetpro
[Link auf :]Die zurückliegende Folge dieser Serie [1] behandelte den Aufbau der Grundstrukturen einer Command-Shell. Die Command-Shell bietet nicht nur eigene Befehle an, sondern ist auch in der Lage, Anwendungsprogramme von der Festplatte zu laden und auszuführen.Diese letzte Folge der Serie zeigt nun, wie man ein Dateisystem implementiert. Dafür wird ein FAT12-Treiber entwickelt, der sowohl lesend als auch schreibend auf das FAT12-Dateisystem des Selbstbau-Betriebssystems zugreifen kann. Tabelle 1 gibt einen Überblick über die Funktionen, die dafür entwickelt und eingebaut werden.
Tabelle 1: Dateisystem-Funktionen
|
Das FAT12 Root Directory
Wie bereits aus den vorangegangenen Folgen dieser Artikelserie bekannt ist, nutzt das Selbstbau-Betriebssystem eine FAT12-Partition, die einerseits einen Boot-Sektor enthält und andererseits auch alle notwendigen Betriebssystem-Komponenten, wie beispielsweise den Kernel.Die Abkürzung FAT steht für File Allocation Table. Diese Datenstruktur beschreibt, aus welchen Teilen (Clustern) eine Datei oder ein Ordner im Dateisystem besteht. Ein Cluster hat hier eine Größe von 512 Bytes und ist damit genauso groß wie ein physischer Sektor auf der Festplatte. In unserer File Allocation Table werden zwölf Bits verwendet, um diese Cluster zu adressieren – davon leitet sich der Name FAT12 ab.Eine Datei kann maximal 4096 Cluster (212) zu jeweils 512 Bytes umfassen und hat somit eine maximale Größe von 2 MByte (4096 × 512 Bytes). Das FAT12-Dateisystem besteht aus den folgenden logischen Abschnitten (siehe auch Bild 1):
Die vier logischen Abschnitte des FAT12-Dateisystems (Bild 1)
Autor
- Boot-Sektor,
- FAT Tables,
- Root Directory,
- Data Area.
Listing 1: Die Struktur RootDirectoryEntry
<span class="hljs-keyword">struct</span> RootDirectoryEntry<br/>{<br/> <span class="hljs-keyword">unsigned</span> <span class="hljs-keyword">char</span> FileName[<span class="hljs-number">8</span>];<br/> <span class="hljs-keyword">unsigned</span> <span class="hljs-keyword">char</span> Extension[<span class="hljs-number">3</span>];<br/> <span class="hljs-keyword">unsigned</span> <span class="hljs-keyword">char</span> Attributes[<span class="hljs-number">1</span>];<br/> <span class="hljs-keyword">unsigned</span> <span class="hljs-keyword">char</span> Reserved[<span class="hljs-number">2</span>];<br/> <span class="hljs-keyword">unsigned</span> CreationSecond: <span class="hljs-number">5</span>;<br/> <span class="hljs-keyword">unsigned</span> CreationMinute: <span class="hljs-number">6</span>;<br/> <span class="hljs-keyword">unsigned</span> CreationHour: <span class="hljs-number">5</span>;<br/> <span class="hljs-keyword">unsigned</span> CreationDay: <span class="hljs-number">5</span>;<br/> <span class="hljs-keyword">unsigned</span> CreationMonth: <span class="hljs-number">4</span>;<br/> <span class="hljs-keyword">unsigned</span> CreationYear: <span class="hljs-number">7</span>;<br/> <span class="hljs-keyword">unsigned</span> LastAccessDay: <span class="hljs-number">5</span>;<br/> <span class="hljs-keyword">unsigned</span> LastAccessMonth: <span class="hljs-number">4</span>;<br/> <span class="hljs-keyword">unsigned</span> LastAccessYear: <span class="hljs-number">7</span>;<br/> <span class="hljs-keyword">unsigned</span> <span class="hljs-keyword">char</span> Ignore[<span class="hljs-number">2</span>];<br/> <span class="hljs-keyword">unsigned</span> LastWriteSecond: <span class="hljs-number">5</span>;<br/> <span class="hljs-keyword">unsigned</span> LastWriteMinute: <span class="hljs-number">6</span>;<br/> <span class="hljs-keyword">unsigned</span> LastWriteHour: <span class="hljs-number">5</span>;<br/> <span class="hljs-keyword">unsigned</span> LastWriteDay: <span class="hljs-number">5</span>;<br/> <span class="hljs-keyword">unsigned</span> LastWriteMonth: <span class="hljs-number">4</span>;<br/> <span class="hljs-keyword">unsigned</span> LastWriteYear: <span class="hljs-number">7</span>;<br/> <span class="hljs-keyword">unsigned</span> <span class="hljs-keyword">short</span> FirstCluster;<br/> <span class="hljs-keyword">unsigned</span> <span class="hljs-keyword">int</span> FileSize;<br/>} __attribute__ ((packed));<br/><br/><span class="hljs-keyword">typedef</span> <span class="hljs-keyword">struct</span> RootDirectoryEntry <br/> RootDirectoryEntry;
Um das Root Directory ausgeben zu können, wird es beim Initialisieren des FAT12-Treibers von der Festplatte mithilfe der Funktion LoadRootDirectory() geladen, siehe Listing 2. Gespeichert wird der Inhalt des Root Directorys an der in der Konstanten ROOT_DIRECTORY_BUFFER definierten Hauptspeicheradresse. Zugleich wird auch die komplette FAT Table in den Hauptspeicher geladen, die Zieladresse dafür ist in der Konstanten FAT_BUFFER hinterlegt.
Listing 2: Das Root Directory laden
<span class="hljs-function"><span class="hljs-keyword">static</span> <span class="hljs-keyword">void</span> <span class="hljs-title">LoadRootDirectory</span><span class="hljs-params">()</span></span><br/>{<br/> <span class="hljs-comment">// Calculate the Root Directory Size:</span><br/><span class="hljs-comment"> // 14 sectors: =&gt; 32 * 224 / 512</span><br/><span class="hljs-comment"> short rootDirectorySectors =</span><br/><span class="hljs-comment"> 32 * ROOT_DIRECTORY_ENTRIES / </span><br/><span class="hljs-comment"> BYTES_PER_SECTOR;</span><br/><span class="hljs-comment"> // Calculate the LBA address of the Root </span><br/><span class="hljs-comment"> // Directory: 19: =&gt; 2 * 9 + 1</span><br/><span class="hljs-comment"> short lbaAddressRootDirectory =</span><br/><span class="hljs-comment"> FAT_COUNT * SECTORS_PER_FAT + </span><br/><span class="hljs-comment"> RESERVED_SECTORS;</span><br/><span class="hljs-comment"> // Load the whole Root Directory (14 sectors)</span><br/><span class="hljs-comment"> // into memory</span><br/><span class="hljs-comment"> ROOT_DIRECTORY_BUFFER = </span><br/><span class="hljs-comment"> malloc(rootDirectorySectors * </span><br/><span class="hljs-comment"> BYTES_PER_SECTOR);</span><br/><span class="hljs-comment"> ReadSectors(</span><br/><span class="hljs-comment"> (unsigned char *)</span><br/><span class="hljs-comment"> ROOT_DIRECTORY_BUFFER, </span><br/><span class="hljs-comment"> lbaAddressRootDirectory, </span><br/><span class="hljs-comment"> rootDirectorySectors);</span><br/><span class="hljs-comment"> // Load the whole FAT (18 sectors)</span><br/><span class="hljs-comment"> // into memory</span><br/><span class="hljs-comment"> FAT_BUFFER = malloc(FAT_COUNT * </span><br/><span class="hljs-comment"> SECTORS_PER_FAT * BYTES_PER_SECTOR);</span><br/><span class="hljs-comment"> ReadSectors((unsigned char *)FAT_BUFFER, </span><br/><span class="hljs-comment"> FAT1_CLUSTER, FAT_COUNT * </span><br/><span class="hljs-comment"> SECTORS_PER_FAT);</span><br/><span class="hljs-comment">}</span>
Ist das Root Directory geladen, kann man über die 224 Einträge iterieren und sie auf dem Bildschirm ausgeben. Das erledigt die Funktion PrintRootDirectory().Wie Sie in Listing 3 erkennen können, wird ein Root-Directory-Eintrag nur dann ausgegeben, wenn er einen Dateinamen aufweist. Fehlt der Name, ignoriert die Funktion Print-RootDirectory() den Eintrag und setzt die Arbeit mit dem nächsten Eintrag fort.
Listing 3: Das Root Directory anzeigen
void PrintRootDirectory()<br/>{<br/> char str[<span class="hljs-number">32</span>] = <span class="hljs-string">""</span>;<br/> <span class="hljs-keyword">int</span> fileCount = <span class="hljs-number">0</span>;<br/> <span class="hljs-keyword">int</span> fileSize = <span class="hljs-number">0</span>;<br/> <span class="hljs-keyword">int</span> i;<br/> RootDirectoryEntry *entry = (RootDirectoryEntry *)<br/> ROOT_DIRECTORY_BUFFER;<br/> <span class="hljs-keyword">for</span> (i = <span class="hljs-number">0</span>; i &lt; ROOT_DIRECTORY_ENTRIES; i++)<br/> {<br/> <span class="hljs-keyword">if</span> (entry-&gt;FileName[<span class="hljs-number">0</span>] != <span class="hljs-number">0x00</span>)<br/> {<br/> <span class="hljs-regexp">//</span> Print out the file size<br/> itoa(entry-&gt;FileSize, <span class="hljs-number">10</span>, str);<br/> <span class="hljs-keyword">printf</span>(str);<br/> <span class="hljs-keyword">printf</span>(<span class="hljs-string">" bytes"</span>);<br/> <span class="hljs-keyword">printf</span>(<span class="hljs-string">"\t"</span>);<br/> <span class="hljs-regexp">//</span> Extract the name <span class="hljs-keyword">and</span> the extension<br/> char name[<span class="hljs-number">9</span>] = <span class="hljs-string">""</span>;<br/> char extension[<span class="hljs-number">4</span>] = <span class="hljs-string">""</span>;<br/> substring(entry-&gt;FileName, <span class="hljs-number">0</span>, <span class="hljs-number">8</span>, name);<br/> substring(entry-&gt;FileName, <span class="hljs-number">8</span>, <span class="hljs-number">3</span>, <br/> extension);<br/> <span class="hljs-regexp">//</span> Convert everything to lower case<br/> tolower(name);<br/> tolower(extension);<br/> <span class="hljs-regexp">//</span> Print out the file name<br/> <span class="hljs-keyword">int</span> <span class="hljs-keyword">pos</span> = find(name, <span class="hljs-string">' '</span>);<br/> char trimmedName[<span class="hljs-number">9</span>] = <span class="hljs-string">""</span>;<br/> substring(name, <span class="hljs-number">0</span>, <span class="hljs-keyword">pos</span>, trimmedName);<br/> <span class="hljs-keyword">printf</span>(trimmedName);<br/> <span class="hljs-keyword">printf</span>(<span class="hljs-string">"."</span>);<br/> <span class="hljs-keyword">printf</span>(extension);<br/> <span class="hljs-keyword">printf</span>(<span class="hljs-string">"\n"</span>);<br/> <span class="hljs-regexp">//</span> Calculate the file count <span class="hljs-keyword">and</span> the file size<br/> fileCount++;<br/> fileSize += entry-&gt;FileSize;<br/> }<br/> // Move to the <span class="hljs-keyword">next</span> Root Directory Entry<br/> entry = entry + <span class="hljs-number">1</span>;<br/> }<br/> // Print out the file count <span class="hljs-keyword">and</span> the file size<br/> <span class="hljs-keyword">printf</span>(<span class="hljs-string">"\t\t"</span>);<br/> itoa(fileCount, <span class="hljs-number">10</span>, str);<br/> <span class="hljs-keyword">printf</span>(str);<br/> <span class="hljs-keyword">printf</span>(<span class="hljs-string">" File(s)"</span>);<br/> <span class="hljs-keyword">printf</span>(<span class="hljs-string">"\t"</span>);<br/> itoa(fileSize, <span class="hljs-number">10</span>, str);<br/> <span class="hljs-keyword">printf</span>(str);<br/> <span class="hljs-keyword">printf</span>(<span class="hljs-string">" bytes"</span>);<br/> <span class="hljs-keyword">printf</span>(<span class="hljs-string">"\n"</span>);<br/>} Neue Dateien erzeugen
Nachdem man sich den Inhalt des Dateisystems anzeigen lassen kann, geht es nun darum, eine neue Datei mithilfe der Funktion CreateFile() zu erzeugen. Listing 4 zeigt die Implementierung dieser Funktion.Listing 4: CreateFile()
<span class="hljs-function"><span class="hljs-title">static</span> void CreateFile(</span><br/><span class="hljs-function"> unsigned char *FileName,</span><br/><span class="hljs-function"> unsigned char *Extension)</span><br/><span class="hljs-function">{</span><br/><span class="hljs-function"> // Find the next free RootDirectoryEntry</span><br/><span class="hljs-function"> RootDirectoryEntry *freeEntry = </span><br/><span class="hljs-function"> FindNextFreeRootDirectoryEntry();</span><br/><span class="hljs-function"> <span class="hljs-keyword">if</span> (freeEntry != 0x0)</span><br/><span class="hljs-function"> {</span><br/><span class="hljs-function"> // Getting a reference to the</span><br/><span class="hljs-function"> // BIOS Information Block</span><br/><span class="hljs-function"> BiosInformationBlock *bib = </span><br/><span class="hljs-function"> (BiosInformationBlock *)BIB_OFFSET;</span><br/><span class="hljs-function"> // Allocate the first cluster <span class="hljs-keyword">for</span> the new file</span><br/><span class="hljs-function"> unsigned short startCluster = </span><br/><span class="hljs-function"> FindNextFreeFATEntry();</span><br/><span class="hljs-function"> FATWrite(startCluster, 0xFFF);</span><br/><span class="hljs-function"> strcpy(freeEntry-&gt;</span>F<span class="hljs-function"><span class="hljs-title">ileName</span>, FileName);</span><br/><span class="hljs-function"> strcpy(freeEntry-&gt;</span>E<span class="hljs-function"><span class="hljs-title">xtension</span>, Extension);</span><br/><span class="hljs-function"> freeEntry-&gt;</span>F<span class="hljs-function"><span class="hljs-title">irstCluster</span> = startCluster;</span><br/><span class="hljs-function"> freeEntry-&gt;</span>F<span class="hljs-function"><span class="hljs-title">ileSize</span> = 0;</span><br/><span class="hljs-function"> // Set the Date/Time information of the</span><br/><span class="hljs-function"> // new file</span><br/><span class="hljs-function"> freeEntry-&gt;</span>L<span class="hljs-function"><span class="hljs-title">astWriteYear</span> =</span><br/><span class="hljs-function"> freeEntry-&gt;</span>L<span class="hljs-function"><span class="hljs-title">astAccessYear</span> =</span><br/><span class="hljs-function"> freeEntry-&gt;</span>C<span class="hljs-function"><span class="hljs-title">reationYear</span> =</span><br/><span class="hljs-function"> bib-&gt;</span>Y<span class="hljs-function"><span class="hljs-title">ear</span> - FAT12_YEAROFFSET;</span><br/><span class="hljs-function"> freeEntry-&gt;</span>L<span class="hljs-function"><span class="hljs-title">astWriteMonth</span> =</span><br/><span class="hljs-function"> freeEntry-&gt;</span>L<span class="hljs-function"><span class="hljs-title">astAccessMonth</span> =</span><br/><span class="hljs-function"> freeEntry-&gt;</span>C<span class="hljs-function"><span class="hljs-title">reationMonth</span> =</span><br/><span class="hljs-function"> bib-&gt;</span>M<span class="hljs-function"><span class="hljs-title">onth</span>;</span><br/><span class="hljs-function"> freeEntry-&gt;</span>L<span class="hljs-function"><span class="hljs-title">astWriteDay</span> = </span><br/><span class="hljs-function"> freeEntry-&gt;</span>L<span class="hljs-function"><span class="hljs-title">astAccessDay</span> =</span><br/><span class="hljs-function"> freeEntry-&gt;</span>C<span class="hljs-function"><span class="hljs-title">reationDay</span> = bib-&gt;</span>D<span class="hljs-function"><span class="hljs-title">ay</span>;</span><br/><span class="hljs-function"> freeEntry-&gt;</span>L<span class="hljs-function"><span class="hljs-title">astWriteHour</span> =</span><br/><span class="hljs-function"> freeEntry-&gt;</span>C<span class="hljs-function"><span class="hljs-title">reationHour</span> = bib-&gt;</span>H<span class="hljs-function"><span class="hljs-title">our</span>;</span><br/><span class="hljs-function"> freeEntry-&gt;</span>L<span class="hljs-function"><span class="hljs-title">astWriteMinute</span> =</span><br/><span class="hljs-function"> freeEntry-&gt;</span>C<span class="hljs-function"><span class="hljs-title">reationMinute</span> = bib-&gt;</span>M<span class="hljs-function"><span class="hljs-title">inute</span>;</span><br/><span class="hljs-function"> freeEntry-&gt;</span>L<span class="hljs-function"><span class="hljs-title">astWriteSecond</span> =</span><br/><span class="hljs-function"> freeEntry-&gt;</span>C<span class="hljs-function"><span class="hljs-title">reationSecond</span> =</span><br/><span class="hljs-function"> bib-&gt;</span>Second / <span class="hljs-number">2</span>;<br/> <span class="hljs-comment">// Write the changed Root Directory and the </span><br/><span class="hljs-comment"> // FAT tables back to disk</span><br/><span class="hljs-comment"> WriteRootDirectoryAndFAT();</span><br/><span class="hljs-comment"> // Allocate a new cluster of 512 bytes in</span><br/><span class="hljs-comment"> // memory, and copy the initial content</span><br/><span class="hljs-comment"> // into it.</span><br/><span class="hljs-comment"> // Therefore, we can make sure that the </span><br/><span class="hljs-comment"> // remaining bytes are all zeroed out.</span><br/><span class="hljs-comment"> unsigned char *content = </span><br/><span class="hljs-comment"> (unsigned char *)</span><br/><span class="hljs-comment"> malloc(BYTES_PER_SECTOR);</span><br/><span class="hljs-comment"> memset(content, 0x00,</span><br/><span class="hljs-comment"> BYTES_PER_SECTOR);</span><br/><span class="hljs-comment"> // Write the intial file content to disk</span><br/><span class="hljs-comment"> WriteSectors((unsigned int *)content, </span><br/><span class="hljs-comment"> startCluster + DATA_AREA_BEGINNING, 1);</span><br/><span class="hljs-comment"> // Release the block of memory</span><br/><span class="hljs-comment"> free(content);</span><br/><span class="hljs-comment"> }</span><br/><span class="hljs-comment">}</span>
Um eine neue Datei im FAT12-Dateisystem anzulegen, gilt es zunächst einen Eintrag im Root Directory zu finden, der noch nicht verwendet wird. Dies erledigt die Funktion FindNextFreeRootDirectoryEntry(). Ist ein freier Eintrag ermittelt, muss die Funktion FindNextFreeFATEntry() noch einen freien Start-Cluster in der FAT Table finden. Listing 5 zeigt die Implementierung beider Funktionen.
Listing 5: Hilfsfunktionen für das Erstellen einer neuen Datei
static RootDirectoryEntry <br/> *FindNextFreeRootDirectoryEntry()<br/>{<br/> RootDirectoryEntry *<span class="hljs-built_in">entry</span> = <br/> (RootDirectoryEntry *)<br/> ROOT_DIRECTORY_BUFFER;<br/> for (<span class="hljs-built_in">int</span> i = <span class="hljs-number">0</span>; i &lt; ROOT_DIRECTORY_ENTRIES; <br/> i++)<br/> {<br/> <span class="hljs-keyword">if</span> (<span class="hljs-built_in">entry</span>-&gt;FileName[<span class="hljs-number">0</span>] == 0x00)<br/> <span class="hljs-keyword"> retur</span>n<span class="hljs-built_in"> entr</span>y;<br/> // Move to the next Root Directory<span class="hljs-built_in"> Entr</span>y<br/> <span class="hljs-built_in"> entr</span>y =<span class="hljs-built_in"> entr</span>y +<span class="hljs-number"> </span>1;<br/> }<br/> // A<span class="hljs-keyword"> fre</span>e Root Directory<span class="hljs-built_in"> Entr</span>y was not found<br/> <span class="hljs-keyword"> retur</span>n 0x0;<br/>}<br/>static unsigned short FindNextFreeFATEntry()<br/>{<br/> unsigned short Cluster <span class="hljs-number">=</span> 1;<br/> unsigned short result <span class="hljs-number">=</span> 1;<br/> <span class="hljs-keyword"> whi</span>le (result <span class="hljs-number">&gt;</span> 0)<br/> {<br/> Cluster++;<br/> // Calculate the offset into the FAT table<br/> unsigne<span class="hljs-built_in">d i</span>nt fatOffset =<br/> (Cluster <span class="hljs-number">/</span> 2) + Cluster;<br/> unsigned long *offset =<br/> FAT_BUFFER + fatOffset;<br/> // Read th<span class="hljs-built_in">e ent</span>ry from the FAT<br/> unsigned short val = *offset;<br/> <span class="hljs-keyword"> </span>if (Cluster &amp; 0x0001)<br/> {<br/> // Odd Cluster<br/> result = val <span class="hljs-number">&gt;</span>&gt; 4; // Highe<span class="hljs-number">st</span> 12 Bits<br/> }<br/> <span class="hljs-keyword"> e</span>lse<br/> {<br/> // Even Cluster<br/> result = val &amp; 0x0FFF; // Low<span class="hljs-number">es</span>t 12 Bits<br/> }<br/> <span class="hljs-keyword">}</span><br/><span class="hljs-keyword"> re</span>turn Cluster;<br/>}
Anschließend werden die Datums- und Uhrzeitinformationen der neuen Datei gesetzt und das Root Directory sowie die FAT Tables wieder zurück auf die Festplatte geschrieben. Zum Abschluss wird auch noch der mit Null-Werten initialisierte erste Cluster der neuen Datei auf die Festplatte geschrieben.
Dateien öffnen und schließen
Bei der Funktion CreateFile(), die Sie oben bereits kennengelernt haben, handelt es sich um eine statische C-Funktion, das heißt, dass sie sich außerhalb des kompilierten Moduls nicht aufrufen lässt, da ihr Gültigkeitsbereich beschränkt ist.Das Erstellen einer neuen Datei erfolgt mit der Funktion OpenFile(), nachdem die Datei im Write- oder Append-Modus geöffnet wurde. Im Dateisystem ist sie zu diesem Zeitpunkt noch nicht vorhanden. Der FAT12-Treiber implementiert aktuell die folgenden Datei-Modi:- r (read): Die Datei wird für einen Lesevorgang geöffnet.
- w (write): Die Datei wird für einen Schreibvorgang geöffnet. Ist die Datei noch nicht vorhanden, wird sie erzeugt, ansonsten wird sie überschrieben.
- a (append): Die Datei zum Anhängen von Daten öffnen.
<span class="hljs-keyword">struct</span> FileDescriptor
{
<span class="hljs-keyword">unsigned</span> <span class="hljs-keyword">char</span> FileName[<span class="hljs-number">11</span>];
<span class="hljs-keyword">unsigned</span> <span class="hljs-keyword">char</span> Extension[<span class="hljs-number">3</span>];
<span class="hljs-keyword">unsigned</span> <span class="hljs-keyword">long</span> FileSize;
<span class="hljs-keyword">unsigned</span> <span class="hljs-keyword">long</span>
CurrentFileOffset;
<span class="hljs-keyword">char</span> FileMode[<span class="hljs-number">2</span>];
};
<span class="hljs-keyword">typedef</span> <span class="hljs-keyword">struct</span> FileDescriptor
FileDescriptor;
In der Variablen CurrentFileOffset wird hier das aktuelle File Offset innerhalb der geöffneten Datei gespeichert. Dieser Wert ist sehr wichtig, wenn eine Datei später gelesen oder geschrieben werden soll. Die Funktion SeekFile() dient dazu den aktuellen File Offset zu ändern.Um nun eine geöffnete Datei in eine Kernel-Liste eintragen zu können, ist noch ein eindeutiger Schlüssel erforderlich. Dieser wird mit der Funktion HashFileName() erzeugt, die auf Basis des Dateinamens (und der angehängten Prozess-ID) einen eindeutigen Hashwert erzeugt. Die Hashfunktion basiert auf einem Algorithmus, der unter [2] näher beschrieben ist. Die Implementierung sieht wie folgt aus:
<span class="hljs-function"><span class="hljs-keyword">static</span> <span class="hljs-keyword">unsigned</span> <span class="hljs-keyword">long</span> <span class="hljs-title">HashFileName</span><span class="hljs-params">(</span></span>
<span class="hljs-function"><span class="hljs-params"> <span class="hljs-keyword">unsigned</span> <span class="hljs-keyword">char</span> *FileName)</span></span>
{
<span class="hljs-keyword">int</span> hash = <span class="hljs-number">0</span>;
<span class="hljs-keyword">int</span> length = <span class="hljs-built_in">strlen</span>(FileName);
<span class="hljs-comment">// To store 'P'.</span>
<span class="hljs-comment"> int p = 1;</span>
<span class="hljs-comment"> // For taking modulo.</span>
<span class="hljs-comment"> int m = 1000000007;</span>
<span class="hljs-comment"> for (int i = 0; i < length; i++)</span>
<span class="hljs-comment"> {</span>
<span class="hljs-comment"> hash += (FileName[i] - 'a') * p;</span>
<span class="hljs-comment"> hash = hash % m;</span>
<span class="hljs-comment"> p *= 41;</span>
<span class="hljs-comment"> }</span>
<span class="hljs-comment"> return hash;</span>
<span class="hljs-comment">}</span>
In Listing 6 sehen Sie die Funktion OpenFile(), die auch die Logik hinsichtlich der unterschiedlichen Datei-Modi implementiert. OpenFile() liefert den erzeugten Hash-Wert des hinzugefügten File Descriptors zurück. Dieser Hash-Wert ist das sogenannte File Handle, das die anderen I/O-Funktionen als Input-Parameter benötigen.
Listing 6: Die Funktion OpenFile()
unsigned long OpenFile(unsigned char *FileName, <br/> unsigned char *Extension, char *FileMode)<br/>{<br/> char pid[<span class="hljs-number">10</span>] = <span class="hljs-string">""</span>;<br/> <span class="hljs-regexp">//</span> Construct the full file name<br/> char fullFileName[<span class="hljs-number">15</span>];<br/> strcpy(fullFileName, FileName);<br/> strcat(fullFileName, Extension);<br/> <span class="hljs-regexp">//</span> Find the Root Directory Entry <span class="hljs-keyword">for</span> the<br/> <span class="hljs-regexp">//</span> given program name<br/> RootDirectoryEntry *entry = <br/> FindRootDirectoryEntry(fullFileName);<br/> <span class="hljs-regexp">//</span> Check, <span class="hljs-keyword">if</span> the requested file was found <span class="hljs-keyword">in</span> the <br/> <span class="hljs-regexp">//</span> FAT12 file system partition<br/> <span class="hljs-keyword">if</span> ((entry == <span class="hljs-number">0</span>x0) &amp;&amp;<br/> (strcmp(FileMode, <span class="hljs-string">"w"</span>) == <span class="hljs-number">0</span>))<br/> {<br/> <span class="hljs-regexp">//</span> If the requested file was not found <span class="hljs-keyword">in</span> the <br/> <span class="hljs-regexp">//</span> <span class="hljs-string">"write"</span> mode, we just create a new empty <br/> <span class="hljs-regexp">//</span> file<br/> CreateFile(FileName, Extension);<br/> }<br/> <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> ((entry == <span class="hljs-number">0</span>x0) &amp;&amp;<br/> (strcmp(FileMode, <span class="hljs-string">"r"</span>) == <span class="hljs-number">0</span>))<br/> {<br/> <span class="hljs-regexp">//</span> If the requested file was not found <span class="hljs-keyword">in</span> the <br/> <span class="hljs-regexp">//</span> <span class="hljs-string">"write"</span> mode, we return a NULL value <span class="hljs-keyword">for</span> <br/> <span class="hljs-regexp">//</span> the file handle<br/> return <span class="hljs-number">0</span>;<br/> }<br/> <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> ((entry == <span class="hljs-number">0</span>x0) &amp;&amp;<br/> (strcmp(FileMode, <span class="hljs-string">"a"</span>) == <span class="hljs-number">0</span>))<br/> {<br/> <span class="hljs-regexp">//</span> If the requested file was not found <span class="hljs-keyword">in</span> the <br/> <span class="hljs-regexp">//</span> <span class="hljs-string">"append"</span> mode, we just create a new <br/> <span class="hljs-regexp">//</span> empty file<br/> CreateFile(FileName, Extension);<br/> }<br/> <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> ((entry != <span class="hljs-number">0</span>x0) &amp;&amp;<br/> (strcmp(FileMode, <span class="hljs-string">"w"</span>) == <span class="hljs-number">0</span>))<br/> {<br/> <span class="hljs-regexp">//</span> If the requested file exists <span class="hljs-keyword">in</span> the <span class="hljs-string">"write"</span> <br/> <span class="hljs-regexp">//</span> mode, its content must be truncated.<br/> <span class="hljs-regexp">//</span> Therefore, we <span class="hljs-keyword">delete</span> and recreate the file<br/> DeleteFile(FileName, Extension);<br/> CreateFile(FileName, Extension);<br/> }<br/> <span class="hljs-regexp">//</span> The PID of the current running task is <br/> <span class="hljs-regexp">//</span> concatenated to the file name<br/> <span class="hljs-regexp">//</span> to make it unique across multiple running <br/> <span class="hljs-regexp">//</span> tasks.<br/> <span class="hljs-regexp">//</span> Otherwise we would have a hash collision <span class="hljs-keyword">if</span> <br/> <span class="hljs-regexp">//</span> the same file is opened across<br/> <span class="hljs-regexp">//</span> multiple running tasks.<br/> tolower(fullFileName);<br/> ltoa(GetTaskState()-&gt;PID, <span class="hljs-number">10</span>, pid);<br/> strcat(fullFileName, pid);<br/> <span class="hljs-regexp">//</span> Calculate a hash value <span class="hljs-keyword">for</span> the given<br/> <span class="hljs-regexp">//</span> file name<br/> unsigned long hashValue = <br/> HashFileName(fullFileName);<br/> <span class="hljs-regexp">//</span> Create a new FileDescriptor and store it <span class="hljs-keyword">in</span> <br/> <span class="hljs-regexp">//</span> a system-wide Kernel list<br/> FileDescriptor *descriptor = (FileDescriptor *)<br/> malloc(sizeof(FileDescriptor));<br/> strcpy(descriptor-&gt;FileName, FileName);<br/> strcpy(descriptor-&gt;Extension, Extension);<br/> descriptor-&gt;FileSize = entry-&gt;FileSize;<br/> descriptor-&gt;CurrentFileOffset = <span class="hljs-number">0</span>;<br/> strcpy((char *)&amp;descriptor-&gt;FileMode, <br/> FileMode);<br/> AddEntryToList(FileDescriptorList,<br/> descriptor, hashValue);<br/> <span class="hljs-regexp">//</span> If the requested file exists <span class="hljs-keyword">in</span> the <span class="hljs-string">"append"</span> <br/> <span class="hljs-regexp">//</span> mode, we set the FileOffset to the end of <br/> <span class="hljs-regexp">//</span> the file<br/> <span class="hljs-keyword">if</span> (strcmp(FileMode, <span class="hljs-string">"a"</span>) == <span class="hljs-number">0</span>)<br/> descriptor-&gt;CurrentFileOffset =<br/> descriptor-&gt;FileSize;<br/> <span class="hljs-regexp">//</span> Return the key of the newly added <br/> <span class="hljs-regexp">//</span> FileDescriptor<br/> return hashValue;<br/>}
Eine dieser Funktionen ist CloseFile(), die eine geöffnete Datei wieder schließt. Dazu wird einfach der entsprechende File Descriptor aus der Kernel-Liste entfernt:
<span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">CloseFile</span><span class="hljs-params">(<span class="hljs-keyword">unsigned</span> <span class="hljs-keyword">long</span> FileHandle)</span></span>
{
<span class="hljs-comment">// Find the file which needs to be closed</span>
<span class="hljs-comment"> ListEntry *entry = </span>
<span class="hljs-comment"> GetEntryFromList(</span>
<span class="hljs-comment"> FileDescriptorList, FileHandle);</span>
<span class="hljs-comment"> if (entry != 0x0)</span>
<span class="hljs-comment"> {</span>
<span class="hljs-comment"> // Close the file by removing it from the list</span>
<span class="hljs-comment"> RemoveEntryFromList(</span>
<span class="hljs-comment"> FileDescriptorList, entry);</span>
<span class="hljs-comment"> return 0;</span>
<span class="hljs-comment"> }</span>
<span class="hljs-comment"> else</span>
<span class="hljs-comment"> return -1;</span>
<span class="hljs-comment">}</span> Dateien schreiben
Legt man eine neue Datei mit OpenFile() an, so hat diese zunächst einmal noch keinen Inhalt. Dieser wird erst durch die Funktion WriteFile() auf die Festplatte geschrieben. Wie Sie bereits aus der ersten Folge dieser Serie [3] wissen, besteht eine Datei im FAT12-Dateisystem aus einer einfach verketteten Liste von Clustern zu 512 Bytes, die in der FAT Table abgelegt sind. Der Eintrag der Datei im Root Directory zeigt auf den ersten Cluster der Datei (Bild 2).
Aufbau des FAT12-Dateisystems (Bild 2)
Autor
Die Funktion WriteFile() erwartet im ersten Parameter das File Handle der bereits geöffneten Datei, im zweiten Parameter werden die Nutzdaten übergeben und im dritten Parameter die Länge der Nutzdaten.Im ersten Schritt muss nun basierend auf dem aktuellen File Offset der Cluster, in den die Nutzdaten geschrieben werden sollen, von der Festplatte in den Hauptspeicher geladen werden. Wie Sie in Listing 7 erkennen können, muss die Funktion WriteFile() auch dafür sorgen, dass die Datei im FAT12-Dateisystem passend vergrößert wird, wenn sich das aktuelle File Offset außerhalb der aktuellen Dateigröße befindet. Das Vergrößern der Datei erfolgt dynamisch über die Funktion AllocateNewClusterToFile().
Listing 7: Laden des richtigen Clusters
// Allocate a file buffer<br/>unsigned char *file_buffer =<br/> (unsigned char *)malloc(BYTES_PER_SECTOR);<br/>// Calculate from the current file position the <br/>// cluster and the offset within that cluster<br/>unsigned long cluster = <br/> descriptor-&gt;CurrentFileOffset / <br/> BYTES_PER_SECTOR;<br/>unsigned long offsetWithinCluster = <br/> descriptor-&gt;CurrentFileOffset – <br/> (cluster * BYTES_PER_SECTOR);<br/>unsigned short currentFatSector = <br/> entry-&gt;FirstCluster;<br/>// Loop until we reach the cluster that we want <br/>// to write to. If necessary, new clusters will be <br/>// created and added for the file.<br/>for (int i = 0; i &lt; cluster; i++)<br/>{<br/> // Read the next Cluster from the FAT table<br/> unsigned short nextFatSector = <br/> FATRead(currentFatSector);<br/> // The next cluster is the last one in the chain<br/> if (nextFatSector &gt;= EOF)<br/> {<br/> // Allocate a new cluster for the file<br/> unsigned short newFatSector = <br/> AllocateNewClusterToFile(<br/> currentFatSector);<br/> // Set the current sector<br/> currentFatSector = newFatSector;<br/> }<br/> else<br/> {<br/> // Set the current sector<br/> currentFatSector = nextFatSector;<br/> }<br/>}<br/>// When the data is stored across the last <br/>// boundary of the current sector, we have <br/>// allocate an additional cluster to the file<br/>if ((offsetWithinCluster + Length &gt;= <br/> BYTES_PER_SECTOR) &amp;&amp; (descriptor-&gt;FileSize <br/> &lt; descriptor-&gt;CurrentFileOffset + Length))<br/>{<br/> // Allocate a new cluster for the file<br/> AllocateNewClusterToFile(currentFatSector);<br/>}<br/>// Calculate the following disk sector<br/>unsigned short fatSectorFollowing = <br/> FATRead(currentFatSector);<br/>// Read the specific sector from disk<br/>ReadSectors((unsigned char *)file_buffer, <br/> currentFatSector + DATA_AREA_BEGINNING, 1);<br/>// Read the following logical sector, when the data is stored across 2 disk sectors<br/>if (offsetWithinCluster + Length &gt;= <br/> BYTES_PER_SECTOR)<br/>{<br/> ReadSectors((unsigned char *)(file_buffer + <br/> BYTES_PER_SECTOR), <br/> fatSectorFollowing + <br/> DATA_AREA_BEGINNING, 1);<br/>}
Wie Sie in Listing 8 erkennen können, wird dafür der nächste freie FAT-Cluster über die Funktion FindNextFreeFATEntry() ermittelt. Über FATWrite() wird dieser neue FAT-Cluster dann in den aktuell letzten FAT-Cluster eingetragen und die Datei somit erweitert. In den letzten FAT-Cluster wird schlussendlich noch der Wert 0xFFF eingetragen, der das Ende der Datei (EOF) signalisiert.
Listing 8: Vergrößern einer Datei
static unsigned short AllocateNewClusterToFile(<br/> unsigned short CurrentFATSector)<br/>{<br/> // Allocate a new cluster for the file<br/> unsigned short newFatSector = <br/> FindNextFreeFATEntry();<br/> FATWrite(CurrentFATSector, newFatSector);<br/> FATWrite(newFatSector, 0xFFF);<br/> // Zero-initialize the new cluster and write it <br/> // to disk<br/> unsigned char *emptyContent = <br/> (unsigned char *)<br/> malloc(BYTES_PER_SECTOR);<br/> memset(emptyContent, 0x00, <br/> BYTES_PER_SECTOR);<br/> WriteSectors((unsigned int *)emptyContent, <br/> newFatSector + DATA_AREA_BEGINNING, 1);<br/> // Release the block of memory<br/> free(emptyContent);<br/> // Return the new allocated FAT sector<br/> return newFatSector;
In Listing 9 sehen Sie die Implementierung der Funktion FATWrite(), die auf den ersten Blick ein wenig kompliziert erscheint, da sich ein 12-Bit langer FAT-Eintrag über zwei Bytes erstreckt und somit ein wenig Bit-Arithmetik betrieben werden muss.
Listing 9: Einen FAT-Eintrag schreiben
static void FATWrite(<br/> unsigned short Cluster,<br/> unsigned short Value)<br/>{<br/> // Calculate the offset into the FAT table<br/> unsigned int fatOffset = (Cluster / 2) + Cluster;<br/> if (Cluster % 2 == 0)<br/> {<br/> // Even Cluster<br/> FAT_BUFFER[fatOffset + 0] = (0xFF &amp; Value);<br/> FAT_BUFFER[fatOffset + 1] =<br/> ((0xF0 &amp; (FAT_BUFFER[fatOffset + 1])) | <br/> (0x0F &amp; (Value &gt;&gt; 8)));<br/> }<br/> else<br/> {<br/> // Odd Cluster<br/> FAT_BUFFER[fatOffset + 0] =<br/> ((0x0F &amp; (FAT_BUFFER[fatOffset + 0])) | <br/> ((0x0F &amp; Value) &lt;&lt; 4));<br/> FAT_BUFFER[fatOffset + 1] =<br/> ((0xFF) &amp; (Value &gt;&gt; 4));<br/> }<br/>}
Nachdem WriteFile() den gesuchten Cluster von der Festplatte in den Hauptspeicher geladen hat, kopiert die Funktion memcpy() die übergebenen Nutzdaten an die entsprechende Stelle im Hauptspeicher. Schlussendlich schreibt die Funktion WriteSectors() die Nutzdaten wieder auf die Festplatte zurück.Außerdem werden noch das aktuelle Zugriffsdatum der Datei und die Dateigröße im Root Directory passend geändert. Listing 10 zeigt den für diesen Zweck innerhalb der Funktion WriteFile() zusätzlich erforderlichen Code.
Listing 10: Dateiänderungen durchführen
// Copy the requested data into the destination <br/>// disk sector<br/>memcpy(file_buffer + offsetWithinCluster, <br/> Buffer, Length);<br/>// Write the specific sector to disk<br/>WriteSectors((unsigned int *)file_buffer, <br/> currentFatSector + DATA_AREA_BEGINNING, 1);<br/>// Write the following logical sector, when the <br/>// data is stored across 2 disk sectors<br/>if (offsetWithinCluster + Length &gt;= <br/> BYTES_PER_SECTOR)<br/>{<br/> WriteSectors((unsigned int *)<br/> (file_buffer + BYTES_PER_SECTOR), <br/> fatSectorFollowing + <br/> DATA_AREA_BEGINNING, 1);<br/>}<br/>// Release the file buffer<br/>free(file_buffer);<br/>// Set the last Access and Write Date<br/>SetLastAccessDate(entry);<br/>// Set the current file position within<br/>// the FileDescriptor<br/>descriptor-&gt;CurrentFileOffset += Length;<br/>// Check if the file size has changed<br/>if (descriptor-&gt;CurrentFileOffset &gt; <br/> entry-&gt;FileSize)<br/>{<br/> // Change the data in the RootDirectory<br/> entry-&gt;FileSize =<br/> descriptor-&gt;CurrentFileOffset;<br/> descriptor-&gt;FileSize =<br/> descriptor-&gt;CurrentFileOffset;<br/>}<br/>// Write the RootDirectory and the FAT<br/>// tables back to disk<br/>WriteRootDirectoryAndFAT(); Dateien lesen
Was noch fehlt, ist eine Funktion ReadFile(), mit der man Daten aus einer Datei lesen kann. Auch diese Funktion erwartet als Parameter das File Handle der geöffneten Datei, den reservierten Hauptspeicherbereich und die gewünschte Länge der zu lesenden Daten.ReadFile() liest die Daten immer basierend auf dem aktuellen File Offset, das im File Descriptor hinterlegt ist. Wie Sie in Listing 11 erkennen können, wird am Schluss das aktuelle File Offset im File Descriptor entsprechend den gelesenen Bytes erhöht, wodurch der nächste Aufruf von ReadFile() die Daten am aktuellen File Offset innerhalb der Datei zurückliefert. Dadurch lässt sich die Datei durch mehrmalige Aufrufe von ReadFile() komplett auslesen. Dass das Ende der Datei erreicht ist, signalisiert die Funktion EndOfFile(), die 1 zurückliefert, sobald keine Nutzdaten mehr vorhanden sind:Listing 11: Lesen einer Datei
// Allocate a file buffer<br/>unsigned char *file_buffer = <br/> (unsigned char *)malloc(BYTES_PER_SECTOR);<br/>// Calculate from the current file position the <br/>// cluster and the offset within that cluster<br/>unsigned long cluster =<br/> descriptor-&gt;CurrentFileOffset / BYTES_PER_SECTOR;<br/>unsigned long offsetWithinCluster = <br/> descriptor-&gt;CurrentFileOffset - <br/> (cluster * BYTES_PER_SECTOR);<br/>unsigned short fatSector = entry-&gt;FirstCluster;<br/>// Loop until we reach the cluster that<br/>// we want to read<br/>for (int i = 0; i &lt; cluster; i++)<br/>{<br/> // Read the next Cluster from the FAT table<br/> fatSector = FATRead(fatSector);<br/>}<br/>// Calculate the following disk sector<br/>unsigned short fatSectorFollowing = <br/> FATRead(fatSector);<br/>// Check for the EndOfFile condition<br/>if (descriptor-&gt;CurrentFileOffset + Length &gt; <br/> descriptor-&gt;FileSize)<br/>{<br/> Length = descriptor-&gt;<br/> FileSize – descriptor-&gt;CurrentFileOffset;<br/>}<br/>// Read the specific sector from disk<br/>ReadSectors((unsigned char *)file_buffer, <br/> fatSector + DATA_AREA_BEGINNING, 1);<br/>// We also read the following sector, when the <br/>// requested data is stored across 2 disk sectors<br/>if (offsetWithinCluster + Length &gt; BYTES_PER_SECTOR)<br/>{<br/> ReadSectors((unsigned char *)file_buffer + <br/> BYTES_PER_SECTOR, <br/> fatSectorFollowing + <br/> DATA_AREA_BEGINNING, 1);<br/>}<br/>// Copy the requested data into the<br/>// destination buffer<br/>memcpy(Buffer, file_buffer + <br/> offsetWithinCluster, Length);<br/>// Set the current file position within<br/>// the FileDescriptor<br/>descriptor-&gt;CurrentFileOffset += Length;<br/>// Release the file buffer
int EndOfFile(unsigned long FileHandle)
{
// Find the file from which we want to check
// the EndOfFile condition
ListEntry *entry =
GetEntryFromList(FileDescriptorList,
FileHandle);
FileDescriptor *descriptor =
(FileDescriptor *)entry->Payload;
if (descriptor->CurrentFileOffset ==
descriptor->FileSize)
return 1;
else
return 0;
}
Auf Basis der vorgestellten Funktionen können Sie nun bereits sehr mächtige Funktionalitäten in unserem Selbstbau-Betriebssystem implementieren, wie zum Beispiel das Kopieren einer Datei. Den dafür erforderlichen Code finden Sie in Listing 12.
Listing 12: Kopieren einer Datei
unsigned char buffer[512] = "";<br/>// Open both files<br/>unsigned long fileHandleSource = <br/> OpenFile("BIGFILE ", "TXT", "r");<br/>unsigned long fileHandleTarget = <br/> OpenFile("TARGET ", "TXT", "w");<br/>// Check if the source file was opened<br/>if (fileHandleSource == 0)<br/> printf("The source file could not be <br/> opened.\n");<br/>// Check if the target file was opened<br/>if (fileHandleSource == 0)<br/> printf("The target file could not be opened or <br/> created.\n");<br/>if ((fileHandleSource != 0) &amp;&amp;<br/> (fileHandleTarget != 0))<br/>{<br/> // Copy the source file to the target file<br/> while (!EndOfFile(fileHandleSource))<br/> {<br/> ReadFile(fileHandleSource,<br/> (unsigned char *)&amp;buffer, 512);<br/> WriteFile(fileHandleTarget,<br/> (unsigned char *)&amp;buffer, 512);<br/> }<br/> // Close both file handles<br/> CloseFile(fileHandleSource);<br/> CloseFile(fileHandleTarget);<br/> printf("File copied.\n");<br/>}
Die bereits erwähnte Funktion SeekFile() erlaubt es, den aktuellen File Offset der geöffneten Datei zu verändern, um an eine gewünschte Position innerhalb der Datei zu springen:
int SeekFile(unsigned long FileHandle,
unsigned long NewFileOffset)
{
// Find the file from which we want to read
ListEntry *entry =
GetEntryFromList(FileDescriptorList,
FileHandle);
FileDescriptor *descriptor =
(FileDescriptor *)entry->Payload;
if (descriptor != 0x0)
{
descriptor->CurrentFileOffset =
NewFileOffset;
return 0;
}
else
return -1;
}
Mithilfe von SeekFile() sind Sie in der Lage, jeden beliebigen Teil einer Datei auszulesen und weiterzuverarbeiten. Damit verfügen Sie nun über einen vollständigen FAT-Treiber, mit dessen Hilfe Sie in der Lage sind, mit dem FAT12-Dateisystem zu interagieren, um persistente Daten zu verwalten.
Fazit
Im Rahmen dieses Artikels wurde ein FAT12-Treiber entwickelt, der in der Lage ist Dateien im FAT12-Dateisystem zu lesen und zu schreiben. Damit ist die inzwischen auf 15 Teile angewachsene Artikelserie zur Betriebssystem-Entwicklung an ihrem Ende angelangt. Das Selbstbau-Betriebssystem hat inzwischen ein Stadium erreicht, in dem man damit bereits etliche sinnvolle Aufgaben realisieren kann. Wenn auch nicht in dieser Serie, geht der Ausbau des Betriebssystems dennoch weiter. Wer möchte kann den Fortgang im GitHub-Repository des Autors [4] verfolgen.Fussnoten
- Klaus Aschenbrenner, Programme ausführen, Das eigene Betriebssystem, Teil 14, dotnetpro 2/2024, Seite 91 ff., http://www.dotnetpro.de/A2402DIYOS
- Ujjawal Gupta, String Hashing, http://www.dotnetpro.de/SL2403DIYOS1
- Klaus Aschenbrenner, Kaos64: Die ersten Schritte, dotnetpro 1/2023, Seite 76 ff., http://www.dotnetpro.de/A2301DIYOS
- GitHub-Repository des Autors, http://www.github.com/sqlpassion/osdev
