Das VFS

VFS = Virtual Filesystem Switch

Ziel: einheitliche Schnittstelle für unterschiedliche Dateisystem-Typen

Der DCache und der Inode-Cache Ausgangssituation

Um die Anzahl der Zugriffe auf die Festplatte beim Lesen und Schreiben der Inodes möglichst niedrig zuhalten, werden diese beiden Caches verwendet. Es handelt sich dabei um nichts anderes als zwei interne Zwischenspeicher, in dem sich die Daten von häufig gebrauchten Inodes bzw. Verzeichnissen befinden. Wenn das VFS auf eine solche Struktur zugreift, prüft es zuerst, ob sich die gewünschten Daten in den Caches befinden. War die Prüfung erfolgreich, können diese Daten verwendet werden, ohne dass irgendwelche anderen (zeitaufwendigen) Routinen zu ihrer Beschaffung aufgewendet werden müssen.

Speichermodul

Kernel-Space

User-Space

Dateien

(Disk-Inode)

struct inode

à Inode-cache

struct stat

Dateinamen / Verzeichnisse

[fs-spezifische Datei mit name, inode-no P...?]

---

struct dirent

ê Der Begriff „inode“ hat zwei Bedeutungen:

Struktur auf dem Speichermedium
Struktur im Kernel-Space

Ursprünglich waren beide Bedeutungen gleich (binäres Abbild der Kernelstruktur auf der Platte)

>> !! Geht nicht mit den verschiedenen Dateisystem-Typen !! <<

à Übersetzung notwendig (à VFS)

Die Struktur Inode enthält im wesentlichen Informationen über die Datei. Zusätzlich befinden sich in dieser Struktur Verwaltungsinformationen sowie die dateisystemabhängige Union u.

