linux-kernel - Re: [PATCH v5 06/13] lockdep: Implement crossrelease feature

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: <20170307114204.GA3312@twins.programming.kicks-ass.net>
Date:   Tue, 7 Mar 2017 12:42:04 +0100
From:   Peter Zijlstra <peterz@...radead.org>
To:     Byungchul Park <byungchul.park@....com>
Cc:     mingo@...nel.org, tglx@...utronix.de, walken@...gle.com,
        boqun.feng@...il.com, kirill@...temov.name,
        linux-kernel@...r.kernel.org, linux-mm@...ck.org,
        iamjoonsoo.kim@....com, akpm@...ux-foundation.org,
        npiggin@...il.com, kernel-team@....com,
        Michal Hocko <mhocko@...nel.org>,
        Nikolay Borisov <nborisov@...e.com>,
        Mel Gorman <mgorman@...e.de>
Subject: Re: [PATCH v5 06/13] lockdep: Implement crossrelease feature

On Sun, Mar 05, 2017 at 12:08:45PM +0900, Byungchul Park wrote:
> On Fri, Mar 03, 2017 at 09:14:16AM +0100, Peter Zijlstra wrote:

> > 
> > Now the problem with the above condition is that it makes reports
> > harder to decipher, because by avoiding adding redundant links to our
> > graph we loose a possible shorter path.
> 
> Let's see the following example:
> 
>    A -> B -> C
> 
>    where A, B and C are typical lock class.
> 
> Assume the graph above was built and operations happena in the
> following order:
> 
>    CONTEXT X		CONTEXT Y
>    ---------		---------
>    acquire DX
> 			acquire A
> 			acquire B
> 			acquire C
> 
> 			release and commit DX
> 
>    where A, B and C are typical lock class, DX is a crosslock class.
> 
> The graph will grow as following _without_ prev_gen_id.
> 
>         -> A -> B -> C
>        /    /    /
>    DX -----------
> 
>    where A, B and C are typical lock class, DX is a crosslock class.
> 
> The graph will grow as following _with_ prev_gen_id.
> 
>    DX -> A -> B -> C
> 
>    where A, B and C are typical lock class, DX is a crosslock class.
> 
> You said the former is better because it has smaller cost in bfs.

No, I said the former is better because when you report a DX inversion
against C, A and B are not required and the report is easier to
understand by _humans_.

I don't particularly care about the BFS cost itself.

> But it has to use _much_ more memory to keep additional nodes in
> graph. Without exaggeration, every crosslock would get linked with all
> locks in history locks, on commit, unless redundant. It might be
> pretty more than we expect - I will check and let you know how many it
> is. Is it still good?

Dunno, probably not.. but it would be good to have numbers.