[Sema] Thread Safety Analysis: Make negative capability typeless.

[ziangwan]

Summary

Re-purpose this revision to make negative capability typeless for clang's thread safety analysis. This is a larger effort so it will take a little bit more time on me.

[nickdesaulniers]

clang/lib/Analysis/ThreadSafety.cpp

2219–2221

The double check of LDat1->kind() == LK_Generic is fishy to me. Particularly the case where LDat1->kind() == LK_Generic is false but LDat2->kind() == LK_Generic is true.

This might be clearer as:

if (LDat2->kind() == LK_Generic)
  continue;
else if (LDat1->kind() == LK_Generic && Modify)
  *Iter1 = Fact;
else {
  ...

Or is there something else to this logic I'm missing?

clang/test/SemaCXX/thread-safety-annotations.h

47

Is this test suite run with other compilers? If not, I think we can remove the case?

[aaronpuchert]

What distinguishes a shared from an exclusive negative capability? Negative capabilities (as I understand them) express the mutex not being held at all, meaning neither in shared nor in exclusive mode.

clang/lib/Analysis/ThreadSafety.cpp

2188–2190

What do these lines mean? That we accept if a lock is shared in one branch and exclusive in the other, and that we make it exclusive after the merge point?

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

135–140

Why would I want these warnings here? This code seems fine to me.

However, I don't see why we don't get acquiring mutex 'mu' requires negative capability '!mu' at line 138, or does that disappear because of the assertion?

[ziangwan]

clang/lib/Analysis/ThreadSafety.cpp

2188–2190

Yes. If at CFG merge point, one path holds type1 lock and the other path holds type2 lock.

We do a type1 + type2 = merged_type and issue warnings if we are doing shared + exclusive merge.

2219–2221

I think your suggestion is to refactor the if statements. What I am thinking is that there are two cases.

1. One of the two locks is generic
   • If so, then take the type of the other non-generic lock (shared or exclusive).
2. Neither of the two locks is generic.

My if statement is trying express that. I am afraid the refactoring is going to lose the logic (as stated in my comment above).

clang/test/SemaCXX/thread-safety-annotations.h

47

Yeah, you are right. I just copied the header definitions from clang thread safety analysis doc.

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

135–140

Showing acquiring mutex 'mu' requires negative capability '!mu' is not in the scope of this patch. Please notice thread safety analysis is still under development.

The reason is that, in one path we have ASSERT_SHARED_CAPABILITY(!mu), and in the other path we have RELEASE(mu). The assertion leads to negative shared capability but the release leads to negative exclusive capability. A merge of the two capabilities (merging "I am not trying to read" versus "I am not trying to write") leads to a warning.

Without my patch, clang will issue a warning for the merge point in test1() but not the merge point in test2().

[aaronpuchert]

clang/test/SemaCXX/thread-safety-annotations.h

47

Why aren't you using the existing macros? The idea was to run the tests with both old and new terminology, and for the time being, I think we should maintain both.

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

135–140

But ASSERT_SHARED_CAPABILITY(!mu) implies that we also don't have an exclusive lock (an exclusive lock is stronger than a shared lock), and RELEASE(mu) without ACQUIRE_SHARED(mu) implies that we have neither a shared nor an exclusive lock as well.

In the end, I have the same question as above: Why do we want two kinds of negative capabilities? Isn't the idea that negative capabilities express the lock not being held at all?

[ziangwan]

This comment was removed by ziangwan.

[ziangwan]

clang/test/SemaCXX/thread-safety-annotations.h

47

There are already tests on existing macros. I want to introduce tests about the new macros as well.

[ziangwan]

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

135–140

The problem is: by the current state of the thread safety analysis, ASSERT_SHARED_CAPABILTIY(!mu) introduces a shared negative capability, whereas RELEASE(mu) and RELEASE_SHARED(mu) introduce an exclusive negative capability, and UNLOCK_FUNCTION(mu) introduces a generic negative capability. All three are different. At merge points, warnings will be issued if different types of negative capability are merged. The current thread safety analysis produces bogus false positive in our code base.

The solution I propose is that we should at least make RELEASE_SHARED(mu) produce a shared negative capability.

Regarding why we should have types for negative capability, thinking about "exclusive !mu" in a reader-writer lock situation, which means "I am not trying to write". However, the code can still read. In other words, "exclusive !mu" does not imply "shared !mu", and the code can still hold the lock in shared state. Without the types of negative capability, we wouldn't be able to express the situation described above.

[aaronpuchert]

clang/test/SemaCXX/thread-safety-annotations.h

47

There are no old and new macros, there are only old and new attributes. The existing macros use both sets of attributes, depending on the value of USE_CAPABILITY with which the tests are run. Using other macro names is just window dressing.

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

135–140

I'm not doubting that there is a bug, but I don't think this is the right solution.

ASSERT_SHARED_CAPABILTIY(!mu) introduces a shared negative capability

We should disallow using "shared" attributes with negative capabilities, and I'm surprised this isn't already the case.

whereas RELEASE(mu) and RELEASE_SHARED(mu) introduce an exclusive negative capability [...] The solution I propose is that we should at least make RELEASE_SHARED(mu) produce a shared negative capability.

Clearly both leave mu in the same (unlocked) state, so why distinguish between them? After the lock is released, whichever mode it has been in before is ancient history. We want to track the current state of the lock.

Regarding why we should have types for negative capability, thinking about "exclusive !mu" in a reader-writer lock situation, which means "I am not trying to write". However, the code can still read.

Negative capabilites aren't about what you are not doing with protected resources, in fact nothing is checked about that. Their purpose is to answer this question: can I draw this lock, or might it already been held? If you are holding a negative capability, that means you can acquire the lock. And when you can acquire the lock, you can do so in either mode. If the lock is currently held in any mode (and hence you're not holding a negative capability), then you can't acquire it in any mode, you have to release it first.

