From 4cb826802413516852a89739454a73c7a6ad0bd8 Mon Sep 17 00:00:00 2001 From: Jim Meyering Date: Tue, 9 Dec 2008 08:49:41 +0100 Subject: 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. --- src/du.c | 73 +++++++++------------------------------------------------------- 1 file changed, 10 insertions(+), 63 deletions(-) (limited to 'src') 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); } -- cgit v1.2.3-70-g09d2