[analyzer] Compute FAM dynamic size

[danix800]

Summary

This commit computes size of FAM which is normally allocated dynamically.

[danix800]

Update testcase

[steakhal]

Thanks for submitting this.
A funny thing is that in my free time I was also working on this last week. I'll have a look at this more in depth during the week.
For the mean time here is my version, committed pretty much a couple days ago to my fork.
https://github.com/steakhal/llvm-project/commit/986059a146e036ec84db64868a079d3c4a0e5e16

EDIT: fix the link to point to my fork.

Your proposed change looks pretty similar to mine.

[danix800]

In D158499#4606291, @steakhal wrote:

Thanks for submitting this.
A funny thing is that in my free time I was also working on this last week. I'll have a look at this more in depth during the week.
For the mean time here is my version, committed pretty much a couple days ago to my fork.
https://github.com/steakhal/llvm-project/commit/986059a146e036ec84db64868a079d3c4a0e5e16

EDIT: fix the link to point to my fork.

Your proposed change looks pretty similar to mine.

Are you going to submit your changes? Which one do you think is more suitable?

Please let me know whether I should continue on this one or wait for yours. Thanks!

[steakhal]

In D158499#4606337, @danix800 wrote:

In D158499#4606291, @steakhal wrote:

Thanks for submitting this.
A funny thing is that in my free time I was also working on this last week. I'll have a look at this more in depth during the week.
For the mean time here is my version, committed pretty much a couple days ago to my fork.
https://github.com/steakhal/llvm-project/commit/986059a146e036ec84db64868a079d3c4a0e5e16

EDIT: fix the link to point to my fork.

Your proposed change looks pretty similar to mine.

Are you going to submit your changes? Which one do you think is more suitable?

Please let me know whether I should continue on this one or wait for yours. Thanks!

I think the difference between yours and my implementation is that I try to accept FAM like arrays even if they are nested inside other strict, if they are notionally the last field of the whole thing. I'm doing it because that is how the machines work, thus the model should model that and return the right extent even for those cases.
What I can tell, that I didn't check my implementation with the packed attribute. I assume it should work.
The decl has a tempting method checking if its a FAM, however that does not accept FAMs of size 1 or of any size.

So its hard to tell right away which approach is better, but I'll look into this.

[danix800]

We have getDynamicExtentWithOffset to use, which can handle more general
dynamic memory based cases than this fix.

I'll abandon this one.

There are issues worth clarifying and fixing:

1). Debugging APIs like clang_analyzer_dumpExtent in ExprInspection might be expanded
to use getDynamicExtentWithOffset if it's intended to be used on not only dynamic allocated
regions but more general ones, and more testcases are needed to demonstrate the usage.

2). Fix type-inconsistency of several size-related SVals, e.g.

FAM fam;
clang_analyzer_dump(clang_analyzer_getExtent(&fam));
clang_analyzer_dump(clang_analyzer_getExtent(fam.data));
// expected-warning@-2 {{4 S64b}}  // U64b is more reasonable when used as an extent
// expected-warning@-2 {{0 U64b}}

ArrayIndexType might be misused here.

Simple searching results listed here (might not be complete):

1. getDynamicExtentWithOffset return value
2. getElementExtent return value
3. ExprEngineCallAndReturn.cpp when calling setDynamicExtent the Size arg

[danix800]

One of the observable issue with inconsistent size type is

void clang_analyzer_eval(int);

typedef unsigned long long size_t;
void *malloc(unsigned long size);
void free(void *);

void symbolic_longlong_and_int0(long long len) {
  char *a = malloc(5);
  (void)a[len + 1]; // no-warning
  // len: [-1,3]
  clang_analyzer_eval(-1 <= len && len <= 3); // expected-warning {{TRUE}}
  clang_analyzer_eval(0 <= len);              // expected-warning {{UNKNOWN}}
  clang_analyzer_eval(len <= 2);              // expected-warning {{UNKNOWN}}
  free(a);
}

