Lockdep incorrectly complaining about circular dependencies involving read-locks
I'm running into circular lock dependencies reported by lockdep that involve read-locks and should not be flagged as deadlocks at all. I wrote a very simple test function that demonstrates the problem:
Quoted 13 lines
static void
test_lockdep(void){ struct mutex fktest_m; struct rw_semaphore fktest_s; mutex_init(&fktest_m); init_rwsem(&fktest_s); down_read(&fktest_s); mutex_lock(&fktest_m); mutex_unlock(&fktest_m); up_read(&fktest_s);
Quoted 7 lines
mutex_lock(&fktest_m); down_read(&fktest_s); up_read(&fktest_s); mutex_unlock(&fktest_m); mutex_destroy(&fktest_m); }
It sets up a circular lock dependency between a mutex and a read-write semaphore. However, the semaphore is only ever locked for reading. As I understand it, there is no potential for a deadlock here because multiple readers don't exclude each other. However, I get this:
Quoted 74 lines
[ 10.832547]
[ 10.834122] ======================================================
[ 10.840655] [ INFO: possible circular locking dependency detected ]
[ 10.847284] 4.4.0-kfd #3 Tainted: G E
[ 10.852356] -------------------------------------------------------
[ 10.858989] systemd-udevd/2385 is trying to acquire lock:
[ 10.864695] (&fktest_s){.+.+..}, at: [<ffffffffc0212463>] test_lockdep+0x9a/0xd4 [amdgpu]
[ 10.873474]
[ 10.873474] but task is already holding lock:
[ 10.879633] (&fktest_m){+.+...}, at: [<ffffffffc0212457>] test_lockdep+0x8e/0xd4 [amdgpu]
[ 10.888418]
[ 10.888418] which lock already depends on the new lock.
[ 10.888418]
[ 10.897071]
[ 10.897071] the existing dependency chain (in reverse order) is:
[ 10.904981]
-> #1 (&fktest_m){+.+...}:
[ 10.909138] [<ffffffff810ada5d>] lock_acquire+0x6d/0x90
[ 10.915309] [<ffffffff8190ddaa>] mutex_lock_nested+0x4a/0x3a0
[ 10.922040] [<ffffffffc0212431>] test_lockdep+0x68/0xd4 [amdgpu]
[ 10.929042] [<ffffffffc0295009>] amdgpu_init+0x9/0x7b [amdgpu]
[ 10.935856] [<ffffffff810003f8>] do_one_initcall+0xc8/0x200
[ 10.942449] [<ffffffff8113f5ad>] do_init_module+0x56/0x1d8
[ 10.948919] [<ffffffff810e83b1>] load_module+0x1b91/0x2460
[ 10.955376] [<ffffffff810e8e5b>] SyS_finit_module+0x7b/0xa0
[ 10.961961] [<ffffffff81910572>] entry_SYSCALL_64_fastpath+0x12/0x76
[ 10.969388]
-> #0 (&fktest_s){.+.+..}:
[ 10.973569] [<ffffffff810acc2a>] __lock_acquire+0x100a/0x16b0
[ 10.980315] [<ffffffff810ada5d>] lock_acquire+0x6d/0x90
[ 10.986502] [<ffffffff8190e884>] down_read+0x34/0x50
[ 11.002586] [<ffffffffc0212463>] test_lockdep+0x9a/0xd4 [amdgpu]
[ 11.009610] [<ffffffffc0295009>] amdgpu_init+0x9/0x7b [amdgpu]
[ 11.016453] [<ffffffff810003f8>] do_one_initcall+0xc8/0x200
[ 11.023001] [<ffffffff8113f5ad>] do_init_module+0x56/0x1d8
[ 11.029462] [<ffffffff810e83b1>] load_module+0x1b91/0x2460
[ 11.035927] [<ffffffff810e8e5b>] SyS_finit_module+0x7b/0xa0
[ 11.042478] [<ffffffff81910572>] entry_SYSCALL_64_fastpath+0x12/0x76
[ 11.049860]
[ 11.049860] other info that might help us debug this:
[ 11.049860]
[ 11.058356] Possible unsafe locking scenario:
[ 11.058356]
[ 11.064644] CPU0 CPU1
[ 11.069436] ---- ----
[ 11.074229] lock(&fktest_m);
[ 11.077465] lock(&fktest_s);
[ 11.083376] lock(&fktest_m);
[ 11.089288] lock(&fktest_s);
[ 11.092542]
[ 11.092542] *** DEADLOCK ***
[ 11.092542]
[ 11.098819] 1 lock held by systemd-udevd/2385:
[ 11.103530] #0: (&fktest_m){+.+...}, at: [<ffffffffc0212457>] test_lockdep+0x8e/0xd4 [amdgpu]
[ 11.112780]
[ 11.112780] stack backtrace:
[ 11.117388] CPU: 7 PID: 2385 Comm: systemd-udevd Tainted: G E 4.4.0-kfd #3
[ 11.125840] Hardware name: ASUS All Series/Z97-PRO(Wi-Fi ac)/USB 3.1, BIOS 2401 04/27/2015
[ 11.134593] ffffffff82714a90 ffff8808335d7a70 ffffffff8144e3cb ffffffff82714a90
[ 11.142421] ffff8808335d7ab0 ffffffff8113ec7a ffff8808335d7b00 0000000000000000
[ 11.150248] ffff8808335a9ee0 ffff8808335a9f08 ffff8808335a96c0 ffff8808335a9f08
[ 11.158076] Call Trace:
[ 11.160655] [<ffffffff8144e3cb>] dump_stack+0x44/0x59
[ 11.166105] [<ffffffff8113ec7a>] print_circular_bug+0x1f9/0x207
[ 11.172457] [<ffffffff810acc2a>] __lock_acquire+0x100a/0x16b0
[ 11.178619] [<ffffffff810ab706>] ? mark_held_locks+0x66/0x90
[ 11.184693] [<ffffffffc0295000>] ? 0xffffffffc0295000
[ 11.190127] [<ffffffff810ada5d>] lock_acquire+0x6d/0x90
[ 11.195758] [<ffffffffc0212463>] ? test_lockdep+0x9a/0xd4 [amdgpu]
[ 11.202376] [<ffffffff8190e884>] down_read+0x34/0x50
[ 11.207729] [<ffffffffc0212463>] ? test_lockdep+0x9a/0xd4 [amdgpu]
[ 11.214370] [<ffffffffc0212463>] test_lockdep+0x9a/0xd4 [amdgpu]
[ 11.220847] [<ffffffffc0295009>] amdgpu_init+0x9/0x7b [amdgpu]
[ 11.227096] [<ffffffff810003f8>] do_one_initcall+0xc8/0x200Quoted 8 lines
[ 11.233083] [<ffffffff8113f574>] ? do_init_module+0x1d/0x1d8 [ 11.239153] [<ffffffff8119bb4f>] ? kmem_cache_alloc+0xbf/0x180 [ 11.245421] [<ffffffff8113f5ad>] do_init_module+0x56/0x1d8 [ 11.251307] [<ffffffff810e83b1>] load_module+0x1b91/0x2460 [ 11.257196] [<ffffffff810e58e0>] ? __symbol_put+0x30/0x30 [ 11.262993] [<ffffffff810e5c06>] ? copy_module_from_fd.isra.61+0xf6/0x150 [ 11.270261] [<ffffffff810e8e5b>] SyS_finit_module+0x7b/0xa0 [ 11.276250] [<ffffffff81910572>] entry_SYSCALL_64_fastpath+0x12/0x76
I confirmed my results with the latest master branch of
https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git, but I was seeing the same thing on a 4.1-based kernel.
Relevant kernel config bits:
Quoted 4 lines
$ grep LOCKDEP .config CONFIG_LOCKDEP_SUPPORT=y CONFIG_LOCKDEP=y # CONFIG_DEBUG_LOCKDEP is not set
I'm reading lockdep code now, trying to understand how lockdep works in detail, and how it could properly deal with read-locks. But it will probably take me a few more days or weeks to figure it out by myself (or be convinced it can't be done). I'd appreciate feedback from someone more familiar with the code.
Thank you,
Felix
P.S.: I'm not subscribed to the list. I'll be watching the archives or digests, but please CC me on replies.
Signature · 8 lines
F e l i x K u e h l i n g SMTS Software Development Engineer | Vertical Workstation/Compute 1 Commerce Valley Dr. East, Markham, ON L3T 7X6 Canada (O) +1(289)695-1597 _ _ _ _____ _____ / \ | \ / | | _ \ \ _ | / A \ | \M/ | | |D) ) /|_| | /_/ \_\ |_| |_| |_____/ |__/ \| facebook.com/AMD | amd.com
Quoted 3 lines · Felix Kuehling
I'm running into circular lock dependencies reported by lockdep that involve read-locks and should not be flagged as deadlocks at all. I wrote a very simple test function that demonstrates the problem:
[snip]
Quoted 2 lines
It sets up a circular lock dependency between a mutex and a read-write semaphore. However, the semaphore is only ever locked for reading.
The same expirement with a spinlock and an rwlock works correctly. The difference is that the rwlock allows recursive read-locks, whereas the rw semaphore does not. Recursive read-locks are not added to the lock dependency graph at all, hence they don't trip the circular lock checks.
I think this handling of recursive read locks is actually incorrect, because it fails to notice potential circular deadlocks like this:
Quoted 7 lines
spinlock_t fktest_sp;
rwlock_t fktest_rw;
spin_lock_init(&fktest_sp);
rwlock_init(&fktest_rw);
read_lock(&fktest_rw);Quoted 8 lines
spin_lock(&fktest_sp);
spin_unlock(&fktest_sp);
read_unlock(&fktest_rw);
spin_lock(&fktest_sp);
write_lock(&fktest_rw);
write_unlock(&fktest_rw);
spin_unlock(&fktest_sp);In a possible deadlock scenario thread A takes read lock, thread B takes spin lock, thread A blocks trying to take spin lock, thread B blocks trying to take write lock.
The read-lock depending on the spinlock is never entered into the dependency graph. Hence the circular dependency is not seen when the write lock is taken.
I think the whole handling of read-locks needs to be revamped for proper detection of circular lock dependencies without false positives or false negatives (I have demonstrated one example of each with the current implementation).
A dependency chain must be able to distinguish, whether a lock is taken for reading or for writing. That means, read locks need their own lock (sub-)class. A new write dependency (a lock that depends on holding a write-lock) creates a dependency on both the read and write-lock classes, because both cases can lead to a potential deadlock. A new read dependency (a lock that depends on holding a read-lock) only creates a dependency on the write-lock class, because read locks don't block each other.
I'm going to prototype my idea. I can use sub-classes for making separate read and write lock classes. But that means, effectively I only have half as many usable lock sub-classes left available for nesting annotations on lock primitives that support read-locking. I hope that's not a problem.
Feedback welcome.
Regards,
Felix
Signature · 8 lines
F e l i x K u e h l i n g SMTS Software Development Engineer | Vertical Workstation/Compute 1 Commerce Valley Dr. East, Markham, ON L3T 7X6 Canada (O) +1(289)695-1597 _ _ _ _____ _____ / \ | \ / | | _ \ \ _ | / A \ | \M/ | | |D) ) /|_| | /_/ \_\ |_| |_| |_____/ |__/ \| facebook.com/AMD | amd.com