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