From: Bart Van Assche <Bart.VanAssche@wdc.com>
To: "byungchul.park@lge.com" <byungchul.park@lge.com>
Cc: "mingo@kernel.org" <mingo@kernel.org>,
"linux-kernel@vger.kernel.org" <linux-kernel@vger.kernel.org>,
"peterz@infradead.org" <peterz@infradead.org>,
"hch@infradead.org" <hch@infradead.org>,
"amir73il@gmail.com" <amir73il@gmail.com>,
"linux-xfs@vger.kernel.org" <linux-xfs@vger.kernel.org>,
"tglx@linutronix.de" <tglx@linutronix.de>,
"linux-mm@kvack.org" <linux-mm@kvack.org>,
"oleg@redhat.com" <oleg@redhat.com>,
"linux-block@vger.kernel.org" <linux-block@vger.kernel.org>,
"darrick.wong@oracle.com" <darrick.wong@oracle.com>,
"johannes.berg@intel.com" <johannes.berg@intel.com>,
"max.byungchul.park@gmail.com" <max.byungchul.park@gmail.com>,
"linux-fsdevel@vger.kernel.org" <linux-fsdevel@vger.kernel.org>,
"idryomov@gmail.com" <idryomov@gmail.com>,
"tj@kernel.org" <tj@kernel.org>,
"kernel-team@lge.com" <kernel-team@lge.com>,
"david@fromorbit.com" <david@fromorbit.com>
Subject: Re: [RESEND PATCH 1/3] completion: Add support for initializing completion with lockdep_map
Date: Wed, 25 Oct 2017 07:07:06 +0000 [thread overview]
Message-ID: <1508915222.2947.15.camel@wdc.com> (raw)
In-Reply-To: <20171023020822.GI3310@X58A-UD3R>
T24gTW9uLCAyMDE3LTEwLTIzIGF0IDExOjA4ICswOTAwLCBCeXVuZ2NodWwgUGFyayB3cm90ZToN
Cj4gT24gU3VuLCBPY3QgMjIsIDIwMTcgYXQgMDI6MzQ6NTZQTSArMDAwMCwgQmFydCBWYW4gQXNz
Y2hlIHdyb3RlOg0KPiA+IE9uIFNhdCwgMjAxNy0xMC0yMSBhdCAxMToyMyArMDkwMCwgQnl1bmdj
aHVsIFBhcmsgd3JvdGU6DQo+ID4gPiBPbiBTYXQsIE9jdCAyMSwgMjAxNyBhdCA0OjU4IEFNLCBC
YXJ0IFZhbiBBc3NjaGUgPEJhcnQuVmFuQXNzY2hlQHdkYy5jb20+IHdyb3RlOg0KPiA+ID4gPiBB
cyBleHBsYWluZWQgaW4gYW5vdGhlciBlLW1haWwgdGhyZWFkLCB1bmxpa2UgdGhlIGxvY2sgaW52
ZXJzaW9uIGNoZWNraW5nDQo+ID4gPiA+IHBlcmZvcm1lZCBieSB0aGUgPD0gdjQuMTMgbG9ja2Rl
cCBjb2RlLCBjcm9zcy1yZWxlYXNlIGNoZWNraW5nIGlzIGEgaGV1cmlzdGljDQo+ID4gPiA+IHRo
YXQgZG9lcyBub3QgaGF2ZSBhIHNvdW5kIHRoZW9yZXRpY2FsIGJhc2lzLiBUaGUgbG9jayB2YWxp
ZGF0b3IgaXMgYW4NCj4gPiA+IA0KPiA+ID4gSXQncyBub3QgaGV1cmlzdGljIGJ1dCBiYXNlZCBv
biB0aGUgc2FtZSB0aGVvcmV0aWNhbCBiYXNpcyBhcyA8PTQuMTMNCj4gPiA+IGxvY2tkZXAuIEkg
bWVhbiwgdGhlIGtleSBiYXNpcyBpczoNCj4gPiA+IA0KPiA+ID4gICAgMSkgV2hhdCBjYXVzZXMg
ZGVhZGxvY2sNCj4gPiA+ICAgIDIpIFdoYXQgaXMgYSBkZXBlbmRlbmN5DQo+ID4gPiAgICAzKSBC
dWlsZCBhIGRlcGVuZGVuY3kgd2hlbiBpZGVudGlmaWVkDQo+ID4gDQo+ID4gU29ycnkgYnV0IEkg
ZG91YnQgdGhhdCB0aGF0IHN0YXRlbWVudCBpcyBjb3JyZWN0LiBUaGUgcHVibGljYXRpb24gWzFd
IGNvbnRhaW5zDQo+IA0KPiBJTUhPLCB0aGUgcGFwZXIgaXMgdGFsa2luZyBhYm91dCB0b3RhbGx5
IGRpZmZlcmVudCB0aGluZ3Mgd3J0DQo+IGRlYWRsb2NrcyBieSB3YWl0X2Zvcl9ldmVudC9ldmVu
dCwgdGhhdCBpcywgbG9zdCBldmVudHMuDQoNClBsZWFzZSByZXJlYWQgdGhlIHBhcGVyIHRpdGxl
LiBUaGUgYXV0aG9ycyBvZiB0aGUgcGFwZXIgZXhwbGFpbiB0aGF0IHRoZWlyIGFsZ29yaXRobQ0K
Y2FuIGRldGVjdCBsb3N0IGV2ZW50cyBidXQgdGhlIG1vc3Qgc2lnbmlmaWNhbnQgY29udHJpYnV0
aW9uIG9mIHRoZSBwYXBlciBpcyBkZWFkbG9jaw0KZGV0ZWN0aW9uLg0KDQo+ID4gZmFsc2UgcG9z
aXRpdmVzIGZvciBwcm9ncmFtcyB0aGF0IG9ubHkgdXNlIG11dGV4ZXMgYXMgc3luY2hyb25pemF0
aW9uIG9iamVjdHMuDQo+IA0KPiBJIHdhbnQgdG8gYXNrIHlvdS4gV2hhdCBtYWtlcyBmYWxzZSBw
b3NpdGl2ZXMgYXZvaWRhYmxlIGluIHRoZSBwYXBlcj8NCg0KVGhlIGFsZ29yaXRobSB1c2VkIHRv
IGRldGVjdCBkZWFkbG9ja3MuIFRoYXQgYWxnb3JpdGhtIGhhcyBiZWVuIGV4cGxhaW5lZCBjbGVh
cmx5DQppbiB0aGUgcGFwZXIuDQoNCj4gPiBUaGUgY29tbWVudCBvZiB0aGUgYXV0aG9ycyBvZiB0
aGF0IHBhcGVyIGZvciBwcm9ncmFtcyB0aGF0IHVzZSBtdXRleGVzLA0KPiA+IGNvbmRpdGlvbiB2
YXJpYWJsZXMgYW5kIHNlbWFwaG9yZXMgaXMgYXMgZm9sbG93czogIkl0IGlzIHVuY2xlYXIgaG93
IHRvIGV4dGVuZA0KPiA+IHRoZSBsb2NrLWdyYXBoLWJhc2VkIGFsZ29yaXRobSBpbiBTZWN0aW9u
IDMgdG8gZWZmaWNpZW50bHkgY29uc2lkZXIgdGhlIGVmZmVjdHMNCj4gPiBvZiBjb25kaXRpb24g
dmFyaWFibGVzIGFuZCBzZW1hcGhvcmVzLiBUaGVyZWZvcmUsIHdoZW4gY29uc2lkZXJpbmcgYWxs
IHRocmVlDQo+ID4gc3luY2hyb25pemF0aW9uIG1lY2hhbmlzbXMsIHdlIGN1cnJlbnRseSB1c2Ug
YSBuYWl2ZSBhbGdvcml0aG0gdGhhdCBjaGVja3MgZWFjaA0KPiA+IGZlYXNpYmxlIHBlcm11dGF0
aW9uIG9mIHRoZSB0cmFjZSBmb3IgZGVhZGxvY2suIiBJbiBvdGhlciB3b3JkcywgaWYgeW91IGhh
dmUNCj4gPiBmb3VuZCBhbiBhcHByb2FjaCBmb3IgZGV0ZWN0aW5nIHBvdGVudGlhbCBkZWFkbG9j
a3MgZm9yIHByb2dyYW1zIHRoYXQgdXNlIHRoZXNlDQo+ID4gdGhyZWUga2luZHMgb2Ygc3luY2hy
b25pemF0aW9uIG9iamVjdHMgYW5kIHRoYXQgZG9lcyBub3QgcmVwb3J0IGZhbHNlIHBvc2l0aXZl
cw0KPiA+IHRoZW4gdGhhdCdzIGEgYnJlYWt0aHJvdWdoIHRoYXQncyB3b3J0aCBwdWJsaXNoaW5n
IGluIGEgam91cm5hbCBvciBpbiB0aGUNCj4gPiBwcm9jZWVkaW5ncyBvZiBhIHNjaWVudGlmaWMg
Y29uZmVyZW5jZS4NCj4gDQo+IFBsZWFzZSwgcG9pbnQgb3V0IGxvZ2ljYWwgcHJvYmxlbXMgb2Yg
Y3Jvc3MtcmVsZWFzZSB0aGFuIHNheWluZyBpdCdzDQo+IGltcG9zc2JpbGUgYWNjb3JkaW5nIHRv
IHRoZSBwYXBlci4NCg0KSXNuJ3QgdGhhdCB0aGUgc2FtZT8gSWYgaXQncyBpbXBvc3NpYmxlIHRv
IHVzZSBsb2NrLWdyYXBocyBmb3IgZGV0ZWN0aW5nIGRlYWRsb2Nrcw0KaW4gcHJvZ3JhbXMgdGhh
dCB1c2UgbXV0ZXhlcywgc2VtYXBob3JlcyBhbmQgY29uZGl0aW9uIHZhcmlhYmxlcyB3aXRob3V0
IHRyaWdnZXJpbmcNCmZhbHNlIHBvc2l0aXZlcyB0aGF0IG1lYW5zIHRoYXQgZXZlcnkgYXBwcm9h
Y2ggdGhhdCB0cmllcyB0byBkZXRlY3QgZGVhZGxvY2tzIGFuZA0KdGhhdCBpcyBiYXNlZCBvbiBs
b2NrIGdyYXBocywgaW5jbHVkaW5nIGNyb3NzLXJlbGVhc2UsIG11c3QgcmVwb3J0IGZhbHNlIHBv
c2l0aXZlcw0KZm9yIGNlcnRhaW4gcHJvZ3JhbXMuDQoNCkJhcnQuDQo=
WARNING: multiple messages have this Message-ID (diff)
From: Bart Van Assche <Bart.VanAssche@wdc.com>
To: "byungchul.park@lge.com" <byungchul.park@lge.com>
Cc: "mingo@kernel.org" <mingo@kernel.org>,
"linux-kernel@vger.kernel.org" <linux-kernel@vger.kernel.org>,
"peterz@infradead.org" <peterz@infradead.org>,
"hch@infradead.org" <hch@infradead.org>,
"amir73il@gmail.com" <amir73il@gmail.com>,
"linux-xfs@vger.kernel.org" <linux-xfs@vger.kernel.org>,
"tglx@linutronix.de" <tglx@linutronix.de>,
"linux-mm@kvack.org" <linux-mm@kvack.org>,
"oleg@redhat.com" <oleg@redhat.com>,
"linux-block@vger.kernel.org" <linux-block@vger.kernel.org>,
"darrick.wong@oracle.com" <darrick.wong@oracle.com>,
"johannes.berg@intel.com" <johannes.berg@intel.com>,
"max.byungchul.park@gmail.com" <max.byungchul.park@gmail.com>,
"linux-fsdevel@vger.kernel.org" <linux-fsdevel@vger.kernel.org>,
"idryomov@gmail.com" <idryomov@gmail.com>,
"tj@kernel.org" <tj@kernel.org>,
"kernel-team@lge.com" <kernel-team@lge.com>,
"david@fromorbit.com" <david@fromorbit.com>
Subject: Re: [RESEND PATCH 1/3] completion: Add support for initializing completion with lockdep_map
Date: Wed, 25 Oct 2017 07:07:06 +0000 [thread overview]
Message-ID: <1508915222.2947.15.camel@wdc.com> (raw)
In-Reply-To: <20171023020822.GI3310@X58A-UD3R>
On Mon, 2017-10-23 at 11:08 +0900, Byungchul Park wrote:
> On Sun, Oct 22, 2017 at 02:34:56PM +0000, Bart Van Assche wrote:
> > On Sat, 2017-10-21 at 11:23 +0900, Byungchul Park wrote:
> > > On Sat, Oct 21, 2017 at 4:58 AM, Bart Van Assche <Bart.VanAssche@wdc.com> wrote:
> > > > As explained in another e-mail thread, unlike the lock inversion checking
> > > > performed by the <= v4.13 lockdep code, cross-release checking is a heuristic
> > > > that does not have a sound theoretical basis. The lock validator is an
> > >
> > > It's not heuristic but based on the same theoretical basis as <=4.13
> > > lockdep. I mean, the key basis is:
> > >
> > > 1) What causes deadlock
> > > 2) What is a dependency
> > > 3) Build a dependency when identified
> >
> > Sorry but I doubt that that statement is correct. The publication [1] contains
>
> IMHO, the paper is talking about totally different things wrt
> deadlocks by wait_for_event/event, that is, lost events.
Please reread the paper title. The authors of the paper explain that their algorithm
can detect lost events but the most significant contribution of the paper is deadlock
detection.
> > false positives for programs that only use mutexes as synchronization objects.
>
> I want to ask you. What makes false positives avoidable in the paper?
The algorithm used to detect deadlocks. That algorithm has been explained clearly
in the paper.
> > The comment of the authors of that paper for programs that use mutexes,
> > condition variables and semaphores is as follows: "It is unclear how to extend
> > the lock-graph-based algorithm in Section 3 to efficiently consider the effects
> > of condition variables and semaphores. Therefore, when considering all three
> > synchronization mechanisms, we currently use a naive algorithm that checks each
> > feasible permutation of the trace for deadlock." In other words, if you have
> > found an approach for detecting potential deadlocks for programs that use these
> > three kinds of synchronization objects and that does not report false positives
> > then that's a breakthrough that's worth publishing in a journal or in the
> > proceedings of a scientific conference.
>
> Please, point out logical problems of cross-release than saying it's
> impossbile according to the paper.
Isn't that the same? If it's impossible to use lock-graphs for detecting deadlocks
in programs that use mutexes, semaphores and condition variables without triggering
false positives that means that every approach that tries to detect deadlocks and
that is based on lock graphs, including cross-release, must report false positives
for certain programs.
Bart.
next prev parent reply other threads:[~2017-10-25 7:07 UTC|newest]
Thread overview: 38+ messages / expand[flat|nested] mbox.gz Atom feed top
2017-10-18 9:38 Fix false positive by LOCKDEP_CROSSRELEASE Byungchul Park
2017-10-18 9:38 ` Byungchul Park
2017-10-18 9:38 ` [RESEND PATCH 1/3] completion: Add support for initializing completion with lockdep_map Byungchul Park
2017-10-18 9:38 ` Byungchul Park
2017-10-19 23:24 ` Bart Van Assche
2017-10-19 23:24 ` Bart Van Assche
2017-10-20 6:14 ` Byungchul Park
2017-10-20 6:14 ` Byungchul Park
2017-10-20 6:34 ` Thomas Gleixner
2017-10-20 6:34 ` Thomas Gleixner
2017-10-20 19:58 ` Bart Van Assche
2017-10-20 19:58 ` Bart Van Assche
2017-10-20 19:58 ` Bart Van Assche
2017-10-21 2:23 ` Byungchul Park
2017-10-21 2:23 ` Byungchul Park
2017-10-22 14:34 ` Bart Van Assche
2017-10-22 14:34 ` Bart Van Assche
2017-10-23 2:08 ` Byungchul Park
2017-10-23 2:08 ` Byungchul Park
2017-10-25 7:07 ` Bart Van Assche [this message]
2017-10-25 7:07 ` Bart Van Assche
2017-10-25 11:49 ` Byungchul Park
2017-10-25 11:49 ` Byungchul Park
2017-10-18 9:38 ` [RESEND PATCH 2/3] lockdep: Remove unnecessary acquisitions wrt workqueue flush Byungchul Park
2017-10-18 9:38 ` Byungchul Park
2017-10-18 9:38 ` [RESEND PATCH 3/3] lockdep: Assign a lock_class per gendisk used for wait_for_completion() Byungchul Park
2017-10-18 9:38 ` Byungchul Park
2017-10-18 9:59 ` Ingo Molnar
2017-10-18 9:59 ` Ingo Molnar
2017-10-19 1:57 ` Byungchul Park
2017-10-19 1:57 ` Byungchul Park
2017-10-18 14:29 ` Fix false positive by LOCKDEP_CROSSRELEASE Bart Van Assche
2017-10-18 14:29 ` Bart Van Assche
2017-10-19 1:57 ` Byungchul Park
2017-10-19 1:57 ` Byungchul Park
2017-10-19 14:52 ` Bart Van Assche
2017-10-19 14:52 ` Bart Van Assche
2017-10-19 14:52 ` Bart Van Assche
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=1508915222.2947.15.camel@wdc.com \
--to=bart.vanassche@wdc.com \
--cc=amir73il@gmail.com \
--cc=byungchul.park@lge.com \
--cc=darrick.wong@oracle.com \
--cc=david@fromorbit.com \
--cc=hch@infradead.org \
--cc=idryomov@gmail.com \
--cc=johannes.berg@intel.com \
--cc=kernel-team@lge.com \
--cc=linux-block@vger.kernel.org \
--cc=linux-fsdevel@vger.kernel.org \
--cc=linux-kernel@vger.kernel.org \
--cc=linux-mm@kvack.org \
--cc=linux-xfs@vger.kernel.org \
--cc=max.byungchul.park@gmail.com \
--cc=mingo@kernel.org \
--cc=oleg@redhat.com \
--cc=peterz@infradead.org \
--cc=tglx@linutronix.de \
--cc=tj@kernel.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.