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:

quoted

On Sat, Oct 21, 2017 at 4:58 AM, Bart Van Assche [off-list ref] wrote:

quoted

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).