From patchwork Wed May 9 20:02:18 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Kees Cook X-Patchwork-Id: 10390755 Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork.web.codeaurora.org (Postfix) with ESMTP id 5C74A60548 for ; Wed, 9 May 2018 20:02:49 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 4A716286DF for ; Wed, 9 May 2018 20:02:49 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 48214286F8; Wed, 9 May 2018 20:02:49 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on pdx-wl-mail.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-3.0 required=2.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,MAILING_LIST_MULTI,RCVD_IN_DNSWL_NONE autolearn=unavailable version=3.3.1 Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id B13A6286DF for ; Wed, 9 May 2018 20:02:47 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 3E0116B0582; Wed, 9 May 2018 16:02:41 -0400 (EDT) Delivered-To: linux-mm-outgoing@kvack.org Received: by kanga.kvack.org (Postfix, from userid 40) id 391436B0584; Wed, 9 May 2018 16:02:41 -0400 (EDT) X-Original-To: int-list-linux-mm@kvack.org X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 1E8D36B0583; Wed, 9 May 2018 16:02:41 -0400 (EDT) X-Original-To: linux-mm@kvack.org X-Delivered-To: linux-mm@kvack.org Received: from mail-pf0-f197.google.com (mail-pf0-f197.google.com [209.85.192.197]) by kanga.kvack.org (Postfix) with ESMTP id BD96D6B0581 for ; Wed, 9 May 2018 16:02:40 -0400 (EDT) Received: by mail-pf0-f197.google.com with SMTP id z5so15129336pfz.6 for ; Wed, 09 May 2018 13:02:40 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:dkim-signature:from:to:cc:subject:date :message-id:in-reply-to:references; bh=G1OHmpSEH017CtI3WvVjeccur56qeHJaWJYJTU4CY4k=; b=MlBVoJxZ5MIzPW+f7wLCWe24r3GLC+YQiBpqi3HdNFs1v4QqndQixkifSrZ10wjN8R Z6uHylHdBimXisj30kpHapbpQDL0UWBqd3VxJUD4WbHhyk+ofikRa3oOkUabR9me9SrT BSiyC2LFNBarYADKgO82L8IolEyK95SIB+Is42MkR0PnmtQ0uyrv8wqo45rsdefkPGzW dpNSWJndFsUPfcv+UmAqxR6HqkwNdzqIhQ/Ee3TfftQWKPfd/Mtehi3oivqFEzWIJQ+C EZ1Kjlhv0fad5MS5mn+Y8XdpDXOT8hD7SLdwuJtPFdFoRmxKRIDSBwmFT79J7CAsEw2M gG0g== X-Gm-Message-State: ALQs6tBEFhcKvNuBtQCyqKAKl9v+6B9Oj5Bwd5FPOj6TROw1cTiswuF1 /bAT2n7qzJM3K/qXXvCaqrhQl7XgcUeYhR0sSC8BPkyIeB5MFpv8E649KWrIaea2RqBgxQvml6u nMKHREhS5xFyLl3NwWttLMHblctiMtXNrdS33GoZdhU/py2ee0ruMzcY/B0F3Z4Z8YYIM6VUwGS atT7SVw9iorzFQou1QJ0JaEiynJR8jEwPApnnVTYnp8XRUubBKViPrtndfJUltL2Mz4bCjuZxW4 L+K9EXfT7p0eROCCDyWfML07MVVZVbbV/rfZizdmbCmf7meA5puxJRA0EfG4MJML+sJW5mkSKQp b97xz96FIh20hAJebMmO22Rw0KPfJpYEB0xFWI1Rke/kYMKOQhh1hpi0Uiezc/R1B1+xmA2H+RN 4 X-Received: by 2002:a17:902:bc49:: with SMTP id t9-v6mr22337799plz.109.1525896160253; Wed, 09 May 2018 13:02:40 -0700 (PDT) X-Received: by 2002:a17:902:bc49:: with SMTP id t9-v6mr22337685plz.109.1525896158715; Wed, 09 May 2018 13:02:38 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1525896158; cv=none; d=google.com; s=arc-20160816; b=Ug6h+oJsbQfMBKwIm9oNZ1eRlLc3pdbeS4juZoPAmN4zD06JeVmfeuu42Ka+XoCmey a75WvAfksb6QTiCSwOIuoZZgqnjuqRBUtVHItb9E6qbqQBS5g3HKmx5STHBEUFxkkOgM 2G8NbtK/z7jxKfrGNdvo/MGlD2D/ODIojEktQM+lz9lHXMz4VE1CPmRwjWD9EOvsmq4J Fy+u/izxDtxyy+3pnqxLlQlPIcls37Y8e5x+oMGul1w7e6Ib5+LjjFpGe3ADDnc1AfxM KqybZEAz+yMikpF52D1HbGAJ7i8YvtjhblVCtdApcwkOa0U20UfkDgVbLpBmb77Ep5pT 2Tjg== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=references:in-reply-to:message-id:date:subject:cc:to:from :dkim-signature:arc-authentication-results; bh=G1OHmpSEH017CtI3WvVjeccur56qeHJaWJYJTU4CY4k=; b=pZmVmK4oS1YZJdSkveZ/Vrt97QLtrwCc2dhjkr6ArflZzbRWOz2Bv6ovlavU05Mxys Xre+Kq90e999Cw9u8NZUjGXm8mgkp6c+U6b8DK5IPOW5MZyp3LG1ExNnuN7AojJ0BUVN FKKIZ8YgeIidbBB/E27ayPZtt9kktaXcL2I1UzQqJEwbG1tiWKxWzSS+VLqUIaseKt8m ATToOcLbfdx6oQn+eb+ZAsEdrJTFWNWKExUp73stN/ZFwzGxco20rbXqcffXVTZkI7nm STD9NlwPPoVEnAOgpnrz3+d+UiFcc+wd5bJgww2k9BqmOoyLhjq79Th43gsuUQ3cF2Oi wFtA== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@chromium.org header.s=google header.b=h9TopDJ3; spf=pass (google.com: domain of keescook@chromium.org designates 209.85.220.65 as permitted sender) smtp.mailfrom=keescook@chromium.org; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=chromium.org Received: from mail-sor-f65.google.com (mail-sor-f65.google.com. [209.85.220.65]) by mx.google.com with SMTPS id e5-v6sor4565350pgn.263.2018.05.09.13.02.38 for (Google Transport Security); Wed, 09 May 2018 13:02:38 -0700 (PDT) Received-SPF: pass (google.com: domain of keescook@chromium.org designates 209.85.220.65 as permitted sender) client-ip=209.85.220.65; Authentication-Results: mx.google.com; dkim=pass header.i=@chromium.org header.s=google header.b=h9TopDJ3; spf=pass (google.com: domain of keescook@chromium.org designates 209.85.220.65 as permitted sender) smtp.mailfrom=keescook@chromium.org; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=chromium.org 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=h9TopDJ3guf3v9w/4BDcRO10TDH4hcq0dSvlLuUf/Lg1NcVnDkmBARWQuUP5Tpb6OE Y2J6COtoI7mvFkcOC/0lBxSI/ygbhNqLB86jMiL1LO6XW0Idq8S2aF8uN+R88q8wfZbe oV8ZZi4byXhVi0c+zLRQUImkuiOBi1+J4rNww= X-Google-Smtp-Source: AB8JxZpmS8vEGG6NNkZU19yt2w20Get+SzCg7+JZ2f4N/2K7VOgiE+bNjqlZswqjbqA1gkJlVLmkhw== X-Received: by 2002:a63:8049:: with SMTP id j70-v6mr37600378pgd.12.1525896158071; Wed, 09 May 2018 13:02:38 -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 131sm27857678pfa.128.2018.05.09.13.02.33 (version=TLS1_2 cipher=ECDHE-RSA-CHACHA20-POLY1305 bits=256/256); Wed, 09 May 2018 13:02:33 -0700 (PDT) From: Kees Cook To: Matthew Wilcox Cc: Kees Cook , Rasmus Villemoes , Matthew Wilcox , LKML , Linux-MM , Kernel Hardening Subject: [PATCH v2 1/6] compiler.h: enable builtin overflow checkers and add fallback code Date: Wed, 9 May 2018 13:02:18 -0700 Message-Id: <20180509200223.22451-2-keescook@chromium.org> X-Mailer: git-send-email 2.17.0 In-Reply-To: <20180509200223.22451-1-keescook@chromium.org> References: <20180509200223.22451-1-keescook@chromium.org> X-Bogosity: Ham, tests=bogofilter, spamicity=0.000000, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: X-Virus-Scanned: ClamAV using ClamSMTP 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 */