tools/testing/selftests/bpf/prog_tests/reg_bounds.c

   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)
  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
  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
  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
  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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 271 static __always_inline u32 sign64(u64 x) { return (x >> 63) & 1; }
 272 static __always_inline u32 sign32(u64 x) { return ((u32)x >> 31) & 1; }
 273 static __always_inline u32 upper32(u64 x) { return (u32)(x >> 32); }
 274 static __always_inline u64 swap_low32(u64 x, u32 y) { return (x & 0xffffffff00000000ULL) | y; }
 275
 276 static bool range_eq(struct range x, struct range y)
 277 {
 278         return x.a == y.a && x.b == y.b;
 279 }
 280
 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
 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
 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
 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
 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  */
 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
 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
 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
 425 static 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
 430 static 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  */
 476 enum op { OP_LT, OP_LE, OP_GT, OP_GE, OP_EQ, OP_NE, first_op = OP_LT, last_op = OP_NE };
 477
 478 static 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
 491 static 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  */
 509 static 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  */
 538 static 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  */
 549 static 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  */
 559 static 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  */
 575 static 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  */
 639 struct reg_state {
 640         struct range r[4]; /* indexed by enum num_t: U64, U32, S64, S32 */
 641         bool valid;
 642 };
 643
 644 static 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
 665 static 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
 677 static 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
 683 again:
 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
 715 static 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
 726 static 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
 770 static 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  */
 817 struct 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  */
 837 static 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  */
