From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 26451 invoked by alias); 29 Oct 2018 15:14:25 -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 25028 invoked by uid 89); 29 Oct 2018 15:14:25 -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=hast, H*M:b387 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; Mon, 29 Oct 2018 15:14:23 +0000 Received: from relay1.suse.de (unknown [195.135.220.254]) by mx1.suse.de (Postfix) with ESMTP id 63FADACC5; Mon, 29 Oct 2018 15:14:21 +0000 (UTC) Subject: Re: [PATCH][RFC] Sanitize equals and hash functions in hash-tables. To: Alexander Monakov Cc: gcc-patches@gcc.gnu.org, Nathan Sidwell , Jason Merrill , Jakub Jelinek , Paul Richard Thomas , Martin Jambor References: <23ffca95-6492-e609-aebb-bbdd83b5185d@suse.cz> From: =?UTF-8?Q?Martin_Li=c5=a1ka?= Message-ID: Date: Mon, 29 Oct 2018 15:56: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: Content-Type: multipart/mixed; boundary="------------2A9C8C3DBE5152F3D5B19D8D" X-IsSubscribed: yes X-SW-Source: 2018-10/txt/msg01832.txt.bz2 This is a multi-part message in MIME format. --------------2A9C8C3DBE5152F3D5B19D8D Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit Content-length: 2441 On 10/29/18 2:53 PM, Alexander Monakov wrote: > On Mon, 29 Oct 2018, Martin Liška wrote: >> My question is whether we want to have in GCC 9 time frame or should I wait with that? >> Does it worth implementing? > > This is cool, thanks! A few questions/comments on the patch. Hi. Thanks for support. > > I think there are places that use libiberty C-style hashtab (htab_t), would it > make sense to have this kind of checking for them as well? I think it's going > to be more complicated though, no need to do both in one step. Sure, that can be also added in the future! > > I would recommend to factor out the error reporting path into a separate > non-template function, e.g. hashtab_chk_error. See how qsort_chk_error > has "cold" and "noreturn" attributes and invokes problematic comparators: > the idea was that a developer can 'break qsort_chk_error' in GDB and then > easily step into broken comparators. I did so. > > Furthermore, it might be nice to investigate if the entire checking loop can > be factored out somehow into a non-template function to avoid having multiple > instantiations of it for different hashtable template parameters. Note that Jakub is preferring to enable the checking only in non-release builds. Thus I've guarded the checking with #if ENABLE_EXTRA_CHECKING. That said I won't care much about saving a binary size. The checking function is dependent on template arguments, so the avoidance is probably not possible. > > On my first attempt to submit qsort_chk, Richi asked how much it slows down > stage2, do you have some data on the cost of this hashtable checking? It does not survive bootstrap right now (too many cselib_find_slot failures). > > I think it is possible to optimize this a bit: instead of checking on > insertions, check on deletions and when destroying the table (with care to do > n^2/2 rather than n^2 tests). Although, such approach would miss errors on > hashtables that are never destroyed (leaked or deliberately not deleted). Interesting idea. Benefit of the current approach is that the ICE is triggered as soon as first bad element is inserted into a hast table. Which means it's easier to debug. One problem with the destruction is that one equals function is defined on: Descriptor::equal (Descriptor::value_type, Descriptor::compare_type). One can have a table where these are not equal and so that equals can't be called. Martin > > Alexander > --------------2A9C8C3DBE5152F3D5B19D8D 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: 2428 >From 9afc42d324820cc0fc8a8a8b2d9cccd218734d10 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..43adfac2dc0 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"); + 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) + && Descriptor::equal (*entry, comparable) + && hash != Descriptor::hash (*entry)) + 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 --------------2A9C8C3DBE5152F3D5B19D8D--