1 // SPDX-License-Identifier: GPL-2.0
2 /* Copyright (c) 2023 Meta Platforms, Inc. and affiliates. */
3
4 #define _GNU_SOURCE
5 #include <limits.h>
6 #include <test_progs.h>
7 #include <linux/filter.h>
8 #include <linux/bpf.h>
9
10 /* =================================
11 * SHORT AND CONSISTENT NUMBER TYPES
12 * =================================
13 */
14 #define U64_MAX ((u64)UINT64_MAX)
15 #define U32_MAX ((u32)UINT_MAX)
16 #define U16_MAX ((u32)UINT_MAX)
17 #define S64_MIN ((s64)INT64_MIN)
18 #define S64_MAX ((s64)INT64_MAX)
19 #define S32_MIN ((s32)INT_MIN)
20 #define S32_MAX ((s32)INT_MAX)
21 #define S16_MIN ((s16)0x80000000)
22 #define S16_MAX ((s16)0x7fffffff)
23
24 typedef unsigned long long ___u64;
25 typedef unsigned int ___u32;
26 typedef long long ___s64;
27 typedef int ___s32;
28
29 /* avoid conflicts with already defined types in kernel headers */
30 #define u64 ___u64
31 #define u32 ___u32
32 #define s64 ___s64
33 #define s32 ___s32
34
35 /* ==================================
36 * STRING BUF ABSTRACTION AND HELPERS
37 * ==================================
38 */
39 struct strbuf {
40 size_t buf_sz;
41 int pos;
42 char buf[0];
43 };
44
45 #define DEFINE_STRBUF(name, N) \
46 struct { struct strbuf buf; char data[(N)]; } ___##name; \
47 struct strbuf *name = (___##name.buf.buf_sz = (N), ___##name.buf.pos = 0, &___##name.buf)
48
49 __printf(2, 3)
snappendf(struct strbuf * s,const char * fmt,...)50 static inline void snappendf(struct strbuf *s, const char *fmt, ...)
51 {
52 va_list args;
53
54 va_start(args, fmt);
55 s->pos += vsnprintf(s->buf + s->pos,
56 s->pos < s->buf_sz ? s->buf_sz - s->pos : 0,
57 fmt, args);
58 va_end(args);
59 }
60
61 /* ==================================
62 * GENERIC NUMBER TYPE AND OPERATIONS
63 * ==================================
64 */
65 enum num_t { U64, first_t = U64, U32, S64, S32, last_t = S32 };
66
min_t(enum num_t t,u64 x,u64 y)67 static __always_inline u64 min_t(enum num_t t, u64 x, u64 y)
68 {
69 switch (t) {
70 case U64: return (u64)x < (u64)y ? (u64)x : (u64)y;
71 case U32: return (u32)x < (u32)y ? (u32)x : (u32)y;
72 case S64: return (s64)x < (s64)y ? (s64)x : (s64)y;
73 case S32: return (s32)x < (s32)y ? (s32)x : (s32)y;
74 default: printf("min_t!\n"); exit(1);
75 }
76 }
77
max_t(enum num_t t,u64 x,u64 y)78 static __always_inline u64 max_t(enum num_t t, u64 x, u64 y)
79 {
80 switch (t) {
81 case U64: return (u64)x > (u64)y ? (u64)x : (u64)y;
82 case U32: return (u32)x > (u32)y ? (u32)x : (u32)y;
83 case S64: return (s64)x > (s64)y ? (s64)x : (s64)y;
84 case S32: return (s32)x > (s32)y ? (u32)(s32)x : (u32)(s32)y;
85 default: printf("max_t!\n"); exit(1);
86 }
87 }
88
cast_t(enum num_t t,u64 x)89 static __always_inline u64 cast_t(enum num_t t, u64 x)
90 {
91 switch (t) {
92 case U64: return (u64)x;
93 case U32: return (u32)x;
94 case S64: return (s64)x;
95 case S32: return (u32)(s32)x;
96 default: printf("cast_t!\n"); exit(1);
97 }
98 }
99
t_str(enum num_t t)100 static const char *t_str(enum num_t t)
101 {
102 switch (t) {
103 case U64: return "u64";
104 case U32: return "u32";
105 case S64: return "s64";
106 case S32: return "s32";
107 default: printf("t_str!\n"); exit(1);
108 }
109 }
110
t_is_32(enum num_t t)111 static enum num_t t_is_32(enum num_t t)
112 {
113 switch (t) {
114 case U64: return false;
115 case U32: return true;
116 case S64: return false;
117 case S32: return true;
118 default: printf("t_is_32!\n"); exit(1);
119 }
120 }
121
t_signed(enum num_t t)122 static enum num_t t_signed(enum num_t t)
123 {
124 switch (t) {
125 case U64: return S64;
126 case U32: return S32;
127 case S64: return S64;
128 case S32: return S32;
129 default: printf("t_signed!\n"); exit(1);
130 }
131 }
132
t_unsigned(enum num_t t)133 static enum num_t t_unsigned(enum num_t t)
134 {
135 switch (t) {
136 case U64: return U64;
137 case U32: return U32;
138 case S64: return U64;
139 case S32: return U32;
140 default: printf("t_unsigned!\n"); exit(1);
141 }
142 }
143
144 #define UNUM_MAX_DECIMAL U16_MAX
145 #define SNUM_MAX_DECIMAL S16_MAX
146 #define SNUM_MIN_DECIMAL S16_MIN
147
num_is_small(enum num_t t,u64 x)148 static bool num_is_small(enum num_t t, u64 x)
149 {
150 switch (t) {
151 case U64: return (u64)x <= UNUM_MAX_DECIMAL;
152 case U32: return (u32)x <= UNUM_MAX_DECIMAL;
153 case S64: return (s64)x >= SNUM_MIN_DECIMAL && (s64)x <= SNUM_MAX_DECIMAL;
154 case S32: return (s32)x >= SNUM_MIN_DECIMAL && (s32)x <= SNUM_MAX_DECIMAL;
155 default: printf("num_is_small!\n"); exit(1);
156 }
157 }
158
snprintf_num(enum num_t t,struct strbuf * sb,u64 x)159 static void snprintf_num(enum num_t t, struct strbuf *sb, u64 x)
160 {
161 bool is_small = num_is_small(t, x);
162
163 if (is_small) {
164 switch (t) {
165 case U64: return snappendf(sb, "%llu", (u64)x);
166 case U32: return snappendf(sb, "%u", (u32)x);
167 case S64: return snappendf(sb, "%lld", (s64)x);
168 case S32: return snappendf(sb, "%d", (s32)x);
169 default: printf("snprintf_num!\n"); exit(1);
170 }
171 } else {
172 switch (t) {
173 case U64:
174 if (x == U64_MAX)
175 return snappendf(sb, "U64_MAX");
176 else if (x >= U64_MAX - 256)
177 return snappendf(sb, "U64_MAX-%llu", U64_MAX - x);
178 else
179 return snappendf(sb, "%#llx", (u64)x);
180 case U32:
181 if ((u32)x == U32_MAX)
182 return snappendf(sb, "U32_MAX");
183 else if ((u32)x >= U32_MAX - 256)
184 return snappendf(sb, "U32_MAX-%u", U32_MAX - (u32)x);
185 else
186 return snappendf(sb, "%#x", (u32)x);
187 case S64:
188 if ((s64)x == S64_MAX)
189 return snappendf(sb, "S64_MAX");
190 else if ((s64)x >= S64_MAX - 256)
191 return snappendf(sb, "S64_MAX-%lld", S64_MAX - (s64)x);
192 else if ((s64)x == S64_MIN)
193 return snappendf(sb, "S64_MIN");
194 else if ((s64)x <= S64_MIN + 256)
195 return snappendf(sb, "S64_MIN+%lld", (s64)x - S64_MIN);
196 else
197 return snappendf(sb, "%#llx", (s64)x);
198 case S32:
199 if ((s32)x == S32_MAX)
200 return snappendf(sb, "S32_MAX");
201 else if ((s32)x >= S32_MAX - 256)
202 return snappendf(sb, "S32_MAX-%d", S32_MAX - (s32)x);
203 else if ((s32)x == S32_MIN)
204 return snappendf(sb, "S32_MIN");
205 else if ((s32)x <= S32_MIN + 256)
206 return snappendf(sb, "S32_MIN+%d", (s32)x - S32_MIN);
207 else
208 return snappendf(sb, "%#x", (s32)x);
209 default: printf("snprintf_num!\n"); exit(1);
210 }
211 }
212 }
213
214 /* ===================================
215 * GENERIC RANGE STRUCT AND OPERATIONS
216 * ===================================
217 */
218 struct range {
219 u64 a, b;
220 };
221
snprintf_range(enum num_t t,struct strbuf * sb,struct range x)222 static void snprintf_range(enum num_t t, struct strbuf *sb, struct range x)
223 {
224 if (x.a == x.b)
225 return snprintf_num(t, sb, x.a);
226
227 snappendf(sb, "[");
228 snprintf_num(t, sb, x.a);
229 snappendf(sb, "; ");
230 snprintf_num(t, sb, x.b);
231 snappendf(sb, "]");
232 }
233
print_range(enum num_t t,struct range x,const char * sfx)234 static void print_range(enum num_t t, struct range x, const char *sfx)
235 {
236 DEFINE_STRBUF(sb, 128);
237
238 snprintf_range(t, sb, x);
239 printf("%s%s", sb->buf, sfx);
240 }
241
242 static const struct range unkn[] = {
243 [U64] = { 0, U64_MAX },
244 [U32] = { 0, U32_MAX },
245 [S64] = { (u64)S64_MIN, (u64)S64_MAX },
246 [S32] = { (u64)(u32)S32_MIN, (u64)(u32)S32_MAX },
247 };
248
unkn_subreg(enum num_t t)249 static struct range unkn_subreg(enum num_t t)
250 {
251 switch (t) {
252 case U64: return unkn[U32];
253 case U32: return unkn[U32];
254 case S64: return unkn[U32];
255 case S32: return unkn[S32];
256 default: printf("unkn_subreg!\n"); exit(1);
257 }
258 }
259
range(enum num_t t,u64 a,u64 b)260 static struct range range(enum num_t t, u64 a, u64 b)
261 {
262 switch (t) {
263 case U64: return (struct range){ (u64)a, (u64)b };
264 case U32: return (struct range){ (u32)a, (u32)b };
265 case S64: return (struct range){ (s64)a, (s64)b };
266 case S32: return (struct range){ (u32)(s32)a, (u32)(s32)b };
267 default: printf("range!\n"); exit(1);
268 }
269 }
270
sign64(u64 x)271 static __always_inline u32 sign64(u64 x) { return (x >> 63) & 1; }
sign32(u64 x)272 static __always_inline u32 sign32(u64 x) { return ((u32)x >> 31) & 1; }
upper32(u64 x)273 static __always_inline u32 upper32(u64 x) { return (u32)(x >> 32); }
swap_low32(u64 x,u32 y)274 static __always_inline u64 swap_low32(u64 x, u32 y) { return (x & 0xffffffff00000000ULL) | y; }
275
range_eq(struct range x,struct range y)276 static bool range_eq(struct range x, struct range y)
277 {
278 return x.a == y.a && x.b == y.b;
279 }
280
range_cast_to_s32(struct range x)281 static struct range range_cast_to_s32(struct range x)
282 {
283 u64 a = x.a, b = x.b;
284
285 /* if upper 32 bits are constant, lower 32 bits should form a proper
286 * s32 range to be correct
287 */
288 if (upper32(a) == upper32(b) && (s32)a <= (s32)b)
289 return range(S32, a, b);
290
291 /* Special case where upper bits form a small sequence of two
292 * sequential numbers (in 32-bit unsigned space, so 0xffffffff to
293 * 0x00000000 is also valid), while lower bits form a proper s32 range
294 * going from negative numbers to positive numbers.
295 *
296 * E.g.: [0xfffffff0ffffff00; 0xfffffff100000010]. Iterating
297 * over full 64-bit numbers range will form a proper [-16, 16]
298 * ([0xffffff00; 0x00000010]) range in its lower 32 bits.
299 */
300 if (upper32(a) + 1 == upper32(b) && (s32)a < 0 && (s32)b >= 0)
301 return range(S32, a, b);
302
303 /* otherwise we can't derive much meaningful information */
304 return unkn[S32];
305 }
306
range_cast_u64(enum num_t to_t,struct range x)307 static struct range range_cast_u64(enum num_t to_t, struct range x)
308 {
309 u64 a = (u64)x.a, b = (u64)x.b;
310
311 switch (to_t) {
312 case U64:
313 return x;
314 case U32:
315 if (upper32(a) != upper32(b))
316 return unkn[U32];
317 return range(U32, a, b);
318 case S64:
319 if (sign64(a) != sign64(b))
320 return unkn[S64];
321 return range(S64, a, b);
322 case S32:
323 return range_cast_to_s32(x);
324 default: printf("range_cast_u64!\n"); exit(1);
325 }
326 }
327
range_cast_s64(enum num_t to_t,struct range x)328 static struct range range_cast_s64(enum num_t to_t, struct range x)
329 {
330 s64 a = (s64)x.a, b = (s64)x.b;
331
332 switch (to_t) {
333 case U64:
334 /* equivalent to (s64)a <= (s64)b check */
335 if (sign64(a) != sign64(b))
336 return unkn[U64];
337 return range(U64, a, b);
338 case U32:
339 if (upper32(a) != upper32(b) || sign32(a) != sign32(b))
340 return unkn[U32];
341 return range(U32, a, b);
342 case S64:
343 return x;
344 case S32:
345 return range_cast_to_s32(x);
346 default: printf("range_cast_s64!\n"); exit(1);
347 }
348 }
349
range_cast_u32(enum num_t to_t,struct range x)350 static struct range range_cast_u32(enum num_t to_t, struct range x)
351 {
352 u32 a = (u32)x.a, b = (u32)x.b;
353
354 switch (to_t) {
355 case U64:
356 case S64:
357 /* u32 is always a valid zero-extended u64/s64 */
358 return range(to_t, a, b);
359 case U32:
360 return x;
361 case S32:
362 return range_cast_to_s32(range(U32, a, b));
363 default: printf("range_cast_u32!\n"); exit(1);
364 }
365 }
366
range_cast_s32(enum num_t to_t,struct range x)367 static struct range range_cast_s32(enum num_t to_t, struct range x)
368 {
369 s32 a = (s32)x.a, b = (s32)x.b;
370
371 switch (to_t) {
372 case U64:
373 case U32:
374 case S64:
375 if (sign32(a) != sign32(b))
376 return unkn[to_t];
377 return range(to_t, a, b);
378 case S32:
379 return x;
380 default: printf("range_cast_s32!\n"); exit(1);
381 }
382 }
383
384 /* Reinterpret range in *from_t* domain as a range in *to_t* domain preserving
385 * all possible information. Worst case, it will be unknown range within
386 * *to_t* domain, if nothing more specific can be guaranteed during the
387 * conversion
388 */
range_cast(enum num_t from_t,enum num_t to_t,struct range from)389 static struct range range_cast(enum num_t from_t, enum num_t to_t, struct range from)
390 {
391 switch (from_t) {
392 case U64: return range_cast_u64(to_t, from);
393 case U32: return range_cast_u32(to_t, from);
394 case S64: return range_cast_s64(to_t, from);
395 case S32: return range_cast_s32(to_t, from);
396 default: printf("range_cast!\n"); exit(1);
397 }
398 }
399
is_valid_num(enum num_t t,u64 x)400 static bool is_valid_num(enum num_t t, u64 x)
401 {
402 switch (t) {
403 case U64: return true;
404 case U32: return upper32(x) == 0;
405 case S64: return true;
406 case S32: return upper32(x) == 0;
407 default: printf("is_valid_num!\n"); exit(1);
408 }
409 }
410
is_valid_range(enum num_t t,struct range x)411 static bool is_valid_range(enum num_t t, struct range x)
412 {
413 if (!is_valid_num(t, x.a) || !is_valid_num(t, x.b))
414 return false;
415
416 switch (t) {
417 case U64: return (u64)x.a <= (u64)x.b;
418 case U32: return (u32)x.a <= (u32)x.b;
419 case S64: return (s64)x.a <= (s64)x.b;
420 case S32: return (s32)x.a <= (s32)x.b;
421 default: printf("is_valid_range!\n"); exit(1);
422 }
423 }
424
range_intersection(enum num_t t,struct range old,struct range new)425 static struct range range_intersection(enum num_t t, struct range old, struct range new)
426 {
427 return range(t, max_t(t, old.a, new.a), min_t(t, old.b, new.b));
428 }
429
430 /*
431 * Result is precise when 'x' and 'y' overlap or form a continuous range,
432 * result is an over-approximation if 'x' and 'y' do not overlap.
433 */
range_union(enum num_t t,struct range x,struct range y)434 static struct range range_union(enum num_t t, struct range x, struct range y)
435 {
436 if (!is_valid_range(t, x))
437 return y;
438 if (!is_valid_range(t, y))
439 return x;
440 return range(t, min_t(t, x.a, y.a), max_t(t, x.b, y.b));
441 }
442
443 /*
444 * This function attempts to improve x range intersecting it with y.
445 * range_cast(... to_t ...) looses precision for ranges that pass to_t
446 * min/max boundaries. To avoid such precision loses this function
447 * splits both x and y into halves corresponding to non-overflowing
448 * sub-ranges: [0, smin] and [smax, -1].
449 * Final result is computed as follows:
450 *
451 * ((x ∩ [0, smax]) ∩ (y ∩ [0, smax])) ∪
452 * ((x ∩ [smin,-1]) ∩ (y ∩ [smin,-1]))
453 *
454 * Precision might still be lost if final union is not a continuous range.
455 */
range_refine_in_halves(enum num_t x_t,struct range x,enum num_t y_t,struct range y)456 static struct range range_refine_in_halves(enum num_t x_t, struct range x,
457 enum num_t y_t, struct range y)
458 {
459 struct range x_pos, x_neg, y_pos, y_neg, r_pos, r_neg;
460 u64 smax, smin, neg_one;
461
462 if (t_is_32(x_t)) {
463 smax = (u64)(u32)S32_MAX;
464 smin = (u64)(u32)S32_MIN;
465 neg_one = (u64)(u32)(s32)(-1);
466 } else {
467 smax = (u64)S64_MAX;
468 smin = (u64)S64_MIN;
469 neg_one = U64_MAX;
470 }
471 x_pos = range_intersection(x_t, x, range(x_t, 0, smax));
472 x_neg = range_intersection(x_t, x, range(x_t, smin, neg_one));
473 y_pos = range_intersection(y_t, y, range(x_t, 0, smax));
474 y_neg = range_intersection(y_t, y, range(y_t, smin, neg_one));
475 r_pos = range_intersection(x_t, x_pos, range_cast(y_t, x_t, y_pos));
476 r_neg = range_intersection(x_t, x_neg, range_cast(y_t, x_t, y_neg));
477 return range_union(x_t, r_pos, r_neg);
478
479 }
480
range_refine(enum num_t x_t,struct range x,enum num_t y_t,struct range y)481 static struct range range_refine(enum num_t x_t, struct range x, enum num_t y_t, struct range y)
482 {
483 struct range y_cast;
484
485 if (t_is_32(x_t) == t_is_32(y_t))
486 x = range_refine_in_halves(x_t, x, y_t, y);
487
488 y_cast = range_cast(y_t, x_t, y);
489
490 /* If we know that
491 * - *x* is in the range of signed 32bit value, and
492 * - *y_cast* range is 32-bit signed non-negative
493 * then *x* range can be improved with *y_cast* such that *x* range
494 * is 32-bit signed non-negative. Otherwise, if the new range for *x*
495 * allows upper 32-bit * 0xffffffff then the eventual new range for
496 * *x* will be out of signed 32-bit range which violates the origin
497 * *x* range.
498 */
499 if (x_t == S64 && y_t == S32 && y_cast.a <= S32_MAX && y_cast.b <= S32_MAX &&
500 (s64)x.a >= S32_MIN && (s64)x.b <= S32_MAX)
501 return range_intersection(x_t, x, y_cast);
502
503 if (y_t == U32 && x_t == U64) {
504 u64 xmin_swap, xmax_swap, xmin_lower32, xmax_lower32;
505
506 xmin_lower32 = x.a & 0xffffffff;
507 xmax_lower32 = x.b & 0xffffffff;
508 if (xmin_lower32 < y.a || xmin_lower32 > y.b) {
509 /* The 32 lower bits of the umin64 are outside the u32
510 * range. Let's update umin64 to match the u32 range.
511 * We want to *increase* the umin64 to the *minimum*
512 * value that matches the u32 range.
513 */
514 xmin_swap = swap_low32(x.a, y.a);
515 /* We should always only increase the minimum, so if
516 * the new value is lower than before, we need to
517 * increase the 32 upper bits by 1.
518 */
519 if (xmin_swap < x.a)
520 xmin_swap += 0x100000000;
521 if (xmin_swap == x.b)
522 return range(x_t, x.b, x.b);
523 } else if (xmax_lower32 < y.a || xmax_lower32 > y.b) {
524 /* Same for the umax64, but we want to *decrease*
525 * umax64 to the *maximum* value that matches the u32
526 * range.
527 */
528 xmax_swap = swap_low32(x.b, y.b);
529 if (xmax_swap > x.b)
530 xmax_swap -= 0x100000000;
531 if (xmax_swap == x.a)
532 return range(x_t, x.a, x.a);
533 }
534 }
535
536 /* the case when new range knowledge, *y*, is a 32-bit subregister
537 * range, while previous range knowledge, *x*, is a full register
538 * 64-bit range, needs special treatment to take into account upper 32
539 * bits of full register range
540 */
541 if (t_is_32(y_t) && !t_is_32(x_t)) {
542 struct range x_swap;
543
544 /* some combinations of upper 32 bits and sign bit can lead to
545 * invalid ranges, in such cases it's easier to detect them
546 * after cast/swap than try to enumerate all the conditions
547 * under which transformation and knowledge transfer is valid
548 */
549 x_swap = range(x_t, swap_low32(x.a, y_cast.a), swap_low32(x.b, y_cast.b));
550 if (!is_valid_range(x_t, x_swap))
551 return x;
552 return range_intersection(x_t, x, x_swap);
553 }
554
555 /* otherwise, plain range cast and intersection works */
556 return range_intersection(x_t, x, y_cast);
557 }
558
559 /* =======================
560 * GENERIC CONDITIONAL OPS
561 * =======================
562 */
563 enum op { OP_LT, OP_LE, OP_GT, OP_GE, OP_EQ, OP_NE, first_op = OP_LT, last_op = OP_NE };
564
complement_op(enum op op)565 static enum op complement_op(enum op op)
566 {
567 switch (op) {
568 case OP_LT: return OP_GE;
569 case OP_LE: return OP_GT;
570 case OP_GT: return OP_LE;
571 case OP_GE: return OP_LT;
572 case OP_EQ: return OP_NE;
573 case OP_NE: return OP_EQ;
574 default: printf("complement_op!\n"); exit(1);
575 }
576 }
577
op_str(enum op op)578 static const char *op_str(enum op op)
579 {
580 switch (op) {
581 case OP_LT: return "<";
582 case OP_LE: return "<=";
583 case OP_GT: return ">";
584 case OP_GE: return ">=";
585 case OP_EQ: return "==";
586 case OP_NE: return "!=";
587 default: printf("op_str!\n"); exit(1);
588 }
589 }
590
591 /* Can register with range [x.a, x.b] *EVER* satisfy
592 * OP (<, <=, >, >=, ==, !=) relation to
593 * a register with range [y.a, y.b]
594 * _in *num_t* domain_
595 */
range_canbe_op(enum num_t t,struct range x,struct range y,enum op op)596 static bool range_canbe_op(enum num_t t, struct range x, struct range y, enum op op)
597 {
598 #define range_canbe(T) do { \
599 switch (op) { \
600 case OP_LT: return (T)x.a < (T)y.b; \
601 case OP_LE: return (T)x.a <= (T)y.b; \
602 case OP_GT: return (T)x.b > (T)y.a; \
603 case OP_GE: return (T)x.b >= (T)y.a; \
604 case OP_EQ: return (T)max_t(t, x.a, y.a) <= (T)min_t(t, x.b, y.b); \
605 case OP_NE: return !((T)x.a == (T)x.b && (T)y.a == (T)y.b && (T)x.a == (T)y.a); \
606 default: printf("range_canbe op %d\n", op); exit(1); \
607 } \
608 } while (0)
609
610 switch (t) {
611 case U64: { range_canbe(u64); }
612 case U32: { range_canbe(u32); }
613 case S64: { range_canbe(s64); }
614 case S32: { range_canbe(s32); }
615 default: printf("range_canbe!\n"); exit(1);
616 }
617 #undef range_canbe
618 }
619
620 /* Does register with range [x.a, x.b] *ALWAYS* satisfy
621 * OP (<, <=, >, >=, ==, !=) relation to
622 * a register with range [y.a, y.b]
623 * _in *num_t* domain_
624 */
range_always_op(enum num_t t,struct range x,struct range y,enum op op)625 static bool range_always_op(enum num_t t, struct range x, struct range y, enum op op)
626 {
627 /* always op <=> ! canbe complement(op) */
628 return !range_canbe_op(t, x, y, complement_op(op));
629 }
630
631 /* Does register with range [x.a, x.b] *NEVER* satisfy
632 * OP (<, <=, >, >=, ==, !=) relation to
633 * a register with range [y.a, y.b]
634 * _in *num_t* domain_
635 */
range_never_op(enum num_t t,struct range x,struct range y,enum op op)636 static bool range_never_op(enum num_t t, struct range x, struct range y, enum op op)
637 {
638 return !range_canbe_op(t, x, y, op);
639 }
640
641 /* similar to verifier's is_branch_taken():
642 * 1 - always taken;
643 * 0 - never taken,
644 * -1 - unsure.
645 */
range_branch_taken_op(enum num_t t,struct range x,struct range y,enum op op)646 static int range_branch_taken_op(enum num_t t, struct range x, struct range y, enum op op)
647 {
648 if (range_always_op(t, x, y, op))
649 return 1;
650 if (range_never_op(t, x, y, op))
651 return 0;
652 return -1;
653 }
654
655 /* What would be the new estimates for register x and y ranges assuming truthful
656 * OP comparison between them. I.e., (x OP y == true) => x <- newx, y <- newy.
657 *
658 * We assume "interesting" cases where ranges overlap. Cases where it's
659 * obvious that (x OP y) is either always true or false should be filtered with
660 * range_never and range_always checks.
661 */
range_cond(enum num_t t,struct range x,struct range y,enum op op,struct range * newx,struct range * newy)662 static void range_cond(enum num_t t, struct range x, struct range y,
663 enum op op, struct range *newx, struct range *newy)
664 {
665 if (!range_canbe_op(t, x, y, op)) {
666 /* nothing to adjust, can't happen, return original values */
667 *newx = x;
668 *newy = y;
669 return;
670 }
671 switch (op) {
672 case OP_LT:
673 *newx = range(t, x.a, min_t(t, x.b, y.b - 1));
674 *newy = range(t, max_t(t, x.a + 1, y.a), y.b);
675 break;
676 case OP_LE:
677 *newx = range(t, x.a, min_t(t, x.b, y.b));
678 *newy = range(t, max_t(t, x.a, y.a), y.b);
679 break;
680 case OP_GT:
681 *newx = range(t, max_t(t, x.a, y.a + 1), x.b);
682 *newy = range(t, y.a, min_t(t, x.b - 1, y.b));
683 break;
684 case OP_GE:
685 *newx = range(t, max_t(t, x.a, y.a), x.b);
686 *newy = range(t, y.a, min_t(t, x.b, y.b));
687 break;
688 case OP_EQ:
689 *newx = range(t, max_t(t, x.a, y.a), min_t(t, x.b, y.b));
690 *newy = range(t, max_t(t, x.a, y.a), min_t(t, x.b, y.b));
691 break;
692 case OP_NE:
693 /* below logic is supported by the verifier now */
694 if (x.a == x.b && x.a == y.a) {
695 /* X is a constant matching left side of Y */
696 *newx = range(t, x.a, x.b);
697 *newy = range(t, y.a + 1, y.b);
698 } else if (x.a == x.b && x.b == y.b) {
699 /* X is a constant matching right side of Y */
700 *newx = range(t, x.a, x.b);
701 *newy = range(t, y.a, y.b - 1);
702 } else if (y.a == y.b && x.a == y.a) {
703 /* Y is a constant matching left side of X */
704 *newx = range(t, x.a + 1, x.b);
705 *newy = range(t, y.a, y.b);
706 } else if (y.a == y.b && x.b == y.b) {
707 /* Y is a constant matching right side of X */
708 *newx = range(t, x.a, x.b - 1);
709 *newy = range(t, y.a, y.b);
710 } else {
711 /* generic case, can't derive more information */
712 *newx = range(t, x.a, x.b);
713 *newy = range(t, y.a, y.b);
714 }
715
716 break;
717 default:
718 break;
719 }
720 }
721
722 /* =======================
723 * REGISTER STATE HANDLING
724 * =======================
725 */
726 struct reg_state {
727 struct range r[4]; /* indexed by enum num_t: U64, U32, S64, S32 */
728 bool valid;
729 };
730
print_reg_state(struct reg_state * r,const char * sfx)731 static void print_reg_state(struct reg_state *r, const char *sfx)
732 {
733 DEFINE_STRBUF(sb, 512);
734 enum num_t t;
735 int cnt = 0;
736
737 if (!r->valid) {
738 printf("<not found>%s", sfx);
739 return;
740 }
741
742 snappendf(sb, "scalar(");
743 for (t = first_t; t <= last_t; t++) {
744 snappendf(sb, "%s%s=", cnt++ ? "," : "", t_str(t));
745 snprintf_range(t, sb, r->r[t]);
746 }
747 snappendf(sb, ")");
748
749 printf("%s%s", sb->buf, sfx);
750 }
751
print_refinement(enum num_t s_t,struct range src,enum num_t d_t,struct range old,struct range new,const char * ctx)752 static void print_refinement(enum num_t s_t, struct range src,
753 enum num_t d_t, struct range old, struct range new,
754 const char *ctx)
755 {
756 printf("REFINING (%s) (%s)SRC=", ctx, t_str(s_t));
757 print_range(s_t, src, "");
758 printf(" (%s)DST_OLD=", t_str(d_t));
759 print_range(d_t, old, "");
760 printf(" (%s)DST_NEW=", t_str(d_t));
761 print_range(d_t, new, "\n");
762 }
763
reg_state_refine(struct reg_state * r,enum num_t t,struct range x,const char * ctx)764 static void reg_state_refine(struct reg_state *r, enum num_t t, struct range x, const char *ctx)
765 {
766 enum num_t d_t, s_t;
767 struct range old;
768 bool keep_going = false;
769
770 again:
771 /* try to derive new knowledge from just learned range x of type t */
772 for (d_t = first_t; d_t <= last_t; d_t++) {
773 old = r->r[d_t];
774 r->r[d_t] = range_refine(d_t, r->r[d_t], t, x);
775 if (!range_eq(r->r[d_t], old)) {
776 keep_going = true;
777 if (env.verbosity >= VERBOSE_VERY)
778 print_refinement(t, x, d_t, old, r->r[d_t], ctx);
779 }
780 }
781
782 /* now see if we can derive anything new from updated reg_state's ranges */
783 for (s_t = first_t; s_t <= last_t; s_t++) {
784 for (d_t = first_t; d_t <= last_t; d_t++) {
785 old = r->r[d_t];
786 r->r[d_t] = range_refine(d_t, r->r[d_t], s_t, r->r[s_t]);
787 if (!range_eq(r->r[d_t], old)) {
788 keep_going = true;
789 if (env.verbosity >= VERBOSE_VERY)
790 print_refinement(s_t, r->r[s_t], d_t, old, r->r[d_t], ctx);
791 }
792 }
793 }
794
795 /* keep refining until we converge */
796 if (keep_going) {
797 keep_going = false;
798 goto again;
799 }
800 }
801
reg_state_set_const(struct reg_state * rs,enum num_t t,u64 val)802 static void reg_state_set_const(struct reg_state *rs, enum num_t t, u64 val)
803 {
804 enum num_t tt;
805
806 rs->valid = true;
807 for (tt = first_t; tt <= last_t; tt++)
808 rs->r[tt] = tt == t ? range(t, val, val) : unkn[tt];
809
810 reg_state_refine(rs, t, rs->r[t], "CONST");
811 }
812
reg_state_cond(enum num_t t,struct reg_state * x,struct reg_state * y,enum op op,struct reg_state * newx,struct reg_state * newy,const char * ctx)813 static void reg_state_cond(enum num_t t, struct reg_state *x, struct reg_state *y, enum op op,
814 struct reg_state *newx, struct reg_state *newy, const char *ctx)
815 {
816 char buf[32];
817 enum num_t ts[2];
818 struct reg_state xx = *x, yy = *y;
819 int i, t_cnt;
820 struct range z1, z2;
821
822 if (op == OP_EQ || op == OP_NE) {
823 /* OP_EQ and OP_NE are sign-agnostic, so we need to process
824 * both signed and unsigned domains at the same time
825 */
826 ts[0] = t_unsigned(t);
827 ts[1] = t_signed(t);
828 t_cnt = 2;
829 } else {
830 ts[0] = t;
831 t_cnt = 1;
832 }
833
834 for (i = 0; i < t_cnt; i++) {
835 t = ts[i];
836 z1 = x->r[t];
837 z2 = y->r[t];
838
839 range_cond(t, z1, z2, op, &z1, &z2);
840
841 if (newx) {
842 snprintf(buf, sizeof(buf), "%s R1", ctx);
843 reg_state_refine(&xx, t, z1, buf);
844 }
845 if (newy) {
846 snprintf(buf, sizeof(buf), "%s R2", ctx);
847 reg_state_refine(&yy, t, z2, buf);
848 }
849 }
850
851 if (newx)
852 *newx = xx;
853 if (newy)
854 *newy = yy;
855 }
856
reg_state_branch_taken_op(enum num_t t,struct reg_state * x,struct reg_state * y,enum op op)857 static int reg_state_branch_taken_op(enum num_t t, struct reg_state *x, struct reg_state *y,
858 enum op op)
859 {
860 if (op == OP_EQ || op == OP_NE) {
861 /* OP_EQ and OP_NE are sign-agnostic */
862 enum num_t tu = t_unsigned(t);
863 enum num_t ts = t_signed(t);
864 int br_u, br_s, br;
865
866 br_u = range_branch_taken_op(tu, x->r[tu], y->r[tu], op);
867 br_s = range_branch_taken_op(ts, x->r[ts], y->r[ts], op);
868
869 if (br_u >= 0 && br_s >= 0 && br_u != br_s)
870 ASSERT_FALSE(true, "branch taken inconsistency!\n");
871
872 /* if 64-bit ranges are indecisive, use 32-bit subranges to
873 * eliminate always/never taken branches, if possible
874 */
875 if (br_u == -1 && (t == U64 || t == S64)) {
876 br = range_branch_taken_op(U32, x->r[U32], y->r[U32], op);
877 /* we can only reject for OP_EQ, never take branch
878 * based on lower 32 bits
879 */
880 if (op == OP_EQ && br == 0)
881 return 0;
882 /* for OP_NEQ we can be conclusive only if lower 32 bits
883 * differ and thus inequality branch is always taken
884 */
885 if (op == OP_NE && br == 1)
886 return 1;
887
888 br = range_branch_taken_op(S32, x->r[S32], y->r[S32], op);
889 if (op == OP_EQ && br == 0)
890 return 0;
891 if (op == OP_NE && br == 1)
892 return 1;
893 }
894
895 return br_u >= 0 ? br_u : br_s;
896 }
897 return range_branch_taken_op(t, x->r[t], y->r[t], op);
898 }
899
900 /* =====================================
901 * BPF PROGS GENERATION AND VERIFICATION
902 * =====================================
903 */
904 struct case_spec {
905 /* whether to init full register (r1) or sub-register (w1) */
906 bool init_subregs;
907 /* whether to establish initial value range on full register (r1) or
908 * sub-register (w1)
909 */
910 bool setup_subregs;
911 /* whether to establish initial value range using signed or unsigned
912 * comparisons (i.e., initialize umin/umax or smin/smax directly)
913 */
914 bool setup_signed;
915 /* whether to perform comparison on full registers or sub-registers */
916 bool compare_subregs;
917 /* whether to perform comparison using signed or unsigned operations */
918 bool compare_signed;
919 };
920
921 /* Generate test BPF program based on provided test ranges, operation, and
922 * specifications about register bitness and signedness.
923 */
load_range_cmp_prog(struct range x,struct range y,enum op op,int branch_taken,struct case_spec spec,char * log_buf,size_t log_sz,int * false_pos,int * true_pos)924 static int load_range_cmp_prog(struct range x, struct range y, enum op op,
925 int branch_taken, struct case_spec spec,
926 char *log_buf, size_t log_sz,
927 int *false_pos, int *true_pos)
928 {
929 #define emit(insn) ({ \
930 struct bpf_insn __insns[] = { insn }; \
931 int __i; \
932 for (__i = 0; __i < ARRAY_SIZE(__insns); __i++) \
933 insns[cur_pos + __i] = __insns[__i]; \
934 cur_pos += __i; \
935 })
936 #define JMP_TO(target) (target - cur_pos - 1)
937 int cur_pos = 0, exit_pos, fd, op_code;
938 struct bpf_insn insns[64];
939 LIBBPF_OPTS(bpf_prog_load_opts, opts,
940 .log_level = 2,
941 .log_buf = log_buf,
942 .log_size = log_sz,
943 .prog_flags = testing_prog_flags(),
944 );
945
946 /* ; skip exit block below
947 * goto +2;
948 */
949 emit(BPF_JMP_A(2));
950 exit_pos = cur_pos;
951 /* ; exit block for all the preparatory conditionals
952 * out:
953 * r0 = 0;
954 * exit;
955 */
956 emit(BPF_MOV64_IMM(BPF_REG_0, 0));
957 emit(BPF_EXIT_INSN());
958 /*
959 * ; assign r6/w6 and r7/w7 unpredictable u64/u32 value
960 * call bpf_get_current_pid_tgid;
961 * r6 = r0; | w6 = w0;
962 * call bpf_get_current_pid_tgid;
963 * r7 = r0; | w7 = w0;
964 */
965 emit(BPF_EMIT_CALL(BPF_FUNC_get_current_pid_tgid));
966 if (spec.init_subregs)
967 emit(BPF_MOV32_REG(BPF_REG_6, BPF_REG_0));
968 else
969 emit(BPF_MOV64_REG(BPF_REG_6, BPF_REG_0));
970 emit(BPF_EMIT_CALL(BPF_FUNC_get_current_pid_tgid));
971 if (spec.init_subregs)
972 emit(BPF_MOV32_REG(BPF_REG_7, BPF_REG_0));
973 else
974 emit(BPF_MOV64_REG(BPF_REG_7, BPF_REG_0));
975 /* ; setup initial r6/w6 possible value range ([x.a, x.b])
976 * r1 = %[x.a] ll; | w1 = %[x.a];
977 * r2 = %[x.b] ll; | w2 = %[x.b];
978 * if r6 < r1 goto out; | if w6 < w1 goto out;
979 * if r6 > r2 goto out; | if w6 > w2 goto out;
980 */
981 if (spec.setup_subregs) {
982 emit(BPF_MOV32_IMM(BPF_REG_1, (s32)x.a));
983 emit(BPF_MOV32_IMM(BPF_REG_2, (s32)x.b));
984 emit(BPF_JMP32_REG(spec.setup_signed ? BPF_JSLT : BPF_JLT,
985 BPF_REG_6, BPF_REG_1, JMP_TO(exit_pos)));
986 emit(BPF_JMP32_REG(spec.setup_signed ? BPF_JSGT : BPF_JGT,
987 BPF_REG_6, BPF_REG_2, JMP_TO(exit_pos)));
988 } else {
989 emit(BPF_LD_IMM64(BPF_REG_1, x.a));
990 emit(BPF_LD_IMM64(BPF_REG_2, x.b));
991 emit(BPF_JMP_REG(spec.setup_signed ? BPF_JSLT : BPF_JLT,
992 BPF_REG_6, BPF_REG_1, JMP_TO(exit_pos)));
993 emit(BPF_JMP_REG(spec.setup_signed ? BPF_JSGT : BPF_JGT,
994 BPF_REG_6, BPF_REG_2, JMP_TO(exit_pos)));
995 }
996 /* ; setup initial r7/w7 possible value range ([y.a, y.b])
997 * r1 = %[y.a] ll; | w1 = %[y.a];
998 * r2 = %[y.b] ll; | w2 = %[y.b];
999 * if r7 < r1 goto out; | if w7 < w1 goto out;
1000 * if r7 > r2 goto out; | if w7 > w2 goto out;
1001 */
1002 if (spec.setup_subregs) {
1003 emit(BPF_MOV32_IMM(BPF_REG_1, (s32)y.a));
1004 emit(BPF_MOV32_IMM(BPF_REG_2, (s32)y.b));
1005 emit(BPF_JMP32_REG(spec.setup_signed ? BPF_JSLT : BPF_JLT,
1006 BPF_REG_7, BPF_REG_1, JMP_TO(exit_pos)));
1007 emit(BPF_JMP32_REG(spec.setup_signed ? BPF_JSGT : BPF_JGT,
1008 BPF_REG_7, BPF_REG_2, JMP_TO(exit_pos)));
1009 } else {
1010 emit(BPF_LD_IMM64(BPF_REG_1, y.a));
1011 emit(BPF_LD_IMM64(BPF_REG_2, y.b));
1012 emit(BPF_JMP_REG(spec.setup_signed ? BPF_JSLT : BPF_JLT,
1013 BPF_REG_7, BPF_REG_1, JMP_TO(exit_pos)));
1014 emit(BPF_JMP_REG(spec.setup_signed ? BPF_JSGT : BPF_JGT,
1015 BPF_REG_7, BPF_REG_2, JMP_TO(exit_pos)));
1016 }
1017 /* ; range test instruction
1018 * if r6 <op> r7 goto +3; | if w6 <op> w7 goto +3;
1019 */
1020 switch (op) {
1021 case OP_LT: op_code = spec.compare_signed ? BPF_JSLT : BPF_JLT; break;
1022 case OP_LE: op_code = spec.compare_signed ? BPF_JSLE : BPF_JLE; break;
1023 case OP_GT: op_code = spec.compare_signed ? BPF_JSGT : BPF_JGT; break;
1024 case OP_GE: op_code = spec.compare_signed ? BPF_JSGE : BPF_JGE; break;
1025 case OP_EQ: op_code = BPF_JEQ; break;
1026 case OP_NE: op_code = BPF_JNE; break;
1027 default:
1028 printf("unrecognized op %d\n", op);
1029 return -ENOTSUP;
1030 }
1031 /* ; BEFORE conditional, r0/w0 = {r6/w6,r7/w7} is to extract verifier state reliably
1032 * ; this is used for debugging, as verifier doesn't always print
1033 * ; registers states as of condition jump instruction (e.g., when
1034 * ; precision marking happens)
1035 * r0 = r6; | w0 = w6;
1036 * r0 = r7; | w0 = w7;
1037 */
1038 if (spec.compare_subregs) {
1039 emit(BPF_MOV32_REG(BPF_REG_0, BPF_REG_6));
1040 emit(BPF_MOV32_REG(BPF_REG_0, BPF_REG_7));
1041 } else {
1042 emit(BPF_MOV64_REG(BPF_REG_0, BPF_REG_6));
1043 emit(BPF_MOV64_REG(BPF_REG_0, BPF_REG_7));
1044 }
1045 if (spec.compare_subregs)
1046 emit(BPF_JMP32_REG(op_code, BPF_REG_6, BPF_REG_7, 3));
1047 else
1048 emit(BPF_JMP_REG(op_code, BPF_REG_6, BPF_REG_7, 3));
1049 /* ; FALSE branch, r0/w0 = {r6/w6,r7/w7} is to extract verifier state reliably
1050 * r0 = r6; | w0 = w6;
1051 * r0 = r7; | w0 = w7;
1052 * exit;
1053 */
1054 *false_pos = cur_pos;
1055 if (spec.compare_subregs) {
1056 emit(BPF_MOV32_REG(BPF_REG_0, BPF_REG_6));
1057 emit(BPF_MOV32_REG(BPF_REG_0, BPF_REG_7));
1058 } else {
1059 emit(BPF_MOV64_REG(BPF_REG_0, BPF_REG_6));
1060 emit(BPF_MOV64_REG(BPF_REG_0, BPF_REG_7));
1061 }
1062 if (branch_taken == 1) /* false branch is never taken */
1063 emit(BPF_EMIT_CALL(0xDEAD)); /* poison this branch */
1064 else
1065 emit(BPF_EXIT_INSN());
1066 /* ; TRUE branch, r0/w0 = {r6/w6,r7/w7} is to extract verifier state reliably
1067 * r0 = r6; | w0 = w6;
1068 * r0 = r7; | w0 = w7;
1069 * exit;
1070 */
1071 *true_pos = cur_pos;
1072 if (spec.compare_subregs) {
1073 emit(BPF_MOV32_REG(BPF_REG_0, BPF_REG_6));
1074 emit(BPF_MOV32_REG(BPF_REG_0, BPF_REG_7));
1075 } else {
1076 emit(BPF_MOV64_REG(BPF_REG_0, BPF_REG_6));
1077 emit(BPF_MOV64_REG(BPF_REG_0, BPF_REG_7));
1078 }
1079 if (branch_taken == 0) /* true branch is never taken */
1080 emit(BPF_EMIT_CALL(0xDEAD)); /* poison this branch */
1081 emit(BPF_EXIT_INSN()); /* last instruction has to be exit */
1082
1083 fd = bpf_prog_load(BPF_PROG_TYPE_RAW_TRACEPOINT, "reg_bounds_test",
1084 "GPL", insns, cur_pos, &opts);
1085 if (fd < 0)
1086 return fd;
1087
1088 close(fd);
1089 return 0;
1090 #undef emit
1091 #undef JMP_TO
1092 }
1093
1094 #define str_has_pfx(str, pfx) (strncmp(str, pfx, strlen(pfx)) == 0)
1095
1096 /* Parse register state from verifier log.
1097 * `s` should point to the start of "Rx = ..." substring in the verifier log.
1098 */
parse_reg_state(const char * s,struct reg_state * reg)1099 static int parse_reg_state(const char *s, struct reg_state *reg)
1100 {
1101 /* There are two generic forms for SCALAR register:
1102 * - known constant: R6_rwD=P%lld
1103 * - range: R6_rwD=scalar(id=1,...), where "..." is a comma-separated
1104 * list of optional range specifiers:
1105 * - umin=%llu, if missing, assumed 0;
1106 * - umax=%llu, if missing, assumed U64_MAX;
1107 * - smin=%lld, if missing, assumed S64_MIN;
1108 * - smax=%lld, if missing, assumed S64_MAX;
1109 * - umin32=%d, if missing, assumed 0;
1110 * - umax32=%d, if missing, assumed U32_MAX;
1111 * - smin32=%d, if missing, assumed S32_MIN;
1112 * - smax32=%d, if missing, assumed S32_MAX;
1113 * - var_off=(%#llx; %#llx), tnum part, we don't care about it.
1114 *
1115 * If some of the values are equal, they will be grouped (but min/max
1116 * are not mixed together, and similarly negative values are not
1117 * grouped with non-negative ones). E.g.:
1118 *
1119 * R6_w=Pscalar(smin=smin32=0, smax=umax=umax32=1000)
1120 *
1121 * _rwD part is optional (and any of the letters can be missing).
1122 * P (precision mark) is optional as well.
1123 *
1124 * Anything inside scalar() is optional, including id, of course.
1125 */
1126 struct {
1127 const char *pfx;
1128 u64 *dst, def;
1129 bool is_32, is_set;
1130 } *f, fields[8] = {
1131 {"smin=", ®->r[S64].a, S64_MIN},
1132 {"smax=", ®->r[S64].b, S64_MAX},
1133 {"umin=", ®->r[U64].a, 0},
1134 {"umax=", ®->r[U64].b, U64_MAX},
1135 {"smin32=", ®->r[S32].a, (u32)S32_MIN, true},
1136 {"smax32=", ®->r[S32].b, (u32)S32_MAX, true},
1137 {"umin32=", ®->r[U32].a, 0, true},
1138 {"umax32=", ®->r[U32].b, U32_MAX, true},
1139 };
1140 const char *p;
1141 int i;
1142
1143 p = strchr(s, '=');
1144 if (!p)
1145 return -EINVAL;
1146 p++;
1147 if (*p == 'P')
1148 p++;
1149
1150 if (!str_has_pfx(p, "scalar(")) {
1151 long long sval;
1152 enum num_t t;
1153
1154 if (p[0] == '0' && p[1] == 'x') {
1155 if (sscanf(p, "%llx", &sval) != 1)
1156 return -EINVAL;
1157 } else {
1158 if (sscanf(p, "%lld", &sval) != 1)
1159 return -EINVAL;
1160 }
1161
1162 reg->valid = true;
1163 for (t = first_t; t <= last_t; t++) {
1164 reg->r[t] = range(t, sval, sval);
1165 }
1166 return 0;
1167 }
1168
1169 p += sizeof("scalar");
1170 while (p) {
1171 int midxs[ARRAY_SIZE(fields)], mcnt = 0;
1172 u64 val;
1173
1174 for (i = 0; i < ARRAY_SIZE(fields); i++) {
1175 f = &fields[i];
1176 if (!str_has_pfx(p, f->pfx))
1177 continue;
1178 midxs[mcnt++] = i;
1179 p += strlen(f->pfx);
1180 }
1181
1182 if (mcnt) {
1183 /* populate all matched fields */
1184 if (p[0] == '0' && p[1] == 'x') {
1185 if (sscanf(p, "%llx", &val) != 1)
1186 return -EINVAL;
1187 } else {
1188 if (sscanf(p, "%lld", &val) != 1)
1189 return -EINVAL;
1190 }
1191
1192 for (i = 0; i < mcnt; i++) {
1193 f = &fields[midxs[i]];
1194 f->is_set = true;
1195 *f->dst = f->is_32 ? (u64)(u32)val : val;
1196 }
1197 } else if (str_has_pfx(p, "var_off")) {
1198 /* skip "var_off=(0x0; 0x3f)" part completely */
1199 p = strchr(p, ')');
1200 if (!p)
1201 return -EINVAL;
1202 p++;
1203 }
1204
1205 p = strpbrk(p, ",)");
1206 if (*p == ')')
1207 break;
1208 if (p)
1209 p++;
1210 }
1211
1212 reg->valid = true;
1213
1214 for (i = 0; i < ARRAY_SIZE(fields); i++) {
1215 f = &fields[i];
1216 if (!f->is_set)
1217 *f->dst = f->def;
1218 }
1219
1220 return 0;
1221 }
1222
1223
1224 /* Parse all register states (TRUE/FALSE branches and DST/SRC registers)
1225 * out of the verifier log for a corresponding test case BPF program.
1226 */
parse_range_cmp_log(const char * log_buf,struct case_spec spec,int false_pos,int true_pos,struct reg_state * false1_reg,struct reg_state * false2_reg,struct reg_state * true1_reg,struct reg_state * true2_reg)1227 static int parse_range_cmp_log(const char *log_buf, struct case_spec spec,
1228 int false_pos, int true_pos,
1229 struct reg_state *false1_reg, struct reg_state *false2_reg,
1230 struct reg_state *true1_reg, struct reg_state *true2_reg)
1231 {
1232 struct {
1233 int insn_idx;
1234 int reg_idx;
1235 const char *reg_upper;
1236 struct reg_state *state;
1237 } specs[] = {
1238 {false_pos, 6, "R6=", false1_reg},
1239 {false_pos + 1, 7, "R7=", false2_reg},
1240 {true_pos, 6, "R6=", true1_reg},
1241 {true_pos + 1, 7, "R7=", true2_reg},
1242 };
1243 char buf[32];
1244 const char *p = log_buf, *q;
1245 int i, err;
1246
1247 for (i = 0; i < 4; i++) {
1248 sprintf(buf, "%d: (%s) %s = %s%d", specs[i].insn_idx,
1249 spec.compare_subregs ? "bc" : "bf",
1250 spec.compare_subregs ? "w0" : "r0",
1251 spec.compare_subregs ? "w" : "r", specs[i].reg_idx);
1252
1253 /*
1254 * In the verifier log look for lines:
1255 * 18: (bf) r0 = r6 ; R0=... R6=...
1256 * Different verifier passes may print
1257 * 18: (bf) r0 = r6
1258 * as well, but never followed by ';'.
1259 */
1260 q = p;
1261 while ((q = strstr(q, buf)) != NULL) {
1262 const char *s = q + strlen(buf);
1263
1264 while (*s == ' ' || *s == '\t')
1265 s++;
1266 if (*s == ';')
1267 break;
1268 q = s;
1269 }
1270 if (!q) {
1271 *specs[i].state = (struct reg_state){.valid = false};
1272 continue;
1273 }
1274 p = strstr(q, specs[i].reg_upper);
1275 if (!p)
1276 return -EINVAL;
1277 err = parse_reg_state(p, specs[i].state);
1278 if (err)
1279 return -EINVAL;
1280 }
1281 return 0;
1282 }
1283
1284 /* Validate ranges match, and print details if they don't */
assert_range_eq(enum num_t t,struct range x,struct range y,const char * ctx1,const char * ctx2)1285 static bool assert_range_eq(enum num_t t, struct range x, struct range y,
1286 const char *ctx1, const char *ctx2)
1287 {
1288 DEFINE_STRBUF(sb, 512);
1289
1290 if (range_eq(x, y))
1291 return true;
1292
1293 snappendf(sb, "MISMATCH %s.%s: ", ctx1, ctx2);
1294 snprintf_range(t, sb, x);
1295 snappendf(sb, " != ");
1296 snprintf_range(t, sb, y);
1297
1298 printf("%s\n", sb->buf);
1299
1300 return false;
1301 }
1302
1303 /* Validate that register states match, and print details if they don't */
assert_reg_state_eq(struct reg_state * r,struct reg_state * e,const char * ctx)1304 static bool assert_reg_state_eq(struct reg_state *r, struct reg_state *e, const char *ctx)
1305 {
1306 bool ok = true;
1307 enum num_t t;
1308
1309 if (r->valid != e->valid) {
1310 printf("MISMATCH %s: actual %s != expected %s\n", ctx,
1311 r->valid ? "<valid>" : "<invalid>",
1312 e->valid ? "<valid>" : "<invalid>");
1313 return false;
1314 }
1315
1316 if (!r->valid)
1317 return true;
1318
1319 for (t = first_t; t <= last_t; t++) {
1320 if (!assert_range_eq(t, r->r[t], e->r[t], ctx, t_str(t)))
1321 ok = false;
1322 }
1323
1324 return ok;
1325 }
1326
1327 /* Printf verifier log, filtering out irrelevant noise */
print_verifier_log(const char * buf)1328 static void print_verifier_log(const char *buf)
1329 {
1330 const char *p;
1331
1332 while (buf[0]) {
1333 p = strchrnul(buf, '\n');
1334
1335 /* filter out irrelevant precision backtracking logs */
1336 if (str_has_pfx(buf, "mark_precise: "))
1337 goto skip_line;
1338
1339 printf("%.*s\n", (int)(p - buf), buf);
1340
1341 skip_line:
1342 buf = *p == '\0' ? p : p + 1;
1343 }
1344 }
1345
1346 /* Simulate provided test case purely with our own range-based logic.
1347 * This is done to set up expectations for verifier's branch_taken logic and
1348 * verifier's register states in the verifier log.
1349 */
sim_case(enum num_t init_t,enum num_t cond_t,struct range x,struct range y,enum op op,struct reg_state * fr1,struct reg_state * fr2,struct reg_state * tr1,struct reg_state * tr2,int * branch_taken)1350 static void sim_case(enum num_t init_t, enum num_t cond_t,
1351 struct range x, struct range y, enum op op,
1352 struct reg_state *fr1, struct reg_state *fr2,
1353 struct reg_state *tr1, struct reg_state *tr2,
1354 int *branch_taken)
1355 {
1356 const u64 A = x.a;
1357 const u64 B = x.b;
1358 const u64 C = y.a;
1359 const u64 D = y.b;
1360 struct reg_state rc;
1361 enum op rev_op = complement_op(op);
1362 enum num_t t;
1363
1364 fr1->valid = fr2->valid = true;
1365 tr1->valid = tr2->valid = true;
1366 for (t = first_t; t <= last_t; t++) {
1367 /* if we are initializing using 32-bit subregisters,
1368 * full registers get upper 32 bits zeroed automatically
1369 */
1370 struct range z = t_is_32(init_t) ? unkn_subreg(t) : unkn[t];
1371
1372 fr1->r[t] = fr2->r[t] = tr1->r[t] = tr2->r[t] = z;
1373 }
1374
1375 /* step 1: r1 >= A, r2 >= C */
1376 reg_state_set_const(&rc, init_t, A);
1377 reg_state_cond(init_t, fr1, &rc, OP_GE, fr1, NULL, "r1>=A");
1378 reg_state_set_const(&rc, init_t, C);
1379 reg_state_cond(init_t, fr2, &rc, OP_GE, fr2, NULL, "r2>=C");
1380 *tr1 = *fr1;
1381 *tr2 = *fr2;
1382 if (env.verbosity >= VERBOSE_VERY) {
1383 printf("STEP1 (%s) R1: ", t_str(init_t)); print_reg_state(fr1, "\n");
1384 printf("STEP1 (%s) R2: ", t_str(init_t)); print_reg_state(fr2, "\n");
1385 }
1386
1387 /* step 2: r1 <= B, r2 <= D */
1388 reg_state_set_const(&rc, init_t, B);
1389 reg_state_cond(init_t, fr1, &rc, OP_LE, fr1, NULL, "r1<=B");
1390 reg_state_set_const(&rc, init_t, D);
1391 reg_state_cond(init_t, fr2, &rc, OP_LE, fr2, NULL, "r2<=D");
1392 *tr1 = *fr1;
1393 *tr2 = *fr2;
1394 if (env.verbosity >= VERBOSE_VERY) {
1395 printf("STEP2 (%s) R1: ", t_str(init_t)); print_reg_state(fr1, "\n");
1396 printf("STEP2 (%s) R2: ", t_str(init_t)); print_reg_state(fr2, "\n");
1397 }
1398
1399 /* step 3: r1 <op> r2 */
1400 *branch_taken = reg_state_branch_taken_op(cond_t, fr1, fr2, op);
1401 fr1->valid = fr2->valid = false;
1402 tr1->valid = tr2->valid = false;
1403 if (*branch_taken != 1) { /* FALSE is possible */
1404 fr1->valid = fr2->valid = true;
1405 reg_state_cond(cond_t, fr1, fr2, rev_op, fr1, fr2, "FALSE");
1406 }
1407 if (*branch_taken != 0) { /* TRUE is possible */
1408 tr1->valid = tr2->valid = true;
1409 reg_state_cond(cond_t, tr1, tr2, op, tr1, tr2, "TRUE");
1410 }
1411 if (env.verbosity >= VERBOSE_VERY) {
1412 printf("STEP3 (%s) FALSE R1:", t_str(cond_t)); print_reg_state(fr1, "\n");
1413 printf("STEP3 (%s) FALSE R2:", t_str(cond_t)); print_reg_state(fr2, "\n");
1414 printf("STEP3 (%s) TRUE R1:", t_str(cond_t)); print_reg_state(tr1, "\n");
1415 printf("STEP3 (%s) TRUE R2:", t_str(cond_t)); print_reg_state(tr2, "\n");
1416 }
1417 }
1418
1419 /* ===============================
1420 * HIGH-LEVEL TEST CASE VALIDATION
1421 * ===============================
1422 */
1423 static u32 upper_seeds[] = {
1424 0,
1425 1,
1426 U32_MAX,
1427 U32_MAX - 1,
1428 S32_MAX,
1429 (u32)S32_MIN,
1430 };
1431
1432 static u32 lower_seeds[] = {
1433 0,
1434 1,
1435 2, (u32)-2,
1436 255, (u32)-255,
1437 UINT_MAX,
1438 UINT_MAX - 1,
1439 INT_MAX,
1440 (u32)INT_MIN,
1441 };
1442
1443 struct ctx {
1444 int val_cnt, subval_cnt, range_cnt, subrange_cnt;
1445 u64 uvals[ARRAY_SIZE(upper_seeds) * ARRAY_SIZE(lower_seeds)];
1446 s64 svals[ARRAY_SIZE(upper_seeds) * ARRAY_SIZE(lower_seeds)];
1447 u32 usubvals[ARRAY_SIZE(lower_seeds)];
1448 s32 ssubvals[ARRAY_SIZE(lower_seeds)];
1449 struct range *uranges, *sranges;
1450 struct range *usubranges, *ssubranges;
1451 int max_failure_cnt, cur_failure_cnt;
1452 int total_case_cnt, case_cnt;
1453 int rand_case_cnt;
1454 unsigned rand_seed;
1455 __u64 start_ns;
1456 char progress_ctx[64];
1457 };
1458
cleanup_ctx(struct ctx * ctx)1459 static void cleanup_ctx(struct ctx *ctx)
1460 {
1461 free(ctx->uranges);
1462 free(ctx->sranges);
1463 free(ctx->usubranges);
1464 free(ctx->ssubranges);
1465 }
1466
1467 struct subtest_case {
1468 enum num_t init_t;
1469 enum num_t cond_t;
1470 struct range x;
1471 struct range y;
1472 enum op op;
1473 };
1474
subtest_case_str(struct strbuf * sb,struct subtest_case * t,bool use_op)1475 static void subtest_case_str(struct strbuf *sb, struct subtest_case *t, bool use_op)
1476 {
1477 snappendf(sb, "(%s)", t_str(t->init_t));
1478 snprintf_range(t->init_t, sb, t->x);
1479 snappendf(sb, " (%s)%s ", t_str(t->cond_t), use_op ? op_str(t->op) : "<op>");
1480 snprintf_range(t->init_t, sb, t->y);
1481 }
1482
1483 /* Generate and validate test case based on specific combination of setup
1484 * register ranges (including their expected num_t domain), and conditional
1485 * operation to perform (including num_t domain in which it has to be
1486 * performed)
1487 */
verify_case_op(enum num_t init_t,enum num_t cond_t,struct range x,struct range y,enum op op)1488 static int verify_case_op(enum num_t init_t, enum num_t cond_t,
1489 struct range x, struct range y, enum op op)
1490 {
1491 char log_buf[256 * 1024];
1492 size_t log_sz = sizeof(log_buf);
1493 int err, false_pos = 0, true_pos = 0, branch_taken;
1494 struct reg_state fr1, fr2, tr1, tr2;
1495 struct reg_state fe1, fe2, te1, te2;
1496 bool failed = false;
1497 struct case_spec spec = {
1498 .init_subregs = (init_t == U32 || init_t == S32),
1499 .setup_subregs = (init_t == U32 || init_t == S32),
1500 .setup_signed = (init_t == S64 || init_t == S32),
1501 .compare_subregs = (cond_t == U32 || cond_t == S32),
1502 .compare_signed = (cond_t == S64 || cond_t == S32),
1503 };
1504
1505 log_buf[0] = '\0';
1506
1507 sim_case(init_t, cond_t, x, y, op, &fe1, &fe2, &te1, &te2, &branch_taken);
1508
1509 err = load_range_cmp_prog(x, y, op, branch_taken, spec,
1510 log_buf, log_sz, &false_pos, &true_pos);
1511 if (err) {
1512 ASSERT_OK(err, "load_range_cmp_prog");
1513 failed = true;
1514 }
1515
1516 err = parse_range_cmp_log(log_buf, spec, false_pos, true_pos,
1517 &fr1, &fr2, &tr1, &tr2);
1518 if (err) {
1519 ASSERT_OK(err, "parse_range_cmp_log");
1520 failed = true;
1521 }
1522
1523 if (!assert_reg_state_eq(&fr1, &fe1, "false_reg1") ||
1524 !assert_reg_state_eq(&fr2, &fe2, "false_reg2") ||
1525 !assert_reg_state_eq(&tr1, &te1, "true_reg1") ||
1526 !assert_reg_state_eq(&tr2, &te2, "true_reg2")) {
1527 failed = true;
1528 }
1529
1530 if (failed || env.verbosity >= VERBOSE_NORMAL) {
1531 if (failed || env.verbosity >= VERBOSE_VERY) {
1532 printf("VERIFIER LOG:\n========================\n");
1533 print_verifier_log(log_buf);
1534 printf("=====================\n");
1535 }
1536 printf("ACTUAL FALSE1: "); print_reg_state(&fr1, "\n");
1537 printf("EXPECTED FALSE1: "); print_reg_state(&fe1, "\n");
1538 printf("ACTUAL FALSE2: "); print_reg_state(&fr2, "\n");
1539 printf("EXPECTED FALSE2: "); print_reg_state(&fe2, "\n");
1540 printf("ACTUAL TRUE1: "); print_reg_state(&tr1, "\n");
1541 printf("EXPECTED TRUE1: "); print_reg_state(&te1, "\n");
1542 printf("ACTUAL TRUE2: "); print_reg_state(&tr2, "\n");
1543 printf("EXPECTED TRUE2: "); print_reg_state(&te2, "\n");
1544
1545 return failed ? -EINVAL : 0;
1546 }
1547
1548 return 0;
1549 }
1550
1551 /* Given setup ranges and number types, go over all supported operations,
1552 * generating individual subtest for each allowed combination
1553 */
verify_case_opt(struct ctx * ctx,enum num_t init_t,enum num_t cond_t,struct range x,struct range y,bool is_subtest)1554 static int verify_case_opt(struct ctx *ctx, enum num_t init_t, enum num_t cond_t,
1555 struct range x, struct range y, bool is_subtest)
1556 {
1557 DEFINE_STRBUF(sb, 256);
1558 int err;
1559 struct subtest_case sub = {
1560 .init_t = init_t,
1561 .cond_t = cond_t,
1562 .x = x,
1563 .y = y,
1564 };
1565
1566 sb->pos = 0; /* reset position in strbuf */
1567 subtest_case_str(sb, &sub, false /* ignore op */);
1568 if (is_subtest && !test__start_subtest(sb->buf))
1569 return 0;
1570
1571 for (sub.op = first_op; sub.op <= last_op; sub.op++) {
1572 sb->pos = 0; /* reset position in strbuf */
1573 subtest_case_str(sb, &sub, true /* print op */);
1574
1575 if (env.verbosity >= VERBOSE_NORMAL) /* this speeds up debugging */
1576 printf("TEST CASE: %s\n", sb->buf);
1577
1578 err = verify_case_op(init_t, cond_t, x, y, sub.op);
1579 if (err || env.verbosity >= VERBOSE_NORMAL)
1580 ASSERT_OK(err, sb->buf);
1581 if (err) {
1582 ctx->cur_failure_cnt++;
1583 if (ctx->cur_failure_cnt > ctx->max_failure_cnt)
1584 return err;
1585 return 0; /* keep testing other cases */
1586 }
1587 ctx->case_cnt++;
1588 if ((ctx->case_cnt % 10000) == 0) {
1589 double progress = (ctx->case_cnt + 0.0) / ctx->total_case_cnt;
1590 u64 elapsed_ns = get_time_ns() - ctx->start_ns;
1591 double remain_ns = elapsed_ns / progress * (1 - progress);
1592
1593 fprintf(env.stderr_saved, "PROGRESS (%s): %d/%d (%.2lf%%), "
1594 "elapsed %llu mins (%.2lf hrs), "
1595 "ETA %.0lf mins (%.2lf hrs)\n",
1596 ctx->progress_ctx,
1597 ctx->case_cnt, ctx->total_case_cnt, 100.0 * progress,
1598 elapsed_ns / 1000000000 / 60,
1599 elapsed_ns / 1000000000.0 / 3600,
1600 remain_ns / 1000000000.0 / 60,
1601 remain_ns / 1000000000.0 / 3600);
1602 }
1603 }
1604
1605 return 0;
1606 }
1607
verify_case(struct ctx * ctx,enum num_t init_t,enum num_t cond_t,struct range x,struct range y)1608 static int verify_case(struct ctx *ctx, enum num_t init_t, enum num_t cond_t,
1609 struct range x, struct range y)
1610 {
1611 return verify_case_opt(ctx, init_t, cond_t, x, y, true /* is_subtest */);
1612 }
1613
1614 /* ================================
1615 * GENERATED CASES FROM SEED VALUES
1616 * ================================
1617 */
u64_cmp(const void * p1,const void * p2)1618 static int u64_cmp(const void *p1, const void *p2)
1619 {
1620 u64 x1 = *(const u64 *)p1, x2 = *(const u64 *)p2;
1621
1622 return x1 != x2 ? (x1 < x2 ? -1 : 1) : 0;
1623 }
1624
u32_cmp(const void * p1,const void * p2)1625 static int u32_cmp(const void *p1, const void *p2)
1626 {
1627 u32 x1 = *(const u32 *)p1, x2 = *(const u32 *)p2;
1628
1629 return x1 != x2 ? (x1 < x2 ? -1 : 1) : 0;
1630 }
1631
s64_cmp(const void * p1,const void * p2)1632 static int s64_cmp(const void *p1, const void *p2)
1633 {
1634 s64 x1 = *(const s64 *)p1, x2 = *(const s64 *)p2;
1635
1636 return x1 != x2 ? (x1 < x2 ? -1 : 1) : 0;
1637 }
1638
s32_cmp(const void * p1,const void * p2)1639 static int s32_cmp(const void *p1, const void *p2)
1640 {
1641 s32 x1 = *(const s32 *)p1, x2 = *(const s32 *)p2;
1642
1643 return x1 != x2 ? (x1 < x2 ? -1 : 1) : 0;
1644 }
1645
1646 /* Generate valid unique constants from seeds, both signed and unsigned */
gen_vals(struct ctx * ctx)1647 static void gen_vals(struct ctx *ctx)
1648 {
1649 int i, j, cnt = 0;
1650
1651 for (i = 0; i < ARRAY_SIZE(upper_seeds); i++) {
1652 for (j = 0; j < ARRAY_SIZE(lower_seeds); j++) {
1653 ctx->uvals[cnt++] = (((u64)upper_seeds[i]) << 32) | lower_seeds[j];
1654 }
1655 }
1656
1657 /* sort and compact uvals (i.e., it's `sort | uniq`) */
1658 qsort(ctx->uvals, cnt, sizeof(*ctx->uvals), u64_cmp);
1659 for (i = 1, j = 0; i < cnt; i++) {
1660 if (ctx->uvals[j] == ctx->uvals[i])
1661 continue;
1662 j++;
1663 ctx->uvals[j] = ctx->uvals[i];
1664 }
1665 ctx->val_cnt = j + 1;
1666
1667 /* we have exactly the same number of s64 values, they are just in
1668 * a different order than u64s, so just sort them differently
1669 */
1670 for (i = 0; i < ctx->val_cnt; i++)
1671 ctx->svals[i] = ctx->uvals[i];
1672 qsort(ctx->svals, ctx->val_cnt, sizeof(*ctx->svals), s64_cmp);
1673
1674 if (env.verbosity >= VERBOSE_SUPER) {
1675 DEFINE_STRBUF(sb1, 256);
1676 DEFINE_STRBUF(sb2, 256);
1677
1678 for (i = 0; i < ctx->val_cnt; i++) {
1679 sb1->pos = sb2->pos = 0;
1680 snprintf_num(U64, sb1, ctx->uvals[i]);
1681 snprintf_num(S64, sb2, ctx->svals[i]);
1682 printf("SEED #%d: u64=%-20s s64=%-20s\n", i, sb1->buf, sb2->buf);
1683 }
1684 }
1685
1686 /* 32-bit values are generated separately */
1687 cnt = 0;
1688 for (i = 0; i < ARRAY_SIZE(lower_seeds); i++) {
1689 ctx->usubvals[cnt++] = lower_seeds[i];
1690 }
1691
1692 /* sort and compact usubvals (i.e., it's `sort | uniq`) */
1693 qsort(ctx->usubvals, cnt, sizeof(*ctx->usubvals), u32_cmp);
1694 for (i = 1, j = 0; i < cnt; i++) {
1695 if (ctx->usubvals[j] == ctx->usubvals[i])
1696 continue;
1697 j++;
1698 ctx->usubvals[j] = ctx->usubvals[i];
1699 }
1700 ctx->subval_cnt = j + 1;
1701
1702 for (i = 0; i < ctx->subval_cnt; i++)
1703 ctx->ssubvals[i] = ctx->usubvals[i];
1704 qsort(ctx->ssubvals, ctx->subval_cnt, sizeof(*ctx->ssubvals), s32_cmp);
1705
1706 if (env.verbosity >= VERBOSE_SUPER) {
1707 DEFINE_STRBUF(sb1, 256);
1708 DEFINE_STRBUF(sb2, 256);
1709
1710 for (i = 0; i < ctx->subval_cnt; i++) {
1711 sb1->pos = sb2->pos = 0;
1712 snprintf_num(U32, sb1, ctx->usubvals[i]);
1713 snprintf_num(S32, sb2, ctx->ssubvals[i]);
1714 printf("SUBSEED #%d: u32=%-10s s32=%-10s\n", i, sb1->buf, sb2->buf);
1715 }
1716 }
1717 }
1718
1719 /* Generate valid ranges from upper/lower seeds */
gen_ranges(struct ctx * ctx)1720 static int gen_ranges(struct ctx *ctx)
1721 {
1722 int i, j, cnt = 0;
1723
1724 for (i = 0; i < ctx->val_cnt; i++) {
1725 for (j = i; j < ctx->val_cnt; j++) {
1726 if (env.verbosity >= VERBOSE_SUPER) {
1727 DEFINE_STRBUF(sb1, 256);
1728 DEFINE_STRBUF(sb2, 256);
1729
1730 sb1->pos = sb2->pos = 0;
1731 snprintf_range(U64, sb1, range(U64, ctx->uvals[i], ctx->uvals[j]));
1732 snprintf_range(S64, sb2, range(S64, ctx->svals[i], ctx->svals[j]));
1733 printf("RANGE #%d: u64=%-40s s64=%-40s\n", cnt, sb1->buf, sb2->buf);
1734 }
1735 cnt++;
1736 }
1737 }
1738 ctx->range_cnt = cnt;
1739
1740 ctx->uranges = calloc(ctx->range_cnt, sizeof(*ctx->uranges));
1741 if (!ASSERT_OK_PTR(ctx->uranges, "uranges_calloc"))
1742 return -EINVAL;
1743 ctx->sranges = calloc(ctx->range_cnt, sizeof(*ctx->sranges));
1744 if (!ASSERT_OK_PTR(ctx->sranges, "sranges_calloc"))
1745 return -EINVAL;
1746
1747 cnt = 0;
1748 for (i = 0; i < ctx->val_cnt; i++) {
1749 for (j = i; j < ctx->val_cnt; j++) {
1750 ctx->uranges[cnt] = range(U64, ctx->uvals[i], ctx->uvals[j]);
1751 ctx->sranges[cnt] = range(S64, ctx->svals[i], ctx->svals[j]);
1752 cnt++;
1753 }
1754 }
1755
1756 cnt = 0;
1757 for (i = 0; i < ctx->subval_cnt; i++) {
1758 for (j = i; j < ctx->subval_cnt; j++) {
1759 if (env.verbosity >= VERBOSE_SUPER) {
1760 DEFINE_STRBUF(sb1, 256);
1761 DEFINE_STRBUF(sb2, 256);
1762
1763 sb1->pos = sb2->pos = 0;
1764 snprintf_range(U32, sb1, range(U32, ctx->usubvals[i], ctx->usubvals[j]));
1765 snprintf_range(S32, sb2, range(S32, ctx->ssubvals[i], ctx->ssubvals[j]));
1766 printf("SUBRANGE #%d: u32=%-20s s32=%-20s\n", cnt, sb1->buf, sb2->buf);
1767 }
1768 cnt++;
1769 }
1770 }
1771 ctx->subrange_cnt = cnt;
1772
1773 ctx->usubranges = calloc(ctx->subrange_cnt, sizeof(*ctx->usubranges));
1774 if (!ASSERT_OK_PTR(ctx->usubranges, "usubranges_calloc"))
1775 return -EINVAL;
1776 ctx->ssubranges = calloc(ctx->subrange_cnt, sizeof(*ctx->ssubranges));
1777 if (!ASSERT_OK_PTR(ctx->ssubranges, "ssubranges_calloc"))
1778 return -EINVAL;
1779
1780 cnt = 0;
1781 for (i = 0; i < ctx->subval_cnt; i++) {
1782 for (j = i; j < ctx->subval_cnt; j++) {
1783 ctx->usubranges[cnt] = range(U32, ctx->usubvals[i], ctx->usubvals[j]);
1784 ctx->ssubranges[cnt] = range(S32, ctx->ssubvals[i], ctx->ssubvals[j]);
1785 cnt++;
1786 }
1787 }
1788
1789 return 0;
1790 }
1791
parse_env_vars(struct ctx * ctx)1792 static int parse_env_vars(struct ctx *ctx)
1793 {
1794 const char *s;
1795
1796 if ((s = getenv("REG_BOUNDS_MAX_FAILURE_CNT"))) {
1797 errno = 0;
1798 ctx->max_failure_cnt = strtol(s, NULL, 10);
1799 if (errno || ctx->max_failure_cnt < 0) {
1800 ASSERT_OK(-errno, "REG_BOUNDS_MAX_FAILURE_CNT");
1801 return -EINVAL;
1802 }
1803 }
1804
1805 if ((s = getenv("REG_BOUNDS_RAND_CASE_CNT"))) {
1806 errno = 0;
1807 ctx->rand_case_cnt = strtol(s, NULL, 10);
1808 if (errno || ctx->rand_case_cnt < 0) {
1809 ASSERT_OK(-errno, "REG_BOUNDS_RAND_CASE_CNT");
1810 return -EINVAL;
1811 }
1812 }
1813
1814 if ((s = getenv("REG_BOUNDS_RAND_SEED"))) {
1815 errno = 0;
1816 ctx->rand_seed = strtoul(s, NULL, 10);
1817 if (errno) {
1818 ASSERT_OK(-errno, "REG_BOUNDS_RAND_SEED");
1819 return -EINVAL;
1820 }
1821 }
1822
1823 return 0;
1824 }
1825
prepare_gen_tests(struct ctx * ctx)1826 static int prepare_gen_tests(struct ctx *ctx)
1827 {
1828 const char *s;
1829 int err;
1830
1831 if (!(s = getenv("SLOW_TESTS")) || strcmp(s, "1") != 0) {
1832 test__skip();
1833 return -ENOTSUP;
1834 }
1835
1836 err = parse_env_vars(ctx);
1837 if (err)
1838 return err;
1839
1840 gen_vals(ctx);
1841 err = gen_ranges(ctx);
1842 if (err) {
1843 ASSERT_OK(err, "gen_ranges");
1844 return err;
1845 }
1846
1847 return 0;
1848 }
1849
1850 /* Go over generated constants and ranges and validate various supported
1851 * combinations of them
1852 */
validate_gen_range_vs_const_64(enum num_t init_t,enum num_t cond_t)1853 static void validate_gen_range_vs_const_64(enum num_t init_t, enum num_t cond_t)
1854 {
1855 struct ctx ctx;
1856 struct range rconst;
1857 const struct range *ranges;
1858 const u64 *vals;
1859 int i, j;
1860
1861 memset(&ctx, 0, sizeof(ctx));
1862
1863 if (prepare_gen_tests(&ctx))
1864 goto cleanup;
1865
1866 ranges = init_t == U64 ? ctx.uranges : ctx.sranges;
1867 vals = init_t == U64 ? ctx.uvals : (const u64 *)ctx.svals;
1868
1869 ctx.total_case_cnt = (last_op - first_op + 1) * (2 * ctx.range_cnt * ctx.val_cnt);
1870 ctx.start_ns = get_time_ns();
1871 snprintf(ctx.progress_ctx, sizeof(ctx.progress_ctx),
1872 "RANGE x CONST, %s -> %s",
1873 t_str(init_t), t_str(cond_t));
1874
1875 for (i = 0; i < ctx.val_cnt; i++) {
1876 for (j = 0; j < ctx.range_cnt; j++) {
1877 rconst = range(init_t, vals[i], vals[i]);
1878
1879 /* (u64|s64)(<range> x <const>) */
1880 if (verify_case(&ctx, init_t, cond_t, ranges[j], rconst))
1881 goto cleanup;
1882 /* (u64|s64)(<const> x <range>) */
1883 if (verify_case(&ctx, init_t, cond_t, rconst, ranges[j]))
1884 goto cleanup;
1885 }
1886 }
1887
1888 cleanup:
1889 cleanup_ctx(&ctx);
1890 }
1891
validate_gen_range_vs_const_32(enum num_t init_t,enum num_t cond_t)1892 static void validate_gen_range_vs_const_32(enum num_t init_t, enum num_t cond_t)
1893 {
1894 struct ctx ctx;
1895 struct range rconst;
1896 const struct range *ranges;
1897 const u32 *vals;
1898 int i, j;
1899
1900 memset(&ctx, 0, sizeof(ctx));
1901
1902 if (prepare_gen_tests(&ctx))
1903 goto cleanup;
1904
1905 ranges = init_t == U32 ? ctx.usubranges : ctx.ssubranges;
1906 vals = init_t == U32 ? ctx.usubvals : (const u32 *)ctx.ssubvals;
1907
1908 ctx.total_case_cnt = (last_op - first_op + 1) * (2 * ctx.subrange_cnt * ctx.subval_cnt);
1909 ctx.start_ns = get_time_ns();
1910 snprintf(ctx.progress_ctx, sizeof(ctx.progress_ctx),
1911 "RANGE x CONST, %s -> %s",
1912 t_str(init_t), t_str(cond_t));
1913
1914 for (i = 0; i < ctx.subval_cnt; i++) {
1915 for (j = 0; j < ctx.subrange_cnt; j++) {
1916 rconst = range(init_t, vals[i], vals[i]);
1917
1918 /* (u32|s32)(<range> x <const>) */
1919 if (verify_case(&ctx, init_t, cond_t, ranges[j], rconst))
1920 goto cleanup;
1921 /* (u32|s32)(<const> x <range>) */
1922 if (verify_case(&ctx, init_t, cond_t, rconst, ranges[j]))
1923 goto cleanup;
1924 }
1925 }
1926
1927 cleanup:
1928 cleanup_ctx(&ctx);
1929 }
1930
validate_gen_range_vs_range(enum num_t init_t,enum num_t cond_t)1931 static void validate_gen_range_vs_range(enum num_t init_t, enum num_t cond_t)
1932 {
1933 struct ctx ctx;
1934 const struct range *ranges;
1935 int i, j, rcnt;
1936
1937 memset(&ctx, 0, sizeof(ctx));
1938
1939 if (prepare_gen_tests(&ctx))
1940 goto cleanup;
1941
1942 switch (init_t)
1943 {
1944 case U64:
1945 ranges = ctx.uranges;
1946 rcnt = ctx.range_cnt;
1947 break;
1948 case U32:
1949 ranges = ctx.usubranges;
1950 rcnt = ctx.subrange_cnt;
1951 break;
1952 case S64:
1953 ranges = ctx.sranges;
1954 rcnt = ctx.range_cnt;
1955 break;
1956 case S32:
1957 ranges = ctx.ssubranges;
1958 rcnt = ctx.subrange_cnt;
1959 break;
1960 default:
1961 printf("validate_gen_range_vs_range!\n");
1962 exit(1);
1963 }
1964
1965 ctx.total_case_cnt = (last_op - first_op + 1) * (2 * rcnt * (rcnt + 1) / 2);
1966 ctx.start_ns = get_time_ns();
1967 snprintf(ctx.progress_ctx, sizeof(ctx.progress_ctx),
1968 "RANGE x RANGE, %s -> %s",
1969 t_str(init_t), t_str(cond_t));
1970
1971 for (i = 0; i < rcnt; i++) {
1972 for (j = i; j < rcnt; j++) {
1973 /* (<range> x <range>) */
1974 if (verify_case(&ctx, init_t, cond_t, ranges[i], ranges[j]))
1975 goto cleanup;
1976 if (verify_case(&ctx, init_t, cond_t, ranges[j], ranges[i]))
1977 goto cleanup;
1978 }
1979 }
1980
1981 cleanup:
1982 cleanup_ctx(&ctx);
1983 }
1984
1985 /* Go over thousands of test cases generated from initial seed values.
1986 * Given this take a long time, guard this begind SLOW_TESTS=1 envvar. If
1987 * envvar is not set, this test is skipped during test_progs testing.
1988 *
1989 * We split this up into smaller subsets based on initialization and
1990 * conditional numeric domains to get an easy parallelization with test_progs'
1991 * -j argument.
1992 */
1993
1994 /* RANGE x CONST, U64 initial range */
test_reg_bounds_gen_consts_u64_u64(void)1995 void test_reg_bounds_gen_consts_u64_u64(void) { validate_gen_range_vs_const_64(U64, U64); }
test_reg_bounds_gen_consts_u64_s64(void)1996 void test_reg_bounds_gen_consts_u64_s64(void) { validate_gen_range_vs_const_64(U64, S64); }
test_reg_bounds_gen_consts_u64_u32(void)1997 void test_reg_bounds_gen_consts_u64_u32(void) { validate_gen_range_vs_const_64(U64, U32); }
test_reg_bounds_gen_consts_u64_s32(void)1998 void test_reg_bounds_gen_consts_u64_s32(void) { validate_gen_range_vs_const_64(U64, S32); }
1999 /* RANGE x CONST, S64 initial range */
test_reg_bounds_gen_consts_s64_u64(void)2000 void test_reg_bounds_gen_consts_s64_u64(void) { validate_gen_range_vs_const_64(S64, U64); }
test_reg_bounds_gen_consts_s64_s64(void)2001 void test_reg_bounds_gen_consts_s64_s64(void) { validate_gen_range_vs_const_64(S64, S64); }
test_reg_bounds_gen_consts_s64_u32(void)2002 void test_reg_bounds_gen_consts_s64_u32(void) { validate_gen_range_vs_const_64(S64, U32); }
test_reg_bounds_gen_consts_s64_s32(void)2003 void test_reg_bounds_gen_consts_s64_s32(void) { validate_gen_range_vs_const_64(S64, S32); }
2004 /* RANGE x CONST, U32 initial range */
test_reg_bounds_gen_consts_u32_u64(void)2005 void test_reg_bounds_gen_consts_u32_u64(void) { validate_gen_range_vs_const_32(U32, U64); }
test_reg_bounds_gen_consts_u32_s64(void)2006 void test_reg_bounds_gen_consts_u32_s64(void) { validate_gen_range_vs_const_32(U32, S64); }
test_reg_bounds_gen_consts_u32_u32(void)2007 void test_reg_bounds_gen_consts_u32_u32(void) { validate_gen_range_vs_const_32(U32, U32); }
test_reg_bounds_gen_consts_u32_s32(void)2008 void test_reg_bounds_gen_consts_u32_s32(void) { validate_gen_range_vs_const_32(U32, S32); }
2009 /* RANGE x CONST, S32 initial range */
test_reg_bounds_gen_consts_s32_u64(void)2010 void test_reg_bounds_gen_consts_s32_u64(void) { validate_gen_range_vs_const_32(S32, U64); }
test_reg_bounds_gen_consts_s32_s64(void)2011 void test_reg_bounds_gen_consts_s32_s64(void) { validate_gen_range_vs_const_32(S32, S64); }
test_reg_bounds_gen_consts_s32_u32(void)2012 void test_reg_bounds_gen_consts_s32_u32(void) { validate_gen_range_vs_const_32(S32, U32); }
test_reg_bounds_gen_consts_s32_s32(void)2013 void test_reg_bounds_gen_consts_s32_s32(void) { validate_gen_range_vs_const_32(S32, S32); }
2014
2015 /* RANGE x RANGE, U64 initial range */
test_reg_bounds_gen_ranges_u64_u64(void)2016 void test_reg_bounds_gen_ranges_u64_u64(void) { validate_gen_range_vs_range(U64, U64); }
test_reg_bounds_gen_ranges_u64_s64(void)2017 void test_reg_bounds_gen_ranges_u64_s64(void) { validate_gen_range_vs_range(U64, S64); }
test_reg_bounds_gen_ranges_u64_u32(void)2018 void test_reg_bounds_gen_ranges_u64_u32(void) { validate_gen_range_vs_range(U64, U32); }
test_reg_bounds_gen_ranges_u64_s32(void)2019 void test_reg_bounds_gen_ranges_u64_s32(void) { validate_gen_range_vs_range(U64, S32); }
2020 /* RANGE x RANGE, S64 initial range */
test_reg_bounds_gen_ranges_s64_u64(void)2021 void test_reg_bounds_gen_ranges_s64_u64(void) { validate_gen_range_vs_range(S64, U64); }
test_reg_bounds_gen_ranges_s64_s64(void)2022 void test_reg_bounds_gen_ranges_s64_s64(void) { validate_gen_range_vs_range(S64, S64); }
test_reg_bounds_gen_ranges_s64_u32(void)2023 void test_reg_bounds_gen_ranges_s64_u32(void) { validate_gen_range_vs_range(S64, U32); }
test_reg_bounds_gen_ranges_s64_s32(void)2024 void test_reg_bounds_gen_ranges_s64_s32(void) { validate_gen_range_vs_range(S64, S32); }
2025 /* RANGE x RANGE, U32 initial range */
test_reg_bounds_gen_ranges_u32_u64(void)2026 void test_reg_bounds_gen_ranges_u32_u64(void) { validate_gen_range_vs_range(U32, U64); }
test_reg_bounds_gen_ranges_u32_s64(void)2027 void test_reg_bounds_gen_ranges_u32_s64(void) { validate_gen_range_vs_range(U32, S64); }
test_reg_bounds_gen_ranges_u32_u32(void)2028 void test_reg_bounds_gen_ranges_u32_u32(void) { validate_gen_range_vs_range(U32, U32); }
test_reg_bounds_gen_ranges_u32_s32(void)2029 void test_reg_bounds_gen_ranges_u32_s32(void) { validate_gen_range_vs_range(U32, S32); }
2030 /* RANGE x RANGE, S32 initial range */
test_reg_bounds_gen_ranges_s32_u64(void)2031 void test_reg_bounds_gen_ranges_s32_u64(void) { validate_gen_range_vs_range(S32, U64); }
test_reg_bounds_gen_ranges_s32_s64(void)2032 void test_reg_bounds_gen_ranges_s32_s64(void) { validate_gen_range_vs_range(S32, S64); }
test_reg_bounds_gen_ranges_s32_u32(void)2033 void test_reg_bounds_gen_ranges_s32_u32(void) { validate_gen_range_vs_range(S32, U32); }
test_reg_bounds_gen_ranges_s32_s32(void)2034 void test_reg_bounds_gen_ranges_s32_s32(void) { validate_gen_range_vs_range(S32, S32); }
2035
2036 #define DEFAULT_RAND_CASE_CNT 100
2037
2038 #define RAND_21BIT_MASK ((1 << 22) - 1)
2039
rand_u64()2040 static u64 rand_u64()
2041 {
2042 /* RAND_MAX is guaranteed to be at least 1<<15, but in practice it
2043 * seems to be 1<<31, so we need to call it thrice to get full u64;
2044 * we'll use roughly equal split: 22 + 21 + 21 bits
2045 */
2046 return ((u64)random() << 42) |
2047 (((u64)random() & RAND_21BIT_MASK) << 21) |
2048 (random() & RAND_21BIT_MASK);
2049 }
2050
rand_const(enum num_t t)2051 static u64 rand_const(enum num_t t)
2052 {
2053 return cast_t(t, rand_u64());
2054 }
2055
rand_range(enum num_t t)2056 static struct range rand_range(enum num_t t)
2057 {
2058 u64 x = rand_const(t), y = rand_const(t);
2059
2060 return range(t, min_t(t, x, y), max_t(t, x, y));
2061 }
2062
validate_rand_ranges(enum num_t init_t,enum num_t cond_t,bool const_range)2063 static void validate_rand_ranges(enum num_t init_t, enum num_t cond_t, bool const_range)
2064 {
2065 struct ctx ctx;
2066 struct range range1, range2;
2067 int err, i;
2068 u64 t;
2069
2070 memset(&ctx, 0, sizeof(ctx));
2071
2072 err = parse_env_vars(&ctx);
2073 if (err) {
2074 ASSERT_OK(err, "parse_env_vars");
2075 return;
2076 }
2077
2078 if (ctx.rand_case_cnt == 0)
2079 ctx.rand_case_cnt = DEFAULT_RAND_CASE_CNT;
2080 if (ctx.rand_seed == 0)
2081 ctx.rand_seed = (unsigned)get_time_ns();
2082
2083 srandom(ctx.rand_seed);
2084
2085 ctx.total_case_cnt = (last_op - first_op + 1) * (2 * ctx.rand_case_cnt);
2086 ctx.start_ns = get_time_ns();
2087 snprintf(ctx.progress_ctx, sizeof(ctx.progress_ctx),
2088 "[RANDOM SEED %u] RANGE x %s, %s -> %s",
2089 ctx.rand_seed, const_range ? "CONST" : "RANGE",
2090 t_str(init_t), t_str(cond_t));
2091
2092 for (i = 0; i < ctx.rand_case_cnt; i++) {
2093 range1 = rand_range(init_t);
2094 if (const_range) {
2095 t = rand_const(init_t);
2096 range2 = range(init_t, t, t);
2097 } else {
2098 range2 = rand_range(init_t);
2099 }
2100
2101 /* <range1> x <range2> */
2102 if (verify_case_opt(&ctx, init_t, cond_t, range1, range2, false /* !is_subtest */))
2103 goto cleanup;
2104 /* <range2> x <range1> */
2105 if (verify_case_opt(&ctx, init_t, cond_t, range2, range1, false /* !is_subtest */))
2106 goto cleanup;
2107 }
2108
2109 cleanup:
2110 /* make sure we report random seed for reproducing */
2111 ASSERT_TRUE(true, ctx.progress_ctx);
2112 cleanup_ctx(&ctx);
2113 }
2114
2115 /* [RANDOM] RANGE x CONST, U64 initial range */
test_reg_bounds_rand_consts_u64_u64(void)2116 void test_reg_bounds_rand_consts_u64_u64(void) { validate_rand_ranges(U64, U64, true /* const */); }
test_reg_bounds_rand_consts_u64_s64(void)2117 void test_reg_bounds_rand_consts_u64_s64(void) { validate_rand_ranges(U64, S64, true /* const */); }
test_reg_bounds_rand_consts_u64_u32(void)2118 void test_reg_bounds_rand_consts_u64_u32(void) { validate_rand_ranges(U64, U32, true /* const */); }
test_reg_bounds_rand_consts_u64_s32(void)2119 void test_reg_bounds_rand_consts_u64_s32(void) { validate_rand_ranges(U64, S32, true /* const */); }
2120 /* [RANDOM] RANGE x CONST, S64 initial range */
test_reg_bounds_rand_consts_s64_u64(void)2121 void test_reg_bounds_rand_consts_s64_u64(void) { validate_rand_ranges(S64, U64, true /* const */); }
test_reg_bounds_rand_consts_s64_s64(void)2122 void test_reg_bounds_rand_consts_s64_s64(void) { validate_rand_ranges(S64, S64, true /* const */); }
test_reg_bounds_rand_consts_s64_u32(void)2123 void test_reg_bounds_rand_consts_s64_u32(void) { validate_rand_ranges(S64, U32, true /* const */); }
test_reg_bounds_rand_consts_s64_s32(void)2124 void test_reg_bounds_rand_consts_s64_s32(void) { validate_rand_ranges(S64, S32, true /* const */); }
2125 /* [RANDOM] RANGE x CONST, U32 initial range */
test_reg_bounds_rand_consts_u32_u64(void)2126 void test_reg_bounds_rand_consts_u32_u64(void) { validate_rand_ranges(U32, U64, true /* const */); }
test_reg_bounds_rand_consts_u32_s64(void)2127 void test_reg_bounds_rand_consts_u32_s64(void) { validate_rand_ranges(U32, S64, true /* const */); }
test_reg_bounds_rand_consts_u32_u32(void)2128 void test_reg_bounds_rand_consts_u32_u32(void) { validate_rand_ranges(U32, U32, true /* const */); }
test_reg_bounds_rand_consts_u32_s32(void)2129 void test_reg_bounds_rand_consts_u32_s32(void) { validate_rand_ranges(U32, S32, true /* const */); }
2130 /* [RANDOM] RANGE x CONST, S32 initial range */
test_reg_bounds_rand_consts_s32_u64(void)2131 void test_reg_bounds_rand_consts_s32_u64(void) { validate_rand_ranges(S32, U64, true /* const */); }
test_reg_bounds_rand_consts_s32_s64(void)2132 void test_reg_bounds_rand_consts_s32_s64(void) { validate_rand_ranges(S32, S64, true /* const */); }
test_reg_bounds_rand_consts_s32_u32(void)2133 void test_reg_bounds_rand_consts_s32_u32(void) { validate_rand_ranges(S32, U32, true /* const */); }
test_reg_bounds_rand_consts_s32_s32(void)2134 void test_reg_bounds_rand_consts_s32_s32(void) { validate_rand_ranges(S32, S32, true /* const */); }
2135
2136 /* [RANDOM] RANGE x RANGE, U64 initial range */
test_reg_bounds_rand_ranges_u64_u64(void)2137 void test_reg_bounds_rand_ranges_u64_u64(void) { validate_rand_ranges(U64, U64, false /* range */); }
test_reg_bounds_rand_ranges_u64_s64(void)2138 void test_reg_bounds_rand_ranges_u64_s64(void) { validate_rand_ranges(U64, S64, false /* range */); }
test_reg_bounds_rand_ranges_u64_u32(void)2139 void test_reg_bounds_rand_ranges_u64_u32(void) { validate_rand_ranges(U64, U32, false /* range */); }
test_reg_bounds_rand_ranges_u64_s32(void)2140 void test_reg_bounds_rand_ranges_u64_s32(void) { validate_rand_ranges(U64, S32, false /* range */); }
2141 /* [RANDOM] RANGE x RANGE, S64 initial range */
test_reg_bounds_rand_ranges_s64_u64(void)2142 void test_reg_bounds_rand_ranges_s64_u64(void) { validate_rand_ranges(S64, U64, false /* range */); }
test_reg_bounds_rand_ranges_s64_s64(void)2143 void test_reg_bounds_rand_ranges_s64_s64(void) { validate_rand_ranges(S64, S64, false /* range */); }
test_reg_bounds_rand_ranges_s64_u32(void)2144 void test_reg_bounds_rand_ranges_s64_u32(void) { validate_rand_ranges(S64, U32, false /* range */); }
test_reg_bounds_rand_ranges_s64_s32(void)2145 void test_reg_bounds_rand_ranges_s64_s32(void) { validate_rand_ranges(S64, S32, false /* range */); }
2146 /* [RANDOM] RANGE x RANGE, U32 initial range */
test_reg_bounds_rand_ranges_u32_u64(void)2147 void test_reg_bounds_rand_ranges_u32_u64(void) { validate_rand_ranges(U32, U64, false /* range */); }
test_reg_bounds_rand_ranges_u32_s64(void)2148 void test_reg_bounds_rand_ranges_u32_s64(void) { validate_rand_ranges(U32, S64, false /* range */); }
test_reg_bounds_rand_ranges_u32_u32(void)2149 void test_reg_bounds_rand_ranges_u32_u32(void) { validate_rand_ranges(U32, U32, false /* range */); }
test_reg_bounds_rand_ranges_u32_s32(void)2150 void test_reg_bounds_rand_ranges_u32_s32(void) { validate_rand_ranges(U32, S32, false /* range */); }
2151 /* [RANDOM] RANGE x RANGE, S32 initial range */
test_reg_bounds_rand_ranges_s32_u64(void)2152 void test_reg_bounds_rand_ranges_s32_u64(void) { validate_rand_ranges(S32, U64, false /* range */); }
test_reg_bounds_rand_ranges_s32_s64(void)2153 void test_reg_bounds_rand_ranges_s32_s64(void) { validate_rand_ranges(S32, S64, false /* range */); }
test_reg_bounds_rand_ranges_s32_u32(void)2154 void test_reg_bounds_rand_ranges_s32_u32(void) { validate_rand_ranges(S32, U32, false /* range */); }
test_reg_bounds_rand_ranges_s32_s32(void)2155 void test_reg_bounds_rand_ranges_s32_s32(void) { validate_rand_ranges(S32, S32, false /* range */); }
2156
2157 /* A set of hard-coded "interesting" cases to validate as part of normal
2158 * test_progs test runs
2159 */
2160 static struct subtest_case crafted_cases[] = {
2161 {U64, U64, {0, 0xffffffff}, {0, 0}},
2162 {U64, U64, {0, 0x80000000}, {0, 0}},
2163 {U64, U64, {0x100000000ULL, 0x100000100ULL}, {0, 0}},
2164 {U64, U64, {0x100000000ULL, 0x180000000ULL}, {0, 0}},
2165 {U64, U64, {0x100000000ULL, 0x1ffffff00ULL}, {0, 0}},
2166 {U64, U64, {0x100000000ULL, 0x1ffffff01ULL}, {0, 0}},
2167 {U64, U64, {0x100000000ULL, 0x1fffffffeULL}, {0, 0}},
2168 {U64, U64, {0x100000001ULL, 0x1000000ffULL}, {0, 0}},
2169
2170 /* single point overlap, interesting BPF_EQ and BPF_NE interactions */
2171 {U64, U64, {0, 1}, {1, 0x80000000}},
2172 {U64, S64, {0, 1}, {1, 0x80000000}},
2173 {U64, U32, {0, 1}, {1, 0x80000000}},
2174 {U64, S32, {0, 1}, {1, 0x80000000}},
2175
2176 {U64, S64, {0, 0xffffffff00000000ULL}, {0, 0}},
2177 {U64, S64, {0x7fffffffffffffffULL, 0xffffffff00000000ULL}, {0, 0}},
2178 {U64, S64, {0x7fffffff00000001ULL, 0xffffffff00000000ULL}, {0, 0}},
2179 {U64, S64, {0, 0xffffffffULL}, {1, 1}},
2180 {U64, S64, {0, 0xffffffffULL}, {0x7fffffff, 0x7fffffff}},
2181 {U64, S32, {0xfffffffe00000001, 0xffffffff00000000}, {S64_MIN, S64_MIN}},
2182 {U64, U32, {0xfffffffe00000000, U64_MAX - 1}, {U64_MAX, U64_MAX}},
2183
2184 {U64, U32, {0, 0x100000000}, {0, 0}},
2185 {U64, U32, {0xfffffffe, 0x300000000}, {0x80000000, 0x80000000}},
2186
2187 {U64, S32, {0, 0xffffffff00000000ULL}, {0, 0}},
2188 /* these are tricky cases where lower 32 bits allow to tighten 64
2189 * bit boundaries based on tightened lower 32 bit boundaries
2190 */
2191 {U64, S32, {0, 0x0ffffffffULL}, {0, 0}},
2192 {U64, S32, {0, 0x100000000ULL}, {0, 0}},
2193 {U64, S32, {0, 0x100000001ULL}, {0, 0}},
2194 {U64, S32, {0, 0x180000000ULL}, {0, 0}},
2195 {U64, S32, {0, 0x17fffffffULL}, {0, 0}},
2196 {U64, S32, {0, 0x180000001ULL}, {0, 0}},
2197
2198 /* verifier knows about [-1, 0] range for s32 for this case already */
2199 {S64, S64, {0xffffffffffffffffULL, 0}, {0xffffffff00000000ULL, 0xffffffff00000000ULL}},
2200 /* but didn't know about these cases initially */
2201 {U64, U64, {0xffffffff, 0x100000000ULL}, {0, 0}}, /* s32: [-1, 0] */
2202 {U64, U64, {0xffffffff, 0x100000001ULL}, {0, 0}}, /* s32: [-1, 1] */
2203
2204 /* longer convergence case: learning from u64 -> s64 -> u64 -> u32,
2205 * arriving at u32: [1, U32_MAX] (instead of more pessimistic [0, U32_MAX])
2206 */
2207 {S64, U64, {0xffffffff00000001ULL, 0}, {0xffffffff00000000ULL, 0xffffffff00000000ULL}},
2208
2209 {U32, U32, {1, U32_MAX}, {0, 0}},
2210
2211 {U32, S32, {0, U32_MAX}, {U32_MAX, U32_MAX}},
2212
2213 {S32, U64, {(u32)S32_MIN, (u32)S32_MIN}, {(u32)(s32)-255, 0}},
2214 {S32, S64, {(u32)S32_MIN, (u32)(s32)-255}, {(u32)(s32)-2, 0}},
2215 {S32, S64, {0, 1}, {(u32)S32_MIN, (u32)S32_MIN}},
2216 {S32, U32, {(u32)S32_MIN, (u32)S32_MIN}, {(u32)S32_MIN, (u32)S32_MIN}},
2217
2218 /* edge overlap testings for BPF_NE */
2219 {U64, U64, {0, U64_MAX}, {U64_MAX, U64_MAX}},
2220 {U64, U64, {0, U64_MAX}, {0, 0}},
2221 {S64, U64, {S64_MIN, 0}, {S64_MIN, S64_MIN}},
2222 {S64, U64, {S64_MIN, 0}, {0, 0}},
2223 {S64, U64, {S64_MIN, S64_MAX}, {S64_MAX, S64_MAX}},
2224 {U32, U32, {0, U32_MAX}, {0, 0}},
2225 {U32, U32, {0, U32_MAX}, {U32_MAX, U32_MAX}},
2226 {S32, U32, {(u32)S32_MIN, 0}, {0, 0}},
2227 {S32, U32, {(u32)S32_MIN, 0}, {(u32)S32_MIN, (u32)S32_MIN}},
2228 {S32, U32, {(u32)S32_MIN, S32_MAX}, {S32_MAX, S32_MAX}},
2229 {S64, U32, {0x0, 0x1f}, {0xffffffff80000000ULL, 0x000000007fffffffULL}},
2230 {S64, U32, {0x0, 0x1f}, {0xffffffffffff8000ULL, 0x0000000000007fffULL}},
2231 {S64, U32, {0x0, 0x1f}, {0xffffffffffffff80ULL, 0x000000000000007fULL}},
2232 };
2233
2234 /* Go over crafted hard-coded cases. This is fast, so we do it as part of
2235 * normal test_progs run.
2236 */
test_reg_bounds_crafted(void)2237 void test_reg_bounds_crafted(void)
2238 {
2239 struct ctx ctx;
2240 int i;
2241
2242 memset(&ctx, 0, sizeof(ctx));
2243
2244 for (i = 0; i < ARRAY_SIZE(crafted_cases); i++) {
2245 struct subtest_case *c = &crafted_cases[i];
2246
2247 verify_case(&ctx, c->init_t, c->cond_t, c->x, c->y);
2248 verify_case(&ctx, c->init_t, c->cond_t, c->y, c->x);
2249 }
2250
2251 cleanup_ctx(&ctx);
2252 }
2253