[analyzer] Implement shared semantics checks for XNU functions in PthreadLockChecker

[ASDenysPetrov]

Summary

Implement shared semantics checks for correct use of XNU functions for shared and exclusive mutexes.

Clarification:
Shared semantics says that if a lock has been acquired as shared, so it shall be released as shared as well. And vice versa, unique(usual) acquisition shall be followed by a unique unlock. This produces so-called pairs "shared-shared" and "unique-unique" Any mixed sequences of "shared-unique" or "unique-shared" are ill-formed and can lead to undefined behavior.

In particular affected functions lck_rw_lock_shared and lck_rw_unlock_shared are guided by documentaion here
https://developer.apple.com/library/archive/documentation/Darwin/Conceptual/KernelProgramming/synchronization/synchronization.html#//apple_ref/doc/uid/TP30000905-CH218-BABCHEIA
Quote: "You should always be careful when using these functions, as unlocking a lock held in shared mode using an exclusive call or vice-versa will lead to undefined results."

[ASDenysPetrov]

Fixed some missed conditions. Added more tests.

[ASDenysPetrov]

Minor fixes.

[ASDenysPetrov]

Test fix.

[ASDenysPetrov]

It would be nice if someone had time to look at this. Thanks.

[baloghadamsoftware]

In D87146#2294423, @ASDenysPetrov wrote:

It would be nice if someone had time to look at this. Thanks.

I am just looking, but I am not a pthread expert.

[baloghadamsoftware]

In D87146#2294514, @baloghadamsoftware wrote:

In D87146#2294423, @ASDenysPetrov wrote:

It would be nice if someone had time to look at this. Thanks.

I am just looking, but I am not a pthread expert.

Sorry, absolutely no competence.

[ASDenysPetrov]

@baloghadamsoftware

Sorry, absolutely no competence.

That's OK. I've added a clarification section to the summary to make it easier to understand my intentions.

[ASDenysPetrov]

Just a ping. Let me, please, do smth with this revision.

[ASDenysPetrov]

Hey, folk. Please, look at this revision.
This is the 2nd revision from the stack of 3. Its aim is preparing the field for the 3rd revision (also welcome to review). The 1st one has been closed.

[ASDenysPetrov]

Just want to load this revision in scope of the stack. I need you review for this. Thanks.

[steakhal]

Could you please give a few links to some documentation about the functions you are trying to model?
Is https://developer.apple.com/library/archive/documentation/Darwin/Conceptual/KernelProgramming/synchronization/synchronization.html a legitimate resource for this?

It's really important to bake the proper semantic rules into the modeling.

[ASDenysPetrov]

@steakhal

Could you please give a few links to some documentation about the functions you are trying to model?

Yes, you a re right. I've edited the summary with the link.

