Skip to content

Undefined Behavior Consequences Contest Winners

The contest that I posted the other day received some very nice entries. I decided to pick multiple winners since the best entries illustrate consequences of several kinds of undefined behavior.

First, here’s the runner up, submitted by Octoploid:

int main (void) {
  int x = 1;
  while (x) x <<= 1;
  return x;
}

This program is undefined by C99, where signed left shifts must not push a 1 bit into or past the sign bit. Recent GCC versions such as r189449 for x86-64 on Linux compile this program into an infinite loop at -O2 and higher. This entry is great because in general, compiler developers have been very reluctant to start enforcing the very strict rules for signed left shift in C99. On the other hand, GCC still performs this optimization when asked to compile in C89 mode, where I don’t think the behavior is undefined. Based on that observation, I filed a GCC bug report. One of the main GCC developers, Joseph Myers, replied with this:

Shifts in GCC are supposed to be defined as long as the shift amount is in range, independent of the LHS, so it should not be folding like that. (Although we document in implement-c.texi that this is subject to change for signed left shift, I don’t think changing it would be a particularly good idea.)

I think it is great to see compiler developers taking this kind of a stand against exploiting certain undefined behaviors. Anyway, although the matter has not yet been completely resolved, and the optimization is perfectly valid in C99, it seems that the developers will back out this transformation. So, while I find this example to be very interesting, it does not seem like a contest winner.

Winner #1

Amonakov submitted this code:

enum {N = 32};
int a[N], pfx[N];
void prefix_sum (void)
{
  int i, accum;
  for (i = 0, accum = a[0]; i < N; i++, accum += a[i])
    pfx[i] = accum;
}

This function forms a bit of an argument against the very terse style of for-loop afforded by C which (in my opinion) makes the undefined behavior harder to see than it might otherwise have been. The undefined operation here is reading a[32]. Recent versions of GCC, apparently as a consequence, decide that the loop exit test can be removed, giving an infinite loop that triggers a segfault when i becomes large enough.

Winner #2

Nick Lewycky submitted this code:

#include <stdio.h>
#include <stdlib.h>

int main() {
  int *p = (int*)malloc(sizeof(int));
  int *q = (int*)realloc(p, sizeof(int));
  *p = 1;
  *q = 2;
  if (p == q)
    printf("%d %d\n", *p, *q);
}

Using a recent version of Clang (r160635 for x86-64 on Linux):

$ clang -O realloc.c ; ./a.out 
1 2

To see the undefined behavior, you need to read the fine print in the C99 standard, which says:

The realloc function deallocates the old object pointed to by ptr and returns a pointer to a new object that has the size specified by size.

In other words, it is an error to use a pointer after it has been passed as an argument to realloc. This particular bit of language does not appear in the ANSI C standard and the situation there is more ambiguous. However, reading between the lines in A.6.2, I believe we can infer that this code was intended to be undefined in C89 as well.

The man pages for realloc() that I looked at do not mention or imply this caveat. If a major compiler is going to exploit this behavior, the documentation must be updated.

Conclusion

I chose these winners because in each case there is an element of surprise. In other words, I would not have guessed that the compiler would exploit these particular undefined behaviors, even after I understood the program or program fragment completely. An entry submitted by Pascal Cuoq, which is otherwise very interesting, fails this test—I would have expected a modern C compiler to exploit those undefined behaviors.

UPDATE: See Pascal’s response here.

