[analyzer] Implement a new checker ThreadPrimitivesChecker

[ASDenysPetrov]

Summary

This checker finds STL thread primitives misuse.

• std::mutex::unlock without std::mutex::lock
• std::recursive_mutex ::unlock without std::recursive_mutex ::lock
• std::mutex::lock twice

In future:

• std::mutex::lock without std::mutex::unlock (discuss)
• try_lock function

P.S. This is an alpha version of my first checker. Do not hesitate to express your complaints!

[vsavchenko]

It is an interesting checker, but it seems that this kind of checker is extremely hard in single TU/top-down analysis. It feels like it's going to produce hell a lot of false positives in the wild.
Also mutex is usually a global variable - the nemesis of any static analysis tool.

In general, it would be great to have checkers for multi-threaded programs. However, it seems like we would need some sort of conventions that we enforce. For example, every function containing a lock for a mutex should also have the unlock. And the checker would verify that the user follows the convention rather than has correct code. The convention, of course, should be designed so it implies correctness. This is the model we have with RetainCountChecker.

clang/lib/StaticAnalyzer/Checkers/ThreadPrimitivesChecker.cpp

37

These days we simply do BugType without unique_ptrs

47

You should also cleanup and remove dead symbols from the set.

47

Maybe SymbolRef is more suitable here?

50

Does it conform with clang-format?

53

I think this is better expressed with enum because this contract implies only 3 possible values. I prefer to bake such contracts into the types of the actual solution so that the code is more robust.

65

Looks overindented

75

If we are sure then why are we using dyn_cast instead of cast?

98

Looks under indented

clang/test/Analysis/Checkers/ThreadPrimitivesChecker.cpp

28

I think we should also add a TODO for having a warning for no m1.unlock()

83

😱😱😱

[ASDenysPetrov]

@vsavchenko
Made changes due to your remarks. Thanks you.

[ASDenysPetrov]

clang/lib/StaticAnalyzer/Checkers/ThreadPrimitivesChecker.cpp

47

Maybe SymbolRef is more suitable here?

I'm afraid it's not. Sval keeps some data but this data
See, getCXXThisVal returns SVal which is MemRegionVal, thus I can't cast it to SymbolVal and get SymbolRef.
But I would appreciate if you could tell me what other actionsI should do to get a correct SymbolRef.

[ASDenysPetrov]

Aded enum FuncIdKind to define function Ids.

[ASDenysPetrov]

Added recursive_mutex support.

Please, look at a test file on TODOs. I want to cover those cases in the future. Could you advise me something on it?

[NoQ]

Umm, why don't you extend PthreadLockChecker instead?

[ASDenysPetrov]

@NoQ

Umm, why don't you extend PthreadLockChecker instead?

First of all I wanted to try to go through all the steps, since it's my first checker. The second is that I considered PthreadLockChecker designed for C-functions. Another reason is that it better helps me to test the code when it is separated from all other.
When I feel more confident and it makes sence I'll try to merge this patch into PthreadLockChecker. For now it's more just an idea to discuss, to collect expertise.

Please, express you thoughts.
Specifically I've got a question: I have a set which holds SVal. @vsavchenko adviced me to clean the set on checkDeadSymbols. But SymbolReaper can only tell what is dead in terms of SymbolRef. What if I'm interested in any SVal (e.g. MemRegion, ConcreteInt)?

UDP: Ok, I found isLiveRegion for MemRegions. What about a common approach? Or it depends case by case?

[NoQ]

You're on the right track but your checker repeats PthreadLockChecker word-by-word. Like, you can find answers to all your questions (eg., "how to use isLiveRegion?") by reading that checker. C++ functions aren't any different from C functions; that's an extremely minor difference that doesn't justify developing a new checker from scratch.

clang/lib/StaticAnalyzer/Checkers/ThreadPrimitivesChecker.cpp

34

CallDescriptionMap is the modern API for this stuff.

[ASDenysPetrov]

@NoQ

You're on the right track but your checker repeats PthreadLockChecker word-by-word. Like, you can find answers to all your questions (eg., "how to use isLiveRegion?") by reading that checker. C++ functions aren't any different from C functions; that's an extremely minor difference that doesn't justify developing a new checker from scratch.

Thanks. I've already looked through PthreadLockChecker. Yes, it's pretty similar. I'll keep working separately for a while though as I feel more comfortable making mistakes.

clang/lib/StaticAnalyzer/Checkers/ThreadPrimitivesChecker.cpp

34

Thanks. I'll look.

[ASDenysPetrov]

Guys!
I've moved my work to PthreadLockChecker https://reviews.llvm.org/D85984. You are welcome to look at it.

clang/include/clang/StaticAnalyzer/Checkers/Checkers.td

