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

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [day] [month] [year] [list]

Message-ID: <56A805D2.20903@amd.com>
Date:	Tue, 26 Jan 2016 18:48:34 -0500
From:	Felix Kuehling <felix.kuehling@....com>
To:	<linux-kernel@...r.kernel.org>
Subject: Re: Lockdep incorrectly complaining about circular dependencies
 involving read-locks

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:
[snip]
> 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
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

-- 
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