Page MenuHomePhabricator

[TSAN] Honor failure memory orders in AtomicCAS
Needs ReviewPublic

Authored by bruno on Mar 26 2021, 12:12 PM.

Details

Summary

LLVM has lifted strong requirements for CAS failure memory orders in 431e3138a and 819e0d105e84.

Add support for honoring them in AtomicCAS.

https://github.com/google/sanitizers/issues/970

Diff Detail

Event Timeline

bruno created this revision.Mar 26 2021, 12:12 PM
bruno requested review of this revision.Mar 26 2021, 12:12 PM
Herald added a project: Restricted Project. · View Herald TranscriptMar 26 2021, 12:12 PM
bruno added a reviewer: yln.
delcypher added a reviewer: kubamracek.

@bruno Thanks for the patch. TSan's runtime isn't my specialty so I've added other reviewers.

compiler-rt/lib/tsan/rtl/tsan_interface_atomic.cpp
446

Is this something user facing code can set? If yes, then we might want to emit a warning rather than crashing the process.

yln accepted this revision.Apr 6 2021, 9:38 AM

I am happy with the mechanics and quality of the patch. Ideally @dvyukov could give a final sign-off.

compiler-rt/lib/tsan/rtl/tsan_interface_atomic.cpp
446

I think calls are generated by the compiler in ThreadSanitizer::instrumentAtomic():

Value *Args[] = {IRB.CreatePointerCast(Addr, PtrTy),
                 CmpOperand,
                 NewOperand,
                 createOrdering(&IRB, CASI->getSuccessOrdering()),
                 createOrdering(&IRB, CASI->getFailureOrdering())};
CallInst *C = IRB.CreateCall(TsanAtomicCAS[Idx], Args);
This revision is now accepted and ready to land.Apr 6 2021, 9:38 AM
bruno added a comment.Apr 6 2021, 5:33 PM

Thanks both of you for the review @delcypher and @yln, will wait for @dvyukov to sign-off!

compiler-rt/lib/tsan/rtl/tsan_interface_atomic.cpp
446

Right, but before things are expanded for instrumentation, there's some sanitization of the failure memory order in emitAtomicCmpXchgFailureSet, so an invalid combination shouldn't get to this point.

dvyukov added inline comments.Wed, Apr 14, 1:40 AM
compiler-rt/lib/tsan/rtl/tsan_interface_atomic.cpp
447

Can't fmo be consume/acq_rel/seq_cst? If yes, please add a test.

449

I think we should not search the object and re-acquire the mutex second time for performance reasons and complexity (won't need to re-read the value).
Note that we may have already acquired due to mo. We should not acquire second time in that case.

456

I don't think this is correct. Can't this lead to false positives?
Consider that a thread does CAS-release to hand off the object to another thread, and that thread frees the object. I think this memory access can race with the free. It's generally not OK to touch memory after atomic operations.
If if leads to a false positive, please add a test that catches it.

compiler-rt/test/tsan/compare_exchange_release_relaxed.cpp
18 ↗(On Diff #333603)

If this test differs only by memory order, it can make sense to use parametrized tests. It would also be good to test other mo combinations (e.g. that the CHECK(IsLoadOrder(fmo)) does not fail).
See e.g. test/tsan/ignore_lib0.cpp for an example.

Also I wonder if we could first evaluate CAS and then use either mo or fmo accordingly, so that we don't over-synchronize on failure if mo is stronger than fmo.

Not directly related to the change but we could also episodically fail weak CASes to test fmo case better.

yln requested changes to this revision.Tue, Apr 20, 6:26 PM

Unapprove until Dmitry's comments are addressed.

This revision now requires changes to proceed.Tue, Apr 20, 6:26 PM
bruno updated this revision to Diff 341362.Wed, Apr 28, 5:11 PM
bruno marked an inline comment as done.
bruno edited the summary of this revision. (Show Details)

Address reviewer comments. To prevent false positive on release/consume, this now depends on https://reviews.llvm.org/D101501.

bruno marked 2 inline comments as done.Wed, Apr 28, 5:16 PM
bruno added inline comments.
compiler-rt/lib/tsan/rtl/tsan_interface_atomic.cpp
447

Added several variations. The consume failing order currently fallbacks to monotonic in LLVM, just opened https://reviews.llvm.org/D101501 to be consistent with success and fallback to acquire instead, without this change it leads to false positive, thanks for bringing this up.

456

Looks like I overthought the approach, thanks for pointing out.

dvyukov added inline comments.Wed, Apr 28, 11:38 PM
compiler-rt/lib/tsan/rtl/tsan_interface_atomic.cpp
412–413

I think it's better to avoid doing this if the CAS will fail and fmo == mo_relaxed. It will provide more precise race detection.
I think we could do something along the following lines:

  • if either mo or fmo != relaxed, do GetOrCreateAndLock
  • if either mo or fmo involves release, do a write lock
  • evaluate cas
  • respect mo or fmo based on the cas result
449

We did not create/obtain the sync object if mo == mo_relaxed. Is mo == mo_relaxed and fmo == mo_acquire possible? If yes, then we will fail to respect fmo.

451

We used a different condition to decide if we need to do read lock. Can't this deadlock? I think we need to check write_lock.

bruno updated this revision to Diff 342557.Mon, May 3, 3:08 PM
bruno marked an inline comment as done and an inline comment as not done.
bruno edited the summary of this revision. (Show Details)

Apply review comments.

Note that we cannot test mo == relaxed and fmo == anything yet because LLVM fallbacks to relaxed/relaxed.

Remove the dep on https://reviews.llvm.org/D101501 for now, since there's even more stuff to improve in LLVM before we get this 100% right, at least we've got release/acquire working as of this patch. I'll come back to fix the other tests once LLVM is fixed.

compiler-rt/lib/tsan/rtl/tsan_interface_atomic.cpp
412–413

Sounds good, minor correction on the fact that fmo cannot be release.

449

Right, will fix.

451

Yea, somehow it slipped, thanks!

bruno updated this revision to Diff 342565.Mon, May 3, 3:15 PM

Update broken comment in the testcase.

dvyukov added inline comments.Tue, May 4, 12:42 AM
compiler-rt/lib/tsan/rtl/tsan_interface_atomic.cpp
412–413

Do I wait for this in this change? I see we still acquire/release before evaluating CAS. Or you want to do it later with other improvements you mentioned?

444

Better to do in the beginning of the function.

451

With the current code it makes sense to do "IsAcquireOrder(fmo) && !IsAcquireOrder(mo)", because otherwise we already acquired.
But even better what's discussed above: first evaluate CAS, then decide what order to use.

bruno updated this revision to Diff 343581.Thu, May 6, 10:38 PM
bruno retitled this revision from [TSAN] Honor acquire failure mode on AtomicCAS to [TSAN] Honor failure memory orders in AtomicCAS.
bruno edited the summary of this revision. (Show Details)

Apply more reviewer suggested changes: first evaluate CAS, then decide what order to use.

Now that LLVM side of this is fixed, also cover all fmo's allowed, add more tests.

bruno updated this revision to Diff 343584.Thu, May 6, 10:50 PM

Cover more cases in atomic.ll.

dvyukov added inline comments.Thu, May 6, 11:48 PM
compiler-rt/lib/tsan/rtl/tsan_interface_atomic.cpp
406

Can it be seq_cst?
If yes, then I think write_lock below is incorrect and checking only IsAcquireOrder(fmo) is incorrect as well.

416

The CAS needs to be evaluated under the sync object mutex, otherwise we can get inconsistent value/memory visibility. If we are going to lock the mutex, we need to lock it before CAS.