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