fts: fix bug in find across filesystems

This fixes a bug I introduced last summer.
Problem reported by Kamil Dudka in:
https://lists.gnu.org/r/bug-gnulib/2018-04/msg00033.html
* lib/fts.c (filesystem_type, dirent_inode_sort_may_be_useful)
(leaf_optimization):
New arg for file descriptor.  All callers changed.
(fts_build): Check for whether inodes should be sorted
before closing the directory.

1 files changed, 31 insertions, 24 deletions

diff --git a/lib/fts.c b/lib/fts.c
index 3814e58fc8..a26c6824a0 100644
--- a/lib/fts.c
+++ b/lib/fts.c
@@ -726,11 +726,12 @@ dev_type_compare (void const *x, void const *y)
   return ax->st_dev == ay->st_dev;
 }
 
-/* Return the file system type of P, or 0 if not known.
+/* Return the file system type of P with file descriptor FD, or 0 if not known.
+   If FD is negative, P's file descriptor is unavailable.
    Try to cache known values.  */
 
 static fsword
-filesystem_type (FTSENT const *p)
+filesystem_type (FTSENT const *p, int fd)
 {
   FTS *sp = p->fts_fts;
   Hash_table *h = sp->fts_leaf_optimization_works_ht;
@@ -756,7 +757,7 @@ filesystem_type (FTSENT const *p)
     }
 
   /* Look-up failed.  Query directly and cache the result.  */
-  if (fstatfs (p->fts_fts->fts_cwd_fd, &fs_buf) != 0)
+  if (fd < 0 || fstatfs (fd, &fs_buf) != 0)
     return 0;
 
   if (h)
@@ -778,12 +779,12 @@ filesystem_type (FTSENT const *p)
   return fs_buf.f_type;
 }
 
-/* Return false if it is easy to determine the file system type of the
-   directory P, and sorting dirents on inode numbers is known not to
-   improve traversal performance with that type of file system.
-   Otherwise, return true.  */
+/* Return true if sorting dirents on inode numbers is known to improve
+   traversal performance for the directory P with descriptor DIR_FD.
+   Return false otherwise.  When in doubt, return true.
+   DIR_FD is negative if unavailable.  */
 static bool
-dirent_inode_sort_may_be_useful (FTSENT const *p)
+dirent_inode_sort_may_be_useful (FTSENT const *p, int dir_fd)
 {
   /* Skip the sort only if we can determine efficiently
      that skipping it is the right thing to do.
@@ -791,7 +792,7 @@ dirent_inode_sort_may_be_useful (FTSENT const *p)
      while the cost of *not* performing it can be O(N^2) with
      a very large constant.  */
 
-  switch (filesystem_type (p))
+  switch (filesystem_type (p, dir_fd))
     {
     case S_MAGIC_CIFS:
     case S_MAGIC_NFS:
@@ -805,16 +806,17 @@ dirent_inode_sort_may_be_useful (FTSENT const *p)
     }
 }
 
-/* Given an FTS entry P for a directory D,
+/* Given an FTS entry P for a directory with descriptor DIR_FD,
    return true if it is both useful and valid to apply leaf optimization.
    The optimization is useful only for file systems that lack usable
    dirent.d_type info.  The optimization is valid if an st_nlink value
    of at least MIN_DIR_NLINK is an upper bound on the number of
-   subdirectories of D, counting "." and ".."  as subdirectories.  */
+   subdirectories of D, counting "." and ".."  as subdirectories.
+   DIR_FD is negative if unavailable.  */
 static enum leaf_optimization
-leaf_optimization (FTSENT const *p)
+leaf_optimization (FTSENT const *p, int dir_fd)
 {
-  switch (filesystem_type (p))
+  switch (filesystem_type (p, dir_fd))
     {
       /* List here the file system types that may lack usable dirent.d_type
          info, yet for which the optimization does apply.  */
@@ -851,12 +853,13 @@ leaf_optimization (FTSENT const *p)
 
 #else
 static bool
-dirent_inode_sort_may_be_useful (FTSENT const *p _GL_UNUSED)
+dirent_inode_sort_may_be_useful (FTSENT const *p _GL_UNUSED,
+                                 int dir_fd _GL_UNUSED)
 {
   return true;
 }
 static enum leaf_optimization
-leaf_optimization (FTSENT const *p _GL_UNUSED)
+leaf_optimization (FTSENT const *p _GL_UNUSED, int dir_fd _GL_UNUSED)
 {
   return NO_LEAF_OPTIMIZATION;
 }
@@ -1050,7 +1053,7 @@ check_for_dir:
                         if (parent->fts_n_dirs_remaining == 0
                             && ISSET(FTS_NOSTAT)
                             && ISSET(FTS_PHYSICAL)
-                            && (leaf_optimization (parent)
+                            && (leaf_optimization (parent, sp->fts_cwd_fd)
                                 == NOSTAT_LEAF_OPTIMIZATION))
                           {
                             /* nothing more needed */
@@ -1335,6 +1338,7 @@ fts_build (register FTS *sp, int type)
         int dir_fd;
         FTSENT *cur = sp->fts_cur;
         bool continue_readdir = !!cur->fts_dirp;
+        bool sort_by_inode = false;
         size_t max_entries;
 
         /* When cur->fts_dirp is non-NULL, that means we should
@@ -1428,7 +1432,7 @@ fts_build (register FTS *sp, int type)
                        && ! (ISSET (FTS_NOSTAT) && ISSET (FTS_PHYSICAL)
                              && ! ISSET (FTS_SEEDOT)
                              && cur->fts_statp->st_nlink == MIN_DIR_NLINK
-                             && (leaf_optimization (cur)
+                             && (leaf_optimization (cur, dir_fd)
                                  != NO_LEAF_OPTIMIZATION)));
             if (descend || type == BREAD)
               {
@@ -1589,6 +1593,15 @@ mem1:                           saved_errno = errno;
                         tail->fts_link = p;
                         tail = p;
                 }
+
+                /* If there are many entries, no sorting function has been
+                   specified, and this file system is of a type that may be
+                   slow with a large number of entries, arrange to sort the
+                   directory entries on increasing inode numbers.  */
+                if (nitems == _FTS_INODE_SORT_DIR_ENTRIES_THRESHOLD
+                    && !sp->fts_compar)
+                  sort_by_inode = dirent_inode_sort_may_be_useful (cur, dir_fd);
+
                 ++nitems;
                 if (max_entries <= nitems) {
                         /* When there are too many dir entries, leave
@@ -1646,13 +1659,7 @@ mem1:                           saved_errno = errno;
                 return (NULL);
         }
 
-        /* If there are many entries, no sorting function has been specified,
-           and this file system is of a type that may be slow with a large
-           number of entries, then sort the directory entries on increasing
-           inode numbers.  */
-        if (nitems > _FTS_INODE_SORT_DIR_ENTRIES_THRESHOLD
-            && !sp->fts_compar
-            && dirent_inode_sort_may_be_useful (cur)) {
+        if (sort_by_inode) {
                 sp->fts_compar = fts_compare_ino;
                 head = fts_sort (sp, head, nitems);
                 sp->fts_compar = NULL;