From a5dc018f1016ffc92024338c300d64acfb1475f5 Mon Sep 17 00:00:00 2001 From: Dmitry Vyukov Date: Mon, 18 Sep 2023 19:14:42 -0700 Subject: 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 --- absl/synchronization/mutex.cc | 18 ++++++++++++++++++ 1 file changed, 18 insertions(+) (limited to 'absl/synchronization') 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 -- cgit v1.2.3