8

When I use find --version with GNU find, I get something like this:

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

What do these "features" mean? There's some reference to O_NOFOLLOW being a security measure in man find, and there's a mention of LEAF_OPTIMISATION being an optimization that saves a few lstat calls on leaf nodes. But I can't find anything about FTS, D_TYPE or CBO.

  • 1
    This seems to be the end of the ladder. Maybe could could force someone to read find's source code. Promise some chocolates. – ott-- Feb 17 '15 at 21:34
8

This is a complete answer derived from the answers of Ketan and daniel kullman, as well as my own research.

Most of the "features" turn out to be query optimizations, since find is in general capable of (almost) arbitrarily complex queries on the filesystem.


D_TYPE

The presence of the D_TYPE feature means that find was compiled with support for the d_type field in struct dirent. This field is a BSD extension also adopted by Linux, which provides the file type (directory, file, pipe, socket, char/block device, etc.) in the structure returned from readdir and friends. As an optimization, find can use this to reduce or eliminate lstat calls when -type is used as a filter expression.

readdir may not always populate d_type on some filesystems, so sometimes an lstat will still be needed.

More info from the official documentation: https://www.gnu.org/software/findutils/manual/html_node/find_html/d_005ftype-Optimisation.html

O_NOFOLLOW

This option will read either (enabled) or (disabled). If present and enabled, this feature implements a security measure that protects find from certain TOCTTOU race attacks. Specifically, it prevents find from traversing a symlink while performing directory traversal, which could occur if the directory were replaced by a symlink after the directory's filetype was checked but before the directory was entered.

With this option enabled, find will use open(..., O_NOFOLLOW) on the directory to open only real directories, then use openat to open files within that directory.

LEAF_OPTIMISATION

This slightly obscure optimization allows find to deduce which subdirectories of a parent directory are directories by using the link count of the parent directory, since subdirectories will contribute to the link count of the parent (via the .. link). In certain circumstances, it will allow find to elide a stat call. However, if the filesystem or OS misrepresents st_nlinks, it may cause find to produce bogus results (this is thankfully a very rare occurrence).

More info in the official documentation: https://www.gnu.org/software/findutils/manual/html_node/find_html/Leaf-Optimisation.html

FTS

When enabled, the FTS feature causes find to use the fts API to traverse the file hierarchy, instead of a straight recursive implementation.

It's not clear to me what the advantage of fts is, but FTS is basically the default on all default find versions I've seen so far.

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

CBO

It turns out (after reading the find source code as suggested by daniel kullman) that "CBO" refers to the query optimization level (it stands for "cost-based optimizer"). For example, if I do find -O9001 --version, I get

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

Looking at the -O option in man find, I see

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

Mystery solved! It's a little strange that the option is a runtime value; usually I would expect the --version output only to reflect compile-time options.

1

Information about O_NOFOLLOW is given in the info page of find:

9.2.1.1 O_NOFOLLOW

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

If your system supports the O_NOFOLLOW flag (1) to the open(2)' system call,find' uses it when safely changing directory. The target directory is first opened and then find' changes working directory with thefchdir()' system call. This ensures that symbolic links are not followed, preventing the sort of race condition attack in which use is made of symbolic links.

...

From the source tree, CBO occurs only in the file parser.c:

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

indicating it to be cost based optimization (my best guess).

D_TYPE occurs at several places in the source-tree and seems like has to do with the directory entry type:

$ grep 'D_TYPE' */**

Yields:

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

and some more entries. You can find the source here.

0

When looking through the findutils source tree (http://git.savannah.gnu.org/cgit/findutils.git/tree/), I found the following:

  • configure.ac: --enable-d_type-optimization,Make use of the file type data returned in struct dirent.d_type by readdir()),
  • m4/withfts.m4: --without-fts Use an older mechanism for searching the filesystem, instead of using fts()

I didn't find anything about CBO; you might have to download the source code and search for the term..

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.