clang/lib/StaticAnalyzer/Checkers/BlockInCriticalSectionChecker.cpp

   1 //===-- BlockInCriticalSectionChecker.cpp -----------------------*- C++ -*-===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // Defines a checker for blocks in critical sections. This checker should find
  10 // the calls to blocking functions (for example: sleep, getc, fgets, read,
  11 // recv etc.) inside a critical section. When sleep(x) is called while a mutex
  12 // is held, other threades cannot lock the same mutex. This might take some
  13 // time, leading to bad performance or even deadlock.
  14 //
  15 //===----------------------------------------------------------------------===//
  16
  17 #include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h"
  18 #include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
  19 #include "clang/StaticAnalyzer/Core/Checker.h"
  20 #include "clang/StaticAnalyzer/Core/PathSensitive/CallDescription.h"
  21 #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
  22 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
  23 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerHelpers.h"
  24 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h"
  25 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState_Fwd.h"
  26 #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h"
  27 #include "llvm/ADT/STLExtras.h"
  28 #include "llvm/ADT/SmallString.h"
  29 #include "llvm/ADT/StringExtras.h"
  30
  31 #include <iterator>
  32 #include <utility>
  33 #include <variant>
  34
  35 using namespace clang;
  36 using namespace ento;
  37
  38 namespace {
  39
  40 struct CritSectionMarker {
  41   const Expr *LockExpr{};
  42   const MemRegion *LockReg{};
  43
  44   void Profile(llvm::FoldingSetNodeID &ID) const {
  45     ID.Add(LockExpr);
  46     ID.Add(LockReg);
  47   }
  48
  49   [[nodiscard]] constexpr bool
  50   operator==(const CritSectionMarker &Other) const noexcept {
  51     return LockExpr == Other.LockExpr && LockReg == Other.LockReg;
  52   }
  53   [[nodiscard]] constexpr bool
  54   operator!=(const CritSectionMarker &Other) const noexcept {
  55     return !(*this == Other);
  56   }
  57 };
  58
  59 class CallDescriptionBasedMatcher {
  60   CallDescription LockFn;
  61   CallDescription UnlockFn;
  62
  63 public:
  64   CallDescriptionBasedMatcher(CallDescription &&LockFn,
  65                               CallDescription &&UnlockFn)
  66       : LockFn(std::move(LockFn)), UnlockFn(std::move(UnlockFn)) {}
  67   [[nodiscard]] bool matches(const CallEvent &Call, bool IsLock) const {
  68     if (IsLock) {
  69       return LockFn.matches(Call);
  70     }
  71     return UnlockFn.matches(Call);
  72   }
  73 };
  74
  75 class FirstArgMutexDescriptor : public CallDescriptionBasedMatcher {
  76 public:
  77   FirstArgMutexDescriptor(CallDescription &&LockFn, CallDescription &&UnlockFn)
  78       : CallDescriptionBasedMatcher(std::move(LockFn), std::move(UnlockFn)) {}
  79
  80   [[nodiscard]] const MemRegion *getRegion(const CallEvent &Call, bool) const {
  81     return Call.getArgSVal(0).getAsRegion();
  82   }
  83 };
  84
  85 class MemberMutexDescriptor : public CallDescriptionBasedMatcher {
  86 public:
  87   MemberMutexDescriptor(CallDescription &&LockFn, CallDescription &&UnlockFn)
  88       : CallDescriptionBasedMatcher(std::move(LockFn), std::move(UnlockFn)) {}
  89
  90   [[nodiscard]] const MemRegion *getRegion(const CallEvent &Call, bool) const {
  91     return cast<CXXMemberCall>(Call).getCXXThisVal().getAsRegion();
  92   }
  93 };
  94
  95 class RAIIMutexDescriptor {
  96   mutable const IdentifierInfo *Guard{};
  97   mutable bool IdentifierInfoInitialized{};
  98   mutable llvm::SmallString<32> GuardName{};
  99
 100   void initIdentifierInfo(const CallEvent &Call) const {
 101     if (!IdentifierInfoInitialized) {
 102       // In case of checking C code, or when the corresponding headers are not
 103       // included, we might end up query the identifier table every time when
 104       // this function is called instead of early returning it. To avoid this, a
 105       // bool variable (IdentifierInfoInitialized) is used and the function will
 106       // be run only once.
 107       const auto &ASTCtx = Call.getState()->getStateManager().getContext();
 108       Guard = &ASTCtx.Idents.get(GuardName);
 109     }
 110   }
 111
 112   template <typename T> bool matchesImpl(const CallEvent &Call) const {
 113     const T *C = dyn_cast<T>(&Call);
 114     if (!C)
 115       return false;
 116     const IdentifierInfo *II =
 117         cast<CXXRecordDecl>(C->getDecl()->getParent())->getIdentifier();
 118     return II == Guard;
 119   }
 120
 121 public:
 122   RAIIMutexDescriptor(StringRef GuardName) : GuardName(GuardName) {}
 123   [[nodiscard]] bool matches(const CallEvent &Call, bool IsLock) const {
 124     initIdentifierInfo(Call);
 125     if (IsLock) {
 126       return matchesImpl<CXXConstructorCall>(Call);
 127     }
 128     return matchesImpl<CXXDestructorCall>(Call);
 129   }
 130   [[nodiscard]] const MemRegion *getRegion(const CallEvent &Call,
 131                                            bool IsLock) const {
 132     const MemRegion *LockRegion = nullptr;
 133     if (IsLock) {
 134       if (std::optional<SVal> Object = Call.getReturnValueUnderConstruction()) {
 135         LockRegion = Object->getAsRegion();
 136       }
 137     } else {
 138       LockRegion = cast<CXXDestructorCall>(Call).getCXXThisVal().getAsRegion();
 139     }
 140     return LockRegion;
 141   }
 142 };
 143
 144 using MutexDescriptor =
 145     std::variant<FirstArgMutexDescriptor, MemberMutexDescriptor,
 146                  RAIIMutexDescriptor>;
 147
 148 class BlockInCriticalSectionChecker : public Checker<check::PostCall> {
 149 private:
 150   const std::array<MutexDescriptor, 8> MutexDescriptors{
 151       // NOTE: There are standard library implementations where some methods
 152       // of `std::mutex` are inherited from an implementation detail base
 153       // class, and those aren't matched by the name specification {"std",
 154       // "mutex", "lock"}.
 155       // As a workaround here we omit the class name and only require the
 156       // presence of the name parts "std" and "lock"/"unlock".
 157       // TODO: Ensure that CallDescription understands inherited methods.
 158       MemberMutexDescriptor(
 159           {/*MatchAs=*/CDM::CXXMethod,
 160            /*QualifiedName=*/{"std", /*"mutex",*/ "lock"},
 161            /*RequiredArgs=*/0},
 162           {CDM::CXXMethod, {"std", /*"mutex",*/ "unlock"}, 0}),
 163       FirstArgMutexDescriptor({CDM::CLibrary, {"pthread_mutex_lock"}, 1},
 164                               {CDM::CLibrary, {"pthread_mutex_unlock"}, 1}),
 165       FirstArgMutexDescriptor({CDM::CLibrary, {"mtx_lock"}, 1},
 166                               {CDM::CLibrary, {"mtx_unlock"}, 1}),
 167       FirstArgMutexDescriptor({CDM::CLibrary, {"pthread_mutex_trylock"}, 1},
 168                               {CDM::CLibrary, {"pthread_mutex_unlock"}, 1}),
 169       FirstArgMutexDescriptor({CDM::CLibrary, {"mtx_trylock"}, 1},
 170                               {CDM::CLibrary, {"mtx_unlock"}, 1}),
 171       FirstArgMutexDescriptor({CDM::CLibrary, {"mtx_timedlock"}, 1},
 172                               {CDM::CLibrary, {"mtx_unlock"}, 1}),
 173       RAIIMutexDescriptor("lock_guard"),
 174       RAIIMutexDescriptor("unique_lock")};
 175
 176   const CallDescriptionSet BlockingFunctions{{CDM::CLibrary, {"sleep"}},
 177                                              {CDM::CLibrary, {"getc"}},
 178                                              {CDM::CLibrary, {"fgets"}},
 179                                              {CDM::CLibrary, {"read"}},
 180                                              {CDM::CLibrary, {"recv"}}};
 181
 182   const BugType BlockInCritSectionBugType{
 183       this, "Call to blocking function in critical section", "Blocking Error"};
 184
 185   void reportBlockInCritSection(const CallEvent &call, CheckerContext &C) const;
 186
 187   [[nodiscard]] const NoteTag *createCritSectionNote(CritSectionMarker M,
 188                                                      CheckerContext &C) const;
 189
 190   [[nodiscard]] std::optional<MutexDescriptor>
 191   checkDescriptorMatch(const CallEvent &Call, CheckerContext &C,
 192                        bool IsLock) const;
 193
 194   void handleLock(const MutexDescriptor &Mutex, const CallEvent &Call,
 195                   CheckerContext &C) const;
 196
 197   void handleUnlock(const MutexDescriptor &Mutex, const CallEvent &Call,
 198                     CheckerContext &C) const;
 199
 200   [[nodiscard]] bool isBlockingInCritSection(const CallEvent &Call,
 201                                              CheckerContext &C) const;
 202
 203 public:
 204   /// Process unlock.
 205   /// Process lock.
 206   /// Process blocking functions (sleep, getc, fgets, read, recv)
 207   void checkPostCall(const CallEvent &Call, CheckerContext &C) const;
 208 };
 209
 210 } // end anonymous namespace
 211
 212 REGISTER_LIST_WITH_PROGRAMSTATE(ActiveCritSections, CritSectionMarker)
 213
 214 // Iterator traits for ImmutableList data structure
 215 // that enable the use of STL algorithms.
 216 // TODO: Move these to llvm::ImmutableList when overhauling immutable data
 217 // structures for proper iterator concept support.
 218 template <>
 219 struct std::iterator_traits<
 220     typename llvm::ImmutableList<CritSectionMarker>::iterator> {
 221   using iterator_category = std::forward_iterator_tag;
 222   using value_type = CritSectionMarker;
 223   using difference_type = std::ptrdiff_t;
 224   using reference = CritSectionMarker &;
 225   using pointer = CritSectionMarker *;
 226 };
 227
 228 std::optional<MutexDescriptor>
 229 BlockInCriticalSectionChecker::checkDescriptorMatch(const CallEvent &Call,
 230                                                     CheckerContext &C,
 231                                                     bool IsLock) const {
 232   const auto Descriptor =
 233       llvm::find_if(MutexDescriptors, [&Call, IsLock](auto &&Descriptor) {
 234         return std::visit(
 235             [&Call, IsLock](auto &&DescriptorImpl) {
 236               return DescriptorImpl.matches(Call, IsLock);
 237             },
 238             Descriptor);
 239       });
 240   if (Descriptor != MutexDescriptors.end())
 241     return *Descriptor;
 242   return std::nullopt;
 243 }
 244
 245 static const MemRegion *skipStdBaseClassRegion(const MemRegion *Reg) {
 246   while (Reg) {
 247     const auto *BaseClassRegion = dyn_cast<CXXBaseObjectRegion>(Reg);
 248     if (!BaseClassRegion || !isWithinStdNamespace(BaseClassRegion->getDecl()))
 249       break;
 250     Reg = BaseClassRegion->getSuperRegion();
 251   }
 252   return Reg;
 253 }
 254
 255 static const MemRegion *getRegion(const CallEvent &Call,
 256                                   const MutexDescriptor &Descriptor,
 257                                   bool IsLock) {
 258   return std::visit(
 259       [&Call, IsLock](auto &Descr) -> const MemRegion * {
 260         return skipStdBaseClassRegion(Descr.getRegion(Call, IsLock));
 261       },
 262       Descriptor);
 263 }
 264
 265 void BlockInCriticalSectionChecker::handleLock(
 266     const MutexDescriptor &LockDescriptor, const CallEvent &Call,
 267     CheckerContext &C) const {
 268   const MemRegion *MutexRegion =
 269       getRegion(Call, LockDescriptor, /*IsLock=*/true);
 270   if (!MutexRegion)
 271     return;
 272
 273   const CritSectionMarker MarkToAdd{Call.getOriginExpr(), MutexRegion};
 274   ProgramStateRef StateWithLockEvent =
 275       C.getState()->add<ActiveCritSections>(MarkToAdd);
 276   C.addTransition(StateWithLockEvent, createCritSectionNote(MarkToAdd, C));
 277 }
 278
 279 void BlockInCriticalSectionChecker::handleUnlock(
 280     const MutexDescriptor &UnlockDescriptor, const CallEvent &Call,
 281     CheckerContext &C) const {
 282   const MemRegion *MutexRegion =
 283       getRegion(Call, UnlockDescriptor, /*IsLock=*/false);
 284   if (!MutexRegion)
 285     return;
 286
 287   ProgramStateRef State = C.getState();
 288   const auto ActiveSections = State->get<ActiveCritSections>();
 289   const auto MostRecentLock =
 290       llvm::find_if(ActiveSections, [MutexRegion](auto &&Marker) {
 291         return Marker.LockReg == MutexRegion;
 292       });
 293   if (MostRecentLock == ActiveSections.end())
 294     return;
 295
 296   // Build a new ImmutableList without this element.
 297   auto &Factory = State->get_context<ActiveCritSections>();
 298   llvm::ImmutableList<CritSectionMarker> NewList = Factory.getEmptyList();
 299   for (auto It = ActiveSections.begin(), End = ActiveSections.end(); It != End;
 300        ++It) {
 301     if (It != MostRecentLock)
 302       NewList = Factory.add(*It, NewList);
 303   }
 304
 305   State = State->set<ActiveCritSections>(NewList);
 306   C.addTransition(State);
 307 }
 308
 309 bool BlockInCriticalSectionChecker::isBlockingInCritSection(
 310     const CallEvent &Call, CheckerContext &C) const {
 311   return BlockingFunctions.contains(Call) &&
 312          !C.getState()->get<ActiveCritSections>().isEmpty();
 313 }
 314
 315 void BlockInCriticalSectionChecker::checkPostCall(const CallEvent &Call,
 316                                                   CheckerContext &C) const {
 317   if (isBlockingInCritSection(Call, C)) {
 318     reportBlockInCritSection(Call, C);
 319   } else if (std::optional<MutexDescriptor> LockDesc =
 320                  checkDescriptorMatch(Call, C, /*IsLock=*/true)) {
 321     handleLock(*LockDesc, Call, C);
 322   } else if (std::optional<MutexDescriptor> UnlockDesc =
 323                  checkDescriptorMatch(Call, C, /*IsLock=*/false)) {
 324     handleUnlock(*UnlockDesc, Call, C);
 325   }
 326 }
 327
 328 void BlockInCriticalSectionChecker::reportBlockInCritSection(
 329     const CallEvent &Call, CheckerContext &C) const {
 330   ExplodedNode *ErrNode = C.generateNonFatalErrorNode(C.getState());
 331   if (!ErrNode)
 332     return;
 333
 334   std::string msg;
 335   llvm::raw_string_ostream os(msg);
 336   os << "Call to blocking function '" << Call.getCalleeIdentifier()->getName()
 337      << "' inside of critical section";
 338   auto R = std::make_unique<PathSensitiveBugReport>(BlockInCritSectionBugType,
 339                                                     os.str(), ErrNode);
 340   R->addRange(Call.getSourceRange());
 341   R->markInteresting(Call.getReturnValue());
 342   C.emitReport(std::move(R));
 343 }
 344
 345 const NoteTag *
 346 BlockInCriticalSectionChecker::createCritSectionNote(CritSectionMarker M,
 347                                                      CheckerContext &C) const {
 348   const BugType *BT = &this->BlockInCritSectionBugType;
 349   return C.getNoteTag([M, BT](PathSensitiveBugReport &BR,
 350                               llvm::raw_ostream &OS) {
 351     if (&BR.getBugType() != BT)
 352       return;
 353
 354     // Get the lock events for the mutex of the current line's lock event.
 355     const auto CritSectionBegins =
 356         BR.getErrorNode()->getState()->get<ActiveCritSections>();
 357     llvm::SmallVector<CritSectionMarker, 4> LocksForMutex;
 358     llvm::copy_if(
 359         CritSectionBegins, std::back_inserter(LocksForMutex),
 360         [M](const auto &Marker) { return Marker.LockReg == M.LockReg; });
 361     if (LocksForMutex.empty())
 362       return;
 363
 364     // As the ImmutableList builds the locks by prepending them, we
 365     // reverse the list to get the correct order.
 366     std::reverse(LocksForMutex.begin(), LocksForMutex.end());
 367
 368     // Find the index of the lock expression in the list of all locks for a
 369     // given mutex (in acquisition order).
 370     const auto Position =
 371         llvm::find_if(std::as_const(LocksForMutex), [M](const auto &Marker) {
 372           return Marker.LockExpr == M.LockExpr;
 373         });
 374     if (Position == LocksForMutex.end())
 375       return;
 376
 377     // If there is only one lock event, we don't need to specify how many times
 378     // the critical section was entered.
 379     if (LocksForMutex.size() == 1) {
 380       OS << "Entering critical section here";
 381       return;
 382     }
 383
 384     const auto IndexOfLock =
 385         std::distance(std::as_const(LocksForMutex).begin(), Position);
 386
 387     const auto OrdinalOfLock = IndexOfLock + 1;
 388     OS << "Entering critical section for the " << OrdinalOfLock
 389        << llvm::getOrdinalSuffix(OrdinalOfLock) << " time here";
 390   });
 391 }
 392
 393 void ento::registerBlockInCriticalSectionChecker(CheckerManager &mgr) {
 394   mgr.registerChecker<BlockInCriticalSectionChecker>();
 395 }
 396
 397 bool ento::shouldRegisterBlockInCriticalSectionChecker(
 398     const CheckerManager &mgr) {
 399   return true;
 400 }