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