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