From: Jason Merrill <jason@redhat.com>
To: "Martin Liška" <mliska@suse.cz>
Cc: Richard Biener <richard.guenther@gmail.com>,
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>,
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, 11 Jun 2019 12:28:00 -0000 [thread overview]
Message-ID: <974d5683-57ee-8c42-af50-07d09803f085@redhat.com> (raw)
In-Reply-To: <69fd71c8-b459-3922-9517-2364740e845a@suse.cz>
On 6/11/19 3:41 AM, Martin Liška wrote:
> On 6/10/19 8:21 PM, Jason Merrill wrote:
>> On Mon, Jun 10, 2019 at 3:08 AM Martin Liška <mliska@suse.cz> wrote:
>>> On 6/7/19 11:43 PM, Jason Merrill wrote:
>>>> 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
>>>
>>> Sorry for the breakage, I've just fixed that in r272104.
>>
>> Thanks. I'm also seeing a massive compile time hit from this: A
>> constexpr testcase that I've been looking at went from compiling in 13
>> seconds to 78 seconds, 6 times as long. I would expect template-heavy
>> code to see similar problems when sanitization is enabled for those
>> hash tables. Could we keep the parameter low or 0 by default, and
>> just do occasional sanitize runs with it explicitly enabled?
>
> Makes sense to me. Can you please provide a test-case which I can measure?
This is the one I've been looking at:
struct Int {
constexpr Int(int v): v(v) {}
constexpr Int& operator+=(Int b) { this->v += b.v; return *this; }
constexpr Int& operator++() { ++this->v; return *this; }
private:
friend constexpr bool operator<(Int a, Int b) { return a.v < b.v; }
int v;
};
constexpr int f(int n) {
Int i = {0};
Int k = {0};
k = 0;
for (; k<10000; ++k) {
i += k;
}
return n;
}
template<int N> struct S {
static constexpr int sm = S<N-1>::sm+f(N);
};
template<> struct S<0> {
static constexpr int sm = 0;
};
constexpr int r = S<20>::sm;
Jason
next prev parent reply other threads:[~2019-06-11 12:28 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
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 [this message]
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=974d5683-57ee-8c42-af50-07d09803f085@redhat.com \
--to=jason@redhat.com \
--cc=amonakov@ispras.ru \
--cc=gcc-patches@gcc.gnu.org \
--cc=jakub@redhat.com \
--cc=law@redhat.com \
--cc=mjambor@suse.cz \
--cc=mliska@suse.cz \
--cc=nathan@acm.org \
--cc=paul.richard.thomas@gmail.com \
--cc=richard.guenther@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).