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
34 using namespace clang;
35 using namespace ento;
36
37 namespace {
38
39 struct CritSectionMarker {
40 const Expr *LockExpr{};
41 const MemRegion *LockReg{};
42
Profile__anon83a18dc50111::CritSectionMarker43 void Profile(llvm::FoldingSetNodeID &ID) const {
44 ID.Add(LockExpr);
45 ID.Add(LockReg);
46 }
47
48 [[nodiscard]] constexpr bool
operator ==__anon83a18dc50111::CritSectionMarker49 operator==(const CritSectionMarker &Other) const noexcept {
50 return LockExpr == Other.LockExpr && LockReg == Other.LockReg;
51 }
52 [[nodiscard]] constexpr bool
operator !=__anon83a18dc50111::CritSectionMarker53 operator!=(const CritSectionMarker &Other) const noexcept {
54 return !(*this == Other);
55 }
56 };
57
58 class CallDescriptionBasedMatcher {
59 CallDescription LockFn;
60 CallDescription UnlockFn;
61
62 public:
CallDescriptionBasedMatcher(CallDescription && LockFn,CallDescription && UnlockFn)63 CallDescriptionBasedMatcher(CallDescription &&LockFn,
64 CallDescription &&UnlockFn)
65 : LockFn(std::move(LockFn)), UnlockFn(std::move(UnlockFn)) {}
matches(const CallEvent & Call,bool IsLock) const66 [[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
74 class FirstArgMutexDescriptor : public CallDescriptionBasedMatcher {
75 public:
FirstArgMutexDescriptor(CallDescription && LockFn,CallDescription && UnlockFn)76 FirstArgMutexDescriptor(CallDescription &&LockFn, CallDescription &&UnlockFn)
77 : CallDescriptionBasedMatcher(std::move(LockFn), std::move(UnlockFn)) {}
78
getRegion(const CallEvent & Call,bool) const79 [[nodiscard]] const MemRegion *getRegion(const CallEvent &Call, bool) const {
80 return Call.getArgSVal(0).getAsRegion();
81 }
82 };
83
84 class MemberMutexDescriptor : public CallDescriptionBasedMatcher {
85 public:
MemberMutexDescriptor(CallDescription && LockFn,CallDescription && UnlockFn)86 MemberMutexDescriptor(CallDescription &&LockFn, CallDescription &&UnlockFn)
87 : CallDescriptionBasedMatcher(std::move(LockFn), std::move(UnlockFn)) {}
88
getRegion(const CallEvent & Call,bool) const89 [[nodiscard]] const MemRegion *getRegion(const CallEvent &Call, bool) const {
90 return cast<CXXMemberCall>(Call).getCXXThisVal().getAsRegion();
91 }
92 };
93
94 class RAIIMutexDescriptor {
95 mutable const IdentifierInfo *Guard{};
96 mutable bool IdentifierInfoInitialized{};
97 mutable llvm::SmallString<32> GuardName{};
98
initIdentifierInfo(const CallEvent & Call) const99 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
matchesImpl(const CallEvent & Call) const111 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
120 public:
RAIIMutexDescriptor(StringRef GuardName)121 RAIIMutexDescriptor(StringRef GuardName) : GuardName(GuardName) {}
matches(const CallEvent & Call,bool IsLock) const122 [[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 }
getRegion(const CallEvent & Call,bool IsLock) const129 [[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
143 using MutexDescriptor =
144 std::variant<FirstArgMutexDescriptor, MemberMutexDescriptor,
145 RAIIMutexDescriptor>;
146
147 class BlockInCriticalSectionChecker : public Checker<check::PostCall> {
148 private:
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
202 public:
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
211 REGISTER_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.
217 template <>
218 struct 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
227 std::optional<MutexDescriptor>
checkDescriptorMatch(const CallEvent & Call,CheckerContext & C,bool IsLock) const228 BlockInCriticalSectionChecker::checkDescriptorMatch(const CallEvent &Call,
229 CheckerContext &C,
230 bool IsLock) const {
231 const auto Descriptor =
232 llvm::find_if(MutexDescriptors, [&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
getRegion(const CallEvent & Call,const MutexDescriptor & Descriptor,bool IsLock)244 static const MemRegion *getRegion(const CallEvent &Call,
245 const MutexDescriptor &Descriptor,
246 bool IsLock) {
247 return std::visit(
248 [&Call, IsLock](auto &&Descriptor) {
249 return Descriptor.getRegion(Call, IsLock);
250 },
251 Descriptor);
252 }
253
handleLock(const MutexDescriptor & LockDescriptor,const CallEvent & Call,CheckerContext & C) const254 void BlockInCriticalSectionChecker::handleLock(
255 const MutexDescriptor &LockDescriptor, const CallEvent &Call,
256 CheckerContext &C) const {
257 const MemRegion *MutexRegion =
258 getRegion(Call, LockDescriptor, /*IsLock=*/true);
259 if (!MutexRegion)
260 return;
261
262 const CritSectionMarker MarkToAdd{Call.getOriginExpr(), MutexRegion};
263 ProgramStateRef StateWithLockEvent =
264 C.getState()->add<ActiveCritSections>(MarkToAdd);
265 C.addTransition(StateWithLockEvent, createCritSectionNote(MarkToAdd, C));
266 }
267
handleUnlock(const MutexDescriptor & UnlockDescriptor,const CallEvent & Call,CheckerContext & C) const268 void BlockInCriticalSectionChecker::handleUnlock(
269 const MutexDescriptor &UnlockDescriptor, const CallEvent &Call,
270 CheckerContext &C) const {
271 const MemRegion *MutexRegion =
272 getRegion(Call, 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(ActiveSections, [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(*It, NewList);
292 }
293
294 State = State->set<ActiveCritSections>(NewList);
295 C.addTransition(State);
296 }
297
isBlockingInCritSection(const CallEvent & Call,CheckerContext & C) const298 bool BlockInCriticalSectionChecker::isBlockingInCritSection(
299 const CallEvent &Call, CheckerContext &C) const {
300 return BlockingFunctions.contains(Call) &&
301 !C.getState()->get<ActiveCritSections>().isEmpty();
302 }
303
checkPostCall(const CallEvent & Call,CheckerContext & C) const304 void BlockInCriticalSectionChecker::checkPostCall(const CallEvent &Call,
305 CheckerContext &C) const {
306 if (isBlockingInCritSection(Call, C)) {
307 reportBlockInCritSection(Call, C);
308 } else if (std::optional<MutexDescriptor> LockDesc =
309 checkDescriptorMatch(Call, C, /*IsLock=*/true)) {
310 handleLock(*LockDesc, Call, C);
311 } else if (std::optional<MutexDescriptor> UnlockDesc =
312 checkDescriptorMatch(Call, C, /*IsLock=*/false)) {
313 handleUnlock(*UnlockDesc, Call, C);
314 }
315 }
316
reportBlockInCritSection(const CallEvent & Call,CheckerContext & C) const317 void BlockInCriticalSectionChecker::reportBlockInCritSection(
318 const CallEvent &Call, CheckerContext &C) const {
319 ExplodedNode *ErrNode = C.generateNonFatalErrorNode(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>(BlockInCritSectionBugType,
328 os.str(), ErrNode);
329 R->addRange(Call.getSourceRange());
330 R->markInteresting(Call.getReturnValue());
331 C.emitReport(std::move(R));
332 }
333
334 const NoteTag *
createCritSectionNote(CritSectionMarker M,CheckerContext & C) const335 BlockInCriticalSectionChecker::createCritSectionNote(CritSectionMarker M,
336 CheckerContext &C) const {
337 const BugType *BT = &this->BlockInCritSectionBugType;
338 return C.getNoteTag([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 CritSectionBegins, std::back_inserter(LocksForMutex),
349 [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(LocksForMutex.begin(), 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(std::as_const(LocksForMutex), [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(std::as_const(LocksForMutex).begin(), Position);
375
376 const auto OrdinalOfLock = IndexOfLock + 1;
377 OS << "Entering critical section for the " << OrdinalOfLock
378 << llvm::getOrdinalSuffix(OrdinalOfLock) << " time here";
379 });
380 }
381
registerBlockInCriticalSectionChecker(CheckerManager & mgr)382 void ento::registerBlockInCriticalSectionChecker(CheckerManager &mgr) {
383 mgr.registerChecker<BlockInCriticalSectionChecker>();
384 }
385
shouldRegisterBlockInCriticalSectionChecker(const CheckerManager & mgr)386 bool ento::shouldRegisterBlockInCriticalSectionChecker(
387 const CheckerManager &mgr) {
388 return true;
389 }
390