This is an archive of the discontinued LLVM Phabricator instance.

[UBSan][clang][compiler-rt] Applying non-zero offset to nullptr is undefined behaviour
ClosedPublic

Authored by lebedev.ri on Sep 3 2019, 11:43 AM.

Details

Summary

Quote from http://eel.is/c++draft/expr.add#4:

4     When an expression J that has integral type is added to or subtracted
      from an expression P of pointer type, the result has the type of P.
(4.1) If P evaluates to a null pointer value and J evaluates to 0,
      the result is a null pointer value.
(4.2) Otherwise, if P points to an array element i of an array object x with n
      elements ([dcl.array]), the expressions P + J and J + P
      (where J has the value j) point to the (possibly-hypothetical) array
      element i+j of x if 0≤i+j≤n and the expression P - J points to the 
      (possibly-hypothetical) array element i−j of x if 0≤i−j≤n.
(4.3) Otherwise, the behavior is undefined.

Therefore, as per the standard, applying non-zero offset to nullptr
(or making non-nullptr a nullptr, by subtracting pointer's integral value
from the pointer itself) is undefined behavior. (*if* nullptr is not defined,
i.e. e.g. -fno-delete-null-pointer-checks was *not* specified.)

To make things more fun, in C (6.5.6p8), applying *any* offset to null pointer
is undefined, although Clang front-end pessimizes the code by not lowering
that info,so this UB is "harmless".

Since rL369789 (D66608 [InstCombine] icmp eq/ne (gep inbounds P, Idx..), null -> icmp eq/ne P, null)
LLVM middle-end uses those guarantees for transformations.
If the source contains such UB's, said code may now be miscompiled.
Such miscompilations were already observed:

Surprisingly, UBSan does not catch those issues
... until now. This diff teaches UBSan about these UB's.

getelementpointer inbounds is a pretty frequent instruction,
so this does have a measurable impact on performance;
I've addressed most of the obvious missing folds (and thus decreased the performance impact by ~5%),
and then re-performed some performance measurements using my RawSpeed benchmark:
(all measurements done with LLVM ToT, the sanitizer never fired.)

  • no sanitization vs. existing check: average +21.62% slowdown
  • existing check vs. check after this patch: average 22.04% slowdown
  • no sanitization vs. this patch: average 48.42% slowdown

Diff Detail

Event Timeline

lebedev.ri created this revision.Sep 3 2019, 11:43 AM
Herald added a project: Restricted Project. · View Herald TranscriptSep 3 2019, 11:43 AM

NFC, fixup docs.

One fear I have with this is in expansions of the offsetof macro, where it is a common implementation strategy to cast a null pointer to be of the correct type when calculating member offsets. Do you think you will be able to distinguish between null pointer additions that the user wrote directly (which is UB) as opposed to null pointer additions that come from the implementation (which is not UB)?

One fear I have with this is in expansions of the offsetof macro, where it is a common implementation strategy to cast a null pointer to be of the correct type when calculating member offsets. Do you think you will be able to distinguish between null pointer additions that the user wrote directly (which is UB) as opposed to null pointer additions that come from the implementation (which is not UB)?

Can you show a snippet on godbolt?

One fear I have with this is in expansions of the offsetof macro, where it is a common implementation strategy to cast a null pointer to be of the correct type when calculating member offsets. Do you think you will be able to distinguish between null pointer additions that the user wrote directly (which is UB) as opposed to null pointer additions that come from the implementation (which is not UB)?

Can you show a snippet on godbolt?

https://godbolt.org/z/5DHL2E

This will show that Clang has a __builtin_offsetof() that gets used. I'm worried about situations where there is no __builtin_offsetof() but the canonical reference implementation is used instead (which looks identical to what initializes bad in my link).

xbolva00 added inline comments.
compiler-rt/test/ubsan/TestCases/Pointer/index-overflow.cpp
15

Not very friendly error msg since the original code has no sub.

Add test that show that __builtin_offsetof() / ((uintptr_t)(&(((S *)nullptr)->y))) are already not sanitized.

lebedev.ri updated this revision to Diff 218533.Sep 3 2019, 2:41 PM
lebedev.ri marked an inline comment as done.

Reworded (ptr - intptr_t(ptr)) -> nullptr ubsan message to be less specific.

Currently, EmitCheckedInBoundsGEP() is used sparsely,
a lot of GEP inbounds are created directly.
While i suspect that is being done intentionally:

rL304459

  • It does not check some GEPs in CGExprCXX. I'm not sure that inserting checks here, or in CGClass, would catch many bugs.

and i think that may have made sense for the original check
(overflow), i'm not sure we get to be this picky here.

I'm still deliberating, but i suspect it will be a good idea
to change all Builder.Create*InBoundsGEP*() in clang CodeGen
to go through EmitCheckedInBoundsGEP().
Although i suppose those new cases should only run this sanitizer.

xbolva00 added inline comments.Sep 3 2019, 2:51 PM
llvm/docs/ReleaseNotes.rst
59

Please add a reference to C/C++ standard that this is a UB.

