From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-lj1-x22d.google.com (mail-lj1-x22d.google.com [IPv6:2a00:1450:4864:20::22d]) by sourceware.org (Postfix) with ESMTPS id D00B93858D38 for ; Mon, 9 Jan 2023 07:47:00 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org D00B93858D38 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=gmail.com Received: by mail-lj1-x22d.google.com with SMTP id q2so8000333ljp.6 for ; Sun, 08 Jan 2023 23:47:00 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=content-transfer-encoding:cc:to:subject:message-id:date:from :in-reply-to:references:mime-version:from:to:cc:subject:date :message-id:reply-to; bh=DuRr3ukaclrDVLaLIc7IIg8TzMw1B+HDVyQnY47mzC0=; b=dBTIOKJDiPj/qB7tQQxy06Z/rbUipZoV2m1Kv7GL0/QeHEcp3lmbuo0XmXsO3YPwkY aWDoZZb1IrOiPZjoTOrjT+MoDAwBo+PYPCfS7sQMqTkzJxk5D5fz7FXhAjs9SiDZJUab NSV+V/E7+HvFA3FeKwx2BEQd8iNN3o7sU5TekFyqKXFieLtuZyH59CyiFs6Ykzv4KmbU blbXPmlHU9f22OPL26U27EIUeV/H1jS+kfrkq7chfB6AWkRZWpCUgIFy5BS5I1m1+F4z R7LMdISASDxHcjqa0PflpEZWlnXo059HSiuJLWYSs1GOpAOrmgxwaSb/yplHL/HOjvn0 QvdQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=content-transfer-encoding:cc:to:subject:message-id:date:from :in-reply-to:references:mime-version:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=DuRr3ukaclrDVLaLIc7IIg8TzMw1B+HDVyQnY47mzC0=; b=qt8P6PFJPOr5NMNvZxDnRpMLAF/4tq3P1uYjhezNvwxAzOrOGE86G5F4kbBMgSKHHa zw5GPTUqnsFqUkmVjNB+0uzf08L9QnDFrZ5oWkXEbTfXh9Jf8iKA0QV3nfaRNBSjs/ti mJdLrs8LLmB8Gxdl+kDXVaE9uJA+OWvwcPvZtDoBS31ceWXq71irCJrPRZF4WhV6Gob8 Y61KH7kwsN7bZlSJ9HZ7tzxE490ekBaDunQtz2aiJEP36LYQQpC6oeZ2QQXWXT9p5XAJ PQ+9W+Ziu/TsLUP1quUZYWWD8rbNmMPQjeBETvjQQFFcA2tvjc8kTXNqlqbG5cT1VAlC X87w== X-Gm-Message-State: AFqh2kpN2wrXcxfGJgggRbViFO4ekkcnM2cQ0SjKx2xcGHcd8G6bpIod NKAqQOS/Bp+PFa7YBHpP+5Q9vWecFw/Lu6SHACY= X-Google-Smtp-Source: AMrXdXs4pDfxU9D+tnfM20rG4jo9wqGsqhaxUmJPWBIllfXMZXeMexHx7Vb7lU/nSJi+m4DZ4CVsfE/OyQ3dhd3lPKU= X-Received: by 2002:a2e:2285:0:b0:285:d819:2b56 with SMTP id i127-20020a2e2285000000b00285d8192b56mr30527lji.467.1673250419269; Sun, 08 Jan 2023 23:46:59 -0800 (PST) MIME-Version: 1.0 References: In-Reply-To: From: Richard Biener Date: Mon, 9 Jan 2023 08:46:45 +0100 Message-ID: Subject: Re: [16/17] check hash table counts at expand To: Alexandre Oliva Cc: =?UTF-8?Q?Martin_Li=C5=A1ka?= , gcc-patches@gcc.gnu.org Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable X-Spam-Status: No, score=-7.3 required=5.0 tests=BAYES_00,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,FREEMAIL_FROM,GIT_PATCH_0,RCVD_IN_DNSWL_NONE,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 List-Id: On Wed, Dec 28, 2022 at 1:47 PM Alexandre Oliva via Gcc-patches wrote: > > On Dec 28, 2022, Martin Li=C5=A1ka wrote: > > > I really like the verification code you added. It's quite similar to wh= at > > 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? OK. > > 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_t= ype) > * osize); > > + size_t n_deleted =3D m_n_deleted; > + > m_entries =3D nentries; > m_size =3D nsize; > m_size_prime_index =3D nindex; > m_n_elements -=3D m_n_deleted; > m_n_deleted =3D 0; > > + size_t n_elements =3D m_n_elements; > + > value_type *p =3D oentries; > do > { > value_type &x =3D *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 =3D 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 a= t '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 template class Allocator> > @@ -1027,14 +1039,23 @@ void > hash_table > ::verify (const compare_type &comparable, hashval_t hash) > { > + size_t n_elements =3D m_n_elements; > + size_t n_deleted =3D m_n_deleted; > for (size_t i =3D 0; i < MIN (hash_table_sanitize_eq_limit, m_size); i= ++) > { > value_type *entry =3D &m_entries[i]; > - if (!is_empty (*entry) && !is_deleted (*entry) > - && hash !=3D 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 !=3D Descriptor::hash (*entry) > + && Descriptor::equal (*entry, comparable)) > + hashtab_chk_error (); > + } > } > + if (hash_table_sanitize_eq_limit >=3D m_size) > + gcc_checking_assert (!n_elements && !n_deleted); > } > > /* This function deletes an element with the given COMPARABLE value > > > -- > Alexandre Oliva, happy hacker https://FSFLA.org/blogs/lxo/ > Free Software Activist GNU Toolchain Engineer > Disinformation flourishes because many people care deeply about injustice > but very few check the facts. Ask me about