pascal_cuoq

Yes, the first two examples in the article weren't obviously enough undefined for the authors of CIL who wrote the list, apparently.

This list contains several invalid items mixed with the good ones. It starts:

     Why does the following code return 0 for most values of x? (This should be easy.)

      int x;
      return x == (1 && x);

“It is UB” also applies to “(1 - sizeof(int)) >> 32”, the next question, on ILP32 architectures that were still prevalent when this page was written (shifting an integer type of width 32 by 32), regardless of the discussion the authors want to have about the type of sizeof(t).

“Functions and function pointers are implicitly converted to each other” is one way to describe what the C standard actually says, but that makes it look more complicated than it is. In reality, functions decay to pointers to function in the same way that arrays decay to pointers-to-first-element, and if you are familiar with the latter, it's a good way to understand the former. Only function pointers can be applied. When you write “f(x)”, f first decays to pointer to function, and then is applied. The reason you don't need to dereference a pointer-to-function p when you apply it as “p(x)” is NOT that p will be converted implicitly to a function, but that function application expects a pointer to function.

The first example in 16.3 is also Undefined Behavior, regardless of the target architecture, because the type of “3” is always “int”, so it's a poor illustration of the VC compiler bug they are referring to.

The sentence you quote is near to the words:

“[The C++ standardization committee] WG21 has recently adapted the changes promoted in their document p12363. Generally, C++ goes much beyond what is presented here:”

I would be extremely surprised if the proposal to make signed arithmetic overflow defined behavior in C made it into C23. The window is narrowing and this would be a very big change to the language. Making it official that 2's complement is the only representation for signed integers is already a large change.

Later in the decade, maybe.

