Page MenuHomePhabricator

[llvm-dwarfdump] Fix unsigned overflow when calculating stats
ClosedPublic

Authored by djtodoro on Sep 3 2021, 2:44 AM.

Details

Summary

This fixes https://bugs.llvm.org/show_bug.cgi?id=51652.

The idea is to bump all the stat fields to 64-bit wide unsigned integers. I've confirmed this resolves the use case for chromium.

Diff Detail

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes
djtodoro requested review of this revision.Sep 3 2021, 2:44 AM
Orlando added a subscriber: Orlando.Sep 3 2021, 4:28 AM
Orlando added inline comments.
llvm/tools/llvm-dwarfdump/Statistics.cpp
416–417

I think this assert should come before the assignment and be something like this to catch a value that would "overflow" by wrapping:
assert(GlobalStats.ScopeBytesCovered + ScopeBytesCovered >= GlobalStats.ScopeBytesCovered && "ScopeBytesCovered - overflow");
Otherwise I don't think this assertion will ever catch anything, since all uint64_t values are <= UINT64_MAX.

Seems like a generally reasonabel direction forward.

llvm/tools/llvm-dwarfdump/Statistics.cpp
416–417

Yep! I think the more general assert probably looks like this:

assert(x <= max - y)
x += y;
418–419

When would this assert fire? If ScopeEntryValueBytesCovered is a uint64_t, it can't ever be > than the max uint64_t value.

Checking for overflow would usually be done, I tihnk, with a check before the overflow:

assert(x <= max - y)
x += y;

no other comments, thanks for the fix!

djtodoro added inline comments.Sep 6 2021, 2:01 AM
llvm/tools/llvm-dwarfdump/Statistics.cpp
416–417

Oh yes, thanks

Probably enough to write the portable code (so it works on MSVC too, etc) and let the compiler optimize it. At least for this saturation code, Clang produces the same with or without the intrinsic (& GCC produces something else entirely - to itself and to clang): https://godbolt.org/z/jb3nnaKvT

Probably enough to write the portable code (so it works on MSVC too, etc) and let the compiler optimize it. At least for this saturation code, Clang produces the same with or without the intrinsic (& GCC produces something else entirely - to itself and to clang): https://godbolt.org/z/jb3nnaKvT

Maybe LLVM should learn saturating integers that assert in debug mode?

Probably enough to write the portable code (so it works on MSVC too, etc) and let the compiler optimize it. At least for this saturation code, Clang produces the same with or without the intrinsic (& GCC produces something else entirely - to itself and to clang): https://godbolt.org/z/jb3nnaKvT

Maybe LLVM should learn saturating integers that assert in debug mode?

Perhaps. (though anything that asserts in debug mode should basically be UB in non-debug mode, in my opinion - if you aren't testing/using the functionality, it shouldn't be defined)

For ints we've got UBSan, but unsigned ints are defined on wrap. There's no unsigned type that's UB on overflow - certainly might be nice to have them to clarify the difference between a think you want to do weird bitfiddling with and expect all the overflow, etc, and a thing that's meant to do maths and where sanitizers could diagnose overflow, etc.

But I think a couple of manual overflow checks here is probably OK - might be worth putting it in a generic function and applying it to all the statistics to make things more robust/generic.

xbolva00 added a subscriber: xbolva00.EditedSep 6 2021, 1:09 PM

For ints we've got UBSan, but unsigned ints are defined on wrap. There's no unsigned type that's UB on overflow - certainly might be nice to have them to clarify the difference between a think you want to do weird bitfiddling with and expect all the overflow, etc, and a thing that's meant to do maths and where sanitizers could diagnose overflow, etc.

-fsanitize=unsigned-integer-overflow ?

For ints we've got UBSan, but unsigned ints are defined on wrap. There's no unsigned type that's UB on overflow - certainly might be nice to have them to clarify the difference between a think you want to do weird bitfiddling with and expect all the overflow, etc, and a thing that's meant to do maths and where sanitizers could diagnose overflow, etc.

-fsanitize=unsigned-integer-overflow ?

