From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 90607 invoked by alias); 7 Jun 2019 14:48: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 75660 invoked by uid 89); 7 Jun 2019 14:48:23 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-17.8 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-qt1-f180.google.com Received: from mail-qt1-f180.google.com (HELO mail-qt1-f180.google.com) (209.85.160.180) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Fri, 07 Jun 2019 14:48:13 +0000 Received: by mail-qt1-f180.google.com with SMTP id i34so2542622qta.6 for ; Fri, 07 Jun 2019 07:48:11 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=subject:to:cc:references:from:message-id:date:user-agent :mime-version:in-reply-to:content-language:content-transfer-encoding; bh=xYVO1LLKw++bXtxktiEjzgrmL4GnA/MeQ+DQTGJSx3o=; b=Yb0V/AzKwXeK9b9Vp6F8+T/5C5qrxWg+hwLcEUyw+9F3XhIKFiSrUm253/Yg5l4fh0 jlZRZC8+eLj/GvOGJYDXFgLiX4GbsoxflCpaJBTCRMfCIaQqw/3CcPjpZ4ZCayJR6NiS UleiEpkXYDNnkWKNfZA34sfrQgaQgLZSaJS5ADss80Bt6Swc/GLAPu2dRO7IwBDVzxYk LB7WNKiHEWbM3WaTANR/CKycZTuKYe8ECBXezwwDWQQxH2HtM+cexZdq4LW5jKfJjYCu PDjfTXuWN0MWxb4sQa9SkhPjwHUc2xXR3sJVit9FNi9aupSzraLTG1Ds7iwJWrbLfpxw /W5Q== Return-Path: Received: from [192.168.0.41] (75-166-109-122.hlrn.qwest.net. [75.166.109.122]) by smtp.gmail.com with ESMTPSA id b66sm1142558qkd.37.2019.06.07.07.48.07 (version=TLS1_3 cipher=AEAD-AES128-GCM-SHA256 bits=128/128); Fri, 07 Jun 2019 07:48:08 -0700 (PDT) Subject: Re: [PATCH][RFC] Sanitize equals and hash functions in hash-tables. To: =?UTF-8?Q?Martin_Li=c5=a1ka?= , Richard Biener Cc: Jeff Law , Jakub Jelinek , Alexander Monakov , GCC Patches , Nathan Sidwell , Jason Merrill , Paul Richard Thomas , Martin Jambor 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> From: Martin Sebor Message-ID: Date: Fri, 07 Jun 2019 14:48:00 -0000 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:60.0) Gecko/20100101 Thunderbird/60.3.1 MIME-Version: 1.0 In-Reply-To: Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit X-IsSubscribed: yes X-SW-Source: 2019-06/txt/msg00445.txt.bz2 On 6/7/19 6:13 AM, Martin Liška wrote: > On 6/7/19 2:09 PM, Richard Biener wrote: >> On Fri, Jun 7, 2019 at 2:03 PM Martin Liška wrote: >>> >>> On 6/7/19 10:57 AM, Richard Biener wrote: >>>> On Mon, Jun 3, 2019 at 3:35 PM Martin Liška wrote: >>>>> >>>>> On 6/1/19 12:06 AM, Jeff Law wrote: >>>>>> On 5/22/19 3:13 AM, Martin Liška wrote: >>>>>>> On 5/21/19 1:51 PM, Richard Biener wrote: >>>>>>>> On Tue, May 21, 2019 at 1:02 PM Martin Liška 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ška wrote: >>>>>>>>>>>> On 11/8/18 9:56 AM, Martin Liška wrote: >>>>>>>>>>>>> On 11/7/18 11:23 PM, Jeff Law wrote: >>>>>>>>>>>>>> On 10/30/18 6:28 AM, Martin Liška wrote: >>>>>>>>>>>>>>> On 10/30/18 11:03 AM, Jakub Jelinek wrote: >>>>>>>>>>>>>>>> On Mon, Oct 29, 2018 at 04:14:21PM +0100, Martin Liška 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 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.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) 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 == INSERT && m_size * 3 <= m_n_elements * 4) >>>>>>>>>>>>>>> expand (); >>>>>>>>>>>>>>> >>>>>>>>>>>>>>> - m_searches++; >>>>>>>>>>>>>>> +#if ENABLE_EXTRA_CHECKING >>>>>>>>>>>>>>> + if (insert == INSERT) >>>>>>>>>>>>>>> + verify (comparable, hash); >>>>>>>>>>>>>>> +#endif >>>>>>>>>>>>>>> >>>>>>>>>>>>>>> + m_searches++; >>>>>>>>>>>>>>> value_type *first_deleted_slot = NULL; >>>>>>>>>>>>>>> hashval_t index = hash_table_mod1 (hash, m_size_prime_index); >>>>>>>>>>>>>>> hashval_t hash2 = 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 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_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=87845 >>>>>>>>>>>>> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=87847 >>>>>>>>>>>> Hi. >>>>>>>>>>>> >>>>>>>>>>>> I've just added one more PR: >>>>>>>>>>>> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=90450 >>>>>>>>>>>> >>>>>>>>>>>> I'm sending updated version of the patch that provides a disablement 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 its >>>>>>>>>>> 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 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/hashing >>>>>>>>>> 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 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 >= 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: In function ‘fn1’: >>>>>>> /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_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-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 ... >>> >>> 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.. >> >> You missed the second occurance >> >> - m_searches++; >> + if (m_sanitize_eq_and_hash) >> + verify (comparable, hash); > > Yep ;) I've just install the patch. I think it breaks bootstrap with the error below. I don't see the error after reverting it so I'm pretty sure it has something to do with it. Martin g++ -std=gnu++98 -O0 -g3 -DIN_GCC -fPIC -fno-exceptions -fno-rtti -fasynchronous-unwind-tables -W -Wall -Wno-narrowing -Wwrite-strings -Wcast-qual -Wno-format -Wmissing-format-attribute -Woverloaded-virtual -pedantic -Wno-long-long -Wno-variadic-macros -Wno-overlength-strings -fno-common -DHAVE_CONFIG_H -DGENERATOR_FILE -fno-PIE -no-pie -o build/gencondmd \ build/gencondmd.o ../build-x86_64-pc-linux-gnu/libiberty/pic/libiberty.a /usr/bin/ld: build/gencondmd.o: in function `hashtab_chk_error()': /src/gcc/git-svn/gcc/hash-table.h:1022: undefined reference to `fancy_abort(char const*, int, char const*)' collect2: error: ld returned 1 exit status make[2]: *** [Makefile:2865: build/gencondmd] Error 1 Martin