which is extracted from clang/test/Analysis/array-bound-v2-constraint-check.c,
with DynamicMemoryModeling turned on,
the second warning does not hold anymore: clang_analyzer_eval(0 <= len);
will be reported as TRUE which is not expected.

DynamicMemoryModeling will record the extent of allocated memory as 5ULL,
ArrayBoundV2 will do len + 1 < 5ULL assumption, simplified to len < 4ULL,
which casts len to unsigned, dropping -1, similar to

void clang_analyzer_eval(int);

void test(int len) {
  if (len >= -1 && len <= 4U) { // len is promoted into unsigned, thus can never be negative
      clang_analyzer_eval(0 <= len);              // TRUE
  }
}

[steakhal]

In D158499#4608847, @danix800 wrote:

We have getDynamicExtentWithOffset to use, which can handle more general
dynamic memory based cases than this fix.

I'll abandon this one.

There are issues worth clarifying and fixing:

1). Debugging APIs like clang_analyzer_dumpExtent in ExprInspection might be expanded
to use getDynamicExtentWithOffset if it's intended to be used on not only dynamic allocated
regions but more general ones, and more testcases are needed to demonstrate the usage.

2). Fix type-inconsistency of several size-related SVals, e.g.

FAM fam;
clang_analyzer_dump(clang_analyzer_getExtent(&fam));
clang_analyzer_dump(clang_analyzer_getExtent(fam.data));
// expected-warning@-2 {{4 S64b}}  // U64b is more reasonable when used as an extent
// expected-warning@-2 {{0 U64b}}

ArrayIndexType might be misused here.

Simple searching results listed here (might not be complete):

1. getDynamicExtentWithOffset return value
2. getElementExtent return value
3. ExprEngineCallAndReturn.cpp when calling setDynamicExtent the Size arg

I've also thought of these two. I think we should indeed fix both.

In D158499#4608974, @danix800 wrote:

One of the observable issue with inconsistent size type is

void clang_analyzer_eval(int);

typedef unsigned long long size_t;
void *malloc(unsigned long size);
void free(void *);

void symbolic_longlong_and_int0(long long len) {
  char *a = malloc(5);
  (void)a[len + 1]; // no-warning
  // len: [-1,3]
  clang_analyzer_eval(-1 <= len && len <= 3); // expected-warning {{TRUE}}
  clang_analyzer_eval(0 <= len);              // expected-warning {{UNKNOWN}}
  clang_analyzer_eval(len <= 2);              // expected-warning {{UNKNOWN}}
  free(a);
}

which is extracted from clang/test/Analysis/array-bound-v2-constraint-check.c,
with DynamicMemoryModeling turned on,
the second warning does not hold anymore: clang_analyzer_eval(0 <= len);
will be reported as TRUE which is not expected.

DynamicMemoryModeling will record the extent of allocated memory as 5ULL,
ArrayBoundV2 will do len + 1 < 5ULL assumption, simplified to len < 4ULL,
which casts len to unsigned, dropping -1, similar to

void clang_analyzer_eval(int);

void test(int len) {
  if (len >= -1 && len <= 4U) { // len is promoted into unsigned, thus can never be negative
      clang_analyzer_eval(0 <= len);              // TRUE
  }
}

I suspected that the wrong cast modeling and how we infer what value ranges are calculated is susceptible to such APSInt signedness issues, but I haven't seen a case in the wild for extents. Thus, I didn't think of fixing it either. But yes, we should.

[danix800]

I suspected that the wrong cast modeling and how we infer what value ranges are calculated is susceptible to such APSInt signedness issues, but I haven't seen a case in the wild for extents. Thus, I didn't think of fixing it either. But yes, we should.

I think cast is not the problem, size-type inconsistent is. For ArrayBound, the assumption should be done with correct types to avoid -Wsign-compare issue.

EDIT: I'm actually NOT sure about the cast modeling, but type-inconsistent is one the issue
worth fixing.

[donat.nagy]

In D158499#4608974, @danix800 wrote:

One of the observable issue with inconsistent size type is

void clang_analyzer_eval(int);

typedef unsigned long long size_t;
void *malloc(unsigned long size);
void free(void *);

