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

Peter Zijlstra
2017-03-07T18:44:29Z

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.