1012 static 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=", &reg->r[S64].a, S64_MIN},
1045                 {"smax=", &reg->r[S64].b, S64_MAX},
1046                 {"umin=", &reg->r[U64].a, 0},
1047                 {"umax=", &reg->r[U64].b, U64_MAX},
1048                 {"smin32=", &reg->r[S32].a, (u32)S32_MIN, true},
1049                 {"smax32=", &reg->r[S32].b, (u32)S32_MAX, true},
1050                 {"umin32=", &reg->r[U32].a, 0,            true},
1051                 {"umax32=", &reg->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  */
1140 static 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 */
1182 static 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 */
1201 static 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 */
1225 static 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
1238 skip_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  */
1247 static 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  */
1320 static u32 upper_seeds[] = {
1321         0,
1322         1,
1323         U32_MAX,
1324         U32_MAX - 1,
1325         S32_MAX,
1326         (u32)S32_MIN,
1327 };
1328
1329 static 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
1340 struct 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
1356 static 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
1364 struct 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
1372 static 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  */
1385 static 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  */
1451 static 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
1505 static 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  */
1515 static 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
1522 static 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
1529 static 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
1536 static 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 */
1544 static 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 */
1617 static 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
1689 static 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
1723 static 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  */
1750 static 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
1785 cleanup:
1786         cleanup_ctx(&ctx);
1787 }
1788
1789 static 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
1824 cleanup:
1825         cleanup_ctx(&ctx);
1826 }
1827
1828 static 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
1878 cleanup:
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 */
1892 void test_reg_bounds_gen_consts_u64_u64(void) { validate_gen_range_vs_const_64(U64, U64); }
1893 void test_reg_bounds_gen_consts_u64_s64(void) { validate_gen_range_vs_const_64(U64, S64); }
1894 void test_reg_bounds_gen_consts_u64_u32(void) { validate_gen_range_vs_const_64(U64, U32); }
1895 void test_reg_bounds_gen_consts_u64_s32(void) { validate_gen_range_vs_const_64(U64, S32); }
1896 /* RANGE x CONST, S64 initial range */
1897 void test_reg_bounds_gen_consts_s64_u64(void) { validate_gen_range_vs_const_64(S64, U64); }
1898 void test_reg_bounds_gen_consts_s64_s64(void) { validate_gen_range_vs_const_64(S64, S64); }
1899 void test_reg_bounds_gen_consts_s64_u32(void) { validate_gen_range_vs_const_64(S64, U32); }
1900 void test_reg_bounds_gen_consts_s64_s32(void) { validate_gen_range_vs_const_64(S64, S32); }
1901 /* RANGE x CONST, U32 initial range */
1902 void test_reg_bounds_gen_consts_u32_u64(void) { validate_gen_range_vs_const_32(U32, U64); }
1903 void test_reg_bounds_gen_consts_u32_s64(void) { validate_gen_range_vs_const_32(U32, S64); }
1904 void test_reg_bounds_gen_consts_u32_u32(void) { validate_gen_range_vs_const_32(U32, U32); }
1905 void test_reg_bounds_gen_consts_u32_s32(void) { validate_gen_range_vs_const_32(U32, S32); }
1906 /* RANGE x CONST, S32 initial range */
1907 void test_reg_bounds_gen_consts_s32_u64(void) { validate_gen_range_vs_const_32(S32, U64); }
1908 void test_reg_bounds_gen_consts_s32_s64(void) { validate_gen_range_vs_const_32(S32, S64); }
1909 void test_reg_bounds_gen_consts_s32_u32(void) { validate_gen_range_vs_const_32(S32, U32); }
1910 void test_reg_bounds_gen_consts_s32_s32(void) { validate_gen_range_vs_const_32(S32, S32); }
1911
1912 /* RANGE x RANGE, U64 initial range */
1913 void test_reg_bounds_gen_ranges_u64_u64(void) { validate_gen_range_vs_range(U64, U64); }
1914 void test_reg_bounds_gen_ranges_u64_s64(void) { validate_gen_range_vs_range(U64, S64); }
1915 void test_reg_bounds_gen_ranges_u64_u32(void) { validate_gen_range_vs_range(U64, U32); }
1916 void test_reg_bounds_gen_ranges_u64_s32(void) { validate_gen_range_vs_range(U64, S32); }
1917 /* RANGE x RANGE, S64 initial range */
1918 void test_reg_bounds_gen_ranges_s64_u64(void) { validate_gen_range_vs_range(S64, U64); }
1919 void test_reg_bounds_gen_ranges_s64_s64(void) { validate_gen_range_vs_range(S64, S64); }
1920 void test_reg_bounds_gen_ranges_s64_u32(void) { validate_gen_range_vs_range(S64, U32); }
1921 void test_reg_bounds_gen_ranges_s64_s32(void) { validate_gen_range_vs_range(S64, S32); }
1922 /* RANGE x RANGE, U32 initial range */
1923 void test_reg_bounds_gen_ranges_u32_u64(void) { validate_gen_range_vs_range(U32, U64); }
1924 void test_reg_bounds_gen_ranges_u32_s64(void) { validate_gen_range_vs_range(U32, S64); }
1925 void test_reg_bounds_gen_ranges_u32_u32(void) { validate_gen_range_vs_range(U32, U32); }
1926 void test_reg_bounds_gen_ranges_u32_s32(void) { validate_gen_range_vs_range(U32, S32); }
1927 /* RANGE x RANGE, S32 initial range */
1928 void test_reg_bounds_gen_ranges_s32_u64(void) { validate_gen_range_vs_range(S32, U64); }
1929 void test_reg_bounds_gen_ranges_s32_s64(void) { validate_gen_range_vs_range(S32, S64); }
1930 void test_reg_bounds_gen_ranges_s32_u32(void) { validate_gen_range_vs_range(S32, U32); }
1931 void 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
1937 static 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
1948 static u64 rand_const(enum num_t t)
1949 {
1950         return cast_t(t, rand_u64());
1951 }
1952
1953 static 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
1960 static 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
2006 cleanup:
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 */
2013 void test_reg_bounds_rand_consts_u64_u64(void) { validate_rand_ranges(U64, U64, true /* const */); }
2014 void test_reg_bounds_rand_consts_u64_s64(void) { validate_rand_ranges(U64, S64, true /* const */); }
2015 void test_reg_bounds_rand_consts_u64_u32(void) { validate_rand_ranges(U64, U32, true /* const */); }
2016 void test_reg_bounds_rand_consts_u64_s32(void) { validate_rand_ranges(U64, S32, true /* const */); }
2017 /* [RANDOM] RANGE x CONST, S64 initial range */
2018 void test_reg_bounds_rand_consts_s64_u64(void) { validate_rand_ranges(S64, U64, true /* const */); }
2019 void test_reg_bounds_rand_consts_s64_s64(void) { validate_rand_ranges(S64, S64, true /* const */); }
2020 void test_reg_bounds_rand_consts_s64_u32(void) { validate_rand_ranges(S64, U32, true /* const */); }
2021 void test_reg_bounds_rand_consts_s64_s32(void) { validate_rand_ranges(S64, S32, true /* const */); }
2022 /* [RANDOM] RANGE x CONST, U32 initial range */
2023 void test_reg_bounds_rand_consts_u32_u64(void) { validate_rand_ranges(U32, U64, true /* const */); }
2024 void test_reg_bounds_rand_consts_u32_s64(void) { validate_rand_ranges(U32, S64, true /* const */); }
2025 void test_reg_bounds_rand_consts_u32_u32(void) { validate_rand_ranges(U32, U32, true /* const */); }
2026 void test_reg_bounds_rand_consts_u32_s32(void) { validate_rand_ranges(U32, S32, true /* const */); }
2027 /* [RANDOM] RANGE x CONST, S32 initial range */
2028 void test_reg_bounds_rand_consts_s32_u64(void) { validate_rand_ranges(S32, U64, true /* const */); }
2029 void test_reg_bounds_rand_consts_s32_s64(void) { validate_rand_ranges(S32, S64, true /* const */); }
2030 void test_reg_bounds_rand_consts_s32_u32(void) { validate_rand_ranges(S32, U32, true /* const */); }
2031 void test_reg_bounds_rand_consts_s32_s32(void) { validate_rand_ranges(S32, S32, true /* const */); }
2032
2033 /* [RANDOM] RANGE x RANGE, U64 initial range */
2034 void test_reg_bounds_rand_ranges_u64_u64(void) { validate_rand_ranges(U64, U64, false /* range */); }
2035 void test_reg_bounds_rand_ranges_u64_s64(void) { validate_rand_ranges(U64, S64, false /* range */); }
2036 void test_reg_bounds_rand_ranges_u64_u32(void) { validate_rand_ranges(U64, U32, false /* range */); }
2037 void test_reg_bounds_rand_ranges_u64_s32(void) { validate_rand_ranges(U64, S32, false /* range */); }
2038 /* [RANDOM] RANGE x RANGE, S64 initial range */
2039 void test_reg_bounds_rand_ranges_s64_u64(void) { validate_rand_ranges(S64, U64, false /* range */); }
2040 void test_reg_bounds_rand_ranges_s64_s64(void) { validate_rand_ranges(S64, S64, false /* range */); }
2041 void test_reg_bounds_rand_ranges_s64_u32(void) { validate_rand_ranges(S64, U32, false /* range */); }
2042 void test_reg_bounds_rand_ranges_s64_s32(void) { validate_rand_ranges(S64, S32, false /* range */); }
2043 /* [RANDOM] RANGE x RANGE, U32 initial range */
2044 void test_reg_bounds_rand_ranges_u32_u64(void) { validate_rand_ranges(U32, U64, false /* range */); }
2045 void test_reg_bounds_rand_ranges_u32_s64(void) { validate_rand_ranges(U32, S64, false /* range */); }
2046 void test_reg_bounds_rand_ranges_u32_u32(void) { validate_rand_ranges(U32, U32, false /* range */); }
2047 void test_reg_bounds_rand_ranges_u32_s32(void) { validate_rand_ranges(U32, S32, false /* range */); }
2048 /* [RANDOM] RANGE x RANGE, S32 initial range */
2049 void test_reg_bounds_rand_ranges_s32_u64(void) { validate_rand_ranges(S32, U64, false /* range */); }
2050 void test_reg_bounds_rand_ranges_s32_s64(void) { validate_rand_ranges(S32, S64, false /* range */); }
2051 void test_reg_bounds_rand_ranges_s32_u32(void) { validate_rand_ranges(S32, U32, false /* range */); }
2052 void 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  */
2057 static 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  */
2132 void 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 }