RFR: 8343840: Rewrite the ObjectMonitor lists

[Coleen Phillimore]

On Wed, 26 Feb 2025 05:42:12 GMT, David Holmes <dholmes 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 fac...
>
> 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.

I like this suggestion.  I like these comments.

> 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.

How about add_to_entry_list with a boolean parameter that tries the lock if it fails, and only have one of these functions?  Although the return true if you get the lock makes it weird.


bool add_to_entry_list(JavaThread* current, ObjectWaiter* node, bool or_lock) {
  return true if locked, false otherwise;
}


Maybe that makes sense.

> 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?

I think for the vthread case, it isn't yet(?).  Maybe motivation to fix the ObjectWaiter constructor with this patch?

> 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

One of the benefits of this work is to read, understand and clean up misleading and out of date comments in this code.

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

PR Review Comment: https://git.openjdk.org/jdk/pull/23421#discussion_r1973636957
PR Review Comment: https://git.openjdk.org/jdk/pull/23421#discussion_r1973657207
PR Review Comment: https://git.openjdk.org/jdk/pull/23421#discussion_r1973681891
PR Review Comment: https://git.openjdk.org/jdk/pull/23421#discussion_r1973684370