2016/Fundamentals3

From CS61
Jump to: navigation, search

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

Undefined behavior

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.