From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 88462 invoked by alias); 23 Jun 2019 23:08:10 -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 88453 invoked by uid 89); 23 Jun 2019 23:08:10 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-25.8 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,SPF_PASS,USER_IN_DEF_SPF_WL autolearn=ham version=3.3.1 spammy=U*mliska, mliskasusecz, mliska@suse.cz, H*f:sk:CAFiYyc X-HELO: mail-vs1-f66.google.com Received: from mail-vs1-f66.google.com (HELO mail-vs1-f66.google.com) (209.85.217.66) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Sun, 23 Jun 2019 23:08:07 +0000 Received: by mail-vs1-f66.google.com with SMTP id l125so7385473vsl.13 for ; Sun, 23 Jun 2019 16:08:06 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=golang-org.20150623.gappssmtp.com; s=20150623; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=xf+KAtttGt0BWg4FI1VRy3TVhDHu3xRk4u/xapU4qMA=; b=AqgbzIeWbjLT4nRmI7YW+T+KKb4wZOcyHY6IeWEBigZqZKJw0EM3De7loljhoU/y2c qZyjrgGgQV+15MMUAkreemNvXv/eE28OejVPXAF4/U6ub0815LFMagpAWZy2f8p9Ga4Z VCDaaMejQTW8tVC1vySuYolTQ37oRlNUQLMaPD71Yop/ebOQvKM/W0vDt6QsH1zxw0Gz C6o0CmcfBrSCittTnWJhje4KCH7IiJCvbWstVXtAlYrnh9Efhx7/fZ0h4bgwFGV/Cain z/IKIcX5WIJmDjzkSPCFJm3pkyxSEZiILAamySZic1XVzbWtFGQIjBhlVAkHLGrdMaA/ QsvA== 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> In-Reply-To: <243b87c2-91e0-063d-0682-de232656beaa@suse.cz> From: Ian Lance Taylor Date: Sun, 23 Jun 2019 23:08: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 , Jason Merrill , Paul Richard Thomas , Martin Jambor Content-Type: multipart/mixed; boundary="000000000000a01b97058c05c47f" X-IsSubscribed: yes X-SW-Source: 2019-06/txt/msg01408.txt.bz2 --000000000000a01b97058c05c47f Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Content-length: 10850 On Fri, Jun 7, 2019 at 5:04 AM Martin Li=C5=A1ka wrote: > > On 6/7/19 10:57 AM, Richard Biener wrote: > > 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 = wrote: > >>>>>> > >>>>>> 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= 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 f= printf > >>>>>>>>>>>>> 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-= 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) co= nst; > >>>>>>>>>>>> value_type *find_empty_slot_for_expand (hashval_t); > >>>>>>>>>>>> + void verify (const compare_type &comparable, hashval_t ha= sh); > >>>>>>>>>>>> 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_i= ndex); > >>>>>>>>>>>> hashval_t hash2 =3D hash_table_mod2 (hash, m_size_prime_i= ndex); > >>>>>>>>>>>> @@ -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 us= ing internal_error. > >>>>>>>>>> > >>>>>>>>>>> The question then becomes can we bootstrap with this stuff en= abled 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_CHEC= KING > >>>>>>>>>>> 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 disabl= ement 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 ha= ve its > >>>>>>>> state set up when you instantiate the object? It's not a huge d= eal, > >>>>>>>> just thinking about loud. > >>>>>>>> > >>>>>>>> > >>>>>>>> > >>>>>>>> So how do we want to go forward, particularly the EXTRA_EXTRA ch= ecking > >>>>>>>> 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 an= other > >>>>>>> object (I guess that's usual even), but the setup is in a way tha= t the > >>>>>>> comparison function only works with those. With the patch we ver= ify > >>>>>>> hashing/comparison for something that is never used. > >>>>>>> > >>>>>>> So - wouldn't it be more "correct" to only verify comparison/hash= ing > >>>>>>> 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 inser= ted) > >>>>>> - new argument 'sanitize_eq_and_hash' added for hash_table::hash_t= able > >>>>>> - new param has been introduced hash-table-verification-limit in o= rder > >>>>>> 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 operatio= ns > >>>> (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/tortu= re/pr63941.c -O2 -c > >>>> hash table checking failed: equal operator returns true for a pair o= f 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(ao_r= ef* const&, unsigned int) > >>>> /home/marxin/Programming/gcc/gcc/hash-table.h:1040 > >>>> 0xe504ea hash_table::find_slot_w= ith_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 somesuc= h? > >> > >> 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 anyo= ne > > 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? Ian 2019-06-23 Ian Lance Taylor * hash-table.h (hashtab_chk_error): Add ATTRIBUTE_UNUSED. --000000000000a01b97058c05c47f Content-Type: text/plain; charset="US-ASCII"; name="patch.txt" Content-Disposition: attachment; filename="patch.txt" Content-Transfer-Encoding: base64 Content-ID: X-Attachment-Id: f_jx9kbcda0 Content-length: 529 SW5kZXg6IGhhc2gtdGFibGUuaAo9PT09PT09PT09PT09PT09PT09PT09PT09 PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09Ci0t LSBoYXNoLXRhYmxlLmgJKHJldmlzaW9uIDI3MjYwOSkKKysrIGhhc2gtdGFi bGUuaAkod29ya2luZyBjb3B5KQpAQCAtMTAxMiw3ICsxMDEyLDcgQEAgaGFz aF90YWJsZTxEZXNjcmlwdG9yLCBMYXp5LCBBbGxvY2F0b3I+CiAKIC8qIFJl cG9ydCBhIGhhc2ggdGFibGUgY2hlY2tpbmcgZXJyb3IuICAqLwogCi1BVFRS SUJVVEVfTk9SRVRVUk4gQVRUUklCVVRFX0NPTEQKK0FUVFJJQlVURV9OT1JF VFVSTiBBVFRSSUJVVEVfQ09MRCBBVFRSSUJVVEVfVU5VU0VECiBzdGF0aWMg dm9pZAogaGFzaHRhYl9jaGtfZXJyb3IgKCkKIHsK --000000000000a01b97058c05c47f--