On RHEL 7 (GCC 4.8.5) we don't have __builtin_add_overflow and similar functions. They were first added in GCC 5. Provide a fallback path for these older compilers. The minimum GCC version we want to support (for the sake of FreeBSD) is 4.2. The fallback path uses the "typeof" and "statement expression" GCC extensions; those are available in gcc-4.2: - https://gcc.gnu.org/onlinedocs/gcc-4.2.4/gcc/Statement-Exprs.html - https://gcc.gnu.org/onlinedocs/gcc-4.2.4/gcc/Typeof.html The math and the macros were discussed in the following thread: - [Libguestfs] [PATCH nbdkit 2/2] common/include/checked-overflow.h: Provide fallback Message-Id: <20211115121417.1174272-2-rjones@redhat.com> https://listman.redhat.com/archives/libguestfs/2021-November/msg00177.html Part of the commit message, and the "configure.ac" hunk, were stolen from Rich's original patch, linked above. Signed-off-by: Laszlo Ersek <lersek@redhat.com> --- Notes: v2: > diff --git a/common/utils/test-checked-overflow.c b/common/utils/test-checked-overflow.c > index 2158950cff22..c2882e38b094 100644 > --- a/common/utils/test-checked-overflow.c > +++ b/common/utils/test-checked-overflow.c > @@ -153,11 +153,11 @@ main (void) > */ > overflow = MUL_OVERFLOW_FALLBACK (3u, 5u, &result.u8); > assert (!overflow); > - assert (result.u8 = 0xF); > + assert (result.u8 == 0xF); > > overflow = MUL_OVERFLOW_FALLBACK (result.u8, 17u, &result.u8); > assert (!overflow); > - assert (result.u8 = UINT8_MAX); > + assert (result.u8 == UINT8_MAX); > > overflow = MUL_OVERFLOW_FALLBACK (result.u8, 257u, &result.u16); > assert (!overflow); configure.ac | 6 + common/utils/Makefile.am | 8 +- common/include/checked-overflow.h | 160 ++++++++++++++++++++++-- common/utils/test-checked-overflow.c | 177 +++++++++++++++++++++++++++ 4 files changed, 337 insertions(+), 14 deletions(-) create mode 100644 common/utils/test-checked-overflow.c diff --git a/configure.ac b/configure.ac index 6092b6cc957f..e22fd01f535f 100644 --- a/configure.ac +++ b/configure.ac @@ -220,6 +220,12 @@ CFLAGS="$old_CFLAGS" AC_MSG_RESULT([$supports_std_c90]) AM_CONDITIONAL([CAN_TEST_ANSI_C], [test "x$supports_std_c90" = "xyes"]) +dnl Check for __builtin_*_overflow. We need the dummy parameters +dnl else detection doesn't work correctly for some reason. +AC_CHECK_DECLS([__builtin_add_overflow(int, int, int *), + __builtin_mul_overflow(int, int, int *)], + [], [], []) + dnl On Haiku we must use BSD-compatibility headers to get the endian dnl macros we use. AC_MSG_CHECKING(whether OS-dependent include paths are required) diff --git a/common/utils/Makefile.am b/common/utils/Makefile.am index 012a5c25a648..5218a6996b9a 100644 --- a/common/utils/Makefile.am +++ b/common/utils/Makefile.am @@ -94,8 +94,12 @@ windows-errors.c: windows-errors.txt # Unit tests. -TESTS = test-quotes test-vector -check_PROGRAMS = test-quotes test-vector +TESTS = test-checked-overflow test-quotes test-vector +check_PROGRAMS = test-checked-overflow test-quotes test-vector + +test_checked_overflow_SOURCES = test-checked-overflow.c +test_checked_overflow_CPPFLAGS = -I$(top_srcdir)/common/include +test_checked_overflow_CFLAGS = $(WARNINGS_CFLAGS) test_quotes_SOURCES = test-quotes.c quote.c utils.h test_quotes_CPPFLAGS = -I$(srcdir) diff --git a/common/include/checked-overflow.h b/common/include/checked-overflow.h index ddc4b487b488..7f52003692c7 100644 --- a/common/include/checked-overflow.h +++ b/common/include/checked-overflow.h @@ -30,13 +30,17 @@ * SUCH DAMAGE. */ -/* This header file defines functions for checking overflow in common - * integer arithmetic operations. +/* This header file defines macros and functions for checking overflow in + * common integer arithmetic operations. * - * It uses GCC/Clang built-ins: a possible future enhancement is to - * provide fallbacks in plain C or for other compilers. The only - * purpose of having a header file for this is to have a single place - * where we would extend this in future. + * The macros use: + * - the "statement expression" GCC extension, + * - the "typeof" GCC extension, + * - the __builtin_add_overflow() and __builtin_mul_overflow() GCC/Clang + * built-ins. + * + * If either built-in is unavailable, the corresponding macro replaces it with + * a call to an inline C function. */ #ifndef NBDKIT_CHECKED_OVERFLOW_H @@ -46,14 +50,146 @@ #error "this file may need to be ported to your compiler" #endif -/* Add two values. *r = a + b - * Returns true if overflow happened. +#include <stdbool.h> +#include <stdint.h> + +/* Add "a" and "b", both of (possibly different) unsigned integer types, and + * store the sum in "*r", which must also have some unsigned integer type. + * + * Each macro argument is evaluated exactly once, as long as it does not have + * variably modified type. + * + * The macro evaluates to "false" if "*r" can represent the mathematical sum. + * Otherwise, the macro evaluates to "true", and the low order bits of the + * mathematical sum are stored to "*r". + */ +#if HAVE_DECL___BUILTIN_ADD_OVERFLOW +#define ADD_OVERFLOW(a, b, r) ADD_OVERFLOW_BUILTIN((a), (b), (r)) +#else +#define ADD_OVERFLOW(a, b, r) ADD_OVERFLOW_FALLBACK((a), (b), (r)) +#endif + +/* Multiply "a" and "b", both of (possibly different) unsigned integer types, + * and store the product in "*r", which must also have some unsigned integer + * type. + * + * Each macro argument is evaluated exactly once, as long as it does not have + * variably modified type. + * + * The macro evaluates to "false" if "*r" can represent the mathematical + * product. Otherwise, the macro evaluates to "true", and the low order bits of + * the mathematical product are stored to "*r". + */ +#if HAVE_DECL___BUILTIN_MUL_OVERFLOW +#define MUL_OVERFLOW(a, b, r) MUL_OVERFLOW_BUILTIN((a), (b), (r)) +#else +#define MUL_OVERFLOW(a, b, r) MUL_OVERFLOW_FALLBACK((a), (b), (r)) +#endif + +/* The ADD_OVERFLOW_BUILTIN and MUL_OVERFLOW_BUILTIN function-like macros + * enforce the unsignedness of all their operands even though the underlying + * compiler built-ins, __builtin_add_overflow() and __builtin_mul_overflow(), + * don't depend on that. The explanation is that the fallback implementation + * does depend on the unsignedness of all operands, and the codebase should + * seamlessly build regardless of the built-in vs. fallback choice. + * + * Each macro argument is evaluated exactly once, as long as it does not have + * variably modified type. */ -#define ADD_OVERFLOW(a, b, r) __builtin_add_overflow((a), (b), (r)) +#if HAVE_DECL___BUILTIN_ADD_OVERFLOW +#define ADD_OVERFLOW_BUILTIN(a, b, r) \ + ({ \ + STATIC_ASSERT_UNSIGNED_INT (a); \ + STATIC_ASSERT_UNSIGNED_INT (b); \ + STATIC_ASSERT_UNSIGNED_INT (*(r)); \ + __builtin_add_overflow((a), (b), (r)); \ + }) +#endif + +#if HAVE_DECL___BUILTIN_MUL_OVERFLOW +#define MUL_OVERFLOW_BUILTIN(a, b, r) \ + ({ \ + STATIC_ASSERT_UNSIGNED_INT (a); \ + STATIC_ASSERT_UNSIGNED_INT (b); \ + STATIC_ASSERT_UNSIGNED_INT (*(r)); \ + __builtin_mul_overflow((a), (b), (r)); \ + }) +#endif -/* Multiply two values. *r = a * b - * Returns true if overflow happened. +/* The fallback macros call inline C functions. The unsignedness of all + * operands is enforced in order to keep the conversion to uintmax_t + * value-preserving, and to keep the conversion back from uintmax_t independent + * of the C language implementation. + * + * Each macro argument is evaluated exactly once, as long as it does not have + * variably modified type. + * + * The fallback macros and the inline C functions are defined regardless of + * HAVE_DECL___BUILTIN_ADD_OVERFLOW and HAVE_DECL___BUILTIN_MUL_OVERFLOW so + * that the test suite can always test the fallback. */ -#define MUL_OVERFLOW(a, b, r) __builtin_mul_overflow((a), (b), (r)) +#define ADD_OVERFLOW_FALLBACK(a, b, r) \ + ({ \ + bool overflow; \ + uintmax_t tmp; \ + \ + STATIC_ASSERT_UNSIGNED_INT (a); \ + STATIC_ASSERT_UNSIGNED_INT (b); \ + STATIC_ASSERT_UNSIGNED_INT (*(r)); \ + overflow = check_add_overflow ((a), (b), (typeof (*(r)))-1, &tmp); \ + *(r) = tmp; \ + overflow; \ + }) + +#define MUL_OVERFLOW_FALLBACK(a, b, r) \ + ({ \ + bool overflow; \ + uintmax_t tmp; \ + \ + STATIC_ASSERT_UNSIGNED_INT (a); \ + STATIC_ASSERT_UNSIGNED_INT (b); \ + STATIC_ASSERT_UNSIGNED_INT (*(r)); \ + overflow = check_mul_overflow ((a), (b), (typeof (*(r)))-1, &tmp); \ + *(r) = tmp; \ + overflow; \ + }) + +/* Assert, at compile time, that the expression "x" has some unsigned integer + * type. + * + * The expression "x" is not evaluated, unless it has variably modified type. + */ +#define STATIC_ASSERT_UNSIGNED_INT(x) \ + do { \ + typedef char x_has_uint_type[(typeof (x))-1 > 0 ? 1 : -1]; \ + } while (0) + +/* Assign the sum "a + b" to "*r", using uintmax_t modular arithmetic. + * + * Return true iff the addition overflows or the result exceeds "max". + */ +static inline bool +check_add_overflow (uintmax_t a, uintmax_t b, uintmax_t max, uintmax_t *r) +{ + bool in_range; + + *r = a + b; + in_range = a <= UINTMAX_MAX - b && *r <= max; + return !in_range; +} + +/* Assign the product "a * b" to "*r", using uintmax_t modular arithmetic. + * + * Return true iff the multiplication overflows or the result exceeds "max". + */ +static inline bool +check_mul_overflow (uintmax_t a, uintmax_t b, uintmax_t max, uintmax_t *r) +{ + bool in_range; + + *r = a * b; + in_range = b == 0 || a <= UINTMAX_MAX / b && *r <= max; + return !in_range; +} #endif /* NBDKIT_CHECKED_OVERFLOW_H */ diff --git a/common/utils/test-checked-overflow.c b/common/utils/test-checked-overflow.c new file mode 100644 index 000000000000..c2882e38b094 --- /dev/null +++ b/common/utils/test-checked-overflow.c @@ -0,0 +1,177 @@ +/* nbdkit + * Copyright (C) 2021 Red Hat Inc. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are + * met: + * + * * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * * Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * * Neither the name of Red Hat nor the names of its contributors may be + * used to endorse or promote products derived from this software without + * specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY RED HAT AND CONTRIBUTORS ''AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, + * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A + * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL RED HAT OR + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF + * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND + * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, + * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT + * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + */ + +#include <stddef.h> +#include <stdint.h> +#undef NDEBUG /* Keep test strong even for nbdkit built without assertions */ +#include <assert.h> + +#include "checked-overflow.h" + +#define TEST_ADD(a, b, result, expected_overflow, expected_result) \ + do { \ + bool overflow; \ + \ + overflow = ADD_OVERFLOW_FALLBACK ((a), (b), (result)); \ + assert (overflow == (expected_overflow)); \ + assert (*(result) == (expected_result)); \ + overflow = ADD_OVERFLOW_FALLBACK ((b), (a), (result)); \ + assert (overflow == (expected_overflow)); \ + assert (*(result) == (expected_result)); \ + } while (0) + +#define TEST_MUL(a, b, result, expected_overflow, expected_result) \ + do { \ + bool overflow; \ + \ + overflow = MUL_OVERFLOW_FALLBACK ((a), (b), (result)); \ + assert (overflow == (expected_overflow)); \ + assert (*(result) == (expected_result)); \ + overflow = MUL_OVERFLOW_FALLBACK ((b), (a), (result)); \ + assert (overflow == (expected_overflow)); \ + assert (*(result) == (expected_result)); \ + } while (0) + +/* Define these const-qualified objects because the UINTN_MAX object-like + * macros in <stdint.h> have "post integer promotion" types. Therefore, + * UINT16_MAX and UINT8_MAX most commonly have type "int". And that trips the + * signedness check in ADD_OVERFLOW_FALLBACK(). + */ +static const uintmax_t umax_max = UINTMAX_MAX; +static const uint64_t u64_max = UINT64_MAX; +static const uint32_t u32_max = UINT32_MAX; +static const uint16_t u16_max = UINT16_MAX; +static const uint8_t u8_max = UINT8_MAX; +static const size_t size_max = SIZE_MAX; + +int +main (void) +{ + union { + uintmax_t umax; + uint64_t u64; + uint32_t u32; + uint16_t u16; + uint8_t u8; + size_t sz; + } result; + bool overflow; + + /* "max + 0" and "0 + max" evaluate to "max", without overflow. */ + TEST_ADD (umax_max, 0u, &result.umax, false, umax_max); + TEST_ADD (u64_max, 0u, &result.u64, false, u64_max); + TEST_ADD (u32_max, 0u, &result.u32, false, u32_max); + TEST_ADD (u16_max, 0u, &result.u16, false, u16_max); + TEST_ADD (u8_max, 0u, &result.u8, false, u8_max); + TEST_ADD (size_max, 0u, &result.sz, false, size_max); + + /* "max + 1" and "1 + max" overflow to zero. */ + TEST_ADD (umax_max, 1u, &result.umax, true, 0); + TEST_ADD (u64_max, 1u, &result.u64, true, 0); + TEST_ADD (u32_max, 1u, &result.u32, true, 0); + TEST_ADD (u16_max, 1u, &result.u16, true, 0); + TEST_ADD (u8_max, 1u, &result.u8, true, 0); + TEST_ADD (size_max, 1u, &result.sz, true, 0); + + /* Adding umax_max (i.e., all-bits-one) amounts (with overflow) to + * subtracting one. + */ + TEST_ADD (umax_max, umax_max, &result.umax, true, umax_max - 1); + TEST_ADD (u64_max, umax_max, &result.u64, true, u64_max - 1); + TEST_ADD (u32_max, umax_max, &result.u32, true, u32_max - 1); + TEST_ADD (u16_max, umax_max, &result.u16, true, u16_max - 1); + TEST_ADD (u8_max, umax_max, &result.u8, true, u8_max - 1); + TEST_ADD (size_max, umax_max, &result.sz, true, size_max - 1); + + /* "max * 0" and "0 * max" evaluate to 0, without overflow. */ + TEST_MUL (umax_max, 0u, &result.umax, false, 0); + TEST_MUL (u64_max, 0u, &result.u64, false, 0); + TEST_MUL (u32_max, 0u, &result.u32, false, 0); + TEST_MUL (u16_max, 0u, &result.u16, false, 0); + TEST_MUL (u8_max, 0u, &result.u8, false, 0); + TEST_MUL (size_max, 0u, &result.sz, false, 0); + + /* "max * 1" and "1 * max" evaluate to "max", without overflow. */ + TEST_MUL (umax_max, 1u, &result.umax, false, umax_max); + TEST_MUL (u64_max, 1u, &result.u64, false, u64_max); + TEST_MUL (u32_max, 1u, &result.u32, false, u32_max); + TEST_MUL (u16_max, 1u, &result.u16, false, u16_max); + TEST_MUL (u8_max, 1u, &result.u8, false, u8_max); + TEST_MUL (size_max, 1u, &result.sz, false, size_max); + + /* "max * 2" and "2 * max" evaluate (with overflow) to "max - 1". */ + TEST_MUL (umax_max, 2u, &result.umax, true, umax_max - 1); + TEST_MUL (u64_max, 2u, &result.u64, true, u64_max - 1); + TEST_MUL (u32_max, 2u, &result.u32, true, u32_max - 1); + TEST_MUL (u16_max, 2u, &result.u16, true, u16_max - 1); + TEST_MUL (u8_max, 2u, &result.u8, true, u8_max - 1); + TEST_MUL (size_max, 2u, &result.sz, true, size_max - 1); + + /* factor 255 -> 3 5 17 + * factor 65535 -> 3 5 17 257 + * factor 4294967295 -> 3 5 17 257 65537 + * factor 18446744073709551615 -> 3 5 17 257 641 65537 6700417 + * + * Note: every time we double the width, we multiply the previous maximum + * 0xF...F with 0x10...01: + * + * 0xF (= 3 * 5) * 0x11 (= 17) = 0xFF + * 0xFF * 0x101 (= 257) = 0xFFFF + * 0xFFFF * 0x10001 (= 65537) = 0xFFFFFFFF + * 0xFFFFFFFF * 0x100000001 (= 641 * 6700417) = 0xFFFFFFFFFFFFFFFF + * + * Perform the above multiplications, advacing with prime factors. + */ + overflow = MUL_OVERFLOW_FALLBACK (3u, 5u, &result.u8); + assert (!overflow); + assert (result.u8 == 0xF); + + overflow = MUL_OVERFLOW_FALLBACK (result.u8, 17u, &result.u8); + assert (!overflow); + assert (result.u8 == UINT8_MAX); + + overflow = MUL_OVERFLOW_FALLBACK (result.u8, 257u, &result.u16); + assert (!overflow); + assert (result.u16 == UINT16_MAX); + + overflow = MUL_OVERFLOW_FALLBACK (result.u16, 65537ul, &result.u32); + assert (!overflow); + assert (result.u32 == UINT32_MAX); + + overflow = MUL_OVERFLOW_FALLBACK (result.u32, 641u, &result.u64); + assert (!overflow); + overflow = MUL_OVERFLOW_FALLBACK (result.u64, 6700417ul, &result.u64); + assert (!overflow); + assert (result.u64 == UINT64_MAX); + + return 0; +} -- 2.19.1.3.g30247aa5d201