Endre =?utf-8?q?Fülöp?= <endre.fu...@sigmatechnology.com>, Endre =?utf-8?q?Fülöp?= <endre.fu...@sigmatechnology.com>, Endre =?utf-8?q?Fülöp?= <endre.fu...@sigmatechnology.com>, Endre =?utf-8?q?Fülöp?= <endre.fu...@sigmatechnology.com> Message-ID: In-Reply-To: <llvm.org/llvm/llvm-project/pull/109...@github.com>
llvmbot wrote: <!--LLVM PR SUMMARY COMMENT--> @llvm/pr-subscribers-clang-static-analyzer-1 @llvm/pr-subscribers-clang Author: Endre Fülöp (gamesh411) <details> <summary>Changes</summary> This patch's primary driving force is reducing code duplication in BlockInCriticalSectionChecker and PthreadLockChecker. This is mainly NFC. The user-facing API is the same, but at least one false positive has been fixed, and the internal state representation has changed. --- Patch is 115.54 KiB, truncated to 20.00 KiB below, full version: https://github.com/llvm/llvm-project/pull/109636.diff 14 Files Affected: - (modified) clang/include/clang/StaticAnalyzer/Checkers/Checkers.td (+8-1) - (modified) clang/lib/StaticAnalyzer/Checkers/BlockInCriticalSectionChecker.cpp (+55-318) - (modified) clang/lib/StaticAnalyzer/Checkers/CMakeLists.txt (+1) - (added) clang/lib/StaticAnalyzer/Checkers/MutexModeling.cpp (+773) - (added) clang/lib/StaticAnalyzer/Checkers/MutexModeling/MutexModelingAPI.h (+244) - (added) clang/lib/StaticAnalyzer/Checkers/MutexModeling/MutexModelingDomain.h (+126) - (added) clang/lib/StaticAnalyzer/Checkers/MutexModeling/MutexModelingGDM.h (+169) - (added) clang/lib/StaticAnalyzer/Checkers/MutexModeling/MutexRegionExtractor.h (+139) - (modified) clang/lib/StaticAnalyzer/Checkers/PthreadLockChecker.cpp (+148-609) - (modified) clang/test/Analysis/analyzer-enabled-checkers.c (+1) - (modified) clang/test/Analysis/block-in-critical-section.cpp (+8-13) - (modified) clang/test/Analysis/pthreadlock_state.c (+48-5) - (modified) clang/test/Analysis/pthreadlock_state_nottracked.c (+5) - (modified) clang/test/Analysis/std-c-library-functions-arg-enabled-checkers.c (+1) ``````````diff diff --git a/clang/include/clang/StaticAnalyzer/Checkers/Checkers.td b/clang/include/clang/StaticAnalyzer/Checkers/Checkers.td index 349040c15eeb83..b41580dcfba575 100644 --- a/clang/include/clang/StaticAnalyzer/Checkers/Checkers.td +++ b/clang/include/clang/StaticAnalyzer/Checkers/Checkers.td @@ -219,6 +219,11 @@ def DereferenceChecker : Checker<"NullDereference">, ]>, Documentation<HasDocumentation>; +def MutexModeling : Checker<"MutexModeling">, + HelpText<"Model mutexes lock and unlock events">, + Documentation<NotDocumented>, + Hidden; + def NonNullParamChecker : Checker<"NonNullParamChecker">, HelpText<"Check for null pointers passed as arguments to a function whose " "arguments are references or marked with the 'nonnull' attribute">, @@ -307,6 +312,7 @@ def StackAddrAsyncEscapeChecker : Checker<"StackAddressAsyncEscape">, def PthreadLockBase : Checker<"PthreadLockBase">, HelpText<"Helper registering multiple checks.">, + Dependencies<[MutexModeling]>, Documentation<NotDocumented>, Hidden; @@ -505,6 +511,7 @@ def UnixAPIMisuseChecker : Checker<"API">, def BlockInCriticalSectionChecker : Checker<"BlockInCriticalSection">, HelpText<"Check for calls to blocking functions inside a critical section">, + Dependencies<[MutexModeling]>, Documentation<HasDocumentation>; def DynamicMemoryModeling: Checker<"DynamicMemoryModeling">, @@ -610,7 +617,7 @@ def ChrootChecker : Checker<"Chroot">, def PthreadLockChecker : Checker<"PthreadLock">, HelpText<"Simple lock -> unlock checker">, - Dependencies<[PthreadLockBase]>, + Dependencies<[PthreadLockBase, MutexModeling]>, Documentation<HasDocumentation>; def SimpleStreamChecker : Checker<"SimpleStream">, diff --git a/clang/lib/StaticAnalyzer/Checkers/BlockInCriticalSectionChecker.cpp b/clang/lib/StaticAnalyzer/Checkers/BlockInCriticalSectionChecker.cpp index 7460781799d08a..e5be2dfc19ff42 100644 --- a/clang/lib/StaticAnalyzer/Checkers/BlockInCriticalSectionChecker.cpp +++ b/clang/lib/StaticAnalyzer/Checkers/BlockInCriticalSectionChecker.cpp @@ -14,165 +14,24 @@ // //===----------------------------------------------------------------------===// +#include "MutexModeling/MutexModelingAPI.h" + #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/SmallString.h" -#include "llvm/ADT/StringExtras.h" -#include <iterator> #include <utility> -#include <variant> using namespace clang; using namespace ento; +using namespace mutex_modeling; 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); - } -}; - -class CallDescriptionBasedMatcher { - CallDescription LockFn; - CallDescription UnlockFn; - -public: - CallDescriptionBasedMatcher(CallDescription &&LockFn, - CallDescription &&UnlockFn) - : LockFn(std::move(LockFn)), UnlockFn(std::move(UnlockFn)) {} - [[nodiscard]] bool matches(const CallEvent &Call, bool IsLock) const { - if (IsLock) { - return LockFn.matches(Call); - } - return UnlockFn.matches(Call); - } -}; - -class FirstArgMutexDescriptor : public CallDescriptionBasedMatcher { -public: - FirstArgMutexDescriptor(CallDescription &&LockFn, CallDescription &&UnlockFn) - : CallDescriptionBasedMatcher(std::move(LockFn), std::move(UnlockFn)) {} - - [[nodiscard]] const MemRegion *getRegion(const CallEvent &Call, bool) const { - return Call.getArgSVal(0).getAsRegion(); - } -}; - -class MemberMutexDescriptor : public CallDescriptionBasedMatcher { -public: - MemberMutexDescriptor(CallDescription &&LockFn, CallDescription &&UnlockFn) - : CallDescriptionBasedMatcher(std::move(LockFn), std::move(UnlockFn)) {} - - [[nodiscard]] const MemRegion *getRegion(const CallEvent &Call, bool) const { - return cast<CXXMemberCall>(Call).getCXXThisVal().getAsRegion(); - } -}; - -class RAIIMutexDescriptor { - mutable const IdentifierInfo *Guard{}; - mutable bool IdentifierInfoInitialized{}; - mutable llvm::SmallString<32> GuardName{}; - - void initIdentifierInfo(const CallEvent &Call) const { - if (!IdentifierInfoInitialized) { - // In case of checking C code, or when the corresponding headers are not - // included, we might end up query the identifier table every time when - // this function is called instead of early returning it. To avoid this, a - // bool variable (IdentifierInfoInitialized) is used and the function will - // be run only once. - const auto &ASTCtx = Call.getState()->getStateManager().getContext(); - Guard = &ASTCtx.Idents.get(GuardName); - } - } - - template <typename T> bool matchesImpl(const CallEvent &Call) const { - const T *C = dyn_cast<T>(&Call); - if (!C) - return false; - const IdentifierInfo *II = - cast<CXXRecordDecl>(C->getDecl()->getParent())->getIdentifier(); - return II == Guard; - } - -public: - RAIIMutexDescriptor(StringRef GuardName) : GuardName(GuardName) {} - [[nodiscard]] bool matches(const CallEvent &Call, bool IsLock) const { - initIdentifierInfo(Call); - if (IsLock) { - return matchesImpl<CXXConstructorCall>(Call); - } - return matchesImpl<CXXDestructorCall>(Call); - } - [[nodiscard]] const MemRegion *getRegion(const CallEvent &Call, - bool IsLock) const { - const MemRegion *LockRegion = nullptr; - if (IsLock) { - if (std::optional<SVal> Object = Call.getReturnValueUnderConstruction()) { - LockRegion = Object->getAsRegion(); - } - } else { - LockRegion = cast<CXXDestructorCall>(Call).getCXXThisVal().getAsRegion(); - } - return LockRegion; - } -}; - -using MutexDescriptor = - std::variant<FirstArgMutexDescriptor, MemberMutexDescriptor, - RAIIMutexDescriptor>; - class BlockInCriticalSectionChecker : public Checker<check::PostCall> { private: - const std::array<MutexDescriptor, 8> MutexDescriptors{ - // 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. - MemberMutexDescriptor( - {/*MatchAs=*/CDM::CXXMethod, - /*QualifiedName=*/{"std", /*"mutex",*/ "lock"}, - /*RequiredArgs=*/0}, - {CDM::CXXMethod, {"std", /*"mutex",*/ "unlock"}, 0}), - FirstArgMutexDescriptor({CDM::CLibrary, {"pthread_mutex_lock"}, 1}, - {CDM::CLibrary, {"pthread_mutex_unlock"}, 1}), - FirstArgMutexDescriptor({CDM::CLibrary, {"mtx_lock"}, 1}, - {CDM::CLibrary, {"mtx_unlock"}, 1}), - FirstArgMutexDescriptor({CDM::CLibrary, {"pthread_mutex_trylock"}, 1}, - {CDM::CLibrary, {"pthread_mutex_unlock"}, 1}), - FirstArgMutexDescriptor({CDM::CLibrary, {"mtx_trylock"}, 1}, - {CDM::CLibrary, {"mtx_unlock"}, 1}), - FirstArgMutexDescriptor({CDM::CLibrary, {"mtx_timedlock"}, 1}, - {CDM::CLibrary, {"mtx_unlock"}, 1}), - RAIIMutexDescriptor("lock_guard"), - RAIIMutexDescriptor("unique_lock")}; - const CallDescriptionSet BlockingFunctions{{CDM::CLibrary, {"sleep"}}, {CDM::CLibrary, {"getc"}}, {CDM::CLibrary, {"fgets"}}, @@ -182,147 +41,25 @@ class BlockInCriticalSectionChecker : public Checker<check::PostCall> { const BugType BlockInCritSectionBugType{ this, "Call to blocking function in critical section", "Blocking Error"}; - void reportBlockInCritSection(const CallEvent &call, CheckerContext &C) const; - - [[nodiscard]] const NoteTag *createCritSectionNote(CritSectionMarker M, - CheckerContext &C) const; - - [[nodiscard]] std::optional<MutexDescriptor> - checkDescriptorMatch(const CallEvent &Call, CheckerContext &C, - bool IsLock) const; - - void handleLock(const MutexDescriptor &Mutex, const CallEvent &Call, - CheckerContext &C) const; - - void handleUnlock(const MutexDescriptor &Mutex, const CallEvent &Call, - CheckerContext &C) const; - [[nodiscard]] bool isBlockingInCritSection(const CallEvent &Call, CheckerContext &C) const; + void reportBlockInCritSection(const CallEvent &call, CheckerContext &C) const; + public: - /// Process unlock. - /// Process lock. - /// Process blocking functions (sleep, getc, fgets, read, recv) + BlockInCriticalSectionChecker(); void checkPostCall(const CallEvent &Call, CheckerContext &C) const; }; } // end anonymous namespace -REGISTER_LIST_WITH_PROGRAMSTATE(ActiveCritSections, CritSectionMarker) - -// Iterator traits for ImmutableList data structure -// that enable the use of STL algorithms. -// TODO: Move these to llvm::ImmutableList when overhauling immutable data -// structures for proper iterator concept support. -template <> -struct std::iterator_traits< - typename llvm::ImmutableList<CritSectionMarker>::iterator> { - using iterator_category = std::forward_iterator_tag; - using value_type = CritSectionMarker; - using difference_type = std::ptrdiff_t; - using reference = CritSectionMarker &; - using pointer = CritSectionMarker *; -}; - -std::optional<MutexDescriptor> -BlockInCriticalSectionChecker::checkDescriptorMatch(const CallEvent &Call, - CheckerContext &C, - bool IsLock) const { - const auto Descriptor = - llvm::find_if(MutexDescriptors, [&Call, IsLock](auto &&Descriptor) { - return std::visit( - [&Call, IsLock](auto &&DescriptorImpl) { - return DescriptorImpl.matches(Call, IsLock); - }, - Descriptor); - }); - if (Descriptor != MutexDescriptors.end()) - return *Descriptor; - return std::nullopt; -} - -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 *getRegion(const CallEvent &Call, - const MutexDescriptor &Descriptor, - bool IsLock) { - return std::visit( - [&Call, IsLock](auto &Descr) -> const MemRegion * { - return skipStdBaseClassRegion(Descr.getRegion(Call, IsLock)); - }, - Descriptor); -} - -void BlockInCriticalSectionChecker::handleLock( - const MutexDescriptor &LockDescriptor, const CallEvent &Call, - CheckerContext &C) const { - const MemRegion *MutexRegion = - getRegion(Call, LockDescriptor, /*IsLock=*/true); - if (!MutexRegion) - return; - - const CritSectionMarker MarkToAdd{Call.getOriginExpr(), MutexRegion}; - ProgramStateRef StateWithLockEvent = - C.getState()->add<ActiveCritSections>(MarkToAdd); - C.addTransition(StateWithLockEvent, createCritSectionNote(MarkToAdd, C)); -} - -void BlockInCriticalSectionChecker::handleUnlock( - const MutexDescriptor &UnlockDescriptor, const CallEvent &Call, - CheckerContext &C) const { - const MemRegion *MutexRegion = - getRegion(Call, UnlockDescriptor, /*IsLock=*/false); - 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); +BlockInCriticalSectionChecker::BlockInCriticalSectionChecker() { + RegisterBugTypeForMutexModeling(&BlockInCritSectionBugType); } 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); - } else if (std::optional<MutexDescriptor> LockDesc = - checkDescriptorMatch(Call, C, /*IsLock=*/true)) { - handleLock(*LockDesc, Call, C); - } else if (std::optional<MutexDescriptor> UnlockDesc = - checkDescriptorMatch(Call, C, /*IsLock=*/false)) { - handleUnlock(*UnlockDesc, Call, C); - } + return BlockingFunctions.contains(Call) && AreAnyCritsectionsActive(C); } void BlockInCriticalSectionChecker::reportBlockInCritSection( @@ -342,56 +79,56 @@ void BlockInCriticalSectionChecker::reportBlockInCritSection( 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 BlockInCriticalSectionChecker::checkPostCall(const CallEvent &Call, + CheckerContext &C) const { + if (!isBlockingInCritSection(Call, C)) + return; + reportBlockInCritSection(Call, C); } +// Checker registration void ento::registerBlockInCriticalSectionChecker(CheckerManager &mgr) { mgr.registerChecker<BlockInCriticalSectionChecker>(); + + // Register events for std::mutex lock and unlock + // 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. + RegisterEvent(EventDescriptor{ + mutex_modeling::MakeMemberExtractor({"std", /*"mutex"*/ "lock"}), + EventKind::Acquire, LibraryKind::NotApplicable, + SemanticsKind::XNUSemantics}); + RegisterEvent(EventDescriptor{ + mutex_modeling::MakeMemberExtractor({"std", /*"mutex"*/ "unlock"}), + EventKind::Release}); + + // Register events for std::lock_guard + RegisterEvent(EventDescriptor{ + mutex_modeling::MakeRAIILockExtractor("lock_guard"), EventKind::Acquire, + LibraryKind::NotApplicable, SemanticsKind::XNUSemantics}); + RegisterEvent( + EventDescriptor{mutex_modeling::MakeRAIIReleaseExtractor("lock_guard"), + EventKind::Release}); + + // Register events for std::unique_lock + RegisterEvent(EventDescriptor{ + mutex_modeling::MakeRAIILockExtractor("unique_lock"), EventKind::Acquire, + LibraryKind::NotApplicable, SemanticsKind::XNUSemantics}); + RegisterEvent( + EventDescriptor{mutex_modeling::MakeRAIIReleaseExtractor("unique_lock"), + EventKind::Release}); + + // Register events for std::scoped_lock + RegisterEvent(EventDescriptor{ + mutex_modeling::MakeRAIILockExtractor("scoped_lock"), EventKind::Acquire, + LibraryKind::NotApplicable, SemanticsKind::XNUSemantics}); + RegisterEvent( + EventDescriptor{mutex_modeling::MakeRAIIReleaseExtractor("scoped_lock"), + EventKind::Release}); } bool ento::shouldRegisterBlockInCriticalSectionChecker( diff --git a/clang/lib/StaticAnalyzer/Checkers/CMakeLists.txt b/clang/lib/StaticAnalyzer/Checkers/CMakeLists.txt index 6da3665ab9a4df..c3987ba76529db 100644 --- a/clang/lib/StaticAnalyzer/Checkers/CMakeLists.txt +++ b/clang/lib/StaticAnalyzer/Checkers/CMakeLists.txt @@ -68,6 +68,7 @@ add_clang_library(clangStaticAnalyzerCheckers MmapWriteExecChecker.cpp MIGChecker.cpp MoveChecker.cpp + MutexModeling.cpp MPI-Checker/MPIBugReporter.cpp MPI-Checker/MPIChecker.cpp MPI-Checker/MPIFunctionClassifier.cpp diff --git a/clang/lib/StaticAnalyzer/Checkers/MutexModeling.cpp b/clang/lib/StaticAnalyzer/Checkers/MutexModeling.cpp new file mode 100644 index 00000000000000..f0e13c5c95e432 --- /dev/null +++ b/clang/lib/StaticAnalyzer/Checkers/MutexModeling.cpp @@ -0,0 +1,773 @@ +//===--- MutexModeling.cpp - Modeling of mutexes --------------------------===// +// +// 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 modeling checker for tracking mutex states. +// +//===----------------------------------------------------------------------===// + +#include "MutexModeling/MutexM... [truncated] `````````` </details> https://github.com/llvm/llvm-project/pull/109636 _______________________________________________ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
