ThreadSafety.cpp revision cb96751b25a934b22402c1e4e0805db7608a5f2b
1fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell//===- ThreadSafety.cpp ----------------------------------------*- C++ --*-===// 2fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell// 3fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell// The LLVM Compiler Infrastructure 451fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie// 5fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell// This file is distributed under the University of Illinois Open Source 6fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell// License. See LICENSE.TXT for details. 7fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell// 8fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell//===----------------------------------------------------------------------===// 9fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell// 10fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell// A intra-procedural analysis for thread safety (e.g. deadlocks and race 11fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell// conditions), based off of an annotation system. 12fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell// 13fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell// See http://clang.llvm.org/docs/LanguageExtensions.html#threadsafety for more 14fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell// information. 15fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell// 16fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell//===----------------------------------------------------------------------===// 17fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell 18fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell#include "clang/Analysis/Analyses/ThreadSafety.h" 19fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell#include "clang/Analysis/AnalysisContext.h" 20fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell#include "clang/Analysis/CFG.h" 21fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell#include "clang/Analysis/CFGStmtMap.h" 22fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell#include "clang/AST/DeclCXX.h" 23fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell#include "clang/AST/ExprCXX.h" 24fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell#include "clang/AST/StmtCXX.h" 25fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell#include "clang/AST/StmtVisitor.h" 26fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell#include "clang/Basic/SourceManager.h" 27fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell#include "clang/Basic/SourceLocation.h" 28ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul#include "llvm/ADT/BitVector.h" 29492b69f3be3e355064c67bc6f4a30d40e997ce9dMarek Olšák#include "llvm/ADT/FoldingSet.h" 30492b69f3be3e355064c67bc6f4a30d40e997ce9dMarek Olšák#include "llvm/ADT/ImmutableMap.h" 31492b69f3be3e355064c67bc6f4a30d40e997ce9dMarek Olšák#include "llvm/ADT/PostOrderIterator.h" 32492b69f3be3e355064c67bc6f4a30d40e997ce9dMarek Olšák#include "llvm/ADT/SmallVector.h" 33fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell#include "llvm/ADT/StringRef.h" 34492b69f3be3e355064c67bc6f4a30d40e997ce9dMarek Olšák#include <algorithm> 35492b69f3be3e355064c67bc6f4a30d40e997ce9dMarek Olšák#include <vector> 36492b69f3be3e355064c67bc6f4a30d40e997ce9dMarek Olšák 37492b69f3be3e355064c67bc6f4a30d40e997ce9dMarek Olšákusing namespace clang; 38fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwellusing namespace thread_safety; 39ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul 40492b69f3be3e355064c67bc6f4a30d40e997ce9dMarek Olšák// Key method definition 41492b69f3be3e355064c67bc6f4a30d40e997ce9dMarek OlšákThreadSafetyHandler::~ThreadSafetyHandler() {} 42492b69f3be3e355064c67bc6f4a30d40e997ce9dMarek Olšák 43ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul// Helper functions 44492b69f3be3e355064c67bc6f4a30d40e997ce9dMarek Olšákstatic Expr *getParent(Expr *Exp) { 45492b69f3be3e355064c67bc6f4a30d40e997ce9dMarek Olšák if (MemberExpr *ME = dyn_cast<MemberExpr>(Exp)) 46492b69f3be3e355064c67bc6f4a30d40e997ce9dMarek Olšák return ME->getBase(); 47492b69f3be3e355064c67bc6f4a30d40e997ce9dMarek Olšák if (CXXMemberCallExpr *CE = dyn_cast<CXXMemberCallExpr>(Exp)) 48492b69f3be3e355064c67bc6f4a30d40e997ce9dMarek Olšák return CE->getImplicitObjectArgument(); 49492b69f3be3e355064c67bc6f4a30d40e997ce9dMarek Olšák return 0; 50492b69f3be3e355064c67bc6f4a30d40e997ce9dMarek Olšák} 51492b69f3be3e355064c67bc6f4a30d40e997ce9dMarek Olšák 52ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paulnamespace { 53ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul/// \brief Implements a set of CFGBlocks using a BitVector. 54ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul/// 55492b69f3be3e355064c67bc6f4a30d40e997ce9dMarek Olšák/// This class contains a minimal interface, primarily dictated by the SetType 56492b69f3be3e355064c67bc6f4a30d40e997ce9dMarek Olšák/// template parameter of the llvm::po_iterator template, as used with external 57492b69f3be3e355064c67bc6f4a30d40e997ce9dMarek Olšák/// storage. We also use this set to keep track of which CFGBlocks we visit 58492b69f3be3e355064c67bc6f4a30d40e997ce9dMarek Olšák/// during the analysis. 59492b69f3be3e355064c67bc6f4a30d40e997ce9dMarek Olšákclass CFGBlockSet { 60492b69f3be3e355064c67bc6f4a30d40e997ce9dMarek Olšák llvm::BitVector VisitedBlockIDs; 61492b69f3be3e355064c67bc6f4a30d40e997ce9dMarek Olšák 62ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paulpublic: 63492b69f3be3e355064c67bc6f4a30d40e997ce9dMarek Olšák // po_iterator requires this iterator, but the only interface needed is the 64492b69f3be3e355064c67bc6f4a30d40e997ce9dMarek Olšák // value_type typedef. 65492b69f3be3e355064c67bc6f4a30d40e997ce9dMarek Olšák struct iterator { 66492b69f3be3e355064c67bc6f4a30d40e997ce9dMarek Olšák typedef const CFGBlock *value_type; 67ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul }; 68492b69f3be3e355064c67bc6f4a30d40e997ce9dMarek Olšák 69fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell CFGBlockSet() {} 709520f483b8f1e45fa474674b415554988de5d8d3Brian Paul CFGBlockSet(const CFG *G) : VisitedBlockIDs(G->getNumBlockIDs(), false) {} 7151fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie 7251fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie /// \brief Set the bit associated with a particular CFGBlock. 7351fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie /// This is the important method for the SetType template parameter. 7451fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie bool insert(const CFGBlock *Block) { 759520f483b8f1e45fa474674b415554988de5d8d3Brian Paul // Note that insert() is called by po_iterator, which doesn't check to make 7651fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie // sure that Block is non-null. Moreover, the CFGBlock iterator will 7751fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie // occasionally hand out null pointers for pruned edges, so we catch those 7851fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie // here. 7951fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie if (Block == 0) 80492b69f3be3e355064c67bc6f4a30d40e997ce9dMarek Olšák return false; // if an edge is trivially false. 81492b69f3be3e355064c67bc6f4a30d40e997ce9dMarek Olšák if (VisitedBlockIDs.test(Block->getBlockID())) 82492b69f3be3e355064c67bc6f4a30d40e997ce9dMarek Olšák return false; 83492b69f3be3e355064c67bc6f4a30d40e997ce9dMarek Olšák VisitedBlockIDs.set(Block->getBlockID()); 8451fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie return true; 85492b69f3be3e355064c67bc6f4a30d40e997ce9dMarek Olšák } 86492b69f3be3e355064c67bc6f4a30d40e997ce9dMarek Olšák 8751fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie /// \brief Check if the bit for a CFGBlock has been already set. 8851fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie /// This method is for tracking visited blocks in the main threadsafety loop. 89492b69f3be3e355064c67bc6f4a30d40e997ce9dMarek Olšák /// Block must not be null. 9051fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie bool alreadySet(const CFGBlock *Block) { 9151fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie return VisitedBlockIDs.test(Block->getBlockID()); 9251fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie } 93492b69f3be3e355064c67bc6f4a30d40e997ce9dMarek Olšák}; 9451fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie 9551fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie/// \brief We create a helper class which we use to iterate through CFGBlocks in 9651fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie/// the topological order. 9751fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlieclass TopologicallySortedCFG { 9851fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie typedef llvm::po_iterator<const CFG*, CFGBlockSet, true> po_iterator; 9951fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie 10051fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie std::vector<const CFGBlock*> Blocks; 10151fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie 1029520f483b8f1e45fa474674b415554988de5d8d3Brian Paulpublic: 10351fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie typedef std::vector<const CFGBlock*>::reverse_iterator iterator; 10451fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie 10551fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie TopologicallySortedCFG(const CFG *CFGraph) { 10651fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie Blocks.reserve(CFGraph->getNumBlockIDs()); 10751fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie CFGBlockSet BSet(CFGraph); 10851fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie 1099520f483b8f1e45fa474674b415554988de5d8d3Brian Paul for (po_iterator I = po_iterator::begin(CFGraph, BSet), 11051fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie E = po_iterator::end(CFGraph, BSet); I != E; ++I) { 11151fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie Blocks.push_back(*I); 11251fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie } 11351fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie } 11451fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie 11551fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie iterator begin() { 1169520f483b8f1e45fa474674b415554988de5d8d3Brian Paul return Blocks.rbegin(); 11751fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie } 11851fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie 11951fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie iterator end() { 12051fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie return Blocks.rend(); 12151fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie } 12251fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie 1239520f483b8f1e45fa474674b415554988de5d8d3Brian Paul bool empty() { 12451fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie return begin() == end(); 12551fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie } 12651fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie}; 12751fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie 12851fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie/// \brief A MutexID object uniquely identifies a particular mutex, and 12951fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie/// is built from an Expr* (i.e. calling a lock function). 130492b69f3be3e355064c67bc6f4a30d40e997ce9dMarek Olšák/// 131492b69f3be3e355064c67bc6f4a30d40e997ce9dMarek Olšák/// Thread-safety analysis works by comparing lock expressions. Within the 13251fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie/// body of a function, an expression such as "x->foo->bar.mu" will resolve to 13351fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie/// a particular mutex object at run-time. Subsequent occurrences of the same 134492b69f3be3e355064c67bc6f4a30d40e997ce9dMarek Olšák/// expression (where "same" means syntactic equality) will refer to the same 13551fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie/// run-time object if three conditions hold: 13651fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie/// (1) Local variables in the expression, such as "x" have not changed. 13751fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie/// (2) Values on the heap that affect the expression have not changed. 138492b69f3be3e355064c67bc6f4a30d40e997ce9dMarek Olšák/// (3) The expression involves only pure function calls. 13951fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie/// The current implementation assumes, but does not verify, that multiple uses 14051fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie/// of the same lock expression satisfies these criteria. 14151fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie/// 14251fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie/// Clang introduces an additional wrinkle, which is that it is difficult to 14351fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie/// derive canonical expressions, or compare expressions directly for equality. 14451fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie/// Thus, we identify a mutex not by an Expr, but by the set of named 145492b69f3be3e355064c67bc6f4a30d40e997ce9dMarek Olšák/// declarations that are referenced by the Expr. In other words, 146492b69f3be3e355064c67bc6f4a30d40e997ce9dMarek Olšák/// x->foo->bar.mu will be a four element vector with the Decls for 14751fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie/// mu, bar, and foo, and x. The vector will uniquely identify the expression 14851fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie/// for all practical purposes. 149492b69f3be3e355064c67bc6f4a30d40e997ce9dMarek Olšák/// 15051fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie/// Note we will need to perform substitution on "this" and function parameter 15151fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie/// names when constructing a lock expression. 15251fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie/// 153492b69f3be3e355064c67bc6f4a30d40e997ce9dMarek Olšák/// For example: 15451fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie/// class C { Mutex Mu; void lock() EXCLUSIVE_LOCK_FUNCTION(this->Mu); }; 15551fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie/// void myFunc(C *X) { ... X->lock() ... } 15651fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie/// The original expression for the mutex acquired by myFunc is "this->Mu", but 15751fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie/// "X" is substituted for "this" so we get X->Mu(); 15851fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie/// 15951fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie/// For another example: 16051fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie/// foo(MyList *L) EXCLUSIVE_LOCKS_REQUIRED(L->Mu) { ... } 16151fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie/// MyList *MyL; 16251fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie/// foo(MyL); // requires lock MyL->Mu to be held 16351fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlieclass MutexID { 16451fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie SmallVector<NamedDecl*, 2> DeclSeq; 16551fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie 16651fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie /// Build a Decl sequence representing the lock from the given expression. 16751fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie /// Recursive function that bottoms out when the final DeclRefExpr is reached. 16851fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie void buildMutexID(Expr *Exp, Expr *Parent) { 16951fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie if (DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(Exp)) { 17051fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie NamedDecl *ND = cast<NamedDecl>(DRE->getDecl()->getCanonicalDecl()); 17151fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie DeclSeq.push_back(ND); 17251fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie } else if (MemberExpr *ME = dyn_cast<MemberExpr>(Exp)) { 17351fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie NamedDecl *ND = ME->getMemberDecl(); 17451fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie DeclSeq.push_back(ND); 17551fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie buildMutexID(ME->getBase(), Parent); 17651fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie } else if (isa<CXXThisExpr>(Exp)) { 17751fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie if (Parent) 17851fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie buildMutexID(Parent, 0); 17951fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie else 18051fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie return; // mutexID is still valid in this case 18151fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie } else if (CastExpr *CE = dyn_cast<CastExpr>(Exp)) 18251fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie buildMutexID(CE->getSubExpr(), Parent); 18351fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie else 184beea704be231ef13edab93a7299efa297039239dBrian Paul DeclSeq.clear(); // invalid lock expression 185beea704be231ef13edab93a7299efa297039239dBrian Paul } 186beea704be231ef13edab93a7299efa297039239dBrian Paul 187fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwellpublic: 188beea704be231ef13edab93a7299efa297039239dBrian Paul MutexID(Expr *LExpr, Expr *ParentExpr) { 189beea704be231ef13edab93a7299efa297039239dBrian Paul buildMutexID(LExpr, ParentExpr); 190fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell } 191fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell 192beea704be231ef13edab93a7299efa297039239dBrian Paul /// If we encounter part of a lock expression we cannot parse 193beea704be231ef13edab93a7299efa297039239dBrian Paul bool isValid() const { 194fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell return !DeclSeq.empty(); 195beea704be231ef13edab93a7299efa297039239dBrian Paul } 196beea704be231ef13edab93a7299efa297039239dBrian Paul 197fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell bool operator==(const MutexID &other) const { 198fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell return DeclSeq == other.DeclSeq; 199beea704be231ef13edab93a7299efa297039239dBrian Paul } 200beea704be231ef13edab93a7299efa297039239dBrian Paul 201fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell bool operator!=(const MutexID &other) const { 202beea704be231ef13edab93a7299efa297039239dBrian Paul return !(*this == other); 203beea704be231ef13edab93a7299efa297039239dBrian Paul } 204fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell 205fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell // SmallVector overloads Operator< to do lexicographic ordering. Note that 206beea704be231ef13edab93a7299efa297039239dBrian Paul // we use pointer equality (and <) to compare NamedDecls. This means the order 207beea704be231ef13edab93a7299efa297039239dBrian Paul // of MutexIDs in a lockset is nondeterministic. In order to output 208fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell // diagnostics in a deterministic ordering, we must order all diagnostics to 209beea704be231ef13edab93a7299efa297039239dBrian Paul // output by SourceLocation when iterating through this lockset. 210beea704be231ef13edab93a7299efa297039239dBrian Paul bool operator<(const MutexID &other) const { 211fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell return DeclSeq < other.DeclSeq; 212fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell } 213beea704be231ef13edab93a7299efa297039239dBrian Paul 214beea704be231ef13edab93a7299efa297039239dBrian Paul /// \brief Returns the name of the first Decl in the list for a given MutexID; 215fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell /// e.g. the lock expression foo.bar() has name "bar". 216beea704be231ef13edab93a7299efa297039239dBrian Paul /// The caret will point unambiguously to the lock expression, so using this 217beea704be231ef13edab93a7299efa297039239dBrian Paul /// name in diagnostics is a way to get simple, and consistent, mutex names. 218fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell /// We do not want to output the entire expression text for security reasons. 219fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell StringRef getName() const { 220beea704be231ef13edab93a7299efa297039239dBrian Paul assert(isValid()); 221beea704be231ef13edab93a7299efa297039239dBrian Paul return DeclSeq.front()->getName(); 222fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell } 223beea704be231ef13edab93a7299efa297039239dBrian Paul 224beea704be231ef13edab93a7299efa297039239dBrian Paul void Profile(llvm::FoldingSetNodeID &ID) const { 225fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell for (SmallVectorImpl<NamedDecl*>::const_iterator I = DeclSeq.begin(), 226fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell E = DeclSeq.end(); I != E; ++I) { 227beea704be231ef13edab93a7299efa297039239dBrian Paul ID.AddPointer(*I); 228beea704be231ef13edab93a7299efa297039239dBrian Paul } 229beea704be231ef13edab93a7299efa297039239dBrian Paul } 230beea704be231ef13edab93a7299efa297039239dBrian Paul}; 231fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell 232beea704be231ef13edab93a7299efa297039239dBrian Paul/// \brief This is a helper class that stores info about the most recent 233beea704be231ef13edab93a7299efa297039239dBrian Paul/// accquire of a Lock. 234fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell/// 235fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell/// The main body of the analysis maps MutexIDs to LockDatas. 236beea704be231ef13edab93a7299efa297039239dBrian Paulstruct LockData { 237beea704be231ef13edab93a7299efa297039239dBrian Paul SourceLocation AcquireLoc; 238fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell 239beea704be231ef13edab93a7299efa297039239dBrian Paul /// \brief LKind stores whether a lock is held shared or exclusively. 240beea704be231ef13edab93a7299efa297039239dBrian Paul /// Note that this analysis does not currently support either re-entrant 241fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell /// locking or lock "upgrading" and "downgrading" between exclusive and 242fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell /// shared. 243beea704be231ef13edab93a7299efa297039239dBrian Paul /// 244beea704be231ef13edab93a7299efa297039239dBrian Paul /// FIXME: add support for re-entrant locking and lock up/downgrading 245fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell LockKind LKind; 246beea704be231ef13edab93a7299efa297039239dBrian Paul 247beea704be231ef13edab93a7299efa297039239dBrian Paul LockData(SourceLocation AcquireLoc, LockKind LKind) 248fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell : AcquireLoc(AcquireLoc), LKind(LKind) {} 249fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell 250beea704be231ef13edab93a7299efa297039239dBrian Paul bool operator==(const LockData &other) const { 251beea704be231ef13edab93a7299efa297039239dBrian Paul return AcquireLoc == other.AcquireLoc && LKind == other.LKind; 252fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell } 253beea704be231ef13edab93a7299efa297039239dBrian Paul 254beea704be231ef13edab93a7299efa297039239dBrian Paul bool operator!=(const LockData &other) const { 255fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell return !(*this == other); 256fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell } 257beea704be231ef13edab93a7299efa297039239dBrian Paul 258beea704be231ef13edab93a7299efa297039239dBrian Paul void Profile(llvm::FoldingSetNodeID &ID) const { 259fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell ID.AddInteger(AcquireLoc.getRawEncoding()); 260beea704be231ef13edab93a7299efa297039239dBrian Paul ID.AddInteger(LKind); 261beea704be231ef13edab93a7299efa297039239dBrian Paul } 262fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell}; 263fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell 264beea704be231ef13edab93a7299efa297039239dBrian Paul/// A Lockset maps each MutexID (defined above) to information about how it has 265beea704be231ef13edab93a7299efa297039239dBrian Paul/// been locked. 266fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwelltypedef llvm::ImmutableMap<MutexID, LockData> Lockset; 267beea704be231ef13edab93a7299efa297039239dBrian Paul 268beea704be231ef13edab93a7299efa297039239dBrian Paul/// \brief We use this class to visit different types of expressions in 269fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell/// CFGBlocks, and build up the lockset. 270fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell/// An expression may cause us to add or remove locks from the lockset, or else 271beea704be231ef13edab93a7299efa297039239dBrian Paul/// output error messages related to missing locks. 272beea704be231ef13edab93a7299efa297039239dBrian Paul/// FIXME: In future, we may be able to not inherit from a visitor. 273fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwellclass BuildLockset : public StmtVisitor<BuildLockset> { 274beea704be231ef13edab93a7299efa297039239dBrian Paul ThreadSafetyHandler &Handler; 275beea704be231ef13edab93a7299efa297039239dBrian Paul Lockset LSet; 276fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell Lockset::Factory &LocksetFactory; 277fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell 278beea704be231ef13edab93a7299efa297039239dBrian Paul // Helper functions 279beea704be231ef13edab93a7299efa297039239dBrian Paul void removeLock(SourceLocation UnlockLoc, Expr *LockExp, Expr *Parent); 280fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell void addLock(SourceLocation LockLoc, Expr *LockExp, Expr *Parent, 281beea704be231ef13edab93a7299efa297039239dBrian Paul LockKind LK); 282beea704be231ef13edab93a7299efa297039239dBrian Paul const ValueDecl *getValueDecl(Expr *Exp); 283fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell void warnIfMutexNotHeld (const NamedDecl *D, Expr *Exp, AccessKind AK, 284fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell Expr *MutexExp, ProtectedOperationKind POK); 285beea704be231ef13edab93a7299efa297039239dBrian Paul void checkAccess(Expr *Exp, AccessKind AK); 286beea704be231ef13edab93a7299efa297039239dBrian Paul void checkDereference(Expr *Exp, AccessKind AK); 287beea704be231ef13edab93a7299efa297039239dBrian Paul 288beea704be231ef13edab93a7299efa297039239dBrian Paul template <class AttrType> 289fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell void addLocksToSet(LockKind LK, Attr *Attr, CXXMemberCallExpr *Exp); 290beea704be231ef13edab93a7299efa297039239dBrian Paul 291beea704be231ef13edab93a7299efa297039239dBrian Paul /// \brief Returns true if the lockset contains a lock, regardless of whether 292fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell /// the lock is held exclusively or shared. 293fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell bool locksetContains(MutexID Lock) const { 294beea704be231ef13edab93a7299efa297039239dBrian Paul return LSet.lookup(Lock); 295beea704be231ef13edab93a7299efa297039239dBrian Paul } 296fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell 297beea704be231ef13edab93a7299efa297039239dBrian Paul /// \brief Returns true if the lockset contains a lock with the passed in 298beea704be231ef13edab93a7299efa297039239dBrian Paul /// locktype. 299fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell bool locksetContains(MutexID Lock, LockKind KindRequested) const { 300fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell const LockData *LockHeld = LSet.lookup(Lock); 301beea704be231ef13edab93a7299efa297039239dBrian Paul return (LockHeld && KindRequested == LockHeld->LKind); 302beea704be231ef13edab93a7299efa297039239dBrian Paul } 303beea704be231ef13edab93a7299efa297039239dBrian Paul 304beea704be231ef13edab93a7299efa297039239dBrian Paul /// \brief Returns true if the lockset contains a lock with at least the 305fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell /// passed in locktype. So for example, if we pass in LK_Shared, this function 306beea704be231ef13edab93a7299efa297039239dBrian Paul /// returns true if the lock is held LK_Shared or LK_Exclusive. If we pass in 307beea704be231ef13edab93a7299efa297039239dBrian Paul /// LK_Exclusive, this function returns true if the lock is held LK_Exclusive. 308fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell bool locksetContainsAtLeast(MutexID Lock, LockKind KindRequested) const { 309fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell switch (KindRequested) { 310beea704be231ef13edab93a7299efa297039239dBrian Paul case LK_Shared: 311beea704be231ef13edab93a7299efa297039239dBrian Paul return locksetContains(Lock); 312beea704be231ef13edab93a7299efa297039239dBrian Paul case LK_Exclusive: 313beea704be231ef13edab93a7299efa297039239dBrian Paul return locksetContains(Lock, KindRequested); 314fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell } 315beea704be231ef13edab93a7299efa297039239dBrian Paul llvm_unreachable("Unknown LockKind"); 316beea704be231ef13edab93a7299efa297039239dBrian Paul } 317fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell 318fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwellpublic: 319beea704be231ef13edab93a7299efa297039239dBrian Paul BuildLockset(ThreadSafetyHandler &Handler, Lockset LS, Lockset::Factory &F) 320beea704be231ef13edab93a7299efa297039239dBrian Paul : StmtVisitor<BuildLockset>(), Handler(Handler), LSet(LS), 321fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell LocksetFactory(F) {} 322beea704be231ef13edab93a7299efa297039239dBrian Paul 323beea704be231ef13edab93a7299efa297039239dBrian Paul Lockset getLockset() { 324fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell return LSet; 325fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell } 326beea704be231ef13edab93a7299efa297039239dBrian Paul 327beea704be231ef13edab93a7299efa297039239dBrian Paul void VisitUnaryOperator(UnaryOperator *UO); 328fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell void VisitBinaryOperator(BinaryOperator *BO); 329beea704be231ef13edab93a7299efa297039239dBrian Paul void VisitCastExpr(CastExpr *CE); 330beea704be231ef13edab93a7299efa297039239dBrian Paul void VisitCXXMemberCallExpr(CXXMemberCallExpr *Exp); 331fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell}; 332fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell 333beea704be231ef13edab93a7299efa297039239dBrian Paul/// \brief Add a new lock to the lockset, warning if the lock is already there. 334beea704be231ef13edab93a7299efa297039239dBrian Paul/// \param LockLoc The source location of the acquire 335fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell/// \param LockExp The lock expression corresponding to the lock to be added 336beea704be231ef13edab93a7299efa297039239dBrian Paulvoid BuildLockset::addLock(SourceLocation LockLoc, Expr *LockExp, Expr *Parent, 337beea704be231ef13edab93a7299efa297039239dBrian Paul LockKind LK) { 338fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell // FIXME: deal with acquired before/after annotations 339fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell MutexID Mutex(LockExp, Parent); 340beea704be231ef13edab93a7299efa297039239dBrian Paul if (!Mutex.isValid()) { 341beea704be231ef13edab93a7299efa297039239dBrian Paul Handler.handleInvalidLockExp(LockExp->getExprLoc()); 342fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell return; 343beea704be231ef13edab93a7299efa297039239dBrian Paul } 344beea704be231ef13edab93a7299efa297039239dBrian Paul 345fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell LockData NewLock(LockLoc, LK); 346fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell 347beea704be231ef13edab93a7299efa297039239dBrian Paul // FIXME: Don't always warn when we have support for reentrant locks. 348beea704be231ef13edab93a7299efa297039239dBrian Paul if (locksetContains(Mutex)) 349beea704be231ef13edab93a7299efa297039239dBrian Paul Handler.handleDoubleLock(Mutex.getName(), LockLoc); 350beea704be231ef13edab93a7299efa297039239dBrian Paul LSet = LocksetFactory.add(LSet, Mutex, NewLock); 351fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell} 352beea704be231ef13edab93a7299efa297039239dBrian Paul 353beea704be231ef13edab93a7299efa297039239dBrian Paul/// \brief Remove a lock from the lockset, warning if the lock is not there. 354fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell/// \param LockExp The lock expression corresponding to the lock to be removed 355fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell/// \param UnlockLoc The source location of the unlock (only used in error msg) 356beea704be231ef13edab93a7299efa297039239dBrian Paulvoid BuildLockset::removeLock(SourceLocation UnlockLoc, Expr *LockExp, 357beea704be231ef13edab93a7299efa297039239dBrian Paul Expr *Parent) { 358fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell MutexID Mutex(LockExp, Parent); 359beea704be231ef13edab93a7299efa297039239dBrian Paul if (!Mutex.isValid()) { 360beea704be231ef13edab93a7299efa297039239dBrian Paul Handler.handleInvalidLockExp(LockExp->getExprLoc()); 361fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell return; 362fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell } 363fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell 364beea704be231ef13edab93a7299efa297039239dBrian Paul Lockset NewLSet = LocksetFactory.remove(LSet, Mutex); 365beea704be231ef13edab93a7299efa297039239dBrian Paul if(NewLSet == LSet) 366beea704be231ef13edab93a7299efa297039239dBrian Paul Handler.handleUnmatchedUnlock(Mutex.getName(), UnlockLoc); 367fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell 368beea704be231ef13edab93a7299efa297039239dBrian Paul LSet = NewLSet; 369beea704be231ef13edab93a7299efa297039239dBrian Paul} 370fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell 371fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell/// \brief Gets the value decl pointer from DeclRefExprs or MemberExprs 372beea704be231ef13edab93a7299efa297039239dBrian Paulconst ValueDecl *BuildLockset::getValueDecl(Expr *Exp) { 373beea704be231ef13edab93a7299efa297039239dBrian Paul if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(Exp)) 374beea704be231ef13edab93a7299efa297039239dBrian Paul return DR->getDecl(); 375beea704be231ef13edab93a7299efa297039239dBrian Paul 376fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell if (const MemberExpr *ME = dyn_cast<MemberExpr>(Exp)) 377beea704be231ef13edab93a7299efa297039239dBrian Paul return ME->getMemberDecl(); 378beea704be231ef13edab93a7299efa297039239dBrian Paul 379fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell return 0; 380fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell} 381beea704be231ef13edab93a7299efa297039239dBrian Paul 382beea704be231ef13edab93a7299efa297039239dBrian Paul/// \brief Warn if the LSet does not contain a lock sufficient to protect access 383fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell/// of at least the passed in AccessType. 384beea704be231ef13edab93a7299efa297039239dBrian Paulvoid BuildLockset::warnIfMutexNotHeld(const NamedDecl *D, Expr *Exp, 385beea704be231ef13edab93a7299efa297039239dBrian Paul AccessKind AK, Expr *MutexExp, 386fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell ProtectedOperationKind POK) { 387fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell LockKind LK = getLockKindFromAccessKind(AK); 388fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell Expr *Parent = getParent(Exp); 389beea704be231ef13edab93a7299efa297039239dBrian Paul MutexID Mutex(MutexExp, Parent); 390beea704be231ef13edab93a7299efa297039239dBrian Paul if (!Mutex.isValid()) 391beea704be231ef13edab93a7299efa297039239dBrian Paul Handler.handleInvalidLockExp(MutexExp->getExprLoc()); 392fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell else if (!locksetContainsAtLeast(Mutex, LK)) 393beea704be231ef13edab93a7299efa297039239dBrian Paul Handler.handleMutexNotHeld(D, POK, Mutex.getName(), LK, Exp->getExprLoc()); 394fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell} 395beea704be231ef13edab93a7299efa297039239dBrian Paul 396fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell 397fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell/// \brief This method identifies variable dereferences and checks pt_guarded_by 398beea704be231ef13edab93a7299efa297039239dBrian Paul/// and pt_guarded_var annotations. Note that we only check these annotations 399beea704be231ef13edab93a7299efa297039239dBrian Paul/// at the time a pointer is dereferenced. 400fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell/// FIXME: We need to check for other types of pointer dereferences 401beea704be231ef13edab93a7299efa297039239dBrian Paul/// (e.g. [], ->) and deal with them here. 402fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell/// \param Exp An expression that has been read or written. 403beea704be231ef13edab93a7299efa297039239dBrian Paulvoid BuildLockset::checkDereference(Expr *Exp, AccessKind AK) { 404fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell UnaryOperator *UO = dyn_cast<UnaryOperator>(Exp); 405fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell if (!UO || UO->getOpcode() != clang::UO_Deref) 406beea704be231ef13edab93a7299efa297039239dBrian Paul return; 407beea704be231ef13edab93a7299efa297039239dBrian Paul Exp = UO->getSubExpr()->IgnoreParenCasts(); 408fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell 409beea704be231ef13edab93a7299efa297039239dBrian Paul const ValueDecl *D = getValueDecl(Exp); 410fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell if(!D || !D->hasAttrs()) 411beea704be231ef13edab93a7299efa297039239dBrian Paul return; 412fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell 413fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell if (D->getAttr<PtGuardedVarAttr>() && LSet.isEmpty()) 414beea704be231ef13edab93a7299efa297039239dBrian Paul Handler.handleNoMutexHeld(D, POK_VarDereference, AK, Exp->getExprLoc()); 415beea704be231ef13edab93a7299efa297039239dBrian Paul 416fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell const AttrVec &ArgAttrs = D->getAttrs(); 417beea704be231ef13edab93a7299efa297039239dBrian Paul for(unsigned i = 0, Size = ArgAttrs.size(); i < Size; ++i) 418fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell if (PtGuardedByAttr *PGBAttr = dyn_cast<PtGuardedByAttr>(ArgAttrs[i])) 419beea704be231ef13edab93a7299efa297039239dBrian Paul warnIfMutexNotHeld(D, Exp, AK, PGBAttr->getArg(), POK_VarDereference); 420fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell} 421fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell 422beea704be231ef13edab93a7299efa297039239dBrian Paul/// \brief Checks guarded_by and guarded_var attributes. 423beea704be231ef13edab93a7299efa297039239dBrian Paul/// Whenever we identify an access (read or write) of a DeclRefExpr or 424fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell/// MemberExpr, we need to check whether there are any guarded_by or 425beea704be231ef13edab93a7299efa297039239dBrian Paul/// guarded_var attributes, and make sure we hold the appropriate mutexes. 426fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwellvoid BuildLockset::checkAccess(Expr *Exp, AccessKind AK) { 427beea704be231ef13edab93a7299efa297039239dBrian Paul const ValueDecl *D = getValueDecl(Exp); 428fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell if(!D || !D->hasAttrs()) 429fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell return; 430beea704be231ef13edab93a7299efa297039239dBrian Paul 431beea704be231ef13edab93a7299efa297039239dBrian Paul if (D->getAttr<GuardedVarAttr>() && LSet.isEmpty()) 432fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell Handler.handleNoMutexHeld(D, POK_VarAccess, AK, Exp->getExprLoc()); 433beea704be231ef13edab93a7299efa297039239dBrian Paul 434fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell const AttrVec &ArgAttrs = D->getAttrs(); 435beea704be231ef13edab93a7299efa297039239dBrian Paul for(unsigned i = 0, Size = ArgAttrs.size(); i < Size; ++i) 436fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell if (GuardedByAttr *GBAttr = dyn_cast<GuardedByAttr>(ArgAttrs[i])) 437fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell warnIfMutexNotHeld(D, Exp, AK, GBAttr->getArg(), POK_VarAccess); 438beea704be231ef13edab93a7299efa297039239dBrian Paul} 439beea704be231ef13edab93a7299efa297039239dBrian Paul 440fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell/// \brief For unary operations which read and write a variable, we need to 441beea704be231ef13edab93a7299efa297039239dBrian Paul/// check whether we hold any required mutexes. Reads are checked in 442fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell/// VisitCastExpr. 443beea704be231ef13edab93a7299efa297039239dBrian Paulvoid BuildLockset::VisitUnaryOperator(UnaryOperator *UO) { 444fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell switch (UO->getOpcode()) { 445fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell case clang::UO_PostDec: 446beea704be231ef13edab93a7299efa297039239dBrian Paul case clang::UO_PostInc: 447beea704be231ef13edab93a7299efa297039239dBrian Paul case clang::UO_PreDec: 448fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell case clang::UO_PreInc: { 449beea704be231ef13edab93a7299efa297039239dBrian Paul Expr *SubExp = UO->getSubExpr()->IgnoreParenCasts(); 450fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell checkAccess(SubExp, AK_Written); 451beea704be231ef13edab93a7299efa297039239dBrian Paul checkDereference(SubExp, AK_Written); 452fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell break; 453fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell } 454fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell default: 455beea704be231ef13edab93a7299efa297039239dBrian Paul break; 456beea704be231ef13edab93a7299efa297039239dBrian Paul } 457beea704be231ef13edab93a7299efa297039239dBrian Paul} 458fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell 459beea704be231ef13edab93a7299efa297039239dBrian Paul/// For binary operations which assign to a variable (writes), we need to check 460beea704be231ef13edab93a7299efa297039239dBrian Paul/// whether we hold any required mutexes. 461fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell/// FIXME: Deal with non-primitive types. 4624a95185c9f30c2de7a03bb1a0653f51b53b1111dBrian Paulvoid BuildLockset::VisitBinaryOperator(BinaryOperator *BO) { 463fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell if (!BO->isAssignmentOp()) 464fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell return; 465a2924b488b8d77381779bbb5a0097c467678d39bBrian Paul Expr *LHSExp = BO->getLHS()->IgnoreParenCasts(); 466fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell checkAccess(LHSExp, AK_Written); 467fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell checkDereference(LHSExp, AK_Written); 468beea704be231ef13edab93a7299efa297039239dBrian Paul} 469beea704be231ef13edab93a7299efa297039239dBrian Paul 470fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell/// Whenever we do an LValue to Rvalue cast, we are reading a variable and 471beea704be231ef13edab93a7299efa297039239dBrian Paul/// need to ensure we hold any required mutexes. 472beea704be231ef13edab93a7299efa297039239dBrian Paul/// FIXME: Deal with non-primitive types. 473fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwellvoid BuildLockset::VisitCastExpr(CastExpr *CE) { 4744a95185c9f30c2de7a03bb1a0653f51b53b1111dBrian Paul if (CE->getCastKind() != CK_LValueToRValue) 475fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell return; 476fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell Expr *SubExp = CE->getSubExpr()->IgnoreParenCasts(); 477a2924b488b8d77381779bbb5a0097c467678d39bBrian Paul checkAccess(SubExp, AK_Read); 478fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell checkDereference(SubExp, AK_Read); 479fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell} 480beea704be231ef13edab93a7299efa297039239dBrian Paul 481beea704be231ef13edab93a7299efa297039239dBrian Paul/// \brief This function, parameterized by an attribute type, is used to add a 482fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell/// set of locks specified as attribute arguments to the lockset. 483beea704be231ef13edab93a7299efa297039239dBrian Paultemplate <typename AttrType> 484beea704be231ef13edab93a7299efa297039239dBrian Paulvoid BuildLockset::addLocksToSet(LockKind LK, Attr *Attr, 485fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell CXXMemberCallExpr *Exp) { 4864a95185c9f30c2de7a03bb1a0653f51b53b1111dBrian Paul typedef typename AttrType::args_iterator iterator_type; 487fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell SourceLocation ExpLocation = Exp->getExprLoc(); 488fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell Expr *Parent = Exp->getImplicitObjectArgument(); 489a2924b488b8d77381779bbb5a0097c467678d39bBrian Paul AttrType *SpecificAttr = cast<AttrType>(Attr); 490fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell 491fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell if (SpecificAttr->args_size() == 0) { 492beea704be231ef13edab93a7299efa297039239dBrian Paul // The mutex held is the "this" object. 493beea704be231ef13edab93a7299efa297039239dBrian Paul addLock(ExpLocation, Parent, 0, LK); 494fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell return; 495beea704be231ef13edab93a7299efa297039239dBrian Paul } 496beea704be231ef13edab93a7299efa297039239dBrian Paul 497fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell for (iterator_type I = SpecificAttr->args_begin(), 4984a95185c9f30c2de7a03bb1a0653f51b53b1111dBrian Paul E = SpecificAttr->args_end(); I != E; ++I) 499fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell addLock(ExpLocation, *I, Parent, LK); 500fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell} 501a2924b488b8d77381779bbb5a0097c467678d39bBrian Paul 502fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell/// \brief When visiting CXXMemberCallExprs we need to examine the attributes on 503fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell/// the method that is being called and add, remove or check locks in the 504beea704be231ef13edab93a7299efa297039239dBrian Paul/// lockset accordingly. 505beea704be231ef13edab93a7299efa297039239dBrian Paul/// 506fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell/// FIXME: For classes annotated with one of the guarded annotations, we need 507beea704be231ef13edab93a7299efa297039239dBrian Paul/// to treat const method calls as reads and non-const method calls as writes, 508beea704be231ef13edab93a7299efa297039239dBrian Paul/// and check that the appropriate locks are held. Non-const method calls with 509fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell/// the same signature as const method calls can be also treated as reads. 5104a95185c9f30c2de7a03bb1a0653f51b53b1111dBrian Paul/// 511fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell/// FIXME: We need to also visit CallExprs to catch/check global functions. 512fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwellvoid BuildLockset::VisitCXXMemberCallExpr(CXXMemberCallExpr *Exp) { 513a2924b488b8d77381779bbb5a0097c467678d39bBrian Paul NamedDecl *D = dyn_cast_or_null<NamedDecl>(Exp->getCalleeDecl()); 514fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell 515fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell SourceLocation ExpLocation = Exp->getExprLoc(); 516beea704be231ef13edab93a7299efa297039239dBrian Paul Expr *Parent = Exp->getImplicitObjectArgument(); 517beea704be231ef13edab93a7299efa297039239dBrian Paul 518fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell if(!D || !D->hasAttrs()) 519beea704be231ef13edab93a7299efa297039239dBrian Paul return; 520beea704be231ef13edab93a7299efa297039239dBrian Paul 521fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell AttrVec &ArgAttrs = D->getAttrs(); 5224a95185c9f30c2de7a03bb1a0653f51b53b1111dBrian Paul for(unsigned i = 0; i < ArgAttrs.size(); ++i) { 523fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell Attr *Attr = ArgAttrs[i]; 524fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell switch (Attr->getKind()) { 525a2924b488b8d77381779bbb5a0097c467678d39bBrian Paul // When we encounter an exclusive lock function, we need to add the lock 526fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell // to our lockset with kind exclusive. 527fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell case attr::ExclusiveLockFunction: 528beea704be231ef13edab93a7299efa297039239dBrian Paul addLocksToSet<ExclusiveLockFunctionAttr>(LK_Exclusive, Attr, Exp); 529beea704be231ef13edab93a7299efa297039239dBrian Paul break; 530fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell 531beea704be231ef13edab93a7299efa297039239dBrian Paul // When we encounter a shared lock function, we need to add the lock 532beea704be231ef13edab93a7299efa297039239dBrian Paul // to our lockset with kind shared. 533fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell case attr::SharedLockFunction: 5344a95185c9f30c2de7a03bb1a0653f51b53b1111dBrian Paul addLocksToSet<SharedLockFunctionAttr>(LK_Shared, Attr, Exp); 535fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell break; 536fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell 537a2924b488b8d77381779bbb5a0097c467678d39bBrian Paul // When we encounter an unlock function, we need to remove unlocked 538fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell // mutexes from the lockset, and flag a warning if they are not there. 539fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell case attr::UnlockFunction: { 540beea704be231ef13edab93a7299efa297039239dBrian Paul UnlockFunctionAttr *UFAttr = cast<UnlockFunctionAttr>(Attr); 541beea704be231ef13edab93a7299efa297039239dBrian Paul 542fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell if (UFAttr->args_size() == 0) { // The lock held is the "this" object. 543beea704be231ef13edab93a7299efa297039239dBrian Paul removeLock(ExpLocation, Parent, 0); 544beea704be231ef13edab93a7299efa297039239dBrian Paul break; 545fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell } 5464a95185c9f30c2de7a03bb1a0653f51b53b1111dBrian Paul 547fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell for (UnlockFunctionAttr::args_iterator I = UFAttr->args_begin(), 548fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell E = UFAttr->args_end(); I != E; ++I) 549a2924b488b8d77381779bbb5a0097c467678d39bBrian Paul removeLock(ExpLocation, *I, Parent); 550fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell break; 551fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell } 552fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell 553ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul case attr::ExclusiveLocksRequired: { 554ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul // FIXME: Also use this attribute to add required locks to the initial 555ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul // lockset when processing a CFG for a function annotated with this 556ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul // attribute. 557ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul ExclusiveLocksRequiredAttr *ELRAttr = 558ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul cast<ExclusiveLocksRequiredAttr>(Attr); 559ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul 560ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul for (ExclusiveLocksRequiredAttr::args_iterator 561ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul I = ELRAttr->args_begin(), E = ELRAttr->args_end(); I != E; ++I) 562ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul warnIfMutexNotHeld(D, Exp, AK_Written, *I, POK_FunctionCall); 563ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul break; 564ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul } 565ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul 566a2924b488b8d77381779bbb5a0097c467678d39bBrian Paul case attr::SharedLocksRequired: { 567ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul // FIXME: Also use this attribute to add required locks to the initial 568ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul // lockset when processing a CFG for a function annotated with this 569ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul // attribute. 570ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul SharedLocksRequiredAttr *SLRAttr = cast<SharedLocksRequiredAttr>(Attr); 571ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul 572ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul for (SharedLocksRequiredAttr::args_iterator I = SLRAttr->args_begin(), 573ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul E = SLRAttr->args_end(); I != E; ++I) 574ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul warnIfMutexNotHeld(D, Exp, AK_Read, *I, POK_FunctionCall); 575ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul break; 576ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul } 577ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul 578a2924b488b8d77381779bbb5a0097c467678d39bBrian Paul case attr::LocksExcluded: { 579ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul LocksExcludedAttr *LEAttr = cast<LocksExcludedAttr>(Attr); 580ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul for (LocksExcludedAttr::args_iterator I = LEAttr->args_begin(), 581ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul E = LEAttr->args_end(); I != E; ++I) { 582ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul MutexID Mutex(*I, Parent); 583ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul if (!Mutex.isValid()) 584ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul Handler.handleInvalidLockExp((*I)->getExprLoc()); 585ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul else if (locksetContains(Mutex)) 586ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul Handler.handleFunExcludesLock(D->getName(), Mutex.getName(), 587ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul ExpLocation); 588ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul } 589ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul break; 590a2924b488b8d77381779bbb5a0097c467678d39bBrian Paul } 591ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul 592ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul case attr::LockReturned: 593ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul // FIXME: Deal with this attribute. 594ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul break; 595ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul 596ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul // Ignore other (non thread-safety) attributes 597ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul default: 598ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul break; 599ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul } 600ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul } 601ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul} 602a2924b488b8d77381779bbb5a0097c467678d39bBrian Paul 603ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul} // end anonymous namespace 604ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul 605ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul/// \brief Compute the intersection of two locksets and issue warnings for any 606ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul/// locks in the symmetric difference. 607ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul/// 608ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul/// This function is used at a merge point in the CFG when comparing the lockset 609ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul/// of each branch being merged. For example, given the following sequence: 610ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul/// A; if () then B; else C; D; we need to check that the lockset after B and C 611ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul/// are the same. In the event of a difference, we use the intersection of these 612ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul/// two locksets at the start of D. 613ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paulstatic Lockset intersectAndWarn(ThreadSafetyHandler &Handler, 614a2924b488b8d77381779bbb5a0097c467678d39bBrian Paul const Lockset LSet1, const Lockset LSet2, 615ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul Lockset::Factory &Fact, LockErrorKind LEK) { 616ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul Lockset Intersection = LSet1; 617ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul for (Lockset::iterator I = LSet2.begin(), E = LSet2.end(); I != E; ++I) { 618ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul const MutexID &LSet2Mutex = I.getKey(); 619ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul const LockData &LSet2LockData = I.getData(); 620ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul if (const LockData *LD = LSet1.lookup(LSet2Mutex)) { 621ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul if (LD->LKind != LSet2LockData.LKind) { 622ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul Handler.handleExclusiveAndShared(LSet2Mutex.getName(), 623ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul LSet2LockData.AcquireLoc, 624ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul LD->AcquireLoc); 625ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul if (LD->LKind != LK_Exclusive) 626a2924b488b8d77381779bbb5a0097c467678d39bBrian Paul Intersection = Fact.add(Intersection, LSet2Mutex, LSet2LockData); 627ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul } 628ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul } else { 629ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul Handler.handleMutexHeldEndOfScope(LSet2Mutex.getName(), 630ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul LSet2LockData.AcquireLoc, LEK); 631ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul } 632ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul } 633ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul 634ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul for (Lockset::iterator I = LSet1.begin(), E = LSet1.end(); I != E; ++I) { 635ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul if (!LSet2.contains(I.getKey())) { 636ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul const MutexID &Mutex = I.getKey(); 637ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul const LockData &MissingLock = I.getData(); 638a2924b488b8d77381779bbb5a0097c467678d39bBrian Paul Handler.handleMutexHeldEndOfScope(Mutex.getName(), 639ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul MissingLock.AcquireLoc, LEK); 640ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul Intersection = Fact.remove(Intersection, Mutex); 641ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul } 642ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul } 643ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul return Intersection; 644ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul} 645ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul 646ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul/// \brief Returns the location of the first Stmt in a Block. 647ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paulstatic SourceLocation getFirstStmtLocation(const CFGBlock *Block) { 648ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul SourceLocation Loc; 649ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul for (CFGBlock::const_iterator BI = Block->begin(), BE = Block->end(); 650ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul BI != BE; ++BI) { 651ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul if (const CFGStmt *CfgStmt = dyn_cast<CFGStmt>(&(*BI))) { 652ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul Loc = CfgStmt->getStmt()->getLocStart(); 653ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul if (Loc.isValid()) return Loc; 654ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul } 655a2924b488b8d77381779bbb5a0097c467678d39bBrian Paul } 656ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul if (const Stmt *S = Block->getTerminator().getStmt()) { 657ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul Loc = S->getLocStart(); 658ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul if (Loc.isValid()) return Loc; 659ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul } 660ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul return Loc; 661ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul} 662ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul 663ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paulstatic Lockset addLock(ThreadSafetyHandler &Handler, 664ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul Lockset::Factory &LocksetFactory, 665ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul Lockset &LSet, Expr *LockExp, LockKind LK, 666ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul SourceLocation Loc) { 667a2924b488b8d77381779bbb5a0097c467678d39bBrian Paul MutexID Mutex(LockExp, 0); 668ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul if (!Mutex.isValid()) { 669ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul Handler.handleInvalidLockExp(LockExp->getExprLoc()); 670ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul return LSet; 671ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul } 672ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul LockData NewLock(Loc, LK); 673ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul return LocksetFactory.add(LSet, Mutex, NewLock); 674ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul} 675ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul 676ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paulnamespace clang { 677ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paulnamespace thread_safety { 678ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul/// \brief Check a function's CFG for thread-safety violations. 679a2924b488b8d77381779bbb5a0097c467678d39bBrian Paul/// 680ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul/// We traverse the blocks in the CFG, compute the set of mutexes that are held 681ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul/// at the end of each block, and issue warnings for thread safety violations. 682ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul/// Each block in the CFG is traversed exactly once. 683ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paulvoid runThreadSafetyAnalysis(AnalysisContext &AC, 684ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul ThreadSafetyHandler &Handler) { 685ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul CFG *CFGraph = AC.getCFG(); 686ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul if (!CFGraph) return; 687ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul const Decl *D = AC.getDecl(); 688ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul if (D && D->getAttr<NoThreadSafetyAnalysisAttr>()) return; 689ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul 690ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul Lockset::Factory LocksetFactory; 691a2924b488b8d77381779bbb5a0097c467678d39bBrian Paul 692ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul // FIXME: Swith to SmallVector? Otherwise improve performance impact? 693ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul std::vector<Lockset> EntryLocksets(CFGraph->getNumBlockIDs(), 694ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul LocksetFactory.getEmptyMap()); 695ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul std::vector<Lockset> ExitLocksets(CFGraph->getNumBlockIDs(), 696ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul LocksetFactory.getEmptyMap()); 697ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul 698ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul // We need to explore the CFG via a "topological" ordering. 699ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul // That way, we will be guaranteed to have information about required 700ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul // predecessor locksets when exploring a new block. 701ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul TopologicallySortedCFG SortedGraph(CFGraph); 702ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul CFGBlockSet VisitedBlocks(CFGraph); 703a2924b488b8d77381779bbb5a0097c467678d39bBrian Paul 704ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul if (!SortedGraph.empty() && D->hasAttrs()) { 705ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul const CFGBlock *FirstBlock = *SortedGraph.begin(); 706ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul Lockset &InitialLockset = EntryLocksets[FirstBlock->getBlockID()]; 707ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul const AttrVec &ArgAttrs = D->getAttrs(); 708ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul for(unsigned i = 0; i < ArgAttrs.size(); ++i) { 709ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul Attr *Attr = ArgAttrs[i]; 710ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul if (SharedLocksRequiredAttr *SLRAttr 711ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul = dyn_cast<SharedLocksRequiredAttr>(Attr)) { 712ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul for (SharedLocksRequiredAttr::args_iterator 713ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul SLRIter = SLRAttr->args_begin(), 714ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul SLREnd = SLRAttr->args_end(); SLRIter != SLREnd; ++SLRIter) 715a2924b488b8d77381779bbb5a0097c467678d39bBrian Paul InitialLockset = addLock(Handler, LocksetFactory, InitialLockset, 716ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul *SLRIter, LK_Shared, 717ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul getFirstStmtLocation(FirstBlock)); 718ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul } else if (ExclusiveLocksRequiredAttr *ELRAttr 719ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul = dyn_cast<ExclusiveLocksRequiredAttr>(Attr)) { 720ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul for (ExclusiveLocksRequiredAttr::args_iterator 721ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul ELRIter = ELRAttr->args_begin(), 722ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul ELREnd = ELRAttr->args_end(); ELRIter != ELREnd; ++ELRIter) 723ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul InitialLockset = addLock(Handler, LocksetFactory, InitialLockset, 724ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul *ELRIter, LK_Exclusive, 725ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul getFirstStmtLocation(FirstBlock)); 726ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul } 727a2924b488b8d77381779bbb5a0097c467678d39bBrian Paul } 728ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul } 729ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul 730ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul for (TopologicallySortedCFG::iterator I = SortedGraph.begin(), 731ca2618f4b632bf4b357a539a8fb7dafc99b35976Brian Paul E = SortedGraph.end(); I!= E; ++I) { 7322421b25dd777ebfd614ae45907fd4af8c2713102Keith Whitwell const CFGBlock *CurrBlock = *I; 733fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell int CurrBlockID = CurrBlock->getBlockID(); 7342421b25dd777ebfd614ae45907fd4af8c2713102Keith Whitwell 7352421b25dd777ebfd614ae45907fd4af8c2713102Keith Whitwell VisitedBlocks.insert(CurrBlock); 736fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell 737beea704be231ef13edab93a7299efa297039239dBrian Paul // Use the default initial lockset in case there are no predecessors. 738beea704be231ef13edab93a7299efa297039239dBrian Paul Lockset &Entryset = EntryLocksets[CurrBlockID]; 739fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell Lockset &Exitset = ExitLocksets[CurrBlockID]; 740beea704be231ef13edab93a7299efa297039239dBrian Paul 741fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell // Iterate through the predecessor blocks and warn if the lockset for all 742fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell // predecessors is not the same. We take the entry lockset of the current 743fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell // block to be the intersection of all previous locksets. 744fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell // FIXME: By keeping the intersection, we may output more errors in future 745beea704be231ef13edab93a7299efa297039239dBrian Paul // for a lock which is not in the intersection, but was in the union. We 746beea704be231ef13edab93a7299efa297039239dBrian Paul // may want to also keep the union in future. As an example, let's say 747fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell // the intersection contains Mutex L, and the union contains L and M. 748beea704be231ef13edab93a7299efa297039239dBrian Paul // Later we unlock M. At this point, we would output an error because we 749beea704be231ef13edab93a7299efa297039239dBrian Paul // never locked M; although the real error is probably that we forgot to 750fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell // lock M on all code paths. Conversely, let's say that later we lock M. 751fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell // In this case, we should compare against the intersection instead of the 752fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell // union because the real error is probably that we forgot to unlock M on 753beea704be231ef13edab93a7299efa297039239dBrian Paul // all code paths. 754beea704be231ef13edab93a7299efa297039239dBrian Paul bool LocksetInitialized = false; 755fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell for (CFGBlock::const_pred_iterator PI = CurrBlock->pred_begin(), 756beea704be231ef13edab93a7299efa297039239dBrian Paul PE = CurrBlock->pred_end(); PI != PE; ++PI) { 757beea704be231ef13edab93a7299efa297039239dBrian Paul 758fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell // if *PI -> CurrBlock is a back edge 759fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell if (*PI == 0 || !VisitedBlocks.alreadySet(*PI)) 760fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell continue; 761beea704be231ef13edab93a7299efa297039239dBrian Paul 762beea704be231ef13edab93a7299efa297039239dBrian Paul int PrevBlockID = (*PI)->getBlockID(); 763fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell if (!LocksetInitialized) { 764beea704be231ef13edab93a7299efa297039239dBrian Paul Entryset = ExitLocksets[PrevBlockID]; 765beea704be231ef13edab93a7299efa297039239dBrian Paul LocksetInitialized = true; 766fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell } else { 767fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell Entryset = intersectAndWarn(Handler, Entryset, 768fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell ExitLocksets[PrevBlockID], LocksetFactory, 769beea704be231ef13edab93a7299efa297039239dBrian Paul LEK_LockedSomePredecessors); 770beea704be231ef13edab93a7299efa297039239dBrian Paul } 771fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell } 772beea704be231ef13edab93a7299efa297039239dBrian Paul 773beea704be231ef13edab93a7299efa297039239dBrian Paul BuildLockset LocksetBuilder(Handler, Entryset, LocksetFactory); 774fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell for (CFGBlock::const_iterator BI = CurrBlock->begin(), 775fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell BE = CurrBlock->end(); BI != BE; ++BI) { 776fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell if (const CFGStmt *CfgStmt = dyn_cast<CFGStmt>(&*BI)) 777beea704be231ef13edab93a7299efa297039239dBrian Paul LocksetBuilder.Visit(const_cast<Stmt*>(CfgStmt->getStmt())); 778beea704be231ef13edab93a7299efa297039239dBrian Paul } 779beea704be231ef13edab93a7299efa297039239dBrian Paul Exitset = LocksetBuilder.getLockset(); 780fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell 781beea704be231ef13edab93a7299efa297039239dBrian Paul // For every back edge from CurrBlock (the end of the loop) to another block 782beea704be231ef13edab93a7299efa297039239dBrian Paul // (FirstLoopBlock) we need to check that the Lockset of Block is equal to 783fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell // the one held at the beginning of FirstLoopBlock. We can look up the 784fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell // Lockset held at the beginning of FirstLoopBlock in the EntryLockSets map. 785fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell for (CFGBlock::const_succ_iterator SI = CurrBlock->succ_begin(), 786beea704be231ef13edab93a7299efa297039239dBrian Paul SE = CurrBlock->succ_end(); SI != SE; ++SI) { 787beea704be231ef13edab93a7299efa297039239dBrian Paul 788fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell // if CurrBlock -> *SI is *not* a back edge 789beea704be231ef13edab93a7299efa297039239dBrian Paul if (*SI == 0 || !VisitedBlocks.alreadySet(*SI)) 790beea704be231ef13edab93a7299efa297039239dBrian Paul continue; 791fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell 792fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell CFGBlock *FirstLoopBlock = *SI; 793fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell Lockset PreLoop = EntryLocksets[FirstLoopBlock->getBlockID()]; 794beea704be231ef13edab93a7299efa297039239dBrian Paul Lockset LoopEnd = ExitLocksets[CurrBlockID]; 795beea704be231ef13edab93a7299efa297039239dBrian Paul intersectAndWarn(Handler, LoopEnd, PreLoop, LocksetFactory, 796fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell LEK_LockedSomeLoopIterations); 797beea704be231ef13edab93a7299efa297039239dBrian Paul } 798beea704be231ef13edab93a7299efa297039239dBrian Paul } 799fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell 800fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell Lockset InitialLockset = EntryLocksets[CFGraph->getEntry().getBlockID()]; 801fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell Lockset FinalLockset = ExitLocksets[CFGraph->getExit().getBlockID()]; 802fd12b37dbada6f945a94b93ecf332d0b6a8eef06Keith Whitwell intersectAndWarn(Handler, InitialLockset, FinalLockset, LocksetFactory, 80351fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie LEK_LockedAtEndOfFunction); 80451fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie} 80551fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie 80651fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie/// \brief Helper function that returns a LockKind required for the given level 80751fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie/// of access. 80851fcf080a342896ea0bc71dce01e948c810a8db9Dave AirlieLockKind getLockKindFromAccessKind(AccessKind AK) { 80951fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie switch (AK) { 81051fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie case AK_Read : 81151fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie return LK_Shared; 81251fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie case AK_Written : 81351fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie return LK_Exclusive; 81451fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie } 81551fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie llvm_unreachable("Unknown AccessKind"); 81651fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie} 81751fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie}} // end namespace clang::thread_safety 81851fcf080a342896ea0bc71dce01e948c810a8db9Dave Airlie