[RFC] Thread safety analysis: Track status of scoped capability

[aaronpuchert]

Summary

We now warn when acquiring or releasing a scoped capability a second
time, not just if the underlying mutexes have been acquired or released
a second time.

Whether we unlock the underlying mutexes now depends on the status of
the scoped capability. So we don't unlock them if we are already
released, and we unlock them (with warning even on destruction) if we
are currently locked.

[aaron.ballman]

I'm not certain how I feel about this as it seems to be removing functionality users may be relying on that I think is still technically correct. Can you describe more about why you think this should change?

[aaronpuchert]

Sure. As I wrote in the commit message, I'm not sure about it myself, but I think it's worth a discussion. Maybe I should have tagged it as RFC.

Releasable scopes need a way of knowing whether the lock is currently held to prevent double unlocking in the destructor. There are basically two ways to achieve that: one can ask the underlying mutex if it is locked, or keep track of the lock status. The second might be the only option available, as not all mutex implementations offer a way to find out if they are currently held.

Suppose we have something like:

class ReleasableScope {
  Mutex *mu;
  bool Locked;

public:
  ReleasableScope(Mutex *mu) : mu(mu), Locked(true) {
    mu->Lock();
  }
  void Unlock() { mu->Unlock(); Locked = false; }
  ~ReleasableScope() { if (Locked) mu->Unlock(); }
};

Then it can be a problem if someone works directly on the underlying mutex without informing the scoped capability:

Mutex mu;

void test1() {
  ReleasableScope scope(&mu);
  mu.Unlock();
} // ~ReleasableScope unlocks mu again, but we don't warn about double unlock.

void test2() {
  ReleasableScope scope(&mu);
  scope.Unlock()
  mu.Lock();
} // ~ReleasableScope does not unlock, but we don't warn about the lock still being held.

In the LockableFactEntry we call mu the "managed" mutex of scope and I think that implies that for its lifetime only scope should touch mu. What we do in test1 is akin to manually deleteing the underlying pointer of a std::unique_ptr. I would actually consider releasing mu again in ScopedLockableFactEntry::handleUnlock in the epilogue of test1 and not releasing it in the epilogue of test2, because we think it is still locked/already unlocked. Then we would emit warnings in both cases.

On the other hand, if the scoped capability can (and does) ask the underlying mutex for its state before doing anything, we might be completely fine, as you stated.

So I'm really not sure, but I think there are some arguments that can be made for introducing this warning (and possibly more).

We could also consider making this part of the -Wthread-safety-beta warnings, so that we don't break anyone's -Werror=thread-safety builds.

[aaronpuchert]

Use Locked flag to determine whether to unlock on destruction

Instead of unlocking the mutexes that are still available while not complaining about those that aren't, we use the status of the scoped capability to determine whether to unlock the underlying mutexes.

This way we will attempt to unlock the mutex even if the user unlocked it manually, warning if it is no longer available, and we will not attempt to unlock if we are already released, hence warning if it is manually acquired again.

[aaronpuchert]

This doesn't work with loops yet:

void relockLoop() {
  RelockableExclusiveMutexLock scope(&mu);

  while (b) {
    scope.Unlock(); // releasing mutex 'scope' that was not held
    scope.Lock();   // acquiring mutex 'mu' that is already held
  }
}

There should be no warnings here — this code is fine.

[delesley]

lib/Analysis/ThreadSafety.cpp

929

It's been a while since I last looked at this code, but I don't think you can use mutable fields in a FactEntry. The analysis creates a FactSet for each program point, but each FactSet simply has pointers (FactIDs) for the underlying FactEntries. If you change the definition of a FactEntry, it will change that definition for every program point. So if you do an unlock on one side of a branch, and change the underlying FactEntry to reflect that, then analysis will then think you have also done the unlock on the other side of the branch.

Any changes should always be done by adding or removing entries from the FactSet, not by mutating the underlying FactEntries.

[aaronpuchert]

Thanks for pointing out my error! Ignoring the implementation for a moment, do you think this is a good idea or will it produce too many false positives? Releasable/relockable scoped capabilities that I have seen keep track of the status, so it makes sense, but maybe there are others out there.

lib/Analysis/ThreadSafety.cpp

929

That explains why there are problems with back edges. Now that you say it I'm actually aware of how the FactManager and FactSet work, but apparently I didn't consider that here.

Would you mind if I make a separate change that returns only const FactEntry* from the FactManager? Maybe that makes it harder to write wrong code in the future.

[delesley]

In D51187#1241354, @aaronpuchert wrote:

