| b3fd78c4 | 14-Sep-2018 |
Jerome Forissier <jerome.forissier@linaro.org> |
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 ...
|
| daeea036 | 03-Nov-2017 |
Jerome Forissier <jerome.forissier@linaro.org> |
Add CFG_CONCURRENT_SINGLE_INSTANCE_TA
Commit 2b07dcb97c5e ("core: avoid deadlocks caused by single-instance
TA") introduces a lock that allows only one single instance TA to be
executing at any time
Add CFG_CONCURRENT_SINGLE_INSTANCE_TA
Commit 2b07dcb97c5e ("core: avoid deadlocks caused by single-instance
TA") introduces a lock that allows only one single instance TA to be
executing at any time. While it does address the risk of deadlock that
can arise when several single instance TAs call each other, it also
puts a serious performance limitation on multi-core platforms, which
could otherwise execute several unrelated single instance TAs
simultaneously.
This commit makes the single instance lock optional. By setting
CFG_CONCURRENT_SINGLE_INSTANCE_TA=y, the lock is disabled and TAs are
allowed to run concurrently. In the future, we may implement a deadlock
detection algorithm; in the meantime, this simple solution should be
enough to cover the current use cases.
Signed-off-by: Jerome Forissier <jerome.forissier@linaro.org>
Tested-by: Jerome Forissier <jerome.forissier@linaro.org> (HiKey960)
CC: Zeng Tao <prime.zeng@hisilicon.com>
Acked-by: Jens Wiklander <jens.wiklander@linaro.org>
Reviewed-by: Etienne Carriere <etienne.carriere@linaro.org>
show more ...
|
| ce553c81 | 12-Oct-2017 |
Jens Wiklander <jens.wiklander@linaro.org> |
core: asan: empty __asan_handle_no_return()
It seems __asan_handle_no_return() isn't called when a __noreturn
function returns, instead it's called before the function is called. So
empty the __asa
core: asan: empty __asan_handle_no_return()
It seems __asan_handle_no_return() isn't called when a __noreturn
function returns, instead it's called before the function is called. So
empty the __asan_handle_no_return() function to let __noreturn function
be called.
Reviewed-by: Etienne Carriere <etienne.carriere@linaro.org>
Signed-off-by: Jens Wiklander <jens.wiklander@linaro.org>
show more ...
|