From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 123274 invoked by alias); 7 Jun 2019 08:57:55 -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 123265 invoked by uid 89); 7 Jun 2019 08:57:55 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-14.5 required=5.0 tests=AWL,BAYES_00,FREEMAIL_FROM,GIT_PATCH_0,GIT_PATCH_1,GIT_PATCH_2,GIT_PATCH_3,KAM_SHORT,RCVD_IN_DNSWL_NONE,SPF_PASS autolearn=ham version=3.3.1 spammy=H*Ad:U*amonakov, loud, vartrack X-HELO: mail-lj1-f178.google.com Received: from mail-lj1-f178.google.com (HELO mail-lj1-f178.google.com) (209.85.208.178) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Fri, 07 Jun 2019 08:57:52 +0000 Received: by mail-lj1-f178.google.com with SMTP id v29so1062326ljv.0 for ; Fri, 07 Jun 2019 01:57:51 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc:content-transfer-encoding; bh=EWf3MSt0/CBcMRZ36Ld7/lx49GazDPqh9PQwUMEsQMk=; b=Tug+pYjwuK/aJhQH6rndgA/QKNgWX2qn9/pCu/3vnz1kiOdBwk1xVI2Or51QUZoEJm 860+cCpWwlwJaISbfuXkA1l90zeJOEUGi5Ge3uwX+KPjRdcwMNS2phhbZAw5woLSo+Cu ysz8GmSf8rooMVtj4FthVJZ9D0+mTH2QjgdOwTSGxsv5ulFTe3P23E0ceHAHa8oj6/6K ocOjLusRNYsgM54cj/aSNOiRLqJ7mBwTIfF3ajd2SsVHUI+KahRDqn+PnWxqAlSnFf+Q EVYeFpkazkWRAIdmA9uRPkkvuzRDSGb/P4Tk8Mnz8anYAvvOHwJHAzOvu48bCmMfvO3C sAdQ== 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> In-Reply-To: <4faef430-49cf-13bc-4bb2-858a72668ae6@suse.cz> From: Richard Biener Date: Fri, 07 Jun 2019 08:57: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: Jeff Law , Jakub Jelinek , Alexander Monakov , GCC Patches , Nathan Sidwell , Jason Merrill , 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/msg00416.txt.bz2 On Mon, Jun 3, 2019 at 3:35 PM Martin Li=C5=A1ka wrote: > > 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 wr= ote: > >>>> > >>>> On 5/21/19 11:38 AM, Richard Biener wrote: > >>>>> On Tue, May 21, 2019 at 12:07 AM Jeff Law wrote: > >>>>>> > >>>>>> 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 w= rote: > >>>>>>>>>>>> +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 fpr= intf > >>>>>>>>>>> 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 > >>>>>>>>>> Date: Mon, 29 Oct 2018 09:38:21 +0100 > >>>>>>>>>> Subject: [PATCH] Sanitize equals and hash functions in hash-ta= bles. > >>>>>>>>>> > >>>>>>>>>> --- > >>>>>>>>>> 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) cons= t; > >>>>>>>>>> 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_elements * = 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_prime_ind= ex); > >>>>>>>>>> hashval_t hash2 =3D hash_table_mod2 (hash, m_size_prime_ind= ex); > >>>>>>>>>> @@ -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 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 usin= g internal_error. > >>>>>>>> > >>>>>>>>> The question then becomes can we bootstrap with this stuff enab= led 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_CHECKI= NG > >>>>>>>>> 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 disablem= ent 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 th= at 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 dea= l, > >>>>>> just thinking about loud. > >>>>>> > >>>>>> > >>>>>> > >>>>>> So how do we want to go forward, particularly the EXTRA_EXTRA chec= king > >>>>>> 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 anot= her > >>>>> 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 ag= ainst > >>>>> 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 inserte= d) > >>>> - new argument 'sanitize_eq_and_hash' added for hash_table::hash_tab= le > >>>> - new param has been introduced hash-table-verification-limit in ord= er > >>>> 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 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: I= n function =E2=80=98fn1=E2=80=99: > >> /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::verify(ao_ref= * const&, unsigned int) > >> /home/marxin/Programming/gcc/gcc/hash-table.h:1040 > >> 0xe504ea hash_table::find_slot_wit= h_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 ... 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 ;)). Thanks, Richard. > Thanks, > Martin > > > > > jeff > > >