From: Richard Biener <richard.guenther@gmail.com>
To: "Martin Liška" <mliska@suse.cz>
Cc: Jeff Law <law@redhat.com>, Jakub Jelinek <jakub@redhat.com>,
Alexander Monakov <amonakov@ispras.ru>,
GCC Patches <gcc-patches@gcc.gnu.org>,
Nathan Sidwell <nathan@acm.org>,
Jason Merrill <jason@redhat.com>,
Paul Richard Thomas <paul.richard.thomas@gmail.com>,
Martin Jambor <mjambor@suse.cz>
Subject: Re: [PATCH][RFC] Sanitize equals and hash functions in hash-tables.
Date: Tue, 21 May 2019 11:52:00 -0000 [thread overview]
Message-ID: <CAFiYyc2DCes7n=S2Hr1Bi0D4k-y75v3Z3cjtJZtjZtZtoySe_g@mail.gmail.com> (raw)
In-Reply-To: <da052a95-6d5d-2b6c-ffce-d3f92a4ae1ac@suse.cz>
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
>
next prev parent reply other threads:[~2019-05-21 11:52 UTC|newest]
Thread overview: 53+ messages / expand[flat|nested] mbox.gz Atom feed top
2018-10-29 12:02 Martin Liška
2018-10-29 14:28 ` Alexander Monakov
2018-10-29 15:56 ` Martin Liška
2018-10-30 10:32 ` Jakub Jelinek
2018-10-30 14:17 ` Martin Liška
2018-11-07 22:24 ` Jeff Law
2018-11-07 22:44 ` Jakub Jelinek
2018-11-08 8:56 ` Martin Liška
2019-05-13 7:42 ` Martin Liška
2019-05-20 17:26 ` Jason Merrill
2019-05-20 22:07 ` Jeff Law
2019-05-21 9:38 ` Richard Biener
2019-05-21 11:02 ` Martin Liška
2019-05-21 11:52 ` Richard Biener [this message]
2019-05-22 9:13 ` Martin Liška
2019-05-31 13:23 ` Richard Biener
2019-05-31 13:35 ` Martin Liška
2019-05-31 22:10 ` Jeff Law
2019-06-03 13:35 ` Martin Liška
2019-06-07 8:57 ` Richard Biener
2019-06-07 12:04 ` Martin Liška
2019-06-07 12:09 ` Richard Biener
2019-06-07 12:13 ` Martin Liška
2019-06-07 14:48 ` Martin Sebor
2019-06-07 21:43 ` Jason Merrill
2019-06-10 7:08 ` Martin Liška
2019-06-10 18:22 ` Jason Merrill
2019-06-11 7:41 ` Martin Liška
2019-06-11 12:28 ` Jason Merrill
2019-06-11 13:16 ` Martin Liška
2019-06-11 19:02 ` Jason Merrill
2019-06-12 7:59 ` Richard Biener
2019-06-12 8:02 ` Martin Liška
2019-06-12 9:15 ` Martin Liška
2019-06-12 9:41 ` Richard Biener
2019-06-12 11:45 ` Martin Liška
2019-06-12 12:50 ` Richard Biener
2019-06-12 13:05 ` Martin Liška
2019-06-23 23:08 ` Ian Lance Taylor
2019-06-24 12:29 ` Richard Biener
2019-06-24 13:51 ` Martin Liška
2019-06-24 14:10 ` Richard Biener
2019-06-25 10:25 ` Martin Liška
2019-06-25 11:59 ` Martin Liška
2019-06-25 14:23 ` Richard Biener
2018-10-30 10:25 ` hash-table violation in cselib.c Martin Liška
2018-11-01 11:57 ` Martin Liška
2018-10-30 10:46 ` hash-table violation in gcc/fortran/trans-decl.c Martin Liška
2018-10-31 10:00 ` Trevor Saunders
2018-10-31 10:18 ` Martin Liška
2018-10-30 11:07 ` hash-table violation in gcc/cp/pt.c Martin Liška
2018-10-30 11:21 ` Martin Liška
2018-11-01 12:06 ` Martin Liška
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to='CAFiYyc2DCes7n=S2Hr1Bi0D4k-y75v3Z3cjtJZtjZtZtoySe_g@mail.gmail.com' \
--to=richard.guenther@gmail.com \
--cc=amonakov@ispras.ru \
--cc=gcc-patches@gcc.gnu.org \
--cc=jakub@redhat.com \
--cc=jason@redhat.com \
--cc=law@redhat.com \
--cc=mjambor@suse.cz \
--cc=mliska@suse.cz \
--cc=nathan@acm.org \
--cc=paul.richard.thomas@gmail.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).