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