From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp-out1.suse.de (smtp-out1.suse.de [195.135.220.28]) by sourceware.org (Postfix) with ESMTPS id 1C6173858D37 for ; Wed, 28 Dec 2022 08:50:13 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 1C6173858D37 Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=suse.cz Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=suse.cz Received: from imap2.suse-dmz.suse.de (imap2.suse-dmz.suse.de [192.168.254.74]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (P-521) server-digest SHA512) (No client certificate requested) by smtp-out1.suse.de (Postfix) with ESMTPS id DDB4C21A31; Wed, 28 Dec 2022 08:50:11 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.cz; s=susede2_rsa; t=1672217411; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc: mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=RlJuxXjBCg59XuEvyg4xTlRsZQH2DVtpLgQhtpjFlNM=; b=S1Q7rF5TeqQ0dsOXeWsnD2okS2RCgCzsmGrnq1jXLKVZ6H+VVFI5JxLmNvQz4eJd1MXQoP 7b/7p5uuR3ZVXXLZomh6GDa7dKUNcnDK3DGG3B3oWY+QdYlB8hMqfE5mkpcSBfNf06/Fq6 rRudpl/l1GwbuhSgkKGMQ3oo0nt1rm4= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.cz; s=susede2_ed25519; t=1672217411; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc: mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=RlJuxXjBCg59XuEvyg4xTlRsZQH2DVtpLgQhtpjFlNM=; b=dWVMraEZmdYp653aJ8bTeqn2Vpm4MVOr8mzfePgBAOULeWa4a+PT/AbrgrmKF+sjF1sOGf 6MRQkdddmxO/dEDg== Received: from imap2.suse-dmz.suse.de (imap2.suse-dmz.suse.de [192.168.254.74]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (P-521) server-digest SHA512) (No client certificate requested) by imap2.suse-dmz.suse.de (Postfix) with ESMTPS id C9A84134F5; Wed, 28 Dec 2022 08:50:11 +0000 (UTC) Received: from dovecot-director2.suse.de ([192.168.254.65]) by imap2.suse-dmz.suse.de with ESMTPSA id 63g6MEMDrGOeSAAAMHmgww (envelope-from ); Wed, 28 Dec 2022 08:50:11 +0000 Message-ID: Date: Wed, 28 Dec 2022 09:50:11 +0100 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101 Thunderbird/102.6.1 Subject: Re: [00/13] check hash table counts Content-Language: en-US To: Alexandre Oliva , gcc-patches@gcc.gnu.org References: From: =?UTF-8?Q?Martin_Li=c5=a1ka?= In-Reply-To: Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 7bit X-Spam-Status: No, score=-12.4 required=5.0 tests=BAYES_00,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,GIT_PATCH_0,NICE_REPLY_A,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 12/27/22 05:07, Alexandre Oliva via Gcc-patches wrote: > > 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. Hello. I really like the verification code you added. It's quite similar to what I added to hash-table.h: void hash_table ::verify (const compare_type &comparable, hashval_t hash) where the check is also expensive, but I guard it with a param value: hash-table-verification-limit The number of elements for which hash table verification is done for each searched element. You can utilize the parameter or come up with your own. Cheers, Martin > 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 > >