{ 23 } Comments

  1. Jesse Ruderman | July 23, 2012 at 4:22 pm | Permalink

    I’d put the “*p = 1;” inside the “if (p == q)” block, so it’s less obvious that it’s undefined behavior. (And Clang still performs the unexpected optimization.)

    #include
    #include

    int main() {
    int *p = (int*)malloc(sizeof(int));
    if (p == NULL) { return 3; }
    int *q = (int*)realloc(p, sizeof(int));
    if (q == NULL) { return 3; }
    *q = 2;
    if (p == q) {
    *p = 1;
    printf(“%d %d\n”, *p, *q);
    }
    }

    clang -Weverything -O r.c && ./a.out
    1 2

  2. Jesse Ruderman | July 23, 2012 at 5:37 pm | Permalink

    I find it disturbing that Clang doesn’t warn: “Every execution of your program is undefined”.

  3. Mike McFadden | July 23, 2012 at 10:49 pm | Permalink

    If anyone is curious, the for-loop in Winner #1 uses the comma operator, which can be used to execute multiple statements sequentially in places where only one statement is accepted:
    return i++, 0; // increments i and returns 0

    http://en.wikipedia.org/wiki/Comma_operator

  4. Kevin | July 24, 2012 at 12:19 am | Permalink

    #2 is a straightforward result of this sentence in the Linux realloc man page:

    >If the area pointed to was moved, a free(ptr) is done.

    Either p was freed or it wasn’t. The former is undefined (due to all the *p’s floating around) so the compiler assumed the latter. Thus p==q since nothing was moved, so the if was optimized away.

    (cross-post from Reddit)

  5. regehr | July 24, 2012 at 12:47 am | Permalink

    Hi Kevin, the MacOS man for realloc() says nothing about freeing and Linux only mentions the case where the pointer is moved—not the case here.

    The point of Nick’s code is to show that the compiler treats the pointer as being freed even when the allocated space is not moved.

  6. Nick Lewycky | July 24, 2012 at 12:56 am | Permalink

    Kevin, you’ve got the right line in the man page, however the consequence you’ve described is wrong. The p == q check is not optimized away, instead the compiler treats ‘p’ and ‘q’ as legitimately pointing to different memory and then folding the loads against the stores. Here’s the machine code on x86-64 linux, showing the comparison in tact:

    [...]
    callq malloc
    movq %rax, %rbx
    movq %rbx, %rdi
    movl $4, %esi
    callq realloc
    movl $1, (%rbx) ; *p = 1
    movl $2, (%rax) ; *q = 2
    cmpq %rax, %rbx ; p == q
    [...]

    and then the printf with the constant values after load folding:

    # BB#1: # %if.then
    movl $.L.str, %edi
    movl $1, %esi
    movl $2, %edx
    xorb %al, %al
    callq printf

  7. Arthur | July 24, 2012 at 1:30 am | Permalink

    @4,5,6: John, you really need to stop posting Nick’s example without at least two paragraphs of explanatory English text. 99% of the people who read these blog posts don’t understand Nick’s example, and 10% of them feel the need to comment about it, and it’s really annoying to the small number of us who read the big thread from last time you posted it.

    @Kevin: You’re not alone. Even I looked at that code the first time and said, “Well, what’s surprising about that?” You have to actually type it in and run it before the interesting feature becomes apparent. (And you must type it by hand! Cutting and pasting is not allowed!)

  8. Kevin | July 24, 2012 at 1:50 am | Permalink

    @Nick: Isn’t my interpretation also perfectly legal for the compiler to do, given the ambiguity in the man page? I was just commenting on how it’s behaving, not partially compiling anything!

  9. loic42 | July 24, 2012 at 4:05 am | Permalink

    Just to clarify what happen with clang.
    Clang simply declare realoc like this :
    declare noalias i8* @realloc(i8* nocapture, i64) nounwind

    The return value is declared noalias, so the alias analysis pass considers that p and q point to different location, and therefore it can use constant propagation.

    Note that this behaviour can be disabled by using : -fno-builtin in which case realloc is declared without the noalias.

  10. Richard Zetterberg | July 24, 2012 at 6:21 am | Permalink

    I am pretty new to C, so I have some questions. #2 seems really obvious to me, just as obvious as:

    int *p = malloc(sizeof(int));
    free(p);
    *p = 1;
    printf(“%d”, *p);

    And all documentation I’ve seen of realloc states that the old object will be freed, even man. What am I missing here?

  11. a | July 24, 2012 at 7:06 am | Permalink

    when is a[32] read? i don’t get it…

  12. Terry A. Davis | July 24, 2012 at 7:38 am | Permalink

    I just changed the language. The language is by definition what my compiler does.

    God says…
    C:\Text\BIBLE.TXT

    on the earth; and what will I, if it be
    already kindled? 12:50 But I have a baptism to be baptized with; and
    how am I straitened till it be accomplished! 12:51 Suppose ye that I
    am come to give peace on earth? I tell you, Nay; but rather division:
    12:52 For from henceforth there shall be five in one house divided,
    three against two, and two against three.

    12:53 The father shall be divided against the son, and the son against
    the father; the mother against the daughter, and the daughter against

  13. regehr | July 24, 2012 at 8:16 am | Permalink

    Terry, I’m not sure I understand the semantics. What happens when a house or father is divided against zero? Is the Bible strongly typed?

  14. regehr | July 24, 2012 at 9:34 am | Permalink

    Hi Arthur, you’re right that I could probably have cut down on the confusion by including more explanation. On the other hand, this topic is tricky enough that a bit of mystery is OK, I think. People need to move themselves towards enlightenment, it cannot be done for them. For additional examples of this phenomenon see the Reddit thread:

    http://www.reddit.com/r/programming/comments/x1ql4/undefined_behavior_in_c_contest_winners/

  15. loic42 | July 24, 2012 at 9:37 am | Permalink

    @ Richard Zetterberg
    It’s not the fact that there is a undef behavior which is interesting but the result.
    Your code will probably work perfectly and print 1 even if the behavior is undefined.
    But #2 produces a very interesting behavior, because two pointers that both point to the same valid memory location gives a different value once dereferenced. Which is valid regarding to the C standard because p point to a deallocated object even if it actually points to a valid memory location.

  16. regehr | July 24, 2012 at 10:11 am | Permalink

    Hi Jesse, you’re right. I played around a little with variations of Nick’s program but didn’t hit upon yours.

  17. Richard Zetterberg | July 24, 2012 at 10:17 am | Permalink

    @loic42 Thank you very much for clarifying :)

  18. Arthur | July 25, 2012 at 2:07 pm | Permalink

    @14 (John): Well, you know I don’t object to puzzles. :) But I think in this case the “puzzle” too easily admits of a misreading that makes people *think* the solution is trivial and/or stupid. Sometimes they’ll still be meta-puzzled, as in Richard #10’s case: “This puzzle is trivial. Why are some of you acting like it’s interesting?” But that’s different from “This puzzle is interesting. What’s the solution?”

    On the Internet, the null hypothesis is always — and rightly — that if something looks stupid or trivial at first glance, it probably *is* stupid or trivial. You have to actively do something to falsify the null hypothesis, or most people (myself included!) aren’t going to bother looking for alternative hypotheses.

    Your “UBCC” is sort of like the Underhanded C Contest, in that the goal is to write innocent-looking code that actually misbehaves… but a reader of the UCC tries to figure out how the code leads to a *particular* misbehavior, whereas the whole point of your UBCC was that one dubious bit is enough to make the program do *anything*, so once the reader has found what looks like the dubious bit, it means they’ve won and can stop thinking. ;)

  19. Kristina | July 25, 2012 at 4:35 pm | Permalink

    So, the important question is: what’s the prize they won?

  20. regehr | July 25, 2012 at 5:30 pm | Permalink

    Hi Kristina, I sent them each a $25 gift certificate from Amazon. This seems kind of impersonal. However, for an earlier blog contest I sent the winner a caramel chocolate apple from a local candy store that I love but the Fedexing ended up being like 2x the cost of the apple, so that didn’t really work out!

  21. regehr | July 25, 2012 at 10:49 pm | Permalink

    Hi Arthur, too right about the Internet null hypothesis. Nice way of putting it.

    I was actually thinking about trying to revive the underhanded C contest, which I loved, but it sounds pretty difficult.

  22. Pascal Cuoq | July 26, 2012 at 3:50 am | Permalink

    I am also interested in the underhanded C contest, whose results are more valuable to me professionally than that of the IOCCC.

    John, what part of a UCCC revival sounds difficult to you? How about starting with a simple blog challenge just like the previous one? I can help with the judging (but if you don’t need me I might participate too).

  23. regehr | July 26, 2012 at 8:55 am | Permalink

    Hi Pascal, you’re right, maybe this wouldn’t be too hard.

    The best thing about the original UCC was the awesome problem statements, like luggage sorting and image processing and (maybe best of all) bad crypto. We’d need to think of some new ones.

    Meanwhile I’m trying to write something about undefined behavior that is funnier than your restrict post.