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