Oh, right, we do have that :) (but no doubt LLVM isn't remotely clean of failures for it)

djtodoro updated this revision to Diff 371007.Sep 7 2021, 1:49 AM
djtodoro edited the summary of this revision. (Show Details)
  • add a test
  • bump the stats version
  • address the comments (I think that these few asserts are enough for this)
  • split JSON part into a separate patch
djtodoro retitled this revision from [NOT FOR COMMIT] [llvm-dwarfdump] Fix unsigned overflow when calculating stats to [llvm-dwarfdump] Fix unsigned overflow when calculating stats.Sep 7 2021, 1:49 AM

Just one more inline question from me, but I will defer to the other reviewers for the rest & approval. Thanks for fixing this.

llvm/tools/llvm-dwarfdump/Statistics.cpp
789–804

I'm not sure how much this matters but looking at the comment above I don't think a version bump is necessary for this patch? Any input that didn't trip the assertions previously will still have the same output with the patch applied.

djtodoro added inline comments.Sep 7 2021, 3:28 AM
llvm/tools/llvm-dwarfdump/Statistics.cpp
789–804

I think since this is a bug fix we should bump it -- e.g., a stat number could have been 0 (as a consequence of the bug), and now it will be 2^32 for example, right? I think that this is the purpose behind the stats version.

tschuett added a comment.EditedSep 7 2021, 9:58 AM

Let me revisit the saturating integer without asserts. If you print 5 for an uint32_t, you will never know whether it overflowed never or 10 times (in release mode).

A saturating integer will print 5 or max int (saturated).

Even an SaturatingUint<uint64_t> shouldn't yield too much overhead.

Let me revisit the saturating integer without asserts. If you print 5 for an uint32_t, you will never know whether it overflowed never or 10 times (in release mode).

A saturating integer will print 5 or max int (saturated).

Even an SaturatingUint<uint64_t> shouldn't yield too much overhead.

Hmm, is there an implementation of the SaturatingUint, or do we need to implement such type?

Not at the moment. I just wanted to pitch the idea of having a saturating integer in LLVM.

I think we can implement it here, and it will be useful/safe.
The question is if that should be implemented as a general thing in LLVM.

It seems like the down side of using asserts to detect the "overflow" (the patch's current approach) is that release-config users may still get misleading stats due to wrapping. Implementing a saturating int in and of itself doesn't seem like a full solution, since a user may not notice that the stat is the saturated value, or even know that it's special, especially if the stats are consumed by another tool.

IMO when the stat cannot be computed properly - however the detection is implemented, either with saturating ints, checks like the ones in the asserts, or something else - a good solution for users would be to print a message, and either skip printing the "bad" stats or all of them. That would be consistent for all build configurations and avoid hiding the issue. What do you think? Sorry if I'm just stating the obvious!

llvm/tools/llvm-dwarfdump/Statistics.cpp
789–804

Sounds reasonable (I wasn't thinking about release mode when I made that comment).

You will always know whether it is max int or max int because of saturating behaviour.

class SatUint32 {
  uint32_t value;
  bool overflowed;
}

The saturating integer class would use the builtins I mentioned above to perform arithmetic operations on value and detect overflow and set overflow to true.

I'd just saturate to max int, and use the max int value to indicate overflow. Shaving one value off to represent the overflow state seems fine to me.

That is fine be me. I guess the point is a save way to collect statistics and give guidance to users when the results could be bad, in release and debug mode. I would argue that saturating integers are different and maybe more precise solution than going from uint32_t to uint64_t ...

That is fine be me. I guess the point is a save way to collect statistics and give guidance to users when the results could be bad, in release and debug mode. I would argue that saturating integers are different and maybe more precise solution than going from uint32_t to uint64_t ...

Well, both, probably - support use cases that weren't supported before (binaries that were too large to fit in the existing stats) and, separately/additionally, some way of reporting overflow rather than reporting bogus values.

djtodoro updated this revision to Diff 372234.Sep 13 2021, 6:31 AM
  • Introduce the SaturatingUINT64
xbolva00 added a comment.EditedSep 13 2021, 7:13 AM

I'd just saturate to max int, and use the max int value to indicate overflow. Shaving one value off to represent the overflow state seems fine to me.

+1, do not need Overflow flag.

djtodoro updated this revision to Diff 373193.Sep 17 2021, 4:47 AM

-remove the isOverflow field

dblaikie added inline comments.Sep 17 2021, 9:03 AM
llvm/tools/llvm-dwarfdump/Statistics.cpp
71

Personally, I think once we've defined the behavior on overflow, we shouldn't assert that overflow doesn't happen - this undermines the concept of having defined behavior on overflow (& makes it somewhat harder to test - since that behavior can now only be tested in a non-asserts build (well, I guess since assert isn't UB-if-false, and the assert is after the warning, that's not the case, but it's a bit subtle)).

Also, might it make more sense to do the warning/etc on the final use/printing out of the statistic instead? (I guess that's difficult because some statistics are derived from others? - so catching it the moment it overflows means it'll always be diagnosed only once, rather than multiple times due to multiple uses?)

djtodoro added inline comments.Sep 20 2021, 8:15 AM
llvm/tools/llvm-dwarfdump/Statistics.cpp
71

Thanks for the suggestions. I totally agree.

I guess that it makes sense to report the warning when printing the overflowed value, since we can point to the specific field.

djtodoro updated this revision to Diff 373595.Sep 20 2021, 8:19 AM
  • addressing comments
    • now the warning looks as follows:
"#call site DIEs": N (llvm-dwarfdump: warning: this field overflows),
  • addressing comments
    • now the warning looks as follows:
"#call site DIEs": N (llvm-dwarfdump: warning: this field overflows),

Maybe we could render it symbolically and just say:

"#call site DIEs": >= 9223372036854775807

But yeah, maybe the warning is more suitable, not sure - I'll leave it up to you folks to decide what's best.

@cmtice @rdhindsa - might be handy if you folks are aware of this in terms of quirks when encoding the stats from our internal analysis pipelines, in case the format chosen here needs to be taken into account for how to render out of range data.

  • addressing comments
    • now the warning looks as follows:
"#call site DIEs": N (llvm-dwarfdump: warning: this field overflows),

Maybe we could render it symbolically and just say:

"#call site DIEs": >= 9223372036854775807

But yeah, maybe the warning is more suitable, not sure - I'll leave it up to you folks to decide what's best.

I'd prefer the warning since it will be easier when parsing the JSON data from utilities such as llvm-locstats.

dblaikie added inline comments.Oct 5 2021, 12:15 PM
llvm/test/tools/llvm-dwarfdump/X86/locstats-bytes-overflow.yaml
25

I think it'd be worth CHECKing the specific/full syntax, rather than just "this warning text appears somewhere in the output" - since we're specifically putting it in the output in a particular place.

Hmm, that raises a question: is this warning going to stderr, but the actual stats output is to stdout? If so then I think that's a different problem. Maybe that answers one of my other questions though when I suggested printing the output as "> max int" - https://reviews.llvm.org/D109217#3012175 - is that what you meant in this comment? That the value in the JSON data doesn't have any mention of the warning/overflow, and only has the saturated integer value?

I worry that's error-prone though, since the value is incorrect and a tool might not be aware of that. So I think it may be valuable to ensure we don't encode a valid value/something that could be mistaken for a valid value in the field when it's overflowed?

JSON supports the value being a string, I assume - so perhaps a string representation of ">= max int" or "overflowed" or something would be suitable?

llvm/tools/llvm-dwarfdump/Statistics.cpp
51–56

Maybe just implement this in terms of the other:

djtodoro added inline comments.Oct 7 2021, 1:18 AM
llvm/test/tools/llvm-dwarfdump/X86/locstats-bytes-overflow.yaml
25

Yep, that was my concern. It was going to stderr, but the JSON data goes to stdout.

JSON supports the value being a string, I assume - so perhaps a string representation of ">= max int" or "overflowed" or something would be suitable?

Hmm, I agree... using some special value will make this output ready for the tools from outside. I'll update that.

llvm/tools/llvm-dwarfdump/Statistics.cpp
51–56

yes, thanks

djtodoro updated this revision to Diff 377759.Oct 7 2021, 1:22 AM
  • introduce "overflow" special stats value for the fields that overflow

This looks alright to me - though I'll leave it to toher folks with more statistics interest to provide final approval.

(@cmtice @rdhindsa - something to be aware of that might crop-up in google uses of the statistics infrastructure, I'd expect)

This looks alright to me - though I'll leave it to toher folks with more statistics interest to provide final approval.

(@cmtice @rdhindsa - something to be aware of that might crop-up in google uses of the statistics infrastructure, I'd expect)

Sure, thanks for your comments!

I think this is reasonable, out of curiosity, would there be a benefit to using APInt? Probably not because 64 bits is already huge...

I think this is reasonable, out of curiosity, would there be a benefit to using APInt? Probably not because 64 bits is already huge...

I guess we can use APInt as well, but the 64 bits seem enough for now. A challenge would be to teach all the front-ends how to parse the big numbers (>64bits), but it is achievable.

aprantl accepted this revision.Oct 11 2021, 10:01 AM

Ok. Works for me.

llvm/tools/llvm-dwarfdump/Statistics.cpp
53
This revision is now accepted and ready to land.Oct 11 2021, 10:01 AM
djtodoro marked an inline comment as done.Oct 12 2021, 12:54 AM

Thanks!

djtodoro updated this revision to Diff 378908.Oct 12 2021, 12:54 AM

-use the std::numeric_limits<uint64_t>::max()