• Boqun Feng's avatar
    lockdep: Introduce lock_list::dep · 3454a36d
    Boqun Feng authored
    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: default avatarBoqun Feng <boqun.feng@gmail.com>
    Signed-off-by: default avatarPeter Zijlstra (Intel) <peterz@infradead.org>
    Link: https://lkml.kernel.org/r/20200807074238.1632519-7-boqun.feng@gmail.com
    3454a36d
lockdep.c 150 KB