def IteratorRangeChecker : Checker<"IteratorRange">,
   Dependencies<[IteratorModeling]>,
   Documentation<HasAlphaDocumentation>;
 
 def MismatchedIteratorChecker : Checker<"MismatchedIterator">,
   HelpText<"Check for use of iterators of different containers where iterators "
            "of the same container are expected">,
   Dependencies<[IteratorModeling]>,
   Documentation<HasAlphaDocumentation>;
   
+def ThreadPrimitivesChecker : Checker<"ThreadPrimitives">,
+  HelpText<"Check STD synchronization primitives">,
+  Documentation<HasAlphaDocumentation>;
+
 def SmartPtrChecker: Checker<"SmartPtr">,
   HelpText<"Find the dereference of null SmrtPtr">,
   Dependencies<[SmartPtrModeling]>,
   Documentation<HasAlphaDocumentation>;
 
 } // end: "alpha.cplusplus"
 
 

clang/include/clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h

ExplodedNode *generateSink(ProgramStateRef State, ExplodedNode *Pred,
     return addTransitionImpl(State ? State : getState(), true, Pred, Tag);
   }
 
   /// Add a sink node to the current path of execution, halting analysis.
   void addSink(ProgramStateRef State = nullptr,
                const ProgramPointTag *Tag = nullptr) {
     if (!State)
       State = getState();
-    addTransition(State, generateSink(State, getPredecessor()));
+    addTransition(State, generateSink(State, getPredecessor(), Tag));
   }
 
   /// Generate a transition to a node that will be used to report
   /// an error. This node will be a sink. That is, it will stop exploration of
   /// the given path.
   ///
   /// @param State The state of the generated node.
   /// @param Tag The tag to uniquely identify the creation site. If null,

clang/include/clang/StaticAnalyzer/Core/PathSensitive/SVals.h

public:
   bool operator==(const SVal &R) const {
     return getRawKind() == R.getRawKind() && Data == R.Data;
   }
 
   bool operator!=(const SVal &R) const {
     return !(*this == R);
   }
 
+  bool operator<(const SVal &R) const { return Data < R.Data; }
+
   bool isUnknown() const {
     return getRawKind() == UnknownValKind;
   }
 
   bool isUndef() const {
     return getRawKind() == UndefinedValKind;
   }
 

clang/lib/StaticAnalyzer/Checkers/CMakeLists.txt

