From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 60590 invoked by alias); 31 May 2019 12:50:36 -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 60565 invoked by uid 89); 31 May 2019 12:50:36 -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=Oct, oct, 21pm, comparable X-HELO: mail-lf1-f66.google.com Received: from mail-lf1-f66.google.com (HELO mail-lf1-f66.google.com) (209.85.167.66) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Fri, 31 May 2019 12:50:33 +0000 Received: by mail-lf1-f66.google.com with SMTP id a25so7821539lfg.2 for ; Fri, 31 May 2019 05:50:33 -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=5rSXu5LUPZF31BiYOoLqBXpv6xQ1Q6zwa5qMX/QRRjk=; b=mg8XIkCAd4yIkvMWY6kTBgZBOpohZsrYjJEO4rRKV5cvgnoAWqrZO9C+tMZWGFCtsP SjEdy1vCe0vZ8KJEoqPFp6FSxKPO0t4FPLC0mZqrd9ICEfsdIyxjGvbAqi6lrzMWjZs9 8i+ZDqP10hlqaepR1NWmwDr5+1uV5kzRVRvhJcwcLSjKOibY7FS/T62Dm3U2wgkb9Ufs f8X7ams3YFfal608GhEXv4rZopom3LK75WmGNxPOa9+D1Xal/0jMRSRNZiicLpcKIEKY R8HoT1wbg42ve40JERnzmOWm8urHBG7nnxi51xCyiuFJV9+idBKkWCI5dWn0qA25JZc/ bDOg== 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> In-Reply-To: <999abc46-57c7-ccf9-b0c9-baf4c0686b16@suse.cz> From: Richard Biener Date: Fri, 31 May 2019 13:23: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-05/txt/msg02126.txt.bz2 On Wed, May 22, 2019 at 11: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 wrot= e: > >> > >> 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 wro= te: > >>>>>>>>>> +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 fprin= tf > >>>>>>>>> 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:0= 0 2001 > >>>>>>>> From: marxin > >>>>>>>> Date: Mon, 29 Oct 2018 09:38:21 +0100 > >>>>>>>> Subject: [PATCH] Sanitize equals and hash functions in hash-tabl= es. > >>>>>>>> > >>>>>>>> --- > >>>>>>>> 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_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_index= ); > >>>>>>>> hashval_t hash2 =3D hash_table_mod2 (hash, m_size_prime_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 than a si= mple > >>>>>>> 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 enable= d 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 disablemen= t 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 i= ts > >>>> 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 checki= ng > >>>> 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 agai= nst > >>> 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 >=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/pr= 63941.c -O2 -c > hash table checking failed: equal operator returns true for a pair of val= ues with a different hash value > during GIMPLE pass: lim > /home/marxin/Programming/gcc/gcc/testsuite/gcc.dg/torture/pr63941.c: In f= unction =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* c= onst&, unsigned int) > /home/marxin/Programming/gcc/gcc/hash-table.h:1040 > 0xe504ea hash_table::find_slot_with_h= ash(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. I can't reproduce this (but I have a slightly patched tree). Richard. > 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 ? > > Thanks, > Martin > > > I guess PR90450 is "real" indeed... > > > > Richard. > > > >> Martin > >> > >>> > >>> Richard. > >>> > >>>> > >>>> Jeff > >> >