- Loading...
Page History
...
T-hash ObjectMonitor T-deflate
------------------------- +-----------------------+ -----------------------------------------------
save_om_ptr() { | owner=DEFLATER_MARKER | deflate_monitor_using_JT() {
1> atomic inc ref_count | contentions=-max_jint | cmpxchg(DEFLATER_MARKER, &owner, NULL)
1> if (owner == | ref_count=1 0 | if (waiters != 0 || ref_count != 0) {
DEFLATER_MARKER && +-----------------------+ }
contentions <= 0) {&& || prev = cmpxchg(-max_jint, &contentions, 0)
restore obj header ref_count <= 0) { \/ 1> if (prev == 0 &&
restore obj header atomic dec ref_count +-----------------------+ owner == DEFLATER_MARKER &&
2> return false to atomic dec ref_count | owner=DEFLATER_MARKER | cmpxchg(-max_jint, &ref_count, 0) == 0) {
2> return false to cause a retry | contentions=-max_jint | restore obj header
} cause a retry | ref_count=0 -max_jint | 2> finish the deflation
} +-----------------------+ }
- T-deflate made it past the first ref_count check before T-hash incremented it.
- T-deflate set the contentions field to -max_jint and T-enter incremented the ref_count fieldis about to make the last of the protocol checks.
- 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-hash observes "deflate sees "prev == 0 && owner == DEFLATER_MARKER" and sets the ref_count field to -max_jint so it has won the race.
- T-deflate && contentions <= 0" so it restores obj header (not shown) and decrements .
- T-hash increments the ref_count.
- T-deflate sees "prev == 0 && hash observes "owner == DEFLATER_MARKER && contentions <= 0 && ref_count =<= 0" so it has won the race.T-deflate restores obj header (not shown) and decrements ref_count.
- 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 finishes the deflation work.
- T-hash returns false to cause a retry and when T-hash retries:
- if it observes "owner == DEFLATER_MARKER && contentions <= 0" it will retry again.if it observes the restored object header :(done by T-hash or T-deflate):
- if the object's header does not have a hash, then generate a hash and merge it with the object's header.
- Otherwise, extract the hash from the object's header and return it.
- if it observes "owner == DEFLATER_MARKER && contentions <= 0" it will retry again.if it observes the restored object header :(done by T-hash or T-deflate):
...
T-hash ObjectMonitor T-deflate
------------------------- +-----------------------+ --------------------------------------------
save_om_ptr() { | header=dmw_no_hash | deflate_monitor_using_JT() {
atomic inc ref_count | owner=DEFLATER_MARKER | cmpxchg(DEFLATER_MARKER, &owner, NULL)
1> if (owner == | contentions=0 | 1> if (waiters != 0 || ref_count != 0) {
DEFLATER_MARKER && | ref_count=1 | cmpxchg(NULL, &owner, DEFLATER_MARKER)
contentions <= 0) {&& +-----------------------+ 2> bailout on deflation
} ref_count <= 0) { || }
} || }
if (object no longer \/ prev = cmpxchg(-max_jint, &contentions, 0)
if has(object ano monitorlonger or +-----------------------+
ishas a differentmonitor or | header=dmw_no_hash |
monitor)is {a different | owner=NULL |
atomic dec ref_count monitor) { | contentions=0 |
returnatomic false to dec ref_count | ref_count=1 |
return false causeto a retry +-----------------------+
} cause a retry ||
} ||
2> save om_ptr in the \/
2> save om_ptr in the ObjectMonitorHandle +-----------------------+
} ObjectMonitorHandle | header=dmw_hash |
} | header=dmw_hash |
if save_om_ptr() { | owner=NULL |
if no hash save_om_ptr() { | contentions=0 |
if gen hash & mergeno hash | ref_count=1 |
gen hash & = hash(header)merge +-----------------------+
}
3> hash = hash(header)
}
3> atomic dec ref_count
return hash
- T-hash has incremented ref_count before T-deflate made it past that check.
- 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 bails out on deflation, but first it tries to restore the owner field:
- 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.
- T-hash observes:
- "owner == DEFLATER_MARKER && contentions == 0 && ref_count > 0" or
- "owner == NULL && contentions == 0 && ref_count > 0" so it does not cause a retry.
- T-hash verifies that the object still has a monitor and that monitor still refers to our current ObjectMonitor.
- 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-hash saves the ObjectMonitor* in the ObjectMonitorHandle (not shown) and returns to the caller.
- save_om_ptr() returns true since the ObjectMonitor is safe:
- if ObjectMonitor's 'header/dmw' field does not have a hash, then generate a hash and merge it with the 'header/dmw' field.
- Otherwise, extract the hash from the ObjectMonitor's 'header/dmw' field.
- The third ObjectMonitor box is showing the fields at this point and the "3>" marker is showing where T-hash is at for that ObjectMonitor box.
- T-hash decrements the ref_count field.
- T-hash returns the hash value.
...
In this T-hash wins scenario, the need for the "ref_count == 0" check in the third phase of the protocol is illustrated.
T-hash hash ObjectMonitor T-deflate
------------------------- +-----------------------+ -----------------------------------------------
save_om_ptr() { | header=dmw_no_hash | deflate_monitor_using_JT() {
atomic inc ref_count | owner=DEFLATER_MARKER | cmpxchg(DEFLATER_MARKER, &owner, NULL)
if (owner == | contentions=0 | if (waiters != 0 || ref_count != 0) {
DEFLATER_MARKER && | ref_count=1 | }
contentions <= 0) {&& +-----------------------+ 1> prev = cmpxchg(-max_jint, &contentions, 0)
} ref_count <= 0) { || 2> if (prev == 0 &&
1> if (object no longer } \/ owner == DEFLATER_MARKER &&
has a monitor or 1> if (object no longer +-----------------------+ ref_count cmpxchg(-max_jint, &ref_count, 0) == 0) {
ishas a differentmonitor or | header=dmw_no_hash | } else {
monitor)is {a different | owner=DEFLATER_MARKER | cmpxchg(NULL, &owner, DEFLATER_MARKER)
atomic dec ref_count monitor) { | contentions=-max_jint | atomic add max_jint to contentions
returnatomic false to dec ref_count | ref_count=1 | 3> bailout on deflation
return false causeto a retry +-----------------------+ }
} cause a retry ||
} ||
2> save om_ptr in the \/
2> save om_ptr in the ObjectMonitorHandle +-----------------------+
} ObjectMonitorHandle | header=dmw_hash |
} | header=dmw_hash |
if save_om_ptr() { | owner=NULL |
if no hash save_om_ptr() { | contentions=0 |
if no hash gen hash & merge | ref_count=1 |
gen hash & merge = hash(header) +-----------------------+
hash = hash(header)
}
3> atomic dec ref_count
return hash
- T-deflate made it past the first ref_count check before T-hash incremented it.
- T-hash made it past the "owner == DEFLATER_MARKER && contentions <= 0 && ref_count <= 0" check before T-deflate updated 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 sets the contentions field to -max_jint and is about the make the last of the protocol checks.
- T-hash verifies that the object still has a monitor and that monitor still refers to our current ObjectMonitor.
- 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 sees "prev == 0 && owner == DEFLATER_MARKER" and fails to set the ref_count field to -max_jint so it has lost the race.
- T-deflate that "ref_count != 0" and 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-hash saves the ObjectMonitor* in the ObjectMonitorHandle (not shown) and returns to the caller.
- save_om_ptr() returns true since the ObjectMonitor is safe:
- if ObjectMonitor's 'header/dmw' field does not have a hash, then generate a hash and merge it with the 'header/dmw' field.
- Otherwise, extract the hash from the ObjectMonitor's 'header/dmw' field.
- 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.
- T-hash decrements the ref_count field.
- T-hash returns the hash value.
...
This subsection title is NOT a typo. It is was previously possible for both T-deflate and T-hash to lose the race. In the "CR0/v2.00/3-for-jdk13" version of the code, the double loss was not an issue. The addition of "restore obj header" to save_om_ptr() created a bug where the ObjectMonitor can be disconnected from the object without the ObjectMonitor being deflated. This led to a situation where the ObjectMonitor is still on the in-use list and thinks it is owned by the object, but the object does not agree. This rare bug existed in the "CR1/v2.01/4-for-jdk13" version of the code. save_om_ptr() and deflate_monitor_using_JT() have been changed to recognize a large negative ref_count value as a marker that async deflation has won the race. With that change in place, it is no longer possible for both T-deflate and T-hash to lose the same race.
T-hash ObjectMonitor T-deflate
T-hash ObjectMonitor T-deflate
------------------------------- +-----------------------+ -----------------------------------------------
save_om_ptr() { | owner=DEFLATER_MARKER | deflate_monitor_using_JT() {
1> atomic inc ref_count | contentions=-max_jint | cmpxchg(DEFLATER_MARKER, &owner, NULL)
1> if (owner == | ref_count=1 0 | if (waiters != 0 || ref_count != 0) {
DEFLATER_MARKER && +-----------------------+ }
contentions <= 0) { && || prev = cmpxchg(-max_jint, &contentions, 0)
restore obj header \/ 1> ref_count <= 0) { if (prev == 0 &&
atomicrestore decobj ref_countheader +-----------------------+ owner == DEFLATER_MARKER &&
2> return false to | owner=NULL | owner ref_count == 0) {
DEFLATER_MARKER &&
atomic causedec aref_count retry | contentions=0 | } else {
} 1> cmpxchg(-max_jint, &ref_count, 0) == 0) {
return false to | ref_count=0 | cmpxchg(NULL, &owner, DEFLATER_MARKER)} else {
cause a retry +-----------------------+ atomic add max_jint to contentions
cmpxchg(NULL, &owner, DEFLATER_MARKER)
} 2> bailout on deflation
atomic add max_jint to contentions
} bailout on deflation
}
- T-deflate made it past the first ref_count check before T-hash incremented it.
- T-deflate set the contentions field to -max_jint and T-enter incremented the ref_count field.
- 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-hash observes "owner == DEFLATER_MARKER && contentions <= 0" and starts to bail out.
- T-deflate sees "ref_count != 0" and 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-hash restores obj header (not shown) and decrements ref_count.
- 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-hash returns false to cause a retry and when T-hash retries:
- the object's header will still refer to the ObjectMonitor (i.e., not deflated)
- it will observe "owner != DEFLATER_MARKER"
- if the ObjectMonitor's header/dmw does not have a hash, then generate a hash and merge it with the ObjectMonitor's header/dmw.
- Otherwise, extract the hash from the ObjectMonitor's header/dmw and return it.
...
- all the way to the cmpxchg() that makes ref_count a large negative value.
- T-hash is ready to increment ref_count.
- 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.
- If T-deflate makes ref_count a large negative value, then this is the "T-deflate Wins" scenario above.
- If T-hash makes "ref_count == 1", then this is the "T-hash Wins Scenario 2" above.
Please note that in Carsten's original prototype, there was another race in ObjectSynchronizer::FastHashCode() when the object's monitor had to be inflated. The setting of the hashcode in the ObjectMonitor's header/dmw could race with T-deflate. That race is resolved in this version by the use of an ObjectMonitorHandle in the call to ObjectSynchronizer::inflate(). The ObjectMonitor* returned by ObjectMonitorHandle.om_ptr() has a non-zero ref_count so no additional races with T-deflate are possible.
...
Overview
Content Tools