1 /* SPDX-License-Identifier: GPL-2.0 OR MIT */ 2 #ifndef __LINUX_OVERFLOW_H 3 #define __LINUX_OVERFLOW_H 4 5 #include <linux/compiler.h> 6 #include <linux/limits.h> 7 8 /* 9 * In the fallback code below, we need to compute the minimum and 10 * maximum values representable in a given type. These macros may also 11 * be useful elsewhere, so we provide them outside the 12 * COMPILER_HAS_GENERIC_BUILTIN_OVERFLOW block. 13 * 14 * It would seem more obvious to do something like 15 * 16 * #define type_min(T) (T)(is_signed_type(T) ? (T)1 << (8*sizeof(T)-1) : 0) 17 * #define type_max(T) (T)(is_signed_type(T) ? ((T)1 << (8*sizeof(T)-1)) - 1 : ~(T)0) 18 * 19 * Unfortunately, the middle expressions, strictly speaking, have 20 * undefined behaviour, and at least some versions of gcc warn about 21 * the type_max expression (but not if -fsanitize=undefined is in 22 * effect; in that case, the warning is deferred to runtime...). 23 * 24 * The slightly excessive casting in type_min is to make sure the 25 * macros also produce sensible values for the exotic type _Bool. [The 26 * overflow checkers only almost work for _Bool, but that's 27 * a-feature-not-a-bug, since people shouldn't be doing arithmetic on 28 * _Bools. Besides, the gcc builtins don't allow _Bool* as third 29 * argument.] 30 * 31 * Idea stolen from 32 * https://mail-index.netbsd.org/tech-misc/2007/02/05/0000.html - 33 * credit to Christian Biere. 34 */ 35 #define is_signed_type(type) (((type)(-1)) < (type)1) 36 #define __type_half_max(type) ((type)1 << (8*sizeof(type) - 1 - is_signed_type(type))) 37 #define type_max(T) ((T)((__type_half_max(T) - 1) + __type_half_max(T))) 38 #define type_min(T) ((T)((T)-type_max(T)-(T)1)) 39 40 /* 41 * Avoids triggering -Wtype-limits compilation warning, 42 * while using unsigned data types to check a < 0. 43 */ 44 #define is_non_negative(a) ((a) > 0 || (a) == 0) 45 #define is_negative(a) (!(is_non_negative(a))) 46 47 /* 48 * Allows for effectively applying __must_check to a macro so we can have 49 * both the type-agnostic benefits of the macros while also being able to 50 * enforce that the return value is, in fact, checked. 51 */ __must_check_overflow(bool overflow)52 static inline bool __must_check __must_check_overflow(bool overflow) 53 { 54 return unlikely(overflow); 55 } 56 57 #ifdef COMPILER_HAS_GENERIC_BUILTIN_OVERFLOW 58 /* 59 * For simplicity and code hygiene, the fallback code below insists on 60 * a, b and *d having the same type (similar to the min() and max() 61 * macros), whereas gcc's type-generic overflow checkers accept 62 * different types. Hence we don't just make check_add_overflow an 63 * alias for __builtin_add_overflow, but add type checks similar to 64 * below. 65 */ 66 #define check_add_overflow(a, b, d) __must_check_overflow(({ \ 67 typeof(a) __a = (a); \ 68 typeof(b) __b = (b); \ 69 typeof(d) __d = (d); \ 70 (void) (&__a == &__b); \ 71 (void) (&__a == __d); \ 72 __builtin_add_overflow(__a, __b, __d); \ 73 })) 74 75 #define check_sub_overflow(a, b, d) __must_check_overflow(({ \ 76 typeof(a) __a = (a); \ 77 typeof(b) __b = (b); \ 78 typeof(d) __d = (d); \ 79 (void) (&__a == &__b); \ 80 (void) (&__a == __d); \ 81 __builtin_sub_overflow(__a, __b, __d); \ 82 })) 83 84 #define check_mul_overflow(a, b, d) __must_check_overflow(({ \ 85 typeof(a) __a = (a); \ 86 typeof(b) __b = (b); \ 87 typeof(d) __d = (d); \ 88 (void) (&__a == &__b); \ 89 (void) (&__a == __d); \ 90 __builtin_mul_overflow(__a, __b, __d); \ 91 })) 92 93 #else 94 95 96 /* Checking for unsigned overflow is relatively easy without causing UB. */ 97 #define __unsigned_add_overflow(a, b, d) ({ \ 98 typeof(a) __a = (a); \ 99 typeof(b) __b = (b); \ 100 typeof(d) __d = (d); \ 101 (void) (&__a == &__b); \ 102 (void) (&__a == __d); \ 103 *__d = __a + __b; \ 104 *__d < __a; \ 105 }) 106 #define __unsigned_sub_overflow(a, b, d) ({ \ 107 typeof(a) __a = (a); \ 108 typeof(b) __b = (b); \ 109 typeof(d) __d = (d); \ 110 (void) (&__a == &__b); \ 111 (void) (&__a == __d); \ 112 *__d = __a - __b; \ 113 __a < __b; \ 114 }) 115 /* 116 * If one of a or b is a compile-time constant, this avoids a division. 117 */ 118 #define __unsigned_mul_overflow(a, b, d) ({ \ 119 typeof(a) __a = (a); \ 120 typeof(b) __b = (b); \ 121 typeof(d) __d = (d); \ 122 (void) (&__a == &__b); \ 123 (void) (&__a == __d); \ 124 *__d = __a * __b; \ 125 __builtin_constant_p(__b) ? \ 126 __b > 0 && __a > type_max(typeof(__a)) / __b : \ 127 __a > 0 && __b > type_max(typeof(__b)) / __a; \ 128 }) 129 130 /* 131 * For signed types, detecting overflow is much harder, especially if 132 * we want to avoid UB. But the interface of these macros is such that 133 * we must provide a result in *d, and in fact we must produce the 134 * result promised by gcc's builtins, which is simply the possibly 135 * wrapped-around value. Fortunately, we can just formally do the 136 * operations in the widest relevant unsigned type (u64) and then 137 * truncate the result - gcc is smart enough to generate the same code 138 * with and without the (u64) casts. 139 */ 140 141 /* 142 * Adding two signed integers can overflow only if they have the same 143 * sign, and overflow has happened iff the result has the opposite 144 * sign. 145 */ 146 #define __signed_add_overflow(a, b, d) ({ \ 147 typeof(a) __a = (a); \ 148 typeof(b) __b = (b); \ 149 typeof(d) __d = (d); \ 150 (void) (&__a == &__b); \ 151 (void) (&__a == __d); \ 152 *__d = (u64)__a + (u64)__b; \ 153 (((~(__a ^ __b)) & (*__d ^ __a)) \ 154 & type_min(typeof(__a))) != 0; \ 155 }) 156 157 /* 158 * Subtraction is similar, except that overflow can now happen only 159 * when the signs are opposite. In this case, overflow has happened if 160 * the result has the opposite sign of a. 161 */ 162 #define __signed_sub_overflow(a, b, d) ({ \ 163 typeof(a) __a = (a); \ 164 typeof(b) __b = (b); \ 165 typeof(d) __d = (d); \ 166 (void) (&__a == &__b); \ 167 (void) (&__a == __d); \ 168 *__d = (u64)__a - (u64)__b; \ 169 ((((__a ^ __b)) & (*__d ^ __a)) \ 170 & type_min(typeof(__a))) != 0; \ 171 }) 172 173 /* 174 * Signed multiplication is rather hard. gcc always follows C99, so 175 * division is truncated towards 0. This means that we can write the 176 * overflow check like this: 177 * 178 * (a > 0 && (b > MAX/a || b < MIN/a)) || 179 * (a < -1 && (b > MIN/a || b < MAX/a) || 180 * (a == -1 && b == MIN) 181 * 182 * The redundant casts of -1 are to silence an annoying -Wtype-limits 183 * (included in -Wextra) warning: When the type is u8 or u16, the 184 * __b_c_e in check_mul_overflow obviously selects 185 * __unsigned_mul_overflow, but unfortunately gcc still parses this 186 * code and warns about the limited range of __b. 187 */ 188 189 #define __signed_mul_overflow(a, b, d) ({ \ 190 typeof(a) __a = (a); \ 191 typeof(b) __b = (b); \ 192 typeof(d) __d = (d); \ 193 typeof(a) __tmax = type_max(typeof(a)); \ 194 typeof(a) __tmin = type_min(typeof(a)); \ 195 (void) (&__a == &__b); \ 196 (void) (&__a == __d); \ 197 *__d = (u64)__a * (u64)__b; \ 198 (__b > 0 && (__a > __tmax/__b || __a < __tmin/__b)) || \ 199 (__b < (typeof(__b))-1 && (__a > __tmin/__b || __a < __tmax/__b)) || \ 200 (__b == (typeof(__b))-1 && __a == __tmin); \ 201 }) 202 203 204 #define check_add_overflow(a, b, d) __must_check_overflow( \ 205 __builtin_choose_expr(is_signed_type(typeof(a)), \ 206 __signed_add_overflow(a, b, d), \ 207 __unsigned_add_overflow(a, b, d))) 208 209 #define check_sub_overflow(a, b, d) __must_check_overflow( \ 210 __builtin_choose_expr(is_signed_type(typeof(a)), \ 211 __signed_sub_overflow(a, b, d), \ 212 __unsigned_sub_overflow(a, b, d))) 213 214 #define check_mul_overflow(a, b, d) __must_check_overflow( \ 215 __builtin_choose_expr(is_signed_type(typeof(a)), \ 216 __signed_mul_overflow(a, b, d), \ 217 __unsigned_mul_overflow(a, b, d))) 218 219 #endif /* COMPILER_HAS_GENERIC_BUILTIN_OVERFLOW */ 220 221 /** check_shl_overflow() - Calculate a left-shifted value and check overflow 222 * 223 * @a: Value to be shifted 224 * @s: How many bits left to shift 225 * @d: Pointer to where to store the result 226 * 227 * Computes *@d = (@a << @s) 228 * 229 * Returns true if '*d' cannot hold the result or when 'a << s' doesn't 230 * make sense. Example conditions: 231 * - 'a << s' causes bits to be lost when stored in *d. 232 * - 's' is garbage (e.g. negative) or so large that the result of 233 * 'a << s' is guaranteed to be 0. 234 * - 'a' is negative. 235 * - 'a << s' sets the sign bit, if any, in '*d'. 236 * 237 * '*d' will hold the results of the attempted shift, but is not 238 * considered "safe for use" if false is returned. 239 */ 240 #define check_shl_overflow(a, s, d) __must_check_overflow(({ \ 241 typeof(a) _a = a; \ 242 typeof(s) _s = s; \ 243 typeof(d) _d = d; \ 244 u64 _a_full = _a; \ 245 unsigned int _to_shift = \ 246 is_non_negative(_s) && _s < 8 * sizeof(*d) ? _s : 0; \ 247 *_d = (_a_full << _to_shift); \ 248 (_to_shift != _s || is_negative(*_d) || is_negative(_a) || \ 249 (*_d >> _to_shift) != _a); \ 250 })) 251 252 /** 253 * size_mul() - Calculate size_t multiplication with saturation at SIZE_MAX 254 * 255 * @factor1: first factor 256 * @factor2: second factor 257 * 258 * Returns: calculate @factor1 * @factor2, both promoted to size_t, 259 * with any overflow causing the return value to be SIZE_MAX. The 260 * lvalue must be size_t to avoid implicit type conversion. 261 */ size_mul(size_t factor1,size_t factor2)262 static inline size_t __must_check size_mul(size_t factor1, size_t factor2) 263 { 264 size_t bytes; 265 266 if (check_mul_overflow(factor1, factor2, &bytes)) 267 return SIZE_MAX; 268 269 return bytes; 270 } 271 272 /** 273 * size_add() - Calculate size_t addition with saturation at SIZE_MAX 274 * 275 * @addend1: first addend 276 * @addend2: second addend 277 * 278 * Returns: calculate @addend1 + @addend2, both promoted to size_t, 279 * with any overflow causing the return value to be SIZE_MAX. The 280 * lvalue must be size_t to avoid implicit type conversion. 281 */ size_add(size_t addend1,size_t addend2)282 static inline size_t __must_check size_add(size_t addend1, size_t addend2) 283 { 284 size_t bytes; 285 286 if (check_add_overflow(addend1, addend2, &bytes)) 287 return SIZE_MAX; 288 289 return bytes; 290 } 291 292 /** 293 * size_sub() - Calculate size_t subtraction with saturation at SIZE_MAX 294 * 295 * @minuend: value to subtract from 296 * @subtrahend: value to subtract from @minuend 297 * 298 * Returns: calculate @minuend - @subtrahend, both promoted to size_t, 299 * with any overflow causing the return value to be SIZE_MAX. For 300 * composition with the size_add() and size_mul() helpers, neither 301 * argument may be SIZE_MAX (or the result with be forced to SIZE_MAX). 302 * The lvalue must be size_t to avoid implicit type conversion. 303 */ size_sub(size_t minuend,size_t subtrahend)304 static inline size_t __must_check size_sub(size_t minuend, size_t subtrahend) 305 { 306 size_t bytes; 307 308 if (minuend == SIZE_MAX || subtrahend == SIZE_MAX || 309 check_sub_overflow(minuend, subtrahend, &bytes)) 310 return SIZE_MAX; 311 312 return bytes; 313 } 314 315 /** 316 * array_size() - Calculate size of 2-dimensional array. 317 * 318 * @a: dimension one 319 * @b: dimension two 320 * 321 * Calculates size of 2-dimensional array: @a * @b. 322 * 323 * Returns: number of bytes needed to represent the array or SIZE_MAX on 324 * overflow. 325 */ 326 #define array_size(a, b) size_mul(a, b) 327 328 /** 329 * array3_size() - Calculate size of 3-dimensional array. 330 * 331 * @a: dimension one 332 * @b: dimension two 333 * @c: dimension three 334 * 335 * Calculates size of 3-dimensional array: @a * @b * @c. 336 * 337 * Returns: number of bytes needed to represent the array or SIZE_MAX on 338 * overflow. 339 */ 340 #define array3_size(a, b, c) size_mul(size_mul(a, b), c) 341 342 /** 343 * flex_array_size() - Calculate size of a flexible array member 344 * within an enclosing structure. 345 * 346 * @p: Pointer to the structure. 347 * @member: Name of the flexible array member. 348 * @count: Number of elements in the array. 349 * 350 * Calculates size of a flexible array of @count number of @member 351 * elements, at the end of structure @p. 352 * 353 * Return: number of bytes needed or SIZE_MAX on overflow. 354 */ 355 #define flex_array_size(p, member, count) \ 356 size_mul(count, \ 357 sizeof(*(p)->member) + __must_be_array((p)->member)) 358 359 /** 360 * struct_size() - Calculate size of structure with trailing flexible array. 361 * 362 * @p: Pointer to the structure. 363 * @member: Name of the array member. 364 * @count: Number of elements in the array. 365 * 366 * Calculates size of memory needed for structure @p followed by an 367 * array of @count number of @member elements. 368 * 369 * Return: number of bytes needed or SIZE_MAX on overflow. 370 */ 371 #define struct_size(p, member, count) \ 372 size_add(sizeof(*(p)), flex_array_size(p, member, count)) 373 374 #endif /* __LINUX_OVERFLOW_H */ 375