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