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