public inbox for libc-alpha@sourceware.org
 help / color / mirror / Atom feed
* [PATCH v2] nptl: Add backoff mechanism to spinlock loop
@ 2022-03-28  8:47 Wangyang Guo
  2022-03-28 16:41 ` Noah Goldstein
                   ` (3 more replies)
  0 siblings, 4 replies; 28+ messages in thread
From: Wangyang Guo @ 2022-03-28  8:47 UTC (permalink / raw)
  To: libc-alpha; +Cc: Wangyang Guo, goldstein.w.n, hjl.tools

When mutiple threads waiting for lock at the same time, once lock owner
releases the lock, waiters will see lock available and all try to lock,
which may cause an expensive CAS storm.

Binary exponential backoff with random jitter is introduced. As try-lock
attempt increases, there is more likely that a larger number threads
compete for adaptive mutex lock, so increase wait time in exponential.
A random jitter is also added to avoid synchronous try-lock from other
threads.

v2: Remove read-check before try-lock for performance.

Signed-off-by: Wangyang Guo <wangyang.guo@intel.com>
---
 nptl/pthread_mutex_lock.c | 25 ++++++++++++++++---------
 1 file changed, 16 insertions(+), 9 deletions(-)

diff --git a/nptl/pthread_mutex_lock.c b/nptl/pthread_mutex_lock.c
index d2e652d151..7e75ec1cba 100644
--- a/nptl/pthread_mutex_lock.c
+++ b/nptl/pthread_mutex_lock.c
@@ -26,6 +26,7 @@
 #include <futex-internal.h>
 #include <stap-probe.h>
 #include <shlib-compat.h>
+#include <random-bits.h>
 
 /* Some of the following definitions differ when pthread_mutex_cond_lock.c
    includes this file.  */
@@ -64,11 +65,6 @@ lll_mutex_lock_optimized (pthread_mutex_t *mutex)
 # define PTHREAD_MUTEX_VERSIONS 1
 #endif
 
-#ifndef LLL_MUTEX_READ_LOCK
-# define LLL_MUTEX_READ_LOCK(mutex) \
-  atomic_load_relaxed (&(mutex)->__data.__lock)
-#endif
-
 static int __pthread_mutex_lock_full (pthread_mutex_t *mutex)
      __attribute_noinline__;
 
@@ -138,17 +134,28 @@ PTHREAD_MUTEX_LOCK (pthread_mutex_t *mutex)
 	  int cnt = 0;
 	  int max_cnt = MIN (max_adaptive_count (),
 			     mutex->__data.__spins * 2 + 10);
+	  int spin_count, exp_backoff = 1;
+	  unsigned int jitter = random_bits ();
 	  do
 	    {
-	      if (cnt++ >= max_cnt)
+	      /* In each loop, spin count is exponential backoff plus
+	         random jitter, random range is [0, exp_backoff-1].  */
+	      spin_count = exp_backoff + (jitter & (exp_backoff - 1));
+	      cnt += spin_count;
+	      if (cnt >= max_cnt)
 		{
+		  /* If cnt exceeds max spin count, just go to wait
+		     queue.  */
 		  LLL_MUTEX_LOCK (mutex);
 		  break;
 		}
-	      atomic_spin_nop ();
+	      do
+		  atomic_spin_nop ();
+	      while (--spin_count > 0);
+	      /* Binary exponential backoff, prepare for next loop.  */
+	      exp_backoff <<= 1;
 	    }
-	  while (LLL_MUTEX_READ_LOCK (mutex) != 0
-		 || LLL_MUTEX_TRYLOCK (mutex) != 0);
+	  while (LLL_MUTEX_TRYLOCK (mutex) != 0);
 
 	  mutex->__data.__spins += (cnt - mutex->__data.__spins) / 8;
 	}
-- 
2.35.1


^ permalink raw reply	[flat|nested] 28+ messages in thread

end of thread, other threads:[~2022-09-30 13:18 UTC | newest]

Thread overview: 28+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2022-03-28  8:47 [PATCH v2] nptl: Add backoff mechanism to spinlock loop Wangyang Guo
2022-03-28 16:41 ` Noah Goldstein
2022-03-30 11:44   ` Guo, Wangyang
2022-03-30 19:39     ` Noah Goldstein
2022-03-30 11:53 ` Adhemerval Zanella
2022-03-30 17:07   ` Noah Goldstein
2022-03-30 17:21     ` Adhemerval Zanella
2022-04-12 11:53       ` Florian Weimer
2022-04-22 13:30         ` Yann Droneaud
2022-04-22 13:32           ` Florian Weimer
2022-04-22 13:35             ` Cristian Rodríguez
2022-04-22 15:25               ` Noah Goldstein
2022-04-26 12:25                 ` Florian Weimer
2022-04-26 12:42                   ` Yann Droneaud
2022-05-04  2:50 ` [PATCH v3] " Wangyang Guo
2022-05-04  2:58 ` Wangyang Guo
2022-05-04  3:17   ` [PATCH v4] " Wangyang Guo
2022-05-05  1:56     ` H.J. Lu
2022-05-05  2:52       ` Noah Goldstein
2022-05-05  2:59       ` Guo, Wangyang
2022-05-05 22:44         ` H.J. Lu
2022-05-06  1:52           ` Guo, Wangyang
2022-05-06  1:50     ` [PATCH v5] " Wangyang Guo
2022-05-06  3:06       ` H.J. Lu
2022-09-11 20:29         ` Sunil Pandey
2022-09-14  1:26           ` Noah Goldstein
2022-09-29  0:12           ` Noah Goldstein
2022-09-30 13:18             ` FUCKETY FUCK FUCK, PLEASE REMOVE ME FROM THESE EMAILS Darren Tristano

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).