User: Password:
|
|
Subscribe / Log in / New account

Generic semaphores

Generic semaphores

Posted Mar 22, 2008 13:47 UTC (Sat) by Alan.Stern (subscriber, #12437)
In reply to: Generic semaphores by willy
Parent article: Generic semaphores

> lockdep would be right to moan about that -- if you have two tasks
> trying to do that, they can deadlock against each other.

There you go -- you are suffering the same weakness as lockdep.  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.)  This
sort of constraint could potentially be represented within lockdep, but right now there's no
way to do it.

> The real problem with lockdep is that mutexes have an owner and
> semaphores simply don't.

That isn't a problem with lockdep; it's a problem with trying to use lockdep to track general
semaphore usage.  Lack of explicit parents for semaphores hasn't prevented many semaphores
from being converted to mutexes, complete with lockdep monitoring.

My point was that even though a semaphore may be used for simple mutual exclusion in a way
that should be compatible with replacement by a mutex, the replacement can't be carried out if
the semaphore is being used to lock members of a tree.


(Log in to post comments)

Generic semaphores

Posted Mar 23, 2008 13:37 UTC (Sun) by willy (subscriber, #9762) [Link]

> 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.

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.


Copyright © 2017, Eklektix, Inc.
Comments and public postings are copyrighted by their creators.
Linux is a registered trademark of Linus Torvalds