Anfragen bearbeiten: Das Ganze noch einmal genauer

Der oben gezeigte sbull-Treiber funktioniert sehr gut. In einfachen Situationen (wie im Falle von sbull) kann die request-Funktion mit den Makros aus <linux/blk.h> einfach geschrieben werden und führt zu einem funktionierenden Treiber. Wie bereits erwähnt wurde, sind Block-Treiber aber oft ein Kernel-Bestandteil, dessen Performance entscheidende Bedeutung hat. Auf dem einfachen oben gezeigten Code basierende Treiber werden in vielen Situationen keine besonders gute Performance aufweisen und könnten sogar das System insgesamt verlangsamen. In diesem Abschnitt schauen wir uns die Details der Funktionsweise der I/O-Anfrage-Warteschlange unter dem Gesichtspunkt schnellerer, effizienterer Treiber an.

Die I/O-Anfrage-Warteschlange

Alle Block-Treiber haben mindestens eine I/O-Anfrage-Warteschlange. Diese Warteschlange enthält zu jedem Zeitpunkt alle I/O-Operationen, die der Kernel von den Geräten des Treibers ausgeführt haben möchte. Die Verwaltung dieser Schlange ist kompliziert, und die Performance des Systems hängt davon ab.

Die Schlange wurde im Hinblick auf physikalische Festplattenlaufwerke entwickelt. Bei diesen ist die benötigte Zeit, um einen Datenblock zu übertragen, normalerweise recht klein. Die Zeit, die es kostet, den Lesekopf für die Übertragung zu positionieren (seek) kann dagegen sehr groß sein. Daher versucht der Linux-Kernel, die Anzahl und den Umfang der Kopfpositionierungen des Geräts zu minimieren.

Um diese Ziele zu erreichen, werden zwei Dinge getan. Zunächst werden Anfragen nach auf der Festplatte benachbarten Sektoren zusammengefaßt. Die meisten modernen Dateisysteme versuchen, Dateien in zusammenhängenden Sektoren unterzubringen; als Folge davon sind Anfragen nach zusammenhängenden Teilen der Festplatte häufig. Der Kernel verwendet außerdem einen “Fahrstuhl-Algorithmus” (elevator algorithm). Ein Fahrstuhl in einem Wolkenkratzer fährt entweder nach oben oder nach unten; er setzt seine Fahrt in eine dieser Richtungen fort, bis alle “Anfragen” (Ein- oder Aussteigewünsche) erfüllt worden sind. Genauso versucht der Kernel, den Kopf sich so lange wie möglich in die gleiche Richtung bewegen zu lassen; dieser Ansatz pflegt die Positionierungszeiten zu minimieren, trotzdem aber sicherzustellen, daß alle Anfragen mit der Zeit erfüllt werden.

Eine Linux-I/O-Anfrage-Warteschlange wird durch eine Struktur des Typs request_queue repräsentiert, die in <linux/blkdev.h> deklariert ist. Die request_queue-Struktur sieht file_operations und anderen solchen Objekten dahingehend ähnlich, als daß sie Zeiger auf eine Reihe von Funktionen enthält, die auf der Warteschlange arbeiten — so ist etwa die request-Funktion des Treibers dort gespeichert. Es gibt außerdem einen Warteschlangen-Kopf (unter Verwendung der Funktionen aus <linux/list.h>, die in "the Section called Verkettete Listen in Kapitel 10" in Kapitel 10 beschrieben werden), der auf die Liste der für das Gerät ausstehenden Anfragen verweist.

Diese Anfragen sind natürlich vom Typ struct request; wir haben uns schon einige der Felder in dieser Struktur angeschaut. In Wirklichkeit ist die request-Struktur ist aber ein wenig komplizierter; um sie zu verstehen, müssen wir einen kleinen Exkurs in die Struktur des Buffer-Cache von Linux machen.

Die request-Struktur und der Buffer-Cache

Das Design der request-Struktur wird von der Speicherverwaltung in Linux bestimmt. Wie die meisten Unix-artigen Systeme verwaltet Linux einen Buffer-Cache, einen Speicherbereich, der Kopien der Blocks auf der Festplatte enthält. Ein Großteil der “Festplatten”-Operationen auf höheren Ebenen des Kernels wie dem Dateisystem-Code wirken in Wirklichkeit nur auf dem Buffer-Cache und erzeugen keine I/O-Operationen. Durch aggressives Cachen kann der Kernel viele Lese-Operationen vermeiden; mehrere Schreiboperationen können oft zu einem einzigen physikalischen Schreiben auf die Festplatte zusammengefaßt werden.

Ein unvermeidbarer Effekt des Buffer-Caches ist aber, daß Blocks, die auf der Festplatte benachbart sind, fast sicher nicht nebeneinander im Speicher liegen. Der Buffer-Cache ist dynamisch, und die Blocks liegen weit verteilt. Um alles zu verwalten, pflegt der Kernel den Buffer-Cache über buffer_head-Strukturen. Zu jedem Daten-Puffer gehört ein buffer_head. Diese Struktur enthält viele Felder, von denen die meisten für Treiberautoren nicht interessant sind. Einige sind aber wichtig, darunter die folgenden:

char *b_data;

