Re: Semphore -> mutex in the device tree

[Alan Stern]

On Thu, 17 Apr 2008, Peter Zijlstra wrote:

> > > That does mean you have to set an effective max depth to the tree, is
> > > that a practical issue?
> > 
> > I don't know.  But I suspect it wouldn't be sufficient to solve the 
> > problems associated with tree nesting.
> 
> It works for strict top-down locking. The sideways locking you do:
> 
> > For example, it's quite likely that some code somewhere needs to hold
> > two sibling nodes' locks at the same time.  Provided the parent node is
> > already locked, this operation is perfectly safe.  But is lockdep able
> > to handle it?
> 
> Your siblings are ordered; so a simple mutex_lock_nested() should work
> between siblings as long as you never need more than 8 siblings locked
> at any one time.

I don't fully understand the implications here.  Let A and B be sibling
device nodes.  Suppose task 0 locks device A with NESTING_PARENT and
then device B with NESTING_CHILD, while at about the same time task 1
locks B with NESTING PARENT and then A with NESTING_CHILD.  This is
perfectly safe provided both tasks acquire the parent lock first, but
otherwise it isn't.  How would lockdep account for this?

And don't say that one task is ignoring the ordering of the siblings.  
In fact the ordering is a rather weak one (time of registration), there
might be different orderings that are more relevant (e.g., the numbers
of the ports into which the siblings are plugged), and it isn't
particularly easy to tell which of two siblings should come first.  
Furthermore the order of locking isn't always under our control; there
_will_ be times when the order has to be "backward".

> > There are other, more subtle problems too; this is just one example.
> 
> Can you think of a situation where the top-down class annotation and the
> sideways _nesting() isn't sufficient? If so, please share.

I don't understand all the intricacies of lockdep.  In principle
ordering of siblings gives rise to a total ordering of the entire tree,
so let's assume we have such a total ordering and that everyone always
obeys it.

Even so there is a potential for trouble.  I don't know of any concrete
examples like this in the kernel, but they might exist.  Suppose a
driver keeps a private mutex associated with each device it manages.  
Normally the device's lock would be acquired first and the private
mutex second.  But there could be places where the driver acquires a
child device's lock while holding the parent's mutex; this would look
to lockdep like a violation.

Alan Stern

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/