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