Inodes und Dentries entschlüsselt: Das virtuelle Filesystem im Kernel lässt Applikationen auf unterschiedlichste Dateisysteme einheitlich zugreifen. Dieser Artikel erklärt die Grundlagen, entschlüsselt Inodes und Dentries und zeigt, wie man ein eigenes Filesystem implementiert.

In Sachen Dateisysteme ist Linux ein echtes Multitalent: Die Anzahl der von Linux unterstützten Filesysteme ist riesig, wie der Befehl »cat /proc/filesystems« auf der Konsole offenbart. Neben den Klassikern wie Ext 3, Reiser, JFS, NTFS oder FAT32 finden sich diverse virtuelle Kollegen. Proc-FS, Sys-FS und UBS-FS sind dabei nur die bekanntesten. Hinzu kommen noch Dateisysteme zur Verschlüsselung oder das “Filesystem in der Datei” (Loop).

Ordnung durch Abstraktion

Eine einheitliche Schnittstelle im Kernel macht diese Vielzahl für Programmierer beherrschbar. Die technische Lösung für eine solche Anforderung lautet Abstraktion. Die Kernelprogrammierer haben das Modell eines universalen Filesystems definiert, auf das sich die unterschiedlichsten Dateisysteme abbilden lassen.

Dieses Modell definiert, dass eine Datei aus Datenblöcken zusammengesetzt ist und eine Dateigröße, einen Besitzer, eine Gruppe und Zugriffsrechte hat (Abbildung 1). Außerdem gibt es unterschiedliche Dateiarten wie normale Dateien, Gerätedateien oder Verzeichnisdateien (Directories). Hinzu kommen noch Daten über die Zeitpunkte des Anlegens, der letzten Modifikation sowie des letzten Zugriffs auf das File.

Alle diesen Informationen stehen im so genannten Inode, der zentralen Datenstruktur jedes Unix-Dateisystems. In diesem Modell ist jedes Directory selbst eine Datei, deren Inhalt den Datei- oder Verzeichnisnamen einem Inode zuordnet (Abbildung 2).

Inodes und Dentries

Wie die Daten auf die einzelnen Blöcke eines Dateisystems verteilt werden oder wo die Inode-Informationen liegen, ist Sache des jeweiligen Filesystems (Abbildung 3). Die Implementierung bildet also das reale Dateisystem auf das VFS ab. Ein Ext-2-Filesystem orientiert sich dabei mit seinen Meta-Informationen sehr am VFS-Modell (genau genommen haben sich die Entwickler am realen FS orientiert). Ein FAT-Filesystem kennt dagegen beispielsweise keine Inodes. Also generiert der Filesystem-Code die Inodes allein auf Basis der vorhandenen Informationen. Spezifische Zugriffsrechte, die das FAT-Filesystem nicht kennt, ersetzt er dabei durch Defaultwerte.

Um auf ein Dateisystem zugreifen zu können, muss zunächst der Inode des Root-Verzeichnisses bekannt sein. Zumindest im Modell ordnet er die Subdirectories und die im Wurzelverzeichnis abgelegten Dateien den jeweils zugehörigen Inodes zu. Eine einzelne derartige Zuordnung zwischen Datei- respektive Verzeichnisname und Inode wird als Dentry (Directory Entry) bezeichnet (Abbildung 4).

Schneller mit Dcache

Erst die Kenntnis des Inode erlaubt den Zugriff auf die Daten der Datei. Die wichtigste Operation des VFS ist daher das Auffinden eines Inode, wenn ein vollständiger Dateiname gegeben ist. Dazu zerlegt es den gegebenen Dateinamen zunächst in seine Bestandteile. Aus »/usr/bin/vim« wird dabei »/«, »usr«, »bin« und »vim«. Im Folgenden sucht das VFS dann für die Pfadkomponente »usr« im Wurzelverzeichnis »/« (dessen Inode ja bekannt ist) nach dem zugehörigen Inode.

Da das VFS-Modell nicht festlegt, wie (und ob überhaupt) die Daten in einer Verzeichnisdatei abgelegt sind, muss jedes Dateisystem die Suchfunktion »lookup()« zur Verfügung stellen. Sie gibt den zur Pfadkomponente gehörigen »dentry« oder einen Fehlercode zurück. Wenn es den Dentry kennt, sucht das Filesystem im Beispielfall die Komponente »bin« im Verzeichnis »usr«. Mit jeder weiteren Pfadkomponente wiederholt es diesen Vorgang, bis es den gesuchten Dentry (und damit den Inode) gefunden hat.

Aus Performancegründen sucht der Kernel nicht mit jeder Pfadkomponente den zugehörigen Inode aufs Neue. Er speichert die Suchanfrage – bestehend aus dem darüber liegenden Inode und der Pfadkomponente – zusammen mit dem Ergebnis (dem zugehörigen Inode) in einem Dentry-Objekt. Die Dentries wiederum speichert er im so genannten Dcache »dentry_cache«.

Abbildung 1: Neben den eigentlichen Daten gehören zu jeder Datei vielfältige Attribute wie Größe, Eigentümer, Gruppe und so weiter.

