Re: [PATCH 1/2] locking: Implement an algorithm choice for Wound-Wait mutexes
On 06/14/2018 08:51 PM, Peter Zijlstra wrote: On Thu, Jun 14, 2018 at 06:43:40PM +0200, Thomas Hellstrom wrote: 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. Thanks! Are you OK with adding the new feature and the cleanup in the same patch? I suppose so, trying to untangle that will be a bit of a pain. But if you feel so inclined I'm not going to stop you :-) OK, I did some untangling. Sending out the resulting two patches. There are very minor changes in comments and naming, mostly trying to avoid "wound" where we really mean "die". The only functional change is that I've moved the waiter-wounding-owner path to *after* we actually set the FLAG_WAITER so that we make sure a valid owner pointer remains valid while we hold the spinlock. This also means we can replace an smp_mb() with smp_mb__after_atomic(). Sending the patches as separate emails. Please let me know if you're OK with them and also the author / co-author info, and if so, I'll send out the full series again. Thanks, /Thomas ___ dri-devel mailing list dri-devel@lists.freedesktop.org https://lists.freedesktop.org/mailman/listinfo/dri-devel
Re: [PATCH 1/2] locking: Implement an algorithm choice for Wound-Wait mutexes
On Thu, Jun 14, 2018 at 06:43:40PM +0200, Thomas Hellstrom wrote: > 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. Thanks! > Are you OK with adding the new feature and the cleanup in the same patch? I suppose so, trying to untangle that will be a bit of a pain. But if you feel so inclined I'm not going to stop you :-) ___ dri-devel mailing list dri-devel@lists.freedesktop.org https://lists.freedesktop.org/mailman/listinfo/dri-devel
Re: [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(_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.
Re: [PATCH 1/2] locking: Implement an algorithm choice for Wound-Wait mutexes
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.
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(_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 -
Re: [PATCH 1/2] locking: Implement an algorithm choice for Wound-Wait mutexes
On 06/14/2018 12:51 PM, Peter Zijlstra wrote:
On Wed, Jun 13, 2018 at 04:05:43PM +0200, Thomas Hellstrom wrote:
In short, with Wait-Die (before the patch) it's the process _taking_ the
contended lock that backs off if necessary. No preemption required. With
Wound-Wait, it's the process _holding_ the contended lock that gets wounded
(preempted), and it needs to back off at its own discretion but no later
than when it's going to sleep on another ww mutex. That point is where we
intercept the preemption request. We're preempting the transaction rather
than the process.
This:
Wait-die:
The newer transactions are killed when:
It (= the newer transaction) makes a reqeust for a lock being held
by an older transactions
Wound-wait:
The newer transactions are killed when:
An older transaction makes a request for a lock being held by the
newer transactions
Would make for an excellent comment somewhere. No talking about
preemption, although I think I know what you mean with it, that is not
how preemption is normally used.
Ok. I'll incorporate something along this line. Unfortunately that last
statement is not fully true. It should read
"The newer transactions are wounded when:", not "killed" when.
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.
In scheduling speak preemption is when we pick a runnable (but !running)
task to run instead of the current running task. In this case however,
our T2 is blocked on a lock acquisition (one owned by our T1) and T1 is
the only runnable task. Only when T1's progress is inhibited by T2 (T1
wants a lock held by T2) do we wound/wake T2.
Indeed. The preemption spoken about in the Wound-Wait litterature means
that a transaction preempts another transaction when it wounds it. In
distributed computing my understanding is that the preempted transaction
is aborted instantly and restarted after a random delay. Of course, we
have no means of mapping wounding to process preemption in the linux
kernel, so that's why I referred to it as "lazy preemption". In process
analogy "wounded" wound roughly correspond to (need_resched() == true),
and returning -EDEADLK would correspond to voluntary preemption.
In any case, I had a little look at the current ww_mutex code and ended
up with the below patch that hopefully clarifies things a little.
---
diff --git a/kernel/locking/mutex.c b/kernel/locking/mutex.c
index f44f658ae629..a20c04619b2a 100644
--- a/kernel/locking/mutex.c
+++ b/kernel/locking/mutex.c
@@ -244,6 +244,10 @@ void __sched mutex_lock(struct mutex *lock)
EXPORT_SYMBOL(mutex_lock);
#endif
+/*
+ * Associate the ww_mutex @ww with the context @ww_ctx under which we acquired
+ * it.
+ */
IMO use of "acquire_context" or "context" is a little unfortunate when
the literature uses "transaction",
but otherwise fine.
static __always_inline void
ww_mutex_lock_acquired(struct ww_mutex *ww, struct ww_acquire_ctx *ww_ctx)
{
@@ -282,26 +286,36 @@ 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++;
+ lock->ctx = ctx;
}
+/*
+ * Determine if context @a is 'after' context @b. IOW, @a should be wounded in
+ * favour of @b.
+ */
So "wounded" should never really be used with Wait-Die
"Determine whether context @a represents a younger transaction than
context @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.
+ * We just acquired @lock under @ww_ctx, if there are later contexts waiting
+ * behind us on the wait-list, wake them up so they can wound themselves.
Actually for Wait-Die, Back off or "Die" is the correct terminology.
*
- * Due to the invariants on the wait list, this can only affect the first
- * waiter with a context.
+ * See __ww_mutex_add_waiter() for the list-order construction; basically the
+ * list is ordered by stamp smallest (oldest) first, so if there is a later
+ * (younger) stamp on the list behind us, wake it so it can wound itself.
+ *
+ * Because __ww_mutex_add_waiter() and __ww_mutex_check_stamp() wake any
+ * but the earliest
Re: [PATCH 1/2] locking: Implement an algorithm choice for Wound-Wait mutexes
On Wed, Jun 13, 2018 at 04:05:43PM +0200, Thomas Hellstrom wrote:
> In short, with Wait-Die (before the patch) it's the process _taking_ the
> contended lock that backs off if necessary. No preemption required. With
> Wound-Wait, it's the process _holding_ the contended lock that gets wounded
> (preempted), and it needs to back off at its own discretion but no later
> than when it's going to sleep on another ww mutex. That point is where we
> intercept the preemption request. We're preempting the transaction rather
> than the process.
This:
Wait-die:
The newer transactions are killed when:
It (= the newer transaction) makes a reqeust for a lock being held
by an older transactions
Wound-wait:
The newer transactions are killed when:
An older transaction makes a request for a lock being held by the
newer transactions
Would make for an excellent comment somewhere. No talking about
preemption, although I think I know what you mean with it, that is not
how preemption is normally used.
In scheduling speak preemption is when we pick a runnable (but !running)
task to run instead of the current running task. In this case however,
our T2 is blocked on a lock acquisition (one owned by our T1) and T1 is
the only runnable task. Only when T1's progress is inhibited by T2 (T1
wants a lock held by T2) do we wound/wake T2.
In any case, I had a little look at the current ww_mutex code and ended
up with the below patch that hopefully clarifies things a little.
---
diff --git a/kernel/locking/mutex.c b/kernel/locking/mutex.c
index f44f658ae629..a20c04619b2a 100644
--- a/kernel/locking/mutex.c
+++ b/kernel/locking/mutex.c
@@ -244,6 +244,10 @@ void __sched mutex_lock(struct mutex *lock)
EXPORT_SYMBOL(mutex_lock);
#endif
+/*
+ * 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 +286,36 @@ 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++;
+ lock->ctx = 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.
+ * We just acquired @lock under @ww_ctx, if there are later contexts waiting
+ * behind us on the wait-list, wake them up so they can wound themselves.
*
- * Due to the invariants on the wait list, this can only affect the first
- * waiter with a context.
+ * See __ww_mutex_add_waiter() for the list-order construction; basically the
+ * list is ordered by stamp smallest (oldest) first, so if there is a later
+ * (younger) stamp on the list behind us, wake it so it can wound itself.
+ *
+ * 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).
*
* 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_wakeup_for_wound(struct mutex *lock, struct ww_acquire_ctx *ww_ctx)
{
struct mutex_waiter *cur;
@@ -322,16 +336,14 @@ __ww_mutex_wakeup_for_backoff(struct mutex *lock, struct
ww_acquire_ctx *ww_ctx)
}
/*
- * 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
@@ -352,25 +364,10 @@ ww_mutex_set_context_fastpath(struct ww_mutex *lock,
struct ww_acquire_ctx *ctx)
* so they can see the new lock->ctx.
*/
spin_lock(>base.wait_lock);
- __ww_mutex_wakeup_for_backoff(>base, ctx);
+ __ww_mutex_wakeup_for_wound(>base, ctx);
spin_unlock(>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
Re: [PATCH 1/2] locking: Implement an algorithm choice for Wound-Wait mutexes
On 06/13/2018 03:10 PM, Peter Zijlstra wrote:
On Wed, Jun 13, 2018 at 12:40:29PM +0200, Thomas Hellstrom wrote:
On 06/13/2018 11:50 AM, Peter Zijlstra wrote:
+
+ lockdep_assert_held(>wait_lock);
+
+ if (owner && hold_ctx && __ww_ctx_stamp_after(hold_ctx, ww_ctx) &&
+ ww_ctx->acquired > 0) {
+ WRITE_ONCE(hold_ctx->wounded, true);
+ if (owner != current) {
+ /*
+* wake_up_process() inserts a write memory barrier to
It does no such thing. But yes, it does ensure the wakee sees all prior
stores IFF the wakeup happened.
+* make sure owner sees it is wounded before
+* TASK_RUNNING in case it's sleeping on another
+* ww_mutex. Note that owner points to a valid
+* task_struct as long as we hold the wait_lock.
+*/
What exactly are you trying to say here ?
I'm thinking this is the pairing barrier to the smp_mb() below, with
your list_empty() thing? Might make sense to write a single coherent
comment and refer to the other location.
So what I'm trying to say here is that wake_up_process() ensures that the
owner, if in !TASK_RUNNING, sees the write to hold_ctx->wounded before the
transition to TASK_RUNNING. This was how I interpreted "woken up" in the
wake up process documentation.
There is documentation!? :-) Aaah, you mean that kerneldoc comment with
wake_up_process() ? Yeah, that needs fixing. /me puts on endless todo
list.
Anyway, wakeup providing that ordering isn't something that needs a
comment of that size; and I think the only comment here is that we care
about the ordering and a reference to the site(s) that pairs with it.
Maybe something like:
/*
* __ww_mutex_lock_check_stamp() will observe our wounded store.
*/
Yes.
Actually, I just found the set_current_state() kerneldoc which explains
the built-in barrier pairing with wake_up_xxx. Perhaps I also should
mention that as well. Looks like the use WRITE_ONCE() and READ_ONCE()
can be dropped as well.
- if (likely(!(atomic_long_read(>base.owner) & MUTEX_FLAG_WAITERS)))
+ if (likely(list_empty(>base.wait_list)))
return;
/*
@@ -653,6 +695,17 @@ __ww_mutex_lock_check_stamp(struct mutex *lock, struct
mutex_waiter *waiter,
struct ww_acquire_ctx *hold_ctx = READ_ONCE(ww->ctx);
struct mutex_waiter *cur;
+ /*
+* If we miss a wounded == true here, we will have a pending
Explain how we can miss that.
This is actually the pairing location of the wake_up_process() comment /
code discussed above. Here we should have !TASK_RUNNING, and let's say
ctx->wounded is set by another process immediately after we've read it (we
"miss" it). At that point there must be a pending wake-up-process() for us
and we'll pick up the set value of wounded on the next iteration after
returning from schedule().
Right, so that's when the above wakeup isn't the one waking us.
I can't say I'm a fan. I'm already cursing the ww_mutex stuff every time
I have to look at it, and you just made it worse spagethi.
Well, I can't speak for the current ww implementation except I didn't think
it was too hard to understand for a first time reader.
Admittedly the Wound-Wait path makes it worse since it's a preemptive
algorithm and we need to touch other processes a acquire contexts and worry
about ordering.
So, assuming your review comments are fixed up, is that a solid NAK or do
you have any suggestion that would make you more comfortable with the code?
like splitting out ww-stuff to a separate file?
Nah, not a NAK, but we should look at whan can be done to improve code.
Maybe add a few more comments that explain why. Part of the problem with
ww_mutex is always that I forget exactly how they work and mutex.c
doesn't have much useful comments in (most of those are in ww_mutex.h
and I always forget to look there).
Understood.
Also; I'm not at all sure about the exact difference between what we
have and what you propose. I did read the documentation part (I really
should not have to) but it just doesn't jive.
I suspect you're using preemption entirely different from what we
usually call a preemption.
I think that perhaps requires a good understanding of the difference of
the algorithms in question before looking at the implementation. I put a
short explanation and some URLs to CS websites describing the two
algorithms and their pros and cons in the patch series introductory
message. I'll forward that.
In short, with Wait-Die (before the patch) it's the process _taking_ the
contended lock that backs off if necessary. No preemption required. With
Wound-Wait, it's the process _holding_ the contended lock that gets
wounded (preempted), and it needs to back off at its own discretion but
no later than when it's going to sleep on another ww mutex. That point
is where
Re: [PATCH 1/2] locking: Implement an algorithm choice for Wound-Wait mutexes
On Wed, Jun 13, 2018 at 12:40:29PM +0200, Thomas Hellstrom wrote:
> On 06/13/2018 11:50 AM, Peter Zijlstra wrote:
> >
> > > +
> > > + lockdep_assert_held(>wait_lock);
> > > +
> > > + if (owner && hold_ctx && __ww_ctx_stamp_after(hold_ctx, ww_ctx) &&
> > > + ww_ctx->acquired > 0) {
> > > + WRITE_ONCE(hold_ctx->wounded, true);
> > > + if (owner != current) {
> > > + /*
> > > + * wake_up_process() inserts a write memory barrier to
> > It does no such thing. But yes, it does ensure the wakee sees all prior
> > stores IFF the wakeup happened.
> >
> > > + * make sure owner sees it is wounded before
> > > + * TASK_RUNNING in case it's sleeping on another
> > > + * ww_mutex. Note that owner points to a valid
> > > + * task_struct as long as we hold the wait_lock.
> > > + */
> > What exactly are you trying to say here ?
> >
> > I'm thinking this is the pairing barrier to the smp_mb() below, with
> > your list_empty() thing? Might make sense to write a single coherent
> > comment and refer to the other location.
>
> So what I'm trying to say here is that wake_up_process() ensures that the
> owner, if in !TASK_RUNNING, sees the write to hold_ctx->wounded before the
> transition to TASK_RUNNING. This was how I interpreted "woken up" in the
> wake up process documentation.
There is documentation!? :-) Aaah, you mean that kerneldoc comment with
wake_up_process() ? Yeah, that needs fixing. /me puts on endless todo
list.
Anyway, wakeup providing that ordering isn't something that needs a
comment of that size; and I think the only comment here is that we care
about the ordering and a reference to the site(s) that pairs with it.
Maybe something like:
/*
* __ww_mutex_lock_check_stamp() will observe our wounded store.
*/
> > > - if (likely(!(atomic_long_read(>base.owner) & MUTEX_FLAG_WAITERS)))
> > > + if (likely(list_empty(>base.wait_list)))
> > > return;
> > > /*
> > > @@ -653,6 +695,17 @@ __ww_mutex_lock_check_stamp(struct mutex *lock,
> > > struct mutex_waiter *waiter,
> > > struct ww_acquire_ctx *hold_ctx = READ_ONCE(ww->ctx);
> > > struct mutex_waiter *cur;
> > > + /*
> > > + * If we miss a wounded == true here, we will have a pending
> > Explain how we can miss that.
>
> This is actually the pairing location of the wake_up_process() comment /
> code discussed above. Here we should have !TASK_RUNNING, and let's say
> ctx->wounded is set by another process immediately after we've read it (we
> "miss" it). At that point there must be a pending wake-up-process() for us
> and we'll pick up the set value of wounded on the next iteration after
> returning from schedule().
Right, so that's when the above wakeup isn't the one waking us.
> > I can't say I'm a fan. I'm already cursing the ww_mutex stuff every time
> > I have to look at it, and you just made it worse spagethi.
> Well, I can't speak for the current ww implementation except I didn't think
> it was too hard to understand for a first time reader.
>
> Admittedly the Wound-Wait path makes it worse since it's a preemptive
> algorithm and we need to touch other processes a acquire contexts and worry
> about ordering.
>
> So, assuming your review comments are fixed up, is that a solid NAK or do
> you have any suggestion that would make you more comfortable with the code?
> like splitting out ww-stuff to a separate file?
Nah, not a NAK, but we should look at whan can be done to improve code.
Maybe add a few more comments that explain why. Part of the problem with
ww_mutex is always that I forget exactly how they work and mutex.c
doesn't have much useful comments in (most of those are in ww_mutex.h
and I always forget to look there).
Also; I'm not at all sure about the exact difference between what we
have and what you propose. I did read the documentation part (I really
should not have to) but it just doesn't jive.
I suspect you're using preemption entirely different from what we
usually call a preemption.
Also, __ww_ctx_stamp_after() is crap; did we want to write:
return (signed long)(a->stamp - b->stamp) > 0;
or something?
___
dri-devel mailing list
dri-devel@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/dri-devel
Re: [PATCH 1/2] locking: Implement an algorithm choice for Wound-Wait mutexes
On 06/13/2018 11:50 AM, Peter Zijlstra wrote:
+
+ lockdep_assert_held(>wait_lock);
+
+ if (owner && hold_ctx && __ww_ctx_stamp_after(hold_ctx, ww_ctx) &&
+ ww_ctx->acquired > 0) {
+ WRITE_ONCE(hold_ctx->wounded, true);
+ if (owner != current) {
+ /*
+* wake_up_process() inserts a write memory barrier to
It does no such thing. But yes, it does ensure the wakee sees all prior
stores IFF the wakeup happened.
+* make sure owner sees it is wounded before
+* TASK_RUNNING in case it's sleeping on another
+* ww_mutex. Note that owner points to a valid
+* task_struct as long as we hold the wait_lock.
+*/
What exactly are you trying to say here ?
I'm thinking this is the pairing barrier to the smp_mb() below, with
your list_empty() thing? Might make sense to write a single coherent
comment and refer to the other location.
So what I'm trying to say here is that wake_up_process() ensures that
the owner, if in !TASK_RUNNING, sees the write to hold_ctx->wounded
before the transition to TASK_RUNNING. This was how I interpreted "woken
up" in the wake up process documentation.
+ wake_up_process(owner);
+ }
+ return true;
+ }
+
+ return false;
+}
+
/*
* Wake up any waiters that may have to back off when the lock is held by the
* given context.
*
* Due to the invariants on the wait list, this can only affect the first
- * waiter with a context.
+ * waiter with a context, unless the Wound-Wait algorithm is used where
+ * also subsequent waiters with a context main wound the lock holder.
*
* The current task must not be on the wait list.
*/
@@ -303,6 +338,7 @@ static void __sched
__ww_mutex_wakeup_for_backoff(struct mutex *lock, struct ww_acquire_ctx
*ww_ctx)
{
struct mutex_waiter *cur;
+ bool is_wait_die = ww_ctx->ww_class->is_wait_die;
lockdep_assert_held(>wait_lock);
@@ -310,13 +346,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;
}
}
@@ -338,12 +375,17 @@ 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.
+* Checking MUTEX_FLAG_WAITERS is not enough here,
That seems like a superfluous thing to say. It makes sense in the
context of this patch because we change the FLAG check into a list
check, but the resulting comment/code looks odd.
since we need to
+* order against the lock->ctx check in __ww_mutex_wound called from
+* __ww_mutex_add_waiter. We can use list_empty without taking the
+* wait_lock, given the memory barrier above and the list_empty
+* documentation.
I don't trust documentation. Please reason about implementation.
Will do.
*/
- if (likely(!(atomic_long_read(>base.owner) & MUTEX_FLAG_WAITERS)))
+ if (likely(list_empty(>base.wait_list)))
return;
/*
@@ -653,6 +695,17 @@ __ww_mutex_lock_check_stamp(struct mutex *lock, struct
mutex_waiter *waiter,
struct ww_acquire_ctx *hold_ctx = READ_ONCE(ww->ctx);
struct mutex_waiter *cur;
+ /*
+* If we miss a wounded == true here, we will have a pending
Explain how we can miss that.
This is actually the pairing location of the wake_up_process() comment /
code discussed above. Here we should have !TASK_RUNNING, and let's say
ctx->wounded is set by another process immediately after we've read it
(we "miss" it). At that point there must be a pending wake-up-process()
for us and we'll pick up the set value of wounded on the next iteration
after returning from schedule().
+* TASK_RUNNING and pick it up on the next schedule fall-through.
+*/
+ if (!ctx->ww_class->is_wait_die) {
+ if (READ_ONCE(ctx->wounded))
+ goto deadlock;
+ else
+ return 0;
Re: [PATCH 1/2] locking: Implement an algorithm choice for Wound-Wait mutexes
/me wonders what's up with partial Cc's today..
On Wed, Jun 13, 2018 at 09:47:44AM +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-04
>
> 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.
> diff --git a/include/linux/ww_mutex.h b/include/linux/ww_mutex.h
> index 39fda195bf78..6278077f288b 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,15 +25,17 @@ struct ww_class {
> struct lock_class_key mutex_key;
> const char *acquire_name;
> const char *mutex_name;
> + bool is_wait_die;
> };
No _Bool in composites please.
> struct ww_acquire_ctx {
> struct task_struct *task;
> unsigned long stamp;
> unsigned acquired;
> + bool wounded;
Again.
> + struct ww_class *ww_class;
> #ifdef CONFIG_DEBUG_MUTEXES
> unsigned done_acquire;
> - struct ww_class *ww_class;
> struct ww_mutex *contending_lock;
> #endif
> #ifdef CONFIG_DEBUG_LOCK_ALLOC
> diff --git a/kernel/locking/mutex.c b/kernel/locking/mutex.c
> index 2048359f33d2..b449a012c6f9 100644
> --- a/kernel/locking/mutex.c
> +++ b/kernel/locking/mutex.c
> @@ -290,12 +290,47 @@ __ww_ctx_stamp_after(struct ww_acquire_ctx *a, struct
> ww_acquire_ctx *b)
> (a->stamp != b->stamp || a > b);
> }
>
> +/*
> + * Wound the lock holder transaction if it's younger than the contending
> + * transaction, and there is a possibility of a deadlock.
> + * Also if the lock holder transaction isn't the current transaction,
Comma followed by a capital?
> + * Make sure it's woken up in case it's sleeping on another ww mutex.
> + */
> +static bool __ww_mutex_wound(struct mutex *lock,
> + struct ww_acquire_ctx *ww_ctx,
> + struct ww_acquire_ctx *hold_ctx)
> +{
> + struct task_struct *owner =
> + __owner_task(atomic_long_read(>owner));
Did you just spell __mutex_owner() wrong?
> +
> + lockdep_assert_held(>wait_lock);
> +
> + if (owner && hold_ctx && __ww_ctx_stamp_after(hold_ctx, ww_ctx) &&
> + ww_ctx->acquired > 0) {
> + WRITE_ONCE(hold_ctx->wounded, true);
> + if (owner != current) {
> + /*
> + * wake_up_process() inserts a write memory barrier to
It does no such thing. But yes, it does ensure the wakee sees all prior
stores IFF the wakeup happened.
> + * make sure owner sees it is wounded before
> + * TASK_RUNNING in case it's sleeping on another
> + * ww_mutex. Note that owner points to a valid
> + * task_struct as long as we hold the wait_lock.
> + */
What exactly are you trying to say here ?
I'm thinking this is the pairing barrier to the smp_mb() below, with
your list_empty() thing? Might make sense to write a single coherent
comment and refer to the other location.
> + wake_up_process(owner);
> + }
> + return true;
> + }
> +
> + return false;
> +}
> +
> /*
> * Wake up any waiters that may have to back off when the lock is held by the
> * given context.
> *
> * Due to the invariants on the wait list, this can only affect the first
> - * waiter with a context.
> + * waiter with a context, unless the Wound-Wait algorithm is used where
> + * also subsequent waiters with a context main wound the lock holder.
> *
> * The current task must not be on the wait list.
> */
> @@ -303,6 +338,7 @@ static void __sched
> __ww_mutex_wakeup_for_backoff(struct mutex *lock, struct ww_acquire_ctx
> *ww_ctx)
> {
> struct mutex_waiter *cur;
> + bool is_wait_die = ww_ctx->ww_class->is_wait_die;
>
> lockdep_assert_held(>wait_lock);
>
> @@ -310,13 +346,14
Re: [PATCH 1/2] locking: Implement an algorithm choice for Wound-Wait mutexes
On 06/13/2018 09:54 AM, Greg Kroah-Hartman wrote: On Wed, Jun 13, 2018 at 09:47:44AM +0200, Thomas Hellstrom wrote: - +The algorithm (Wait-Die vs Wound-Wait) is chosen using the _is_wait_die +argument to DEFINE_WW_CLASS(). As a rough rule of thumb, use Wound-Wait iff you +typically expect the number of simultaneous competing transactions to be small, +and the rollback cost can be substantial. + Three different ways to acquire locks within the same w/w class. Common definitions for methods #1 and #2: -static DEFINE_WW_CLASS(ww_class); +static DEFINE_WW_CLASS(ww_class, false); Minor nit on the api here. Having a "flag" is a royal pain. You have to go and look up exactly what that "true/false" means every time you run across it in code to figure out what it means. Don't do that if at all possible. Make a new api: DEFINE_WW_CLASS_DIE(ww_class); instead that then wraps that boolean internally to switch between the different types. That way the api is "self-documenting" and we all know what is going on without having to dig through a header file. thanks, greg k-h Good point. I'll update in a v2. Thanks, Thomas ___ dri-devel mailing list dri-devel@lists.freedesktop.org https://lists.freedesktop.org/mailman/listinfo/dri-devel
Re: [PATCH 1/2] locking: Implement an algorithm choice for Wound-Wait mutexes
On Wed, Jun 13, 2018 at 09:47:44AM +0200, Thomas Hellstrom wrote: > - > > +The algorithm (Wait-Die vs Wound-Wait) is chosen using the _is_wait_die > +argument to DEFINE_WW_CLASS(). As a rough rule of thumb, use Wound-Wait iff > you > +typically expect the number of simultaneous competing transactions to be > small, > +and the rollback cost can be substantial. > + > Three different ways to acquire locks within the same w/w class. Common > definitions for methods #1 and #2: > > -static DEFINE_WW_CLASS(ww_class); > +static DEFINE_WW_CLASS(ww_class, false); Minor nit on the api here. Having a "flag" is a royal pain. You have to go and look up exactly what that "true/false" means every time you run across it in code to figure out what it means. Don't do that if at all possible. Make a new api: DEFINE_WW_CLASS_DIE(ww_class); instead that then wraps that boolean internally to switch between the different types. That way the api is "self-documenting" and we all know what is going on without having to dig through a header file. thanks, greg k-h ___ dri-devel mailing list dri-devel@lists.freedesktop.org https://lists.freedesktop.org/mailman/listinfo/dri-devel
[PATCH 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-04 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 --- Documentation/locking/ww-mutex-design.txt | 57 ++ 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| 98 --- kernel/locking/test-ww_mutex.c| 2 +- lib/locking-selftest.c| 2 +- 8 files changed, 152 insertions(+), 32 deletions(-) diff --git a/Documentation/locking/ww-mutex-design.txt b/Documentation/locking/ww-mutex-design.txt index 34c3a1b50b9a..29c85623b551 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. +w/w mutexes, since it is required to initialize the acquire context. The lock +class also specifies what algorithm to use, Wound-Wait or Wait-Die. Furthermore there are three different class of w/w lock acquire functions: @@ -90,10 +105,15 @@ provided. Usage - +The algorithm (Wait-Die vs Wound-Wait) is chosen using the _is_wait_die +argument to
