[v5] locking/rwbase: Mitigate indefinite writer starvation

From: Mel Gorman <mgorman@techsingularity.net>

rw_semaphore and rwlock are explicitly unfair to writers in the presence
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.

Record a timestamp when the first writer is blocked and force all new
readers into the slow path upon expiration. Set the timeout to 4ms or
one tick which aligns with the generic implementation of rwsem.
This is sufficient to allow the dio_truncate test case to complete
within the 30 minutes timeout.

[bigeasy@linutronix.de: Fix overflow, close race against reader, match rwsem
			timeouts, simplification, don't prefer RT/DL reader
			as per tglx suggestion.]

Signed-off-by: Mel Gorman <mgorman@techsingularity.net>
Reviewed-by: Sebastian Andrzej Siewior <bigeasy@linutronix.de>
Signed-off-by: Sebastian Andrzej Siewior <bigeasy@linutronix.de>
---
- v4 https://lore.kernel.org/20230120140847.4pjqf3oinemokcyp@techsingularity.net
    - Reworded last paragraph of the commit message as Mel's suggestion
    - RT/DL tasks are no longer excluded from the waiter timeout. There
      is no reason why this should be done since no RT user relies on
      rwsem (and would need this kind of behaviour). The critical user
      from RT perspective replaced rwsem with RCU.
      Avoiding special treatment avoids this kind of bug with RT
      readers.
    - Update comments accordingly.

 include/linux/rwbase_rt.h  |  3 +++
 kernel/locking/rwbase_rt.c | 37 +++++++++++++++++++++++++++++++++----
 2 files changed, 36 insertions(+), 4 deletions(-)

On Wed, Feb 15 2023 at 18:30, Sebastian Andrzej Siewior wrote:
> diff --git a/include/linux/rwbase_rt.h b/include/linux/rwbase_rt.h
> index 1d264dd086250..b969b1d9bb85c 100644
> --- a/include/linux/rwbase_rt.h
> +++ b/include/linux/rwbase_rt.h
> @@ -10,12 +10,14 @@
>  
>  struct rwbase_rt {
>  	atomic_t		readers;
> +	unsigned long		waiter_timeout;

I'm still not convinced that this timeout has any value and if it has
then it should be clearly named writer_timeout because that's what it is
about.

The only reason for this timeout I saw so far is:

> +/*
> + * 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.

Clearly RT and !RT have completely different implementations and
behaviour vs. rwsems and rwlocks. Just because !RT has a timeout does
not make a good argument.

Just for the record: !RT has the timeout applicable in both directions
to prevent writer bias via lock stealing. That's not a problem for RT
because?

Can we finally get a proper justification for this?

> @@ -264,12 +285,20 @@ static int __sched rwbase_write_lock(struct rwbase_rt *rwb,
>  		if (__rwbase_write_trylock(rwb))
>  			break;
>  
> +		/*
> +		 * Record timeout when reader bias is ignored. Ensure timeout
> +		 * is at least 1 in case of overflow.
> +		 */
> +		rwb->waiter_timeout = (jiffies + RWBASE_RT_WAIT_TIMEOUT) | 1;
> +

So this has two sillies:

   1) It resets the timeout once per loop which is plain wrong

   2) The "| 1" is really a sloppy hack

Why not doing the obvious:

static bool __sched rwbase_allow_reader_bias(struct rwbase_rt *rwb)
{
	int r = atomic_read(&rwb->readers);

        if (likely(r < 0))
        	return true;

        if (r == WRITER_BIAS)
        	return false;

	/* Allow reader bias unless the writer timeout has expired. */
	return time_before(jiffies, rwb->writer_timeout);
}

and with that the "| 1" and all the rwb->timeout = 0 nonsense simply
goes away and rwbase_read_lock() becomes:

	if (rwbase_allow_reader_bias(rwb)) {
		// fastpath
		atomic_inc(&rwb->readers);
		raw_spin_unlock_irq(&rtm->wait_lock);
		return 0;
	}
        // slowpath

and the writelock slowpath has:

	rwb->writer_timeout = jiffies + RWBASE_RT_WAIT_TIMEOUT;

	for (;;) {
        	....

No?

Thanks,

        tglx

On 2023-02-21 00:55:33 [+0100], Thomas Gleixner wrote:
> On Wed, Feb 15 2023 at 18:30, Sebastian Andrzej Siewior wrote:
> > diff --git a/include/linux/rwbase_rt.h b/include/linux/rwbase_rt.h
> > index 1d264dd086250..b969b1d9bb85c 100644
> > --- a/include/linux/rwbase_rt.h
> > +++ b/include/linux/rwbase_rt.h
> > @@ -10,12 +10,14 @@
> >  
> >  struct rwbase_rt {
> >  	atomic_t		readers;
> > +	unsigned long		waiter_timeout;
> 
> I'm still not convinced that this timeout has any value and if it has
> then it should be clearly named writer_timeout because that's what it is
> about.
> 
> The only reason for this timeout I saw so far is:
> 
> > +/*
> > + * 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.
> 
> Clearly RT and !RT have completely different implementations and
> behaviour vs. rwsems and rwlocks. Just because !RT has a timeout does
> not make a good argument.
> 
> Just for the record: !RT has the timeout applicable in both directions
> to prevent writer bias via lock stealing. That's not a problem for RT
> because?

Once the writer got the lock, then all further reader and writer queue
up on rtmutex and will be processed one after the other. It only becomes
a problem once a writer with elevated priority acquires the lock
repeatedly to the point that tasks with lower priority starve.

> Can we finally get a proper justification for this?

Avoid writer starvation caused by having at least one reader in the
critical section all the time blocking the writer to make any progress.
Reader starvation is not an issue because all tasks line up on the
rtmutex and will be processed in FIFO order.
Tasks with elevated priority will be preferred and can lead starvation
of the tasks with lower priority. This is by design and can happen with
other lock types, too.

> > @@ -264,12 +285,20 @@ static int __sched rwbase_write_lock(struct rwbase_rt *rwb,
> >  		if (__rwbase_write_trylock(rwb))
> >  			break;
> >  
> > +		/*
> > +		 * Record timeout when reader bias is ignored. Ensure timeout
> > +		 * is at least 1 in case of overflow.
> > +		 */
> > +		rwb->waiter_timeout = (jiffies + RWBASE_RT_WAIT_TIMEOUT) | 1;
> > +
> 
> So this has two sillies:
> 
>    1) It resets the timeout once per loop which is plain wrong
> 
>    2) The "| 1" is really a sloppy hack
> 
> Why not doing the obvious:

Sure. Let me look at this once we agreed on the justification.

…
> Thanks,
> 
>         tglx
Sebastian