Bei einer erneuten Anfrage sucht er zuerst im Cache. Erst wenn er hier keinen Dentry findet, beauftragt er den Filesystem-Code mit der Suche. Natürlich lassen sich im Dcache nicht unendlich viele Dentries ablegen. Nach dem Least-Recently-Used-Algorithmus (LRU) ersetzt der Kernel die jeweils ältesten Einträge durch neuere.

Hashes statt Suche

Den für die Suche notwendigen Vergleich zwischen der Pfadangabe im Verzeichnis und der gesuchten Pfadkomponente beschleunigt ein Hash-Algorithmus. Vereinfacht ausgedrückt ersetzt ein solches Verfahren einen teuren Suchalgorithmus durch eine einfache und damit schnelle Berechnung. Dazu trägt der Kernel im Dentry sowohl den realen Namen als auch dessen Länge sowie den zugehörigen Hashwert ein.

Abbildung 2: Inodes und Dentries realisieren die Filesystem-Hierarchie.

Im Detail ist das hier vorgestellte VFS-Modell natürlich etwas komplexer, schließlich unterstützt es auch noch Gerätedateien, Named Pipes und Links. Hardlinks sind dabei sehr einfach zu realisieren. Für sie legt der Kernel einfach einen weiteren Dentry an. Softlinks wiederum sind Pfadnamen, die nicht einem Inode, sondern einem anderen Pfadnamen zugeordnet sind.

Die beschriebenen Grundlagen reichen bereits aus, um praktische Erfahrungen durch die Implementierung eines eigenen virtuellen Filesystems zu sammeln. Der Betriebssystemkern unterstützt den Programmierer bei der Erstellung seines Filesystems nicht nur durch das skizzierte Modell, sondern zusätzlich mit einigen Hilfsfunktionen. Die meisten von ihnen sind in der Bibliothek »libfs.a« (in den Kernelquellen in »/usr/src/linux/fs/libfs.c«) zu finden.

Abbildung 3: Beim Zugriff auf Daten sind mehrere Komponenten des Kernels beteiligt, die schichtartig aufeinander aufbauen. Unten im Kernel befinden sich die Gerätetreiber, ganz oben das VFS.

Das hier vorgeführte Kernelmodul in Listing 1 implementiert ein Filesystem-Objekt, für jedes dann wirklich gemountete Filesystem einen Superblock und für jede Datei ein Inode-Objekt. Zusätzlich braucht das Beispiel die beschriebenen Dentry-Objekte, die Inodes und Dateinamen einander zuordnen.

Ein neues Dateisystem registriert sich beim Betriebssystemkern über »register_filesystem()«. Parameter dieser Funktion ist erwartungsgemäß das Filesystem-Objekt, welches das neue Dateisystem typisiert: Es legt also den Namen (zum Beispiel »ext2«) fest und stellt eine Methode zur Verfügung, mit der der Kernel den Superblock für eine Instanz des Filesystems erhält.

Zeile 109 in Listing 1 ordnet dem zugehörigen Feld ».get_sb« die Funktion »get_superblock()« (Zeile 99) zu. Diese Methode wird typischerweise beim Mounten des Filesystems aufgerufen. Sie bekommt unter anderem den Gerätenamen übergeben, also zum Beispiel »/dev/hda1«. Bei virtuellen Dateisystemen ist der Gerätename nicht relevant, es hat sich daher eingebürgert, beim Mounten dafür das Schlüsselwort »none« zu verwenden.

Die vom Kernel bereitgestellte Funktion »get_sb_single()« reserviert den Speicher für den Superblock und führt die Grundinitialisierung durch. Die Beispielfunktion »fill_superblock()« schließt die Initialisierung ab (Listing 1, Zeile 70).

