| |||||||||||||
Generic semaphoresGeneric semaphoresPosted Mar 23, 2008 13:37 UTC (Sun) by willy (subscriber, #9762)In reply to: Generic semaphores by Alan.Stern Parent article: Generic semaphores
> It's not possible for two tasks to deadlock when acquiring locks in a > tree structure provided that the locks are always acquired going down > a branch. (Or if the locks are always acquired going up a branch.) That's not what you said before! It sounded like you were describing a situation where task A acquires locks walking down the tree and simultaneously task B acquires locks walking up the tree. That can't work. lockdep does manage to handle situations like the VFS where we have i_mutex protecting each inode and some rather byzantine rules regarding which have to be locked first (it's particularly hairy when doing cross-directory renames -- you have to lock the renamed object, its parent and the destination directory. While not deadlocking against any other operation happening at the same time). So your assertion is demonstratedly untrue, but you still can't give semaphores an owner.
(Log in to post comments)
Generic semaphores Posted Mar 23, 2008 14:15 UTC (Sun) by Alan.Stern (subscriber, #12437) [Link] > That's not what you said before! It sounded like you were describing a > situation where task A acquires locks walking down the tree and > simultaneously task B acquires locks walking up the > tree. That can't work. Okay, what I wrote before wasn't sufficiently unambiguous and you misinterpreted it. > So your assertion is demonstratedly untrue, but you still can't give > semaphores an owner. Lockdep works in the special-case example of VFS. It still can't be made to handle general tree-usage patterns. It's true that many semaphores can't be given an owner. However there are some which can, but which nevertheless can't be converted to a mutex.
Generic semaphores Posted Mar 23, 2008 16:45 UTC (Sun) by willy (subscriber, #9762) [Link] > Lockdep works in the special-case example of VFS. It still can't be > made to handle general tree-usage patterns. I don't think that's true. Take a look at Documentation/lockdep-design.txt. The mutex_lock_nested() interface needs to be specialised for each tree, but that doesn't look hard -- the one in linux/fs.h (inode_i_mutex_lock_class) is more complex than most. It looks like a parent/child locking rule would be sufficient for most trees.
Generic semaphores Posted Mar 23, 2008 23:33 UTC (Sun) by Alan.Stern (subscriber, #12437) [Link]
> It looks like a parent/child locking rule would be sufficient for most
> trees.
Only if you never need to hold more than two locks at a time. In general that isn't good
enough. (It certainly isn't good enough for the device tree!) Furthermore lockdep has a
limit of 8 subclasses; thus you won't be able to acquire the locks for all the nodes along a
branch if the branch is too long.
In addition, trees can have other, more complicated, access patterns which lockdep can't even
come close to handling. For instance, the rule about always acquiring locks going down a
branch can be generalized as follows:
Whenever you hold a lock on a node A, you must not acquire
a lock on node B unless you already hold the lock for the
closest common ancestor of A and B.
This rule allows you to acquire locks down a branch, but it allows other patterns as well. If
all threads follow the rule then deadlock can never occur (exercize!). Clearly this is far
beyond lockdep's ability to express.
|
|||||||||||||