add_clang_library(clangStaticAnalyzerCheckers
   SmartPtrModeling.cpp
   StackAddrEscapeChecker.cpp
   StdLibraryFunctionsChecker.cpp
   STLAlgorithmModeling.cpp
   StreamChecker.cpp
   Taint.cpp
   TaintTesterChecker.cpp
   TestAfterDivZeroChecker.cpp
+  ThreadPrimitivesChecker.cpp
   TraversalChecker.cpp
   TrustNonnullChecker.cpp
   UndefBranchChecker.cpp
   UndefCapturedBlockVarChecker.cpp
   UndefResultChecker.cpp
   UndefinedArraySubscriptChecker.cpp
   UndefinedAssignmentChecker.cpp
   UninitializedObject/UninitializedObjectChecker.cpp

clang/lib/StaticAnalyzer/Checkers/ThreadPrimitivesChecker.cpp

+//=== ConversionChecker.cpp -------------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This checker finds STL thread primitives misuse.
+// - std::mutex::unlock without std::mutex::lock
+// - std::mutex::lock twice
+//
+//===----------------------------------------------------------------------===//
+#include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h"
+#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
+#include "clang/StaticAnalyzer/Core/Checker.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
+#include <cstdint>
+
+using namespace clang;
+using namespace ento;
+
+namespace {
+
+enum FuncIdKind : uint8_t {
+  Undefined = 0,
+  Mutex_Lock,
+  Mutex_Unlock,
+  Recursive_Mutex_Lock,
+  Recursive_Mutex_Unlock,
+};
+
+static const std::pair<FuncIdKind, CallDescription> FuncMapping[]{
+    {Mutex_Lock, {{"std", "mutex", "lock"}, 0, 0}},
+    {Mutex_Unlock, {{"std", "mutex", "unlock"}, 0, 0}},
+    {Recursive_Mutex_Lock, {{"std", "recursive_mutex", "lock"}, 0, 0}},
+    {Recursive_Mutex_Unlock, {{"std", "recursive_mutex", "unlock"}, 0, 0}},
+};
+
+class ThreadPrimitivesChecker : public Checker<check::PostCall> {
+public:
+  void checkPostCall(const CallEvent &Call, CheckerContext &C) const;
+
+private:
+  BugType BT{this, "STL thread primitives misuse", "std::mutex misuse"};
+
+  FuncIdKind FindMutexLockOrUnlock(const CallEvent &Call,
+                                   CheckerContext &C) const;
+  void reportBug(CheckerContext &C, const char Msg[]) const;
+};
+
+} // namespace
+
+REGISTER_SET_WITH_PROGRAMSTATE(LockedMutexes, SVal)
+
+FuncIdKind
+ThreadPrimitivesChecker::FindMutexLockOrUnlock(const CallEvent &Call,
+                                               CheckerContext &C) const {
+  if (const auto *MCall = dyn_cast<CXXMemberCall>(&Call))
+    for (auto &P : FuncMapping)
+      if (MCall->isCalled(P.second))
+        return P.first;
+  return Undefined;
+}
+
+void ThreadPrimitivesChecker::checkPostCall(const CallEvent &Call,
+                                            CheckerContext &C) const {
+  // Find mutex::lock or mutex::unlock functions.
+  FuncIdKind FuncId = FindMutexLockOrUnlock(Call, C);
+
+  if (FuncId == Undefined)
+    return;
+
+  // We are sure about cast here, because mutex::lock/unlock met before.
+  const auto *MCall = cast<CXXMemberCall>(&Call);
+  SVal SymVal = MCall->getCXXThisVal();
+  const bool LockFound = C.getState()->contains<LockedMutexes>(SymVal);
+
+  switch (FuncId) {
+  case Mutex_Lock:
+  case Recursive_Mutex_Lock:
+    if (LockFound) {
+      if (FuncId == Mutex_Lock)
+        reportBug(C, "Call mutex::lock more than once.");
+    } else {
+      ProgramStateRef State = C.getState()->add<LockedMutexes>(SymVal);
+      C.addTransition(State);
+    }
+    break;
+  case Mutex_Unlock:
+  case Recursive_Mutex_Unlock:
+    if (LockFound) {
+      ProgramStateRef State = C.getState()->remove<LockedMutexes>(SymVal);
+      C.addTransition(State);
+    } else {
+      reportBug(C, "unlock without lock");
+    }
+    break;
+  default:
+    break;
+  }
+}
+
+void ThreadPrimitivesChecker::reportBug(CheckerContext &C,
+                                        const char Msg[]) const {
+  ExplodedNode *ErrNode = C.generateNonFatalErrorNode();
+  if (!ErrNode)
+    return;
+
+  // Generate a report for this bug.
+  C.emitReport(std::make_unique<PathSensitiveBugReport>(BT, Msg, ErrNode));
+}
+
+void ento::registerThreadPrimitivesChecker(CheckerManager &mgr) {
+  mgr.registerChecker<ThreadPrimitivesChecker>();
+}
+
+bool ento::shouldRegisterThreadPrimitivesChecker(const CheckerManager &mgr) {
+  return true;
+}

clang/test/Analysis/Checkers/ThreadPrimitivesChecker.cpp

+// RUN: %clang_analyze_cc1 -analyzer-checker=alpha.cplusplus.ThreadPrimitives -verify %s
+
+namespace std {
+struct mutex {
+  void lock();
+  void unlock();
+};
+struct recursive_mutex {
+  void lock();
+  void unlock();
+};
+template <typename T>
+struct guard_lock {
+  T &t;
+  guard_lock(T &m) : t(m) {
+    t.lock();
+  }
+  ~guard_lock() {
+    t.unlock();
+  }
+};
+} // namespace std
+
+void correct_lock_unlock(std::mutex m) {
+  m.lock();
+  std::mutex *m2 = &m;
+  m2->unlock();
+}
+
+void correct_lock_unlock2(std::mutex m) {
+  m.lock();
+  std::mutex &m2 = m;
+  m2.unlock();
+}
+
+void correct_lock_unlock3(std::mutex m) {
+  m.lock();
+  m.unlock();
+}
+
+void correct_lock_unlock4(std::mutex m) {
+  std::guard_lock<std::mutex> l(m);
+}
+
+void incorrect_lock_unlock(std::mutex m1, std::mutex m2, std::recursive_mutex rm1, std::recursive_mutex rm2) {
+  m1.lock();
+  m2.unlock(); // expected-warning{{unlock without lock}}
+  rm1.lock();
+  rm2.unlock(); // expected-warning{{unlock without lock}}
+}
+
+void lock_without_unlock(std::mutex m, bool b) {
+  m.lock();
+  if (b)
+    m.unlock(); // TODO: Detect case when unlock is in one branch only.
+}
+
+// TODO: Detect lock without unlock at the end of the block.
+void lock_without_unlock(std::mutex m, std::recursive_mutex rm2) {
+  m.lock();
+  rm2.lock();
+}
+
+void unlock_without_lock(std::mutex m, std::recursive_mutex rm) {
+  m.unlock();  // expected-warning{{unlock without lock}}
+  rm.unlock(); // expected-warning{{unlock without lock}}
+}
+
+void twice_lock(std::mutex m, std::recursive_mutex rm) {
+  m.lock();
+  m.lock(); // expected-warning{{lock more than once}}
+
+  rm.lock();
+  rm.lock(); // OK
+}
+
+void twice_lock2(std::mutex m, std::recursive_mutex rm) {
+  while (true) {
+    m.lock();  // expected-warning{{lock more than once}}
+    rm.lock(); // OK
+  }
+}