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: 37192 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a5d:4e01:0:0:0:0:0 with SMTP id p1csp1872625wrt; Wed, 28 Dec 2022 04:47:16 -0800 (PST) X-Google-Smtp-Source: AMrXdXtaRcQB7j8KeNRetxt8EyzfpafJLdOFrMWqeP83KuS+yj94sKt4CWrNCe6WXhkh+jEmKThI X-Received: by 2002:a17:906:345a:b0:7c0:eb33:892a with SMTP id d26-20020a170906345a00b007c0eb33892amr19417948ejb.77.1672231636768; Wed, 28 Dec 2022 04:47:16 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1672231636; cv=none; d=google.com; s=arc-20160816; b=P/Yjs6Y00VLUS9bqRhQbVeeGsFF6DFgCknNwaTt7muqv1VeKwSZxvq89CwIi2tFKd3 5HtOiNoqQQitQ6uvFv6D6Rjo6PBWcOQZNArlXlbS3LKYEIpGnyEQh7UXswzP/89BYWAY +yi0shzcx+Q56NTCwA9hx+ejlBcgtboCzVlBfzhP2SHRHcXQr2b45WL5uxjEdw6x1Ax9 GU5Anmhu7MGvE2m3R4azw9bj/odN0iR8F8NFPwXYBiWaS+GME4Qf4leRijqfKzDDmHR0 QjEplU3yD5XqBrU2ULMbEhvFMdFnuYZzvrtr14YBwiejOElWUc5tZbTqSVymwAdUyK2o 1G1Q== 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 :content-transfer-encoding:mime-version:user-agent:message-id :in-reply-to:date:references:organization:subject:cc:to:dmarc-filter :delivered-to:dkim-signature:dkim-filter; bh=SznVbtpk0UZCxzIlwNSbUWfWRmg8LH5ID5puFhQOCYs=; b=lqUV1yyBX3yHO576cISMz0mXJfJhHYnmp+/2ppsUCOajN7T0EtgdqfdFWyic5JuD6/ louiHOlWmR9OJaCeN+J56X0HXBl8DDtVsiDPwqqLV5HctN9ZO1zyQc1my9sCnDPNKDdq +gtvs99otBpAxszqfr8nO0w3WWFewv14U4stXjqEk+JVv5vId4xYUnva0meZoHhbe5GX 6Pz1Z0z8BDvULVqWflhV3x+G/E00pJ/IvGdyikjwa/bJc1YSa4AajiUxqJY4RSju7A3Z hvp1FgJQE+LAbBnXe6ZHJSlMfd1ZNBVqvxoFcJdvfUgZN6hLF7ljQ9Z+85vz8EZZApYL 2wbg== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b="O/+LXSSe"; 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 dt12-20020a170907728c00b00817f698091csi13208080ejc.301.2022.12.28.04.47.16 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 28 Dec 2022 04:47:16 -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="O/+LXSSe"; 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 8FDE33858D3C for ; Wed, 28 Dec 2022 12:47:15 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 8FDE33858D3C DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1672231635; 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=O/+LXSSekLka5MCb3+v3Cn3X132WU6MM5Guxx0xiuNnFzPnYAfaGOPfWLfrzaRoW9 nFSvvpSQEUK8db52HtU7J78ep/4wxfIVdSStB6Q/PgZq4zIUhkq7MCRC5UR1cuxBFy Epf0yD5xjwYN3VsdnXH0VGD9mgNTgaGzsjccn6us= 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+ouuuleilei=gmail.com@gcc.gnu.org Sender: "Gcc-patches" X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1753461960831163573?= X-GMAIL-MSGID: =?utf-8?q?1753461960831163573?= 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