From patchwork Mon Mar 28 08:47:05 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Wangyang Guo X-Patchwork-Id: 1610071 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: bilbo.ozlabs.org; dkim=pass (1024-bit key; secure) header.d=sourceware.org header.i=@sourceware.org header.a=rsa-sha256 header.s=default header.b=ZQrXNtJk; dkim-atps=neutral Authentication-Results: ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=sourceware.org (client-ip=2620:52:3:1:0:246e:9693:128c; helo=sourceware.org; envelope-from=libc-alpha-bounces+incoming=patchwork.ozlabs.org@sourceware.org; receiver=) Received: from sourceware.org (server2.sourceware.org [IPv6:2620:52:3:1:0:246e:9693:128c]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by bilbo.ozlabs.org (Postfix) with ESMTPS id 4KRmYM49bxz9sFy for ; Mon, 28 Mar 2022 19:47:51 +1100 (AEDT) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 03542385782D for ; Mon, 28 Mar 2022 08:47:49 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 03542385782D DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sourceware.org; s=default; t=1648457269; bh=JnR1/7YnUkKtLOHVbT1DtRkE9qXcERIGcKcEdTsfAyE=; h=To:Subject:Date:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:Cc:From; b=ZQrXNtJkGzzSbqYn03E+AGP4wD5oU0VwJZxx8DTpa8WHbSUM62C8sjXjpKeZzX6ep SHOJVLahQZqAN9EfrXAAiq0sCzbHzPq8XfUOK2nfV4dq+VYoAQrjfuPkNpYUIbOBGX f64MBxD5/0ob3nSetX1rVBbQY70yDfj/fKjOQImw= X-Original-To: libc-alpha@sourceware.org Delivered-To: libc-alpha@sourceware.org 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 To: libc-alpha@sourceware.org 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 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-Patchwork-Original-From: Wangyang Guo via Libc-alpha From: Wangyang Guo Reply-To: Wangyang Guo Cc: Wangyang Guo Errors-To: libc-alpha-bounces+incoming=patchwork.ozlabs.org@sourceware.org Sender: "Libc-alpha" 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; }