9/8/16: Fundamentals 3: Undefined Behavior and Arena Allocation

• Exercise
• Slides from lecture
• Lecture code is in cs61-exercises/fundamentals3

Undefined behavior

• A Guide to Undefined Behavior in C and C++, Part 1 (John Regehr)
• What Every C Programmer Should Know About Undefined Behavior, Part 1 (Chris Lattner of LLVM)

In lecture, we saw a slightly contrived example of undefined behavior causing a problem. Here are some (slightly tweaked) examples.

Defined

static int array[10] = { ... };
int f1(int index) {
    if (index < 0 || index >= 10)
        abort();
    int x = array[index];
    assert(index >= 0 && index < 10);
    return x;
}

• Well-defined for all indexes
• Semantics: If index is in range, return array[index]; otherwise call abort(), which quits the program
• The assert will never fail
• Furthermore, the compiler can prove that the assert will never fail
  • If the index was out of range, the program already aborted
• So the compiler can remove the assert! And gcc will at high optimization levels.

Sometimes-undefined

static int array[10] = { ... };
int f1(int index) {
    if (index < 0 || index >= 11)
        abort();
    int x = array[index];
    assert(index >= 0 && index < 10);
    return x;
}

• Well-defined for all indexes except 10
• Expected semantics: If index is in range, return array[index]; otherwise, if index == 10, the assertion fails, which quits the program; otherwise, call abort(), which quits the program
• Actual semantics: If index is in range, return array[index]; otherwise, if index == 10, undefined behavior; otherwise, call abort(), which quits the program
  • The program references array[index] before the assert
  • This means that when index == 10, the program performs undefined behavior
• The compiler has no responsibilities if a program executes undefined behavior
• So the compiler can assume undefined behavior never occurs
• Which means the compiler can remove the assert!!
  • The compiler can prove that index \>= 0 (otherwise the program aborted)
  • The compiler can prove that index \< 11 (otherwise the program aborted)
  • The compiler can “prove” that index ≠ 10 (otherwise the program executed undefined behavior)
• GCC does not currently remove the assert in this case—but one day it could! Similar codes have had similar serious problems in the past.