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