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
34using namespace clang;
35using namespace ento;
36
37namespace {
38
39struct CritSectionMarker {
40 const Expr *LockExpr{};
41 const MemRegion *LockReg{};
42
43 void Profile(llvm::FoldingSetNodeID &ID) const {
44 ID.Add(x: LockExpr);
45 ID.Add(x: 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
58class CallDescriptionBasedMatcher {
59 CallDescription LockFn;
60 CallDescription UnlockFn;
61
62public:
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
74class FirstArgMutexDescriptor : public CallDescriptionBasedMatcher {
75public:
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(Index: 0).getAsRegion();
81 }
82};
83
84class MemberMutexDescriptor : public CallDescriptionBasedMatcher {
85public:
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>(Val: Call).getCXXThisVal().getAsRegion();
91 }
92};
93
94class 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(Name: 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
120public:
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>(Val: Call).getCXXThisVal().getAsRegion();
138 }
139 return LockRegion;
140 }
141};
142
143using MutexDescriptor =
144 std::variant<FirstArgMutexDescriptor, MemberMutexDescriptor,
145 RAIIMutexDescriptor>;
146
147class BlockInCriticalSectionChecker : public Checker<check::PostCall> {
148private:
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
202public:
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
211REGISTER_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.
217template <>
218struct 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
227std::optional<MutexDescriptor>
228BlockInCriticalSectionChecker::checkDescriptorMatch(const CallEvent &Call,
229 CheckerContext &C,
230 bool IsLock) const {
231 const auto Descriptor =
232 llvm::find_if(Range: MutexDescriptors, P: [&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
244static const MemRegion *getRegion(const CallEvent &Call,
245 const MutexDescriptor &Descriptor,
246 bool IsLock) {
247 return std::visit(
248 visitor: [&Call, IsLock](auto &&Descriptor) {
249 return Descriptor.getRegion(Call, IsLock);
250 },
251 variants: Descriptor);
252}
253
254void BlockInCriticalSectionChecker::handleLock(
255 const MutexDescriptor &LockDescriptor, const CallEvent &Call,
256 CheckerContext &C) const {
257 const MemRegion *MutexRegion =
258 getRegion(Call, Descriptor: LockDescriptor, /*IsLock=*/true);
259 if (!MutexRegion)
260 return;
261
262 const CritSectionMarker MarkToAdd{.LockExpr: Call.getOriginExpr(), .LockReg: MutexRegion};
263 ProgramStateRef StateWithLockEvent =
264 C.getState()->add<ActiveCritSections>(K: MarkToAdd);
265 C.addTransition(State: StateWithLockEvent, Tag: createCritSectionNote(M: MarkToAdd, C));
266}
267
268void BlockInCriticalSectionChecker::handleUnlock(
269 const MutexDescriptor &UnlockDescriptor, const CallEvent &Call,
270 CheckerContext &C) const {
271 const MemRegion *MutexRegion =
272 getRegion(Call, Descriptor: 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(Range: ActiveSections, P: [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(Data: *It, L: NewList);
292 }
293
294 State = State->set<ActiveCritSections>(NewList);
295 C.addTransition(State);
296}
297
298bool BlockInCriticalSectionChecker::isBlockingInCritSection(
299 const CallEvent &Call, CheckerContext &C) const {
300 return BlockingFunctions.contains(Call) &&
301 !C.getState()->get<ActiveCritSections>().isEmpty();
302}
303
304void BlockInCriticalSectionChecker::checkPostCall(const CallEvent &Call,
305 CheckerContext &C) const {
306 if (isBlockingInCritSection(Call, C)) {
307 reportBlockInCritSection(call: Call, C);
308 } else if (std::optional<MutexDescriptor> LockDesc =
309 checkDescriptorMatch(Call, C, /*IsLock=*/true)) {
310 handleLock(LockDescriptor: *LockDesc, Call, C);
311 } else if (std::optional<MutexDescriptor> UnlockDesc =
312 checkDescriptorMatch(Call, C, /*IsLock=*/false)) {
313 handleUnlock(UnlockDescriptor: *UnlockDesc, Call, C);
314 }
315}
316
317void BlockInCriticalSectionChecker::reportBlockInCritSection(
318 const CallEvent &Call, CheckerContext &C) const {
319 ExplodedNode *ErrNode = C.generateNonFatalErrorNode(State: 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>(args: BlockInCritSectionBugType,
328 args&: os.str(), args&: ErrNode);
329 R->addRange(R: Call.getSourceRange());
330 R->markInteresting(V: Call.getReturnValue());
331 C.emitReport(R: std::move(R));
332}
333
334const NoteTag *
335BlockInCriticalSectionChecker::createCritSectionNote(CritSectionMarker M,
336 CheckerContext &C) const {
337 const BugType *BT = &this->BlockInCritSectionBugType;
338 return C.getNoteTag(Cb: [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 Range: CritSectionBegins, Out: std::back_inserter(x&: LocksForMutex),
349 P: [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(first: LocksForMutex.begin(), last: 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(Range: std::as_const(t&: LocksForMutex), P: [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(first: std::as_const(t&: LocksForMutex).begin(), last: Position);
375
376 const auto OrdinalOfLock = IndexOfLock + 1;
377 OS << "Entering critical section for the " << OrdinalOfLock
378 << llvm::getOrdinalSuffix(Val: OrdinalOfLock) << " time here";
379 });
380}
381
382void ento::registerBlockInCriticalSectionChecker(CheckerManager &mgr) {
383 mgr.registerChecker<BlockInCriticalSectionChecker>();
384}
385
386bool ento::shouldRegisterBlockInCriticalSectionChecker(
387 const CheckerManager &mgr) {
388 return true;
389}
390