bug-gnulib
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

fts: make find *much* faster on dirent.d_type-challenged FS


From: Jim Meyering
Subject: fts: make find *much* faster on dirent.d_type-challenged FS
Date: Thu, 12 Feb 2009 22:58:24 +0100

Following up on this thread,

  http://thread.gmane.org/gmane.comp.gnu.findutils.bugs/3894

Here are the gnulib pieces to make find stop stat'ing
non-directories on reiserfs file systems.
This makes find *sooo* much faster on some trees
(like my 1.7M-inode maildir one) that it's like night and day.
Before, disks would spin for 30minutes and totally hose performance
every morning while updatedb's find traversed my trees.  Now the same
job completes in minutes with almost no cache pressure.

I will test it a little more tomorrow, before pushing.



>From 86014dca17f984dbb6c8e66dfcce0f655f7bd3eb Mon Sep 17 00:00:00 2001
From: Jim Meyering <address@hidden>
Date: Wed, 11 Feb 2009 21:08:11 +0100
Subject: [PATCH 1/2] 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.
---
 lib/fts.c |   92 ++++++++++++++++++++++++++++++------------------------------
 1 files changed, 46 insertions(+), 46 deletions(-)

diff --git a/lib/fts.c b/lib/fts.c
index 017ccd5..164834c 100644
--- a/lib/fts.c
+++ b/lib/fts.c
@@ -1,6 +1,6 @@
 /* Traverse a file hierarchy.

-   Copyright (C) 2004, 2005, 2006, 2007, 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
@@ -631,6 +631,51 @@ fts_close (FTS *sp)
        return (0);
 }

+#if defined __linux__ \
+  && HAVE_SYS_VFS_H && HAVE_FSTATFS && HAVE_STRUCT_STATFS_F_TYPE
+
+#include <sys/vfs.h>
+
+/* Linux-specific constants from coreutils' src/fs.h */
+# define S_MAGIC_TMPFS 0x1021994
+# define S_MAGIC_NFS 0x6969
+
+/* 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
+   inode numbers is known not to improve traversal performance with
+   that type of file system.  Otherwise, return true.  */
+static bool
+dirent_inode_sort_may_be_useful (int dir_fd)
+{
+  /* Skip the sort only if we can determine efficiently
+     that skipping it is the right thing to do.
+     The cost of performing an unnecessary sort is negligible,
+     while the cost of *not* performing it can be O(N^2) with
+     a very large constant.  */
+  struct statfs fs_buf;
+
+  /* If fstatfs fails, assume sorting would be useful.  */
+  if (fstatfs (dir_fd, &fs_buf) != 0)
+    return true;
+
+  /* FIXME: what about when f_type is not an integral type?
+     deal with that if/when it's encountered.  */
+  switch (fs_buf.f_type)
+    {
+    case S_MAGIC_TMPFS:
+    case S_MAGIC_NFS:
+      /* On a file system of any of these types, sorting
+        is unnecessary, and hence wasteful.  */
+      return false;
+
+    default:
+      return true;
+    }
+}
+#else
+static bool dirent_inode_sort_may_be_useful (int dir_fd) { return true; }
+#endif
+
 /*
  * 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".
@@ -961,51 +1006,6 @@ fts_children (register FTS *sp, int instr)
        return (sp->fts_child);
 }

-#if defined __linux__ \
-  && HAVE_SYS_VFS_H && HAVE_FSTATFS && HAVE_STRUCT_STATFS_F_TYPE
-
-#include <sys/vfs.h>
-
-/* Linux-specific constants from coreutils' src/fs.h */
-# define S_MAGIC_TMPFS 0x1021994
-# define S_MAGIC_NFS 0x6969
-
-/* 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
-   inode numbers is known not to improve traversal performance with
-   that type of file system.  Otherwise, return true.  */
-static bool
-dirent_inode_sort_may_be_useful (int dir_fd)
-{
-  /* Skip the sort only if we can determine efficiently
-     that skipping it is the right thing to do.
-     The cost of performing an unnecessary sort is negligible,
-     while the cost of *not* performing it can be O(N^2) with
-     a very large constant.  */
-  struct statfs fs_buf;
-
-  /* If fstatfs fails, assume sorting would be useful.  */
-  if (fstatfs (dir_fd, &fs_buf) != 0)
-    return true;
-
-  /* FIXME: what about when f_type is not an integral type?
-     deal with that if/when it's encountered.  */
-  switch (fs_buf.f_type)
-    {
-    case S_MAGIC_TMPFS:
-    case S_MAGIC_NFS:
-      /* On a file system of any of these types, sorting
-        is unnecessary, and hence wasteful.  */
-      return false;
-
-    default:
-      return true;
-    }
-}
-#else
-static bool dirent_inode_sort_may_be_useful (int dir_fd) { return true; }
-#endif
-
 /* A comparison function to sort on increasing inode number.
    For some file system types, sorting either way makes a huge
    performance difference for a directory with very many entries,
--
1.6.2.rc0.226.gf08f


>From ed57db12fbd085014f4cc162ffb483151936b930 Mon Sep 17 00:00:00 2001
From: Jim Meyering <address@hidden>
Date: Wed, 11 Feb 2009 21:32:01 +0100
Subject: [PATCH 2/2] 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.

FIXME: see 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  |  142 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-
 lib/fts_.h |   12 +++++-
 2 files changed, 152 insertions(+), 2 deletions(-)

diff --git a/lib/fts.c b/lib/fts.c
index 164834c..735f23f 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,124 @@ 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 documentat 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;
+
+  /* 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;
+  struct LCO_ent tmp;
+  tmp.st_dev = p->fts_statp->st_dev;
+  struct LCO_ent *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);
+  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);
+  t2->opt_ok = opt_ok;
+
+  struct LCO_ent *e = hash_insert (h, t2);
+  if (e == NULL)
+    {
+      /* insertion failed */
+      free (t2);
+      return false;
+    }
+  fts_assert (e == 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 +956,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 +1698,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




reply via email to

[Prev in Thread] Current Thread [Next in Thread]