From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 67131 invoked by alias); 10 Jun 2019 18:22:09 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Received: (qmail 67106 invoked by uid 89); 10 Jun 2019 18:22:09 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-16.6 required=5.0 tests=AWL,BAYES_00,GIT_PATCH_0,GIT_PATCH_1,GIT_PATCH_2,GIT_PATCH_3,KAM_SHORT,RCVD_IN_DNSWL_NONE autolearn=ham version=3.3.1 spammy= X-HELO: mail-ot1-f50.google.com Received: from mail-ot1-f50.google.com (HELO mail-ot1-f50.google.com) (209.85.210.50) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Mon, 10 Jun 2019 18:22:06 +0000 Received: by mail-ot1-f50.google.com with SMTP id d17so9245629oth.5 for ; Mon, 10 Jun 2019 11:22:06 -0700 (PDT) MIME-Version: 1.0 References: <23ffca95-6492-e609-aebb-bbdd83b5185d@suse.cz> <20181030100342.GN11625@tucnak> <32744d50-09fd-496c-e97e-9ec478d64ec4@suse.cz> <492d87a7-0210-0df3-f484-f126baa6866c@suse.cz> <47fcf0aa-4b89-5354-1b59-4e6c623f5c3a@suse.cz> <999abc46-57c7-ccf9-b0c9-baf4c0686b16@suse.cz> <4faef430-49cf-13bc-4bb2-858a72668ae6@suse.cz> <243b87c2-91e0-063d-0682-de232656beaa@suse.cz> <96a94055-1f19-e76a-5753-ec72b088f363@suse.cz> In-Reply-To: <96a94055-1f19-e76a-5753-ec72b088f363@suse.cz> From: Jason Merrill Date: Mon, 10 Jun 2019 18:22:00 -0000 Message-ID: Subject: Re: [PATCH][RFC] Sanitize equals and hash functions in hash-tables. To: =?UTF-8?Q?Martin_Li=C5=A1ka?= Cc: Richard Biener , Jeff Law , Jakub Jelinek , Alexander Monakov , GCC Patches , Nathan Sidwell , Paul Richard Thomas , Martin Jambor Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable X-IsSubscribed: yes X-SW-Source: 2019-06/txt/msg00569.txt.bz2 On Mon, Jun 10, 2019 at 3:08 AM Martin Li=C5=A1ka wrote: > On 6/7/19 11:43 PM, Jason Merrill wrote: > > On Fri, Jun 7, 2019 at 8:14 AM Martin Li=C5=A1ka wrote: > >> On 6/7/19 2:09 PM, Richard Biener wrote: > >>> On Fri, Jun 7, 2019 at 2:03 PM Martin Li=C5=A1ka wro= te: > >>>> On 6/7/19 10:57 AM, Richard Biener wrote: > >>>>> On Mon, Jun 3, 2019 at 3:35 PM Martin Li=C5=A1ka w= rote: > >>>>>> On 6/1/19 12:06 AM, Jeff Law wrote: > >>>>>>> On 5/22/19 3:13 AM, Martin Li=C5=A1ka wrote: > >>>>>>>> On 5/21/19 1:51 PM, Richard Biener wrote: > >>>>>>>>> On Tue, May 21, 2019 at 1:02 PM Martin Li=C5=A1ka wrote: > >>>>>>>>>> > >>>>>>>>>> On 5/21/19 11:38 AM, Richard Biener wrote: > >>>>>>>>>>> On Tue, May 21, 2019 at 12:07 AM Jeff Law wr= ote: > >>>>>>>>>>>> > >>>>>>>>>>>> On 5/13/19 1:41 AM, Martin Li=C5=A1ka wrote: > >>>>>>>>>>>>> On 11/8/18 9:56 AM, Martin Li=C5=A1ka wrote: > >>>>>>>>>>>>>> On 11/7/18 11:23 PM, Jeff Law wrote: > >>>>>>>>>>>>>>> On 10/30/18 6:28 AM, Martin Li=C5=A1ka wrote: > >>>>>>>>>>>>>>>> On 10/30/18 11:03 AM, Jakub Jelinek wrote: > >>>>>>>>>>>>>>>>> On Mon, Oct 29, 2018 at 04:14:21PM +0100, Martin Li=C5= =A1ka 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 usi= ng 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.p= atch > >>>>>>>>>>>>>>>> > >>>>>>>>>>>>>>>> From 0d9c979c845580a98767b83c099053d36eb49bb9 Mon Sep 17= 00:00:00 2001 > >>>>>>>>>>>>>>>> From: marxin > >>>>>>>>>>>>>>>> Date: Mon, 29 Oct 2018 09:38:21 +0100 > >>>>>>>>>>>>>>>> Subject: [PATCH] Sanitize equals and hash functions in h= ash-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 > >>>>>>>>>>>>>>>> if (insert =3D=3D INSERT && m_size * 3 <=3D m_n_eleme= nts * 4) > >>>>>>>>>>>>>>>> expand (); > >>>>>>>>>>>>>>>> > >>>>>>>>>>>>>>>> - m_searches++; > >>>>>>>>>>>>>>>> +#if ENABLE_EXTRA_CHECKING > >>>>>>>>>>>>>>>> + if (insert =3D=3D INSERT) > >>>>>>>>>>>>>>>> + verify (comparable, hash); > >>>>>>>>>>>>>>>> +#endif > >>>>>>>>>>>>>>>> > >>>>>>>>>>>>>>>> + m_searches++; > >>>>>>>>>>>>>>>> value_type *first_deleted_slot =3D NULL; > >>>>>>>>>>>>>>>> hashval_t index =3D hash_table_mod1 (hash, m_size_pri= me_index); > >>>>>>>>>>>>>>>> hashval_t hash2 =3D hash_table_mod2 (hash, m_size_pri= me_index); > >>>>>>>>>>>>>>>> @@ -930,6 +935,39 @@ hash_table > >>>>>>>>>>>>>>>> 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 t= han a simple > >>>>>>>>>>>>>>> fprintf, even if the fprintf is terminated with a \n :-) > >>>>>>>>>>>>>> Fully agree with that, but I see a lot of build errors whe= n using internal_error. > >>>>>>>>>>>>>> > >>>>>>>>>>>>>>> The question then becomes can we bootstrap with this stuf= f 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=3D87845 > >>>>>>>>>>>>>> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=3D87847 > >>>>>>>>>>>>> Hi. > >>>>>>>>>>>>> > >>>>>>>>>>>>> I've just added one more PR: > >>>>>>>>>>>>> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=3D90450 > >>>>>>>>>>>>> > >>>>>>>>>>>>> I'm sending updated version of the patch that provides a di= sablement for the 3 PRs > >>>>>>>>>>>>> with a new function disable_sanitize_eq_and_hash. > >>>>>>>>>>>>> > >>>>>>>>>>>>> With that I can bootstrap and finish tests. However, I've d= one that with a patch > >>>>>>>>>>>>> limits maximal number of checks: > >>>>>>>>>>>> So rather than call the disable_sanitize_eq_and_hash, can yo= u have its > >>>>>>>>>>>> state set up when you instantiate the object? It's not a hu= ge deal, > >>>>>>>>>>>> just thinking about loud. > >>>>>>>>>>>> > >>>>>>>>>>>> > >>>>>>>>>>>> > >>>>>>>>>>>> So how do we want to go forward, particularly the EXTRA_EXTR= A 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 agains= t 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 t= hat 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 i= nserted) > >>>>>>>>>> - new argument 'sanitize_eq_and_hash' added for hash_table::ha= sh_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 >=3D 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 oper= ations > >>>>>>>> (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/t= orture/pr63941.c -O2 -c > >>>>>>>> hash table checking failed: equal operator returns true for a pa= ir of values with a different hash value > >>>>>>>> during GIMPLE pass: lim > >>>>>>>> /home/marxin/Programming/gcc/gcc/testsuite/gcc.dg/torture/pr6394= 1.c: In function =E2=80=98fn1=E2=80=99: > >>>>>>>> /home/marxin/Programming/gcc/gcc/testsuite/gcc.dg/torture/pr6394= 1.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::verify(= ao_ref* const&, unsigned int) > >>>>>>>> /home/marxin/Programming/gcc/gcc/hash-table.h:1040 > >>>>>>>> 0xe504ea hash_table::find_sl= ot_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-l= oop-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 som= esuch? > >>>>>> > >>>>>> Good point, I've just adjusted that. > >>>>>> > >>>>>> Patch can bootstrap on x86_64-linux-gnu and survives regression te= sts. > >>>>>> > >>>>>> 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) ca= ll > >>>>> 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 =E2=80=98hash_table > escription::mem_location_hash, mem_usage*, > > simple_hashmap_traits > ription::mem_location_hash>, mem_usage*> >::hash_entry, > > false, xcallocator>::hash_table(size_t&, bo\ > > ol&, bool&, mem_alloc_origin, const char*&, int&, const char*&)=E2=80=99 > > : 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? Jason