RFR: 8268290: Improve LockFreeQueue<> utility [v3]

[Kim Barrett]

On Tue, 22 Jun 2021 17:47:08 GMT, Kim Barrett <kbarrett at openjdk.org> wrote:

>> Please review this change to the LockFreeQueue utility class.
>> 
>> The LockFreeQueue originated as an implementation detail of
>> G1DirtyCardQueueSet, and was recently refactored into a public utility
>> class.  In that refactoring it retained some limitations that were
>> acceptable in its original context, but may be problematic as a general
>> utility.
>> 
>> In particular, under some conditions a thread was not be able to pop the
>> last element in the queue, due to interference by a concurrent operation.
>> And this state will persist, so retrying the pop operation won't help until
>> the interfering thread had made sufficient progress. This was mitigated by
>> making the API more complex to provide notice to the client that the queue
>> may be in this state.
>> 
>> But it turns out we can do somewhat better, eliminating one of the
>> limitations, which is the point of this change.  We introduce a
>> pseudo-object used as an end of queue marker.  We can use the transition of
>> the last element's next value from the end marker to NULL by a pop operation
>> as a claim on the element, allowing the losing thread to recognize, retry,
>> and make progress.
>> 
>> This queue still has the limitation that an in-progress push/append may
>> prevent popping elements.  Because of this, the class is being renamed to
>> NonblockingQueue.  The old name suggests stronger guarantees than actually
>> provided.
>> 
>> The PR has two commits, the first for the functional changes, the second for
>> the renaming.  The github diffs don't seem to be recognizing the renaming of
>> the source files as a rename, instead treating the old files as deleted and
>> the new files as added.  The first commit by itself is probably more useful
>> for reviewing the functional changes.
>> 
>> Testing:
>> mach5 tier1-5
>
> Kim Barrett has updated the pull request with a new target base due to a merge or a rebase. The incremental webrev excludes the unrelated changes brought in by the merge/rebase. The pull request contains four additional commits since the last revision:
> 
>  - Merge branch 'master' into lfqueue
>  - Merge branch 'master' into lfqueue
>  - rename
>  - use end marker to improve pop

I don't think `pop()` needs `SpinPause()` in its body.  It's not really an empty spin.  It only loops on a cmpxchg failure.  Someone might want to use `try_pop()` and `SpinYield` or something similar in a highly contended case, but I'd rather leave that to the specific case to parameterize.

You are correct that this comment should be removed: "it is an invariant that the old tail's "next" value is NULL".  Oops, sorry I missed that.

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

PR: https://git.openjdk.java.net/jdk/pull/4379