Race condition on InsertPairUnique can result in duplicates of the same key

[huntermBerkeley]

There is a race condition in the table when insertions and deletions occur concurrently.

This occurs when multiple unique insertions of the same key have a deletion interleaved between them, resulting in the inserting warps disagreeing on the correct position for insertion.

For a simple walkthrough consider a bucket currently storing one key A in slot 0, so the bucket is [A,empty].

Thread one is inserting key B and observes the bucket as [A,empty]. From this it determines slot 1 is the correct slot for insertion.

A different thread deletes A and frees slot 0, resulting in [empty, empty].

A third thread also inserts B. It observes the bucket as [empty, empty] and determines slot 0 as the correct slot.

Finally, both threads sucessfully CAS with empty_pair_64 and insert their keys. Neither thread observed the operation of the other but the final result in the bucket is [B,B] which is disallowed by insertPairUnique.

This also appears to be an issue if a key exists later in the chain, as the insertion will proceed if an empty slot exists in previous buckets in the chain despite a duplicate existing. Is this the expected behavior?