Um das Betriebssystem tOSh herunterzuladen, kannst du dies über den Bereich Resources dieser Website tun.

Teile

Diese Artikelserie wird aus folgenden Teilen bestehen:

fuck wINdOzE gO tOSh!fuck wINdOzE gO tOSh!

Einen Treiber programmieren

Hast du dich schon mal gefragt, was zur Hölle ein Treiber ist?

Es ist eine Scheiße, das ist es. ;-( – Aber es ist eine Scheiße, die wir programmieren müssen, sonst funktioniert hier gar keine Scheiße. 3;-D !

Eine Scheißmenge Jahre vergingen und das Leben hat die Entwicklung von tOSh gestoppt, dem revolutionären Betriebssystem, das das Leben von weiß der Geier wem verändern wird, aber meines ganz sicher verändert hat.

Wir haben den Boden bereitet, um nach –Jahren!– endlich etwas Nützliches mit unserem Betriebssystem machen zu können. Und eine der nützlichen Sachen, die ein Computer tatsächlich macht, ist, Dateien zu speichern.

Bei tOSh haben wir vorerst nicht einmal eine Festplatte. Nicht einmal auf der gleichen Diskette, von der wir booten, können wir eine Datei speichern, weil wir erstens die Diskette überhaupt nicht ansteuern und schon gar kein Dateisystem haben, um irgendetwas zu speichern!

Irgendwann dachte ich, dass es unter x86 einfacher sein würde, das Floppy zu kontrollieren, als einen Treiber für eine Festplatte zusammenzubauen.

Da ich mich für das Floppy entschieden habe, weil ICH MAG DISKETTEN, weiß ich momentan nicht einmal, ob es besser gewesen wäre, HDDs oder das Floppy zu handhaben. Aber einen funktionierenden Floppy-Treiber hinzubekommen war überraschend viel schwieriger, als ich erwartet hatte.

Während ich tOSh entwickle, benutze ich normalerweise qemu und bochs, um zu testen, ob die Sachen funktionieren, einschließlich des Floppy-Laufwerks. Wenn ich aber irgendeine Version des Betriebssystems auf echter Hardware teste, etwa auf meiner [Maschine von 1997], auf einigen anderen Rechnern aus dem Hackerspace, in dem ich Mitglied bin, oder bei Freunden mit wirklich alter Hardware, wird es noch komplizierter.

Begleitet mich auf diesem Abenteuer, einen Treiber für Floppy-Disk-Controller, FDC (Floppy Disk Controller), so generisch wie möglich zu programmieren und ein Dateisystem zu bauen, um nonstop Daten zu schreiben, 70er-Style.

Floppy-Laufwerk-Treiber

Fangen wir mit ein paar #dEfInEz an:

#define FDC_DOR   0x3F2   /* Digital Output Register */
#define FDC_MSR   0x3F4   /* Main Status Register */
#define FDC_FIFO  0x3F5   /* Data FIFO */
#define FDC_CCR   0x3F7   /* Configuration Control Register */
  • FDC_DOR schaltet den Motor ein und aus, wählt das aktive Laufwerk aus und aktiviert IRQ/DMA.
  • FDC_MSR ist nur lesbar und sagt dir, in welchem Zustand sich der Controller befindet.
  • FDC_FIFO ist der 1-Byte-Buffer, über den Befehle reingehen und Ergebnisse rauskommen. Das gesamte FDC-Protokoll läuft über diesen einen Port, ein Byte nach dem anderen.
  • FDC_CCR definiert die "Geschwindigkeit" der Übertragung.

Protokoll

Das Protokoll besteht aus drei Teilen bzw. Phasen.

  • command phase, du schickst Bytes.
  • execution phase, der Controller erledigt extrem wichtige Sachen.
  • result phase, der Controller gibt dir den Status der vorherigen Operation zurück.

Das MSR sagt dir, in welchem Teil du gerade bist, indem du die Bits RQM (Request For Master) und DIO (Data Input/Output) anschaust:

static bool fdc_wait_write_ready(void)
{
    uint32_t start = pit_get_ticks();

    while ((pit_get_ticks() - start) < 100) {

        uint8_t msr = inb(FDC_MSR);

        if ((msr & 0xC0) == 0x80)
            return true;

        inb(0x80); /* I/O Delay for ISA hardware */
    }

    terminal_writestring("FLOPPY: FDC write timeout\n");
    return false;
}

(msr & 0xC0) == 0x80 bedeutet RQM=1, DIO=0. Der Controller wartet auf ein Byte. Um ein Ergebnis zu lesen, ändert sich die Bedingung zu (msr & 0xD0) == 0xD0, wodurch zu RQM=1, DIO=1 noch CB=1 (controller busy) dazukommt: Der FDC hat ein Byte bereit und verarbeitet gerade einen Befehl (daher busy).

Das alles mache ich mit Polling und einem Timeout. Wenn der FDC nicht antwortet, hängt sich der Kernel für immer auf. Jedes fdc_write / floppy_read_byte hat 100 Ticks Spielraum (bei 100Hz eine Sekunde), und wenn es nicht klappt, wird das gemeldet und abgebrochen.

Das inb(0x80) brauchen wir –auf echter Hardware– für ein ISA-I/O-Delay. Der Bus braucht zwischen den Polls eine gewisse Zeit X.

*Hustet*
Reden wir über Emulatoren.

Ist euch schon mal aufgefallen, dass manche Leute –fukken wunderschöne Menschen in dieser beschissenen Welt– davon besessen sind, ganze Architekturen mit clock-genauer Präzision zu emulieren? Nun, qemu und bochs gehören nicht dazu.

Wir reden gerade über x86, aber bei anderen Architekturen oder Konsolen, wie Super Nintendo oder was weiß ich, Playstation, gibt es verschiedene Ansätze für die Emulation. Vielleicht ist es beim SNES, weil es ein ROM ist, nicht ganz so offensichtlich, aber bei CDROM, wo ein Motor im Spiel ist (wie bei einem Floppy), ändern sich die Dinge.

Wenn ich einen Controller für irgendeine Scheiße programmiere, die mit qemu emuliert wird, entgehen mir all die physischen Besonderheiten, die der Motor und die RPMs der CD oder die magnetische Scheibe der Diskette mit sich bringen. In diesem Fall reden wir über ein Floppy-Laufwerk, bei dem ein Motor (!) rotiert und ein paar Millisekunden braucht, um eine stabile Drehgeschwindigkeit zu erreichen.

Als ich diesen Treiber und das Betriebssystem im Allgemeinen programmierte, lief es in qemu, und als ich es auf echter Hardware laufen lassen wollte, lief es verdammt nochmal überhaupt nicht.

Deshalb ist es unglaublich wichtig, die Datasheets von allem zu befolgen, was man gerade programmiert, und wenn man Glück hat, Informationen zusammenzutragen, die andere Leute bereits recherchiert haben. Zum Beispiel Josh Cole von floppy.cafe, der praktisch 90% von allem, was ich für die Entwicklung des Treibers brauchte, an einem einzigen Ort gesammelt hat. Ein verdammter Meister.

Im Zeitalter der Künstlichen Intelligenz ist es vielleicht sogar besser zu wissen, wo man die Dokumentation findet, aus der sie gefüttert wurde, als sie blind nach einer Implementierung zu fragen.

Ich versichere es euch.

Reset und Initialisierung

Die FDC-Startsequenz in floppy_init() folgt der Reihenfolge aus dem Datasheet:

1. IRQ6 am PIC unmasken
2. Datenrate konfigurieren (CCR = 0x00)
3. DOR = enable + irq, Motor aus
4. Reset: DOR = 0x00
5. I/O-Delay (4x Schreibzugriffe auf 0x80)
6. DOR = enable + irq (Ende des Resets)
7. Auf IRQ6 warten (der FDC-Reset erzeugt einen IRQ)
8. 4x SENSE INTERRUPT
9. SPECIFY
10. CONFIGURE
11. Motor an -> RECALIBRATE -> Motor aus
12. Testlesen (Sector 0, Head 0, Sector 1)

Das einzig Relevante hier ist, warum wir nach dem Reset 4 Sense Interrupt machen. Das liegt daran, dass ich den Controller im Modus "Drive Polling" gelassen habe: Wenn der FDC in diesem Modus einen Reset durchführt, erzeugt er einen ausstehenden Status für jedes der 4 Laufwerke, die er haben kann (A, B, C oder D Floppys), selbst wenn nur eines davon angeschlossen ist. Wenn du diese 4 Ergebnisse nicht mit floppy_sense_interrupt() leerst, bleibt im Controller noch irgendein Scheiß in der Queue und du musst die Daten darin erst vollständig abarbeiten.

Ich habe ziemlich lange versucht herauszufinden, warum sich das Laufwerk bei mir ständig aufhängte, und einer der Gründe war genau das.

Specify

static bool floppy_specify(void)
{
    if (!fdc_write(FDC_CMD_SPECIFY))
        return false;

    if (!fdc_write(0x8f))   /* SRT=8, HUT=15 */
        return false;

    if (!fdc_write(0x1e))   /* HLT=15, NDMA=0 */
        return false;

    return true;
}

SPECIFY hat keine Result-Phase und erzeugt keinen IRQ. Sobald die 3 Bytes gesendet wurden, war’s das. Die Werte:

  • Byte 1 (0x8f): High-Nibble = SRT (Step Rate Time, wie lange jeder Schritt des Kopfes dauert, in umgekehrten Einheiten – höhere Werte = schnellere Schritte), Low-Nibble = HUT (Head Unload Time, wie lange gewartet wird, bevor der Kopf nach einer Operation "losgelassen" wird).

  • Byte 2 (0x1e): obere Bits = HLT (Head Load Time, wie lange es dauert, bis sich der Kopf vor dem Lesen/Schreiben gesetzt hat), unterstes Bit = NDMA. NDMA=0 ist das Wichtige: Damit sagen wir dem FDC, dass wir DMA für die Datenübertragung verwenden werden, nicht PIO.

Ich verwende DMA-Transfers, weil (ich glaube, das ist in floppy.h kommentiert) bochs keine PIO-Transfers unterstützt, sondern nur DMA.

Wenn du dieses Bit vergisst, erwartet der FDC, dass du jedes Byte manuell aus dem FIFO liest, und die ganze DMA-Pipeline, die wir weiter unten aufbauen, ist für die Katz.

Da der Reset diese Konfiguration löscht, müssen wir sie bei jedem floppy_init() erneut senden.

Configure

static bool floppy_configure(void)
{
    if (!fdc_write(0x13))   /* CONFIGURE */
        return false;
    if (!fdc_write(0x00))   /* reserved byte */
        return false;
    if (!fdc_write(0x57))   /* EIS=1, EFIFO=0, POLL=1, FIFOTHR=7 */
        return false;
    if (!fdc_write(0x00))   /* PRETRK */
        return false;

    return true;
}

0x57 aktiviert drei Dinge: EIS (Enable Implied Seek, der FDC führt den Seek automatisch vor einem Read/Write aus, ohne dass du ihn explizit dazu aufforderst), EFIFO=0 (was kontraintuitiv den internen 16-Byte-FIFO des Controllers aktiviert statt ihn zu deaktivieren – der Name des Bits ist genau das Gegenteil von dem, was man erwarten würde) und FIFOTHR=7, den 8-Byte-Schwellenwert, der einen DMA-/Speicherzugriff auslöst. Das gibt dem System etwas Spielraum, damit es bei etwas Bus-Latenz keine Bytes verliert.

CONFIGURE erzeugt wie SPECIFY ebenfalls keinen IRQ und hat keine Result-Phase.

Motor und timing

static void floppy_motor_on(void)
{
    outb(FDC_DOR, FDC_DOR_ENABLE | FDC_DOR_IRQ | FDC_DOR_MOTOR_A | FDC_DRIVE_A);
    pit_wait_ms(500);
}

500ms sind mehr als das, was osdev dokumentiert (dort werden 300ms für 3,5" vorgeschlagen und es heißt sogar, dass 50ms reichen). In meinem echten Setup waren 50ms nicht genug und ich hatte sporadische Seek-Fehler. Ich habe mich lieber für eine halbe Sekunde auf der sicheren Seite entschieden, statt dem theoretischen Minimum hinterherzujagen – die Kosten für ein etwas längeres Warten sind im Vergleich zu einem fehlgeschlagenen Read mitten im Bootvorgang völlig unbedeutend.

Dafür brauche ich einen Timer, der nicht davon abhängt, CPU-Zyklen von Hand zu zählen, also kommt pit.c ins Spiel.

El PIT (Programmable Interval Timer)

void pit_init(uint32_t frequency)
{
    pit_hz = frequency;
    uint32_t divisor = PIT_FREQUENCY / frequency;

    outb(PIT_COMMAND, 0x36);   /* Ch0, lo/hi, mode 3, binario */
    outb(PIT_CH0, divisor & 0xFF);
    outb(PIT_CH0, (divisor >> 8) & 0xFF);
}

Der PIT läuft intern mit 1193182 Hz (PIT_FREQUENCY). Mit pit_init(100) konfiguriere ich einen Teiler, der alle 10ms einen IRQ0 auslöst, also 100 Ticks pro Sekunde. pit_ticks ist ein globaler Counter, der von pit_irq_handler() inkrementiert wird, und alles andere im System (pit_wait_ms, die FDC-Timeouts, floppy_wait_irq) stützt sich auf diesen Counter, statt blind Busy-Waiting zu machen.

static bool floppy_wait_irq(void)
{
    uint32_t start = pit_get_ticks();

    while (!floppy_irq) {
        if ((pit_get_ticks() - start) >= 200) {
            terminal_writestring("FLOPPY: IRQ timeout\n");
            return false;
        }
        __asm__ volatile ("hlt");
    }
    return true;
}

200 Ticks bei 100Hz bedeuten ein 2-Sekunden-Timeout, damit der IRQ6 des FDC ankommt – absichtlich großzügig, weil ich nicht will, dass ein echtes Floppy-Laufwerk (das etwas Zeit für Spin-up und Seek brauchen kann) einen falschen Timeout auslöst.

Beachtet das hlt in der Schleife: Statt per Spin-Waiting CPU-Zeit zu verbraten, hält der Prozessor bis zum nächsten Interrupt an (entweder vom PIT oder vom FDC), genau das, was ein echter Kernel tun sollte, wenn er auf I/O wartet.

Sense Interrupt, Recalibrate y Seek

RECALIBRATE und SEEK erzeugen einen IRQ, haben aber keine eigene Result-Phase. Der Status muss separat mit SENSE INTERRUPT abgefragt werden:

static bool floppy_sense_interrupt(uint8_t *st0, uint8_t *cyl)
{
    inb(0x80);
    inb(0x80);

    if (!fdc_write(FDC_CMD_SENSE_INT))
        return false;
    if (!floppy_read_byte(st0))
        return false;
    if (!floppy_read_byte(cyl))
        return false;

    return true;
}

RECALIBRATE bewegt den Kopf auf Spur 0 (nützlich, um die bekannte physische Position zu "resynchronisieren"), während SEEK ihn auf einen bestimmten Zylinder bewegt. In beiden Fällen mache ich nach dem IRQ ein SENSE INTERRUPT und prüfe zwei Dinge: das Seek End-Bit (st0 & 0x20) und ob der gemeldete Zylinder (cyl) mit dem erwarteten übereinstimmt (0 beim Recalibrate, der angeforderte Zylinder beim Seek). Wenn etwas schiefgeht, spucke ich es auf der Konsole aus.

Lesen und Schreiben von Sektoren

Der Read/Write-Befehl sendet insgesamt 9 Bytes:

if (!fdc_write(FDC_CMD_READ_DATA | 0xC0)) { [...] }  /* MT=1, MFM=1 */
if (!fdc_write((head << 2) | FDC_DRIVE_A)) { [...] } /* HD + DR */
if (!fdc_write(cylinder)) { [...] }                  /* C */
if (!fdc_write(head)) { [...] }                      /* H */
if (!fdc_write(sector)) { [...] }                    /* R */
if (!fdc_write(2)) { [...] }                         /* N = 512 bytes */
if (!fdc_write(18)) { [...] }                        /* EOT: último sector de la pista */
if (!fdc_write(0x1B)) { [...] }                      /* GPL */
if (!fdc_write(0xFF)) { [...] }                      /* DTL, ignorado cuando N != 0 */

0xC0 im Befehl aktiviert MT (Multi-Track, der Controller kann automatisch mit dem nächsten Kopf weitermachen, wenn er EOT überschreitet) und MFM (die Standardmodulation für Floppys und magnetische Speicher ab Double Density aufwärts). N=2 sagt dem FDC "jeder Sektor ist 512 Bytes groß", anhand der Standard-Größentabelle des Chips (0=128B, 1=256B, 2=512B…). EOT=18 ist die Anzahl der Sektoren pro Spur bei der 1,44MB-Geometrie.

Nach dem IRQ (der kommt, wenn der DMA-Transfer abgeschlossen ist, nicht vorher) folgt die Result-Phase mit 7 Bytes (ST0 bis ST2 plus C/H/R/N als Rückgabewerte), von denen ich nur die ersten drei prüfe:

if (st[0] & 0xC0) { [...] }   /* error phase */
if (st[1] != 0)   { [...] }   /* ST1: errores de datos, CRC, etc. */
if (st[2] != 0)   { [...] }   /* ST2: errores específicos de la pista/sector */

Jedes gesetzte Bit in ST1/ST2 behandle ich als kompletten Fehler der Operation – ich versuche nicht zu unterscheiden, ob es sich um "einen behebbaren CRC-Fehler" oder "den Sektor gibt es nicht" handelt; ich wiederhole einfach die komplette Operation.

floppy_write_sector_impl ist fast ein Spiegelbild des Reads. Dabei ändert sich der Befehl (FDC_CMD_WRITE_DATA | 0xC0, MFM ohne MT nötig zu haben… obwohl ich im Code dasselbe 0xC0 gelassen habe) und die DMA-Richtung.

CHS und LBA-Konvertierung

Damit ich im restlichen Kernel nicht über Zylinder/Kopf/Sektor nachdenken muss, stelle ich floppy_read_lba / floppy_write_lba bereit:

uint32_t cylinder = lba / (2 * 18);
uint32_t tmp = lba % (2 * 18);
uint32_t head = tmp / 18;
uint32_t sector = (tmp % 18) + 1;

Das setzt die feste Geometrie einer 1,44MB-Diskette voraus: 2 Köpfe, 18 Sektoren pro Spur, 80 Zylinder (2×18×80 = 2880 Sektoren insgesamt, daher das if (lba >= 2880) return false;). Es gibt keine Geometrie-Erkennung über den Media Descriptor und keine Unterstützung für andere Formate – für tOSh reicht ein einziger Diskettentyp völlig aus, und die fest codierte Geometrie spart eine ganze Abstraktionsebene, die ich nicht brauche.

Retry logic

bool floppy_read_sector(uint8_t cylinder, uint8_t head, uint8_t sector, uint8_t *buffer)
{
    for (int attempt = 0; attempt < 3; attempt++) {
        if (floppy_read_sector_impl(cylinder, head, sector, buffer))
            return true;

        terminal_writestring("FLOPPY: retrying read...\n");
        floppy_motor_on();
        floppy_recalibrate();
        floppy_motor_off();
    }
    return false;
}

Echte Disketten sind anfällig für vorübergehende Fehler: Staub, abgenutztes Medium, ein Kopf, der beim ersten Versuch nicht richtig aufgesetzt hat, einen KÜHLSCHRANKMAGNETEN ALS PAPIERBESCHWERER AUF EINEN STAPEL DISKETTEN ZU LEGEN, usw…

Statt beim ersten Fehler sofort aufzugeben, versuche ich es 3-mal erneut und mache zwischen jedem Versuch ein vollständiges RECALIBRATE, um den Kopf zu zwingen, seine physische Position neu zu synchronisieren – wenn der Fehler gerade dadurch verursacht wurde, dass der Kopf nicht korrekt positioniert war, behebt das Recalibrate das Problem vor dem nächsten Versuch.

DMA, 8237-Chip

Der FDC liefert die gelesenen Daten bei NDMA=0 (siehe Specify weiter oben) nicht Byte für Byte über den FIFO – er verwendet den 8237-DMA-Chip, um direkt in den Speicher zu schreiben, während die CPU etwas anderes macht (oder in unserem Fall in einem hlt wartet).

static void dma_transfer(uint8_t channel, uint32_t address, uint16_t count, uint8_t mode)
{
    uint8_t page = (address >> 16) & 0xff;
    uint16_t offset = address & 0xffff;

    outb(DMA_MASK, 0x04 | channel);   /* deshabilita el canal */
    outb(DMA_CLEAR_FF, 0);            /* resetea el flip-flop de byte lo/hi */

    outb(addr_port, offset & 0xff);
    outb(addr_port, (offset >> 8) & 0xff);
    outb(page_port, page);

    outb(DMA_CLEAR_FF, 0);

    count--;                          /* el 8237 cuenta N-1 */
    outb(count_port, count & 0xff);
    outb(count_port, (count >> 8) & 0xff);

    outb(DMA_MODE, mode | channel);
    outb(DMA_MASK, channel);          /* habilita el canal */
}

Ein paar Punkte sind hier erwähnenswert:

  • Das Flip-Flop ist ein internes Bit im 8237, das angibt, ob das nächste Byte, das an einen Adress-/Count-Port geschrieben wird, das Low-Byte oder das High-Byte ist. Da dieser Zustand zwischen den Kanälen geteilt wird, muss man es explizit zurücksetzen (DMA_CLEAR_FF), bevor man sowohl die Adresse als auch den Count schreibt – sonst kann es passieren, dass das High-Byte dort landet, wo eigentlich das Low-Byte hin sollte, und man am Ende eine Adresse zusammenbaut, die weiß der Geier wohin zeigt.

  • Das Page Register (DMA_PAGE_CH2 = 0x81) ist ein Überbleibsel davon, dass der ursprüngliche 8237 für den Offset nur 16-Bit-Adressen verarbeitet. Um 24-Bit-Speicheradressen zu erreichen (wie sie ein echter PC braucht), wird das High-Byte der Adresse separat in das Page Register des entsprechenden Kanals geschrieben. Das ist auch der Grund für die Einschränkung, dass der Buffer keine 64KiB-Grenze überschreiten darf: Der 8237 erhöht den 16-Bit-Offset bei jedem übertragenen Byte, greift während der Übertragung aber nie auf das Page Register zu. Wenn der Buffer nahe am Ende einer 64-KB-Page beginnt und darüber hinausläuft, wechselt der DMA nicht auf die nächste Page – der Offset läuft über und beginnt, den Anfang derselben 64-KB-Page zu überschreiben. Deshalb habe ich den Floppy-Buffer so angelegt:

static uint8_t floppy_dma_buffer[512]
    __attribute__((aligned(512), section(".dma")));

Die Ausrichtung auf 512 Bytes (die Größe eines Sektors) garantiert, dass du niemals einen 512-Byte-Buffer hast, der zum Beispiel bei Adresse 0xFFF00 beginnt und beim nächsten 64KB-Block über 0x10000 hinausläuft. Die .dma-Section des Linker-Scripts (siehe Teil III) legt diesen Buffer in einen eigenen, auf 4KB-Seiten ausgerichteten Bereich, weit weg von allen anderen Daten. Dadurch tritt in der Praxis nie ein Boundary-Crossing auf, sodass der Treiber dafür keine Runtime-Prüfung braucht.

  • Der Modus (0x46 zum Lesen, 0x4A zum Schreiben) folgt der Namenskonvention des 8237 aus Sicht des Peripheriegeräts, nicht aus Sicht des Speichers: dma_read() bedeutet "der FDC liest von der Diskette und schreibt in den Speicher" (wodurch in floppy_read_sector_impl effektiv dein Buffer gefüllt wird), während dma_write() bedeutet "der Speicher wird gelesen und an den FDC geschrieben" (um Daten auf die Diskette zu schicken). Der Name ist leicht verwirrend, wenn man in Begriffen der CPU statt des Peripheriegeräts denkt – hier sind dma_read/dma_write aus der Perspektive "Was macht der FDC mit den Daten?" benannt, was mit der Dokumentation des Chips von Intel übereinstimmt.

  • count--, weil der 8237 den Count als N-1 erwartet (du überträgst count Bytes, aber das interne Register zählt von count-1 bis 0 herunter).

Grob gesagt richtet also floppy_read_sector mit dma_read() Kanal 2 für den Buffer und 512 Bytes ein, der READ DATA-Befehl wird an den FDC gesendet, die Übertragung läuft im Hintergrund, während die CPU mit hlt wartet, und wenn sie fertig ist, erzeugt der FDC IRQ6, den floppy_wait_irq behandelt.

Das ist eine ganze Menge, und vielleicht lassen sich manche Dinge besser verstehen, wenn man den Source-Code liest.

Wie ich am Anfang dieser ganzen Artikelserie schreibe, kannst du dir den Source von der Seite Resources herunterladen, wenn du möchtest.

Das Dateisystem

Probando el Filesystem en mi máquina del 97'Das Dateisystem auf meiner ‘97er Maschine testen

Bringen wir es zum Laufen'

Für tOSh gibt es keine Blöcke, kein FAT, keinen Verzeichnisbaum, kein Journaling, keine langen Dateinamen und keine Pfade.

tOSh scheißt auf den ganzen Kram, nicht einmal die Konsistenz deiner Daten interessiert es. tOSh ist ein Betriebssystem NUR FÜR DIE VERRÜCKTEN UND DIE MUTIGEN.

Nachdem das gesagt und diese Klarstellung gemacht ist, fange ich an, euch zu erzählen, wie ich das aufgebaut habe.

Es gibt ein Verzeichnis mit fester Größe für bis zu 256 Dateien, jede davon mit einem Namen, einem Startsektor und einer Größe. Punkt.

Der Grund dafür ist derselbe wie bei der festen Floppy-Geometrie: Jede Funktion eines echten Dateisystems (FAT, ext2, was auch immer) fügt eine Ebene der Indirektion hinzu – Blöcke, verkettete Cluster-Listen, Bitmaps für freien Speicher – die Probleme löst, die tOSh noch gar nicht hat, etwa echte Fragmentierung auf einer Diskette, die immer wieder gefüllt und geleert wird. Für das, was ich brauche (ein paar kleine Dateien während der Kernel-Entwicklung auf einer 1,44MB-Diskette persistent zu speichern), reicht ein flaches Verzeichnis völlig aus.

Disk-Layout

#define FS_SUPERBLOCK_SECTOR   256

#define FS_DIRECTORY_START     257
#define FS_DIRECTORY_SECTORS   32

#define FS_DATA_START          320

+--------------------------+
| 0    BOOT                |
+--------------------------+
| 1-8  STAGE1              |
+--------------------------+
| 9-136 KERNEL             | <- 64 KiB
+--------------------------+
| 137-255 RESERVED         |
+--------------------------+
| 256     SUPERBLOCK       |
| 257-288 DIRECTORY        |
| 289-319 RESERVED         |
+--------------------------+
| 320-2879 FILE DATA       | <- ~1.28 MB
+--------------------------+

Das Dateisystem beginnt bei Sektor 256, weit hinter dem Kernel (der bei 136 endet). Der Gap, den ich zwischen 137 und 255 lasse (119 Sektoren, ~59KB), ist Spielraum, damit der Kernel während der Entwicklung wachsen kann, ohne mit dem Dateisystem zu kollidieren – denkt daran, dass das Makefile/build.sh aus Teil III prüft, dass der Kernel die dafür vorgesehenen 128 Sektoren nicht überschreitet. Dieser reservierte Bereich ist also das tatsächliche Polster, bevor ich das gesamte Layout verschieben muss.

Der Gap zwischen 289 und 319 (31 Sektoren) ist dasselbe, aber für das Verzeichnis: FS_DIRECTORY_SECTORS ist fest auf 32 gesetzt, aber die tatsächliche Größe, die struct fs_file[FS_MAX_FILES] belegt, kann am Ende kleiner sein. Dieser Spielraum erspart mir, FS_DATA_START jedes Mal neu berechnen zu müssen, wenn ich FS_MAX_FILES oder die Größe von fs_file ändere.

Der Superblock

struct fs_superblock {
    uint32_t magic;
    uint16_t version;
    uint16_t sector_size;
    uint32_t total_sectors;
    uint32_t data_start;
} __attribute__((packed));

FS_MAGIC ist 0x48534f54, was als Little-Endian-ASCII-Bytes gelesen TOSH ergibt. fs_is_initialized() liest Sektor 256 und vergleicht diesen Magic-Wert – wenn er nicht übereinstimmt, geht es davon aus, dass die Diskette nie mit diesem Dateisystem formatiert wurde, und das war’s; es wird nicht versucht, irgendetwas von diesem Sektor zu "recovern" oder zu interpretieren. __attribute__((packed)) ist notwendig, damit das Struct exakt die von mir angegebenen Bytes belegt, ohne Padding, das der Compiler zur Ausrichtung einfügen würde.

Das Verzeichnis

struct fs_file {
    char     name[FS_FILENAME_MAX];
    uint32_t start_sector;
    uint32_t size;
    uint8_t  used;
} __attribute__((packed));

static struct fs_file directory[FS_MAX_FILES];

Das gesamte Verzeichnis ist ein Array mit 256 Einträgen, das während der Laufzeit des Kernels im RAM liegt und bei jeder Änderung (create, write, delete) mit fs_save_directory() vollständig auf die Diskette geschrieben wird. Es gibt keine separate Bitmap für "freie Einträge" – ein Eintrag ist frei, wenn used == 0 ist, und eine Datei zu suchen (fs_find) bedeutet einfach, das Array durchzugehen und die Namen zu vergleichen.

Das bedeutet, dass jede Operation, die das Dateisystem verändert, alle 32 Sektoren des Verzeichnisses neu schreibt, selbst wenn sich nur ein einziger Eintrag geändert hat. In Bezug auf I/O ist das offensichtlich nicht optimal, aber bei einer Diskette, die ohnehin schon quälend langsam ist, macht der Unterschied zwischen 1 und 32 geschriebenen Sektoren keinen Unterschied für die Benutzererfahrung, und ich erspare mir, nachverfolgen zu müssen, welcher bestimmte Verzeichnissektor zu welchem Eintrag gehört.

Keinen freien Speicher verwalten

static uint32_t fs_next_free_sector(void)
{
    uint32_t sector = FS_DATA_START;

    for (int i = 0; i < FS_MAX_FILES; i++) {
        if (!directory[i].used)
            continue;

        uint32_t sectors = (directory[i].size + 511) / 512;
        uint32_t end = directory[i].start_sector + sectors;

        if (end > sector)
            sector = end;
    }

    return sector;
}

Die Speicherzuweisung ist so primitiv, wie es nur geht: Ich gehe alle belegten Dateien durch, finde das höchste start_sector + sectors_occupied, und dort beginnt die nächste Datei. Es gibt keine Bitmap für freie Sektoren, keine Free-List, keine Kompression.

Die direkte Konsequenz daraus –und eine bewusste Entscheidung, DAS IST KEIN BUG, DAS IST EIN FEATURE– ist, dass fs_delete() den Speicher weder freigibt noch recycelt.

Beim Löschen einer Datei wird nur ihr Verzeichniseintrag geleert (used = 0); die von ihr belegten Sektoren bleiben dort und werden von fs_next_free_sector() für immer ignoriert, weil diese Funktion keine Einträge mit used == 0 berücksichtigt, sondern nur den am weitesten hinten liegenden Bereich, der von aktuell existierenden Dateien belegt ist… aber dieser am weitesten hinten liegende Punkt kann von einer Datei hinterlassen worden sein, die gar nicht mehr existiert. Anders gesagt: Dateien zu erstellen und zu löschen hinterlässt Lücken, die niemals wieder verwendet werden, bis man die gesamte Diskette mit fs_format() neu formatiert. Das nannte man Festplattenfragmentierung und genau das sollte der "Windows-Defragmentierer" beheben. Bei MS-DOS und Windows 9x trat das aus anderen Gründen ebenfalls ein bisschen auf.

Für den aktuellen Stand von tOSh ist das akzeptabel: Das Dateisystem ist (noch, wer weiß) nicht für intensives, lang andauerndes Schreiben und Löschen gedacht, sondern dafür, eine Handvoll Konfigurationsdateien oder System-Binaries persistent zu speichern. Wenn das eines Tages zu einem echten Problem wird (kkjjj, also niemals, lang lebe tOSh), wäre die einfachste Lösung ohne das Design komplett neu zu bauen, eine Bitmap für freie Sektoren hinzuzufügen oder auf ein Block-Schema mit Free-List umzusteigen – aber das würde das Dateisystem komplett verändern.

Operationen

fs_create, fs_write, fs_read und fs_delete sind angesichts des oben erklärten Designs ziemlich direkt:

  • fs_create sucht einen freien Eintrag, weist ihm über fs_next_free_sector() den nächsten Sektor zu, speichert den Namen und persistiert das Verzeichnis. Die Größe startet bei 0 – es gibt noch keine Daten, nur die Reservierung der Position.

  • fs_write teilt die Daten in 512-Byte-Sektoren auf (und füllt den letzten mit Nullen auf, wenn die Größe kein exaktes Vielfaches ist) und schreibt sie ab start_sector sequentiell. Es aktualisiert size und persistiert erneut das gesamte Verzeichnis.

  • fs_read macht das Gegenteil: Es berechnet anhand von size, wie viele Sektoren die Datei belegt, liest sie alle und kopiert nur die gültigen Bytes (also nicht das Null-Padding) in den Buffer des Callers.

  • fs_delete leert den Eintrag, ohne die Datensektoren anzufassen (siehe direkt oben).

Keine dieser vier Funktionen unterstützt Dateien, die über den freien Platz hinauswachsen, den sie zum Zeitpunkt ihrer Erstellung hatten – es gibt kein Konzept, eine Datei über den Platz hinaus zu "erweitern", der beim ersten zusammenhängenden Schreiben verfügbar war, weil fs_write immer ab start_sector schreibt und davon ausgeht, dass der Platz bereits durch fs_create + die Erstellungsreihenfolge der anderen Dateien reserviert wurde.

Bekannte Einschränkungen

Damit das dokumentiert ist und nicht mit der Zeit verloren geht, wenn ich in drei Jahren wieder anfange, Dinge in tOSh zu implementieren:

  • Feste maximale Dateisystemgröße von FS_TOTAL_SECTORS = 2880 (die kompletten 1,44MB der Diskette, ohne zu berücksichtigen, dass ein Teil davon bereits vom Bootloader/Kernel belegt ist – dafür zu sorgen, dass man das nicht überschreibt, ist Aufgabe eines korrekt gesetzten FS_DATA_START und nichts, was das Dateisystem zur Laufzeit überprüft). Trotzdem wäre es vielleicht ganz nett, wenn ich das Dateisystem noch einmal anfasse oder neu schreibe, auch Unterstützung für Festplatten einzubauen und das von Anfang an zu berücksichtigen, um das Ganze etwas ernsthafter zu machen. Mal sehen.
  • Nicht-hierarchische Dateinamen: FS_FILENAME_MAX = 32 Bytes, kein Path-Trenner, alles lebt im selben hardcodierten Namespace.
  • Keine Dateifragmentierung: Jede Datei belegt einen zusammenhängenden Bereich von Sektoren. Das vereinfacht den Code enorm (man muss keine Blockketten verwalten), bedeutet aber auch, dass große Dateien in einem Dateisystem mit vielen Lücken durch vorherige Löschvorgänge irgendwann nicht mehr hineinpassen, obwohl insgesamt noch genug "freier Speicher" über die verschiedenen Lücken verteilt vorhanden ist. Irgendwann wird das Dateisystem, nachdem es genug Dateien erstellt und gelöscht hat, einfach crashen :)
  • Kein Journaling und keinerlei Recovery-Mechanismus für einen Stromausfall mitten in einem fs_save_directory(). Wenn das Schreiben des Verzeichnisses mittendrin abgebrochen wird, bleibt eine teilweise geschriebene Version zurück und man kann sogar das gesamte Dateisystem verlieren, weil auch der Superblock beschädigt werden kann.

Beim nächsten Mal lassen wir tOSh auf mehreren Maschinen laufen, emulierten und echten, geliehenen und/oder zu diesem Zweck von lieben Nerd-Freunden und Kollegen gespendeten, die ich sehr respektiere und ganz doll lieb habe.

Referenzen