From: Peter Zijlstra <peterz@infradead.org>
To: Imre Deak <imre.deak@intel.com>
Cc: linux-kernel@vger.kernel.org, Ingo Molnar <mingo@redhat.com>,
Chris Wilson <chris@chris-wilson.co.uk>,
Daniel Vetter <daniel.vetter@intel.com>,
Ville Syrj??l?? <ville.syrjala@linux.intel.com>,
Waiman Long <Waiman.Long@hpe.com>,
Davidlohr Bueso <dave@stgolabs.net>,
Jason Low <jason.low2@hpe.com>
Subject: Re: [RFC] locking/mutex: Fix starvation of sleeping waiters
Date: Mon, 18 Jul 2016 19:15:37 +0200 [thread overview]
Message-ID: <20160718171537.GC6862@twins.programming.kicks-ass.net> (raw)
In-Reply-To: <1468858607-20481-1-git-send-email-imre.deak@intel.com>
On Mon, Jul 18, 2016 at 07:16:47PM +0300, Imre Deak wrote:
> Currently a thread sleeping on a mutex wait queue can be delayed
> indefinitely by other threads managing to steal the lock, that is
> acquiring the lock out-of-order before the sleepers. I noticed this via
> a testcase (see the Reference: below) where one CPU was unlocking /
> relocking a mutex in a tight loop while another CPU was delayed
> indefinitely trying to wake up and get the lock but losing out to the
> first CPU and going back to sleep:
>
> CPU0: CPU1:
> mutex_lock->acquire
> mutex_lock->sleep
> mutex_unlock->wake CPU1
> wakeup
> mutex_lock->acquire
> trylock fail->sleep
> mutex_unlock->wake CPU1
> wakeup
> mutex_lock->acquire
> trylock fail->sleep
> ... ...
>
> To fix this we can make sure that CPU1 makes progress by avoiding the
> fastpath locking, optimistic spinning and trylocking if there is any
> waiter on the list. The corresponding check can be done without holding
> wait_lock, since the goal is only to make sure sleepers make progress
> and not to guarantee that the locking will happen in FIFO order.
I think we went over this before, that will also completely destroy
performance under a number of workloads.
I'd have to go dig up that thread, but let's Cc more people first.
>
> CC: Peter Zijlstra <peterz@infradead.org>
> CC: Ingo Molnar <mingo@redhat.com>
> CC: Chris Wilson <chris@chris-wilson.co.uk>
> CC: Daniel Vetter <daniel.vetter@intel.com>
> CC: Ville Syrj??l?? <ville.syrjala@linux.intel.com>
> Reference: https://bugs.freedesktop.org/show_bug.cgi?id=96701
> Signed-off-by: Imre Deak <imre.deak@intel.com>
> ---
> include/linux/mutex.h | 5 +++++
> kernel/locking/mutex.c | 33 +++++++++++++++++++++------------
> 2 files changed, 26 insertions(+), 12 deletions(-)
>
> diff --git a/include/linux/mutex.h b/include/linux/mutex.h
> index 2cb7531..562dfa8 100644
> --- a/include/linux/mutex.h
> +++ b/include/linux/mutex.h
> @@ -130,6 +130,11 @@ static inline int mutex_is_locked(struct mutex *lock)
> return atomic_read(&lock->count) != 1;
> }
>
> +static inline int mutex_has_waiters(struct mutex *lock)
> +{
> + return !list_empty(&lock->wait_list);
> +}
> +
> /*
> * See kernel/locking/mutex.c for detailed documentation of these APIs.
> * Also see Documentation/locking/mutex-design.txt.
> diff --git a/kernel/locking/mutex.c b/kernel/locking/mutex.c
> index a70b90d..d18b531 100644
> --- a/kernel/locking/mutex.c
> +++ b/kernel/locking/mutex.c
> @@ -276,7 +276,7 @@ static inline int mutex_can_spin_on_owner(struct mutex *lock)
> */
> static inline bool mutex_try_to_acquire(struct mutex *lock)
> {
> - return !mutex_is_locked(lock) &&
> + return !mutex_is_locked(lock) && !mutex_has_waiters(lock) &&
> (atomic_cmpxchg_acquire(&lock->count, 1, 0) == 1);
> }
>
> @@ -520,7 +520,8 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass,
> preempt_disable();
> mutex_acquire_nest(&lock->dep_map, subclass, 0, nest_lock, ip);
>
> - if (mutex_optimistic_spin(lock, ww_ctx, use_ww_ctx)) {
> + if (!mutex_has_waiters(lock) &&
> + mutex_optimistic_spin(lock, ww_ctx, use_ww_ctx)) {
> /* got the lock, yay! */
> preempt_enable();
> return 0;
> @@ -532,7 +533,7 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass,
> * Once more, try to acquire the lock. Only try-lock the mutex if
> * it is unlocked to reduce unnecessary xchg() operations.
> */
> - if (!mutex_is_locked(lock) &&
> + if (!mutex_is_locked(lock) && !mutex_has_waiters(lock) &&
> (atomic_xchg_acquire(&lock->count, 0) == 1))
> goto skip_wait;
>
> @@ -556,7 +557,8 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass,
> * other waiters. We only attempt the xchg if the count is
> * non-negative in order to avoid unnecessary xchg operations:
> */
> - if (atomic_read(&lock->count) >= 0 &&
> + if (lock->wait_list.next == &waiter.list &&
> + atomic_read(&lock->count) >= 0 &&
> (atomic_xchg_acquire(&lock->count, -1) == 1))
> break;
>
> @@ -789,10 +791,11 @@ __mutex_lock_interruptible_slowpath(struct mutex *lock);
> */
> int __sched mutex_lock_interruptible(struct mutex *lock)
> {
> - int ret;
> + int ret = -1;
>
> might_sleep();
> - ret = __mutex_fastpath_lock_retval(&lock->count);
> + if (!mutex_has_waiters(lock))
> + ret = __mutex_fastpath_lock_retval(&lock->count);
> if (likely(!ret)) {
> mutex_set_owner(lock);
> return 0;
> @@ -804,10 +807,11 @@ EXPORT_SYMBOL(mutex_lock_interruptible);
>
> int __sched mutex_lock_killable(struct mutex *lock)
> {
> - int ret;
> + int ret = -1;
>
> might_sleep();
> - ret = __mutex_fastpath_lock_retval(&lock->count);
> + if (!mutex_has_waiters(lock))
> + ret = __mutex_fastpath_lock_retval(&lock->count);
> if (likely(!ret)) {
> mutex_set_owner(lock);
> return 0;
> @@ -905,6 +909,9 @@ int __sched mutex_trylock(struct mutex *lock)
> {
> int ret;
>
> + if (mutex_has_waiters(lock))
> + return 0;
> +
> ret = __mutex_fastpath_trylock(&lock->count, __mutex_trylock_slowpath);
> if (ret)
> mutex_set_owner(lock);
> @@ -917,11 +924,12 @@ EXPORT_SYMBOL(mutex_trylock);
> int __sched
> __ww_mutex_lock(struct ww_mutex *lock, struct ww_acquire_ctx *ctx)
> {
> - int ret;
> + int ret = -1;
>
> might_sleep();
>
> - ret = __mutex_fastpath_lock_retval(&lock->base.count);
> + if (!mutex_has_waiters(lock))
> + ret = __mutex_fastpath_lock_retval(&lock->base.count);
>
> if (likely(!ret)) {
> ww_mutex_set_context_fastpath(lock, ctx);
> @@ -935,11 +943,12 @@ EXPORT_SYMBOL(__ww_mutex_lock);
> int __sched
> __ww_mutex_lock_interruptible(struct ww_mutex *lock, struct ww_acquire_ctx *ctx)
> {
> - int ret;
> + int ret = -1;
>
> might_sleep();
>
> - ret = __mutex_fastpath_lock_retval(&lock->base.count);
> + if (!mutex_has_waiters(lock))
> + ret = __mutex_fastpath_lock_retval(&lock->base.count);
>
> if (likely(!ret)) {
> ww_mutex_set_context_fastpath(lock, ctx);
> --
> 2.5.0
>
next prev parent reply other threads:[~2016-07-18 17:15 UTC|newest]
Thread overview: 19+ messages / expand[flat|nested] mbox.gz Atom feed top
2016-07-18 16:16 [RFC] locking/mutex: Fix starvation of sleeping waiters Imre Deak
2016-07-18 17:15 ` Peter Zijlstra [this message]
2016-07-18 17:47 ` Jason Low
2016-07-19 16:53 ` Imre Deak
2016-07-19 22:57 ` Jason Low
2016-07-19 23:04 ` [RFC] Avoid mutex starvation when optimistic spinning is disabled Jason Low
2016-07-20 4:39 ` Jason Low
2016-07-20 13:29 ` Imre Deak
2016-07-21 20:57 ` Jason Low
2016-07-22 17:55 ` Waiman Long
2016-07-22 18:03 ` Davidlohr Bueso
2016-07-22 18:29 ` Imre Deak
2016-07-22 19:26 ` Davidlohr Bueso
2016-07-22 19:53 ` Imre Deak
2016-07-20 18:37 ` Waiman Long
2016-07-21 22:29 ` Jason Low
2016-07-22 9:34 ` Imre Deak
2016-07-22 18:44 ` Jason Low
2016-07-22 18:01 ` Waiman Long
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=20160718171537.GC6862@twins.programming.kicks-ass.net \
--to=peterz@infradead.org \
--cc=Waiman.Long@hpe.com \
--cc=chris@chris-wilson.co.uk \
--cc=daniel.vetter@intel.com \
--cc=dave@stgolabs.net \
--cc=imre.deak@intel.com \
--cc=jason.low2@hpe.com \
--cc=linux-kernel@vger.kernel.org \
--cc=mingo@redhat.com \
--cc=ville.syrjala@linux.intel.com \
/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).