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/ThreadSafetyAnalysis.html 14 // for more information. 15 // 16 //===----------------------------------------------------------------------===// 17 18 #include "clang/AST/Attr.h" 19 #include "clang/AST/DeclCXX.h" 20 #include "clang/AST/ExprCXX.h" 21 #include "clang/AST/StmtCXX.h" 22 #include "clang/AST/StmtVisitor.h" 23 #include "clang/Analysis/Analyses/PostOrderCFGView.h" 24 #include "clang/Analysis/Analyses/ThreadSafety.h" 25 #include "clang/Analysis/Analyses/ThreadSafetyCommon.h" 26 #include "clang/Analysis/Analyses/ThreadSafetyLogical.h" 27 #include "clang/Analysis/Analyses/ThreadSafetyTIL.h" 28 #include "clang/Analysis/Analyses/ThreadSafetyTraverse.h" 29 #include "clang/Analysis/AnalysisContext.h" 30 #include "clang/Analysis/CFG.h" 31 #include "clang/Analysis/CFGStmtMap.h" 32 #include "clang/Basic/OperatorKinds.h" 33 #include "clang/Basic/SourceLocation.h" 34 #include "clang/Basic/SourceManager.h" 35 #include "llvm/ADT/BitVector.h" 36 #include "llvm/ADT/FoldingSet.h" 37 #include "llvm/ADT/ImmutableMap.h" 38 #include "llvm/ADT/PostOrderIterator.h" 39 #include "llvm/ADT/SmallVector.h" 40 #include "llvm/ADT/StringRef.h" 41 #include "llvm/Support/raw_ostream.h" 42 #include <algorithm> 43 #include <ostream> 44 #include <sstream> 45 #include <utility> 46 #include <vector> 47 using namespace clang; 48 using namespace threadSafety; 49 50 // Key method definition 51 ThreadSafetyHandler::~ThreadSafetyHandler() {} 52 53 namespace { 54 class TILPrinter : 55 public til::PrettyPrinter<TILPrinter, llvm::raw_ostream> {}; 56 57 58 /// Issue a warning about an invalid lock expression 59 static void warnInvalidLock(ThreadSafetyHandler &Handler, 60 const Expr *MutexExp, const NamedDecl *D, 61 const Expr *DeclExp, StringRef Kind) { 62 SourceLocation Loc; 63 if (DeclExp) 64 Loc = DeclExp->getExprLoc(); 65 66 // FIXME: add a note about the attribute location in MutexExp or D 67 if (Loc.isValid()) 68 Handler.handleInvalidLockExp(Kind, Loc); 69 } 70 71 /// \brief A set of CapabilityInfo objects, which are compiled from the 72 /// requires attributes on a function. 73 class CapExprSet : public SmallVector<CapabilityExpr, 4> { 74 public: 75 /// \brief Push M onto list, but discard duplicates. 76 void push_back_nodup(const CapabilityExpr &CapE) { 77 iterator It = std::find_if(begin(), end(), 78 [=](const CapabilityExpr &CapE2) { 79 return CapE.equals(CapE2); 80 }); 81 if (It == end()) 82 push_back(CapE); 83 } 84 }; 85 86 class FactManager; 87 class FactSet; 88 89 /// \brief This is a helper class that stores a fact that is known at a 90 /// particular point in program execution. Currently, a fact is a capability, 91 /// along with additional information, such as where it was acquired, whether 92 /// it is exclusive or shared, etc. 93 /// 94 /// FIXME: this analysis does not currently support either re-entrant 95 /// locking or lock "upgrading" and "downgrading" between exclusive and 96 /// shared. 97 class FactEntry : public CapabilityExpr { 98 private: 99 LockKind LKind; ///< exclusive or shared 100 SourceLocation AcquireLoc; ///< where it was acquired. 101 bool Asserted; ///< true if the lock was asserted 102 bool Declared; ///< true if the lock was declared 103 104 public: 105 FactEntry(const CapabilityExpr &CE, LockKind LK, SourceLocation Loc, 106 bool Asrt, bool Declrd = false) 107 : CapabilityExpr(CE), LKind(LK), AcquireLoc(Loc), Asserted(Asrt), 108 Declared(Declrd) {} 109 110 virtual ~FactEntry() {} 111 112 LockKind kind() const { return LKind; } 113 SourceLocation loc() const { return AcquireLoc; } 114 bool asserted() const { return Asserted; } 115 bool declared() const { return Declared; } 116 117 void setDeclared(bool D) { Declared = D; } 118 119 virtual void 120 handleRemovalFromIntersection(const FactSet &FSet, FactManager &FactMan, 121 SourceLocation JoinLoc, LockErrorKind LEK, 122 ThreadSafetyHandler &Handler) const = 0; 123 virtual void handleUnlock(FactSet &FSet, FactManager &FactMan, 124 const CapabilityExpr &Cp, SourceLocation UnlockLoc, 125 bool FullyRemove, ThreadSafetyHandler &Handler, 126 StringRef DiagKind) const = 0; 127 128 // Return true if LKind >= LK, where exclusive > shared 129 bool isAtLeast(LockKind LK) { 130 return (LKind == LK_Exclusive) || (LK == LK_Shared); 131 } 132 }; 133 134 135 typedef unsigned short FactID; 136 137 /// \brief FactManager manages the memory for all facts that are created during 138 /// the analysis of a single routine. 139 class FactManager { 140 private: 141 std::vector<std::unique_ptr<FactEntry>> Facts; 142 143 public: 144 FactID newFact(std::unique_ptr<FactEntry> Entry) { 145 Facts.push_back(std::move(Entry)); 146 return static_cast<unsigned short>(Facts.size() - 1); 147 } 148 149 const FactEntry &operator[](FactID F) const { return *Facts[F]; } 150 FactEntry &operator[](FactID F) { return *Facts[F]; } 151 }; 152 153 154 /// \brief A FactSet is the set of facts that are known to be true at a 155 /// particular program point. FactSets must be small, because they are 156 /// frequently copied, and are thus implemented as a set of indices into a 157 /// table maintained by a FactManager. A typical FactSet only holds 1 or 2 158 /// locks, so we can get away with doing a linear search for lookup. Note 159 /// that a hashtable or map is inappropriate in this case, because lookups 160 /// may involve partial pattern matches, rather than exact matches. 161 class FactSet { 162 private: 163 typedef SmallVector<FactID, 4> FactVec; 164 165 FactVec FactIDs; 166 167 public: 168 typedef FactVec::iterator iterator; 169 typedef FactVec::const_iterator const_iterator; 170 171 iterator begin() { return FactIDs.begin(); } 172 const_iterator begin() const { return FactIDs.begin(); } 173 174 iterator end() { return FactIDs.end(); } 175 const_iterator end() const { return FactIDs.end(); } 176 177 bool isEmpty() const { return FactIDs.size() == 0; } 178 179 // Return true if the set contains only negative facts 180 bool isEmpty(FactManager &FactMan) const { 181 for (FactID FID : *this) { 182 if (!FactMan[FID].negative()) 183 return false; 184 } 185 return true; 186 } 187 188 void addLockByID(FactID ID) { FactIDs.push_back(ID); } 189 190 FactID addLock(FactManager &FM, std::unique_ptr<FactEntry> Entry) { 191 FactID F = FM.newFact(std::move(Entry)); 192 FactIDs.push_back(F); 193 return F; 194 } 195 196 bool removeLock(FactManager& FM, const CapabilityExpr &CapE) { 197 unsigned n = FactIDs.size(); 198 if (n == 0) 199 return false; 200 201 for (unsigned i = 0; i < n-1; ++i) { 202 if (FM[FactIDs[i]].matches(CapE)) { 203 FactIDs[i] = FactIDs[n-1]; 204 FactIDs.pop_back(); 205 return true; 206 } 207 } 208 if (FM[FactIDs[n-1]].matches(CapE)) { 209 FactIDs.pop_back(); 210 return true; 211 } 212 return false; 213 } 214 215 iterator findLockIter(FactManager &FM, const CapabilityExpr &CapE) { 216 return std::find_if(begin(), end(), [&](FactID ID) { 217 return FM[ID].matches(CapE); 218 }); 219 } 220 221 FactEntry *findLock(FactManager &FM, const CapabilityExpr &CapE) const { 222 auto I = std::find_if(begin(), end(), [&](FactID ID) { 223 return FM[ID].matches(CapE); 224 }); 225 return I != end() ? &FM[*I] : nullptr; 226 } 227 228 FactEntry *findLockUniv(FactManager &FM, const CapabilityExpr &CapE) const { 229 auto I = std::find_if(begin(), end(), [&](FactID ID) -> bool { 230 return FM[ID].matchesUniv(CapE); 231 }); 232 return I != end() ? &FM[*I] : nullptr; 233 } 234 235 FactEntry *findPartialMatch(FactManager &FM, 236 const CapabilityExpr &CapE) const { 237 auto I = std::find_if(begin(), end(), [&](FactID ID) -> bool { 238 return FM[ID].partiallyMatches(CapE); 239 }); 240 return I != end() ? &FM[*I] : nullptr; 241 } 242 243 bool containsMutexDecl(FactManager &FM, const ValueDecl* Vd) const { 244 auto I = std::find_if(begin(), end(), [&](FactID ID) -> bool { 245 return FM[ID].valueDecl() == Vd; 246 }); 247 return I != end(); 248 } 249 }; 250 251 class ThreadSafetyAnalyzer; 252 } // namespace 253 254 namespace clang { 255 namespace threadSafety { 256 class BeforeSet { 257 private: 258 typedef SmallVector<const ValueDecl*, 4> BeforeVect; 259 260 struct BeforeInfo { 261 BeforeInfo() : Vect(nullptr), Visited(false) { } 262 BeforeInfo(BeforeInfo &&O) 263 : Vect(std::move(O.Vect)), Visited(O.Visited) 264 {} 265 266 std::unique_ptr<BeforeVect> Vect; 267 int Visited; 268 }; 269 270 typedef llvm::DenseMap<const ValueDecl*, BeforeInfo> BeforeMap; 271 typedef llvm::DenseMap<const ValueDecl*, bool> CycleMap; 272 273 public: 274 BeforeSet() { } 275 276 BeforeInfo* insertAttrExprs(const ValueDecl* Vd, 277 ThreadSafetyAnalyzer& Analyzer); 278 279 void checkBeforeAfter(const ValueDecl* Vd, 280 const FactSet& FSet, 281 ThreadSafetyAnalyzer& Analyzer, 282 SourceLocation Loc, StringRef CapKind); 283 284 private: 285 BeforeMap BMap; 286 CycleMap CycMap; 287 }; 288 } // end namespace threadSafety 289 } // end namespace clang 290 291 namespace { 292 typedef llvm::ImmutableMap<const NamedDecl*, unsigned> LocalVarContext; 293 class LocalVariableMap; 294 295 /// A side (entry or exit) of a CFG node. 296 enum CFGBlockSide { CBS_Entry, CBS_Exit }; 297 298 /// CFGBlockInfo is a struct which contains all the information that is 299 /// maintained for each block in the CFG. See LocalVariableMap for more 300 /// information about the contexts. 301 struct CFGBlockInfo { 302 FactSet EntrySet; // Lockset held at entry to block 303 FactSet ExitSet; // Lockset held at exit from block 304 LocalVarContext EntryContext; // Context held at entry to block 305 LocalVarContext ExitContext; // Context held at exit from block 306 SourceLocation EntryLoc; // Location of first statement in block 307 SourceLocation ExitLoc; // Location of last statement in block. 308 unsigned EntryIndex; // Used to replay contexts later 309 bool Reachable; // Is this block reachable? 310 311 const FactSet &getSet(CFGBlockSide Side) const { 312 return Side == CBS_Entry ? EntrySet : ExitSet; 313 } 314 SourceLocation getLocation(CFGBlockSide Side) const { 315 return Side == CBS_Entry ? EntryLoc : ExitLoc; 316 } 317 318 private: 319 CFGBlockInfo(LocalVarContext EmptyCtx) 320 : EntryContext(EmptyCtx), ExitContext(EmptyCtx), Reachable(false) 321 { } 322 323 public: 324 static CFGBlockInfo getEmptyBlockInfo(LocalVariableMap &M); 325 }; 326 327 328 329 // A LocalVariableMap maintains a map from local variables to their currently 330 // valid definitions. It provides SSA-like functionality when traversing the 331 // CFG. Like SSA, each definition or assignment to a variable is assigned a 332 // unique name (an integer), which acts as the SSA name for that definition. 333 // The total set of names is shared among all CFG basic blocks. 334 // Unlike SSA, we do not rewrite expressions to replace local variables declrefs 335 // with their SSA-names. Instead, we compute a Context for each point in the 336 // code, which maps local variables to the appropriate SSA-name. This map 337 // changes with each assignment. 338 // 339 // The map is computed in a single pass over the CFG. Subsequent analyses can 340 // then query the map to find the appropriate Context for a statement, and use 341 // that Context to look up the definitions of variables. 342 class LocalVariableMap { 343 public: 344 typedef LocalVarContext Context; 345 346 /// A VarDefinition consists of an expression, representing the value of the 347 /// variable, along with the context in which that expression should be 348 /// interpreted. A reference VarDefinition does not itself contain this 349 /// information, but instead contains a pointer to a previous VarDefinition. 350 struct VarDefinition { 351 public: 352 friend class LocalVariableMap; 353 354 const NamedDecl *Dec; // The original declaration for this variable. 355 const Expr *Exp; // The expression for this variable, OR 356 unsigned Ref; // Reference to another VarDefinition 357 Context Ctx; // The map with which Exp should be interpreted. 358 359 bool isReference() { return !Exp; } 360 361 private: 362 // Create ordinary variable definition 363 VarDefinition(const NamedDecl *D, const Expr *E, Context C) 364 : Dec(D), Exp(E), Ref(0), Ctx(C) 365 { } 366 367 // Create reference to previous definition 368 VarDefinition(const NamedDecl *D, unsigned R, Context C) 369 : Dec(D), Exp(nullptr), Ref(R), Ctx(C) 370 { } 371 }; 372 373 private: 374 Context::Factory ContextFactory; 375 std::vector<VarDefinition> VarDefinitions; 376 std::vector<unsigned> CtxIndices; 377 std::vector<std::pair<Stmt*, Context> > SavedContexts; 378 379 public: 380 LocalVariableMap() { 381 // index 0 is a placeholder for undefined variables (aka phi-nodes). 382 VarDefinitions.push_back(VarDefinition(nullptr, 0u, getEmptyContext())); 383 } 384 385 /// Look up a definition, within the given context. 386 const VarDefinition* lookup(const NamedDecl *D, Context Ctx) { 387 const unsigned *i = Ctx.lookup(D); 388 if (!i) 389 return nullptr; 390 assert(*i < VarDefinitions.size()); 391 return &VarDefinitions[*i]; 392 } 393 394 /// Look up the definition for D within the given context. Returns 395 /// NULL if the expression is not statically known. If successful, also 396 /// modifies Ctx to hold the context of the return Expr. 397 const Expr* lookupExpr(const NamedDecl *D, Context &Ctx) { 398 const unsigned *P = Ctx.lookup(D); 399 if (!P) 400 return nullptr; 401 402 unsigned i = *P; 403 while (i > 0) { 404 if (VarDefinitions[i].Exp) { 405 Ctx = VarDefinitions[i].Ctx; 406 return VarDefinitions[i].Exp; 407 } 408 i = VarDefinitions[i].Ref; 409 } 410 return nullptr; 411 } 412 413 Context getEmptyContext() { return ContextFactory.getEmptyMap(); } 414 415 /// Return the next context after processing S. This function is used by 416 /// clients of the class to get the appropriate context when traversing the 417 /// CFG. It must be called for every assignment or DeclStmt. 418 Context getNextContext(unsigned &CtxIndex, Stmt *S, Context C) { 419 if (SavedContexts[CtxIndex+1].first == S) { 420 CtxIndex++; 421 Context Result = SavedContexts[CtxIndex].second; 422 return Result; 423 } 424 return C; 425 } 426 427 void dumpVarDefinitionName(unsigned i) { 428 if (i == 0) { 429 llvm::errs() << "Undefined"; 430 return; 431 } 432 const NamedDecl *Dec = VarDefinitions[i].Dec; 433 if (!Dec) { 434 llvm::errs() << "<<NULL>>"; 435 return; 436 } 437 Dec->printName(llvm::errs()); 438 llvm::errs() << "." << i << " " << ((const void*) Dec); 439 } 440 441 /// Dumps an ASCII representation of the variable map to llvm::errs() 442 void dump() { 443 for (unsigned i = 1, e = VarDefinitions.size(); i < e; ++i) { 444 const Expr *Exp = VarDefinitions[i].Exp; 445 unsigned Ref = VarDefinitions[i].Ref; 446 447 dumpVarDefinitionName(i); 448 llvm::errs() << " = "; 449 if (Exp) Exp->dump(); 450 else { 451 dumpVarDefinitionName(Ref); 452 llvm::errs() << "\n"; 453 } 454 } 455 } 456 457 /// Dumps an ASCII representation of a Context to llvm::errs() 458 void dumpContext(Context C) { 459 for (Context::iterator I = C.begin(), E = C.end(); I != E; ++I) { 460 const NamedDecl *D = I.getKey(); 461 D->printName(llvm::errs()); 462 const unsigned *i = C.lookup(D); 463 llvm::errs() << " -> "; 464 dumpVarDefinitionName(*i); 465 llvm::errs() << "\n"; 466 } 467 } 468 469 /// Builds the variable map. 470 void traverseCFG(CFG *CFGraph, const PostOrderCFGView *SortedGraph, 471 std::vector<CFGBlockInfo> &BlockInfo); 472 473 protected: 474 // Get the current context index 475 unsigned getContextIndex() { return SavedContexts.size()-1; } 476 477 // Save the current context for later replay 478 void saveContext(Stmt *S, Context C) { 479 SavedContexts.push_back(std::make_pair(S,C)); 480 } 481 482 // Adds a new definition to the given context, and returns a new context. 483 // This method should be called when declaring a new variable. 484 Context addDefinition(const NamedDecl *D, const Expr *Exp, Context Ctx) { 485 assert(!Ctx.contains(D)); 486 unsigned newID = VarDefinitions.size(); 487 Context NewCtx = ContextFactory.add(Ctx, D, newID); 488 VarDefinitions.push_back(VarDefinition(D, Exp, Ctx)); 489 return NewCtx; 490 } 491 492 // Add a new reference to an existing definition. 493 Context addReference(const NamedDecl *D, unsigned i, Context Ctx) { 494 unsigned newID = VarDefinitions.size(); 495 Context NewCtx = ContextFactory.add(Ctx, D, newID); 496 VarDefinitions.push_back(VarDefinition(D, i, Ctx)); 497 return NewCtx; 498 } 499 500 // Updates a definition only if that definition is already in the map. 501 // This method should be called when assigning to an existing variable. 502 Context updateDefinition(const NamedDecl *D, Expr *Exp, Context Ctx) { 503 if (Ctx.contains(D)) { 504 unsigned newID = VarDefinitions.size(); 505 Context NewCtx = ContextFactory.remove(Ctx, D); 506 NewCtx = ContextFactory.add(NewCtx, D, newID); 507 VarDefinitions.push_back(VarDefinition(D, Exp, Ctx)); 508 return NewCtx; 509 } 510 return Ctx; 511 } 512 513 // Removes a definition from the context, but keeps the variable name 514 // as a valid variable. The index 0 is a placeholder for cleared definitions. 515 Context clearDefinition(const NamedDecl *D, Context Ctx) { 516 Context NewCtx = Ctx; 517 if (NewCtx.contains(D)) { 518 NewCtx = ContextFactory.remove(NewCtx, D); 519 NewCtx = ContextFactory.add(NewCtx, D, 0); 520 } 521 return NewCtx; 522 } 523 524 // Remove a definition entirely frmo the context. 525 Context removeDefinition(const NamedDecl *D, Context Ctx) { 526 Context NewCtx = Ctx; 527 if (NewCtx.contains(D)) { 528 NewCtx = ContextFactory.remove(NewCtx, D); 529 } 530 return NewCtx; 531 } 532 533 Context intersectContexts(Context C1, Context C2); 534 Context createReferenceContext(Context C); 535 void intersectBackEdge(Context C1, Context C2); 536 537 friend class VarMapBuilder; 538 }; 539 540 541 // This has to be defined after LocalVariableMap. 542 CFGBlockInfo CFGBlockInfo::getEmptyBlockInfo(LocalVariableMap &M) { 543 return CFGBlockInfo(M.getEmptyContext()); 544 } 545 546 547 /// Visitor which builds a LocalVariableMap 548 class VarMapBuilder : public StmtVisitor<VarMapBuilder> { 549 public: 550 LocalVariableMap* VMap; 551 LocalVariableMap::Context Ctx; 552 553 VarMapBuilder(LocalVariableMap *VM, LocalVariableMap::Context C) 554 : VMap(VM), Ctx(C) {} 555 556 void VisitDeclStmt(DeclStmt *S); 557 void VisitBinaryOperator(BinaryOperator *BO); 558 }; 559 560 561 // Add new local variables to the variable map 562 void VarMapBuilder::VisitDeclStmt(DeclStmt *S) { 563 bool modifiedCtx = false; 564 DeclGroupRef DGrp = S->getDeclGroup(); 565 for (const auto *D : DGrp) { 566 if (const auto *VD = dyn_cast_or_null<VarDecl>(D)) { 567 const Expr *E = VD->getInit(); 568 569 // Add local variables with trivial type to the variable map 570 QualType T = VD->getType(); 571 if (T.isTrivialType(VD->getASTContext())) { 572 Ctx = VMap->addDefinition(VD, E, Ctx); 573 modifiedCtx = true; 574 } 575 } 576 } 577 if (modifiedCtx) 578 VMap->saveContext(S, Ctx); 579 } 580 581 // Update local variable definitions in variable map 582 void VarMapBuilder::VisitBinaryOperator(BinaryOperator *BO) { 583 if (!BO->isAssignmentOp()) 584 return; 585 586 Expr *LHSExp = BO->getLHS()->IgnoreParenCasts(); 587 588 // Update the variable map and current context. 589 if (DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(LHSExp)) { 590 ValueDecl *VDec = DRE->getDecl(); 591 if (Ctx.lookup(VDec)) { 592 if (BO->getOpcode() == BO_Assign) 593 Ctx = VMap->updateDefinition(VDec, BO->getRHS(), Ctx); 594 else 595 // FIXME -- handle compound assignment operators 596 Ctx = VMap->clearDefinition(VDec, Ctx); 597 VMap->saveContext(BO, Ctx); 598 } 599 } 600 } 601 602 603 // Computes the intersection of two contexts. The intersection is the 604 // set of variables which have the same definition in both contexts; 605 // variables with different definitions are discarded. 606 LocalVariableMap::Context 607 LocalVariableMap::intersectContexts(Context C1, Context C2) { 608 Context Result = C1; 609 for (const auto &P : C1) { 610 const NamedDecl *Dec = P.first; 611 const unsigned *i2 = C2.lookup(Dec); 612 if (!i2) // variable doesn't exist on second path 613 Result = removeDefinition(Dec, Result); 614 else if (*i2 != P.second) // variable exists, but has different definition 615 Result = clearDefinition(Dec, Result); 616 } 617 return Result; 618 } 619 620 // For every variable in C, create a new variable that refers to the 621 // definition in C. Return a new context that contains these new variables. 622 // (We use this for a naive implementation of SSA on loop back-edges.) 623 LocalVariableMap::Context LocalVariableMap::createReferenceContext(Context C) { 624 Context Result = getEmptyContext(); 625 for (const auto &P : C) 626 Result = addReference(P.first, P.second, Result); 627 return Result; 628 } 629 630 // This routine also takes the intersection of C1 and C2, but it does so by 631 // altering the VarDefinitions. C1 must be the result of an earlier call to 632 // createReferenceContext. 633 void LocalVariableMap::intersectBackEdge(Context C1, Context C2) { 634 for (const auto &P : C1) { 635 unsigned i1 = P.second; 636 VarDefinition *VDef = &VarDefinitions[i1]; 637 assert(VDef->isReference()); 638 639 const unsigned *i2 = C2.lookup(P.first); 640 if (!i2 || (*i2 != i1)) 641 VDef->Ref = 0; // Mark this variable as undefined 642 } 643 } 644 645 646 // Traverse the CFG in topological order, so all predecessors of a block 647 // (excluding back-edges) are visited before the block itself. At 648 // each point in the code, we calculate a Context, which holds the set of 649 // variable definitions which are visible at that point in execution. 650 // Visible variables are mapped to their definitions using an array that 651 // contains all definitions. 652 // 653 // At join points in the CFG, the set is computed as the intersection of 654 // the incoming sets along each edge, E.g. 655 // 656 // { Context | VarDefinitions } 657 // int x = 0; { x -> x1 | x1 = 0 } 658 // int y = 0; { x -> x1, y -> y1 | y1 = 0, x1 = 0 } 659 // if (b) x = 1; { x -> x2, y -> y1 | x2 = 1, y1 = 0, ... } 660 // else x = 2; { x -> x3, y -> y1 | x3 = 2, x2 = 1, ... } 661 // ... { y -> y1 (x is unknown) | x3 = 2, x2 = 1, ... } 662 // 663 // This is essentially a simpler and more naive version of the standard SSA 664 // algorithm. Those definitions that remain in the intersection are from blocks 665 // that strictly dominate the current block. We do not bother to insert proper 666 // phi nodes, because they are not used in our analysis; instead, wherever 667 // a phi node would be required, we simply remove that definition from the 668 // context (E.g. x above). 669 // 670 // The initial traversal does not capture back-edges, so those need to be 671 // handled on a separate pass. Whenever the first pass encounters an 672 // incoming back edge, it duplicates the context, creating new definitions 673 // that refer back to the originals. (These correspond to places where SSA 674 // might have to insert a phi node.) On the second pass, these definitions are 675 // set to NULL if the variable has changed on the back-edge (i.e. a phi 676 // node was actually required.) E.g. 677 // 678 // { Context | VarDefinitions } 679 // int x = 0, y = 0; { x -> x1, y -> y1 | y1 = 0, x1 = 0 } 680 // while (b) { x -> x2, y -> y1 | [1st:] x2=x1; [2nd:] x2=NULL; } 681 // x = x+1; { x -> x3, y -> y1 | x3 = x2 + 1, ... } 682 // ... { y -> y1 | x3 = 2, x2 = 1, ... } 683 // 684 void LocalVariableMap::traverseCFG(CFG *CFGraph, 685 const PostOrderCFGView *SortedGraph, 686 std::vector<CFGBlockInfo> &BlockInfo) { 687 PostOrderCFGView::CFGBlockSet VisitedBlocks(CFGraph); 688 689 CtxIndices.resize(CFGraph->getNumBlockIDs()); 690 691 for (const auto *CurrBlock : *SortedGraph) { 692 int CurrBlockID = CurrBlock->getBlockID(); 693 CFGBlockInfo *CurrBlockInfo = &BlockInfo[CurrBlockID]; 694 695 VisitedBlocks.insert(CurrBlock); 696 697 // Calculate the entry context for the current block 698 bool HasBackEdges = false; 699 bool CtxInit = true; 700 for (CFGBlock::const_pred_iterator PI = CurrBlock->pred_begin(), 701 PE = CurrBlock->pred_end(); PI != PE; ++PI) { 702 // if *PI -> CurrBlock is a back edge, so skip it 703 if (*PI == nullptr || !VisitedBlocks.alreadySet(*PI)) { 704 HasBackEdges = true; 705 continue; 706 } 707 708 int PrevBlockID = (*PI)->getBlockID(); 709 CFGBlockInfo *PrevBlockInfo = &BlockInfo[PrevBlockID]; 710 711 if (CtxInit) { 712 CurrBlockInfo->EntryContext = PrevBlockInfo->ExitContext; 713 CtxInit = false; 714 } 715 else { 716 CurrBlockInfo->EntryContext = 717 intersectContexts(CurrBlockInfo->EntryContext, 718 PrevBlockInfo->ExitContext); 719 } 720 } 721 722 // Duplicate the context if we have back-edges, so we can call 723 // intersectBackEdges later. 724 if (HasBackEdges) 725 CurrBlockInfo->EntryContext = 726 createReferenceContext(CurrBlockInfo->EntryContext); 727 728 // Create a starting context index for the current block 729 saveContext(nullptr, CurrBlockInfo->EntryContext); 730 CurrBlockInfo->EntryIndex = getContextIndex(); 731 732 // Visit all the statements in the basic block. 733 VarMapBuilder VMapBuilder(this, CurrBlockInfo->EntryContext); 734 for (CFGBlock::const_iterator BI = CurrBlock->begin(), 735 BE = CurrBlock->end(); BI != BE; ++BI) { 736 switch (BI->getKind()) { 737 case CFGElement::Statement: { 738 CFGStmt CS = BI->castAs<CFGStmt>(); 739 VMapBuilder.Visit(const_cast<Stmt*>(CS.getStmt())); 740 break; 741 } 742 default: 743 break; 744 } 745 } 746 CurrBlockInfo->ExitContext = VMapBuilder.Ctx; 747 748 // Mark variables on back edges as "unknown" if they've been changed. 749 for (CFGBlock::const_succ_iterator SI = CurrBlock->succ_begin(), 750 SE = CurrBlock->succ_end(); SI != SE; ++SI) { 751 // if CurrBlock -> *SI is *not* a back edge 752 if (*SI == nullptr || !VisitedBlocks.alreadySet(*SI)) 753 continue; 754 755 CFGBlock *FirstLoopBlock = *SI; 756 Context LoopBegin = BlockInfo[FirstLoopBlock->getBlockID()].EntryContext; 757 Context LoopEnd = CurrBlockInfo->ExitContext; 758 intersectBackEdge(LoopBegin, LoopEnd); 759 } 760 } 761 762 // Put an extra entry at the end of the indexed context array 763 unsigned exitID = CFGraph->getExit().getBlockID(); 764 saveContext(nullptr, BlockInfo[exitID].ExitContext); 765 } 766 767 /// Find the appropriate source locations to use when producing diagnostics for 768 /// each block in the CFG. 769 static void findBlockLocations(CFG *CFGraph, 770 const PostOrderCFGView *SortedGraph, 771 std::vector<CFGBlockInfo> &BlockInfo) { 772 for (const auto *CurrBlock : *SortedGraph) { 773 CFGBlockInfo *CurrBlockInfo = &BlockInfo[CurrBlock->getBlockID()]; 774 775 // Find the source location of the last statement in the block, if the 776 // block is not empty. 777 if (const Stmt *S = CurrBlock->getTerminator()) { 778 CurrBlockInfo->EntryLoc = CurrBlockInfo->ExitLoc = S->getLocStart(); 779 } else { 780 for (CFGBlock::const_reverse_iterator BI = CurrBlock->rbegin(), 781 BE = CurrBlock->rend(); BI != BE; ++BI) { 782 // FIXME: Handle other CFGElement kinds. 783 if (Optional<CFGStmt> CS = BI->getAs<CFGStmt>()) { 784 CurrBlockInfo->ExitLoc = CS->getStmt()->getLocStart(); 785 break; 786 } 787 } 788 } 789 790 if (!CurrBlockInfo->ExitLoc.isInvalid()) { 791 // This block contains at least one statement. Find the source location 792 // of the first statement in the block. 793 for (CFGBlock::const_iterator BI = CurrBlock->begin(), 794 BE = CurrBlock->end(); BI != BE; ++BI) { 795 // FIXME: Handle other CFGElement kinds. 796 if (Optional<CFGStmt> CS = BI->getAs<CFGStmt>()) { 797 CurrBlockInfo->EntryLoc = CS->getStmt()->getLocStart(); 798 break; 799 } 800 } 801 } else if (CurrBlock->pred_size() == 1 && *CurrBlock->pred_begin() && 802 CurrBlock != &CFGraph->getExit()) { 803 // The block is empty, and has a single predecessor. Use its exit 804 // location. 805 CurrBlockInfo->EntryLoc = CurrBlockInfo->ExitLoc = 806 BlockInfo[(*CurrBlock->pred_begin())->getBlockID()].ExitLoc; 807 } 808 } 809 } 810 811 class LockableFactEntry : public FactEntry { 812 private: 813 bool Managed; ///< managed by ScopedLockable object 814 815 public: 816 LockableFactEntry(const CapabilityExpr &CE, LockKind LK, SourceLocation Loc, 817 bool Mng = false, bool Asrt = false) 818 : FactEntry(CE, LK, Loc, Asrt), Managed(Mng) {} 819 820 void 821 handleRemovalFromIntersection(const FactSet &FSet, FactManager &FactMan, 822 SourceLocation JoinLoc, LockErrorKind LEK, 823 ThreadSafetyHandler &Handler) const override { 824 if (!Managed && !asserted() && !negative() && !isUniversal()) { 825 Handler.handleMutexHeldEndOfScope("mutex", toString(), loc(), JoinLoc, 826 LEK); 827 } 828 } 829 830 void handleUnlock(FactSet &FSet, FactManager &FactMan, 831 const CapabilityExpr &Cp, SourceLocation UnlockLoc, 832 bool FullyRemove, ThreadSafetyHandler &Handler, 833 StringRef DiagKind) const override { 834 FSet.removeLock(FactMan, Cp); 835 if (!Cp.negative()) { 836 FSet.addLock(FactMan, llvm::make_unique<LockableFactEntry>( 837 !Cp, LK_Exclusive, UnlockLoc)); 838 } 839 } 840 }; 841 842 class ScopedLockableFactEntry : public FactEntry { 843 private: 844 SmallVector<const til::SExpr *, 4> UnderlyingMutexes; 845 846 public: 847 ScopedLockableFactEntry(const CapabilityExpr &CE, SourceLocation Loc, 848 const CapExprSet &Excl, const CapExprSet &Shrd) 849 : FactEntry(CE, LK_Exclusive, Loc, false) { 850 for (const auto &M : Excl) 851 UnderlyingMutexes.push_back(M.sexpr()); 852 for (const auto &M : Shrd) 853 UnderlyingMutexes.push_back(M.sexpr()); 854 } 855 856 void 857 handleRemovalFromIntersection(const FactSet &FSet, FactManager &FactMan, 858 SourceLocation JoinLoc, LockErrorKind LEK, 859 ThreadSafetyHandler &Handler) const override { 860 for (const til::SExpr *UnderlyingMutex : UnderlyingMutexes) { 861 if (FSet.findLock(FactMan, CapabilityExpr(UnderlyingMutex, false))) { 862 // If this scoped lock manages another mutex, and if the underlying 863 // mutex is still held, then warn about the underlying mutex. 864 Handler.handleMutexHeldEndOfScope( 865 "mutex", sx::toString(UnderlyingMutex), loc(), JoinLoc, LEK); 866 } 867 } 868 } 869 870 void handleUnlock(FactSet &FSet, FactManager &FactMan, 871 const CapabilityExpr &Cp, SourceLocation UnlockLoc, 872 bool FullyRemove, ThreadSafetyHandler &Handler, 873 StringRef DiagKind) const override { 874 assert(!Cp.negative() && "Managing object cannot be negative."); 875 for (const til::SExpr *UnderlyingMutex : UnderlyingMutexes) { 876 CapabilityExpr UnderCp(UnderlyingMutex, false); 877 auto UnderEntry = llvm::make_unique<LockableFactEntry>( 878 !UnderCp, LK_Exclusive, UnlockLoc); 879 880 if (FullyRemove) { 881 // We're destroying the managing object. 882 // Remove the underlying mutex if it exists; but don't warn. 883 if (FSet.findLock(FactMan, UnderCp)) { 884 FSet.removeLock(FactMan, UnderCp); 885 FSet.addLock(FactMan, std::move(UnderEntry)); 886 } 887 } else { 888 // We're releasing the underlying mutex, but not destroying the 889 // managing object. Warn on dual release. 890 if (!FSet.findLock(FactMan, UnderCp)) { 891 Handler.handleUnmatchedUnlock(DiagKind, UnderCp.toString(), 892 UnlockLoc); 893 } 894 FSet.removeLock(FactMan, UnderCp); 895 FSet.addLock(FactMan, std::move(UnderEntry)); 896 } 897 } 898 if (FullyRemove) 899 FSet.removeLock(FactMan, Cp); 900 } 901 }; 902 903 /// \brief Class which implements the core thread safety analysis routines. 904 class ThreadSafetyAnalyzer { 905 friend class BuildLockset; 906 friend class threadSafety::BeforeSet; 907 908 llvm::BumpPtrAllocator Bpa; 909 threadSafety::til::MemRegionRef Arena; 910 threadSafety::SExprBuilder SxBuilder; 911 912 ThreadSafetyHandler &Handler; 913 const CXXMethodDecl *CurrentMethod; 914 LocalVariableMap LocalVarMap; 915 FactManager FactMan; 916 std::vector<CFGBlockInfo> BlockInfo; 917 918 BeforeSet* GlobalBeforeSet; 919 920 public: 921 ThreadSafetyAnalyzer(ThreadSafetyHandler &H, BeforeSet* Bset) 922 : Arena(&Bpa), SxBuilder(Arena), Handler(H), GlobalBeforeSet(Bset) {} 923 924 bool inCurrentScope(const CapabilityExpr &CapE); 925 926 void addLock(FactSet &FSet, std::unique_ptr<FactEntry> Entry, 927 StringRef DiagKind, bool ReqAttr = false); 928 void removeLock(FactSet &FSet, const CapabilityExpr &CapE, 929 SourceLocation UnlockLoc, bool FullyRemove, LockKind Kind, 930 StringRef DiagKind); 931 932 template <typename AttrType> 933 void getMutexIDs(CapExprSet &Mtxs, AttrType *Attr, Expr *Exp, 934 const NamedDecl *D, VarDecl *SelfDecl = nullptr); 935 936 template <class AttrType> 937 void getMutexIDs(CapExprSet &Mtxs, AttrType *Attr, Expr *Exp, 938 const NamedDecl *D, 939 const CFGBlock *PredBlock, const CFGBlock *CurrBlock, 940 Expr *BrE, bool Neg); 941 942 const CallExpr* getTrylockCallExpr(const Stmt *Cond, LocalVarContext C, 943 bool &Negate); 944 945 void getEdgeLockset(FactSet &Result, const FactSet &ExitSet, 946 const CFGBlock* PredBlock, 947 const CFGBlock *CurrBlock); 948 949 void intersectAndWarn(FactSet &FSet1, const FactSet &FSet2, 950 SourceLocation JoinLoc, 951 LockErrorKind LEK1, LockErrorKind LEK2, 952 bool Modify=true); 953 954 void intersectAndWarn(FactSet &FSet1, const FactSet &FSet2, 955 SourceLocation JoinLoc, LockErrorKind LEK1, 956 bool Modify=true) { 957 intersectAndWarn(FSet1, FSet2, JoinLoc, LEK1, LEK1, Modify); 958 } 959 960 void runAnalysis(AnalysisDeclContext &AC); 961 }; 962 } // namespace 963 964 /// Process acquired_before and acquired_after attributes on Vd. 965 BeforeSet::BeforeInfo* BeforeSet::insertAttrExprs(const ValueDecl* Vd, 966 ThreadSafetyAnalyzer& Analyzer) { 967 // Create a new entry for Vd. 968 auto& Entry = BMap.FindAndConstruct(Vd); 969 BeforeInfo* Info = &Entry.second; 970 BeforeVect* Bv = nullptr; 971 972 for (Attr* At : Vd->attrs()) { 973 switch (At->getKind()) { 974 case attr::AcquiredBefore: { 975 auto *A = cast<AcquiredBeforeAttr>(At); 976 977 // Create a new BeforeVect for Vd if necessary. 978 if (!Bv) { 979 Bv = new BeforeVect; 980 Info->Vect.reset(Bv); 981 } 982 // Read exprs from the attribute, and add them to BeforeVect. 983 for (const auto *Arg : A->args()) { 984 CapabilityExpr Cp = 985 Analyzer.SxBuilder.translateAttrExpr(Arg, nullptr); 986 if (const ValueDecl *Cpvd = Cp.valueDecl()) { 987 Bv->push_back(Cpvd); 988 auto It = BMap.find(Cpvd); 989 if (It == BMap.end()) 990 insertAttrExprs(Cpvd, Analyzer); 991 } 992 } 993 break; 994 } 995 case attr::AcquiredAfter: { 996 auto *A = cast<AcquiredAfterAttr>(At); 997 998 // Read exprs from the attribute, and add them to BeforeVect. 999 for (const auto *Arg : A->args()) { 1000 CapabilityExpr Cp = 1001 Analyzer.SxBuilder.translateAttrExpr(Arg, nullptr); 1002 if (const ValueDecl *ArgVd = Cp.valueDecl()) { 1003 // Get entry for mutex listed in attribute 1004 BeforeInfo* ArgInfo; 1005 auto It = BMap.find(ArgVd); 1006 if (It == BMap.end()) 1007 ArgInfo = insertAttrExprs(ArgVd, Analyzer); 1008 else 1009 ArgInfo = &It->second; 1010 1011 // Create a new BeforeVect if necessary. 1012 BeforeVect* ArgBv = ArgInfo->Vect.get(); 1013 if (!ArgBv) { 1014 ArgBv = new BeforeVect; 1015 ArgInfo->Vect.reset(ArgBv); 1016 } 1017 ArgBv->push_back(Vd); 1018 } 1019 } 1020 break; 1021 } 1022 default: 1023 break; 1024 } 1025 } 1026 1027 return Info; 1028 } 1029 1030 1031 /// Return true if any mutexes in FSet are in the acquired_before set of Vd. 1032 void BeforeSet::checkBeforeAfter(const ValueDecl* StartVd, 1033 const FactSet& FSet, 1034 ThreadSafetyAnalyzer& Analyzer, 1035 SourceLocation Loc, StringRef CapKind) { 1036 SmallVector<BeforeInfo*, 8> InfoVect; 1037 1038 // Do a depth-first traversal of Vd. 1039 // Return true if there are cycles. 1040 std::function<bool (const ValueDecl*)> traverse = [&](const ValueDecl* Vd) { 1041 if (!Vd) 1042 return false; 1043 1044 BeforeSet::BeforeInfo* Info; 1045 auto It = BMap.find(Vd); 1046 if (It == BMap.end()) 1047 Info = insertAttrExprs(Vd, Analyzer); 1048 else 1049 Info = &It->second; 1050 1051 if (Info->Visited == 1) 1052 return true; 1053 1054 if (Info->Visited == 2) 1055 return false; 1056 1057 BeforeVect* Bv = Info->Vect.get(); 1058 if (!Bv) 1059 return false; 1060 1061 InfoVect.push_back(Info); 1062 Info->Visited = 1; 1063 for (auto *Vdb : *Bv) { 1064 // Exclude mutexes in our immediate before set. 1065 if (FSet.containsMutexDecl(Analyzer.FactMan, Vdb)) { 1066 StringRef L1 = StartVd->getName(); 1067 StringRef L2 = Vdb->getName(); 1068 Analyzer.Handler.handleLockAcquiredBefore(CapKind, L1, L2, Loc); 1069 } 1070 // Transitively search other before sets, and warn on cycles. 1071 if (traverse(Vdb)) { 1072 if (CycMap.find(Vd) == CycMap.end()) { 1073 CycMap.insert(std::make_pair(Vd, true)); 1074 StringRef L1 = Vd->getName(); 1075 Analyzer.Handler.handleBeforeAfterCycle(L1, Vd->getLocation()); 1076 } 1077 } 1078 } 1079 Info->Visited = 2; 1080 return false; 1081 }; 1082 1083 traverse(StartVd); 1084 1085 for (auto* Info : InfoVect) 1086 Info->Visited = 0; 1087 } 1088 1089 1090 1091 /// \brief Gets the value decl pointer from DeclRefExprs or MemberExprs. 1092 static const ValueDecl *getValueDecl(const Expr *Exp) { 1093 if (const auto *CE = dyn_cast<ImplicitCastExpr>(Exp)) 1094 return getValueDecl(CE->getSubExpr()); 1095 1096 if (const auto *DR = dyn_cast<DeclRefExpr>(Exp)) 1097 return DR->getDecl(); 1098 1099 if (const auto *ME = dyn_cast<MemberExpr>(Exp)) 1100 return ME->getMemberDecl(); 1101 1102 return nullptr; 1103 } 1104 1105 namespace { 1106 template <typename Ty> 1107 class has_arg_iterator_range { 1108 typedef char yes[1]; 1109 typedef char no[2]; 1110 1111 template <typename Inner> 1112 static yes& test(Inner *I, decltype(I->args()) * = nullptr); 1113 1114 template <typename> 1115 static no& test(...); 1116 1117 public: 1118 static const bool value = sizeof(test<Ty>(nullptr)) == sizeof(yes); 1119 }; 1120 } // namespace 1121 1122 static StringRef ClassifyDiagnostic(const CapabilityAttr *A) { 1123 return A->getName(); 1124 } 1125 1126 static StringRef ClassifyDiagnostic(QualType VDT) { 1127 // We need to look at the declaration of the type of the value to determine 1128 // which it is. The type should either be a record or a typedef, or a pointer 1129 // or reference thereof. 1130 if (const auto *RT = VDT->getAs<RecordType>()) { 1131 if (const auto *RD = RT->getDecl()) 1132 if (const auto *CA = RD->getAttr<CapabilityAttr>()) 1133 return ClassifyDiagnostic(CA); 1134 } else if (const auto *TT = VDT->getAs<TypedefType>()) { 1135 if (const auto *TD = TT->getDecl()) 1136 if (const auto *CA = TD->getAttr<CapabilityAttr>()) 1137 return ClassifyDiagnostic(CA); 1138 } else if (VDT->isPointerType() || VDT->isReferenceType()) 1139 return ClassifyDiagnostic(VDT->getPointeeType()); 1140 1141 return "mutex"; 1142 } 1143 1144 static StringRef ClassifyDiagnostic(const ValueDecl *VD) { 1145 assert(VD && "No ValueDecl passed"); 1146 1147 // The ValueDecl is the declaration of a mutex or role (hopefully). 1148 return ClassifyDiagnostic(VD->getType()); 1149 } 1150 1151 template <typename AttrTy> 1152 static typename std::enable_if<!has_arg_iterator_range<AttrTy>::value, 1153 StringRef>::type 1154 ClassifyDiagnostic(const AttrTy *A) { 1155 if (const ValueDecl *VD = getValueDecl(A->getArg())) 1156 return ClassifyDiagnostic(VD); 1157 return "mutex"; 1158 } 1159 1160 template <typename AttrTy> 1161 static typename std::enable_if<has_arg_iterator_range<AttrTy>::value, 1162 StringRef>::type 1163 ClassifyDiagnostic(const AttrTy *A) { 1164 for (const auto *Arg : A->args()) { 1165 if (const ValueDecl *VD = getValueDecl(Arg)) 1166 return ClassifyDiagnostic(VD); 1167 } 1168 return "mutex"; 1169 } 1170 1171 1172 inline bool ThreadSafetyAnalyzer::inCurrentScope(const CapabilityExpr &CapE) { 1173 if (!CurrentMethod) 1174 return false; 1175 if (auto *P = dyn_cast_or_null<til::Project>(CapE.sexpr())) { 1176 auto *VD = P->clangDecl(); 1177 if (VD) 1178 return VD->getDeclContext() == CurrentMethod->getDeclContext(); 1179 } 1180 return false; 1181 } 1182 1183 1184 /// \brief Add a new lock to the lockset, warning if the lock is already there. 1185 /// \param ReqAttr -- true if this is part of an initial Requires attribute. 1186 void ThreadSafetyAnalyzer::addLock(FactSet &FSet, 1187 std::unique_ptr<FactEntry> Entry, 1188 StringRef DiagKind, bool ReqAttr) { 1189 if (Entry->shouldIgnore()) 1190 return; 1191 1192 if (!ReqAttr && !Entry->negative()) { 1193 // look for the negative capability, and remove it from the fact set. 1194 CapabilityExpr NegC = !*Entry; 1195 FactEntry *Nen = FSet.findLock(FactMan, NegC); 1196 if (Nen) { 1197 FSet.removeLock(FactMan, NegC); 1198 } 1199 else { 1200 if (inCurrentScope(*Entry) && !Entry->asserted()) 1201 Handler.handleNegativeNotHeld(DiagKind, Entry->toString(), 1202 NegC.toString(), Entry->loc()); 1203 } 1204 } 1205 1206 // Check before/after constraints 1207 if (Handler.issueBetaWarnings() && 1208 !Entry->asserted() && !Entry->declared()) { 1209 GlobalBeforeSet->checkBeforeAfter(Entry->valueDecl(), FSet, *this, 1210 Entry->loc(), DiagKind); 1211 } 1212 1213 // FIXME: Don't always warn when we have support for reentrant locks. 1214 if (FSet.findLock(FactMan, *Entry)) { 1215 if (!Entry->asserted()) 1216 Handler.handleDoubleLock(DiagKind, Entry->toString(), Entry->loc()); 1217 } else { 1218 FSet.addLock(FactMan, std::move(Entry)); 1219 } 1220 } 1221 1222 1223 /// \brief Remove a lock from the lockset, warning if the lock is not there. 1224 /// \param UnlockLoc The source location of the unlock (only used in error msg) 1225 void ThreadSafetyAnalyzer::removeLock(FactSet &FSet, const CapabilityExpr &Cp, 1226 SourceLocation UnlockLoc, 1227 bool FullyRemove, LockKind ReceivedKind, 1228 StringRef DiagKind) { 1229 if (Cp.shouldIgnore()) 1230 return; 1231 1232 const FactEntry *LDat = FSet.findLock(FactMan, Cp); 1233 if (!LDat) { 1234 Handler.handleUnmatchedUnlock(DiagKind, Cp.toString(), UnlockLoc); 1235 return; 1236 } 1237 1238 // Generic lock removal doesn't care about lock kind mismatches, but 1239 // otherwise diagnose when the lock kinds are mismatched. 1240 if (ReceivedKind != LK_Generic && LDat->kind() != ReceivedKind) { 1241 Handler.handleIncorrectUnlockKind(DiagKind, Cp.toString(), 1242 LDat->kind(), ReceivedKind, UnlockLoc); 1243 } 1244 1245 LDat->handleUnlock(FSet, FactMan, Cp, UnlockLoc, FullyRemove, Handler, 1246 DiagKind); 1247 } 1248 1249 1250 /// \brief Extract the list of mutexIDs from the attribute on an expression, 1251 /// and push them onto Mtxs, discarding any duplicates. 1252 template <typename AttrType> 1253 void ThreadSafetyAnalyzer::getMutexIDs(CapExprSet &Mtxs, AttrType *Attr, 1254 Expr *Exp, const NamedDecl *D, 1255 VarDecl *SelfDecl) { 1256 if (Attr->args_size() == 0) { 1257 // The mutex held is the "this" object. 1258 CapabilityExpr Cp = SxBuilder.translateAttrExpr(nullptr, D, Exp, SelfDecl); 1259 if (Cp.isInvalid()) { 1260 warnInvalidLock(Handler, nullptr, D, Exp, ClassifyDiagnostic(Attr)); 1261 return; 1262 } 1263 //else 1264 if (!Cp.shouldIgnore()) 1265 Mtxs.push_back_nodup(Cp); 1266 return; 1267 } 1268 1269 for (const auto *Arg : Attr->args()) { 1270 CapabilityExpr Cp = SxBuilder.translateAttrExpr(Arg, D, Exp, SelfDecl); 1271 if (Cp.isInvalid()) { 1272 warnInvalidLock(Handler, nullptr, D, Exp, ClassifyDiagnostic(Attr)); 1273 continue; 1274 } 1275 //else 1276 if (!Cp.shouldIgnore()) 1277 Mtxs.push_back_nodup(Cp); 1278 } 1279 } 1280 1281 1282 /// \brief Extract the list of mutexIDs from a trylock attribute. If the 1283 /// trylock applies to the given edge, then push them onto Mtxs, discarding 1284 /// any duplicates. 1285 template <class AttrType> 1286 void ThreadSafetyAnalyzer::getMutexIDs(CapExprSet &Mtxs, AttrType *Attr, 1287 Expr *Exp, const NamedDecl *D, 1288 const CFGBlock *PredBlock, 1289 const CFGBlock *CurrBlock, 1290 Expr *BrE, bool Neg) { 1291 // Find out which branch has the lock 1292 bool branch = false; 1293 if (CXXBoolLiteralExpr *BLE = dyn_cast_or_null<CXXBoolLiteralExpr>(BrE)) 1294 branch = BLE->getValue(); 1295 else if (IntegerLiteral *ILE = dyn_cast_or_null<IntegerLiteral>(BrE)) 1296 branch = ILE->getValue().getBoolValue(); 1297 1298 int branchnum = branch ? 0 : 1; 1299 if (Neg) 1300 branchnum = !branchnum; 1301 1302 // If we've taken the trylock branch, then add the lock 1303 int i = 0; 1304 for (CFGBlock::const_succ_iterator SI = PredBlock->succ_begin(), 1305 SE = PredBlock->succ_end(); SI != SE && i < 2; ++SI, ++i) { 1306 if (*SI == CurrBlock && i == branchnum) 1307 getMutexIDs(Mtxs, Attr, Exp, D); 1308 } 1309 } 1310 1311 static bool getStaticBooleanValue(Expr *E, bool &TCond) { 1312 if (isa<CXXNullPtrLiteralExpr>(E) || isa<GNUNullExpr>(E)) { 1313 TCond = false; 1314 return true; 1315 } else if (CXXBoolLiteralExpr *BLE = dyn_cast<CXXBoolLiteralExpr>(E)) { 1316 TCond = BLE->getValue(); 1317 return true; 1318 } else if (IntegerLiteral *ILE = dyn_cast<IntegerLiteral>(E)) { 1319 TCond = ILE->getValue().getBoolValue(); 1320 return true; 1321 } else if (ImplicitCastExpr *CE = dyn_cast<ImplicitCastExpr>(E)) { 1322 return getStaticBooleanValue(CE->getSubExpr(), TCond); 1323 } 1324 return false; 1325 } 1326 1327 1328 // If Cond can be traced back to a function call, return the call expression. 1329 // The negate variable should be called with false, and will be set to true 1330 // if the function call is negated, e.g. if (!mu.tryLock(...)) 1331 const CallExpr* ThreadSafetyAnalyzer::getTrylockCallExpr(const Stmt *Cond, 1332 LocalVarContext C, 1333 bool &Negate) { 1334 if (!Cond) 1335 return nullptr; 1336 1337 if (const CallExpr *CallExp = dyn_cast<CallExpr>(Cond)) { 1338 return CallExp; 1339 } 1340 else if (const ParenExpr *PE = dyn_cast<ParenExpr>(Cond)) { 1341 return getTrylockCallExpr(PE->getSubExpr(), C, Negate); 1342 } 1343 else if (const ImplicitCastExpr *CE = dyn_cast<ImplicitCastExpr>(Cond)) { 1344 return getTrylockCallExpr(CE->getSubExpr(), C, Negate); 1345 } 1346 else if (const ExprWithCleanups* EWC = dyn_cast<ExprWithCleanups>(Cond)) { 1347 return getTrylockCallExpr(EWC->getSubExpr(), C, Negate); 1348 } 1349 else if (const DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(Cond)) { 1350 const Expr *E = LocalVarMap.lookupExpr(DRE->getDecl(), C); 1351 return getTrylockCallExpr(E, C, Negate); 1352 } 1353 else if (const UnaryOperator *UOP = dyn_cast<UnaryOperator>(Cond)) { 1354 if (UOP->getOpcode() == UO_LNot) { 1355 Negate = !Negate; 1356 return getTrylockCallExpr(UOP->getSubExpr(), C, Negate); 1357 } 1358 return nullptr; 1359 } 1360 else if (const BinaryOperator *BOP = dyn_cast<BinaryOperator>(Cond)) { 1361 if (BOP->getOpcode() == BO_EQ || BOP->getOpcode() == BO_NE) { 1362 if (BOP->getOpcode() == BO_NE) 1363 Negate = !Negate; 1364 1365 bool TCond = false; 1366 if (getStaticBooleanValue(BOP->getRHS(), TCond)) { 1367 if (!TCond) Negate = !Negate; 1368 return getTrylockCallExpr(BOP->getLHS(), C, Negate); 1369 } 1370 TCond = false; 1371 if (getStaticBooleanValue(BOP->getLHS(), TCond)) { 1372 if (!TCond) Negate = !Negate; 1373 return getTrylockCallExpr(BOP->getRHS(), C, Negate); 1374 } 1375 return nullptr; 1376 } 1377 if (BOP->getOpcode() == BO_LAnd) { 1378 // LHS must have been evaluated in a different block. 1379 return getTrylockCallExpr(BOP->getRHS(), C, Negate); 1380 } 1381 if (BOP->getOpcode() == BO_LOr) { 1382 return getTrylockCallExpr(BOP->getRHS(), C, Negate); 1383 } 1384 return nullptr; 1385 } 1386 return nullptr; 1387 } 1388 1389 1390 /// \brief Find the lockset that holds on the edge between PredBlock 1391 /// and CurrBlock. The edge set is the exit set of PredBlock (passed 1392 /// as the ExitSet parameter) plus any trylocks, which are conditionally held. 1393 void ThreadSafetyAnalyzer::getEdgeLockset(FactSet& Result, 1394 const FactSet &ExitSet, 1395 const CFGBlock *PredBlock, 1396 const CFGBlock *CurrBlock) { 1397 Result = ExitSet; 1398 1399 const Stmt *Cond = PredBlock->getTerminatorCondition(); 1400 if (!Cond) 1401 return; 1402 1403 bool Negate = false; 1404 const CFGBlockInfo *PredBlockInfo = &BlockInfo[PredBlock->getBlockID()]; 1405 const LocalVarContext &LVarCtx = PredBlockInfo->ExitContext; 1406 StringRef CapDiagKind = "mutex"; 1407 1408 CallExpr *Exp = 1409 const_cast<CallExpr*>(getTrylockCallExpr(Cond, LVarCtx, Negate)); 1410 if (!Exp) 1411 return; 1412 1413 NamedDecl *FunDecl = dyn_cast_or_null<NamedDecl>(Exp->getCalleeDecl()); 1414 if(!FunDecl || !FunDecl->hasAttrs()) 1415 return; 1416 1417 CapExprSet ExclusiveLocksToAdd; 1418 CapExprSet SharedLocksToAdd; 1419 1420 // If the condition is a call to a Trylock function, then grab the attributes 1421 for (auto *Attr : FunDecl->attrs()) { 1422 switch (Attr->getKind()) { 1423 case attr::ExclusiveTrylockFunction: { 1424 ExclusiveTrylockFunctionAttr *A = 1425 cast<ExclusiveTrylockFunctionAttr>(Attr); 1426 getMutexIDs(ExclusiveLocksToAdd, A, Exp, FunDecl, 1427 PredBlock, CurrBlock, A->getSuccessValue(), Negate); 1428 CapDiagKind = ClassifyDiagnostic(A); 1429 break; 1430 } 1431 case attr::SharedTrylockFunction: { 1432 SharedTrylockFunctionAttr *A = 1433 cast<SharedTrylockFunctionAttr>(Attr); 1434 getMutexIDs(SharedLocksToAdd, A, Exp, FunDecl, 1435 PredBlock, CurrBlock, A->getSuccessValue(), Negate); 1436 CapDiagKind = ClassifyDiagnostic(A); 1437 break; 1438 } 1439 default: 1440 break; 1441 } 1442 } 1443 1444 // Add and remove locks. 1445 SourceLocation Loc = Exp->getExprLoc(); 1446 for (const auto &ExclusiveLockToAdd : ExclusiveLocksToAdd) 1447 addLock(Result, llvm::make_unique<LockableFactEntry>(ExclusiveLockToAdd, 1448 LK_Exclusive, Loc), 1449 CapDiagKind); 1450 for (const auto &SharedLockToAdd : SharedLocksToAdd) 1451 addLock(Result, llvm::make_unique<LockableFactEntry>(SharedLockToAdd, 1452 LK_Shared, Loc), 1453 CapDiagKind); 1454 } 1455 1456 namespace { 1457 /// \brief We use this class to visit different types of expressions in 1458 /// CFGBlocks, and build up the lockset. 1459 /// An expression may cause us to add or remove locks from the lockset, or else 1460 /// output error messages related to missing locks. 1461 /// FIXME: In future, we may be able to not inherit from a visitor. 1462 class BuildLockset : public StmtVisitor<BuildLockset> { 1463 friend class ThreadSafetyAnalyzer; 1464 1465 ThreadSafetyAnalyzer *Analyzer; 1466 FactSet FSet; 1467 LocalVariableMap::Context LVarCtx; 1468 unsigned CtxIndex; 1469 1470 // helper functions 1471 void warnIfMutexNotHeld(const NamedDecl *D, const Expr *Exp, AccessKind AK, 1472 Expr *MutexExp, ProtectedOperationKind POK, 1473 StringRef DiagKind, SourceLocation Loc); 1474 void warnIfMutexHeld(const NamedDecl *D, const Expr *Exp, Expr *MutexExp, 1475 StringRef DiagKind); 1476 1477 void checkAccess(const Expr *Exp, AccessKind AK, 1478 ProtectedOperationKind POK = POK_VarAccess); 1479 void checkPtAccess(const Expr *Exp, AccessKind AK, 1480 ProtectedOperationKind POK = POK_VarAccess); 1481 1482 void handleCall(Expr *Exp, const NamedDecl *D, VarDecl *VD = nullptr); 1483 1484 public: 1485 BuildLockset(ThreadSafetyAnalyzer *Anlzr, CFGBlockInfo &Info) 1486 : StmtVisitor<BuildLockset>(), 1487 Analyzer(Anlzr), 1488 FSet(Info.EntrySet), 1489 LVarCtx(Info.EntryContext), 1490 CtxIndex(Info.EntryIndex) 1491 {} 1492 1493 void VisitUnaryOperator(UnaryOperator *UO); 1494 void VisitBinaryOperator(BinaryOperator *BO); 1495 void VisitCastExpr(CastExpr *CE); 1496 void VisitCallExpr(CallExpr *Exp); 1497 void VisitCXXConstructExpr(CXXConstructExpr *Exp); 1498 void VisitDeclStmt(DeclStmt *S); 1499 }; 1500 } // namespace 1501 1502 /// \brief Warn if the LSet does not contain a lock sufficient to protect access 1503 /// of at least the passed in AccessKind. 1504 void BuildLockset::warnIfMutexNotHeld(const NamedDecl *D, const Expr *Exp, 1505 AccessKind AK, Expr *MutexExp, 1506 ProtectedOperationKind POK, 1507 StringRef DiagKind, SourceLocation Loc) { 1508 LockKind LK = getLockKindFromAccessKind(AK); 1509 1510 CapabilityExpr Cp = Analyzer->SxBuilder.translateAttrExpr(MutexExp, D, Exp); 1511 if (Cp.isInvalid()) { 1512 warnInvalidLock(Analyzer->Handler, MutexExp, D, Exp, DiagKind); 1513 return; 1514 } else if (Cp.shouldIgnore()) { 1515 return; 1516 } 1517 1518 if (Cp.negative()) { 1519 // Negative capabilities act like locks excluded 1520 FactEntry *LDat = FSet.findLock(Analyzer->FactMan, !Cp); 1521 if (LDat) { 1522 Analyzer->Handler.handleFunExcludesLock( 1523 DiagKind, D->getNameAsString(), (!Cp).toString(), Loc); 1524 return; 1525 } 1526 1527 // If this does not refer to a negative capability in the same class, 1528 // then stop here. 1529 if (!Analyzer->inCurrentScope(Cp)) 1530 return; 1531 1532 // Otherwise the negative requirement must be propagated to the caller. 1533 LDat = FSet.findLock(Analyzer->FactMan, Cp); 1534 if (!LDat) { 1535 Analyzer->Handler.handleMutexNotHeld("", D, POK, Cp.toString(), 1536 LK_Shared, Loc); 1537 } 1538 return; 1539 } 1540 1541 FactEntry* LDat = FSet.findLockUniv(Analyzer->FactMan, Cp); 1542 bool NoError = true; 1543 if (!LDat) { 1544 // No exact match found. Look for a partial match. 1545 LDat = FSet.findPartialMatch(Analyzer->FactMan, Cp); 1546 if (LDat) { 1547 // Warn that there's no precise match. 1548 std::string PartMatchStr = LDat->toString(); 1549 StringRef PartMatchName(PartMatchStr); 1550 Analyzer->Handler.handleMutexNotHeld(DiagKind, D, POK, Cp.toString(), 1551 LK, Loc, &PartMatchName); 1552 } else { 1553 // Warn that there's no match at all. 1554 Analyzer->Handler.handleMutexNotHeld(DiagKind, D, POK, Cp.toString(), 1555 LK, Loc); 1556 } 1557 NoError = false; 1558 } 1559 // Make sure the mutex we found is the right kind. 1560 if (NoError && LDat && !LDat->isAtLeast(LK)) { 1561 Analyzer->Handler.handleMutexNotHeld(DiagKind, D, POK, Cp.toString(), 1562 LK, Loc); 1563 } 1564 } 1565 1566 /// \brief Warn if the LSet contains the given lock. 1567 void BuildLockset::warnIfMutexHeld(const NamedDecl *D, const Expr *Exp, 1568 Expr *MutexExp, StringRef DiagKind) { 1569 CapabilityExpr Cp = Analyzer->SxBuilder.translateAttrExpr(MutexExp, D, Exp); 1570 if (Cp.isInvalid()) { 1571 warnInvalidLock(Analyzer->Handler, MutexExp, D, Exp, DiagKind); 1572 return; 1573 } else if (Cp.shouldIgnore()) { 1574 return; 1575 } 1576 1577 FactEntry* LDat = FSet.findLock(Analyzer->FactMan, Cp); 1578 if (LDat) { 1579 Analyzer->Handler.handleFunExcludesLock( 1580 DiagKind, D->getNameAsString(), Cp.toString(), Exp->getExprLoc()); 1581 } 1582 } 1583 1584 /// \brief Checks guarded_by and pt_guarded_by attributes. 1585 /// Whenever we identify an access (read or write) to a DeclRefExpr that is 1586 /// marked with guarded_by, we must ensure the appropriate mutexes are held. 1587 /// Similarly, we check if the access is to an expression that dereferences 1588 /// a pointer marked with pt_guarded_by. 1589 void BuildLockset::checkAccess(const Expr *Exp, AccessKind AK, 1590 ProtectedOperationKind POK) { 1591 Exp = Exp->IgnoreParenCasts(); 1592 1593 SourceLocation Loc = Exp->getExprLoc(); 1594 1595 // Local variables of reference type cannot be re-assigned; 1596 // map them to their initializer. 1597 while (const auto *DRE = dyn_cast<DeclRefExpr>(Exp)) { 1598 const auto *VD = dyn_cast<VarDecl>(DRE->getDecl()->getCanonicalDecl()); 1599 if (VD && VD->isLocalVarDecl() && VD->getType()->isReferenceType()) { 1600 if (const auto *E = VD->getInit()) { 1601 Exp = E; 1602 continue; 1603 } 1604 } 1605 break; 1606 } 1607 1608 if (const UnaryOperator *UO = dyn_cast<UnaryOperator>(Exp)) { 1609 // For dereferences 1610 if (UO->getOpcode() == clang::UO_Deref) 1611 checkPtAccess(UO->getSubExpr(), AK, POK); 1612 return; 1613 } 1614 1615 if (const ArraySubscriptExpr *AE = dyn_cast<ArraySubscriptExpr>(Exp)) { 1616 checkPtAccess(AE->getLHS(), AK, POK); 1617 return; 1618 } 1619 1620 if (const MemberExpr *ME = dyn_cast<MemberExpr>(Exp)) { 1621 if (ME->isArrow()) 1622 checkPtAccess(ME->getBase(), AK, POK); 1623 else 1624 checkAccess(ME->getBase(), AK, POK); 1625 } 1626 1627 const ValueDecl *D = getValueDecl(Exp); 1628 if (!D || !D->hasAttrs()) 1629 return; 1630 1631 if (D->hasAttr<GuardedVarAttr>() && FSet.isEmpty(Analyzer->FactMan)) { 1632 Analyzer->Handler.handleNoMutexHeld("mutex", D, POK, AK, Loc); 1633 } 1634 1635 for (const auto *I : D->specific_attrs<GuardedByAttr>()) 1636 warnIfMutexNotHeld(D, Exp, AK, I->getArg(), POK, 1637 ClassifyDiagnostic(I), Loc); 1638 } 1639 1640 1641 /// \brief Checks pt_guarded_by and pt_guarded_var attributes. 1642 /// POK is the same operationKind that was passed to checkAccess. 1643 void BuildLockset::checkPtAccess(const Expr *Exp, AccessKind AK, 1644 ProtectedOperationKind POK) { 1645 while (true) { 1646 if (const ParenExpr *PE = dyn_cast<ParenExpr>(Exp)) { 1647 Exp = PE->getSubExpr(); 1648 continue; 1649 } 1650 if (const CastExpr *CE = dyn_cast<CastExpr>(Exp)) { 1651 if (CE->getCastKind() == CK_ArrayToPointerDecay) { 1652 // If it's an actual array, and not a pointer, then it's elements 1653 // are protected by GUARDED_BY, not PT_GUARDED_BY; 1654 checkAccess(CE->getSubExpr(), AK, POK); 1655 return; 1656 } 1657 Exp = CE->getSubExpr(); 1658 continue; 1659 } 1660 break; 1661 } 1662 1663 // Pass by reference warnings are under a different flag. 1664 ProtectedOperationKind PtPOK = POK_VarDereference; 1665 if (POK == POK_PassByRef) PtPOK = POK_PtPassByRef; 1666 1667 const ValueDecl *D = getValueDecl(Exp); 1668 if (!D || !D->hasAttrs()) 1669 return; 1670 1671 if (D->hasAttr<PtGuardedVarAttr>() && FSet.isEmpty(Analyzer->FactMan)) 1672 Analyzer->Handler.handleNoMutexHeld("mutex", D, PtPOK, AK, 1673 Exp->getExprLoc()); 1674 1675 for (auto const *I : D->specific_attrs<PtGuardedByAttr>()) 1676 warnIfMutexNotHeld(D, Exp, AK, I->getArg(), PtPOK, 1677 ClassifyDiagnostic(I), Exp->getExprLoc()); 1678 } 1679 1680 /// \brief Process a function call, method call, constructor call, 1681 /// or destructor call. This involves looking at the attributes on the 1682 /// corresponding function/method/constructor/destructor, issuing warnings, 1683 /// and updating the locksets accordingly. 1684 /// 1685 /// FIXME: For classes annotated with one of the guarded annotations, we need 1686 /// to treat const method calls as reads and non-const method calls as writes, 1687 /// and check that the appropriate locks are held. Non-const method calls with 1688 /// the same signature as const method calls can be also treated as reads. 1689 /// 1690 void BuildLockset::handleCall(Expr *Exp, const NamedDecl *D, VarDecl *VD) { 1691 SourceLocation Loc = Exp->getExprLoc(); 1692 CapExprSet ExclusiveLocksToAdd, SharedLocksToAdd; 1693 CapExprSet ExclusiveLocksToRemove, SharedLocksToRemove, GenericLocksToRemove; 1694 CapExprSet ScopedExclusiveReqs, ScopedSharedReqs; 1695 StringRef CapDiagKind = "mutex"; 1696 1697 // Figure out if we're calling the constructor of scoped lockable class 1698 bool isScopedVar = false; 1699 if (VD) { 1700 if (const CXXConstructorDecl *CD = dyn_cast<const CXXConstructorDecl>(D)) { 1701 const CXXRecordDecl* PD = CD->getParent(); 1702 if (PD && PD->hasAttr<ScopedLockableAttr>()) 1703 isScopedVar = true; 1704 } 1705 } 1706 1707 for(Attr *Atconst : D->attrs()) { 1708 Attr* At = const_cast<Attr*>(Atconst); 1709 switch (At->getKind()) { 1710 // When we encounter a lock function, we need to add the lock to our 1711 // lockset. 1712 case attr::AcquireCapability: { 1713 auto *A = cast<AcquireCapabilityAttr>(At); 1714 Analyzer->getMutexIDs(A->isShared() ? SharedLocksToAdd 1715 : ExclusiveLocksToAdd, 1716 A, Exp, D, VD); 1717 1718 CapDiagKind = ClassifyDiagnostic(A); 1719 break; 1720 } 1721 1722 // An assert will add a lock to the lockset, but will not generate 1723 // a warning if it is already there, and will not generate a warning 1724 // if it is not removed. 1725 case attr::AssertExclusiveLock: { 1726 AssertExclusiveLockAttr *A = cast<AssertExclusiveLockAttr>(At); 1727 1728 CapExprSet AssertLocks; 1729 Analyzer->getMutexIDs(AssertLocks, A, Exp, D, VD); 1730 for (const auto &AssertLock : AssertLocks) 1731 Analyzer->addLock(FSet, 1732 llvm::make_unique<LockableFactEntry>( 1733 AssertLock, LK_Exclusive, Loc, false, true), 1734 ClassifyDiagnostic(A)); 1735 break; 1736 } 1737 case attr::AssertSharedLock: { 1738 AssertSharedLockAttr *A = cast<AssertSharedLockAttr>(At); 1739 1740 CapExprSet AssertLocks; 1741 Analyzer->getMutexIDs(AssertLocks, A, Exp, D, VD); 1742 for (const auto &AssertLock : AssertLocks) 1743 Analyzer->addLock(FSet, llvm::make_unique<LockableFactEntry>( 1744 AssertLock, LK_Shared, Loc, false, true), 1745 ClassifyDiagnostic(A)); 1746 break; 1747 } 1748 1749 // When we encounter an unlock function, we need to remove unlocked 1750 // mutexes from the lockset, and flag a warning if they are not there. 1751 case attr::ReleaseCapability: { 1752 auto *A = cast<ReleaseCapabilityAttr>(At); 1753 if (A->isGeneric()) 1754 Analyzer->getMutexIDs(GenericLocksToRemove, A, Exp, D, VD); 1755 else if (A->isShared()) 1756 Analyzer->getMutexIDs(SharedLocksToRemove, A, Exp, D, VD); 1757 else 1758 Analyzer->getMutexIDs(ExclusiveLocksToRemove, A, Exp, D, VD); 1759 1760 CapDiagKind = ClassifyDiagnostic(A); 1761 break; 1762 } 1763 1764 case attr::RequiresCapability: { 1765 RequiresCapabilityAttr *A = cast<RequiresCapabilityAttr>(At); 1766 for (auto *Arg : A->args()) { 1767 warnIfMutexNotHeld(D, Exp, A->isShared() ? AK_Read : AK_Written, Arg, 1768 POK_FunctionCall, ClassifyDiagnostic(A), 1769 Exp->getExprLoc()); 1770 // use for adopting a lock 1771 if (isScopedVar) { 1772 Analyzer->getMutexIDs(A->isShared() ? ScopedSharedReqs 1773 : ScopedExclusiveReqs, 1774 A, Exp, D, VD); 1775 } 1776 } 1777 break; 1778 } 1779 1780 case attr::LocksExcluded: { 1781 LocksExcludedAttr *A = cast<LocksExcludedAttr>(At); 1782 for (auto *Arg : A->args()) 1783 warnIfMutexHeld(D, Exp, Arg, ClassifyDiagnostic(A)); 1784 break; 1785 } 1786 1787 // Ignore attributes unrelated to thread-safety 1788 default: 1789 break; 1790 } 1791 } 1792 1793 // Add locks. 1794 for (const auto &M : ExclusiveLocksToAdd) 1795 Analyzer->addLock(FSet, llvm::make_unique<LockableFactEntry>( 1796 M, LK_Exclusive, Loc, isScopedVar), 1797 CapDiagKind); 1798 for (const auto &M : SharedLocksToAdd) 1799 Analyzer->addLock(FSet, llvm::make_unique<LockableFactEntry>( 1800 M, LK_Shared, Loc, isScopedVar), 1801 CapDiagKind); 1802 1803 if (isScopedVar) { 1804 // Add the managing object as a dummy mutex, mapped to the underlying mutex. 1805 SourceLocation MLoc = VD->getLocation(); 1806 DeclRefExpr DRE(VD, false, VD->getType(), VK_LValue, VD->getLocation()); 1807 // FIXME: does this store a pointer to DRE? 1808 CapabilityExpr Scp = Analyzer->SxBuilder.translateAttrExpr(&DRE, nullptr); 1809 1810 std::copy(ScopedExclusiveReqs.begin(), ScopedExclusiveReqs.end(), 1811 std::back_inserter(ExclusiveLocksToAdd)); 1812 std::copy(ScopedSharedReqs.begin(), ScopedSharedReqs.end(), 1813 std::back_inserter(SharedLocksToAdd)); 1814 Analyzer->addLock(FSet, 1815 llvm::make_unique<ScopedLockableFactEntry>( 1816 Scp, MLoc, ExclusiveLocksToAdd, SharedLocksToAdd), 1817 CapDiagKind); 1818 } 1819 1820 // Remove locks. 1821 // FIXME -- should only fully remove if the attribute refers to 'this'. 1822 bool Dtor = isa<CXXDestructorDecl>(D); 1823 for (const auto &M : ExclusiveLocksToRemove) 1824 Analyzer->removeLock(FSet, M, Loc, Dtor, LK_Exclusive, CapDiagKind); 1825 for (const auto &M : SharedLocksToRemove) 1826 Analyzer->removeLock(FSet, M, Loc, Dtor, LK_Shared, CapDiagKind); 1827 for (const auto &M : GenericLocksToRemove) 1828 Analyzer->removeLock(FSet, M, Loc, Dtor, LK_Generic, CapDiagKind); 1829 } 1830 1831 1832 /// \brief For unary operations which read and write a variable, we need to 1833 /// check whether we hold any required mutexes. Reads are checked in 1834 /// VisitCastExpr. 1835 void BuildLockset::VisitUnaryOperator(UnaryOperator *UO) { 1836 switch (UO->getOpcode()) { 1837 case clang::UO_PostDec: 1838 case clang::UO_PostInc: 1839 case clang::UO_PreDec: 1840 case clang::UO_PreInc: { 1841 checkAccess(UO->getSubExpr(), AK_Written); 1842 break; 1843 } 1844 default: 1845 break; 1846 } 1847 } 1848 1849 /// For binary operations which assign to a variable (writes), we need to check 1850 /// whether we hold any required mutexes. 1851 /// FIXME: Deal with non-primitive types. 1852 void BuildLockset::VisitBinaryOperator(BinaryOperator *BO) { 1853 if (!BO->isAssignmentOp()) 1854 return; 1855 1856 // adjust the context 1857 LVarCtx = Analyzer->LocalVarMap.getNextContext(CtxIndex, BO, LVarCtx); 1858 1859 checkAccess(BO->getLHS(), AK_Written); 1860 } 1861 1862 1863 /// Whenever we do an LValue to Rvalue cast, we are reading a variable and 1864 /// need to ensure we hold any required mutexes. 1865 /// FIXME: Deal with non-primitive types. 1866 void BuildLockset::VisitCastExpr(CastExpr *CE) { 1867 if (CE->getCastKind() != CK_LValueToRValue) 1868 return; 1869 checkAccess(CE->getSubExpr(), AK_Read); 1870 } 1871 1872 1873 void BuildLockset::VisitCallExpr(CallExpr *Exp) { 1874 bool ExamineArgs = true; 1875 bool OperatorFun = false; 1876 1877 if (CXXMemberCallExpr *CE = dyn_cast<CXXMemberCallExpr>(Exp)) { 1878 MemberExpr *ME = dyn_cast<MemberExpr>(CE->getCallee()); 1879 // ME can be null when calling a method pointer 1880 CXXMethodDecl *MD = CE->getMethodDecl(); 1881 1882 if (ME && MD) { 1883 if (ME->isArrow()) { 1884 if (MD->isConst()) { 1885 checkPtAccess(CE->getImplicitObjectArgument(), AK_Read); 1886 } else { // FIXME -- should be AK_Written 1887 checkPtAccess(CE->getImplicitObjectArgument(), AK_Read); 1888 } 1889 } else { 1890 if (MD->isConst()) 1891 checkAccess(CE->getImplicitObjectArgument(), AK_Read); 1892 else // FIXME -- should be AK_Written 1893 checkAccess(CE->getImplicitObjectArgument(), AK_Read); 1894 } 1895 } 1896 } else if (CXXOperatorCallExpr *OE = dyn_cast<CXXOperatorCallExpr>(Exp)) { 1897 OperatorFun = true; 1898 1899 auto OEop = OE->getOperator(); 1900 switch (OEop) { 1901 case OO_Equal: { 1902 ExamineArgs = false; 1903 const Expr *Target = OE->getArg(0); 1904 const Expr *Source = OE->getArg(1); 1905 checkAccess(Target, AK_Written); 1906 checkAccess(Source, AK_Read); 1907 break; 1908 } 1909 case OO_Star: 1910 case OO_Arrow: 1911 case OO_Subscript: { 1912 const Expr *Obj = OE->getArg(0); 1913 checkAccess(Obj, AK_Read); 1914 if (!(OEop == OO_Star && OE->getNumArgs() > 1)) { 1915 // Grrr. operator* can be multiplication... 1916 checkPtAccess(Obj, AK_Read); 1917 } 1918 break; 1919 } 1920 default: { 1921 // TODO: get rid of this, and rely on pass-by-ref instead. 1922 const Expr *Obj = OE->getArg(0); 1923 checkAccess(Obj, AK_Read); 1924 break; 1925 } 1926 } 1927 } 1928 1929 1930 if (ExamineArgs) { 1931 if (FunctionDecl *FD = Exp->getDirectCallee()) { 1932 unsigned Fn = FD->getNumParams(); 1933 unsigned Cn = Exp->getNumArgs(); 1934 unsigned Skip = 0; 1935 1936 unsigned i = 0; 1937 if (OperatorFun) { 1938 if (isa<CXXMethodDecl>(FD)) { 1939 // First arg in operator call is implicit self argument, 1940 // and doesn't appear in the FunctionDecl. 1941 Skip = 1; 1942 Cn--; 1943 } else { 1944 // Ignore the first argument of operators; it's been checked above. 1945 i = 1; 1946 } 1947 } 1948 // Ignore default arguments 1949 unsigned n = (Fn < Cn) ? Fn : Cn; 1950 1951 for (; i < n; ++i) { 1952 ParmVarDecl* Pvd = FD->getParamDecl(i); 1953 Expr* Arg = Exp->getArg(i+Skip); 1954 QualType Qt = Pvd->getType(); 1955 if (Qt->isReferenceType()) 1956 checkAccess(Arg, AK_Read, POK_PassByRef); 1957 } 1958 } 1959 } 1960 1961 NamedDecl *D = dyn_cast_or_null<NamedDecl>(Exp->getCalleeDecl()); 1962 if(!D || !D->hasAttrs()) 1963 return; 1964 handleCall(Exp, D); 1965 } 1966 1967 void BuildLockset::VisitCXXConstructExpr(CXXConstructExpr *Exp) { 1968 const CXXConstructorDecl *D = Exp->getConstructor(); 1969 if (D && D->isCopyConstructor()) { 1970 const Expr* Source = Exp->getArg(0); 1971 checkAccess(Source, AK_Read); 1972 } 1973 // FIXME -- only handles constructors in DeclStmt below. 1974 } 1975 1976 void BuildLockset::VisitDeclStmt(DeclStmt *S) { 1977 // adjust the context 1978 LVarCtx = Analyzer->LocalVarMap.getNextContext(CtxIndex, S, LVarCtx); 1979 1980 for (auto *D : S->getDeclGroup()) { 1981 if (VarDecl *VD = dyn_cast_or_null<VarDecl>(D)) { 1982 Expr *E = VD->getInit(); 1983 // handle constructors that involve temporaries 1984 if (ExprWithCleanups *EWC = dyn_cast_or_null<ExprWithCleanups>(E)) 1985 E = EWC->getSubExpr(); 1986 1987 if (CXXConstructExpr *CE = dyn_cast_or_null<CXXConstructExpr>(E)) { 1988 NamedDecl *CtorD = dyn_cast_or_null<NamedDecl>(CE->getConstructor()); 1989 if (!CtorD || !CtorD->hasAttrs()) 1990 return; 1991 handleCall(CE, CtorD, VD); 1992 } 1993 } 1994 } 1995 } 1996 1997 1998 1999 /// \brief Compute the intersection of two locksets and issue warnings for any 2000 /// locks in the symmetric difference. 2001 /// 2002 /// This function is used at a merge point in the CFG when comparing the lockset 2003 /// of each branch being merged. For example, given the following sequence: 2004 /// A; if () then B; else C; D; we need to check that the lockset after B and C 2005 /// are the same. In the event of a difference, we use the intersection of these 2006 /// two locksets at the start of D. 2007 /// 2008 /// \param FSet1 The first lockset. 2009 /// \param FSet2 The second lockset. 2010 /// \param JoinLoc The location of the join point for error reporting 2011 /// \param LEK1 The error message to report if a mutex is missing from LSet1 2012 /// \param LEK2 The error message to report if a mutex is missing from Lset2 2013 void ThreadSafetyAnalyzer::intersectAndWarn(FactSet &FSet1, 2014 const FactSet &FSet2, 2015 SourceLocation JoinLoc, 2016 LockErrorKind LEK1, 2017 LockErrorKind LEK2, 2018 bool Modify) { 2019 FactSet FSet1Orig = FSet1; 2020 2021 // Find locks in FSet2 that conflict or are not in FSet1, and warn. 2022 for (const auto &Fact : FSet2) { 2023 const FactEntry *LDat1 = nullptr; 2024 const FactEntry *LDat2 = &FactMan[Fact]; 2025 FactSet::iterator Iter1 = FSet1.findLockIter(FactMan, *LDat2); 2026 if (Iter1 != FSet1.end()) LDat1 = &FactMan[*Iter1]; 2027 2028 if (LDat1) { 2029 if (LDat1->kind() != LDat2->kind()) { 2030 Handler.handleExclusiveAndShared("mutex", LDat2->toString(), 2031 LDat2->loc(), LDat1->loc()); 2032 if (Modify && LDat1->kind() != LK_Exclusive) { 2033 // Take the exclusive lock, which is the one in FSet2. 2034 *Iter1 = Fact; 2035 } 2036 } 2037 else if (Modify && LDat1->asserted() && !LDat2->asserted()) { 2038 // The non-asserted lock in FSet2 is the one we want to track. 2039 *Iter1 = Fact; 2040 } 2041 } else { 2042 LDat2->handleRemovalFromIntersection(FSet2, FactMan, JoinLoc, LEK1, 2043 Handler); 2044 } 2045 } 2046 2047 // Find locks in FSet1 that are not in FSet2, and remove them. 2048 for (const auto &Fact : FSet1Orig) { 2049 const FactEntry *LDat1 = &FactMan[Fact]; 2050 const FactEntry *LDat2 = FSet2.findLock(FactMan, *LDat1); 2051 2052 if (!LDat2) { 2053 LDat1->handleRemovalFromIntersection(FSet1Orig, FactMan, JoinLoc, LEK2, 2054 Handler); 2055 if (Modify) 2056 FSet1.removeLock(FactMan, *LDat1); 2057 } 2058 } 2059 } 2060 2061 2062 // Return true if block B never continues to its successors. 2063 static bool neverReturns(const CFGBlock *B) { 2064 if (B->hasNoReturnElement()) 2065 return true; 2066 if (B->empty()) 2067 return false; 2068 2069 CFGElement Last = B->back(); 2070 if (Optional<CFGStmt> S = Last.getAs<CFGStmt>()) { 2071 if (isa<CXXThrowExpr>(S->getStmt())) 2072 return true; 2073 } 2074 return false; 2075 } 2076 2077 2078 /// \brief Check a function's CFG for thread-safety violations. 2079 /// 2080 /// We traverse the blocks in the CFG, compute the set of mutexes that are held 2081 /// at the end of each block, and issue warnings for thread safety violations. 2082 /// Each block in the CFG is traversed exactly once. 2083 void ThreadSafetyAnalyzer::runAnalysis(AnalysisDeclContext &AC) { 2084 // TODO: this whole function needs be rewritten as a visitor for CFGWalker. 2085 // For now, we just use the walker to set things up. 2086 threadSafety::CFGWalker walker; 2087 if (!walker.init(AC)) 2088 return; 2089 2090 // AC.dumpCFG(true); 2091 // threadSafety::printSCFG(walker); 2092 2093 CFG *CFGraph = walker.getGraph(); 2094 const NamedDecl *D = walker.getDecl(); 2095 const FunctionDecl *CurrentFunction = dyn_cast<FunctionDecl>(D); 2096 CurrentMethod = dyn_cast<CXXMethodDecl>(D); 2097 2098 if (D->hasAttr<NoThreadSafetyAnalysisAttr>()) 2099 return; 2100 2101 // FIXME: Do something a bit more intelligent inside constructor and 2102 // destructor code. Constructors and destructors must assume unique access 2103 // to 'this', so checks on member variable access is disabled, but we should 2104 // still enable checks on other objects. 2105 if (isa<CXXConstructorDecl>(D)) 2106 return; // Don't check inside constructors. 2107 if (isa<CXXDestructorDecl>(D)) 2108 return; // Don't check inside destructors. 2109 2110 Handler.enterFunction(CurrentFunction); 2111 2112 BlockInfo.resize(CFGraph->getNumBlockIDs(), 2113 CFGBlockInfo::getEmptyBlockInfo(LocalVarMap)); 2114 2115 // We need to explore the CFG via a "topological" ordering. 2116 // That way, we will be guaranteed to have information about required 2117 // predecessor locksets when exploring a new block. 2118 const PostOrderCFGView *SortedGraph = walker.getSortedGraph(); 2119 PostOrderCFGView::CFGBlockSet VisitedBlocks(CFGraph); 2120 2121 // Mark entry block as reachable 2122 BlockInfo[CFGraph->getEntry().getBlockID()].Reachable = true; 2123 2124 // Compute SSA names for local variables 2125 LocalVarMap.traverseCFG(CFGraph, SortedGraph, BlockInfo); 2126 2127 // Fill in source locations for all CFGBlocks. 2128 findBlockLocations(CFGraph, SortedGraph, BlockInfo); 2129 2130 CapExprSet ExclusiveLocksAcquired; 2131 CapExprSet SharedLocksAcquired; 2132 CapExprSet LocksReleased; 2133 2134 // Add locks from exclusive_locks_required and shared_locks_required 2135 // to initial lockset. Also turn off checking for lock and unlock functions. 2136 // FIXME: is there a more intelligent way to check lock/unlock functions? 2137 if (!SortedGraph->empty() && D->hasAttrs()) { 2138 const CFGBlock *FirstBlock = *SortedGraph->begin(); 2139 FactSet &InitialLockset = BlockInfo[FirstBlock->getBlockID()].EntrySet; 2140 2141 CapExprSet ExclusiveLocksToAdd; 2142 CapExprSet SharedLocksToAdd; 2143 StringRef CapDiagKind = "mutex"; 2144 2145 SourceLocation Loc = D->getLocation(); 2146 for (const auto *Attr : D->attrs()) { 2147 Loc = Attr->getLocation(); 2148 if (const auto *A = dyn_cast<RequiresCapabilityAttr>(Attr)) { 2149 getMutexIDs(A->isShared() ? SharedLocksToAdd : ExclusiveLocksToAdd, A, 2150 nullptr, D); 2151 CapDiagKind = ClassifyDiagnostic(A); 2152 } else if (const auto *A = dyn_cast<ReleaseCapabilityAttr>(Attr)) { 2153 // UNLOCK_FUNCTION() is used to hide the underlying lock implementation. 2154 // We must ignore such methods. 2155 if (A->args_size() == 0) 2156 return; 2157 // FIXME -- deal with exclusive vs. shared unlock functions? 2158 getMutexIDs(ExclusiveLocksToAdd, A, nullptr, D); 2159 getMutexIDs(LocksReleased, A, nullptr, D); 2160 CapDiagKind = ClassifyDiagnostic(A); 2161 } else if (const auto *A = dyn_cast<AcquireCapabilityAttr>(Attr)) { 2162 if (A->args_size() == 0) 2163 return; 2164 getMutexIDs(A->isShared() ? SharedLocksAcquired 2165 : ExclusiveLocksAcquired, 2166 A, nullptr, D); 2167 CapDiagKind = ClassifyDiagnostic(A); 2168 } else if (isa<ExclusiveTrylockFunctionAttr>(Attr)) { 2169 // Don't try to check trylock functions for now 2170 return; 2171 } else if (isa<SharedTrylockFunctionAttr>(Attr)) { 2172 // Don't try to check trylock functions for now 2173 return; 2174 } 2175 } 2176 2177 // FIXME -- Loc can be wrong here. 2178 for (const auto &Mu : ExclusiveLocksToAdd) { 2179 auto Entry = llvm::make_unique<LockableFactEntry>(Mu, LK_Exclusive, Loc); 2180 Entry->setDeclared(true); 2181 addLock(InitialLockset, std::move(Entry), CapDiagKind, true); 2182 } 2183 for (const auto &Mu : SharedLocksToAdd) { 2184 auto Entry = llvm::make_unique<LockableFactEntry>(Mu, LK_Shared, Loc); 2185 Entry->setDeclared(true); 2186 addLock(InitialLockset, std::move(Entry), CapDiagKind, true); 2187 } 2188 } 2189 2190 for (const auto *CurrBlock : *SortedGraph) { 2191 int CurrBlockID = CurrBlock->getBlockID(); 2192 CFGBlockInfo *CurrBlockInfo = &BlockInfo[CurrBlockID]; 2193 2194 // Use the default initial lockset in case there are no predecessors. 2195 VisitedBlocks.insert(CurrBlock); 2196 2197 // Iterate through the predecessor blocks and warn if the lockset for all 2198 // predecessors is not the same. We take the entry lockset of the current 2199 // block to be the intersection of all previous locksets. 2200 // FIXME: By keeping the intersection, we may output more errors in future 2201 // for a lock which is not in the intersection, but was in the union. We 2202 // may want to also keep the union in future. As an example, let's say 2203 // the intersection contains Mutex L, and the union contains L and M. 2204 // Later we unlock M. At this point, we would output an error because we 2205 // never locked M; although the real error is probably that we forgot to 2206 // lock M on all code paths. Conversely, let's say that later we lock M. 2207 // In this case, we should compare against the intersection instead of the 2208 // union because the real error is probably that we forgot to unlock M on 2209 // all code paths. 2210 bool LocksetInitialized = false; 2211 SmallVector<CFGBlock *, 8> SpecialBlocks; 2212 for (CFGBlock::const_pred_iterator PI = CurrBlock->pred_begin(), 2213 PE = CurrBlock->pred_end(); PI != PE; ++PI) { 2214 2215 // if *PI -> CurrBlock is a back edge 2216 if (*PI == nullptr || !VisitedBlocks.alreadySet(*PI)) 2217 continue; 2218 2219 int PrevBlockID = (*PI)->getBlockID(); 2220 CFGBlockInfo *PrevBlockInfo = &BlockInfo[PrevBlockID]; 2221 2222 // Ignore edges from blocks that can't return. 2223 if (neverReturns(*PI) || !PrevBlockInfo->Reachable) 2224 continue; 2225 2226 // Okay, we can reach this block from the entry. 2227 CurrBlockInfo->Reachable = true; 2228 2229 // If the previous block ended in a 'continue' or 'break' statement, then 2230 // a difference in locksets is probably due to a bug in that block, rather 2231 // than in some other predecessor. In that case, keep the other 2232 // predecessor's lockset. 2233 if (const Stmt *Terminator = (*PI)->getTerminator()) { 2234 if (isa<ContinueStmt>(Terminator) || isa<BreakStmt>(Terminator)) { 2235 SpecialBlocks.push_back(*PI); 2236 continue; 2237 } 2238 } 2239 2240 FactSet PrevLockset; 2241 getEdgeLockset(PrevLockset, PrevBlockInfo->ExitSet, *PI, CurrBlock); 2242 2243 if (!LocksetInitialized) { 2244 CurrBlockInfo->EntrySet = PrevLockset; 2245 LocksetInitialized = true; 2246 } else { 2247 intersectAndWarn(CurrBlockInfo->EntrySet, PrevLockset, 2248 CurrBlockInfo->EntryLoc, 2249 LEK_LockedSomePredecessors); 2250 } 2251 } 2252 2253 // Skip rest of block if it's not reachable. 2254 if (!CurrBlockInfo->Reachable) 2255 continue; 2256 2257 // Process continue and break blocks. Assume that the lockset for the 2258 // resulting block is unaffected by any discrepancies in them. 2259 for (const auto *PrevBlock : SpecialBlocks) { 2260 int PrevBlockID = PrevBlock->getBlockID(); 2261 CFGBlockInfo *PrevBlockInfo = &BlockInfo[PrevBlockID]; 2262 2263 if (!LocksetInitialized) { 2264 CurrBlockInfo->EntrySet = PrevBlockInfo->ExitSet; 2265 LocksetInitialized = true; 2266 } else { 2267 // Determine whether this edge is a loop terminator for diagnostic 2268 // purposes. FIXME: A 'break' statement might be a loop terminator, but 2269 // it might also be part of a switch. Also, a subsequent destructor 2270 // might add to the lockset, in which case the real issue might be a 2271 // double lock on the other path. 2272 const Stmt *Terminator = PrevBlock->getTerminator(); 2273 bool IsLoop = Terminator && isa<ContinueStmt>(Terminator); 2274 2275 FactSet PrevLockset; 2276 getEdgeLockset(PrevLockset, PrevBlockInfo->ExitSet, 2277 PrevBlock, CurrBlock); 2278 2279 // Do not update EntrySet. 2280 intersectAndWarn(CurrBlockInfo->EntrySet, PrevLockset, 2281 PrevBlockInfo->ExitLoc, 2282 IsLoop ? LEK_LockedSomeLoopIterations 2283 : LEK_LockedSomePredecessors, 2284 false); 2285 } 2286 } 2287 2288 BuildLockset LocksetBuilder(this, *CurrBlockInfo); 2289 2290 // Visit all the statements in the basic block. 2291 for (CFGBlock::const_iterator BI = CurrBlock->begin(), 2292 BE = CurrBlock->end(); BI != BE; ++BI) { 2293 switch (BI->getKind()) { 2294 case CFGElement::Statement: { 2295 CFGStmt CS = BI->castAs<CFGStmt>(); 2296 LocksetBuilder.Visit(const_cast<Stmt*>(CS.getStmt())); 2297 break; 2298 } 2299 // Ignore BaseDtor, MemberDtor, and TemporaryDtor for now. 2300 case CFGElement::AutomaticObjectDtor: { 2301 CFGAutomaticObjDtor AD = BI->castAs<CFGAutomaticObjDtor>(); 2302 CXXDestructorDecl *DD = const_cast<CXXDestructorDecl *>( 2303 AD.getDestructorDecl(AC.getASTContext())); 2304 if (!DD->hasAttrs()) 2305 break; 2306 2307 // Create a dummy expression, 2308 VarDecl *VD = const_cast<VarDecl*>(AD.getVarDecl()); 2309 DeclRefExpr DRE(VD, false, VD->getType().getNonReferenceType(), 2310 VK_LValue, AD.getTriggerStmt()->getLocEnd()); 2311 LocksetBuilder.handleCall(&DRE, DD); 2312 break; 2313 } 2314 default: 2315 break; 2316 } 2317 } 2318 CurrBlockInfo->ExitSet = LocksetBuilder.FSet; 2319 2320 // For every back edge from CurrBlock (the end of the loop) to another block 2321 // (FirstLoopBlock) we need to check that the Lockset of Block is equal to 2322 // the one held at the beginning of FirstLoopBlock. We can look up the 2323 // Lockset held at the beginning of FirstLoopBlock in the EntryLockSets map. 2324 for (CFGBlock::const_succ_iterator SI = CurrBlock->succ_begin(), 2325 SE = CurrBlock->succ_end(); SI != SE; ++SI) { 2326 2327 // if CurrBlock -> *SI is *not* a back edge 2328 if (*SI == nullptr || !VisitedBlocks.alreadySet(*SI)) 2329 continue; 2330 2331 CFGBlock *FirstLoopBlock = *SI; 2332 CFGBlockInfo *PreLoop = &BlockInfo[FirstLoopBlock->getBlockID()]; 2333 CFGBlockInfo *LoopEnd = &BlockInfo[CurrBlockID]; 2334 intersectAndWarn(LoopEnd->ExitSet, PreLoop->EntrySet, 2335 PreLoop->EntryLoc, 2336 LEK_LockedSomeLoopIterations, 2337 false); 2338 } 2339 } 2340 2341 CFGBlockInfo *Initial = &BlockInfo[CFGraph->getEntry().getBlockID()]; 2342 CFGBlockInfo *Final = &BlockInfo[CFGraph->getExit().getBlockID()]; 2343 2344 // Skip the final check if the exit block is unreachable. 2345 if (!Final->Reachable) 2346 return; 2347 2348 // By default, we expect all locks held on entry to be held on exit. 2349 FactSet ExpectedExitSet = Initial->EntrySet; 2350 2351 // Adjust the expected exit set by adding or removing locks, as declared 2352 // by *-LOCK_FUNCTION and UNLOCK_FUNCTION. The intersect below will then 2353 // issue the appropriate warning. 2354 // FIXME: the location here is not quite right. 2355 for (const auto &Lock : ExclusiveLocksAcquired) 2356 ExpectedExitSet.addLock(FactMan, llvm::make_unique<LockableFactEntry>( 2357 Lock, LK_Exclusive, D->getLocation())); 2358 for (const auto &Lock : SharedLocksAcquired) 2359 ExpectedExitSet.addLock(FactMan, llvm::make_unique<LockableFactEntry>( 2360 Lock, LK_Shared, D->getLocation())); 2361 for (const auto &Lock : LocksReleased) 2362 ExpectedExitSet.removeLock(FactMan, Lock); 2363 2364 // FIXME: Should we call this function for all blocks which exit the function? 2365 intersectAndWarn(ExpectedExitSet, Final->ExitSet, 2366 Final->ExitLoc, 2367 LEK_LockedAtEndOfFunction, 2368 LEK_NotLockedAtEndOfFunction, 2369 false); 2370 2371 Handler.leaveFunction(CurrentFunction); 2372 } 2373 2374 2375 /// \brief Check a function's CFG for thread-safety violations. 2376 /// 2377 /// We traverse the blocks in the CFG, compute the set of mutexes that are held 2378 /// at the end of each block, and issue warnings for thread safety violations. 2379 /// Each block in the CFG is traversed exactly once. 2380 void threadSafety::runThreadSafetyAnalysis(AnalysisDeclContext &AC, 2381 ThreadSafetyHandler &Handler, 2382 BeforeSet **BSet) { 2383 if (!*BSet) 2384 *BSet = new BeforeSet; 2385 ThreadSafetyAnalyzer Analyzer(Handler, *BSet); 2386 Analyzer.runAnalysis(AC); 2387 } 2388 2389 void threadSafety::threadSafetyCleanup(BeforeSet *Cache) { delete Cache; } 2390 2391 /// \brief Helper function that returns a LockKind required for the given level 2392 /// of access. 2393 LockKind threadSafety::getLockKindFromAccessKind(AccessKind AK) { 2394 switch (AK) { 2395 case AK_Read : 2396 return LK_Shared; 2397 case AK_Written : 2398 return LK_Exclusive; 2399 } 2400 llvm_unreachable("Unknown AccessKind"); 2401 } 2402