du: use less than half as much memory when tracking hard links

When processing a hard-linked file, du must keep track of the file's
device and inode numbers in order to avoid counting its storage
more than once.  When du would process many hard linked files --
as are created by some backup tools -- the amount of memory required
for the supporting data structure could become prohibitively large.
This patch takes advantage of the fact that the amount of information
in the numbers of the typical dev,inode pair is far less than even
32 bits, and hence usually fits in the space of a pointer, be it
32 or 64 bits wide.  A typical du traversal examines files on no
more than a handful of distinct devices, so the device number can
be encoded in just a few bits.  Similarly, few inode numbers use
all of the high bits in an ino_t.  Before, we would represent the
dev,inode pair using a naive struct, and allocate space for each.
Thus, an entry in the hash table consisted of a pointer (to that
struct) and a "next" pointer.  With this change, we encode the
dev,inode information and put those bits in place of the pointer,
and thus do away with the need to allocate additional space for
each dev,inode pair.

* src/du.c: Include "di-set.h".
Don't include "hash.h"; it's no longer used.
(INITIAL_DI_SET_SIZE): Define.
(di_set): New global, to replace "htab".
(entry_hash, entry_compare, hash_init): Remove functions.
(hash_ins): Use di-set functions, rather than ones from the hash module.
(main): Likewise.
* bootstrap.conf (gnulib_modules): Add the new di-set module.
* NEWS (New features): Mention it.

3 files changed, 15 insertions, 63 deletions

diff --git a/NEWS b/NEWS
index b02a2233c..82190d9ce 100644
--- a/NEWS
+++ b/NEWS
@@ -10,6 +10,10 @@ GNU coreutils NEWS                                    -*- outline -*-
   du recognizes -d N as equivalent to --max-depth=N, for compatibility
   with FreeBSD.
 
+  du now uses less than half as much memory when operating on trees
+  with many hard-linked files.  With --count-links (-l), or when
+  operating on trees with no hard-linked files, there is no change.
+
   sort now accepts the --debug option, to highlight the part of the
   line significant in the sort, and warn about questionable options.
 
diff --git a/bootstrap.conf b/bootstrap.conf
index 6e85c9a30..644c18b45 100644
--- a/bootstrap.conf
+++ b/bootstrap.conf
@@ -69,6 +69,7 @@ gnulib_modules="
   cycle-check
   d-ino
   d-type
+  di-set
   diacrit
   dirfd
   dirname
diff --git a/src/du.c b/src/du.c
index 4d6e03ae9..9a2585886 100644
--- a/src/du.c
+++ b/src/du.c
@@ -30,10 +30,10 @@
 #include "system.h"
 #include "argmatch.h"
 #include "argv-iter.h"
+#include "di-set.h"
 #include "error.h"
 #include "exclude.h"
 #include "fprintftime.h"
-#include "hash.h"
 #include "human.h"
 #include "quote.h"
 #include "quotearg.h"
@@ -61,18 +61,10 @@ extern bool fts_debug;
 #endif
 
 /* Initial size of the hash table.  */
-#define INITIAL_TABLE_SIZE 103
-
-/* Hash structure for inode and device numbers.  The separate entry
-   structure makes it easier to rehash "in place".  */
-struct entry
-{
-  ino_t st_ino;
-  dev_t st_dev;
-};
+enum { INITIAL_DI_SET_SIZE = 103 };
 
 /* A set of dev/ino pairs.  */
-static Hash_table *htab;
+static struct di_set_state di_set;
 
 /* Define a class for collecting directory information. */
 
@@ -339,66 +331,20 @@ Mandatory arguments to long options are mandatory for short options too.\n\
   exit (status);
 }
 
-static size_t
-entry_hash (void const *x, size_t table_size)
-{
-  struct entry const *p = x;
-
-  /* Ignoring the device number here should be fine.  */
-  /* The cast to uintmax_t prevents negative remainders
-     if st_ino is negative.  */
-  return (uintmax_t) p->st_ino % table_size;
-}
-
-/* Compare two dev/ino pairs.  Return true if they are the same.  */
-static bool
-entry_compare (void const *x, void const *y)
-{
-  struct entry const *a = x;
-  struct entry const *b = y;
-  return SAME_INODE (*a, *b) ? true : false;
-}
-
 /* Try to insert the INO/DEV pair into the global table, HTAB.
    Return true if the pair is successfully inserted,
    false if the pair is already in the table.  */
 static bool
 hash_ins (ino_t ino, dev_t dev)
 {
-  struct entry *ent;
-  struct entry *ent_from_table;
-
-  ent = xmalloc (sizeof *ent);
-  ent->st_ino = ino;
-  ent->st_dev = dev;
-
-  ent_from_table = hash_insert (htab, ent);
-  if (ent_from_table == NULL)
+  int inserted = di_set_insert (&di_set, dev, ino);
+  if (inserted < 0)
     {
       /* Insertion failed due to lack of memory.  */
       xalloc_die ();
     }
 
-  if (ent_from_table == ent)
-    {
-      /* Insertion succeeded.  */
-      return true;
-    }
-
-  /* That pair is already in the table, so ENT was not inserted.  Free it.  */
-  free (ent);
-
-  return false;
-}
-
-/* Initialize the hash table.  */
-static void
-hash_init (void)
-{
-  htab = hash_initialize (INITIAL_TABLE_SIZE, NULL,
-                          entry_hash, entry_compare, free);
-  if (htab == NULL)
-    xalloc_die ();
+  return inserted ? true : false;
 }
 
 /* FIXME: this code is nearly identical to code in date.c  */
@@ -958,8 +904,9 @@ main (int argc, char **argv)
   if (!ai)
     xalloc_die ();
 
-  /* Initialize the hash structure for inode numbers.  */
-  hash_init ();
+  /* Initialize the set of dev,inode pairs.  */
+  if (di_set_init (&di_set, INITIAL_DI_SET_SIZE))
+    xalloc_die ();
 
   bit_flags |= symlink_deref_bits;
   static char *temp_argv[] = { NULL, NULL };
@@ -1037,7 +984,7 @@ main (int argc, char **argv)
   if (print_grand_total)
     print_size (&tot_dui, _("total"));
 
-  hash_free (htab);
+  di_set_free (&di_set);
 
   exit (ok ? EXIT_SUCCESS : EXIT_FAILURE);
 }