clang/lib/StaticAnalyzer/Checkers/PthreadLockChecker.cpp

 using namespace ento;
 
 namespace {
 
 struct LockState {
   enum Kind {
     Destroyed,
     Locked,
+    SharedLocked,
     Unlocked,
+    SharedUnlocked,
     UntouchedAndPossiblyDestroyed,
     UnlockedAndPossiblyDestroyed
   } K;
 
 private:
   LockState(Kind K) : K(K) {}
 
 public:
   static LockState getLocked() { return LockState(Locked); }
+  static LockState getSharedLocked() { return LockState(SharedLocked); }
   static LockState getUnlocked() { return LockState(Unlocked); }
+  static LockState getSharedUnlocked() { return LockState(SharedUnlocked); }
   static LockState getDestroyed() { return LockState(Destroyed); }
   static LockState getUntouchedAndPossiblyDestroyed() {
     return LockState(UntouchedAndPossiblyDestroyed);
   }
   static LockState getUnlockedAndPossiblyDestroyed() {
     return LockState(UnlockedAndPossiblyDestroyed);
   }
 
   bool operator==(const LockState &X) const { return K == X.K; }
 
   bool isLocked() const { return K == Locked; }
+  bool isSharedLocked() const { return K == SharedLocked; }
   bool isUnlocked() const { return K == Unlocked; }
+  bool isSharedUnlocked() const { return K == SharedUnlocked; }
   bool isDestroyed() const { return K == Destroyed; }
   bool isUntouchedAndPossiblyDestroyed() const {
     return K == UntouchedAndPossiblyDestroyed;
   }
   bool isUnlockedAndPossiblyDestroyed() const {
     return K == UnlockedAndPossiblyDestroyed;
   }
 
CallDescriptionMap<FnCheck> PThreadCallbacks = {
       // TODO: lck_rw_alloc_init(2 arguments) => returns the mutex.
 
       // Acquire.
       {{"pthread_mutex_lock", 1}, &PthreadLockChecker::AcquirePthreadLock},
       {{"pthread_rwlock_rdlock", 1}, &PthreadLockChecker::AcquirePthreadLock},
       {{"pthread_rwlock_wrlock", 1}, &PthreadLockChecker::AcquirePthreadLock},
       {{"lck_mtx_lock", 1}, &PthreadLockChecker::AcquireXNULock},
       {{"lck_rw_lock_exclusive", 1}, &PthreadLockChecker::AcquireXNULock},
-      {{"lck_rw_lock_shared", 1}, &PthreadLockChecker::AcquireXNULock},
+      {{"lck_rw_lock_shared", 1}, &PthreadLockChecker::AcquireXNULockShared},
 
       // Try.
       {{"pthread_mutex_trylock", 1}, &PthreadLockChecker::TryPthreadLock},
       {{"pthread_rwlock_tryrdlock", 1}, &PthreadLockChecker::TryPthreadLock},
       {{"pthread_rwlock_trywrlock", 1}, &PthreadLockChecker::TryPthreadLock},
       {{"lck_mtx_try_lock", 1}, &PthreadLockChecker::TryXNULock},
       {{"lck_rw_try_lock_exclusive", 1}, &PthreadLockChecker::TryXNULock},
-      {{"lck_rw_try_lock_shared", 1}, &PthreadLockChecker::TryXNULock},
+      {{"lck_rw_try_lock_shared", 1}, &PthreadLockChecker::TryXNULockShared},
 
       // Release.
       {{"pthread_mutex_unlock", 1}, &PthreadLockChecker::ReleaseAnyLock},
       {{"pthread_rwlock_unlock", 1}, &PthreadLockChecker::ReleaseAnyLock},
       {{"lck_mtx_unlock", 1}, &PthreadLockChecker::ReleaseAnyLock},
       {{"lck_rw_unlock_exclusive", 1}, &PthreadLockChecker::ReleaseAnyLock},
-      {{"lck_rw_unlock_shared", 1}, &PthreadLockChecker::ReleaseAnyLock},
+      {{"lck_rw_unlock_shared", 1}, &PthreadLockChecker::ReleaseAnyLockShared},
       {{"lck_rw_done", 1}, &PthreadLockChecker::ReleaseAnyLock},
 
       // Destroy.
       {{"pthread_mutex_destroy", 1}, &PthreadLockChecker::DestroyPthreadLock},
       {{"lck_mtx_destroy", 2}, &PthreadLockChecker::DestroyXNULock},
       // TODO: pthread_rwlock_destroy(1 argument).
       // TODO: lck_rw_destroy(2 arguments).
   };
void InitLockAux(const CallEvent &Call, CheckerContext &C,
                    const Expr *MtxExpr, SVal MtxVal,
                    CheckerKind CheckKind) const;
 
   // Lock, Try-lock.
   void AcquirePthreadLock(const CallEvent &Call, CheckerContext &C,
                           CheckerKind CheckKind) const;
   void AcquireXNULock(const CallEvent &Call, CheckerContext &C,
                       CheckerKind CheckKind) const;
+  void AcquireXNULockShared(const CallEvent &Call, CheckerContext &C,
+                            CheckerKind CheckKind) const;
   void TryPthreadLock(const CallEvent &Call, CheckerContext &C,
                       CheckerKind CheckKind) const;
   void TryXNULock(const CallEvent &Call, CheckerContext &C,
                   CheckerKind CheckKind) const;
+  void TryXNULockShared(const CallEvent &Call, CheckerContext &C,
+                        CheckerKind CheckKind) const;
   void TryFuchsiaLock(const CallEvent &Call, CheckerContext &C,
                       CheckerKind CheckKind) const;
   void TryC11Lock(const CallEvent &Call, CheckerContext &C,
                   CheckerKind CheckKind) const;
   void AcquireLockAux(const CallEvent &Call, CheckerContext &C,
                       const Expr *MtxExpr, SVal MtxVal, bool IsTryLock,
-                      LockingSemantics Semantics, CheckerKind CheckKind) const;
+                      bool IsShared, LockingSemantics Semantics,
+                      CheckerKind CheckKind) const;
 
   // Release.
   void ReleaseAnyLock(const CallEvent &Call, CheckerContext &C,
                       CheckerKind CheckKind) const;
+  void ReleaseAnyLockShared(const CallEvent &Call, CheckerContext &C,
+                            CheckerKind CheckKind) const;
   void ReleaseLockAux(const CallEvent &Call, CheckerContext &C,
-                      const Expr *MtxExpr, SVal MtxVal,
+                      const Expr *MtxExpr, SVal MtxVal, bool IsShared,
+                      enum LockingSemantics Semantics,
                       CheckerKind CheckKind) const;
 
   // Destroy.
   void DestroyPthreadLock(const CallEvent &Call, CheckerContext &C,
                           CheckerKind CheckKind) const;
   void DestroyXNULock(const CallEvent &Call, CheckerContext &C,
                       CheckerKind CheckKind) const;
   void DestroyLockAux(const CallEvent &Call, CheckerContext &C,
void printState(raw_ostream &Out, ProgramStateRef State, const char *NL,
                   const char *Sep) const override;
 
 private:
   mutable std::unique_ptr<BugType> BT_doublelock[CK_NumCheckKinds];
   mutable std::unique_ptr<BugType> BT_doubleunlock[CK_NumCheckKinds];
   mutable std::unique_ptr<BugType> BT_destroylock[CK_NumCheckKinds];
   mutable std::unique_ptr<BugType> BT_initlock[CK_NumCheckKinds];
   mutable std::unique_ptr<BugType> BT_lor[CK_NumCheckKinds];
+  mutable std::unique_ptr<BugType> BT_shared[CK_NumCheckKinds];
 
   void initBugType(CheckerKind CheckKind) const {
     if (BT_doublelock[CheckKind])
       return;
     BT_doublelock[CheckKind].reset(
         new BugType{CheckNames[CheckKind], "Double locking", "Lock checker"});
     BT_doubleunlock[CheckKind].reset(
         new BugType{CheckNames[CheckKind], "Double unlocking", "Lock checker"});
     BT_destroylock[CheckKind].reset(new BugType{
         CheckNames[CheckKind], "Use destroyed lock", "Lock checker"});
     BT_initlock[CheckKind].reset(new BugType{
         CheckNames[CheckKind], "Init invalid lock", "Lock checker"});
     BT_lor[CheckKind].reset(new BugType{CheckNames[CheckKind],
                                         "Lock order reversal", "Lock checker"});
+    BT_shared[CheckKind].reset(new BugType{
+        CheckNames[CheckKind], "Shared semantics misuse", "Lock checker"});
   }
 };
 } // end anonymous namespace
 
 // A stack of locks for tracking lock-unlock order.
 REGISTER_LIST_WITH_PROGRAMSTATE(LockSet, const MemRegion *)
 
 // An entry for tracking lock states.
