R/W semaphore changes

I see you've made some R/W semaphore changes...

| /*
|  * nested locking:
|  */

This comment is inadequate. Please be more explicit about when you're allowed to do this.

| extern void down_read_nested(struct rw_semaphore *sem, int subclass); | extern void down_write_nested(struct rw_semaphore *sem, int subclass);

Please, please, please don't. R/W semaphores are _not_ permitted to nest. That way lies deadlock.

| /*
|  * Take/release a lock when not the owner will release it:
|  */
| extern void down_read_non_owner(struct rw_semaphore *sem);
| extern void up_read_non_owner(struct rw_semaphore *sem);

Does that mean that the owner may not then release the semaphore? I presume not, but it's not entirely clear.

| # define down_read_nested(sem, subclass) down_read(sem)
| # define down_write_nested(sem, subclass) down_write(sem)

This is _not_ okay.

I also notice that you've out-of-lined the rwsems debugging wrappers in all situations. Please don't. On some archs this is going to slow things down. On FRV for example, this is converted to:

	0xc00437f0 <down_read+0>:	addi sp,-16,sp
	0xc00437f4 <down_read+4>:	sti fp,@(sp,0)
	0xc00437f8 <down_read+8>:	ori sp,0,fp
	0xc00437fc <down_read+12>:	movsg lr,gr5
	0xc0043800 <down_read+16>:	sti gr5,@(fp,8)
	0xc0043804 <down_read+20>:	call 0xc01ea910 <__down_read>
	0xc0043808 <down_read+24>:	ldi @(fp,8),gr5
	0xc004380c <down_read+28>:	ld @(fp,gr0),fp
	0xc0043810 <down_read+32>:	addi sp,16,sp
	0xc0043814 <down_read+36>:	jmpl @(gr5,gr0)

When previously __down_read would be called directly... This applies to every arch that uses the spinlock-based R/W sems. In FRV's case, you've required the loading of extra icache lines to no useful purpose. Now I do have GDB stub compiled in, so normally it would be shorter than this as it wouldn't normally save the frame pointer, and would probably tail-call.

If you must put your annotations somewhere, please place them in lib/rwsem*.c directly.

Please _only_ out-of-line the rwsem debugging wrappers when the appropriate config options are set. It is reasonable to do it then - it is debugging code after all, and therefore not enabled for normal operation.

Oh, and if you're going to out-of-line the rwsem debugging wrappers like this, please remove all the then-redundant PUSHL instructions from the inline asm in include/asm-i386/rwsem.h. They're then no longer required as there's no need to save registers that are callee-clobbered, since you're marking them clobbered anyway by interpolating an extra function call.

yet they do in places, there where there is a natural hierarchy..

why not?

Where? I believe the mm used to but no longer does.

They still aren't allowed to. Consider:

	CPU 1			CPU 2
	=======================	=======================
	-->down_read(&A);
	<--down_read(&A);
				-->down_write(&A);
				   --- SLEEPING ---
	-->down_read(&A);
	   --- DEADLOCKED ---

See above.

R/W semaphores are as completely fair as I can make them, and they do not keep track of who's currently been granted what sort of lock. This means they are liable to fall foul of the above deadlock sequence.

Any viable down_read()/down_write() nesting must be handled outside of rwsems themselves.

Also, assume down_write() nesting is permitted, what do you do in the following situation:

	CPU 1			CPU 2
	=======================	=======================
	-->down_write(&A);
	<--down_write(&A);
				-->down_read(&A);
				   --- SLEEPING ---
	-->foo();
	   -->down_write(&A);
	   <--down_write(&A);
	   ...
	   -->downgrade_write(&A);
	   <--downgrade_write(&A);
				   --- ??? ---
	   -->up_read(&A);
	      --- ??? ---
	   <--up_read(&A);
	<--foo();
	-->up_write(&A);
	   --- ??? ---
	<--up_write(&A);

David

you mean recursion, while nesting != recursion!
(for examples of nesting see the general lockdep documentation) With nesting we mean

down_read(&A);
down_read(&B);

where A and B are a similar lock but not the same exact instance (for example two inode locks of different inodes)

i think you misunderstood what nested locking means in the lockdep case. (and that is my fault, for not adding enough documentation to down_write_nested() and down_read_nested().)

nested locking does not mean the same instance is allowed to nest! It only allows different-instance nesting, 'nesting within the same lock class'. (Lockdep has a very broad notion of 'lock class', to achieve the collection of very generic locking rules and to do as generic validation as possible. See Documentation/lockdep-design.txt for more details.)

Rw-locks on the other hand have special permission to nest for the same instance too. See commit 6c9076ec9cd448f43bbda871352a7067f456ee26:

lockdep so far only allowed read-recursion for the same lock instance. This is enough in the overwhelming majority of cases, but a hostap case triggered and reported by Miles Lane relies on same-class different-instance recursion. So we relax the restriction on read-lock recursion.

(This change does not allow rwsem read-recursion, which is still forbidden.)

also please see the testcases in lib/locking-selftest.c, we specifically test the rwsem scenario you outlined above, to make sure the validator immediately flags it:

------------------------
| Locking API testsuite:
----------------------------------------------------------------------------
| spin |wlock |rlock |mutex | wsem | rsem |
--------------------------------------------------------------------------
[...]

              recursive read-lock:             |  ok  |             |  ok  |
           recursive read-lock #2:             |  ok  |             |  ok  |

[...]

Ingo

the patch below adds more documentation.

Ingo

---------------->
Subject: [patch] lockdep: add more rwsem.h documentation
From: Ingo Molnar <[email protected]>

add more documentation to rwsem.h.

---
 include/linux/rwsem.h |   17 +++++++++++++++--
 1 file changed, 15 insertions(+), 2 deletions(-)

Index: linux/include/linux/rwsem.h
===================================================================
@@ -61,12 +61,25 @@ extern void downgrade_write(struct rw_se
 
 #ifdef CONFIG_DEBUG_LOCK_ALLOC
 /*
- * nested locking:
+ * nested locking. NOTE: rwsems are not allowed to recurse
+ * (which occurs if the same task tries to acquire the same
+ * lock instance multiple times), but multiple locks of the
+ * same lock class might be taken, if the order of the locks
+ * is always the same. This ordering rule can be expressed
+ * to lockdep via the _nested() APIs, but enumerating the
+ * subclasses that are used. (If the nesting relationship is
+ * static then another method for expressing nested locking is
+ * the explicit definition of lock class keys and the use of
+ * lockdep_set_class() at lock initialization time.
+ * See Documentation/lockdep-design.txt for more details.)
  */
 extern void down_read_nested(struct rw_semaphore *sem, int subclass);
 extern void down_write_nested(struct rw_semaphore *sem, int subclass);
 /*
- * Take/release a lock when not the owner will release it:
+ * Take/release a lock when not the owner will release it.
+ *
+ * [ This API should be avoided as much as possible - the
+ *   proper abstraction for this case is completions. ]
  */
 extern void down_read_non_owner(struct rw_semaphore *sem);
 extern void up_read_non_owner(struct rw_semaphore *sem);