GNU bug report logs - #6551
[PATCH] hash: extend module to deal with non-pointer keys

Previous Next

To add a comment to this bug, you must first unarchive it, by sending
a message to control AT debbugs.gnu.org, with unarchive 6551 in the body.
You can then email your comments to 6551 AT debbugs.gnu.org in the normal way.

Toggle the display of automated, internal messages from the tracker.

Message #5 received at submit <at> debbugs.gnu.org (full text, mbox):

From: Paul Eggert <eggert <at> CS.UCLA.EDU>
To: Jim Meyering <jim <at> meyering.net>
Cc: bug-coreutils <at> gnu.org, bug-gnulib <at> gnu.org, 6524 <at> debbugs.gnu.org
Subject: Re: [PATCH] hash: extend module to deal with non-pointer keys
Date: Thu, 01 Jul 2010 15:39:32 -0700

Re the patch you just reported in:
<http://lists.gnu.org/archive/html/bug-gnulib/2010-07/msg00005.html>

I assume this is to support the du performance improvement that was proposed in
<http://debbugs.gnu.org/db/65/6524.html>.  I see that you incorporated a further
improvement in the gnulib patch, namely, support for NULL keys.

The gnulib change seems fine, but I noticed some problems with the coreutils
part of that earlier proposal.  Among other things, it makes du dump core on a
(large) test case that I have locally.  I don't know why (perhaps there
were further fixes to the gnulib part that I didn't get right?).  I found
out about the core dump only because I had independently prepared a patch
that I think is better: it uses a bit less memory and is quite a bit simpler.
I'll try to merge my patch with your gnulib change and send it off to
bug-coreutils in the next day or two.

My patch, by the way, doesn't hash pointer keys: it just uses size_t values
and casts them to void * (which is what the hash package wants).  This trick
works on all architectures that I know about, but it isn't guaranteed by
C or POSIX and the casts are a bit offputting, so it'd be nice if the hash
package supported hashing size_t keys directly.  That's lower priority, though.

Message #8 received at submit <at> debbugs.gnu.org (full text, mbox):

From: Jim Meyering <jim <at> meyering.net>
To: Paul Eggert <eggert <at> CS.UCLA.EDU>
Cc: bug-coreutils <at> gnu.org, bug-gnulib <at> gnu.org, 6524 <at> debbugs.gnu.org
Subject: Re: [PATCH] hash: extend module to deal with non-pointer keys
Date: Fri, 02 Jul 2010 00:59:09 +0200

Paul Eggert wrote:
> Re the patch you just reported in:
> <http://lists.gnu.org/archive/html/bug-gnulib/2010-07/msg00005.html>
>
> I assume this is to support the du performance improvement that was proposed in
> <http://debbugs.gnu.org/db/65/6524.html>.

Right.  That's the same as this:
http://thread.gmane.org/gmane.comp.gnu.coreutils.bugs/20857

> I see that you incorporated a further
> improvement in the gnulib patch, namely, support for NULL keys.
>
> The gnulib change seems fine, but I noticed some problems with the coreutils
> part of that earlier proposal.  Among other things, it makes du dump core on a
> (large) test case that I have locally.  I don't know why (perhaps there
> were further fixes to the gnulib part that I didn't get right?).  I found

Thanks for testing those.

Can you give me a backtrace?
Even if your patch is clearly better, I'd like to know
how my code is malfunctioning.

> out about the core dump only because I had independently prepared a patch
> that I think is better: it uses a bit less memory and is quite a bit simpler.
> I'll try to merge my patch with your gnulib change and send it off to
> bug-coreutils in the next day or two.
>
> My patch, by the way, doesn't hash pointer keys: it just uses size_t values
> and casts them to void * (which is what the hash package wants).  This trick
> works on all architectures that I know about, but it isn't guaranteed by
> C or POSIX and the casts are a bit offputting,

Using unions is one way to avoid casts (and certain warnings).

> so it'd be nice if the hash
> package supported hashing size_t keys directly.  That's lower priority, though.

