From patchwork Wed May 9 00:42:17 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Kees Cook X-Patchwork-Id: 10387833 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 9BEC16055A for ; Wed, 9 May 2018 00:45:38 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 6FB55287AE for ; Wed, 9 May 2018 00:45:38 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id D57D329164; Wed, 9 May 2018 00:44:33 +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 C5D062943F for ; Wed, 9 May 2018 00:42:56 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 17BC56B02F4; Tue, 8 May 2018 20:42:46 -0400 (EDT) Delivered-To: linux-mm-outgoing@kvack.org Received: by kanga.kvack.org (Postfix, from userid 40) id 1029D6B02F3; Tue, 8 May 2018 20:42:46 -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 EBF026B02F4; Tue, 8 May 2018 20:42:45 -0400 (EDT) X-Original-To: linux-mm@kvack.org X-Delivered-To: linux-mm@kvack.org Received: from mail-pg0-f72.google.com (mail-pg0-f72.google.com [74.125.83.72]) by kanga.kvack.org (Postfix) with ESMTP id A39A36B02F2 for ; Tue, 8 May 2018 20:42:45 -0400 (EDT) Received: by mail-pg0-f72.google.com with SMTP id a9-v6so19002853pgt.6 for ; Tue, 08 May 2018 17:42:45 -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=qQjv/tgJdV/JPLB+j9JKZkAo/wcLTMci6/mu/LDMSc69BfqgcHl91TCrMog/W/hJzE DoDEcOpw9yv+yRLxGOljRLLqz3zIJpyqwKZ8+9XUu2cgf7Zzy6v9XRIIpNoI10VHEO3s FMleeyYixvjQXm0+rmYJSjsq/T5oBgPI2QQ83vujWHIs7TyHnhuMbGvEVjcqd1COkZyJ /AD7ReyaBvohU1pMyfCBk2e25puugM6T/Olk750r/gWOSuxJyq2OCKCH/+3u6ExteIQa YOcKD7EpzGJqtwGFYYNAzmxSKA+QT/P54Keeb1E52tm5dae6wrKYVf5H6eKfho8FFTcm JzbA== X-Gm-Message-State: ALQs6tDkaVpn0rklbvF7PGUVtPdooy/QgVOqRTlSOEZg2Ni+eXK8qtFd s13eparrxRiW5zLKwyqS7BixyZK2ftEl4Co8bg1QwyQMpKjSw+lXYfm+ucoqt5ce1vTPOdk4h0f TqS+vK6sByRkJCWY3ekelJYV7+jfIaWdD8T5vPaCpwiW916B26DhGomT7Mo8wLzhtlabxuigz9c V2FhuG89NVVEe9/Q/rY+J9Ot1qCoeNAPtmadcn8F2TlhNwu92JzxhxYefYMAJcCjkqTFgAA63+R /uL2U0V/bd2wQs/hmrXP/rpyd5IYDGaXAb7I7UMxCCl8XDWhHWetv0l8uFj6zA9kSS+fm5nBRx0 UnLYAtLx6nwa+NNv0+TyIxvKcrqzaXBZCBwKPEpzwOgy67pLMbo+ydTrpEOH7LHcSCFEO7d/9jy h X-Received: by 2002:a17:902:3a5:: with SMTP id d34-v6mr44134430pld.103.1525826565327; Tue, 08 May 2018 17:42:45 -0700 (PDT) X-Received: by 2002:a17:902:3a5:: with SMTP id d34-v6mr44134391pld.103.1525826564184; Tue, 08 May 2018 17:42:44 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1525826564; cv=none; d=google.com; s=arc-20160816; b=so+/95XMiTzXh+qlr6Yg70FFCwIKYVhs37cPNGTR9W/iRp3jHwNm3XQD2fvSSeN0oH Te+XBNgiY1gM/+gJ6QHUuzAGSCOVsimFIecmpzPs12y/hezQ/KI+NnnWQH6J4sTSfIvF Ihv+lAVmUXixmpY4HNh9I136UJ6u17Pbs/TJPh64DfX1lY5UeOtxUiLoxu7QnyP3cytE gZwvJRm4236ZKNPYXXgDleNGgBQCWfk/l4MPG06jhrdiwjlmwQLPCVlCkYAG1VnVh0t/ vFF2LtWcKvDSo/bX7iqA064+Al9I9RE2Bx6Dgp6FrFaHYe8X7MEZwKqXTdT+LDzAAxTj cEuA== 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=m3hmoIZP30QedTjHF6bTKgTGoJiC8d5FaMMsdOxLHa7BQ7hhVTDoHMtvyzlPYQ65nC SaoIaGMRJT2KchPaHO+t97zITrWN4qxZ0aShzPIy/O9UEYreSWsKD2x8tccjAV/NUGsP dkDR+wHHG3K/Uik//qvTEyaWg37voKKYjDLBHQVS+LKGZSLNZmENkxwtYWOvE9y1i8Z7 rSRIqwMd1Veie5VBW4DJ3bKtA3OO6pJEo7z1XfTWVzeO/VOYAFqEHEK1uRdpyIb00/Hq mGr9cKE4bcnFOtASDWy/ou2L0KS1oCsxUTeKyPmpzNlmcP1t/QfAzqL/82YkFxb4psRc qhgg== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@chromium.org header.s=google header.b=hPQfQGHc; 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 k8-v6sor9719314plt.57.2018.05.08.17.42.44 for (Google Transport Security); Tue, 08 May 2018 17:42:44 -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=hPQfQGHc; 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=hPQfQGHcxgP13HB3EI5Ar/TIBrLveo3g20G4zFsF/R6jPp+KRI19o4Z8DAQ5SGAEIE XjnQ5jElN2+0ydCrdxenqVzPSIjNZxI+7xeyFNEhhqtsRtk33ehSMnMe7+Li8Y4D+pz6 3CIDPAcEp8bA6JSHSM4eHVLpoz5kGrTUQ45Rs= X-Google-Smtp-Source: AB8JxZqwIk2c6Q5u1UvxlkrUWyf7XLtTsCcAhQynOJcJQYjNOsl7HWS0aOtr4GuzrRlFtFgNY1MxoQ== X-Received: by 2002:a17:902:3281:: with SMTP id z1-v6mr42817245plb.226.1525826563687; Tue, 08 May 2018 17:42:43 -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 z25sm19573388pfi.171.2018.05.08.17.42.38 (version=TLS1_2 cipher=ECDHE-RSA-CHACHA20-POLY1305 bits=256/256); Tue, 08 May 2018 17:42:39 -0700 (PDT) From: Kees Cook To: Matthew Wilcox Cc: Kees Cook , Rasmus Villemoes , linux-kernel@vger.kernel.org, linux-mm@kvack.org, kernel-hardening@lists.openwall.com Subject: [PATCH 01/13] compiler.h: enable builtin overflow checkers and add fallback code Date: Tue, 8 May 2018 17:42:17 -0700 Message-Id: <20180509004229.36341-2-keescook@chromium.org> X-Mailer: git-send-email 2.17.0 In-Reply-To: <20180509004229.36341-1-keescook@chromium.org> References: <20180509004229.36341-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 */