Was bedeuten die "aktivierten Funktionen" in GNU find?

8

Wenn ich find --versionmit GNU find verwende, erhalte ich ungefähr Folgendes:

find (GNU findutils) 4.5.9     
[license text]
Features enabled: D_TYPE O_NOFOLLOW(enabled) LEAF_OPTIMISATION FTS(FTS_CWDFD) CBO(level=2)

Was bedeuten diese "Funktionen"? Es gibt einen Hinweis darauf, O_NOFOLLOWdass es sich um eine Sicherheitsmaßnahme handelt man find, und es wird erwähnt, LEAF_OPTIMISATIONdass es sich um eine Optimierung handelt, die einige lstatAufrufe von Blattknoten erspart . Aber ich kann nichts darüber finden FTS, D_TYPEoder CBO.

nneonneo
quelle
1
Dies scheint das Ende der Leiter zu sein. Vielleicht könnte jemand gezwungen werden, den Quellcode von find zu lesen. Versprich ein paar Pralinen.
ott--

Antworten:

8

Dies ist eine vollständige Antwort, die sich aus den Antworten von Ketan und Daniel Kullman sowie meiner eigenen Forschung ergibt.

Die meisten "Funktionen" stellen sich als Abfrageoptimierungen heraus, da sie findim Allgemeinen (fast) beliebig komplexe Abfragen im Dateisystem ausführen können.


D_TYPE

Das Vorhandensein des D_TYPEFeatures bedeutet, dass findmit Unterstützung für das d_typeFeld in kompiliert wurde struct dirent. Dieses Feld ist eine BSD-Erweiterung, die ebenfalls von Linux übernommen wurde und den Dateityp (Verzeichnis, Datei, Pipe, Socket, Zeichen- / Blockgerät usw.) in der von readdirund Freunden zurückgegebenen Struktur angibt . findKann als Optimierung verwendet werden, um lstatAnrufe zu reduzieren oder zu eliminieren , wenn -typesie als Filterausdruck verwendet werden.

readdird_typeAuf einigen Dateisystemen ist dies möglicherweise nicht immer der lstatFall , daher wird manchmal immer noch eine benötigt.

Weitere Informationen finden Sie in der offiziellen Dokumentation: https://www.gnu.org/software/findutils/manual/html_node/find_html/d_005ftype-Optimisation.html

O_NOFOLLOW

Diese Option liest entweder (enabled)oder (disabled). Wenn vorhanden und aktiviert, implementiert diese Funktion eine Sicherheitsmaßnahme, die findvor bestimmten TOCTTOU-Race-Angriffen schützt . Insbesondere wird verhindert, dass findein Symlink beim Durchlaufen des Verzeichnisses durchlaufen wird. Dies kann auftreten, wenn das Verzeichnis durch einen Symlink ersetzt wird, nachdem der Dateityp des Verzeichnisses überprüft wurde, aber bevor das Verzeichnis eingegeben wurde.

Wenn diese Option aktiviert ist, findwerden open(..., O_NOFOLLOW)im Verzeichnis nur echte Verzeichnisse openatgeöffnet und anschließend Dateien in diesem Verzeichnis geöffnet.

LEAF_OPTIMISATION

Diese etwas undurchsichtige Optimierung ermöglicht es find, anhand der Linkanzahl des übergeordneten Verzeichnisses abzuleiten, welche Unterverzeichnisse eines übergeordneten Verzeichnisses Verzeichnisse sind, da Unterverzeichnisse (über den ..Link) zur Linkanzahl des übergeordneten Verzeichnisses beitragen . Unter bestimmten Umständen findkann ein statAnruf gelöscht werden . Wenn das Dateisystem oder das Betriebssystem jedoch falsch dargestellt wird st_nlinks, kann dies findzu falschen Ergebnissen führen (dies ist zum Glück ein sehr seltenes Ereignis).

Weitere Informationen finden Sie in der offiziellen Dokumentation: https://www.gnu.org/software/findutils/manual/html_node/find_html/Leaf-Optimisation.html

FTS

Wenn diese Funktion aktiviert ist, verwendet die FTSFunktion finddie ftsAPI zum Durchlaufen der Dateihierarchie anstelle einer direkten rekursiven Implementierung.

Mir ist nicht klar, was der Vorteil ftsist, aber es FTSist im Grunde die Standardeinstellung für alle Standardversionen, die findich bisher gesehen habe.

Weitere Informationen: https://www.gnu.org/software/findutils/manual/html_node/find_html/fts.html , http://man7.org/linux/man-pages/man3/fts.3.html

CBO