Thanks for pointing out my error! Ignoring the implementation for a moment, do you think this is a good idea or will it produce too many false positives? Releasable/relockable scoped capabilities that I have seen keep track of the status, so it makes sense, but maybe there are others out there.

I think this is probably a good idea. Code which manipulates the underlying mutex while it is being managed by another object is a recipe for trouble. It's hard for me to guess how many false positives it will generate without actually running it over our code base, which I personally don't have time to do right now. It should definitely go in -Wthread-safety-beta so it won't break the build. Unfortunately, the before/after checks are still in thread-safety-beta, and they should really be moved out of beta before something else is moved in. The good news is that Matthew O'Niel just volunteered to do that. That is, unfortunately, not a trivial operation, so it may be some weeks before he's done.

[aaronpuchert]

Any changes should always be done by adding or removing entries from the FactSet, not by mutating the underlying FactEntries.

To make that clearer in the code, I made FactEntrys immutable that are managed by FactManager in rC342787.

In D51187#1242620, @delesley wrote:

It should definitely go in -Wthread-safety-beta so it won't break the build. Unfortunately, the before/after checks are still in thread-safety-beta, and they should really be moved out of beta before something else is moved in. The good news is that Matthew O'Niel just volunteered to do that. That is, unfortunately, not a trivial operation, so it may be some weeks before he's done.

That's Ok for me. It's not something that I terribly need, but it seemed to make things more consistent.

Does the migration of the before/after checks include changes to how it is handled? Because I wondered why it doesn't work on S-expressions like the rest of the analysis, but just ValueDecls. That leads to some false positives with more complex expressions:

class A {
public:
  Mutex mu1;
  Mutex mu2 ACQUIRED_AFTER(mu1);
};

class B {
  A a1, a2;
  Mutex lm ACQUIRED_AFTER(a1.mu2);

public:
  void f() {
    a2.mu2.Lock();
    a1.mu1.Lock();    // warns "mutex 'mu1' must be acquired before 'mu2'", but they are on different objects
    a1.mu1.Unlock();
    a2.mu2.Unlock();
  }

  void g() {
    lm.Lock();
    a1.mu1.Lock();
    a1.mu1.Unlock();
    a2.mu1.Lock();    // Warns "mutex 'mu1' must be acquired before 'lm'", but lm talks only about a1.mu2.
    a2.mu1.Unlock();
    lm.Unlock();
  }
};

But maybe that's not the right place to discuss this.

lib/Analysis/ThreadSafety.cpp

public:
   void setDeclared(bool D) { Declared = D; }
 
   virtual void
   handleRemovalFromIntersection(const FactSet &FSet, FactManager &FactMan,
                                 SourceLocation JoinLoc, LockErrorKind LEK,
                                 ThreadSafetyHandler &Handler) const = 0;
   virtual void handleLock(FactSet &FSet, FactManager &FactMan,
                           const FactEntry &entry, ThreadSafetyHandler &Handler,
-                          StringRef DiagKind) const = 0;
+                          StringRef DiagKind) = 0;
   virtual void handleUnlock(FactSet &FSet, FactManager &FactMan,
                             const CapabilityExpr &Cp, SourceLocation UnlockLoc,
                             bool FullyRemove, ThreadSafetyHandler &Handler,
-                            StringRef DiagKind) const = 0;
+                            StringRef DiagKind) = 0;
 
   // Return true if LKind >= LK, where exclusive > shared
   bool isAtLeast(LockKind LK) {
     return  (LKind == LK_Exclusive) || (LK == LK_Shared);
   }
 };
 
 using FactID = unsigned short;
