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>

1 files changed, 5 insertions, 0 deletions

diff --git a/lib/libutee/include/pta_invoke_tests.h b/lib/libutee/include/pta_invoke_tests.h
index 234a6bc7..9653bd9b 100644
--- a/lib/libutee/include/pta_invoke_tests.h
+++ b/lib/libutee/include/pta_invoke_tests.h
@@ -68,5 +68,10 @@
 #define PTA_MUTEX_TEST_READER			1
 #define PTA_INVOKE_TESTS_CMD_MUTEX		7
 
+/*
+ * Tests lock dependency checking algorithm
+ */
+#define PTA_INVOKE_TESTS_CMD_LOCKDEP		8
+
 #endif /*__PTA_INVOKE_TESTS_H*/