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/StringExtras.h"
29
30#include <iterator>
31#include <utility>
32
33using namespace clang;
34using namespace ento;
35
36static const MemRegion *getFirstArgRegion(const CallEvent &Call) {
37 return Call.getArgSVal(Index: 0).getAsRegion();
38}
39
40static const MemRegion *getCXXThisRegion(const CallEvent &Call) {
41 return cast<CXXMemberCall>(Val: Call).getCXXThisVal().getAsRegion();
42}
43
44static const MemRegion *getObjectUnderConstruction(const CallEvent &Call) {
45 if (std::optional<SVal> Object = Call.getReturnValueUnderConstruction())
46 return Object->getAsRegion();
47 return nullptr;
48}
49
50static const MemRegion *getCXXDestructorThisRegion(const CallEvent &Call) {
51 // Match both implicit (CXXDestructorCall) and explicit p->~T()
52 // (CXXMemberCall) destructions using the common CXXInstanceCall base.
53 const auto *Instance = dyn_cast<CXXInstanceCall>(Val: &Call);
54 if (Instance && isa_and_nonnull<CXXDestructorDecl>(Val: Instance->getDecl()))
55 return Instance->getCXXThisVal().getAsRegion();
56 return nullptr;
57}
58
59static bool isNotDeferLockUniqueLock(const CallEvent &Call) {
60 // Use the constructor's declared parameter type to identify the defer_lock_t
61 // overload.
62 ArrayRef<ParmVarDecl *> Params = Call.parameters();
63 if (Params.size() < 2)
64 return true;
65 QualType ParamType = Params[1]->getType().getNonReferenceType();
66 const auto *RD = ParamType->getAsRecordDecl();
67 return !(RD && RD->getName() == "defer_lock_t" && RD->isInStdNamespace());
68}
69
70namespace {
71
72struct CritSectionMarker {
73 const Expr *LockExpr{};
74 const MemRegion *LockReg{};
75
76 void Profile(llvm::FoldingSetNodeID &ID) const {
77 ID.Add(x: LockExpr);
78 ID.Add(x: LockReg);
79 }
80
81 [[nodiscard]] constexpr bool
82 operator==(const CritSectionMarker &Other) const noexcept {
83 return LockExpr == Other.LockExpr && LockReg == Other.LockReg;
84 }
85 [[nodiscard]] constexpr bool
86 operator!=(const CritSectionMarker &Other) const noexcept {
87 return !(*this == Other);
88 }
89};
90
91enum class RoleKind {
92 Lock,
93 Unlock,
94};
95
96// llvm::function_ref does not reject stateful functors/capturing lambdas, so
97// function pointers are used to avoid future issues coming from those objects'
98// lifetimes (more specifically to prevent such configuration entries from
99// compiling, increasing robustness).
100using GetRegionFn = const MemRegion *(*)(const CallEvent &);
101using FilterFn = bool (*)(const CallEvent &);
102
103struct ThreadingCallDescription {
104 RoleKind Role;
105 GetRegionFn GetRegion = getFirstArgRegion;
106 FilterFn Filter = [](const CallEvent &) { return true; };
107};
108
109class SuppressNonBlockingStreams : public BugReporterVisitor {
110private:
111 const CallDescription OpenFunction{CDM::CLibrary, {"open"}, 2};
112 SymbolRef StreamSym;
113 const int NonBlockMacroVal;
114 bool Satisfied = false;
115
116public:
117 SuppressNonBlockingStreams(SymbolRef StreamSym, int NonBlockMacroVal)
118 : StreamSym(StreamSym), NonBlockMacroVal(NonBlockMacroVal) {}
119
120 static void *getTag() {
121 static bool Tag;
122 return &Tag;
123 }
124
125 void Profile(llvm::FoldingSetNodeID &ID) const override {
126 ID.AddPointer(Ptr: getTag());
127 }
128
129 PathDiagnosticPieceRef VisitNode(const ExplodedNode *N,
130 BugReporterContext &BRC,
131 PathSensitiveBugReport &BR) override {
132 if (Satisfied)
133 return nullptr;
134
135 std::optional<StmtPoint> Point = N->getLocationAs<StmtPoint>();
136 if (!Point)
137 return nullptr;
138
139 const auto *CE = Point->getStmtAs<CallExpr>();
140 if (!CE || !OpenFunction.matchesAsWritten(CE: *CE))
141 return nullptr;
142
143 if (N->getSVal(E: CE).getAsSymbol() != StreamSym)
144 return nullptr;
145
146 Satisfied = true;
147
148 // Check if open's second argument contains O_NONBLOCK
149 const llvm::APSInt *FlagVal = N->getSVal(E: CE->getArg(Arg: 1)).getAsInteger();
150 if (!FlagVal)
151 return nullptr;
152
153 if ((*FlagVal & NonBlockMacroVal) != 0)
154 BR.markInvalid(Tag: getTag(), Data: nullptr);
155
156 return nullptr;
157 }
158};
159
160class BlockInCriticalSectionChecker
161 : public Checker<check::PostCall, eval::Call> {
162private:
163 const CallDescriptionMap<ThreadingCallDescription> ThreadingCalls{
164 // NOTE: There are standard library implementations where some methods
165 // of `std::mutex` are inherited from an implementation detail base
166 // class, and those aren't matched by the name specification {"std",
167 // "mutex", "lock"}.
168 // As a workaround here we omit the class name and only require the
169 // presence of the name parts "std" and "lock"/"unlock".
170 // TODO: Ensure that CallDescription understands inherited methods.
171 {{CDM::CXXMethod, {"std", /*"mutex",*/ "lock"}, 0},
172 {.Role: RoleKind::Lock, .GetRegion: getCXXThisRegion}},
173 {{CDM::CXXMethod, {"std", /*"mutex",*/ "unlock"}, 0},
174 {.Role: RoleKind::Unlock, .GetRegion: getCXXThisRegion}},
175 {{CDM::CLibrary, {"pthread_mutex_lock"}, 1}, {.Role: RoleKind::Lock}},
176 {{CDM::CLibrary, {"pthread_mutex_unlock"}, 1}, {.Role: RoleKind::Unlock}},
177 {{CDM::CLibrary, {"mtx_lock"}, 1}, {.Role: RoleKind::Lock}},
178 {{CDM::CLibrary, {"mtx_unlock"}, 1}, {.Role: RoleKind::Unlock}},
179 {{CDM::CLibrary, {"pthread_mutex_trylock"}, 1}, {.Role: RoleKind::Lock}},
180 {{CDM::CLibrary, {"mtx_trylock"}, 1}, {.Role: RoleKind::Lock}},
181 {{CDM::CLibrary, {"mtx_timedlock"}, 1}, {.Role: RoleKind::Lock}},
182 {{CDM::CXXMethod, {"lock_guard", "lock_guard"}},
183 {.Role: RoleKind::Lock, .GetRegion: getObjectUnderConstruction}},
184 {{CDM::CXXMethod, {"lock_guard", "~lock_guard"}},
185 {.Role: RoleKind::Unlock, .GetRegion: getCXXDestructorThisRegion}},
186 {{CDM::CXXMethod, {"unique_lock", "unique_lock"}},
187 {.Role: RoleKind::Lock, .GetRegion: getObjectUnderConstruction, .Filter: isNotDeferLockUniqueLock}},
188 {{CDM::CXXMethod, {"unique_lock", "~unique_lock"}},
189 {.Role: RoleKind::Unlock, .GetRegion: getCXXDestructorThisRegion}},
190 {{CDM::CXXMethod, {"scoped_lock", "scoped_lock"}},
191 {.Role: RoleKind::Lock, .GetRegion: getObjectUnderConstruction}},
192 {{CDM::CXXMethod, {"scoped_lock", "~scoped_lock"}},
193 {.Role: RoleKind::Unlock, .GetRegion: getCXXDestructorThisRegion}},
194 };
195
196 const CallDescriptionSet BlockingFunctions{{CDM::CLibrary, {"sleep"}},
197 {CDM::CLibrary, {"getc"}},
198 {CDM::CLibrary, {"fgets"}},
199 {CDM::CLibrary, {"read"}},
200 {CDM::CLibrary, {"recv"}}};
201
202 const BugType BlockInCritSectionBugType{
203 this, "Call to blocking function in critical section", "Blocking Error"};
204
205 using O_NONBLOCKValueTy = std::optional<int>;
206 mutable std::optional<O_NONBLOCKValueTy> O_NONBLOCKValue;
207
208 void reportBlockInCritSection(const CallEvent &call, CheckerContext &C) const;
209
210 [[nodiscard]] const NoteTag *createCritSectionNote(CritSectionMarker M,
211 CheckerContext &C) const;
212
213 [[nodiscard]] const ThreadingCallDescription *
214 lookupThreadingCall(const CallEvent &Call) const;
215
216 void handleLock(const ThreadingCallDescription &Desc, const CallEvent &Call,
217 CheckerContext &C, ProgramStateRef State) const;
218
219 void handleUnlock(const ThreadingCallDescription &Desc, const CallEvent &Call,
220 CheckerContext &C) const;
221
222 [[nodiscard]] bool isBlockingInCritSection(const CallEvent &Call,
223 CheckerContext &C) const;
224
225public:
226 /// Process unlock.
227 /// Process lock.
228 /// Process blocking functions (sleep, getc, fgets, read, recv)
229 void checkPostCall(const CallEvent &Call, CheckerContext &C) const;
230
231 // Process RAII lock guard constructors (to avoid double-counting by
232 // inlining).
233 bool evalCall(const CallEvent &Call, CheckerContext &C) const;
234};
235
236} // end anonymous namespace
237
238REGISTER_LIST_WITH_PROGRAMSTATE(ActiveCritSections, CritSectionMarker)
239
240const ThreadingCallDescription *
241BlockInCriticalSectionChecker::lookupThreadingCall(
242 const CallEvent &Call) const {
243 const ThreadingCallDescription *Desc = ThreadingCalls.lookup(Call);
244 if (!Desc)
245 return nullptr;
246 if (!Desc->Filter(Call))
247 return nullptr;
248 return Desc;
249}
250
251static const MemRegion *skipStdBaseClassRegion(const MemRegion *Reg) {
252 while (Reg) {
253 const auto *BaseClassRegion = dyn_cast<CXXBaseObjectRegion>(Val: Reg);
254 if (!BaseClassRegion || !isWithinStdNamespace(D: BaseClassRegion->getDecl()))
255 break;
256 Reg = BaseClassRegion->getSuperRegion();
257 }
258 return Reg;
259}
260
261static const MemRegion *getMutexRegion(const CallEvent &Call,
262 const ThreadingCallDescription &Desc) {
263 return skipStdBaseClassRegion(Reg: Desc.GetRegion(Call));
264}
265
266void BlockInCriticalSectionChecker::handleLock(
267 const ThreadingCallDescription &Desc, const CallEvent &Call,
268 CheckerContext &C, ProgramStateRef State) const {
269 const MemRegion *MutexRegion = getMutexRegion(Call, Desc);
270 if (!MutexRegion)
271 return;
272
273 const CritSectionMarker MarkToAdd{.LockExpr: Call.getOriginExpr(), .LockReg: MutexRegion};
274 ProgramStateRef StateWithLockEvent =
275 State->add<ActiveCritSections>(K: MarkToAdd);
276 C.addTransition(State: StateWithLockEvent, Tag: createCritSectionNote(M: MarkToAdd, C));
277}
278
279void BlockInCriticalSectionChecker::handleUnlock(
280 const ThreadingCallDescription &Desc, const CallEvent &Call,
281 CheckerContext &C) const {
282 const MemRegion *MutexRegion = getMutexRegion(Call, Desc);
283 if (!MutexRegion)
284 return;
285
286 ProgramStateRef State = C.getState();
287 const auto ActiveSections = State->get<ActiveCritSections>();
288 const auto MostRecentLock =
289 llvm::find_if(Range: ActiveSections, P: [MutexRegion](auto &&Marker) {
290 return Marker.LockReg == MutexRegion;
291 });
292 if (MostRecentLock == ActiveSections.end())
293 return;
294
295 // Build a new ImmutableList without this element.
296 auto &Factory = State->get_context<ActiveCritSections>();
297 llvm::ImmutableList<CritSectionMarker> NewList = Factory.getEmptyList();
298 for (auto It = ActiveSections.begin(), End = ActiveSections.end(); It != End;
299 ++It) {
300 if (It != MostRecentLock)
301 NewList = Factory.add(Data: *It, L: NewList);
302 }
303
304 State = State->set<ActiveCritSections>(NewList);
305 C.addTransition(State);
306}
307
308bool BlockInCriticalSectionChecker::isBlockingInCritSection(
309 const CallEvent &Call, CheckerContext &C) const {
310 return BlockingFunctions.contains(Call) &&
311 !C.getState()->get<ActiveCritSections>().isEmpty();
312}
313
314void BlockInCriticalSectionChecker::checkPostCall(const CallEvent &Call,
315 CheckerContext &C) const {
316 if (isBlockingInCritSection(Call, C)) {
317 reportBlockInCritSection(call: Call, C);
318 return;
319 }
320
321 // Constructors are modeled in evalCall, so skip them before the lookup.
322 if (isa<CXXConstructorCall>(Val: Call))
323 return;
324
325 const ThreadingCallDescription *Desc = lookupThreadingCall(Call);
326 if (!Desc)
327 return;
328
329 switch (Desc->Role) {
330 case RoleKind::Lock:
331 handleLock(Desc: *Desc, Call, C, State: C.getState());
332 return;
333 case RoleKind::Unlock:
334 handleUnlock(Desc: *Desc, Call, C);
335 return;
336 }
337}
338
339bool BlockInCriticalSectionChecker::evalCall(const CallEvent &Call,
340 CheckerContext &C) const {
341 // Only RAII constructors are modeled here, so skip everything else before
342 // the lookup.
343 if (!isa<CXXConstructorCall>(Val: Call))
344 return false;
345
346 const ThreadingCallDescription *Desc = lookupThreadingCall(Call);
347 if (!Desc)
348 return false;
349
350 // Every constructor entry in the configuration is a lock acquisition.
351 // This seems to be reasonable, but if modeling requires to relax this
352 // assumption, we can do so.
353 assert(Desc->Role == RoleKind::Lock &&
354 "Constructor threading call must be a lock");
355
356 ProgramStateRef State = C.getState();
357 // Escape the object under construction to model the side-effects of the
358 // constructor.
359 if (const auto *Ctor = dyn_cast<AnyCXXConstructorCall>(Val: &Call)) {
360 const MemRegion *ObjRegion = Ctor->getCXXThisVal().getAsRegion();
361 State = State->invalidateRegions(Regions: ObjRegion, Elem: C.getCFGElementRef(),
362 BlockCount: C.blockCount(), SF: C.getStackFrame(),
363 /*CausesPointerEscape=*/false);
364 }
365 handleLock(Desc: *Desc, Call, C, State);
366 return true;
367}
368
369void BlockInCriticalSectionChecker::reportBlockInCritSection(
370 const CallEvent &Call, CheckerContext &C) const {
371 ExplodedNode *ErrNode = C.generateNonFatalErrorNode(State: C.getState());
372 if (!ErrNode)
373 return;
374
375 std::string msg;
376 llvm::raw_string_ostream os(msg);
377 os << "Call to blocking function '" << Call.getCalleeIdentifier()->getName()
378 << "' inside of critical section";
379 auto R = std::make_unique<PathSensitiveBugReport>(args: BlockInCritSectionBugType,
380 args&: os.str(), args&: ErrNode);
381 // for 'read' and 'recv' call, check whether it's file descriptor(first
382 // argument) is
383 // created by 'open' API with O_NONBLOCK flag or is equal to -1, they will
384 // not cause block in these situations, don't report
385 StringRef FuncName = Call.getCalleeIdentifier()->getName();
386 if (FuncName == "read" || FuncName == "recv") {
387 SVal SV = Call.getArgSVal(Index: 0);
388 SValBuilder &SVB = C.getSValBuilder();
389 ProgramStateRef state = C.getState();
390 ConditionTruthVal CTV =
391 state->areEqual(Lhs: SV, Rhs: SVB.makeIntVal(integer: -1, type: C.getASTContext().IntTy));
392 if (CTV.isConstrainedTrue())
393 return;
394
395 if (SymbolRef SR = SV.getAsSymbol()) {
396 if (!O_NONBLOCKValue)
397 O_NONBLOCKValue = tryExpandAsInteger(
398 Macro: "O_NONBLOCK", PP: C.getBugReporter().getPreprocessor());
399 if (*O_NONBLOCKValue)
400 R->addVisitor<SuppressNonBlockingStreams>(ConstructorArgs&: SR, ConstructorArgs&: **O_NONBLOCKValue);
401 }
402 }
403 R->addRange(R: Call.getSourceRange());
404 R->markInteresting(V: Call.getReturnValue());
405 C.emitReport(R: std::move(R));
406}
407
408const NoteTag *
409BlockInCriticalSectionChecker::createCritSectionNote(CritSectionMarker M,
410 CheckerContext &C) const {
411 const BugType *BT = &this->BlockInCritSectionBugType;
412 return C.getNoteTag(Cb: [M, BT](PathSensitiveBugReport &BR,
413 llvm::raw_ostream &OS) {
414 if (&BR.getBugType() != BT)
415 return;
416
417 // Get the lock events for the mutex of the current line's lock event.
418 const auto CritSectionBegins =
419 BR.getErrorNode()->getState()->get<ActiveCritSections>();
420 llvm::SmallVector<CritSectionMarker, 4> LocksForMutex;
421 llvm::copy_if(
422 Range: CritSectionBegins, Out: std::back_inserter(x&: LocksForMutex),
423 P: [M](const auto &Marker) { return Marker.LockReg == M.LockReg; });
424 if (LocksForMutex.empty())
425 return;
426
427 // As the ImmutableList builds the locks by prepending them, we
428 // reverse the list to get the correct order.
429 std::reverse(first: LocksForMutex.begin(), last: LocksForMutex.end());
430
431 // Find the index of the lock expression in the list of all locks for a
432 // given mutex (in acquisition order).
433 const auto Position =
434 llvm::find_if(Range: std::as_const(t&: LocksForMutex), P: [M](const auto &Marker) {
435 return Marker.LockExpr == M.LockExpr;
436 });
437 if (Position == LocksForMutex.end())
438 return;
439
440 // If there is only one lock event, we don't need to specify how many times
441 // the critical section was entered.
442 if (LocksForMutex.size() == 1) {
443 OS << "Entering critical section here";
444 return;
445 }
446
447 const auto IndexOfLock =
448 std::distance(first: std::as_const(t&: LocksForMutex).begin(), last: Position);
449
450 const auto OrdinalOfLock = IndexOfLock + 1;
451 OS << "Entering critical section for the " << OrdinalOfLock
452 << llvm::getOrdinalSuffix(Val: OrdinalOfLock) << " time here";
453 });
454}
455
456void ento::registerBlockInCriticalSectionChecker(CheckerManager &mgr) {
457 mgr.registerChecker<BlockInCriticalSectionChecker>();
458}
459
460bool ento::shouldRegisterBlockInCriticalSectionChecker(
461 const CheckerManager &mgr) {
462 return true;
463}
464