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