1 /* SPDX-License-Identifier: GPL-2.0 OR MIT */ 2 #ifndef _LINUXKPI_LINUX_OVERFLOW_H 3 #define _LINUXKPI_LINUX_OVERFLOW_H 4 5 #include <linux/compiler.h> 6 #include <linux/limits.h> 7 #ifdef __linux__ 8 #include <linux/const.h> 9 #endif 10 11 /* 12 * We need to compute the minimum and maximum values representable in a given 13 * type. These macros may also be useful elsewhere. It would seem more obvious 14 * 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 __type_half_max(type) ((type)1 << (8*sizeof(type) - 1 - is_signed_type(type))) 36 #define __type_max(T) ((T)((__type_half_max(T) - 1) + __type_half_max(T))) 37 #define type_max(t) __type_max(typeof(t)) 38 #define __type_min(T) ((T)((T)-type_max(T)-(T)1)) 39 #define type_min(t) __type_min(typeof(t)) 40 41 /* 42 * Avoids triggering -Wtype-limits compilation warning, 43 * while using unsigned data types to check a < 0. 44 */ 45 #define is_non_negative(a) ((a) > 0 || (a) == 0) 46 #define is_negative(a) (!(is_non_negative(a))) 47 48 /* 49 * Allows for effectively applying __must_check to a macro so we can have 50 * both the type-agnostic benefits of the macros while also being able to 51 * enforce that the return value is, in fact, checked. 52 */ 53 static inline bool __must_check __must_check_overflow(bool overflow) 54 { 55 return unlikely(overflow); 56 } 57 58 /** 59 * check_add_overflow() - Calculate addition with overflow checking 60 * @a: first addend 61 * @b: second addend 62 * @d: pointer to store sum 63 * 64 * Returns true on wrap-around, false otherwise. 65 * 66 * *@d holds the results of the attempted addition, regardless of whether 67 * wrap-around occurred. 68 */ 69 #define check_add_overflow(a, b, d) \ 70 __must_check_overflow(__builtin_add_overflow(a, b, d)) 71 72 /** 73 * wrapping_add() - Intentionally perform a wrapping addition 74 * @type: type for result of calculation 75 * @a: first addend 76 * @b: second addend 77 * 78 * Return the potentially wrapped-around addition without 79 * tripping any wrap-around sanitizers that may be enabled. 80 */ 81 #define wrapping_add(type, a, b) \ 82 ({ \ 83 type __val; \ 84 __builtin_add_overflow(a, b, &__val); \ 85 __val; \ 86 }) 87 88 /** 89 * wrapping_assign_add() - Intentionally perform a wrapping increment assignment 90 * @var: variable to be incremented 91 * @offset: amount to add 92 * 93 * Increments @var by @offset with wrap-around. Returns the resulting 94 * value of @var. Will not trip any wrap-around sanitizers. 95 * 96 * Returns the new value of @var. 97 */ 98 #define wrapping_assign_add(var, offset) \ 99 ({ \ 100 typeof(var) *__ptr = &(var); \ 101 *__ptr = wrapping_add(typeof(var), *__ptr, offset); \ 102 }) 103 104 /** 105 * check_sub_overflow() - Calculate subtraction with overflow checking 106 * @a: minuend; value to subtract from 107 * @b: subtrahend; value to subtract from @a 108 * @d: pointer to store difference 109 * 110 * Returns true on wrap-around, false otherwise. 111 * 112 * *@d holds the results of the attempted subtraction, regardless of whether 113 * wrap-around occurred. 114 */ 115 #define check_sub_overflow(a, b, d) \ 116 __must_check_overflow(__builtin_sub_overflow(a, b, d)) 117 118 /** 119 * wrapping_sub() - Intentionally perform a wrapping subtraction 120 * @type: type for result of calculation 121 * @a: minuend; value to subtract from 122 * @b: subtrahend; value to subtract from @a 123 * 124 * Return the potentially wrapped-around subtraction without 125 * tripping any wrap-around sanitizers that may be enabled. 126 */ 127 #define wrapping_sub(type, a, b) \ 128 ({ \ 129 type __val; \ 130 __builtin_sub_overflow(a, b, &__val); \ 131 __val; \ 132 }) 133 134 /** 135 * wrapping_assign_sub() - Intentionally perform a wrapping decrement assign 136 * @var: variable to be decremented 137 * @offset: amount to subtract 138 * 139 * Decrements @var by @offset with wrap-around. Returns the resulting 140 * value of @var. Will not trip any wrap-around sanitizers. 141 * 142 * Returns the new value of @var. 143 */ 144 #define wrapping_assign_sub(var, offset) \ 145 ({ \ 146 typeof(var) *__ptr = &(var); \ 147 *__ptr = wrapping_sub(typeof(var), *__ptr, offset); \ 148 }) 149 150 /** 151 * check_mul_overflow() - Calculate multiplication with overflow checking 152 * @a: first factor 153 * @b: second factor 154 * @d: pointer to store product 155 * 156 * Returns true on wrap-around, false otherwise. 157 * 158 * *@d holds the results of the attempted multiplication, regardless of whether 159 * wrap-around occurred. 160 */ 161 #define check_mul_overflow(a, b, d) \ 162 __must_check_overflow(__builtin_mul_overflow(a, b, d)) 163 164 /** 165 * wrapping_mul() - Intentionally perform a wrapping multiplication 166 * @type: type for result of calculation 167 * @a: first factor 168 * @b: second factor 169 * 170 * Return the potentially wrapped-around multiplication without 171 * tripping any wrap-around sanitizers that may be enabled. 172 */ 173 #define wrapping_mul(type, a, b) \ 174 ({ \ 175 type __val; \ 176 __builtin_mul_overflow(a, b, &__val); \ 177 __val; \ 178 }) 179 180 /** 181 * check_shl_overflow() - Calculate a left-shifted value and check overflow 182 * @a: Value to be shifted 183 * @s: How many bits left to shift 184 * @d: Pointer to where to store the result 185 * 186 * Computes *@d = (@a << @s) 187 * 188 * Returns true if '*@d' cannot hold the result or when '@a << @s' doesn't 189 * make sense. Example conditions: 190 * 191 * - '@a << @s' causes bits to be lost when stored in *@d. 192 * - '@s' is garbage (e.g. negative) or so large that the result of 193 * '@a << @s' is guaranteed to be 0. 194 * - '@a' is negative. 195 * - '@a << @s' sets the sign bit, if any, in '*@d'. 196 * 197 * '*@d' will hold the results of the attempted shift, but is not 198 * considered "safe for use" if true is returned. 199 */ 200 #define check_shl_overflow(a, s, d) __must_check_overflow(({ \ 201 typeof(a) _a = a; \ 202 typeof(s) _s = s; \ 203 typeof(d) _d = d; \ 204 unsigned long long _a_full = _a; \ 205 unsigned int _to_shift = \ 206 is_non_negative(_s) && _s < 8 * sizeof(*d) ? _s : 0; \ 207 *_d = (_a_full << _to_shift); \ 208 (_to_shift != _s || is_negative(*_d) || is_negative(_a) || \ 209 (*_d >> _to_shift) != _a); \ 210 })) 211 212 #define __overflows_type_constexpr(x, T) ( \ 213 is_unsigned_type(typeof(x)) ? \ 214 (x) > type_max(T) : \ 215 is_unsigned_type(typeof(T)) ? \ 216 (x) < 0 || (x) > type_max(T) : \ 217 (x) < type_min(T) || (x) > type_max(T)) 218 219 #define __overflows_type(x, T) ({ \ 220 typeof(T) v = 0; \ 221 check_add_overflow((x), v, &v); \ 222 }) 223 224 /** 225 * overflows_type - helper for checking the overflows between value, variables, 226 * or data type 227 * 228 * @n: source constant value or variable to be checked 229 * @T: destination variable or data type proposed to store @x 230 * 231 * Compares the @x expression for whether or not it can safely fit in 232 * the storage of the type in @T. @x and @T can have different types. 233 * If @x is a constant expression, this will also resolve to a constant 234 * expression. 235 * 236 * Returns: true if overflow can occur, false otherwise. 237 */ 238 #define overflows_type(n, T) \ 239 __builtin_choose_expr(__is_constexpr(n), \ 240 __overflows_type_constexpr(n, T), \ 241 __overflows_type(n, T)) 242 243 /** 244 * castable_to_type - like __same_type(), but also allows for casted literals 245 * 246 * @n: variable or constant value 247 * @T: variable or data type 248 * 249 * Unlike the __same_type() macro, this allows a constant value as the 250 * first argument. If this value would not overflow into an assignment 251 * of the second argument's type, it returns true. Otherwise, this falls 252 * back to __same_type(). 253 */ 254 #define castable_to_type(n, T) \ 255 __builtin_choose_expr(__is_constexpr(n), \ 256 !__overflows_type_constexpr(n, T), \ 257 __same_type(n, T)) 258 259 /** 260 * size_mul() - Calculate size_t multiplication with saturation at SIZE_MAX 261 * @factor1: first factor 262 * @factor2: second factor 263 * 264 * Returns: calculate @factor1 * @factor2, both promoted to size_t, 265 * with any overflow causing the return value to be SIZE_MAX. The 266 * lvalue must be size_t to avoid implicit type conversion. 267 */ 268 static inline size_t __must_check size_mul(size_t factor1, size_t factor2) 269 { 270 size_t bytes; 271 272 if (check_mul_overflow(factor1, factor2, &bytes)) 273 return SIZE_MAX; 274 275 return bytes; 276 } 277 278 /** 279 * size_add() - Calculate size_t addition with saturation at SIZE_MAX 280 * @addend1: first addend 281 * @addend2: second addend 282 * 283 * Returns: calculate @addend1 + @addend2, both promoted to size_t, 284 * with any overflow causing the return value to be SIZE_MAX. The 285 * lvalue must be size_t to avoid implicit type conversion. 286 */ 287 static inline size_t __must_check size_add(size_t addend1, size_t addend2) 288 { 289 size_t bytes; 290 291 if (check_add_overflow(addend1, addend2, &bytes)) 292 return SIZE_MAX; 293 294 return bytes; 295 } 296 297 /** 298 * size_sub() - Calculate size_t subtraction with saturation at SIZE_MAX 299 * @minuend: value to subtract from 300 * @subtrahend: value to subtract from @minuend 301 * 302 * Returns: calculate @minuend - @subtrahend, both promoted to size_t, 303 * with any overflow causing the return value to be SIZE_MAX. For 304 * composition with the size_add() and size_mul() helpers, neither 305 * argument may be SIZE_MAX (or the result with be forced to SIZE_MAX). 306 * The lvalue must be size_t to avoid implicit type conversion. 307 */ 308 static inline size_t __must_check size_sub(size_t minuend, size_t subtrahend) 309 { 310 size_t bytes; 311 312 if (minuend == SIZE_MAX || subtrahend == SIZE_MAX || 313 check_sub_overflow(minuend, subtrahend, &bytes)) 314 return SIZE_MAX; 315 316 return bytes; 317 } 318 319 /** 320 * array_size() - Calculate size of 2-dimensional array. 321 * @a: dimension one 322 * @b: dimension two 323 * 324 * Calculates size of 2-dimensional array: @a * @b. 325 * 326 * Returns: number of bytes needed to represent the array or SIZE_MAX on 327 * overflow. 328 */ 329 #define array_size(a, b) size_mul(a, b) 330 331 /** 332 * array3_size() - Calculate size of 3-dimensional array. 333 * @a: dimension one 334 * @b: dimension two 335 * @c: dimension three 336 * 337 * Calculates size of 3-dimensional array: @a * @b * @c. 338 * 339 * Returns: number of bytes needed to represent the array or SIZE_MAX on 340 * overflow. 341 */ 342 #define array3_size(a, b, c) size_mul(size_mul(a, b), c) 343 344 /** 345 * flex_array_size() - Calculate size of a flexible array member 346 * within an enclosing structure. 347 * @p: Pointer to the structure. 348 * @member: Name of the flexible array member. 349 * @count: Number of elements in the array. 350 * 351 * Calculates size of a flexible array of @count number of @member 352 * elements, at the end of structure @p. 353 * 354 * Return: number of bytes needed or SIZE_MAX on overflow. 355 */ 356 #define flex_array_size(p, member, count) \ 357 __builtin_choose_expr(__is_constexpr(count), \ 358 (count) * sizeof(*(p)->member) + __must_be_array((p)->member), \ 359 size_mul(count, sizeof(*(p)->member) + __must_be_array((p)->member))) 360 361 /** 362 * struct_size() - Calculate size of structure with trailing flexible array. 363 * @p: Pointer to the structure. 364 * @member: Name of the array member. 365 * @count: Number of elements in the array. 366 * 367 * Calculates size of memory needed for structure of @p followed by an 368 * array of @count number of @member elements. 369 * 370 * Return: number of bytes needed or SIZE_MAX on overflow. 371 */ 372 #define struct_size(p, member, count) \ 373 __builtin_choose_expr(__is_constexpr(count), \ 374 sizeof(*(p)) + flex_array_size(p, member, count), \ 375 size_add(sizeof(*(p)), flex_array_size(p, member, count))) 376 377 /** 378 * struct_size_t() - Calculate size of structure with trailing flexible array 379 * @type: structure type name. 380 * @member: Name of the array member. 381 * @count: Number of elements in the array. 382 * 383 * Calculates size of memory needed for structure @type followed by an 384 * array of @count number of @member elements. Prefer using struct_size() 385 * when possible instead, to keep calculations associated with a specific 386 * instance variable of type @type. 387 * 388 * Return: number of bytes needed or SIZE_MAX on overflow. 389 */ 390 #define struct_size_t(type, member, count) \ 391 struct_size((type *)NULL, member, count) 392 393 /** 394 * __DEFINE_FLEX() - helper macro for DEFINE_FLEX() family. 395 * Enables caller macro to pass arbitrary trailing expressions 396 * 397 * @type: structure type name, including "struct" keyword. 398 * @name: Name for a variable to define. 399 * @member: Name of the array member. 400 * @count: Number of elements in the array; must be compile-time const. 401 * @trailer: Trailing expressions for attributes and/or initializers. 402 */ 403 #define __DEFINE_FLEX(type, name, member, count, trailer...) \ 404 _Static_assert(__builtin_constant_p(count), \ 405 "onstack flex array members require compile-time const count"); \ 406 union { \ 407 u8 bytes[struct_size_t(type, member, count)]; \ 408 type obj; \ 409 } name##_u trailer; \ 410 type *name = (type *)&name##_u 411 412 /** 413 * _DEFINE_FLEX() - helper macro for DEFINE_FLEX() family. 414 * Enables caller macro to pass (different) initializer. 415 * 416 * @type: structure type name, including "struct" keyword. 417 * @name: Name for a variable to define. 418 * @member: Name of the array member. 419 * @count: Number of elements in the array; must be compile-time const. 420 * @initializer: Initializer expression (e.g., pass `= { }` at minimum). 421 */ 422 #define _DEFINE_FLEX(type, name, member, count, initializer...) \ 423 __DEFINE_FLEX(type, name, member, count, = { .obj initializer }) 424 425 /** 426 * DEFINE_RAW_FLEX() - Define an on-stack instance of structure with a trailing 427 * flexible array member, when it does not have a __counted_by annotation. 428 * 429 * @type: structure type name, including "struct" keyword. 430 * @name: Name for a variable to define. 431 * @member: Name of the array member. 432 * @count: Number of elements in the array; must be compile-time const. 433 * 434 * Define a zeroed, on-stack, instance of @type structure with a trailing 435 * flexible array member. 436 * Use __struct_size(@name) to get compile-time size of it afterwards. 437 * Use __member_size(@name->member) to get compile-time size of @name members. 438 * Use STACK_FLEX_ARRAY_SIZE(@name, @member) to get compile-time number of 439 * elements in array @member. 440 */ 441 #define DEFINE_RAW_FLEX(type, name, member, count) \ 442 __DEFINE_FLEX(type, name, member, count, = { }) 443 444 /** 445 * DEFINE_FLEX() - Define an on-stack instance of structure with a trailing 446 * flexible array member. 447 * 448 * @TYPE: structure type name, including "struct" keyword. 449 * @NAME: Name for a variable to define. 450 * @MEMBER: Name of the array member. 451 * @COUNTER: Name of the __counted_by member. 452 * @COUNT: Number of elements in the array; must be compile-time const. 453 * 454 * Define a zeroed, on-stack, instance of @TYPE structure with a trailing 455 * flexible array member. 456 * Use __struct_size(@NAME) to get compile-time size of it afterwards. 457 * Use __member_size(@NAME->member) to get compile-time size of @NAME members. 458 * Use STACK_FLEX_ARRAY_SIZE(@name, @member) to get compile-time number of 459 * elements in array @member. 460 */ 461 #define DEFINE_FLEX(TYPE, NAME, MEMBER, COUNTER, COUNT) \ 462 _DEFINE_FLEX(TYPE, NAME, MEMBER, COUNT, = { .COUNTER = COUNT, }) 463 464 /** 465 * STACK_FLEX_ARRAY_SIZE() - helper macro for DEFINE_FLEX() family. 466 * Returns the number of elements in @array. 467 * 468 * @name: Name for a variable defined in DEFINE_RAW_FLEX()/DEFINE_FLEX(). 469 * @array: Name of the array member. 470 */ 471 #define STACK_FLEX_ARRAY_SIZE(name, array) \ 472 (__member_size((name)->array) / sizeof(*(name)->array) + \ 473 __must_be_array((name)->array)) 474 475 #endif /* _LINUXKPI_LINUX_OVERFLOW_H */ 476