A glimpse of undefined behavior in C

A few weeks ago a coworker of mine stopped by my desk with a coding question.  We’d recently been quizzing each other over our C knowledge, so I smiled and braced myself for the hell which was clearly to come.

He wrote a few lines of code up on the whiteboard and asked what the program output:

#include <stdio.h>

int main(){
    int i = 0;
    int a[] = {10,20,30};

    int r = 1 * a[i++] + 2 * a[i++] + 3 * a[i++];
    printf("%d\n", r); 
    return 0;
}

It seemed pretty straightforward. I explained the order of operator precedence – postfix binds before multiplication which binds before addition and also that multiplication and addition’s associativity was left to right, so I grabbed the marker and started writing out the arithmetic.

int r = 1 * a[i++] + 2 * a[i++] + 3 * a[i++];
//    =    a[0]    + 2 * a[1]  + 3 * a[2];
//    =     10     +     40    +    90;
//    = 140

After I smugly scribbled down the answer, my coworker replied a simple “nope”. I thought for a few minutes, and was stumped. I couldn’t quite remember the order of the postfix operators’ associativity. Furthermore, I knew that wouldn’t even change the order of evaluation here as associativity rules only apply between operators of the same precedence level, but thought I’d give it a shot and walk through the arithmetic as if the postfix operators were all evaluated right to left.

int r = 1 * a[i++] + 2 * a[i++] + 3 * a[i++];
//    =    a[2]    + 2 * a[1]  + 3 * a[0];
//    =     30     +     40    +    30;
//    = 100

Again, my coworker replied it was still wrong. At this point I threw up my hands and asked what the answer was. It turned out that this small sample was actually reduced from a larger code snippet he’d put together. To verify his question, he’d compiled and run the larger sample but was surprised to see it not behave as he’d thought. After reducing the unexpected behavior to this illuminating example, he’d compiled it with gcc 4.7.3 and it output a startling result: “60″.

At this point I was intrigued. I remembered that, in C, the order of function argument evaluation was undefined, so we thought maybe the postfix operators were just being evaluated in some random non-left-to-right order. Still convinced that postfix had a higher operator precedence than addition and multiplication, we quickly proved to ourselves that there was no order we could evaluate the i++’s such that the three elements of the array were added/multiplied together to get “60″.

Now I was hooked. My first thought was to look at the disassembly of the snippet and try and track down what was actually going on. I compiled the sample with debugging symbols and after a quick objdump we had the source-annotated x86_64 disassembly:

Disassembly of section .text:

0000000000000000 <main>:
#include <stdio.h>

int main(){
   0:	55                   	push   %rbp
   1:	48 89 e5             	mov    %rsp,%rbp
   4:	48 83 ec 20          	sub    $0x20,%rsp
    int i = 0;
   8:	c7 45 e8 00 00 00 00 	movl   $0x0,-0x18(%rbp)
    int a[] = {10,20,30};
   f:	c7 45 f0 0a 00 00 00 	movl   $0xa,-0x10(%rbp)
  16:	c7 45 f4 14 00 00 00 	movl   $0x14,-0xc(%rbp)
  1d:	c7 45 f8 1e 00 00 00 	movl   $0x1e,-0x8(%rbp)
    int r = 1 * a[i++] + 2 * a[i++] + 3 * a[i++];
  24:	8b 45 e8             	mov    -0x18(%rbp),%eax
  27:	48 98                	cltq   
  29:	8b 54 85 f0          	mov    -0x10(%rbp,%rax,4),%edx
  2d:	8b 45 e8             	mov    -0x18(%rbp),%eax
  30:	48 98                	cltq   
  32:	8b 44 85 f0          	mov    -0x10(%rbp,%rax,4),%eax
  36:	01 c0                	add    %eax,%eax
  38:	8d 0c 02             	lea    (%rdx,%rax,1),%ecx
  3b:	8b 45 e8             	mov    -0x18(%rbp),%eax
  3e:	48 98                	cltq   
  40:	8b 54 85 f0          	mov    -0x10(%rbp,%rax,4),%edx
  44:	89 d0                	mov    %edx,%eax
  46:	01 c0                	add    %eax,%eax
  48:	01 d0                	add    %edx,%eax
  4a:	01 c8                	add    %ecx,%eax
  4c:	89 45 ec             	mov    %eax,-0x14(%rbp)
  4f:	83 45 e8 01          	addl   $0x1,-0x18(%rbp)
  53:	83 45 e8 01          	addl   $0x1,-0x18(%rbp)
  57:	83 45 e8 01          	addl   $0x1,-0x18(%rbp)
    printf("%d\n", r);
  5b:	8b 45 ec             	mov    -0x14(%rbp),%eax
  5e:	89 c6                	mov    %eax,%esi
  60:	bf 00 00 00 00       	mov    $0x0,%edi
  65:	b8 00 00 00 00       	mov    $0x0,%eax
  6a:	e8 00 00 00 00       	callq  6f <main+0x6f>
    return 0;
  6f:	b8 00 00 00 00       	mov    $0x0,%eax
}
  74:	c9                   	leaveq 
  75:	c3                   	retq 

