Issue 81 in thread-sanitizer: False lock-order-inversion reports for locks taken in a single thread

[thread-s...@googlecode.com]

Status: New
Owner: ----
Labels: Type-Defect Priority-Medium

New issue 81 by gli...@chromium.org: False lock-order-inversion reports for
locks taken in a single thread
https://code.google.com/p/thread-sanitizer/issues/detail?id=81

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.

--
You received this message because this project is configured to send all
issue notifications to this address.
You may adjust your notification preferences at:
https://code.google.com/hosting/settings

[thread-s...@googlecode.com]

Comment #1 on issue 81 by gli...@google.com: False lock-order-inversion

reports for locks taken in a single thread
https://code.google.com/p/thread-sanitizer/issues/detail?id=81

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

[thread-s...@googlecode.com]

Comment #2 on issue 81 by gli...@google.com: False lock-order-inversion

reports for locks taken in a single thread
https://code.google.com/p/thread-sanitizer/issues/detail?id=81

Another one:
https://code.google.com/p/v8/source/browse/trunk/test/cctest/test-lockers.cc?r=24476#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.

[thread-s...@googlecode.com]

Comment #3 on issue 81 by gli...@google.com: False lock-order-inversion

reports for locks taken in a single thread
https://code.google.com/p/thread-sanitizer/issues/detail?id=81

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

[thread-s...@googlecode.com]

Updates:
Status: Accepted
Owner: dvyu...@google.com

Comment #4 on issue 81 by dvyu...@google.com: False lock-order-inversion

reports for locks taken in a single thread
https://code.google.com/p/thread-sanitizer/issues/detail?id=81

(No comment was entered for this change.)

[thread-s...@googlecode.com]

Comment #5 on issue 81 by konstant...@gmail.com: False lock-order-inversion

reports for locks taken in a single thread
https://code.google.com/p/thread-sanitizer/issues/detail?id=81

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

[thread-s...@googlecode.com]

Comment #6 on issue 81 by dvyu...@google.com: False lock-order-inversion

reports for locks taken in a single thread
https://code.google.com/p/thread-sanitizer/issues/detail?id=81

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

[thread-s...@googlecode.com]

Comment #7 on issue 81 by t...@cloudera.com: False lock-order-inversion

reports for locks taken in a single thread
https://code.google.com/p/thread-sanitizer/issues/detail?id=81

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.

[thread-s...@googlecode.com]

Comment #8 on issue 81 by dvyu...@google.com: False lock-order-inversion

reports for locks taken in a single thread
https://code.google.com/p/thread-sanitizer/issues/detail?id=81

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.

[thread-s...@googlecode.com]

Comment #9 on issue 81 by tlip...@gmail.com: False lock-order-inversion

reports for locks taken in a single thread
https://code.google.com/p/thread-sanitizer/issues/detail?id=81

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.

[thread-s...@googlecode.com]

Comment #10 on issue 81 by dvyu...@google.com: False lock-order-inversion

reports for locks taken in a single thread
https://code.google.com/p/thread-sanitizer/issues/detail?id=81

OK, makes sense, thanks!