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 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 false positives for programs that only use mutexes as synchronization objects. 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. 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).
