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