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