lebedev.ri marked 2 inline comments as done.Sep 3 2019, 2:58 PM
lebedev.ri added inline comments.
llvm/docs/ReleaseNotes.rst
59

It is irrelevant what semantics C/C++ standard has/doesn't have for whatever C/C++ construct,
this is talking about LLVM IR.

xbolva00 added inline comments.Sep 3 2019, 3:06 PM
llvm/docs/ReleaseNotes.rst
59

Ok, so Clang docs?

“The compiler now optimizes ... since ... is a UB according to ... Use UBSan to catch these cases.”

lebedev.ri updated this revision to Diff 218542.Sep 3 2019, 3:10 PM
lebedev.ri marked 3 inline comments as done.

clang/docs/ReleaseNotes.rst: also mention C17 verse in addition to C++ verse.

llvm/docs/ReleaseNotes.rst
59

... see clang/docs/ReleaseNotes.rst then?
Those words were present in the first revision of the differential already,
https://reviews.llvm.org/D67122?id=218504#change-RNUd6wICb9iD

xbolva00 added inline comments.Sep 3 2019, 3:20 PM
llvm/docs/ReleaseNotes.rst
59

Oh, sorry.

vsk added inline comments.Sep 3 2019, 3:20 PM
clang/docs/UndefinedBehaviorSanitizer.rst
177

Why does this need to be a separate sanitizer, as opposed to being a part of -fsanitize=pointer-overflow? Is there a need for a new group?

clang/lib/CodeGen/CGExprScalar.cpp
4544–4554

s/has//, s/been//

clang/lib/CodeGen/CodeGenFunction.h
4072

Why does this need to be a method in CodeGenFunction? This seems too tied to the work done in EmitCheckedInBoundsGEP to warrant inclusion here.

compiler-rt/lib/ubsan/ubsan_handlers.cpp
715

I don't think these diagnostics generally need to repeat the fact that there is UB: that seems implicit.

How about: 'non-zero offset %0 applied to null pointer', and 'non-zero offset %0 applied to non-null pointer %1 produced null'?

lebedev.ri updated this revision to Diff 218556.Sep 3 2019, 3:39 PM
lebedev.ri marked 7 inline comments as done.

@vsk thank you for taking a look!
Review notes addressed, except grouping one.

clang/docs/UndefinedBehaviorSanitizer.rst
177

That ties in with the question i'm asking myself in last update:
https://reviews.llvm.org/D67122#1656418
I.e., would it be okay to produce *all* these checks for every gep inbounds we codegen, indiscriminantly,
as opposed to only always producing this nullptr-and-nonzero-offset?

compiler-rt/lib/ubsan/ubsan_handlers.cpp
715

I don't think these diagnostics generally need to repeat the fact that there is UB: that seems implicit.

Sure, ok.

'non-zero offset %0 applied to non-null pointer %1 produced null'?

I don't want to spell any more info that it already does, it isn't really useful here.
Also, we only receive the base pointer and the computed pointer.
We don't know the actual offset, we may have done ptr - intptr_t(ptr),
or maybe it was ptr + (0-intptr_t(ptr)).
(Sure, we could receive more info, but i'm not sure worth it here.)

llvm/docs/ReleaseNotes.rst
59

NP :)

vsk added inline comments.Sep 3 2019, 4:46 PM
clang/docs/UndefinedBehaviorSanitizer.rst
177

It's worth considering whether or not to emit a checked GEP on a case-by-case basis. For example, there are some GEPs emitted in the ABI lowering logic that are not likely to catch bugs in user code. I'm not sure what the point of instrumenting these would be.

Separately, the proposed 'nullptr-and-nonzero-offset' check is interesting only/exactly when the existing 'pointer-overflow' check is interesting, and vice versa. So I don't see the need to make them distinct.

compiler-rt/lib/ubsan/ubsan_handlers.cpp
715

Works for me.

lebedev.ri updated this revision to Diff 218720.Sep 4 2019, 8:31 AM
lebedev.ri marked 3 inline comments as done.

Merged the check into pointer-overflow, revisited test coverage.
Using EmitCheckedInBoundsGEP() in more places TBD.

lebedev.ri marked an inline comment as done.Sep 4 2019, 8:32 AM
lebedev.ri added inline comments.
clang/lib/CodeGen/CGExprScalar.cpp
4691–4708

This makes me ick every time i look at it.
I wonder if this can be sanely rewritten via .with.overflow intrinsic..

vsk added a subscriber: dtzWill.Sep 4 2019, 11:33 AM

Thanks, this is looking pretty good.

clang/lib/CodeGen/CGExprScalar.cpp
4539

Please document this helper. Also, consider having it return a struct, so that the field names don't need to be specified as comments. It'd be great to move the documentation for the TotalOffset and OffsetOverflows fields in EmitCheckedInBoundsGEP into the struct definition.

4669

nit: don't expect

4677

nit: pointers

clang/test/CodeGen/catch-nullptr-and-nonzero-offset-blacklist.c
2

