absl: requeue waiters as LIFO

Currently if a thread already blocked on a Mutex,
but then failed to acquire the Mutex, we queue it in FIFO order again.
As the result unlucky threads can suffer bad latency
if they are requeued several times.
The least we can do for them is to queue in LIFO order after blocking.

PiperOrigin-RevId: 566478783
Change-Id: I8bac08325f20ff6ccc2658e04e1847fd4614c653

1 files changed, 18 insertions, 0 deletions

diff --git a/absl/synchronization/mutex.cc b/absl/synchronization/mutex.cc
index ad9e2894..268327de 100644
--- a/absl/synchronization/mutex.cc
+++ b/absl/synchronization/mutex.cc
@@ -991,6 +991,24 @@ static PerThreadSynch* Enqueue(PerThreadSynch* head, SynchWaitParams* waitp,
       if (MuEquivalentWaiter(s, s->next)) {  // s->may_skip is known to be true
         s->skip = s->next;                   // s may skip to its successor
       }
+    } else if ((flags & kMuHasBlocked) &&
+               (s->priority >= head->next->priority) &&
+               (!head->maybe_unlocking ||
+                (waitp->how == kExclusive &&
+                 Condition::GuaranteedEqual(waitp->cond, nullptr)))) {
+      // This thread has already waited, then was woken, then failed to acquire
+      // the mutex and now tries to requeue. Try to requeue it at head,
+      // otherwise it can suffer bad latency (wait whole qeueue several times).
+      // However, we need to be conservative. First, we need to ensure that we
+      // respect priorities. Then, we need to be careful to not break wait
+      // queue invariants: we require either that unlocker is not scanning
+      // the queue or that the current thread is a writer with no condition
+      // (unlocker will recheck the queue for such waiters).
+      s->next = head->next;
+      head->next = s;
+      if (MuEquivalentWaiter(s, s->next)) {  // s->may_skip is known to be true
+        s->skip = s->next;                   // s may skip to its successor
+      }
     } else {  // enqueue not done any other way, so
               // we're inserting s at the back
       // s will become new head; copy data from head into it