From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-17.4 required=3.0 tests=BAYES_00,DKIMWL_WL_HIGH, DKIM_SIGNED,DKIM_VALID,HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_CR_TRAILER, INCLUDES_PATCH,MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS,UNPARSEABLE_RELAY, USER_AGENT_GIT autolearn=unavailable autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 87A9BC433ED for ; Fri, 14 May 2021 20:11:39 +0000 (UTC) Received: from desiato.infradead.org (desiato.infradead.org [90.155.92.199]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by mail.kernel.org (Postfix) with ESMTPS id 1A58861076 for ; Fri, 14 May 2021 20:11:39 +0000 (UTC) DMARC-Filter: OpenDMARC Filter v1.3.2 mail.kernel.org 1A58861076 Authentication-Results: mail.kernel.org; dmarc=fail (p=none dis=none) header.from=oracle.com Authentication-Results: mail.kernel.org; spf=none smtp.mailfrom=linux-arm-kernel-bounces+linux-arm-kernel=archiver.kernel.org@lists.infradead.org DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=lists.infradead.org; s=desiato.20200630; h=Sender:Content-Transfer-Encoding :Content-Type:List-Subscribe:List-Help:List-Post:List-Archive: List-Unsubscribe:List-Id:MIME-Version:References:In-Reply-To:Message-Id:Date: Subject:Cc:To:From:Reply-To:Content-ID:Content-Description:Resent-Date: Resent-From:Resent-Sender:Resent-To:Resent-Cc:Resent-Message-ID:List-Owner; bh=6qwdyfimR7jOCxw3aT+EEkOfZdC2oXYu6YIfU84+r9M=; b=g6XWSp6AaeHg9D/EIfYArJ+5L nYrefEeXAiZmFdMbKWUxRYfmT+37Yz85zt591bRyIM+950E8fXn8SB+TwA0mVri4eCymjBVTR0vHf +sK0Fz/6GpZRduB81c4aSP/999kqLdUkALQASKNdrgeXE4mKY92B0hgrZPyVE5Jq3w+pfY0AWd4jC EN3067Sk0vfST8jBoxQ1R2WYZARX1HuP0wIX4bk+YVFe8c8hxm0Xe6/skT3xsoydvtxdEbVVDIH4Z VAawNgFtivzfKWk2lfqJVV7gFwK7gYULNt58rrZdV4ZCkCrAtNAYa2dQQTxjm+CzSyghnnMPaLfi6 OqnPKS0hw==; Received: from localhost ([::1] helo=desiato.infradead.org) by desiato.infradead.org with esmtp (Exim 4.94 #2 (Red Hat Linux)) id 1lhe7l-008uCG-EF; Fri, 14 May 2021 20:09:31 +0000 Received: from bombadil.infradead.org ([2607:7c80:54:e::133]) by desiato.infradead.org with esmtps (Exim 4.94 #2 (Red Hat Linux)) id 1lhe7O-008uAF-FF for linux-arm-kernel@desiato.infradead.org; Fri, 14 May 2021 20:09:06 +0000 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=infradead.org; s=bombadil.20210309; h=Content-Transfer-Encoding: MIME-Version:References:In-Reply-To:Message-Id:Date:Subject:Cc:To:From:Sender :Reply-To:Content-Type:Content-ID:Content-Description; bh=XHTJx+Gw+efrfyD467AyIdG7MgU2iHdmVP8/T5c98js=; b=tgCstq0kNwtD3SewzBRDgLmhcX B2/TSx7dqAmUx7KFFMHFuYeDGXZ3LJCfxVnR8HVfmTIICGD/Hcd8fDNOUHKoy/NCnHqFqlC3RZlFU 9mPboDRZdBe9Ki6WZfOT3C4F0KibYV9ZPvFfyjgMxRMzXU755GTGRSP3Hefb31pf0SsMjg6qyBUjP 75wcE+dR9dNBYvZmxsh7Pwi786EoMcC4ww/8JbKvC6WGZliXiU6V+sC0lBOC5gySqxWzLHPXjB82k 4oJGvLpixVFmMcxmmKnsoITtxtaq6E0RY9uI7vgAlrAQ3HzvPsdCtdhWk4hiDQDInMImjxuFENN1N WEIxF4YQ==; Received: from aserp2130.oracle.com ([141.146.126.79]) by bombadil.infradead.org with esmtps (Exim 4.94 #2 (Red Hat Linux)) id 1lhe7L-00CE6r-LF for linux-arm-kernel@lists.infradead.org; Fri, 14 May 2021 20:09:05 +0000 Received: from pps.filterd (aserp2130.oracle.com [127.0.0.1]) by aserp2130.oracle.com (8.16.0.42/8.16.0.42) with SMTP id 14EK40C3009406; Fri, 14 May 2021 20:08:08 GMT DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=oracle.com; h=from : to : cc : subject : date : message-id : in-reply-to : references : mime-version : content-transfer-encoding; s=corp-2020-01-29; bh=XHTJx+Gw+efrfyD467AyIdG7MgU2iHdmVP8/T5c98js=; b=y5pWO9/7W1W8BSSFDQePLGlB1oTkrk6WZHIJG/J9ea9Kem98f19guDroqt1zUzp5aKS+ nlWH9gyunbABvved5yJQckHTxeoeqtq36v0HhM0Q/rkqGpVrRO4FgbcOv8Y2oGxBBto1 UCPGRtEGHTR0SwwyXnTDarjzvkJARNqp46kR2yMtIspPMTkSGhupfhGCVOxd8QMtiIi6 EMtZEWTlbXL70+EGHA+WXD+30Pj+uXtvFPcsMha7JW7hr3CQRzb3N/faAlTjNTgNTJRd 8N6087DD/lLBREaNtW1VDaQje6ZiF+2qjqXAiQrCueJfoqI1ffRYAPbul77dnyGxqzt+ iA== Received: from aserp3030.oracle.com (aserp3030.oracle.com [141.146.126.71]) by aserp2130.oracle.com with ESMTP id 38gpnen8sj-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Fri, 14 May 2021 20:08:08 +0000 Received: from pps.filterd (aserp3030.oracle.com [127.0.0.1]) by aserp3030.oracle.com (8.16.0.42/8.16.0.42) with SMTP id 14EK60la158899; Fri, 14 May 2021 20:08:08 GMT Received: from pps.reinject (localhost [127.0.0.1]) by aserp3030.oracle.com with ESMTP id 38gppqd6qv-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Fri, 14 May 2021 20:08:08 +0000 Received: from aserp3030.oracle.com (aserp3030.oracle.com [127.0.0.1]) by pps.reinject (8.16.0.36/8.16.0.36) with SMTP id 14EK87f2161889; Fri, 14 May 2021 20:08:07 GMT Received: from userv0121.oracle.com (userv0121.oracle.com [156.151.31.72]) by aserp3030.oracle.com with ESMTP id 38gppqd6qf-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Fri, 14 May 2021 20:08:07 +0000 Received: from abhmp0014.oracle.com (abhmp0014.oracle.com [141.146.116.20]) by userv0121.oracle.com (8.14.4/8.13.8) with ESMTP id 14EK80cq011969; Fri, 14 May 2021 20:08:00 GMT Received: from neelam.us.oracle.com (/10.152.128.16) by default (Oracle Beehive Gateway v4.0) with ESMTP ; Fri, 14 May 2021 13:08:00 -0700 From: Alex Kogan To: linux@armlinux.org.uk, peterz@infradead.org, mingo@redhat.com, will.deacon@arm.com, arnd@arndb.de, longman@redhat.com, linux-arch@vger.kernel.org, linux-arm-kernel@lists.infradead.org, linux-kernel@vger.kernel.org, tglx@linutronix.de, bp@alien8.de, hpa@zytor.com, x86@kernel.org, guohanjun@huawei.com, jglauber@marvell.com Cc: steven.sistare@oracle.com, daniel.m.jordan@oracle.com, alex.kogan@oracle.com, dave.dice@oracle.com Subject: [PATCH v15 6/6] locking/qspinlock: Introduce the shuffle reduction optimization into CNA Date: Fri, 14 May 2021 16:07:43 -0400 Message-Id: <20210514200743.3026725-7-alex.kogan@oracle.com> X-Mailer: git-send-email 2.25.1 In-Reply-To: <20210514200743.3026725-1-alex.kogan@oracle.com> References: <20210514200743.3026725-1-alex.kogan@oracle.com> MIME-Version: 1.0 X-Proofpoint-GUID: fREsjUSXJkDnALJ_uXvk4qOk1SCZ_ztQ X-Proofpoint-ORIG-GUID: fREsjUSXJkDnALJ_uXvk4qOk1SCZ_ztQ X-Proofpoint-Virus-Version: vendor=nai engine=6200 definitions=9984 signatures=668683 X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 impostorscore=0 phishscore=0 suspectscore=0 bulkscore=0 lowpriorityscore=0 adultscore=0 malwarescore=0 priorityscore=1501 clxscore=1015 mlxscore=0 spamscore=0 mlxlogscore=999 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2104190000 definitions=main-2105140159 X-CRM114-Version: 20100106-BlameMichelson ( TRE 0.8.0 (BSD) ) MR-646709E3 X-CRM114-CacheID: sfid-20210514_130903_799780_09C07B0F X-CRM114-Status: GOOD ( 20.18 ) X-BeenThere: linux-arm-kernel@lists.infradead.org X-Mailman-Version: 2.1.34 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit Sender: "linux-arm-kernel" Errors-To: linux-arm-kernel-bounces+linux-arm-kernel=archiver.kernel.org@lists.infradead.org This performance optimization chooses probabilistically to avoid moving threads from the main queue into the secondary one when the secondary queue is empty. It is helpful when the lock is only lightly contended. In particular, it makes CNA less eager to create a secondary queue, but does not introduce any extra delays for threads waiting in that queue once it is created. Signed-off-by: Alex Kogan Reviewed-by: Steve Sistare Reviewed-by: Waiman Long --- kernel/locking/qspinlock_cna.h | 39 ++++++++++++++++++++++++++++++++++ 1 file changed, 39 insertions(+) diff --git a/kernel/locking/qspinlock_cna.h b/kernel/locking/qspinlock_cna.h index ffc5c3301f0f..17d56c739e57 100644 --- a/kernel/locking/qspinlock_cna.h +++ b/kernel/locking/qspinlock_cna.h @@ -7,6 +7,7 @@ #include #include #include +#include /* * Implement a NUMA-aware version of MCS (aka CNA, or compact NUMA-aware lock). @@ -76,6 +77,34 @@ static inline bool intra_node_threshold_reached(struct cna_node *cn) return current_time > threshold; } +/* + * Controls the probability for enabling the ordering of the main queue + * when the secondary queue is empty. The chosen value reduces the amount + * of unnecessary shuffling of threads between the two waiting queues + * when the contention is low, while responding fast enough and enabling + * the shuffling when the contention is high. + */ +#define SHUFFLE_REDUCTION_PROB_ARG (7) + +/* Per-CPU pseudo-random number seed */ +static DEFINE_PER_CPU(u32, seed); + +/* + * Return false with probability 1 / 2^@num_bits. + * Intuitively, the larger @num_bits the less likely false is to be returned. + * @num_bits must be a number between 0 and 31. + */ +static bool probably(unsigned int num_bits) +{ + u32 s; + + s = this_cpu_read(seed); + s = next_pseudo_random32(s); + this_cpu_write(seed, s); + + return s & ((1 << num_bits) - 1); +} + static void __init cna_init_nodes_per_cpu(unsigned int cpu) { struct mcs_spinlock *base = per_cpu_ptr(&qnodes[0].mcs, cpu); @@ -276,6 +305,16 @@ static __always_inline u32 cna_wait_head_or_lock(struct qspinlock *lock, { struct cna_node *cn = (struct cna_node *)node; + if (node->locked <= 1 && probably(SHUFFLE_REDUCTION_PROB_ARG)) { + /* + * When the secondary queue is empty, skip the calls to + * cna_order_queue() below with high probability. This optimization + * reduces the overhead of unnecessary shuffling of threads + * between waiting queues when the lock is only lightly contended. + */ + return 0; + } + if (!cn->start_time || !intra_node_threshold_reached(cn)) { /* * We are at the head of the wait queue, no need to use -- 2.24.3 (Apple Git-128) _______________________________________________ linux-arm-kernel mailing list linux-arm-kernel@lists.infradead.org http://lists.infradead.org/mailman/listinfo/linux-arm-kernel