Re: Lockdep incorrectly complaining about circular dependencies involving read-locks

From: Felix Kuehling
Date: Tue Jan 26 2016 - 19:02:41 EST

On 16-01-21 05:20 PM, Felix Kuehling wrote:
> 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:
> 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:
> spinlock_t fktest_sp;
> rwlock_t fktest_rw;
> spin_lock_init(&fktest_sp);
> rwlock_init(&fktest_rw);
> read_lock(&fktest_rw);
> 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

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

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.


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) ) /|_| |
/_/ \_\ |_| |_| |_____/ |__/ \| |