Skip to contentSkip to conversation

locking/rwbase: Mitigate indefinite writer starvation

PATCH In review Mel Gorman 3 participants 5 messages Jan 20, 2023 – Feb 15, 2023 Locking primitives

lore
Share & tools
lore

Mel Gorman

author
#0 lore raw

PATCH v4 1/1 locking/rwbase: Mitigate 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.

[[email protected]: Fix overflow, close race against reader, match rwsem
timeouts, better rt_task handling, simplification]

---
 include/linux/rwbase_rt.h  |  3 +++
 kernel/locking/rwbase_rt.c | 41 ++++++++++++++++++++++++++++++++++++++---
 2 files changed, 41 insertions(+), 3 deletions(-)
include/linux/rwbase_rt.h +3 -0
index 1d264dd08625..b969b1d9bb85 100644
@@ -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 +38 -3

78 lines not on this page · raw message

Signature · 2 lines
Mel Gorman
SUSE Labs
author
#1 lore raw
Quoted 28 lines · Mel Gorman

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.

Quoted 4 lines

[[email protected]: Fix overflow, close race against reader, match rwsem
timeouts, better rt_task handling, simplification]

Yay/nay?

Signature · 2 lines
Mel Gorman
SUSE Labs
#2 lore raw
In reply to Mel Gorman

Mel!

Quoted 7 lines · Mel Gorman

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 /

git grep 'This patch' Documentation/process/

Quoted 4 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_truncate test case to complete within the 30 minutes timeout.

I'm not opposed to this, but what's the actual reason for this pulled out of thin air timeout?

What's the downside of actually forcing !RT readers into the slowpath once there is a writer waiting?

Thanks,

tglx

author
#3 lore raw
Quoted 1 line · Thomas Gleixner

Mel!

Hi :)

I'm not really online for the next several weeks so further responses may take ages. It's co-incidence that I'm online at the moment for an unrelated matter and glancing through mail.

Quoted 8 lines · Mel Gorman
Quoted 6 lines

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.

Quoted 4 lines
Quoted 1 line

This patch records a timestamp when the first writer is blocked. DL /

git grep 'This patch' Documentation/process/

I'm aware of the rule but tend to forget at times as enforcement varies between subsystems. First sentence of the paragraph becomes;

Record a timestamp when the first writer is blocked and force all new readers into the slow path upon expiration.

Quoted 8 lines
Quoted 4 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_truncate test case to complete within the 30 minutes timeout.

I'm not opposed to this, but what's the actual reason for this pulled out of thin air timeout?

No good reason, a value had to be picked. It happens to match the rwsem cutoff for optimistic spinning. That at least is some threshold for "a lock failed to be acquired within a reasonable time period". It's also arbitrary that it happened to be a value that allowed the dio_truncate LTP test to complete in a reasonable time.

Quoted 3 lines

What's the downside of actually forcing !RT readers into the slowpath once there is a writer waiting?

I actually don't know for sure because it's application dependant but at minimum, I believe it would be a deviation from how generic rwsems behave where a writer optimistically spins for the same duration before forcing the handoff. Whether that matters or not depends on the application, the ratio between readers/writers and the number of concurrent readers.

Signature · 2 lines
Mel Gorman
SUSE Labs
#4 lore raw
In reply to Thomas Gleixner
Quoted 2 lines · Thomas Gleixner

What's the downside of actually forcing !RT readers into the slowpath once there is a writer waiting?

We always said that there are no RT users of rwsem. Therefore it shouldn't matter because we still assume that nothing depends on this. After all we had one a one reader implementation of rwsem and this is the first report (to my knowledge) of a fallout since it was changed to multi-reader.

That said let me update Mel's patch and resend it without this bit.

Quoted 3 lines

Thanks,

tglx

Sebastian