[analyzer] DynamicSize: Remove 'getSizeInElements()' from store

[Charusso]

Summary

This patch uses the new DynamicSize.cpp to serve dynamic information.
Previously it was static and probably imprecise data.

[Charusso]

The [1] patch which introduced such static element-count data has only one test case in outofbound.c:

void f2() {
  int *p = malloc(12);
  p[3] = 4; // expected-warning{{Access out-of-bound array element (buffer overflow)}}
}

which probably wanted to be (int *)malloc(12), but in both ways the warning occurs, which is problematic. This is the first step to mitigate that issue.
[1] https://github.com/llvm/llvm-project/commit/228b0d4defb85b2e7acbb642b9f0b5dfc49d3fe7

[NoQ]

This is the first step to mitigate that issue.

What's the issue?

clang/lib/StaticAnalyzer/Core/DynamicSize.cpp

38–40

Even if the size is not concrete, you can ask SValBuilder to perform the division. It's going to be a symbolic expression which we won't be able to work with anyway, but these days we believe that it's still worth it, in hope that our constraint solver eventually gets better.

[Charusso]

• Fix.

[Charusso]

In D69599#1730707, @NoQ wrote:

This is the first step to mitigate that issue.

What's the issue?

Well, after I mentioned an issue I have realized the somewhat path-insensitive getSizeInElements() does not touch the (void *) return value. Basically the expression int *foo = malloc() could not compile, and I had felt that the assumptions about the overflow are wrong. Now I see that none of the overflow tests would compile, so I think we just bypass a cast here-and-there. Therefore there is no issue, just I was surprised.

clang/lib/StaticAnalyzer/Core/DynamicSize.cpp

38–40

Good idea, thanks!

[NoQ]

clang/lib/StaticAnalyzer/Core/DynamicSize.cpp

40–48

And then remove the manual division.

[Charusso]

clang/lib/StaticAnalyzer/Core/DynamicSize.cpp

40–48

Hmpf.

Failing Tests (7):
    Clang :: Analysis/misc-ps-region-store.m
    Clang :: Analysis/mpichecker.cpp
    Clang :: Analysis/outofbound.c
    Clang :: Analysis/rdar-6541136-region.c
    Clang :: Analysis/return-ptr-range.cpp
    Clang :: Analysis/track-control-dependency-conditions.cpp
    Clang :: Analysis/uninit-vals.c

I would pick that solution because it may be a tiny-bit faster, and then later on investigate this issue when we model more about dynamic sizes.

[NoQ]

clang/lib/StaticAnalyzer/Core/DynamicSize.cpp

40–48

Soooooo what does it tell us about the correctness of the new evalBinOp-based solution?

[Charusso]

• Old division swapped by evalBinOp.

[Charusso]

Thanks, now it is cool!

clang/lib/StaticAnalyzer/Core/DynamicSize.cpp

40–48

So, when I tried to inject an APSInt it converted to 0 so division by zero made that. I felt that the implicit conversion is wonky, but dividing by 0, ugh.

[NoQ]

clang/lib/StaticAnalyzer/Core/DynamicSize.cpp

40–48

Yay, great job figuring this out!

Also the conversion wasn't implicit; you explicitly specified llvm::APSInt(...). I agree that this constructor is evil, though.

44–47

I'd rather do a castAs here. Allocating a region of garbage size should be an immediate warning; supplying a zero-size ElementTy should be an immediate crash; in all other cases the result of division must be defined.

[Charusso]

• Done.

[Charusso]

Thanks for the review!

clang/lib/StaticAnalyzer/Core/DynamicSize.cpp

40–48

getQuantity() retuns a QuantityType, but now I see: typedef int64_t QuantityType, so I was fooled.

[ASDenysPetrov]

@Charusso
I think this patch may fix this bug https://bugs.llvm.org/show_bug.cgi?id=25284
Could you please verify and close it if so?
At least I couldn't reproduce it on the latest build.

clang/include/clang/StaticAnalyzer/Core/PathSensitive/DynamicSize.h

 
 namespace clang {
 namespace ento {
 
 /// Get the stored dynamic size for the region \p MR.
 DefinedOrUnknownSVal getDynamicSize(ProgramStateRef State, const MemRegion *MR,
                                     SValBuilder &SVB);
 
+/// Get the stored element count of the region \p MR.
+DefinedOrUnknownSVal getDynamicElementCount(ProgramStateRef State,
+                                            const MemRegion *MR,
+                                            SValBuilder &SVB,
+                                            QualType ElementTy);
+
 } // namespace ento
 } // namespace clang
 
 #endif // LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_DYNAMICSIZE_H

