Ted Kremenek | 827f93b | 2008-03-06 00:08:09 +0000 | [diff] [blame] | 1 | // CFRefCount.cpp - Transfer functions for tracking simple values -*- 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 | // |
Gabor Greif | 2224fcb | 2008-03-06 10:40:09 +0000 | [diff] [blame] | 10 | // This file defines the methods for CFRefCount, which implements |
Ted Kremenek | 827f93b | 2008-03-06 00:08:09 +0000 | [diff] [blame] | 11 | // a reference count checker for Core Foundation (Mac OS X). |
| 12 | // |
| 13 | //===----------------------------------------------------------------------===// |
| 14 | |
Ted Kremenek | a7338b4 | 2008-03-11 06:39:11 +0000 | [diff] [blame] | 15 | #include "GRSimpleVals.h" |
Ted Kremenek | 827f93b | 2008-03-06 00:08:09 +0000 | [diff] [blame] | 16 | #include "clang/Analysis/PathSensitive/ValueState.h" |
| 17 | #include "clang/Basic/Diagnostic.h" |
| 18 | #include "clang/Analysis/LocalCheckers.h" |
Ted Kremenek | a7338b4 | 2008-03-11 06:39:11 +0000 | [diff] [blame] | 19 | #include "llvm/ADT/DenseMap.h" |
| 20 | #include "llvm/ADT/FoldingSet.h" |
| 21 | #include "llvm/ADT/ImmutableMap.h" |
Ted Kremenek | 827f93b | 2008-03-06 00:08:09 +0000 | [diff] [blame] | 22 | |
| 23 | using namespace clang; |
| 24 | |
Ted Kremenek | a7338b4 | 2008-03-11 06:39:11 +0000 | [diff] [blame] | 25 | namespace { |
| 26 | enum ArgEffect { IncRef, DecRef, DoNothing }; |
| 27 | typedef std::vector<ArgEffect> ArgEffects; |
| 28 | } |
Ted Kremenek | 827f93b | 2008-03-06 00:08:09 +0000 | [diff] [blame] | 29 | |
Ted Kremenek | a7338b4 | 2008-03-11 06:39:11 +0000 | [diff] [blame] | 30 | namespace llvm { |
| 31 | template <> struct FoldingSetTrait<ArgEffects> { |
| 32 | static void Profile(const ArgEffects& X, FoldingSetNodeID ID) { |
| 33 | for (ArgEffects::const_iterator I = X.begin(), E = X.end(); I!= E; ++I) |
| 34 | ID.AddInteger((unsigned) *I); |
| 35 | } |
| 36 | |
| 37 | static void Profile(ArgEffects& X, FoldingSetNodeID ID) { |
| 38 | Profile(X, ID); |
| 39 | } |
| 40 | }; |
| 41 | } // end llvm namespace |
| 42 | |
| 43 | namespace { |
Ted Kremenek | 827f93b | 2008-03-06 00:08:09 +0000 | [diff] [blame] | 44 | |
Ted Kremenek | a7338b4 | 2008-03-11 06:39:11 +0000 | [diff] [blame] | 45 | class RetEffect { |
| 46 | public: |
| 47 | enum Kind { Alias = 0x0, OwnedSymbol = 0x1, NotOwnedSymbol = 0x2 }; |
| 48 | |
| 49 | private: |
| 50 | unsigned Data; |
| 51 | RetEffect(Kind k, unsigned D) { Data = (Data << 2) | (unsigned) k; } |
Ted Kremenek | 827f93b | 2008-03-06 00:08:09 +0000 | [diff] [blame] | 52 | |
Ted Kremenek | a7338b4 | 2008-03-11 06:39:11 +0000 | [diff] [blame] | 53 | public: |
| 54 | |
| 55 | Kind getKind() const { return (Kind) (Data & 0x3); } |
| 56 | |
| 57 | unsigned getValue() const { |
| 58 | assert(getKind() == Alias); |
| 59 | return Data & ~0x3; |
| 60 | } |
Ted Kremenek | 827f93b | 2008-03-06 00:08:09 +0000 | [diff] [blame] | 61 | |
Ted Kremenek | a7338b4 | 2008-03-11 06:39:11 +0000 | [diff] [blame] | 62 | static RetEffect MakeAlias(unsigned Idx) { return RetEffect(Alias, Idx); } |
Ted Kremenek | 827f93b | 2008-03-06 00:08:09 +0000 | [diff] [blame] | 63 | |
Ted Kremenek | a7338b4 | 2008-03-11 06:39:11 +0000 | [diff] [blame] | 64 | static RetEffect MakeOwned() { return RetEffect(OwnedSymbol, 0); } |
Ted Kremenek | 827f93b | 2008-03-06 00:08:09 +0000 | [diff] [blame] | 65 | |
Ted Kremenek | a7338b4 | 2008-03-11 06:39:11 +0000 | [diff] [blame] | 66 | static RetEffect MakeNotOwned() { return RetEffect(NotOwnedSymbol, 0); } |
| 67 | |
| 68 | operator Kind() const { return getKind(); } |
| 69 | |
| 70 | void Profile(llvm::FoldingSetNodeID& ID) const { ID.AddInteger(Data); } |
| 71 | }; |
| 72 | |
| 73 | |
| 74 | class CFRefSummary : public llvm::FoldingSetNode { |
| 75 | ArgEffects* Args; |
| 76 | RetEffect Ret; |
| 77 | public: |
| 78 | |
| 79 | CFRefSummary(ArgEffects* A, RetEffect R) : Args(A), Ret(R) {} |
| 80 | |
| 81 | unsigned getNumArgs() const { return Args->size(); } |
| 82 | |
Ted Kremenek | 0d72157 | 2008-03-11 17:48:22 +0000 | [diff] [blame^] | 83 | ArgEffect getArg(unsigned idx) const { |
| 84 | assert (idx < getNumArgs()); |
| 85 | return (*Args)[idx]; |
| 86 | } |
| 87 | |
Ted Kremenek | a7338b4 | 2008-03-11 06:39:11 +0000 | [diff] [blame] | 88 | typedef ArgEffects::const_iterator arg_iterator; |
| 89 | |
| 90 | arg_iterator begin_args() const { return Args->begin(); } |
| 91 | arg_iterator end_args() const { return Args->end(); } |
| 92 | |
| 93 | static void Profile(llvm::FoldingSetNodeID& ID, ArgEffects* A, RetEffect R) { |
| 94 | ID.AddPointer(A); |
| 95 | ID.Add(R); |
| 96 | } |
| 97 | |
| 98 | void Profile(llvm::FoldingSetNodeID& ID) const { |
| 99 | Profile(ID, Args, Ret); |
| 100 | } |
| 101 | }; |
| 102 | |
| 103 | |
| 104 | class CFRefSummaryManager { |
| 105 | typedef llvm::FoldingSet<llvm::FoldingSetNodeWrapper<ArgEffects> > AESetTy; |
| 106 | typedef llvm::FoldingSet<CFRefSummary> SummarySetTy; |
| 107 | typedef llvm::DenseMap<FunctionDecl*, CFRefSummary*> SummaryMapTy; |
| 108 | |
| 109 | SummarySetTy SummarySet; |
| 110 | SummaryMapTy SummaryMap; |
| 111 | AESetTy AESet; |
| 112 | llvm::BumpPtrAllocator BPAlloc; |
| 113 | |
| 114 | ArgEffects ScratchArgs; |
| 115 | |
| 116 | public: |
| 117 | CFRefSummaryManager() {} |
| 118 | ~CFRefSummaryManager(); |
| 119 | |
| 120 | CFRefSummary* getSummary(FunctionDecl* FD); |
| 121 | }; |
| 122 | |
| 123 | } // end anonymous namespace |
| 124 | |
| 125 | //===----------------------------------------------------------------------===// |
| 126 | // Implementation of checker data structures. |
| 127 | //===----------------------------------------------------------------------===// |
| 128 | |
| 129 | CFRefSummaryManager::~CFRefSummaryManager() { |
| 130 | |
| 131 | // FIXME: The ArgEffects could eventually be allocated from BPAlloc, |
| 132 | // mitigating the need to do explicit cleanup of the |
| 133 | // Argument-Effect summaries. |
| 134 | |
| 135 | for (AESetTy::iterator I = AESet.begin(), E = AESet.end(); I!=E; ++I) |
| 136 | I->getValue().~ArgEffects(); |
Ted Kremenek | 827f93b | 2008-03-06 00:08:09 +0000 | [diff] [blame] | 137 | } |
Ted Kremenek | a7338b4 | 2008-03-11 06:39:11 +0000 | [diff] [blame] | 138 | |
| 139 | CFRefSummary* CFRefSummaryManager::getSummary(FunctionDecl* FD) { |
Ted Kremenek | 827f93b | 2008-03-06 00:08:09 +0000 | [diff] [blame] | 140 | |
Ted Kremenek | a7338b4 | 2008-03-11 06:39:11 +0000 | [diff] [blame] | 141 | { // Look into our cache of summaries to see if we have already computed |
| 142 | // a summary for this FunctionDecl. |
| 143 | |
| 144 | SummaryMapTy::iterator I = SummaryMap.find(FD); |
| 145 | |
| 146 | if (I != SummaryMap.end()) |
| 147 | return I->second; |
| 148 | } |
| 149 | |
| 150 | // |
| 151 | |
| 152 | |
| 153 | return NULL; |
Ted Kremenek | 827f93b | 2008-03-06 00:08:09 +0000 | [diff] [blame] | 154 | } |
| 155 | |
Ted Kremenek | a7338b4 | 2008-03-11 06:39:11 +0000 | [diff] [blame] | 156 | //===----------------------------------------------------------------------===// |
| 157 | // Transfer functions. |
| 158 | //===----------------------------------------------------------------------===// |
| 159 | |
Ted Kremenek | a7338b4 | 2008-03-11 06:39:11 +0000 | [diff] [blame] | 160 | namespace { |
| 161 | |
Ted Kremenek | 0d72157 | 2008-03-11 17:48:22 +0000 | [diff] [blame^] | 162 | class RefVal { |
| 163 | unsigned Data; |
| 164 | |
| 165 | RefVal(unsigned K, unsigned D) : Data((D << 3) | K) { |
| 166 | assert ((K & ~0x5) == 0x0); |
| 167 | } |
| 168 | |
| 169 | RefVal(unsigned K) : Data(K) { |
| 170 | assert ((K & ~0x5) == 0x0); |
| 171 | } |
| 172 | |
| 173 | public: |
| 174 | enum Kind { Owned = 0, AcqOwned = 1, NotOwned = 2, Released = 3, |
| 175 | ErrorUseAfterRelease = 4, ErrorReleaseNotOwned = 5 }; |
| 176 | |
| 177 | |
| 178 | Kind getKind() const { return (Kind) (Data & 0x5); } |
| 179 | |
| 180 | unsigned getCount() const { |
| 181 | assert (getKind() == Owned || getKind() == AcqOwned); |
| 182 | return Data >> 3; |
| 183 | } |
| 184 | |
| 185 | static RefVal makeOwned(unsigned Count) { return RefVal(Owned, Count); } |
| 186 | static RefVal makeAcqOwned(unsigned Count) { return RefVal(AcqOwned, Count); } |
| 187 | static RefVal makeNotOwned() { return RefVal(NotOwned); } |
| 188 | static RefVal makeReleased() { return RefVal(Released); } |
| 189 | static RefVal makeUseAfterRelease() { return RefVal(ErrorUseAfterRelease); } |
| 190 | static RefVal makeReleaseNotOwned() { return RefVal(ErrorReleaseNotOwned); } |
| 191 | |
| 192 | bool operator==(const RefVal& X) const { return Data == X.Data; } |
| 193 | void Profile(llvm::FoldingSetNodeID& ID) const { ID.AddInteger(Data); } |
| 194 | }; |
| 195 | |
| 196 | |
Ted Kremenek | a7338b4 | 2008-03-11 06:39:11 +0000 | [diff] [blame] | 197 | class CFRefCount : public GRSimpleVals { |
Ted Kremenek | 0d72157 | 2008-03-11 17:48:22 +0000 | [diff] [blame^] | 198 | typedef llvm::ImmutableMap<SymbolID, RefVal> RefBindings; |
Ted Kremenek | a7338b4 | 2008-03-11 06:39:11 +0000 | [diff] [blame] | 199 | typedef RefBindings::Factory RefBFactoryTy; |
| 200 | |
| 201 | CFRefSummaryManager Summaries; |
| 202 | RefBFactoryTy RefBFactory; |
| 203 | |
| 204 | static RefBindings GetRefBindings(ValueState& StImpl) { |
| 205 | return RefBindings((RefBindings::TreeTy*) StImpl.CheckerState); |
| 206 | } |
| 207 | |
| 208 | static void SetRefBindings(ValueState& StImpl, RefBindings B) { |
| 209 | StImpl.CheckerState = B.getRoot(); |
| 210 | } |
| 211 | |
| 212 | RefBindings Remove(RefBindings B, SymbolID sym) { |
| 213 | return RefBFactory.Remove(B, sym); |
| 214 | } |
| 215 | |
Ted Kremenek | 0d72157 | 2008-03-11 17:48:22 +0000 | [diff] [blame^] | 216 | RefBindings Update(RefBindings B, SymbolID sym, RefVal V, ArgEffect E, |
| 217 | bool& hasError); |
Ted Kremenek | a7338b4 | 2008-03-11 06:39:11 +0000 | [diff] [blame] | 218 | |
| 219 | public: |
| 220 | CFRefCount() {} |
| 221 | virtual ~CFRefCount() {} |
| 222 | |
| 223 | // Calls. |
| 224 | |
| 225 | virtual void EvalCall(ExplodedNodeSet<ValueState>& Dst, |
| 226 | ValueStateManager& StateMgr, |
| 227 | GRStmtNodeBuilder<ValueState>& Builder, |
| 228 | BasicValueFactory& BasicVals, |
| 229 | CallExpr* CE, LVal L, |
| 230 | ExplodedNode<ValueState>* Pred); |
| 231 | }; |
| 232 | |
| 233 | } // end anonymous namespace |
| 234 | |
Ted Kremenek | 827f93b | 2008-03-06 00:08:09 +0000 | [diff] [blame] | 235 | void CFRefCount::EvalCall(ExplodedNodeSet<ValueState>& Dst, |
| 236 | ValueStateManager& StateMgr, |
| 237 | GRStmtNodeBuilder<ValueState>& Builder, |
Ted Kremenek | 8ad1987 | 2008-03-07 20:13:31 +0000 | [diff] [blame] | 238 | BasicValueFactory& BasicVals, |
Ted Kremenek | 827f93b | 2008-03-06 00:08:09 +0000 | [diff] [blame] | 239 | CallExpr* CE, LVal L, |
| 240 | ExplodedNode<ValueState>* Pred) { |
| 241 | |
Ted Kremenek | a7338b4 | 2008-03-11 06:39:11 +0000 | [diff] [blame] | 242 | // FIXME: Support calls to things other than lval::FuncVal. At the very |
| 243 | // least we should stop tracking ref-state for ref-counted objects passed |
| 244 | // to these functions. |
Ted Kremenek | 827f93b | 2008-03-06 00:08:09 +0000 | [diff] [blame] | 245 | |
Ted Kremenek | a7338b4 | 2008-03-11 06:39:11 +0000 | [diff] [blame] | 246 | assert (isa<lval::FuncVal>(L) && "Not yet implemented."); |
| 247 | |
| 248 | // Get the summary. |
Ted Kremenek | 827f93b | 2008-03-06 00:08:09 +0000 | [diff] [blame] | 249 | |
Ted Kremenek | a7338b4 | 2008-03-11 06:39:11 +0000 | [diff] [blame] | 250 | lval::FuncVal FV = cast<lval::FuncVal>(L); |
| 251 | FunctionDecl* FD = FV.getDecl(); |
| 252 | CFRefSummary* Summ = Summaries.getSummary(FD); |
Ted Kremenek | 827f93b | 2008-03-06 00:08:09 +0000 | [diff] [blame] | 253 | |
Ted Kremenek | a7338b4 | 2008-03-11 06:39:11 +0000 | [diff] [blame] | 254 | // Get the state. |
| 255 | |
| 256 | ValueState* St = Builder.GetState(Pred); |
| 257 | |
| 258 | // Evaluate the effects of the call. |
| 259 | |
| 260 | ValueState StVals = *St; |
Ted Kremenek | 0d72157 | 2008-03-11 17:48:22 +0000 | [diff] [blame^] | 261 | bool hasError = false; |
Ted Kremenek | a7338b4 | 2008-03-11 06:39:11 +0000 | [diff] [blame] | 262 | |
| 263 | if (!Summ) { |
Ted Kremenek | 827f93b | 2008-03-06 00:08:09 +0000 | [diff] [blame] | 264 | |
Ted Kremenek | a7338b4 | 2008-03-11 06:39:11 +0000 | [diff] [blame] | 265 | // This function has no summary. Invalidate all reference-count state |
| 266 | // for arguments passed to this function, and also nuke the values of |
| 267 | // arguments passed-by-reference. |
| 268 | |
| 269 | ValueState StVals = *St; |
| 270 | |
| 271 | for (CallExpr::arg_iterator I = CE->arg_begin(), E = CE->arg_end(); |
| 272 | I != E; ++I) { |
| 273 | |
| 274 | RVal V = StateMgr.GetRVal(St, *I); |
| 275 | |
| 276 | if (isa<lval::SymbolVal>(V)) { |
| 277 | SymbolID Sym = cast<lval::SymbolVal>(V).getSymbol(); |
| 278 | RefBindings B = GetRefBindings(StVals); |
| 279 | SetRefBindings(StVals, Remove(B, Sym)); |
| 280 | } |
| 281 | |
| 282 | if (isa<LVal>(V)) |
| 283 | StateMgr.Unbind(StVals, cast<LVal>(V)); |
| 284 | } |
Ted Kremenek | 827f93b | 2008-03-06 00:08:09 +0000 | [diff] [blame] | 285 | } |
Ted Kremenek | a7338b4 | 2008-03-11 06:39:11 +0000 | [diff] [blame] | 286 | else { |
| 287 | |
| 288 | // This function has a summary. Evaluate the effect of the arguments. |
| 289 | |
| 290 | unsigned idx = 0; |
| 291 | |
| 292 | for (CallExpr::arg_iterator I=CE->arg_begin(), E=CE->arg_end(); |
| 293 | I!=E; ++I, ++idx) { |
| 294 | |
| 295 | RVal V = StateMgr.GetRVal(St, *I); |
| 296 | |
| 297 | if (isa<lval::SymbolVal>(V)) { |
| 298 | SymbolID Sym = cast<lval::SymbolVal>(V).getSymbol(); |
| 299 | RefBindings B = GetRefBindings(StVals); |
Ted Kremenek | 0d72157 | 2008-03-11 17:48:22 +0000 | [diff] [blame^] | 300 | |
| 301 | if (RefBindings::TreeTy* T = B.SlimFind(Sym)) { |
| 302 | B = Update(B, Sym, T->getValue().second, Summ->getArg(idx), hasError); |
| 303 | SetRefBindings(StVals, B); |
| 304 | if (hasError) break; |
| 305 | } |
Ted Kremenek | a7338b4 | 2008-03-11 06:39:11 +0000 | [diff] [blame] | 306 | } |
| 307 | } |
| 308 | } |
| 309 | |
| 310 | St = StateMgr.getPersistentState(StVals); |
Ted Kremenek | 0d72157 | 2008-03-11 17:48:22 +0000 | [diff] [blame^] | 311 | |
| 312 | if (hasError) { |
Ted Kremenek | 827f93b | 2008-03-06 00:08:09 +0000 | [diff] [blame] | 313 | |
Ted Kremenek | 0d72157 | 2008-03-11 17:48:22 +0000 | [diff] [blame^] | 314 | } |
| 315 | |
Ted Kremenek | 827f93b | 2008-03-06 00:08:09 +0000 | [diff] [blame] | 316 | Builder.Nodify(Dst, CE, Pred, St); |
| 317 | } |
Ted Kremenek | a7338b4 | 2008-03-11 06:39:11 +0000 | [diff] [blame] | 318 | |
| 319 | |
| 320 | CFRefCount::RefBindings CFRefCount::Update(RefBindings B, SymbolID sym, |
Ted Kremenek | 0d72157 | 2008-03-11 17:48:22 +0000 | [diff] [blame^] | 321 | RefVal V, ArgEffect E, |
| 322 | bool& hasError) { |
Ted Kremenek | a7338b4 | 2008-03-11 06:39:11 +0000 | [diff] [blame] | 323 | |
Ted Kremenek | 0d72157 | 2008-03-11 17:48:22 +0000 | [diff] [blame^] | 324 | // FIXME: This dispatch can potentially be sped up by unifiying it into |
| 325 | // a single switch statement. Opt for simplicity for now. |
Ted Kremenek | a7338b4 | 2008-03-11 06:39:11 +0000 | [diff] [blame] | 326 | |
Ted Kremenek | 0d72157 | 2008-03-11 17:48:22 +0000 | [diff] [blame^] | 327 | switch (E) { |
| 328 | default: |
| 329 | assert (false && "Unhandled CFRef transition."); |
| 330 | |
| 331 | case DoNothing: |
| 332 | return B; |
| 333 | |
| 334 | case IncRef: |
| 335 | switch (V.getKind()) { |
| 336 | default: |
| 337 | assert(false); |
| 338 | |
| 339 | case RefVal::Owned: |
| 340 | V = RefVal::makeOwned(V.getCount()+1); break; |
| 341 | |
| 342 | case RefVal::AcqOwned: |
| 343 | V = RefVal::makeAcqOwned(V.getCount()+1); |
| 344 | break; |
| 345 | |
| 346 | case RefVal::NotOwned: |
| 347 | V = RefVal::makeAcqOwned(1); |
| 348 | break; |
| 349 | |
| 350 | case RefVal::Released: |
| 351 | hasError = true; |
| 352 | V = RefVal::makeUseAfterRelease(); |
| 353 | break; |
| 354 | } |
| 355 | |
| 356 | case DecRef: |
| 357 | switch (V.getKind()) { |
| 358 | default: |
| 359 | assert (false); |
| 360 | |
| 361 | case RefVal::Owned: { |
| 362 | unsigned Count = V.getCount() - 1; |
| 363 | V = Count ? RefVal::makeOwned(Count) : RefVal::makeReleased(); |
| 364 | break; |
| 365 | } |
| 366 | |
| 367 | case RefVal::AcqOwned: { |
| 368 | unsigned Count = V.getCount() - 1; |
| 369 | V = Count ? RefVal::makeAcqOwned(Count) : RefVal::makeNotOwned(); |
| 370 | break; |
| 371 | } |
| 372 | |
| 373 | case RefVal::NotOwned: |
| 374 | hasError = true; |
| 375 | V = RefVal::makeReleaseNotOwned(); |
| 376 | break; |
| 377 | |
| 378 | case RefVal::Released: |
| 379 | hasError = true; |
| 380 | V = RefVal::makeUseAfterRelease(); |
| 381 | break; |
| 382 | } |
| 383 | } |
| 384 | |
| 385 | return RefBFactory.Add(B, sym, V); |
Ted Kremenek | a7338b4 | 2008-03-11 06:39:11 +0000 | [diff] [blame] | 386 | } |
| 387 | |
| 388 | //===----------------------------------------------------------------------===// |
| 389 | // Driver for the CFRefCount Checker. |
| 390 | //===----------------------------------------------------------------------===// |
| 391 | |
| 392 | namespace clang { |
| 393 | |
| 394 | void CheckCFRefCount(CFG& cfg, FunctionDecl& FD, ASTContext& Ctx, |
| 395 | Diagnostic& Diag) { |
| 396 | |
| 397 | if (Diag.hasErrorOccurred()) |
| 398 | return; |
| 399 | |
| 400 | // FIXME: Refactor some day so this becomes a single function invocation. |
| 401 | |
| 402 | GRCoreEngine<GRExprEngine> Engine(cfg, FD, Ctx); |
| 403 | GRExprEngine* CS = &Engine.getCheckerState(); |
| 404 | CFRefCount TF; |
| 405 | CS->setTransferFunctions(TF); |
| 406 | Engine.ExecuteWorkList(20000); |
| 407 | |
| 408 | } |
| 409 | |
| 410 | } // end clang namespace |