Der eigentliche Daten-Block, der zu diesem Puffer-Kopf gehört.

unsigned long b_size;

Die Größe des Blocks, auf die b_data zeigt.

kdev_t b_rdev;

Das Gerät, das den Block enthält, der von diesem Buffer-Head repräsentiert wird.

unsigned long b_rsector;

Die Sektornummer, an der sich dieser Block auf der Festplatte befindet.

struct buffer_head *b_reqnext;

Ein Zeiger auf eine verkettete Liste von Puffer-Kopf-Strukturen in der Anfrage-Warteschlange.

void (*b_end_io)(struct buffer_head *bh, int uptodate);

Ein Zeiger auf eine Funktion, die aufgerufen werden soll, wenn die I/O-Operation auf diesem Puffer abgeschlossen ist. bh ist der Puffer-Kopf selbst, und uptodate ist ungleich 0, wenn die I/O-Operation erfolgreich war.

Jeder Block, der an die request-Funktion eines Treibers übergeben wird, befindet sich entweder im Buffer-Cache oder, in seltenen Fällen, an anderer Stelle, sieht aber so aus, als befände er sich im Buffer-Cache.[1] Daher hat es jede an den Treiber übergebene Anfrage mit einer oder mehreren buffer_head-Strukturen zu tun. Die request-Struktur enthält ein Feld (mit dem Namen bh), das auf eine verkettete Liste dieser Strukturen zeigt; um eine Anfrage zu erfüllen, muß die angeforderte I/O-Operation auf jedem Puffer der Liste durchgeführt werden. Abbildung 12-2 zeigt, wie die Anfrage-Warteschlange und die buffer_head-Strukturen zusammenpassen.

Abbildung 12-2. Puffer in der I/O-Anfrage-Warteschlange

Anfragen bestehen nicht aus zufälligen Listen von Puffern; alle Puffer-Köpfe in einer Anfrage gehören vielmehr zu einer Folge auf der Festplatte benachbarter Blocks. Eine Anfrage ist damit in gewissem Sinne eine einzige Operation, die sich auf eine (möglicherweise lange) Liste von Blocks auf der Festplatte bezieht. Diese Gruppierung von Blocks wird Clustering genannt; wir schauen uns dies noch genauer an, nachdem wir die Besprechung der Anfrage-Liste beendet haben.

Manipulation der Anfrage-Warteschlange

Die Header-Datei <linux/blkdev.h> definiert eine kleine Anzahl von Funktionen, die die Anfrage-Warteschlangen manipulieren. Die meisten dieser Funktionen sind als Präprozessor-Makros definiert. Nicht alle Treiber müssen auf dieser Ebene mit der Anfrage-Warteschlange arbeiten, aber es kann hilfreich sein, sich damit vertraut zu machen, wie alles zusammenhängt. Die meisten Funktionen, die mit Anfrage-Warteschlangen arbeiten, führen wir ein, wenn wir sie brauchen, aber einige wenige sollen schon hier genannt werden.

struct request *blkdev_entry_next_request(struct list_head *head);

Gibt den nächsten Eintrag in der Anfrage-Liste zurück. Normalerweise ist das head-Argument das queue_head-Element der request_queue-Struktur; in diesem Fall gibt die Funktion den ersten Eintrag in der Warteschlange zurück. Die Funktion verwendet das Makro list_entry, um in die Liste hineinschauen zu können.

struct request *blkdev_next_request(struct request *req);, struct request *blkdev_prev_request(struct request *req);

Diese Funktionen geben zu einer gegebenen Anfrage-Struktur die nächste beziehungsweise vorherige Struktur in der Anfrage-Warteschlange zurück.

blkdev_dequeue_request(struct request *req);

Entfernt eine Anfrage aus ihrer Anfrage-Warteschlange.

blkdev_release_request(struct request *req);

Gibt eine Anfrage-Struktur an den Kernel zurück, wenn sie vollständig abgearbeitet worden ist. Jede Anfrage-Warteschlange verwaltet eine eigene Liste von Anfrage-Strukturen (genauer gesagt sogar zwei, eine zum Lesen und eine zum Schreiben); diese Funktion stellt die Struktur in die passende Liste zurück. blkdev_release_request weckt auch alle Prozesse, die auf eine freie Anfrage-Struktur warten.

Alle diese Funktionen setzen voraus, daß man die io_request_lock-Sperre hat, die wir als nächstes besprechen.

Die I/O-Anfrage-Sperre

Die I/O-Anfrage-Warteschlange ist eine komplexe Datenstruktur, auf die an vielen Stellen im Kernel zugegriffen wird. Es ist durchaus möglich, daß der Kernel der Warteschlange weitere Anfragen hinzufügen muß, während Ihr Treiber gleichzeitig welche entnimmt. Daher unterliegt die Warteschlange auch den üblichen Race Conditions und muß entsprechend geschützt werden.

In Linux 2.2 und 2.4 sind alle Anfrage-Warteschlangen mit einem einzigen globalen Spinlock namens io_request_lock geschützt. Jeder Code, der Anfrage-Warteschlangen manipuliert, muß sich erst diese Sperre holen und Interrupts abschalten. Davon gibt es nur eine kleine Ausnahme: Der allererste Eintrag in der Anfrage-Warteschlange gilt per Default als im Besitzt des Treibers befindlich. Wenn man sich das io_request_lock vor der Arbeit mit der Anfrage-Warteschlange nicht holt, kann die Warteschlange beschädigt werden, was kurz danach zu einem Systemabsturz führen wird.

