Wie werden Verzeichnisse in Unix-Dateisystemen implementiert?

19

Meine Frage ist, wie Verzeichnisse implementiert werden? Ich kann eine Datenstruktur wie eine Variable glauben, zB eine Tabelle, ein Array oder ähnliches. Da UNIX Open Source ist, kann ich in der Quelle nachsehen, was das Programm beim Erstellen eines neuen Verzeichnisses tut. Können Sie mir sagen, wo ich das Thema suchen oder erläutern soll? Dass ein Verzeichnis eine Datei ist, die ich verstehen konnte, und ein Verzeichnis wirklich eine Datei ist? Ich bin nicht sicher, ob es wahr ist, dass Dateien "in" Dateien gespeichert werden, während man das Wort "file" noch so gut wie immer sagen kann, und ich bin mir nicht sicher, was überhaupt keine Datei ist, da man sogar eine Variable "a" nennen kann Datei. Zum Beispiel ist ein Link sicherlich keine Datei und ein Link ist wie ein Verzeichnis, aber das verstößt dann dagegen, dass ein Verzeichnis eine Datei ist?

Niklas
quelle
1
Interessieren Sie sich für ein bestimmtes Dateisystem?
Ignacio Vazquez-Abrams
3
In UNIX ist alles eine Datei (historische Weisheit). Aber nicht jeder UNIX ist Open Source. Gnu ist nicht Unix, weißt du? Open Solaris ist ein Open Source-Unix, während Linux nur ein unixoides Betriebssystem ist. :) Und ja - Dateisysteme - Reiserfs? Ext2-3-4? XFS? NFS?
Benutzer unbekannt
2
Ein Link ist eigentlich auch eine Datei.
Mattdm
5
Ein symbolischer Link ist eine Datei. Ein fester Link ist eine Kante im Dateisystemgraphen.
dmckee
3
Anzeige: Möglicherweise interessieren Sie sich für den Site-Vorschlag zur Betriebssystementwicklung .
Gilles 'SO - hör auf, böse zu sein'

Antworten:

22

Die interne Struktur der Verzeichnisse hängt vom verwendeten Dateisystem ab. Wenn Sie genau wissen möchten, was passiert, schauen Sie sich die Implementierungen von Dateisystemen an.

Grundsätzlich ist ein Verzeichnis in den meisten Dateisystemen ein assoziatives Array zwischen Dateinamen (Schlüsseln) und Inodennummern (Werten). So etwas¹:

1167010 .
1158721 ..
1167626 subdir
 132651 barfile
 132650 bazfile

Diese Liste ist in einer Kette von (normalerweise) 4-KB-Blöcken mehr oder weniger effizient codiert. Beachten Sie, dass der Inhalt regulärer Dateien auf ähnliche Weise gespeichert wird. Bei Verzeichnissen macht es keinen Sinn zu wissen, welche Größe tatsächlich in diesen Blöcken verwendet wird. Aus diesem Grund dubeträgt die Größe der von gemeldeten Verzeichnisse ein Vielfaches von 4 KB.

Inodes sind dazu da, Blöcke miteinander zu verbinden, um eine Einheit zu bilden, nämlich eine "Datei" im allgemeinen Sinne. Sie werden durch eine Nummer identifiziert, die eine Art von Adresse ist, und jede wird normalerweise als einzelner spezieller Block gespeichert.

All dies wird im Kernel-Modus verwaltet. Die Software fordert lediglich die Erstellung eines Verzeichnisses mit einer Funktion an, int mkdir(const char *pathname, mode_t mode);die zu einem Systemaufruf führt, und der Rest wird hinter den Kulissen ausgeführt.

Über links struktur:

Ein fester Link ist keine Datei, sondern lediglich ein neuer Verzeichniseintrag (dh eine Zuordnung von Name zu Inode-Nummer ), der auf eine bereits vorhandene Inode-Entität² verweist. Dies bedeutet, dass auf denselben Inode über verschiedene Pfadnamen zugegriffen werden kann. Da Metadaten (Berechtigungen, Eigentumsrechte, Zeitstempel usw.) im Inode gespeichert sind, sind diese eindeutig und unabhängig vom Pfadnamen, der für den Zugriff auf die Datei ausgewählt wurde.

Ein symbolischer Link ist eine Datei und unterscheidet sich von ihrem Ziel. Dies bedeutet, dass es eine eigene Inode hat. Früher wurde es wie eine normale Datei behandelt: Der Zielpfad wurde in einem Datenblock gespeichert. Aus Gründen der Effizienz werden in neueren ext- Dateisystemen Pfade, die kürzer als 60 Byte sind, im Inode selbst gespeichert (unter Verwendung der Felder, die normalerweise zum Speichern der Zeiger auf Datenblöcke verwendet würden).

-
1. dies wurde erhalten mit ls -ai1 testdir.
2. Wessen Typ muss sich heutzutage von 'directory' unterscheiden?

Stéphane Gimenez
quelle
Vielen Dank für die Ausarbeitung, damit ich den Unterschied zwischen Verzeichnissen und Dateien auf programmatischer Ebene verstehen kann.
Niklas
12