handleRemovalFromIntersection(const FactSet &FSet, FactManager &FactMan,
                                 ThreadSafetyHandler &Handler) const override {
     if (!Managed && !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 {
+                  ThreadSafetyHandler &Handler, StringRef DiagKind) override {
     Handler.handleDoubleLock(DiagKind, entry.toString(), entry.loc());
   }
 
   void handleUnlock(FactSet &FSet, FactManager &FactMan,
                     const CapabilityExpr &Cp, SourceLocation UnlockLoc,
                     bool FullyRemove, ThreadSafetyHandler &Handler,
-                    StringRef DiagKind) const override {
+                    StringRef DiagKind) override {
     FSet.removeLock(FactMan, Cp);
     if (!Cp.negative()) {
       FSet.addLock(FactMan, llvm::make_unique<LockableFactEntry>(
                                 !Cp, LK_Exclusive, UnlockLoc));
     }
   }
 };
 
 class ScopedLockableFactEntry : public FactEntry {
 private:
   SmallVector<const til::SExpr *, 4> UnderlyingMutexes;
+  bool Locked = true; // Are the UnderlyingMutexes currently locked?
 
 public:
   ScopedLockableFactEntry(const CapabilityExpr &CE, SourceLocation Loc,
                           const CapExprSet &Excl, const CapExprSet &Shrd)
       : FactEntry(CE, LK_Exclusive, Loc, false) {
     for (const auto &M : Excl)
       UnderlyingMutexes.push_back(M.sexpr());
     for (const auto &M : Shrd)
for (const auto *UnderlyingMutex : UnderlyingMutexes) {
         // mutex is still held, then warn about the underlying mutex.
         Handler.handleMutexHeldEndOfScope(
             "mutex", sx::toString(UnderlyingMutex), loc(), JoinLoc, LEK);
       }
     }
   }
 
   void handleLock(FactSet &FSet, FactManager &FactMan, const FactEntry &entry,
-                  ThreadSafetyHandler &Handler,
-                  StringRef DiagKind) const override {
+                  ThreadSafetyHandler &Handler, StringRef DiagKind) override {
+    if (Locked)
+      return Handler.handleDoubleLock(DiagKind, entry.toString(), entry.loc());
+    Locked = true;
+
     for (const auto *UnderlyingMutex : UnderlyingMutexes) {
       CapabilityExpr UnderCp(UnderlyingMutex, false);
 
       // We're relocking the underlying mutexes. Warn on double locking.
       if (FSet.findLock(FactMan, UnderCp)) {
         Handler.handleDoubleLock(DiagKind, UnderCp.toString(), entry.loc());
       } else {
         FSet.removeLock(FactMan, !UnderCp);
         FSet.addLock(FactMan, llvm::make_unique<LockableFactEntry>(
                                   UnderCp, entry.kind(), entry.loc()));
       }
     }
   }
 
   void handleUnlock(FactSet &FSet, FactManager &FactMan,
                     const CapabilityExpr &Cp, SourceLocation UnlockLoc,
                     bool FullyRemove, ThreadSafetyHandler &Handler,
-                    StringRef DiagKind) const override {
+                    StringRef DiagKind) override {
     assert(!Cp.negative() && "Managing object cannot be negative.");
+
+    if (Locked) {
       for (const auto *UnderlyingMutex : UnderlyingMutexes) {
         CapabilityExpr UnderCp(UnderlyingMutex, false);
-      auto UnderEntry = llvm::make_unique<LockableFactEntry>(
-          !UnderCp, LK_Exclusive, UnlockLoc);
 
-      if (FullyRemove) {
-        // We're destroying the managing object.
-        // Remove the underlying mutex if it exists; but don't warn.
+        // We're releasing the underlying mutexes.  Warn on dual release.
         if (FSet.findLock(FactMan, UnderCp)) {
           FSet.removeLock(FactMan, UnderCp);
-          FSet.addLock(FactMan, std::move(UnderEntry));
-        }
+          FSet.addLock(FactMan, llvm::make_unique<LockableFactEntry>(
+                                    !UnderCp, LK_Exclusive, UnlockLoc));
         } else {
-        // We're releasing the underlying mutex, but not destroying the
-        // managing object.  Warn on dual release.
-        if (!FSet.findLock(FactMan, UnderCp)) {
           Handler.handleUnmatchedUnlock(DiagKind, UnderCp.toString(),
                                         UnlockLoc);
         }
-        FSet.removeLock(FactMan, UnderCp);
-        FSet.addLock(FactMan, std::move(UnderEntry));
       }
+      Locked = false;
+    } else {
+      // Unlocking an already unlocked scoped capability on destruction is fine.
+      if (!FullyRemove)
+        Handler.handleUnmatchedUnlock(DiagKind, Cp.toString(), UnlockLoc);
     }
     if (FullyRemove)
       FSet.removeLock(FactMan, Cp);
   }
 };
 
 /// Class which implements the core thread safety analysis routines.
 class ThreadSafetyAnalyzer {

 /// \param UnlockLoc The source location of the unlock (only used in error msg)
 void ThreadSafetyAnalyzer::removeLock(FactSet &FSet, const CapabilityExpr &Cp,
                                       SourceLocation UnlockLoc,
                                       bool FullyRemove, LockKind ReceivedKind,
                                       StringRef DiagKind) {
   if (Cp.shouldIgnore())
     return;
 
-  const FactEntry *LDat = FSet.findLock(FactMan, Cp);
+  FactEntry *LDat = FSet.findLock(FactMan, Cp);
   if (!LDat) {
     Handler.handleUnmatchedUnlock(DiagKind, Cp.toString(), UnlockLoc);
     return;
   }
 
   // Generic lock removal doesn't care about lock kind mismatches, but
   // otherwise diagnose when the lock kinds are mismatched.
   if (ReceivedKind != LK_Generic && LDat->kind() != ReceivedKind) {

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

else {
       b = a + 2;
     }
   }
 
   void foo3() {
     MutexLock mulock_a(&mu1);
     MutexLock mulock_b(&mu1); // \
       // expected-warning {{acquiring mutex 'mu1' that is already held}}
-  }
+  } // expected-warning {{releasing mutex 'mu1' that was not held}}
 
   void foo4() {
     MutexLock mulock1(&mu1), mulock2(&mu2);
     a = b+1;
     b = a+1;
   }
 
   void foo5() {
class Foo {
   bool c;
   int a GUARDED_BY(mu_);
 
   void test1();
   void test2();
   void test3();
   void test4();
   void test5();
+  void test6();
+  void test7();
 };
 
 
 void Foo::test1() {
   ReleasableMutexLock rlock(&mu_);
   rlock.Release();
 }
 
void Foo::test3() {
   a = 0;
   rlock.Release();
   a = 1;  // expected-warning {{writing variable 'a' requires holding mutex 'mu_' exclusively}}
 }
 
 void Foo::test4() {
   ReleasableMutexLock rlock(&mu_);
   rlock.Release();
-  rlock.Release();  // expected-warning {{releasing mutex 'mu_' that was not held}}
+  rlock.Release();  // expected-warning {{releasing mutex 'rlock' that was not held}}
 }
 
 void Foo::test5() {
   ReleasableMutexLock rlock(&mu_);
   if (c) {
     rlock.Release();
   }
   // no warning on join point for managed lock.
-  rlock.Release();  // expected-warning {{releasing mutex 'mu_' that was not held}}
+  rlock.Release();  // expected-warning {{releasing mutex 'rlock' that was not held}}
 }
 
+void Foo::test6() {
+  ReleasableMutexLock rlock(&mu_);
+  mu_.Unlock();
+} // expected-warning {{releasing mutex 'mu_' that was not held}}
+
+void Foo::test7() {
+  ReleasableMutexLock rlock(&mu_);
+  rlock.Release();
+  mu_.Lock(); // expected-note {{mutex acquired here}}
+} // expected-warning {{mutex 'mu_' is still held at the end of function}}
+
 
 } // end namespace ReleasableScopedLock
 
 
 namespace RelockableScopedLock {
 
 class SCOPED_LOCKABLE RelockableExclusiveMutexLock {
 public:
void relockShared() {
   scope.PromoteShared();
   print(x);
   x = 5;
 }
 
 void doubleUnlock() {
   RelockableExclusiveMutexLock scope(&mu);
   scope.Unlock();
-  scope.Unlock(); // expected-warning {{releasing mutex 'mu' that was not held}}
+  scope.Unlock(); // expected-warning {{releasing mutex 'scope' that was not held}}
 }
 
 void doubleLock1() {
   RelockableExclusiveMutexLock scope(&mu);
-  scope.Lock(); // expected-warning {{acquiring mutex 'mu' that is already held}}
+  scope.Lock(); // expected-warning {{acquiring mutex 'scope' that is already held}}
 }
 
 void doubleLock2() {
   RelockableExclusiveMutexLock scope(&mu);
   scope.Unlock();
   scope.Lock();
-  scope.Lock(); // expected-warning {{acquiring mutex 'mu' that is already held}}
+  scope.Lock(); // expected-warning {{acquiring mutex 'scope' that is already held}}
 }
 
 void directUnlock() {
   RelockableExclusiveMutexLock scope(&mu);
   mu.Unlock();
-  // Debatable that there is no warning. Currently we don't track in the scoped
-  // object whether it is active, but just check if the contained locks can be
-  // reacquired. Here they can, because mu has been unlocked manually.
-  scope.Lock();
-}
+  scope.Lock(); // expected-warning {{acquiring mutex 'scope' that is already held}}
+} // expected-warning {{releasing mutex 'mu' that was not held}}
 
 void directRelock() {
   RelockableExclusiveMutexLock scope(&mu);
   scope.Unlock();
-  mu.Lock();
-  // Similarly debatable that there is no warning.
-  scope.Unlock();
-}
+  mu.Lock(); // expected-note {{mutex acquired here}}
+  scope.Unlock(); // expected-warning {{releasing mutex 'scope' that was not held}}
+} // expected-warning {{mutex 'mu' is still held at the end of function}}
 
 // Doesn't make a lot of sense, just making sure there is no crash.
 void destructLock() {
   RelockableExclusiveMutexLock scope(&mu);
   scope.~RelockableExclusiveMutexLock();
   scope.Lock(); // Should be UB, so we don't really care.
 }