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