Die einfache request-Funktion, die wir oben gezeigt haben, mußte sich nicht um diese Sperre kümmern, weil der Kernel die request-Funktion immer mit gehaltener io_request_lock-Sperre aufruft. Ein Treiber ist also davor geschützt, die Anfrage-Warteschlange zu beschädigen oder die request-Funktion reentrant aufzurufen. Dies wurde so eingeführt, damit nicht-SMP-fähige Treiber auch auf Multiprozessor-Systemen funktionieren.

Beachten Sie aber, daß es teuer ist, die io_request_lock-Sperre zu halten. Solange Ihr Treiber diese Sperre hält, können keine anderen Anfragen an irgendeinen Block-Treiber im System vorgemerkt werden und keine anderen request-Funktionen aufgerufen werden. Ein Treiber, der diese Sperre zu lange hält, kann das ganze System ausbremsen.

Gut geschriebene Block-Treiber geben diese Sperre daher so schnell wie möglich frei. Wir werden in Kürze ein Beispiel sehen, wie man dies tun kann. Block-Treiber, die die io_request_lock-Sperre freigeben, müssen aber unter Berücksichtigung einer Reihe wichtiger Punkte geschrieben werden. Zunächst muß die request-Funktion diese Sperre vor dem Zurückkehren immer erneut erwerben, weil der aufrufende Code erwartet, daß die Sperre gehalten wird. Zweitens besteht die Gefahr, daß request-Funktion unmittelbar nach Aufgabe der io_request_lock-Sperre reentrant aufgerufen wird; die Funktion muß dies berücksichtigen.

Eine Variante des letztgenannten Falles kann auch auftreten, wenn Ihre request-Funktion zurückkehrt, während noch eine I/O-Anfrage aktiv ist. Viele Treiber für echte Hardware fangen eine I/O-Operation an und springen dann zurück; die Arbeit wird im Interrupt-Handler des Treibers beendet. Wir werden uns Interrupt-gesteuerte Block-I/O weiter hinten in diesem Kapitel noch detailliert anschauen. Im Moment soll nur erwähnt werden, daß die request-Funktion aufgerufen werden kann, während diese Operationen noch laufen.

Manche Treiber berücksichtigen die Reentranz der request-Funktion, indem sie eine interne Anfrage-Warteschlange verwalten. Die request-Funktion entfernt einfach neue Anfragen aus der I/O-Anfrage-Warteschlange und fügt sie zur internen Warteschlange hinzu. Letztere wird dann durch eine Kombination aus Tasklets und Interrupt-Handlern abgearbeitet.

Die Funktionsweise der Funktionen und Makros in blk.h

In unser zuvor gezeigten einfachen request-Funktion haben wir uns nicht um buffer_head-Strukturen oder verkettete Listen gekümmert. Die Makros und Funktionen in <linux/blk.h> verstecken die Struktur der I/O-Anfrage-Warteschlange, um das Schreiben von Block-Treibern zu vereinfachen. In vielen Fällen braucht man aber ein tieferes Verständnis der Funktionsweise der Warteschlange, um leistungsstarke Treiber zu bekommen. In diesem Abschnitt schauen wir uns die Schritte zur Manipulation der Anfrage-Warteschlange an; die folgenden Abschnitte führen dann fortgeschrittene Techniken zum Schreiben von Block-request-Funktionen vor.

Die Felder in der request-Struktur, die wir uns bisher angeschaut haben — sector, current_nr_sectors und buffer — sind in Wirklichkeit nur Kopien der entsprechenden Informationen, die in der ersten buffer_head-Struktur der Liste gespeichert sind. Eine request-Funktion, die diese Informationen vom CURRENT-Zeiger verwendet, verarbeitet daher nur den ersten von möglicherweise vielen Puffern in der Anfrage. Die Aufgabe, eine Multi-Puffer-Anfrage in mehrere scheinbar unabhängige Einzel-Puffer-Anfragen aufzuteilen, wird durch zwei wichtige Definitionen in <linux/blk.h> erledigt: das Makro INIT_REQUEST und die Funktion end_request.

INIT_REQUEST ist die einfachere der beiden; hier werden lediglich ein paar Konsistenzüberprüfungen auf der Anfrage-Warteschlange vorgenommen und es wird aus der request-Funktion zurückgesprungen, wenn die Warteschlange noch leer ist. Dieses Makro stellt einfach nur sicher, daß noch Arbeit ansteht.

