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@xxxxxxx> 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. Furthermore, it doesn't rely on dependencies itself, but just lock ordering 'case by case', which is a subset of the more general concept. > a proof that an algorithm that is closely related to the traditional lockdep > lock inversion detector is able to detect all deadlocks and does not report I can admit this. > 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 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 Right. The paper seems to use a naive algorigm for that cases, not replying on dependencies, which they should. > 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. I think you'd better understand how cross-release works *first*. I'll do my best to help you do. > Bart. > > [1] Agarwal, Rahul, and Scott D. Stoller. "Run-time detection of potential > deadlocks for programs with locks, semaphores, and condition variables." In > Proceedings of the 2006 workshop on Parallel and distributed systems: testing > and debugging, pp. 51-60. ACM, 2006. > (https://pdfs.semanticscholar.org/9324/fc0b5d5cd5e05d551a3e98757122039946a2.pdf).
