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