bug#6524: du now uses less than half as much memory, sometimes

[Jim Meyering]

Pádraig Brady wrote:
> On 27/06/10 23:09, Jim Meyering wrote:
>> FYI,
>> This is just a preliminary heads-up.  At least one detail must be
>> addressed before I push: I haven't written justification for the
>> change to hash.c (I confess that I don't remember -- parts of this
>> change date back to Dec 2008 ;-)
>
> I tried to test the speed of this compared to the original,
> but got a consistent abort() after doing:
>
> cd /other/dev/gcc
> cp -al gcc-4.5.0 gcc-4.5.0.hl
> cd ~/git/coreutils
> ./src/du -hs /other/dev/gcc
>
> Setting breakpoint at hash.c:1077 is just before it calls abort()
>   hash_find_entry (table=0x8060ac8, entry=0x810201dd, bucket_head=0xbfffef9c, 
> delete=false) at hash.c:788
>     di_ent_compare (x=0x810201dd, y=0x81fc7a95) == true
>
> shout if you need anything else.

Thank you for the quick testing!
So far I've been unable to spot the cause or to reproduce that, but since
the way the new code works depends on the range of inode number values,
that's not too surprising.  You have some very large inode numbers in
that hierarchy, and that's exercising code that is not run in my tests.

I ran this in a directory with a few hundred cloned/checked-out
source directories:

    for i in *; do echo $i; cp -al $i .k; /cu/src/du -hs $i || break;
      find .k -type d -exec chmod 700 '{}' + ; rm -rf .k;done

and du never aborted. (that was on an x86_64/F13 system)

What type of file system are you using?  How big is it?
Fedora 13?  i686 or x86_64?

It may help if you can print the "a" and "b" structs
that are compared in di_ent_compare.

If I haven't made a mistake in e.g., di_ent_hash, di_ent_compare,
decode_ptr, etc., then the trouble may be with hash.c itself, via its
rehashing algorithm.  The offending abort is essentially making this
assertion:

    We did a lookup for "entry" before the rehash, and it wasn't there.
    Now, after the rehash, determine which bucket "entry" hashes to,
    and by the way, if we find a matching entry in the table, then abort.

BTW, how did you build?
I used ./configure --enable-gcc-warnings --disable-nls --prefix=/p

For good measure I repeated the test above on an i686/F13 system.
Still no failure.

What is in your /other/dev/gcc/gcc-4.5.0 directory,
other than an unpacked official 4.5.0 tarball?
I tried to reproduce like this, on both tmpfs and ext4, and
on i686 and x86_64:

  mkdir gcc && cd gcc
  tar xf ../gcc-4.5.0.tar.bz2
  cp -al gcc-4.5.0 gcc-4.5.0.hl
  ...path-to-just-built/src/du -sh $PWD

It always succeeds like this:

  586M    /home/meyering/gcc