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.vanass...@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.
