mutex: Add w/w mutex slowpath debugging

Injects EDEADLK conditions at pseudo-random interval, with
exponential backoff up to UINT_MAX (to ensure that every lock
operation still completes in a reasonable time).

This way we can test the wound slowpath even for ww mutex users
where contention is never expected, and the ww deadlock
avoidance algorithm is only needed for correctness against
malicious userspace. An example would be protecting kernel
modesetting properties, which thanks to single-threaded X isn't
really expected to contend, ever.

I've looked into using the CONFIG_FAULT_INJECTION
infrastructure, but decided against it for two reasons:

- EDEADLK handling is mandatory for ww mutex users and should
  never affect the outcome of a syscall. This is in contrast to -ENOMEM
  injection. So fine configurability isn't required.

- The fault injection framework only allows to set a simple
  probability for failure. Now the probability that a ww mutex acquire
  stage with N locks will never complete (due to too many injected
  EDEADLK backoffs) is zero. But the expected number of ww_mutex_lock
  operations for the completely uncontended case would be O(exp(N)).
  The per-acuiqire ctx exponential backoff solution choosen here only
  results in O(log N) overhead due to injection and so O(log N * N)
  lock operations. This way we can fail with high probability (and so
  have good test coverage even for fancy backoff and lock acquisition
  paths) without running into patalogical cases.

Note that EDEADLK will only ever be injected when we managed to
acquire the lock. This prevents any behaviour changes for users
which rely on the EALREADY semantics.

Signed-off-by: Daniel Vetter <daniel.vetter@ffwll.ch>
Signed-off-by: Maarten Lankhorst <maarten.lankhorst@canonical.com>
Acked-by: Peter Zijlstra <a.p.zijlstra@chello.nl>
Cc: dri-devel@lists.freedesktop.org
Cc: linaro-mm-sig@lists.linaro.org
Cc: rostedt@goodmis.org
Cc: daniel@ffwll.ch
Cc: Linus Torvalds <torvalds@linux-foundation.org>
Cc: Andrew Morton <akpm@linux-foundation.org>
Cc: Thomas Gleixner <tglx@linutronix.de>
Link: http://lkml.kernel.org/r/20130620113117.4001.21681.stgit@patser
Signed-off-by: Ingo Molnar <mingo@kernel.org>

1 files changed, 41 insertions, 3 deletions

diff --git a/kernel/mutex.c b/kernel/mutex.c
index fc801aafe8fd..e581ada5faf4 100644
--- a/kernel/mutex.c
+++ b/kernel/mutex.c
@@ -651,22 +651,60 @@ mutex_lock_interruptible_nested(struct mutex *lock, unsigned int subclass)
 
 EXPORT_SYMBOL_GPL(mutex_lock_interruptible_nested);
 
+static inline int
+ww_mutex_deadlock_injection(struct ww_mutex *lock, struct ww_acquire_ctx *ctx)
+{
+#ifdef CONFIG_DEBUG_WW_MUTEX_SLOWPATH
+        unsigned tmp;
+
+        if (ctx->deadlock_inject_countdown-- == 0) {
+                tmp = ctx->deadlock_inject_interval;
+                if (tmp > UINT_MAX/4)
+                        tmp = UINT_MAX;
+                else
+                        tmp = tmp*2 + tmp + tmp/2;
+
+                ctx->deadlock_inject_interval = tmp;
+                ctx->deadlock_inject_countdown = tmp;
+                ctx->contending_lock = lock;
+
+                ww_mutex_unlock(lock);
+
+                return -EDEADLK;
+        }
+#endif
+
+        return 0;
+}
 
 int __sched
 __ww_mutex_lock(struct ww_mutex *lock, struct ww_acquire_ctx *ctx)
 {
+        int ret;
+
         might_sleep();
-        return __mutex_lock_common(&lock->base, TASK_UNINTERRUPTIBLE,
+        ret =  __mutex_lock_common(&lock->base, TASK_UNINTERRUPTIBLE,
                                    0, &ctx->dep_map, _RET_IP_, ctx);
+        if (!ret && ctx->acquired > 0)
+                return ww_mutex_deadlock_injection(lock, ctx);
+
+        return ret;
 }
 EXPORT_SYMBOL_GPL(__ww_mutex_lock);
 
 int __sched
 __ww_mutex_lock_interruptible(struct ww_mutex *lock, struct ww_acquire_ctx *ctx)
 {
+        int ret;
+
         might_sleep();
-        return __mutex_lock_common(&lock->base, TASK_INTERRUPTIBLE,
-                                   0, &ctx->dep_map, _RET_IP_, ctx);
+        ret = __mutex_lock_common(&lock->base, TASK_INTERRUPTIBLE,
+                                  0, &ctx->dep_map, _RET_IP_, ctx);
+
+        if (!ret && ctx->acquired > 0)
+                return ww_mutex_deadlock_injection(lock, ctx);
+
+        return ret;
 }
 EXPORT_SYMBOL_GPL(__ww_mutex_lock_interruptible);