The first few and last few instructions just set up the stack frame, initial variable values, and do the printf call and return from main, so we really only cared about instructions 0×24 through 0×57. That’s where the interesting behavior was. Let’s walk through the instructions a few at a time:

  24:	8b 45 e8             	mov    -0x18(%rbp),%eax
  27:	48 98                	cltq   
  29:	8b 54 85 f0          	mov    -0x10(%rbp,%rax,4),%edx

The first three instructions were as we expected. First, it loads the value of i (0) into register eax, sign-extends it to 64 bits, then loads a[0] into register edx. The 1 * was obviously optimized out by the compiler, but everything looked normal here. The next few started out much the same:

  2d:	8b 45 e8             	mov    -0x18(%rbp),%eax
  30:	48 98                	cltq   
  32:	8b 44 85 f0          	mov    -0x10(%rbp,%rax,4),%eax
  36:	01 c0                	add    %eax,%eax
  38:	8d 0c 02             	lea    (%rdx,%rax,1),%ecx

The first mov loads the value of i (still 0) into eax, sign-extends it to 64-bits, then loads a[0] into eax. That’s intersting – we expected the i++ to have been performed before these three instructions again, but maybe the last two instructions will do some sort of assembly magic to get us to the expected result (2 * a[1]). The two instructions add eax to itself, effectively performing 2 * a[0], then add that result to the previous computation and stores it in ecx. At this point the instructions have evaluated a[0] + 2 * a[0]. Things are starting to look a little strange but again, maybe there’s some compiler magic going on.

  3b:	8b 45 e8             	mov    -0x18(%rbp),%eax
  3e:	48 98                	cltq   
  40:	8b 54 85 f0          	mov    -0x10(%rbp,%rax,4),%edx
  44:	89 d0                	mov    %edx,%eax

These next few instructions are starting to look pretty familiar. They load the value of i (still 0), sign extend it to 64-bits, load a[0] into edx, then copy edx into eax. Hmm, ok let’s take a look at a few more:

  46:	01 c0                	add    %eax,%eax
  48:	01 d0                	add    %edx,%eax
  4a:	01 c8                	add    %ecx,%eax
  4c:	89 45 ec             	mov    %eax,-0x14(%rbp)

Here, it adds a[0] to itself 3 times, adds it the previous computation, then stores it into variable ‘r’. Now that’s wild – our variable r now contains a[0] + 2 * a[0] + 3 * a[0]. Sure enough, that’s what the program output: “60″. But what happened to those postfix operations? They’re all there at the end:

  4f:	83 45 e8 01          	addl   $0x1,-0x18(%rbp)
  53:	83 45 e8 01          	addl   $0x1,-0x18(%rbp)
  57:	83 45 e8 01          	addl   $0x1,-0x18(%rbp)

It seemed our compiled version of the code just seemed completely wrong! Why had the postfix operations been thrown down at the end after the assignment had already happened? With my faith in reality dwindling, I decided to go straight to the source. No, not the compiler’s source – that’s just an implementation – I grabbed the C11 language specification.

The issue lay within the details of the postfix operations. In our case, we were thrice performing a postfix increment to our array index in a single expression. When evaluating a postfix operator it returns the initial value of the variable. The assignment of the new value back to the variable is known as a side effect. It turns out that side effects are only defined to have been committed between sequence points. See section 5.1.2.3 of the standard for the specifics of where sequence points are defined, but in our case our expression exhibits undefined behavior. It’s entirely up to the compiler when the side-effect of the assignment of the new value back to the variable is performed with respect to the other parts of the expression.

