linux-kernel - Re: [RESEND PATCH 1/3] completion: Add support for initializing completion with lockdep

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <1508915222.2947.15.camel@wdc.com>
Date:   Wed, 25 Oct 2017 07:07:06 +0000
From:   Bart Van Assche <Bart.VanAssche@....com>
To:     "byungchul.park@....com" <byungchul.park@....com>
CC:     "mingo@...nel.org" <mingo@...nel.org>,
        "linux-kernel@...r.kernel.org" <linux-kernel@...r.kernel.org>,
        "peterz@...radead.org" <peterz@...radead.org>,
        "hch@...radead.org" <hch@...radead.org>,
        "amir73il@...il.com" <amir73il@...il.com>,
        "linux-xfs@...r.kernel.org" <linux-xfs@...r.kernel.org>,
        "tglx@...utronix.de" <tglx@...utronix.de>,
        "linux-mm@...ck.org" <linux-mm@...ck.org>,
        "oleg@...hat.com" <oleg@...hat.com>,
        "linux-block@...r.kernel.org" <linux-block@...r.kernel.org>,
        "darrick.wong@...cle.com" <darrick.wong@...cle.com>,
        "johannes.berg@...el.com" <johannes.berg@...el.com>,
        "max.byungchul.park@...il.com" <max.byungchul.park@...il.com>,
        "linux-fsdevel@...r.kernel.org" <linux-fsdevel@...r.kernel.org>,
        "idryomov@...il.com" <idryomov@...il.com>,
        "tj@...nel.org" <tj@...nel.org>,
        "kernel-team@....com" <kernel-team@....com>,
        "david@...morbit.com" <david@...morbit.com>
Subject: Re: [RESEND PATCH 1/3] completion: Add support for initializing
 completion with lockdep_map

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