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 ...

core: instrument mutexes with lockdep

Implements lockdep hooks for mutexes. CFG_LOCKDEP is disabled by default,
because it causes a noticeable slowdown (plain xtest runs 2-4x slower).

Tested-by: Je

core: instrument mutexes with lockdep

Implements lockdep hooks for mutexes. CFG_LOCKDEP is disabled by default,
because it causes a noticeable slowdown (plain xtest runs 2-4x slower).

Tested-by: Jerome Forissier <jerome.forissier@linaro.org> (QEMU, HiKey960)
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 ...

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 ...