File: | build/llvm-toolchain-snapshot-15~++20220420111733+e13d2efed663/clang/lib/StaticAnalyzer/Checkers/CStringChecker.cpp |
Warning: | line 1490, column 17 Called C++ object pointer is null |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
1 | //= CStringChecker.cpp - Checks calls to C string functions --------*- C++ -*-// | ||||||
2 | // | ||||||
3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. | ||||||
4 | // See https://llvm.org/LICENSE.txt for license information. | ||||||
5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception | ||||||
6 | // | ||||||
7 | //===----------------------------------------------------------------------===// | ||||||
8 | // | ||||||
9 | // This defines CStringChecker, which is an assortment of checks on calls | ||||||
10 | // to functions in <string.h>. | ||||||
11 | // | ||||||
12 | //===----------------------------------------------------------------------===// | ||||||
13 | |||||||
14 | #include "InterCheckerAPI.h" | ||||||
15 | #include "clang/Basic/CharInfo.h" | ||||||
16 | #include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h" | ||||||
17 | #include "clang/StaticAnalyzer/Core/BugReporter/BugType.h" | ||||||
18 | #include "clang/StaticAnalyzer/Core/Checker.h" | ||||||
19 | #include "clang/StaticAnalyzer/Core/CheckerManager.h" | ||||||
20 | #include "clang/StaticAnalyzer/Core/PathSensitive/CallDescription.h" | ||||||
21 | #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h" | ||||||
22 | #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h" | ||||||
23 | #include "clang/StaticAnalyzer/Core/PathSensitive/DynamicExtent.h" | ||||||
24 | #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h" | ||||||
25 | #include "llvm/ADT/STLExtras.h" | ||||||
26 | #include "llvm/ADT/SmallString.h" | ||||||
27 | #include "llvm/ADT/StringExtras.h" | ||||||
28 | #include "llvm/Support/raw_ostream.h" | ||||||
29 | |||||||
30 | using namespace clang; | ||||||
31 | using namespace ento; | ||||||
32 | |||||||
33 | namespace { | ||||||
34 | struct AnyArgExpr { | ||||||
35 | // FIXME: Remove constructor in C++17 to turn it into an aggregate. | ||||||
36 | AnyArgExpr(const Expr *Expression, unsigned ArgumentIndex) | ||||||
37 | : Expression{Expression}, ArgumentIndex{ArgumentIndex} {} | ||||||
38 | const Expr *Expression; | ||||||
39 | unsigned ArgumentIndex; | ||||||
40 | }; | ||||||
41 | |||||||
42 | struct SourceArgExpr : AnyArgExpr { | ||||||
43 | using AnyArgExpr::AnyArgExpr; // FIXME: Remove using in C++17. | ||||||
44 | }; | ||||||
45 | |||||||
46 | struct DestinationArgExpr : AnyArgExpr { | ||||||
47 | using AnyArgExpr::AnyArgExpr; // FIXME: Same. | ||||||
48 | }; | ||||||
49 | |||||||
50 | struct SizeArgExpr : AnyArgExpr { | ||||||
51 | using AnyArgExpr::AnyArgExpr; // FIXME: Same. | ||||||
52 | }; | ||||||
53 | |||||||
54 | using ErrorMessage = SmallString<128>; | ||||||
55 | enum class AccessKind { write, read }; | ||||||
56 | |||||||
57 | static ErrorMessage createOutOfBoundErrorMsg(StringRef FunctionDescription, | ||||||
58 | AccessKind Access) { | ||||||
59 | ErrorMessage Message; | ||||||
60 | llvm::raw_svector_ostream Os(Message); | ||||||
61 | |||||||
62 | // Function classification like: Memory copy function | ||||||
63 | Os << toUppercase(FunctionDescription.front()) | ||||||
64 | << &FunctionDescription.data()[1]; | ||||||
65 | |||||||
66 | if (Access == AccessKind::write) { | ||||||
67 | Os << " overflows the destination buffer"; | ||||||
68 | } else { // read access | ||||||
69 | Os << " accesses out-of-bound array element"; | ||||||
70 | } | ||||||
71 | |||||||
72 | return Message; | ||||||
73 | } | ||||||
74 | |||||||
75 | enum class ConcatFnKind { none = 0, strcat = 1, strlcat = 2 }; | ||||||
76 | class CStringChecker : public Checker< eval::Call, | ||||||
77 | check::PreStmt<DeclStmt>, | ||||||
78 | check::LiveSymbols, | ||||||
79 | check::DeadSymbols, | ||||||
80 | check::RegionChanges | ||||||
81 | > { | ||||||
82 | mutable std::unique_ptr<BugType> BT_Null, BT_Bounds, BT_Overlap, | ||||||
83 | BT_NotCString, BT_AdditionOverflow, BT_UninitRead; | ||||||
84 | |||||||
85 | mutable const char *CurrentFunctionDescription; | ||||||
86 | |||||||
87 | public: | ||||||
88 | /// The filter is used to filter out the diagnostics which are not enabled by | ||||||
89 | /// the user. | ||||||
90 | struct CStringChecksFilter { | ||||||
91 | DefaultBool CheckCStringNullArg; | ||||||
92 | DefaultBool CheckCStringOutOfBounds; | ||||||
93 | DefaultBool CheckCStringBufferOverlap; | ||||||
94 | DefaultBool CheckCStringNotNullTerm; | ||||||
95 | DefaultBool CheckCStringUninitializedRead; | ||||||
96 | |||||||
97 | CheckerNameRef CheckNameCStringNullArg; | ||||||
98 | CheckerNameRef CheckNameCStringOutOfBounds; | ||||||
99 | CheckerNameRef CheckNameCStringBufferOverlap; | ||||||
100 | CheckerNameRef CheckNameCStringNotNullTerm; | ||||||
101 | CheckerNameRef CheckNameCStringUninitializedRead; | ||||||
102 | }; | ||||||
103 | |||||||
104 | CStringChecksFilter Filter; | ||||||
105 | |||||||
106 | static void *getTag() { static int tag; return &tag; } | ||||||
107 | |||||||
108 | bool evalCall(const CallEvent &Call, CheckerContext &C) const; | ||||||
109 | void checkPreStmt(const DeclStmt *DS, CheckerContext &C) const; | ||||||
110 | void checkLiveSymbols(ProgramStateRef state, SymbolReaper &SR) const; | ||||||
111 | void checkDeadSymbols(SymbolReaper &SR, CheckerContext &C) const; | ||||||
112 | |||||||
113 | ProgramStateRef | ||||||
114 | checkRegionChanges(ProgramStateRef state, | ||||||
115 | const InvalidatedSymbols *, | ||||||
116 | ArrayRef<const MemRegion *> ExplicitRegions, | ||||||
117 | ArrayRef<const MemRegion *> Regions, | ||||||
118 | const LocationContext *LCtx, | ||||||
119 | const CallEvent *Call) const; | ||||||
120 | |||||||
121 | typedef void (CStringChecker::*FnCheck)(CheckerContext &, | ||||||
122 | const CallExpr *) const; | ||||||
123 | CallDescriptionMap<FnCheck> Callbacks = { | ||||||
124 | {{CDF_MaybeBuiltin, "memcpy", 3}, &CStringChecker::evalMemcpy}, | ||||||
125 | {{CDF_MaybeBuiltin, "mempcpy", 3}, &CStringChecker::evalMempcpy}, | ||||||
126 | {{CDF_MaybeBuiltin, "memcmp", 3}, &CStringChecker::evalMemcmp}, | ||||||
127 | {{CDF_MaybeBuiltin, "memmove", 3}, &CStringChecker::evalMemmove}, | ||||||
128 | {{CDF_MaybeBuiltin, "memset", 3}, &CStringChecker::evalMemset}, | ||||||
129 | {{CDF_MaybeBuiltin, "explicit_memset", 3}, &CStringChecker::evalMemset}, | ||||||
130 | {{CDF_MaybeBuiltin, "strcpy", 2}, &CStringChecker::evalStrcpy}, | ||||||
131 | {{CDF_MaybeBuiltin, "strncpy", 3}, &CStringChecker::evalStrncpy}, | ||||||
132 | {{CDF_MaybeBuiltin, "stpcpy", 2}, &CStringChecker::evalStpcpy}, | ||||||
133 | {{CDF_MaybeBuiltin, "strlcpy", 3}, &CStringChecker::evalStrlcpy}, | ||||||
134 | {{CDF_MaybeBuiltin, "strcat", 2}, &CStringChecker::evalStrcat}, | ||||||
135 | {{CDF_MaybeBuiltin, "strncat", 3}, &CStringChecker::evalStrncat}, | ||||||
136 | {{CDF_MaybeBuiltin, "strlcat", 3}, &CStringChecker::evalStrlcat}, | ||||||
137 | {{CDF_MaybeBuiltin, "strlen", 1}, &CStringChecker::evalstrLength}, | ||||||
138 | {{CDF_MaybeBuiltin, "strnlen", 2}, &CStringChecker::evalstrnLength}, | ||||||
139 | {{CDF_MaybeBuiltin, "strcmp", 2}, &CStringChecker::evalStrcmp}, | ||||||
140 | {{CDF_MaybeBuiltin, "strncmp", 3}, &CStringChecker::evalStrncmp}, | ||||||
141 | {{CDF_MaybeBuiltin, "strcasecmp", 2}, &CStringChecker::evalStrcasecmp}, | ||||||
142 | {{CDF_MaybeBuiltin, "strncasecmp", 3}, &CStringChecker::evalStrncasecmp}, | ||||||
143 | {{CDF_MaybeBuiltin, "strsep", 2}, &CStringChecker::evalStrsep}, | ||||||
144 | {{CDF_MaybeBuiltin, "bcopy", 3}, &CStringChecker::evalBcopy}, | ||||||
145 | {{CDF_MaybeBuiltin, "bcmp", 3}, &CStringChecker::evalMemcmp}, | ||||||
146 | {{CDF_MaybeBuiltin, "bzero", 2}, &CStringChecker::evalBzero}, | ||||||
147 | {{CDF_MaybeBuiltin, "explicit_bzero", 2}, &CStringChecker::evalBzero}, | ||||||
148 | }; | ||||||
149 | |||||||
150 | // These require a bit of special handling. | ||||||
151 | CallDescription StdCopy{{"std", "copy"}, 3}, | ||||||
152 | StdCopyBackward{{"std", "copy_backward"}, 3}; | ||||||
153 | |||||||
154 | FnCheck identifyCall(const CallEvent &Call, CheckerContext &C) const; | ||||||
155 | void evalMemcpy(CheckerContext &C, const CallExpr *CE) const; | ||||||
156 | void evalMempcpy(CheckerContext &C, const CallExpr *CE) const; | ||||||
157 | void evalMemmove(CheckerContext &C, const CallExpr *CE) const; | ||||||
158 | void evalBcopy(CheckerContext &C, const CallExpr *CE) const; | ||||||
159 | void evalCopyCommon(CheckerContext &C, const CallExpr *CE, | ||||||
160 | ProgramStateRef state, SizeArgExpr Size, | ||||||
161 | DestinationArgExpr Dest, SourceArgExpr Source, | ||||||
162 | bool Restricted, bool IsMempcpy) const; | ||||||
163 | |||||||
164 | void evalMemcmp(CheckerContext &C, const CallExpr *CE) const; | ||||||
165 | |||||||
166 | void evalstrLength(CheckerContext &C, const CallExpr *CE) const; | ||||||
167 | void evalstrnLength(CheckerContext &C, const CallExpr *CE) const; | ||||||
168 | void evalstrLengthCommon(CheckerContext &C, | ||||||
169 | const CallExpr *CE, | ||||||
170 | bool IsStrnlen = false) const; | ||||||
171 | |||||||
172 | void evalStrcpy(CheckerContext &C, const CallExpr *CE) const; | ||||||
173 | void evalStrncpy(CheckerContext &C, const CallExpr *CE) const; | ||||||
174 | void evalStpcpy(CheckerContext &C, const CallExpr *CE) const; | ||||||
175 | void evalStrlcpy(CheckerContext &C, const CallExpr *CE) const; | ||||||
176 | void evalStrcpyCommon(CheckerContext &C, const CallExpr *CE, bool ReturnEnd, | ||||||
177 | bool IsBounded, ConcatFnKind appendK, | ||||||
178 | bool returnPtr = true) const; | ||||||
179 | |||||||
180 | void evalStrcat(CheckerContext &C, const CallExpr *CE) const; | ||||||
181 | void evalStrncat(CheckerContext &C, const CallExpr *CE) const; | ||||||
182 | void evalStrlcat(CheckerContext &C, const CallExpr *CE) const; | ||||||
183 | |||||||
184 | void evalStrcmp(CheckerContext &C, const CallExpr *CE) const; | ||||||
185 | void evalStrncmp(CheckerContext &C, const CallExpr *CE) const; | ||||||
186 | void evalStrcasecmp(CheckerContext &C, const CallExpr *CE) const; | ||||||
187 | void evalStrncasecmp(CheckerContext &C, const CallExpr *CE) const; | ||||||
188 | void evalStrcmpCommon(CheckerContext &C, | ||||||
189 | const CallExpr *CE, | ||||||
190 | bool IsBounded = false, | ||||||
191 | bool IgnoreCase = false) const; | ||||||
192 | |||||||
193 | void evalStrsep(CheckerContext &C, const CallExpr *CE) const; | ||||||
194 | |||||||
195 | void evalStdCopy(CheckerContext &C, const CallExpr *CE) const; | ||||||
196 | void evalStdCopyBackward(CheckerContext &C, const CallExpr *CE) const; | ||||||
197 | void evalStdCopyCommon(CheckerContext &C, const CallExpr *CE) const; | ||||||
198 | void evalMemset(CheckerContext &C, const CallExpr *CE) const; | ||||||
199 | void evalBzero(CheckerContext &C, const CallExpr *CE) const; | ||||||
200 | |||||||
201 | // Utility methods | ||||||
202 | std::pair<ProgramStateRef , ProgramStateRef > | ||||||
203 | static assumeZero(CheckerContext &C, | ||||||
204 | ProgramStateRef state, SVal V, QualType Ty); | ||||||
205 | |||||||
206 | static ProgramStateRef setCStringLength(ProgramStateRef state, | ||||||
207 | const MemRegion *MR, | ||||||
208 | SVal strLength); | ||||||
209 | static SVal getCStringLengthForRegion(CheckerContext &C, | ||||||
210 | ProgramStateRef &state, | ||||||
211 | const Expr *Ex, | ||||||
212 | const MemRegion *MR, | ||||||
213 | bool hypothetical); | ||||||
214 | SVal getCStringLength(CheckerContext &C, | ||||||
215 | ProgramStateRef &state, | ||||||
216 | const Expr *Ex, | ||||||
217 | SVal Buf, | ||||||
218 | bool hypothetical = false) const; | ||||||
219 | |||||||
220 | const StringLiteral *getCStringLiteral(CheckerContext &C, | ||||||
221 | ProgramStateRef &state, | ||||||
222 | const Expr *expr, | ||||||
223 | SVal val) const; | ||||||
224 | |||||||
225 | static ProgramStateRef InvalidateBuffer(CheckerContext &C, | ||||||
226 | ProgramStateRef state, | ||||||
227 | const Expr *Ex, SVal V, | ||||||
228 | bool IsSourceBuffer, | ||||||
229 | const Expr *Size); | ||||||
230 | |||||||
231 | static bool SummarizeRegion(raw_ostream &os, ASTContext &Ctx, | ||||||
232 | const MemRegion *MR); | ||||||
233 | |||||||
234 | static bool memsetAux(const Expr *DstBuffer, SVal CharE, | ||||||
235 | const Expr *Size, CheckerContext &C, | ||||||
236 | ProgramStateRef &State); | ||||||
237 | |||||||
238 | // Re-usable checks | ||||||
239 | ProgramStateRef checkNonNull(CheckerContext &C, ProgramStateRef State, | ||||||
240 | AnyArgExpr Arg, SVal l) const; | ||||||
241 | ProgramStateRef CheckLocation(CheckerContext &C, ProgramStateRef state, | ||||||
242 | AnyArgExpr Buffer, SVal Element, | ||||||
243 | AccessKind Access) const; | ||||||
244 | ProgramStateRef CheckBufferAccess(CheckerContext &C, ProgramStateRef State, | ||||||
245 | AnyArgExpr Buffer, SizeArgExpr Size, | ||||||
246 | AccessKind Access) const; | ||||||
247 | ProgramStateRef CheckOverlap(CheckerContext &C, ProgramStateRef state, | ||||||
248 | SizeArgExpr Size, AnyArgExpr First, | ||||||
249 | AnyArgExpr Second) const; | ||||||
250 | void emitOverlapBug(CheckerContext &C, | ||||||
251 | ProgramStateRef state, | ||||||
252 | const Stmt *First, | ||||||
253 | const Stmt *Second) const; | ||||||
254 | |||||||
255 | void emitNullArgBug(CheckerContext &C, ProgramStateRef State, const Stmt *S, | ||||||
256 | StringRef WarningMsg) const; | ||||||
257 | void emitOutOfBoundsBug(CheckerContext &C, ProgramStateRef State, | ||||||
258 | const Stmt *S, StringRef WarningMsg) const; | ||||||
259 | void emitNotCStringBug(CheckerContext &C, ProgramStateRef State, | ||||||
260 | const Stmt *S, StringRef WarningMsg) const; | ||||||
261 | void emitAdditionOverflowBug(CheckerContext &C, ProgramStateRef State) const; | ||||||
262 | void emitUninitializedReadBug(CheckerContext &C, ProgramStateRef State, | ||||||
263 | const Expr *E) const; | ||||||
264 | ProgramStateRef checkAdditionOverflow(CheckerContext &C, | ||||||
265 | ProgramStateRef state, | ||||||
266 | NonLoc left, | ||||||
267 | NonLoc right) const; | ||||||
268 | |||||||
269 | // Return true if the destination buffer of the copy function may be in bound. | ||||||
270 | // Expects SVal of Size to be positive and unsigned. | ||||||
271 | // Expects SVal of FirstBuf to be a FieldRegion. | ||||||
272 | static bool IsFirstBufInBound(CheckerContext &C, | ||||||
273 | ProgramStateRef state, | ||||||
274 | const Expr *FirstBuf, | ||||||
275 | const Expr *Size); | ||||||
276 | }; | ||||||
277 | |||||||
278 | } //end anonymous namespace | ||||||
279 | |||||||
280 | REGISTER_MAP_WITH_PROGRAMSTATE(CStringLength, const MemRegion *, SVal)namespace { class CStringLength {}; using CStringLengthTy = llvm ::ImmutableMap<const MemRegion *, SVal>; } namespace clang { namespace ento { template <> struct ProgramStateTrait <CStringLength> : public ProgramStatePartialTrait<CStringLengthTy > { static void *GDMIndex() { static int Index; return & Index; } }; } } | ||||||
281 | |||||||
282 | //===----------------------------------------------------------------------===// | ||||||
283 | // Individual checks and utility methods. | ||||||
284 | //===----------------------------------------------------------------------===// | ||||||
285 | |||||||
286 | std::pair<ProgramStateRef , ProgramStateRef > | ||||||
287 | CStringChecker::assumeZero(CheckerContext &C, ProgramStateRef state, SVal V, | ||||||
288 | QualType Ty) { | ||||||
289 | Optional<DefinedSVal> val = V.getAs<DefinedSVal>(); | ||||||
290 | if (!val) | ||||||
291 | return std::pair<ProgramStateRef , ProgramStateRef >(state, state); | ||||||
292 | |||||||
293 | SValBuilder &svalBuilder = C.getSValBuilder(); | ||||||
294 | DefinedOrUnknownSVal zero = svalBuilder.makeZeroVal(Ty); | ||||||
295 | return state->assume(svalBuilder.evalEQ(state, *val, zero)); | ||||||
296 | } | ||||||
297 | |||||||
298 | ProgramStateRef CStringChecker::checkNonNull(CheckerContext &C, | ||||||
299 | ProgramStateRef State, | ||||||
300 | AnyArgExpr Arg, SVal l) const { | ||||||
301 | // If a previous check has failed, propagate the failure. | ||||||
302 | if (!State) | ||||||
303 | return nullptr; | ||||||
304 | |||||||
305 | ProgramStateRef stateNull, stateNonNull; | ||||||
306 | std::tie(stateNull, stateNonNull) = | ||||||
307 | assumeZero(C, State, l, Arg.Expression->getType()); | ||||||
308 | |||||||
309 | if (stateNull && !stateNonNull) { | ||||||
310 | if (Filter.CheckCStringNullArg) { | ||||||
311 | SmallString<80> buf; | ||||||
312 | llvm::raw_svector_ostream OS(buf); | ||||||
313 | assert(CurrentFunctionDescription)(static_cast <bool> (CurrentFunctionDescription) ? void (0) : __assert_fail ("CurrentFunctionDescription", "clang/lib/StaticAnalyzer/Checkers/CStringChecker.cpp" , 313, __extension__ __PRETTY_FUNCTION__)); | ||||||
314 | OS << "Null pointer passed as " << (Arg.ArgumentIndex + 1) | ||||||
315 | << llvm::getOrdinalSuffix(Arg.ArgumentIndex + 1) << " argument to " | ||||||
316 | << CurrentFunctionDescription; | ||||||
317 | |||||||
318 | emitNullArgBug(C, stateNull, Arg.Expression, OS.str()); | ||||||
319 | } | ||||||
320 | return nullptr; | ||||||
321 | } | ||||||
322 | |||||||
323 | // From here on, assume that the value is non-null. | ||||||
324 | assert(stateNonNull)(static_cast <bool> (stateNonNull) ? void (0) : __assert_fail ("stateNonNull", "clang/lib/StaticAnalyzer/Checkers/CStringChecker.cpp" , 324, __extension__ __PRETTY_FUNCTION__)); | ||||||
325 | return stateNonNull; | ||||||
326 | } | ||||||
327 | |||||||
328 | // FIXME: This was originally copied from ArrayBoundChecker.cpp. Refactor? | ||||||
329 | ProgramStateRef CStringChecker::CheckLocation(CheckerContext &C, | ||||||
330 | ProgramStateRef state, | ||||||
331 | AnyArgExpr Buffer, SVal Element, | ||||||
332 | AccessKind Access) const { | ||||||
333 | |||||||
334 | // If a previous check has failed, propagate the failure. | ||||||
335 | if (!state) | ||||||
336 | return nullptr; | ||||||
337 | |||||||
338 | // Check for out of bound array element access. | ||||||
339 | const MemRegion *R = Element.getAsRegion(); | ||||||
340 | if (!R) | ||||||
341 | return state; | ||||||
342 | |||||||
343 | const auto *ER = dyn_cast<ElementRegion>(R); | ||||||
344 | if (!ER) | ||||||
345 | return state; | ||||||
346 | |||||||
347 | if (ER->getValueType() != C.getASTContext().CharTy) | ||||||
348 | return state; | ||||||
349 | |||||||
350 | // Get the size of the array. | ||||||
351 | const auto *superReg = cast<SubRegion>(ER->getSuperRegion()); | ||||||
352 | DefinedOrUnknownSVal Size = | ||||||
353 | getDynamicExtent(state, superReg, C.getSValBuilder()); | ||||||
354 | |||||||
355 | // Get the index of the accessed element. | ||||||
356 | DefinedOrUnknownSVal Idx = ER->getIndex().castAs<DefinedOrUnknownSVal>(); | ||||||
357 | |||||||
358 | ProgramStateRef StInBound = state->assumeInBound(Idx, Size, true); | ||||||
359 | ProgramStateRef StOutBound = state->assumeInBound(Idx, Size, false); | ||||||
360 | if (StOutBound && !StInBound) { | ||||||
361 | // These checks are either enabled by the CString out-of-bounds checker | ||||||
362 | // explicitly or implicitly by the Malloc checker. | ||||||
363 | // In the latter case we only do modeling but do not emit warning. | ||||||
364 | if (!Filter.CheckCStringOutOfBounds) | ||||||
365 | return nullptr; | ||||||
366 | |||||||
367 | // Emit a bug report. | ||||||
368 | ErrorMessage Message = | ||||||
369 | createOutOfBoundErrorMsg(CurrentFunctionDescription, Access); | ||||||
370 | emitOutOfBoundsBug(C, StOutBound, Buffer.Expression, Message); | ||||||
371 | return nullptr; | ||||||
372 | } | ||||||
373 | |||||||
374 | // Ensure that we wouldn't read uninitialized value. | ||||||
375 | if (Access == AccessKind::read) { | ||||||
376 | if (Filter.CheckCStringUninitializedRead && | ||||||
377 | StInBound->getSVal(ER).isUndef()) { | ||||||
378 | emitUninitializedReadBug(C, StInBound, Buffer.Expression); | ||||||
379 | return nullptr; | ||||||
380 | } | ||||||
381 | } | ||||||
382 | |||||||
383 | // Array bound check succeeded. From this point forward the array bound | ||||||
384 | // should always succeed. | ||||||
385 | return StInBound; | ||||||
386 | } | ||||||
387 | |||||||
388 | ProgramStateRef CStringChecker::CheckBufferAccess(CheckerContext &C, | ||||||
389 | ProgramStateRef State, | ||||||
390 | AnyArgExpr Buffer, | ||||||
391 | SizeArgExpr Size, | ||||||
392 | AccessKind Access) const { | ||||||
393 | // If a previous check has failed, propagate the failure. | ||||||
394 | if (!State) | ||||||
395 | return nullptr; | ||||||
396 | |||||||
397 | SValBuilder &svalBuilder = C.getSValBuilder(); | ||||||
398 | ASTContext &Ctx = svalBuilder.getContext(); | ||||||
399 | |||||||
400 | QualType SizeTy = Size.Expression->getType(); | ||||||
401 | QualType PtrTy = Ctx.getPointerType(Ctx.CharTy); | ||||||
402 | |||||||
403 | // Check that the first buffer is non-null. | ||||||
404 | SVal BufVal = C.getSVal(Buffer.Expression); | ||||||
405 | State = checkNonNull(C, State, Buffer, BufVal); | ||||||
406 | if (!State) | ||||||
407 | return nullptr; | ||||||
408 | |||||||
409 | // If out-of-bounds checking is turned off, skip the rest. | ||||||
410 | if (!Filter.CheckCStringOutOfBounds) | ||||||
411 | return State; | ||||||
412 | |||||||
413 | // Get the access length and make sure it is known. | ||||||
414 | // FIXME: This assumes the caller has already checked that the access length | ||||||
415 | // is positive. And that it's unsigned. | ||||||
416 | SVal LengthVal = C.getSVal(Size.Expression); | ||||||
417 | Optional<NonLoc> Length = LengthVal.getAs<NonLoc>(); | ||||||
418 | if (!Length) | ||||||
419 | return State; | ||||||
420 | |||||||
421 | // Compute the offset of the last element to be accessed: size-1. | ||||||
422 | NonLoc One = svalBuilder.makeIntVal(1, SizeTy).castAs<NonLoc>(); | ||||||
423 | SVal Offset = svalBuilder.evalBinOpNN(State, BO_Sub, *Length, One, SizeTy); | ||||||
424 | if (Offset.isUnknown()) | ||||||
425 | return nullptr; | ||||||
426 | NonLoc LastOffset = Offset.castAs<NonLoc>(); | ||||||
427 | |||||||
428 | // Check that the first buffer is sufficiently long. | ||||||
429 | SVal BufStart = | ||||||
430 | svalBuilder.evalCast(BufVal, PtrTy, Buffer.Expression->getType()); | ||||||
431 | if (Optional<Loc> BufLoc = BufStart.getAs<Loc>()) { | ||||||
432 | |||||||
433 | SVal BufEnd = | ||||||
434 | svalBuilder.evalBinOpLN(State, BO_Add, *BufLoc, LastOffset, PtrTy); | ||||||
435 | State = CheckLocation(C, State, Buffer, BufEnd, Access); | ||||||
436 | |||||||
437 | // If the buffer isn't large enough, abort. | ||||||
438 | if (!State) | ||||||
439 | return nullptr; | ||||||
440 | } | ||||||
441 | |||||||
442 | // Large enough or not, return this state! | ||||||
443 | return State; | ||||||
444 | } | ||||||
445 | |||||||
446 | ProgramStateRef CStringChecker::CheckOverlap(CheckerContext &C, | ||||||
447 | ProgramStateRef state, | ||||||
448 | SizeArgExpr Size, AnyArgExpr First, | ||||||
449 | AnyArgExpr Second) const { | ||||||
450 | if (!Filter.CheckCStringBufferOverlap) | ||||||
451 | return state; | ||||||
452 | |||||||
453 | // Do a simple check for overlap: if the two arguments are from the same | ||||||
454 | // buffer, see if the end of the first is greater than the start of the second | ||||||
455 | // or vice versa. | ||||||
456 | |||||||
457 | // If a previous check has failed, propagate the failure. | ||||||
458 | if (!state) | ||||||
459 | return nullptr; | ||||||
460 | |||||||
461 | ProgramStateRef stateTrue, stateFalse; | ||||||
462 | |||||||
463 | // Assume different address spaces cannot overlap. | ||||||
464 | if (First.Expression->getType()->getPointeeType().getAddressSpace() != | ||||||
465 | Second.Expression->getType()->getPointeeType().getAddressSpace()) | ||||||
466 | return state; | ||||||
467 | |||||||
468 | // Get the buffer values and make sure they're known locations. | ||||||
469 | const LocationContext *LCtx = C.getLocationContext(); | ||||||
470 | SVal firstVal = state->getSVal(First.Expression, LCtx); | ||||||
471 | SVal secondVal = state->getSVal(Second.Expression, LCtx); | ||||||
472 | |||||||
473 | Optional<Loc> firstLoc = firstVal.getAs<Loc>(); | ||||||
474 | if (!firstLoc) | ||||||
475 | return state; | ||||||
476 | |||||||
477 | Optional<Loc> secondLoc = secondVal.getAs<Loc>(); | ||||||
478 | if (!secondLoc) | ||||||
479 | return state; | ||||||
480 | |||||||
481 | // Are the two values the same? | ||||||
482 | SValBuilder &svalBuilder = C.getSValBuilder(); | ||||||
483 | std::tie(stateTrue, stateFalse) = | ||||||
484 | state->assume(svalBuilder.evalEQ(state, *firstLoc, *secondLoc)); | ||||||
485 | |||||||
486 | if (stateTrue && !stateFalse) { | ||||||
487 | // If the values are known to be equal, that's automatically an overlap. | ||||||
488 | emitOverlapBug(C, stateTrue, First.Expression, Second.Expression); | ||||||
489 | return nullptr; | ||||||
490 | } | ||||||
491 | |||||||
492 | // assume the two expressions are not equal. | ||||||
493 | assert(stateFalse)(static_cast <bool> (stateFalse) ? void (0) : __assert_fail ("stateFalse", "clang/lib/StaticAnalyzer/Checkers/CStringChecker.cpp" , 493, __extension__ __PRETTY_FUNCTION__)); | ||||||
494 | state = stateFalse; | ||||||
495 | |||||||
496 | // Which value comes first? | ||||||
497 | QualType cmpTy = svalBuilder.getConditionType(); | ||||||
498 | SVal reverse = | ||||||
499 | svalBuilder.evalBinOpLL(state, BO_GT, *firstLoc, *secondLoc, cmpTy); | ||||||
500 | Optional<DefinedOrUnknownSVal> reverseTest = | ||||||
501 | reverse.getAs<DefinedOrUnknownSVal>(); | ||||||
502 | if (!reverseTest) | ||||||
503 | return state; | ||||||
504 | |||||||
505 | std::tie(stateTrue, stateFalse) = state->assume(*reverseTest); | ||||||
506 | if (stateTrue) { | ||||||
507 | if (stateFalse) { | ||||||
508 | // If we don't know which one comes first, we can't perform this test. | ||||||
509 | return state; | ||||||
510 | } else { | ||||||
511 | // Switch the values so that firstVal is before secondVal. | ||||||
512 | std::swap(firstLoc, secondLoc); | ||||||
513 | |||||||
514 | // Switch the Exprs as well, so that they still correspond. | ||||||
515 | std::swap(First, Second); | ||||||
516 | } | ||||||
517 | } | ||||||
518 | |||||||
519 | // Get the length, and make sure it too is known. | ||||||
520 | SVal LengthVal = state->getSVal(Size.Expression, LCtx); | ||||||
521 | Optional<NonLoc> Length = LengthVal.getAs<NonLoc>(); | ||||||
522 | if (!Length) | ||||||
523 | return state; | ||||||
524 | |||||||
525 | // Convert the first buffer's start address to char*. | ||||||
526 | // Bail out if the cast fails. | ||||||
527 | ASTContext &Ctx = svalBuilder.getContext(); | ||||||
528 | QualType CharPtrTy = Ctx.getPointerType(Ctx.CharTy); | ||||||
529 | SVal FirstStart = | ||||||
530 | svalBuilder.evalCast(*firstLoc, CharPtrTy, First.Expression->getType()); | ||||||
531 | Optional<Loc> FirstStartLoc = FirstStart.getAs<Loc>(); | ||||||
532 | if (!FirstStartLoc) | ||||||
533 | return state; | ||||||
534 | |||||||
535 | // Compute the end of the first buffer. Bail out if THAT fails. | ||||||
536 | SVal FirstEnd = svalBuilder.evalBinOpLN(state, BO_Add, *FirstStartLoc, | ||||||
537 | *Length, CharPtrTy); | ||||||
538 | Optional<Loc> FirstEndLoc = FirstEnd.getAs<Loc>(); | ||||||
539 | if (!FirstEndLoc) | ||||||
540 | return state; | ||||||
541 | |||||||
542 | // Is the end of the first buffer past the start of the second buffer? | ||||||
543 | SVal Overlap = | ||||||
544 | svalBuilder.evalBinOpLL(state, BO_GT, *FirstEndLoc, *secondLoc, cmpTy); | ||||||
545 | Optional<DefinedOrUnknownSVal> OverlapTest = | ||||||
546 | Overlap.getAs<DefinedOrUnknownSVal>(); | ||||||
547 | if (!OverlapTest) | ||||||
548 | return state; | ||||||
549 | |||||||
550 | std::tie(stateTrue, stateFalse) = state->assume(*OverlapTest); | ||||||
551 | |||||||
552 | if (stateTrue && !stateFalse) { | ||||||
553 | // Overlap! | ||||||
554 | emitOverlapBug(C, stateTrue, First.Expression, Second.Expression); | ||||||
555 | return nullptr; | ||||||
556 | } | ||||||
557 | |||||||
558 | // assume the two expressions don't overlap. | ||||||
559 | assert(stateFalse)(static_cast <bool> (stateFalse) ? void (0) : __assert_fail ("stateFalse", "clang/lib/StaticAnalyzer/Checkers/CStringChecker.cpp" , 559, __extension__ __PRETTY_FUNCTION__)); | ||||||
560 | return stateFalse; | ||||||
561 | } | ||||||
562 | |||||||
563 | void CStringChecker::emitOverlapBug(CheckerContext &C, ProgramStateRef state, | ||||||
564 | const Stmt *First, const Stmt *Second) const { | ||||||
565 | ExplodedNode *N = C.generateErrorNode(state); | ||||||
566 | if (!N) | ||||||
567 | return; | ||||||
568 | |||||||
569 | if (!BT_Overlap) | ||||||
570 | BT_Overlap.reset(new BugType(Filter.CheckNameCStringBufferOverlap, | ||||||
571 | categories::UnixAPI, "Improper arguments")); | ||||||
572 | |||||||
573 | // Generate a report for this bug. | ||||||
574 | auto report = std::make_unique<PathSensitiveBugReport>( | ||||||
575 | *BT_Overlap, "Arguments must not be overlapping buffers", N); | ||||||
576 | report->addRange(First->getSourceRange()); | ||||||
577 | report->addRange(Second->getSourceRange()); | ||||||
578 | |||||||
579 | C.emitReport(std::move(report)); | ||||||
580 | } | ||||||
581 | |||||||
582 | void CStringChecker::emitNullArgBug(CheckerContext &C, ProgramStateRef State, | ||||||
583 | const Stmt *S, StringRef WarningMsg) const { | ||||||
584 | if (ExplodedNode *N = C.generateErrorNode(State)) { | ||||||
585 | if (!BT_Null) | ||||||
586 | BT_Null.reset(new BuiltinBug( | ||||||
587 | Filter.CheckNameCStringNullArg, categories::UnixAPI, | ||||||
588 | "Null pointer argument in call to byte string function")); | ||||||
589 | |||||||
590 | BuiltinBug *BT = static_cast<BuiltinBug *>(BT_Null.get()); | ||||||
591 | auto Report = std::make_unique<PathSensitiveBugReport>(*BT, WarningMsg, N); | ||||||
592 | Report->addRange(S->getSourceRange()); | ||||||
593 | if (const auto *Ex = dyn_cast<Expr>(S)) | ||||||
594 | bugreporter::trackExpressionValue(N, Ex, *Report); | ||||||
595 | C.emitReport(std::move(Report)); | ||||||
596 | } | ||||||
597 | } | ||||||
598 | |||||||
599 | void CStringChecker::emitUninitializedReadBug(CheckerContext &C, | ||||||
600 | ProgramStateRef State, | ||||||
601 | const Expr *E) const { | ||||||
602 | if (ExplodedNode *N = C.generateErrorNode(State)) { | ||||||
603 | const char *Msg = | ||||||
604 | "Bytes string function accesses uninitialized/garbage values"; | ||||||
605 | if (!BT_UninitRead) | ||||||
606 | BT_UninitRead.reset( | ||||||
607 | new BuiltinBug(Filter.CheckNameCStringUninitializedRead, | ||||||
608 | "Accessing unitialized/garbage values", Msg)); | ||||||
609 | |||||||
610 | BuiltinBug *BT = static_cast<BuiltinBug *>(BT_UninitRead.get()); | ||||||
611 | |||||||
612 | auto Report = std::make_unique<PathSensitiveBugReport>(*BT, Msg, N); | ||||||
613 | Report->addRange(E->getSourceRange()); | ||||||
614 | bugreporter::trackExpressionValue(N, E, *Report); | ||||||
615 | C.emitReport(std::move(Report)); | ||||||
616 | } | ||||||
617 | } | ||||||
618 | |||||||
619 | void CStringChecker::emitOutOfBoundsBug(CheckerContext &C, | ||||||
620 | ProgramStateRef State, const Stmt *S, | ||||||
621 | StringRef WarningMsg) const { | ||||||
622 | if (ExplodedNode *N = C.generateErrorNode(State)) { | ||||||
623 | if (!BT_Bounds) | ||||||
624 | BT_Bounds.reset(new BuiltinBug( | ||||||
625 | Filter.CheckCStringOutOfBounds ? Filter.CheckNameCStringOutOfBounds | ||||||
626 | : Filter.CheckNameCStringNullArg, | ||||||
627 | "Out-of-bound array access", | ||||||
628 | "Byte string function accesses out-of-bound array element")); | ||||||
629 | |||||||
630 | BuiltinBug *BT = static_cast<BuiltinBug *>(BT_Bounds.get()); | ||||||
631 | |||||||
632 | // FIXME: It would be nice to eventually make this diagnostic more clear, | ||||||
633 | // e.g., by referencing the original declaration or by saying *why* this | ||||||
634 | // reference is outside the range. | ||||||
635 | auto Report = std::make_unique<PathSensitiveBugReport>(*BT, WarningMsg, N); | ||||||
636 | Report->addRange(S->getSourceRange()); | ||||||
637 | C.emitReport(std::move(Report)); | ||||||
638 | } | ||||||
639 | } | ||||||
640 | |||||||
641 | void CStringChecker::emitNotCStringBug(CheckerContext &C, ProgramStateRef State, | ||||||
642 | const Stmt *S, | ||||||
643 | StringRef WarningMsg) const { | ||||||
644 | if (ExplodedNode *N = C.generateNonFatalErrorNode(State)) { | ||||||
645 | if (!BT_NotCString) | ||||||
646 | BT_NotCString.reset(new BuiltinBug( | ||||||
647 | Filter.CheckNameCStringNotNullTerm, categories::UnixAPI, | ||||||
648 | "Argument is not a null-terminated string.")); | ||||||
649 | |||||||
650 | auto Report = | ||||||
651 | std::make_unique<PathSensitiveBugReport>(*BT_NotCString, WarningMsg, N); | ||||||
652 | |||||||
653 | Report->addRange(S->getSourceRange()); | ||||||
654 | C.emitReport(std::move(Report)); | ||||||
655 | } | ||||||
656 | } | ||||||
657 | |||||||
658 | void CStringChecker::emitAdditionOverflowBug(CheckerContext &C, | ||||||
659 | ProgramStateRef State) const { | ||||||
660 | if (ExplodedNode *N = C.generateErrorNode(State)) { | ||||||
661 | if (!BT_AdditionOverflow) | ||||||
662 | BT_AdditionOverflow.reset( | ||||||
663 | new BuiltinBug(Filter.CheckNameCStringOutOfBounds, "API", | ||||||
664 | "Sum of expressions causes overflow.")); | ||||||
665 | |||||||
666 | // This isn't a great error message, but this should never occur in real | ||||||
667 | // code anyway -- you'd have to create a buffer longer than a size_t can | ||||||
668 | // represent, which is sort of a contradiction. | ||||||
669 | const char *WarningMsg = | ||||||
670 | "This expression will create a string whose length is too big to " | ||||||
671 | "be represented as a size_t"; | ||||||
672 | |||||||
673 | auto Report = std::make_unique<PathSensitiveBugReport>(*BT_AdditionOverflow, | ||||||
674 | WarningMsg, N); | ||||||
675 | C.emitReport(std::move(Report)); | ||||||
676 | } | ||||||
677 | } | ||||||
678 | |||||||
679 | ProgramStateRef CStringChecker::checkAdditionOverflow(CheckerContext &C, | ||||||
680 | ProgramStateRef state, | ||||||
681 | NonLoc left, | ||||||
682 | NonLoc right) const { | ||||||
683 | // If out-of-bounds checking is turned off, skip the rest. | ||||||
684 | if (!Filter.CheckCStringOutOfBounds) | ||||||
685 | return state; | ||||||
686 | |||||||
687 | // If a previous check has failed, propagate the failure. | ||||||
688 | if (!state) | ||||||
689 | return nullptr; | ||||||
690 | |||||||
691 | SValBuilder &svalBuilder = C.getSValBuilder(); | ||||||
692 | BasicValueFactory &BVF = svalBuilder.getBasicValueFactory(); | ||||||
693 | |||||||
694 | QualType sizeTy = svalBuilder.getContext().getSizeType(); | ||||||
695 | const llvm::APSInt &maxValInt = BVF.getMaxValue(sizeTy); | ||||||
696 | NonLoc maxVal = svalBuilder.makeIntVal(maxValInt); | ||||||
697 | |||||||
698 | SVal maxMinusRight; | ||||||
699 | if (right.getAs<nonloc::ConcreteInt>()) { | ||||||
700 | maxMinusRight = svalBuilder.evalBinOpNN(state, BO_Sub, maxVal, right, | ||||||
701 | sizeTy); | ||||||
702 | } else { | ||||||
703 | // Try switching the operands. (The order of these two assignments is | ||||||
704 | // important!) | ||||||
705 | maxMinusRight = svalBuilder.evalBinOpNN(state, BO_Sub, maxVal, left, | ||||||
706 | sizeTy); | ||||||
707 | left = right; | ||||||
708 | } | ||||||
709 | |||||||
710 | if (Optional<NonLoc> maxMinusRightNL = maxMinusRight.getAs<NonLoc>()) { | ||||||
711 | QualType cmpTy = svalBuilder.getConditionType(); | ||||||
712 | // If left > max - right, we have an overflow. | ||||||
713 | SVal willOverflow = svalBuilder.evalBinOpNN(state, BO_GT, left, | ||||||
714 | *maxMinusRightNL, cmpTy); | ||||||
715 | |||||||
716 | ProgramStateRef stateOverflow, stateOkay; | ||||||
717 | std::tie(stateOverflow, stateOkay) = | ||||||
718 | state->assume(willOverflow.castAs<DefinedOrUnknownSVal>()); | ||||||
719 | |||||||
720 | if (stateOverflow && !stateOkay) { | ||||||
721 | // We have an overflow. Emit a bug report. | ||||||
722 | emitAdditionOverflowBug(C, stateOverflow); | ||||||
723 | return nullptr; | ||||||
724 | } | ||||||
725 | |||||||
726 | // From now on, assume an overflow didn't occur. | ||||||
727 | assert(stateOkay)(static_cast <bool> (stateOkay) ? void (0) : __assert_fail ("stateOkay", "clang/lib/StaticAnalyzer/Checkers/CStringChecker.cpp" , 727, __extension__ __PRETTY_FUNCTION__)); | ||||||
728 | state = stateOkay; | ||||||
729 | } | ||||||
730 | |||||||
731 | return state; | ||||||
732 | } | ||||||
733 | |||||||
734 | ProgramStateRef CStringChecker::setCStringLength(ProgramStateRef state, | ||||||
735 | const MemRegion *MR, | ||||||
736 | SVal strLength) { | ||||||
737 | assert(!strLength.isUndef() && "Attempt to set an undefined string length")(static_cast <bool> (!strLength.isUndef() && "Attempt to set an undefined string length" ) ? void (0) : __assert_fail ("!strLength.isUndef() && \"Attempt to set an undefined string length\"" , "clang/lib/StaticAnalyzer/Checkers/CStringChecker.cpp", 737 , __extension__ __PRETTY_FUNCTION__)); | ||||||
738 | |||||||
739 | MR = MR->StripCasts(); | ||||||
740 | |||||||
741 | switch (MR->getKind()) { | ||||||
742 | case MemRegion::StringRegionKind: | ||||||
743 | // FIXME: This can happen if we strcpy() into a string region. This is | ||||||
744 | // undefined [C99 6.4.5p6], but we should still warn about it. | ||||||
745 | return state; | ||||||
746 | |||||||
747 | case MemRegion::SymbolicRegionKind: | ||||||
748 | case MemRegion::AllocaRegionKind: | ||||||
749 | case MemRegion::NonParamVarRegionKind: | ||||||
750 | case MemRegion::ParamVarRegionKind: | ||||||
751 | case MemRegion::FieldRegionKind: | ||||||
752 | case MemRegion::ObjCIvarRegionKind: | ||||||
753 | // These are the types we can currently track string lengths for. | ||||||
754 | break; | ||||||
755 | |||||||
756 | case MemRegion::ElementRegionKind: | ||||||
757 | // FIXME: Handle element regions by upper-bounding the parent region's | ||||||
758 | // string length. | ||||||
759 | return state; | ||||||
760 | |||||||
761 | default: | ||||||
762 | // Other regions (mostly non-data) can't have a reliable C string length. | ||||||
763 | // For now, just ignore the change. | ||||||
764 | // FIXME: These are rare but not impossible. We should output some kind of | ||||||
765 | // warning for things like strcpy((char[]){'a', 0}, "b"); | ||||||
766 | return state; | ||||||
767 | } | ||||||
768 | |||||||
769 | if (strLength.isUnknown()) | ||||||
770 | return state->remove<CStringLength>(MR); | ||||||
771 | |||||||
772 | return state->set<CStringLength>(MR, strLength); | ||||||
773 | } | ||||||
774 | |||||||
775 | SVal CStringChecker::getCStringLengthForRegion(CheckerContext &C, | ||||||
776 | ProgramStateRef &state, | ||||||
777 | const Expr *Ex, | ||||||
778 | const MemRegion *MR, | ||||||
779 | bool hypothetical) { | ||||||
780 | if (!hypothetical) { | ||||||
781 | // If there's a recorded length, go ahead and return it. | ||||||
782 | const SVal *Recorded = state->get<CStringLength>(MR); | ||||||
783 | if (Recorded) | ||||||
784 | return *Recorded; | ||||||
785 | } | ||||||
786 | |||||||
787 | // Otherwise, get a new symbol and update the state. | ||||||
788 | SValBuilder &svalBuilder = C.getSValBuilder(); | ||||||
789 | QualType sizeTy = svalBuilder.getContext().getSizeType(); | ||||||
790 | SVal strLength = svalBuilder.getMetadataSymbolVal(CStringChecker::getTag(), | ||||||
791 | MR, Ex, sizeTy, | ||||||
792 | C.getLocationContext(), | ||||||
793 | C.blockCount()); | ||||||
794 | |||||||
795 | if (!hypothetical) { | ||||||
796 | if (Optional<NonLoc> strLn = strLength.getAs<NonLoc>()) { | ||||||
797 | // In case of unbounded calls strlen etc bound the range to SIZE_MAX/4 | ||||||
798 | BasicValueFactory &BVF = svalBuilder.getBasicValueFactory(); | ||||||
799 | const llvm::APSInt &maxValInt = BVF.getMaxValue(sizeTy); | ||||||
800 | llvm::APSInt fourInt = APSIntType(maxValInt).getValue(4); | ||||||
801 | const llvm::APSInt *maxLengthInt = BVF.evalAPSInt(BO_Div, maxValInt, | ||||||
802 | fourInt); | ||||||
803 | NonLoc maxLength = svalBuilder.makeIntVal(*maxLengthInt); | ||||||
804 | SVal evalLength = svalBuilder.evalBinOpNN(state, BO_LE, *strLn, | ||||||
805 | maxLength, sizeTy); | ||||||
806 | state = state->assume(evalLength.castAs<DefinedOrUnknownSVal>(), true); | ||||||
807 | } | ||||||
808 | state = state->set<CStringLength>(MR, strLength); | ||||||
809 | } | ||||||
810 | |||||||
811 | return strLength; | ||||||
812 | } | ||||||
813 | |||||||
814 | SVal CStringChecker::getCStringLength(CheckerContext &C, ProgramStateRef &state, | ||||||
815 | const Expr *Ex, SVal Buf, | ||||||
816 | bool hypothetical) const { | ||||||
817 | const MemRegion *MR = Buf.getAsRegion(); | ||||||
818 | if (!MR) { | ||||||
819 | // If we can't get a region, see if it's something we /know/ isn't a | ||||||
820 | // C string. In the context of locations, the only time we can issue such | ||||||
821 | // a warning is for labels. | ||||||
822 | if (Optional<loc::GotoLabel> Label = Buf.getAs<loc::GotoLabel>()) { | ||||||
823 | if (Filter.CheckCStringNotNullTerm) { | ||||||
824 | SmallString<120> buf; | ||||||
825 | llvm::raw_svector_ostream os(buf); | ||||||
826 | assert(CurrentFunctionDescription)(static_cast <bool> (CurrentFunctionDescription) ? void (0) : __assert_fail ("CurrentFunctionDescription", "clang/lib/StaticAnalyzer/Checkers/CStringChecker.cpp" , 826, __extension__ __PRETTY_FUNCTION__)); | ||||||
827 | os << "Argument to " << CurrentFunctionDescription | ||||||
828 | << " is the address of the label '" << Label->getLabel()->getName() | ||||||
829 | << "', which is not a null-terminated string"; | ||||||
830 | |||||||
831 | emitNotCStringBug(C, state, Ex, os.str()); | ||||||
832 | } | ||||||
833 | return UndefinedVal(); | ||||||
834 | } | ||||||
835 | |||||||
836 | // If it's not a region and not a label, give up. | ||||||
837 | return UnknownVal(); | ||||||
838 | } | ||||||
839 | |||||||
840 | // If we have a region, strip casts from it and see if we can figure out | ||||||
841 | // its length. For anything we can't figure out, just return UnknownVal. | ||||||
842 | MR = MR->StripCasts(); | ||||||
843 | |||||||
844 | switch (MR->getKind()) { | ||||||
845 | case MemRegion::StringRegionKind: { | ||||||
846 | // Modifying the contents of string regions is undefined [C99 6.4.5p6], | ||||||
847 | // so we can assume that the byte length is the correct C string length. | ||||||
848 | SValBuilder &svalBuilder = C.getSValBuilder(); | ||||||
849 | QualType sizeTy = svalBuilder.getContext().getSizeType(); | ||||||
850 | const StringLiteral *strLit = cast<StringRegion>(MR)->getStringLiteral(); | ||||||
851 | return svalBuilder.makeIntVal(strLit->getByteLength(), sizeTy); | ||||||
852 | } | ||||||
853 | case MemRegion::SymbolicRegionKind: | ||||||
854 | case MemRegion::AllocaRegionKind: | ||||||
855 | case MemRegion::NonParamVarRegionKind: | ||||||
856 | case MemRegion::ParamVarRegionKind: | ||||||
857 | case MemRegion::FieldRegionKind: | ||||||
858 | case MemRegion::ObjCIvarRegionKind: | ||||||
859 | return getCStringLengthForRegion(C, state, Ex, MR, hypothetical); | ||||||
860 | case MemRegion::CompoundLiteralRegionKind: | ||||||
861 | // FIXME: Can we track this? Is it necessary? | ||||||
862 | return UnknownVal(); | ||||||
863 | case MemRegion::ElementRegionKind: | ||||||
864 | // FIXME: How can we handle this? It's not good enough to subtract the | ||||||
865 | // offset from the base string length; consider "123\x00567" and &a[5]. | ||||||
866 | return UnknownVal(); | ||||||
867 | default: | ||||||
868 | // Other regions (mostly non-data) can't have a reliable C string length. | ||||||
869 | // In this case, an error is emitted and UndefinedVal is returned. | ||||||
870 | // The caller should always be prepared to handle this case. | ||||||
871 | if (Filter.CheckCStringNotNullTerm) { | ||||||
872 | SmallString<120> buf; | ||||||
873 | llvm::raw_svector_ostream os(buf); | ||||||
874 | |||||||
875 | assert(CurrentFunctionDescription)(static_cast <bool> (CurrentFunctionDescription) ? void (0) : __assert_fail ("CurrentFunctionDescription", "clang/lib/StaticAnalyzer/Checkers/CStringChecker.cpp" , 875, __extension__ __PRETTY_FUNCTION__)); | ||||||
876 | os << "Argument to " << CurrentFunctionDescription << " is "; | ||||||
877 | |||||||
878 | if (SummarizeRegion(os, C.getASTContext(), MR)) | ||||||
879 | os << ", which is not a null-terminated string"; | ||||||
880 | else | ||||||
881 | os << "not a null-terminated string"; | ||||||
882 | |||||||
883 | emitNotCStringBug(C, state, Ex, os.str()); | ||||||
884 | } | ||||||
885 | return UndefinedVal(); | ||||||
886 | } | ||||||
887 | } | ||||||
888 | |||||||
889 | const StringLiteral *CStringChecker::getCStringLiteral(CheckerContext &C, | ||||||
890 | ProgramStateRef &state, const Expr *expr, SVal val) const { | ||||||
891 | |||||||
892 | // Get the memory region pointed to by the val. | ||||||
893 | const MemRegion *bufRegion = val.getAsRegion(); | ||||||
894 | if (!bufRegion) | ||||||
895 | return nullptr; | ||||||
896 | |||||||
897 | // Strip casts off the memory region. | ||||||
898 | bufRegion = bufRegion->StripCasts(); | ||||||
899 | |||||||
900 | // Cast the memory region to a string region. | ||||||
901 | const StringRegion *strRegion= dyn_cast<StringRegion>(bufRegion); | ||||||
902 | if (!strRegion) | ||||||
903 | return nullptr; | ||||||
904 | |||||||
905 | // Return the actual string in the string region. | ||||||
906 | return strRegion->getStringLiteral(); | ||||||
907 | } | ||||||
908 | |||||||
909 | bool CStringChecker::IsFirstBufInBound(CheckerContext &C, | ||||||
910 | ProgramStateRef state, | ||||||
911 | const Expr *FirstBuf, | ||||||
912 | const Expr *Size) { | ||||||
913 | // If we do not know that the buffer is long enough we return 'true'. | ||||||
914 | // Otherwise the parent region of this field region would also get | ||||||
915 | // invalidated, which would lead to warnings based on an unknown state. | ||||||
916 | |||||||
917 | // Originally copied from CheckBufferAccess and CheckLocation. | ||||||
918 | SValBuilder &svalBuilder = C.getSValBuilder(); | ||||||
919 | ASTContext &Ctx = svalBuilder.getContext(); | ||||||
920 | const LocationContext *LCtx = C.getLocationContext(); | ||||||
921 | |||||||
922 | QualType sizeTy = Size->getType(); | ||||||
923 | QualType PtrTy = Ctx.getPointerType(Ctx.CharTy); | ||||||
924 | SVal BufVal = state->getSVal(FirstBuf, LCtx); | ||||||
925 | |||||||
926 | SVal LengthVal = state->getSVal(Size, LCtx); | ||||||
927 | Optional<NonLoc> Length = LengthVal.getAs<NonLoc>(); | ||||||
928 | if (!Length) | ||||||
929 | return true; // cf top comment. | ||||||
930 | |||||||
931 | // Compute the offset of the last element to be accessed: size-1. | ||||||
932 | NonLoc One = svalBuilder.makeIntVal(1, sizeTy).castAs<NonLoc>(); | ||||||
933 | SVal Offset = svalBuilder.evalBinOpNN(state, BO_Sub, *Length, One, sizeTy); | ||||||
934 | if (Offset.isUnknown()) | ||||||
935 | return true; // cf top comment | ||||||
936 | NonLoc LastOffset = Offset.castAs<NonLoc>(); | ||||||
937 | |||||||
938 | // Check that the first buffer is sufficiently long. | ||||||
939 | SVal BufStart = svalBuilder.evalCast(BufVal, PtrTy, FirstBuf->getType()); | ||||||
940 | Optional<Loc> BufLoc = BufStart.getAs<Loc>(); | ||||||
941 | if (!BufLoc) | ||||||
942 | return true; // cf top comment. | ||||||
943 | |||||||
944 | SVal BufEnd = | ||||||
945 | svalBuilder.evalBinOpLN(state, BO_Add, *BufLoc, LastOffset, PtrTy); | ||||||
946 | |||||||
947 | // Check for out of bound array element access. | ||||||
948 | const MemRegion *R = BufEnd.getAsRegion(); | ||||||
949 | if (!R) | ||||||
950 | return true; // cf top comment. | ||||||
951 | |||||||
952 | const ElementRegion *ER = dyn_cast<ElementRegion>(R); | ||||||
953 | if (!ER) | ||||||
954 | return true; // cf top comment. | ||||||
955 | |||||||
956 | // FIXME: Does this crash when a non-standard definition | ||||||
957 | // of a library function is encountered? | ||||||
958 | assert(ER->getValueType() == C.getASTContext().CharTy &&(static_cast <bool> (ER->getValueType() == C.getASTContext ().CharTy && "IsFirstBufInBound should only be called with char* ElementRegions" ) ? void (0) : __assert_fail ("ER->getValueType() == C.getASTContext().CharTy && \"IsFirstBufInBound should only be called with char* ElementRegions\"" , "clang/lib/StaticAnalyzer/Checkers/CStringChecker.cpp", 959 , __extension__ __PRETTY_FUNCTION__)) | ||||||
959 | "IsFirstBufInBound should only be called with char* ElementRegions")(static_cast <bool> (ER->getValueType() == C.getASTContext ().CharTy && "IsFirstBufInBound should only be called with char* ElementRegions" ) ? void (0) : __assert_fail ("ER->getValueType() == C.getASTContext().CharTy && \"IsFirstBufInBound should only be called with char* ElementRegions\"" , "clang/lib/StaticAnalyzer/Checkers/CStringChecker.cpp", 959 , __extension__ __PRETTY_FUNCTION__)); | ||||||
960 | |||||||
961 | // Get the size of the array. | ||||||
962 | const SubRegion *superReg = cast<SubRegion>(ER->getSuperRegion()); | ||||||
963 | DefinedOrUnknownSVal SizeDV = getDynamicExtent(state, superReg, svalBuilder); | ||||||
964 | |||||||
965 | // Get the index of the accessed element. | ||||||
966 | DefinedOrUnknownSVal Idx = ER->getIndex().castAs<DefinedOrUnknownSVal>(); | ||||||
967 | |||||||
968 | ProgramStateRef StInBound = state->assumeInBound(Idx, SizeDV, true); | ||||||
969 | |||||||
970 | return static_cast<bool>(StInBound); | ||||||
971 | } | ||||||
972 | |||||||
973 | ProgramStateRef CStringChecker::InvalidateBuffer(CheckerContext &C, | ||||||
974 | ProgramStateRef state, | ||||||
975 | const Expr *E, SVal V, | ||||||
976 | bool IsSourceBuffer, | ||||||
977 | const Expr *Size) { | ||||||
978 | Optional<Loc> L = V.getAs<Loc>(); | ||||||
979 | if (!L) | ||||||
980 | return state; | ||||||
981 | |||||||
982 | // FIXME: This is a simplified version of what's in CFRefCount.cpp -- it makes | ||||||
983 | // some assumptions about the value that CFRefCount can't. Even so, it should | ||||||
984 | // probably be refactored. | ||||||
985 | if (Optional<loc::MemRegionVal> MR = L->getAs<loc::MemRegionVal>()) { | ||||||
986 | const MemRegion *R = MR->getRegion()->StripCasts(); | ||||||
987 | |||||||
988 | // Are we dealing with an ElementRegion? If so, we should be invalidating | ||||||
989 | // the super-region. | ||||||
990 | if (const ElementRegion *ER = dyn_cast<ElementRegion>(R)) { | ||||||
991 | R = ER->getSuperRegion(); | ||||||
992 | // FIXME: What about layers of ElementRegions? | ||||||
993 | } | ||||||
994 | |||||||
995 | // Invalidate this region. | ||||||
996 | const LocationContext *LCtx = C.getPredecessor()->getLocationContext(); | ||||||
997 | |||||||
998 | bool CausesPointerEscape = false; | ||||||
999 | RegionAndSymbolInvalidationTraits ITraits; | ||||||
1000 | // Invalidate and escape only indirect regions accessible through the source | ||||||
1001 | // buffer. | ||||||
1002 | if (IsSourceBuffer) { | ||||||
1003 | ITraits.setTrait(R->getBaseRegion(), | ||||||
1004 | RegionAndSymbolInvalidationTraits::TK_PreserveContents); | ||||||
1005 | ITraits.setTrait(R, RegionAndSymbolInvalidationTraits::TK_SuppressEscape); | ||||||
1006 | CausesPointerEscape = true; | ||||||
1007 | } else { | ||||||
1008 | const MemRegion::Kind& K = R->getKind(); | ||||||
1009 | if (K == MemRegion::FieldRegionKind) | ||||||
1010 | if (Size && IsFirstBufInBound(C, state, E, Size)) { | ||||||
1011 | // If destination buffer is a field region and access is in bound, | ||||||
1012 | // do not invalidate its super region. | ||||||
1013 | ITraits.setTrait( | ||||||
1014 | R, | ||||||
1015 | RegionAndSymbolInvalidationTraits::TK_DoNotInvalidateSuperRegion); | ||||||
1016 | } | ||||||
1017 | } | ||||||
1018 | |||||||
1019 | return state->invalidateRegions(R, E, C.blockCount(), LCtx, | ||||||
1020 | CausesPointerEscape, nullptr, nullptr, | ||||||
1021 | &ITraits); | ||||||
1022 | } | ||||||
1023 | |||||||
1024 | // If we have a non-region value by chance, just remove the binding. | ||||||
1025 | // FIXME: is this necessary or correct? This handles the non-Region | ||||||
1026 | // cases. Is it ever valid to store to these? | ||||||
1027 | return state->killBinding(*L); | ||||||
1028 | } | ||||||
1029 | |||||||
1030 | bool CStringChecker::SummarizeRegion(raw_ostream &os, ASTContext &Ctx, | ||||||
1031 | const MemRegion *MR) { | ||||||
1032 | switch (MR->getKind()) { | ||||||
1033 | case MemRegion::FunctionCodeRegionKind: { | ||||||
1034 | if (const auto *FD = cast<FunctionCodeRegion>(MR)->getDecl()) | ||||||
1035 | os << "the address of the function '" << *FD << '\''; | ||||||
1036 | else | ||||||
1037 | os << "the address of a function"; | ||||||
1038 | return true; | ||||||
1039 | } | ||||||
1040 | case MemRegion::BlockCodeRegionKind: | ||||||
1041 | os << "block text"; | ||||||
1042 | return true; | ||||||
1043 | case MemRegion::BlockDataRegionKind: | ||||||
1044 | os << "a block"; | ||||||
1045 | return true; | ||||||
1046 | case MemRegion::CXXThisRegionKind: | ||||||
1047 | case MemRegion::CXXTempObjectRegionKind: | ||||||
1048 | os << "a C++ temp object of type " | ||||||
1049 | << cast<TypedValueRegion>(MR)->getValueType().getAsString(); | ||||||
1050 | return true; | ||||||
1051 | case MemRegion::NonParamVarRegionKind: | ||||||
1052 | os << "a variable of type" | ||||||
1053 | << cast<TypedValueRegion>(MR)->getValueType().getAsString(); | ||||||
1054 | return true; | ||||||
1055 | case MemRegion::ParamVarRegionKind: | ||||||
1056 | os << "a parameter of type" | ||||||
1057 | << cast<TypedValueRegion>(MR)->getValueType().getAsString(); | ||||||
1058 | return true; | ||||||
1059 | case MemRegion::FieldRegionKind: | ||||||
1060 | os << "a field of type " | ||||||
1061 | << cast<TypedValueRegion>(MR)->getValueType().getAsString(); | ||||||
1062 | return true; | ||||||
1063 | case MemRegion::ObjCIvarRegionKind: | ||||||
1064 | os << "an instance variable of type " | ||||||
1065 | << cast<TypedValueRegion>(MR)->getValueType().getAsString(); | ||||||
1066 | return true; | ||||||
1067 | default: | ||||||
1068 | return false; | ||||||
1069 | } | ||||||
1070 | } | ||||||
1071 | |||||||
1072 | bool CStringChecker::memsetAux(const Expr *DstBuffer, SVal CharVal, | ||||||
1073 | const Expr *Size, CheckerContext &C, | ||||||
1074 | ProgramStateRef &State) { | ||||||
1075 | SVal MemVal = C.getSVal(DstBuffer); | ||||||
1076 | SVal SizeVal = C.getSVal(Size); | ||||||
1077 | const MemRegion *MR = MemVal.getAsRegion(); | ||||||
1078 | if (!MR) | ||||||
1079 | return false; | ||||||
1080 | |||||||
1081 | // We're about to model memset by producing a "default binding" in the Store. | ||||||
1082 | // Our current implementation - RegionStore - doesn't support default bindings | ||||||
1083 | // that don't cover the whole base region. So we should first get the offset | ||||||
1084 | // and the base region to figure out whether the offset of buffer is 0. | ||||||
1085 | RegionOffset Offset = MR->getAsOffset(); | ||||||
1086 | const MemRegion *BR = Offset.getRegion(); | ||||||
1087 | |||||||
1088 | Optional<NonLoc> SizeNL = SizeVal.getAs<NonLoc>(); | ||||||
1089 | if (!SizeNL) | ||||||
1090 | return false; | ||||||
1091 | |||||||
1092 | SValBuilder &svalBuilder = C.getSValBuilder(); | ||||||
1093 | ASTContext &Ctx = C.getASTContext(); | ||||||
1094 | |||||||
1095 | // void *memset(void *dest, int ch, size_t count); | ||||||
1096 | // For now we can only handle the case of offset is 0 and concrete char value. | ||||||
1097 | if (Offset.isValid() && !Offset.hasSymbolicOffset() && | ||||||
1098 | Offset.getOffset() == 0) { | ||||||
1099 | // Get the base region's size. | ||||||
1100 | DefinedOrUnknownSVal SizeDV = getDynamicExtent(State, BR, svalBuilder); | ||||||
1101 | |||||||
1102 | ProgramStateRef StateWholeReg, StateNotWholeReg; | ||||||
1103 | std::tie(StateWholeReg, StateNotWholeReg) = | ||||||
1104 | State->assume(svalBuilder.evalEQ(State, SizeDV, *SizeNL)); | ||||||
1105 | |||||||
1106 | // With the semantic of 'memset()', we should convert the CharVal to | ||||||
1107 | // unsigned char. | ||||||
1108 | CharVal = svalBuilder.evalCast(CharVal, Ctx.UnsignedCharTy, Ctx.IntTy); | ||||||
1109 | |||||||
1110 | ProgramStateRef StateNullChar, StateNonNullChar; | ||||||
1111 | std::tie(StateNullChar, StateNonNullChar) = | ||||||
1112 | assumeZero(C, State, CharVal, Ctx.UnsignedCharTy); | ||||||
1113 | |||||||
1114 | if (StateWholeReg && !StateNotWholeReg && StateNullChar && | ||||||
1115 | !StateNonNullChar) { | ||||||
1116 | // If the 'memset()' acts on the whole region of destination buffer and | ||||||
1117 | // the value of the second argument of 'memset()' is zero, bind the second | ||||||
1118 | // argument's value to the destination buffer with 'default binding'. | ||||||
1119 | // FIXME: Since there is no perfect way to bind the non-zero character, we | ||||||
1120 | // can only deal with zero value here. In the future, we need to deal with | ||||||
1121 | // the binding of non-zero value in the case of whole region. | ||||||
1122 | State = State->bindDefaultZero(svalBuilder.makeLoc(BR), | ||||||
1123 | C.getLocationContext()); | ||||||
1124 | } else { | ||||||
1125 | // If the destination buffer's extent is not equal to the value of | ||||||
1126 | // third argument, just invalidate buffer. | ||||||
1127 | State = InvalidateBuffer(C, State, DstBuffer, MemVal, | ||||||
1128 | /*IsSourceBuffer*/ false, Size); | ||||||
1129 | } | ||||||
1130 | |||||||
1131 | if (StateNullChar && !StateNonNullChar) { | ||||||
1132 | // If the value of the second argument of 'memset()' is zero, set the | ||||||
1133 | // string length of destination buffer to 0 directly. | ||||||
1134 | State = setCStringLength(State, MR, | ||||||
1135 | svalBuilder.makeZeroVal(Ctx.getSizeType())); | ||||||
1136 | } else if (!StateNullChar && StateNonNullChar) { | ||||||
1137 | SVal NewStrLen = svalBuilder.getMetadataSymbolVal( | ||||||
1138 | CStringChecker::getTag(), MR, DstBuffer, Ctx.getSizeType(), | ||||||
1139 | C.getLocationContext(), C.blockCount()); | ||||||
1140 | |||||||
1141 | // If the value of second argument is not zero, then the string length | ||||||
1142 | // is at least the size argument. | ||||||
1143 | SVal NewStrLenGESize = svalBuilder.evalBinOp( | ||||||
1144 | State, BO_GE, NewStrLen, SizeVal, svalBuilder.getConditionType()); | ||||||
1145 | |||||||
1146 | State = setCStringLength( | ||||||
1147 | State->assume(NewStrLenGESize.castAs<DefinedOrUnknownSVal>(), true), | ||||||
1148 | MR, NewStrLen); | ||||||
1149 | } | ||||||
1150 | } else { | ||||||
1151 | // If the offset is not zero and char value is not concrete, we can do | ||||||
1152 | // nothing but invalidate the buffer. | ||||||
1153 | State = InvalidateBuffer(C, State, DstBuffer, MemVal, | ||||||
1154 | /*IsSourceBuffer*/ false, Size); | ||||||
1155 | } | ||||||
1156 | return true; | ||||||
1157 | } | ||||||
1158 | |||||||
1159 | //===----------------------------------------------------------------------===// | ||||||
1160 | // evaluation of individual function calls. | ||||||
1161 | //===----------------------------------------------------------------------===// | ||||||
1162 | |||||||
1163 | void CStringChecker::evalCopyCommon(CheckerContext &C, const CallExpr *CE, | ||||||
1164 | ProgramStateRef state, SizeArgExpr Size, | ||||||
1165 | DestinationArgExpr Dest, | ||||||
1166 | SourceArgExpr Source, bool Restricted, | ||||||
1167 | bool IsMempcpy) const { | ||||||
1168 | CurrentFunctionDescription = "memory copy function"; | ||||||
1169 | |||||||
1170 | // See if the size argument is zero. | ||||||
1171 | const LocationContext *LCtx = C.getLocationContext(); | ||||||
1172 | SVal sizeVal = state->getSVal(Size.Expression, LCtx); | ||||||
1173 | QualType sizeTy = Size.Expression->getType(); | ||||||
1174 | |||||||
1175 | ProgramStateRef stateZeroSize, stateNonZeroSize; | ||||||
1176 | std::tie(stateZeroSize, stateNonZeroSize) = | ||||||
1177 | assumeZero(C, state, sizeVal, sizeTy); | ||||||
1178 | |||||||
1179 | // Get the value of the Dest. | ||||||
1180 | SVal destVal = state->getSVal(Dest.Expression, LCtx); | ||||||
1181 | |||||||
1182 | // If the size is zero, there won't be any actual memory access, so | ||||||
1183 | // just bind the return value to the destination buffer and return. | ||||||
1184 | if (stateZeroSize && !stateNonZeroSize) { | ||||||
1185 | stateZeroSize = stateZeroSize->BindExpr(CE, LCtx, destVal); | ||||||
1186 | C.addTransition(stateZeroSize); | ||||||
1187 | return; | ||||||
1188 | } | ||||||
1189 | |||||||
1190 | // If the size can be nonzero, we have to check the other arguments. | ||||||
1191 | if (stateNonZeroSize) { | ||||||
1192 | state = stateNonZeroSize; | ||||||
1193 | |||||||
1194 | // Ensure the destination is not null. If it is NULL there will be a | ||||||
1195 | // NULL pointer dereference. | ||||||
1196 | state = checkNonNull(C, state, Dest, destVal); | ||||||
1197 | if (!state) | ||||||
1198 | return; | ||||||
1199 | |||||||
1200 | // Get the value of the Src. | ||||||
1201 | SVal srcVal = state->getSVal(Source.Expression, LCtx); | ||||||
1202 | |||||||
1203 | // Ensure the source is not null. If it is NULL there will be a | ||||||
1204 | // NULL pointer dereference. | ||||||
1205 | state = checkNonNull(C, state, Source, srcVal); | ||||||
1206 | if (!state) | ||||||
1207 | return; | ||||||
1208 | |||||||
1209 | // Ensure the accesses are valid and that the buffers do not overlap. | ||||||
1210 | state = CheckBufferAccess(C, state, Dest, Size, AccessKind::write); | ||||||
1211 | state = CheckBufferAccess(C, state, Source, Size, AccessKind::read); | ||||||
1212 | |||||||
1213 | if (Restricted) | ||||||
1214 | state = CheckOverlap(C, state, Size, Dest, Source); | ||||||
1215 | |||||||
1216 | if (!state) | ||||||
1217 | return; | ||||||
1218 | |||||||
1219 | // If this is mempcpy, get the byte after the last byte copied and | ||||||
1220 | // bind the expr. | ||||||
1221 | if (IsMempcpy) { | ||||||
1222 | // Get the byte after the last byte copied. | ||||||
1223 | SValBuilder &SvalBuilder = C.getSValBuilder(); | ||||||
1224 | ASTContext &Ctx = SvalBuilder.getContext(); | ||||||
1225 | QualType CharPtrTy = Ctx.getPointerType(Ctx.CharTy); | ||||||
1226 | SVal DestRegCharVal = | ||||||
1227 | SvalBuilder.evalCast(destVal, CharPtrTy, Dest.Expression->getType()); | ||||||
1228 | SVal lastElement = C.getSValBuilder().evalBinOp( | ||||||
1229 | state, BO_Add, DestRegCharVal, sizeVal, Dest.Expression->getType()); | ||||||
1230 | // If we don't know how much we copied, we can at least | ||||||
1231 | // conjure a return value for later. | ||||||
1232 | if (lastElement.isUnknown()) | ||||||
1233 | lastElement = C.getSValBuilder().conjureSymbolVal(nullptr, CE, LCtx, | ||||||
1234 | C.blockCount()); | ||||||
1235 | |||||||
1236 | // The byte after the last byte copied is the return value. | ||||||
1237 | state = state->BindExpr(CE, LCtx, lastElement); | ||||||
1238 | } else { | ||||||
1239 | // All other copies return the destination buffer. | ||||||
1240 | // (Well, bcopy() has a void return type, but this won't hurt.) | ||||||
1241 | state = state->BindExpr(CE, LCtx, destVal); | ||||||
1242 | } | ||||||
1243 | |||||||
1244 | // Invalidate the destination (regular invalidation without pointer-escaping | ||||||
1245 | // the address of the top-level region). | ||||||
1246 | // FIXME: Even if we can't perfectly model the copy, we should see if we | ||||||
1247 | // can use LazyCompoundVals to copy the source values into the destination. | ||||||
1248 | // This would probably remove any existing bindings past the end of the | ||||||
1249 | // copied region, but that's still an improvement over blank invalidation. | ||||||
1250 | state = | ||||||
1251 | InvalidateBuffer(C, state, Dest.Expression, C.getSVal(Dest.Expression), | ||||||
1252 | /*IsSourceBuffer*/ false, Size.Expression); | ||||||
1253 | |||||||
1254 | // Invalidate the source (const-invalidation without const-pointer-escaping | ||||||
1255 | // the address of the top-level region). | ||||||
1256 | state = InvalidateBuffer(C, state, Source.Expression, | ||||||
1257 | C.getSVal(Source.Expression), | ||||||
1258 | /*IsSourceBuffer*/ true, nullptr); | ||||||
1259 | |||||||
1260 | C.addTransition(state); | ||||||
1261 | } | ||||||
1262 | } | ||||||
1263 | |||||||
1264 | void CStringChecker::evalMemcpy(CheckerContext &C, const CallExpr *CE) const { | ||||||
1265 | // void *memcpy(void *restrict dst, const void *restrict src, size_t n); | ||||||
1266 | // The return value is the address of the destination buffer. | ||||||
1267 | DestinationArgExpr Dest = {CE->getArg(0), 0}; | ||||||
1268 | SourceArgExpr Src = {CE->getArg(1), 1}; | ||||||
1269 | SizeArgExpr Size = {CE->getArg(2), 2}; | ||||||
1270 | |||||||
1271 | ProgramStateRef State = C.getState(); | ||||||
1272 | |||||||
1273 | constexpr bool IsRestricted = true; | ||||||
1274 | constexpr bool IsMempcpy = false; | ||||||
1275 | evalCopyCommon(C, CE, State, Size, Dest, Src, IsRestricted, IsMempcpy); | ||||||
1276 | } | ||||||
1277 | |||||||
1278 | void CStringChecker::evalMempcpy(CheckerContext &C, const CallExpr *CE) const { | ||||||
1279 | // void *mempcpy(void *restrict dst, const void *restrict src, size_t n); | ||||||
1280 | // The return value is a pointer to the byte following the last written byte. | ||||||
1281 | DestinationArgExpr Dest = {CE->getArg(0), 0}; | ||||||
1282 | SourceArgExpr Src = {CE->getArg(1), 1}; | ||||||
1283 | SizeArgExpr Size = {CE->getArg(2), 2}; | ||||||
1284 | |||||||
1285 | constexpr bool IsRestricted = true; | ||||||
1286 | constexpr bool IsMempcpy = true; | ||||||
1287 | evalCopyCommon(C, CE, C.getState(), Size, Dest, Src, IsRestricted, IsMempcpy); | ||||||
1288 | } | ||||||
1289 | |||||||
1290 | void CStringChecker::evalMemmove(CheckerContext &C, const CallExpr *CE) const { | ||||||
1291 | // void *memmove(void *dst, const void *src, size_t n); | ||||||
1292 | // The return value is the address of the destination buffer. | ||||||
1293 | DestinationArgExpr Dest = {CE->getArg(0), 0}; | ||||||
1294 | SourceArgExpr Src = {CE->getArg(1), 1}; | ||||||
1295 | SizeArgExpr Size = {CE->getArg(2), 2}; | ||||||
1296 | |||||||
1297 | constexpr bool IsRestricted = false; | ||||||
1298 | constexpr bool IsMempcpy = false; | ||||||
1299 | evalCopyCommon(C, CE, C.getState(), Size, Dest, Src, IsRestricted, IsMempcpy); | ||||||
1300 | } | ||||||
1301 | |||||||
1302 | void CStringChecker::evalBcopy(CheckerContext &C, const CallExpr *CE) const { | ||||||
1303 | // void bcopy(const void *src, void *dst, size_t n); | ||||||
1304 | SourceArgExpr Src(CE->getArg(0), 0); | ||||||
1305 | DestinationArgExpr Dest = {CE->getArg(1), 1}; | ||||||
1306 | SizeArgExpr Size = {CE->getArg(2), 2}; | ||||||
1307 | |||||||
1308 | constexpr bool IsRestricted = false; | ||||||
1309 | constexpr bool IsMempcpy = false; | ||||||
1310 | evalCopyCommon(C, CE, C.getState(), Size, Dest, Src, IsRestricted, IsMempcpy); | ||||||
1311 | } | ||||||
1312 | |||||||
1313 | void CStringChecker::evalMemcmp(CheckerContext &C, const CallExpr *CE) const { | ||||||
1314 | // int memcmp(const void *s1, const void *s2, size_t n); | ||||||
1315 | CurrentFunctionDescription = "memory comparison function"; | ||||||
1316 | |||||||
1317 | AnyArgExpr Left = {CE->getArg(0), 0}; | ||||||
1318 | AnyArgExpr Right = {CE->getArg(1), 1}; | ||||||
1319 | SizeArgExpr Size = {CE->getArg(2), 2}; | ||||||
1320 | |||||||
1321 | ProgramStateRef State = C.getState(); | ||||||
1322 | SValBuilder &Builder = C.getSValBuilder(); | ||||||
1323 | const LocationContext *LCtx = C.getLocationContext(); | ||||||
1324 | |||||||
1325 | // See if the size argument is zero. | ||||||
1326 | SVal sizeVal = State->getSVal(Size.Expression, LCtx); | ||||||
1327 | QualType sizeTy = Size.Expression->getType(); | ||||||
1328 | |||||||
1329 | ProgramStateRef stateZeroSize, stateNonZeroSize; | ||||||
1330 | std::tie(stateZeroSize, stateNonZeroSize) = | ||||||
1331 | assumeZero(C, State, sizeVal, sizeTy); | ||||||
1332 | |||||||
1333 | // If the size can be zero, the result will be 0 in that case, and we don't | ||||||
1334 | // have to check either of the buffers. | ||||||
1335 | if (stateZeroSize) { | ||||||
1336 | State = stateZeroSize; | ||||||
1337 | State = State->BindExpr(CE, LCtx, Builder.makeZeroVal(CE->getType())); | ||||||
1338 | C.addTransition(State); | ||||||
1339 | } | ||||||
1340 | |||||||
1341 | // If the size can be nonzero, we have to check the other arguments. | ||||||
1342 | if (stateNonZeroSize) { | ||||||
1343 | State = stateNonZeroSize; | ||||||
1344 | // If we know the two buffers are the same, we know the result is 0. | ||||||
1345 | // First, get the two buffers' addresses. Another checker will have already | ||||||
1346 | // made sure they're not undefined. | ||||||
1347 | DefinedOrUnknownSVal LV = | ||||||
1348 | State->getSVal(Left.Expression, LCtx).castAs<DefinedOrUnknownSVal>(); | ||||||
1349 | DefinedOrUnknownSVal RV = | ||||||
1350 | State->getSVal(Right.Expression, LCtx).castAs<DefinedOrUnknownSVal>(); | ||||||
1351 | |||||||
1352 | // See if they are the same. | ||||||
1353 | ProgramStateRef SameBuffer, NotSameBuffer; | ||||||
1354 | std::tie(SameBuffer, NotSameBuffer) = | ||||||
1355 | State->assume(Builder.evalEQ(State, LV, RV)); | ||||||
1356 | |||||||
1357 | // If the two arguments are the same buffer, we know the result is 0, | ||||||
1358 | // and we only need to check one size. | ||||||
1359 | if (SameBuffer && !NotSameBuffer) { | ||||||
1360 | State = SameBuffer; | ||||||
1361 | State = CheckBufferAccess(C, State, Left, Size, AccessKind::read); | ||||||
1362 | if (State) { | ||||||
1363 | State = | ||||||
1364 | SameBuffer->BindExpr(CE, LCtx, Builder.makeZeroVal(CE->getType())); | ||||||
1365 | C.addTransition(State); | ||||||
1366 | } | ||||||
1367 | return; | ||||||
1368 | } | ||||||
1369 | |||||||
1370 | // If the two arguments might be different buffers, we have to check | ||||||
1371 | // the size of both of them. | ||||||
1372 | assert(NotSameBuffer)(static_cast <bool> (NotSameBuffer) ? void (0) : __assert_fail ("NotSameBuffer", "clang/lib/StaticAnalyzer/Checkers/CStringChecker.cpp" , 1372, __extension__ __PRETTY_FUNCTION__)); | ||||||
1373 | State = CheckBufferAccess(C, State, Right, Size, AccessKind::read); | ||||||
1374 | State = CheckBufferAccess(C, State, Left, Size, AccessKind::read); | ||||||
1375 | if (State) { | ||||||
1376 | // The return value is the comparison result, which we don't know. | ||||||
1377 | SVal CmpV = Builder.conjureSymbolVal(nullptr, CE, LCtx, C.blockCount()); | ||||||
1378 | State = State->BindExpr(CE, LCtx, CmpV); | ||||||
1379 | C.addTransition(State); | ||||||
1380 | } | ||||||
1381 | } | ||||||
1382 | } | ||||||
1383 | |||||||
1384 | void CStringChecker::evalstrLength(CheckerContext &C, | ||||||
1385 | const CallExpr *CE) const { | ||||||
1386 | // size_t strlen(const char *s); | ||||||
1387 | evalstrLengthCommon(C, CE, /* IsStrnlen = */ false); | ||||||
1388 | } | ||||||
1389 | |||||||
1390 | void CStringChecker::evalstrnLength(CheckerContext &C, | ||||||
1391 | const CallExpr *CE) const { | ||||||
1392 | // size_t strnlen(const char *s, size_t maxlen); | ||||||
1393 | evalstrLengthCommon(C, CE, /* IsStrnlen = */ true); | ||||||
| |||||||
1394 | } | ||||||
1395 | |||||||
1396 | void CStringChecker::evalstrLengthCommon(CheckerContext &C, const CallExpr *CE, | ||||||
1397 | bool IsStrnlen) const { | ||||||
1398 | CurrentFunctionDescription = "string length function"; | ||||||
1399 | ProgramStateRef state = C.getState(); | ||||||
1400 | const LocationContext *LCtx = C.getLocationContext(); | ||||||
1401 | |||||||
1402 | if (IsStrnlen
| ||||||
1403 | const Expr *maxlenExpr = CE->getArg(1); | ||||||
1404 | SVal maxlenVal = state->getSVal(maxlenExpr, LCtx); | ||||||
1405 | |||||||
1406 | ProgramStateRef stateZeroSize, stateNonZeroSize; | ||||||
1407 | std::tie(stateZeroSize, stateNonZeroSize) = | ||||||
1408 | assumeZero(C, state, maxlenVal, maxlenExpr->getType()); | ||||||
1409 | |||||||
1410 | // If the size can be zero, the result will be 0 in that case, and we don't | ||||||
1411 | // have to check the string itself. | ||||||
1412 | if (stateZeroSize) { | ||||||
1413 | SVal zero = C.getSValBuilder().makeZeroVal(CE->getType()); | ||||||
1414 | stateZeroSize = stateZeroSize->BindExpr(CE, LCtx, zero); | ||||||
1415 | C.addTransition(stateZeroSize); | ||||||
1416 | } | ||||||
1417 | |||||||
1418 | // If the size is GUARANTEED to be zero, we're done! | ||||||
1419 | if (!stateNonZeroSize) | ||||||
1420 | return; | ||||||
1421 | |||||||
1422 | // Otherwise, record the assumption that the size is nonzero. | ||||||
1423 | state = stateNonZeroSize; | ||||||
1424 | } | ||||||
1425 | |||||||
1426 | // Check that the string argument is non-null. | ||||||
1427 | AnyArgExpr Arg = {CE->getArg(0), 0}; | ||||||
1428 | SVal ArgVal = state->getSVal(Arg.Expression, LCtx); | ||||||
1429 | state = checkNonNull(C, state, Arg, ArgVal); | ||||||
1430 | |||||||
1431 | if (!state) | ||||||
1432 | return; | ||||||
1433 | |||||||
1434 | SVal strLength = getCStringLength(C, state, Arg.Expression, ArgVal); | ||||||
1435 | |||||||
1436 | // If the argument isn't a valid C string, there's no valid state to | ||||||
1437 | // transition to. | ||||||
1438 | if (strLength.isUndef()) | ||||||
1439 | return; | ||||||
1440 | |||||||
1441 | DefinedOrUnknownSVal result = UnknownVal(); | ||||||
1442 | |||||||
1443 | // If the check is for strnlen() then bind the return value to no more than | ||||||
1444 | // the maxlen value. | ||||||
1445 | if (IsStrnlen
| ||||||
1446 | QualType cmpTy = C.getSValBuilder().getConditionType(); | ||||||
1447 | |||||||
1448 | // It's a little unfortunate to be getting this again, | ||||||
1449 | // but it's not that expensive... | ||||||
1450 | const Expr *maxlenExpr = CE->getArg(1); | ||||||
1451 | SVal maxlenVal = state->getSVal(maxlenExpr, LCtx); | ||||||
1452 | |||||||
1453 | Optional<NonLoc> strLengthNL = strLength.getAs<NonLoc>(); | ||||||
1454 | Optional<NonLoc> maxlenValNL = maxlenVal.getAs<NonLoc>(); | ||||||
1455 | |||||||
1456 | if (strLengthNL && maxlenValNL) { | ||||||
1457 | ProgramStateRef stateStringTooLong, stateStringNotTooLong; | ||||||
1458 | |||||||
1459 | // Check if the strLength is greater than the maxlen. | ||||||
1460 | std::tie(stateStringTooLong, stateStringNotTooLong) = state->assume( | ||||||
1461 | C.getSValBuilder() | ||||||
1462 | .evalBinOpNN(state, BO_GT, *strLengthNL, *maxlenValNL, cmpTy) | ||||||
1463 | .castAs<DefinedOrUnknownSVal>()); | ||||||
1464 | |||||||
1465 | if (stateStringTooLong && !stateStringNotTooLong) { | ||||||
1466 | // If the string is longer than maxlen, return maxlen. | ||||||
1467 | result = *maxlenValNL; | ||||||
1468 | } else if (stateStringNotTooLong && !stateStringTooLong) { | ||||||
1469 | // If the string is shorter than maxlen, return its length. | ||||||
1470 | result = *strLengthNL; | ||||||
1471 | } | ||||||
1472 | } | ||||||
1473 | |||||||
1474 | if (result.isUnknown()) { | ||||||
1475 | // If we don't have enough information for a comparison, there's | ||||||
1476 | // no guarantee the full string length will actually be returned. | ||||||
1477 | // All we know is the return value is the min of the string length | ||||||
1478 | // and the limit. This is better than nothing. | ||||||
1479 | result = C.getSValBuilder().conjureSymbolVal(nullptr, CE, LCtx, | ||||||
1480 | C.blockCount()); | ||||||
1481 | NonLoc resultNL = result.castAs<NonLoc>(); | ||||||
1482 | |||||||
1483 | if (strLengthNL) { | ||||||
1484 | state = state->assume(C.getSValBuilder().evalBinOpNN( | ||||||
1485 | state, BO_LE, resultNL, *strLengthNL, cmpTy) | ||||||
1486 | .castAs<DefinedOrUnknownSVal>(), true); | ||||||
1487 | } | ||||||
1488 | |||||||
1489 | if (maxlenValNL) { | ||||||
1490 | state = state->assume(C.getSValBuilder().evalBinOpNN( | ||||||
| |||||||
1491 | state, BO_LE, resultNL, *maxlenValNL, cmpTy) | ||||||
1492 | .castAs<DefinedOrUnknownSVal>(), true); | ||||||
1493 | } | ||||||
1494 | } | ||||||
1495 | |||||||
1496 | } else { | ||||||
1497 | // This is a plain strlen(), not strnlen(). | ||||||
1498 | result = strLength.castAs<DefinedOrUnknownSVal>(); | ||||||
1499 | |||||||
1500 | // If we don't know the length of the string, conjure a return | ||||||
1501 | // value, so it can be used in constraints, at least. | ||||||
1502 | if (result.isUnknown()) { | ||||||
1503 | result = C.getSValBuilder().conjureSymbolVal(nullptr, CE, LCtx, | ||||||
1504 | C.blockCount()); | ||||||
1505 | } | ||||||
1506 | } | ||||||
1507 | |||||||
1508 | // Bind the return value. | ||||||
1509 | assert(!result.isUnknown() && "Should have conjured a value by now")(static_cast <bool> (!result.isUnknown() && "Should have conjured a value by now" ) ? void (0) : __assert_fail ("!result.isUnknown() && \"Should have conjured a value by now\"" , "clang/lib/StaticAnalyzer/Checkers/CStringChecker.cpp", 1509 , __extension__ __PRETTY_FUNCTION__)); | ||||||
1510 | state = state->BindExpr(CE, LCtx, result); | ||||||
1511 | C.addTransition(state); | ||||||
1512 | } | ||||||
1513 | |||||||
1514 | void CStringChecker::evalStrcpy(CheckerContext &C, const CallExpr *CE) const { | ||||||
1515 | // char *strcpy(char *restrict dst, const char *restrict src); | ||||||
1516 | evalStrcpyCommon(C, CE, | ||||||
1517 | /* ReturnEnd = */ false, | ||||||
1518 | /* IsBounded = */ false, | ||||||
1519 | /* appendK = */ ConcatFnKind::none); | ||||||
1520 | } | ||||||
1521 | |||||||
1522 | void CStringChecker::evalStrncpy(CheckerContext &C, const CallExpr *CE) const { | ||||||
1523 | // char *strncpy(char *restrict dst, const char *restrict src, size_t n); | ||||||
1524 | evalStrcpyCommon(C, CE, | ||||||
1525 | /* ReturnEnd = */ false, | ||||||
1526 | /* IsBounded = */ true, | ||||||
1527 | /* appendK = */ ConcatFnKind::none); | ||||||
1528 | } | ||||||
1529 | |||||||
1530 | void CStringChecker::evalStpcpy(CheckerContext &C, const CallExpr *CE) const { | ||||||
1531 | // char *stpcpy(char *restrict dst, const char *restrict src); | ||||||
1532 | evalStrcpyCommon(C, CE, | ||||||
1533 | /* ReturnEnd = */ true, | ||||||
1534 | /* IsBounded = */ false, | ||||||
1535 | /* appendK = */ ConcatFnKind::none); | ||||||
1536 | } | ||||||
1537 | |||||||
1538 | void CStringChecker::evalStrlcpy(CheckerContext &C, const CallExpr *CE) const { | ||||||
1539 | // size_t strlcpy(char *dest, const char *src, size_t size); | ||||||
1540 | evalStrcpyCommon(C, CE, | ||||||
1541 | /* ReturnEnd = */ true, | ||||||
1542 | /* IsBounded = */ true, | ||||||
1543 | /* appendK = */ ConcatFnKind::none, | ||||||
1544 | /* returnPtr = */ false); | ||||||
1545 | } | ||||||
1546 | |||||||
1547 | void CStringChecker::evalStrcat(CheckerContext &C, const CallExpr *CE) const { | ||||||
1548 | // char *strcat(char *restrict s1, const char *restrict s2); | ||||||
1549 | evalStrcpyCommon(C, CE, | ||||||
1550 | /* ReturnEnd = */ false, | ||||||
1551 | /* IsBounded = */ false, | ||||||
1552 | /* appendK = */ ConcatFnKind::strcat); | ||||||
1553 | } | ||||||
1554 | |||||||
1555 | void CStringChecker::evalStrncat(CheckerContext &C, const CallExpr *CE) const { | ||||||
1556 | // char *strncat(char *restrict s1, const char *restrict s2, size_t n); | ||||||
1557 | evalStrcpyCommon(C, CE, | ||||||
1558 | /* ReturnEnd = */ false, | ||||||
1559 | /* IsBounded = */ true, | ||||||
1560 | /* appendK = */ ConcatFnKind::strcat); | ||||||
1561 | } | ||||||
1562 | |||||||
1563 | void CStringChecker::evalStrlcat(CheckerContext &C, const CallExpr *CE) const { | ||||||
1564 | // size_t strlcat(char *dst, const char *src, size_t size); | ||||||
1565 | // It will append at most size - strlen(dst) - 1 bytes, | ||||||
1566 | // NULL-terminating the result. | ||||||
1567 | evalStrcpyCommon(C, CE, | ||||||
1568 | /* ReturnEnd = */ false, | ||||||
1569 | /* IsBounded = */ true, | ||||||
1570 | /* appendK = */ ConcatFnKind::strlcat, | ||||||
1571 | /* returnPtr = */ false); | ||||||
1572 | } | ||||||
1573 | |||||||
1574 | void CStringChecker::evalStrcpyCommon(CheckerContext &C, const CallExpr *CE, | ||||||
1575 | bool ReturnEnd, bool IsBounded, | ||||||
1576 | ConcatFnKind appendK, | ||||||
1577 | bool returnPtr) const { | ||||||
1578 | if (appendK == ConcatFnKind::none) | ||||||
1579 | CurrentFunctionDescription = "string copy function"; | ||||||
1580 | else | ||||||
1581 | CurrentFunctionDescription = "string concatenation function"; | ||||||
1582 | |||||||
1583 | ProgramStateRef state = C.getState(); | ||||||
1584 | const LocationContext *LCtx = C.getLocationContext(); | ||||||
1585 | |||||||
1586 | // Check that the destination is non-null. | ||||||
1587 | DestinationArgExpr Dst = {CE->getArg(0), 0}; | ||||||
1588 | SVal DstVal = state->getSVal(Dst.Expression, LCtx); | ||||||
1589 | state = checkNonNull(C, state, Dst, DstVal); | ||||||
1590 | if (!state) | ||||||
1591 | return; | ||||||
1592 | |||||||
1593 | // Check that the source is non-null. | ||||||
1594 | SourceArgExpr srcExpr = {CE->getArg(1), 1}; | ||||||
1595 | SVal srcVal = state->getSVal(srcExpr.Expression, LCtx); | ||||||
1596 | state = checkNonNull(C, state, srcExpr, srcVal); | ||||||
1597 | if (!state) | ||||||
1598 | return; | ||||||
1599 | |||||||
1600 | // Get the string length of the source. | ||||||
1601 | SVal strLength = getCStringLength(C, state, srcExpr.Expression, srcVal); | ||||||
1602 | Optional<NonLoc> strLengthNL = strLength.getAs<NonLoc>(); | ||||||
1603 | |||||||
1604 | // Get the string length of the destination buffer. | ||||||
1605 | SVal dstStrLength = getCStringLength(C, state, Dst.Expression, DstVal); | ||||||
1606 | Optional<NonLoc> dstStrLengthNL = dstStrLength.getAs<NonLoc>(); | ||||||
1607 | |||||||
1608 | // If the source isn't a valid C string, give up. | ||||||
1609 | if (strLength.isUndef()) | ||||||
1610 | return; | ||||||
1611 | |||||||
1612 | SValBuilder &svalBuilder = C.getSValBuilder(); | ||||||
1613 | QualType cmpTy = svalBuilder.getConditionType(); | ||||||
1614 | QualType sizeTy = svalBuilder.getContext().getSizeType(); | ||||||
1615 | |||||||
1616 | // These two values allow checking two kinds of errors: | ||||||
1617 | // - actual overflows caused by a source that doesn't fit in the destination | ||||||
1618 | // - potential overflows caused by a bound that could exceed the destination | ||||||
1619 | SVal amountCopied = UnknownVal(); | ||||||
1620 | SVal maxLastElementIndex = UnknownVal(); | ||||||
1621 | const char *boundWarning = nullptr; | ||||||
1622 | |||||||
1623 | // FIXME: Why do we choose the srcExpr if the access has no size? | ||||||
1624 | // Note that the 3rd argument of the call would be the size parameter. | ||||||
1625 | SizeArgExpr SrcExprAsSizeDummy = {srcExpr.Expression, srcExpr.ArgumentIndex}; | ||||||
1626 | state = CheckOverlap( | ||||||
1627 | C, state, | ||||||
1628 | (IsBounded ? SizeArgExpr{CE->getArg(2), 2} : SrcExprAsSizeDummy), Dst, | ||||||
1629 | srcExpr); | ||||||
1630 | |||||||
1631 | if (!state) | ||||||
1632 | return; | ||||||
1633 | |||||||
1634 | // If the function is strncpy, strncat, etc... it is bounded. | ||||||
1635 | if (IsBounded) { | ||||||
1636 | // Get the max number of characters to copy. | ||||||
1637 | SizeArgExpr lenExpr = {CE->getArg(2), 2}; | ||||||
1638 | SVal lenVal = state->getSVal(lenExpr.Expression, LCtx); | ||||||
1639 | |||||||
1640 | // Protect against misdeclared strncpy(). | ||||||
1641 | lenVal = | ||||||
1642 | svalBuilder.evalCast(lenVal, sizeTy, lenExpr.Expression->getType()); | ||||||
1643 | |||||||
1644 | Optional<NonLoc> lenValNL = lenVal.getAs<NonLoc>(); | ||||||
1645 | |||||||
1646 | // If we know both values, we might be able to figure out how much | ||||||
1647 | // we're copying. | ||||||
1648 | if (strLengthNL && lenValNL) { | ||||||
1649 | switch (appendK) { | ||||||
1650 | case ConcatFnKind::none: | ||||||
1651 | case ConcatFnKind::strcat: { | ||||||
1652 | ProgramStateRef stateSourceTooLong, stateSourceNotTooLong; | ||||||
1653 | // Check if the max number to copy is less than the length of the src. | ||||||
1654 | // If the bound is equal to the source length, strncpy won't null- | ||||||
1655 | // terminate the result! | ||||||
1656 | std::tie(stateSourceTooLong, stateSourceNotTooLong) = state->assume( | ||||||
1657 | svalBuilder | ||||||
1658 | .evalBinOpNN(state, BO_GE, *strLengthNL, *lenValNL, cmpTy) | ||||||
1659 | .castAs<DefinedOrUnknownSVal>()); | ||||||
1660 | |||||||
1661 | if (stateSourceTooLong && !stateSourceNotTooLong) { | ||||||
1662 | // Max number to copy is less than the length of the src, so the | ||||||
1663 | // actual strLength copied is the max number arg. | ||||||
1664 | state = stateSourceTooLong; | ||||||
1665 | amountCopied = lenVal; | ||||||
1666 | |||||||
1667 | } else if (!stateSourceTooLong && stateSourceNotTooLong) { | ||||||
1668 | // The source buffer entirely fits in the bound. | ||||||
1669 | state = stateSourceNotTooLong; | ||||||
1670 | amountCopied = strLength; | ||||||
1671 | } | ||||||
1672 | break; | ||||||
1673 | } | ||||||
1674 | case ConcatFnKind::strlcat: | ||||||
1675 | if (!dstStrLengthNL) | ||||||
1676 | return; | ||||||
1677 | |||||||
1678 | // amountCopied = min (size - dstLen - 1 , srcLen) | ||||||
1679 | SVal freeSpace = svalBuilder.evalBinOpNN(state, BO_Sub, *lenValNL, | ||||||
1680 | *dstStrLengthNL, sizeTy); | ||||||
1681 | if (!freeSpace.getAs<NonLoc>()) | ||||||
1682 | return; | ||||||
1683 | freeSpace = | ||||||
1684 | svalBuilder.evalBinOp(state, BO_Sub, freeSpace, | ||||||
1685 | svalBuilder.makeIntVal(1, sizeTy), sizeTy); | ||||||
1686 | Optional<NonLoc> freeSpaceNL = freeSpace.getAs<NonLoc>(); | ||||||
1687 | |||||||
1688 | // While unlikely, it is possible that the subtraction is | ||||||
1689 | // too complex to compute, let's check whether it succeeded. | ||||||
1690 | if (!freeSpaceNL) | ||||||
1691 | return; | ||||||
1692 | SVal hasEnoughSpace = svalBuilder.evalBinOpNN( | ||||||
1693 | state, BO_LE, *strLengthNL, *freeSpaceNL, cmpTy); | ||||||
1694 | |||||||
1695 | ProgramStateRef TrueState, FalseState; | ||||||
1696 | std::tie(TrueState, FalseState) = | ||||||
1697 | state->assume(hasEnoughSpace.castAs<DefinedOrUnknownSVal>()); | ||||||
1698 | |||||||
1699 | // srcStrLength <= size - dstStrLength -1 | ||||||
1700 | if (TrueState && !FalseState) { | ||||||
1701 | amountCopied = strLength; | ||||||
1702 | } | ||||||
1703 | |||||||
1704 | // srcStrLength > size - dstStrLength -1 | ||||||
1705 | if (!TrueState && FalseState) { | ||||||
1706 | amountCopied = freeSpace; | ||||||
1707 | } | ||||||
1708 | |||||||
1709 | if (TrueState && FalseState) | ||||||
1710 | amountCopied = UnknownVal(); | ||||||
1711 | break; | ||||||
1712 | } | ||||||
1713 | } | ||||||
1714 | // We still want to know if the bound is known to be too large. | ||||||
1715 | if (lenValNL) { | ||||||
1716 | switch (appendK) { | ||||||
1717 | case ConcatFnKind::strcat: | ||||||
1718 | // For strncat, the check is strlen(dst) + lenVal < sizeof(dst) | ||||||
1719 | |||||||
1720 | // Get the string length of the destination. If the destination is | ||||||
1721 | // memory that can't have a string length, we shouldn't be copying | ||||||
1722 | // into it anyway. | ||||||
1723 | if (dstStrLength.isUndef()) | ||||||
1724 | return; | ||||||
1725 | |||||||
1726 | if (dstStrLengthNL) { | ||||||
1727 | maxLastElementIndex = svalBuilder.evalBinOpNN( | ||||||
1728 | state, BO_Add, *lenValNL, *dstStrLengthNL, sizeTy); | ||||||
1729 | |||||||
1730 | boundWarning = "Size argument is greater than the free space in the " | ||||||
1731 | "destination buffer"; | ||||||
1732 | } | ||||||
1733 | break; | ||||||
1734 | case ConcatFnKind::none: | ||||||
1735 | case ConcatFnKind::strlcat: | ||||||
1736 | // For strncpy and strlcat, this is just checking | ||||||
1737 | // that lenVal <= sizeof(dst). | ||||||
1738 | // (Yes, strncpy and strncat differ in how they treat termination. | ||||||
1739 | // strncat ALWAYS terminates, but strncpy doesn't.) | ||||||
1740 | |||||||
1741 | // We need a special case for when the copy size is zero, in which | ||||||
1742 | // case strncpy will do no work at all. Our bounds check uses n-1 | ||||||
1743 | // as the last element accessed, so n == 0 is problematic. | ||||||
1744 | ProgramStateRef StateZeroSize, StateNonZeroSize; | ||||||
1745 | std::tie(StateZeroSize, StateNonZeroSize) = | ||||||
1746 | assumeZero(C, state, *lenValNL, sizeTy); | ||||||
1747 | |||||||
1748 | // If the size is known to be zero, we're done. | ||||||
1749 | if (StateZeroSize && !StateNonZeroSize) { | ||||||
1750 | if (returnPtr) { | ||||||
1751 | StateZeroSize = StateZeroSize->BindExpr(CE, LCtx, DstVal); | ||||||
1752 | } else { | ||||||
1753 | if (appendK == ConcatFnKind::none) { | ||||||
1754 | // strlcpy returns strlen(src) | ||||||
1755 | StateZeroSize = StateZeroSize->BindExpr(CE, LCtx, strLength); | ||||||
1756 | } else { | ||||||
1757 | // strlcat returns strlen(src) + strlen(dst) | ||||||
1758 | SVal retSize = svalBuilder.evalBinOp( | ||||||
1759 | state, BO_Add, strLength, dstStrLength, sizeTy); | ||||||
1760 | StateZeroSize = StateZeroSize->BindExpr(CE, LCtx, retSize); | ||||||
1761 | } | ||||||
1762 | } | ||||||
1763 | C.addTransition(StateZeroSize); | ||||||
1764 | return; | ||||||
1765 | } | ||||||
1766 | |||||||
1767 | // Otherwise, go ahead and figure out the last element we'll touch. | ||||||
1768 | // We don't record the non-zero assumption here because we can't | ||||||
1769 | // be sure. We won't warn on a possible zero. | ||||||
1770 | NonLoc one = svalBuilder.makeIntVal(1, sizeTy).castAs<NonLoc>(); | ||||||
1771 | maxLastElementIndex = | ||||||
1772 | svalBuilder.evalBinOpNN(state, BO_Sub, *lenValNL, one, sizeTy); | ||||||
1773 | boundWarning = "Size argument is greater than the length of the " | ||||||
1774 | "destination buffer"; | ||||||
1775 | break; | ||||||
1776 | } | ||||||
1777 | } | ||||||
1778 | } else { | ||||||
1779 | // The function isn't bounded. The amount copied should match the length | ||||||
1780 | // of the source buffer. | ||||||
1781 | amountCopied = strLength; | ||||||
1782 | } | ||||||
1783 | |||||||
1784 | assert(state)(static_cast <bool> (state) ? void (0) : __assert_fail ( "state", "clang/lib/StaticAnalyzer/Checkers/CStringChecker.cpp" , 1784, __extension__ __PRETTY_FUNCTION__)); | ||||||
1785 | |||||||
1786 | // This represents the number of characters copied into the destination | ||||||
1787 | // buffer. (It may not actually be the strlen if the destination buffer | ||||||
1788 | // is not terminated.) | ||||||
1789 | SVal finalStrLength = UnknownVal(); | ||||||
1790 | SVal strlRetVal = UnknownVal(); | ||||||
1791 | |||||||
1792 | if (appendK == ConcatFnKind::none && !returnPtr) { | ||||||
1793 | // strlcpy returns the sizeof(src) | ||||||
1794 | strlRetVal = strLength; | ||||||
1795 | } | ||||||
1796 | |||||||
1797 | // If this is an appending function (strcat, strncat...) then set the | ||||||
1798 | // string length to strlen(src) + strlen(dst) since the buffer will | ||||||
1799 | // ultimately contain both. | ||||||
1800 | if (appendK != ConcatFnKind::none) { | ||||||
1801 | // Get the string length of the destination. If the destination is memory | ||||||
1802 | // that can't have a string length, we shouldn't be copying into it anyway. | ||||||
1803 | if (dstStrLength.isUndef()) | ||||||
1804 | return; | ||||||
1805 | |||||||
1806 | if (appendK == ConcatFnKind::strlcat && dstStrLengthNL && strLengthNL) { | ||||||
1807 | strlRetVal = svalBuilder.evalBinOpNN(state, BO_Add, *strLengthNL, | ||||||
1808 | *dstStrLengthNL, sizeTy); | ||||||
1809 | } | ||||||
1810 | |||||||
1811 | Optional<NonLoc> amountCopiedNL = amountCopied.getAs<NonLoc>(); | ||||||
1812 | |||||||
1813 | // If we know both string lengths, we might know the final string length. | ||||||
1814 | if (amountCopiedNL && dstStrLengthNL) { | ||||||
1815 | // Make sure the two lengths together don't overflow a size_t. | ||||||
1816 | state = checkAdditionOverflow(C, state, *amountCopiedNL, *dstStrLengthNL); | ||||||
1817 | if (!state) | ||||||
1818 | return; | ||||||
1819 | |||||||
1820 | finalStrLength = svalBuilder.evalBinOpNN(state, BO_Add, *amountCopiedNL, | ||||||
1821 | *dstStrLengthNL, sizeTy); | ||||||
1822 | } | ||||||
1823 | |||||||
1824 | // If we couldn't get a single value for the final string length, | ||||||
1825 | // we can at least bound it by the individual lengths. | ||||||
1826 | if (finalStrLength.isUnknown()) { | ||||||
1827 | // Try to get a "hypothetical" string length symbol, which we can later | ||||||
1828 | // set as a real value if that turns out to be the case. | ||||||
1829 | finalStrLength = getCStringLength(C, state, CE, DstVal, true); | ||||||
1830 | assert(!finalStrLength.isUndef())(static_cast <bool> (!finalStrLength.isUndef()) ? void ( 0) : __assert_fail ("!finalStrLength.isUndef()", "clang/lib/StaticAnalyzer/Checkers/CStringChecker.cpp" , 1830, __extension__ __PRETTY_FUNCTION__)); | ||||||
1831 | |||||||
1832 | if (Optional<NonLoc> finalStrLengthNL = finalStrLength.getAs<NonLoc>()) { | ||||||
1833 | if (amountCopiedNL && appendK == ConcatFnKind::none) { | ||||||
1834 | // we overwrite dst string with the src | ||||||
1835 | // finalStrLength >= srcStrLength | ||||||
1836 | SVal sourceInResult = svalBuilder.evalBinOpNN( | ||||||
1837 | state, BO_GE, *finalStrLengthNL, *amountCopiedNL, cmpTy); | ||||||
1838 | state = state->assume(sourceInResult.castAs<DefinedOrUnknownSVal>(), | ||||||
1839 | true); | ||||||
1840 | if (!state) | ||||||
1841 | return; | ||||||
1842 | } | ||||||
1843 | |||||||
1844 | if (dstStrLengthNL && appendK != ConcatFnKind::none) { | ||||||
1845 | // we extend the dst string with the src | ||||||
1846 | // finalStrLength >= dstStrLength | ||||||
1847 | SVal destInResult = svalBuilder.evalBinOpNN(state, BO_GE, | ||||||
1848 | *finalStrLengthNL, | ||||||
1849 | *dstStrLengthNL, | ||||||
1850 | cmpTy); | ||||||
1851 | state = | ||||||
1852 | state->assume(destInResult.castAs<DefinedOrUnknownSVal>(), true); | ||||||
1853 | if (!state) | ||||||
1854 | return; | ||||||
1855 | } | ||||||
1856 | } | ||||||
1857 | } | ||||||
1858 | |||||||
1859 | } else { | ||||||
1860 | // Otherwise, this is a copy-over function (strcpy, strncpy, ...), and | ||||||
1861 | // the final string length will match the input string length. | ||||||
1862 | finalStrLength = amountCopied; | ||||||
1863 | } | ||||||
1864 | |||||||
1865 | SVal Result; | ||||||
1866 | |||||||
1867 | if (returnPtr) { | ||||||
1868 | // The final result of the function will either be a pointer past the last | ||||||
1869 | // copied element, or a pointer to the start of the destination buffer. | ||||||
1870 | Result = (ReturnEnd ? UnknownVal() : DstVal); | ||||||
1871 | } else { | ||||||
1872 | if (appendK == ConcatFnKind::strlcat || appendK == ConcatFnKind::none) | ||||||
1873 | //strlcpy, strlcat | ||||||
1874 | Result = strlRetVal; | ||||||
1875 | else | ||||||
1876 | Result = finalStrLength; | ||||||
1877 | } | ||||||
1878 | |||||||
1879 | assert(state)(static_cast <bool> (state) ? void (0) : __assert_fail ( "state", "clang/lib/StaticAnalyzer/Checkers/CStringChecker.cpp" , 1879, __extension__ __PRETTY_FUNCTION__)); | ||||||
1880 | |||||||
1881 | // If the destination is a MemRegion, try to check for a buffer overflow and | ||||||
1882 | // record the new string length. | ||||||
1883 | if (Optional<loc::MemRegionVal> dstRegVal = | ||||||
1884 | DstVal.getAs<loc::MemRegionVal>()) { | ||||||
1885 | QualType ptrTy = Dst.Expression->getType(); | ||||||
1886 | |||||||
1887 | // If we have an exact value on a bounded copy, use that to check for | ||||||
1888 | // overflows, rather than our estimate about how much is actually copied. | ||||||
1889 | if (Optional<NonLoc> maxLastNL = maxLastElementIndex.getAs<NonLoc>()) { | ||||||
1890 | SVal maxLastElement = | ||||||
1891 | svalBuilder.evalBinOpLN(state, BO_Add, *dstRegVal, *maxLastNL, ptrTy); | ||||||
1892 | |||||||
1893 | state = CheckLocation(C, state, Dst, maxLastElement, AccessKind::write); | ||||||
1894 | if (!state) | ||||||
1895 | return; | ||||||
1896 | } | ||||||
1897 | |||||||
1898 | // Then, if the final length is known... | ||||||
1899 | if (Optional<NonLoc> knownStrLength = finalStrLength.getAs<NonLoc>()) { | ||||||
1900 | SVal lastElement = svalBuilder.evalBinOpLN(state, BO_Add, *dstRegVal, | ||||||
1901 | *knownStrLength, ptrTy); | ||||||
1902 | |||||||
1903 | // ...and we haven't checked the bound, we'll check the actual copy. | ||||||
1904 | if (!boundWarning) { | ||||||
1905 | state = CheckLocation(C, state, Dst, lastElement, AccessKind::write); | ||||||
1906 | if (!state) | ||||||
1907 | return; | ||||||
1908 | } | ||||||
1909 | |||||||
1910 | // If this is a stpcpy-style copy, the last element is the return value. | ||||||
1911 | if (returnPtr && ReturnEnd) | ||||||
1912 | Result = lastElement; | ||||||
1913 | } | ||||||
1914 | |||||||
1915 | // Invalidate the destination (regular invalidation without pointer-escaping | ||||||
1916 | // the address of the top-level region). This must happen before we set the | ||||||
1917 | // C string length because invalidation will clear the length. | ||||||
1918 | // FIXME: Even if we can't perfectly model the copy, we should see if we | ||||||
1919 | // can use LazyCompoundVals to copy the source values into the destination. | ||||||
1920 | // This would probably remove any existing bindings past the end of the | ||||||
1921 | // string, but that's still an improvement over blank invalidation. | ||||||
1922 | state = InvalidateBuffer(C, state, Dst.Expression, *dstRegVal, | ||||||
1923 | /*IsSourceBuffer*/ false, nullptr); | ||||||
1924 | |||||||
1925 | // Invalidate the source (const-invalidation without const-pointer-escaping | ||||||
1926 | // the address of the top-level region). | ||||||
1927 | state = InvalidateBuffer(C, state, srcExpr.Expression, srcVal, | ||||||
1928 | /*IsSourceBuffer*/ true, nullptr); | ||||||
1929 | |||||||
1930 | // Set the C string length of the destination, if we know it. | ||||||
1931 | if (IsBounded && (appendK == ConcatFnKind::none)) { | ||||||
1932 | // strncpy is annoying in that it doesn't guarantee to null-terminate | ||||||
1933 | // the result string. If the original string didn't fit entirely inside | ||||||
1934 | // the bound (including the null-terminator), we don't know how long the | ||||||
1935 | // result is. | ||||||
1936 | if (amountCopied != strLength) | ||||||
1937 | finalStrLength = UnknownVal(); | ||||||
1938 | } | ||||||
1939 | state = setCStringLength(state, dstRegVal->getRegion(), finalStrLength); | ||||||
1940 | } | ||||||
1941 | |||||||
1942 | assert(state)(static_cast <bool> (state) ? void (0) : __assert_fail ( "state", "clang/lib/StaticAnalyzer/Checkers/CStringChecker.cpp" , 1942, __extension__ __PRETTY_FUNCTION__)); | ||||||
1943 | |||||||
1944 | if (returnPtr) { | ||||||
1945 | // If this is a stpcpy-style copy, but we were unable to check for a buffer | ||||||
1946 | // overflow, we still need a result. Conjure a return value. | ||||||
1947 | if (ReturnEnd && Result.isUnknown()) { | ||||||
1948 | Result = svalBuilder.conjureSymbolVal(nullptr, CE, LCtx, C.blockCount()); | ||||||
1949 | } | ||||||
1950 | } | ||||||
1951 | // Set the return value. | ||||||
1952 | state = state->BindExpr(CE, LCtx, Result); | ||||||
1953 | C.addTransition(state); | ||||||
1954 | } | ||||||
1955 | |||||||
1956 | void CStringChecker::evalStrcmp(CheckerContext &C, const CallExpr *CE) const { | ||||||
1957 | //int strcmp(const char *s1, const char *s2); | ||||||
1958 | evalStrcmpCommon(C, CE, /* IsBounded = */ false, /* IgnoreCase = */ false); | ||||||
1959 | } | ||||||
1960 | |||||||
1961 | void CStringChecker::evalStrncmp(CheckerContext &C, const CallExpr *CE) const { | ||||||
1962 | //int strncmp(const char *s1, const char *s2, size_t n); | ||||||
1963 | evalStrcmpCommon(C, CE, /* IsBounded = */ true, /* IgnoreCase = */ false); | ||||||
1964 | } | ||||||
1965 | |||||||
1966 | void CStringChecker::evalStrcasecmp(CheckerContext &C, | ||||||
1967 | const CallExpr *CE) const { | ||||||
1968 | //int strcasecmp(const char *s1, const char *s2); | ||||||
1969 | evalStrcmpCommon(C, CE, /* IsBounded = */ false, /* IgnoreCase = */ true); | ||||||
1970 | } | ||||||
1971 | |||||||
1972 | void CStringChecker::evalStrncasecmp(CheckerContext &C, | ||||||
1973 | const CallExpr *CE) const { | ||||||
1974 | //int strncasecmp(const char *s1, const char *s2, size_t n); | ||||||
1975 | evalStrcmpCommon(C, CE, /* IsBounded = */ true, /* IgnoreCase = */ true); | ||||||
1976 | } | ||||||
1977 | |||||||
1978 | void CStringChecker::evalStrcmpCommon(CheckerContext &C, const CallExpr *CE, | ||||||
1979 | bool IsBounded, bool IgnoreCase) const { | ||||||
1980 | CurrentFunctionDescription = "string comparison function"; | ||||||
1981 | ProgramStateRef state = C.getState(); | ||||||
1982 | const LocationContext *LCtx = C.getLocationContext(); | ||||||
1983 | |||||||
1984 | // Check that the first string is non-null | ||||||
1985 | AnyArgExpr Left = {CE->getArg(0), 0}; | ||||||
1986 | SVal LeftVal = state->getSVal(Left.Expression, LCtx); | ||||||
1987 | state = checkNonNull(C, state, Left, LeftVal); | ||||||
1988 | if (!state) | ||||||
1989 | return; | ||||||
1990 | |||||||
1991 | // Check that the second string is non-null. | ||||||
1992 | AnyArgExpr Right = {CE->getArg(1), 1}; | ||||||
1993 | SVal RightVal = state->getSVal(Right.Expression, LCtx); | ||||||
1994 | state = checkNonNull(C, state, Right, RightVal); | ||||||
1995 | if (!state) | ||||||
1996 | return; | ||||||
1997 | |||||||
1998 | // Get the string length of the first string or give up. | ||||||
1999 | SVal LeftLength = getCStringLength(C, state, Left.Expression, LeftVal); | ||||||
2000 | if (LeftLength.isUndef()) | ||||||
2001 | return; | ||||||
2002 | |||||||
2003 | // Get the string length of the second string or give up. | ||||||
2004 | SVal RightLength = getCStringLength(C, state, Right.Expression, RightVal); | ||||||
2005 | if (RightLength.isUndef()) | ||||||
2006 | return; | ||||||
2007 | |||||||
2008 | // If we know the two buffers are the same, we know the result is 0. | ||||||
2009 | // First, get the two buffers' addresses. Another checker will have already | ||||||
2010 | // made sure they're not undefined. | ||||||
2011 | DefinedOrUnknownSVal LV = LeftVal.castAs<DefinedOrUnknownSVal>(); | ||||||
2012 | DefinedOrUnknownSVal RV = RightVal.castAs<DefinedOrUnknownSVal>(); | ||||||
2013 | |||||||
2014 | // See if they are the same. | ||||||
2015 | SValBuilder &svalBuilder = C.getSValBuilder(); | ||||||
2016 | DefinedOrUnknownSVal SameBuf = svalBuilder.evalEQ(state, LV, RV); | ||||||
2017 | ProgramStateRef StSameBuf, StNotSameBuf; | ||||||
2018 | std::tie(StSameBuf, StNotSameBuf) = state->assume(SameBuf); | ||||||
2019 | |||||||
2020 | // If the two arguments might be the same buffer, we know the result is 0, | ||||||
2021 | // and we only need to check one size. | ||||||
2022 | if (StSameBuf) { | ||||||
2023 | StSameBuf = StSameBuf->BindExpr(CE, LCtx, | ||||||
2024 | svalBuilder.makeZeroVal(CE->getType())); | ||||||
2025 | C.addTransition(StSameBuf); | ||||||
2026 | |||||||
2027 | // If the two arguments are GUARANTEED to be the same, we're done! | ||||||
2028 | if (!StNotSameBuf) | ||||||
2029 | return; | ||||||
2030 | } | ||||||
2031 | |||||||
2032 | assert(StNotSameBuf)(static_cast <bool> (StNotSameBuf) ? void (0) : __assert_fail ("StNotSameBuf", "clang/lib/StaticAnalyzer/Checkers/CStringChecker.cpp" , 2032, __extension__ __PRETTY_FUNCTION__)); | ||||||
2033 | state = StNotSameBuf; | ||||||
2034 | |||||||
2035 | // At this point we can go about comparing the two buffers. | ||||||
2036 | // For now, we only do this if they're both known string literals. | ||||||
2037 | |||||||
2038 | // Attempt to extract string literals from both expressions. | ||||||
2039 | const StringLiteral *LeftStrLiteral = | ||||||
2040 | getCStringLiteral(C, state, Left.Expression, LeftVal); | ||||||
2041 | const StringLiteral *RightStrLiteral = | ||||||
2042 | getCStringLiteral(C, state, Right.Expression, RightVal); | ||||||
2043 | bool canComputeResult = false; | ||||||
2044 | SVal resultVal = svalBuilder.conjureSymbolVal(nullptr, CE, LCtx, | ||||||
2045 | C.blockCount()); | ||||||
2046 | |||||||
2047 | if (LeftStrLiteral && RightStrLiteral) { | ||||||
2048 | StringRef LeftStrRef = LeftStrLiteral->getString(); | ||||||
2049 | StringRef RightStrRef = RightStrLiteral->getString(); | ||||||
2050 | |||||||
2051 | if (IsBounded) { | ||||||
2052 | // Get the max number of characters to compare. | ||||||
2053 | const Expr *lenExpr = CE->getArg(2); | ||||||
2054 | SVal lenVal = state->getSVal(lenExpr, LCtx); | ||||||
2055 | |||||||
2056 | // If the length is known, we can get the right substrings. | ||||||
2057 | if (const llvm::APSInt *len = svalBuilder.getKnownValue(state, lenVal)) { | ||||||
2058 | // Create substrings of each to compare the prefix. | ||||||
2059 | LeftStrRef = LeftStrRef.substr(0, (size_t)len->getZExtValue()); | ||||||
2060 | RightStrRef = RightStrRef.substr(0, (size_t)len->getZExtValue()); | ||||||
2061 | canComputeResult = true; | ||||||
2062 | } | ||||||
2063 | } else { | ||||||
2064 | // This is a normal, unbounded strcmp. | ||||||
2065 | canComputeResult = true; | ||||||
2066 | } | ||||||
2067 | |||||||
2068 | if (canComputeResult) { | ||||||
2069 | // Real strcmp stops at null characters. | ||||||
2070 | size_t s1Term = LeftStrRef.find('\0'); | ||||||
2071 | if (s1Term != StringRef::npos) | ||||||
2072 | LeftStrRef = LeftStrRef.substr(0, s1Term); | ||||||
2073 | |||||||
2074 | size_t s2Term = RightStrRef.find('\0'); | ||||||
2075 | if (s2Term != StringRef::npos) | ||||||
2076 | RightStrRef = RightStrRef.substr(0, s2Term); | ||||||
2077 | |||||||
2078 | // Use StringRef's comparison methods to compute the actual result. | ||||||
2079 | int compareRes = IgnoreCase ? LeftStrRef.compare_insensitive(RightStrRef) | ||||||
2080 | : LeftStrRef.compare(RightStrRef); | ||||||
2081 | |||||||
2082 | // The strcmp function returns an integer greater than, equal to, or less | ||||||
2083 | // than zero, [c11, p7.24.4.2]. | ||||||
2084 | if (compareRes == 0) { | ||||||
2085 | resultVal = svalBuilder.makeIntVal(compareRes, CE->getType()); | ||||||
2086 | } | ||||||
2087 | else { | ||||||
2088 | DefinedSVal zeroVal = svalBuilder.makeIntVal(0, CE->getType()); | ||||||
2089 | // Constrain strcmp's result range based on the result of StringRef's | ||||||
2090 | // comparison methods. | ||||||
2091 | BinaryOperatorKind op = (compareRes == 1) ? BO_GT : BO_LT; | ||||||
2092 | SVal compareWithZero = | ||||||
2093 | svalBuilder.evalBinOp(state, op, resultVal, zeroVal, | ||||||
2094 | svalBuilder.getConditionType()); | ||||||
2095 | DefinedSVal compareWithZeroVal = compareWithZero.castAs<DefinedSVal>(); | ||||||
2096 | state = state->assume(compareWithZeroVal, true); | ||||||
2097 | } | ||||||
2098 | } | ||||||
2099 | } | ||||||
2100 | |||||||
2101 | state = state->BindExpr(CE, LCtx, resultVal); | ||||||
2102 | |||||||
2103 | // Record this as a possible path. | ||||||
2104 | C.addTransition(state); | ||||||
2105 | } | ||||||
2106 | |||||||
2107 | void CStringChecker::evalStrsep(CheckerContext &C, const CallExpr *CE) const { | ||||||
2108 | // char *strsep(char **stringp, const char *delim); | ||||||
2109 | // Verify whether the search string parameter matches the return type. | ||||||
2110 | SourceArgExpr SearchStrPtr = {CE->getArg(0), 0}; | ||||||
2111 | |||||||
2112 | QualType CharPtrTy = SearchStrPtr.Expression->getType()->getPointeeType(); | ||||||
2113 | if (CharPtrTy.isNull() || | ||||||
2114 | CE->getType().getUnqualifiedType() != CharPtrTy.getUnqualifiedType()) | ||||||
2115 | return; | ||||||
2116 | |||||||
2117 | CurrentFunctionDescription = "strsep()"; | ||||||
2118 | ProgramStateRef State = C.getState(); | ||||||
2119 | const LocationContext *LCtx = C.getLocationContext(); | ||||||
2120 | |||||||
2121 | // Check that the search string pointer is non-null (though it may point to | ||||||
2122 | // a null string). | ||||||
2123 | SVal SearchStrVal = State->getSVal(SearchStrPtr.Expression, LCtx); | ||||||
2124 | State = checkNonNull(C, State, SearchStrPtr, SearchStrVal); | ||||||
2125 | if (!State) | ||||||
2126 | return; | ||||||
2127 | |||||||
2128 | // Check that the delimiter string is non-null. | ||||||
2129 | AnyArgExpr DelimStr = {CE->getArg(1), 1}; | ||||||
2130 | SVal DelimStrVal = State->getSVal(DelimStr.Expression, LCtx); | ||||||
2131 | State = checkNonNull(C, State, DelimStr, DelimStrVal); | ||||||
2132 | if (!State) | ||||||
2133 | return; | ||||||
2134 | |||||||
2135 | SValBuilder &SVB = C.getSValBuilder(); | ||||||
2136 | SVal Result; | ||||||
2137 | if (Optional<Loc> SearchStrLoc = SearchStrVal.getAs<Loc>()) { | ||||||
2138 | // Get the current value of the search string pointer, as a char*. | ||||||
2139 | Result = State->getSVal(*SearchStrLoc, CharPtrTy); | ||||||
2140 | |||||||
2141 | // Invalidate the search string, representing the change of one delimiter | ||||||
2142 | // character to NUL. | ||||||
2143 | State = InvalidateBuffer(C, State, SearchStrPtr.Expression, Result, | ||||||
2144 | /*IsSourceBuffer*/ false, nullptr); | ||||||
2145 | |||||||
2146 | // Overwrite the search string pointer. The new value is either an address | ||||||
2147 | // further along in the same string, or NULL if there are no more tokens. | ||||||
2148 | State = State->bindLoc(*SearchStrLoc, | ||||||
2149 | SVB.conjureSymbolVal(getTag(), | ||||||
2150 | CE, | ||||||
2151 | LCtx, | ||||||
2152 | CharPtrTy, | ||||||
2153 | C.blockCount()), | ||||||
2154 | LCtx); | ||||||
2155 | } else { | ||||||
2156 | assert(SearchStrVal.isUnknown())(static_cast <bool> (SearchStrVal.isUnknown()) ? void ( 0) : __assert_fail ("SearchStrVal.isUnknown()", "clang/lib/StaticAnalyzer/Checkers/CStringChecker.cpp" , 2156, __extension__ __PRETTY_FUNCTION__)); | ||||||
2157 | // Conjure a symbolic value. It's the best we can do. | ||||||
2158 | Result = SVB.conjureSymbolVal(nullptr, CE, LCtx, C.blockCount()); | ||||||
2159 | } | ||||||
2160 | |||||||
2161 | // Set the return value, and finish. | ||||||
2162 | State = State->BindExpr(CE, LCtx, Result); | ||||||
2163 | C.addTransition(State); | ||||||
2164 | } | ||||||
2165 | |||||||
2166 | // These should probably be moved into a C++ standard library checker. | ||||||
2167 | void CStringChecker::evalStdCopy(CheckerContext &C, const CallExpr *CE) const { | ||||||
2168 | evalStdCopyCommon(C, CE); | ||||||
2169 | } | ||||||
2170 | |||||||
2171 | void CStringChecker::evalStdCopyBackward(CheckerContext &C, | ||||||
2172 | const CallExpr *CE) const { | ||||||
2173 | evalStdCopyCommon(C, CE); | ||||||
2174 | } | ||||||
2175 | |||||||
2176 | void CStringChecker::evalStdCopyCommon(CheckerContext &C, | ||||||
2177 | const CallExpr *CE) const { | ||||||
2178 | if (!CE->getArg(2)->getType()->isPointerType()) | ||||||
2179 | return; | ||||||
2180 | |||||||
2181 | ProgramStateRef State = C.getState(); | ||||||
2182 | |||||||
2183 | const LocationContext *LCtx = C.getLocationContext(); | ||||||
2184 | |||||||
2185 | // template <class _InputIterator, class _OutputIterator> | ||||||
2186 | // _OutputIterator | ||||||
2187 | // copy(_InputIterator __first, _InputIterator __last, | ||||||
2188 | // _OutputIterator __result) | ||||||
2189 | |||||||
2190 | // Invalidate the destination buffer | ||||||
2191 | const Expr *Dst = CE->getArg(2); | ||||||
2192 | SVal DstVal = State->getSVal(Dst, LCtx); | ||||||
2193 | State = InvalidateBuffer(C, State, Dst, DstVal, /*IsSource=*/false, | ||||||
2194 | /*Size=*/nullptr); | ||||||
2195 | |||||||
2196 | SValBuilder &SVB = C.getSValBuilder(); | ||||||
2197 | |||||||
2198 | SVal ResultVal = SVB.conjureSymbolVal(nullptr, CE, LCtx, C.blockCount()); | ||||||
2199 | State = State->BindExpr(CE, LCtx, ResultVal); | ||||||
2200 | |||||||
2201 | C.addTransition(State); | ||||||
2202 | } | ||||||
2203 | |||||||
2204 | void CStringChecker::evalMemset(CheckerContext &C, const CallExpr *CE) const { | ||||||
2205 | // void *memset(void *s, int c, size_t n); | ||||||
2206 | CurrentFunctionDescription = "memory set function"; | ||||||
2207 | |||||||
2208 | DestinationArgExpr Buffer = {CE->getArg(0), 0}; | ||||||
2209 | AnyArgExpr CharE = {CE->getArg(1), 1}; | ||||||
2210 | SizeArgExpr Size = {CE->getArg(2), 2}; | ||||||
2211 | |||||||
2212 | ProgramStateRef State = C.getState(); | ||||||
2213 | |||||||
2214 | // See if the size argument is zero. | ||||||
2215 | const LocationContext *LCtx = C.getLocationContext(); | ||||||
2216 | SVal SizeVal = C.getSVal(Size.Expression); | ||||||
2217 | QualType SizeTy = Size.Expression->getType(); | ||||||
2218 | |||||||
2219 | ProgramStateRef ZeroSize, NonZeroSize; | ||||||
2220 | std::tie(ZeroSize, NonZeroSize) = assumeZero(C, State, SizeVal, SizeTy); | ||||||
2221 | |||||||
2222 | // Get the value of the memory area. | ||||||
2223 | SVal BufferPtrVal = C.getSVal(Buffer.Expression); | ||||||
2224 | |||||||
2225 | // If the size is zero, there won't be any actual memory access, so | ||||||
2226 | // just bind the return value to the buffer and return. | ||||||
2227 | if (ZeroSize && !NonZeroSize) { | ||||||
2228 | ZeroSize = ZeroSize->BindExpr(CE, LCtx, BufferPtrVal); | ||||||
2229 | C.addTransition(ZeroSize); | ||||||
2230 | return; | ||||||
2231 | } | ||||||
2232 | |||||||
2233 | // Ensure the memory area is not null. | ||||||
2234 | // If it is NULL there will be a NULL pointer dereference. | ||||||
2235 | State = checkNonNull(C, NonZeroSize, Buffer, BufferPtrVal); | ||||||
2236 | if (!State) | ||||||
2237 | return; | ||||||
2238 | |||||||
2239 | State = CheckBufferAccess(C, State, Buffer, Size, AccessKind::write); | ||||||
2240 | if (!State) | ||||||
2241 | return; | ||||||
2242 | |||||||
2243 | // According to the values of the arguments, bind the value of the second | ||||||
2244 | // argument to the destination buffer and set string length, or just | ||||||
2245 | // invalidate the destination buffer. | ||||||
2246 | if (!memsetAux(Buffer.Expression, C.getSVal(CharE.Expression), | ||||||
2247 | Size.Expression, C, State)) | ||||||
2248 | return; | ||||||
2249 | |||||||
2250 | State = State->BindExpr(CE, LCtx, BufferPtrVal); | ||||||
2251 | C.addTransition(State); | ||||||
2252 | } | ||||||
2253 | |||||||
2254 | void CStringChecker::evalBzero(CheckerContext &C, const CallExpr *CE) const { | ||||||
2255 | CurrentFunctionDescription = "memory clearance function"; | ||||||
2256 | |||||||
2257 | DestinationArgExpr Buffer = {CE->getArg(0), 0}; | ||||||
2258 | SizeArgExpr Size = {CE->getArg(1), 1}; | ||||||
2259 | SVal Zero = C.getSValBuilder().makeZeroVal(C.getASTContext().IntTy); | ||||||
2260 | |||||||
2261 | ProgramStateRef State = C.getState(); | ||||||
2262 | |||||||
2263 | // See if the size argument is zero. | ||||||
2264 | SVal SizeVal = C.getSVal(Size.Expression); | ||||||
2265 | QualType SizeTy = Size.Expression->getType(); | ||||||
2266 | |||||||
2267 | ProgramStateRef StateZeroSize, StateNonZeroSize; | ||||||
2268 | std::tie(StateZeroSize, StateNonZeroSize) = | ||||||
2269 | assumeZero(C, State, SizeVal, SizeTy); | ||||||
2270 | |||||||
2271 | // If the size is zero, there won't be any actual memory access, | ||||||
2272 | // In this case we just return. | ||||||
2273 | if (StateZeroSize && !StateNonZeroSize) { | ||||||
2274 | C.addTransition(StateZeroSize); | ||||||
2275 | return; | ||||||
2276 | } | ||||||
2277 | |||||||
2278 | // Get the value of the memory area. | ||||||
2279 | SVal MemVal = C.getSVal(Buffer.Expression); | ||||||
2280 | |||||||
2281 | // Ensure the memory area is not null. | ||||||
2282 | // If it is NULL there will be a NULL pointer dereference. | ||||||
2283 | State = checkNonNull(C, StateNonZeroSize, Buffer, MemVal); | ||||||
2284 | if (!State) | ||||||
2285 | return; | ||||||
2286 | |||||||
2287 | State = CheckBufferAccess(C, State, Buffer, Size, AccessKind::write); | ||||||
2288 | if (!State) | ||||||
2289 | return; | ||||||
2290 | |||||||
2291 | if (!memsetAux(Buffer.Expression, Zero, Size.Expression, C, State)) | ||||||
2292 | return; | ||||||
2293 | |||||||
2294 | C.addTransition(State); | ||||||
2295 | } | ||||||
2296 | |||||||
2297 | //===----------------------------------------------------------------------===// | ||||||
2298 | // The driver method, and other Checker callbacks. | ||||||
2299 | //===----------------------------------------------------------------------===// | ||||||
2300 | |||||||
2301 | CStringChecker::FnCheck CStringChecker::identifyCall(const CallEvent &Call, | ||||||
2302 | CheckerContext &C) const { | ||||||
2303 | const auto *CE = dyn_cast_or_null<CallExpr>(Call.getOriginExpr()); | ||||||
2304 | if (!CE) | ||||||
2305 | return nullptr; | ||||||
2306 | |||||||
2307 | const FunctionDecl *FD = dyn_cast_or_null<FunctionDecl>(Call.getDecl()); | ||||||
2308 | if (!FD) | ||||||
2309 | return nullptr; | ||||||
2310 | |||||||
2311 | if (StdCopy.matches(Call)) | ||||||
2312 | return &CStringChecker::evalStdCopy; | ||||||
2313 | if (StdCopyBackward.matches(Call)) | ||||||
2314 | return &CStringChecker::evalStdCopyBackward; | ||||||
2315 | |||||||
2316 | // Pro-actively check that argument types are safe to do arithmetic upon. | ||||||
2317 | // We do not want to crash if someone accidentally passes a structure | ||||||
2318 | // into, say, a C++ overload of any of these functions. We could not check | ||||||
2319 | // that for std::copy because they may have arguments of other types. | ||||||
2320 | for (auto I : CE->arguments()) { | ||||||
2321 | QualType T = I->getType(); | ||||||
2322 | if (!T->isIntegralOrEnumerationType() && !T->isPointerType()) | ||||||
2323 | return nullptr; | ||||||
2324 | } | ||||||
2325 | |||||||
2326 | const FnCheck *Callback = Callbacks.lookup(Call); | ||||||
2327 | if (Callback) | ||||||
2328 | return *Callback; | ||||||
2329 | |||||||
2330 | return nullptr; | ||||||
2331 | } | ||||||
2332 | |||||||
2333 | bool CStringChecker::evalCall(const CallEvent &Call, CheckerContext &C) const { | ||||||
2334 | FnCheck Callback = identifyCall(Call, C); | ||||||
2335 | |||||||
2336 | // If the callee isn't a string function, let another checker handle it. | ||||||
2337 | if (!Callback) | ||||||
2338 | return false; | ||||||
2339 | |||||||
2340 | // Check and evaluate the call. | ||||||
2341 | const auto *CE = cast<CallExpr>(Call.getOriginExpr()); | ||||||
2342 | (this->*Callback)(C, CE); | ||||||
2343 | |||||||
2344 | // If the evaluate call resulted in no change, chain to the next eval call | ||||||
2345 | // handler. | ||||||
2346 | // Note, the custom CString evaluation calls assume that basic safety | ||||||
2347 | // properties are held. However, if the user chooses to turn off some of these | ||||||
2348 | // checks, we ignore the issues and leave the call evaluation to a generic | ||||||
2349 | // handler. | ||||||
2350 | return C.isDifferent(); | ||||||
2351 | } | ||||||
2352 | |||||||
2353 | void CStringChecker::checkPreStmt(const DeclStmt *DS, CheckerContext &C) const { | ||||||
2354 | // Record string length for char a[] = "abc"; | ||||||
2355 | ProgramStateRef state = C.getState(); | ||||||
2356 | |||||||
2357 | for (const auto *I : DS->decls()) { | ||||||
2358 | const VarDecl *D = dyn_cast<VarDecl>(I); | ||||||
2359 | if (!D) | ||||||
2360 | continue; | ||||||
2361 | |||||||
2362 | // FIXME: Handle array fields of structs. | ||||||
2363 | if (!D->getType()->isArrayType()) | ||||||
2364 | continue; | ||||||
2365 | |||||||
2366 | const Expr *Init = D->getInit(); | ||||||
2367 | if (!Init) | ||||||
2368 | continue; | ||||||
2369 | if (!isa<StringLiteral>(Init)) | ||||||
2370 | continue; | ||||||
2371 | |||||||
2372 | Loc VarLoc = state->getLValue(D, C.getLocationContext()); | ||||||
2373 | const MemRegion *MR = VarLoc.getAsRegion(); | ||||||
2374 | if (!MR) | ||||||
2375 | continue; | ||||||
2376 | |||||||
2377 | SVal StrVal = C.getSVal(Init); | ||||||
2378 | assert(StrVal.isValid() && "Initializer string is unknown or undefined")(static_cast <bool> (StrVal.isValid() && "Initializer string is unknown or undefined" ) ? void (0) : __assert_fail ("StrVal.isValid() && \"Initializer string is unknown or undefined\"" , "clang/lib/StaticAnalyzer/Checkers/CStringChecker.cpp", 2378 , __extension__ __PRETTY_FUNCTION__)); | ||||||
2379 | DefinedOrUnknownSVal strLength = | ||||||
2380 | getCStringLength(C, state, Init, StrVal).castAs<DefinedOrUnknownSVal>(); | ||||||
2381 | |||||||
2382 | state = state->set<CStringLength>(MR, strLength); | ||||||
2383 | } | ||||||
2384 | |||||||
2385 | C.addTransition(state); | ||||||
2386 | } | ||||||
2387 | |||||||
2388 | ProgramStateRef | ||||||
2389 | CStringChecker::checkRegionChanges(ProgramStateRef state, | ||||||
2390 | const InvalidatedSymbols *, | ||||||
2391 | ArrayRef<const MemRegion *> ExplicitRegions, | ||||||
2392 | ArrayRef<const MemRegion *> Regions, | ||||||
2393 | const LocationContext *LCtx, | ||||||
2394 | const CallEvent *Call) const { | ||||||
2395 | CStringLengthTy Entries = state->get<CStringLength>(); | ||||||
2396 | if (Entries.isEmpty()) | ||||||
2397 | return state; | ||||||
2398 | |||||||
2399 | llvm::SmallPtrSet<const MemRegion *, 8> Invalidated; | ||||||
2400 | llvm::SmallPtrSet<const MemRegion *, 32> SuperRegions; | ||||||
2401 | |||||||
2402 | // First build sets for the changed regions and their super-regions. | ||||||
2403 | for (ArrayRef<const MemRegion *>::iterator | ||||||
2404 | I = Regions.begin(), E = Regions.end(); I != E; ++I) { | ||||||
2405 | const MemRegion *MR = *I; | ||||||
2406 | Invalidated.insert(MR); | ||||||
2407 | |||||||
2408 | SuperRegions.insert(MR); | ||||||
2409 | while (const SubRegion *SR = dyn_cast<SubRegion>(MR)) { | ||||||
2410 | MR = SR->getSuperRegion(); | ||||||
2411 | SuperRegions.insert(MR); | ||||||
2412 | } | ||||||
2413 | } | ||||||
2414 | |||||||
2415 | CStringLengthTy::Factory &F = state->get_context<CStringLength>(); | ||||||
2416 | |||||||
2417 | // Then loop over the entries in the current state. | ||||||
2418 | for (CStringLengthTy::iterator I = Entries.begin(), | ||||||
2419 | E = Entries.end(); I != E; ++I) { | ||||||
2420 | const MemRegion *MR = I.getKey(); | ||||||
2421 | |||||||
2422 | // Is this entry for a super-region of a changed region? | ||||||
2423 | if (SuperRegions.count(MR)) { | ||||||
2424 | Entries = F.remove(Entries, MR); | ||||||
2425 | continue; | ||||||
2426 | } | ||||||
2427 | |||||||
2428 | // Is this entry for a sub-region of a changed region? | ||||||
2429 | const MemRegion *Super = MR; | ||||||
2430 | while (const SubRegion *SR = dyn_cast<SubRegion>(Super)) { | ||||||
2431 | Super = SR->getSuperRegion(); | ||||||
2432 | if (Invalidated.count(Super)) { | ||||||
2433 | Entries = F.remove(Entries, MR); | ||||||
2434 | break; | ||||||
2435 | } | ||||||
2436 | } | ||||||
2437 | } | ||||||
2438 | |||||||
2439 | return state->set<CStringLength>(Entries); | ||||||
2440 | } | ||||||
2441 | |||||||
2442 | void CStringChecker::checkLiveSymbols(ProgramStateRef state, | ||||||
2443 | SymbolReaper &SR) const { | ||||||
2444 | // Mark all symbols in our string length map as valid. | ||||||
2445 | CStringLengthTy Entries = state->get<CStringLength>(); | ||||||
2446 | |||||||
2447 | for (CStringLengthTy::iterator I = Entries.begin(), E = Entries.end(); | ||||||
2448 | I != E; ++I) { | ||||||
2449 | SVal Len = I.getData(); | ||||||
2450 | |||||||
2451 | for (SymExpr::symbol_iterator si = Len.symbol_begin(), | ||||||
2452 | se = Len.symbol_end(); si != se; ++si) | ||||||
2453 | SR.markInUse(*si); | ||||||
2454 | } | ||||||
2455 | } | ||||||
2456 | |||||||
2457 | void CStringChecker::checkDeadSymbols(SymbolReaper &SR, | ||||||
2458 | CheckerContext &C) const { | ||||||
2459 | ProgramStateRef state = C.getState(); | ||||||
2460 | CStringLengthTy Entries = state->get<CStringLength>(); | ||||||
2461 | if (Entries.isEmpty()) | ||||||
2462 | return; | ||||||
2463 | |||||||
2464 | CStringLengthTy::Factory &F = state->get_context<CStringLength>(); | ||||||
2465 | for (CStringLengthTy::iterator I = Entries.begin(), E = Entries.end(); | ||||||
2466 | I != E; ++I) { | ||||||
2467 | SVal Len = I.getData(); | ||||||
2468 | if (SymbolRef Sym = Len.getAsSymbol()) { | ||||||
2469 | if (SR.isDead(Sym)) | ||||||
2470 | Entries = F.remove(Entries, I.getKey()); | ||||||
2471 | } | ||||||
2472 | } | ||||||
2473 | |||||||
2474 | state = state->set<CStringLength>(Entries); | ||||||
2475 | C.addTransition(state); | ||||||
2476 | } | ||||||
2477 | |||||||
2478 | void ento::registerCStringModeling(CheckerManager &Mgr) { | ||||||
2479 | Mgr.registerChecker<CStringChecker>(); | ||||||
2480 | } | ||||||
2481 | |||||||
2482 | bool ento::shouldRegisterCStringModeling(const CheckerManager &mgr) { | ||||||
2483 | return true; | ||||||
2484 | } | ||||||
2485 | |||||||
2486 | #define REGISTER_CHECKER(name)void ento::registername(CheckerManager &mgr) { CStringChecker *checker = mgr.getChecker<CStringChecker>(); checker-> Filter.Checkname = true; checker->Filter.CheckNamename = mgr .getCurrentCheckerName(); } bool ento::shouldRegistername(const CheckerManager &mgr) { return true; } \ | ||||||
2487 | void ento::register##name(CheckerManager &mgr) { \ | ||||||
2488 | CStringChecker *checker = mgr.getChecker<CStringChecker>(); \ | ||||||
2489 | checker->Filter.Check##name = true; \ | ||||||
2490 | checker->Filter.CheckName##name = mgr.getCurrentCheckerName(); \ | ||||||
2491 | } \ | ||||||
2492 | \ | ||||||
2493 | bool ento::shouldRegister##name(const CheckerManager &mgr) { return true; } | ||||||
2494 | |||||||
2495 | REGISTER_CHECKER(CStringNullArg)void ento::registerCStringNullArg(CheckerManager &mgr) { CStringChecker *checker = mgr.getChecker<CStringChecker>(); checker-> Filter.CheckCStringNullArg = true; checker->Filter.CheckNameCStringNullArg = mgr.getCurrentCheckerName(); } bool ento::shouldRegisterCStringNullArg (const CheckerManager &mgr) { return true; } | ||||||
2496 | REGISTER_CHECKER(CStringOutOfBounds)void ento::registerCStringOutOfBounds(CheckerManager &mgr ) { CStringChecker *checker = mgr.getChecker<CStringChecker >(); checker->Filter.CheckCStringOutOfBounds = true; checker ->Filter.CheckNameCStringOutOfBounds = mgr.getCurrentCheckerName (); } bool ento::shouldRegisterCStringOutOfBounds(const CheckerManager &mgr) { return true; } | ||||||
2497 | REGISTER_CHECKER(CStringBufferOverlap)void ento::registerCStringBufferOverlap(CheckerManager &mgr ) { CStringChecker *checker = mgr.getChecker<CStringChecker >(); checker->Filter.CheckCStringBufferOverlap = true; checker ->Filter.CheckNameCStringBufferOverlap = mgr.getCurrentCheckerName (); } bool ento::shouldRegisterCStringBufferOverlap(const CheckerManager &mgr) { return true; } | ||||||
2498 | REGISTER_CHECKER(CStringNotNullTerm)void ento::registerCStringNotNullTerm(CheckerManager &mgr ) { CStringChecker *checker = mgr.getChecker<CStringChecker >(); checker->Filter.CheckCStringNotNullTerm = true; checker ->Filter.CheckNameCStringNotNullTerm = mgr.getCurrentCheckerName (); } bool ento::shouldRegisterCStringNotNullTerm(const CheckerManager &mgr) { return true; } | ||||||
2499 | REGISTER_CHECKER(CStringUninitializedRead)void ento::registerCStringUninitializedRead(CheckerManager & mgr) { CStringChecker *checker = mgr.getChecker<CStringChecker >(); checker->Filter.CheckCStringUninitializedRead = true ; checker->Filter.CheckNameCStringUninitializedRead = mgr. getCurrentCheckerName(); } bool ento::shouldRegisterCStringUninitializedRead (const CheckerManager &mgr) { return true; } |
1 | //== ProgramState.h - Path-sensitive "State" for tracking values -*- C++ -*--=// |
2 | // |
3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
4 | // See https://llvm.org/LICENSE.txt for license information. |
5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
6 | // |
7 | //===----------------------------------------------------------------------===// |
8 | // |
9 | // This file defines the state of the program along the analysisa path. |
10 | // |
11 | //===----------------------------------------------------------------------===// |
12 | |
13 | #ifndef LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_PROGRAMSTATE_H |
14 | #define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_PROGRAMSTATE_H |
15 | |
16 | #include "clang/Basic/LLVM.h" |
17 | #include "clang/StaticAnalyzer/Core/PathSensitive/ConstraintManager.h" |
18 | #include "clang/StaticAnalyzer/Core/PathSensitive/DynamicTypeInfo.h" |
19 | #include "clang/StaticAnalyzer/Core/PathSensitive/Environment.h" |
20 | #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState_Fwd.h" |
21 | #include "clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h" |
22 | #include "clang/StaticAnalyzer/Core/PathSensitive/Store.h" |
23 | #include "llvm/ADT/FoldingSet.h" |
24 | #include "llvm/ADT/ImmutableMap.h" |
25 | #include "llvm/Support/Allocator.h" |
26 | #include <utility> |
27 | |
28 | namespace llvm { |
29 | class APSInt; |
30 | } |
31 | |
32 | namespace clang { |
33 | class ASTContext; |
34 | |
35 | namespace ento { |
36 | |
37 | class AnalysisManager; |
38 | class CallEvent; |
39 | class CallEventManager; |
40 | |
41 | typedef std::unique_ptr<ConstraintManager>(*ConstraintManagerCreator)( |
42 | ProgramStateManager &, ExprEngine *); |
43 | typedef std::unique_ptr<StoreManager>(*StoreManagerCreator)( |
44 | ProgramStateManager &); |
45 | |
46 | //===----------------------------------------------------------------------===// |
47 | // ProgramStateTrait - Traits used by the Generic Data Map of a ProgramState. |
48 | //===----------------------------------------------------------------------===// |
49 | |
50 | template <typename T> struct ProgramStateTrait { |
51 | typedef typename T::data_type data_type; |
52 | static inline void *MakeVoidPtr(data_type D) { return (void*) D; } |
53 | static inline data_type MakeData(void *const* P) { |
54 | return P ? (data_type) *P : (data_type) 0; |
55 | } |
56 | }; |
57 | |
58 | /// \class ProgramState |
59 | /// ProgramState - This class encapsulates: |
60 | /// |
61 | /// 1. A mapping from expressions to values (Environment) |
62 | /// 2. A mapping from locations to values (Store) |
63 | /// 3. Constraints on symbolic values (GenericDataMap) |
64 | /// |
65 | /// Together these represent the "abstract state" of a program. |
66 | /// |
67 | /// ProgramState is intended to be used as a functional object; that is, |
68 | /// once it is created and made "persistent" in a FoldingSet, its |
69 | /// values will never change. |
70 | class ProgramState : public llvm::FoldingSetNode { |
71 | public: |
72 | typedef llvm::ImmutableSet<llvm::APSInt*> IntSetTy; |
73 | typedef llvm::ImmutableMap<void*, void*> GenericDataMap; |
74 | |
75 | private: |
76 | void operator=(const ProgramState& R) = delete; |
77 | |
78 | friend class ProgramStateManager; |
79 | friend class ExplodedGraph; |
80 | friend class ExplodedNode; |
81 | |
82 | ProgramStateManager *stateMgr; |
83 | Environment Env; // Maps a Stmt to its current SVal. |
84 | Store store; // Maps a location to its current value. |
85 | GenericDataMap GDM; // Custom data stored by a client of this class. |
86 | unsigned refCount; |
87 | |
88 | /// makeWithStore - Return a ProgramState with the same values as the current |
89 | /// state with the exception of using the specified Store. |
90 | ProgramStateRef makeWithStore(const StoreRef &store) const; |
91 | |
92 | void setStore(const StoreRef &storeRef); |
93 | |
94 | public: |
95 | /// This ctor is used when creating the first ProgramState object. |
96 | ProgramState(ProgramStateManager *mgr, const Environment& env, |
97 | StoreRef st, GenericDataMap gdm); |
98 | |
99 | /// Copy ctor - We must explicitly define this or else the "Next" ptr |
100 | /// in FoldingSetNode will also get copied. |
101 | ProgramState(const ProgramState &RHS); |
102 | |
103 | ~ProgramState(); |
104 | |
105 | int64_t getID() const; |
106 | |
107 | /// Return the ProgramStateManager associated with this state. |
108 | ProgramStateManager &getStateManager() const { |
109 | return *stateMgr; |
110 | } |
111 | |
112 | AnalysisManager &getAnalysisManager() const; |
113 | |
114 | /// Return the ConstraintManager. |
115 | ConstraintManager &getConstraintManager() const; |
116 | |
117 | /// getEnvironment - Return the environment associated with this state. |
118 | /// The environment is the mapping from expressions to values. |
119 | const Environment& getEnvironment() const { return Env; } |
120 | |
121 | /// Return the store associated with this state. The store |
122 | /// is a mapping from locations to values. |
123 | Store getStore() const { return store; } |
124 | |
125 | |
126 | /// getGDM - Return the generic data map associated with this state. |
127 | GenericDataMap getGDM() const { return GDM; } |
128 | |
129 | void setGDM(GenericDataMap gdm) { GDM = gdm; } |
130 | |
131 | /// Profile - Profile the contents of a ProgramState object for use in a |
132 | /// FoldingSet. Two ProgramState objects are considered equal if they |
133 | /// have the same Environment, Store, and GenericDataMap. |
134 | static void Profile(llvm::FoldingSetNodeID& ID, const ProgramState *V) { |
135 | V->Env.Profile(ID); |
136 | ID.AddPointer(V->store); |
137 | V->GDM.Profile(ID); |
138 | } |
139 | |
140 | /// Profile - Used to profile the contents of this object for inclusion |
141 | /// in a FoldingSet. |
142 | void Profile(llvm::FoldingSetNodeID& ID) const { |
143 | Profile(ID, this); |
144 | } |
145 | |
146 | BasicValueFactory &getBasicVals() const; |
147 | SymbolManager &getSymbolManager() const; |
148 | |
149 | //==---------------------------------------------------------------------==// |
150 | // Constraints on values. |
151 | //==---------------------------------------------------------------------==// |
152 | // |
153 | // Each ProgramState records constraints on symbolic values. These constraints |
154 | // are managed using the ConstraintManager associated with a ProgramStateManager. |
155 | // As constraints gradually accrue on symbolic values, added constraints |
156 | // may conflict and indicate that a state is infeasible (as no real values |
157 | // could satisfy all the constraints). This is the principal mechanism |
158 | // for modeling path-sensitivity in ExprEngine/ProgramState. |
159 | // |
160 | // Various "assume" methods form the interface for adding constraints to |
161 | // symbolic values. A call to 'assume' indicates an assumption being placed |
162 | // on one or symbolic values. 'assume' methods take the following inputs: |
163 | // |
164 | // (1) A ProgramState object representing the current state. |
165 | // |
166 | // (2) The assumed constraint (which is specific to a given "assume" method). |
167 | // |
168 | // (3) A binary value "Assumption" that indicates whether the constraint is |
169 | // assumed to be true or false. |
170 | // |
171 | // The output of "assume*" is a new ProgramState object with the added constraints. |
172 | // If no new state is feasible, NULL is returned. |
173 | // |
174 | |
175 | /// Assumes that the value of \p cond is zero (if \p assumption is "false") |
176 | /// or non-zero (if \p assumption is "true"). |
177 | /// |
178 | /// This returns a new state with the added constraint on \p cond. |
179 | /// If no new state is feasible, NULL is returned. |
180 | LLVM_NODISCARD[[clang::warn_unused_result]] ProgramStateRef assume(DefinedOrUnknownSVal cond, |
181 | bool assumption) const; |
182 | |
183 | /// Assumes both "true" and "false" for \p cond, and returns both |
184 | /// corresponding states (respectively). |
185 | /// |
186 | /// This is more efficient than calling assume() twice. Note that one (but not |
187 | /// both) of the returned states may be NULL. |
188 | LLVM_NODISCARD[[clang::warn_unused_result]] std::pair<ProgramStateRef, ProgramStateRef> |
189 | assume(DefinedOrUnknownSVal cond) const; |
190 | |
191 | LLVM_NODISCARD[[clang::warn_unused_result]] ProgramStateRef |
192 | assumeInBound(DefinedOrUnknownSVal idx, DefinedOrUnknownSVal upperBound, |
193 | bool assumption, QualType IndexType = QualType()) const; |
194 | |
195 | /// Assumes that the value of \p Val is bounded with [\p From; \p To] |
196 | /// (if \p assumption is "true") or it is fully out of this range |
197 | /// (if \p assumption is "false"). |
198 | /// |
199 | /// This returns a new state with the added constraint on \p cond. |
200 | /// If no new state is feasible, NULL is returned. |
201 | LLVM_NODISCARD[[clang::warn_unused_result]] ProgramStateRef assumeInclusiveRange(DefinedOrUnknownSVal Val, |
202 | const llvm::APSInt &From, |
203 | const llvm::APSInt &To, |
204 | bool assumption) const; |
205 | |
206 | /// Assumes given range both "true" and "false" for \p Val, and returns both |
207 | /// corresponding states (respectively). |
208 | /// |
209 | /// This is more efficient than calling assume() twice. Note that one (but not |
210 | /// both) of the returned states may be NULL. |
211 | LLVM_NODISCARD[[clang::warn_unused_result]] std::pair<ProgramStateRef, ProgramStateRef> |
212 | assumeInclusiveRange(DefinedOrUnknownSVal Val, const llvm::APSInt &From, |
213 | const llvm::APSInt &To) const; |
214 | |
215 | /// Check if the given SVal is not constrained to zero and is not |
216 | /// a zero constant. |
217 | ConditionTruthVal isNonNull(SVal V) const; |
218 | |
219 | /// Check if the given SVal is constrained to zero or is a zero |
220 | /// constant. |
221 | ConditionTruthVal isNull(SVal V) const; |
222 | |
223 | /// \return Whether values \p Lhs and \p Rhs are equal. |
224 | ConditionTruthVal areEqual(SVal Lhs, SVal Rhs) const; |
225 | |
226 | /// Utility method for getting regions. |
227 | const VarRegion* getRegion(const VarDecl *D, const LocationContext *LC) const; |
228 | |
229 | //==---------------------------------------------------------------------==// |
230 | // Binding and retrieving values to/from the environment and symbolic store. |
231 | //==---------------------------------------------------------------------==// |
232 | |
233 | /// Create a new state by binding the value 'V' to the statement 'S' in the |
234 | /// state's environment. |
235 | LLVM_NODISCARD[[clang::warn_unused_result]] ProgramStateRef BindExpr(const Stmt *S, |
236 | const LocationContext *LCtx, SVal V, |
237 | bool Invalidate = true) const; |
238 | |
239 | LLVM_NODISCARD[[clang::warn_unused_result]] ProgramStateRef bindLoc(Loc location, SVal V, |
240 | const LocationContext *LCtx, |
241 | bool notifyChanges = true) const; |
242 | |
243 | LLVM_NODISCARD[[clang::warn_unused_result]] ProgramStateRef bindLoc(SVal location, SVal V, |
244 | const LocationContext *LCtx) const; |
245 | |
246 | /// Initializes the region of memory represented by \p loc with an initial |
247 | /// value. Once initialized, all values loaded from any sub-regions of that |
248 | /// region will be equal to \p V, unless overwritten later by the program. |
249 | /// This method should not be used on regions that are already initialized. |
250 | /// If you need to indicate that memory contents have suddenly become unknown |
251 | /// within a certain region of memory, consider invalidateRegions(). |
252 | LLVM_NODISCARD[[clang::warn_unused_result]] ProgramStateRef |
253 | bindDefaultInitial(SVal loc, SVal V, const LocationContext *LCtx) const; |
254 | |
255 | /// Performs C++ zero-initialization procedure on the region of memory |
256 | /// represented by \p loc. |
257 | LLVM_NODISCARD[[clang::warn_unused_result]] ProgramStateRef |
258 | bindDefaultZero(SVal loc, const LocationContext *LCtx) const; |
259 | |
260 | LLVM_NODISCARD[[clang::warn_unused_result]] ProgramStateRef killBinding(Loc LV) const; |
261 | |
262 | /// Returns the state with bindings for the given regions |
263 | /// cleared from the store. |
264 | /// |
265 | /// Optionally invalidates global regions as well. |
266 | /// |
267 | /// \param Regions the set of regions to be invalidated. |
268 | /// \param E the expression that caused the invalidation. |
269 | /// \param BlockCount The number of times the current basic block has been |
270 | // visited. |
271 | /// \param CausesPointerEscape the flag is set to true when |
272 | /// the invalidation entails escape of a symbol (representing a |
273 | /// pointer). For example, due to it being passed as an argument in a |
274 | /// call. |
275 | /// \param IS the set of invalidated symbols. |
276 | /// \param Call if non-null, the invalidated regions represent parameters to |
277 | /// the call and should be considered directly invalidated. |
278 | /// \param ITraits information about special handling for a particular |
279 | /// region/symbol. |
280 | LLVM_NODISCARD[[clang::warn_unused_result]] ProgramStateRef |
281 | invalidateRegions(ArrayRef<const MemRegion *> Regions, const Expr *E, |
282 | unsigned BlockCount, const LocationContext *LCtx, |
283 | bool CausesPointerEscape, InvalidatedSymbols *IS = nullptr, |
284 | const CallEvent *Call = nullptr, |
285 | RegionAndSymbolInvalidationTraits *ITraits = nullptr) const; |
286 | |
287 | LLVM_NODISCARD[[clang::warn_unused_result]] ProgramStateRef |
288 | invalidateRegions(ArrayRef<SVal> Regions, const Expr *E, |
289 | unsigned BlockCount, const LocationContext *LCtx, |
290 | bool CausesPointerEscape, InvalidatedSymbols *IS = nullptr, |
291 | const CallEvent *Call = nullptr, |
292 | RegionAndSymbolInvalidationTraits *ITraits = nullptr) const; |
293 | |
294 | /// enterStackFrame - Returns the state for entry to the given stack frame, |
295 | /// preserving the current state. |
296 | LLVM_NODISCARD[[clang::warn_unused_result]] ProgramStateRef enterStackFrame( |
297 | const CallEvent &Call, const StackFrameContext *CalleeCtx) const; |
298 | |
299 | /// Return the value of 'self' if available in the given context. |
300 | SVal getSelfSVal(const LocationContext *LC) const; |
301 | |
302 | /// Get the lvalue for a base class object reference. |
303 | Loc getLValue(const CXXBaseSpecifier &BaseSpec, const SubRegion *Super) const; |
304 | |
305 | /// Get the lvalue for a base class object reference. |
306 | Loc getLValue(const CXXRecordDecl *BaseClass, const SubRegion *Super, |
307 | bool IsVirtual) const; |
308 | |
309 | /// Get the lvalue for a parameter. |
310 | Loc getLValue(const Expr *Call, unsigned Index, |
311 | const LocationContext *LC) const; |
312 | |
313 | /// Get the lvalue for a variable reference. |
314 | Loc getLValue(const VarDecl *D, const LocationContext *LC) const; |
315 | |
316 | Loc getLValue(const CompoundLiteralExpr *literal, |
317 | const LocationContext *LC) const; |
318 | |
319 | /// Get the lvalue for an ivar reference. |
320 | SVal getLValue(const ObjCIvarDecl *decl, SVal base) const; |
321 | |
322 | /// Get the lvalue for a field reference. |
323 | SVal getLValue(const FieldDecl *decl, SVal Base) const; |
324 | |
325 | /// Get the lvalue for an indirect field reference. |
326 | SVal getLValue(const IndirectFieldDecl *decl, SVal Base) const; |
327 | |
328 | /// Get the lvalue for an array index. |
329 | SVal getLValue(QualType ElementType, SVal Idx, SVal Base) const; |
330 | |
331 | /// Returns the SVal bound to the statement 'S' in the state's environment. |
332 | SVal getSVal(const Stmt *S, const LocationContext *LCtx) const; |
333 | |
334 | SVal getSValAsScalarOrLoc(const Stmt *Ex, const LocationContext *LCtx) const; |
335 | |
336 | /// Return the value bound to the specified location. |
337 | /// Returns UnknownVal() if none found. |
338 | SVal getSVal(Loc LV, QualType T = QualType()) const; |
339 | |
340 | /// Returns the "raw" SVal bound to LV before any value simplfication. |
341 | SVal getRawSVal(Loc LV, QualType T= QualType()) const; |
342 | |
343 | /// Return the value bound to the specified location. |
344 | /// Returns UnknownVal() if none found. |
345 | SVal getSVal(const MemRegion* R, QualType T = QualType()) const; |
346 | |
347 | /// Return the value bound to the specified location, assuming |
348 | /// that the value is a scalar integer or an enumeration or a pointer. |
349 | /// Returns UnknownVal() if none found or the region is not known to hold |
350 | /// a value of such type. |
351 | SVal getSValAsScalarOrLoc(const MemRegion *R) const; |
352 | |
353 | using region_iterator = const MemRegion **; |
354 | |
355 | /// Visits the symbols reachable from the given SVal using the provided |
356 | /// SymbolVisitor. |
357 | /// |
358 | /// This is a convenience API. Consider using ScanReachableSymbols class |
359 | /// directly when making multiple scans on the same state with the same |
360 | /// visitor to avoid repeated initialization cost. |
361 | /// \sa ScanReachableSymbols |
362 | bool scanReachableSymbols(SVal val, SymbolVisitor& visitor) const; |
363 | |
364 | /// Visits the symbols reachable from the regions in the given |
365 | /// MemRegions range using the provided SymbolVisitor. |
366 | bool scanReachableSymbols(llvm::iterator_range<region_iterator> Reachable, |
367 | SymbolVisitor &visitor) const; |
368 | |
369 | template <typename CB> CB scanReachableSymbols(SVal val) const; |
370 | template <typename CB> CB |
371 | scanReachableSymbols(llvm::iterator_range<region_iterator> Reachable) const; |
372 | |
373 | //==---------------------------------------------------------------------==// |
374 | // Accessing the Generic Data Map (GDM). |
375 | //==---------------------------------------------------------------------==// |
376 | |
377 | void *const* FindGDM(void *K) const; |
378 | |
379 | template <typename T> |
380 | LLVM_NODISCARD[[clang::warn_unused_result]] ProgramStateRef |
381 | add(typename ProgramStateTrait<T>::key_type K) const; |
382 | |
383 | template <typename T> |
384 | typename ProgramStateTrait<T>::data_type |
385 | get() const { |
386 | return ProgramStateTrait<T>::MakeData(FindGDM(ProgramStateTrait<T>::GDMIndex())); |
387 | } |
388 | |
389 | template<typename T> |
390 | typename ProgramStateTrait<T>::lookup_type |
391 | get(typename ProgramStateTrait<T>::key_type key) const { |
392 | void *const* d = FindGDM(ProgramStateTrait<T>::GDMIndex()); |
393 | return ProgramStateTrait<T>::Lookup(ProgramStateTrait<T>::MakeData(d), key); |
394 | } |
395 | |
396 | template <typename T> |
397 | typename ProgramStateTrait<T>::context_type get_context() const; |
398 | |
399 | template <typename T> |
400 | LLVM_NODISCARD[[clang::warn_unused_result]] ProgramStateRef |
401 | remove(typename ProgramStateTrait<T>::key_type K) const; |
402 | |
403 | template <typename T> |
404 | LLVM_NODISCARD[[clang::warn_unused_result]] ProgramStateRef |
405 | remove(typename ProgramStateTrait<T>::key_type K, |
406 | typename ProgramStateTrait<T>::context_type C) const; |
407 | |
408 | template <typename T> LLVM_NODISCARD[[clang::warn_unused_result]] ProgramStateRef remove() const; |
409 | |
410 | template <typename T> |
411 | LLVM_NODISCARD[[clang::warn_unused_result]] ProgramStateRef |
412 | set(typename ProgramStateTrait<T>::data_type D) const; |
413 | |
414 | template <typename T> |
415 | LLVM_NODISCARD[[clang::warn_unused_result]] ProgramStateRef |
416 | set(typename ProgramStateTrait<T>::key_type K, |
417 | typename ProgramStateTrait<T>::value_type E) const; |
418 | |
419 | template <typename T> |
420 | LLVM_NODISCARD[[clang::warn_unused_result]] ProgramStateRef |
421 | set(typename ProgramStateTrait<T>::key_type K, |
422 | typename ProgramStateTrait<T>::value_type E, |
423 | typename ProgramStateTrait<T>::context_type C) const; |
424 | |
425 | template<typename T> |
426 | bool contains(typename ProgramStateTrait<T>::key_type key) const { |
427 | void *const* d = FindGDM(ProgramStateTrait<T>::GDMIndex()); |
428 | return ProgramStateTrait<T>::Contains(ProgramStateTrait<T>::MakeData(d), key); |
429 | } |
430 | |
431 | // Pretty-printing. |
432 | void printJson(raw_ostream &Out, const LocationContext *LCtx = nullptr, |
433 | const char *NL = "\n", unsigned int Space = 0, |
434 | bool IsDot = false) const; |
435 | |
436 | void printDOT(raw_ostream &Out, const LocationContext *LCtx = nullptr, |
437 | unsigned int Space = 0) const; |
438 | |
439 | void dump() const; |
440 | |
441 | private: |
442 | friend void ProgramStateRetain(const ProgramState *state); |
443 | friend void ProgramStateRelease(const ProgramState *state); |
444 | |
445 | /// \sa invalidateValues() |
446 | /// \sa invalidateRegions() |
447 | ProgramStateRef |
448 | invalidateRegionsImpl(ArrayRef<SVal> Values, |
449 | const Expr *E, unsigned BlockCount, |
450 | const LocationContext *LCtx, |
451 | bool ResultsInSymbolEscape, |
452 | InvalidatedSymbols *IS, |
453 | RegionAndSymbolInvalidationTraits *HTraits, |
454 | const CallEvent *Call) const; |
455 | }; |
456 | |
457 | //===----------------------------------------------------------------------===// |
458 | // ProgramStateManager - Factory object for ProgramStates. |
459 | //===----------------------------------------------------------------------===// |
460 | |
461 | class ProgramStateManager { |
462 | friend class ProgramState; |
463 | friend void ProgramStateRelease(const ProgramState *state); |
464 | private: |
465 | /// Eng - The ExprEngine that owns this state manager. |
466 | ExprEngine *Eng; /* Can be null. */ |
467 | |
468 | EnvironmentManager EnvMgr; |
469 | std::unique_ptr<StoreManager> StoreMgr; |
470 | std::unique_ptr<ConstraintManager> ConstraintMgr; |
471 | |
472 | ProgramState::GenericDataMap::Factory GDMFactory; |
473 | |
474 | typedef llvm::DenseMap<void*,std::pair<void*,void (*)(void*)> > GDMContextsTy; |
475 | GDMContextsTy GDMContexts; |
476 | |
477 | /// StateSet - FoldingSet containing all the states created for analyzing |
478 | /// a particular function. This is used to unique states. |
479 | llvm::FoldingSet<ProgramState> StateSet; |
480 | |
481 | /// Object that manages the data for all created SVals. |
482 | std::unique_ptr<SValBuilder> svalBuilder; |
483 | |
484 | /// Manages memory for created CallEvents. |
485 | std::unique_ptr<CallEventManager> CallEventMgr; |
486 | |
487 | /// A BumpPtrAllocator to allocate states. |
488 | llvm::BumpPtrAllocator &Alloc; |
489 | |
490 | /// A vector of ProgramStates that we can reuse. |
491 | std::vector<ProgramState *> freeStates; |
492 | |
493 | public: |
494 | ProgramStateManager(ASTContext &Ctx, |
495 | StoreManagerCreator CreateStoreManager, |
496 | ConstraintManagerCreator CreateConstraintManager, |
497 | llvm::BumpPtrAllocator& alloc, |
498 | ExprEngine *expreng); |
499 | |
500 | ~ProgramStateManager(); |
501 | |
502 | ProgramStateRef getInitialState(const LocationContext *InitLoc); |
503 | |
504 | ASTContext &getContext() { return svalBuilder->getContext(); } |
505 | const ASTContext &getContext() const { return svalBuilder->getContext(); } |
506 | |
507 | BasicValueFactory &getBasicVals() { |
508 | return svalBuilder->getBasicValueFactory(); |
509 | } |
510 | |
511 | SValBuilder &getSValBuilder() { |
512 | return *svalBuilder; |
513 | } |
514 | |
515 | const SValBuilder &getSValBuilder() const { |
516 | return *svalBuilder; |
517 | } |
518 | |
519 | SymbolManager &getSymbolManager() { |
520 | return svalBuilder->getSymbolManager(); |
521 | } |
522 | const SymbolManager &getSymbolManager() const { |
523 | return svalBuilder->getSymbolManager(); |
524 | } |
525 | |
526 | llvm::BumpPtrAllocator& getAllocator() { return Alloc; } |
527 | |
528 | MemRegionManager& getRegionManager() { |
529 | return svalBuilder->getRegionManager(); |
530 | } |
531 | const MemRegionManager &getRegionManager() const { |
532 | return svalBuilder->getRegionManager(); |
533 | } |
534 | |
535 | CallEventManager &getCallEventManager() { return *CallEventMgr; } |
536 | |
537 | StoreManager &getStoreManager() { return *StoreMgr; } |
538 | ConstraintManager &getConstraintManager() { return *ConstraintMgr; } |
539 | ExprEngine &getOwningEngine() { return *Eng; } |
540 | |
541 | ProgramStateRef |
542 | removeDeadBindingsFromEnvironmentAndStore(ProgramStateRef St, |
543 | const StackFrameContext *LCtx, |
544 | SymbolReaper &SymReaper); |
545 | |
546 | public: |
547 | |
548 | SVal ArrayToPointer(Loc Array, QualType ElementTy) { |
549 | return StoreMgr->ArrayToPointer(Array, ElementTy); |
550 | } |
551 | |
552 | // Methods that manipulate the GDM. |
553 | ProgramStateRef addGDM(ProgramStateRef St, void *Key, void *Data); |
554 | ProgramStateRef removeGDM(ProgramStateRef state, void *Key); |
555 | |
556 | // Methods that query & manipulate the Store. |
557 | |
558 | void iterBindings(ProgramStateRef state, StoreManager::BindingsHandler& F) { |
559 | StoreMgr->iterBindings(state->getStore(), F); |
560 | } |
561 | |
562 | ProgramStateRef getPersistentState(ProgramState &Impl); |
563 | ProgramStateRef getPersistentStateWithGDM(ProgramStateRef FromState, |
564 | ProgramStateRef GDMState); |
565 | |
566 | bool haveEqualConstraints(ProgramStateRef S1, ProgramStateRef S2) const { |
567 | return ConstraintMgr->haveEqualConstraints(S1, S2); |
568 | } |
569 | |
570 | bool haveEqualEnvironments(ProgramStateRef S1, ProgramStateRef S2) const { |
571 | return S1->Env == S2->Env; |
572 | } |
573 | |
574 | bool haveEqualStores(ProgramStateRef S1, ProgramStateRef S2) const { |
575 | return S1->store == S2->store; |
576 | } |
577 | |
578 | //==---------------------------------------------------------------------==// |
579 | // Generic Data Map methods. |
580 | //==---------------------------------------------------------------------==// |
581 | // |
582 | // ProgramStateManager and ProgramState support a "generic data map" that allows |
583 | // different clients of ProgramState objects to embed arbitrary data within a |
584 | // ProgramState object. The generic data map is essentially an immutable map |
585 | // from a "tag" (that acts as the "key" for a client) and opaque values. |
586 | // Tags/keys and values are simply void* values. The typical way that clients |
587 | // generate unique tags are by taking the address of a static variable. |
588 | // Clients are responsible for ensuring that data values referred to by a |
589 | // the data pointer are immutable (and thus are essentially purely functional |
590 | // data). |
591 | // |
592 | // The templated methods below use the ProgramStateTrait<T> class |
593 | // to resolve keys into the GDM and to return data values to clients. |
594 | // |
595 | |
596 | // Trait based GDM dispatch. |
597 | template <typename T> |
598 | ProgramStateRef set(ProgramStateRef st, typename ProgramStateTrait<T>::data_type D) { |
599 | return addGDM(st, ProgramStateTrait<T>::GDMIndex(), |
600 | ProgramStateTrait<T>::MakeVoidPtr(D)); |
601 | } |
602 | |
603 | template<typename T> |
604 | ProgramStateRef set(ProgramStateRef st, |
605 | typename ProgramStateTrait<T>::key_type K, |
606 | typename ProgramStateTrait<T>::value_type V, |
607 | typename ProgramStateTrait<T>::context_type C) { |
608 | |
609 | return addGDM(st, ProgramStateTrait<T>::GDMIndex(), |
610 | ProgramStateTrait<T>::MakeVoidPtr(ProgramStateTrait<T>::Set(st->get<T>(), K, V, C))); |
611 | } |
612 | |
613 | template <typename T> |
614 | ProgramStateRef add(ProgramStateRef st, |
615 | typename ProgramStateTrait<T>::key_type K, |
616 | typename ProgramStateTrait<T>::context_type C) { |
617 | return addGDM(st, ProgramStateTrait<T>::GDMIndex(), |
618 | ProgramStateTrait<T>::MakeVoidPtr(ProgramStateTrait<T>::Add(st->get<T>(), K, C))); |
619 | } |
620 | |
621 | template <typename T> |
622 | ProgramStateRef remove(ProgramStateRef st, |
623 | typename ProgramStateTrait<T>::key_type K, |
624 | typename ProgramStateTrait<T>::context_type C) { |
625 | |
626 | return addGDM(st, ProgramStateTrait<T>::GDMIndex(), |
627 | ProgramStateTrait<T>::MakeVoidPtr(ProgramStateTrait<T>::Remove(st->get<T>(), K, C))); |
628 | } |
629 | |
630 | template <typename T> |
631 | ProgramStateRef remove(ProgramStateRef st) { |
632 | return removeGDM(st, ProgramStateTrait<T>::GDMIndex()); |
633 | } |
634 | |
635 | void *FindGDMContext(void *index, |
636 | void *(*CreateContext)(llvm::BumpPtrAllocator&), |
637 | void (*DeleteContext)(void*)); |
638 | |
639 | template <typename T> |
640 | typename ProgramStateTrait<T>::context_type get_context() { |
641 | void *p = FindGDMContext(ProgramStateTrait<T>::GDMIndex(), |
642 | ProgramStateTrait<T>::CreateContext, |
643 | ProgramStateTrait<T>::DeleteContext); |
644 | |
645 | return ProgramStateTrait<T>::MakeContext(p); |
646 | } |
647 | }; |
648 | |
649 | |
650 | //===----------------------------------------------------------------------===// |
651 | // Out-of-line method definitions for ProgramState. |
652 | //===----------------------------------------------------------------------===// |
653 | |
654 | inline ConstraintManager &ProgramState::getConstraintManager() const { |
655 | return stateMgr->getConstraintManager(); |
656 | } |
657 | |
658 | inline const VarRegion* ProgramState::getRegion(const VarDecl *D, |
659 | const LocationContext *LC) const |
660 | { |
661 | return getStateManager().getRegionManager().getVarRegion(D, LC); |
662 | } |
663 | |
664 | inline ProgramStateRef ProgramState::assume(DefinedOrUnknownSVal Cond, |
665 | bool Assumption) const { |
666 | if (Cond.isUnknown()) |
667 | return this; |
668 | |
669 | return getStateManager().ConstraintMgr |
670 | ->assume(this, Cond.castAs<DefinedSVal>(), Assumption); |
671 | } |
672 | |
673 | inline std::pair<ProgramStateRef , ProgramStateRef > |
674 | ProgramState::assume(DefinedOrUnknownSVal Cond) const { |
675 | if (Cond.isUnknown()) |
676 | return std::make_pair(this, this); |
677 | |
678 | return getStateManager().ConstraintMgr |
679 | ->assumeDual(this, Cond.castAs<DefinedSVal>()); |
680 | } |
681 | |
682 | inline ProgramStateRef ProgramState::assumeInclusiveRange( |
683 | DefinedOrUnknownSVal Val, const llvm::APSInt &From, const llvm::APSInt &To, |
684 | bool Assumption) const { |
685 | if (Val.isUnknown()) |
686 | return this; |
687 | |
688 | assert(Val.getAs<NonLoc>() && "Only NonLocs are supported!")(static_cast <bool> (Val.getAs<NonLoc>() && "Only NonLocs are supported!") ? void (0) : __assert_fail ("Val.getAs<NonLoc>() && \"Only NonLocs are supported!\"" , "clang/include/clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" , 688, __extension__ __PRETTY_FUNCTION__)); |
689 | |
690 | return getStateManager().ConstraintMgr->assumeInclusiveRange( |
691 | this, Val.castAs<NonLoc>(), From, To, Assumption); |
692 | } |
693 | |
694 | inline std::pair<ProgramStateRef, ProgramStateRef> |
695 | ProgramState::assumeInclusiveRange(DefinedOrUnknownSVal Val, |
696 | const llvm::APSInt &From, |
697 | const llvm::APSInt &To) const { |
698 | if (Val.isUnknown()) |
699 | return std::make_pair(this, this); |
700 | |
701 | assert(Val.getAs<NonLoc>() && "Only NonLocs are supported!")(static_cast <bool> (Val.getAs<NonLoc>() && "Only NonLocs are supported!") ? void (0) : __assert_fail ("Val.getAs<NonLoc>() && \"Only NonLocs are supported!\"" , "clang/include/clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" , 701, __extension__ __PRETTY_FUNCTION__)); |
702 | |
703 | return getStateManager().ConstraintMgr->assumeInclusiveRangeDual( |
704 | this, Val.castAs<NonLoc>(), From, To); |
705 | } |
706 | |
707 | inline ProgramStateRef ProgramState::bindLoc(SVal LV, SVal V, const LocationContext *LCtx) const { |
708 | if (Optional<Loc> L = LV.getAs<Loc>()) |
709 | return bindLoc(*L, V, LCtx); |
710 | return this; |
711 | } |
712 | |
713 | inline Loc ProgramState::getLValue(const CXXBaseSpecifier &BaseSpec, |
714 | const SubRegion *Super) const { |
715 | const auto *Base = BaseSpec.getType()->getAsCXXRecordDecl(); |
716 | return loc::MemRegionVal( |
717 | getStateManager().getRegionManager().getCXXBaseObjectRegion( |
718 | Base, Super, BaseSpec.isVirtual())); |
719 | } |
720 | |
721 | inline Loc ProgramState::getLValue(const CXXRecordDecl *BaseClass, |
722 | const SubRegion *Super, |
723 | bool IsVirtual) const { |
724 | return loc::MemRegionVal( |
725 | getStateManager().getRegionManager().getCXXBaseObjectRegion( |
726 | BaseClass, Super, IsVirtual)); |
727 | } |
728 | |
729 | inline Loc ProgramState::getLValue(const VarDecl *VD, |
730 | const LocationContext *LC) const { |
731 | return getStateManager().StoreMgr->getLValueVar(VD, LC); |
732 | } |
733 | |
734 | inline Loc ProgramState::getLValue(const CompoundLiteralExpr *literal, |
735 | const LocationContext *LC) const { |
736 | return getStateManager().StoreMgr->getLValueCompoundLiteral(literal, LC); |
737 | } |
738 | |
739 | inline SVal ProgramState::getLValue(const ObjCIvarDecl *D, SVal Base) const { |
740 | return getStateManager().StoreMgr->getLValueIvar(D, Base); |
741 | } |
742 | |
743 | inline SVal ProgramState::getLValue(const FieldDecl *D, SVal Base) const { |
744 | return getStateManager().StoreMgr->getLValueField(D, Base); |
745 | } |
746 | |
747 | inline SVal ProgramState::getLValue(const IndirectFieldDecl *D, |
748 | SVal Base) const { |
749 | StoreManager &SM = *getStateManager().StoreMgr; |
750 | for (const auto *I : D->chain()) { |
751 | Base = SM.getLValueField(cast<FieldDecl>(I), Base); |
752 | } |
753 | |
754 | return Base; |
755 | } |
756 | |
757 | inline SVal ProgramState::getLValue(QualType ElementType, SVal Idx, SVal Base) const{ |
758 | if (Optional<NonLoc> N = Idx.getAs<NonLoc>()) |
759 | return getStateManager().StoreMgr->getLValueElement(ElementType, *N, Base); |
760 | return UnknownVal(); |
761 | } |
762 | |
763 | inline SVal ProgramState::getSVal(const Stmt *Ex, |
764 | const LocationContext *LCtx) const{ |
765 | return Env.getSVal(EnvironmentEntry(Ex, LCtx), |
766 | *getStateManager().svalBuilder); |
767 | } |
768 | |
769 | inline SVal |
770 | ProgramState::getSValAsScalarOrLoc(const Stmt *S, |
771 | const LocationContext *LCtx) const { |
772 | if (const Expr *Ex = dyn_cast<Expr>(S)) { |
773 | QualType T = Ex->getType(); |
774 | if (Ex->isGLValue() || Loc::isLocType(T) || |
775 | T->isIntegralOrEnumerationType()) |
776 | return getSVal(S, LCtx); |
777 | } |
778 | |
779 | return UnknownVal(); |
780 | } |
781 | |
782 | inline SVal ProgramState::getRawSVal(Loc LV, QualType T) const { |
783 | return getStateManager().StoreMgr->getBinding(getStore(), LV, T); |
784 | } |
785 | |
786 | inline SVal ProgramState::getSVal(const MemRegion* R, QualType T) const { |
787 | return getStateManager().StoreMgr->getBinding(getStore(), |
788 | loc::MemRegionVal(R), |
789 | T); |
790 | } |
791 | |
792 | inline BasicValueFactory &ProgramState::getBasicVals() const { |
793 | return getStateManager().getBasicVals(); |
794 | } |
795 | |
796 | inline SymbolManager &ProgramState::getSymbolManager() const { |
797 | return getStateManager().getSymbolManager(); |
798 | } |
799 | |
800 | template<typename T> |
801 | ProgramStateRef ProgramState::add(typename ProgramStateTrait<T>::key_type K) const { |
802 | return getStateManager().add<T>(this, K, get_context<T>()); |
803 | } |
804 | |
805 | template <typename T> |
806 | typename ProgramStateTrait<T>::context_type ProgramState::get_context() const { |
807 | return getStateManager().get_context<T>(); |
808 | } |
809 | |
810 | template<typename T> |
811 | ProgramStateRef ProgramState::remove(typename ProgramStateTrait<T>::key_type K) const { |
812 | return getStateManager().remove<T>(this, K, get_context<T>()); |
813 | } |
814 | |
815 | template<typename T> |
816 | ProgramStateRef ProgramState::remove(typename ProgramStateTrait<T>::key_type K, |
817 | typename ProgramStateTrait<T>::context_type C) const { |
818 | return getStateManager().remove<T>(this, K, C); |
819 | } |
820 | |
821 | template <typename T> |
822 | ProgramStateRef ProgramState::remove() const { |
823 | return getStateManager().remove<T>(this); |
824 | } |
825 | |
826 | template<typename T> |
827 | ProgramStateRef ProgramState::set(typename ProgramStateTrait<T>::data_type D) const { |
828 | return getStateManager().set<T>(this, D); |
829 | } |
830 | |
831 | template<typename T> |
832 | ProgramStateRef ProgramState::set(typename ProgramStateTrait<T>::key_type K, |
833 | typename ProgramStateTrait<T>::value_type E) const { |
834 | return getStateManager().set<T>(this, K, E, get_context<T>()); |
835 | } |
836 | |
837 | template<typename T> |
838 | ProgramStateRef ProgramState::set(typename ProgramStateTrait<T>::key_type K, |
839 | typename ProgramStateTrait<T>::value_type E, |
840 | typename ProgramStateTrait<T>::context_type C) const { |
841 | return getStateManager().set<T>(this, K, E, C); |
842 | } |
843 | |
844 | template <typename CB> |
845 | CB ProgramState::scanReachableSymbols(SVal val) const { |
846 | CB cb(this); |
847 | scanReachableSymbols(val, cb); |
848 | return cb; |
849 | } |
850 | |
851 | template <typename CB> |
852 | CB ProgramState::scanReachableSymbols( |
853 | llvm::iterator_range<region_iterator> Reachable) const { |
854 | CB cb(this); |
855 | scanReachableSymbols(Reachable, cb); |
856 | return cb; |
857 | } |
858 | |
859 | /// \class ScanReachableSymbols |
860 | /// A utility class that visits the reachable symbols using a custom |
861 | /// SymbolVisitor. Terminates recursive traversal when the visitor function |
862 | /// returns false. |
863 | class ScanReachableSymbols { |
864 | typedef llvm::DenseSet<const void*> VisitedItems; |
865 | |
866 | VisitedItems visited; |
867 | ProgramStateRef state; |
868 | SymbolVisitor &visitor; |
869 | public: |
870 | ScanReachableSymbols(ProgramStateRef st, SymbolVisitor &v) |
871 | : state(std::move(st)), visitor(v) {} |
872 | |
873 | bool scan(nonloc::LazyCompoundVal val); |
874 | bool scan(nonloc::CompoundVal val); |
875 | bool scan(SVal val); |
876 | bool scan(const MemRegion *R); |
877 | bool scan(const SymExpr *sym); |
878 | }; |
879 | |
880 | } // end ento namespace |
881 | |
882 | } // end clang namespace |
883 | |
884 | #endif |
1 | //==- llvm/ADT/IntrusiveRefCntPtr.h - Smart Refcounting Pointer --*- C++ -*-==// |
2 | // |
3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
4 | // See https://llvm.org/LICENSE.txt for license information. |
5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
6 | // |
7 | //===----------------------------------------------------------------------===// |
8 | /// |
9 | /// \file |
10 | /// This file defines the RefCountedBase, ThreadSafeRefCountedBase, and |
11 | /// IntrusiveRefCntPtr classes. |
12 | /// |
13 | /// IntrusiveRefCntPtr is a smart pointer to an object which maintains a |
14 | /// reference count. (ThreadSafe)RefCountedBase is a mixin class that adds a |
15 | /// refcount member variable and methods for updating the refcount. An object |
16 | /// that inherits from (ThreadSafe)RefCountedBase deletes itself when its |
17 | /// refcount hits zero. |
18 | /// |
19 | /// For example: |
20 | /// |
21 | /// ``` |
22 | /// class MyClass : public RefCountedBase<MyClass> {}; |
23 | /// |
24 | /// void foo() { |
25 | /// // Constructing an IntrusiveRefCntPtr increases the pointee's refcount |
26 | /// // by 1 (from 0 in this case). |
27 | /// IntrusiveRefCntPtr<MyClass> Ptr1(new MyClass()); |
28 | /// |
29 | /// // Copying an IntrusiveRefCntPtr increases the pointee's refcount by 1. |
30 | /// IntrusiveRefCntPtr<MyClass> Ptr2(Ptr1); |
31 | /// |
32 | /// // Constructing an IntrusiveRefCntPtr has no effect on the object's |
33 | /// // refcount. After a move, the moved-from pointer is null. |
34 | /// IntrusiveRefCntPtr<MyClass> Ptr3(std::move(Ptr1)); |
35 | /// assert(Ptr1 == nullptr); |
36 | /// |
37 | /// // Clearing an IntrusiveRefCntPtr decreases the pointee's refcount by 1. |
38 | /// Ptr2.reset(); |
39 | /// |
40 | /// // The object deletes itself when we return from the function, because |
41 | /// // Ptr3's destructor decrements its refcount to 0. |
42 | /// } |
43 | /// ``` |
44 | /// |
45 | /// You can use IntrusiveRefCntPtr with isa<T>(), dyn_cast<T>(), etc.: |
46 | /// |
47 | /// ``` |
48 | /// IntrusiveRefCntPtr<MyClass> Ptr(new MyClass()); |
49 | /// OtherClass *Other = dyn_cast<OtherClass>(Ptr); // Ptr.get() not required |
50 | /// ``` |
51 | /// |
52 | /// IntrusiveRefCntPtr works with any class that |
53 | /// |
54 | /// - inherits from (ThreadSafe)RefCountedBase, |
55 | /// - has Retain() and Release() methods, or |
56 | /// - specializes IntrusiveRefCntPtrInfo. |
57 | /// |
58 | //===----------------------------------------------------------------------===// |
59 | |
60 | #ifndef LLVM_ADT_INTRUSIVEREFCNTPTR_H |
61 | #define LLVM_ADT_INTRUSIVEREFCNTPTR_H |
62 | |
63 | #include <atomic> |
64 | #include <cassert> |
65 | #include <cstddef> |
66 | #include <memory> |
67 | |
68 | namespace llvm { |
69 | |
70 | /// A CRTP mixin class that adds reference counting to a type. |
71 | /// |
72 | /// The lifetime of an object which inherits from RefCountedBase is managed by |
73 | /// calls to Release() and Retain(), which increment and decrement the object's |
74 | /// refcount, respectively. When a Release() call decrements the refcount to 0, |
75 | /// the object deletes itself. |
76 | template <class Derived> class RefCountedBase { |
77 | mutable unsigned RefCount = 0; |
78 | |
79 | protected: |
80 | RefCountedBase() = default; |
81 | RefCountedBase(const RefCountedBase &) {} |
82 | RefCountedBase &operator=(const RefCountedBase &) = delete; |
83 | |
84 | #ifndef NDEBUG |
85 | ~RefCountedBase() { |
86 | assert(RefCount == 0 &&(static_cast <bool> (RefCount == 0 && "Destruction occurred when there are still references to this." ) ? void (0) : __assert_fail ("RefCount == 0 && \"Destruction occurred when there are still references to this.\"" , "llvm/include/llvm/ADT/IntrusiveRefCntPtr.h", 87, __extension__ __PRETTY_FUNCTION__)) |
87 | "Destruction occurred when there are still references to this.")(static_cast <bool> (RefCount == 0 && "Destruction occurred when there are still references to this." ) ? void (0) : __assert_fail ("RefCount == 0 && \"Destruction occurred when there are still references to this.\"" , "llvm/include/llvm/ADT/IntrusiveRefCntPtr.h", 87, __extension__ __PRETTY_FUNCTION__)); |
88 | } |
89 | #else |
90 | // Default the destructor in release builds, A trivial destructor may enable |
91 | // better codegen. |
92 | ~RefCountedBase() = default; |
93 | #endif |
94 | |
95 | public: |
96 | void Retain() const { ++RefCount; } |
97 | |
98 | void Release() const { |
99 | assert(RefCount > 0 && "Reference count is already zero.")(static_cast <bool> (RefCount > 0 && "Reference count is already zero." ) ? void (0) : __assert_fail ("RefCount > 0 && \"Reference count is already zero.\"" , "llvm/include/llvm/ADT/IntrusiveRefCntPtr.h", 99, __extension__ __PRETTY_FUNCTION__)); |
100 | if (--RefCount == 0) |
101 | delete static_cast<const Derived *>(this); |
102 | } |
103 | }; |
104 | |
105 | /// A thread-safe version of \c RefCountedBase. |
106 | template <class Derived> class ThreadSafeRefCountedBase { |
107 | mutable std::atomic<int> RefCount{0}; |
108 | |
109 | protected: |
110 | ThreadSafeRefCountedBase() = default; |
111 | ThreadSafeRefCountedBase(const ThreadSafeRefCountedBase &) {} |
112 | ThreadSafeRefCountedBase & |
113 | operator=(const ThreadSafeRefCountedBase &) = delete; |
114 | |
115 | #ifndef NDEBUG |
116 | ~ThreadSafeRefCountedBase() { |
117 | assert(RefCount == 0 &&(static_cast <bool> (RefCount == 0 && "Destruction occurred when there are still references to this." ) ? void (0) : __assert_fail ("RefCount == 0 && \"Destruction occurred when there are still references to this.\"" , "llvm/include/llvm/ADT/IntrusiveRefCntPtr.h", 118, __extension__ __PRETTY_FUNCTION__)) |
118 | "Destruction occurred when there are still references to this.")(static_cast <bool> (RefCount == 0 && "Destruction occurred when there are still references to this." ) ? void (0) : __assert_fail ("RefCount == 0 && \"Destruction occurred when there are still references to this.\"" , "llvm/include/llvm/ADT/IntrusiveRefCntPtr.h", 118, __extension__ __PRETTY_FUNCTION__)); |
119 | } |
120 | #else |
121 | // Default the destructor in release builds, A trivial destructor may enable |
122 | // better codegen. |
123 | ~ThreadSafeRefCountedBase() = default; |
124 | #endif |
125 | |
126 | public: |
127 | void Retain() const { RefCount.fetch_add(1, std::memory_order_relaxed); } |
128 | |
129 | void Release() const { |
130 | int NewRefCount = RefCount.fetch_sub(1, std::memory_order_acq_rel) - 1; |
131 | assert(NewRefCount >= 0 && "Reference count was already zero.")(static_cast <bool> (NewRefCount >= 0 && "Reference count was already zero." ) ? void (0) : __assert_fail ("NewRefCount >= 0 && \"Reference count was already zero.\"" , "llvm/include/llvm/ADT/IntrusiveRefCntPtr.h", 131, __extension__ __PRETTY_FUNCTION__)); |
132 | if (NewRefCount == 0) |
133 | delete static_cast<const Derived *>(this); |
134 | } |
135 | }; |
136 | |
137 | /// Class you can specialize to provide custom retain/release functionality for |
138 | /// a type. |
139 | /// |
140 | /// Usually specializing this class is not necessary, as IntrusiveRefCntPtr |
141 | /// works with any type which defines Retain() and Release() functions -- you |
142 | /// can define those functions yourself if RefCountedBase doesn't work for you. |
143 | /// |
144 | /// One case when you might want to specialize this type is if you have |
145 | /// - Foo.h defines type Foo and includes Bar.h, and |
146 | /// - Bar.h uses IntrusiveRefCntPtr<Foo> in inline functions. |
147 | /// |
148 | /// Because Foo.h includes Bar.h, Bar.h can't include Foo.h in order to pull in |
149 | /// the declaration of Foo. Without the declaration of Foo, normally Bar.h |
150 | /// wouldn't be able to use IntrusiveRefCntPtr<Foo>, which wants to call |
151 | /// T::Retain and T::Release. |
152 | /// |
153 | /// To resolve this, Bar.h could include a third header, FooFwd.h, which |
154 | /// forward-declares Foo and specializes IntrusiveRefCntPtrInfo<Foo>. Then |
155 | /// Bar.h could use IntrusiveRefCntPtr<Foo>, although it still couldn't call any |
156 | /// functions on Foo itself, because Foo would be an incomplete type. |
157 | template <typename T> struct IntrusiveRefCntPtrInfo { |
158 | static void retain(T *obj) { obj->Retain(); } |
159 | static void release(T *obj) { obj->Release(); } |
160 | }; |
161 | |
162 | /// A smart pointer to a reference-counted object that inherits from |
163 | /// RefCountedBase or ThreadSafeRefCountedBase. |
164 | /// |
165 | /// This class increments its pointee's reference count when it is created, and |
166 | /// decrements its refcount when it's destroyed (or is changed to point to a |
167 | /// different object). |
168 | template <typename T> class IntrusiveRefCntPtr { |
169 | T *Obj = nullptr; |
170 | |
171 | public: |
172 | using element_type = T; |
173 | |
174 | explicit IntrusiveRefCntPtr() = default; |
175 | IntrusiveRefCntPtr(T *obj) : Obj(obj) { retain(); } |
176 | IntrusiveRefCntPtr(const IntrusiveRefCntPtr &S) : Obj(S.Obj) { retain(); } |
177 | IntrusiveRefCntPtr(IntrusiveRefCntPtr &&S) : Obj(S.Obj) { S.Obj = nullptr; } |
178 | |
179 | template <class X, |
180 | std::enable_if_t<std::is_convertible<X *, T *>::value, bool> = true> |
181 | IntrusiveRefCntPtr(IntrusiveRefCntPtr<X> S) : Obj(S.get()) { |
182 | S.Obj = nullptr; |
183 | } |
184 | |
185 | template <class X, |
186 | std::enable_if_t<std::is_convertible<X *, T *>::value, bool> = true> |
187 | IntrusiveRefCntPtr(std::unique_ptr<X> S) : Obj(S.release()) { |
188 | retain(); |
189 | } |
190 | |
191 | ~IntrusiveRefCntPtr() { release(); } |
192 | |
193 | IntrusiveRefCntPtr &operator=(IntrusiveRefCntPtr S) { |
194 | swap(S); |
195 | return *this; |
196 | } |
197 | |
198 | T &operator*() const { return *Obj; } |
199 | T *operator->() const { return Obj; } |
200 | T *get() const { return Obj; } |
201 | explicit operator bool() const { return Obj; } |
202 | |
203 | void swap(IntrusiveRefCntPtr &other) { |
204 | T *tmp = other.Obj; |
205 | other.Obj = Obj; |
206 | Obj = tmp; |
207 | } |
208 | |
209 | void reset() { |
210 | release(); |
211 | Obj = nullptr; |
212 | } |
213 | |
214 | void resetWithoutRelease() { Obj = nullptr; } |
215 | |
216 | private: |
217 | void retain() { |
218 | if (Obj) |
219 | IntrusiveRefCntPtrInfo<T>::retain(Obj); |
220 | } |
221 | |
222 | void release() { |
223 | if (Obj) |
224 | IntrusiveRefCntPtrInfo<T>::release(Obj); |
225 | } |
226 | |
227 | template <typename X> friend class IntrusiveRefCntPtr; |
228 | }; |
229 | |
230 | template <class T, class U> |
231 | inline bool operator==(const IntrusiveRefCntPtr<T> &A, |
232 | const IntrusiveRefCntPtr<U> &B) { |
233 | return A.get() == B.get(); |
234 | } |
235 | |
236 | template <class T, class U> |
237 | inline bool operator!=(const IntrusiveRefCntPtr<T> &A, |
238 | const IntrusiveRefCntPtr<U> &B) { |
239 | return A.get() != B.get(); |
240 | } |
241 | |
242 | template <class T, class U> |
243 | inline bool operator==(const IntrusiveRefCntPtr<T> &A, U *B) { |
244 | return A.get() == B; |
245 | } |
246 | |
247 | template <class T, class U> |
248 | inline bool operator!=(const IntrusiveRefCntPtr<T> &A, U *B) { |
249 | return A.get() != B; |
250 | } |
251 | |
252 | template <class T, class U> |
253 | inline bool operator==(T *A, const IntrusiveRefCntPtr<U> &B) { |
254 | return A == B.get(); |
255 | } |
256 | |
257 | template <class T, class U> |
258 | inline bool operator!=(T *A, const IntrusiveRefCntPtr<U> &B) { |
259 | return A != B.get(); |
260 | } |
261 | |
262 | template <class T> |
263 | bool operator==(std::nullptr_t, const IntrusiveRefCntPtr<T> &B) { |
264 | return !B; |
265 | } |
266 | |
267 | template <class T> |
268 | bool operator==(const IntrusiveRefCntPtr<T> &A, std::nullptr_t B) { |
269 | return B == A; |
270 | } |
271 | |
272 | template <class T> |
273 | bool operator!=(std::nullptr_t A, const IntrusiveRefCntPtr<T> &B) { |
274 | return !(A == B); |
275 | } |
276 | |
277 | template <class T> |
278 | bool operator!=(const IntrusiveRefCntPtr<T> &A, std::nullptr_t B) { |
279 | return !(A == B); |
280 | } |
281 | |
282 | // Make IntrusiveRefCntPtr work with dyn_cast, isa, and the other idioms from |
283 | // Casting.h. |
284 | template <typename From> struct simplify_type; |
285 | |
286 | template <class T> struct simplify_type<IntrusiveRefCntPtr<T>> { |
287 | using SimpleType = T *; |
288 | |
289 | static SimpleType getSimplifiedValue(IntrusiveRefCntPtr<T> &Val) { |
290 | return Val.get(); |
291 | } |
292 | }; |
293 | |
294 | template <class T> struct simplify_type<const IntrusiveRefCntPtr<T>> { |
295 | using SimpleType = /*const*/ T *; |
296 | |
297 | static SimpleType getSimplifiedValue(const IntrusiveRefCntPtr<T> &Val) { |
298 | return Val.get(); |
299 | } |
300 | }; |
301 | |
302 | /// Factory function for creating intrusive ref counted pointers. |
303 | template <typename T, typename... Args> |
304 | IntrusiveRefCntPtr<T> makeIntrusiveRefCnt(Args &&...A) { |
305 | return IntrusiveRefCntPtr<T>(new T(std::forward<Args>(A)...)); |
306 | } |
307 | |
308 | } // end namespace llvm |
309 | |
310 | #endif // LLVM_ADT_INTRUSIVEREFCNTPTR_H |