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

[Richard Biener <richard dot guenther at gmail dot com>]

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.

I guess PR90450 is "real" indeed...

Richard.

> Martin
>
> >
> > Richard.
> >
> >>
> >> Jeff
>