>From be9b95a8f5a3ddbb722099df10d19c74a341fff9 Mon Sep 17 00:00:00 2001 From: Paul Eggert Date: Wed, 11 Apr 2018 12:50:35 -0700 Subject: [PATCH] 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. --- ChangeLog | 12 ++++++++++++ lib/fts.c | 55 +++++++++++++++++++++++++++++++------------------------ 2 files changed, 43 insertions(+), 24 deletions(-) diff --git a/ChangeLog b/ChangeLog index ea30952f5..3702f75c1 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,15 @@ +2018-04-11 Paul Eggert + + 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. + 2018-04-07 Bruno Haible unicase/u*-context: Fix link errors with libunistring <= 0.9.9. diff --git a/lib/fts.c b/lib/fts.c index 3814e58fc..a26c6824a 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; -- 2.14.3