ThreadSafety.cpp revision 57d2b8aefcf58a7bb82de1cdc69358b1893d1219
124943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner//===- ThreadSafety.cpp ----------------------------------------*- C++ --*-===// 224943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner// 324943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner// The LLVM Compiler Infrastructure 424943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner// 524943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner// This file is distributed under the University of Illinois Open Source 624943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner// License. See LICENSE.TXT for details. 724943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner// 824943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner//===----------------------------------------------------------------------===// 924943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner// 1024943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner// A intra-procedural analysis for thread safety (e.g. deadlocks and race 1124943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner// conditions), based off of an annotation system. 1224943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner// 1324943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner// See http://clang.llvm.org/docs/LanguageExtensions.html#threadsafety for more 1424943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner// information. 1524943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner// 1624943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner//===----------------------------------------------------------------------===// 1724943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner 1824943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner#include "clang/Analysis/Analyses/ThreadSafety.h" 1924943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner#include "clang/Analysis/AnalysisContext.h" 2024943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner#include "clang/Analysis/CFG.h" 2124943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner#include "clang/Analysis/CFGStmtMap.h" 2224943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner#include "clang/AST/DeclCXX.h" 2324943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner#include "clang/AST/ExprCXX.h" 2424943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner#include "clang/AST/StmtCXX.h" 2524943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner#include "clang/AST/StmtVisitor.h" 2624943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner#include "clang/Basic/SourceManager.h" 2724943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner#include "clang/Basic/SourceLocation.h" 2824943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner#include "llvm/ADT/BitVector.h" 2924943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner#include "llvm/ADT/FoldingSet.h" 305a47e8bcc7277dc3683f2af2aeb9717184e8360cJim Ingham#include "llvm/ADT/ImmutableMap.h" 3124943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner#include "llvm/ADT/PostOrderIterator.h" 3224943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner#include "llvm/ADT/SmallVector.h" 3324943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner#include "llvm/ADT/StringRef.h" 3424943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner#include <algorithm> 3524943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner#include <vector> 365a47e8bcc7277dc3683f2af2aeb9717184e8360cJim Ingham 37863aa28adf536c9c008e1590f25da662431d6f13Greg Claytonusing namespace clang; 38863aa28adf536c9c008e1590f25da662431d6f13Greg Claytonusing namespace thread_safety; 395a47e8bcc7277dc3683f2af2aeb9717184e8360cJim Ingham 4024943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner// Key method definition 4124943d2ee8bfaa7cf5893e4709143924157a5c1eChris LattnerThreadSafetyHandler::~ThreadSafetyHandler() {} 42f4124deeb9532044a38c0774ced872f2709347daGreg Clayton 4324943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattnernamespace { 4424943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner 4524943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner/// \brief Implements a set of CFGBlocks using a BitVector. 4624943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner/// 4724943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner/// This class contains a minimal interface, primarily dictated by the SetType 4824943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner/// template parameter of the llvm::po_iterator template, as used with external 4924943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner/// storage. We also use this set to keep track of which CFGBlocks we visit 5024943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner/// during the analysis. 5124943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattnerclass CFGBlockSet { 525f35a4be95aed0e5b2cb36f7d785bcbfc67284aeDaniel Malea llvm::BitVector VisitedBlockIDs; 5324943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner 5424943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattnerpublic: 5524943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner // po_iterator requires this iterator, but the only interface needed is the 5624943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner // value_type typedef. 5724943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner struct iterator { 5824943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner typedef const CFGBlock *value_type; 5924943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner }; 6024943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner 6124943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner CFGBlockSet() {} 627c79a27b955432dfd3ad9439640f0af2eccf37b8Jim Ingham CFGBlockSet(const CFG *G) : VisitedBlockIDs(G->getNumBlockIDs(), false) {} 6324943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner 6404cc48eb5cff32268a822b57f87590c9dc2643f8Jim Ingham /// \brief Set the bit associated with a particular CFGBlock. 65d14a0bddf3f71d531f5a757f102b30917e310512Jim Ingham /// This is the important method for the SetType template parameter. 66d14a0bddf3f71d531f5a757f102b30917e310512Jim Ingham bool insert(const CFGBlock *Block) { 67d14a0bddf3f71d531f5a757f102b30917e310512Jim Ingham // Note that insert() is called by po_iterator, which doesn't check to make 68d14a0bddf3f71d531f5a757f102b30917e310512Jim Ingham // sure that Block is non-null. Moreover, the CFGBlock iterator will 69d14a0bddf3f71d531f5a757f102b30917e310512Jim Ingham // occasionally hand out null pointers for pruned edges, so we catch those 70d14a0bddf3f71d531f5a757f102b30917e310512Jim Ingham // here. 71d14a0bddf3f71d531f5a757f102b30917e310512Jim Ingham if (Block == 0) 72d14a0bddf3f71d531f5a757f102b30917e310512Jim Ingham return false; // if an edge is trivially false. 73d14a0bddf3f71d531f5a757f102b30917e310512Jim Ingham if (VisitedBlockIDs.test(Block->getBlockID())) 7424943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner return false; 7524943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner VisitedBlockIDs.set(Block->getBlockID()); 7624943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner return true; 7724943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner } 7824943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner 7924943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner /// \brief Check if the bit for a CFGBlock has been already set. 8024943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner /// This method is for tracking visited blocks in the main threadsafety loop. 8124943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner /// Block must not be null. 8224943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner bool alreadySet(const CFGBlock *Block) { 8324943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner return VisitedBlockIDs.test(Block->getBlockID()); 8424943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner } 8524943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner}; 8624943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner 8724943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner 8824943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner/// \brief We create a helper class which we use to iterate through CFGBlocks in 89745ac7a5826fe7c392007941a4046bfb1a8dff81Jim Ingham/// the topological order. 9024943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattnerclass TopologicallySortedCFG { 9124943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner typedef llvm::po_iterator<const CFG*, CFGBlockSet, true> po_iterator; 9224943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner 9324943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner std::vector<const CFGBlock*> Blocks; 9424943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner 957c79a27b955432dfd3ad9439640f0af2eccf37b8Jim Inghampublic: 9624943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner typedef std::vector<const CFGBlock*>::reverse_iterator iterator; 9724943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner 9824943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner TopologicallySortedCFG(const CFG *CFGraph) { 99f4124deeb9532044a38c0774ced872f2709347daGreg Clayton Blocks.reserve(CFGraph->getNumBlockIDs()); 10024943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner CFGBlockSet BSet(CFGraph); 101efb4aeba2bd8411ac0aee9934f08959094d50711Jim Ingham 10224943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner for (po_iterator I = po_iterator::begin(CFGraph, BSet), 10324943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner E = po_iterator::end(CFGraph, BSet); I != E; ++I) { 10424943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner Blocks.push_back(*I); 10524943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner } 10624943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner } 10724943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner 10824943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner iterator begin() { 109863aa28adf536c9c008e1590f25da662431d6f13Greg Clayton return Blocks.rbegin(); 11024943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner } 11124943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner 11224943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner iterator end() { 11324943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner return Blocks.rend(); 11424943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner } 11524943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner 11624943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner bool empty() { 11724943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner return begin() == end(); 11824943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner } 11924943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner}; 12024943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner 12124943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner 12224943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner/// \brief A MutexID object uniquely identifies a particular mutex, and 12324943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner/// is built from an Expr* (i.e. calling a lock function). 12424943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner/// 12524943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner/// Thread-safety analysis works by comparing lock expressions. Within the 126952e9dc874944fcdbbb224f3ec4fc2c859376f64Greg Clayton/// body of a function, an expression such as "x->foo->bar.mu" will resolve to 12724943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner/// a particular mutex object at run-time. Subsequent occurrences of the same 12824943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner/// expression (where "same" means syntactic equality) will refer to the same 12924943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner/// run-time object if three conditions hold: 130863aa28adf536c9c008e1590f25da662431d6f13Greg Clayton/// (1) Local variables in the expression, such as "x" have not changed. 131863aa28adf536c9c008e1590f25da662431d6f13Greg Clayton/// (2) Values on the heap that affect the expression have not changed. 132863aa28adf536c9c008e1590f25da662431d6f13Greg Clayton/// (3) The expression involves only pure function calls. 133863aa28adf536c9c008e1590f25da662431d6f13Greg Clayton/// 134863aa28adf536c9c008e1590f25da662431d6f13Greg Clayton/// The current implementation assumes, but does not verify, that multiple uses 135863aa28adf536c9c008e1590f25da662431d6f13Greg Clayton/// of the same lock expression satisfies these criteria. 136863aa28adf536c9c008e1590f25da662431d6f13Greg Clayton/// 137863aa28adf536c9c008e1590f25da662431d6f13Greg Clayton/// Clang introduces an additional wrinkle, which is that it is difficult to 138863aa28adf536c9c008e1590f25da662431d6f13Greg Clayton/// derive canonical expressions, or compare expressions directly for equality. 139863aa28adf536c9c008e1590f25da662431d6f13Greg Clayton/// Thus, we identify a mutex not by an Expr, but by the set of named 140863aa28adf536c9c008e1590f25da662431d6f13Greg Clayton/// declarations that are referenced by the Expr. In other words, 141863aa28adf536c9c008e1590f25da662431d6f13Greg Clayton/// x->foo->bar.mu will be a four element vector with the Decls for 142f4124deeb9532044a38c0774ced872f2709347daGreg Clayton/// mu, bar, and foo, and x. The vector will uniquely identify the expression 14324943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner/// for all practical purposes. 144863aa28adf536c9c008e1590f25da662431d6f13Greg Clayton/// 145efb4aeba2bd8411ac0aee9934f08959094d50711Jim Ingham/// Note we will need to perform substitution on "this" and function parameter 146863aa28adf536c9c008e1590f25da662431d6f13Greg Clayton/// names when constructing a lock expression. 14724943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner/// 14824943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner/// For example: 149863aa28adf536c9c008e1590f25da662431d6f13Greg Clayton/// class C { Mutex Mu; void lock() EXCLUSIVE_LOCK_FUNCTION(this->Mu); }; 150863aa28adf536c9c008e1590f25da662431d6f13Greg Clayton/// void myFunc(C *X) { ... X->lock() ... } 151863aa28adf536c9c008e1590f25da662431d6f13Greg Clayton/// The original expression for the mutex acquired by myFunc is "this->Mu", but 152863aa28adf536c9c008e1590f25da662431d6f13Greg Clayton/// "X" is substituted for "this" so we get X->Mu(); 153863aa28adf536c9c008e1590f25da662431d6f13Greg Clayton/// 15424943d2ee8bfaa7cf5893e4709143924157a5c1eChris Lattner/// For another example: 1555a47e8bcc7277dc3683f2af2aeb9717184e8360cJim Ingham/// foo(MyList *L) EXCLUSIVE_LOCKS_REQUIRED(L->Mu) { ... } 1565a47e8bcc7277dc3683f2af2aeb9717184e8360cJim Ingham/// MyList *MyL; 1575a47e8bcc7277dc3683f2af2aeb9717184e8360cJim Ingham/// foo(MyL); // requires lock MyL->Mu to be held 1585a47e8bcc7277dc3683f2af2aeb9717184e8360cJim Inghamclass MutexID { 1595a47e8bcc7277dc3683f2af2aeb9717184e8360cJim Ingham SmallVector<NamedDecl*, 2> DeclSeq; 1605a47e8bcc7277dc3683f2af2aeb9717184e8360cJim Ingham 1615a47e8bcc7277dc3683f2af2aeb9717184e8360cJim Ingham /// Build a Decl sequence representing the lock from the given expression. 1625a47e8bcc7277dc3683f2af2aeb9717184e8360cJim Ingham /// Recursive function that terminates on DeclRefExpr. 1635a47e8bcc7277dc3683f2af2aeb9717184e8360cJim Ingham /// Note: this function merely creates a MutexID; it does not check to 1645a47e8bcc7277dc3683f2af2aeb9717184e8360cJim Ingham /// ensure that the original expression is a valid mutex expression. 1655a47e8bcc7277dc3683f2af2aeb9717184e8360cJim Ingham void buildMutexID(Expr *Exp, Expr *Parent, int NumArgs, 166 const NamedDecl **FunArgDecls, Expr **FunArgs) { 167 if (!Exp) { 168 DeclSeq.clear(); 169 return; 170 } 171 172 if (DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(Exp)) { 173 if (FunArgDecls) { 174 // Substitute call arguments for references to function parameters 175 for (int i = 0; i < NumArgs; ++i) { 176 if (DRE->getDecl() == FunArgDecls[i]) { 177 buildMutexID(FunArgs[i], 0, 0, 0, 0); 178 return; 179 } 180 } 181 } 182 NamedDecl *ND = cast<NamedDecl>(DRE->getDecl()->getCanonicalDecl()); 183 DeclSeq.push_back(ND); 184 } else if (MemberExpr *ME = dyn_cast<MemberExpr>(Exp)) { 185 NamedDecl *ND = ME->getMemberDecl(); 186 DeclSeq.push_back(ND); 187 buildMutexID(ME->getBase(), Parent, NumArgs, FunArgDecls, FunArgs); 188 } else if (isa<CXXThisExpr>(Exp)) { 189 if (Parent) 190 buildMutexID(Parent, 0, 0, 0, 0); 191 else 192 return; // mutexID is still valid in this case 193 } else if (UnaryOperator *UOE = dyn_cast<UnaryOperator>(Exp)) 194 buildMutexID(UOE->getSubExpr(), Parent, NumArgs, FunArgDecls, FunArgs); 195 else if (CastExpr *CE = dyn_cast<CastExpr>(Exp)) 196 buildMutexID(CE->getSubExpr(), Parent, NumArgs, FunArgDecls, FunArgs); 197 else 198 DeclSeq.clear(); // Mark as invalid lock expression. 199 } 200 201 /// \brief Construct a MutexID from an expression. 202 /// \param MutexExp The original mutex expression within an attribute 203 /// \param DeclExp An expression involving the Decl on which the attribute 204 /// occurs. 205 /// \param D The declaration to which the lock/unlock attribute is attached. 206 void buildMutexIDFromExp(Expr *MutexExp, Expr *DeclExp, const NamedDecl *D) { 207 Expr *Parent = 0; 208 unsigned NumArgs = 0; 209 Expr **FunArgs = 0; 210 SmallVector<const NamedDecl*, 8> FunArgDecls; 211 212 // If we are processing a raw attribute expression, with no substitutions. 213 if (DeclExp == 0) { 214 buildMutexID(MutexExp, 0, 0, 0, 0); 215 return; 216 } 217 218 // Examine DeclExp to find Parent and FunArgs, which are used to substitute 219 // for formal parameters when we call buildMutexID later. 220 if (MemberExpr *ME = dyn_cast<MemberExpr>(DeclExp)) { 221 Parent = ME->getBase(); 222 } else if (CXXMemberCallExpr *CE = dyn_cast<CXXMemberCallExpr>(DeclExp)) { 223 Parent = CE->getImplicitObjectArgument(); 224 NumArgs = CE->getNumArgs(); 225 FunArgs = CE->getArgs(); 226 } else if (CXXConstructExpr *CE = dyn_cast<CXXConstructExpr>(DeclExp)) { 227 Parent = 0; // FIXME -- get the parent from DeclStmt 228 NumArgs = CE->getNumArgs(); 229 FunArgs = CE->getArgs(); 230 } 231 232 // If the attribute has no arguments, then assume the argument is "this". 233 if (MutexExp == 0) { 234 buildMutexID(Parent, 0, 0, 0, 0); 235 return; 236 } 237 238 // FIXME: handle default arguments 239 if (const FunctionDecl *FD = dyn_cast_or_null<FunctionDecl>(D)) { 240 for (unsigned i = 0, ni = FD->getNumParams(); i < ni && i < NumArgs; ++i) { 241 FunArgDecls.push_back(FD->getParamDecl(i)); 242 } 243 } 244 buildMutexID(MutexExp, Parent, NumArgs, &FunArgDecls.front(), FunArgs); 245 } 246 247public: 248 /// \param MutexExp The original mutex expression within an attribute 249 /// \param DeclExp An expression involving the Decl on which the attribute 250 /// occurs. 251 /// \param D The declaration to which the lock/unlock attribute is attached. 252 /// Caller must check isValid() after construction. 253 MutexID(Expr* MutexExp, Expr *DeclExp, const NamedDecl* D) { 254 buildMutexIDFromExp(MutexExp, DeclExp, D); 255 } 256 257 /// Return true if this is a valid decl sequence. 258 /// Caller must call this by hand after construction to handle errors. 259 bool isValid() const { 260 return !DeclSeq.empty(); 261 } 262 263 /// Issue a warning about an invalid lock expression 264 static void warnInvalidLock(ThreadSafetyHandler &Handler, Expr* MutexExp, 265 Expr *DeclExp, const NamedDecl* D) { 266 SourceLocation Loc; 267 if (DeclExp) 268 Loc = DeclExp->getExprLoc(); 269 270 // FIXME: add a note about the attribute location in MutexExp or D 271 if (Loc.isValid()) 272 Handler.handleInvalidLockExp(Loc); 273 } 274 275 bool operator==(const MutexID &other) const { 276 return DeclSeq == other.DeclSeq; 277 } 278 279 bool operator!=(const MutexID &other) const { 280 return !(*this == other); 281 } 282 283 // SmallVector overloads Operator< to do lexicographic ordering. Note that 284 // we use pointer equality (and <) to compare NamedDecls. This means the order 285 // of MutexIDs in a lockset is nondeterministic. In order to output 286 // diagnostics in a deterministic ordering, we must order all diagnostics to 287 // output by SourceLocation when iterating through this lockset. 288 bool operator<(const MutexID &other) const { 289 return DeclSeq < other.DeclSeq; 290 } 291 292 /// \brief Returns the name of the first Decl in the list for a given MutexID; 293 /// e.g. the lock expression foo.bar() has name "bar". 294 /// The caret will point unambiguously to the lock expression, so using this 295 /// name in diagnostics is a way to get simple, and consistent, mutex names. 296 /// We do not want to output the entire expression text for security reasons. 297 StringRef getName() const { 298 assert(isValid()); 299 return DeclSeq.front()->getName(); 300 } 301 302 void Profile(llvm::FoldingSetNodeID &ID) const { 303 for (SmallVectorImpl<NamedDecl*>::const_iterator I = DeclSeq.begin(), 304 E = DeclSeq.end(); I != E; ++I) { 305 ID.AddPointer(*I); 306 } 307 } 308}; 309 310 311/// \brief This is a helper class that stores info about the most recent 312/// accquire of a Lock. 313/// 314/// The main body of the analysis maps MutexIDs to LockDatas. 315struct LockData { 316 SourceLocation AcquireLoc; 317 318 /// \brief LKind stores whether a lock is held shared or exclusively. 319 /// Note that this analysis does not currently support either re-entrant 320 /// locking or lock "upgrading" and "downgrading" between exclusive and 321 /// shared. 322 /// 323 /// FIXME: add support for re-entrant locking and lock up/downgrading 324 LockKind LKind; 325 326 LockData(SourceLocation AcquireLoc, LockKind LKind) 327 : AcquireLoc(AcquireLoc), LKind(LKind) {} 328 329 bool operator==(const LockData &other) const { 330 return AcquireLoc == other.AcquireLoc && LKind == other.LKind; 331 } 332 333 bool operator!=(const LockData &other) const { 334 return !(*this == other); 335 } 336 337 void Profile(llvm::FoldingSetNodeID &ID) const { 338 ID.AddInteger(AcquireLoc.getRawEncoding()); 339 ID.AddInteger(LKind); 340 } 341}; 342 343 344/// A Lockset maps each MutexID (defined above) to information about how it has 345/// been locked. 346typedef llvm::ImmutableMap<MutexID, LockData> Lockset; 347 348/// \brief We use this class to visit different types of expressions in 349/// CFGBlocks, and build up the lockset. 350/// An expression may cause us to add or remove locks from the lockset, or else 351/// output error messages related to missing locks. 352/// FIXME: In future, we may be able to not inherit from a visitor. 353class BuildLockset : public StmtVisitor<BuildLockset> { 354 friend class ThreadSafetyAnalyzer; 355 356 ThreadSafetyHandler &Handler; 357 Lockset LSet; 358 Lockset::Factory &LocksetFactory; 359 360 // Helper functions 361 void removeLock(SourceLocation UnlockLoc, MutexID &Mutex); 362 void addLock(SourceLocation LockLoc, MutexID &Mutex, LockKind LK); 363 364 template <class AttrType> 365 void addLocksToSet(LockKind LK, AttrType *Attr, Expr *Exp, NamedDecl *D); 366 void removeLocksFromSet(UnlockFunctionAttr *Attr, 367 Expr *Exp, NamedDecl* FunDecl); 368 369 const ValueDecl *getValueDecl(Expr *Exp); 370 void warnIfMutexNotHeld (const NamedDecl *D, Expr *Exp, AccessKind AK, 371 Expr *MutexExp, ProtectedOperationKind POK); 372 void checkAccess(Expr *Exp, AccessKind AK); 373 void checkDereference(Expr *Exp, AccessKind AK); 374 void handleCall(Expr *Exp, NamedDecl *D); 375 376 /// \brief Returns true if the lockset contains a lock, regardless of whether 377 /// the lock is held exclusively or shared. 378 bool locksetContains(const MutexID &Lock) const { 379 return LSet.lookup(Lock); 380 } 381 382 /// \brief Returns true if the lockset contains a lock with the passed in 383 /// locktype. 384 bool locksetContains(const MutexID &Lock, LockKind KindRequested) const { 385 const LockData *LockHeld = LSet.lookup(Lock); 386 return (LockHeld && KindRequested == LockHeld->LKind); 387 } 388 389 /// \brief Returns true if the lockset contains a lock with at least the 390 /// passed in locktype. So for example, if we pass in LK_Shared, this function 391 /// returns true if the lock is held LK_Shared or LK_Exclusive. If we pass in 392 /// LK_Exclusive, this function returns true if the lock is held LK_Exclusive. 393 bool locksetContainsAtLeast(const MutexID &Lock, 394 LockKind KindRequested) const { 395 switch (KindRequested) { 396 case LK_Shared: 397 return locksetContains(Lock); 398 case LK_Exclusive: 399 return locksetContains(Lock, KindRequested); 400 } 401 llvm_unreachable("Unknown LockKind"); 402 } 403 404public: 405 BuildLockset(ThreadSafetyHandler &Handler, Lockset LS, Lockset::Factory &F) 406 : StmtVisitor<BuildLockset>(), Handler(Handler), LSet(LS), 407 LocksetFactory(F) {} 408 409 Lockset getLockset() { 410 return LSet; 411 } 412 413 void VisitUnaryOperator(UnaryOperator *UO); 414 void VisitBinaryOperator(BinaryOperator *BO); 415 void VisitCastExpr(CastExpr *CE); 416 void VisitCXXMemberCallExpr(CXXMemberCallExpr *Exp); 417 void VisitCXXConstructExpr(CXXConstructExpr *Exp); 418}; 419 420/// \brief Add a new lock to the lockset, warning if the lock is already there. 421/// \param LockLoc The source location of the acquire 422/// \param LockExp The lock expression corresponding to the lock to be added 423void BuildLockset::addLock(SourceLocation LockLoc, MutexID &Mutex, 424 LockKind LK) { 425 // FIXME: deal with acquired before/after annotations. We can write a first 426 // pass that does the transitive lookup lazily, and refine afterwards. 427 LockData NewLock(LockLoc, LK); 428 429 // FIXME: Don't always warn when we have support for reentrant locks. 430 if (locksetContains(Mutex)) 431 Handler.handleDoubleLock(Mutex.getName(), LockLoc); 432 else 433 LSet = LocksetFactory.add(LSet, Mutex, NewLock); 434} 435 436/// \brief Remove a lock from the lockset, warning if the lock is not there. 437/// \param LockExp The lock expression corresponding to the lock to be removed 438/// \param UnlockLoc The source location of the unlock (only used in error msg) 439void BuildLockset::removeLock(SourceLocation UnlockLoc, MutexID &Mutex) { 440 Lockset NewLSet = LocksetFactory.remove(LSet, Mutex); 441 if(NewLSet == LSet) 442 Handler.handleUnmatchedUnlock(Mutex.getName(), UnlockLoc); 443 else 444 LSet = NewLSet; 445} 446 447/// \brief This function, parameterized by an attribute type, is used to add a 448/// set of locks specified as attribute arguments to the lockset. 449template <typename AttrType> 450void BuildLockset::addLocksToSet(LockKind LK, AttrType *Attr, 451 Expr *Exp, NamedDecl* FunDecl) { 452 typedef typename AttrType::args_iterator iterator_type; 453 454 SourceLocation ExpLocation = Exp->getExprLoc(); 455 456 if (Attr->args_size() == 0) { 457 // The mutex held is the "this" object. 458 MutexID Mutex(0, Exp, FunDecl); 459 if (!Mutex.isValid()) 460 MutexID::warnInvalidLock(Handler, 0, Exp, FunDecl); 461 else 462 addLock(ExpLocation, Mutex, LK); 463 return; 464 } 465 466 for (iterator_type I=Attr->args_begin(), E=Attr->args_end(); I != E; ++I) { 467 MutexID Mutex(*I, Exp, FunDecl); 468 if (!Mutex.isValid()) 469 MutexID::warnInvalidLock(Handler, *I, Exp, FunDecl); 470 else 471 addLock(ExpLocation, Mutex, LK); 472 } 473} 474 475/// \brief This function removes a set of locks specified as attribute 476/// arguments from the lockset. 477void BuildLockset::removeLocksFromSet(UnlockFunctionAttr *Attr, 478 Expr *Exp, NamedDecl* FunDecl) { 479 SourceLocation ExpLocation; 480 if (Exp) ExpLocation = Exp->getExprLoc(); 481 482 if (Attr->args_size() == 0) { 483 // The mutex held is the "this" object. 484 MutexID Mu(0, Exp, FunDecl); 485 if (!Mu.isValid()) 486 MutexID::warnInvalidLock(Handler, 0, Exp, FunDecl); 487 else 488 removeLock(ExpLocation, Mu); 489 return; 490 } 491 492 for (UnlockFunctionAttr::args_iterator I = Attr->args_begin(), 493 E = Attr->args_end(); I != E; ++I) { 494 MutexID Mutex(*I, Exp, FunDecl); 495 if (!Mutex.isValid()) 496 MutexID::warnInvalidLock(Handler, *I, Exp, FunDecl); 497 else 498 removeLock(ExpLocation, Mutex); 499 } 500} 501 502/// \brief Gets the value decl pointer from DeclRefExprs or MemberExprs 503const ValueDecl *BuildLockset::getValueDecl(Expr *Exp) { 504 if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(Exp)) 505 return DR->getDecl(); 506 507 if (const MemberExpr *ME = dyn_cast<MemberExpr>(Exp)) 508 return ME->getMemberDecl(); 509 510 return 0; 511} 512 513/// \brief Warn if the LSet does not contain a lock sufficient to protect access 514/// of at least the passed in AccessKind. 515void BuildLockset::warnIfMutexNotHeld(const NamedDecl *D, Expr *Exp, 516 AccessKind AK, Expr *MutexExp, 517 ProtectedOperationKind POK) { 518 LockKind LK = getLockKindFromAccessKind(AK); 519 520 MutexID Mutex(MutexExp, Exp, D); 521 if (!Mutex.isValid()) 522 MutexID::warnInvalidLock(Handler, MutexExp, Exp, D); 523 else if (!locksetContainsAtLeast(Mutex, LK)) 524 Handler.handleMutexNotHeld(D, POK, Mutex.getName(), LK, Exp->getExprLoc()); 525} 526 527/// \brief This method identifies variable dereferences and checks pt_guarded_by 528/// and pt_guarded_var annotations. Note that we only check these annotations 529/// at the time a pointer is dereferenced. 530/// FIXME: We need to check for other types of pointer dereferences 531/// (e.g. [], ->) and deal with them here. 532/// \param Exp An expression that has been read or written. 533void BuildLockset::checkDereference(Expr *Exp, AccessKind AK) { 534 UnaryOperator *UO = dyn_cast<UnaryOperator>(Exp); 535 if (!UO || UO->getOpcode() != clang::UO_Deref) 536 return; 537 Exp = UO->getSubExpr()->IgnoreParenCasts(); 538 539 const ValueDecl *D = getValueDecl(Exp); 540 if(!D || !D->hasAttrs()) 541 return; 542 543 if (D->getAttr<PtGuardedVarAttr>() && LSet.isEmpty()) 544 Handler.handleNoMutexHeld(D, POK_VarDereference, AK, Exp->getExprLoc()); 545 546 const AttrVec &ArgAttrs = D->getAttrs(); 547 for(unsigned i = 0, Size = ArgAttrs.size(); i < Size; ++i) 548 if (PtGuardedByAttr *PGBAttr = dyn_cast<PtGuardedByAttr>(ArgAttrs[i])) 549 warnIfMutexNotHeld(D, Exp, AK, PGBAttr->getArg(), POK_VarDereference); 550} 551 552/// \brief Checks guarded_by and guarded_var attributes. 553/// Whenever we identify an access (read or write) of a DeclRefExpr or 554/// MemberExpr, we need to check whether there are any guarded_by or 555/// guarded_var attributes, and make sure we hold the appropriate mutexes. 556void BuildLockset::checkAccess(Expr *Exp, AccessKind AK) { 557 const ValueDecl *D = getValueDecl(Exp); 558 if(!D || !D->hasAttrs()) 559 return; 560 561 if (D->getAttr<GuardedVarAttr>() && LSet.isEmpty()) 562 Handler.handleNoMutexHeld(D, POK_VarAccess, AK, Exp->getExprLoc()); 563 564 const AttrVec &ArgAttrs = D->getAttrs(); 565 for(unsigned i = 0, Size = ArgAttrs.size(); i < Size; ++i) 566 if (GuardedByAttr *GBAttr = dyn_cast<GuardedByAttr>(ArgAttrs[i])) 567 warnIfMutexNotHeld(D, Exp, AK, GBAttr->getArg(), POK_VarAccess); 568} 569 570/// \brief Process a function call, method call, constructor call, 571/// or destructor call. This involves looking at the attributes on the 572/// corresponding function/method/constructor/destructor, issuing warnings, 573/// and updating the locksets accordingly. 574/// 575/// FIXME: For classes annotated with one of the guarded annotations, we need 576/// to treat const method calls as reads and non-const method calls as writes, 577/// and check that the appropriate locks are held. Non-const method calls with 578/// the same signature as const method calls can be also treated as reads. 579/// 580/// FIXME: We need to also visit CallExprs to catch/check global functions. 581/// 582/// FIXME: Do not flag an error for member variables accessed in constructors/ 583/// destructors 584void BuildLockset::handleCall(Expr *Exp, NamedDecl *D) { 585 AttrVec &ArgAttrs = D->getAttrs(); 586 for(unsigned i = 0; i < ArgAttrs.size(); ++i) { 587 Attr *Attr = ArgAttrs[i]; 588 switch (Attr->getKind()) { 589 // When we encounter an exclusive lock function, we need to add the lock 590 // to our lockset with kind exclusive. 591 case attr::ExclusiveLockFunction: { 592 ExclusiveLockFunctionAttr *A = cast<ExclusiveLockFunctionAttr>(Attr); 593 addLocksToSet(LK_Exclusive, A, Exp, D); 594 break; 595 } 596 597 // When we encounter a shared lock function, we need to add the lock 598 // to our lockset with kind shared. 599 case attr::SharedLockFunction: { 600 SharedLockFunctionAttr *A = cast<SharedLockFunctionAttr>(Attr); 601 addLocksToSet(LK_Shared, A, Exp, D); 602 break; 603 } 604 605 // When we encounter an unlock function, we need to remove unlocked 606 // mutexes from the lockset, and flag a warning if they are not there. 607 case attr::UnlockFunction: { 608 UnlockFunctionAttr *UFAttr = cast<UnlockFunctionAttr>(Attr); 609 removeLocksFromSet(UFAttr, Exp, D); 610 break; 611 } 612 613 case attr::ExclusiveLocksRequired: { 614 ExclusiveLocksRequiredAttr *ELRAttr = 615 cast<ExclusiveLocksRequiredAttr>(Attr); 616 617 for (ExclusiveLocksRequiredAttr::args_iterator 618 I = ELRAttr->args_begin(), E = ELRAttr->args_end(); I != E; ++I) 619 warnIfMutexNotHeld(D, Exp, AK_Written, *I, POK_FunctionCall); 620 break; 621 } 622 623 case attr::SharedLocksRequired: { 624 SharedLocksRequiredAttr *SLRAttr = cast<SharedLocksRequiredAttr>(Attr); 625 626 for (SharedLocksRequiredAttr::args_iterator I = SLRAttr->args_begin(), 627 E = SLRAttr->args_end(); I != E; ++I) 628 warnIfMutexNotHeld(D, Exp, AK_Read, *I, POK_FunctionCall); 629 break; 630 } 631 632 case attr::LocksExcluded: { 633 LocksExcludedAttr *LEAttr = cast<LocksExcludedAttr>(Attr); 634 for (LocksExcludedAttr::args_iterator I = LEAttr->args_begin(), 635 E = LEAttr->args_end(); I != E; ++I) { 636 MutexID Mutex(*I, Exp, D); 637 if (!Mutex.isValid()) 638 MutexID::warnInvalidLock(Handler, *I, Exp, D); 639 else if (locksetContains(Mutex)) 640 Handler.handleFunExcludesLock(D->getName(), Mutex.getName(), 641 Exp->getExprLoc()); 642 } 643 break; 644 } 645 646 // Ignore other (non thread-safety) attributes 647 default: 648 break; 649 } 650 } 651} 652 653/// \brief For unary operations which read and write a variable, we need to 654/// check whether we hold any required mutexes. Reads are checked in 655/// VisitCastExpr. 656void BuildLockset::VisitUnaryOperator(UnaryOperator *UO) { 657 switch (UO->getOpcode()) { 658 case clang::UO_PostDec: 659 case clang::UO_PostInc: 660 case clang::UO_PreDec: 661 case clang::UO_PreInc: { 662 Expr *SubExp = UO->getSubExpr()->IgnoreParenCasts(); 663 checkAccess(SubExp, AK_Written); 664 checkDereference(SubExp, AK_Written); 665 break; 666 } 667 default: 668 break; 669 } 670} 671 672/// For binary operations which assign to a variable (writes), we need to check 673/// whether we hold any required mutexes. 674/// FIXME: Deal with non-primitive types. 675void BuildLockset::VisitBinaryOperator(BinaryOperator *BO) { 676 if (!BO->isAssignmentOp()) 677 return; 678 Expr *LHSExp = BO->getLHS()->IgnoreParenCasts(); 679 checkAccess(LHSExp, AK_Written); 680 checkDereference(LHSExp, AK_Written); 681} 682 683/// Whenever we do an LValue to Rvalue cast, we are reading a variable and 684/// need to ensure we hold any required mutexes. 685/// FIXME: Deal with non-primitive types. 686void BuildLockset::VisitCastExpr(CastExpr *CE) { 687 if (CE->getCastKind() != CK_LValueToRValue) 688 return; 689 Expr *SubExp = CE->getSubExpr()->IgnoreParenCasts(); 690 checkAccess(SubExp, AK_Read); 691 checkDereference(SubExp, AK_Read); 692} 693 694 695void BuildLockset::VisitCXXMemberCallExpr(CXXMemberCallExpr *Exp) { 696 NamedDecl *D = dyn_cast_or_null<NamedDecl>(Exp->getCalleeDecl()); 697 if(!D || !D->hasAttrs()) 698 return; 699 handleCall(Exp, D); 700} 701 702void BuildLockset::VisitCXXConstructExpr(CXXConstructExpr *Exp) { 703 NamedDecl *D = cast<NamedDecl>(Exp->getConstructor()); 704 if(!D || !D->hasAttrs()) 705 return; 706 handleCall(Exp, D); 707} 708 709 710/// \brief Class which implements the core thread safety analysis routines. 711class ThreadSafetyAnalyzer { 712 ThreadSafetyHandler &Handler; 713 Lockset::Factory LocksetFactory; 714 715public: 716 ThreadSafetyAnalyzer(ThreadSafetyHandler &H) : Handler(H) {} 717 718 Lockset intersectAndWarn(const Lockset LSet1, const Lockset LSet2, 719 LockErrorKind LEK); 720 721 Lockset addLock(Lockset &LSet, Expr *MutexExp, const NamedDecl *D, 722 LockKind LK, SourceLocation Loc); 723 724 void runAnalysis(AnalysisContext &AC); 725}; 726 727/// \brief Compute the intersection of two locksets and issue warnings for any 728/// locks in the symmetric difference. 729/// 730/// This function is used at a merge point in the CFG when comparing the lockset 731/// of each branch being merged. For example, given the following sequence: 732/// A; if () then B; else C; D; we need to check that the lockset after B and C 733/// are the same. In the event of a difference, we use the intersection of these 734/// two locksets at the start of D. 735Lockset ThreadSafetyAnalyzer::intersectAndWarn(const Lockset LSet1, 736 const Lockset LSet2, 737 LockErrorKind LEK) { 738 Lockset Intersection = LSet1; 739 for (Lockset::iterator I = LSet2.begin(), E = LSet2.end(); I != E; ++I) { 740 const MutexID &LSet2Mutex = I.getKey(); 741 const LockData &LSet2LockData = I.getData(); 742 if (const LockData *LD = LSet1.lookup(LSet2Mutex)) { 743 if (LD->LKind != LSet2LockData.LKind) { 744 Handler.handleExclusiveAndShared(LSet2Mutex.getName(), 745 LSet2LockData.AcquireLoc, 746 LD->AcquireLoc); 747 if (LD->LKind != LK_Exclusive) 748 Intersection = LocksetFactory.add(Intersection, LSet2Mutex, 749 LSet2LockData); 750 } 751 } else { 752 Handler.handleMutexHeldEndOfScope(LSet2Mutex.getName(), 753 LSet2LockData.AcquireLoc, LEK); 754 } 755 } 756 757 for (Lockset::iterator I = LSet1.begin(), E = LSet1.end(); I != E; ++I) { 758 if (!LSet2.contains(I.getKey())) { 759 const MutexID &Mutex = I.getKey(); 760 const LockData &MissingLock = I.getData(); 761 Handler.handleMutexHeldEndOfScope(Mutex.getName(), 762 MissingLock.AcquireLoc, LEK); 763 Intersection = LocksetFactory.remove(Intersection, Mutex); 764 } 765 } 766 return Intersection; 767} 768 769Lockset ThreadSafetyAnalyzer::addLock(Lockset &LSet, Expr *MutexExp, 770 const NamedDecl *D, 771 LockKind LK, SourceLocation Loc) { 772 MutexID Mutex(MutexExp, 0, D); 773 if (!Mutex.isValid()) { 774 MutexID::warnInvalidLock(Handler, MutexExp, 0, D); 775 return LSet; 776 } 777 LockData NewLock(Loc, LK); 778 return LocksetFactory.add(LSet, Mutex, NewLock); 779} 780 781/// \brief Check a function's CFG for thread-safety violations. 782/// 783/// We traverse the blocks in the CFG, compute the set of mutexes that are held 784/// at the end of each block, and issue warnings for thread safety violations. 785/// Each block in the CFG is traversed exactly once. 786void ThreadSafetyAnalyzer::runAnalysis(AnalysisContext &AC) { 787 CFG *CFGraph = AC.getCFG(); 788 if (!CFGraph) return; 789 const NamedDecl *D = dyn_cast_or_null<NamedDecl>(AC.getDecl()); 790 791 if (!D) 792 return; // Ignore anonymous functions for now. 793 if (D->getAttr<NoThreadSafetyAnalysisAttr>()) 794 return; 795 796 // FIXME: Switch to SmallVector? Otherwise improve performance impact? 797 std::vector<Lockset> EntryLocksets(CFGraph->getNumBlockIDs(), 798 LocksetFactory.getEmptyMap()); 799 std::vector<Lockset> ExitLocksets(CFGraph->getNumBlockIDs(), 800 LocksetFactory.getEmptyMap()); 801 802 // We need to explore the CFG via a "topological" ordering. 803 // That way, we will be guaranteed to have information about required 804 // predecessor locksets when exploring a new block. 805 TopologicallySortedCFG SortedGraph(CFGraph); 806 CFGBlockSet VisitedBlocks(CFGraph); 807 808 // Add locks from exclusive_locks_required and shared_locks_required 809 // to initial lockset. 810 if (!SortedGraph.empty() && D->hasAttrs()) { 811 const CFGBlock *FirstBlock = *SortedGraph.begin(); 812 Lockset &InitialLockset = EntryLocksets[FirstBlock->getBlockID()]; 813 const AttrVec &ArgAttrs = D->getAttrs(); 814 for(unsigned i = 0; i < ArgAttrs.size(); ++i) { 815 Attr *Attr = ArgAttrs[i]; 816 SourceLocation AttrLoc = Attr->getLocation(); 817 if (SharedLocksRequiredAttr *SLRAttr 818 = dyn_cast<SharedLocksRequiredAttr>(Attr)) { 819 for (SharedLocksRequiredAttr::args_iterator 820 SLRIter = SLRAttr->args_begin(), 821 SLREnd = SLRAttr->args_end(); SLRIter != SLREnd; ++SLRIter) 822 InitialLockset = addLock(InitialLockset, 823 *SLRIter, D, LK_Shared, 824 AttrLoc); 825 } else if (ExclusiveLocksRequiredAttr *ELRAttr 826 = dyn_cast<ExclusiveLocksRequiredAttr>(Attr)) { 827 for (ExclusiveLocksRequiredAttr::args_iterator 828 ELRIter = ELRAttr->args_begin(), 829 ELREnd = ELRAttr->args_end(); ELRIter != ELREnd; ++ELRIter) 830 InitialLockset = addLock(InitialLockset, 831 *ELRIter, D, LK_Exclusive, 832 AttrLoc); 833 } 834 } 835 } 836 837 for (TopologicallySortedCFG::iterator I = SortedGraph.begin(), 838 E = SortedGraph.end(); I!= E; ++I) { 839 const CFGBlock *CurrBlock = *I; 840 int CurrBlockID = CurrBlock->getBlockID(); 841 842 VisitedBlocks.insert(CurrBlock); 843 844 // Use the default initial lockset in case there are no predecessors. 845 Lockset &Entryset = EntryLocksets[CurrBlockID]; 846 Lockset &Exitset = ExitLocksets[CurrBlockID]; 847 848 // Iterate through the predecessor blocks and warn if the lockset for all 849 // predecessors is not the same. We take the entry lockset of the current 850 // block to be the intersection of all previous locksets. 851 // FIXME: By keeping the intersection, we may output more errors in future 852 // for a lock which is not in the intersection, but was in the union. We 853 // may want to also keep the union in future. As an example, let's say 854 // the intersection contains Mutex L, and the union contains L and M. 855 // Later we unlock M. At this point, we would output an error because we 856 // never locked M; although the real error is probably that we forgot to 857 // lock M on all code paths. Conversely, let's say that later we lock M. 858 // In this case, we should compare against the intersection instead of the 859 // union because the real error is probably that we forgot to unlock M on 860 // all code paths. 861 bool LocksetInitialized = false; 862 for (CFGBlock::const_pred_iterator PI = CurrBlock->pred_begin(), 863 PE = CurrBlock->pred_end(); PI != PE; ++PI) { 864 865 // if *PI -> CurrBlock is a back edge 866 if (*PI == 0 || !VisitedBlocks.alreadySet(*PI)) 867 continue; 868 869 int PrevBlockID = (*PI)->getBlockID(); 870 if (!LocksetInitialized) { 871 Entryset = ExitLocksets[PrevBlockID]; 872 LocksetInitialized = true; 873 } else { 874 Entryset = intersectAndWarn(Entryset, ExitLocksets[PrevBlockID], 875 LEK_LockedSomePredecessors); 876 } 877 } 878 879 BuildLockset LocksetBuilder(Handler, Entryset, LocksetFactory); 880 for (CFGBlock::const_iterator BI = CurrBlock->begin(), 881 BE = CurrBlock->end(); BI != BE; ++BI) { 882 if (const CFGStmt *CfgStmt = dyn_cast<CFGStmt>(&*BI)) 883 LocksetBuilder.Visit(const_cast<Stmt*>(CfgStmt->getStmt())); 884 } 885 Exitset = LocksetBuilder.getLockset(); 886 887 // For every back edge from CurrBlock (the end of the loop) to another block 888 // (FirstLoopBlock) we need to check that the Lockset of Block is equal to 889 // the one held at the beginning of FirstLoopBlock. We can look up the 890 // Lockset held at the beginning of FirstLoopBlock in the EntryLockSets map. 891 for (CFGBlock::const_succ_iterator SI = CurrBlock->succ_begin(), 892 SE = CurrBlock->succ_end(); SI != SE; ++SI) { 893 894 // if CurrBlock -> *SI is *not* a back edge 895 if (*SI == 0 || !VisitedBlocks.alreadySet(*SI)) 896 continue; 897 898 CFGBlock *FirstLoopBlock = *SI; 899 Lockset PreLoop = EntryLocksets[FirstLoopBlock->getBlockID()]; 900 Lockset LoopEnd = ExitLocksets[CurrBlockID]; 901 intersectAndWarn(LoopEnd, PreLoop, LEK_LockedSomeLoopIterations); 902 } 903 } 904 905 Lockset InitialLockset = EntryLocksets[CFGraph->getEntry().getBlockID()]; 906 Lockset FinalLockset = ExitLocksets[CFGraph->getExit().getBlockID()]; 907 908 // FIXME: Should we call this function for all blocks which exit the function? 909 intersectAndWarn(InitialLockset, FinalLockset, LEK_LockedAtEndOfFunction); 910} 911 912} // end anonymous namespace 913 914 915namespace clang { 916namespace thread_safety { 917 918/// \brief Check a function's CFG for thread-safety violations. 919/// 920/// We traverse the blocks in the CFG, compute the set of mutexes that are held 921/// at the end of each block, and issue warnings for thread safety violations. 922/// Each block in the CFG is traversed exactly once. 923void runThreadSafetyAnalysis(AnalysisContext &AC, 924 ThreadSafetyHandler &Handler) { 925 ThreadSafetyAnalyzer Analyzer(Handler); 926 Analyzer.runAnalysis(AC); 927} 928 929/// \brief Helper function that returns a LockKind required for the given level 930/// of access. 931LockKind getLockKindFromAccessKind(AccessKind AK) { 932 switch (AK) { 933 case AK_Read : 934 return LK_Shared; 935 case AK_Written : 936 return LK_Exclusive; 937 } 938 llvm_unreachable("Unknown AccessKind"); 939} 940 941}} // end namespace clang::thread_safety 942