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 #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 */
__must_check_overflow(bool overflow)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 */
size_mul(size_t factor1,size_t factor2)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 */
size_add(size_t addend1,size_t addend2)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 */
size_sub(size_t minuend,size_t subtrahend)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 /* __LINUX_OVERFLOW_H */
592