Message #11 received at submit <at> debbugs.gnu.org (full text, mbox):

From: Paul Eggert <eggert <at> CS.UCLA.EDU>
To: Jim Meyering <jim <at> meyering.net>
Cc: bug-coreutils <at> gnu.org, bug-gnulib <at> gnu.org, 6524 <at> debbugs.gnu.org
Subject: Re: [PATCH] hash: extend module to deal with non-pointer keys
Date: Thu, 01 Jul 2010 17:07:00 -0700

On 07/01/10 15:59, Jim Meyering wrote:

> Can you give me a backtrace?
> Even if your patch is clearly better, I'd like to know
> how my code is malfunctioning.

Sure.  This uses your older patch, not the newer gnulib one.

Program received signal SIGABRT, Aborted.
0x0012d422 in __kernel_vsyscall ()
(gdb) where
#0  0x0012d422 in __kernel_vsyscall ()
#1  0x00158651 in *__GI_raise (sig=6) at ../nptl/sysdeps/unix/sysv/linux/raise.c:64
#2  0x0015ba82 in *__GI_abort () at abort.c:92
#3  0x08054826 in hash_insert0 (table=0x805f208, entry=0x8017384d, matched_ent=0x0) at hash.c:1078
#4  0x0804bdba in di_set_insert (dis=0x805e2f4, dev=2049, ino=380435) at di-set.c:264
#5  0x0804ab0f in hash_ins (argc=52, argv=0xbffff304) at du.c:335
#6  process_file (argc=52, argv=0xbffff304) at du.c:467
#7  du_files (argc=52, argv=0xbffff304) at du.c:592
#8  main (argc=52, argv=0xbffff304) at du.c:962