Der Großteil der Warteschlangen-Verarbeitung geschieht in end_request. Wir haben bereits gesagt, daß diese Funktion immer dann aufgerufen wird, wenn der Treiber eine einzelne "Anfrage" (genauer gesagt einen Puffer) verarbeitet hat. Sie hat mehrere Aufgaben:

  1. Die I/O-Verarbeitung des aktuellen Puffers abschließen; dazu gehört das Aufrufen der Funktion b_end_io mit dem Status der Operation, was alle Prozesse aufweckt, die eventuell auf dem Puffer schlafen.

  2. Den Puffer aus der verketteten Liste der Anfrage entfernen. Wenn noch weitere Puffer zu verarbeiten sind, werden die Felder sector, current_nr_sectors und buffer in der Anfrage-Struktur aktualisiert, um den Inhalt der nächsten buffer_head-Struktur in der Liste wiederzugeben. In diesem Fall (es sind noch weitere Puffer zu übertragen) ist end_request für diesen Durchgang beendet, und die Schritte 3 bis 5 werden nicht ausgeführt.

  3. add_blkdev_randomness aufrufen, um den Entropie-Pool zu aktualisieren, sofern nicht DEVICE_NO_RANDOM definiert worden ist (wie das beim sbull-Treiber der Fall ist).

  4. Die beendete Anfrage durch Aufrufen von blkdev_dequeue_request aus der Anfrage-Warteschlange nehmen. Dieser Schritt verändert die Anfrage-Warteschlange und muß daher bei gehaltener io_request_lock-Sperre ausgeführt werden.

  5. Die fertig bearbeitete Anfrage an das System zurückgeben; auch hierfür muß die Sperre io_request_lock gehalten werden.

Der Kernel definiert eine Reihe von Hilfsfunktionen, die von end_request verwendet werden und den Großteil der Arbeit erledigen. Die erste heißt end_that_request_first und erledigt die ersten beiden der gerade beschriebenen Schritte. Ihr Prototyp lautet:


int end_that_request_first(struct request *req, int status, char *name);

status ist der Status der Anfrage, der an end_request übergeben wurde; der Parameter name ist der Gerätename, der für die Ausgabe von Fehlermeldungen verwendet wird. Der Rückgabewert ist von Null verschieden, wenn in der aktuellen Anfrage noch Puffer zu verarbeiten sind; in diesem Fall ist die Arbeit beendet. Falls nicht, wird die Anfrage mit end_that_request_last aus der Warteschlange entfernt und freigegeben:


void end_that_request_last(struct request *req);

In end_request wird dieser Schritt mit folgendem Code erledigt:


struct request *req = CURRENT;
blkdev_dequeue_request(req);
end_that_request_last(req);

Mehr gibt es zu diesem Thema nicht zu sagen.

Cluster-Anfragen

Es ist jetzt an der Zeit, all dieses Hintergrundwissen anzuwenden, um bessere Block-Treiber zu schreiben. Wir schauen uns als erstes an, wie man mit Cluster-Anfragen umgeht. Clustering ist, wie bereits erwähnt wurde, einfach die Praxis, Anfragen, die auf benachbarten Blocks auf der Festplatte operieren, zusammenzufassen. Dies hat zwei Vorteile: Zunächst einmal wird die Übertragung beschleunigt; es kann aber durch Vermeiden von redundanten request-Strukturen auch Speicher im Kernel gespart werden.

Wie Sie bereits gesehen haben müssen sich Block-Treiber gar keine Gedanken um das Clustering machen. <linux/blk.h> teilt alle Cluster-Anfragen transparent in ihre Bestandteile auf. In vielen Fällen kann ein Treiber aber eine bessere Performance erreichen, indem er sich explizit um Cluster kümmert. Es ist oft möglich, die I/O-Operationen für mehrere zusammenhängende Blocks gleichzeitig einzurichten, um den Durchsatz zu verbessern. Beispielsweise versucht der Linux-Floppy-Treiber immer, eine vollständige Spur auf einmal auf die Diskette zu schreiben. Die meisten High-Performance-Festplatten-Controller können solche "Scatter/Gather"-I/O ebenfalls durchführen, was große Performance-Verbesserungen mit sich bringt.

Um das Clustering auszunutzen, müssen Block-Treiber die Liste der buffer_head-Strukturen einer Anfrage direkt anschauen. Auf diese Liste verweist CURRENT->bh; die folgenden Puffer stehen dann in den b_reqnext-Zeigern in den einzelnen buffer_head-Strukturen. Ein Treiber, der Cluster-I/O verwendet, sollte bei jedem Puffer etwa folgendermaßen vorgehen:

  1. Die Übertragung des Datenblocks an der Adresse bh->b_data mit der Größe von bh->b_size Bytes einrichten. Die Richtung der Datenübertragung wird durch CURRENT->cmd vorgegeben (entweder READ oder WRITE).

  2. Den nächsten Puffer-Kopf aus der Liste holen: bh->b_reqnext. Dann den gerade übertragenen Puffer aus der Liste entfernen, indem das Feld b_reqnext auf Null gesetzt wird, also den Zeiger auf den gerade geholten neuen Puffer.

  3. Die request-Struktur aktualisieren, um die mit dem gerade entfernten Puffer durchgeführte I/O widerzuspiegeln. Sowohl CURRENT->hard_nr_sectors als auch CURRENT->nr_sectors sollten um die Anzahl der aus dem Puffer übertragenen Sektoren (nicht Blocks) dekrementiert werden. Die Sektoren-Nummern CURRENT->hard_sector und CURRENT->sector sollten um den gleichen Betrag inkrementiert werden. Durch diese Strukturen bleibt die request-Struktur konsistent.

  4. Zurück an den Anfang springen, um die Übertragung des nächsten benachbarten Blocks einzuleiten.

