From patchwork Wed Dec 28 12:50:26 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Alexandre Oliva X-Patchwork-Id: 1719825 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org Authentication-Results: legolas.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=2620:52:3:1:0:246e:9693:128c; helo=sourceware.org; envelope-from=gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: legolas.ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.a=rsa-sha256 header.s=default header.b=FOfXlufV; dkim-atps=neutral Received: from sourceware.org (server2.sourceware.org [IPv6:2620:52:3:1:0:246e:9693:128c]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (P-384) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4Nhrwv5L2xz23dc for ; Wed, 28 Dec 2022 23:50:55 +1100 (AEDT) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id A3B3A3858CDA for ; Wed, 28 Dec 2022 12:50:53 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org A3B3A3858CDA DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1672231853; bh=9AAKtjJuS6Nf76eh9BXvmE1MkZZ7t4J7QdWZmiYymXE=; h=To:Subject:References:Date:In-Reply-To:List-Id:List-Unsubscribe: List-Archive:List-Post:List-Help:List-Subscribe:From:Reply-To: From; b=FOfXlufVkt0MXC56jUCz4erKUUbJdZNLaLyRrhcxEY0bN1ccDDxJlcToaFNq/kWaD c7wmgBBBU+PwXCxpbg3MDAQuElHskibW3/KwEKaCj4pC2j0xAg+sIOTcxRqoR7m6RA BiscdQifOiopB/bHcDYee5zJoRdC4tr1abycBO0M= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from rock.gnat.com (rock.gnat.com [IPv6:2620:20:4000:0:a9e:1ff:fe9b:1d1]) by sourceware.org (Postfix) with ESMTPS id 859EE3858D33 for ; Wed, 28 Dec 2022 12:50:34 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 859EE3858D33 Received: from localhost (localhost.localdomain [127.0.0.1]) by filtered-rock.gnat.com (Postfix) with ESMTP id 598BF116316; Wed, 28 Dec 2022 07:50:34 -0500 (EST) X-Virus-Scanned: Debian amavisd-new at gnat.com Received: from rock.gnat.com ([127.0.0.1]) by localhost (rock.gnat.com [127.0.0.1]) (amavisd-new, port 10024) with LMTP id z2OgpBsHNfKc; Wed, 28 Dec 2022 07:50:34 -0500 (EST) Received: from free.home (tron.gnat.com [IPv6:2620:20:4000:0:46a8:42ff:fe0e:e294]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by rock.gnat.com (Postfix) with ESMTPS id 061F4116312; Wed, 28 Dec 2022 07:50:33 -0500 (EST) Received: from livre (livre.home [172.31.160.2]) by free.home (8.15.2/8.15.2) with ESMTPS id 2BSCoQ02744060 (version=TLSv1.3 cipher=TLS_AES_256_GCM_SHA384 bits=256 verify=NOT); Wed, 28 Dec 2022 09:50:26 -0300 To: gcc-patches@gcc.gnu.org Subject: [17/17] check hash table insertions Organization: Free thinker, does not speak for AdaCore References: Date: Wed, 28 Dec 2022 09:50:26 -0300 In-Reply-To: (Alexandre Oliva's message of "Tue, 27 Dec 2022 01:07:35 -0300") Message-ID: User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/26.3 (gnu/linux) MIME-Version: 1.0 X-Scanned-By: MIMEDefang 2.84 X-Spam-Status: No, score=-12.3 required=5.0 tests=BAYES_00, GIT_PATCH_0, KAM_DMARC_STATUS, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-Patchwork-Original-From: Alexandre Oliva via Gcc-patches From: Alexandre Oliva Reply-To: Alexandre Oliva Errors-To: gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org Sender: "Gcc-patches" On Dec 27, 2022, Alexandre Oliva wrote: > The number of bugs it revealed tells me that leaving callers in charge > of completing insertions is too error prone. I found this > verification code a bit too expensive to enable in general. Here's a relatively cheap, checking-only test to catch dangling inserts. I've noticed a number of potential problems in hash tables, of three kinds: insertion of entries that seem empty, dangling insertions, and lookups during insertions. These problems may all have the effect of replacing a deleted entry with one that seems empty, which may disconnect double-hashing chains involving that entry, and thus cause entries to go missing. This patch detects such problems by recording a pending insertion and checking that it's completed before other potentially-conflicting operations. The additional field is only introduced when checking is enabled. Regstrapped on x86_64-linux-gnu. Ok to install? for gcc/ChnageLog * hash-table.h (check_complete_insertion, check_insert_slot): New hash_table methods. (m_inserting_slot): New hash_table field. (begin, hash_table ctors, ~hash_table): Check previous insert. (expand, empty_slow, clear_slot, find_with_hash): Likewise. (remote_elt_with_hash, traverse_noresize): Likewise. (gt_pch_nx): Likewise. (find_slot_with_hash): Likewise. Record requested insert. --- gcc/hash-table.h | 63 +++++++++++++++++++++++++++++++++++++++++++++++++++--- 1 file changed, 60 insertions(+), 3 deletions(-) diff --git a/gcc/hash-table.h b/gcc/hash-table.h index f4bda6102323e..33753d04b7bdb 100644 --- a/gcc/hash-table.h +++ b/gcc/hash-table.h @@ -495,6 +495,7 @@ public: { if (Lazy && m_entries == NULL) return iterator (); + check_complete_insertion (); iterator iter (m_entries, m_entries + m_size); iter.slide (); return iter; @@ -551,8 +552,39 @@ private: Descriptor::mark_empty (v); } +public: + void check_complete_insertion () const + { +#if CHECKING_P + if (!m_inserting_slot) + return; + + gcc_checking_assert (m_inserting_slot >= &m_entries[0] + && m_inserting_slot < &m_entries[m_size]); + + if (!is_empty (*m_inserting_slot)) + m_inserting_slot = NULL; + else + gcc_unreachable (); +#endif + } + +private: + value_type *check_insert_slot (value_type *ret) + { +#if CHECKING_P + gcc_checking_assert (is_empty (*ret)); + m_inserting_slot = ret; +#endif + return ret; + } + +#if CHECKING_P + mutable value_type *m_inserting_slot; +#endif + /* Table itself. */ - typename Descriptor::value_type *m_entries; + value_type *m_entries; size_t m_size; @@ -607,6 +639,9 @@ hash_table::hash_table (size_t size, bool ggc, ATTRIBUTE_UNUSED, mem_alloc_origin origin MEM_STAT_DECL) : +#if CHECKING_P + m_inserting_slot (0), +#endif m_n_elements (0), m_n_deleted (0), m_searches (0), m_collisions (0), m_ggc (ggc), m_sanitize_eq_and_hash (sanitize_eq_and_hash) #if GATHER_STATISTICS @@ -639,6 +674,9 @@ hash_table::hash_table (const hash_table &h, ATTRIBUTE_UNUSED, mem_alloc_origin origin MEM_STAT_DECL) : +#if CHECKING_P + m_inserting_slot (0), +#endif m_n_elements (h.m_n_elements), m_n_deleted (h.m_n_deleted), m_searches (0), m_collisions (0), m_ggc (ggc), m_sanitize_eq_and_hash (sanitize_eq_and_hash) @@ -646,6 +684,8 @@ hash_table::hash_table (const hash_table &h, , m_gather_mem_stats (gather_mem_stats) #endif { + h.check_complete_insertion (); + size_t size = h.m_size; if (m_gather_mem_stats) @@ -675,6 +715,8 @@ template class Allocator> hash_table::~hash_table () { + check_complete_insertion (); + if (!Lazy || m_entries) { for (size_t i = m_size - 1; i < m_size; i--) @@ -778,6 +820,8 @@ template::expand () { + check_complete_insertion (); + value_type *oentries = m_entries; unsigned int oindex = m_size_prime_index; size_t osize = size (); @@ -853,6 +897,8 @@ template::empty_slow () { + check_complete_insertion (); + size_t size = m_size; size_t nsize = size; value_type *entries = m_entries; @@ -901,6 +947,8 @@ template::clear_slot (value_type *slot) { + check_complete_insertion (); + gcc_checking_assert (!(slot < m_entries || slot >= m_entries + size () || is_empty (*slot) || is_deleted (*slot))); @@ -927,6 +975,8 @@ hash_table if (Lazy && m_entries == NULL) m_entries = alloc_entries (size); + check_complete_insertion (); + #if CHECKING_P if (m_sanitize_eq_and_hash) verify (comparable, hash); @@ -976,6 +1026,8 @@ hash_table } if (insert == INSERT && m_size * 3 <= m_n_elements * 4) expand (); + else + check_complete_insertion (); #if CHECKING_P if (m_sanitize_eq_and_hash) @@ -1022,11 +1074,11 @@ hash_table { m_n_deleted--; mark_empty (*first_deleted_slot); - return first_deleted_slot; + return check_insert_slot (first_deleted_slot); } m_n_elements++; - return &m_entries[index]; + return check_insert_slot (&m_entries[index]); } /* Verify that all existing elements in the hash table which are @@ -1068,6 +1120,8 @@ void hash_table ::remove_elt_with_hash (const compare_type &comparable, hashval_t hash) { + check_complete_insertion (); + value_type *slot = find_slot_with_hash (comparable, hash, NO_INSERT); if (slot == NULL) return; @@ -1094,6 +1148,8 @@ hash_table::traverse_noresize (Argument argument) if (Lazy && m_entries == NULL) return; + check_complete_insertion (); + value_type *slot = m_entries; value_type *limit = slot + size (); @@ -1210,6 +1266,7 @@ template static void gt_pch_nx (hash_table *h) { + h->check_complete_insertion (); bool success = gt_pch_note_object (h->m_entries, h, hashtab_entry_note_pointers); gcc_checking_assert (success);