struct inode{

/* Verwaltungs-infos */

unsigned long i_ino; /* Inode-Nummer */
unsigned int i_count; /* Referenzzähler */

kdev_t i_dev; /* Gerätenummer */

int i_nlink; /* Hardlinks */

mode_t i_mode; /* Typ der Inode */

uid_t i_uid: /* Eigentümer */

... ... (siehe Seite )

struct semaphore i_sem;

struct inode_operations* i_op;

struct super_block* i_sb;

...

union {

struct pipe_inode_info pipe_i;

struct minix_inode_info minix_i;

} u;

Generische Inodeoperationen

struct inode* get_empty_inode (void);

liefert eine “freie” Inode.

Für den schnellen Zugriff auf Inodes sind die Inodes zusätzlich in einer offenen Hashtabelle hash_table[] untergebracht.

void insert_inode_hash (struct inode* inode);

void remove_inode_hash (struct inode* inode);

void clear_inode (struct inode* inode);

struct inode* iget (struct superblock* sb,

unsigned long ino);

Liefert die durch den Superblock sb und die Inode-Nummer ino angegebene Inode. Kann die Inode in der Hashtabelle gefunden werden, wird der Referenzzähler i_count erhöht.

void iput (struct inode* inode);

Eine mit iget() erhaltene Inode muss mit der Funktion iput() wieder „freigegeben“ werden. Diese verringert den Referenzzähler um 1 und markiert die Inode-Struktur als „frei“, wenn dieser 0 ist.

Inodes können von mehreren konkurrierenden Prozessen verwendet werden à

ê Race-Conditions

à Referenzzähler-Methode
i_count = 0: Inode nicht in Verwendung, darf aus Kernelspace entfernt werden

i_count > 0: Es gibt i_count Referenzen (Pointer), Inode darf nicht zerstört werden.

Funktionsweise eines Caches:

Wenn Element benötigt wird ((iget()), wird es über den Primärindex (hier (dev, inoNr)-Paar) gesucht (z.B. über Hashtabelle)
à weiterer iget() sieht zwar zuerst in Hashtabelle nach, falls gefunden, wird i_count erhöht und der Inode-Pointer zurückgeliefert.
Wenn Element nicht mehr benötigt wird iput() ausgeführt. Führt dies zu i_count = 0, wird eine LRU-Liste der inaktiven Elemente verwaltet.

ê Gesamtzahl der im Kernel-Memory gehaltenen Elemente ist begrenzt.

à letztes Element der LRU-Liste wird bei Bedarf wiederverwendet.

Was passiert allerdings, wenn sich eine Inode (noch) nicht in der Hashtabelle befindet? In diesem Fall muss eine VFS-Inode im Speicher mit den Werten der Inode aus dem untergeordneten Dateisystem belegt werden. Wie wird aber die VFS-Inode ermittelt, die mit den Daten belegt werden soll? Die Zahl der hashbaren Inodes ist kernelseitig begrenzt (und zwar durch die Konstante NR_IHASH, die üblicherweise auf 512 eingestellt ist). Wenn die Zahl noch nicht ausgeschöpft ist, ist die Situation einfach: Das Dateisystem braucht nur den benötigten Speicher zu reservieren und kann diesen zur Aufnahme von Inodes verwenden. Komplizierter wird das Ganze, wenn die Grenze bereits erreicht ist, da das Dateisystem in diesem Fall eine Inode aus dem Cache entfernen und dafür eine neue integrieren muss. Um zu entscheiden, welche Inodes entfernt werden soll, orientiert sich Linux daran, wie wichtig die Inode im Moment für das System ist. Mit Hilfe der Variablen i_count, kann festgestellt werden, von wie vielen Prozessen die Inode im Moment verwendet wird. Wenn dieser Zähler gleich 0 ist, wird die Inode nicht mehr gebraucht und kann daher aus dem Cache entfernt werden, um den benötigten Platz zu schaffen. Dieser Mechanismus ermöglicht es übrigens auch, sicherzustellen, dass die für das System wichtigen Inodes nie aus dem Cache entfernt werden, indem ihr i_count immer größer 0 gehalten wird.

Problem bei bisherigen Implementierungen der Namesauflösung:

Zugriff auf dirents findet nicht-zentral sowohl in readdir() als auch in lookup() statt.
lookup() =
a) Directory scannen, ob (name, ino)-Paar vorhanden

b) iget(ino) aufrufen
à Inode-Pointer rurück liefern

lookup() durchsucht jedes Mal das gesamte Directory (wird sehr oft im Kernel aufgerufen)

à „alter Dcache“ war eine ad hoc – Methode für Problem 2) Hashtabelle mit (pfad, inode-Pointer)

Neuer DCache

	Speichermedium	Kernel-Space	User-Space
Datei-Inhalte	[disk-inode]	struct inode	struct stat
Datei-Namen	fs-spezifisches Format	struct dentry	struct dirent

struct dentry {

int d_count; /* Referenzzähler */

struct inode* d_inode;

struct dentry* d_parent; à Vater wird „gehalten“

char* d_name;

list_link d_subdirs; /* Anker */

list_link d_child; /* Mitglieder */

list_link d_hash; /* zum schnellen Finden durch Namen */

[...]

[Flags und andere Dinge]

};

Der DCache arbeitet teilweise nach dem gleichen Prinzip wie der Inode-Cache, ist allerdings etwas komplizierter aufgebaut. Basis das Caches ist ebenfalls eine Hashing-Funktion. Die Werte der Tabelle sind wiederum Zeiger auf Listen mit Verzeichnisnamen (und den entsprechenden Inodes). Allerdings kann als Schlüssel für den Hash nicht nur wie beim InodeCache eine Kombination aus Inode-Nummer und untergeordnetem Gerät verwendet werden, sondern zusätzlich auch der Name des Verzeichnisses.

