From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S936489AbcKWNBE (ORCPT ); Wed, 23 Nov 2016 08:01:04 -0500 Received: from merlin.infradead.org ([205.233.59.134]:40072 "EHLO merlin.infradead.org" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S935439AbcKWNBD (ORCPT ); Wed, 23 Nov 2016 08:01:03 -0500 Date: Wed, 23 Nov 2016 14:00:46 +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 , Chris Wilson , Maarten Lankhorst , dri-devel@lists.freedesktop.org, stable@vger.kernel.org Subject: Re: [PATCH 1/4] locking/ww_mutex: Fix a deadlock affecting ww_mutexes Message-ID: <20161123130046.GS3092@twins.programming.kicks-ass.net> References: <1479900325-28358-1-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: <1479900325-28358-1-git-send-email-nhaehnle@gmail.com> User-Agent: Mutt/1.5.23.1 (2014-03-12) Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On Wed, Nov 23, 2016 at 12:25:22PM +0100, Nicolai Hähnle wrote: > From: Nicolai Hähnle > > Fix a race condition involving 4 threads and 2 ww_mutexes as indicated in > the following example. Acquire context stamps are ordered like the thread > numbers, i.e. thread #1 should back off when it encounters a mutex locked > by thread #0 etc. > > Thread #0 Thread #1 Thread #2 Thread #3 > --------- --------- --------- --------- > lock(ww) > success > lock(ww') > success > lock(ww) > lock(ww) . > . . unlock(ww) part 1 > lock(ww) . . . > success . . . > . . unlock(ww) part 2 > . back off > lock(ww') . > . . > (stuck) (stuck) > > Here, unlock(ww) part 1 is the part that sets lock->base.count to 1 > (without being protected by lock->base.wait_lock), meaning that thread #0 > can acquire ww in the fast path or, much more likely, the medium path > in mutex_optimistic_spin. Since lock->base.count == 0, thread #0 then > won't wake up any of the waiters in ww_mutex_set_context_fastpath. > > Then, unlock(ww) part 2 wakes up _only_the_first_ waiter of ww. This is > thread #2, since waiters are added at the tail. Thread #2 wakes up and > backs off since it sees ww owned by a context with a lower stamp. > > Meanwhile, thread #1 is never woken up, and so it won't back off its lock > on ww'. So thread #0 gets stuck waiting for ww' to be released. > > This patch fixes the deadlock by waking up all waiters in the slow path > of ww_mutex_unlock. > > We have an internal test case for amdgpu which continuously submits > command streams from tens of threads, where all command streams reference > hundreds of GPU buffer objects with a lot of overlap in the buffer lists > between command streams. This test reliably caused a deadlock, and while I > haven't completely confirmed that it is exactly the scenario outlined > above, this patch does fix the test case. > > v2: > - use wake_q_add > - add additional explanations > > Cc: Peter Zijlstra > Cc: Ingo Molnar > Cc: Chris Wilson > Cc: Maarten Lankhorst > Cc: dri-devel@lists.freedesktop.org > Cc: stable@vger.kernel.org > Reviewed-by: Christian König (v1) > Signed-off-by: Nicolai Hähnle Completely and utterly fails to apply; I think this patch is based on code prior to the mutex rewrite. Please rebase on tip/locking/core. Also, is this a regression, or has this been a 'feature' of the ww_mutex code from early on? From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from merlin.infradead.org ([205.233.59.134]:40072 "EHLO merlin.infradead.org" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S935439AbcKWNBD (ORCPT ); Wed, 23 Nov 2016 08:01:03 -0500 Date: Wed, 23 Nov 2016 14:00:46 +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 , Chris Wilson , Maarten Lankhorst , dri-devel@lists.freedesktop.org, stable@vger.kernel.org Subject: Re: [PATCH 1/4] locking/ww_mutex: Fix a deadlock affecting ww_mutexes Message-ID: <20161123130046.GS3092@twins.programming.kicks-ass.net> References: <1479900325-28358-1-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: <1479900325-28358-1-git-send-email-nhaehnle@gmail.com> Sender: stable-owner@vger.kernel.org List-ID: On Wed, Nov 23, 2016 at 12:25:22PM +0100, Nicolai H�hnle wrote: > From: Nicolai H�hnle > > Fix a race condition involving 4 threads and 2 ww_mutexes as indicated in > the following example. Acquire context stamps are ordered like the thread > numbers, i.e. thread #1 should back off when it encounters a mutex locked > by thread #0 etc. > > Thread #0 Thread #1 Thread #2 Thread #3 > --------- --------- --------- --------- > lock(ww) > success > lock(ww') > success > lock(ww) > lock(ww) . > . . unlock(ww) part 1 > lock(ww) . . . > success . . . > . . unlock(ww) part 2 > . back off > lock(ww') . > . . > (stuck) (stuck) > > Here, unlock(ww) part 1 is the part that sets lock->base.count to 1 > (without being protected by lock->base.wait_lock), meaning that thread #0 > can acquire ww in the fast path or, much more likely, the medium path > in mutex_optimistic_spin. Since lock->base.count == 0, thread #0 then > won't wake up any of the waiters in ww_mutex_set_context_fastpath. > > Then, unlock(ww) part 2 wakes up _only_the_first_ waiter of ww. This is > thread #2, since waiters are added at the tail. Thread #2 wakes up and > backs off since it sees ww owned by a context with a lower stamp. > > Meanwhile, thread #1 is never woken up, and so it won't back off its lock > on ww'. So thread #0 gets stuck waiting for ww' to be released. > > This patch fixes the deadlock by waking up all waiters in the slow path > of ww_mutex_unlock. > > We have an internal test case for amdgpu which continuously submits > command streams from tens of threads, where all command streams reference > hundreds of GPU buffer objects with a lot of overlap in the buffer lists > between command streams. This test reliably caused a deadlock, and while I > haven't completely confirmed that it is exactly the scenario outlined > above, this patch does fix the test case. > > v2: > - use wake_q_add > - add additional explanations > > Cc: Peter Zijlstra > Cc: Ingo Molnar > Cc: Chris Wilson > Cc: Maarten Lankhorst > Cc: dri-devel@lists.freedesktop.org > Cc: stable@vger.kernel.org > Reviewed-by: Christian K�nig (v1) > Signed-off-by: Nicolai H�hnle Completely and utterly fails to apply; I think this patch is based on code prior to the mutex rewrite. Please rebase on tip/locking/core. Also, is this a regression, or has this been a 'feature' of the ww_mutex code from early on? From mboxrd@z Thu Jan 1 00:00:00 1970 From: Peter Zijlstra Subject: Re: [PATCH 1/4] locking/ww_mutex: Fix a deadlock affecting ww_mutexes Date: Wed, 23 Nov 2016 14:00:46 +0100 Message-ID: <20161123130046.GS3092@twins.programming.kicks-ass.net> References: <1479900325-28358-1-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 30FAF6E891 for ; Wed, 23 Nov 2016 13:00:55 +0000 (UTC) Content-Disposition: inline In-Reply-To: <1479900325-28358-1-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: Nicolai =?iso-8859-1?Q?H=E4hnle?= , linux-kernel@vger.kernel.org, dri-devel@lists.freedesktop.org, Ingo Molnar , stable@vger.kernel.org, Maarten Lankhorst List-Id: dri-devel@lists.freedesktop.org T24gV2VkLCBOb3YgMjMsIDIwMTYgYXQgMTI6MjU6MjJQTSArMDEwMCwgTmljb2xhaSBIw6Robmxl IHdyb3RlOgo+IEZyb206IE5pY29sYWkgSMOkaG5sZSA8Tmljb2xhaS5IYWVobmxlQGFtZC5jb20+ Cj4gCj4gRml4IGEgcmFjZSBjb25kaXRpb24gaW52b2x2aW5nIDQgdGhyZWFkcyBhbmQgMiB3d19t dXRleGVzIGFzIGluZGljYXRlZCBpbgo+IHRoZSBmb2xsb3dpbmcgZXhhbXBsZS4gQWNxdWlyZSBj b250ZXh0IHN0YW1wcyBhcmUgb3JkZXJlZCBsaWtlIHRoZSB0aHJlYWQKPiBudW1iZXJzLCBpLmUu IHRocmVhZCAjMSBzaG91bGQgYmFjayBvZmYgd2hlbiBpdCBlbmNvdW50ZXJzIGEgbXV0ZXggbG9j a2VkCj4gYnkgdGhyZWFkICMwIGV0Yy4KPiAKPiBUaHJlYWQgIzAgICAgVGhyZWFkICMxICAgIFRo cmVhZCAjMiAgICBUaHJlYWQgIzMKPiAtLS0tLS0tLS0gICAgLS0tLS0tLS0tICAgIC0tLS0tLS0t LSAgICAtLS0tLS0tLS0KPiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBs b2NrKHd3KQo+ICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHN1Y2Nlc3MK PiAgICAgICAgICAgICAgbG9jayh3dycpCj4gICAgICAgICAgICAgIHN1Y2Nlc3MKPiAgICAgICAg ICAgICAgICAgICAgICAgICAgIGxvY2sod3cpCj4gICAgICAgICAgICAgIGxvY2sod3cpICAgICAg ICAuCj4gICAgICAgICAgICAgICAgIC4gICAgICAgICAgICAuICAgICAgICAgdW5sb2NrKHd3KSBw YXJ0IDEKPiBsb2NrKHd3KSAgICAgICAgLiAgICAgICAgICAgIC4gICAgICAgICAgICAuCj4gc3Vj Y2VzcyAgICAgICAgIC4gICAgICAgICAgICAuICAgICAgICAgICAgLgo+ICAgICAgICAgICAgICAg ICAuICAgICAgICAgICAgLiAgICAgICAgIHVubG9jayh3dykgcGFydCAyCj4gICAgICAgICAgICAg ICAgIC4gICAgICAgICBiYWNrIG9mZgo+IGxvY2sod3cnKSAgICAgICAuCj4gICAgLiAgICAgICAg ICAgIC4KPiAoc3R1Y2spICAgICAgKHN0dWNrKQo+IAo+IEhlcmUsIHVubG9jayh3dykgcGFydCAx IGlzIHRoZSBwYXJ0IHRoYXQgc2V0cyBsb2NrLT5iYXNlLmNvdW50IHRvIDEKPiAod2l0aG91dCBi ZWluZyBwcm90ZWN0ZWQgYnkgbG9jay0+YmFzZS53YWl0X2xvY2spLCBtZWFuaW5nIHRoYXQgdGhy ZWFkICMwCj4gY2FuIGFjcXVpcmUgd3cgaW4gdGhlIGZhc3QgcGF0aCBvciwgbXVjaCBtb3JlIGxp a2VseSwgdGhlIG1lZGl1bSBwYXRoCj4gaW4gbXV0ZXhfb3B0aW1pc3RpY19zcGluLiBTaW5jZSBs b2NrLT5iYXNlLmNvdW50ID09IDAsIHRocmVhZCAjMCB0aGVuCj4gd29uJ3Qgd2FrZSB1cCBhbnkg b2YgdGhlIHdhaXRlcnMgaW4gd3dfbXV0ZXhfc2V0X2NvbnRleHRfZmFzdHBhdGguCj4gCj4gVGhl biwgdW5sb2NrKHd3KSBwYXJ0IDIgd2FrZXMgdXAgX29ubHlfdGhlX2ZpcnN0XyB3YWl0ZXIgb2Yg d3cuIFRoaXMgaXMKPiB0aHJlYWQgIzIsIHNpbmNlIHdhaXRlcnMgYXJlIGFkZGVkIGF0IHRoZSB0 YWlsLiBUaHJlYWQgIzIgd2FrZXMgdXAgYW5kCj4gYmFja3Mgb2ZmIHNpbmNlIGl0IHNlZXMgd3cg b3duZWQgYnkgYSBjb250ZXh0IHdpdGggYSBsb3dlciBzdGFtcC4KPiAKPiBNZWFud2hpbGUsIHRo cmVhZCAjMSBpcyBuZXZlciB3b2tlbiB1cCwgYW5kIHNvIGl0IHdvbid0IGJhY2sgb2ZmIGl0cyBs b2NrCj4gb24gd3cnLiBTbyB0aHJlYWQgIzAgZ2V0cyBzdHVjayB3YWl0aW5nIGZvciB3dycgdG8g YmUgcmVsZWFzZWQuCj4gCj4gVGhpcyBwYXRjaCBmaXhlcyB0aGUgZGVhZGxvY2sgYnkgd2FraW5n IHVwIGFsbCB3YWl0ZXJzIGluIHRoZSBzbG93IHBhdGgKPiBvZiB3d19tdXRleF91bmxvY2suCj4g Cj4gV2UgaGF2ZSBhbiBpbnRlcm5hbCB0ZXN0IGNhc2UgZm9yIGFtZGdwdSB3aGljaCBjb250aW51 b3VzbHkgc3VibWl0cwo+IGNvbW1hbmQgc3RyZWFtcyBmcm9tIHRlbnMgb2YgdGhyZWFkcywgd2hl cmUgYWxsIGNvbW1hbmQgc3RyZWFtcyByZWZlcmVuY2UKPiBodW5kcmVkcyBvZiBHUFUgYnVmZmVy IG9iamVjdHMgd2l0aCBhIGxvdCBvZiBvdmVybGFwIGluIHRoZSBidWZmZXIgbGlzdHMKPiBiZXR3 ZWVuIGNvbW1hbmQgc3RyZWFtcy4gVGhpcyB0ZXN0IHJlbGlhYmx5IGNhdXNlZCBhIGRlYWRsb2Nr LCBhbmQgd2hpbGUgSQo+IGhhdmVuJ3QgY29tcGxldGVseSBjb25maXJtZWQgdGhhdCBpdCBpcyBl eGFjdGx5IHRoZSBzY2VuYXJpbyBvdXRsaW5lZAo+IGFib3ZlLCB0aGlzIHBhdGNoIGRvZXMgZml4 IHRoZSB0ZXN0IGNhc2UuCj4gCj4gdjI6Cj4gLSB1c2Ugd2FrZV9xX2FkZAo+IC0gYWRkIGFkZGl0 aW9uYWwgZXhwbGFuYXRpb25zCj4gCj4gQ2M6IFBldGVyIFppamxzdHJhIDxwZXRlcnpAaW5mcmFk ZWFkLm9yZz4KPiBDYzogSW5nbyBNb2xuYXIgPG1pbmdvQHJlZGhhdC5jb20+Cj4gQ2M6IENocmlz IFdpbHNvbiA8Y2hyaXNAY2hyaXMtd2lsc29uLmNvLnVrPgo+IENjOiBNYWFydGVuIExhbmtob3Jz dCA8bWFhcnRlbi5sYW5raG9yc3RAY2Fub25pY2FsLmNvbT4KPiBDYzogZHJpLWRldmVsQGxpc3Rz LmZyZWVkZXNrdG9wLm9yZwo+IENjOiBzdGFibGVAdmdlci5rZXJuZWwub3JnCj4gUmV2aWV3ZWQt Ynk6IENocmlzdGlhbiBLw7ZuaWcgPGNocmlzdGlhbi5rb2VuaWdAYW1kLmNvbT4gKHYxKQo+IFNp Z25lZC1vZmYtYnk6IE5pY29sYWkgSMOkaG5sZSA8bmljb2xhaS5oYWVobmxlQGFtZC5jb20+CgpD b21wbGV0ZWx5IGFuZCB1dHRlcmx5IGZhaWxzIHRvIGFwcGx5OyBJIHRoaW5rIHRoaXMgcGF0Y2gg aXMgYmFzZWQgb24KY29kZSBwcmlvciB0byB0aGUgbXV0ZXggcmV3cml0ZS4KClBsZWFzZSByZWJh c2Ugb24gdGlwL2xvY2tpbmcvY29yZS4KCkFsc28sIGlzIHRoaXMgYSByZWdyZXNzaW9uLCBvciBo YXMgdGhpcyBiZWVuIGEgJ2ZlYXR1cmUnIG9mIHRoZSB3d19tdXRleApjb2RlIGZyb20gZWFybHkg b24/Cl9fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fCmRyaS1k ZXZlbCBtYWlsaW5nIGxpc3QKZHJpLWRldmVsQGxpc3RzLmZyZWVkZXNrdG9wLm9yZwpodHRwczov L2xpc3RzLmZyZWVkZXNrdG9wLm9yZy9tYWlsbWFuL2xpc3RpbmZvL2RyaS1kZXZlbAo=