Line data Source code
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 is_signed_type(type) (((type)(-1)) < (type)1)
34 : #define __type_half_max(type) ((type)1 << (8*sizeof(type) - 1 - is_signed_type(type)))
35 : #define type_max(T) ((T)((__type_half_max(T) - 1) + __type_half_max(T)))
36 : #define type_min(T) ((T)((T)-type_max(T)-(T)1))
37 :
38 : /*
39 : * Avoids triggering -Wtype-limits compilation warning,
40 : * while using unsigned data types to check a < 0.
41 : */
42 : #define is_non_negative(a) ((a) > 0 || (a) == 0)
43 : #define is_negative(a) (!(is_non_negative(a)))
44 :
45 : /*
46 : * Allows for effectively applying __must_check to a macro so we can have
47 : * both the type-agnostic benefits of the macros while also being able to
48 : * enforce that the return value is, in fact, checked.
49 : */
50 : static inline bool __must_check __must_check_overflow(bool overflow)
51 : {
52 277 : return unlikely(overflow);
53 : }
54 :
55 : /*
56 : * For simplicity and code hygiene, the fallback code below insists on
57 : * a, b and *d having the same type (similar to the min() and max()
58 : * macros), whereas gcc's type-generic overflow checkers accept
59 : * different types. Hence we don't just make check_add_overflow an
60 : * alias for __builtin_add_overflow, but add type checks similar to
61 : * below.
62 : */
63 : #define check_add_overflow(a, b, d) __must_check_overflow(({ \
64 : typeof(a) __a = (a); \
65 : typeof(b) __b = (b); \
66 : typeof(d) __d = (d); \
67 : (void) (&__a == &__b); \
68 : (void) (&__a == __d); \
69 : __builtin_add_overflow(__a, __b, __d); \
70 : }))
71 :
72 : #define check_sub_overflow(a, b, d) __must_check_overflow(({ \
73 : typeof(a) __a = (a); \
74 : typeof(b) __b = (b); \
75 : typeof(d) __d = (d); \
76 : (void) (&__a == &__b); \
77 : (void) (&__a == __d); \
78 : __builtin_sub_overflow(__a, __b, __d); \
79 : }))
80 :
81 : #define check_mul_overflow(a, b, d) __must_check_overflow(({ \
82 : typeof(a) __a = (a); \
83 : typeof(b) __b = (b); \
84 : typeof(d) __d = (d); \
85 : (void) (&__a == &__b); \
86 : (void) (&__a == __d); \
87 : __builtin_mul_overflow(__a, __b, __d); \
88 : }))
89 :
90 : /** check_shl_overflow() - Calculate a left-shifted value and check overflow
91 : *
92 : * @a: Value to be shifted
93 : * @s: How many bits left to shift
94 : * @d: Pointer to where to store the result
95 : *
96 : * Computes *@d = (@a << @s)
97 : *
98 : * Returns true if '*d' cannot hold the result or when 'a << s' doesn't
99 : * make sense. Example conditions:
100 : * - 'a << s' causes bits to be lost when stored in *d.
101 : * - 's' is garbage (e.g. negative) or so large that the result of
102 : * 'a << s' is guaranteed to be 0.
103 : * - 'a' is negative.
104 : * - 'a << s' sets the sign bit, if any, in '*d'.
105 : *
106 : * '*d' will hold the results of the attempted shift, but is not
107 : * considered "safe for use" if true is returned.
108 : */
109 : #define check_shl_overflow(a, s, d) __must_check_overflow(({ \
110 : typeof(a) _a = a; \
111 : typeof(s) _s = s; \
112 : typeof(d) _d = d; \
113 : u64 _a_full = _a; \
114 : unsigned int _to_shift = \
115 : is_non_negative(_s) && _s < 8 * sizeof(*d) ? _s : 0; \
116 : *_d = (_a_full << _to_shift); \
117 : (_to_shift != _s || is_negative(*_d) || is_negative(_a) || \
118 : (*_d >> _to_shift) != _a); \
119 : }))
120 :
121 : /**
122 : * size_mul() - Calculate size_t multiplication with saturation at SIZE_MAX
123 : *
124 : * @factor1: first factor
125 : * @factor2: second factor
126 : *
127 : * Returns: calculate @factor1 * @factor2, both promoted to size_t,
128 : * with any overflow causing the return value to be SIZE_MAX. The
129 : * lvalue must be size_t to avoid implicit type conversion.
130 : */
131 : static inline size_t __must_check size_mul(size_t factor1, size_t factor2)
132 : {
133 : size_t bytes;
134 :
135 6 : if (check_mul_overflow(factor1, factor2, &bytes))
136 : return SIZE_MAX;
137 :
138 : return bytes;
139 : }
140 :
141 : /**
142 : * size_add() - Calculate size_t addition with saturation at SIZE_MAX
143 : *
144 : * @addend1: first addend
145 : * @addend2: second addend
146 : *
147 : * Returns: calculate @addend1 + @addend2, both promoted to size_t,
148 : * with any overflow causing the return value to be SIZE_MAX. The
149 : * lvalue must be size_t to avoid implicit type conversion.
150 : */
151 : static inline size_t __must_check size_add(size_t addend1, size_t addend2)
152 : {
153 : size_t bytes;
154 :
155 6 : if (check_add_overflow(addend1, addend2, &bytes))
156 : return SIZE_MAX;
157 :
158 : return bytes;
159 : }
160 :
161 : /**
162 : * size_sub() - Calculate size_t subtraction with saturation at SIZE_MAX
163 : *
164 : * @minuend: value to subtract from
165 : * @subtrahend: value to subtract from @minuend
166 : *
167 : * Returns: calculate @minuend - @subtrahend, both promoted to size_t,
168 : * with any overflow causing the return value to be SIZE_MAX. For
169 : * composition with the size_add() and size_mul() helpers, neither
170 : * argument may be SIZE_MAX (or the result with be forced to SIZE_MAX).
171 : * The lvalue must be size_t to avoid implicit type conversion.
172 : */
173 : static inline size_t __must_check size_sub(size_t minuend, size_t subtrahend)
174 : {
175 : size_t bytes;
176 :
177 : if (minuend == SIZE_MAX || subtrahend == SIZE_MAX ||
178 : check_sub_overflow(minuend, subtrahend, &bytes))
179 : return SIZE_MAX;
180 :
181 : return bytes;
182 : }
183 :
184 : /**
185 : * array_size() - Calculate size of 2-dimensional array.
186 : *
187 : * @a: dimension one
188 : * @b: dimension two
189 : *
190 : * Calculates size of 2-dimensional array: @a * @b.
191 : *
192 : * Returns: number of bytes needed to represent the array or SIZE_MAX on
193 : * overflow.
194 : */
195 : #define array_size(a, b) size_mul(a, b)
196 :
197 : /**
198 : * array3_size() - Calculate size of 3-dimensional array.
199 : *
200 : * @a: dimension one
201 : * @b: dimension two
202 : * @c: dimension three
203 : *
204 : * Calculates size of 3-dimensional array: @a * @b * @c.
205 : *
206 : * Returns: number of bytes needed to represent the array or SIZE_MAX on
207 : * overflow.
208 : */
209 : #define array3_size(a, b, c) size_mul(size_mul(a, b), c)
210 :
211 : /**
212 : * flex_array_size() - Calculate size of a flexible array member
213 : * within an enclosing structure.
214 : *
215 : * @p: Pointer to the structure.
216 : * @member: Name of the flexible array member.
217 : * @count: Number of elements in the array.
218 : *
219 : * Calculates size of a flexible array of @count number of @member
220 : * elements, at the end of structure @p.
221 : *
222 : * Return: number of bytes needed or SIZE_MAX on overflow.
223 : */
224 : #define flex_array_size(p, member, count) \
225 : __builtin_choose_expr(__is_constexpr(count), \
226 : (count) * sizeof(*(p)->member) + __must_be_array((p)->member), \
227 : size_mul(count, sizeof(*(p)->member) + __must_be_array((p)->member)))
228 :
229 : /**
230 : * struct_size() - Calculate size of structure with trailing flexible array.
231 : *
232 : * @p: Pointer to the structure.
233 : * @member: Name of the array member.
234 : * @count: Number of elements in the array.
235 : *
236 : * Calculates size of memory needed for structure @p followed by an
237 : * array of @count number of @member elements.
238 : *
239 : * Return: number of bytes needed or SIZE_MAX on overflow.
240 : */
241 : #define struct_size(p, member, count) \
242 : __builtin_choose_expr(__is_constexpr(count), \
243 : sizeof(*(p)) + flex_array_size(p, member, count), \
244 : size_add(sizeof(*(p)), flex_array_size(p, member, count)))
245 :
246 : #endif /* __LINUX_OVERFLOW_H */
|
