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]
Date:   Sun, 22 Oct 2017 14:34:56 +0000
From:   Bart Van Assche <Bart.VanAssche@....com>
To:     "max.byungchul.park@...il.com" <max.byungchul.park@...il.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>,
        "byungchul.park@....com" <byungchul.park@....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 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
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).

Powered by blists - more mailing lists