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 SuppressNonBlockingStreams : public BugReporterVisitor { 149 private: 150 const CallDescription OpenFunction{CDM::CLibrary, {"open"}, 2}; 151 SymbolRef StreamSym; 152 const int NonBlockMacroVal; 153 bool Satisfied = false; 154 155 public: 156 SuppressNonBlockingStreams(SymbolRef StreamSym, int NonBlockMacroVal) 157 : StreamSym(StreamSym), NonBlockMacroVal(NonBlockMacroVal) {} 158 159 static void *getTag() { 160 static bool Tag; 161 return &Tag; 162 } 163 164 void Profile(llvm::FoldingSetNodeID &ID) const override { 165 ID.AddPointer(getTag()); 166 } 167 168 PathDiagnosticPieceRef VisitNode(const ExplodedNode *N, 169 BugReporterContext &BRC, 170 PathSensitiveBugReport &BR) override { 171 if (Satisfied) 172 return nullptr; 173 174 std::optional<StmtPoint> Point = N->getLocationAs<StmtPoint>(); 175 if (!Point) 176 return nullptr; 177 178 const auto *CE = Point->getStmtAs<CallExpr>(); 179 if (!CE || !OpenFunction.matchesAsWritten(*CE)) 180 return nullptr; 181 182 if (N->getSVal(CE).getAsSymbol() != StreamSym) 183 return nullptr; 184 185 Satisfied = true; 186 187 // Check if open's second argument contains O_NONBLOCK 188 const llvm::APSInt *FlagVal = N->getSVal(CE->getArg(1)).getAsInteger(); 189 if (!FlagVal) 190 return nullptr; 191 192 if ((*FlagVal & NonBlockMacroVal) != 0) 193 BR.markInvalid(getTag(), nullptr); 194 195 return nullptr; 196 } 197 }; 198 199 class BlockInCriticalSectionChecker : public Checker<check::PostCall> { 200 private: 201 const std::array<MutexDescriptor, 8> MutexDescriptors{ 202 // NOTE: There are standard library implementations where some methods 203 // of `std::mutex` are inherited from an implementation detail base 204 // class, and those aren't matched by the name specification {"std", 205 // "mutex", "lock"}. 206 // As a workaround here we omit the class name and only require the 207 // presence of the name parts "std" and "lock"/"unlock". 208 // TODO: Ensure that CallDescription understands inherited methods. 209 MemberMutexDescriptor( 210 {/*MatchAs=*/CDM::CXXMethod, 211 /*QualifiedName=*/{"std", /*"mutex",*/ "lock"}, 212 /*RequiredArgs=*/0}, 213 {CDM::CXXMethod, {"std", /*"mutex",*/ "unlock"}, 0}), 214 FirstArgMutexDescriptor({CDM::CLibrary, {"pthread_mutex_lock"}, 1}, 215 {CDM::CLibrary, {"pthread_mutex_unlock"}, 1}), 216 FirstArgMutexDescriptor({CDM::CLibrary, {"mtx_lock"}, 1}, 217 {CDM::CLibrary, {"mtx_unlock"}, 1}), 218 FirstArgMutexDescriptor({CDM::CLibrary, {"pthread_mutex_trylock"}, 1}, 219 {CDM::CLibrary, {"pthread_mutex_unlock"}, 1}), 220 FirstArgMutexDescriptor({CDM::CLibrary, {"mtx_trylock"}, 1}, 221 {CDM::CLibrary, {"mtx_unlock"}, 1}), 222 FirstArgMutexDescriptor({CDM::CLibrary, {"mtx_timedlock"}, 1}, 223 {CDM::CLibrary, {"mtx_unlock"}, 1}), 224 RAIIMutexDescriptor("lock_guard"), 225 RAIIMutexDescriptor("unique_lock")}; 226 227 const CallDescriptionSet BlockingFunctions{{CDM::CLibrary, {"sleep"}}, 228 {CDM::CLibrary, {"getc"}}, 229 {CDM::CLibrary, {"fgets"}}, 230 {CDM::CLibrary, {"read"}}, 231 {CDM::CLibrary, {"recv"}}}; 232 233 const BugType BlockInCritSectionBugType{ 234 this, "Call to blocking function in critical section", "Blocking Error"}; 235 236 using O_NONBLOCKValueTy = std::optional<int>; 237 mutable std::optional<O_NONBLOCKValueTy> O_NONBLOCKValue; 238 239 void reportBlockInCritSection(const CallEvent &call, CheckerContext &C) const; 240 241 [[nodiscard]] const NoteTag *createCritSectionNote(CritSectionMarker M, 242 CheckerContext &C) const; 243 244 [[nodiscard]] std::optional<MutexDescriptor> 245 checkDescriptorMatch(const CallEvent &Call, CheckerContext &C, 246 bool IsLock) const; 247 248 void handleLock(const MutexDescriptor &Mutex, const CallEvent &Call, 249 CheckerContext &C) const; 250 251 void handleUnlock(const MutexDescriptor &Mutex, const CallEvent &Call, 252 CheckerContext &C) const; 253 254 [[nodiscard]] bool isBlockingInCritSection(const CallEvent &Call, 255 CheckerContext &C) const; 256 257 public: 258 /// Process unlock. 259 /// Process lock. 260 /// Process blocking functions (sleep, getc, fgets, read, recv) 261 void checkPostCall(const CallEvent &Call, CheckerContext &C) const; 262 }; 263 264 } // end anonymous namespace 265 266 REGISTER_LIST_WITH_PROGRAMSTATE(ActiveCritSections, CritSectionMarker) 267 268 // Iterator traits for ImmutableList data structure 269 // that enable the use of STL algorithms. 270 // TODO: Move these to llvm::ImmutableList when overhauling immutable data 271 // structures for proper iterator concept support. 272 template <> 273 struct std::iterator_traits< 274 typename llvm::ImmutableList<CritSectionMarker>::iterator> { 275 using iterator_category = std::forward_iterator_tag; 276 using value_type = CritSectionMarker; 277 using difference_type = std::ptrdiff_t; 278 using reference = CritSectionMarker &; 279 using pointer = CritSectionMarker *; 280 }; 281 282 std::optional<MutexDescriptor> 283 BlockInCriticalSectionChecker::checkDescriptorMatch(const CallEvent &Call, 284 CheckerContext &C, 285 bool IsLock) const { 286 const auto Descriptor = 287 llvm::find_if(MutexDescriptors, [&Call, IsLock](auto &&Descriptor) { 288 return std::visit( 289 [&Call, IsLock](auto &&DescriptorImpl) { 290 return DescriptorImpl.matches(Call, IsLock); 291 }, 292 Descriptor); 293 }); 294 if (Descriptor != MutexDescriptors.end()) 295 return *Descriptor; 296 return std::nullopt; 297 } 298 299 static const MemRegion *skipStdBaseClassRegion(const MemRegion *Reg) { 300 while (Reg) { 301 const auto *BaseClassRegion = dyn_cast<CXXBaseObjectRegion>(Reg); 302 if (!BaseClassRegion || !isWithinStdNamespace(BaseClassRegion->getDecl())) 303 break; 304 Reg = BaseClassRegion->getSuperRegion(); 305 } 306 return Reg; 307 } 308 309 static const MemRegion *getRegion(const CallEvent &Call, 310 const MutexDescriptor &Descriptor, 311 bool IsLock) { 312 return std::visit( 313 [&Call, IsLock](auto &Descr) -> const MemRegion * { 314 return skipStdBaseClassRegion(Descr.getRegion(Call, IsLock)); 315 }, 316 Descriptor); 317 } 318 319 void BlockInCriticalSectionChecker::handleLock( 320 const MutexDescriptor &LockDescriptor, const CallEvent &Call, 321 CheckerContext &C) const { 322 const MemRegion *MutexRegion = 323 getRegion(Call, LockDescriptor, /*IsLock=*/true); 324 if (!MutexRegion) 325 return; 326 327 const CritSectionMarker MarkToAdd{Call.getOriginExpr(), MutexRegion}; 328 ProgramStateRef StateWithLockEvent = 329 C.getState()->add<ActiveCritSections>(MarkToAdd); 330 C.addTransition(StateWithLockEvent, createCritSectionNote(MarkToAdd, C)); 331 } 332 333 void BlockInCriticalSectionChecker::handleUnlock( 334 const MutexDescriptor &UnlockDescriptor, const CallEvent &Call, 335 CheckerContext &C) const { 336 const MemRegion *MutexRegion = 337 getRegion(Call, UnlockDescriptor, /*IsLock=*/false); 338 if (!MutexRegion) 339 return; 340 341 ProgramStateRef State = C.getState(); 342 const auto ActiveSections = State->get<ActiveCritSections>(); 343 const auto MostRecentLock = 344 llvm::find_if(ActiveSections, [MutexRegion](auto &&Marker) { 345 return Marker.LockReg == MutexRegion; 346 }); 347 if (MostRecentLock == ActiveSections.end()) 348 return; 349 350 // Build a new ImmutableList without this element. 351 auto &Factory = State->get_context<ActiveCritSections>(); 352 llvm::ImmutableList<CritSectionMarker> NewList = Factory.getEmptyList(); 353 for (auto It = ActiveSections.begin(), End = ActiveSections.end(); It != End; 354 ++It) { 355 if (It != MostRecentLock) 356 NewList = Factory.add(*It, NewList); 357 } 358 359 State = State->set<ActiveCritSections>(NewList); 360 C.addTransition(State); 361 } 362 363 bool BlockInCriticalSectionChecker::isBlockingInCritSection( 364 const CallEvent &Call, CheckerContext &C) const { 365 return BlockingFunctions.contains(Call) && 366 !C.getState()->get<ActiveCritSections>().isEmpty(); 367 } 368 369 void BlockInCriticalSectionChecker::checkPostCall(const CallEvent &Call, 370 CheckerContext &C) const { 371 if (isBlockingInCritSection(Call, C)) { 372 reportBlockInCritSection(Call, C); 373 } else if (std::optional<MutexDescriptor> LockDesc = 374 checkDescriptorMatch(Call, C, /*IsLock=*/true)) { 375 handleLock(*LockDesc, Call, C); 376 } else if (std::optional<MutexDescriptor> UnlockDesc = 377 checkDescriptorMatch(Call, C, /*IsLock=*/false)) { 378 handleUnlock(*UnlockDesc, Call, C); 379 } 380 } 381 382 void BlockInCriticalSectionChecker::reportBlockInCritSection( 383 const CallEvent &Call, CheckerContext &C) const { 384 ExplodedNode *ErrNode = C.generateNonFatalErrorNode(C.getState()); 385 if (!ErrNode) 386 return; 387 388 std::string msg; 389 llvm::raw_string_ostream os(msg); 390 os << "Call to blocking function '" << Call.getCalleeIdentifier()->getName() 391 << "' inside of critical section"; 392 auto R = std::make_unique<PathSensitiveBugReport>(BlockInCritSectionBugType, 393 os.str(), ErrNode); 394 // for 'read' and 'recv' call, check whether it's file descriptor(first 395 // argument) is 396 // created by 'open' API with O_NONBLOCK flag or is equal to -1, they will 397 // not cause block in these situations, don't report 398 StringRef FuncName = Call.getCalleeIdentifier()->getName(); 399 if (FuncName == "read" || FuncName == "recv") { 400 SVal SV = Call.getArgSVal(0); 401 SValBuilder &SVB = C.getSValBuilder(); 402 ProgramStateRef state = C.getState(); 403 ConditionTruthVal CTV = 404 state->areEqual(SV, SVB.makeIntVal(-1, C.getASTContext().IntTy)); 405 if (CTV.isConstrainedTrue()) 406 return; 407 408 if (SymbolRef SR = SV.getAsSymbol()) { 409 if (!O_NONBLOCKValue) 410 O_NONBLOCKValue = tryExpandAsInteger( 411 "O_NONBLOCK", C.getBugReporter().getPreprocessor()); 412 if (*O_NONBLOCKValue) 413 R->addVisitor<SuppressNonBlockingStreams>(SR, **O_NONBLOCKValue); 414 } 415 } 416 R->addRange(Call.getSourceRange()); 417 R->markInteresting(Call.getReturnValue()); 418 C.emitReport(std::move(R)); 419 } 420 421 const NoteTag * 422 BlockInCriticalSectionChecker::createCritSectionNote(CritSectionMarker M, 423 CheckerContext &C) const { 424 const BugType *BT = &this->BlockInCritSectionBugType; 425 return C.getNoteTag([M, BT](PathSensitiveBugReport &BR, 426 llvm::raw_ostream &OS) { 427 if (&BR.getBugType() != BT) 428 return; 429 430 // Get the lock events for the mutex of the current line's lock event. 431 const auto CritSectionBegins = 432 BR.getErrorNode()->getState()->get<ActiveCritSections>(); 433 llvm::SmallVector<CritSectionMarker, 4> LocksForMutex; 434 llvm::copy_if( 435 CritSectionBegins, std::back_inserter(LocksForMutex), 436 [M](const auto &Marker) { return Marker.LockReg == M.LockReg; }); 437 if (LocksForMutex.empty()) 438 return; 439 440 // As the ImmutableList builds the locks by prepending them, we 441 // reverse the list to get the correct order. 442 std::reverse(LocksForMutex.begin(), LocksForMutex.end()); 443 444 // Find the index of the lock expression in the list of all locks for a 445 // given mutex (in acquisition order). 446 const auto Position = 447 llvm::find_if(std::as_const(LocksForMutex), [M](const auto &Marker) { 448 return Marker.LockExpr == M.LockExpr; 449 }); 450 if (Position == LocksForMutex.end()) 451 return; 452 453 // If there is only one lock event, we don't need to specify how many times 454 // the critical section was entered. 455 if (LocksForMutex.size() == 1) { 456 OS << "Entering critical section here"; 457 return; 458 } 459 460 const auto IndexOfLock = 461 std::distance(std::as_const(LocksForMutex).begin(), Position); 462 463 const auto OrdinalOfLock = IndexOfLock + 1; 464 OS << "Entering critical section for the " << OrdinalOfLock 465 << llvm::getOrdinalSuffix(OrdinalOfLock) << " time here"; 466 }); 467 } 468 469 void ento::registerBlockInCriticalSectionChecker(CheckerManager &mgr) { 470 mgr.registerChecker<BlockInCriticalSectionChecker>(); 471 } 472 473 bool ento::shouldRegisterBlockInCriticalSectionChecker( 474 const CheckerManager &mgr) { 475 return true; 476 } 477