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