Re: [17/17] check hash table insertions

[Richard Biener <richard.guenther@gmail.com>]

> Am 30.12.2022 um 09:53 schrieb Alexandre Oliva <oliva@adacore.com>:
> 
> On Dec 29, 2022, Richard Biener <richard.guenther@gmail.com> wrote:
> 
>>>> Am 29.12.2022 um 00:06 schrieb Alexandre Oliva <oliva@adacore.com>:
>>> 
>>> On Dec 28, 2022, Richard Biener <richard.guenther@gmail.com> wrote:
>>> 
>>>> 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)
>>> 
>>> I'm undecided whether a design that rules out the possibility of not
>>> having DELETED would qualify as unequivocally better.
>>> 
>>> 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’s 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’ll 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.

Ah, OK, so the completion is checked at the next conflicting operation.  Yeah, that makes sense I guess.

Thus OK (I think Jeff already approved the patch).

Thanks and happy holidays!

Richard 

> 
> 
> -- 
> 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 <https://stallmansupport.org>