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

From: Jim Meyering <[email-masked]>
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.