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