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 #include <linux/const.h> 8 9 /* 10 * We need to compute the minimum and maximum values representable in a given 11 * type. These macros may also be useful elsewhere. It would seem more obvious 12 * to do something like: 13 * 14 * #define type_min(T) (T)(is_signed_type(T) ? (T)1 << (8*sizeof(T)-1) : 0) 15 * #define type_max(T) (T)(is_signed_type(T) ? ((T)1 << (8*sizeof(T)-1)) - 1 : ~(T)0) 16 * 17 * Unfortunately, the middle expressions, strictly speaking, have 18 * undefined behaviour, and at least some versions of gcc warn about 19 * the type_max expression (but not if -fsanitize=undefined is in 20 * effect; in that case, the warning is deferred to runtime...). 21 * 22 * The slightly excessive casting in type_min is to make sure the 23 * macros also produce sensible values for the exotic type _Bool. [The 24 * overflow checkers only almost work for _Bool, but that's 25 * a-feature-not-a-bug, since people shouldn't be doing arithmetic on 26 * _Bools. Besides, the gcc builtins don't allow _Bool* as third 27 * argument.] 28 * 29 * Idea stolen from 30 * https://mail-index.netbsd.org/tech-misc/2007/02/05/0000.html - 31 * credit to Christian Biere. 32 */ 33 #define __type_half_max(type) ((type)1 << (8*sizeof(type) - 1 - is_signed_type(type))) 34 #define __type_max(T) ((T)((__type_half_max(T) - 1) + __type_half_max(T))) 35 #define type_max(t) __type_max(typeof(t)) 36 #define __type_min(T) ((T)((T)-type_max(T)-(T)1)) 37 #define type_min(t) __type_min(typeof(t)) 38 39 40 /* 41 * Allows for effectively applying __must_check to a macro so we can have 42 * both the type-agnostic benefits of the macros while also being able to 43 * enforce that the return value is, in fact, checked. 44 */ 45 static __always_inline bool __must_check __must_check_overflow(bool overflow) 46 { 47 return unlikely(overflow); 48 } 49 50 /** 51 * check_add_overflow() - Calculate addition with overflow checking 52 * @a: first addend 53 * @b: second addend 54 * @d: pointer to store sum 55 * 56 * Returns true on wrap-around, false otherwise. 57 * 58 * *@d holds the results of the attempted addition, regardless of whether 59 * wrap-around occurred. 60 */ 61 #define check_add_overflow(a, b, d) \ 62 __must_check_overflow(__builtin_add_overflow(a, b, d)) 63 64 /** 65 * wrapping_add() - Intentionally perform a wrapping addition 66 * @type: type for result of calculation 67 * @a: first addend 68 * @b: second addend 69 * 70 * Return the potentially wrapped-around addition without 71 * tripping any wrap-around sanitizers that may be enabled. 72 */ 73 #define wrapping_add(type, a, b) \ 74 ({ \ 75 type __val; \ 76 __builtin_add_overflow(a, b, &__val); \ 77 __val; \ 78 }) 79 80 /** 81 * wrapping_assign_add() - Intentionally perform a wrapping increment assignment 82 * @var: variable to be incremented 83 * @offset: amount to add 84 * 85 * Increments @var by @offset with wrap-around. Returns the resulting 86 * value of @var. Will not trip any wrap-around sanitizers. 87 * 88 * Returns the new value of @var. 89 */ 90 #define wrapping_assign_add(var, offset) \ 91 ({ \ 92 typeof(var) *__ptr = &(var); \ 93 *__ptr = wrapping_add(typeof(var), *__ptr, offset); \ 94 }) 95 96 /** 97 * check_sub_overflow() - Calculate subtraction with overflow checking 98 * @a: minuend; value to subtract from 99 * @b: subtrahend; value to subtract from @a 100 * @d: pointer to store difference 101 * 102 * Returns true on wrap-around, false otherwise. 103 * 104 * *@d holds the results of the attempted subtraction, regardless of whether 105 * wrap-around occurred. 106 */ 107 #define check_sub_overflow(a, b, d) \ 108 __must_check_overflow(__builtin_sub_overflow(a, b, d)) 109 110 /** 111 * wrapping_sub() - Intentionally perform a wrapping subtraction 112 * @type: type for result of calculation 113 * @a: minuend; value to subtract from 114 * @b: subtrahend; value to subtract from @a 115 * 116 * Return the potentially wrapped-around subtraction without 117 * tripping any wrap-around sanitizers that may be enabled. 118 */ 119 #define wrapping_sub(type, a, b) \ 120 ({ \ 121 type __val; \ 122 __builtin_sub_overflow(a, b, &__val); \ 123 __val; \ 124 }) 125 126 /** 127 * wrapping_assign_sub() - Intentionally perform a wrapping decrement assign 128 * @var: variable to be decremented 129 * @offset: amount to subtract 130 * 131 * Decrements @var by @offset with wrap-around. Returns the resulting 132 * value of @var. Will not trip any wrap-around sanitizers. 133 * 134 * Returns the new value of @var. 135 */ 136 #define wrapping_assign_sub(var, offset) \ 137 ({ \ 138 typeof(var) *__ptr = &(var); \ 139 *__ptr = wrapping_sub(typeof(var), *__ptr, offset); \ 140 }) 141 142 /** 143 * check_mul_overflow() - Calculate multiplication with overflow checking 144 * @a: first factor 145 * @b: second factor 146 * @d: pointer to store product 147 * 148 * Returns true on wrap-around, false otherwise. 149 * 150 * *@d holds the results of the attempted multiplication, regardless of whether 151 * wrap-around occurred. 152 */ 153 #define check_mul_overflow(a, b, d) \ 154 __must_check_overflow(__builtin_mul_overflow(a, b, d)) 155 156 /** 157 * wrapping_mul() - Intentionally perform a wrapping multiplication 158 * @type: type for result of calculation 159 * @a: first factor 160 * @b: second factor 161 * 162 * Return the potentially wrapped-around multiplication without 163 * tripping any wrap-around sanitizers that may be enabled. 164 */ 165 #define wrapping_mul(type, a, b) \ 166 ({ \ 167 type __val; \ 168 __builtin_mul_overflow(a, b, &__val); \ 169 __val; \ 170 }) 171 172 /** 173 * check_shl_overflow() - Calculate a left-shifted value and check overflow 174 * @a: Value to be shifted 175 * @s: How many bits left to shift 176 * @d: Pointer to where to store the result 177 * 178 * Computes *@d = (@a << @s) 179 * 180 * Returns true if '*@d' cannot hold the result or when '@a << @s' doesn't 181 * make sense. Example conditions: 182 * 183 * - '@a << @s' causes bits to be lost when stored in *@d. 184 * - '@s' is garbage (e.g. negative) or so large that the result of 185 * '@a << @s' is guaranteed to be 0. 186 * - '@a' is negative. 187 * - '@a << @s' sets the sign bit, if any, in '*@d'. 188 * 189 * '*@d' will hold the results of the attempted shift, but is not 190 * considered "safe for use" if true is returned. 191 */ 192 #define check_shl_overflow(a, s, d) __must_check_overflow(({ \ 193 typeof(a) _a = a; \ 194 typeof(s) _s = s; \ 195 typeof(d) _d = d; \ 196 unsigned long long _a_full = _a; \ 197 unsigned int _to_shift = \ 198 _s >= 0 && _s < 8 * sizeof(*d) ? _s : 0; \ 199 *_d = (_a_full << _to_shift); \ 200 (_to_shift != _s || *_d < 0 || _a < 0 || \ 201 (*_d >> _to_shift) != _a); \ 202 })) 203 204 #define __overflows_type_constexpr(x, T) ( \ 205 is_unsigned_type(typeof(x)) ? \ 206 (x) > type_max(T) : \ 207 is_unsigned_type(typeof(T)) ? \ 208 (x) < 0 || (x) > type_max(T) : \ 209 (x) < type_min(T) || (x) > type_max(T)) 210 211 #define __overflows_type(x, T) ({ \ 212 typeof(T) v = 0; \ 213 check_add_overflow((x), v, &v); \ 214 }) 215 216 /** 217 * overflows_type - helper for checking the overflows between value, variables, 218 * or data type 219 * 220 * @n: source constant value or variable to be checked 221 * @T: destination variable or data type proposed to store @x 222 * 223 * Compares the @x expression for whether or not it can safely fit in 224 * the storage of the type in @T. @x and @T can have different types. 225 * If @x is a constant expression, this will also resolve to a constant 226 * expression. 227 * 228 * Returns: true if overflow can occur, false otherwise. 229 */ 230 #define overflows_type(n, T) \ 231 __builtin_choose_expr(__is_constexpr(n), \ 232 __overflows_type_constexpr(n, T), \ 233 __overflows_type(n, T)) 234 235 /** 236 * range_overflows() - Check if a range is out of bounds 237 * @start: Start of the range. 238 * @size: Size of the range. 239 * @max: Exclusive upper boundary. 240 * 241 * A strict check to determine if the range [@start, @start + @size) is 242 * invalid with respect to the allowable range [0, @max). Any range 243 * starting at or beyond @max is considered an overflow, even if @size is 0. 244 * 245 * Returns: true if the range is out of bounds. 246 */ 247 #define range_overflows(start, size, max) ({ \ 248 typeof(start) start__ = (start); \ 249 typeof(size) size__ = (size); \ 250 typeof(max) max__ = (max); \ 251 (void)(&start__ == &size__); \ 252 (void)(&start__ == &max__); \ 253 start__ >= max__ || size__ > max__ - start__; \ 254 }) 255 256 /** 257 * range_overflows_t() - Check if a range is out of bounds 258 * @type: Data type to use. 259 * @start: Start of the range. 260 * @size: Size of the range. 261 * @max: Exclusive upper boundary. 262 * 263 * Same as range_overflows() but forcing the parameters to @type. 264 * 265 * Returns: true if the range is out of bounds. 266 */ 267 #define range_overflows_t(type, start, size, max) \ 268 range_overflows((type)(start), (type)(size), (type)(max)) 269 270 /** 271 * range_end_overflows() - Check if a range's endpoint is out of bounds 272 * @start: Start of the range. 273 * @size: Size of the range. 274 * @max: Exclusive upper boundary. 275 * 276 * Checks only if the endpoint of a range (@start + @size) exceeds @max. 277 * Unlike range_overflows(), a zero-sized range at the boundary (@start == @max) 278 * is not considered an overflow. Useful for iterator-style checks. 279 * 280 * Returns: true if the endpoint exceeds the boundary. 281 */ 282 #define range_end_overflows(start, size, max) ({ \ 283 typeof(start) start__ = (start); \ 284 typeof(size) size__ = (size); \ 285 typeof(max) max__ = (max); \ 286 (void)(&start__ == &size__); \ 287 (void)(&start__ == &max__); \ 288 start__ > max__ || size__ > max__ - start__; \ 289 }) 290 291 /** 292 * range_end_overflows_t() - Check if a range's endpoint is out of bounds 293 * @type: Data type to use. 294 * @start: Start of the range. 295 * @size: Size of the range. 296 * @max: Exclusive upper boundary. 297 * 298 * Same as range_end_overflows() but forcing the parameters to @type. 299 * 300 * Returns: true if the endpoint exceeds the boundary. 301 */ 302 #define range_end_overflows_t(type, start, size, max) \ 303 range_end_overflows((type)(start), (type)(size), (type)(max)) 304 305 /** 306 * castable_to_type - like __same_type(), but also allows for casted literals 307 * 308 * @n: variable or constant value 309 * @T: variable or data type 310 * 311 * Unlike the __same_type() macro, this allows a constant value as the 312 * first argument. If this value would not overflow into an assignment 313 * of the second argument's type, it returns true. Otherwise, this falls 314 * back to __same_type(). 315 */ 316 #define castable_to_type(n, T) \ 317 __builtin_choose_expr(__is_constexpr(n), \ 318 !__overflows_type_constexpr(n, T), \ 319 __same_type(n, T)) 320 321 /** 322 * size_mul() - Calculate size_t multiplication with saturation at SIZE_MAX 323 * @factor1: first factor 324 * @factor2: second factor 325 * 326 * Returns: calculate @factor1 * @factor2, both promoted to size_t, 327 * with any overflow causing the return value to be SIZE_MAX. The 328 * lvalue must be size_t to avoid implicit type conversion. 329 */ 330 static __always_inline size_t __must_check size_mul(size_t factor1, size_t factor2) 331 { 332 size_t bytes; 333 334 if (check_mul_overflow(factor1, factor2, &bytes)) 335 return SIZE_MAX; 336 337 return bytes; 338 } 339 340 /** 341 * size_add() - Calculate size_t addition with saturation at SIZE_MAX 342 * @addend1: first addend 343 * @addend2: second addend 344 * 345 * Returns: calculate @addend1 + @addend2, both promoted to size_t, 346 * with any overflow causing the return value to be SIZE_MAX. The 347 * lvalue must be size_t to avoid implicit type conversion. 348 */ 349 static __always_inline size_t __must_check size_add(size_t addend1, size_t addend2) 350 { 351 size_t bytes; 352 353 if (check_add_overflow(addend1, addend2, &bytes)) 354 return SIZE_MAX; 355 356 return bytes; 357 } 358 359 /** 360 * size_sub() - Calculate size_t subtraction with saturation at SIZE_MAX 361 * @minuend: value to subtract from 362 * @subtrahend: value to subtract from @minuend 363 * 364 * Returns: calculate @minuend - @subtrahend, both promoted to size_t, 365 * with any overflow causing the return value to be SIZE_MAX. For 366 * composition with the size_add() and size_mul() helpers, neither 367 * argument may be SIZE_MAX (or the result with be forced to SIZE_MAX). 368 * The lvalue must be size_t to avoid implicit type conversion. 369 */ 370 static __always_inline size_t __must_check size_sub(size_t minuend, size_t subtrahend) 371 { 372 size_t bytes; 373 374 if (minuend == SIZE_MAX || subtrahend == SIZE_MAX || 375 check_sub_overflow(minuend, subtrahend, &bytes)) 376 return SIZE_MAX; 377 378 return bytes; 379 } 380 381 /** 382 * array_size() - Calculate size of 2-dimensional array. 383 * @a: dimension one 384 * @b: dimension two 385 * 386 * Calculates size of 2-dimensional array: @a * @b. 387 * 388 * Returns: number of bytes needed to represent the array or SIZE_MAX on 389 * overflow. 390 */ 391 #define array_size(a, b) size_mul(a, b) 392 393 /** 394 * array3_size() - Calculate size of 3-dimensional array. 395 * @a: dimension one 396 * @b: dimension two 397 * @c: dimension three 398 * 399 * Calculates size of 3-dimensional array: @a * @b * @c. 400 * 401 * Returns: number of bytes needed to represent the array or SIZE_MAX on 402 * overflow. 403 */ 404 #define array3_size(a, b, c) size_mul(size_mul(a, b), c) 405 406 /** 407 * flex_array_size() - Calculate size of a flexible array member 408 * within an enclosing structure. 409 * @p: Pointer to the structure. 410 * @member: Name of the flexible array member. 411 * @count: Number of elements in the array. 412 * 413 * Calculates size of a flexible array of @count number of @member 414 * elements, at the end of structure @p. 415 * 416 * Return: number of bytes needed or SIZE_MAX on overflow. 417 */ 418 #define flex_array_size(p, member, count) \ 419 __builtin_choose_expr(__is_constexpr(count), \ 420 (count) * sizeof(*(p)->member) + __must_be_array((p)->member), \ 421 size_mul(count, sizeof(*(p)->member) + __must_be_array((p)->member))) 422 423 /** 424 * struct_size() - Calculate size of structure with trailing flexible array. 425 * @p: Pointer to the structure. 426 * @member: Name of the array member. 427 * @count: Number of elements in the array. 428 * 429 * Calculates size of memory needed for structure of @p followed by an 430 * array of @count number of @member elements. 431 * 432 * Return: number of bytes needed or SIZE_MAX on overflow. 433 */ 434 #define struct_size(p, member, count) \ 435 __builtin_choose_expr(__is_constexpr(count), \ 436 sizeof(*(p)) + flex_array_size(p, member, count), \ 437 size_add(sizeof(*(p)), flex_array_size(p, member, count))) 438 439 /** 440 * struct_size_t() - Calculate size of structure with trailing flexible array 441 * @type: structure type name. 442 * @member: Name of the array member. 443 * @count: Number of elements in the array. 444 * 445 * Calculates size of memory needed for structure @type followed by an 446 * array of @count number of @member elements. Prefer using struct_size() 447 * when possible instead, to keep calculations associated with a specific 448 * instance variable of type @type. 449 * 450 * Return: number of bytes needed or SIZE_MAX on overflow. 451 */ 452 #define struct_size_t(type, member, count) \ 453 struct_size((type *)NULL, member, count) 454 455 /** 456 * struct_offset() - Calculate the offset of a member within a struct 457 * @p: Pointer to the struct 458 * @member: Name of the member to get the offset of 459 * 460 * Calculates the offset of a particular @member of the structure pointed 461 * to by @p. 462 * 463 * Return: number of bytes to the location of @member. 464 */ 465 #define struct_offset(p, member) (offsetof(typeof(*(p)), member)) 466 467 /** 468 * __DEFINE_FLEX() - helper macro for DEFINE_FLEX() family. 469 * Enables caller macro to pass arbitrary trailing expressions 470 * 471 * @type: structure type name, including "struct" keyword. 472 * @name: Name for a variable to define. 473 * @member: Name of the array member. 474 * @count: Number of elements in the array; must be compile-time const. 475 * @trailer: Trailing expressions for attributes and/or initializers. 476 */ 477 #define __DEFINE_FLEX(type, name, member, count, trailer...) \ 478 _Static_assert(__builtin_constant_p(count), \ 479 "onstack flex array members require compile-time const count"); \ 480 union { \ 481 u8 bytes[struct_size_t(type, member, count)]; \ 482 type obj; \ 483 } name##_u trailer; \ 484 type *name = (type *)&name##_u 485 486 /** 487 * _DEFINE_FLEX() - helper macro for DEFINE_FLEX() family. 488 * Enables caller macro to pass (different) initializer. 489 * 490 * @type: structure type name, including "struct" keyword. 491 * @name: Name for a variable to define. 492 * @member: Name of the array member. 493 * @count: Number of elements in the array; must be compile-time const. 494 * @initializer: Initializer expression (e.g., pass `= { }` at minimum). 495 */ 496 #define _DEFINE_FLEX(type, name, member, count, initializer...) \ 497 __DEFINE_FLEX(type, name, member, count, = { .obj initializer }) 498 499 /** 500 * DEFINE_RAW_FLEX() - Define an on-stack instance of structure with a trailing 501 * flexible array member, when it does not have a __counted_by annotation. 502 * 503 * @type: structure type name, including "struct" keyword. 504 * @name: Name for a variable to define. 505 * @member: Name of the array member. 506 * @count: Number of elements in the array; must be compile-time const. 507 * 508 * Define a zeroed, on-stack, instance of @type structure with a trailing 509 * flexible array member. 510 * Use __struct_size(@name) to get compile-time size of it afterwards. 511 * Use __member_size(@name->member) to get compile-time size of @name members. 512 * Use STACK_FLEX_ARRAY_SIZE(@name, @member) to get compile-time number of 513 * elements in array @member. 514 */ 515 #define DEFINE_RAW_FLEX(type, name, member, count) \ 516 __DEFINE_FLEX(type, name, member, count, = { }) 517 518 /** 519 * DEFINE_FLEX() - Define an on-stack instance of structure with a trailing 520 * flexible array member. 521 * 522 * @TYPE: structure type name, including "struct" keyword. 523 * @NAME: Name for a variable to define. 524 * @MEMBER: Name of the array member. 525 * @COUNTER: Name of the __counted_by member. 526 * @COUNT: Number of elements in the array; must be compile-time const. 527 * 528 * Define a zeroed, on-stack, instance of @TYPE structure with a trailing 529 * flexible array member. 530 * Use __struct_size(@NAME) to get compile-time size of it afterwards. 531 * Use __member_size(@NAME->member) to get compile-time size of @NAME members. 532 * Use STACK_FLEX_ARRAY_SIZE(@name, @member) to get compile-time number of 533 * elements in array @member. 534 */ 535 #define DEFINE_FLEX(TYPE, NAME, MEMBER, COUNTER, COUNT) \ 536 _DEFINE_FLEX(TYPE, NAME, MEMBER, COUNT, = { .COUNTER = COUNT, }) 537 538 /** 539 * STACK_FLEX_ARRAY_SIZE() - helper macro for DEFINE_FLEX() family. 540 * Returns the number of elements in @array. 541 * 542 * @name: Name for a variable defined in DEFINE_RAW_FLEX()/DEFINE_FLEX(). 543 * @array: Name of the array member. 544 */ 545 #define STACK_FLEX_ARRAY_SIZE(name, array) \ 546 (__member_size((name)->array) / sizeof(*(name)->array) + \ 547 __must_be_array((name)->array)) 548 549 /** 550 * typeof_flex_counter() - Return the type of the counter variable of a given 551 * flexible array member annotated by __counted_by(). 552 * @FAM: Instance of flexible array member within a given struct. 553 * 554 * Returns: "size_t" if no annotation exists. 555 */ 556 #define typeof_flex_counter(FAM) \ 557 typeof(_Generic(__flex_counter(FAM), \ 558 void *: (size_t)0, \ 559 default: *__flex_counter(FAM))) 560 561 /** 562 * overflows_flex_counter_type() - Check if the counter associated with the 563 * given flexible array member can represent 564 * a value. 565 * @TYPE: Type of the struct that contains the @FAM. 566 * @FAM: Member name of the FAM within @TYPE. 567 * @COUNT: Value to check against the __counted_by annotated @FAM's counter. 568 * 569 * Returns: true if @COUNT can be represented in the @FAM's counter. When 570 * @FAM is not annotated with __counted_by(), always returns true. 571 */ 572 #define overflows_flex_counter_type(TYPE, FAM, COUNT) \ 573 (overflows_type(COUNT, typeof_flex_counter(((TYPE *)NULL)->FAM))) 574 575 /** 576 * __set_flex_counter() - Set the counter associated with the given flexible 577 * array member that has been annoated by __counted_by(). 578 * @FAM: Instance of flexible array member within a given struct. 579 * @COUNT: Value to store to the __counted_by annotated @FAM_PTR's counter. 580 * 581 * This is a no-op if no annotation exists. Count needs to be checked with 582 * overflows_flex_counter_type() before using this function. 583 */ 584 #define __set_flex_counter(FAM, COUNT) \ 585 ({ \ 586 *_Generic(__flex_counter(FAM), \ 587 void *: &(size_t){ 0 }, \ 588 default: __flex_counter(FAM)) = (COUNT); \ 589 }) 590 591 #endif /* _LINUXKPI_LINUX_OVERFLOW_H */ 592