Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > linux.kernel > #1534122
| From | Nicolai Hähnle <nhaehnle@gmail.com> |
|---|---|
| Newsgroups | linux.kernel |
| Subject | [PATCH v2 05/11] locking/ww_mutex: Add waiters in stamp order |
| Date | 2016-12-01 15:10 +0100 |
| Message-ID | <sJAdI-4Rh-33@gated-at.bofh.it> (permalink) |
| References | <sJAdI-4Rh-7@gated-at.bofh.it> |
| Organization | linux.* mail to news gateway |
From: Nicolai Hähnle <Nicolai.Haehnle@amd.com>
Add regular waiters in stamp order. Keep adding waiters that have no
context in FIFO order and take care not to starve them.
While adding our task as a waiter, back off if we detect that there is a
waiter with a lower stamp in front of us.
Make sure to call lock_contended even when we back off early.
v2:
- rein in the indentation of __ww_mutex_add_waiter a bit
- set contending_lock in __ww_mutex_add_waiter (Chris Wilson)
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Ingo Molnar <mingo@redhat.com>
Cc: Maarten Lankhorst <dev@mblankhorst.nl>
Cc: Daniel Vetter <daniel@ffwll.ch>
Cc: Chris Wilson <chris@chris-wilson.co.uk>
Cc: dri-devel@lists.freedesktop.org
Signed-off-by: Nicolai Hähnle <Nicolai.Haehnle@amd.com>
---
include/linux/mutex.h | 3 ++
kernel/locking/mutex.c | 87 ++++++++++++++++++++++++++++++++++++++++++++++----
2 files changed, 83 insertions(+), 7 deletions(-)
diff --git a/include/linux/mutex.h b/include/linux/mutex.h
index b97870f..118a3b6 100644
--- a/include/linux/mutex.h
+++ b/include/linux/mutex.h
@@ -20,6 +20,8 @@
#include <linux/osq_lock.h>
#include <linux/debug_locks.h>
+struct ww_acquire_ctx;
+
/*
* Simple, straightforward mutexes with strict semantics:
*
@@ -75,6 +77,7 @@ static inline struct task_struct *__mutex_owner(struct mutex *lock)
struct mutex_waiter {
struct list_head list;
struct task_struct *task;
+ struct ww_acquire_ctx *ww_ctx;
#ifdef CONFIG_DEBUG_MUTEXES
void *magic;
#endif
diff --git a/kernel/locking/mutex.c b/kernel/locking/mutex.c
index 585627f..d63eebb 100644
--- a/kernel/locking/mutex.c
+++ b/kernel/locking/mutex.c
@@ -628,6 +628,51 @@ __ww_mutex_lock_check_stamp(struct mutex *lock, struct ww_acquire_ctx *ctx)
return 0;
}
+static inline int __sched
+__ww_mutex_add_waiter(struct mutex_waiter *waiter,
+ struct mutex *lock,
+ struct ww_acquire_ctx *ww_ctx)
+{
+ struct mutex_waiter *cur;
+
+ if (!ww_ctx) {
+ list_add_tail(&waiter->list, &lock->wait_list);
+ return 0;
+ }
+
+ /*
+ * Add the waiter before the first waiter with a higher stamp.
+ * Waiters without a context are skipped to avoid starving
+ * them.
+ */
+ list_for_each_entry(cur, &lock->wait_list, list) {
+ if (!cur->ww_ctx)
+ continue;
+
+ if (__ww_mutex_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;
+ }
+
+ continue;
+ }
+
+ list_add_tail(&waiter->list, &cur->list);
+ return 0;
+ }
+
+ list_add_tail(&waiter->list, &lock->wait_list);
+ return 0;
+}
+
/*
* Lock a mutex (possibly interruptible), slowpath:
*/
@@ -677,15 +722,25 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass,
debug_mutex_lock_common(lock, &waiter);
debug_mutex_add_waiter(lock, &waiter, task);
- /* add waiting tasks to the end of the waitqueue (FIFO): */
- list_add_tail(&waiter.list, &lock->wait_list);
+ lock_contended(&lock->dep_map, ip);
+
+ if (!use_ww_ctx) {
+ /* add waiting tasks to the end of the waitqueue (FIFO): */
+ list_add_tail(&waiter.list, &lock->wait_list);
+ } else {
+ /* Add in stamp order, waking up waiters that must back off. */
+ ret = __ww_mutex_add_waiter(&waiter, lock, ww_ctx);
+ if (ret)
+ goto err_early_backoff;
+
+ waiter.ww_ctx = ww_ctx;
+ }
+
waiter.task = task;
if (__mutex_waiter_is_first(lock, &waiter))
__mutex_set_flag(lock, MUTEX_FLAG_WAITERS);
- lock_contended(&lock->dep_map, ip);
-
set_task_state(task, state);
for (;;) {
/*
@@ -693,8 +748,12 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass,
* mutex_unlock() handing the lock off to us, do a trylock
* before testing the error conditions to make sure we pick up
* the handoff.
+ *
+ * For w/w locks, we always need to do this even if we're not
+ * currently the first waiter, because we may have been the
+ * first waiter during the unlock.
*/
- if (__mutex_trylock(lock, first))
+ if (__mutex_trylock(lock, use_ww_ctx || first))
goto acquired;
/*
@@ -716,7 +775,20 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass,
spin_unlock_mutex(&lock->wait_lock, flags);
schedule_preempt_disabled();
- if (!first && __mutex_waiter_is_first(lock, &waiter)) {
+ if (use_ww_ctx && ww_ctx) {
+ /*
+ * Always re-check whether we're in first position. We
+ * don't want to spin if another task with a lower
+ * stamp has taken our position.
+ *
+ * We also may have to set the handoff flag again, if
+ * our position at the head was temporarily taken away.
+ */
+ first = __mutex_waiter_is_first(lock, &waiter);
+
+ if (first)
+ __mutex_set_flag(lock, MUTEX_FLAG_HANDOFF);
+ } else if (!first && __mutex_waiter_is_first(lock, &waiter)) {
first = true;
__mutex_set_flag(lock, MUTEX_FLAG_HANDOFF);
}
@@ -728,7 +800,7 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass,
* or we must see its unlock and acquire.
*/
if ((first && mutex_optimistic_spin(lock, ww_ctx, use_ww_ctx, true)) ||
- __mutex_trylock(lock, first))
+ __mutex_trylock(lock, use_ww_ctx || first))
break;
spin_lock_mutex(&lock->wait_lock, flags);
@@ -761,6 +833,7 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass,
err:
__set_task_state(task, TASK_RUNNING);
mutex_remove_waiter(lock, &waiter, task);
+err_early_backoff:
spin_unlock_mutex(&lock->wait_lock, flags);
debug_mutex_free_waiter(&waiter);
mutex_release(&lock->dep_map, 1, ip);
--
2.7.4
Back to linux.kernel | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
[PATCH v2 00/11] locking/ww_mutex: Keep sorted wait list to avoid stampedes Nicolai Hähnle <nhaehnle@gmail.com> - 2016-12-01 15:10 +0100
[PATCH v2 05/11] locking/ww_mutex: Add waiters in stamp order Nicolai Hähnle <nhaehnle@gmail.com> - 2016-12-01 15:10 +0100
Re: [PATCH v2 05/11] locking/ww_mutex: Add waiters in stamp order Chris Wilson <chris@chris-wilson.co.uk> - 2016-12-01 17:10 +0100
Re: [PATCH v2 05/11] locking/ww_mutex: Add waiters in stamp order Peter Zijlstra <peterz@infradead.org> - 2016-12-06 16:40 +0100
Re: [PATCH v2 05/11] locking/ww_mutex: Add waiters in stamp order Peter Zijlstra <peterz@infradead.org> - 2016-12-06 18:00 +0100
[PATCH v2 07/11] locking/ww_mutex: Wake at most one waiter for back off when acquiring the lock Nicolai Hähnle <nhaehnle@gmail.com> - 2016-12-01 15:10 +0100
[PATCH v2 10/11] Documentation/locking/ww_mutex: Update the design document Nicolai Hähnle <nhaehnle@gmail.com> - 2016-12-01 15:10 +0100
[PATCH v2 09/11] locking/mutex: Initialize mutex_waiter::ww_ctx with poison when debugging Nicolai Hähnle <nhaehnle@gmail.com> - 2016-12-01 15:10 +0100
[PATCH v2 02/11] locking/ww_mutex: Re-check ww->ctx in the inner optimistic spin loop Nicolai Hähnle <nhaehnle@gmail.com> - 2016-12-01 15:10 +0100
Re: [PATCH v2 02/11] locking/ww_mutex: Re-check ww->ctx in the inner optimistic spin loop Chris Wilson <chris@chris-wilson.co.uk> - 2016-12-01 15:40 +0100
Re: [PATCH v2 02/11] locking/ww_mutex: Re-check ww->ctx in the inner optimistic spin loop Peter Zijlstra <peterz@infradead.org> - 2016-12-06 16:10 +0100
Re: [PATCH v2 02/11] locking/ww_mutex: Re-check ww->ctx in the inner optimistic spin loop Waiman Long <longman@redhat.com> - 2016-12-06 17:10 +0100
Re: [PATCH v2 02/11] locking/ww_mutex: Re-check ww->ctx in the inner optimistic spin loop Waiman Long <longman@redhat.com> - 2016-12-06 19:50 +0100
Re: [PATCH v2 02/11] locking/ww_mutex: Re-check ww->ctx in the inner optimistic spin loop Peter Zijlstra <peterz@infradead.org> - 2016-12-06 20:10 +0100
[PATCH v2 01/11] drm/vgem: Use ww_mutex_(un)lock even with a NULL context Nicolai Hähnle <nhaehnle@gmail.com> - 2016-12-01 15:10 +0100
Re: [PATCH v2 01/11] drm/vgem: Use ww_mutex_(un)lock even with a NULL context Chris Wilson <chris@chris-wilson.co.uk> - 2016-12-01 15:20 +0100
Re: [PATCH v2 01/11] drm/vgem: Use ww_mutex_(un)lock even with a NULL context Daniel Vetter <daniel@ffwll.ch> - 2016-12-01 16:20 +0100
Re: [PATCH v2 01/11] drm/vgem: Use ww_mutex_(un)lock even with a NULL context Peter Zijlstra <peterz@infradead.org> - 2016-12-01 17:30 +0100
[PATCH v2 11/11] [rfc] locking/ww_mutex: Always spin optimistically for the first waiter Nicolai Hähnle <nhaehnle@gmail.com> - 2016-12-01 15:10 +0100
[PATCH v2 06/11] locking/ww_mutex: Notify waiters that have to back off while adding tasks to wait list Nicolai Hähnle <nhaehnle@gmail.com> - 2016-12-01 15:10 +0100
csiph-web