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

[Thomas Schatzl]

On Mon, 14 Jun 2021 14:55:46 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 three additional commits since the last revision:
> 
>  - Merge branch 'master' into lfqueue
>  - rename
>  - use end marker to improve pop

I think this is good.

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

Marked as reviewed by tschatzl (Reviewer).

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