From 97d5b66578be50712cb77fbe6a047b8fffa1cfbd Mon Sep 17 00:00:00 2001 From: Jim Meyering Date: Wed, 11 Feb 2009 21:32:01 +0100 Subject: [PATCH] fts: arrange not to stat non-directories in more cases This makes GNU find (when it doesn't need to stat each file) *much* more efficient at traversing reiserfs file systems. * lib/fts_.h (struct ftsent) [fts_n_dirs_remaining]: New member. (struct FTS) [fts_leaf_optimization_works_ht]: Add member. * lib/fts.c (fts_close): Free ->fts_leaf_optimization_works_ht. (S_MAGIC_REISERFS, S_MAGIC_PROC): Define. (leaf_optimization_applies): New function. (LCO_hash, LCO_compare): New helper functions. (link_count_optimize_ok): New function. (fts_stat): Initialize new member (if dir). (fts_read): Decrement parent's fts_n_dirs_remaining count if we've just stat'ed a directory. Skip the stat call when possible. Note this AFS-related exchange: http://bugs.debian.org/cgi-bin/bugreport.cgi?bug=143111 and note find's pioctl call in find/fstype.c. But that is necessary only if you want to enable the optimization for AFS, and for now, I don't. --- ChangeLog | 20 +++++++++ lib/fts.c | 145 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++- lib/fts_.h | 12 ++++- 3 files changed, 175 insertions(+), 2 deletions(-) diff --git a/ChangeLog b/ChangeLog index 57ba9441f..e14b96612 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,5 +1,25 @@ 2009-02-13 Jim Meyering + fts: arrange not to stat non-directories in more cases + This makes GNU find (when it doesn't need to stat each file) + *much* more efficient at traversing reiserfs file systems. + * lib/fts_.h (struct ftsent) [fts_n_dirs_remaining]: New member. + (struct FTS) [fts_leaf_optimization_works_ht]: Add member. + * lib/fts.c (fts_close): Free ->fts_leaf_optimization_works_ht. + (S_MAGIC_REISERFS, S_MAGIC_PROC): Define. + (leaf_optimization_applies): New function. + (LCO_hash, LCO_compare): New helper functions. + (link_count_optimize_ok): New function. + (fts_stat): Initialize new member (if dir). + (fts_read): Decrement parent's fts_n_dirs_remaining count if + we've just stat'ed a directory. Skip the stat call when possible. + --- + Note this AFS-related exchange: + http://bugs.debian.org/cgi-bin/bugreport.cgi?bug=143111 + and note find's pioctl call in find/fstype.c. + But that is necessary only if you want to enable the + optimization for AFS, and for now, I don't. + fts: move a function definition "up" (no semantic change) * lib/fts.c (dirent_inode_sort_may_be_useful): Move definition "up" to precede upcoming use of a related function. diff --git a/lib/fts.c b/lib/fts.c index 164834ccd..fdbe2586c 100644 --- a/lib/fts.c +++ b/lib/fts.c @@ -617,6 +617,10 @@ fts_close (FTS *sp) } fd_ring_clear (&sp->fts_fd_ring); + + if (sp->fts_leaf_optimization_works_ht) + hash_free (sp->fts_leaf_optimization_works_ht); + free_dir (sp); /* Free up the stream pointer. */ @@ -639,6 +643,8 @@ fts_close (FTS *sp) /* Linux-specific constants from coreutils' src/fs.h */ # define S_MAGIC_TMPFS 0x1021994 # define S_MAGIC_NFS 0x6969 +# define S_MAGIC_REISERFS 0x52654973 +# define S_MAGIC_PROC 0x9FA0 /* Return false if it is easy to determine the file system type of the directory on which DIR_FD is open, and sorting dirents on @@ -672,10 +678,127 @@ dirent_inode_sort_may_be_useful (int dir_fd) return true; } } + +/* Given a file descriptor DIR_FD open on a directory D, + return true if it is valid to apply the leaf-optimization + technique of counting directories in D via stat.st_nlink. */ +static bool +leaf_optimization_applies (int dir_fd) +{ + struct statfs fs_buf; + + /* If fstatfs fails, assume we can't use the optimization. */ + if (fstatfs (dir_fd, &fs_buf) != 0) + return false; + + /* FIXME: do we need to detect AFS mount points? I doubt it, + unless fstatfs can report S_MAGIC_REISERFS for such a directory. */ + + switch (fs_buf.f_type) + { + /* List here the file system types that lack useable dirent.d_type + info, yet for which the optimization does apply. */ + case S_MAGIC_REISERFS: + return true; + + case S_MAGIC_PROC: + /* Explicitly listing this or any other file system type for which + the optimization is not applicable is not necessary, but we leave + it here to document the risk. Per http://bugs.debian.org/143111, + /proc may have bogus stat.st_nlink values. */ + /* fall through */ + default: + return false; + } +} + #else static bool dirent_inode_sort_may_be_useful (int dir_fd) { return true; } +static bool leaf_optimization_applies (int dir_fd) { return false; } #endif +/* link-count-optimization entry: + map an stat.st_dev number to a boolean: leaf_optimization_works */ +struct LCO_ent +{ + dev_t st_dev; + bool opt_ok; +}; + +/* Use a tiny initial size. If a traversal encounters more than + a few devices, the cost of growing/rehashing this table will be + rendered negligible by the number of inodes processed. */ +enum { LCO_HT_INITIAL_SIZE = 13 }; + +static size_t +LCO_hash (void const *x, size_t table_size) +{ + struct LCO_ent const *ax = x; + return (uintmax_t) ax->st_dev % table_size; +} + +static bool +LCO_compare (void const *x, void const *y) +{ + struct LCO_ent const *ax = x; + struct LCO_ent const *ay = y; + return ax->st_dev == ay->st_dev; +} + +/* Ask the same question as leaf_optimization_applies, but query + the cache first (FTS.fts_leaf_optimization_works_ht), and if necessary, + update that cache. */ +static bool +link_count_optimize_ok (FTSENT const *p) +{ + FTS *sp = p->fts_fts; + Hash_table *h = sp->fts_leaf_optimization_works_ht; + struct LCO_ent tmp; + struct LCO_ent *ent; + bool opt_ok; + struct LCO_ent *t2; + + /* If we're not in CWDFD mode, don't bother with this optimization, + since the caller is not serious about performance. */ + if (!ISSET(FTS_CWDFD)) + return false; + + /* map st_dev to the boolean, leaf_optimization_works */ + if (h == NULL) + { + h = sp->fts_leaf_optimization_works_ht + = hash_initialize (LCO_HT_INITIAL_SIZE, NULL, LCO_hash, + LCO_compare, free); + if (h == NULL) + return false; + } + tmp.st_dev = p->fts_statp->st_dev; + ent = hash_lookup (h, &tmp); + if (ent) + return ent->opt_ok; + + /* Look-up failed. Query directly and cache the result. */ + t2 = malloc (sizeof *t2); + if (t2 == NULL) + return false; + + /* Is it ok to perform the optimization in the dir, FTS_CWD_FD? */ + opt_ok = leaf_optimization_applies (sp->fts_cwd_fd); + t2->opt_ok = opt_ok; + t2->st_dev = p->fts_statp->st_dev; + + ent = hash_insert (h, t2); + if (ent == NULL) + { + /* insertion failed */ + free (t2); + return false; + } + fts_assert (ent == t2); + + return opt_ok; +} + /* * Special case of "/" at the end of the file name so that slashes aren't * appended which would cause file names to be written as "....//foo". @@ -836,7 +959,25 @@ check_for_dir: if (p->fts_info == FTS_NSOK) { if (p->fts_statp->st_size == FTS_STAT_REQUIRED) - p->fts_info = fts_stat(sp, p, false); + { + FTSENT *parent = p->fts_parent; + if (parent->fts_n_dirs_remaining == 0 + && ISSET(FTS_NOSTAT) + && ISSET(FTS_PHYSICAL) + && link_count_optimize_ok (parent)) + { + /* nothing more needed */ + } + else + { + p->fts_info = fts_stat(sp, p, false); + if (S_ISDIR(p->fts_statp->st_mode)) + { + if (parent->fts_n_dirs_remaining) + parent->fts_n_dirs_remaining--; + } + } + } else fts_assert (p->fts_statp->st_size == FTS_NO_STAT_REQUIRED); } @@ -1560,6 +1701,8 @@ err: memset(sbp, 0, sizeof(struct stat)); } if (S_ISDIR(sbp->st_mode)) { + p->fts_n_dirs_remaining = (sbp->st_nlink + - (ISSET(FTS_SEEDOT) ? 0 : 2)); if (ISDOT(p->fts_name)) { /* Command-line "." and ".." are real directories. */ return (p->fts_level == FTS_ROOTLEVEL ? FTS_D : FTS_DOT); diff --git a/lib/fts_.h b/lib/fts_.h index b9554f2bf..ad339cab5 100644 --- a/lib/fts_.h +++ b/lib/fts_.h @@ -1,6 +1,6 @@ /* Traverse a file hierarchy. - Copyright (C) 2004-2008 Free Software Foundation, Inc. + Copyright (C) 2004-2009 Free Software Foundation, Inc. This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by @@ -144,6 +144,15 @@ typedef struct { int fts_options; /* fts_open options, global flags */ # if GNULIB_FTS + /* Map a directory's device number to a boolean. The boolean is + true if for that file system (type determined by a single fstatfs + call per FS) st_nlink can be used to calculate the number of + sub-directory entries in a directory. + Using this table is an optimization that permits us to look up + file system type on a per-inode basis at the minimal cost of + calling fstatfs only once per traversed device. */ + struct hash_table *fts_leaf_optimization_works_ht; + union { /* This data structure is used if FTS_TIGHT_CYCLE_CHECK is specified. It records the directories between a starting @@ -192,6 +201,7 @@ typedef struct _ftsent { ptrdiff_t fts_level; /* depth (-1 to N) */ size_t fts_namelen; /* strlen(fts_name) */ + nlink_t fts_n_dirs_remaining; /* count down from st_nlink */ # define FTS_D 1 /* preorder directory */ # define FTS_DC 2 /* directory that causes cycles */ -- 2.11.0