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=-3.9 required=3.0 tests=DKIMWL_WL_HIGH,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,HEADER_FROM_DIFFERENT_DOMAINS,MAILING_LIST_MULTI, SPF_HELO_NONE,SPF_PASS,UNPARSEABLE_RELAY,USER_AGENT_GIT autolearn=no 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 1E875C33CB2 for ; Wed, 15 Jan 2020 04:15:18 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id E14B124679 for ; Wed, 15 Jan 2020 04:15:17 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=oracle.com header.i=@oracle.com header.b="WuTsIsiJ" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1729091AbgAOEPQ (ORCPT ); Tue, 14 Jan 2020 23:15:16 -0500 Received: from aserp2120.oracle.com ([141.146.126.78]:51166 "EHLO aserp2120.oracle.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1728880AbgAOEPP (ORCPT ); Tue, 14 Jan 2020 23:15:15 -0500 Received: from pps.filterd (aserp2120.oracle.com [127.0.0.1]) by aserp2120.oracle.com (8.16.0.27/8.16.0.27) with SMTP id 00F4E4cU195639; Wed, 15 Jan 2020 04:14:22 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=+RxhSJQrzetPG91u08zd91itBeag0Lx32kZWxDFBx+A=; b=WuTsIsiJwn8+TyQ4/lIlN8yLBd6bolkePj3jYyPyheVCD5giRLBhQsrWNG816QiAA48t Bxqw1PTV5hCkDGr87p/rQ7fXFpJFjc9NxweK8XaTO1m9gm3OD5i48/WNPN6h9evaYL75 Nc/t/MULAyef8xpK8LF5TBBCo4Cn5OpeRKDGdGYvisIhAOaIlop8IRoV/4iX/OWMW/ZU RKlrwSgepAaNpehliHW+P9IWNDuW1sx79ImhYnxK9YV53cQbyczCwb2fXzDJe6hOjxXj QQ+YyANBetYEg6GYd7hJBdGyTlgH41hSie0ttKcqqA+KlHbZxEtqZnHA2h3XbDTx/zYk 3Q== Received: from userp3020.oracle.com (userp3020.oracle.com [156.151.31.79]) by aserp2120.oracle.com with ESMTP id 2xf73tsvc0-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Wed, 15 Jan 2020 04:14:22 +0000 Received: from pps.filterd (userp3020.oracle.com [127.0.0.1]) by userp3020.oracle.com (8.16.0.27/8.16.0.27) with SMTP id 00F4EGhQ078029; Wed, 15 Jan 2020 04:14:21 GMT Received: from userv0121.oracle.com (userv0121.oracle.com [156.151.31.72]) by userp3020.oracle.com with ESMTP id 2xh8et8t2k-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Wed, 15 Jan 2020 04:14:21 +0000 Received: from abhmp0013.oracle.com (abhmp0013.oracle.com [141.146.116.19]) by userv0121.oracle.com (8.14.4/8.13.8) with ESMTP id 00F4D08O005657; Wed, 15 Jan 2020 04:13:00 GMT Received: from neelam.us.oracle.com (/10.152.128.16) by default (Oracle Beehive Gateway v4.0) with ESMTP ; Tue, 14 Jan 2020 20:12:59 -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 Cc: steven.sistare@oracle.com, daniel.m.jordan@oracle.com, alex.kogan@oracle.com, dave.dice@oracle.com Subject: [PATCH v9 0/5] Add NUMA-awareness to qspinlock Date: Tue, 14 Jan 2020 22:59:15 -0500 Message-Id: <20200115035920.54451-1-alex.kogan@oracle.com> X-Mailer: git-send-email 2.19.1 MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Proofpoint-Virus-Version: vendor=nai engine=6000 definitions=9500 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-2001150033 X-Proofpoint-Virus-Version: vendor=nai engine=6000 definitions=9500 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-2001150033 Sender: linux-kernel-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Minor changes from v8 based on feedback from Longman: ----------------------------------------------------- - Add __init to cna_configure_spin_lock_slowpath(). - Fix the comment for cna_scan_main_queue(). - Change the type of intra_node_handoff_threshold to unsigned int. 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-rc6, commit b3a987b026. 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 | 399 ++++++++++++++++++ kernel/locking/qspinlock_paravirt.h | 2 +- 10 files changed, 536 insertions(+), 23 deletions(-) create mode 100644 kernel/locking/qspinlock_cna.h -- 2.21.0 (Apple Git-122.2)