This is an archive of the discontinued LLVM Phabricator instance.

[analyzer] Upgrading RegionStore to keep track of the region extent
Needs ReviewPublic

Authored by isuckatcs on Aug 26 2022, 11:55 AM.

Details

Summary

The goal is to find a solution for the FIXME in RegionStoreManager::getLazyBinding(), when the default binding is overwritten and we lose information.

Diff Detail

Event Timeline

isuckatcs created this revision.Aug 26 2022, 11:55 AM
Herald added a project: Restricted Project. · View Herald TranscriptAug 26 2022, 11:55 AM
isuckatcs requested review of this revision.Aug 26 2022, 11:55 AM
NoQ added a comment.Aug 27 2022, 11:42 PM

Aha I see, this patch attempts to make multiple bindings live together at the same begin-offset when they have different size.

This is very nice progress but also there are a lot more ways in which bindings can overlap. Even if we're talking about C++ base classes, they aren't necessarily at the same offset (multiple inheritance is a thing). Then we have to figure out how to load from an offset that doesn't coincide with either of the bindings' begin-offset (need to figure out which binding is hit, and it could be that both are hit so the *freshest* binding has priority). I don't know whether incremental progress can be made here; we might need to experiment to see if there are easy strict improvements.

clang/lib/StaticAnalyzer/Core/RegionStore.cpp
124

This operator== is no longer symmetric, i.e. we can have a situation where X == Y but not Y == X. I'm worried that containers may behave very weirdly in such situation.

136

Using R->getExtent() is a clever solution, I like it! It avoids passing in the type separately.

isuckatcs updated this revision to Diff 456219.Aug 28 2022, 4:49 PM
isuckatcs marked 2 inline comments as done.

Trying a different approach.

isuckatcs updated this revision to Diff 456583.Aug 30 2022, 2:53 AM

Removed the hack from RegionStoreManager::getLazyBinding().

isuckatcs updated this revision to Diff 457801.Sep 3 2022, 9:53 AM

Minor tweaks in overlapping region lookup

Can I get a review on this one please, just to see how far it actually is from a viable solution?

Hey, sorry for not responding earlier, we got a bit busy lately. I think this is a really big change and I think we might want to discuss this in more detail, do some benchmarks on open-source projects and so on.
I think the solution you proposed looks great for the specific problem you want to solve, but I want to know more whether it will have any impact on something else. Historically, we had a lot of trouble with representing conversions (e.g., accessing the same memory through pointers of different type). It would be unfortunate, if some things we want to be collapsed to be the same binding would suddenly become separate and produce unsound results. I am thinking if scenarios like looking at an object as if it was an array of bytes and using different lengths of arrays.

clang/test/Analysis/array-init-loop.cpp
170–171

How do we feel about this change?

clang/test/Analysis/uninit-structured-binding-array.cpp
202

What is the reason of deleting this test case? Or was it just too similar to the one before it?

clang/test/Analysis/uninit-structured-binding-struct.cpp
15

Are we OK with losing these warnings?

isuckatcs added a comment.EditedMay 21 2023, 3:51 PM

Hey, sorry for not responding earlier, we got a bit busy lately. I think this is a really big change and I think we might want to discuss this in more detail, do some benchmarks on open-source projects and so on.

