| //===-- BlockInCriticalSectionChecker.cpp -----------------------*- C++ -*-===// | |
| // | |
| // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. | |
| // See https://llvm.org/LICENSE.txt for license information. | |
| // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception | |
| // | |
| //===----------------------------------------------------------------------===// | |
| // | |
| // Defines a checker for blocks in critical sections. This checker should find | |
| // the calls to blocking functions (for example: sleep, getc, fgets, read, | |
| // recv etc.) inside a critical section. When sleep(x) is called while a mutex | |
| // is held, other threades cannot lock the same mutex. This might take some | |
| // time, leading to bad performance or even deadlock. | |
| // | |
| //===----------------------------------------------------------------------===// | |
| #include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h" | |
| #include "clang/StaticAnalyzer/Core/BugReporter/BugType.h" | |
| #include "clang/StaticAnalyzer/Core/Checker.h" | |
| #include "clang/StaticAnalyzer/Core/PathSensitive/CallDescription.h" | |
| #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h" | |
| #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h" | |
| #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerHelpers.h" | |
| #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h" | |
| #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState_Fwd.h" | |
| #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h" | |
| #include "llvm/ADT/STLExtras.h" | |
| #include "llvm/ADT/StringExtras.h" | |
| #include <iterator> | |
| #include <utility> | |
| using namespace clang; | |
| using namespace ento; | |
| static const MemRegion *getFirstArgRegion(const CallEvent &Call) { | |
| return Call.getArgSVal(0).getAsRegion(); | |
| } | |
| static const MemRegion *getCXXThisRegion(const CallEvent &Call) { | |
| return cast<CXXMemberCall>(Call).getCXXThisVal().getAsRegion(); | |
| } | |
| static const MemRegion *getObjectUnderConstruction(const CallEvent &Call) { | |
| if (std::optional<SVal> Object = Call.getReturnValueUnderConstruction()) | |
| return Object->getAsRegion(); | |
| return nullptr; | |
| } | |
| static const MemRegion *getCXXDestructorThisRegion(const CallEvent &Call) { | |
| // Match both implicit (CXXDestructorCall) and explicit p->~T() | |
| // (CXXMemberCall) destructions using the common CXXInstanceCall base. | |
| const auto *Instance = dyn_cast<CXXInstanceCall>(&Call); | |
| if (Instance && isa_and_nonnull<CXXDestructorDecl>(Instance->getDecl())) | |
| return Instance->getCXXThisVal().getAsRegion(); | |
| return nullptr; | |
| } | |
| static bool isNotDeferLockUniqueLock(const CallEvent &Call) { | |
| // Use the constructor's declared parameter type to identify the defer_lock_t | |
| // overload. | |
| ArrayRef<ParmVarDecl *> Params = Call.parameters(); | |
| if (Params.size() < 2) | |
| return true; | |
| QualType ParamType = Params[1]->getType().getNonReferenceType(); | |
| const auto *RD = ParamType->getAsRecordDecl(); | |
| return !(RD && RD->getName() == "defer_lock_t" && RD->isInStdNamespace()); | |
| } | |
| namespace { | |
| struct CritSectionMarker { | |
| const Expr *LockExpr{}; | |
| const MemRegion *LockReg{}; | |
| void Profile(llvm::FoldingSetNodeID &ID) const { | |
| ID.Add(LockExpr); | |
| ID.Add(LockReg); | |
| } | |
| [[nodiscard]] constexpr bool | |
| operator==(const CritSectionMarker &Other) const noexcept { | |
| return LockExpr == Other.LockExpr && LockReg == Other.LockReg; | |
| } | |
| [[nodiscard]] constexpr bool | |
| operator!=(const CritSectionMarker &Other) const noexcept { | |
| return !(*this == Other); | |
| } | |
| }; | |
| enum class RoleKind { | |
| Lock, | |
| Unlock, | |
| }; | |
| // llvm::function_ref does not reject stateful functors/capturing lambdas, so | |
| // function pointers are used to avoid future issues coming from those objects' | |
| // lifetimes (more specifically to prevent such configuration entries from | |
| // compiling, increasing robustness). | |
| using GetRegionFn = const MemRegion *(*)(const CallEvent &); | |
| using FilterFn = bool (*)(const CallEvent &); | |
| struct ThreadingCallDescription { | |
| RoleKind Role; | |
| GetRegionFn GetRegion = getFirstArgRegion; | |
| FilterFn Filter = [](const CallEvent &) { return true; }; | |
| }; | |
| class SuppressNonBlockingStreams : public BugReporterVisitor { | |
| private: | |
| const CallDescription OpenFunction{CDM::CLibrary, {"open"}, 2}; | |
| SymbolRef StreamSym; | |
| const int NonBlockMacroVal; | |
| bool Satisfied = false; | |
| public: | |
| SuppressNonBlockingStreams(SymbolRef StreamSym, int NonBlockMacroVal) | |
| : StreamSym(StreamSym), NonBlockMacroVal(NonBlockMacroVal) {} | |
| static void *getTag() { | |
| static bool Tag; | |
| return &Tag; | |
| } | |
| void Profile(llvm::FoldingSetNodeID &ID) const override { | |
| ID.AddPointer(getTag()); | |
| } | |
| PathDiagnosticPieceRef VisitNode(const ExplodedNode *N, | |
| BugReporterContext &BRC, | |
| PathSensitiveBugReport &BR) override { | |
| if (Satisfied) | |
| return nullptr; | |
| std::optional<StmtPoint> Point = N->getLocationAs<StmtPoint>(); | |
| if (!Point) | |
| return nullptr; | |
| const auto *CE = Point->getStmtAs<CallExpr>(); | |
| if (!CE || !OpenFunction.matchesAsWritten(*CE)) | |
| return nullptr; | |
| if (N->getSVal(CE).getAsSymbol() != StreamSym) | |
| return nullptr; | |
| Satisfied = true; | |
| // Check if open's second argument contains O_NONBLOCK | |
| const llvm::APSInt *FlagVal = N->getSVal(CE->getArg(1)).getAsInteger(); | |
| if (!FlagVal) | |
| return nullptr; | |
| if ((*FlagVal & NonBlockMacroVal) != 0) | |
| BR.markInvalid(getTag(), nullptr); | |
| return nullptr; | |
| } | |
| }; | |
| class BlockInCriticalSectionChecker | |
| : public Checker<check::PostCall, eval::Call> { | |
| private: | |
| const CallDescriptionMap<ThreadingCallDescription> ThreadingCalls{ | |
| // NOTE: There are standard library implementations where some methods | |
| // of `std::mutex` are inherited from an implementation detail base | |
| // class, and those aren't matched by the name specification {"std", | |
| // "mutex", "lock"}. | |
| // As a workaround here we omit the class name and only require the | |
| // presence of the name parts "std" and "lock"/"unlock". | |
| // TODO: Ensure that CallDescription understands inherited methods. | |
| {{CDM::CXXMethod, {"std", /*"mutex",*/ "lock"}, 0}, | |
| {RoleKind::Lock, getCXXThisRegion}}, | |
| {{CDM::CXXMethod, {"std", /*"mutex",*/ "unlock"}, 0}, | |
| {RoleKind::Unlock, getCXXThisRegion}}, | |
| {{CDM::CLibrary, {"pthread_mutex_lock"}, 1}, {RoleKind::Lock}}, | |
| {{CDM::CLibrary, {"pthread_mutex_unlock"}, 1}, {RoleKind::Unlock}}, | |
| {{CDM::CLibrary, {"mtx_lock"}, 1}, {RoleKind::Lock}}, | |
| {{CDM::CLibrary, {"mtx_unlock"}, 1}, {RoleKind::Unlock}}, | |
| {{CDM::CLibrary, {"pthread_mutex_trylock"}, 1}, {RoleKind::Lock}}, | |
| {{CDM::CLibrary, {"mtx_trylock"}, 1}, {RoleKind::Lock}}, | |
| {{CDM::CLibrary, {"mtx_timedlock"}, 1}, {RoleKind::Lock}}, | |
| {{CDM::CXXMethod, {"lock_guard", "lock_guard"}}, | |
| {RoleKind::Lock, getObjectUnderConstruction}}, | |
| {{CDM::CXXMethod, {"lock_guard", "~lock_guard"}}, | |
| {RoleKind::Unlock, getCXXDestructorThisRegion}}, | |
| {{CDM::CXXMethod, {"unique_lock", "unique_lock"}}, | |
| {RoleKind::Lock, getObjectUnderConstruction, isNotDeferLockUniqueLock}}, | |
| {{CDM::CXXMethod, {"unique_lock", "~unique_lock"}}, | |
| {RoleKind::Unlock, getCXXDestructorThisRegion}}, | |
| {{CDM::CXXMethod, {"scoped_lock", "scoped_lock"}}, | |
| {RoleKind::Lock, getObjectUnderConstruction}}, | |
| {{CDM::CXXMethod, {"scoped_lock", "~scoped_lock"}}, | |
| {RoleKind::Unlock, getCXXDestructorThisRegion}}, | |
| }; | |
| const CallDescriptionSet BlockingFunctions{{CDM::CLibrary, {"sleep"}}, | |
| {CDM::CLibrary, {"getc"}}, | |
| {CDM::CLibrary, {"fgets"}}, | |
| {CDM::CLibrary, {"read"}}, | |
| {CDM::CLibrary, {"recv"}}}; | |
| const BugType BlockInCritSectionBugType{ | |
| this, "Call to blocking function in critical section", "Blocking Error"}; | |
| using O_NONBLOCKValueTy = std::optional<int>; | |
| mutable std::optional<O_NONBLOCKValueTy> O_NONBLOCKValue; | |
| void reportBlockInCritSection(const CallEvent &call, CheckerContext &C) const; | |
| [[nodiscard]] const NoteTag *createCritSectionNote(CritSectionMarker M, | |
| CheckerContext &C) const; | |
| [[nodiscard]] const ThreadingCallDescription * | |
| lookupThreadingCall(const CallEvent &Call) const; | |
| void handleLock(const ThreadingCallDescription &Desc, const CallEvent &Call, | |
| CheckerContext &C, ProgramStateRef State) const; | |
| void handleUnlock(const ThreadingCallDescription &Desc, const CallEvent &Call, | |
| CheckerContext &C) const; | |
| [[nodiscard]] bool isBlockingInCritSection(const CallEvent &Call, | |
| CheckerContext &C) const; | |
| public: | |
| /// Process unlock. | |
| /// Process lock. | |
| /// Process blocking functions (sleep, getc, fgets, read, recv) | |
| void checkPostCall(const CallEvent &Call, CheckerContext &C) const; | |
| // Process RAII lock guard constructors (to avoid double-counting by | |
| // inlining). | |
| bool evalCall(const CallEvent &Call, CheckerContext &C) const; | |
| }; | |
| } // end anonymous namespace | |
| REGISTER_LIST_WITH_PROGRAMSTATE(ActiveCritSections, CritSectionMarker) | |
| const ThreadingCallDescription * | |
| BlockInCriticalSectionChecker::lookupThreadingCall( | |
| const CallEvent &Call) const { | |
| const ThreadingCallDescription *Desc = ThreadingCalls.lookup(Call); | |
| if (!Desc) | |
| return nullptr; | |
| if (!Desc->Filter(Call)) | |
| return nullptr; | |
| return Desc; | |
| } | |
| static const MemRegion *skipStdBaseClassRegion(const MemRegion *Reg) { | |
| while (Reg) { | |
| const auto *BaseClassRegion = dyn_cast<CXXBaseObjectRegion>(Reg); | |
| if (!BaseClassRegion || !isWithinStdNamespace(BaseClassRegion->getDecl())) | |
| break; | |
| Reg = BaseClassRegion->getSuperRegion(); | |
| } | |
| return Reg; | |
| } | |
| static const MemRegion *getMutexRegion(const CallEvent &Call, | |
| const ThreadingCallDescription &Desc) { | |
| return skipStdBaseClassRegion(Desc.GetRegion(Call)); | |
| } | |
| void BlockInCriticalSectionChecker::handleLock( | |
| const ThreadingCallDescription &Desc, const CallEvent &Call, | |
| CheckerContext &C, ProgramStateRef State) const { | |
| const MemRegion *MutexRegion = getMutexRegion(Call, Desc); | |
| if (!MutexRegion) | |
| return; | |
| const CritSectionMarker MarkToAdd{Call.getOriginExpr(), MutexRegion}; | |
| ProgramStateRef StateWithLockEvent = | |
| State->add<ActiveCritSections>(MarkToAdd); | |
| C.addTransition(StateWithLockEvent, createCritSectionNote(MarkToAdd, C)); | |
| } | |
| void BlockInCriticalSectionChecker::handleUnlock( | |
| const ThreadingCallDescription &Desc, const CallEvent &Call, | |
| CheckerContext &C) const { | |
| const MemRegion *MutexRegion = getMutexRegion(Call, Desc); | |
| if (!MutexRegion) | |
| return; | |
| ProgramStateRef State = C.getState(); | |
| const auto ActiveSections = State->get<ActiveCritSections>(); | |
| const auto MostRecentLock = | |
| llvm::find_if(ActiveSections, [MutexRegion](auto &&Marker) { | |
| return Marker.LockReg == MutexRegion; | |
| }); | |
| if (MostRecentLock == ActiveSections.end()) | |
| return; | |
| // Build a new ImmutableList without this element. | |
| auto &Factory = State->get_context<ActiveCritSections>(); | |
| llvm::ImmutableList<CritSectionMarker> NewList = Factory.getEmptyList(); | |
| for (auto It = ActiveSections.begin(), End = ActiveSections.end(); It != End; | |
| ++It) { | |
| if (It != MostRecentLock) | |
| NewList = Factory.add(*It, NewList); | |
| } | |
| State = State->set<ActiveCritSections>(NewList); | |
| C.addTransition(State); | |
| } | |
| bool BlockInCriticalSectionChecker::isBlockingInCritSection( | |
| const CallEvent &Call, CheckerContext &C) const { | |
| return BlockingFunctions.contains(Call) && | |
| !C.getState()->get<ActiveCritSections>().isEmpty(); | |
| } | |
| void BlockInCriticalSectionChecker::checkPostCall(const CallEvent &Call, | |
| CheckerContext &C) const { | |
| if (isBlockingInCritSection(Call, C)) { | |
| reportBlockInCritSection(Call, C); | |
| return; | |
| } | |
| // Constructors are modeled in evalCall, so skip them before the lookup. | |
| if (isa<CXXConstructorCall>(Call)) | |
| return; | |
| const ThreadingCallDescription *Desc = lookupThreadingCall(Call); | |
| if (!Desc) | |
| return; | |
| switch (Desc->Role) { | |
| case RoleKind::Lock: | |
| handleLock(*Desc, Call, C, C.getState()); | |
| return; | |
| case RoleKind::Unlock: | |
| handleUnlock(*Desc, Call, C); | |
| return; | |
| } | |
| } | |
| bool BlockInCriticalSectionChecker::evalCall(const CallEvent &Call, | |
| CheckerContext &C) const { | |
| // Only RAII constructors are modeled here, so skip everything else before | |
| // the lookup. | |
| if (!isa<CXXConstructorCall>(Call)) | |
| return false; | |
| const ThreadingCallDescription *Desc = lookupThreadingCall(Call); | |
| if (!Desc) | |
| return false; | |
| // Every constructor entry in the configuration is a lock acquisition. | |
| // This seems to be reasonable, but if modeling requires to relax this | |
| // assumption, we can do so. | |
| assert(Desc->Role == RoleKind::Lock && | |
| "Constructor threading call must be a lock"); | |
| ProgramStateRef State = C.getState(); | |
| // Escape the object under construction to model the side-effects of the | |
| // constructor. | |
| if (const auto *Ctor = dyn_cast<AnyCXXConstructorCall>(&Call)) { | |
| const MemRegion *ObjRegion = Ctor->getCXXThisVal().getAsRegion(); | |
| State = State->invalidateRegions(ObjRegion, C.getCFGElementRef(), | |
| C.blockCount(), C.getStackFrame(), | |
| /*CausesPointerEscape=*/false); | |
| } | |
| handleLock(*Desc, Call, C, State); | |
| return true; | |
| } | |
| void BlockInCriticalSectionChecker::reportBlockInCritSection( | |
| const CallEvent &Call, CheckerContext &C) const { | |
| ExplodedNode *ErrNode = C.generateNonFatalErrorNode(C.getState()); | |
| if (!ErrNode) | |
| return; | |
| std::string msg; | |
| llvm::raw_string_ostream os(msg); | |
| os << "Call to blocking function '" << Call.getCalleeIdentifier()->getName() | |
| << "' inside of critical section"; | |
| auto R = std::make_unique<PathSensitiveBugReport>(BlockInCritSectionBugType, | |
| os.str(), ErrNode); | |
| // for 'read' and 'recv' call, check whether it's file descriptor(first | |
| // argument) is | |
| // created by 'open' API with O_NONBLOCK flag or is equal to -1, they will | |
| // not cause block in these situations, don't report | |
| StringRef FuncName = Call.getCalleeIdentifier()->getName(); | |
| if (FuncName == "read" || FuncName == "recv") { | |
| SVal SV = Call.getArgSVal(0); | |
| SValBuilder &SVB = C.getSValBuilder(); | |
| ProgramStateRef state = C.getState(); | |
| ConditionTruthVal CTV = | |
| state->areEqual(SV, SVB.makeIntVal(-1, C.getASTContext().IntTy)); | |
| if (CTV.isConstrainedTrue()) | |
| return; | |
| if (SymbolRef SR = SV.getAsSymbol()) { | |
| if (!O_NONBLOCKValue) | |
| O_NONBLOCKValue = tryExpandAsInteger( | |
| "O_NONBLOCK", C.getBugReporter().getPreprocessor()); | |
| if (*O_NONBLOCKValue) | |
| R->addVisitor<SuppressNonBlockingStreams>(SR, **O_NONBLOCKValue); | |
| } | |
| } | |
| R->addRange(Call.getSourceRange()); | |
| R->markInteresting(Call.getReturnValue()); | |
| C.emitReport(std::move(R)); | |
| } | |
| const NoteTag * | |
| BlockInCriticalSectionChecker::createCritSectionNote(CritSectionMarker M, | |
| CheckerContext &C) const { | |
| const BugType *BT = &this->BlockInCritSectionBugType; | |
| return C.getNoteTag([M, BT](PathSensitiveBugReport &BR, | |
| llvm::raw_ostream &OS) { | |
| if (&BR.getBugType() != BT) | |
| return; | |
| // Get the lock events for the mutex of the current line's lock event. | |
| const auto CritSectionBegins = | |
| BR.getErrorNode()->getState()->get<ActiveCritSections>(); | |
| llvm::SmallVector<CritSectionMarker, 4> LocksForMutex; | |
| llvm::copy_if( | |
| CritSectionBegins, std::back_inserter(LocksForMutex), | |
| [M](const auto &Marker) { return Marker.LockReg == M.LockReg; }); | |
| if (LocksForMutex.empty()) | |
| return; | |
| // As the ImmutableList builds the locks by prepending them, we | |
| // reverse the list to get the correct order. | |
| std::reverse(LocksForMutex.begin(), LocksForMutex.end()); | |
| // Find the index of the lock expression in the list of all locks for a | |
| // given mutex (in acquisition order). | |
| const auto Position = | |
| llvm::find_if(std::as_const(LocksForMutex), [M](const auto &Marker) { | |
| return Marker.LockExpr == M.LockExpr; | |
| }); | |
| if (Position == LocksForMutex.end()) | |
| return; | |
| // If there is only one lock event, we don't need to specify how many times | |
| // the critical section was entered. | |
| if (LocksForMutex.size() == 1) { | |
| OS << "Entering critical section here"; | |
| return; | |
| } | |
| const auto IndexOfLock = | |
| std::distance(std::as_const(LocksForMutex).begin(), Position); | |
| const auto OrdinalOfLock = IndexOfLock + 1; | |
| OS << "Entering critical section for the " << OrdinalOfLock | |
| << llvm::getOrdinalSuffix(OrdinalOfLock) << " time here"; | |
| }); | |
| } | |
| void ento::registerBlockInCriticalSectionChecker(CheckerManager &mgr) { | |
| mgr.registerChecker<BlockInCriticalSectionChecker>(); | |
| } | |
| bool ento::shouldRegisterBlockInCriticalSectionChecker( | |
| const CheckerManager &mgr) { | |
| return true; | |
| } |