RFR: 8343840: Rewrite the ObjectMonitor lists
David Holmes
dholmes at openjdk.org
Wed Feb 26 07:02:12 UTC 2025
On Mon, 3 Feb 2025 16:29:25 GMT, Fredrik Bredberg <fbredberg at openjdk.org> wrote:
> I've combined two `ObjectMonitor`'s lists, `EntryList` and `cxq`, into one list. The `entry_list`.
>
> This way c2 no longer has to check both `EntryList` and `cxq` in order to opt out if the "conceptual entry list" is empty, which also means that the constant question about if it's safe to first check the `EntryList` and then `cxq` will be a thing of the past.
>
> In the current multi-queue design new threads where always added to the `cxq`, then `ObjectMonitor::exit` would choose a successor from the head of `EntryList`. When the `EntryList` was empty and `cxq` was not, `ObjectMonitor::exit` whould detached the singly linked `cxq` list, and add the elements to the doubly linked `EntryList`. The element that was first added to `cxq` whould be at the tail of the `EntryList`. This way you ended up working through the contending threads in LIFO-chunks.
>
> The new list-design is as much a multi-queue as the current. Conceptually it can be looked upon as if the old singly linked `cxq` list doesn't end with a null pointer, but instead has a link that points to the head of the doubly linked `entry_list`.
>
> You always add to the `entry_list` by Compare And Exchange to the head. The most common case is that you remove from the tail (the successor is chosen in strict FIFO order). The head is volatile, but the interior is stable.
>
> The first contending thread that "pushes" itself onto `entry_list`, will be the last thread in the list. Each newly pushed thread in `entry_list` will be linked trough its next pointer, and have its prev pointer set to null, thus pushing new threads onto `entry_list` will form a singly linked list. The list is always in the right order (via the next-pointers) and is never moved to another list.
>
> Since we choose the successor in FIFO order, the exiting thread needs to find the tail of the `entry_list`. This is done by walking from the `entry_list` head. While walking the list we assign the prev pointers of each thread, essentially forming a doubly linked list. The tail pointer is cached in `entry_list_tail` so that we don't need to walk from the `entry_list` head each time we need to find the tail (successor).
>
> Performance wise the new design seems to be equal to the old design, even though c2 generates two less instructions per monitor unlock operation.
>
> However the complexity of the source has been reduced by removing the `TS_CXQ` state and adding functions instead of inlining `cmpxchg` here and there, and the fact that c2 no longer has to check b...
Disclaimer for other reviewers, I have been looking at this code for some time now.
Overall code looks good. I have quite a few comments/suggestions about comments.
I suggest renaming `_vthread_cxq_head` to just `_vthread_head` as the `cxq` part is no longer meaningful.
I agree that even though this seems performance neutral, the code simplification (for people reading it for the first time) will be worth it.
Thanks.
src/hotspot/share/jvmci/vmStructs_jvmci.cpp line 331:
> 329: volatile_nonstatic_field(ObjectMonitor, _owner, int64_t) \
> 330: volatile_nonstatic_field(ObjectMonitor, _recursions, intptr_t) \
> 331: volatile_nonstatic_field(ObjectMonitor, _entry_list, ObjectWaiter*) \
Suggestion:
volatile_nonstatic_field(ObjectMonitor, _entry_list, ObjectWaiter*) \
Extra space
src/hotspot/share/runtime/objectMonitor.cpp line 166:
> 164: // its next pointer, and have its prev pointer set to null. Thus
> 165: // pushing six threads A-F (in that order) onto entry_list, will
> 166: // form a singly-linked list, see 1) below.
Suggestion: have diagram 1 immediately follow this text so the reader doesn't have to jump down.
src/hotspot/share/runtime/objectMonitor.cpp line 172:
> 170: // from the entry_list head. While walking the list we also assign
> 171: // the prev pointers of each thread, essentially forming a doubly
> 172: // linked list, see 2) below.
Suggestion: have diagram 2 immediately follow this text so the reader doesn't have to jump down.
src/hotspot/share/runtime/objectMonitor.cpp line 176:
> 174: // Once we have formed a doubly linked list it's easy to find the
> 175: // successor, wake it up, have it remove itself, and update the
> 176: // tail pointer, as seen in 2) and 3) below.
Suggestion:
// tail pointer, as seen in 3) below.
But have diagram 3 right here.
src/hotspot/share/runtime/objectMonitor.cpp line 179:
> 177: //
> 178: // At any time new threads can add themselves to the entry_list, see
> 179: // 4) and 5).
Diagrams 4 and 5 do not follow from what has just been described, but the use of "at any time" implies to me you intended to show them affecting the queue as we have already seen it.
Again show the diagram you want here.
src/hotspot/share/runtime/objectMonitor.cpp line 183:
> 181: // If the thread that removes itself from the end of the list hasn't
> 182: // got any prev pointer, we just set the tail pointer to null, see
> 183: // 5) and 6).
Suggestion:
// If the thread to be removed is the only thread in the entry list:
// entry_list -> A -> null
// entry_list_tail ---^
// we remove it and just set the tail pointer to null,
// entry_list -> null
// entry_list_tail -> null
src/hotspot/share/runtime/objectMonitor.cpp line 187:
> 185: // Next time we need to find the successor and the tail is null, we
> 186: // just start walking from the entry_list head again forming a new
> 187: // doubly linked list, see 6) and 7) below.
Suggestion:
// Next time we need to find the successor and the tail is null,
// entry_list ->I->H->G->null
// entry_list_tail ->null
// we just start walking from the entry_list head again forming a new
// doubly linked list:
// entry_list ->I<=>H<=>G->null
// entry_list_tail ----------^
src/hotspot/share/runtime/objectMonitor.cpp line 189:
> 187: // doubly linked list, see 6) and 7) below.
> 188: //
> 189: // 1) entry_list ->F->E->D->C->B->A->null
Suggestion:
// 1) entry_list ->F->E->D->C->B->A->null
Right-justify the names please
src/hotspot/share/runtime/objectMonitor.cpp line 215:
> 213: // The mutex property of the monitor itself protects the entry_list
> 214: // from concurrent interference.
> 215: // -- Only the monitor owner may detach nodes from the entry_list.
Suggestion for this block - get rid of invariants headings and just say:
// The monitor itself protects all of the operations on the entry_list except for the CAS of a new arrival
// to the head. Only the monitor owner can read or write the prev links (e.g. to remove itself) or update
// the tail.
src/hotspot/share/runtime/objectMonitor.cpp line 225:
> 223: // concurrent detaching thread. This mechanism is immune from the
> 224: // ABA corruption. More precisely, the CAS-based "push" onto
> 225: // entry_list is ABA-oblivious.
Not sure this actually says anything to help people understand the code or its operation. There basically is no A-B-A issue with the use of CAS here.
src/hotspot/share/runtime/objectMonitor.cpp line 227:
> 225: // entry_list is ABA-oblivious.
> 226: //
> 227: // * The entry_list form a queue of threads stalled trying to acquire
Suggestion:
// * The entry_list forms a queue of threads stalled trying to acquire
src/hotspot/share/runtime/objectMonitor.cpp line 232:
> 230: // thread notices that the tail of the entry_list is not known, we
> 231: // convert the singly-linked entry_list into a doubly linked list by
> 232: // assigning the prev pointers and the entry_list_tail pointer.
Didn't we essentially say all this at the beginning?
src/hotspot/share/runtime/objectMonitor.cpp line 260:
> 258: //
> 259: // * notify() or notifyAll() simply transfers threads from the WaitSet
> 260: // to either the entry_list. Subsequent exit() operations will
Suggestion:
// to the entry_list. Subsequent exit() operations will
src/hotspot/share/runtime/objectMonitor.cpp line 704:
> 702:
> 703: for (;;) {
> 704: ObjectWaiter* front = Atomic::load(&_entry_list);
In comments and code pick "head" or "front" to use to describe what _entry_list points to and use that consistently. I think "front" is much more common.
src/hotspot/share/runtime/objectMonitor.cpp line 705:
> 703: for (;;) {
> 704: ObjectWaiter* front = Atomic::load(&_entry_list);
> 705:
No need for blank line.
src/hotspot/share/runtime/objectMonitor.cpp line 718:
> 716: // if we added current to _entry_list. Once on _entry_list, current
> 717: // stays on-queue until it acquires the lock.
> 718: bool ObjectMonitor::try_lock_or_add_to_entry_list(JavaThread* current, ObjectWaiter* node) {
Nit: the name suggests we do the try_lock first, when we don't. If we reverse the name we should also reverse the true/false return so that true relates to the first part of the name. See what others think.
src/hotspot/share/runtime/objectMonitor.cpp line 719:
> 717: // stays on-queue until it acquires the lock.
> 718: bool ObjectMonitor::try_lock_or_add_to_entry_list(JavaThread* current, ObjectWaiter* node) {
> 719: node->_prev = nullptr;
Shouldn't this already be the case?
src/hotspot/share/runtime/objectMonitor.cpp line 724:
> 722: for (;;) {
> 723: ObjectWaiter* front = Atomic::load(&_entry_list);
> 724:
No need for blank line.
src/hotspot/share/runtime/objectMonitor.cpp line 731:
> 729:
> 730: // Interference - the CAS failed because _entry_list changed. Just retry.
> 731: // As an optional optimization we retry the lock.
Suggestion:
// Interference - the CAS failed because _entry_list changed. Before
// retrying the CAS retry taking the lock as it may now be free.
src/hotspot/share/runtime/objectMonitor.cpp line 812:
> 810: guarantee(_entry_list == nullptr,
> 811: "must be no entering threads: entry_list=" INTPTR_FORMAT,
> 812: p2i(_entry_list));
Mustn't re-read _entry_list in the p2i as it may have changed from the value that is causing the guarantee to fail. The old guarantees were buggy in this regard - a temp is needed.
src/hotspot/share/runtime/objectMonitor.cpp line 1299:
> 1297: assert(_entry_list_tail == nullptr || _entry_list_tail == currentNode, "invariant");
> 1298:
> 1299: ObjectWaiter* v = Atomic::load(&_entry_list);
Nit: use `w` to be consistent with similar code. The original used `w` for EntryList and `v` for cxq IIRC.
src/hotspot/share/runtime/objectMonitor.cpp line 2018:
> 2016: // that in prepend-mode we invert the order of the waiters. Let's say that the
> 2017: // waitset is "ABCD" and the entry_list is "XYZ". After a notifyAll() in prepend
> 2018: // mode the waitset will be empty and the entry_list will be "DCBAXYZ".
We don't support different ordering modes any more so we always "prepend" such that waiters are added to the entry_list in the reverse order of waiting. So given waitList -> A -> B -> C -> D, and _entry_list -> x -> y -> z we will get _entry_list -> D -> C -> B -> A -> X -> Y -> Z
src/hotspot/share/runtime/objectMonitor.hpp line 195:
> 193: volatile intx _recursions; // recursion count, 0 for first entry
> 194: ObjectWaiter* volatile _entry_list; // Threads blocked on entry or reentry.
> 195: // The list is actually composed of WaitNodes,
Suggestion:
// The list is actually composed of wait-nodes,
Pre-existing (check for other uses) `WaitNodes` reads like a class name but it isn't.
-------------
Changes requested by dholmes (Reviewer).
PR Review: https://git.openjdk.org/jdk/pull/23421#pullrequestreview-2643098063
PR Review Comment: https://git.openjdk.org/jdk/pull/23421#discussion_r1970923830
PR Review Comment: https://git.openjdk.org/jdk/pull/23421#discussion_r1970940771
PR Review Comment: https://git.openjdk.org/jdk/pull/23421#discussion_r1970940914
PR Review Comment: https://git.openjdk.org/jdk/pull/23421#discussion_r1970941662
PR Review Comment: https://git.openjdk.org/jdk/pull/23421#discussion_r1970936929
PR Review Comment: https://git.openjdk.org/jdk/pull/23421#discussion_r1970946641
PR Review Comment: https://git.openjdk.org/jdk/pull/23421#discussion_r1970948581
PR Review Comment: https://git.openjdk.org/jdk/pull/23421#discussion_r1970934947
PR Review Comment: https://git.openjdk.org/jdk/pull/23421#discussion_r1970956573
PR Review Comment: https://git.openjdk.org/jdk/pull/23421#discussion_r1970965071
PR Review Comment: https://git.openjdk.org/jdk/pull/23421#discussion_r1970965291
PR Review Comment: https://git.openjdk.org/jdk/pull/23421#discussion_r1970966451
PR Review Comment: https://git.openjdk.org/jdk/pull/23421#discussion_r1970967237
PR Review Comment: https://git.openjdk.org/jdk/pull/23421#discussion_r1970971522
PR Review Comment: https://git.openjdk.org/jdk/pull/23421#discussion_r1970968581
PR Review Comment: https://git.openjdk.org/jdk/pull/23421#discussion_r1970975419
PR Review Comment: https://git.openjdk.org/jdk/pull/23421#discussion_r1970976144
PR Review Comment: https://git.openjdk.org/jdk/pull/23421#discussion_r1970976457
PR Review Comment: https://git.openjdk.org/jdk/pull/23421#discussion_r1970977990
PR Review Comment: https://git.openjdk.org/jdk/pull/23421#discussion_r1970979335
PR Review Comment: https://git.openjdk.org/jdk/pull/23421#discussion_r1970982964
PR Review Comment: https://git.openjdk.org/jdk/pull/23421#discussion_r1971037645
PR Review Comment: https://git.openjdk.org/jdk/pull/23421#discussion_r1970926134
More information about the hotspot-dev
mailing list