Weiter verfeinert wird die Caching-Technik durch Verwendung zweier LRU-Listen (Least Recently Used). Wenn ein Verzeichnis von einem Programm verwendet wird, setzt Linux dessen Namen, zusammen mit der Nummer der assoziierten Inode, in die Hashtabelle und damit in den Cache. Zusätzlich allerdings wird die gecachte Datenstruktur noch in die erste LRU-Liste aufgenommen und zwar genau an das Ende der Liste; das bisher letzte Element wird vorletztes Element und das bisher erste Element fällt vorne aus der Liste.

Wenn nun nochmals auf das Verzeichnis zugegriffen wird, wird der Eintrag ans Ende der zweiten LRU-Liste verschoben. Weitere Zugriffe auf das Verzeichnis bewirken jeweils, dass der Cache-Eintrag wieder ans Ende der zweiten LRU-Liste gesetzt wird.

Wird lange nicht mehr auf ein Verzeichnis zugegriffen, verschiebt sich der Eintrag immer weiter ans vordere Ende der LRU-Liste, bis er schließlich aus der Liste fällt.

Die maximale Zahl der Verzeichniseinträge in eine LRU beträgt defaultmäßig 128 (festgelegt durch DCACHE_SIZE), was eine Gesamtgröße von 256 Einträgen ergibt.

Ebenfalls interessant ist, dass nur Verzeichnisnamen bis zu einer maximalen Länge von 15 Zeichen (DCACHE_NAME_LEN) in die Hashtabelle aufgenommen werden. Da nur weinige Verzeichniseinträge diese Länge überschreiten, kann diese Beschränkung sowohl Speicherplatz als auch Rechenzeit sparen.

Generische Dentry-Operationen

struct dentry* d_alloc ( struct dentry* parent,

const struct qstr* name);

wobei

struct qstr{

char* name;

int len;

}

int d_invalidate (struct dentry* entry);

struct dentry* dget (struct dentry* entry);

void dput (struct dentry* entry);

void d_add (struct dentry* entry,

struct inode* inode);

ê Falls d_inode == NULL à “negatives dentry” è Name hat kein zugehöriges Inode!

void d_move (struct dentry* entry,

struct dentry* newdentry);

(kopiert Inhalt hinüber)

struct dentry* d_loockup (struct dentry* dir,

struct qstr* name);

void d_delete (struct dentry* entry);

Der Buffer-Cache

Der Buffer Cache hat mit den eigentlichen Strukturen des Dateisystems keine Verbindung. Vielmehr beschleunigt er das Schrieben/Lesen der vom Dateisystem benötigten „Rohdaten“ auf das untergeordnete Gerät, aus denen dann die für das Dateisystem notwendigen Informationen gewonnen werden.

Obwohl es in einem Linux-System üblicherweise verschiedene blockorientierte Geräte gibt, wird für alle nur ein einziger Cache verwendet, d.h. die Datenstrukturen des Caches gelten universell für alle Blockgeräte. Bei der Initialisierung des Caches werden zuerst Listen mit freien Puffern angelegt, die Daten zur Zwischenspeicherung aufnehmen können. Da sich die Blockgrößen der einzelnen Geräte voneinander unterscheiden, werden 5 verschiedene Listen angelegt, in denen jeweils Blöcke mit 512, 1024, 2048, 4096, 8192 Bytes abgelegt werden können. Alle Dateisystem-Module kommunizieren mit den Gerätetreiber über eine Datenstruktur, die die Bezeichnung buffer_head trägt. Die Liste, in der die freien Puffer verwaltet werden, enthält darum eben solche Strukturen.

Wenn nun ein Block gelesen werden soll, sucht Linux zuerst im eigentlichen Buffer-Cache danach. Der Cache besteht aus einer Hashtabelle, die auf Listen aus Blöcken zeigt, sowie einer LRU-Liste (der Schlüssel für den Hash wird dabei aus der Blocknummer und der hexadezimalen Kennzahl des assoziierten Geräts gebildet). Falls sich der Block im Hash befindet, kann er für die weiteren Operationen verwendet werden, ansonsten wird ein neuer Block aus der Liste der freien Blöcke entfernt, mit den entsprechenden Daten gefüllt und in den Hash integriert.

