From patchwork Tue Dec 27 04:07:35 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Alexandre Oliva X-Patchwork-Id: 36761 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a5d:4e01:0:0:0:0:0 with SMTP id p1csp1216953wrt; Mon, 26 Dec 2022 20:12:24 -0800 (PST) X-Google-Smtp-Source: AMrXdXtBNAByKfHl/xMY+cw4ddZfc2p7ZVXAP3uLFZVA18fU2tqxp7PhCfDXKS2t5k0bTTXEnwKa X-Received: by 2002:a17:907:8b93:b0:7c1:1dc7:8837 with SMTP id tb19-20020a1709078b9300b007c11dc78837mr17980671ejc.66.1672114343936; Mon, 26 Dec 2022 20:12:23 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1672114343; cv=none; d=google.com; s=arc-20160816; b=Kq+q/qoqR/FWk4ayN3HYS6DC8YCdwB+4QnPRe0112G2ESn7w+90O6PNr9BtCrA8Vol VX9iQnAb7icnEL30t2kI1mYbgBCZXGv16a3TBF7c1uglj/Vsc7KXalw7WMGkzC7y1w+S t8MYnweDJ4p6V/MrxLptPXDhN3FhoYa3wg721g94eX31mnKyoKSYclAi2EKuO65hZaD5 Rm3xUVfSR2K0QFBdAOLTQYHyujfHLqgoYHyqc7fX4ymcBLu1Mjfuuxa/8HO1ZpQZFQUt biWaP+UwcmhD6vFWGZbZzT3z5nfDikHZof6Rgw2GOANWjF38E2W6AOC4GHQYHQz9smfh p5/g== 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=9QRb1H4xDKDRjJDTN0wJ/J4juqE6iX9hYTi3moRjAxw=; b=i/Dhaqct1O0HZlr7YpZN0rDaz4IFMwxieIvM/7m+/biGG47RNzp8RSUTm1kOlrClTh r2GWkJnNwhwc89uEDh/haLxxzmwebGxxhriObK7AbzmaU1in6CJSoMHTYY5CVpg9T21v XjqfEEaJD1wgBqpI6p7ahynDA9zDC5ikioSFk9bgj+diFYdMmuZx+/Yq0wF13Yd4Llbt abt9OuMR9k3J3xlzyJlHJDKyJXvOaePOhjRZzrS0E4jx/jXklLx/anHvhTXpxuJh2aQI gcTZs7XuPIjIjQRSJikG++xc1MrVoVOc6OlLPlay3PUhcSoh5XGYUayXlQeSUuovNvjq cGSA== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=o1eJYFxc; 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 (ip-8-43-85-97.sourceware.org. [8.43.85.97]) by mx.google.com with ESMTPS id xe10-20020a170907318a00b007ae127c6c80si10160004ejb.672.2022.12.26.20.12.23 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 26 Dec 2022 20:12:23 -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=o1eJYFxc; 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 24FCF3857B9B for ; Tue, 27 Dec 2022 04:12:16 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 24FCF3857B9B DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1672114336; bh=9QRb1H4xDKDRjJDTN0wJ/J4juqE6iX9hYTi3moRjAxw=; h=To:Subject:Date:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=o1eJYFxcfv2YuBJVw7pMJSmJcPZK06QVxGiv9K8p13sNtQfDs6pOFFiShCHQe1c0Z TtZPoUI9VIYnxXvSDc/rrGtrXcaW0zg2ufbkRtENBdxq6szxGGw0wo9iwukSIrgMvo BTlTC8V2T2qvIoT/LB376DDHsUGpNNexddJ/4Ew8= 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 BDF4E3858D32 for ; Tue, 27 Dec 2022 04:11:31 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org BDF4E3858D32 Received: from localhost (localhost.localdomain [127.0.0.1]) by filtered-rock.gnat.com (Postfix) with ESMTP id 572A31162A6; Mon, 26 Dec 2022 23:11:30 -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 vOwOGuttvXTw; Mon, 26 Dec 2022 23:11:30 -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 1C36111628F; Mon, 26 Dec 2022 23:11:29 -0500 (EST) Received: from livre (livre.home [172.31.160.2]) by free.home (8.15.2/8.15.2) with ESMTPS id 2BR47Zxl711471 (version=TLSv1.3 cipher=TLS_AES_256_GCM_SHA384 bits=256 verify=NOT); Tue, 27 Dec 2022 01:07:35 -0300 To: gcc-patches@gcc.gnu.org Subject: [00/13] check hash table counts Organization: Free thinker, does not speak for AdaCore Date: Tue, 27 Dec 2022 01:07:35 -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=-12.2 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?1753338970114006121?= X-GMAIL-MSGID: =?utf-8?q?1753338970114006121?= While looking into another issue that corrupted hash tables, I added code to check consistency of element counts, and hit numerous issues that were concerning, of three kinds: insertion of entries that seem empty, dangling insertions, and lookups during insertions. These problems may all have the effect of replacing a deleted entry with one that seems empty, which may disconnect double-hashing chains involving that entry, and thus cause entries to go missing. This patch, opening the patch series, only adds code to detect these problems to the hash table verifier method. I'm not sure it makes sense to put it in, but I post it for the record. Fixes and cheaper detectors for some of these errors are going to be posted separately. The number of bugs it revealed tells me that leaving callers in charge of completing insertions is too error prone. I found this verification code a bit too expensive to enable in general. We could add check entry count cheaply at expand time and catch some of these at very low cost, which would likely catch at least some of the errors, but perhaps a safer interface could avoid them entirely. WDYT? I'm going to post a collection of 13 patches a as a followup to this one, fixing various problems it has detected, or adding code to catch some of these problems sooner. for gcc/ChangeLog * hash-table.h (verify): Check elements and deleted counts. --- gcc/hash-table.h | 17 +++++++++++++++++ 1 file changed, 17 insertions(+) diff --git a/gcc/hash-table.h b/gcc/hash-table.h index 53507daae26c3..7dbeea05373a2 100644 --- a/gcc/hash-table.h +++ b/gcc/hash-table.h @@ -1035,6 +1035,23 @@ hash_table && Descriptor::equal (*entry, comparable)) hashtab_chk_error (); } + + if (m_size < 2048) + { + size_t elmts = m_n_elements, dels = m_n_deleted; + for (size_t i = 0; i < m_size; i++) + { + value_type *entry = &m_entries[i]; + if (!is_empty (*entry)) + { + elmts--; + if (is_deleted (*entry)) + dels--; + } + } + if (elmts || dels) + hashtab_chk_error (); + } } /* This function deletes an element with the given COMPARABLE value