blob: 3cc3670645e7c737f99368ab79557ae35adf301d [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
Zhongxing Xu7b760962009-11-13 07:25:27 +000015#include "GRExprEngineExperimentalChecks.h"
Benjamin Kramer5e2d2c22010-03-27 21:19:47 +000016#include "clang/Checker/BugReporter/BugType.h"
Ted Kremenek1309f9a2010-01-25 04:41:41 +000017#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 Xu589c0f22009-11-12 08:38:56 +000021#include "llvm/ADT/ImmutableMap.h"
22using namespace clang;
23
24namespace {
25
Zhongxing Xu7fb14642009-12-11 00:55:44 +000026class RefState {
Ted Kremenekdde201b2010-08-06 21:12:55 +000027 enum Kind { AllocateUnchecked, AllocateFailed, Released, Escaped,
28 Relinquished } K;
Zhongxing Xu243fde92009-11-17 07:54:15 +000029 const Stmt *S;
30
Zhongxing Xu7fb14642009-12-11 00:55:44 +000031public:
Zhongxing Xu243fde92009-11-17 07:54:15 +000032 RefState(Kind k, const Stmt *s) : K(k), S(s) {}
33
Zhongxing Xub94b81a2009-12-31 06:13:07 +000034 bool isAllocated() const { return K == AllocateUnchecked; }
Chris Lattnerfae96222010-09-03 04:34:38 +000035 //bool isFailed() const { return K == AllocateFailed; }
Zhongxing Xu243fde92009-11-17 07:54:15 +000036 bool isReleased() const { return K == Released; }
Chris Lattnerfae96222010-09-03 04:34:38 +000037 //bool isEscaped() const { return K == Escaped; }
38 //bool isRelinquished() const { return K == Relinquished; }
Zhongxing Xu243fde92009-11-17 07:54:15 +000039
40 bool operator==(const RefState &X) const {
41 return K == X.K && S == X.S;
42 }
43
Zhongxing Xub94b81a2009-12-31 06:13:07 +000044 static RefState getAllocateUnchecked(const Stmt *s) {
45 return RefState(AllocateUnchecked, s);
46 }
47 static RefState getAllocateFailed() {
48 return RefState(AllocateFailed, 0);
49 }
Zhongxing Xu243fde92009-11-17 07:54:15 +000050 static RefState getReleased(const Stmt *s) { return RefState(Released, s); }
51 static RefState getEscaped(const Stmt *s) { return RefState(Escaped, s); }
Ted Kremenekdde201b2010-08-06 21:12:55 +000052 static RefState getRelinquished(const Stmt *s) {
53 return RefState(Relinquished, s);
54 }
Zhongxing Xu243fde92009-11-17 07:54:15 +000055
56 void Profile(llvm::FoldingSetNodeID &ID) const {
57 ID.AddInteger(K);
58 ID.AddPointer(S);
59 }
Zhongxing Xu589c0f22009-11-12 08:38:56 +000060};
61
Kovarththanan Rajaratnamba5fb5a2009-11-28 06:07:30 +000062class RegionState {};
Zhongxing Xu589c0f22009-11-12 08:38:56 +000063
Kovarththanan Rajaratnamba5fb5a2009-11-28 06:07:30 +000064class MallocChecker : public CheckerVisitor<MallocChecker> {
Zhongxing Xu589c0f22009-11-12 08:38:56 +000065 BuiltinBug *BT_DoubleFree;
Zhongxing Xufc7ac8f2009-11-13 07:48:11 +000066 BuiltinBug *BT_Leak;
Zhongxing Xuc8023782010-03-10 04:58:55 +000067 BuiltinBug *BT_UseFree;
Ted Kremenekdd0e4902010-07-31 01:52:11 +000068 BuiltinBug *BT_UseRelinquished;
Jordy Rose43859f62010-06-07 19:32:37 +000069 BuiltinBug *BT_BadFree;
Zhongxing Xua5ce9662010-06-01 03:01:33 +000070 IdentifierInfo *II_malloc, *II_free, *II_realloc, *II_calloc;
Zhongxing Xu589c0f22009-11-12 08:38:56 +000071
72public:
Zhongxing Xud9c84c82009-12-12 12:29:38 +000073 MallocChecker()
Ted Kremenekdde201b2010-08-06 21:12:55 +000074 : BT_DoubleFree(0), BT_Leak(0), BT_UseFree(0), BT_UseRelinquished(0),
75 BT_BadFree(0),
Zhongxing Xua5ce9662010-06-01 03:01:33 +000076 II_malloc(0), II_free(0), II_realloc(0), II_calloc(0) {}
Zhongxing Xu589c0f22009-11-12 08:38:56 +000077 static void *getTag();
Ted Kremenek9c149532010-12-01 21:57:22 +000078 bool evalCallExpr(CheckerContext &C, const CallExpr *CE);
79 void evalDeadSymbols(CheckerContext &C, SymbolReaper &SymReaper);
80 void evalEndPath(GREndPathNodeBuilder &B, void *tag, GRExprEngine &Eng);
Zhongxing Xu4985e3e2009-11-17 08:58:18 +000081 void PreVisitReturnStmt(CheckerContext &C, const ReturnStmt *S);
Ted Kremenek9c149532010-12-01 21:57:22 +000082 const GRState *evalAssume(const GRState *state, SVal Cond, bool Assumption,
Jordy Rose72905cf2010-08-04 07:10:57 +000083 bool *respondsToCallback);
Ted Kremenek342e9072010-12-20 21:22:47 +000084 void visitLocation(CheckerContext &C, const Stmt *S, SVal l);
Ted Kremenek79d73042010-09-02 00:56:20 +000085 virtual void PreVisitBind(CheckerContext &C, const Stmt *StoreE,
86 SVal location, SVal val);
Zhongxing Xub94b81a2009-12-31 06:13:07 +000087
Zhongxing Xu7b760962009-11-13 07:25:27 +000088private:
Zhongxing Xu589c0f22009-11-12 08:38:56 +000089 void MallocMem(CheckerContext &C, const CallExpr *CE);
Ted Kremenekdde201b2010-08-06 21:12:55 +000090 void MallocMemReturnsAttr(CheckerContext &C, const CallExpr *CE,
91 const OwnershipAttr* Att);
Zhongxing Xud9c84c82009-12-12 12:29:38 +000092 const GRState *MallocMemAux(CheckerContext &C, const CallExpr *CE,
Zhongxing Xua5ce9662010-06-01 03:01:33 +000093 const Expr *SizeEx, SVal Init,
94 const GRState *state) {
95 return MallocMemAux(C, CE, state->getSVal(SizeEx), Init, state);
96 }
97 const GRState *MallocMemAux(CheckerContext &C, const CallExpr *CE,
98 SVal SizeEx, SVal Init,
99 const GRState *state);
100
Zhongxing Xu589c0f22009-11-12 08:38:56 +0000101 void FreeMem(CheckerContext &C, const CallExpr *CE);
Jordy Rose2a479922010-08-12 08:54:03 +0000102 void FreeMemAttr(CheckerContext &C, const CallExpr *CE,
103 const OwnershipAttr* Att);
Zhongxing Xud9c84c82009-12-12 12:29:38 +0000104 const GRState *FreeMemAux(CheckerContext &C, const CallExpr *CE,
Ted Kremenekdd0e4902010-07-31 01:52:11 +0000105 const GRState *state, unsigned Num, bool Hold);
Zhongxing Xud9c84c82009-12-12 12:29:38 +0000106
107 void ReallocMem(CheckerContext &C, const CallExpr *CE);
Zhongxing Xua5ce9662010-06-01 03:01:33 +0000108 void CallocMem(CheckerContext &C, const CallExpr *CE);
Jordy Rose43859f62010-06-07 19:32:37 +0000109
110 bool SummarizeValue(llvm::raw_ostream& os, SVal V);
111 bool SummarizeRegion(llvm::raw_ostream& os, const MemRegion *MR);
112 void ReportBadFree(CheckerContext &C, SVal ArgVal, SourceRange range);
Zhongxing Xu589c0f22009-11-12 08:38:56 +0000113};
Kovarththanan Rajaratnamba5fb5a2009-11-28 06:07:30 +0000114} // end anonymous namespace
Zhongxing Xu589c0f22009-11-12 08:38:56 +0000115
Zhongxing Xub94b81a2009-12-31 06:13:07 +0000116typedef llvm::ImmutableMap<SymbolRef, RefState> RegionStateTy;
117
Zhongxing Xu589c0f22009-11-12 08:38:56 +0000118namespace clang {
Zhongxing Xu243fde92009-11-17 07:54:15 +0000119 template <>
Zhongxing Xu589c0f22009-11-12 08:38:56 +0000120 struct GRStateTrait<RegionState>
Jordy Rose09cef092010-08-18 04:26:59 +0000121 : public GRStatePartialTrait<RegionStateTy> {
Zhongxing Xu589c0f22009-11-12 08:38:56 +0000122 static void *GDMIndex() { return MallocChecker::getTag(); }
123 };
124}
125
Zhongxing Xu7b760962009-11-13 07:25:27 +0000126void clang::RegisterMallocChecker(GRExprEngine &Eng) {
127 Eng.registerCheck(new MallocChecker());
128}
129
Zhongxing Xu589c0f22009-11-12 08:38:56 +0000130void *MallocChecker::getTag() {
131 static int x;
132 return &x;
133}
134
Ted Kremenek9c149532010-12-01 21:57:22 +0000135bool MallocChecker::evalCallExpr(CheckerContext &C, const CallExpr *CE) {
Zhongxing Xua49c6b72009-12-11 03:09:01 +0000136 const GRState *state = C.getState();
137 const Expr *Callee = CE->getCallee();
Ted Kremenek13976632010-02-08 16:18:51 +0000138 SVal L = state->getSVal(Callee);
Zhongxing Xua49c6b72009-12-11 03:09:01 +0000139
140 const FunctionDecl *FD = L.getAsFunctionDecl();
Zhongxing Xu589c0f22009-11-12 08:38:56 +0000141 if (!FD)
Zhongxing Xua49c6b72009-12-11 03:09:01 +0000142 return false;
Zhongxing Xu589c0f22009-11-12 08:38:56 +0000143
144 ASTContext &Ctx = C.getASTContext();
145 if (!II_malloc)
146 II_malloc = &Ctx.Idents.get("malloc");
147 if (!II_free)
Zhongxing Xufc7ac8f2009-11-13 07:48:11 +0000148 II_free = &Ctx.Idents.get("free");
Zhongxing Xud9c84c82009-12-12 12:29:38 +0000149 if (!II_realloc)
150 II_realloc = &Ctx.Idents.get("realloc");
Zhongxing Xua5ce9662010-06-01 03:01:33 +0000151 if (!II_calloc)
152 II_calloc = &Ctx.Idents.get("calloc");
Zhongxing Xu589c0f22009-11-12 08:38:56 +0000153
154 if (FD->getIdentifier() == II_malloc) {
155 MallocMem(C, CE);
Zhongxing Xua49c6b72009-12-11 03:09:01 +0000156 return true;
Zhongxing Xu589c0f22009-11-12 08:38:56 +0000157 }
158
159 if (FD->getIdentifier() == II_free) {
160 FreeMem(C, CE);
Zhongxing Xua49c6b72009-12-11 03:09:01 +0000161 return true;
Zhongxing Xu589c0f22009-11-12 08:38:56 +0000162 }
Zhongxing Xua49c6b72009-12-11 03:09:01 +0000163
Zhongxing Xud9c84c82009-12-12 12:29:38 +0000164 if (FD->getIdentifier() == II_realloc) {
165 ReallocMem(C, CE);
166 return true;
167 }
168
Zhongxing Xua5ce9662010-06-01 03:01:33 +0000169 if (FD->getIdentifier() == II_calloc) {
170 CallocMem(C, CE);
171 return true;
172 }
173
Ted Kremenekdd0e4902010-07-31 01:52:11 +0000174 // Check all the attributes, if there are any.
175 // There can be multiple of these attributes.
176 bool rv = false;
177 if (FD->hasAttrs()) {
Sean Huntcf807c42010-08-18 23:23:40 +0000178 for (specific_attr_iterator<OwnershipAttr>
179 i = FD->specific_attr_begin<OwnershipAttr>(),
180 e = FD->specific_attr_end<OwnershipAttr>();
181 i != e; ++i) {
182 switch ((*i)->getOwnKind()) {
183 case OwnershipAttr::Returns: {
184 MallocMemReturnsAttr(C, CE, *i);
Jordy Rose2a479922010-08-12 08:54:03 +0000185 rv = true;
186 break;
Sean Huntcf807c42010-08-18 23:23:40 +0000187 }
188 case OwnershipAttr::Takes:
189 case OwnershipAttr::Holds: {
190 FreeMemAttr(C, CE, *i);
Jordy Rose2a479922010-08-12 08:54:03 +0000191 rv = true;
192 break;
Sean Huntcf807c42010-08-18 23:23:40 +0000193 }
Jordy Rose2a479922010-08-12 08:54:03 +0000194 default:
Jordy Rose2a479922010-08-12 08:54:03 +0000195 break;
Ted Kremenekdd0e4902010-07-31 01:52:11 +0000196 }
197 }
198 }
199 return rv;
Zhongxing Xu589c0f22009-11-12 08:38:56 +0000200}
201
202void MallocChecker::MallocMem(CheckerContext &C, const CallExpr *CE) {
Zhongxing Xua5ce9662010-06-01 03:01:33 +0000203 const GRState *state = MallocMemAux(C, CE, CE->getArg(0), UndefinedVal(),
204 C.getState());
Zhongxing Xud9c84c82009-12-12 12:29:38 +0000205 C.addTransition(state);
206}
207
Ted Kremenekdd0e4902010-07-31 01:52:11 +0000208void MallocChecker::MallocMemReturnsAttr(CheckerContext &C, const CallExpr *CE,
209 const OwnershipAttr* Att) {
Sean Huntcf807c42010-08-18 23:23:40 +0000210 if (Att->getModule() != "malloc")
Ted Kremenekdd0e4902010-07-31 01:52:11 +0000211 return;
212
Sean Huntcf807c42010-08-18 23:23:40 +0000213 OwnershipAttr::args_iterator I = Att->args_begin(), E = Att->args_end();
Ted Kremenekdd0e4902010-07-31 01:52:11 +0000214 if (I != E) {
215 const GRState *state =
216 MallocMemAux(C, CE, CE->getArg(*I), UndefinedVal(), C.getState());
217 C.addTransition(state);
218 return;
219 }
220 const GRState *state = MallocMemAux(C, CE, UnknownVal(), UndefinedVal(),
221 C.getState());
222 C.addTransition(state);
223}
224
Zhongxing Xud9c84c82009-12-12 12:29:38 +0000225const GRState *MallocChecker::MallocMemAux(CheckerContext &C,
226 const CallExpr *CE,
Zhongxing Xua5ce9662010-06-01 03:01:33 +0000227 SVal Size, SVal Init,
Zhongxing Xud9c84c82009-12-12 12:29:38 +0000228 const GRState *state) {
Zhongxing Xua49c6b72009-12-11 03:09:01 +0000229 unsigned Count = C.getNodeBuilder().getCurrentBlockCount();
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000230 SValBuilder &svalBuilder = C.getSValBuilder();
Zhongxing Xua49c6b72009-12-11 03:09:01 +0000231
Jordy Rose32f26562010-07-04 00:00:41 +0000232 // Set the return value.
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000233 SVal retVal = svalBuilder.getConjuredSymbolVal(NULL, CE, CE->getType(), Count);
234 state = state->BindExpr(CE, retVal);
Zhongxing Xua49c6b72009-12-11 03:09:01 +0000235
Jordy Rose32f26562010-07-04 00:00:41 +0000236 // Fill the region with the initialization value.
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000237 state = state->bindDefault(retVal, Init);
Zhongxing Xua5ce9662010-06-01 03:01:33 +0000238
Jordy Rose32f26562010-07-04 00:00:41 +0000239 // Set the region's extent equal to the Size parameter.
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000240 const SymbolicRegion *R = cast<SymbolicRegion>(retVal.getAsRegion());
241 DefinedOrUnknownSVal Extent = R->getExtent(svalBuilder);
Jordy Rose32f26562010-07-04 00:00:41 +0000242 DefinedOrUnknownSVal DefinedSize = cast<DefinedOrUnknownSVal>(Size);
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000243 DefinedOrUnknownSVal extentMatchesSize =
Ted Kremenek9c149532010-12-01 21:57:22 +0000244 svalBuilder.evalEQ(state, Extent, DefinedSize);
Jordy Rose32f26562010-07-04 00:00:41 +0000245
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000246 state = state->assume(extentMatchesSize, true);
247 assert(state);
248
249 SymbolRef Sym = retVal.getAsLocSymbol();
Zhongxing Xu589c0f22009-11-12 08:38:56 +0000250 assert(Sym);
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000251
Zhongxing Xu589c0f22009-11-12 08:38:56 +0000252 // Set the symbol's state to Allocated.
Zhongxing Xub94b81a2009-12-31 06:13:07 +0000253 return state->set<RegionState>(Sym, RefState::getAllocateUnchecked(CE));
Zhongxing Xu589c0f22009-11-12 08:38:56 +0000254}
255
256void MallocChecker::FreeMem(CheckerContext &C, const CallExpr *CE) {
Ted Kremenekdd0e4902010-07-31 01:52:11 +0000257 const GRState *state = FreeMemAux(C, CE, C.getState(), 0, false);
Zhongxing Xud9c84c82009-12-12 12:29:38 +0000258
259 if (state)
260 C.addTransition(state);
261}
262
Ted Kremenekdd0e4902010-07-31 01:52:11 +0000263void MallocChecker::FreeMemAttr(CheckerContext &C, const CallExpr *CE,
Jordy Rose2a479922010-08-12 08:54:03 +0000264 const OwnershipAttr* Att) {
Sean Huntcf807c42010-08-18 23:23:40 +0000265 if (Att->getModule() != "malloc")
Ted Kremenekdd0e4902010-07-31 01:52:11 +0000266 return;
267
Sean Huntcf807c42010-08-18 23:23:40 +0000268 for (OwnershipAttr::args_iterator I = Att->args_begin(), E = Att->args_end();
269 I != E; ++I) {
270 const GRState *state = FreeMemAux(C, CE, C.getState(), *I,
271 Att->getOwnKind() == OwnershipAttr::Holds);
272 if (state)
273 C.addTransition(state);
Ted Kremenekdd0e4902010-07-31 01:52:11 +0000274 }
275}
276
Zhongxing Xud9c84c82009-12-12 12:29:38 +0000277const GRState *MallocChecker::FreeMemAux(CheckerContext &C, const CallExpr *CE,
Ted Kremenekdd0e4902010-07-31 01:52:11 +0000278 const GRState *state, unsigned Num,
279 bool Hold) {
280 const Expr *ArgExpr = CE->getArg(Num);
Jordy Rose43859f62010-06-07 19:32:37 +0000281 SVal ArgVal = state->getSVal(ArgExpr);
Zhongxing Xu181cc3d2010-02-14 06:49:48 +0000282
Ted Kremenekdd0e4902010-07-31 01:52:11 +0000283 DefinedOrUnknownSVal location = cast<DefinedOrUnknownSVal>(ArgVal);
284
285 // Check for null dereferences.
286 if (!isa<Loc>(location))
Zhongxing Xu181cc3d2010-02-14 06:49:48 +0000287 return state;
Ted Kremenekdd0e4902010-07-31 01:52:11 +0000288
289 // FIXME: Technically using 'Assume' here can result in a path
290 // bifurcation. In such cases we need to return two states, not just one.
291 const GRState *notNullState, *nullState;
Ted Kremenek28f47b92010-12-01 22:16:56 +0000292 llvm::tie(notNullState, nullState) = state->assume(location);
Ted Kremenekdd0e4902010-07-31 01:52:11 +0000293
294 // The explicit NULL case, no operation is performed.
295 if (nullState && !notNullState)
296 return nullState;
297
298 assert(notNullState);
299
Jordy Rose43859f62010-06-07 19:32:37 +0000300 // Unknown values could easily be okay
301 // Undefined values are handled elsewhere
302 if (ArgVal.isUnknownOrUndef())
Ted Kremenekdd0e4902010-07-31 01:52:11 +0000303 return notNullState;
Zhongxing Xu589c0f22009-11-12 08:38:56 +0000304
Jordy Rose43859f62010-06-07 19:32:37 +0000305 const MemRegion *R = ArgVal.getAsRegion();
306
307 // Nonlocs can't be freed, of course.
308 // Non-region locations (labels and fixed addresses) also shouldn't be freed.
309 if (!R) {
310 ReportBadFree(C, ArgVal, ArgExpr->getSourceRange());
311 return NULL;
312 }
313
314 R = R->StripCasts();
315
316 // Blocks might show up as heap data, but should not be free()d
317 if (isa<BlockDataRegion>(R)) {
318 ReportBadFree(C, ArgVal, ArgExpr->getSourceRange());
319 return NULL;
320 }
321
322 const MemSpaceRegion *MS = R->getMemorySpace();
323
324 // Parameters, locals, statics, and globals shouldn't be freed.
325 if (!(isa<UnknownSpaceRegion>(MS) || isa<HeapSpaceRegion>(MS))) {
326 // FIXME: at the time this code was written, malloc() regions were
327 // represented by conjured symbols, which are all in UnknownSpaceRegion.
328 // This means that there isn't actually anything from HeapSpaceRegion
329 // that should be freed, even though we allow it here.
330 // Of course, free() can work on memory allocated outside the current
331 // function, so UnknownSpaceRegion is always a possibility.
332 // False negatives are better than false positives.
333
334 ReportBadFree(C, ArgVal, ArgExpr->getSourceRange());
335 return NULL;
336 }
337
338 const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R);
339 // Various cases could lead to non-symbol values here.
340 // For now, ignore them.
341 if (!SR)
Ted Kremenekdd0e4902010-07-31 01:52:11 +0000342 return notNullState;
Jordy Rose43859f62010-06-07 19:32:37 +0000343
344 SymbolRef Sym = SR->getSymbol();
Zhongxing Xu589c0f22009-11-12 08:38:56 +0000345 const RefState *RS = state->get<RegionState>(Sym);
Zhongxing Xu7e3cda92010-01-18 03:27:34 +0000346
347 // If the symbol has not been tracked, return. This is possible when free() is
348 // called on a pointer that does not get its pointee directly from malloc().
349 // Full support of this requires inter-procedural analysis.
350 if (!RS)
Ted Kremenekdd0e4902010-07-31 01:52:11 +0000351 return notNullState;
Zhongxing Xu589c0f22009-11-12 08:38:56 +0000352
353 // Check double free.
Zhongxing Xu243fde92009-11-17 07:54:15 +0000354 if (RS->isReleased()) {
Ted Kremenekd048c6e2010-12-20 21:19:09 +0000355 if (ExplodedNode *N = C.generateSink()) {
Zhongxing Xu589c0f22009-11-12 08:38:56 +0000356 if (!BT_DoubleFree)
Ted Kremenekdd0e4902010-07-31 01:52:11 +0000357 BT_DoubleFree
358 = new BuiltinBug("Double free",
Zhongxing Xu589c0f22009-11-12 08:38:56 +0000359 "Try to free a memory block that has been released");
360 // FIXME: should find where it's freed last time.
361 BugReport *R = new BugReport(*BT_DoubleFree,
Benjamin Kramerd02e2322009-11-14 12:08:24 +0000362 BT_DoubleFree->getDescription(), N);
Zhongxing Xu589c0f22009-11-12 08:38:56 +0000363 C.EmitReport(R);
364 }
Zhongxing Xud9c84c82009-12-12 12:29:38 +0000365 return NULL;
Zhongxing Xu589c0f22009-11-12 08:38:56 +0000366 }
367
368 // Normal free.
Ted Kremenekdd0e4902010-07-31 01:52:11 +0000369 if (Hold)
370 return notNullState->set<RegionState>(Sym, RefState::getRelinquished(CE));
371 return notNullState->set<RegionState>(Sym, RefState::getReleased(CE));
Zhongxing Xud9c84c82009-12-12 12:29:38 +0000372}
373
Jordy Rose43859f62010-06-07 19:32:37 +0000374bool MallocChecker::SummarizeValue(llvm::raw_ostream& os, SVal V) {
375 if (nonloc::ConcreteInt *IntVal = dyn_cast<nonloc::ConcreteInt>(&V))
376 os << "an integer (" << IntVal->getValue() << ")";
377 else if (loc::ConcreteInt *ConstAddr = dyn_cast<loc::ConcreteInt>(&V))
378 os << "a constant address (" << ConstAddr->getValue() << ")";
379 else if (loc::GotoLabel *Label = dyn_cast<loc::GotoLabel>(&V))
380 os << "the address of the label '"
381 << Label->getLabel()->getID()->getName()
382 << "'";
383 else
384 return false;
385
386 return true;
387}
388
389bool MallocChecker::SummarizeRegion(llvm::raw_ostream& os,
390 const MemRegion *MR) {
391 switch (MR->getKind()) {
392 case MemRegion::FunctionTextRegionKind: {
393 const FunctionDecl *FD = cast<FunctionTextRegion>(MR)->getDecl();
394 if (FD)
395 os << "the address of the function '" << FD << "'";
396 else
397 os << "the address of a function";
398 return true;
399 }
400 case MemRegion::BlockTextRegionKind:
401 os << "block text";
402 return true;
403 case MemRegion::BlockDataRegionKind:
404 // FIXME: where the block came from?
405 os << "a block";
406 return true;
407 default: {
408 const MemSpaceRegion *MS = MR->getMemorySpace();
409
410 switch (MS->getKind()) {
411 case MemRegion::StackLocalsSpaceRegionKind: {
412 const VarRegion *VR = dyn_cast<VarRegion>(MR);
413 const VarDecl *VD;
414 if (VR)
415 VD = VR->getDecl();
416 else
417 VD = NULL;
418
419 if (VD)
420 os << "the address of the local variable '" << VD->getName() << "'";
421 else
422 os << "the address of a local stack variable";
423 return true;
424 }
425 case MemRegion::StackArgumentsSpaceRegionKind: {
426 const VarRegion *VR = dyn_cast<VarRegion>(MR);
427 const VarDecl *VD;
428 if (VR)
429 VD = VR->getDecl();
430 else
431 VD = NULL;
432
433 if (VD)
434 os << "the address of the parameter '" << VD->getName() << "'";
435 else
436 os << "the address of a parameter";
437 return true;
438 }
Ted Kremenekdcee3ce2010-07-01 20:16:50 +0000439 case MemRegion::NonStaticGlobalSpaceRegionKind:
440 case MemRegion::StaticGlobalSpaceRegionKind: {
Jordy Rose43859f62010-06-07 19:32:37 +0000441 const VarRegion *VR = dyn_cast<VarRegion>(MR);
442 const VarDecl *VD;
443 if (VR)
444 VD = VR->getDecl();
445 else
446 VD = NULL;
447
448 if (VD) {
449 if (VD->isStaticLocal())
450 os << "the address of the static variable '" << VD->getName() << "'";
451 else
452 os << "the address of the global variable '" << VD->getName() << "'";
453 } else
454 os << "the address of a global variable";
455 return true;
456 }
457 default:
458 return false;
459 }
460 }
461 }
462}
463
464void MallocChecker::ReportBadFree(CheckerContext &C, SVal ArgVal,
465 SourceRange range) {
Ted Kremenekd048c6e2010-12-20 21:19:09 +0000466 if (ExplodedNode *N = C.generateSink()) {
Jordy Rose43859f62010-06-07 19:32:37 +0000467 if (!BT_BadFree)
468 BT_BadFree = new BuiltinBug("Bad free");
469
470 llvm::SmallString<100> buf;
471 llvm::raw_svector_ostream os(buf);
472
473 const MemRegion *MR = ArgVal.getAsRegion();
474 if (MR) {
475 while (const ElementRegion *ER = dyn_cast<ElementRegion>(MR))
476 MR = ER->getSuperRegion();
477
478 // Special case for alloca()
479 if (isa<AllocaRegion>(MR))
480 os << "Argument to free() was allocated by alloca(), not malloc()";
481 else {
482 os << "Argument to free() is ";
483 if (SummarizeRegion(os, MR))
484 os << ", which is not memory allocated by malloc()";
485 else
486 os << "not memory allocated by malloc()";
487 }
488 } else {
489 os << "Argument to free() is ";
490 if (SummarizeValue(os, ArgVal))
491 os << ", which is not memory allocated by malloc()";
492 else
493 os << "not memory allocated by malloc()";
494 }
495
Jordy Rose31041242010-06-08 22:59:01 +0000496 EnhancedBugReport *R = new EnhancedBugReport(*BT_BadFree, os.str(), N);
Jordy Rose43859f62010-06-07 19:32:37 +0000497 R->addRange(range);
498 C.EmitReport(R);
499 }
500}
501
Zhongxing Xud9c84c82009-12-12 12:29:38 +0000502void MallocChecker::ReallocMem(CheckerContext &C, const CallExpr *CE) {
503 const GRState *state = C.getState();
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000504 const Expr *arg0Expr = CE->getArg(0);
505 DefinedOrUnknownSVal arg0Val
506 = cast<DefinedOrUnknownSVal>(state->getSVal(arg0Expr));
Zhongxing Xud9c84c82009-12-12 12:29:38 +0000507
Ted Kremenek846eabd2010-12-01 21:28:31 +0000508 SValBuilder &svalBuilder = C.getSValBuilder();
Zhongxing Xud9c84c82009-12-12 12:29:38 +0000509
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000510 DefinedOrUnknownSVal PtrEQ =
511 svalBuilder.evalEQ(state, arg0Val, svalBuilder.makeNull());
Zhongxing Xud9c84c82009-12-12 12:29:38 +0000512
513 // If the ptr is NULL, the call is equivalent to malloc(size).
Ted Kremenek28f47b92010-12-01 22:16:56 +0000514 if (const GRState *stateEqual = state->assume(PtrEQ, true)) {
Zhongxing Xud9c84c82009-12-12 12:29:38 +0000515 // Hack: set the NULL symbolic region to released to suppress false warning.
516 // In the future we should add more states for allocated regions, e.g.,
517 // CheckedNull, CheckedNonNull.
518
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000519 SymbolRef Sym = arg0Val.getAsLocSymbol();
Zhongxing Xud9c84c82009-12-12 12:29:38 +0000520 if (Sym)
521 stateEqual = stateEqual->set<RegionState>(Sym, RefState::getReleased(CE));
522
Zhongxing Xua5ce9662010-06-01 03:01:33 +0000523 const GRState *stateMalloc = MallocMemAux(C, CE, CE->getArg(1),
524 UndefinedVal(), stateEqual);
Zhongxing Xud9c84c82009-12-12 12:29:38 +0000525 C.addTransition(stateMalloc);
526 }
527
Ted Kremenek28f47b92010-12-01 22:16:56 +0000528 if (const GRState *stateNotEqual = state->assume(PtrEQ, false)) {
Zhongxing Xud9c84c82009-12-12 12:29:38 +0000529 const Expr *Arg1 = CE->getArg(1);
530 DefinedOrUnknownSVal Arg1Val =
Ted Kremenek13976632010-02-08 16:18:51 +0000531 cast<DefinedOrUnknownSVal>(stateNotEqual->getSVal(Arg1));
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000532 DefinedOrUnknownSVal SizeZero =
533 svalBuilder.evalEQ(stateNotEqual, Arg1Val,
534 svalBuilder.makeIntValWithPtrWidth(0, false));
Zhongxing Xud9c84c82009-12-12 12:29:38 +0000535
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000536 if (const GRState *stateSizeZero = stateNotEqual->assume(SizeZero, true))
537 if (const GRState *stateFree = FreeMemAux(C, CE, stateSizeZero, 0, false))
Zhongxing Xud9c84c82009-12-12 12:29:38 +0000538 C.addTransition(stateFree->BindExpr(CE, UndefinedVal(), true));
Zhongxing Xud9c84c82009-12-12 12:29:38 +0000539
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000540 if (const GRState *stateSizeNotZero = stateNotEqual->assume(SizeZero,false))
541 if (const GRState *stateFree = FreeMemAux(C, CE, stateSizeNotZero,
542 0, false)) {
Zhongxing Xud9c84c82009-12-12 12:29:38 +0000543 // FIXME: We should copy the content of the original buffer.
Zhongxing Xu3ed04d32010-01-18 08:54:31 +0000544 const GRState *stateRealloc = MallocMemAux(C, CE, CE->getArg(1),
Zhongxing Xua5ce9662010-06-01 03:01:33 +0000545 UnknownVal(), stateFree);
Zhongxing Xud9c84c82009-12-12 12:29:38 +0000546 C.addTransition(stateRealloc);
547 }
Zhongxing Xud9c84c82009-12-12 12:29:38 +0000548 }
Zhongxing Xu589c0f22009-11-12 08:38:56 +0000549}
Zhongxing Xu7b760962009-11-13 07:25:27 +0000550
Zhongxing Xua5ce9662010-06-01 03:01:33 +0000551void MallocChecker::CallocMem(CheckerContext &C, const CallExpr *CE) {
552 const GRState *state = C.getState();
Ted Kremenek846eabd2010-12-01 21:28:31 +0000553 SValBuilder &svalBuilder = C.getSValBuilder();
Zhongxing Xua5ce9662010-06-01 03:01:33 +0000554
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000555 SVal count = state->getSVal(CE->getArg(0));
556 SVal elementSize = state->getSVal(CE->getArg(1));
557 SVal TotalSize = svalBuilder.evalBinOp(state, BO_Mul, count, elementSize,
558 svalBuilder.getContext().getSizeType());
559 SVal zeroVal = svalBuilder.makeZeroVal(svalBuilder.getContext().CharTy);
Zhongxing Xua5ce9662010-06-01 03:01:33 +0000560
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000561 C.addTransition(MallocMemAux(C, CE, TotalSize, zeroVal, state));
Zhongxing Xua5ce9662010-06-01 03:01:33 +0000562}
563
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000564void MallocChecker::evalDeadSymbols(CheckerContext &C, SymbolReaper &SymReaper)
565{
Zhongxing Xu173ff562010-08-15 08:19:57 +0000566 if (!SymReaper.hasDeadSymbols())
567 return;
Zhongxing Xufc7ac8f2009-11-13 07:48:11 +0000568
Zhongxing Xu173ff562010-08-15 08:19:57 +0000569 const GRState *state = C.getState();
570 RegionStateTy RS = state->get<RegionState>();
Jordy Rose90760142010-08-18 04:33:47 +0000571 RegionStateTy::Factory &F = state->get_context<RegionState>();
Zhongxing Xu173ff562010-08-15 08:19:57 +0000572
573 for (RegionStateTy::iterator I = RS.begin(), E = RS.end(); I != E; ++I) {
574 if (SymReaper.isDead(I->first)) {
575 if (I->second.isAllocated()) {
Ted Kremenekd048c6e2010-12-20 21:19:09 +0000576 if (ExplodedNode *N = C.generateNode()) {
Zhongxing Xu173ff562010-08-15 08:19:57 +0000577 if (!BT_Leak)
578 BT_Leak = new BuiltinBug("Memory leak",
Zhongxing Xufc7ac8f2009-11-13 07:48:11 +0000579 "Allocated memory never released. Potential memory leak.");
Zhongxing Xu173ff562010-08-15 08:19:57 +0000580 // FIXME: where it is allocated.
581 BugReport *R = new BugReport(*BT_Leak, BT_Leak->getDescription(), N);
582 C.EmitReport(R);
583 }
Zhongxing Xufc7ac8f2009-11-13 07:48:11 +0000584 }
Jordy Rose90760142010-08-18 04:33:47 +0000585
586 // Remove the dead symbol from the map.
Ted Kremenek3baf6722010-11-24 00:54:37 +0000587 RS = F.remove(RS, I->first);
Zhongxing Xufc7ac8f2009-11-13 07:48:11 +0000588 }
589 }
Ted Kremenekd048c6e2010-12-20 21:19:09 +0000590 C.generateNode(state->set<RegionState>(RS));
Zhongxing Xu7b760962009-11-13 07:25:27 +0000591}
Zhongxing Xu243fde92009-11-17 07:54:15 +0000592
Ted Kremenek9c149532010-12-01 21:57:22 +0000593void MallocChecker::evalEndPath(GREndPathNodeBuilder &B, void *tag,
Zhongxing Xu243fde92009-11-17 07:54:15 +0000594 GRExprEngine &Eng) {
Zhongxing Xuf605aae2009-11-22 13:22:34 +0000595 SaveAndRestore<bool> OldHasGen(B.HasGeneratedNode);
Zhongxing Xu243fde92009-11-17 07:54:15 +0000596 const GRState *state = B.getState();
Jordy Rose09cef092010-08-18 04:26:59 +0000597 RegionStateTy M = state->get<RegionState>();
Zhongxing Xu243fde92009-11-17 07:54:15 +0000598
Jordy Rose09cef092010-08-18 04:26:59 +0000599 for (RegionStateTy::iterator I = M.begin(), E = M.end(); I != E; ++I) {
Zhongxing Xu243fde92009-11-17 07:54:15 +0000600 RefState RS = I->second;
601 if (RS.isAllocated()) {
602 ExplodedNode *N = B.generateNode(state, tag, B.getPredecessor());
603 if (N) {
604 if (!BT_Leak)
605 BT_Leak = new BuiltinBug("Memory leak",
606 "Allocated memory never released. Potential memory leak.");
607 BugReport *R = new BugReport(*BT_Leak, BT_Leak->getDescription(), N);
608 Eng.getBugReporter().EmitReport(R);
609 }
610 }
611 }
612}
Zhongxing Xu4985e3e2009-11-17 08:58:18 +0000613
614void MallocChecker::PreVisitReturnStmt(CheckerContext &C, const ReturnStmt *S) {
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000615 const Expr *retExpr = S->getRetValue();
616 if (!retExpr)
Zhongxing Xu4985e3e2009-11-17 08:58:18 +0000617 return;
618
619 const GRState *state = C.getState();
620
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000621 SymbolRef Sym = state->getSVal(retExpr).getAsSymbol();
Zhongxing Xu4985e3e2009-11-17 08:58:18 +0000622 if (!Sym)
623 return;
624
625 const RefState *RS = state->get<RegionState>(Sym);
626 if (!RS)
627 return;
628
629 // FIXME: check other cases.
630 if (RS->isAllocated())
631 state = state->set<RegionState>(Sym, RefState::getEscaped(S));
632
Ted Kremenek19d67b52009-11-23 22:22:01 +0000633 C.addTransition(state);
Zhongxing Xu4985e3e2009-11-17 08:58:18 +0000634}
Zhongxing Xub94b81a2009-12-31 06:13:07 +0000635
Ted Kremenek9c149532010-12-01 21:57:22 +0000636const GRState *MallocChecker::evalAssume(const GRState *state, SVal Cond,
Jordy Rose72905cf2010-08-04 07:10:57 +0000637 bool Assumption,
638 bool * /* respondsToCallback */) {
Zhongxing Xub94b81a2009-12-31 06:13:07 +0000639 // If a symblic region is assumed to NULL, set its state to AllocateFailed.
640 // FIXME: should also check symbols assumed to non-null.
641
642 RegionStateTy RS = state->get<RegionState>();
643
644 for (RegionStateTy::iterator I = RS.begin(), E = RS.end(); I != E; ++I) {
645 if (state->getSymVal(I.getKey()))
646 state = state->set<RegionState>(I.getKey(),RefState::getAllocateFailed());
647 }
648
649 return state;
650}
Zhongxing Xuc8023782010-03-10 04:58:55 +0000651
652// Check if the location is a freed symbolic region.
Ted Kremenek342e9072010-12-20 21:22:47 +0000653void MallocChecker::visitLocation(CheckerContext &C, const Stmt *S, SVal l) {
Zhongxing Xuc8023782010-03-10 04:58:55 +0000654 SymbolRef Sym = l.getLocSymbolInBase();
655 if (Sym) {
656 const RefState *RS = C.getState()->get<RegionState>(Sym);
Ted Kremenekcea68652010-08-06 21:12:49 +0000657 if (RS && RS->isReleased()) {
Ted Kremenekd048c6e2010-12-20 21:19:09 +0000658 if (ExplodedNode *N = C.generateNode()) {
Zhongxing Xuc8023782010-03-10 04:58:55 +0000659 if (!BT_UseFree)
660 BT_UseFree = new BuiltinBug("Use dynamically allocated memory after"
661 " it is freed.");
662
663 BugReport *R = new BugReport(*BT_UseFree, BT_UseFree->getDescription(),
664 N);
665 C.EmitReport(R);
666 }
Ted Kremenekcea68652010-08-06 21:12:49 +0000667 }
Zhongxing Xuc8023782010-03-10 04:58:55 +0000668 }
669}
Ted Kremenekdd0e4902010-07-31 01:52:11 +0000670
671void MallocChecker::PreVisitBind(CheckerContext &C,
Ted Kremenekdd0e4902010-07-31 01:52:11 +0000672 const Stmt *StoreE,
673 SVal location,
674 SVal val) {
675 // The PreVisitBind implements the same algorithm as already used by the
676 // Objective C ownership checker: if the pointer escaped from this scope by
677 // assignment, let it go. However, assigning to fields of a stack-storage
678 // structure does not transfer ownership.
679
680 const GRState *state = C.getState();
681 DefinedOrUnknownSVal l = cast<DefinedOrUnknownSVal>(location);
682
683 // Check for null dereferences.
684 if (!isa<Loc>(l))
685 return;
686
687 // Before checking if the state is null, check if 'val' has a RefState.
688 // Only then should we check for null and bifurcate the state.
689 SymbolRef Sym = val.getLocSymbolInBase();
690 if (Sym) {
691 if (const RefState *RS = state->get<RegionState>(Sym)) {
692 // If ptr is NULL, no operation is performed.
693 const GRState *notNullState, *nullState;
Ted Kremenek28f47b92010-12-01 22:16:56 +0000694 llvm::tie(notNullState, nullState) = state->assume(l);
Ted Kremenekdd0e4902010-07-31 01:52:11 +0000695
696 // Generate a transition for 'nullState' to record the assumption
697 // that the state was null.
698 if (nullState)
699 C.addTransition(nullState);
700
701 if (!notNullState)
702 return;
703
704 if (RS->isAllocated()) {
705 // Something we presently own is being assigned somewhere.
706 const MemRegion *AR = location.getAsRegion();
707 if (!AR)
708 return;
709 AR = AR->StripCasts()->getBaseRegion();
710 do {
711 // If it is on the stack, we still own it.
712 if (AR->hasStackNonParametersStorage())
713 break;
714
715 // If the state can't represent this binding, we still own it.
Ted Kremenekdde201b2010-08-06 21:12:55 +0000716 if (notNullState == (notNullState->bindLoc(cast<Loc>(location),
717 UnknownVal())))
Ted Kremenekdd0e4902010-07-31 01:52:11 +0000718 break;
719
720 // We no longer own this pointer.
Ted Kremenekdde201b2010-08-06 21:12:55 +0000721 notNullState =
722 notNullState->set<RegionState>(Sym,
723 RefState::getRelinquished(StoreE));
Ted Kremenekdd0e4902010-07-31 01:52:11 +0000724 }
725 while (false);
726 }
727 C.addTransition(notNullState);
728 }
729 }
730}