Neben den eigentlichen Nutzdaten wird unter anderem eine zusätzliche Variable (b_state) gespeichert, die den aktuellen Zustand des Buffers angibt. Sie ist ein Feld aus Bits, in dem verschiedene Werte kombiniert werden können; insgesamt existieren 8 Stück davon, wobei an dieser Stelle allerdings nur einer interessant ist: BH_Dirty. Wenn das entsprechende Bit gesetzt ist, zeigt dies, dass der Inhalt des Buffers verändert wurde und daher nicht mit den Daten auf der Festplatte übereinstimmt. Buffer mit diesem Status müssen von Zeit zu Zeit auf die Festplatte geschrieben werden, damit die Daten dauerhaft gespeichert sind. Dies übernimmt die Kernel-Routine bdflush: Wenn die Zahl der „dreckigen“ (dirty) Puffer einen bestimmten Prozentsart der insgesamt zur Verfügung stehenden Puffer erreicht hat, wird diese Routine aufgerufen und „bereinigt“ die Situation, indem es die wie gezeigt markierten Puffer auf die Festplatte verewigt.

struct buffer_head {

unsigned long b_blocknr; /* Blocknummer */

unsigned long b_size; /* Blockgröße */

kdev_t b_dev; /* Gerät */

unsigned long b_state; /* Pufferstatusbitmap */

unsigned int b_count; /* Anzahl der Benutzer dieses Blocks */

char* b_data; /* Zeiger auf Datenblock */

[…]

};

struct buffer_head* getblk (kdev_t dev,

int block,

int size);

à Versucht, den Puffer im Cache zu finden.

ê Puffer braucht nicht aktuell zu sein!

struct buffer_head* bread (kdev_t dev,

int block,

int size);

Um einen Block zu lesen, ruft eine Systemroutine die Funktion bread() auf. Zuerst wird überprüft, ob für den Block block zum Gerät dev nicht schon ein Blockpuffer vorhanden ist. Wird der Puffer gefunden, und ist das Flag BH_Uptodate gesetzt, wird bread() mit der Rückgabe des Blockpuffers beendet. Ist das Flag nicht gesetzt, muss der Puffer durch lesen des externen Mediums aktualisiert werden und die Routine kann zurückkehren.

void brelse (struct buffer_head* bh);

Mit brelse() (block release) soll der von bread() zurückgegebene Speicherblock, wenn er nicht mehr benötigt wird, freigegeben werden. Modifizierte Puffer werden hierbei asynchron zurückgeschrieben.

void bforget (struct buffer_head* bh);

Zurückschreiben unnötig!

ê Zustandsmodell des Buffer-Caches ist sehr komplex!

Buffer-Cache realisiert ein virtuelles Array von Blöcken (á 512 Bytes)

è In Zukunft Byte-Offsets verwenden!

Der virtuelle Switch

Idee: virtuelle Methoden mittels Pointer auf Funktionen simulieren.

(mehrere in struct* -operationen gesammelt)

ê Stimmt nicht vollständig:

Man kann die Existenz einer Implementierung prüfen (ob pointer == null) è default-operationen ausführen.
Man kann Ponter auf Funktionen einzeln zur Laufzeit auswechseln.
Z.B.: In der Pipe-Implementierung.
Je nach Open-Flags verschiedene Read/Write-Funktioenen eingeführt

è Prinzip der Funktions-Pointer ist echt mächtiger als OOP!

Architektur:

VFS-helper (Auszug)

mit [un] register_filesystemtype (struct file_system_type* ini);

struct file_system_type {

const char* name;

int fs_flags;

struct super_block*(*read_super) (struct super_block* sb,

void* data,

int silent);

};

Über read_super() wird beim Mounten der Superblock gelesen, von dort aus sind Pointer auf root-dentry und super__operations erreichbar.