From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-lj1-x233.google.com (mail-lj1-x233.google.com [IPv6:2a00:1450:4864:20::233]) by sourceware.org (Postfix) with ESMTPS id 90DFF3858D32 for ; Fri, 13 Jan 2023 07:20:14 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 90DFF3858D32 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-x233.google.com with SMTP id bx6so21674672ljb.3 for ; Thu, 12 Jan 2023 23:20:14 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:from:to:cc:subject:date:message-id:reply-to; bh=AZLCVe+kyEq3YOSSZLU6mWqfFnEfjXFvFSRYJznXNyY=; b=WGsc3m+YJ10veWr/3r8A0YkhNJNnUBxyH0Djxha4igVK8HzeNM1LRvq4GjNoXzcoSL y9YfoFZjVofi0KQPR+pJnVKsly/d0Tu7ZbIpHnuEAStd0aNDAH+8a1im9Z76zvFuf50e aa4j21zu7MHBxii79Db/6cNEqyIxDS5+F6wGRhm6jEo1FiDkrU3zWIgHmQIZjik97ycF fOrUSJSrtA+bq+If6zk9ZykLQ/Umr5yV4/8V0hOy8v538+yMeyRUQFsnGzakQ6QlKdnl Ph4BTe9IHgFd7c74efxQFW9mB+bUq7iACBBQjY67HnRqhQEMLRodceJyKyRy/rOSlEGG U2Lg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=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=AZLCVe+kyEq3YOSSZLU6mWqfFnEfjXFvFSRYJznXNyY=; b=uFYQAdpHIqJcbYx1JNFmWBip6PrUBF2W9FotWFJTrvEk+xQBBfFNL5w2iBmF+kFaVO hEmu76MfhrOnNrjvfWp0eU1f/Wn71zBTECm4zBWP5Psk6niIbeL2h2UZOUGghXEfXRBL WJaMZgYDqBvBHVUx7+aNA2Hlzrv6q+Y3wbL/IkLo0g8eh6a/YMN501gnDtyN8d0pZWSZ vt85wbGScXJxT9/fnp/hoJlkE531p9ralFw71WxByUE3Br+ws1CprU6fYLa7xwECzDps 8qosNpT7LulcmFyMN6gvt9cfiKPhgGri1Cj70crza02mP8wO0oWmO6jfZRf2TqPxsVUl BFew== X-Gm-Message-State: AFqh2kplFbOoejFzpXwccmSTmIo2T+P6qf0PlwNwqpuUKhSlPhyCBZdS 1a8FYGmSTSHDpz5JgTtRQMX2cu17M6U4G3AVClI= X-Google-Smtp-Source: AMrXdXt4e3/UR6bWZ/auVii7vDzZEJ/7kgl+EDgo8Da4VnJ8F0TV1P5NA3BAWHSLdoi+FGAxGuARLyL8kzLKcS8QsUY= X-Received: by 2002:a2e:2285:0:b0:285:d819:2b56 with SMTP id i127-20020a2e2285000000b00285d8192b56mr703269lji.467.1673594413196; Thu, 12 Jan 2023 23:20:13 -0800 (PST) MIME-Version: 1.0 References: In-Reply-To: From: Richard Biener Date: Fri, 13 Jan 2023 08:20:01 +0100 Message-ID: Subject: Re: [18/18] hash table: enforce testing is_empty before is_deleted To: Alexandre Oliva Cc: gcc-patches@gcc.gnu.org Content-Type: text/plain; charset="UTF-8" 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 Thu, Jan 12, 2023 at 10:32 PM Alexandre Oliva via Gcc-patches wrote: > > > Existing hash_table traits that use the same representation for empty > and deleted slots reject marking slots as deleted, and to not pass > is_deleted for slots that pass is_empty. > > Nevertheless, nearly everywhere, we only test for is_deleted after > checking that !is_empty first. The one exception was the copy > constructor, that would fail if traits recognized is_empty slots as > is_deleted, but then refused to mark_deleted. > > This asymmetry is neither necessary nor desirable, and there is a > theoretical risk that traits might not only fail to refuse to > mark_deleted, but also return is_deleted for is_empty slots. > > This patch introduces checks that detect these potentially problematic > situations, and reorders the tests in the copy constructor so as to > use the conventional testing order and thus avoid them. > > Regstrapped on x86_64-linux-gnu. Ok to install? OK. > > for gcc/ChangeLog > > * hash-table.h (is_deleted): Precheck !is_empty. > (mark_deleted): Postcheck !is_empty. > (copy constructor): Test is_empty before is_deleted. > --- > gcc/hash-table.h | 16 ++++++++++++++-- > 1 file changed, 14 insertions(+), 2 deletions(-) > > diff --git a/gcc/hash-table.h b/gcc/hash-table.h > index 1d3166504c38e..e37625dc315bf 100644 > --- a/gcc/hash-table.h > +++ b/gcc/hash-table.h > @@ -534,6 +534,11 @@ private: > void expand (); > static bool is_deleted (value_type &v) > { > + /* Traits are supposed to avoid recognizing elements as both empty > + and deleted, but to fail safe in case custom traits fail to do > + that, make sure we never test for is_deleted without having > + first ruled out is_empty. */ > + gcc_checking_assert (!Descriptor::is_empty (v)); > return Descriptor::is_deleted (v); > } > > @@ -545,6 +550,11 @@ private: > static void mark_deleted (value_type &v) > { > Descriptor::mark_deleted (v); > + /* Traits are supposed to refuse to set elements as deleted if > + those would be indistinguishable from empty, but to fail safe > + in case custom traits fail to do that, check that the > + just-deleted element does not look empty. */ > + gcc_checking_assert (!Descriptor::is_empty (v)); > } > > static void mark_empty (value_type &v) > @@ -700,9 +710,11 @@ hash_table::hash_table (const hash_table &h, > for (size_t i = 0; i < size; ++i) > { > value_type &entry = h.m_entries[i]; > - if (is_deleted (entry)) > + if (is_empty (entry)) > + continue; > + else if (is_deleted (entry)) > mark_deleted (nentries[i]); > - else if (!is_empty (entry)) > + else > new ((void*) (nentries + i)) value_type (entry); > } > m_entries = nentries; > > -- > 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