core: introduce lockdep algorithm

This commit introduces an algorithm that may be used to detect improper
usage of locks at runtime. It can detect two kinds errors:

 1. A thread tries to release a lock it does not own,
 2. A thread tries to aquire a lock and the operation could *potentially*
    result in a deadlock.

The potential deadlock detection assumes that the code adheres to a strict
locking hierarchy, in other word, that there is a partial ordering on the
locks so that there can be no situation where circular waits can occur. To
put things simply, any two locks should be acquired in the same order in
the same thread. This addresses the following case:

  [Thread #1]  [Thread #2]

    lock(A)
                 lock(B)
    lock(B)
                 lock(A) <-- deadlock!
      ...

The algorithm builds the lock hierarchy dynamically and reports as soon as
a violation is detected.

The interface is made of two functions: lockdep_lock_acquire() and
lockdep_lock_release(), which are meant to be introduced in the
implementation of the actual lock objects. The "acquire" hook tells the
algorithm that a particular lock is about to be requested by a particular
thread, while the "release" hook is meant to be called before the lock is
actually released. If an error is detected, debugging information is sent
to the console, and panic() is called. The debugging information includes
the lock cycle that was detected (in the above example, {A, B}), as well
as the call stacks at the points where the locks were acquired.

The good thing with such an instrumentation of the locking code is that
there is no need to wait for an actual deadlock to occur in order to
detect potential problems. For instance, the timing of execution in the
above example could be different but the problem would still be detected:

  [Thread #1]  [Thread #2]

    lock(A)
    lock(B)
    unlock(B)
    unlock(A)
                 lock(B)
                 lock(A) <-- error!

A pseudo-TA is added for testing (pta/core_lockdep_tests.c).

This code is based on two sources:
- A presentation called "Dl-Check: dynamic potential deadlock detection
tool for Java programs" [1], although the somewhat complex MNR algorithm
for topological ordering of a DAG was not used;
- A depth-first search algorithm [2] was used instead.

Link: [1] https://www.slideshare.net/IosifItkin/tmpa2017-dlcheck-dynamic-potential-deadlock-detection-tool-for-java-programs
Link: [2] https://en.wikipedia.org/wiki/Topological_sorting#Depth-first_search
Signed-off-by: Jerome Forissier <jerome.forissier@linaro.org>
Reviewed-by: Joakim Bech <joakim.bech@linaro.org>
Reviewed-by: Etienne Carriere <etienne.carriere@linaro.org>
Acked-by: Jens Wiklander <jens.wiklander@linaro.org>

2 files changed, 413 insertions, 7 deletions

diff --git a/core/kernel/lockdep.c b/core/kernel/lockdep.c
new file mode 100644
index 00000000..7d8b89d3
--- /dev/null
+++ b/core/kernel/lockdep.c
@@ -0,0 +1,405 @@
+// SPDX-License-Identifier: BSD-2-Clause
+/*
+ * Copyright (c) 2018, Linaro Limited
+ */
+
+#include <assert.h>
+#include <kernel/lockdep.h>
+#include <kernel/unwind.h>
+#include <stdlib.h>
+#include <string.h>
+#include <sys/queue.h>
+#include <util.h>
+
+/* lockdep_node::flags values */
+/* Flags used for depth-first topological sorting */
+#define LOCKDEP_NODE_TEMP_MARK		BIT(0)
+#define LOCKDEP_NODE_PERM_MARK		BIT(1)
+/* Flag used during breadth-first search (print shortest cycle) */
+#define LOCKDEP_NODE_BFS_VISITED	BIT(2)
+
+/* Find node in graph or add it */
+static struct lockdep_node *lockdep_add_to_graph(
+				struct lockdep_node_head *graph,
+				uintptr_t lock_id)
+{
+	struct lockdep_node *node = NULL;
+
+	assert(graph);
+	TAILQ_FOREACH(node, graph, link)
+		if (node->lock_id == lock_id)
+			return node;
+
+	node = calloc(1, sizeof(*node));
+	if (!node)
+		return NULL;
+
+	node->lock_id = lock_id;
+	STAILQ_INIT(&node->edges);
+	TAILQ_INSERT_TAIL(graph, node, link);
+
+	return node;
+}
+
+static vaddr_t *dup_call_stack(vaddr_t *stack)
+{
+	if (!stack)
+		return NULL;
+
+	int n = 0;
+
+	while (stack[n])
+		n++;
+
+	vaddr_t *nstack = malloc(n * sizeof(vaddr_t));
+
+	if (!nstack)
+		return NULL;
+	memcpy(nstack, stack, n * sizeof(vaddr_t));
+	return nstack;
+}
+
+static void lockdep_print_call_stack(vaddr_t *stack)
+{
+	vaddr_t *p = NULL;
+
+	EMSG_RAW("Call stack:");
+	for (p = stack; p && *p; p++)
+		EMSG_RAW(" %#" PRIxPTR, *p);
+}
+
+static TEE_Result lockdep_add_edge(struct lockdep_node *from,
+				   struct lockdep_node *to,
+				   vaddr_t *call_stack_from,
+				   vaddr_t *call_stack_to,
+				   uintptr_t thread_id)
+{
+	struct lockdep_edge *edge = NULL;
+
+	STAILQ_FOREACH(edge, &from->edges, link)
+		if (edge->to == to)
+			return TEE_SUCCESS;
+
+	edge = calloc(1, sizeof(*edge));
+	if (!edge)
+		return TEE_ERROR_OUT_OF_MEMORY;
+	edge->to = to;
+	edge->call_stack_from = dup_call_stack(call_stack_from);
+	edge->call_stack_to = dup_call_stack(call_stack_to);
+	edge->thread_id = thread_id;
+	STAILQ_INSERT_TAIL(&from->edges, edge, link);
+
+	return TEE_SUCCESS;
+}
+
+struct lockdep_bfs {
+	struct lockdep_node *node;
+	uintptr_t *path;
+	int pathlen;
+	TAILQ_ENTRY(lockdep_bfs) link;
+};
+
+TAILQ_HEAD(lockdep_bfs_head, lockdep_bfs);
+
+static void lockdep_bfs_queue_delete(struct lockdep_bfs_head *queue)
+{
+	struct lockdep_bfs *cur = NULL;
+	struct lockdep_bfs *next = NULL;
+
+	TAILQ_FOREACH_SAFE(cur, queue, link, next) {
+		TAILQ_REMOVE(queue, cur, link);
+		free(cur->path);
+		free(cur);
+	}
+}
+
+/*
+ * Print shortest cycle in @graph that contains @node.
+ * This function performs an iterative breadth-first search starting from @node,
+ * and stops when it reaches @node again. In each node we're tracking the path
+ * from the start node.
+ */
+static uintptr_t *lockdep_graph_get_shortest_cycle(struct lockdep_node *node)
+{
+	struct lockdep_bfs_head queue;
+	struct lockdep_bfs *qe = NULL;
+	uintptr_t *ret = NULL;
+
+	TAILQ_INIT(&queue);
+	node->flags |= LOCKDEP_NODE_BFS_VISITED;
+
+	qe = calloc(1, sizeof(*qe));
+	if (!qe)
+		goto out;
+	qe->node = node;
+	qe->path = malloc(sizeof(uintptr_t));
+	if (!qe->path)
+		goto out;
+	qe->path[0] = node->lock_id;
+	qe->pathlen = 1;
+	TAILQ_INSERT_TAIL(&queue, qe, link);
+
+	while (!TAILQ_EMPTY(&queue)) {
+		qe = TAILQ_FIRST(&queue);
+
+		struct lockdep_node *n = qe->node;
+
+		TAILQ_REMOVE(&queue, qe, link);
+
+		struct lockdep_edge *e = NULL;
+
+		STAILQ_FOREACH(e, &n->edges, link) {
+			if (e->to->lock_id == node->lock_id) {
+				uintptr_t *tmp = NULL;
+				size_t nlen = qe->pathlen + 1;
+
+				/*
+				 * Cycle found. Terminate cycle path with NULL
+				 * and return it.
+				 */
+				tmp = realloc(qe->path,
+					      nlen * sizeof(uintptr_t));
+				if (!tmp) {
+					EMSG("Out of memory");
+					free(qe->path);
+					ret = NULL;
+					goto out;
+				}
+				qe->path = tmp;
+				qe->path[nlen - 1] = 0;
+				ret = qe->path;
+				goto out;
+			}
+
+			if (!(e->to->flags & LOCKDEP_NODE_BFS_VISITED)) {
+				e->to->flags |= LOCKDEP_NODE_BFS_VISITED;
+
+				size_t nlen = qe->pathlen + 1;
+				struct lockdep_bfs *nqe = calloc(1,
+								 sizeof(*nqe));
+
+				if (!nqe)
+					goto out;
+				nqe->node = e->to;
+				nqe->path = malloc(nlen * sizeof(uintptr_t));
+				if (!nqe->path)
+					goto out;
+				nqe->pathlen = nlen;
+				memcpy(nqe->path, qe->path,
+				       qe->pathlen * sizeof(uintptr_t));
+				nqe->path[nlen - 1] = e->to->lock_id;
+				TAILQ_INSERT_TAIL(&queue, nqe, link);
+			}
+		}
+		free(qe->path);
+		free(qe);
+		qe = NULL;
+	}
+
+out:
+	free(qe);
+	lockdep_bfs_queue_delete(&queue);
+	return ret;
+}
+
+static TEE_Result lockdep_visit(struct lockdep_node *node)
+{
+	if (node->flags & LOCKDEP_NODE_PERM_MARK)
+		return TEE_SUCCESS;
+
+	if (node->flags & LOCKDEP_NODE_TEMP_MARK)
+		return TEE_ERROR_BAD_STATE;	/* Not a DAG! */
+
+	node->flags |= LOCKDEP_NODE_TEMP_MARK;
+
+	struct lockdep_edge *e;
+
+	STAILQ_FOREACH(e, &node->edges, link) {
+		TEE_Result res = lockdep_visit(e->to);
+
+		if (res)
+			return res;
+	}
+
+	node->flags |= LOCKDEP_NODE_PERM_MARK;
+	return TEE_SUCCESS;
+}
+
+static TEE_Result lockdep_graph_sort(struct lockdep_node_head *graph)
+{
+	struct lockdep_node *node = NULL;
+
+	TAILQ_FOREACH(node, graph, link) {
+		if (!node->flags) {
+			/* Unmarked node */
+			TEE_Result res = lockdep_visit(node);
+
+			if (res)
+				return res;
+		}
+	}
+
+	TAILQ_FOREACH(node, graph, link)
+		node->flags = 0;
+
+	return TEE_SUCCESS;
+}
+
+static struct lockdep_edge *lockdep_find_edge(struct lockdep_node_head *graph,
+					      uintptr_t from, uintptr_t to)
+{
+	struct lockdep_node *node = NULL;
+	struct lockdep_edge *edge = NULL;
+
+	TAILQ_FOREACH(node, graph, link)
+		if (node->lock_id == from)
+			STAILQ_FOREACH(edge, &node->edges, link)
+				if (edge->to->lock_id == to)
+					return edge;
+	return NULL;
+}
+
+static void lockdep_print_edge_info(uintptr_t from __maybe_unused,
+				    struct lockdep_edge *edge)
+{
+	uintptr_t __maybe_unused to = edge->to->lock_id;
+
+	EMSG_RAW("-> Thread %#" PRIxPTR " acquired lock %#" PRIxPTR " at:",
+		 edge->thread_id, to);
+	lockdep_print_call_stack(edge->call_stack_to);
+	EMSG_RAW("...while holding lock %#" PRIxPTR " acquired at:",
+		 from);
+	lockdep_print_call_stack(edge->call_stack_from);
+}
+
+/*
+ * Find cycle containing @node in the lock graph, then print full debug
+ * information about each edge (thread that acquired the locks and call stacks)
+ */
+static void lockdep_print_cycle_info(struct lockdep_node_head *graph,
+				     struct lockdep_node *node)
+{
+	struct lockdep_edge *edge = NULL;
+	uintptr_t *cycle = NULL;
+	uintptr_t *p = NULL;
+	uintptr_t from = 0;
+	uintptr_t to = 0;
+
+	cycle = lockdep_graph_get_shortest_cycle(node);
+	assert(cycle && cycle[0]);
+	EMSG_RAW("-> Shortest cycle:");
+	for (p = cycle; *p; p++)
+		EMSG_RAW(" Lock %#" PRIxPTR, *p);
+	for (p = cycle; ; p++) {
+		if (!*p) {
+			assert(p != cycle);
+			from = to;
+			to = cycle[0];
+			edge = lockdep_find_edge(graph, from, to);
+			lockdep_print_edge_info(from, edge);
+			break;
+		}
+		if (p != cycle)
+			from = to;
+		to = *p;
+		if (p != cycle) {
+			edge = lockdep_find_edge(graph, from, to);
+			lockdep_print_edge_info(from, edge);
+		}
+	}
+	free(cycle);
+}
+
+TEE_Result __lockdep_lock_acquire(struct lockdep_node_head *graph,
+				  struct lockdep_lock_head *owned,
+				  uintptr_t id)
+{
+	struct lockdep_node *node = lockdep_add_to_graph(graph, id);
+
+	if (!node)
+		return TEE_ERROR_OUT_OF_MEMORY;
+
+	struct lockdep_lock *lock = NULL;
+	vaddr_t *acq_stack = unw_get_kernel_stack();
+
+	TAILQ_FOREACH(lock, owned, link) {
+		TEE_Result res = lockdep_add_edge(lock->node, node,
+						  lock->call_stack,
+						  acq_stack,
+						  (uintptr_t)owned);
+
+		if (res)
+			return res;
+	}
+
+	TEE_Result res = lockdep_graph_sort(graph);
+
+	if (res) {
+		EMSG_RAW("Potential deadlock detected!");
+		EMSG_RAW("When trying to acquire lock %#" PRIxPTR, id);
+		lockdep_print_cycle_info(graph, node);
+		return res;
+	}
+
+	lock = calloc(1, sizeof(*lock));
+	if (!lock)
+		return TEE_ERROR_OUT_OF_MEMORY;
+
+	lock->node = node;
+	lock->call_stack = acq_stack;
+	TAILQ_INSERT_TAIL(owned, lock, link);
+
+	return TEE_SUCCESS;
+}
+
+TEE_Result __lockdep_lock_release(struct lockdep_lock_head *owned, uintptr_t id)
+{
+	struct lockdep_lock *lock = NULL;
+
+	TAILQ_FOREACH_REVERSE(lock, owned, lockdep_lock_head, link) {
+		if (lock->node->lock_id == id) {
+			TAILQ_REMOVE(owned, lock, link);
+			free(lock->call_stack);
+			free(lock);
+			return TEE_SUCCESS;
+		}
+	}
+
+	EMSG_RAW("Thread %p does not own lock %#" PRIxPTR, (void *)owned, id);
+	return TEE_ERROR_ITEM_NOT_FOUND;
+}
+
+static void lockdep_node_delete(struct lockdep_node *node)
+{
+	struct lockdep_edge *edge = NULL;
+	struct lockdep_edge *next = NULL;
+
+	STAILQ_FOREACH_SAFE(edge, &node->edges, link, next) {
+		free(edge->call_stack_from);
+		free(edge->call_stack_to);
+		free(edge);
+	}
+	free(node);
+}
+
+void lockdep_graph_delete(struct lockdep_node_head *graph)
+{
+	struct lockdep_node *node = NULL;
+	struct lockdep_node *next = NULL;
+
+	TAILQ_FOREACH_SAFE(node, graph, link, next) {
+		TAILQ_REMOVE(graph, node, link);
+		lockdep_node_delete(node);
+	}
+}
+
+void lockdep_queue_delete(struct lockdep_lock_head *owned)
+{
+	struct lockdep_lock *lock = NULL;
+	struct lockdep_lock *next = NULL;
+
+	TAILQ_FOREACH_SAFE(lock, owned, link, next) {
+		TAILQ_REMOVE(owned, lock, link);
+		free(lock);
+	}
+}
diff --git a/core/kernel/sub.mk b/core/kernel/sub.mk
index 41be95ff..5124d968 100644
--- a/core/kernel/sub.mk
+++ b/core/kernel/sub.mk
@@ -1,13 +1,14 @@
+srcs-$(CFG_CORE_SANITIZE_KADDRESS) += asan.c
+cflags-remove-asan.c-y += $(cflags_kasan)
 srcs-y += assert.c
 srcs-y += console.c
 srcs-$(CFG_DT) += dt.c
-srcs-y += msg_param.c
-srcs-y += tee_ta_manager.c
-srcs-y += tee_misc.c
-srcs-y += panic.c
 srcs-y += handle.c
 srcs-y += interrupt.c
-srcs-$(CFG_CORE_SANITIZE_UNDEFINED) += ubsan.c
-srcs-$(CFG_CORE_SANITIZE_KADDRESS) += asan.c
-cflags-remove-asan.c-y += $(cflags_kasan)
+srcs-$(CFG_LOCKDEP) += lockdep.c
+srcs-y += msg_param.c
+srcs-y += panic.c
 srcs-y += refcount.c
+srcs-y += tee_misc.c
+srcs-y += tee_ta_manager.c
+srcs-$(CFG_CORE_SANITIZE_UNDEFINED) += ubsan.c