void symbolic_longlong_and_int0(long long len) {
  char *a = malloc(5);
  (void)a[len + 1]; // no-warning
  // len: [-1,3]
  clang_analyzer_eval(-1 <= len && len <= 3); // expected-warning {{TRUE}}
  clang_analyzer_eval(0 <= len);              // expected-warning {{UNKNOWN}}
  clang_analyzer_eval(len <= 2);              // expected-warning {{UNKNOWN}}
  free(a);
}

which is extracted from clang/test/Analysis/array-bound-v2-constraint-check.c,
with DynamicMemoryModeling turned on,
the second warning does not hold anymore: clang_analyzer_eval(0 <= len);
will be reported as TRUE which is not expected.

DynamicMemoryModeling will record the extent of allocated memory as 5ULL,
ArrayBoundV2 will do len + 1 < 5ULL assumption, simplified to len < 4ULL,
which casts len to unsigned, dropping -1, similar to

void clang_analyzer_eval(int);

void test(int len) {
  if (len >= -1 && len <= 4U) { // len is promoted into unsigned, thus can never be negative
      clang_analyzer_eval(0 <= len);              // TRUE
  }
}

This issue is very interesting and scary -- I wouldn't have guessed that the core constraint handling algorithms are so buggy that things like this can happen 😦. I reproduced the issue and double-checked that the logic error is not in ArrayBoundV2 (despite that its simplification algorithm is messy and suspicious); I'd be very happy if this issue could be resolved (perhaps along with other inaccuracies of APSInt math...).

[steakhal]

@danix800 FYI I think you used the wrong revision link in the commit. Maybe mark this revision as "abandoned" again, to reflect the actual status.

[danix800]

https://github.com/llvm/llvm-project/commit/12559064e05a11e8418425de59d8745f0cfb1122 mistakingly linked here. The actual revision is D158707

[danix800]

In D158499#4634166, @steakhal wrote:

@danix800 FYI I think you used the wrong revision link in the commit. Maybe mark this revision as "abandoned" again, to reflect the actual status.

Sorry for this mistake.

D158707 originates from this but I forgot to update the revision ID.

