Re: [PATCH v2 1/2] locking: Implement an algorithm choice for Wound-Wait mutexes
[...] > >>+ /* > >>+* wake_up_process() paired with set_current_state() inserts > >>+* sufficient barriers to make sure @owner either sees it's > >>+* wounded or has a wakeup pending to re-read the wounded > >>+* state. > >IIUC, "sufficient barriers" = full memory barriers (here). (You may > >want to be more specific.) > > Thanks for reviewing! > OK. What about if someone relaxes that in the future? This is actually one of my main concerns ;-) as, IIUC, those barriers are not only sufficient but also necessary: anything "less than a full barrier" (in either wake_up_process() or set_current_state()) would _not_ guarantee the "condition" above unless I'm misunderstanding it. But am I misunderstanding it? Which barriers/guarantee do you _need_ from the above mentioned pairing? (hence my comment...) Andrea ___ dri-devel mailing list dri-devel@lists.freedesktop.org https://lists.freedesktop.org/mailman/listinfo/dri-devel
Re: [PATCH v2 1/2] locking: Implement an algorithm choice for Wound-Wait mutexes
Hi Thomas, On Thu, Jun 14, 2018 at 09:29:21AM +0200, Thomas Hellstrom wrote: > The current Wound-Wait mutex algorithm is actually not Wound-Wait but > Wait-Die. Implement also Wound-Wait as a per-ww-class choice. Wound-Wait > is, contrary to Wait-Die a preemptive algorithm and is known to generate > fewer backoffs. Testing reveals that this is true if the > number of simultaneous contending transactions is small. > As the number of simultaneous contending threads increases, Wait-Wound > becomes inferior to Wait-Die in terms of elapsed time. > Possibly due to the larger number of held locks of sleeping transactions. > > Update documentation and callers. > > Timings using git://people.freedesktop.org/~thomash/ww_mutex_test > tag patch-18-06-14 > > Each thread runs 10 batches of lock / unlock 800 ww mutexes randomly > chosen out of 10. Four core Intel x86_64: > > Algorithm#threads Rollbacks time > Wound-Wait 4 ~100 ~17s. > Wait-Die 4 ~15~19s. > Wound-Wait 16 ~36~109s. > Wait-Die 16 ~45~82s. > > Cc: Peter Zijlstra > Cc: Ingo Molnar > Cc: Jonathan Corbet > Cc: Gustavo Padovan > Cc: Maarten Lankhorst > Cc: Sean Paul > Cc: David Airlie > Cc: Davidlohr Bueso > Cc: "Paul E. McKenney" > Cc: Josh Triplett > Cc: Thomas Gleixner > Cc: Kate Stewart > Cc: Philippe Ombredanne > Cc: Greg Kroah-Hartman > Cc: linux-...@vger.kernel.org > Cc: linux-me...@vger.kernel.org > Cc: linaro-mm-...@lists.linaro.org > Signed-off-by: Thomas Hellstrom > > --- > v2: > * Update API according to review comment by Greg Kroah-Hartman. > * Address review comments by Peter Zijlstra: > - Avoid _Bool in composites > - Fix typo > - Use __mutex_owner() where applicable > - Rely on built-in barriers for the main loop exit condition, > struct ww_acquire_ctx::wounded. Update code comments. > - Explain unlocked use of list_empty(). > --- > Documentation/locking/ww-mutex-design.txt | 54 > drivers/dma-buf/reservation.c | 2 +- > drivers/gpu/drm/drm_modeset_lock.c| 2 +- > include/linux/ww_mutex.h | 19 -- > kernel/locking/locktorture.c | 2 +- > kernel/locking/mutex.c| 103 > +++--- > kernel/locking/test-ww_mutex.c| 2 +- > lib/locking-selftest.c| 2 +- > 8 files changed, 156 insertions(+), 30 deletions(-) > > diff --git a/Documentation/locking/ww-mutex-design.txt > b/Documentation/locking/ww-mutex-design.txt > index 34c3a1b50b9a..b9597def9581 100644 > --- a/Documentation/locking/ww-mutex-design.txt > +++ b/Documentation/locking/ww-mutex-design.txt > @@ -1,4 +1,4 @@ > -Wait/Wound Deadlock-Proof Mutex Design > +Wound/Wait Deadlock-Proof Mutex Design > == > > Please read mutex-design.txt first, as it applies to wait/wound mutexes too. > @@ -32,10 +32,23 @@ the oldest task) wins, and the one with the higher > reservation id (i.e. the > younger task) unlocks all of the buffers that it has already locked, and then > tries again. > > -In the RDBMS literature this deadlock handling approach is called wait/wound: > -The older tasks waits until it can acquire the contended lock. The younger > tasks > -needs to back off and drop all the locks it is currently holding, i.e. the > -younger task is wounded. > +In the RDBMS literature, a reservation ticket is associated with a > transaction. > +and the deadlock handling approach is called Wait-Die. The name is based on > +the actions of a locking thread when it encounters an already locked mutex. > +If the transaction holding the lock is younger, the locking transaction > waits. > +If the transaction holding the lock is older, the locking transaction backs > off > +and dies. Hence Wait-Die. > +There is also another algorithm called Wound-Wait: > +If the transaction holding the lock is younger, the locking transaction > +preempts the transaction holding the lock, requiring it to back off. It > +Wounds the other transaction. > +If the transaction holding the lock is older, it waits for the other > +transaction. Hence Wound-Wait. > +The two algorithms are both fair in that a transaction will eventually > succeed. > +However, the Wound-Wait algorithm is typically stated to generate fewer > backoffs > +compared to Wait-Die, but is, on the other hand, associated with more work > than > +Wait-Die when recovering from a backoff. Wound-Wait is also a preemptive > +algorithm which requires a reliable way to preempt another transaction. > > Concepts > > @@ -47,10 +60,12 @@ Acquire context: To ensure eventual forward progress it > is important the a task > trying to acquire locks doesn't grab a new reservation id, but keeps the one > it > acquired when starting the lock acquisition. This ticket is stored in the > acquire context. Furthermore the acquire
Re: [PATCH v2 1/2] locking: Implement an algorithm choice for Wound-Wait mutexes
On Thu, Jun 14, 2018 at 01:54:15PM +0200, Thomas Hellstrom wrote: > On 06/14/2018 01:36 PM, Peter Zijlstra wrote: > > Currently you don't allow mixing WD and WW contexts (which is not > > immediately obvious from the above code), and the above hard relies on > > that. Are there sensible use cases for mixing them? IOW will your > > current restriction stand without hassle? > > Contexts _must_ agree on the algorithm used to resolve deadlocks. With > Wait-Die, for example, older transactions will wait if a lock is held by a > younger transaction and with Wound-Wait, younger transactions will wait if a > lock is held by an older transaction so there is no way of mixing them. Maybe the compiler should be enforcing that; ie make it a different type? ___ dri-devel mailing list dri-devel@lists.freedesktop.org https://lists.freedesktop.org/mailman/listinfo/dri-devel
Re: [PATCH v2 1/2] locking: Implement an algorithm choice for Wound-Wait mutexes
On Thu, Jun 14, 2018 at 03:43:04PM +0200, Thomas Hellstrom wrote: > It's intended to be enforced by storing the algorithm choice in the > WW_MUTEX_CLASS which must be common for an acquire context and the > ww_mutexes it acquires. However, I don't think there is a check that that > holds. I guess we could add it as a DEBUG_MUTEX test in ww_mutex_lock(). There is ww_mutex_lock_acquired(): DEBUG_LOCKS_WARN_ON(ww_ctx->ww_class != ww->ww_class) which should trigger if you try and be clever. ___ dri-devel mailing list dri-devel@lists.freedesktop.org https://lists.freedesktop.org/mailman/listinfo/dri-devel
Re: [PATCH v2 1/2] locking: Implement an algorithm choice for Wound-Wait mutexes
On 06/14/2018 03:29 PM, Matthew Wilcox wrote: On Thu, Jun 14, 2018 at 01:54:15PM +0200, Thomas Hellstrom wrote: On 06/14/2018 01:36 PM, Peter Zijlstra wrote: Currently you don't allow mixing WD and WW contexts (which is not immediately obvious from the above code), and the above hard relies on that. Are there sensible use cases for mixing them? IOW will your current restriction stand without hassle? Contexts _must_ agree on the algorithm used to resolve deadlocks. With Wait-Die, for example, older transactions will wait if a lock is held by a younger transaction and with Wound-Wait, younger transactions will wait if a lock is held by an older transaction so there is no way of mixing them. Maybe the compiler should be enforcing that; ie make it a different type? It's intended to be enforced by storing the algorithm choice in the WW_MUTEX_CLASS which must be common for an acquire context and the ww_mutexes it acquires. However, I don't think there is a check that that holds. I guess we could add it as a DEBUG_MUTEX test in ww_mutex_lock(). Thanks, Thomas ___ dri-devel mailing list dri-devel@lists.freedesktop.org https://lists.freedesktop.org/mailman/listinfo/dri-devel
Re: [PATCH v2 1/2] locking: Implement an algorithm choice for Wound-Wait mutexes
On 06/14/2018 02:48 PM, Thomas Hellstrom wrote:
Hi, Peter,
On 06/14/2018 02:41 PM, Peter Zijlstra wrote:
On Thu, Jun 14, 2018 at 09:29:21AM +0200, Thomas Hellstrom wrote:
+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(>wait_lock);
+
+ if (owner && hold_ctx && __ww_ctx_stamp_after(hold_ctx, ww_ctx) &&
+ ww_ctx->acquired > 0) {
+ hold_ctx->wounded = 1;
+
+ /*
+ * wake_up_process() paired with set_current_state() inserts
+ * sufficient barriers to make sure @owner either sees it's
+ * wounded or has a wakeup pending to re-read the wounded
+ * state.
+ *
+ * The value of hold_ctx->wounded in
+ * __ww_mutex_lock_check_stamp();
+ */
+ if (owner != current)
+ wake_up_process(owner);
+
+ return true;
+ }
+
+ return false;
+}
@@ -338,12 +377,18 @@ ww_mutex_set_context_fastpath(struct ww_mutex
*lock, struct ww_acquire_ctx *ctx)
* 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
+ * Check if lock is contended, if not there is nobody to wake up.
+ * We can use list_empty() unlocked here since it only compares a
+ * list_head field pointer to the address of the list head
+ * itself, similarly to how list_empty() can be considered
RCU-safe.
+ * The memory barrier above pairs with the memory barrier in
+ * __ww_mutex_add_waiter and makes sure lock->ctx is visible
before
+ * we check for waiters.
*/
- if (likely(!(atomic_long_read(>base.owner) &
MUTEX_FLAG_WAITERS)))
+ if (likely(list_empty(>base.wait_list)))
return;
OK, so what happens is that if we see !empty list, we take wait_lock,
if we end up in __ww_mutex_wound() we must really have !empty wait-list.
It can however still see !owner because __mutex_unlock_slowpath() can
clear the owner field. But if owner is set, it must stay valid because
FLAG_WAITERS and we're holding wait_lock.
If __ww_mutex_wound() is called from ww_mutex_set_context_fastpath()
owner is the current process so we can never see !owner. However if
__ww_mutex_wound() is called from __ww_mutex_add_waiter() then the
above is true.
Or actually it was intended to be true, but FLAG_WAITERS is set too
late. It needs to be moved to just after we actually add the waiter to
the list.
Then the hunk that replaces a FLAG_WAITERS read with a lockless
list_empty() can also be ditched.
/Thomas
So the wake_up_process() is in fact safe.
Let me put that in a comment.
Thanks,
Thomas
___
dri-devel mailing list
dri-devel@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/dri-devel
Re: [PATCH v2 1/2] locking: Implement an algorithm choice for Wound-Wait mutexes
Hi, Peter,
On 06/14/2018 02:41 PM, Peter Zijlstra wrote:
On Thu, Jun 14, 2018 at 09:29:21AM +0200, Thomas Hellstrom wrote:
+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(>wait_lock);
+
+ if (owner && hold_ctx && __ww_ctx_stamp_after(hold_ctx, ww_ctx) &&
+ ww_ctx->acquired > 0) {
+ hold_ctx->wounded = 1;
+
+ /*
+* wake_up_process() paired with set_current_state() inserts
+* sufficient barriers to make sure @owner either sees it's
+* wounded or has a wakeup pending to re-read the wounded
+* state.
+*
+* The value of hold_ctx->wounded in
+* __ww_mutex_lock_check_stamp();
+*/
+ if (owner != current)
+ wake_up_process(owner);
+
+ return true;
+ }
+
+ return false;
+}
@@ -338,12 +377,18 @@ ww_mutex_set_context_fastpath(struct ww_mutex *lock,
struct ww_acquire_ctx *ctx)
* 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
+* Check if lock is contended, if not there is nobody to wake up.
+* We can use list_empty() unlocked here since it only compares a
+* list_head field pointer to the address of the list head
+* itself, similarly to how list_empty() can be considered RCU-safe.
+* The memory barrier above pairs with the memory barrier in
+* __ww_mutex_add_waiter and makes sure lock->ctx is visible before
+* we check for waiters.
*/
- if (likely(!(atomic_long_read(>base.owner) & MUTEX_FLAG_WAITERS)))
+ if (likely(list_empty(>base.wait_list)))
return;
OK, so what happens is that if we see !empty list, we take wait_lock,
if we end up in __ww_mutex_wound() we must really have !empty wait-list.
It can however still see !owner because __mutex_unlock_slowpath() can
clear the owner field. But if owner is set, it must stay valid because
FLAG_WAITERS and we're holding wait_lock.
If __ww_mutex_wound() is called from ww_mutex_set_context_fastpath()
owner is the current process so we can never see !owner. However if
__ww_mutex_wound() is called from __ww_mutex_add_waiter() then the above
is true.
So the wake_up_process() is in fact safe.
Let me put that in a comment.
Thanks,
Thomas
___
dri-devel mailing list
dri-devel@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/dri-devel
Re: [PATCH v2 1/2] locking: Implement an algorithm choice for Wound-Wait mutexes
On Thu, Jun 14, 2018 at 09:29:21AM +0200, Thomas Hellstrom wrote:
> +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(>wait_lock);
> +
> + if (owner && hold_ctx && __ww_ctx_stamp_after(hold_ctx, ww_ctx) &&
> + ww_ctx->acquired > 0) {
> + hold_ctx->wounded = 1;
> +
> + /*
> + * wake_up_process() paired with set_current_state() inserts
> + * sufficient barriers to make sure @owner either sees it's
> + * wounded or has a wakeup pending to re-read the wounded
> + * state.
> + *
> + * The value of hold_ctx->wounded in
> + * __ww_mutex_lock_check_stamp();
> + */
> + if (owner != current)
> + wake_up_process(owner);
> +
> + return true;
> + }
> +
> + return false;
> +}
> @@ -338,12 +377,18 @@ ww_mutex_set_context_fastpath(struct ww_mutex *lock,
> struct ww_acquire_ctx *ctx)
>* 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
> + * Check if lock is contended, if not there is nobody to wake up.
> + * We can use list_empty() unlocked here since it only compares a
> + * list_head field pointer to the address of the list head
> + * itself, similarly to how list_empty() can be considered RCU-safe.
> + * The memory barrier above pairs with the memory barrier in
> + * __ww_mutex_add_waiter and makes sure lock->ctx is visible before
> + * we check for waiters.
>*/
> - if (likely(!(atomic_long_read(>base.owner) & MUTEX_FLAG_WAITERS)))
> + if (likely(list_empty(>base.wait_list)))
> return;
>
OK, so what happens is that if we see !empty list, we take wait_lock,
if we end up in __ww_mutex_wound() we must really have !empty wait-list.
It can however still see !owner because __mutex_unlock_slowpath() can
clear the owner field. But if owner is set, it must stay valid because
FLAG_WAITERS and we're holding wait_lock.
So the wake_up_process() is in fact safe.
Let me put that in a comment.
___
dri-devel mailing list
dri-devel@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/dri-devel
Re: [PATCH v2 1/2] locking: Implement an algorithm choice for Wound-Wait mutexes
Resending hopefully better formatted..
On 06/14/2018 01:49 PM, Andrea Parri wrote:
[...]
+ /*
+* wake_up_process() paired with set_current_state() inserts
+* sufficient barriers to make sure @owner either sees it's
+* wounded or has a wakeup pending to re-read the wounded
+* state.
IIUC, "sufficient barriers" = full memory barriers (here). (You may
want to be more specific.)
Thanks for reviewing!
OK. What about if someone relaxes that in the future?
This is actually one of my main concerns ;-) as, IIUC, those barriers are
not only sufficient but also necessary: anything "less than a full barrier"
(in either wake_up_process() or set_current_state()) would _not_ guarantee
the "condition" above unless I'm misunderstanding it.
But am I misunderstanding it? Which barriers/guarantee do you _need_ from
the above mentioned pairing? (hence my comment...)
Andrea
No you are probably not misunderstanding me at all. My comment
originated from the reading of the kerneldoc of set_current_state()
/*
* set_current_state() includes a barrier so that the write of current->state
* is correctly serialised wrt the caller's subsequent test of whether to
* actually sleep:
*
* for (;;) {
* set_current_state(TASK_UNINTERRUPTIBLE);
* if (!need_sleep)
* break;
*
* schedule();
* }
* __set_current_state(TASK_RUNNING);
*
* If the caller does not need such serialisation (because, for instance, the
* condition test and condition change and wakeup are under the same
lock) then
* use __set_current_state().
*
* The above is typically ordered against the wakeup, which does:
*
* need_sleep = false;
* wake_up_state(p, TASK_UNINTERRUPTIBLE);
*
* Where wake_up_state() (and all other wakeup primitives) imply enough
* barriers to order the store of the variable against wakeup.
---
*/
And with ctx->wounded := !need_sleep this exactly matches what's
happening in my code. So what I was trying to say in the comment was
that this above contract is sufficient to guarantee the "condition"
above, whitout me actually knowing exactly what barriers are required.
Thanks, Thomas
___
dri-devel mailing list
dri-devel@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/dri-devel
Re: [PATCH v2 1/2] locking: Implement an algorithm choice for Wound-Wait mutexes
On 06/14/2018 01:49 PM, Andrea Parri wrote:
[...]
+ /*
+* wake_up_process() paired with set_current_state() inserts
+* sufficient barriers to make sure @owner either sees it's
+* wounded or has a wakeup pending to re-read the wounded
+* state.
IIUC, "sufficient barriers" = full memory barriers (here). (You may
want to be more specific.)
Thanks for reviewing!
OK. What about if someone relaxes that in the future?
This is actually one of my main concerns ;-) as, IIUC, those barriers are
not only sufficient but also necessary: anything "less than a full barrier"
(in either wake_up_process() or set_current_state()) would _not_ guarantee
the "condition" above unless I'm misunderstanding it.
But am I misunderstanding it? Which barriers/guarantee do you _need_ from
the above mentioned pairing? (hence my comment...)
Andrea
No you are probably not misunderstanding me at all. My comment
originated from the reading of the kerneldoc of set_current_state()
* set_current_state() includes a barrier so that the write of current->state
* is correctly serialised wrt the caller's subsequent test of whether to
* actually sleep:
*
* for (;;) {
* set_current_state(TASK_UNINTERRUPTIBLE);
* if (!need_sleep)
* break;
*
* schedule();
* }
* __set_current_state(TASK_RUNNING);
*
* If the caller does not need such serialisation (because, for instance, the
* condition test and condition change and wakeup are under the same
lock) then
* use __set_current_state().
*
* The above is typically ordered against the wakeup, which does:
*
* need_sleep = false;
* wake_up_state(p, TASK_UNINTERRUPTIBLE);
*
* Where wake_up_state() (and all other wakeup primitives) imply enough
* barriers to order the store of the variable against wakeup. And with
ctx->wounded := !need_sleep this exactly matches what's happening in my
code. So what I was trying to say in the comment was that this above
contract is sufficient to guarantee the "condition" above, whitout me
actually knowing exactly what barriers are required. Thanks, Thomas
___
dri-devel mailing list
dri-devel@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/dri-devel
Re: [PATCH v2 1/2] locking: Implement an algorithm choice for Wound-Wait mutexes
On 06/14/2018 01:36 PM, Peter Zijlstra wrote:
On Thu, Jun 14, 2018 at 09:29:21AM +0200, Thomas Hellstrom wrote:
__ww_mutex_wakeup_for_backoff(struct mutex *lock, struct ww_acquire_ctx
*ww_ctx)
{
struct mutex_waiter *cur;
+ unsigned int is_wait_die = ww_ctx->ww_class->is_wait_die;
lockdep_assert_held(>wait_lock);
@@ -310,13 +348,14 @@ __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 &&
+ if (is_wait_die && 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 (is_wait_die || __ww_mutex_wound(lock, cur->ww_ctx, ww_ctx))
+ break;
}
}
I ended up with:
static void __sched
__ww_mutex_check_waiters(struct mutex *lock, struct ww_acquire_ctx *ww_ctx)
{
bool is_wait_die = ww_ctx->ww_class->is_wait_die;
struct mutex_waiter *cur;
lockdep_assert_held(>wait_lock);
list_for_each_entry(cur, >wait_list, list) {
if (!cur->ww_ctx)
continue;
if (is_wait_die) {
/*
* Because __ww_mutex_add_waiter() and
* __ww_mutex_check_stamp() wake any but the earliest
* context, this can only affect the first waiter (with
* a context).
*/
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_wound(lock, cur->ww_ctx, ww_ctx))
break;
}
}
Looks OK to me.
Currently you don't allow mixing WD and WW contexts (which is not
immediately obvious from the above code), and the above hard relies on
that. Are there sensible use cases for mixing them? IOW will your
current restriction stand without hassle?
Contexts _must_ agree on the algorithm used to resolve deadlocks. With
Wait-Die, for example, older transactions will wait if a lock is held by
a younger transaction and with Wound-Wait, younger transactions will
wait if a lock is held by an older transaction so there is no way of
mixing them.
Thanks,
/Thomas
___
dri-devel mailing list
dri-devel@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/dri-devel
Re: [PATCH v2 1/2] locking: Implement an algorithm choice for Wound-Wait mutexes
On Thu, Jun 14, 2018 at 09:29:21AM +0200, Thomas Hellstrom wrote:
> __ww_mutex_wakeup_for_backoff(struct mutex *lock, struct ww_acquire_ctx
> *ww_ctx)
> {
> struct mutex_waiter *cur;
> + unsigned int is_wait_die = ww_ctx->ww_class->is_wait_die;
>
> lockdep_assert_held(>wait_lock);
>
> @@ -310,13 +348,14 @@ __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 &&
> + if (is_wait_die && 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 (is_wait_die || __ww_mutex_wound(lock, cur->ww_ctx, ww_ctx))
> + break;
> }
> }
I ended up with:
static void __sched
__ww_mutex_check_waiters(struct mutex *lock, struct ww_acquire_ctx *ww_ctx)
{
bool is_wait_die = ww_ctx->ww_class->is_wait_die;
struct mutex_waiter *cur;
lockdep_assert_held(>wait_lock);
list_for_each_entry(cur, >wait_list, list) {
if (!cur->ww_ctx)
continue;
if (is_wait_die) {
/*
* Because __ww_mutex_add_waiter() and
* __ww_mutex_check_stamp() wake any but the earliest
* context, this can only affect the first waiter (with
* a context).
*/
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_wound(lock, cur->ww_ctx, ww_ctx))
break;
}
}
Currently you don't allow mixing WD and WW contexts (which is not
immediately obvious from the above code), and the above hard relies on
that. Are there sensible use cases for mixing them? IOW will your
current restriction stand without hassle?
___
dri-devel mailing list
dri-devel@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/dri-devel
Re: [PATCH v2 1/2] locking: Implement an algorithm choice for Wound-Wait mutexes
On 06/14/2018 12:38 PM, Andrea Parri wrote: Hi Thomas, On Thu, Jun 14, 2018 at 09:29:21AM +0200, Thomas Hellstrom wrote: The current Wound-Wait mutex algorithm is actually not Wound-Wait but Wait-Die. Implement also Wound-Wait as a per-ww-class choice. Wound-Wait is, contrary to Wait-Die a preemptive algorithm and is known to generate fewer backoffs. Testing reveals that this is true if the number of simultaneous contending transactions is small. As the number of simultaneous contending threads increases, Wait-Wound becomes inferior to Wait-Die in terms of elapsed time. Possibly due to the larger number of held locks of sleeping transactions. Update documentation and callers. Timings using git://people.freedesktop.org/~thomash/ww_mutex_test tag patch-18-06-14 Each thread runs 10 batches of lock / unlock 800 ww mutexes randomly chosen out of 10. Four core Intel x86_64: Algorithm#threads Rollbacks time Wound-Wait 4 ~100 ~17s. Wait-Die 4 ~15~19s. Wound-Wait 16 ~36~109s. Wait-Die 16 ~45~82s. Cc: Peter Zijlstra Cc: Ingo Molnar Cc: Jonathan Corbet Cc: Gustavo Padovan Cc: Maarten Lankhorst Cc: Sean Paul Cc: David Airlie Cc: Davidlohr Bueso Cc: "Paul E. McKenney" Cc: Josh Triplett Cc: Thomas Gleixner Cc: Kate Stewart Cc: Philippe Ombredanne Cc: Greg Kroah-Hartman Cc: linux-...@vger.kernel.org Cc: linux-me...@vger.kernel.org Cc: linaro-mm-...@lists.linaro.org Signed-off-by: Thomas Hellstrom --- v2: * Update API according to review comment by Greg Kroah-Hartman. * Address review comments by Peter Zijlstra: - Avoid _Bool in composites - Fix typo - Use __mutex_owner() where applicable - Rely on built-in barriers for the main loop exit condition, struct ww_acquire_ctx::wounded. Update code comments. - Explain unlocked use of list_empty(). --- Documentation/locking/ww-mutex-design.txt | 54 drivers/dma-buf/reservation.c | 2 +- drivers/gpu/drm/drm_modeset_lock.c| 2 +- include/linux/ww_mutex.h | 19 -- kernel/locking/locktorture.c | 2 +- kernel/locking/mutex.c| 103 +++--- kernel/locking/test-ww_mutex.c| 2 +- lib/locking-selftest.c| 2 +- 8 files changed, 156 insertions(+), 30 deletions(-) diff --git a/Documentation/locking/ww-mutex-design.txt b/Documentation/locking/ww-mutex-design.txt index 34c3a1b50b9a..b9597def9581 100644 --- a/Documentation/locking/ww-mutex-design.txt +++ b/Documentation/locking/ww-mutex-design.txt @@ -1,4 +1,4 @@ -Wait/Wound Deadlock-Proof Mutex Design +Wound/Wait Deadlock-Proof Mutex Design == Please read mutex-design.txt first, as it applies to wait/wound mutexes too. @@ -32,10 +32,23 @@ the oldest task) wins, and the one with the higher reservation id (i.e. the younger task) unlocks all of the buffers that it has already locked, and then tries again. -In the RDBMS literature this deadlock handling approach is called wait/wound: -The older tasks waits until it can acquire the contended lock. The younger tasks -needs to back off and drop all the locks it is currently holding, i.e. the -younger task is wounded. +In the RDBMS literature, a reservation ticket is associated with a transaction. +and the deadlock handling approach is called Wait-Die. The name is based on +the actions of a locking thread when it encounters an already locked mutex. +If the transaction holding the lock is younger, the locking transaction waits. +If the transaction holding the lock is older, the locking transaction backs off +and dies. Hence Wait-Die. +There is also another algorithm called Wound-Wait: +If the transaction holding the lock is younger, the locking transaction +preempts the transaction holding the lock, requiring it to back off. It +Wounds the other transaction. +If the transaction holding the lock is older, it waits for the other +transaction. Hence Wound-Wait. +The two algorithms are both fair in that a transaction will eventually succeed. +However, the Wound-Wait algorithm is typically stated to generate fewer backoffs +compared to Wait-Die, but is, on the other hand, associated with more work than +Wait-Die when recovering from a backoff. Wound-Wait is also a preemptive +algorithm which requires a reliable way to preempt another transaction. Concepts @@ -47,10 +60,12 @@ Acquire context: To ensure eventual forward progress it is important the a task trying to acquire locks doesn't grab a new reservation id, but keeps the one it acquired when starting the lock acquisition. This ticket is stored in the acquire context. Furthermore the acquire context keeps track of debugging state -to catch w/w mutex interface abuse. +to catch w/w mutex interface abuse. An acquire context is representing a +transaction.
[PATCH v2 1/2] locking: Implement an algorithm choice for Wound-Wait mutexes
The current Wound-Wait mutex algorithm is actually not Wound-Wait but Wait-Die. Implement also Wound-Wait as a per-ww-class choice. Wound-Wait is, contrary to Wait-Die a preemptive algorithm and is known to generate fewer backoffs. Testing reveals that this is true if the number of simultaneous contending transactions is small. As the number of simultaneous contending threads increases, Wait-Wound becomes inferior to Wait-Die in terms of elapsed time. Possibly due to the larger number of held locks of sleeping transactions. Update documentation and callers. Timings using git://people.freedesktop.org/~thomash/ww_mutex_test tag patch-18-06-14 Each thread runs 10 batches of lock / unlock 800 ww mutexes randomly chosen out of 10. Four core Intel x86_64: Algorithm#threads Rollbacks time Wound-Wait 4 ~100 ~17s. Wait-Die 4 ~15~19s. Wound-Wait 16 ~36~109s. Wait-Die 16 ~45~82s. Cc: Peter Zijlstra Cc: Ingo Molnar Cc: Jonathan Corbet Cc: Gustavo Padovan Cc: Maarten Lankhorst Cc: Sean Paul Cc: David Airlie Cc: Davidlohr Bueso Cc: "Paul E. McKenney" Cc: Josh Triplett Cc: Thomas Gleixner Cc: Kate Stewart Cc: Philippe Ombredanne Cc: Greg Kroah-Hartman Cc: linux-...@vger.kernel.org Cc: linux-me...@vger.kernel.org Cc: linaro-mm-...@lists.linaro.org Signed-off-by: Thomas Hellstrom --- v2: * Update API according to review comment by Greg Kroah-Hartman. * Address review comments by Peter Zijlstra: - Avoid _Bool in composites - Fix typo - Use __mutex_owner() where applicable - Rely on built-in barriers for the main loop exit condition, struct ww_acquire_ctx::wounded. Update code comments. - Explain unlocked use of list_empty(). --- Documentation/locking/ww-mutex-design.txt | 54 drivers/dma-buf/reservation.c | 2 +- drivers/gpu/drm/drm_modeset_lock.c| 2 +- include/linux/ww_mutex.h | 19 -- kernel/locking/locktorture.c | 2 +- kernel/locking/mutex.c| 103 +++--- kernel/locking/test-ww_mutex.c| 2 +- lib/locking-selftest.c| 2 +- 8 files changed, 156 insertions(+), 30 deletions(-) diff --git a/Documentation/locking/ww-mutex-design.txt b/Documentation/locking/ww-mutex-design.txt index 34c3a1b50b9a..b9597def9581 100644 --- a/Documentation/locking/ww-mutex-design.txt +++ b/Documentation/locking/ww-mutex-design.txt @@ -1,4 +1,4 @@ -Wait/Wound Deadlock-Proof Mutex Design +Wound/Wait Deadlock-Proof Mutex Design == Please read mutex-design.txt first, as it applies to wait/wound mutexes too. @@ -32,10 +32,23 @@ the oldest task) wins, and the one with the higher reservation id (i.e. the younger task) unlocks all of the buffers that it has already locked, and then tries again. -In the RDBMS literature this deadlock handling approach is called wait/wound: -The older tasks waits until it can acquire the contended lock. The younger tasks -needs to back off and drop all the locks it is currently holding, i.e. the -younger task is wounded. +In the RDBMS literature, a reservation ticket is associated with a transaction. +and the deadlock handling approach is called Wait-Die. The name is based on +the actions of a locking thread when it encounters an already locked mutex. +If the transaction holding the lock is younger, the locking transaction waits. +If the transaction holding the lock is older, the locking transaction backs off +and dies. Hence Wait-Die. +There is also another algorithm called Wound-Wait: +If the transaction holding the lock is younger, the locking transaction +preempts the transaction holding the lock, requiring it to back off. It +Wounds the other transaction. +If the transaction holding the lock is older, it waits for the other +transaction. Hence Wound-Wait. +The two algorithms are both fair in that a transaction will eventually succeed. +However, the Wound-Wait algorithm is typically stated to generate fewer backoffs +compared to Wait-Die, but is, on the other hand, associated with more work than +Wait-Die when recovering from a backoff. Wound-Wait is also a preemptive +algorithm which requires a reliable way to preempt another transaction. Concepts @@ -47,10 +60,12 @@ Acquire context: To ensure eventual forward progress it is important the a task trying to acquire locks doesn't grab a new reservation id, but keeps the one it acquired when starting the lock acquisition. This ticket is stored in the acquire context. Furthermore the acquire context keeps track of debugging state -to catch w/w mutex interface abuse. +to catch w/w mutex interface abuse. An acquire context is representing a +transaction. W/w class: In contrast to normal mutexes the lock class needs to be explicit for -w/w mutexes, since it is required to initialize the acquire context.
