semantics of reader/writer semaphores in rt patch

semantics of reader/writer semaphores in rt patch

[Chris Friesen]

I recently noticed that when CONFIG_PREEMPT_RT_FULL is enabled we the 
semantics change.  From "include/linux/rwsem_rt.h":

  * Note that the semantics are different from the usual
  * Linux rw-sems, in PREEMPT_RT mode we do not allow
  * multiple readers to hold the lock at once, we only allow
  * a read-lock owner to read-lock recursively. This is
  * better for latency, makes the implementation inherently
  * fair and makes it simpler as well.

How is this valid?  It seems to me that there are any number of code 
paths that could depend on having multiple threads of execution be able 
to hold the reader lock simultaneously.  Something as simple as:

thread A:
take rw_semaphore X for reading
take lock Y, modify data, release lock Y
wake up thread B
wait on conditional protected by lock Y
free rw_semaphore X

thread B:
take rw_semaphore X for reading
wait on conditional protected by lock Y
send message to wake up thread A
free rw_semaphore X


In the regular kernel this would work, in the RT kernel it would deadlock.

Does the RT kernel just disallow this sort of algorithm?

Chris

Re: semantics of reader/writer semaphores in rt patch

[Thomas Gleixner]

On Thu, 23 Oct 2014, Chris Friesen wrote:

> I recently noticed that when CONFIG_PREEMPT_RT_FULL is enabled we the
> semantics change.  From "include/linux/rwsem_rt.h":
> 
>  * Note that the semantics are different from the usual
>  * Linux rw-sems, in PREEMPT_RT mode we do not allow
>  * multiple readers to hold the lock at once, we only allow
>  * a read-lock owner to read-lock recursively. This is
>  * better for latency, makes the implementation inherently
>  * fair and makes it simpler as well.
> 
> How is this valid?  It seems to me that there are any number of code paths
> that could depend on having multiple threads of execution be able to hold the
> reader lock simultaneously.  Something as simple as:
> 
> thread A:
> take rw_semaphore X for reading
> take lock Y, modify data, release lock Y
> wake up thread B
> wait on conditional protected by lock Y
> free rw_semaphore X
> 
> thread B:
> take rw_semaphore X for reading
> wait on conditional protected by lock Y
> send message to wake up thread A
> free rw_semaphore X

I don't see why B should wake A without changing the conditional. A
won't make progress by being woken by B as the conditional does not
magically change just because B wakes A.

So what you wanted to say is:

  thread B:
  take rw_semaphore X for reading
  wait on conditional protected by lock Y
+ take lock Y, modify data, release lock Y
  send message to wake up thread A
  free rw_semaphore X

Otherwise your example does not make any sense at all. And that has
some serious non RT related implications.

> In the regular kernel this would work, in the RT kernel it would deadlock.

Works by some definition of 'works'
 
> Does the RT kernel just disallow this sort of algorithm?

Yes. For a good reason. Let's add thread C

A    	   	B		C
down_read(X)
				down_write(X)
lock(Y)
modify data
unlock(Y)
wake(B)
		down_read(X)

Due to the mainline rwsem fairness semantics:

A holds X, C is blocked on A and B is blocked on A.

Deadlock, without RT and the single reader restriction being involved.

So RT does not violate ANY of the existing mainline semantics, it just
imposes a performance impact of not allowing multiple readers.

Aside of that it provides as usual the free of charge service to
expose mainline bugs faster.

Yes, it's valid and not that simple as you might think.

Thanks,

	tglx

Re: semantics of reader/writer semaphores in rt patch

[Thomas Gleixner]

On Sun, 26 Oct 2014, Thomas Gleixner wrote:
> On Thu, 23 Oct 2014, Chris Friesen wrote:
> > Does the RT kernel just disallow this sort of algorithm?
> 
> Yes. For a good reason. Let's add thread C
> 
> A    	   	B		C
> down_read(X)
> 				down_write(X)
> lock(Y)
> modify data
> unlock(Y)
> wake(B)
> 		down_read(X)
> 
> Due to the mainline rwsem fairness semantics:
> 
> A holds X, C is blocked on A and B is blocked on A.
> 
> Deadlock, without RT and the single reader restriction being involved.
> 
> So RT does not violate ANY of the existing mainline semantics, it just
> imposes a performance impact of not allowing multiple readers.

@peterz: It might be worthwhile to have a CONFIG_LOCKDEP=y dependent
mode which restricts concurrent readers to 1 in mainline to catch this
kind of stuff. Hmm?

Thanks,

	tglx

Re: semantics of reader/writer semaphores in rt patch

[Peter Zijlstra]

On Sun, Oct 26, 2014 at 12:21:31AM +0200, Thomas Gleixner wrote:
> On Sun, 26 Oct 2014, Thomas Gleixner wrote:
> > On Thu, 23 Oct 2014, Chris Friesen wrote:
> > > Does the RT kernel just disallow this sort of algorithm?
> > 
> > Yes. For a good reason. Let's add thread C
> > 
> > A    	   	B		C
> > down_read(X)
> > 				down_write(X)
> > lock(Y)
> > modify data
> > unlock(Y)
> > wake(B)
> > 		down_read(X)
> > 
> > Due to the mainline rwsem fairness semantics:
> > 
> > A holds X, C is blocked on A and B is blocked on A.
> > 
> > Deadlock, without RT and the single reader restriction being involved.
> > 
> > So RT does not violate ANY of the existing mainline semantics, it just
> > imposes a performance impact of not allowing multiple readers.
> 
> @peterz: It might be worthwhile to have a CONFIG_LOCKDEP=y dependent
> mode which restricts concurrent readers to 1 in mainline to catch this
> kind of stuff. Hmm?

