lockdep: Introduce lock_list::dep
authorBoqun Feng <boqun.feng@gmail.com>
Fri, 7 Aug 2020 07:42:25 +0000 (15:42 +0800)
committerPeter Zijlstra <peterz@infradead.org>
Wed, 26 Aug 2020 10:42:04 +0000 (12:42 +0200)
commit3454a36d6a39186de508dd43df590a6363364176
treee2cce77c493fabdf9b791e6ce02fe8ad8e8ff96a
parentbd76eca10de2eb9998d5125b08e8997cbf5508d5
lockdep: Introduce lock_list::dep

To add recursive read locks into the dependency graph, we need to store
the types of dependencies for the BFS later. There are four types of
dependencies:

* Exclusive -> Non-recursive dependencies: EN
e.g. write_lock(prev) held and try to acquire write_lock(next)
or non-recursive read_lock(next), which can be represented as
"prev -(EN)-> next"

* Shared -> Non-recursive dependencies: SN
e.g. read_lock(prev) held and try to acquire write_lock(next) or
non-recursive read_lock(next), which can be represented as
"prev -(SN)-> next"

* Exclusive -> Recursive dependencies: ER
e.g. write_lock(prev) held and try to acquire recursive
read_lock(next), which can be represented as "prev -(ER)-> next"

* Shared -> Recursive dependencies: SR
e.g. read_lock(prev) held and try to acquire recursive
read_lock(next), which can be represented as "prev -(SR)-> next"

So we use 4 bits for the presence of each type in lock_list::dep. Helper
functions and macros are also introduced to convert a pair of locks into
lock_list::dep bit and maintain the addition of different types of
dependencies.

Signed-off-by: Boqun Feng <boqun.feng@gmail.com>
Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
Link: https://lkml.kernel.org/r/20200807074238.1632519-7-boqun.feng@gmail.com
include/linux/lockdep.h
kernel/locking/lockdep.c