[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: fts: make find *much* faster on dirent.d_type-challenged FS
From: |
Jim Meyering |
Subject: |
Re: fts: make find *much* faster on dirent.d_type-challenged FS |
Date: |
Fri, 13 Feb 2009 09:09:07 +0100 |
Ralf Wildenhues <address@hidden> 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 <address@hidden>
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
- fts: make find *much* faster on dirent.d_type-challenged FS, Jim Meyering, 2009/02/12
- Re: fts: make find *much* faster on dirent.d_type-challenged FS, Ralf Wildenhues, 2009/02/13
- Re: fts: make find *much* faster on dirent.d_type-challenged FS,
Jim Meyering <=
- Re: fts: make find *much* faster on dirent.d_type-challenged FS, Simon Josefsson, 2009/02/13
- Re: fts: make find *much* faster on dirent.d_type-challenged FS, Karl Berry, 2009/02/13
- Re: fts: make find *much* faster on dirent.d_type-challenged FS, Eric Blake, 2009/02/13
- Re: fts: make find *much* faster on dirent.d_type-challenged FS, Matthew Woehlke, 2009/02/19
- Re: fts: make find *much* faster on dirent.d_type-challenged FS, Karl Berry, 2009/02/19