JDK-8176393 : Fix Mutex ranking system
  • Type: Enhancement
  • Component: hotspot
  • Sub-Component: runtime
  • Affected Version: 9
  • Priority: P3
  • Status: Resolved
  • Resolution: Delivered
  • Submitted: 2017-03-08
  • Updated: 2021-10-08
  • Resolved: 2021-10-08
The Version table provides details related to the release that this issue/RFE will be addressed.

Unresolved : Release in which this issue/RFE will be addressed.
Resolved: Release in which this issue/RFE has been resolved.
Fixed : Release in which this issue/RFE has been fixed. The release containing this fix may be available for download as an Early Access Release or a General Availability Release.

To download the current JDK release, click here.
JDK 18
18Resolved
Related Reports
Relates :  
Relates :  
Relates :  
Relates :  
Relates :  
Sub Tasks
JDK-8272447 :  
JDK-8272788 :  
JDK-8272797 :  
JDK-8273300 :  
JDK-8273456 :  
JDK-8273611 :  
JDK-8273915 :  
JDK-8273916 :  
JDK-8273917 :  
JDK-8273956 :  
JDK-8274004 :  
JDK-8274282 :  
Description
If a mutex has "leaf" ranking, it should be a leaf mutex, but alas, there are leaf-1 mutexes that are taken out when leaf mutexes are held.   The ranking system is a bit fragile.

I've been thinking about how to make this better, discussing with people like ErikO, Patricio and Kim, and suggest these improvements that can be made in stages:

1. Remove 'native' rank.  It's not used anymore for raw monitors and shouldn't have been used for others.
2. Remove 'safepoint' and 'barrier' ranks that don't make sense.
   Their rank is odd because they're higher than 'leaf' but some have 'safepoint_check_never'
   The goal is to partition the safepoint checking locks vs. nonsafepoint checking locks by rank.
   If we want to have names for specific ranks, especially for locks in other files, that's ok to add later.

