[Skiboot] [PATCH] core/lock: Add deadlock detection

[Matt Brown]

This adds simple deadlock detection.
The detection looks for circular dependencies in the lock requests.
It will abort and display a stack trace when a deadlock occurs.
The detection will reduce performance so only use for debugging.
To use, enable DEBUG_DEADLOCKS in include/config.h (disabled by default).

Signed-off-by: Matt Brown <matthew.brown.dev at gmail.com>
---
 core/lock.c      | 83 +++++++++++++++++++++++++++++++++++++++++++++++++++++++-
 include/config.h |  3 ++
 include/lock.h   |  5 ++++
 3 files changed, 90 insertions(+), 1 deletion(-)

diff --git a/core/lock.c b/core/lock.c
index e82048b..0379fb0 100644
--- a/core/lock.c
+++ b/core/lock.c
@@ -1,4 +1,4 @@
-/* Copyright 2013-2014 IBM Corp.
+/* Copyright 2013-2017 IBM Corp.
  *
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
@@ -66,6 +66,73 @@ static inline void lock_check(struct lock *l) { };
 static inline void unlock_check(struct lock *l) { };
 #endif /* DEBUG_LOCKS */
 
+#ifdef DEBUG_DEADLOCKS
+
+#define MAX_THREADS 2048
+static struct lock *lock_table[MAX_THREADS];
+
+/* Find circular dependencies in the lock requests. */
+static bool check_deadlock(void)
+{
+	int lock_owner, i, start;
+	struct lock *next;
+
+	start = this_cpu()->pir;
+	next = lock_table[start];
+	i = 0;
+
+	while (i < MAX_THREADS) {
+
+		if (!next)
+			return false;
+
+		if (!(next->lock_val & 1) || next->in_con_path)
+			return false;
+
+		lock_owner = next->lock_val >> 32;
+
+		if (lock_owner >= MAX_THREADS)
+			return false;
+
+		if (lock_owner == start && i > 0)
+			return true;
+
+		next = lock_table[lock_owner];
+		i++;
+	}
+
+	return false;
+}
+
+void add_lock_request(struct lock *l)
+{
+	if (this_cpu()->state == cpu_state_active ||
+	    this_cpu()->state == cpu_state_os) {
+
+		if (this_cpu()->pir >= MAX_THREADS)
+			return;
+
+		lock_table[this_cpu()->pir] = l;
+
+		if (check_deadlock() && check_deadlock()) {
+#ifdef DEBUG_LOCKS
+			lock_error(l, "Deadlock detected", 0);
+#else
+			prlog(PR_EMERG, "LOCK: Deadlock detected\n");
+			backtrace();
+			abort();
+#endif /* DEBUG_LOCKS */
+		}
+	}
+}
+
+void remove_lock_request(void)
+{
+	if (this_cpu()->pir < MAX_THREADS)
+		lock_table[this_cpu()->pir] = NULL;
+}
+#endif /* DEBUG_DEADLOCKS */
+
 bool lock_held_by_me(struct lock *l)
 {
 	uint64_t pir64 = this_cpu()->pir;
@@ -86,15 +153,29 @@ bool try_lock(struct lock *l)
 
 void lock(struct lock *l)
 {
+
 	if (bust_locks)
 		return;
 
 	lock_check(l);
+
+#ifdef DEBUG_DEADLOCKS
+	if (try_lock(l))
+		return;
+
+	add_lock_request(l);
+#endif
+
 	for (;;) {
 		if (try_lock(l))
 			break;
 		cpu_relax();
 	}
+
+#ifdef DEBUG_DEADLOCKS
+	remove_lock_request();
+#endif
+
 }
 
 void unlock(struct lock *l)
diff --git a/include/config.h b/include/config.h
index cd8a0a6..c2f80e9 100644
--- a/include/config.h
+++ b/include/config.h
@@ -39,6 +39,9 @@
 /* Enable lock debugging */
 #define DEBUG_LOCKS		1
 
+/* Enable deadlock detection */
+//#define DEBUG_DEADLOCKS	1
+
 /* Enable malloc debugging */
 #define DEBUG_MALLOC		1
 
diff --git a/include/lock.h b/include/lock.h
index 0ac943d..27bedc7 100644
--- a/include/lock.h
+++ b/include/lock.h
@@ -81,4 +81,9 @@ extern bool lock_recursive(struct lock *l);
 /* Called after per-cpu data structures are available */
 extern void init_locks(void);
 
+#ifdef DEBUG_DEADLOCKS
+extern void add_lock_request(struct lock *l);
+extern void remove_lock_request(void);
+#endif /* DEBUG_DEADLOCKS*/
+
 #endif /* __LOCK_H */
-- 
2.9.3