Ralf Wildenhues <ralf.wildenh...@gmx.de> wrote: ... > Nice speedup! A couple of comments, reading the patch:
Hi Ralf, Thanks for taking the time. >> diff --git a/lib/fts.c b/lib/fts.c >> index 164834c..735f23f 100644 >> --- a/lib/fts.c >> +++ b/lib/fts.c > >> + 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 documentat the risk. Per http://bugs.debian.org/143111, > > s/documentat/document/ Fixed. >> + /proc may have bogus stat.st_nlink values. */ >> + /* fall through */ > > >> +/* 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; >> + >> + /* 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 (sp->fts_leaf_optimization_works_ht == NULL) >> + { >> + sp->fts_leaf_optimization_works_ht >> + = hash_initialize (LCO_HT_INITIAL_SIZE, NULL, LCO_hash, >> + LCO_compare, free); >> + if (sp->fts_leaf_optimization_works_ht == NULL) >> + return false; >> + } >> + Hash_table *h = sp->fts_leaf_optimization_works_ht; > > Does this code need to be C89 compatible (several declaration after > statement here)? I vaguely recall feeling a slight twinge as I did that, but since coreutils proper has been using decl-after-stmt, for so long, I let it slide. However, this is gnulib, so I'll accommodate the slackers^W compiler-challenged for maybe a year more. Here's an incremental, then the adjusted full patch. BTW, I test this with coreutils by running chcon -R[*] on a directory containing 1000 files. With the patch, strace -c reports *1* calls to newfstatat, but without, it reports 1001 of them. [*] chcon -R is like "find . -print" in that it doesn't need to stat the non-directories it processes. diff --git a/lib/fts.c b/lib/fts.c index f293073..fdbe258 100644 --- a/lib/fts.c +++ b/lib/fts.c @@ -752,6 +752,11 @@ 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. */ @@ -759,39 +764,37 @@ link_count_optimize_ok (FTSENT const *p) return false; /* map st_dev to the boolean, leaf_optimization_works */ - if (sp->fts_leaf_optimization_works_ht == NULL) + if (h == NULL) { - sp->fts_leaf_optimization_works_ht + h = sp->fts_leaf_optimization_works_ht = hash_initialize (LCO_HT_INITIAL_SIZE, NULL, LCO_hash, LCO_compare, free); - if (sp->fts_leaf_optimization_works_ht == NULL) + if (h == NULL) return false; } - Hash_table *h = sp->fts_leaf_optimization_works_ht; - struct LCO_ent tmp; tmp.st_dev = p->fts_statp->st_dev; - struct LCO_ent *ent = hash_lookup (h, &tmp); + ent = hash_lookup (h, &tmp); if (ent) return ent->opt_ok; - int fd = p->fts_fts->fts_cwd_fd; - struct LCO_ent *t2 = malloc (sizeof *t2); + /* Look-up failed. Query directly and cache the result. */ + t2 = malloc (sizeof *t2); if (t2 == NULL) return false; - t2->st_dev = p->fts_statp->st_dev; - /* Is it ok to perform the optimization in the dir on which FD is open? */ - bool opt_ok = leaf_optimization_applies (fd); + /* 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; - struct LCO_ent *e = hash_insert (h, t2); - if (e == NULL) + ent = hash_insert (h, t2); + if (ent == NULL) { /* insertion failed */ free (t2); return false; } - fts_assert (e == t2); + fts_assert (ent == t2); return opt_ok; } >From 0879aea66243307f0e8df86c757a847494dbf54a Mon Sep 17 00:00:00 2001 From: Jim Meyering <meyer...@redhat.com> 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 *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. --- lib/fts.c | 145 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++- lib/fts_.h | 12 +++++- 2 files changed, 155 insertions(+), 2 deletions(-) diff --git a/lib/fts.c b/lib/fts.c index 164834c..fdbe258 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 b9554f2..ad339ca 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 */ -- 1.6.2.rc0.226.gf08f
