ThreadSafety.cpp 70 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418141914201421142214231424142514261427142814291430143114321433143414351436143714381439144014411442144314441445144614471448144914501451145214531454145514561457145814591460146114621463146414651466146714681469147014711472147314741475147614771478147914801481148214831484148514861487148814891490149114921493149414951496149714981499150015011502150315041505150615071508150915101511151215131514151515161517151815191520152115221523152415251526152715281529153015311532153315341535153615371538153915401541154215431544154515461547154815491550155115521553155415551556155715581559156015611562156315641565156615671568156915701571157215731574157515761577157815791580158115821583158415851586158715881589159015911592159315941595159615971598159916001601160216031604160516061607160816091610161116121613161416151616161716181619162016211622162316241625162616271628162916301631163216331634163516361637163816391640164116421643164416451646164716481649165016511652165316541655165616571658165916601661166216631664166516661667166816691670167116721673167416751676167716781679168016811682168316841685168616871688168916901691169216931694169516961697169816991700170117021703170417051706170717081709171017111712171317141715171617171718171917201721172217231724172517261727172817291730173117321733173417351736173717381739174017411742174317441745174617471748174917501751175217531754175517561757175817591760176117621763176417651766176717681769177017711772177317741775177617771778177917801781178217831784178517861787178817891790179117921793179417951796179717981799180018011802180318041805180618071808180918101811181218131814181518161817181818191820182118221823182418251826182718281829183018311832183318341835183618371838183918401841184218431844184518461847184818491850185118521853
  1. //===- ThreadSafety.cpp ----------------------------------------*- C++ --*-===//
  2. //
  3. // The LLVM Compiler Infrastructure
  4. //
  5. // This file is distributed under the University of Illinois Open Source
  6. // License. See LICENSE.TXT for details.
  7. //
  8. //===----------------------------------------------------------------------===//
  9. //
  10. // A intra-procedural analysis for thread safety (e.g. deadlocks and race
  11. // conditions), based off of an annotation system.
  12. //
  13. // See http://clang.llvm.org/docs/LanguageExtensions.html#threadsafety for more
  14. // information.
  15. //
  16. //===----------------------------------------------------------------------===//
  17. #include "clang/Analysis/Analyses/ThreadSafety.h"
  18. #include "clang/Analysis/Analyses/PostOrderCFGView.h"
  19. #include "clang/Analysis/AnalysisContext.h"
  20. #include "clang/Analysis/CFG.h"
  21. #include "clang/Analysis/CFGStmtMap.h"
  22. #include "clang/AST/DeclCXX.h"
  23. #include "clang/AST/ExprCXX.h"
  24. #include "clang/AST/StmtCXX.h"
  25. #include "clang/AST/StmtVisitor.h"
  26. #include "clang/Basic/SourceManager.h"
  27. #include "clang/Basic/SourceLocation.h"
  28. #include "llvm/ADT/BitVector.h"
  29. #include "llvm/ADT/FoldingSet.h"
  30. #include "llvm/ADT/ImmutableMap.h"
  31. #include "llvm/ADT/PostOrderIterator.h"
  32. #include "llvm/ADT/SmallVector.h"
  33. #include "llvm/ADT/StringRef.h"
  34. #include "llvm/Support/raw_ostream.h"
  35. #include <algorithm>
  36. #include <utility>
  37. #include <vector>
  38. using namespace clang;
  39. using namespace thread_safety;
  40. // Key method definition
  41. ThreadSafetyHandler::~ThreadSafetyHandler() {}
  42. namespace {
  43. /// \brief A MutexID object uniquely identifies a particular mutex, and
  44. /// is built from an Expr* (i.e. calling a lock function).
  45. ///
  46. /// Thread-safety analysis works by comparing lock expressions. Within the
  47. /// body of a function, an expression such as "x->foo->bar.mu" will resolve to
  48. /// a particular mutex object at run-time. Subsequent occurrences of the same
  49. /// expression (where "same" means syntactic equality) will refer to the same
  50. /// run-time object if three conditions hold:
  51. /// (1) Local variables in the expression, such as "x" have not changed.
  52. /// (2) Values on the heap that affect the expression have not changed.
  53. /// (3) The expression involves only pure function calls.
  54. ///
  55. /// The current implementation assumes, but does not verify, that multiple uses
  56. /// of the same lock expression satisfies these criteria.
  57. ///
  58. /// Clang introduces an additional wrinkle, which is that it is difficult to
  59. /// derive canonical expressions, or compare expressions directly for equality.
  60. /// Thus, we identify a mutex not by an Expr, but by the list of named
  61. /// declarations that are referenced by the Expr. In other words,
  62. /// x->foo->bar.mu will be a four element vector with the Decls for
  63. /// mu, bar, and foo, and x. The vector will uniquely identify the expression
  64. /// for all practical purposes. Null is used to denote 'this'.
  65. ///
  66. /// Note we will need to perform substitution on "this" and function parameter
  67. /// names when constructing a lock expression.
  68. ///
  69. /// For example:
  70. /// class C { Mutex Mu; void lock() EXCLUSIVE_LOCK_FUNCTION(this->Mu); };
  71. /// void myFunc(C *X) { ... X->lock() ... }
  72. /// The original expression for the mutex acquired by myFunc is "this->Mu", but
  73. /// "X" is substituted for "this" so we get X->Mu();
  74. ///
  75. /// For another example:
  76. /// foo(MyList *L) EXCLUSIVE_LOCKS_REQUIRED(L->Mu) { ... }
  77. /// MyList *MyL;
  78. /// foo(MyL); // requires lock MyL->Mu to be held
  79. class MutexID {
  80. SmallVector<NamedDecl*, 2> DeclSeq;
  81. /// \brief Encapsulates the lexical context of a function call. The lexical
  82. /// context includes the arguments to the call, including the implicit object
  83. /// argument. When an attribute containing a mutex expression is attached to
  84. /// a method, the expression may refer to formal parameters of the method.
  85. /// Actual arguments must be substituted for formal parameters to derive
  86. /// the appropriate mutex expression in the lexical context where the function
  87. /// is called. PrevCtx holds the context in which the arguments themselves
  88. /// should be evaluated; multiple calling contexts can be chained together
  89. /// by the lock_returned attribute.
  90. struct CallingContext {
  91. const NamedDecl* AttrDecl; // The decl to which the attribute is attached.
  92. Expr* SelfArg; // Implicit object argument -- e.g. 'this'
  93. unsigned NumArgs; // Number of funArgs
  94. Expr** FunArgs; // Function arguments
  95. CallingContext* PrevCtx; // The previous context; or 0 if none.
  96. CallingContext(const NamedDecl* D = 0, Expr* S = 0,
  97. unsigned N = 0, Expr** A = 0, CallingContext* P = 0)
  98. : AttrDecl(D), SelfArg(S), NumArgs(N), FunArgs(A), PrevCtx(P)
  99. { }
  100. };
  101. /// Build a Decl sequence representing the lock from the given expression.
  102. /// Recursive function that terminates on DeclRefExpr.
  103. /// Note: this function merely creates a MutexID; it does not check to
  104. /// ensure that the original expression is a valid mutex expression.
  105. void buildMutexID(Expr *Exp, CallingContext* CallCtx) {
  106. if (!Exp) {
  107. DeclSeq.clear();
  108. return;
  109. }
  110. if (DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(Exp)) {
  111. NamedDecl *ND = cast<NamedDecl>(DRE->getDecl()->getCanonicalDecl());
  112. ParmVarDecl *PV = dyn_cast_or_null<ParmVarDecl>(ND);
  113. if (PV) {
  114. FunctionDecl *FD =
  115. cast<FunctionDecl>(PV->getDeclContext())->getCanonicalDecl();
  116. unsigned i = PV->getFunctionScopeIndex();
  117. if (CallCtx && CallCtx->FunArgs &&
  118. FD == CallCtx->AttrDecl->getCanonicalDecl()) {
  119. // Substitute call arguments for references to function parameters
  120. assert(i < CallCtx->NumArgs);
  121. buildMutexID(CallCtx->FunArgs[i], CallCtx->PrevCtx);
  122. return;
  123. }
  124. // Map the param back to the param of the original function declaration.
  125. DeclSeq.push_back(FD->getParamDecl(i));
  126. return;
  127. }
  128. // Not a function parameter -- just store the reference.
  129. DeclSeq.push_back(ND);
  130. } else if (isa<CXXThisExpr>(Exp)) {
  131. // Substitute parent for 'this'
  132. if (CallCtx && CallCtx->SelfArg)
  133. buildMutexID(CallCtx->SelfArg, CallCtx->PrevCtx);
  134. else {
  135. DeclSeq.push_back(0); // Use 0 to represent 'this'.
  136. return; // mutexID is still valid in this case
  137. }
  138. } else if (MemberExpr *ME = dyn_cast<MemberExpr>(Exp)) {
  139. NamedDecl *ND = ME->getMemberDecl();
  140. DeclSeq.push_back(ND);
  141. buildMutexID(ME->getBase(), CallCtx);
  142. } else if (CXXMemberCallExpr *CMCE = dyn_cast<CXXMemberCallExpr>(Exp)) {
  143. // When calling a function with a lock_returned attribute, replace
  144. // the function call with the expression in lock_returned.
  145. if (LockReturnedAttr* At =
  146. CMCE->getMethodDecl()->getAttr<LockReturnedAttr>()) {
  147. CallingContext LRCallCtx(CMCE->getMethodDecl());
  148. LRCallCtx.SelfArg = CMCE->getImplicitObjectArgument();
  149. LRCallCtx.NumArgs = CMCE->getNumArgs();
  150. LRCallCtx.FunArgs = CMCE->getArgs();
  151. LRCallCtx.PrevCtx = CallCtx;
  152. buildMutexID(At->getArg(), &LRCallCtx);
  153. return;
  154. }
  155. DeclSeq.push_back(CMCE->getMethodDecl()->getCanonicalDecl());
  156. buildMutexID(CMCE->getImplicitObjectArgument(), CallCtx);
  157. unsigned NumCallArgs = CMCE->getNumArgs();
  158. Expr** CallArgs = CMCE->getArgs();
  159. for (unsigned i = 0; i < NumCallArgs; ++i) {
  160. buildMutexID(CallArgs[i], CallCtx);
  161. }
  162. } else if (CallExpr *CE = dyn_cast<CallExpr>(Exp)) {
  163. if (LockReturnedAttr* At =
  164. CE->getDirectCallee()->getAttr<LockReturnedAttr>()) {
  165. CallingContext LRCallCtx(CE->getDirectCallee());
  166. LRCallCtx.NumArgs = CE->getNumArgs();
  167. LRCallCtx.FunArgs = CE->getArgs();
  168. LRCallCtx.PrevCtx = CallCtx;
  169. buildMutexID(At->getArg(), &LRCallCtx);
  170. return;
  171. }
  172. buildMutexID(CE->getCallee(), CallCtx);
  173. unsigned NumCallArgs = CE->getNumArgs();
  174. Expr** CallArgs = CE->getArgs();
  175. for (unsigned i = 0; i < NumCallArgs; ++i) {
  176. buildMutexID(CallArgs[i], CallCtx);
  177. }
  178. } else if (BinaryOperator *BOE = dyn_cast<BinaryOperator>(Exp)) {
  179. buildMutexID(BOE->getLHS(), CallCtx);
  180. buildMutexID(BOE->getRHS(), CallCtx);
  181. } else if (UnaryOperator *UOE = dyn_cast<UnaryOperator>(Exp)) {
  182. buildMutexID(UOE->getSubExpr(), CallCtx);
  183. } else if (ArraySubscriptExpr *ASE = dyn_cast<ArraySubscriptExpr>(Exp)) {
  184. buildMutexID(ASE->getBase(), CallCtx);
  185. buildMutexID(ASE->getIdx(), CallCtx);
  186. } else if (AbstractConditionalOperator *CE =
  187. dyn_cast<AbstractConditionalOperator>(Exp)) {
  188. buildMutexID(CE->getCond(), CallCtx);
  189. buildMutexID(CE->getTrueExpr(), CallCtx);
  190. buildMutexID(CE->getFalseExpr(), CallCtx);
  191. } else if (ChooseExpr *CE = dyn_cast<ChooseExpr>(Exp)) {
  192. buildMutexID(CE->getCond(), CallCtx);
  193. buildMutexID(CE->getLHS(), CallCtx);
  194. buildMutexID(CE->getRHS(), CallCtx);
  195. } else if (CastExpr *CE = dyn_cast<CastExpr>(Exp)) {
  196. buildMutexID(CE->getSubExpr(), CallCtx);
  197. } else if (ParenExpr *PE = dyn_cast<ParenExpr>(Exp)) {
  198. buildMutexID(PE->getSubExpr(), CallCtx);
  199. } else if (isa<CharacterLiteral>(Exp) ||
  200. isa<CXXNullPtrLiteralExpr>(Exp) ||
  201. isa<GNUNullExpr>(Exp) ||
  202. isa<CXXBoolLiteralExpr>(Exp) ||
  203. isa<FloatingLiteral>(Exp) ||
  204. isa<ImaginaryLiteral>(Exp) ||
  205. isa<IntegerLiteral>(Exp) ||
  206. isa<StringLiteral>(Exp) ||
  207. isa<ObjCStringLiteral>(Exp)) {
  208. return; // FIXME: Ignore literals for now
  209. } else {
  210. // Ignore. FIXME: mark as invalid expression?
  211. }
  212. }
  213. /// \brief Construct a MutexID from an expression.
  214. /// \param MutexExp The original mutex expression within an attribute
  215. /// \param DeclExp An expression involving the Decl on which the attribute
  216. /// occurs.
  217. /// \param D The declaration to which the lock/unlock attribute is attached.
  218. void buildMutexIDFromExp(Expr *MutexExp, Expr *DeclExp, const NamedDecl *D) {
  219. CallingContext CallCtx(D);
  220. // If we are processing a raw attribute expression, with no substitutions.
  221. if (DeclExp == 0) {
  222. buildMutexID(MutexExp, 0);
  223. return;
  224. }
  225. // Examine DeclExp to find SelfArg and FunArgs, which are used to substitute
  226. // for formal parameters when we call buildMutexID later.
  227. if (MemberExpr *ME = dyn_cast<MemberExpr>(DeclExp)) {
  228. CallCtx.SelfArg = ME->getBase();
  229. } else if (CXXMemberCallExpr *CE = dyn_cast<CXXMemberCallExpr>(DeclExp)) {
  230. CallCtx.SelfArg = CE->getImplicitObjectArgument();
  231. CallCtx.NumArgs = CE->getNumArgs();
  232. CallCtx.FunArgs = CE->getArgs();
  233. } else if (CallExpr *CE = dyn_cast<CallExpr>(DeclExp)) {
  234. CallCtx.NumArgs = CE->getNumArgs();
  235. CallCtx.FunArgs = CE->getArgs();
  236. } else if (CXXConstructExpr *CE = dyn_cast<CXXConstructExpr>(DeclExp)) {
  237. CallCtx.SelfArg = 0; // FIXME -- get the parent from DeclStmt
  238. CallCtx.NumArgs = CE->getNumArgs();
  239. CallCtx.FunArgs = CE->getArgs();
  240. } else if (D && isa<CXXDestructorDecl>(D)) {
  241. // There's no such thing as a "destructor call" in the AST.
  242. CallCtx.SelfArg = DeclExp;
  243. }
  244. // If the attribute has no arguments, then assume the argument is "this".
  245. if (MutexExp == 0) {
  246. buildMutexID(CallCtx.SelfArg, 0);
  247. return;
  248. }
  249. // For most attributes.
  250. buildMutexID(MutexExp, &CallCtx);
  251. }
  252. public:
  253. explicit MutexID(clang::Decl::EmptyShell e) {
  254. DeclSeq.clear();
  255. }
  256. /// \param MutexExp The original mutex expression within an attribute
  257. /// \param DeclExp An expression involving the Decl on which the attribute
  258. /// occurs.
  259. /// \param D The declaration to which the lock/unlock attribute is attached.
  260. /// Caller must check isValid() after construction.
  261. MutexID(Expr* MutexExp, Expr *DeclExp, const NamedDecl* D) {
  262. buildMutexIDFromExp(MutexExp, DeclExp, D);
  263. }
  264. /// Return true if this is a valid decl sequence.
  265. /// Caller must call this by hand after construction to handle errors.
  266. bool isValid() const {
  267. return !DeclSeq.empty();
  268. }
  269. /// Issue a warning about an invalid lock expression
  270. static void warnInvalidLock(ThreadSafetyHandler &Handler, Expr* MutexExp,
  271. Expr *DeclExp, const NamedDecl* D) {
  272. SourceLocation Loc;
  273. if (DeclExp)
  274. Loc = DeclExp->getExprLoc();
  275. // FIXME: add a note about the attribute location in MutexExp or D
  276. if (Loc.isValid())
  277. Handler.handleInvalidLockExp(Loc);
  278. }
  279. bool operator==(const MutexID &other) const {
  280. return DeclSeq == other.DeclSeq;
  281. }
  282. bool operator!=(const MutexID &other) const {
  283. return !(*this == other);
  284. }
  285. // SmallVector overloads Operator< to do lexicographic ordering. Note that
  286. // we use pointer equality (and <) to compare NamedDecls. This means the order
  287. // of MutexIDs in a lockset is nondeterministic. In order to output
  288. // diagnostics in a deterministic ordering, we must order all diagnostics to
  289. // output by SourceLocation when iterating through this lockset.
  290. bool operator<(const MutexID &other) const {
  291. return DeclSeq < other.DeclSeq;
  292. }
  293. /// \brief Returns the name of the first Decl in the list for a given MutexID;
  294. /// e.g. the lock expression foo.bar() has name "bar".
  295. /// The caret will point unambiguously to the lock expression, so using this
  296. /// name in diagnostics is a way to get simple, and consistent, mutex names.
  297. /// We do not want to output the entire expression text for security reasons.
  298. std::string getName() const {
  299. assert(isValid());
  300. if (!DeclSeq.front())
  301. return "this"; // Use 0 to represent 'this'.
  302. return DeclSeq.front()->getNameAsString();
  303. }
  304. void Profile(llvm::FoldingSetNodeID &ID) const {
  305. for (SmallVectorImpl<NamedDecl*>::const_iterator I = DeclSeq.begin(),
  306. E = DeclSeq.end(); I != E; ++I) {
  307. ID.AddPointer(*I);
  308. }
  309. }
  310. };
  311. /// \brief This is a helper class that stores info about the most recent
  312. /// accquire of a Lock.
  313. ///
  314. /// The main body of the analysis maps MutexIDs to LockDatas.
  315. struct LockData {
  316. SourceLocation AcquireLoc;
  317. /// \brief LKind stores whether a lock is held shared or exclusively.
  318. /// Note that this analysis does not currently support either re-entrant
  319. /// locking or lock "upgrading" and "downgrading" between exclusive and
  320. /// shared.
  321. ///
  322. /// FIXME: add support for re-entrant locking and lock up/downgrading
  323. LockKind LKind;
  324. bool Managed; // for ScopedLockable objects
  325. MutexID UnderlyingMutex; // for ScopedLockable objects
  326. LockData(SourceLocation AcquireLoc, LockKind LKind, bool M = false)
  327. : AcquireLoc(AcquireLoc), LKind(LKind), Managed(M),
  328. UnderlyingMutex(Decl::EmptyShell())
  329. {}
  330. LockData(SourceLocation AcquireLoc, LockKind LKind, const MutexID &Mu)
  331. : AcquireLoc(AcquireLoc), LKind(LKind), Managed(false),
  332. UnderlyingMutex(Mu)
  333. {}
  334. bool operator==(const LockData &other) const {
  335. return AcquireLoc == other.AcquireLoc && LKind == other.LKind;
  336. }
  337. bool operator!=(const LockData &other) const {
  338. return !(*this == other);
  339. }
  340. void Profile(llvm::FoldingSetNodeID &ID) const {
  341. ID.AddInteger(AcquireLoc.getRawEncoding());
  342. ID.AddInteger(LKind);
  343. }
  344. };
  345. /// A Lockset maps each MutexID (defined above) to information about how it has
  346. /// been locked.
  347. typedef llvm::ImmutableMap<MutexID, LockData> Lockset;
  348. typedef llvm::ImmutableMap<const NamedDecl*, unsigned> LocalVarContext;
  349. class LocalVariableMap;
  350. /// A side (entry or exit) of a CFG node.
  351. enum CFGBlockSide { CBS_Entry, CBS_Exit };
  352. /// CFGBlockInfo is a struct which contains all the information that is
  353. /// maintained for each block in the CFG. See LocalVariableMap for more
  354. /// information about the contexts.
  355. struct CFGBlockInfo {
  356. Lockset EntrySet; // Lockset held at entry to block
  357. Lockset ExitSet; // Lockset held at exit from block
  358. LocalVarContext EntryContext; // Context held at entry to block
  359. LocalVarContext ExitContext; // Context held at exit from block
  360. SourceLocation EntryLoc; // Location of first statement in block
  361. SourceLocation ExitLoc; // Location of last statement in block.
  362. unsigned EntryIndex; // Used to replay contexts later
  363. const Lockset &getSet(CFGBlockSide Side) const {
  364. return Side == CBS_Entry ? EntrySet : ExitSet;
  365. }
  366. SourceLocation getLocation(CFGBlockSide Side) const {
  367. return Side == CBS_Entry ? EntryLoc : ExitLoc;
  368. }
  369. private:
  370. CFGBlockInfo(Lockset EmptySet, LocalVarContext EmptyCtx)
  371. : EntrySet(EmptySet), ExitSet(EmptySet),
  372. EntryContext(EmptyCtx), ExitContext(EmptyCtx)
  373. { }
  374. public:
  375. static CFGBlockInfo getEmptyBlockInfo(Lockset::Factory &F,
  376. LocalVariableMap &M);
  377. };
  378. // A LocalVariableMap maintains a map from local variables to their currently
  379. // valid definitions. It provides SSA-like functionality when traversing the
  380. // CFG. Like SSA, each definition or assignment to a variable is assigned a
  381. // unique name (an integer), which acts as the SSA name for that definition.
  382. // The total set of names is shared among all CFG basic blocks.
  383. // Unlike SSA, we do not rewrite expressions to replace local variables declrefs
  384. // with their SSA-names. Instead, we compute a Context for each point in the
  385. // code, which maps local variables to the appropriate SSA-name. This map
  386. // changes with each assignment.
  387. //
  388. // The map is computed in a single pass over the CFG. Subsequent analyses can
  389. // then query the map to find the appropriate Context for a statement, and use
  390. // that Context to look up the definitions of variables.
  391. class LocalVariableMap {
  392. public:
  393. typedef LocalVarContext Context;
  394. /// A VarDefinition consists of an expression, representing the value of the
  395. /// variable, along with the context in which that expression should be
  396. /// interpreted. A reference VarDefinition does not itself contain this
  397. /// information, but instead contains a pointer to a previous VarDefinition.
  398. struct VarDefinition {
  399. public:
  400. friend class LocalVariableMap;
  401. const NamedDecl *Dec; // The original declaration for this variable.
  402. const Expr *Exp; // The expression for this variable, OR
  403. unsigned Ref; // Reference to another VarDefinition
  404. Context Ctx; // The map with which Exp should be interpreted.
  405. bool isReference() { return !Exp; }
  406. private:
  407. // Create ordinary variable definition
  408. VarDefinition(const NamedDecl *D, const Expr *E, Context C)
  409. : Dec(D), Exp(E), Ref(0), Ctx(C)
  410. { }
  411. // Create reference to previous definition
  412. VarDefinition(const NamedDecl *D, unsigned R, Context C)
  413. : Dec(D), Exp(0), Ref(R), Ctx(C)
  414. { }
  415. };
  416. private:
  417. Context::Factory ContextFactory;
  418. std::vector<VarDefinition> VarDefinitions;
  419. std::vector<unsigned> CtxIndices;
  420. std::vector<std::pair<Stmt*, Context> > SavedContexts;
  421. public:
  422. LocalVariableMap() {
  423. // index 0 is a placeholder for undefined variables (aka phi-nodes).
  424. VarDefinitions.push_back(VarDefinition(0, 0u, getEmptyContext()));
  425. }
  426. /// Look up a definition, within the given context.
  427. const VarDefinition* lookup(const NamedDecl *D, Context Ctx) {
  428. const unsigned *i = Ctx.lookup(D);
  429. if (!i)
  430. return 0;
  431. assert(*i < VarDefinitions.size());
  432. return &VarDefinitions[*i];
  433. }
  434. /// Look up the definition for D within the given context. Returns
  435. /// NULL if the expression is not statically known. If successful, also
  436. /// modifies Ctx to hold the context of the return Expr.
  437. const Expr* lookupExpr(const NamedDecl *D, Context &Ctx) {
  438. const unsigned *P = Ctx.lookup(D);
  439. if (!P)
  440. return 0;
  441. unsigned i = *P;
  442. while (i > 0) {
  443. if (VarDefinitions[i].Exp) {
  444. Ctx = VarDefinitions[i].Ctx;
  445. return VarDefinitions[i].Exp;
  446. }
  447. i = VarDefinitions[i].Ref;
  448. }
  449. return 0;
  450. }
  451. Context getEmptyContext() { return ContextFactory.getEmptyMap(); }
  452. /// Return the next context after processing S. This function is used by
  453. /// clients of the class to get the appropriate context when traversing the
  454. /// CFG. It must be called for every assignment or DeclStmt.
  455. Context getNextContext(unsigned &CtxIndex, Stmt *S, Context C) {
  456. if (SavedContexts[CtxIndex+1].first == S) {
  457. CtxIndex++;
  458. Context Result = SavedContexts[CtxIndex].second;
  459. return Result;
  460. }
  461. return C;
  462. }
  463. void dumpVarDefinitionName(unsigned i) {
  464. if (i == 0) {
  465. llvm::errs() << "Undefined";
  466. return;
  467. }
  468. const NamedDecl *Dec = VarDefinitions[i].Dec;
  469. if (!Dec) {
  470. llvm::errs() << "<<NULL>>";
  471. return;
  472. }
  473. Dec->printName(llvm::errs());
  474. llvm::errs() << "." << i << " " << ((void*) Dec);
  475. }
  476. /// Dumps an ASCII representation of the variable map to llvm::errs()
  477. void dump() {
  478. for (unsigned i = 1, e = VarDefinitions.size(); i < e; ++i) {
  479. const Expr *Exp = VarDefinitions[i].Exp;
  480. unsigned Ref = VarDefinitions[i].Ref;
  481. dumpVarDefinitionName(i);
  482. llvm::errs() << " = ";
  483. if (Exp) Exp->dump();
  484. else {
  485. dumpVarDefinitionName(Ref);
  486. llvm::errs() << "\n";
  487. }
  488. }
  489. }
  490. /// Dumps an ASCII representation of a Context to llvm::errs()
  491. void dumpContext(Context C) {
  492. for (Context::iterator I = C.begin(), E = C.end(); I != E; ++I) {
  493. const NamedDecl *D = I.getKey();
  494. D->printName(llvm::errs());
  495. const unsigned *i = C.lookup(D);
  496. llvm::errs() << " -> ";
  497. dumpVarDefinitionName(*i);
  498. llvm::errs() << "\n";
  499. }
  500. }
  501. /// Builds the variable map.
  502. void traverseCFG(CFG *CFGraph, PostOrderCFGView *SortedGraph,
  503. std::vector<CFGBlockInfo> &BlockInfo);
  504. protected:
  505. // Get the current context index
  506. unsigned getContextIndex() { return SavedContexts.size()-1; }
  507. // Save the current context for later replay
  508. void saveContext(Stmt *S, Context C) {
  509. SavedContexts.push_back(std::make_pair(S,C));
  510. }
  511. // Adds a new definition to the given context, and returns a new context.
  512. // This method should be called when declaring a new variable.
  513. Context addDefinition(const NamedDecl *D, Expr *Exp, Context Ctx) {
  514. assert(!Ctx.contains(D));
  515. unsigned newID = VarDefinitions.size();
  516. Context NewCtx = ContextFactory.add(Ctx, D, newID);
  517. VarDefinitions.push_back(VarDefinition(D, Exp, Ctx));
  518. return NewCtx;
  519. }
  520. // Add a new reference to an existing definition.
  521. Context addReference(const NamedDecl *D, unsigned i, Context Ctx) {
  522. unsigned newID = VarDefinitions.size();
  523. Context NewCtx = ContextFactory.add(Ctx, D, newID);
  524. VarDefinitions.push_back(VarDefinition(D, i, Ctx));
  525. return NewCtx;
  526. }
  527. // Updates a definition only if that definition is already in the map.
  528. // This method should be called when assigning to an existing variable.
  529. Context updateDefinition(const NamedDecl *D, Expr *Exp, Context Ctx) {
  530. if (Ctx.contains(D)) {
  531. unsigned newID = VarDefinitions.size();
  532. Context NewCtx = ContextFactory.remove(Ctx, D);
  533. NewCtx = ContextFactory.add(NewCtx, D, newID);
  534. VarDefinitions.push_back(VarDefinition(D, Exp, Ctx));
  535. return NewCtx;
  536. }
  537. return Ctx;
  538. }
  539. // Removes a definition from the context, but keeps the variable name
  540. // as a valid variable. The index 0 is a placeholder for cleared definitions.
  541. Context clearDefinition(const NamedDecl *D, Context Ctx) {
  542. Context NewCtx = Ctx;
  543. if (NewCtx.contains(D)) {
  544. NewCtx = ContextFactory.remove(NewCtx, D);
  545. NewCtx = ContextFactory.add(NewCtx, D, 0);
  546. }
  547. return NewCtx;
  548. }
  549. // Remove a definition entirely frmo the context.
  550. Context removeDefinition(const NamedDecl *D, Context Ctx) {
  551. Context NewCtx = Ctx;
  552. if (NewCtx.contains(D)) {
  553. NewCtx = ContextFactory.remove(NewCtx, D);
  554. }
  555. return NewCtx;
  556. }
  557. Context intersectContexts(Context C1, Context C2);
  558. Context createReferenceContext(Context C);
  559. void intersectBackEdge(Context C1, Context C2);
  560. friend class VarMapBuilder;
  561. };
  562. // This has to be defined after LocalVariableMap.
  563. CFGBlockInfo CFGBlockInfo::getEmptyBlockInfo(Lockset::Factory &F,
  564. LocalVariableMap &M) {
  565. return CFGBlockInfo(F.getEmptyMap(), M.getEmptyContext());
  566. }
  567. /// Visitor which builds a LocalVariableMap
  568. class VarMapBuilder : public StmtVisitor<VarMapBuilder> {
  569. public:
  570. LocalVariableMap* VMap;
  571. LocalVariableMap::Context Ctx;
  572. VarMapBuilder(LocalVariableMap *VM, LocalVariableMap::Context C)
  573. : VMap(VM), Ctx(C) {}
  574. void VisitDeclStmt(DeclStmt *S);
  575. void VisitBinaryOperator(BinaryOperator *BO);
  576. };
  577. // Add new local variables to the variable map
  578. void VarMapBuilder::VisitDeclStmt(DeclStmt *S) {
  579. bool modifiedCtx = false;
  580. DeclGroupRef DGrp = S->getDeclGroup();
  581. for (DeclGroupRef::iterator I = DGrp.begin(), E = DGrp.end(); I != E; ++I) {
  582. if (VarDecl *VD = dyn_cast_or_null<VarDecl>(*I)) {
  583. Expr *E = VD->getInit();
  584. // Add local variables with trivial type to the variable map
  585. QualType T = VD->getType();
  586. if (T.isTrivialType(VD->getASTContext())) {
  587. Ctx = VMap->addDefinition(VD, E, Ctx);
  588. modifiedCtx = true;
  589. }
  590. }
  591. }
  592. if (modifiedCtx)
  593. VMap->saveContext(S, Ctx);
  594. }
  595. // Update local variable definitions in variable map
  596. void VarMapBuilder::VisitBinaryOperator(BinaryOperator *BO) {
  597. if (!BO->isAssignmentOp())
  598. return;
  599. Expr *LHSExp = BO->getLHS()->IgnoreParenCasts();
  600. // Update the variable map and current context.
  601. if (DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(LHSExp)) {
  602. ValueDecl *VDec = DRE->getDecl();
  603. if (Ctx.lookup(VDec)) {
  604. if (BO->getOpcode() == BO_Assign)
  605. Ctx = VMap->updateDefinition(VDec, BO->getRHS(), Ctx);
  606. else
  607. // FIXME -- handle compound assignment operators
  608. Ctx = VMap->clearDefinition(VDec, Ctx);
  609. VMap->saveContext(BO, Ctx);
  610. }
  611. }
  612. }
  613. // Computes the intersection of two contexts. The intersection is the
  614. // set of variables which have the same definition in both contexts;
  615. // variables with different definitions are discarded.
  616. LocalVariableMap::Context
  617. LocalVariableMap::intersectContexts(Context C1, Context C2) {
  618. Context Result = C1;
  619. for (Context::iterator I = C1.begin(), E = C1.end(); I != E; ++I) {
  620. const NamedDecl *Dec = I.getKey();
  621. unsigned i1 = I.getData();
  622. const unsigned *i2 = C2.lookup(Dec);
  623. if (!i2) // variable doesn't exist on second path
  624. Result = removeDefinition(Dec, Result);
  625. else if (*i2 != i1) // variable exists, but has different definition
  626. Result = clearDefinition(Dec, Result);
  627. }
  628. return Result;
  629. }
  630. // For every variable in C, create a new variable that refers to the
  631. // definition in C. Return a new context that contains these new variables.
  632. // (We use this for a naive implementation of SSA on loop back-edges.)
  633. LocalVariableMap::Context LocalVariableMap::createReferenceContext(Context C) {
  634. Context Result = getEmptyContext();
  635. for (Context::iterator I = C.begin(), E = C.end(); I != E; ++I) {
  636. const NamedDecl *Dec = I.getKey();
  637. unsigned i = I.getData();
  638. Result = addReference(Dec, i, Result);
  639. }
  640. return Result;
  641. }
  642. // This routine also takes the intersection of C1 and C2, but it does so by
  643. // altering the VarDefinitions. C1 must be the result of an earlier call to
  644. // createReferenceContext.
  645. void LocalVariableMap::intersectBackEdge(Context C1, Context C2) {
  646. for (Context::iterator I = C1.begin(), E = C1.end(); I != E; ++I) {
  647. const NamedDecl *Dec = I.getKey();
  648. unsigned i1 = I.getData();
  649. VarDefinition *VDef = &VarDefinitions[i1];
  650. assert(VDef->isReference());
  651. const unsigned *i2 = C2.lookup(Dec);
  652. if (!i2 || (*i2 != i1))
  653. VDef->Ref = 0; // Mark this variable as undefined
  654. }
  655. }
  656. // Traverse the CFG in topological order, so all predecessors of a block
  657. // (excluding back-edges) are visited before the block itself. At
  658. // each point in the code, we calculate a Context, which holds the set of
  659. // variable definitions which are visible at that point in execution.
  660. // Visible variables are mapped to their definitions using an array that
  661. // contains all definitions.
  662. //
  663. // At join points in the CFG, the set is computed as the intersection of
  664. // the incoming sets along each edge, E.g.
  665. //
  666. // { Context | VarDefinitions }
  667. // int x = 0; { x -> x1 | x1 = 0 }
  668. // int y = 0; { x -> x1, y -> y1 | y1 = 0, x1 = 0 }
  669. // if (b) x = 1; { x -> x2, y -> y1 | x2 = 1, y1 = 0, ... }
  670. // else x = 2; { x -> x3, y -> y1 | x3 = 2, x2 = 1, ... }
  671. // ... { y -> y1 (x is unknown) | x3 = 2, x2 = 1, ... }
  672. //
  673. // This is essentially a simpler and more naive version of the standard SSA
  674. // algorithm. Those definitions that remain in the intersection are from blocks
  675. // that strictly dominate the current block. We do not bother to insert proper
  676. // phi nodes, because they are not used in our analysis; instead, wherever
  677. // a phi node would be required, we simply remove that definition from the
  678. // context (E.g. x above).
  679. //
  680. // The initial traversal does not capture back-edges, so those need to be
  681. // handled on a separate pass. Whenever the first pass encounters an
  682. // incoming back edge, it duplicates the context, creating new definitions
  683. // that refer back to the originals. (These correspond to places where SSA
  684. // might have to insert a phi node.) On the second pass, these definitions are
  685. // set to NULL if the the variable has changed on the back-edge (i.e. a phi
  686. // node was actually required.) E.g.
  687. //
  688. // { Context | VarDefinitions }
  689. // int x = 0, y = 0; { x -> x1, y -> y1 | y1 = 0, x1 = 0 }
  690. // while (b) { x -> x2, y -> y1 | [1st:] x2=x1; [2nd:] x2=NULL; }
  691. // x = x+1; { x -> x3, y -> y1 | x3 = x2 + 1, ... }
  692. // ... { y -> y1 | x3 = 2, x2 = 1, ... }
  693. //
  694. void LocalVariableMap::traverseCFG(CFG *CFGraph,
  695. PostOrderCFGView *SortedGraph,
  696. std::vector<CFGBlockInfo> &BlockInfo) {
  697. PostOrderCFGView::CFGBlockSet VisitedBlocks(CFGraph);
  698. CtxIndices.resize(CFGraph->getNumBlockIDs());
  699. for (PostOrderCFGView::iterator I = SortedGraph->begin(),
  700. E = SortedGraph->end(); I!= E; ++I) {
  701. const CFGBlock *CurrBlock = *I;
  702. int CurrBlockID = CurrBlock->getBlockID();
  703. CFGBlockInfo *CurrBlockInfo = &BlockInfo[CurrBlockID];
  704. VisitedBlocks.insert(CurrBlock);
  705. // Calculate the entry context for the current block
  706. bool HasBackEdges = false;
  707. bool CtxInit = true;
  708. for (CFGBlock::const_pred_iterator PI = CurrBlock->pred_begin(),
  709. PE = CurrBlock->pred_end(); PI != PE; ++PI) {
  710. // if *PI -> CurrBlock is a back edge, so skip it
  711. if (*PI == 0 || !VisitedBlocks.alreadySet(*PI)) {
  712. HasBackEdges = true;
  713. continue;
  714. }
  715. int PrevBlockID = (*PI)->getBlockID();
  716. CFGBlockInfo *PrevBlockInfo = &BlockInfo[PrevBlockID];
  717. if (CtxInit) {
  718. CurrBlockInfo->EntryContext = PrevBlockInfo->ExitContext;
  719. CtxInit = false;
  720. }
  721. else {
  722. CurrBlockInfo->EntryContext =
  723. intersectContexts(CurrBlockInfo->EntryContext,
  724. PrevBlockInfo->ExitContext);
  725. }
  726. }
  727. // Duplicate the context if we have back-edges, so we can call
  728. // intersectBackEdges later.
  729. if (HasBackEdges)
  730. CurrBlockInfo->EntryContext =
  731. createReferenceContext(CurrBlockInfo->EntryContext);
  732. // Create a starting context index for the current block
  733. saveContext(0, CurrBlockInfo->EntryContext);
  734. CurrBlockInfo->EntryIndex = getContextIndex();
  735. // Visit all the statements in the basic block.
  736. VarMapBuilder VMapBuilder(this, CurrBlockInfo->EntryContext);
  737. for (CFGBlock::const_iterator BI = CurrBlock->begin(),
  738. BE = CurrBlock->end(); BI != BE; ++BI) {
  739. switch (BI->getKind()) {
  740. case CFGElement::Statement: {
  741. const CFGStmt *CS = cast<CFGStmt>(&*BI);
  742. VMapBuilder.Visit(const_cast<Stmt*>(CS->getStmt()));
  743. break;
  744. }
  745. default:
  746. break;
  747. }
  748. }
  749. CurrBlockInfo->ExitContext = VMapBuilder.Ctx;
  750. // Mark variables on back edges as "unknown" if they've been changed.
  751. for (CFGBlock::const_succ_iterator SI = CurrBlock->succ_begin(),
  752. SE = CurrBlock->succ_end(); SI != SE; ++SI) {
  753. // if CurrBlock -> *SI is *not* a back edge
  754. if (*SI == 0 || !VisitedBlocks.alreadySet(*SI))
  755. continue;
  756. CFGBlock *FirstLoopBlock = *SI;
  757. Context LoopBegin = BlockInfo[FirstLoopBlock->getBlockID()].EntryContext;
  758. Context LoopEnd = CurrBlockInfo->ExitContext;
  759. intersectBackEdge(LoopBegin, LoopEnd);
  760. }
  761. }
  762. // Put an extra entry at the end of the indexed context array
  763. unsigned exitID = CFGraph->getExit().getBlockID();
  764. saveContext(0, BlockInfo[exitID].ExitContext);
  765. }
  766. /// Find the appropriate source locations to use when producing diagnostics for
  767. /// each block in the CFG.
  768. static void findBlockLocations(CFG *CFGraph,
  769. PostOrderCFGView *SortedGraph,
  770. std::vector<CFGBlockInfo> &BlockInfo) {
  771. for (PostOrderCFGView::iterator I = SortedGraph->begin(),
  772. E = SortedGraph->end(); I!= E; ++I) {
  773. const CFGBlock *CurrBlock = *I;
  774. CFGBlockInfo *CurrBlockInfo = &BlockInfo[CurrBlock->getBlockID()];
  775. // Find the source location of the last statement in the block, if the
  776. // block is not empty.
  777. if (const Stmt *S = CurrBlock->getTerminator()) {
  778. CurrBlockInfo->EntryLoc = CurrBlockInfo->ExitLoc = S->getLocStart();
  779. } else {
  780. for (CFGBlock::const_reverse_iterator BI = CurrBlock->rbegin(),
  781. BE = CurrBlock->rend(); BI != BE; ++BI) {
  782. // FIXME: Handle other CFGElement kinds.
  783. if (const CFGStmt *CS = dyn_cast<CFGStmt>(&*BI)) {
  784. CurrBlockInfo->ExitLoc = CS->getStmt()->getLocStart();
  785. break;
  786. }
  787. }
  788. }
  789. if (!CurrBlockInfo->ExitLoc.isInvalid()) {
  790. // This block contains at least one statement. Find the source location
  791. // of the first statement in the block.
  792. for (CFGBlock::const_iterator BI = CurrBlock->begin(),
  793. BE = CurrBlock->end(); BI != BE; ++BI) {
  794. // FIXME: Handle other CFGElement kinds.
  795. if (const CFGStmt *CS = dyn_cast<CFGStmt>(&*BI)) {
  796. CurrBlockInfo->EntryLoc = CS->getStmt()->getLocStart();
  797. break;
  798. }
  799. }
  800. } else if (CurrBlock->pred_size() == 1 && *CurrBlock->pred_begin() &&
  801. CurrBlock != &CFGraph->getExit()) {
  802. // The block is empty, and has a single predecessor. Use its exit
  803. // location.
  804. CurrBlockInfo->EntryLoc = CurrBlockInfo->ExitLoc =
  805. BlockInfo[(*CurrBlock->pred_begin())->getBlockID()].ExitLoc;
  806. }
  807. }
  808. }
  809. /// \brief Class which implements the core thread safety analysis routines.
  810. class ThreadSafetyAnalyzer {
  811. friend class BuildLockset;
  812. ThreadSafetyHandler &Handler;
  813. Lockset::Factory LocksetFactory;
  814. LocalVariableMap LocalVarMap;
  815. std::vector<CFGBlockInfo> BlockInfo;
  816. public:
  817. ThreadSafetyAnalyzer(ThreadSafetyHandler &H) : Handler(H) {}
  818. Lockset addLock(const Lockset &LSet, const MutexID &Mutex,
  819. const LockData &LDat, bool Warn=true);
  820. Lockset addLock(const Lockset &LSet, Expr *MutexExp, const NamedDecl *D,
  821. const LockData &LDat, bool Warn=true);
  822. Lockset removeLock(const Lockset &LSet, const MutexID &Mutex,
  823. SourceLocation UnlockLoc,
  824. bool Warn=true, bool FullyRemove=false);
  825. template <class AttrType>
  826. Lockset addLocksToSet(const Lockset &LSet, LockKind LK, AttrType *Attr,
  827. Expr *Exp, NamedDecl *D, VarDecl *VD = 0);
  828. Lockset removeLocksFromSet(const Lockset &LSet,
  829. UnlockFunctionAttr *Attr,
  830. Expr *Exp, NamedDecl* FunDecl);
  831. template <class AttrType>
  832. Lockset addTrylock(const Lockset &LSet,
  833. LockKind LK, AttrType *Attr, Expr *Exp, NamedDecl *FunDecl,
  834. const CFGBlock* PredBlock, const CFGBlock *CurrBlock,
  835. Expr *BrE, bool Neg);
  836. const CallExpr* getTrylockCallExpr(const Stmt *Cond, LocalVarContext C,
  837. bool &Negate);
  838. Lockset getEdgeLockset(const Lockset &ExitSet,
  839. const CFGBlock* PredBlock,
  840. const CFGBlock *CurrBlock);
  841. Lockset intersectAndWarn(const Lockset &LSet1, const Lockset &LSet2,
  842. SourceLocation JoinLoc, LockErrorKind LEK);
  843. void runAnalysis(AnalysisDeclContext &AC);
  844. };
  845. /// \brief Add a new lock to the lockset, warning if the lock is already there.
  846. /// \param Mutex -- the Mutex expression for the lock
  847. /// \param LDat -- the LockData for the lock
  848. Lockset ThreadSafetyAnalyzer::addLock(const Lockset &LSet,
  849. const MutexID &Mutex,
  850. const LockData &LDat,
  851. bool Warn) {
  852. // FIXME: deal with acquired before/after annotations.
  853. // FIXME: Don't always warn when we have support for reentrant locks.
  854. if (LSet.lookup(Mutex)) {
  855. if (Warn)
  856. Handler.handleDoubleLock(Mutex.getName(), LDat.AcquireLoc);
  857. return LSet;
  858. } else {
  859. return LocksetFactory.add(LSet, Mutex, LDat);
  860. }
  861. }
  862. /// \brief Construct a new mutex and add it to the lockset.
  863. Lockset ThreadSafetyAnalyzer::addLock(const Lockset &LSet,
  864. Expr *MutexExp, const NamedDecl *D,
  865. const LockData &LDat,
  866. bool Warn) {
  867. MutexID Mutex(MutexExp, 0, D);
  868. if (!Mutex.isValid()) {
  869. MutexID::warnInvalidLock(Handler, MutexExp, 0, D);
  870. return LSet;
  871. }
  872. return addLock(LSet, Mutex, LDat, Warn);
  873. }
  874. /// \brief Remove a lock from the lockset, warning if the lock is not there.
  875. /// \param LockExp The lock expression corresponding to the lock to be removed
  876. /// \param UnlockLoc The source location of the unlock (only used in error msg)
  877. Lockset ThreadSafetyAnalyzer::removeLock(const Lockset &LSet,
  878. const MutexID &Mutex,
  879. SourceLocation UnlockLoc,
  880. bool Warn, bool FullyRemove) {
  881. const LockData *LDat = LSet.lookup(Mutex);
  882. if (!LDat) {
  883. if (Warn)
  884. Handler.handleUnmatchedUnlock(Mutex.getName(), UnlockLoc);
  885. return LSet;
  886. }
  887. else {
  888. Lockset Result = LSet;
  889. if (LDat->UnderlyingMutex.isValid()) {
  890. // For scoped-lockable vars, remove the mutex associated with this var.
  891. Result = removeLock(Result, LDat->UnderlyingMutex, UnlockLoc,
  892. false, true);
  893. // Fully remove the object only when the destructor is called
  894. if (FullyRemove)
  895. return LocksetFactory.remove(Result, Mutex);
  896. else
  897. return Result;
  898. }
  899. return LocksetFactory.remove(Result, Mutex);
  900. }
  901. }
  902. /// \brief This function, parameterized by an attribute type, is used to add a
  903. /// set of locks specified as attribute arguments to the lockset.
  904. template <typename AttrType>
  905. Lockset ThreadSafetyAnalyzer::addLocksToSet(const Lockset &LSet,
  906. LockKind LK, AttrType *Attr,
  907. Expr *Exp, NamedDecl* FunDecl,
  908. VarDecl *VD) {
  909. typedef typename AttrType::args_iterator iterator_type;
  910. SourceLocation ExpLocation = Exp->getExprLoc();
  911. // Figure out if we're calling the constructor of scoped lockable class
  912. bool isScopedVar = false;
  913. if (VD) {
  914. if (CXXConstructorDecl *CD = dyn_cast<CXXConstructorDecl>(FunDecl)) {
  915. CXXRecordDecl* PD = CD->getParent();
  916. if (PD && PD->getAttr<ScopedLockableAttr>())
  917. isScopedVar = true;
  918. }
  919. }
  920. if (Attr->args_size() == 0) {
  921. // The mutex held is the "this" object.
  922. MutexID Mutex(0, Exp, FunDecl);
  923. if (!Mutex.isValid()) {
  924. MutexID::warnInvalidLock(Handler, 0, Exp, FunDecl);
  925. return LSet;
  926. }
  927. else {
  928. return addLock(LSet, Mutex, LockData(ExpLocation, LK));
  929. }
  930. }
  931. Lockset Result = LSet;
  932. for (iterator_type I=Attr->args_begin(), E=Attr->args_end(); I != E; ++I) {
  933. MutexID Mutex(*I, Exp, FunDecl);
  934. if (!Mutex.isValid())
  935. MutexID::warnInvalidLock(Handler, *I, Exp, FunDecl);
  936. else {
  937. if (isScopedVar) {
  938. // Mutex is managed by scoped var -- suppress certain warnings.
  939. Result = addLock(Result, Mutex, LockData(ExpLocation, LK, true));
  940. // For scoped lockable vars, map this var to its underlying mutex.
  941. DeclRefExpr DRE(VD, false, VD->getType(), VK_LValue, VD->getLocation());
  942. MutexID SMutex(&DRE, 0, 0);
  943. Result = addLock(Result, SMutex,
  944. LockData(VD->getLocation(), LK, Mutex));
  945. }
  946. else {
  947. Result = addLock(Result, Mutex, LockData(ExpLocation, LK));
  948. }
  949. }
  950. }
  951. return Result;
  952. }
  953. /// \brief This function removes a set of locks specified as attribute
  954. /// arguments from the lockset.
  955. Lockset ThreadSafetyAnalyzer::removeLocksFromSet(const Lockset &LSet,
  956. UnlockFunctionAttr *Attr,
  957. Expr *Exp,
  958. NamedDecl* FunDecl) {
  959. SourceLocation ExpLocation;
  960. if (Exp) ExpLocation = Exp->getExprLoc();
  961. bool Dtor = isa<CXXDestructorDecl>(FunDecl);
  962. if (Attr->args_size() == 0) {
  963. // The mutex held is the "this" object.
  964. MutexID Mu(0, Exp, FunDecl);
  965. if (!Mu.isValid()) {
  966. MutexID::warnInvalidLock(Handler, 0, Exp, FunDecl);
  967. return LSet;
  968. } else {
  969. return removeLock(LSet, Mu, ExpLocation, true, Dtor);
  970. }
  971. }
  972. Lockset Result = LSet;
  973. for (UnlockFunctionAttr::args_iterator I = Attr->args_begin(),
  974. E = Attr->args_end(); I != E; ++I) {
  975. MutexID Mutex(*I, Exp, FunDecl);
  976. if (!Mutex.isValid())
  977. MutexID::warnInvalidLock(Handler, *I, Exp, FunDecl);
  978. else
  979. Result = removeLock(Result, Mutex, ExpLocation, true, Dtor);
  980. }
  981. return Result;
  982. }
  983. /// \brief Add lock to set, if the current block is in the taken branch of a
  984. /// trylock.
  985. template <class AttrType>
  986. Lockset ThreadSafetyAnalyzer::addTrylock(const Lockset &LSet,
  987. LockKind LK, AttrType *Attr,
  988. Expr *Exp, NamedDecl *FunDecl,
  989. const CFGBlock *PredBlock,
  990. const CFGBlock *CurrBlock,
  991. Expr *BrE, bool Neg) {
  992. // Find out which branch has the lock
  993. bool branch = 0;
  994. if (CXXBoolLiteralExpr *BLE = dyn_cast_or_null<CXXBoolLiteralExpr>(BrE)) {
  995. branch = BLE->getValue();
  996. }
  997. else if (IntegerLiteral *ILE = dyn_cast_or_null<IntegerLiteral>(BrE)) {
  998. branch = ILE->getValue().getBoolValue();
  999. }
  1000. int branchnum = branch ? 0 : 1;
  1001. if (Neg) branchnum = !branchnum;
  1002. Lockset Result = LSet;
  1003. // If we've taken the trylock branch, then add the lock
  1004. int i = 0;
  1005. for (CFGBlock::const_succ_iterator SI = PredBlock->succ_begin(),
  1006. SE = PredBlock->succ_end(); SI != SE && i < 2; ++SI, ++i) {
  1007. if (*SI == CurrBlock && i == branchnum) {
  1008. Result = addLocksToSet(Result, LK, Attr, Exp, FunDecl, 0);
  1009. }
  1010. }
  1011. return Result;
  1012. }
  1013. // If Cond can be traced back to a function call, return the call expression.
  1014. // The negate variable should be called with false, and will be set to true
  1015. // if the function call is negated, e.g. if (!mu.tryLock(...))
  1016. const CallExpr* ThreadSafetyAnalyzer::getTrylockCallExpr(const Stmt *Cond,
  1017. LocalVarContext C,
  1018. bool &Negate) {
  1019. if (!Cond)
  1020. return 0;
  1021. if (const CallExpr *CallExp = dyn_cast<CallExpr>(Cond)) {
  1022. return CallExp;
  1023. }
  1024. else if (const ImplicitCastExpr *CE = dyn_cast<ImplicitCastExpr>(Cond)) {
  1025. return getTrylockCallExpr(CE->getSubExpr(), C, Negate);
  1026. }
  1027. else if (const DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(Cond)) {
  1028. const Expr *E = LocalVarMap.lookupExpr(DRE->getDecl(), C);
  1029. return getTrylockCallExpr(E, C, Negate);
  1030. }
  1031. else if (const UnaryOperator *UOP = dyn_cast<UnaryOperator>(Cond)) {
  1032. if (UOP->getOpcode() == UO_LNot) {
  1033. Negate = !Negate;
  1034. return getTrylockCallExpr(UOP->getSubExpr(), C, Negate);
  1035. }
  1036. }
  1037. // FIXME -- handle && and || as well.
  1038. return NULL;
  1039. }
  1040. /// \brief Find the lockset that holds on the edge between PredBlock
  1041. /// and CurrBlock. The edge set is the exit set of PredBlock (passed
  1042. /// as the ExitSet parameter) plus any trylocks, which are conditionally held.
  1043. Lockset ThreadSafetyAnalyzer::getEdgeLockset(const Lockset &ExitSet,
  1044. const CFGBlock *PredBlock,
  1045. const CFGBlock *CurrBlock) {
  1046. if (!PredBlock->getTerminatorCondition())
  1047. return ExitSet;
  1048. bool Negate = false;
  1049. const Stmt *Cond = PredBlock->getTerminatorCondition();
  1050. const CFGBlockInfo *PredBlockInfo = &BlockInfo[PredBlock->getBlockID()];
  1051. const LocalVarContext &LVarCtx = PredBlockInfo->ExitContext;
  1052. CallExpr *Exp = const_cast<CallExpr*>(
  1053. getTrylockCallExpr(Cond, LVarCtx, Negate));
  1054. if (!Exp)
  1055. return ExitSet;
  1056. NamedDecl *FunDecl = dyn_cast_or_null<NamedDecl>(Exp->getCalleeDecl());
  1057. if(!FunDecl || !FunDecl->hasAttrs())
  1058. return ExitSet;
  1059. Lockset Result = ExitSet;
  1060. // If the condition is a call to a Trylock function, then grab the attributes
  1061. AttrVec &ArgAttrs = FunDecl->getAttrs();
  1062. for (unsigned i = 0; i < ArgAttrs.size(); ++i) {
  1063. Attr *Attr = ArgAttrs[i];
  1064. switch (Attr->getKind()) {
  1065. case attr::ExclusiveTrylockFunction: {
  1066. ExclusiveTrylockFunctionAttr *A =
  1067. cast<ExclusiveTrylockFunctionAttr>(Attr);
  1068. Result = addTrylock(Result, LK_Exclusive, A, Exp, FunDecl,
  1069. PredBlock, CurrBlock,
  1070. A->getSuccessValue(), Negate);
  1071. break;
  1072. }
  1073. case attr::SharedTrylockFunction: {
  1074. SharedTrylockFunctionAttr *A =
  1075. cast<SharedTrylockFunctionAttr>(Attr);
  1076. Result = addTrylock(Result, LK_Shared, A, Exp, FunDecl,
  1077. PredBlock, CurrBlock,
  1078. A->getSuccessValue(), Negate);
  1079. break;
  1080. }
  1081. default:
  1082. break;
  1083. }
  1084. }
  1085. return Result;
  1086. }
  1087. /// \brief We use this class to visit different types of expressions in
  1088. /// CFGBlocks, and build up the lockset.
  1089. /// An expression may cause us to add or remove locks from the lockset, or else
  1090. /// output error messages related to missing locks.
  1091. /// FIXME: In future, we may be able to not inherit from a visitor.
  1092. class BuildLockset : public StmtVisitor<BuildLockset> {
  1093. friend class ThreadSafetyAnalyzer;
  1094. ThreadSafetyAnalyzer *Analyzer;
  1095. Lockset LSet;
  1096. LocalVariableMap::Context LVarCtx;
  1097. unsigned CtxIndex;
  1098. // Helper functions
  1099. const ValueDecl *getValueDecl(Expr *Exp);
  1100. void warnIfMutexNotHeld(const NamedDecl *D, Expr *Exp, AccessKind AK,
  1101. Expr *MutexExp, ProtectedOperationKind POK);
  1102. void checkAccess(Expr *Exp, AccessKind AK);
  1103. void checkDereference(Expr *Exp, AccessKind AK);
  1104. void handleCall(Expr *Exp, NamedDecl *D, VarDecl *VD = 0);
  1105. /// \brief Returns true if the lockset contains a lock, regardless of whether
  1106. /// the lock is held exclusively or shared.
  1107. bool locksetContains(const MutexID &Lock) const {
  1108. return LSet.lookup(Lock);
  1109. }
  1110. /// \brief Returns true if the lockset contains a lock with the passed in
  1111. /// locktype.
  1112. bool locksetContains(const MutexID &Lock, LockKind KindRequested) const {
  1113. const LockData *LockHeld = LSet.lookup(Lock);
  1114. return (LockHeld && KindRequested == LockHeld->LKind);
  1115. }
  1116. /// \brief Returns true if the lockset contains a lock with at least the
  1117. /// passed in locktype. So for example, if we pass in LK_Shared, this function
  1118. /// returns true if the lock is held LK_Shared or LK_Exclusive. If we pass in
  1119. /// LK_Exclusive, this function returns true if the lock is held LK_Exclusive.
  1120. bool locksetContainsAtLeast(const MutexID &Lock,
  1121. LockKind KindRequested) const {
  1122. switch (KindRequested) {
  1123. case LK_Shared:
  1124. return locksetContains(Lock);
  1125. case LK_Exclusive:
  1126. return locksetContains(Lock, KindRequested);
  1127. }
  1128. llvm_unreachable("Unknown LockKind");
  1129. }
  1130. public:
  1131. BuildLockset(ThreadSafetyAnalyzer *Anlzr, CFGBlockInfo &Info)
  1132. : StmtVisitor<BuildLockset>(),
  1133. Analyzer(Anlzr),
  1134. LSet(Info.EntrySet),
  1135. LVarCtx(Info.EntryContext),
  1136. CtxIndex(Info.EntryIndex)
  1137. {}
  1138. void VisitUnaryOperator(UnaryOperator *UO);
  1139. void VisitBinaryOperator(BinaryOperator *BO);
  1140. void VisitCastExpr(CastExpr *CE);
  1141. void VisitCallExpr(CallExpr *Exp);
  1142. void VisitCXXConstructExpr(CXXConstructExpr *Exp);
  1143. void VisitDeclStmt(DeclStmt *S);
  1144. };
  1145. /// \brief Gets the value decl pointer from DeclRefExprs or MemberExprs
  1146. const ValueDecl *BuildLockset::getValueDecl(Expr *Exp) {
  1147. if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(Exp))
  1148. return DR->getDecl();
  1149. if (const MemberExpr *ME = dyn_cast<MemberExpr>(Exp))
  1150. return ME->getMemberDecl();
  1151. return 0;
  1152. }
  1153. /// \brief Warn if the LSet does not contain a lock sufficient to protect access
  1154. /// of at least the passed in AccessKind.
  1155. void BuildLockset::warnIfMutexNotHeld(const NamedDecl *D, Expr *Exp,
  1156. AccessKind AK, Expr *MutexExp,
  1157. ProtectedOperationKind POK) {
  1158. LockKind LK = getLockKindFromAccessKind(AK);
  1159. MutexID Mutex(MutexExp, Exp, D);
  1160. if (!Mutex.isValid())
  1161. MutexID::warnInvalidLock(Analyzer->Handler, MutexExp, Exp, D);
  1162. else if (!locksetContainsAtLeast(Mutex, LK))
  1163. Analyzer->Handler.handleMutexNotHeld(D, POK, Mutex.getName(), LK,
  1164. Exp->getExprLoc());
  1165. }
  1166. /// \brief This method identifies variable dereferences and checks pt_guarded_by
  1167. /// and pt_guarded_var annotations. Note that we only check these annotations
  1168. /// at the time a pointer is dereferenced.
  1169. /// FIXME: We need to check for other types of pointer dereferences
  1170. /// (e.g. [], ->) and deal with them here.
  1171. /// \param Exp An expression that has been read or written.
  1172. void BuildLockset::checkDereference(Expr *Exp, AccessKind AK) {
  1173. UnaryOperator *UO = dyn_cast<UnaryOperator>(Exp);
  1174. if (!UO || UO->getOpcode() != clang::UO_Deref)
  1175. return;
  1176. Exp = UO->getSubExpr()->IgnoreParenCasts();
  1177. const ValueDecl *D = getValueDecl(Exp);
  1178. if(!D || !D->hasAttrs())
  1179. return;
  1180. if (D->getAttr<PtGuardedVarAttr>() && LSet.isEmpty())
  1181. Analyzer->Handler.handleNoMutexHeld(D, POK_VarDereference, AK,
  1182. Exp->getExprLoc());
  1183. const AttrVec &ArgAttrs = D->getAttrs();
  1184. for(unsigned i = 0, Size = ArgAttrs.size(); i < Size; ++i)
  1185. if (PtGuardedByAttr *PGBAttr = dyn_cast<PtGuardedByAttr>(ArgAttrs[i]))
  1186. warnIfMutexNotHeld(D, Exp, AK, PGBAttr->getArg(), POK_VarDereference);
  1187. }
  1188. /// \brief Checks guarded_by and guarded_var attributes.
  1189. /// Whenever we identify an access (read or write) of a DeclRefExpr or
  1190. /// MemberExpr, we need to check whether there are any guarded_by or
  1191. /// guarded_var attributes, and make sure we hold the appropriate mutexes.
  1192. void BuildLockset::checkAccess(Expr *Exp, AccessKind AK) {
  1193. const ValueDecl *D = getValueDecl(Exp);
  1194. if(!D || !D->hasAttrs())
  1195. return;
  1196. if (D->getAttr<GuardedVarAttr>() && LSet.isEmpty())
  1197. Analyzer->Handler.handleNoMutexHeld(D, POK_VarAccess, AK,
  1198. Exp->getExprLoc());
  1199. const AttrVec &ArgAttrs = D->getAttrs();
  1200. for(unsigned i = 0, Size = ArgAttrs.size(); i < Size; ++i)
  1201. if (GuardedByAttr *GBAttr = dyn_cast<GuardedByAttr>(ArgAttrs[i]))
  1202. warnIfMutexNotHeld(D, Exp, AK, GBAttr->getArg(), POK_VarAccess);
  1203. }
  1204. /// \brief Process a function call, method call, constructor call,
  1205. /// or destructor call. This involves looking at the attributes on the
  1206. /// corresponding function/method/constructor/destructor, issuing warnings,
  1207. /// and updating the locksets accordingly.
  1208. ///
  1209. /// FIXME: For classes annotated with one of the guarded annotations, we need
  1210. /// to treat const method calls as reads and non-const method calls as writes,
  1211. /// and check that the appropriate locks are held. Non-const method calls with
  1212. /// the same signature as const method calls can be also treated as reads.
  1213. ///
  1214. /// FIXME: We need to also visit CallExprs to catch/check global functions.
  1215. ///
  1216. /// FIXME: Do not flag an error for member variables accessed in constructors/
  1217. /// destructors
  1218. void BuildLockset::handleCall(Expr *Exp, NamedDecl *D, VarDecl *VD) {
  1219. AttrVec &ArgAttrs = D->getAttrs();
  1220. for(unsigned i = 0; i < ArgAttrs.size(); ++i) {
  1221. Attr *Attr = ArgAttrs[i];
  1222. switch (Attr->getKind()) {
  1223. // When we encounter an exclusive lock function, we need to add the lock
  1224. // to our lockset with kind exclusive.
  1225. case attr::ExclusiveLockFunction: {
  1226. ExclusiveLockFunctionAttr *A = cast<ExclusiveLockFunctionAttr>(Attr);
  1227. LSet = Analyzer->addLocksToSet(LSet, LK_Exclusive, A, Exp, D, VD);
  1228. break;
  1229. }
  1230. // When we encounter a shared lock function, we need to add the lock
  1231. // to our lockset with kind shared.
  1232. case attr::SharedLockFunction: {
  1233. SharedLockFunctionAttr *A = cast<SharedLockFunctionAttr>(Attr);
  1234. LSet = Analyzer->addLocksToSet(LSet, LK_Shared, A, Exp, D, VD);
  1235. break;
  1236. }
  1237. // When we encounter an unlock function, we need to remove unlocked
  1238. // mutexes from the lockset, and flag a warning if they are not there.
  1239. case attr::UnlockFunction: {
  1240. UnlockFunctionAttr *UFAttr = cast<UnlockFunctionAttr>(Attr);
  1241. LSet = Analyzer->removeLocksFromSet(LSet, UFAttr, Exp, D);
  1242. break;
  1243. }
  1244. case attr::ExclusiveLocksRequired: {
  1245. ExclusiveLocksRequiredAttr *ELRAttr =
  1246. cast<ExclusiveLocksRequiredAttr>(Attr);
  1247. for (ExclusiveLocksRequiredAttr::args_iterator
  1248. I = ELRAttr->args_begin(), E = ELRAttr->args_end(); I != E; ++I)
  1249. warnIfMutexNotHeld(D, Exp, AK_Written, *I, POK_FunctionCall);
  1250. break;
  1251. }
  1252. case attr::SharedLocksRequired: {
  1253. SharedLocksRequiredAttr *SLRAttr = cast<SharedLocksRequiredAttr>(Attr);
  1254. for (SharedLocksRequiredAttr::args_iterator I = SLRAttr->args_begin(),
  1255. E = SLRAttr->args_end(); I != E; ++I)
  1256. warnIfMutexNotHeld(D, Exp, AK_Read, *I, POK_FunctionCall);
  1257. break;
  1258. }
  1259. case attr::LocksExcluded: {
  1260. LocksExcludedAttr *LEAttr = cast<LocksExcludedAttr>(Attr);
  1261. for (LocksExcludedAttr::args_iterator I = LEAttr->args_begin(),
  1262. E = LEAttr->args_end(); I != E; ++I) {
  1263. MutexID Mutex(*I, Exp, D);
  1264. if (!Mutex.isValid())
  1265. MutexID::warnInvalidLock(Analyzer->Handler, *I, Exp, D);
  1266. else if (locksetContains(Mutex))
  1267. Analyzer->Handler.handleFunExcludesLock(D->getName(),
  1268. Mutex.getName(),
  1269. Exp->getExprLoc());
  1270. }
  1271. break;
  1272. }
  1273. // Ignore other (non thread-safety) attributes
  1274. default:
  1275. break;
  1276. }
  1277. }
  1278. }
  1279. /// \brief For unary operations which read and write a variable, we need to
  1280. /// check whether we hold any required mutexes. Reads are checked in
  1281. /// VisitCastExpr.
  1282. void BuildLockset::VisitUnaryOperator(UnaryOperator *UO) {
  1283. switch (UO->getOpcode()) {
  1284. case clang::UO_PostDec:
  1285. case clang::UO_PostInc:
  1286. case clang::UO_PreDec:
  1287. case clang::UO_PreInc: {
  1288. Expr *SubExp = UO->getSubExpr()->IgnoreParenCasts();
  1289. checkAccess(SubExp, AK_Written);
  1290. checkDereference(SubExp, AK_Written);
  1291. break;
  1292. }
  1293. default:
  1294. break;
  1295. }
  1296. }
  1297. /// For binary operations which assign to a variable (writes), we need to check
  1298. /// whether we hold any required mutexes.
  1299. /// FIXME: Deal with non-primitive types.
  1300. void BuildLockset::VisitBinaryOperator(BinaryOperator *BO) {
  1301. if (!BO->isAssignmentOp())
  1302. return;
  1303. // adjust the context
  1304. LVarCtx = Analyzer->LocalVarMap.getNextContext(CtxIndex, BO, LVarCtx);
  1305. Expr *LHSExp = BO->getLHS()->IgnoreParenCasts();
  1306. checkAccess(LHSExp, AK_Written);
  1307. checkDereference(LHSExp, AK_Written);
  1308. }
  1309. /// Whenever we do an LValue to Rvalue cast, we are reading a variable and
  1310. /// need to ensure we hold any required mutexes.
  1311. /// FIXME: Deal with non-primitive types.
  1312. void BuildLockset::VisitCastExpr(CastExpr *CE) {
  1313. if (CE->getCastKind() != CK_LValueToRValue)
  1314. return;
  1315. Expr *SubExp = CE->getSubExpr()->IgnoreParenCasts();
  1316. checkAccess(SubExp, AK_Read);
  1317. checkDereference(SubExp, AK_Read);
  1318. }
  1319. void BuildLockset::VisitCallExpr(CallExpr *Exp) {
  1320. NamedDecl *D = dyn_cast_or_null<NamedDecl>(Exp->getCalleeDecl());
  1321. if(!D || !D->hasAttrs())
  1322. return;
  1323. handleCall(Exp, D);
  1324. }
  1325. void BuildLockset::VisitCXXConstructExpr(CXXConstructExpr *Exp) {
  1326. // FIXME -- only handles constructors in DeclStmt below.
  1327. }
  1328. void BuildLockset::VisitDeclStmt(DeclStmt *S) {
  1329. // adjust the context
  1330. LVarCtx = Analyzer->LocalVarMap.getNextContext(CtxIndex, S, LVarCtx);
  1331. DeclGroupRef DGrp = S->getDeclGroup();
  1332. for (DeclGroupRef::iterator I = DGrp.begin(), E = DGrp.end(); I != E; ++I) {
  1333. Decl *D = *I;
  1334. if (VarDecl *VD = dyn_cast_or_null<VarDecl>(D)) {
  1335. Expr *E = VD->getInit();
  1336. if (CXXConstructExpr *CE = dyn_cast_or_null<CXXConstructExpr>(E)) {
  1337. NamedDecl *CtorD = dyn_cast_or_null<NamedDecl>(CE->getConstructor());
  1338. if (!CtorD || !CtorD->hasAttrs())
  1339. return;
  1340. handleCall(CE, CtorD, VD);
  1341. }
  1342. }
  1343. }
  1344. }
  1345. /// \brief Compute the intersection of two locksets and issue warnings for any
  1346. /// locks in the symmetric difference.
  1347. ///
  1348. /// This function is used at a merge point in the CFG when comparing the lockset
  1349. /// of each branch being merged. For example, given the following sequence:
  1350. /// A; if () then B; else C; D; we need to check that the lockset after B and C
  1351. /// are the same. In the event of a difference, we use the intersection of these
  1352. /// two locksets at the start of D.
  1353. ///
  1354. /// \param LSet1 The first lockset.
  1355. /// \param LSet2 The second lockset.
  1356. /// \param JoinLoc The location of the join point for error reporting
  1357. /// \param LEK The error message to report.
  1358. Lockset ThreadSafetyAnalyzer::intersectAndWarn(const Lockset &LSet1,
  1359. const Lockset &LSet2,
  1360. SourceLocation JoinLoc,
  1361. LockErrorKind LEK) {
  1362. Lockset Intersection = LSet1;
  1363. for (Lockset::iterator I = LSet2.begin(), E = LSet2.end(); I != E; ++I) {
  1364. const MutexID &LSet2Mutex = I.getKey();
  1365. const LockData &LSet2LockData = I.getData();
  1366. if (const LockData *LD = LSet1.lookup(LSet2Mutex)) {
  1367. if (LD->LKind != LSet2LockData.LKind) {
  1368. Handler.handleExclusiveAndShared(LSet2Mutex.getName(),
  1369. LSet2LockData.AcquireLoc,
  1370. LD->AcquireLoc);
  1371. if (LD->LKind != LK_Exclusive)
  1372. Intersection = LocksetFactory.add(Intersection, LSet2Mutex,
  1373. LSet2LockData);
  1374. }
  1375. } else {
  1376. if (!LSet2LockData.Managed)
  1377. Handler.handleMutexHeldEndOfScope(LSet2Mutex.getName(),
  1378. LSet2LockData.AcquireLoc,
  1379. JoinLoc, LEK);
  1380. }
  1381. }
  1382. for (Lockset::iterator I = LSet1.begin(), E = LSet1.end(); I != E; ++I) {
  1383. if (!LSet2.contains(I.getKey())) {
  1384. const MutexID &Mutex = I.getKey();
  1385. const LockData &MissingLock = I.getData();
  1386. if (!MissingLock.Managed)
  1387. Handler.handleMutexHeldEndOfScope(Mutex.getName(),
  1388. MissingLock.AcquireLoc,
  1389. JoinLoc, LEK);
  1390. Intersection = LocksetFactory.remove(Intersection, Mutex);
  1391. }
  1392. }
  1393. return Intersection;
  1394. }
  1395. /// \brief Check a function's CFG for thread-safety violations.
  1396. ///
  1397. /// We traverse the blocks in the CFG, compute the set of mutexes that are held
  1398. /// at the end of each block, and issue warnings for thread safety violations.
  1399. /// Each block in the CFG is traversed exactly once.
  1400. void ThreadSafetyAnalyzer::runAnalysis(AnalysisDeclContext &AC) {
  1401. CFG *CFGraph = AC.getCFG();
  1402. if (!CFGraph) return;
  1403. const NamedDecl *D = dyn_cast_or_null<NamedDecl>(AC.getDecl());
  1404. // AC.dumpCFG(true);
  1405. if (!D)
  1406. return; // Ignore anonymous functions for now.
  1407. if (D->getAttr<NoThreadSafetyAnalysisAttr>())
  1408. return;
  1409. // FIXME: Do something a bit more intelligent inside constructor and
  1410. // destructor code. Constructors and destructors must assume unique access
  1411. // to 'this', so checks on member variable access is disabled, but we should
  1412. // still enable checks on other objects.
  1413. if (isa<CXXConstructorDecl>(D))
  1414. return; // Don't check inside constructors.
  1415. if (isa<CXXDestructorDecl>(D))
  1416. return; // Don't check inside destructors.
  1417. BlockInfo.resize(CFGraph->getNumBlockIDs(),
  1418. CFGBlockInfo::getEmptyBlockInfo(LocksetFactory, LocalVarMap));
  1419. // We need to explore the CFG via a "topological" ordering.
  1420. // That way, we will be guaranteed to have information about required
  1421. // predecessor locksets when exploring a new block.
  1422. PostOrderCFGView *SortedGraph = AC.getAnalysis<PostOrderCFGView>();
  1423. PostOrderCFGView::CFGBlockSet VisitedBlocks(CFGraph);
  1424. // Compute SSA names for local variables
  1425. LocalVarMap.traverseCFG(CFGraph, SortedGraph, BlockInfo);
  1426. // Fill in source locations for all CFGBlocks.
  1427. findBlockLocations(CFGraph, SortedGraph, BlockInfo);
  1428. // Add locks from exclusive_locks_required and shared_locks_required
  1429. // to initial lockset. Also turn off checking for lock and unlock functions.
  1430. // FIXME: is there a more intelligent way to check lock/unlock functions?
  1431. if (!SortedGraph->empty() && D->hasAttrs()) {
  1432. const CFGBlock *FirstBlock = *SortedGraph->begin();
  1433. Lockset &InitialLockset = BlockInfo[FirstBlock->getBlockID()].EntrySet;
  1434. const AttrVec &ArgAttrs = D->getAttrs();
  1435. for (unsigned i = 0; i < ArgAttrs.size(); ++i) {
  1436. Attr *Attr = ArgAttrs[i];
  1437. SourceLocation AttrLoc = Attr->getLocation();
  1438. if (SharedLocksRequiredAttr *SLRAttr
  1439. = dyn_cast<SharedLocksRequiredAttr>(Attr)) {
  1440. for (SharedLocksRequiredAttr::args_iterator
  1441. SLRIter = SLRAttr->args_begin(),
  1442. SLREnd = SLRAttr->args_end(); SLRIter != SLREnd; ++SLRIter)
  1443. InitialLockset = addLock(InitialLockset, *SLRIter, D,
  1444. LockData(AttrLoc, LK_Shared), false);
  1445. } else if (ExclusiveLocksRequiredAttr *ELRAttr
  1446. = dyn_cast<ExclusiveLocksRequiredAttr>(Attr)) {
  1447. for (ExclusiveLocksRequiredAttr::args_iterator
  1448. ELRIter = ELRAttr->args_begin(),
  1449. ELREnd = ELRAttr->args_end(); ELRIter != ELREnd; ++ELRIter)
  1450. InitialLockset = addLock(InitialLockset, *ELRIter, D,
  1451. LockData(AttrLoc, LK_Exclusive), false);
  1452. } else if (isa<UnlockFunctionAttr>(Attr)) {
  1453. // Don't try to check unlock functions for now
  1454. return;
  1455. } else if (isa<ExclusiveLockFunctionAttr>(Attr)) {
  1456. // Don't try to check lock functions for now
  1457. return;
  1458. } else if (isa<SharedLockFunctionAttr>(Attr)) {
  1459. // Don't try to check lock functions for now
  1460. return;
  1461. } else if (isa<ExclusiveTrylockFunctionAttr>(Attr)) {
  1462. // Don't try to check trylock functions for now
  1463. return;
  1464. } else if (isa<SharedTrylockFunctionAttr>(Attr)) {
  1465. // Don't try to check trylock functions for now
  1466. return;
  1467. }
  1468. }
  1469. }
  1470. for (PostOrderCFGView::iterator I = SortedGraph->begin(),
  1471. E = SortedGraph->end(); I!= E; ++I) {
  1472. const CFGBlock *CurrBlock = *I;
  1473. int CurrBlockID = CurrBlock->getBlockID();
  1474. CFGBlockInfo *CurrBlockInfo = &BlockInfo[CurrBlockID];
  1475. // Use the default initial lockset in case there are no predecessors.
  1476. VisitedBlocks.insert(CurrBlock);
  1477. // Iterate through the predecessor blocks and warn if the lockset for all
  1478. // predecessors is not the same. We take the entry lockset of the current
  1479. // block to be the intersection of all previous locksets.
  1480. // FIXME: By keeping the intersection, we may output more errors in future
  1481. // for a lock which is not in the intersection, but was in the union. We
  1482. // may want to also keep the union in future. As an example, let's say
  1483. // the intersection contains Mutex L, and the union contains L and M.
  1484. // Later we unlock M. At this point, we would output an error because we
  1485. // never locked M; although the real error is probably that we forgot to
  1486. // lock M on all code paths. Conversely, let's say that later we lock M.
  1487. // In this case, we should compare against the intersection instead of the
  1488. // union because the real error is probably that we forgot to unlock M on
  1489. // all code paths.
  1490. bool LocksetInitialized = false;
  1491. llvm::SmallVector<CFGBlock*, 8> SpecialBlocks;
  1492. for (CFGBlock::const_pred_iterator PI = CurrBlock->pred_begin(),
  1493. PE = CurrBlock->pred_end(); PI != PE; ++PI) {
  1494. // if *PI -> CurrBlock is a back edge
  1495. if (*PI == 0 || !VisitedBlocks.alreadySet(*PI))
  1496. continue;
  1497. // Ignore edges from blocks that can't return.
  1498. if ((*PI)->hasNoReturnElement())
  1499. continue;
  1500. // If the previous block ended in a 'continue' or 'break' statement, then
  1501. // a difference in locksets is probably due to a bug in that block, rather
  1502. // than in some other predecessor. In that case, keep the other
  1503. // predecessor's lockset.
  1504. if (const Stmt *Terminator = (*PI)->getTerminator()) {
  1505. if (isa<ContinueStmt>(Terminator) || isa<BreakStmt>(Terminator)) {
  1506. SpecialBlocks.push_back(*PI);
  1507. continue;
  1508. }
  1509. }
  1510. int PrevBlockID = (*PI)->getBlockID();
  1511. CFGBlockInfo *PrevBlockInfo = &BlockInfo[PrevBlockID];
  1512. Lockset PrevLockset =
  1513. getEdgeLockset(PrevBlockInfo->ExitSet, *PI, CurrBlock);
  1514. if (!LocksetInitialized) {
  1515. CurrBlockInfo->EntrySet = PrevLockset;
  1516. LocksetInitialized = true;
  1517. } else {
  1518. CurrBlockInfo->EntrySet =
  1519. intersectAndWarn(CurrBlockInfo->EntrySet, PrevLockset,
  1520. CurrBlockInfo->EntryLoc,
  1521. LEK_LockedSomePredecessors);
  1522. }
  1523. }
  1524. // Process continue and break blocks. Assume that the lockset for the
  1525. // resulting block is unaffected by any discrepancies in them.
  1526. for (unsigned SpecialI = 0, SpecialN = SpecialBlocks.size();
  1527. SpecialI < SpecialN; ++SpecialI) {
  1528. CFGBlock *PrevBlock = SpecialBlocks[SpecialI];
  1529. int PrevBlockID = PrevBlock->getBlockID();
  1530. CFGBlockInfo *PrevBlockInfo = &BlockInfo[PrevBlockID];
  1531. if (!LocksetInitialized) {
  1532. CurrBlockInfo->EntrySet = PrevBlockInfo->ExitSet;
  1533. LocksetInitialized = true;
  1534. } else {
  1535. // Determine whether this edge is a loop terminator for diagnostic
  1536. // purposes. FIXME: A 'break' statement might be a loop terminator, but
  1537. // it might also be part of a switch. Also, a subsequent destructor
  1538. // might add to the lockset, in which case the real issue might be a
  1539. // double lock on the other path.
  1540. const Stmt *Terminator = PrevBlock->getTerminator();
  1541. bool IsLoop = Terminator && isa<ContinueStmt>(Terminator);
  1542. Lockset PrevLockset =
  1543. getEdgeLockset(PrevBlockInfo->ExitSet, PrevBlock, CurrBlock);
  1544. // Do not update EntrySet.
  1545. intersectAndWarn(CurrBlockInfo->EntrySet, PrevLockset,
  1546. PrevBlockInfo->ExitLoc,
  1547. IsLoop ? LEK_LockedSomeLoopIterations
  1548. : LEK_LockedSomePredecessors);
  1549. }
  1550. }
  1551. BuildLockset LocksetBuilder(this, *CurrBlockInfo);
  1552. // Visit all the statements in the basic block.
  1553. for (CFGBlock::const_iterator BI = CurrBlock->begin(),
  1554. BE = CurrBlock->end(); BI != BE; ++BI) {
  1555. switch (BI->getKind()) {
  1556. case CFGElement::Statement: {
  1557. const CFGStmt *CS = cast<CFGStmt>(&*BI);
  1558. LocksetBuilder.Visit(const_cast<Stmt*>(CS->getStmt()));
  1559. break;
  1560. }
  1561. // Ignore BaseDtor, MemberDtor, and TemporaryDtor for now.
  1562. case CFGElement::AutomaticObjectDtor: {
  1563. const CFGAutomaticObjDtor *AD = cast<CFGAutomaticObjDtor>(&*BI);
  1564. CXXDestructorDecl *DD = const_cast<CXXDestructorDecl*>(
  1565. AD->getDestructorDecl(AC.getASTContext()));
  1566. if (!DD->hasAttrs())
  1567. break;
  1568. // Create a dummy expression,
  1569. VarDecl *VD = const_cast<VarDecl*>(AD->getVarDecl());
  1570. DeclRefExpr DRE(VD, false, VD->getType(), VK_LValue,
  1571. AD->getTriggerStmt()->getLocEnd());
  1572. LocksetBuilder.handleCall(&DRE, DD);
  1573. break;
  1574. }
  1575. default:
  1576. break;
  1577. }
  1578. }
  1579. CurrBlockInfo->ExitSet = LocksetBuilder.LSet;
  1580. // For every back edge from CurrBlock (the end of the loop) to another block
  1581. // (FirstLoopBlock) we need to check that the Lockset of Block is equal to
  1582. // the one held at the beginning of FirstLoopBlock. We can look up the
  1583. // Lockset held at the beginning of FirstLoopBlock in the EntryLockSets map.
  1584. for (CFGBlock::const_succ_iterator SI = CurrBlock->succ_begin(),
  1585. SE = CurrBlock->succ_end(); SI != SE; ++SI) {
  1586. // if CurrBlock -> *SI is *not* a back edge
  1587. if (*SI == 0 || !VisitedBlocks.alreadySet(*SI))
  1588. continue;
  1589. CFGBlock *FirstLoopBlock = *SI;
  1590. CFGBlockInfo *PreLoop = &BlockInfo[FirstLoopBlock->getBlockID()];
  1591. CFGBlockInfo *LoopEnd = &BlockInfo[CurrBlockID];
  1592. intersectAndWarn(LoopEnd->ExitSet, PreLoop->EntrySet,
  1593. PreLoop->EntryLoc,
  1594. LEK_LockedSomeLoopIterations);
  1595. }
  1596. }
  1597. CFGBlockInfo *Initial = &BlockInfo[CFGraph->getEntry().getBlockID()];
  1598. CFGBlockInfo *Final = &BlockInfo[CFGraph->getExit().getBlockID()];
  1599. // FIXME: Should we call this function for all blocks which exit the function?
  1600. intersectAndWarn(Initial->EntrySet, Final->ExitSet,
  1601. Final->ExitLoc,
  1602. LEK_LockedAtEndOfFunction);
  1603. }
  1604. } // end anonymous namespace
  1605. namespace clang {
  1606. namespace thread_safety {
  1607. /// \brief Check a function's CFG for thread-safety violations.
  1608. ///
  1609. /// We traverse the blocks in the CFG, compute the set of mutexes that are held
  1610. /// at the end of each block, and issue warnings for thread safety violations.
  1611. /// Each block in the CFG is traversed exactly once.
  1612. void runThreadSafetyAnalysis(AnalysisDeclContext &AC,
  1613. ThreadSafetyHandler &Handler) {
  1614. ThreadSafetyAnalyzer Analyzer(Handler);
  1615. Analyzer.runAnalysis(AC);
  1616. }
  1617. /// \brief Helper function that returns a LockKind required for the given level
  1618. /// of access.
  1619. LockKind getLockKindFromAccessKind(AccessKind AK) {
  1620. switch (AK) {
  1621. case AK_Read :
  1622. return LK_Shared;
  1623. case AK_Written :
  1624. return LK_Exclusive;
  1625. }
  1626. llvm_unreachable("Unknown AccessKind");
  1627. }
  1628. }} // end namespace clang::thread_safety