From 4266522ab9a5c1c868e42b0d617a1136408cdec7 Mon Sep 17 00:00:00 2001 From: DeLesley Hutchins Date: Mon, 4 Aug 2014 16:10:59 +0000 Subject: [PATCH] Thread safety analysis: Add support for negative requirements, which are capability expressions of the form !expr, and denote a capability that must not be held. llvm-svn: 214725 --- .../include/clang/Analysis/Analyses/ThreadSafety.h | 4 +- .../clang/Analysis/Analyses/ThreadSafetyCommon.h | 102 ++++- clang/lib/Analysis/ThreadSafety.cpp | 500 ++++++++++----------- clang/lib/Analysis/ThreadSafetyCommon.cpp | 47 +- clang/test/SemaCXX/warn-thread-safety-analysis.cpp | 105 +++++ 5 files changed, 473 insertions(+), 285 deletions(-) diff --git a/clang/include/clang/Analysis/Analyses/ThreadSafety.h b/clang/include/clang/Analysis/Analyses/ThreadSafety.h index fadc8b0..bc22c4d 100644 --- a/clang/include/clang/Analysis/Analyses/ThreadSafety.h +++ b/clang/include/clang/Analysis/Analyses/ThreadSafety.h @@ -38,9 +38,9 @@ enum ProtectedOperationKind { /// example, it is an error to write a variable protected by shared version of a /// mutex. enum LockKind { - LK_Shared, ///< Shared/reader lock of a mutex. + LK_Shared, ///< Shared/reader lock of a mutex. LK_Exclusive, ///< Exclusive/writer lock of a mutex. - LK_Generic ///< Can be either Shared or Exclusive + LK_Generic ///< Can be either Shared or Exclusive }; /// This enum distinguishes between different ways to access (read or write) a diff --git a/clang/include/clang/Analysis/Analyses/ThreadSafetyCommon.h b/clang/include/clang/Analysis/Analyses/ThreadSafetyCommon.h index 9dd2547..06b106d 100644 --- a/clang/include/clang/Analysis/Analyses/ThreadSafetyCommon.h +++ b/clang/include/clang/Analysis/Analyses/ThreadSafetyCommon.h @@ -24,16 +24,59 @@ #include "clang/Analysis/Analyses/PostOrderCFGView.h" #include "clang/Analysis/Analyses/ThreadSafetyTIL.h" +#include "clang/Analysis/Analyses/ThreadSafetyTraverse.h" #include "clang/Analysis/AnalysisContext.h" #include "clang/Basic/OperatorKinds.h" #include +#include +#include #include namespace clang { namespace threadSafety { + +// Various helper functions on til::SExpr +namespace sx { + +inline bool equals(const til::SExpr *E1, const til::SExpr *E2) { + return til::EqualsComparator::compareExprs(E1, E2); +} + +inline bool matches(const til::SExpr *E1, const til::SExpr *E2) { + // We treat a top-level wildcard as the "univsersal" lock. + // It matches everything for the purpose of checking locks, but not + // for unlocking them. + if (isa(E1)) + return isa(E2); + if (isa(E2)) + return isa(E1); + + return til::MatchComparator::compareExprs(E1, E2); +} + +inline bool partiallyMatches(const til::SExpr *E1, const til::SExpr *E2) { + auto *PE1 = dyn_cast_or_null(E1); + if (!PE1) + return false; + auto *PE2 = dyn_cast_or_null(E2); + if (!PE2) + return false; + return PE1->clangDecl() == PE2->clangDecl(); +} + +inline std::string toString(const til::SExpr *E) { + std::stringstream ss; + til::StdPrinter::print(E, ss); + return ss.str(); +} + +} // end namespace sx + + + // This class defines the interface of a clang CFG Visitor. // CFGWalker will invoke the following methods. // Note that methods are not virtual; the visitor is templatized. @@ -206,6 +249,59 @@ private: }; + + +class CapabilityExpr { + // TODO: move this back into ThreadSafety.cpp + // This is specific to thread safety. It is here because + // translateAttrExpr needs it, but that should be moved too. + +private: + const til::SExpr* CapExpr; //< The capability expression. + bool Negated; //< True if this is a negative capability + +public: + CapabilityExpr(const til::SExpr *E, bool Neg) : CapExpr(E), Negated(Neg) {} + + const til::SExpr* sexpr() const { return CapExpr; } + bool negative() const { return Negated; } + + CapabilityExpr operator!() const { + return CapabilityExpr(CapExpr, !Negated); + } + + bool equals(const CapabilityExpr &other) const { + return (Negated == other.Negated) && sx::equals(CapExpr, other.CapExpr); + } + + bool matches(const CapabilityExpr &other) const { + return (Negated == other.Negated) && sx::matches(CapExpr, other.CapExpr); + } + + bool matchesUniv(const CapabilityExpr &CapE) const { + return isUniversal() || matches(CapE); + } + + bool partiallyMatches(const CapabilityExpr &other) const { + return (Negated == other.Negated) && + sx::partiallyMatches(CapExpr, other.CapExpr); + } + + std::string toString() const { + if (Negated) + return "!" + sx::toString(CapExpr); + return sx::toString(CapExpr); + } + + bool shouldIgnore() const { return CapExpr == nullptr; } + + bool isInvalid() const { return sexpr() && isa(sexpr()); } + + bool isUniversal() const { return sexpr() && isa(sexpr()); } +}; + + + // Translate clang::Expr to til::SExpr. class SExprBuilder { public: @@ -242,10 +338,10 @@ public: // Translate a clang expression in an attribute to a til::SExpr. // Constructs the context from D, DeclExp, and SelfDecl. - til::SExpr *translateAttrExpr(const Expr *AttrExp, const NamedDecl *D, - const Expr *DeclExp, VarDecl *SelfDecl=nullptr); + CapabilityExpr translateAttrExpr(const Expr *AttrExp, const NamedDecl *D, + const Expr *DeclExp, VarDecl *SelfD=nullptr); - til::SExpr *translateAttrExpr(const Expr *AttrExp, CallingContext *Ctx); + CapabilityExpr translateAttrExpr(const Expr *AttrExp, CallingContext *Ctx); // Translate a clang statement or expression to a TIL expression. // Also performs substitution of variables; Ctx provides the context. diff --git a/clang/lib/Analysis/ThreadSafety.cpp b/clang/lib/Analysis/ThreadSafety.cpp index f4f174d..e43297a 100644 --- a/clang/lib/Analysis/ThreadSafety.cpp +++ b/clang/lib/Analysis/ThreadSafety.cpp @@ -70,141 +70,65 @@ static void warnInvalidLock(ThreadSafetyHandler &Handler, } -// Various helper functions on til::SExpr -namespace sx { - -bool isUniversal(const til::SExpr *E) { - return isa(E); -} - -bool equals(const til::SExpr *E1, const til::SExpr *E2) { - return til::EqualsComparator::compareExprs(E1, E2); -} - -const til::SExpr* ignorePtrCasts(const til::SExpr *E) { - if (auto *CE = dyn_cast(E)) { - if (CE->castOpcode() == til::CAST_objToPtr) - return CE->expr(); - } - return E; -} - -bool matches(const til::SExpr *E1, const til::SExpr *E2) { - // We treat a top-level wildcard as the "univsersal" lock. - // It matches everything for the purpose of checking locks, but not - // for unlocking them. - if (isa(E1)) - return isa(E2); - if (isa(E2)) - return isa(E1); - - return til::MatchComparator::compareExprs(E1, E2); -} - -bool partiallyMatches(const til::SExpr *E1, const til::SExpr *E2) { - auto *PE1 = dyn_cast_or_null(E1); - if (!PE1) - return false; - auto *PE2 = dyn_cast_or_null(E2); - if (!PE2) - return false; - return PE1->clangDecl() == PE2->clangDecl(); -} - -std::string toString(const til::SExpr *E) { - std::stringstream ss; - til::StdPrinter::print(E, ss); - return ss.str(); -} - -bool shouldIgnore(const til::SExpr *E) { - if (!E) - return true; - // Trap mutex expressions like nullptr, or 0. - // Any literal value is nonsense. - if (isa(E)) - return true; - return false; -} - -} // end namespace sx - - - -/// \brief A short list of SExprs -class MutexIDList : public SmallVector { +/// \brief A set of CapabilityInfo objects, which are compiled from the +/// requires attributes on a function. +class CapExprSet : public SmallVector { public: /// \brief Push M onto list, but discard duplicates. - void push_back_nodup(const til::SExpr *E) { - iterator It = std::find_if(begin(), end(), [=](const til::SExpr *E2) { - return sx::equals(E, E2); + void push_back_nodup(const CapabilityExpr &CapE) { + iterator It = std::find_if(begin(), end(), + [=](const CapabilityExpr &CapE2) { + return CapE.equals(CapE2); }); if (It == end()) - push_back(E); + push_back(CapE); } }; -/// \brief This is a helper class that stores info about the most recent -/// accquire of a Lock. + + +/// \brief This is a helper class that stores a fact that is known at a +/// particular point in program execution. Currently, a fact is a capability, +/// along with additional information, such as where it was acquired, whether +/// it is exclusive or shared, etc. /// -/// The main body of the analysis maps MutexIDs to LockDatas. -struct LockData { - SourceLocation AcquireLoc; - - /// \brief LKind stores whether a lock is held shared or exclusively. - /// Note that this analysis does not currently support either re-entrant - /// locking or lock "upgrading" and "downgrading" between exclusive and - /// shared. - /// - /// FIXME: add support for re-entrant locking and lock up/downgrading - LockKind LKind; - bool Asserted; // for asserted locks - bool Managed; // for ScopedLockable objects - const til::SExpr* UnderlyingMutex; // for ScopedLockable objects - - LockData(SourceLocation AcquireLoc, LockKind LKind, bool M=false, - bool Asrt=false) - : AcquireLoc(AcquireLoc), LKind(LKind), Asserted(Asrt), Managed(M), - UnderlyingMutex(nullptr) - {} +/// FIXME: this analysis does not currently support either re-entrant +/// locking or lock "upgrading" and "downgrading" between exclusive and +/// shared. +class FactEntry : public CapabilityExpr { +private: + LockKind LKind; //< exclusive or shared + SourceLocation AcquireLoc; //< where it was acquired. + bool Managed; //< for ScopedLockable objects + bool Asserted; //< true if the lock was asserted + const til::SExpr* UnderlyingMutex; //< for ScopedLockable objects - LockData(SourceLocation AcquireLoc, LockKind LKind, const til::SExpr *Mu) - : AcquireLoc(AcquireLoc), LKind(LKind), Asserted(false), Managed(false), - UnderlyingMutex(Mu) +public: + FactEntry(const CapabilityExpr &CE, LockKind LK, SourceLocation Loc, + bool Mng=false, bool Asrt=false) + : CapabilityExpr(CE), LKind(LK), AcquireLoc(Loc), Managed(Mng), + Asserted(Asrt), UnderlyingMutex(nullptr) {} - bool operator==(const LockData &other) const { - return AcquireLoc == other.AcquireLoc && LKind == other.LKind; - } - - bool operator!=(const LockData &other) const { - return !(*this == other); - } + FactEntry(const CapabilityExpr &CE, LockKind LK, SourceLocation Loc, + const til::SExpr *Mu) + : CapabilityExpr(CE), LKind(LK), AcquireLoc(Loc), Managed(false), + Asserted(false), UnderlyingMutex(Mu) + {} - void Profile(llvm::FoldingSetNodeID &ID) const { - ID.AddInteger(AcquireLoc.getRawEncoding()); - ID.AddInteger(LKind); - } + LockKind kind() const { return LKind; } + SourceLocation loc() const { return AcquireLoc; } + bool asserted() const { return Asserted; } + bool managed() const { return Managed; } + const til::SExpr* underlying() const { return UnderlyingMutex; } + // Return true if LKind >= LK, where exclusive > shared bool isAtLeast(LockKind LK) { - return (LK == LK_Shared) || (LKind == LK_Exclusive); + return (LKind == LK_Exclusive) || (LK == LK_Shared); } }; -/// \brief A FactEntry stores a single fact that is known at a particular point -/// in the program execution. Currently, this is information regarding a lock -/// that is held at that point. -struct FactEntry { - const til::SExpr *MutID; - LockData LDat; - - FactEntry(const til::SExpr* M, const LockData& L) - : MutID(M), LDat(L) - { } -}; - - typedef unsigned short FactID; /// \brief FactManager manages the memory for all facts that are created during @@ -214,8 +138,8 @@ private: std::vector Facts; public: - FactID newLock(const til::SExpr *M, const LockData& L) { - Facts.push_back(FactEntry(M, L)); + FactID newFact(const FactEntry &Entry) { + Facts.push_back(Entry); return static_cast(Facts.size() - 1); } @@ -249,69 +173,62 @@ public: bool isEmpty() const { return FactIDs.size() == 0; } - FactID addLock(FactManager& FM, const til::SExpr *M, const LockData& L) { - FactID F = FM.newLock(M, L); + FactID addLock(FactManager& FM, const FactEntry &Entry) { + FactID F = FM.newFact(Entry); FactIDs.push_back(F); return F; } - bool removeLock(FactManager& FM, const til::SExpr *M) { + bool removeLock(FactManager& FM, const CapabilityExpr &CapE) { unsigned n = FactIDs.size(); if (n == 0) return false; for (unsigned i = 0; i < n-1; ++i) { - if (sx::matches(FM[FactIDs[i]].MutID, M)) { + if (FM[FactIDs[i]].matches(CapE)) { FactIDs[i] = FactIDs[n-1]; FactIDs.pop_back(); return true; } } - if (sx::matches(FM[FactIDs[n-1]].MutID, M)) { + if (FM[FactIDs[n-1]].matches(CapE)) { FactIDs.pop_back(); return true; } return false; } - iterator findLockIter(FactManager &FM, const til::SExpr *M) { + iterator findLockIter(FactManager &FM, const CapabilityExpr &CapE) { return std::find_if(begin(), end(), [&](FactID ID) { - return sx::matches(FM[ID].MutID, M); + return FM[ID].matches(CapE); }); } - LockData *findLock(FactManager &FM, const til::SExpr *M) const { + FactEntry *findLock(FactManager &FM, const CapabilityExpr &CapE) const { auto I = std::find_if(begin(), end(), [&](FactID ID) { - return sx::matches(FM[ID].MutID, M); + return FM[ID].matches(CapE); }); - - return I != end() ? &FM[*I].LDat : nullptr; + return I != end() ? &FM[*I] : nullptr; } - LockData *findLockUniv(FactManager &FM, const til::SExpr *M) const { + FactEntry *findLockUniv(FactManager &FM, const CapabilityExpr &CapE) const { auto I = std::find_if(begin(), end(), [&](FactID ID) -> bool { - const til::SExpr *E = FM[ID].MutID; - return sx::isUniversal(E) || sx::matches(E, M); + return FM[ID].matchesUniv(CapE); }); - - return I != end() ? &FM[*I].LDat : nullptr; + return I != end() ? &FM[*I] : nullptr; } - FactEntry *findPartialMatch(FactManager &FM, const til::SExpr *M) const { + FactEntry *findPartialMatch(FactManager &FM, + const CapabilityExpr &CapE) const { auto I = std::find_if(begin(), end(), [&](FactID ID) { - return sx::partiallyMatches(FM[ID].MutID, M); + return FM[ID].partiallyMatches(CapE); }); - return I != end() ? &FM[*I] : nullptr; } }; -/// A Lockset maps each SExpr (defined above) to information about how it has -/// been locked. -typedef llvm::ImmutableMap Lockset; typedef llvm::ImmutableMap LocalVarContext; - class LocalVariableMap; /// A side (entry or exit) of a CFG node. @@ -839,6 +756,7 @@ class ThreadSafetyAnalyzer { threadSafety::SExprBuilder SxBuilder; ThreadSafetyHandler &Handler; + const CXXMethodDecl *CurrentMethod; LocalVariableMap LocalVarMap; FactManager FactMan; std::vector BlockInfo; @@ -847,18 +765,17 @@ public: ThreadSafetyAnalyzer(ThreadSafetyHandler &H) : Arena(&Bpa), SxBuilder(Arena), Handler(H) {} - void addLock(FactSet &FSet, const til::SExpr *Mutex, const LockData &LDat, - StringRef DiagKind); - void removeLock(FactSet &FSet, const til::SExpr *Mutex, + void addLock(FactSet &FSet, const FactEntry &Entry, StringRef DiagKind); + void removeLock(FactSet &FSet, const CapabilityExpr &CapE, SourceLocation UnlockLoc, bool FullyRemove, LockKind Kind, StringRef DiagKind); template - void getMutexIDs(MutexIDList &Mtxs, AttrType *Attr, Expr *Exp, + void getMutexIDs(CapExprSet &Mtxs, AttrType *Attr, Expr *Exp, const NamedDecl *D, VarDecl *SelfDecl = nullptr); template - void getMutexIDs(MutexIDList &Mtxs, AttrType *Attr, Expr *Exp, + void getMutexIDs(CapExprSet &Mtxs, AttrType *Attr, Expr *Exp, const NamedDecl *D, const CFGBlock *PredBlock, const CFGBlock *CurrBlock, Expr *BrE, bool Neg); @@ -965,18 +882,19 @@ ClassifyDiagnostic(const AttrTy *A) { /// \brief Add a new lock to the lockset, warning if the lock is already there. /// \param Mutex -- the Mutex expression for the lock /// \param LDat -- the LockData for the lock -void ThreadSafetyAnalyzer::addLock(FactSet &FSet, const til::SExpr *Mutex, - const LockData &LDat, StringRef DiagKind) { - // FIXME: deal with acquired before/after annotations. - // FIXME: Don't always warn when we have support for reentrant locks. - if (sx::shouldIgnore(Mutex)) +void ThreadSafetyAnalyzer::addLock(FactSet &FSet, const FactEntry &Entry, + StringRef DiagKind) { + if (Entry.shouldIgnore()) return; - if (FSet.findLock(FactMan, Mutex)) { - if (!LDat.Asserted) - Handler.handleDoubleLock(DiagKind, sx::toString(Mutex), LDat.AcquireLoc); + + + // FIXME: deal with acquired before/after annotations. + // FIXME: Don't always warn when we have support for reentrant locks. + if (!Entry.asserted() && FSet.findLock(FactMan, Entry)) { + Handler.handleDoubleLock(DiagKind, Entry.toString(), Entry.loc()); } else { - FSet.addLock(FactMan, Mutex, LDat); + FSet.addLock(FactMan, Entry); } } @@ -984,77 +902,78 @@ void ThreadSafetyAnalyzer::addLock(FactSet &FSet, const til::SExpr *Mutex, /// \brief Remove a lock from the lockset, warning if the lock is not there. /// \param Mutex The lock expression corresponding to the lock to be removed /// \param UnlockLoc The source location of the unlock (only used in error msg) -void ThreadSafetyAnalyzer::removeLock(FactSet &FSet, const til::SExpr *Mutex, +void ThreadSafetyAnalyzer::removeLock(FactSet &FSet, const CapabilityExpr &Cp, SourceLocation UnlockLoc, bool FullyRemove, LockKind ReceivedKind, StringRef DiagKind) { - if (sx::shouldIgnore(Mutex)) + if (Cp.shouldIgnore()) return; - const LockData *LDat = FSet.findLock(FactMan, Mutex); + const FactEntry *LDat = FSet.findLock(FactMan, Cp); if (!LDat) { - Handler.handleUnmatchedUnlock(DiagKind, sx::toString(Mutex), UnlockLoc); + Handler.handleUnmatchedUnlock(DiagKind, Cp.toString(), UnlockLoc); return; } // Generic lock removal doesn't care about lock kind mismatches, but // otherwise diagnose when the lock kinds are mismatched. - if (ReceivedKind != LK_Generic && LDat->LKind != ReceivedKind) { - Handler.handleIncorrectUnlockKind(DiagKind, sx::toString(Mutex), - LDat->LKind, ReceivedKind, UnlockLoc); + if (ReceivedKind != LK_Generic && LDat->kind() != ReceivedKind) { + Handler.handleIncorrectUnlockKind(DiagKind, Cp.toString(), + LDat->kind(), ReceivedKind, UnlockLoc); return; } - if (LDat->UnderlyingMutex) { + if (LDat->underlying()) { + CapabilityExpr UnderCp(LDat->underlying(), false); + // This is scoped lockable object, which manages the real mutex. if (FullyRemove) { // We're destroying the managing object. // Remove the underlying mutex if it exists; but don't warn. - if (FSet.findLock(FactMan, LDat->UnderlyingMutex)) - FSet.removeLock(FactMan, LDat->UnderlyingMutex); + if (FSet.findLock(FactMan, UnderCp)) + FSet.removeLock(FactMan, UnderCp); } else { // We're releasing the underlying mutex, but not destroying the // managing object. Warn on dual release. - if (!FSet.findLock(FactMan, LDat->UnderlyingMutex)) { - Handler.handleUnmatchedUnlock( - DiagKind, sx::toString(LDat->UnderlyingMutex), UnlockLoc); + if (!FSet.findLock(FactMan, UnderCp)) { + Handler.handleUnmatchedUnlock(DiagKind, UnderCp.toString(), UnlockLoc); } - FSet.removeLock(FactMan, LDat->UnderlyingMutex); + FSet.removeLock(FactMan, UnderCp); return; } } - FSet.removeLock(FactMan, Mutex); + FSet.removeLock(FactMan, Cp); } /// \brief Extract the list of mutexIDs from the attribute on an expression, /// and push them onto Mtxs, discarding any duplicates. template -void ThreadSafetyAnalyzer::getMutexIDs(MutexIDList &Mtxs, AttrType *Attr, +void ThreadSafetyAnalyzer::getMutexIDs(CapExprSet &Mtxs, AttrType *Attr, Expr *Exp, const NamedDecl *D, VarDecl *SelfDecl) { if (Attr->args_size() == 0) { // The mutex held is the "this" object. - til::SExpr *Mu = SxBuilder.translateAttrExpr(nullptr, D, Exp, SelfDecl); - if (Mu && isa(Mu)) { + CapabilityExpr Cp = SxBuilder.translateAttrExpr(nullptr, D, Exp, SelfDecl); + if (Cp.isInvalid()) { warnInvalidLock(Handler, nullptr, D, Exp, ClassifyDiagnostic(Attr)); return; } //else - if (Mu) - Mtxs.push_back_nodup(Mu); + if (!Cp.shouldIgnore()) + Mtxs.push_back_nodup(Cp); return; } for (const auto *Arg : Attr->args()) { - til::SExpr *Mu = SxBuilder.translateAttrExpr(Arg, D, Exp, SelfDecl); - if (Mu && isa(Mu)) { + CapabilityExpr Cp = SxBuilder.translateAttrExpr(Arg, D, Exp, SelfDecl); + if (Cp.isInvalid()) { warnInvalidLock(Handler, nullptr, D, Exp, ClassifyDiagnostic(Attr)); - return; + continue; } //else - if (Mu) - Mtxs.push_back_nodup(Mu); + if (!Cp.shouldIgnore()) + Mtxs.push_back_nodup(Cp); } } @@ -1063,7 +982,7 @@ void ThreadSafetyAnalyzer::getMutexIDs(MutexIDList &Mtxs, AttrType *Attr, /// trylock applies to the given edge, then push them onto Mtxs, discarding /// any duplicates. template -void ThreadSafetyAnalyzer::getMutexIDs(MutexIDList &Mtxs, AttrType *Attr, +void ThreadSafetyAnalyzer::getMutexIDs(CapExprSet &Mtxs, AttrType *Attr, Expr *Exp, const NamedDecl *D, const CFGBlock *PredBlock, const CFGBlock *CurrBlock, @@ -1195,8 +1114,8 @@ void ThreadSafetyAnalyzer::getEdgeLockset(FactSet& Result, if(!FunDecl || !FunDecl->hasAttrs()) return; - MutexIDList ExclusiveLocksToAdd; - MutexIDList SharedLocksToAdd; + CapExprSet ExclusiveLocksToAdd; + CapExprSet SharedLocksToAdd; // If the condition is a call to a Trylock function, then grab the attributes for (auto *Attr : FunDecl->getAttrs()) { @@ -1225,10 +1144,11 @@ void ThreadSafetyAnalyzer::getEdgeLockset(FactSet& Result, // Add and remove locks. SourceLocation Loc = Exp->getExprLoc(); for (const auto &ExclusiveLockToAdd : ExclusiveLocksToAdd) - addLock(Result, ExclusiveLockToAdd, LockData(Loc, LK_Exclusive), + addLock(Result, FactEntry(ExclusiveLockToAdd, LK_Exclusive, Loc), CapDiagKind); for (const auto &SharedLockToAdd : SharedLocksToAdd) - addLock(Result, SharedLockToAdd, LockData(Loc, LK_Shared), CapDiagKind); + addLock(Result, FactEntry(SharedLockToAdd, LK_Shared, Loc), + CapDiagKind); } /// \brief We use this class to visit different types of expressions in @@ -1245,6 +1165,7 @@ class BuildLockset : public StmtVisitor { unsigned CtxIndex; // Helper functions + bool inCurrentScope(const CapabilityExpr &CapE); void warnIfMutexNotHeld(const NamedDecl *D, const Expr *Exp, AccessKind AK, Expr *MutexExp, ProtectedOperationKind POK, @@ -1274,6 +1195,19 @@ public: void VisitDeclStmt(DeclStmt *S); }; + +inline bool BuildLockset::inCurrentScope(const CapabilityExpr &CapE) { + if (!Analyzer->CurrentMethod) + return false; + if (auto *P = dyn_cast_or_null(CapE.sexpr())) { + auto *VD = P->clangDecl(); + if (VD) + return VD->getDeclContext() == Analyzer->CurrentMethod->getDeclContext(); + } + return false; +} + + /// \brief Warn if the LSet does not contain a lock sufficient to protect access /// of at least the passed in AccessKind. void BuildLockset::warnIfMutexNotHeld(const NamedDecl *D, const Expr *Exp, @@ -1282,59 +1216,83 @@ void BuildLockset::warnIfMutexNotHeld(const NamedDecl *D, const Expr *Exp, StringRef DiagKind) { LockKind LK = getLockKindFromAccessKind(AK); - til::SExpr *Mutex = Analyzer->SxBuilder.translateAttrExpr(MutexExp, D, Exp); - if (!Mutex) { - // TODO: invalid locks? - // warnInvalidLock(Analyzer->Handler, MutexExp, D, Exp, DiagKind); + CapabilityExpr Cp = Analyzer->SxBuilder.translateAttrExpr(MutexExp, D, Exp); + if (Cp.isInvalid()) { + warnInvalidLock(Analyzer->Handler, MutexExp, D, Exp, DiagKind); return; - } else if (sx::shouldIgnore(Mutex)) { + } else if (Cp.shouldIgnore()) { return; } - LockData* LDat = FSet.findLockUniv(Analyzer->FactMan, Mutex); + if (Cp.negative()) { + // Negative capabilities act like locks excluded + FactEntry *LDat = FSet.findLock(Analyzer->FactMan, !Cp); + if (LDat) { + Analyzer->Handler.handleFunExcludesLock( + DiagKind, D->getNameAsString(), (!Cp).toString(), Exp->getExprLoc()); + return; + } + + // If this does not refer to a negative capability in the same class, + // then stop here. + if (!inCurrentScope(Cp)) + return; + + // Otherwise the negative requirement must be propagated to the caller. + LDat = FSet.findLock(Analyzer->FactMan, Cp); + if (!LDat) { + Analyzer->Handler.handleMutexNotHeld("", D, POK, Cp.toString(), + LK_Shared, Exp->getExprLoc()); + } + return; + } + + FactEntry* LDat = FSet.findLockUniv(Analyzer->FactMan, Cp); bool NoError = true; if (!LDat) { // No exact match found. Look for a partial match. - FactEntry* FEntry = FSet.findPartialMatch(Analyzer->FactMan, Mutex); - if (FEntry) { + LDat = FSet.findPartialMatch(Analyzer->FactMan, Cp); + if (LDat) { // Warn that there's no precise match. - LDat = &FEntry->LDat; - std::string PartMatchStr = sx::toString(FEntry->MutID); + std::string PartMatchStr = LDat->toString(); StringRef PartMatchName(PartMatchStr); Analyzer->Handler.handleMutexNotHeld(DiagKind, D, POK, - sx::toString(Mutex), + Cp.toString(), LK, Exp->getExprLoc(), &PartMatchName); } else { // Warn that there's no match at all. Analyzer->Handler.handleMutexNotHeld(DiagKind, D, POK, - sx::toString(Mutex), + Cp.toString(), LK, Exp->getExprLoc()); } NoError = false; } // Make sure the mutex we found is the right kind. - if (NoError && LDat && !LDat->isAtLeast(LK)) + if (NoError && LDat && !LDat->isAtLeast(LK)) { Analyzer->Handler.handleMutexNotHeld(DiagKind, D, POK, - sx::toString(Mutex), + Cp.toString(), LK, Exp->getExprLoc()); + } } /// \brief Warn if the LSet contains the given lock. void BuildLockset::warnIfMutexHeld(const NamedDecl *D, const Expr *Exp, Expr *MutexExp, StringRef DiagKind) { - til::SExpr *Mutex = Analyzer->SxBuilder.translateAttrExpr(MutexExp, D, Exp); - if (!Mutex) { - // TODO: invalid locks? - // warnInvalidLock(Analyzer->Handler, MutexExp, D, Exp, DiagKind); + CapabilityExpr Cp = Analyzer->SxBuilder.translateAttrExpr(MutexExp, D, Exp); + if (Cp.isInvalid()) { + warnInvalidLock(Analyzer->Handler, MutexExp, D, Exp, DiagKind); + return; + } else if (Cp.shouldIgnore()) { return; } - LockData* LDat = FSet.findLock(Analyzer->FactMan, Mutex); - if (LDat) + FactEntry* LDat = FSet.findLock(Analyzer->FactMan, Cp); + if (LDat) { Analyzer->Handler.handleFunExcludesLock( - DiagKind, D->getNameAsString(), sx::toString(Mutex), Exp->getExprLoc()); + DiagKind, D->getNameAsString(), Cp.toString(), Exp->getExprLoc()); + } } /// \brief Checks guarded_by and pt_guarded_by attributes. @@ -1423,8 +1381,8 @@ void BuildLockset::checkPtAccess(const Expr *Exp, AccessKind AK) { void BuildLockset::handleCall(Expr *Exp, const NamedDecl *D, VarDecl *VD) { SourceLocation Loc = Exp->getExprLoc(); const AttrVec &ArgAttrs = D->getAttrs(); - MutexIDList ExclusiveLocksToAdd, SharedLocksToAdd; - MutexIDList ExclusiveLocksToRemove, SharedLocksToRemove, GenericLocksToRemove; + CapExprSet ExclusiveLocksToAdd, SharedLocksToAdd; + CapExprSet ExclusiveLocksToRemove, SharedLocksToRemove, GenericLocksToRemove; StringRef CapDiagKind = "mutex"; for(unsigned i = 0; i < ArgAttrs.size(); ++i) { @@ -1448,22 +1406,22 @@ void BuildLockset::handleCall(Expr *Exp, const NamedDecl *D, VarDecl *VD) { case attr::AssertExclusiveLock: { AssertExclusiveLockAttr *A = cast(At); - MutexIDList AssertLocks; + CapExprSet AssertLocks; Analyzer->getMutexIDs(AssertLocks, A, Exp, D, VD); for (const auto &AssertLock : AssertLocks) - Analyzer->addLock(FSet, AssertLock, - LockData(Loc, LK_Exclusive, false, true), + Analyzer->addLock(FSet, FactEntry(AssertLock, LK_Exclusive, Loc, + false, true), ClassifyDiagnostic(A)); break; } case attr::AssertSharedLock: { AssertSharedLockAttr *A = cast(At); - MutexIDList AssertLocks; + CapExprSet AssertLocks; Analyzer->getMutexIDs(AssertLocks, A, Exp, D, VD); for (const auto &AssertLock : AssertLocks) - Analyzer->addLock(FSet, AssertLock, - LockData(Loc, LK_Shared, false, true), + Analyzer->addLock(FSet, FactEntry(AssertLock, LK_Shared, Loc, + false, true), ClassifyDiagnostic(A)); break; } @@ -1516,29 +1474,30 @@ void BuildLockset::handleCall(Expr *Exp, const NamedDecl *D, VarDecl *VD) { // Add locks. for (const auto &M : ExclusiveLocksToAdd) - Analyzer->addLock(FSet, M, LockData(Loc, LK_Exclusive, isScopedVar), + Analyzer->addLock(FSet, FactEntry(M, LK_Exclusive, Loc, isScopedVar), CapDiagKind); for (const auto &M : SharedLocksToAdd) - Analyzer->addLock(FSet, M, LockData(Loc, LK_Shared, isScopedVar), + Analyzer->addLock(FSet, FactEntry(M, LK_Shared, Loc, isScopedVar), CapDiagKind); // Add the managing object as a dummy mutex, mapped to the underlying mutex. - // FIXME -- this doesn't work if we acquire multiple locks. + // FIXME: this doesn't work if we acquire multiple locks. if (isScopedVar) { SourceLocation MLoc = VD->getLocation(); DeclRefExpr DRE(VD, false, VD->getType(), VK_LValue, VD->getLocation()); - til::SExpr *SMutex = Analyzer->SxBuilder.translateAttrExpr(&DRE, nullptr); + // FIXME: does this store a pointer to DRE? + CapabilityExpr Scp = Analyzer->SxBuilder.translateAttrExpr(&DRE, nullptr); for (const auto &M : ExclusiveLocksToAdd) - Analyzer->addLock(FSet, SMutex, LockData(MLoc, LK_Exclusive, M), + Analyzer->addLock(FSet, FactEntry(Scp, LK_Exclusive, MLoc, M.sexpr()), CapDiagKind); for (const auto &M : SharedLocksToAdd) - Analyzer->addLock(FSet, SMutex, LockData(MLoc, LK_Shared, M), + Analyzer->addLock(FSet, FactEntry(Scp, LK_Shared, MLoc, M.sexpr()), CapDiagKind); // handle corner case where the underlying mutex is invalid if (ExclusiveLocksToAdd.size() == 0 && SharedLocksToAdd.size() == 0) { - Analyzer->addLock(FSet, SMutex, LockData(MLoc, LK_Exclusive), + Analyzer->addLock(FSet, FactEntry(Scp, LK_Exclusive, MLoc), CapDiagKind); } } @@ -1702,64 +1661,68 @@ void ThreadSafetyAnalyzer::intersectAndWarn(FactSet &FSet1, // Find locks in FSet2 that conflict or are not in FSet1, and warn. for (const auto &Fact : FSet2) { - const til::SExpr *FSet2Mutex = FactMan[Fact].MutID; - const LockData &LDat2 = FactMan[Fact].LDat; - FactSet::iterator I1 = FSet1.findLockIter(FactMan, FSet2Mutex); - - if (I1 != FSet1.end()) { - const LockData* LDat1 = &FactMan[*I1].LDat; - if (LDat1->LKind != LDat2.LKind) { - Handler.handleExclusiveAndShared("mutex", sx::toString(FSet2Mutex), - LDat2.AcquireLoc, LDat1->AcquireLoc); - if (Modify && LDat1->LKind != LK_Exclusive) { + const FactEntry *LDat1 = nullptr; + const FactEntry *LDat2 = &FactMan[Fact]; + FactSet::iterator Iter1 = FSet1.findLockIter(FactMan, *LDat2); + if (Iter1 != FSet1.end()) LDat1 = &FactMan[*Iter1]; + + if (LDat1) { + if (LDat1->kind() != LDat2->kind()) { + Handler.handleExclusiveAndShared("mutex", LDat2->toString(), + LDat2->loc(), LDat1->loc()); + if (Modify && LDat1->kind() != LK_Exclusive) { // Take the exclusive lock, which is the one in FSet2. - *I1 = Fact; + *Iter1 = Fact; } } - else if (LDat1->Asserted && !LDat2.Asserted) { + else if (Modify && LDat1->asserted() && !LDat2->asserted()) { // The non-asserted lock in FSet2 is the one we want to track. - *I1 = Fact; + *Iter1 = Fact; } } else { - if (LDat2.UnderlyingMutex) { - if (FSet2.findLock(FactMan, LDat2.UnderlyingMutex)) { + if (LDat2->underlying()) { + if (FSet2.findLock(FactMan, CapabilityExpr(LDat2->underlying(), + false))) { // If this is a scoped lock that manages another mutex, and if the // underlying mutex is still held, then warn about the underlying // mutex. Handler.handleMutexHeldEndOfScope("mutex", - sx::toString(LDat2.UnderlyingMutex), - LDat2.AcquireLoc, JoinLoc, LEK1); + sx::toString(LDat2->underlying()), + LDat2->loc(), JoinLoc, LEK1); } } - else if (!LDat2.Managed && !sx::isUniversal(FSet2Mutex) && - !LDat2.Asserted) - Handler.handleMutexHeldEndOfScope("mutex", sx::toString(FSet2Mutex), - LDat2.AcquireLoc, JoinLoc, LEK1); + else if (!LDat2->managed() && !LDat2->asserted() && + !LDat2->isUniversal()) { + Handler.handleMutexHeldEndOfScope("mutex", LDat2->toString(), + LDat2->loc(), JoinLoc, LEK1); + } } } // Find locks in FSet1 that are not in FSet2, and remove them. for (const auto &Fact : FSet1Orig) { - const til::SExpr *FSet1Mutex = FactMan[Fact].MutID; - const LockData &LDat1 = FactMan[Fact].LDat; + const FactEntry *LDat1 = &FactMan[Fact]; + const FactEntry *LDat2 = FSet2.findLock(FactMan, *LDat1); - if (!FSet2.findLock(FactMan, FSet1Mutex)) { - if (LDat1.UnderlyingMutex) { - if (FSet1Orig.findLock(FactMan, LDat1.UnderlyingMutex)) { + if (!LDat2) { + if (LDat1->underlying()) { + if (FSet1Orig.findLock(FactMan, CapabilityExpr(LDat1->underlying(), + false))) { // If this is a scoped lock that manages another mutex, and if the // underlying mutex is still held, then warn about the underlying // mutex. Handler.handleMutexHeldEndOfScope("mutex", - sx::toString(LDat1.UnderlyingMutex), - LDat1.AcquireLoc, JoinLoc, LEK1); + sx::toString(LDat1->underlying()), + LDat1->loc(), JoinLoc, LEK1); } } - else if (!LDat1.Managed && !sx::isUniversal(FSet1Mutex) && - !LDat1.Asserted) - Handler.handleMutexHeldEndOfScope("mutex", sx::toString(FSet1Mutex), - LDat1.AcquireLoc, JoinLoc, LEK2); + else if (!LDat1->managed() && !LDat1->asserted() && + !LDat1->isUniversal()) { + Handler.handleMutexHeldEndOfScope("mutex", LDat1->toString(), + LDat1->loc(), JoinLoc, LEK2); + } if (Modify) - FSet1.removeLock(FactMan, FSet1Mutex); + FSet1.removeLock(FactMan, *LDat1); } } } @@ -1798,6 +1761,7 @@ void ThreadSafetyAnalyzer::runAnalysis(AnalysisDeclContext &AC) { CFG *CFGraph = walker.getGraph(); const NamedDecl *D = walker.getDecl(); + CurrentMethod = dyn_cast(D); if (D->hasAttr()) return; @@ -1829,9 +1793,9 @@ void ThreadSafetyAnalyzer::runAnalysis(AnalysisDeclContext &AC) { // Fill in source locations for all CFGBlocks. findBlockLocations(CFGraph, SortedGraph, BlockInfo); - MutexIDList ExclusiveLocksAcquired; - MutexIDList SharedLocksAcquired; - MutexIDList LocksReleased; + CapExprSet ExclusiveLocksAcquired; + CapExprSet SharedLocksAcquired; + CapExprSet LocksReleased; // Add locks from exclusive_locks_required and shared_locks_required // to initial lockset. Also turn off checking for lock and unlock functions. @@ -1841,8 +1805,8 @@ void ThreadSafetyAnalyzer::runAnalysis(AnalysisDeclContext &AC) { FactSet &InitialLockset = BlockInfo[FirstBlock->getBlockID()].EntrySet; const AttrVec &ArgAttrs = D->getAttrs(); - MutexIDList ExclusiveLocksToAdd; - MutexIDList SharedLocksToAdd; + CapExprSet ExclusiveLocksToAdd; + CapExprSet SharedLocksToAdd; StringRef CapDiagKind = "mutex"; SourceLocation Loc = D->getLocation(); @@ -1878,11 +1842,11 @@ void ThreadSafetyAnalyzer::runAnalysis(AnalysisDeclContext &AC) { } // FIXME -- Loc can be wrong here. - for (const auto &ExclusiveLockToAdd : ExclusiveLocksToAdd) - addLock(InitialLockset, ExclusiveLockToAdd, LockData(Loc, LK_Exclusive), + for (const auto &Mu : ExclusiveLocksToAdd) + addLock(InitialLockset, FactEntry(Mu, LK_Exclusive, Loc), CapDiagKind); - for (const auto &SharedLockToAdd : SharedLocksToAdd) - addLock(InitialLockset, SharedLockToAdd, LockData(Loc, LK_Shared), + for (const auto &Mu : SharedLocksToAdd) + addLock(InitialLockset, FactEntry(Mu, LK_Shared, Loc), CapDiagKind); } @@ -2052,11 +2016,11 @@ void ThreadSafetyAnalyzer::runAnalysis(AnalysisDeclContext &AC) { // issue the appropriate warning. // FIXME: the location here is not quite right. for (const auto &Lock : ExclusiveLocksAcquired) - ExpectedExitSet.addLock(FactMan, Lock, - LockData(D->getLocation(), LK_Exclusive)); + ExpectedExitSet.addLock(FactMan, FactEntry(Lock, LK_Exclusive, + D->getLocation())); for (const auto &Lock : SharedLocksAcquired) - ExpectedExitSet.addLock(FactMan, Lock, - LockData(D->getLocation(), LK_Shared)); + ExpectedExitSet.addLock(FactMan, FactEntry(Lock, LK_Shared, + D->getLocation())); for (const auto &Lock : LocksReleased) ExpectedExitSet.removeLock(FactMan, Lock); diff --git a/clang/lib/Analysis/ThreadSafetyCommon.cpp b/clang/lib/Analysis/ThreadSafetyCommon.cpp index 56feba7..e9b1f64 100644 --- a/clang/lib/Analysis/ThreadSafetyCommon.cpp +++ b/clang/lib/Analysis/ThreadSafetyCommon.cpp @@ -105,10 +105,10 @@ inline bool isCalleeArrow(const Expr *E) { /// \param D The declaration to which the attribute is attached. /// \param DeclExp An expression involving the Decl to which the attribute /// is attached. E.g. the call to a function. -til::SExpr *SExprBuilder::translateAttrExpr(const Expr *AttrExp, - const NamedDecl *D, - const Expr *DeclExp, - VarDecl *SelfDecl) { +CapabilityExpr SExprBuilder::translateAttrExpr(const Expr *AttrExp, + const NamedDecl *D, + const Expr *DeclExp, + VarDecl *SelfDecl) { // If we are processing a raw attribute expression, with no substitutions. if (!DeclExp) return translateAttrExpr(AttrExp, nullptr); @@ -163,26 +163,48 @@ til::SExpr *SExprBuilder::translateAttrExpr(const Expr *AttrExp, /// \brief Translate a clang expression in an attribute to a til::SExpr. // This assumes a CallingContext has already been created. -til::SExpr *SExprBuilder::translateAttrExpr(const Expr *AttrExp, - CallingContext *Ctx) { - if (const StringLiteral* SLit = dyn_cast_or_null(AttrExp)) { +CapabilityExpr SExprBuilder::translateAttrExpr(const Expr *AttrExp, + CallingContext *Ctx) { + if (!AttrExp) + return CapabilityExpr(nullptr, false); + + if (auto* SLit = dyn_cast(AttrExp)) { if (SLit->getString() == StringRef("*")) // The "*" expr is a universal lock, which essentially turns off // checks until it is removed from the lockset. - return new (Arena) til::Wildcard(); + return CapabilityExpr(new (Arena) til::Wildcard(), false); else // Ignore other string literals for now. - return nullptr; + return CapabilityExpr(nullptr, false); + } + + bool Neg = false; + if (auto *OE = dyn_cast(AttrExp)) { + if (OE->getOperator() == OO_Exclaim) { + Neg = true; + AttrExp = OE->getArg(0); + } + } + else if (auto *UO = dyn_cast(AttrExp)) { + if (UO->getOpcode() == UO_LNot) { + Neg = true; + AttrExp = UO->getSubExpr(); + } } til::SExpr *E = translate(AttrExp, Ctx); + // Trap mutex expressions like nullptr, or 0. + // Any literal value is nonsense. + if (!E || isa(E)) + return CapabilityExpr(nullptr, false); + // Hack to deal with smart pointers -- strip off top-level pointer casts. if (auto *CE = dyn_cast_or_null(E)) { if (CE->castOpcode() == til::CAST_objToPtr) - return CE->expr(); + return CapabilityExpr(CE->expr(), Neg); } - return E; + return CapabilityExpr(E, Neg); } @@ -357,7 +379,8 @@ til::SExpr *SExprBuilder::translateCallExpr(const CallExpr *CE, LRCallCtx.SelfArg = SelfE; LRCallCtx.NumArgs = CE->getNumArgs(); LRCallCtx.FunArgs = CE->getArgs(); - return translateAttrExpr(At->getArg(), &LRCallCtx); + return const_cast( + translateAttrExpr(At->getArg(), &LRCallCtx).sexpr()); } } diff --git a/clang/test/SemaCXX/warn-thread-safety-analysis.cpp b/clang/test/SemaCXX/warn-thread-safety-analysis.cpp index 17ab4c9..be3040e 100644 --- a/clang/test/SemaCXX/warn-thread-safety-analysis.cpp +++ b/clang/test/SemaCXX/warn-thread-safety-analysis.cpp @@ -36,6 +36,9 @@ class __attribute__((lockable)) Mutex { bool ReaderTryLock() __attribute__((shared_trylock_function(true))); void LockWhen(const int &cond) __attribute__((exclusive_lock_function)); + // for negative capabilities + const Mutex& operator!() const { return *this; } + void AssertHeld() ASSERT_EXCLUSIVE_LOCK(); void AssertReaderHeld() ASSERT_SHARED_LOCK(); }; @@ -4517,3 +4520,105 @@ void test(Opaque* o) { } // end namespace ScopedLockReturnedInvalid + +namespace NegativeRequirements { + +class Bar { + Mutex mu; + int a GUARDED_BY(mu); + +public: + void baz() EXCLUSIVE_LOCKS_REQUIRED(!mu) { + mu.Lock(); + a = 0; + mu.Unlock(); + } +}; + + +class Foo { + Mutex mu; + int a GUARDED_BY(mu); + +public: + void foo() { + mu.Lock(); // warning? needs !mu? + baz(); // expected-warning {{cannot call function 'baz' while mutex 'mu' is held}} + bar(); + mu.Unlock(); + } + + void bar() { + baz(); // expected-warning {{calling function 'baz' requires holding '!mu'}} + } + + void baz() EXCLUSIVE_LOCKS_REQUIRED(!mu) { + mu.Lock(); + a = 0; + mu.Unlock(); + } + + void test() { + Bar b; + b.baz(); // no warning -- in different class. + } +}; + +} // end namespace NegativeRequirements + + +namespace NegativeThreadRoles { + +typedef int __attribute__((capability("role"))) ThreadRole; + +void acquire(ThreadRole R) __attribute__((exclusive_lock_function(R))) __attribute__((no_thread_safety_analysis)) {} +void release(ThreadRole R) __attribute__((unlock_function(R))) __attribute__((no_thread_safety_analysis)) {} + +ThreadRole FlightControl, Logger; + +extern void enque_log_msg(const char *msg); +void log_msg(const char *msg) { + enque_log_msg(msg); +} + +void dispatch_log(const char *msg) __attribute__((requires_capability(!FlightControl))) {} +void dispatch_log2(const char *msg) __attribute__((requires_capability(Logger))) {} + +void flight_control_entry(void) __attribute__((requires_capability(FlightControl))) { + dispatch_log("wrong"); /* expected-warning {{cannot call function 'dispatch_log' while mutex 'FlightControl' is held}} */ + dispatch_log2("also wrong"); /* expected-warning {{calling function 'dispatch_log2' requires holding role 'Logger' exclusively}} */ +} + +void spawn_fake_flight_control_thread(void) { + acquire(FlightControl); + flight_control_entry(); + release(FlightControl); +} + +extern const char *deque_log_msg(void) __attribute__((requires_capability(Logger))); +void logger_entry(void) __attribute__((requires_capability(Logger))) { + const char *msg; + + while ((msg = deque_log_msg())) { + dispatch_log(msg); + } +} + +void spawn_fake_logger_thread(void) { + acquire(Logger); + logger_entry(); + release(Logger); +} + +int main(void) { + spawn_fake_flight_control_thread(); + spawn_fake_logger_thread(); + + for (;;) + ; /* Pretend to dispatch things. */ + + return 0; +} + +} + -- 2.7.4