Re: [Linaro-mm-sig] [PATCH 1/2] locking: Implement an algorithm choice for Wound-Wait mutexes

On 06/14/2018 04:42 PM, Peter Zijlstra wrote:

On Thu, Jun 14, 2018 at 01:48:39PM +0200, Thomas Hellstrom wrote:

...

The literature makes a distinction between "killed" and "wounded". In our context, "Killed" is when a transaction actually receives an -EDEADLK and needs to back off. "Wounded" is when someone (typically another transaction) requests a transaction to kill itself. A wound will often, but not always, lead to a kill. If the wounded transaction has finished its locking sequence, or has the opportunity to grab uncontended ww mutexes or steal contended (non-handoff) ww mutexes to finish its transaction it will do so and never kill itself.

Hopefully I got it all right this time; I folded your patch in and mucked around with it a bit, but haven't done anything except compile it.

I left the context/transaction thing because well, that's what we called the thing.

Overall, I think this looks fine. I'll just fix up the FLAG_WAITERS setting and affected comments and do some torture testing on it.

Are you OK with adding the new feature and the cleanup in the same patch?

Thomas

diff --git a/include/linux/ww_mutex.h b/include/linux/ww_mutex.h index 39fda195bf78..50ef5a10cfa0 100644 --- a/include/linux/ww_mutex.h +++ b/include/linux/ww_mutex.h @@ -8,6 +8,8 @@

• Wound/wait implementation:
• Copyright (C) 2013 Canonical Ltd.

• • Choice of algorithm:
• • Copyright (C) 2018 WMWare Inc.
  • This file contains the main data structure and API definitions.
  */

@@ -23,14 +25,17 @@ struct ww_class { struct lock_class_key mutex_key; const char *acquire_name; const char *mutex_name;

• unsigned int is_wait_die; };

