Thread safety analysis: Always warn when dropping locks on back edges

[aaronpuchert]

Summary

We allow branches to join where one holds a managed lock but the other
doesn't, but we can't do so for back edges: because there we can't drop
them from the lockset, as we have already analyzed the loop with the
larger lockset. So we can't allow dropping managed locks on back edges.

We move the managed() check from handleRemovalFromIntersection up to
intersectAndWarn, where we additionally check if we're on a back edge if
we're removing from the first lock set (the entry set of the next block)
but not if we're removing from the second lock set (the exit set of the
previous block). Now that the order of arguments matters, I had to swap
them in one invocation, which also causes some minor differences in the
tests.

[aaronpuchert]

clang/lib/Analysis/ThreadSafety.cpp

868

One might ask: what about asserted capabilities? I plan to introduce a warning when they are released, because that can't be consistent, and then they can't disappear on back edges without warning.

For negative capabilities we'd presumably see a warning for the "positive" capability instead.

Not sure how universal capabilities are typically used. Presumably one could release such a capability in a loop? Then on the other hand, code using such capabilities is probably not very interested in false negatives.

2227–2228

Presumably we should call these EntrySet and ExitSet instead? The second parameter is always the exit set of an existing block, the first parameter the entry set of a (sometimes new) block.

clang/test/SemaCXX/warn-thread-safety-analysis.cpp

643

These are just swapped because I'm merging the branches in a different order now. I think that's Ok.

2788

This warning is new.

2813

This is also new.

[aaronpuchert]

clang/lib/Analysis/ThreadSafety.cpp

2227–2228

Did this in a separate change D104649, because it would obfuscate the changes here. Nevertheless, it's probably a good idea to look at both changes together.

[aaron.ballman]

I think the CI failure (libarcher.races::lock-unrelated.c) is not related to this patch but is a tsan thing, but you may want to double-check that just in case.

I think this looks reasonable, but I'd like to hear from @delesley before landing.

clang/test/SemaCXX/warn-thread-safety-analysis.cpp

643

I think the new order is actually an improvement because it diagnoses the second acquisition (diagnosing the first is a bit weirdly predictive for my tastes).

2806–2816

How about a test like:

void foo() {
  RelockableMutexLock scope(&mu, ExclusiveTraits{});
  for (unsigned i = 1; i < 10; ++i) {
    if (i > 0) // Always true
      scope.Lock(); // So we always lock
    x = 1; // So I'd assume we don't warn
  }
}

[aaronpuchert]

In D104261#2832892, @aaron.ballman wrote:

I think the CI failure (libarcher.races::lock-unrelated.c) is not related to this patch but is a tsan thing, but you may want to double-check that just in case.

Seems that an expected race didn't materialize, perhaps it's a bit flaky. I'd be surprised if it was related.

I'd like to hear from @delesley before landing.

Me too. Generally about treating back edges differently, as we can't modify the lockset anymore. (I have a similar change that's going to take back some of relaxations in D102026, namely for an exclusive lock coming back as a shared lock on the back edge.)

clang/test/SemaCXX/warn-thread-safety-analysis.cpp

2806–2816

The CFG isn't that clever, it would only consider i > 0 always true if i was a compile-time constant. It doesn't even consider type limits, so for i >= 0 the else-branch would still be considered reachable:

[B2]
  1: x
  2: [B2.1] (ImplicitCastExpr, LValueToRValue, unsigned int)
  3: 0
  4: [B2.3] (ImplicitCastExpr, IntegralCast, unsigned int)
  5: [B2.2] >= [B2.4]
  T: if [B2.5]
  Preds (1): B3
  Succs (2): B1 B0

versus the same with true:

[B2]
  1: true
  T: if [B2.1]
  Preds (1): B3
  Succs (2): B1 B0(Unreachable)

But let's say we use a compile-time constant, then it's equivalent to not having the Lock call conditional at all, and there is no warning. Actually I might just change loopAcquire into this, because as that test is written right now it doesn't affect the back edge at all. (The lock will be removed from the lockset when the if joins with the else, before we loop back.)

[aaronpuchert]

clang/lib/Analysis/ThreadSafety.cpp

868

For negative capabilities we'd presumably see a warning for the "positive" capability instead.

No, because a back edge is missing a positive capability when I'm unlocking in a loop, whereas it would be missing a negative capability when I'm locking in a loop.

But we probably want to warn about this only when -Wthread-safety-negative is active.

[delesley]

This looks good to me. Thanks for the patch! Since you're adding a new warning, this may break some code somewhere, but since it's restricted to relockable managed locks, I'm not too worried...

[aaronpuchert]

