Laszlo Ersek
2021-Nov-25 14:34 UTC
[Libguestfs] [nbdkit PATCH 0/2] common/include/checked-overflow: provide fallback
The second patch is the relevant one; the first patch is just a small tweak to an existent ADD_OVERFLOW() invocation in "common/utils/vector.c" -- because we'll need to pass unsigned arguments to ADD_OVERFLOW() (and MUL_OVERFLOW()) going forward. Thanks, Laszlo Laszlo Ersek (2): utils/vector: pass only unsigned arguments to (ADD|MUL)_OVERFLOW common/include/checked-overflow: provide fallback common/include/checked-overflow.h | 160 ++++++++++++++++++++++-- common/utils/Makefile.am | 8 +- common/utils/test-checked-overflow.c | 177 +++++++++++++++++++++++++++ common/utils/vector.c | 2 +- configure.ac | 6 + 5 files changed, 338 insertions(+), 15 deletions(-) create mode 100644 common/utils/test-checked-overflow.c base-commit: b9a2c12da886decf662f4e2bbcd1699a200676aa -- 2.19.1.3.g30247aa5d201
Laszlo Ersek
2021-Nov-25 14:34 UTC
[Libguestfs] [nbdkit PATCH 1/2] utils/vector: pass only unsigned arguments to (ADD|MUL)_OVERFLOW
In a subsequent patch, the (ADD|MUL)_OVERFLOW macros will require each
operand to have some unsigned integer type. To prevent a build failure in
"common/utils/vector.c", satisfy that requirement in advance.
Signed-off-by: Laszlo Ersek <lersek at redhat.com>
---
common/utils/vector.c | 2 +-
1 file changed, 1 insertion(+), 1 deletion(-)
diff --git a/common/utils/vector.c b/common/utils/vector.c
index ee7591560ca5..54e6b810bea6 100644
--- a/common/utils/vector.c
+++ b/common/utils/vector.c
@@ -60,7 +60,7 @@ generic_vector_reserve (struct generic_vector *v, size_t n,
size_t itemsize)
* newcap = v->cap + (v->cap + 1) / 2
* newbytes = newcap * itemsize
*/
- if (ADD_OVERFLOW (v->cap, 1, &t) ||
+ if (ADD_OVERFLOW (v->cap, 1u, &t) ||
ADD_OVERFLOW (v->cap, t/2, &newcap) ||
MUL_OVERFLOW (newcap, itemsize, &newbytes) ||
newbytes < reqbytes) {
--
2.19.1.3.g30247aa5d201
Laszlo Ersek
2021-Nov-25 14:34 UTC
[Libguestfs] [nbdkit PATCH 2/2] common/include/checked-overflow: provide fallback
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 at 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 at redhat.com>
---
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..2158950cff22
--- /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
Laszlo Ersek
2021-Nov-25 14:39 UTC
[Libguestfs] [nbdkit PATCH 0/2] common/include/checked-overflow: provide fallback
On 11/25/21 15:34, Laszlo Ersek wrote:> The second patch is the relevant one; the first patch is just a small > tweak to an existent ADD_OVERFLOW() invocation in > "common/utils/vector.c" -- because we'll need to pass unsigned arguments > to ADD_OVERFLOW() (and MUL_OVERFLOW()) going forward. > > Thanks, > Laszlo > > Laszlo Ersek (2): > utils/vector: pass only unsigned arguments to (ADD|MUL)_OVERFLOW > common/include/checked-overflow: provide fallback > > common/include/checked-overflow.h | 160 ++++++++++++++++++++++-- > common/utils/Makefile.am | 8 +- > common/utils/test-checked-overflow.c | 177 +++++++++++++++++++++++++++ > common/utils/vector.c | 2 +- > configure.ac | 6 + > 5 files changed, 338 insertions(+), 15 deletions(-) > create mode 100644 common/utils/test-checked-overflow.c > > > base-commit: b9a2c12da886decf662f4e2bbcd1699a200676aa >Sigh, ignore this. I'll send v2 soon. The issue in this version that my OCaml studies have (apparently) confused me about "=" vs. "==", and now I've done the unthinkable in this series, in some asserts :( (I used to prefer Yoda conditionals, that is (2 == a) rather than (a =2), because the former turns (2 = a) into a compilation failure. But most developers dislike Yoda conditionals, so I stopped using them.) Sorry, Laszlo