Zhongxing Xu | 589c0f2 | 2009-11-12 08:38:56 +0000 | [diff] [blame] | 1 | //=== MallocChecker.cpp - A malloc/free checker -------------------*- 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 | // This file defines malloc/free checker, which checks for potential memory |
| 11 | // leaks, double free, and use-after-free problems. |
| 12 | // |
| 13 | //===----------------------------------------------------------------------===// |
| 14 | |
Zhongxing Xu | 7b76096 | 2009-11-13 07:25:27 +0000 | [diff] [blame] | 15 | #include "GRExprEngineExperimentalChecks.h" |
Benjamin Kramer | 5e2d2c2 | 2010-03-27 21:19:47 +0000 | [diff] [blame] | 16 | #include "clang/Checker/BugReporter/BugType.h" |
Ted Kremenek | 1309f9a | 2010-01-25 04:41:41 +0000 | [diff] [blame] | 17 | #include "clang/Checker/PathSensitive/CheckerVisitor.h" |
| 18 | #include "clang/Checker/PathSensitive/GRState.h" |
| 19 | #include "clang/Checker/PathSensitive/GRStateTrait.h" |
| 20 | #include "clang/Checker/PathSensitive/SymbolManager.h" |
Zhongxing Xu | 589c0f2 | 2009-11-12 08:38:56 +0000 | [diff] [blame] | 21 | #include "llvm/ADT/ImmutableMap.h" |
| 22 | using namespace clang; |
| 23 | |
| 24 | namespace { |
| 25 | |
Zhongxing Xu | 7fb1464 | 2009-12-11 00:55:44 +0000 | [diff] [blame] | 26 | class RefState { |
Zhongxing Xu | b94b81a | 2009-12-31 06:13:07 +0000 | [diff] [blame] | 27 | enum Kind { AllocateUnchecked, AllocateFailed, Released, Escaped } K; |
Zhongxing Xu | 243fde9 | 2009-11-17 07:54:15 +0000 | [diff] [blame] | 28 | const Stmt *S; |
| 29 | |
Zhongxing Xu | 7fb1464 | 2009-12-11 00:55:44 +0000 | [diff] [blame] | 30 | public: |
Zhongxing Xu | 243fde9 | 2009-11-17 07:54:15 +0000 | [diff] [blame] | 31 | RefState(Kind k, const Stmt *s) : K(k), S(s) {} |
| 32 | |
Zhongxing Xu | b94b81a | 2009-12-31 06:13:07 +0000 | [diff] [blame] | 33 | bool isAllocated() const { return K == AllocateUnchecked; } |
Zhongxing Xu | 243fde9 | 2009-11-17 07:54:15 +0000 | [diff] [blame] | 34 | bool isReleased() const { return K == Released; } |
| 35 | bool isEscaped() const { return K == Escaped; } |
| 36 | |
| 37 | bool operator==(const RefState &X) const { |
| 38 | return K == X.K && S == X.S; |
| 39 | } |
| 40 | |
Zhongxing Xu | b94b81a | 2009-12-31 06:13:07 +0000 | [diff] [blame] | 41 | static RefState getAllocateUnchecked(const Stmt *s) { |
| 42 | return RefState(AllocateUnchecked, s); |
| 43 | } |
| 44 | static RefState getAllocateFailed() { |
| 45 | return RefState(AllocateFailed, 0); |
| 46 | } |
Zhongxing Xu | 243fde9 | 2009-11-17 07:54:15 +0000 | [diff] [blame] | 47 | static RefState getReleased(const Stmt *s) { return RefState(Released, s); } |
| 48 | static RefState getEscaped(const Stmt *s) { return RefState(Escaped, s); } |
| 49 | |
| 50 | void Profile(llvm::FoldingSetNodeID &ID) const { |
| 51 | ID.AddInteger(K); |
| 52 | ID.AddPointer(S); |
| 53 | } |
Zhongxing Xu | 589c0f2 | 2009-11-12 08:38:56 +0000 | [diff] [blame] | 54 | }; |
| 55 | |
Kovarththanan Rajaratnam | ba5fb5a | 2009-11-28 06:07:30 +0000 | [diff] [blame] | 56 | class RegionState {}; |
Zhongxing Xu | 589c0f2 | 2009-11-12 08:38:56 +0000 | [diff] [blame] | 57 | |
Kovarththanan Rajaratnam | ba5fb5a | 2009-11-28 06:07:30 +0000 | [diff] [blame] | 58 | class MallocChecker : public CheckerVisitor<MallocChecker> { |
Zhongxing Xu | 589c0f2 | 2009-11-12 08:38:56 +0000 | [diff] [blame] | 59 | BuiltinBug *BT_DoubleFree; |
Zhongxing Xu | fc7ac8f | 2009-11-13 07:48:11 +0000 | [diff] [blame] | 60 | BuiltinBug *BT_Leak; |
Zhongxing Xu | c802378 | 2010-03-10 04:58:55 +0000 | [diff] [blame] | 61 | BuiltinBug *BT_UseFree; |
Jordy Rose | 43859f6 | 2010-06-07 19:32:37 +0000 | [diff] [blame] | 62 | BuiltinBug *BT_BadFree; |
Zhongxing Xu | a5ce966 | 2010-06-01 03:01:33 +0000 | [diff] [blame] | 63 | IdentifierInfo *II_malloc, *II_free, *II_realloc, *II_calloc; |
Zhongxing Xu | 589c0f2 | 2009-11-12 08:38:56 +0000 | [diff] [blame] | 64 | |
| 65 | public: |
Zhongxing Xu | d9c84c8 | 2009-12-12 12:29:38 +0000 | [diff] [blame] | 66 | MallocChecker() |
Jordy Rose | 43859f6 | 2010-06-07 19:32:37 +0000 | [diff] [blame] | 67 | : BT_DoubleFree(0), BT_Leak(0), BT_UseFree(0), BT_BadFree(0), |
Zhongxing Xu | a5ce966 | 2010-06-01 03:01:33 +0000 | [diff] [blame] | 68 | II_malloc(0), II_free(0), II_realloc(0), II_calloc(0) {} |
Zhongxing Xu | 589c0f2 | 2009-11-12 08:38:56 +0000 | [diff] [blame] | 69 | static void *getTag(); |
Zhongxing Xu | a49c6b7 | 2009-12-11 03:09:01 +0000 | [diff] [blame] | 70 | bool EvalCallExpr(CheckerContext &C, const CallExpr *CE); |
Zhongxing Xu | 7b76096 | 2009-11-13 07:25:27 +0000 | [diff] [blame] | 71 | void EvalDeadSymbols(CheckerContext &C,const Stmt *S,SymbolReaper &SymReaper); |
Zhongxing Xu | 243fde9 | 2009-11-17 07:54:15 +0000 | [diff] [blame] | 72 | void EvalEndPath(GREndPathNodeBuilder &B, void *tag, GRExprEngine &Eng); |
Zhongxing Xu | 4985e3e | 2009-11-17 08:58:18 +0000 | [diff] [blame] | 73 | void PreVisitReturnStmt(CheckerContext &C, const ReturnStmt *S); |
Zhongxing Xu | b94b81a | 2009-12-31 06:13:07 +0000 | [diff] [blame] | 74 | const GRState *EvalAssume(const GRState *state, SVal Cond, bool Assumption); |
Zhongxing Xu | c802378 | 2010-03-10 04:58:55 +0000 | [diff] [blame] | 75 | void VisitLocation(CheckerContext &C, const Stmt *S, SVal l); |
Zhongxing Xu | b94b81a | 2009-12-31 06:13:07 +0000 | [diff] [blame] | 76 | |
Zhongxing Xu | 7b76096 | 2009-11-13 07:25:27 +0000 | [diff] [blame] | 77 | private: |
Zhongxing Xu | 589c0f2 | 2009-11-12 08:38:56 +0000 | [diff] [blame] | 78 | void MallocMem(CheckerContext &C, const CallExpr *CE); |
Zhongxing Xu | d9c84c8 | 2009-12-12 12:29:38 +0000 | [diff] [blame] | 79 | const GRState *MallocMemAux(CheckerContext &C, const CallExpr *CE, |
Zhongxing Xu | a5ce966 | 2010-06-01 03:01:33 +0000 | [diff] [blame] | 80 | const Expr *SizeEx, SVal Init, |
| 81 | const GRState *state) { |
| 82 | return MallocMemAux(C, CE, state->getSVal(SizeEx), Init, state); |
| 83 | } |
| 84 | const GRState *MallocMemAux(CheckerContext &C, const CallExpr *CE, |
| 85 | SVal SizeEx, SVal Init, |
| 86 | const GRState *state); |
| 87 | |
Zhongxing Xu | 589c0f2 | 2009-11-12 08:38:56 +0000 | [diff] [blame] | 88 | void FreeMem(CheckerContext &C, const CallExpr *CE); |
Zhongxing Xu | d9c84c8 | 2009-12-12 12:29:38 +0000 | [diff] [blame] | 89 | const GRState *FreeMemAux(CheckerContext &C, const CallExpr *CE, |
| 90 | const GRState *state); |
| 91 | |
| 92 | void ReallocMem(CheckerContext &C, const CallExpr *CE); |
Zhongxing Xu | a5ce966 | 2010-06-01 03:01:33 +0000 | [diff] [blame] | 93 | void CallocMem(CheckerContext &C, const CallExpr *CE); |
Jordy Rose | 43859f6 | 2010-06-07 19:32:37 +0000 | [diff] [blame] | 94 | |
| 95 | bool SummarizeValue(llvm::raw_ostream& os, SVal V); |
| 96 | bool SummarizeRegion(llvm::raw_ostream& os, const MemRegion *MR); |
| 97 | void ReportBadFree(CheckerContext &C, SVal ArgVal, SourceRange range); |
Zhongxing Xu | 589c0f2 | 2009-11-12 08:38:56 +0000 | [diff] [blame] | 98 | }; |
Kovarththanan Rajaratnam | ba5fb5a | 2009-11-28 06:07:30 +0000 | [diff] [blame] | 99 | } // end anonymous namespace |
Zhongxing Xu | 589c0f2 | 2009-11-12 08:38:56 +0000 | [diff] [blame] | 100 | |
Zhongxing Xu | b94b81a | 2009-12-31 06:13:07 +0000 | [diff] [blame] | 101 | typedef llvm::ImmutableMap<SymbolRef, RefState> RegionStateTy; |
| 102 | |
Zhongxing Xu | 589c0f2 | 2009-11-12 08:38:56 +0000 | [diff] [blame] | 103 | namespace clang { |
Zhongxing Xu | 243fde9 | 2009-11-17 07:54:15 +0000 | [diff] [blame] | 104 | template <> |
Zhongxing Xu | 589c0f2 | 2009-11-12 08:38:56 +0000 | [diff] [blame] | 105 | struct GRStateTrait<RegionState> |
| 106 | : public GRStatePartialTrait<llvm::ImmutableMap<SymbolRef, RefState> > { |
| 107 | static void *GDMIndex() { return MallocChecker::getTag(); } |
| 108 | }; |
| 109 | } |
| 110 | |
Zhongxing Xu | 7b76096 | 2009-11-13 07:25:27 +0000 | [diff] [blame] | 111 | void clang::RegisterMallocChecker(GRExprEngine &Eng) { |
| 112 | Eng.registerCheck(new MallocChecker()); |
| 113 | } |
| 114 | |
Zhongxing Xu | 589c0f2 | 2009-11-12 08:38:56 +0000 | [diff] [blame] | 115 | void *MallocChecker::getTag() { |
| 116 | static int x; |
| 117 | return &x; |
| 118 | } |
| 119 | |
Zhongxing Xu | a49c6b7 | 2009-12-11 03:09:01 +0000 | [diff] [blame] | 120 | bool MallocChecker::EvalCallExpr(CheckerContext &C, const CallExpr *CE) { |
| 121 | const GRState *state = C.getState(); |
| 122 | const Expr *Callee = CE->getCallee(); |
Ted Kremenek | 1397663 | 2010-02-08 16:18:51 +0000 | [diff] [blame] | 123 | SVal L = state->getSVal(Callee); |
Zhongxing Xu | a49c6b7 | 2009-12-11 03:09:01 +0000 | [diff] [blame] | 124 | |
| 125 | const FunctionDecl *FD = L.getAsFunctionDecl(); |
Zhongxing Xu | 589c0f2 | 2009-11-12 08:38:56 +0000 | [diff] [blame] | 126 | if (!FD) |
Zhongxing Xu | a49c6b7 | 2009-12-11 03:09:01 +0000 | [diff] [blame] | 127 | return false; |
Zhongxing Xu | 589c0f2 | 2009-11-12 08:38:56 +0000 | [diff] [blame] | 128 | |
| 129 | ASTContext &Ctx = C.getASTContext(); |
| 130 | if (!II_malloc) |
| 131 | II_malloc = &Ctx.Idents.get("malloc"); |
| 132 | if (!II_free) |
Zhongxing Xu | fc7ac8f | 2009-11-13 07:48:11 +0000 | [diff] [blame] | 133 | II_free = &Ctx.Idents.get("free"); |
Zhongxing Xu | d9c84c8 | 2009-12-12 12:29:38 +0000 | [diff] [blame] | 134 | if (!II_realloc) |
| 135 | II_realloc = &Ctx.Idents.get("realloc"); |
Zhongxing Xu | a5ce966 | 2010-06-01 03:01:33 +0000 | [diff] [blame] | 136 | if (!II_calloc) |
| 137 | II_calloc = &Ctx.Idents.get("calloc"); |
Zhongxing Xu | 589c0f2 | 2009-11-12 08:38:56 +0000 | [diff] [blame] | 138 | |
| 139 | if (FD->getIdentifier() == II_malloc) { |
| 140 | MallocMem(C, CE); |
Zhongxing Xu | a49c6b7 | 2009-12-11 03:09:01 +0000 | [diff] [blame] | 141 | return true; |
Zhongxing Xu | 589c0f2 | 2009-11-12 08:38:56 +0000 | [diff] [blame] | 142 | } |
| 143 | |
| 144 | if (FD->getIdentifier() == II_free) { |
| 145 | FreeMem(C, CE); |
Zhongxing Xu | a49c6b7 | 2009-12-11 03:09:01 +0000 | [diff] [blame] | 146 | return true; |
Zhongxing Xu | 589c0f2 | 2009-11-12 08:38:56 +0000 | [diff] [blame] | 147 | } |
Zhongxing Xu | a49c6b7 | 2009-12-11 03:09:01 +0000 | [diff] [blame] | 148 | |
Zhongxing Xu | d9c84c8 | 2009-12-12 12:29:38 +0000 | [diff] [blame] | 149 | if (FD->getIdentifier() == II_realloc) { |
| 150 | ReallocMem(C, CE); |
| 151 | return true; |
| 152 | } |
| 153 | |
Zhongxing Xu | a5ce966 | 2010-06-01 03:01:33 +0000 | [diff] [blame] | 154 | if (FD->getIdentifier() == II_calloc) { |
| 155 | CallocMem(C, CE); |
| 156 | return true; |
| 157 | } |
| 158 | |
Zhongxing Xu | a49c6b7 | 2009-12-11 03:09:01 +0000 | [diff] [blame] | 159 | return false; |
Zhongxing Xu | 589c0f2 | 2009-11-12 08:38:56 +0000 | [diff] [blame] | 160 | } |
| 161 | |
| 162 | void MallocChecker::MallocMem(CheckerContext &C, const CallExpr *CE) { |
Zhongxing Xu | a5ce966 | 2010-06-01 03:01:33 +0000 | [diff] [blame] | 163 | const GRState *state = MallocMemAux(C, CE, CE->getArg(0), UndefinedVal(), |
| 164 | C.getState()); |
Zhongxing Xu | d9c84c8 | 2009-12-12 12:29:38 +0000 | [diff] [blame] | 165 | C.addTransition(state); |
| 166 | } |
| 167 | |
| 168 | const GRState *MallocChecker::MallocMemAux(CheckerContext &C, |
| 169 | const CallExpr *CE, |
Zhongxing Xu | a5ce966 | 2010-06-01 03:01:33 +0000 | [diff] [blame] | 170 | SVal Size, SVal Init, |
Zhongxing Xu | d9c84c8 | 2009-12-12 12:29:38 +0000 | [diff] [blame] | 171 | const GRState *state) { |
Zhongxing Xu | a49c6b7 | 2009-12-11 03:09:01 +0000 | [diff] [blame] | 172 | unsigned Count = C.getNodeBuilder().getCurrentBlockCount(); |
| 173 | ValueManager &ValMgr = C.getValueManager(); |
| 174 | |
| 175 | SVal RetVal = ValMgr.getConjuredSymbolVal(NULL, CE, CE->getType(), Count); |
| 176 | |
Zhongxing Xu | 3ed04d3 | 2010-01-18 08:54:31 +0000 | [diff] [blame] | 177 | state = C.getEngine().getStoreManager().setExtent(state, RetVal.getAsRegion(), |
| 178 | Size); |
| 179 | |
Zhongxing Xu | a5ce966 | 2010-06-01 03:01:33 +0000 | [diff] [blame] | 180 | state = state->bindDefault(RetVal, Init); |
| 181 | |
Zhongxing Xu | a49c6b7 | 2009-12-11 03:09:01 +0000 | [diff] [blame] | 182 | state = state->BindExpr(CE, RetVal); |
| 183 | |
| 184 | SymbolRef Sym = RetVal.getAsLocSymbol(); |
Zhongxing Xu | 589c0f2 | 2009-11-12 08:38:56 +0000 | [diff] [blame] | 185 | assert(Sym); |
| 186 | // Set the symbol's state to Allocated. |
Zhongxing Xu | b94b81a | 2009-12-31 06:13:07 +0000 | [diff] [blame] | 187 | return state->set<RegionState>(Sym, RefState::getAllocateUnchecked(CE)); |
Zhongxing Xu | 589c0f2 | 2009-11-12 08:38:56 +0000 | [diff] [blame] | 188 | } |
| 189 | |
| 190 | void MallocChecker::FreeMem(CheckerContext &C, const CallExpr *CE) { |
Zhongxing Xu | d9c84c8 | 2009-12-12 12:29:38 +0000 | [diff] [blame] | 191 | const GRState *state = FreeMemAux(C, CE, C.getState()); |
| 192 | |
| 193 | if (state) |
| 194 | C.addTransition(state); |
| 195 | } |
| 196 | |
| 197 | const GRState *MallocChecker::FreeMemAux(CheckerContext &C, const CallExpr *CE, |
| 198 | const GRState *state) { |
Jordy Rose | 43859f6 | 2010-06-07 19:32:37 +0000 | [diff] [blame] | 199 | const Expr *ArgExpr = CE->getArg(0); |
| 200 | SVal ArgVal = state->getSVal(ArgExpr); |
Zhongxing Xu | 181cc3d | 2010-02-14 06:49:48 +0000 | [diff] [blame] | 201 | |
| 202 | // If ptr is NULL, no operation is preformed. |
| 203 | if (ArgVal.isZeroConstant()) |
| 204 | return state; |
Jordy Rose | 43859f6 | 2010-06-07 19:32:37 +0000 | [diff] [blame] | 205 | |
| 206 | // Unknown values could easily be okay |
| 207 | // Undefined values are handled elsewhere |
| 208 | if (ArgVal.isUnknownOrUndef()) |
Zhongxing Xu | 8e98ac1 | 2010-05-13 08:26:32 +0000 | [diff] [blame] | 209 | return state; |
Zhongxing Xu | 589c0f2 | 2009-11-12 08:38:56 +0000 | [diff] [blame] | 210 | |
Jordy Rose | 43859f6 | 2010-06-07 19:32:37 +0000 | [diff] [blame] | 211 | const MemRegion *R = ArgVal.getAsRegion(); |
| 212 | |
| 213 | // Nonlocs can't be freed, of course. |
| 214 | // Non-region locations (labels and fixed addresses) also shouldn't be freed. |
| 215 | if (!R) { |
| 216 | ReportBadFree(C, ArgVal, ArgExpr->getSourceRange()); |
| 217 | return NULL; |
| 218 | } |
| 219 | |
| 220 | R = R->StripCasts(); |
| 221 | |
| 222 | // Blocks might show up as heap data, but should not be free()d |
| 223 | if (isa<BlockDataRegion>(R)) { |
| 224 | ReportBadFree(C, ArgVal, ArgExpr->getSourceRange()); |
| 225 | return NULL; |
| 226 | } |
| 227 | |
| 228 | const MemSpaceRegion *MS = R->getMemorySpace(); |
| 229 | |
| 230 | // Parameters, locals, statics, and globals shouldn't be freed. |
| 231 | if (!(isa<UnknownSpaceRegion>(MS) || isa<HeapSpaceRegion>(MS))) { |
| 232 | // FIXME: at the time this code was written, malloc() regions were |
| 233 | // represented by conjured symbols, which are all in UnknownSpaceRegion. |
| 234 | // This means that there isn't actually anything from HeapSpaceRegion |
| 235 | // that should be freed, even though we allow it here. |
| 236 | // Of course, free() can work on memory allocated outside the current |
| 237 | // function, so UnknownSpaceRegion is always a possibility. |
| 238 | // False negatives are better than false positives. |
| 239 | |
| 240 | ReportBadFree(C, ArgVal, ArgExpr->getSourceRange()); |
| 241 | return NULL; |
| 242 | } |
| 243 | |
| 244 | const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R); |
| 245 | // Various cases could lead to non-symbol values here. |
| 246 | // For now, ignore them. |
| 247 | if (!SR) |
| 248 | return state; |
| 249 | |
| 250 | SymbolRef Sym = SR->getSymbol(); |
| 251 | |
Zhongxing Xu | 589c0f2 | 2009-11-12 08:38:56 +0000 | [diff] [blame] | 252 | const RefState *RS = state->get<RegionState>(Sym); |
Zhongxing Xu | 7e3cda9 | 2010-01-18 03:27:34 +0000 | [diff] [blame] | 253 | |
| 254 | // If the symbol has not been tracked, return. This is possible when free() is |
| 255 | // called on a pointer that does not get its pointee directly from malloc(). |
| 256 | // Full support of this requires inter-procedural analysis. |
| 257 | if (!RS) |
| 258 | return state; |
Zhongxing Xu | 589c0f2 | 2009-11-12 08:38:56 +0000 | [diff] [blame] | 259 | |
| 260 | // Check double free. |
Zhongxing Xu | 243fde9 | 2009-11-17 07:54:15 +0000 | [diff] [blame] | 261 | if (RS->isReleased()) { |
Ted Kremenek | 19d67b5 | 2009-11-23 22:22:01 +0000 | [diff] [blame] | 262 | ExplodedNode *N = C.GenerateSink(); |
Zhongxing Xu | 589c0f2 | 2009-11-12 08:38:56 +0000 | [diff] [blame] | 263 | if (N) { |
| 264 | if (!BT_DoubleFree) |
| 265 | BT_DoubleFree = new BuiltinBug("Double free", |
| 266 | "Try to free a memory block that has been released"); |
| 267 | // FIXME: should find where it's freed last time. |
| 268 | BugReport *R = new BugReport(*BT_DoubleFree, |
Benjamin Kramer | d02e232 | 2009-11-14 12:08:24 +0000 | [diff] [blame] | 269 | BT_DoubleFree->getDescription(), N); |
Zhongxing Xu | 589c0f2 | 2009-11-12 08:38:56 +0000 | [diff] [blame] | 270 | C.EmitReport(R); |
| 271 | } |
Zhongxing Xu | d9c84c8 | 2009-12-12 12:29:38 +0000 | [diff] [blame] | 272 | return NULL; |
Zhongxing Xu | 589c0f2 | 2009-11-12 08:38:56 +0000 | [diff] [blame] | 273 | } |
| 274 | |
| 275 | // Normal free. |
Zhongxing Xu | d9c84c8 | 2009-12-12 12:29:38 +0000 | [diff] [blame] | 276 | return state->set<RegionState>(Sym, RefState::getReleased(CE)); |
| 277 | } |
| 278 | |
Jordy Rose | 43859f6 | 2010-06-07 19:32:37 +0000 | [diff] [blame] | 279 | bool MallocChecker::SummarizeValue(llvm::raw_ostream& os, SVal V) { |
| 280 | if (nonloc::ConcreteInt *IntVal = dyn_cast<nonloc::ConcreteInt>(&V)) |
| 281 | os << "an integer (" << IntVal->getValue() << ")"; |
| 282 | else if (loc::ConcreteInt *ConstAddr = dyn_cast<loc::ConcreteInt>(&V)) |
| 283 | os << "a constant address (" << ConstAddr->getValue() << ")"; |
| 284 | else if (loc::GotoLabel *Label = dyn_cast<loc::GotoLabel>(&V)) |
| 285 | os << "the address of the label '" |
| 286 | << Label->getLabel()->getID()->getName() |
| 287 | << "'"; |
| 288 | else |
| 289 | return false; |
| 290 | |
| 291 | return true; |
| 292 | } |
| 293 | |
| 294 | bool MallocChecker::SummarizeRegion(llvm::raw_ostream& os, |
| 295 | const MemRegion *MR) { |
| 296 | switch (MR->getKind()) { |
| 297 | case MemRegion::FunctionTextRegionKind: { |
| 298 | const FunctionDecl *FD = cast<FunctionTextRegion>(MR)->getDecl(); |
| 299 | if (FD) |
| 300 | os << "the address of the function '" << FD << "'"; |
| 301 | else |
| 302 | os << "the address of a function"; |
| 303 | return true; |
| 304 | } |
| 305 | case MemRegion::BlockTextRegionKind: |
| 306 | os << "block text"; |
| 307 | return true; |
| 308 | case MemRegion::BlockDataRegionKind: |
| 309 | // FIXME: where the block came from? |
| 310 | os << "a block"; |
| 311 | return true; |
| 312 | default: { |
| 313 | const MemSpaceRegion *MS = MR->getMemorySpace(); |
| 314 | |
| 315 | switch (MS->getKind()) { |
| 316 | case MemRegion::StackLocalsSpaceRegionKind: { |
| 317 | const VarRegion *VR = dyn_cast<VarRegion>(MR); |
| 318 | const VarDecl *VD; |
| 319 | if (VR) |
| 320 | VD = VR->getDecl(); |
| 321 | else |
| 322 | VD = NULL; |
| 323 | |
| 324 | if (VD) |
| 325 | os << "the address of the local variable '" << VD->getName() << "'"; |
| 326 | else |
| 327 | os << "the address of a local stack variable"; |
| 328 | return true; |
| 329 | } |
| 330 | case MemRegion::StackArgumentsSpaceRegionKind: { |
| 331 | const VarRegion *VR = dyn_cast<VarRegion>(MR); |
| 332 | const VarDecl *VD; |
| 333 | if (VR) |
| 334 | VD = VR->getDecl(); |
| 335 | else |
| 336 | VD = NULL; |
| 337 | |
| 338 | if (VD) |
| 339 | os << "the address of the parameter '" << VD->getName() << "'"; |
| 340 | else |
| 341 | os << "the address of a parameter"; |
| 342 | return true; |
| 343 | } |
| 344 | case MemRegion::GlobalsSpaceRegionKind: { |
| 345 | const VarRegion *VR = dyn_cast<VarRegion>(MR); |
| 346 | const VarDecl *VD; |
| 347 | if (VR) |
| 348 | VD = VR->getDecl(); |
| 349 | else |
| 350 | VD = NULL; |
| 351 | |
| 352 | if (VD) { |
| 353 | if (VD->isStaticLocal()) |
| 354 | os << "the address of the static variable '" << VD->getName() << "'"; |
| 355 | else |
| 356 | os << "the address of the global variable '" << VD->getName() << "'"; |
| 357 | } else |
| 358 | os << "the address of a global variable"; |
| 359 | return true; |
| 360 | } |
| 361 | default: |
| 362 | return false; |
| 363 | } |
| 364 | } |
| 365 | } |
| 366 | } |
| 367 | |
| 368 | void MallocChecker::ReportBadFree(CheckerContext &C, SVal ArgVal, |
| 369 | SourceRange range) { |
| 370 | ExplodedNode *N = C.GenerateSink(); |
| 371 | if (N) { |
| 372 | if (!BT_BadFree) |
| 373 | BT_BadFree = new BuiltinBug("Bad free"); |
| 374 | |
| 375 | llvm::SmallString<100> buf; |
| 376 | llvm::raw_svector_ostream os(buf); |
| 377 | |
| 378 | const MemRegion *MR = ArgVal.getAsRegion(); |
| 379 | if (MR) { |
| 380 | while (const ElementRegion *ER = dyn_cast<ElementRegion>(MR)) |
| 381 | MR = ER->getSuperRegion(); |
| 382 | |
| 383 | // Special case for alloca() |
| 384 | if (isa<AllocaRegion>(MR)) |
| 385 | os << "Argument to free() was allocated by alloca(), not malloc()"; |
| 386 | else { |
| 387 | os << "Argument to free() is "; |
| 388 | if (SummarizeRegion(os, MR)) |
| 389 | os << ", which is not memory allocated by malloc()"; |
| 390 | else |
| 391 | os << "not memory allocated by malloc()"; |
| 392 | } |
| 393 | } else { |
| 394 | os << "Argument to free() is "; |
| 395 | if (SummarizeValue(os, ArgVal)) |
| 396 | os << ", which is not memory allocated by malloc()"; |
| 397 | else |
| 398 | os << "not memory allocated by malloc()"; |
| 399 | } |
| 400 | |
Jordy Rose | 3104124 | 2010-06-08 22:59:01 +0000 | [diff] [blame^] | 401 | EnhancedBugReport *R = new EnhancedBugReport(*BT_BadFree, os.str(), N); |
Jordy Rose | 43859f6 | 2010-06-07 19:32:37 +0000 | [diff] [blame] | 402 | R->addRange(range); |
| 403 | C.EmitReport(R); |
| 404 | } |
| 405 | } |
| 406 | |
Zhongxing Xu | d9c84c8 | 2009-12-12 12:29:38 +0000 | [diff] [blame] | 407 | void MallocChecker::ReallocMem(CheckerContext &C, const CallExpr *CE) { |
| 408 | const GRState *state = C.getState(); |
| 409 | const Expr *Arg0 = CE->getArg(0); |
Ted Kremenek | 1397663 | 2010-02-08 16:18:51 +0000 | [diff] [blame] | 410 | DefinedOrUnknownSVal Arg0Val=cast<DefinedOrUnknownSVal>(state->getSVal(Arg0)); |
Zhongxing Xu | d9c84c8 | 2009-12-12 12:29:38 +0000 | [diff] [blame] | 411 | |
| 412 | ValueManager &ValMgr = C.getValueManager(); |
| 413 | SValuator &SVator = C.getSValuator(); |
| 414 | |
| 415 | DefinedOrUnknownSVal PtrEQ = SVator.EvalEQ(state, Arg0Val, ValMgr.makeNull()); |
| 416 | |
| 417 | // If the ptr is NULL, the call is equivalent to malloc(size). |
| 418 | if (const GRState *stateEqual = state->Assume(PtrEQ, true)) { |
| 419 | // Hack: set the NULL symbolic region to released to suppress false warning. |
| 420 | // In the future we should add more states for allocated regions, e.g., |
| 421 | // CheckedNull, CheckedNonNull. |
| 422 | |
| 423 | SymbolRef Sym = Arg0Val.getAsLocSymbol(); |
| 424 | if (Sym) |
| 425 | stateEqual = stateEqual->set<RegionState>(Sym, RefState::getReleased(CE)); |
| 426 | |
Zhongxing Xu | a5ce966 | 2010-06-01 03:01:33 +0000 | [diff] [blame] | 427 | const GRState *stateMalloc = MallocMemAux(C, CE, CE->getArg(1), |
| 428 | UndefinedVal(), stateEqual); |
Zhongxing Xu | d9c84c8 | 2009-12-12 12:29:38 +0000 | [diff] [blame] | 429 | C.addTransition(stateMalloc); |
| 430 | } |
| 431 | |
| 432 | if (const GRState *stateNotEqual = state->Assume(PtrEQ, false)) { |
| 433 | const Expr *Arg1 = CE->getArg(1); |
| 434 | DefinedOrUnknownSVal Arg1Val = |
Ted Kremenek | 1397663 | 2010-02-08 16:18:51 +0000 | [diff] [blame] | 435 | cast<DefinedOrUnknownSVal>(stateNotEqual->getSVal(Arg1)); |
Zhongxing Xu | d9c84c8 | 2009-12-12 12:29:38 +0000 | [diff] [blame] | 436 | DefinedOrUnknownSVal SizeZero = SVator.EvalEQ(stateNotEqual, Arg1Val, |
| 437 | ValMgr.makeIntValWithPtrWidth(0, false)); |
| 438 | |
| 439 | if (const GRState *stateSizeZero = stateNotEqual->Assume(SizeZero, true)) { |
| 440 | const GRState *stateFree = FreeMemAux(C, CE, stateSizeZero); |
| 441 | if (stateFree) |
| 442 | C.addTransition(stateFree->BindExpr(CE, UndefinedVal(), true)); |
| 443 | } |
| 444 | |
| 445 | if (const GRState *stateSizeNotZero=stateNotEqual->Assume(SizeZero,false)) { |
| 446 | const GRState *stateFree = FreeMemAux(C, CE, stateSizeNotZero); |
| 447 | if (stateFree) { |
| 448 | // FIXME: We should copy the content of the original buffer. |
Zhongxing Xu | 3ed04d3 | 2010-01-18 08:54:31 +0000 | [diff] [blame] | 449 | const GRState *stateRealloc = MallocMemAux(C, CE, CE->getArg(1), |
Zhongxing Xu | a5ce966 | 2010-06-01 03:01:33 +0000 | [diff] [blame] | 450 | UnknownVal(), stateFree); |
Zhongxing Xu | d9c84c8 | 2009-12-12 12:29:38 +0000 | [diff] [blame] | 451 | C.addTransition(stateRealloc); |
| 452 | } |
| 453 | } |
| 454 | } |
Zhongxing Xu | 589c0f2 | 2009-11-12 08:38:56 +0000 | [diff] [blame] | 455 | } |
Zhongxing Xu | 7b76096 | 2009-11-13 07:25:27 +0000 | [diff] [blame] | 456 | |
Zhongxing Xu | a5ce966 | 2010-06-01 03:01:33 +0000 | [diff] [blame] | 457 | void MallocChecker::CallocMem(CheckerContext &C, const CallExpr *CE) { |
| 458 | const GRState *state = C.getState(); |
| 459 | |
| 460 | ValueManager &ValMgr = C.getValueManager(); |
| 461 | SValuator &SVator = C.getSValuator(); |
| 462 | |
| 463 | SVal Count = state->getSVal(CE->getArg(0)); |
| 464 | SVal EleSize = state->getSVal(CE->getArg(1)); |
| 465 | SVal TotalSize = SVator.EvalBinOp(state, BinaryOperator::Mul, Count, EleSize, |
| 466 | ValMgr.getContext().getSizeType()); |
| 467 | |
| 468 | SVal Zero = ValMgr.makeZeroVal(ValMgr.getContext().CharTy); |
| 469 | |
| 470 | state = MallocMemAux(C, CE, TotalSize, Zero, state); |
| 471 | C.addTransition(state); |
| 472 | } |
| 473 | |
Zhongxing Xu | 7b76096 | 2009-11-13 07:25:27 +0000 | [diff] [blame] | 474 | void MallocChecker::EvalDeadSymbols(CheckerContext &C, const Stmt *S, |
| 475 | SymbolReaper &SymReaper) { |
Zhongxing Xu | fc7ac8f | 2009-11-13 07:48:11 +0000 | [diff] [blame] | 476 | for (SymbolReaper::dead_iterator I = SymReaper.dead_begin(), |
| 477 | E = SymReaper.dead_end(); I != E; ++I) { |
| 478 | SymbolRef Sym = *I; |
| 479 | const GRState *state = C.getState(); |
| 480 | const RefState *RS = state->get<RegionState>(Sym); |
| 481 | if (!RS) |
| 482 | return; |
| 483 | |
Zhongxing Xu | 243fde9 | 2009-11-17 07:54:15 +0000 | [diff] [blame] | 484 | if (RS->isAllocated()) { |
Ted Kremenek | 19d67b5 | 2009-11-23 22:22:01 +0000 | [diff] [blame] | 485 | ExplodedNode *N = C.GenerateSink(); |
Zhongxing Xu | fc7ac8f | 2009-11-13 07:48:11 +0000 | [diff] [blame] | 486 | if (N) { |
| 487 | if (!BT_Leak) |
| 488 | BT_Leak = new BuiltinBug("Memory leak", |
| 489 | "Allocated memory never released. Potential memory leak."); |
| 490 | // FIXME: where it is allocated. |
Zhongxing Xu | 243fde9 | 2009-11-17 07:54:15 +0000 | [diff] [blame] | 491 | BugReport *R = new BugReport(*BT_Leak, BT_Leak->getDescription(), N); |
Zhongxing Xu | fc7ac8f | 2009-11-13 07:48:11 +0000 | [diff] [blame] | 492 | C.EmitReport(R); |
| 493 | } |
| 494 | } |
| 495 | } |
Zhongxing Xu | 7b76096 | 2009-11-13 07:25:27 +0000 | [diff] [blame] | 496 | } |
Zhongxing Xu | 243fde9 | 2009-11-17 07:54:15 +0000 | [diff] [blame] | 497 | |
| 498 | void MallocChecker::EvalEndPath(GREndPathNodeBuilder &B, void *tag, |
| 499 | GRExprEngine &Eng) { |
Zhongxing Xu | f605aae | 2009-11-22 13:22:34 +0000 | [diff] [blame] | 500 | SaveAndRestore<bool> OldHasGen(B.HasGeneratedNode); |
Zhongxing Xu | 243fde9 | 2009-11-17 07:54:15 +0000 | [diff] [blame] | 501 | const GRState *state = B.getState(); |
| 502 | typedef llvm::ImmutableMap<SymbolRef, RefState> SymMap; |
| 503 | SymMap M = state->get<RegionState>(); |
| 504 | |
| 505 | for (SymMap::iterator I = M.begin(), E = M.end(); I != E; ++I) { |
| 506 | RefState RS = I->second; |
| 507 | if (RS.isAllocated()) { |
| 508 | ExplodedNode *N = B.generateNode(state, tag, B.getPredecessor()); |
| 509 | if (N) { |
| 510 | if (!BT_Leak) |
| 511 | BT_Leak = new BuiltinBug("Memory leak", |
| 512 | "Allocated memory never released. Potential memory leak."); |
| 513 | BugReport *R = new BugReport(*BT_Leak, BT_Leak->getDescription(), N); |
| 514 | Eng.getBugReporter().EmitReport(R); |
| 515 | } |
| 516 | } |
| 517 | } |
| 518 | } |
Zhongxing Xu | 4985e3e | 2009-11-17 08:58:18 +0000 | [diff] [blame] | 519 | |
| 520 | void MallocChecker::PreVisitReturnStmt(CheckerContext &C, const ReturnStmt *S) { |
| 521 | const Expr *RetE = S->getRetValue(); |
| 522 | if (!RetE) |
| 523 | return; |
| 524 | |
| 525 | const GRState *state = C.getState(); |
| 526 | |
Ted Kremenek | 1397663 | 2010-02-08 16:18:51 +0000 | [diff] [blame] | 527 | SymbolRef Sym = state->getSVal(RetE).getAsSymbol(); |
Zhongxing Xu | 4985e3e | 2009-11-17 08:58:18 +0000 | [diff] [blame] | 528 | |
| 529 | if (!Sym) |
| 530 | return; |
| 531 | |
| 532 | const RefState *RS = state->get<RegionState>(Sym); |
| 533 | if (!RS) |
| 534 | return; |
| 535 | |
| 536 | // FIXME: check other cases. |
| 537 | if (RS->isAllocated()) |
| 538 | state = state->set<RegionState>(Sym, RefState::getEscaped(S)); |
| 539 | |
Ted Kremenek | 19d67b5 | 2009-11-23 22:22:01 +0000 | [diff] [blame] | 540 | C.addTransition(state); |
Zhongxing Xu | 4985e3e | 2009-11-17 08:58:18 +0000 | [diff] [blame] | 541 | } |
Zhongxing Xu | b94b81a | 2009-12-31 06:13:07 +0000 | [diff] [blame] | 542 | |
| 543 | const GRState *MallocChecker::EvalAssume(const GRState *state, SVal Cond, |
| 544 | bool Assumption) { |
| 545 | // If a symblic region is assumed to NULL, set its state to AllocateFailed. |
| 546 | // FIXME: should also check symbols assumed to non-null. |
| 547 | |
| 548 | RegionStateTy RS = state->get<RegionState>(); |
| 549 | |
| 550 | for (RegionStateTy::iterator I = RS.begin(), E = RS.end(); I != E; ++I) { |
| 551 | if (state->getSymVal(I.getKey())) |
| 552 | state = state->set<RegionState>(I.getKey(),RefState::getAllocateFailed()); |
| 553 | } |
| 554 | |
| 555 | return state; |
| 556 | } |
Zhongxing Xu | c802378 | 2010-03-10 04:58:55 +0000 | [diff] [blame] | 557 | |
| 558 | // Check if the location is a freed symbolic region. |
| 559 | void MallocChecker::VisitLocation(CheckerContext &C, const Stmt *S, SVal l) { |
| 560 | SymbolRef Sym = l.getLocSymbolInBase(); |
| 561 | if (Sym) { |
| 562 | const RefState *RS = C.getState()->get<RegionState>(Sym); |
| 563 | if (RS) |
| 564 | if (RS->isReleased()) { |
| 565 | ExplodedNode *N = C.GenerateSink(); |
| 566 | if (!BT_UseFree) |
| 567 | BT_UseFree = new BuiltinBug("Use dynamically allocated memory after" |
| 568 | " it is freed."); |
| 569 | |
| 570 | BugReport *R = new BugReport(*BT_UseFree, BT_UseFree->getDescription(), |
| 571 | N); |
| 572 | C.EmitReport(R); |
| 573 | } |
| 574 | } |
| 575 | } |