Um den Beitrag von Stéphane Gimenez zu erweitern, müssen Sie beim Erstellen eines neuen Verzeichnisses einen neuen Inode mit dem Wert st_mode von S_IFDIR (im Berechtigungsmodus) erstellen und zwei Einträge im ersten Datenblock des neuen Inodes mit dem Link ( 2) Systemaufruf: '.' welche auf diesen neuen Inode verweist und '..' welche auf das übergeordnete Verzeichnis verweist, dann einen Eintrag im übergeordneten Verzeichnis mit dem Inode und dem Namen des neuen Verzeichnisses erstellen - der erste und letzte Teil werden vom Systemaufruf mknod ( 2). Heutzutage kann nur root mknod (2) für solche Aufgaben verwenden, über die wir sprechen.

mkdir("/home/larry.user/xyzzy", 0666)Dies ist beispielsweise im Wesentlichen der folgende Code (dies war C-Code aus SysV-Tagen [1]):

int mode = 0666;
char newdir[] = "/home/larry.user/xyzzy";
char path1[NAMESZ+4, path2[NAMESZ+4], *p;
mknod(newdir, S_IFDIR|mode);
strcpy(path1, newdir);
strcat(path1, "/."); /* "." link */
link(newdir, path1);
strcat(path1, ".");  /* ".." link */
strcpy(path2, newdir);
if ((p = strrchr(path2, '/') == (char *)0) /* root directory */
    link(".", path1);
else {
    *p = '\0';
    link(path2, path1);
}
  1. Haviland & Salama, "UNIX System Programming", 1987, S. 69-71.

Dies war zu fehleranfällig (und einer der Hauptgründe für fsck), sodass ein mkdir (2) -Systemaufruf erstellt wurde, um dies für Sie tun zu können.

Beachten Sie, dass jedes Dateisystemobjekt mit mknod (2) erstellt werden kann: reguläre Datei, Verzeichnis, Gerätedatei, Symlink usw. Um also eine der Fragen des OP zu beantworten, ist ein Verzeichnis eine Datei, dh "es" ist ein Objekt, das durch eine Inode repräsentiert wird und sich in einem Dateisystem befindet, das sich mit einer I / O-Schnittstelle verhält. "

Arcege
quelle
Vielen Dank für die sehr interessante Antwort. Ich verstehe und denke, ich kann auch in der Quelle nach dem Programm suchen, touchdas eine leere Datei erstellt, und sehen, was es tut.
Niklas
2

Wenn Sie weitere Informationen zu Unix / Linux-Dateisystemen wünschen, empfehle ich Ihnen 2 Bücher Grundlegendes zum Linux-Kernel und zur Linux-Kernel-Entwicklung . Dies sind die besten Bücher zum Verständnis des Linux-Kernels.

In den Unix-Systemen "Common File Model" wird jedes Verzeichnis als Datei betrachtet, die eine Liste von Dateien und Verzeichnissen enthält.

Im VFS (Virtual File Systems) werden die Verzeichnisse in einer Struktur namens dargestellt dentry. Es dentry handelt sich um eine C-Struktur mit einem Zeichenfolgennamen ( d_name ), einem Zeiger auf einen Inode ( d_inode ) und einem Zeiger auf den übergeordneten Eintrag ( d_parent ). Eine Inode ist eine Struktur zum Verarbeiten von Informationen zu einer Datei im Dateisystem. Wenn Sie beispielsweise das Verzeichnis haben /tmp/test/foo, erstellt das VFS für jede Komponente im Pfadnamen ein Eintragsobjekt. Es wird also ein Eintragsobjekt für /, ein zweites Eintragsobjekt für den testEintrag des Wurzelverzeichnisses und ein drittes Eintragsobjekt für den fooEintrag des Testverzeichnisses erstellt .

Dimitri
quelle
Vielen Dank Dimitri. Ich möchte verstehen, warum ein Projekt eine bestimmte Datenstruktur wie einen B-Baum, einen Binärbaum, einen Trie oder ein assoziatives Array ausgewählt hat. Ich halte es für wichtig, eine geeignete Datenstruktur / ein geeignetes Datenmodell auszuwählen. Wenn Sie mehr über die verschiedenen Implementierungen erfahren, erhalten Sie die Details, nach denen ich suche.
Niklas,
1

Sie können mit dem Lesen von http://www.freebsd.org/doc/en/books/design-44bsd/book.html#OVERVIEW-FILESYSTEM beginnen . Weitere Informationen finden Sie im hervorragenden klassischen Buch "Das Design und die Implementierung des 4.4 BSD-Betriebssystems".

schnappen
quelle
Danke für den Link. Ich verstehe, dass beide Dateien Verzeichnisse sind, also Arrays, die entweder als Dateien oder als Verzeichnisse interpretiert werden. Bitte korrigieren Sie mich, wenn ich falsch liege.
Niklas
1
Verzeichnisse sind traditionell nur speziell formatierte Dateien, aber das stimmt nicht mehr: de.wikipedia.org/wiki/ReiserFS#Design In ReiserFS und einigen anderen sind Verzeichnisse Einträge in einer Datenbank. Verzeichnisse können als Arrays fungieren, aber das ist nur die Programmierabstraktion.
Bruce Ediger
Vielen Dank für den Hinweis auf die Details. Jetzt denke ich , dass ich mehr verstehen , wie Dateisysteme noch funktionieren fragen , wie und warum das Programm locateseine Werke tut und wie dies im Zusammenhang mit der Aktualisierung des Programm finden , indem Sie updatedb(spez I Verwendung PC-BSD, DragonflyBSD und Ubuntu Natty Boote von Live - CDs und Benchmarking verschiedene Installationen und Schnittstellen)
Niklas