444 lines · c
1/* SPDX-License-Identifier: GPL-2.0 OR MIT */2#ifndef __LINUX_OVERFLOW_H3#define __LINUX_OVERFLOW_H4 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 given11 * type. These macros may also be useful elsewhere. It would seem more obvious12 * 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, have18 * undefined behaviour, and at least some versions of gcc warn about19 * the type_max expression (but not if -fsanitize=undefined is in20 * effect; in that case, the warning is deferred to runtime...).21 *22 * The slightly excessive casting in type_min is to make sure the23 * macros also produce sensible values for the exotic type _Bool. [The24 * overflow checkers only almost work for _Bool, but that's25 * a-feature-not-a-bug, since people shouldn't be doing arithmetic on26 * _Bools. Besides, the gcc builtins don't allow _Bool* as third27 * argument.]28 *29 * Idea stolen from30 * 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 * Avoids triggering -Wtype-limits compilation warning,41 * while using unsigned data types to check a < 0.42 */43#define is_non_negative(a) ((a) > 0 || (a) == 0)44#define is_negative(a) (!(is_non_negative(a)))45 46/*47 * Allows for effectively applying __must_check to a macro so we can have48 * both the type-agnostic benefits of the macros while also being able to49 * enforce that the return value is, in fact, checked.50 */51static inline bool __must_check __must_check_overflow(bool overflow)52{53 return unlikely(overflow);54}55 56/**57 * check_add_overflow() - Calculate addition with overflow checking58 * @a: first addend59 * @b: second addend60 * @d: pointer to store sum61 *62 * Returns true on wrap-around, false otherwise.63 *64 * *@d holds the results of the attempted addition, regardless of whether65 * wrap-around occurred.66 */67#define check_add_overflow(a, b, d) \68 __must_check_overflow(__builtin_add_overflow(a, b, d))69 70/**71 * wrapping_add() - Intentionally perform a wrapping addition72 * @type: type for result of calculation73 * @a: first addend74 * @b: second addend75 *76 * Return the potentially wrapped-around addition without77 * tripping any wrap-around sanitizers that may be enabled.78 */79#define wrapping_add(type, a, b) \80 ({ \81 type __val; \82 __builtin_add_overflow(a, b, &__val); \83 __val; \84 })85 86/**87 * wrapping_assign_add() - Intentionally perform a wrapping increment assignment88 * @var: variable to be incremented89 * @offset: amount to add90 *91 * Increments @var by @offset with wrap-around. Returns the resulting92 * value of @var. Will not trip any wrap-around sanitizers.93 *94 * Returns the new value of @var.95 */96#define wrapping_assign_add(var, offset) \97 ({ \98 typeof(var) *__ptr = &(var); \99 *__ptr = wrapping_add(typeof(var), *__ptr, offset); \100 })101 102/**103 * check_sub_overflow() - Calculate subtraction with overflow checking104 * @a: minuend; value to subtract from105 * @b: subtrahend; value to subtract from @a106 * @d: pointer to store difference107 *108 * Returns true on wrap-around, false otherwise.109 *110 * *@d holds the results of the attempted subtraction, regardless of whether111 * wrap-around occurred.112 */113#define check_sub_overflow(a, b, d) \114 __must_check_overflow(__builtin_sub_overflow(a, b, d))115 116/**117 * wrapping_sub() - Intentionally perform a wrapping subtraction118 * @type: type for result of calculation119 * @a: minuend; value to subtract from120 * @b: subtrahend; value to subtract from @a121 *122 * Return the potentially wrapped-around subtraction without123 * tripping any wrap-around sanitizers that may be enabled.124 */125#define wrapping_sub(type, a, b) \126 ({ \127 type __val; \128 __builtin_sub_overflow(a, b, &__val); \129 __val; \130 })131 132/**133 * wrapping_assign_sub() - Intentionally perform a wrapping decrement assign134 * @var: variable to be decremented135 * @offset: amount to subtract136 *137 * Decrements @var by @offset with wrap-around. Returns the resulting138 * value of @var. Will not trip any wrap-around sanitizers.139 *140 * Returns the new value of @var.141 */142#define wrapping_assign_sub(var, offset) \143 ({ \144 typeof(var) *__ptr = &(var); \145 *__ptr = wrapping_sub(typeof(var), *__ptr, offset); \146 })147 148/**149 * check_mul_overflow() - Calculate multiplication with overflow checking150 * @a: first factor151 * @b: second factor152 * @d: pointer to store product153 *154 * Returns true on wrap-around, false otherwise.155 *156 * *@d holds the results of the attempted multiplication, regardless of whether157 * wrap-around occurred.158 */159#define check_mul_overflow(a, b, d) \160 __must_check_overflow(__builtin_mul_overflow(a, b, d))161 162/**163 * wrapping_mul() - Intentionally perform a wrapping multiplication164 * @type: type for result of calculation165 * @a: first factor166 * @b: second factor167 *168 * Return the potentially wrapped-around multiplication without169 * tripping any wrap-around sanitizers that may be enabled.170 */171#define wrapping_mul(type, a, b) \172 ({ \173 type __val; \174 __builtin_mul_overflow(a, b, &__val); \175 __val; \176 })177 178/**179 * check_shl_overflow() - Calculate a left-shifted value and check overflow180 * @a: Value to be shifted181 * @s: How many bits left to shift182 * @d: Pointer to where to store the result183 *184 * Computes *@d = (@a << @s)185 *186 * Returns true if '*@d' cannot hold the result or when '@a << @s' doesn't187 * make sense. Example conditions:188 *189 * - '@a << @s' causes bits to be lost when stored in *@d.190 * - '@s' is garbage (e.g. negative) or so large that the result of191 * '@a << @s' is guaranteed to be 0.192 * - '@a' is negative.193 * - '@a << @s' sets the sign bit, if any, in '*@d'.194 *195 * '*@d' will hold the results of the attempted shift, but is not196 * considered "safe for use" if true is returned.197 */198#define check_shl_overflow(a, s, d) __must_check_overflow(({ \199 typeof(a) _a = a; \200 typeof(s) _s = s; \201 typeof(d) _d = d; \202 unsigned long long _a_full = _a; \203 unsigned int _to_shift = \204 is_non_negative(_s) && _s < 8 * sizeof(*d) ? _s : 0; \205 *_d = (_a_full << _to_shift); \206 (_to_shift != _s || is_negative(*_d) || is_negative(_a) || \207 (*_d >> _to_shift) != _a); \208}))209 210#define __overflows_type_constexpr(x, T) ( \211 is_unsigned_type(typeof(x)) ? \212 (x) > type_max(T) : \213 is_unsigned_type(typeof(T)) ? \214 (x) < 0 || (x) > type_max(T) : \215 (x) < type_min(T) || (x) > type_max(T))216 217#define __overflows_type(x, T) ({ \218 typeof(T) v = 0; \219 check_add_overflow((x), v, &v); \220})221 222/**223 * overflows_type - helper for checking the overflows between value, variables,224 * or data type225 *226 * @n: source constant value or variable to be checked227 * @T: destination variable or data type proposed to store @x228 *229 * Compares the @x expression for whether or not it can safely fit in230 * the storage of the type in @T. @x and @T can have different types.231 * If @x is a constant expression, this will also resolve to a constant232 * expression.233 *234 * Returns: true if overflow can occur, false otherwise.235 */236#define overflows_type(n, T) \237 __builtin_choose_expr(__is_constexpr(n), \238 __overflows_type_constexpr(n, T), \239 __overflows_type(n, T))240 241/**242 * castable_to_type - like __same_type(), but also allows for casted literals243 *244 * @n: variable or constant value245 * @T: variable or data type246 *247 * Unlike the __same_type() macro, this allows a constant value as the248 * first argument. If this value would not overflow into an assignment249 * of the second argument's type, it returns true. Otherwise, this falls250 * back to __same_type().251 */252#define castable_to_type(n, T) \253 __builtin_choose_expr(__is_constexpr(n), \254 !__overflows_type_constexpr(n, T), \255 __same_type(n, T))256 257/**258 * size_mul() - Calculate size_t multiplication with saturation at SIZE_MAX259 * @factor1: first factor260 * @factor2: second factor261 *262 * Returns: calculate @factor1 * @factor2, both promoted to size_t,263 * with any overflow causing the return value to be SIZE_MAX. The264 * lvalue must be size_t to avoid implicit type conversion.265 */266static inline size_t __must_check size_mul(size_t factor1, size_t factor2)267{268 size_t bytes;269 270 if (check_mul_overflow(factor1, factor2, &bytes))271 return SIZE_MAX;272 273 return bytes;274}275 276/**277 * size_add() - Calculate size_t addition with saturation at SIZE_MAX278 * @addend1: first addend279 * @addend2: second addend280 *281 * Returns: calculate @addend1 + @addend2, both promoted to size_t,282 * with any overflow causing the return value to be SIZE_MAX. The283 * lvalue must be size_t to avoid implicit type conversion.284 */285static inline size_t __must_check size_add(size_t addend1, size_t addend2)286{287 size_t bytes;288 289 if (check_add_overflow(addend1, addend2, &bytes))290 return SIZE_MAX;291 292 return bytes;293}294 295/**296 * size_sub() - Calculate size_t subtraction with saturation at SIZE_MAX297 * @minuend: value to subtract from298 * @subtrahend: value to subtract from @minuend299 *300 * Returns: calculate @minuend - @subtrahend, both promoted to size_t,301 * with any overflow causing the return value to be SIZE_MAX. For302 * composition with the size_add() and size_mul() helpers, neither303 * argument may be SIZE_MAX (or the result with be forced to SIZE_MAX).304 * The lvalue must be size_t to avoid implicit type conversion.305 */306static inline size_t __must_check size_sub(size_t minuend, size_t subtrahend)307{308 size_t bytes;309 310 if (minuend == SIZE_MAX || subtrahend == SIZE_MAX ||311 check_sub_overflow(minuend, subtrahend, &bytes))312 return SIZE_MAX;313 314 return bytes;315}316 317/**318 * array_size() - Calculate size of 2-dimensional array.319 * @a: dimension one320 * @b: dimension two321 *322 * Calculates size of 2-dimensional array: @a * @b.323 *324 * Returns: number of bytes needed to represent the array or SIZE_MAX on325 * overflow.326 */327#define array_size(a, b) size_mul(a, b)328 329/**330 * array3_size() - Calculate size of 3-dimensional array.331 * @a: dimension one332 * @b: dimension two333 * @c: dimension three334 *335 * Calculates size of 3-dimensional array: @a * @b * @c.336 *337 * Returns: number of bytes needed to represent the array or SIZE_MAX on338 * 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 member344 * within an enclosing structure.345 * @p: Pointer to the structure.346 * @member: Name of the flexible array member.347 * @count: Number of elements in the array.348 *349 * Calculates size of a flexible array of @count number of @member350 * elements, at the end of structure @p.351 *352 * Return: number of bytes needed or SIZE_MAX on overflow.353 */354#define flex_array_size(p, member, count) \355 __builtin_choose_expr(__is_constexpr(count), \356 (count) * sizeof(*(p)->member) + __must_be_array((p)->member), \357 size_mul(count, sizeof(*(p)->member) + __must_be_array((p)->member)))358 359/**360 * struct_size() - Calculate size of structure with trailing flexible array.361 * @p: Pointer to the structure.362 * @member: Name of the array member.363 * @count: Number of elements in the array.364 *365 * Calculates size of memory needed for structure of @p followed by an366 * array of @count number of @member elements.367 *368 * Return: number of bytes needed or SIZE_MAX on overflow.369 */370#define struct_size(p, member, count) \371 __builtin_choose_expr(__is_constexpr(count), \372 sizeof(*(p)) + flex_array_size(p, member, count), \373 size_add(sizeof(*(p)), flex_array_size(p, member, count)))374 375/**376 * struct_size_t() - Calculate size of structure with trailing flexible array377 * @type: structure type name.378 * @member: Name of the array member.379 * @count: Number of elements in the array.380 *381 * Calculates size of memory needed for structure @type followed by an382 * array of @count number of @member elements. Prefer using struct_size()383 * when possible instead, to keep calculations associated with a specific384 * instance variable of type @type.385 *386 * Return: number of bytes needed or SIZE_MAX on overflow.387 */388#define struct_size_t(type, member, count) \389 struct_size((type *)NULL, member, count)390 391/**392 * _DEFINE_FLEX() - helper macro for DEFINE_FLEX() family.393 * Enables caller macro to pass (different) initializer.394 *395 * @type: structure type name, including "struct" keyword.396 * @name: Name for a variable to define.397 * @member: Name of the array member.398 * @count: Number of elements in the array; must be compile-time const.399 * @initializer: initializer expression (could be empty for no init).400 */401#define _DEFINE_FLEX(type, name, member, count, initializer...) \402 _Static_assert(__builtin_constant_p(count), \403 "onstack flex array members require compile-time const count"); \404 union { \405 u8 bytes[struct_size_t(type, member, count)]; \406 type obj; \407 } name##_u initializer; \408 type *name = (type *)&name##_u409 410/**411 * DEFINE_RAW_FLEX() - Define an on-stack instance of structure with a trailing412 * flexible array member, when it does not have a __counted_by annotation.413 *414 * @type: structure type name, including "struct" keyword.415 * @name: Name for a variable to define.416 * @member: Name of the array member.417 * @count: Number of elements in the array; must be compile-time const.418 *419 * Define a zeroed, on-stack, instance of @type structure with a trailing420 * flexible array member.421 * Use __struct_size(@name) to get compile-time size of it afterwards.422 */423#define DEFINE_RAW_FLEX(type, name, member, count) \424 _DEFINE_FLEX(type, name, member, count, = {})425 426/**427 * DEFINE_FLEX() - Define an on-stack instance of structure with a trailing428 * flexible array member.429 *430 * @TYPE: structure type name, including "struct" keyword.431 * @NAME: Name for a variable to define.432 * @MEMBER: Name of the array member.433 * @COUNTER: Name of the __counted_by member.434 * @COUNT: Number of elements in the array; must be compile-time const.435 *436 * Define a zeroed, on-stack, instance of @TYPE structure with a trailing437 * flexible array member.438 * Use __struct_size(@NAME) to get compile-time size of it afterwards.439 */440#define DEFINE_FLEX(TYPE, NAME, MEMBER, COUNTER, COUNT) \441 _DEFINE_FLEX(TYPE, NAME, MEMBER, COUNT, = { .obj.COUNTER = COUNT, })442 443#endif /* __LINUX_OVERFLOW_H */444