struct ww_acquire_ctx { struct task_struct *task; unsigned long stamp;

• unsigned acquired;

• unsigned int acquired;
• unsigned short wounded;
• unsigned short is_wait_die; #ifdef CONFIG_DEBUG_MUTEXES

• unsigned done_acquire;

• unsigned int done_acquire; struct ww_class *ww_class; struct ww_mutex *contending_lock; #endif

@@ -38,8 +43,8 @@ struct ww_acquire_ctx { struct lockdep_map dep_map; #endif #ifdef CONFIG_DEBUG_WW_MUTEX_SLOWPATH

• unsigned deadlock_inject_interval;
• unsigned deadlock_inject_countdown;

• unsigned int deadlock_inject_interval;
• unsigned int deadlock_inject_countdown; #endif };

@@ -58,17 +63,21 @@ struct ww_mutex { # define __WW_CLASS_MUTEX_INITIALIZER(lockname, class) #endif -#define __WW_CLASS_INITIALIZER(ww_class) \ +#define __WW_CLASS_INITIALIZER(ww_class, _is_wait_die) \ { .stamp = ATOMIC_LONG_INIT(0) \ , .acquire_name = #ww_class "_acquire" \

• , .mutex_name = #ww_class "_mutex" }
  

• , .mutex_name = #ww_class "_mutex" \
  

• , .is_wait_die = _is_wait_die }
  

#define __WW_MUTEX_INITIALIZER(lockname, class) \ { .base = __MUTEX_INITIALIZER(lockname.base) \ __WW_CLASS_MUTEX_INITIALIZER(lockname, class) } +#define DEFINE_WD_CLASS(classname) \

• struct ww_class classname = __WW_CLASS_INITIALIZER(classname, 1)
• #define DEFINE_WW_CLASS(classname) \

• struct ww_class classname = __WW_CLASS_INITIALIZER(classname)

• struct ww_class classname = __WW_CLASS_INITIALIZER(classname, 0)

#define DEFINE_WW_MUTEX(mutexname, ww_class) \ struct ww_mutex mutexname = __WW_MUTEX_INITIALIZER(mutexname, ww_class) @@ -123,6 +132,8 @@ static inline void ww_acquire_init(struct ww_acquire_ctx *ctx, ctx->task = current; ctx->stamp = atomic_long_inc_return_relaxed(&ww_class->stamp); ctx->acquired = 0;

• ctx->wounded = false;
• ctx->is_wait_die = ww_class->is_wait_die; #ifdef CONFIG_DEBUG_MUTEXES ctx->ww_class = ww_class; ctx->done_acquire = 0;

diff --git a/kernel/locking/mutex.c b/kernel/locking/mutex.c index f44f658ae629..9e244af4647d 100644 --- a/kernel/locking/mutex.c +++ b/kernel/locking/mutex.c @@ -244,6 +244,22 @@ void __sched mutex_lock(struct mutex *lock) EXPORT_SYMBOL(mutex_lock); #endif +/*

• • Wait-Die:
• • The newer transactions are killed when:

• • It (the new transaction) makes a request for a lock being held
    

• • by an older transaction.
    

• • Wound-Wait:
• • The newer transactions are wounded when:

• • An older transaction makes a request for a lock being held by
    

• • the newer transaction.
    

• */

+/*

• • Associate the ww_mutex @ww with the context @ww_ctx under which we acquired
• • it.
• */ static __always_inline void ww_mutex_lock_acquired(struct ww_mutex *ww, struct ww_acquire_ctx *ww_ctx) {

@@ -282,26 +298,96 @@ ww_mutex_lock_acquired(struct ww_mutex *ww, struct ww_acquire_ctx *ww_ctx) DEBUG_LOCKS_WARN_ON(ww_ctx->ww_class != ww->ww_class); #endif ww_ctx->acquired++;

• ww->ctx = ww_ctx; }

+/*

• • Determine if context @a is 'after' context @b. IOW, @a should be wounded in
• • favour of @b.
• */ static inline bool __sched __ww_ctx_stamp_after(struct ww_acquire_ctx *a, struct ww_acquire_ctx *b) {

• return a->stamp - b->stamp <= LONG_MAX &&

•       (a->stamp != b->stamp || a > b);
  

• return (signed long)(a->stamp - b->stamp) > 0; }

/*

• • Wake up any waiters that may have to back off when the lock is held by the
• • given context.

• • Wait-Die; wake a younger waiter context (when locks held) such that it can die.

• • Due to the invariants on the wait list, this can only affect the first
• • waiter with a context.

• • Among waiters with context, only the first one can have other locks acquired
• • already (ctx->acquired > 0), because __ww_mutex_add_waiter() and
• • __ww_mutex_check_wound() wake any but the earliest context.
• */

+static bool __ww_mutex_die(struct mutex *lock, struct mutex_waiter *waiter,

•            struct ww_acquire_ctx *ww_ctx)
  

+{

• if (!ww_ctx->is_wait_die)

• return false;
  

• if (waiter->ww_ctx->acquired > 0 &&

• 	__ww_ctx_stamp_after(waiter->ww_ctx, ww_ctx)) {
  

• debug_mutex_wake_waiter(lock, waiter);
  

• wake_up_process(waiter->task);
  

• }
• return true;

+}

+/*

• • Wound-Wait; wound a younger @hold_ctx (if it has locks held).
• • XXX more; explain why we too only need to wake the first.
• */

+static bool __ww_mutex_wound(struct mutex *lock,

• 	     struct ww_acquire_ctx *ww_ctx,
  

• 	     struct ww_acquire_ctx *hold_ctx)
  

+{

• struct task_struct *owner = __mutex_owner(lock);
• lockdep_assert_held(&lock->wait_lock);
• /*

• * Possible through __ww_mutex_add_waiter() when we race with
  

• * ww_mutex_set_context_fastpath(). In that case we'll get here again
  

• * through __ww_mutex_check_waiters().
  

• */
  

• if (!hold_ctx)

• return false;
  

• /*

• * Can have !owner because of __mutex_unlock_slowpath(), but if owner,
  

• * it cannot go away because we'll have FLAG_WAITERS set and hold
  

• * wait_lock.
  

• */
  

• if (!owner)

• return false;
  

• if (ww_ctx->acquired > 0 && __ww_ctx_stamp_after(hold_ctx, ww_ctx)) {

• hold_ctx->wounded = 1;
  

• if (owner != current)
  

• 	wake_up_process(owner);
  

• return true;
  

• }
• return false;

+}

+/*

• • We just acquired @lock under @ww_ctx, if there are later contexts waiting
• • behind us on the wait-list, check if they need wounding/killing.
• • See __ww_mutex_add_waiter() for the list-order construction; basically the
• • list is ordered by stamp, smallest (oldest) first.
• • This relies on never mixing wait-die/wound-wait on the same wait-list; which is
• • currently ensured by that being a ww_class property.
  • The current task must not be on the wait list.
  */ static void __sched

-__ww_mutex_wakeup_for_backoff(struct mutex *lock, struct ww_acquire_ctx *ww_ctx) +__ww_mutex_check_waiters(struct mutex *lock, struct ww_acquire_ctx *ww_ctx) { struct mutex_waiter *cur; @@ -311,66 +397,50 @@ __ww_mutex_wakeup_for_backoff(struct mutex *lock, struct ww_acquire_ctx *ww_ctx) if (!cur->ww_ctx) continue;

• if (cur->ww_ctx->acquired > 0 &&
  

•     __ww_ctx_stamp_after(cur->ww_ctx, ww_ctx)) {
  

• 	debug_mutex_wake_waiter(lock, cur);
  

• 	wake_up_process(cur->task);
  

• }
  

• break;
  

• if (__ww_mutex_die(lock, cur, ww_ctx) ||
  

•     __ww_mutex_wound(lock, cur->ww_ctx, ww_ctx))
  

• 	break;
  

  } }

/*

• • After acquiring lock with fastpath or when we lost out in contested
• • slowpath, set ctx and wake up any waiters so they can recheck.

• • After acquiring lock with fastpath, where we do not hold wait_lock, set ctx
• • and wake up any waiters so they can recheck.
  */ static __always_inline void ww_mutex_set_context_fastpath(struct ww_mutex *lock, struct ww_acquire_ctx *ctx) { ww_mutex_lock_acquired(lock, ctx);

• lock->ctx = ctx;
• /*
  • The lock->ctx update should be visible on all cores before

• * the atomic read is done, otherwise contended waiters might be
  

• * the list_empty check is done, otherwise contended waiters might be
  

  • missed. The contended waiters will either see ww_ctx == NULL
  • and keep spinning, or it will acquire wait_lock, add itself
  • to waiter list and sleep.
  */

• smp_mb(); /* ^^^ */

• smp_mb(); /* See comments above and below. */

/*

• * Check if lock is contended, if not there is nobody to wake up
  

• * [W] ww->ctx = ctx	[W] list_add_tail()
  

• *     MB		    MB
  

• * [R] list_empty()	[R] ww->ctx
  

• *
  

• * The memory barrier above pairs with the memory barrier in
  

• * __ww_mutex_add_waiter() and makes sure we either observe ww->ctx
  

• * and/or !empty list.
  

  */

• if (likely(!(atomic_long_read(&lock->base.owner) & MUTEX_FLAG_WAITERS)))

• if (likely(list_empty(&lock->base.wait_list))) return;

/*

• * Uh oh, we raced in fastpath, wake up everyone in this case,
  

• * so they can see the new lock->ctx.
  

• * Uh oh, we raced in fastpath, check if any of the waiters need wounding.
  

  */ spin_lock(&lock->base.wait_lock);

• __ww_mutex_wakeup_for_backoff(&lock->base, ctx);

• __ww_mutex_check_waiters(&lock->base, ctx); spin_unlock(&lock->base.wait_lock); }

-/*

• • After acquiring lock in the slowpath set ctx.
• • Unlike for the fast path, the caller ensures that waiters are woken up where
• • necessary.
• • Callers must hold the mutex wait_lock.
• */

-static __always_inline void -ww_mutex_set_context_slowpath(struct ww_mutex *lock, struct ww_acquire_ctx *ctx) -{

• ww_mutex_lock_acquired(lock, ctx);
• lock->ctx = ctx;

-}

• #ifdef CONFIG_MUTEX_SPIN_ON_OWNER

static inline @@ -646,37 +716,83 @@ void __sched ww_mutex_unlock(struct ww_mutex *lock) } EXPORT_SYMBOL(ww_mutex_unlock);

