From: Mel Gorman <mgorman@techsingularity.net>
To: Sebastian Andrzej Siewior <bigeasy@linutronix.de>
Cc: Peter Zijlstra <peterz@infradead.org>,
Thomas Gleixner <tglx@linutronix.de>,
Ingo Molnar <mingo@kernel.org>,
Davidlohr Bueso <dave@stgolabs.net>,
Linux-RT <linux-rt-users@vger.kernel.org>,
LKML <linux-kernel@vger.kernel.org>
Subject: Re: [PATCH v2] locking/rwbase: Prevent indefinite writer starvation
Date: Thu, 19 Jan 2023 17:41:01 +0000 [thread overview]
Message-ID: <20230119174101.rddtxk5xlamlnquh@techsingularity.net> (raw)
In-Reply-To: <Y8lvwKHmmnikVDgk@linutronix.de>
On Thu, Jan 19, 2023 at 05:28:48PM +0100, Sebastian Andrzej Siewior wrote:
> On 2023-01-19 11:02:20 [+0000], Mel Gorman wrote:
> > > - Once the writer removes READER_BIAS, it forces the reader into the
> > > slowpath.
> >
> > Removed in __rwbase_write_trylock IIUC
>
> And added back in case try trylock failed via __rwbase_write_unlock().
> The RTmutex is unlocked and the READER_BIAS is "returned".
>
Indeed.
> > > 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).
> > >
> >
> > 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.
>
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.
--
Mel Gorman
SUSE Labs
next prev parent reply other threads:[~2023-01-19 17:41 UTC|newest]
Thread overview: 22+ messages / expand[flat|nested] mbox.gz Atom feed top
2023-01-17 8:38 [PATCH v2] locking/rwbase: Prevent indefinite writer starvation Mel Gorman
[not found] ` <20230117105031.2512-1-hdanton@sina.com>
2023-01-17 12:18 ` Mel Gorman
2023-01-17 14:22 ` Sebastian Andrzej Siewior
2023-01-17 16:50 ` Mel Gorman
2023-01-18 10:45 ` Ingo Molnar
2023-01-18 16:00 ` Mel Gorman
2023-01-18 15:25 ` Sebastian Andrzej Siewior
2023-01-18 17:31 ` Mel Gorman
2023-01-19 8:25 ` Sebastian Andrzej Siewior
2023-01-19 11:02 ` Mel Gorman
2023-01-19 16:28 ` Sebastian Andrzej Siewior
2023-01-19 17:41 ` Mel Gorman [this message]
2023-01-19 17:48 ` Davidlohr Bueso
2023-01-19 17:58 ` Davidlohr Bueso
2023-01-20 8:25 ` Sebastian Andrzej Siewior
2023-01-20 13:24 ` Mel Gorman
2023-01-20 13:38 ` Sebastian Andrzej Siewior
2023-01-20 14:07 ` Mel Gorman
2023-01-20 15:36 ` Davidlohr Bueso
[not found] ` <20230119011538.3247-1-hdanton@sina.com>
2023-01-19 8:32 ` Sebastian Andrzej Siewior
[not found] ` <20230119135903.3524-1-hdanton@sina.com>
2023-01-19 16:36 ` Sebastian Andrzej Siewior
[not found] ` <20230120093711.3862-1-hdanton@sina.com>
2023-01-20 18:34 ` Sebastian Andrzej Siewior
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20230119174101.rddtxk5xlamlnquh@techsingularity.net \
--to=mgorman@techsingularity.net \
--cc=bigeasy@linutronix.de \
--cc=dave@stgolabs.net \
--cc=linux-kernel@vger.kernel.org \
--cc=linux-rt-users@vger.kernel.org \
--cc=mingo@kernel.org \
--cc=peterz@infradead.org \
--cc=tglx@linutronix.de \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).