Wenn die I/O-Operation auf einem Puffer vollständig abgearbeitet ist, sollte der Treiber den Kernel durch Aufruf der I/O-Vervollständigungsroutine des Puffers informieren:


bh->b_end_io(bh, status);

status ist von Null verschieden, wenn die Operation erfolgreich war. Sie müssen natürlich auch die request-Struktur vollständig abgearbeiteter Operationen aus der Warteschlange entfernen. Die gerade beschriebenen Verarbeitungsschritte können ohne Besitz der Sperre io_request_lock durchgeführt werden, aber um die Warteschlange selbst zu verändern, muß man die Sperre halten.

Ihr Treiber kann beim Beenden der I/O-Operation weiterhin end_request verwenden (anstatt die Warteschlange direkt zu manipulieren), sofern er den Zeiger CURRENT->bh korrekt setzt. Dieser Zeiger sollte entweder NULL sein oder auf die letzte übertragene buffer_head-Struktur verweisen. Im letzteren Fall sollte die Funktion b_end_io auf diesem letzten Puffer nicht aufgerufen worden sein, weil end_request das selbst macht.

Eine vollständige Cluster-Implementation können Sie in drivers/block/floppy.c sehen, eine Zusammenfassung der in end_request benötigten Operationen in blk.h. Weder floppy.c noch blk.h sind einfach zu verstehen, aber blk.h ist der bessere Ausgangspunkt.

Der aktive Warteschlangenkopf

Ein weiteres Detail hinsichtlich des Verhaltens der I/O-Anfrage-Warteschlange ist für Block-Treiber, die mit Clustering arbeiten, wichtig. Dies hängt mit dem Kopf der Warteschlange zusammen, also der ersten Anfrage in der Warteschlange. Aus historischen Kompatibilitätsgründen geht der Kernel (fast) immer davon aus, daß ein Block-Treiber den ersten Eintrag in der Anfrage-Warteschlange verarbeitet. Um Schäden durch sich widersprechende Aktivitäten zu vermeiden, wird der Kernel eine Anfrage, die an den Kopf der Schlange geraten ist, nie verändern. Mit dieser Anfrage erfolgt kein weiteres Clustering, und der Fahrstuhl-Code wird keine weiteren Anfragen davor stellen.

Viele Block-Treiber entfernen Anfragen vollständig aus der Warteschlange, bevor sie die Anfragen bearbeiten. Wenn Ihr Treiber auch so arbeitet, sollte die Anfrage am Kopf der Warteschlange Freiwild für den Kernel sein. In diesem Fall sollte Ihr Treiber den Kernel darüber informieren, daß der Kopf der Warteschlange nicht aktiv ist, indem er blk_queue_headactive aufruft:


blk_queue_headactive(request_queue_t *queue, int active);

Wenn active 0 ist, darf der Kernel Änderungen am Kopf der Anfrage-Warteschlange vornehmen.

Block-Treiber mit mehreren Warteschlangen

Wie wir bereits gesehen haben, verwaltet der Kernel default-mäßig eine einzige I/O-Anfrage-Warteschlange je Major-Nummer. Dies funktioniert gut für Geräte wie sbull, ist aber in real existierenden Situationen nicht immer optimal.

Stellen Sie sich einen Treiber vor, der es mit echten Festplatten zu tun hat. Jede Festplatte kann unabhängig von den anderen arbeiten, und die Performance des Systems ist sicherlich besser, wenn die Festplatten parallel laufen. Ein einfacher Treiber mit einer einzigen Warteschlange kann das nicht erreichen, er führt immer nur Operationen auf jeweils einem Gerät aus.

Es wäre nicht besonders schwer für einen Treiber, die Anfrage-Warteschlange durchzusehen und Anfragen nach unabhängigen Festplatten zu suchen. Aber der 2.4-Kernel macht das Leben noch einfacher, indem er es dem Treiber ermöglicht, mehrere unabhängige Warteschlangen für jedes Gerät einzurichten. Die meisten High-Performance-Treiber machen davon Gebrauch. Das ist auch nicht schwierig, allerdings muß man sich schon von den einfachen Definitionen in <linux/blk.h> wegbewegen.

Der sbull-Treiber arbeitet mit mehreren Warteschlangen, wenn das Symbol SBULL_MULTIQUEUE beim Kompilieren definiert wird. Dies funktioniert ohne die Makros in <linux/blk.h> und führt eine Reihe von Features vor, die wir in diesem Abschnitt beschrieben haben.

Um mit mehreren Warteschlangen zu arbeiten, muß ein Block-Treiber eigene Anfrage-Warteschlangen definieren. sbull macht dies, indem er ein queue-Felds zur Struktur Sbull_Dev hinzufügt:


request_queue_t queue;
int busy;

Das Flag busy wird dazu verwendet, die Funktion request vor Reentranz zu schützen; wir schauen uns das noch an.

Anfrage-Warteschlangen müssen natürlich initialisiert werden. sbull macht das folgendermaßen:


for (i = 0; i < sbull_devs; i++) {
    blk_init_queue(&sbull_devices[i].queue, sbull_request);
    blk_queue_headactive(&sbull_devices[i].queue, 0);
}
blk_dev[major].queue = sbull_find_queue;

