1 files changed, 310 insertions, 81 deletions

diff --git a/contrib/llvm-project/clang/lib/StaticAnalyzer/Checkers/BlockInCriticalSectionChecker.cpp b/contrib/llvm-project/clang/lib/StaticAnalyzer/Checkers/BlockInCriticalSectionChecker.cpp
index 66e080adb138..4cd2f2802f30 100644
--- a/contrib/llvm-project/clang/lib/StaticAnalyzer/Checkers/BlockInCriticalSectionChecker.cpp
+++ b/contrib/llvm-project/clang/lib/StaticAnalyzer/Checkers/BlockInCriticalSectionChecker.cpp
@@ -20,48 +20,186 @@
 #include "clang/StaticAnalyzer/Core/PathSensitive/CallDescription.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState_Fwd.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/SmallString.h"
+#include "llvm/ADT/StringExtras.h"
+
+#include <iterator>
+#include <utility>
+#include <variant>
 
 using namespace clang;
 using namespace ento;
 
 namespace {
+
+struct CritSectionMarker {
+  const Expr *LockExpr{};
+  const MemRegion *LockReg{};
+
+  void Profile(llvm::FoldingSetNodeID &ID) const {
+    ID.Add(LockExpr);
+    ID.Add(LockReg);
+  }
+
+  [[nodiscard]] constexpr bool
+  operator==(const CritSectionMarker &Other) const noexcept {
+    return LockExpr == Other.LockExpr && LockReg == Other.LockReg;
+  }
+  [[nodiscard]] constexpr bool
+  operator!=(const CritSectionMarker &Other) const noexcept {
+    return !(*this == Other);
+  }
+};
+
+class CallDescriptionBasedMatcher {
+  CallDescription LockFn;
+  CallDescription UnlockFn;
+
+public:
+  CallDescriptionBasedMatcher(CallDescription &&LockFn,
+                              CallDescription &&UnlockFn)
+      : LockFn(std::move(LockFn)), UnlockFn(std::move(UnlockFn)) {}
+  [[nodiscard]] bool matches(const CallEvent &Call, bool IsLock) const {
+    if (IsLock) {
+      return LockFn.matches(Call);
+    }
+    return UnlockFn.matches(Call);
+  }
+};
+
+class FirstArgMutexDescriptor : public CallDescriptionBasedMatcher {
+public:
+  FirstArgMutexDescriptor(CallDescription &&LockFn, CallDescription &&UnlockFn)
+      : CallDescriptionBasedMatcher(std::move(LockFn), std::move(UnlockFn)) {}
+
+  [[nodiscard]] const MemRegion *getRegion(const CallEvent &Call, bool) const {
+    return Call.getArgSVal(0).getAsRegion();
+  }
+};
+
+class MemberMutexDescriptor : public CallDescriptionBasedMatcher {
+public:
+  MemberMutexDescriptor(CallDescription &&LockFn, CallDescription &&UnlockFn)
+      : CallDescriptionBasedMatcher(std::move(LockFn), std::move(UnlockFn)) {}
+
+  [[nodiscard]] const MemRegion *getRegion(const CallEvent &Call, bool) const {
+    return cast<CXXMemberCall>(Call).getCXXThisVal().getAsRegion();
+  }
+};
+
+class RAIIMutexDescriptor {
+  mutable const IdentifierInfo *Guard{};
+  mutable bool IdentifierInfoInitialized{};
+  mutable llvm::SmallString<32> GuardName{};
+
+  void initIdentifierInfo(const CallEvent &Call) const {
+    if (!IdentifierInfoInitialized) {
+      // In case of checking C code, or when the corresponding headers are not
+      // included, we might end up query the identifier table every time when
+      // this function is called instead of early returning it. To avoid this, a
+      // bool variable (IdentifierInfoInitialized) is used and the function will
+      // be run only once.
+      const auto &ASTCtx = Call.getState()->getStateManager().getContext();
+      Guard = &ASTCtx.Idents.get(GuardName);
+    }
+  }
+
+  template <typename T> bool matchesImpl(const CallEvent &Call) const {
+    const T *C = dyn_cast<T>(&Call);
+    if (!C)
+      return false;
+    const IdentifierInfo *II =
+        cast<CXXRecordDecl>(C->getDecl()->getParent())->getIdentifier();
+    return II == Guard;
+  }
+
+public:
+  RAIIMutexDescriptor(StringRef GuardName) : GuardName(GuardName) {}
+  [[nodiscard]] bool matches(const CallEvent &Call, bool IsLock) const {
+    initIdentifierInfo(Call);
+    if (IsLock) {
+      return matchesImpl<CXXConstructorCall>(Call);
+    }
+    return matchesImpl<CXXDestructorCall>(Call);
+  }
+  [[nodiscard]] const MemRegion *getRegion(const CallEvent &Call,
+                                           bool IsLock) const {
+    const MemRegion *LockRegion = nullptr;
+    if (IsLock) {
+      if (std::optional<SVal> Object = Call.getReturnValueUnderConstruction()) {
+        LockRegion = Object->getAsRegion();
+      }
+    } else {
+      LockRegion = cast<CXXDestructorCall>(Call).getCXXThisVal().getAsRegion();
+    }
+    return LockRegion;
+  }
+};
+
+using MutexDescriptor =
+    std::variant<FirstArgMutexDescriptor, MemberMutexDescriptor,
+                 RAIIMutexDescriptor>;
+
 class BlockInCriticalSectionChecker : public Checker<check::PostCall> {
-  mutable IdentifierInfo *IILockGuard = nullptr;
-  mutable IdentifierInfo *IIUniqueLock = nullptr;
-  mutable bool IdentifierInfoInitialized = false;
-
-  const CallDescription LockFn{{"lock"}};
-  const CallDescription UnlockFn{{"unlock"}};
-  const CallDescription SleepFn{{"sleep"}};
-  const CallDescription GetcFn{{"getc"}};
-  const CallDescription FgetsFn{{"fgets"}};
-  const CallDescription ReadFn{{"read"}};
-  const CallDescription RecvFn{{"recv"}};
-  const CallDescription PthreadLockFn{{"pthread_mutex_lock"}};
-  const CallDescription PthreadTryLockFn{{"pthread_mutex_trylock"}};
-  const CallDescription PthreadUnlockFn{{"pthread_mutex_unlock"}};
-  const CallDescription MtxLock{{"mtx_lock"}};
-  const CallDescription MtxTimedLock{{"mtx_timedlock"}};
-  const CallDescription MtxTryLock{{"mtx_trylock"}};
-  const CallDescription MtxUnlock{{"mtx_unlock"}};
-
-  const llvm::StringLiteral ClassLockGuard{"lock_guard"};
-  const llvm::StringLiteral ClassUniqueLock{"unique_lock"};
+private:
+  const std::array<MutexDescriptor, 8> MutexDescriptors{
+      // NOTE: There are standard library implementations where some methods
+      // of `std::mutex` are inherited from an implementation detail base
+      // class, and those aren't matched by the name specification {"std",
+      // "mutex", "lock"}.
+      // As a workaround here we omit the class name and only require the
+      // presence of the name parts "std" and "lock"/"unlock".
+      // TODO: Ensure that CallDescription understands inherited methods.
+      MemberMutexDescriptor(
+          {/*MatchAs=*/CDM::CXXMethod,
+           /*QualifiedName=*/{"std", /*"mutex",*/ "lock"},
+           /*RequiredArgs=*/0},
+          {CDM::CXXMethod, {"std", /*"mutex",*/ "unlock"}, 0}),
+      FirstArgMutexDescriptor({CDM::CLibrary, {"pthread_mutex_lock"}, 1},
+                              {CDM::CLibrary, {"pthread_mutex_unlock"}, 1}),
+      FirstArgMutexDescriptor({CDM::CLibrary, {"mtx_lock"}, 1},
+                              {CDM::CLibrary, {"mtx_unlock"}, 1}),
+      FirstArgMutexDescriptor({CDM::CLibrary, {"pthread_mutex_trylock"}, 1},
+                              {CDM::CLibrary, {"pthread_mutex_unlock"}, 1}),
+      FirstArgMutexDescriptor({CDM::CLibrary, {"mtx_trylock"}, 1},
+                              {CDM::CLibrary, {"mtx_unlock"}, 1}),
+      FirstArgMutexDescriptor({CDM::CLibrary, {"mtx_timedlock"}, 1},
+                              {CDM::CLibrary, {"mtx_unlock"}, 1}),
+      RAIIMutexDescriptor("lock_guard"),
+      RAIIMutexDescriptor("unique_lock")};
+
+  const CallDescriptionSet BlockingFunctions{{CDM::CLibrary, {"sleep"}},
+                                             {CDM::CLibrary, {"getc"}},
+                                             {CDM::CLibrary, {"fgets"}},
+                                             {CDM::CLibrary, {"read"}},
+                                             {CDM::CLibrary, {"recv"}}};
 
   const BugType BlockInCritSectionBugType{
       this, "Call to blocking function in critical section", "Blocking Error"};
 
-  void initIdentifierInfo(ASTContext &Ctx) const;
+  void reportBlockInCritSection(const CallEvent &call, CheckerContext &C) const;
 
-  void reportBlockInCritSection(SymbolRef FileDescSym,
-                                const CallEvent &call,
-                                CheckerContext &C) const;
+  [[nodiscard]] const NoteTag *createCritSectionNote(CritSectionMarker M,
+                                                     CheckerContext &C) const;
 
-public:
-  bool isBlockingFunction(const CallEvent &Call) const;
-  bool isLockFunction(const CallEvent &Call) const;
-  bool isUnlockFunction(const CallEvent &Call) const;
+  [[nodiscard]] std::optional<MutexDescriptor>
+  checkDescriptorMatch(const CallEvent &Call, CheckerContext &C,
+                       bool IsLock) const;
+
+  void handleLock(const MutexDescriptor &Mutex, const CallEvent &Call,
+                  CheckerContext &C) const;
 
+  void handleUnlock(const MutexDescriptor &Mutex, const CallEvent &Call,
+                    CheckerContext &C) const;
+
+  [[nodiscard]] bool isBlockingInCritSection(const CallEvent &Call,
+                                             CheckerContext &C) const;
+
+public:
   /// Process unlock.
   /// Process lock.
   /// Process blocking functions (sleep, getc, fgets, read, recv)
@@ -70,73 +208,115 @@ public:
 
 } // end anonymous namespace
 
-REGISTER_TRAIT_WITH_PROGRAMSTATE(MutexCounter, unsigned)
-
-void BlockInCriticalSectionChecker::initIdentifierInfo(ASTContext &Ctx) const {
-  if (!IdentifierInfoInitialized) {
-    /* In case of checking C code, or when the corresponding headers are not
-     * included, we might end up query the identifier table every time when this
-     * function is called instead of early returning it. To avoid this, a bool
-     * variable (IdentifierInfoInitialized) is used and the function will be run
-     * only once. */
-    IILockGuard  = &Ctx.Idents.get(ClassLockGuard);
-    IIUniqueLock = &Ctx.Idents.get(ClassUniqueLock);
-    IdentifierInfoInitialized = true;
-  }
+REGISTER_LIST_WITH_PROGRAMSTATE(ActiveCritSections, CritSectionMarker)
+
+// Iterator traits for ImmutableList data structure
+// that enable the use of STL algorithms.
+// TODO: Move these to llvm::ImmutableList when overhauling immutable data
+// structures for proper iterator concept support.
+template <>
+struct std::iterator_traits<
+    typename llvm::ImmutableList<CritSectionMarker>::iterator> {
+  using iterator_category = std::forward_iterator_tag;
+  using value_type = CritSectionMarker;
+  using difference_type = std::ptrdiff_t;
+  using reference = CritSectionMarker &;
+  using pointer = CritSectionMarker *;
+};
+
+std::optional<MutexDescriptor>
+BlockInCriticalSectionChecker::checkDescriptorMatch(const CallEvent &Call,
+                                                    CheckerContext &C,
+                                                    bool IsLock) const {
+  const auto Descriptor =
+      llvm::find_if(MutexDescriptors, [&Call, IsLock](auto &&Descriptor) {
+        return std::visit(
+            [&Call, IsLock](auto &&DescriptorImpl) {
+              return DescriptorImpl.matches(Call, IsLock);
+            },
+            Descriptor);
+      });
+  if (Descriptor != MutexDescriptors.end())
+    return *Descriptor;
+  return std::nullopt;
 }
 
-bool BlockInCriticalSectionChecker::isBlockingFunction(const CallEvent &Call) const {
-  return matchesAny(Call, SleepFn, GetcFn, FgetsFn, ReadFn, RecvFn);
+static const MemRegion *getRegion(const CallEvent &Call,
+                                  const MutexDescriptor &Descriptor,
+                                  bool IsLock) {
+  return std::visit(
+      [&Call, IsLock](auto &&Descriptor) {
+        return Descriptor.getRegion(Call, IsLock);
+      },
+      Descriptor);
 }
 
-bool BlockInCriticalSectionChecker::isLockFunction(const CallEvent &Call) const {
-  if (const auto *Ctor = dyn_cast<CXXConstructorCall>(&Call)) {
-    auto IdentifierInfo = Ctor->getDecl()->getParent()->getIdentifier();
-    if (IdentifierInfo == IILockGuard || IdentifierInfo == IIUniqueLock)
-      return true;
-  }
+void BlockInCriticalSectionChecker::handleLock(
+    const MutexDescriptor &LockDescriptor, const CallEvent &Call,
+    CheckerContext &C) const {
+  const MemRegion *MutexRegion =
+      getRegion(Call, LockDescriptor, /*IsLock=*/true);
+  if (!MutexRegion)
+    return;
 
-  return matchesAny(Call, LockFn, PthreadLockFn, PthreadTryLockFn, MtxLock,
-                    MtxTimedLock, MtxTryLock);
+  const CritSectionMarker MarkToAdd{Call.getOriginExpr(), MutexRegion};
+  ProgramStateRef StateWithLockEvent =
+      C.getState()->add<ActiveCritSections>(MarkToAdd);
+  C.addTransition(StateWithLockEvent, createCritSectionNote(MarkToAdd, C));
 }
 
-bool BlockInCriticalSectionChecker::isUnlockFunction(const CallEvent &Call) const {
-  if (const auto *Dtor = dyn_cast<CXXDestructorCall>(&Call)) {
-    const auto *DRecordDecl = cast<CXXRecordDecl>(Dtor->getDecl()->getParent());
-    auto IdentifierInfo = DRecordDecl->getIdentifier();
-    if (IdentifierInfo == IILockGuard || IdentifierInfo == IIUniqueLock)
-      return true;
+void BlockInCriticalSectionChecker::handleUnlock(
+    const MutexDescriptor &UnlockDescriptor, const CallEvent &Call,
+    CheckerContext &C) const {
+  const MemRegion *MutexRegion =
+      getRegion(Call, UnlockDescriptor, /*IsLock=*/false);
+  if (!MutexRegion)
+    return;
+
+  ProgramStateRef State = C.getState();
+  const auto ActiveSections = State->get<ActiveCritSections>();
+  const auto MostRecentLock =
+      llvm::find_if(ActiveSections, [MutexRegion](auto &&Marker) {
+        return Marker.LockReg == MutexRegion;
+      });
+  if (MostRecentLock == ActiveSections.end())
+    return;
+
+  // Build a new ImmutableList without this element.
+  auto &Factory = State->get_context<ActiveCritSections>();
+  llvm::ImmutableList<CritSectionMarker> NewList = Factory.getEmptyList();
+  for (auto It = ActiveSections.begin(), End = ActiveSections.end(); It != End;
+       ++It) {
+    if (It != MostRecentLock)
+      NewList = Factory.add(*It, NewList);
   }
 
-  return matchesAny(Call, UnlockFn, PthreadUnlockFn, MtxUnlock);
+  State = State->set<ActiveCritSections>(NewList);
+  C.addTransition(State);
+}
+
+bool BlockInCriticalSectionChecker::isBlockingInCritSection(
+    const CallEvent &Call, CheckerContext &C) const {
+  return BlockingFunctions.contains(Call) &&
+         !C.getState()->get<ActiveCritSections>().isEmpty();
 }
 
 void BlockInCriticalSectionChecker::checkPostCall(const CallEvent &Call,
                                                   CheckerContext &C) const {
-  initIdentifierInfo(C.getASTContext());
-
-  if (!isBlockingFunction(Call)
-      && !isLockFunction(Call)
-      && !isUnlockFunction(Call))
-    return;
-
-  ProgramStateRef State = C.getState();
-  unsigned mutexCount = State->get<MutexCounter>();
-  if (isUnlockFunction(Call) && mutexCount > 0) {
-    State = State->set<MutexCounter>(--mutexCount);
-    C.addTransition(State);
-  } else if (isLockFunction(Call)) {
-    State = State->set<MutexCounter>(++mutexCount);
-    C.addTransition(State);
-  } else if (mutexCount > 0) {
-    SymbolRef BlockDesc = Call.getReturnValue().getAsSymbol();
-    reportBlockInCritSection(BlockDesc, Call, C);
+  if (isBlockingInCritSection(Call, C)) {
+    reportBlockInCritSection(Call, C);
+  } else if (std::optional<MutexDescriptor> LockDesc =
+                 checkDescriptorMatch(Call, C, /*IsLock=*/true)) {
+    handleLock(*LockDesc, Call, C);
+  } else if (std::optional<MutexDescriptor> UnlockDesc =
+                 checkDescriptorMatch(Call, C, /*IsLock=*/false)) {
+    handleUnlock(*UnlockDesc, Call, C);
   }
 }
 
 void BlockInCriticalSectionChecker::reportBlockInCritSection(
-    SymbolRef BlockDescSym, const CallEvent &Call, CheckerContext &C) const {
-  ExplodedNode *ErrNode = C.generateNonFatalErrorNode();
+    const CallEvent &Call, CheckerContext &C) const {
+  ExplodedNode *ErrNode = C.generateNonFatalErrorNode(C.getState());
   if (!ErrNode)
     return;
 
@@ -147,14 +327,63 @@ void BlockInCriticalSectionChecker::reportBlockInCritSection(
   auto R = std::make_unique<PathSensitiveBugReport>(BlockInCritSectionBugType,
                                                     os.str(), ErrNode);
   R->addRange(Call.getSourceRange());
-  R->markInteresting(BlockDescSym);
+  R->markInteresting(Call.getReturnValue());
   C.emitReport(std::move(R));
 }
 
+const NoteTag *
+BlockInCriticalSectionChecker::createCritSectionNote(CritSectionMarker M,
+                                                     CheckerContext &C) const {
+  const BugType *BT = &this->BlockInCritSectionBugType;
+  return C.getNoteTag([M, BT](PathSensitiveBugReport &BR,
+                              llvm::raw_ostream &OS) {
+    if (&BR.getBugType() != BT)
+      return;
+
+    // Get the lock events for the mutex of the current line's lock event.
+    const auto CritSectionBegins =
+        BR.getErrorNode()->getState()->get<ActiveCritSections>();
+    llvm::SmallVector<CritSectionMarker, 4> LocksForMutex;
+    llvm::copy_if(
+        CritSectionBegins, std::back_inserter(LocksForMutex),
+        [M](const auto &Marker) { return Marker.LockReg == M.LockReg; });
+    if (LocksForMutex.empty())
+      return;
+
+    // As the ImmutableList builds the locks by prepending them, we
+    // reverse the list to get the correct order.
+    std::reverse(LocksForMutex.begin(), LocksForMutex.end());
+
+    // Find the index of the lock expression in the list of all locks for a
+    // given mutex (in acquisition order).
+    const auto Position =
+        llvm::find_if(std::as_const(LocksForMutex), [M](const auto &Marker) {
+          return Marker.LockExpr == M.LockExpr;
+        });
+    if (Position == LocksForMutex.end())
+      return;
+
+    // If there is only one lock event, we don't need to specify how many times
+    // the critical section was entered.
+    if (LocksForMutex.size() == 1) {
+      OS << "Entering critical section here";
+      return;
+    }
+
+    const auto IndexOfLock =
+        std::distance(std::as_const(LocksForMutex).begin(), Position);
+
+    const auto OrdinalOfLock = IndexOfLock + 1;
+    OS << "Entering critical section for the " << OrdinalOfLock
+       << llvm::getOrdinalSuffix(OrdinalOfLock) << " time here";
+  });
+}
+
 void ento::registerBlockInCriticalSectionChecker(CheckerManager &mgr) {
   mgr.registerChecker<BlockInCriticalSectionChecker>();
 }
 
-bool ento::shouldRegisterBlockInCriticalSectionChecker(const CheckerManager &mgr) {
+bool ento::shouldRegisterBlockInCriticalSectionChecker(
+    const CheckerManager &mgr) {
   return true;
 }