Es stellt sich heraus (nach dem Lesen des findvon Daniel Kullman vorgeschlagenen Quellcodes), dass sich "CBO" auf die Abfrageoptimierungsstufe bezieht (es steht für "kostenbasierter Optimierer"). Wenn ich es zum Beispiel tue find -O9001 --version, bekomme ich

Features enabled: D_TYPE O_NOFOLLOW(enabled) LEAF_OPTIMISATION FTS() CBO(level=9001) 

Wenn ich mir die -OOption in anschaue man find, sehe ich

-Olevel
  Enables query optimisation.   The find program reorders tests to speed up execution  while  preserving  the  overall
  effect; that is, predicates with side effects are not reordered relative to each other.  The optimisations performed
  at each optimisation level are as follows.

  0      Equivalent to optimisation level 1.

  1      This is the default optimisation level  and  corresponds  to  the  traditional  behaviour.   Expressions  are
         reordered  so that tests based only on the names of files (for example -name and -regex) are performed first.

  2      Any -type or -xtype tests are performed after any tests based only on the names  of  files,  but  before  any
         tests  that  require information from the inode.  On many modern versions of Unix, file types are returned by
         readdir() and so these predicates are faster to evaluate than predicates which need to stat the file first.

  3      At this optimisation level, the full cost-based query optimiser is enabled.  The order of tests  is  modified
         so  that  cheap  (i.e. fast) tests are performed first and more expensive ones are performed later, if neces-
         sary.  Within each cost band, predicates are evaluated earlier or later according to whether they are  likely
         to  succeed or not.  For -o, predicates which are likely to succeed are evaluated earlier, and for -a, predi-
         cates which are likely to fail are evaluated earlier.

  The cost-based optimiser has a fixed idea of how likely any given test is to succeed.  In some cases the probability
  takes  account of the specific nature of the test (for example, -type f is assumed to be more likely to succeed than
  -type c).  The cost-based optimiser is currently being evaluated.   If it does not actually improve the  performance
  of find, it will be removed again.  Conversely, optimisations that prove to be reliable, robust and effective may be
  enabled at lower optimisation levels over time.  However, the default behaviour (i.e. optimisation level 1) will not
  be  changed  in  the 4.3.x release series.  The findutils test suite runs all the tests on find at each optimisation
  level and ensures that the result is the same.

Geheimnis gelüftet! Es ist etwas seltsam, dass die Option ein Laufzeitwert ist. Normalerweise würde ich erwarten, dass die --versionAusgabe nur Optionen zur Kompilierungszeit widerspiegelt.

nneonneo
quelle
1

Informationen zu finden Sie O_NOFOLLOWauf der infoSeite von find:

9.2.1.1 O_NOFOLLOW

..................

Wenn Ihr System das O_NOFOLLOW-Flag (1) für die open(2)' system call,Suche unterstützt, wird es beim sicheren Wechseln des Verzeichnisses verwendet. Das Zielverzeichnis wird zuerst geöffnet und dann der find' changes working directory with theSystemaufruf von fchdir (). Dies stellt sicher, dass symbolischen Links nicht gefolgt wird, und verhindert die Art von Race Condition Attack, bei dem symbolische Links verwendet werden.

...

Aus dem Quellbaum, CBOtritt nur in der Datei parser.c:

 printf("CBO(level=%d) ", (int)(options.optimisation_level)); 

Dies ist eine kostenbasierte Optimierung (meine beste Vermutung).

D_TYPE tritt an mehreren Stellen im Quellbaum auf und scheint mit dem Verzeichniseintragstyp zu tun zu haben:

$ grep 'D_TYPE' */**

Ausbeuten:

find/parser.c:#if defined USE_STRUCT_DIRENT_D_TYPE && defined HAVE_STRUCT_DIRENT_D_TYPE
lib/savedirinfo.c:#if defined HAVE_STRUCT_DIRENT_D_TYPE && defined USE_STRUCT_DIRENT_D_TYPE

und einige weitere Einträge. Die Quelle finden Sie hier .

mkc
quelle
0

Beim Durchsuchen des Findutils-Quellbaums ( http://git.savannah.gnu.org/cgit/findutils.git/tree/ ) habe ich Folgendes festgestellt:

  • configure.ac: --enable-d_type-optimierung, Verwenden Sie die von readdir ()) in struct dirent.d_type zurückgegebenen Dateitypdaten.
  • m4 / withfts.m4: --without-fts Verwenden Sie einen älteren Mechanismus zum Durchsuchen des Dateisystems, anstatt fts () zu verwenden.

Ich habe nichts über CBO gefunden; Möglicherweise müssen Sie den Quellcode herunterladen und nach dem Begriff suchen.

Daniel Kullmann
quelle