Re: [PATCH][RFC] Sanitize equals and hash functions in hash-tables.

[Jason Merrill <jason@redhat.com>]

On Fri, Jun 7, 2019 at 8:14 AM Martin Liška <mliska@suse.cz> wrote:
>
> On 6/7/19 2:09 PM, Richard Biener wrote:
> > On Fri, Jun 7, 2019 at 2:03 PM Martin Liška <mliska@suse.cz> wrote:
> >>
> >> On 6/7/19 10:57 AM, Richard Biener wrote:
> >>> On Mon, Jun 3, 2019 at 3:35 PM Martin Liška <mliska@suse.cz> wrote:
> >>>>
> >>>> On 6/1/19 12:06 AM, Jeff Law wrote:
> >>>>> On 5/22/19 3:13 AM, Martin Liška wrote:
> >>>>>> On 5/21/19 1:51 PM, Richard Biener wrote:
> >>>>>>> On Tue, May 21, 2019 at 1:02 PM Martin Liška <mliska@suse.cz> wrote:
> >>>>>>>>
> >>>>>>>> On 5/21/19 11:38 AM, Richard Biener wrote:
> >>>>>>>>> On Tue, May 21, 2019 at 12:07 AM Jeff Law <law@redhat.com> wrote:
> >>>>>>>>>>
> >>>>>>>>>> On 5/13/19 1:41 AM, Martin Liška wrote:
> >>>>>>>>>>> On 11/8/18 9:56 AM, Martin Liška wrote:
> >>>>>>>>>>>> On 11/7/18 11:23 PM, Jeff Law wrote:
> >>>>>>>>>>>>> On 10/30/18 6:28 AM, Martin Liška wrote:
> >>>>>>>>>>>>>> On 10/30/18 11:03 AM, Jakub Jelinek wrote:
> >>>>>>>>>>>>>>> On Mon, Oct 29, 2018 at 04:14:21PM +0100, Martin Liška wrote:
> >>>>>>>>>>>>>>>> +hashtab_chk_error ()
> >>>>>>>>>>>>>>>> +{
> >>>>>>>>>>>>>>>> +  fprintf (stderr, "hash table checking failed: "
> >>>>>>>>>>>>>>>> +           "equal operator returns true for a pair "
> >>>>>>>>>>>>>>>> +           "of values with a different hash value");
> >>>>>>>>>>>>>>> BTW, either use internal_error here, or at least if using fprintf
> >>>>>>>>>>>>>>> terminate with \n, in your recent mail I saw:
> >>>>>>>>>>>>>>> ...different hash valueduring RTL pass: vartrack
> >>>>>>>>>>>>>>>                     ^^^^^^
> >>>>>>>>>>>>>> Sure, fixed in attached patch.
> >>>>>>>>>>>>>>
> >>>>>>>>>>>>>> Martin
> >>>>>>>>>>>>>>
> >>>>>>>>>>>>>>>> +  gcc_unreachable ();
> >>>>>>>>>>>>>>>> +}
> >>>>>>>>>>>>>>>   Jakub
> >>>>>>>>>>>>>>>
> >>>>>>>>>>>>>> 0001-Sanitize-equals-and-hash-functions-in-hash-tables.patch
> >>>>>>>>>>>>>>
> >>>>>>>>>>>>>> From 0d9c979c845580a98767b83c099053d36eb49bb9 Mon Sep 17 00:00:00 2001
> >>>>>>>>>>>>>> From: marxin <mliska@suse.cz>
> >>>>>>>>>>>>>> Date: Mon, 29 Oct 2018 09:38:21 +0100
> >>>>>>>>>>>>>> Subject: [PATCH] Sanitize equals and hash functions in hash-tables.
> >>>>>>>>>>>>>>
> >>>>>>>>>>>>>> ---
> >>>>>>>>>>>>>>  gcc/hash-table.h | 40 +++++++++++++++++++++++++++++++++++++++-
> >>>>>>>>>>>>>>  1 file changed, 39 insertions(+), 1 deletion(-)
> >>>>>>>>>>>>>>
> >>>>>>>>>>>>>> diff --git a/gcc/hash-table.h b/gcc/hash-table.h
> >>>>>>>>>>>>>> index bd83345c7b8..694eedfc4be 100644
> >>>>>>>>>>>>>> --- a/gcc/hash-table.h
> >>>>>>>>>>>>>> +++ b/gcc/hash-table.h
> >>>>>>>>>>>>>> @@ -503,6 +503,7 @@ private:
> >>>>>>>>>>>>>>
> >>>>>>>>>>>>>>    value_type *alloc_entries (size_t n CXX_MEM_STAT_INFO) const;
> >>>>>>>>>>>>>>    value_type *find_empty_slot_for_expand (hashval_t);
> >>>>>>>>>>>>>> +  void verify (const compare_type &comparable, hashval_t hash);
> >>>>>>>>>>>>>>    bool too_empty_p (unsigned int);
> >>>>>>>>>>>>>>    void expand ();
> >>>>>>>>>>>>>>    static bool is_deleted (value_type &v)
> >>>>>>>>>>>>>> @@ -882,8 +883,12 @@ hash_table<Descriptor, Allocator>
> >>>>>>>>>>>>>>    if (insert == INSERT && m_size * 3 <= m_n_elements * 4)
> >>>>>>>>>>>>>>      expand ();
> >>>>>>>>>>>>>>
> >>>>>>>>>>>>>> -  m_searches++;
> >>>>>>>>>>>>>> +#if ENABLE_EXTRA_CHECKING
> >>>>>>>>>>>>>> +    if (insert == INSERT)
> >>>>>>>>>>>>>> +      verify (comparable, hash);
> >>>>>>>>>>>>>> +#endif
> >>>>>>>>>>>>>>
> >>>>>>>>>>>>>> +  m_searches++;
> >>>>>>>>>>>>>>    value_type *first_deleted_slot = NULL;
> >>>>>>>>>>>>>>    hashval_t index = hash_table_mod1 (hash, m_size_prime_index);
> >>>>>>>>>>>>>>    hashval_t hash2 = hash_table_mod2 (hash, m_size_prime_index);
> >>>>>>>>>>>>>> @@ -930,6 +935,39 @@ hash_table<Descriptor, Allocator>
> >>>>>>>>>>>>>>    return &m_entries[index];
> >>>>>>>>>>>>>>  }
> >>>>>>>>>>>>>>
> >>>>>>>>>>>>>> +#if ENABLE_EXTRA_CHECKING
> >>>>>>>>>>>>>> +
> >>>>>>>>>>>>>> +/* Report a hash table checking error.  */
> >>>>>>>>>>>>>> +
> >>>>>>>>>>>>>> +ATTRIBUTE_NORETURN ATTRIBUTE_COLD
> >>>>>>>>>>>>>> +static void
> >>>>>>>>>>>>>> +hashtab_chk_error ()
> >>>>>>>>>>>>>> +{
> >>>>>>>>>>>>>> +  fprintf (stderr, "hash table checking failed: "
> >>>>>>>>>>>>>> +     "equal operator returns true for a pair "
> >>>>>>>>>>>>>> +     "of values with a different hash value\n");
> >>>>>>>>>>>>>> +  gcc_unreachable ();
> >>>>>>>>>>>>>> +}
> >>>>>>>>>>>>> I think an internal_error here is probably still better than a simple
> >>>>>>>>>>>>> fprintf, even if the fprintf is terminated with a \n :-)
> >>>>>>>>>>>> Fully agree with that, but I see a lot of build errors when using internal_error.
> >>>>>>>>>>>>
> >>>>>>>>>>>>> The question then becomes can we bootstrap with this stuff enabled and
> >>>>>>>>>>>>> if not, are we likely to soon?  It'd be a shame to put it into
> >>>>>>>>>>>>> EXTRA_CHECKING, but then not be able to really use EXTRA_CHECKING
> >>>>>>>>>>>>> because we've got too many bugs to fix.
> >>>>>>>>>>>> Unfortunately it's blocked with these 2 PRs:
> >>>>>>>>>>>> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=87845
> >>>>>>>>>>>> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=87847
> >>>>>>>>>>> Hi.
> >>>>>>>>>>>
> >>>>>>>>>>> I've just added one more PR:
> >>>>>>>>>>> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=90450
> >>>>>>>>>>>
> >>>>>>>>>>> I'm sending updated version of the patch that provides a disablement for the 3 PRs
> >>>>>>>>>>> with a new function disable_sanitize_eq_and_hash.
> >>>>>>>>>>>
> >>>>>>>>>>> With that I can bootstrap and finish tests. However, I've done that with a patch
> >>>>>>>>>>> limits maximal number of checks:
> >>>>>>>>>> So rather than call the disable_sanitize_eq_and_hash, can you have its
> >>>>>>>>>> state set up when you instantiate the object?  It's not a huge deal,
> >>>>>>>>>> just thinking about loud.
> >>>>>>>>>>
> >>>>>>>>>>
> >>>>>>>>>>
> >>>>>>>>>> So how do we want to go forward, particularly the EXTRA_EXTRA checking
> >>>>>>>>>> issue :-)
> >>>>>>>>>
> >>>>>>>>> There is at least one PR where we have a table where elements _in_ the
> >>>>>>>>> table are never compared against each other but always against another
> >>>>>>>>> object (I guess that's usual even), but the setup is in a way that the
> >>>>>>>>> comparison function only works with those.  With the patch we verify
> >>>>>>>>> hashing/comparison for something that is never used.
> >>>>>>>>>
> >>>>>>>>> So - wouldn't it be more "correct" to only verify comparison/hashing
> >>>>>>>>> at lookup time, using the object from the lookup and verify that against
> >>>>>>>>> all other elements?
> >>>>>>>>
> >>>>>>>> I don't a have problem with that. Apparently this changes fixes
> >>>>>>>> PR90450 and PR87847.
> >>>>>>>>
> >>>>>>>> Changes from previous version:
> >>>>>>>> - verification happens only when an element is searched (not inserted)
> >>>>>>>> - new argument 'sanitize_eq_and_hash' added for hash_table::hash_table
> >>>>>>>> - new param has been introduced hash-table-verification-limit in order
> >>>>>>>>   to limit number of elements that are compared within a table
> >>>>>>>> - verification happens only with flag_checking >= 2
> >>>>>>>>
> >>>>>>>> I've been bootstrapping and testing the patch right now.
> >>>>>>>
> >>>>>>> Looks like I misremembered the original patch.  The issue isn't
> >>>>>>> comparing random two elements in the table.
> >>>>>>>
> >>>>>>> That it fixes PR90450 is because LIM never calls find_slot_with_hash
> >>>>>>> without INSERTing.
> >>>>>>>
> >>>>>>
> >>>>>> There's updated version of the patch where I check all find operations
> >>>>>> (both w/ and w/o insertion).
> >>>>>>
> >>>>>> Patch can bootstrap on x86_64-linux-gnu and survives regression tests
> >>>>>> except for:
> >>>>>>
> >>>>>> $ ./xgcc -B. /home/marxin/Programming/gcc/gcc/testsuite/gcc.dg/torture/pr63941.c -O2 -c
> >>>>>> hash table checking failed: equal operator returns true for a pair of values with a different hash value
> >>>>>> during GIMPLE pass: lim
> >>>>>> /home/marxin/Programming/gcc/gcc/testsuite/gcc.dg/torture/pr63941.c: In function ‘fn1’:
> >>>>>> /home/marxin/Programming/gcc/gcc/testsuite/gcc.dg/torture/pr63941.c:6:1: internal compiler error: in hashtab_chk_error, at hash-table.h:1019
> >>>>>>     6 | fn1 ()
> >>>>>>       | ^~~
> >>>>>> 0x6c5725 hashtab_chk_error
> >>>>>>      /home/marxin/Programming/gcc/gcc/hash-table.h:1019
> >>>>>> 0xe504ea hash_table<mem_ref_hasher, false, xcallocator>::verify(ao_ref* const&, unsigned int)
> >>>>>>      /home/marxin/Programming/gcc/gcc/hash-table.h:1040
> >>>>>> 0xe504ea hash_table<mem_ref_hasher, false, xcallocator>::find_slot_with_hash(ao_ref* const&, unsigned int, insert_option)
> >>>>>>      /home/marxin/Programming/gcc/gcc/hash-table.h:960
> >>>>>> 0xe504ea gather_mem_refs_stmt
> >>>>>>      /home/marxin/Programming/gcc/gcc/tree-ssa-loop-im.c:1501
> >>>>>> 0xe504ea analyze_memory_references
> >>>>>>      /home/marxin/Programming/gcc/gcc/tree-ssa-loop-im.c:1625
> >>>>>> 0xe504ea tree_ssa_lim
> >>>>>>      /home/marxin/Programming/gcc/gcc/tree-ssa-loop-im.c:2646
> >>>>>> 0xe504ea execute
> >>>>>>      /home/marxin/Programming/gcc/gcc/tree-ssa-loop-im.c:2708
> >>>>>>
> >>>>>> Richi: it's after your recent patch.
> >>>>>>
> >>>>>> For some reason I don't see PR87847 issue any longer.
> >>>>>>
> >>>>>>
> >>>>>> May I install the patch with disabled sanitization in tree-ssa-loop-im.c ?
> >>>>> Don't we still need to deal with the naked fprintf when there's a
> >>>>> failure.  ie, shouldn't we be raising it with a gcc_assert or somesuch?
> >>>>
> >>>> Good point, I've just adjusted that.
> >>>>
> >>>> Patch can bootstrap on x86_64-linux-gnu and survives regression tests.
> >>>>
> >>>> Ready to be installed?
> >>>
> >>> Ugh, the cselib one is really bad.  But I don't hold my breath for anyone
> >>> fixing it ...
> >>
> >> Yes :D It's been some time and there's no interest in the PR.
> >>
> >>>
> >>> One question - there's unconditional
> >>>
> >>> +         if (m_sanitize_eq_and_hash)
> >>> +           verify (comparable, hash);
> >>>
> >>> which will read a global variable and have (possibly not inline) call
> >>> to verify on a common path even with checking disabled.  So I think
> >>> we want to compile this checking feature out for !CHECKING_P
> >>> or at least make the if __builtin_expect (..., 0), ::verify not
> >>> inlined and marked pure () (thus, !CHECKING_P is simplest ;)).
> >>
> >> Fixed. May I install the patch? The cselib issue can be solved later..
> >
> > You missed the second occurance
> >
> > -  m_searches++;
> > +  if (m_sanitize_eq_and_hash)
> > +    verify (comparable, hash);
>
> Yep ;) I've just install the patch.

This is breaking my build:

/home/jason/gt/gcc/hash-map.h:123:71: error: no matching function for
call to ‘hash_table<hash_map<mem_alloc_d\
escription<mem_usage>::mem_location_hash, mem_usage*,
simple_hashmap_traits<default_hash_traits<mem_alloc_desc\
ription<mem_usage>::mem_location_hash>, mem_usage*> >::hash_entry,
false, xcallocator>::hash_table(size_t&, bo\
ol&, bool&, mem_alloc_origin, const char*&, int&, const char*&)’
     : m_table (n, ggc, gather_mem_stats, HASH_MAP_ORIGIN PASS_MEM_STAT) {}

Looks like this needs to be updated to pass an argument to the new
sanitize_eq_and_hash parameter.

Jason