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.getState()->getStateManager().getContext();
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 return II == Guard;
119 }
120
121public:
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>(Val: Call).getCXXThisVal().getAsRegion();
139 }
140 return LockRegion;
141 }
142};
143
144using MutexDescriptor =
145 std::variant<FirstArgMutexDescriptor, MemberMutexDescriptor,
146 RAIIMutexDescriptor>;
147
148class SuppressNonBlockingStreams : public BugReporterVisitor {
149private:
150 const CallDescription OpenFunction{CDM::CLibrary, {"open"}, 2};
151 SymbolRef StreamSym;
152 const int NonBlockMacroVal;
153 bool Satisfied = false;
154
155public:
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(Ptr: 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: *CE))
180 return nullptr;
181
182 if (N->getSVal(S: 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(S: CE->getArg(Arg: 1)).getAsInteger();
189 if (!FlagVal)
190 return nullptr;
191
192 if ((*FlagVal & NonBlockMacroVal) != 0)
193 BR.markInvalid(Tag: getTag(), Data: nullptr);
194
195 return nullptr;
196 }
197};
198
199class BlockInCriticalSectionChecker : public Checker<check::PostCall> {
200private:
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
257public:
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
266REGISTER_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.
272template <>
273struct 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
282std::optional<MutexDescriptor>
283BlockInCriticalSectionChecker::checkDescriptorMatch(const CallEvent &Call,
284 CheckerContext &C,
285 bool IsLock) const {
286 const auto Descriptor =
287 llvm::find_if(Range: MutexDescriptors, P: [&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
299static const MemRegion *skipStdBaseClassRegion(const MemRegion *Reg) {
300 while (Reg) {
301 const auto *BaseClassRegion = dyn_cast<CXXBaseObjectRegion>(Val: Reg);
302 if (!BaseClassRegion || !isWithinStdNamespace(D: BaseClassRegion->getDecl()))
303 break;
304 Reg = BaseClassRegion->getSuperRegion();
305 }
306 return Reg;
307}
308
309static const MemRegion *getRegion(const CallEvent &Call,
310 const MutexDescriptor &Descriptor,
311 bool IsLock) {
312 return std::visit(
313 visitor: [&Call, IsLock](auto &Descr) -> const MemRegion * {
314 return skipStdBaseClassRegion(Descr.getRegion(Call, IsLock));
315 },
316 variants: Descriptor);
317}
318
319void BlockInCriticalSectionChecker::handleLock(
320 const MutexDescriptor &LockDescriptor, const CallEvent &Call,
321 CheckerContext &C) const {
322 const MemRegion *MutexRegion =
323 getRegion(Call, Descriptor: LockDescriptor, /*IsLock=*/true);
324 if (!MutexRegion)
325 return;
326
327 const CritSectionMarker MarkToAdd{.LockExpr: Call.getOriginExpr(), .LockReg: MutexRegion};
328 ProgramStateRef StateWithLockEvent =
329 C.getState()->add<ActiveCritSections>(K: MarkToAdd);
330 C.addTransition(State: StateWithLockEvent, Tag: createCritSectionNote(M: MarkToAdd, C));
331}
332
333void BlockInCriticalSectionChecker::handleUnlock(
334 const MutexDescriptor &UnlockDescriptor, const CallEvent &Call,
335 CheckerContext &C) const {
336 const MemRegion *MutexRegion =
337 getRegion(Call, Descriptor: 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(Range: ActiveSections, P: [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(Data: *It, L: NewList);
357 }
358
359 State = State->set<ActiveCritSections>(NewList);
360 C.addTransition(State);
361}
362
363bool BlockInCriticalSectionChecker::isBlockingInCritSection(
364 const CallEvent &Call, CheckerContext &C) const {
365 return BlockingFunctions.contains(Call) &&
366 !C.getState()->get<ActiveCritSections>().isEmpty();
367}
368
369void BlockInCriticalSectionChecker::checkPostCall(const CallEvent &Call,
370 CheckerContext &C) const {
371 if (isBlockingInCritSection(Call, C)) {
372 reportBlockInCritSection(call: Call, C);
373 } else if (std::optional<MutexDescriptor> LockDesc =
374 checkDescriptorMatch(Call, C, /*IsLock=*/true)) {
375 handleLock(LockDescriptor: *LockDesc, Call, C);
376 } else if (std::optional<MutexDescriptor> UnlockDesc =
377 checkDescriptorMatch(Call, C, /*IsLock=*/false)) {
378 handleUnlock(UnlockDescriptor: *UnlockDesc, Call, C);
379 }
380}
381
382void BlockInCriticalSectionChecker::reportBlockInCritSection(
383 const CallEvent &Call, CheckerContext &C) const {
384 ExplodedNode *ErrNode = C.generateNonFatalErrorNode(State: 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>(args: BlockInCritSectionBugType,
393 args&: os.str(), args&: 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(Index: 0);
401 SValBuilder &SVB = C.getSValBuilder();
402 ProgramStateRef state = C.getState();
403 ConditionTruthVal CTV =
404 state->areEqual(Lhs: SV, Rhs: SVB.makeIntVal(integer: -1, type: 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 Macro: "O_NONBLOCK", PP: C.getBugReporter().getPreprocessor());
412 if (*O_NONBLOCKValue)
413 R->addVisitor<SuppressNonBlockingStreams>(ConstructorArgs&: SR, ConstructorArgs&: **O_NONBLOCKValue);
414 }
415 }
416 R->addRange(R: Call.getSourceRange());
417 R->markInteresting(V: Call.getReturnValue());
418 C.emitReport(R: std::move(R));
419}
420
421const NoteTag *
422BlockInCriticalSectionChecker::createCritSectionNote(CritSectionMarker M,
423 CheckerContext &C) const {
424 const BugType *BT = &this->BlockInCritSectionBugType;
425 return C.getNoteTag(Cb: [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 Range: CritSectionBegins, Out: std::back_inserter(x&: LocksForMutex),
436 P: [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(first: LocksForMutex.begin(), last: 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(Range: std::as_const(t&: LocksForMutex), P: [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(first: std::as_const(t&: LocksForMutex).begin(), last: Position);
462
463 const auto OrdinalOfLock = IndexOfLock + 1;
464 OS << "Entering critical section for the " << OrdinalOfLock
465 << llvm::getOrdinalSuffix(Val: OrdinalOfLock) << " time here";
466 });
467}
468
469void ento::registerBlockInCriticalSectionChecker(CheckerManager &mgr) {
470 mgr.registerChecker<BlockInCriticalSectionChecker>();
471}
472
473bool ento::shouldRegisterBlockInCriticalSectionChecker(
474 const CheckerManager &mgr) {
475 return true;
476}
477