clang 19.0.0git
BlockInCriticalSectionChecker.cpp
Go to the documentation of this file.
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
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(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
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(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>(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(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>(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 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
194public:
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
203REGISTER_LIST_WITH_PROGRAMSTATE(ActiveCritSections, CritSectionMarker)
204
205namespace 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.
210template <>
211struct 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
221std::optional<MutexDescriptor>
222BlockInCriticalSectionChecker::checkDescriptorMatch(const CallEvent &Call,
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
238static 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
248void 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
262void 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
292bool BlockInCriticalSectionChecker::isBlockingInCritSection(
293 const CallEvent &Call, CheckerContext &C) const {
294 return BlockingFunctions.contains(Call) &&
295 !C.getState()->get<ActiveCritSections>().isEmpty();
296}
297
298void 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
311void 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
328const NoteTag *
329BlockInCriticalSectionChecker::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>();
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
376void ento::registerBlockInCriticalSectionChecker(CheckerManager &mgr) {
377 mgr.registerChecker<BlockInCriticalSectionChecker>();
378}
379
380bool ento::shouldRegisterBlockInCriticalSectionChecker(
381 const CheckerManager &mgr) {
382 return true;
383}
static const MemRegion * getRegion(const CallEvent &Call, const MutexDescriptor &Descriptor, bool IsLock)
#define REGISTER_LIST_WITH_PROGRAMSTATE(Name, Elem)
Declares an immutable list type NameTy, suitable for placement into the ProgramState.
This represents one expression.
Definition: Expr.h:110
One of these records is kept for each identifier that is lexed.
const BugType & getBugType() const
Definition: BugReporter.h:149
An immutable set of CallDescriptions.
A CallDescription is a pattern that can be used to match calls based on the qualified name and the ar...
bool matches(const CallEvent &Call) const
Returns true if the CallEvent is a call to a function that matches the CallDescription.
Represents an abstract call to a function or method along a particular path.
Definition: CallEvent.h:153
CHECKER * registerChecker(AT &&... Args)
Used to register checkers.
const ProgramStateRef & getState() const
MemRegion - The root abstract class for all memory regions.
Definition: MemRegion.h:96
The tag upon which the TagVisitor reacts.
Definition: BugReporter.h:779
const ExplodedNode * getErrorNode() const
Definition: BugReporter.h:402
bool matches(const til::SExpr *E1, const til::SExpr *E2)
The JSON file list parser is used to communicate input to InstallAPI.
if(T->getSizeExpr()) TRY_TO(TraverseStmt(const_cast< Expr * >(T -> getSizeExpr())))
bool operator==(const CallGraphNode::CallRecord &LHS, const CallGraphNode::CallRecord &RHS)
Definition: CallGraph.h:207
bool operator!=(CanQual< T > x, CanQual< U > y)
const FunctionProtoType * T
@ Other
Other implicit parameter.
Diagnostic wrappers for TextAPI types for error reporting.
Definition: Dominators.h:30
Definition: Format.h:5428