From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 49991 invoked by alias); 30 Oct 2018 12:29:03 -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 48328 invoked by uid 89); 30 Oct 2018 12:29:02 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-26.9 required=5.0 tests=BAYES_00,GIT_PATCH_0,GIT_PATCH_1,GIT_PATCH_2,GIT_PATCH_3,SPF_PASS autolearn=ham version=3.3.2 spammy= X-HELO: mx1.suse.de Received: from mx2.suse.de (HELO mx1.suse.de) (195.135.220.15) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Tue, 30 Oct 2018 12:29:00 +0000 Received: from relay2.suse.de (unknown [195.135.220.254]) by mx1.suse.de (Postfix) with ESMTP id 91118B08A; Tue, 30 Oct 2018 12:28:58 +0000 (UTC) Subject: Re: [PATCH][RFC] Sanitize equals and hash functions in hash-tables. To: Jakub Jelinek Cc: Alexander Monakov , gcc-patches@gcc.gnu.org, Nathan Sidwell , Jason Merrill , Paul Richard Thomas , Martin Jambor References: <23ffca95-6492-e609-aebb-bbdd83b5185d@suse.cz> <20181030100342.GN11625@tucnak> From: =?UTF-8?Q?Martin_Li=c5=a1ka?= Message-ID: <32744d50-09fd-496c-e97e-9ec478d64ec4@suse.cz> Date: Tue, 30 Oct 2018 14:17:00 -0000 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:60.0) Gecko/20100101 Thunderbird/60.0 MIME-Version: 1.0 In-Reply-To: <20181030100342.GN11625@tucnak> Content-Type: multipart/mixed; boundary="------------AB7B63ECE84D17E01F3F3C9F" X-IsSubscribed: yes X-SW-Source: 2018-10/txt/msg01903.txt.bz2 This is a multi-part message in MIME format. --------------AB7B63ECE84D17E01F3F3C9F Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit Content-length: 584 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 > --------------AB7B63ECE84D17E01F3F3C9F Content-Type: text/x-patch; name="0001-Sanitize-equals-and-hash-functions-in-hash-tables.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename*0="0001-Sanitize-equals-and-hash-functions-in-hash-tables.patch" Content-length: 2430 >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 (); +} + +/* Verify that all existing elements in th hash table which are + equal to COMPARABLE have an equal HASH value provided as argument. */ + +template class Allocator> +void +hash_table +::verify (const compare_type &comparable, hashval_t hash) +{ + for (size_t i = 0; i < m_size; i++) + { + value_type *entry = &m_entries[i]; + if (!is_empty (*entry) && !is_deleted (*entry) + && hash != Descriptor::hash (*entry) + && Descriptor::equal (*entry, comparable)) + hashtab_chk_error (); + } +} +#endif + /* This function deletes an element with the given COMPARABLE value from hash table starting with the given HASH. If there is no matching element in the hash table, this function does nothing. */ -- 2.19.0 --------------AB7B63ECE84D17E01F3F3C9F--