From patchwork Mon Dec 30 19:40:37 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Alex Kogan X-Patchwork-Id: 11313677 Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 97A0614E3 for ; Mon, 30 Dec 2019 19:54:03 +0000 (UTC) Received: from bombadil.infradead.org (bombadil.infradead.org [198.137.202.133]) (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 4BFC32071E for ; Mon, 30 Dec 2019 19:54:03 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=lists.infradead.org header.i=@lists.infradead.org header.b="peyavotE"; dkim=fail reason="signature verification failed" (2048-bit key) header.d=oracle.com header.i=@oracle.com header.b="laerQ0wc" DMARC-Filter: OpenDMARC Filter v1.3.2 mail.kernel.org 4BFC32071E 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+patchwork-linux-arm=patchwork.kernel.org@lists.infradead.org DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=lists.infradead.org; s=bombadil.20170209; h=Sender: Content-Transfer-Encoding:Content-Type:Cc:List-Subscribe:List-Help:List-Post: List-Archive:List-Unsubscribe:List-Id:MIME-Version:Message-Id:Date:Subject:To :From:Reply-To:Content-ID:Content-Description:Resent-Date:Resent-From: Resent-Sender:Resent-To:Resent-Cc:Resent-Message-ID:In-Reply-To:References: List-Owner; bh=AKZXfXxYUHhIzmeEhQ9E0mGcpWgGbg6P9rh6VvzsHMI=; b=peyavotEh5+oRy IAp6q6Xe92oVJLnBfzi53sHJaSxaRPgmKFMu0kLXZ33cTSFz+tDt7kfrqZt+0ZZbNTPQ174gQts+n hbSomqkvhd9QnmTiVwuq8ck9zyhC1leoiS48NGQAIBzFcu7V+MwLrgXaK/4SMbsuYut1asS+CQXmm ZkcRh06Hmkno+KvjfOzuUs+3mehq6/RWfrid4jGyP0Qts/Q/3G4P+j+5nEn/XfS+TyFg0ThsqCG1H 1r7iTPH+W4maub3QOdFWA50eL2ouTbqrcb/Pc6tmB1/sNNs1UbLyAh6WoD54Y1uLgcbt4ERR1jSFZ gXSgYWeQf+DF97KR2W4Q==; Received: from localhost ([127.0.0.1] helo=bombadil.infradead.org) by bombadil.infradead.org with esmtp (Exim 4.92.3 #3 (Red Hat Linux)) id 1im170-0005kB-E0; Mon, 30 Dec 2019 19:53:58 +0000 Received: from userp2120.oracle.com ([156.151.31.85]) by bombadil.infradead.org with esmtps (Exim 4.92.3 #3 (Red Hat Linux)) id 1im16o-0005a5-1o for linux-arm-kernel@lists.infradead.org; Mon, 30 Dec 2019 19:53:47 +0000 Received: from pps.filterd (userp2120.oracle.com [127.0.0.1]) by userp2120.oracle.com (8.16.0.27/8.16.0.27) with SMTP id xBUJnG2Q139032; Mon, 30 Dec 2019 19:52:48 GMT DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=oracle.com; h=from : to : cc : subject : date : message-id : mime-version : content-transfer-encoding; s=corp-2019-08-05; bh=6tNX/v2fnqChmL5AwO3FwDGjEomCixJM8gJZG+jJ9m8=; b=laerQ0wcN+YnS8ARdZ7JDBGX4A5LqOToQjYUsa6/nB7XAt5fpNM4SyW58sa4QHQ90arl LGew1UhB+ZVy1C3d6+GR6WTuTKWQUsK45gLmPDBsYNC/6MWsvbqgeNen3Y9YgfcbJILK kEC/NOdwga1hc8QsTgo/Yg0gdHBzuEH14LvUV3vOVdWeP7cWZ/MxZ+syT/vrf7gwLBWJ 8mborE5XKt/W6iKvRy73bmRafL9Qx7RabcAskaq9j/BvT4qtcAQCpQZiIZ7a5kizbQ8o wAONrCAY9sEv0TIU+57VK9+PpPrJzvpkLItFck+5kHPo+Gx1yTAV6h7DnktXTPlSVqFl jg== Received: from aserp3020.oracle.com (aserp3020.oracle.com [141.146.126.70]) by userp2120.oracle.com with ESMTP id 2x5ypqeuag-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Mon, 30 Dec 2019 19:52:48 +0000 Received: from pps.filterd (aserp3020.oracle.com [127.0.0.1]) by aserp3020.oracle.com (8.16.0.27/8.16.0.27) with SMTP id xBUJmOi1050740; Mon, 30 Dec 2019 19:52:47 GMT Received: from aserv0122.oracle.com (aserv0122.oracle.com [141.146.126.236]) by aserp3020.oracle.com with ESMTP id 2x6gk4pv3b-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Mon, 30 Dec 2019 19:52:47 +0000 Received: from abhmp0003.oracle.com (abhmp0003.oracle.com [141.146.116.9]) by aserv0122.oracle.com (8.14.4/8.14.4) with ESMTP id xBUJqTph021933; Mon, 30 Dec 2019 19:52:29 GMT Received: from neelam.us.oracle.com (/10.152.128.16) by default (Oracle Beehive Gateway v4.0) with ESMTP ; Mon, 30 Dec 2019 11:52:29 -0800 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 Subject: [PATCH v8 0/5] Add NUMA-awareness to qspinlock Date: Mon, 30 Dec 2019 14:40:37 -0500 Message-Id: <20191230194042.67789-1-alex.kogan@oracle.com> X-Mailer: git-send-email 2.19.1 MIME-Version: 1.0 X-Proofpoint-Virus-Version: vendor=nai engine=6000 definitions=9486 signatures=668685 X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 suspectscore=0 malwarescore=0 phishscore=0 bulkscore=0 spamscore=0 mlxscore=0 mlxlogscore=999 adultscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.0.1-1911140001 definitions=main-1912300178 X-Proofpoint-Virus-Version: vendor=nai engine=6000 definitions=9486 signatures=668685 X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 priorityscore=1501 malwarescore=0 suspectscore=0 phishscore=0 bulkscore=0 spamscore=0 clxscore=1015 lowpriorityscore=0 mlxscore=0 impostorscore=0 mlxlogscore=999 adultscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.0.1-1911140001 definitions=main-1912300178 X-CRM114-Version: 20100106-BlameMichelson ( TRE 0.8.0 (BSD) ) MR-646709E3 X-CRM114-CacheID: sfid-20191230_115346_177921_C31FE909 X-CRM114-Status: GOOD ( 20.19 ) X-Spam-Score: -2.5 (--) X-Spam-Report: SpamAssassin version 3.4.2 on bombadil.infradead.org summary: Content analysis details: (-2.5 points) pts rule name description ---- ---------------------- -------------------------------------------------- -2.3 RCVD_IN_DNSWL_MED RBL: Sender listed at https://www.dnswl.org/, medium trust [156.151.31.85 listed in list.dnswl.org] -0.0 SPF_PASS SPF: sender matches SPF record -0.0 SPF_HELO_PASS SPF: HELO matches SPF record -0.1 DKIM_VALID Message has at least one valid DKIM or DK signature -0.1 DKIM_VALID_AU Message has a valid DKIM or DK signature from author's domain 0.1 DKIM_SIGNED Message has a DKIM or DK signature, not necessarily valid -0.1 DKIM_VALID_EF Message has a valid DKIM or DK signature from envelope-from domain 0.0 UNPARSEABLE_RELAY Informational: message has unparseable relay lines -0.0 DKIMWL_WL_HIGH DKIMwl.org - Whitelisted High sender X-BeenThere: linux-arm-kernel@lists.infradead.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Cc: alex.kogan@oracle.com, dave.dice@oracle.com, steven.sistare@oracle.com, daniel.m.jordan@oracle.com Sender: "linux-arm-kernel" Errors-To: linux-arm-kernel-bounces+patchwork-linux-arm=patchwork.kernel.org@lists.infradead.org Minor changes from v7 based on feedback from Longman: ----------------------------------------------------- - Move __init functions from alternative.c to qspinlock_cna.h - Introduce enum for return values from cna_pre_scan(), for better readability. - Add/revise a few comments to improve readability. Summary ------- Lock throughput can be increased by handing a lock to a waiter on the same NUMA node as the lock holder, provided care is taken to avoid starvation of waiters on other NUMA nodes. This patch introduces CNA (compact NUMA-aware lock) as the slow path for qspinlock. It is enabled through a configuration option (NUMA_AWARE_SPINLOCKS). CNA is a NUMA-aware version of the MCS lock. Spinning threads are organized in two queues, a main queue for threads running on the same node as the current lock holder, and a secondary queue for threads running on other nodes. Threads store the ID of the node on which they are running in their queue nodes. After acquiring the MCS lock and before acquiring the spinlock, the lock holder scans the main queue looking for a thread running on the same node (pre-scan). If found (call it thread T), all threads in the main queue between the current lock holder and T are moved to the end of the secondary queue. If such T is not found, we make another scan of the main queue after acquiring the spinlock when unlocking the MCS lock (post-scan), starting at the node where pre-scan stopped. If both scans fail to find such T, the MCS lock is passed to the first thread in the secondary queue. If the secondary queue is empty, the MCS lock is passed to the next thread in the main queue. To avoid starvation of threads in the secondary queue, those threads are moved back to the head of the main queue after a certain number of intra-node lock hand-offs. More details are available at https://arxiv.org/abs/1810.05600. The series applies on top of v5.5.0-rc2, commit ea200dec51. Performance numbers are available in previous revisions of the series. Further comments are welcome and appreciated. Alex Kogan (5): locking/qspinlock: Rename mcs lock/unlock macros and make them more generic locking/qspinlock: Refactor the qspinlock slow path locking/qspinlock: Introduce CNA into the slow path of qspinlock locking/qspinlock: Introduce starvation avoidance into CNA locking/qspinlock: Introduce the shuffle reduction optimization into CNA .../admin-guide/kernel-parameters.txt | 18 + arch/arm/include/asm/mcs_spinlock.h | 6 +- arch/x86/Kconfig | 20 + arch/x86/include/asm/qspinlock.h | 4 + arch/x86/kernel/alternative.c | 4 + include/asm-generic/mcs_spinlock.h | 4 +- kernel/locking/mcs_spinlock.h | 20 +- kernel/locking/qspinlock.c | 82 +++- kernel/locking/qspinlock_cna.h | 400 ++++++++++++++++++ kernel/locking/qspinlock_paravirt.h | 2 +- 10 files changed, 537 insertions(+), 23 deletions(-) create mode 100644 kernel/locking/qspinlock_cna.h Reviewed-by: Waiman Long