R/W semaphore changes

R/W semaphore changes

[David Howells]

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.

Re: R/W semaphore changes

[Arjan van de Ven]

On Tue, 2006-07-04 at 13:47 +0100, David Howells wrote:
> 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.

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

> | # define down_read_nested(sem, subclass)		down_read(sem)
> | # define down_write_nested(sem, subclass)	down_write(sem)
> 
> This is _not_ okay.

why not?

Re: R/W semaphore changes

[David Howells]

Arjan van de Ven <arjan@infradead.org> wrote:

> > Please, please, please don't.  R/W semaphores are _not_ permitted to nest.
> 
> yet they do in places, there where there is a natural hierarchy..

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

> > | # define down_read_nested(sem, subclass)		down_read(sem)
> > | # define down_write_nested(sem, subclass)	down_write(sem)
> > 
> > This is _not_ okay.
> 
> why not?

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

Re: R/W semaphore changes

[Arjan van de Ven]

On Tue, 2006-07-04 at 14:05 +0100, David Howells wrote:
> Arjan van de Ven <arjan@infradead.org> wrote:
> 
> > > Please, please, please don't.  R/W semaphores are _not_ permitted to nest.
> > 
> > yet they do in places, there where there is a natural hierarchy..
> 
> 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 ---

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)

Re: R/W semaphore changes

[Ingo Molnar]

* David Howells <dhowells@redhat.com> wrote:

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

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

[patch] lockdep: add more rwsem.h documentation

[Ingo Molnar]

* Ingo Molnar <mingo@elte.hu> wrote:

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

the patch below adds more documentation.

	Ingo

---------------->
Subject: [patch] lockdep: add more rwsem.h documentation
From: Ingo Molnar <mingo@elte.hu>

add more documentation to rwsem.h.

Signed-off-by: Ingo Molnar <mingo@elte.hu>
---
 include/linux/rwsem.h |   17 +++++++++++++++--
 1 file changed, 15 insertions(+), 2 deletions(-)

Index: linux/include/linux/rwsem.h
===================================================================
--- linux.orig/include/linux/rwsem.h
+++ 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);