From patchwork Thu Jan 12 06:46:23 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Alexandre Oliva X-Patchwork-Id: 42823 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a5d:4e01:0:0:0:0:0 with SMTP id p1csp4115733wrt; Thu, 12 Jan 2023 13:33:03 -0800 (PST) X-Google-Smtp-Source: AMrXdXtieAHrAbYn5sjODVFz9XHBLKmQRJY9EOYSZ5ofszJr7TtWuszfazwVWjjKk0PeNwfA9G1s X-Received: by 2002:a17:907:a705:b0:7bd:ece7:ae66 with SMTP id vw5-20020a170907a70500b007bdece7ae66mr72505892ejc.34.1673559183864; Thu, 12 Jan 2023 13:33:03 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1673559183; cv=none; d=google.com; s=arc-20160816; b=tQxtTH8uKbCK5h5HouWyzJlm7+NTSA/gPkmYaCLNHNjsm7dvLkG1/Cqlw9NCrzlVY1 zWPk9/ySWJ0FcAV7LrRxHCnmaKTpbUDBF2uwDWDenBU2W4Gt9ehd4Zjw4pvdRPg/ltEJ 4bmA+QLXUhQQOaf+cwgmAEX5UImdb/HYTpfxJ41J3n5+KHR8jpo9XzKEGrWWid5Vw5PX gsYekas5eeo8XPQedXDlZ0liCwhEy6a8a7S+EQtOCNIhgPKtStMPWpsaZ0lgYrQ0UEND QGCUyr5NvMNRt17EmqLxtqVgUvmt8ZkDpXw3dMlBYDcbxMtMtypAZsASwiBr2fnitfVa KxkA== 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:date:organization:subject:to:dmarc-filter :delivered-to:dkim-signature:dkim-filter; bh=SuZH0pDamXsIkgQ7KILS0N0b+Gw1/a518duG2Sfleho=; b=r8h0z/PERjVRnCvMt2FLZfO8xQTZFKYthEXJ/6BYu5icraGpXuZQUAtVKD5GZ45aWZ KyumAdignq2L03Nzx4mmYmZQLtJqoQtY/V0BUBn6I0KHty45XdekPmkKP1Qok7wahKke Go0XHzN4d4GTqKX+QFyoPj10AvTiWaO2Z0L72KB7Ot4IThTyMHp62t75rSM7qoEdzawt /YCBBBYIc5yEoywdAwki+PmaPDkrmCmAGKm9r0GOWsW4zIt9vsMB3zVeU0skhes9qCee ZkAp0gOFkKyEyckwZzwDMKsvasUpaqo/22MENOHIsVMDskag5wJT7vUA4eIBnuxZMMos HvJQ== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=htcd32J3; spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 8.43.85.97 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. [8.43.85.97]) by mx.google.com with ESMTPS id hc39-20020a17090716a700b007baa6e22742si23087710ejc.570.2023.01.12.13.33.03 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 12 Jan 2023 13:33:03 -0800 (PST) Received-SPF: pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 8.43.85.97 as permitted sender) client-ip=8.43.85.97; Authentication-Results: mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=htcd32J3; spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 8.43.85.97 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 9FAB6385E004 for ; Thu, 12 Jan 2023 21:33:02 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 9FAB6385E004 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1673559182; bh=SuZH0pDamXsIkgQ7KILS0N0b+Gw1/a518duG2Sfleho=; h=To:Subject:Date:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=htcd32J3OyRkQBdbNMjU5cZt7cGgzthyQN8N+rZ05WHfKzOm1q/SpNeF+8egNegGY z1/9bNuTByRqkHVtyDjgJy61GH08M848z7S35ydIVMYQHKnRpyzx6ZRZRGRmjCegQs h7tyG2MN6RhzuWxI4gsokowtHIUG8rwLKs6xMdXg= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from rock.gnat.com (rock.gnat.com [205.232.38.15]) by sourceware.org (Postfix) with ESMTPS id 8941B3858C66 for ; Thu, 12 Jan 2023 21:32:19 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 8941B3858C66 Received: from localhost (localhost.localdomain [127.0.0.1]) by filtered-rock.gnat.com (Postfix) with ESMTP id 75015116920; Thu, 12 Jan 2023 16:32:18 -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 irCvRKQTmEIe; Thu, 12 Jan 2023 16:32:18 -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 3AA61116913; Thu, 12 Jan 2023 16:32:18 -0500 (EST) Received: from livre (livre.home [172.31.160.2]) by free.home (8.15.2/8.15.2) with ESMTPS id 30C6kNJt1248379 (version=TLSv1.3 cipher=TLS_AES_256_GCM_SHA384 bits=256 verify=NOT); Thu, 12 Jan 2023 03:46:23 -0300 To: gcc-patches@gcc.gnu.org Subject: [18/18] hash table: enforce testing is_empty before is_deleted Organization: Free thinker, does not speak for AdaCore Date: Thu, 12 Jan 2023 03:46:23 -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=-11.6 required=5.0 tests=BAYES_00, DATE_IN_PAST_12_24, 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?1754853994446490676?= X-GMAIL-MSGID: =?utf-8?q?1754853994446490676?= 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? 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;