[jdk18] RFR: 8279294: NonblockingQueue::try_pop may improperly indicate queue is empty

[Kim Barrett]

On Mon, 17 Jan 2022 22:42:29 GMT, David Holmes <dholmes at openjdk.org> wrote:

> Hi Kim,
> 
> I haven't looked at this implementation in detail before, but what you are describing as a bug seems to be a known "property" of the implementation:
> 
> ```
> // A queue may temporarily appear to be empty even though elements have been
> // added and not removed.  For example, after running the following program,
> // the value of r may be NULL.
> //
> // thread1: q.push(a); r = q.pop();
> // thread2: q.push(b);
> //
> // This can occur if the push of b started before the push of a, but didn't
> // complete until after the pop.
> ```
> 
> ??
> 
> David

That's a different situation, and seems unavoidable without a pretty different design.

The case we're trying to squash with this change can exhibit even without any
concurrent push/append, i.e.
1. phase1 collects entries in the queue.
2. phase change ensures phase1 is complete and phase2 not yet started.
3. phase2 takes entries from the queue.

During phase2, the bug being addressed could lead concurrent try_pops to have
some (possibly even all but one) threads conclude there are no more entries
and so no more work to do, even though there are actually lots of entries and
all those threads just lost the race for the next one.

That isn't necessary or intended behavior.

-------------

PR: https://git.openjdk.java.net/jdk18/pull/106