On Tue, 2007-11-06 at 11:32 -0500, Alan Stern wrote:
> On Tue, 6 Nov 2007, Peter Zijlstra wrote:
> > On Tue, 2007-11-06 at 10:36 -0500, Alan Stern wrote:
> > > You can't possibly solve the lockdep problems here with a simple-minded
> > > approach like your DRIVER_NORMAL, DRIVER_PARENT, etc. The device tree
> > > is arbitrarily deep & wide, and there is at least one routine that
> > > acquires the semaphores for _all_ the devices in the tree.
> >
> > *blink* someone needs to take all locks - why?
>
> It's for system suspend. All the devices are locked to prevent driver
> binding and unbinding during the suspend transition.
Just locking the tree root is not enough? (thereby avoiding all any new
modifying operation to descend into the tree).
> Even apart from that, there are places where the USB core needs to
> acquire multiple layers of locks (more than just two). For example, if
> somebody has hubs nested several deep and then unplugs the hub closest
> to the computer, this will happen.
Pin the sub-tree root with a reference, iterate the sub-tree and delete
the leafs one by one?
> Shucks, any time a driver's probe routine tries to register a child
> device you will run into problems. probe() is always called with the
> device locked, and registration of a child will acquire the child's
> lock in order to probe drivers for the child.
Right, so you say you have unbounded stack recursion? How about pushing
each probe into a stack (workqueue perhaps). Then each stack entry would
only do a single level probe, if it would recurse push a new entry on
the stack. Basic recursive -> stack transform.
> > > This fact
> > > alone seems to preclude using lockdep for device locks. (If there was
> > > a form of mutex_lock() that bypassed the lockdep checks, you could use
> > > it and avoid these issues.)
> >
> > I'm sceptical of this, since its a simple tree (as opposed to a balanced
> > tree) a simple lock-coupling approach should be enough to guarantee
> > consistency.
>
> I don't follow your reasoning. Let's say a task wants to lock all the
> direct children of a particular device. In what order should the locks
> be acquired?
I'd first start by asking if you want to lock all the children or the
sub-tree. The latter can be done by locking the root of said sub-tree.
> There's no natural tree-related ordering to follow.
Of course there is a natural deadlock free locking order in a tree: lock
the parent, lock all its children, repeat by noting that each child is a
parent again. If you only ever lock top down, there should not be any
lateral dependencies.
> In the simple case where locks are acquired along a path in the tree,
> you could solve the lockdep issues by passing mutex_lock_nested() a key
> equal to the device's depth in the tree. But that won't work with more
> complicated cases.
And only up to 8, as that's the max nesting depth.
> > > Deadlock is a serious consideration. For the most part, routines
> > > locking devices do so along a single path in the tree. For this simple
> > > case the rule is: Never acquire a parent's lock while holding the
> > > child's lock.
> >
> > Sure, but once you have a parent's lock, you could unlock your
> > grandparent, no? (it having a locked child, your parent, should be
> > enough to guarantee its continued existence)
>
> Of course. So what? In many cases the code needs to keep all three
> locks. The locks don't merely guarantee the device structs' continued
> existence (a kref could do that) -- they serialize a number of related
> operations.
Right, but does the grandparent really need serialisation? Normal simple
tree manipulations don't require more than 2 locks to guarantee tree
consistency. So you either don't have a simple tree, or you have more
requirements.
> > > The routine that locks all the devices acquires the locks in order of
> > > device registration. The idea here is that children are always
> > > registered _after_ their parents, so this should be compatible with the
> > > previous rule. But there is a potential problem: device_move() can
> > > move an older child under a younger parent!
> >
> > Seems like a weird rule, a typical tree locking rule would be to lock
> > them top-down - such a rule can easily cope with moves: lock old parent,
> > lock child, lock new parent, move child, unlock all in reverse order.
>
> Yep. But this isn't a typical tree-locking. System suspend sometimes
> requires that devices be powered down in a specific order, and there
> are constraints not captured by the positions in the tree. We get
> around this by powering devices down in reverse order of detection,
> which should always be safe. Although the locking need not necessarily
> follow these same constraints, it is certainly the easiest approach.
Ah, there are more constraints than tree order (which as I get it
resembles bus order)? Which confuses me, as you cannot detect a leaf
before you have a parent, so top-down should still be good, no?
> (And by the way, your example rule "lock old parent, lock child, lock
> new parent" is subject to deadlocks. What if another task tries to
> move a different device from under the new parent to the old parent at
> the same time?)
D'0h, right you are. How about a delete, insert sequence?
> > Like said, I think the tree locking model should be revisited. A
> > top-down locking model with lock-coupling should, from my ignorant
> > perspective, solve your problems.
>
> I don't understand what you mean by "lock-coupling".
A
B C
D E F G
In order to lock F we do:
lock A, lock C, unlock A, lock F, unlock C
Look at it this way, either you're more complex than the VFS or it can
be annotated :-)
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
[Index of Archives]
[Kernel Newbies]
[Netfilter]
[Bugtraq]
[Photo]
[Stuff]
[Gimp]
[Yosemite News]
[MIPS Linux]
[ARM Linux]
[Linux Security]
[Linux RAID]
[Video 4 Linux]
[Linux for the blind]
[Linux Resources]
