locking/rwbase: Prevent indefinite writer starvation
Subsystems (2)
PATCH v2 1/1 locking/rwbase: Prevent indefinite writer starvation
rw_semaphore and rwlock are explicitly unfair to writers in the presense of readers by design with a PREEMPT_RT configuration. Commit 943f0edb754f ("locking/rt: Add base code for RT rw_semaphore and rwlock") notes;
The implementation is writer unfair, as it is not feasible to do priority inheritance on multiple readers, but experience has shown that real-time workloads are not the typical workloads which are sensitive to writer starvation.
While atypical, it's also trivial to block writers with PREEMPT_RT indefinitely without ever making forward progress. Since LTP-20220121, the dio_truncate test case went from having 1 reader to having 16 readers and the number of readers is sufficient to prevent the down_write ever succeeding while readers exist. Eventually the test is killed after 30 minutes as a failure.
dio_truncate is not a realtime application but indefinite writer starvation is undesirable. The test case has one writer appending and truncating files A and B while multiple readers read file A. The readers and writer are contending for one file's inode lock which never succeeds as the readers keep reading until the writer is done which never happens.
This patch records a timestamp when the first writer is blocked if no deadline or realtime task has recently acquired the lock for read. If dt/rt tasks are involved, then reader bias is preserved. For other tasks, reader bias is allowed until the first writer has been blocked for a minimum of 4ms or 1 tick. The cutoff time is arbitrary on the assumption that a normal application contending for 4ms also does not need PREEMPT_RT. On a test machine, the test completed in 88 seconds.
--- include/linux/rwbase_rt.h | 3 ++ kernel/locking/rwbase_rt.c | 84 +++++++++++++++++++++++++++++++++++++++++++--- 2 files changed, 82 insertions(+), 5 deletions(-)
include/linux/rwbase_rt.h +3 -0
@@ -10,12 +10,14 @@struct rwbase_rt {atomic_t readers; +unsigned long waiter_blocked;struct rt_mutex_base rtmutex; };#define __RWBASE_INITIALIZER (name) \ { \ .readers = ATOMIC_INIT(READER_BIAS), \ + .waiter_blocked = 0, \ .rtmutex = __RT_MUTEX_BASE_INITIALIZER(name.rtmutex), \ }
@@ -23,6 +25,7 @@ struct rwbase_rt {do { \rt_mutex_base_init (&(rwbase)->rtmutex); \atomic_set (&(rwbase)->readers,READER_BIAS ); \ + (rwbase)->waiter_blocked =0 ; \ }while (0 )
kernel/locking/rwbase_rt.c +79 -5
123 lines not on this page · raw message
A message that is not in the archive (sent off-list or not yet received): [email protected]
Quoted 42 lines · Hillf Danton
On Tue, 17 Jan 2023 08:38:17 +0000 Mel Gorman <[email protected]>
Quoted 41 lines
kernel/locking/rwbase_rt.c +41
-0+/* +* Allow reader bias with a pending writer for a minimum of 4ms or 1 tick. +* The granularity is not exact as the lowest bit in rwbase_rt->waiter_blocked +* is used to detect recent rt/dl tasks taking a read lock. +*/ +#define RW_CONTENTION_THRESHOLD (HZ/250+1) + +static void __sched update_dlrt_reader(struct rwbase_rt *rwb) +{ +/* No update required if dl/rt tasks already identified. */ +if (rwb->waiter_blocked &1 ) +return ; + +/* +* Record a dl/rt task acquiring the lock for read. This may result +* in indefinite writer starvation but dl/rt tasks should avoid such +* behaviour. +*/ +if (dl_task (current) ||rt_task (current)) { +struct rt_mutex_base *rtm = &rwb->rtmutex; +unsigned long flags; + +raw_spin_lock_irqsave (&rtm->wait_lock, flags); + rwb->waiter_blocked |=1 ; +raw_spin_unlock_irqrestore (&rtm->wait_lock, flags); + } +} + +/* rtmutex->wait_lock must be held. */ +static void __sched set_writer_blocked(struct rwbase_rt *rwb) +{ +/* +* Lowest bit preserved to identify recent rt/dl tasks acquiring +* the lock for read so guarantee at least one tick delay. +*/ + rwb->waiter_blocked |= (jiffies +2 ) & ~1UL ; +} + +static bool __sched rwbase_allow_reader_bias(struct rwbase_rt *rwb) +{ +/*
Quoted 8 lines
kernel/locking/rwbase_rt.c static __always_inline int rwbase_read_trylock(struct rwbase_rt *rwb) · line 118
Quoted 6 lines
kernel/locking/rwbase_rt.c +6
-0+* Allow reader bias if a dl or rt task took the lock for read +* since the last write unlock. Such tasks should be designed +* to avoid heavy writer contention or indefinite starvation. +*/ +if (rwb->waiter_blocked &1 ) +return true;This true opens a window for two tons of readers, no?
I don't understand the question or what you mean by two tons of readers. In case you mean that the threshold is not precise, it's noted earlier in a comment.
* The granularity is not exact as the lowest bit in rwbase_rt->waiter_blocked
* is used to detect recent rt/dl tasks taking a read lock.
Quoted 9 lines
kernel/locking/rwbase_rt.c static __always_inline int rwbase_read_trylock(struct rwbase_rt *rwb) · line 124
Quoted 6 lines
kernel/locking/rwbase_rt.c +6
-0+ +/* +* Allow reader bias unless a writer has been blocked for more +* than RW_CONTENTION_THRESHOLD jiffies. +*/ +return jiffies - rwb->waiter_blocked <RW_CONTENTION_THRESHOLD ;Why pure 4ms deadline fails to work without taking care of dlrt tasks?
I don't understand the question. For DL/RT tasks taking the lock for read, indefinite writer starvation is still possible. It is assumed DL/RT tasks take care to avoid the scenario. For other tasks, 4 ms is an arbitrary cutoff so forward progress is made.
Quoted 2 lines
Given it would take 88 seconds to complete the test, is it going to take 100 seconds or more for the 4ms deadline?
It took 88 seconds to complete the test. Without the patch, the test never finishes and is eventually killed after a timeout and marked as failure. Actual time to completion will vary depending on the machine, number of CPUs and speed of storage. The point isn't how fast the test completes, the point is that the test completes successfully.
Signature · 2 lines
Mel Gorman SUSE Labs
Quoted 9 lines · Mel Gorman
rw_semaphoreand rwlock are explicitly unfair to writers in the presense of readers by design with aPREEMPT_RTconfiguration. Commit943f0edb754f("locking/rt: Add base code for RTrw_semaphoreand rwlock") notes;The implementation is writer unfair, as it is not feasible to do priority inheritance on multiple readers, but experience has shown that real-time workloads are not the typical workloads which are sensitive to writer starvation.
Quoted 8 lines
While atypical, it's also trivial to block writers with
PREEMPT_RTindefinitely without ever making forward progress. Since LTP-20220121, thedio_truncatetest case went from having 1 reader to having 16 readers and the number of readers is sufficient to prevent thedown_writeever succeeding while readers exist. Eventually the test is killed after 30 minutes as a failure.
dio_truncateis not a realtime application but indefinite writer starvation
If so then the PI boosting would not work if we would have it ;)
Quoted 4 lines
is undesirable. The test case has one writer appending and truncating files A and B while multiple readers read file A. The readers and writer are contending for one file's inode lock which never succeeds as the readers keep reading until the writer is done which never happens.
This tests the implementation of rwsem/ rwlock functionality to ensure that it is not writer unfair.
Quoted 3 lines
This patch records a timestamp when the first writer is blocked if no deadline or realtime task has recently acquired the lock for read. If dt/rt tasks are involved, then reader bias is preserved. For other tasks,
DL/ RT. Would it work to use the capital letters if it refers to the scheduling class?
Quoted 4 lines
reader bias is allowed until the first writer has been blocked for a minimum of 4ms or 1 tick. The cutoff time is arbitrary on the assumption that a normal application contending for 4ms also does not need
PREEMPT_RT. On a test machine, the test completed in 88 seconds.
I would go for one second just because it _usually_ does not matter since none of the important locks rely on that (as stated in the commit message). But then why not use the 4ms/ 1 tick as you suggest. This is after all what the NON-PREEMPT_RT implementation is using to ensure that the writer is not stalled infinitely. The RWLOCK implementation is already writer unfair.
Side note: If the test case gets updated to RT reader which acquire the lock (the whole time) then they will block writer again :)
Quoted 38 lines
Signed-off-by Mel Gorman <[email protected]>--- include/linux/rwbase_rt.h | 3 ++ kernel/locking/rwbase_rt.c | 84 +++++++++++++++++++++++++++++++++++++++++++--- 2 files changed, 82 insertions(+), 5 deletions(-)include/linux/rwbase_rt.h +3
-0@@ -10,12 +10,14 @@struct rwbase_rt {atomic_t readers; +unsigned long waiter_blocked;struct rt_mutex_base rtmutex; };#define __RWBASE_INITIALIZER (name) \ { \ .readers = ATOMIC_INIT(READER_BIAS), \ + .waiter_blocked = 0, \ .rtmutex = __RT_MUTEX_BASE_INITIALIZER(name.rtmutex), \ }@@ -23,6 +25,7 @@ struct rwbase_rt {do { \rt_mutex_base_init (&(rwbase)->rtmutex); \atomic_set (&(rwbase)->readers,READER_BIAS ); \ + (rwbase)->waiter_blocked =0 ; \ }while (0 )kernel/locking/rwbase_rt.c +0
-0
kernel/locking/rwbase_rt.c line 45
Quoted 8 lines
kernel/locking/rwbase_rt.c +4
-1@@ -39,7 +39,11 @@* major surgery for a very dubious value. * * The risk of writer starvation is there, but the pathological use cases -* which trigger it are not necessarily the typical RT workloads. +* which trigger it are not necessarily the typical RT workloads. The worst +* case of indefinite starvation of a writer will force readers into the +* slow path if a writer is blocked for more than RW_CONTENTION_THRESHOLD +* jiffies unless dl/rt tasks have taken a read lock since the last write
DL/RT please.
kernel/locking/rwbase_rt.c static __always_inline int rwbase_read_trylock(struct rwbase_rt *rwb) · line 73
Quoted 10 lines
kernel/locking/rwbase_rt.c +3
-0+* unlock. * * Fast-path orderings: * The lock/unlock of readers can run in fast paths: lock and unlock are only @@ -65,6 +69,61 @@ static __always_inline int rwbase_read_trylock(struct rwbase_rt *rwb)return 0 ; } +/* +* Allow reader bias with a pending writer for a minimum of 4ms or 1 tick.
* This matches RWSEM_WAIT_TIMEOUT for the generic RWSEM
* implementation.
kernel/locking/rwbase_rt.c static __always_inline int rwbase_read_trylock(struct rwbase_rt *rwb) · line 77
Quoted 4 lines
kernel/locking/rwbase_rt.c +4
-0+* The granularity is not exact as the lowest bit in rwbase_rt->waiter_blocked +* is used to detect recent rt/dl tasks taking a read lock. +*/ +#define RW_CONTENTION_THRESHOLD (HZ/250+1)
DIV_ROUND_UP(HZ, 250)
kernel/locking/rwbase_rt.c static __always_inline int rwbase_read_trylock(struct rwbase_rt *rwb) · line 86
Quoted 8 lines
kernel/locking/rwbase_rt.c +8
-0+static void __sched update_dlrt_reader(struct rwbase_rt *rwb) +{ +/* No update required if dl/rt tasks already identified. */ +if (rwb->waiter_blocked &1 ) +return ; + +/* +* Record a dl/rt task acquiring the lock for read. This may result
DL/RT
kernel/locking/rwbase_rt.c static __always_inline int rwbase_read_trylock(struct rwbase_rt *rwb) · line 90
Quoted 4 lines
kernel/locking/rwbase_rt.c +4
-0+* in indefinite writer starvation but dl/rt tasks should avoid such +* behaviour. +*/ +if (dl_task (current) ||rt_task (current)) {
There is also task_is_realtime(). But using only rt_task() should work since it also covers dl_task().
Quoted 7 lines
kernel/locking/rwbase_rt.c +7
-0+struct rt_mutex_base *rtm = &rwb->rtmutex; +unsigned long flags; + +raw_spin_lock_irqsave (&rtm->wait_lock, flags); + rwb->waiter_blocked |=1 ; +raw_spin_unlock_irqrestore (&rtm->wait_lock, flags); + }
kernel/locking/rwbase_rt.c static __always_inline int rwbase_read_trylock(struct rwbase_rt *rwb) · line 107
Quoted 10 lines
kernel/locking/rwbase_rt.c +10
-0+} + +/* rtmutex->wait_lock must be held. */ +static void __sched set_writer_blocked(struct rwbase_rt *rwb) +{ +/* +* Lowest bit preserved to identify recent rt/dl tasks acquiring +* the lock for read so guarantee at least one tick delay. +*/ + rwb->waiter_blocked |= (jiffies +2 ) & ~1UL ;
I'm unsure what |= means in terms of multiple writers. It seems to extend the wait period and the second writer has none after the first one leaves.
Quoted 7 lines
kernel/locking/rwbase_rt.c +7
-0+} + +static bool __sched rwbase_allow_reader_bias(struct rwbase_rt *rwb) +{ +/* +* Allow reader bias if a dl or rt task took the lock for read +* since the last write unlock. Such tasks should be designed
kernel/locking/rwbase_rt.c static __always_inline int rwbase_read_trylock(struct rwbase_rt *rwb) · line 124
Quoted 10 lines
kernel/locking/rwbase_rt.c +10
-0+* to avoid heavy writer contention or indefinite starvation. +*/ +if (rwb->waiter_blocked &1 ) +return true; + +/* +* Allow reader bias unless a writer has been blocked for more +* than RW_CONTENTION_THRESHOLD jiffies. +*/ +return jiffies - rwb->waiter_blocked <RW_CONTENTION_THRESHOLD ;
if you set
rwb->waiter_blocked = jiffies + RW_CONTENTION_THRESHOLD
then you could use
time_after(jiffies, waiter->waiter_blocked)
and we could name it timeout. So the first writer sets it and my guess would be that the each RT reader ignores this delay while every non-RT tries to acquire the lock unless as long as the timeout did not occur. Then they back off and wait for one writer to acquire the lock. I don't know what we do with the possible second writer but I guess first writer on unlock should reset the timeout for the next writer. So we have again reader followed by writer.
Quoted 48 lines
kernel/locking/rwbase_rt.c +19
-4+} + static int __sched __rwbase_read_lock(struct rwbase_rt *rwb,unsigned int state) {@@ -74,9 +133,11 @@ static int __sched __rwbase_read_lock(struct rwbase_rt *rwb,raw_spin_lock_irq (&rtm->wait_lock);/* * Allow readers, as long as the writer has not completely -* acquired the semaphore for write. +* acquired the semaphore for write and reader bias is still +* allowed. */ -if (atomic_read (&rwb->readers) !=WRITER_BIAS ) { +if (atomic_read (&rwb->readers) !=WRITER_BIAS && +rwbase_allow_reader_bias (rwb)) {atomic_inc (&rwb->readers);raw_spin_unlock_irq (&rtm->wait_lock);return 0 ;@@ -140,10 +201,18 @@ static int __sched __rwbase_read_lock(struct rwbase_rt *rwb, static __always_inline int rwbase_read_lock(struct rwbase_rt *rwb,unsigned int state) { +int ret; +if (rwbase_read_trylock (rwb)) -return 0 ; + ret =0 ; +else + ret =__rwbase_read_lock (rwb, state); + +/* Record if the current task acquiring the lock is a dl/rt task. */ +if (!ret) +update_dlrt_reader (rwb); -return __rwbase_read_lock (rwb, state); +return ret; } static void __sched __rwbase_read_unlock(struct rwbase_rt *rwb,@@ -264,12 +333,17 @@ static int __sched rwbase_write_lock(struct rwbase_rt *rwb,if (__rwbase_write_trylock (rwb))break ; +/* Record first new read/write contention. */ +set_writer_blocked (rwb); +raw_spin_unlock_irqrestore (&rtm->wait_lock, flags);
kernel/locking/rwbase_rt.c static int __sched rwbase_write_lock(struct rwbase_rt *rwb, · line 349
Quoted 10 lines
kernel/locking/rwbase_rt.c +2
-0rwbase_schedule ();raw_spin_lock_irqsave (&rtm->wait_lock, flags);set_current_state (state); } + + rwb->waiter_blocked =0 ;rwbase_restore_current_state ();trace_contention_end (rwb,0 );
Sebastian
Quoted 17 lines · Sebastian Andrzej Siewior
Quoted 16 lines · Mel Gorman
rw_semaphoreand rwlock are explicitly unfair to writers in the presense of readers by design with aPREEMPT_RTconfiguration. Commit943f0edb754f("locking/rt: Add base code for RTrw_semaphoreand rwlock") notes;The implementation is writer unfair, as it is not feasible to do priority inheritance on multiple readers, but experience has shown that real-time workloads are not the typical workloads which are sensitive to writer starvation.
While atypical, it's also trivial to block writers with
PREEMPT_RTindefinitely without ever making forward progress. Since LTP-20220121, thedio_truncatetest case went from having 1 reader to having 16 readers and the number of readers is sufficient to prevent thedown_writeever succeeding while readers exist. Eventually the test is killed after 30 minutes as a failure.
Quoted 4 lines
Quoted 1 line
dio_truncateis not a realtime application but indefinite writer starvationIf so then the PI boosting would not work if we would have it ;)
True, but it's still undesirable for a basic functional test using normal tasks with no prioritisation to stall forever.
Quoted 8 lines
Quoted 4 lines
is undesirable. The test case has one writer appending and truncating files A and B while multiple readers read file A. The readers and writer are contending for one file's inode lock which never succeeds as the readers keep reading until the writer is done which never happens.
This tests the implementation of rwsem/ rwlock functionality to ensure that it is not writer unfair.
Also true but in this case at least, the test's tasks do not care about priority inheritance.
Quoted 6 lines
Quoted 3 lines
This patch records a timestamp when the first writer is blocked if no deadline or realtime task has recently acquired the lock for read. If dt/rt tasks are involved, then reader bias is preserved. For other tasks,
DL/ RT. Would it work to use the capital letters if it refers to the scheduling class?
Sure.
Quoted 5 lines
Quoted 4 lines
reader bias is allowed until the first writer has been blocked for a minimum of 4ms or 1 tick. The cutoff time is arbitrary on the assumption that a normal application contending for 4ms also does not need
PREEMPT_RT. On a test machine, the test completed in 88 seconds.
Quoted 7 lines
I would go for one second just because it _usually_ does not matter since none of the important locks rely on that (as stated in the commit message). But then why not use the 4ms/ 1 tick as you suggest. This is after all what the NON-PREEMPT_RT implementation is using to ensure that the writer is not stalled infinitely. The RWLOCK implementation is already writer unfair.
1 second is a relatively long time. The test would eventually complete but not before the 30 minute timeout hits and kills the test anyway. It makes more sense to explicitly make it similar to RWSEM_WAIT_TIMEOUT.
Quoted 3 lines
Side note: If the test case gets updated to RT reader which acquire the lock (the whole time) then they will block writer again :)
True, but in that case a RT-specific test showed that the lock is writer unfair and no one is surprised. It's the test design equivalent of "stop hitting yourself" until the lock is writer fair assuming that happens.
Quoted 33 lines
Quoted 33 lines
Signed-off-by Mel Gorman <[email protected]>--- include/linux/rwbase_rt.h | 3 ++ kernel/locking/rwbase_rt.c | 84 +++++++++++++++++++++++++++++++++++++++++++--- 2 files changed, 82 insertions(+), 5 deletions(-)include/linux/rwbase_rt.h +3
-0@@ -10,12 +10,14 @@struct rwbase_rt {atomic_t readers; +unsigned long waiter_blocked;struct rt_mutex_base rtmutex; };#define __RWBASE_INITIALIZER (name) \ { \ .readers = ATOMIC_INIT(READER_BIAS), \ + .waiter_blocked = 0, \ .rtmutex = __RT_MUTEX_BASE_INITIALIZER(name.rtmutex), \ }@@ -23,6 +25,7 @@ struct rwbase_rt {do { \rt_mutex_base_init (&(rwbase)->rtmutex); \atomic_set (&(rwbase)->readers,READER_BIAS ); \ + (rwbase)->waiter_blocked =0 ; \ }while (0 )
Quoted 16 lines
kernel/locking/rwbase_rt.c line 45
Quoted 13 lines
kernel/locking/rwbase_rt.c +4
-1@@ -39,7 +39,11 @@* major surgery for a very dubious value. * * The risk of writer starvation is there, but the pathological use cases -* which trigger it are not necessarily the typical RT workloads. +* which trigger it are not necessarily the typical RT workloads. The worst +* case of indefinite starvation of a writer will force readers into the +* slow path if a writer is blocked for more than RW_CONTENTION_THRESHOLD +* jiffies unless dl/rt tasks have taken a read lock since the last write DL/RT please.
Done.
Quoted 8 lines
Quoted 8 lines
kernel/locking/rwbase_rt.c +1
-0+* unlock. * * Fast-path orderings: * The lock/unlock of readers can run in fast paths: lock and unlock are only @@ -65,6 +69,61 @@ static __always_inline int rwbase_read_trylock(struct rwbase_rt *rwb)return 0 ; }
Quoted 6 lines
kernel/locking/rwbase_rt.c static __always_inline int rwbase_read_trylock(struct rwbase_rt *rwb) · line 73
Quoted 2 lines
kernel/locking/rwbase_rt.c +2
-0+/* +* Allow reader bias with a pending writer for a minimum of 4ms or 1 tick. * This matches
RWSEM_WAIT_TIMEOUTfor the generic RWSEM
* implementation.
Done, but I also renamed the threshold to RWBASE_RT_WAIT_TIMEOUT.
Quoted 15 lines
kernel/locking/rwbase_rt.c static __always_inline int rwbase_read_trylock(struct rwbase_rt *rwb) · line 77
Quoted 4 lines
kernel/locking/rwbase_rt.c +4
-0+* The granularity is not exact as the lowest bit in rwbase_rt->waiter_blocked +* is used to detect recent rt/dl tasks taking a read lock. +*/ +#define RW_CONTENTION_THRESHOLD (HZ/250+1)DIV_ROUND_UP(HZ, 250)kernel/locking/rwbase_rt.c static __always_inline int rwbase_read_trylock(struct rwbase_rt *rwb) · line 85
Quoted 8 lines
kernel/locking/rwbase_rt.c +8
-0+static void __sched update_dlrt_reader(struct rwbase_rt *rwb) +{ +/* No update required if dl/rt tasks already identified. */ +if (rwb->waiter_blocked &1 ) +return ; + +/* +* Record a dl/rt task acquiring the lock for read. This may result DL/RT
Quoted 7 lines
kernel/locking/rwbase_rt.c static __always_inline int rwbase_read_trylock(struct rwbase_rt *rwb) · line 89
Quoted 4 lines
kernel/locking/rwbase_rt.c +4
-0+* in indefinite writer starvation but dl/rt tasks should avoid such +* behaviour. +*/ +if (dl_task (current) ||rt_task (current)) {There is also
task_is_realtime(). But using onlyrt_task()should work since it also coversdl_task().
True, changed to rt_task only.
Quoted 14 lines
Quoted 14 lines
kernel/locking/rwbase_rt.c +13
-0+struct rt_mutex_base *rtm = &rwb->rtmutex; +unsigned long flags; + +raw_spin_lock_irqsave (&rtm->wait_lock, flags); + rwb->waiter_blocked |=1 ; +raw_spin_unlock_irqrestore (&rtm->wait_lock, flags); + } +} + +/* rtmutex->wait_lock must be held. */ +static void __sched set_writer_blocked(struct rwbase_rt *rwb) +{ +/*
Quoted 9 lines
kernel/locking/rwbase_rt.c static __always_inline int rwbase_read_trylock(struct rwbase_rt *rwb) · line 106
Quoted 4 lines
kernel/locking/rwbase_rt.c +4
-0+* Lowest bit preserved to identify recent rt/dl tasks acquiring +* the lock for read so guarantee at least one tick delay. +*/ + rwb->waiter_blocked |= (jiffies +2 ) & ~1UL ;I'm unsure what |= means in terms of multiple writers. It seems to extend the wait period and the second writer has none after the first one leaves.
That's an oversight as v1 only covered the first writer. The unguarded check turns into garbage for multiple writers.
Quoted 24 lines
Quoted 7 lines
kernel/locking/rwbase_rt.c +7
-0+} + +static bool __sched rwbase_allow_reader_bias(struct rwbase_rt *rwb) +{ +/* +* Allow reader bias if a dl or rt task took the lock for read +* since the last write unlock. Such tasks should be designed kernel/locking/rwbase_rt.c static __always_inline int rwbase_read_trylock(struct rwbase_rt *rwb) · line 123
Quoted 10 lines
kernel/locking/rwbase_rt.c +10
-0+* to avoid heavy writer contention or indefinite starvation. +*/ +if (rwb->waiter_blocked &1 ) +return true; + +/* +* Allow reader bias unless a writer has been blocked for more +* than RW_CONTENTION_THRESHOLD jiffies. +*/ +return jiffies - rwb->waiter_blocked <RW_CONTENTION_THRESHOLD ;if you set
rwb->waiter_blocked = jiffies + RW_CONTENTION_THRESHOLDthen you could use
time_after(jiffies, waiter->waiter_blocked)
Quoted 8 lines
and we could name it timeout. So the first writer sets it and my guess would be that the each RT reader ignores this delay while every non-RT tries to acquire the lock unless as long as the timeout did not occur. Then they back off and wait for one writer to acquire the lock. I don't know what we do with the possible second writer but I guess first writer on unlock should reset the timeout for the next writer. So we have again reader followed by writer.
The second writer was an oversight. I think it's better to keep it simple and let the first writer blocked determine when reader bias finishes. The timeout resets when the write lock is released.
Thanks Sebastian. Based on your feedback, v3 looks like this
--8<--
locking/rwbase: Prevent indefinite writer starvation
rw_semaphore and rwlock are explicitly unfair to writers in the presense of readers by design with a PREEMPT_RT configuration. Commit 943f0edb754f ("locking/rt: Add base code for RT rw_semaphore and rwlock") notes;
The implementation is writer unfair, as it is not feasible to do priority inheritance on multiple readers, but experience has shown that real-time workloads are not the typical workloads which are sensitive to writer starvation.
While atypical, it's also trivial to block writers with PREEMPT_RT indefinitely without ever making forward progress. Since LTP-20220121, the dio_truncate test case went from having 1 reader to having 16 readers and the number of readers is sufficient to prevent the down_write ever succeeding while readers exist. Eventually the test is killed after 30 minutes as a failure.
dio_truncate is not a realtime application but indefinite writer starvation is undesirable. The test case has one writer appending and truncating files A and B while multiple readers read file A. The readers and writer are contending for one file's inode lock which never succeeds as the readers keep reading until the writer is done which never happens.
This patch records a timestamp when the first writer is blocked if no deadline or realtime task has recently acquired the lock for read. If DT / RT tasks are involved, then reader bias priority inheritance is preserved. For other tasks, reader bias is allowed until the first writer has been blocked for a minimum of 4ms similar to RWSEM_WAIT_TIMEOUT. This is sufficient to allow the test case to complete within the 30 minutes timeout.
--- include/linux/rwbase_rt.h | 3 ++ kernel/locking/rwbase_rt.c | 87 +++++++++++++++++++++++++++++++++++++++++++--- 2 files changed, 85 insertions(+), 5 deletions(-)
include/linux/rwbase_rt.h +3 -0
@@ -10,12 +10,14 @@struct rwbase_rt {atomic_t readers; +unsigned long waiter_timeout;struct rt_mutex_base rtmutex; };#define __RWBASE_INITIALIZER (name) \ { \ .readers = ATOMIC_INIT(READER_BIAS), \ + .waiter_timeout = 0, \ .rtmutex = __RT_MUTEX_BASE_INITIALIZER(name.rtmutex), \ }
@@ -23,6 +25,7 @@ struct rwbase_rt {do { \rt_mutex_base_init (&(rwbase)->rtmutex); \atomic_set (&(rwbase)->readers,READER_BIAS ); \ + (rwbase)->waiter_timeout =0 ; \ }while (0 )
kernel/locking/rwbase_rt.c +82 -5
126 lines not on this page · raw message
Quoted 8 lines · Mel Gorman
Quoted 5 lines
Quoted 2 lines
dio_truncateis not a realtime application but indefinite writer starvationIf so then the PI boosting would not work if we would have it ;)
True, but it's still undesirable for a basic functional test using normal tasks with no prioritisation to stall forever.
Agreed.
Quoted 18 lines
kernel/locking/rwbase_rt.c +18
-0+/* +* Allow reader bias with a pending writer for a minimum of 4ms or 1 tick. +* This matches RWSEM_WAIT_TIMEOUT for the generic RWSEM implementation. +* The granularity is not exact as the lowest bit in rwbase_rt->waiter_timeout +* is used to detect recent DL / RT tasks taking a read lock. +*/ +#define RWBASE_RT_WAIT_TIMEOUT DIV_ROUND_UP(HZ, 250) + +static void __sched update_dlrt_reader(struct rwbase_rt *rwb) +{ +/* No update required if DL / RT tasks already identified. */ +if (rwb->waiter_timeout &1 ) +return ; + +/* +* Record a DL / RT task acquiring the lock for read. This may result +* in indefinite writer starvation but DL / RT tasks should avoid such +* behaviour.
kernel/locking/rwbase_rt.c static __always_inline int rwbase_read_trylock(struct rwbase_rt *rwb) · line 99
Quoted 10 lines
kernel/locking/rwbase_rt.c +10
-0+*/ +if (rt_task (current)) { +struct rt_mutex_base *rtm = &rwb->rtmutex; +unsigned long flags; + +raw_spin_lock_irqsave (&rtm->wait_lock, flags); + rwb->waiter_timeout |=1 ; +raw_spin_unlock_irqrestore (&rtm->wait_lock, flags); + } +}
So I'm not sure this should be dependent on the task being an RT task.
Starvation scenarios are bad no matter what scheduling policy is used.
Should be unconditional - and all workloads should live with the new behavior.
Thanks,
Ingo
Quoted 32 lines · Ingo Molnar
Quoted 19 lines
kernel/locking/rwbase_rt.c +18
-0+/* +* Allow reader bias with a pending writer for a minimum of 4ms or 1 tick. +* This matches RWSEM_WAIT_TIMEOUT for the generic RWSEM implementation. +* The granularity is not exact as the lowest bit in rwbase_rt->waiter_timeout +* is used to detect recent DL / RT tasks taking a read lock. +*/ +#define RWBASE_RT_WAIT_TIMEOUT DIV_ROUND_UP(HZ, 250) + +static void __sched update_dlrt_reader(struct rwbase_rt *rwb) +{ +/* No update required if DL / RT tasks already identified. */ +if (rwb->waiter_timeout &1 ) +return ; + +/* +* Record a DL / RT task acquiring the lock for read. This may result +* in indefinite writer starvation but DL / RT tasks should avoid such +* behaviour. kernel/locking/rwbase_rt.c static __always_inline int rwbase_read_trylock(struct rwbase_rt *rwb) · line 99
Quoted 10 lines
kernel/locking/rwbase_rt.c +10
-0+*/ +if (rt_task (current)) { +struct rt_mutex_base *rtm = &rwb->rtmutex; +unsigned long flags; + +raw_spin_lock_irqsave (&rtm->wait_lock, flags); + rwb->waiter_timeout |=1 ; +raw_spin_unlock_irqrestore (&rtm->wait_lock, flags); + } +}So I'm not sure this should be dependent on the task being an RT task.
Quoted 5 lines
Starvation scenarios are bad no matter what scheduling policy is used.
Should be unconditional - and all workloads should live with the new behavior.
The DL / RT task special casing was based on feedback given here
https://lore.kernel.org/r/[email protected].
Based on that, I assumed that allowing write to blocks readers that may be depending on priority inheritance is potentially problematic for applications that likely have been designed with writer-starvation in mind. The first version of the patch did not care about the scheduling classes were but I admit there is a non-zero possibility that breaking reader bias for a writer may break some unknown RT-specific application that relied on writer starvation for DL / RT tasks.
Signature · 2 lines
Mel Gorman SUSE Labs
Quoted 23 lines · Mel Gorman
kernel/locking/rwbase_rt.c +15
-0@@ -65,6 +69,64 @@ static __always_inline int rwbase_read_trylock(struct rwbase_rt *rwb)return 0 ; } +/* +* Allow reader bias with a pending writer for a minimum of 4ms or 1 tick. +* This matches RWSEM_WAIT_TIMEOUT for the generic RWSEM implementation. +* The granularity is not exact as the lowest bit in rwbase_rt->waiter_timeout +* is used to detect recent DL / RT tasks taking a read lock. +*/ +#define RWBASE_RT_WAIT_TIMEOUT DIV_ROUND_UP(HZ, 250) + +static void __sched update_dlrt_reader(struct rwbase_rt *rwb) +{ +/* No update required if DL / RT tasks already identified. */ +if (rwb->waiter_timeout &1 ) +return ; + +/*
kernel/locking/rwbase_rt.c static __always_inline int rwbase_read_trylock(struct rwbase_rt *rwb) · line 96
Quoted 10 lines
kernel/locking/rwbase_rt.c +10
-0+* Record a DL / RT task acquiring the lock for read. This may result +* in indefinite writer starvation but DL / RT tasks should avoid such +* behaviour. +*/ +if (rt_task (current)) { +struct rt_mutex_base *rtm = &rwb->rtmutex; +unsigned long flags; + +raw_spin_lock_irqsave (&rtm->wait_lock, flags); + rwb->waiter_timeout |=1 ;
Let me see of I parsed the whole logic right:
_After_ the RT reader acquired the lock, the lowest bit is set. This may be immediately if the timeout did not occur yet.
With this flag set, all following reader incl. SCHED_OTHER will acquire the lock.
If so, then I don't know why this is a good idea.
If _only_ the RT reader is allowed to acquire the lock while the writer is waiting then it make sense to prefer the RT tasks. (So the check is on current and not on the lowest bit).
All other (SCHED_OTHER) reader would have to block on the rtmutex after the timeout. This makes sense to avoid the starvation.
If we drop that "we prefer the RT reader" then it would block on the RTmutex. It will _still_ be preferred over the writer because it will be enqueued before the writer in the queue due to its RT priority. The only downside is that it has to wait until all readers are left. So by allowing the RT reader to always acquire the lock as long as the WRITER_BIAS isn't set, we would allow to enter early while the other reader are still in and after the timeout you would only have RT reader going in and out. All SCHED_OTHER reader block on the RTmutex.
I think I like this.
kernel/locking/rwbase_rt.c static __always_inline int rwbase_read_trylock(struct rwbase_rt *rwb) · line 100
Quoted 4 lines
kernel/locking/rwbase_rt.c +4
-0+raw_spin_unlock_irqrestore (&rtm->wait_lock, flags); + } +} +
Sebastian
Quoted 38 lines · Sebastian Andrzej Siewior
Quoted 23 lines · Mel Gorman
kernel/locking/rwbase_rt.c +15
-0@@ -65,6 +69,64 @@ static __always_inline int rwbase_read_trylock(struct rwbase_rt *rwb)return 0 ; } +/* +* Allow reader bias with a pending writer for a minimum of 4ms or 1 tick. +* This matches RWSEM_WAIT_TIMEOUT for the generic RWSEM implementation. +* The granularity is not exact as the lowest bit in rwbase_rt->waiter_timeout +* is used to detect recent DL / RT tasks taking a read lock. +*/ +#define RWBASE_RT_WAIT_TIMEOUT DIV_ROUND_UP(HZ, 250) + +static void __sched update_dlrt_reader(struct rwbase_rt *rwb) +{ +/* No update required if DL / RT tasks already identified. */ +if (rwb->waiter_timeout &1 ) +return ; + +/* kernel/locking/rwbase_rt.c static __always_inline int rwbase_read_trylock(struct rwbase_rt *rwb) · line 96
Quoted 10 lines
kernel/locking/rwbase_rt.c +10
-0+* Record a DL / RT task acquiring the lock for read. This may result +* in indefinite writer starvation but DL / RT tasks should avoid such +* behaviour. +*/ +if (rt_task (current)) { +struct rt_mutex_base *rtm = &rwb->rtmutex; +unsigned long flags; + +raw_spin_lock_irqsave (&rtm->wait_lock, flags); + rwb->waiter_timeout |=1 ;Let me see of I parsed the whole logic right:
Quoted 5 lines
_After_ the RT reader acquired the lock, the lowest bit is set. This may be immediately if the timeout did not occur yet.
With this flag set, all following reader incl.SCHED_OTHERwill acquire the lock.
Correct. The intent was to track if there were any DL / RT tasks since the last write unlock in case there was a mix of SCHED_OTHER and rt_tasks contending on the same lock with unknown arrival times.
Quoted 8 lines
If so, then I don't know why this is a good idea.
If _only_ the RT reader is allowed to acquire the lock while the writer is waiting then it make sense to prefer the RT tasks. (So the check is on current and not on the lowest bit).
All other (SCHED_OTHER) reader would have to block on the rtmutex after the timeout. This makes sense to avoid the starvation.
Ok, fair enough.
Quoted 4 lines
If we drop that "we prefer the RT reader" then it would block on the RTmutex. It will _still_ be preferred over the writer because it will be enqueued before the writer in the queue due to its RT priority. The only downside is that it has to wait until all readers are left.
The writer has to wait until all the readers have left anyway.
Quoted 7 lines
So by allowing the RT reader to always acquire the lock as long as the
WRITER_BIASisn't set, we would allow to enter early while the other reader are still in and after the timeout you would only have RT reader going in and out. AllSCHED_OTHERreader block on the RTmutex.I think I like this.
If I understand you correctly, the patch becomes this;
--8<--
locking/rwbase: Prevent indefinite writer starvation
rw_semaphore and rwlock are explicitly unfair to writers in the presense of readers by design with a PREEMPT_RT configuration. Commit 943f0edb754f ("locking/rt: Add base code for RT rw_semaphore and rwlock") notes;
The implementation is writer unfair, as it is not feasible to do priority inheritance on multiple readers, but experience has shown that real-time workloads are not the typical workloads which are sensitive to writer starvation.
While atypical, it's also trivial to block writers with PREEMPT_RT indefinitely without ever making forward progress. Since LTP-20220121, the dio_truncate test case went from having 1 reader to having 16 readers and the number of readers is sufficient to prevent the down_write ever succeeding while readers exist. Eventually the test is killed after 30 minutes as a failure.
dio_truncate is not a realtime application but indefinite writer starvation is undesirable. The test case has one writer appending and truncating files A and B while multiple readers read file A. The readers and writer are contending for one file's inode lock which never succeeds as the readers keep reading until the writer is done which never happens.
This patch records a timestamp when the first writer is blocked. DT / RT tasks can continue to take the lock for read as long as readers exist indefinitely. Other readers can acquire the read lock unless a writer has been blocked for a minimum of 4ms. This is sufficient to allow the dio_truncate test case to complete within the 30 minutes timeout.
--- include/linux/rwbase_rt.h | 3 +++ kernel/locking/rwbase_rt.c | 45 ++++++++++++++++++++++++++++++++++++++++++--- 2 files changed, 45 insertions(+), 3 deletions(-)
include/linux/rwbase_rt.h +3 -0
@@ -10,12 +10,14 @@struct rwbase_rt {atomic_t readers; +unsigned long waiter_timeout;struct rt_mutex_base rtmutex; };#define __RWBASE_INITIALIZER (name) \ { \ .readers = ATOMIC_INIT(READER_BIAS), \ + .waiter_timeout = 0, \ .rtmutex = __RT_MUTEX_BASE_INITIALIZER(name.rtmutex), \ }
@@ -23,6 +25,7 @@ struct rwbase_rt {do { \rt_mutex_base_init (&(rwbase)->rtmutex); \atomic_set (&(rwbase)->readers,READER_BIAS ); \ + (rwbase)->waiter_timeout =0 ; \ }while (0 )
kernel/locking/rwbase_rt.c +42 -3
76 lines not on this page · raw message
On Wed, 18 Jan 2023 17:31:30 +0000 Mel Gorman <[email protected]>
Quoted 179 lines · Sebastian Andrzej Siewior
Quoted 38 lines · Mel Gorman
Quoted 24 lines
kernel/locking/rwbase_rt.c +15
-0@@ -65,6 +69,64 @@ static __always_inline int rwbase_read_trylock(struct rwbase_rt *rwb)return 0 ; } +/* +* Allow reader bias with a pending writer for a minimum of 4ms or 1 tick. +* This matches RWSEM_WAIT_TIMEOUT for the generic RWSEM implementation. +* The granularity is not exact as the lowest bit in rwbase_rt->waiter_timeout +* is used to detect recent DL / RT tasks taking a read lock. +*/ +#define RWBASE_RT_WAIT_TIMEOUT DIV_ROUND_UP(HZ, 250) + +static void __sched update_dlrt_reader(struct rwbase_rt *rwb) +{ +/* No update required if DL / RT tasks already identified. */ +if (rwb->waiter_timeout &1 ) +return ; + +/* kernel/locking/rwbase_rt.c static __always_inline int rwbase_read_trylock(struct rwbase_rt *rwb) · line 96
Quoted 10 lines
kernel/locking/rwbase_rt.c +10
-0+* Record a DL / RT task acquiring the lock for read. This may result +* in indefinite writer starvation but DL / RT tasks should avoid such +* behaviour. +*/ +if (rt_task (current)) { +struct rt_mutex_base *rtm = &rwb->rtmutex; +unsigned long flags; + +raw_spin_lock_irqsave (&rtm->wait_lock, flags); + rwb->waiter_timeout |=1 ;Let me see of I parsed the whole logic right:
Quoted 5 lines
_After_ the RT reader acquired the lock, the lowest bit is set. This may be immediately if the timeout did not occur yet.
With this flag set, all following reader incl.SCHED_OTHERwill acquire the lock.Correct. The intent was to track if there were any DL / RT tasks since the last write unlock in case there was a mix of
SCHED_OTHERandrt_taskscontending on the same lock with unknown arrival times.Quoted 8 lines
If so, then I don't know why this is a good idea.
If _only_ the RT reader is allowed to acquire the lock while the writer is waiting then it make sense to prefer the RT tasks. (So the check is on current and not on the lowest bit).
All other (SCHED_OTHER) reader would have to block on the rtmutex after the timeout. This makes sense to avoid the starvation.Ok, fair enough.
Quoted 4 lines
If we drop that "we prefer the RT reader" then it would block on the RTmutex. It will _still_ be preferred over the writer because it will be enqueued before the writer in the queue due to its RT priority. The only downside is that it has to wait until all readers are left.
The writer has to wait until all the readers have left anyway.
Quoted 7 lines
So by allowing the RT reader to always acquire the lock as long as the
WRITER_BIASisn't set, we would allow to enter early while the other reader are still in and after the timeout you would only have RT reader going in and out. AllSCHED_OTHERreader block on the RTmutex.I think I like this.
If I understand you correctly, the patch becomes this;
--8<--
locking/rwbase: Prevent indefinite writer starvation
rw_semaphoreand rwlock are explicitly unfair to writers in the presense of readers by design with aPREEMPT_RTconfiguration. Commit943f0edb754f("locking/rt: Add base code for RTrw_semaphoreand rwlock") notes;The implementation is writer unfair, as it is not feasible to do priority inheritance on multiple readers, but experience has shown that real-time workloads are not the typical workloads which are sensitive to writer starvation.
While atypical, it's also trivial to block writers with
PREEMPT_RTindefinitely without ever making forward progress. Since LTP-20220121, thedio_truncatetest case went from having 1 reader to having 16 readers and the number of readers is sufficient to prevent thedown_writeever succeeding while readers exist. Eventually the test is killed after 30 minutes as a failure.
dio_truncateis not a realtime application but indefinite writer starvation is undesirable. The test case has one writer appending and truncating files A and B while multiple readers read file A. The readers and writer are contending for one file's inode lock which never succeeds as the readers keep reading until the writer is done which never happens.This patch records a timestamp when the first writer is blocked. DT / RT tasks can continue to take the lock for read as long as readers exist indefinitely. Other readers can acquire the read lock unless a writer has been blocked for a minimum of 4ms. This is sufficient to allow the
dio_truncatetest case to complete within the 30 minutes timeout.Signed-off-by Mel Gorman <[email protected]>--- include/linux/rwbase_rt.h | 3 +++ kernel/locking/rwbase_rt.c | 45 ++++++++++++++++++++++++++++++++++++++++++--- 2 files changed, 45 insertions(+), 3 deletions(-)include/linux/rwbase_rt.h +3
-0@@ -10,12 +10,14 @@struct rwbase_rt {atomic_t readers; +unsigned long waiter_timeout;struct rt_mutex_base rtmutex; };#define __RWBASE_INITIALIZER (name) \ { \ .readers = ATOMIC_INIT(READER_BIAS), \ + .waiter_timeout = 0, \ .rtmutex = __RT_MUTEX_BASE_INITIALIZER(name.rtmutex), \ }@@ -23,6 +25,7 @@ struct rwbase_rt {do { \rt_mutex_base_init (&(rwbase)->rtmutex); \atomic_set (&(rwbase)->readers,READER_BIAS ); \ + (rwbase)->waiter_timeout =0 ; \ }while (0 )kernel/locking/rwbase_rt.c +22
-1@@ -39,7 +39,10 @@* major surgery for a very dubious value. * * The risk of writer starvation is there, but the pathological use cases -* which trigger it are not necessarily the typical RT workloads. +* which trigger it are not necessarily the typical RT workloads. SCHED_OTHER +* reader acquisitions will be forced into the slow path if a writer is +* blocked for more than RWBASE_RT_WAIT_TIMEOUT jiffies. New DL / RT readers +* can still starve a writer indefinitely. * * Fast-path orderings: * The lock/unlock of readers can run in fast paths: lock and unlock are only @@ -65,6 +68,35 @@ static __always_inline int rwbase_read_trylock(struct rwbase_rt *rwb)return 0 ; } +/* +* Allow reader bias for SCHED_OTHER tasks with a pending writer for a +* minimum of 4ms or 1 tick. This matches RWSEM_WAIT_TIMEOUT for the +* generic RWSEM implementation. +*/ +#define RWBASE_RT_WAIT_TIMEOUT DIV_ROUND_UP(HZ, 250) + +/* rtmutex->wait_lock must be held. */ +static void __sched set_writer_blocked(struct rwbase_rt *rwb) +{ +/* Record the timeout based on the the first writer to block. */ +if (!rwb->waiter_timeout) + rwb->waiter_timeout = jiffies +RWBASE_RT_WAIT_TIMEOUT ; +} + +static bool __sched rwbase_allow_reader_bias(struct rwbase_rt *rwb) +{ +/*
kernel/locking/rwbase_rt.c static __always_inline int rwbase_read_trylock(struct rwbase_rt *rwb) · line 98
Quoted 10 lines
kernel/locking/rwbase_rt.c +10
-0+* Allow reader bias for DL / RT tasks. Such tasks should be +* designed to avoid heavy writer contention or indefinite +* starvation. +*/ +if (rt_task (current)) +return true; + +/* Allow reader bias unless a writer timeout is reached. */ +return time_before (jiffies, rwb->waiter_timeout); +}
Good to see the change in your mind since last post.
But starvation remains same given RT contenders, even if prevent is put on your subject line.
What sense could the 4ms deadline make at best if RT contenders extend it to a week?
What will happen if RT contenders are hurt by the starvation deadline?
Quoted 6 lines · Hillf Danton
But starvation remains same given RT contenders, even if prevent is put on your subject line.
What sense could the 4ms deadline make at best if RT contenders extend it to a week?
What will happen if RT contenders are hurt by the starvation deadline?
As far as Mel's efforts go, I am satisfied so far. Maybe you can improve it further afterwards.
Sebastian
On Thu, 19 Jan 2023 09:32:22 +0100 Sebastian Andrzej Siewior <[email protected]>
Quoted 2 lines
As far as Mel's efforts go, I am satisfied so far.
If not because you can, could you specify why 4ms fails to cure starvation?
Quoted 5 lines · Hillf Danton
On Thu, 19 Jan 2023 09:32:22 +0100 Sebastian Andrzej Siewior <[email protected]>
Quoted 2 lines
As far as Mel's efforts go, I am satisfied so far.
If not because you can, could you specify why 4ms fails to cure starvation?
It does not fail to cure the starvation. I haven't tested it myself but base on Mel's description and the patch it very much looks like it cures the writer starvation.
If you don't like the 4ms, it could be 1ms or 40ms - it does not really matter. The 4ms is aligned on the generic implementation which uses the same value. Unless there is strong evidence to use something else I don't see the need to diverse.
Sebastian
On Thu, 19 Jan 2023 17:36:22 +0100 Sebastian Andrzej Siewior
Quoted 7 lines · Hillf Danton
Quoted 5 lines
On Thu, 19 Jan 2023 09:32:22 +0100 Sebastian Andrzej Siewior <[email protected]>
Quoted 2 lines
As far as Mel's efforts go, I am satisfied so far.
If not because you can, could you specify why 4ms fails to cure starvation?
Quoted 8 lines
It does not fail to cure the starvation. I haven't tested it myself but base on Mel's description and the patch it very much looks like it cures the writer starvation.
If you don't like the 4ms, it could be 1ms or 40ms - it does not really matter. The 4ms is aligned on the generic implementation which uses the same value. Unless there is strong evidence to use something else I don't see the need to diverse.
I am fine with either 4ms or 40ms, or a second.
Given the cure, does it still work when reader bias for RT tasks is allowed? If not, why keep starving waiters after they pay the 40ms price?
Quoted 4 lines · Hillf Danton
I am fine with either 4ms or 40ms, or a second.
Given the cure, does it still work when reader bias for RT tasks is allowed?
No.
Quoted 1 line
If not, why keep starving waiters after they pay the 40ms price?
That kind of starvation will also happen if you have only spinlock_t locks and you say 3 RT tasks that acquire the lock back to back. And a few SCHED_OTHER tasks. Those 3 will be always be in front of the queue (as they skip the line) and the following SCHED_OTHER tasks will starve and never get the lock.
So it is basically the same scenario.
Sebastian
On Fri, 20 Jan 2023 19:34:02 +0100 Sebastian Andrzej Siewior <[email protected]>
Quoted 7 lines · Hillf Danton
Quoted 4 lines
I am fine with either 4ms or 40ms, or a second.
Given the cure, does it still work when reader bias for RT tasks is allowed?
No.
Quoted 7 lines
Quoted 1 line
If not, why keep starving waiters after they pay the 40ms price?
That kind of starvation will also happen if you have only
spinlock_tlocks and you say 3 RT tasks that acquire the lock back to back. And a fewSCHED_OTHERtasks. Those 3 will be always be in front of the queue (as they skip the line) and the followingSCHED_OTHERtasks will starve and never get the lock.
Given priority, what sense could be made by keeping RT task starved?
Quoted 6 lines · Mel Gorman
If we drop that "we prefer the RT reader" then it would block on the
Quoted 3 lines
RTmutex. It will _still_ be preferred over the writer because it will be enqueued before the writer in the queue due to its RT priority. The only downside is that it has to wait until all readers are left.
The writer has to wait until all the readers have left anyway.
I meant the READER in case it has RT priority. It will enqueue itself on the RTmutex, first in line, and wait until all other READER leave.
Quoted 1 line
If I understand you correctly, the patch becomes this;
exactly.
Quoted 1 line
--8<--
…
Quoted 1 line
This patch records a timestamp when the first writer is blocked. DT /
s/DT/DL
Quoted 7 lines
RT tasks can continue to take the lock for read as long as readers exist indefinitely. Other readers can acquire the read lock unless a writer has been blocked for a minimum of 4ms. This is sufficient to allow the
dio_truncatetest case to complete within the 30 minutes timeout.Signed-off-by Mel Gorman <[email protected]>---
…
Quoted 23 lines
kernel/locking/rwbase_rt.c +5
-2@@ -74,9 +106,11 @@ static int __sched __rwbase_read_lock(struct rwbase_rt *rwb,raw_spin_lock_irq (&rtm->wait_lock);/* * Allow readers, as long as the writer has not completely -* acquired the semaphore for write. +* acquired the semaphore for write and reader bias is still +* allowed. */ -if (atomic_read (&rwb->readers) !=WRITER_BIAS ) { +if (atomic_read (&rwb->readers) !=WRITER_BIAS && +rwbase_allow_reader_bias (rwb)) {atomic_inc (&rwb->readers);raw_spin_unlock_irq (&rtm->wait_lock);return 0 ;@@ -264,12 +298,17 @@ static int __sched rwbase_write_lock(struct rwbase_rt *rwb,if (__rwbase_write_trylock (rwb))break ; +/* Record first new read/write contention. */
kernel/locking/rwbase_rt.c static int __sched rwbase_write_lock(struct rwbase_rt *rwb, · line 311
Quoted 10 lines
kernel/locking/rwbase_rt.c +4
-0+set_writer_blocked (rwb); +raw_spin_unlock_irqrestore (&rtm->wait_lock, flags);rwbase_schedule ();raw_spin_lock_irqsave (&rtm->wait_lock, flags);set_current_state (state); } + + rwb->waiter_timeout =0 ;
Regarding memory ordering and ordering in general:
- Should the writer leave from rwbase_schedule() due to a signal then set_writer_blocked() sets a timeout but it is not cleared on the signal leave.
- There is only writer in that for loop within rwbase_write_lock() because only one writer can own the rtmutex at a time. (A second writer blocks on the RTmutex and needs to wait, I may have spread some confusion earler). Therefore it should be okay to unconditionally set the timeout (instead of checking for zero).
- Once the writer removes READER_BIAS, it forces the reader into the slowpath. At that time the writer does not own the wait_lock meaning the reader _could_ check the timeout before writer had a chance to set it. The worst thing is probably that if jiffies does not have the highest bit set then it will always disable the reader bias here. The easiest thing is probably to check timeout vs 0 and ensure on the writer side that the lowest bit is always set (in the unlikely case it will end up as zero).
kernel/locking/rwbase_rt.c static int __sched rwbase_write_lock(struct rwbase_rt *rwb, · line 313
Quoted 2 lines
kernel/locking/rwbase_rt.c +0
-0rwbase_restore_current_state ();trace_contention_end (rwb,0 );
Sebastian
Quoted 11 lines · Sebastian Andrzej Siewior
Quoted 6 lines · Mel Gorman
If we drop that "we prefer the RT reader" then it would block on the
Quoted 3 lines
RTmutex. It will _still_ be preferred over the writer because it will be enqueued before the writer in the queue due to its RT priority. The only downside is that it has to wait until all readers are left.
The writer has to wait until all the readers have left anyway.
I meant the READER in case it has RT priority. It will enqueue itself on the RTmutex, first in line, and wait until all other READER leave.
Ah.
Quoted 10 lines
Quoted 1 line
If I understand you correctly, the patch becomes this;
exactly.
Quoted 1 line
--8<--
???
Quoted 1 line
This patch records a timestamp when the first writer is blocked. DT /
s/DT/DL
Fixed.
Quoted 37 lines
Quoted 7 lines
RT tasks can continue to take the lock for read as long as readers exist indefinitely. Other readers can acquire the read lock unless a writer has been blocked for a minimum of 4ms. This is sufficient to allow the
dio_truncatetest case to complete within the 30 minutes timeout.Signed-off-by Mel Gorman <[email protected]>---
???
Quoted 29 lines
kernel/locking/rwbase_rt.c +7
-2@@ -74,9 +106,11 @@ static int __sched __rwbase_read_lock(struct rwbase_rt *rwb,raw_spin_lock_irq (&rtm->wait_lock);/* * Allow readers, as long as the writer has not completely -* acquired the semaphore for write. +* acquired the semaphore for write and reader bias is still +* allowed. */ -if (atomic_read (&rwb->readers) !=WRITER_BIAS ) { +if (atomic_read (&rwb->readers) !=WRITER_BIAS && +rwbase_allow_reader_bias (rwb)) {atomic_inc (&rwb->readers);raw_spin_unlock_irq (&rtm->wait_lock);return 0 ;@@ -264,12 +298,17 @@ static int __sched rwbase_write_lock(struct rwbase_rt *rwb,if (__rwbase_write_trylock (rwb))break ; +/* Record first new read/write contention. */ +set_writer_blocked (rwb); +raw_spin_unlock_irqrestore (&rtm->wait_lock, flags);rwbase_schedule ();raw_spin_lock_irqsave (&rtm->wait_lock, flags);
Quoted 10 lines
kernel/locking/rwbase_rt.c static int __sched rwbase_write_lock(struct rwbase_rt *rwb, · line 311
Quoted 4 lines
kernel/locking/rwbase_rt.c +2
-0set_current_state (state); } + + rwb->waiter_timeout =0 ;Regarding memory ordering and ordering in general:
- Should the writer leave fromrwbase_schedule()due to a signal thenset_writer_blocked()sets a timeout but it is not cleared on the signal leave.
You're correct, it should be reset in the signal check block before the wait_lock is released by __rwbase_write_unlock. I considered different ways to avoid multiple reset points but it was untidy.
Quoted 6 lines
- There is only writer in that for loop within
rwbase_write_lock()because only one writer can own the rtmutex at a time. (A second writer blocks on the RTmutex and needs to wait, I may have spread some confusion earler). Therefore it should be okay to unconditionally set the timeout (instead of checking for zero).
Ah ok, I see now or at least I think I do.
Quoted 2 lines
- Once the writer removes
READER_BIAS, it forces the reader into the slowpath.
Removed in __rwbase_write_trylock IIUC
Quoted 8 lines
At that time the writer does not own the
wait_lockmeaning the reader _could_ check the timeout before writer had a chance to set it. The worst thing is probably that if jiffies does not have the highest bit set then it will always disable the reader bias here. The easiest thing is probably to check timeout vs 0 and ensure on the writer side that the lowest bit is always set (in the unlikely case it will end up as zero).
I am missing something important. On the read side, we have
raw_spin_lock_irq(&rtm->wait_lock);
/*
* Allow readers, as long as the writer has not completely
* acquired the semaphore for write and reader bias is still
* allowed.
*/
if (atomic_read(&rwb->readers) != WRITER_BIAS &&
rwbase_allow_reader_bias(rwb)) {
atomic_inc(&rwb->readers);
raw_spin_unlock_irq(&rtm->wait_lock);
return 0;
}So rtm->wait_lock is held and both the WRITER_BASE and timeout are checked under the lock. On the write side it's also held when the timeout is updated here
raw_spin_lock_irqsave(&rtm->wait_lock, flags);
...
for (;;) {
...
/* Record timeout when reader bias is ignored. */
rwb->waiter_timeout = jiffies + RWBASE_RT_WAIT_TIMEOUT;
raw_spin_unlock_irqrestore(&rtm->wait_lock, flags);
rwbase_schedule();
raw_spin_lock_irqsave(&rtm->wait_lock, flags);
set_current_state(state);
}
rwb->waiter_timeout = 0;
...out_unlock:
raw_spin_unlock_irqrestore(&rtm->wait_lock, flags);
(it's also now held in the signal block when it is cleared)
I'm not seeing exactly what the problem is unless it's an issue in the fast path but I think the atomic_try_cmpxchg_acquire works there.
In the absense of wait_lock, I guess there would be a potential race between the atomic_read(&rwb->readers) != WRITER_BIAS and rwbase_allow_reader_bias(rwb) but that shouldn't be the case now. Even if it wasn't locked, it might allow a new reader through but it'd be a transient problem and writer starvation should be prevented once the timeout is observed.
Signature · 2 lines
Mel Gorman SUSE Labs
Quoted 4 lines · Mel Gorman
Quoted 2 lines
- Once the writer removes
READER_BIAS, it forces the reader into the slowpath.Removed in
__rwbase_write_trylockIIUC
And added back in case try trylock failed via __rwbase_write_unlock(). The RTmutex is unlocked and the READER_BIAS is "returned".
Quoted 11 lines
Quoted 8 lines
At that time the writer does not own the
wait_lockmeaning the reader _could_ check the timeout before writer had a chance to set it. The worst thing is probably that if jiffies does not have the highest bit set then it will always disable the reader bias here. The easiest thing is probably to check timeout vs 0 and ensure on the writer side that the lowest bit is always set (in the unlikely case it will end up as zero).I am missing something important. On the read side, we have
Look at this side by side:
writer reader
| static int __sched rwbase_write_lock(struct rwbase_rt *rwb,
| unsigned int state)
| {
| /* Force readers into slow path */
| atomic_sub(READER_BIAS, &rwb->readers);| static int __sched __rwbase_read_lock(struct rwbase_rt *rwb,
| unsigned int state)
| {
| struct rt_mutex_base *rtm = &rwb->rtmutex;
| int ret;
|
| raw_spin_lock_irq(&rtm->wait_lock);Reader has the lock, writer will wait.
| /*
| * Allow readers, as long as the writer has not completely
| * acquired the semaphore for write.
| */
| if (atomic_read(&rwb->readers) != WRITER_BIAS) {here, the timeout value is not yet populated by the writer so the reader compares vs 0.
| atomic_inc(&rwb->readers); | raw_spin_unlock_irq(&rtm->wait_lock); | return 0; | } |
| raw_spin_lock_irqsave(&rtm->wait_lock, flags); | if (__rwbase_write_trylock(rwb)) | goto out_unlock; |
Hope this makes it easier.
Sebastian
Quoted 9 lines · Sebastian Andrzej Siewior
Quoted 4 lines · Mel Gorman
Quoted 2 lines
- Once the writer removes
READER_BIAS, it forces the reader into the slowpath.Removed in
__rwbase_write_trylockIIUCAnd added back in case try trylock failed via
__rwbase_write_unlock(). The RTmutex is unlocked and theREADER_BIASis "returned".
Indeed.
Quoted 48 lines
Quoted 11 lines
Quoted 8 lines
At that time the writer does not own the
wait_lockmeaning the reader _could_ check the timeout before writer had a chance to set it. The worst thing is probably that if jiffies does not have the highest bit set then it will always disable the reader bias here. The easiest thing is probably to check timeout vs 0 and ensure on the writer side that the lowest bit is always set (in the unlikely case it will end up as zero).I am missing something important. On the read side, we have
Look at this side by side:
writer reader
| static int __sched rwbase_write_lock(struct rwbase_rt *rwb, | unsigned int state) | { | /* Force readers into slow path */ | atomic_sub(READER_BIAS, &rwb->readers);| static int __sched __rwbase_read_lock(struct rwbase_rt *rwb, | unsigned int state) | { | struct rt_mutex_base *rtm = &rwb->rtmutex; | int ret; | | raw_spin_lock_irq(&rtm->wait_lock);Reader has the lock, writer will wait.
| /* | * Allow readers, as long as the writer has not completely | * acquired the semaphore for write. | */ | if (atomic_read(&rwb->readers) != WRITER_BIAS) {here, the timeout value is not yet populated by the writer so the reader compares vs 0.
| atomic_inc(&rwb->readers); | raw_spin_unlock_irq(&rtm->wait_lock); | return 0; | } |
Quoted 7 lines
| raw_spin_lock_irqsave(&rtm->wait_lock, flags); | if (__rwbase_write_trylock(rwb)) | goto out_unlock; |Hope this makes it easier.
Yes, it makes your concern much clearer but I'm not sure it actually matters in terms of preventing write starvation or in terms of correctness. At worst, a writer is blocked that could have acquired the lock during a tiny race but that's a timing issue rather than a correctness issue.
Lets say the race hits
reader sees waiter_timeout == 0 writer acquires wait_lock __rwbase_write_trylock fails update waiter_timeout rwbase_schedule
Each reader that hits the race goes ahead at a point in time but anything readers after that observe the timeout and eventually the writer goes ahead.
If the waiter_timeout was updated before atomic_sub(READER_BIAS), it doesn't close the race as atomic_sub is unordered so barriers would also be needed and clearing of waiter_timeout moves to out_unlock in case __rwbase_write_trylock succeeds. That's possible but the need for barriers makes it more complicated than is necessary.
The race could be closed by moving wait_lock acquisition before the atomic_sub in rwbase_write_lock() but it expands the scope of the wait_lock and I'm not sure that's necessary for either correctness or preventing writer starvation. It's a more straight-forward fix but expanding the scope of a lock unnecessarily has been unpopular in the past.
I think we can close the race that concerns you but I'm not convinced we need to and changing the scope of wait_lock would need a big comment and probably deserves a separate patch.
Sorry if I'm still missing something stupid and thanks for your patience reviewing this.
Signature · 2 lines
Mel Gorman SUSE Labs
Quoted 5 lines · Mel Gorman
The race could be closed by moving
wait_lockacquisition before theatomic_subinrwbase_write_lock()but it expands the scope of thewait_lockand I'm not sure that's necessary for either correctness or preventing writer starvation. It's a more straight-forward fix but expanding the scope of a lock unnecessarily has been unpopular in the past.
Curiously, this is the documented behavior:
* down_write/write_lock()
* 1) Lock rtmutex
* 2) Remove the reader BIAS to force readers into the slow path
Quoted 8 lines · Davidlohr Bueso
Quoted 5 lines · Mel Gorman
The race could be closed by moving
wait_lockacquisition before theatomic_subinrwbase_write_lock()but it expands the scope of thewait_lockand I'm not sure that's necessary for either correctness or preventing writer starvation. It's a more straight-forward fix but expanding the scope of a lock unnecessarily has been unpopular in the past.
Quoted 5 lines
Curiously, this is the documented behavior:
* down_write/write_lock()
* 1) Lock rtmutex
* 2) Remove the reader BIAS to force readers into the slow path
Nevermind, this was the rtmutex, not the wait_lock, sorry for the noise.
Quoted 5 lines · Mel Gorman
Yes, it makes your concern much clearer but I'm not sure it actually matters in terms of preventing write starvation or in terms of correctness. At worst, a writer is blocked that could have acquired the lock during a tiny race but that's a timing issue rather than a correctness issue.
Correct. My concern is that one reader may need to wait 4ms+ for the lock while a following reader (that one that sees the timeout) does not. This can lead to confusion later on.
Quoted 8 lines
Lets say the race hits
reader sees waiter_timeout == 0 writer acquires wait_lock __rwbase_write_trylock fails update waiter_timeout rwbase_schedule
Quoted 8 lines
Each reader that hits the race goes ahead at a point in time but anything readers after that observe the timeout and eventually the writer goes ahead.
If the
waiter_timeoutwas updated beforeatomic_sub(READER_BIAS), it doesn't close the race asatomic_subis unordered so barriers would also be needed and clearing ofwaiter_timeoutmoves toout_unlockin case__rwbase_write_trylocksucceeds. That's possible but the need for barriers makes it more complicated than is necessary.
yes...
Quoted 9 lines
The race could be closed by moving
wait_lockacquisition before theatomic_subinrwbase_write_lock()but it expands the scope of thewait_lockand I'm not sure that's necessary for either correctness or preventing writer starvation. It's a more straight-forward fix but expanding the scope of a lock unnecessarily has been unpopular in the past.I think we can close the race that concerns you but I'm not convinced we need to and changing the scope of
wait_lockwould need a big comment and probably deserves a separate patch.
would it work to check the timeout vs 0 before and only apply the timeout check if it is != zero? The writer would need to unconditionally or the lowest bit. That should close gaps at a low price. The timeout variable is always read within the lock so there shouldn't be need for any additional barriers.
Quoted 2 lines
Sorry if I'm still missing something stupid and thanks for your patience reviewing this.
thank that it is patience and not pain in the ass ;)
Sebastian
Quoted 11 lines · Sebastian Andrzej Siewior
Quoted 5 lines · Mel Gorman
Yes, it makes your concern much clearer but I'm not sure it actually matters in terms of preventing write starvation or in terms of correctness. At worst, a writer is blocked that could have acquired the lock during a tiny race but that's a timing issue rather than a correctness issue.
Correct. My concern is that one reader may need to wait 4ms+ for the lock while a following reader (that one that sees the timeout) does not. This can lead to confusion later on.
Ok, yes, that is a valid concern I had not considered when thinking in terms of correctness or writer starvation. It would be very tricky to diagnose if it happened.
Quoted 10 lines
Quoted 9 lines
The race could be closed by moving
wait_lockacquisition before theatomic_subinrwbase_write_lock()but it expands the scope of thewait_lockand I'm not sure that's necessary for either correctness or preventing writer starvation. It's a more straight-forward fix but expanding the scope of a lock unnecessarily has been unpopular in the past.I think we can close the race that concerns you but I'm not convinced we need to and changing the scope of
wait_lockwould need a big comment and probably deserves a separate patch.
Quoted 6 lines
would it work to check the timeout vs 0 before and only apply the timeout check if it is != zero? The writer would need to unconditionally or the lowest bit. That should close gaps at a low price. The timeout variable is always read within the lock so there shouldn't be need for any additional barriers.
Yes, as a bonus point, it can be checked early in rwbase_allow_reader_bias and is an cheap test for the common case so it's win-win all round.
Patch is now this;
--8<--
locking/rwbase: Prevent indefinite writer starvation
rw_semaphore and rwlock are explicitly unfair to writers in the presense of readers by design with a PREEMPT_RT configuration. Commit 943f0edb754f ("locking/rt: Add base code for RT rw_semaphore and rwlock") notes;
The implementation is writer unfair, as it is not feasible to do priority inheritance on multiple readers, but experience has shown that real-time workloads are not the typical workloads which are sensitive to writer starvation.
While atypical, it's also trivial to block writers with PREEMPT_RT indefinitely without ever making forward progress. Since LTP-20220121, the dio_truncate test case went from having 1 reader to having 16 readers and the number of readers is sufficient to prevent the down_write ever succeeding while readers exist. Eventually the test is killed after 30 minutes as a failure.
dio_truncate is not a realtime application but indefinite writer starvation is undesirable. The test case has one writer appending and truncating files A and B while multiple readers read file A. The readers and writer are contending for one file's inode lock which never succeeds as the readers keep reading until the writer is done which never happens.
This patch records a timestamp when the first writer is blocked. DL / RT tasks can continue to take the lock for read as long as readers exist indefinitely. Other readers can acquire the read lock unless a writer has been blocked for a minimum of 4ms. This is sufficient to allow the dio_truncate test case to complete within the 30 minutes timeout.
--- include/linux/rwbase_rt.h | 3 +++ kernel/locking/rwbase_rt.c | 38 +++++++++++++++++++++++++++++++++++--- 2 files changed, 38 insertions(+), 3 deletions(-)
include/linux/rwbase_rt.h +3 -0
@@ -10,12 +10,14 @@struct rwbase_rt {atomic_t readers; +unsigned long waiter_timeout;struct rt_mutex_base rtmutex; };#define __RWBASE_INITIALIZER (name) \ { \ .readers = ATOMIC_INIT(READER_BIAS), \ + .waiter_timeout = 0, \ .rtmutex = __RT_MUTEX_BASE_INITIALIZER(name.rtmutex), \ }
@@ -23,6 +25,7 @@ struct rwbase_rt {do { \rt_mutex_base_init (&(rwbase)->rtmutex); \atomic_set (&(rwbase)->readers,READER_BIAS ); \ + (rwbase)->waiter_timeout =0 ; \ }while (0 )
kernel/locking/rwbase_rt.c +35 -3
@@ -39,7 +39,10 @@* major surgery for a very dubious value. * * The risk of writer starvation is there, but the pathological use cases -* which trigger it are not necessarily the typical RT workloads. +* which trigger it are not necessarily the typical RT workloads. SCHED_OTHER +* reader acquisitions will be forced into the slow path if a writer is +* blocked for more than RWBASE_RT_WAIT_TIMEOUT jiffies. New DL / RT readers +* can still starve a writer indefinitely. * * Fast-path orderings: * The lock/unlock of readers can run in fast paths: lock and unlock are only
@@ -65,6 +68,27 @@ static __always_inline int rwbase_read_trylock(struct rwbase_rt *rwb)return 0 ; } +/* +* Allow reader bias for SCHED_OTHER tasks with a pending writer for a +* minimum of 4ms or 1 tick. This matches RWSEM_WAIT_TIMEOUT for the +* generic RWSEM implementation. +*/ +#define RWBASE_RT_WAIT_TIMEOUT DIV_ROUND_UP(HZ, 250) + +static bool __sched rwbase_allow_reader_bias(struct rwbase_rt *rwb) +{ +/* +* Allow reader bias if no writer is blocked or for DL / RT tasks. +* Such tasks should be designed to avoid heavy writer contention +* or indefinite starvation. +*/ +if (!rwb->waiter_timeout ||rt_task (current)) +return true; + +/* Allow reader bias unless a writer timeout has expired. */ +return time_before (jiffies, rwb->waiter_timeout); +} + static int __sched __rwbase_read_lock(struct rwbase_rt *rwb,unsigned int state) {
@@ -74,9 +98,11 @@ static int __sched __rwbase_read_lock(struct rwbase_rt *rwb,raw_spin_lock_irq (&rtm->wait_lock);/* * Allow readers, as long as the writer has not completely -* acquired the semaphore for write. +* acquired the semaphore for write and reader bias is still +* allowed. */ -if (atomic_read (&rwb->readers) !=WRITER_BIAS ) { +if (atomic_read (&rwb->readers) !=WRITER_BIAS && +rwbase_allow_reader_bias (rwb)) {atomic_inc (&rwb->readers);raw_spin_unlock_irq (&rtm->wait_lock);return 0 ;
@@ -255,6 +281,7 @@ static int __sched rwbase_write_lock(struct rwbase_rt *rwb,for (;;) {/* Optimized out for rwlocks */ if (rwbase_signal_pending_state (state, current)) { + rwb->waiter_timeout =0 ;rwbase_restore_current_state ();__rwbase_write_unlock (rwb,0 , flags);trace_contention_end (rwb, -EINTR );
@@ -264,12 +291,17 @@ static int __sched rwbase_write_lock(struct rwbase_rt *rwb,if (__rwbase_write_trylock (rwb))break ; +/* Record timeout when reader bias is ignored. */ + rwb->waiter_timeout = jiffies +RWBASE_RT_WAIT_TIMEOUT ; +raw_spin_unlock_irqrestore (&rtm->wait_lock, flags);rwbase_schedule ();raw_spin_lock_irqsave (&rtm->wait_lock, flags);set_current_state (state); } + + rwb->waiter_timeout =0 ;rwbase_restore_current_state ();trace_contention_end (rwb,0 );
Sebastian Andrzej Siewior
Reviewed-bykernel/locking/rwbase_rt.c static int __sched rwbase_write_lock(struct rwbase_rt *rwb, · line 295
Quoted 8 lines · Mel Gorman
kernel/locking/rwbase_rt.c +2
-0@@ -264,12 +291,17 @@ static int __sched rwbase_write_lock(struct rwbase_rt *rwb,if (__rwbase_write_trylock (rwb))break ; +/* Record timeout when reader bias is ignored. */ + rwb->waiter_timeout = jiffies +RWBASE_RT_WAIT_TIMEOUT ;
rwb->waiter_timeout = (jiffies + RWBASE_RT_WAIT_TIMEOUT) | 1;
There is the unlikely case that (jiffies + RWBASE_RT_WAIT_TIMEOUT) = 0 on 32bit where it is not jiffies64.
kernel/locking/rwbase_rt.c static int __sched rwbase_write_lock(struct rwbase_rt *rwb, · line 306
Quoted 11 lines
kernel/locking/rwbase_rt.c +3
-0+raw_spin_unlock_irqrestore (&rtm->wait_lock, flags);rwbase_schedule ();raw_spin_lock_irqsave (&rtm->wait_lock, flags);set_current_state (state); } + + rwb->waiter_timeout =0 ;rwbase_restore_current_state ();trace_contention_end (rwb,0 );
Sebastian
Quoted 7 lines · Sebastian Andrzej Siewior
Quoted 6 lines · Mel Gorman
kernel/locking/rwbase_rt.c +0
-0@@ -264,12 +291,17 @@ static int __sched rwbase_write_lock(struct rwbase_rt *rwb,if (__rwbase_write_trylock (rwb))break ;
Quoted 9 lines
kernel/locking/rwbase_rt.c static int __sched rwbase_write_lock(struct rwbase_rt *rwb, · line 295
Quoted 2 lines
kernel/locking/rwbase_rt.c +2
-0+/* Record timeout when reader bias is ignored. */ + rwb->waiter_timeout = jiffies +RWBASE_RT_WAIT_TIMEOUT ;rwb->waiter_timeout = (jiffies + RWBASE_RT_WAIT_TIMEOUT) | 1;There is the unlikely case that (jiffies +
RWBASE_RT_WAIT_TIMEOUT) = 0 on 32bit where it is not jiffies64.Reviewed-by Sebastian Andrzej Siewior <[email protected]>
Thanks very much, updated version will be posted shortly.
Signature · 2 lines
Mel Gorman SUSE Labs
Davidlohr Bueso
Reviewed-byQuoted 24 lines · Mel Gorman
locking/rwbase: Prevent indefinite writer starvation
rw_semaphoreand rwlock are explicitly unfair to writers in the presense of readers by design with aPREEMPT_RTconfiguration. Commit943f0edb754f("locking/rt: Add base code for RTrw_semaphoreand rwlock") notes;The implementation is writer unfair, as it is not feasible to do priority inheritance on multiple readers, but experience has shown that real-time workloads are not the typical workloads which are sensitive to writer starvation.
While atypical, it's also trivial to block writers with
PREEMPT_RTindefinitely without ever making forward progress. Since LTP-20220121, thedio_truncatetest case went from having 1 reader to having 16 readers and the number of readers is sufficient to prevent thedown_writeever succeeding while readers exist. Eventually the test is killed after 30 minutes as a failure.
dio_truncateis not a realtime application but indefinite writer starvation is undesirable. The test case has one writer appending and truncating files A and B while multiple readers read file A. The readers and writer are contending for one file's inode lock which never succeeds as the readers keep reading until the writer is done which never happens.
Quoted 7 lines
This patch records a timestamp when the first writer is blocked. DL / RT tasks can continue to take the lock for read as long as readers exist indefinitely. Other readers can acquire the read lock unless a writer has been blocked for a minimum of 4ms. This is sufficient to allow the
dio_truncatetest case to complete within the 30 minutes timeout.Signed-off-by Mel Gorman <[email protected]>
LGTM (albeit Sebastian's last comment).