228 return AllocateHeap(size, mtInternal);
229 }
230 void* ObjectMonitor::operator new[] (size_t size) throw() {
231 return operator new (size);
232 }
233 void ObjectMonitor::operator delete(void* p) {
234 FreeHeap(p);
235 }
236 void ObjectMonitor::operator delete[] (void *p) {
237 operator delete(p);
238 }
239
240 // -----------------------------------------------------------------------------
241 // Enter support
242
243 void ObjectMonitor::enter(TRAPS) {
244 // The following code is ordered to check the most common cases first
245 // and to reduce RTS->RTO cache line upgrades on SPARC and IA32 processors.
246 Thread * const Self = THREAD;
247
248 void * cur = Atomic::cmpxchg(Self, &_owner, (void*)NULL);
249 if (cur == NULL) {
250 assert(_recursions == 0, "invariant");
251 return;
252 }
253
254 if (cur == Self) {
255 // TODO-FIXME: check for integer overflow! BUGID 6557169.
256 _recursions++;
257 return;
258 }
259
260 if (Self->is_lock_owned((address)cur)) {
261 assert(_recursions == 0, "internal state error");
262 _recursions = 1;
263 // Commute owner from a thread-specific on-stack BasicLockObject address to
264 // a full-fledged "Thread *".
265 _owner = Self;
266 return;
267 }
268
386
387 // The current thread already owns the monitor and is not going to
388 // call park() for the remainder of the monitor enter protocol. So
389 // it doesn't matter if the JVMTI_EVENT_MONITOR_CONTENDED_ENTERED
390 // event handler consumed an unpark() issued by the thread that
391 // just exited the monitor.
392 }
393 if (event.should_commit()) {
394 event.set_previousOwner((uintptr_t)_previous_owner_tid);
395 event.commit();
396 }
397 OM_PERFDATA_OP(ContendedLockAttempts, inc());
398 }
399
400 // Caveat: TryLock() is not necessarily serializing if it returns failure.
401 // Callers must compensate as needed.
402
403 int ObjectMonitor::TryLock(Thread * Self) {
404 void * own = _owner;
405 if (own != NULL) return 0;
406 if (Atomic::replace_if_null(Self, &_owner)) {
407 assert(_recursions == 0, "invariant");
408 return 1;
409 }
410 // The lock had been free momentarily, but we lost the race to the lock.
411 // Interference -- the CAS failed.
412 // We can either return -1 or retry.
413 // Retry doesn't make as much sense because the lock was just acquired.
414 return -1;
415 }
416
417 // Convert the fields used by is_busy() to a string that can be
418 // used for diagnostic output.
419 const char* ObjectMonitor::is_busy_to_string(stringStream* ss) {
420 ss->print("is_busy: contentions=%d, waiters=%d, owner=" INTPTR_FORMAT
421 ", cxq=" INTPTR_FORMAT ", EntryList=" INTPTR_FORMAT, _contentions,
422 _waiters, p2i(_owner), p2i(_cxq), p2i(_EntryList));
423 return ss->base();
424 }
425
426 #define MAX_RECHECK_INTERVAL 1000
463 //
464 // Node acts as a proxy for Self.
465 // As an aside, if were to ever rewrite the synchronization code mostly
466 // in Java, WaitNodes, ObjectMonitors, and Events would become 1st-class
467 // Java objects. This would avoid awkward lifecycle and liveness issues,
468 // as well as eliminate a subset of ABA issues.
469 // TODO: eliminate ObjectWaiter and enqueue either Threads or Events.
470
471 ObjectWaiter node(Self);
472 Self->_ParkEvent->reset();
473 node._prev = (ObjectWaiter *) 0xBAD;
474 node.TState = ObjectWaiter::TS_CXQ;
475
476 // Push "Self" onto the front of the _cxq.
477 // Once on cxq/EntryList, Self stays on-queue until it acquires the lock.
478 // Note that spinning tends to reduce the rate at which threads
479 // enqueue and dequeue on EntryList|cxq.
480 ObjectWaiter * nxt;
481 for (;;) {
482 node._next = nxt = _cxq;
483 if (Atomic::cmpxchg(&node, &_cxq, nxt) == nxt) break;
484
485 // Interference - the CAS failed because _cxq changed. Just retry.
486 // As an optional optimization we retry the lock.
487 if (TryLock (Self) > 0) {
488 assert(_succ != Self, "invariant");
489 assert(_owner == Self, "invariant");
490 assert(_Responsible != Self, "invariant");
491 return;
492 }
493 }
494
495 // Check for cxq|EntryList edge transition to non-null. This indicates
496 // the onset of contention. While contention persists exiting threads
497 // will use a ST:MEMBAR:LD 1-1 exit protocol. When contention abates exit
498 // operations revert to the faster 1-0 mode. This enter operation may interleave
499 // (race) a concurrent 1-0 exit operation, resulting in stranding, so we
500 // arrange for one of the contending thread to use a timed park() operations
501 // to detect and recover from the race. (Stranding is form of progress failure
502 // where the monitor is unlocked but all the contending threads remain parked).
503 // That is, at least one of the contended threads will periodically poll _owner.
504 // One of the contending threads will become the designated "Responsible" thread.
505 // The Responsible thread uses a timed park instead of a normal indefinite park
506 // operation -- it periodically wakes and checks for and recovers from potential
507 // strandings admitted by 1-0 exit operations. We need at most one Responsible
508 // thread per-monitor at any given moment. Only threads on cxq|EntryList may
509 // be responsible for a monitor.
510 //
511 // Currently, one of the contended threads takes on the added role of "Responsible".
512 // A viable alternative would be to use a dedicated "stranding checker" thread
513 // that periodically iterated over all the threads (or active monitors) and unparked
514 // successors where there was risk of stranding. This would help eliminate the
515 // timer scalability issues we see on some platforms as we'd only have one thread
516 // -- the checker -- parked on a timer.
517
518 if (nxt == NULL && _EntryList == NULL) {
519 // Try to assume the role of responsible thread for the monitor.
520 // CONSIDER: ST vs CAS vs { if (Responsible==null) Responsible=Self }
521 Atomic::replace_if_null(Self, &_Responsible);
522 }
523
524 // The lock might have been released while this thread was occupied queueing
525 // itself onto _cxq. To close the race and avoid "stranding" and
526 // progress-liveness failure we must resample-retry _owner before parking.
527 // Note the Dekker/Lamport duality: ST cxq; MEMBAR; LD Owner.
528 // In this case the ST-MEMBAR is accomplished with CAS().
529 //
530 // TODO: Defer all thread state transitions until park-time.
531 // Since state transitions are heavy and inefficient we'd like
532 // to defer the state transitions until absolutely necessary,
533 // and in doing so avoid some transitions ...
534
535 int nWakeups = 0;
536 int recheckInterval = 1;
537
538 for (;;) {
539
540 if (TryLock(Self) > 0) break;
541 assert(_owner != Self, "invariant");
756 if (SelfNode == _EntryList) _EntryList = nxt;
757 assert(nxt == NULL || nxt->TState == ObjectWaiter::TS_ENTER, "invariant");
758 assert(prv == NULL || prv->TState == ObjectWaiter::TS_ENTER, "invariant");
759 } else {
760 assert(SelfNode->TState == ObjectWaiter::TS_CXQ, "invariant");
761 // Inopportune interleaving -- Self is still on the cxq.
762 // This usually means the enqueue of self raced an exiting thread.
763 // Normally we'll find Self near the front of the cxq, so
764 // dequeueing is typically fast. If needbe we can accelerate
765 // this with some MCS/CHL-like bidirectional list hints and advisory
766 // back-links so dequeueing from the interior will normally operate
767 // in constant-time.
768 // Dequeue Self from either the head (with CAS) or from the interior
769 // with a linear-time scan and normal non-atomic memory operations.
770 // CONSIDER: if Self is on the cxq then simply drain cxq into EntryList
771 // and then unlink Self from EntryList. We have to drain eventually,
772 // so it might as well be now.
773
774 ObjectWaiter * v = _cxq;
775 assert(v != NULL, "invariant");
776 if (v != SelfNode || Atomic::cmpxchg(SelfNode->_next, &_cxq, v) != v) {
777 // The CAS above can fail from interference IFF a "RAT" arrived.
778 // In that case Self must be in the interior and can no longer be
779 // at the head of cxq.
780 if (v == SelfNode) {
781 assert(_cxq != v, "invariant");
782 v = _cxq; // CAS above failed - start scan at head of list
783 }
784 ObjectWaiter * p;
785 ObjectWaiter * q = NULL;
786 for (p = v; p != NULL && p != SelfNode; p = p->_next) {
787 q = p;
788 assert(p->TState == ObjectWaiter::TS_CXQ, "invariant");
789 }
790 assert(v != SelfNode, "invariant");
791 assert(p == SelfNode, "Node not found on cxq");
792 assert(p != _cxq, "invariant");
793 assert(q != NULL, "invariant");
794 assert(q->_next == p, "invariant");
795 q->_next = p->_next;
796 }
942 // Note that spinners in Enter() also set _succ non-null.
943 // In the current implementation spinners opportunistically set
944 // _succ so that exiting threads might avoid waking a successor.
945 // Another less appealing alternative would be for the exiting thread
946 // to drop the lock and then spin briefly to see if a spinner managed
947 // to acquire the lock. If so, the exiting thread could exit
948 // immediately without waking a successor, otherwise the exiting
949 // thread would need to dequeue and wake a successor.
950 // (Note that we'd need to make the post-drop spin short, but no
951 // shorter than the worst-case round-trip cache-line migration time.
952 // The dropped lock needs to become visible to the spinner, and then
953 // the acquisition of the lock by the spinner must become visible to
954 // the exiting thread).
955
956 // It appears that an heir-presumptive (successor) must be made ready.
957 // Only the current lock owner can manipulate the EntryList or
958 // drain _cxq, so we need to reacquire the lock. If we fail
959 // to reacquire the lock the responsibility for ensuring succession
960 // falls to the new owner.
961 //
962 if (!Atomic::replace_if_null(THREAD, &_owner)) {
963 return;
964 }
965
966 guarantee(_owner == THREAD, "invariant");
967
968 ObjectWaiter * w = NULL;
969
970 w = _EntryList;
971 if (w != NULL) {
972 // I'd like to write: guarantee (w->_thread != Self).
973 // But in practice an exiting thread may find itself on the EntryList.
974 // Let's say thread T1 calls O.wait(). Wait() enqueues T1 on O's waitset and
975 // then calls exit(). Exit release the lock by setting O._owner to NULL.
976 // Let's say T1 then stalls. T2 acquires O and calls O.notify(). The
977 // notify() operation moves T1 from O's waitset to O's EntryList. T2 then
978 // release the lock "O". T2 resumes immediately after the ST of null into
979 // _owner, above. T2 notices that the EntryList is populated, so it
980 // reacquires the lock and then finds itself on the EntryList.
981 // Given all that, we have to tolerate the circumstance where "w" is
982 // associated with Self.
983 assert(w->TState == ObjectWaiter::TS_ENTER, "invariant");
984 ExitEpilog(Self, w);
985 return;
986 }
987
988 // If we find that both _cxq and EntryList are null then just
989 // re-run the exit protocol from the top.
990 w = _cxq;
991 if (w == NULL) continue;
992
993 // Drain _cxq into EntryList - bulk transfer.
994 // First, detach _cxq.
995 // The following loop is tantamount to: w = swap(&cxq, NULL)
996 for (;;) {
997 assert(w != NULL, "Invariant");
998 ObjectWaiter * u = Atomic::cmpxchg((ObjectWaiter*)NULL, &_cxq, w);
999 if (u == w) break;
1000 w = u;
1001 }
1002
1003 assert(w != NULL, "invariant");
1004 assert(_EntryList == NULL, "invariant");
1005
1006 // Convert the LIFO SLL anchored by _cxq into a DLL.
1007 // The list reorganization step operates in O(LENGTH(w)) time.
1008 // It's critical that this step operate quickly as
1009 // "Self" still holds the outer-lock, restricting parallelism
1010 // and effectively lengthening the critical section.
1011 // Invariant: s chases t chases u.
1012 // TODO-FIXME: consider changing EntryList from a DLL to a CDLL so
1013 // we have faster access to the tail.
1014
1015 _EntryList = w;
1016 ObjectWaiter * q = NULL;
1017 ObjectWaiter * p;
1018 for (p = w; p != NULL; p = p->_next) {
1442
1443 iterator->_notified = 1;
1444 iterator->_notifier_tid = JFR_THREAD_ID(Self);
1445
1446 ObjectWaiter * list = _EntryList;
1447 if (list != NULL) {
1448 assert(list->_prev == NULL, "invariant");
1449 assert(list->TState == ObjectWaiter::TS_ENTER, "invariant");
1450 assert(list != iterator, "invariant");
1451 }
1452
1453 // prepend to cxq
1454 if (list == NULL) {
1455 iterator->_next = iterator->_prev = NULL;
1456 _EntryList = iterator;
1457 } else {
1458 iterator->TState = ObjectWaiter::TS_CXQ;
1459 for (;;) {
1460 ObjectWaiter * front = _cxq;
1461 iterator->_next = front;
1462 if (Atomic::cmpxchg(iterator, &_cxq, front) == front) {
1463 break;
1464 }
1465 }
1466 }
1467
1468 // _WaitSetLock protects the wait queue, not the EntryList. We could
1469 // move the add-to-EntryList operation, above, outside the critical section
1470 // protected by _WaitSetLock. In practice that's not useful. With the
1471 // exception of wait() timeouts and interrupts the monitor owner
1472 // is the only thread that grabs _WaitSetLock. There's almost no contention
1473 // on _WaitSetLock so it's not profitable to reduce the length of the
1474 // critical section.
1475
1476 iterator->wait_reenter_begin(this);
1477 }
1478 Thread::SpinRelease(&_WaitSetLock);
1479 }
1480
1481 // Consider: a not-uncommon synchronization bug is to use notify() when
1482 // notifyAll() is more appropriate, potentially resulting in stranded
1663 // We periodically check to see if there's a safepoint pending.
1664 if ((ctr & 0xFF) == 0) {
1665 if (SafepointMechanism::should_block(Self)) {
1666 goto Abort; // abrupt spin egress
1667 }
1668 SpinPause();
1669 }
1670
1671 // Probe _owner with TATAS
1672 // If this thread observes the monitor transition or flicker
1673 // from locked to unlocked to locked, then the odds that this
1674 // thread will acquire the lock in this spin attempt go down
1675 // considerably. The same argument applies if the CAS fails
1676 // or if we observe _owner change from one non-null value to
1677 // another non-null value. In such cases we might abort
1678 // the spin without prejudice or apply a "penalty" to the
1679 // spin count-down variable "ctr", reducing it by 100, say.
1680
1681 Thread * ox = (Thread *) _owner;
1682 if (ox == NULL) {
1683 ox = (Thread*)Atomic::cmpxchg(Self, &_owner, (void*)NULL);
1684 if (ox == NULL) {
1685 // The CAS succeeded -- this thread acquired ownership
1686 // Take care of some bookkeeping to exit spin state.
1687 if (_succ == Self) {
1688 _succ = NULL;
1689 }
1690
1691 // Increase _SpinDuration :
1692 // The spin was successful (profitable) so we tend toward
1693 // longer spin attempts in the future.
1694 // CONSIDER: factor "ctr" into the _SpinDuration adjustment.
1695 // If we acquired the lock early in the spin cycle it
1696 // makes sense to increase _SpinDuration proportionally.
1697 // Note that we don't clamp SpinDuration precisely at SpinLimit.
1698 int x = _SpinDuration;
1699 if (x < Knob_SpinLimit) {
1700 if (x < Knob_Poverty) x = Knob_Poverty;
1701 _SpinDuration = x + Knob_Bonus;
1702 }
1703 return 1;
|
228 return AllocateHeap(size, mtInternal);
229 }
230 void* ObjectMonitor::operator new[] (size_t size) throw() {
231 return operator new (size);
232 }
233 void ObjectMonitor::operator delete(void* p) {
234 FreeHeap(p);
235 }
236 void ObjectMonitor::operator delete[] (void *p) {
237 operator delete(p);
238 }
239
240 // -----------------------------------------------------------------------------
241 // Enter support
242
243 void ObjectMonitor::enter(TRAPS) {
244 // The following code is ordered to check the most common cases first
245 // and to reduce RTS->RTO cache line upgrades on SPARC and IA32 processors.
246 Thread * const Self = THREAD;
247
248 void * cur = Atomic::cmpxchg(&_owner, (void*)NULL, Self);
249 if (cur == NULL) {
250 assert(_recursions == 0, "invariant");
251 return;
252 }
253
254 if (cur == Self) {
255 // TODO-FIXME: check for integer overflow! BUGID 6557169.
256 _recursions++;
257 return;
258 }
259
260 if (Self->is_lock_owned((address)cur)) {
261 assert(_recursions == 0, "internal state error");
262 _recursions = 1;
263 // Commute owner from a thread-specific on-stack BasicLockObject address to
264 // a full-fledged "Thread *".
265 _owner = Self;
266 return;
267 }
268
386
387 // The current thread already owns the monitor and is not going to
388 // call park() for the remainder of the monitor enter protocol. So
389 // it doesn't matter if the JVMTI_EVENT_MONITOR_CONTENDED_ENTERED
390 // event handler consumed an unpark() issued by the thread that
391 // just exited the monitor.
392 }
393 if (event.should_commit()) {
394 event.set_previousOwner((uintptr_t)_previous_owner_tid);
395 event.commit();
396 }
397 OM_PERFDATA_OP(ContendedLockAttempts, inc());
398 }
399
400 // Caveat: TryLock() is not necessarily serializing if it returns failure.
401 // Callers must compensate as needed.
402
403 int ObjectMonitor::TryLock(Thread * Self) {
404 void * own = _owner;
405 if (own != NULL) return 0;
406 if (Atomic::replace_if_null(&_owner, Self)) {
407 assert(_recursions == 0, "invariant");
408 return 1;
409 }
410 // The lock had been free momentarily, but we lost the race to the lock.
411 // Interference -- the CAS failed.
412 // We can either return -1 or retry.
413 // Retry doesn't make as much sense because the lock was just acquired.
414 return -1;
415 }
416
417 // Convert the fields used by is_busy() to a string that can be
418 // used for diagnostic output.
419 const char* ObjectMonitor::is_busy_to_string(stringStream* ss) {
420 ss->print("is_busy: contentions=%d, waiters=%d, owner=" INTPTR_FORMAT
421 ", cxq=" INTPTR_FORMAT ", EntryList=" INTPTR_FORMAT, _contentions,
422 _waiters, p2i(_owner), p2i(_cxq), p2i(_EntryList));
423 return ss->base();
424 }
425
426 #define MAX_RECHECK_INTERVAL 1000
463 //
464 // Node acts as a proxy for Self.
465 // As an aside, if were to ever rewrite the synchronization code mostly
466 // in Java, WaitNodes, ObjectMonitors, and Events would become 1st-class
467 // Java objects. This would avoid awkward lifecycle and liveness issues,
468 // as well as eliminate a subset of ABA issues.
469 // TODO: eliminate ObjectWaiter and enqueue either Threads or Events.
470
471 ObjectWaiter node(Self);
472 Self->_ParkEvent->reset();
473 node._prev = (ObjectWaiter *) 0xBAD;
474 node.TState = ObjectWaiter::TS_CXQ;
475
476 // Push "Self" onto the front of the _cxq.
477 // Once on cxq/EntryList, Self stays on-queue until it acquires the lock.
478 // Note that spinning tends to reduce the rate at which threads
479 // enqueue and dequeue on EntryList|cxq.
480 ObjectWaiter * nxt;
481 for (;;) {
482 node._next = nxt = _cxq;
483 if (Atomic::cmpxchg(&_cxq, nxt, &node) == nxt) break;
484
485 // Interference - the CAS failed because _cxq changed. Just retry.
486 // As an optional optimization we retry the lock.
487 if (TryLock (Self) > 0) {
488 assert(_succ != Self, "invariant");
489 assert(_owner == Self, "invariant");
490 assert(_Responsible != Self, "invariant");
491 return;
492 }
493 }
494
495 // Check for cxq|EntryList edge transition to non-null. This indicates
496 // the onset of contention. While contention persists exiting threads
497 // will use a ST:MEMBAR:LD 1-1 exit protocol. When contention abates exit
498 // operations revert to the faster 1-0 mode. This enter operation may interleave
499 // (race) a concurrent 1-0 exit operation, resulting in stranding, so we
500 // arrange for one of the contending thread to use a timed park() operations
501 // to detect and recover from the race. (Stranding is form of progress failure
502 // where the monitor is unlocked but all the contending threads remain parked).
503 // That is, at least one of the contended threads will periodically poll _owner.
504 // One of the contending threads will become the designated "Responsible" thread.
505 // The Responsible thread uses a timed park instead of a normal indefinite park
506 // operation -- it periodically wakes and checks for and recovers from potential
507 // strandings admitted by 1-0 exit operations. We need at most one Responsible
508 // thread per-monitor at any given moment. Only threads on cxq|EntryList may
509 // be responsible for a monitor.
510 //
511 // Currently, one of the contended threads takes on the added role of "Responsible".
512 // A viable alternative would be to use a dedicated "stranding checker" thread
513 // that periodically iterated over all the threads (or active monitors) and unparked
514 // successors where there was risk of stranding. This would help eliminate the
515 // timer scalability issues we see on some platforms as we'd only have one thread
516 // -- the checker -- parked on a timer.
517
518 if (nxt == NULL && _EntryList == NULL) {
519 // Try to assume the role of responsible thread for the monitor.
520 // CONSIDER: ST vs CAS vs { if (Responsible==null) Responsible=Self }
521 Atomic::replace_if_null(&_Responsible, Self);
522 }
523
524 // The lock might have been released while this thread was occupied queueing
525 // itself onto _cxq. To close the race and avoid "stranding" and
526 // progress-liveness failure we must resample-retry _owner before parking.
527 // Note the Dekker/Lamport duality: ST cxq; MEMBAR; LD Owner.
528 // In this case the ST-MEMBAR is accomplished with CAS().
529 //
530 // TODO: Defer all thread state transitions until park-time.
531 // Since state transitions are heavy and inefficient we'd like
532 // to defer the state transitions until absolutely necessary,
533 // and in doing so avoid some transitions ...
534
535 int nWakeups = 0;
536 int recheckInterval = 1;
537
538 for (;;) {
539
540 if (TryLock(Self) > 0) break;
541 assert(_owner != Self, "invariant");
756 if (SelfNode == _EntryList) _EntryList = nxt;
757 assert(nxt == NULL || nxt->TState == ObjectWaiter::TS_ENTER, "invariant");
758 assert(prv == NULL || prv->TState == ObjectWaiter::TS_ENTER, "invariant");
759 } else {
760 assert(SelfNode->TState == ObjectWaiter::TS_CXQ, "invariant");
761 // Inopportune interleaving -- Self is still on the cxq.
762 // This usually means the enqueue of self raced an exiting thread.
763 // Normally we'll find Self near the front of the cxq, so
764 // dequeueing is typically fast. If needbe we can accelerate
765 // this with some MCS/CHL-like bidirectional list hints and advisory
766 // back-links so dequeueing from the interior will normally operate
767 // in constant-time.
768 // Dequeue Self from either the head (with CAS) or from the interior
769 // with a linear-time scan and normal non-atomic memory operations.
770 // CONSIDER: if Self is on the cxq then simply drain cxq into EntryList
771 // and then unlink Self from EntryList. We have to drain eventually,
772 // so it might as well be now.
773
774 ObjectWaiter * v = _cxq;
775 assert(v != NULL, "invariant");
776 if (v != SelfNode || Atomic::cmpxchg(&_cxq, v, SelfNode->_next) != v) {
777 // The CAS above can fail from interference IFF a "RAT" arrived.
778 // In that case Self must be in the interior and can no longer be
779 // at the head of cxq.
780 if (v == SelfNode) {
781 assert(_cxq != v, "invariant");
782 v = _cxq; // CAS above failed - start scan at head of list
783 }
784 ObjectWaiter * p;
785 ObjectWaiter * q = NULL;
786 for (p = v; p != NULL && p != SelfNode; p = p->_next) {
787 q = p;
788 assert(p->TState == ObjectWaiter::TS_CXQ, "invariant");
789 }
790 assert(v != SelfNode, "invariant");
791 assert(p == SelfNode, "Node not found on cxq");
792 assert(p != _cxq, "invariant");
793 assert(q != NULL, "invariant");
794 assert(q->_next == p, "invariant");
795 q->_next = p->_next;
796 }
942 // Note that spinners in Enter() also set _succ non-null.
943 // In the current implementation spinners opportunistically set
944 // _succ so that exiting threads might avoid waking a successor.
945 // Another less appealing alternative would be for the exiting thread
946 // to drop the lock and then spin briefly to see if a spinner managed
947 // to acquire the lock. If so, the exiting thread could exit
948 // immediately without waking a successor, otherwise the exiting
949 // thread would need to dequeue and wake a successor.
950 // (Note that we'd need to make the post-drop spin short, but no
951 // shorter than the worst-case round-trip cache-line migration time.
952 // The dropped lock needs to become visible to the spinner, and then
953 // the acquisition of the lock by the spinner must become visible to
954 // the exiting thread).
955
956 // It appears that an heir-presumptive (successor) must be made ready.
957 // Only the current lock owner can manipulate the EntryList or
958 // drain _cxq, so we need to reacquire the lock. If we fail
959 // to reacquire the lock the responsibility for ensuring succession
960 // falls to the new owner.
961 //
962 if (!Atomic::replace_if_null(&_owner, THREAD)) {
963 return;
964 }
965
966 guarantee(_owner == THREAD, "invariant");
967
968 ObjectWaiter * w = NULL;
969
970 w = _EntryList;
971 if (w != NULL) {
972 // I'd like to write: guarantee (w->_thread != Self).
973 // But in practice an exiting thread may find itself on the EntryList.
974 // Let's say thread T1 calls O.wait(). Wait() enqueues T1 on O's waitset and
975 // then calls exit(). Exit release the lock by setting O._owner to NULL.
976 // Let's say T1 then stalls. T2 acquires O and calls O.notify(). The
977 // notify() operation moves T1 from O's waitset to O's EntryList. T2 then
978 // release the lock "O". T2 resumes immediately after the ST of null into
979 // _owner, above. T2 notices that the EntryList is populated, so it
980 // reacquires the lock and then finds itself on the EntryList.
981 // Given all that, we have to tolerate the circumstance where "w" is
982 // associated with Self.
983 assert(w->TState == ObjectWaiter::TS_ENTER, "invariant");
984 ExitEpilog(Self, w);
985 return;
986 }
987
988 // If we find that both _cxq and EntryList are null then just
989 // re-run the exit protocol from the top.
990 w = _cxq;
991 if (w == NULL) continue;
992
993 // Drain _cxq into EntryList - bulk transfer.
994 // First, detach _cxq.
995 // The following loop is tantamount to: w = swap(&cxq, NULL)
996 for (;;) {
997 assert(w != NULL, "Invariant");
998 ObjectWaiter * u = Atomic::cmpxchg(&_cxq, w, (ObjectWaiter*)NULL);
999 if (u == w) break;
1000 w = u;
1001 }
1002
1003 assert(w != NULL, "invariant");
1004 assert(_EntryList == NULL, "invariant");
1005
1006 // Convert the LIFO SLL anchored by _cxq into a DLL.
1007 // The list reorganization step operates in O(LENGTH(w)) time.
1008 // It's critical that this step operate quickly as
1009 // "Self" still holds the outer-lock, restricting parallelism
1010 // and effectively lengthening the critical section.
1011 // Invariant: s chases t chases u.
1012 // TODO-FIXME: consider changing EntryList from a DLL to a CDLL so
1013 // we have faster access to the tail.
1014
1015 _EntryList = w;
1016 ObjectWaiter * q = NULL;
1017 ObjectWaiter * p;
1018 for (p = w; p != NULL; p = p->_next) {
1442
1443 iterator->_notified = 1;
1444 iterator->_notifier_tid = JFR_THREAD_ID(Self);
1445
1446 ObjectWaiter * list = _EntryList;
1447 if (list != NULL) {
1448 assert(list->_prev == NULL, "invariant");
1449 assert(list->TState == ObjectWaiter::TS_ENTER, "invariant");
1450 assert(list != iterator, "invariant");
1451 }
1452
1453 // prepend to cxq
1454 if (list == NULL) {
1455 iterator->_next = iterator->_prev = NULL;
1456 _EntryList = iterator;
1457 } else {
1458 iterator->TState = ObjectWaiter::TS_CXQ;
1459 for (;;) {
1460 ObjectWaiter * front = _cxq;
1461 iterator->_next = front;
1462 if (Atomic::cmpxchg(&_cxq, front, iterator) == front) {
1463 break;
1464 }
1465 }
1466 }
1467
1468 // _WaitSetLock protects the wait queue, not the EntryList. We could
1469 // move the add-to-EntryList operation, above, outside the critical section
1470 // protected by _WaitSetLock. In practice that's not useful. With the
1471 // exception of wait() timeouts and interrupts the monitor owner
1472 // is the only thread that grabs _WaitSetLock. There's almost no contention
1473 // on _WaitSetLock so it's not profitable to reduce the length of the
1474 // critical section.
1475
1476 iterator->wait_reenter_begin(this);
1477 }
1478 Thread::SpinRelease(&_WaitSetLock);
1479 }
1480
1481 // Consider: a not-uncommon synchronization bug is to use notify() when
1482 // notifyAll() is more appropriate, potentially resulting in stranded
1663 // We periodically check to see if there's a safepoint pending.
1664 if ((ctr & 0xFF) == 0) {
1665 if (SafepointMechanism::should_block(Self)) {
1666 goto Abort; // abrupt spin egress
1667 }
1668 SpinPause();
1669 }
1670
1671 // Probe _owner with TATAS
1672 // If this thread observes the monitor transition or flicker
1673 // from locked to unlocked to locked, then the odds that this
1674 // thread will acquire the lock in this spin attempt go down
1675 // considerably. The same argument applies if the CAS fails
1676 // or if we observe _owner change from one non-null value to
1677 // another non-null value. In such cases we might abort
1678 // the spin without prejudice or apply a "penalty" to the
1679 // spin count-down variable "ctr", reducing it by 100, say.
1680
1681 Thread * ox = (Thread *) _owner;
1682 if (ox == NULL) {
1683 ox = (Thread*)Atomic::cmpxchg(&_owner, (void*)NULL, Self);
1684 if (ox == NULL) {
1685 // The CAS succeeded -- this thread acquired ownership
1686 // Take care of some bookkeeping to exit spin state.
1687 if (_succ == Self) {
1688 _succ = NULL;
1689 }
1690
1691 // Increase _SpinDuration :
1692 // The spin was successful (profitable) so we tend toward
1693 // longer spin attempts in the future.
1694 // CONSIDER: factor "ctr" into the _SpinDuration adjustment.
1695 // If we acquired the lock early in the spin cycle it
1696 // makes sense to increase _SpinDuration proportionally.
1697 // Note that we don't clamp SpinDuration precisely at SpinLimit.
1698 int x = _SpinDuration;
1699 if (x < Knob_SpinLimit) {
1700 if (x < Knob_Poverty) x = Knob_Poverty;
1701 _SpinDuration = x + Knob_Bonus;
1702 }
1703 return 1;
|