The test case, by the way, is "./du ../../cu*", where the
globbing pattern expands to 51 directories, each a copy of coreutils,
with several hard links because many are git clones of each other.
Arf arf!  (I'm eating my own dog food.)


> Using unions is one way to avoid casts (and certain warnings).

Yes; but ouch!  That's jumping into the fire!  I suspect it's even less
likely to work on weird architectures.  I'd rather stay in the frying pan.

Message #14 received at submit <at> debbugs.gnu.org (full text, mbox):

From: Jim Meyering <jim <at> meyering.net>
To: Paul Eggert <eggert <at> CS.UCLA.EDU>
Cc: bug-gnulib <at> gnu.org, bug-coreutils <at> gnu.org,
	Pádraig Brady <P <at> draigBrady.com>, 6524 <at> debbugs.gnu.org
Subject: Re: [PATCH] hash: extend module to deal with non-pointer keys
Date: Fri, 02 Jul 2010 12:58:50 +0200

Paul Eggert wrote:

> On 07/01/10 15:59, Jim Meyering wrote:
>
>> Can you give me a backtrace?
>> Even if your patch is clearly better, I'd like to know
>> how my code is malfunctioning.
>
> Sure.  This uses your older patch, not the newer gnulib one.

I think they're functionally equivalent.
The new one adds comments.

> Program received signal SIGABRT, Aborted.
> 0x0012d422 in __kernel_vsyscall ()
> (gdb) where
> #0  0x0012d422 in __kernel_vsyscall ()
> #1  0x00158651 in *__GI_raise (sig=6) at ../nptl/sysdeps/unix/sysv/linux/raise.c:64
> #2  0x0015ba82 in *__GI_abort () at abort.c:92
> #3  0x08054826 in hash_insert0 (table=0x805f208, entry=0x8017384d, matched_ent=0x0) at hash.c:1078
> #4  0x0804bdba in di_set_insert (dis=0x805e2f4, dev=2049, ino=380435) at di-set.c:264
> #5  0x0804ab0f in hash_ins (argc=52, argv=0xbffff304) at du.c:335
> #6  process_file (argc=52, argv=0xbffff304) at du.c:467
> #7  du_files (argc=52, argv=0xbffff304) at du.c:592
> #8  main (argc=52, argv=0xbffff304) at du.c:962
>
> The test case, by the way, is "./du ../../cu*", where the
> globbing pattern expands to 51 directories, each a copy of coreutils,
> with several hard links because many are git clones of each other.

Ouch.  That's the same assertion that Pádraig hit.  But he was
subsequently unable to reproduce it.  It indicates that when attempting
to insert the 2049,380435 dev,inode pair, hash_insert0 found that
the pair was not yet in the table, and that the table was too full,
so it first rehashed everything into a larger table, and then asserted
this:

    Since ENTRY was not in the initial table,
    it had better not be in the rehashed table.

That assertion failed, because somehow, ENTRY *was* in the new table.

Knowing the initial table size and the new one, given the above,
we might be able to determine what went wrong.

I have tried numerous times on both x86_64 and i686 to reproduce
it, but have never managed to trigger the failure.

Can you run "print *table" in gdb, say in hash_insert0?

Better still, set a conditional breakpoint in hash_insert0
to trigger when ENTRY == 0x8017384d (encoded version of 2049,380435),
and print the entire table using a variant of hash_print, step past
the rehash, and print the new table.

Message #17 received at submit <at> debbugs.gnu.org (full text, mbox):

From: Jim Meyering <jim <at> meyering.net>
To: Paul Eggert <eggert <at> CS.UCLA.EDU>
Cc: bug-coreutils <at> gnu.org, bug-gnulib <at> gnu.org, 6524 <at> debbugs.gnu.org
Subject: Re: [PATCH] hash: extend module to deal with non-pointer keys
Date: Fri, 02 Jul 2010 21:17:20 +0200

Paul Eggert wrote:

> On 07/01/10 15:59, Jim Meyering wrote:
>
>> Can you give me a backtrace?
>> Even if your patch is clearly better, I'd like to know
>> how my code is malfunctioning.
>
> Sure.  This uses your older patch, not the newer gnulib one.
>
> Program received signal SIGABRT, Aborted.
> 0x0012d422 in __kernel_vsyscall ()
> (gdb) where
> #0  0x0012d422 in __kernel_vsyscall ()
> #1  0x00158651 in *__GI_raise (sig=6) at ../nptl/sysdeps/unix/sysv/linux/raise.c:64
> #2  0x0015ba82 in *__GI_abort () at abort.c:92
> #3  0x08054826 in hash_insert0 (table=0x805f208, entry=0x8017384d, matched_ent=0x0) at hash.c:1078
> #4  0x0804bdba in di_set_insert (dis=0x805e2f4, dev=2049, ino=380435) at di-set.c:264
> #5  0x0804ab0f in hash_ins (argc=52, argv=0xbffff304) at du.c:335
> #6  process_file (argc=52, argv=0xbffff304) at du.c:467
> #7  du_files (argc=52, argv=0xbffff304) at du.c:592
> #8  main (argc=52, argv=0xbffff304) at du.c:962
>
> The test case, by the way, is "./du ../../cu*", where the
> globbing pattern expands to 51 directories, each a copy of coreutils,
> with several hard links because many are git clones of each other.
> Arf arf!  (I'm eating my own dog food.)

Thanks again for the report.
However, while I was able to reproduce it (on Paul's system)
and debug it, it appears to be due to a miscompilation of di-set.o
when using a private copy of gcc-4.5.0.  When I recompiled
that one file with gcc-Ubuntu 4.4.3-4ubuntu5 and -g -O2
or with 4.5.0 and -g -O, the code works as expected.

The problem arose in the di_ent_compare function and its use
of the tiny decode_ptr.  For the record, here they are:

    static struct di_ent
    decode_ptr (struct di_ent const *v)
    {
      if (!is_encoded_ptr (v))
        return *v;

      struct di_ent di;
      di.u.ptr = (void *) v;
      return di;
    }

    /* Compare two di_ent structs.
       Return true if they are the same.  */
    static bool
    di_ent_compare (void const *x, void const *y)
    {
      struct di_ent a = decode_ptr (x);
      struct di_ent b = decode_ptr (y);
      if (a.u.di4.mode != b.u.di4.mode)
        return false;

      if (a.u.di4.mode == DI_MODE_4)
        return (a.u.di4.short_ino == b.u.di4.short_ino
                && a.u.di4.mapped_dev == b.u.di4.mapped_dev);

      if (a.u.di8.mode == DI_MODE_8)
        return (a.u.di8.short_ino == b.u.di8.short_ino
                && a.u.di8.mapped_dev == b.u.di8.mapped_dev);

      return (a.u.full.ino == b.u.full.ino
              && a.u.full.dev == b.u.full.dev);
    }

Even though they're obviously distinct encoded values (see the
hexadecimal values below), di_ent_compare (aka table->comparator)
reports they're equal when using gcc-4.5.0 -g -O2, and that causes
the failed assertion:

    (gdb) p table->comparator (entry, bucket->data)
    $9 = true
    (gdb) p bucket->data
    $10 = (void *) 0x80143c4d
    (gdb) p entry
    $11 = (const void *) 0x80173851

I expect to push this series shortly.
Paul, if you end up improving further, you're welcome to revert
any pieces that are no longer used.

Message #20 received at submit <at> debbugs.gnu.org (full text, mbox):

From: Pádraig Brady <P <at> draigBrady.com>
To: Jim Meyering <jim <at> meyering.net>
Cc: bug-gnulib <at> gnu.org, Paul Eggert <eggert <at> CS.UCLA.EDU>, bug-coreutils <at> gnu.org,
	6524 <at> debbugs.gnu.org
Subject: Re: [PATCH] hash: extend module to deal with non-pointer keys
Date: Sun, 04 Jul 2010 23:43:33 +0100

On 02/07/10 20:17, Jim Meyering wrote:
> Thanks again for the report.
> However, while I was able to reproduce it (on Paul's system)
> and debug it, it appears to be due to a miscompilation of di-set.o
> when using a private copy of gcc-4.5.0.  When I recompiled
> that one file with gcc-Ubuntu 4.4.3-4ubuntu5 and -g -O2
> or with 4.5.0 and -g -O, the code works as expected.

I used a private gcc 4.5.0 also, and switched to
gcc 4.4.1 for debugging where I couldn't reproduce it
(gcc 4.5.0 produces debugging info with incompatible
line number info for my gdb (6.8.50)).

I had used gcc 4.5.0 to test -Wlogical-op with coreutils
which was also buggy unfortunately:
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=43772

I'll not be using that again.

cheers,
Pádraig.

Message #23 received at submit <at> debbugs.gnu.org (full text, mbox):

From: Jim Meyering <jim <at> meyering.net>
To: Pádraig Brady <P <at> draigBrady.com>
Cc: bug-coreutils <at> gnu.org, Paul Eggert <eggert <at> CS.UCLA.EDU>, bug-gnulib <at> gnu.org,
	6524 <at> debbugs.gnu.org
Subject: Re: [PATCH] hash: extend module to deal with non-pointer keys
Date: Mon, 05 Jul 2010 07:29:26 +0200

Pádraig Brady wrote:
> On 02/07/10 20:17, Jim Meyering wrote:
>> Thanks again for the report.
>> However, while I was able to reproduce it (on Paul's system)
>> and debug it, it appears to be due to a miscompilation of di-set.o
>> when using a private copy of gcc-4.5.0.  When I recompiled
>> that one file with gcc-Ubuntu 4.4.3-4ubuntu5 and -g -O2
>> or with 4.5.0 and -g -O, the code works as expected.
>
> I used a private gcc 4.5.0 also, and switched to
> gcc 4.4.1 for debugging where I couldn't reproduce it
> (gcc 4.5.0 produces debugging info with incompatible
> line number info for my gdb (6.8.50)).

I reported the code gen bug (i686-specific), and learned that
it's fixed on the trunk and for the upcoming 4.5.1:

    http://gcc.gnu.org/bugzilla/show_bug.cgi?id=44806

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.