ThreadSafety.cpp revision 4444446abb50f7b0314d82be0afa892f945cc9bc
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#thread-safety-annotation-checking 14// for more information. 15// 16//===----------------------------------------------------------------------===// 17 18#include "clang/Analysis/Analyses/ThreadSafety.h" 19#include "clang/AST/Attr.h" 20#include "clang/AST/DeclCXX.h" 21#include "clang/AST/ExprCXX.h" 22#include "clang/AST/StmtCXX.h" 23#include "clang/AST/StmtVisitor.h" 24#include "clang/Analysis/Analyses/PostOrderCFGView.h" 25#include "clang/Analysis/AnalysisContext.h" 26#include "clang/Analysis/CFG.h" 27#include "clang/Analysis/CFGStmtMap.h" 28#include "clang/Basic/OperatorKinds.h" 29#include "clang/Basic/SourceLocation.h" 30#include "clang/Basic/SourceManager.h" 31#include "llvm/ADT/BitVector.h" 32#include "llvm/ADT/FoldingSet.h" 33#include "llvm/ADT/ImmutableMap.h" 34#include "llvm/ADT/PostOrderIterator.h" 35#include "llvm/ADT/SmallVector.h" 36#include "llvm/ADT/StringRef.h" 37#include "llvm/Support/raw_ostream.h" 38#include <algorithm> 39#include <utility> 40#include <vector> 41 42using namespace clang; 43using namespace thread_safety; 44 45// Key method definition 46ThreadSafetyHandler::~ThreadSafetyHandler() {} 47 48namespace { 49 50/// SExpr implements a simple expression language that is used to store, 51/// compare, and pretty-print C++ expressions. Unlike a clang Expr, a SExpr 52/// does not capture surface syntax, and it does not distinguish between 53/// C++ concepts, like pointers and references, that have no real semantic 54/// differences. This simplicity allows SExprs to be meaningfully compared, 55/// e.g. 56/// (x) = x 57/// (*this).foo = this->foo 58/// *&a = a 59/// 60/// Thread-safety analysis works by comparing lock expressions. Within the 61/// body of a function, an expression such as "x->foo->bar.mu" will resolve to 62/// a particular mutex object at run-time. Subsequent occurrences of the same 63/// expression (where "same" means syntactic equality) will refer to the same 64/// run-time object if three conditions hold: 65/// (1) Local variables in the expression, such as "x" have not changed. 66/// (2) Values on the heap that affect the expression have not changed. 67/// (3) The expression involves only pure function calls. 68/// 69/// The current implementation assumes, but does not verify, that multiple uses 70/// of the same lock expression satisfies these criteria. 71class SExpr { 72private: 73 enum ExprOp { 74 EOP_Nop, ///< No-op 75 EOP_Wildcard, ///< Matches anything. 76 EOP_Universal, ///< Universal lock. 77 EOP_This, ///< This keyword. 78 EOP_NVar, ///< Named variable. 79 EOP_LVar, ///< Local variable. 80 EOP_Dot, ///< Field access 81 EOP_Call, ///< Function call 82 EOP_MCall, ///< Method call 83 EOP_Index, ///< Array index 84 EOP_Unary, ///< Unary operation 85 EOP_Binary, ///< Binary operation 86 EOP_Unknown ///< Catchall for everything else 87 }; 88 89 90 class SExprNode { 91 private: 92 unsigned char Op; ///< Opcode of the root node 93 unsigned char Flags; ///< Additional opcode-specific data 94 unsigned short Sz; ///< Number of child nodes 95 const void* Data; ///< Additional opcode-specific data 96 97 public: 98 SExprNode(ExprOp O, unsigned F, const void* D) 99 : Op(static_cast<unsigned char>(O)), 100 Flags(static_cast<unsigned char>(F)), Sz(1), Data(D) 101 { } 102 103 unsigned size() const { return Sz; } 104 void setSize(unsigned S) { Sz = S; } 105 106 ExprOp kind() const { return static_cast<ExprOp>(Op); } 107 108 const NamedDecl* getNamedDecl() const { 109 assert(Op == EOP_NVar || Op == EOP_LVar || Op == EOP_Dot); 110 return reinterpret_cast<const NamedDecl*>(Data); 111 } 112 113 const NamedDecl* getFunctionDecl() const { 114 assert(Op == EOP_Call || Op == EOP_MCall); 115 return reinterpret_cast<const NamedDecl*>(Data); 116 } 117 118 bool isArrow() const { return Op == EOP_Dot && Flags == 1; } 119 void setArrow(bool A) { Flags = A ? 1 : 0; } 120 121 unsigned arity() const { 122 switch (Op) { 123 case EOP_Nop: return 0; 124 case EOP_Wildcard: return 0; 125 case EOP_Universal: return 0; 126 case EOP_NVar: return 0; 127 case EOP_LVar: return 0; 128 case EOP_This: return 0; 129 case EOP_Dot: return 1; 130 case EOP_Call: return Flags+1; // First arg is function. 131 case EOP_MCall: return Flags+1; // First arg is implicit obj. 132 case EOP_Index: return 2; 133 case EOP_Unary: return 1; 134 case EOP_Binary: return 2; 135 case EOP_Unknown: return Flags; 136 } 137 return 0; 138 } 139 140 bool operator==(const SExprNode& Other) const { 141 // Ignore flags and size -- they don't matter. 142 return (Op == Other.Op && 143 Data == Other.Data); 144 } 145 146 bool operator!=(const SExprNode& Other) const { 147 return !(*this == Other); 148 } 149 150 bool matches(const SExprNode& Other) const { 151 return (*this == Other) || 152 (Op == EOP_Wildcard) || 153 (Other.Op == EOP_Wildcard); 154 } 155 }; 156 157 158 /// \brief Encapsulates the lexical context of a function call. The lexical 159 /// context includes the arguments to the call, including the implicit object 160 /// argument. When an attribute containing a mutex expression is attached to 161 /// a method, the expression may refer to formal parameters of the method. 162 /// Actual arguments must be substituted for formal parameters to derive 163 /// the appropriate mutex expression in the lexical context where the function 164 /// is called. PrevCtx holds the context in which the arguments themselves 165 /// should be evaluated; multiple calling contexts can be chained together 166 /// by the lock_returned attribute. 167 struct CallingContext { 168 const NamedDecl* AttrDecl; // The decl to which the attribute is attached. 169 const Expr* SelfArg; // Implicit object argument -- e.g. 'this' 170 bool SelfArrow; // is Self referred to with -> or .? 171 unsigned NumArgs; // Number of funArgs 172 const Expr* const* FunArgs; // Function arguments 173 CallingContext* PrevCtx; // The previous context; or 0 if none. 174 175 CallingContext(const NamedDecl *D = 0, const Expr *S = 0, 176 unsigned N = 0, const Expr* const *A = 0, 177 CallingContext *P = 0) 178 : AttrDecl(D), SelfArg(S), SelfArrow(false), 179 NumArgs(N), FunArgs(A), PrevCtx(P) 180 { } 181 }; 182 183 typedef SmallVector<SExprNode, 4> NodeVector; 184 185private: 186 // A SExpr is a list of SExprNodes in prefix order. The Size field allows 187 // the list to be traversed as a tree. 188 NodeVector NodeVec; 189 190private: 191 unsigned makeNop() { 192 NodeVec.push_back(SExprNode(EOP_Nop, 0, 0)); 193 return NodeVec.size()-1; 194 } 195 196 unsigned makeWildcard() { 197 NodeVec.push_back(SExprNode(EOP_Wildcard, 0, 0)); 198 return NodeVec.size()-1; 199 } 200 201 unsigned makeUniversal() { 202 NodeVec.push_back(SExprNode(EOP_Universal, 0, 0)); 203 return NodeVec.size()-1; 204 } 205 206 unsigned makeNamedVar(const NamedDecl *D) { 207 NodeVec.push_back(SExprNode(EOP_NVar, 0, D)); 208 return NodeVec.size()-1; 209 } 210 211 unsigned makeLocalVar(const NamedDecl *D) { 212 NodeVec.push_back(SExprNode(EOP_LVar, 0, D)); 213 return NodeVec.size()-1; 214 } 215 216 unsigned makeThis() { 217 NodeVec.push_back(SExprNode(EOP_This, 0, 0)); 218 return NodeVec.size()-1; 219 } 220 221 unsigned makeDot(const NamedDecl *D, bool Arrow) { 222 NodeVec.push_back(SExprNode(EOP_Dot, Arrow ? 1 : 0, D)); 223 return NodeVec.size()-1; 224 } 225 226 unsigned makeCall(unsigned NumArgs, const NamedDecl *D) { 227 NodeVec.push_back(SExprNode(EOP_Call, NumArgs, D)); 228 return NodeVec.size()-1; 229 } 230 231 // Grab the very first declaration of virtual method D 232 const CXXMethodDecl* getFirstVirtualDecl(const CXXMethodDecl *D) { 233 while (true) { 234 D = D->getCanonicalDecl(); 235 CXXMethodDecl::method_iterator I = D->begin_overridden_methods(), 236 E = D->end_overridden_methods(); 237 if (I == E) 238 return D; // Method does not override anything 239 D = *I; // FIXME: this does not work with multiple inheritance. 240 } 241 return 0; 242 } 243 244 unsigned makeMCall(unsigned NumArgs, const CXXMethodDecl *D) { 245 NodeVec.push_back(SExprNode(EOP_MCall, NumArgs, getFirstVirtualDecl(D))); 246 return NodeVec.size()-1; 247 } 248 249 unsigned makeIndex() { 250 NodeVec.push_back(SExprNode(EOP_Index, 0, 0)); 251 return NodeVec.size()-1; 252 } 253 254 unsigned makeUnary() { 255 NodeVec.push_back(SExprNode(EOP_Unary, 0, 0)); 256 return NodeVec.size()-1; 257 } 258 259 unsigned makeBinary() { 260 NodeVec.push_back(SExprNode(EOP_Binary, 0, 0)); 261 return NodeVec.size()-1; 262 } 263 264 unsigned makeUnknown(unsigned Arity) { 265 NodeVec.push_back(SExprNode(EOP_Unknown, Arity, 0)); 266 return NodeVec.size()-1; 267 } 268 269 inline bool isCalleeArrow(const Expr *E) { 270 const MemberExpr *ME = dyn_cast<MemberExpr>(E->IgnoreParenCasts()); 271 return ME ? ME->isArrow() : false; 272 } 273 274 /// Build an SExpr from the given C++ expression. 275 /// Recursive function that terminates on DeclRefExpr. 276 /// Note: this function merely creates a SExpr; it does not check to 277 /// ensure that the original expression is a valid mutex expression. 278 /// 279 /// NDeref returns the number of Derefence and AddressOf operations 280 /// preceeding the Expr; this is used to decide whether to pretty-print 281 /// SExprs with . or ->. 282 unsigned buildSExpr(const Expr *Exp, CallingContext* CallCtx, 283 int* NDeref = 0) { 284 if (!Exp) 285 return 0; 286 287 if (const DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(Exp)) { 288 const NamedDecl *ND = cast<NamedDecl>(DRE->getDecl()->getCanonicalDecl()); 289 const ParmVarDecl *PV = dyn_cast_or_null<ParmVarDecl>(ND); 290 if (PV) { 291 const FunctionDecl *FD = 292 cast<FunctionDecl>(PV->getDeclContext())->getCanonicalDecl(); 293 unsigned i = PV->getFunctionScopeIndex(); 294 295 if (CallCtx && CallCtx->FunArgs && 296 FD == CallCtx->AttrDecl->getCanonicalDecl()) { 297 // Substitute call arguments for references to function parameters 298 assert(i < CallCtx->NumArgs); 299 return buildSExpr(CallCtx->FunArgs[i], CallCtx->PrevCtx, NDeref); 300 } 301 // Map the param back to the param of the original function declaration. 302 makeNamedVar(FD->getParamDecl(i)); 303 return 1; 304 } 305 // Not a function parameter -- just store the reference. 306 makeNamedVar(ND); 307 return 1; 308 } else if (isa<CXXThisExpr>(Exp)) { 309 // Substitute parent for 'this' 310 if (CallCtx && CallCtx->SelfArg) { 311 if (!CallCtx->SelfArrow && NDeref) 312 // 'this' is a pointer, but self is not, so need to take address. 313 --(*NDeref); 314 return buildSExpr(CallCtx->SelfArg, CallCtx->PrevCtx, NDeref); 315 } 316 else { 317 makeThis(); 318 return 1; 319 } 320 } else if (const MemberExpr *ME = dyn_cast<MemberExpr>(Exp)) { 321 const NamedDecl *ND = ME->getMemberDecl(); 322 int ImplicitDeref = ME->isArrow() ? 1 : 0; 323 unsigned Root = makeDot(ND, false); 324 unsigned Sz = buildSExpr(ME->getBase(), CallCtx, &ImplicitDeref); 325 NodeVec[Root].setArrow(ImplicitDeref > 0); 326 NodeVec[Root].setSize(Sz + 1); 327 return Sz + 1; 328 } else if (const CXXMemberCallExpr *CMCE = dyn_cast<CXXMemberCallExpr>(Exp)) { 329 // When calling a function with a lock_returned attribute, replace 330 // the function call with the expression in lock_returned. 331 const CXXMethodDecl *MD = CMCE->getMethodDecl()->getMostRecentDecl(); 332 if (LockReturnedAttr* At = MD->getAttr<LockReturnedAttr>()) { 333 CallingContext LRCallCtx(CMCE->getMethodDecl()); 334 LRCallCtx.SelfArg = CMCE->getImplicitObjectArgument(); 335 LRCallCtx.SelfArrow = isCalleeArrow(CMCE->getCallee()); 336 LRCallCtx.NumArgs = CMCE->getNumArgs(); 337 LRCallCtx.FunArgs = CMCE->getArgs(); 338 LRCallCtx.PrevCtx = CallCtx; 339 return buildSExpr(At->getArg(), &LRCallCtx); 340 } 341 // Hack to treat smart pointers and iterators as pointers; 342 // ignore any method named get(). 343 if (CMCE->getMethodDecl()->getNameAsString() == "get" && 344 CMCE->getNumArgs() == 0) { 345 if (NDeref && isCalleeArrow(CMCE->getCallee())) 346 ++(*NDeref); 347 return buildSExpr(CMCE->getImplicitObjectArgument(), CallCtx, NDeref); 348 } 349 unsigned NumCallArgs = CMCE->getNumArgs(); 350 unsigned Root = makeMCall(NumCallArgs, CMCE->getMethodDecl()); 351 unsigned Sz = buildSExpr(CMCE->getImplicitObjectArgument(), CallCtx); 352 const Expr* const* CallArgs = CMCE->getArgs(); 353 for (unsigned i = 0; i < NumCallArgs; ++i) { 354 Sz += buildSExpr(CallArgs[i], CallCtx); 355 } 356 NodeVec[Root].setSize(Sz + 1); 357 return Sz + 1; 358 } else if (const CallExpr *CE = dyn_cast<CallExpr>(Exp)) { 359 const FunctionDecl *FD = CE->getDirectCallee()->getMostRecentDecl(); 360 if (LockReturnedAttr* At = FD->getAttr<LockReturnedAttr>()) { 361 CallingContext LRCallCtx(CE->getDirectCallee()); 362 LRCallCtx.NumArgs = CE->getNumArgs(); 363 LRCallCtx.FunArgs = CE->getArgs(); 364 LRCallCtx.PrevCtx = CallCtx; 365 return buildSExpr(At->getArg(), &LRCallCtx); 366 } 367 // Treat smart pointers and iterators as pointers; 368 // ignore the * and -> operators. 369 if (const CXXOperatorCallExpr *OE = dyn_cast<CXXOperatorCallExpr>(CE)) { 370 OverloadedOperatorKind k = OE->getOperator(); 371 if (k == OO_Star) { 372 if (NDeref) ++(*NDeref); 373 return buildSExpr(OE->getArg(0), CallCtx, NDeref); 374 } 375 else if (k == OO_Arrow) { 376 return buildSExpr(OE->getArg(0), CallCtx, NDeref); 377 } 378 } 379 unsigned NumCallArgs = CE->getNumArgs(); 380 unsigned Root = makeCall(NumCallArgs, 0); 381 unsigned Sz = buildSExpr(CE->getCallee(), CallCtx); 382 const Expr* const* CallArgs = CE->getArgs(); 383 for (unsigned i = 0; i < NumCallArgs; ++i) { 384 Sz += buildSExpr(CallArgs[i], CallCtx); 385 } 386 NodeVec[Root].setSize(Sz+1); 387 return Sz+1; 388 } else if (const BinaryOperator *BOE = dyn_cast<BinaryOperator>(Exp)) { 389 unsigned Root = makeBinary(); 390 unsigned Sz = buildSExpr(BOE->getLHS(), CallCtx); 391 Sz += buildSExpr(BOE->getRHS(), CallCtx); 392 NodeVec[Root].setSize(Sz); 393 return Sz; 394 } else if (const UnaryOperator *UOE = dyn_cast<UnaryOperator>(Exp)) { 395 // Ignore & and * operators -- they're no-ops. 396 // However, we try to figure out whether the expression is a pointer, 397 // so we can use . and -> appropriately in error messages. 398 if (UOE->getOpcode() == UO_Deref) { 399 if (NDeref) ++(*NDeref); 400 return buildSExpr(UOE->getSubExpr(), CallCtx, NDeref); 401 } 402 if (UOE->getOpcode() == UO_AddrOf) { 403 if (DeclRefExpr* DRE = dyn_cast<DeclRefExpr>(UOE->getSubExpr())) { 404 if (DRE->getDecl()->isCXXInstanceMember()) { 405 // This is a pointer-to-member expression, e.g. &MyClass::mu_. 406 // We interpret this syntax specially, as a wildcard. 407 unsigned Root = makeDot(DRE->getDecl(), false); 408 makeWildcard(); 409 NodeVec[Root].setSize(2); 410 return 2; 411 } 412 } 413 if (NDeref) --(*NDeref); 414 return buildSExpr(UOE->getSubExpr(), CallCtx, NDeref); 415 } 416 unsigned Root = makeUnary(); 417 unsigned Sz = buildSExpr(UOE->getSubExpr(), CallCtx); 418 NodeVec[Root].setSize(Sz); 419 return Sz; 420 } else if (const ArraySubscriptExpr *ASE = 421 dyn_cast<ArraySubscriptExpr>(Exp)) { 422 unsigned Root = makeIndex(); 423 unsigned Sz = buildSExpr(ASE->getBase(), CallCtx); 424 Sz += buildSExpr(ASE->getIdx(), CallCtx); 425 NodeVec[Root].setSize(Sz); 426 return Sz; 427 } else if (const AbstractConditionalOperator *CE = 428 dyn_cast<AbstractConditionalOperator>(Exp)) { 429 unsigned Root = makeUnknown(3); 430 unsigned Sz = buildSExpr(CE->getCond(), CallCtx); 431 Sz += buildSExpr(CE->getTrueExpr(), CallCtx); 432 Sz += buildSExpr(CE->getFalseExpr(), CallCtx); 433 NodeVec[Root].setSize(Sz); 434 return Sz; 435 } else if (const ChooseExpr *CE = dyn_cast<ChooseExpr>(Exp)) { 436 unsigned Root = makeUnknown(3); 437 unsigned Sz = buildSExpr(CE->getCond(), CallCtx); 438 Sz += buildSExpr(CE->getLHS(), CallCtx); 439 Sz += buildSExpr(CE->getRHS(), CallCtx); 440 NodeVec[Root].setSize(Sz); 441 return Sz; 442 } else if (const CastExpr *CE = dyn_cast<CastExpr>(Exp)) { 443 return buildSExpr(CE->getSubExpr(), CallCtx, NDeref); 444 } else if (const ParenExpr *PE = dyn_cast<ParenExpr>(Exp)) { 445 return buildSExpr(PE->getSubExpr(), CallCtx, NDeref); 446 } else if (const ExprWithCleanups *EWC = dyn_cast<ExprWithCleanups>(Exp)) { 447 return buildSExpr(EWC->getSubExpr(), CallCtx, NDeref); 448 } else if (const CXXBindTemporaryExpr *E = dyn_cast<CXXBindTemporaryExpr>(Exp)) { 449 return buildSExpr(E->getSubExpr(), CallCtx, NDeref); 450 } else if (isa<CharacterLiteral>(Exp) || 451 isa<CXXNullPtrLiteralExpr>(Exp) || 452 isa<GNUNullExpr>(Exp) || 453 isa<CXXBoolLiteralExpr>(Exp) || 454 isa<FloatingLiteral>(Exp) || 455 isa<ImaginaryLiteral>(Exp) || 456 isa<IntegerLiteral>(Exp) || 457 isa<StringLiteral>(Exp) || 458 isa<ObjCStringLiteral>(Exp)) { 459 makeNop(); 460 return 1; // FIXME: Ignore literals for now 461 } else { 462 makeNop(); 463 return 1; // Ignore. FIXME: mark as invalid expression? 464 } 465 } 466 467 /// \brief Construct a SExpr from an expression. 468 /// \param MutexExp The original mutex expression within an attribute 469 /// \param DeclExp An expression involving the Decl on which the attribute 470 /// occurs. 471 /// \param D The declaration to which the lock/unlock attribute is attached. 472 void buildSExprFromExpr(const Expr *MutexExp, const Expr *DeclExp, 473 const NamedDecl *D, VarDecl *SelfDecl = 0) { 474 CallingContext CallCtx(D); 475 476 if (MutexExp) { 477 if (const StringLiteral* SLit = dyn_cast<StringLiteral>(MutexExp)) { 478 if (SLit->getString() == StringRef("*")) 479 // The "*" expr is a universal lock, which essentially turns off 480 // checks until it is removed from the lockset. 481 makeUniversal(); 482 else 483 // Ignore other string literals for now. 484 makeNop(); 485 return; 486 } 487 } 488 489 // If we are processing a raw attribute expression, with no substitutions. 490 if (DeclExp == 0) { 491 buildSExpr(MutexExp, 0); 492 return; 493 } 494 495 // Examine DeclExp to find SelfArg and FunArgs, which are used to substitute 496 // for formal parameters when we call buildMutexID later. 497 if (const MemberExpr *ME = dyn_cast<MemberExpr>(DeclExp)) { 498 CallCtx.SelfArg = ME->getBase(); 499 CallCtx.SelfArrow = ME->isArrow(); 500 } else if (const CXXMemberCallExpr *CE = 501 dyn_cast<CXXMemberCallExpr>(DeclExp)) { 502 CallCtx.SelfArg = CE->getImplicitObjectArgument(); 503 CallCtx.SelfArrow = isCalleeArrow(CE->getCallee()); 504 CallCtx.NumArgs = CE->getNumArgs(); 505 CallCtx.FunArgs = CE->getArgs(); 506 } else if (const CallExpr *CE = dyn_cast<CallExpr>(DeclExp)) { 507 CallCtx.NumArgs = CE->getNumArgs(); 508 CallCtx.FunArgs = CE->getArgs(); 509 } else if (const CXXConstructExpr *CE = 510 dyn_cast<CXXConstructExpr>(DeclExp)) { 511 CallCtx.SelfArg = 0; // Will be set below 512 CallCtx.NumArgs = CE->getNumArgs(); 513 CallCtx.FunArgs = CE->getArgs(); 514 } else if (D && isa<CXXDestructorDecl>(D)) { 515 // There's no such thing as a "destructor call" in the AST. 516 CallCtx.SelfArg = DeclExp; 517 } 518 519 // Hack to handle constructors, where self cannot be recovered from 520 // the expression. 521 if (SelfDecl && !CallCtx.SelfArg) { 522 DeclRefExpr SelfDRE(SelfDecl, false, SelfDecl->getType(), VK_LValue, 523 SelfDecl->getLocation()); 524 CallCtx.SelfArg = &SelfDRE; 525 526 // If the attribute has no arguments, then assume the argument is "this". 527 if (MutexExp == 0) 528 buildSExpr(CallCtx.SelfArg, 0); 529 else // For most attributes. 530 buildSExpr(MutexExp, &CallCtx); 531 return; 532 } 533 534 // If the attribute has no arguments, then assume the argument is "this". 535 if (MutexExp == 0) 536 buildSExpr(CallCtx.SelfArg, 0); 537 else // For most attributes. 538 buildSExpr(MutexExp, &CallCtx); 539 } 540 541 /// \brief Get index of next sibling of node i. 542 unsigned getNextSibling(unsigned i) const { 543 return i + NodeVec[i].size(); 544 } 545 546public: 547 explicit SExpr(clang::Decl::EmptyShell e) { NodeVec.clear(); } 548 549 /// \param MutexExp The original mutex expression within an attribute 550 /// \param DeclExp An expression involving the Decl on which the attribute 551 /// occurs. 552 /// \param D The declaration to which the lock/unlock attribute is attached. 553 /// Caller must check isValid() after construction. 554 SExpr(const Expr* MutexExp, const Expr *DeclExp, const NamedDecl* D, 555 VarDecl *SelfDecl=0) { 556 buildSExprFromExpr(MutexExp, DeclExp, D, SelfDecl); 557 } 558 559 /// Return true if this is a valid decl sequence. 560 /// Caller must call this by hand after construction to handle errors. 561 bool isValid() const { 562 return !NodeVec.empty(); 563 } 564 565 bool shouldIgnore() const { 566 // Nop is a mutex that we have decided to deliberately ignore. 567 assert(NodeVec.size() > 0 && "Invalid Mutex"); 568 return NodeVec[0].kind() == EOP_Nop; 569 } 570 571 bool isUniversal() const { 572 assert(NodeVec.size() > 0 && "Invalid Mutex"); 573 return NodeVec[0].kind() == EOP_Universal; 574 } 575 576 /// Issue a warning about an invalid lock expression 577 static void warnInvalidLock(ThreadSafetyHandler &Handler, 578 const Expr *MutexExp, 579 const Expr *DeclExp, const NamedDecl* D) { 580 SourceLocation Loc; 581 if (DeclExp) 582 Loc = DeclExp->getExprLoc(); 583 584 // FIXME: add a note about the attribute location in MutexExp or D 585 if (Loc.isValid()) 586 Handler.handleInvalidLockExp(Loc); 587 } 588 589 bool operator==(const SExpr &other) const { 590 return NodeVec == other.NodeVec; 591 } 592 593 bool operator!=(const SExpr &other) const { 594 return !(*this == other); 595 } 596 597 bool matches(const SExpr &Other, unsigned i = 0, unsigned j = 0) const { 598 if (NodeVec[i].matches(Other.NodeVec[j])) { 599 unsigned ni = NodeVec[i].arity(); 600 unsigned nj = Other.NodeVec[j].arity(); 601 unsigned n = (ni < nj) ? ni : nj; 602 bool Result = true; 603 unsigned ci = i+1; // first child of i 604 unsigned cj = j+1; // first child of j 605 for (unsigned k = 0; k < n; 606 ++k, ci=getNextSibling(ci), cj = Other.getNextSibling(cj)) { 607 Result = Result && matches(Other, ci, cj); 608 } 609 return Result; 610 } 611 return false; 612 } 613 614 // A partial match between a.mu and b.mu returns true a and b have the same 615 // type (and thus mu refers to the same mutex declaration), regardless of 616 // whether a and b are different objects or not. 617 bool partiallyMatches(const SExpr &Other) const { 618 if (NodeVec[0].kind() == EOP_Dot) 619 return NodeVec[0].matches(Other.NodeVec[0]); 620 return false; 621 } 622 623 /// \brief Pretty print a lock expression for use in error messages. 624 std::string toString(unsigned i = 0) const { 625 assert(isValid()); 626 if (i >= NodeVec.size()) 627 return ""; 628 629 const SExprNode* N = &NodeVec[i]; 630 switch (N->kind()) { 631 case EOP_Nop: 632 return "_"; 633 case EOP_Wildcard: 634 return "(?)"; 635 case EOP_Universal: 636 return "*"; 637 case EOP_This: 638 return "this"; 639 case EOP_NVar: 640 case EOP_LVar: { 641 return N->getNamedDecl()->getNameAsString(); 642 } 643 case EOP_Dot: { 644 if (NodeVec[i+1].kind() == EOP_Wildcard) { 645 std::string S = "&"; 646 S += N->getNamedDecl()->getQualifiedNameAsString(); 647 return S; 648 } 649 std::string FieldName = N->getNamedDecl()->getNameAsString(); 650 if (NodeVec[i+1].kind() == EOP_This) 651 return FieldName; 652 653 std::string S = toString(i+1); 654 if (N->isArrow()) 655 return S + "->" + FieldName; 656 else 657 return S + "." + FieldName; 658 } 659 case EOP_Call: { 660 std::string S = toString(i+1) + "("; 661 unsigned NumArgs = N->arity()-1; 662 unsigned ci = getNextSibling(i+1); 663 for (unsigned k=0; k<NumArgs; ++k, ci = getNextSibling(ci)) { 664 S += toString(ci); 665 if (k+1 < NumArgs) S += ","; 666 } 667 S += ")"; 668 return S; 669 } 670 case EOP_MCall: { 671 std::string S = ""; 672 if (NodeVec[i+1].kind() != EOP_This) 673 S = toString(i+1) + "."; 674 if (const NamedDecl *D = N->getFunctionDecl()) 675 S += D->getNameAsString() + "("; 676 else 677 S += "#("; 678 unsigned NumArgs = N->arity()-1; 679 unsigned ci = getNextSibling(i+1); 680 for (unsigned k=0; k<NumArgs; ++k, ci = getNextSibling(ci)) { 681 S += toString(ci); 682 if (k+1 < NumArgs) S += ","; 683 } 684 S += ")"; 685 return S; 686 } 687 case EOP_Index: { 688 std::string S1 = toString(i+1); 689 std::string S2 = toString(i+1 + NodeVec[i+1].size()); 690 return S1 + "[" + S2 + "]"; 691 } 692 case EOP_Unary: { 693 std::string S = toString(i+1); 694 return "#" + S; 695 } 696 case EOP_Binary: { 697 std::string S1 = toString(i+1); 698 std::string S2 = toString(i+1 + NodeVec[i+1].size()); 699 return "(" + S1 + "#" + S2 + ")"; 700 } 701 case EOP_Unknown: { 702 unsigned NumChildren = N->arity(); 703 if (NumChildren == 0) 704 return "(...)"; 705 std::string S = "("; 706 unsigned ci = i+1; 707 for (unsigned j = 0; j < NumChildren; ++j, ci = getNextSibling(ci)) { 708 S += toString(ci); 709 if (j+1 < NumChildren) S += "#"; 710 } 711 S += ")"; 712 return S; 713 } 714 } 715 return ""; 716 } 717}; 718 719 720 721/// \brief A short list of SExprs 722class MutexIDList : public SmallVector<SExpr, 3> { 723public: 724 /// \brief Return true if the list contains the specified SExpr 725 /// Performs a linear search, because these lists are almost always very small. 726 bool contains(const SExpr& M) { 727 for (iterator I=begin(),E=end(); I != E; ++I) 728 if ((*I) == M) return true; 729 return false; 730 } 731 732 /// \brief Push M onto list, bud discard duplicates 733 void push_back_nodup(const SExpr& M) { 734 if (!contains(M)) push_back(M); 735 } 736}; 737 738 739 740/// \brief This is a helper class that stores info about the most recent 741/// accquire of a Lock. 742/// 743/// The main body of the analysis maps MutexIDs to LockDatas. 744struct LockData { 745 SourceLocation AcquireLoc; 746 747 /// \brief LKind stores whether a lock is held shared or exclusively. 748 /// Note that this analysis does not currently support either re-entrant 749 /// locking or lock "upgrading" and "downgrading" between exclusive and 750 /// shared. 751 /// 752 /// FIXME: add support for re-entrant locking and lock up/downgrading 753 LockKind LKind; 754 bool Asserted; // for asserted locks 755 bool Managed; // for ScopedLockable objects 756 SExpr UnderlyingMutex; // for ScopedLockable objects 757 758 LockData(SourceLocation AcquireLoc, LockKind LKind, bool M=false, 759 bool Asrt=false) 760 : AcquireLoc(AcquireLoc), LKind(LKind), Asserted(Asrt), Managed(M), 761 UnderlyingMutex(Decl::EmptyShell()) 762 {} 763 764 LockData(SourceLocation AcquireLoc, LockKind LKind, const SExpr &Mu) 765 : AcquireLoc(AcquireLoc), LKind(LKind), Asserted(false), Managed(false), 766 UnderlyingMutex(Mu) 767 {} 768 769 bool operator==(const LockData &other) const { 770 return AcquireLoc == other.AcquireLoc && LKind == other.LKind; 771 } 772 773 bool operator!=(const LockData &other) const { 774 return !(*this == other); 775 } 776 777 void Profile(llvm::FoldingSetNodeID &ID) const { 778 ID.AddInteger(AcquireLoc.getRawEncoding()); 779 ID.AddInteger(LKind); 780 } 781 782 bool isAtLeast(LockKind LK) { 783 return (LK == LK_Shared) || (LKind == LK_Exclusive); 784 } 785}; 786 787 788/// \brief A FactEntry stores a single fact that is known at a particular point 789/// in the program execution. Currently, this is information regarding a lock 790/// that is held at that point. 791struct FactEntry { 792 SExpr MutID; 793 LockData LDat; 794 795 FactEntry(const SExpr& M, const LockData& L) 796 : MutID(M), LDat(L) 797 { } 798}; 799 800 801typedef unsigned short FactID; 802 803/// \brief FactManager manages the memory for all facts that are created during 804/// the analysis of a single routine. 805class FactManager { 806private: 807 std::vector<FactEntry> Facts; 808 809public: 810 FactID newLock(const SExpr& M, const LockData& L) { 811 Facts.push_back(FactEntry(M,L)); 812 return static_cast<unsigned short>(Facts.size() - 1); 813 } 814 815 const FactEntry& operator[](FactID F) const { return Facts[F]; } 816 FactEntry& operator[](FactID F) { return Facts[F]; } 817}; 818 819 820/// \brief A FactSet is the set of facts that are known to be true at a 821/// particular program point. FactSets must be small, because they are 822/// frequently copied, and are thus implemented as a set of indices into a 823/// table maintained by a FactManager. A typical FactSet only holds 1 or 2 824/// locks, so we can get away with doing a linear search for lookup. Note 825/// that a hashtable or map is inappropriate in this case, because lookups 826/// may involve partial pattern matches, rather than exact matches. 827class FactSet { 828private: 829 typedef SmallVector<FactID, 4> FactVec; 830 831 FactVec FactIDs; 832 833public: 834 typedef FactVec::iterator iterator; 835 typedef FactVec::const_iterator const_iterator; 836 837 iterator begin() { return FactIDs.begin(); } 838 const_iterator begin() const { return FactIDs.begin(); } 839 840 iterator end() { return FactIDs.end(); } 841 const_iterator end() const { return FactIDs.end(); } 842 843 bool isEmpty() const { return FactIDs.size() == 0; } 844 845 FactID addLock(FactManager& FM, const SExpr& M, const LockData& L) { 846 FactID F = FM.newLock(M, L); 847 FactIDs.push_back(F); 848 return F; 849 } 850 851 bool removeLock(FactManager& FM, const SExpr& M) { 852 unsigned n = FactIDs.size(); 853 if (n == 0) 854 return false; 855 856 for (unsigned i = 0; i < n-1; ++i) { 857 if (FM[FactIDs[i]].MutID.matches(M)) { 858 FactIDs[i] = FactIDs[n-1]; 859 FactIDs.pop_back(); 860 return true; 861 } 862 } 863 if (FM[FactIDs[n-1]].MutID.matches(M)) { 864 FactIDs.pop_back(); 865 return true; 866 } 867 return false; 868 } 869 870 // Returns an iterator 871 iterator findLockIter(FactManager &FM, const SExpr &M) { 872 for (iterator I = begin(), E = end(); I != E; ++I) { 873 const SExpr &Exp = FM[*I].MutID; 874 if (Exp.matches(M)) 875 return I; 876 } 877 return end(); 878 } 879 880 LockData* findLock(FactManager &FM, const SExpr &M) const { 881 for (const_iterator I = begin(), E = end(); I != E; ++I) { 882 const SExpr &Exp = FM[*I].MutID; 883 if (Exp.matches(M)) 884 return &FM[*I].LDat; 885 } 886 return 0; 887 } 888 889 LockData* findLockUniv(FactManager &FM, const SExpr &M) const { 890 for (const_iterator I = begin(), E = end(); I != E; ++I) { 891 const SExpr &Exp = FM[*I].MutID; 892 if (Exp.matches(M) || Exp.isUniversal()) 893 return &FM[*I].LDat; 894 } 895 return 0; 896 } 897 898 FactEntry* findPartialMatch(FactManager &FM, const SExpr &M) const { 899 for (const_iterator I=begin(), E=end(); I != E; ++I) { 900 const SExpr& Exp = FM[*I].MutID; 901 if (Exp.partiallyMatches(M)) return &FM[*I]; 902 } 903 return 0; 904 } 905}; 906 907 908 909/// A Lockset maps each SExpr (defined above) to information about how it has 910/// been locked. 911typedef llvm::ImmutableMap<SExpr, LockData> Lockset; 912typedef llvm::ImmutableMap<const NamedDecl*, unsigned> LocalVarContext; 913 914class LocalVariableMap; 915 916/// A side (entry or exit) of a CFG node. 917enum CFGBlockSide { CBS_Entry, CBS_Exit }; 918 919/// CFGBlockInfo is a struct which contains all the information that is 920/// maintained for each block in the CFG. See LocalVariableMap for more 921/// information about the contexts. 922struct CFGBlockInfo { 923 FactSet EntrySet; // Lockset held at entry to block 924 FactSet ExitSet; // Lockset held at exit from block 925 LocalVarContext EntryContext; // Context held at entry to block 926 LocalVarContext ExitContext; // Context held at exit from block 927 SourceLocation EntryLoc; // Location of first statement in block 928 SourceLocation ExitLoc; // Location of last statement in block. 929 unsigned EntryIndex; // Used to replay contexts later 930 bool Reachable; // Is this block reachable? 931 932 const FactSet &getSet(CFGBlockSide Side) const { 933 return Side == CBS_Entry ? EntrySet : ExitSet; 934 } 935 SourceLocation getLocation(CFGBlockSide Side) const { 936 return Side == CBS_Entry ? EntryLoc : ExitLoc; 937 } 938 939private: 940 CFGBlockInfo(LocalVarContext EmptyCtx) 941 : EntryContext(EmptyCtx), ExitContext(EmptyCtx), Reachable(false) 942 { } 943 944public: 945 static CFGBlockInfo getEmptyBlockInfo(LocalVariableMap &M); 946}; 947 948 949 950// A LocalVariableMap maintains a map from local variables to their currently 951// valid definitions. It provides SSA-like functionality when traversing the 952// CFG. Like SSA, each definition or assignment to a variable is assigned a 953// unique name (an integer), which acts as the SSA name for that definition. 954// The total set of names is shared among all CFG basic blocks. 955// Unlike SSA, we do not rewrite expressions to replace local variables declrefs 956// with their SSA-names. Instead, we compute a Context for each point in the 957// code, which maps local variables to the appropriate SSA-name. This map 958// changes with each assignment. 959// 960// The map is computed in a single pass over the CFG. Subsequent analyses can 961// then query the map to find the appropriate Context for a statement, and use 962// that Context to look up the definitions of variables. 963class LocalVariableMap { 964public: 965 typedef LocalVarContext Context; 966 967 /// A VarDefinition consists of an expression, representing the value of the 968 /// variable, along with the context in which that expression should be 969 /// interpreted. A reference VarDefinition does not itself contain this 970 /// information, but instead contains a pointer to a previous VarDefinition. 971 struct VarDefinition { 972 public: 973 friend class LocalVariableMap; 974 975 const NamedDecl *Dec; // The original declaration for this variable. 976 const Expr *Exp; // The expression for this variable, OR 977 unsigned Ref; // Reference to another VarDefinition 978 Context Ctx; // The map with which Exp should be interpreted. 979 980 bool isReference() { return !Exp; } 981 982 private: 983 // Create ordinary variable definition 984 VarDefinition(const NamedDecl *D, const Expr *E, Context C) 985 : Dec(D), Exp(E), Ref(0), Ctx(C) 986 { } 987 988 // Create reference to previous definition 989 VarDefinition(const NamedDecl *D, unsigned R, Context C) 990 : Dec(D), Exp(0), Ref(R), Ctx(C) 991 { } 992 }; 993 994private: 995 Context::Factory ContextFactory; 996 std::vector<VarDefinition> VarDefinitions; 997 std::vector<unsigned> CtxIndices; 998 std::vector<std::pair<Stmt*, Context> > SavedContexts; 999 1000public: 1001 LocalVariableMap() { 1002 // index 0 is a placeholder for undefined variables (aka phi-nodes). 1003 VarDefinitions.push_back(VarDefinition(0, 0u, getEmptyContext())); 1004 } 1005 1006 /// Look up a definition, within the given context. 1007 const VarDefinition* lookup(const NamedDecl *D, Context Ctx) { 1008 const unsigned *i = Ctx.lookup(D); 1009 if (!i) 1010 return 0; 1011 assert(*i < VarDefinitions.size()); 1012 return &VarDefinitions[*i]; 1013 } 1014 1015 /// Look up the definition for D within the given context. Returns 1016 /// NULL if the expression is not statically known. If successful, also 1017 /// modifies Ctx to hold the context of the return Expr. 1018 const Expr* lookupExpr(const NamedDecl *D, Context &Ctx) { 1019 const unsigned *P = Ctx.lookup(D); 1020 if (!P) 1021 return 0; 1022 1023 unsigned i = *P; 1024 while (i > 0) { 1025 if (VarDefinitions[i].Exp) { 1026 Ctx = VarDefinitions[i].Ctx; 1027 return VarDefinitions[i].Exp; 1028 } 1029 i = VarDefinitions[i].Ref; 1030 } 1031 return 0; 1032 } 1033 1034 Context getEmptyContext() { return ContextFactory.getEmptyMap(); } 1035 1036 /// Return the next context after processing S. This function is used by 1037 /// clients of the class to get the appropriate context when traversing the 1038 /// CFG. It must be called for every assignment or DeclStmt. 1039 Context getNextContext(unsigned &CtxIndex, Stmt *S, Context C) { 1040 if (SavedContexts[CtxIndex+1].first == S) { 1041 CtxIndex++; 1042 Context Result = SavedContexts[CtxIndex].second; 1043 return Result; 1044 } 1045 return C; 1046 } 1047 1048 void dumpVarDefinitionName(unsigned i) { 1049 if (i == 0) { 1050 llvm::errs() << "Undefined"; 1051 return; 1052 } 1053 const NamedDecl *Dec = VarDefinitions[i].Dec; 1054 if (!Dec) { 1055 llvm::errs() << "<<NULL>>"; 1056 return; 1057 } 1058 Dec->printName(llvm::errs()); 1059 llvm::errs() << "." << i << " " << ((const void*) Dec); 1060 } 1061 1062 /// Dumps an ASCII representation of the variable map to llvm::errs() 1063 void dump() { 1064 for (unsigned i = 1, e = VarDefinitions.size(); i < e; ++i) { 1065 const Expr *Exp = VarDefinitions[i].Exp; 1066 unsigned Ref = VarDefinitions[i].Ref; 1067 1068 dumpVarDefinitionName(i); 1069 llvm::errs() << " = "; 1070 if (Exp) Exp->dump(); 1071 else { 1072 dumpVarDefinitionName(Ref); 1073 llvm::errs() << "\n"; 1074 } 1075 } 1076 } 1077 1078 /// Dumps an ASCII representation of a Context to llvm::errs() 1079 void dumpContext(Context C) { 1080 for (Context::iterator I = C.begin(), E = C.end(); I != E; ++I) { 1081 const NamedDecl *D = I.getKey(); 1082 D->printName(llvm::errs()); 1083 const unsigned *i = C.lookup(D); 1084 llvm::errs() << " -> "; 1085 dumpVarDefinitionName(*i); 1086 llvm::errs() << "\n"; 1087 } 1088 } 1089 1090 /// Builds the variable map. 1091 void traverseCFG(CFG *CFGraph, PostOrderCFGView *SortedGraph, 1092 std::vector<CFGBlockInfo> &BlockInfo); 1093 1094protected: 1095 // Get the current context index 1096 unsigned getContextIndex() { return SavedContexts.size()-1; } 1097 1098 // Save the current context for later replay 1099 void saveContext(Stmt *S, Context C) { 1100 SavedContexts.push_back(std::make_pair(S,C)); 1101 } 1102 1103 // Adds a new definition to the given context, and returns a new context. 1104 // This method should be called when declaring a new variable. 1105 Context addDefinition(const NamedDecl *D, Expr *Exp, Context Ctx) { 1106 assert(!Ctx.contains(D)); 1107 unsigned newID = VarDefinitions.size(); 1108 Context NewCtx = ContextFactory.add(Ctx, D, newID); 1109 VarDefinitions.push_back(VarDefinition(D, Exp, Ctx)); 1110 return NewCtx; 1111 } 1112 1113 // Add a new reference to an existing definition. 1114 Context addReference(const NamedDecl *D, unsigned i, Context Ctx) { 1115 unsigned newID = VarDefinitions.size(); 1116 Context NewCtx = ContextFactory.add(Ctx, D, newID); 1117 VarDefinitions.push_back(VarDefinition(D, i, Ctx)); 1118 return NewCtx; 1119 } 1120 1121 // Updates a definition only if that definition is already in the map. 1122 // This method should be called when assigning to an existing variable. 1123 Context updateDefinition(const NamedDecl *D, Expr *Exp, Context Ctx) { 1124 if (Ctx.contains(D)) { 1125 unsigned newID = VarDefinitions.size(); 1126 Context NewCtx = ContextFactory.remove(Ctx, D); 1127 NewCtx = ContextFactory.add(NewCtx, D, newID); 1128 VarDefinitions.push_back(VarDefinition(D, Exp, Ctx)); 1129 return NewCtx; 1130 } 1131 return Ctx; 1132 } 1133 1134 // Removes a definition from the context, but keeps the variable name 1135 // as a valid variable. The index 0 is a placeholder for cleared definitions. 1136 Context clearDefinition(const NamedDecl *D, Context Ctx) { 1137 Context NewCtx = Ctx; 1138 if (NewCtx.contains(D)) { 1139 NewCtx = ContextFactory.remove(NewCtx, D); 1140 NewCtx = ContextFactory.add(NewCtx, D, 0); 1141 } 1142 return NewCtx; 1143 } 1144 1145 // Remove a definition entirely frmo the context. 1146 Context removeDefinition(const NamedDecl *D, Context Ctx) { 1147 Context NewCtx = Ctx; 1148 if (NewCtx.contains(D)) { 1149 NewCtx = ContextFactory.remove(NewCtx, D); 1150 } 1151 return NewCtx; 1152 } 1153 1154 Context intersectContexts(Context C1, Context C2); 1155 Context createReferenceContext(Context C); 1156 void intersectBackEdge(Context C1, Context C2); 1157 1158 friend class VarMapBuilder; 1159}; 1160 1161 1162// This has to be defined after LocalVariableMap. 1163CFGBlockInfo CFGBlockInfo::getEmptyBlockInfo(LocalVariableMap &M) { 1164 return CFGBlockInfo(M.getEmptyContext()); 1165} 1166 1167 1168/// Visitor which builds a LocalVariableMap 1169class VarMapBuilder : public StmtVisitor<VarMapBuilder> { 1170public: 1171 LocalVariableMap* VMap; 1172 LocalVariableMap::Context Ctx; 1173 1174 VarMapBuilder(LocalVariableMap *VM, LocalVariableMap::Context C) 1175 : VMap(VM), Ctx(C) {} 1176 1177 void VisitDeclStmt(DeclStmt *S); 1178 void VisitBinaryOperator(BinaryOperator *BO); 1179}; 1180 1181 1182// Add new local variables to the variable map 1183void VarMapBuilder::VisitDeclStmt(DeclStmt *S) { 1184 bool modifiedCtx = false; 1185 DeclGroupRef DGrp = S->getDeclGroup(); 1186 for (DeclGroupRef::iterator I = DGrp.begin(), E = DGrp.end(); I != E; ++I) { 1187 if (VarDecl *VD = dyn_cast_or_null<VarDecl>(*I)) { 1188 Expr *E = VD->getInit(); 1189 1190 // Add local variables with trivial type to the variable map 1191 QualType T = VD->getType(); 1192 if (T.isTrivialType(VD->getASTContext())) { 1193 Ctx = VMap->addDefinition(VD, E, Ctx); 1194 modifiedCtx = true; 1195 } 1196 } 1197 } 1198 if (modifiedCtx) 1199 VMap->saveContext(S, Ctx); 1200} 1201 1202// Update local variable definitions in variable map 1203void VarMapBuilder::VisitBinaryOperator(BinaryOperator *BO) { 1204 if (!BO->isAssignmentOp()) 1205 return; 1206 1207 Expr *LHSExp = BO->getLHS()->IgnoreParenCasts(); 1208 1209 // Update the variable map and current context. 1210 if (DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(LHSExp)) { 1211 ValueDecl *VDec = DRE->getDecl(); 1212 if (Ctx.lookup(VDec)) { 1213 if (BO->getOpcode() == BO_Assign) 1214 Ctx = VMap->updateDefinition(VDec, BO->getRHS(), Ctx); 1215 else 1216 // FIXME -- handle compound assignment operators 1217 Ctx = VMap->clearDefinition(VDec, Ctx); 1218 VMap->saveContext(BO, Ctx); 1219 } 1220 } 1221} 1222 1223 1224// Computes the intersection of two contexts. The intersection is the 1225// set of variables which have the same definition in both contexts; 1226// variables with different definitions are discarded. 1227LocalVariableMap::Context 1228LocalVariableMap::intersectContexts(Context C1, Context C2) { 1229 Context Result = C1; 1230 for (Context::iterator I = C1.begin(), E = C1.end(); I != E; ++I) { 1231 const NamedDecl *Dec = I.getKey(); 1232 unsigned i1 = I.getData(); 1233 const unsigned *i2 = C2.lookup(Dec); 1234 if (!i2) // variable doesn't exist on second path 1235 Result = removeDefinition(Dec, Result); 1236 else if (*i2 != i1) // variable exists, but has different definition 1237 Result = clearDefinition(Dec, Result); 1238 } 1239 return Result; 1240} 1241 1242// For every variable in C, create a new variable that refers to the 1243// definition in C. Return a new context that contains these new variables. 1244// (We use this for a naive implementation of SSA on loop back-edges.) 1245LocalVariableMap::Context LocalVariableMap::createReferenceContext(Context C) { 1246 Context Result = getEmptyContext(); 1247 for (Context::iterator I = C.begin(), E = C.end(); I != E; ++I) { 1248 const NamedDecl *Dec = I.getKey(); 1249 unsigned i = I.getData(); 1250 Result = addReference(Dec, i, Result); 1251 } 1252 return Result; 1253} 1254 1255// This routine also takes the intersection of C1 and C2, but it does so by 1256// altering the VarDefinitions. C1 must be the result of an earlier call to 1257// createReferenceContext. 1258void LocalVariableMap::intersectBackEdge(Context C1, Context C2) { 1259 for (Context::iterator I = C1.begin(), E = C1.end(); I != E; ++I) { 1260 const NamedDecl *Dec = I.getKey(); 1261 unsigned i1 = I.getData(); 1262 VarDefinition *VDef = &VarDefinitions[i1]; 1263 assert(VDef->isReference()); 1264 1265 const unsigned *i2 = C2.lookup(Dec); 1266 if (!i2 || (*i2 != i1)) 1267 VDef->Ref = 0; // Mark this variable as undefined 1268 } 1269} 1270 1271 1272// Traverse the CFG in topological order, so all predecessors of a block 1273// (excluding back-edges) are visited before the block itself. At 1274// each point in the code, we calculate a Context, which holds the set of 1275// variable definitions which are visible at that point in execution. 1276// Visible variables are mapped to their definitions using an array that 1277// contains all definitions. 1278// 1279// At join points in the CFG, the set is computed as the intersection of 1280// the incoming sets along each edge, E.g. 1281// 1282// { Context | VarDefinitions } 1283// int x = 0; { x -> x1 | x1 = 0 } 1284// int y = 0; { x -> x1, y -> y1 | y1 = 0, x1 = 0 } 1285// if (b) x = 1; { x -> x2, y -> y1 | x2 = 1, y1 = 0, ... } 1286// else x = 2; { x -> x3, y -> y1 | x3 = 2, x2 = 1, ... } 1287// ... { y -> y1 (x is unknown) | x3 = 2, x2 = 1, ... } 1288// 1289// This is essentially a simpler and more naive version of the standard SSA 1290// algorithm. Those definitions that remain in the intersection are from blocks 1291// that strictly dominate the current block. We do not bother to insert proper 1292// phi nodes, because they are not used in our analysis; instead, wherever 1293// a phi node would be required, we simply remove that definition from the 1294// context (E.g. x above). 1295// 1296// The initial traversal does not capture back-edges, so those need to be 1297// handled on a separate pass. Whenever the first pass encounters an 1298// incoming back edge, it duplicates the context, creating new definitions 1299// that refer back to the originals. (These correspond to places where SSA 1300// might have to insert a phi node.) On the second pass, these definitions are 1301// set to NULL if the variable has changed on the back-edge (i.e. a phi 1302// node was actually required.) E.g. 1303// 1304// { Context | VarDefinitions } 1305// int x = 0, y = 0; { x -> x1, y -> y1 | y1 = 0, x1 = 0 } 1306// while (b) { x -> x2, y -> y1 | [1st:] x2=x1; [2nd:] x2=NULL; } 1307// x = x+1; { x -> x3, y -> y1 | x3 = x2 + 1, ... } 1308// ... { y -> y1 | x3 = 2, x2 = 1, ... } 1309// 1310void LocalVariableMap::traverseCFG(CFG *CFGraph, 1311 PostOrderCFGView *SortedGraph, 1312 std::vector<CFGBlockInfo> &BlockInfo) { 1313 PostOrderCFGView::CFGBlockSet VisitedBlocks(CFGraph); 1314 1315 CtxIndices.resize(CFGraph->getNumBlockIDs()); 1316 1317 for (PostOrderCFGView::iterator I = SortedGraph->begin(), 1318 E = SortedGraph->end(); I!= E; ++I) { 1319 const CFGBlock *CurrBlock = *I; 1320 int CurrBlockID = CurrBlock->getBlockID(); 1321 CFGBlockInfo *CurrBlockInfo = &BlockInfo[CurrBlockID]; 1322 1323 VisitedBlocks.insert(CurrBlock); 1324 1325 // Calculate the entry context for the current block 1326 bool HasBackEdges = false; 1327 bool CtxInit = true; 1328 for (CFGBlock::const_pred_iterator PI = CurrBlock->pred_begin(), 1329 PE = CurrBlock->pred_end(); PI != PE; ++PI) { 1330 // if *PI -> CurrBlock is a back edge, so skip it 1331 if (*PI == 0 || !VisitedBlocks.alreadySet(*PI)) { 1332 HasBackEdges = true; 1333 continue; 1334 } 1335 1336 int PrevBlockID = (*PI)->getBlockID(); 1337 CFGBlockInfo *PrevBlockInfo = &BlockInfo[PrevBlockID]; 1338 1339 if (CtxInit) { 1340 CurrBlockInfo->EntryContext = PrevBlockInfo->ExitContext; 1341 CtxInit = false; 1342 } 1343 else { 1344 CurrBlockInfo->EntryContext = 1345 intersectContexts(CurrBlockInfo->EntryContext, 1346 PrevBlockInfo->ExitContext); 1347 } 1348 } 1349 1350 // Duplicate the context if we have back-edges, so we can call 1351 // intersectBackEdges later. 1352 if (HasBackEdges) 1353 CurrBlockInfo->EntryContext = 1354 createReferenceContext(CurrBlockInfo->EntryContext); 1355 1356 // Create a starting context index for the current block 1357 saveContext(0, CurrBlockInfo->EntryContext); 1358 CurrBlockInfo->EntryIndex = getContextIndex(); 1359 1360 // Visit all the statements in the basic block. 1361 VarMapBuilder VMapBuilder(this, CurrBlockInfo->EntryContext); 1362 for (CFGBlock::const_iterator BI = CurrBlock->begin(), 1363 BE = CurrBlock->end(); BI != BE; ++BI) { 1364 switch (BI->getKind()) { 1365 case CFGElement::Statement: { 1366 CFGStmt CS = BI->castAs<CFGStmt>(); 1367 VMapBuilder.Visit(const_cast<Stmt*>(CS.getStmt())); 1368 break; 1369 } 1370 default: 1371 break; 1372 } 1373 } 1374 CurrBlockInfo->ExitContext = VMapBuilder.Ctx; 1375 1376 // Mark variables on back edges as "unknown" if they've been changed. 1377 for (CFGBlock::const_succ_iterator SI = CurrBlock->succ_begin(), 1378 SE = CurrBlock->succ_end(); SI != SE; ++SI) { 1379 // if CurrBlock -> *SI is *not* a back edge 1380 if (*SI == 0 || !VisitedBlocks.alreadySet(*SI)) 1381 continue; 1382 1383 CFGBlock *FirstLoopBlock = *SI; 1384 Context LoopBegin = BlockInfo[FirstLoopBlock->getBlockID()].EntryContext; 1385 Context LoopEnd = CurrBlockInfo->ExitContext; 1386 intersectBackEdge(LoopBegin, LoopEnd); 1387 } 1388 } 1389 1390 // Put an extra entry at the end of the indexed context array 1391 unsigned exitID = CFGraph->getExit().getBlockID(); 1392 saveContext(0, BlockInfo[exitID].ExitContext); 1393} 1394 1395/// Find the appropriate source locations to use when producing diagnostics for 1396/// each block in the CFG. 1397static void findBlockLocations(CFG *CFGraph, 1398 PostOrderCFGView *SortedGraph, 1399 std::vector<CFGBlockInfo> &BlockInfo) { 1400 for (PostOrderCFGView::iterator I = SortedGraph->begin(), 1401 E = SortedGraph->end(); I!= E; ++I) { 1402 const CFGBlock *CurrBlock = *I; 1403 CFGBlockInfo *CurrBlockInfo = &BlockInfo[CurrBlock->getBlockID()]; 1404 1405 // Find the source location of the last statement in the block, if the 1406 // block is not empty. 1407 if (const Stmt *S = CurrBlock->getTerminator()) { 1408 CurrBlockInfo->EntryLoc = CurrBlockInfo->ExitLoc = S->getLocStart(); 1409 } else { 1410 for (CFGBlock::const_reverse_iterator BI = CurrBlock->rbegin(), 1411 BE = CurrBlock->rend(); BI != BE; ++BI) { 1412 // FIXME: Handle other CFGElement kinds. 1413 if (Optional<CFGStmt> CS = BI->getAs<CFGStmt>()) { 1414 CurrBlockInfo->ExitLoc = CS->getStmt()->getLocStart(); 1415 break; 1416 } 1417 } 1418 } 1419 1420 if (!CurrBlockInfo->ExitLoc.isInvalid()) { 1421 // This block contains at least one statement. Find the source location 1422 // of the first statement in the block. 1423 for (CFGBlock::const_iterator BI = CurrBlock->begin(), 1424 BE = CurrBlock->end(); BI != BE; ++BI) { 1425 // FIXME: Handle other CFGElement kinds. 1426 if (Optional<CFGStmt> CS = BI->getAs<CFGStmt>()) { 1427 CurrBlockInfo->EntryLoc = CS->getStmt()->getLocStart(); 1428 break; 1429 } 1430 } 1431 } else if (CurrBlock->pred_size() == 1 && *CurrBlock->pred_begin() && 1432 CurrBlock != &CFGraph->getExit()) { 1433 // The block is empty, and has a single predecessor. Use its exit 1434 // location. 1435 CurrBlockInfo->EntryLoc = CurrBlockInfo->ExitLoc = 1436 BlockInfo[(*CurrBlock->pred_begin())->getBlockID()].ExitLoc; 1437 } 1438 } 1439} 1440 1441/// \brief Class which implements the core thread safety analysis routines. 1442class ThreadSafetyAnalyzer { 1443 friend class BuildLockset; 1444 1445 ThreadSafetyHandler &Handler; 1446 LocalVariableMap LocalVarMap; 1447 FactManager FactMan; 1448 std::vector<CFGBlockInfo> BlockInfo; 1449 1450public: 1451 ThreadSafetyAnalyzer(ThreadSafetyHandler &H) : Handler(H) {} 1452 1453 void addLock(FactSet &FSet, const SExpr &Mutex, const LockData &LDat); 1454 void removeLock(FactSet &FSet, const SExpr &Mutex, 1455 SourceLocation UnlockLoc, bool FullyRemove=false); 1456 1457 template <typename AttrType> 1458 void getMutexIDs(MutexIDList &Mtxs, AttrType *Attr, Expr *Exp, 1459 const NamedDecl *D, VarDecl *SelfDecl=0); 1460 1461 template <class AttrType> 1462 void getMutexIDs(MutexIDList &Mtxs, AttrType *Attr, Expr *Exp, 1463 const NamedDecl *D, 1464 const CFGBlock *PredBlock, const CFGBlock *CurrBlock, 1465 Expr *BrE, bool Neg); 1466 1467 const CallExpr* getTrylockCallExpr(const Stmt *Cond, LocalVarContext C, 1468 bool &Negate); 1469 1470 void getEdgeLockset(FactSet &Result, const FactSet &ExitSet, 1471 const CFGBlock* PredBlock, 1472 const CFGBlock *CurrBlock); 1473 1474 void intersectAndWarn(FactSet &FSet1, const FactSet &FSet2, 1475 SourceLocation JoinLoc, 1476 LockErrorKind LEK1, LockErrorKind LEK2, 1477 bool Modify=true); 1478 1479 void intersectAndWarn(FactSet &FSet1, const FactSet &FSet2, 1480 SourceLocation JoinLoc, LockErrorKind LEK1, 1481 bool Modify=true) { 1482 intersectAndWarn(FSet1, FSet2, JoinLoc, LEK1, LEK1, Modify); 1483 } 1484 1485 void runAnalysis(AnalysisDeclContext &AC); 1486}; 1487 1488 1489/// \brief Add a new lock to the lockset, warning if the lock is already there. 1490/// \param Mutex -- the Mutex expression for the lock 1491/// \param LDat -- the LockData for the lock 1492void ThreadSafetyAnalyzer::addLock(FactSet &FSet, const SExpr &Mutex, 1493 const LockData &LDat) { 1494 // FIXME: deal with acquired before/after annotations. 1495 // FIXME: Don't always warn when we have support for reentrant locks. 1496 if (Mutex.shouldIgnore()) 1497 return; 1498 1499 if (FSet.findLock(FactMan, Mutex)) { 1500 if (!LDat.Asserted) 1501 Handler.handleDoubleLock(Mutex.toString(), LDat.AcquireLoc); 1502 } else { 1503 FSet.addLock(FactMan, Mutex, LDat); 1504 } 1505} 1506 1507 1508/// \brief Remove a lock from the lockset, warning if the lock is not there. 1509/// \param Mutex The lock expression corresponding to the lock to be removed 1510/// \param UnlockLoc The source location of the unlock (only used in error msg) 1511void ThreadSafetyAnalyzer::removeLock(FactSet &FSet, 1512 const SExpr &Mutex, 1513 SourceLocation UnlockLoc, 1514 bool FullyRemove) { 1515 if (Mutex.shouldIgnore()) 1516 return; 1517 1518 const LockData *LDat = FSet.findLock(FactMan, Mutex); 1519 if (!LDat) { 1520 Handler.handleUnmatchedUnlock(Mutex.toString(), UnlockLoc); 1521 return; 1522 } 1523 1524 if (LDat->UnderlyingMutex.isValid()) { 1525 // This is scoped lockable object, which manages the real mutex. 1526 if (FullyRemove) { 1527 // We're destroying the managing object. 1528 // Remove the underlying mutex if it exists; but don't warn. 1529 if (FSet.findLock(FactMan, LDat->UnderlyingMutex)) 1530 FSet.removeLock(FactMan, LDat->UnderlyingMutex); 1531 } else { 1532 // We're releasing the underlying mutex, but not destroying the 1533 // managing object. Warn on dual release. 1534 if (!FSet.findLock(FactMan, LDat->UnderlyingMutex)) { 1535 Handler.handleUnmatchedUnlock(LDat->UnderlyingMutex.toString(), 1536 UnlockLoc); 1537 } 1538 FSet.removeLock(FactMan, LDat->UnderlyingMutex); 1539 return; 1540 } 1541 } 1542 FSet.removeLock(FactMan, Mutex); 1543} 1544 1545 1546/// \brief Extract the list of mutexIDs from the attribute on an expression, 1547/// and push them onto Mtxs, discarding any duplicates. 1548template <typename AttrType> 1549void ThreadSafetyAnalyzer::getMutexIDs(MutexIDList &Mtxs, AttrType *Attr, 1550 Expr *Exp, const NamedDecl *D, 1551 VarDecl *SelfDecl) { 1552 typedef typename AttrType::args_iterator iterator_type; 1553 1554 if (Attr->args_size() == 0) { 1555 // The mutex held is the "this" object. 1556 SExpr Mu(0, Exp, D, SelfDecl); 1557 if (!Mu.isValid()) 1558 SExpr::warnInvalidLock(Handler, 0, Exp, D); 1559 else 1560 Mtxs.push_back_nodup(Mu); 1561 return; 1562 } 1563 1564 for (iterator_type I=Attr->args_begin(), E=Attr->args_end(); I != E; ++I) { 1565 SExpr Mu(*I, Exp, D, SelfDecl); 1566 if (!Mu.isValid()) 1567 SExpr::warnInvalidLock(Handler, *I, Exp, D); 1568 else 1569 Mtxs.push_back_nodup(Mu); 1570 } 1571} 1572 1573 1574/// \brief Extract the list of mutexIDs from a trylock attribute. If the 1575/// trylock applies to the given edge, then push them onto Mtxs, discarding 1576/// any duplicates. 1577template <class AttrType> 1578void ThreadSafetyAnalyzer::getMutexIDs(MutexIDList &Mtxs, AttrType *Attr, 1579 Expr *Exp, const NamedDecl *D, 1580 const CFGBlock *PredBlock, 1581 const CFGBlock *CurrBlock, 1582 Expr *BrE, bool Neg) { 1583 // Find out which branch has the lock 1584 bool branch = 0; 1585 if (CXXBoolLiteralExpr *BLE = dyn_cast_or_null<CXXBoolLiteralExpr>(BrE)) { 1586 branch = BLE->getValue(); 1587 } 1588 else if (IntegerLiteral *ILE = dyn_cast_or_null<IntegerLiteral>(BrE)) { 1589 branch = ILE->getValue().getBoolValue(); 1590 } 1591 int branchnum = branch ? 0 : 1; 1592 if (Neg) branchnum = !branchnum; 1593 1594 // If we've taken the trylock branch, then add the lock 1595 int i = 0; 1596 for (CFGBlock::const_succ_iterator SI = PredBlock->succ_begin(), 1597 SE = PredBlock->succ_end(); SI != SE && i < 2; ++SI, ++i) { 1598 if (*SI == CurrBlock && i == branchnum) { 1599 getMutexIDs(Mtxs, Attr, Exp, D); 1600 } 1601 } 1602} 1603 1604 1605bool getStaticBooleanValue(Expr* E, bool& TCond) { 1606 if (isa<CXXNullPtrLiteralExpr>(E) || isa<GNUNullExpr>(E)) { 1607 TCond = false; 1608 return true; 1609 } else if (CXXBoolLiteralExpr *BLE = dyn_cast<CXXBoolLiteralExpr>(E)) { 1610 TCond = BLE->getValue(); 1611 return true; 1612 } else if (IntegerLiteral *ILE = dyn_cast<IntegerLiteral>(E)) { 1613 TCond = ILE->getValue().getBoolValue(); 1614 return true; 1615 } else if (ImplicitCastExpr *CE = dyn_cast<ImplicitCastExpr>(E)) { 1616 return getStaticBooleanValue(CE->getSubExpr(), TCond); 1617 } 1618 return false; 1619} 1620 1621 1622// If Cond can be traced back to a function call, return the call expression. 1623// The negate variable should be called with false, and will be set to true 1624// if the function call is negated, e.g. if (!mu.tryLock(...)) 1625const CallExpr* ThreadSafetyAnalyzer::getTrylockCallExpr(const Stmt *Cond, 1626 LocalVarContext C, 1627 bool &Negate) { 1628 if (!Cond) 1629 return 0; 1630 1631 if (const CallExpr *CallExp = dyn_cast<CallExpr>(Cond)) { 1632 return CallExp; 1633 } 1634 else if (const ParenExpr *PE = dyn_cast<ParenExpr>(Cond)) { 1635 return getTrylockCallExpr(PE->getSubExpr(), C, Negate); 1636 } 1637 else if (const ImplicitCastExpr *CE = dyn_cast<ImplicitCastExpr>(Cond)) { 1638 return getTrylockCallExpr(CE->getSubExpr(), C, Negate); 1639 } 1640 else if (const ExprWithCleanups* EWC = dyn_cast<ExprWithCleanups>(Cond)) { 1641 return getTrylockCallExpr(EWC->getSubExpr(), C, Negate); 1642 } 1643 else if (const DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(Cond)) { 1644 const Expr *E = LocalVarMap.lookupExpr(DRE->getDecl(), C); 1645 return getTrylockCallExpr(E, C, Negate); 1646 } 1647 else if (const UnaryOperator *UOP = dyn_cast<UnaryOperator>(Cond)) { 1648 if (UOP->getOpcode() == UO_LNot) { 1649 Negate = !Negate; 1650 return getTrylockCallExpr(UOP->getSubExpr(), C, Negate); 1651 } 1652 return 0; 1653 } 1654 else if (const BinaryOperator *BOP = dyn_cast<BinaryOperator>(Cond)) { 1655 if (BOP->getOpcode() == BO_EQ || BOP->getOpcode() == BO_NE) { 1656 if (BOP->getOpcode() == BO_NE) 1657 Negate = !Negate; 1658 1659 bool TCond = false; 1660 if (getStaticBooleanValue(BOP->getRHS(), TCond)) { 1661 if (!TCond) Negate = !Negate; 1662 return getTrylockCallExpr(BOP->getLHS(), C, Negate); 1663 } 1664 TCond = false; 1665 if (getStaticBooleanValue(BOP->getLHS(), TCond)) { 1666 if (!TCond) Negate = !Negate; 1667 return getTrylockCallExpr(BOP->getRHS(), C, Negate); 1668 } 1669 return 0; 1670 } 1671 if (BOP->getOpcode() == BO_LAnd) { 1672 // LHS must have been evaluated in a different block. 1673 return getTrylockCallExpr(BOP->getRHS(), C, Negate); 1674 } 1675 if (BOP->getOpcode() == BO_LOr) { 1676 return getTrylockCallExpr(BOP->getRHS(), C, Negate); 1677 } 1678 return 0; 1679 } 1680 return 0; 1681} 1682 1683 1684/// \brief Find the lockset that holds on the edge between PredBlock 1685/// and CurrBlock. The edge set is the exit set of PredBlock (passed 1686/// as the ExitSet parameter) plus any trylocks, which are conditionally held. 1687void ThreadSafetyAnalyzer::getEdgeLockset(FactSet& Result, 1688 const FactSet &ExitSet, 1689 const CFGBlock *PredBlock, 1690 const CFGBlock *CurrBlock) { 1691 Result = ExitSet; 1692 1693 const Stmt *Cond = PredBlock->getTerminatorCondition(); 1694 if (!Cond) 1695 return; 1696 1697 bool Negate = false; 1698 const CFGBlockInfo *PredBlockInfo = &BlockInfo[PredBlock->getBlockID()]; 1699 const LocalVarContext &LVarCtx = PredBlockInfo->ExitContext; 1700 1701 CallExpr *Exp = 1702 const_cast<CallExpr*>(getTrylockCallExpr(Cond, LVarCtx, Negate)); 1703 if (!Exp) 1704 return; 1705 1706 NamedDecl *FunDecl = dyn_cast_or_null<NamedDecl>(Exp->getCalleeDecl()); 1707 if(!FunDecl || !FunDecl->hasAttrs()) 1708 return; 1709 1710 MutexIDList ExclusiveLocksToAdd; 1711 MutexIDList SharedLocksToAdd; 1712 1713 // If the condition is a call to a Trylock function, then grab the attributes 1714 AttrVec &ArgAttrs = FunDecl->getAttrs(); 1715 for (unsigned i = 0; i < ArgAttrs.size(); ++i) { 1716 Attr *Attr = ArgAttrs[i]; 1717 switch (Attr->getKind()) { 1718 case attr::ExclusiveTrylockFunction: { 1719 ExclusiveTrylockFunctionAttr *A = 1720 cast<ExclusiveTrylockFunctionAttr>(Attr); 1721 getMutexIDs(ExclusiveLocksToAdd, A, Exp, FunDecl, 1722 PredBlock, CurrBlock, A->getSuccessValue(), Negate); 1723 break; 1724 } 1725 case attr::SharedTrylockFunction: { 1726 SharedTrylockFunctionAttr *A = 1727 cast<SharedTrylockFunctionAttr>(Attr); 1728 getMutexIDs(SharedLocksToAdd, A, Exp, FunDecl, 1729 PredBlock, CurrBlock, A->getSuccessValue(), Negate); 1730 break; 1731 } 1732 default: 1733 break; 1734 } 1735 } 1736 1737 // Add and remove locks. 1738 SourceLocation Loc = Exp->getExprLoc(); 1739 for (unsigned i=0,n=ExclusiveLocksToAdd.size(); i<n; ++i) { 1740 addLock(Result, ExclusiveLocksToAdd[i], 1741 LockData(Loc, LK_Exclusive)); 1742 } 1743 for (unsigned i=0,n=SharedLocksToAdd.size(); i<n; ++i) { 1744 addLock(Result, SharedLocksToAdd[i], 1745 LockData(Loc, LK_Shared)); 1746 } 1747} 1748 1749 1750/// \brief We use this class to visit different types of expressions in 1751/// CFGBlocks, and build up the lockset. 1752/// An expression may cause us to add or remove locks from the lockset, or else 1753/// output error messages related to missing locks. 1754/// FIXME: In future, we may be able to not inherit from a visitor. 1755class BuildLockset : public StmtVisitor<BuildLockset> { 1756 friend class ThreadSafetyAnalyzer; 1757 1758 ThreadSafetyAnalyzer *Analyzer; 1759 FactSet FSet; 1760 LocalVariableMap::Context LVarCtx; 1761 unsigned CtxIndex; 1762 1763 // Helper functions 1764 const ValueDecl *getValueDecl(const Expr *Exp); 1765 1766 void warnIfMutexNotHeld(const NamedDecl *D, const Expr *Exp, AccessKind AK, 1767 Expr *MutexExp, ProtectedOperationKind POK); 1768 void warnIfMutexHeld(const NamedDecl *D, const Expr *Exp, Expr *MutexExp); 1769 1770 void checkAccess(const Expr *Exp, AccessKind AK); 1771 void checkPtAccess(const Expr *Exp, AccessKind AK); 1772 1773 void handleCall(Expr *Exp, const NamedDecl *D, VarDecl *VD = 0); 1774 1775public: 1776 BuildLockset(ThreadSafetyAnalyzer *Anlzr, CFGBlockInfo &Info) 1777 : StmtVisitor<BuildLockset>(), 1778 Analyzer(Anlzr), 1779 FSet(Info.EntrySet), 1780 LVarCtx(Info.EntryContext), 1781 CtxIndex(Info.EntryIndex) 1782 {} 1783 1784 void VisitUnaryOperator(UnaryOperator *UO); 1785 void VisitBinaryOperator(BinaryOperator *BO); 1786 void VisitCastExpr(CastExpr *CE); 1787 void VisitCallExpr(CallExpr *Exp); 1788 void VisitCXXConstructExpr(CXXConstructExpr *Exp); 1789 void VisitDeclStmt(DeclStmt *S); 1790}; 1791 1792 1793/// \brief Gets the value decl pointer from DeclRefExprs or MemberExprs 1794const ValueDecl *BuildLockset::getValueDecl(const Expr *Exp) { 1795 if (const ImplicitCastExpr *CE = dyn_cast<ImplicitCastExpr>(Exp)) 1796 return getValueDecl(CE->getSubExpr()); 1797 1798 if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(Exp)) 1799 return DR->getDecl(); 1800 1801 if (const MemberExpr *ME = dyn_cast<MemberExpr>(Exp)) 1802 return ME->getMemberDecl(); 1803 1804 return 0; 1805} 1806 1807/// \brief Warn if the LSet does not contain a lock sufficient to protect access 1808/// of at least the passed in AccessKind. 1809void BuildLockset::warnIfMutexNotHeld(const NamedDecl *D, const Expr *Exp, 1810 AccessKind AK, Expr *MutexExp, 1811 ProtectedOperationKind POK) { 1812 LockKind LK = getLockKindFromAccessKind(AK); 1813 1814 SExpr Mutex(MutexExp, Exp, D); 1815 if (!Mutex.isValid()) { 1816 SExpr::warnInvalidLock(Analyzer->Handler, MutexExp, Exp, D); 1817 return; 1818 } else if (Mutex.shouldIgnore()) { 1819 return; 1820 } 1821 1822 LockData* LDat = FSet.findLockUniv(Analyzer->FactMan, Mutex); 1823 bool NoError = true; 1824 if (!LDat) { 1825 // No exact match found. Look for a partial match. 1826 FactEntry* FEntry = FSet.findPartialMatch(Analyzer->FactMan, Mutex); 1827 if (FEntry) { 1828 // Warn that there's no precise match. 1829 LDat = &FEntry->LDat; 1830 std::string PartMatchStr = FEntry->MutID.toString(); 1831 StringRef PartMatchName(PartMatchStr); 1832 Analyzer->Handler.handleMutexNotHeld(D, POK, Mutex.toString(), LK, 1833 Exp->getExprLoc(), &PartMatchName); 1834 } else { 1835 // Warn that there's no match at all. 1836 Analyzer->Handler.handleMutexNotHeld(D, POK, Mutex.toString(), LK, 1837 Exp->getExprLoc()); 1838 } 1839 NoError = false; 1840 } 1841 // Make sure the mutex we found is the right kind. 1842 if (NoError && LDat && !LDat->isAtLeast(LK)) 1843 Analyzer->Handler.handleMutexNotHeld(D, POK, Mutex.toString(), LK, 1844 Exp->getExprLoc()); 1845} 1846 1847/// \brief Warn if the LSet contains the given lock. 1848void BuildLockset::warnIfMutexHeld(const NamedDecl *D, const Expr* Exp, 1849 Expr *MutexExp) { 1850 SExpr Mutex(MutexExp, Exp, D); 1851 if (!Mutex.isValid()) { 1852 SExpr::warnInvalidLock(Analyzer->Handler, MutexExp, Exp, D); 1853 return; 1854 } 1855 1856 LockData* LDat = FSet.findLock(Analyzer->FactMan, Mutex); 1857 if (LDat) { 1858 std::string DeclName = D->getNameAsString(); 1859 StringRef DeclNameSR (DeclName); 1860 Analyzer->Handler.handleFunExcludesLock(DeclNameSR, Mutex.toString(), 1861 Exp->getExprLoc()); 1862 } 1863} 1864 1865 1866/// \brief Checks guarded_by and pt_guarded_by attributes. 1867/// Whenever we identify an access (read or write) to a DeclRefExpr that is 1868/// marked with guarded_by, we must ensure the appropriate mutexes are held. 1869/// Similarly, we check if the access is to an expression that dereferences 1870/// a pointer marked with pt_guarded_by. 1871void BuildLockset::checkAccess(const Expr *Exp, AccessKind AK) { 1872 Exp = Exp->IgnoreParenCasts(); 1873 1874 if (const UnaryOperator *UO = dyn_cast<UnaryOperator>(Exp)) { 1875 // For dereferences 1876 if (UO->getOpcode() == clang::UO_Deref) 1877 checkPtAccess(UO->getSubExpr(), AK); 1878 return; 1879 } 1880 1881 if (const ArraySubscriptExpr *AE = dyn_cast<ArraySubscriptExpr>(Exp)) { 1882 if (Analyzer->Handler.issueBetaWarnings()) { 1883 checkPtAccess(AE->getLHS(), AK); 1884 return; 1885 } 1886 } 1887 1888 if (const MemberExpr *ME = dyn_cast<MemberExpr>(Exp)) { 1889 if (ME->isArrow()) 1890 checkPtAccess(ME->getBase(), AK); 1891 else 1892 checkAccess(ME->getBase(), AK); 1893 } 1894 1895 const ValueDecl *D = getValueDecl(Exp); 1896 if (!D || !D->hasAttrs()) 1897 return; 1898 1899 if (D->getAttr<GuardedVarAttr>() && FSet.isEmpty()) 1900 Analyzer->Handler.handleNoMutexHeld(D, POK_VarAccess, AK, 1901 Exp->getExprLoc()); 1902 1903 const AttrVec &ArgAttrs = D->getAttrs(); 1904 for (unsigned i = 0, Size = ArgAttrs.size(); i < Size; ++i) 1905 if (GuardedByAttr *GBAttr = dyn_cast<GuardedByAttr>(ArgAttrs[i])) 1906 warnIfMutexNotHeld(D, Exp, AK, GBAttr->getArg(), POK_VarAccess); 1907} 1908 1909/// \brief Checks pt_guarded_by and pt_guarded_var attributes. 1910void BuildLockset::checkPtAccess(const Expr *Exp, AccessKind AK) { 1911 if (Analyzer->Handler.issueBetaWarnings()) { 1912 while (true) { 1913 if (const ParenExpr *PE = dyn_cast<ParenExpr>(Exp)) { 1914 Exp = PE->getSubExpr(); 1915 continue; 1916 } 1917 if (const CastExpr *CE = dyn_cast<CastExpr>(Exp)) { 1918 if (CE->getCastKind() == CK_ArrayToPointerDecay) { 1919 // If it's an actual array, and not a pointer, then it's elements 1920 // are protected by GUARDED_BY, not PT_GUARDED_BY; 1921 checkAccess(CE->getSubExpr(), AK); 1922 return; 1923 } 1924 Exp = CE->getSubExpr(); 1925 continue; 1926 } 1927 break; 1928 } 1929 } 1930 else 1931 Exp = Exp->IgnoreParenCasts(); 1932 1933 const ValueDecl *D = getValueDecl(Exp); 1934 if (!D || !D->hasAttrs()) 1935 return; 1936 1937 if (D->getAttr<PtGuardedVarAttr>() && FSet.isEmpty()) 1938 Analyzer->Handler.handleNoMutexHeld(D, POK_VarDereference, AK, 1939 Exp->getExprLoc()); 1940 1941 const AttrVec &ArgAttrs = D->getAttrs(); 1942 for (unsigned i = 0, Size = ArgAttrs.size(); i < Size; ++i) 1943 if (PtGuardedByAttr *GBAttr = dyn_cast<PtGuardedByAttr>(ArgAttrs[i])) 1944 warnIfMutexNotHeld(D, Exp, AK, GBAttr->getArg(), POK_VarDereference); 1945} 1946 1947 1948/// \brief Process a function call, method call, constructor call, 1949/// or destructor call. This involves looking at the attributes on the 1950/// corresponding function/method/constructor/destructor, issuing warnings, 1951/// and updating the locksets accordingly. 1952/// 1953/// FIXME: For classes annotated with one of the guarded annotations, we need 1954/// to treat const method calls as reads and non-const method calls as writes, 1955/// and check that the appropriate locks are held. Non-const method calls with 1956/// the same signature as const method calls can be also treated as reads. 1957/// 1958void BuildLockset::handleCall(Expr *Exp, const NamedDecl *D, VarDecl *VD) { 1959 SourceLocation Loc = Exp->getExprLoc(); 1960 const AttrVec &ArgAttrs = D->getAttrs(); 1961 MutexIDList ExclusiveLocksToAdd; 1962 MutexIDList SharedLocksToAdd; 1963 MutexIDList LocksToRemove; 1964 1965 for(unsigned i = 0; i < ArgAttrs.size(); ++i) { 1966 Attr *At = const_cast<Attr*>(ArgAttrs[i]); 1967 switch (At->getKind()) { 1968 // When we encounter an exclusive lock function, we need to add the lock 1969 // to our lockset with kind exclusive. 1970 case attr::ExclusiveLockFunction: { 1971 ExclusiveLockFunctionAttr *A = cast<ExclusiveLockFunctionAttr>(At); 1972 Analyzer->getMutexIDs(ExclusiveLocksToAdd, A, Exp, D, VD); 1973 break; 1974 } 1975 1976 // When we encounter a shared lock function, we need to add the lock 1977 // to our lockset with kind shared. 1978 case attr::SharedLockFunction: { 1979 SharedLockFunctionAttr *A = cast<SharedLockFunctionAttr>(At); 1980 Analyzer->getMutexIDs(SharedLocksToAdd, A, Exp, D, VD); 1981 break; 1982 } 1983 1984 // An assert will add a lock to the lockset, but will not generate 1985 // a warning if it is already there, and will not generate a warning 1986 // if it is not removed. 1987 case attr::AssertExclusiveLock: { 1988 AssertExclusiveLockAttr *A = cast<AssertExclusiveLockAttr>(At); 1989 1990 MutexIDList AssertLocks; 1991 Analyzer->getMutexIDs(AssertLocks, A, Exp, D, VD); 1992 for (unsigned i=0,n=AssertLocks.size(); i<n; ++i) { 1993 Analyzer->addLock(FSet, AssertLocks[i], 1994 LockData(Loc, LK_Exclusive, false, true)); 1995 } 1996 break; 1997 } 1998 case attr::AssertSharedLock: { 1999 AssertSharedLockAttr *A = cast<AssertSharedLockAttr>(At); 2000 2001 MutexIDList AssertLocks; 2002 Analyzer->getMutexIDs(AssertLocks, A, Exp, D, VD); 2003 for (unsigned i=0,n=AssertLocks.size(); i<n; ++i) { 2004 Analyzer->addLock(FSet, AssertLocks[i], 2005 LockData(Loc, LK_Shared, false, true)); 2006 } 2007 break; 2008 } 2009 2010 // When we encounter an unlock function, we need to remove unlocked 2011 // mutexes from the lockset, and flag a warning if they are not there. 2012 case attr::UnlockFunction: { 2013 UnlockFunctionAttr *A = cast<UnlockFunctionAttr>(At); 2014 Analyzer->getMutexIDs(LocksToRemove, A, Exp, D, VD); 2015 break; 2016 } 2017 2018 case attr::ExclusiveLocksRequired: { 2019 ExclusiveLocksRequiredAttr *A = cast<ExclusiveLocksRequiredAttr>(At); 2020 2021 for (ExclusiveLocksRequiredAttr::args_iterator 2022 I = A->args_begin(), E = A->args_end(); I != E; ++I) 2023 warnIfMutexNotHeld(D, Exp, AK_Written, *I, POK_FunctionCall); 2024 break; 2025 } 2026 2027 case attr::SharedLocksRequired: { 2028 SharedLocksRequiredAttr *A = cast<SharedLocksRequiredAttr>(At); 2029 2030 for (SharedLocksRequiredAttr::args_iterator I = A->args_begin(), 2031 E = A->args_end(); I != E; ++I) 2032 warnIfMutexNotHeld(D, Exp, AK_Read, *I, POK_FunctionCall); 2033 break; 2034 } 2035 2036 case attr::LocksExcluded: { 2037 LocksExcludedAttr *A = cast<LocksExcludedAttr>(At); 2038 2039 for (LocksExcludedAttr::args_iterator I = A->args_begin(), 2040 E = A->args_end(); I != E; ++I) { 2041 warnIfMutexHeld(D, Exp, *I); 2042 } 2043 break; 2044 } 2045 2046 // Ignore other (non thread-safety) attributes 2047 default: 2048 break; 2049 } 2050 } 2051 2052 // Figure out if we're calling the constructor of scoped lockable class 2053 bool isScopedVar = false; 2054 if (VD) { 2055 if (const CXXConstructorDecl *CD = dyn_cast<const CXXConstructorDecl>(D)) { 2056 const CXXRecordDecl* PD = CD->getParent(); 2057 if (PD && PD->getAttr<ScopedLockableAttr>()) 2058 isScopedVar = true; 2059 } 2060 } 2061 2062 // Add locks. 2063 for (unsigned i=0,n=ExclusiveLocksToAdd.size(); i<n; ++i) { 2064 Analyzer->addLock(FSet, ExclusiveLocksToAdd[i], 2065 LockData(Loc, LK_Exclusive, isScopedVar)); 2066 } 2067 for (unsigned i=0,n=SharedLocksToAdd.size(); i<n; ++i) { 2068 Analyzer->addLock(FSet, SharedLocksToAdd[i], 2069 LockData(Loc, LK_Shared, isScopedVar)); 2070 } 2071 2072 // Add the managing object as a dummy mutex, mapped to the underlying mutex. 2073 // FIXME -- this doesn't work if we acquire multiple locks. 2074 if (isScopedVar) { 2075 SourceLocation MLoc = VD->getLocation(); 2076 DeclRefExpr DRE(VD, false, VD->getType(), VK_LValue, VD->getLocation()); 2077 SExpr SMutex(&DRE, 0, 0); 2078 2079 for (unsigned i=0,n=ExclusiveLocksToAdd.size(); i<n; ++i) { 2080 Analyzer->addLock(FSet, SMutex, LockData(MLoc, LK_Exclusive, 2081 ExclusiveLocksToAdd[i])); 2082 } 2083 for (unsigned i=0,n=SharedLocksToAdd.size(); i<n; ++i) { 2084 Analyzer->addLock(FSet, SMutex, LockData(MLoc, LK_Shared, 2085 SharedLocksToAdd[i])); 2086 } 2087 } 2088 2089 // Remove locks. 2090 // FIXME -- should only fully remove if the attribute refers to 'this'. 2091 bool Dtor = isa<CXXDestructorDecl>(D); 2092 for (unsigned i=0,n=LocksToRemove.size(); i<n; ++i) { 2093 Analyzer->removeLock(FSet, LocksToRemove[i], Loc, Dtor); 2094 } 2095} 2096 2097 2098/// \brief For unary operations which read and write a variable, we need to 2099/// check whether we hold any required mutexes. Reads are checked in 2100/// VisitCastExpr. 2101void BuildLockset::VisitUnaryOperator(UnaryOperator *UO) { 2102 switch (UO->getOpcode()) { 2103 case clang::UO_PostDec: 2104 case clang::UO_PostInc: 2105 case clang::UO_PreDec: 2106 case clang::UO_PreInc: { 2107 checkAccess(UO->getSubExpr(), AK_Written); 2108 break; 2109 } 2110 default: 2111 break; 2112 } 2113} 2114 2115/// For binary operations which assign to a variable (writes), we need to check 2116/// whether we hold any required mutexes. 2117/// FIXME: Deal with non-primitive types. 2118void BuildLockset::VisitBinaryOperator(BinaryOperator *BO) { 2119 if (!BO->isAssignmentOp()) 2120 return; 2121 2122 // adjust the context 2123 LVarCtx = Analyzer->LocalVarMap.getNextContext(CtxIndex, BO, LVarCtx); 2124 2125 checkAccess(BO->getLHS(), AK_Written); 2126} 2127 2128 2129/// Whenever we do an LValue to Rvalue cast, we are reading a variable and 2130/// need to ensure we hold any required mutexes. 2131/// FIXME: Deal with non-primitive types. 2132void BuildLockset::VisitCastExpr(CastExpr *CE) { 2133 if (CE->getCastKind() != CK_LValueToRValue) 2134 return; 2135 checkAccess(CE->getSubExpr(), AK_Read); 2136} 2137 2138 2139void BuildLockset::VisitCallExpr(CallExpr *Exp) { 2140 if (CXXMemberCallExpr *CE = dyn_cast<CXXMemberCallExpr>(Exp)) { 2141 MemberExpr *ME = dyn_cast<MemberExpr>(CE->getCallee()); 2142 // ME can be null when calling a method pointer 2143 CXXMethodDecl *MD = CE->getMethodDecl(); 2144 2145 if (ME && MD) { 2146 if (ME->isArrow()) { 2147 if (MD->isConst()) { 2148 checkPtAccess(CE->getImplicitObjectArgument(), AK_Read); 2149 } else { // FIXME -- should be AK_Written 2150 checkPtAccess(CE->getImplicitObjectArgument(), AK_Read); 2151 } 2152 } else { 2153 if (MD->isConst()) 2154 checkAccess(CE->getImplicitObjectArgument(), AK_Read); 2155 else // FIXME -- should be AK_Written 2156 checkAccess(CE->getImplicitObjectArgument(), AK_Read); 2157 } 2158 } 2159 } else if (CXXOperatorCallExpr *OE = dyn_cast<CXXOperatorCallExpr>(Exp)) { 2160 switch (OE->getOperator()) { 2161 case OO_Equal: { 2162 const Expr *Target = OE->getArg(0); 2163 const Expr *Source = OE->getArg(1); 2164 checkAccess(Target, AK_Written); 2165 checkAccess(Source, AK_Read); 2166 break; 2167 } 2168 case OO_Star: 2169 case OO_Arrow: 2170 case OO_Subscript: { 2171 if (Analyzer->Handler.issueBetaWarnings()) { 2172 const Expr *Obj = OE->getArg(0); 2173 checkAccess(Obj, AK_Read); 2174 checkPtAccess(Obj, AK_Read); 2175 } 2176 break; 2177 } 2178 default: { 2179 const Expr *Obj = OE->getArg(0); 2180 checkAccess(Obj, AK_Read); 2181 break; 2182 } 2183 } 2184 } 2185 NamedDecl *D = dyn_cast_or_null<NamedDecl>(Exp->getCalleeDecl()); 2186 if(!D || !D->hasAttrs()) 2187 return; 2188 handleCall(Exp, D); 2189} 2190 2191void BuildLockset::VisitCXXConstructExpr(CXXConstructExpr *Exp) { 2192 const CXXConstructorDecl *D = Exp->getConstructor(); 2193 if (D && D->isCopyConstructor()) { 2194 const Expr* Source = Exp->getArg(0); 2195 checkAccess(Source, AK_Read); 2196 } 2197 // FIXME -- only handles constructors in DeclStmt below. 2198} 2199 2200void BuildLockset::VisitDeclStmt(DeclStmt *S) { 2201 // adjust the context 2202 LVarCtx = Analyzer->LocalVarMap.getNextContext(CtxIndex, S, LVarCtx); 2203 2204 DeclGroupRef DGrp = S->getDeclGroup(); 2205 for (DeclGroupRef::iterator I = DGrp.begin(), E = DGrp.end(); I != E; ++I) { 2206 Decl *D = *I; 2207 if (VarDecl *VD = dyn_cast_or_null<VarDecl>(D)) { 2208 Expr *E = VD->getInit(); 2209 // handle constructors that involve temporaries 2210 if (ExprWithCleanups *EWC = dyn_cast_or_null<ExprWithCleanups>(E)) 2211 E = EWC->getSubExpr(); 2212 2213 if (CXXConstructExpr *CE = dyn_cast_or_null<CXXConstructExpr>(E)) { 2214 NamedDecl *CtorD = dyn_cast_or_null<NamedDecl>(CE->getConstructor()); 2215 if (!CtorD || !CtorD->hasAttrs()) 2216 return; 2217 handleCall(CE, CtorD, VD); 2218 } 2219 } 2220 } 2221} 2222 2223 2224 2225/// \brief Compute the intersection of two locksets and issue warnings for any 2226/// locks in the symmetric difference. 2227/// 2228/// This function is used at a merge point in the CFG when comparing the lockset 2229/// of each branch being merged. For example, given the following sequence: 2230/// A; if () then B; else C; D; we need to check that the lockset after B and C 2231/// are the same. In the event of a difference, we use the intersection of these 2232/// two locksets at the start of D. 2233/// 2234/// \param FSet1 The first lockset. 2235/// \param FSet2 The second lockset. 2236/// \param JoinLoc The location of the join point for error reporting 2237/// \param LEK1 The error message to report if a mutex is missing from LSet1 2238/// \param LEK2 The error message to report if a mutex is missing from Lset2 2239void ThreadSafetyAnalyzer::intersectAndWarn(FactSet &FSet1, 2240 const FactSet &FSet2, 2241 SourceLocation JoinLoc, 2242 LockErrorKind LEK1, 2243 LockErrorKind LEK2, 2244 bool Modify) { 2245 FactSet FSet1Orig = FSet1; 2246 2247 // Find locks in FSet2 that conflict or are not in FSet1, and warn. 2248 for (FactSet::const_iterator I = FSet2.begin(), E = FSet2.end(); 2249 I != E; ++I) { 2250 const SExpr &FSet2Mutex = FactMan[*I].MutID; 2251 const LockData &LDat2 = FactMan[*I].LDat; 2252 FactSet::iterator I1 = FSet1.findLockIter(FactMan, FSet2Mutex); 2253 2254 if (I1 != FSet1.end()) { 2255 const LockData* LDat1 = &FactMan[*I1].LDat; 2256 if (LDat1->LKind != LDat2.LKind) { 2257 Handler.handleExclusiveAndShared(FSet2Mutex.toString(), 2258 LDat2.AcquireLoc, 2259 LDat1->AcquireLoc); 2260 if (Modify && LDat1->LKind != LK_Exclusive) { 2261 // Take the exclusive lock, which is the one in FSet2. 2262 *I1 = *I; 2263 } 2264 } 2265 else if (LDat1->Asserted && !LDat2.Asserted) { 2266 // The non-asserted lock in FSet2 is the one we want to track. 2267 *I1 = *I; 2268 } 2269 } else { 2270 if (LDat2.UnderlyingMutex.isValid()) { 2271 if (FSet2.findLock(FactMan, LDat2.UnderlyingMutex)) { 2272 // If this is a scoped lock that manages another mutex, and if the 2273 // underlying mutex is still held, then warn about the underlying 2274 // mutex. 2275 Handler.handleMutexHeldEndOfScope(LDat2.UnderlyingMutex.toString(), 2276 LDat2.AcquireLoc, 2277 JoinLoc, LEK1); 2278 } 2279 } 2280 else if (!LDat2.Managed && !FSet2Mutex.isUniversal() && !LDat2.Asserted) 2281 Handler.handleMutexHeldEndOfScope(FSet2Mutex.toString(), 2282 LDat2.AcquireLoc, 2283 JoinLoc, LEK1); 2284 } 2285 } 2286 2287 // Find locks in FSet1 that are not in FSet2, and remove them. 2288 for (FactSet::const_iterator I = FSet1Orig.begin(), E = FSet1Orig.end(); 2289 I != E; ++I) { 2290 const SExpr &FSet1Mutex = FactMan[*I].MutID; 2291 const LockData &LDat1 = FactMan[*I].LDat; 2292 2293 if (!FSet2.findLock(FactMan, FSet1Mutex)) { 2294 if (LDat1.UnderlyingMutex.isValid()) { 2295 if (FSet1Orig.findLock(FactMan, LDat1.UnderlyingMutex)) { 2296 // If this is a scoped lock that manages another mutex, and if the 2297 // underlying mutex is still held, then warn about the underlying 2298 // mutex. 2299 Handler.handleMutexHeldEndOfScope(LDat1.UnderlyingMutex.toString(), 2300 LDat1.AcquireLoc, 2301 JoinLoc, LEK1); 2302 } 2303 } 2304 else if (!LDat1.Managed && !FSet1Mutex.isUniversal() && !LDat1.Asserted) 2305 Handler.handleMutexHeldEndOfScope(FSet1Mutex.toString(), 2306 LDat1.AcquireLoc, 2307 JoinLoc, LEK2); 2308 if (Modify) 2309 FSet1.removeLock(FactMan, FSet1Mutex); 2310 } 2311 } 2312} 2313 2314 2315// Return true if block B never continues to its successors. 2316inline bool neverReturns(const CFGBlock* B) { 2317 if (B->hasNoReturnElement()) 2318 return true; 2319 if (B->empty()) 2320 return false; 2321 2322 CFGElement Last = B->back(); 2323 if (Optional<CFGStmt> S = Last.getAs<CFGStmt>()) { 2324 if (isa<CXXThrowExpr>(S->getStmt())) 2325 return true; 2326 } 2327 return false; 2328} 2329 2330 2331/// \brief Check a function's CFG for thread-safety violations. 2332/// 2333/// We traverse the blocks in the CFG, compute the set of mutexes that are held 2334/// at the end of each block, and issue warnings for thread safety violations. 2335/// Each block in the CFG is traversed exactly once. 2336void ThreadSafetyAnalyzer::runAnalysis(AnalysisDeclContext &AC) { 2337 CFG *CFGraph = AC.getCFG(); 2338 if (!CFGraph) return; 2339 const NamedDecl *D = dyn_cast_or_null<NamedDecl>(AC.getDecl()); 2340 2341 // AC.dumpCFG(true); 2342 2343 if (!D) 2344 return; // Ignore anonymous functions for now. 2345 if (D->getAttr<NoThreadSafetyAnalysisAttr>()) 2346 return; 2347 // FIXME: Do something a bit more intelligent inside constructor and 2348 // destructor code. Constructors and destructors must assume unique access 2349 // to 'this', so checks on member variable access is disabled, but we should 2350 // still enable checks on other objects. 2351 if (isa<CXXConstructorDecl>(D)) 2352 return; // Don't check inside constructors. 2353 if (isa<CXXDestructorDecl>(D)) 2354 return; // Don't check inside destructors. 2355 2356 BlockInfo.resize(CFGraph->getNumBlockIDs(), 2357 CFGBlockInfo::getEmptyBlockInfo(LocalVarMap)); 2358 2359 // We need to explore the CFG via a "topological" ordering. 2360 // That way, we will be guaranteed to have information about required 2361 // predecessor locksets when exploring a new block. 2362 PostOrderCFGView *SortedGraph = AC.getAnalysis<PostOrderCFGView>(); 2363 PostOrderCFGView::CFGBlockSet VisitedBlocks(CFGraph); 2364 2365 // Mark entry block as reachable 2366 BlockInfo[CFGraph->getEntry().getBlockID()].Reachable = true; 2367 2368 // Compute SSA names for local variables 2369 LocalVarMap.traverseCFG(CFGraph, SortedGraph, BlockInfo); 2370 2371 // Fill in source locations for all CFGBlocks. 2372 findBlockLocations(CFGraph, SortedGraph, BlockInfo); 2373 2374 MutexIDList ExclusiveLocksAcquired; 2375 MutexIDList SharedLocksAcquired; 2376 MutexIDList LocksReleased; 2377 2378 // Add locks from exclusive_locks_required and shared_locks_required 2379 // to initial lockset. Also turn off checking for lock and unlock functions. 2380 // FIXME: is there a more intelligent way to check lock/unlock functions? 2381 if (!SortedGraph->empty() && D->hasAttrs()) { 2382 const CFGBlock *FirstBlock = *SortedGraph->begin(); 2383 FactSet &InitialLockset = BlockInfo[FirstBlock->getBlockID()].EntrySet; 2384 const AttrVec &ArgAttrs = D->getAttrs(); 2385 2386 MutexIDList ExclusiveLocksToAdd; 2387 MutexIDList SharedLocksToAdd; 2388 2389 SourceLocation Loc = D->getLocation(); 2390 for (unsigned i = 0; i < ArgAttrs.size(); ++i) { 2391 Attr *Attr = ArgAttrs[i]; 2392 Loc = Attr->getLocation(); 2393 if (ExclusiveLocksRequiredAttr *A 2394 = dyn_cast<ExclusiveLocksRequiredAttr>(Attr)) { 2395 getMutexIDs(ExclusiveLocksToAdd, A, (Expr*) 0, D); 2396 } else if (SharedLocksRequiredAttr *A 2397 = dyn_cast<SharedLocksRequiredAttr>(Attr)) { 2398 getMutexIDs(SharedLocksToAdd, A, (Expr*) 0, D); 2399 } else if (UnlockFunctionAttr *A = dyn_cast<UnlockFunctionAttr>(Attr)) { 2400 // UNLOCK_FUNCTION() is used to hide the underlying lock implementation. 2401 // We must ignore such methods. 2402 if (A->args_size() == 0) 2403 return; 2404 // FIXME -- deal with exclusive vs. shared unlock functions? 2405 getMutexIDs(ExclusiveLocksToAdd, A, (Expr*) 0, D); 2406 getMutexIDs(LocksReleased, A, (Expr*) 0, D); 2407 } else if (ExclusiveLockFunctionAttr *A 2408 = dyn_cast<ExclusiveLockFunctionAttr>(Attr)) { 2409 if (A->args_size() == 0) 2410 return; 2411 getMutexIDs(ExclusiveLocksAcquired, A, (Expr*) 0, D); 2412 } else if (SharedLockFunctionAttr *A 2413 = dyn_cast<SharedLockFunctionAttr>(Attr)) { 2414 if (A->args_size() == 0) 2415 return; 2416 getMutexIDs(SharedLocksAcquired, A, (Expr*) 0, D); 2417 } else if (isa<ExclusiveTrylockFunctionAttr>(Attr)) { 2418 // Don't try to check trylock functions for now 2419 return; 2420 } else if (isa<SharedTrylockFunctionAttr>(Attr)) { 2421 // Don't try to check trylock functions for now 2422 return; 2423 } 2424 } 2425 2426 // FIXME -- Loc can be wrong here. 2427 for (unsigned i=0,n=ExclusiveLocksToAdd.size(); i<n; ++i) { 2428 addLock(InitialLockset, ExclusiveLocksToAdd[i], 2429 LockData(Loc, LK_Exclusive)); 2430 } 2431 for (unsigned i=0,n=SharedLocksToAdd.size(); i<n; ++i) { 2432 addLock(InitialLockset, SharedLocksToAdd[i], 2433 LockData(Loc, LK_Shared)); 2434 } 2435 } 2436 2437 for (PostOrderCFGView::iterator I = SortedGraph->begin(), 2438 E = SortedGraph->end(); I!= E; ++I) { 2439 const CFGBlock *CurrBlock = *I; 2440 int CurrBlockID = CurrBlock->getBlockID(); 2441 CFGBlockInfo *CurrBlockInfo = &BlockInfo[CurrBlockID]; 2442 2443 // Use the default initial lockset in case there are no predecessors. 2444 VisitedBlocks.insert(CurrBlock); 2445 2446 // Iterate through the predecessor blocks and warn if the lockset for all 2447 // predecessors is not the same. We take the entry lockset of the current 2448 // block to be the intersection of all previous locksets. 2449 // FIXME: By keeping the intersection, we may output more errors in future 2450 // for a lock which is not in the intersection, but was in the union. We 2451 // may want to also keep the union in future. As an example, let's say 2452 // the intersection contains Mutex L, and the union contains L and M. 2453 // Later we unlock M. At this point, we would output an error because we 2454 // never locked M; although the real error is probably that we forgot to 2455 // lock M on all code paths. Conversely, let's say that later we lock M. 2456 // In this case, we should compare against the intersection instead of the 2457 // union because the real error is probably that we forgot to unlock M on 2458 // all code paths. 2459 bool LocksetInitialized = false; 2460 SmallVector<CFGBlock *, 8> SpecialBlocks; 2461 for (CFGBlock::const_pred_iterator PI = CurrBlock->pred_begin(), 2462 PE = CurrBlock->pred_end(); PI != PE; ++PI) { 2463 2464 // if *PI -> CurrBlock is a back edge 2465 if (*PI == 0 || !VisitedBlocks.alreadySet(*PI)) 2466 continue; 2467 2468 int PrevBlockID = (*PI)->getBlockID(); 2469 CFGBlockInfo *PrevBlockInfo = &BlockInfo[PrevBlockID]; 2470 2471 // Ignore edges from blocks that can't return. 2472 if (neverReturns(*PI) || !PrevBlockInfo->Reachable) 2473 continue; 2474 2475 // Okay, we can reach this block from the entry. 2476 CurrBlockInfo->Reachable = true; 2477 2478 // If the previous block ended in a 'continue' or 'break' statement, then 2479 // a difference in locksets is probably due to a bug in that block, rather 2480 // than in some other predecessor. In that case, keep the other 2481 // predecessor's lockset. 2482 if (const Stmt *Terminator = (*PI)->getTerminator()) { 2483 if (isa<ContinueStmt>(Terminator) || isa<BreakStmt>(Terminator)) { 2484 SpecialBlocks.push_back(*PI); 2485 continue; 2486 } 2487 } 2488 2489 FactSet PrevLockset; 2490 getEdgeLockset(PrevLockset, PrevBlockInfo->ExitSet, *PI, CurrBlock); 2491 2492 if (!LocksetInitialized) { 2493 CurrBlockInfo->EntrySet = PrevLockset; 2494 LocksetInitialized = true; 2495 } else { 2496 intersectAndWarn(CurrBlockInfo->EntrySet, PrevLockset, 2497 CurrBlockInfo->EntryLoc, 2498 LEK_LockedSomePredecessors); 2499 } 2500 } 2501 2502 // Skip rest of block if it's not reachable. 2503 if (!CurrBlockInfo->Reachable) 2504 continue; 2505 2506 // Process continue and break blocks. Assume that the lockset for the 2507 // resulting block is unaffected by any discrepancies in them. 2508 for (unsigned SpecialI = 0, SpecialN = SpecialBlocks.size(); 2509 SpecialI < SpecialN; ++SpecialI) { 2510 CFGBlock *PrevBlock = SpecialBlocks[SpecialI]; 2511 int PrevBlockID = PrevBlock->getBlockID(); 2512 CFGBlockInfo *PrevBlockInfo = &BlockInfo[PrevBlockID]; 2513 2514 if (!LocksetInitialized) { 2515 CurrBlockInfo->EntrySet = PrevBlockInfo->ExitSet; 2516 LocksetInitialized = true; 2517 } else { 2518 // Determine whether this edge is a loop terminator for diagnostic 2519 // purposes. FIXME: A 'break' statement might be a loop terminator, but 2520 // it might also be part of a switch. Also, a subsequent destructor 2521 // might add to the lockset, in which case the real issue might be a 2522 // double lock on the other path. 2523 const Stmt *Terminator = PrevBlock->getTerminator(); 2524 bool IsLoop = Terminator && isa<ContinueStmt>(Terminator); 2525 2526 FactSet PrevLockset; 2527 getEdgeLockset(PrevLockset, PrevBlockInfo->ExitSet, 2528 PrevBlock, CurrBlock); 2529 2530 // Do not update EntrySet. 2531 intersectAndWarn(CurrBlockInfo->EntrySet, PrevLockset, 2532 PrevBlockInfo->ExitLoc, 2533 IsLoop ? LEK_LockedSomeLoopIterations 2534 : LEK_LockedSomePredecessors, 2535 false); 2536 } 2537 } 2538 2539 BuildLockset LocksetBuilder(this, *CurrBlockInfo); 2540 2541 // Visit all the statements in the basic block. 2542 for (CFGBlock::const_iterator BI = CurrBlock->begin(), 2543 BE = CurrBlock->end(); BI != BE; ++BI) { 2544 switch (BI->getKind()) { 2545 case CFGElement::Statement: { 2546 CFGStmt CS = BI->castAs<CFGStmt>(); 2547 LocksetBuilder.Visit(const_cast<Stmt*>(CS.getStmt())); 2548 break; 2549 } 2550 // Ignore BaseDtor, MemberDtor, and TemporaryDtor for now. 2551 case CFGElement::AutomaticObjectDtor: { 2552 CFGAutomaticObjDtor AD = BI->castAs<CFGAutomaticObjDtor>(); 2553 CXXDestructorDecl *DD = const_cast<CXXDestructorDecl *>( 2554 AD.getDestructorDecl(AC.getASTContext())); 2555 if (!DD->hasAttrs()) 2556 break; 2557 2558 // Create a dummy expression, 2559 VarDecl *VD = const_cast<VarDecl*>(AD.getVarDecl()); 2560 DeclRefExpr DRE(VD, false, VD->getType(), VK_LValue, 2561 AD.getTriggerStmt()->getLocEnd()); 2562 LocksetBuilder.handleCall(&DRE, DD); 2563 break; 2564 } 2565 default: 2566 break; 2567 } 2568 } 2569 CurrBlockInfo->ExitSet = LocksetBuilder.FSet; 2570 2571 // For every back edge from CurrBlock (the end of the loop) to another block 2572 // (FirstLoopBlock) we need to check that the Lockset of Block is equal to 2573 // the one held at the beginning of FirstLoopBlock. We can look up the 2574 // Lockset held at the beginning of FirstLoopBlock in the EntryLockSets map. 2575 for (CFGBlock::const_succ_iterator SI = CurrBlock->succ_begin(), 2576 SE = CurrBlock->succ_end(); SI != SE; ++SI) { 2577 2578 // if CurrBlock -> *SI is *not* a back edge 2579 if (*SI == 0 || !VisitedBlocks.alreadySet(*SI)) 2580 continue; 2581 2582 CFGBlock *FirstLoopBlock = *SI; 2583 CFGBlockInfo *PreLoop = &BlockInfo[FirstLoopBlock->getBlockID()]; 2584 CFGBlockInfo *LoopEnd = &BlockInfo[CurrBlockID]; 2585 intersectAndWarn(LoopEnd->ExitSet, PreLoop->EntrySet, 2586 PreLoop->EntryLoc, 2587 LEK_LockedSomeLoopIterations, 2588 false); 2589 } 2590 } 2591 2592 CFGBlockInfo *Initial = &BlockInfo[CFGraph->getEntry().getBlockID()]; 2593 CFGBlockInfo *Final = &BlockInfo[CFGraph->getExit().getBlockID()]; 2594 2595 // Skip the final check if the exit block is unreachable. 2596 if (!Final->Reachable) 2597 return; 2598 2599 // By default, we expect all locks held on entry to be held on exit. 2600 FactSet ExpectedExitSet = Initial->EntrySet; 2601 2602 // Adjust the expected exit set by adding or removing locks, as declared 2603 // by *-LOCK_FUNCTION and UNLOCK_FUNCTION. The intersect below will then 2604 // issue the appropriate warning. 2605 // FIXME: the location here is not quite right. 2606 for (unsigned i=0,n=ExclusiveLocksAcquired.size(); i<n; ++i) { 2607 ExpectedExitSet.addLock(FactMan, ExclusiveLocksAcquired[i], 2608 LockData(D->getLocation(), LK_Exclusive)); 2609 } 2610 for (unsigned i=0,n=SharedLocksAcquired.size(); i<n; ++i) { 2611 ExpectedExitSet.addLock(FactMan, SharedLocksAcquired[i], 2612 LockData(D->getLocation(), LK_Shared)); 2613 } 2614 for (unsigned i=0,n=LocksReleased.size(); i<n; ++i) { 2615 ExpectedExitSet.removeLock(FactMan, LocksReleased[i]); 2616 } 2617 2618 // FIXME: Should we call this function for all blocks which exit the function? 2619 intersectAndWarn(ExpectedExitSet, Final->ExitSet, 2620 Final->ExitLoc, 2621 LEK_LockedAtEndOfFunction, 2622 LEK_NotLockedAtEndOfFunction, 2623 false); 2624} 2625 2626} // end anonymous namespace 2627 2628 2629namespace clang { 2630namespace thread_safety { 2631 2632/// \brief Check a function's CFG for thread-safety violations. 2633/// 2634/// We traverse the blocks in the CFG, compute the set of mutexes that are held 2635/// at the end of each block, and issue warnings for thread safety violations. 2636/// Each block in the CFG is traversed exactly once. 2637void runThreadSafetyAnalysis(AnalysisDeclContext &AC, 2638 ThreadSafetyHandler &Handler) { 2639 ThreadSafetyAnalyzer Analyzer(Handler); 2640 Analyzer.runAnalysis(AC); 2641} 2642 2643/// \brief Helper function that returns a LockKind required for the given level 2644/// of access. 2645LockKind getLockKindFromAccessKind(AccessKind AK) { 2646 switch (AK) { 2647 case AK_Read : 2648 return LK_Shared; 2649 case AK_Written : 2650 return LK_Exclusive; 2651 } 2652 llvm_unreachable("Unknown AccessKind"); 2653} 2654 2655}} // end namespace clang::thread_safety 2656