False lock-order-inversion reports for locks taken in a single thread

[GoogleCodeExporter]

Consider there're two locks, L1 and L2, and a thread T1 that does the following:
 lock(L1)
 lock(L2)
 unlock(L1)
 lock(L1)
 unlock(L1)
 unlock(L2)

, while other threads may (or may not) acquire and release L1 and L2 (but not 
both) at the same time.
Based on the lock acquisition pattern in T1 ThreadSanitizer will report a 
lock-order-inversion (potential deadlock), although there's no possibility of a 
deadlock as long as other threads do not take both L1 and L2.
The error can even be reported in a single-threaded process, which isn't 
correct at all.

Original issue reported on code.google.com by gli...@chromium.org on 9 Oct 2014 at 9:25

[GoogleCodeExporter]

Example: https://code.google.com/p/chromium/issues/detail?id=412097

Original comment by gli...@google.com on 9 Oct 2014 at 9:27

[GoogleCodeExporter]

Another one: 
https://code.google.com/p/v8/source/browse/trunk/test/cctest/test-lockers.cc?r=2
4476#483

Run() acquires the first lock at line 485 and the second lock at line 499, 
creating the L1->L2 edge in the lock acquisition graph.
Then first lock is unlocked at line 510 and locked again at line 517 (when the 
unlocker dies), creating the L2->L1 edge.

Original comment by gli...@google.com on 9 Oct 2014 at 9:35

[GoogleCodeExporter]

We can probably filter such reports out if we prove that each edge has been 
created by the same thread. This may require keeping the list of threads that 
acquired L_i while holding L_j for each (L_i, L_j).

Original comment by gli...@google.com on 9 Oct 2014 at 9:37

[GoogleCodeExporter]

Original comment by dvyu...@google.com on 9 Oct 2014 at 9:52

• Changed state: Accepted

[GoogleCodeExporter]

>> We can probably filter such reports out if we prove that each edge has been 
created by the same thread.

We shouldn't imho...
What if the locking happens in a worker thread and just because the test is 
small there is a single worker (but the large app will have more workers)

Are you sure the pattern in #0 is good coding practice?
I would rather annotate that code (btw, do we have annotations?) than try to 
fix the detector. 

Original comment by konstant...@gmail.com on 9 Oct 2014 at 6:37

[GoogleCodeExporter]

> What if the locking happens in a worker thread and just because the test is 
small there is a single worker (but the large app will have more workers)

It can happen with a data race as well, tsan won't report racy accesses that 
happen to be in the same thread. And asan won't report a racy UAF if use 
happens before free.
Our general strategy to-date is to sacrifice some potential true positives to 
not have false positives; and require tests to expose bugs -- for any 
concurrency-related testing (races, deadlocks, etc) it means that the test must 
be multi-threaded.
I don't understand why we need to deviate from this line in this case.
Some of these cases involve pre-built libraries, so annotations are not 
possible. And suppressions have high chances of suppressing true deadlocks.

Original comment by dvyu...@google.com on 9 Oct 2014 at 8:04

[GoogleCodeExporter]

I previously worked on a Java deadlock detector (JCarder) and provided this as 
an option. The default was to report all cycles, but there was an option to 
only include multi-threaded cycles in the output. In using jcarder on some 
large Java projects, I found it helpful to have both options available.

Original comment by t...@cloudera.com on 8 Jan 2015 at 4:05

[GoogleCodeExporter]

Hi Todd,

Thanks for sharing your experience!

Can you provide an example of where it is useful to report "single-threaded 
deadlocks"?
My concern is that developers frequently apply the tool to large projects with 
lots of external dependencies; in such context the tool ideally works w/o any 
tuning (potentially sacrificing some percent of true positives for absence of 
false positives); or uses some form of per-function/file annotations if 
absolutely necessary. I do not really see how a global setting can be useful in 
such contexts.

Original comment by dvyu...@google.com on 19 Jan 2015 at 8:35

[GoogleCodeExporter]

I agree that in general, it's best to optimize to avoid false positives.

The reason that the "single-threaded deadlocks" are useful is just what the 
earlier commenter mentioned. We run the tool on our unit test suite, and often 
times unit tests don't generate enough multi-threaded concurrency to cause 
thread pools to exercise multiple threads in places like RPC handler pools.

Another case I've found is that, even though today the code might be safe, it's 
still the case that different methods are taking a pair of locks in inverted 
order. If the code changes a bit in the future (or users call library methods 
differently than the unit tests) then you are likely to hit a deadlock. It's 
generally a best practice to have a strict specified order of locks, and 
deviation from it is a code smell which many teams would want to eliminate 
early on.

So, I think it's best to allow a global setting, and also allow suppressions. 
Then, in many projects it's feasible to enable the global setting and either 
fix or suppress the few false positives that come out. If a project uses lots 
and lots of dependencies that exhibit this sort of problem, they can disable 
the reporting of single-threaded deadlocks.

Original comment by tlip...@gmail.com on 19 Jan 2015 at 8:43

[GoogleCodeExporter]

OK, makes sense, thanks!

Original comment by dvyu...@google.com on 19 Jan 2015 at 8:50