From patchwork Fri Jun 1 00:42: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: 10442197 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 2936F603D7 for ; Fri, 1 Jun 2018 00:43:47 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 20DA028E43 for ; Fri, 1 Jun 2018 00:43:47 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 1532128E58; Fri, 1 Jun 2018 00:43:47 +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=ham 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 E31FD28E43 for ; Fri, 1 Jun 2018 00:43:45 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id E9A046B000A; Thu, 31 May 2018 20:43:44 -0400 (EDT) Delivered-To: linux-mm-outgoing@kvack.org Received: by kanga.kvack.org (Postfix, from userid 40) id E6E436B0008; Thu, 31 May 2018 20:43:44 -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 CC1BB6B000D; Thu, 31 May 2018 20:43:44 -0400 (EDT) X-Original-To: linux-mm@kvack.org X-Delivered-To: linux-mm@kvack.org Received: from mail-pf0-f199.google.com (mail-pf0-f199.google.com [209.85.192.199]) by kanga.kvack.org (Postfix) with ESMTP id 866F46B0008 for ; Thu, 31 May 2018 20:43:44 -0400 (EDT) Received: by mail-pf0-f199.google.com with SMTP id e3-v6so13576100pfe.15 for ; Thu, 31 May 2018 17:43:44 -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=R0pXk98YgIh856vFFdDZZ9QLmL3EjrXWVP42WQxxfp7X52gNttMPILn5WZNBlOvvve rAXrP//TffhfvyVZbEAectqCNyZTvPVA7oV+GeIMactPtMt/Bq2qiAA8JvfEx5HZsuLC LUDhzepWHrb52jNuUwVAVGi1sg8m7BFr3jKFdCVFSzVN7u0VOXfobAuQRza+GeVtZT6r jbiUmSEctlOiKPIJE4m0xrt2cdPbWdHd7HCTE7jYHYQ6s8AFOAqhiqEakiacgwhfHqS6 34Vyf3E1rA8qfdFvF0LtLRmXIOK52WjqUVymgH6rjRGwVqWFC6OxNhVWHjkxOzH1Z+o1 9tow== X-Gm-Message-State: ALKqPweD9kqSNMbnSDQ4H8I5aX4fn+5iyW0p97YA0x/YYrj/U+PazHPr HeZFXew/lqYz6p9XPcPx3G7vF8gKN/lUytmlsOVkWOJDEB76AlXMVl2VXNZ1GYnCjFgJtaTIqY1 eCinpxJs9OpreyM9mwcqMST2UIJ9MlFJfNdiElyZc+quXxqneC9cIoY4m26Fo6fFFZjBRcS9lxw hgIXs8LInU6aEeMfO5QGRzYJnPzqSXge6hMQkUVLke5ivGsbNBKyLRNuMI0aaP3r1j2EzMk8Xca 3l8PCqDUEv5wOetT2X1MevJ3gS/BVnGMwqV+Dyldf8ossfoHiz6Ib7Adik0DnZNLWZuCJam7YnP cwXf7qU5yC4Nw4E8iCS3pYlIydR4PxAq9ckdx+hwUXdH0M5UMJRXV4KmWmjUdG5ljhd1y0wzfsf g X-Received: by 2002:a62:18d6:: with SMTP id 205-v6mr8784200pfy.242.1527813824188; Thu, 31 May 2018 17:43:44 -0700 (PDT) X-Received: by 2002:a62:18d6:: with SMTP id 205-v6mr8784149pfy.242.1527813822746; Thu, 31 May 2018 17:43:42 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1527813822; cv=none; d=google.com; s=arc-20160816; b=byLMknNCD0KPLClZABF//WeDjCpWsIZDjUbVzwZlLON5pEUJqSxWK251ph8h07ONcL wpiID2fIN7gvd0L6dugjaShKWzyS8K+hBs+R2YvyAaKoDmYA53DrZ5a/4N1E1FRMVYFV LXICzlOmXZdeK2Q7bylidnnnvlfU7tWef4wG9Rv9BJxnI1u+cfCiFG3N9bPYk3q9Y566 jRKHteFj4atluEeD7mdiQZTWYpcNX9lexceOkMKLTwJs9k2wui4G4yGZ1jfk3iXv1jJ9 z9lJwOfGSRHBL/8kCpyA1A7vQNuMMEof8hHurWDvYySuqECxfbaqXCVIrcJ/cNDcxoRi x+Jg== 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=l+8MGGUKuFIMLXhm88FOQPa7EpRqvTnKJCHKciRdIz12Xr/UtkLAnABh6POmRmM8mi aV0bwn2D5vVCgr6JUdZZNdc68kOf49No8KbDSPVl2bOXnFSXlMv0HgCmCVDq9Fq8decl p80EoQqR6cBLFZkAbpVvyS99mIt8L5Hf/DNJ+fRjWu2QOXRqWxKb+n6M59fRdN6gS1wl FX6IkhopmAQtyjtWCAFLt3vDuqR1LYyocH+21O1dsch/cM/hS2RRDZlIuSXTClfiyIVb NV/00VYmqaP37biZQUhnEZMGEWS2RB/wcqFe3OfJYpQ+o50aSryc2l48VdM7ZS9ipTjM GWjw== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@chromium.org header.s=google header.b=h6wX7vCl; 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 g1-v6sor14171788plt.70.2018.05.31.17.43.42 for (Google Transport Security); Thu, 31 May 2018 17:43:42 -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=h6wX7vCl; 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=h6wX7vCl3cuVP20xVEgOA/HQ38ZC4+3oTu74VJiW9UJ97gDyDyDy/2Jil8Y//nKo+0 pAxA6lfAK0kNk0YlfYOgxiQHvj54kV5qY43kwZbxX77NcM/rva4u/ktHRal659fC4hrt K+8U9crqaII8n43O2Sz5LShcriRz5AFu4KAtU= X-Google-Smtp-Source: ADUXVKLq/Nf56qllHQ17NsDF/wxfU5IfYSsCDQ4YxwmUSlZ4i1U9KkzQsxvv9pApe8hIDkKpi7NGow== 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> 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 */