ThreadSafety.cpp revision 9d6e7f3e12f1a825377ace33161e80caeda8cd06
1//===- ThreadSafety.cpp ----------------------------------------*- C++ --*-===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// A intra-procedural analysis for thread safety (e.g. deadlocks and race 11// conditions), based off of an annotation system. 12// 13// See http://clang.llvm.org/docs/LanguageExtensions.html#threadsafety for more 14// information. 15// 16//===----------------------------------------------------------------------===// 17 18#include "clang/Analysis/Analyses/ThreadSafety.h" 19#include "clang/Analysis/Analyses/PostOrderCFGView.h" 20#include "clang/Analysis/AnalysisContext.h" 21#include "clang/Analysis/CFG.h" 22#include "clang/Analysis/CFGStmtMap.h" 23#include "clang/AST/DeclCXX.h" 24#include "clang/AST/ExprCXX.h" 25#include "clang/AST/StmtCXX.h" 26#include "clang/AST/StmtVisitor.h" 27#include "clang/Basic/SourceManager.h" 28#include "clang/Basic/SourceLocation.h" 29#include "llvm/ADT/BitVector.h" 30#include "llvm/ADT/FoldingSet.h" 31#include "llvm/ADT/ImmutableMap.h" 32#include "llvm/ADT/PostOrderIterator.h" 33#include "llvm/ADT/SmallVector.h" 34#include "llvm/ADT/StringRef.h" 35#include "llvm/Support/raw_ostream.h" 36#include <algorithm> 37#include <utility> 38#include <vector> 39 40using namespace clang; 41using namespace thread_safety; 42 43// Key method definition 44ThreadSafetyHandler::~ThreadSafetyHandler() {} 45 46namespace { 47 48/// \brief A MutexID object uniquely identifies a particular mutex, and 49/// is built from an Expr* (i.e. calling a lock function). 50/// 51/// Thread-safety analysis works by comparing lock expressions. Within the 52/// body of a function, an expression such as "x->foo->bar.mu" will resolve to 53/// a particular mutex object at run-time. Subsequent occurrences of the same 54/// expression (where "same" means syntactic equality) will refer to the same 55/// run-time object if three conditions hold: 56/// (1) Local variables in the expression, such as "x" have not changed. 57/// (2) Values on the heap that affect the expression have not changed. 58/// (3) The expression involves only pure function calls. 59/// 60/// The current implementation assumes, but does not verify, that multiple uses 61/// of the same lock expression satisfies these criteria. 62/// 63/// Clang introduces an additional wrinkle, which is that it is difficult to 64/// derive canonical expressions, or compare expressions directly for equality. 65/// Thus, we identify a mutex not by an Expr, but by the list of named 66/// declarations that are referenced by the Expr. In other words, 67/// x->foo->bar.mu will be a four element vector with the Decls for 68/// mu, bar, and foo, and x. The vector will uniquely identify the expression 69/// for all practical purposes. Null is used to denote 'this'. 70/// 71/// Note we will need to perform substitution on "this" and function parameter 72/// names when constructing a lock expression. 73/// 74/// For example: 75/// class C { Mutex Mu; void lock() EXCLUSIVE_LOCK_FUNCTION(this->Mu); }; 76/// void myFunc(C *X) { ... X->lock() ... } 77/// The original expression for the mutex acquired by myFunc is "this->Mu", but 78/// "X" is substituted for "this" so we get X->Mu(); 79/// 80/// For another example: 81/// foo(MyList *L) EXCLUSIVE_LOCKS_REQUIRED(L->Mu) { ... } 82/// MyList *MyL; 83/// foo(MyL); // requires lock MyL->Mu to be held 84class MutexID { 85 SmallVector<NamedDecl*, 2> DeclSeq; 86 87 /// \brief Encapsulates the lexical context of a function call. The lexical 88 /// context includes the arguments to the call, including the implicit object 89 /// argument. When an attribute containing a mutex expression is attached to 90 /// a method, the expression may refer to formal parameters of the method. 91 /// Actual arguments must be substituted for formal parameters to derive 92 /// the appropriate mutex expression in the lexical context where the function 93 /// is called. PrevCtx holds the context in which the arguments themselves 94 /// should be evaluated; multiple calling contexts can be chained together 95 /// by the lock_returned attribute. 96 struct CallingContext { 97 const NamedDecl* AttrDecl; // The decl to which the attribute is attached. 98 Expr* SelfArg; // Implicit object argument -- e.g. 'this' 99 unsigned NumArgs; // Number of funArgs 100 Expr** FunArgs; // Function arguments 101 CallingContext* PrevCtx; // The previous context; or 0 if none. 102 103 CallingContext(const NamedDecl* D = 0, Expr* S = 0, 104 unsigned N = 0, Expr** A = 0, CallingContext* P = 0) 105 : AttrDecl(D), SelfArg(S), NumArgs(N), FunArgs(A), PrevCtx(P) 106 { } 107 }; 108 109 /// Build a Decl sequence representing the lock from the given expression. 110 /// Recursive function that terminates on DeclRefExpr. 111 /// Note: this function merely creates a MutexID; it does not check to 112 /// ensure that the original expression is a valid mutex expression. 113 void buildMutexID(Expr *Exp, CallingContext* CallCtx) { 114 if (!Exp) { 115 DeclSeq.clear(); 116 return; 117 } 118 119 if (DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(Exp)) { 120 NamedDecl *ND = cast<NamedDecl>(DRE->getDecl()->getCanonicalDecl()); 121 ParmVarDecl *PV = dyn_cast_or_null<ParmVarDecl>(ND); 122 if (PV) { 123 FunctionDecl *FD = 124 cast<FunctionDecl>(PV->getDeclContext())->getCanonicalDecl(); 125 unsigned i = PV->getFunctionScopeIndex(); 126 127 if (CallCtx && CallCtx->FunArgs && 128 FD == CallCtx->AttrDecl->getCanonicalDecl()) { 129 // Substitute call arguments for references to function parameters 130 assert(i < CallCtx->NumArgs); 131 buildMutexID(CallCtx->FunArgs[i], CallCtx->PrevCtx); 132 return; 133 } 134 // Map the param back to the param of the original function declaration. 135 DeclSeq.push_back(FD->getParamDecl(i)); 136 return; 137 } 138 // Not a function parameter -- just store the reference. 139 DeclSeq.push_back(ND); 140 } else if (isa<CXXThisExpr>(Exp)) { 141 // Substitute parent for 'this' 142 if (CallCtx && CallCtx->SelfArg) 143 buildMutexID(CallCtx->SelfArg, CallCtx->PrevCtx); 144 else { 145 DeclSeq.push_back(0); // Use 0 to represent 'this'. 146 return; // mutexID is still valid in this case 147 } 148 } else if (MemberExpr *ME = dyn_cast<MemberExpr>(Exp)) { 149 NamedDecl *ND = ME->getMemberDecl(); 150 DeclSeq.push_back(ND); 151 buildMutexID(ME->getBase(), CallCtx); 152 } else if (CXXMemberCallExpr *CMCE = dyn_cast<CXXMemberCallExpr>(Exp)) { 153 // When calling a function with a lock_returned attribute, replace 154 // the function call with the expression in lock_returned. 155 if (LockReturnedAttr* At = 156 CMCE->getMethodDecl()->getAttr<LockReturnedAttr>()) { 157 CallingContext LRCallCtx(CMCE->getMethodDecl()); 158 LRCallCtx.SelfArg = CMCE->getImplicitObjectArgument(); 159 LRCallCtx.NumArgs = CMCE->getNumArgs(); 160 LRCallCtx.FunArgs = CMCE->getArgs(); 161 LRCallCtx.PrevCtx = CallCtx; 162 buildMutexID(At->getArg(), &LRCallCtx); 163 return; 164 } 165 DeclSeq.push_back(CMCE->getMethodDecl()->getCanonicalDecl()); 166 buildMutexID(CMCE->getImplicitObjectArgument(), CallCtx); 167 unsigned NumCallArgs = CMCE->getNumArgs(); 168 Expr** CallArgs = CMCE->getArgs(); 169 for (unsigned i = 0; i < NumCallArgs; ++i) { 170 buildMutexID(CallArgs[i], CallCtx); 171 } 172 } else if (CallExpr *CE = dyn_cast<CallExpr>(Exp)) { 173 if (LockReturnedAttr* At = 174 CE->getDirectCallee()->getAttr<LockReturnedAttr>()) { 175 CallingContext LRCallCtx(CE->getDirectCallee()); 176 LRCallCtx.NumArgs = CE->getNumArgs(); 177 LRCallCtx.FunArgs = CE->getArgs(); 178 LRCallCtx.PrevCtx = CallCtx; 179 buildMutexID(At->getArg(), &LRCallCtx); 180 return; 181 } 182 buildMutexID(CE->getCallee(), CallCtx); 183 unsigned NumCallArgs = CE->getNumArgs(); 184 Expr** CallArgs = CE->getArgs(); 185 for (unsigned i = 0; i < NumCallArgs; ++i) { 186 buildMutexID(CallArgs[i], CallCtx); 187 } 188 } else if (BinaryOperator *BOE = dyn_cast<BinaryOperator>(Exp)) { 189 buildMutexID(BOE->getLHS(), CallCtx); 190 buildMutexID(BOE->getRHS(), CallCtx); 191 } else if (UnaryOperator *UOE = dyn_cast<UnaryOperator>(Exp)) { 192 buildMutexID(UOE->getSubExpr(), CallCtx); 193 } else if (ArraySubscriptExpr *ASE = dyn_cast<ArraySubscriptExpr>(Exp)) { 194 buildMutexID(ASE->getBase(), CallCtx); 195 buildMutexID(ASE->getIdx(), CallCtx); 196 } else if (AbstractConditionalOperator *CE = 197 dyn_cast<AbstractConditionalOperator>(Exp)) { 198 buildMutexID(CE->getCond(), CallCtx); 199 buildMutexID(CE->getTrueExpr(), CallCtx); 200 buildMutexID(CE->getFalseExpr(), CallCtx); 201 } else if (ChooseExpr *CE = dyn_cast<ChooseExpr>(Exp)) { 202 buildMutexID(CE->getCond(), CallCtx); 203 buildMutexID(CE->getLHS(), CallCtx); 204 buildMutexID(CE->getRHS(), CallCtx); 205 } else if (CastExpr *CE = dyn_cast<CastExpr>(Exp)) { 206 buildMutexID(CE->getSubExpr(), CallCtx); 207 } else if (ParenExpr *PE = dyn_cast<ParenExpr>(Exp)) { 208 buildMutexID(PE->getSubExpr(), CallCtx); 209 } else if (ExprWithCleanups *EWC = dyn_cast<ExprWithCleanups>(Exp)) { 210 buildMutexID(EWC->getSubExpr(), CallCtx); 211 } else if (isa<CharacterLiteral>(Exp) || 212 isa<CXXNullPtrLiteralExpr>(Exp) || 213 isa<GNUNullExpr>(Exp) || 214 isa<CXXBoolLiteralExpr>(Exp) || 215 isa<FloatingLiteral>(Exp) || 216 isa<ImaginaryLiteral>(Exp) || 217 isa<IntegerLiteral>(Exp) || 218 isa<StringLiteral>(Exp) || 219 isa<ObjCStringLiteral>(Exp)) { 220 return; // FIXME: Ignore literals for now 221 } else { 222 // Ignore. FIXME: mark as invalid expression? 223 } 224 } 225 226 /// \brief Construct a MutexID from an expression. 227 /// \param MutexExp The original mutex expression within an attribute 228 /// \param DeclExp An expression involving the Decl on which the attribute 229 /// occurs. 230 /// \param D The declaration to which the lock/unlock attribute is attached. 231 void buildMutexIDFromExp(Expr *MutexExp, Expr *DeclExp, const NamedDecl *D) { 232 CallingContext CallCtx(D); 233 234 // If we are processing a raw attribute expression, with no substitutions. 235 if (DeclExp == 0) { 236 buildMutexID(MutexExp, 0); 237 return; 238 } 239 240 // Examine DeclExp to find SelfArg and FunArgs, which are used to substitute 241 // for formal parameters when we call buildMutexID later. 242 if (MemberExpr *ME = dyn_cast<MemberExpr>(DeclExp)) { 243 CallCtx.SelfArg = ME->getBase(); 244 } else if (CXXMemberCallExpr *CE = dyn_cast<CXXMemberCallExpr>(DeclExp)) { 245 CallCtx.SelfArg = CE->getImplicitObjectArgument(); 246 CallCtx.NumArgs = CE->getNumArgs(); 247 CallCtx.FunArgs = CE->getArgs(); 248 } else if (CallExpr *CE = dyn_cast<CallExpr>(DeclExp)) { 249 CallCtx.NumArgs = CE->getNumArgs(); 250 CallCtx.FunArgs = CE->getArgs(); 251 } else if (CXXConstructExpr *CE = dyn_cast<CXXConstructExpr>(DeclExp)) { 252 CallCtx.SelfArg = 0; // FIXME -- get the parent from DeclStmt 253 CallCtx.NumArgs = CE->getNumArgs(); 254 CallCtx.FunArgs = CE->getArgs(); 255 } else if (D && isa<CXXDestructorDecl>(D)) { 256 // There's no such thing as a "destructor call" in the AST. 257 CallCtx.SelfArg = DeclExp; 258 } 259 260 // If the attribute has no arguments, then assume the argument is "this". 261 if (MutexExp == 0) { 262 buildMutexID(CallCtx.SelfArg, 0); 263 return; 264 } 265 266 // For most attributes. 267 buildMutexID(MutexExp, &CallCtx); 268 } 269 270public: 271 explicit MutexID(clang::Decl::EmptyShell e) { 272 DeclSeq.clear(); 273 } 274 275 /// \param MutexExp The original mutex expression within an attribute 276 /// \param DeclExp An expression involving the Decl on which the attribute 277 /// occurs. 278 /// \param D The declaration to which the lock/unlock attribute is attached. 279 /// Caller must check isValid() after construction. 280 MutexID(Expr* MutexExp, Expr *DeclExp, const NamedDecl* D) { 281 buildMutexIDFromExp(MutexExp, DeclExp, D); 282 } 283 284 /// Return true if this is a valid decl sequence. 285 /// Caller must call this by hand after construction to handle errors. 286 bool isValid() const { 287 return !DeclSeq.empty(); 288 } 289 290 /// Issue a warning about an invalid lock expression 291 static void warnInvalidLock(ThreadSafetyHandler &Handler, Expr* MutexExp, 292 Expr *DeclExp, const NamedDecl* D) { 293 SourceLocation Loc; 294 if (DeclExp) 295 Loc = DeclExp->getExprLoc(); 296 297 // FIXME: add a note about the attribute location in MutexExp or D 298 if (Loc.isValid()) 299 Handler.handleInvalidLockExp(Loc); 300 } 301 302 bool operator==(const MutexID &other) const { 303 return DeclSeq == other.DeclSeq; 304 } 305 306 bool operator!=(const MutexID &other) const { 307 return !(*this == other); 308 } 309 310 // SmallVector overloads Operator< to do lexicographic ordering. Note that 311 // we use pointer equality (and <) to compare NamedDecls. This means the order 312 // of MutexIDs in a lockset is nondeterministic. In order to output 313 // diagnostics in a deterministic ordering, we must order all diagnostics to 314 // output by SourceLocation when iterating through this lockset. 315 bool operator<(const MutexID &other) const { 316 return DeclSeq < other.DeclSeq; 317 } 318 319 /// \brief Returns the name of the first Decl in the list for a given MutexID; 320 /// e.g. the lock expression foo.bar() has name "bar". 321 /// The caret will point unambiguously to the lock expression, so using this 322 /// name in diagnostics is a way to get simple, and consistent, mutex names. 323 /// We do not want to output the entire expression text for security reasons. 324 std::string getName() const { 325 assert(isValid()); 326 if (!DeclSeq.front()) 327 return "this"; // Use 0 to represent 'this'. 328 return DeclSeq.front()->getNameAsString(); 329 } 330 331 void Profile(llvm::FoldingSetNodeID &ID) const { 332 for (SmallVectorImpl<NamedDecl*>::const_iterator I = DeclSeq.begin(), 333 E = DeclSeq.end(); I != E; ++I) { 334 ID.AddPointer(*I); 335 } 336 } 337}; 338 339 340/// \brief This is a helper class that stores info about the most recent 341/// accquire of a Lock. 342/// 343/// The main body of the analysis maps MutexIDs to LockDatas. 344struct LockData { 345 SourceLocation AcquireLoc; 346 347 /// \brief LKind stores whether a lock is held shared or exclusively. 348 /// Note that this analysis does not currently support either re-entrant 349 /// locking or lock "upgrading" and "downgrading" between exclusive and 350 /// shared. 351 /// 352 /// FIXME: add support for re-entrant locking and lock up/downgrading 353 LockKind LKind; 354 bool Managed; // for ScopedLockable objects 355 MutexID UnderlyingMutex; // for ScopedLockable objects 356 357 LockData(SourceLocation AcquireLoc, LockKind LKind, bool M = false) 358 : AcquireLoc(AcquireLoc), LKind(LKind), Managed(M), 359 UnderlyingMutex(Decl::EmptyShell()) 360 {} 361 362 LockData(SourceLocation AcquireLoc, LockKind LKind, const MutexID &Mu) 363 : AcquireLoc(AcquireLoc), LKind(LKind), Managed(false), 364 UnderlyingMutex(Mu) 365 {} 366 367 bool operator==(const LockData &other) const { 368 return AcquireLoc == other.AcquireLoc && LKind == other.LKind; 369 } 370 371 bool operator!=(const LockData &other) const { 372 return !(*this == other); 373 } 374 375 void Profile(llvm::FoldingSetNodeID &ID) const { 376 ID.AddInteger(AcquireLoc.getRawEncoding()); 377 ID.AddInteger(LKind); 378 } 379}; 380 381 382/// A Lockset maps each MutexID (defined above) to information about how it has 383/// been locked. 384typedef llvm::ImmutableMap<MutexID, LockData> Lockset; 385typedef llvm::ImmutableMap<const NamedDecl*, unsigned> LocalVarContext; 386 387class LocalVariableMap; 388 389/// A side (entry or exit) of a CFG node. 390enum CFGBlockSide { CBS_Entry, CBS_Exit }; 391 392/// CFGBlockInfo is a struct which contains all the information that is 393/// maintained for each block in the CFG. See LocalVariableMap for more 394/// information about the contexts. 395struct CFGBlockInfo { 396 Lockset EntrySet; // Lockset held at entry to block 397 Lockset ExitSet; // Lockset held at exit from block 398 LocalVarContext EntryContext; // Context held at entry to block 399 LocalVarContext ExitContext; // Context held at exit from block 400 SourceLocation EntryLoc; // Location of first statement in block 401 SourceLocation ExitLoc; // Location of last statement in block. 402 unsigned EntryIndex; // Used to replay contexts later 403 404 const Lockset &getSet(CFGBlockSide Side) const { 405 return Side == CBS_Entry ? EntrySet : ExitSet; 406 } 407 SourceLocation getLocation(CFGBlockSide Side) const { 408 return Side == CBS_Entry ? EntryLoc : ExitLoc; 409 } 410 411private: 412 CFGBlockInfo(Lockset EmptySet, LocalVarContext EmptyCtx) 413 : EntrySet(EmptySet), ExitSet(EmptySet), 414 EntryContext(EmptyCtx), ExitContext(EmptyCtx) 415 { } 416 417public: 418 static CFGBlockInfo getEmptyBlockInfo(Lockset::Factory &F, 419 LocalVariableMap &M); 420}; 421 422 423 424// A LocalVariableMap maintains a map from local variables to their currently 425// valid definitions. It provides SSA-like functionality when traversing the 426// CFG. Like SSA, each definition or assignment to a variable is assigned a 427// unique name (an integer), which acts as the SSA name for that definition. 428// The total set of names is shared among all CFG basic blocks. 429// Unlike SSA, we do not rewrite expressions to replace local variables declrefs 430// with their SSA-names. Instead, we compute a Context for each point in the 431// code, which maps local variables to the appropriate SSA-name. This map 432// changes with each assignment. 433// 434// The map is computed in a single pass over the CFG. Subsequent analyses can 435// then query the map to find the appropriate Context for a statement, and use 436// that Context to look up the definitions of variables. 437class LocalVariableMap { 438public: 439 typedef LocalVarContext Context; 440 441 /// A VarDefinition consists of an expression, representing the value of the 442 /// variable, along with the context in which that expression should be 443 /// interpreted. A reference VarDefinition does not itself contain this 444 /// information, but instead contains a pointer to a previous VarDefinition. 445 struct VarDefinition { 446 public: 447 friend class LocalVariableMap; 448 449 const NamedDecl *Dec; // The original declaration for this variable. 450 const Expr *Exp; // The expression for this variable, OR 451 unsigned Ref; // Reference to another VarDefinition 452 Context Ctx; // The map with which Exp should be interpreted. 453 454 bool isReference() { return !Exp; } 455 456 private: 457 // Create ordinary variable definition 458 VarDefinition(const NamedDecl *D, const Expr *E, Context C) 459 : Dec(D), Exp(E), Ref(0), Ctx(C) 460 { } 461 462 // Create reference to previous definition 463 VarDefinition(const NamedDecl *D, unsigned R, Context C) 464 : Dec(D), Exp(0), Ref(R), Ctx(C) 465 { } 466 }; 467 468private: 469 Context::Factory ContextFactory; 470 std::vector<VarDefinition> VarDefinitions; 471 std::vector<unsigned> CtxIndices; 472 std::vector<std::pair<Stmt*, Context> > SavedContexts; 473 474public: 475 LocalVariableMap() { 476 // index 0 is a placeholder for undefined variables (aka phi-nodes). 477 VarDefinitions.push_back(VarDefinition(0, 0u, getEmptyContext())); 478 } 479 480 /// Look up a definition, within the given context. 481 const VarDefinition* lookup(const NamedDecl *D, Context Ctx) { 482 const unsigned *i = Ctx.lookup(D); 483 if (!i) 484 return 0; 485 assert(*i < VarDefinitions.size()); 486 return &VarDefinitions[*i]; 487 } 488 489 /// Look up the definition for D within the given context. Returns 490 /// NULL if the expression is not statically known. If successful, also 491 /// modifies Ctx to hold the context of the return Expr. 492 const Expr* lookupExpr(const NamedDecl *D, Context &Ctx) { 493 const unsigned *P = Ctx.lookup(D); 494 if (!P) 495 return 0; 496 497 unsigned i = *P; 498 while (i > 0) { 499 if (VarDefinitions[i].Exp) { 500 Ctx = VarDefinitions[i].Ctx; 501 return VarDefinitions[i].Exp; 502 } 503 i = VarDefinitions[i].Ref; 504 } 505 return 0; 506 } 507 508 Context getEmptyContext() { return ContextFactory.getEmptyMap(); } 509 510 /// Return the next context after processing S. This function is used by 511 /// clients of the class to get the appropriate context when traversing the 512 /// CFG. It must be called for every assignment or DeclStmt. 513 Context getNextContext(unsigned &CtxIndex, Stmt *S, Context C) { 514 if (SavedContexts[CtxIndex+1].first == S) { 515 CtxIndex++; 516 Context Result = SavedContexts[CtxIndex].second; 517 return Result; 518 } 519 return C; 520 } 521 522 void dumpVarDefinitionName(unsigned i) { 523 if (i == 0) { 524 llvm::errs() << "Undefined"; 525 return; 526 } 527 const NamedDecl *Dec = VarDefinitions[i].Dec; 528 if (!Dec) { 529 llvm::errs() << "<<NULL>>"; 530 return; 531 } 532 Dec->printName(llvm::errs()); 533 llvm::errs() << "." << i << " " << ((void*) Dec); 534 } 535 536 /// Dumps an ASCII representation of the variable map to llvm::errs() 537 void dump() { 538 for (unsigned i = 1, e = VarDefinitions.size(); i < e; ++i) { 539 const Expr *Exp = VarDefinitions[i].Exp; 540 unsigned Ref = VarDefinitions[i].Ref; 541 542 dumpVarDefinitionName(i); 543 llvm::errs() << " = "; 544 if (Exp) Exp->dump(); 545 else { 546 dumpVarDefinitionName(Ref); 547 llvm::errs() << "\n"; 548 } 549 } 550 } 551 552 /// Dumps an ASCII representation of a Context to llvm::errs() 553 void dumpContext(Context C) { 554 for (Context::iterator I = C.begin(), E = C.end(); I != E; ++I) { 555 const NamedDecl *D = I.getKey(); 556 D->printName(llvm::errs()); 557 const unsigned *i = C.lookup(D); 558 llvm::errs() << " -> "; 559 dumpVarDefinitionName(*i); 560 llvm::errs() << "\n"; 561 } 562 } 563 564 /// Builds the variable map. 565 void traverseCFG(CFG *CFGraph, PostOrderCFGView *SortedGraph, 566 std::vector<CFGBlockInfo> &BlockInfo); 567 568protected: 569 // Get the current context index 570 unsigned getContextIndex() { return SavedContexts.size()-1; } 571 572 // Save the current context for later replay 573 void saveContext(Stmt *S, Context C) { 574 SavedContexts.push_back(std::make_pair(S,C)); 575 } 576 577 // Adds a new definition to the given context, and returns a new context. 578 // This method should be called when declaring a new variable. 579 Context addDefinition(const NamedDecl *D, Expr *Exp, Context Ctx) { 580 assert(!Ctx.contains(D)); 581 unsigned newID = VarDefinitions.size(); 582 Context NewCtx = ContextFactory.add(Ctx, D, newID); 583 VarDefinitions.push_back(VarDefinition(D, Exp, Ctx)); 584 return NewCtx; 585 } 586 587 // Add a new reference to an existing definition. 588 Context addReference(const NamedDecl *D, unsigned i, Context Ctx) { 589 unsigned newID = VarDefinitions.size(); 590 Context NewCtx = ContextFactory.add(Ctx, D, newID); 591 VarDefinitions.push_back(VarDefinition(D, i, Ctx)); 592 return NewCtx; 593 } 594 595 // Updates a definition only if that definition is already in the map. 596 // This method should be called when assigning to an existing variable. 597 Context updateDefinition(const NamedDecl *D, Expr *Exp, Context Ctx) { 598 if (Ctx.contains(D)) { 599 unsigned newID = VarDefinitions.size(); 600 Context NewCtx = ContextFactory.remove(Ctx, D); 601 NewCtx = ContextFactory.add(NewCtx, D, newID); 602 VarDefinitions.push_back(VarDefinition(D, Exp, Ctx)); 603 return NewCtx; 604 } 605 return Ctx; 606 } 607 608 // Removes a definition from the context, but keeps the variable name 609 // as a valid variable. The index 0 is a placeholder for cleared definitions. 610 Context clearDefinition(const NamedDecl *D, Context Ctx) { 611 Context NewCtx = Ctx; 612 if (NewCtx.contains(D)) { 613 NewCtx = ContextFactory.remove(NewCtx, D); 614 NewCtx = ContextFactory.add(NewCtx, D, 0); 615 } 616 return NewCtx; 617 } 618 619 // Remove a definition entirely frmo the context. 620 Context removeDefinition(const NamedDecl *D, Context Ctx) { 621 Context NewCtx = Ctx; 622 if (NewCtx.contains(D)) { 623 NewCtx = ContextFactory.remove(NewCtx, D); 624 } 625 return NewCtx; 626 } 627 628 Context intersectContexts(Context C1, Context C2); 629 Context createReferenceContext(Context C); 630 void intersectBackEdge(Context C1, Context C2); 631 632 friend class VarMapBuilder; 633}; 634 635 636// This has to be defined after LocalVariableMap. 637CFGBlockInfo CFGBlockInfo::getEmptyBlockInfo(Lockset::Factory &F, 638 LocalVariableMap &M) { 639 return CFGBlockInfo(F.getEmptyMap(), M.getEmptyContext()); 640} 641 642 643/// Visitor which builds a LocalVariableMap 644class VarMapBuilder : public StmtVisitor<VarMapBuilder> { 645public: 646 LocalVariableMap* VMap; 647 LocalVariableMap::Context Ctx; 648 649 VarMapBuilder(LocalVariableMap *VM, LocalVariableMap::Context C) 650 : VMap(VM), Ctx(C) {} 651 652 void VisitDeclStmt(DeclStmt *S); 653 void VisitBinaryOperator(BinaryOperator *BO); 654}; 655 656 657// Add new local variables to the variable map 658void VarMapBuilder::VisitDeclStmt(DeclStmt *S) { 659 bool modifiedCtx = false; 660 DeclGroupRef DGrp = S->getDeclGroup(); 661 for (DeclGroupRef::iterator I = DGrp.begin(), E = DGrp.end(); I != E; ++I) { 662 if (VarDecl *VD = dyn_cast_or_null<VarDecl>(*I)) { 663 Expr *E = VD->getInit(); 664 665 // Add local variables with trivial type to the variable map 666 QualType T = VD->getType(); 667 if (T.isTrivialType(VD->getASTContext())) { 668 Ctx = VMap->addDefinition(VD, E, Ctx); 669 modifiedCtx = true; 670 } 671 } 672 } 673 if (modifiedCtx) 674 VMap->saveContext(S, Ctx); 675} 676 677// Update local variable definitions in variable map 678void VarMapBuilder::VisitBinaryOperator(BinaryOperator *BO) { 679 if (!BO->isAssignmentOp()) 680 return; 681 682 Expr *LHSExp = BO->getLHS()->IgnoreParenCasts(); 683 684 // Update the variable map and current context. 685 if (DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(LHSExp)) { 686 ValueDecl *VDec = DRE->getDecl(); 687 if (Ctx.lookup(VDec)) { 688 if (BO->getOpcode() == BO_Assign) 689 Ctx = VMap->updateDefinition(VDec, BO->getRHS(), Ctx); 690 else 691 // FIXME -- handle compound assignment operators 692 Ctx = VMap->clearDefinition(VDec, Ctx); 693 VMap->saveContext(BO, Ctx); 694 } 695 } 696} 697 698 699// Computes the intersection of two contexts. The intersection is the 700// set of variables which have the same definition in both contexts; 701// variables with different definitions are discarded. 702LocalVariableMap::Context 703LocalVariableMap::intersectContexts(Context C1, Context C2) { 704 Context Result = C1; 705 for (Context::iterator I = C1.begin(), E = C1.end(); I != E; ++I) { 706 const NamedDecl *Dec = I.getKey(); 707 unsigned i1 = I.getData(); 708 const unsigned *i2 = C2.lookup(Dec); 709 if (!i2) // variable doesn't exist on second path 710 Result = removeDefinition(Dec, Result); 711 else if (*i2 != i1) // variable exists, but has different definition 712 Result = clearDefinition(Dec, Result); 713 } 714 return Result; 715} 716 717// For every variable in C, create a new variable that refers to the 718// definition in C. Return a new context that contains these new variables. 719// (We use this for a naive implementation of SSA on loop back-edges.) 720LocalVariableMap::Context LocalVariableMap::createReferenceContext(Context C) { 721 Context Result = getEmptyContext(); 722 for (Context::iterator I = C.begin(), E = C.end(); I != E; ++I) { 723 const NamedDecl *Dec = I.getKey(); 724 unsigned i = I.getData(); 725 Result = addReference(Dec, i, Result); 726 } 727 return Result; 728} 729 730// This routine also takes the intersection of C1 and C2, but it does so by 731// altering the VarDefinitions. C1 must be the result of an earlier call to 732// createReferenceContext. 733void LocalVariableMap::intersectBackEdge(Context C1, Context C2) { 734 for (Context::iterator I = C1.begin(), E = C1.end(); I != E; ++I) { 735 const NamedDecl *Dec = I.getKey(); 736 unsigned i1 = I.getData(); 737 VarDefinition *VDef = &VarDefinitions[i1]; 738 assert(VDef->isReference()); 739 740 const unsigned *i2 = C2.lookup(Dec); 741 if (!i2 || (*i2 != i1)) 742 VDef->Ref = 0; // Mark this variable as undefined 743 } 744} 745 746 747// Traverse the CFG in topological order, so all predecessors of a block 748// (excluding back-edges) are visited before the block itself. At 749// each point in the code, we calculate a Context, which holds the set of 750// variable definitions which are visible at that point in execution. 751// Visible variables are mapped to their definitions using an array that 752// contains all definitions. 753// 754// At join points in the CFG, the set is computed as the intersection of 755// the incoming sets along each edge, E.g. 756// 757// { Context | VarDefinitions } 758// int x = 0; { x -> x1 | x1 = 0 } 759// int y = 0; { x -> x1, y -> y1 | y1 = 0, x1 = 0 } 760// if (b) x = 1; { x -> x2, y -> y1 | x2 = 1, y1 = 0, ... } 761// else x = 2; { x -> x3, y -> y1 | x3 = 2, x2 = 1, ... } 762// ... { y -> y1 (x is unknown) | x3 = 2, x2 = 1, ... } 763// 764// This is essentially a simpler and more naive version of the standard SSA 765// algorithm. Those definitions that remain in the intersection are from blocks 766// that strictly dominate the current block. We do not bother to insert proper 767// phi nodes, because they are not used in our analysis; instead, wherever 768// a phi node would be required, we simply remove that definition from the 769// context (E.g. x above). 770// 771// The initial traversal does not capture back-edges, so those need to be 772// handled on a separate pass. Whenever the first pass encounters an 773// incoming back edge, it duplicates the context, creating new definitions 774// that refer back to the originals. (These correspond to places where SSA 775// might have to insert a phi node.) On the second pass, these definitions are 776// set to NULL if the the variable has changed on the back-edge (i.e. a phi 777// node was actually required.) E.g. 778// 779// { Context | VarDefinitions } 780// int x = 0, y = 0; { x -> x1, y -> y1 | y1 = 0, x1 = 0 } 781// while (b) { x -> x2, y -> y1 | [1st:] x2=x1; [2nd:] x2=NULL; } 782// x = x+1; { x -> x3, y -> y1 | x3 = x2 + 1, ... } 783// ... { y -> y1 | x3 = 2, x2 = 1, ... } 784// 785void LocalVariableMap::traverseCFG(CFG *CFGraph, 786 PostOrderCFGView *SortedGraph, 787 std::vector<CFGBlockInfo> &BlockInfo) { 788 PostOrderCFGView::CFGBlockSet VisitedBlocks(CFGraph); 789 790 CtxIndices.resize(CFGraph->getNumBlockIDs()); 791 792 for (PostOrderCFGView::iterator I = SortedGraph->begin(), 793 E = SortedGraph->end(); I!= E; ++I) { 794 const CFGBlock *CurrBlock = *I; 795 int CurrBlockID = CurrBlock->getBlockID(); 796 CFGBlockInfo *CurrBlockInfo = &BlockInfo[CurrBlockID]; 797 798 VisitedBlocks.insert(CurrBlock); 799 800 // Calculate the entry context for the current block 801 bool HasBackEdges = false; 802 bool CtxInit = true; 803 for (CFGBlock::const_pred_iterator PI = CurrBlock->pred_begin(), 804 PE = CurrBlock->pred_end(); PI != PE; ++PI) { 805 // if *PI -> CurrBlock is a back edge, so skip it 806 if (*PI == 0 || !VisitedBlocks.alreadySet(*PI)) { 807 HasBackEdges = true; 808 continue; 809 } 810 811 int PrevBlockID = (*PI)->getBlockID(); 812 CFGBlockInfo *PrevBlockInfo = &BlockInfo[PrevBlockID]; 813 814 if (CtxInit) { 815 CurrBlockInfo->EntryContext = PrevBlockInfo->ExitContext; 816 CtxInit = false; 817 } 818 else { 819 CurrBlockInfo->EntryContext = 820 intersectContexts(CurrBlockInfo->EntryContext, 821 PrevBlockInfo->ExitContext); 822 } 823 } 824 825 // Duplicate the context if we have back-edges, so we can call 826 // intersectBackEdges later. 827 if (HasBackEdges) 828 CurrBlockInfo->EntryContext = 829 createReferenceContext(CurrBlockInfo->EntryContext); 830 831 // Create a starting context index for the current block 832 saveContext(0, CurrBlockInfo->EntryContext); 833 CurrBlockInfo->EntryIndex = getContextIndex(); 834 835 // Visit all the statements in the basic block. 836 VarMapBuilder VMapBuilder(this, CurrBlockInfo->EntryContext); 837 for (CFGBlock::const_iterator BI = CurrBlock->begin(), 838 BE = CurrBlock->end(); BI != BE; ++BI) { 839 switch (BI->getKind()) { 840 case CFGElement::Statement: { 841 const CFGStmt *CS = cast<CFGStmt>(&*BI); 842 VMapBuilder.Visit(const_cast<Stmt*>(CS->getStmt())); 843 break; 844 } 845 default: 846 break; 847 } 848 } 849 CurrBlockInfo->ExitContext = VMapBuilder.Ctx; 850 851 // Mark variables on back edges as "unknown" if they've been changed. 852 for (CFGBlock::const_succ_iterator SI = CurrBlock->succ_begin(), 853 SE = CurrBlock->succ_end(); SI != SE; ++SI) { 854 // if CurrBlock -> *SI is *not* a back edge 855 if (*SI == 0 || !VisitedBlocks.alreadySet(*SI)) 856 continue; 857 858 CFGBlock *FirstLoopBlock = *SI; 859 Context LoopBegin = BlockInfo[FirstLoopBlock->getBlockID()].EntryContext; 860 Context LoopEnd = CurrBlockInfo->ExitContext; 861 intersectBackEdge(LoopBegin, LoopEnd); 862 } 863 } 864 865 // Put an extra entry at the end of the indexed context array 866 unsigned exitID = CFGraph->getExit().getBlockID(); 867 saveContext(0, BlockInfo[exitID].ExitContext); 868} 869 870/// Find the appropriate source locations to use when producing diagnostics for 871/// each block in the CFG. 872static void findBlockLocations(CFG *CFGraph, 873 PostOrderCFGView *SortedGraph, 874 std::vector<CFGBlockInfo> &BlockInfo) { 875 for (PostOrderCFGView::iterator I = SortedGraph->begin(), 876 E = SortedGraph->end(); I!= E; ++I) { 877 const CFGBlock *CurrBlock = *I; 878 CFGBlockInfo *CurrBlockInfo = &BlockInfo[CurrBlock->getBlockID()]; 879 880 // Find the source location of the last statement in the block, if the 881 // block is not empty. 882 if (const Stmt *S = CurrBlock->getTerminator()) { 883 CurrBlockInfo->EntryLoc = CurrBlockInfo->ExitLoc = S->getLocStart(); 884 } else { 885 for (CFGBlock::const_reverse_iterator BI = CurrBlock->rbegin(), 886 BE = CurrBlock->rend(); BI != BE; ++BI) { 887 // FIXME: Handle other CFGElement kinds. 888 if (const CFGStmt *CS = dyn_cast<CFGStmt>(&*BI)) { 889 CurrBlockInfo->ExitLoc = CS->getStmt()->getLocStart(); 890 break; 891 } 892 } 893 } 894 895 if (!CurrBlockInfo->ExitLoc.isInvalid()) { 896 // This block contains at least one statement. Find the source location 897 // of the first statement in the block. 898 for (CFGBlock::const_iterator BI = CurrBlock->begin(), 899 BE = CurrBlock->end(); BI != BE; ++BI) { 900 // FIXME: Handle other CFGElement kinds. 901 if (const CFGStmt *CS = dyn_cast<CFGStmt>(&*BI)) { 902 CurrBlockInfo->EntryLoc = CS->getStmt()->getLocStart(); 903 break; 904 } 905 } 906 } else if (CurrBlock->pred_size() == 1 && *CurrBlock->pred_begin() && 907 CurrBlock != &CFGraph->getExit()) { 908 // The block is empty, and has a single predecessor. Use its exit 909 // location. 910 CurrBlockInfo->EntryLoc = CurrBlockInfo->ExitLoc = 911 BlockInfo[(*CurrBlock->pred_begin())->getBlockID()].ExitLoc; 912 } 913 } 914} 915 916/// \brief Class which implements the core thread safety analysis routines. 917class ThreadSafetyAnalyzer { 918 friend class BuildLockset; 919 920 ThreadSafetyHandler &Handler; 921 Lockset::Factory LocksetFactory; 922 LocalVariableMap LocalVarMap; 923 std::vector<CFGBlockInfo> BlockInfo; 924 925public: 926 ThreadSafetyAnalyzer(ThreadSafetyHandler &H) : Handler(H) {} 927 928 Lockset addLock(const Lockset &LSet, const MutexID &Mutex, 929 const LockData &LDat, bool Warn=true); 930 Lockset addLock(const Lockset &LSet, Expr *MutexExp, const NamedDecl *D, 931 const LockData &LDat, bool Warn=true); 932 Lockset removeLock(const Lockset &LSet, const MutexID &Mutex, 933 SourceLocation UnlockLoc, 934 bool Warn=true, bool FullyRemove=false); 935 936 template <class AttrType> 937 Lockset addLocksToSet(const Lockset &LSet, LockKind LK, AttrType *Attr, 938 Expr *Exp, NamedDecl *D, VarDecl *VD = 0); 939 Lockset removeLocksFromSet(const Lockset &LSet, 940 UnlockFunctionAttr *Attr, 941 Expr *Exp, NamedDecl* FunDecl); 942 943 template <class AttrType> 944 Lockset addTrylock(const Lockset &LSet, 945 LockKind LK, AttrType *Attr, Expr *Exp, NamedDecl *FunDecl, 946 const CFGBlock* PredBlock, const CFGBlock *CurrBlock, 947 Expr *BrE, bool Neg); 948 const CallExpr* getTrylockCallExpr(const Stmt *Cond, LocalVarContext C, 949 bool &Negate); 950 951 Lockset getEdgeLockset(const Lockset &ExitSet, 952 const CFGBlock* PredBlock, 953 const CFGBlock *CurrBlock); 954 955 Lockset intersectAndWarn(const Lockset &LSet1, const Lockset &LSet2, 956 SourceLocation JoinLoc, 957 LockErrorKind LEK1, LockErrorKind LEK2); 958 959 Lockset intersectAndWarn(const Lockset &LSet1, const Lockset &LSet2, 960 SourceLocation JoinLoc, LockErrorKind LEK1) { 961 return intersectAndWarn(LSet1, LSet2, JoinLoc, LEK1, LEK1); 962 } 963 964 void runAnalysis(AnalysisDeclContext &AC); 965}; 966 967 968/// \brief Add a new lock to the lockset, warning if the lock is already there. 969/// \param Mutex -- the Mutex expression for the lock 970/// \param LDat -- the LockData for the lock 971Lockset ThreadSafetyAnalyzer::addLock(const Lockset &LSet, 972 const MutexID &Mutex, 973 const LockData &LDat, 974 bool Warn) { 975 // FIXME: deal with acquired before/after annotations. 976 // FIXME: Don't always warn when we have support for reentrant locks. 977 if (LSet.lookup(Mutex)) { 978 if (Warn) 979 Handler.handleDoubleLock(Mutex.getName(), LDat.AcquireLoc); 980 return LSet; 981 } else { 982 return LocksetFactory.add(LSet, Mutex, LDat); 983 } 984} 985 986/// \brief Construct a new mutex and add it to the lockset. 987Lockset ThreadSafetyAnalyzer::addLock(const Lockset &LSet, 988 Expr *MutexExp, const NamedDecl *D, 989 const LockData &LDat, 990 bool Warn) { 991 MutexID Mutex(MutexExp, 0, D); 992 if (!Mutex.isValid()) { 993 MutexID::warnInvalidLock(Handler, MutexExp, 0, D); 994 return LSet; 995 } 996 return addLock(LSet, Mutex, LDat, Warn); 997} 998 999 1000/// \brief Remove a lock from the lockset, warning if the lock is not there. 1001/// \param LockExp The lock expression corresponding to the lock to be removed 1002/// \param UnlockLoc The source location of the unlock (only used in error msg) 1003Lockset ThreadSafetyAnalyzer::removeLock(const Lockset &LSet, 1004 const MutexID &Mutex, 1005 SourceLocation UnlockLoc, 1006 bool Warn, bool FullyRemove) { 1007 const LockData *LDat = LSet.lookup(Mutex); 1008 if (!LDat) { 1009 if (Warn) 1010 Handler.handleUnmatchedUnlock(Mutex.getName(), UnlockLoc); 1011 return LSet; 1012 } 1013 else { 1014 Lockset Result = LSet; 1015 if (LDat->UnderlyingMutex.isValid()) { 1016 // For scoped-lockable vars, remove the mutex associated with this var. 1017 Result = removeLock(Result, LDat->UnderlyingMutex, UnlockLoc, 1018 false, true); 1019 // Fully remove the object only when the destructor is called 1020 if (FullyRemove) 1021 return LocksetFactory.remove(Result, Mutex); 1022 else 1023 return Result; 1024 } 1025 return LocksetFactory.remove(Result, Mutex); 1026 } 1027} 1028 1029 1030/// \brief This function, parameterized by an attribute type, is used to add a 1031/// set of locks specified as attribute arguments to the lockset. 1032template <typename AttrType> 1033Lockset ThreadSafetyAnalyzer::addLocksToSet(const Lockset &LSet, 1034 LockKind LK, AttrType *Attr, 1035 Expr *Exp, NamedDecl* FunDecl, 1036 VarDecl *VD) { 1037 typedef typename AttrType::args_iterator iterator_type; 1038 1039 SourceLocation ExpLocation = Exp->getExprLoc(); 1040 1041 // Figure out if we're calling the constructor of scoped lockable class 1042 bool isScopedVar = false; 1043 if (VD) { 1044 if (CXXConstructorDecl *CD = dyn_cast<CXXConstructorDecl>(FunDecl)) { 1045 CXXRecordDecl* PD = CD->getParent(); 1046 if (PD && PD->getAttr<ScopedLockableAttr>()) 1047 isScopedVar = true; 1048 } 1049 } 1050 1051 if (Attr->args_size() == 0) { 1052 // The mutex held is the "this" object. 1053 MutexID Mutex(0, Exp, FunDecl); 1054 if (!Mutex.isValid()) { 1055 MutexID::warnInvalidLock(Handler, 0, Exp, FunDecl); 1056 return LSet; 1057 } 1058 else { 1059 return addLock(LSet, Mutex, LockData(ExpLocation, LK)); 1060 } 1061 } 1062 1063 Lockset Result = LSet; 1064 for (iterator_type I=Attr->args_begin(), E=Attr->args_end(); I != E; ++I) { 1065 MutexID Mutex(*I, Exp, FunDecl); 1066 if (!Mutex.isValid()) 1067 MutexID::warnInvalidLock(Handler, *I, Exp, FunDecl); 1068 else { 1069 if (isScopedVar) { 1070 // Mutex is managed by scoped var -- suppress certain warnings. 1071 Result = addLock(Result, Mutex, LockData(ExpLocation, LK, true)); 1072 // For scoped lockable vars, map this var to its underlying mutex. 1073 DeclRefExpr DRE(VD, false, VD->getType(), VK_LValue, VD->getLocation()); 1074 MutexID SMutex(&DRE, 0, 0); 1075 Result = addLock(Result, SMutex, 1076 LockData(VD->getLocation(), LK, Mutex)); 1077 } 1078 else { 1079 Result = addLock(Result, Mutex, LockData(ExpLocation, LK)); 1080 } 1081 } 1082 } 1083 return Result; 1084} 1085 1086/// \brief This function removes a set of locks specified as attribute 1087/// arguments from the lockset. 1088Lockset ThreadSafetyAnalyzer::removeLocksFromSet(const Lockset &LSet, 1089 UnlockFunctionAttr *Attr, 1090 Expr *Exp, 1091 NamedDecl* FunDecl) { 1092 SourceLocation ExpLocation; 1093 if (Exp) ExpLocation = Exp->getExprLoc(); 1094 bool Dtor = isa<CXXDestructorDecl>(FunDecl); 1095 1096 if (Attr->args_size() == 0) { 1097 // The mutex held is the "this" object. 1098 MutexID Mu(0, Exp, FunDecl); 1099 if (!Mu.isValid()) { 1100 MutexID::warnInvalidLock(Handler, 0, Exp, FunDecl); 1101 return LSet; 1102 } else { 1103 return removeLock(LSet, Mu, ExpLocation, true, Dtor); 1104 } 1105 } 1106 1107 Lockset Result = LSet; 1108 for (UnlockFunctionAttr::args_iterator I = Attr->args_begin(), 1109 E = Attr->args_end(); I != E; ++I) { 1110 MutexID Mutex(*I, Exp, FunDecl); 1111 if (!Mutex.isValid()) 1112 MutexID::warnInvalidLock(Handler, *I, Exp, FunDecl); 1113 else 1114 Result = removeLock(Result, Mutex, ExpLocation, true, Dtor); 1115 } 1116 return Result; 1117} 1118 1119 1120/// \brief Add lock to set, if the current block is in the taken branch of a 1121/// trylock. 1122template <class AttrType> 1123Lockset ThreadSafetyAnalyzer::addTrylock(const Lockset &LSet, 1124 LockKind LK, AttrType *Attr, 1125 Expr *Exp, NamedDecl *FunDecl, 1126 const CFGBlock *PredBlock, 1127 const CFGBlock *CurrBlock, 1128 Expr *BrE, bool Neg) { 1129 // Find out which branch has the lock 1130 bool branch = 0; 1131 if (CXXBoolLiteralExpr *BLE = dyn_cast_or_null<CXXBoolLiteralExpr>(BrE)) { 1132 branch = BLE->getValue(); 1133 } 1134 else if (IntegerLiteral *ILE = dyn_cast_or_null<IntegerLiteral>(BrE)) { 1135 branch = ILE->getValue().getBoolValue(); 1136 } 1137 int branchnum = branch ? 0 : 1; 1138 if (Neg) branchnum = !branchnum; 1139 1140 Lockset Result = LSet; 1141 // If we've taken the trylock branch, then add the lock 1142 int i = 0; 1143 for (CFGBlock::const_succ_iterator SI = PredBlock->succ_begin(), 1144 SE = PredBlock->succ_end(); SI != SE && i < 2; ++SI, ++i) { 1145 if (*SI == CurrBlock && i == branchnum) { 1146 Result = addLocksToSet(Result, LK, Attr, Exp, FunDecl, 0); 1147 } 1148 } 1149 return Result; 1150} 1151 1152 1153// If Cond can be traced back to a function call, return the call expression. 1154// The negate variable should be called with false, and will be set to true 1155// if the function call is negated, e.g. if (!mu.tryLock(...)) 1156const CallExpr* ThreadSafetyAnalyzer::getTrylockCallExpr(const Stmt *Cond, 1157 LocalVarContext C, 1158 bool &Negate) { 1159 if (!Cond) 1160 return 0; 1161 1162 if (const CallExpr *CallExp = dyn_cast<CallExpr>(Cond)) { 1163 return CallExp; 1164 } 1165 else if (const ImplicitCastExpr *CE = dyn_cast<ImplicitCastExpr>(Cond)) { 1166 return getTrylockCallExpr(CE->getSubExpr(), C, Negate); 1167 } 1168 else if (const DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(Cond)) { 1169 const Expr *E = LocalVarMap.lookupExpr(DRE->getDecl(), C); 1170 return getTrylockCallExpr(E, C, Negate); 1171 } 1172 else if (const UnaryOperator *UOP = dyn_cast<UnaryOperator>(Cond)) { 1173 if (UOP->getOpcode() == UO_LNot) { 1174 Negate = !Negate; 1175 return getTrylockCallExpr(UOP->getSubExpr(), C, Negate); 1176 } 1177 } 1178 // FIXME -- handle && and || as well. 1179 return NULL; 1180} 1181 1182 1183/// \brief Find the lockset that holds on the edge between PredBlock 1184/// and CurrBlock. The edge set is the exit set of PredBlock (passed 1185/// as the ExitSet parameter) plus any trylocks, which are conditionally held. 1186Lockset ThreadSafetyAnalyzer::getEdgeLockset(const Lockset &ExitSet, 1187 const CFGBlock *PredBlock, 1188 const CFGBlock *CurrBlock) { 1189 if (!PredBlock->getTerminatorCondition()) 1190 return ExitSet; 1191 1192 bool Negate = false; 1193 const Stmt *Cond = PredBlock->getTerminatorCondition(); 1194 const CFGBlockInfo *PredBlockInfo = &BlockInfo[PredBlock->getBlockID()]; 1195 const LocalVarContext &LVarCtx = PredBlockInfo->ExitContext; 1196 1197 CallExpr *Exp = const_cast<CallExpr*>( 1198 getTrylockCallExpr(Cond, LVarCtx, Negate)); 1199 if (!Exp) 1200 return ExitSet; 1201 1202 NamedDecl *FunDecl = dyn_cast_or_null<NamedDecl>(Exp->getCalleeDecl()); 1203 if(!FunDecl || !FunDecl->hasAttrs()) 1204 return ExitSet; 1205 1206 Lockset Result = ExitSet; 1207 1208 // If the condition is a call to a Trylock function, then grab the attributes 1209 AttrVec &ArgAttrs = FunDecl->getAttrs(); 1210 for (unsigned i = 0; i < ArgAttrs.size(); ++i) { 1211 Attr *Attr = ArgAttrs[i]; 1212 switch (Attr->getKind()) { 1213 case attr::ExclusiveTrylockFunction: { 1214 ExclusiveTrylockFunctionAttr *A = 1215 cast<ExclusiveTrylockFunctionAttr>(Attr); 1216 Result = addTrylock(Result, LK_Exclusive, A, Exp, FunDecl, 1217 PredBlock, CurrBlock, 1218 A->getSuccessValue(), Negate); 1219 break; 1220 } 1221 case attr::SharedTrylockFunction: { 1222 SharedTrylockFunctionAttr *A = 1223 cast<SharedTrylockFunctionAttr>(Attr); 1224 Result = addTrylock(Result, LK_Shared, A, Exp, FunDecl, 1225 PredBlock, CurrBlock, 1226 A->getSuccessValue(), Negate); 1227 break; 1228 } 1229 default: 1230 break; 1231 } 1232 } 1233 return Result; 1234} 1235 1236 1237/// \brief We use this class to visit different types of expressions in 1238/// CFGBlocks, and build up the lockset. 1239/// An expression may cause us to add or remove locks from the lockset, or else 1240/// output error messages related to missing locks. 1241/// FIXME: In future, we may be able to not inherit from a visitor. 1242class BuildLockset : public StmtVisitor<BuildLockset> { 1243 friend class ThreadSafetyAnalyzer; 1244 1245 ThreadSafetyAnalyzer *Analyzer; 1246 Lockset LSet; 1247 LocalVariableMap::Context LVarCtx; 1248 unsigned CtxIndex; 1249 1250 // Helper functions 1251 const ValueDecl *getValueDecl(Expr *Exp); 1252 1253 void warnIfMutexNotHeld(const NamedDecl *D, Expr *Exp, AccessKind AK, 1254 Expr *MutexExp, ProtectedOperationKind POK); 1255 1256 void checkAccess(Expr *Exp, AccessKind AK); 1257 void checkDereference(Expr *Exp, AccessKind AK); 1258 void handleCall(Expr *Exp, NamedDecl *D, VarDecl *VD = 0); 1259 1260 /// \brief Returns true if the lockset contains a lock, regardless of whether 1261 /// the lock is held exclusively or shared. 1262 bool locksetContains(const MutexID &Lock) const { 1263 return LSet.lookup(Lock); 1264 } 1265 1266 /// \brief Returns true if the lockset contains a lock with the passed in 1267 /// locktype. 1268 bool locksetContains(const MutexID &Lock, LockKind KindRequested) const { 1269 const LockData *LockHeld = LSet.lookup(Lock); 1270 return (LockHeld && KindRequested == LockHeld->LKind); 1271 } 1272 1273 /// \brief Returns true if the lockset contains a lock with at least the 1274 /// passed in locktype. So for example, if we pass in LK_Shared, this function 1275 /// returns true if the lock is held LK_Shared or LK_Exclusive. If we pass in 1276 /// LK_Exclusive, this function returns true if the lock is held LK_Exclusive. 1277 bool locksetContainsAtLeast(const MutexID &Lock, 1278 LockKind KindRequested) const { 1279 switch (KindRequested) { 1280 case LK_Shared: 1281 return locksetContains(Lock); 1282 case LK_Exclusive: 1283 return locksetContains(Lock, KindRequested); 1284 } 1285 llvm_unreachable("Unknown LockKind"); 1286 } 1287 1288public: 1289 BuildLockset(ThreadSafetyAnalyzer *Anlzr, CFGBlockInfo &Info) 1290 : StmtVisitor<BuildLockset>(), 1291 Analyzer(Anlzr), 1292 LSet(Info.EntrySet), 1293 LVarCtx(Info.EntryContext), 1294 CtxIndex(Info.EntryIndex) 1295 {} 1296 1297 void VisitUnaryOperator(UnaryOperator *UO); 1298 void VisitBinaryOperator(BinaryOperator *BO); 1299 void VisitCastExpr(CastExpr *CE); 1300 void VisitCallExpr(CallExpr *Exp); 1301 void VisitCXXConstructExpr(CXXConstructExpr *Exp); 1302 void VisitDeclStmt(DeclStmt *S); 1303}; 1304 1305 1306/// \brief Gets the value decl pointer from DeclRefExprs or MemberExprs 1307const ValueDecl *BuildLockset::getValueDecl(Expr *Exp) { 1308 if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(Exp)) 1309 return DR->getDecl(); 1310 1311 if (const MemberExpr *ME = dyn_cast<MemberExpr>(Exp)) 1312 return ME->getMemberDecl(); 1313 1314 return 0; 1315} 1316 1317/// \brief Warn if the LSet does not contain a lock sufficient to protect access 1318/// of at least the passed in AccessKind. 1319void BuildLockset::warnIfMutexNotHeld(const NamedDecl *D, Expr *Exp, 1320 AccessKind AK, Expr *MutexExp, 1321 ProtectedOperationKind POK) { 1322 LockKind LK = getLockKindFromAccessKind(AK); 1323 1324 MutexID Mutex(MutexExp, Exp, D); 1325 if (!Mutex.isValid()) 1326 MutexID::warnInvalidLock(Analyzer->Handler, MutexExp, Exp, D); 1327 else if (!locksetContainsAtLeast(Mutex, LK)) 1328 Analyzer->Handler.handleMutexNotHeld(D, POK, Mutex.getName(), LK, 1329 Exp->getExprLoc()); 1330} 1331 1332/// \brief This method identifies variable dereferences and checks pt_guarded_by 1333/// and pt_guarded_var annotations. Note that we only check these annotations 1334/// at the time a pointer is dereferenced. 1335/// FIXME: We need to check for other types of pointer dereferences 1336/// (e.g. [], ->) and deal with them here. 1337/// \param Exp An expression that has been read or written. 1338void BuildLockset::checkDereference(Expr *Exp, AccessKind AK) { 1339 UnaryOperator *UO = dyn_cast<UnaryOperator>(Exp); 1340 if (!UO || UO->getOpcode() != clang::UO_Deref) 1341 return; 1342 Exp = UO->getSubExpr()->IgnoreParenCasts(); 1343 1344 const ValueDecl *D = getValueDecl(Exp); 1345 if(!D || !D->hasAttrs()) 1346 return; 1347 1348 if (D->getAttr<PtGuardedVarAttr>() && LSet.isEmpty()) 1349 Analyzer->Handler.handleNoMutexHeld(D, POK_VarDereference, AK, 1350 Exp->getExprLoc()); 1351 1352 const AttrVec &ArgAttrs = D->getAttrs(); 1353 for(unsigned i = 0, Size = ArgAttrs.size(); i < Size; ++i) 1354 if (PtGuardedByAttr *PGBAttr = dyn_cast<PtGuardedByAttr>(ArgAttrs[i])) 1355 warnIfMutexNotHeld(D, Exp, AK, PGBAttr->getArg(), POK_VarDereference); 1356} 1357 1358/// \brief Checks guarded_by and guarded_var attributes. 1359/// Whenever we identify an access (read or write) of a DeclRefExpr or 1360/// MemberExpr, we need to check whether there are any guarded_by or 1361/// guarded_var attributes, and make sure we hold the appropriate mutexes. 1362void BuildLockset::checkAccess(Expr *Exp, AccessKind AK) { 1363 const ValueDecl *D = getValueDecl(Exp); 1364 if(!D || !D->hasAttrs()) 1365 return; 1366 1367 if (D->getAttr<GuardedVarAttr>() && LSet.isEmpty()) 1368 Analyzer->Handler.handleNoMutexHeld(D, POK_VarAccess, AK, 1369 Exp->getExprLoc()); 1370 1371 const AttrVec &ArgAttrs = D->getAttrs(); 1372 for(unsigned i = 0, Size = ArgAttrs.size(); i < Size; ++i) 1373 if (GuardedByAttr *GBAttr = dyn_cast<GuardedByAttr>(ArgAttrs[i])) 1374 warnIfMutexNotHeld(D, Exp, AK, GBAttr->getArg(), POK_VarAccess); 1375} 1376 1377/// \brief Process a function call, method call, constructor call, 1378/// or destructor call. This involves looking at the attributes on the 1379/// corresponding function/method/constructor/destructor, issuing warnings, 1380/// and updating the locksets accordingly. 1381/// 1382/// FIXME: For classes annotated with one of the guarded annotations, we need 1383/// to treat const method calls as reads and non-const method calls as writes, 1384/// and check that the appropriate locks are held. Non-const method calls with 1385/// the same signature as const method calls can be also treated as reads. 1386/// 1387/// FIXME: We need to also visit CallExprs to catch/check global functions. 1388/// 1389/// FIXME: Do not flag an error for member variables accessed in constructors/ 1390/// destructors 1391void BuildLockset::handleCall(Expr *Exp, NamedDecl *D, VarDecl *VD) { 1392 AttrVec &ArgAttrs = D->getAttrs(); 1393 for(unsigned i = 0; i < ArgAttrs.size(); ++i) { 1394 Attr *Attr = ArgAttrs[i]; 1395 switch (Attr->getKind()) { 1396 // When we encounter an exclusive lock function, we need to add the lock 1397 // to our lockset with kind exclusive. 1398 case attr::ExclusiveLockFunction: { 1399 ExclusiveLockFunctionAttr *A = cast<ExclusiveLockFunctionAttr>(Attr); 1400 LSet = Analyzer->addLocksToSet(LSet, LK_Exclusive, A, Exp, D, VD); 1401 break; 1402 } 1403 1404 // When we encounter a shared lock function, we need to add the lock 1405 // to our lockset with kind shared. 1406 case attr::SharedLockFunction: { 1407 SharedLockFunctionAttr *A = cast<SharedLockFunctionAttr>(Attr); 1408 LSet = Analyzer->addLocksToSet(LSet, LK_Shared, A, Exp, D, VD); 1409 break; 1410 } 1411 1412 // When we encounter an unlock function, we need to remove unlocked 1413 // mutexes from the lockset, and flag a warning if they are not there. 1414 case attr::UnlockFunction: { 1415 UnlockFunctionAttr *UFAttr = cast<UnlockFunctionAttr>(Attr); 1416 LSet = Analyzer->removeLocksFromSet(LSet, UFAttr, Exp, D); 1417 break; 1418 } 1419 1420 case attr::ExclusiveLocksRequired: { 1421 ExclusiveLocksRequiredAttr *ELRAttr = 1422 cast<ExclusiveLocksRequiredAttr>(Attr); 1423 1424 for (ExclusiveLocksRequiredAttr::args_iterator 1425 I = ELRAttr->args_begin(), E = ELRAttr->args_end(); I != E; ++I) 1426 warnIfMutexNotHeld(D, Exp, AK_Written, *I, POK_FunctionCall); 1427 break; 1428 } 1429 1430 case attr::SharedLocksRequired: { 1431 SharedLocksRequiredAttr *SLRAttr = cast<SharedLocksRequiredAttr>(Attr); 1432 1433 for (SharedLocksRequiredAttr::args_iterator I = SLRAttr->args_begin(), 1434 E = SLRAttr->args_end(); I != E; ++I) 1435 warnIfMutexNotHeld(D, Exp, AK_Read, *I, POK_FunctionCall); 1436 break; 1437 } 1438 1439 case attr::LocksExcluded: { 1440 LocksExcludedAttr *LEAttr = cast<LocksExcludedAttr>(Attr); 1441 for (LocksExcludedAttr::args_iterator I = LEAttr->args_begin(), 1442 E = LEAttr->args_end(); I != E; ++I) { 1443 MutexID Mutex(*I, Exp, D); 1444 if (!Mutex.isValid()) 1445 MutexID::warnInvalidLock(Analyzer->Handler, *I, Exp, D); 1446 else if (locksetContains(Mutex)) 1447 Analyzer->Handler.handleFunExcludesLock(D->getName(), 1448 Mutex.getName(), 1449 Exp->getExprLoc()); 1450 } 1451 break; 1452 } 1453 1454 // Ignore other (non thread-safety) attributes 1455 default: 1456 break; 1457 } 1458 } 1459} 1460 1461 1462/// \brief For unary operations which read and write a variable, we need to 1463/// check whether we hold any required mutexes. Reads are checked in 1464/// VisitCastExpr. 1465void BuildLockset::VisitUnaryOperator(UnaryOperator *UO) { 1466 switch (UO->getOpcode()) { 1467 case clang::UO_PostDec: 1468 case clang::UO_PostInc: 1469 case clang::UO_PreDec: 1470 case clang::UO_PreInc: { 1471 Expr *SubExp = UO->getSubExpr()->IgnoreParenCasts(); 1472 checkAccess(SubExp, AK_Written); 1473 checkDereference(SubExp, AK_Written); 1474 break; 1475 } 1476 default: 1477 break; 1478 } 1479} 1480 1481/// For binary operations which assign to a variable (writes), we need to check 1482/// whether we hold any required mutexes. 1483/// FIXME: Deal with non-primitive types. 1484void BuildLockset::VisitBinaryOperator(BinaryOperator *BO) { 1485 if (!BO->isAssignmentOp()) 1486 return; 1487 1488 // adjust the context 1489 LVarCtx = Analyzer->LocalVarMap.getNextContext(CtxIndex, BO, LVarCtx); 1490 1491 Expr *LHSExp = BO->getLHS()->IgnoreParenCasts(); 1492 checkAccess(LHSExp, AK_Written); 1493 checkDereference(LHSExp, AK_Written); 1494} 1495 1496/// Whenever we do an LValue to Rvalue cast, we are reading a variable and 1497/// need to ensure we hold any required mutexes. 1498/// FIXME: Deal with non-primitive types. 1499void BuildLockset::VisitCastExpr(CastExpr *CE) { 1500 if (CE->getCastKind() != CK_LValueToRValue) 1501 return; 1502 Expr *SubExp = CE->getSubExpr()->IgnoreParenCasts(); 1503 checkAccess(SubExp, AK_Read); 1504 checkDereference(SubExp, AK_Read); 1505} 1506 1507 1508void BuildLockset::VisitCallExpr(CallExpr *Exp) { 1509 NamedDecl *D = dyn_cast_or_null<NamedDecl>(Exp->getCalleeDecl()); 1510 if(!D || !D->hasAttrs()) 1511 return; 1512 handleCall(Exp, D); 1513} 1514 1515void BuildLockset::VisitCXXConstructExpr(CXXConstructExpr *Exp) { 1516 // FIXME -- only handles constructors in DeclStmt below. 1517} 1518 1519void BuildLockset::VisitDeclStmt(DeclStmt *S) { 1520 // adjust the context 1521 LVarCtx = Analyzer->LocalVarMap.getNextContext(CtxIndex, S, LVarCtx); 1522 1523 DeclGroupRef DGrp = S->getDeclGroup(); 1524 for (DeclGroupRef::iterator I = DGrp.begin(), E = DGrp.end(); I != E; ++I) { 1525 Decl *D = *I; 1526 if (VarDecl *VD = dyn_cast_or_null<VarDecl>(D)) { 1527 Expr *E = VD->getInit(); 1528 // handle constructors that involve temporaries 1529 if (ExprWithCleanups *EWC = dyn_cast_or_null<ExprWithCleanups>(E)) 1530 E = EWC->getSubExpr(); 1531 1532 if (CXXConstructExpr *CE = dyn_cast_or_null<CXXConstructExpr>(E)) { 1533 NamedDecl *CtorD = dyn_cast_or_null<NamedDecl>(CE->getConstructor()); 1534 if (!CtorD || !CtorD->hasAttrs()) 1535 return; 1536 handleCall(CE, CtorD, VD); 1537 } 1538 } 1539 } 1540} 1541 1542 1543 1544/// \brief Compute the intersection of two locksets and issue warnings for any 1545/// locks in the symmetric difference. 1546/// 1547/// This function is used at a merge point in the CFG when comparing the lockset 1548/// of each branch being merged. For example, given the following sequence: 1549/// A; if () then B; else C; D; we need to check that the lockset after B and C 1550/// are the same. In the event of a difference, we use the intersection of these 1551/// two locksets at the start of D. 1552/// 1553/// \param LSet1 The first lockset. 1554/// \param LSet2 The second lockset. 1555/// \param JoinLoc The location of the join point for error reporting 1556/// \param LEK1 The error message to report if a mutex is missing from LSet1 1557/// \param LEK2 The error message to report if a mutex is missing from Lset2 1558Lockset ThreadSafetyAnalyzer::intersectAndWarn(const Lockset &LSet1, 1559 const Lockset &LSet2, 1560 SourceLocation JoinLoc, 1561 LockErrorKind LEK1, 1562 LockErrorKind LEK2) { 1563 Lockset Intersection = LSet1; 1564 1565 for (Lockset::iterator I = LSet2.begin(), E = LSet2.end(); I != E; ++I) { 1566 const MutexID &LSet2Mutex = I.getKey(); 1567 const LockData &LDat2 = I.getData(); 1568 if (const LockData *LDat1 = LSet1.lookup(LSet2Mutex)) { 1569 if (LDat1->LKind != LDat2.LKind) { 1570 Handler.handleExclusiveAndShared(LSet2Mutex.getName(), 1571 LDat2.AcquireLoc, 1572 LDat1->AcquireLoc); 1573 if (LDat1->LKind != LK_Exclusive) 1574 Intersection = LocksetFactory.add(Intersection, LSet2Mutex, LDat2); 1575 } 1576 } else { 1577 if (LDat2.UnderlyingMutex.isValid()) { 1578 if (LSet2.lookup(LDat2.UnderlyingMutex)) { 1579 // If this is a scoped lock that manages another mutex, and if the 1580 // underlying mutex is still held, then warn about the underlying 1581 // mutex. 1582 Handler.handleMutexHeldEndOfScope(LDat2.UnderlyingMutex.getName(), 1583 LDat2.AcquireLoc, 1584 JoinLoc, LEK1); 1585 } 1586 } 1587 else if (!LDat2.Managed) 1588 Handler.handleMutexHeldEndOfScope(LSet2Mutex.getName(), 1589 LDat2.AcquireLoc, 1590 JoinLoc, LEK1); 1591 } 1592 } 1593 1594 for (Lockset::iterator I = LSet1.begin(), E = LSet1.end(); I != E; ++I) { 1595 if (!LSet2.contains(I.getKey())) { 1596 const MutexID &Mutex = I.getKey(); 1597 const LockData &LDat1 = I.getData(); 1598 1599 if (LDat1.UnderlyingMutex.isValid()) { 1600 if (LSet1.lookup(LDat1.UnderlyingMutex)) { 1601 // If this is a scoped lock that manages another mutex, and if the 1602 // underlying mutex is still held, then warn about the underlying 1603 // mutex. 1604 Handler.handleMutexHeldEndOfScope(LDat1.UnderlyingMutex.getName(), 1605 LDat1.AcquireLoc, 1606 JoinLoc, LEK1); 1607 } 1608 } 1609 else if (!LDat1.Managed) 1610 Handler.handleMutexHeldEndOfScope(Mutex.getName(), 1611 LDat1.AcquireLoc, 1612 JoinLoc, LEK2); 1613 Intersection = LocksetFactory.remove(Intersection, Mutex); 1614 } 1615 } 1616 return Intersection; 1617} 1618 1619 1620/// \brief Check a function's CFG for thread-safety violations. 1621/// 1622/// We traverse the blocks in the CFG, compute the set of mutexes that are held 1623/// at the end of each block, and issue warnings for thread safety violations. 1624/// Each block in the CFG is traversed exactly once. 1625void ThreadSafetyAnalyzer::runAnalysis(AnalysisDeclContext &AC) { 1626 CFG *CFGraph = AC.getCFG(); 1627 if (!CFGraph) return; 1628 const NamedDecl *D = dyn_cast_or_null<NamedDecl>(AC.getDecl()); 1629 1630 // AC.dumpCFG(true); 1631 1632 if (!D) 1633 return; // Ignore anonymous functions for now. 1634 if (D->getAttr<NoThreadSafetyAnalysisAttr>()) 1635 return; 1636 // FIXME: Do something a bit more intelligent inside constructor and 1637 // destructor code. Constructors and destructors must assume unique access 1638 // to 'this', so checks on member variable access is disabled, but we should 1639 // still enable checks on other objects. 1640 if (isa<CXXConstructorDecl>(D)) 1641 return; // Don't check inside constructors. 1642 if (isa<CXXDestructorDecl>(D)) 1643 return; // Don't check inside destructors. 1644 1645 BlockInfo.resize(CFGraph->getNumBlockIDs(), 1646 CFGBlockInfo::getEmptyBlockInfo(LocksetFactory, LocalVarMap)); 1647 1648 // We need to explore the CFG via a "topological" ordering. 1649 // That way, we will be guaranteed to have information about required 1650 // predecessor locksets when exploring a new block. 1651 PostOrderCFGView *SortedGraph = AC.getAnalysis<PostOrderCFGView>(); 1652 PostOrderCFGView::CFGBlockSet VisitedBlocks(CFGraph); 1653 1654 // Compute SSA names for local variables 1655 LocalVarMap.traverseCFG(CFGraph, SortedGraph, BlockInfo); 1656 1657 // Fill in source locations for all CFGBlocks. 1658 findBlockLocations(CFGraph, SortedGraph, BlockInfo); 1659 1660 // Add locks from exclusive_locks_required and shared_locks_required 1661 // to initial lockset. Also turn off checking for lock and unlock functions. 1662 // FIXME: is there a more intelligent way to check lock/unlock functions? 1663 if (!SortedGraph->empty() && D->hasAttrs()) { 1664 const CFGBlock *FirstBlock = *SortedGraph->begin(); 1665 Lockset &InitialLockset = BlockInfo[FirstBlock->getBlockID()].EntrySet; 1666 const AttrVec &ArgAttrs = D->getAttrs(); 1667 for (unsigned i = 0; i < ArgAttrs.size(); ++i) { 1668 Attr *Attr = ArgAttrs[i]; 1669 SourceLocation AttrLoc = Attr->getLocation(); 1670 if (SharedLocksRequiredAttr *SLRAttr 1671 = dyn_cast<SharedLocksRequiredAttr>(Attr)) { 1672 for (SharedLocksRequiredAttr::args_iterator 1673 SLRIter = SLRAttr->args_begin(), 1674 SLREnd = SLRAttr->args_end(); SLRIter != SLREnd; ++SLRIter) 1675 InitialLockset = addLock(InitialLockset, *SLRIter, D, 1676 LockData(AttrLoc, LK_Shared), false); 1677 } else if (ExclusiveLocksRequiredAttr *ELRAttr 1678 = dyn_cast<ExclusiveLocksRequiredAttr>(Attr)) { 1679 for (ExclusiveLocksRequiredAttr::args_iterator 1680 ELRIter = ELRAttr->args_begin(), 1681 ELREnd = ELRAttr->args_end(); ELRIter != ELREnd; ++ELRIter) 1682 InitialLockset = addLock(InitialLockset, *ELRIter, D, 1683 LockData(AttrLoc, LK_Exclusive), false); 1684 } else if (isa<UnlockFunctionAttr>(Attr)) { 1685 // Don't try to check unlock functions for now 1686 return; 1687 } else if (isa<ExclusiveLockFunctionAttr>(Attr)) { 1688 // Don't try to check lock functions for now 1689 return; 1690 } else if (isa<SharedLockFunctionAttr>(Attr)) { 1691 // Don't try to check lock functions for now 1692 return; 1693 } else if (isa<ExclusiveTrylockFunctionAttr>(Attr)) { 1694 // Don't try to check trylock functions for now 1695 return; 1696 } else if (isa<SharedTrylockFunctionAttr>(Attr)) { 1697 // Don't try to check trylock functions for now 1698 return; 1699 } 1700 } 1701 } 1702 1703 for (PostOrderCFGView::iterator I = SortedGraph->begin(), 1704 E = SortedGraph->end(); I!= E; ++I) { 1705 const CFGBlock *CurrBlock = *I; 1706 int CurrBlockID = CurrBlock->getBlockID(); 1707 CFGBlockInfo *CurrBlockInfo = &BlockInfo[CurrBlockID]; 1708 1709 // Use the default initial lockset in case there are no predecessors. 1710 VisitedBlocks.insert(CurrBlock); 1711 1712 // Iterate through the predecessor blocks and warn if the lockset for all 1713 // predecessors is not the same. We take the entry lockset of the current 1714 // block to be the intersection of all previous locksets. 1715 // FIXME: By keeping the intersection, we may output more errors in future 1716 // for a lock which is not in the intersection, but was in the union. We 1717 // may want to also keep the union in future. As an example, let's say 1718 // the intersection contains Mutex L, and the union contains L and M. 1719 // Later we unlock M. At this point, we would output an error because we 1720 // never locked M; although the real error is probably that we forgot to 1721 // lock M on all code paths. Conversely, let's say that later we lock M. 1722 // In this case, we should compare against the intersection instead of the 1723 // union because the real error is probably that we forgot to unlock M on 1724 // all code paths. 1725 bool LocksetInitialized = false; 1726 llvm::SmallVector<CFGBlock*, 8> SpecialBlocks; 1727 for (CFGBlock::const_pred_iterator PI = CurrBlock->pred_begin(), 1728 PE = CurrBlock->pred_end(); PI != PE; ++PI) { 1729 1730 // if *PI -> CurrBlock is a back edge 1731 if (*PI == 0 || !VisitedBlocks.alreadySet(*PI)) 1732 continue; 1733 1734 // Ignore edges from blocks that can't return. 1735 if ((*PI)->hasNoReturnElement()) 1736 continue; 1737 1738 // If the previous block ended in a 'continue' or 'break' statement, then 1739 // a difference in locksets is probably due to a bug in that block, rather 1740 // than in some other predecessor. In that case, keep the other 1741 // predecessor's lockset. 1742 if (const Stmt *Terminator = (*PI)->getTerminator()) { 1743 if (isa<ContinueStmt>(Terminator) || isa<BreakStmt>(Terminator)) { 1744 SpecialBlocks.push_back(*PI); 1745 continue; 1746 } 1747 } 1748 1749 int PrevBlockID = (*PI)->getBlockID(); 1750 CFGBlockInfo *PrevBlockInfo = &BlockInfo[PrevBlockID]; 1751 Lockset PrevLockset = 1752 getEdgeLockset(PrevBlockInfo->ExitSet, *PI, CurrBlock); 1753 1754 if (!LocksetInitialized) { 1755 CurrBlockInfo->EntrySet = PrevLockset; 1756 LocksetInitialized = true; 1757 } else { 1758 CurrBlockInfo->EntrySet = 1759 intersectAndWarn(CurrBlockInfo->EntrySet, PrevLockset, 1760 CurrBlockInfo->EntryLoc, 1761 LEK_LockedSomePredecessors); 1762 } 1763 } 1764 1765 // Process continue and break blocks. Assume that the lockset for the 1766 // resulting block is unaffected by any discrepancies in them. 1767 for (unsigned SpecialI = 0, SpecialN = SpecialBlocks.size(); 1768 SpecialI < SpecialN; ++SpecialI) { 1769 CFGBlock *PrevBlock = SpecialBlocks[SpecialI]; 1770 int PrevBlockID = PrevBlock->getBlockID(); 1771 CFGBlockInfo *PrevBlockInfo = &BlockInfo[PrevBlockID]; 1772 1773 if (!LocksetInitialized) { 1774 CurrBlockInfo->EntrySet = PrevBlockInfo->ExitSet; 1775 LocksetInitialized = true; 1776 } else { 1777 // Determine whether this edge is a loop terminator for diagnostic 1778 // purposes. FIXME: A 'break' statement might be a loop terminator, but 1779 // it might also be part of a switch. Also, a subsequent destructor 1780 // might add to the lockset, in which case the real issue might be a 1781 // double lock on the other path. 1782 const Stmt *Terminator = PrevBlock->getTerminator(); 1783 bool IsLoop = Terminator && isa<ContinueStmt>(Terminator); 1784 1785 Lockset PrevLockset = 1786 getEdgeLockset(PrevBlockInfo->ExitSet, PrevBlock, CurrBlock); 1787 1788 // Do not update EntrySet. 1789 intersectAndWarn(CurrBlockInfo->EntrySet, PrevLockset, 1790 PrevBlockInfo->ExitLoc, 1791 IsLoop ? LEK_LockedSomeLoopIterations 1792 : LEK_LockedSomePredecessors); 1793 } 1794 } 1795 1796 BuildLockset LocksetBuilder(this, *CurrBlockInfo); 1797 1798 // Visit all the statements in the basic block. 1799 for (CFGBlock::const_iterator BI = CurrBlock->begin(), 1800 BE = CurrBlock->end(); BI != BE; ++BI) { 1801 switch (BI->getKind()) { 1802 case CFGElement::Statement: { 1803 const CFGStmt *CS = cast<CFGStmt>(&*BI); 1804 LocksetBuilder.Visit(const_cast<Stmt*>(CS->getStmt())); 1805 break; 1806 } 1807 // Ignore BaseDtor, MemberDtor, and TemporaryDtor for now. 1808 case CFGElement::AutomaticObjectDtor: { 1809 const CFGAutomaticObjDtor *AD = cast<CFGAutomaticObjDtor>(&*BI); 1810 CXXDestructorDecl *DD = const_cast<CXXDestructorDecl*>( 1811 AD->getDestructorDecl(AC.getASTContext())); 1812 if (!DD->hasAttrs()) 1813 break; 1814 1815 // Create a dummy expression, 1816 VarDecl *VD = const_cast<VarDecl*>(AD->getVarDecl()); 1817 DeclRefExpr DRE(VD, false, VD->getType(), VK_LValue, 1818 AD->getTriggerStmt()->getLocEnd()); 1819 LocksetBuilder.handleCall(&DRE, DD); 1820 break; 1821 } 1822 default: 1823 break; 1824 } 1825 } 1826 CurrBlockInfo->ExitSet = LocksetBuilder.LSet; 1827 1828 // For every back edge from CurrBlock (the end of the loop) to another block 1829 // (FirstLoopBlock) we need to check that the Lockset of Block is equal to 1830 // the one held at the beginning of FirstLoopBlock. We can look up the 1831 // Lockset held at the beginning of FirstLoopBlock in the EntryLockSets map. 1832 for (CFGBlock::const_succ_iterator SI = CurrBlock->succ_begin(), 1833 SE = CurrBlock->succ_end(); SI != SE; ++SI) { 1834 1835 // if CurrBlock -> *SI is *not* a back edge 1836 if (*SI == 0 || !VisitedBlocks.alreadySet(*SI)) 1837 continue; 1838 1839 CFGBlock *FirstLoopBlock = *SI; 1840 CFGBlockInfo *PreLoop = &BlockInfo[FirstLoopBlock->getBlockID()]; 1841 CFGBlockInfo *LoopEnd = &BlockInfo[CurrBlockID]; 1842 intersectAndWarn(LoopEnd->ExitSet, PreLoop->EntrySet, 1843 PreLoop->EntryLoc, 1844 LEK_LockedSomeLoopIterations); 1845 } 1846 } 1847 1848 CFGBlockInfo *Initial = &BlockInfo[CFGraph->getEntry().getBlockID()]; 1849 CFGBlockInfo *Final = &BlockInfo[CFGraph->getExit().getBlockID()]; 1850 1851 // FIXME: Should we call this function for all blocks which exit the function? 1852 intersectAndWarn(Initial->EntrySet, Final->ExitSet, 1853 Final->ExitLoc, 1854 LEK_LockedAtEndOfFunction, 1855 LEK_NotLockedAtEndOfFunction); 1856} 1857 1858} // end anonymous namespace 1859 1860 1861namespace clang { 1862namespace thread_safety { 1863 1864/// \brief Check a function's CFG for thread-safety violations. 1865/// 1866/// We traverse the blocks in the CFG, compute the set of mutexes that are held 1867/// at the end of each block, and issue warnings for thread safety violations. 1868/// Each block in the CFG is traversed exactly once. 1869void runThreadSafetyAnalysis(AnalysisDeclContext &AC, 1870 ThreadSafetyHandler &Handler) { 1871 ThreadSafetyAnalyzer Analyzer(Handler); 1872 Analyzer.runAnalysis(AC); 1873} 1874 1875/// \brief Helper function that returns a LockKind required for the given level 1876/// of access. 1877LockKind getLockKindFromAccessKind(AccessKind AK) { 1878 switch (AK) { 1879 case AK_Read : 1880 return LK_Shared; 1881 case AK_Written : 1882 return LK_Exclusive; 1883 } 1884 llvm_unreachable("Unknown AccessKind"); 1885} 1886 1887}} // end namespace clang::thread_safety 1888