3. Disallow _allow_vm_block=false, _safepoint_check_never configuration.  If it's _safepoint_check_never, assume that the VM can take this lock.  The other configurations make sense.

        _allow_vm_block=true,  _safepoint_check_always   - after safepoint check and lock acquired NSV
        _allow_vm_block=true,  _safepoint_check_never    - after lock acquired NSV
        _allow_vm_block=false, _safepoint_check_always   - after safepoint check and lock acquired, other safepoints ok
        _allow_vm_block=false, _safepoint_check_never    - after lock acquired, safepoints allowed (don't allow this!)

4. Make a 'max_safepoint_never' rank > oopstorage, so max_safepoint_never is the highest ranked lock that doesn't check for safepoints. (Now we have that check as 'special')

5. nonleaf ranked lock that don't safepoint don't make sense!  Change to leaf, to set up for step 6.

6. Divide leaf locks that check for safepoints, and leaf locks that don't check for safepoints into two.
Non safepoint become 'max_safepoint_never', safepoint become 'safepoint' or some better name

7. Log all lock hierarchies in /tmp while running the tests.

8. Reverse order in the mutexLocker.cpp list so highest ranked locks go first.
9. Make all safepoint checking locks = max_safepoint_always = 900 and put them first in the list, put the ones
   afterwards as some lock you own.rank() -1, ie:

  def(ClassLoaderDataGraph_lock    , PaddedMutex  , nonleaf,     false, _safepoint_check_always);
  def(SystemDictionary_lock        , PaddedMonitor, ClassLoaderDataGraph_lock.rank() -1, true,  _safepoint_check_always);

10. Add rank range checking so that there's no values that overlap the enum.  Also add an operator so that you can't add to a rank.  You can only subtract from max_safepoint_always or max_safepoint_never, but other ranks can be added in the middle if it makes things more clear, especially for locks defined in other files.

11. If all 'max_safepoint_never' and below cannot safepoint and above that can, remove the _no_safepoint_check field and its initialization. It's implied by the rank now.
Comments
Yes, "Resolved" as "Delivered" should be just fine...
08-10-2021

All the subtasks are done so I'm closing this as "Delivered" Is that right? There are more RFEs (and a broken rank bug) but they can be not subtasks.
08-10-2021

Also see PR comments from @dholmes in https://github.com/openjdk/jdk/pull/5467 The range between ranks should be less arbitrary (and checked for non-overlap, which is in this plan).
16-09-2021

I wrote some logging to record the least ranked lock held for every lock acquisition to a data file in /tmp/locks. If no lock is held, the lock ranking starts at either 'nosafepoint' for non-safepoint checking locks, or 'nonleaf' for safepoint checking locks. As locks are taken with other locks held, I write a new data file with that lower rank (with the lock name of the lower ranked lock). I ran this logging through tier1-3 tests and kitchensink and other tests, then processed these constraints to find the lowest ranked lock across these test runs. Attached are the data files.
10-09-2021

Suggested change: // All locks in the range of [0 .. nosafepoint] are guaranteed not to block // for a safepoint while holding it, i.e., no vm operation can happen, taking other // (safepoint blocking) locks, etc. // The rank 'tty' is reserved for the tty_lock. It's a low ranked lock because it can // be taken in many places in the VM. // All locks in the range of [nosafepoint .. nonleaf] may block // when holding it except if _allow_vm_block is true. _allow_vm_block means that the VM // can also take this lock. This lock is essentially a no_safepoint_after_acquire lock. // The service lock is quite low but because the we made it that way (has to be below stackwatermark) // When creating new locks, one can either specify the rank as nonleaf or // nosafepoint, unless other locks are held while this can be taken. Then // the choice is to subtract or give the least ranked held lock-1 as a rank. // Locks that are allocated outside mutexLocker.cpp may have named ranks for relative ranking. // The ranges are given so that the code can check that lock ranks don't overlap. enum lock_types { event, tty = event + 3, service = tty + 3, stackwatermark = service + 3, oopstorage = stackwatermark + 3, nosafepoint = oopstorage + 20, // top/default rank for no safepoint checking locks handshake = nosafepoint + 20, nonleaf = handshake + 20, // top/default rank for safepoint checking locks max_rank = nonleaf }; Also, would change Rank to be a enum class (thanks for the code [~kbarrett]) to only allow subtraction and checking for overlap.
25-08-2021

I agree that we can't use mutex ranking alone to avoid deadlock, the system we have today is a partial ordering. It is true that NonJavaThreads don't safepoint check when the locks are safepoint_check_always. Those threads should have the property 'true' in _allow_vm_block because they can acquired during safepoints, while JavaThreads can be holding them. That configuration of _allow_vm_block/safepoint_check_always handles that. The problems that I'm trying to solve are the historical bit rot that's occurred with these locks. 1. 'leaf' isn't. 2. 'special' isn't. 3. Adding and subtracting from ranks is arbitrary to get the locks in question to not hit the assert. 4. Ranks can overlap unintentionally and perhaps disastrously. 5. Nobody knows or can prove what _vm_block means or is set correctly. 6. NSV can be used more frequently to help prevent deadlocks if there are invariants about the setting of some locks. 7. The rank names barrier and safepoint don't really do anything special. Confusing why they exist today. 8. Many comments are wrong, confusing or obsolete. We made a lot of progress on lock ranking in the past few years. More NSV for allow_vm_block, getting rid of safepoint_check_sometimes, and adding new names for locks like oopstorage. I'm not convinced that we can not simply assert (rank < no_safepoint_check_top (ie max no_safepoint_check_rank)) == _safepoint_check_never *for Java threads*. I haven't found any case where that would fail (yet?) The work proposed is mainly renaming the lock ranks but keeping the existing system. The new rank names are based on a locking graph that I'm creating based on our existing tests. Any locks excluded from this graph can be visually inspected for a static rank best suited to them. I feel strongly that we want static lock ranking scheme that makes sense.
24-08-2021

So we have three related properties: - the rank: used to detect nested lock acquisition ordering issues that could lead to deadlock - the safepoint check: which may be a correctness issue (avoiding deadlock with VM thread) but can also be an optimisation - the _allow_vm_block: which is the VMThread side of the safepoint check effectively The basic idea is to not allow any thread to perform nested locking in a way that can lead to deadlock. It is not obvious to me that there is a linearization of ranks that allow all the potential deadlocking interactions to be handled based on rank alone - or even that rank can be used to partition the safepoint checks. Things are made more complex if we have locks that can be used by NonJavaThreads as well as JavaThreads. The ranking of locks used by NonJavaThreads may be leaf or non-leaf completely independent of any safepoint-checking notion because there is none in that case. The issue of ranking and safepoint-checking are not completely orthogonal, but nor do they align. The safepoint check when acquiring a lock is not about the lock being acquired, but about the lock(s) that may already be held. If a thread holds lock A and the VMThread may need lock A during a VMOp, then when the thread tries to acquire lock B it must not perform a safepoint check. But if lock A is never used by the VMThread then lock B can safely be acquired with a safepoint check. So I don't see how the safepoint checking aspect can be folded into the ranking system directly. To me, as I briefly wrote in 2017, you "need to generate a complete locking graph for the VM.". By seeing which locks may be acquired in a nested fashion, and by which type of threads, then you can see whether you can form a consistent ranking. And maybe we need to partition locks in a different way splitting out those that are only used by NJTs; those only used by JTs; those that can be used by VMThread at a safepoint etc. But again you need the analysis to know how locks are acquired.
23-08-2021

I have a prototype where I have an alternate _least_rank field in Mutex. The _least_rank field starts out as nsc_top (no_safepoint_check_top) where the lock has safepoint_check_never and sc_top (safepoint_check_top) where the lock has safepoint_check_always. As the VM runs, it records the first rank, and then reduces the _least_rank of the lock to the _least_rank of the locks it holds minus one. The ranks are stored as files as /tmp/locks. The lowest /tmp/lock/My_lock_<rank> is the suggested rank for the lock. For example: $ more Service_lock* :::::::::::::: Service_lock_11 :::::::::::::: def(Service_lock , PaddedMonitor, stack_watermark_lock->rank()-1, false, _safepoint_check_never); :::::::::::::: Service_lock_12 :::::::::::::: def(Service_lock , PaddedMonitor, HandshakeState->rank()-1, true, _safepoint_check_never); :::::::::::::: Service_lock_13 :::::::::::::: def(Service_lock , PaddedMonitor, nsc_top , true, _safepoint_check_never); $ more stack_watermark_lock_1* ::::::::::::: stack_watermark_lock_12 :::::::::::::: def(stack_watermark_lock , PaddedMutex , Patching_lock->rank()-1, true, _safepoint_check_never); :::::::::::::: stack_watermark_lock_13 :::::::::::::: def(stack_watermark_lock , PaddedMutex , nsc_top , true, _safepoint_check_never); $ more Patching_lock_13 def(Patching_lock , PaddedMutex , nsc_top , true, _safepoint_check_never);
20-08-2021

Maybe disallowing addition of mutex ranking doesn't make sense. Ignoring the safepont_check_never ranks which are at the bottom of the hierarchy, maybe there should be: enum class Rank { ... non safepoint checking ranks with names and small relative offsets (only allow negation?) no_safepoint_check_default = 100, no_safepoint_check_max = no_safepoint_check_default + 100, safepoint_check_min = no_safepoint_check_max +100, safepoint_check_default = safepoint_check_min + 100, safepoint_check_max = 900 }; Then most flags start out as safepoint_check_default, and as one adds locks, you can either use locks_it_uses.rank() +/- 1 as the new ranking. The problem I'm trying to solve is that when we add new locks, you don't want to have to reshuffle the rankings of the locks that are held, or that are taken out while this lock is being held in order to place the new lock in the right place. Comments? Names tbd.
15-08-2021

We already have a rank that means ignore this rank, which was rank native, but if we need an unranked lock, this could just be PlatformMonitor or semaphore or even the locks in ZGC that don't participate. If the locks are a Mutex, we want to not exclude rank checking.
12-08-2021

The ranking system is very obscure and fragile. Given non-obvious paths that can lead to locking (eg ttyLocker and probably now UL related locks) a strict ranking may not be possible. Possibly we need a rank that means "ignore the rank of this lock". Unclear how to make progress on this bug/RFE as you would need to generate a complete locking graph for the VM.
09-03-2017

From RFR discussion http://mail.openjdk.java.net/pipermail/hotspot-dev/2017-March/026120.html [~mgerdin] I suggest that the ranks of the involved locks are changed to "leaf - 1", allowing them to be acquired by threads holding "leaf" locks. This should not cause any further problems since reducing the ranks only allows the locks to be taken in more places. Both pairs of locks (the SATB and DirtyCardQ ones) have an associated FL_lock which protects a free list of buffers which is acquired while holding the respective CBL monitors but the FL_locks have the "special" lock rank and so they will still order correctly with the new "leaf - 1" ranks. I'm not sure what "special" means. // A special lock: Is a lock where you are guaranteed not to block while you are // holding it, i.e., no vm operation can happen, taking other locks, etc. // NOTE: It is critical that the rank 'special' be the lowest (earliest) Sounds like "really leaf".
08-03-2017