You need to look at the disassembly of the generated binary to make sense of this sort of performance variation (paying attention to line cache boundaries for code and data), and even so, it is highly non-trivial. The performance counters found in modern processors sometimes help (https://en.wikipedia.org/wiki/Hardware_performance_counter ).

https://www.agner.org/optimize/microarchitecture.pdf contains the sort of information you need to have absorbed before you even start investigating. In most cases, it's not worth acquiring the expertise for 5% one way or the other in micro-benchmarks. If you care about these 5%, you shouldn't be programming in C in the first place.

And then there is this anecdote:

My job is to make tools to detect subtle undefined behaviors in C programs. I once had the opportunity to report a signed arithmetic overflow in a library that its authors considered, rightly or wrongly, to be performance-critical. My suggestion was:

… this is not one of the subtle undefined behaviors that we are the only ones to detect, UBSan would also have told you that the library was doing something wrong with “x + y” where x and y are ints. The good news is that you can write “(int)((unsigned)x + y)”, this is defined and it behaves exactly like you expected “x + y” to behave (but had no right to).

And the answer was “Ah, no, sorry, we can't apply this change, I ran the benchmarks and the library was 2% slower with it. It's a no, I'm afraid”.

The thing is, I am pretty sure that any modern optimizing C compiler (the interlocutor was using Clang) has been generating the exact same binary code for the two constructs for years (unless it applies an optimization that relies on the addition not overflowing in the “x + y” case, but then the authors would have noticed). I would bet a house that the binary that was 2% slower in benchmarks was byte-identical to the reference one.

UBSan does detect and report misaligned pointer accesses in the latest versions of GCC and Clang:

https://gcc.godbolt.org/z/xpSbXL

I have seen it said in another thread that UBSan detects this.

If you aren't already using all the sanitizers that come with your {CLang, GCC} compiler, you should! They are great!

UBSan detects everything that can be detected without metadata. It would be its job to find this, since this is a simple mask to apply and test at each pointer access.

UBSan cannot detect if memory is initialized or if a pointer is valid, because these questions cannot be answered locally, looking only at the instruction doing the access. You need metadata for this. The sanitizers that maintain the metadata to answer these questions are respectively MSan and ASan. Their heavy instrumentations are incompatible, so you can only use one at a time.

Please explain to me why you think it is.

The clause says:

“If the value being stored in an object is read from another object that overlaps in any way the storage of the first object, then the overlap shall be exact and the two objects shall have qualified or unqualified versions of a compatible type; otherwise, the behavior is undefined.”

Under “6.5.16.1 Simple assignment”, so this describes a rule about assignment.

Which assignment in the program are you claiming stores in an object a value read from another object that overlaps in any way the storage of the first object?

So the clause about assignment? Thanks, that was helpful.

1 is not an object, but even if it was one, it would not be an object that overlaps with “* p”.

You are interpreting the C standard as if it were a philosophy text. It contains a rule that says that in very precise circumstances (for an assignment from one to the other) objects must not partially overlap, and you are claiming that it means that “two pointers to the same basic type cannot overlap in memory”. The clause does not say that, sorry. The clause applies to the objects that are on one side and the other of an assignment.

I said the standard expressly allowed the optimization in the linked article.

I hope that the article makes it clear that the standard expressly allows the optimization. Specific, explicit rules, cited in the article, about pointer alignment, allow the optimization.

For this reason, I, “violently” as you say, disagree with the sentence “The complaint isn't about alignment at all, it's that the optimizer assumes that two pointers to the same basic type cannot overlap in memory”. This sentence gets it all wrong. It is about alignment; it is not about “pointers to basic types”, whatever that is, not being allowed to overlap in memory; they are allowed to overlap for large enough “basic types” because it is about alignment, not overlap:

https://gcc.godbolt.org/z/ZAMkeH

You could argue that GCC 9.3 only missed the optimization in the example in this Compiler Explorer link for some other reason and that absence of optimization doesn't mean that p and q cannot overlap. This would be correct, this aspect is one of the difficulties in studying the rules that these compilers implement. However, what I am saying is that if you reported this missed optimization to GCC developers, they would tell you that GCC can't optimize the function f because p and q can overlap. There is no clause in the C standard that prevent them to (apart from strict aliasing rules, but I used the option to tell the compiler I didn't want it to take advantage of these ones).

(Please do not bother them with this, or if you do, at least leave me out of it; I have nothing better to do than to write this because it's the week-end but they have better things to do.)

This line of J.2 only refers to the already cited 6.5.16.1.

You keep quoting this clause as if it applied to any of the assignments in the program being discussed.

It doesn't.

That clause says that in an assignment of the form “lvalue1 = lvalue2;”, there must only be exact overlap or no overlap between lvalue1 and lvalue2. This does not apply to assignments of the form “lvalue = 1;” or “lvalue = 2;” which are the interesting assignments in the program being discussed.

Objects are not “basic types” for the original sentence that claimed that “basic types cannot overlap in memory”. Objects overlap in memory all the time.

You repeatedly (in this thread, and on your blog) express that you don't really understand "strict" (ISO standard) aliasing rules, and that seems to be the case.

If you say so. I'm not the one who thinks that “* p” and “1” overlap.

6.5.16.1 is the “rule that only apply to “lvalue = lvalue;” assignments and is not relevant here”

It does not apply to “lvalue = 1;” or to “lvalue = 2;”, which are the two relevant assignments in the example in the article.

For context, I think I made it clear in the article that the program being discussed is UB, and therefore that the compiler is not to blame. But since I wrote this article, I have had people telling me “The complaint isn't about alignment at all, it's that the optimizer assumes that two pointers to the same basic type cannot overlap in memory”.

My reply to this specific sentence is:

No. You are wrong. There are no words in the standard that say that “basic types cannot overlap in memory”. There is not even a notion of “basic type”. There are clauses about pointer alignment, that are explicitly cited in the article, and there are clauses about strict aliasing, that are shown in the article not to be the reason for GCC optimizing the program by using -fno-strict-aliasing. There are no rules about “basic types not overlapping” in the C standard. You only think there are. Or please cite them. (6.5.16.1 is a rule about assignment, it only applies for the code pattern lvalue1 = lvalue2;)

Could you clarify which clause of the C standard you are referring to when you say “due to aliasing, not due to alignment”?

I make sense of the C standard for a living (this is literally my day job) and I do not see what clause of the C standard you are referring to. It would be very useful to me to know which clause you are referring to, and I would be eternally thankful.

I have heard this reaction to this article a lot, but sorry, there is nothing in the C standard that says that objects should not overlap, except a rule that only apply to “lvalue = lvalue;” assignments and is not relevant here.

Plus on a some 32-bit ISA, a long long and a double only need to be aligned to 32-bit boundaries, so I note that in the made-up C rules that you are referring to, “basic type” is not very well defined.

I believe this behavior is actually specified in the standard, actually,

in the same section that defines the aliasing rules.

The strict aliasing rules are here: https://port70.net/~nsz/c/c11/n1570.html#6.5p7

Go ahead and point to the rule that says that “basic types” cannot overlap with themselves.

Author here!

I am not saying or thinking that there is a problem with GCC. I do think that GCC and Clang would be more useful with an option to make them not assume that every pointer is aligned if the target architecture does not impose this, but that's not the same thing as saying there is something wrong with GCC.

The message of the post, rather than “something is wrong with GCC”, is, “Beware. You might think that this is okay to do in your C programs, but it is not and here is why.”

Also before I post something like this, I need a confirmation that the behavior is intended and not accidental. It has happened to me before that I was about to document that GCC had an agressive behavior with respect to a kind of optimization (while remaining arguably in line with the intent of the standard, even if the word of the standard was in this case ambiguous enough to be interpreted any which way), and my co-author and I had to use a “missed optimization” ticket on GCC's bugzilla in order to have them confirm that GCC was doing the thing in question on purpose. GCC's developers, seeing the bug report, changed the behavior to remove the optimization entirely instead: https://gcc.gnu.org/ml/gcc/2016-11/msg00111.html

Coming back to the example at hand, if I had phrased the ticket as “GCC shouldn't optimize this”, it would have been closed instantly as “well it's UB”. I hoped for a more interesting search for a trade-off that would satisfy everyone, from people who just want legacy C code to keep working with new compilers to people who want programs to run as fast as possible if I phrased it this way.

(And yes, you have to ask in the bugzilla if you need some sort of official answer for this kind of thing. If you ask on a mailing list, you'll get a “no that was UB from the start” answer from someone you have never heard of who is in fact a power user who subscribed to the mailing list, and whose opinion, while useful, should not be assumed to be that of the compiler developers.)

That may be the case in C++, but in C infinite loops are allowed as long as the controlling condition is a constant expression (making it clear that the developper intends an infinite loop). These infinite loops without side-effects are even useful from time to time in embedded software, so it was natural for the committee to allow them: https://port70.net/~nsz/c/c11/n1570.html#6.8.5p6

And you now have all the details of the Clang bug, by the way: write an infinite loop without side-effects in a C function, then call the function from another C function, without using its result.

The problem in practice is that you do not write “hello” and “world” to the destination buffer. You write data that is computed more or less directly from user inputs. Often a malicious user.

So the user only needs to find a way to make the data longer than the developer expected. This may be very simple: the developer may have written a screensaver to accept 20 characters for a password, because who has a longer password than this? Everyone knows that only the first 8 characters matter anyway. (This may have been literally true a long time ago, I think, although it's terrible design. Anyway only 8 characters of hash were stored, so in a sense characters after the first 8 did not buy you as much security as the first 8, even if it was not literally true.)

And this is how there were screensavers that, when you input ~500 characters into the password field, would simply crash and leave the applications they were hiding visible and ready for user input. This is an actual security bug that has happened in actual Unix screensavers. The screensavers were written in C.

And long story short, we have been having the exact same problem approximately once a week for the last 25 years. Many people agree that it is urgent to finally fix this, especially as the consequences are getting worse and worse as computers are more connected.

One solution that some favor is functions that make it easier not to overflow buffers because you tell them the size of the buffer instead of trying to guess in advance how much is enough for all possible data that may be written in the buffer. This is the thing being discussed in this thread. The function sprintf is not a contender in this discussion. The function snprintf could be, if used wisely, but it is a bit unwieldy and the OP's proposal has a specific advantage: you compute the end pointer only once, because this is the invariant.

Oh, that was your question. In this case, the reason why &a + 1 == &b is unspecified is that:

- it's generally false—there is no reason for b to be just after a in memory, so these two addresses compare different.

- it is sometimes true: when addresses are implemented as integers, and compilers use exactly sizeof(T) bytes to represent an object of type T, and do not waste precious integers by leaving gaps between objects, and == between pointers is implemented as the assembly instruction that compares integers, sometimes that instruction produces true for &a + 1 == &b, because b was placed just after a in memory.

In short, &a + 1 == &b was made unspecified so that compilers could implement pointer == by the integer equality instruction, and could place objects in memory without having to leave gaps between them. Anything more specific (such as “&a + 1 == &b is always false”) would have forced compilers to take additional measures against providing the wrong answer.

If you wrote down your proposal, which the C committee member Robert Seacord is encouraging you to do here: https://news.ycombinator.com/item?id=22870210 , you would have to think carefully about functions that are pure according to your definition (free from side effects and only uses its inputs) but do not terminate for some inputs.

There is at least one incorrect optimization present in Clang because of this (function that has no side-effects detected as pure, and call to that function omitted from a caller on this basis, when in fact the function may not terminate).

Thanks Dan, I missed this question in the heat of the moment.

I still want to write at least one sequel to that post, on the theme “Alright, can we make a Friendly C Compiler by disabling the annoying optimizations, then?”.

Obviously the people who want a Friendly C Compiler do not want to disable all optimizations. This would be easy to do, but these users do not want the stupid 1+2+16 expressions in their C programs, generated through macro-expansion, to be compiled to two additions with each intermediate result making a round-trip through memory.

So the question is: can we get a Friendly C Compiler by enabling only the Friendly optimizations in an unfriendly compiler?

And for the answer to that, I had to write an entire other blog post as preparation, to show that there are some assumptions an optimizing compiler can do:

- that may be used in one or several optimizations, but the compiler authors did not really keep track of where they were used,

- that cannot be disabled and that the compiler maintainers will not consider having an option to disable,

- and that are definitely unfriendly.

Here is the URL of the blog post that I had to write in preparation for the upcoming blog post about getting ourselves a Friendly C Compiler: https://trust-in-soft.com/blog/2020/04/06/gcc-always-assumes... . I recommend you take a look, I think it is interesting in itself.

You will have guessed that I'm not optimistic about the approach. We can try to maintain a list of friendly optimizations for ourselves, though, even if the compiler developers are not helping. This might still be less work that maintaining a C compiler.

3. would have to be a new mechanism for variadic functions, that would have to be distinguished in header files from the old mechanism with which it is incompatible. So this proposal would imply some new keyword or syntax. I am not in the committee, but I don't think this is going to happen. The improvement is way too incremental to force a new syntax.

(The committee is fine with incremental improvements, but new syntax need to have strong motivation behind it, much stronger than this.)

For what it's worth, I personally like this approach, because there are some cases in which it requires less arithmetic in order to be used correctly. And it lends itself better to some forms of static analysis, for similar reasons, in the following sense:

There is the problem of detecting that the function overflows despite being a “safe” function. And there is the problem of precisely predicting what happens after the call, because there might be an undefined behavior in that part of the execution. When writing to, say, a member of a struct, you pass the address of the next member and the analyzer can safely assume that that member and the following ones are not modified. With a function that receives a length, the analyzer has to detect that if the pointer passed points 5 bytes before the end of the destination, the accompanying size it 5, if the pointer points 4 bytes before the end the accompanying size is 4, etc.

This is a much more difficult problem, and as soon as the analyzer fails to capture this information, it appears that the safe function a) might not be called safely and b) might overwrite the following members of the struct.

a) is a false positive, and b) generally implies tons of false positives in the remainder of the analysis.

(In this discussion I assume that you want to allow a call to a memory function to access several members of a struct. You can also choose to forbid this, but then you run into a different problem, which is that C programs do this on purpose more often than you'd think.)

Unfortunately I am out of useful information:

https://news.ycombinator.com/item?id=22868999

I hope someone will provide the next link.

If I remember correctly, Chandler was the one writing down the draft for LLVM developers to comment on LLVM-side. Unfortunately, if you Google his name and the relevant keywords, the results are full of his work on speculative load hardening.

Someone who read the LLVM mailing-list attentively should have seen it and may have a link.

One concrete reason why “unspecified” means “anything and not always the same thing” is to enable the maximum of optimizations.

Write a function c that compares pointers in a compilation unit, and in another compilation using, define:

    int a, b;
    X1 = (&a == &b + 1);
    X2 = c(&a, &b + 1);

  - be false
  - or invoke undefined behavior
  - or be unspecified

Here is an example I have at hand that shows that when you are using an optimizing compiler, there is no such thing as “just pointers to addresses in memory”. There are plenty more examples, but I do not have the other ones at hand.

https://gcc.godbolt.org/z/Budx3n

I think this is plenty ok. For one thing, If a struct as a member of type T, it's ok to access it through a pointer to T (and also the address of the struct is guaranteed to be identical to the address of the first member). For another, you are using dynamically allocated memory, so the only thing that matters is the type of the pointer when the access is finally made. It doesn't matter that it was a Foo* before, if what you dereference is an int*.

This is different from pretending that the address of a struct s { int a; double b; } is the address of a struct t { int a; long long c; } and accessing it through a pointer to that. If you do that, C compilers will (given the opportunity) assume that the write-through-a-pointer-to-struct-t does not modify any object of type “struct s”. This is what the example st1 in the article illustrates.

The latter is what I suspect plenty of socket implementations still do (because there are several types of sockets, represented by different struct types with a common prefix). It is possible to revise them carefully so that they do not break the rules, but I doubt this work has been done.

The only thing that is not defined is comparing a pointer one-past-the-end to a pointer to the very beginning of a toplevel object. Apart from this rule, pointers of course do not need to be derived from the same object in order to be compared with == and !=.

&a + 1 == &b is unspecified: it may produce 0 or 1, and it may not produce the same result if you evaluate it several times.

Similarly, if both the char pointers p and q were obtained with malloc(10), after they have been tested for NULL, all these operations are valid:

  p == q (false)
  p + 1 == q (false)
  p + 1 == q + 1 (false)
  p + 10 == q + 1 (false)

I have no idea what led that person to (apparently) write that &a==&b is undefined. This is plain wrong. I do not see any ambiguity in the relevant clause (https://port70.net/~nsz/c/c11/n1570.html#6.5.9p6 ). Yes, the standard is in English and natural languages are ambiguous, but you might as well claim that a+b is undefined because the standard does not define what the word “sum” means (https://port70.net/~nsz/c/c11/n1570.html#6.5.6p5 ).

The C standard also allows to use memcpy to do type punning:

    If a value is copied into an object having no declared type using memcpy or memmove,
    or is copied as an array of character type, then the effective type of the modified
    object for that access and for subsequent accesses that do not modify the value is
    the effective type of the object from which the value is copied, if it has one

https://port70.net/~nsz/c/c11/n1570.html#6.5p6

This example is clearly UB.

You could argue that it suddenly becomes less UB if you take the address of x:

  unsigned int x;
  &x;
  x -= x;

So the short answer is that, for all intent and purposes, you should consider use of uninitialized variables as UB, because C compilers already do. (There exists somewhere a document clarifying what C compilers can and cannot do with indeterminate values. A search for “wobbly values” might turn it up. Anyway, you do not want to have wobbly values in your C programs any more than you want it to have undefined behavior.)