From 1bbb5a4434d395f48163abc5435c5c720a15d327 Mon Sep 17 00:00:00 2001 From: Waiman Long Date: Thu, 21 Jan 2016 17:53:14 -0500 Subject: [PATCH] locking/mutex: Enable optimistic spinning of woken task in wait list Ding Tianhong reported a live-lock situation where a constant stream of incoming optimistic spinners blocked a task in the wait list from getting the mutex. This patch attempts to fix this live-lock condition by enabling the a woken task in the wait list to enter optimistic spinning loop itself with precedence over the ones in the OSQ. This should prevent the live-lock condition from happening. Signed-off-by: Waiman Long --- include/linux/mutex.h | 2 + kernel/locking/mutex.c | 95 +++++++++++++++++++++++++++++++++++++++++++++++- 2 files changed, 95 insertions(+), 2 deletions(-) diff --git a/include/linux/mutex.h b/include/linux/mutex.h index 2cb7531..2c55ecd 100644 --- a/include/linux/mutex.h +++ b/include/linux/mutex.h @@ -57,6 +57,8 @@ struct mutex { #endif #ifdef CONFIG_MUTEX_SPIN_ON_OWNER struct optimistic_spin_queue osq; /* Spinner MCS lock */ + /* Set if wait list head actively spinning */ + int wlh_spinning; #endif #ifdef CONFIG_DEBUG_MUTEXES void *magic; diff --git a/kernel/locking/mutex.c b/kernel/locking/mutex.c index 0551c21..8b27b03 100644 --- a/kernel/locking/mutex.c +++ b/kernel/locking/mutex.c @@ -55,6 +55,7 @@ __mutex_init(struct mutex *lock, const char *name, struct lock_class_key *key) mutex_clear_owner(lock); #ifdef CONFIG_MUTEX_SPIN_ON_OWNER osq_lock_init(&lock->osq); + lock->wlh_spinning = false; #endif debug_mutex_init(lock, name, key); @@ -346,8 +347,12 @@ static bool mutex_optimistic_spin(struct mutex *lock, if (owner && !mutex_spin_on_owner(lock, owner)) break; - /* Try to acquire the mutex if it is unlocked. */ - if (mutex_try_to_acquire(lock)) { + /* + * Try to acquire the mutex if it is unlocked and the wait + * list head isn't spinning on the lock. + */ + if (!READ_ONCE(lock->wlh_spinning) && + mutex_try_to_acquire(lock)) { lock_acquired(&lock->dep_map, ip); if (use_ww_ctx) { @@ -398,12 +403,91 @@ done: return false; } + +/* + * Wait list head optimistic spinning + * + * The wait list head, when woken up, will try to spin on the lock if the + * lock owner is active. It will also set the wlh_spinning flag to give + * itself a higher chance of getting the lock than the other optimisically + * spinning locker in the OSQ. + */ +static bool mutex_wlh_opt_spin(struct mutex *lock, + struct ww_acquire_ctx *ww_ctx, const bool use_ww_ctx) +{ + struct task_struct *owner, *task = current; + int gotlock = false; + + WRITE_ONCE(lock->wlh_spinning, true); + while (true) { + if (use_ww_ctx && ww_ctx->acquired > 0) { + struct ww_mutex *ww; + + ww = container_of(lock, struct ww_mutex, base); + /* + * If ww->ctx is set the contents are undefined, only + * by acquiring wait_lock there is a guarantee that + * they are not invalid when reading. + * + * As such, when deadlock detection needs to be + * performed the optimistic spinning cannot be done. + */ + if (READ_ONCE(ww->ctx)) + break; + } + + /* + * If there's an owner, wait for it to either + * release the lock or go to sleep. + */ + owner = READ_ONCE(lock->owner); + if (owner && !mutex_spin_on_owner(lock, owner)) + break; + + /* + * Try to acquire the mutex if it is unlocked. The mutex + * value is set to -1 which will be changed to 0 later on + * if the wait list becomes empty. + */ + if (!mutex_is_locked(lock) && + (atomic_cmpxchg_acquire(&lock->count, 1, -1) == 1)) { + gotlock = true; + break; + } + + /* + * When there's no owner, we might have preempted between the + * owner acquiring the lock and setting the owner field. If + * we're an RT task that will live-lock because we won't let + * the owner complete. + */ + if (!owner && (need_resched() || rt_task(task))) + break; + + /* + * The cpu_relax() call is a compiler barrier which forces + * everything in this loop to be re-loaded. We don't need + * memory barriers as we'll eventually observe the right + * values at the cost of a few extra spins. + */ + cpu_relax_lowlatency(); + + } + WRITE_ONCE(lock->wlh_spinning, false); + return gotlock; +} #else static bool mutex_optimistic_spin(struct mutex *lock, struct ww_acquire_ctx *ww_ctx, const bool use_ww_ctx) { return false; } + +static bool mutex_wlh_opt_spin(struct mutex *lock, + struct ww_acquire_ctx *ww_ctx, const bool use_ww_ctx) +{ + return false; +} #endif __visible __used noinline @@ -543,6 +627,8 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass, lock_contended(&lock->dep_map, ip); for (;;) { + int gotlock; + /* * Lets try to take the lock again - this is needed even if * we get here for the first time (shortly after failing to @@ -577,7 +663,12 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass, /* didn't get the lock, go to sleep: */ spin_unlock_mutex(&lock->wait_lock, flags); schedule_preempt_disabled(); + + /* optimistically spinning on the mutex without the wait lock */ + gotlock = mutex_wlh_opt_spin(lock, ww_ctx, use_ww_ctx); spin_lock_mutex(&lock->wait_lock, flags); + if (gotlock) + break; } __set_task_state(task, TASK_RUNNING); -- 1.7.1