LEFT | RIGHT |
1 //===- ThreadSafety.cpp ----------------------------------------*- C++ --*-===// | 1 //===- ThreadSafety.cpp ----------------------------------------*- C++ --*-===// |
2 // | 2 // |
3 // The LLVM Compiler Infrastructure | 3 // The LLVM Compiler Infrastructure |
4 // | 4 // |
5 // This file is distributed under the University of Illinois Open Source | 5 // This file is distributed under the University of Illinois Open Source |
6 // License. See LICENSE.TXT for details. | 6 // License. See LICENSE.TXT for details. |
7 // | 7 // |
8 //===----------------------------------------------------------------------===// | 8 //===----------------------------------------------------------------------===// |
9 // | 9 // |
10 // A intra-procedural analysis for thread safety (e.g. deadlocks and race | 10 // A intra-procedural analysis for thread safety (e.g. deadlocks and race |
(...skipping 112 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
123 /// is built from an Expr* (i.e. calling a lock function). | 123 /// is built from an Expr* (i.e. calling a lock function). |
124 /// | 124 /// |
125 /// Thread-safety analysis works by comparing lock expressions. Within the | 125 /// Thread-safety analysis works by comparing lock expressions. Within the |
126 /// body of a function, an expression such as "x->foo->bar.mu" will resolve to | 126 /// body of a function, an expression such as "x->foo->bar.mu" will resolve to |
127 /// a particular mutex object at run-time. Subsequent occurrences of the same | 127 /// a particular mutex object at run-time. Subsequent occurrences of the same |
128 /// expression (where "same" means syntactic equality) will refer to the same | 128 /// expression (where "same" means syntactic equality) will refer to the same |
129 /// run-time object if three conditions hold: | 129 /// run-time object if three conditions hold: |
130 /// (1) Local variables in the expression, such as "x" have not changed. | 130 /// (1) Local variables in the expression, such as "x" have not changed. |
131 /// (2) Values on the heap that affect the expression have not changed. | 131 /// (2) Values on the heap that affect the expression have not changed. |
132 /// (3) The expression involves only pure function calls. | 132 /// (3) The expression involves only pure function calls. |
| 133 /// |
133 /// The current implementation assumes, but does not verify, that multiple uses | 134 /// The current implementation assumes, but does not verify, that multiple uses |
134 /// of the same lock expression satisfies these criteria. | 135 /// of the same lock expression satisfies these criteria. |
135 /// | 136 /// |
136 /// Clang introduces an additional wrinkle, which is that it is difficult to | 137 /// Clang introduces an additional wrinkle, which is that it is difficult to |
137 /// derive canonical expressions, or compare expressions directly for equality. | 138 /// derive canonical expressions, or compare expressions directly for equality. |
138 /// Thus, we identify a mutex not by an Expr, but by the set of named | 139 /// Thus, we identify a mutex not by an Expr, but by the set of named |
139 /// declarations that are referenced by the Expr. In other words, | 140 /// declarations that are referenced by the Expr. In other words, |
140 /// x->foo->bar.mu will be a four element vector with the Decls for | 141 /// x->foo->bar.mu will be a four element vector with the Decls for |
141 /// mu, bar, and foo, and x. The vector will uniquely identify the expression | 142 /// mu, bar, and foo, and x. The vector will uniquely identify the expression |
142 /// for all practical purposes. | 143 /// for all practical purposes. |
143 /// | 144 /// |
144 /// Note we will need to perform substitution on "this" and function parameter | 145 /// Note we will need to perform substitution on "this" and function parameter |
145 /// names when constructing a lock expression. | 146 /// names when constructing a lock expression. |
146 /// | 147 /// |
147 /// For example: | 148 /// For example: |
148 /// class C { Mutex Mu; void lock() EXCLUSIVE_LOCK_FUNCTION(this->Mu); }; | 149 /// class C { Mutex Mu; void lock() EXCLUSIVE_LOCK_FUNCTION(this->Mu); }; |
149 /// void myFunc(C *X) { ... X->lock() ... } | 150 /// void myFunc(C *X) { ... X->lock() ... } |
150 /// The original expression for the mutex acquired by myFunc is "this->Mu", but | 151 /// The original expression for the mutex acquired by myFunc is "this->Mu", but |
151 /// "X" is substituted for "this" so we get X->Mu(); | 152 /// "X" is substituted for "this" so we get X->Mu(); |
152 /// | 153 /// |
153 /// For another example: | 154 /// For another example: |
154 /// foo(MyList *L) EXCLUSIVE_LOCKS_REQUIRED(L->Mu) { ... } | 155 /// foo(MyList *L) EXCLUSIVE_LOCKS_REQUIRED(L->Mu) { ... } |
155 /// MyList *MyL; | 156 /// MyList *MyL; |
156 /// foo(MyL); // requires lock MyL->Mu to be held | 157 /// foo(MyL); // requires lock MyL->Mu to be held |
157 class MutexID { | 158 class MutexID { |
158 SmallVector<NamedDecl*, 2> DeclSeq; | 159 SmallVector<NamedDecl*, 2> DeclSeq; |
159 | 160 |
160 /// Build a Decl sequence representing the lock from the given expression. | 161 /// Build a Decl sequence representing the lock from the given expression. |
161 /// Recursive function that bottoms out when the final DeclRefExpr is reached. | 162 /// Recursive function that terminates on DeclRefExpr. |
| 163 /// Note: this function merely creates a MutexID; it does not check to |
| 164 /// ensure that the original expression is a valid mutex expression. |
162 void buildMutexID(Expr *Exp, Expr *Parent, int NumArgs, | 165 void buildMutexID(Expr *Exp, Expr *Parent, int NumArgs, |
163 const NamedDecl **FunArgDecls, Expr **FunArgs) { | 166 const NamedDecl **FunArgDecls, Expr **FunArgs) { |
164 if (!Exp) { | 167 if (!Exp) { |
165 DeclSeq.clear(); | 168 DeclSeq.clear(); |
166 return; | 169 return; |
167 } | 170 } |
168 | 171 |
169 if (DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(Exp)) { | 172 if (DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(Exp)) { |
170 if (FunArgDecls) { | 173 if (FunArgDecls) { |
171 // Substitute call arguments for references to function parameters | 174 // Substitute call arguments for references to function parameters |
172 for (int i = 0; i < NumArgs; ++i) { | 175 for (int i = 0; i < NumArgs; ++i) { |
173 if (DRE->getDecl() == FunArgDecls[i]) { | 176 if (DRE->getDecl() == FunArgDecls[i]) { |
174 buildMutexID(FunArgs[i], 0, 0, 0, 0); | 177 buildMutexID(FunArgs[i], 0, 0, 0, 0); |
175 return; | 178 return; |
176 } | 179 } |
177 } | 180 } |
178 } | 181 } |
179 NamedDecl *ND = cast<NamedDecl>(DRE->getDecl()->getCanonicalDecl()); | 182 NamedDecl *ND = cast<NamedDecl>(DRE->getDecl()->getCanonicalDecl()); |
180 DeclSeq.push_back(ND); | 183 DeclSeq.push_back(ND); |
181 } else if (MemberExpr *ME = dyn_cast<MemberExpr>(Exp)) { | 184 } else if (MemberExpr *ME = dyn_cast<MemberExpr>(Exp)) { |
182 NamedDecl *ND = ME->getMemberDecl(); | 185 NamedDecl *ND = ME->getMemberDecl(); |
183 DeclSeq.push_back(ND); | 186 DeclSeq.push_back(ND); |
184 buildMutexID(ME->getBase(), Parent, NumArgs, FunArgDecls, FunArgs); | 187 buildMutexID(ME->getBase(), Parent, NumArgs, FunArgDecls, FunArgs); |
185 } else if (isa<CXXThisExpr>(Exp)) { | 188 } else if (isa<CXXThisExpr>(Exp)) { |
186 if (Parent) | 189 if (Parent) |
187 buildMutexID(Parent, 0, 0, 0, 0); | 190 buildMutexID(Parent, 0, 0, 0, 0); |
188 else | 191 else |
189 return; // mutexID is still valid in this case | 192 return; // mutexID is still valid in this case |
190 } else if (UnaryOperator *UOE = dyn_cast<UnaryOperator>(Exp)) { | 193 } else if (UnaryOperator *UOE = dyn_cast<UnaryOperator>(Exp)) |
191 buildMutexID(UOE->getSubExpr(), Parent, NumArgs, FunArgDecls, FunArgs); | 194 buildMutexID(UOE->getSubExpr(), Parent, NumArgs, FunArgDecls, FunArgs); |
192 } else if (CastExpr *CE = dyn_cast<CastExpr>(Exp)) { | 195 else if (CastExpr *CE = dyn_cast<CastExpr>(Exp)) |
193 buildMutexID(CE->getSubExpr(), Parent, NumArgs, FunArgDecls, FunArgs); | 196 buildMutexID(CE->getSubExpr(), Parent, NumArgs, FunArgDecls, FunArgs); |
194 } else { | 197 else |
195 DeclSeq.clear(); // Mark as invalid lock expression. | 198 DeclSeq.clear(); // Mark as invalid lock expression. |
196 } | |
197 } | 199 } |
198 | 200 |
199 /// \brief Construct a MutexID from an expression. | 201 /// \brief Construct a MutexID from an expression. |
200 /// \param MutexExp The original mutex expression within an attribute | 202 /// \param MutexExp The original mutex expression within an attribute |
201 /// \param DeclExp An expression involving the Decl on which the attribute | 203 /// \param DeclExp An expression involving the Decl on which the attribute |
202 /// occurs. | 204 /// occurs. |
203 /// \param D The declaration to which the lock/unlock attribute is attached. | 205 /// \param D The declaration to which the lock/unlock attribute is attached. |
204 void buildMutexIDFromExp(Expr *MutexExp, Expr *DeclExp, const NamedDecl *D) { | 206 void buildMutexIDFromExp(Expr *MutexExp, Expr *DeclExp, const NamedDecl *D) { |
205 Expr *Parent = 0; | 207 Expr *Parent = 0; |
206 unsigned NumArgs = 0; | 208 unsigned NumArgs = 0; |
207 Expr **FunArgs = 0; | 209 Expr **FunArgs = 0; |
208 SmallVector<const NamedDecl*, 8> FunArgDecls; | 210 SmallVector<const NamedDecl*, 8> FunArgDecls; |
209 | 211 |
210 // If we are processing a raw attribute expression... | 212 // If we are processing a raw attribute expression, with no substitutions. |
211 if (DeclExp == 0) { | 213 if (DeclExp == 0) { |
212 buildMutexID(MutexExp, 0, 0, 0, 0); | 214 buildMutexID(MutexExp, 0, 0, 0, 0); |
213 return; | 215 return; |
214 } | 216 } |
215 | 217 |
216 // Get Parent and FunArgs from DeclExp | 218 // Examine DeclExp to find Parent and FunArgs, which are used to substitute |
| 219 // for formal parameters when we call buildMutexID later. |
217 if (MemberExpr *ME = dyn_cast<MemberExpr>(DeclExp)) { | 220 if (MemberExpr *ME = dyn_cast<MemberExpr>(DeclExp)) { |
218 Parent = ME->getBase(); | 221 Parent = ME->getBase(); |
219 } else if (CXXMemberCallExpr *CE = dyn_cast<CXXMemberCallExpr>(DeclExp)) { | 222 } else if (CXXMemberCallExpr *CE = dyn_cast<CXXMemberCallExpr>(DeclExp)) { |
220 Parent = CE->getImplicitObjectArgument(); | 223 Parent = CE->getImplicitObjectArgument(); |
221 NumArgs = CE->getNumArgs(); | 224 NumArgs = CE->getNumArgs(); |
222 FunArgs = CE->getArgs(); | 225 FunArgs = CE->getArgs(); |
223 } else if (CXXConstructExpr *CE = dyn_cast<CXXConstructExpr>(DeclExp)) { | 226 } else if (CXXConstructExpr *CE = dyn_cast<CXXConstructExpr>(DeclExp)) { |
224 Parent = 0; // FIXME -- is there a way to get the parent? | 227 Parent = 0; // FIXME -- get the parent from DeclStmt |
225 NumArgs = CE->getNumArgs(); | 228 NumArgs = CE->getNumArgs(); |
226 FunArgs = CE->getArgs(); | 229 FunArgs = CE->getArgs(); |
227 } | 230 } |
228 | 231 |
229 // If the attribute has no arguments, then assume the argument is "this". | 232 // If the attribute has no arguments, then assume the argument is "this". |
230 if (MutexExp == 0) { | 233 if (MutexExp == 0) { |
231 buildMutexID(Parent, 0, 0, 0, 0); | 234 buildMutexID(Parent, 0, 0, 0, 0); |
232 return; | 235 return; |
233 } | 236 } |
234 | 237 |
(...skipping 182 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
417 /// \brief Add a new lock to the lockset, warning if the lock is already there. | 420 /// \brief Add a new lock to the lockset, warning if the lock is already there. |
418 /// \param LockLoc The source location of the acquire | 421 /// \param LockLoc The source location of the acquire |
419 /// \param LockExp The lock expression corresponding to the lock to be added | 422 /// \param LockExp The lock expression corresponding to the lock to be added |
420 void BuildLockset::addLock(SourceLocation LockLoc, MutexID &Mutex, | 423 void BuildLockset::addLock(SourceLocation LockLoc, MutexID &Mutex, |
421 LockKind LK) { | 424 LockKind LK) { |
422 // FIXME: deal with acquired before/after annotations. We can write a first | 425 // FIXME: deal with acquired before/after annotations. We can write a first |
423 // pass that does the transitive lookup lazily, and refine afterwards. | 426 // pass that does the transitive lookup lazily, and refine afterwards. |
424 LockData NewLock(LockLoc, LK); | 427 LockData NewLock(LockLoc, LK); |
425 | 428 |
426 // FIXME: Don't always warn when we have support for reentrant locks. | 429 // FIXME: Don't always warn when we have support for reentrant locks. |
427 if (locksetContains(Mutex) && LockLoc.isValid()) | 430 if (locksetContains(Mutex)) |
428 Handler.handleDoubleLock(Mutex.getName(), LockLoc); | 431 Handler.handleDoubleLock(Mutex.getName(), LockLoc); |
429 else | 432 else |
430 LSet = LocksetFactory.add(LSet, Mutex, NewLock); | 433 LSet = LocksetFactory.add(LSet, Mutex, NewLock); |
431 } | 434 } |
432 | 435 |
433 /// \brief Remove a lock from the lockset, warning if the lock is not there. | 436 /// \brief Remove a lock from the lockset, warning if the lock is not there. |
434 /// \param LockExp The lock expression corresponding to the lock to be removed | 437 /// \param LockExp The lock expression corresponding to the lock to be removed |
435 /// \param UnlockLoc The source location of the unlock (only used in error msg) | 438 /// \param UnlockLoc The source location of the unlock (only used in error msg) |
436 void BuildLockset::removeLock(SourceLocation UnlockLoc, MutexID &Mutex) { | 439 void BuildLockset::removeLock(SourceLocation UnlockLoc, MutexID &Mutex) { |
437 Lockset NewLSet = LocksetFactory.remove(LSet, Mutex); | 440 Lockset NewLSet = LocksetFactory.remove(LSet, Mutex); |
438 if(NewLSet == LSet && UnlockLoc.isValid()) | 441 if(NewLSet == LSet) |
439 Handler.handleUnmatchedUnlock(Mutex.getName(), UnlockLoc); | 442 Handler.handleUnmatchedUnlock(Mutex.getName(), UnlockLoc); |
440 else | 443 else |
441 LSet = NewLSet; | 444 LSet = NewLSet; |
442 } | 445 } |
443 | 446 |
444 /// \brief This function, parameterized by an attribute type, is used to add a | 447 /// \brief This function, parameterized by an attribute type, is used to add a |
445 /// set of locks specified as attribute arguments to the lockset. | 448 /// set of locks specified as attribute arguments to the lockset. |
446 template <typename AttrType> | 449 template <typename AttrType> |
447 void BuildLockset::addLocksToSet(LockKind LK, AttrType *Attr, | 450 void BuildLockset::addLocksToSet(LockKind LK, AttrType *Attr, |
448 Expr *Exp, NamedDecl* FunDecl) { | 451 Expr *Exp, NamedDecl* FunDecl) { |
(...skipping 13 matching lines...) Expand all Loading... |
462 | 465 |
463 for (iterator_type I=Attr->args_begin(), E=Attr->args_end(); I != E; ++I) { | 466 for (iterator_type I=Attr->args_begin(), E=Attr->args_end(); I != E; ++I) { |
464 MutexID Mutex(*I, Exp, FunDecl); | 467 MutexID Mutex(*I, Exp, FunDecl); |
465 if (!Mutex.isValid()) | 468 if (!Mutex.isValid()) |
466 MutexID::warnInvalidLock(Handler, *I, Exp, FunDecl); | 469 MutexID::warnInvalidLock(Handler, *I, Exp, FunDecl); |
467 else | 470 else |
468 addLock(ExpLocation, Mutex, LK); | 471 addLock(ExpLocation, Mutex, LK); |
469 } | 472 } |
470 } | 473 } |
471 | 474 |
472 /// \brief this function adds a set of locks specified as attribute arguments | 475 /// \brief this function removes a set of locks specified as attribute |
473 /// to the lockset. | 476 /// arguments to the lockset. |
474 void BuildLockset::removeLocksFromSet(UnlockFunctionAttr *Attr, | 477 void BuildLockset::removeLocksFromSet(UnlockFunctionAttr *Attr, |
475 Expr *Exp, NamedDecl* FunDecl) { | 478 Expr *Exp, NamedDecl* FunDecl) { |
476 SourceLocation ExpLocation; | 479 SourceLocation ExpLocation; |
477 if (Exp) ExpLocation = Exp->getExprLoc(); | 480 if (Exp) ExpLocation = Exp->getExprLoc(); |
478 | 481 |
479 if (Attr->args_size() == 0) { | 482 if (Attr->args_size() == 0) { |
480 // The mutex held is the "this" object. | 483 // The mutex held is the "this" object. |
481 MutexID Mu(0, Exp, FunDecl); | 484 MutexID Mu(0, Exp, FunDecl); |
482 if (!Mu.isValid()) | 485 if (!Mu.isValid()) |
483 MutexID::warnInvalidLock(Handler, 0, Exp, FunDecl); | 486 MutexID::warnInvalidLock(Handler, 0, Exp, FunDecl); |
(...skipping 445 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
929 switch (AK) { | 932 switch (AK) { |
930 case AK_Read : | 933 case AK_Read : |
931 return LK_Shared; | 934 return LK_Shared; |
932 case AK_Written : | 935 case AK_Written : |
933 return LK_Exclusive; | 936 return LK_Exclusive; |
934 } | 937 } |
935 llvm_unreachable("Unknown AccessKind"); | 938 llvm_unreachable("Unknown AccessKind"); |
936 } | 939 } |
937 | 940 |
938 }} // end namespace clang::thread_safety | 941 }} // end namespace clang::thread_safety |
LEFT | RIGHT |