• Rasmus Villemoes's avatar
    compiler.h: enable builtin overflow checkers and add fallback code · f0907827
    Rasmus Villemoes authored
    This adds wrappers for the __builtin overflow checkers present in gcc
    5.1+ as well as fallback implementations for earlier compilers. It's not
    that easy to implement the fully generic __builtin_X_overflow(T1 a, T2
    b, T3 *d) in macros, so the fallback code assumes that T1, T2 and T3 are
    the same. We obviously don't want the wrappers to have different
    semantics depending on $GCC_VERSION, so we also insist on that even when
    using the builtins.
    
    There are a few problems with the 'a+b < a' idiom for checking for
    overflow: For signed types, it relies on undefined behaviour and is
    not actually complete (it doesn't check underflow;
    e.g. INT_MIN+INT_MIN == 0 isn't caught). Due to type promotion it
    is wrong for all types (signed and unsigned) narrower than
    int. Similarly, when a and b does not have the same type, there are
    subtle cases like
    
      u32 a;
    
      if (a + sizeof(foo) < a)
        return -EOVERFLOW;
      a += sizeof(foo);
    
    where the test is always false on 64 bit platforms. Add to that that it
    is not always possible to determine the types involved at a glance.
    
    The new overflow.h is somewhat bulky, but that's mostly a result of
    trying to be type-generic, complete (e.g. catching not only overflow
    but also signed underflow) and not relying on undefined behaviour.
    
    Linus is of course right [1] that for unsigned subtraction a-b, the
    right way to check for overflow (underflow) is "b > a" and not
    "__builtin_sub_overflow(a, b, &d)", but that's just one out of six cases
    covered here, and included mostly for completeness.
    
    So is it worth it? I think it is, if nothing else for the documentation
    value of seeing
    
      if (check_add_overflow(a, b, &d))
        return -EGOAWAY;
      do_stuff_with(d);
    
    instead of the open-coded (and possibly wrong and/or incomplete and/or
    UBsan-tickling)
    
      if (a+b < a)
        return -EGOAWAY;
      do_stuff_with(a+b);
    
    While gcc does recognize the 'a+b < a' idiom for testing unsigned add
    overflow, it doesn't do nearly as good for unsigned multiplication
    (there's also no single well-established idiom). So using
    check_mul_overflow in kcalloc and friends may also make gcc generate
    slightly better code.
    
    [1] https://lkml.org/lkml/2015/11/2/658
    
    Signed-off-by: default avatarRasmus Villemoes <linux@rasmusvillemoes.dk>
    Signed-off-by: default avatarKees Cook <keescook@chromium.org>
    f0907827