Der Aufruf von blk_init_queue sieht aus wie zuvor, allerdings übergeben wir jetzt die gerätespezifischen Warteschlangen anstelle der Default-Warteschlange für unsere Major-Nummer. Dieser Code gibt auch an, daß die Warteschlangen inaktive Köpfe haben.

Sie fragen sich vielleicht, wie der Kernel die Anfrage-Warteschlangen finden kann, die tief in einer gerätespezifischen, privaten Struktur verborgen sind. Das zentrale Element dazu ist die letzte gerade gezeigte Linie, die das Feld queue in der globalen Struktur blk_dev setzt. Dieses Feld zeigt auf eine Funktion, deren Aufgabe es ist, die passende Anfrage-Warteschlange für eine bestimmte Gerätenummer zu finden. Geräte, die die Default-Warteschlange verwenden, haben so eine Funktion nicht, aber Geräte mit mehreren Warteschlangen müssen sie implementieren. Die entsprechende Funktion in sbull sieht folgendermaßen aus:


request_queue_t *sbull_find_queue(kdev_t device)
{
    int devno = DEVICE_NR(device);

    if (devno >= sbull_devs) {
        static int count = 0;
        if (count++ < 5) /* Meldung hoechstens fuenfmal ausgeben */
            printk(KERN_WARNING "sbull: request for unknown device\n");
        return NULL;
    }
    return &sbull_devices[devno].queue;
}

Wie die Funktion request muß auch sbull_find_queue atomar sein (darf also nicht schlafen gehen).

Jede Warteschlange hat ihre eigene request-Funktion, obwohl Treiber normalerweise die gleiche Funktion für alle Warteschlangen verwenden. Der Kernel übergibt die jeweilige Anfrage-Warteschlange als Parameter an die request-Funktion, weswegen die Funktion immer herausfinden kann, um welches Gerät es gerade geht. Die request-Funktion für mehrere Warteschlangen in sbull unterscheidet sich etwas von den Funktionen, die wir bisher gesehen haben, weil sie die Anfrage-Warteschlange direkt manipuliert. Sie gibt außerdem die Sperre io_request_lock frei, während sie Übertragungen durchführt, um dem Kernel die Ausführung anderer Block-Operationen zu ermöglichen. Schließlich muß der Code zwei weitere Gefahren umschiffen: mehrfache Aufrufe der request-Funktion und Konflikte beim Zugriff auf das Gerät selbst.


void sbull_request(request_queue_t *q)
{
    Sbull_Dev *device;
    struct request *req;
    int status;

    /* Unser Geraet finden */
    device = sbull_locate_device (blkdev_entry_next_request(&q->queue_head));
    if (device->busy) /* keine Race Condition - wir halten io_request_lock */
        return;
    device->busy = 1;

    /* Anfragen in der Warteschlange verarbeiten */
    while(! list_empty(&q->queue_head)) {

    /* Die naechste Anfrage aus der Liste holen. */
        req = blkdev_entry_next_request(&q->queue_head);
        blkdev_dequeue_request(req);
        spin_unlock_irq (&io_request_lock);
        spin_lock(&device->lock);

    /* Alle Puffer in dieser (moeglicherweise Cluster-) Anfrage verarbeiten. */
        do {
            status = sbull_transfer(device, req);
        } while (end_that_request_first(req, status, DEVICE_NAME));
        spin_unlock(&device->lock);
        spin_lock_irq (&io_request_lock);
        end_that_request_last(req);
    }
    device->busy = 0;
}

Anstatt INIT_REQUEST zu verwenden, testet diese Funktion ihre jeweilige Anfrage-Warteschlange mit list_empty. Solange noch Anfragen vorliegen, entfernt sie diese eine nach der anderen mit blkdev_dequeue_request aus der Warteschlange. Erst dann, wenn das Entfernen abgeschlossen ist, darf die Sperre io_request_lock freigegeben werden und die gerätespezifische Sperre erworben werden. Die eigentliche Übertragung geschieht mit der Funktion sbull_transfer, die wir bereits gesehen haben.

Jeder Aufruf von sbull_transfer arbeitet genau eine buffer_head-Struktur ab, die zur Anfrage gehört. Die Funktion ruft dann end_that_request_first auf, um den Puffer loszuwerden, und macht mit end_that_request_last weiter (sofern die Anfrage vollständig abgearbeitet wurde), um die Anfrage insgesamt aufzuräumen.

Es lohnt sich, noch einen Blick auf die Verwaltung der Nebenläufigkeit zu werfen. Das Flag busy verhindert mehrfache Aufrufe von sbull_request. Weil sbull_request immer mit gehaltener io_request_lock-Sperre aufgerufen wird, kann man das Flag busy ohne zusätzlichen Schutz abfragen und verändern. (Ansonsten hätte man einen atomic_t benutzen können.) Die io_request_lock -Sperre wird freigegeben, bevor die gerätespezifische Sperre geholt wird. Man kann mehrere Sperren halten, ohne ein Deadlock zu riskieren, aber das ist schwieriger. Wenn die Umgebungsbedingungen es erlauben, ist es besser, eine Sperre freizugeben, bevor man die nächste holt.