In the end, we both learned a bit more about the C language. It’s well-known best practice to avoid constructing complex expressions with prefix/postfix operators, and this is a great example of why that is the case.

17 thoughts on “A glimpse of undefined behavior in C

      1. Jose

        How is that undefined behavior?

        Thank God c works this way. It should not be a subjective order in operands in c(left to right, why?, in other countries they do it backwards), or the order should be based automated on mathematical terms, as it is today.

        What I love about c is that is so simple to understand and parse, product of not being too constrained in committees and bureaucracies, but made by a very small group of people. When you want to order something you just split it in multiple lines, which by the way is easier to read.

        When I want a high level language I use python , objc, java or c#.

  1. sftrabbit

    To correct, you first need to say that the order of evaluation of the increment subexpressions is “unsequenced” (according to §6.5/3). Then, unsequenced side effects on a single scalar object lead to “undefined behaviour” (§6.5/2), which is very different to implementation-defined behaviour!

    Reply
  2. mjduminy

    Very interesting read. I am not a low-level programmer at all, although I wish I knew more about it, so please forgive me for this question: would changing i++ into ++i change the output?

    Reply
    1. Christopher Cole Post author

      Changing i++ to ++i would indeed change the output, but not to what one might expect – it would still be undefined behavior. The side-effect of assigning the incremented value back to the variable i is only guaranteed by the language to have been performed by the next sequence point, which in this case is the end of the statement not within the expression. That means that while the first ++i would yield the value 1 within the expression, when the subsequent ++i expressions are evaluated the side-effect of assigning 1 back to variable i is not guaranteed to have occurred, meaning the second ++i could legally return i + 1 = 1 again. The compiler could very well produce code where r = a[1] + 2 * a[1] + 3 * a[1] or even r = a[0] + a[1] + a[2] – again, it’s undefined.

      Note: The scary part of it being undefined is that the evaluated values of the multiple i++’s aren’t limited to 0,1,2 in this example. It could very well evaluate to 0xDEADBEEF if it wanted to.

      Reply
    1. patriot7

      140 for clang 3.3
      60 for gcc 4.6.4

      clang seems more clever, it gives the warning: multiple unsequenced modifications to ‘i’ and tries understand the code in a more intuitive way

      Reply
      1. benmcollins

        I ran mine with gcc 4.8.1 and got 140. Turning on -Wall produced similar warnings to which you saw in clang:

        $ gcc -Wall math.c -o math
        math.c: In function ‘main’:
        math.c:7:46: warning: operation on ‘i’ may be undefined [-Wsequence-point]
        int r = 1 * a[i++] + 2 * a[i++] + 3 * a[i++];
        ^
        math.c:7:46: warning: operation on ‘i’ may be undefined [-Wsequence-point]

        Seems it’s just as smart. Odd when undefined behavior changes between versions of gcc though. I tried with differing levels of optimization and it always gave 140.

  3. Pingback: A glimpse of undefined behavior in C | Enjoying The Moment

  4. @f4grx

    I was recently bitten with a compiler that would spit invalid code for:

    char array[len];
    char *pointer = array – 3;

    But still compiled this correctly:
    char array[len];
    char *pointer; //initialization irrelevant
    char *otherpointer = array – pointer – 3;

    so it did not want to subtract a constant from an array reference, but would subtract a pointer from this array reference!

    This is also undefined by C.

    NEVER tell anyone that arrays and pointers are the same!

    Reply
  5. Russ C.

    Have to admit, this kind of behaviour by the compiler irritates me a little; the reason one often uses infix ++/– operators within these loops is to achieve concise code.

    In this case, the alternative not only forces you to roll-out your expression, but (in shared code anyway) also to add excessive comments to say why you’ve had to extend your code in such an un-natural way.

    Thats my issue anyway :)

    Perhaps a pragma operator to say when to evaluate side effects would be a solution ?

    Reply
  6. William

    So C is also not spared with platform and compiler issue, that’s why I like Java, which doesn’t have any undefined behavior, oh sorry, they also have JVM, GC and thread schedulers.

    Reply
  7. Pingback: Recent Readings: 2014 Week 10 | Larry's Notebook

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s