Re: [RFC tip/locking/lockdep v5 05/17] lockdep: Extend __bfs() to work with multiple kinds of dependencies

[Boqun Feng]

On Thu, Feb 22, 2018 at 03:26:14PM +0100, Peter Zijlstra wrote:
> On Thu, Feb 22, 2018 at 03:08:52PM +0800, Boqun Feng wrote:
> > Now we have four kinds of dependencies in the dependency graph, and not
> > all the pathes carry strong dependencies, for example:
> > 
> > 	Given lock A, B, C, if we have:
> > 
> > 	CPU1			CPU2
> > 	=============		==============
> > 	write_lock(A);		read_lock(B);
> > 	read_lock(B);		write_lock(C);
> > 
> > 	then we have dependencies A--(NR)-->B, and B--(RN)-->C, (NR and
> > 	RN are to indicate the dependency kind), A actually doesn't have
> > 	strong dependency to C(IOW, C doesn't depend on A), to see this,
>                               ^ missing space
> 
> You're fairly consistent with not putting spaces before opening braces
> in text, please don't do this, this is not a C function call. Also

Got it.

> double check all your braces are matched, IIRC there's at least one that
> isn't closed in the previous patches.
> 

Sure, will do.

> > 	let's say we have a third CPU3 doing:
> > 
> > 	CPU3:
> > 	=============
> > 	write_lock(C);
> > 	write_lock(A);
> > 
> > 	, this is not a deadlock. However if we change the read_lock()
> > 	on CPU2 to a write_lock(), it's a deadlock then.
> > 
> > 	So A --(NR)--> B --(RN)--> C is not a strong dependency path but
> > 	A --(NR)--> B --(NN)-->C is a strong dependency path.
> 
> I'm not really satisfied with the above reasoning. I don't disagree, but
> if possible it would be nice to have something a little more solid.
> 

What do you mean by "solid"? You mean "A --(NR)--> B --(NN)-->C" is too
abstract, and want something like the below instead:

	CPU 1			CPU 2			CPU 3
	===========		============		============
	write_lock(A);
				write_lock(B);
	read_lock(B); // blocked			write_lock(C);
				write_lock(C); // blocked
							write_lock(A); // blocked

?


> 
> > We can generalize this as: If a path of dependencies doesn't have two
> > adjacent dependencies as (*R)--L-->(R*), where L is some lock, it is a
> > strong dependency path, otherwise it's not.
> > 
> > Now our mission is to make __bfs() traverse only the strong dependency
> > paths, which is simple: we record whether we have -(*R)-> at the current
> > tail of the path in lock_list::is_rr, and whenever we pick a dependency
> > in the traverse, we 1) make sure we don't pick a -(R*)-> dependency if
> > our current tail is -(*R)-> and 2) greedily pick a -(*N)-> as hard as
> > possible.
> > 
> > With this extension for __bfs(), we now need to initialize the root of
> > __bfs() properly(with a correct ->is_rr), to do so, we introduce some
>                   ^ another missing space
> 
> Also, I don't like is_rr as a name, have_xr might be better.
> 

Maybe "pick_xr", which means we pick a *R in the BFS search path for the
previous entry, then we can not pick R* for the next entry.

> Only if we combine *R with R* do we have RR.
> 
> > +/*
> > + * return -1 if no proper dependency could be picked
> > + * return 0 if a -(*N)-> dependency could be picked
> > + * return 1 if only a -(*R)-> dependency could be picked
> > + *
> > + * N: non-recursive lock
> > + * R: recursive read lock
> > + */
> > +static inline int pick_dep(u16 is_rr, u16 cap_dep)
> > +{
> > +	if (is_rr) { /* could only pick -(N*)-> */
> > +		if (cap_dep & DEP_NN_MASK)
> > +			return 0;
> > +		else if (cap_dep & DEP_NR_MASK)
> > +			return 1;
> > +		else
> > +			return -1;
> > +	} else {
> > +		if (cap_dep & DEP_NN_MASK || cap_dep & DEP_RN_MASK)
> 
> 	if (cap_dep & (DEP_NN_MASK | DEP_RN_MASK))

Good point!


> 
> > +			return 0;
> > +		else
> > +			return 1;
> > +	}
> > +}
> 
> However, I would suggest:
> 
> static inline bool is_xr(u16 dep)
> {
> 	return !!(dep & (DEP_NR_MASK | DEP_RR_MASK));
> }
> 
> static inline bool is_rx(u16 dep)
> {
> 	return !!(dep & (DEP_RN_MASK | DEP_RR_MASK));
> }
> 
> 
> > @@ -1095,11 +1179,18 @@ static enum bfs_result __bfs(struct lock_list *source_entry,
> >  		else
> >  			head = &lock->class->locks_before;
> >  
> > +		is_rr = lock->is_rr;
> > +
> >  		DEBUG_LOCKS_WARN_ON(!irqs_disabled());
> >  
> >  		list_for_each_entry_rcu(entry, head, entry) {
> >  			unsigned int cq_depth;
> >  
> > +			next_is_rr = pick_dep(is_rr, entry->dep);
> > +			if (next_is_rr < 0)
> > +				continue;
> > +			entry->is_rr = next_is_rr;
> 
> 		/* Skip *R -> R* relations */
> 		if (have_xr && is_rx(entry->dep))
> 			continue;

I don't think this works, if we pick a *R for previous entry, and for
current entry, we have RR, NN and NR, your approach will skip the
current entry, but actually we can pick NN or NR (of course, in __bfs(),
we can greedily pick NN, because if NR causes a deadlock, so does NN).

Note that lock_list::dep can be treated as a set/bitmap for different
kinds of dependencies between the same pair of locks.

Some related explanation of pick_dep() is put in the comment of
__bfs(), which is my bad ;-( I will reorder the code to have an
overall explanation for the algorithm, and put all related functions
after that.

Regards,
Boqun

> 
> 		entry->have_xr = is_xr(entry->dep);
> 
> Which to me is a much simpler construct, hmm?
> 
> > +
> >  			visit_lock_entry(entry, lock);
> >  			if (match(entry, data)) {
> >  				*target_entry = entry;
> 
> 
>

Attachment: signature.asc
Description: PGP signature