From patchwork Wed Dec 28 12:46:20 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Alexandre Oliva X-Patchwork-Id: 1719822 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=qYjnKxec; 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 4NhrrH6VHyz23dZ for ; Wed, 28 Dec 2022 23:46:54 +1100 (AEDT) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 565D63858C66 for ; Wed, 28 Dec 2022 12:46:52 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 565D63858C66 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1672231612; bh=SznVbtpk0UZCxzIlwNSbUWfWRmg8LH5ID5puFhQOCYs=; h=To:Cc:Subject:References:Date:In-Reply-To:List-Id: List-Unsubscribe:List-Archive:List-Post:List-Help:List-Subscribe: From:Reply-To:From; b=qYjnKxec+mvrr0fVc6deAMJ0eoZ4DVwEpa82CkK7x+B530p7ylr39GmkdzLhpItfN GBlLFmhN6RJ4eNVUHY2nQThJEkUZdEbUJlVXlEGgltadACb6j6c/28cnj4FdeQhWdR xoUOXHef/Jtn4KVbHzLuzFLHAif3WeEvRlJdJ4C8= 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 5AB113858D33 for ; Wed, 28 Dec 2022 12:46:33 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 5AB113858D33 Received: from localhost (localhost.localdomain [127.0.0.1]) by filtered-rock.gnat.com (Postfix) with ESMTP id 21287116304; Wed, 28 Dec 2022 07:46:33 -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 jqewHsGVlnxu; Wed, 28 Dec 2022 07:46:33 -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 DD2D5116213; Wed, 28 Dec 2022 07:46:32 -0500 (EST) Received: from livre (livre.home [172.31.160.2]) by free.home (8.15.2/8.15.2) with ESMTPS id 2BSCkLkR743977 (version=TLSv1.3 cipher=TLS_AES_256_GCM_SHA384 bits=256 verify=NOT); Wed, 28 Dec 2022 09:46:22 -0300 To: Martin =?utf-8?b?TGnFoWth?= Cc: gcc-patches@gcc.gnu.org Subject: [16/17] check hash table counts at expand Organization: Free thinker, does not speak for AdaCore References: Date: Wed, 28 Dec 2022 09:46:20 -0300 In-Reply-To: ("Martin \=\?utf-8\?Q\?Li\=C5\=A1ka\=22's\?\= message of "Wed, 28 Dec 2022 09:50:11 +0100") 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 28, 2022, Martin Liška wrote: > I really like the verification code you added. It's quite similar to what > I added to hash-table.h: *nod* Prompted by your encouragement, I've combined the element count verification code with the verify() loop, and also added it to expand, where it can be done cheaply. Add cheap verification of element and deleted entry counts during expand and hash verify. Regstrapped on x86_64-linux-gnu. Ok to install? for gcc/ChangeLog * hash-table.h (expand): Check elements and deleted counts. (verify): Likewise. --- gcc/hash-table.h | 35 ++++++++++++++++++++++++++++------- 1 file changed, 28 insertions(+), 7 deletions(-) diff --git a/gcc/hash-table.h b/gcc/hash-table.h index 53507daae26c3..f4bda6102323e 100644 --- a/gcc/hash-table.h +++ b/gcc/hash-table.h @@ -805,19 +805,28 @@ hash_table::expand () hash_table_usage ().release_instance_overhead (this, sizeof (value_type) * osize); + size_t n_deleted = m_n_deleted; + m_entries = nentries; m_size = nsize; m_size_prime_index = nindex; m_n_elements -= m_n_deleted; m_n_deleted = 0; + size_t n_elements = m_n_elements; + value_type *p = oentries; do { value_type &x = *p; - if (!is_empty (x) && !is_deleted (x)) + if (is_empty (x)) + ; + else if (is_deleted (x)) + n_deleted--; + else { + n_elements--; value_type *q = find_empty_slot_for_expand (Descriptor::hash (x)); new ((void*) q) value_type (std::move (x)); /* After the resources of 'x' have been moved to a new object at 'q', @@ -829,6 +838,8 @@ hash_table::expand () } while (p < olimit); + gcc_checking_assert (!n_elements && !n_deleted); + if (!m_ggc) Allocator ::data_free (oentries); else @@ -1018,8 +1029,9 @@ hash_table return &m_entries[index]; } -/* Verify that all existing elements in th hash table which are - equal to COMPARABLE have an equal HASH value provided as argument. */ +/* Verify that all existing elements in the hash table which are + equal to COMPARABLE have an equal HASH value provided as argument. + Also check that the hash table element counts are correct. */ template class Allocator> @@ -1027,14 +1039,23 @@ void hash_table ::verify (const compare_type &comparable, hashval_t hash) { + size_t n_elements = m_n_elements; + size_t n_deleted = m_n_deleted; for (size_t i = 0; i < MIN (hash_table_sanitize_eq_limit, 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 (); + if (!is_empty (*entry)) + { + n_elements--; + if (is_deleted (*entry)) + n_deleted--; + else if (hash != Descriptor::hash (*entry) + && Descriptor::equal (*entry, comparable)) + hashtab_chk_error (); + } } + if (hash_table_sanitize_eq_limit >= m_size) + gcc_checking_assert (!n_elements && !n_deleted); } /* This function deletes an element with the given COMPARABLE value