002 #include <linux/init.h>
003 #include <linux/pagemap.h>
004 #include <linux/fs.h>
005 
006 static ssize_t read_hello_world(struct file *, char *, size_t , loff_t *);
007 
008 static struct super_operations superblock_ops = {
009     .statfs     = simple_statfs,
010     .drop_inode = generic_delete_inode,
011 };
012 
013 static struct file_operations file_ops = {
014     .read = read_hello_world,
015 };
016 
017 static ssize_t read_hello_world(struct file *instanz, char *buf,
018     size_t tocopy, loff_t *offset)
019 {
020     char *text = "hello worldn";
021     int c, len=strlen(text)+1;
022 
023     if( tocopy<len )
024         tocopy=len;
025     if( (c=copy_to_user(buf,text,len))<0 )
026         return -EFAULT;
027     return tocopy-c;
028 }
029 
030 static struct inode *make_new_inode(struct super_block *sb, int mode)
031 {
032     struct inode *ret = new_inode(sb);
033 
034     if (ret) {
035         ret->i_mode = mode;
036         ret->i_uid = ret->i_gid = 0;
037         ret->i_blksize = PAGE_CACHE_SIZE;
038         ret->i_blocks = 0;
039         ret->i_atime = ret->i_mtime = ret->i_ctime = CURRENT_TIME;
040     }
041     return ret;
042 }
043 
044 static struct dentry *create_file(struct super_block *sb,
045     struct dentry *parent, char *name)
046 {
047     struct qstr qname;
048     struct inode *inode;
049     struct dentry *dentry;
050 
051     inode = make_new_inode(sb, S_IFREG | 0644);
052     if( !inode )
053         return 0;
054     inode->i_fop = &file_ops;
055     inode->i_size = 14; // strlen("hello worldn")+1;
056 
057     qname.name = name;
058     qname.len = strlen(name);
059     qname.hash = full_name_hash(name, qname.len);
060 
061     dentry = d_alloc(parent, &qname);
062     if( !dentry ) {
063         iput( inode );
064         return 0;
065     }
066     d_add(dentry, inode);
067     return dentry;
068 }
069 
070 static int fill_superblock(struct super_block *sb, void *data, int silent)
071 {
072     struct inode *root;
073     struct dentry *root_dentry;
074 
075     sb->s_blocksize = PAGE_CACHE_SIZE;
076     sb->s_blocksize_bits = PAGE_CACHE_SHIFT;
077     sb->s_magic = 0x20040804;
078     sb->s_op = &superblock_ops;
079 
080     // Inode fuer das Root-Verzeichnis anlegen...
081     root = make_new_inode(sb, S_IFDIR | 0755);
082     if( !root )
083         return -ENOMEM;
084     root->i_op = &simple_dir_inode_operations;
085     root->i_fop = &simple_dir_operations;
086     root_dentry = d_alloc_root(root);
087     printk("root_dentry->name: %sn", root_dentry->d_iname );
088     if( !root_dentry ) {
089         iput( root );
090         return -ENOMEM;
091     }
092     sb->s_root = root_dentry;
093 
094     create_file( sb, root_dentry, "hello" );
095 
096     return 0;
097 }
098 
099 static struct super_block *get_superblock(struct file_system_type *fst,
100     int flags, const char *devname, void *data)
101 {
102     printk("get_superblock (%s, %s)...n", fst->name, devname);
103     return get_sb_single(fst, flags, data, fill_superblock);
104 }
105 
106 struct file_system_type hello={
107     .owner              = THIS_MODULE,
108     .name               = "hello",
109     .get_sb             = get_superblock,
110     .kill_sb    = kill_litter_super
111 };
112 
113 static int __init mod_init(void)
114 {
115     return register_filesystem(&hello);
116 }
117 
118 static void __exit mod_exit(void)
119 {
120     unregister_filesystem(&hello);
121 }
122 
123 module_init( mod_init );
124 module_exit( mod_exit );
125 MODULE_LICENSE("GPL");

Beim Unmounten des Filesystems ruft der Kernel die Methode »kill_sb()« auf. Wenn das Filesystem keine besonderen De-Initialisierungen durchführen muss, kann der Programmierer einfach auf die ebenfalls vorhandene Funktion »kill_litter_super()« zurückgreifen.

Jede Filesystem-Instanz benötigt nicht nur den Superblock, sondern auch einen Inode und ein »dentry«-Objekt für das Wurzelverzeichnis. Beides legt das Beispiel beim Mounten an. Das Filesystem soll eine (virtuelle) Datei enthalten, die beim Lesen den String »Hello World« zurückgibt. »struct file_operations« ordnet dem Inode dieser Datei die Lesefunktion »read_hello_world()« zu (Zeile 13). Die Implementierung der »struct file_operations«-Funktionen hatte die zweite Kern-Technik-Folge vorgestellt [1]. Im Ernstfall müsste man für die Inodes noch die beschrieben »lookup()«-Funktionen implementieren. Stattdessen erzeugt das Beispiel direkt das »dentry«-Objekt und legt es über die Funktion »d_add()« im Dcache ab (Zeile 66).

Abbildung 4: Das VFS-Modell hat vier verschiedene Objekte, Inodes und Dentries realisieren die Hierarchie.

Listing 1 zeigt den vollständigen Code des virtuellen Dateisystems. Der Name des Filesystemtyps lautet »hello« (Zeile 108). Der Code und das zugehörige Makefile ist unter [2] zu finden. Ist das kompilierte Modul geladen, mountet der Befehl »mount -t hello none /mnt« das virtuelle Filesystem.

Ein »ls -l /mnt« zeigt die Datei »hello«, die sich per »cat« lesen lässt. Der Einfachheit halber ist »hello« als unendliche Datei realisiert, also als eine, die beim Lesen nie ein End-of-File liefert. Der Befehl »cat /mnt/hello« lässt sich mit [Strg]+[C] abbrechen.

Nicht stehen bleiben

Wer nach dieser Einführung auf den Geschmack gekommen ist, kann versuchen die Moduldatei »hello« um eine Schreibfunktion zu erweitern. Danach könnte die Implementierung eines Unterverzeichnisses auf dem Plan stehen. Hilfestellung dazu leisten [3], [4] und [5]. Ein weiterer wichtiger Ausgangspunkt für eigene Dateisystem-Projekte ist der offene Quellcode des Kernels, vor allen Dingen das von Linus Torvalds selbst erstellte Template »/usr/src/linux/fs/ramfs/inode.c«. (ofr)