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" |
Zhongxing Xu | 589c0f2 | 2009-11-12 08:38:56 +0000 | [diff] [blame] | 16 | #include "clang/Analysis/PathSensitive/CheckerVisitor.h" |
| 17 | #include "clang/Analysis/PathSensitive/GRState.h" |
| 18 | #include "clang/Analysis/PathSensitive/GRStateTrait.h" |
| 19 | #include "clang/Analysis/PathSensitive/SymbolManager.h" |
| 20 | #include "llvm/ADT/ImmutableMap.h" |
| 21 | using namespace clang; |
| 22 | |
| 23 | namespace { |
| 24 | |
Zhongxing Xu | 7fb1464 | 2009-12-11 00:55:44 +0000 | [diff] [blame] | 25 | class RefState { |
Zhongxing Xu | 243fde9 | 2009-11-17 07:54:15 +0000 | [diff] [blame] | 26 | enum Kind { Allocated, Released, Escaped } K; |
| 27 | const Stmt *S; |
| 28 | |
Zhongxing Xu | 7fb1464 | 2009-12-11 00:55:44 +0000 | [diff] [blame] | 29 | public: |
Zhongxing Xu | 243fde9 | 2009-11-17 07:54:15 +0000 | [diff] [blame] | 30 | RefState(Kind k, const Stmt *s) : K(k), S(s) {} |
| 31 | |
| 32 | bool isAllocated() const { return K == Allocated; } |
| 33 | bool isReleased() const { return K == Released; } |
| 34 | bool isEscaped() const { return K == Escaped; } |
| 35 | |
| 36 | bool operator==(const RefState &X) const { |
| 37 | return K == X.K && S == X.S; |
| 38 | } |
| 39 | |
| 40 | static RefState getAllocated(const Stmt *s) { return RefState(Allocated, s); } |
| 41 | static RefState getReleased(const Stmt *s) { return RefState(Released, s); } |
| 42 | static RefState getEscaped(const Stmt *s) { return RefState(Escaped, s); } |
| 43 | |
| 44 | void Profile(llvm::FoldingSetNodeID &ID) const { |
| 45 | ID.AddInteger(K); |
| 46 | ID.AddPointer(S); |
| 47 | } |
Zhongxing Xu | 589c0f2 | 2009-11-12 08:38:56 +0000 | [diff] [blame] | 48 | }; |
| 49 | |
Kovarththanan Rajaratnam | ba5fb5a | 2009-11-28 06:07:30 +0000 | [diff] [blame] | 50 | class RegionState {}; |
Zhongxing Xu | 589c0f2 | 2009-11-12 08:38:56 +0000 | [diff] [blame] | 51 | |
Kovarththanan Rajaratnam | ba5fb5a | 2009-11-28 06:07:30 +0000 | [diff] [blame] | 52 | class MallocChecker : public CheckerVisitor<MallocChecker> { |
Zhongxing Xu | 589c0f2 | 2009-11-12 08:38:56 +0000 | [diff] [blame] | 53 | BuiltinBug *BT_DoubleFree; |
Zhongxing Xu | fc7ac8f | 2009-11-13 07:48:11 +0000 | [diff] [blame] | 54 | BuiltinBug *BT_Leak; |
Zhongxing Xu | 589c0f2 | 2009-11-12 08:38:56 +0000 | [diff] [blame] | 55 | IdentifierInfo *II_malloc; |
| 56 | IdentifierInfo *II_free; |
| 57 | |
| 58 | public: |
Zhongxing Xu | fc7ac8f | 2009-11-13 07:48:11 +0000 | [diff] [blame] | 59 | MallocChecker() : BT_DoubleFree(0), BT_Leak(0), II_malloc(0), II_free(0) {} |
Zhongxing Xu | 589c0f2 | 2009-11-12 08:38:56 +0000 | [diff] [blame] | 60 | static void *getTag(); |
Zhongxing Xu | a49c6b7 | 2009-12-11 03:09:01 +0000 | [diff] [blame^] | 61 | bool EvalCallExpr(CheckerContext &C, const CallExpr *CE); |
Zhongxing Xu | 7b76096 | 2009-11-13 07:25:27 +0000 | [diff] [blame] | 62 | void EvalDeadSymbols(CheckerContext &C,const Stmt *S,SymbolReaper &SymReaper); |
Zhongxing Xu | 243fde9 | 2009-11-17 07:54:15 +0000 | [diff] [blame] | 63 | void EvalEndPath(GREndPathNodeBuilder &B, void *tag, GRExprEngine &Eng); |
Zhongxing Xu | 4985e3e | 2009-11-17 08:58:18 +0000 | [diff] [blame] | 64 | void PreVisitReturnStmt(CheckerContext &C, const ReturnStmt *S); |
Zhongxing Xu | 7b76096 | 2009-11-13 07:25:27 +0000 | [diff] [blame] | 65 | private: |
Zhongxing Xu | 589c0f2 | 2009-11-12 08:38:56 +0000 | [diff] [blame] | 66 | void MallocMem(CheckerContext &C, const CallExpr *CE); |
| 67 | void FreeMem(CheckerContext &C, const CallExpr *CE); |
| 68 | }; |
Kovarththanan Rajaratnam | ba5fb5a | 2009-11-28 06:07:30 +0000 | [diff] [blame] | 69 | } // end anonymous namespace |
Zhongxing Xu | 589c0f2 | 2009-11-12 08:38:56 +0000 | [diff] [blame] | 70 | |
Zhongxing Xu | 589c0f2 | 2009-11-12 08:38:56 +0000 | [diff] [blame] | 71 | namespace clang { |
Zhongxing Xu | 243fde9 | 2009-11-17 07:54:15 +0000 | [diff] [blame] | 72 | template <> |
Zhongxing Xu | 589c0f2 | 2009-11-12 08:38:56 +0000 | [diff] [blame] | 73 | struct GRStateTrait<RegionState> |
| 74 | : public GRStatePartialTrait<llvm::ImmutableMap<SymbolRef, RefState> > { |
| 75 | static void *GDMIndex() { return MallocChecker::getTag(); } |
| 76 | }; |
| 77 | } |
| 78 | |
Zhongxing Xu | 7b76096 | 2009-11-13 07:25:27 +0000 | [diff] [blame] | 79 | void clang::RegisterMallocChecker(GRExprEngine &Eng) { |
| 80 | Eng.registerCheck(new MallocChecker()); |
| 81 | } |
| 82 | |
Zhongxing Xu | 589c0f2 | 2009-11-12 08:38:56 +0000 | [diff] [blame] | 83 | void *MallocChecker::getTag() { |
| 84 | static int x; |
| 85 | return &x; |
| 86 | } |
| 87 | |
Zhongxing Xu | a49c6b7 | 2009-12-11 03:09:01 +0000 | [diff] [blame^] | 88 | bool MallocChecker::EvalCallExpr(CheckerContext &C, const CallExpr *CE) { |
| 89 | const GRState *state = C.getState(); |
| 90 | const Expr *Callee = CE->getCallee(); |
| 91 | SVal L = state->getSVal(Callee); |
| 92 | |
| 93 | const FunctionDecl *FD = L.getAsFunctionDecl(); |
Zhongxing Xu | 589c0f2 | 2009-11-12 08:38:56 +0000 | [diff] [blame] | 94 | if (!FD) |
Zhongxing Xu | a49c6b7 | 2009-12-11 03:09:01 +0000 | [diff] [blame^] | 95 | return false; |
Zhongxing Xu | 589c0f2 | 2009-11-12 08:38:56 +0000 | [diff] [blame] | 96 | |
| 97 | ASTContext &Ctx = C.getASTContext(); |
| 98 | if (!II_malloc) |
| 99 | II_malloc = &Ctx.Idents.get("malloc"); |
| 100 | if (!II_free) |
Zhongxing Xu | fc7ac8f | 2009-11-13 07:48:11 +0000 | [diff] [blame] | 101 | II_free = &Ctx.Idents.get("free"); |
Zhongxing Xu | 589c0f2 | 2009-11-12 08:38:56 +0000 | [diff] [blame] | 102 | |
| 103 | if (FD->getIdentifier() == II_malloc) { |
| 104 | MallocMem(C, CE); |
Zhongxing Xu | a49c6b7 | 2009-12-11 03:09:01 +0000 | [diff] [blame^] | 105 | return true; |
Zhongxing Xu | 589c0f2 | 2009-11-12 08:38:56 +0000 | [diff] [blame] | 106 | } |
| 107 | |
| 108 | if (FD->getIdentifier() == II_free) { |
| 109 | FreeMem(C, CE); |
Zhongxing Xu | a49c6b7 | 2009-12-11 03:09:01 +0000 | [diff] [blame^] | 110 | return true; |
Zhongxing Xu | 589c0f2 | 2009-11-12 08:38:56 +0000 | [diff] [blame] | 111 | } |
Zhongxing Xu | a49c6b7 | 2009-12-11 03:09:01 +0000 | [diff] [blame^] | 112 | |
| 113 | return false; |
Zhongxing Xu | 589c0f2 | 2009-11-12 08:38:56 +0000 | [diff] [blame] | 114 | } |
| 115 | |
| 116 | void MallocChecker::MallocMem(CheckerContext &C, const CallExpr *CE) { |
Zhongxing Xu | a49c6b7 | 2009-12-11 03:09:01 +0000 | [diff] [blame^] | 117 | unsigned Count = C.getNodeBuilder().getCurrentBlockCount(); |
| 118 | ValueManager &ValMgr = C.getValueManager(); |
| 119 | |
| 120 | SVal RetVal = ValMgr.getConjuredSymbolVal(NULL, CE, CE->getType(), Count); |
| 121 | |
Zhongxing Xu | 589c0f2 | 2009-11-12 08:38:56 +0000 | [diff] [blame] | 122 | const GRState *state = C.getState(); |
Zhongxing Xu | a49c6b7 | 2009-12-11 03:09:01 +0000 | [diff] [blame^] | 123 | state = state->BindExpr(CE, RetVal); |
| 124 | |
| 125 | SymbolRef Sym = RetVal.getAsLocSymbol(); |
Zhongxing Xu | 589c0f2 | 2009-11-12 08:38:56 +0000 | [diff] [blame] | 126 | assert(Sym); |
| 127 | // Set the symbol's state to Allocated. |
Ted Kremenek | 19d67b5 | 2009-11-23 22:22:01 +0000 | [diff] [blame] | 128 | C.addTransition(state->set<RegionState>(Sym, RefState::getAllocated(CE))); |
Zhongxing Xu | 589c0f2 | 2009-11-12 08:38:56 +0000 | [diff] [blame] | 129 | } |
| 130 | |
| 131 | void MallocChecker::FreeMem(CheckerContext &C, const CallExpr *CE) { |
| 132 | const GRState *state = C.getState(); |
| 133 | SVal ArgVal = state->getSVal(CE->getArg(0)); |
| 134 | SymbolRef Sym = ArgVal.getAsLocSymbol(); |
| 135 | assert(Sym); |
| 136 | |
| 137 | const RefState *RS = state->get<RegionState>(Sym); |
| 138 | assert(RS); |
| 139 | |
| 140 | // Check double free. |
Zhongxing Xu | 243fde9 | 2009-11-17 07:54:15 +0000 | [diff] [blame] | 141 | if (RS->isReleased()) { |
Ted Kremenek | 19d67b5 | 2009-11-23 22:22:01 +0000 | [diff] [blame] | 142 | ExplodedNode *N = C.GenerateSink(); |
Zhongxing Xu | 589c0f2 | 2009-11-12 08:38:56 +0000 | [diff] [blame] | 143 | if (N) { |
| 144 | if (!BT_DoubleFree) |
| 145 | BT_DoubleFree = new BuiltinBug("Double free", |
| 146 | "Try to free a memory block that has been released"); |
| 147 | // FIXME: should find where it's freed last time. |
| 148 | BugReport *R = new BugReport(*BT_DoubleFree, |
Benjamin Kramer | d02e232 | 2009-11-14 12:08:24 +0000 | [diff] [blame] | 149 | BT_DoubleFree->getDescription(), N); |
Zhongxing Xu | 589c0f2 | 2009-11-12 08:38:56 +0000 | [diff] [blame] | 150 | C.EmitReport(R); |
| 151 | } |
| 152 | return; |
| 153 | } |
| 154 | |
| 155 | // Normal free. |
Zhongxing Xu | 243fde9 | 2009-11-17 07:54:15 +0000 | [diff] [blame] | 156 | const GRState *FreedState |
| 157 | = state->set<RegionState>(Sym, RefState::getReleased(CE)); |
Ted Kremenek | 19d67b5 | 2009-11-23 22:22:01 +0000 | [diff] [blame] | 158 | C.addTransition(FreedState); |
Zhongxing Xu | 589c0f2 | 2009-11-12 08:38:56 +0000 | [diff] [blame] | 159 | } |
Zhongxing Xu | 7b76096 | 2009-11-13 07:25:27 +0000 | [diff] [blame] | 160 | |
| 161 | void MallocChecker::EvalDeadSymbols(CheckerContext &C, const Stmt *S, |
| 162 | SymbolReaper &SymReaper) { |
Zhongxing Xu | fc7ac8f | 2009-11-13 07:48:11 +0000 | [diff] [blame] | 163 | for (SymbolReaper::dead_iterator I = SymReaper.dead_begin(), |
| 164 | E = SymReaper.dead_end(); I != E; ++I) { |
| 165 | SymbolRef Sym = *I; |
| 166 | const GRState *state = C.getState(); |
| 167 | const RefState *RS = state->get<RegionState>(Sym); |
| 168 | if (!RS) |
| 169 | return; |
| 170 | |
Zhongxing Xu | 243fde9 | 2009-11-17 07:54:15 +0000 | [diff] [blame] | 171 | if (RS->isAllocated()) { |
Ted Kremenek | 19d67b5 | 2009-11-23 22:22:01 +0000 | [diff] [blame] | 172 | ExplodedNode *N = C.GenerateSink(); |
Zhongxing Xu | fc7ac8f | 2009-11-13 07:48:11 +0000 | [diff] [blame] | 173 | if (N) { |
| 174 | if (!BT_Leak) |
| 175 | BT_Leak = new BuiltinBug("Memory leak", |
| 176 | "Allocated memory never released. Potential memory leak."); |
| 177 | // FIXME: where it is allocated. |
Zhongxing Xu | 243fde9 | 2009-11-17 07:54:15 +0000 | [diff] [blame] | 178 | BugReport *R = new BugReport(*BT_Leak, BT_Leak->getDescription(), N); |
Zhongxing Xu | fc7ac8f | 2009-11-13 07:48:11 +0000 | [diff] [blame] | 179 | C.EmitReport(R); |
| 180 | } |
| 181 | } |
| 182 | } |
Zhongxing Xu | 7b76096 | 2009-11-13 07:25:27 +0000 | [diff] [blame] | 183 | } |
Zhongxing Xu | 243fde9 | 2009-11-17 07:54:15 +0000 | [diff] [blame] | 184 | |
| 185 | void MallocChecker::EvalEndPath(GREndPathNodeBuilder &B, void *tag, |
| 186 | GRExprEngine &Eng) { |
Zhongxing Xu | f605aae | 2009-11-22 13:22:34 +0000 | [diff] [blame] | 187 | SaveAndRestore<bool> OldHasGen(B.HasGeneratedNode); |
Zhongxing Xu | 243fde9 | 2009-11-17 07:54:15 +0000 | [diff] [blame] | 188 | const GRState *state = B.getState(); |
| 189 | typedef llvm::ImmutableMap<SymbolRef, RefState> SymMap; |
| 190 | SymMap M = state->get<RegionState>(); |
| 191 | |
| 192 | for (SymMap::iterator I = M.begin(), E = M.end(); I != E; ++I) { |
| 193 | RefState RS = I->second; |
| 194 | if (RS.isAllocated()) { |
| 195 | ExplodedNode *N = B.generateNode(state, tag, B.getPredecessor()); |
| 196 | if (N) { |
| 197 | if (!BT_Leak) |
| 198 | BT_Leak = new BuiltinBug("Memory leak", |
| 199 | "Allocated memory never released. Potential memory leak."); |
| 200 | BugReport *R = new BugReport(*BT_Leak, BT_Leak->getDescription(), N); |
| 201 | Eng.getBugReporter().EmitReport(R); |
| 202 | } |
| 203 | } |
| 204 | } |
| 205 | } |
Zhongxing Xu | 4985e3e | 2009-11-17 08:58:18 +0000 | [diff] [blame] | 206 | |
| 207 | void MallocChecker::PreVisitReturnStmt(CheckerContext &C, const ReturnStmt *S) { |
| 208 | const Expr *RetE = S->getRetValue(); |
| 209 | if (!RetE) |
| 210 | return; |
| 211 | |
| 212 | const GRState *state = C.getState(); |
| 213 | |
| 214 | SymbolRef Sym = state->getSVal(RetE).getAsSymbol(); |
| 215 | |
| 216 | if (!Sym) |
| 217 | return; |
| 218 | |
| 219 | const RefState *RS = state->get<RegionState>(Sym); |
| 220 | if (!RS) |
| 221 | return; |
| 222 | |
| 223 | // FIXME: check other cases. |
| 224 | if (RS->isAllocated()) |
| 225 | state = state->set<RegionState>(Sym, RefState::getEscaped(S)); |
| 226 | |
Ted Kremenek | 19d67b5 | 2009-11-23 22:22:01 +0000 | [diff] [blame] | 227 | C.addTransition(state); |
Zhongxing Xu | 4985e3e | 2009-11-17 08:58:18 +0000 | [diff] [blame] | 228 | } |