So there is no use in having two kinds of negative capabilities. An "exclusive !mu" should be either "!mu" or "shared(mu)", depending on what the functions expects. The attributes encode state transitions, as I mentioned in D49355#1191544, and there is simply no way to go from "either having no lock or a shared lock" to anywhere else, because all attributes assume a certain previous state.

[ziangwan]

clang/test/SemaCXX/thread-safety-annotations.h

47

Gotcha.

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

135–140

IIUC, if the only type of negative capability we are introducing is exclusive negative capability, ASSERT_SHARED_CAPABILITY(!mu) should introduce an exclusive negative capability as well, right?

The current state of the thread safety analysis is:

1. UNLOCK_FUNCTION(!mu) and RELEASE_GENERIC_CAPABILITY(!mu) -> generic negative capability
2. ASSERT_SHARED_CAPABILITY(!mu) -> shared negative capability.
3. All others -> exclusive negative capability.

A fix would be to let all three produce exclusive negative capability, which essentially means there is no type associated with negative capability. This fix could also fix my bug.

The reason why I am still calling it "exclusive" is that there is a flag IsShared() associated with capability objects no matter whether it is positive or negative.

[aaronpuchert]

The primary purpose of Thread Safety Analysis is to make sure that accesses to shared resources are protected. That's why we only track whether a lock is available by default (i.e. without -Wthread-safety-negative), locks that we don't know anything about are assumed to be unlocked. As a side effect, we can detect double unlocks and lock/unlock-kind mismatches.

But we cannot detect double locks (and deadlocks) over function boundaries. This is why negative capabilities were introduced. But because not everybody cares about that enough to warrant more annotations, it's not on by default.

Regarding why we should have types for negative capability, thinking about "exclusive !mu" in a reader-writer lock situation, which means "I am not trying to write". However, the code can still read.

Negative capabilities don't declare that we're not reading/writing: we can't do that without holding the actual (positive) capability anyway!

Having the capability !mu just means that we can assume mu is not locked. We will then usually acquire the mu (otherwise the annotation wouldn't be needed).

[aaronpuchert]

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

135–140

Yes, that sounds right. In the long-term I would want negative capabilities to be neither exclusive nor shared, but for now I would take them to be exclusive, to be consistent with the kinds of attributes we use them with.

In my opinion we should also warn about ASSERT_SHARED_CAPABILITY(!mu) in -Wthread-safety-attributes.

[aaronpuchert]

This is a larger effort so it will take a little bit more time on me.

This is fine, but could you add a "Plan changes" action then? This will make the revision disappear from the active review queue.

[aaronpuchert]

A fix would be to let all three produce exclusive negative capability, which essentially means there is no type associated with negative capability. This fix could also fix my bug.

As discussed, this is how it should be solved. I'm changing the state so that it's clear there is nothing to review here currently.

clang/lib/Analysis/ThreadSafety.cpp

public:
   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;
   virtual void handleUnlock(FactSet &FSet, FactManager &FactMan,
                             const CapabilityExpr &Cp, SourceLocation UnlockLoc,
-                            bool FullyRemove, ThreadSafetyHandler &Handler,
+                            bool FullyRemove, LockKind ReceivedKind,
+                            ThreadSafetyHandler &Handler,
                             StringRef DiagKind) const = 0;
 
   // Return true if LKind >= LK, where exclusive > shared
   bool isAtLeast(LockKind LK) const {
     return  (LKind == LK_Exclusive) || (LK == LK_Shared);
   }
 };
 