There were patches by ego that fix lockdep's read side tracking. I need
to find a few spare days to look at those :/

Re: semantics of reader/writer semaphores in rt patch

[Peter Zijlstra]

On Sun, Oct 26, 2014 at 08:42:57AM +0100, Peter Zijlstra wrote:
> On Sun, Oct 26, 2014 at 12:21:31AM +0200, Thomas Gleixner wrote:
> > On Sun, 26 Oct 2014, Thomas Gleixner wrote:
> > > On Thu, 23 Oct 2014, Chris Friesen wrote:
> > > > Does the RT kernel just disallow this sort of algorithm?
> > > 
> > > Yes. For a good reason. Let's add thread C
> > > 
> > > A    	   	B		C
> > > down_read(X)
> > > 				down_write(X)
> > > lock(Y)
> > > modify data
> > > unlock(Y)
> > > wake(B)
> > > 		down_read(X)
> > > 
> > > Due to the mainline rwsem fairness semantics:
> > > 
> > > A holds X, C is blocked on A and B is blocked on A.
> > > 
> > > Deadlock, without RT and the single reader restriction being involved.
> > > 
> > > So RT does not violate ANY of the existing mainline semantics, it just
> > > imposes a performance impact of not allowing multiple readers.
> > 
> > @peterz: It might be worthwhile to have a CONFIG_LOCKDEP=y dependent
> > mode which restricts concurrent readers to 1 in mainline to catch this
> > kind of stuff. Hmm?
> 
> There were patches by ego that fix lockdep's read side tracking. I need
> to find a few spare days to look at those :/

Hmm, that's only for the rwlock_t because that has 'creative' locking
rules, I'm not sure why rwsem would need a distinction between read and
write at all; so something simple like the below might just be all we
need.

Entirely untested..

---
 include/linux/lockdep.h | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/include/linux/lockdep.h b/include/linux/lockdep.h
index 74ab23176e9b..10606beb5672 100644
--- a/include/linux/lockdep.h
+++ b/include/linux/lockdep.h
@@ -505,7 +505,7 @@ static inline void print_irqtrace_events(struct task_struct *curr)
 
 #define rwsem_acquire(l, s, t, i)		lock_acquire_exclusive(l, s, t, NULL, i)
 #define rwsem_acquire_nest(l, s, t, n, i)	lock_acquire_exclusive(l, s, t, n, i)
-#define rwsem_acquire_read(l, s, t, i)		lock_acquire_shared(l, s, t, NULL, i)
+#define rwsem_acquire_read(l, s, t, i)		lock_acquire_exclusive(l, s, t, NULL, i)
 #define rwsem_release(l, n, i)			lock_release(l, n, i)
 
 #define lock_map_acquire(l)			lock_acquire_exclusive(l, 0, 0, NULL, _THIS_IP_)

Re: semantics of reader/writer semaphores in rt patch

[Chris Friesen]

On 10/25/2014 04:19 PM, Thomas Gleixner wrote:
> On Thu, 23 Oct 2014, Chris Friesen wrote:
>
>> I recently noticed that when CONFIG_PREEMPT_RT_FULL is enabled we the
>> semantics change.  From "include/linux/rwsem_rt.h":
>>
>>   * Note that the semantics are different from the usual
>>   * Linux rw-sems, in PREEMPT_RT mode we do not allow
>>   * multiple readers to hold the lock at once, we only allow
>>   * a read-lock owner to read-lock recursively. This is
>>   * better for latency, makes the implementation inherently
>>   * fair and makes it simpler as well.
>>
>> How is this valid?  It seems to me that there are any number of code paths
>> that could depend on having multiple threads of execution be able to hold the
>> reader lock simultaneously.  Something as simple as:
>>
>> thread A:
>> take rw_semaphore X for reading
>> take lock Y, modify data, release lock Y
>> wake up thread B
>> wait on conditional protected by lock Y
>> free rw_semaphore X
>>
>> thread B:
>> take rw_semaphore X for reading
>> wait on conditional protected by lock Y
>> send message to wake up thread A
>> free rw_semaphore X
>
> I don't see why B should wake A without changing the conditional. A
> won't make progress by being woken by B as the conditional does not
> magically change just because B wakes A.
>
> So what you wanted to say is:
>
>    thread B:
>    take rw_semaphore X for reading
>    wait on conditional protected by lock Y
> + take lock Y, modify data, release lock Y
>    send message to wake up thread A
>    free rw_semaphore X
>
> Otherwise your example does not make any sense at all. And that has
> some serious non RT related implications.


Yes, your reformulated version is what I meant to say.  Sorry for any 
confusion.


>> Does the RT kernel just disallow this sort of algorithm?
>
> Yes. For a good reason. Let's add thread C
>
> A    	   	B		C
> down_read(X)
> 				down_write(X)
> lock(Y)
> modify data
> unlock(Y)
> wake(B)
> 		down_read(X)
>
> Due to the mainline rwsem fairness semantics:
>
> A holds X, C is blocked on A and B is blocked on A.
>
> Deadlock, without RT and the single reader restriction being involved.


Crap, I had forgotten about the fairness semantics stuff.  That makes 
perfect sense.

Thanks for the explanation.

Chris