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