semantics of reader/writer semaphores in rt patch

DISCUSSION Chris Friesen 3 participants 6 messages Oct 23, 2014 – Oct 27, 2014 Locking primitives

Share & tools

Chris Friesen

author

2014-10-23 19:27 UTC #0 lore raw

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

Thomas Gleixner

2014-10-25 22:19 UTC #1 lore raw

Quoted 21 lines · 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

Quoted 5 lines

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.

Quoted 1 line

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

Works by some definition of 'works'

Quoted 1 line

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

Thomas Gleixner

2014-10-25 22:21 UTC #2 lore raw

Quoted 14 lines · Thomas Gleixner

Quoted 1 line · Chris Friesen
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)

Quoted 8 lines

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

Peter Zijlstra

maintainer

2014-10-26 07:43 UTC #3 lore raw

Quoted 19 lines · Thomas Gleixner

Quoted 18 lines · Thomas Gleixner
Quoted 1 line · Chris Friesen
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.

Quoted 8 lines

Quoted 4 lines
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 :/

Peter Zijlstra

maintainer

2014-10-26 08:47 UTC #4 lore raw

Quoted 25 lines · Peter Zijlstra

Quoted 24 lines · Thomas Gleixner
Quoted 22 lines · Thomas Gleixner
Quoted 1 line · Chris Friesen
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.

Quoted 6 lines

Quoted 3 lines
@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(-)

include/linux/lockdep.h +1 -1

index 74ab23176e9b..10606beb5672 100644
@@ -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_)

Chris Friesen

author

2014-10-27 15:02 UTC #5 lore raw

In reply to Thomas Gleixner

Quoted 42 lines · Thomas Gleixner

Quoted 21 lines · 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
Quoted 5 lines
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

Quoted 2 lines

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.

Quoted 13 lines

Quoted 1 line
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)

Quoted 5 lines

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