From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mga14.intel.com (mga14.intel.com [192.55.52.115]) by sourceware.org (Postfix) with ESMTPS id 2A3643858C74 for ; Mon, 28 Mar 2022 08:47:34 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 2A3643858C74 X-IronPort-AV: E=McAfee;i="6200,9189,10299"; a="259134588" X-IronPort-AV: E=Sophos;i="5.90,216,1643702400"; d="scan'208";a="259134588" Received: from orsmga005.jf.intel.com ([10.7.209.41]) by fmsmga103.fm.intel.com with ESMTP/TLS/ECDHE-RSA-AES256-GCM-SHA384; 28 Mar 2022 01:47:33 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.90,216,1643702400"; d="scan'208";a="719028339" Received: from clr-pnp-server-19.sh.intel.com ([10.239.146.153]) by orsmga005.jf.intel.com with ESMTP; 28 Mar 2022 01:47:31 -0700 From: Wangyang Guo To: libc-alpha@sourceware.org Cc: Wangyang Guo , goldstein.w.n@gmail.com, hjl.tools@gmail.com Subject: [PATCH v2] nptl: Add backoff mechanism to spinlock loop Date: Mon, 28 Mar 2022 08:47:05 +0000 Message-Id: <20220328084705.468207-1-wangyang.guo@intel.com> X-Mailer: git-send-email 2.35.1 MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Spam-Status: No, score=-10.4 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, SPF_HELO_NONE, SPF_NONE, TXREP, T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.4 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on server2.sourceware.org X-BeenThere: libc-alpha@sourceware.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Libc-alpha mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 28 Mar 2022 08:47:35 -0000 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 --- 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 #include #include +#include /* 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