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

[Jeff Law <law@redhat.com>]

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?

jeff