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

[Byungchul Park]

On Fri, Mar 03, 2017 at 09:14:16AM +0100, Peter Zijlstra wrote:
> On Fri, Mar 03, 2017 at 09:17:37AM +0900, Byungchul Park wrote:
> > On Thu, Mar 02, 2017 at 02:40:31PM +0100, Peter Zijlstra wrote:
> 
> > > diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
> > > index a95e5d1..7baea89 100644
> > > --- a/kernel/locking/lockdep.c
> > > +++ b/kernel/locking/lockdep.c
> > > @@ -1860,6 +1860,17 @@ check_prev_add(struct task_struct *curr, struct held_lock *prev,
> > >  		}
> > >  	}
> > >  
> > > +	/*
> > > +	 * Is the <prev> -> <next> redundant?
> > > +	 */
> > > +	this.class = hlock_class(prev);
> > > +	this.parent = NULL;
> > > +	ret = check_noncircular(&this, hlock_class(next), &target_entry);
> > > +	if (!ret) /* exists, redundant */
> > > +		return 2;
> > > +	if (ret < 0)
> > > +		return print_bfs_bug(ret);
> > > +
> > >  	if (!*stack_saved) {
> > >  		if (!save_trace(&trace))
> > >  			return 0;
> > 
> > This whoud be very nice if you allow to add this code. However, prev_gen_id
> > thingy is still useful, the code above can achieve it though. Agree?
> 
> So my goal was to avoid prev_gen_id, and yes I think the above does
> that.
> 
> 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. 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?