No worries, I also looked at the problem again in the past couple of days and I'm not happy with this solution yet. It seems to work but I don't like that we fall back to the original lookup strategy. I'm investigating a
different approach and I already started working on a discourse post where I discuss the problem we are facing with extents and a solution (which I still haven't entirely figured out).

we had a lot of trouble with representing conversions (e.g., accessing the same memory through pointers of different type)

This is also something I ran into recently. See #62822. I'm also not sure how to deal with it when extents are there.

Snippet:
  int x = 1024;
  *((char *)&x) = 0;
Store:
  {"kind": "Direct", "offset": 0, "extent": 8, "value": 0 S8b}

Imagine that the next statement is int y = x;.

Snippet:
  int x = 1024;
  *((char *)&x) = 0;
  int y = x;
Store:
  {"kind": "Direct", "offset": 0, "extent": 8, "value": 0 S8b}

We are looking up {"kind": "Default", "offset": 0, "extent": 32} and by looking at the store you would say we have 1 initialized and 3 uninitialized bytes, so the value is Undefined,
however in reality we had 4 initialized bytes, where the last one was changed, but since we don't implement SVal slicing, I think we should return Unknown (even though in this example the value
doesn't actually changes).

But what about this scenario:

Snippet:
  char x = 0;
  int y = *((int *)&x);
Store:
  {"kind": "Direct", "offset": 0, "extent": 8, "value": 0 S8b}

We are looking up {"kind": "Default", "offset": 0, "extent": 32} again, however this time the value should be Undefined. I'm experimenting with returning Unknown it both cases,
even though it's not correct.

Overlapping values are tricky, even leaving both of them in the store would make it difficult to reason about them. Consider these examples:

Snippet:
  int x = 1024;
  *((char *)&x) = 1;

  int y = x;
  char z = *((char *)&x);
Store:
  {"kind": "Direct", "offset": 0, "extent": 32 value: 1024 S32b}
  {"kind": "Direct", "offset": 0, "extent": 8, "value": 1 S8b}

Here z is 1 and y is Unknown (1025 in reality but again we can't handle this yet).

Snippet:
  char x = 1;
  *((int *)&x) = 1024;

  int y = *((int *)&x);
  char z = x;
Store:
  {"kind": "Direct", "offset": 0, "extent": 8 value: 1 S8b}
  {"kind": "Direct", "offset": 0, "extent": 32 value: 1024 S32b}

Here z should be 0 and y should be 1024 (at least pretend that).

Region store however can't track which binding was created first since it uses a map as a representation and even if it had timestamps you would need to keep track of all the overlaping regions and
figure out which region is valid and which has been modified.

clang/test/Analysis/array-init-loop.cpp
170–171

I think we want the warning to appear as it used to be. Sadly I modified this patch since then, but with my current version, when I tried to reproduce this, the analyzer crashed due to a source location issue, so I leave this comment here to investigate it later.

warning: Value assigned to field 'i' in implicit constructor is garbage or undefined [core.uninitialized.Assign]
struct S3 {
       ^
note: Calling implicit copy constructor for 'S3'
clang++: llvm-project/clang/lib/Frontend/TextDiagnostic.cpp:1019: void highlightRange(const clang::CharSourceRange&, unsigned int, clang::FileID, const {anonymous}::SourceColumnMap&, std::string&, const clang::SourceManager&, const clang::LangOptions&): Assertion `StartColNo <= EndColNo && "Invalid range!"' failed.
clang/test/Analysis/uninit-structured-binding-array.cpp
202

It's been a while, so I don't remember my exact motives here. It seems like this test case has been combined with the previous one, so both a and c are checked in the same test case after the change.

clang/test/Analysis/uninit-structured-binding-struct.cpp
15

We're not losing it, but I want to check if both i and j are Undefined and after the assigment, the analyzer bails out, so I would need to create a different test case to check it for j too.

isuckatcs updated this revision to Diff 524906.May 23 2023, 3:23 PM

Trying a more consistent approach.

isuckatcs added inline comments.May 23 2023, 3:35 PM
clang/test/Analysis/casts.c
162

Please see my comment under the original patch for explanation.

clang/test/Analysis/cxx-uninitialized-object-ptr-ref.cpp
292–293

I think this is an issue with the checker. I analyze the problem in a comment in the original revision, please see that for explanation.

clang/test/Analysis/pr22954.c
830

Here we actually read 1 byte from a place in memory to which we assigned 4 bytes (memory slicing happens). If instead of 11, we assigned a value that cannot be represented on 1 byte, this would be a false positive.

868

Same as above.

clang/test/Analysis/pr37802.cpp
26

As we don't know what this snippet does and it cannot be executed, I don't know if this warning is correct or not.

Note that this infinitely recursive function should be invoked:

Z g() {
  Z az = g();
  Z e = az;
  Y d;
  e.au(d);
}
74

Same as above.

clang/test/Analysis/uninit-structured-binding-struct.cpp
15

For the record, the warning is lost because the core checkers have been disabled and this comes from core.uninitialized.Assign.

isuckatcs updated this revision to Diff 525378.May 24 2023, 5:14 PM

Fixed the issue which caused the patch to fail CI

isuckatcs updated this revision to Diff 526282.EditedMay 27 2023, 11:58 AM

Added a logic that helps us reason about these snippets:

struct S {
  char a;
  char b;
  char c;
  char d;
};

void everyByteInitialized() {
  S s = {1, 2, 3, 4};
  int x = *((int *)&s);

  // FIXME: Every byte inside 'x' is initialized, we just can't concatenate them.
  clang_analyzer_eval(x); //expected-warning{{UNKNOWN}}
}

void someGarbageBytes() {
  S s;
  s.a = 1;
  s.b = 2;
  s.d = 4;

  // Here one byte of 'x' is a garbage value.
  int x = *((int *)&s); //expected-warning{{Assigned value is garbage or undefined}}
  (void) x;
}
isuckatcs retitled this revision from [analyzer] Attempt to track region extent for binding to [analyzer] Upgrading RegionStore to keep track of the region extent.May 27 2023, 12:25 PM
isuckatcs added inline comments.May 27 2023, 12:31 PM
clang/test/Analysis/array-init-loop.cpp
170–171

Edit: this warning disappeared only due to disabling the core checkers in this test file

clang/test/Analysis/array-punned-region.c
24

An explanation can be found in my comment under the patch that added this test case.

Addressed the issues related to this snippet:

void issue() {
  int x = 0x01020304;
  *((char *)&x + 1) = 1;

  int y = x;
}
isuckatcs updated this revision to Diff 526795.May 30 2023, 2:23 PM

The false positive issue due to bindings getting removed has been mitigated by only removing bindings if we are binding a symbolic region, or the store contains a symbolic region. We are good at handling overlapping non-symbolic bindings.

Thanks for the proof of concept implementation. It was really thoughtful and constructive.
This will improve the store by a long shot if finished.
This implementation would fix a lot of FN cases in our testsuite.
However, it also introduces some new reports, and those are primarily FPs as far as I can tell.

I'll refer to my comment on the RFC for explaining how we think extents should work.

clang/lib/StaticAnalyzer/Core/MemRegion.cpp
1636–1644

On our testbench we encountered a really rare crash, where Ty was a dependent type.
Given how rare it was and that the given TU had parsing errors it probably not affects regular CSA users, but let's be on the safe side and guard our code against dependent types as well.

When I reduced the case I had this:

} // <-- This needs to be here :D
template <typename a> void b(a); // <-- This shouldn't have a body.
void c() {
  b([](auto d) {
    static auto a(d);
    a;
  });
}

This code is likely not too useful for you, but I'll leave it here for history.

clang/lib/StaticAnalyzer/Core/RegionStore.cpp
120

How about this one: std::tie(Data, Extent) < std::tie(X.Data, X.Extent)

TBH I'm not sure why it's not std::tie(P.getOpaqueValue(), Data, Extent) < std::tie(...) in the first place.

337–346

We should probably also count this as well:

[        B1         ][    B2     ]
          [       K         ]
1780

I'm not really sure why we need to look up a partial binding here.
I wonder what will be the result for a code like this:

struct A {
  int x;
  int y;
};

struct B {
  int z;
  A a;
};

struct C {
  B b;
  int x;
};

void top() {
  C c{}; // bind zero default
  B b{1, {2, 3}};
  c.b = b;
  A a = c.b.a;
  // b:
  // [ dir: 1 | dir: 2 | dir: 3 ]

  // c:
  // [        def: 0         ]
  // [ def: lcv(b) ]

  // a:
  // [ def: lcv(c.b.a) ]
  clang_analyzer_dump(a.x); // I would expect "1" here but I got "0" with this patch.
}
2062–2077

I'm so happy to see this going away.

isuckatcs updated this revision to Diff 529065.Jun 6 2023, 3:46 PM
  • Added the contains() and overlapsWith() methods to BindingKey.
  • Implemented the proposed Store to binding B ([start, end]) with the modifications discussed in the RFC.
  • The store implementation is scattered across different places, which needs to be cleaned up
  • Added one more test case, which used to be a false positive
isuckatcs marked an inline comment as done.Jun 6 2023, 4:01 PM
isuckatcs added inline comments.
clang/lib/StaticAnalyzer/Core/RegionStore.cpp
120

I'm not sure if creating 2 tuples is more efficient than calling a ternary operator.

TBH I'm not sure why it's not std::tie(P.getOpaqueValue(), Data, Extent) < std::tie(...) in the first place.

Well, I don't use std::tuple<> that much, so I wasn't aware that it's operator< does exactly what this piece of code does. This however is also a con against std::tie(), because it might lead to people, who are not familiar with how std::tuple<> comparison works (like I was) being confused about what happens here.

I don't mark this comment as done, as I'm still considering using std::tie() instead of this.

1780

I'm not really sure why we need to look up a partial binding here.

I'm not sure either. I think this is an artifact, that has been added here accidentally. I'll remove it in the next update.

I wonder what will be the result for a code like this:

That snippet indeed resulted in a false value, which has been fixed by the new add method. I added the snippet as a testcase, however note that a.x should be 2 at the point of the dumping. See on godbolt.

isuckatcs marked an inline comment as done.Jun 6 2023, 4:42 PM
isuckatcs updated this revision to Diff 530062.Jun 9 2023, 1:01 PM

Cleaned up the patch a bit

isuckatcs marked an inline comment as done.Jun 9 2023, 1:03 PM
isuckatcs added inline comments.Jun 9 2023, 3:21 PM
clang/test/Analysis/bstring_UninitRead.c
34

@steakhal
So we no longer have the FP for the mempcpy, and leaves me wonder why is the diag for clang_analyzer_eval still missing?
In any case, the comment there should be updated.

This is a good catch. The reason is that debug.ExprInspection is not enabled for this source file for some reason.

54

@steakhal
Same here as in the previous mempcpy14 case.

Same as above.

clang/test/Analysis/casts.c
159–167

@steakhal
I think we could take this opportunity to get rid of these macros and use different -verify=xxx suffixes for 32 and 64 bit systems. It should be possible, because only the outputs should be different in the test for the same code across different RUN lines.

clang/test/Analysis/cxx-uninitialized-object-ptr-ref.cpp
291–298

@steakhal
At first glance, it looks fine.
I think in the abstract machine it's valid to dereference the value ptr.
So, I think we don't need a FIXME there, but @Szelethus probably can judge this better.

clang/test/Analysis/cxx-uninitialized-object.cpp
869–882

@steakhal
Oh, now that is confusing :D So, the checker counts the members of the functor there.
Put here a FIXME if you want.

clang/test/Analysis/misc-ps-region-store.m
799–806 ↗(On Diff #530062)

@steakhal
I'm surprised about this one.

Generally, we cannot depend on the initializers of local statics, as this function might have been already called once, and changed the variable, or worse, escaped its address and something magical wrote there something brand new since that.

So, if we had an assignment before loading for the condition, we should track the assigned value; but we cannot trust the initializer.
Consequently, this test case was simply wrong and now works as it should.

BTW this might be related to D139534, but only now surfaces.

clang/test/Analysis/pr22954.c
912–914

@steakhal
Isn't this fixed by this patch?

Well, it says it should be UNKNOWN or FALSE, however because it might turn FALSE in the future, I left the fixme here.

clang/test/Analysis/pr37802.cpp
6–28

@steakhal
lol, what's going on here? Did you check if this is actually a TP?
Anyway, is probably fine 😅

I have no idea what this is and I cannot run it either because of the reasons in the above comment. 😅

isuckatcs updated this revision to Diff 530210.Jun 10 2023, 7:50 AM
isuckatcs marked 2 inline comments as done.

Cleanup

isuckatcs updated this revision to Diff 530247.Jun 10 2023, 1:49 PM

Improved the way MemRegion::getExtent() calculates the extents.

isuckatcs added inline comments.Jun 10 2023, 1:53 PM
clang/test/Analysis/misc-ps-region-store.m
799–806 ↗(On Diff #530062)

This happened because of some issues about calculating the flexible array member extent, nothing wrong with the original patch I think.

isuckatcs updated this revision to Diff 530691.Jun 12 2023, 3:52 PM

Updated how bindings are added to the store.

It turned out there was a different kind of problem with this snippet:

struct rdar_7515938 {
  int x;
  int y[];
};

const struct rdar_7515938 *rdar_7515938(void) {
  static const struct rdar_7515938 z = { 0, { 1, 2 } };
  if (z.y[0] != 1) {
    int *p = 0;
    *p = 0xDEADBEEF; // no-warning
  }
  return &z;
}

These are the bindings that are added to the store in order:

"kind": "Direct", "offset": 0, "extent": 32 0 S32b
-----------------------------------------------
"kind": "Direct", "offset": 32, "extent": 32 1 S32b
-----------------------------------------------
"kind": "Direct", "offset": 64, "extent": 32 2 S32b
-----------------------------------------------
"kind": "Default", "offset": 32, "extent": 9223372036854775807 0 S32b

The Default binding removes the bindings with the value of 1 and 2 from the store.
This is probably some issue with the checker, but for now addition is changed so that a
Default binding cannot remove Direct bindings...

@steakhal the patch is ready for a run. Can you please test it on IRL projects?

@steakhal the patch is ready for a run. Can you please test it on IRL projects?

I run it, but now the challenge is to share the reproducers in some form to let you investigate them.
However, I use our frontend so the reproducers are in a specific form. Consequently, you wouldn't be able to reduce it.
So, I have to reduce them; but we are speaking of ~8 reproducers.
I'll think about how to do this efficiently on Monday.
But one should note that it's difficult to dedicate time.

@steakhal the patch is ready for a run. Can you please test it on IRL projects?

I run it, but now the challenge is to share the reproducers in some form to let you investigate them.
However, I use our frontend so the reproducers are in a specific form. Consequently, you wouldn't be able to reduce it.
So, I have to reduce them; but we are speaking of ~8 reproducers.
I'll think about how to do this efficiently on Monday.
But one should note that it's difficult to dedicate time.

I picked randomly some files for which we had differences. Mostly new uninit read reports.

Clang/clang/lib/AST/APValue.cpp:240 New: Argument to 'delete[]' is uninitialized
Clang/clang/lib/AST/APValue.cpp:249 New: Undefined or garbage value returned to caller
cataclysm-dda/src/npc_class.cpp:472 New: Potential memory leak
cataclysm-dda/src/npc_class.cpp:481 New: Potential memory leak
fmt/test/chrono-test.cc:230 New: The right operand of '==' is a garbage value
git/builtin/log.c:1785 New: 1st function call argument is an uninitialized value
HHVM/hphp/runtime/vm/native.cpp:112 New: Assigned value is garbage or undefined
linux-drivers/drivers/infiniband/hw/qedr/main.c:977 Absent: Assigned value is garbage or undefined

I usually use something like this for the interestingness test for reducing with creduce:

#!/bin/bash

set -e

SCRIPT_DIR=$( cd -- "$( dirname -- "${BASH_SOURCE[0]}" )" &> /dev/null && pwd )

# We had no issues like that, nor were parsing errors.
bash -c "${SCRIPT_DIR}/../old-clang -c -o /dev/null preprocessed_APValue.cpp \
  --analyze -Xclang -analyzer-checker=core --analyzer-output text-minimal \
  2>&1 | grep --extended-regexp \"(warning: Argument to 'delete\[\]' is uninitialized)|(error)\" | wc -l | grep '^0$'" &

# A new issue appeared.
bash -c "${SCRIPT_DIR}/../new-clang -c -o /dev/null preprocessed_APValue.cpp \
  --analyze -Xclang -analyzer-checker=core --analyzer-output text-minimal \
  2>&1 | grep --extended-regexp \"(warning: Argument to 'delete\[\]' is uninitialized)\" | wc -l | grep '^1$'" &

# Wait for the fastest job to early-return on error; otherwise wait for all jobs.
myjobs="$(jobs -p)"
for i in $myjobs; do
  if ! wait -n $myjobs 2>/dev/null; then
    kill -KILL $myjobs 2>/dev/null
    exit 1
  fi
done

I started looking at the preprocessed examples, however there are some that I either can't compile or I can't reproduce.

APValue.cpp      <-- managed to reproduce and reduce
npc_class.cpp    <-- can't reproduce
chrono-test.cc   <-- managed to reproduce and reduce
log.c            <-- only gcc compiles it, and scan-build doesn't work either
native.cpp       <-- can't compile
main.c           <-- managed to reproduce and reduce

These are the reproduced snippets:

// APValue.cpp
class a {
  struct b;
  int c;
  a(const a &);
};

struct a::b {
  int *g;
  void d() { delete[] g; }
};

a::a(const a &e) {
  *this = a(e);
  b f = *(b *)&c;
  f.d();
}
// chrono-test
struct a {
  int b;
  int c;
  int d;
};

int e;

auto f(a h) -> bool {
  e == h.d;
  a g;
  f(g);
}
// main
char a, b;

void c() {
  char d[2];
  *(int *)d = a;
  b = d[1];
}

I need to allocate more time to investigate them, but all of the differences between the old analyzer and the one using this store
look wrong so far.

For the ones I failed to reduce can you please provide, which clang invocation was used?

I started looking at the preprocessed examples, however there are some that I either can't compile or I can't reproduce.

APValue.cpp      <-- managed to reproduce and reduce
npc_class.cpp    <-- can't reproduce
chrono-test.cc   <-- managed to reproduce and reduce
log.c            <-- only gcc compiles it, and scan-build doesn't work either
native.cpp       <-- can't compile
main.c           <-- managed to reproduce and reduce

These are the reproduced snippets:

// APValue.cpp
class a {
  struct b;
  int c;
  a(const a &);
};

struct a::b {
  int *g;
  void d() { delete[] g; }
};

a::a(const a &e) {
  *this = a(e);
  b f = *(b *)&c;
  f.d();
}
// chrono-test
struct a {
  int b;
  int c;
  int d;
};

int e;

auto f(a h) -> bool {
  e == h.d;
  a g;
  f(g);
}
// main
char a, b;

void c() {
  char d[2];
  *(int *)d = a;
  b = d[1];
}

I need to allocate more time to investigate them, but all of the differences between the old analyzer and the one using this store
look wrong so far.

Thanks for your time.

For the ones I failed to reduce can you please provide, which clang invocation was used?

I must admit that since our infra is suited for our tool, I used our fork (while backporting this patch to it). On our fork, we accept parsing errors or similar things if they don't affect directly the Static Analyzer.
This basically means that we select top-level functions without parsing errors and if we encounter a call to a function that has parsing errors, we just conservative eval call of that function instead of trying to inline it.
Usually, this doesn't have an effect to the results, hence the minimal repro would/should still apply to the upstream-clang as well - it's just harder to get there :D

I didn't check for parsing errors prior to submitting these files, so that's my bad.
I don't have an ETA for coming back to reduce those cases myself. A weak maybe is 1.5-2 weeks.

I started looking at the reduced snippets and it seems I was too hasty to say they are false positives. All of them look correct after analyzing them.

APValue

// APValue.cpp
class a {
  struct b;
  int c;
  a(const a &);
};

struct a::b {
  int *g;
  void d() { delete[] g; }
};

a::a(const a &e) {
  *this = a(e);
  b f = *(b *)&c;
  f.d();
}
preprocessed_APValue.cpp:9:14: warning: Argument to 'delete[]' is uninitialized [core.CallAndMessage]
  void d() { delete[] g; }
             ^~~~~~~~~~

This first one is correct. class a has only 1 data member, int c, so on x86 sizeof(a) == 32. a::b has one int * member, so on x86 sizeof(b) == 64.
b f = *(b *)&c; takes the address of a 32 bit variable, and treats it as a 64 bit variable, so when the pointer is dereferenced, 64 bits are read, out of
which only 32 is initialized.

This is the performed lookup:

Key: "kind": "Direct", "offset": 0, "extent": 64
{"kind": "Direct", "offset": 0, "extent": 32, "value": derived_$5{conj_$2{int, LC5, S1498, #1},temp_object{a, S1498}.c}}
Overlapping bindings:
{
    derived_$5{conj_$2{int, LC5, S1498, #1},temp_object{a, S1498}.c}
    Undefined
}

The question is, why it isn't reported at the moment of the assigment instead. If the i386-pc-linux-gnu triple is used, the warning is not reported.

chrono-test

// chrono-test
struct a {
  int b;
  int c;
  int d;
};

int e;

auto f(a h) -> bool {
  e == h.d;
  a g;
  f(g);
}

This one is also correct. g is an aggregate type on the stack, so all of it's members contain some garbage values. Then g is passed to f(), which
reads one of it's uninitialized fields.

This is the full bugpath:

preprocessed_chrono-test.cc:8:5: warning: The right operand of '==' is a garbage value [core.UndefinedBinaryOperatorResult]
  e == h.d;
    ^
preprocessed_chrono-test.cc:8:3: note: Assuming 'e' is not equal to field 'd'
  e == h.d;
  ^~~~~~~~
preprocessed_chrono-test.cc:9:3: note: 'g' initialized here
  a g;
  ^~~
preprocessed_chrono-test.cc:10:5: note: Uninitialized value stored to 'h.d'
  f(g);
    ^
preprocessed_chrono-test.cc:10:3: note: Calling 'f'
  f(g);
  ^~~~
preprocessed_chrono-test.cc:8:5: note: The right operand of '==' is a garbage value
  e == h.d;
    ^  ~~~

main

// main.c
char a, b;

void c() {
  char d[2];
  *(int *)d = a;
  b = d[1];
}

Here the warning disappeared because a has a symbolic value. Then this symbolic value is assigned to d, and later we read one byte from it,
so the result is considered Unknown.

This is the performed lookup:

Key: "kind": "Direct", "offset": 8, "extent": 8
{"kind": "Direct", "offset": 0, "extent": 32, "value": reg_$0<char a>}
Overlapping bindings:
{
    reg_$0<char a>
}

Before this patch we reported a warning, because the lookup starts at offset 8, not at offset 0.

Thanks for the investigation.

I started looking at the reduced snippets and it seems I was too hasty to say they are false positives. All of them look correct after analyzing them.

// APValue.cpp
class a {
  struct b;
  int c;
  a(const a &);
};

struct a::b {
  int *g;
  void d() { delete[] g; }
};

a::a(const a &e) {
  *this = a(e);
  b f = *(b *)&c;
  f.d();
}
preprocessed_APValue.cpp:9:14: warning: Argument to 'delete[]' is uninitialized [core.CallAndMessage]
  void d() { delete[] g; }
             ^~~~~~~~~~

This first one is correct. class a has only 1 data member, int c, so on x86 sizeof(a) == 32. a::b has one int * member, so on x86 sizeof(b) == 64.
b f = *(b *)&c; takes the address of a 32 bit variable, and treats it as a 64 bit variable, so when the pointer is dereferenced, 64 bits are read, out of
which only 32 is initialized.

This is the performed lookup:

Key: "kind": "Direct", "offset": 0, "extent": 64
{"kind": "Direct", "offset": 0, "extent": 32, "value": derived_$5{conj_$2{int, LC5, S1498, #1},temp_object{a, S1498}.c}}
Overlapping bindings:
{
    derived_$5{conj_$2{int, LC5, S1498, #1},temp_object{a, S1498}.c}
    Undefined
}

The question is, why it isn't reported at the moment of the assigment instead. If the i386-pc-linux-gnu triple is used, the warning is not reported.

I think I would agree if I would only look at the reduced case. However, I think it's highly unlikely that such a widely used type as APValue has this sort of bug. Note that it's being used everywhere, the whole constexpr interpreter is based around that.
So, my guess is that it reduced into a different case. I'd recommend to have tighter constraints during reduction. Maybe match the whole sequence of notes (masking the locations, but keeping the order and content) using some fancy regex.

I haven't looked at the rest, but given that the reduction produced a different case than we began with, I'd say it's likely to happen for the rest of the cases as well.
For example, IMO it's similarly unlikely to find (such a banal) bug in gtest or git TBH.

To conclude, I appreciate the effort, but I'm afraid it's going to be more effort to understand why we have the new reports.
I do think we need better tools for such investigations, but unfortunately I don't have anything helpful for such tricky-to-reduce cases.
I think if anyone has ideas what tooling or techniques can help to uncover such questions, let's gather those ideas in a discuss thread.

I think I would agree if I would only look at the reduced case. However, I think it's highly unlikely that such a widely used type as APValue has this sort of bug. Note that it's being used everywhere, the whole constexpr interpreter is based around that.

I tried reducing it with the method you suggested (matching the whole error path), however that was incredibly slow (~2% after 2 hours). Instead I started logging what happens in the store and checked the results. After a while we end up with this in
the environment: "pretty": "this->PathPtr", "value": "Undefined".

I reverted almost all of the changes and I found that before the checker reports the warning, we perform this lookup:

Lookup key: "kind": "Default", "offset": 64, "extent": 512 region: temp_object{APValue, S1124035}
{"kind": "Default", "offset": 64, "extent": 128 value: lazyCompoundVal{0x5581c0cecc00,B}}
{"kind": "Direct", "offset": 0, "extent": 32 value: 0 U32b}
{"kind": "Direct", "offset": 192, "extent": 64 value: 0 S64b}
{"kind": "Direct", "offset": 256, "extent": 32 value: 4294967295 U32b}

Note that with the current store, this would fail but without the extents it returns lazyCompoundVal{0x5581c0cecc00,B}, where B is coming from here: APValue::setLValueUninit(LValueBase B, ...), so we basically confuse the structures.

One more thing worths mentioning is that the variable from which we report the warning (delete [] PathPtr;) is inside a union, which we don't model AFAIK.

union {
  LValuePathEntry Path[InlinePathSpace];
  LValuePathEntry *PathPtr;
};

Now let's take a closer look to the piece of code, from which the warning comes.

struct LVBase {
   ...
  unsigned PathLength;
  ...
};

struct APValue::LV : LVBase {
  ...
  LV() { PathLength = (unsigned)-1; }
  ...
}

struct APValue {
  ...
  typedef llvm::AlignedCharArrayUnion<void *, APSInt, APFloat, ComplexAPSInt,
                                      ComplexAPFloat, Vec, Arr, StructData,
                                      UnionData, AddrLabelDiffData> DataType;
  DataType Data;
  ...
}
void APValue::MakeLValue() {
  ...
  new ((void *)(char *)&Data) LV();
  ...
}

bool hasPath() const { return PathLength != (unsigned)-1; }

bool APValue::hasLValuePath() const {
  ...
  return ((const LV *)(const char *)&Data)->hasPath();
}

case LValue:
    MakeLValue();             <-- PathLength == -1, set in ctor
    if (RHS.hasLValuePath())  <-- PathLength == -1, we fail to evaluate the condition
      setLValue(...);         <-- warning comes from here

So, basically we fail to read a value from a union properly, which causes us to enter a branch, we should not enter otherwise.

I also extracted a reproducer, which interestingly fails with our current implementation too. See on godbolt.
My conclusion is that this bug wasn't introduced by this patch, it was just hidden before.

cc: @NoQ @xazax.hun

For chrono-test, the lines that prevented us from reporting a warning were these:

if (Result.isUndef())
    Result = UnknownVal();

From the source code that caused the issue, I extracted this reproduce:

using time_t = long int;
extern struct tm *gmtime_r(const time_t *__restrict __timer,
                           struct tm *__restrict __tp) throw();
extern void abort() __attribute__((__noreturn__));

struct tm {
  int tm_sec;
  int tm_min;
  int tm_hour;
};

inline tm gmtime(time_t time) {
  struct dispatcher {
    time_t time_;
    tm tm_;

    dispatcher(time_t t) : time_(t) {}

    bool run() { return gmtime_r(&time_, &tm_) != nullptr; }
  };

  dispatcher gt(time);

  if (!gt.run())
    abort();
  return gt.tm_;
}

void foo() {
  auto rhs = gmtime(0xDEADBEEF);
  int x = rhs.tm_sec;
  (void)x;
}

Note that struct tm has 3 members. If I reduce it down to 1 (let small struct binding policy happen), the current clang also reports the warning.
See on godbolt.

Upon taking a closer look it can be seen that dispatcher has a tm member, however it's not initialized explicitly and it's an aggregate, so no
constructor will be run either. Later this tm is returned by gmtime().

The only catch I see here is that gmtime_r() takes a non-const pointer to tm_, which means it could initialize it. But since the current clang
also reports a warning for this struct, this is probably just another case we fail to handle elsewhere.

cc: @NoQ @xazax.hun

I dug deeper into the missing warning too. Below is the snippet that it comes from:

void ether_addr_copy(u8 *dst, const u8 *src)
{
 *(u32 *)dst = *(const u32 *)src;
 *(u16 *)(dst + 4) = *(const u16 *)(src + 4);
}

static void qedr_mac_address_change(struct qedr_dev *dev)
{
 ...
 u8 mac_addr[6];
 ...
 ether_addr_copy(&mac_addr[0], dev->ndev->dev_addr);
 guid[0] = mac_addr[0] ^ 2;
 guid[1] = mac_addr[1];          <-- warning emitted here
 ...
}

This is how the store looks like at this point:

{ 
"cluster": "mac_addr", "pointer": "0x5634ab4d0190", "items": [
      { "kind": "Direct", "offset": 0, "value": "reg_$20<unsigned int Element{SymRegion{reg_$19<const unsigned char * Element{SymRegion{reg_$4<struct net_device * Element{SymRegion{reg_$1<struct qedr_dev * dev>},0 S64b,struct qedr_dev}.ndev>},0 S64b,struct net_device}.dev_addr>},0 S64b,unsigned int}>" },
      { "kind": "Direct", "offset": 32, "value": "reg_$21<unsigned short Element{SymRegion{reg_$19<const unsigned char * Element{SymRegion{reg_$4<struct net_device * Element{SymRegion{reg_$1<struct qedr_dev * dev>},0 S64b,struct qedr_dev}.ndev>},0 S64b,struct net_device}.dev_addr>},2 S64b,unsigned short}>" }
    ]
}

mac_addr[1] is at offset 8, so here we fail to read a partial value.

With the extends added by this patch, the store looks like this:

{ 
"cluster": "mac_addr", "pointer": "0x564c40a59ce8", "items": [
      { "kind": "Direct", "offset": 0, "extent": 32, "value": "reg_$20<unsigned int Element{SymRegion{reg_$19<const unsigned char * Element{SymRegion{reg_$4<struct net_device * Element{SymRegion{reg_$1<struct qedr_dev * dev>},0 S64b,struct qedr_dev}.ndev>},0 S64b,struct net_device}.dev_addr>},0 S64b,unsigned int}>" },
      { "kind": "Direct", "offset": 32, "extent": 16, "value": "reg_$21<unsigned short Element{SymRegion{reg_$19<const unsigned char * Element{SymRegion{reg_$4<struct net_device * Element{SymRegion{reg_$1<struct qedr_dev * dev>},0 S64b,struct qedr_dev}.ndev>},0 S64b,struct net_device}.dev_addr>},2 S64b,unsigned short}>" }
    ]
}

Here it seems like, the false result is the one, that the current clang reports.

cc: @NoQ @xazax.hun

Via Web