clang/lib/StaticAnalyzer/Core/DynamicExtent.cpp

 
 REGISTER_MAP_WITH_PROGRAMSTATE(DynamicExtentMap, const clang::ento::MemRegion *,
                                clang::ento::DefinedOrUnknownSVal)
 
 namespace clang {
 namespace ento {
 
 DefinedOrUnknownSVal getDynamicExtent(ProgramStateRef State,
+                                      const MemRegion *MR, SValBuilder &SVB);
+
+static bool isFlexibleArrayMember(const FieldDecl *FD) {
+  const auto *RD = FD->getParent();
+  if (!RD->hasFlexibleArrayMember())
+    return false;
+
+  const FieldDecl *LastFD = nullptr;
+  for (const FieldDecl *It : RD->fields())
+    LastFD = It;
+
+  return FD == LastFD;
+}
+
+static std::optional<DefinedOrUnknownSVal>
+getFlexibleArrayExtent(ProgramStateRef State, const MemRegion *MR,
+                       SValBuilder &SVB) {
+  const auto *FieldMR = dyn_cast<FieldRegion>(MR);
+  if (nullptr == FieldMR)
+    return std::nullopt;
+
+  const FieldDecl *FD = FieldMR->getDecl();
+  if (!isFlexibleArrayMember(FD))
+    return std::nullopt;
+
+  const RecordDecl *RD = FD->getParent();
+  const MemRegion *BaseMR = FieldMR->getBaseRegion();
+  auto BaseSize = getDynamicExtent(State, BaseMR, SVB);
+
+  auto &C = SVB.getContext();
+  uint64_t RecordSize = C.getTypeSizeInChars(C.getRecordType(RD)).getQuantity();
+  SVal RecordSizeVal = SVB.makeIntVal(RecordSize, C.getSizeType());
+
+  SVal BaseTooSmall =
+      SVB.evalBinOp(State, BO_LT, BaseSize, RecordSizeVal, C.BoolTy);
+  if (!BaseTooSmall.isUndef() &&
+      State->assume(*BaseTooSmall.getAs<DefinedOrUnknownSVal>(), true))
+    return std::nullopt;
+
+  SVal FlexibleArrayExtent =
+      SVB.evalBinOp(State, BO_Sub, BaseSize, RecordSizeVal, C.getSizeType());
+  return FlexibleArrayExtent.getAs<DefinedOrUnknownSVal>();
+}
+
+DefinedOrUnknownSVal getDynamicExtent(ProgramStateRef State,
                                       const MemRegion *MR, SValBuilder &SVB) {
   MR = MR->StripCasts();
 
   if (const DefinedOrUnknownSVal *Size = State->get<DynamicExtentMap>(MR))
     return *Size;
 
+  if (auto FlexibleArrayExtent = getFlexibleArrayExtent(State, MR, SVB))
+    return *FlexibleArrayExtent;
+
   return MR->getMemRegionManager().getStaticSize(MR, SVB);
 }
 
 DefinedOrUnknownSVal getElementExtent(QualType Ty, SValBuilder &SVB) {
   return SVB.makeIntVal(SVB.getContext().getTypeSizeInChars(Ty).getQuantity(),
                         SVB.getArrayIndexType());
 }
 

clang/test/Analysis/flexible-array-members.c

typedef struct FAM {
     char c;
     int data[];
   } FAM;
 
   FAM fam;
   clang_analyzer_dump(clang_analyzer_getExtent(&fam));
   clang_analyzer_dump(clang_analyzer_getExtent(fam.data));
   // expected-warning@-2 {{4 S64b}}
-  // expected-warning@-2 {{Unknown}}
+  // expected-warning@-2 {{0 U64b}}
 
   FAM *p = (FAM *)alloca(sizeof(FAM));
   clang_analyzer_dump(clang_analyzer_getExtent(p));
   clang_analyzer_dump(clang_analyzer_getExtent(p->data));
   // expected-warning@-2 {{4 U64b}}
-  // expected-warning@-2 {{Unknown}}
+  // expected-warning@-2 {{0 U64b}}
 
   FAM *q = (FAM *)malloc(sizeof(FAM));
   clang_analyzer_dump(clang_analyzer_getExtent(q));
   clang_analyzer_dump(clang_analyzer_getExtent(q->data));
   // expected-warning@-2 {{4 U64b}}
-  // expected-warning@-2 {{Unknown}}
+  // expected-warning@-2 {{0 U64b}}
   free(q);
+
+  q = (FAM *)malloc(sizeof(FAM) + sizeof(int) * 2);
+  clang_analyzer_dump(clang_analyzer_getExtent(q));
+  clang_analyzer_dump(clang_analyzer_getExtent(q->data));
+  // expected-warning@-2 {{12 U64b}}
+  // expected-warning@-2 {{8 U64b}}
+  free(q);
+
+  typedef struct __attribute__((packed)) {
+    char c;
+    int data[];
+  } PackedFAM;
+
+  PackedFAM *t = (PackedFAM *)malloc(sizeof(PackedFAM) + sizeof(int) * 2);
+  clang_analyzer_dump(clang_analyzer_getExtent(t));
+  clang_analyzer_dump(clang_analyzer_getExtent(t->data));
+  // expected-warning@-2 {{9 U64b}}
+  // expected-warning@-2 {{8 U64b}}
+  free(t);
+}
+
+void test_too_small_base(void) {
+  typedef struct FAM {
+    long c;
+    int data[];
+  } FAM;
+  short s = 0;
+  FAM *p = (FAM *) &s;
+  clang_analyzer_dump(clang_analyzer_getExtent(p));
+  clang_analyzer_dump(clang_analyzer_getExtent(p->data));
+  // expected-warning@-2 {{2 S64b}}
+  // expected-warning@-2 {{Unknown}}
 }
 
 void test_zero_length_array_fam(void) {
   typedef struct FAM {
     char c;
     int data[0];
   } FAM;