+static __always_inline int __sched +__ww_mutex_kill(struct mutex *lock, struct ww_acquire_ctx *ww_ctx) +{

• if (ww_ctx->acquired > 0) {

+#ifdef CONFIG_DEBUG_MUTEXES

• struct ww_mutex *ww;
  

• ww = container_of(lock, struct ww_mutex, base);
  

• DEBUG_LOCKS_WARN_ON(ww_ctx->contending_lock);
  

• ww_ctx->contending_lock = ww;
  

+#endif

• return -EDEADLK;
  

• }
• return 0;

+}

+/*

• • Check the wound condition for the current lock acquire.
• • Wound-Wait: If we're wounded, kill ourself.
• • Wait-Die: If we're trying to acquire a lock already held by an older

• •       context, kill ourselves.
    

• • Since __ww_mutex_add_waiter() orders the wait-list on stamp, we only have to
• • look at waiters before us in the wait-list.
• */ static inline int __sched

-__ww_mutex_lock_check_stamp(struct mutex *lock, struct mutex_waiter *waiter, +__ww_mutex_check_wound(struct mutex *lock, struct mutex_waiter *waiter, struct ww_acquire_ctx *ctx) { struct ww_mutex *ww = container_of(lock, struct ww_mutex, base); struct ww_acquire_ctx *hold_ctx = READ_ONCE(ww->ctx); struct mutex_waiter *cur;

• if (ctx->acquired == 0)

• return 0;
  

• if (!ctx->is_wait_die) {

• if (ctx->wounded)
  

• 	return __ww_mutex_kill(lock, ctx);
  

• return 0;
  

• }
• if (hold_ctx && __ww_ctx_stamp_after(ctx, hold_ctx))

• goto deadlock;
  

• return __ww_mutex_kill(lock, ctx);
  

/* * If there is a waiter in front of us that has a context, then its

• * stamp is earlier than ours and we must back off.
  

• * stamp is earlier than ours and we must wound ourself.
  

  */ cur = waiter; list_for_each_entry_continue_reverse(cur, &lock->wait_list, list) {

• if (cur->ww_ctx)
  

• 	goto deadlock;
  

• if (!cur->ww_ctx)
  

• 	continue;
  

• return __ww_mutex_kill(lock, ctx);
  

  }

return 0;

-deadlock: -#ifdef CONFIG_DEBUG_MUTEXES

• DEBUG_LOCKS_WARN_ON(ctx->contending_lock);
• ctx->contending_lock = ww;

-#endif

• return -EDEADLK; }

+/*

• • Add @waiter to the wait-list, keep the wait-list ordered by stamp, smallest
• • first. Such that older contexts are preferred to acquire the lock over
• • younger contexts.
• • Waiters without context are interspersed in FIFO order.
• • Furthermore, for Wait-Die kill ourself immediately when possible (there are
• • older contexts already waiting) to avoid unnecessary waiting and for
• • Wound-Wait ensure we wound the owning context when it is younger.
• */ static inline int __sched __ww_mutex_add_waiter(struct mutex_waiter *waiter, struct mutex *lock,

@@ -684,16 +800,21 @@ __ww_mutex_add_waiter(struct mutex_waiter *waiter, { struct mutex_waiter *cur; struct list_head *pos;

• bool is_wait_die;

if (!ww_ctx) { list_add_tail(&waiter->list, &lock->wait_list); return 0; }

• is_wait_die = ww_ctx->is_wait_die;
• /*
  • Add the waiter before the first waiter with a higher stamp.
  • Waiters without a context are skipped to avoid starving

• * them.
  

• * them. Wait-Die waiters may back off here. Wound-Wait waiters
  

• * never back off here, but they are sorted in stamp order and
  

• * may wound the lock holder.
  

  */ pos = &lock->wait_list; list_for_each_entry_reverse(cur, &lock->wait_list, list) {

@@ -701,16 +822,16 @@ __ww_mutex_add_waiter(struct mutex_waiter *waiter, continue; if (__ww_ctx_stamp_after(ww_ctx, cur->ww_ctx)) {

• 	/* Back off immediately if necessary. */
  

• 	if (ww_ctx->acquired > 0) {
  

-#ifdef CONFIG_DEBUG_MUTEXES

• 		struct ww_mutex *ww;
  

• 		ww = container_of(lock, struct ww_mutex, base);
  

• 		DEBUG_LOCKS_WARN_ON(ww_ctx->contending_lock);
  

• 		ww_ctx->contending_lock = ww;
  

-#endif

• 		return -EDEADLK;
  

• 	/*
  

• 	 * Wait-Die: if we find an older context waiting, there
  

• 	 * is no point in queueing behind it, as we'd have to
  

• 	 * wound ourselves the moment it would acquire the
  

• 	 * lock.
  

• 	 */
  

• 	if (is_wait_die) {
  

• 		int ret = __ww_mutex_kill(lock, ww_ctx);
  

• 		if (ret)
  

• 			return ret;
  }
  

break; @@ -718,17 +839,29 @@ __ww_mutex_add_waiter(struct mutex_waiter *waiter, pos = &cur->list;

• /* Wait-Die: ensure younger waiters die. */
  

• __ww_mutex_die(lock, cur, ww_ctx);
  

• }
• list_add_tail(&waiter->list, pos);
• /*

• * Wound-Wait: if we're blocking on a mutex owned by a younger context,
  

• * wound that such that we might proceed.
  

• */
  

• if (!is_wait_die) {

• struct ww_mutex *ww = container_of(lock, struct ww_mutex, base);
  

• /*

•  * Wake up the waiter so that it gets a chance to back
  

•  * off.
  

•  * See ww_mutex_set_context_fastpath(). Orders the
  

•  * list_add_tail() vs the ww->ctx load, such that either we
  

•  * or the fastpath will wound @ww->ctx.
  

  */

• if (cur->ww_ctx->acquired > 0) {
  

• 	debug_mutex_wake_waiter(lock, cur);
  

• 	wake_up_process(cur->task);
  

• }
  

• smp_mb();
  

• __ww_mutex_wound(lock, ww_ctx, ww->ctx);
  

  }

• list_add_tail(&waiter->list, pos); return 0; }

@@ -751,6 +884,14 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass, if (use_ww_ctx && ww_ctx) { if (unlikely(ww_ctx == READ_ONCE(ww->ctx))) return -EALREADY;

• /*
  

•  * Reset the wounded flag after a kill.  No other process can
  

•  * race and wound us here since they can't have a valid owner
  

•  * pointer at this time.
  

•  */
  

• if (ww_ctx->acquired == 0)
  

• 	ww_ctx->wounded = 0;
  

  }

preempt_disable(); @@ -772,7 +913,7 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass, */ if (__mutex_trylock(lock)) { if (use_ww_ctx && ww_ctx)

• 	__ww_mutex_wakeup_for_backoff(lock, ww_ctx);
  

• 	__ww_mutex_check_waiters(lock, ww_ctx);
  

goto skip_wait; } @@ -790,10 +931,10 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass, waiter.ww_ctx = MUTEX_POISON_WW_CTX; #endif } else {

• /* Add in stamp order, waking up waiters that must back off. */
  

• /* Add in stamp order, waking up waiters that must wound themselves. */
  

  ret = __ww_mutex_add_waiter(&waiter, lock, ww_ctx); if (ret)

• 	goto err_early_backoff;
  

• 	goto err_early_kill;
  

waiter.ww_ctx = ww_ctx; } @@ -824,8 +965,8 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass, goto err; }

• if (use_ww_ctx && ww_ctx && ww_ctx->acquired > 0) {
  

• 	ret = __ww_mutex_lock_check_stamp(lock, &waiter, ww_ctx);
  

• if (use_ww_ctx && ww_ctx) {
  

• 	ret = __ww_mutex_check_wound(lock, &waiter, ww_ctx);
  if (ret)
  	goto err;
  

  }

@@ -859,6 +1000,16 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass, acquired: __set_current_state(TASK_RUNNING);

• if (use_ww_ctx && ww_ctx) {

• /*
  

•  * Wound-Wait; we stole the lock (!first_waiter), check the
  

•  * waiters. This, together with XXX, ensures __ww_mutex_wound()
  

•  * only needs to check the first waiter (with context).
  

•  */
  

• if (!ww_ctx->is_wait_die && !__mutex_waiter_is_first(lock, &waiter))
  

• 	__ww_mutex_check_waiters(lock, ww_ctx);
  

• }
• mutex_remove_waiter(lock, &waiter, current); if (likely(list_empty(&lock->wait_list))) __mutex_clear_flag(lock, MUTEX_FLAGS);

@@ -870,7 +1021,7 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass, lock_acquired(&lock->dep_map, ip); if (use_ww_ctx && ww_ctx)

• ww_mutex_set_context_slowpath(ww, ww_ctx);
  

• ww_mutex_lock_acquired(ww, ww_ctx);
  

spin_unlock(&lock->wait_lock); preempt_enable(); @@ -879,7 +1030,7 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass, err: __set_current_state(TASK_RUNNING); mutex_remove_waiter(lock, &waiter, current); -err_early_backoff: +err_early_kill: spin_unlock(&lock->wait_lock); debug_mutex_free_waiter(&waiter); mutex_release(&lock->dep_map, 1, ip);