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

Generic semaphores

Generic semaphores

Posted Mar 23, 2008 14:15 UTC (Sun) by Alan.Stern (subscriber, #12437)
In reply to: Generic semaphores by willy
Parent article: Generic semaphores

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


(Log in to post comments)

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