Integrated: 8268290: Improve LockFreeQueue<> utility

[Kim Barrett]

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

This pull request has now been integrated.

Changeset: 0c693e2f
Author:    Kim Barrett <kbarrett at openjdk.org>
URL:       https://git.openjdk.java.net/jdk/commit/0c693e2f03b1adef0e946ebc32827ac09192f5f0
Stats:     1229 lines in 8 files changed: 619 ins; 601 del; 9 mod

8268290: Improve LockFreeQueue<> utility

Reviewed-by: iwalulya, tschatzl

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

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