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: 37193 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a5d:4e01:0:0:0:0:0 with SMTP id p1csp1873841wrt; Wed, 28 Dec 2022 04:51:18 -0800 (PST) X-Google-Smtp-Source: AMrXdXtELOrsw3jNk+saL7l9GkxYyBDkqaSDGO2eJtAqDUPCvDxztUVRJ9XHvRARM1jrS3LvAaLB X-Received: by 2002:a05:6402:1819:b0:463:c960:7589 with SMTP id g25-20020a056402181900b00463c9607589mr20198656edy.40.1672231878627; Wed, 28 Dec 2022 04:51:18 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1672231878; cv=none; d=google.com; s=arc-20160816; b=C7g7XkMn4fCKQBuroiPMcDy9yJ6LvVD374e4q/gj3vlNmLNmQ5133GuHNH6kDz59AI v4TpzUVlADTSkv1tjF4LXQKeT6vh+6oL4VrlG1A8zXHUiWpweiUHX9ONUzSZSo5U5Arn 6ilS5vLFwZuYqSjWGRJ7PFpkhreudmiHya/SX8hxqh2AgDkcRRrqsofb6WGKBbLPWxdt k7nZr5c7p/H2DHBiLSFObU8zm6sRIG2lgpxt0ZS1jaTheBWlWg6gb44rQgI7/fkZ8X3z SImUWVWoZC8Bd8l3cvR1Y3Mc0E4Agfa6JSUbTF1eRcVNWwTLZJuYsE9rILYVFJf4KH96 oLLw== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=sender:errors-to:reply-to:from:list-subscribe:list-help:list-post :list-archive:list-unsubscribe:list-id:precedence:mime-version :user-agent:message-id:in-reply-to:date:references:organization :subject:to:dmarc-filter:delivered-to:dkim-signature:dkim-filter; bh=9AAKtjJuS6Nf76eh9BXvmE1MkZZ7t4J7QdWZmiYymXE=; b=F9ZqJqpOM2SNvXu0XxXwsa4ozuf3VoZG5OReQdn3jMBxubcdQNPQ0ezISubQOsEubA q0erX9iBfg4Yva9D5cY3ThZX55aiAwQnZNtsjbwHjGRfGI37Em5rZpDu2V6h5qzozcNL /fq2fKBlAU0hn3QkI9TJU+YKocZoMoGfU/CxhsSi0mgDkXmXnyB2Rvol00kw7AlLoE8n /FlN7hRXKW6DyeXCqw1KHLzKwdqWklpnw6VNpCs3lHwAgxIJi8NzgwkPd3amX1Av3pap 2f7yjVLAG6tYPXpJyBHcV1Jm8YAaIltmvGggrDVR8k/e42Nn4rLTdptcNH3D55bEJu7g qn8Q== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=ZOivGfFQ; spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 2620:52:3:1:0:246e:9693:128c as permitted sender) smtp.mailfrom="gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=gnu.org Received: from sourceware.org (server2.sourceware.org. [2620:52:3:1:0:246e:9693:128c]) by mx.google.com with ESMTPS id v18-20020a056402349200b0047b405e7746si14777235edc.1.2022.12.28.04.51.18 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 28 Dec 2022 04:51:18 -0800 (PST) Received-SPF: pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 2620:52:3:1:0:246e:9693:128c as permitted sender) client-ip=2620:52:3:1:0:246e:9693:128c; Authentication-Results: mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=ZOivGfFQ; spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 2620:52:3:1:0:246e:9693:128c as permitted sender) smtp.mailfrom="gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=gnu.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id E02563858D3C for ; Wed, 28 Dec 2022 12:51:16 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org E02563858D3C DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1672231876; 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=ZOivGfFQvzMAfE7kZTRw4yZOaz4Zbi870ttsaDujS+RZMV1TxqoJEegsLfp/9s7Be WbinoXwBp3LeRh7MzyhTnzfFGrz9QpsijzS5QX2VSbBODtP3u1c4snWGNvQpgatQJE hMgJeS7drpkFmUFa9p8inu1iFp+GCKQicp8X5H8E= 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+ouuuleilei=gmail.com@gcc.gnu.org Sender: "Gcc-patches" X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1753462213858171829?= X-GMAIL-MSGID: =?utf-8?q?1753462213858171829?= 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);