core: Fix warnings in core/kernel/lockdep.c

Fixes -Wdeclaration-after-statement warnings in core/kernel/lockdep.c:
core/kernel/lockdep.c: In function 'lockdep_graph_get_shortest_cycle':
core/kernel/

core: Fix warnings in core/kernel/lockdep.c

Fixes -Wdeclaration-after-statement warnings in core/kernel/lockdep.c:
core/kernel/lockdep.c: In function 'lockdep_graph_get_shortest_cycle':
core/kernel/lockdep.c:151:3: error: ISO C90 forbids mixed declarations and code [-Werror=declaration-after-statement]
struct lockdep_node *n = qe->node;
^~~~~~
core/kernel/lockdep.c:155:3: error: ISO C90 forbids mixed declarations and code [-Werror=declaration-after-statement]
struct lockdep_edge *e = NULL;
^~~~~~
core/kernel/lockdep.c:183:5: error: ISO C90 forbids mixed declarations and code [-Werror=declaration-after-statement]
size_t nlen = qe->pathlen + 1;
^~~~~~
core/kernel/lockdep.c: In function 'lockdep_visit':
core/kernel/lockdep.c:221:2: error: ISO C90 forbids mixed declarations and code [-Werror=declaration-after-statement]
struct lockdep_edge *e;
^~~~~~
core/kernel/lockdep.c: In function '__lockdep_lock_acquire':
core/kernel/lockdep.c:343:2: error: ISO C90 forbids mixed declarations and code [-Werror=declaration-after-statement]
struct lockdep_lock *lock = NULL;
^~~~~~
core/kernel/lockdep.c:356:2: error: ISO C90 forbids mixed declarations and code [-Werror=declaration-after-statement]
TEE_Result res = lockdep_graph_sort(graph);
^~~~~~~~~~
core/kernel/lockdep.c: In function '__lockdep_lock_tryacquire':
core/kernel/lockdep.c:390:2: error: ISO C90 forbids mixed declarations and code [-Werror=declaration-after-statement]
struct lockdep_lock *lock = NULL;
^~~~~~

Reviewed-by: Etienne Carriere <etienne.carriere@linaro.org>
Signed-off-by: Jens Wiklander <jens.wiklander@linaro.org>

show more ...

core: lockdep: introduce CFG_LOCKDEP_RECORD_STACK

The lockdep algorithm uses quite a bit of heap memory to record the
call stacks. This commit adds a configuration flag so that this may be
turned of

core: lockdep: introduce CFG_LOCKDEP_RECORD_STACK

The lockdep algorithm uses quite a bit of heap memory to record the
call stacks. This commit adds a configuration flag so that this may be
turned off. When CFG_LOCKDEP_RECORD_STACK=n the deadlock detection
still works but the diagnostics message will show no call stack
obviously.

Signed-off-by: Jerome Forissier <jerome@forissier.org>
Acked-by: Jens Wiklander <jens.wiklander@linaro.org>

show more ...

core: lockdep: support non-blocking acquire

Adds support for non-blocking lock semantics such as mutex_trylock().
A new function is introduced to instrument this operation:
lockdep_tryacquire(). It

core: lockdep: support non-blocking acquire

Adds support for non-blocking lock semantics such as mutex_trylock().
A new function is introduced to instrument this operation:
lockdep_tryacquire(). It should be called when it is known that
ownership of the underlying object has been granted to the caller. It
behaves similarly to lockdep_acquire() in that it does record the call
stack and records that the lock is owned. But it does not create any
dependencies to the locks that are currently owned by the caller. See
"Dynamic Lock Dependency Analysis of Concurrent Systems" [1] section
5.3.

Link: [1] http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.87.132&rep=rep1&type=pdf
Signed-off-by: Jerome Forissier <jerome.forissier@linaro.org>
Acked-by: Jens Wiklander <jens.wiklander@linaro.org>

show more ...

core: lockdep: support lock destroy

With lockdep enabled (CFG_LOCKDEP=y), additional cleanup is needed when
a mutex is destroyed. This patch adds mutex_destroy_check() which is
called when a mutex i

core: lockdep: support lock destroy

With lockdep enabled (CFG_LOCKDEP=y), additional cleanup is needed when
a mutex is destroyed. This patch adds mutex_destroy_check() which is
called when a mutex is destroyed with mutex_destroy(). From
mutex_destroy_check() the corresponding lockdep node and all edges
referring to it are removed.

Reviewed-by: Jerome Forissier <jerome.forissier@linaro.org>
Acked-by: Etienne Carriere <etienne.carriere@linaro.org>
Signed-off-by: Jens Wiklander <jens.wiklander@linaro.org>

show more ...

lockdep: fix dup_call_stack()

dup_call_stack() does not properly deal with the sentinel. Fix it.

Signed-off-by: Jerome Forissier <jerome.forissier@linaro.org>
Reviewed-by: Jens Wiklander <jens.wikl

lockdep: fix dup_call_stack()

dup_call_stack() does not properly deal with the sentinel. Fix it.

Signed-off-by: Jerome Forissier <jerome.forissier@linaro.org>
Reviewed-by: Jens Wiklander <jens.wiklander@linaro.org>

show more ...

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

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>

show more ...