xref: /llvm-project/clang/lib/StaticAnalyzer/Checkers/BlockInCriticalSectionChecker.cpp (revision 82e314e3664d2c8768212e74f751187d51950b87) 
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 
35 using namespace clang;
36 using namespace ento;
37 
38 namespace {
39 
40 struct CritSectionMarker {
41   const Expr *LockExpr{};
42   const MemRegion *LockReg{};
43 
44   void Profile(llvm::FoldingSetNodeID &ID) const {
45     ID.Add(LockExpr);
46     ID.Add(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 
59 class CallDescriptionBasedMatcher {
60   CallDescription LockFn;
61   CallDescription UnlockFn;
62 
63 public:
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 
75 class FirstArgMutexDescriptor : public CallDescriptionBasedMatcher {
76 public:
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(0).getAsRegion();
82   }
83 };
84 
85 class MemberMutexDescriptor : public CallDescriptionBasedMatcher {
86 public:
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>(Call).getCXXThisVal().getAsRegion();
92   }
93 };
94 
95 class 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(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 
121 public:
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>(Call).getCXXThisVal().getAsRegion();
139     }
140     return LockRegion;
141   }
142 };
143 
144 using MutexDescriptor =
145     std::variant<FirstArgMutexDescriptor, MemberMutexDescriptor,
146                  RAIIMutexDescriptor>;
147 
148 class BlockInCriticalSectionChecker : public Checker<check::PostCall> {
149 private:
150   const std::array<MutexDescriptor, 8> MutexDescriptors{
151       // NOTE: There are standard library implementations where some methods
152       // of `std::mutex` are inherited from an implementation detail base
153       // class, and those aren't matched by the name specification {"std",
154       // "mutex", "lock"}.
155       // As a workaround here we omit the class name and only require the
156       // presence of the name parts "std" and "lock"/"unlock".
157       // TODO: Ensure that CallDescription understands inherited methods.
158       MemberMutexDescriptor(
159           {/*MatchAs=*/CDM::CXXMethod,
160            /*QualifiedName=*/{"std", /*"mutex",*/ "lock"},
161            /*RequiredArgs=*/0},
162           {CDM::CXXMethod, {"std", /*"mutex",*/ "unlock"}, 0}),
163       FirstArgMutexDescriptor({CDM::CLibrary, {"pthread_mutex_lock"}, 1},
164                               {CDM::CLibrary, {"pthread_mutex_unlock"}, 1}),
165       FirstArgMutexDescriptor({CDM::CLibrary, {"mtx_lock"}, 1},
166                               {CDM::CLibrary, {"mtx_unlock"}, 1}),
167       FirstArgMutexDescriptor({CDM::CLibrary, {"pthread_mutex_trylock"}, 1},
168                               {CDM::CLibrary, {"pthread_mutex_unlock"}, 1}),
169       FirstArgMutexDescriptor({CDM::CLibrary, {"mtx_trylock"}, 1},
170                               {CDM::CLibrary, {"mtx_unlock"}, 1}),
171       FirstArgMutexDescriptor({CDM::CLibrary, {"mtx_timedlock"}, 1},
172                               {CDM::CLibrary, {"mtx_unlock"}, 1}),
173       RAIIMutexDescriptor("lock_guard"),
174       RAIIMutexDescriptor("unique_lock")};
175 
176   const CallDescriptionSet BlockingFunctions{{CDM::CLibrary, {"sleep"}},
177                                              {CDM::CLibrary, {"getc"}},
178                                              {CDM::CLibrary, {"fgets"}},
179                                              {CDM::CLibrary, {"read"}},
180                                              {CDM::CLibrary, {"recv"}}};
181 
182   const BugType BlockInCritSectionBugType{
183       this, "Call to blocking function in critical section", "Blocking Error"};
184 
185   void reportBlockInCritSection(const CallEvent &call, CheckerContext &C) const;
186 
187   [[nodiscard]] const NoteTag *createCritSectionNote(CritSectionMarker M,
188                                                      CheckerContext &C) const;
189 
190   [[nodiscard]] std::optional<MutexDescriptor>
191   checkDescriptorMatch(const CallEvent &Call, CheckerContext &C,
192                        bool IsLock) const;
193 
194   void handleLock(const MutexDescriptor &Mutex, const CallEvent &Call,
195                   CheckerContext &C) const;
196 
197   void handleUnlock(const MutexDescriptor &Mutex, const CallEvent &Call,
198                     CheckerContext &C) const;
199 
200   [[nodiscard]] bool isBlockingInCritSection(const CallEvent &Call,
201                                              CheckerContext &C) const;
202 
203 public:
204   /// Process unlock.
205   /// Process lock.
206   /// Process blocking functions (sleep, getc, fgets, read, recv)
207   void checkPostCall(const CallEvent &Call, CheckerContext &C) const;
208 };
209 
210 } // end anonymous namespace
211 
212 REGISTER_LIST_WITH_PROGRAMSTATE(ActiveCritSections, CritSectionMarker)
213 
214 // Iterator traits for ImmutableList data structure
215 // that enable the use of STL algorithms.
216 // TODO: Move these to llvm::ImmutableList when overhauling immutable data
217 // structures for proper iterator concept support.
218 template <>
219 struct std::iterator_traits<
220     typename llvm::ImmutableList<CritSectionMarker>::iterator> {
221   using iterator_category = std::forward_iterator_tag;
222   using value_type = CritSectionMarker;
223   using difference_type = std::ptrdiff_t;
224   using reference = CritSectionMarker &;
225   using pointer = CritSectionMarker *;
226 };
227 
228 std::optional<MutexDescriptor>
229 BlockInCriticalSectionChecker::checkDescriptorMatch(const CallEvent &Call,
230                                                     CheckerContext &C,
231                                                     bool IsLock) const {
232   const auto Descriptor =
233       llvm::find_if(MutexDescriptors, [&Call, IsLock](auto &&Descriptor) {
234         return std::visit(
235             [&Call, IsLock](auto &&DescriptorImpl) {
236               return DescriptorImpl.matches(Call, IsLock);
237             },
238             Descriptor);
239       });
240   if (Descriptor != MutexDescriptors.end())
241     return *Descriptor;
242   return std::nullopt;
243 }
244 
245 static const MemRegion *skipStdBaseClassRegion(const MemRegion *Reg) {
246   while (Reg) {
247     const auto *BaseClassRegion = dyn_cast<CXXBaseObjectRegion>(Reg);
248     if (!BaseClassRegion || !isWithinStdNamespace(BaseClassRegion->getDecl()))
249       break;
250     Reg = BaseClassRegion->getSuperRegion();
251   }
252   return Reg;
253 }
254 
255 static const MemRegion *getRegion(const CallEvent &Call,
256                                   const MutexDescriptor &Descriptor,
257                                   bool IsLock) {
258   return std::visit(
259       [&Call, IsLock](auto &Descr) -> const MemRegion * {
260         return skipStdBaseClassRegion(Descr.getRegion(Call, IsLock));
261       },
262       Descriptor);
263 }
264 
265 void BlockInCriticalSectionChecker::handleLock(
266     const MutexDescriptor &LockDescriptor, const CallEvent &Call,
267     CheckerContext &C) const {
268   const MemRegion *MutexRegion =
269       getRegion(Call, LockDescriptor, /*IsLock=*/true);
270   if (!MutexRegion)
271     return;
272 
273   const CritSectionMarker MarkToAdd{Call.getOriginExpr(), MutexRegion};
274   ProgramStateRef StateWithLockEvent =
275       C.getState()->add<ActiveCritSections>(MarkToAdd);
276   C.addTransition(StateWithLockEvent, createCritSectionNote(MarkToAdd, C));
277 }
278 
279 void BlockInCriticalSectionChecker::handleUnlock(
280     const MutexDescriptor &UnlockDescriptor, const CallEvent &Call,
281     CheckerContext &C) const {
282   const MemRegion *MutexRegion =
283       getRegion(Call, UnlockDescriptor, /*IsLock=*/false);
284   if (!MutexRegion)
285     return;
286 
287   ProgramStateRef State = C.getState();
288   const auto ActiveSections = State->get<ActiveCritSections>();
289   const auto MostRecentLock =
290       llvm::find_if(ActiveSections, [MutexRegion](auto &&Marker) {
291         return Marker.LockReg == MutexRegion;
292       });
293   if (MostRecentLock == ActiveSections.end())
294     return;
295 
296   // Build a new ImmutableList without this element.
297   auto &Factory = State->get_context<ActiveCritSections>();
298   llvm::ImmutableList<CritSectionMarker> NewList = Factory.getEmptyList();
299   for (auto It = ActiveSections.begin(), End = ActiveSections.end(); It != End;
300        ++It) {
301     if (It != MostRecentLock)
302       NewList = Factory.add(*It, NewList);
303   }
304 
305   State = State->set<ActiveCritSections>(NewList);
306   C.addTransition(State);
307 }
308 
309 bool BlockInCriticalSectionChecker::isBlockingInCritSection(
310     const CallEvent &Call, CheckerContext &C) const {
311   return BlockingFunctions.contains(Call) &&
312          !C.getState()->get<ActiveCritSections>().isEmpty();
313 }
314 
315 void BlockInCriticalSectionChecker::checkPostCall(const CallEvent &Call,
316                                                   CheckerContext &C) const {
317   if (isBlockingInCritSection(Call, C)) {
318     reportBlockInCritSection(Call, C);
319   } else if (std::optional<MutexDescriptor> LockDesc =
320                  checkDescriptorMatch(Call, C, /*IsLock=*/true)) {
321     handleLock(*LockDesc, Call, C);
322   } else if (std::optional<MutexDescriptor> UnlockDesc =
323                  checkDescriptorMatch(Call, C, /*IsLock=*/false)) {
324     handleUnlock(*UnlockDesc, Call, C);
325   }
326 }
327 
328 void BlockInCriticalSectionChecker::reportBlockInCritSection(
329     const CallEvent &Call, CheckerContext &C) const {
330   ExplodedNode *ErrNode = C.generateNonFatalErrorNode(C.getState());
331   if (!ErrNode)
332     return;
333 
334   std::string msg;
335   llvm::raw_string_ostream os(msg);
336   os << "Call to blocking function '" << Call.getCalleeIdentifier()->getName()
337      << "' inside of critical section";
338   auto R = std::make_unique<PathSensitiveBugReport>(BlockInCritSectionBugType,
339                                                     os.str(), ErrNode);
340   R->addRange(Call.getSourceRange());
341   R->markInteresting(Call.getReturnValue());
342   C.emitReport(std::move(R));
343 }
344 
345 const NoteTag *
346 BlockInCriticalSectionChecker::createCritSectionNote(CritSectionMarker M,
347                                                      CheckerContext &C) const {
348   const BugType *BT = &this->BlockInCritSectionBugType;
349   return C.getNoteTag([M, BT](PathSensitiveBugReport &BR,
350                               llvm::raw_ostream &OS) {
351     if (&BR.getBugType() != BT)
352       return;
353 
354     // Get the lock events for the mutex of the current line's lock event.
355     const auto CritSectionBegins =
356         BR.getErrorNode()->getState()->get<ActiveCritSections>();
357     llvm::SmallVector<CritSectionMarker, 4> LocksForMutex;
358     llvm::copy_if(
359         CritSectionBegins, std::back_inserter(LocksForMutex),
360         [M](const auto &Marker) { return Marker.LockReg == M.LockReg; });
361     if (LocksForMutex.empty())
362       return;
363 
364     // As the ImmutableList builds the locks by prepending them, we
365     // reverse the list to get the correct order.
366     std::reverse(LocksForMutex.begin(), LocksForMutex.end());
367 
368     // Find the index of the lock expression in the list of all locks for a
369     // given mutex (in acquisition order).
370     const auto Position =
371         llvm::find_if(std::as_const(LocksForMutex), [M](const auto &Marker) {
372           return Marker.LockExpr == M.LockExpr;
373         });
374     if (Position == LocksForMutex.end())
375       return;
376 
377     // If there is only one lock event, we don't need to specify how many times
378     // the critical section was entered.
379     if (LocksForMutex.size() == 1) {
380       OS << "Entering critical section here";
381       return;
382     }
383 
384     const auto IndexOfLock =
385         std::distance(std::as_const(LocksForMutex).begin(), Position);
386 
387     const auto OrdinalOfLock = IndexOfLock + 1;
388     OS << "Entering critical section for the " << OrdinalOfLock
389        << llvm::getOrdinalSuffix(OrdinalOfLock) << " time here";
390   });
391 }
392 
393 void ento::registerBlockInCriticalSectionChecker(CheckerManager &mgr) {
394   mgr.registerChecker<BlockInCriticalSectionChecker>();
395 }
396 
397 bool ento::shouldRegisterBlockInCriticalSectionChecker(
398     const CheckerManager &mgr) {
399   return true;
400 }
401