217 // CAS-based "push" used to enqueue recently arrived threads (RATs).
218 //
219 // * Concurrency invariants:
220 //
221 // -- only the monitor owner may access or mutate the EntryList.
222 // The mutex property of the monitor itself protects the EntryList
223 // from concurrent interference.
224 // -- Only the monitor owner may detach the cxq.
225 //
226 // * The monitor entry list operations avoid locks, but strictly speaking
227 // they're not lock-free. Enter is lock-free, exit is not.
228 // See http://j2se.east/~dice/PERSIST/040825-LockFreeQueues.html
229 //
230 // * The cxq can have multiple concurrent "pushers" but only one concurrent
231 // detaching thread. This mechanism is immune from the ABA corruption.
232 // More precisely, the CAS-based "push" onto cxq is ABA-oblivious.
233 //
234 // * Taken together, the cxq and the EntryList constitute or form a
235 // single logical queue of threads stalled trying to acquire the lock.
236 // We use two distinct lists to improve the odds of a constant-time
237 // dequeue operation after acquisition (in the ::enter() epilog) and
238 // to reduce heat on the list ends. (c.f. Michael Scott's "2Q" algorithm).
239 // A key desideratum is to minimize queue & monitor metadata manipulation
240 // that occurs while holding the monitor lock -- that is, we want to
241 // minimize monitor lock holds times. Note that even a small amount of
242 // fixed spinning will greatly reduce the # of enqueue-dequeue operations
243 // on EntryList|cxq. That is, spinning relieves contention on the "inner"
244 // locks and monitor metadata.
245 //
246 // Cxq points to the the set of Recently Arrived Threads attempting entry.
247 // Because we push threads onto _cxq with CAS, the RATs must take the form of
248 // a singly-linked LIFO. We drain _cxq into EntryList at unlock-time when
249 // the unlocking thread notices that EntryList is null but _cxq is != null.
250 //
251 // The EntryList is ordered by the prevailing queue discipline and
252 // can be organized in any convenient fashion, such as a doubly-linked list or
253 // a circular doubly-linked list. Critically, we want insert and delete operations
254 // to operate in constant-time. If we need a priority queue then something akin
255 // to Solaris' sleepq would work nicely. Viz.,
256 // http://agg.eng/ws/on10_nightly/source/usr/src/uts/common/os/sleepq.c.
257 // Queue discipline is enforced at ::exit() time, when the unlocking thread
660 // guarantee (((oop)(object()))->mark() == markOopDesc::encode(this), "invariant") ;
661 // but as we're at a safepoint that's not safe.
662
663 UnlinkAfterAcquire (Self, &node) ;
664 if (_succ == Self) _succ = NULL ;
665
666 assert (_succ != Self, "invariant") ;
667 if (_Responsible == Self) {
668 _Responsible = NULL ;
669 OrderAccess::fence(); // Dekker pivot-point
670
671 // We may leave threads on cxq|EntryList without a designated
672 // "Responsible" thread. This is benign. When this thread subsequently
673 // exits the monitor it can "see" such preexisting "old" threads --
674 // threads that arrived on the cxq|EntryList before the fence, above --
675 // by LDing cxq|EntryList. Newly arrived threads -- that is, threads
676 // that arrive on cxq after the ST:MEMBAR, above -- will set Responsible
677 // non-null and elect a new "Responsible" timer thread.
678 //
679 // This thread executes:
680 // ST Responsible=null; MEMBAR (in enter epilog - here)
681 // LD cxq|EntryList (in subsequent exit)
682 //
683 // Entering threads in the slow/contended path execute:
684 // ST cxq=nonnull; MEMBAR; LD Responsible (in enter prolog)
685 // The (ST cxq; MEMBAR) is accomplished with CAS().
686 //
687 // The MEMBAR, above, prevents the LD of cxq|EntryList in the subsequent
688 // exit operation from floating above the ST Responsible=null.
689 }
690
691 // We've acquired ownership with CAS().
692 // CAS is serializing -- it has MEMBAR/FENCE-equivalent semantics.
693 // But since the CAS() this thread may have also stored into _succ,
694 // EntryList, cxq or Responsible. These meta-data updates must be
695 // visible __before this thread subsequently drops the lock.
696 // Consider what could occur if we didn't enforce this constraint --
697 // STs to monitor meta-data and user-data could reorder with (become
698 // visible after) the ST in exit that drops ownership of the lock.
699 // Some other thread could then acquire the lock, but observe inconsistent
700 // or old monitor meta-data and heap data. That violates the JMM.
2014 // the # of failed spin attempts (or iterations) reaches some threshold.
2015 // This takes us into the realm of 1-out-of-N spinning, where we
2016 // hold the duration constant but vary the frequency.
2017
2018 ctr = _SpinDuration ;
2019 if (ctr < Knob_SpinBase) ctr = Knob_SpinBase ;
2020 if (ctr <= 0) return 0 ;
2021
2022 if (Knob_SuccRestrict && _succ != NULL) return 0 ;
2023 if (Knob_OState && NotRunnable (Self, (Thread *) _owner)) {
2024 TEVENT (Spin abort - notrunnable [TOP]);
2025 return 0 ;
2026 }
2027
2028 int MaxSpin = Knob_MaxSpinners ;
2029 if (MaxSpin >= 0) {
2030 if (_Spinner > MaxSpin) {
2031 TEVENT (Spin abort -- too many spinners) ;
2032 return 0 ;
2033 }
2034 // Slighty racy, but benign ...
2035 Adjust (&_Spinner, 1) ;
2036 }
2037
2038 // We're good to spin ... spin ingress.
2039 // CONSIDER: use Prefetch::write() to avoid RTS->RTO upgrades
2040 // when preparing to LD...CAS _owner, etc and the CAS is likely
2041 // to succeed.
2042 int hits = 0 ;
2043 int msk = 0 ;
2044 int caspty = Knob_CASPenalty ;
2045 int oxpty = Knob_OXPenalty ;
2046 int sss = Knob_SpinSetSucc ;
2047 if (sss && _succ == NULL ) _succ = Self ;
2048 Thread * prv = NULL ;
2049
2050 // There are three ways to exit the following loop:
2051 // 1. A successful spin where this thread has acquired the lock.
2052 // 2. Spin failure with prejudice
2053 // 3. Spin failure without prejudice
2054
|
217 // CAS-based "push" used to enqueue recently arrived threads (RATs).
218 //
219 // * Concurrency invariants:
220 //
221 // -- only the monitor owner may access or mutate the EntryList.
222 // The mutex property of the monitor itself protects the EntryList
223 // from concurrent interference.
224 // -- Only the monitor owner may detach the cxq.
225 //
226 // * The monitor entry list operations avoid locks, but strictly speaking
227 // they're not lock-free. Enter is lock-free, exit is not.
228 // See http://j2se.east/~dice/PERSIST/040825-LockFreeQueues.html
229 //
230 // * The cxq can have multiple concurrent "pushers" but only one concurrent
231 // detaching thread. This mechanism is immune from the ABA corruption.
232 // More precisely, the CAS-based "push" onto cxq is ABA-oblivious.
233 //
234 // * Taken together, the cxq and the EntryList constitute or form a
235 // single logical queue of threads stalled trying to acquire the lock.
236 // We use two distinct lists to improve the odds of a constant-time
237 // dequeue operation after acquisition (in the ::enter() epilogue) and
238 // to reduce heat on the list ends. (c.f. Michael Scott's "2Q" algorithm).
239 // A key desideratum is to minimize queue & monitor metadata manipulation
240 // that occurs while holding the monitor lock -- that is, we want to
241 // minimize monitor lock holds times. Note that even a small amount of
242 // fixed spinning will greatly reduce the # of enqueue-dequeue operations
243 // on EntryList|cxq. That is, spinning relieves contention on the "inner"
244 // locks and monitor metadata.
245 //
246 // Cxq points to the the set of Recently Arrived Threads attempting entry.
247 // Because we push threads onto _cxq with CAS, the RATs must take the form of
248 // a singly-linked LIFO. We drain _cxq into EntryList at unlock-time when
249 // the unlocking thread notices that EntryList is null but _cxq is != null.
250 //
251 // The EntryList is ordered by the prevailing queue discipline and
252 // can be organized in any convenient fashion, such as a doubly-linked list or
253 // a circular doubly-linked list. Critically, we want insert and delete operations
254 // to operate in constant-time. If we need a priority queue then something akin
255 // to Solaris' sleepq would work nicely. Viz.,
256 // http://agg.eng/ws/on10_nightly/source/usr/src/uts/common/os/sleepq.c.
257 // Queue discipline is enforced at ::exit() time, when the unlocking thread
660 // guarantee (((oop)(object()))->mark() == markOopDesc::encode(this), "invariant") ;
661 // but as we're at a safepoint that's not safe.
662
663 UnlinkAfterAcquire (Self, &node) ;
664 if (_succ == Self) _succ = NULL ;
665
666 assert (_succ != Self, "invariant") ;
667 if (_Responsible == Self) {
668 _Responsible = NULL ;
669 OrderAccess::fence(); // Dekker pivot-point
670
671 // We may leave threads on cxq|EntryList without a designated
672 // "Responsible" thread. This is benign. When this thread subsequently
673 // exits the monitor it can "see" such preexisting "old" threads --
674 // threads that arrived on the cxq|EntryList before the fence, above --
675 // by LDing cxq|EntryList. Newly arrived threads -- that is, threads
676 // that arrive on cxq after the ST:MEMBAR, above -- will set Responsible
677 // non-null and elect a new "Responsible" timer thread.
678 //
679 // This thread executes:
680 // ST Responsible=null; MEMBAR (in enter epilogue - here)
681 // LD cxq|EntryList (in subsequent exit)
682 //
683 // Entering threads in the slow/contended path execute:
684 // ST cxq=nonnull; MEMBAR; LD Responsible (in enter prolog)
685 // The (ST cxq; MEMBAR) is accomplished with CAS().
686 //
687 // The MEMBAR, above, prevents the LD of cxq|EntryList in the subsequent
688 // exit operation from floating above the ST Responsible=null.
689 }
690
691 // We've acquired ownership with CAS().
692 // CAS is serializing -- it has MEMBAR/FENCE-equivalent semantics.
693 // But since the CAS() this thread may have also stored into _succ,
694 // EntryList, cxq or Responsible. These meta-data updates must be
695 // visible __before this thread subsequently drops the lock.
696 // Consider what could occur if we didn't enforce this constraint --
697 // STs to monitor meta-data and user-data could reorder with (become
698 // visible after) the ST in exit that drops ownership of the lock.
699 // Some other thread could then acquire the lock, but observe inconsistent
700 // or old monitor meta-data and heap data. That violates the JMM.
2014 // the # of failed spin attempts (or iterations) reaches some threshold.
2015 // This takes us into the realm of 1-out-of-N spinning, where we
2016 // hold the duration constant but vary the frequency.
2017
2018 ctr = _SpinDuration ;
2019 if (ctr < Knob_SpinBase) ctr = Knob_SpinBase ;
2020 if (ctr <= 0) return 0 ;
2021
2022 if (Knob_SuccRestrict && _succ != NULL) return 0 ;
2023 if (Knob_OState && NotRunnable (Self, (Thread *) _owner)) {
2024 TEVENT (Spin abort - notrunnable [TOP]);
2025 return 0 ;
2026 }
2027
2028 int MaxSpin = Knob_MaxSpinners ;
2029 if (MaxSpin >= 0) {
2030 if (_Spinner > MaxSpin) {
2031 TEVENT (Spin abort -- too many spinners) ;
2032 return 0 ;
2033 }
2034 // Slightly racy, but benign ...
2035 Adjust (&_Spinner, 1) ;
2036 }
2037
2038 // We're good to spin ... spin ingress.
2039 // CONSIDER: use Prefetch::write() to avoid RTS->RTO upgrades
2040 // when preparing to LD...CAS _owner, etc and the CAS is likely
2041 // to succeed.
2042 int hits = 0 ;
2043 int msk = 0 ;
2044 int caspty = Knob_CASPenalty ;
2045 int oxpty = Knob_OXPenalty ;
2046 int sss = Knob_SpinSetSucc ;
2047 if (sss && _succ == NULL ) _succ = Self ;
2048 Thread * prv = NULL ;
2049
2050 // There are three ways to exit the following loop:
2051 // 1. A successful spin where this thread has acquired the lock.
2052 // 2. Spin failure with prejudice
2053 // 3. Spin failure without prejudice
2054
|