Что означают «включенные функции» в GNU find?

Когда я использую find --versionс GNU find, я получаю что-то вроде этого:

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

Что означают эти «особенности»? Есть некоторая ссылка на O_NOFOLLOWто, чтобы быть мерой безопасности man find, и есть упоминание LEAF_OPTIMISATIONоб оптимизации, которая экономит несколько lstatвызовов на конечных узлах. Но я не могу найти ничего о FTS, D_TYPEили CBO.

Это полный ответ, полученный из ответов Кетана и Даниэля Куллмана, а также из моих собственных исследований.

Большая часть «функций» оказывается оптимизацией запросов, поскольку findв целом способна (почти) произвольно усложнять запросы в файловой системе.

D_TYPE

Наличие D_TYPEфункции означает, что findбыло скомпилировано с поддержкой d_typeполя в struct dirent. Это поле является расширением BSD, также принятым в Linux, которое предоставляет тип файла (каталог, файл, канал, сокет, устройство char / block и т. Д.) В структуре, возвращаемой от readdirдрузей. В качестве оптимизации findможно использовать это для уменьшения или исключения lstatвызовов, когда -typeиспользуется в качестве выражения фильтра.

readdirможет не всегда заполнять d_typeнекоторые файловые системы, поэтому иногда lstatони все равно будут необходимы.

Дополнительная информация из официальной документации: https://www.gnu.org/software/findutils/manual/html_node/find_html/d_005ftype-Optimisation.html.

O_NOFOLLOW

Эта опция будет читать (enabled)или (disabled). Если эта функция присутствует и включена, она реализует меру безопасности, которая защищает findот определенных гонок TOCTTOU. В частности, он предотвращает findобход символической ссылки при выполнении обхода каталога, что может произойти, если каталог был заменен символической ссылкой после проверки типа файла каталога, но до того, как каталог был введен.

Если эта опция включена, findбудет использовать open(..., O_NOFOLLOW)каталог для открытия только реальных каталогов, а затем использовать openatдля открытия файлов в этом каталоге.

LEAF_OPTIMISATION

Эта немного неясная оптимизация позволяет findопределить, какие подкаталоги родительского каталога являются каталогами, используя счетчик ссылок родительского каталога, поскольку подкаталоги будут вносить вклад в счетчик ссылок родительского каталога (через ..ссылку). В определенных обстоятельствах это позволит findотказаться от statвызова. Однако, если файловая система или операционная система искажают данные st_nlinks, это может привести findк ложным результатам (к счастью, это очень редкое явление).

Более подробная информация в официальной документации: https://www.gnu.org/software/findutils/manual/html_node/find_html/Leaf-Optimisation.html.

FTS

При включении эта FTSфункция заставляет findиспользовать ftsAPI для обхода файловой иерархии вместо прямой рекурсивной реализации.

Мне не ясно, в чем преимущество fts, но FTSв основном это стандартное значение во всех findверсиях по умолчанию, которые я видел до сих пор.

Дополнительная информация: https://www.gnu.org/software/findutils/manual/html_node/find_html/fts.html , http://man7.org/linux/man-pages/man3/fts.3.html.

СВО

Оказывается (после прочтения findисходного кода, как предложил Даниэль Куллман), что «CBO» относится к уровню оптимизации запросов (он означает «оптимизатор на основе затрат»). Например, если я делаю find -O9001 --version, я получаю

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

Глядя на -Oвариант в man find, я вижу

-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.

Тайна разгадана! Немного странно, что опция является значением времени выполнения; обычно я ожидаю, что --versionвыходные данные будут отражать только параметры времени компиляции.

Информация о размещена O_NOFOLLOWна infoстранице find:

9.2.1.1 O_NOFOLLOW

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

Если ваша система поддерживает флаг O_NOFOLLOW (1) для open(2)' system call,поиска, он использует его для безопасного изменения каталога. Целевой каталог сначала открывается, а затемfind' changes working directory with the системный вызов fchdir (). Это гарантирует, что символические ссылки не будут отслеживаться, предотвращая атаку типа гонки, в которой используются символические ссылки.

...

Из исходного дерева CBOвстречается только в файле parser.c:

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

указав, что это оптимизация на основе затрат (моя лучшая догадка).

D_TYPE встречается в нескольких местах дерева исходных текстов и, похоже, связано с типом записи каталога:

$ grep 'D_TYPE' */**

Урожайность:

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

и еще несколько записей. Вы можете найти источник здесь .

Просматривая дерево исходников findutils ( http://git.savannah.gnu.org/cgit/findutils.git/tree/ ), я обнаружил следующее:

• configure.ac: --enable-d_type-оптимизация, использовать данные типа файла, возвращаемые в struct dirent.d_type функцией readdir ()),
• m4 / withfts.m4: --without-fts Использовать более старый механизм для поиска в файловой системе вместо использования fts ()

Я не нашел ничего о CBO; вам, возможно, придется скачать исходный код и найти термин ..