clang/include/clang/StaticAnalyzer/Core/PathSensitive/Store.h

public:
   virtual SVal getLValueIvar(const ObjCIvarDecl *decl, SVal base);
 
   virtual SVal getLValueField(const FieldDecl *D, SVal Base) {
     return getLValueFieldOrIvar(D, Base);
   }
 
   virtual SVal getLValueElement(QualType elementType, NonLoc offset, SVal Base);
 
-  // FIXME: This should soon be eliminated altogether; clients should deal with
-  // region extents directly.
-  virtual DefinedOrUnknownSVal getSizeInElements(ProgramStateRef state,
-                                                 const MemRegion *region,
-                                                 QualType EleTy) {
-    return UnknownVal();
-  }
-
   /// ArrayToPointer - Used by ExprEngine::VistCast to handle implicit
   ///  conversions between arrays and pointers.
   virtual SVal ArrayToPointer(Loc Array, QualType ElementTy) = 0;
 
   /// Evaluates a chain of derived-to-base casts through the path specified in
   /// \p Cast.
   SVal evalDerivedToBase(SVal Derived, const CastExpr *Cast);
 

clang/lib/StaticAnalyzer/Checkers/ArrayBoundChecker.cpp

 //
 //===----------------------------------------------------------------------===//
 
 #include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h"
 #include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
 #include "clang/StaticAnalyzer/Core/Checker.h"
 #include "clang/StaticAnalyzer/Core/CheckerManager.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/DynamicSize.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h"
 
 using namespace clang;
 using namespace ento;
 
 namespace {
 class ArrayBoundChecker :
     public Checker<check::Location> {
void ArrayBoundChecker::checkLocation(SVal l, bool isLoad, const Stmt* LoadS,
   // Zero index is always in bound, this also passes ElementRegions created for
   // pointer casts.
   if (Idx.isZeroConstant())
     return;
 
   ProgramStateRef state = C.getState();
 
   // Get the size of the array.
-  DefinedOrUnknownSVal NumElements
-    = C.getStoreManager().getSizeInElements(state, ER->getSuperRegion(),
-                                            ER->getValueType());
+  DefinedOrUnknownSVal ElementCount = getDynamicElementCount(
+      state, ER->getSuperRegion(), C.getSValBuilder(), ER->getValueType());
 
-  ProgramStateRef StInBound = state->assumeInBound(Idx, NumElements, true);
-  ProgramStateRef StOutBound = state->assumeInBound(Idx, NumElements, false);
+  ProgramStateRef StInBound = state->assumeInBound(Idx, ElementCount, true);
+  ProgramStateRef StOutBound = state->assumeInBound(Idx, ElementCount, false);
   if (StOutBound && !StInBound) {
     ExplodedNode *N = C.generateErrorNode(StOutBound);
     if (!N)
       return;
 
     if (!BT)
       BT.reset(new BuiltinBug(
           this, "Out-of-bound array access",

clang/lib/StaticAnalyzer/Checkers/MPI-Checker/MPIChecker.cpp

 /// point. It is created once for each translation unit analysed.
 /// The checker defines path-sensitive checks, to verify correct usage of the
 /// MPI API.
 ///
 //===----------------------------------------------------------------------===//
 
 #include "MPIChecker.h"
 #include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/DynamicSize.h"
 
 namespace clang {
 namespace ento {
 namespace mpi {
 
 void MPIChecker::checkDoubleNonblocking(const CallEvent &PreCallEvent,
                                         CheckerContext &Ctx) const {
   if (!FuncClassifier->isNonBlockingType(PreCallEvent.getCalleeIdentifier())) {
if (FuncClassifier->isMPI_Waitall(CE.getCalleeIdentifier())) {
     }
 
     // A single request is passed to MPI_Waitall.
     if (!SuperRegion) {
       ReqRegions.push_back(MR);
       return;
     }
 
-    const auto &Size = Ctx.getStoreManager().getSizeInElements(
-        Ctx.getState(), SuperRegion,
+    DefinedOrUnknownSVal ElementCount = getDynamicElementCount(
+        Ctx.getState(), SuperRegion, Ctx.getSValBuilder(),
         CE.getArgExpr(1)->getType()->getPointeeType());
-    const llvm::APSInt &ArrSize = Size.getAs<nonloc::ConcreteInt>()->getValue();
+    const llvm::APSInt &ArrSize =
+        ElementCount.getAs<nonloc::ConcreteInt>()->getValue();
 
     for (size_t i = 0; i < ArrSize; ++i) {
       const NonLoc Idx = Ctx.getSValBuilder().makeArrayIndex(i);
 
       const ElementRegion *const ER = RegionManager.getElementRegion(
           CE.getArgExpr(1)->getType()->getPointeeType(), Idx, SuperRegion,
           Ctx.getASTContext());
 

clang/lib/StaticAnalyzer/Checkers/ReturnPointerRangeChecker.cpp

 //
 //===----------------------------------------------------------------------===//
 
 #include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h"
 #include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
 #include "clang/StaticAnalyzer/Core/Checker.h"
 #include "clang/StaticAnalyzer/Core/CheckerManager.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/DynamicSize.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h"
 
 using namespace clang;
 using namespace ento;
 
 namespace {
 class ReturnPointerRangeChecker :
     public Checker< check::PreStmt<ReturnStmt> > {
void ReturnPointerRangeChecker::checkPreStmt(const ReturnStmt *RS,
   if (!ER)
     return;
 
   DefinedOrUnknownSVal Idx = ER->getIndex().castAs<DefinedOrUnknownSVal>();
   // Zero index is always in bound, this also passes ElementRegions created for
   // pointer casts.
   if (Idx.isZeroConstant())
     return;
+
   // FIXME: All of this out-of-bounds checking should eventually be refactored
   // into a common place.
+  DefinedOrUnknownSVal ElementCount = getDynamicElementCount(
+      state, ER->getSuperRegion(), C.getSValBuilder(), ER->getValueType());
 
-  DefinedOrUnknownSVal NumElements
-    = C.getStoreManager().getSizeInElements(state, ER->getSuperRegion(),
-                                           ER->getValueType());
-
-  ProgramStateRef StInBound = state->assumeInBound(Idx, NumElements, true);
-  ProgramStateRef StOutBound = state->assumeInBound(Idx, NumElements, false);
+  ProgramStateRef StInBound = state->assumeInBound(Idx, ElementCount, true);
+  ProgramStateRef StOutBound = state->assumeInBound(Idx, ElementCount, false);
   if (StOutBound && !StInBound) {
     ExplodedNode *N = C.generateErrorNode(StOutBound);
 
     if (!N)
       return;
 
     // FIXME: This bug correspond to CWE-466.  Eventually we should have bug
     // types explicitly reference such exploit categories (when applicable).

clang/lib/StaticAnalyzer/Checkers/UndefResultChecker.cpp

 //
 //===----------------------------------------------------------------------===//
 
 #include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h"
 #include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
 #include "clang/StaticAnalyzer/Core/Checker.h"
 #include "clang/StaticAnalyzer/Core/CheckerManager.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/DynamicSize.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h"
 #include "llvm/ADT/SmallString.h"
 #include "llvm/Support/raw_ostream.h"
 
 using namespace clang;
 using namespace ento;
 
 namespace {
if (!Loc.isValid())
     return false;
 
   const MemRegion *MR = Loc.castAs<loc::MemRegionVal>().getRegion();
   const ElementRegion *ER = dyn_cast<ElementRegion>(MR);
   if (!ER)
     return false;
 
   DefinedOrUnknownSVal Idx = ER->getIndex().castAs<DefinedOrUnknownSVal>();
-  DefinedOrUnknownSVal NumElements = C.getStoreManager().getSizeInElements(
-      state, ER->getSuperRegion(), ER->getValueType());
-  ProgramStateRef StInBound = state->assumeInBound(Idx, NumElements, true);
-  ProgramStateRef StOutBound = state->assumeInBound(Idx, NumElements, false);
+  DefinedOrUnknownSVal ElementCount = getDynamicElementCount(
+      state, ER->getSuperRegion(), C.getSValBuilder(), ER->getValueType());
+  ProgramStateRef StInBound = state->assumeInBound(Idx, ElementCount, true);
+  ProgramStateRef StOutBound = state->assumeInBound(Idx, ElementCount, false);
   return StOutBound && !StInBound;
 }
 
 static bool isShiftOverflow(const BinaryOperator *B, CheckerContext &C) {
   return C.isGreaterOrEqual(
       B->getRHS(), C.getASTContext().getIntWidth(B->getLHS()->getType()));
 }
 

clang/lib/StaticAnalyzer/Core/DynamicSize.cpp

 //===- DynamicSize.cpp - Dynamic size related APIs --------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 //  This file defines APIs that track and query dynamic size information.
 //
 //===----------------------------------------------------------------------===//
 
 #include "clang/StaticAnalyzer/Core/PathSensitive/DynamicSize.h"
+#include "clang/AST/Expr.h"
 #include "clang/Basic/LLVM.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h"
 
 namespace clang {
 namespace ento {
 
 DefinedOrUnknownSVal getDynamicSize(ProgramStateRef State, const MemRegion *MR,
                                     SValBuilder &SVB) {
   return MR->getMemRegionManager().getStaticSize(MR, SVB);
 }
 
+DefinedOrUnknownSVal getDynamicElementCount(ProgramStateRef State,
+                                            const MemRegion *MR,
+                                            SValBuilder &SVB,
+                                            QualType ElementTy) {
+  MemRegionManager &MemMgr = MR->getMemRegionManager();
+  ASTContext &Ctx = MemMgr.getContext();
+
+  DefinedOrUnknownSVal Size = getDynamicSize(State, MR, SVB);
+  SVal ElementSizeV = SVB.makeIntVal(
+      Ctx.getTypeSizeInChars(ElementTy).getQuantity(), SVB.getArrayIndexType());
+
+  SVal DivisionV =
+      SVB.evalBinOp(State, BO_Div, Size, ElementSizeV, SVB.getArrayIndexType());
+
+  return DivisionV.castAs<DefinedOrUnknownSVal>();
+}
+
 } // namespace ento
 } // namespace clang

clang/lib/StaticAnalyzer/Core/RegionStore.cpp

public: // Part of public interface to class.
   //===------------------------------------------------------------------===//
 
   /// removeDeadBindings - Scans the RegionStore of 'state' for dead values.
   ///  It returns a new Store with these values removed.
   StoreRef removeDeadBindings(Store store, const StackFrameContext *LCtx,
                               SymbolReaper& SymReaper) override;
 
   //===------------------------------------------------------------------===//
-  // Region "extents".
-  //===------------------------------------------------------------------===//
-
-  // FIXME: This method will soon be eliminated; see the note in Store.h.
-  DefinedOrUnknownSVal getSizeInElements(ProgramStateRef state,
-                                         const MemRegion* R,
-                                         QualType EleTy) override;
-
-  //===------------------------------------------------------------------===//
   // Utility methods.
   //===------------------------------------------------------------------===//
 
   RegionBindingsRef getRegionBindings(Store store) const {
     llvm::PointerIntPair<Store, 1, bool> Ptr;
     Ptr.setFromOpaqueValue(const_cast<void *>(store));
     return RegionBindingsRef(
         CBFactory,
RegionStoreManager::invalidateRegions(Store store,
   case GFK_None:
     break;
   }
 
   return StoreRef(B.asStore(), *this);
 }
 
 //===----------------------------------------------------------------------===//
-// Extents for regions.
-//===----------------------------------------------------------------------===//
-
-DefinedOrUnknownSVal
-RegionStoreManager::getSizeInElements(ProgramStateRef state,
-                                      const MemRegion *R,
-                                      QualType EleTy) {
-  DefinedOrUnknownSVal Size = getDynamicSize(state, R, svalBuilder);
-  const llvm::APSInt *SizeInt = svalBuilder.getKnownValue(state, Size);
-  if (!SizeInt)
-    return UnknownVal();
-
-  CharUnits RegionSize = CharUnits::fromQuantity(SizeInt->getSExtValue());
-
-  if (Ctx.getAsVariableArrayType(EleTy)) {
-    // FIXME: We need to track extra state to properly record the size
-    // of VLAs.  Returning UnknownVal here, however, is a stop-gap so that
-    // we don't have a divide-by-zero below.
-    return UnknownVal();
-  }
-
-  CharUnits EleSize = Ctx.getTypeSizeInChars(EleTy);
-
-  // If a variable is reinterpreted as a type that doesn't fit into a larger
-  // type evenly, round it down.
-  // This is a signed value, since it's used in arithmetic with signed indices.
-  return svalBuilder.makeIntVal(RegionSize / EleSize,
-                                svalBuilder.getArrayIndexType());
-}
-
-//===----------------------------------------------------------------------===//
 // Location and region casting.
 //===----------------------------------------------------------------------===//
 
 /// ArrayToPointer - Emulates the "decay" of an array to a pointer
 ///  type.  'Array' represents the lvalue of the array being decayed
 ///  to a pointer, and the returned SVal represents the decayed
 ///  version of that lvalue (i.e., a pointer to the first element of
 ///  the array).  This is called by ExprEngine when evaluating casts