end_that_request_first wird ohne die Sperre io_request_lock aufgerufen. Weil diese Funktion nur auf der angegebenen Anfrage-Struktur arbeitet, ist das gefahrlos möglich — solange sich die Anfrage nicht in der Warteschlange befindet. Um end_that_request_last aufzurufen, muß man aber die Sperre haben, weil die Anfrage an die Liste freier Einträge der Anfrage-Warteschlange zurückgegeben wird. Die Funktion springt außerdem immer mit gehaltener io_request_lock-Sperre und freigegebener Gerätesperre aus der äußeren Schleife (und der Funktion selbst) zurück.

Treiber mit mehreren Warteschlangen müssen natürlich beim Entfernen des Moduls alle Warteschlangen hinter sich aufräumen:


for (i = 0; i < sbull_devs; i++)
        blk_cleanup_queue(&sbull_devices[i].queue);
blk_dev[major].queue = NULL;

Man sollte hier noch kurz erwähnen, daß dieser Code effizienter sein könnte. Er alloziert in der Initialisierung einen ganzen Satz von Anfrage-Warteschlangen, obwohl manche davon möglicherweise nie verwendet werden. Eine Anfrage-Warteschlange ist eine große Struktur, weil viele (vielleicht Tausende) von request-Strukturen alloziert werden, wenn die Warteschlange initialisiert wird. Eine intelligentere Implementation würde die Anfrage-Warteschlange bei Bedarf entweder in der open-Methode oder in der queue-Funktion allozieren. Wir haben uns bei sbull für die einfachere Implementation entschieden, um den Code nicht zu verkomplizieren.

Damit haben wir die Funktionsweise von Treibern mit mehreren Warteschlangen abgehandelt. Treiber, die es mit richtiger Hardware zu tun haben, haben natürlich auch noch andere Probleme, wie etwa das Serialisieren des Zugriffs auf den Controller. Aber die grundlegende Struktur von Treibern mit mehreren Warteschlangen haben Sie hier gesehen.

Ohne die Anfrage-Warteschlange arbeiten

Diese darstellung hat sich bisher zum größten Teil mit der Manipulation der I/O-Anfrage-Warteschlange beschäftigt. Die Aufgabe der Anfrage-Warteschlange ist die Performance-Verbesserung, indem sie dem Treiber asynchrones Arbeiten ermöglicht und — vor allem — auf der Festplatte zusammenhängende Operationen zusammenfaßt. Bei normalen Festplatten sind solche Operationen auf zusammenhängenden Blocks gang und gäbe, was diese Optimierung notwendig macht.

Nicht alle Block-Geräte ziehen aber einen Vorteil aus der Anfrage-Warteschlange. sbull beispielsweise verarbeitet Anfragen synchron und hat keine Probleme mit Suchzeiten. Für sbull wird die Verarbeitung durch die Anfrage-Warteschlange nur langsamer. Auch andere Typen von Block-Geräten sind ohne Anfrage-Warteschlange besser bedient. Dazu gehören beispielsweise RAID-Geräte, die aus mehreren Festplatten bestehen und “zusammenhängende” Blocks oft über mehrere physikalische Geräte verteilen. Block-Geräte, die vom Logical Volume Manager (LVM, ab Kernel 2.4) implementiert werden, haben ebenfalls eine komplexere Implementation als die Block-Schnittstelle, die der Rest des Kernels zu sehen bekommt.

Im 2.4-Kernel werden Block-I/O-Anfragen von der Funktion _ _make_request in die Warteschlange eingestellt. Diese Funktion ist auch für den Aufruf der request-Funktion des Treibers verantwortlich. Block-Treiber, die eine genauere Kontrolle über das Einstellen von Anfragen benötigen, können eine eigene “make request”-Funktion implementieren. Die RAID- und LVM-Treiber machen das beispielsweise so; ihre Variante leitet jede I/O-Anfrage (mit unterschiedlichen Block-Nummern) an das oder die passenden Geräte weiter, aus denen sich das Gesamtgerät zusammensetzt. Ein RAM-Disk-Treiber kann dagegen die I/O-Operation direkt ausführen.

Wenn sbull auf 2.4-Systemen mit der Option noqueue=1 gestartet wird, stellt der Treiber eine eigene “make request”-Funktion bereit und arbeitet ohne Anfrage-Warteschlange. Als ersten Schritt dazu wird _ _make_request entfernt. Der “make request”-Funktionszeiger wird in der Anfrage-Warteschlange gespeichert und kann mit blk_queue_make_request geändert werden:


void blk_queue_make_request(request_queue_t *queue,
make_request_fn *func);

Der Typ make_request_fn ist wiederum folgendermaßen definiert:


typedef int (make_request_fn) (request_queue_t *q, int rw,
             struct buffer_head *bh);

Die Funktion “make request” muß die Übertragung des angegebenen Blocks organisieren und dafür sorgen, daß die Funktion b_end_io aufgerufen wird, wenn die Übertragung abgeschlossen ist. Der Kernel hält die Sperre io_request_lock nicht, wenn die make_request_fn-Funktion aufgerufen wird; die Funktion muß sich also die Sperre selbst holen, wenn sie vorhat, die Anfrage-Warteschlange zu manipulieren. Wenn die Übertragung eingeleitet worden ist, (sie muß aber nicht unbedingt abgeschlossen worden sein), sollte die Funktion 0 zurückgeben.

