ThreadSafety.cpp revision 0e2c34f92f00628d48968dfea096d36381f494cb
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 48 49namespace clang { 50namespace threadSafety { 51 52// Key method definition 53ThreadSafetyHandler::~ThreadSafetyHandler() {} 54 55class TILPrinter : 56 public til::PrettyPrinter<TILPrinter, llvm::raw_ostream> {}; 57 58 59/// Issue a warning about an invalid lock expression 60static void warnInvalidLock(ThreadSafetyHandler &Handler, 61 const Expr *MutexExp, const NamedDecl *D, 62 const Expr *DeclExp, StringRef Kind) { 63 SourceLocation Loc; 64 if (DeclExp) 65 Loc = DeclExp->getExprLoc(); 66 67 // FIXME: add a note about the attribute location in MutexExp or D 68 if (Loc.isValid()) 69 Handler.handleInvalidLockExp(Kind, Loc); 70} 71 72 73/// \brief A set of CapabilityInfo objects, which are compiled from the 74/// requires attributes on a function. 75class CapExprSet : public SmallVector<CapabilityExpr, 4> { 76public: 77 /// \brief Push M onto list, but discard duplicates. 78 void push_back_nodup(const CapabilityExpr &CapE) { 79 iterator It = std::find_if(begin(), end(), 80 [=](const CapabilityExpr &CapE2) { 81 return CapE.equals(CapE2); 82 }); 83 if (It == end()) 84 push_back(CapE); 85 } 86}; 87 88class FactManager; 89class FactSet; 90 91/// \brief This is a helper class that stores a fact that is known at a 92/// particular point in program execution. Currently, a fact is a capability, 93/// along with additional information, such as where it was acquired, whether 94/// it is exclusive or shared, etc. 95/// 96/// FIXME: this analysis does not currently support either re-entrant 97/// locking or lock "upgrading" and "downgrading" between exclusive and 98/// shared. 99class FactEntry : public CapabilityExpr { 100private: 101 LockKind LKind; ///< exclusive or shared 102 SourceLocation AcquireLoc; ///< where it was acquired. 103 bool Asserted; ///< true if the lock was asserted 104 bool Declared; ///< true if the lock was declared 105 106public: 107 FactEntry(const CapabilityExpr &CE, LockKind LK, SourceLocation Loc, 108 bool Asrt, bool Declrd = false) 109 : CapabilityExpr(CE), LKind(LK), AcquireLoc(Loc), Asserted(Asrt), 110 Declared(Declrd) {} 111 112 virtual ~FactEntry() {} 113 114 LockKind kind() const { return LKind; } 115 SourceLocation loc() const { return AcquireLoc; } 116 bool asserted() const { return Asserted; } 117 bool declared() const { return Declared; } 118 119 void setDeclared(bool D) { Declared = D; } 120 121 virtual void 122 handleRemovalFromIntersection(const FactSet &FSet, FactManager &FactMan, 123 SourceLocation JoinLoc, LockErrorKind LEK, 124 ThreadSafetyHandler &Handler) const = 0; 125 virtual void handleUnlock(FactSet &FSet, FactManager &FactMan, 126 const CapabilityExpr &Cp, SourceLocation UnlockLoc, 127 bool FullyRemove, ThreadSafetyHandler &Handler, 128 StringRef DiagKind) const = 0; 129 130 // Return true if LKind >= LK, where exclusive > shared 131 bool isAtLeast(LockKind LK) { 132 return (LKind == LK_Exclusive) || (LK == LK_Shared); 133 } 134}; 135 136 137typedef unsigned short FactID; 138 139/// \brief FactManager manages the memory for all facts that are created during 140/// the analysis of a single routine. 141class FactManager { 142private: 143 std::vector<std::unique_ptr<FactEntry>> Facts; 144 145public: 146 FactID newFact(std::unique_ptr<FactEntry> Entry) { 147 Facts.push_back(std::move(Entry)); 148 return static_cast<unsigned short>(Facts.size() - 1); 149 } 150 151 const FactEntry &operator[](FactID F) const { return *Facts[F]; } 152 FactEntry &operator[](FactID F) { return *Facts[F]; } 153}; 154 155 156/// \brief A FactSet is the set of facts that are known to be true at a 157/// particular program point. FactSets must be small, because they are 158/// frequently copied, and are thus implemented as a set of indices into a 159/// table maintained by a FactManager. A typical FactSet only holds 1 or 2 160/// locks, so we can get away with doing a linear search for lookup. Note 161/// that a hashtable or map is inappropriate in this case, because lookups 162/// may involve partial pattern matches, rather than exact matches. 163class FactSet { 164private: 165 typedef SmallVector<FactID, 4> FactVec; 166 167 FactVec FactIDs; 168 169public: 170 typedef FactVec::iterator iterator; 171 typedef FactVec::const_iterator const_iterator; 172 173 iterator begin() { return FactIDs.begin(); } 174 const_iterator begin() const { return FactIDs.begin(); } 175 176 iterator end() { return FactIDs.end(); } 177 const_iterator end() const { return FactIDs.end(); } 178 179 bool isEmpty() const { return FactIDs.size() == 0; } 180 181 // Return true if the set contains only negative facts 182 bool isEmpty(FactManager &FactMan) const { 183 for (FactID FID : *this) { 184 if (!FactMan[FID].negative()) 185 return false; 186 } 187 return true; 188 } 189 190 void addLockByID(FactID ID) { FactIDs.push_back(ID); } 191 192 FactID addLock(FactManager &FM, std::unique_ptr<FactEntry> Entry) { 193 FactID F = FM.newFact(std::move(Entry)); 194 FactIDs.push_back(F); 195 return F; 196 } 197 198 bool removeLock(FactManager& FM, const CapabilityExpr &CapE) { 199 unsigned n = FactIDs.size(); 200 if (n == 0) 201 return false; 202 203 for (unsigned i = 0; i < n-1; ++i) { 204 if (FM[FactIDs[i]].matches(CapE)) { 205 FactIDs[i] = FactIDs[n-1]; 206 FactIDs.pop_back(); 207 return true; 208 } 209 } 210 if (FM[FactIDs[n-1]].matches(CapE)) { 211 FactIDs.pop_back(); 212 return true; 213 } 214 return false; 215 } 216 217 iterator findLockIter(FactManager &FM, const CapabilityExpr &CapE) { 218 return std::find_if(begin(), end(), [&](FactID ID) { 219 return FM[ID].matches(CapE); 220 }); 221 } 222 223 FactEntry *findLock(FactManager &FM, const CapabilityExpr &CapE) const { 224 auto I = std::find_if(begin(), end(), [&](FactID ID) { 225 return FM[ID].matches(CapE); 226 }); 227 return I != end() ? &FM[*I] : nullptr; 228 } 229 230 FactEntry *findLockUniv(FactManager &FM, const CapabilityExpr &CapE) const { 231 auto I = std::find_if(begin(), end(), [&](FactID ID) -> bool { 232 return FM[ID].matchesUniv(CapE); 233 }); 234 return I != end() ? &FM[*I] : nullptr; 235 } 236 237 FactEntry *findPartialMatch(FactManager &FM, 238 const CapabilityExpr &CapE) const { 239 auto I = std::find_if(begin(), end(), [&](FactID ID) -> bool { 240 return FM[ID].partiallyMatches(CapE); 241 }); 242 return I != end() ? &FM[*I] : nullptr; 243 } 244 245 bool containsMutexDecl(FactManager &FM, const ValueDecl* Vd) const { 246 auto I = std::find_if(begin(), end(), [&](FactID ID) -> bool { 247 return FM[ID].valueDecl() == Vd; 248 }); 249 return I != end(); 250 } 251}; 252 253 254class ThreadSafetyAnalyzer; 255 256 257class BeforeSet { 258private: 259 typedef SmallVector<const ValueDecl*, 4> BeforeVect; 260 261 struct BeforeInfo { 262 BeforeInfo() : Vect(nullptr), Visited(false) { } 263 BeforeInfo(BeforeInfo &&O) 264 : Vect(std::move(O.Vect)), Visited(O.Visited) 265 {} 266 267 std::unique_ptr<BeforeVect> Vect; 268 int Visited; 269 }; 270 271 typedef llvm::DenseMap<const ValueDecl*, BeforeInfo> BeforeMap; 272 typedef llvm::DenseMap<const ValueDecl*, bool> CycleMap; 273 274public: 275 BeforeSet() { } 276 277 BeforeInfo* insertAttrExprs(const ValueDecl* Vd, 278 ThreadSafetyAnalyzer& Analyzer); 279 280 void checkBeforeAfter(const ValueDecl* Vd, 281 const FactSet& FSet, 282 ThreadSafetyAnalyzer& Analyzer, 283 SourceLocation Loc, StringRef CapKind); 284 285private: 286 BeforeMap BMap; 287 CycleMap CycMap; 288}; 289 290 291 292typedef llvm::ImmutableMap<const NamedDecl*, unsigned> LocalVarContext; 293class LocalVariableMap; 294 295/// A side (entry or exit) of a CFG node. 296enum 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. 301struct 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 318private: 319 CFGBlockInfo(LocalVarContext EmptyCtx) 320 : EntryContext(EmptyCtx), ExitContext(EmptyCtx), Reachable(false) 321 { } 322 323public: 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. 342class LocalVariableMap { 343public: 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 373private: 374 Context::Factory ContextFactory; 375 std::vector<VarDefinition> VarDefinitions; 376 std::vector<unsigned> CtxIndices; 377 std::vector<std::pair<Stmt*, Context> > SavedContexts; 378 379public: 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 473protected: 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. 542CFGBlockInfo CFGBlockInfo::getEmptyBlockInfo(LocalVariableMap &M) { 543 return CFGBlockInfo(M.getEmptyContext()); 544} 545 546 547/// Visitor which builds a LocalVariableMap 548class VarMapBuilder : public StmtVisitor<VarMapBuilder> { 549public: 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 562void 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 582void 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. 606LocalVariableMap::Context 607LocalVariableMap::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.) 623LocalVariableMap::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. 633void 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// 684void 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. 769static 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 811class LockableFactEntry : public FactEntry { 812private: 813 bool Managed; ///< managed by ScopedLockable object 814 815public: 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 842class ScopedLockableFactEntry : public FactEntry { 843private: 844 SmallVector<const til::SExpr *, 4> UnderlyingMutexes; 845 846public: 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. 904class ThreadSafetyAnalyzer { 905 friend class BuildLockset; 906 friend class 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 920public: 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 963 964 965/// Process acquired_before and acquired_after attributes on Vd. 966BeforeSet::BeforeInfo* BeforeSet::insertAttrExprs(const ValueDecl* Vd, 967 ThreadSafetyAnalyzer& Analyzer) { 968 // Create a new entry for Vd. 969 auto& Entry = BMap.FindAndConstruct(Vd); 970 BeforeInfo* Info = &Entry.second; 971 BeforeVect* Bv = nullptr; 972 973 for (Attr* At : Vd->attrs()) { 974 switch (At->getKind()) { 975 case attr::AcquiredBefore: { 976 auto *A = cast<AcquiredBeforeAttr>(At); 977 978 // Create a new BeforeVect for Vd if necessary. 979 if (!Bv) { 980 Bv = new BeforeVect; 981 Info->Vect.reset(Bv); 982 } 983 // Read exprs from the attribute, and add them to BeforeVect. 984 for (const auto *Arg : A->args()) { 985 CapabilityExpr Cp = 986 Analyzer.SxBuilder.translateAttrExpr(Arg, nullptr); 987 if (const ValueDecl *Cpvd = Cp.valueDecl()) { 988 Bv->push_back(Cpvd); 989 auto It = BMap.find(Cpvd); 990 if (It == BMap.end()) 991 insertAttrExprs(Cpvd, Analyzer); 992 } 993 } 994 break; 995 } 996 case attr::AcquiredAfter: { 997 auto *A = cast<AcquiredAfterAttr>(At); 998 999 // Read exprs from the attribute, and add them to BeforeVect. 1000 for (const auto *Arg : A->args()) { 1001 CapabilityExpr Cp = 1002 Analyzer.SxBuilder.translateAttrExpr(Arg, nullptr); 1003 if (const ValueDecl *ArgVd = Cp.valueDecl()) { 1004 // Get entry for mutex listed in attribute 1005 BeforeInfo* ArgInfo; 1006 auto It = BMap.find(ArgVd); 1007 if (It == BMap.end()) 1008 ArgInfo = insertAttrExprs(ArgVd, Analyzer); 1009 else 1010 ArgInfo = &It->second; 1011 1012 // Create a new BeforeVect if necessary. 1013 BeforeVect* ArgBv = ArgInfo->Vect.get(); 1014 if (!ArgBv) { 1015 ArgBv = new BeforeVect; 1016 ArgInfo->Vect.reset(ArgBv); 1017 } 1018 ArgBv->push_back(Vd); 1019 } 1020 } 1021 break; 1022 } 1023 default: 1024 break; 1025 } 1026 } 1027 1028 return Info; 1029} 1030 1031 1032/// Return true if any mutexes in FSet are in the acquired_before set of Vd. 1033void BeforeSet::checkBeforeAfter(const ValueDecl* StartVd, 1034 const FactSet& FSet, 1035 ThreadSafetyAnalyzer& Analyzer, 1036 SourceLocation Loc, StringRef CapKind) { 1037 SmallVector<BeforeInfo*, 8> InfoVect; 1038 1039 // Do a depth-first traversal of Vd. 1040 // Return true if there are cycles. 1041 std::function<bool (const ValueDecl*)> traverse = [&](const ValueDecl* Vd) { 1042 if (!Vd) 1043 return false; 1044 1045 BeforeSet::BeforeInfo* Info; 1046 auto It = BMap.find(Vd); 1047 if (It == BMap.end()) 1048 Info = insertAttrExprs(Vd, Analyzer); 1049 else 1050 Info = &It->second; 1051 1052 if (Info->Visited == 1) 1053 return true; 1054 1055 if (Info->Visited == 2) 1056 return false; 1057 1058 BeforeVect* Bv = Info->Vect.get(); 1059 if (!Bv) 1060 return false; 1061 1062 InfoVect.push_back(Info); 1063 Info->Visited = 1; 1064 for (auto *Vdb : *Bv) { 1065 // Exclude mutexes in our immediate before set. 1066 if (FSet.containsMutexDecl(Analyzer.FactMan, Vdb)) { 1067 StringRef L1 = StartVd->getName(); 1068 StringRef L2 = Vdb->getName(); 1069 Analyzer.Handler.handleLockAcquiredBefore(CapKind, L1, L2, Loc); 1070 } 1071 // Transitively search other before sets, and warn on cycles. 1072 if (traverse(Vdb)) { 1073 if (CycMap.find(Vd) == CycMap.end()) { 1074 CycMap.insert(std::make_pair(Vd, true)); 1075 StringRef L1 = Vd->getName(); 1076 Analyzer.Handler.handleBeforeAfterCycle(L1, Vd->getLocation()); 1077 } 1078 } 1079 } 1080 Info->Visited = 2; 1081 return false; 1082 }; 1083 1084 traverse(StartVd); 1085 1086 for (auto* Info : InfoVect) 1087 Info->Visited = 0; 1088} 1089 1090 1091 1092/// \brief Gets the value decl pointer from DeclRefExprs or MemberExprs. 1093static const ValueDecl *getValueDecl(const Expr *Exp) { 1094 if (const auto *CE = dyn_cast<ImplicitCastExpr>(Exp)) 1095 return getValueDecl(CE->getSubExpr()); 1096 1097 if (const auto *DR = dyn_cast<DeclRefExpr>(Exp)) 1098 return DR->getDecl(); 1099 1100 if (const auto *ME = dyn_cast<MemberExpr>(Exp)) 1101 return ME->getMemberDecl(); 1102 1103 return nullptr; 1104} 1105 1106template <typename Ty> 1107class 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 1117public: 1118 static const bool value = sizeof(test<Ty>(nullptr)) == sizeof(yes); 1119}; 1120 1121static StringRef ClassifyDiagnostic(const CapabilityAttr *A) { 1122 return A->getName(); 1123} 1124 1125static StringRef ClassifyDiagnostic(QualType VDT) { 1126 // We need to look at the declaration of the type of the value to determine 1127 // which it is. The type should either be a record or a typedef, or a pointer 1128 // or reference thereof. 1129 if (const auto *RT = VDT->getAs<RecordType>()) { 1130 if (const auto *RD = RT->getDecl()) 1131 if (const auto *CA = RD->getAttr<CapabilityAttr>()) 1132 return ClassifyDiagnostic(CA); 1133 } else if (const auto *TT = VDT->getAs<TypedefType>()) { 1134 if (const auto *TD = TT->getDecl()) 1135 if (const auto *CA = TD->getAttr<CapabilityAttr>()) 1136 return ClassifyDiagnostic(CA); 1137 } else if (VDT->isPointerType() || VDT->isReferenceType()) 1138 return ClassifyDiagnostic(VDT->getPointeeType()); 1139 1140 return "mutex"; 1141} 1142 1143static StringRef ClassifyDiagnostic(const ValueDecl *VD) { 1144 assert(VD && "No ValueDecl passed"); 1145 1146 // The ValueDecl is the declaration of a mutex or role (hopefully). 1147 return ClassifyDiagnostic(VD->getType()); 1148} 1149 1150template <typename AttrTy> 1151static typename std::enable_if<!has_arg_iterator_range<AttrTy>::value, 1152 StringRef>::type 1153ClassifyDiagnostic(const AttrTy *A) { 1154 if (const ValueDecl *VD = getValueDecl(A->getArg())) 1155 return ClassifyDiagnostic(VD); 1156 return "mutex"; 1157} 1158 1159template <typename AttrTy> 1160static typename std::enable_if<has_arg_iterator_range<AttrTy>::value, 1161 StringRef>::type 1162ClassifyDiagnostic(const AttrTy *A) { 1163 for (const auto *Arg : A->args()) { 1164 if (const ValueDecl *VD = getValueDecl(Arg)) 1165 return ClassifyDiagnostic(VD); 1166 } 1167 return "mutex"; 1168} 1169 1170 1171inline bool ThreadSafetyAnalyzer::inCurrentScope(const CapabilityExpr &CapE) { 1172 if (!CurrentMethod) 1173 return false; 1174 if (auto *P = dyn_cast_or_null<til::Project>(CapE.sexpr())) { 1175 auto *VD = P->clangDecl(); 1176 if (VD) 1177 return VD->getDeclContext() == CurrentMethod->getDeclContext(); 1178 } 1179 return false; 1180} 1181 1182 1183/// \brief Add a new lock to the lockset, warning if the lock is already there. 1184/// \param ReqAttr -- true if this is part of an initial Requires attribute. 1185void ThreadSafetyAnalyzer::addLock(FactSet &FSet, 1186 std::unique_ptr<FactEntry> Entry, 1187 StringRef DiagKind, bool ReqAttr) { 1188 if (Entry->shouldIgnore()) 1189 return; 1190 1191 if (!ReqAttr && !Entry->negative()) { 1192 // look for the negative capability, and remove it from the fact set. 1193 CapabilityExpr NegC = !*Entry; 1194 FactEntry *Nen = FSet.findLock(FactMan, NegC); 1195 if (Nen) { 1196 FSet.removeLock(FactMan, NegC); 1197 } 1198 else { 1199 if (inCurrentScope(*Entry) && !Entry->asserted()) 1200 Handler.handleNegativeNotHeld(DiagKind, Entry->toString(), 1201 NegC.toString(), Entry->loc()); 1202 } 1203 } 1204 1205 // Check before/after constraints 1206 if (Handler.issueBetaWarnings() && 1207 !Entry->asserted() && !Entry->declared()) { 1208 GlobalBeforeSet->checkBeforeAfter(Entry->valueDecl(), FSet, *this, 1209 Entry->loc(), DiagKind); 1210 } 1211 1212 // FIXME: Don't always warn when we have support for reentrant locks. 1213 if (FSet.findLock(FactMan, *Entry)) { 1214 if (!Entry->asserted()) 1215 Handler.handleDoubleLock(DiagKind, Entry->toString(), Entry->loc()); 1216 } else { 1217 FSet.addLock(FactMan, std::move(Entry)); 1218 } 1219} 1220 1221 1222/// \brief Remove a lock from the lockset, warning if the lock is not there. 1223/// \param UnlockLoc The source location of the unlock (only used in error msg) 1224void ThreadSafetyAnalyzer::removeLock(FactSet &FSet, const CapabilityExpr &Cp, 1225 SourceLocation UnlockLoc, 1226 bool FullyRemove, LockKind ReceivedKind, 1227 StringRef DiagKind) { 1228 if (Cp.shouldIgnore()) 1229 return; 1230 1231 const FactEntry *LDat = FSet.findLock(FactMan, Cp); 1232 if (!LDat) { 1233 Handler.handleUnmatchedUnlock(DiagKind, Cp.toString(), UnlockLoc); 1234 return; 1235 } 1236 1237 // Generic lock removal doesn't care about lock kind mismatches, but 1238 // otherwise diagnose when the lock kinds are mismatched. 1239 if (ReceivedKind != LK_Generic && LDat->kind() != ReceivedKind) { 1240 Handler.handleIncorrectUnlockKind(DiagKind, Cp.toString(), 1241 LDat->kind(), ReceivedKind, UnlockLoc); 1242 } 1243 1244 LDat->handleUnlock(FSet, FactMan, Cp, UnlockLoc, FullyRemove, Handler, 1245 DiagKind); 1246} 1247 1248 1249/// \brief Extract the list of mutexIDs from the attribute on an expression, 1250/// and push them onto Mtxs, discarding any duplicates. 1251template <typename AttrType> 1252void ThreadSafetyAnalyzer::getMutexIDs(CapExprSet &Mtxs, AttrType *Attr, 1253 Expr *Exp, const NamedDecl *D, 1254 VarDecl *SelfDecl) { 1255 if (Attr->args_size() == 0) { 1256 // The mutex held is the "this" object. 1257 CapabilityExpr Cp = SxBuilder.translateAttrExpr(nullptr, D, Exp, SelfDecl); 1258 if (Cp.isInvalid()) { 1259 warnInvalidLock(Handler, nullptr, D, Exp, ClassifyDiagnostic(Attr)); 1260 return; 1261 } 1262 //else 1263 if (!Cp.shouldIgnore()) 1264 Mtxs.push_back_nodup(Cp); 1265 return; 1266 } 1267 1268 for (const auto *Arg : Attr->args()) { 1269 CapabilityExpr Cp = SxBuilder.translateAttrExpr(Arg, D, Exp, SelfDecl); 1270 if (Cp.isInvalid()) { 1271 warnInvalidLock(Handler, nullptr, D, Exp, ClassifyDiagnostic(Attr)); 1272 continue; 1273 } 1274 //else 1275 if (!Cp.shouldIgnore()) 1276 Mtxs.push_back_nodup(Cp); 1277 } 1278} 1279 1280 1281/// \brief Extract the list of mutexIDs from a trylock attribute. If the 1282/// trylock applies to the given edge, then push them onto Mtxs, discarding 1283/// any duplicates. 1284template <class AttrType> 1285void ThreadSafetyAnalyzer::getMutexIDs(CapExprSet &Mtxs, AttrType *Attr, 1286 Expr *Exp, const NamedDecl *D, 1287 const CFGBlock *PredBlock, 1288 const CFGBlock *CurrBlock, 1289 Expr *BrE, bool Neg) { 1290 // Find out which branch has the lock 1291 bool branch = false; 1292 if (CXXBoolLiteralExpr *BLE = dyn_cast_or_null<CXXBoolLiteralExpr>(BrE)) 1293 branch = BLE->getValue(); 1294 else if (IntegerLiteral *ILE = dyn_cast_or_null<IntegerLiteral>(BrE)) 1295 branch = ILE->getValue().getBoolValue(); 1296 1297 int branchnum = branch ? 0 : 1; 1298 if (Neg) 1299 branchnum = !branchnum; 1300 1301 // If we've taken the trylock branch, then add the lock 1302 int i = 0; 1303 for (CFGBlock::const_succ_iterator SI = PredBlock->succ_begin(), 1304 SE = PredBlock->succ_end(); SI != SE && i < 2; ++SI, ++i) { 1305 if (*SI == CurrBlock && i == branchnum) 1306 getMutexIDs(Mtxs, Attr, Exp, D); 1307 } 1308} 1309 1310 1311bool 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(...)) 1331const 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. 1393void 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/// \brief We use this class to visit different types of expressions in 1457/// CFGBlocks, and build up the lockset. 1458/// An expression may cause us to add or remove locks from the lockset, or else 1459/// output error messages related to missing locks. 1460/// FIXME: In future, we may be able to not inherit from a visitor. 1461class BuildLockset : public StmtVisitor<BuildLockset> { 1462 friend class ThreadSafetyAnalyzer; 1463 1464 ThreadSafetyAnalyzer *Analyzer; 1465 FactSet FSet; 1466 LocalVariableMap::Context LVarCtx; 1467 unsigned CtxIndex; 1468 1469 // helper functions 1470 void warnIfMutexNotHeld(const NamedDecl *D, const Expr *Exp, AccessKind AK, 1471 Expr *MutexExp, ProtectedOperationKind POK, 1472 StringRef DiagKind, SourceLocation Loc); 1473 void warnIfMutexHeld(const NamedDecl *D, const Expr *Exp, Expr *MutexExp, 1474 StringRef DiagKind); 1475 1476 void checkAccess(const Expr *Exp, AccessKind AK, 1477 ProtectedOperationKind POK = POK_VarAccess); 1478 void checkPtAccess(const Expr *Exp, AccessKind AK, 1479 ProtectedOperationKind POK = POK_VarAccess); 1480 1481 void handleCall(Expr *Exp, const NamedDecl *D, VarDecl *VD = nullptr); 1482 1483public: 1484 BuildLockset(ThreadSafetyAnalyzer *Anlzr, CFGBlockInfo &Info) 1485 : StmtVisitor<BuildLockset>(), 1486 Analyzer(Anlzr), 1487 FSet(Info.EntrySet), 1488 LVarCtx(Info.EntryContext), 1489 CtxIndex(Info.EntryIndex) 1490 {} 1491 1492 void VisitUnaryOperator(UnaryOperator *UO); 1493 void VisitBinaryOperator(BinaryOperator *BO); 1494 void VisitCastExpr(CastExpr *CE); 1495 void VisitCallExpr(CallExpr *Exp); 1496 void VisitCXXConstructExpr(CXXConstructExpr *Exp); 1497 void VisitDeclStmt(DeclStmt *S); 1498}; 1499 1500 1501/// \brief Warn if the LSet does not contain a lock sufficient to protect access 1502/// of at least the passed in AccessKind. 1503void BuildLockset::warnIfMutexNotHeld(const NamedDecl *D, const Expr *Exp, 1504 AccessKind AK, Expr *MutexExp, 1505 ProtectedOperationKind POK, 1506 StringRef DiagKind, SourceLocation Loc) { 1507 LockKind LK = getLockKindFromAccessKind(AK); 1508 1509 CapabilityExpr Cp = Analyzer->SxBuilder.translateAttrExpr(MutexExp, D, Exp); 1510 if (Cp.isInvalid()) { 1511 warnInvalidLock(Analyzer->Handler, MutexExp, D, Exp, DiagKind); 1512 return; 1513 } else if (Cp.shouldIgnore()) { 1514 return; 1515 } 1516 1517 if (Cp.negative()) { 1518 // Negative capabilities act like locks excluded 1519 FactEntry *LDat = FSet.findLock(Analyzer->FactMan, !Cp); 1520 if (LDat) { 1521 Analyzer->Handler.handleFunExcludesLock( 1522 DiagKind, D->getNameAsString(), (!Cp).toString(), Loc); 1523 return; 1524 } 1525 1526 // If this does not refer to a negative capability in the same class, 1527 // then stop here. 1528 if (!Analyzer->inCurrentScope(Cp)) 1529 return; 1530 1531 // Otherwise the negative requirement must be propagated to the caller. 1532 LDat = FSet.findLock(Analyzer->FactMan, Cp); 1533 if (!LDat) { 1534 Analyzer->Handler.handleMutexNotHeld("", D, POK, Cp.toString(), 1535 LK_Shared, Loc); 1536 } 1537 return; 1538 } 1539 1540 FactEntry* LDat = FSet.findLockUniv(Analyzer->FactMan, Cp); 1541 bool NoError = true; 1542 if (!LDat) { 1543 // No exact match found. Look for a partial match. 1544 LDat = FSet.findPartialMatch(Analyzer->FactMan, Cp); 1545 if (LDat) { 1546 // Warn that there's no precise match. 1547 std::string PartMatchStr = LDat->toString(); 1548 StringRef PartMatchName(PartMatchStr); 1549 Analyzer->Handler.handleMutexNotHeld(DiagKind, D, POK, Cp.toString(), 1550 LK, Loc, &PartMatchName); 1551 } else { 1552 // Warn that there's no match at all. 1553 Analyzer->Handler.handleMutexNotHeld(DiagKind, D, POK, Cp.toString(), 1554 LK, Loc); 1555 } 1556 NoError = false; 1557 } 1558 // Make sure the mutex we found is the right kind. 1559 if (NoError && LDat && !LDat->isAtLeast(LK)) { 1560 Analyzer->Handler.handleMutexNotHeld(DiagKind, D, POK, Cp.toString(), 1561 LK, Loc); 1562 } 1563} 1564 1565/// \brief Warn if the LSet contains the given lock. 1566void BuildLockset::warnIfMutexHeld(const NamedDecl *D, const Expr *Exp, 1567 Expr *MutexExp, StringRef DiagKind) { 1568 CapabilityExpr Cp = Analyzer->SxBuilder.translateAttrExpr(MutexExp, D, Exp); 1569 if (Cp.isInvalid()) { 1570 warnInvalidLock(Analyzer->Handler, MutexExp, D, Exp, DiagKind); 1571 return; 1572 } else if (Cp.shouldIgnore()) { 1573 return; 1574 } 1575 1576 FactEntry* LDat = FSet.findLock(Analyzer->FactMan, Cp); 1577 if (LDat) { 1578 Analyzer->Handler.handleFunExcludesLock( 1579 DiagKind, D->getNameAsString(), Cp.toString(), Exp->getExprLoc()); 1580 } 1581} 1582 1583/// \brief Checks guarded_by and pt_guarded_by attributes. 1584/// Whenever we identify an access (read or write) to a DeclRefExpr that is 1585/// marked with guarded_by, we must ensure the appropriate mutexes are held. 1586/// Similarly, we check if the access is to an expression that dereferences 1587/// a pointer marked with pt_guarded_by. 1588void BuildLockset::checkAccess(const Expr *Exp, AccessKind AK, 1589 ProtectedOperationKind POK) { 1590 Exp = Exp->IgnoreParenCasts(); 1591 1592 SourceLocation Loc = Exp->getExprLoc(); 1593 1594 // Local variables of reference type cannot be re-assigned; 1595 // map them to their initializer. 1596 while (const auto *DRE = dyn_cast<DeclRefExpr>(Exp)) { 1597 const auto *VD = dyn_cast<VarDecl>(DRE->getDecl()->getCanonicalDecl()); 1598 if (VD && VD->isLocalVarDecl() && VD->getType()->isReferenceType()) { 1599 if (const auto *E = VD->getInit()) { 1600 Exp = E; 1601 continue; 1602 } 1603 } 1604 break; 1605 } 1606 1607 if (const UnaryOperator *UO = dyn_cast<UnaryOperator>(Exp)) { 1608 // For dereferences 1609 if (UO->getOpcode() == clang::UO_Deref) 1610 checkPtAccess(UO->getSubExpr(), AK, POK); 1611 return; 1612 } 1613 1614 if (const ArraySubscriptExpr *AE = dyn_cast<ArraySubscriptExpr>(Exp)) { 1615 checkPtAccess(AE->getLHS(), AK, POK); 1616 return; 1617 } 1618 1619 if (const MemberExpr *ME = dyn_cast<MemberExpr>(Exp)) { 1620 if (ME->isArrow()) 1621 checkPtAccess(ME->getBase(), AK, POK); 1622 else 1623 checkAccess(ME->getBase(), AK, POK); 1624 } 1625 1626 const ValueDecl *D = getValueDecl(Exp); 1627 if (!D || !D->hasAttrs()) 1628 return; 1629 1630 if (D->hasAttr<GuardedVarAttr>() && FSet.isEmpty(Analyzer->FactMan)) { 1631 Analyzer->Handler.handleNoMutexHeld("mutex", D, POK, AK, Loc); 1632 } 1633 1634 for (const auto *I : D->specific_attrs<GuardedByAttr>()) 1635 warnIfMutexNotHeld(D, Exp, AK, I->getArg(), POK, 1636 ClassifyDiagnostic(I), Loc); 1637} 1638 1639 1640/// \brief Checks pt_guarded_by and pt_guarded_var attributes. 1641/// POK is the same operationKind that was passed to checkAccess. 1642void BuildLockset::checkPtAccess(const Expr *Exp, AccessKind AK, 1643 ProtectedOperationKind POK) { 1644 while (true) { 1645 if (const ParenExpr *PE = dyn_cast<ParenExpr>(Exp)) { 1646 Exp = PE->getSubExpr(); 1647 continue; 1648 } 1649 if (const CastExpr *CE = dyn_cast<CastExpr>(Exp)) { 1650 if (CE->getCastKind() == CK_ArrayToPointerDecay) { 1651 // If it's an actual array, and not a pointer, then it's elements 1652 // are protected by GUARDED_BY, not PT_GUARDED_BY; 1653 checkAccess(CE->getSubExpr(), AK, POK); 1654 return; 1655 } 1656 Exp = CE->getSubExpr(); 1657 continue; 1658 } 1659 break; 1660 } 1661 1662 // Pass by reference warnings are under a different flag. 1663 ProtectedOperationKind PtPOK = POK_VarDereference; 1664 if (POK == POK_PassByRef) PtPOK = POK_PtPassByRef; 1665 1666 const ValueDecl *D = getValueDecl(Exp); 1667 if (!D || !D->hasAttrs()) 1668 return; 1669 1670 if (D->hasAttr<PtGuardedVarAttr>() && FSet.isEmpty(Analyzer->FactMan)) 1671 Analyzer->Handler.handleNoMutexHeld("mutex", D, PtPOK, AK, 1672 Exp->getExprLoc()); 1673 1674 for (auto const *I : D->specific_attrs<PtGuardedByAttr>()) 1675 warnIfMutexNotHeld(D, Exp, AK, I->getArg(), PtPOK, 1676 ClassifyDiagnostic(I), Exp->getExprLoc()); 1677} 1678 1679/// \brief Process a function call, method call, constructor call, 1680/// or destructor call. This involves looking at the attributes on the 1681/// corresponding function/method/constructor/destructor, issuing warnings, 1682/// and updating the locksets accordingly. 1683/// 1684/// FIXME: For classes annotated with one of the guarded annotations, we need 1685/// to treat const method calls as reads and non-const method calls as writes, 1686/// and check that the appropriate locks are held. Non-const method calls with 1687/// the same signature as const method calls can be also treated as reads. 1688/// 1689void BuildLockset::handleCall(Expr *Exp, const NamedDecl *D, VarDecl *VD) { 1690 SourceLocation Loc = Exp->getExprLoc(); 1691 CapExprSet ExclusiveLocksToAdd, SharedLocksToAdd; 1692 CapExprSet ExclusiveLocksToRemove, SharedLocksToRemove, GenericLocksToRemove; 1693 CapExprSet ScopedExclusiveReqs, ScopedSharedReqs; 1694 StringRef CapDiagKind = "mutex"; 1695 1696 // Figure out if we're calling the constructor of scoped lockable class 1697 bool isScopedVar = false; 1698 if (VD) { 1699 if (const CXXConstructorDecl *CD = dyn_cast<const CXXConstructorDecl>(D)) { 1700 const CXXRecordDecl* PD = CD->getParent(); 1701 if (PD && PD->hasAttr<ScopedLockableAttr>()) 1702 isScopedVar = true; 1703 } 1704 } 1705 1706 for(Attr *Atconst : D->attrs()) { 1707 Attr* At = const_cast<Attr*>(Atconst); 1708 switch (At->getKind()) { 1709 // When we encounter a lock function, we need to add the lock to our 1710 // lockset. 1711 case attr::AcquireCapability: { 1712 auto *A = cast<AcquireCapabilityAttr>(At); 1713 Analyzer->getMutexIDs(A->isShared() ? SharedLocksToAdd 1714 : ExclusiveLocksToAdd, 1715 A, Exp, D, VD); 1716 1717 CapDiagKind = ClassifyDiagnostic(A); 1718 break; 1719 } 1720 1721 // An assert will add a lock to the lockset, but will not generate 1722 // a warning if it is already there, and will not generate a warning 1723 // if it is not removed. 1724 case attr::AssertExclusiveLock: { 1725 AssertExclusiveLockAttr *A = cast<AssertExclusiveLockAttr>(At); 1726 1727 CapExprSet AssertLocks; 1728 Analyzer->getMutexIDs(AssertLocks, A, Exp, D, VD); 1729 for (const auto &AssertLock : AssertLocks) 1730 Analyzer->addLock(FSet, 1731 llvm::make_unique<LockableFactEntry>( 1732 AssertLock, LK_Exclusive, Loc, false, true), 1733 ClassifyDiagnostic(A)); 1734 break; 1735 } 1736 case attr::AssertSharedLock: { 1737 AssertSharedLockAttr *A = cast<AssertSharedLockAttr>(At); 1738 1739 CapExprSet AssertLocks; 1740 Analyzer->getMutexIDs(AssertLocks, A, Exp, D, VD); 1741 for (const auto &AssertLock : AssertLocks) 1742 Analyzer->addLock(FSet, llvm::make_unique<LockableFactEntry>( 1743 AssertLock, LK_Shared, Loc, false, true), 1744 ClassifyDiagnostic(A)); 1745 break; 1746 } 1747 1748 // When we encounter an unlock function, we need to remove unlocked 1749 // mutexes from the lockset, and flag a warning if they are not there. 1750 case attr::ReleaseCapability: { 1751 auto *A = cast<ReleaseCapabilityAttr>(At); 1752 if (A->isGeneric()) 1753 Analyzer->getMutexIDs(GenericLocksToRemove, A, Exp, D, VD); 1754 else if (A->isShared()) 1755 Analyzer->getMutexIDs(SharedLocksToRemove, A, Exp, D, VD); 1756 else 1757 Analyzer->getMutexIDs(ExclusiveLocksToRemove, A, Exp, D, VD); 1758 1759 CapDiagKind = ClassifyDiagnostic(A); 1760 break; 1761 } 1762 1763 case attr::RequiresCapability: { 1764 RequiresCapabilityAttr *A = cast<RequiresCapabilityAttr>(At); 1765 for (auto *Arg : A->args()) { 1766 warnIfMutexNotHeld(D, Exp, A->isShared() ? AK_Read : AK_Written, Arg, 1767 POK_FunctionCall, ClassifyDiagnostic(A), 1768 Exp->getExprLoc()); 1769 // use for adopting a lock 1770 if (isScopedVar) { 1771 Analyzer->getMutexIDs(A->isShared() ? ScopedSharedReqs 1772 : ScopedExclusiveReqs, 1773 A, Exp, D, VD); 1774 } 1775 } 1776 break; 1777 } 1778 1779 case attr::LocksExcluded: { 1780 LocksExcludedAttr *A = cast<LocksExcludedAttr>(At); 1781 for (auto *Arg : A->args()) 1782 warnIfMutexHeld(D, Exp, Arg, ClassifyDiagnostic(A)); 1783 break; 1784 } 1785 1786 // Ignore attributes unrelated to thread-safety 1787 default: 1788 break; 1789 } 1790 } 1791 1792 // Add locks. 1793 for (const auto &M : ExclusiveLocksToAdd) 1794 Analyzer->addLock(FSet, llvm::make_unique<LockableFactEntry>( 1795 M, LK_Exclusive, Loc, isScopedVar), 1796 CapDiagKind); 1797 for (const auto &M : SharedLocksToAdd) 1798 Analyzer->addLock(FSet, llvm::make_unique<LockableFactEntry>( 1799 M, LK_Shared, Loc, isScopedVar), 1800 CapDiagKind); 1801 1802 if (isScopedVar) { 1803 // Add the managing object as a dummy mutex, mapped to the underlying mutex. 1804 SourceLocation MLoc = VD->getLocation(); 1805 DeclRefExpr DRE(VD, false, VD->getType(), VK_LValue, VD->getLocation()); 1806 // FIXME: does this store a pointer to DRE? 1807 CapabilityExpr Scp = Analyzer->SxBuilder.translateAttrExpr(&DRE, nullptr); 1808 1809 std::copy(ScopedExclusiveReqs.begin(), ScopedExclusiveReqs.end(), 1810 std::back_inserter(ExclusiveLocksToAdd)); 1811 std::copy(ScopedSharedReqs.begin(), ScopedSharedReqs.end(), 1812 std::back_inserter(SharedLocksToAdd)); 1813 Analyzer->addLock(FSet, 1814 llvm::make_unique<ScopedLockableFactEntry>( 1815 Scp, MLoc, ExclusiveLocksToAdd, SharedLocksToAdd), 1816 CapDiagKind); 1817 } 1818 1819 // Remove locks. 1820 // FIXME -- should only fully remove if the attribute refers to 'this'. 1821 bool Dtor = isa<CXXDestructorDecl>(D); 1822 for (const auto &M : ExclusiveLocksToRemove) 1823 Analyzer->removeLock(FSet, M, Loc, Dtor, LK_Exclusive, CapDiagKind); 1824 for (const auto &M : SharedLocksToRemove) 1825 Analyzer->removeLock(FSet, M, Loc, Dtor, LK_Shared, CapDiagKind); 1826 for (const auto &M : GenericLocksToRemove) 1827 Analyzer->removeLock(FSet, M, Loc, Dtor, LK_Generic, CapDiagKind); 1828} 1829 1830 1831/// \brief For unary operations which read and write a variable, we need to 1832/// check whether we hold any required mutexes. Reads are checked in 1833/// VisitCastExpr. 1834void BuildLockset::VisitUnaryOperator(UnaryOperator *UO) { 1835 switch (UO->getOpcode()) { 1836 case clang::UO_PostDec: 1837 case clang::UO_PostInc: 1838 case clang::UO_PreDec: 1839 case clang::UO_PreInc: { 1840 checkAccess(UO->getSubExpr(), AK_Written); 1841 break; 1842 } 1843 default: 1844 break; 1845 } 1846} 1847 1848/// For binary operations which assign to a variable (writes), we need to check 1849/// whether we hold any required mutexes. 1850/// FIXME: Deal with non-primitive types. 1851void BuildLockset::VisitBinaryOperator(BinaryOperator *BO) { 1852 if (!BO->isAssignmentOp()) 1853 return; 1854 1855 // adjust the context 1856 LVarCtx = Analyzer->LocalVarMap.getNextContext(CtxIndex, BO, LVarCtx); 1857 1858 checkAccess(BO->getLHS(), AK_Written); 1859} 1860 1861 1862/// Whenever we do an LValue to Rvalue cast, we are reading a variable and 1863/// need to ensure we hold any required mutexes. 1864/// FIXME: Deal with non-primitive types. 1865void BuildLockset::VisitCastExpr(CastExpr *CE) { 1866 if (CE->getCastKind() != CK_LValueToRValue) 1867 return; 1868 checkAccess(CE->getSubExpr(), AK_Read); 1869} 1870 1871 1872void BuildLockset::VisitCallExpr(CallExpr *Exp) { 1873 bool ExamineArgs = true; 1874 bool OperatorFun = false; 1875 1876 if (CXXMemberCallExpr *CE = dyn_cast<CXXMemberCallExpr>(Exp)) { 1877 MemberExpr *ME = dyn_cast<MemberExpr>(CE->getCallee()); 1878 // ME can be null when calling a method pointer 1879 CXXMethodDecl *MD = CE->getMethodDecl(); 1880 1881 if (ME && MD) { 1882 if (ME->isArrow()) { 1883 if (MD->isConst()) { 1884 checkPtAccess(CE->getImplicitObjectArgument(), AK_Read); 1885 } else { // FIXME -- should be AK_Written 1886 checkPtAccess(CE->getImplicitObjectArgument(), AK_Read); 1887 } 1888 } else { 1889 if (MD->isConst()) 1890 checkAccess(CE->getImplicitObjectArgument(), AK_Read); 1891 else // FIXME -- should be AK_Written 1892 checkAccess(CE->getImplicitObjectArgument(), AK_Read); 1893 } 1894 } 1895 } else if (CXXOperatorCallExpr *OE = dyn_cast<CXXOperatorCallExpr>(Exp)) { 1896 OperatorFun = true; 1897 1898 auto OEop = OE->getOperator(); 1899 switch (OEop) { 1900 case OO_Equal: { 1901 ExamineArgs = false; 1902 const Expr *Target = OE->getArg(0); 1903 const Expr *Source = OE->getArg(1); 1904 checkAccess(Target, AK_Written); 1905 checkAccess(Source, AK_Read); 1906 break; 1907 } 1908 case OO_Star: 1909 case OO_Arrow: 1910 case OO_Subscript: { 1911 const Expr *Obj = OE->getArg(0); 1912 checkAccess(Obj, AK_Read); 1913 if (!(OEop == OO_Star && OE->getNumArgs() > 1)) { 1914 // Grrr. operator* can be multiplication... 1915 checkPtAccess(Obj, AK_Read); 1916 } 1917 break; 1918 } 1919 default: { 1920 // TODO: get rid of this, and rely on pass-by-ref instead. 1921 const Expr *Obj = OE->getArg(0); 1922 checkAccess(Obj, AK_Read); 1923 break; 1924 } 1925 } 1926 } 1927 1928 1929 if (ExamineArgs) { 1930 if (FunctionDecl *FD = Exp->getDirectCallee()) { 1931 unsigned Fn = FD->getNumParams(); 1932 unsigned Cn = Exp->getNumArgs(); 1933 unsigned Skip = 0; 1934 1935 unsigned i = 0; 1936 if (OperatorFun) { 1937 if (isa<CXXMethodDecl>(FD)) { 1938 // First arg in operator call is implicit self argument, 1939 // and doesn't appear in the FunctionDecl. 1940 Skip = 1; 1941 Cn--; 1942 } else { 1943 // Ignore the first argument of operators; it's been checked above. 1944 i = 1; 1945 } 1946 } 1947 // Ignore default arguments 1948 unsigned n = (Fn < Cn) ? Fn : Cn; 1949 1950 for (; i < n; ++i) { 1951 ParmVarDecl* Pvd = FD->getParamDecl(i); 1952 Expr* Arg = Exp->getArg(i+Skip); 1953 QualType Qt = Pvd->getType(); 1954 if (Qt->isReferenceType()) 1955 checkAccess(Arg, AK_Read, POK_PassByRef); 1956 } 1957 } 1958 } 1959 1960 NamedDecl *D = dyn_cast_or_null<NamedDecl>(Exp->getCalleeDecl()); 1961 if(!D || !D->hasAttrs()) 1962 return; 1963 handleCall(Exp, D); 1964} 1965 1966void BuildLockset::VisitCXXConstructExpr(CXXConstructExpr *Exp) { 1967 const CXXConstructorDecl *D = Exp->getConstructor(); 1968 if (D && D->isCopyConstructor()) { 1969 const Expr* Source = Exp->getArg(0); 1970 checkAccess(Source, AK_Read); 1971 } 1972 // FIXME -- only handles constructors in DeclStmt below. 1973} 1974 1975void BuildLockset::VisitDeclStmt(DeclStmt *S) { 1976 // adjust the context 1977 LVarCtx = Analyzer->LocalVarMap.getNextContext(CtxIndex, S, LVarCtx); 1978 1979 for (auto *D : S->getDeclGroup()) { 1980 if (VarDecl *VD = dyn_cast_or_null<VarDecl>(D)) { 1981 Expr *E = VD->getInit(); 1982 // handle constructors that involve temporaries 1983 if (ExprWithCleanups *EWC = dyn_cast_or_null<ExprWithCleanups>(E)) 1984 E = EWC->getSubExpr(); 1985 1986 if (CXXConstructExpr *CE = dyn_cast_or_null<CXXConstructExpr>(E)) { 1987 NamedDecl *CtorD = dyn_cast_or_null<NamedDecl>(CE->getConstructor()); 1988 if (!CtorD || !CtorD->hasAttrs()) 1989 return; 1990 handleCall(CE, CtorD, VD); 1991 } 1992 } 1993 } 1994} 1995 1996 1997 1998/// \brief Compute the intersection of two locksets and issue warnings for any 1999/// locks in the symmetric difference. 2000/// 2001/// This function is used at a merge point in the CFG when comparing the lockset 2002/// of each branch being merged. For example, given the following sequence: 2003/// A; if () then B; else C; D; we need to check that the lockset after B and C 2004/// are the same. In the event of a difference, we use the intersection of these 2005/// two locksets at the start of D. 2006/// 2007/// \param FSet1 The first lockset. 2008/// \param FSet2 The second lockset. 2009/// \param JoinLoc The location of the join point for error reporting 2010/// \param LEK1 The error message to report if a mutex is missing from LSet1 2011/// \param LEK2 The error message to report if a mutex is missing from Lset2 2012void ThreadSafetyAnalyzer::intersectAndWarn(FactSet &FSet1, 2013 const FactSet &FSet2, 2014 SourceLocation JoinLoc, 2015 LockErrorKind LEK1, 2016 LockErrorKind LEK2, 2017 bool Modify) { 2018 FactSet FSet1Orig = FSet1; 2019 2020 // Find locks in FSet2 that conflict or are not in FSet1, and warn. 2021 for (const auto &Fact : FSet2) { 2022 const FactEntry *LDat1 = nullptr; 2023 const FactEntry *LDat2 = &FactMan[Fact]; 2024 FactSet::iterator Iter1 = FSet1.findLockIter(FactMan, *LDat2); 2025 if (Iter1 != FSet1.end()) LDat1 = &FactMan[*Iter1]; 2026 2027 if (LDat1) { 2028 if (LDat1->kind() != LDat2->kind()) { 2029 Handler.handleExclusiveAndShared("mutex", LDat2->toString(), 2030 LDat2->loc(), LDat1->loc()); 2031 if (Modify && LDat1->kind() != LK_Exclusive) { 2032 // Take the exclusive lock, which is the one in FSet2. 2033 *Iter1 = Fact; 2034 } 2035 } 2036 else if (Modify && LDat1->asserted() && !LDat2->asserted()) { 2037 // The non-asserted lock in FSet2 is the one we want to track. 2038 *Iter1 = Fact; 2039 } 2040 } else { 2041 LDat2->handleRemovalFromIntersection(FSet2, FactMan, JoinLoc, LEK1, 2042 Handler); 2043 } 2044 } 2045 2046 // Find locks in FSet1 that are not in FSet2, and remove them. 2047 for (const auto &Fact : FSet1Orig) { 2048 const FactEntry *LDat1 = &FactMan[Fact]; 2049 const FactEntry *LDat2 = FSet2.findLock(FactMan, *LDat1); 2050 2051 if (!LDat2) { 2052 LDat1->handleRemovalFromIntersection(FSet1Orig, FactMan, JoinLoc, LEK2, 2053 Handler); 2054 if (Modify) 2055 FSet1.removeLock(FactMan, *LDat1); 2056 } 2057 } 2058} 2059 2060 2061// Return true if block B never continues to its successors. 2062inline bool neverReturns(const CFGBlock* B) { 2063 if (B->hasNoReturnElement()) 2064 return true; 2065 if (B->empty()) 2066 return false; 2067 2068 CFGElement Last = B->back(); 2069 if (Optional<CFGStmt> S = Last.getAs<CFGStmt>()) { 2070 if (isa<CXXThrowExpr>(S->getStmt())) 2071 return true; 2072 } 2073 return false; 2074} 2075 2076 2077/// \brief Check a function's CFG for thread-safety violations. 2078/// 2079/// We traverse the blocks in the CFG, compute the set of mutexes that are held 2080/// at the end of each block, and issue warnings for thread safety violations. 2081/// Each block in the CFG is traversed exactly once. 2082void ThreadSafetyAnalyzer::runAnalysis(AnalysisDeclContext &AC) { 2083 // TODO: this whole function needs be rewritten as a visitor for CFGWalker. 2084 // For now, we just use the walker to set things up. 2085 threadSafety::CFGWalker walker; 2086 if (!walker.init(AC)) 2087 return; 2088 2089 // AC.dumpCFG(true); 2090 // threadSafety::printSCFG(walker); 2091 2092 CFG *CFGraph = walker.getGraph(); 2093 const NamedDecl *D = walker.getDecl(); 2094 const FunctionDecl *CurrentFunction = dyn_cast<FunctionDecl>(D); 2095 CurrentMethod = dyn_cast<CXXMethodDecl>(D); 2096 2097 if (D->hasAttr<NoThreadSafetyAnalysisAttr>()) 2098 return; 2099 2100 // FIXME: Do something a bit more intelligent inside constructor and 2101 // destructor code. Constructors and destructors must assume unique access 2102 // to 'this', so checks on member variable access is disabled, but we should 2103 // still enable checks on other objects. 2104 if (isa<CXXConstructorDecl>(D)) 2105 return; // Don't check inside constructors. 2106 if (isa<CXXDestructorDecl>(D)) 2107 return; // Don't check inside destructors. 2108 2109 Handler.enterFunction(CurrentFunction); 2110 2111 BlockInfo.resize(CFGraph->getNumBlockIDs(), 2112 CFGBlockInfo::getEmptyBlockInfo(LocalVarMap)); 2113 2114 // We need to explore the CFG via a "topological" ordering. 2115 // That way, we will be guaranteed to have information about required 2116 // predecessor locksets when exploring a new block. 2117 const PostOrderCFGView *SortedGraph = walker.getSortedGraph(); 2118 PostOrderCFGView::CFGBlockSet VisitedBlocks(CFGraph); 2119 2120 // Mark entry block as reachable 2121 BlockInfo[CFGraph->getEntry().getBlockID()].Reachable = true; 2122 2123 // Compute SSA names for local variables 2124 LocalVarMap.traverseCFG(CFGraph, SortedGraph, BlockInfo); 2125 2126 // Fill in source locations for all CFGBlocks. 2127 findBlockLocations(CFGraph, SortedGraph, BlockInfo); 2128 2129 CapExprSet ExclusiveLocksAcquired; 2130 CapExprSet SharedLocksAcquired; 2131 CapExprSet LocksReleased; 2132 2133 // Add locks from exclusive_locks_required and shared_locks_required 2134 // to initial lockset. Also turn off checking for lock and unlock functions. 2135 // FIXME: is there a more intelligent way to check lock/unlock functions? 2136 if (!SortedGraph->empty() && D->hasAttrs()) { 2137 const CFGBlock *FirstBlock = *SortedGraph->begin(); 2138 FactSet &InitialLockset = BlockInfo[FirstBlock->getBlockID()].EntrySet; 2139 2140 CapExprSet ExclusiveLocksToAdd; 2141 CapExprSet SharedLocksToAdd; 2142 StringRef CapDiagKind = "mutex"; 2143 2144 SourceLocation Loc = D->getLocation(); 2145 for (const auto *Attr : D->attrs()) { 2146 Loc = Attr->getLocation(); 2147 if (const auto *A = dyn_cast<RequiresCapabilityAttr>(Attr)) { 2148 getMutexIDs(A->isShared() ? SharedLocksToAdd : ExclusiveLocksToAdd, A, 2149 nullptr, D); 2150 CapDiagKind = ClassifyDiagnostic(A); 2151 } else if (const auto *A = dyn_cast<ReleaseCapabilityAttr>(Attr)) { 2152 // UNLOCK_FUNCTION() is used to hide the underlying lock implementation. 2153 // We must ignore such methods. 2154 if (A->args_size() == 0) 2155 return; 2156 // FIXME -- deal with exclusive vs. shared unlock functions? 2157 getMutexIDs(ExclusiveLocksToAdd, A, nullptr, D); 2158 getMutexIDs(LocksReleased, A, nullptr, D); 2159 CapDiagKind = ClassifyDiagnostic(A); 2160 } else if (const auto *A = dyn_cast<AcquireCapabilityAttr>(Attr)) { 2161 if (A->args_size() == 0) 2162 return; 2163 getMutexIDs(A->isShared() ? SharedLocksAcquired 2164 : ExclusiveLocksAcquired, 2165 A, nullptr, D); 2166 CapDiagKind = ClassifyDiagnostic(A); 2167 } else if (isa<ExclusiveTrylockFunctionAttr>(Attr)) { 2168 // Don't try to check trylock functions for now 2169 return; 2170 } else if (isa<SharedTrylockFunctionAttr>(Attr)) { 2171 // Don't try to check trylock functions for now 2172 return; 2173 } 2174 } 2175 2176 // FIXME -- Loc can be wrong here. 2177 for (const auto &Mu : ExclusiveLocksToAdd) { 2178 auto Entry = llvm::make_unique<LockableFactEntry>(Mu, LK_Exclusive, Loc); 2179 Entry->setDeclared(true); 2180 addLock(InitialLockset, std::move(Entry), CapDiagKind, true); 2181 } 2182 for (const auto &Mu : SharedLocksToAdd) { 2183 auto Entry = llvm::make_unique<LockableFactEntry>(Mu, LK_Shared, Loc); 2184 Entry->setDeclared(true); 2185 addLock(InitialLockset, std::move(Entry), CapDiagKind, true); 2186 } 2187 } 2188 2189 for (const auto *CurrBlock : *SortedGraph) { 2190 int CurrBlockID = CurrBlock->getBlockID(); 2191 CFGBlockInfo *CurrBlockInfo = &BlockInfo[CurrBlockID]; 2192 2193 // Use the default initial lockset in case there are no predecessors. 2194 VisitedBlocks.insert(CurrBlock); 2195 2196 // Iterate through the predecessor blocks and warn if the lockset for all 2197 // predecessors is not the same. We take the entry lockset of the current 2198 // block to be the intersection of all previous locksets. 2199 // FIXME: By keeping the intersection, we may output more errors in future 2200 // for a lock which is not in the intersection, but was in the union. We 2201 // may want to also keep the union in future. As an example, let's say 2202 // the intersection contains Mutex L, and the union contains L and M. 2203 // Later we unlock M. At this point, we would output an error because we 2204 // never locked M; although the real error is probably that we forgot to 2205 // lock M on all code paths. Conversely, let's say that later we lock M. 2206 // In this case, we should compare against the intersection instead of the 2207 // union because the real error is probably that we forgot to unlock M on 2208 // all code paths. 2209 bool LocksetInitialized = false; 2210 SmallVector<CFGBlock *, 8> SpecialBlocks; 2211 for (CFGBlock::const_pred_iterator PI = CurrBlock->pred_begin(), 2212 PE = CurrBlock->pred_end(); PI != PE; ++PI) { 2213 2214 // if *PI -> CurrBlock is a back edge 2215 if (*PI == nullptr || !VisitedBlocks.alreadySet(*PI)) 2216 continue; 2217 2218 int PrevBlockID = (*PI)->getBlockID(); 2219 CFGBlockInfo *PrevBlockInfo = &BlockInfo[PrevBlockID]; 2220 2221 // Ignore edges from blocks that can't return. 2222 if (neverReturns(*PI) || !PrevBlockInfo->Reachable) 2223 continue; 2224 2225 // Okay, we can reach this block from the entry. 2226 CurrBlockInfo->Reachable = true; 2227 2228 // If the previous block ended in a 'continue' or 'break' statement, then 2229 // a difference in locksets is probably due to a bug in that block, rather 2230 // than in some other predecessor. In that case, keep the other 2231 // predecessor's lockset. 2232 if (const Stmt *Terminator = (*PI)->getTerminator()) { 2233 if (isa<ContinueStmt>(Terminator) || isa<BreakStmt>(Terminator)) { 2234 SpecialBlocks.push_back(*PI); 2235 continue; 2236 } 2237 } 2238 2239 FactSet PrevLockset; 2240 getEdgeLockset(PrevLockset, PrevBlockInfo->ExitSet, *PI, CurrBlock); 2241 2242 if (!LocksetInitialized) { 2243 CurrBlockInfo->EntrySet = PrevLockset; 2244 LocksetInitialized = true; 2245 } else { 2246 intersectAndWarn(CurrBlockInfo->EntrySet, PrevLockset, 2247 CurrBlockInfo->EntryLoc, 2248 LEK_LockedSomePredecessors); 2249 } 2250 } 2251 2252 // Skip rest of block if it's not reachable. 2253 if (!CurrBlockInfo->Reachable) 2254 continue; 2255 2256 // Process continue and break blocks. Assume that the lockset for the 2257 // resulting block is unaffected by any discrepancies in them. 2258 for (const auto *PrevBlock : SpecialBlocks) { 2259 int PrevBlockID = PrevBlock->getBlockID(); 2260 CFGBlockInfo *PrevBlockInfo = &BlockInfo[PrevBlockID]; 2261 2262 if (!LocksetInitialized) { 2263 CurrBlockInfo->EntrySet = PrevBlockInfo->ExitSet; 2264 LocksetInitialized = true; 2265 } else { 2266 // Determine whether this edge is a loop terminator for diagnostic 2267 // purposes. FIXME: A 'break' statement might be a loop terminator, but 2268 // it might also be part of a switch. Also, a subsequent destructor 2269 // might add to the lockset, in which case the real issue might be a 2270 // double lock on the other path. 2271 const Stmt *Terminator = PrevBlock->getTerminator(); 2272 bool IsLoop = Terminator && isa<ContinueStmt>(Terminator); 2273 2274 FactSet PrevLockset; 2275 getEdgeLockset(PrevLockset, PrevBlockInfo->ExitSet, 2276 PrevBlock, CurrBlock); 2277 2278 // Do not update EntrySet. 2279 intersectAndWarn(CurrBlockInfo->EntrySet, PrevLockset, 2280 PrevBlockInfo->ExitLoc, 2281 IsLoop ? LEK_LockedSomeLoopIterations 2282 : LEK_LockedSomePredecessors, 2283 false); 2284 } 2285 } 2286 2287 BuildLockset LocksetBuilder(this, *CurrBlockInfo); 2288 2289 // Visit all the statements in the basic block. 2290 for (CFGBlock::const_iterator BI = CurrBlock->begin(), 2291 BE = CurrBlock->end(); BI != BE; ++BI) { 2292 switch (BI->getKind()) { 2293 case CFGElement::Statement: { 2294 CFGStmt CS = BI->castAs<CFGStmt>(); 2295 LocksetBuilder.Visit(const_cast<Stmt*>(CS.getStmt())); 2296 break; 2297 } 2298 // Ignore BaseDtor, MemberDtor, and TemporaryDtor for now. 2299 case CFGElement::AutomaticObjectDtor: { 2300 CFGAutomaticObjDtor AD = BI->castAs<CFGAutomaticObjDtor>(); 2301 CXXDestructorDecl *DD = const_cast<CXXDestructorDecl *>( 2302 AD.getDestructorDecl(AC.getASTContext())); 2303 if (!DD->hasAttrs()) 2304 break; 2305 2306 // Create a dummy expression, 2307 VarDecl *VD = const_cast<VarDecl*>(AD.getVarDecl()); 2308 DeclRefExpr DRE(VD, false, VD->getType(), VK_LValue, 2309 AD.getTriggerStmt()->getLocEnd()); 2310 LocksetBuilder.handleCall(&DRE, DD); 2311 break; 2312 } 2313 default: 2314 break; 2315 } 2316 } 2317 CurrBlockInfo->ExitSet = LocksetBuilder.FSet; 2318 2319 // For every back edge from CurrBlock (the end of the loop) to another block 2320 // (FirstLoopBlock) we need to check that the Lockset of Block is equal to 2321 // the one held at the beginning of FirstLoopBlock. We can look up the 2322 // Lockset held at the beginning of FirstLoopBlock in the EntryLockSets map. 2323 for (CFGBlock::const_succ_iterator SI = CurrBlock->succ_begin(), 2324 SE = CurrBlock->succ_end(); SI != SE; ++SI) { 2325 2326 // if CurrBlock -> *SI is *not* a back edge 2327 if (*SI == nullptr || !VisitedBlocks.alreadySet(*SI)) 2328 continue; 2329 2330 CFGBlock *FirstLoopBlock = *SI; 2331 CFGBlockInfo *PreLoop = &BlockInfo[FirstLoopBlock->getBlockID()]; 2332 CFGBlockInfo *LoopEnd = &BlockInfo[CurrBlockID]; 2333 intersectAndWarn(LoopEnd->ExitSet, PreLoop->EntrySet, 2334 PreLoop->EntryLoc, 2335 LEK_LockedSomeLoopIterations, 2336 false); 2337 } 2338 } 2339 2340 CFGBlockInfo *Initial = &BlockInfo[CFGraph->getEntry().getBlockID()]; 2341 CFGBlockInfo *Final = &BlockInfo[CFGraph->getExit().getBlockID()]; 2342 2343 // Skip the final check if the exit block is unreachable. 2344 if (!Final->Reachable) 2345 return; 2346 2347 // By default, we expect all locks held on entry to be held on exit. 2348 FactSet ExpectedExitSet = Initial->EntrySet; 2349 2350 // Adjust the expected exit set by adding or removing locks, as declared 2351 // by *-LOCK_FUNCTION and UNLOCK_FUNCTION. The intersect below will then 2352 // issue the appropriate warning. 2353 // FIXME: the location here is not quite right. 2354 for (const auto &Lock : ExclusiveLocksAcquired) 2355 ExpectedExitSet.addLock(FactMan, llvm::make_unique<LockableFactEntry>( 2356 Lock, LK_Exclusive, D->getLocation())); 2357 for (const auto &Lock : SharedLocksAcquired) 2358 ExpectedExitSet.addLock(FactMan, llvm::make_unique<LockableFactEntry>( 2359 Lock, LK_Shared, D->getLocation())); 2360 for (const auto &Lock : LocksReleased) 2361 ExpectedExitSet.removeLock(FactMan, Lock); 2362 2363 // FIXME: Should we call this function for all blocks which exit the function? 2364 intersectAndWarn(ExpectedExitSet, Final->ExitSet, 2365 Final->ExitLoc, 2366 LEK_LockedAtEndOfFunction, 2367 LEK_NotLockedAtEndOfFunction, 2368 false); 2369 2370 Handler.leaveFunction(CurrentFunction); 2371} 2372 2373 2374/// \brief Check a function's CFG for thread-safety violations. 2375/// 2376/// We traverse the blocks in the CFG, compute the set of mutexes that are held 2377/// at the end of each block, and issue warnings for thread safety violations. 2378/// Each block in the CFG is traversed exactly once. 2379void runThreadSafetyAnalysis(AnalysisDeclContext &AC, 2380 ThreadSafetyHandler &Handler, 2381 BeforeSet **BSet) { 2382 if (!*BSet) 2383 *BSet = new BeforeSet; 2384 ThreadSafetyAnalyzer Analyzer(Handler, *BSet); 2385 Analyzer.runAnalysis(AC); 2386} 2387 2388 2389void threadSafetyCleanup(BeforeSet* Cache) { 2390 delete Cache; 2391} 2392 2393 2394/// \brief Helper function that returns a LockKind required for the given level 2395/// of access. 2396LockKind getLockKindFromAccessKind(AccessKind AK) { 2397 switch (AK) { 2398 case AK_Read : 2399 return LK_Shared; 2400 case AK_Written : 2401 return LK_Exclusive; 2402 } 2403 llvm_unreachable("Unknown AccessKind"); 2404} 2405 2406}} // end namespace clang::threadSafety 2407