public:
   void handleLock(FactSet &FSet, FactManager &FactMan, const FactEntry &entry,
                   ThreadSafetyHandler &Handler,
                   StringRef DiagKind) const override {
     Handler.handleDoubleLock(DiagKind, entry.toString(), loc(), entry.loc());
   }
 
   void handleUnlock(FactSet &FSet, FactManager &FactMan,
                     const CapabilityExpr &Cp, SourceLocation UnlockLoc,
-                    bool FullyRemove, ThreadSafetyHandler &Handler,
+                    bool FullyRemove, LockKind ReceivedKind,
+                    ThreadSafetyHandler &Handler,
                     StringRef DiagKind) const override {
     FSet.removeLock(FactMan, Cp);
     if (!Cp.negative()) {
       FSet.addLock(FactMan, llvm::make_unique<LockableFactEntry>(
-                                !Cp, LK_Exclusive, UnlockLoc));
+                                !Cp, ReceivedKind, UnlockLoc));
     }
   }
 };
 
 class ScopedLockableFactEntry : public FactEntry {
 private:
   enum UnderlyingCapabilityKind {
     UCK_Acquired,          ///< Any kind of acquired capability.
void handleLock(FactSet &FSet, FactManager &FactMan, const FactEntry &entry,
                   StringRef DiagKind) const override {
     for (const auto &UnderlyingMutex : UnderlyingMutexes) {
       CapabilityExpr UnderCp(UnderlyingMutex.getPointer(), false);
 
       if (UnderlyingMutex.getInt() == UCK_Acquired)
         lock(FSet, FactMan, UnderCp, entry.kind(), entry.loc(), &Handler,
              DiagKind);
       else
-        unlock(FSet, FactMan, UnderCp, entry.loc(), &Handler, DiagKind);
+        unlock(FSet, FactMan, UnderCp, entry.loc(), entry.kind(), &Handler,
+               DiagKind);
     }
   }
 
   void handleUnlock(FactSet &FSet, FactManager &FactMan,
                     const CapabilityExpr &Cp, SourceLocation UnlockLoc,
-                    bool FullyRemove, ThreadSafetyHandler &Handler,
+                    bool FullyRemove, LockKind ReceivedKind,
+                    ThreadSafetyHandler &Handler,
                     StringRef DiagKind) const override {
     assert(!Cp.negative() && "Managing object cannot be negative.");
     for (const auto &UnderlyingMutex : UnderlyingMutexes) {
       CapabilityExpr UnderCp(UnderlyingMutex.getPointer(), false);
 
       // Remove/lock the underlying mutex if it exists/is still unlocked; warn
       // on double unlocking/locking if we're not destroying the scoped object.
       ThreadSafetyHandler *TSHandler = FullyRemove ? nullptr : &Handler;
       if (UnderlyingMutex.getInt() == UCK_Acquired) {
-        unlock(FSet, FactMan, UnderCp, UnlockLoc, TSHandler, DiagKind);
+        unlock(FSet, FactMan, UnderCp, UnlockLoc, ReceivedKind, TSHandler,
+               DiagKind);
       } else {
         LockKind kind = UnderlyingMutex.getInt() == UCK_ReleasedShared
                             ? LK_Shared
                             : LK_Exclusive;
         lock(FSet, FactMan, UnderCp, kind, UnlockLoc, TSHandler, DiagKind);
       }
     }
     if (FullyRemove)
void lock(FactSet &FSet, FactManager &FactMan, const CapabilityExpr &Cp,
     } else {
       FSet.removeLock(FactMan, !Cp);
       FSet.addLock(FactMan,
                    llvm::make_unique<LockableFactEntry>(Cp, kind, loc));
     }
   }
 
   void unlock(FactSet &FSet, FactManager &FactMan, const CapabilityExpr &Cp,
-              SourceLocation loc, ThreadSafetyHandler *Handler,
-              StringRef DiagKind) const {
+              SourceLocation loc, LockKind kind,
+              ThreadSafetyHandler *Handler, StringRef DiagKind) const {
     if (FSet.findLock(FactMan, Cp)) {
       FSet.removeLock(FactMan, Cp);
       FSet.addLock(FactMan, llvm::make_unique<LockableFactEntry>(
-                                !Cp, LK_Exclusive, loc));
+                                !Cp, kind, loc));
     } else if (Handler) {
       Handler->handleUnmatchedUnlock(DiagKind, Cp.toString(), loc);
     }
   }
 };
 
 /// Class which implements the core thread safety analysis routines.
 class ThreadSafetyAnalyzer {
void ThreadSafetyAnalyzer::removeLock(FactSet &FSet, const CapabilityExpr &Cp,
 
   // 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) {
     Handler.handleIncorrectUnlockKind(DiagKind, Cp.toString(), LDat->kind(),
                                       ReceivedKind, LDat->loc(), UnlockLoc);
   }
 
-  LDat->handleUnlock(FSet, FactMan, Cp, UnlockLoc, FullyRemove, Handler,
-                     DiagKind);
+  LDat->handleUnlock(FSet, FactMan, Cp, UnlockLoc, FullyRemove, ReceivedKind,
+                     Handler, DiagKind);
 }
 
 /// Extract the list of mutexIDs from the attribute on an expression,
 /// and push them onto Mtxs, discarding any duplicates.
 template <typename AttrType>
 void ThreadSafetyAnalyzer::getMutexIDs(CapExprSet &Mtxs, AttrType *Attr,
                                        const Expr *Exp, const NamedDecl *D,
                                        VarDecl *SelfDecl) {

 /// locks in the symmetric difference.
 ///
 /// This function is used at a merge point in the CFG when comparing the lockset
 /// of each branch being merged. For example, given the following sequence:
 /// A; if () then B; else C; D; we need to check that the lockset after B and C
 /// are the same. In the event of a difference, we use the intersection of these
 /// two locksets at the start of D.
 ///
+/// At a merge point, the same lock in the two sets can be different kinds,
+/// exclusive, shared or generic. generic type is incured only by
+/// UNLOCK_FUNCTION and RELEASE_GENERIC_CAPABILITY attributes.
+/// shared + exclusive = exclusive
+/// generic + exclusive = exclusive
+/// generic + shared = shared
+/// A warning will also be issued for shared + exclusive merge.
+///
 /// \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
+/// \param Modify whether to modify FSet1 or not.
 void ThreadSafetyAnalyzer::intersectAndWarn(FactSet &FSet1,
                                             const FactSet &FSet2,
                                             SourceLocation JoinLoc,
                                             LockErrorKind LEK1,
                                             LockErrorKind LEK2,
                                             bool Modify) {
   FactSet FSet1Orig = FSet1;
 
   // Find locks in FSet2 that conflict or are not in FSet1, and warn.
   for (const auto &Fact : FSet2) {
     const FactEntry *LDat1 = nullptr;
     const FactEntry *LDat2 = &FactMan[Fact];
     FactSet::iterator Iter1  = FSet1.findLockIter(FactMan, *LDat2);
     if (Iter1 != FSet1.end()) LDat1 = &FactMan[*Iter1];
 
     if (LDat1) {
       if (LDat1->kind() != LDat2->kind()) {
+        // If one lock is generic, take the type of the other lock, which
+        // is the lock in FSet2. Otherwise, both locks are not generic.
+        // We are merging exclusive with shared
+        if (LDat1->kind() == LK_Generic || LDat2->kind() == LK_Generic) {
+          // No warning is issued in this case.
+          if (Modify && LDat1->kind() == LK_Generic) {
+            *Iter1 = Fact;
+          }
+        } else {
           Handler.handleExclusiveAndShared("mutex", LDat2->toString(),
                                           LDat2->loc(), LDat1->loc());
           if (Modify && LDat1->kind() != LK_Exclusive) {
             // Take the exclusive lock, which is the one in FSet2.
             *Iter1 = Fact;
           }
         }
-      else if (Modify && LDat1->asserted() && !LDat2->asserted()) {
+      } else if (Modify && LDat1->asserted() && !LDat2->asserted()) {
         // The non-asserted lock in FSet2 is the one we want to track.
         *Iter1 = Fact;
       }
     } else {
       LDat2->handleRemovalFromIntersection(FSet2, FactMan, JoinLoc, LEK1,
                                            Handler);
     }
   }

clang/test/SemaCXX/thread-safety-annotations.h

 
 // Common
 #define SCOPED_LOCKABLE                 __attribute__((scoped_lockable))
 #define ACQUIRED_AFTER(...)             __attribute__((acquired_after(__VA_ARGS__)))
 #define ACQUIRED_BEFORE(...)            __attribute__((acquired_before(__VA_ARGS__)))
 #define LOCK_RETURNED(x)                __attribute__((lock_returned(x)))
 #define LOCKS_EXCLUDED(...)             __attribute__((locks_excluded(__VA_ARGS__)))
 #define NO_THREAD_SAFETY_ANALYSIS       __attribute__((no_thread_safety_analysis))
+
+
+// New terminologies:
+// Enable thread safety attributes only with clang.
+// The attributes can be safely erased when compiling with other compilers.
+#if defined(__clang__) && (!defined(SWIG))
+#define THREAD_ANNOTATION_ATTRIBUTE__(x)   __attribute__((x))
+#else
+#define THREAD_ANNOTATION_ATTRIBUTE__(x)   // no-op
+#endif
+
+#define CAPABILITY(x) \
+  THREAD_ANNOTATION_ATTRIBUTE__(capability(x))
+
+#define SCOPED_CAPABILITY \
+  THREAD_ANNOTATION_ATTRIBUTE__(scoped_lockable)
+
+#define REQUIRES(...) \
+  THREAD_ANNOTATION_ATTRIBUTE__(requires_capability(__VA_ARGS__))
+
+#define REQUIRES_SHARED(...) \
+  THREAD_ANNOTATION_ATTRIBUTE__(requires_shared_capability(__VA_ARGS__))
+
+#define ACQUIRE(...) \
+  THREAD_ANNOTATION_ATTRIBUTE__(acquire_capability(__VA_ARGS__))
+
+#define ACQUIRE_SHARED(...) \
+  THREAD_ANNOTATION_ATTRIBUTE__(acquire_shared_capability(__VA_ARGS__))
+
+#define RELEASE(...) \
+  THREAD_ANNOTATION_ATTRIBUTE__(release_capability(__VA_ARGS__))
+
+#define RELEASE_SHARED(...) \
+  THREAD_ANNOTATION_ATTRIBUTE__(release_shared_capability(__VA_ARGS__))
+
+#define TRY_ACQUIRE(...) \
+  THREAD_ANNOTATION_ATTRIBUTE__(try_acquire_capability(__VA_ARGS__))
+
+#define TRY_ACQUIRE_SHARED(...) \
+  THREAD_ANNOTATION_ATTRIBUTE__(try_acquire_shared_capability(__VA_ARGS__))
+
+#define EXCLUDES(...) \
+  THREAD_ANNOTATION_ATTRIBUTE__(locks_excluded(__VA_ARGS__))
+
+#define ASSERT_CAPABILITY(x) \
+  THREAD_ANNOTATION_ATTRIBUTE__(assert_capability(x))
+
+#define ASSERT_SHARED_CAPABILITY(x) \
+  THREAD_ANNOTATION_ATTRIBUTE__(assert_shared_capability(x))
+
+#define RETURN_CAPABILITY(x) \
+  THREAD_ANNOTATION_ATTRIBUTE__(lock_returned(x))

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

class TemplateClass {
   template <typename B>
   static void Function(Foo *F)
       EXCLUSIVE_LOCKS_REQUIRED(F->mutex()) UNLOCK_FUNCTION(F->mutex()) {}
 };
 
 void test() { TemplateClass<int> TC; }
 
 }  // end namespace DoubleAttribute
+
+
+// Test new terminology and accurate unlock.
+class CAPABILITY("mutex") NewMutex {
+public:
+  void Lock() ACQUIRE();
+  void Unlock() RELEASE();
+
+  void ReaderLock() ACQUIRE_SHARED();
+  void ReaderUnlock() RELEASE_SHARED();
+
+  void GenericUnlock() UNLOCK_FUNCTION();
+
+  // for negative capabilities
+  const NewMutex& operator!() const { return *this; }
+};
+
+
+namespace TestMerge {
+
+NewMutex mu;
+bool condition;
+
+void assertNotHeld() ASSERT_SHARED_CAPABILITY(!mu);
+
+void test1() {
+  if (condition) {
+    assertNotHeld();
+  } else {
+    mu.ReaderLock();
+    mu.ReaderUnlock();
+  } // merge point no problem.
+}
+
+void test2() {
+  if (condition) {
+    assertNotHeld(); // expected-warning {{mutex '!mu' is acquired exclusively and shared in the same scope}}
+  } else {
+    mu.Lock();
+    mu.Unlock(); // expected-warning {{the other acquisition of mutex '!mu' is here}}
+  }
+}
+
+void test3() {
+  if (condition) {
+    assertNotHeld();
+  } else {
+    mu.Lock();
+    mu.GenericUnlock();
+  } // merge point no problem.
+}
+
+} // end namespace NewTerminology