Why `find` likes `stat` or `fstat` so much?

Question

I'm trying to make /usr/bin/find to show something meaningful without doing any sort of stat, with no useful results so far. If I forcefully inhibit stat, find stops descending into subdirectories at all.

As manual page of getdents syscall say, there is d_type field there, so find should already have some information necessary for decisions.

Why need to for stat regardless of -L, -H or whatever options.

Answer 1

Use the source, Luke!

In the GNU find source (I'm looking at version 4.2.2), the code that traverses directory trees is in gnulib/lib/fts.c. At line 1123 there is the following comment:

Record what fts_read will have to do with this entry. In many cases, it will simply fts_stat it, but we can take advantage of any d_type information to optimize away the unnecessary stat calls. I.e., if FTS_NOSTAT is in effect and we're not following symlinks (FTS_PHYSICAL) and d_type indicates this is not a directory, then we won't have to stat it at all. If it is a directory, then (currently) we stat it regardless, in order to get device and inode numbers. Some day we might optimize that away, too, for directories where d_ino is known to be valid.

So they have thought of the optimization you describe, but it is not implemented.

Answer 2

The cited manual page for getdents is Linux-specific, and does not apply to all filesystem types (for instance, the manual page does not mention procfs or nfs), while GNU find is not platform-specific (its manual page mentions SELinux, which is arguably a useful feature to take into account). It could be optimized for this special case as well.

Even if the feature is available, the manual page recommends:

All applications must properly handle a return of DT_UNKNOWN.

That is, the information if available can be useful, but it is not guaranteed to be present.

With all of those drawbacks, the developers of find may not see the need for this optimization. A motivated user could delve into the source code to see how to do this and propose a suitable ifdef'd change.

@Nate Eldredge notes that someone started in this direction. The find manual states in 7.2 d_type Optimisation

When this feature is enabled, find takes advantage of the fact that on some systems readdir will return the type of a file in struct dirent.

The feature was first mentioned in

2005-01-17  James Youngman  <jay@gnu.org>
    * configure.in, find/defs.h, find/find.c, find/parser.c, find/pred.c, find/tree.c, find/util.c:
    Implemented d_type optimisation but not working correctly, so currently disabled

Later, it was revised to use gnulib to support this:

2010-04-08  James Youngman  <jay@gnu.org>

    Adopt the use of the gnulib module d-type.
    * import-gnulib.config (modules): Import the d-type module.
    * configure.ac: Remove old struct dirent.d_type detection logic
    (since we now use the gnulib macro from the d-type module for
    this).

Version 4.2.2 is rather old (perhaps a typo), by the way: 4.2.3 dates from 2004, and is before these changelog entries. The current release-tag in git is 4.5.14 (mid-2014).

Regardless of the status of a d_type optimization, the developers are interested in reducing the number of calls to stat. A note from 4.5.4 (2009-03-10) says for instance:

The ftsfind executable also now avoids calling stat() functions to discover the inode number of a file, if we already read this information from the directory. This does provide a speed-up, but only for a restricted set of commands such as "find . -inum 4001". This fix is listed below as bug #24342.

In summary: OP asked

Why need to for stat regardless of -L, -H or whatever options.

The reason is that it is a special case which is troublesome to make it work seamlessly instead of stat for all of the scenarios where find might need this, and that it takes time to do this.