Re: [RESEND PATCH 1/3] completion: Add support for initializing completion with lockdep_map

[Byungchul Park]

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