Initial commit.HEADmaster

Signed-off-by: Thomas Hellstrom <thellstrom@vmware.com>

6 files changed, 1091 insertions, 0 deletions

diff --git a/Makefile b/Makefile
new file mode 100644
index 0000000..16f7b2f
--- /dev/null
+++ b/Makefile
@@ -0,0 +1,13 @@
+wtest-y := ww_mutex_test.o  ww_mutex.o
+
+obj-m += wtest.o
+
+all:
+	make -C /lib/modules/$(shell uname -r)/build M=$(PWD) modules
+
+clean:
+	make -C /lib/modules/$(shell uname -r)/build M=$(PWD) clean
+
+install:
+	cp wtest.ko /lib/modules/$(shell uname -r)/extra
+	depmod -a
diff --git a/README b/README
new file mode 100644
index 0000000..77a732f
--- /dev/null
+++ b/README
@@ -0,0 +1,59 @@
+The ww_mutex_test kernel module
+
+Compile using
+make
+make install
+
+Start a test sequence using
+sudo modprobe wtest
+
+After test sequence use
+sudo rmmod wtest
+
+The test sequence simulates a number of gpu command submissions taking
+ww_mutex_locks. The module maintains a number of global locks and each thread
+is required to lock a local number of locks that are randomly determined from
+the set of global locks. Typically threads will sometimes try to acquire
+the same lock and the ww mutex rollback will be initialized. Defines to
+tune this behaviour (ww_mutex_test.h):
+#define WWT_NUM_LOCKS 100000 /* Number of global locks *
+#define WWT_NUM_T_LOCKS 800  /* Number of locks per thread out of the global */
+#define WWT_NUM_THREADS 16   /* Number of locking threads to fire off */
+
+Each thread performs a number of simulated command submissions with the same
+locks. Each command submission consists of
+*) Taking the locks
+*) Busy-wait for a while (Mimicing time use to submit GPU commands)
+*) Releasing the locks.
+The busy wait makes it more difficult to judge how much time was used for
+the actual locking, but would on the other hand give more real-world-like
+results for the number of rollbacks. Related defines:
+#define WWT_NUM_SUB 10000    /* Number of command submissions */
+#define WWT_CS_UDELAY 000    /* Command submission udelay */
+
+The results can be wiewed as starting and ending time for each thread in
+"dmesg". Each thread also prints the number of rollbacks it had to do.
+There are two ways to have zero rollbacks: One is to fire off the threads
+sequentially in which case there will be no contention. The other one is to
+make sure there are no common locks between threads. Be careful with the latter
+option so that there are enough global locks to accommodate the requests for
+all threads. Otherwise module loading may lock up.
+Related defines:
+#define WWT_NO_SHARED         /* No shared mutexes - No rollbacks */
+#define WWT_SEQUENTIAL        /* Fire off locking threads sequentially */
+
+The module can either use the kernel built-in ww mutex implementation or a
+replacement drop-in implementation. The drop in replacement implements a
+choice of algorithms: Wait-Die and Wound-Wait. It's also possible to batch
+mutex locks and unlocks, significantly reducing the number of locked CPU cycles.
+Note that the drop-in replacement manipulates locking state under a class
+global spinlock instead of the builtin atomic operation manipulation. This
+is slightly slower in cases where the global spinlock is not contended, and
+significantly slower in cases where the global spinlock is contended, but
+it allows for batching locks and unlocks in a single global spinlock
+critical section.
+
+Related defines:
+#define WW_BUILTIN            /* Use kernel builtin ww mutexes */
+#define WW_WAITDIE true       /* Use wait-die, not wound-wait */
+#define WW_BATCHING           /* Batch locks and unlocks */
diff --git a/ww_mutex.c b/ww_mutex.c
new file mode 100644
index 0000000..6858949
--- /dev/null
+++ b/ww_mutex.c
@@ -0,0 +1,583 @@
+/*
+ * Wound/Wait Mutexes: blocking mutual exclusion locks with deadlock avoidance
+ *
+ * Original mutex implementation started by Ingo Molnar:
+ *
+ *  Copyright (C) 2004, 2005, 2006 Red Hat, Inc., Ingo Molnar <mingo@redhat.com>
+ *
+ * Wound/wait implementation:
+ *  Copyright (C) 2013 Canonical Ltd.
+ *
+ * Wound/ wait drop-in, actual wound-wait semantics and batching:
+ *  Copyright (C) 2016-2018 VMWare Inc.
+ */
+
+#include "ww_mutex.h"
+#include <linux/sched/signal.h>
+#include <linux/sched/debug.h>
+
+#ifndef WW_BUILTIN
+
+#undef EXPORT_SYMBOL_GPL
+#define EXPORT_SYMBOL_GPL(_a)
+#define MUTEX_FLAGS		0x07
+
+#ifndef CONFIG_DEBUG_MUTEXES
+#define debug_ww_mutex_add_waiter(_a, _b, _c)
+#define debug_ww_mutex_wake_waiter(_a, _b)
+#define debug_ww_mutex_lock_common(_a, _b)
+#define mutex_remove_waiter(__lock, __waiter, __task) \
+	__list_del((__waiter)->list.prev, (__waiter)->list.next)
+#else
+static void debug_ww_mutex_add_waiter(struct ww_mutex *ww,
+				      struct mutex_waiter *waiter,
+				      struct task_struct *task)
+{
+	SMP_DEBUG_LOCKS_WARN_ON(!spin_is_locked(&ww->my_class->lock));
+	task->blocked_on = waiter;
+}
+
+static void debug_ww_mutex_wake_waiter(struct ww_mutex *ww,
+				       struct mutex_waiter *waiter)
+{
+	struct mutex *lock = &ww->base;
+
+	SMP_DEBUG_LOCKS_WARN_ON(!spin_is_locked(&ww->my_class->lock));
+	DEBUG_LOCKS_WARN_ON(list_empty(&lock->wait_list));
+	DEBUG_LOCKS_WARN_ON(waiter->magic != waiter);
+	DEBUG_LOCKS_WARN_ON(list_empty(&waiter->list));
+}
+
+static void debug_ww_mutex_lock_common(struct ww_mutex *ww,
+				       struct mutex_waiter *waiter)
+{
+	memset(waiter, MUTEX_DEBUG_INIT, sizeof(*waiter));
+	waiter->magic = waiter;
+	INIT_LIST_HEAD(&waiter->list);
+}
+
+static void mutex_remove_waiter(struct mutex *lock, struct mutex_waiter *waiter,
+				struct task_struct *task)
+{
+	DEBUG_LOCKS_WARN_ON(list_empty(&waiter->list));
+	DEBUG_LOCKS_WARN_ON(waiter->task != task);
+	DEBUG_LOCKS_WARN_ON(task->blocked_on != waiter);
+	task->blocked_on = NULL;
+
+	list_del_init(&waiter->list);
+	waiter->task = NULL;
+}
+#endif
+
+
+/**
+ * ww_acquire_class_lock - Lock the global class spinlock unless batching
+ *
+ * @ww: The ww mutex.
+ * @ww_ctx: The acquire context.
+ *
+ * Take the global class spinlock unless we're batching in which case the
+ * global class spinlock was taken during batch begin.
+ */
+static void ww_acquire_class_lock(struct ww_mutex *ww,
+				  struct ww_acquire_ctx *ww_ctx)
+{
+	if (!ww_ctx || !ww_ctx->batched)
+		spin_lock(&ww->my_class->lock);
+}
+
+
+/**
+ * ww_acquire_class_unlock - Unlock the global class spinlock unless batching
+ *
+ * @ww: The ww mutex.
+ * @ww_ctx: The acquire context.
+ *
+ * Free the global class spinlock unless we're batching in which case the
+ * global class spinlock is freed at batch end.
+ */
+static void ww_acquire_class_unlock(struct ww_mutex *ww,
+				    struct ww_acquire_ctx *ww_ctx)
+{
+	if (!ww_ctx || !ww_ctx->batched)
+		spin_unlock(&ww->my_class->lock);
+}
+
+static bool __mutex_waiter_is_first(struct mutex *lock,
+				    struct mutex_waiter *waiter)
+{
+	return list_first_entry(&lock->wait_list, struct mutex_waiter, list) ==
+		waiter;
+}
+
+
+/**
+ * __ww_mutex_trylock - Trylock a ww_mutex
+ *
+ * @ww: The mutex to trylock
+ * @ww_ctx: The acquire_ctx to register as locker or NULL.
+ * @waiter: The waiter if a waiter is trying to lock, or NULL.
+ * Return: true if lock succeeded. false otherwise.
+ */
+static bool __ww_mutex_trylock(struct ww_mutex *ww,
+			       struct ww_acquire_ctx *ww_ctx,
+			       struct mutex_waiter *waiter)
+{
+	struct mutex *lock = &ww->base;
+
+	lockdep_assert_held(&ww->my_class->lock);
+
+	if (atomic_long_read(&lock->owner))
+		return false;
+
+	/*
+	 * No lock stealing for now. If there are waiters, only the first
+	 * waiter is allowed to lock.
+	 */
+	if (!list_empty(&lock->wait_list) &&
+	    !__mutex_waiter_is_first(lock, waiter))
+		return false;
+
+	atomic_long_set(&lock->owner, (unsigned long) current);
+	ww->ctx = ww_ctx;
+	if (ww_ctx)
+		ww_ctx->acquired++;
+
+	return true;
+}
+
+static bool
+__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);
+}
+
+static struct task_struct *__owner_task(unsigned long owner)
+{
+	return (struct task_struct *)(owner & ~MUTEX_FLAGS);
+}
+
+
+/**
+ * ww_mutex_waiter_backoff - Whether to backoff if younger
+ *
+ * @us: Our acquire_ctx.
+ * @other: other waiter or lock owner acquire_ctx.
+ * Return: Whether to back off for another waiter or lock owner if we're
+ * younger than the lock owner or other waiter.
+ */
+static bool ww_mutex_waiter_backoff(struct ww_acquire_ctx *us,
+				    struct ww_acquire_ctx *other)
+{
+  return (us->my_class->is_wait_die || us->wounded) && us->acquired > 0 &&
+	  !other->done_acquire;
+}
+
+
+/**
+ * ww_mutex_backoff - Whether to backoff
+ *
+ * @us: Our acquire_ctx.
+ * @other: other waiter or lock owner acquire_ctx.
+ * Return: Whether to back off for another waiter or lock owner.
+ */
+static bool ww_mutex_backoff(struct ww_acquire_ctx *us,
+			     struct ww_acquire_ctx *other)
+{
+	return other && ww_mutex_waiter_backoff(us, other) &&
+		us != other && __ww_ctx_stamp_after(us, other);
+}
+
+
+/**
+ * ww_mutex_lock_backoff - Check backoff for lock owner and all other waiters.
+ *
+ * @us: Our acquire_ctx.
+ * @ww: The ww_mutex considered.
+ * Return: Whether to back off for any other waiters or lock owner.
+ */
+static bool ww_mutex_lock_backoff(struct ww_acquire_ctx *us,
+				  struct ww_mutex *ww)
+{
+	struct mutex_waiter *cur;
+
+	if (!us)
+		return false;
+
+	/*
+	 * Wounded contexts lazy-preempt before first wounded lock wait, so that
+	 * we have a lock to wait on after backoff.
+	 */
+	if (us->wounded)
+		return true;
+
+	/* Backoff for lock owner? */
+	if (ww_mutex_backoff(us, ww->ctx))
+		return true;
+
+	/* Backoff for other waiters? */
+	list_for_each_entry(cur, &ww->base.wait_list, list) {
+		if (ww_mutex_backoff(us, cur->ww_ctx))
+			return true;
+	}
+
+	return false;
+}
+
+static int
+__ww_mutex_add_waiter(struct mutex_waiter *waiter,
+		      struct ww_mutex *ww,
+		      struct ww_acquire_ctx *ww_ctx)
+{
+	struct mutex *lock = &ww->base;
+	struct mutex_waiter *cur;
+	struct list_head *pos;
+	bool is_wait_die = ww->my_class->is_wait_die;
+
+	waiter->task = current;
+	waiter->ww_ctx = ww_ctx;
+
+	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.
+	 */
+	pos = &lock->wait_list;
+	list_for_each_entry_reverse(cur, &lock->wait_list, list) {
+		if (!cur->ww_ctx)
+			continue;
+
+		/* Early backoff for other waiter */
+		if (__ww_ctx_stamp_after(ww_ctx, cur->ww_ctx)) {
+			if (ww_mutex_waiter_backoff(ww_ctx, cur->ww_ctx))
+				return -EDEADLK;
+
+			break;
+		}
+
+		pos = &cur->list;
+
+		/*
+		 * Other waiter needs to backoff for us.
+		 * Wake up the waiter so that it gets a chance to back
+		 * off.
+		 */
+		if (ww_mutex_waiter_backoff(cur->ww_ctx, ww_ctx)) {
+			debug_ww_mutex_wake_waiter(ww, cur);
+			wake_up_process(cur->task);
+		}
+	}
+
+	list_add_tail(&waiter->list, pos);
+
+	/* Need to wound the lock owner? */
+	if (!is_wait_die && ww->ctx && __ww_ctx_stamp_after(ww->ctx, ww_ctx) &&
+	    ww_ctx->acquired > 0){
+		ww->ctx->wounded = true;
+
+		/*
+		 * Wake up the lock owner in case it's sleeping on
+		 * another ww_mutex..
+		 */
+		wake_up_process(__owner_task(atomic_long_read(&lock->owner)));
+	}
+
+	return 0;
+}
+
+
+/**
+ * ww_mutex_wake_first_waiter - Wake first waiter if any.
+ *
+ * @ww: The ww_mutex on which to wake first waiter.
+ */
+static void ww_mutex_wake_first_waiter(struct ww_mutex *ww)
+{
+	struct mutex_waiter *cur;
+	struct mutex *lock = &ww->base;
+
+	if (!list_empty(&lock->wait_list)) {
+		cur = list_first_entry(&lock->wait_list, struct mutex_waiter,
+				       list);
+		debug_ww_mutex_wake_waiter(ww, cur);
+		wake_up_process(cur->task);
+	}
+}
+
+static int __ww_mutex_lock(struct ww_mutex *ww, long state,
+			   unsigned int subclass,
+			   struct lockdep_map *nest_lock,
+			   unsigned long ip,
+			   struct ww_acquire_ctx *ww_ctx)
+{
+	struct mutex_waiter waiter;
+	int ret = 0;
+
+	lockdep_assert_held(&ww->my_class->lock);
+
+	if (ww_ctx) {
+		/*
+		 * If we've backed off when wounded, there are no more
+		 * acquired locks, and we can clear the wounded flag.
+		 */
+		if (ww_ctx->acquired == 0)
+			ww_ctx->wounded = false;
+
+		if (ww->ctx == ww_ctx) {
+			ret = -EALREADY;
+			goto err_early_backoff;
+		}
+	}
+
+	if (__ww_mutex_trylock(ww, ww_ctx, &waiter))
+		goto skip_wait;
+
+	debug_ww_mutex_lock_common(ww, &waiter);
+	debug_ww_mutex_add_waiter(ww, &waiter, current);
+
+	lock_contended(&ww->base.dep_map, ip);
+
+	ret = __ww_mutex_add_waiter(&waiter, ww, ww_ctx);
+	if (ret)
+		goto err_early_backoff;
+
+	set_current_state(state);
+	for (;;) {
+		if (__ww_mutex_trylock(ww, ww_ctx, &waiter))
+			break;
+
+		if (unlikely(signal_pending_state(state, current))) {
+			ret = -EINTR;
+			goto err;
+		}
+
+		if (ww_mutex_lock_backoff(ww_ctx, ww)) {
+			ret = -EDEADLK;
+			goto err;
+		}
+
+		spin_unlock(&ww->my_class->lock);
+		schedule();
+		spin_lock(&ww->my_class->lock);
+		set_current_state(state);
+	}
+	set_current_state(TASK_RUNNING);
+	mutex_remove_waiter(&ww->base, &waiter, current);
+skip_wait:
+	lock_acquired(&ww->base.dep_map, ip);
+	return 0;
+
+err:
+	set_current_state(TASK_RUNNING);
+	mutex_remove_waiter(&ww->base, &waiter, current);
+	ww_mutex_wake_first_waiter(ww);
+err_early_backoff:
+	lock_release(&ww->base.dep_map, !!ww_ctx, ip);
+	return ret;
+}
+
+static void __ww_mutex_unlock(struct ww_mutex *ww, unsigned long ip)
+{
+	struct mutex *lock = &ww->base;
+
+	lockdep_assert_held(&ww->my_class->lock);
+	lock_release(&lock->dep_map, !!ww->ctx, ip);
+	if (ww->ctx)
+		ww->ctx->acquired--;
+	ww->ctx = NULL;
+	atomic_long_set(&lock->owner, 0);
+	ww_mutex_wake_first_waiter(ww);
+}
+
+#ifdef CONFIG_DEBUG_LOCK_ALLOC
+static int ww_mutex_deadlock_injection(struct ww_mutex *ww,
+				       struct ww_acquire_ctx *ww_ctx)
+{
+#ifdef CONFIG_DEBUG_WW_MUTEX_SLOWPATH
+	unsigned tmp;
+
+	if (ww_ctx->deadlock_inject_countdown-- == 0) {
+		tmp = ww_ctx->deadlock_inject_interval;
+		if (tmp > UINT_MAX/4)
+			tmp = UINT_MAX;
+		else
+			tmp = tmp*2 + tmp + tmp/2;
+
+		ww_ctx->deadlock_inject_interval = tmp;
+		ww_ctx->deadlock_inject_countdown = tmp;
+
+		ww_mutex_unlock(ww);
+
+		return -EDEADLK;
+	}
+
+	return 0;
+#endif /* CONFIG_DEBUG_WW_MUTEX_SLOWPATH */
+}
+
+/**
+ * ww_class_lock_annotate - lockdep annotation at locking time.
+ *
+ * @ww: The ww_mutex
+ * @ww_ctx: The acquire ctx or NULL
+ * @ip: The caller stack
+ */
+static void  ww_class_lock_annotate(struct ww_mutex *ww,
+					   struct ww_acquire_ctx *ww_ctx,
+					   unsigned long ip)
+{
+	if (!ww_ctx || !ww_ctx->batched) {
+		/* Annotate wait lock before the spinlock. */
+		lock_acquire(&ww->base.dep_map, 0, 0, 0, 1,
+			     ww_ctx ? &ww_ctx->dep_map : NULL, ip);
+	} else {
+		/*
+		 * OK, We'd like to annotate ww trylocks under the class
+		 * spinlock, but since each trylock becomes a lockdep level,
+		 * we'd quickly run out of levels. And we can't annotate
+		 * nested trylocks, since apparently lockdep can't cope
+		 * with that. So cheat lockdep and fake a class spinlock
+		 * release and annotate a wating ww lock...
+		 */
+		lock_release(&ww->my_class->lock.dep_map, 0, ip);
+		lock_acquire(&ww->base.dep_map, 0, 0, 0, 1,
+			     &ww_ctx->dep_map, ip);
+		lock_acquire(&ww->my_class->lock.dep_map, 0, 1, 0, 1, NULL, ip);
+	}
+}
+
+int
+ww_mutex_lock(struct ww_mutex *ww, struct ww_acquire_ctx *ww_ctx)
+{
+	int ret;
+
+	ww_class_lock_annotate(ww, ww_ctx, _RET_IP_);
+	ww_acquire_class_lock(ww, ww_ctx);
+	ret =  __ww_mutex_lock(ww, TASK_UNINTERRUPTIBLE,
+			       0, ww_ctx ? &ww_ctx->dep_map : NULL, _RET_IP_,
+			       ww_ctx);
+	ww_acquire_class_unlock(ww, ww_ctx);
+	if (!ret && ww_ctx && ww_ctx->acquired > 1)
+		return ww_mutex_deadlock_injection(ww, ww_ctx);
+
+	return ret;
+}
+EXPORT_SYMBOL_GPL(ww_mutex_lock);
+
+
+int
+ww_mutex_lock_interruptible(struct ww_mutex *ww, struct ww_acquire_ctx *ww_ctx)
+{
+	int ret;
+
+	ww_class_lock_annotate(ww, ww_ctx, _RET_IP_);
+	ww_acquire_class_lock(ww, ww_ctx);
+	ret = __ww_mutex_lock(ww, TASK_INTERRUPTIBLE,
+			      0, ww_ctx ? &ww_ctx->dep_map : NULL, _RET_IP_,
+			      ww_ctx);
+	ww_acquire_class_unlock(ww, ww_ctx);
+	if (!ret && ww_ctx && ww_ctx->acquired > 1)
+		return ww_mutex_deadlock_injection(ww, ww_ctx);
+
+	return ret;
+}
+EXPORT_SYMBOL_GPL(ww_mutex_lock_interruptible);
+
+#else /* CONFIG_DEBUG_LOCK_ALLOC */
+
+int
+ww_mutex_lock(struct ww_mutex *ww, struct ww_acquire_ctx *ww_ctx)
+{
+	int ret;
+
+	ww_acquire_class_lock(ww, ww_ctx);
+	ret = __ww_mutex_lock(ww, TASK_UNINTERRUPTIBLE, 0, NULL, _RET_IP_, ww_ctx);
+	ww_acquire_class_unlock(ww, ww_ctx);
+
+	return ret;
+}
+EXPORT_SYMBOL_GPL(ww_mutex_lock);
+
+
+int
+ww_mutex_lock_interruptible(struct ww_mutex *ww, struct ww_acquire_ctx *ww_ctx)
+{
+	int ret;
+
+	ww_acquire_class_lock(ww, ww_ctx);
+	ret = __ww_mutex_lock(ww, TASK_INTERRUPTIBLE, 0, NULL, _RET_IP_, ww_ctx);
+	ww_acquire_class_unlock(ww, ww_ctx);
+
+	return ret;
+}
+EXPORT_SYMBOL_GPL(ww_mutex_lock_interruptible);
+
+#endif  /* CONFIG_DEBUG_LOCK_ALLOC */
+
+/**
+ * ww_mutex_unlock_batched - Replacement to be used for batched unlock
+ *
+ * @ww: The mutex to unlock
+ */
+void
+ww_mutex_unlock_batched(struct ww_mutex *ww)
+{
+
+	__ww_mutex_unlock(ww, _RET_IP_);
+}
+EXPORT_SYMBOL_GPL(ww_mutex_unlock_batched);
+
+void
+ww_mutex_unlock(struct ww_mutex *ww)
+{
+	struct ww_acquire_ctx *ww_ctx = ww->ctx;
+
+	ww_acquire_class_lock(ww, ww_ctx);
+	__ww_mutex_unlock(ww, _RET_IP_);
+	ww_acquire_class_unlock(ww, ww_ctx);
+}
+EXPORT_SYMBOL_GPL(ww_mutex_unlock);
+
+#ifdef WW_BATCHING
+void  ww_acquire_batch_begin(struct ww_acquire_ctx *ww_ctx)
+{
+#ifdef CONFIG_DEBUG_MUTEXES
+	WARN_ON(ww_ctx->batched);
+#endif
+	spin_lock(&ww_ctx->my_class->lock);
+	ww_ctx->batched = true;
+}
+EXPORT_SYMBOL_GPL(ww_acquire_batch_begin);
+
+void  ww_acquire_batch_end(struct ww_acquire_ctx *ww_ctx)
+{
+#ifdef CONFIG_DEBUG_MUTEXES
+	WARN_ON(!ww_ctx->batched);
+#endif
+	ww_ctx->batched = false;
+	spin_unlock(&ww_ctx->my_class->lock);
+}
+EXPORT_SYMBOL_GPL(ww_acquire_batch_end);
+#endif
+
+int  ww_mutex_trylock(struct ww_mutex *ww)
+{
+	bool locked;
+
+        spin_lock(&ww->my_class->lock);
+	locked = __ww_mutex_trylock(ww, NULL, NULL);
+	spin_unlock(&ww->my_class->lock);
+	if (locked)
+		lock_acquire(&ww->base.dep_map, 0, 1, 0, 1, NULL, _RET_IP_);
+
+	return locked;
+}
+EXPORT_SYMBOL_GPL(ww_mutex_trylock);
+
+#endif
diff --git a/ww_mutex.h b/ww_mutex.h
new file mode 100644
index 0000000..177f107
--- /dev/null
+++ b/ww_mutex.h
@@ -0,0 +1,187 @@
+/*
+ * Wound/Wait Mutexes: blocking mutual exclusion locks with deadlock avoidance
+ *
+ * Original mutex implementation started by Ingo Molnar:
+ *
+ *  Copyright (C) 2004, 2005, 2006 Red Hat, Inc., Ingo Molnar <mingo@redhat.com>
+ *
+ * Wound/wait implementation:
+ *  Copyright (C) 2013 Canonical Ltd.
+ *
+ * Wound/ wait drop-in, actual wound-wait semantics and batching:
+ *  Copyright (C) 2016-2018 VMWare Inc.
+ *
+ * This file contains the main data structure and API definitions.
+ */
+
+#ifndef _WW_MUTEX_H_
+#define _WW_MUTEX_H_
+
+#include "ww_mutex_test.h"
+#include <linux/kernel.h>
+#include <asm/atomic.h>
+#include <linux/sched.h>
+#include <linux/wait.h>
+#include <linux/spinlock.h>
+
+struct ww_class {
+	spinlock_t lock;
+	atomic_long_t stamp;
+	struct lock_class_key acquire_key;
+	struct lock_class_key mutex_key;
+	const char *acquire_name;
+	const char *mutex_name;
+	bool is_wait_die;
+};
+
+struct ww_acquire_ctx {
+	struct ww_class *my_class;
+	unsigned long stamp;
+	unsigned long acquired;
+	u32 batched : 1;
+	u32 wounded : 1;
+	u32 done_acquire : 1;
+#ifdef CONFIG_DEBUG_LOCK_ALLOC
+	struct lockdep_map dep_map;
+	struct lockdep_map batch_map;
+#endif
+#ifdef CONFIG_DEBUG_WW_MUTEX_SLOWPATH
+	unsigned deadlock_inject_interval;
+	unsigned deadlock_inject_countdown;
+#endif
+};
+
+struct ww_mutex {
+	struct mutex base;
+	struct ww_class *my_class;
+	wait_queue_head_t queue;
+	struct ww_acquire_ctx *ctx;
+};
+
+#define __WW_CLASS_INITIALIZER(ww_class) {				\
+		.lock = __SPIN_LOCK_UNLOCKED(ww_class.lock),		\
+			.stamp = ATOMIC_LONG_INIT(0),			\
+			.acquire_name = #ww_class "_acquire",		\
+			.mutex_name = #ww_class "_mutex",		\
+			.is_wait_die = WW_WAITDIE,			\
+}
+
+#define DEFINE_WW_CLASS(classname)			\
+	struct ww_class classname = __WW_CLASS_INITIALIZER(classname)
+
+#ifdef WW_BATCHING
+void ww_acquire_batch_begin(struct ww_acquire_ctx *ctx);
+void ww_acquire_batch_end(struct ww_acquire_ctx *ctx);
+#else
+#define ww_acquire_batch_begin(_a)
+#define ww_acquire_batch_end(_a)
+#endif
+
+static inline void ww_acquire_init(struct ww_acquire_ctx *ctx,
+				   struct ww_class *ww_class)
+{
+	ctx->my_class = ww_class;
+	ctx->stamp = atomic_long_inc_return(&ww_class->stamp);
+	ctx->acquired = 0L;
+	ctx->batched = false;
+	ctx->wounded = false;
+	ctx->done_acquire = 0;
+#ifdef CONFIG_DEBUG_LOCK_ALLOC
+	lockdep_init_map(&ctx->dep_map, ww_class->acquire_name,
+			 &ww_class->acquire_key, 0);
+	lockdep_init_map(&ctx->batch_map, ww_class->mutex_name,
+			 &ww_class->mutex_key, 0);
+	lock_acquire(&ctx->dep_map, 0, 0, 0, 1, NULL, _RET_IP_);
+	lock_acquired(&ctx->dep_map, _RET_IP_);
+#endif
+#ifdef CONFIG_DEBUG_WW_MUTEX_SLOWPATH
+	ctx->deadlock_inject_interval = 1L;
+	ctx->deadlock_inject_countdown = ctx->stamp & 0x0f;
+#endif
+}
+
+/**
+ * ww_acquire_done - marks the end of the acquire phase
+ * @ctx: the acquire context
+ *
+ * Marks the end of the acquire phase, any further w/w mutex lock calls using
+ * this context are forbidden.
+ *
+ * Calling this function is optional, it is just useful to document w/w mutex
+ * code and clearly designated the acquire phase from actually using the locked
+ * data structures.
+ */
+static inline void ww_acquire_done(struct ww_acquire_ctx *ctx)
+{
+#ifdef CONFIG_DEBUG_MUTEXES
+	lockdep_assert_held(ctx);
+
+	WARN_ON(ctx->batched);
+	DEBUG_LOCKS_WARN_ON(ctx->done_acquire);
+#endif
+	ctx->done_acquire = 1;
+}
+
+/**
+ * ww_acquire_fini - releases a w/w acquire context
+ * @ctx: the acquire context to free
+ *
+ * Releases a w/w acquire context. This must be called _after_ all acquired w/w
+ * mutexes have been released with ww_mutex_unlock.
+ */
+static inline void ww_acquire_fini(struct ww_acquire_ctx *ctx)
+{
+#ifdef CONFIG_DEBUG_LOCK_ALLOC
+	lock_release(&ctx->dep_map, 0, _THIS_IP_);
+#endif
+#ifdef CONFIG_DEBUG_MUTEXES
+	DEBUG_LOCKS_WARN_ON(ctx->acquired);
+	if (!IS_ENABLED(CONFIG_PROVE_LOCKING))
+		/*
+		 * lockdep will normally handle this,
+		 * but fail without anyway
+		 */
+		ctx->done_acquire = 1;
+
+	if (!IS_ENABLED(CONFIG_DEBUG_LOCK_ALLOC))
+		/* ensure ww_acquire_fini will still fail if called twice */
+		ctx->acquired = ~0U;
+#endif
+}
+
+
+static inline void ww_mutex_init(struct ww_mutex *ww,
+				 struct ww_class *ww_class)
+{
+  ww->my_class = ww_class;
+  ww->ctx = NULL;
+  init_waitqueue_head(&ww->queue);
+  mutex_init(&ww->base);
+}
+
+static inline bool ww_mutex_is_locked(struct ww_mutex *ww)
+{
+	return mutex_is_locked(&ww->base);
+}
+
+int ww_mutex_trylock(struct ww_mutex *lock);
+
+int ww_mutex_lock_interruptible(struct ww_mutex *lock,
+				struct ww_acquire_ctx *ctx);
+
+#define ww_mutex_lock_slow_interruptible ww_mutex_lock_interruptible
+
+int ww_mutex_lock(struct ww_mutex *lock,
+		  struct ww_acquire_ctx *ctx);
+
+#define ww_mutex_lock_slow ww_mutex_lock
+
+void ww_mutex_unlock(struct ww_mutex *lock);
+
+static inline void ww_mutex_destroy(struct ww_mutex *lock)
+{
+	mutex_destroy(&lock->base);
+}
+
+
+#endif
diff --git a/ww_mutex_test.c b/ww_mutex_test.c
new file mode 100644
index 0000000..8ebfdc9
--- /dev/null
+++ b/ww_mutex_test.c
@@ -0,0 +1,229 @@
+/*
+ * Wound/Wait Mutex testing module.
+ *  Copyright (C) 2016-2018 VMWare Inc.
+ */
+
+#include "ww_mutex_test.h"
+
+#ifdef WW_BUILTIN
+#include <linux/ww_mutex.h>
+#define ww_acquire_batch_begin(_a)
+#define ww_acquire_batch_end(_a)
+#else
+#include "ww_mutex.h"
+#endif
+
+#include <linux/init.h>
+#include <linux/module.h>
+#include <linux/kernel.h>
+#include <linux/printk.h>
+#include <linux/random.h>
+#include <linux/delay.h>
+
+MODULE_LICENSE("GPL");
+MODULE_AUTHOR("Thomas Hellström");
+MODULE_DESCRIPTION("Test module for ww_mutex performance");
+MODULE_VERSION("1.0.0");
+
+struct ww_mutex_item  {
+	struct ww_mutex mutex;
+	/* Align to a typical cache line */
+	u8 pad[64 - sizeof(struct ww_mutex) % 64];
+};
+
+struct wwt_device {
+	struct ww_mutex_item *locks;
+	int *used;
+	int num_locks;
+};
+
+struct wwt_thread {
+	struct wwt_device *dev;
+	struct ww_mutex **p_locks;
+	u8 *used;
+	int num_locks;
+	int thread;
+	u32 num_rollbacks;
+	struct work_struct work;
+};
+
+
+
+
+static struct wwt_device g_dev;
+static struct wwt_thread threads[WWT_NUM_THREADS];
+static DEFINE_WW_CLASS(wwt_class);
+
+static void wwt_thread_rollback(struct wwt_thread *t, int upto)
+{
+	while(upto--)
+		ww_mutex_unlock(t->p_locks[upto]);
+	t->num_rollbacks++;
+}
+
+static int wwt_thread_lock_sequence(struct wwt_thread *t)
+{
+	struct ww_acquire_ctx ctx;
+	int ret = 0;
+	int i;
+
+	ww_acquire_init(&ctx, &wwt_class);
+	ww_acquire_batch_begin(&ctx);
+restart:
+	for (i = 0; i < t->num_locks; ++i) {
+		ret = ww_mutex_lock(t->p_locks[i], &ctx);
+		if (ret) {
+			WARN_ON(i == 0);
+			wwt_thread_rollback(t, i);
+			if (ret == -EDEADLK) {
+				swap(t->p_locks[0], t->p_locks[i]);
+				goto restart;
+			} else
+				goto out_err;
+		}
+	}
+	ww_acquire_batch_end(&ctx);
+	ww_acquire_done(&ctx);
+
+	udelay(WWT_CS_UDELAY);
+
+	ww_acquire_batch_begin(&ctx);
+	wwt_thread_rollback(t, t->num_locks);
+	t->num_rollbacks--;
+out_err:
+	ww_acquire_batch_end(&ctx);
+	ww_acquire_fini(&ctx);
+	return ret;
+}
+
+static void wwt_lock_work(struct work_struct *work) {
+	struct wwt_thread *t = container_of(work, struct wwt_thread, work);
+	int i, ret;
+
+	printk(KERN_INFO "thread %d: Starting work.\n", t->thread);
+	for (i = 0; i < WWT_NUM_SUB; ++i) {
+		ret = wwt_thread_lock_sequence(t);
+		if (ret)
+			break;
+	}
+
+	printk(KERN_INFO "thread %d; Fininshed with %u rollbacks. ret is %d\n",
+	       t->thread, t->num_rollbacks, ret);
+}
+
+
+static int wwt_thread_setup(struct wwt_thread *t, int thread)
+{
+	struct wwt_device *dev = &g_dev;
+	u32 idx;
+	int i;
+
+	t->dev = dev;
+	t->p_locks = vmalloc(WWT_NUM_T_LOCKS * sizeof(*t->p_locks));
+	t->num_rollbacks = 0;
+	t->thread = thread;
+	INIT_WORK(&t->work, wwt_lock_work);
+#ifndef WWT_NO_SHARED
+	memset(dev->used, 0, dev->num_locks * sizeof(*dev->used));
+#endif
+	if (!t->p_locks)
+		return -ENOMEM;
+
+	for (i = 0; i < WWT_NUM_T_LOCKS; ++i) {
+		get_random_bytes(&idx, sizeof(idx));
+		idx %= WWT_NUM_LOCKS;
+		while(dev->used[idx]) {
+			idx++;
+			idx %= WWT_NUM_LOCKS;
+		}
+		dev->used[idx] = 1;
+		t->p_locks[i] = &dev->locks[idx].mutex;
+	}
+	t->num_locks = WWT_NUM_T_LOCKS;
+
+	return 0;
+}
+
+static void wwt_thread_destroy(struct wwt_thread *t)
+{
+	cancel_work_sync(&t->work);
+	if (t->p_locks)
+		vfree(t->p_locks);
+}
+
+static void wwt_device_fini(struct wwt_device *wdev)
+{
+	int i;
+
+	if (wdev->used)
+		vfree(wdev->used);
+
+	for (i = 0; i < ARRAY_SIZE(threads); ++i)
+		wwt_thread_destroy(&threads[i]);
+
+	for (i = 0; i < wdev->num_locks; ++i)
+		ww_mutex_destroy(&wdev->locks[i].mutex);
+
+	vfree(wdev->locks);
+	wdev->num_locks = 0;
+}
+
+
+static int wwt_device_init(struct wwt_device *wdev, int num_locks)
+{
+	int i, ret;
+
+	wdev->num_locks = 0;
+	wdev->locks = vzalloc(num_locks * sizeof(*wdev->locks));
+	if (!wdev->locks)
+		return -ENOMEM;
+
+	wdev->used = vzalloc(num_locks * sizeof(*wdev->used));
+	if (!wdev->locks)
+		goto out_thread_setup;
+
+	for (i = 0; i < num_locks; ++i)
+		ww_mutex_init(&wdev->locks[i].mutex, &wwt_class);
+
+	wdev->num_locks = num_locks;
+
+	printk(KERN_INFO "Allocated %d mutexes. Alignment is %lu %lu\n",
+	       num_locks, ((unsigned long) wdev->locks) % 64,
+	       sizeof(struct ww_mutex));
+
+	for (i = 0; i < ARRAY_SIZE(threads); ++i) {
+		ret = wwt_thread_setup(&threads[i], i);
+		if (ret)
+			goto out_thread_setup;
+	}
+
+	printk(KERN_INFO "Set up %lu threads\n", ARRAY_SIZE(threads));
+	usleep_range(10000, 20000);
+	for (i = 0; i < ARRAY_SIZE(threads); ++i) {
+#ifndef WWT_SEQUENTIAL
+	  queue_work(system_unbound_wq, &threads[i].work);
+#else
+	  wwt_lock_work(&threads[i].work);
+#endif
+	}
+
+	return 0;
+
+out_thread_setup:
+	wwt_device_fini(&g_dev);
+	return ret;
+}
+
+static int __init wwt_init(void) {
+
+	printk(KERN_INFO "Hello, World!\n");
+	return wwt_device_init(&g_dev, WWT_NUM_LOCKS);
+}
+
+static void __exit wwt_exit(void) {
+	wwt_device_fini(&g_dev);
+	printk(KERN_INFO "Goodbye, World!\n");
+}
+
+module_init(wwt_init);
+module_exit(wwt_exit);
diff --git a/ww_mutex_test.h b/ww_mutex_test.h
new file mode 100644
index 0000000..8911ea7
--- /dev/null
+++ b/ww_mutex_test.h
@@ -0,0 +1,20 @@
+/*
+ * Wound/Wait Mutex testing module.
+ *  Copyright (C) 2016-2018 VMWare Inc.
+ */
+
+#ifndef _WW_MUTEX_TEST_H_
+#define _WW_MUTEX_TEST_H_
+
+#undef WW_BUILTIN            /* Use kernel builtin ww mutexes */
+#define WW_WAITDIE true      /* Use wait-die, not wound-wait */
+#define WW_BATCHING          /* Batch locks and unlocks */
+#define WWT_NUM_LOCKS 100000  /* Number of global locks */
+#define WWT_NUM_T_LOCKS 800  /* Number of locks per thread out of the global */
+#define WWT_NUM_THREADS 16    /* Number of locking threads to fire off */
+#undef WWT_SEQUENTIAL        /* Fire off locking threads sequentially */
+#define WWT_CS_UDELAY 000    /* Command submission udelay */
+#define WWT_NUM_SUB 10000    /* Number of command submissions */
+#undef WWT_NO_SHARED         /* No shared mutexes - No rollbacks */
+
+#endif