From mboxrd@z Thu Jan 1 00:00:00 1970 From: Peter Zijlstra Subject: Re: [PATCH v3 3/5] locking/qspinlock: Introduce CNA into the slow path of qspinlock Date: Wed, 17 Jul 2019 17:09:13 +0200 Message-ID: <20190717150913.GY3419@hirez.programming.kicks-ass.net> References: <20190715192536.104548-1-alex.kogan@oracle.com> <20190715192536.104548-4-alex.kogan@oracle.com> <20190716155022.GR3419@hirez.programming.kicks-ass.net> <193BBB31-F376-451F-BDE1-D4807140EB51@oracle.com> <20190716184724.GH3402@hirez.programming.kicks-ass.net> <20190717083944.GR3463@hirez.programming.kicks-ass.net> Mime-Version: 1.0 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: base64 Return-path: Content-Disposition: inline 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.org@lists.infradead.org To: Alex Kogan Cc: linux-arch@vger.kernel.org, guohanjun@huawei.com, arnd@arndb.de, 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, rahul.x.yadav@oracle.com, mingo@redhat.com, bp@alien8.de, hpa@zytor.com, longman@redhat.com, tglx@linutronix.de, daniel.m.jordan@oracle.com, linux-arm-kernel@lists.infradead.org List-Id: linux-arch.vger.kernel.org T24gV2VkLCBKdWwgMTcsIDIwMTkgYXQgMTA6Mjc6MzBBTSAtMDQwMCwgQWxleCBLb2dhbiB3cm90 ZToKPiA+IE9uIEp1bCAxNywgMjAxOSwgYXQgNDozOSBBTSwgUGV0ZXIgWmlqbHN0cmEgPHBldGVy ekBpbmZyYWRlYWQub3JnPiB3cm90ZToKCj4gPiBzdGF0aWMgdm9pZCBjbmFfc3BsaWNlX3RhaWwo c3RydWN0IGNuYV9ub2RlICpjbiwgc3RydWN0IGNuYV9ub2RlICpoZWFkLCBzdHJ1Y3QgY25hX25v ZGUgKnRhaWwpCj4gPiB7Cj4gPiAJc3RydWN0IGNuYV9ub2RlICpsaXN0Owo+ID4gCj4gPiAJLyog cmVtb3ZlIFtoZWFkLHRhaWxdICovCj4gPiAJV1JJVEVfT05DRShjbi0+bWNzLm5leHQsIHRhaWwt Pm1jcy5uZXh0KTsKPiA+IAl0YWlsLT5tY3MubmV4dCA9IE5VTEw7Cj4gPiAKPiA+IAkvKiBzdGlj ayBbaGVhZCx0YWlsXSBvbiB0aGUgc2Vjb25kYXJ5IGxpc3QgdGFpbCAqLwo+ID4gCWlmIChjbi0+ bWNzLmxvY2tlZCA8PSAxKSB7Cj4gPiAJCS8qIGNyZWF0ZSBzZWNvbmRhcnkgbGlzdCAqLwo+ID4g CQloZWFkLT50YWlsID0gdGFpbDsKPiA+IAkJY24tPm1jcy5sb2NrZWQgPSBoZWFkLT5lbmNvZGVk X3RhaWw7Cj4gPiAJfSBlbHNlIHsKPiA+IAkJLyogYWRkIHRvIHRhaWwgKi8KPiA+IAkJbGlzdCA9 IChzdHJ1Y3QgY25hX25vZGUgKilkZWNvZGVfdGFpbChjbi0+bWNzLmxvY2tlZCk7Cj4gPiAJCWxp c3QtPnRhaWwtPm5leHQgPSBoZWFkOwo+ID4gCQlsaXN0LT50YWlsID0gdGFpbDsKPiA+IAl9Cj4g PiB9Cj4gPiAKPiA+IHN0YXRpYyBzdHJ1Y3QgY25hX25vZGUgKmNuYV9maW5kX25leHQoc3RydWN0 IG1jc19zcGlubG9jayAqbm9kZSkKPiA+IHsKPiA+IAlzdHJ1Y3QgY25hX25vZGUgKmNuaSwgKmNu ID0gKHN0cnVjdCBjbmFfbm9kZSAqKW5vZGU7Cj4gPiAJc3RydWN0IGNuYV9ub2RlICpoZWFkLCAq dGFpbCA9IE5VTEw7Cj4gPiAKPiA+IAkvKiBmaW5kIGFueSBuZXh0IGxvY2sgZnJvbSAnb3VyJyBu b2RlICovCj4gPiAJZm9yIChoZWFkID0gY25pID0gKHN0cnVjdCBjbmFfbm9kZSAqKVJFQURfT05D RShjbi0+bWNzLm5leHQpOwo+ID4gCSAgICAgY25pICYmIGNuaS0+bm9kZSAhPSBjbi0+bm9kZTsK PiA+IAkgICAgIHRhaWwgPSBjbmksIGNuaSA9IChzdHJ1Y3QgY25hX25vZGUgKilSRUFEX09OQ0Uo Y25pLT5tY3MubmV4dCkpCj4gPiAJCTsKPiA+IAo+ID4gCS8qIHdoZW4gZm91bmQsIHNwbGljZSBh bnkgc2tpcHBlZCBsb2NrcyBvbnRvIHRoZSBzZWNvbmRhcnkgbGlzdCAqLwo+ID4gCWlmIChjbmkg JiYgdGFpbCkKPiA+IAkJY25hX3NwbGljZV90YWlsKGNuLCBoZWFkLCB0YWlsKTsKPiA+IAo+ID4g CXJldHVybiBjbmk7Cj4gPiB9Cj4gPiAKPiA+IEhvdydzIHRoYXQ/Cj4gCj4gVGhpcyBpcyBhbG1v c3QgcGVyZmVjdCEhIDopCj4gCj4gVGhlIGFib3ZlIHNob3VsZCB3b3JrLCBidXQgSSB0aGluayB3 ZSBzaG91bGQgaGF2ZSBhIHNwZWNpYWxpemVkIGZhc3QtcGF0aCBmb3IgCj4gY2hlY2tpbmcgdGhl IGltbWVkaWF0ZSBuZXh0IG5vZGUgaW4gdGhlIG1haW4gcXVldWUuIFRoaXMgd291bGQgYmUgdGhl IGNvbW1vbgo+IGNhc2UsIG9uY2Ugd2Ugc3BsaWNlIOKAmG90aGVy4oCZIG5vZGVzIG9udG8gdGhl IHNlY29uZGFyeSBxdWV1ZS4gSW4gdGhlIGFib3ZlIHdlCj4gd291bGQgZ28gdGhyb3VnaCBmb3Vy IGJyYW5jaGVzIGJlZm9yZSByZXR1cm5pbmcgZnJvbSBjbmFfZmluZF9uZXh0KCkuIEluIHRoZSAK PiBmb2xsb3dpbmcgd2Ugd291bGQgaGF2ZSBqdXN0IG9uZToKClJpZ2h0LCBidXQgY2FuIHlvdSBt ZWFzdXJlIGEgZGlmZmVyZW5jZT8gOy0pIEFueXdheSwgbm8gcmVhbCBvYmplY3Rpb24sCmp1c3Qg cGxheWluZyBkZXZpbHMgYWR2b2NhdGUgaGVyZS4KCj4gPiBzdGF0aWMgc3RydWN0IGNuYV9ub2Rl ICpjbmFfZmluZF9uZXh0KHN0cnVjdCBtY3Nfc3BpbmxvY2sgKm5vZGUpCj4gPiB7Cj4gPiAJc3Ry dWN0IGNuYV9ub2RlICpjbiA9IChzdHJ1Y3QgY25hX25vZGUgKilub2RlOwo+IAkgICBzdHJ1Y3Qg Y25hX25vZGUgKmNuaSA9IChzdHJ1Y3QgY25hX25vZGUgKilSRUFEX09OQ0UoY24tPm1jcy5uZXh0 KTsKPiA+IAo+ID4gCXN0cnVjdCBjbmFfbm9kZSAqaGVhZCwgKnRhaWwgPSBOVUxMOwo+ID4gCj4g CSAgIC8qIGZhc3QgcGF0aCAqLwo+IAkgICBpZiAoY25pLT5ub2RlID09IGNuLT5ub2RlKSAKPiAJ CXJldHVybiBjbmk7Cj4gCj4gPiAJLyogZmluZCBhbnkgbmV4dCBsb2NrIGZyb20gJ291cicgbm9k ZSAqLwo+ID4gCWZvciAoaGVhZCA9IGNuLT5tY3MubmV4dDsKCSAgICAgaGVhZCA9IGNuaSwKCnlv dSBqdXN0IGRpZCB0aGF0IGxvYWQgOi0pCgo+ID4gCSAgICAgY25pICYmIGNuaS0+bm9kZSAhPSBj bi0+bm9kZTsKPiA+IAkgICAgIHRhaWwgPSBjbmksIGNuaSA9IChzdHJ1Y3QgY25hX25vZGUgKilS RUFEX09OQ0UoY25pLT5tY3MubmV4dCkpCj4gPiAJCTsKPiA+IAo+ID4gCS8qIHdoZW4gZm91bmQs IHNwbGljZSBhbnkgc2tpcHBlZCBsb2NrcyBvbnRvIHRoZSBzZWNvbmRhcnkgbGlzdCAqLwo+ID4g CWlmIChjbmkgJiYgdGFpbCkKPiA+IAkJY25hX3NwbGljZV90YWlsKGNuLCBoZWFkLCB0YWlsKTsK PiA+IAo+ID4gCXJldHVybiBjbmk7Cj4gPiB9Cj4gCj4gCj4gQWxzbywgYW55IHJlYXNvbiB5b3Ug c2F5IOKAmGxvY2vigJkgaW5zdGVhZCBvZiDigJlub2Rl4oCZIGluIHRoZSBjb21tZW50cz8KPiBJ LmUuLCBJIHRoaW5rICJ3aGVuIGZvdW5kLCBzcGxpY2UgYW55IHNraXBwZWQgbG9ja3Mgb250byB0 aGUgc2Vjb25kYXJ5IGxpc3TigJ0gc2hvdWxkIGJlCj4gIndoZW4gZm91bmQsIHNwbGljZSBhbnkg c2tpcHBlZCBub2RlcyBvbnRvIHRoZSBzZWNvbmRhcnkgbGlzdOKAnS4KCkR1ZSB0byB0aGUgY29u ZnVzaW9uIGJldHdlZW4gbG9jayB3YWl0ZXIgbm9kZSBhbmQgbnVtYSBub2RlIDotKQoKX19fX19f X19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX18KbGludXgtYXJtLWtlcm5l bCBtYWlsaW5nIGxpc3QKbGludXgtYXJtLWtlcm5lbEBsaXN0cy5pbmZyYWRlYWQub3JnCmh0dHA6 Ly9saXN0cy5pbmZyYWRlYWQub3JnL21haWxtYW4vbGlzdGluZm8vbGludXgtYXJtLWtlcm5lbAo= From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from merlin.infradead.org ([205.233.59.134]:37630 "EHLO merlin.infradead.org" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726260AbfGQPJr (ORCPT ); Wed, 17 Jul 2019 11:09:47 -0400 Date: Wed, 17 Jul 2019 17:09:13 +0200 From: Peter Zijlstra Subject: Re: [PATCH v3 3/5] locking/qspinlock: Introduce CNA into the slow path of qspinlock Message-ID: <20190717150913.GY3419@hirez.programming.kicks-ass.net> References: <20190715192536.104548-1-alex.kogan@oracle.com> <20190715192536.104548-4-alex.kogan@oracle.com> <20190716155022.GR3419@hirez.programming.kicks-ass.net> <193BBB31-F376-451F-BDE1-D4807140EB51@oracle.com> <20190716184724.GH3402@hirez.programming.kicks-ass.net> <20190717083944.GR3463@hirez.programming.kicks-ass.net> MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Disposition: inline Content-Transfer-Encoding: 8bit In-Reply-To: Sender: linux-arch-owner@vger.kernel.org List-ID: To: Alex Kogan Cc: linux@armlinux.org.uk, 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, steven.sistare@oracle.com, daniel.m.jordan@oracle.com, dave.dice@oracle.com, rahul.x.yadav@oracle.com Message-ID: <20190717150913.DtOyeh8zBOaE1ut49dSHbOS0qsZLF0bnXnfEWVWNsxA@z> On Wed, Jul 17, 2019 at 10:27:30AM -0400, Alex Kogan wrote: > > On Jul 17, 2019, at 4:39 AM, Peter Zijlstra wrote: > > static void cna_splice_tail(struct cna_node *cn, struct cna_node *head, struct cna_node *tail) > > { > > struct cna_node *list; > > > > /* remove [head,tail] */ > > WRITE_ONCE(cn->mcs.next, tail->mcs.next); > > tail->mcs.next = NULL; > > > > /* stick [head,tail] on the secondary list tail */ > > if (cn->mcs.locked <= 1) { > > /* create secondary list */ > > head->tail = tail; > > cn->mcs.locked = head->encoded_tail; > > } else { > > /* add to tail */ > > list = (struct cna_node *)decode_tail(cn->mcs.locked); > > list->tail->next = head; > > list->tail = tail; > > } > > } > > > > static struct cna_node *cna_find_next(struct mcs_spinlock *node) > > { > > struct cna_node *cni, *cn = (struct cna_node *)node; > > struct cna_node *head, *tail = NULL; > > > > /* find any next lock from 'our' node */ > > for (head = cni = (struct cna_node *)READ_ONCE(cn->mcs.next); > > cni && cni->node != cn->node; > > tail = cni, cni = (struct cna_node *)READ_ONCE(cni->mcs.next)) > > ; > > > > /* when found, splice any skipped locks onto the secondary list */ > > if (cni && tail) > > cna_splice_tail(cn, head, tail); > > > > return cni; > > } > > > > How's that? > > This is almost perfect!! :) > > The above should work, but I think we should have a specialized fast-path for > checking the immediate next node in the main queue. This would be the common > case, once we splice ‘other’ nodes onto the secondary queue. In the above we > would go through four branches before returning from cna_find_next(). In the > following we would have just one: Right, but can you measure a difference? ;-) Anyway, no real objection, just playing devils advocate here. > > static struct cna_node *cna_find_next(struct mcs_spinlock *node) > > { > > struct cna_node *cn = (struct cna_node *)node; > struct cna_node *cni = (struct cna_node *)READ_ONCE(cn->mcs.next); > > > > struct cna_node *head, *tail = NULL; > > > /* fast path */ > if (cni->node == cn->node) > return cni; > > > /* find any next lock from 'our' node */ > > for (head = cn->mcs.next; head = cni, you just did that load :-) > > cni && cni->node != cn->node; > > tail = cni, cni = (struct cna_node *)READ_ONCE(cni->mcs.next)) > > ; > > > > /* when found, splice any skipped locks onto the secondary list */ > > if (cni && tail) > > cna_splice_tail(cn, head, tail); > > > > return cni; > > } > > > Also, any reason you say ‘lock’ instead of ’node’ in the comments? > I.e., I think "when found, splice any skipped locks onto the secondary list” should be > "when found, splice any skipped nodes onto the secondary list”. Due to the confusion between lock waiter node and numa node :-)