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