Messages in this thread Patch in this message | | | Date | Thu, 11 Aug 2016 11:01:27 -0400 | From | Waiman Long <> | Subject | Re: [PATCH v5 3/3] locking/mutex: Ensure forward progress of waiter-spinner |
| |
On 08/10/2016 02:25 PM, Waiman Long wrote: > As both an optimistic spinner and a waiter-spinner (a woken task from > the wait queue spinning) can be spinning on the lock at the same time, > we cannot ensure forward progress for the waiter-spinner. So it is > possible for the waiter-spinner to be starved of getting the lock, > though not likely. > > This patch adds a flag to indicate that a waiter-spinner is > spinning and hence has priority over the acquisition of the lock. A > waiter-spinner sets this flag while spinning. An optimistic spinner > will check this flag and yield if set. This essentially makes the > waiter-spinner jump to the head of the optimistic spinning queue to > acquire the lock. > > There will be no increase in size for the mutex structure for > 64-bit architectures as there is an existing 4-byte hole. For 32-bit > architectures, there will be a size increase of 4 bytes. > > Signed-off-by: Waiman Long<Waiman.Long@hpe.com> > --- > include/linux/mutex.h | 1 + > kernel/locking/mutex.c | 36 +++++++++++++++++++++++++++--------- > 2 files changed, 28 insertions(+), 9 deletions(-) > > diff --git a/include/linux/mutex.h b/include/linux/mutex.h > index 2cb7531..f8e91ad 100644 > --- a/include/linux/mutex.h > +++ b/include/linux/mutex.h > @@ -57,6 +57,7 @@ struct mutex { > #endif > #ifdef CONFIG_MUTEX_SPIN_ON_OWNER > struct optimistic_spin_queue osq; /* Spinner MCS lock */ > + int waiter_spinning; > #endif > #ifdef CONFIG_DEBUG_MUTEXES > void *magic; > diff --git a/kernel/locking/mutex.c b/kernel/locking/mutex.c > index 15b521a..0912964 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->waiter_spinning = false; > #endif > > debug_mutex_init(lock, name, key); > @@ -337,9 +338,21 @@ static bool mutex_optimistic_spin(struct mutex *lock, > */ > if (!osq_lock(&lock->osq)) > goto done; > + } else { > + /* > + * Turn on the waiter spinning flag to discourage the spinner > + * from getting the lock. > + */ > + lock->waiter_spinning = true; > } > > - while (true) { > + /* > + * The cpu_relax_lowlatency() 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. > + */ > + for (;; cpu_relax_lowlatency()) { > struct task_struct *owner; > > if (use_ww_ctx&& ww_ctx->acquired> 0) { > @@ -359,6 +372,17 @@ static bool mutex_optimistic_spin(struct mutex *lock, > } > > /* > + * For regular opt-spinner, it waits until the waiter_spinning > + * flag isn't set. This will ensure forward progress for > + * the waiter spinner. > + */ > + if (!waiter&& READ_ONCE(lock->waiter_spinning)) { > + if (need_resched()) > + break; > + continue; > + } > + > + /* > * If there's an owner, wait for it to either > * release the lock or go to sleep. > */ > @@ -390,18 +414,12 @@ static bool mutex_optimistic_spin(struct mutex *lock, > */ > 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(); > } > > if (!waiter) > osq_unlock(&lock->osq); > + else > + lock->waiter_spinning = false; > done: > /* > * If we fell out of the spin path because of need_resched(),
The following is the updated patch that should fix the build error in non-x86 platform.
Cheers, Longman
================================ cut here ================================
locking/mutex: Ensure forward progress of waiter-spinner
As both an optimistic spinner and a waiter-spinner (a woken task from the wait queue spinning) can be spinning on the lock at the same time, we cannot ensure forward progress for the waiter-spinner. So it is possible for the waiter-spinner to be starved of getting the lock, though not likely.
This patch adds a flag to indicate that a waiter-spinner is spinning and hence has priority over the acquisition of the lock. A waiter-spinner sets this flag while spinning. An optimistic spinner will check this flag and yield if set. This essentially makes the waiter-spinner jump to the head of the optimistic spinning queue to acquire the lock.
There will be no increase in size for the mutex structure for 64-bit architectures as there is an existing 4-byte hole. For 32-bit architectures, there will be a size increase of 4 bytes.
Signed-off-by: Waiman Long <Waiman.Long@hpe.com> --- include/linux/mutex.h | 1 + kernel/locking/mutex.c | 21 +++++++++++++++++++++ 2 files changed, 22 insertions(+), 0 deletions(-)
diff --git a/include/linux/mutex.h b/include/linux/mutex.h index 2cb7531..f8e91ad 100644 --- a/include/linux/mutex.h +++ b/include/linux/mutex.h @@ -57,6 +57,7 @@ struct mutex { #endif #ifdef CONFIG_MUTEX_SPIN_ON_OWNER struct optimistic_spin_queue osq; /* Spinner MCS lock */ + int waiter_spinning; #endif #ifdef CONFIG_DEBUG_MUTEXES void *magic; diff --git a/kernel/locking/mutex.c b/kernel/locking/mutex.c index 15b521a..02d8029 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->waiter_spinning = false; #endif
debug_mutex_init(lock, name, key); @@ -337,6 +338,12 @@ static bool mutex_optimistic_spin(struct mutex *lock, */ if (!osq_lock(&lock->osq)) goto done; + } else { + /* + * Turn on the waiter spinning flag to discourage the spinner + * from getting the lock. + */ + lock->waiter_spinning = true; }
while (true) { @@ -359,6 +366,17 @@ static bool mutex_optimistic_spin(struct mutex *lock, }
/* + * For regular opt-spinner, it waits until the waiter_spinning + * flag isn't set. This will ensure forward progress for + * the waiter spinner. + */ + if (!waiter && READ_ONCE(lock->waiter_spinning)) { + if (need_resched()) + break; + goto relax; + } + + /* * If there's an owner, wait for it to either * release the lock or go to sleep. */ @@ -391,6 +409,7 @@ static bool mutex_optimistic_spin(struct mutex *lock, if (!owner && (need_resched() || rt_task(task))) break;
+relax: /* * The cpu_relax() call is a compiler barrier which forces * everything in this loop to be re-loaded. We don't need @@ -402,6 +421,8 @@ static bool mutex_optimistic_spin(struct mutex *lock,
if (!waiter) osq_unlock(&lock->osq); + else + lock->waiter_spinning = false; done: /* * If we fell out of the spin path because of need_resched(), -- 1.7.1
| |