vm/runtime/mutex.cpp

51 //   queue -- called the cxq -- with CAS and then spin/park.
53 //   of the cxq.  Colocating the LockByte with the cxq precludes certain races.
82 //   -- The contention queue (cxq) contains recently-arrived threads (RATs).
83 //      Threads on the cxq eventually drain into the EntryList.
84 //   -- Invariant: a thread appears on at most one list -- cxq, EntryList
121 // * The cxq can have multiple concurrent "pushers" but only one concurrent
123 //   More precisely, the CAS-based "push" onto cxq is ABA-oblivious.
127 // * Taken together, the cxq and the EntryList constitute or form a
130 //   Threads in lock() enqueue onto cxq while threads in unlock() will
143 //   drains the cxq into the EntryList, and orders or reorders the threads on the
152 //       unlinked from the EntryList and cxq by some previous unlock() operations.
155 //   --  Threads on the EntryList or cxq are _not allowed to attempt lock acquisition.
160 //       drain the cxq into the EntryList.  By convention, only this thread, the holder of
162 //       RATs on the cxq into the EntryList.  This avoids ABA corruption on the cxq as
179 //   transfers threads from the WaitSet to either the EntryList or cxq.
429       if (u == v) return 0;        // indicate pushed onto cxq
460   // Either Enqueue Self on cxq or acquire the outer lock.
461   // LockWord encoding = (cxq,LOCKBYTE)
473   // ondeck implies not resident on cxq and not resident on EntryList
489     // preemptively drain the cxq into the EntryList.
552   intptr_t cxq = _LockWord.FullWord;
553   if (((cxq & ~_LBIT)|UNS(_EntryList)) == 0) {
554     return;      // normal fast-path exit - cxq and EntryList both empty
556   if (cxq & _LBIT) {
565   // OnDeck serves as lock to protect cxq and EntryList.
566   // Only the holder of OnDeck can manipulate EntryList or detach the RATs from cxq.
604     cxq = _LockWord.FullWord;
605     if (cxq & _LBIT) return;
611   cxq = _LockWord.FullWord;
612   if ((cxq & ~_LBIT) != 0) {
613     // The EntryList is empty but the cxq is populated.
614     // drain RATs from cxq into EntryList
618       if (cxq & _LBIT) goto Punt;
619       const intptr_t vfy = CASPTR(&_LockWord, cxq, cxq & _LBIT);
620       if (vfy == cxq) break;
621       cxq = vfy;
624       // pushing themselves onto the cxq or from lock-unlock operations.
626       // the cxq is prepend-only -- the head is volatile but the interior
627       // of the cxq is stable.  In theory if we encounter interference from threads
628       // pushing onto cxq we could simply break off the original cxq suffix and
630       // on the high-traffic LockWord variable.   For instance lets say the cxq is "ABCD"
631       // when we first fetch cxq above.  Between the fetch -- where we observed "A"
633       // yielding cxq = "PQRABCD".  In this case we could simply set A.ListNext
634       // null, leaving cxq = "PQRA" and transfer the "BCD" segment to the EntryList.
635       // Note too, that it's safe for this thread to traverse the cxq
639     // We don't currently reorder the cxq segment as we move it onto
644     _EntryList = List = (ParkEvent *)(cxq & ~_LBIT);
649   // cxq|EntryList is empty.
650   // w == NULL implies that cxq|EntryList == NULL in the past.
652   // A thread could have added itself to cxq since this thread previously checked.
653   // Detect and recover by refetching cxq.
659   // Resample LockWord/cxq to recover from possible race.
662   // lock, but encounter contention and enqueue itself on cxq.  T2 then drops the
666   // Note that we don't need to recheck EntryList, just cxq.
669   cxq = _LockWord.FullWord;
670   if ((cxq & ~_LBIT) != 0 && (cxq & _LBIT) == 0) {
682   // Transfer one thread from the WaitSet to the EntryList or cxq.
683   // Currently we just unlink the head of the WaitSet and prepend to the cxq.
691     // push nfy onto the cxq
699     // Note that setting Notified before pushing nfy onto the cxq is
716 // to the cxq.  This could be done more efficiently with a single bulk en-mass transfer,
719 // waitset is "ABCD" and the cxq is "XYZ".  After a notifyAll() the waitset
720 // will be empty and the cxq will be "DCBAXYZ".  This is benign, of course.
749   // on both the WaitSet and the EntryList|cxq at the same time..  That is, a thread
780   // T1 from the WaitSet to the cxq.  T2 then drops the lock.  T1 resumes,
781   // and then finds *itself* on the cxq.  During the course of a normal
783   // or cxq, but in the case of wait() it's possible.
800   // 2. On the cxq or EntryList
801   // 3. Not resident on cxq, EntryList or WaitSet, but in the OnDeck position.
812       // end up on the cxq|EntryList -- it can't be on two lists at once.
839     // A prior notify() operation moved ESelf from the WaitSet to the cxq.
840     // ESelf is now on the cxq, EntryList or at the OnDeck position.
1050   // Either Enqueue Self on cxq or acquire the outer lock.
1057   // ondeck implies not resident on cxq and not resident on EntryList