- Loading...
Page History
...
- The data fields are at their starting values.
- T-deflate is about to execute cmpxchg().
- T-enter hasn't done anything yet.
...
ObjectMonitor T-deflate
T-enter +-----------------------+ --------------------------------------
---------------- | owner=DEFLATER_MARKER | cmpxchg(DEFLATER_MARKER, &owner, NULL)
owner contended | count=-max_jint | :
atomic inc count +-----------------------+ prev = cmpxchg(-max_jint, &count, 0)
if (count <= 0 && owner if (prev == 0 &&
== DEFLATER_MARKER) { owner == DEFLATER_MARKER) {
restore header restore object header
retry enter finish the deflation
} }
- This diagram starts after "Racing Threads".
- T-enter and T-deflate both observe owner == DEFLATER_MARKER and a negative count field.
- T-enter has lost the race and it retries.
- T-deflate finishes deflation of the ObjectMonitor.
T-enter Wins
ObjectMonitor T-deflate
T-enter +-----------------------+ ----------------------------------------
---------------- | owner=DEFLATER_MARKER | cmpxchg(DEFLATER_MARKER, &owner, NULL)
owner contended | count=1 | :
atomic inc count +-----------------------+ prev = cmpxchg(-max_jint, &count, 0)
if (count > 0) if (prev != 0 ||
do contended owner != DEFLATER_MARKER)
enter work bailout on deflation (nothing to undo)
...
- The return value from cmpxchg() in each thread will be different.
- Since T-deflate won the race, its 'dmw' variable contains the header/dmw from the ObjectMonitor.
- Since T-enter lost the race, its 'dmw' variable contains the 'marked_dmw' set by T-deflate.
- T-enter will unmark its 'dmw' variable.
- Both threads are poised to call cas_set_mark() at the same time.
...
- This diagram is the same as "T-deflate Wins First Race" except we've swapped the post cmpxchg() comments.
- Since T-enter won the race, its 'dmw' variable contains the header/dmw from the ObjectMonitor.
- Since T-deflate lost the race, its 'dmw' variable contains the 'marked_dmw' set by T-enter.
- T-deflate will unmark its 'dmw' variable.
- Both threads are poised to call cas_set_mark() at the same time.
...
T-hash ObjectMonitor T-deflate
---------------------- +-----------------------+ --------------------------------------
save_om_ptr() { | owner=NULL | cmpxchg(DEFLATER_MARKER, &owner, NULL)
: | count=0 |
atomic inc ref_count | ref_count=0 |
+-----------------------+
- The data fields are at their starting values.
- T-deflate is about to execute cmpxchg().
- T-hash is about to increment ref_count.
Racing Threads
T-hash ObjectMonitor T-deflate
---------------------- +-----------------------+ --------------------------------------
save_om_ptr() { | owner=DEFLATER_MARKER | cmpxchg(DEFLATER_MARKER, &owner, NULL)
: | count=0 | if (waiters != 0 or ref_count != 0) {
atomic inc ref_count | ref_count=1 | }
+-----------------------+ prev = cmpxchg(-max_jint, &count, 0)
- T-deflate has set the owner field to DEFLATER_MARKER.
- T-deflate is about to check the waiters and ref_count fields.
- T-hash is about to inc the ref_count field.
T-deflate Wins
T-hash ObjectMonitor T-deflate
------------------------ +-----------------------+ --------------------------------------
save_om_ptr() { | owner=DEFLATER_MARKER | cmpxchg(DEFLATER_MARKER, &owner, NULL)
atomic inc ref_count | count=-max_jint | if (waiters != 0 or ref_count != 0) {
if (owner == | ref_count=0 1 | }
DEFLATER_MARKER) { +-----------------------+ prev = cmpxchg(-max_jint, &count, 0)
atomic dec ref_count count || if (prev == 0 &&
return false to to \/ owner == DEFLATER_MARKER) {
cause a retry restore header
} finish the deflation
}
T-hash Wins
T-hash ObjectMonitor T-deflate
------------------------ retry +-----------------------+ ----------------------------------------
save_om_ptr() { | owner=NULL | cmpxchg(DEFLATER_MARKER, &owner, NULL)
atomic inc ref_count | count=0 | if (waiters != 0 or ref_count != 0) {
if (owner == restore object header
} | owner=DEFLATER_MARKER | finish the deflation
| count=-max_jint | }
| ref_count=1 | cmpxchg(NULL, &owner, DEFLATER_MARKER)
DEFLATER_MARKER) { 0 |
+-----------------------+ return false to cause a retry
} }
if (object no longer prev = cmpxchg(-max_jint, &count, 0)
has a monitor or
is a different
monitor) {
- T-deflate made it past the ref_count check before T-hash incremented it.
- T-deflate set the count field to -max_jint and T-enter incremented the ref_count field.
- The first ObjectMonitor box is showing the fields at this point.
- T-deflate has won the race so it restores object header (not shown) and finishes the deflation.
- T-hash observes "owner == DEFLATER_MARKER" so it decrements ref_count and returns false to cause a retry.
- The second ObjectMonitor box is showing the fields at this point.
- When T-hash retries:
- if it observes "owner == DEFLATER_MARKER" it will retry again.
- if it observes the restored object header:
- if the object's header does not have a hash, then generate a hash and merge it with the object's header.
- extract the hash from the object's header and return it.
T-hash Wins
If T-hash wins the race, then the ref_count will cause T-deflate to bail out on deflating the monitor which is what this diagram shows; ref_count is not mentioned in any of the previous examples for simplicity.
T-hash ObjectMonitor T-deflate
------------------------ +-----------------------+ ----------------------------------------
save_om_ptr() { | header=dmw_no_hash | cmpxchg(DEFLATER_MARKER, &owner, NULL)
atomic inc ref_count | owner=DEFLATER_MARKER | if (waiters != 0 or ref_count != 0) {
if (owner == | count=0 | cmpxchg(NULL, &owner, DEFLATER_MARKER)
DEFLATER_MARKER) { | ref_count=1 | bailout on deflation
} +-----------------------+ }
if (object no longer || prev = cmpxchg(-max_jint, &count, 0)
has a monitor or \/
is a different +-----------------------+
monitor) { | header=dmw_no_hash |
atomic dec ref_count | owner=NULL |
return false to | count=0 |
cause a retry | ref_count=1 |
} +-----------------------+
save om_ptr in the ||
ObjectMonitorHandle \/
} +-----------------------+
if save_om_ptr() { | header=dmw_hash |
if no hash | owner=NULL |
gen hash & merge | count=0 |
hash = hash(header) | ref_count=1 |
} +-----------------------+
atomic dec ref_count
return false to
cause a retry
}
save om_ptr in the
ObjectMonitorHandle
}
If T-hash wins the first race, then the ref_count will cause T-deflate to bail out on deflating the monitor; ref_count is not mentioned in any of the previous examples for simplicity. If T-deflate wins the race, then T-hash will retry which will bring us to the second race.
In the second T-hash versus T-deflate race, T-deflate is trying to restore the object's header/mark from the ObjectMonitor*'s header/dmw field and T-hash is trying to read a stable mark value from the object's header/mark that will allow it to get/set a hash code. When T-hash reads a stable mark value:
...
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.
- 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" 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.
- if save_om_ptr() returned true 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.
- extract the hash from the ObjectMonitor's 'header/dmw' field.
- The third ObjectMonitor box is showing the fields at this point.
- T-hash decrements the ref_count field.
- T-hash returns the hash value
...
- .
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 hash code 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