1 //===- ThreadSafety.cpp ----------------------------------------*- C++ --*-===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // A intra-procedural analysis for thread safety (e.g. deadlocks and race 11 // conditions), based off of an annotation system. 12 // 13 // See http://clang.llvm.org/docs/LanguageExtensions.html#threadsafety for more 14 // information. 15 // 16 //===----------------------------------------------------------------------===// 17 18 #include "clang/Analysis/Analyses/ThreadSafety.h" 19 #include "clang/Analysis/AnalysisContext.h" 20 #include "clang/Analysis/CFG.h" 21 #include "clang/Analysis/CFGStmtMap.h" 22 #include "clang/AST/DeclCXX.h" 23 #include "clang/AST/ExprCXX.h" 24 #include "clang/AST/StmtCXX.h" 25 #include "clang/AST/StmtVisitor.h" 26 #include "clang/Basic/SourceManager.h" 27 #include "clang/Basic/SourceLocation.h" 28 #include "llvm/ADT/BitVector.h" 29 #include "llvm/ADT/FoldingSet.h" 30 #include "llvm/ADT/ImmutableMap.h" 31 #include "llvm/ADT/PostOrderIterator.h" 32 #include "llvm/ADT/SmallVector.h" 33 #include "llvm/ADT/StringRef.h" 34 #include <algorithm> 35 #include <vector> 36 37 using namespace clang; 38 using namespace thread_safety; 39 40 // Key method definition 41 ThreadSafetyHandler::~ThreadSafetyHandler() {} 42 43 namespace { 44 /// \brief Implements a set of CFGBlocks using a BitVector. 45 /// 46 /// This class contains a minimal interface, primarily dictated by the SetType 47 /// template parameter of the llvm::po_iterator template, as used with external 48 /// storage. We also use this set to keep track of which CFGBlocks we visit 49 /// during the analysis. 50 class CFGBlockSet { 51 llvm::BitVector VisitedBlockIDs; 52 53 public: 54 // po_iterator requires this iterator, but the only interface needed is the 55 // value_type typedef. 56 struct iterator { 57 typedef const CFGBlock *value_type; 58 }; 59 60 CFGBlockSet() {} 61 CFGBlockSet(const CFG *G) : VisitedBlockIDs(G->getNumBlockIDs(), false) {} 62 63 /// \brief Set the bit associated with a particular CFGBlock. 64 /// This is the important method for the SetType template parameter. 65 bool insert(const CFGBlock *Block) { 66 // Note that insert() is called by po_iterator, which doesn't check to make 67 // sure that Block is non-null. Moreover, the CFGBlock iterator will 68 // occasionally hand out null pointers for pruned edges, so we catch those 69 // here. 70 if (Block == 0) 71 return false; // if an edge is trivially false. 72 if (VisitedBlockIDs.test(Block->getBlockID())) 73 return false; 74 VisitedBlockIDs.set(Block->getBlockID()); 75 return true; 76 } 77 78 /// \brief Check if the bit for a CFGBlock has been already set. 79 /// This method is for tracking visited blocks in the main threadsafety loop. 80 /// Block must not be null. 81 bool alreadySet(const CFGBlock *Block) { 82 return VisitedBlockIDs.test(Block->getBlockID()); 83 } 84 }; 85 86 /// \brief We create a helper class which we use to iterate through CFGBlocks in 87 /// the topological order. 88 class TopologicallySortedCFG { 89 typedef llvm::po_iterator<const CFG*, CFGBlockSet, true> po_iterator; 90 91 std::vector<const CFGBlock*> Blocks; 92 93 public: 94 typedef std::vector<const CFGBlock*>::reverse_iterator iterator; 95 96 TopologicallySortedCFG(const CFG *CFGraph) { 97 Blocks.reserve(CFGraph->getNumBlockIDs()); 98 CFGBlockSet BSet(CFGraph); 99 100 for (po_iterator I = po_iterator::begin(CFGraph, BSet), 101 E = po_iterator::end(CFGraph, BSet); I != E; ++I) { 102 Blocks.push_back(*I); 103 } 104 } 105 106 iterator begin() { 107 return Blocks.rbegin(); 108 } 109 110 iterator end() { 111 return Blocks.rend(); 112 } 113 114 bool empty() { 115 return begin() == end(); 116 } 117 }; 118 119 /// \brief A MutexID object uniquely identifies a particular mutex, and 120 /// is built from an Expr* (i.e. calling a lock function). 121 /// 122 /// Thread-safety analysis works by comparing lock expressions. Within the 123 /// body of a function, an expression such as "x->foo->bar.mu" will resolve to 124 /// a particular mutex object at run-time. Subsequent occurrences of the same 125 /// expression (where "same" means syntactic equality) will refer to the same 126 /// run-time object if three conditions hold: 127 /// (1) Local variables in the expression, such as "x" have not changed. 128 /// (2) Values on the heap that affect the expression have not changed. 129 /// (3) The expression involves only pure function calls. 130 /// The current implementation assumes, but does not verify, that multiple uses 131 /// of the same lock expression satisfies these criteria. 132 /// 133 /// Clang introduces an additional wrinkle, which is that it is difficult to 134 /// derive canonical expressions, or compare expressions directly for equality. 135 /// Thus, we identify a mutex not by an Expr, but by the set of named 136 /// declarations that are referenced by the Expr. In other words, 137 /// x->foo->bar.mu will be a four element vector with the Decls for 138 /// mu, bar, and foo, and x. The vector will uniquely identify the expression 139 /// for all practical purposes. 140 /// 141 /// Note we will need to perform substitution on "this" and function parameter 142 /// names when constructing a lock expression. 143 /// 144 /// For example: 145 /// class C { Mutex Mu; void lock() EXCLUSIVE_LOCK_FUNCTION(this->Mu); }; 146 /// void myFunc(C *X) { ... X->lock() ... } 147 /// The original expression for the mutex acquired by myFunc is "this->Mu", but 148 /// "X" is substituted for "this" so we get X->Mu(); 149 /// 150 /// For another example: 151 /// foo(MyList *L) EXCLUSIVE_LOCKS_REQUIRED(L->Mu) { ... } 152 /// MyList *MyL; 153 /// foo(MyL); // requires lock MyL->Mu to be held 154 class MutexID { 155 SmallVector<NamedDecl*, 2> DeclSeq; 156 157 /// Build a Decl sequence representing the lock from the given expression. 158 /// Recursive function that bottoms out when the final DeclRefExpr is reached. 159 void buildMutexID(Expr *Exp, Expr *Parent, int NumArgs, 160 const NamedDecl **FunArgDecls, Expr **FunArgs) { 161 if (DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(Exp)) { 162 if (FunArgDecls) { 163 // Substitute call arguments for references to function parameters 164 for (int i = 0; i < NumArgs; ++i) { 165 if (DRE->getDecl() == FunArgDecls[i]) { 166 buildMutexID(FunArgs[i], 0, 0, 0, 0); 167 return; 168 } 169 } 170 } 171 NamedDecl *ND = cast<NamedDecl>(DRE->getDecl()->getCanonicalDecl()); 172 DeclSeq.push_back(ND); 173 } else if (MemberExpr *ME = dyn_cast<MemberExpr>(Exp)) { 174 NamedDecl *ND = ME->getMemberDecl(); 175 DeclSeq.push_back(ND); 176 buildMutexID(ME->getBase(), Parent, NumArgs, FunArgDecls, FunArgs); 177 } else if (isa<CXXThisExpr>(Exp)) { 178 if (Parent) 179 buildMutexID(Parent, 0, 0, 0, 0); 180 else 181 return; // mutexID is still valid in this case 182 } else if (CastExpr *CE = dyn_cast<CastExpr>(Exp)) 183 buildMutexID(CE->getSubExpr(), Parent, NumArgs, FunArgDecls, FunArgs); 184 else 185 DeclSeq.clear(); // Mark as invalid lock expression. 186 } 187 188 /// \brief Construct a MutexID from an expression. 189 /// \param MutexExp The original mutex expression within an attribute 190 /// \param DeclExp An expression involving the Decl on which the attribute 191 /// occurs. 192 /// \param D The declaration to which the lock/unlock attribute is attached. 193 void buildMutexIDFromExp(Expr *MutexExp, Expr *DeclExp, const NamedDecl *D) { 194 Expr *Parent = 0; 195 unsigned NumArgs = 0; 196 Expr **FunArgs = 0; 197 SmallVector<const NamedDecl*, 8> FunArgDecls; 198 199 if (DeclExp == 0) { 200 buildMutexID(MutexExp, 0, 0, 0, 0); 201 return; 202 } 203 204 if (MemberExpr *ME = dyn_cast<MemberExpr>(DeclExp)) { 205 Parent = ME->getBase(); 206 } else if (CXXMemberCallExpr *CE = dyn_cast<CXXMemberCallExpr>(DeclExp)) { 207 Parent = CE->getImplicitObjectArgument(); 208 NumArgs = CE->getNumArgs(); 209 FunArgs = CE->getArgs(); 210 } 211 212 // If the attribute has no arguments, then assume the argument is "this". 213 if (MutexExp == 0) { 214 buildMutexID(Parent, 0, 0, 0, 0); 215 return; 216 } 217 218 // FIXME: handle default arguments 219 if (const FunctionDecl *FD = dyn_cast_or_null<FunctionDecl>(D)) { 220 for (unsigned i = 0, ni = FD->getNumParams(); i < ni && i < NumArgs; ++i) { 221 FunArgDecls.push_back(FD->getParamDecl(i)); 222 } 223 } 224 buildMutexID(MutexExp, Parent, NumArgs, &FunArgDecls.front(), FunArgs); 225 } 226 227 public: 228 /// \param MutexExp The original mutex expression within an attribute 229 /// \param DeclExp An expression involving the Decl on which the attribute 230 /// occurs. 231 /// \param D The declaration to which the lock/unlock attribute is attached. 232 /// Caller must check isValid() after construction. 233 MutexID(Expr* MutexExp, Expr *DeclExp, const NamedDecl* D) { 234 buildMutexIDFromExp(MutexExp, DeclExp, D); 235 } 236 237 /// Return true if this is a valid decl sequence. 238 /// Caller must call this by hand after construction to handle errors. 239 bool isValid() const { 240 return !DeclSeq.empty(); 241 } 242 243 bool operator==(const MutexID &other) const { 244 return DeclSeq == other.DeclSeq; 245 } 246 247 bool operator!=(const MutexID &other) const { 248 return !(*this == other); 249 } 250 251 // SmallVector overloads Operator< to do lexicographic ordering. Note that 252 // we use pointer equality (and <) to compare NamedDecls. This means the order 253 // of MutexIDs in a lockset is nondeterministic. In order to output 254 // diagnostics in a deterministic ordering, we must order all diagnostics to 255 // output by SourceLocation when iterating through this lockset. 256 bool operator<(const MutexID &other) const { 257 return DeclSeq < other.DeclSeq; 258 } 259 260 /// \brief Returns the name of the first Decl in the list for a given MutexID; 261 /// e.g. the lock expression foo.bar() has name "bar". 262 /// The caret will point unambiguously to the lock expression, so using this 263 /// name in diagnostics is a way to get simple, and consistent, mutex names. 264 /// We do not want to output the entire expression text for security reasons. 265 StringRef getName() const { 266 assert(isValid()); 267 return DeclSeq.front()->getName(); 268 } 269 270 void Profile(llvm::FoldingSetNodeID &ID) const { 271 for (SmallVectorImpl<NamedDecl*>::const_iterator I = DeclSeq.begin(), 272 E = DeclSeq.end(); I != E; ++I) { 273 ID.AddPointer(*I); 274 } 275 } 276 }; 277 278 /// \brief This is a helper class that stores info about the most recent 279 /// accquire of a Lock. 280 /// 281 /// The main body of the analysis maps MutexIDs to LockDatas. 282 struct LockData { 283 SourceLocation AcquireLoc; 284 285 /// \brief LKind stores whether a lock is held shared or exclusively. 286 /// Note that this analysis does not currently support either re-entrant 287 /// locking or lock "upgrading" and "downgrading" between exclusive and 288 /// shared. 289 /// 290 /// FIXME: add support for re-entrant locking and lock up/downgrading 291 LockKind LKind; 292 293 LockData(SourceLocation AcquireLoc, LockKind LKind) 294 : AcquireLoc(AcquireLoc), LKind(LKind) {} 295 296 bool operator==(const LockData &other) const { 297 return AcquireLoc == other.AcquireLoc && LKind == other.LKind; 298 } 299 300 bool operator!=(const LockData &other) const { 301 return !(*this == other); 302 } 303 304 void Profile(llvm::FoldingSetNodeID &ID) const { 305 ID.AddInteger(AcquireLoc.getRawEncoding()); 306 ID.AddInteger(LKind); 307 } 308 }; 309 310 /// A Lockset maps each MutexID (defined above) to information about how it has 311 /// been locked. 312 typedef llvm::ImmutableMap<MutexID, LockData> Lockset; 313 314 /// \brief We use this class to visit different types of expressions in 315 /// CFGBlocks, and build up the lockset. 316 /// An expression may cause us to add or remove locks from the lockset, or else 317 /// output error messages related to missing locks. 318 /// FIXME: In future, we may be able to not inherit from a visitor. 319 class BuildLockset : public StmtVisitor<BuildLockset> { 320 ThreadSafetyHandler &Handler; 321 Lockset LSet; 322 Lockset::Factory &LocksetFactory; 323 324 // Helper functions 325 void removeLock(SourceLocation UnlockLoc, MutexID &Mutex); 326 void addLock(SourceLocation LockLoc, MutexID &Mutex, LockKind LK); 327 const ValueDecl *getValueDecl(Expr *Exp); 328 void warnIfMutexNotHeld (const NamedDecl *D, Expr *Exp, AccessKind AK, 329 Expr *MutexExp, ProtectedOperationKind POK); 330 void checkAccess(Expr *Exp, AccessKind AK); 331 void checkDereference(Expr *Exp, AccessKind AK); 332 333 template <class AttrType> 334 void addLocksToSet(LockKind LK, AttrType *Attr, CXXMemberCallExpr *Exp, 335 NamedDecl* D); 336 337 /// \brief Returns true if the lockset contains a lock, regardless of whether 338 /// the lock is held exclusively or shared. 339 bool locksetContains(MutexID Lock) const { 340 return LSet.lookup(Lock); 341 } 342 343 /// \brief Returns true if the lockset contains a lock with the passed in 344 /// locktype. 345 bool locksetContains(MutexID Lock, LockKind KindRequested) const { 346 const LockData *LockHeld = LSet.lookup(Lock); 347 return (LockHeld && KindRequested == LockHeld->LKind); 348 } 349 350 /// \brief Returns true if the lockset contains a lock with at least the 351 /// passed in locktype. So for example, if we pass in LK_Shared, this function 352 /// returns true if the lock is held LK_Shared or LK_Exclusive. If we pass in 353 /// LK_Exclusive, this function returns true if the lock is held LK_Exclusive. 354 bool locksetContainsAtLeast(MutexID Lock, LockKind KindRequested) const { 355 switch (KindRequested) { 356 case LK_Shared: 357 return locksetContains(Lock); 358 case LK_Exclusive: 359 return locksetContains(Lock, KindRequested); 360 } 361 llvm_unreachable("Unknown LockKind"); 362 } 363 364 public: 365 BuildLockset(ThreadSafetyHandler &Handler, Lockset LS, Lockset::Factory &F) 366 : StmtVisitor<BuildLockset>(), Handler(Handler), LSet(LS), 367 LocksetFactory(F) {} 368 369 Lockset getLockset() { 370 return LSet; 371 } 372 373 void VisitUnaryOperator(UnaryOperator *UO); 374 void VisitBinaryOperator(BinaryOperator *BO); 375 void VisitCastExpr(CastExpr *CE); 376 void VisitCXXMemberCallExpr(CXXMemberCallExpr *Exp); 377 }; 378 379 /// \brief Add a new lock to the lockset, warning if the lock is already there. 380 /// \param LockLoc The source location of the acquire 381 /// \param LockExp The lock expression corresponding to the lock to be added 382 void BuildLockset::addLock(SourceLocation LockLoc, MutexID &Mutex, 383 LockKind LK) { 384 // FIXME: deal with acquired before/after annotations. We can write a first 385 // pass that does the transitive lookup lazily, and refine afterwards. 386 LockData NewLock(LockLoc, LK); 387 388 // FIXME: Don't always warn when we have support for reentrant locks. 389 if (locksetContains(Mutex)) 390 Handler.handleDoubleLock(Mutex.getName(), LockLoc); 391 LSet = LocksetFactory.add(LSet, Mutex, NewLock); 392 } 393 394 /// \brief Remove a lock from the lockset, warning if the lock is not there. 395 /// \param LockExp The lock expression corresponding to the lock to be removed 396 /// \param UnlockLoc The source location of the unlock (only used in error msg) 397 void BuildLockset::removeLock(SourceLocation UnlockLoc, MutexID &Mutex) { 398 Lockset NewLSet = LocksetFactory.remove(LSet, Mutex); 399 if(NewLSet == LSet) 400 Handler.handleUnmatchedUnlock(Mutex.getName(), UnlockLoc); 401 402 LSet = NewLSet; 403 } 404 405 /// \brief Gets the value decl pointer from DeclRefExprs or MemberExprs 406 const ValueDecl *BuildLockset::getValueDecl(Expr *Exp) { 407 if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(Exp)) 408 return DR->getDecl(); 409 410 if (const MemberExpr *ME = dyn_cast<MemberExpr>(Exp)) 411 return ME->getMemberDecl(); 412 413 return 0; 414 } 415 416 /// \brief Warn if the LSet does not contain a lock sufficient to protect access 417 /// of at least the passed in AccessKind. 418 void BuildLockset::warnIfMutexNotHeld(const NamedDecl *D, Expr *Exp, 419 AccessKind AK, Expr *MutexExp, 420 ProtectedOperationKind POK) { 421 LockKind LK = getLockKindFromAccessKind(AK); 422 423 MutexID Mutex(MutexExp, Exp, D); 424 if (!Mutex.isValid()) 425 Handler.handleInvalidLockExp(MutexExp->getExprLoc()); 426 else if (!locksetContainsAtLeast(Mutex, LK)) 427 Handler.handleMutexNotHeld(D, POK, Mutex.getName(), LK, Exp->getExprLoc()); 428 } 429 430 431 /// \brief This method identifies variable dereferences and checks pt_guarded_by 432 /// and pt_guarded_var annotations. Note that we only check these annotations 433 /// at the time a pointer is dereferenced. 434 /// FIXME: We need to check for other types of pointer dereferences 435 /// (e.g. [], ->) and deal with them here. 436 /// \param Exp An expression that has been read or written. 437 void BuildLockset::checkDereference(Expr *Exp, AccessKind AK) { 438 UnaryOperator *UO = dyn_cast<UnaryOperator>(Exp); 439 if (!UO || UO->getOpcode() != clang::UO_Deref) 440 return; 441 Exp = UO->getSubExpr()->IgnoreParenCasts(); 442 443 const ValueDecl *D = getValueDecl(Exp); 444 if(!D || !D->hasAttrs()) 445 return; 446 447 if (D->getAttr<PtGuardedVarAttr>() && LSet.isEmpty()) 448 Handler.handleNoMutexHeld(D, POK_VarDereference, AK, Exp->getExprLoc()); 449 450 const AttrVec &ArgAttrs = D->getAttrs(); 451 for(unsigned i = 0, Size = ArgAttrs.size(); i < Size; ++i) 452 if (PtGuardedByAttr *PGBAttr = dyn_cast<PtGuardedByAttr>(ArgAttrs[i])) 453 warnIfMutexNotHeld(D, Exp, AK, PGBAttr->getArg(), POK_VarDereference); 454 } 455 456 /// \brief Checks guarded_by and guarded_var attributes. 457 /// Whenever we identify an access (read or write) of a DeclRefExpr or 458 /// MemberExpr, we need to check whether there are any guarded_by or 459 /// guarded_var attributes, and make sure we hold the appropriate mutexes. 460 void BuildLockset::checkAccess(Expr *Exp, AccessKind AK) { 461 const ValueDecl *D = getValueDecl(Exp); 462 if(!D || !D->hasAttrs()) 463 return; 464 465 if (D->getAttr<GuardedVarAttr>() && LSet.isEmpty()) 466 Handler.handleNoMutexHeld(D, POK_VarAccess, AK, Exp->getExprLoc()); 467 468 const AttrVec &ArgAttrs = D->getAttrs(); 469 for(unsigned i = 0, Size = ArgAttrs.size(); i < Size; ++i) 470 if (GuardedByAttr *GBAttr = dyn_cast<GuardedByAttr>(ArgAttrs[i])) 471 warnIfMutexNotHeld(D, Exp, AK, GBAttr->getArg(), POK_VarAccess); 472 } 473 474 /// \brief For unary operations which read and write a variable, we need to 475 /// check whether we hold any required mutexes. Reads are checked in 476 /// VisitCastExpr. 477 void BuildLockset::VisitUnaryOperator(UnaryOperator *UO) { 478 switch (UO->getOpcode()) { 479 case clang::UO_PostDec: 480 case clang::UO_PostInc: 481 case clang::UO_PreDec: 482 case clang::UO_PreInc: { 483 Expr *SubExp = UO->getSubExpr()->IgnoreParenCasts(); 484 checkAccess(SubExp, AK_Written); 485 checkDereference(SubExp, AK_Written); 486 break; 487 } 488 default: 489 break; 490 } 491 } 492 493 /// For binary operations which assign to a variable (writes), we need to check 494 /// whether we hold any required mutexes. 495 /// FIXME: Deal with non-primitive types. 496 void BuildLockset::VisitBinaryOperator(BinaryOperator *BO) { 497 if (!BO->isAssignmentOp()) 498 return; 499 Expr *LHSExp = BO->getLHS()->IgnoreParenCasts(); 500 checkAccess(LHSExp, AK_Written); 501 checkDereference(LHSExp, AK_Written); 502 } 503 504 /// Whenever we do an LValue to Rvalue cast, we are reading a variable and 505 /// need to ensure we hold any required mutexes. 506 /// FIXME: Deal with non-primitive types. 507 void BuildLockset::VisitCastExpr(CastExpr *CE) { 508 if (CE->getCastKind() != CK_LValueToRValue) 509 return; 510 Expr *SubExp = CE->getSubExpr()->IgnoreParenCasts(); 511 checkAccess(SubExp, AK_Read); 512 checkDereference(SubExp, AK_Read); 513 } 514 515 /// \brief This function, parameterized by an attribute type, is used to add a 516 /// set of locks specified as attribute arguments to the lockset. 517 template <typename AttrType> 518 void BuildLockset::addLocksToSet(LockKind LK, AttrType *Attr, 519 CXXMemberCallExpr *Exp, 520 NamedDecl* FunDecl) { 521 typedef typename AttrType::args_iterator iterator_type; 522 523 SourceLocation ExpLocation = Exp->getExprLoc(); 524 525 if (Attr->args_size() == 0) { 526 // The mutex held is the "this" object. 527 528 MutexID Mutex(0, Exp, FunDecl); 529 if (!Mutex.isValid()) 530 Handler.handleInvalidLockExp(Exp->getExprLoc()); 531 else 532 addLock(ExpLocation, Mutex, LK); 533 return; 534 } 535 536 for (iterator_type I=Attr->args_begin(), E=Attr->args_end(); I != E; ++I) { 537 MutexID Mutex(*I, Exp, FunDecl); 538 if (!Mutex.isValid()) 539 Handler.handleInvalidLockExp(Exp->getExprLoc()); 540 else 541 addLock(ExpLocation, Mutex, LK); 542 } 543 } 544 545 /// \brief When visiting CXXMemberCallExprs we need to examine the attributes on 546 /// the method that is being called and add, remove or check locks in the 547 /// lockset accordingly. 548 /// 549 /// FIXME: For classes annotated with one of the guarded annotations, we need 550 /// to treat const method calls as reads and non-const method calls as writes, 551 /// and check that the appropriate locks are held. Non-const method calls with 552 /// the same signature as const method calls can be also treated as reads. 553 /// 554 /// FIXME: We need to also visit CallExprs to catch/check global functions. 555 /// 556 /// FIXME: Do not flag an error for member variables accessed in constructors/ 557 /// destructors 558 void BuildLockset::VisitCXXMemberCallExpr(CXXMemberCallExpr *Exp) { 559 SourceLocation ExpLocation = Exp->getExprLoc(); 560 561 NamedDecl *D = dyn_cast_or_null<NamedDecl>(Exp->getCalleeDecl()); 562 if(!D || !D->hasAttrs()) 563 return; 564 565 AttrVec &ArgAttrs = D->getAttrs(); 566 for(unsigned i = 0; i < ArgAttrs.size(); ++i) { 567 Attr *Attr = ArgAttrs[i]; 568 switch (Attr->getKind()) { 569 // When we encounter an exclusive lock function, we need to add the lock 570 // to our lockset with kind exclusive. 571 case attr::ExclusiveLockFunction: { 572 ExclusiveLockFunctionAttr *A = cast<ExclusiveLockFunctionAttr>(Attr); 573 addLocksToSet(LK_Exclusive, A, Exp, D); 574 break; 575 } 576 577 // When we encounter a shared lock function, we need to add the lock 578 // to our lockset with kind shared. 579 case attr::SharedLockFunction: { 580 SharedLockFunctionAttr *A = cast<SharedLockFunctionAttr>(Attr); 581 addLocksToSet(LK_Shared, A, Exp, D); 582 break; 583 } 584 585 // When we encounter an unlock function, we need to remove unlocked 586 // mutexes from the lockset, and flag a warning if they are not there. 587 case attr::UnlockFunction: { 588 UnlockFunctionAttr *UFAttr = cast<UnlockFunctionAttr>(Attr); 589 590 if (UFAttr->args_size() == 0) { // The lock held is the "this" object. 591 MutexID Mu(0, Exp, D); 592 if (!Mu.isValid()) 593 Handler.handleInvalidLockExp(Exp->getExprLoc()); 594 else 595 removeLock(ExpLocation, Mu); 596 break; 597 } 598 599 for (UnlockFunctionAttr::args_iterator I = UFAttr->args_begin(), 600 E = UFAttr->args_end(); I != E; ++I) { 601 MutexID Mutex(*I, Exp, D); 602 if (!Mutex.isValid()) 603 Handler.handleInvalidLockExp(Exp->getExprLoc()); 604 else 605 removeLock(ExpLocation, Mutex); 606 } 607 break; 608 } 609 610 case attr::ExclusiveLocksRequired: { 611 ExclusiveLocksRequiredAttr *ELRAttr = 612 cast<ExclusiveLocksRequiredAttr>(Attr); 613 614 for (ExclusiveLocksRequiredAttr::args_iterator 615 I = ELRAttr->args_begin(), E = ELRAttr->args_end(); I != E; ++I) 616 warnIfMutexNotHeld(D, Exp, AK_Written, *I, POK_FunctionCall); 617 break; 618 } 619 620 case attr::SharedLocksRequired: { 621 SharedLocksRequiredAttr *SLRAttr = cast<SharedLocksRequiredAttr>(Attr); 622 623 for (SharedLocksRequiredAttr::args_iterator I = SLRAttr->args_begin(), 624 E = SLRAttr->args_end(); I != E; ++I) 625 warnIfMutexNotHeld(D, Exp, AK_Read, *I, POK_FunctionCall); 626 break; 627 } 628 629 case attr::LocksExcluded: { 630 LocksExcludedAttr *LEAttr = cast<LocksExcludedAttr>(Attr); 631 for (LocksExcludedAttr::args_iterator I = LEAttr->args_begin(), 632 E = LEAttr->args_end(); I != E; ++I) { 633 MutexID Mutex(*I, Exp, D); 634 if (!Mutex.isValid()) 635 Handler.handleInvalidLockExp((*I)->getExprLoc()); 636 else if (locksetContains(Mutex)) 637 Handler.handleFunExcludesLock(D->getName(), Mutex.getName(), 638 ExpLocation); 639 } 640 break; 641 } 642 643 // Ignore other (non thread-safety) attributes 644 default: 645 break; 646 } 647 } 648 } 649 650 } // end anonymous namespace 651 652 /// \brief Compute the intersection of two locksets and issue warnings for any 653 /// locks in the symmetric difference. 654 /// 655 /// This function is used at a merge point in the CFG when comparing the lockset 656 /// of each branch being merged. For example, given the following sequence: 657 /// A; if () then B; else C; D; we need to check that the lockset after B and C 658 /// are the same. In the event of a difference, we use the intersection of these 659 /// two locksets at the start of D. 660 static Lockset intersectAndWarn(ThreadSafetyHandler &Handler, 661 const Lockset LSet1, const Lockset LSet2, 662 Lockset::Factory &Fact, LockErrorKind LEK) { 663 Lockset Intersection = LSet1; 664 for (Lockset::iterator I = LSet2.begin(), E = LSet2.end(); I != E; ++I) { 665 const MutexID &LSet2Mutex = I.getKey(); 666 const LockData &LSet2LockData = I.getData(); 667 if (const LockData *LD = LSet1.lookup(LSet2Mutex)) { 668 if (LD->LKind != LSet2LockData.LKind) { 669 Handler.handleExclusiveAndShared(LSet2Mutex.getName(), 670 LSet2LockData.AcquireLoc, 671 LD->AcquireLoc); 672 if (LD->LKind != LK_Exclusive) 673 Intersection = Fact.add(Intersection, LSet2Mutex, LSet2LockData); 674 } 675 } else { 676 Handler.handleMutexHeldEndOfScope(LSet2Mutex.getName(), 677 LSet2LockData.AcquireLoc, LEK); 678 } 679 } 680 681 for (Lockset::iterator I = LSet1.begin(), E = LSet1.end(); I != E; ++I) { 682 if (!LSet2.contains(I.getKey())) { 683 const MutexID &Mutex = I.getKey(); 684 const LockData &MissingLock = I.getData(); 685 Handler.handleMutexHeldEndOfScope(Mutex.getName(), 686 MissingLock.AcquireLoc, LEK); 687 Intersection = Fact.remove(Intersection, Mutex); 688 } 689 } 690 return Intersection; 691 } 692 693 static Lockset addLock(ThreadSafetyHandler &Handler, 694 Lockset::Factory &LocksetFactory, 695 Lockset &LSet, Expr *MutexExp, const NamedDecl *D, 696 LockKind LK, SourceLocation Loc) { 697 MutexID Mutex(MutexExp, 0, D); 698 if (!Mutex.isValid()) { 699 Handler.handleInvalidLockExp(MutexExp->getExprLoc()); 700 return LSet; 701 } 702 LockData NewLock(Loc, LK); 703 return LocksetFactory.add(LSet, Mutex, NewLock); 704 } 705 706 namespace clang { 707 namespace thread_safety { 708 /// \brief Check a function's CFG for thread-safety violations. 709 /// 710 /// We traverse the blocks in the CFG, compute the set of mutexes that are held 711 /// at the end of each block, and issue warnings for thread safety violations. 712 /// Each block in the CFG is traversed exactly once. 713 void runThreadSafetyAnalysis(AnalysisContext &AC, 714 ThreadSafetyHandler &Handler) { 715 CFG *CFGraph = AC.getCFG(); 716 if (!CFGraph) return; 717 const NamedDecl *D = dyn_cast_or_null<NamedDecl>(AC.getDecl()); 718 719 if (!D) 720 return; // Ignore anonymous functions for now. 721 if (D->getAttr<NoThreadSafetyAnalysisAttr>()) 722 return; 723 724 Lockset::Factory LocksetFactory; 725 726 // FIXME: Swith to SmallVector? Otherwise improve performance impact? 727 std::vector<Lockset> EntryLocksets(CFGraph->getNumBlockIDs(), 728 LocksetFactory.getEmptyMap()); 729 std::vector<Lockset> ExitLocksets(CFGraph->getNumBlockIDs(), 730 LocksetFactory.getEmptyMap()); 731 732 // We need to explore the CFG via a "topological" ordering. 733 // That way, we will be guaranteed to have information about required 734 // predecessor locksets when exploring a new block. 735 TopologicallySortedCFG SortedGraph(CFGraph); 736 CFGBlockSet VisitedBlocks(CFGraph); 737 738 if (!SortedGraph.empty() && D->hasAttrs()) { 739 const CFGBlock *FirstBlock = *SortedGraph.begin(); 740 Lockset &InitialLockset = EntryLocksets[FirstBlock->getBlockID()]; 741 const AttrVec &ArgAttrs = D->getAttrs(); 742 for(unsigned i = 0; i < ArgAttrs.size(); ++i) { 743 Attr *Attr = ArgAttrs[i]; 744 SourceLocation AttrLoc = Attr->getLocation(); 745 if (SharedLocksRequiredAttr *SLRAttr 746 = dyn_cast<SharedLocksRequiredAttr>(Attr)) { 747 for (SharedLocksRequiredAttr::args_iterator 748 SLRIter = SLRAttr->args_begin(), 749 SLREnd = SLRAttr->args_end(); SLRIter != SLREnd; ++SLRIter) 750 InitialLockset = addLock(Handler, LocksetFactory, InitialLockset, 751 *SLRIter, D, LK_Shared, 752 AttrLoc); 753 } else if (ExclusiveLocksRequiredAttr *ELRAttr 754 = dyn_cast<ExclusiveLocksRequiredAttr>(Attr)) { 755 for (ExclusiveLocksRequiredAttr::args_iterator 756 ELRIter = ELRAttr->args_begin(), 757 ELREnd = ELRAttr->args_end(); ELRIter != ELREnd; ++ELRIter) 758 InitialLockset = addLock(Handler, LocksetFactory, InitialLockset, 759 *ELRIter, D, LK_Exclusive, 760 AttrLoc); 761 } 762 } 763 } 764 765 for (TopologicallySortedCFG::iterator I = SortedGraph.begin(), 766 E = SortedGraph.end(); I!= E; ++I) { 767 const CFGBlock *CurrBlock = *I; 768 int CurrBlockID = CurrBlock->getBlockID(); 769 770 VisitedBlocks.insert(CurrBlock); 771 772 // Use the default initial lockset in case there are no predecessors. 773 Lockset &Entryset = EntryLocksets[CurrBlockID]; 774 Lockset &Exitset = ExitLocksets[CurrBlockID]; 775 776 // Iterate through the predecessor blocks and warn if the lockset for all 777 // predecessors is not the same. We take the entry lockset of the current 778 // block to be the intersection of all previous locksets. 779 // FIXME: By keeping the intersection, we may output more errors in future 780 // for a lock which is not in the intersection, but was in the union. We 781 // may want to also keep the union in future. As an example, let's say 782 // the intersection contains Mutex L, and the union contains L and M. 783 // Later we unlock M. At this point, we would output an error because we 784 // never locked M; although the real error is probably that we forgot to 785 // lock M on all code paths. Conversely, let's say that later we lock M. 786 // In this case, we should compare against the intersection instead of the 787 // union because the real error is probably that we forgot to unlock M on 788 // all code paths. 789 bool LocksetInitialized = false; 790 for (CFGBlock::const_pred_iterator PI = CurrBlock->pred_begin(), 791 PE = CurrBlock->pred_end(); PI != PE; ++PI) { 792 793 // if *PI -> CurrBlock is a back edge 794 if (*PI == 0 || !VisitedBlocks.alreadySet(*PI)) 795 continue; 796 797 int PrevBlockID = (*PI)->getBlockID(); 798 if (!LocksetInitialized) { 799 Entryset = ExitLocksets[PrevBlockID]; 800 LocksetInitialized = true; 801 } else { 802 Entryset = intersectAndWarn(Handler, Entryset, 803 ExitLocksets[PrevBlockID], LocksetFactory, 804 LEK_LockedSomePredecessors); 805 } 806 } 807 808 BuildLockset LocksetBuilder(Handler, Entryset, LocksetFactory); 809 for (CFGBlock::const_iterator BI = CurrBlock->begin(), 810 BE = CurrBlock->end(); BI != BE; ++BI) { 811 if (const CFGStmt *CfgStmt = dyn_cast<CFGStmt>(&*BI)) 812 LocksetBuilder.Visit(const_cast<Stmt*>(CfgStmt->getStmt())); 813 } 814 Exitset = LocksetBuilder.getLockset(); 815 816 // For every back edge from CurrBlock (the end of the loop) to another block 817 // (FirstLoopBlock) we need to check that the Lockset of Block is equal to 818 // the one held at the beginning of FirstLoopBlock. We can look up the 819 // Lockset held at the beginning of FirstLoopBlock in the EntryLockSets map. 820 for (CFGBlock::const_succ_iterator SI = CurrBlock->succ_begin(), 821 SE = CurrBlock->succ_end(); SI != SE; ++SI) { 822 823 // if CurrBlock -> *SI is *not* a back edge 824 if (*SI == 0 || !VisitedBlocks.alreadySet(*SI)) 825 continue; 826 827 CFGBlock *FirstLoopBlock = *SI; 828 Lockset PreLoop = EntryLocksets[FirstLoopBlock->getBlockID()]; 829 Lockset LoopEnd = ExitLocksets[CurrBlockID]; 830 intersectAndWarn(Handler, LoopEnd, PreLoop, LocksetFactory, 831 LEK_LockedSomeLoopIterations); 832 } 833 } 834 835 Lockset InitialLockset = EntryLocksets[CFGraph->getEntry().getBlockID()]; 836 Lockset FinalLockset = ExitLocksets[CFGraph->getExit().getBlockID()]; 837 838 // FIXME: Should we call this function for all blocks which exit the function? 839 intersectAndWarn(Handler, InitialLockset, FinalLockset, LocksetFactory, 840 LEK_LockedAtEndOfFunction); 841 } 842 843 /// \brief Helper function that returns a LockKind required for the given level 844 /// of access. 845 LockKind getLockKindFromAccessKind(AccessKind AK) { 846 switch (AK) { 847 case AK_Read : 848 return LK_Shared; 849 case AK_Written : 850 return LK_Exclusive; 851 } 852 llvm_unreachable("Unknown AccessKind"); 853 } 854 }} // end namespace clang::thread_safety 855