blob: bbfc7b076d316cc8ce9aaadfe6f2f12933ab1c63 [file] [log] [blame]
Zhongxing Xu589c0f22009-11-12 08:38:56 +00001//=== 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
Argyrios Kyrtzidisd2592a32010-12-22 18:53:44 +000015#include "ExprEngineExperimentalChecks.h"
Argyrios Kyrtzidis98cabba2010-12-22 18:51:49 +000016#include "clang/GR/BugReporter/BugType.h"
17#include "clang/GR/PathSensitive/CheckerVisitor.h"
18#include "clang/GR/PathSensitive/GRState.h"
19#include "clang/GR/PathSensitive/GRStateTrait.h"
20#include "clang/GR/PathSensitive/SymbolManager.h"
Zhongxing Xu589c0f22009-11-12 08:38:56 +000021#include "llvm/ADT/ImmutableMap.h"
22using namespace clang;
Argyrios Kyrtzidis5a4f98f2010-12-22 18:53:20 +000023using namespace GR;
Zhongxing Xu589c0f22009-11-12 08:38:56 +000024
25namespace {
26
Zhongxing Xu7fb14642009-12-11 00:55:44 +000027class RefState {
Ted Kremenekdde201b2010-08-06 21:12:55 +000028 enum Kind { AllocateUnchecked, AllocateFailed, Released, Escaped,
29 Relinquished } K;
Zhongxing Xu243fde92009-11-17 07:54:15 +000030 const Stmt *S;
31
Zhongxing Xu7fb14642009-12-11 00:55:44 +000032public:
Zhongxing Xu243fde92009-11-17 07:54:15 +000033 RefState(Kind k, const Stmt *s) : K(k), S(s) {}
34
Zhongxing Xub94b81a2009-12-31 06:13:07 +000035 bool isAllocated() const { return K == AllocateUnchecked; }
Chris Lattnerfae96222010-09-03 04:34:38 +000036 //bool isFailed() const { return K == AllocateFailed; }
Zhongxing Xu243fde92009-11-17 07:54:15 +000037 bool isReleased() const { return K == Released; }
Chris Lattnerfae96222010-09-03 04:34:38 +000038 //bool isEscaped() const { return K == Escaped; }
39 //bool isRelinquished() const { return K == Relinquished; }
Zhongxing Xu243fde92009-11-17 07:54:15 +000040
41 bool operator==(const RefState &X) const {
42 return K == X.K && S == X.S;
43 }
44
Zhongxing Xub94b81a2009-12-31 06:13:07 +000045 static RefState getAllocateUnchecked(const Stmt *s) {
46 return RefState(AllocateUnchecked, s);
47 }
48 static RefState getAllocateFailed() {
49 return RefState(AllocateFailed, 0);
50 }
Zhongxing Xu243fde92009-11-17 07:54:15 +000051 static RefState getReleased(const Stmt *s) { return RefState(Released, s); }
52 static RefState getEscaped(const Stmt *s) { return RefState(Escaped, s); }
Ted Kremenekdde201b2010-08-06 21:12:55 +000053 static RefState getRelinquished(const Stmt *s) {
54 return RefState(Relinquished, s);
55 }
Zhongxing Xu243fde92009-11-17 07:54:15 +000056
57 void Profile(llvm::FoldingSetNodeID &ID) const {
58 ID.AddInteger(K);
59 ID.AddPointer(S);
60 }
Zhongxing Xu589c0f22009-11-12 08:38:56 +000061};
62
Kovarththanan Rajaratnamba5fb5a2009-11-28 06:07:30 +000063class RegionState {};
Zhongxing Xu589c0f22009-11-12 08:38:56 +000064
Kovarththanan Rajaratnamba5fb5a2009-11-28 06:07:30 +000065class MallocChecker : public CheckerVisitor<MallocChecker> {
Zhongxing Xu589c0f22009-11-12 08:38:56 +000066 BuiltinBug *BT_DoubleFree;
Zhongxing Xufc7ac8f2009-11-13 07:48:11 +000067 BuiltinBug *BT_Leak;
Zhongxing Xuc8023782010-03-10 04:58:55 +000068 BuiltinBug *BT_UseFree;
Ted Kremenekdd0e4902010-07-31 01:52:11 +000069 BuiltinBug *BT_UseRelinquished;
Jordy Rose43859f62010-06-07 19:32:37 +000070 BuiltinBug *BT_BadFree;
Zhongxing Xua5ce9662010-06-01 03:01:33 +000071 IdentifierInfo *II_malloc, *II_free, *II_realloc, *II_calloc;
Zhongxing Xu589c0f22009-11-12 08:38:56 +000072
73public:
Zhongxing Xud9c84c82009-12-12 12:29:38 +000074 MallocChecker()
Ted Kremenekdde201b2010-08-06 21:12:55 +000075 : BT_DoubleFree(0), BT_Leak(0), BT_UseFree(0), BT_UseRelinquished(0),
76 BT_BadFree(0),
Zhongxing Xua5ce9662010-06-01 03:01:33 +000077 II_malloc(0), II_free(0), II_realloc(0), II_calloc(0) {}
Zhongxing Xu589c0f22009-11-12 08:38:56 +000078 static void *getTag();
Ted Kremenek9c149532010-12-01 21:57:22 +000079 bool evalCallExpr(CheckerContext &C, const CallExpr *CE);
80 void evalDeadSymbols(CheckerContext &C, SymbolReaper &SymReaper);
Argyrios Kyrtzidisd2592a32010-12-22 18:53:44 +000081 void evalEndPath(EndPathNodeBuilder &B, void *tag, ExprEngine &Eng);
Zhongxing Xu4985e3e2009-11-17 08:58:18 +000082 void PreVisitReturnStmt(CheckerContext &C, const ReturnStmt *S);
Ted Kremenek9c149532010-12-01 21:57:22 +000083 const GRState *evalAssume(const GRState *state, SVal Cond, bool Assumption,
Jordy Rose72905cf2010-08-04 07:10:57 +000084 bool *respondsToCallback);
Ted Kremenek342e9072010-12-20 21:22:47 +000085 void visitLocation(CheckerContext &C, const Stmt *S, SVal l);
Ted Kremenek79d73042010-09-02 00:56:20 +000086 virtual void PreVisitBind(CheckerContext &C, const Stmt *StoreE,
87 SVal location, SVal val);
Zhongxing Xub94b81a2009-12-31 06:13:07 +000088
Zhongxing Xu7b760962009-11-13 07:25:27 +000089private:
Zhongxing Xu589c0f22009-11-12 08:38:56 +000090 void MallocMem(CheckerContext &C, const CallExpr *CE);
Ted Kremenekdde201b2010-08-06 21:12:55 +000091 void MallocMemReturnsAttr(CheckerContext &C, const CallExpr *CE,
92 const OwnershipAttr* Att);
Zhongxing Xud9c84c82009-12-12 12:29:38 +000093 const GRState *MallocMemAux(CheckerContext &C, const CallExpr *CE,
Zhongxing Xua5ce9662010-06-01 03:01:33 +000094 const Expr *SizeEx, SVal Init,
95 const GRState *state) {
96 return MallocMemAux(C, CE, state->getSVal(SizeEx), Init, state);
97 }
98 const GRState *MallocMemAux(CheckerContext &C, const CallExpr *CE,
99 SVal SizeEx, SVal Init,
100 const GRState *state);
101
Zhongxing Xu589c0f22009-11-12 08:38:56 +0000102 void FreeMem(CheckerContext &C, const CallExpr *CE);
Jordy Rose2a479922010-08-12 08:54:03 +0000103 void FreeMemAttr(CheckerContext &C, const CallExpr *CE,
104 const OwnershipAttr* Att);
Zhongxing Xud9c84c82009-12-12 12:29:38 +0000105 const GRState *FreeMemAux(CheckerContext &C, const CallExpr *CE,
Ted Kremenekdd0e4902010-07-31 01:52:11 +0000106 const GRState *state, unsigned Num, bool Hold);
Zhongxing Xud9c84c82009-12-12 12:29:38 +0000107
108 void ReallocMem(CheckerContext &C, const CallExpr *CE);
Zhongxing Xua5ce9662010-06-01 03:01:33 +0000109 void CallocMem(CheckerContext &C, const CallExpr *CE);
Jordy Rose43859f62010-06-07 19:32:37 +0000110
111 bool SummarizeValue(llvm::raw_ostream& os, SVal V);
112 bool SummarizeRegion(llvm::raw_ostream& os, const MemRegion *MR);
113 void ReportBadFree(CheckerContext &C, SVal ArgVal, SourceRange range);
Zhongxing Xu589c0f22009-11-12 08:38:56 +0000114};
Kovarththanan Rajaratnamba5fb5a2009-11-28 06:07:30 +0000115} // end anonymous namespace
Zhongxing Xu589c0f22009-11-12 08:38:56 +0000116
Zhongxing Xub94b81a2009-12-31 06:13:07 +0000117typedef llvm::ImmutableMap<SymbolRef, RefState> RegionStateTy;
118
Zhongxing Xu589c0f22009-11-12 08:38:56 +0000119namespace clang {
Argyrios Kyrtzidis5a4f98f2010-12-22 18:53:20 +0000120namespace GR {
Zhongxing Xu243fde92009-11-17 07:54:15 +0000121 template <>
Zhongxing Xu589c0f22009-11-12 08:38:56 +0000122 struct GRStateTrait<RegionState>
Jordy Rose09cef092010-08-18 04:26:59 +0000123 : public GRStatePartialTrait<RegionStateTy> {
Zhongxing Xu589c0f22009-11-12 08:38:56 +0000124 static void *GDMIndex() { return MallocChecker::getTag(); }
125 };
126}
Argyrios Kyrtzidis5a4f98f2010-12-22 18:53:20 +0000127}
Zhongxing Xu589c0f22009-11-12 08:38:56 +0000128
Argyrios Kyrtzidisd2592a32010-12-22 18:53:44 +0000129void GR::RegisterMallocChecker(ExprEngine &Eng) {
Zhongxing Xu7b760962009-11-13 07:25:27 +0000130 Eng.registerCheck(new MallocChecker());
131}
132
Zhongxing Xu589c0f22009-11-12 08:38:56 +0000133void *MallocChecker::getTag() {
134 static int x;
135 return &x;
136}
137
Ted Kremenek9c149532010-12-01 21:57:22 +0000138bool MallocChecker::evalCallExpr(CheckerContext &C, const CallExpr *CE) {
Zhongxing Xua49c6b72009-12-11 03:09:01 +0000139 const GRState *state = C.getState();
140 const Expr *Callee = CE->getCallee();
Ted Kremenek13976632010-02-08 16:18:51 +0000141 SVal L = state->getSVal(Callee);
Zhongxing Xua49c6b72009-12-11 03:09:01 +0000142
143 const FunctionDecl *FD = L.getAsFunctionDecl();
Zhongxing Xu589c0f22009-11-12 08:38:56 +0000144 if (!FD)
Zhongxing Xua49c6b72009-12-11 03:09:01 +0000145 return false;
Zhongxing Xu589c0f22009-11-12 08:38:56 +0000146
147 ASTContext &Ctx = C.getASTContext();
148 if (!II_malloc)
149 II_malloc = &Ctx.Idents.get("malloc");
150 if (!II_free)
Zhongxing Xufc7ac8f2009-11-13 07:48:11 +0000151 II_free = &Ctx.Idents.get("free");
Zhongxing Xud9c84c82009-12-12 12:29:38 +0000152 if (!II_realloc)
153 II_realloc = &Ctx.Idents.get("realloc");
Zhongxing Xua5ce9662010-06-01 03:01:33 +0000154 if (!II_calloc)
155 II_calloc = &Ctx.Idents.get("calloc");
Zhongxing Xu589c0f22009-11-12 08:38:56 +0000156
157 if (FD->getIdentifier() == II_malloc) {
158 MallocMem(C, CE);
Zhongxing Xua49c6b72009-12-11 03:09:01 +0000159 return true;
Zhongxing Xu589c0f22009-11-12 08:38:56 +0000160 }
161
162 if (FD->getIdentifier() == II_free) {
163 FreeMem(C, CE);
Zhongxing Xua49c6b72009-12-11 03:09:01 +0000164 return true;
Zhongxing Xu589c0f22009-11-12 08:38:56 +0000165 }
Zhongxing Xua49c6b72009-12-11 03:09:01 +0000166
Zhongxing Xud9c84c82009-12-12 12:29:38 +0000167 if (FD->getIdentifier() == II_realloc) {
168 ReallocMem(C, CE);
169 return true;
170 }
171
Zhongxing Xua5ce9662010-06-01 03:01:33 +0000172 if (FD->getIdentifier() == II_calloc) {
173 CallocMem(C, CE);
174 return true;
175 }
176
Ted Kremenekdd0e4902010-07-31 01:52:11 +0000177 // Check all the attributes, if there are any.
178 // There can be multiple of these attributes.
179 bool rv = false;
180 if (FD->hasAttrs()) {
Sean Huntcf807c42010-08-18 23:23:40 +0000181 for (specific_attr_iterator<OwnershipAttr>
182 i = FD->specific_attr_begin<OwnershipAttr>(),
183 e = FD->specific_attr_end<OwnershipAttr>();
184 i != e; ++i) {
185 switch ((*i)->getOwnKind()) {
186 case OwnershipAttr::Returns: {
187 MallocMemReturnsAttr(C, CE, *i);
Jordy Rose2a479922010-08-12 08:54:03 +0000188 rv = true;
189 break;
Sean Huntcf807c42010-08-18 23:23:40 +0000190 }
191 case OwnershipAttr::Takes:
192 case OwnershipAttr::Holds: {
193 FreeMemAttr(C, CE, *i);
Jordy Rose2a479922010-08-12 08:54:03 +0000194 rv = true;
195 break;
Sean Huntcf807c42010-08-18 23:23:40 +0000196 }
Jordy Rose2a479922010-08-12 08:54:03 +0000197 default:
Jordy Rose2a479922010-08-12 08:54:03 +0000198 break;
Ted Kremenekdd0e4902010-07-31 01:52:11 +0000199 }
200 }
201 }
202 return rv;
Zhongxing Xu589c0f22009-11-12 08:38:56 +0000203}
204
205void MallocChecker::MallocMem(CheckerContext &C, const CallExpr *CE) {
Zhongxing Xua5ce9662010-06-01 03:01:33 +0000206 const GRState *state = MallocMemAux(C, CE, CE->getArg(0), UndefinedVal(),
207 C.getState());
Zhongxing Xud9c84c82009-12-12 12:29:38 +0000208 C.addTransition(state);
209}
210
Ted Kremenekdd0e4902010-07-31 01:52:11 +0000211void MallocChecker::MallocMemReturnsAttr(CheckerContext &C, const CallExpr *CE,
212 const OwnershipAttr* Att) {
Sean Huntcf807c42010-08-18 23:23:40 +0000213 if (Att->getModule() != "malloc")
Ted Kremenekdd0e4902010-07-31 01:52:11 +0000214 return;
215
Sean Huntcf807c42010-08-18 23:23:40 +0000216 OwnershipAttr::args_iterator I = Att->args_begin(), E = Att->args_end();
Ted Kremenekdd0e4902010-07-31 01:52:11 +0000217 if (I != E) {
218 const GRState *state =
219 MallocMemAux(C, CE, CE->getArg(*I), UndefinedVal(), C.getState());
220 C.addTransition(state);
221 return;
222 }
223 const GRState *state = MallocMemAux(C, CE, UnknownVal(), UndefinedVal(),
224 C.getState());
225 C.addTransition(state);
226}
227
Zhongxing Xud9c84c82009-12-12 12:29:38 +0000228const GRState *MallocChecker::MallocMemAux(CheckerContext &C,
229 const CallExpr *CE,
Zhongxing Xua5ce9662010-06-01 03:01:33 +0000230 SVal Size, SVal Init,
Zhongxing Xud9c84c82009-12-12 12:29:38 +0000231 const GRState *state) {
Zhongxing Xua49c6b72009-12-11 03:09:01 +0000232 unsigned Count = C.getNodeBuilder().getCurrentBlockCount();
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000233 SValBuilder &svalBuilder = C.getSValBuilder();
Zhongxing Xua49c6b72009-12-11 03:09:01 +0000234
Jordy Rose32f26562010-07-04 00:00:41 +0000235 // Set the return value.
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000236 SVal retVal = svalBuilder.getConjuredSymbolVal(NULL, CE, CE->getType(), Count);
237 state = state->BindExpr(CE, retVal);
Zhongxing Xua49c6b72009-12-11 03:09:01 +0000238
Jordy Rose32f26562010-07-04 00:00:41 +0000239 // Fill the region with the initialization value.
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000240 state = state->bindDefault(retVal, Init);
Zhongxing Xua5ce9662010-06-01 03:01:33 +0000241
Jordy Rose32f26562010-07-04 00:00:41 +0000242 // Set the region's extent equal to the Size parameter.
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000243 const SymbolicRegion *R = cast<SymbolicRegion>(retVal.getAsRegion());
244 DefinedOrUnknownSVal Extent = R->getExtent(svalBuilder);
Jordy Rose32f26562010-07-04 00:00:41 +0000245 DefinedOrUnknownSVal DefinedSize = cast<DefinedOrUnknownSVal>(Size);
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000246 DefinedOrUnknownSVal extentMatchesSize =
Ted Kremenek9c149532010-12-01 21:57:22 +0000247 svalBuilder.evalEQ(state, Extent, DefinedSize);
Jordy Rose32f26562010-07-04 00:00:41 +0000248
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000249 state = state->assume(extentMatchesSize, true);
250 assert(state);
251
252 SymbolRef Sym = retVal.getAsLocSymbol();
Zhongxing Xu589c0f22009-11-12 08:38:56 +0000253 assert(Sym);
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000254
Zhongxing Xu589c0f22009-11-12 08:38:56 +0000255 // Set the symbol's state to Allocated.
Zhongxing Xub94b81a2009-12-31 06:13:07 +0000256 return state->set<RegionState>(Sym, RefState::getAllocateUnchecked(CE));
Zhongxing Xu589c0f22009-11-12 08:38:56 +0000257}
258
259void MallocChecker::FreeMem(CheckerContext &C, const CallExpr *CE) {
Ted Kremenekdd0e4902010-07-31 01:52:11 +0000260 const GRState *state = FreeMemAux(C, CE, C.getState(), 0, false);
Zhongxing Xud9c84c82009-12-12 12:29:38 +0000261
262 if (state)
263 C.addTransition(state);
264}
265
Ted Kremenekdd0e4902010-07-31 01:52:11 +0000266void MallocChecker::FreeMemAttr(CheckerContext &C, const CallExpr *CE,
Jordy Rose2a479922010-08-12 08:54:03 +0000267 const OwnershipAttr* Att) {
Sean Huntcf807c42010-08-18 23:23:40 +0000268 if (Att->getModule() != "malloc")
Ted Kremenekdd0e4902010-07-31 01:52:11 +0000269 return;
270
Sean Huntcf807c42010-08-18 23:23:40 +0000271 for (OwnershipAttr::args_iterator I = Att->args_begin(), E = Att->args_end();
272 I != E; ++I) {
273 const GRState *state = FreeMemAux(C, CE, C.getState(), *I,
274 Att->getOwnKind() == OwnershipAttr::Holds);
275 if (state)
276 C.addTransition(state);
Ted Kremenekdd0e4902010-07-31 01:52:11 +0000277 }
278}
279
Zhongxing Xud9c84c82009-12-12 12:29:38 +0000280const GRState *MallocChecker::FreeMemAux(CheckerContext &C, const CallExpr *CE,
Ted Kremenekdd0e4902010-07-31 01:52:11 +0000281 const GRState *state, unsigned Num,
282 bool Hold) {
283 const Expr *ArgExpr = CE->getArg(Num);
Jordy Rose43859f62010-06-07 19:32:37 +0000284 SVal ArgVal = state->getSVal(ArgExpr);
Zhongxing Xu181cc3d2010-02-14 06:49:48 +0000285
Ted Kremenekdd0e4902010-07-31 01:52:11 +0000286 DefinedOrUnknownSVal location = cast<DefinedOrUnknownSVal>(ArgVal);
287
288 // Check for null dereferences.
289 if (!isa<Loc>(location))
Zhongxing Xu181cc3d2010-02-14 06:49:48 +0000290 return state;
Ted Kremenekdd0e4902010-07-31 01:52:11 +0000291
292 // FIXME: Technically using 'Assume' here can result in a path
293 // bifurcation. In such cases we need to return two states, not just one.
294 const GRState *notNullState, *nullState;
Ted Kremenek28f47b92010-12-01 22:16:56 +0000295 llvm::tie(notNullState, nullState) = state->assume(location);
Ted Kremenekdd0e4902010-07-31 01:52:11 +0000296
297 // The explicit NULL case, no operation is performed.
298 if (nullState && !notNullState)
299 return nullState;
300
301 assert(notNullState);
302
Jordy Rose43859f62010-06-07 19:32:37 +0000303 // Unknown values could easily be okay
304 // Undefined values are handled elsewhere
305 if (ArgVal.isUnknownOrUndef())
Ted Kremenekdd0e4902010-07-31 01:52:11 +0000306 return notNullState;
Zhongxing Xu589c0f22009-11-12 08:38:56 +0000307
Jordy Rose43859f62010-06-07 19:32:37 +0000308 const MemRegion *R = ArgVal.getAsRegion();
309
310 // Nonlocs can't be freed, of course.
311 // Non-region locations (labels and fixed addresses) also shouldn't be freed.
312 if (!R) {
313 ReportBadFree(C, ArgVal, ArgExpr->getSourceRange());
314 return NULL;
315 }
316
317 R = R->StripCasts();
318
319 // Blocks might show up as heap data, but should not be free()d
320 if (isa<BlockDataRegion>(R)) {
321 ReportBadFree(C, ArgVal, ArgExpr->getSourceRange());
322 return NULL;
323 }
324
325 const MemSpaceRegion *MS = R->getMemorySpace();
326
327 // Parameters, locals, statics, and globals shouldn't be freed.
328 if (!(isa<UnknownSpaceRegion>(MS) || isa<HeapSpaceRegion>(MS))) {
329 // FIXME: at the time this code was written, malloc() regions were
330 // represented by conjured symbols, which are all in UnknownSpaceRegion.
331 // This means that there isn't actually anything from HeapSpaceRegion
332 // that should be freed, even though we allow it here.
333 // Of course, free() can work on memory allocated outside the current
334 // function, so UnknownSpaceRegion is always a possibility.
335 // False negatives are better than false positives.
336
337 ReportBadFree(C, ArgVal, ArgExpr->getSourceRange());
338 return NULL;
339 }
340
341 const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R);
342 // Various cases could lead to non-symbol values here.
343 // For now, ignore them.
344 if (!SR)
Ted Kremenekdd0e4902010-07-31 01:52:11 +0000345 return notNullState;
Jordy Rose43859f62010-06-07 19:32:37 +0000346
347 SymbolRef Sym = SR->getSymbol();
Zhongxing Xu589c0f22009-11-12 08:38:56 +0000348 const RefState *RS = state->get<RegionState>(Sym);
Zhongxing Xu7e3cda92010-01-18 03:27:34 +0000349
350 // If the symbol has not been tracked, return. This is possible when free() is
351 // called on a pointer that does not get its pointee directly from malloc().
352 // Full support of this requires inter-procedural analysis.
353 if (!RS)
Ted Kremenekdd0e4902010-07-31 01:52:11 +0000354 return notNullState;
Zhongxing Xu589c0f22009-11-12 08:38:56 +0000355
356 // Check double free.
Zhongxing Xu243fde92009-11-17 07:54:15 +0000357 if (RS->isReleased()) {
Ted Kremenekd048c6e2010-12-20 21:19:09 +0000358 if (ExplodedNode *N = C.generateSink()) {
Zhongxing Xu589c0f22009-11-12 08:38:56 +0000359 if (!BT_DoubleFree)
Ted Kremenekdd0e4902010-07-31 01:52:11 +0000360 BT_DoubleFree
361 = new BuiltinBug("Double free",
Zhongxing Xu589c0f22009-11-12 08:38:56 +0000362 "Try to free a memory block that has been released");
363 // FIXME: should find where it's freed last time.
364 BugReport *R = new BugReport(*BT_DoubleFree,
Benjamin Kramerd02e2322009-11-14 12:08:24 +0000365 BT_DoubleFree->getDescription(), N);
Zhongxing Xu589c0f22009-11-12 08:38:56 +0000366 C.EmitReport(R);
367 }
Zhongxing Xud9c84c82009-12-12 12:29:38 +0000368 return NULL;
Zhongxing Xu589c0f22009-11-12 08:38:56 +0000369 }
370
371 // Normal free.
Ted Kremenekdd0e4902010-07-31 01:52:11 +0000372 if (Hold)
373 return notNullState->set<RegionState>(Sym, RefState::getRelinquished(CE));
374 return notNullState->set<RegionState>(Sym, RefState::getReleased(CE));
Zhongxing Xud9c84c82009-12-12 12:29:38 +0000375}
376
Jordy Rose43859f62010-06-07 19:32:37 +0000377bool MallocChecker::SummarizeValue(llvm::raw_ostream& os, SVal V) {
378 if (nonloc::ConcreteInt *IntVal = dyn_cast<nonloc::ConcreteInt>(&V))
379 os << "an integer (" << IntVal->getValue() << ")";
380 else if (loc::ConcreteInt *ConstAddr = dyn_cast<loc::ConcreteInt>(&V))
381 os << "a constant address (" << ConstAddr->getValue() << ")";
382 else if (loc::GotoLabel *Label = dyn_cast<loc::GotoLabel>(&V))
383 os << "the address of the label '"
384 << Label->getLabel()->getID()->getName()
385 << "'";
386 else
387 return false;
388
389 return true;
390}
391
392bool MallocChecker::SummarizeRegion(llvm::raw_ostream& os,
393 const MemRegion *MR) {
394 switch (MR->getKind()) {
395 case MemRegion::FunctionTextRegionKind: {
396 const FunctionDecl *FD = cast<FunctionTextRegion>(MR)->getDecl();
397 if (FD)
398 os << "the address of the function '" << FD << "'";
399 else
400 os << "the address of a function";
401 return true;
402 }
403 case MemRegion::BlockTextRegionKind:
404 os << "block text";
405 return true;
406 case MemRegion::BlockDataRegionKind:
407 // FIXME: where the block came from?
408 os << "a block";
409 return true;
410 default: {
411 const MemSpaceRegion *MS = MR->getMemorySpace();
412
413 switch (MS->getKind()) {
414 case MemRegion::StackLocalsSpaceRegionKind: {
415 const VarRegion *VR = dyn_cast<VarRegion>(MR);
416 const VarDecl *VD;
417 if (VR)
418 VD = VR->getDecl();
419 else
420 VD = NULL;
421
422 if (VD)
423 os << "the address of the local variable '" << VD->getName() << "'";
424 else
425 os << "the address of a local stack variable";
426 return true;
427 }
428 case MemRegion::StackArgumentsSpaceRegionKind: {
429 const VarRegion *VR = dyn_cast<VarRegion>(MR);
430 const VarDecl *VD;
431 if (VR)
432 VD = VR->getDecl();
433 else
434 VD = NULL;
435
436 if (VD)
437 os << "the address of the parameter '" << VD->getName() << "'";
438 else
439 os << "the address of a parameter";
440 return true;
441 }
Ted Kremenekdcee3ce2010-07-01 20:16:50 +0000442 case MemRegion::NonStaticGlobalSpaceRegionKind:
443 case MemRegion::StaticGlobalSpaceRegionKind: {
Jordy Rose43859f62010-06-07 19:32:37 +0000444 const VarRegion *VR = dyn_cast<VarRegion>(MR);
445 const VarDecl *VD;
446 if (VR)
447 VD = VR->getDecl();
448 else
449 VD = NULL;
450
451 if (VD) {
452 if (VD->isStaticLocal())
453 os << "the address of the static variable '" << VD->getName() << "'";
454 else
455 os << "the address of the global variable '" << VD->getName() << "'";
456 } else
457 os << "the address of a global variable";
458 return true;
459 }
460 default:
461 return false;
462 }
463 }
464 }
465}
466
467void MallocChecker::ReportBadFree(CheckerContext &C, SVal ArgVal,
468 SourceRange range) {
Ted Kremenekd048c6e2010-12-20 21:19:09 +0000469 if (ExplodedNode *N = C.generateSink()) {
Jordy Rose43859f62010-06-07 19:32:37 +0000470 if (!BT_BadFree)
471 BT_BadFree = new BuiltinBug("Bad free");
472
473 llvm::SmallString<100> buf;
474 llvm::raw_svector_ostream os(buf);
475
476 const MemRegion *MR = ArgVal.getAsRegion();
477 if (MR) {
478 while (const ElementRegion *ER = dyn_cast<ElementRegion>(MR))
479 MR = ER->getSuperRegion();
480
481 // Special case for alloca()
482 if (isa<AllocaRegion>(MR))
483 os << "Argument to free() was allocated by alloca(), not malloc()";
484 else {
485 os << "Argument to free() is ";
486 if (SummarizeRegion(os, MR))
487 os << ", which is not memory allocated by malloc()";
488 else
489 os << "not memory allocated by malloc()";
490 }
491 } else {
492 os << "Argument to free() is ";
493 if (SummarizeValue(os, ArgVal))
494 os << ", which is not memory allocated by malloc()";
495 else
496 os << "not memory allocated by malloc()";
497 }
498
Jordy Rose31041242010-06-08 22:59:01 +0000499 EnhancedBugReport *R = new EnhancedBugReport(*BT_BadFree, os.str(), N);
Jordy Rose43859f62010-06-07 19:32:37 +0000500 R->addRange(range);
501 C.EmitReport(R);
502 }
503}
504
Zhongxing Xud9c84c82009-12-12 12:29:38 +0000505void MallocChecker::ReallocMem(CheckerContext &C, const CallExpr *CE) {
506 const GRState *state = C.getState();
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000507 const Expr *arg0Expr = CE->getArg(0);
508 DefinedOrUnknownSVal arg0Val
509 = cast<DefinedOrUnknownSVal>(state->getSVal(arg0Expr));
Zhongxing Xud9c84c82009-12-12 12:29:38 +0000510
Ted Kremenek846eabd2010-12-01 21:28:31 +0000511 SValBuilder &svalBuilder = C.getSValBuilder();
Zhongxing Xud9c84c82009-12-12 12:29:38 +0000512
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000513 DefinedOrUnknownSVal PtrEQ =
514 svalBuilder.evalEQ(state, arg0Val, svalBuilder.makeNull());
Zhongxing Xud9c84c82009-12-12 12:29:38 +0000515
516 // If the ptr is NULL, the call is equivalent to malloc(size).
Ted Kremenek28f47b92010-12-01 22:16:56 +0000517 if (const GRState *stateEqual = state->assume(PtrEQ, true)) {
Zhongxing Xud9c84c82009-12-12 12:29:38 +0000518 // Hack: set the NULL symbolic region to released to suppress false warning.
519 // In the future we should add more states for allocated regions, e.g.,
520 // CheckedNull, CheckedNonNull.
521
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000522 SymbolRef Sym = arg0Val.getAsLocSymbol();
Zhongxing Xud9c84c82009-12-12 12:29:38 +0000523 if (Sym)
524 stateEqual = stateEqual->set<RegionState>(Sym, RefState::getReleased(CE));
525
Zhongxing Xua5ce9662010-06-01 03:01:33 +0000526 const GRState *stateMalloc = MallocMemAux(C, CE, CE->getArg(1),
527 UndefinedVal(), stateEqual);
Zhongxing Xud9c84c82009-12-12 12:29:38 +0000528 C.addTransition(stateMalloc);
529 }
530
Ted Kremenek28f47b92010-12-01 22:16:56 +0000531 if (const GRState *stateNotEqual = state->assume(PtrEQ, false)) {
Zhongxing Xud9c84c82009-12-12 12:29:38 +0000532 const Expr *Arg1 = CE->getArg(1);
533 DefinedOrUnknownSVal Arg1Val =
Ted Kremenek13976632010-02-08 16:18:51 +0000534 cast<DefinedOrUnknownSVal>(stateNotEqual->getSVal(Arg1));
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000535 DefinedOrUnknownSVal SizeZero =
536 svalBuilder.evalEQ(stateNotEqual, Arg1Val,
537 svalBuilder.makeIntValWithPtrWidth(0, false));
Zhongxing Xud9c84c82009-12-12 12:29:38 +0000538
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000539 if (const GRState *stateSizeZero = stateNotEqual->assume(SizeZero, true))
540 if (const GRState *stateFree = FreeMemAux(C, CE, stateSizeZero, 0, false))
Zhongxing Xud9c84c82009-12-12 12:29:38 +0000541 C.addTransition(stateFree->BindExpr(CE, UndefinedVal(), true));
Zhongxing Xud9c84c82009-12-12 12:29:38 +0000542
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000543 if (const GRState *stateSizeNotZero = stateNotEqual->assume(SizeZero,false))
544 if (const GRState *stateFree = FreeMemAux(C, CE, stateSizeNotZero,
545 0, false)) {
Zhongxing Xud9c84c82009-12-12 12:29:38 +0000546 // FIXME: We should copy the content of the original buffer.
Zhongxing Xu3ed04d32010-01-18 08:54:31 +0000547 const GRState *stateRealloc = MallocMemAux(C, CE, CE->getArg(1),
Zhongxing Xua5ce9662010-06-01 03:01:33 +0000548 UnknownVal(), stateFree);
Zhongxing Xud9c84c82009-12-12 12:29:38 +0000549 C.addTransition(stateRealloc);
550 }
Zhongxing Xud9c84c82009-12-12 12:29:38 +0000551 }
Zhongxing Xu589c0f22009-11-12 08:38:56 +0000552}
Zhongxing Xu7b760962009-11-13 07:25:27 +0000553
Zhongxing Xua5ce9662010-06-01 03:01:33 +0000554void MallocChecker::CallocMem(CheckerContext &C, const CallExpr *CE) {
555 const GRState *state = C.getState();
Ted Kremenek846eabd2010-12-01 21:28:31 +0000556 SValBuilder &svalBuilder = C.getSValBuilder();
Zhongxing Xua5ce9662010-06-01 03:01:33 +0000557
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000558 SVal count = state->getSVal(CE->getArg(0));
559 SVal elementSize = state->getSVal(CE->getArg(1));
560 SVal TotalSize = svalBuilder.evalBinOp(state, BO_Mul, count, elementSize,
561 svalBuilder.getContext().getSizeType());
562 SVal zeroVal = svalBuilder.makeZeroVal(svalBuilder.getContext().CharTy);
Zhongxing Xua5ce9662010-06-01 03:01:33 +0000563
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000564 C.addTransition(MallocMemAux(C, CE, TotalSize, zeroVal, state));
Zhongxing Xua5ce9662010-06-01 03:01:33 +0000565}
566
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000567void MallocChecker::evalDeadSymbols(CheckerContext &C, SymbolReaper &SymReaper)
568{
Zhongxing Xu173ff562010-08-15 08:19:57 +0000569 if (!SymReaper.hasDeadSymbols())
570 return;
Zhongxing Xufc7ac8f2009-11-13 07:48:11 +0000571
Zhongxing Xu173ff562010-08-15 08:19:57 +0000572 const GRState *state = C.getState();
573 RegionStateTy RS = state->get<RegionState>();
Jordy Rose90760142010-08-18 04:33:47 +0000574 RegionStateTy::Factory &F = state->get_context<RegionState>();
Zhongxing Xu173ff562010-08-15 08:19:57 +0000575
576 for (RegionStateTy::iterator I = RS.begin(), E = RS.end(); I != E; ++I) {
577 if (SymReaper.isDead(I->first)) {
578 if (I->second.isAllocated()) {
Ted Kremenekd048c6e2010-12-20 21:19:09 +0000579 if (ExplodedNode *N = C.generateNode()) {
Zhongxing Xu173ff562010-08-15 08:19:57 +0000580 if (!BT_Leak)
581 BT_Leak = new BuiltinBug("Memory leak",
Zhongxing Xufc7ac8f2009-11-13 07:48:11 +0000582 "Allocated memory never released. Potential memory leak.");
Zhongxing Xu173ff562010-08-15 08:19:57 +0000583 // FIXME: where it is allocated.
584 BugReport *R = new BugReport(*BT_Leak, BT_Leak->getDescription(), N);
585 C.EmitReport(R);
586 }
Zhongxing Xufc7ac8f2009-11-13 07:48:11 +0000587 }
Jordy Rose90760142010-08-18 04:33:47 +0000588
589 // Remove the dead symbol from the map.
Ted Kremenek3baf6722010-11-24 00:54:37 +0000590 RS = F.remove(RS, I->first);
Zhongxing Xufc7ac8f2009-11-13 07:48:11 +0000591 }
592 }
Ted Kremenekd048c6e2010-12-20 21:19:09 +0000593 C.generateNode(state->set<RegionState>(RS));
Zhongxing Xu7b760962009-11-13 07:25:27 +0000594}
Zhongxing Xu243fde92009-11-17 07:54:15 +0000595
Argyrios Kyrtzidisd2592a32010-12-22 18:53:44 +0000596void MallocChecker::evalEndPath(EndPathNodeBuilder &B, void *tag,
597 ExprEngine &Eng) {
Zhongxing Xuf605aae2009-11-22 13:22:34 +0000598 SaveAndRestore<bool> OldHasGen(B.HasGeneratedNode);
Zhongxing Xu243fde92009-11-17 07:54:15 +0000599 const GRState *state = B.getState();
Jordy Rose09cef092010-08-18 04:26:59 +0000600 RegionStateTy M = state->get<RegionState>();
Zhongxing Xu243fde92009-11-17 07:54:15 +0000601
Jordy Rose09cef092010-08-18 04:26:59 +0000602 for (RegionStateTy::iterator I = M.begin(), E = M.end(); I != E; ++I) {
Zhongxing Xu243fde92009-11-17 07:54:15 +0000603 RefState RS = I->second;
604 if (RS.isAllocated()) {
605 ExplodedNode *N = B.generateNode(state, tag, B.getPredecessor());
606 if (N) {
607 if (!BT_Leak)
608 BT_Leak = new BuiltinBug("Memory leak",
609 "Allocated memory never released. Potential memory leak.");
610 BugReport *R = new BugReport(*BT_Leak, BT_Leak->getDescription(), N);
611 Eng.getBugReporter().EmitReport(R);
612 }
613 }
614 }
615}
Zhongxing Xu4985e3e2009-11-17 08:58:18 +0000616
617void MallocChecker::PreVisitReturnStmt(CheckerContext &C, const ReturnStmt *S) {
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000618 const Expr *retExpr = S->getRetValue();
619 if (!retExpr)
Zhongxing Xu4985e3e2009-11-17 08:58:18 +0000620 return;
621
622 const GRState *state = C.getState();
623
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000624 SymbolRef Sym = state->getSVal(retExpr).getAsSymbol();
Zhongxing Xu4985e3e2009-11-17 08:58:18 +0000625 if (!Sym)
626 return;
627
628 const RefState *RS = state->get<RegionState>(Sym);
629 if (!RS)
630 return;
631
632 // FIXME: check other cases.
633 if (RS->isAllocated())
634 state = state->set<RegionState>(Sym, RefState::getEscaped(S));
635
Ted Kremenek19d67b52009-11-23 22:22:01 +0000636 C.addTransition(state);
Zhongxing Xu4985e3e2009-11-17 08:58:18 +0000637}
Zhongxing Xub94b81a2009-12-31 06:13:07 +0000638
Ted Kremenek9c149532010-12-01 21:57:22 +0000639const GRState *MallocChecker::evalAssume(const GRState *state, SVal Cond,
Jordy Rose72905cf2010-08-04 07:10:57 +0000640 bool Assumption,
641 bool * /* respondsToCallback */) {
Zhongxing Xub94b81a2009-12-31 06:13:07 +0000642 // If a symblic region is assumed to NULL, set its state to AllocateFailed.
643 // FIXME: should also check symbols assumed to non-null.
644
645 RegionStateTy RS = state->get<RegionState>();
646
647 for (RegionStateTy::iterator I = RS.begin(), E = RS.end(); I != E; ++I) {
648 if (state->getSymVal(I.getKey()))
649 state = state->set<RegionState>(I.getKey(),RefState::getAllocateFailed());
650 }
651
652 return state;
653}
Zhongxing Xuc8023782010-03-10 04:58:55 +0000654
655// Check if the location is a freed symbolic region.
Ted Kremenek342e9072010-12-20 21:22:47 +0000656void MallocChecker::visitLocation(CheckerContext &C, const Stmt *S, SVal l) {
Zhongxing Xuc8023782010-03-10 04:58:55 +0000657 SymbolRef Sym = l.getLocSymbolInBase();
658 if (Sym) {
659 const RefState *RS = C.getState()->get<RegionState>(Sym);
Ted Kremenekcea68652010-08-06 21:12:49 +0000660 if (RS && RS->isReleased()) {
Ted Kremenekd048c6e2010-12-20 21:19:09 +0000661 if (ExplodedNode *N = C.generateNode()) {
Zhongxing Xuc8023782010-03-10 04:58:55 +0000662 if (!BT_UseFree)
663 BT_UseFree = new BuiltinBug("Use dynamically allocated memory after"
664 " it is freed.");
665
666 BugReport *R = new BugReport(*BT_UseFree, BT_UseFree->getDescription(),
667 N);
668 C.EmitReport(R);
669 }
Ted Kremenekcea68652010-08-06 21:12:49 +0000670 }
Zhongxing Xuc8023782010-03-10 04:58:55 +0000671 }
672}
Ted Kremenekdd0e4902010-07-31 01:52:11 +0000673
674void MallocChecker::PreVisitBind(CheckerContext &C,
Ted Kremenekdd0e4902010-07-31 01:52:11 +0000675 const Stmt *StoreE,
676 SVal location,
677 SVal val) {
678 // The PreVisitBind implements the same algorithm as already used by the
679 // Objective C ownership checker: if the pointer escaped from this scope by
680 // assignment, let it go. However, assigning to fields of a stack-storage
681 // structure does not transfer ownership.
682
683 const GRState *state = C.getState();
684 DefinedOrUnknownSVal l = cast<DefinedOrUnknownSVal>(location);
685
686 // Check for null dereferences.
687 if (!isa<Loc>(l))
688 return;
689
690 // Before checking if the state is null, check if 'val' has a RefState.
691 // Only then should we check for null and bifurcate the state.
692 SymbolRef Sym = val.getLocSymbolInBase();
693 if (Sym) {
694 if (const RefState *RS = state->get<RegionState>(Sym)) {
695 // If ptr is NULL, no operation is performed.
696 const GRState *notNullState, *nullState;
Ted Kremenek28f47b92010-12-01 22:16:56 +0000697 llvm::tie(notNullState, nullState) = state->assume(l);
Ted Kremenekdd0e4902010-07-31 01:52:11 +0000698
699 // Generate a transition for 'nullState' to record the assumption
700 // that the state was null.
701 if (nullState)
702 C.addTransition(nullState);
703
704 if (!notNullState)
705 return;
706
707 if (RS->isAllocated()) {
708 // Something we presently own is being assigned somewhere.
709 const MemRegion *AR = location.getAsRegion();
710 if (!AR)
711 return;
712 AR = AR->StripCasts()->getBaseRegion();
713 do {
714 // If it is on the stack, we still own it.
715 if (AR->hasStackNonParametersStorage())
716 break;
717
718 // If the state can't represent this binding, we still own it.
Ted Kremenekdde201b2010-08-06 21:12:55 +0000719 if (notNullState == (notNullState->bindLoc(cast<Loc>(location),
720 UnknownVal())))
Ted Kremenekdd0e4902010-07-31 01:52:11 +0000721 break;
722
723 // We no longer own this pointer.
Ted Kremenekdde201b2010-08-06 21:12:55 +0000724 notNullState =
725 notNullState->set<RegionState>(Sym,
726 RefState::getRelinquished(StoreE));
Ted Kremenekdd0e4902010-07-31 01:52:11 +0000727 }
728 while (false);
729 }
730 C.addTransition(notNullState);
731 }
732 }
733}