diff options
Diffstat (limited to 'clang/lib/Analysis/ThreadSafety.cpp')
| -rw-r--r-- | clang/lib/Analysis/ThreadSafety.cpp | 2570 |
1 files changed, 2570 insertions, 0 deletions
diff --git a/clang/lib/Analysis/ThreadSafety.cpp b/clang/lib/Analysis/ThreadSafety.cpp new file mode 100644 index 000000000000..c60954374ce3 --- /dev/null +++ b/clang/lib/Analysis/ThreadSafety.cpp @@ -0,0 +1,2570 @@ +//===- ThreadSafety.cpp ---------------------------------------------------===// +// +// 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 +// +//===----------------------------------------------------------------------===// +// +// A intra-procedural analysis for thread safety (e.g. deadlocks and race +// conditions), based off of an annotation system. +// +// See http://clang.llvm.org/docs/ThreadSafetyAnalysis.html +// for more information. +// +//===----------------------------------------------------------------------===// + +#include "clang/Analysis/Analyses/ThreadSafety.h" +#include "clang/AST/Attr.h" +#include "clang/AST/Decl.h" +#include "clang/AST/DeclCXX.h" +#include "clang/AST/DeclGroup.h" +#include "clang/AST/Expr.h" +#include "clang/AST/ExprCXX.h" +#include "clang/AST/OperationKinds.h" +#include "clang/AST/Stmt.h" +#include "clang/AST/StmtVisitor.h" +#include "clang/AST/Type.h" +#include "clang/Analysis/Analyses/PostOrderCFGView.h" +#include "clang/Analysis/Analyses/ThreadSafetyCommon.h" +#include "clang/Analysis/Analyses/ThreadSafetyTIL.h" +#include "clang/Analysis/Analyses/ThreadSafetyTraverse.h" +#include "clang/Analysis/Analyses/ThreadSafetyUtil.h" +#include "clang/Analysis/AnalysisDeclContext.h" +#include "clang/Analysis/CFG.h" +#include "clang/Basic/Builtins.h" +#include "clang/Basic/LLVM.h" +#include "clang/Basic/OperatorKinds.h" +#include "clang/Basic/SourceLocation.h" +#include "clang/Basic/Specifiers.h" +#include "llvm/ADT/ArrayRef.h" +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/ImmutableMap.h" +#include "llvm/ADT/Optional.h" +#include "llvm/ADT/PointerIntPair.h" +#include "llvm/ADT/STLExtras.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/StringRef.h" +#include "llvm/Support/Allocator.h" +#include "llvm/Support/Casting.h" +#include "llvm/Support/ErrorHandling.h" +#include "llvm/Support/raw_ostream.h" +#include <algorithm> +#include <cassert> +#include <functional> +#include <iterator> +#include <memory> +#include <string> +#include <type_traits> +#include <utility> +#include <vector> + +using namespace clang; +using namespace threadSafety; + +// Key method definition +ThreadSafetyHandler::~ThreadSafetyHandler() = default; + +/// Issue a warning about an invalid lock expression +static void warnInvalidLock(ThreadSafetyHandler &Handler, + const Expr *MutexExp, const NamedDecl *D, + const Expr *DeclExp, StringRef Kind) { + SourceLocation Loc; + if (DeclExp) + Loc = DeclExp->getExprLoc(); + + // FIXME: add a note about the attribute location in MutexExp or D + if (Loc.isValid()) + Handler.handleInvalidLockExp(Kind, Loc); +} + +namespace { + +/// A set of CapabilityExpr objects, which are compiled from thread safety +/// attributes on a function. +class CapExprSet : public SmallVector<CapabilityExpr, 4> { +public: + /// Push M onto list, but discard duplicates. + 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(CapE); + } +}; + +class FactManager; +class FactSet; + +/// 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. +/// +/// FIXME: this analysis does not currently support re-entrant locking. +class FactEntry : public CapabilityExpr { +private: + /// Exclusive or shared. + LockKind LKind; + + /// Where it was acquired. + SourceLocation AcquireLoc; + + /// True if the lock was asserted. + bool Asserted; + + /// True if the lock was declared. + bool Declared; + +public: + FactEntry(const CapabilityExpr &CE, LockKind LK, SourceLocation Loc, + bool Asrt, bool Declrd = false) + : CapabilityExpr(CE), LKind(LK), AcquireLoc(Loc), Asserted(Asrt), + Declared(Declrd) {} + virtual ~FactEntry() = default; + + LockKind kind() const { return LKind; } + SourceLocation loc() const { return AcquireLoc; } + bool asserted() const { return Asserted; } + bool declared() const { return Declared; } + + void setDeclared(bool D) { Declared = D; } + + virtual void + handleRemovalFromIntersection(const FactSet &FSet, FactManager &FactMan, + SourceLocation JoinLoc, LockErrorKind LEK, + ThreadSafetyHandler &Handler) const = 0; + virtual void handleLock(FactSet &FSet, FactManager &FactMan, + const FactEntry &entry, ThreadSafetyHandler &Handler, + StringRef DiagKind) const = 0; + virtual void handleUnlock(FactSet &FSet, FactManager &FactMan, + const CapabilityExpr &Cp, SourceLocation UnlockLoc, + bool FullyRemove, ThreadSafetyHandler &Handler, + StringRef DiagKind) const = 0; + + // Return true if LKind >= LK, where exclusive > shared + bool isAtLeast(LockKind LK) const { + return (LKind == LK_Exclusive) || (LK == LK_Shared); + } +}; + +using FactID = unsigned short; + +/// FactManager manages the memory for all facts that are created during +/// the analysis of a single routine. +class FactManager { +private: + std::vector<std::unique_ptr<const FactEntry>> Facts; + +public: + FactID newFact(std::unique_ptr<FactEntry> Entry) { + Facts.push_back(std::move(Entry)); + return static_cast<unsigned short>(Facts.size() - 1); + } + + const FactEntry &operator[](FactID F) const { return *Facts[F]; } +}; + +/// A FactSet is the set of facts that are known to be true at a +/// particular program point. FactSets must be small, because they are +/// frequently copied, and are thus implemented as a set of indices into a +/// table maintained by a FactManager. A typical FactSet only holds 1 or 2 +/// locks, so we can get away with doing a linear search for lookup. Note +/// that a hashtable or map is inappropriate in this case, because lookups +/// may involve partial pattern matches, rather than exact matches. +class FactSet { +private: + using FactVec = SmallVector<FactID, 4>; + + FactVec FactIDs; + +public: + using iterator = FactVec::iterator; + using const_iterator = FactVec::const_iterator; + + iterator begin() { return FactIDs.begin(); } + const_iterator begin() const { return FactIDs.begin(); } + + iterator end() { return FactIDs.end(); } + const_iterator end() const { return FactIDs.end(); } + + bool isEmpty() const { return FactIDs.size() == 0; } + + // Return true if the set contains only negative facts + bool isEmpty(FactManager &FactMan) const { + for (const auto FID : *this) { + if (!FactMan[FID].negative()) + return false; + } + return true; + } + + void addLockByID(FactID ID) { FactIDs.push_back(ID); } + + FactID addLock(FactManager &FM, std::unique_ptr<FactEntry> Entry) { + FactID F = FM.newFact(std::move(Entry)); + FactIDs.push_back(F); + return F; + } + + 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 (FM[FactIDs[i]].matches(CapE)) { + FactIDs[i] = FactIDs[n-1]; + FactIDs.pop_back(); + return true; + } + } + if (FM[FactIDs[n-1]].matches(CapE)) { + FactIDs.pop_back(); + return true; + } + return false; + } + + iterator findLockIter(FactManager &FM, const CapabilityExpr &CapE) { + return std::find_if(begin(), end(), [&](FactID ID) { + return FM[ID].matches(CapE); + }); + } + + const FactEntry *findLock(FactManager &FM, const CapabilityExpr &CapE) const { + auto I = std::find_if(begin(), end(), [&](FactID ID) { + return FM[ID].matches(CapE); + }); + return I != end() ? &FM[*I] : nullptr; + } + + const FactEntry *findLockUniv(FactManager &FM, + const CapabilityExpr &CapE) const { + auto I = std::find_if(begin(), end(), [&](FactID ID) -> bool { + return FM[ID].matchesUniv(CapE); + }); + return I != end() ? &FM[*I] : nullptr; + } + + const FactEntry *findPartialMatch(FactManager &FM, + const CapabilityExpr &CapE) const { + auto I = std::find_if(begin(), end(), [&](FactID ID) -> bool { + return FM[ID].partiallyMatches(CapE); + }); + return I != end() ? &FM[*I] : nullptr; + } + + bool containsMutexDecl(FactManager &FM, const ValueDecl* Vd) const { + auto I = std::find_if(begin(), end(), [&](FactID ID) -> bool { + return FM[ID].valueDecl() == Vd; + }); + return I != end(); + } +}; + +class ThreadSafetyAnalyzer; + +} // namespace + +namespace clang { +namespace threadSafety { + +class BeforeSet { +private: + using BeforeVect = SmallVector<const ValueDecl *, 4>; + + struct BeforeInfo { + BeforeVect Vect; + int Visited = 0; + + BeforeInfo() = default; + BeforeInfo(BeforeInfo &&) = default; + }; + + using BeforeMap = + llvm::DenseMap<const ValueDecl *, std::unique_ptr<BeforeInfo>>; + using CycleMap = llvm::DenseMap<const ValueDecl *, bool>; + +public: + BeforeSet() = default; + + BeforeInfo* insertAttrExprs(const ValueDecl* Vd, + ThreadSafetyAnalyzer& Analyzer); + + BeforeInfo *getBeforeInfoForDecl(const ValueDecl *Vd, + ThreadSafetyAnalyzer &Analyzer); + + void checkBeforeAfter(const ValueDecl* Vd, + const FactSet& FSet, + ThreadSafetyAnalyzer& Analyzer, + SourceLocation Loc, StringRef CapKind); + +private: + BeforeMap BMap; + CycleMap CycMap; +}; + +} // namespace threadSafety +} // namespace clang + +namespace { + +class LocalVariableMap; + +using LocalVarContext = llvm::ImmutableMap<const NamedDecl *, unsigned>; + +/// A side (entry or exit) of a CFG node. +enum CFGBlockSide { CBS_Entry, CBS_Exit }; + +/// CFGBlockInfo is a struct which contains all the information that is +/// maintained for each block in the CFG. See LocalVariableMap for more +/// information about the contexts. +struct CFGBlockInfo { + // Lockset held at entry to block + FactSet EntrySet; + + // Lockset held at exit from block + FactSet ExitSet; + + // Context held at entry to block + LocalVarContext EntryContext; + + // Context held at exit from block + LocalVarContext ExitContext; + + // Location of first statement in block + SourceLocation EntryLoc; + + // Location of last statement in block. + SourceLocation ExitLoc; + + // Used to replay contexts later + unsigned EntryIndex; + + // Is this block reachable? + bool Reachable = false; + + const FactSet &getSet(CFGBlockSide Side) const { + return Side == CBS_Entry ? EntrySet : ExitSet; + } + + SourceLocation getLocation(CFGBlockSide Side) const { + return Side == CBS_Entry ? EntryLoc : ExitLoc; + } + +private: + CFGBlockInfo(LocalVarContext EmptyCtx) + : EntryContext(EmptyCtx), ExitContext(EmptyCtx) {} + +public: + static CFGBlockInfo getEmptyBlockInfo(LocalVariableMap &M); +}; + +// A LocalVariableMap maintains a map from local variables to their currently +// valid definitions. It provides SSA-like functionality when traversing the +// CFG. Like SSA, each definition or assignment to a variable is assigned a +// unique name (an integer), which acts as the SSA name for that definition. +// The total set of names is shared among all CFG basic blocks. +// Unlike SSA, we do not rewrite expressions to replace local variables declrefs +// with their SSA-names. Instead, we compute a Context for each point in the +// code, which maps local variables to the appropriate SSA-name. This map +// changes with each assignment. +// +// The map is computed in a single pass over the CFG. Subsequent analyses can +// then query the map to find the appropriate Context for a statement, and use +// that Context to look up the definitions of variables. +class LocalVariableMap { +public: + using Context = LocalVarContext; + + /// A VarDefinition consists of an expression, representing the value of the + /// variable, along with the context in which that expression should be + /// interpreted. A reference VarDefinition does not itself contain this + /// information, but instead contains a pointer to a previous VarDefinition. + struct VarDefinition { + public: + friend class LocalVariableMap; + + // The original declaration for this variable. + const NamedDecl *Dec; + + // The expression for this variable, OR + const Expr *Exp = nullptr; + + // Reference to another VarDefinition + unsigned Ref = 0; + + // The map with which Exp should be interpreted. + Context Ctx; + + bool isReference() { return !Exp; } + + private: + // Create ordinary variable definition + VarDefinition(const NamedDecl *D, const Expr *E, Context C) + : Dec(D), Exp(E), Ctx(C) {} + + // Create reference to previous definition + VarDefinition(const NamedDecl *D, unsigned R, Context C) + : Dec(D), Ref(R), Ctx(C) {} + }; + +private: + Context::Factory ContextFactory; + std::vector<VarDefinition> VarDefinitions; + std::vector<unsigned> CtxIndices; + std::vector<std::pair<const Stmt *, Context>> SavedContexts; + +public: + LocalVariableMap() { + // index 0 is a placeholder for undefined variables (aka phi-nodes). + VarDefinitions.push_back(VarDefinition(nullptr, 0u, getEmptyContext())); + } + + /// Look up a definition, within the given context. + const VarDefinition* lookup(const NamedDecl *D, Context Ctx) { + const unsigned *i = Ctx.lookup(D); + if (!i) + return nullptr; + assert(*i < VarDefinitions.size()); + return &VarDefinitions[*i]; + } + + /// Look up the definition for D within the given context. Returns + /// NULL if the expression is not statically known. If successful, also + /// modifies Ctx to hold the context of the return Expr. + const Expr* lookupExpr(const NamedDecl *D, Context &Ctx) { + const unsigned *P = Ctx.lookup(D); + if (!P) + return nullptr; + + unsigned i = *P; + while (i > 0) { + if (VarDefinitions[i].Exp) { + Ctx = VarDefinitions[i].Ctx; + return VarDefinitions[i].Exp; + } + i = VarDefinitions[i].Ref; + } + return nullptr; + } + + Context getEmptyContext() { return ContextFactory.getEmptyMap(); } + + /// Return the next context after processing S. This function is used by + /// clients of the class to get the appropriate context when traversing the + /// CFG. It must be called for every assignment or DeclStmt. + Context getNextContext(unsigned &CtxIndex, const Stmt *S, Context C) { + if (SavedContexts[CtxIndex+1].first == S) { + CtxIndex++; + Context Result = SavedContexts[CtxIndex].second; + return Result; + } + return C; + } + + void dumpVarDefinitionName(unsigned i) { + if (i == 0) { + llvm::errs() << "Undefined"; + return; + } + const NamedDecl *Dec = VarDefinitions[i].Dec; + if (!Dec) { + llvm::errs() << "<<NULL>>"; + return; + } + Dec->printName(llvm::errs()); + llvm::errs() << "." << i << " " << ((const void*) Dec); + } + + /// Dumps an ASCII representation of the variable map to llvm::errs() + void dump() { + for (unsigned i = 1, e = VarDefinitions.size(); i < e; ++i) { + const Expr *Exp = VarDefinitions[i].Exp; + unsigned Ref = VarDefinitions[i].Ref; + + dumpVarDefinitionName(i); + llvm::errs() << " = "; + if (Exp) Exp->dump(); + else { + dumpVarDefinitionName(Ref); + llvm::errs() << "\n"; + } + } + } + + /// Dumps an ASCII representation of a Context to llvm::errs() + void dumpContext(Context C) { + for (Context::iterator I = C.begin(), E = C.end(); I != E; ++I) { + const NamedDecl *D = I.getKey(); + D->printName(llvm::errs()); + const unsigned *i = C.lookup(D); + llvm::errs() << " -> "; + dumpVarDefinitionName(*i); + llvm::errs() << "\n"; + } + } + + /// Builds the variable map. + void traverseCFG(CFG *CFGraph, const PostOrderCFGView *SortedGraph, + std::vector<CFGBlockInfo> &BlockInfo); + +protected: + friend class VarMapBuilder; + + // Get the current context index + unsigned getContextIndex() { return SavedContexts.size()-1; } + + // Save the current context for later replay + void saveContext(const Stmt *S, Context C) { + SavedContexts.push_back(std::make_pair(S, C)); + } + + // Adds a new definition to the given context, and returns a new context. + // This method should be called when declaring a new variable. + Context addDefinition(const NamedDecl *D, const Expr *Exp, Context Ctx) { + assert(!Ctx.contains(D)); + unsigned newID = VarDefinitions.size(); + Context NewCtx = ContextFactory.add(Ctx, D, newID); + VarDefinitions.push_back(VarDefinition(D, Exp, Ctx)); + return NewCtx; + } + + // Add a new reference to an existing definition. + Context addReference(const NamedDecl *D, unsigned i, Context Ctx) { + unsigned newID = VarDefinitions.size(); + Context NewCtx = ContextFactory.add(Ctx, D, newID); + VarDefinitions.push_back(VarDefinition(D, i, Ctx)); + return NewCtx; + } + + // Updates a definition only if that definition is already in the map. + // This method should be called when assigning to an existing variable. + Context updateDefinition(const NamedDecl *D, Expr *Exp, Context Ctx) { + if (Ctx.contains(D)) { + unsigned newID = VarDefinitions.size(); + Context NewCtx = ContextFactory.remove(Ctx, D); + NewCtx = ContextFactory.add(NewCtx, D, newID); + VarDefinitions.push_back(VarDefinition(D, Exp, Ctx)); + return NewCtx; + } + return Ctx; + } + + // Removes a definition from the context, but keeps the variable name + // as a valid variable. The index 0 is a placeholder for cleared definitions. + Context clearDefinition(const NamedDecl *D, Context Ctx) { + Context NewCtx = Ctx; + if (NewCtx.contains(D)) { + NewCtx = ContextFactory.remove(NewCtx, D); + NewCtx = ContextFactory.add(NewCtx, D, 0); + } + return NewCtx; + } + + // Remove a definition entirely frmo the context. + Context removeDefinition(const NamedDecl *D, Context Ctx) { + Context NewCtx = Ctx; + if (NewCtx.contains(D)) { + NewCtx = ContextFactory.remove(NewCtx, D); + } + return NewCtx; + } + + Context intersectContexts(Context C1, Context C2); + Context createReferenceContext(Context C); + void intersectBackEdge(Context C1, Context C2); +}; + +} // namespace + +// This has to be defined after LocalVariableMap. +CFGBlockInfo CFGBlockInfo::getEmptyBlockInfo(LocalVariableMap &M) { + return CFGBlockInfo(M.getEmptyContext()); +} + +namespace { + +/// Visitor which builds a LocalVariableMap +class VarMapBuilder : public ConstStmtVisitor<VarMapBuilder> { +public: + LocalVariableMap* VMap; + LocalVariableMap::Context Ctx; + + VarMapBuilder(LocalVariableMap *VM, LocalVariableMap::Context C) + : VMap(VM), Ctx(C) {} + + void VisitDeclStmt(const DeclStmt *S); + void VisitBinaryOperator(const BinaryOperator *BO); +}; + +} // namespace + +// Add new local variables to the variable map +void VarMapBuilder::VisitDeclStmt(const DeclStmt *S) { + bool modifiedCtx = false; + const DeclGroupRef DGrp = S->getDeclGroup(); + for (const auto *D : DGrp) { + if (const auto *VD = dyn_cast_or_null<VarDecl>(D)) { + const Expr *E = VD->getInit(); + + // Add local variables with trivial type to the variable map + QualType T = VD->getType(); + if (T.isTrivialType(VD->getASTContext())) { + Ctx = VMap->addDefinition(VD, E, Ctx); + modifiedCtx = true; + } + } + } + if (modifiedCtx) + VMap->saveContext(S, Ctx); +} + +// Update local variable definitions in variable map +void VarMapBuilder::VisitBinaryOperator(const BinaryOperator *BO) { + if (!BO->isAssignmentOp()) + return; + + Expr *LHSExp = BO->getLHS()->IgnoreParenCasts(); + + // Update the variable map and current context. + if (const auto *DRE = dyn_cast<DeclRefExpr>(LHSExp)) { + const ValueDecl *VDec = DRE->getDecl(); + if (Ctx.lookup(VDec)) { + if (BO->getOpcode() == BO_Assign) + Ctx = VMap->updateDefinition(VDec, BO->getRHS(), Ctx); + else + // FIXME -- handle compound assignment operators + Ctx = VMap->clearDefinition(VDec, Ctx); + VMap->saveContext(BO, Ctx); + } + } +} + +// Computes the intersection of two contexts. The intersection is the +// set of variables which have the same definition in both contexts; +// variables with different definitions are discarded. +LocalVariableMap::Context +LocalVariableMap::intersectContexts(Context C1, Context C2) { + Context Result = C1; + for (const auto &P : C1) { + const NamedDecl *Dec = P.first; + const unsigned *i2 = C2.lookup(Dec); + if (!i2) // variable doesn't exist on second path + Result = removeDefinition(Dec, Result); + else if (*i2 != P.second) // variable exists, but has different definition + Result = clearDefinition(Dec, Result); + } + return Result; +} + +// For every variable in C, create a new variable that refers to the +// definition in C. Return a new context that contains these new variables. +// (We use this for a naive implementation of SSA on loop back-edges.) +LocalVariableMap::Context LocalVariableMap::createReferenceContext(Context C) { + Context Result = getEmptyContext(); + for (const auto &P : C) + Result = addReference(P.first, P.second, Result); + return Result; +} + +// This routine also takes the intersection of C1 and C2, but it does so by +// altering the VarDefinitions. C1 must be the result of an earlier call to +// createReferenceContext. +void LocalVariableMap::intersectBackEdge(Context C1, Context C2) { + for (const auto &P : C1) { + unsigned i1 = P.second; + VarDefinition *VDef = &VarDefinitions[i1]; + assert(VDef->isReference()); + + const unsigned *i2 = C2.lookup(P.first); + if (!i2 || (*i2 != i1)) + VDef->Ref = 0; // Mark this variable as undefined + } +} + +// Traverse the CFG in topological order, so all predecessors of a block +// (excluding back-edges) are visited before the block itself. At +// each point in the code, we calculate a Context, which holds the set of +// variable definitions which are visible at that point in execution. +// Visible variables are mapped to their definitions using an array that +// contains all definitions. +// +// At join points in the CFG, the set is computed as the intersection of +// the incoming sets along each edge, E.g. +// +// { Context | VarDefinitions } +// int x = 0; { x -> x1 | x1 = 0 } +// int y = 0; { x -> x1, y -> y1 | y1 = 0, x1 = 0 } +// if (b) x = 1; { x -> x2, y -> y1 | x2 = 1, y1 = 0, ... } +// else x = 2; { x -> x3, y -> y1 | x3 = 2, x2 = 1, ... } +// ... { y -> y1 (x is unknown) | x3 = 2, x2 = 1, ... } +// +// This is essentially a simpler and more naive version of the standard SSA +// algorithm. Those definitions that remain in the intersection are from blocks +// that strictly dominate the current block. We do not bother to insert proper +// phi nodes, because they are not used in our analysis; instead, wherever +// a phi node would be required, we simply remove that definition from the +// context (E.g. x above). +// +// The initial traversal does not capture back-edges, so those need to be +// handled on a separate pass. Whenever the first pass encounters an +// incoming back edge, it duplicates the context, creating new definitions +// that refer back to the originals. (These correspond to places where SSA +// might have to insert a phi node.) On the second pass, these definitions are +// set to NULL if the variable has changed on the back-edge (i.e. a phi +// node was actually required.) E.g. +// +// { Context | VarDefinitions } +// int x = 0, y = 0; { x -> x1, y -> y1 | y1 = 0, x1 = 0 } +// while (b) { x -> x2, y -> y1 | [1st:] x2=x1; [2nd:] x2=NULL; } +// x = x+1; { x -> x3, y -> y1 | x3 = x2 + 1, ... } +// ... { y -> y1 | x3 = 2, x2 = 1, ... } +void LocalVariableMap::traverseCFG(CFG *CFGraph, + const PostOrderCFGView *SortedGraph, + std::vector<CFGBlockInfo> &BlockInfo) { + PostOrderCFGView::CFGBlockSet VisitedBlocks(CFGraph); + + CtxIndices.resize(CFGraph->getNumBlockIDs()); + + for (const auto *CurrBlock : *SortedGraph) { + unsigned CurrBlockID = CurrBlock->getBlockID(); + CFGBlockInfo *CurrBlockInfo = &BlockInfo[CurrBlockID]; + + VisitedBlocks.insert(CurrBlock); + + // Calculate the entry context for the current block + bool HasBackEdges = false; + bool CtxInit = true; + for (CFGBlock::const_pred_iterator PI = CurrBlock->pred_begin(), + PE = CurrBlock->pred_end(); PI != PE; ++PI) { + // if *PI -> CurrBlock is a back edge, so skip it + if (*PI == nullptr || !VisitedBlocks.alreadySet(*PI)) { + HasBackEdges = true; + continue; + } + + unsigned PrevBlockID = (*PI)->getBlockID(); + CFGBlockInfo *PrevBlockInfo = &BlockInfo[PrevBlockID]; + + if (CtxInit) { + CurrBlockInfo->EntryContext = PrevBlockInfo->ExitContext; + CtxInit = false; + } + else { + CurrBlockInfo->EntryContext = + intersectContexts(CurrBlockInfo->EntryContext, + PrevBlockInfo->ExitContext); + } + } + + // Duplicate the context if we have back-edges, so we can call + // intersectBackEdges later. + if (HasBackEdges) + CurrBlockInfo->EntryContext = + createReferenceContext(CurrBlockInfo->EntryContext); + + // Create a starting context index for the current block + saveContext(nullptr, CurrBlockInfo->EntryContext); + CurrBlockInfo->EntryIndex = getContextIndex(); + + // Visit all the statements in the basic block. + VarMapBuilder VMapBuilder(this, CurrBlockInfo->EntryContext); + for (const auto &BI : *CurrBlock) { + switch (BI.getKind()) { + case CFGElement::Statement: { + CFGStmt CS = BI.castAs<CFGStmt>(); + VMapBuilder.Visit(CS.getStmt()); + break; + } + default: + break; + } + } + CurrBlockInfo->ExitContext = VMapBuilder.Ctx; + + // Mark variables on back edges as "unknown" if they've been changed. + for (CFGBlock::const_succ_iterator SI = CurrBlock->succ_begin(), + SE = CurrBlock->succ_end(); SI != SE; ++SI) { + // if CurrBlock -> *SI is *not* a back edge + if (*SI == nullptr || !VisitedBlocks.alreadySet(*SI)) + continue; + + CFGBlock *FirstLoopBlock = *SI; + Context LoopBegin = BlockInfo[FirstLoopBlock->getBlockID()].EntryContext; + Context LoopEnd = CurrBlockInfo->ExitContext; + intersectBackEdge(LoopBegin, LoopEnd); + } + } + + // Put an extra entry at the end of the indexed context array + unsigned exitID = CFGraph->getExit().getBlockID(); + saveContext(nullptr, BlockInfo[exitID].ExitContext); +} + +/// Find the appropriate source locations to use when producing diagnostics for +/// each block in the CFG. +static void findBlockLocations(CFG *CFGraph, + const PostOrderCFGView *SortedGraph, + std::vector<CFGBlockInfo> &BlockInfo) { + for (const auto *CurrBlock : *SortedGraph) { + CFGBlockInfo *CurrBlockInfo = &BlockInfo[CurrBlock->getBlockID()]; + + // Find the source location of the last statement in the block, if the + // block is not empty. + if (const Stmt *S = CurrBlock->getTerminatorStmt()) { + CurrBlockInfo->EntryLoc = CurrBlockInfo->ExitLoc = S->getBeginLoc(); + } else { + for (CFGBlock::const_reverse_iterator BI = CurrBlock->rbegin(), + BE = CurrBlock->rend(); BI != BE; ++BI) { + // FIXME: Handle other CFGElement kinds. + if (Optional<CFGStmt> CS = BI->getAs<CFGStmt>()) { + CurrBlockInfo->ExitLoc = CS->getStmt()->getBeginLoc(); + break; + } + } + } + + if (CurrBlockInfo->ExitLoc.isValid()) { + // This block contains at least one statement. Find the source location + // of the first statement in the block. + for (const auto &BI : *CurrBlock) { + // FIXME: Handle other CFGElement kinds. + if (Optional<CFGStmt> CS = BI.getAs<CFGStmt>()) { + CurrBlockInfo->EntryLoc = CS->getStmt()->getBeginLoc(); + break; + } + } + } else if (CurrBlock->pred_size() == 1 && *CurrBlock->pred_begin() && + CurrBlock != &CFGraph->getExit()) { + // The block is empty, and has a single predecessor. Use its exit + // location. + CurrBlockInfo->EntryLoc = CurrBlockInfo->ExitLoc = + BlockInfo[(*CurrBlock->pred_begin())->getBlockID()].ExitLoc; + } + } +} + +namespace { + +class LockableFactEntry : public FactEntry { +private: + /// managed by ScopedLockable object + bool Managed; + +public: + LockableFactEntry(const CapabilityExpr &CE, LockKind LK, SourceLocation Loc, + bool Mng = false, bool Asrt = false) + : FactEntry(CE, LK, Loc, Asrt), Managed(Mng) {} + + void + handleRemovalFromIntersection(const FactSet &FSet, FactManager &FactMan, + SourceLocation JoinLoc, LockErrorKind LEK, + ThreadSafetyHandler &Handler) const override { + if (!Managed && !asserted() && !negative() && !isUniversal()) { + Handler.handleMutexHeldEndOfScope("mutex", toString(), loc(), JoinLoc, + LEK); + } + } + + void handleLock(FactSet &FSet, FactManager &FactMan, const FactEntry &entry, + ThreadSafetyHandler &Handler, + StringRef DiagKind) const override { + Handler.handleDoubleLock(DiagKind, entry.toString(), loc(), entry.loc()); + } + + void handleUnlock(FactSet &FSet, FactManager &FactMan, + const CapabilityExpr &Cp, SourceLocation UnlockLoc, + bool FullyRemove, ThreadSafetyHandler &Handler, + StringRef DiagKind) const override { + FSet.removeLock(FactMan, Cp); + if (!Cp.negative()) { + FSet.addLock(FactMan, std::make_unique<LockableFactEntry>( + !Cp, LK_Exclusive, UnlockLoc)); + } + } +}; + +class ScopedLockableFactEntry : public FactEntry { +private: + enum UnderlyingCapabilityKind { + UCK_Acquired, ///< Any kind of acquired capability. + UCK_ReleasedShared, ///< Shared capability that was released. + UCK_ReleasedExclusive, ///< Exclusive capability that was released. + }; + + using UnderlyingCapability = + llvm::PointerIntPair<const til::SExpr *, 2, UnderlyingCapabilityKind>; + + SmallVector<UnderlyingCapability, 4> UnderlyingMutexes; + +public: + ScopedLockableFactEntry(const CapabilityExpr &CE, SourceLocation Loc) + : FactEntry(CE, LK_Exclusive, Loc, false) {} + + void addExclusiveLock(const CapabilityExpr &M) { + UnderlyingMutexes.emplace_back(M.sexpr(), UCK_Acquired); + } + + void addSharedLock(const CapabilityExpr &M) { + UnderlyingMutexes.emplace_back(M.sexpr(), UCK_Acquired); + } + + void addExclusiveUnlock(const CapabilityExpr &M) { + UnderlyingMutexes.emplace_back(M.sexpr(), UCK_ReleasedExclusive); + } + + void addSharedUnlock(const CapabilityExpr &M) { + UnderlyingMutexes.emplace_back(M.sexpr(), UCK_ReleasedShared); + } + + void + handleRemovalFromIntersection(const FactSet &FSet, FactManager &FactMan, + SourceLocation JoinLoc, LockErrorKind LEK, + ThreadSafetyHandler &Handler) const override { + for (const auto &UnderlyingMutex : UnderlyingMutexes) { + const auto *Entry = FSet.findLock( + FactMan, CapabilityExpr(UnderlyingMutex.getPointer(), false)); + if ((UnderlyingMutex.getInt() == UCK_Acquired && Entry) || + (UnderlyingMutex.getInt() != UCK_Acquired && !Entry)) { + // If this scoped lock manages another mutex, and if the underlying + // mutex is still/not held, then warn about the underlying mutex. + Handler.handleMutexHeldEndOfScope( + "mutex", sx::toString(UnderlyingMutex.getPointer()), loc(), JoinLoc, + LEK); + } + } + } + + void handleLock(FactSet &FSet, FactManager &FactMan, const FactEntry &entry, + ThreadSafetyHandler &Handler, + StringRef DiagKind) const override { + for (const auto &UnderlyingMutex : UnderlyingMutexes) { + CapabilityExpr UnderCp(UnderlyingMutex.getPointer(), false); + + if (UnderlyingMutex.getInt() == UCK_Acquired) + lock(FSet, FactMan, UnderCp, entry.kind(), entry.loc(), &Handler, + DiagKind); + else + unlock(FSet, FactMan, UnderCp, entry.loc(), &Handler, DiagKind); + } + } + + void handleUnlock(FactSet &FSet, FactManager &FactMan, + const CapabilityExpr &Cp, SourceLocation UnlockLoc, + bool FullyRemove, ThreadSafetyHandler &Handler, + StringRef DiagKind) const override { + assert(!Cp.negative() && "Managing object cannot be negative."); + for (const auto &UnderlyingMutex : UnderlyingMutexes) { + CapabilityExpr UnderCp(UnderlyingMutex.getPointer(), false); + + // Remove/lock the underlying mutex if it exists/is still unlocked; warn + // on double unlocking/locking if we're not destroying the scoped object. + ThreadSafetyHandler *TSHandler = FullyRemove ? nullptr : &Handler; + if (UnderlyingMutex.getInt() == UCK_Acquired) { + unlock(FSet, FactMan, UnderCp, UnlockLoc, TSHandler, DiagKind); + } else { + LockKind kind = UnderlyingMutex.getInt() == UCK_ReleasedShared + ? LK_Shared + : LK_Exclusive; + lock(FSet, FactMan, UnderCp, kind, UnlockLoc, TSHandler, DiagKind); + } + } + if (FullyRemove) + FSet.removeLock(FactMan, Cp); + } + +private: + void lock(FactSet &FSet, FactManager &FactMan, const CapabilityExpr &Cp, + LockKind kind, SourceLocation loc, ThreadSafetyHandler *Handler, + StringRef DiagKind) const { + if (const FactEntry *Fact = FSet.findLock(FactMan, Cp)) { + if (Handler) + Handler->handleDoubleLock(DiagKind, Cp.toString(), Fact->loc(), loc); + } else { + FSet.removeLock(FactMan, !Cp); + FSet.addLock(FactMan, + std::make_unique<LockableFactEntry>(Cp, kind, loc)); + } + } + + void unlock(FactSet &FSet, FactManager &FactMan, const CapabilityExpr &Cp, + SourceLocation loc, ThreadSafetyHandler *Handler, + StringRef DiagKind) const { + if (FSet.findLock(FactMan, Cp)) { + FSet.removeLock(FactMan, Cp); + FSet.addLock(FactMan, std::make_unique<LockableFactEntry>( + !Cp, LK_Exclusive, loc)); + } else if (Handler) { + Handler->handleUnmatchedUnlock(DiagKind, Cp.toString(), loc); + } + } +}; + +/// Class which implements the core thread safety analysis routines. +class ThreadSafetyAnalyzer { + friend class BuildLockset; + friend class threadSafety::BeforeSet; + + llvm::BumpPtrAllocator Bpa; + threadSafety::til::MemRegionRef Arena; + threadSafety::SExprBuilder SxBuilder; + + ThreadSafetyHandler &Handler; + const CXXMethodDecl *CurrentMethod; + LocalVariableMap LocalVarMap; + FactManager FactMan; + std::vector<CFGBlockInfo> BlockInfo; + + BeforeSet *GlobalBeforeSet; + +public: + ThreadSafetyAnalyzer(ThreadSafetyHandler &H, BeforeSet* Bset) + : Arena(&Bpa), SxBuilder(Arena), Handler(H), GlobalBeforeSet(Bset) {} + + bool inCurrentScope(const CapabilityExpr &CapE); + + void addLock(FactSet &FSet, std::unique_ptr<FactEntry> Entry, + StringRef DiagKind, bool ReqAttr = false); + void removeLock(FactSet &FSet, const CapabilityExpr &CapE, + SourceLocation UnlockLoc, bool FullyRemove, LockKind Kind, + StringRef DiagKind); + + template <typename AttrType> + void getMutexIDs(CapExprSet &Mtxs, AttrType *Attr, const Expr *Exp, + const NamedDecl *D, VarDecl *SelfDecl = nullptr); + + template <class AttrType> + void getMutexIDs(CapExprSet &Mtxs, AttrType *Attr, const Expr *Exp, + const NamedDecl *D, + const CFGBlock *PredBlock, const CFGBlock *CurrBlock, + Expr *BrE, bool Neg); + + const CallExpr* getTrylockCallExpr(const Stmt *Cond, LocalVarContext C, + bool &Negate); + + void getEdgeLockset(FactSet &Result, const FactSet &ExitSet, + const CFGBlock* PredBlock, + const CFGBlock *CurrBlock); + + void intersectAndWarn(FactSet &FSet1, const FactSet &FSet2, + SourceLocation JoinLoc, + LockErrorKind LEK1, LockErrorKind LEK2, + bool Modify=true); + + void intersectAndWarn(FactSet &FSet1, const FactSet &FSet2, + SourceLocation JoinLoc, LockErrorKind LEK1, + bool Modify=true) { + intersectAndWarn(FSet1, FSet2, JoinLoc, LEK1, LEK1, Modify); + } + + void runAnalysis(AnalysisDeclContext &AC); +}; + +} // namespace + +/// Process acquired_before and acquired_after attributes on Vd. +BeforeSet::BeforeInfo* BeforeSet::insertAttrExprs(const ValueDecl* Vd, + ThreadSafetyAnalyzer& Analyzer) { + // Create a new entry for Vd. + BeforeInfo *Info = nullptr; + { + // Keep InfoPtr in its own scope in case BMap is modified later and the + // reference becomes invalid. + std::unique_ptr<BeforeInfo> &InfoPtr = BMap[Vd]; + if (!InfoPtr) + InfoPtr.reset(new BeforeInfo()); + Info = InfoPtr.get(); + } + + for (const auto *At : Vd->attrs()) { + switch (At->getKind()) { + case attr::AcquiredBefore: { + const auto *A = cast<AcquiredBeforeAttr>(At); + + // Read exprs from the attribute, and add them to BeforeVect. + for (const auto *Arg : A->args()) { + CapabilityExpr Cp = + Analyzer.SxBuilder.translateAttrExpr(Arg, nullptr); + if (const ValueDecl *Cpvd = Cp.valueDecl()) { + Info->Vect.push_back(Cpvd); + const auto It = BMap.find(Cpvd); + if (It == BMap.end()) + insertAttrExprs(Cpvd, Analyzer); + } + } + break; + } + case attr::AcquiredAfter: { + const auto *A = cast<AcquiredAfterAttr>(At); + + // Read exprs from the attribute, and add them to BeforeVect. + for (const auto *Arg : A->args()) { + CapabilityExpr Cp = + Analyzer.SxBuilder.translateAttrExpr(Arg, nullptr); + if (const ValueDecl *ArgVd = Cp.valueDecl()) { + // Get entry for mutex listed in attribute + BeforeInfo *ArgInfo = getBeforeInfoForDecl(ArgVd, Analyzer); + ArgInfo->Vect.push_back(Vd); + } + } + break; + } + default: + break; + } + } + + return Info; +} + +BeforeSet::BeforeInfo * +BeforeSet::getBeforeInfoForDecl(const ValueDecl *Vd, + ThreadSafetyAnalyzer &Analyzer) { + auto It = BMap.find(Vd); + BeforeInfo *Info = nullptr; + if (It == BMap.end()) + Info = insertAttrExprs(Vd, Analyzer); + else + Info = It->second.get(); + assert(Info && "BMap contained nullptr?"); + return Info; +} + +/// Return true if any mutexes in FSet are in the acquired_before set of Vd. +void BeforeSet::checkBeforeAfter(const ValueDecl* StartVd, + const FactSet& FSet, + ThreadSafetyAnalyzer& Analyzer, + SourceLocation Loc, StringRef CapKind) { + SmallVector<BeforeInfo*, 8> InfoVect; + + // Do a depth-first traversal of Vd. + // Return true if there are cycles. + std::function<bool (const ValueDecl*)> traverse = [&](const ValueDecl* Vd) { + if (!Vd) + return false; + + BeforeSet::BeforeInfo *Info = getBeforeInfoForDecl(Vd, Analyzer); + + if (Info->Visited == 1) + return true; + + if (Info->Visited == 2) + return false; + + if (Info->Vect.empty()) + return false; + + InfoVect.push_back(Info); + Info->Visited = 1; + for (const auto *Vdb : Info->Vect) { + // Exclude mutexes in our immediate before set. + if (FSet.containsMutexDecl(Analyzer.FactMan, Vdb)) { + StringRef L1 = StartVd->getName(); + StringRef L2 = Vdb->getName(); + Analyzer.Handler.handleLockAcquiredBefore(CapKind, L1, L2, Loc); + } + // Transitively search other before sets, and warn on cycles. + if (traverse(Vdb)) { + if (CycMap.find(Vd) == CycMap.end()) { + CycMap.insert(std::make_pair(Vd, true)); + StringRef L1 = Vd->getName(); + Analyzer.Handler.handleBeforeAfterCycle(L1, Vd->getLocation()); + } + } + } + Info->Visited = 2; + return false; + }; + + traverse(StartVd); + + for (auto *Info : InfoVect) + Info->Visited = 0; +} + +/// Gets the value decl pointer from DeclRefExprs or MemberExprs. +static const ValueDecl *getValueDecl(const Expr *Exp) { + if (const auto *CE = dyn_cast<ImplicitCastExpr>(Exp)) + return getValueDecl(CE->getSubExpr()); + + if (const auto *DR = dyn_cast<DeclRefExpr>(Exp)) + return DR->getDecl(); + + if (const auto *ME = dyn_cast<MemberExpr>(Exp)) + return ME->getMemberDecl(); + + return nullptr; +} + +namespace { + +template <typename Ty> +class has_arg_iterator_range { + using yes = char[1]; + using no = char[2]; + + template <typename Inner> + static yes& test(Inner *I, decltype(I->args()) * = nullptr); + + template <typename> + static no& test(...); + +public: + static const bool value = sizeof(test<Ty>(nullptr)) == sizeof(yes); +}; + +} // namespace + +static StringRef ClassifyDiagnostic(const CapabilityAttr *A) { + return A->getName(); +} + +static StringRef ClassifyDiagnostic(QualType VDT) { + // We need to look at the declaration of the type of the value to determine + // which it is. The type should either be a record or a typedef, or a pointer + // or reference thereof. + if (const auto *RT = VDT->getAs<RecordType>()) { + if (const auto *RD = RT->getDecl()) + if (const auto *CA = RD->getAttr<CapabilityAttr>()) + return ClassifyDiagnostic(CA); + } else if (const auto *TT = VDT->getAs<TypedefType>()) { + if (const auto *TD = TT->getDecl()) + if (const auto *CA = TD->getAttr<CapabilityAttr>()) + return ClassifyDiagnostic(CA); + } else if (VDT->isPointerType() || VDT->isReferenceType()) + return ClassifyDiagnostic(VDT->getPointeeType()); + + return "mutex"; +} + +static StringRef ClassifyDiagnostic(const ValueDecl *VD) { + assert(VD && "No ValueDecl passed"); + + // The ValueDecl is the declaration of a mutex or role (hopefully). + return ClassifyDiagnostic(VD->getType()); +} + +template <typename AttrTy> +static typename std::enable_if<!has_arg_iterator_range<AttrTy>::value, + StringRef>::type +ClassifyDiagnostic(const AttrTy *A) { + if (const ValueDecl *VD = getValueDecl(A->getArg())) + return ClassifyDiagnostic(VD); + return "mutex"; +} + +template <typename AttrTy> +static typename std::enable_if<has_arg_iterator_range<AttrTy>::value, + StringRef>::type +ClassifyDiagnostic(const AttrTy *A) { + for (const auto *Arg : A->args()) { + if (const ValueDecl *VD = getValueDecl(Arg)) + return ClassifyDiagnostic(VD); + } + return "mutex"; +} + +bool ThreadSafetyAnalyzer::inCurrentScope(const CapabilityExpr &CapE) { + if (!CurrentMethod) + return false; + if (const auto *P = dyn_cast_or_null<til::Project>(CapE.sexpr())) { + const auto *VD = P->clangDecl(); + if (VD) + return VD->getDeclContext() == CurrentMethod->getDeclContext(); + } + return false; +} + +/// Add a new lock to the lockset, warning if the lock is already there. +/// \param ReqAttr -- true if this is part of an initial Requires attribute. +void ThreadSafetyAnalyzer::addLock(FactSet &FSet, + std::unique_ptr<FactEntry> Entry, + StringRef DiagKind, bool ReqAttr) { + if (Entry->shouldIgnore()) + return; + + if (!ReqAttr && !Entry->negative()) { + // look for the negative capability, and remove it from the fact set. + CapabilityExpr NegC = !*Entry; + const FactEntry *Nen = FSet.findLock(FactMan, NegC); + if (Nen) { + FSet.removeLock(FactMan, NegC); + } + else { + if (inCurrentScope(*Entry) && !Entry->asserted()) + Handler.handleNegativeNotHeld(DiagKind, Entry->toString(), + NegC.toString(), Entry->loc()); + } + } + + // Check before/after constraints + if (Handler.issueBetaWarnings() && + !Entry->asserted() && !Entry->declared()) { + GlobalBeforeSet->checkBeforeAfter(Entry->valueDecl(), FSet, *this, + Entry->loc(), DiagKind); + } + + // FIXME: Don't always warn when we have support for reentrant locks. + if (const FactEntry *Cp = FSet.findLock(FactMan, *Entry)) { + if (!Entry->asserted()) + Cp->handleLock(FSet, FactMan, *Entry, Handler, DiagKind); + } else { + FSet.addLock(FactMan, std::move(Entry)); + } +} + +/// Remove a lock from the lockset, warning if the lock is not there. +/// \param UnlockLoc The source location of the unlock (only used in error msg) +void ThreadSafetyAnalyzer::removeLock(FactSet &FSet, const CapabilityExpr &Cp, + SourceLocation UnlockLoc, + bool FullyRemove, LockKind ReceivedKind, + StringRef DiagKind) { + if (Cp.shouldIgnore()) + return; + + const FactEntry *LDat = FSet.findLock(FactMan, Cp); + if (!LDat) { + 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->kind() != ReceivedKind) { + Handler.handleIncorrectUnlockKind(DiagKind, Cp.toString(), LDat->kind(), + ReceivedKind, LDat->loc(), UnlockLoc); + } + + LDat->handleUnlock(FSet, FactMan, Cp, UnlockLoc, FullyRemove, Handler, + DiagKind); +} + +/// Extract the list of mutexIDs from the attribute on an expression, +/// and push them onto Mtxs, discarding any duplicates. +template <typename AttrType> +void ThreadSafetyAnalyzer::getMutexIDs(CapExprSet &Mtxs, AttrType *Attr, + const Expr *Exp, const NamedDecl *D, + VarDecl *SelfDecl) { + if (Attr->args_size() == 0) { + // The mutex held is the "this" object. + CapabilityExpr Cp = SxBuilder.translateAttrExpr(nullptr, D, Exp, SelfDecl); + if (Cp.isInvalid()) { + warnInvalidLock(Handler, nullptr, D, Exp, ClassifyDiagnostic(Attr)); + return; + } + //else + if (!Cp.shouldIgnore()) + Mtxs.push_back_nodup(Cp); + return; + } + + for (const auto *Arg : Attr->args()) { + CapabilityExpr Cp = SxBuilder.translateAttrExpr(Arg, D, Exp, SelfDecl); + if (Cp.isInvalid()) { + warnInvalidLock(Handler, nullptr, D, Exp, ClassifyDiagnostic(Attr)); + continue; + } + //else + if (!Cp.shouldIgnore()) + Mtxs.push_back_nodup(Cp); + } +} + +/// Extract the list of mutexIDs from a trylock attribute. If the +/// trylock applies to the given edge, then push them onto Mtxs, discarding +/// any duplicates. +template <class AttrType> +void ThreadSafetyAnalyzer::getMutexIDs(CapExprSet &Mtxs, AttrType *Attr, + const Expr *Exp, const NamedDecl *D, + const CFGBlock *PredBlock, + const CFGBlock *CurrBlock, + Expr *BrE, bool Neg) { + // Find out which branch has the lock + bool branch = false; + if (const auto *BLE = dyn_cast_or_null<CXXBoolLiteralExpr>(BrE)) + branch = BLE->getValue(); + else if (const auto *ILE = dyn_cast_or_null<IntegerLiteral>(BrE)) + branch = ILE->getValue().getBoolValue(); + + int branchnum = branch ? 0 : 1; + if (Neg) + branchnum = !branchnum; + + // If we've taken the trylock branch, then add the lock + int i = 0; + for (CFGBlock::const_succ_iterator SI = PredBlock->succ_begin(), + SE = PredBlock->succ_end(); SI != SE && i < 2; ++SI, ++i) { + if (*SI == CurrBlock && i == branchnum) + getMutexIDs(Mtxs, Attr, Exp, D); + } +} + +static bool getStaticBooleanValue(Expr *E, bool &TCond) { + if (isa<CXXNullPtrLiteralExpr>(E) || isa<GNUNullExpr>(E)) { + TCond = false; + return true; + } else if (const auto *BLE = dyn_cast<CXXBoolLiteralExpr>(E)) { + TCond = BLE->getValue(); + return true; + } else if (const auto *ILE = dyn_cast<IntegerLiteral>(E)) { + TCond = ILE->getValue().getBoolValue(); + return true; + } else if (auto *CE = dyn_cast<ImplicitCastExpr>(E)) + return getStaticBooleanValue(CE->getSubExpr(), TCond); + return false; +} + +// If Cond can be traced back to a function call, return the call expression. +// The negate variable should be called with false, and will be set to true +// if the function call is negated, e.g. if (!mu.tryLock(...)) +const CallExpr* ThreadSafetyAnalyzer::getTrylockCallExpr(const Stmt *Cond, + LocalVarContext C, + bool &Negate) { + if (!Cond) + return nullptr; + + if (const auto *CallExp = dyn_cast<CallExpr>(Cond)) { + if (CallExp->getBuiltinCallee() == Builtin::BI__builtin_expect) + return getTrylockCallExpr(CallExp->getArg(0), C, Negate); + return CallExp; + } + else if (const auto *PE = dyn_cast<ParenExpr>(Cond)) + return getTrylockCallExpr(PE->getSubExpr(), C, Negate); + else if (const auto *CE = dyn_cast<ImplicitCastExpr>(Cond)) + return getTrylockCallExpr(CE->getSubExpr(), C, Negate); + else if (const auto *FE = dyn_cast<FullExpr>(Cond)) + return getTrylockCallExpr(FE->getSubExpr(), C, Negate); + else if (const auto *DRE = dyn_cast<DeclRefExpr>(Cond)) { + const Expr *E = LocalVarMap.lookupExpr(DRE->getDecl(), C); + return getTrylockCallExpr(E, C, Negate); + } + else if (const auto *UOP = dyn_cast<UnaryOperator>(Cond)) { + if (UOP->getOpcode() == UO_LNot) { + Negate = !Negate; + return getTrylockCallExpr(UOP->getSubExpr(), C, Negate); + } + return nullptr; + } + else if (const auto *BOP = dyn_cast<BinaryOperator>(Cond)) { + if (BOP->getOpcode() == BO_EQ || BOP->getOpcode() == BO_NE) { + if (BOP->getOpcode() == BO_NE) + Negate = !Negate; + + bool TCond = false; + if (getStaticBooleanValue(BOP->getRHS(), TCond)) { + if (!TCond) Negate = !Negate; + return getTrylockCallExpr(BOP->getLHS(), C, Negate); + } + TCond = false; + if (getStaticBooleanValue(BOP->getLHS(), TCond)) { + if (!TCond) Negate = !Negate; + return getTrylockCallExpr(BOP->getRHS(), C, Negate); + } + return nullptr; + } + if (BOP->getOpcode() == BO_LAnd) { + // LHS must have been evaluated in a different block. + return getTrylockCallExpr(BOP->getRHS(), C, Negate); + } + if (BOP->getOpcode() == BO_LOr) + return getTrylockCallExpr(BOP->getRHS(), C, Negate); + return nullptr; + } else if (const auto *COP = dyn_cast<ConditionalOperator>(Cond)) { + bool TCond, FCond; + if (getStaticBooleanValue(COP->getTrueExpr(), TCond) && + getStaticBooleanValue(COP->getFalseExpr(), FCond)) { + if (TCond && !FCond) + return getTrylockCallExpr(COP->getCond(), C, Negate); + if (!TCond && FCond) { + Negate = !Negate; + return getTrylockCallExpr(COP->getCond(), C, Negate); + } + } + } + return nullptr; +} + +/// Find the lockset that holds on the edge between PredBlock +/// and CurrBlock. The edge set is the exit set of PredBlock (passed +/// as the ExitSet parameter) plus any trylocks, which are conditionally held. +void ThreadSafetyAnalyzer::getEdgeLockset(FactSet& Result, + const FactSet &ExitSet, + const CFGBlock *PredBlock, + const CFGBlock *CurrBlock) { + Result = ExitSet; + + const Stmt *Cond = PredBlock->getTerminatorCondition(); + // We don't acquire try-locks on ?: branches, only when its result is used. + if (!Cond || isa<ConditionalOperator>(PredBlock->getTerminatorStmt())) + return; + + bool Negate = false; + const CFGBlockInfo *PredBlockInfo = &BlockInfo[PredBlock->getBlockID()]; + const LocalVarContext &LVarCtx = PredBlockInfo->ExitContext; + StringRef CapDiagKind = "mutex"; + + const auto *Exp = getTrylockCallExpr(Cond, LVarCtx, Negate); + if (!Exp) + return; + + auto *FunDecl = dyn_cast_or_null<NamedDecl>(Exp->getCalleeDecl()); + if(!FunDecl || !FunDecl->hasAttrs()) + return; + + CapExprSet ExclusiveLocksToAdd; + CapExprSet SharedLocksToAdd; + + // If the condition is a call to a Trylock function, then grab the attributes + for (const auto *Attr : FunDecl->attrs()) { + switch (Attr->getKind()) { + case attr::TryAcquireCapability: { + auto *A = cast<TryAcquireCapabilityAttr>(Attr); + getMutexIDs(A->isShared() ? SharedLocksToAdd : ExclusiveLocksToAdd, A, + Exp, FunDecl, PredBlock, CurrBlock, A->getSuccessValue(), + Negate); + CapDiagKind = ClassifyDiagnostic(A); + break; + }; + case attr::ExclusiveTrylockFunction: { + const auto *A = cast<ExclusiveTrylockFunctionAttr>(Attr); + getMutexIDs(ExclusiveLocksToAdd, A, Exp, FunDecl, + PredBlock, CurrBlock, A->getSuccessValue(), Negate); + CapDiagKind = ClassifyDiagnostic(A); + break; + } + case attr::SharedTrylockFunction: { + const auto *A = cast<SharedTrylockFunctionAttr>(Attr); + getMutexIDs(SharedLocksToAdd, A, Exp, FunDecl, + PredBlock, CurrBlock, A->getSuccessValue(), Negate); + CapDiagKind = ClassifyDiagnostic(A); + break; + } + default: + break; + } + } + + // Add and remove locks. + SourceLocation Loc = Exp->getExprLoc(); + for (const auto &ExclusiveLockToAdd : ExclusiveLocksToAdd) + addLock(Result, std::make_unique<LockableFactEntry>(ExclusiveLockToAdd, + LK_Exclusive, Loc), + CapDiagKind); + for (const auto &SharedLockToAdd : SharedLocksToAdd) + addLock(Result, std::make_unique<LockableFactEntry>(SharedLockToAdd, + LK_Shared, Loc), + CapDiagKind); +} + +namespace { + +/// We use this class to visit different types of expressions in +/// CFGBlocks, and build up the lockset. +/// An expression may cause us to add or remove locks from the lockset, or else +/// output error messages related to missing locks. +/// FIXME: In future, we may be able to not inherit from a visitor. +class BuildLockset : public ConstStmtVisitor<BuildLockset> { + friend class ThreadSafetyAnalyzer; + + ThreadSafetyAnalyzer *Analyzer; + FactSet FSet; + LocalVariableMap::Context LVarCtx; + unsigned CtxIndex; + + // helper functions + void warnIfMutexNotHeld(const NamedDecl *D, const Expr *Exp, AccessKind AK, + Expr *MutexExp, ProtectedOperationKind POK, + StringRef DiagKind, SourceLocation Loc); + void warnIfMutexHeld(const NamedDecl *D, const Expr *Exp, Expr *MutexExp, + StringRef DiagKind); + + void checkAccess(const Expr *Exp, AccessKind AK, + ProtectedOperationKind POK = POK_VarAccess); + void checkPtAccess(const Expr *Exp, AccessKind AK, + ProtectedOperationKind POK = POK_VarAccess); + + void handleCall(const Expr *Exp, const NamedDecl *D, VarDecl *VD = nullptr); + void examineArguments(const FunctionDecl *FD, + CallExpr::const_arg_iterator ArgBegin, + CallExpr::const_arg_iterator ArgEnd, + bool SkipFirstParam = false); + +public: + BuildLockset(ThreadSafetyAnalyzer *Anlzr, CFGBlockInfo &Info) + : ConstStmtVisitor<BuildLockset>(), Analyzer(Anlzr), FSet(Info.EntrySet), + LVarCtx(Info.EntryContext), CtxIndex(Info.EntryIndex) {} + + void VisitUnaryOperator(const UnaryOperator *UO); + void VisitBinaryOperator(const BinaryOperator *BO); + void VisitCastExpr(const CastExpr *CE); + void VisitCallExpr(const CallExpr *Exp); + void VisitCXXConstructExpr(const CXXConstructExpr *Exp); + void VisitDeclStmt(const DeclStmt *S); +}; + +} // namespace + +/// 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, + AccessKind AK, Expr *MutexExp, + ProtectedOperationKind POK, + StringRef DiagKind, SourceLocation Loc) { + LockKind LK = getLockKindFromAccessKind(AK); + + CapabilityExpr Cp = Analyzer->SxBuilder.translateAttrExpr(MutexExp, D, Exp); + if (Cp.isInvalid()) { + warnInvalidLock(Analyzer->Handler, MutexExp, D, Exp, DiagKind); + return; + } else if (Cp.shouldIgnore()) { + return; + } + + if (Cp.negative()) { + // Negative capabilities act like locks excluded + const FactEntry *LDat = FSet.findLock(Analyzer->FactMan, !Cp); + if (LDat) { + Analyzer->Handler.handleFunExcludesLock( + DiagKind, D->getNameAsString(), (!Cp).toString(), Loc); + return; + } + + // If this does not refer to a negative capability in the same class, + // then stop here. + if (!Analyzer->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, Loc); + } + return; + } + + const FactEntry *LDat = FSet.findLockUniv(Analyzer->FactMan, Cp); + bool NoError = true; + if (!LDat) { + // No exact match found. Look for a partial match. + LDat = FSet.findPartialMatch(Analyzer->FactMan, Cp); + if (LDat) { + // Warn that there's no precise match. + std::string PartMatchStr = LDat->toString(); + StringRef PartMatchName(PartMatchStr); + Analyzer->Handler.handleMutexNotHeld(DiagKind, D, POK, Cp.toString(), + LK, Loc, &PartMatchName); + } else { + // Warn that there's no match at all. + Analyzer->Handler.handleMutexNotHeld(DiagKind, D, POK, Cp.toString(), + LK, Loc); + } + NoError = false; + } + // Make sure the mutex we found is the right kind. + if (NoError && LDat && !LDat->isAtLeast(LK)) { + Analyzer->Handler.handleMutexNotHeld(DiagKind, D, POK, Cp.toString(), + LK, Loc); + } +} + +/// Warn if the LSet contains the given lock. +void BuildLockset::warnIfMutexHeld(const NamedDecl *D, const Expr *Exp, + Expr *MutexExp, StringRef 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; + } + + const FactEntry *LDat = FSet.findLock(Analyzer->FactMan, Cp); + if (LDat) { + Analyzer->Handler.handleFunExcludesLock( + DiagKind, D->getNameAsString(), Cp.toString(), Exp->getExprLoc()); + } +} + +/// Checks guarded_by and pt_guarded_by attributes. +/// Whenever we identify an access (read or write) to a DeclRefExpr that is +/// marked with guarded_by, we must ensure the appropriate mutexes are held. +/// Similarly, we check if the access is to an expression that dereferences +/// a pointer marked with pt_guarded_by. +void BuildLockset::checkAccess(const Expr *Exp, AccessKind AK, + ProtectedOperationKind POK) { + Exp = Exp->IgnoreImplicit()->IgnoreParenCasts(); + + SourceLocation Loc = Exp->getExprLoc(); + + // Local variables of reference type cannot be re-assigned; + // map them to their initializer. + while (const auto *DRE = dyn_cast<DeclRefExpr>(Exp)) { + const auto *VD = dyn_cast<VarDecl>(DRE->getDecl()->getCanonicalDecl()); + if (VD && VD->isLocalVarDecl() && VD->getType()->isReferenceType()) { + if (const auto *E = VD->getInit()) { + // Guard against self-initialization. e.g., int &i = i; + if (E == Exp) + break; + Exp = E; + continue; + } + } + break; + } + + if (const auto *UO = dyn_cast<UnaryOperator>(Exp)) { + // For dereferences + if (UO->getOpcode() == UO_Deref) + checkPtAccess(UO->getSubExpr(), AK, POK); + return; + } + + if (const auto *AE = dyn_cast<ArraySubscriptExpr>(Exp)) { + checkPtAccess(AE->getLHS(), AK, POK); + return; + } + + if (const auto *ME = dyn_cast<MemberExpr>(Exp)) { + if (ME->isArrow()) + checkPtAccess(ME->getBase(), AK, POK); + else + checkAccess(ME->getBase(), AK, POK); + } + + const ValueDecl *D = getValueDecl(Exp); + if (!D || !D->hasAttrs()) + return; + + if (D->hasAttr<GuardedVarAttr>() && FSet.isEmpty(Analyzer->FactMan)) { + Analyzer->Handler.handleNoMutexHeld("mutex", D, POK, AK, Loc); + } + + for (const auto *I : D->specific_attrs<GuardedByAttr>()) + warnIfMutexNotHeld(D, Exp, AK, I->getArg(), POK, + ClassifyDiagnostic(I), Loc); +} + +/// Checks pt_guarded_by and pt_guarded_var attributes. +/// POK is the same operationKind that was passed to checkAccess. +void BuildLockset::checkPtAccess(const Expr *Exp, AccessKind AK, + ProtectedOperationKind POK) { + while (true) { + if (const auto *PE = dyn_cast<ParenExpr>(Exp)) { + Exp = PE->getSubExpr(); + continue; + } + if (const auto *CE = dyn_cast<CastExpr>(Exp)) { + if (CE->getCastKind() == CK_ArrayToPointerDecay) { + // If it's an actual array, and not a pointer, then it's elements + // are protected by GUARDED_BY, not PT_GUARDED_BY; + checkAccess(CE->getSubExpr(), AK, POK); + return; + } + Exp = CE->getSubExpr(); + continue; + } + break; + } + + // Pass by reference warnings are under a different flag. + ProtectedOperationKind PtPOK = POK_VarDereference; + if (POK == POK_PassByRef) PtPOK = POK_PtPassByRef; + + const ValueDecl *D = getValueDecl(Exp); + if (!D || !D->hasAttrs()) + return; + + if (D->hasAttr<PtGuardedVarAttr>() && FSet.isEmpty(Analyzer->FactMan)) + Analyzer->Handler.handleNoMutexHeld("mutex", D, PtPOK, AK, + Exp->getExprLoc()); + + for (auto const *I : D->specific_attrs<PtGuardedByAttr>()) + warnIfMutexNotHeld(D, Exp, AK, I->getArg(), PtPOK, + ClassifyDiagnostic(I), Exp->getExprLoc()); +} + +/// Process a function call, method call, constructor call, +/// or destructor call. This involves looking at the attributes on the +/// corresponding function/method/constructor/destructor, issuing warnings, +/// and updating the locksets accordingly. +/// +/// FIXME: For classes annotated with one of the guarded annotations, we need +/// to treat const method calls as reads and non-const method calls as writes, +/// and check that the appropriate locks are held. Non-const method calls with +/// the same signature as const method calls can be also treated as reads. +/// +void BuildLockset::handleCall(const Expr *Exp, const NamedDecl *D, + VarDecl *VD) { + SourceLocation Loc = Exp->getExprLoc(); + CapExprSet ExclusiveLocksToAdd, SharedLocksToAdd; + CapExprSet ExclusiveLocksToRemove, SharedLocksToRemove, GenericLocksToRemove; + CapExprSet ScopedExclusiveReqs, ScopedSharedReqs; + StringRef CapDiagKind = "mutex"; + + // Figure out if we're constructing an object of scoped lockable class + bool isScopedVar = false; + if (VD) { + if (const auto *CD = dyn_cast<const CXXConstructorDecl>(D)) { + const CXXRecordDecl* PD = CD->getParent(); + if (PD && PD->hasAttr<ScopedLockableAttr>()) + isScopedVar = true; + } + } + + for(const Attr *At : D->attrs()) { + switch (At->getKind()) { + // When we encounter a lock function, we need to add the lock to our + // lockset. + case attr::AcquireCapability: { + const auto *A = cast<AcquireCapabilityAttr>(At); + Analyzer->getMutexIDs(A->isShared() ? SharedLocksToAdd + : ExclusiveLocksToAdd, + A, Exp, D, VD); + + CapDiagKind = ClassifyDiagnostic(A); + break; + } + + // An assert will add a lock to the lockset, but will not generate + // a warning if it is already there, and will not generate a warning + // if it is not removed. + case attr::AssertExclusiveLock: { + const auto *A = cast<AssertExclusiveLockAttr>(At); + + CapExprSet AssertLocks; + Analyzer->getMutexIDs(AssertLocks, A, Exp, D, VD); + for (const auto &AssertLock : AssertLocks) + Analyzer->addLock(FSet, + std::make_unique<LockableFactEntry>( + AssertLock, LK_Exclusive, Loc, false, true), + ClassifyDiagnostic(A)); + break; + } + case attr::AssertSharedLock: { + const auto *A = cast<AssertSharedLockAttr>(At); + + CapExprSet AssertLocks; + Analyzer->getMutexIDs(AssertLocks, A, Exp, D, VD); + for (const auto &AssertLock : AssertLocks) + Analyzer->addLock(FSet, + std::make_unique<LockableFactEntry>( + AssertLock, LK_Shared, Loc, false, true), + ClassifyDiagnostic(A)); + break; + } + + case attr::AssertCapability: { + const auto *A = cast<AssertCapabilityAttr>(At); + CapExprSet AssertLocks; + Analyzer->getMutexIDs(AssertLocks, A, Exp, D, VD); + for (const auto &AssertLock : AssertLocks) + Analyzer->addLock(FSet, + std::make_unique<LockableFactEntry>( + AssertLock, + A->isShared() ? LK_Shared : LK_Exclusive, Loc, + false, true), + ClassifyDiagnostic(A)); + break; + } + + // When we encounter an unlock function, we need to remove unlocked + // mutexes from the lockset, and flag a warning if they are not there. + case attr::ReleaseCapability: { + const auto *A = cast<ReleaseCapabilityAttr>(At); + if (A->isGeneric()) + Analyzer->getMutexIDs(GenericLocksToRemove, A, Exp, D, VD); + else if (A->isShared()) + Analyzer->getMutexIDs(SharedLocksToRemove, A, Exp, D, VD); + else + Analyzer->getMutexIDs(ExclusiveLocksToRemove, A, Exp, D, VD); + + CapDiagKind = ClassifyDiagnostic(A); + break; + } + + case attr::RequiresCapability: { + const auto *A = cast<RequiresCapabilityAttr>(At); + for (auto *Arg : A->args()) { + warnIfMutexNotHeld(D, Exp, A->isShared() ? AK_Read : AK_Written, Arg, + POK_FunctionCall, ClassifyDiagnostic(A), + Exp->getExprLoc()); + // use for adopting a lock + if (isScopedVar) { + Analyzer->getMutexIDs(A->isShared() ? ScopedSharedReqs + : ScopedExclusiveReqs, + A, Exp, D, VD); + } + } + break; + } + + case attr::LocksExcluded: { + const auto *A = cast<LocksExcludedAttr>(At); + for (auto *Arg : A->args()) + warnIfMutexHeld(D, Exp, Arg, ClassifyDiagnostic(A)); + break; + } + + // Ignore attributes unrelated to thread-safety + default: + break; + } + } + + // Remove locks first to allow lock upgrading/downgrading. + // FIXME -- should only fully remove if the attribute refers to 'this'. + bool Dtor = isa<CXXDestructorDecl>(D); + for (const auto &M : ExclusiveLocksToRemove) + Analyzer->removeLock(FSet, M, Loc, Dtor, LK_Exclusive, CapDiagKind); + for (const auto &M : SharedLocksToRemove) + Analyzer->removeLock(FSet, M, Loc, Dtor, LK_Shared, CapDiagKind); + for (const auto &M : GenericLocksToRemove) + Analyzer->removeLock(FSet, M, Loc, Dtor, LK_Generic, CapDiagKind); + + // Add locks. + for (const auto &M : ExclusiveLocksToAdd) + Analyzer->addLock(FSet, std::make_unique<LockableFactEntry>( + M, LK_Exclusive, Loc, isScopedVar), + CapDiagKind); + for (const auto &M : SharedLocksToAdd) + Analyzer->addLock(FSet, std::make_unique<LockableFactEntry>( + M, LK_Shared, Loc, isScopedVar), + CapDiagKind); + + if (isScopedVar) { + // Add the managing object as a dummy mutex, mapped to the underlying mutex. + SourceLocation MLoc = VD->getLocation(); + DeclRefExpr DRE(VD->getASTContext(), VD, false, VD->getType(), VK_LValue, + VD->getLocation()); + // FIXME: does this store a pointer to DRE? + CapabilityExpr Scp = Analyzer->SxBuilder.translateAttrExpr(&DRE, nullptr); + + auto ScopedEntry = std::make_unique<ScopedLockableFactEntry>(Scp, MLoc); + for (const auto &M : ExclusiveLocksToAdd) + ScopedEntry->addExclusiveLock(M); + for (const auto &M : ScopedExclusiveReqs) + ScopedEntry->addExclusiveLock(M); + for (const auto &M : SharedLocksToAdd) + ScopedEntry->addSharedLock(M); + for (const auto &M : ScopedSharedReqs) + ScopedEntry->addSharedLock(M); + for (const auto &M : ExclusiveLocksToRemove) + ScopedEntry->addExclusiveUnlock(M); + for (const auto &M : SharedLocksToRemove) + ScopedEntry->addSharedUnlock(M); + Analyzer->addLock(FSet, std::move(ScopedEntry), CapDiagKind); + } +} + +/// For unary operations which read and write a variable, we need to +/// check whether we hold any required mutexes. Reads are checked in +/// VisitCastExpr. +void BuildLockset::VisitUnaryOperator(const UnaryOperator *UO) { + switch (UO->getOpcode()) { + case UO_PostDec: + case UO_PostInc: + case UO_PreDec: + case UO_PreInc: + checkAccess(UO->getSubExpr(), AK_Written); + break; + default: + break; + } +} + +/// For binary operations which assign to a variable (writes), we need to check +/// whether we hold any required mutexes. +/// FIXME: Deal with non-primitive types. +void BuildLockset::VisitBinaryOperator(const BinaryOperator *BO) { + if (!BO->isAssignmentOp()) + return; + + // adjust the context + LVarCtx = Analyzer->LocalVarMap.getNextContext(CtxIndex, BO, LVarCtx); + + checkAccess(BO->getLHS(), AK_Written); +} + +/// Whenever we do an LValue to Rvalue cast, we are reading a variable and +/// need to ensure we hold any required mutexes. +/// FIXME: Deal with non-primitive types. +void BuildLockset::VisitCastExpr(const CastExpr *CE) { + if (CE->getCastKind() != CK_LValueToRValue) + return; + checkAccess(CE->getSubExpr(), AK_Read); +} + +void BuildLockset::examineArguments(const FunctionDecl *FD, + CallExpr::const_arg_iterator ArgBegin, + CallExpr::const_arg_iterator ArgEnd, + bool SkipFirstParam) { + // Currently we can't do anything if we don't know the function declaration. + if (!FD) + return; + + // NO_THREAD_SAFETY_ANALYSIS does double duty here. Normally it + // only turns off checking within the body of a function, but we also + // use it to turn off checking in arguments to the function. This + // could result in some false negatives, but the alternative is to + // create yet another attribute. + if (FD->hasAttr<NoThreadSafetyAnalysisAttr>()) + return; + + const ArrayRef<ParmVarDecl *> Params = FD->parameters(); + auto Param = Params.begin(); + if (SkipFirstParam) + ++Param; + + // There can be default arguments, so we stop when one iterator is at end(). + for (auto Arg = ArgBegin; Param != Params.end() && Arg != ArgEnd; + ++Param, ++Arg) { + QualType Qt = (*Param)->getType(); + if (Qt->isReferenceType()) + checkAccess(*Arg, AK_Read, POK_PassByRef); + } +} + +void BuildLockset::VisitCallExpr(const CallExpr *Exp) { + if (const auto *CE = dyn_cast<CXXMemberCallExpr>(Exp)) { + const auto *ME = dyn_cast<MemberExpr>(CE->getCallee()); + // ME can be null when calling a method pointer + const CXXMethodDecl *MD = CE->getMethodDecl(); + + if (ME && MD) { + if (ME->isArrow()) { + if (MD->isConst()) + checkPtAccess(CE->getImplicitObjectArgument(), AK_Read); + else // FIXME -- should be AK_Written + checkPtAccess(CE->getImplicitObjectArgument(), AK_Read); + } else { + if (MD->isConst()) + checkAccess(CE->getImplicitObjectArgument(), AK_Read); + else // FIXME -- should be AK_Written + checkAccess(CE->getImplicitObjectArgument(), AK_Read); + } + } + + examineArguments(CE->getDirectCallee(), CE->arg_begin(), CE->arg_end()); + } else if (const auto *OE = dyn_cast<CXXOperatorCallExpr>(Exp)) { + auto OEop = OE->getOperator(); + switch (OEop) { + case OO_Equal: { + const Expr *Target = OE->getArg(0); + const Expr *Source = OE->getArg(1); + checkAccess(Target, AK_Written); + checkAccess(Source, AK_Read); + break; + } + case OO_Star: + case OO_Arrow: + case OO_Subscript: + if (!(OEop == OO_Star && OE->getNumArgs() > 1)) { + // Grrr. operator* can be multiplication... + checkPtAccess(OE->getArg(0), AK_Read); + } + LLVM_FALLTHROUGH; + default: { + // TODO: get rid of this, and rely on pass-by-ref instead. + const Expr *Obj = OE->getArg(0); + checkAccess(Obj, AK_Read); + // Check the remaining arguments. For method operators, the first + // argument is the implicit self argument, and doesn't appear in the + // FunctionDecl, but for non-methods it does. + const FunctionDecl *FD = OE->getDirectCallee(); + examineArguments(FD, std::next(OE->arg_begin()), OE->arg_end(), + /*SkipFirstParam*/ !isa<CXXMethodDecl>(FD)); + break; + } + } + } else { + examineArguments(Exp->getDirectCallee(), Exp->arg_begin(), Exp->arg_end()); + } + + auto *D = dyn_cast_or_null<NamedDecl>(Exp->getCalleeDecl()); + if(!D || !D->hasAttrs()) + return; + handleCall(Exp, D); +} + +void BuildLockset::VisitCXXConstructExpr(const CXXConstructExpr *Exp) { + const CXXConstructorDecl *D = Exp->getConstructor(); + if (D && D->isCopyConstructor()) { + const Expr* Source = Exp->getArg(0); + checkAccess(Source, AK_Read); + } else { + examineArguments(D, Exp->arg_begin(), Exp->arg_end()); + } +} + +static CXXConstructorDecl * +findConstructorForByValueReturn(const CXXRecordDecl *RD) { + // Prefer a move constructor over a copy constructor. If there's more than + // one copy constructor or more than one move constructor, we arbitrarily + // pick the first declared such constructor rather than trying to guess which + // one is more appropriate. + CXXConstructorDecl *CopyCtor = nullptr; + for (auto *Ctor : RD->ctors()) { + if (Ctor->isDeleted()) + continue; + if (Ctor->isMoveConstructor()) + return Ctor; + if (!CopyCtor && Ctor->isCopyConstructor()) + CopyCtor = Ctor; + } + return CopyCtor; +} + +static Expr *buildFakeCtorCall(CXXConstructorDecl *CD, ArrayRef<Expr *> Args, + SourceLocation Loc) { + ASTContext &Ctx = CD->getASTContext(); + return CXXConstructExpr::Create(Ctx, Ctx.getRecordType(CD->getParent()), Loc, + CD, true, Args, false, false, false, false, + CXXConstructExpr::CK_Complete, + SourceRange(Loc, Loc)); +} + +void BuildLockset::VisitDeclStmt(const DeclStmt *S) { + // adjust the context + LVarCtx = Analyzer->LocalVarMap.getNextContext(CtxIndex, S, LVarCtx); + + for (auto *D : S->getDeclGroup()) { + if (auto *VD = dyn_cast_or_null<VarDecl>(D)) { + Expr *E = VD->getInit(); + if (!E) + continue; + E = E->IgnoreParens(); + + // handle constructors that involve temporaries + if (auto *EWC = dyn_cast<ExprWithCleanups>(E)) + E = EWC->getSubExpr(); + if (auto *BTE = dyn_cast<CXXBindTemporaryExpr>(E)) + E = BTE->getSubExpr(); + + if (const auto *CE = dyn_cast<CXXConstructExpr>(E)) { + const auto *CtorD = dyn_cast_or_null<NamedDecl>(CE->getConstructor()); + if (!CtorD || !CtorD->hasAttrs()) + continue; + handleCall(E, CtorD, VD); + } else if (isa<CallExpr>(E) && E->isRValue()) { + // If the object is initialized by a function call that returns a + // scoped lockable by value, use the attributes on the copy or move + // constructor to figure out what effect that should have on the + // lockset. + // FIXME: Is this really the best way to handle this situation? + auto *RD = E->getType()->getAsCXXRecordDecl(); + if (!RD || !RD->hasAttr<ScopedLockableAttr>()) + continue; + CXXConstructorDecl *CtorD = findConstructorForByValueReturn(RD); + if (!CtorD || !CtorD->hasAttrs()) + continue; + handleCall(buildFakeCtorCall(CtorD, {E}, E->getBeginLoc()), CtorD, VD); + } + } + } +} + +/// Compute the intersection of two locksets and issue warnings for any +/// locks in the symmetric difference. +/// +/// This function is used at a merge point in the CFG when comparing the lockset +/// of each branch being merged. For example, given the following sequence: +/// A; if () then B; else C; D; we need to check that the lockset after B and C +/// are the same. In the event of a difference, we use the intersection of these +/// two locksets at the start of D. +/// +/// \param FSet1 The first lockset. +/// \param FSet2 The second lockset. +/// \param JoinLoc The location of the join point for error reporting +/// \param LEK1 The error message to report if a mutex is missing from LSet1 +/// \param LEK2 The error message to report if a mutex is missing from Lset2 +void ThreadSafetyAnalyzer::intersectAndWarn(FactSet &FSet1, + const FactSet &FSet2, + SourceLocation JoinLoc, + LockErrorKind LEK1, + LockErrorKind LEK2, + bool Modify) { + FactSet FSet1Orig = FSet1; + + // Find locks in FSet2 that conflict or are not in FSet1, and warn. + for (const auto &Fact : FSet2) { + 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. + *Iter1 = Fact; + } + } + else if (Modify && LDat1->asserted() && !LDat2->asserted()) { + // The non-asserted lock in FSet2 is the one we want to track. + *Iter1 = Fact; + } + } else { + LDat2->handleRemovalFromIntersection(FSet2, FactMan, JoinLoc, LEK1, + Handler); + } + } + + // Find locks in FSet1 that are not in FSet2, and remove them. + for (const auto &Fact : FSet1Orig) { + const FactEntry *LDat1 = &FactMan[Fact]; + const FactEntry *LDat2 = FSet2.findLock(FactMan, *LDat1); + + if (!LDat2) { + LDat1->handleRemovalFromIntersection(FSet1Orig, FactMan, JoinLoc, LEK2, + Handler); + if (Modify) + FSet1.removeLock(FactMan, *LDat1); + } + } +} + +// Return true if block B never continues to its successors. +static bool neverReturns(const CFGBlock *B) { + if (B->hasNoReturnElement()) + return true; + if (B->empty()) + return false; + + CFGElement Last = B->back(); + if (Optional<CFGStmt> S = Last.getAs<CFGStmt>()) { + if (isa<CXXThrowExpr>(S->getStmt())) + return true; + } + return false; +} + +/// Check a function's CFG for thread-safety violations. +/// +/// We traverse the blocks in the CFG, compute the set of mutexes that are held +/// at the end of each block, and issue warnings for thread safety violations. +/// Each block in the CFG is traversed exactly once. +void ThreadSafetyAnalyzer::runAnalysis(AnalysisDeclContext &AC) { + // TODO: this whole function needs be rewritten as a visitor for CFGWalker. + // For now, we just use the walker to set things up. + threadSafety::CFGWalker walker; + if (!walker.init(AC)) + return; + + // AC.dumpCFG(true); + // threadSafety::printSCFG(walker); + + CFG *CFGraph = walker.getGraph(); + const NamedDecl *D = walker.getDecl(); + const auto *CurrentFunction = dyn_cast<FunctionDecl>(D); + CurrentMethod = dyn_cast<CXXMethodDecl>(D); + + if (D->hasAttr<NoThreadSafetyAnalysisAttr>()) + return; + + // FIXME: Do something a bit more intelligent inside constructor and + // destructor code. Constructors and destructors must assume unique access + // to 'this', so checks on member variable access is disabled, but we should + // still enable checks on other objects. + if (isa<CXXConstructorDecl>(D)) + return; // Don't check inside constructors. + if (isa<CXXDestructorDecl>(D)) + return; // Don't check inside destructors. + + Handler.enterFunction(CurrentFunction); + + BlockInfo.resize(CFGraph->getNumBlockIDs(), + CFGBlockInfo::getEmptyBlockInfo(LocalVarMap)); + + // We need to explore the CFG via a "topological" ordering. + // That way, we will be guaranteed to have information about required + // predecessor locksets when exploring a new block. + const PostOrderCFGView *SortedGraph = walker.getSortedGraph(); + PostOrderCFGView::CFGBlockSet VisitedBlocks(CFGraph); + + // Mark entry block as reachable + BlockInfo[CFGraph->getEntry().getBlockID()].Reachable = true; + + // Compute SSA names for local variables + LocalVarMap.traverseCFG(CFGraph, SortedGraph, BlockInfo); + + // Fill in source locations for all CFGBlocks. + findBlockLocations(CFGraph, SortedGraph, BlockInfo); + + 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. + // FIXME: is there a more intelligent way to check lock/unlock functions? + if (!SortedGraph->empty() && D->hasAttrs()) { + const CFGBlock *FirstBlock = *SortedGraph->begin(); + FactSet &InitialLockset = BlockInfo[FirstBlock->getBlockID()].EntrySet; + + CapExprSet ExclusiveLocksToAdd; + CapExprSet SharedLocksToAdd; + StringRef CapDiagKind = "mutex"; + + SourceLocation Loc = D->getLocation(); + for (const auto *Attr : D->attrs()) { + Loc = Attr->getLocation(); + if (const auto *A = dyn_cast<RequiresCapabilityAttr>(Attr)) { + getMutexIDs(A->isShared() ? SharedLocksToAdd : ExclusiveLocksToAdd, A, + nullptr, D); + CapDiagKind = ClassifyDiagnostic(A); + } else if (const auto *A = dyn_cast<ReleaseCapabilityAttr>(Attr)) { + // UNLOCK_FUNCTION() is used to hide the underlying lock implementation. + // We must ignore such methods. + if (A->args_size() == 0) + return; + getMutexIDs(A->isShared() ? SharedLocksToAdd : ExclusiveLocksToAdd, A, + nullptr, D); + getMutexIDs(LocksReleased, A, nullptr, D); + CapDiagKind = ClassifyDiagnostic(A); + } else if (const auto *A = dyn_cast<AcquireCapabilityAttr>(Attr)) { + if (A->args_size() == 0) + return; + getMutexIDs(A->isShared() ? SharedLocksAcquired + : ExclusiveLocksAcquired, + A, nullptr, D); + CapDiagKind = ClassifyDiagnostic(A); + } else if (isa<ExclusiveTrylockFunctionAttr>(Attr)) { + // Don't try to check trylock functions for now. + return; + } else if (isa<SharedTrylockFunctionAttr>(Attr)) { + // Don't try to check trylock functions for now. + return; + } else if (isa<TryAcquireCapabilityAttr>(Attr)) { + // Don't try to check trylock functions for now. + return; + } + } + + // FIXME -- Loc can be wrong here. + for (const auto &Mu : ExclusiveLocksToAdd) { + auto Entry = std::make_unique<LockableFactEntry>(Mu, LK_Exclusive, Loc); + Entry->setDeclared(true); + addLock(InitialLockset, std::move(Entry), CapDiagKind, true); + } + for (const auto &Mu : SharedLocksToAdd) { + auto Entry = std::make_unique<LockableFactEntry>(Mu, LK_Shared, Loc); + Entry->setDeclared(true); + addLock(InitialLockset, std::move(Entry), CapDiagKind, true); + } + } + + for (const auto *CurrBlock : *SortedGraph) { + unsigned CurrBlockID = CurrBlock->getBlockID(); + CFGBlockInfo *CurrBlockInfo = &BlockInfo[CurrBlockID]; + + // Use the default initial lockset in case there are no predecessors. + VisitedBlocks.insert(CurrBlock); + + // Iterate through the predecessor blocks and warn if the lockset for all + // predecessors is not the same. We take the entry lockset of the current + // block to be the intersection of all previous locksets. + // FIXME: By keeping the intersection, we may output more errors in future + // for a lock which is not in the intersection, but was in the union. We + // may want to also keep the union in future. As an example, let's say + // the intersection contains Mutex L, and the union contains L and M. + // Later we unlock M. At this point, we would output an error because we + // never locked M; although the real error is probably that we forgot to + // lock M on all code paths. Conversely, let's say that later we lock M. + // In this case, we should compare against the intersection instead of the + // union because the real error is probably that we forgot to unlock M on + // all code paths. + bool LocksetInitialized = false; + SmallVector<CFGBlock *, 8> SpecialBlocks; + for (CFGBlock::const_pred_iterator PI = CurrBlock->pred_begin(), + PE = CurrBlock->pred_end(); PI != PE; ++PI) { + // if *PI -> CurrBlock is a back edge + if (*PI == nullptr || !VisitedBlocks.alreadySet(*PI)) + continue; + + unsigned PrevBlockID = (*PI)->getBlockID(); + CFGBlockInfo *PrevBlockInfo = &BlockInfo[PrevBlockID]; + + // Ignore edges from blocks that can't return. + if (neverReturns(*PI) || !PrevBlockInfo->Reachable) + continue; + + // Okay, we can reach this block from the entry. + CurrBlockInfo->Reachable = true; + + // If the previous block ended in a 'continue' or 'break' statement, then + // a difference in locksets is probably due to a bug in that block, rather + // than in some other predecessor. In that case, keep the other + // predecessor's lockset. + if (const Stmt *Terminator = (*PI)->getTerminatorStmt()) { + if (isa<ContinueStmt>(Terminator) || isa<BreakStmt>(Terminator)) { + SpecialBlocks.push_back(*PI); + continue; + } + } + + FactSet PrevLockset; + getEdgeLockset(PrevLockset, PrevBlockInfo->ExitSet, *PI, CurrBlock); + + if (!LocksetInitialized) { + CurrBlockInfo->EntrySet = PrevLockset; + LocksetInitialized = true; + } else { + intersectAndWarn(CurrBlockInfo->EntrySet, PrevLockset, + CurrBlockInfo->EntryLoc, + LEK_LockedSomePredecessors); + } + } + + // Skip rest of block if it's not reachable. + if (!CurrBlockInfo->Reachable) + continue; + + // Process continue and break blocks. Assume that the lockset for the + // resulting block is unaffected by any discrepancies in them. + for (const auto *PrevBlock : SpecialBlocks) { + unsigned PrevBlockID = PrevBlock->getBlockID(); + CFGBlockInfo *PrevBlockInfo = &BlockInfo[PrevBlockID]; + + if (!LocksetInitialized) { + CurrBlockInfo->EntrySet = PrevBlockInfo->ExitSet; + LocksetInitialized = true; + } else { + // Determine whether this edge is a loop terminator for diagnostic + // purposes. FIXME: A 'break' statement might be a loop terminator, but + // it might also be part of a switch. Also, a subsequent destructor + // might add to the lockset, in which case the real issue might be a + // double lock on the other path. + const Stmt *Terminator = PrevBlock->getTerminatorStmt(); + bool IsLoop = Terminator && isa<ContinueStmt>(Terminator); + + FactSet PrevLockset; + getEdgeLockset(PrevLockset, PrevBlockInfo->ExitSet, + PrevBlock, CurrBlock); + + // Do not update EntrySet. + intersectAndWarn(CurrBlockInfo->EntrySet, PrevLockset, + PrevBlockInfo->ExitLoc, + IsLoop ? LEK_LockedSomeLoopIterations + : LEK_LockedSomePredecessors, + false); + } + } + + BuildLockset LocksetBuilder(this, *CurrBlockInfo); + + // Visit all the statements in the basic block. + for (const auto &BI : *CurrBlock) { + switch (BI.getKind()) { + case CFGElement::Statement: { + CFGStmt CS = BI.castAs<CFGStmt>(); + LocksetBuilder.Visit(CS.getStmt()); + break; + } + // Ignore BaseDtor, MemberDtor, and TemporaryDtor for now. + case CFGElement::AutomaticObjectDtor: { + CFGAutomaticObjDtor AD = BI.castAs<CFGAutomaticObjDtor>(); + const auto *DD = AD.getDestructorDecl(AC.getASTContext()); + if (!DD->hasAttrs()) + break; + + // Create a dummy expression, + auto *VD = const_cast<VarDecl *>(AD.getVarDecl()); + DeclRefExpr DRE(VD->getASTContext(), VD, false, + VD->getType().getNonReferenceType(), VK_LValue, + AD.getTriggerStmt()->getEndLoc()); + LocksetBuilder.handleCall(&DRE, DD); + break; + } + default: + break; + } + } + CurrBlockInfo->ExitSet = LocksetBuilder.FSet; + + // For every back edge from CurrBlock (the end of the loop) to another block + // (FirstLoopBlock) we need to check that the Lockset of Block is equal to + // the one held at the beginning of FirstLoopBlock. We can look up the + // Lockset held at the beginning of FirstLoopBlock in the EntryLockSets map. + for (CFGBlock::const_succ_iterator SI = CurrBlock->succ_begin(), + SE = CurrBlock->succ_end(); SI != SE; ++SI) { + // if CurrBlock -> *SI is *not* a back edge + if (*SI == nullptr || !VisitedBlocks.alreadySet(*SI)) + continue; + + CFGBlock *FirstLoopBlock = *SI; + CFGBlockInfo *PreLoop = &BlockInfo[FirstLoopBlock->getBlockID()]; + CFGBlockInfo *LoopEnd = &BlockInfo[CurrBlockID]; + intersectAndWarn(LoopEnd->ExitSet, PreLoop->EntrySet, + PreLoop->EntryLoc, + LEK_LockedSomeLoopIterations, + false); + } + } + + CFGBlockInfo *Initial = &BlockInfo[CFGraph->getEntry().getBlockID()]; + CFGBlockInfo *Final = &BlockInfo[CFGraph->getExit().getBlockID()]; + + // Skip the final check if the exit block is unreachable. + if (!Final->Reachable) + return; + + // By default, we expect all locks held on entry to be held on exit. + FactSet ExpectedExitSet = Initial->EntrySet; + + // Adjust the expected exit set by adding or removing locks, as declared + // by *-LOCK_FUNCTION and UNLOCK_FUNCTION. The intersect below will then + // issue the appropriate warning. + // FIXME: the location here is not quite right. + for (const auto &Lock : ExclusiveLocksAcquired) + ExpectedExitSet.addLock(FactMan, std::make_unique<LockableFactEntry>( + Lock, LK_Exclusive, D->getLocation())); + for (const auto &Lock : SharedLocksAcquired) + ExpectedExitSet.addLock(FactMan, std::make_unique<LockableFactEntry>( + Lock, LK_Shared, D->getLocation())); + for (const auto &Lock : LocksReleased) + ExpectedExitSet.removeLock(FactMan, Lock); + + // FIXME: Should we call this function for all blocks which exit the function? + intersectAndWarn(ExpectedExitSet, Final->ExitSet, + Final->ExitLoc, + LEK_LockedAtEndOfFunction, + LEK_NotLockedAtEndOfFunction, + false); + + Handler.leaveFunction(CurrentFunction); +} + +/// Check a function's CFG for thread-safety violations. +/// +/// We traverse the blocks in the CFG, compute the set of mutexes that are held +/// at the end of each block, and issue warnings for thread safety violations. +/// Each block in the CFG is traversed exactly once. +void threadSafety::runThreadSafetyAnalysis(AnalysisDeclContext &AC, + ThreadSafetyHandler &Handler, + BeforeSet **BSet) { + if (!*BSet) + *BSet = new BeforeSet; + ThreadSafetyAnalyzer Analyzer(Handler, *BSet); + Analyzer.runAnalysis(AC); +} + +void threadSafety::threadSafetyCleanup(BeforeSet *Cache) { delete Cache; } + +/// Helper function that returns a LockKind required for the given level +/// of access. +LockKind threadSafety::getLockKindFromAccessKind(AccessKind AK) { + switch (AK) { + case AK_Read : + return LK_Shared; + case AK_Written : + return LK_Exclusive; + } + llvm_unreachable("Unknown AccessKind"); +} |