RFR: 8268290: Improve LockFreeQueue<> utility
Kim Barrett
kbarrett at openjdk.java.net
Sun Jun 6 16:26:19 UTC 2021
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
-------------
Commit messages:
- rename
- use end marker to improve pop
Changes: https://git.openjdk.java.net/jdk/pull/4379/files
Webrev: https://webrevs.openjdk.java.net/?repo=jdk&pr=4379&range=00
Issue: https://bugs.openjdk.java.net/browse/JDK-8268290
Stats: 1229 lines in 8 files changed: 619 ins; 601 del; 9 mod
Patch: https://git.openjdk.java.net/jdk/pull/4379.diff
Fetch: git fetch https://git.openjdk.java.net/jdk pull/4379/head:pull/4379
PR: https://git.openjdk.java.net/jdk/pull/4379
More information about the hotspot-dev
mailing list