Should the test filename be "ignore-nullptr-and-nonzero-..."?

6

The baseline case is tested elsewhere, why include it here?

clang/test/CodeGen/catch-nullptr-and-nonzero-offset-in-offsetof-idiom.c
1 ↗(On Diff #218720)

Should the test filename be "ignore-nullptr-and-nonzero-..."?

14 ↗(On Diff #218720)

nit: CHECK-LABEL: define i64 @get_offset_of_y(

clang/test/CodeGen/catch-nullptr-and-nonzero-offset.c
13

nit: versa

29

I don't quite follow the comments. Perhaps it would be simpler to list the expected checks in the comment, e.g. "The base and offset are unknown. Check for pointer wrap and null status change."

67

Does this simplify to:

CHECK-LABEL: define i8* @var_zero_ok(
CHECK-NOT: !nosanitize
clang/test/CodeGen/ubsan-pointer-overflow.m
48 ↗(On Diff #218720)

I'm curious about what happens here with the new null-status-change check. If array indices are unsigned, there is no need for a separate null-status-change check: if the result of the GEP is indeed null, that will be detected by the pointer wraparound check. We just need to check that the base pointer itself isn't null.

That generalizes to addition of unsigned offsets to base pointers, I think. So e.g. I wouldn't expect the 'preinc' function to contain a null-status-change check either.

clang/test/CodeGenCXX/catch-nullptr-and-nonzero-offset-in-offsetof-idiom.cpp
1 ↗(On Diff #218720)

How is this different from the other offsetof test file?

compiler-rt/test/ubsan/TestCases/Pointer/nullptr-and-nonzero-offset-constants.cpp
23

Should be 'produced null pointer' or 'gave null result'

compiler-rt/test/ubsan_minimal/TestCases/nullptr-and-nonzero-offset.c
2

implicit-check-not="pointer-overflow"?

lebedev.ri updated this revision to Diff 218792.Sep 4 2019, 2:35 PM
lebedev.ri marked 25 inline comments as done.

@vsk thank you for taking a look!
I believe i have addressed or replied to all the comments.
Other than the optimization comment, i currently don't believe that is a sound transform.

clang/lib/CodeGen/CGExprScalar.cpp
4539

Uh, comment got lost when it became static.

4669

I'm not sure what you mean here. Changed, not sure if this is what you meant.

4691–4708

Hm,

Name: add unsigned
  %computed = add i8 %base, %offset
  %PosOrZeroValid = icmp uge i8 %computed, %base
=>
  %agg = uadd_overflow i8 %base, %offset
  %computed = extractvalue i8 %agg, 0
  %ov = extractvalue i1 %agg, 1
  %PosOrZeroValid = xor i1 %ov, -1

Name: sub unsigned
  %computed = add i8 %base, %offset
  %PosOrZeroValid = icmp ule i8 %computed, %base
=>
  %negated_offset = sub i8 0, %offset
  %agg = usub_overflow i8 %base, %negated_offset
  %computed = extractvalue i8 %agg, 0
  %ov = extractvalue i1 %agg, 1
  %PosOrZeroValid = xor i1 %ov, -1

Name: add signed
  %computed = add i8 %base, %offset
  %PosOrZeroValid = icmp uge i8 %computed, %base
  %PosOrZeroOffset = icmp sge i8 %offset, 0
  %NegValid = icmp ult i8 %computed, %base
  %OKay = select i1 %PosOrZeroOffset, i1 %PosOrZeroValid, i1 %NegValid
=>
  %uadd.agg = uadd_overflow i8 %base, %offset
  %uadd.ov = extractvalue i1 %uadd.agg, 1
  %negated_offset = sub i8 0, %offset
  %usub.agg = usub_overflow i8 %base, %negated_offset
  %usub.ov = extractvalue i1 %usub.agg, 1
  %computed = add i8 %base, %offset
  %PosOrZeroOffset = icmp sge i8 %offset, 0
  %NotOKay = select i1 %PosOrZeroOffset, i1 %uadd.ov, i1 %usub.ov
  %OKay = xor i1 %NotOKay, -1

That's not great, but i wonder what is more friendly to middle-end.
https://godbolt.org/z/ORSU_L

clang/test/CodeGen/catch-nullptr-and-nonzero-offset-blacklist.c
2

-blacklist.c is the filename i have i used for all similar testfiles in all previous sanitizers.
"black list" means here "list of cases where no sanitization will be emitted".

6

So the rest won't have false-positive just because -fsanitize=pointer-overflow is omitted.

clang/test/CodeGen/catch-nullptr-and-nonzero-offset-in-offsetof-idiom.c
14 ↗(On Diff #218720)

No, because this runs both in C mode and in C++ mode, so the name may be mangled.

clang/test/CodeGen/catch-nullptr-and-nonzero-offset.c
29

These comments are rather pointless now that the checks are merged, i'll just drop them.

67

I find it easier to reason about readable check lines.

clang/test/CodeGenCXX/catch-nullptr-and-nonzero-offset-in-offsetof-idiom.cpp
1 ↗(On Diff #218720)

It uses nullptr specifically, unlike 0.

compiler-rt/test/ubsan/TestCases/Pointer/nullptr-and-nonzero-offset-constants.cpp
23

Oh, i was looking for better spelling, but didn't think of produced. Thanks!

lebedev.ri added inline comments.Sep 4 2019, 2:35 PM
clang/test/CodeGen/catch-nullptr-and-nonzero-offset-in-offsetof-idiom.c
1 ↗(On Diff #218720)

Honestly, i'm using the consistent file naming scheme of catch-<option-name-or-so>, so that they are all checked by
$ ninja clang && ./bin/llvm-lit -v -v -vv /repositories/llvm-project/clang/test/CodeGen/catch-*

clang/test/CodeGen/ubsan-pointer-overflow.m
48 ↗(On Diff #218720)

Ugh, i still hate those codegen-time optimizations :)
Not only do they result in a maze that is 'hard' to comprehend and argue about,
the middle-end isn't "forced" to know these folds so the other code stays unoptimized,
worse yet, unlike miscompile that will be detected, if the logic error is made here,
it will likely "only" result in false-negatives :(

We just need to check that the base pointer itself isn't null.

I don't believe that is sound for unsigned add: https://rise4fun.com/Alive/2J5 - will consider that base=0 offset=0 is invalid.
Likewise, does not seem valid for unsigned sub: https://rise4fun.com/Alive/VEr - will not detect when pointer becomes null.
Likewise, does not seem valid for signed add/sub: https://rise4fun.com/Alive/97B - will not detect when pointer becomes null.

So, i'm not going to touch this. Unless i'm getting the gist of your comment wrong, or wrote those checks wrong?

lebedev.ri marked an inline comment as done.Sep 4 2019, 2:36 PM
vsk added a comment.Sep 5 2019, 1:00 PM

Still think this looks good. Have you tried running this on the llvm test suite, or some other interesting corpus? Would be curious to see any pre/post patch numbers.

clang/lib/CodeGen/CGExprScalar.cpp
4691–4708

I suggest splitting out changes to the existing pointer wraparound check in a follow-up patch. This may well be an improvement, but there are enough moving parts to this patch as-is.

clang/test/CodeGen/catch-nullptr-and-nonzero-offset-blacklist.c
2

This is minor. I only raised the nit as I felt that this test was about ignoring "foo", not about catching "foo", and that "blacklist" already means something else in the context of sanitizers. Happy to defer to your preference here.

clang/test/CodeGen/catch-nullptr-and-nonzero-offset.c
67

Ah, sure, having the IR written out explicitly can help. The downside is that it's more to read/maintain, and arguably the key idea here is that "no sanitizer stuff happens" since presumably IRGen for generic pointer arithmetic is tested elsewhere, but again this is minor & I'm happy to defer on this.

clang/test/CodeGen/ubsan-pointer-overflow.m
48 ↗(On Diff #218720)

Totally see your point and understand the frustration :), we all want a tidy/simple frontend. And thanks for sharing these counter-examples. The context for my comment here is that -O0 -g and -Os -g compile-time and run-time performance (yes! -O0 run-time performance, really) matters a fair amount for Xcode users, and tend to regress with sanitizer changes. If there are simple (and correct :) ways to avoid regressing these, it's a plus.

Still think this looks good. Have you tried running this on the llvm test suite, or some other interesting corpus? Would be curious to see any pre/post patch numbers.

I finally had time this morning to patch this in and give it a shot. (Sorry for the delay... it's been a real busy week :( )

First, starting off with the good news: I reverted all the fixes I made, and now all the tests fail when running w/ ubsan. Yay!

The error we see in each case is UndefinedBehaviorSanitizer: nullptr-with-nonzero-offset with the logs containing runtime error: applying non-zero offset <non-zero> to null pointer. Which catches the two places where we were adding some non-zero offset to nullptr, but doesn't seem to catch the nullptr-after-nonzero-offset case in https://github.com/google/filament/pull/1566 -- instead, it fails later, when the pointer with a value of nullptr is incremented. (Or... maybe this is actually a separate bug. Hmm. Needs some more testing...)

At any rate, I have some more tests to run to get some idea of what % of code this would flag as being bad.

Still think this looks good. Have you tried running this on the llvm test suite, or some other interesting corpus? Would be curious to see any pre/post patch numbers.

I finally had time this morning to patch this in and give it a shot. (Sorry for the delay... it's been a real busy week :( )

First, starting off with the good news: I reverted all the fixes I made, and now all the tests fail when running w/ ubsan. Yay!
The error we see in each case is UndefinedBehaviorSanitizer: nullptr-with-nonzero-offset with the logs containing runtime error: applying non-zero offset <non-zero> to null pointer. Which catches the two places where we were adding some non-zero offset to nullptr,

That is good :)

but doesn't seem to catch the nullptr-after-nonzero-offset case in https://github.com/google/filament/pull/1566 -- instead, it fails later, when the pointer with a value of nullptr is incremented. (Or... maybe this is actually a separate bug. Hmm. Needs some more testing...)

Well yeah, there are quite a few cases in clang codegen where we create gep inbounds without sanitization, so it may or may not be one of those cases.

At any rate, I have some more tests to run to get some idea of what % of code this would flag as being bad.

lebedev.ri marked 5 inline comments as done.Sep 6 2019, 6:30 AM
lebedev.ri added inline comments.
clang/lib/CodeGen/CGExprScalar.cpp
4691–4708

I'll just precommit them, they are NFC.

clang/test/CodeGen/catch-nullptr-and-nonzero-offset-blacklist.c
2

Nitpicking is good, less chance to omit something that wasn't intentional and is thus bad :)

clang/test/CodeGen/ubsan-pointer-overflow.m
48 ↗(On Diff #218720)

I mean, yeah, -O0 is unreplaceable for best debugging expirience, and it is pretty sluggish.

lebedev.ri updated this revision to Diff 219103.Sep 6 2019, 7:36 AM
lebedev.ri marked 4 inline comments as done.

Rebased over precommitted NFC changes, much nicer diff! :)

I will still need to see where else EmitCheckedInBoundsGEP() should be used, but i'm wondering
if it should be best done in follow-ups, since this already catches the interesting bits..

In D67122#1659721, @vsk wrote:

Still think this looks good. Have you tried running this on the llvm test suite, or some other interesting corpus? Would be curious to see any pre/post patch numbers.

There were 1.5 occurrences in test-suite.
I'd prefer not to try running it over llvm stage-2/3 (i can, but it's gonna be slow..)

Though i guess you were talking about *performance* numbers?

I'm not good with using test-suite for perf, so i'm yet again going to use my own bench.

TLDR: (all measurements done with llvm ToT, the sanitizer never fired.)

  • no sanitization vs. existing check: average +20.75% slowdown
  • existing check vs. check after this patch: average +26.36% slowdown
  • no sanitization vs. this patch: average +52.58% slowdown

I suspect some of this might be recoverable, but i don't know yet.

@vsk let me know if that answered your questions. thanks!

Still think this looks good. Have you tried running this on the llvm test suite, or some other interesting corpus? Would be curious to see any pre/post patch numbers.

I finally had time this morning to patch this in and give it a shot. (Sorry for the delay... it's been a real busy week :( )

First, starting off with the good news: I reverted all the fixes I made, and now all the tests fail when running w/ ubsan. Yay!
The error we see in each case is UndefinedBehaviorSanitizer: nullptr-with-nonzero-offset with the logs containing runtime error: applying non-zero offset <non-zero> to null pointer. Which catches the two places where we were adding some non-zero offset to nullptr,

That is good :)

but doesn't seem to catch the nullptr-after-nonzero-offset case in https://github.com/google/filament/pull/1566 -- instead, it fails later, when the pointer with a value of nullptr is incremented. (Or... maybe this is actually a separate bug. Hmm. Needs some more testing...)

Well yeah, there are quite a few cases in clang codegen where we create gep inbounds without sanitization, so it may or may not be one of those cases.

At any rate, I have some more tests to run to get some idea of what % of code this would flag as being bad.

@rupprecht

So i have tried to reduce https://github.com/google/filament/pull/1566/files
CommandBase by hand, and arrived at: https://godbolt.org/z/O7svxp

And it is clearly being sanitized, and you wouldn't even get to call execute()
with this = nullptr, a check for that was inserted too.

If you revert whatever fixes that were applied, fix the code
about which sanitizer complaints, does that fix miscompilation?

But TLDR, either the fix in https://github.com/google/filament/pull/1566
is incorrect and the actually-bad code is elsewhere,
or you have some other unsanitized UB elsewhere. Could be both :S

lebedev.ri edited the summary of this revision. (Show Details)Sep 6 2019, 1:03 PM

But TLDR, either the fix in https://github.com/google/filament/pull/1566
is incorrect and the actually-bad code is elsewhere,
or you have some other unsanitized UB elsewhere. Could be both :S

My money is on "both" :p

I tested a random sample of a couple thousand tests internally and ~1% of them failed, but when I looked at them, they were all coming from two separate widely used libraries. I fixed those, and I'll do a broader test now to see how bad the long tail of issues are.

nikic added a subscriber: nikic.Sep 7 2019, 2:36 PM
vsk added a comment.Sep 9 2019, 12:52 PM
In D67122#1659721, @vsk wrote:

Still think this looks good. Have you tried running this on the llvm test suite, or some other interesting corpus? Would be curious to see any pre/post patch numbers.

There were 1.5 occurrences in test-suite.

I'd prefer not to try running it over llvm stage-2/3 (i can, but it's gonna be slow..)

Though i guess you were talking about *performance* numbers?

Yes, I'm primarily interested in run-time and compile-time performance (at {-O0 -g, -Os -g}). The number of occurrences of new diagnostics is also interesting. What does the .5 mean?

I'm not good with using test-suite for perf, so i'm yet again going to use my own bench.

I see, I'll make some time to collect & share stats from it soon. On that note, I've never had any problems with running the suite in the past, and the results have been very helpful (if nothing else, it's nice to have a mid-size test corpus everyone can share). What sorts of issues are you running into? Were you able to get interesting results with -DTEST_SUITE_RUN_BENCHMARKS=0 set?

TLDR: (all measurements done with llvm ToT, the sanitizer never fired.)

  • no sanitization vs. existing check: average +20.75% slowdown
  • existing check vs. check after this patch: average +26.36% slowdown
  • no sanitization vs. this patch: average +52.58% slowdown

I suspect some of this might be recoverable, but i don't know yet.

In D67122#1663619, @vsk wrote:
In D67122#1659721, @vsk wrote:

Still think this looks good. Have you tried running this on the llvm test suite, or some other interesting corpus? Would be curious to see any pre/post patch numbers.

There were 1.5 occurrences in test-suite.

I'd prefer not to try running it over llvm stage-2/3 (i can, but it's gonna be slow..)

Though i guess you were talking about *performance* numbers?

Yes, I'm primarily interested in run-time and compile-time performance (at {-O0 -g, -Os -g}).

Uh, feel free to measure _that_ yourself :D

The number of occurrences of new diagnostics is also interesting. What does the .5 mean?

There were two occurrences - rL371219 and rL371220, and only one of those is new.
(as per @rupprecht it catches something in the original miscompile test, so there's that too)

I'm not good with using test-suite for perf, so i'm yet again going to use my own bench.

I see, I'll make some time to collect & share stats from it soon.

Cool

On that note, I've never had any problems with running the suite in the past,
and the results have been very helpful (if nothing else,
it's nice to have a mid-size test corpus everyone can share).
What sorts of issues are you running into?
Were you able to get interesting results with -DTEST_SUITE_RUN_BENCHMARKS=0 set?

Note that i wasn't looking for compile time stats, let alone at -O0,
there is nothing odd in the diff that could have an impact other than the usual "death by a thousand cuts".

As for benchmarking, it has pretty long run-time,
multiply that by the number of repetitions, and the results are noisy still.

TLDR: (all measurements done with llvm ToT, the sanitizer never fired.)

  • no sanitization vs. existing check: average +20.75% slowdown
  • existing check vs. check after this patch: average +26.36% slowdown
  • no sanitization vs. this patch: average +52.58% slowdown

^ so i provide my own numbers.

I'm chirping away at missed folds, already handled two, two more coming,
so i suspect runtime overhead is already lower and will be lower still.

There's definitely a lot of new findings this creates, but it's hard to say exactly how many root causes there are due to the way test failures are (not) grouped well in the way I'm testing. So far they all seem like true positives, so this would be good to submit. However a few are positive yet benign, like this interesting one (simplified):

void ParseString(char *s) {
  char *next = s;
  for (char *end = s; end; next = end + 1) { // ubsan error computing (nil + 1), although it doesn't matter because the loop terminates when end == nil and next is not read after the loop
    // ...
    end = strchr(next, 'x'); // returns null if not found
    // ...
  }
}

If I had to guesstimate, I'd say 20-100 bugs in a couple billion lines of code, so a lot, but shouldn't be too disruptive to anyone that has these checks enabled globally.

I haven't noticed any timeouts -- which is not to say this isn't a slowdown, but at least it's not egregious.

BTW, here's a minimal + complete repro of the original issue:

$ cat ub.cc
#include <cstdio>
#include <cstdlib>

static void Test(const char *x, int offset) {
  printf("%p + %d => %s\n", x, offset, x + offset ? "true" : "false");
}

int main(int argc, char **argv) {
  if (argc != 3) return 1;

  const char *x = reinterpret_cast<const char *>(atoi(argv[1]));
  int offset = atoi(argv[2]);

  Test(x, offset);

  return 0;
}
$ previous-clang++ -O3 ub.cc && ./a.out 0 1
(nil) + 1 => true
$ next-clang++ -O3 ub.cc && ./a.out 0 1
(nil) + 1 => false
$ patch-D67122-clang++ -O3 -fsanitize=undefined ub.cc && ./a.out 0 1
ubsan: ub.cc:5:42: runtime error: applying non-zero offset 1 to null pointer                                                                                                    
(nil) + 1 => false

Did you run it with the linux kernel? It could be interesting

cc @nickdesaulniers

lebedev.ri edited the summary of this revision. (Show Details)

Rebased.
I've added most (?) of the obviously-missing folds.
This improved situation, although admittedly by not as much as i had hoped.

ping @vsk; can this get going please? live miscompiles aren't fun i suspect :)

In D67122#1659721, @vsk wrote:

Still think this looks good. Have you tried running this on the llvm test suite, or some other interesting corpus? Would be curious to see any pre/post patch numbers.

<...>

TLDR: (all measurements done with llvm ToT, the sanitizer never fired.)

  • no sanitization vs. existing check: average +20.75% slowdown
  • existing check vs. check after this patch: average +26.36% slowdown
  • no sanitization vs. this patch: average +52.58% slowdown

New numbers:


TLDR: (all measurements done with llvm ToT, the sanitizer never fired.)

  • no sanitization vs. existing check: average +21.62% slowdown (+0.87%, noise?)
  • existing check vs. check after this patch: average 22.04% slowdown (-4.32% yay)
  • no sanitization vs. this patch: average 48.42% slowdown (-4.16% yay)

Did you run it with the linux kernel? It could be interesting

cc @nickdesaulniers

It can't possibly matter for them, they treat null pointer as defined.

rsmith added inline comments.Sep 26 2019, 12:28 PM
clang/docs/ReleaseNotes.rst
59

In C, even adding 0 to a null pointer is undefined. Did this change in C17?

64

LLVM -> the LLVM

65

"undefined behavior", like (eg) "code", is generally treated as an uncountable noun, so this should be "If the source contains such undefined behavior, said code [...]" rather than "If the source contains such undefined behavior*s*, said code [...]".

214–248

Reusing this group seems a little surprising, since the new checks don't seem to have anything to do with overflow. Is the general idea that this warning identifies places where pointer artihmetic leaves the complete object (where, for now, we only catch the case where it wraps around the address space or leaves / reaches a hypothetical size-0 object at the null address)?

clang/lib/CodeGen/CGExprScalar.cpp
4634

Remove the Shalls here. They don't add anything.

lebedev.ri marked 2 inline comments as done.Sep 26 2019, 12:47 PM
clang/docs/ReleaseNotes.rst
214–248

As it can be seen in the patch history i initially added this as a new group,
but then merged it back into this group as per @vsk request in D67122#inline-602602 :

Separately, the proposed 'nullptr-and-nonzero-offset' check is interesting only/exactly when the existing 'pointer-overflow' check is interesting, and vice versa. So I don't see the need to make them distinct.

So yes, the idea is that in the retrospect, the pointer-overflow name might be just too specific,
but this is the same UB, so there is no point in fragmenting it.

aaron.ballman added inline comments.Sep 26 2019, 12:53 PM
clang/docs/ReleaseNotes.rst
59

I don't see what words in the C standard make this UB. If it's UB-by-omission, I think it's unintentional. I mean, this language allows &*some_null_pointer without UB, so I would be really surprised if some_null_ptr + 0 was UB. Do you have a source in the C standard for the UB?

rsmith added inline comments.Sep 26 2019, 2:08 PM
clang/docs/ReleaseNotes.rst
59

C11 6.5.6/8: "If both the pointer operand and the result point to elements of the same array object, or one past the last element of the array object, the evaluation shall not produce an overflow; otherwise, the behavior is undefined."

Pointer arithmetic in C11 is only defined if the pointer points to an array object (where per /7, a pointer to a non-array object is treated as a pointer to an array of length 1). So arithmetic on null pointers is undefined, even if you add zero. This rule was explicitly changed in C++ to permit adding zero to a null pointer. Similar analysis applies to taking the difference of two pointers, where C++ explicitly says null_pointer - null_pointer is zero and C11 says both pointers need to point to the same array object or you get undefined behavior (C11 6.5.6/9: "When two pointers are subtracted, both shall point to elements of the same array object, or one past the last element of the array object").

In contrast, C explicitly calls out the &*null_pointer case (C11 6.5.3.2/3: " If the operand is the result of a unary * operator, neither that operator nor the & operator is evaluated and the result is as if both were omitted"). The corresponding case is undefined in C++, but that's likely to be addressed by a defect report resolution (see http://wg21.link/cwg232).

I don't think these two things are all that closely related, though. The C model, as I understand it, is that the null pointer is not a pointer to any object, whereas the C++ model is as if there is an object of type T[0] at the null address for every object type T, and a null pointer to object type points to (== past the end of) that object. And the &* thing is just a very specific, weird C special case, and only applies to certain very specific syntactic forms (but that's OK in C, because there are only a very small number of syntactic forms for lvalues).

clang/test/CodeGen/catch-nullptr-and-nonzero-offset-in-offsetof-idiom.c
14 ↗(On Diff #218720)

CHECK-LABEL: define i64 @{{.*}}get_offset_of_y{{.*}}( ?

(Even if you don't add the function names, please do add the -LABEL.)

lebedev.ri marked 6 inline comments as done.

Patch updated - mainly wording changes only.

It isn't clear that for C the rule is actually different from C++,
if it is it does not make much sense and is irrelevant for LLVM IR - there is no such UB there,
so i'we deferred wasting hours upon hours on test updates until there's definitive answer.

lebedev.ri updated this revision to Diff 222825.Oct 2 2019, 6:58 AM
lebedev.ri marked 3 inline comments as done.
lebedev.ri edited the summary of this revision. (Show Details)

Ping.
After talking with @aaron.ballman, revised the check to also handle the C semantics ("ptr+0 is UB").

If it was the other way around (UB in C++ as opposed to in C only)
i'd also look into properly lowering that info into IR,
but since this is C-only i guess i won't do that.

Ping.
After talking with @aaron.ballman, revised the check to also handle the C semantics ("ptr+0 is UB").

And that resulted in one more occurrence in test-suite - rL373486.

This comment was removed by xbolva00.

Ping.
Friendly remainder that the unsanitized UB is still being miscompiled.

rsmith added a comment.Oct 8 2019, 5:06 PM

Looks fine to me with some doc improvements.

clang/docs/ReleaseNotes.rst
60–62

The parenthetical here makes this awkward to read. Also, I don't think we need to say which LLVM revision this happened in. How about:

"In both C and C++ (C17 6.5.6p8, C++ [expr.add]), pointer arithmetic is only permitted within arrays. In particular, the behavior of a program is not defined if it adds a non-zero offset (or in C, any offset) to a null pointer, or that forms a null pointer by subtracting an integer from a non-null pointer, and the LLVM optimizer now uses those guarantees for transformations. This may lead to unintended behavior in code that performs these operations. The Undefined Behavior Sanitizer -fsanitize=pointer-overflow check has been extended to detect these cases, so that code relying on them can be detected and fixed."

214–248

Add "The" to the start of this bullet.

215–216

"[...] where a non-zero offset is applied to a null pointer, or the result of applying the offset is a null pointer."

217

I don't think we really need to say this is undefined behavior here.

clang/docs/UndefinedBehaviorSanitizer.rst
136

Simplify this a bit: "Performing pointer arithmetic which overflows, or where either the old or new pointer value is a null pointer (or in C, when they both are)."

clang/lib/CodeGen/CGExprScalar.cpp
4632

If we want to split out the "constant folded" case to avoid issuing too many sanitizer traps on bogus but common patterns, we should have another sanitizer group to re-enable those diagnostics for the constant-folded cases. (I'm fine with not doing that in this patch, though.)

lebedev.ri updated this revision to Diff 224007.Oct 9 2019, 3:42 AM
lebedev.ri marked 5 inline comments as done.

@rsmith thank you for the review!

Rebased, addressed documentation nits.

Anything else here? If not, care to stamp? :)

lebedev.ri added inline comments.Oct 9 2019, 3:50 AM
clang/lib/CodeGen/CGExprScalar.cpp
4632

I'm not sure about this point, i think i'm gonna leave this as-is for now..

rsmith accepted this revision.Oct 9 2019, 3:56 PM
rsmith added inline comments.
clang/docs/ReleaseNotes.rst
62

Oops, "that" -> "if it" here.

215

Delete one of these two "where"s.

This revision is now accepted and ready to land.Oct 9 2019, 3:56 PM
lebedev.ri updated this revision to Diff 224195.Oct 9 2019, 4:06 PM
lebedev.ri marked 2 inline comments as done.

@rsmith thank you for the review!

Will be attempting to land this tomorrow.

Just wanna say huge +1 for this patch. Thanks!

This revision was automatically updated to reflect the committed changes.
russell.gallop added a subscriber: russell.gallop.EditedOct 10 2019, 4:06 AM

This is failing the sanitizer lint check:
http://lab.llvm.org:8011/builders/sanitizer-x86_64-linux/builds/23819/steps/64-bit%20check-sanitizer/logs/stdio

<path...>/compiler-rt/lib/ubsan/ubsan_checks.inc:22: Lines should be <= 80 characters long [whitespace/line_length] [2]
<path...>/compiler-rt/lib/ubsan/ubsan_checks.inc:23: Lines should be <= 80 characters long [whitespace/line_length] [2]

Please could you take a look?

This is failing the sanitizer lint check:
http://lab.llvm.org:8011/builders/sanitizer-x86_64-linux/builds/23819/steps/64-bit%20check-sanitizer/logs/stdio

<path...>/compiler-rt/lib/ubsan/ubsan_checks.inc:22: Lines should be <= 80 characters long [whitespace/line_length] [2]
<path...>/compiler-rt/lib/ubsan/ubsan_checks.inc:23: Lines should be <= 80 characters long [whitespace/line_length] [2]

Please could you take a look?

Hm, i didn't see *that* failure, thanks for relaying the message.
Should be good now, or not..

Not unexpectedly, this broke sanitizer-x86_64-linux-bootstrap-ubsan.
I'm going to attempt to address uncovered issues

http://lab.llvm.org:8011/builders/sanitizer-x86_64-linux-bootstrap-ubsan/builds/15329/steps/annotate/logs/stdio appears to contain "only" 3 distinct issues.
I've pushed those 3 fixes, but maybe that is not enough, we'll see.

http://lab.llvm.org:8011/builders/sanitizer-x86_64-linux-bootstrap-ubsan/builds/15329/steps/annotate/logs/stdio appears to contain "only" 3 distinct issues.
I've pushed those 3 fixes, but maybe that is not enough, we'll see.

And we're green. Thanks for everyone's patience and lack of reverts :)
As per that bot(!) there were "only" 3 places in LLVM that had that UB.

Herald added a project: Restricted Project. · View Herald TranscriptMay 26 2022, 11:20 AM