- Loading...
Page History
...
ObjectMonitor T-deflate
T-enter +-----------------------+ --------------------------------------------
---------------------- | owner=DEFLATER_MARKER | deflate_monitor_using_JT() {
owner<owner contendedis contended> | contentions=0 | cmpxchg(DEFLATER_MARKER, &owner, NULL)
atomic inc contentions +-----------------------+ :
prev = cmpxchg(-max_jint, &contentions, 0)
...
ObjectMonitor T-deflate
T-enter +-----------------------+ --------------------------------------------
------------------------------- | owner=DEFLATER_MARKER | deflate_monitor_using_JT() {
owner<owner contended is contended> | contentions=-max_jint | cmpxchg(DEFLATER_MARKER, &owner, NULL)
atomic inc contentions +-----------------------+ :
if (contentions <= 0 && prev = cmpxchg(-max_jint, &contentions, 0)
owner == DEFLATER_MARKER) { if (prev == 0 &&
restore obj header owner == DEFLATER_MARKER) {
retry enter restore obj header
} finish the deflation
}
...
ObjectMonitor T-deflate
T-enter +-----------------------+ --------------------------------------------
------------------------------- | owner=DEFLATER_MARKER | deflate_monitor_using_JT() {
<owner owneris contended contended> | contentions=1 | cmpxchg(DEFLATER_MARKER, &owner, NULL)
atomic inc contentions +-----------------------+ :
if (contentions <= 0 && prev = cmpxchg(-max_jint, &contentions, 0)
owner == DEFLATER_MARKER) { if (prev == 0 &&
} else { owner == DEFLATER_MARKER) {
do contended } else {
enter work cmpxchg(NULL, &owner, DEFLATER_MARKER)
...
ObjectMonitor T-deflate
T-enter +-------------------------+ ------------------------------------------
------------------------------------------ | owner=DEFLATER_MARKER | deflate_monitor_using_JT() {
owner<owner contended is contended> | contentions=1 | cmpxchg(DEFLATER_MARKER, &owner, NULL)
atomic inc contentions +-------------------------+ 1> :
1> if (contentions <= 0 && || 2> : <thread_stalls>
owner == DEFLATER_MARKER) { \/ :
} else { +-------------------------+ :
EnterI() | owner=Self/T-enter | :
cmpxchg(Self, &owner, DEFLATER_MARKER) | contentions=0 | : <thread_resumes>
atomic dec contentions +-------------------------+ prev = cmpxchg(-max_jint, &contentions, 0)
2> } || if (prev == 0 &&
// finished with enter \/ owner == DEFLATER_MARKER) {
3> : <does app work> +-------------------------+ } else {
exit() monitor | owner=Self/T-enter|NULL | cmpxchg(NULL, &owner, DEFLATER_MARKER)
owner = NULL | contentions=0 | atomic add max_jint to contentions
+-------------------------+ 3> bailout on deflation
}
- This diagram starts after "Racing Threads".
- T-enter incremented contentions to 1.
- The first ObjectMonitor box is showing the fields at this point and the "1>" markers are showing where each thread is at for that ObjectMonitor box.
- T-deflate stalls after setting the owner field to DEFLATER_MARKER.
- T-enter has won the race and calls EnterI() to do the contended enter work.
- EnterI() observes owner == DEFLATER_MARKER and uses cmpxchg() to set the owner field to Self/T-enter.
- T-enter decrements the contentions field because it is no longer contending for the monitor; it owns the monitor.
- The second ObjectMonitor box is showing the fields at this point and the "2>" markers are showing where each thread is at for that ObjectMonitor box.
- T-deflate resumes, sets the contentions field to -max_jint (not shown), and passes the first part of the bailout expression because "prev == 0".
- T-deflate observes that "owner != DEFLATE_MARKER" and bails out on deflation:
- Depending on when T-deflate resumes after the stall, it will see "owner == T-enter" or "owner == NULL".
- Both of those values will cause deflation to bailout so we have to conditionally undo work:
- restore the owner field to NULL if it is still DEFLATER_MARKER (it's not DEFLATER_MARKER)
- undo setting contentions to -max_jint by atomically adding max_jint to contentions which will restore contentions to its proper value.
- The third ObjectMonitor box is showing the fields at this point and the "3>" markers are showing where each thread is at for that ObjectMonitor box.
If the T-enter thread has managed to enter but not exit the monitor during the T-deflate stall, then our owner field A-B-A transition is:
NULL → DEFLATE_MARKER → Self/T-enter
so we really have A1-B-A2, but the A-B-A principal still holds.- If the T-enter thread has managed to enter and exit the monitor during the T-deflate stall, then our owner field A-B-A transition is:
NULL → DEFLATE_MARKER → Self/T-enter → NULL
so we really have A-B1-B2-A, but the A-B-A principal still holds.
T-enter and T-deflate Both Lose
This subsection is pure theory right now. I don't have a failing test case that illustrates this race result.
After working out the bug described in the "T-deflate and T-hash Both Lose" subsection below, it is time to take a closer look at the T-enter versus T-deflate race. For analysis of this race to make sense, the ref_count field has to be introduced in this subsection instead of in the "Hashcodes and Object Header Interference" section below.
ObjectMonitor T-deflate
T-enter +-------------------------+ -----------------------------------------------
------------------------------------------ | owner=DEFLATER_MARKER | deflate_monitor_using_JT() {
ref_count inc by ObjectMonitorHandle | contentions=0 | cmpxchg(DEFLATER_MARKER, &owner, NULL)
<owner is contended> | ref_count=1 | if (waiters != 0 || ref_count != 0) {
1> atomic inc contentions +-------------------------+ }
if (contentions <= 0 && || 1> prev = cmpxchg(-max_jint, &contentions, 0)
owner == DEFLATER_MARKER) { \/ 2> if (prev == 0 &&
2> restore obj header +-------------------------+ owner == DEFLATER_MARKER &&
retry enter | owner=DEFLATER_MARKER | cmpxchg(-max_jint, &ref_count, 0) == 0) {
} | contentions=-max_jint | restore obj header
| ref_count=1 | finish the deflation
+-------------------------+ } else {
cmpxchg(NULL, &owner, DEFLATER_MARKER)
atomic add max_jint to contentions
bailout on deflation
}
- T-deflate has set owner to DEFLATER_MARKER and made it past the first ref_count check.
- T-deflate is about change contentions to -max_jint.
- T-enter calls ObjectMonitor::enter() with an ObjectMonitorHandle already in place so "ref_count == 1".
- T-enter detects that owner is contended and is about to increment contentions.
- The first ObjectMonitor box is showing the fields at this point and the "1>" markers are showing where each thread is at for that ObjectMonitor box.
- T-deflate set the contentions field to -max_jint and is about to make the last of the protocol checks.
- T-enter sees "contentions <= 0 && owner == DEFLATER_MARKER" and realizes that it has lost the race.
- The second ObjectMonitor box is showing the fields at this point and the "2>" markers are showing where each thread is at for that ObjectMonitor box.
- T-enter restores the obj header (not shown) and the object is now disconnected from the ObjectMonitor.
- T-deflate sees "prev == 0 && owner == DEFLATER_MARKER" and tries to set the ref_count field to -max_jint.
- T-enter returns false to its caller to cause a retry (which will also decrement the ref_count in the ObjectMonitorHandle destructor).
- If T-enter manages to decrement the ref_count before T-deflate calls cmpxchg():
- T-deflate will change the ref_count field to -max_jint
- T-deflate will restore the obj header (not shown and already done) and finish the deflation
- T-enter will retry and there is no problem here (luckily).
- If T-deflate calls cmpxchg() while "ref_count == 1" that will fail:
- T-deflate bails out on deflation but it has to restore some data if possible:
- The return value of cmpxchg() is not checked here.
- If T-deflate cannot restore the owner field to NULL, then another thread has managed to enter the monitor (or enter and exit the monitor) and we don't want to overwrite that information.
- Add back max_jint to restore the contentions field to its proper value (which may not be the same as when we started).
- T-enter will retry, but the ObjectMonitor is still on the in-use list and still thinks it is associated with the object. Ouch!
- T-deflate bails out on deflation but it has to restore some data if possible:
I have to look at this new theory with fresh eyes, but if it holds together, then T-enter's "contentions <= 0 && owner == DEFLATER_MARKER" check will need to be changed to "contentions <= 0 && owner == DEFLATER_MARKER && ref_count <= 0" as was done for save_om_ptr().
An Example of Object Header Interference
...
Overview
Content Tools