From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from rock.gnat.com (rock.gnat.com [IPv6:2620:20:4000:0:a9e:1ff:fe9b:1d1]) by sourceware.org (Postfix) with ESMTPS id 098333858D1E for ; Fri, 30 Dec 2022 08:53:53 +0000 (GMT) Received: from localhost (localhost.localdomain [127.0.0.1]) by filtered-rock.gnat.com (Postfix) with ESMTP id A40DB1163E8; Fri, 30 Dec 2022 03:53:51 -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 uWa9xCyPFh6L; Fri, 30 Dec 2022 03:53:51 -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 69F37116381; Fri, 30 Dec 2022 03:53:51 -0500 (EST) Received: from livre (livre.home [172.31.160.2]) by free.home (8.15.2/8.15.2) with ESMTPS id 2BU8rcmi792608 (version=TLSv1.3 cipher=TLS_AES_256_GCM_SHA384 bits=256 verify=NOT); Fri, 30 Dec 2022 05:53:39 -0300 From: Alexandre Oliva To: Richard Biener Cc: gcc-patches@gcc.gnu.org Subject: Re: [17/17] check hash table insertions Organization: Free thinker, does not speak for AdaCore References: Errors-To: aoliva@lxoliva.fsfla.org Date: Fri, 30 Dec 2022 05:53:37 -0300 In-Reply-To: (Richard Biener's message of "Thu, 29 Dec 2022 08:29:17 +0100") Message-ID: User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/26.3 (gnu/linux) MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable X-Scanned-By: MIMEDefang 2.84 X-Spam-Status: No, score=-6.3 required=5.0 tests=BAYES_00,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 List-Id: On Dec 29, 2022, Richard Biener wrote: >> Am 29.12.2022 um 00:06 schrieb Alexandre Oliva : >>=20 >> =EF=BB=BFOn Dec 28, 2022, Richard Biener wr= ote: >>=20 >>> I wonder if on INSERT, pushing a DELETED marker would fix the dangling >>> insert and search during delete problem be whether that would be >>> better from a design point of view? (It of course requires a DELETED >>> representation) >>=20 >> I'm undecided whether a design that rules out the possibility of not >> having DELETED would qualify as unequivocally better. >>=20 >> Unless DELETED takes over the NULL representation, and something else is >> used for EMPTY, every INSERT point would have to be adjusted to look for >> the non-NULL DELETED representation. > Not sure what you mean I meant existing code tests that dereferencing the returned slot pointer yields NULL. If we were to change the slot value during insert, we'd have to adjust all callers. > I think turning EMPTY (or DELETED) into > DELETED at insert time would make the slot occupied for lookups and > thus fix lookup during insert. Yup. > Of course insert during insert would > still fail and possibly return the same slot again. Yeah. > So the most foolproof design would be a new INSERTING representation. There's a glitch there: we can't expand with a pending insert. So we might need to count inserting nodes separately, or (ideally) be able to check quickly that insertions have completed. But then, inserting with a pending insert ought to be caught and reported, because an insertion invalidates previously-returned slot pointers, including that of the pending insert. And that's how I got to the proposed patch. >> The one-pending-insertion strategy I implemented was the only one I >> could find that addressed all of the pitfalls without significant >> overhead. It caught even one case that the mere element-counting had >> failed to catch. > Yes, it=E2=80=99s true that this addresses all issues with just imposing > constraints on API use. But the I wondered how you catched the > completion of the insertion? (I=E2=80=99ll have to > Dig into the patch to see) Record the slot with the pending insert, and at any subsequent operation (that could be affected by the pending insert), check and report in case the insertion was not completed. --=20 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