Re: [PATCH RFC] drivers/core: Replace lockdep_set_novalidate_class() with unique class keys

[Peter Zijlstra <peterz@infradead.org>]

On Tue, Feb 14, 2023 at 03:05:42PM -0500, Alan Stern wrote:
> On Tue, Feb 14, 2023 at 12:05:27PM +0100, Peter Zijlstra wrote:
> > Every class gets a fixed 8 subclasses (0-7) given by the unique byte
> > addresses inside the actual key object.
> > 
> > Subclasses will let you create nesting order of the same class that are
> > acceptable. Typically lock/1 nests inside lock/0, but that's not
> > hard-coded, simply convention.
> 
> Can you explain in more detail how this works in the lockdep checking 
> algorithm?  (For simplicity, let's leave out issues of interrupt status 
> and other environmental things.)
> 
> I've been assuming that lockdep builds up a set of links between the 
> classes -- namely, a link is created from A to B whenever a thread holds 
> a lock of class A while acquiring a lock of class B.  The checking part 
> would then amount to just making sure that these links don't form any 
> cycles.
> 
> So then how do subclasses fit into the picture?  Is it just that now the 
> links are between subclasses rather than classes, so it's not 
> automatically wrong to hold a lock while acquiring another lock of the 
> same class as long as the two acquisitions are in different subclasses?  
> But you can still provoke a violation if there's a cycle among the 
> subclasses?

For all intents and purposes the subclasses are fully distinct classes
from the validation pov.

	mutex_lock(L);
	mutex_lock_nested(L, 0);

are equivalent (ignoring lockdep_set_subclass()), and

	mutex_lock_nested(L, 1);

is a distinct class, validation wise. So if you write:

	mutex_lock(L1);
	mutex_lock_nested(L2, 1);

you explicitly create a lock order between the distinct validation
classes: L/0,  L/1

> > Then there's that nesting lock, that requires two classes and at least 3
> > locks to make sense:
> > 
> >   P, C1, C2
> > 
> > Where we posit that any multi-lock of Cn is fully serialized by P
> 
> Assuming the speculations above are correct, how does the algorithm take 
> lockdep nesting into account?  Does it simply avoid creating a link from 
> subclass C to itself if both C1 and C2 were acquired while holding a 
> lock of the parent subclass and both acquisitions were annotated with 
> mutex_lock_next_lock()?

Basically this; it will explicitly ignore the nesting.

Given:

	mutex_lock(P);
	mutex_lock_nest_lock(C1, P);
	mutex_lock_nest_lock(C2, P);

mutex_lock_nest_lock() basically does:

 - validate that the instance of P is actually held.
   (as such, mutex_lock_nest_lock(C1, P1); mutex_lock_nest_lock(C2, P2);
   will cause objections).

 - either:

   * establish P->C in the held-lock stack
     and update the graph if so required

   * find the existing C in the held-lock stack
     and instead of complaining about class recursion, increment a
     refcount, and leave the held-stack and thus the graph unmodified.

subsequent mutex_unlock() will decrement the refcount and only when 0
'pop' the actual entry from the held stack.