From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 26659 invoked by alias); 24 Jun 2019 14:10:16 -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 26600 invoked by uid 89); 24 Jun 2019 14:10:15 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-14.6 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= X-HELO: mail-lf1-f68.google.com Received: from mail-lf1-f68.google.com (HELO mail-lf1-f68.google.com) (209.85.167.68) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Mon, 24 Jun 2019 14:10:11 +0000 Received: by mail-lf1-f68.google.com with SMTP id b11so10176052lfa.5 for ; Mon, 24 Jun 2019 07:10:10 -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=teD/dZcSHAEhmforLMHCMQPY395IpJT+l1upV/0jw1g=; b=JZ05/4Hv855vghjSntW+yKRYFy/OJgpA4gFgsuNxGHr79/0dQmo+7SxAWpNRdaoYsb AjCCDrYaP96EVhK6RHOPUOExk+IgBRS0kb7tEplHFHcEueYLDFvZV0I7L3TOoDSLXsTp NhFS82OMPuDca/FvBDJDI3uDCgWcYJkQ99btA3n/BsX742gLd+M9DCMCZN5hdZyqkTyG cyGmA02bF4IV8TPVREOt4wlMSZe3kqPxHzge+YKXVPOpwsBfmuOXkmDyLizTpxa7y3wC iDCdA9N5GSc5jscGeCuQ8YsYC0e8pAc/gqUBwGU124maX5Ww0k1t9pU10s6ZHmFb7SVl jKPA== 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> <4e546ac2-bb41-42bd-6b12-72e4f5c08d5d@suse.cz> In-Reply-To: <4e546ac2-bb41-42bd-6b12-72e4f5c08d5d@suse.cz> From: Richard Biener Date: Mon, 24 Jun 2019 14:10: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: Ian Lance Taylor , 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/msg01453.txt.bz2 On Mon, Jun 24, 2019 at 3:51 PM Martin Li=C5=A1ka wrote: > > On 6/24/19 2:29 PM, Richard Biener wrote: > > On Mon, Jun 24, 2019 at 1:08 AM Ian Lance Taylor wrot= e: > >> > >> On Fri, Jun 7, 2019 at 5:04 AM Martin Li=C5=A1ka wrot= e: > >>> > >>> On 6/7/19 10:57 AM, Richard Biener wrote: > >>>> On Mon, Jun 3, 2019 at 3:35 PM Martin Li=C5=A1ka wr= ote: > >>>>> > >>>>> 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 wro= te: > >>>>>>>>>>> > >>>>>>>>>>> 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 usin= g 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.pa= tch > >>>>>>>>>>>>>>> > >>>>>>>>>>>>>>> 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 ha= sh-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_elemen= ts * 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_prim= e_index); > >>>>>>>>>>>>>>> hashval_t hash2 =3D hash_table_mod2 (hash, m_size_prim= e_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 th= an 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_C= HECKING > >>>>>>>>>>>>>> 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 dis= ablement for the 3 PRs > >>>>>>>>>>>> with a new function disable_sanitize_eq_and_hash. > >>>>>>>>>>>> > >>>>>>>>>>>> With that I can bootstrap and finish tests. However, I've do= ne 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 hug= e 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/h= ashing > >>>>>>>>>> at lookup time, using the object from the lookup and verify th= at 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 in= serted) > >>>>>>>>> - new argument 'sanitize_eq_and_hash' added for hash_table::has= h_table > >>>>>>>>> - new param has been introduced hash-table-verification-limit i= n 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 opera= tions > >>>>>>> (both w/ and w/o insertion). > >>>>>>> > >>>>>>> Patch can bootstrap on x86_64-linux-gnu and survives regression t= ests > >>>>>>> except for: > >>>>>>> > >>>>>>> $ ./xgcc -B. /home/marxin/Programming/gcc/gcc/testsuite/gcc.dg/to= rture/pr63941.c -O2 -c > >>>>>>> hash table checking failed: equal operator returns true for a pai= r of values with a different hash value > >>>>>>> during GIMPLE pass: lim > >>>>>>> /home/marxin/Programming/gcc/gcc/testsuite/gcc.dg/torture/pr63941= .c: In 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(a= o_ref* const&, unsigned int) > >>>>>>> /home/marxin/Programming/gcc/gcc/hash-table.h:1040 > >>>>>>> 0xe504ea hash_table::find_slo= t_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-lo= op-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 some= such? > >>>>> > >>>>> Good point, I've just adjusted that. > >>>>> > >>>>> Patch can bootstrap on x86_64-linux-gnu and survives regression tes= ts. > >>>>> > >>>>> Ready to be installed? > >>>> > >>>> Ugh, the cselib one is really bad. But I don't hold my breath for a= nyone > >>>> 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: =E2=80=98void > >> hashtab_chk_error()=E2=80=99 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. You still get one instance in each TU ... > 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 > >> > >> * hash-table.h (hashtab_chk_error): Add ATTRIBUTE_UNUSED. >