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 From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: 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 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 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> Sender: linux-arch-owner@vger.kernel.org List-ID: To: Lihao Liang 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 Message-ID: <20200127160133.4EZEcQLrdQdf6v0yPQNNUzRuuMef1HVJzLjlfAdw16g@z> 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=