Der Ausdruck “die Übertragung organisieren” ist sorgfältig gewählt; oft überträgt eine treiberspezifische “make request”-Funktion die Daten gar nicht. Denken Sie etwa an ein RAID-Gerät. Die Funktion muß die I/O-Operation auf eines der Untergeräte abbilden und dann den Treiber dieses Geräts aufrufen, der dann die Arbeit tut. Diese Abbildung erfolgt dadurch, daß das Feld b_rdev in der buffer_head-Struktur auf die Nummer des "echten" Geräts gesetzt wird, das die Übertragung vornimmt. Dann wird angezeigt, daß der Block noch geschrieben werden muß, indem ein von Null verschiedener Wert zurückgegeben wird.

Wenn der Kernel einen von Null verschiedenen Rückgabewert der “make request”-Funktion sieht, schließt er daraus, daß die Aufgabe nicht ausgeführt wurde, und probiert es noch einmal. Zunächst aber schlägt er die “make request”-Funktion des Geräts im b_rdev-Feld nach. Im Falle von RAID-Geräten wird also die ”make request”-Funktion des RAID-Treibers nicht noch einmal aufgerufen, sondern der Kernel gibt den Block an die passende Funktion des zugrundeliegenden Geräts weiter.

sbull richtet seine “make request”-Funktion bei der Initialisierung folgendermaßen ein:


if (noqueue)
    blk_queue_make_request(BLK_DEFAULT_QUEUE(major), sbull_make_request);

In diesem Modus wird blk_init_queue nicht aufgerufen, weil die Anfrage-Warteschlange nicht verwendet wird.

Wenn der Kernel eine Anfrage nach einem sbull-Gerät erzeugt, ruft er die Funktion sbull_make_request auf, die folgendermaßen definiert ist:


int sbull_make_request(request_queue_t *queue, int rw,
                       struct buffer_head *bh)
{
    u8 *ptr;

    /* Herausfinden, was wir tun sollen */
    Sbull_Dev *device = sbull_devices + MINOR(bh->b_rdev);
    ptr = device->data + bh->b_rsector * sbull_hardsect;

    /* Paranoide Kontrolle; so etwas kann wirklich passieren */
    if (ptr + bh->b_size > device->data + sbull_blksize*sbull_size) {
        static int count = 0;
        if (count++ < 5)
            printk(KERN_WARNING "sbull: request past end of device\n");
        bh->b_end_io(bh, 0);
        return 0;
    }

    /* Dies koennte ein Puffer im hohen Speicher sein, herunterholen */
#if CONFIG_HIGHMEM
    bh = create_bounce(rw, bh);
#endif

    /* Die Uebertragung durchfuehren */
    switch(rw) {
    case READ:
    case READA:  /* Vorauslesen */
        memcpy(bh->b_data, ptr, bh->b_size); /* von sbull in den Puffer */
        bh->b_end_io(bh, 1);
        break;
    case WRITE:
        refile_buffer(bh);
        memcpy(ptr, bh->b_data, bh->b_size); /* vom Puffer nach sbull */
        mark_buffer_uptodate(bh, 1);
        bh->b_end_io(bh, 1);
        break;
    default:
        /* kann nicht passieren */
        bh->b_end_io(bh, 0);
        break;
    }

    /* 0 heißt fertig */
    return 0;
}

Dieser Code sollte größtenteils bekannt aussehen. Er enthält die üblichen Berechnungen, um zu bestimmen, wo sich der Block im sbull-Gerät befindet, und verwendet memcpy, um die Operation durchzuführen. Weil die Operation unmittelbar abgeschlossen ist, kann bh->b_end_io aufgerufen werden, um den Abschluß der Operation anzuzeigen. An den Kernel wird 0 zurückgegeben.

Es gibt aber noch ein Detail, um das sich die “make request”-Funktion kümmern muß. Der Puffer, der übertragen werden muß, könnte sich im hohen Speicher befinden, auf den der Kernel nicht direkt zugreifen kann. Hoher Speicher wird detailliert in Kapitel 13 behandelt. Wir wollen das dort Gesagte hier nicht wiederholen; es reicht hier zu sagen, daß eine mögliche Problemlösung darin besteht, einen Puffer im hohen Speicher durch einen im erreichbaren Speicher zu ersetzen. Die Funktion create_bounce erledigt das auf für den Treiber transparente Weise. Der Kernel verwendet create_bounce normalerweise, bevor er Puffer in die Anfrage-Warteschlange des Treibers stellt, aber wenn der Treiber eine eigene make_request_fn-Funktion implementiert, muß er auch diese Aufgabe selbst erledigen.

Fußnoten

[1]

Der RAM-Disk-Treiber läßt seinen Speicher beispielsweise so aussehen, als befände dieser sich im Buffer-Cache. Weil sich der “Festplatten”-Puffer bereits im System-RAM befindet, es es sinnlos, noch eine Kopie im Buffer-Cache zu halten. Unser Beispiel-Code ist daher deutlich weniger effizient als eine korrekt implementierte RAM-Disk und kümmert sich nicht um RAM-Disk-spezifische Performance-Fragen.