reg_bounds.c

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