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 MemberMutexDescriptor({/*MatchAs=*/CDM::CXXMethod, 151 /*QualifiedName=*/{"std", "mutex", "lock"}, 152 /*RequiredArgs=*/0}, 153 {CDM::CXXMethod, {"std", "mutex", "unlock"}, 0}), 154 FirstArgMutexDescriptor({CDM::CLibrary, {"pthread_mutex_lock"}, 1}, 155 {CDM::CLibrary, {"pthread_mutex_unlock"}, 1}), 156 FirstArgMutexDescriptor({CDM::CLibrary, {"mtx_lock"}, 1}, 157 {CDM::CLibrary, {"mtx_unlock"}, 1}), 158 FirstArgMutexDescriptor({CDM::CLibrary, {"pthread_mutex_trylock"}, 1}, 159 {CDM::CLibrary, {"pthread_mutex_unlock"}, 1}), 160 FirstArgMutexDescriptor({CDM::CLibrary, {"mtx_trylock"}, 1}, 161 {CDM::CLibrary, {"mtx_unlock"}, 1}), 162 FirstArgMutexDescriptor({CDM::CLibrary, {"mtx_timedlock"}, 1}, 163 {CDM::CLibrary, {"mtx_unlock"}, 1}), 164 RAIIMutexDescriptor("lock_guard"), 165 RAIIMutexDescriptor("unique_lock")}; 166 167 const CallDescriptionSet BlockingFunctions{{CDM::CLibrary, {"sleep"}}, 168 {CDM::CLibrary, {"getc"}}, 169 {CDM::CLibrary, {"fgets"}}, 170 {CDM::CLibrary, {"read"}}, 171 {CDM::CLibrary, {"recv"}}}; 172 173 const BugType BlockInCritSectionBugType{ 174 this, "Call to blocking function in critical section", "Blocking Error"}; 175 176 void reportBlockInCritSection(const CallEvent &call, CheckerContext &C) const; 177 178 [[nodiscard]] const NoteTag *createCritSectionNote(CritSectionMarker M, 179 CheckerContext &C) const; 180 181 [[nodiscard]] std::optional<MutexDescriptor> 182 checkDescriptorMatch(const CallEvent &Call, CheckerContext &C, 183 bool IsLock) const; 184 185 void handleLock(const MutexDescriptor &Mutex, const CallEvent &Call, 186 CheckerContext &C) const; 187 188 void handleUnlock(const MutexDescriptor &Mutex, const CallEvent &Call, 189 CheckerContext &C) const; 190 191 [[nodiscard]] bool isBlockingInCritSection(const CallEvent &Call, 192 CheckerContext &C) const; 193 194 public: 195 /// Process unlock. 196 /// Process lock. 197 /// Process blocking functions (sleep, getc, fgets, read, recv) 198 void checkPostCall(const CallEvent &Call, CheckerContext &C) const; 199 }; 200 201 } // end anonymous namespace 202 203 REGISTER_LIST_WITH_PROGRAMSTATE(ActiveCritSections, CritSectionMarker) 204 205 namespace std { 206 // Iterator traits for ImmutableList data structure 207 // that enable the use of STL algorithms. 208 // TODO: Move these to llvm::ImmutableList when overhauling immutable data 209 // structures for proper iterator concept support. 210 template <> 211 struct iterator_traits< 212 typename llvm::ImmutableList<CritSectionMarker>::iterator> { 213 using iterator_category = std::forward_iterator_tag; 214 using value_type = CritSectionMarker; 215 using difference_type = std::ptrdiff_t; 216 using reference = CritSectionMarker &; 217 using pointer = CritSectionMarker *; 218 }; 219 } // namespace std 220 221 std::optional<MutexDescriptor> 222 BlockInCriticalSectionChecker::checkDescriptorMatch(const CallEvent &Call, 223 CheckerContext &C, 224 bool IsLock) const { 225 const auto Descriptor = 226 llvm::find_if(MutexDescriptors, [&Call, IsLock](auto &&Descriptor) { 227 return std::visit( 228 [&Call, IsLock](auto &&DescriptorImpl) { 229 return DescriptorImpl.matches(Call, IsLock); 230 }, 231 Descriptor); 232 }); 233 if (Descriptor != MutexDescriptors.end()) 234 return *Descriptor; 235 return std::nullopt; 236 } 237 238 static const MemRegion *getRegion(const CallEvent &Call, 239 const MutexDescriptor &Descriptor, 240 bool IsLock) { 241 return std::visit( 242 [&Call, IsLock](auto &&Descriptor) { 243 return Descriptor.getRegion(Call, IsLock); 244 }, 245 Descriptor); 246 } 247 248 void BlockInCriticalSectionChecker::handleLock( 249 const MutexDescriptor &LockDescriptor, const CallEvent &Call, 250 CheckerContext &C) const { 251 const MemRegion *MutexRegion = 252 getRegion(Call, LockDescriptor, /*IsLock=*/true); 253 if (!MutexRegion) 254 return; 255 256 const CritSectionMarker MarkToAdd{Call.getOriginExpr(), MutexRegion}; 257 ProgramStateRef StateWithLockEvent = 258 C.getState()->add<ActiveCritSections>(MarkToAdd); 259 C.addTransition(StateWithLockEvent, createCritSectionNote(MarkToAdd, C)); 260 } 261 262 void BlockInCriticalSectionChecker::handleUnlock( 263 const MutexDescriptor &UnlockDescriptor, const CallEvent &Call, 264 CheckerContext &C) const { 265 const MemRegion *MutexRegion = 266 getRegion(Call, UnlockDescriptor, /*IsLock=*/false); 267 if (!MutexRegion) 268 return; 269 270 ProgramStateRef State = C.getState(); 271 const auto ActiveSections = State->get<ActiveCritSections>(); 272 const auto MostRecentLock = 273 llvm::find_if(ActiveSections, [MutexRegion](auto &&Marker) { 274 return Marker.LockReg == MutexRegion; 275 }); 276 if (MostRecentLock == ActiveSections.end()) 277 return; 278 279 // Build a new ImmutableList without this element. 280 auto &Factory = State->get_context<ActiveCritSections>(); 281 llvm::ImmutableList<CritSectionMarker> NewList = Factory.getEmptyList(); 282 for (auto It = ActiveSections.begin(), End = ActiveSections.end(); It != End; 283 ++It) { 284 if (It != MostRecentLock) 285 NewList = Factory.add(*It, NewList); 286 } 287 288 State = State->set<ActiveCritSections>(NewList); 289 C.addTransition(State); 290 } 291 292 bool BlockInCriticalSectionChecker::isBlockingInCritSection( 293 const CallEvent &Call, CheckerContext &C) const { 294 return BlockingFunctions.contains(Call) && 295 !C.getState()->get<ActiveCritSections>().isEmpty(); 296 } 297 298 void BlockInCriticalSectionChecker::checkPostCall(const CallEvent &Call, 299 CheckerContext &C) const { 300 if (isBlockingInCritSection(Call, C)) { 301 reportBlockInCritSection(Call, C); 302 } else if (std::optional<MutexDescriptor> LockDesc = 303 checkDescriptorMatch(Call, C, /*IsLock=*/true)) { 304 handleLock(*LockDesc, Call, C); 305 } else if (std::optional<MutexDescriptor> UnlockDesc = 306 checkDescriptorMatch(Call, C, /*IsLock=*/false)) { 307 handleUnlock(*UnlockDesc, Call, C); 308 } 309 } 310 311 void BlockInCriticalSectionChecker::reportBlockInCritSection( 312 const CallEvent &Call, CheckerContext &C) const { 313 ExplodedNode *ErrNode = C.generateNonFatalErrorNode(C.getState()); 314 if (!ErrNode) 315 return; 316 317 std::string msg; 318 llvm::raw_string_ostream os(msg); 319 os << "Call to blocking function '" << Call.getCalleeIdentifier()->getName() 320 << "' inside of critical section"; 321 auto R = std::make_unique<PathSensitiveBugReport>(BlockInCritSectionBugType, 322 os.str(), ErrNode); 323 R->addRange(Call.getSourceRange()); 324 R->markInteresting(Call.getReturnValue()); 325 C.emitReport(std::move(R)); 326 } 327 328 const NoteTag * 329 BlockInCriticalSectionChecker::createCritSectionNote(CritSectionMarker M, 330 CheckerContext &C) const { 331 const BugType *BT = &this->BlockInCritSectionBugType; 332 return C.getNoteTag([M, BT](PathSensitiveBugReport &BR, 333 llvm::raw_ostream &OS) { 334 if (&BR.getBugType() != BT) 335 return; 336 337 // Get the lock events for the mutex of the current line's lock event. 338 const auto CritSectionBegins = 339 BR.getErrorNode()->getState()->get<ActiveCritSections>(); 340 llvm::SmallVector<CritSectionMarker, 4> LocksForMutex; 341 llvm::copy_if( 342 CritSectionBegins, std::back_inserter(LocksForMutex), 343 [M](const auto &Marker) { return Marker.LockReg == M.LockReg; }); 344 if (LocksForMutex.empty()) 345 return; 346 347 // As the ImmutableList builds the locks by prepending them, we 348 // reverse the list to get the correct order. 349 std::reverse(LocksForMutex.begin(), LocksForMutex.end()); 350 351 // Find the index of the lock expression in the list of all locks for a 352 // given mutex (in acquisition order). 353 const auto Position = 354 llvm::find_if(std::as_const(LocksForMutex), [M](const auto &Marker) { 355 return Marker.LockExpr == M.LockExpr; 356 }); 357 if (Position == LocksForMutex.end()) 358 return; 359 360 // If there is only one lock event, we don't need to specify how many times 361 // the critical section was entered. 362 if (LocksForMutex.size() == 1) { 363 OS << "Entering critical section here"; 364 return; 365 } 366 367 const auto IndexOfLock = 368 std::distance(std::as_const(LocksForMutex).begin(), Position); 369 370 const auto OrdinalOfLock = IndexOfLock + 1; 371 OS << "Entering critical section for the " << OrdinalOfLock 372 << llvm::getOrdinalSuffix(OrdinalOfLock) << " time here"; 373 }); 374 } 375 376 void ento::registerBlockInCriticalSectionChecker(CheckerManager &mgr) { 377 mgr.registerChecker<BlockInCriticalSectionChecker>(); 378 } 379 380 bool ento::shouldRegisterBlockInCriticalSectionChecker( 381 const CheckerManager &mgr) { 382 return true; 383 } 384