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