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
| ||
|
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
Powered by blists - more mailing lists