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: 62423 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 2F5C53858284 for ; Tue, 27 Dec 2022 04:12:01 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 2F5C53858284 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1672114321; bh=9QRb1H4xDKDRjJDTN0wJ/J4juqE6iX9hYTi3moRjAxw=; h=To:Subject:Date:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=l7QR39m706m0vx6BtjMTV+cOST8waSN/NFpqdScttOGJ3RNo4AsFka4akL4tIQFAB U8KIJgqcCTqtE7Y0CuUiO027pPiG3Q8YHS/LK/XEq0QLmSZAMuU16k3uyLt1sYUGqx eqexy7AQjfCAmTBxOU/ncPBOJR+NVZKG47AIFjxM= 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+patchwork=sourceware.org@gcc.gnu.org Sender: "Gcc-patches" 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