void PthreadLockChecker::printState(raw_ostream &Out, ProgramStateRef State,
   }
 
   // TODO: Dump destroyed mutex symbols?
 }
 
 void PthreadLockChecker::AcquirePthreadLock(const CallEvent &Call,
                                             CheckerContext &C,
                                             CheckerKind CheckKind) const {
-  AcquireLockAux(Call, C, Call.getArgExpr(0), Call.getArgSVal(0), false,
+  AcquireLockAux(Call, C, Call.getArgExpr(0), Call.getArgSVal(0), false, false,
                  PthreadSemantics, CheckKind);
 }
 
 void PthreadLockChecker::AcquireXNULock(const CallEvent &Call,
                                         CheckerContext &C,
                                         CheckerKind CheckKind) const {
-  AcquireLockAux(Call, C, Call.getArgExpr(0), Call.getArgSVal(0), false,
+  AcquireLockAux(Call, C, Call.getArgExpr(0), Call.getArgSVal(0), false, false,
+                 XNUSemantics, CheckKind);
+}
+
+void PthreadLockChecker::AcquireXNULockShared(const CallEvent &Call,
+                                              CheckerContext &C,
+                                              CheckerKind CheckKind) const {
+  AcquireLockAux(Call, C, Call.getArgExpr(0), Call.getArgSVal(0), false, true,
                  XNUSemantics, CheckKind);
 }
 
 void PthreadLockChecker::TryPthreadLock(const CallEvent &Call,
                                         CheckerContext &C,
                                         CheckerKind CheckKind) const {
-  AcquireLockAux(Call, C, Call.getArgExpr(0), Call.getArgSVal(0), true,
+  AcquireLockAux(Call, C, Call.getArgExpr(0), Call.getArgSVal(0), true, false,
                  PthreadSemantics, CheckKind);
 }
 
 void PthreadLockChecker::TryXNULock(const CallEvent &Call, CheckerContext &C,
                                     CheckerKind CheckKind) const {
-  AcquireLockAux(Call, C, Call.getArgExpr(0), Call.getArgSVal(0), true,
-                 PthreadSemantics, CheckKind);
+  AcquireLockAux(Call, C, Call.getArgExpr(0), Call.getArgSVal(0), true, false,
+                 XNUSemantics, CheckKind);
+}
+
+void PthreadLockChecker::TryXNULockShared(const CallEvent &Call,
+                                          CheckerContext &C,
+                                          CheckerKind CheckKind) const {
+  AcquireLockAux(Call, C, Call.getArgExpr(0), Call.getArgSVal(0), true, true,
+                 XNUSemantics, CheckKind);
 }
 
 void PthreadLockChecker::TryFuchsiaLock(const CallEvent &Call,
                                         CheckerContext &C,
                                         CheckerKind CheckKind) const {
-  AcquireLockAux(Call, C, Call.getArgExpr(0), Call.getArgSVal(0), true,
+  AcquireLockAux(Call, C, Call.getArgExpr(0), Call.getArgSVal(0), true, false,
                  PthreadSemantics, CheckKind);
 }
 
 void PthreadLockChecker::TryC11Lock(const CallEvent &Call, CheckerContext &C,
                                     CheckerKind CheckKind) const {
-  AcquireLockAux(Call, C, Call.getArgExpr(0), Call.getArgSVal(0), true,
+  AcquireLockAux(Call, C, Call.getArgExpr(0), Call.getArgSVal(0), true, false,
                  PthreadSemantics, CheckKind);
 }
 
 void PthreadLockChecker::AcquireLockAux(const CallEvent &Call,
                                         CheckerContext &C, const Expr *MtxExpr,
                                         SVal MtxVal, bool IsTryLock,
+                                        bool IsShared,
                                         enum LockingSemantics Semantics,
                                         CheckerKind CheckKind) const {
   if (!ChecksEnabled[CheckKind])
     return;
 
   const MemRegion *lockR = MtxVal.getAsRegion();
   if (!lockR)
     return;
void PthreadLockChecker::AcquireLockAux(const CallEvent &Call,
   } else {
     // XNU locking semantics return void on non-try locks
     assert((Semantics == XNUSemantics) && "Unknown locking semantics");
     lockSucc = state;
   }
 
   // Record that the lock was acquired.
   lockSucc = lockSucc->add<LockSet>(lockR);
-  lockSucc = lockSucc->set<LockMap>(lockR, LockState::getLocked());
+  auto State = IsShared ? LockState::getSharedLocked() : LockState::getLocked();
+  lockSucc = lockSucc->set<LockMap>(lockR, State);
   C.addTransition(lockSucc);
 }
 
 void PthreadLockChecker::ReleaseAnyLock(const CallEvent &Call,
                                         CheckerContext &C,
                                         CheckerKind CheckKind) const {
-  ReleaseLockAux(Call, C, Call.getArgExpr(0), Call.getArgSVal(0), CheckKind);
+  ReleaseLockAux(Call, C, Call.getArgExpr(0), Call.getArgSVal(0), false,
+                 NotApplicable, CheckKind);
+}
+
+void PthreadLockChecker::ReleaseAnyLockShared(const CallEvent &Call,
+                                              CheckerContext &C,
+                                              CheckerKind CheckKind) const {
+  ReleaseLockAux(Call, C, Call.getArgExpr(0), Call.getArgSVal(0), true,
+                 NotApplicable, CheckKind);
 }
 
 void PthreadLockChecker::ReleaseLockAux(const CallEvent &Call,
                                         CheckerContext &C, const Expr *MtxExpr,
-                                        SVal MtxVal,
+                                        SVal MtxVal, bool IsShared,
+                                        enum LockingSemantics Semantics,
                                         CheckerKind CheckKind) const {
   if (!ChecksEnabled[CheckKind])
     return;
 
   const MemRegion *lockR = MtxVal.getAsRegion();
   if (!lockR)
     return;
 
   ProgramStateRef state = C.getState();
   const SymbolRef *sym = state->get<DestroyRetVal>(lockR);
   if (sym)
     state = resolvePossiblyDestroyedMutex(state, lockR, sym);
 
   if (const LockState *LState = state->get<LockMap>(lockR)) {
     if (LState->isUnlocked()) {
       reportBug(C, BT_doubleunlock, MtxExpr, CheckKind,
                 "This lock has already been unlocked");
       return;
     } else if (LState->isDestroyed()) {
       reportBug(C, BT_destroylock, MtxExpr, CheckKind,
                 "This lock has already been destroyed");
       return;
+    } else if (LState->isLocked()) {
+      if (IsShared) {
+        reportBug(
+            C, BT_shared, MtxExpr, CheckKind,
+            "This lock has been acquired exclusively, but shared unlock used");
+        return;
+      }
+    } else if (LState->isSharedLocked()) {
+      if (!IsShared) {
+        reportBug(
+            C, BT_shared, MtxExpr, CheckKind,
+            "This lock has been acquired as shared, but exclusive unlock used");
+        return;
+      }
     }
   }
 
   LockSetTy LS = state->get<LockSet>();
 
   if (!LS.isEmpty()) {
     const MemRegion *firstLockR = LS.getHead();
     if (firstLockR != lockR) {
       reportBug(C, BT_lor, MtxExpr, CheckKind,
                 "This was not the most recently acquired lock. Possible lock "
                 "order reversal");
       return;
     }
     // Record that the lock was released.
     state = state->set<LockSet>(LS.getTail());
   }
 
-  state = state->set<LockMap>(lockR, LockState::getUnlocked());
+  auto State =
+      IsShared ? LockState::getSharedUnlocked() : LockState::getUnlocked();
+  state = state->set<LockMap>(lockR, State);
   C.addTransition(state);
 }
 
 void PthreadLockChecker::DestroyPthreadLock(const CallEvent &Call,
                                             CheckerContext &C,
                                             CheckerKind CheckKind) const {
   DestroyLockAux(Call, C, Call.getArgExpr(0), Call.getArgSVal(0),
                  PthreadSemantics, CheckKind);

clang/test/Analysis/Inputs/system-header-simulator-for-pthread-lock.h

typedef struct {
   void  *foo;
 } lck_grp_t;
 
 typedef struct {
   void *foo;
 } lck_rw_t;
 
 typedef pthread_mutex_t lck_mtx_t;
+typedef pthread_mutex_t lck_mtx_t;
 
 extern void fake_system_function();
 extern void fake_system_function_that_takes_a_mutex(pthread_mutex_t *mtx);
 
 extern int pthread_mutex_lock(pthread_mutex_t *);
 extern int pthread_mutex_unlock(pthread_mutex_t *);
 extern int pthread_mutex_trylock(pthread_mutex_t *);
 extern int pthread_mutex_destroy(pthread_mutex_t *);
 extern int pthread_mutex_init(pthread_mutex_t  *mutex, const pthread_mutexattr_t *mutexattr);
 
 typedef int boolean_t;
 extern void lck_mtx_lock(lck_mtx_t *);
 extern void lck_mtx_unlock(lck_mtx_t *);
 extern boolean_t lck_mtx_try_lock(lck_mtx_t *);
+extern boolean_t lck_rw_try_lock_shared(lck_rw_t *lck);
+extern boolean_t lck_rw_try_lock_exclusive(lck_rw_t *lck);
 extern void lck_mtx_destroy(lck_mtx_t *lck, lck_grp_t *grp);
 
 extern void lck_rw_lock_exclusive(lck_rw_t *lck);
 extern void lck_rw_unlock_exclusive(lck_rw_t *lck);
 extern void lck_rw_lock_shared(lck_rw_t *lck);
 extern void lck_rw_unlock_shared(lck_rw_t *lck);

clang/test/Analysis/pthreadlock.c

void ok31(void) {
   pthread_mutex_init(&local_mtx, NULL);
   pthread_mutex_lock(&local_mtx);
   fake_system_function_that_takes_a_mutex(&local_mtx);
   pthread_mutex_lock(&local_mtx); // no-warning
   pthread_mutex_unlock(&local_mtx);
   pthread_mutex_destroy(&local_mtx);
 }
 
+void ok32(void) {
+  if (lck_rw_try_lock_exclusive(&rw) != 0) // no-warning
+    lck_rw_unlock_exclusive(&rw);          // no-warning
+}
+
+void ok33(void) {
+  if (lck_rw_try_lock_shared(&rw) != 0) // no-warning
+    lck_rw_lock_shared(&rw);            // no-warning
+}
+
 void
 bad1(void)
 {
   pthread_mutex_lock(&mtx1);  // no-warning
   pthread_mutex_lock(&mtx1);  // expected-warning{{This lock has already been acquired}}
 }
 
 void

 void bad31(void) {
   int ret = pthread_mutex_destroy(&mtx1); // no-warning
   pthread_mutex_lock(&mtx1);              // expected-warning{{This lock has already been destroyed}}
   if (ret != 0)
     pthread_mutex_lock(&mtx1);
 }
 
 void bad32(void) {
-  lck_rw_lock_shared(&rw);
-  lck_rw_unlock_exclusive(&rw); // FIXME: warn - should be shared?
-  lck_rw_lock_exclusive(&rw);
-  lck_rw_unlock_shared(&rw); // FIXME: warn - should be exclusive?
-}
-
-void bad33(void) {
   pthread_mutex_lock(pmtx);
   fake_system_function();
   pthread_mutex_lock(pmtx); // expected-warning{{This lock has already been acquired}}
 }
+
+void bad33(void) {
+  lck_rw_lock_exclusive(&rw);
+  lck_rw_unlock_shared(&rw); // expected-warning{{This lock has been acquired exclusively, but shared unlock used}}
+}
+
+void bad34(void) {
+  lck_rw_lock_shared(&rw);
+  lck_rw_unlock_exclusive(&rw); // expected-warning{{This lock has been acquired as shared, but exclusive unlock used}}
+}
+
+void bad35(void) {
+  if (lck_rw_try_lock_exclusive(&rw) != 0) // no-warning
+    lck_rw_unlock_shared(&rw);             // expected-warning{{This lock has been acquired exclusively, but shared unlock used}}
+}
+
+void bad36(void) {
+  if (lck_rw_try_lock_shared(&rw) != 0) // no-warning
+    lck_rw_unlock_exclusive(&rw);       // expected-warning{{This lock has been acquired as shared, but exclusive unlock used}}
+}