☰

Warum durchläuft find -inum den gesamten Dateisystembaum?

tag-icon • tag-icon find performance ext4 inode
Warum durchläuft find -inum den gesamten Dateisystembaum?

Es überrascht mich, dass find das gesamte Dateisystem durchläuft, wenn ich eine einfache

find -inum 12345

Ohne Hintergrundinformationen scheint es mir, dass es viel einfachere Möglichkeiten geben müsste, alle Dateien mit diesem spezifischen Inode 12345 (der hier einfach ein Platzhalter ist) zu ermitteln?

Gibt es hierfür vielleicht sogar eine bessere Möglichkeit? Eine, bei der man nicht die gesamte Verzeichnisstruktur eines Dateisystems durchsuchen muss, nur um zu erkennen, welche Dateinamen zu einem Inode gehören?

aktualisieren

Es gibt noch eine weitere Frage zu diesem Thema Finden Sie schnell heraus, welche Datei(en) zu einer bestimmten Inode-Nummer gehört/gehören aber mit der Absicht, einen besseren (schnelleren) Weg zu finden.

Diese Frage zielt eher darauf ab, herauszufinden, warum dies überhaupt ein solches Problem darstellt. Vielleicht gibt es einen guten Grund im Zusammenhang mit Berechtigungen usw., der es den Benutzern absichtlich schwer machen würde, nicht die Verzeichnisstruktur durchsuchen zu müssen, um nach allen Dateinamen in einem Inode zu suchen.

Dennoch erscheint es ziemlich seltsam, dass ein Dateisystem ein solches Problem damit haben würde, alle Dateinamen einem Inode (zumindest dem privilegierten root) Benutzer mitzuteilen

Das Dateisystem, für das ich diese Frage am liebsten beantwortet hätte (falls es wichtig ist), ist ext4.

Antwort1

Der sehr einfache Grund ist, dass zumindest für die Dateisysteme vom Typ ext2/ext3/ext4 die Dateinamen über dasVerzeichniseinträgein Verzeichnisdateien gespeicherte Daten.

Dies bedeutet, dass die Dateien vom Typ „Verzeichnis“ über ein mehr oder weniger kompliziertes System zum Speichern der Dateinamen (der Dateien im Verzeichnis) und der Inodes verfügen, die zu den Daten dieser Dateien führen.

Etwas vereinfacht (ext3/4 verwenden Hash-Tabellen-Erweiterungen zur Beschleunigung der Verzeichnisbaum-Durchquerung usw.) sieht es wie eine solche Auflistung aus:

## filenames ##    ## inode-numbers ##
filename1            0123
filename2            01242
anotherfilename      3313
yetanotherfilename   11233

Im Wesentlichen die Dateinamentritt immer nur innerhalb der Daten auf, die sich auf die Verzeichnisdateien beziehen, undwerden nirgends in den Metadaten gespeichertdas Dateisystem speichertfür/von den Inodes. Daher besteht die einzige Möglichkeit, die mit einer Inode-Nummer verknüpften Dateinamen zu erhalten darin, alle Verzeichniseinträge aller Verzeichnisdateien durchzugehen.

Antwort2

Sie schrieben:

Es überrascht mich, dass find das gesamte Dateisystem durchläuft, wenn ich ein einfaches find -inum 12345 ausführe.

findführt per Definition einen Baumdurchlauf aus, der bei dem angegebenen Verzeichnis oder den angegebenen Verzeichnissen beginnt, mit einem Standardstartverzeichnis von ..

find -inum 12345durchläuft den gesamten Verzeichnisbaum, beginnend mit dem aktuellen Arbeitsverzeichnis. Es durchläuft wahrscheinlich nicht das gesamte Dateisystem, es sei denn, es .enthält zufällig einen Einhängepunkt für das Dateisystem.

Es gibt effizientere Möglichkeiten, alle Dateien mit einer bestimmten Inode-Nummer zu finden - fsdb, debugfs, und ncheckin der Antwort, auf die Sie verlinkt haben - aber findes muss ein Tree Walk durchgeführt werden, weilNormen. Beachten Sie, dass Sie, wenn der gesuchte Inode nur einen Link hat, finddie -quitOption angeben können, den Tree Walk nach der ersten Übereinstimmung zu beenden (sofern unterstützt).

Auch diese anderen Befehle sind nicht immer schnell, teilweise weil sie ein ganzes Dateisystem und nicht nur einen Verzeichnisbaum durchsuchen müssen, aber sie machen das Beste aus den Daten, die ihnen zur Verfügung stehen. Das Grundproblem ist die Struktur der meisten Unix-Dateisysteme.

  • Der Inode einer Datei enthält zahlreiche Informationen, „der Name oder die Namen der Datei“ und „das Verzeichnis oder die Verzeichnisse, die die Datei enthalten“ gehören jedoch nicht dazu.
  • Die Struktur eines Verzeichnisses ist auf den meisten Unix-Dateisystemen sehr einfach: Es enthält lediglich eine Liste von Einträgen, von denen jeder ein (Inode-Nummer, Dateiname)-Paar ist.
  • Um das Verzeichnis oder die Verzeichnisse zu finden, die Inode 12345 enthalten, und den Namen oder die Namen, mit denen diese Verzeichnisse darauf verweisen, müssen diese Befehle auf den meisten Unix-Dateisystemen jeden Eintrag jedes Verzeichnisses im Dateisystem durchsuchen, bis sie alle passenden Einträge gefunden haben. Der Inode einer Dateitutenthält die Anzahl der Verzeichniseinträge, die darauf verweisen, so dass sie die Suche beenden können, sobald sie so viele Einträge gefunden haben.
  • Im Gegensatz dazu ist die Suche nach einem Verzeichnisnamen viel effizienter, da jedes Verzeichnis die Inode-Nummer seines übergeordneten Verzeichnisses enthält, ..sodass nur dieses eine Verzeichnis nach einem passenden Eintrag durchsucht werden muss. (Es gibt eine Ausnahme: Das Stammverzeichnis eines Dateisystems hat einen ..Eintrag, der auf dasselbe Verzeichnis verweist.)

Antwort3

Eine einfachere Antwort wäre möglicherweise eine Analogie.

Stellen Sie sich vor, Sie würden in einem Telefonbuch nach einer Telefonnummer statt nach einem Namen suchen.

verwandte Informationen