From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 10394 invoked by alias); 11 Jun 2019 19:02:19 -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 10385 invoked by uid 89); 11 Jun 2019 19:02:19 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-18.5 required=5.0 tests=AWL,BAYES_00,GIT_PATCH_0,GIT_PATCH_1,GIT_PATCH_2,GIT_PATCH_3,KAM_ASCII_DIVIDERS,KAM_SHORT,RCVD_IN_DNSWL_NONE autolearn=ham version=3.3.1 spammy= X-HELO: mail-qk1-f178.google.com Received: from mail-qk1-f178.google.com (HELO mail-qk1-f178.google.com) (209.85.222.178) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Tue, 11 Jun 2019 19:02:16 +0000 Received: by mail-qk1-f178.google.com with SMTP id w187so8340616qkb.11 for ; Tue, 11 Jun 2019 12:02:16 -0700 (PDT) Return-Path: Received: from [192.168.1.116] (209-6-216-142.s141.c3-0.smr-cbr1.sbo-smr.ma.cable.rcncustomer.com. [209.6.216.142]) by smtp.gmail.com with ESMTPSA id o71sm8178363qke.18.2019.06.11.12.02.12 (version=TLS1_3 cipher=AEAD-AES128-GCM-SHA256 bits=128/128); Tue, 11 Jun 2019 12:02:13 -0700 (PDT) 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 , Paul Richard Thomas , Martin Jambor References: <23ffca95-6492-e609-aebb-bbdd83b5185d@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> <96a94055-1f19-e76a-5753-ec72b088f363@suse.cz> <69fd71c8-b459-3922-9517-2364740e845a@suse.cz> <974d5683-57ee-8c42-af50-07d09803f085@redhat.com> From: Jason Merrill Message-ID: Date: Tue, 11 Jun 2019 19:02:00 -0000 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:60.0) Gecko/20100101 Thunderbird/60.6.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/msg00653.txt.bz2 On 6/11/19 9:16 AM, Martin Liška wrote: > On 6/11/19 2:27 PM, Jason Merrill wrote: >> On 6/11/19 3:41 AM, Martin Liška wrote: >>> On 6/10/19 8:21 PM, Jason Merrill wrote: >>>> On Mon, Jun 10, 2019 at 3:08 AM Martin Liška wrote: >>>>> On 6/7/19 11:43 PM, Jason Merrill wrote: >>>>>> On Fri, Jun 7, 2019 at 8:14 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. >>>>>> >>>>>> This is breaking my build: >>>>>> >>>>>> /home/jason/gt/gcc/hash-map.h:123:71: error: no matching function for >>>>>> call to ‘hash_table>>>>> escription::mem_location_hash, mem_usage*, >>>>>> simple_hashmap_traits>>>>> ription::mem_location_hash>, mem_usage*> >::hash_entry, >>>>>> false, xcallocator>::hash_table(size_t&, bo\ >>>>>> ol&, bool&, mem_alloc_origin, const char*&, int&, const char*&)’ >>>>>>       : m_table (n, ggc, gather_mem_stats, HASH_MAP_ORIGIN PASS_MEM_STAT) {} >>>>>> >>>>>> Looks like this needs to be updated to pass an argument to the new >>>>>> sanitize_eq_and_hash parameter. >>>>>> >>>>>> Jason >>>>> >>>>> Sorry for the breakage, I've just fixed that in r272104. >>>> >>>> Thanks.  I'm also seeing a massive compile time hit from this:  A >>>> constexpr testcase that I've been looking at went from compiling in 13 >>>> seconds to 78 seconds, 6 times as long.  I would expect template-heavy >>>> code to see similar problems when sanitization is enabled for those >>>> hash tables.  Could we keep the parameter low or 0 by default, and >>>> just do occasional sanitize runs with it explicitly enabled? >>> >>> Makes sense to me. Can you please provide a test-case which I can measure? >> >> This is the one I've been looking at: >> >>   struct Int { >>     constexpr Int(int v): v(v) {} >>     constexpr Int& operator+=(Int b) { this->v += b.v; return *this; } >>     constexpr Int& operator++() { ++this->v; return *this; } >>   private: >>     friend constexpr bool operator<(Int a, Int b) { return a.v < b.v; } >>     int v; >>   }; >>   constexpr int f(int n) { >>     Int i = {0}; >>     Int k = {0}; >>     k = 0; >>     for (; k<10000; ++k) { >>       i += k; >>     } >>     return n; >>   } >> >>   template struct S { >>     static constexpr int sm = S::sm+f(N); >>   }; >>   template<> struct S<0> { >>     static constexpr int sm = 0; >>   }; >>   constexpr int r = S<20>::sm; >> >> Jason > > For the test-case provided I see: > > $ time g++ time.cc -c --param hash-table-verification-limit=100 > > real 0m1.855s > user 0m1.829s > sys 0m0.025s > > $ time g++ time.cc -c --param hash-table-verification-limit=0 > > real 0m1.275s > user 0m1.219s > sys 0m0.052s > > $ time g++-9 time.cc -c > > real 0m0.939s > user 0m0.827s > sys 0m0.109s > > So it's slower, but I can't confirm the huge slowdown you see. > Is it due to r272144? Hmm, I wonder if this is because of the --enable-gather-detailed-mem-stats hash tables. Jason