RFR: 8268290: Improve LockFreeQueue<> utility

[Ivan Walulya]

On Sun, 6 Jun 2021 16:17:40 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

lgtm!

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

Marked as reviewed by iwalulya (Committer).

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