common/include/checked-overflow.h

   1 /* nbdkit
   2  * Copyright Red Hat
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions are
   6  * met:
   7  *
   8  * * Redistributions of source code must retain the above copyright
   9  * notice, this list of conditions and the following disclaimer.
  10  *
  11  * * Redistributions in binary form must reproduce the above copyright
  12  * notice, this list of conditions and the following disclaimer in the
  13  * documentation and/or other materials provided with the distribution.
  14  *
  15  * * Neither the name of Red Hat nor the names of its contributors may be
  16  * used to endorse or promote products derived from this software without
  17  * specific prior written permission.
  18  *
  19  * THIS SOFTWARE IS PROVIDED BY RED HAT AND CONTRIBUTORS ''AS IS'' AND
  20  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
  21  * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
  22  * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL RED HAT OR
  23  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  24  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  25  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
  26  * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
  27  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  28  * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
  29  * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  30  * SUCH DAMAGE.
  31  */
  32
  33 /* This header file defines macros and functions for checking overflow in
  34  * common integer arithmetic operations.
  35  *
  36  * The macros use:
  37  * - the "statement expression" GCC extension,
  38  * - the "typeof" GCC extension,
  39  * - the __builtin_add_overflow() and __builtin_mul_overflow() GCC/Clang
  40  *   built-ins.
  41  *
  42  * If either built-in is unavailable, the corresponding macro replaces it with
  43  * a call to an inline C function.
  44  */
  45
  46 #ifndef NBDKIT_CHECKED_OVERFLOW_H
  47 #define NBDKIT_CHECKED_OVERFLOW_H
  48
  49 #if !defined (__GNUC__) && !defined (__clang__)
  50 #error "this file may need to be ported to your compiler"
  51 #endif
  52
  53 #include <stdbool.h>
  54 #include <stdint.h>
  55
  56 #include "static-assert.h"
  57 #include "unique-name.h"
  58
  59 /* Add "a" and "b", both of (possibly different) unsigned integer types, and
  60  * store the sum in "*r", which must also have some unsigned integer type.
  61  *
  62  * Each macro argument is evaluated exactly once, as long as it does not have
  63  * variably modified type.
  64  *
  65  * The macro evaluates to "false" if "*r" can represent the mathematical sum.
  66  * Otherwise, the macro evaluates to "true", and the low order bits of the
  67  * mathematical sum are stored to "*r".
  68  */
  69 #if HAVE_DECL___BUILTIN_ADD_OVERFLOW
  70 #define ADD_OVERFLOW(a, b, r) ADD_OVERFLOW_BUILTIN ((a), (b), (r))
  71 #else
  72 #define ADD_OVERFLOW(a, b, r) ADD_OVERFLOW_FALLBACK ((a), (b), (r))
  73 #endif
  74
  75 /* Multiply "a" and "b", both of (possibly different) unsigned integer types,
  76  * and store the product in "*r", which must also have some unsigned integer
  77  * type.
  78  *
  79  * Each macro argument is evaluated exactly once, as long as it does not have
  80  * variably modified type.
  81  *
  82  * The macro evaluates to "false" if "*r" can represent the mathematical
  83  * product. Otherwise, the macro evaluates to "true", and the low order bits of
  84  * the mathematical product are stored to "*r".
  85  */
  86 #if HAVE_DECL___BUILTIN_MUL_OVERFLOW
  87 #define MUL_OVERFLOW(a, b, r) MUL_OVERFLOW_BUILTIN ((a), (b), (r))
  88 #else
  89 #define MUL_OVERFLOW(a, b, r) MUL_OVERFLOW_FALLBACK ((a), (b), (r))
  90 #endif
  91
  92 /* The ADD_OVERFLOW_BUILTIN and MUL_OVERFLOW_BUILTIN function-like macros
  93  * enforce the unsignedness of all their operands even though the underlying
  94  * compiler built-ins, __builtin_add_overflow() and __builtin_mul_overflow(),
  95  * don't depend on that. The explanation is that the fallback implementation
  96  * does depend on the unsignedness of all operands, and the codebase should
  97  * seamlessly build regardless of the built-in vs. fallback choice.
  98  *
  99  * Each macro argument is evaluated exactly once, as long as it does not have
 100  * variably modified type.
 101  */
 102 #if HAVE_DECL___BUILTIN_ADD_OVERFLOW
 103 #define ADD_OVERFLOW_BUILTIN(a, b, r)       \
 104   ({                                        \
 105     STATIC_ASSERT_UNSIGNED_INT (a);         \
 106     STATIC_ASSERT_UNSIGNED_INT (b);         \
 107     STATIC_ASSERT_UNSIGNED_INT (*(r));      \
 108     __builtin_add_overflow ((a), (b), (r)); \
 109   })
 110 #endif
 111
 112 #if HAVE_DECL___BUILTIN_MUL_OVERFLOW
 113 #define MUL_OVERFLOW_BUILTIN(a, b, r)       \
 114   ({                                        \
 115     STATIC_ASSERT_UNSIGNED_INT (a);         \
 116     STATIC_ASSERT_UNSIGNED_INT (b);         \
 117     STATIC_ASSERT_UNSIGNED_INT (*(r));      \
 118     __builtin_mul_overflow ((a), (b), (r)); \
 119   })
 120 #endif
 121
 122 /* The fallback macros call inline C functions. The unsignedness of all
 123  * operands is enforced in order to keep the conversion to uintmax_t
 124  * value-preserving, and to keep the conversion back from uintmax_t independent
 125  * of the C language implementation.
 126  *
 127  * Each macro argument is evaluated exactly once, as long as it does not have
 128  * variably modified type.
 129  *
 130  * The fallback macros and the inline C functions are defined regardless of
 131  * HAVE_DECL___BUILTIN_ADD_OVERFLOW and HAVE_DECL___BUILTIN_MUL_OVERFLOW so
 132  * that the test suite can always test the fallback.
 133  */
 134 #define ADD_OVERFLOW_FALLBACK(a, b, r)                                \
 135   ADD_OVERFLOW_FALLBACK_1 ((a), (b), (r),                             \
 136                            NBDKIT_UNIQUE_NAME (_overflow),            \
 137                            NBDKIT_UNIQUE_NAME (_tmp))
 138 #define ADD_OVERFLOW_FALLBACK_1(a, b, r, overflow, tmp)               \
 139   ({                                                                  \
 140     bool overflow;                                                    \
 141     uintmax_t tmp;                                                    \
 142                                                                       \
 143     STATIC_ASSERT_UNSIGNED_INT (a);                                   \
 144     STATIC_ASSERT_UNSIGNED_INT (b);                                   \
 145     STATIC_ASSERT_UNSIGNED_INT (*(r));                                \
 146     overflow = check_add_overflow ((a), (b),                          \
 147                                    (typeof (*(r)))-1,                 \
 148                                    &tmp);                             \
 149     *(r) = tmp;                                                       \
 150     overflow;                                                         \
 151   })
 152
 153 #define MUL_OVERFLOW_FALLBACK(a, b, r)                                \
 154   MUL_OVERFLOW_FALLBACK_1 ((a), (b), (r),                             \
 155                            NBDKIT_UNIQUE_NAME (_overflow),            \
 156                            NBDKIT_UNIQUE_NAME (_tmp))
 157 #define MUL_OVERFLOW_FALLBACK_1(a, b, r, overflow, tmp)               \
 158   ({                                                                  \
 159     bool overflow;                                                    \
 160     uintmax_t tmp;                                                    \
 161                                                                       \
 162     STATIC_ASSERT_UNSIGNED_INT (a);                                   \
 163     STATIC_ASSERT_UNSIGNED_INT (b);                                   \
 164     STATIC_ASSERT_UNSIGNED_INT (*(r));                                \
 165     overflow = check_mul_overflow ((a), (b),                          \
 166                                    (typeof (*(r)))-1,                 \
 167                                    &tmp);                             \
 168     *(r) = tmp;                                                       \
 169     overflow;                                                         \
 170   })
 171
 172 /* Assert, at compile time, that the expression "x" has some unsigned integer
 173  * type.
 174  *
 175  * The expression "x" is not evaluated, unless it has variably modified type.
 176  */
 177 #define STATIC_ASSERT_UNSIGNED_INT(x) \
 178   STATIC_ASSERT ((typeof (x))-1 > 0, _x_has_uint_type)
 179
 180 /* Assign the sum "a + b" to "*r", using uintmax_t modular arithmetic.
 181  *
 182  * Return true iff the addition overflows or the result exceeds "max".
 183  */
 184 static inline bool
 185 check_add_overflow (uintmax_t a, uintmax_t b, uintmax_t max, uintmax_t *r)
 186 {
 187   bool in_range;
 188
 189   *r = a + b;
 190   in_range = a <= UINTMAX_MAX - b && *r <= max;
 191   return !in_range;
 192 }
 193
 194 /* Assign the product "a * b" to "*r", using uintmax_t modular arithmetic.
 195  *
 196  * Return true iff the multiplication overflows or the result exceeds "max".
 197  */
 198 static inline bool
 199 check_mul_overflow (uintmax_t a, uintmax_t b, uintmax_t max, uintmax_t *r)
 200 {
 201   bool in_range;
 202
 203   *r = a * b;
 204   in_range = b == 0 || (a <= UINTMAX_MAX / b && *r <= max);
 205   return !in_range;
 206 }
 207
 208 #endif /* NBDKIT_CHECKED_OVERFLOW_H */