RFR: 8343840: Rewrite the ObjectMonitor lists

Thu Feb 27 14:28:05 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...

This looks really good - I have some small change and improvement requests.

src/hotspot/cpu/x86/c2_MacroAssembler_x86.cpp line 418:

> 416:   // have released the lock.
> 417:   // Refer to the comments in synchronizer.cpp for how we might encode extra
> 418:   // state in _succ so we can avoid fetching entry_list.

I there is no comment in synchronizer about this (that I can find) and whether or not this is a good idea, can you remove this line with this change?

src/hotspot/share/runtime/objectMonitor.cpp line 701:

> 699: void ObjectMonitor::add_to_entry_list(JavaThread* current, ObjectWaiter* node) {
> 700:   node->_prev   = nullptr;
> 701:   node->TState  = ObjectWaiter::TS_ENTER;

I think you should do this in a future cleanup.  The ObjectWaiter's constructor should initialize these fields to TS_ENTER or TS_WAIT when it's created  and make prev, next null (or 0xBAD?).  And fix the constructor to have an initialization list instead.

src/hotspot/share/runtime/objectMonitor.cpp line 735:

> 733:       assert(!has_successor(current), "invariant");
> 734:       assert(has_owner(current), "invariant");
> 735:       return true;

I wonder for a future RFE we can move these asserts into TryLock.

src/hotspot/share/runtime/objectMonitor.cpp line 1285:

> 1283: // By convention we unlink a contending thread from _entry_list immediately
> 1284: // after the thread acquires the lock in ::enter().  Equally, we could defer
> 1285: // unlinking the thread until ::exit()-time.

Since you're here, remove these two lines 1222-1223.  I really don't think pointing out an alternate implementation that we did not choose is helpful to understanding this code.

src/hotspot/share/runtime/objectMonitor.hpp line 46:

> 44: class ObjectWaiter : public CHeapObj<mtThread> {
> 45:  public:
> 46:   enum TStates : uint8_t { TS_UNDEF, TS_READY, TS_RUN, TS_WAIT, TS_ENTER };

TS_READY looks unused.

src/hotspot/share/runtime/objectMonitor.hpp line 79:

> 77:   void set_bad_pointers() {
> 78: #ifdef ASSERT
> 79:     // Diagnostic hygiene ...

hygiene seems like the wrong word here.  Can you remove this comment?

src/hotspot/share/runtime/synchronizer.cpp line 369:

> 367:       // We have one or more waiters. Since this is an inflated monitor
> 368:       // that we own, we can transfer one or more threads from the waitset
> 369:       // to the entry_list here and now, avoiding the slow-path.

Not related to this change but I found that this quick_notify isn't quicker.

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

Changes requested by coleenp (Reviewer).

PR Review: https://git.openjdk.org/jdk/pull/23421#pullrequestreview-2647862248
PR Review Comment: https://git.openjdk.org/jdk/pull/23421#discussion_r1973630782
PR Review Comment: https://git.openjdk.org/jdk/pull/23421#discussion_r1973654464
PR Review Comment: https://git.openjdk.org/jdk/pull/23421#discussion_r1973664035
PR Review Comment: https://git.openjdk.org/jdk/pull/23421#discussion_r1973670396
PR Review Comment: https://git.openjdk.org/jdk/pull/23421#discussion_r1973678657
PR Review Comment: https://git.openjdk.org/jdk/pull/23421#discussion_r1973632087
PR Review Comment: https://git.openjdk.org/jdk/pull/23421#discussion_r1973634214