In D104261#2841356, @delesley wrote:

since it's restricted to relockable managed locks, I'm not too worried...

Not quite, it affects scoped locks with explicit unlock, which was supported before D49885.

@rupprecht, can you still test patches on Google's code? Would be good to know if this breaks anything.

[rupprecht]

In D104261#2844636, @aaronpuchert wrote:

In D104261#2841356, @delesley wrote:

since it's restricted to relockable managed locks, I'm not too worried...

Not quite, it affects scoped locks with explicit unlock, which was supported before D49885.

@rupprecht, can you still test patches on Google's code? Would be good to know if this breaks anything.

Thanks for the heads up. I ran this on the same targets that broke in D84604 (in case that's what you're looking for), and those continue to pass. I can try further testing of other targets, but that may take a little longer, so I have no problem with you landing this as-is and I can follow up if there are problems elsewhere.

clang/lib/Analysis/ThreadSafety.cpp

public:
   LockableFactEntry(const CapabilityExpr &CE, LockKind LK, SourceLocation Loc,
                     SourceKind Src = Acquired)
       : FactEntry(CE, LK, Loc, Src) {}
 
   void
   handleRemovalFromIntersection(const FactSet &FSet, FactManager &FactMan,
                                 SourceLocation JoinLoc, LockErrorKind LEK,
                                 ThreadSafetyHandler &Handler) const override {
-    if (!managed() && !asserted() && !negative() && !isUniversal()) {
+    if (!asserted() && !negative() && !isUniversal()) {
       Handler.handleMutexHeldEndOfScope("mutex", toString(), loc(), JoinLoc,
                                         LEK);
     }
   }
 
   void handleLock(FactSet &FSet, FactManager &FactMan, const FactEntry &entry,
                   ThreadSafetyHandler &Handler,
                   StringRef DiagKind) const override {

 /// are the same. In the event of a difference, we use the intersection of these
 /// two locksets at the start of D.
 ///
 /// \param FSet1 The first lockset.
 /// \param FSet2 The second lockset.
 /// \param JoinLoc The location of the join point for error reporting
 /// \param LEK1 The error message to report if a mutex is missing from LSet1
 /// \param LEK2 The error message to report if a mutex is missing from Lset2
 void ThreadSafetyAnalyzer::intersectAndWarn(FactSet &FSet1,
                                             const FactSet &FSet2,
                                             SourceLocation JoinLoc,
                                             LockErrorKind LEK1,
                                             LockErrorKind LEK2) {
   FactSet FSet1Orig = FSet1;
 
   // Find locks in FSet2 that conflict or are not in FSet1, and warn.
   for (const auto &Fact : FSet2) {
     const FactEntry &LDat2 = FactMan[Fact];
 
     FactSet::iterator Iter1 = FSet1.findLockIter(FactMan, LDat2);
     if (Iter1 != FSet1.end()) {
       if (join(FactMan[*Iter1], LDat2) && LEK1 == LEK_LockedSomePredecessors)
         *Iter1 = Fact;
-    } else {
+    } else if (!LDat2.managed()) {
       LDat2.handleRemovalFromIntersection(FSet2, FactMan, JoinLoc, LEK1,
                                           Handler);
     }
   }
 
   // Find locks in FSet1 that are not in FSet2, and remove them.
   for (const auto &Fact : FSet1Orig) {
     const FactEntry *LDat1 = &FactMan[Fact];
     const FactEntry *LDat2 = FSet2.findLock(FactMan, *LDat1);
 
     if (!LDat2) {
+      if (!LDat1->managed() || LEK2 == LEK_LockedSomeLoopIterations)
         LDat1->handleRemovalFromIntersection(FSet1Orig, FactMan, JoinLoc, LEK2,
                                              Handler);
       if (LEK2 == LEK_LockedSomePredecessors)
         FSet1.removeLock(FactMan, *LDat1);
     }
   }
 }
 
 // Return true if block B never continues to its successors.
 static bool neverReturns(const CFGBlock *B) {
for (CFGBlock::const_succ_iterator SI = CurrBlock->succ_begin(),
          SE  = CurrBlock->succ_end(); SI != SE; ++SI) {
       // if CurrBlock -> *SI is *not* a back edge
       if (*SI == nullptr || !VisitedBlocks.alreadySet(*SI))
         continue;
 
       CFGBlock *FirstLoopBlock = *SI;
       CFGBlockInfo *PreLoop = &BlockInfo[FirstLoopBlock->getBlockID()];
       CFGBlockInfo *LoopEnd = &BlockInfo[CurrBlockID];
-      intersectAndWarn(LoopEnd->ExitSet, PreLoop->EntrySet, PreLoop->EntryLoc,
+      intersectAndWarn(PreLoop->EntrySet, LoopEnd->ExitSet, PreLoop->EntryLoc,
                        LEK_LockedSomeLoopIterations);
     }
   }
 
   CFGBlockInfo *Initial = &BlockInfo[CFGraph->getEntry().getBlockID()];
   CFGBlockInfo *Final   = &BlockInfo[CFGraph->getExit().getBlockID()];
 
   // Skip the final check if the exit block is unreachable.

clang/test/SemaCXX/warn-thread-safety-analysis.cpp

do {
     sls_mu.Unlock();
     sls_mu.Lock();
   } while (getBool());
   sls_mu.Unlock();
 }
 
 void shared_fun_1() {
   sls_mu.ReaderLock(); // \
-    // expected-warning {{mutex 'sls_mu' is acquired exclusively and shared in the same scope}}
+    // expected-note {{the other acquisition of mutex 'sls_mu' is here}}
   do {
     sls_mu.Unlock();
     sls_mu.Lock();  // \
-      // expected-note {{the other acquisition of mutex 'sls_mu' is here}}
+      // expected-warning {{mutex 'sls_mu' is acquired exclusively and shared in the same scope}}
   } while (getBool());
   sls_mu.Unlock();
 }
 
 void shared_fun_3() {
   if (getBool())
     sls_mu.Lock();
   else

 void shared_fun_11() {
   sls_mu.ReaderLock();
   sls_mu.PromoteShared();
   sls_mu.Unlock();
 }
 
 void shared_bad_0() {
   sls_mu.Lock();  // \
-    // expected-warning {{mutex 'sls_mu' is acquired exclusively and shared in the same scope}}
+    // expected-note {{the other acquisition of mutex 'sls_mu' is here}}
   do {
     sls_mu.Unlock();
     sls_mu.ReaderLock();  // \
-      // expected-note {{the other acquisition of mutex 'sls_mu' is here}}
+      // expected-warning {{mutex 'sls_mu' is acquired exclusively and shared in the same scope}}
   } while (getBool());
   sls_mu.Unlock();
 }
 
 void shared_bad_1() {
   if (getBool())
     sls_mu.Lock(); // \
       // expected-warning {{mutex 'sls_mu' is acquired exclusively and shared in the same scope}}
void unlockJoin() {
   RelockableMutexLock scope(&mu, DeferTraits{});
   scope.Lock();
   if (b)
     scope.Unlock();
   // No warning on join point because the lock will be released by the scope object anyway.
   x = 2; // expected-warning {{writing variable 'x' requires holding mutex 'mu' exclusively}}
 }
 
+void loopAcquire() {
+  RelockableMutexLock scope(&mu, DeferTraits{});
+  for (unsigned i = 1; i < 10; ++i)
+    scope.Lock(); // We could catch this double lock with negative capabilities.
+}
+
+void loopRelease() {
+  RelockableMutexLock scope(&mu, ExclusiveTraits{}); // expected-note {{mutex acquired here}}
+  // We have to warn on this join point despite the lock being managed ...
+  for (unsigned i = 1; i < 10; ++i) { // expected-warning {{expecting mutex 'mu' to be held at start of each loop}}
+    x = 1; // ... because we might miss that this doesn't always happen under lock.
+    if (i == 5)
+      scope.Unlock();
+  }
+}
+
+void loopAcquireContinue() {
+  RelockableMutexLock scope(&mu, DeferTraits{});
+  for (unsigned i = 1; i < 10; ++i) {
+    x = 1; // expected-warning {{writing variable 'x' requires holding mutex 'mu' exclusively}}
+    if (i == 5) {
+      scope.Lock();
+      continue;
+    }
+  }
+}
+
+void loopReleaseContinue() {
+  RelockableMutexLock scope(&mu, ExclusiveTraits{}); // expected-note {{mutex acquired here}}
+  // We have to warn on this join point despite the lock being managed ...
+  for (unsigned i = 1; i < 10; ++i) {
+    x = 1; // ... because we might miss that this doesn't always happen under lock.
+    if (i == 5) {
+      scope.Unlock();
+      continue; // expected-warning {{expecting mutex 'mu' to be held at start of each loop}}
+    }
+  }
+}
+
 void exclusiveSharedJoin() {
   RelockableMutexLock scope(&mu, DeferTraits{});
   if (b)
     scope.Lock();
   else
     scope.ReaderLock();
   // No warning on join point because the lock will be released by the scope object anyway.
   print(x);
   x = 2; // expected-warning {{writing variable 'x' requires holding mutex 'mu' exclusively}}
 }