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=-9.8 required=3.0 tests=DKIMWL_WL_HIGH,DKIM_SIGNED, DKIM_VALID,HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_PATCH,MAILING_LIST_MULTI, SIGNED_OFF_BY,SPF_HELO_NONE,SPF_PASS,UNPARSEABLE_RELAY,USER_AGENT_GIT autolearn=ham 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 B93C4C76191 for ; Mon, 15 Jul 2019 19:27:16 +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 912C920861 for ; Mon, 15 Jul 2019 19:27:16 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=lists.infradead.org header.i=@lists.infradead.org header.b="TDI/tVgQ"; dkim=fail reason="signature verification failed" (2048-bit key) header.d=oracle.com header.i=@oracle.com header.b="iK3uUaP1" DMARC-Filter: OpenDMARC Filter v1.3.2 mail.kernel.org 912C920861 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+infradead-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=bombadil.20170209; h=Sender: Content-Transfer-Encoding:Content-Type:MIME-Version:Cc:List-Subscribe: List-Help:List-Post:List-Archive:List-Unsubscribe:List-Id:References: In-Reply-To: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:List-Owner; bh=fbLVCOK4nRFX35PRE+mUNbsSFNBDGlxXgC1CTHdpaCk=; b=TDI/tVgQod6SzMlTgxjz+GlhPK cwi19KjyEj6y8jccoDBI7MWijYfs3Bxb+Hc+GClbUd3Z7FLt7NfmoQxVyVVUPqjRP42RlJYDmotx7 igobr1r+JyuZM9zgGMTyh8KkngBOpV5wRy7nyXMWnbBGfuk0ugl6ObYkz7f/RaS9UfVIGGf65iamL 88eTEs/7a6Nl+O3u3UTJJbYOYmWDsyASpkQjCoSBSijC/EDon/d8/5ozZLiqK4YwXFV23Gph2XqqV iucwpI0y9eK7mNQ3kgc26Nbwcgd0yStZZRqP6xAQJQLIGjEQfQJy81mjTCgop+200VWpqO0PN44Uj cPjU5NUw==; Received: from localhost ([127.0.0.1] helo=bombadil.infradead.org) by bombadil.infradead.org with esmtp (Exim 4.92 #3 (Red Hat Linux)) id 1hn6d2-00057X-3M; Mon, 15 Jul 2019 19:27:16 +0000 Received: from userp2130.oracle.com ([156.151.31.86]) by bombadil.infradead.org with esmtps (Exim 4.92 #3 (Red Hat Linux)) id 1hn6cj-0004tG-8s for linux-arm-kernel@lists.infradead.org; Mon, 15 Jul 2019 19:26:58 +0000 Received: from pps.filterd (userp2130.oracle.com [127.0.0.1]) by userp2130.oracle.com (8.16.0.27/8.16.0.27) with SMTP id x6FJOAcp018340; Mon, 15 Jul 2019 19:26:02 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; s=corp-2018-07-02; bh=3eVuBt9o65dPhmPiMWn6lk9FzUIcXbbNKM5BCFCplCY=; b=iK3uUaP12YpqPpt8uouhFcoO5w01/8gINdUTpWhwVQ2rcwq9VZOxHEIs3tJ0MpZ5klNk mAhk8dwEbBmomAdnucYeGDZtxJ/m8YJIeUPv01VRXqhziWap/+pYRKomIq1THSz9eKmE ZoBnET3deAPH0Yczr++qyGAIpNECIh+GjbhORYQesj/A6EjUcm99cMqNbxtAVVukSRQD r31TyY/ipeYboGLuSwoHF+6aFskBrtirnDgogD3MbF5V3lY+tflz0eO0dxDPiHpSerQS GVqvnqs9lnEgmbx9J6MnWwf8bI9k07i1Xnzdaa5x1CVym0akLx5Ppjt9cBUQSQI3RxPA Zw== Received: from userp3030.oracle.com (userp3030.oracle.com [156.151.31.80]) by userp2130.oracle.com with ESMTP id 2tq6qtghyn-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Mon, 15 Jul 2019 19:26:01 +0000 Received: from pps.filterd (userp3030.oracle.com [127.0.0.1]) by userp3030.oracle.com (8.16.0.27/8.16.0.27) with SMTP id x6FJMkk5185803; Mon, 15 Jul 2019 19:26:01 GMT Received: from aserv0122.oracle.com (aserv0122.oracle.com [141.146.126.236]) by userp3030.oracle.com with ESMTP id 2tq4dtg9hy-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Mon, 15 Jul 2019 19:26:01 +0000 Received: from abhmp0013.oracle.com (abhmp0013.oracle.com [141.146.116.19]) by aserv0122.oracle.com (8.14.4/8.14.4) with ESMTP id x6FJPvpB031345; Mon, 15 Jul 2019 19:25:57 GMT Received: from ol-bur-x5-4.us.oracle.com (/10.152.128.37) by default (Oracle Beehive Gateway v4.0) with ESMTP ; Mon, 15 Jul 2019 12:25:56 -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 Subject: [PATCH v3 4/5] locking/qspinlock: Introduce starvation avoidance into CNA Date: Mon, 15 Jul 2019 15:25:35 -0400 Message-Id: <20190715192536.104548-5-alex.kogan@oracle.com> X-Mailer: git-send-email 2.17.1 In-Reply-To: <20190715192536.104548-1-alex.kogan@oracle.com> References: <20190715192536.104548-1-alex.kogan@oracle.com> X-Proofpoint-Virus-Version: vendor=nai engine=6000 definitions=9319 signatures=668688 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-1810050000 definitions=main-1907150221 X-Proofpoint-Virus-Version: vendor=nai engine=6000 definitions=9319 signatures=668688 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-1810050000 definitions=main-1907150222 X-CRM114-Version: 20100106-BlameMichelson ( TRE 0.8.0 (BSD) ) MR-646709E3 X-CRM114-CacheID: sfid-20190715_122657_445396_1BD06821 X-CRM114-Status: GOOD ( 19.35 ) 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, rahul.x.yadav@oracle.com, steven.sistare@oracle.com, daniel.m.jordan@oracle.com MIME-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit Sender: "linux-arm-kernel" Errors-To: linux-arm-kernel-bounces+infradead-linux-arm-kernel=archiver.kernel.org@lists.infradead.org Choose the next lock holder among spinning threads running on the same node with high probability rather than always. With small probability, hand the lock to the first thread in the secondary queue or, if that queue is empty, to the immediate successor of the current lock holder in the main queue. Thus, assuming no failures while threads hold the lock, every thread would be able to acquire the lock after a bounded number of lock transitions, with high probability. Signed-off-by: Alex Kogan Reviewed-by: Steve Sistare --- kernel/locking/qspinlock_cna.h | 36 +++++++++++++++++++++++++++++++++++- 1 file changed, 35 insertions(+), 1 deletion(-) diff --git a/kernel/locking/qspinlock_cna.h b/kernel/locking/qspinlock_cna.h index efb9b12b2f9b..3de5be813a46 100644 --- a/kernel/locking/qspinlock_cna.h +++ b/kernel/locking/qspinlock_cna.h @@ -4,6 +4,7 @@ #endif #include +#include /* * Implement a NUMA-aware version of MCS (aka CNA, or compact NUMA-aware lock). @@ -36,6 +37,33 @@ struct cna_node { #define CNA_NODE(ptr) ((struct cna_node *)(ptr)) +/* Per-CPU pseudo-random number seed */ +static DEFINE_PER_CPU(u32, seed); + +/* + * Controls the probability for intra-node lock hand-off. It can be + * tuned and depend, e.g., on the number of CPUs per node. For now, + * choose a value that provides reasonable long-term fairness without + * sacrificing performance compared to a version that does not have any + * fairness guarantees. + */ +#define INTRA_NODE_HANDOFF_PROB_ARG 0x10000 + +/* + * Return false with probability 1 / @range. + * @range must be a power of 2. + */ +static bool probably(unsigned int range) +{ + u32 s; + + s = this_cpu_read(seed); + s = next_pseudo_random32(s); + this_cpu_write(seed, s); + + return s & (range - 1); +} + static void cna_init_node(struct mcs_spinlock *node) { struct cna_node *cn = CNA_NODE(node); @@ -140,7 +168,13 @@ static inline void cna_pass_mcs_lock(struct mcs_spinlock *node, u64 *var = &next->locked; u64 val = 1; - succ = find_successor(node); + /* + * Try to pass the lock to a thread running on the same node. + * For long-term fairness, search for such a thread with high + * probability rather than always. + */ + if (probably(INTRA_NODE_HANDOFF_PROB_ARG)) + succ = find_successor(node); if (succ) { var = &succ->mcs.locked; -- 2.11.0 (Apple Git-81) _______________________________________________ linux-arm-kernel mailing list linux-arm-kernel@lists.infradead.org http://lists.infradead.org/mailman/listinfo/linux-arm-kernel