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=-0.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 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 6A8C7C2D0DB for ; Mon, 27 Jan 2020 16:02:48 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id 3DED524125 for ; Mon, 27 Jan 2020 16:02:48 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=oracle.com header.i=@oracle.com header.b="SsBwwRut" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1729777AbgA0QCr (ORCPT ); Mon, 27 Jan 2020 11:02:47 -0500 Received: from aserp2120.oracle.com ([141.146.126.78]:33634 "EHLO aserp2120.oracle.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1729347AbgA0QCr (ORCPT ); Mon, 27 Jan 2020 11:02:47 -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 00RFw33d009465; Mon, 27 Jan 2020 16:01:55 GMT DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=oracle.com; h=content-type : mime-version : subject : from : in-reply-to : date : cc : content-transfer-encoding : message-id : references : to; s=corp-2019-08-05; bh=fQJQyN44UUauHocBYRd01tMSTWgiqH1MXpHVaQEGRs8=; b=SsBwwRut8ax5nfhXXsjcZEjzQI+wmh46icmI68AODoRKGwFUDgf8e4AIyQZCsWVEdBig ahMJYWxG+j3KqSMGLNYA3NgFFLVeNzW0P903/7UqpHJVeqZIA8jgUNTUMxi8oTkCQBZE Dm4cDtkZxetID+K2eq2FhwMYTfAcVj3CIMaDYh/4VLx4ORLPDaX7ZMHDAcgYUyKOGtXe Wt3L66cbq7XMNoVIJ2DwsRQ1FTZi/bu/GMPDjYtFCopdLw0S/AOJTBu/6VMFvZLZLOMS ScU9BFdkSsRk+5RiaD40ItDKgYaXTU3q7PCMbYxo3s4A8GpDVBY36ltcPg35uVeXhAex 3A== Received: from userp3030.oracle.com (userp3030.oracle.com [156.151.31.80]) by aserp2120.oracle.com with ESMTP id 2xrdmq899q-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Mon, 27 Jan 2020 16:01:55 +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 00RG133i175223; Mon, 27 Jan 2020 16:01:54 GMT Received: from userv0121.oracle.com (userv0121.oracle.com [156.151.31.72]) by userp3030.oracle.com with ESMTP id 2xry4un3pm-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Mon, 27 Jan 2020 16:01:54 +0000 Received: from abhmp0008.oracle.com (abhmp0008.oracle.com [141.146.116.14]) by userv0121.oracle.com (8.14.4/8.13.8) with ESMTP id 00RG1VeP030884; Mon, 27 Jan 2020 16:01:31 GMT Received: from [10.11.111.157] (/10.11.111.157) by default (Oracle Beehive Gateway v4.0) with ESMTP ; Mon, 27 Jan 2020 08:01:30 -0800 Content-Type: text/plain; charset=utf-8 Mime-Version: 1.0 (Mac OS X Mail 12.4 \(3445.104.11\)) Subject: Re: [PATCH v9 0/5] Add NUMA-awareness to qspinlock From: Alex Kogan In-Reply-To: Date: Mon, 27 Jan 2020 11:01:33 -0500 Cc: linux@armlinux.org.uk, Peter Zijlstra , 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, dave.dice@oracle.com, steven.sistare@oracle.com, daniel.m.jordan@oracle.com, Will Deacon Content-Transfer-Encoding: quoted-printable Message-Id: <25401561-CD1F-4FDC-AED5-256EBE56B9F6@oracle.com> References: <20200115035920.54451-1-alex.kogan@oracle.com> <4F71A184-42C0-4865-9AAA-79A636743C25@oracle.com> To: Lihao Liang X-Mailer: Apple Mail (2.3445.104.11) X-Proofpoint-Virus-Version: vendor=nai engine=6000 definitions=9513 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-2001270135 X-Proofpoint-Virus-Version: vendor=nai engine=6000 definitions=9513 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-2001270135 Sender: linux-kernel-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Hi, Lihao. >>>=20 >>>> This is particularly relevant >>>> in high contention situations when new threads keep arriving on the = same >>>> socket as the lock holder. >>> In this case, the lock will stay on the same NUMA node/socket for >>> 2^numa_spinlock_threshold times, which is the worst case scenario if = we >>> consider the long-term fairness. And if we have multiple nodes, it = will take >>> up to 2^numa_spinlock_threshold X (nr_nodes - 1) + nr_cpus_per_node >>> lock transitions until any given thread will acquire the lock >>> (assuming 2^numa_spinlock_threshold > nr_cpus_per_node). >>>=20 >>=20 >> You're right that the latest version of the patch handles long-term = fairness >> deterministically. >>=20 >> As I understand it, the n-th thread in the main queue is guaranteed = to >> acquire the lock after N lock handovers, where N is bounded by >>=20 >> n - 1 + 2^numa_spinlock_threshold * (nr_nodes - 1) >>=20 >> I'm not sure what role the variable nr_cpus_per_node plays in your = analysis. >>=20 >> Do I miss anything? >>=20 >=20 > If I understand correctly, there are two phases in the algorithm: >=20 > MCS phase: when the secondary queue is empty, as explained in your = emails, > the algorithm hands the lock to threads in the main queue in an FIFO = order. > When probably(SHUFFLE_REDUCTION_PROB_ARG) returns false (with default > probability 1%), if the algorithm finds the first thread running on = the same > socket as the lock holder in cna_scan_main_queue(), it enters the = following > CNA phase Yep. When probably() returns false, we scan the main queue. If as the = result of this scan the secondary queue becomes not empty, we enter what you call the CNA phase. > . >=20 > CNA phase: when the secondary queue is not empty, the algorithm keeps > handing the lock to threads in the main queue that run on the same = socket as > the lock holder. When 2^numa_spinlock_threshold is reached, it splices > the secondary queue to the front of the main queue. And we are back to = the > MCS phase above. Correct. > For the n-th thread T in the main queue, the MCS phase handles threads = that > arrived in the main queue before T. In high contention situations, the = CNA > phase handles two kinds of threads: >=20 > 1. Threads ahead of T that run on the same socket as the lock holder = when > a transition from the MCS to CNA phase was made. Assume there are m = such > threads. >=20 > 2. Threads that keep arriving on the same socket as the lock holder. = There > are at most 2^numa_spinlock_threshold of them. >=20 > Then the number of lock handovers in the CNA phase is max(m, > 2^numa_spinlock_threshold). So the total number of lock handovers = before T > acquires the lock is at most >=20 > n - 1 + 2^numa_spinlock_threshold * (nr_nodes - 1) >=20 > Please let me know if I misunderstand anything. I think you got it right (modulo nr_cpus_per_node instead of n, as = mentioned in=20 my other response). Regards, =E2=80=94 Alex= From mboxrd@z Thu Jan 1 00:00:00 1970 From: Alex Kogan Subject: Re: [PATCH v9 0/5] Add NUMA-awareness to qspinlock Date: Mon, 27 Jan 2020 11:01:33 -0500 Message-ID: <25401561-CD1F-4FDC-AED5-256EBE56B9F6@oracle.com> References: <20200115035920.54451-1-alex.kogan@oracle.com> <4F71A184-42C0-4865-9AAA-79A636743C25@oracle.com> Mime-Version: 1.0 (Mac OS X Mail 12.4 \(3445.104.11\)) Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: base64 Return-path: In-Reply-To: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: "linux-arm-kernel" Errors-To: linux-arm-kernel-bounces+linux-arm-kernel=m.gmane-mx.org@lists.infradead.org To: Lihao Liang Cc: linux-arch@vger.kernel.org, guohanjun@huawei.com, arnd@arndb.de, Peter Zijlstra , dave.dice@oracle.com, jglauber@marvell.com, x86@kernel.org, will.deacon@arm.com, linux@armlinux.org.uk, steven.sistare@oracle.com, linux-kernel@vger.kernel.org, mingo@redhat.com, bp@alien8.de, hpa@zytor.com, longman@redhat.com, tglx@linutronix.de, daniel.m.jordan@oracle.com, Will Deacon , linux-arm-kernel@lists.infradead.org List-Id: linux-arch.vger.kernel.org SGksIExpaGFvLgoKPj4+IAo+Pj4+IFRoaXMgaXMgcGFydGljdWxhcmx5IHJlbGV2YW50Cj4+Pj4g aW4gaGlnaCBjb250ZW50aW9uIHNpdHVhdGlvbnMgd2hlbiBuZXcgdGhyZWFkcyBrZWVwIGFycml2 aW5nIG9uIHRoZSBzYW1lCj4+Pj4gc29ja2V0IGFzIHRoZSBsb2NrIGhvbGRlci4KPj4+IEluIHRo aXMgY2FzZSwgdGhlIGxvY2sgd2lsbCBzdGF5IG9uIHRoZSBzYW1lIE5VTUEgbm9kZS9zb2NrZXQg Zm9yCj4+PiAyXm51bWFfc3BpbmxvY2tfdGhyZXNob2xkIHRpbWVzLCB3aGljaCBpcyB0aGUgd29y c3QgY2FzZSBzY2VuYXJpbyBpZiB3ZQo+Pj4gY29uc2lkZXIgdGhlIGxvbmctdGVybSBmYWlybmVz cy4gQW5kIGlmIHdlIGhhdmUgbXVsdGlwbGUgbm9kZXMsIGl0IHdpbGwgdGFrZQo+Pj4gdXAgdG8g Ml5udW1hX3NwaW5sb2NrX3RocmVzaG9sZCBYIChucl9ub2RlcyAtIDEpICsgbnJfY3B1c19wZXJf bm9kZQo+Pj4gbG9jayB0cmFuc2l0aW9ucyB1bnRpbCBhbnkgZ2l2ZW4gdGhyZWFkIHdpbGwgYWNx dWlyZSB0aGUgbG9jawo+Pj4gKGFzc3VtaW5nIDJebnVtYV9zcGlubG9ja190aHJlc2hvbGQgPiBu cl9jcHVzX3Blcl9ub2RlKS4KPj4+IAo+PiAKPj4gWW91J3JlIHJpZ2h0IHRoYXQgdGhlIGxhdGVz dCB2ZXJzaW9uIG9mIHRoZSBwYXRjaCBoYW5kbGVzIGxvbmctdGVybSBmYWlybmVzcwo+PiBkZXRl cm1pbmlzdGljYWxseS4KPj4gCj4+IEFzIEkgdW5kZXJzdGFuZCBpdCwgdGhlIG4tdGggdGhyZWFk IGluIHRoZSBtYWluIHF1ZXVlIGlzIGd1YXJhbnRlZWQgdG8KPj4gYWNxdWlyZSB0aGUgbG9jayBh ZnRlciBOIGxvY2sgaGFuZG92ZXJzLCB3aGVyZSBOIGlzIGJvdW5kZWQgYnkKPj4gCj4+IG4gLSAx ICsgMl5udW1hX3NwaW5sb2NrX3RocmVzaG9sZCAqIChucl9ub2RlcyAtIDEpCj4+IAo+PiBJJ20g bm90IHN1cmUgd2hhdCByb2xlIHRoZSB2YXJpYWJsZSBucl9jcHVzX3Blcl9ub2RlIHBsYXlzIGlu IHlvdXIgYW5hbHlzaXMuCj4+IAo+PiBEbyBJIG1pc3MgYW55dGhpbmc/Cj4+IAo+IAo+IElmIEkg dW5kZXJzdGFuZCBjb3JyZWN0bHksIHRoZXJlIGFyZSB0d28gcGhhc2VzIGluIHRoZSBhbGdvcml0 aG06Cj4gCj4gTUNTIHBoYXNlOiB3aGVuIHRoZSBzZWNvbmRhcnkgcXVldWUgaXMgZW1wdHksIGFz IGV4cGxhaW5lZCBpbiB5b3VyIGVtYWlscywKPiB0aGUgYWxnb3JpdGhtIGhhbmRzIHRoZSBsb2Nr IHRvIHRocmVhZHMgaW4gdGhlIG1haW4gcXVldWUgaW4gYW4gRklGTyBvcmRlci4KPiBXaGVuIHBy b2JhYmx5KFNIVUZGTEVfUkVEVUNUSU9OX1BST0JfQVJHKSByZXR1cm5zIGZhbHNlICh3aXRoIGRl ZmF1bHQKPiBwcm9iYWJpbGl0eSAxJSksIGlmIHRoZSBhbGdvcml0aG0gZmluZHMgdGhlIGZpcnN0 IHRocmVhZCBydW5uaW5nIG9uIHRoZSBzYW1lCj4gc29ja2V0IGFzIHRoZSBsb2NrIGhvbGRlciBp biBjbmFfc2Nhbl9tYWluX3F1ZXVlKCksIGl0IGVudGVycyB0aGUgZm9sbG93aW5nCj4gQ05BIHBo YXNlClllcC4gV2hlbiBwcm9iYWJseSgpIHJldHVybnMgZmFsc2UsIHdlIHNjYW4gdGhlIG1haW4g cXVldWUuIElmIGFzIHRoZSByZXN1bHQgb2YKdGhpcyBzY2FuIHRoZSBzZWNvbmRhcnkgcXVldWUg YmVjb21lcyBub3QgZW1wdHksIHdlIGVudGVyIHdoYXQgeW91IGNhbGwKdGhlIENOQSBwaGFzZS4K Cj4gLgo+IAo+IENOQSBwaGFzZTogd2hlbiB0aGUgc2Vjb25kYXJ5IHF1ZXVlIGlzIG5vdCBlbXB0 eSwgdGhlIGFsZ29yaXRobSBrZWVwcwo+IGhhbmRpbmcgdGhlIGxvY2sgdG8gdGhyZWFkcyBpbiB0 aGUgbWFpbiBxdWV1ZSB0aGF0IHJ1biBvbiB0aGUgc2FtZSBzb2NrZXQgYXMKPiB0aGUgbG9jayBo b2xkZXIuIFdoZW4gMl5udW1hX3NwaW5sb2NrX3RocmVzaG9sZCBpcyByZWFjaGVkLCBpdCBzcGxp Y2VzCj4gdGhlIHNlY29uZGFyeSBxdWV1ZSB0byB0aGUgZnJvbnQgb2YgdGhlIG1haW4gcXVldWUu IEFuZCB3ZSBhcmUgYmFjayB0byB0aGUKPiBNQ1MgcGhhc2UgYWJvdmUuCkNvcnJlY3QuCgo+IEZv ciB0aGUgbi10aCB0aHJlYWQgVCBpbiB0aGUgbWFpbiBxdWV1ZSwgdGhlIE1DUyBwaGFzZSBoYW5k bGVzIHRocmVhZHMgdGhhdAo+IGFycml2ZWQgaW4gdGhlIG1haW4gcXVldWUgYmVmb3JlIFQuIElu IGhpZ2ggY29udGVudGlvbiBzaXR1YXRpb25zLCB0aGUgQ05BCj4gcGhhc2UgaGFuZGxlcyB0d28g a2luZHMgb2YgdGhyZWFkczoKPiAKPiAxLiBUaHJlYWRzIGFoZWFkIG9mIFQgdGhhdCBydW4gb24g dGhlIHNhbWUgc29ja2V0IGFzIHRoZSBsb2NrIGhvbGRlciB3aGVuCj4gYSB0cmFuc2l0aW9uIGZy b20gdGhlIE1DUyB0byBDTkEgcGhhc2Ugd2FzIG1hZGUuIEFzc3VtZSB0aGVyZSBhcmUgbSBzdWNo Cj4gdGhyZWFkcy4KPiAKPiAyLiBUaHJlYWRzIHRoYXQga2VlcCBhcnJpdmluZyBvbiB0aGUgc2Ft ZSBzb2NrZXQgYXMgdGhlIGxvY2sgaG9sZGVyLiBUaGVyZQo+IGFyZSBhdCBtb3N0IDJebnVtYV9z cGlubG9ja190aHJlc2hvbGQgb2YgdGhlbS4KPiAKPiBUaGVuIHRoZSBudW1iZXIgb2YgbG9jayBo YW5kb3ZlcnMgaW4gdGhlIENOQSBwaGFzZSBpcyBtYXgobSwKPiAyXm51bWFfc3BpbmxvY2tfdGhy ZXNob2xkKS4gU28gdGhlIHRvdGFsIG51bWJlciBvZiBsb2NrIGhhbmRvdmVycyBiZWZvcmUgVAo+ IGFjcXVpcmVzIHRoZSBsb2NrIGlzIGF0IG1vc3QKPiAKPiBuIC0gMSArIDJebnVtYV9zcGlubG9j a190aHJlc2hvbGQgKiAobnJfbm9kZXMgLSAxKQo+IAo+IFBsZWFzZSBsZXQgbWUga25vdyBpZiBJ IG1pc3VuZGVyc3RhbmQgYW55dGhpbmcuCkkgdGhpbmsgeW91IGdvdCBpdCByaWdodCAobW9kdWxv IG5yX2NwdXNfcGVyX25vZGUgaW5zdGVhZCBvZiBuLCBhcyBtZW50aW9uZWQgaW4gCm15IG90aGVy IHJlc3BvbnNlKS4KClJlZ2FyZHMsCuKAlCBBbGV4Cl9fX19fX19fX19fX19fX19fX19fX19fX19f X19fX19fX19fX19fX19fX19fX19fCmxpbnV4LWFybS1rZXJuZWwgbWFpbGluZyBsaXN0CmxpbnV4 LWFybS1rZXJuZWxAbGlzdHMuaW5mcmFkZWFkLm9yZwpodHRwOi8vbGlzdHMuaW5mcmFkZWFkLm9y Zy9tYWlsbWFuL2xpc3RpbmZvL2xpbnV4LWFybS1rZXJuZWwK