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

["Martin Liška" <mliska@suse.cz>]

On 6/24/19 2:29 PM, Richard Biener wrote:
> On Mon, Jun 24, 2019 at 1:08 AM Ian Lance Taylor <iant@golang.org> wrote:
>>
>> On Fri, Jun 7, 2019 at 5:04 AM 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..
>>
>> After this patch, when I do a configure with --disable-bootstrap, and
>> build with "gcc (Debian 7.3.0-18) 7.3.0", I get a lot of warnings of
>> the form
>>
>> In file included from ../../gccgo3/gcc/coretypes.h:440:0,
>>                  from ../../gccgo3/gcc/go/go-system.h:137,
>>                  from ../../gccgo3/gcc/go/gofrontend/go.cc:7:
>> ../../gccgo3/gcc/hash-table.h:1017:1: warning: ‘void
>> hashtab_chk_error()’ defined but not used [-Wunused-function]
>>  hashtab_chk_error ()
>>  ^~~~~~~~~~~~~~~~~
>>
>> These are just warnings, since I am using --disable-bootstrap, but
>> they are distracting.
>>
>> This patch fixes it.  OK for trunk?
> 
> Hmm, the function is called exactly once.  I guess the intent was
> to not emit the printf in every ::verify instance but then why not
> instantiate this function in just hash-table.c and not mark it inline?

I marked the function ATTRIBUTE_COLD, so it should not be inlined
into ::verify.

  1013  /* Report a hash table checking error.  */
  1014  
  1015  ATTRIBUTE_NORETURN ATTRIBUTE_COLD
  1016  static void
  1017  hashtab_chk_error ()
  1018  {
  1019    fprintf (stderr, "hash table checking failed: "
  1020             "equal operator returns true for a pair "
  1021             "of values with a different hash value\n");
  1022    gcc_unreachable ();
  1023  }

Martin

> 
> Richard.
> 
>>
>> Ian
>>
>> 2019-06-23  Ian Lance Taylor  <iant@golang.org>
>>
>> * hash-table.h (hashtab_chk_error): Add ATTRIBUTE_UNUSED.