Received: by 2002:ac0:a5b6:0:0:0:0:0 with SMTP id m51-v6csp30738imm; Thu, 31 May 2018 17:49:33 -0700 (PDT) X-Google-Smtp-Source: ADUXVKKNGLnFX4jyytfi5Yi9fpcDXUhnZK38vzkfQ1joAi4YJbGa2orByJANzOVMikqwHeFhu2Zv X-Received: by 2002:a63:6945:: with SMTP id e66-v6mr7211907pgc.306.1527814173492; Thu, 31 May 2018 17:49:33 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1527814173; cv=none; d=google.com; s=arc-20160816; b=wr/aMQBbHq2psKLU9UkS8qY1iS8QkyybxG88DTSr9L6fXZwwVpHN1hg7bY5ergmeyB rAx/x/B1nw8dc65paI0X286HH3xVcu/BuL9iYHLG8Bmls2ogLGyfH5gloANYb5ffxgKN 0qqP98oiTloBP7xhQ/cczgCcYDS8xQm5KYc3Dl8RLpUSO0qQhkhTDdYRVe9Pw4Zt1hPr qWFo0/wkHTiKaxF8uy7X0zqAO/sX8ZDn2Q+QboFltVaPAb1v3GBNvwzPHgmoeBM9vpTE W9483F3dZd5rf1JTNUTnpqgLYwTgd5rURFK/9akI9CcqrUZ4yd+YPxs7Lzw9YmAlzdBa SejQ== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:sender:references:in-reply-to:message-id:date :subject:cc:to:from:dkim-signature:arc-authentication-results; bh=G1OHmpSEH017CtI3WvVjeccur56qeHJaWJYJTU4CY4k=; b=ZHEz11Kw4AAqyP7kFQMfxX5i8R/APPX1JAKVz18diKRkrlEoDhUdlAoE3EkAQvJFWU aeAAc32MawkoN+4tCjUsTjp2BE2VUgZygAgCofRxU9Hw6l3ZKIhZdBAtVJO/eGzJzJBg HDkZx4zNH9itrcsCejYlzH9J4X/exkkaVj9BtvqvHL82BHzmPRW7MTmgsIwKjl1Mp/zP OLUEAHPkx8qNtyNo1rYGN858KdPzIhbRRVWIIGSCGrbYXCYSAf2lYvFx1hv5O8H5i7pF agkuXZy2bfGH7rjl2WZLv+y/GVaT7qpbw6V0iy5fbSLSFC4d3Is2j3Oiy85OXsrrZN59 Ae2A== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@chromium.org header.s=google header.b=h6wX7vCl; spf=pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=chromium.org Return-Path: Received: from vger.kernel.org (vger.kernel.org. [209.132.180.67]) by mx.google.com with ESMTP id o3-v6si3340511pfa.15.2018.05.31.17.49.19; Thu, 31 May 2018 17:49:33 -0700 (PDT) Received-SPF: pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) client-ip=209.132.180.67; Authentication-Results: mx.google.com; dkim=pass header.i=@chromium.org header.s=google header.b=h6wX7vCl; spf=pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=chromium.org Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1751357AbeFAAnr (ORCPT + 99 others); Thu, 31 May 2018 20:43:47 -0400 Received: from mail-pl0-f66.google.com ([209.85.160.66]:45047 "EHLO mail-pl0-f66.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1750724AbeFAAnn (ORCPT ); Thu, 31 May 2018 20:43:43 -0400 Received: by mail-pl0-f66.google.com with SMTP id z9-v6so10898243plk.11 for ; Thu, 31 May 2018 17:43:43 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=chromium.org; s=google; h=from:to:cc:subject:date:message-id:in-reply-to:references; bh=G1OHmpSEH017CtI3WvVjeccur56qeHJaWJYJTU4CY4k=; b=h6wX7vCl3cuVP20xVEgOA/HQ38ZC4+3oTu74VJiW9UJ97gDyDyDy/2Jil8Y//nKo+0 pAxA6lfAK0kNk0YlfYOgxiQHvj54kV5qY43kwZbxX77NcM/rva4u/ktHRal659fC4hrt K+8U9crqaII8n43O2Sz5LShcriRz5AFu4KAtU= X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references; bh=G1OHmpSEH017CtI3WvVjeccur56qeHJaWJYJTU4CY4k=; b=Lx5DXwMDYqB3xvkfBD+KHrBPJRxftW9PuNzu83ma8hDGJKka+jUkM5NR4tEuG/AQjN +HHQu8ikYHWTj6h3uBMO6qeupocwi9wf8ZqXb51TmCkgWUoN0FwRWUy8p0Kx2oh7+mRH 2JDEu6DnyqOn2Q0NOXdEebyhJSb9D/dMW0ZQNMtrrkH1fbCR3fY9eNi21ECDOEDeZ4MX CaGKMhUVrdCcLJ5laU+AWaPRnUFvfImC98yqW+XSTI2tcLJ1Et7hvDkcaEE082jKOx4z pZ4G2IcGwQ6buY0BSMF53vBdZdTrM0z9eUgvfXlLmjdEvsJquicUKR7TxIHrwt3qjL9R RjjA== X-Gm-Message-State: ALKqPwfSponNbRLUh8naurpRfryICqUCdpQkLuGl2vfK0Ba97iH97yc4 1JaOKX3Zerdc/hasfERROvEvsw== X-Received: by 2002:a17:902:780a:: with SMTP id p10-v6mr9008931pll.281.1527813822353; Thu, 31 May 2018 17:43:42 -0700 (PDT) Received: from www.outflux.net (173-164-112-133-Oregon.hfc.comcastbusiness.net. [173.164.112.133]) by smtp.gmail.com with ESMTPSA id m14-v6sm60967072pgs.72.2018.05.31.17.43.40 (version=TLS1_2 cipher=ECDHE-RSA-CHACHA20-POLY1305 bits=256/256); Thu, 31 May 2018 17:43:41 -0700 (PDT) From: Kees Cook To: Matthew Wilcox Cc: Kees Cook , Rasmus Villemoes , Linus Torvalds , Matthew Wilcox , LKML , Linux-MM , Kernel Hardening Subject: [PATCH v3 01/16] compiler.h: enable builtin overflow checkers and add fallback code Date: Thu, 31 May 2018 17:42:18 -0700 Message-Id: <20180601004233.37822-2-keescook@chromium.org> X-Mailer: git-send-email 2.17.0 In-Reply-To: <20180601004233.37822-1-keescook@chromium.org> References: <20180601004233.37822-1-keescook@chromium.org> Sender: linux-kernel-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org From: Rasmus Villemoes 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: Rasmus Villemoes Signed-off-by: Kees Cook --- include/linux/compiler-clang.h | 14 +++ include/linux/compiler-gcc.h | 4 + include/linux/compiler-intel.h | 4 + include/linux/overflow.h | 205 +++++++++++++++++++++++++++++++++ 4 files changed, 227 insertions(+) create mode 100644 include/linux/overflow.h diff --git a/include/linux/compiler-clang.h b/include/linux/compiler-clang.h index 7d98e263e048..7087446c24c8 100644 --- a/include/linux/compiler-clang.h +++ b/include/linux/compiler-clang.h @@ -32,3 +32,17 @@ #ifdef __noretpoline #undef __noretpoline #endif + +/* + * Not all versions of clang implement the the type-generic versions + * of the builtin overflow checkers. Fortunately, clang implements + * __has_builtin allowing us to avoid awkward version + * checks. Unfortunately, we don't know which version of gcc clang + * pretends to be, so the macro may or may not be defined. + */ +#undef COMPILER_HAS_GENERIC_BUILTIN_OVERFLOW +#if __has_builtin(__builtin_mul_overflow) && \ + __has_builtin(__builtin_add_overflow) && \ + __has_builtin(__builtin_sub_overflow) +#define COMPILER_HAS_GENERIC_BUILTIN_OVERFLOW 1 +#endif diff --git a/include/linux/compiler-gcc.h b/include/linux/compiler-gcc.h index b4bf73f5e38f..f1a7492a5cc8 100644 --- a/include/linux/compiler-gcc.h +++ b/include/linux/compiler-gcc.h @@ -343,3 +343,7 @@ * code */ #define uninitialized_var(x) x = x + +#if GCC_VERSION >= 50100 +#define COMPILER_HAS_GENERIC_BUILTIN_OVERFLOW 1 +#endif diff --git a/include/linux/compiler-intel.h b/include/linux/compiler-intel.h index bfa08160db3a..547cdc920a3c 100644 --- a/include/linux/compiler-intel.h +++ b/include/linux/compiler-intel.h @@ -44,3 +44,7 @@ #define __builtin_bswap16 _bswap16 #endif +/* + * icc defines __GNUC__, but does not implement the builtin overflow checkers. + */ +#undef COMPILER_HAS_GENERIC_BUILTIN_OVERFLOW diff --git a/include/linux/overflow.h b/include/linux/overflow.h new file mode 100644 index 000000000000..c8890ec358a7 --- /dev/null +++ b/include/linux/overflow.h @@ -0,0 +1,205 @@ +/* SPDX-License-Identifier: GPL-2.0 OR MIT */ +#ifndef __LINUX_OVERFLOW_H +#define __LINUX_OVERFLOW_H + +#include + +/* + * In the fallback code below, we need to compute the minimum and + * maximum values representable in a given type. These macros may also + * be useful elsewhere, so we provide them outside the + * COMPILER_HAS_GENERIC_BUILTIN_OVERFLOW block. + * + * It would seem more obvious to do something like + * + * #define type_min(T) (T)(is_signed_type(T) ? (T)1 << (8*sizeof(T)-1) : 0) + * #define type_max(T) (T)(is_signed_type(T) ? ((T)1 << (8*sizeof(T)-1)) - 1 : ~(T)0) + * + * Unfortunately, the middle expressions, strictly speaking, have + * undefined behaviour, and at least some versions of gcc warn about + * the type_max expression (but not if -fsanitize=undefined is in + * effect; in that case, the warning is deferred to runtime...). + * + * The slightly excessive casting in type_min is to make sure the + * macros also produce sensible values for the exotic type _Bool. [The + * overflow checkers only almost work for _Bool, but that's + * a-feature-not-a-bug, since people shouldn't be doing arithmetic on + * _Bools. Besides, the gcc builtins don't allow _Bool* as third + * argument.] + * + * Idea stolen from + * https://mail-index.netbsd.org/tech-misc/2007/02/05/0000.html - + * credit to Christian Biere. + */ +#define is_signed_type(type) (((type)(-1)) < (type)1) +#define __type_half_max(type) ((type)1 << (8*sizeof(type) - 1 - is_signed_type(type))) +#define type_max(T) ((T)((__type_half_max(T) - 1) + __type_half_max(T))) +#define type_min(T) ((T)((T)-type_max(T)-(T)1)) + + +#ifdef COMPILER_HAS_GENERIC_BUILTIN_OVERFLOW +/* + * For simplicity and code hygiene, the fallback code below insists on + * a, b and *d having the same type (similar to the min() and max() + * macros), whereas gcc's type-generic overflow checkers accept + * different types. Hence we don't just make check_add_overflow an + * alias for __builtin_add_overflow, but add type checks similar to + * below. + */ +#define check_add_overflow(a, b, d) ({ \ + typeof(a) __a = (a); \ + typeof(b) __b = (b); \ + typeof(d) __d = (d); \ + (void) (&__a == &__b); \ + (void) (&__a == __d); \ + __builtin_add_overflow(__a, __b, __d); \ +}) + +#define check_sub_overflow(a, b, d) ({ \ + typeof(a) __a = (a); \ + typeof(b) __b = (b); \ + typeof(d) __d = (d); \ + (void) (&__a == &__b); \ + (void) (&__a == __d); \ + __builtin_sub_overflow(__a, __b, __d); \ +}) + +#define check_mul_overflow(a, b, d) ({ \ + typeof(a) __a = (a); \ + typeof(b) __b = (b); \ + typeof(d) __d = (d); \ + (void) (&__a == &__b); \ + (void) (&__a == __d); \ + __builtin_mul_overflow(__a, __b, __d); \ +}) + +#else + + +/* Checking for unsigned overflow is relatively easy without causing UB. */ +#define __unsigned_add_overflow(a, b, d) ({ \ + typeof(a) __a = (a); \ + typeof(b) __b = (b); \ + typeof(d) __d = (d); \ + (void) (&__a == &__b); \ + (void) (&__a == __d); \ + *__d = __a + __b; \ + *__d < __a; \ +}) +#define __unsigned_sub_overflow(a, b, d) ({ \ + typeof(a) __a = (a); \ + typeof(b) __b = (b); \ + typeof(d) __d = (d); \ + (void) (&__a == &__b); \ + (void) (&__a == __d); \ + *__d = __a - __b; \ + __a < __b; \ +}) +/* + * If one of a or b is a compile-time constant, this avoids a division. + */ +#define __unsigned_mul_overflow(a, b, d) ({ \ + typeof(a) __a = (a); \ + typeof(b) __b = (b); \ + typeof(d) __d = (d); \ + (void) (&__a == &__b); \ + (void) (&__a == __d); \ + *__d = __a * __b; \ + __builtin_constant_p(__b) ? \ + __b > 0 && __a > type_max(typeof(__a)) / __b : \ + __a > 0 && __b > type_max(typeof(__b)) / __a; \ +}) + +/* + * For signed types, detecting overflow is much harder, especially if + * we want to avoid UB. But the interface of these macros is such that + * we must provide a result in *d, and in fact we must produce the + * result promised by gcc's builtins, which is simply the possibly + * wrapped-around value. Fortunately, we can just formally do the + * operations in the widest relevant unsigned type (u64) and then + * truncate the result - gcc is smart enough to generate the same code + * with and without the (u64) casts. + */ + +/* + * Adding two signed integers can overflow only if they have the same + * sign, and overflow has happened iff the result has the opposite + * sign. + */ +#define __signed_add_overflow(a, b, d) ({ \ + typeof(a) __a = (a); \ + typeof(b) __b = (b); \ + typeof(d) __d = (d); \ + (void) (&__a == &__b); \ + (void) (&__a == __d); \ + *__d = (u64)__a + (u64)__b; \ + (((~(__a ^ __b)) & (*__d ^ __a)) \ + & type_min(typeof(__a))) != 0; \ +}) + +/* + * Subtraction is similar, except that overflow can now happen only + * when the signs are opposite. In this case, overflow has happened if + * the result has the opposite sign of a. + */ +#define __signed_sub_overflow(a, b, d) ({ \ + typeof(a) __a = (a); \ + typeof(b) __b = (b); \ + typeof(d) __d = (d); \ + (void) (&__a == &__b); \ + (void) (&__a == __d); \ + *__d = (u64)__a - (u64)__b; \ + ((((__a ^ __b)) & (*__d ^ __a)) \ + & type_min(typeof(__a))) != 0; \ +}) + +/* + * Signed multiplication is rather hard. gcc always follows C99, so + * division is truncated towards 0. This means that we can write the + * overflow check like this: + * + * (a > 0 && (b > MAX/a || b < MIN/a)) || + * (a < -1 && (b > MIN/a || b < MAX/a) || + * (a == -1 && b == MIN) + * + * The redundant casts of -1 are to silence an annoying -Wtype-limits + * (included in -Wextra) warning: When the type is u8 or u16, the + * __b_c_e in check_mul_overflow obviously selects + * __unsigned_mul_overflow, but unfortunately gcc still parses this + * code and warns about the limited range of __b. + */ + +#define __signed_mul_overflow(a, b, d) ({ \ + typeof(a) __a = (a); \ + typeof(b) __b = (b); \ + typeof(d) __d = (d); \ + typeof(a) __tmax = type_max(typeof(a)); \ + typeof(a) __tmin = type_min(typeof(a)); \ + (void) (&__a == &__b); \ + (void) (&__a == __d); \ + *__d = (u64)__a * (u64)__b; \ + (__b > 0 && (__a > __tmax/__b || __a < __tmin/__b)) || \ + (__b < (typeof(__b))-1 && (__a > __tmin/__b || __a < __tmax/__b)) || \ + (__b == (typeof(__b))-1 && __a == __tmin); \ +}) + + +#define check_add_overflow(a, b, d) \ + __builtin_choose_expr(is_signed_type(typeof(a)), \ + __signed_add_overflow(a, b, d), \ + __unsigned_add_overflow(a, b, d)) + +#define check_sub_overflow(a, b, d) \ + __builtin_choose_expr(is_signed_type(typeof(a)), \ + __signed_sub_overflow(a, b, d), \ + __unsigned_sub_overflow(a, b, d)) + +#define check_mul_overflow(a, b, d) \ + __builtin_choose_expr(is_signed_type(typeof(a)), \ + __signed_mul_overflow(a, b, d), \ + __unsigned_mul_overflow(a, b, d)) + + +#endif /* COMPILER_HAS_GENERIC_BUILTIN_OVERFLOW */ + +#endif /* __LINUX_OVERFLOW_H */ -- 2.17.0