From mboxrd@z Thu Jan 1 00:00:00 1970 From: Peter Zijlstra Subject: Re: [PATCH v2 05/11] locking/ww_mutex: Add waiters in stamp order Date: Tue, 6 Dec 2016 16:36:06 +0100 Message-ID: <20161206153606.GW3045@worktop.programming.kicks-ass.net> References: <1480601214-26583-1-git-send-email-nhaehnle@gmail.com> <1480601214-26583-6-git-send-email-nhaehnle@gmail.com> Mime-Version: 1.0 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: base64 Return-path: Received: from merlin.infradead.org (merlin.infradead.org [IPv6:2001:4978:20e::2]) by gabe.freedesktop.org (Postfix) with ESMTPS id 9252A6E322 for ; Tue, 6 Dec 2016 15:36:13 +0000 (UTC) Content-Disposition: inline In-Reply-To: <1480601214-26583-6-git-send-email-nhaehnle@gmail.com> List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: dri-devel-bounces@lists.freedesktop.org Sender: "dri-devel" To: Nicolai =?iso-8859-1?Q?H=E4hnle?= Cc: Maarten Lankhorst , Nicolai =?iso-8859-1?Q?H=E4hnle?= , linux-kernel@vger.kernel.org, dri-devel@lists.freedesktop.org, Ingo Molnar List-Id: dri-devel@lists.freedesktop.org T24gVGh1LCBEZWMgMDEsIDIwMTYgYXQgMDM6MDY6NDhQTSArMDEwMCwgTmljb2xhaSBIw6Robmxl IHdyb3RlOgo+ICtzdGF0aWMgaW5saW5lIGludCBfX3NjaGVkCj4gK19fd3dfbXV0ZXhfYWRkX3dh aXRlcihzdHJ1Y3QgbXV0ZXhfd2FpdGVyICp3YWl0ZXIsCj4gKwkJICAgICAgc3RydWN0IG11dGV4 ICpsb2NrLAo+ICsJCSAgICAgIHN0cnVjdCB3d19hY3F1aXJlX2N0eCAqd3dfY3R4KQo+ICt7Cj4g KwlzdHJ1Y3QgbXV0ZXhfd2FpdGVyICpjdXI7Cj4gKwo+ICsJaWYgKCF3d19jdHgpIHsKPiArCQls aXN0X2FkZF90YWlsKCZ3YWl0ZXItPmxpc3QsICZsb2NrLT53YWl0X2xpc3QpOwo+ICsJCXJldHVy biAwOwo+ICsJfQo+ICsKPiArCS8qCj4gKwkgKiBBZGQgdGhlIHdhaXRlciBiZWZvcmUgdGhlIGZp cnN0IHdhaXRlciB3aXRoIGEgaGlnaGVyIHN0YW1wLgo+ICsJICogV2FpdGVycyB3aXRob3V0IGEg Y29udGV4dCBhcmUgc2tpcHBlZCB0byBhdm9pZCBzdGFydmluZwo+ICsJICogdGhlbS4KPiArCSAq Lwo+ICsJbGlzdF9mb3JfZWFjaF9lbnRyeShjdXIsICZsb2NrLT53YWl0X2xpc3QsIGxpc3QpIHsK PiArCQlpZiAoIWN1ci0+d3dfY3R4KQo+ICsJCQljb250aW51ZTsKPiArCj4gKwkJaWYgKF9fd3df bXV0ZXhfc3RhbXBfYWZ0ZXIod3dfY3R4LCBjdXItPnd3X2N0eCkpIHsKPiArCQkJLyogQmFjayBv ZmYgaW1tZWRpYXRlbHkgaWYgbmVjZXNzYXJ5LiAqLwo+ICsJCQlpZiAod3dfY3R4LT5hY3F1aXJl ZCA+IDApIHsKPiArI2lmZGVmIENPTkZJR19ERUJVR19NVVRFWEVTCj4gKwkJCQlzdHJ1Y3Qgd3df bXV0ZXggKnd3Owo+ICsKPiArCQkJCXd3ID0gY29udGFpbmVyX29mKGxvY2ssIHN0cnVjdCB3d19t dXRleCwgYmFzZSk7Cj4gKwkJCQlERUJVR19MT0NLU19XQVJOX09OKHd3X2N0eC0+Y29udGVuZGlu Z19sb2NrKTsKPiArCQkJCXd3X2N0eC0+Y29udGVuZGluZ19sb2NrID0gd3c7Cj4gKyNlbmRpZgo+ ICsJCQkJcmV0dXJuIC1FREVBRExLOwo+ICsJCQl9Cj4gKwo+ICsJCQljb250aW51ZTsKPiArCQl9 Cj4gKwo+ICsJCWxpc3RfYWRkX3RhaWwoJndhaXRlci0+bGlzdCwgJmN1ci0+bGlzdCk7Cj4gKwkJ cmV0dXJuIDA7Cj4gKwl9Cj4gKwo+ICsJbGlzdF9hZGRfdGFpbCgmd2FpdGVyLT5saXN0LCAmbG9j ay0+d2FpdF9saXN0KTsKPiArCXJldHVybiAwOwo+ICt9CgpTbyB5b3Uga2VlcCB0aGUgbGlzdCBp biBvcmRlciBvZiBzdGFtcCwgYW5kIGluIGdlbmVyYWwgc3RhbXBzIGNvbWUgaW4sCmluLW9yZGVy LiBUaGF0IGlzLCBiYXJyaW5nIHJhY2VzIG9uIGNvbmN1cnJlbnQgd3dfbXV0ZXhfbG9jaygpLCB0 aGluZ3MKYXJlIGFscmVhZHkgb3JkZXJlZC4KClNvIGl0IGRvZXNuJ3QgbWFrZSBzZW5zZSB0byBz Y2FuIHRoZSBlbnRpcmUgbGlzdCBmb3J3YXJkcywgdGhhdCdzIGFsbW9zdApndWFyYW50ZWVzIHlv dSBzY2FuIHRoZSBlbnRpcmUgbGlzdCBldmVyeSBzaW5nbGUgdGltZS4KCk9yIGFtIEkgcmVhZGlu ZyB0aGlzIHdyb25nPyBXaGljaCBpbiBpdHNlbGYgaXMgYSBoaW50IGEgY29tbWVudCBtaWdodCBi ZQppbiBwbGFjZS4KX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19f X18KZHJpLWRldmVsIG1haWxpbmcgbGlzdApkcmktZGV2ZWxAbGlzdHMuZnJlZWRlc2t0b3Aub3Jn Cmh0dHBzOi8vbGlzdHMuZnJlZWRlc2t0b3Aub3JnL21haWxtYW4vbGlzdGluZm8vZHJpLWRldmVs Cg== From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1753842AbcLFPgS (ORCPT ); Tue, 6 Dec 2016 10:36:18 -0500 Received: from merlin.infradead.org ([205.233.59.134]:36902 "EHLO merlin.infradead.org" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1752892AbcLFPgQ (ORCPT ); Tue, 6 Dec 2016 10:36:16 -0500 Date: Tue, 6 Dec 2016 16:36:06 +0100 From: Peter Zijlstra To: Nicolai =?iso-8859-1?Q?H=E4hnle?= Cc: linux-kernel@vger.kernel.org, Nicolai =?iso-8859-1?Q?H=E4hnle?= , Ingo Molnar , Maarten Lankhorst , Daniel Vetter , Chris Wilson , dri-devel@lists.freedesktop.org Subject: Re: [PATCH v2 05/11] locking/ww_mutex: Add waiters in stamp order Message-ID: <20161206153606.GW3045@worktop.programming.kicks-ass.net> References: <1480601214-26583-1-git-send-email-nhaehnle@gmail.com> <1480601214-26583-6-git-send-email-nhaehnle@gmail.com> MIME-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Disposition: inline Content-Transfer-Encoding: 8bit In-Reply-To: <1480601214-26583-6-git-send-email-nhaehnle@gmail.com> User-Agent: Mutt/1.5.22.1 (2013-10-16) Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On Thu, Dec 01, 2016 at 03:06:48PM +0100, Nicolai Hähnle wrote: > +static inline int __sched > +__ww_mutex_add_waiter(struct mutex_waiter *waiter, > + struct mutex *lock, > + struct ww_acquire_ctx *ww_ctx) > +{ > + struct mutex_waiter *cur; > + > + if (!ww_ctx) { > + list_add_tail(&waiter->list, &lock->wait_list); > + return 0; > + } > + > + /* > + * Add the waiter before the first waiter with a higher stamp. > + * Waiters without a context are skipped to avoid starving > + * them. > + */ > + list_for_each_entry(cur, &lock->wait_list, list) { > + if (!cur->ww_ctx) > + continue; > + > + if (__ww_mutex_stamp_after(ww_ctx, cur->ww_ctx)) { > + /* Back off immediately if necessary. */ > + if (ww_ctx->acquired > 0) { > +#ifdef CONFIG_DEBUG_MUTEXES > + struct ww_mutex *ww; > + > + ww = container_of(lock, struct ww_mutex, base); > + DEBUG_LOCKS_WARN_ON(ww_ctx->contending_lock); > + ww_ctx->contending_lock = ww; > +#endif > + return -EDEADLK; > + } > + > + continue; > + } > + > + list_add_tail(&waiter->list, &cur->list); > + return 0; > + } > + > + list_add_tail(&waiter->list, &lock->wait_list); > + return 0; > +} So you keep the list in order of stamp, and in general stamps come in, in-order. That is, barring races on concurrent ww_mutex_lock(), things are already ordered. So it doesn't make sense to scan the entire list forwards, that's almost guarantees you scan the entire list every single time. Or am I reading this wrong? Which in itself is a hint a comment might be in place.