Branch data 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 : :
7 : : /*
8 : : * In the fallback code below, we need to compute the minimum and
9 : : * maximum values representable in a given type. These macros may also
10 : : * be useful elsewhere, so we provide them outside the
11 : : * COMPILER_HAS_GENERIC_BUILTIN_OVERFLOW block.
12 : : *
13 : : * It would seem more obvious to do something like
14 : : *
15 : : * #define type_min(T) (T)(is_signed_type(T) ? (T)1 << (8*sizeof(T)-1) : 0)
16 : : * #define type_max(T) (T)(is_signed_type(T) ? ((T)1 << (8*sizeof(T)-1)) - 1 : ~(T)0)
17 : : *
18 : : * Unfortunately, the middle expressions, strictly speaking, have
19 : : * undefined behaviour, and at least some versions of gcc warn about
20 : : * the type_max expression (but not if -fsanitize=undefined is in
21 : : * effect; in that case, the warning is deferred to runtime...).
22 : : *
23 : : * The slightly excessive casting in type_min is to make sure the
24 : : * macros also produce sensible values for the exotic type _Bool. [The
25 : : * overflow checkers only almost work for _Bool, but that's
26 : : * a-feature-not-a-bug, since people shouldn't be doing arithmetic on
27 : : * _Bools. Besides, the gcc builtins don't allow _Bool* as third
28 : : * argument.]
29 : : *
30 : : * Idea stolen from
31 : : * https://mail-index.netbsd.org/tech-misc/2007/02/05/0000.html -
32 : : * credit to Christian Biere.
33 : : */
34 : : #define is_signed_type(type) (((type)(-1)) < (type)1)
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_min(T) ((T)((T)-type_max(T)-(T)1))
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 : : #ifdef COMPILER_HAS_GENERIC_BUILTIN_OVERFLOW
47 : : /*
48 : : * For simplicity and code hygiene, the fallback code below insists on
49 : : * a, b and *d having the same type (similar to the min() and max()
50 : : * macros), whereas gcc's type-generic overflow checkers accept
51 : : * different types. Hence we don't just make check_add_overflow an
52 : : * alias for __builtin_add_overflow, but add type checks similar to
53 : : * below.
54 : : */
55 : : #define check_add_overflow(a, b, d) ({ \
56 : : typeof(a) __a = (a); \
57 : : typeof(b) __b = (b); \
58 : : typeof(d) __d = (d); \
59 : : (void) (&__a == &__b); \
60 : : (void) (&__a == __d); \
61 : : __builtin_add_overflow(__a, __b, __d); \
62 : : })
63 : :
64 : : #define check_sub_overflow(a, b, d) ({ \
65 : : typeof(a) __a = (a); \
66 : : typeof(b) __b = (b); \
67 : : typeof(d) __d = (d); \
68 : : (void) (&__a == &__b); \
69 : : (void) (&__a == __d); \
70 : : __builtin_sub_overflow(__a, __b, __d); \
71 : : })
72 : :
73 : : #define check_mul_overflow(a, b, d) ({ \
74 : : typeof(a) __a = (a); \
75 : : typeof(b) __b = (b); \
76 : : typeof(d) __d = (d); \
77 : : (void) (&__a == &__b); \
78 : : (void) (&__a == __d); \
79 : : __builtin_mul_overflow(__a, __b, __d); \
80 : : })
81 : :
82 : : #else
83 : :
84 : :
85 : : /* Checking for unsigned overflow is relatively easy without causing UB. */
86 : : #define __unsigned_add_overflow(a, b, d) ({ \
87 : : typeof(a) __a = (a); \
88 : : typeof(b) __b = (b); \
89 : : typeof(d) __d = (d); \
90 : : (void) (&__a == &__b); \
91 : : (void) (&__a == __d); \
92 : : *__d = __a + __b; \
93 : : *__d < __a; \
94 : : })
95 : : #define __unsigned_sub_overflow(a, b, d) ({ \
96 : : typeof(a) __a = (a); \
97 : : typeof(b) __b = (b); \
98 : : typeof(d) __d = (d); \
99 : : (void) (&__a == &__b); \
100 : : (void) (&__a == __d); \
101 : : *__d = __a - __b; \
102 : : __a < __b; \
103 : : })
104 : : /*
105 : : * If one of a or b is a compile-time constant, this avoids a division.
106 : : */
107 : : #define __unsigned_mul_overflow(a, b, d) ({ \
108 : : typeof(a) __a = (a); \
109 : : typeof(b) __b = (b); \
110 : : typeof(d) __d = (d); \
111 : : (void) (&__a == &__b); \
112 : : (void) (&__a == __d); \
113 : : *__d = __a * __b; \
114 : : __builtin_constant_p(__b) ? \
115 : : __b > 0 && __a > type_max(typeof(__a)) / __b : \
116 : : __a > 0 && __b > type_max(typeof(__b)) / __a; \
117 : : })
118 : :
119 : : /*
120 : : * For signed types, detecting overflow is much harder, especially if
121 : : * we want to avoid UB. But the interface of these macros is such that
122 : : * we must provide a result in *d, and in fact we must produce the
123 : : * result promised by gcc's builtins, which is simply the possibly
124 : : * wrapped-around value. Fortunately, we can just formally do the
125 : : * operations in the widest relevant unsigned type (u64) and then
126 : : * truncate the result - gcc is smart enough to generate the same code
127 : : * with and without the (u64) casts.
128 : : */
129 : :
130 : : /*
131 : : * Adding two signed integers can overflow only if they have the same
132 : : * sign, and overflow has happened iff the result has the opposite
133 : : * sign.
134 : : */
135 : : #define __signed_add_overflow(a, b, d) ({ \
136 : : typeof(a) __a = (a); \
137 : : typeof(b) __b = (b); \
138 : : typeof(d) __d = (d); \
139 : : (void) (&__a == &__b); \
140 : : (void) (&__a == __d); \
141 : : *__d = (u64)__a + (u64)__b; \
142 : : (((~(__a ^ __b)) & (*__d ^ __a)) \
143 : : & type_min(typeof(__a))) != 0; \
144 : : })
145 : :
146 : : /*
147 : : * Subtraction is similar, except that overflow can now happen only
148 : : * when the signs are opposite. In this case, overflow has happened if
149 : : * the result has the opposite sign of a.
150 : : */
151 : : #define __signed_sub_overflow(a, b, d) ({ \
152 : : typeof(a) __a = (a); \
153 : : typeof(b) __b = (b); \
154 : : typeof(d) __d = (d); \
155 : : (void) (&__a == &__b); \
156 : : (void) (&__a == __d); \
157 : : *__d = (u64)__a - (u64)__b; \
158 : : ((((__a ^ __b)) & (*__d ^ __a)) \
159 : : & type_min(typeof(__a))) != 0; \
160 : : })
161 : :
162 : : /*
163 : : * Signed multiplication is rather hard. gcc always follows C99, so
164 : : * division is truncated towards 0. This means that we can write the
165 : : * overflow check like this:
166 : : *
167 : : * (a > 0 && (b > MAX/a || b < MIN/a)) ||
168 : : * (a < -1 && (b > MIN/a || b < MAX/a) ||
169 : : * (a == -1 && b == MIN)
170 : : *
171 : : * The redundant casts of -1 are to silence an annoying -Wtype-limits
172 : : * (included in -Wextra) warning: When the type is u8 or u16, the
173 : : * __b_c_e in check_mul_overflow obviously selects
174 : : * __unsigned_mul_overflow, but unfortunately gcc still parses this
175 : : * code and warns about the limited range of __b.
176 : : */
177 : :
178 : : #define __signed_mul_overflow(a, b, d) ({ \
179 : : typeof(a) __a = (a); \
180 : : typeof(b) __b = (b); \
181 : : typeof(d) __d = (d); \
182 : : typeof(a) __tmax = type_max(typeof(a)); \
183 : : typeof(a) __tmin = type_min(typeof(a)); \
184 : : (void) (&__a == &__b); \
185 : : (void) (&__a == __d); \
186 : : *__d = (u64)__a * (u64)__b; \
187 : : (__b > 0 && (__a > __tmax/__b || __a < __tmin/__b)) || \
188 : : (__b < (typeof(__b))-1 && (__a > __tmin/__b || __a < __tmax/__b)) || \
189 : : (__b == (typeof(__b))-1 && __a == __tmin); \
190 : : })
191 : :
192 : :
193 : : #define check_add_overflow(a, b, d) \
194 : : __builtin_choose_expr(is_signed_type(typeof(a)), \
195 : : __signed_add_overflow(a, b, d), \
196 : : __unsigned_add_overflow(a, b, d))
197 : :
198 : : #define check_sub_overflow(a, b, d) \
199 : : __builtin_choose_expr(is_signed_type(typeof(a)), \
200 : : __signed_sub_overflow(a, b, d), \
201 : : __unsigned_sub_overflow(a, b, d))
202 : :
203 : : #define check_mul_overflow(a, b, d) \
204 : : __builtin_choose_expr(is_signed_type(typeof(a)), \
205 : : __signed_mul_overflow(a, b, d), \
206 : : __unsigned_mul_overflow(a, b, d))
207 : :
208 : :
209 : : #endif /* COMPILER_HAS_GENERIC_BUILTIN_OVERFLOW */
210 : :
211 : : /** check_shl_overflow() - Calculate a left-shifted value and check overflow
212 : : *
213 : : * @a: Value to be shifted
214 : : * @s: How many bits left to shift
215 : : * @d: Pointer to where to store the result
216 : : *
217 : : * Computes *@d = (@a << @s)
218 : : *
219 : : * Returns true if '*d' cannot hold the result or when 'a << s' doesn't
220 : : * make sense. Example conditions:
221 : : * - 'a << s' causes bits to be lost when stored in *d.
222 : : * - 's' is garbage (e.g. negative) or so large that the result of
223 : : * 'a << s' is guaranteed to be 0.
224 : : * - 'a' is negative.
225 : : * - 'a << s' sets the sign bit, if any, in '*d'.
226 : : *
227 : : * '*d' will hold the results of the attempted shift, but is not
228 : : * considered "safe for use" if false is returned.
229 : : */
230 : : #define check_shl_overflow(a, s, d) ({ \
231 : : typeof(a) _a = a; \
232 : : typeof(s) _s = s; \
233 : : typeof(d) _d = d; \
234 : : u64 _a_full = _a; \
235 : : unsigned int _to_shift = \
236 : : is_non_negative(_s) && _s < 8 * sizeof(*d) ? _s : 0; \
237 : : *_d = (_a_full << _to_shift); \
238 : : (_to_shift != _s || is_negative(*_d) || is_negative(_a) || \
239 : : (*_d >> _to_shift) != _a); \
240 : : })
241 : :
242 : : /**
243 : : * array_size() - Calculate size of 2-dimensional array.
244 : : *
245 : : * @a: dimension one
246 : : * @b: dimension two
247 : : *
248 : : * Calculates size of 2-dimensional array: @a * @b.
249 : : *
250 : : * Returns: number of bytes needed to represent the array or SIZE_MAX on
251 : : * overflow.
252 : : */
253 : 44 : static inline __must_check size_t array_size(size_t a, size_t b)
254 : : {
255 : 44 : size_t bytes;
256 : :
257 [ - + ]: 44 : if (check_mul_overflow(a, b, &bytes))
258 : 0 : return SIZE_MAX;
259 : :
260 : : return bytes;
261 : : }
262 : :
263 : : /**
264 : : * array3_size() - Calculate size of 3-dimensional array.
265 : : *
266 : : * @a: dimension one
267 : : * @b: dimension two
268 : : * @c: dimension three
269 : : *
270 : : * Calculates size of 3-dimensional array: @a * @b * @c.
271 : : *
272 : : * Returns: number of bytes needed to represent the array or SIZE_MAX on
273 : : * overflow.
274 : : */
275 : 0 : static inline __must_check size_t array3_size(size_t a, size_t b, size_t c)
276 : : {
277 : 0 : size_t bytes;
278 : :
279 [ # # ]: 0 : if (check_mul_overflow(a, b, &bytes))
280 : : return SIZE_MAX;
281 [ # # ]: 0 : if (check_mul_overflow(bytes, c, &bytes))
282 : 0 : return SIZE_MAX;
283 : :
284 : : return bytes;
285 : : }
286 : :
287 : : /*
288 : : * Compute a*b+c, returning SIZE_MAX on overflow. Internal helper for
289 : : * struct_size() below.
290 : : */
291 : 1737 : static inline __must_check size_t __ab_c_size(size_t a, size_t b, size_t c)
292 : : {
293 : 1737 : size_t bytes;
294 : :
295 [ + - ]: 1737 : if (check_mul_overflow(a, b, &bytes))
296 : : return SIZE_MAX;
297 [ - + # # : 1737 : if (check_add_overflow(bytes, c, &bytes))
# # ]
298 : 0 : return SIZE_MAX;
299 : :
300 : : return bytes;
301 : : }
302 : :
303 : : /**
304 : : * struct_size() - Calculate size of structure with trailing array.
305 : : * @p: Pointer to the structure.
306 : : * @member: Name of the array member.
307 : : * @n: Number of elements in the array.
308 : : *
309 : : * Calculates size of memory needed for structure @p followed by an
310 : : * array of @n @member elements.
311 : : *
312 : : * Return: number of bytes needed or SIZE_MAX on overflow.
313 : : */
314 : : #define struct_size(p, member, n) \
315 : : __ab_c_size(n, \
316 : : sizeof(*(p)->member) + __must_be_array((p)->member),\
317 : : sizeof(*(p)))
318 : :
319 : : #endif /* __LINUX_OVERFLOW_H */
|
