lib/bpf/bpf_validate.c - main - phprus/github_dpdk

lib/bpf/bpf_validate.c
3 162 строки79 KB
Marat Khalili
bpf/validate: prevent overflow when building graph
03 июл 2026, 04:10
03 июл 2026, 04:101ad243a
/* SPDX-License-Identifier: BSD-3-Clause
 * Copyright(c) 2018 Intel Corporation
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <errno.h>
#include <stdint.h>
#include <inttypes.h>

#include <rte_bpf_validate_debug.h>
#include <rte_common.h>

#include "bpf_impl.h"
#include "bpf_validate.h"
#include "bpf_validate_debug.h"
#include "bpf_value_set.h"

#define BPF_ARG_PTR_STACK RTE_BPF_ARG_RESERVED

/* type containing no values (AKA "bottom", "never" etc)  */
#define BPF_ARG_UNINHABITED ((enum rte_bpf_arg_type)(RTE_BPF_ARG_UNDEF - 1))

struct bpf_reg_val {
	struct rte_bpf_arg v;
	uint64_t mask;
	struct {
		int64_t min;
		int64_t max;
	} s;
	struct {
		uint64_t min;
		uint64_t max;
	} u;
};

struct bpf_eval_state {
	SLIST_ENTRY(bpf_eval_state) next; /* for @safe list traversal */
	struct bpf_reg_val rv[EBPF_REG_NUM];
	struct bpf_reg_val sv[MAX_BPF_STACK_SIZE / sizeof(uint64_t)];
	/* flag set for branches determined to be dynamically unreachable */
	bool unreachable;
};

SLIST_HEAD(bpf_evst_head, bpf_eval_state);

/* possible instruction node colour */
enum {
	WHITE,
	GREY,
	BLACK,
	MAX_NODE_COLOUR
};

/* possible edge types */
enum {
	UNKNOWN_EDGE,
	TREE_EDGE,
	BACK_EDGE,
	CROSS_EDGE,
	MAX_EDGE_TYPE
};

#define	MAX_EDGES	2

/* max number of 'safe' evaluated states to track per node */
#define NODE_EVST_MAX	32

struct inst_node {
	uint8_t colour;
	uint8_t nb_edge:4;
	uint8_t cur_edge:4;
	uint8_t edge_type[MAX_EDGES];
	uint32_t edge_dest[MAX_EDGES];
	struct inst_node *prev_node;
	struct {
		struct bpf_eval_state *cur;   /* save/restore for jcc targets */
		struct bpf_eval_state *start;
		struct bpf_evst_head safe;    /* safe states for track/prune */
		uint32_t nb_safe;
	} evst;
};

struct evst_pool {
	uint32_t num;
	uint32_t cur;
	struct bpf_eval_state *ent;
};

struct bpf_verifier {
	const struct rte_bpf_prm_ex *prm;
	struct inst_node *in;
	uint64_t stack_sz;
	uint32_t nb_nodes;
	uint32_t nb_jcc_nodes;
	uint32_t nb_ldmb_nodes;
	uint32_t node_colour[MAX_NODE_COLOUR];
	uint32_t edge_type[MAX_EDGE_TYPE];
	struct bpf_eval_state *evst;
	struct inst_node *evin;
	struct evst_pool evst_sr_pool; /* for evst save/restore */
	struct evst_pool evst_tp_pool; /* for evst track/prune */
	struct rte_bpf_validate_debug *debug;
};

struct bpf_ins_check {
	struct {
		uint16_t dreg;
		uint16_t sreg;
	} mask;
	struct {
		uint16_t min;
		uint16_t max;
	} off;
	struct {
		uint32_t min;
		uint32_t max;
	} imm;
	const char * (*check)(const struct ebpf_insn *);
	const char * (*eval)(struct bpf_verifier *, const struct ebpf_insn *);
};

#define	ALL_REGS	RTE_LEN2MASK(EBPF_REG_NUM, uint16_t)
#define	WRT_REGS	RTE_LEN2MASK(EBPF_REG_10, uint16_t)
#define	ZERO_REG	RTE_LEN2MASK(EBPF_REG_1, uint16_t)

/* For LD_IND R6 is an implicit CTX register. */
#define	IND_SRC_REGS	(WRT_REGS ^ 1 << EBPF_REG_6)

/*
 * Debugging internal interface and helpers.
 */

static bool
reg_val_range_is_valid(const struct bpf_reg_val *rv)
{
	if (rv->v.type == RTE_BPF_ARG_UNDEF)
		return true;

	if (rv->s.min > rv->s.max)
		return false;

	if (rv->u.min > rv->u.max)
		return false;

	/* If one of the ranges does not change sign, the other should match. */
	if (rv->s.min >= 0 || rv->s.max < 0 ||
			rv->u.min > INT64_MAX || rv->u.max <= INT64_MAX)
		return rv->u.min == (uint64_t)rv->s.min &&
			rv->u.max == (uint64_t)rv->s.max;

	return true;
}

int
__rte_bpf_validate_state_is_valid(const struct bpf_verifier *verifier)
{
	const struct bpf_eval_state *const st = verifier->evst;

	for (int reg = 0; reg != RTE_DIM(st->rv); ++reg)
		if (!reg_val_range_is_valid(st->rv + reg))
			return false;

	for (int var = 0; var != RTE_DIM(st->sv); ++var)
		if (!reg_val_range_is_valid(st->sv + var))
			return false;

	return true;
}

int
__rte_bpf_validate_can_access(const struct bpf_verifier *verifier,
	const struct ebpf_insn *access, uint64_t off64)
{
	const struct bpf_eval_state *const st = verifier->evst;
	const struct bpf_reg_val *rv;
	/* Set of accessed byte offsets relative to memory area base. */
	struct value_set access_set;
	uint32_t opsz;

	if (st->unreachable)
		return -ENOENT;

	switch (BPF_CLASS(access->code)) {
	case BPF_LDX:
		rv = &st->rv[access->src_reg];
		if (rv->v.type == BPF_ARG_PTR_STACK)
			/* Not supporting stack access queries yet. */
			return -ENOTSUP;
		break;
	case BPF_ST:
		rv = &st->rv[access->dst_reg];
		break;
	case BPF_STX:
		rv = &st->rv[access->dst_reg];
		if (st->rv[access->src_reg].v.type == RTE_BPF_ARG_UNDEF)
			return false;
		break;
	default:
		return -ENOTSUP;
	}

	if (!RTE_BPF_ARG_PTR_TYPE(rv->v.type) || rv->v.size == 0)
		return false;

	access_set = value_set_from_pair(rv->s.min, rv->s.max, rv->u.min, rv->u.max);
	value_set_translate(&access_set, off64);
	opsz = bpf_size(BPF_SIZE(access->code));
	value_set_add_contiguous(&access_set, 0, opsz - 1);

	return value_set_is_covered_by_contiguous(&access_set, 0, rv->v.size - 1);
}

/* Return true if instruction `code` is supported by `may_jump`. */
static bool
may_jump_code_is_supported(uint8_t code)
{
	if (BPF_CLASS(code) != BPF_JMP)
		return false;

	switch (BPF_OP(code)) {
	case BPF_JEQ:
	case BPF_JGT:
	case BPF_JGE:
	case EBPF_JNE:
	case EBPF_JSGT:
	case EBPF_JSGE:
	case EBPF_JLT:
	case EBPF_JLE:
	case EBPF_JSLT:
	case EBPF_JSLE:
		return true;
	default:
		return false;
	}
}

/* Return true if instruction `code` corresponds to a signed comparison. */
static bool
may_jump_code_is_signed(uint8_t code)
{
	switch (BPF_OP(code)) {
	case EBPF_JSGT:
	case EBPF_JSGE:
	case EBPF_JSLT:
	case EBPF_JSLE:
		return true;
	default:
		return false;
	}
}

/* Return true the specified jump condition _may_ be true. */
static bool
may_jump(uint8_t code, const struct value_set *origin,
	const struct value_set *dst_set, const struct value_set *src_set)
{
	switch (BPF_OP(code)) {
	case BPF_JEQ:
		return value_sets_intersect(dst_set, src_set);
	case EBPF_JNE:
		return !(value_set_is_singleton(dst_set) &&
			value_sets_equal(dst_set, src_set));
	case BPF_JGT:
	case EBPF_JSGT:
		return !value_sets_based_less_or_equal(origin, dst_set, src_set);
	case BPF_JGE:
	case EBPF_JSGE:
		return !value_sets_based_less(origin, dst_set, src_set);
	case EBPF_JLT:
	case EBPF_JSLT:
		return !value_sets_based_less_or_equal(origin, src_set, dst_set);
	case EBPF_JSLE:
	case EBPF_JLE:
		return !value_sets_based_less(origin, src_set, dst_set);
	}
	/* may_jump_code_is_supported should have caught this */
	RTE_ASSERT(false);
	return false;
}

/* Return instruction code for jump condition complement (negated result). */
static uint8_t
may_jump_code_complement(uint8_t code)
{
	switch (BPF_OP(code)) {
	case BPF_JEQ:
	case EBPF_JNE:
		return code ^ BPF_JEQ ^ EBPF_JNE;
	case BPF_JGT:
	case EBPF_JLE:
		return code ^ BPF_JGT ^ EBPF_JLE;
	case BPF_JGE:
	case EBPF_JLT:
		return code ^ BPF_JGE ^ EBPF_JLT;
	case EBPF_JSGT:
	case EBPF_JSLE:
		return code ^ EBPF_JSGT ^ EBPF_JSLE;
	case EBPF_JSGE:
	case EBPF_JSLT:
		return code ^ EBPF_JSGE ^ EBPF_JSLT;
	}
	/* may_jump_code_is_supported should have caught this */
	RTE_ASSERT(false);
	return 0;
}

int
__rte_bpf_validate_may_jump(const struct bpf_verifier *verifier,
	const struct ebpf_insn *jump, uint64_t imm64)
{
	const struct bpf_eval_state *const st = verifier->evst;
	const struct bpf_reg_val *rd, *rs;
	struct value_set dst_set, src_set, origin;
	int result;

	if (!may_jump_code_is_supported(jump->code))
		return -ENOTSUP;

	if (st->unreachable)
		/* Set no bits since neither false nor true is possible. */
		return 0;

	rd = &st->rv[jump->dst_reg];
	dst_set = (rd->v.type == RTE_BPF_ARG_UNDEF) ? value_set_full :
		value_set_from_pair(rd->s.min, rd->s.max, rd->u.min, rd->u.max);

	rs = BPF_SRC(jump->code) == BPF_X ? &st->rv[jump->src_reg] : NULL;
	src_set = rs == NULL ? value_set_singleton((int64_t)jump->imm) :
		rs->v.type == RTE_BPF_ARG_UNDEF ? value_set_full :
		value_set_from_pair(rs->s.min, rs->s.max, rs->u.min, rs->u.max);

	value_set_translate(&src_set, imm64);

	if (RTE_BPF_ARG_PTR_TYPE(rd->v.type) &&
			(rs != NULL && RTE_BPF_ARG_PTR_TYPE(rs->v.type)) &&
			rd->v.size == rs->v.size) {
		/*
		 * Both sides are pointers with the same memory area size.
		 * Until tracking of memory areas is implemented we will consider them
		 * pointing to the same memory area just because of this.
		 * In this case our value sets represent offsets from the memory area base,
		 * which is some unknown distance from the scalar zero (NULL).
		 * We know however that the memory area cannot cross zero address.
		 * Thus range of origin relative to memory base starts with 1 byte gap
		 * after the memory area and ends just before it.
		 */
		origin = value_set_contiguous(rd->v.size + 1, -1);
	} else {
		/* Scalar value of a pointer depends on the memory area base address. */
		if (RTE_BPF_ARG_PTR_TYPE(rd->v.type))
			value_set_add_contiguous(&dst_set, 1, UINT64_MAX - rd->v.size);
		if (rs != NULL && RTE_BPF_ARG_PTR_TYPE(rs->v.type))
			value_set_add_contiguous(&dst_set, 1, UINT64_MAX - rs->v.size);
		origin = value_set_singleton(0);
	}

	if (may_jump_code_is_signed(jump->code))
		/* Shift origin to the minimal value for signed comparisons. */
		value_set_translate(&origin, INT64_MIN);

	result = 0;

	if (may_jump(jump->code, &origin, &dst_set, &src_set))
		result |= RTE_BPF_VALIDATE_DEBUG_MAY_BE_TRUE;

	if (may_jump(may_jump_code_complement(jump->code), &origin, &dst_set, &src_set))
		result |= RTE_BPF_VALIDATE_DEBUG_MAY_BE_FALSE;

	return result;
}

/* Like snprintf, but advances (except for overflow) ptr and reduces szleft. */
__rte_format_printf(3, 4)
static int
buf_printf(char **ptr, ssize_t *szleft, const char *format, ...)
{
	va_list args;
	int rc;

	va_start(args, format);
	rc = vsnprintf(*ptr, RTE_MAX(0, *szleft), format, args);
	va_end(args);

	if (rc > 0) {
		*szleft -= rc;
		if (*szleft > 0)
			*ptr += rc;
	}

	return rc;
}

static int
format_memory_area(char **ptr, ssize_t *szleft, const struct bpf_reg_val *rv)
{
	switch (rv->v.type) {
	case RTE_BPF_ARG_RAW:
		return 0;
	case RTE_BPF_ARG_PTR:
		return buf_printf(ptr, szleft, "%%buffer<%zu> + ",
			(size_t)rv->v.size);
	case RTE_BPF_ARG_PTR_MBUF:
		return buf_printf(ptr, szleft, "%%mbuf<%zu, %zu> + ",
			(size_t)rv->v.size, (size_t)rv->v.buf_size);
	case BPF_ARG_PTR_STACK:
		return buf_printf(ptr, szleft, "%%stack + ");
	default:
		return -ENOTSUP;
	}
}

/* Format min..max interval using validate-debug API and updating ptr and szleft. */
static int
buf_print_interval(char **ptr, ssize_t *szleft, char format, uint64_t min, uint64_t max)
{
	int rc;

	rc = rte_bpf_validate_debug_format_interval(*ptr, RTE_MAX(0, *szleft),
		format, min, max);

	if (rc > 0) {
		*szleft -= rc;
		if (*szleft > 0)
			*ptr += rc;
	}

	return rc;
}

/* Format rv roughly as "<signed-range> INTERSECT <unsigned-hex-range>" */
static int
format_register_range(char **ptr, ssize_t *szleft, const struct bpf_reg_val *rv)
{
	int rc;
	uint64_t expected_unsigned_min, expected_unsigned_max;
	const bool valid = reg_val_range_is_valid(rv);

	/* Print signed unless trivial. */
	if (!valid || rv->s.min != INT64_MIN || rv->s.max != INT64_MAX) {
		rc = buf_print_interval(ptr, szleft, 'd', rv->s.min, rv->s.max);
		if (rc < 0)
			return rc;

		if (valid) {
			/* Skip printing unsigned if it has expected values. */
			if (rv->s.min >= 0 || rv->s.max < 0) {
				expected_unsigned_min = (uint64_t)rv->s.min;
				expected_unsigned_max = (uint64_t)rv->s.max;
			} else {
				expected_unsigned_min = 0;
				expected_unsigned_max = UINT64_MAX;
			}

			if (rv->u.min == expected_unsigned_min &&
					rv->u.max == expected_unsigned_max)
				return 0;
		}

		rc = buf_printf(ptr, szleft, " INTERSECT ");
		if (rc < 0)
			return rc;
	}

	rc = buf_print_interval(ptr, szleft, 'x', rv->u.min, rv->u.max);
	if (rc < 0)
		return rc;

	if (!valid) {
		rc = buf_printf(ptr, szleft, " (!)");
		if (rc < 0)
			return rc;
	}

	return 0;
}

/* Format rv roughly as "<memory-object> + <offsets-range>" */
static int
format_reg_val(char *buffer, size_t bufsz, const struct bpf_reg_val *rv)
{
	char *ptr = buffer;
	ssize_t szleft = bufsz;
	int rc;

	if (rv->v.type == RTE_BPF_ARG_UNDEF)
		return snprintf(buffer, bufsz, "%%undefined");

	/* Print data area info, if any. */
	rc = format_memory_area(&ptr, &szleft, rv);
	if (rc < 0)
		return rc;

	rc = format_register_range(&ptr, &szleft, rv);
	if (rc < 0)
		return rc;

	/* At least one snprintf was called and added terminating zero. */
	RTE_ASSERT(szleft < (ssize_t)bufsz);
	--szleft;

	return bufsz - szleft;
}

int
__rte_bpf_validate_format_register_info(const struct bpf_verifier *verifier,
	char *buffer, size_t bufsz, uint8_t reg)
{
	if (reg >= EBPF_REG_NUM)
		return -EINVAL;

	return format_reg_val(buffer, bufsz, &verifier->evst->rv[reg]);
}

int
__rte_bpf_validate_format_frame_info(const struct bpf_verifier *verifier,
	char *buffer, size_t bufsz, int32_t offset)
{
	if (offset % sizeof(uint64_t) != 0)
		return -EINVAL;

	if (offset >= 0 || offset < -MAX_BPF_STACK_SIZE)
		return -ERANGE;

	offset = (MAX_BPF_STACK_SIZE + offset) / sizeof(uint64_t);

	return format_reg_val(buffer, bufsz, &verifier->evst->sv[offset]);
}

int32_t
__rte_bpf_validate_get_frame_size(const struct bpf_verifier *verifier)
{
	if (verifier->stack_sz > INT32_MAX)
		return -ERANGE;

	return verifier->stack_sz;
}


/*
 * check and evaluate functions for particular instruction types.
 */

static const char *
check_alu_bele(const struct ebpf_insn *ins)
{
	if (ins->imm != 16 && ins->imm != 32 && ins->imm != 64)
		return "invalid imm field";
	return NULL;
}

static const char *
eval_exit(struct bpf_verifier *bvf, const struct ebpf_insn *ins)
{
	RTE_SET_USED(ins);
	if (bvf->evst->rv[EBPF_REG_0].v.type == RTE_BPF_ARG_UNDEF)
		return "undefined return value";
	return NULL;
}

/* setup max possible with this mask bounds */
static void
eval_umax_bound(struct bpf_reg_val *rv, uint64_t mask)
{
	rv->u.max = mask;
	rv->u.min = 0;
}

static void
eval_smax_bound(struct bpf_reg_val *rv, uint64_t mask)
{
	rv->s.max = mask >> 1;
	rv->s.min = rv->s.max ^ UINT64_MAX;
}

static void
eval_max_bound(struct bpf_reg_val *rv, uint64_t mask)
{
	eval_umax_bound(rv, mask);
	eval_smax_bound(rv, mask);
}

static void
eval_fill_max_bound(struct bpf_reg_val *rv, uint64_t mask)
{
	eval_max_bound(rv, mask);
	rv->v.type = RTE_BPF_ARG_RAW;
	rv->mask = mask;
}

static void
eval_fill_imm64(struct bpf_reg_val *rv, uint64_t mask, uint64_t val)
{
	rv->mask = mask;
	rv->s.min = val;
	rv->s.max = val;
	rv->u.min = val;
	rv->u.max = val;
}

static void
eval_fill_imm(struct bpf_reg_val *rv, uint64_t mask, int32_t imm)
{
	uint64_t v;

	v = (uint64_t)imm & mask;

	rv->v.type = RTE_BPF_ARG_RAW;
	eval_fill_imm64(rv, mask, v);
}

static const char *
eval_ld_imm64(struct bpf_verifier *bvf, const struct ebpf_insn *ins)
{
	uint32_t i;
	uint64_t val;
	struct bpf_reg_val *rd;

	val = (uint32_t)ins[0].imm | (uint64_t)(uint32_t)ins[1].imm << 32;

	rd = bvf->evst->rv + ins->dst_reg;
	rd->v.type = RTE_BPF_ARG_RAW;
	eval_fill_imm64(rd, UINT64_MAX, val);

	for (i = 0; i != bvf->prm->nb_xsym; i++) {

		/* load of external variable */
		if (bvf->prm->xsym[i].type == RTE_BPF_XTYPE_VAR &&
				(uintptr_t)bvf->prm->xsym[i].var.val == val) {
			rd->v = bvf->prm->xsym[i].var.desc;
			eval_fill_imm64(rd, UINT64_MAX, 0);
			break;
		}
	}

	return NULL;
}

static void
eval_apply_mask(struct bpf_reg_val *rv, uint64_t mask)
{
	struct bpf_reg_val rt;

	rt.u.min = rv->u.min & mask;
	rt.u.max = rv->u.max & mask;
	if (rt.u.min != rv->u.min || rt.u.max != rv->u.max) {
		rv->u.max = RTE_MAX(rt.u.max, mask);
		rv->u.min = 0;
	}

	eval_smax_bound(&rt, mask);
	rv->s.max = RTE_MIN(rt.s.max, rv->s.max);
	rv->s.min = RTE_MAX(rt.s.min, rv->s.min);

	rv->mask = mask;
}

static void
eval_add(struct bpf_reg_val *rd, const struct bpf_reg_val *rs, uint64_t msk)
{
	struct bpf_reg_val rs_buf;
	struct bpf_reg_val rv;

	if (RTE_BPF_ARG_PTR_TYPE(rs->v.type) != 0) {
		if (RTE_BPF_ARG_PTR_TYPE(rd->v.type) != 0) {
			/* treat sum of pointers as sum of two unknown scalars */
			eval_fill_max_bound(&rs_buf, msk);
			*rd = rs_buf;
			rs = &rs_buf;
		} else
			/* scalar + pointer is a pointer of the same type */
			rd->v = rs->v;
	}

	rv.u.min = (rd->u.min + rs->u.min) & msk;
	rv.u.max = (rd->u.max + rs->u.max) & msk;
	rv.s.min = ((uint64_t)rd->s.min + (uint64_t)rs->s.min) & msk;
	rv.s.max = ((uint64_t)rd->s.max + (uint64_t)rs->s.max) & msk;

	/*
	 * if at least one of the operands is not constant,
	 * then check for overflow
	 */
	if ((rd->u.min != rd->u.max || rs->u.min != rs->u.max) &&
			(rv.u.min < rd->u.min || rv.u.max < rd->u.max))
		eval_umax_bound(&rv, msk);

	if ((rd->s.min != rd->s.max || rs->s.min != rs->s.max) &&
			(((rs->s.min < 0 && rv.s.min > rd->s.min) ||
			rv.s.min < rd->s.min) ||
			((rs->s.max < 0 && rv.s.max > rd->s.max) ||
				rv.s.max < rd->s.max)))
		eval_smax_bound(&rv, msk);

	rd->s = rv.s;
	rd->u = rv.u;
}

static void
eval_sub(struct bpf_reg_val *rd, const struct bpf_reg_val *rs, uint64_t msk)
{
	struct bpf_reg_val rv;

	rv.u.min = (rd->u.min - rs->u.max) & msk;
	rv.u.max = (rd->u.max - rs->u.min) & msk;
	rv.s.min = ((uint64_t)rd->s.min - (uint64_t)rs->s.max) & msk;
	rv.s.max = ((uint64_t)rd->s.max - (uint64_t)rs->s.min) & msk;

	/*
	 * if at least one of the operands is not constant,
	 * then check for overflow
	 */
	if ((rd->u.min != rd->u.max || rs->u.min != rs->u.max) &&
			(rv.u.min > rd->u.min || rv.u.max > rd->u.max))
		eval_umax_bound(&rv, msk);

	if ((rd->s.min != rd->s.max || rs->s.min != rs->s.max) &&
			(((rs->s.max < 0 && rv.s.min < rd->s.min) ||
			rv.s.min > rd->s.min) ||
			((rs->s.min < 0 && rv.s.max < rd->s.max) ||
			rv.s.max > rd->s.max)))
		eval_smax_bound(&rv, msk);

	rd->s = rv.s;
	rd->u = rv.u;
}

static void
eval_lsh(struct bpf_reg_val *rd, const struct bpf_reg_val *rs, size_t opsz,
	uint64_t msk)
{
	/* check if shift value is less then max result bits */
	if (rs->u.max >= opsz) {
		eval_max_bound(rd, msk);
		return;
	}

	/* check for overflow */
	if (rd->u.max > RTE_LEN2MASK(opsz - rs->u.max, uint64_t))
		eval_umax_bound(rd, msk);
	else {
		rd->u.max <<= rs->u.max;
		rd->u.min <<= rs->u.min;
	}

	/* check that dreg values are and would remain always positive */
	if ((uint64_t)rd->s.min >> (opsz - 1) != 0 || rd->s.max >=
			(rs->u.max == opsz - 1 ? 0 :
				 RTE_LEN2MASK(opsz - rs->u.max - 1, int64_t)))
		eval_smax_bound(rd, msk);
	else {
		rd->s.max <<= rs->u.max;
		rd->s.min <<= rs->u.min;
	}
}

static void
eval_rsh(struct bpf_reg_val *rd, const struct bpf_reg_val *rs, size_t opsz,
	uint64_t msk)
{
	/* check if shift value is less then max result bits */
	if (rs->u.max >= opsz) {
		eval_max_bound(rd, msk);
		return;
	}

	rd->u.max >>= rs->u.min;
	rd->u.min >>= rs->u.max;

	/* check that dreg values are always positive */
	if ((uint64_t)rd->s.min >> (opsz - 1) != 0)
		eval_smax_bound(rd, msk);
	else {
		rd->s.max >>= rs->u.min;
		rd->s.min >>= rs->u.max;
	}
}

static void
eval_arsh(struct bpf_reg_val *rd, const struct bpf_reg_val *rs, size_t opsz,
	uint64_t msk)
{
	uint32_t shv;

	/* check if shift value is less then max result bits */
	if (rs->u.max >= opsz) {
		eval_max_bound(rd, msk);
		return;
	}

	rd->u.max = (int64_t)rd->u.max >> rs->u.min;
	rd->u.min = (int64_t)rd->u.min >> rs->u.max;

	/* if we have 32-bit values - extend them to 64-bit */
	if (opsz == sizeof(uint32_t) * CHAR_BIT) {
		rd->s.min <<= opsz;
		rd->s.max <<= opsz;
		shv = opsz;
	} else
		shv = 0;

	if (rd->s.min < 0)
		rd->s.min = (rd->s.min >> (rs->u.min + shv)) & msk;
	else
		rd->s.min = (rd->s.min >> (rs->u.max + shv)) & msk;

	if (rd->s.max < 0)
		rd->s.max = (rd->s.max >> (rs->u.max + shv)) & msk;
	else
		rd->s.max = (rd->s.max >> (rs->u.min + shv)) & msk;
}

static uint64_t
eval_umax_bits(uint64_t v, size_t opsz)
{
	if (v == 0)
		return 0;

	v = rte_clz64(v);
	return RTE_LEN2MASK(opsz - v, uint64_t);
}

/* estimate max possible value for (v1 & v2) */
static uint64_t
eval_uand_max(uint64_t v1, uint64_t v2, size_t opsz)
{
	v1 = eval_umax_bits(v1, opsz);
	v2 = eval_umax_bits(v2, opsz);
	return (v1 & v2);
}

/* estimate max possible value for (v1 | v2) */
static uint64_t
eval_uor_max(uint64_t v1, uint64_t v2, size_t opsz)
{
	v1 = eval_umax_bits(v1, opsz);
	v2 = eval_umax_bits(v2, opsz);
	return (v1 | v2);
}

static void
eval_and(struct bpf_reg_val *rd, const struct bpf_reg_val *rs, size_t opsz,
	uint64_t msk)
{
	/* both operands are constants */
	if (rd->u.min == rd->u.max && rs->u.min == rs->u.max) {
		rd->u.min &= rs->u.min;
		rd->u.max &= rs->u.max;
	} else {
		rd->u.max = eval_uand_max(rd->u.max, rs->u.max, opsz);
		rd->u.min = 0;
	}

	/* both operands are constants */
	if (rd->s.min == rd->s.max && rs->s.min == rs->s.max) {
		rd->s.min &= rs->s.min;
		rd->s.max &= rs->s.max;
	/* at least one of operand is non-negative */
	} else if (rd->s.min >= 0 || rs->s.min >= 0) {
		rd->s.max = eval_uand_max(rd->s.max & (msk >> 1),
			rs->s.max & (msk >> 1), opsz);
		rd->s.min = 0;
	} else
		eval_smax_bound(rd, msk);
}

static void
eval_or(struct bpf_reg_val *rd, const struct bpf_reg_val *rs, size_t opsz,
	uint64_t msk)
{
	/* both operands are constants */
	if (rd->u.min == rd->u.max && rs->u.min == rs->u.max) {
		rd->u.min |= rs->u.min;
		rd->u.max |= rs->u.max;
	} else {
		rd->u.max = eval_uor_max(rd->u.max, rs->u.max, opsz);
		rd->u.min = RTE_MAX(rd->u.min, rs->u.min);
	}

	/* both operands are constants */
	if (rd->s.min == rd->s.max && rs->s.min == rs->s.max) {
		rd->s.min |= rs->s.min;
		rd->s.max |= rs->s.max;

	/* both operands are non-negative */
	} else if (rd->s.min >= 0 && rs->s.min >= 0) {
		rd->s.max = eval_uor_max(rd->s.max, rs->s.max, opsz);
		rd->s.min = RTE_MAX(rd->s.min, rs->s.min);
	} else
		eval_smax_bound(rd, msk);
}

static void
eval_xor(struct bpf_reg_val *rd, const struct bpf_reg_val *rs, size_t opsz,
	uint64_t msk)
{
	/* both operands are constants */
	if (rd->u.min == rd->u.max && rs->u.min == rs->u.max) {
		rd->u.min ^= rs->u.min;
		rd->u.max ^= rs->u.max;
	} else {
		rd->u.max = eval_uor_max(rd->u.max, rs->u.max, opsz);
		rd->u.min = 0;
	}

	/* both operands are constants */
	if (rd->s.min == rd->s.max && rs->s.min == rs->s.max) {
		rd->s.min ^= rs->s.min;
		rd->s.max ^= rs->s.max;

	/* both operands are non-negative */
	} else if (rd->s.min >= 0 && rs->s.min >= 0) {
		rd->s.max = eval_uor_max(rd->s.max, rs->s.max, opsz);
		rd->s.min = 0;
	} else
		eval_smax_bound(rd, msk);
}

static void
eval_mul(struct bpf_reg_val *rd, const struct bpf_reg_val *rs, size_t opsz,
	uint64_t msk)
{
	/* both operands are constants */
	if (rd->u.min == rd->u.max && rs->u.min == rs->u.max) {
		rd->u.min = (rd->u.min * rs->u.min) & msk;
		rd->u.max = (rd->u.max * rs->u.max) & msk;
	/* check for overflow */
	} else if (rd->u.max <= msk >> opsz / 2 && rs->u.max <= msk >> opsz) {
		rd->u.max *= rs->u.max;
		rd->u.min *= rs->u.min;
	} else
		eval_umax_bound(rd, msk);

	/* both operands are constants */
	if (rd->s.min == rd->s.max && rs->s.min == rs->s.max) {
		rd->s.min = ((uint64_t)rd->s.min * (uint64_t)rs->s.min) & msk;
		rd->s.max = ((uint64_t)rd->s.max * (uint64_t)rs->s.max) & msk;
	/* check that both operands are positive and no overflow */
	} else if (rd->s.min >= 0 && rs->s.min >= 0) {
		rd->s.max *= rs->s.max;
		rd->s.min *= rs->s.min;
	} else
		eval_smax_bound(rd, msk);
}

static const char *
eval_divmod(uint32_t op, struct bpf_reg_val *rd, struct bpf_reg_val *rs, uint64_t msk)
{
	/* both operands are constants */
	if (rd->u.min == rd->u.max && rs->u.min == rs->u.max) {
		if (rs->u.max == 0)
			return "division by 0";
		if (op == BPF_DIV) {
			rd->u.min /= rs->u.min;
			rd->u.max /= rs->u.max;
		} else {
			rd->u.min %= rs->u.min;
			rd->u.max %= rs->u.max;
		}
	} else {
		if (op == BPF_MOD)
			rd->u.max = RTE_MIN(rd->u.max, rs->u.max - 1);
		else
			rd->u.max = rd->u.max;
		rd->u.min = 0;
	}

	if (rd->u.min >= (uint64_t)INT64_MIN || rd->u.max <= (uint64_t)INT64_MAX) {
		/*
		 * All values have the same sign bit, which means range
		 * contiguous as unsigned is also contiguous as signed,
		 * so we can just reuse it without any changes.
		 */
		rd->s.min = rd->u.min;
		rd->s.max = rd->u.max;
	} else
		eval_smax_bound(rd, msk);

	return NULL;
}

static void
eval_neg(struct bpf_reg_val *rd, size_t opsz, uint64_t msk)
{
	uint64_t ux, uy;
	int64_t sx, sy;
	/* additional limits imposed by signed on unsigned and back */
	struct bpf_reg_val cross_limits = {
		.s = { INT64_MIN, INT64_MAX },
		.u = { 0, UINT64_MAX },
	};

	/* if we have 32-bit values - extend them to 64-bit */
	if (opsz == sizeof(uint32_t) * CHAR_BIT) {
		rd->u.min = (int32_t)rd->u.min;
		rd->u.max = (int32_t)rd->u.max;
	}

	if (rd->u.min == 0) {
		/* special case: ranges that include 0 and, possibly, 1 */

		/*
		 * Calculate requirements on the signed range of negation.
		 * It is only possible when negated range does not cross from
		 * INT64_MIN to INT64_MAX, which means our original range does
		 * not reach (uint64_t)-INT64_MAX.
		 */
		if (rd->u.max < (uint64_t)-INT64_MAX) {
			cross_limits.s.min = -rd->u.max;
			cross_limits.s.max = -rd->u.min;
		}

		if (rd->u.max != 0)
			rd->u.max = UINT64_MAX;
	} else {
		ux = -rd->u.min & msk;
		uy = -rd->u.max & msk;

		rd->u.max = RTE_MAX(ux, uy);
		rd->u.min = RTE_MIN(ux, uy);
	}

	/* if we have 32-bit values - extend them to 64-bit */
	if (opsz == sizeof(uint32_t) * CHAR_BIT) {
		rd->s.min = (int32_t)rd->s.min;
		rd->s.max = (int32_t)rd->s.max;
	}

	if (rd->s.min == INT64_MIN) {
		/* special case: negation of INT64_MIN is INT64_MIN */
		if (rd->s.max <= 0) {
			cross_limits.u.min = -(uint64_t)rd->s.max;
			cross_limits.u.max = -(uint64_t)rd->s.min;
		}
		if (rd->s.max != INT64_MIN)
			rd->s.max = INT64_MAX;
	} else {
		/* since max >= min, neither can be INT64_MIN here */
		sx = -rd->s.min & msk;
		sy = -rd->s.max & msk;

		rd->s.max = RTE_MAX(sx, sy);
		rd->s.min = RTE_MIN(sx, sy);
	}

	rd->s.min = RTE_MAX(rd->s.min, cross_limits.s.min) & msk;
	rd->s.max = RTE_MIN(rd->s.max, cross_limits.s.max) & msk;
	rd->u.min = RTE_MAX(rd->u.min, cross_limits.u.min) & msk;
	rd->u.max = RTE_MIN(rd->u.max, cross_limits.u.max) & msk;
}

static const char *
eval_ld_mbuf(struct bpf_verifier *bvf, const struct ebpf_insn *ins)
{
	uint32_t i, mode;
	struct bpf_reg_val *rv, ri, rs;

	mode = BPF_MODE(ins->code);

	/* R6 is an implicit input that must contain pointer to mbuf */
	if (bvf->evst->rv[EBPF_REG_6].v.type != RTE_BPF_ARG_PTR_MBUF)
		return "invalid type for implicit ctx register";

	if (mode == BPF_IND) {
		rs = bvf->evst->rv[ins->src_reg];
		if (rs.v.type != RTE_BPF_ARG_RAW)
			return "unexpected type for src register";

		eval_fill_imm(&ri, UINT64_MAX, ins->imm);
		eval_add(&rs, &ri, UINT64_MAX);

		if (rs.s.max < 0 || rs.u.min > UINT32_MAX)
			return "mbuf boundary violation";
	}

	/* R1-R5 scratch registers */
	for (i = EBPF_REG_1; i != EBPF_REG_6; i++)
		bvf->evst->rv[i].v.type = RTE_BPF_ARG_UNDEF;

	/* R0 is an implicit output, contains data fetched from the packet */
	rv = bvf->evst->rv + EBPF_REG_0;
	rv->v.size = bpf_size(BPF_SIZE(ins->code));
	eval_fill_max_bound(rv, RTE_LEN2MASK(rv->v.size * CHAR_BIT, uint64_t));

	return NULL;
}

/*
 * check that destination and source operand are in defined state.
 */
static const char *
eval_defined(const struct bpf_reg_val *dst, const struct bpf_reg_val *src)
{
	if (dst != NULL && dst->v.type == RTE_BPF_ARG_UNDEF)
		return "dest reg value is undefined";
	if (src != NULL && src->v.type == RTE_BPF_ARG_UNDEF)
		return "src reg value is undefined";
	return NULL;
}

static const char *
eval_alu(struct bpf_verifier *bvf, const struct ebpf_insn *ins)
{
	uint64_t msk;
	uint32_t op;
	size_t opsz, sz;
	const char *err;
	struct bpf_eval_state *st;
	struct bpf_reg_val *rd, rs;

	sz = (BPF_CLASS(ins->code) == BPF_ALU) ?
		sizeof(uint32_t) : sizeof(uint64_t);
	opsz = sz * CHAR_BIT;
	msk = RTE_LEN2MASK(opsz, uint64_t);

	st = bvf->evst;
	rd = st->rv + ins->dst_reg;

	if (BPF_SRC(ins->code) == BPF_X) {
		rs = st->rv[ins->src_reg];
		eval_apply_mask(&rs, msk);
	} else {
		rs = (struct bpf_reg_val){.v = {.size = sz,},};
		eval_fill_imm(&rs, msk, ins->imm);
	}

	eval_apply_mask(rd, msk);

	op = BPF_OP(ins->code);

	/* Allow self-xor as way to zero register */
	if (op == BPF_XOR && BPF_SRC(ins->code) == BPF_X &&
	    ins->src_reg == ins->dst_reg) {
		eval_fill_imm(&rs, UINT64_MAX, 0);
		eval_fill_imm(rd, UINT64_MAX, 0);
	}

	err = eval_defined((op != EBPF_MOV) ? rd : NULL,
			   (op != BPF_NEG) ? &rs : NULL);
	if (err != NULL)
		return err;

	if (op == BPF_ADD)
		eval_add(rd, &rs, msk);
	else if (op == BPF_SUB)
		eval_sub(rd, &rs, msk);
	else if (op == BPF_LSH)
		eval_lsh(rd, &rs, opsz, msk);
	else if (op == BPF_RSH)
		eval_rsh(rd, &rs, opsz, msk);
	else if (op == EBPF_ARSH)
		eval_arsh(rd, &rs, opsz, msk);
	else if (op == BPF_AND)
		eval_and(rd, &rs, opsz, msk);
	else if (op == BPF_OR)
		eval_or(rd, &rs, opsz, msk);
	else if (op == BPF_XOR)
		eval_xor(rd, &rs, opsz, msk);
	else if (op == BPF_MUL)
		eval_mul(rd, &rs, opsz, msk);
	else if (op == BPF_DIV || op == BPF_MOD)
		err = eval_divmod(op, rd, &rs, msk);
	else if (op == BPF_NEG)
		eval_neg(rd, opsz, msk);
	else if (op == EBPF_MOV)
		*rd = rs;
	else
		eval_max_bound(rd, msk);

	return err;
}

static const char *
eval_bele(struct bpf_verifier *bvf, const struct ebpf_insn *ins)
{
	uint64_t msk;
	struct bpf_eval_state *st;
	struct bpf_reg_val *rd;
	const char *err;

	msk = RTE_LEN2MASK(ins->imm, uint64_t);

	st = bvf->evst;
	rd = st->rv + ins->dst_reg;

	err = eval_defined(rd, NULL);
	if (err != NULL)
		return err;

#if RTE_BYTE_ORDER == RTE_LITTLE_ENDIAN
	if (ins->code == (BPF_ALU | EBPF_END | EBPF_TO_BE))
		eval_max_bound(rd, msk);
	else
		eval_apply_mask(rd, msk);
#else
	if (ins->code == (BPF_ALU | EBPF_END | EBPF_TO_LE))
		eval_max_bound(rd, msk);
	else
		eval_apply_mask(rd, msk);
#endif

	return NULL;
}

static const char *
eval_ptr(struct bpf_verifier *bvf, struct bpf_reg_val *rm, uint32_t opsz,
	uint32_t align, int16_t off)
{
	struct bpf_reg_val rv;

	/* calculate reg + offset */
	eval_fill_imm(&rv, rm->mask, off);
	eval_add(rm, &rv, rm->mask);

	if (RTE_BPF_ARG_PTR_TYPE(rm->v.type) == 0)
		return "destination is not a pointer";

	if (rm->mask != UINT64_MAX)
		return "pointer truncation";

	if (rm->u.max + opsz > rm->v.size ||
			(uint64_t)rm->s.max + opsz > rm->v.size ||
			rm->s.min < 0)
		return "memory boundary violation";

	if (rm->u.max % align !=  0)
		return "unaligned memory access";

	if (rm->v.type == BPF_ARG_PTR_STACK) {

		if (rm->u.max != rm->u.min || rm->s.max != rm->s.min ||
				rm->u.max != (uint64_t)rm->s.max)
			return "stack access with variable offset";

		bvf->stack_sz = RTE_MAX(bvf->stack_sz, rm->v.size - rm->u.max);

	/* pointer to mbuf */
	} else if (rm->v.type == RTE_BPF_ARG_PTR_MBUF) {

		if (rm->u.max != rm->u.min || rm->s.max != rm->s.min ||
				rm->u.max != (uint64_t)rm->s.max)
			return "mbuf access with variable offset";
	}

	return NULL;
}

static void
eval_max_load(struct bpf_reg_val *rv, uint64_t mask)
{
	eval_umax_bound(rv, mask);

	/* full 64-bit load */
	if (mask == UINT64_MAX)
		eval_smax_bound(rv, mask);
	else {
		/* zero-extend load */
		rv->s.min = rv->u.min;
		rv->s.max = rv->u.max;
	}
}


static const char *
eval_load(struct bpf_verifier *bvf, const struct ebpf_insn *ins)
{
	uint32_t opsz;
	uint64_t msk;
	const char *err;
	struct bpf_eval_state *st;
	struct bpf_reg_val *rd, rs;
	const struct bpf_reg_val *sv;

	st = bvf->evst;
	rd = st->rv + ins->dst_reg;
	rs = st->rv[ins->src_reg];
	opsz = bpf_size(BPF_SIZE(ins->code));
	msk = RTE_LEN2MASK(opsz * CHAR_BIT, uint64_t);

	err = eval_ptr(bvf, &rs, opsz, 1, ins->off);
	if (err != NULL)
		return err;

	if (rs.v.type == BPF_ARG_PTR_STACK) {

		sv = st->sv + rs.u.max / sizeof(uint64_t);
		if (sv->v.type == RTE_BPF_ARG_UNDEF || sv->mask < msk)
			return "undefined value on the stack";

		*rd = *sv;

	/* pointer to mbuf */
	} else if (rs.v.type == RTE_BPF_ARG_PTR_MBUF) {

		if (rs.u.max == offsetof(struct rte_mbuf, next)) {
			eval_fill_imm(rd, msk, 0);
			rd->v = rs.v;
		} else if (rs.u.max == offsetof(struct rte_mbuf, buf_addr)) {
			eval_fill_imm(rd, msk, 0);
			rd->v.type = RTE_BPF_ARG_PTR;
			rd->v.size = rs.v.buf_size;
		} else if (rs.u.max == offsetof(struct rte_mbuf, data_off)) {
			eval_fill_imm(rd, msk, RTE_PKTMBUF_HEADROOM);
			rd->v.type = RTE_BPF_ARG_RAW;
		} else {
			eval_max_load(rd, msk);
			rd->v.type = RTE_BPF_ARG_RAW;
		}

	/* pointer to raw data */
	} else {
		eval_max_load(rd, msk);
		rd->v.type = RTE_BPF_ARG_RAW;
	}

	return NULL;
}

static const char *
eval_mbuf_store(const struct bpf_reg_val *rv, uint32_t opsz)
{
	uint32_t i;

	static const struct {
		size_t off;
		size_t sz;
	} mbuf_ro_fileds[] = {
		{ .off = offsetof(struct rte_mbuf, buf_addr), },
		{ .off = offsetof(struct rte_mbuf, refcnt), },
		{ .off = offsetof(struct rte_mbuf, nb_segs), },
		{ .off = offsetof(struct rte_mbuf, buf_len), },
		{ .off = offsetof(struct rte_mbuf, pool), },
		{ .off = offsetof(struct rte_mbuf, next), },
		{ .off = offsetof(struct rte_mbuf, priv_size), },
	};

	for (i = 0; i != RTE_DIM(mbuf_ro_fileds) &&
			(mbuf_ro_fileds[i].off + mbuf_ro_fileds[i].sz <=
			rv->u.max || rv->u.max + opsz <= mbuf_ro_fileds[i].off);
			i++)
		;

	if (i != RTE_DIM(mbuf_ro_fileds))
		return "store to the read-only mbuf field";

	return NULL;

}

static const char *
eval_store(struct bpf_verifier *bvf, const struct ebpf_insn *ins)
{
	uint32_t opsz;
	uint64_t msk;
	const char *err;
	struct bpf_eval_state *st;
	struct bpf_reg_val rd, rs, *sv;

	opsz = bpf_size(BPF_SIZE(ins->code));
	msk = RTE_LEN2MASK(opsz * CHAR_BIT, uint64_t);

	st = bvf->evst;
	rd = st->rv[ins->dst_reg];

	if (BPF_CLASS(ins->code) == BPF_STX) {
		rs = st->rv[ins->src_reg];
		if (BPF_MODE(ins->code) == EBPF_ATOMIC)
			switch (ins->imm) {
			case BPF_ATOMIC_ADD:
				break;
			case BPF_ATOMIC_XCHG:
				eval_max_bound(&st->rv[ins->src_reg], msk);
				break;
			default:
				return "unsupported atomic operation";
			}
		eval_apply_mask(&rs, msk);
	} else
		eval_fill_imm(&rs, msk, ins->imm);

	err = eval_defined(NULL, &rs);
	if (err != NULL)
		return err;

	err = eval_ptr(bvf, &rd, opsz, 1, ins->off);
	if (err != NULL)
		return err;

	if (rd.v.type == BPF_ARG_PTR_STACK) {

		sv = st->sv + rd.u.max / sizeof(uint64_t);
		if (BPF_CLASS(ins->code) == BPF_STX &&
				BPF_MODE(ins->code) == EBPF_ATOMIC)
			eval_max_bound(sv, msk);
		else
			*sv = rs;

	/* pointer to mbuf */
	} else if (rd.v.type == RTE_BPF_ARG_PTR_MBUF) {
		err = eval_mbuf_store(&rd, opsz);
		if (err != NULL)
			return err;
	}

	return NULL;
}

static const char *
eval_ja(struct bpf_verifier *bvf, const struct ebpf_insn *ins)
{
	RTE_SET_USED(bvf);
	RTE_SET_USED(ins);
	return NULL;
}

static const char *
eval_func_arg(struct bpf_verifier *bvf, const struct rte_bpf_arg *arg,
	struct bpf_reg_val *rv)
{
	uint32_t i, n;
	struct bpf_eval_state *st;
	const char *err;

	st = bvf->evst;

	if (rv->v.type == RTE_BPF_ARG_UNDEF)
		return "Undefined argument type";

	if (arg->type != rv->v.type &&
			arg->type != RTE_BPF_ARG_RAW &&
			(arg->type != RTE_BPF_ARG_PTR ||
			RTE_BPF_ARG_PTR_TYPE(rv->v.type) == 0))
		return "Invalid argument type";

	err = NULL;

	/* argument is a pointer */
	if (RTE_BPF_ARG_PTR_TYPE(arg->type) != 0) {

		err = eval_ptr(bvf, rv, arg->size, 1, 0);

		/*
		 * pointer to the variable on the stack is passed
		 * as an argument, mark stack space it occupies as initialized.
		 */
		if (err == NULL && rv->v.type == BPF_ARG_PTR_STACK) {

			i = rv->u.max / sizeof(uint64_t);
			n = i + arg->size / sizeof(uint64_t);
			while (i != n) {
				eval_fill_max_bound(st->sv + i, UINT64_MAX);
				i++;
			};
		}
	}

	return err;
}

static const char *
eval_call(struct bpf_verifier *bvf, const struct ebpf_insn *ins)
{
	uint32_t i, idx;
	struct bpf_reg_val *rv;
	const struct rte_bpf_xsym *xsym;
	const char *err;

	idx = ins->imm;

	if (idx >= bvf->prm->nb_xsym ||
			bvf->prm->xsym[idx].type != RTE_BPF_XTYPE_FUNC)
		return "invalid external function index";

	/* for now don't support function calls on 32 bit platform */
	if (sizeof(uint64_t) != sizeof(uintptr_t))
		return "function calls are supported only for 64 bit apps";

	xsym = bvf->prm->xsym + idx;

	/* evaluate function arguments */
	err = NULL;
	for (i = 0; i != xsym->func.nb_args && err == NULL; i++) {
		err = eval_func_arg(bvf, xsym->func.args + i,
			bvf->evst->rv + EBPF_REG_1 + i);
	}

	/* R1-R5 argument/scratch registers */
	for (i = EBPF_REG_1; i != EBPF_REG_6; i++)
		bvf->evst->rv[i].v.type = RTE_BPF_ARG_UNDEF;

	/* update return value */

	rv = bvf->evst->rv + EBPF_REG_0;
	rv->v = xsym->func.ret;
	if (rv->v.type == RTE_BPF_ARG_RAW)
		eval_fill_max_bound(rv,
			RTE_LEN2MASK(rv->v.size * CHAR_BIT, uint64_t));
	else if (RTE_BPF_ARG_PTR_TYPE(rv->v.type) != 0)
		eval_fill_imm64(rv, UINTPTR_MAX, 0);

	return err;
}

static void
eval_jeq_jne(struct bpf_reg_val *trd, struct bpf_reg_val *trs)
{
	/* sreg is constant */
	if (trs->u.min == trs->u.max) {
		trd->u = trs->u;
	/* dreg is constant */
	} else if (trd->u.min == trd->u.max) {
		trs->u = trd->u;
	} else {
		trd->u.max = RTE_MIN(trd->u.max, trs->u.max);
		trd->u.min = RTE_MAX(trd->u.min, trs->u.min);
		trs->u = trd->u;
	}

	/* sreg is constant */
	if (trs->s.min == trs->s.max) {
		trd->s = trs->s;
	/* dreg is constant */
	} else if (trd->s.min == trd->s.max) {
		trs->s = trd->s;
	} else {
		trd->s.max = RTE_MIN(trd->s.max, trs->s.max);
		trd->s.min = RTE_MAX(trd->s.min, trs->s.min);
		trs->s = trd->s;
	}
}

static void
eval_jgt_jle(struct bpf_reg_val *trd, struct bpf_reg_val *trs,
	struct bpf_reg_val *frd, struct bpf_reg_val *frs)
{
	if (frd->u.min <= frs->u.max) {
		frd->u.max = RTE_MIN(frd->u.max, frs->u.max);
		frs->u.min = RTE_MAX(frs->u.min, frd->u.min);
	} else
		frd->v.type = frs->v.type = BPF_ARG_UNINHABITED;

	if (trs->u.min < trd->u.max) {
		trd->u.min = RTE_MAX(trd->u.min, trs->u.min + 1);
		trs->u.max = RTE_MIN(trs->u.max, trd->u.max - 1);
	} else
		trd->v.type = trs->v.type = BPF_ARG_UNINHABITED;
}

static void
eval_jlt_jge(struct bpf_reg_val *trd, struct bpf_reg_val *trs,
	struct bpf_reg_val *frd, struct bpf_reg_val *frs)
{
	if (frs->u.min <= frd->u.max) {
		frd->u.min = RTE_MAX(frd->u.min, frs->u.min);
		frs->u.max = RTE_MIN(frs->u.max, frd->u.max);
	} else
		frd->v.type = frs->v.type = BPF_ARG_UNINHABITED;

	if (trd->u.min < trs->u.max) {
		trd->u.max = RTE_MIN(trd->u.max, trs->u.max - 1);
		trs->u.min = RTE_MAX(trs->u.min, trd->u.min + 1);
	} else
		trd->v.type = trs->v.type = BPF_ARG_UNINHABITED;
}

static void
eval_jsgt_jsle(struct bpf_reg_val *trd, struct bpf_reg_val *trs,
	struct bpf_reg_val *frd, struct bpf_reg_val *frs)
{
	if (frd->s.min <= frs->s.max) {
		frd->s.max = RTE_MIN(frd->s.max, frs->s.max);
		frs->s.min = RTE_MAX(frs->s.min, frd->s.min);
	} else
		frd->v.type = frs->v.type = BPF_ARG_UNINHABITED;

	if (trs->s.min < trd->s.max) {
		trd->s.min = RTE_MAX(trd->s.min, trs->s.min + 1);
		trs->s.max = RTE_MIN(trs->s.max, trd->s.max - 1);
	} else
		trd->v.type = trs->v.type = BPF_ARG_UNINHABITED;
}

static void
eval_jslt_jsge(struct bpf_reg_val *trd, struct bpf_reg_val *trs,
	struct bpf_reg_val *frd, struct bpf_reg_val *frs)
{
	if (frs->s.min <= frd->s.max) {
		frd->s.min = RTE_MAX(frd->s.min, frs->s.min);
		frs->s.max = RTE_MIN(frs->s.max, frd->s.max);
	} else
		frd->v.type = frs->v.type = BPF_ARG_UNINHABITED;

	if (trd->s.min < trs->s.max) {
		trd->s.max = RTE_MIN(trd->s.max, trs->s.max - 1);
		trs->s.min = RTE_MAX(trs->s.min, trd->s.min + 1);
	} else
		trd->v.type = trs->v.type = BPF_ARG_UNINHABITED;
}

static const char *
eval_jcc(struct bpf_verifier *bvf, const struct ebpf_insn *ins)
{
	uint32_t op;
	const char *err;
	struct bpf_eval_state *fst, *tst;
	struct bpf_reg_val *frd, *frs, *trd, *trs;
	struct bpf_reg_val rvf, rvt;

	tst = bvf->evst;
	fst = bvf->evin->evst.cur;

	frd = fst->rv + ins->dst_reg;
	trd = tst->rv + ins->dst_reg;

	if (BPF_SRC(ins->code) == BPF_X) {
		frs = fst->rv + ins->src_reg;
		trs = tst->rv + ins->src_reg;
	} else {
		frs = &rvf;
		trs = &rvt;
		eval_fill_imm(frs, UINT64_MAX, ins->imm);
		eval_fill_imm(trs, UINT64_MAX, ins->imm);
	}

	err = eval_defined(trd, trs);
	if (err != NULL)
		return err;

	op = BPF_OP(ins->code);

	if (op == BPF_JEQ)
		eval_jeq_jne(trd, trs);
	else if (op == EBPF_JNE)
		eval_jeq_jne(frd, frs);
	else if (op == BPF_JGT)
		eval_jgt_jle(trd, trs, frd, frs);
	else if (op == EBPF_JLE)
		eval_jgt_jle(frd, frs, trd, trs);
	else if (op == EBPF_JLT)
		eval_jlt_jge(trd, trs, frd, frs);
	else if (op == BPF_JGE)
		eval_jlt_jge(frd, frs, trd, trs);
	else if (op == EBPF_JSGT)
		eval_jsgt_jsle(trd, trs, frd, frs);
	else if (op == EBPF_JSLE)
		eval_jsgt_jsle(frd, frs, trd, trs);
	else if (op == EBPF_JSLT)
		eval_jslt_jsge(trd, trs, frd, frs);
	else if (op == EBPF_JSGE)
		eval_jslt_jsge(frd, frs, trd, trs);

	if (trd->v.type == BPF_ARG_UNINHABITED ||
			trs->v.type == BPF_ARG_UNINHABITED)
		tst->unreachable = true;

	if (frd->v.type == BPF_ARG_UNINHABITED ||
			frs->v.type == BPF_ARG_UNINHABITED)
		fst->unreachable = true;

	return NULL;
}

/*
 * validate parameters for each instruction type.
 */
static const struct bpf_ins_check ins_chk[UINT8_MAX + 1] = {
	/* ALU IMM 32-bit instructions */
	[(BPF_ALU | BPF_ADD | BPF_K)] = {
		.mask = {.dreg = WRT_REGS, .sreg = ZERO_REG},
		.off = { .min = 0, .max = 0},
		.imm = { .min = 0, .max = UINT32_MAX,},
		.eval = eval_alu,
	},
	[(BPF_ALU | BPF_SUB | BPF_K)] = {
		.mask = {.dreg = WRT_REGS, .sreg = ZERO_REG},
		.off = { .min = 0, .max = 0},
		.imm = { .min = 0, .max = UINT32_MAX,},
		.eval = eval_alu,
	},
	[(BPF_ALU | BPF_AND | BPF_K)] = {
		.mask = {.dreg = WRT_REGS, .sreg = ZERO_REG},
		.off = { .min = 0, .max = 0},
		.imm = { .min = 0, .max = UINT32_MAX,},
		.eval = eval_alu,
	},
	[(BPF_ALU | BPF_OR | BPF_K)] = {
		.mask = {.dreg = WRT_REGS, .sreg = ZERO_REG},
		.off = { .min = 0, .max = 0},
		.imm = { .min = 0, .max = UINT32_MAX,},
		.eval = eval_alu,
	},
	[(BPF_ALU | BPF_LSH | BPF_K)] = {
		.mask = {.dreg = WRT_REGS, .sreg = ZERO_REG},
		.off = { .min = 0, .max = 0},
		.imm = { .min = 0, .max = UINT32_MAX,},
		.eval = eval_alu,
	},
	[(BPF_ALU | BPF_RSH | BPF_K)] = {
		.mask = {.dreg = WRT_REGS, .sreg = ZERO_REG},
		.off = { .min = 0, .max = 0},
		.imm = { .min = 0, .max = UINT32_MAX,},
		.eval = eval_alu,
	},
	[(BPF_ALU | BPF_XOR | BPF_K)] = {
		.mask = {.dreg = WRT_REGS, .sreg = ZERO_REG},
		.off = { .min = 0, .max = 0},
		.imm = { .min = 0, .max = UINT32_MAX,},
		.eval = eval_alu,
	},
	[(BPF_ALU | BPF_MUL | BPF_K)] = {
		.mask = {.dreg = WRT_REGS, .sreg = ZERO_REG},
		.off = { .min = 0, .max = 0},
		.imm = { .min = 0, .max = UINT32_MAX,},
		.eval = eval_alu,
	},
	[(BPF_ALU | EBPF_MOV | BPF_K)] = {
		.mask = {.dreg = WRT_REGS, .sreg = ZERO_REG},
		.off = { .min = 0, .max = 0},
		.imm = { .min = 0, .max = UINT32_MAX,},
		.eval = eval_alu,
	},
	[(BPF_ALU | BPF_DIV | BPF_K)] = {
		.mask = { .dreg = WRT_REGS, .sreg = ZERO_REG},
		.off = { .min = 0, .max = 0},
		.imm = { .min = 1, .max = UINT32_MAX},
		.eval = eval_alu,
	},
	[(BPF_ALU | BPF_MOD | BPF_K)] = {
		.mask = { .dreg = WRT_REGS, .sreg = ZERO_REG},
		.off = { .min = 0, .max = 0},
		.imm = { .min = 1, .max = UINT32_MAX},
		.eval = eval_alu,
	},
	/* ALU IMM 64-bit instructions */
	[(EBPF_ALU64 | BPF_ADD | BPF_K)] = {
		.mask = {.dreg = WRT_REGS, .sreg = ZERO_REG},
		.off = { .min = 0, .max = 0},
		.imm = { .min = 0, .max = UINT32_MAX,},
		.eval = eval_alu,
	},
	[(EBPF_ALU64 | BPF_SUB | BPF_K)] = {
		.mask = {.dreg = WRT_REGS, .sreg = ZERO_REG},
		.off = { .min = 0, .max = 0},
		.imm = { .min = 0, .max = UINT32_MAX,},
		.eval = eval_alu,
	},
	[(EBPF_ALU64 | BPF_AND | BPF_K)] = {
		.mask = {.dreg = WRT_REGS, .sreg = ZERO_REG},
		.off = { .min = 0, .max = 0},
		.imm = { .min = 0, .max = UINT32_MAX,},
		.eval = eval_alu,
	},
	[(EBPF_ALU64 | BPF_OR | BPF_K)] = {
		.mask = {.dreg = WRT_REGS, .sreg = ZERO_REG},
		.off = { .min = 0, .max = 0},
		.imm = { .min = 0, .max = UINT32_MAX,},
		.eval = eval_alu,
	},
	[(EBPF_ALU64 | BPF_LSH | BPF_K)] = {
		.mask = {.dreg = WRT_REGS, .sreg = ZERO_REG},
		.off = { .min = 0, .max = 0},
		.imm = { .min = 0, .max = UINT32_MAX,},
		.eval = eval_alu,
	},
	[(EBPF_ALU64 | BPF_RSH | BPF_K)] = {
		.mask = {.dreg = WRT_REGS, .sreg = ZERO_REG},
		.off = { .min = 0, .max = 0},
		.imm = { .min = 0, .max = UINT32_MAX,},
		.eval = eval_alu,
	},
	[(EBPF_ALU64 | EBPF_ARSH | BPF_K)] = {
		.mask = {.dreg = WRT_REGS, .sreg = ZERO_REG},
		.off = { .min = 0, .max = 0},
		.imm = { .min = 0, .max = UINT32_MAX,},
		.eval = eval_alu,
	},
	[(EBPF_ALU64 | BPF_XOR | BPF_K)] = {
		.mask = {.dreg = WRT_REGS, .sreg = ZERO_REG},
		.off = { .min = 0, .max = 0},
		.imm = { .min = 0, .max = UINT32_MAX,},
		.eval = eval_alu,
	},
	[(EBPF_ALU64 | BPF_MUL | BPF_K)] = {
		.mask = {.dreg = WRT_REGS, .sreg = ZERO_REG},
		.off = { .min = 0, .max = 0},
		.imm = { .min = 0, .max = UINT32_MAX,},
		.eval = eval_alu,
	},
	[(EBPF_ALU64 | EBPF_MOV | BPF_K)] = {
		.mask = {.dreg = WRT_REGS, .sreg = ZERO_REG},
		.off = { .min = 0, .max = 0},
		.imm = { .min = 0, .max = UINT32_MAX,},
		.eval = eval_alu,
	},
	[(EBPF_ALU64 | BPF_DIV | BPF_K)] = {
		.mask = { .dreg = WRT_REGS, .sreg = ZERO_REG},
		.off = { .min = 0, .max = 0},
		.imm = { .min = 1, .max = UINT32_MAX},
		.eval = eval_alu,
	},
	[(EBPF_ALU64 | BPF_MOD | BPF_K)] = {
		.mask = { .dreg = WRT_REGS, .sreg = ZERO_REG},
		.off = { .min = 0, .max = 0},
		.imm = { .min = 1, .max = UINT32_MAX},
		.eval = eval_alu,
	},
	/* ALU REG 32-bit instructions */
	[(BPF_ALU | BPF_ADD | BPF_X)] = {
		.mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
		.off = { .min = 0, .max = 0},
		.imm = { .min = 0, .max = 0},
		.eval = eval_alu,
	},
	[(BPF_ALU | BPF_SUB | BPF_X)] = {
		.mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
		.off = { .min = 0, .max = 0},
		.imm = { .min = 0, .max = 0},
		.eval = eval_alu,
	},
	[(BPF_ALU | BPF_AND | BPF_X)] = {
		.mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
		.off = { .min = 0, .max = 0},
		.imm = { .min = 0, .max = 0},
		.eval = eval_alu,
	},
	[(BPF_ALU | BPF_OR | BPF_X)] = {
		.mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
		.off = { .min = 0, .max = 0},
		.imm = { .min = 0, .max = 0},
		.eval = eval_alu,
	},
	[(BPF_ALU | BPF_LSH | BPF_X)] = {
		.mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
		.off = { .min = 0, .max = 0},
		.imm = { .min = 0, .max = 0},
		.eval = eval_alu,
	},
	[(BPF_ALU | BPF_RSH | BPF_X)] = {
		.mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
		.off = { .min = 0, .max = 0},
		.imm = { .min = 0, .max = 0},
		.eval = eval_alu,
	},
	[(BPF_ALU | BPF_XOR | BPF_X)] = {
		.mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
		.off = { .min = 0, .max = 0},
		.imm = { .min = 0, .max = 0},
		.eval = eval_alu,
	},
	[(BPF_ALU | BPF_MUL | BPF_X)] = {
		.mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
		.off = { .min = 0, .max = 0},
		.imm = { .min = 0, .max = 0},
		.eval = eval_alu,
	},
	[(BPF_ALU | BPF_DIV | BPF_X)] = {
		.mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
		.off = { .min = 0, .max = 0},
		.imm = { .min = 0, .max = 0},
		.eval = eval_alu,
	},
	[(BPF_ALU | BPF_MOD | BPF_X)] = {
		.mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
		.off = { .min = 0, .max = 0},
		.imm = { .min = 0, .max = 0},
		.eval = eval_alu,
	},
	[(BPF_ALU | EBPF_MOV | BPF_X)] = {
		.mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
		.off = { .min = 0, .max = 0},
		.imm = { .min = 0, .max = 0},
		.eval = eval_alu,
	},
	[(BPF_ALU | BPF_NEG)] = {
		.mask = { .dreg = WRT_REGS, .sreg = ZERO_REG},
		.off = { .min = 0, .max = 0},
		.imm = { .min = 0, .max = 0},
		.eval = eval_alu,
	},
	[(BPF_ALU | EBPF_END | EBPF_TO_BE)] = {
		.mask = { .dreg = WRT_REGS, .sreg = ZERO_REG},
		.off = { .min = 0, .max = 0},
		.imm = { .min = 16, .max = 64},
		.check = check_alu_bele,
		.eval = eval_bele,
	},
	[(BPF_ALU | EBPF_END | EBPF_TO_LE)] = {
		.mask = { .dreg = WRT_REGS, .sreg = ZERO_REG},
		.off = { .min = 0, .max = 0},
		.imm = { .min = 16, .max = 64},
		.check = check_alu_bele,
		.eval = eval_bele,
	},
	/* ALU REG 64-bit instructions */
	[(EBPF_ALU64 | BPF_ADD | BPF_X)] = {
		.mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
		.off = { .min = 0, .max = 0},
		.imm = { .min = 0, .max = 0},
		.eval = eval_alu,
	},
	[(EBPF_ALU64 | BPF_SUB | BPF_X)] = {
		.mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
		.off = { .min = 0, .max = 0},
		.imm = { .min = 0, .max = 0},
		.eval = eval_alu,
	},
	[(EBPF_ALU64 | BPF_AND | BPF_X)] = {
		.mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
		.off = { .min = 0, .max = 0},
		.imm = { .min = 0, .max = 0},
		.eval = eval_alu,
	},
	[(EBPF_ALU64 | BPF_OR | BPF_X)] = {
		.mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
		.off = { .min = 0, .max = 0},
		.imm = { .min = 0, .max = 0},
		.eval = eval_alu,
	},
	[(EBPF_ALU64 | BPF_LSH | BPF_X)] = {
		.mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
		.off = { .min = 0, .max = 0},
		.imm = { .min = 0, .max = 0},
		.eval = eval_alu,
	},
	[(EBPF_ALU64 | BPF_RSH | BPF_X)] = {
		.mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
		.off = { .min = 0, .max = 0},
		.imm = { .min = 0, .max = 0},
		.eval = eval_alu,
	},
	[(EBPF_ALU64 | EBPF_ARSH | BPF_X)] = {
		.mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
		.off = { .min = 0, .max = 0},
		.imm = { .min = 0, .max = 0},
		.eval = eval_alu,
	},
	[(EBPF_ALU64 | BPF_XOR | BPF_X)] = {
		.mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
		.off = { .min = 0, .max = 0},
		.imm = { .min = 0, .max = 0},
		.eval = eval_alu,
	},
	[(EBPF_ALU64 | BPF_MUL | BPF_X)] = {
		.mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
		.off = { .min = 0, .max = 0},
		.imm = { .min = 0, .max = 0},
		.eval = eval_alu,
	},
	[(EBPF_ALU64 | BPF_DIV | BPF_X)] = {
		.mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
		.off = { .min = 0, .max = 0},
		.imm = { .min = 0, .max = 0},
		.eval = eval_alu,
	},
	[(EBPF_ALU64 | BPF_MOD | BPF_X)] = {
		.mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
		.off = { .min = 0, .max = 0},
		.imm = { .min = 0, .max = 0},
		.eval = eval_alu,
	},
	[(EBPF_ALU64 | EBPF_MOV | BPF_X)] = {
		.mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
		.off = { .min = 0, .max = 0},
		.imm = { .min = 0, .max = 0},
		.eval = eval_alu,
	},
	[(EBPF_ALU64 | BPF_NEG)] = {
		.mask = { .dreg = WRT_REGS, .sreg = ZERO_REG},
		.off = { .min = 0, .max = 0},
		.imm = { .min = 0, .max = 0},
		.eval = eval_alu,
	},
	/* load instructions */
	[(BPF_LDX | BPF_MEM | BPF_B)] = {
		.mask = {. dreg = WRT_REGS, .sreg = ALL_REGS},
		.off = { .min = 0, .max = UINT16_MAX},
		.imm = { .min = 0, .max = 0},
		.eval = eval_load,
	},
	[(BPF_LDX | BPF_MEM | BPF_H)] = {
		.mask = {. dreg = WRT_REGS, .sreg = ALL_REGS},
		.off = { .min = 0, .max = UINT16_MAX},
		.imm = { .min = 0, .max = 0},
		.eval = eval_load,
	},
	[(BPF_LDX | BPF_MEM | BPF_W)] = {
		.mask = {. dreg = WRT_REGS, .sreg = ALL_REGS},
		.off = { .min = 0, .max = UINT16_MAX},
		.imm = { .min = 0, .max = 0},
		.eval = eval_load,
	},
	[(BPF_LDX | BPF_MEM | EBPF_DW)] = {
		.mask = {. dreg = WRT_REGS, .sreg = ALL_REGS},
		.off = { .min = 0, .max = UINT16_MAX},
		.imm = { .min = 0, .max = 0},
		.eval = eval_load,
	},
	/* load 64 bit immediate value */
	[(BPF_LD | BPF_IMM | EBPF_DW)] = {
		.mask = { .dreg = WRT_REGS, .sreg = ZERO_REG},
		.off = { .min = 0, .max = 0},
		.imm = { .min = 0, .max = UINT32_MAX},
		.eval = eval_ld_imm64,
	},
	/* load absolute instructions */
	[(BPF_LD | BPF_ABS | BPF_B)] = {
		.mask = {. dreg = ZERO_REG, .sreg = ZERO_REG},
		.off = { .min = 0, .max = 0},
		.imm = { .min = 0, .max = INT32_MAX},
		.eval = eval_ld_mbuf,
	},
	[(BPF_LD | BPF_ABS | BPF_H)] = {
		.mask = {. dreg = ZERO_REG, .sreg = ZERO_REG},
		.off = { .min = 0, .max = 0},
		.imm = { .min = 0, .max = INT32_MAX},
		.eval = eval_ld_mbuf,
	},
	[(BPF_LD | BPF_ABS | BPF_W)] = {
		.mask = {. dreg = ZERO_REG, .sreg = ZERO_REG},
		.off = { .min = 0, .max = 0},
		.imm = { .min = 0, .max = INT32_MAX},
		.eval = eval_ld_mbuf,
	},
	/* load indirect instructions */
	[(BPF_LD | BPF_IND | BPF_B)] = {
		.mask = {. dreg = ZERO_REG, .sreg = IND_SRC_REGS},
		.off = { .min = 0, .max = 0},
		.imm = { .min = 0, .max = UINT32_MAX},
		.eval = eval_ld_mbuf,
	},
	[(BPF_LD | BPF_IND | BPF_H)] = {
		.mask = {. dreg = ZERO_REG, .sreg = IND_SRC_REGS},
		.off = { .min = 0, .max = 0},
		.imm = { .min = 0, .max = UINT32_MAX},
		.eval = eval_ld_mbuf,
	},
	[(BPF_LD | BPF_IND | BPF_W)] = {
		.mask = {. dreg = ZERO_REG, .sreg = IND_SRC_REGS},
		.off = { .min = 0, .max = 0},
		.imm = { .min = 0, .max = UINT32_MAX},
		.eval = eval_ld_mbuf,
	},
	/* store REG instructions */
	[(BPF_STX | BPF_MEM | BPF_B)] = {
		.mask = { .dreg = ALL_REGS, .sreg = ALL_REGS},
		.off = { .min = 0, .max = UINT16_MAX},
		.imm = { .min = 0, .max = 0},
		.eval = eval_store,
	},
	[(BPF_STX | BPF_MEM | BPF_H)] = {
		.mask = { .dreg = ALL_REGS, .sreg = ALL_REGS},
		.off = { .min = 0, .max = UINT16_MAX},
		.imm = { .min = 0, .max = 0},
		.eval = eval_store,
	},
	[(BPF_STX | BPF_MEM | BPF_W)] = {
		.mask = { .dreg = ALL_REGS, .sreg = ALL_REGS},
		.off = { .min = 0, .max = UINT16_MAX},
		.imm = { .min = 0, .max = 0},
		.eval = eval_store,
	},
	[(BPF_STX | BPF_MEM | EBPF_DW)] = {
		.mask = { .dreg = ALL_REGS, .sreg = ALL_REGS},
		.off = { .min = 0, .max = UINT16_MAX},
		.imm = { .min = 0, .max = 0},
		.eval = eval_store,
	},
	/* atomic instructions */
	[(BPF_STX | EBPF_ATOMIC | BPF_W)] = {
		.mask = { .dreg = ALL_REGS, .sreg = ALL_REGS},
		.off = { .min = 0, .max = UINT16_MAX},
		.imm = { .min = BPF_ATOMIC_ADD, .max = BPF_ATOMIC_XCHG},
		.eval = eval_store,
	},
	[(BPF_STX | EBPF_ATOMIC | EBPF_DW)] = {
		.mask = { .dreg = ALL_REGS, .sreg = ALL_REGS},
		.off = { .min = 0, .max = UINT16_MAX},
		.imm = { .min = BPF_ATOMIC_ADD, .max = BPF_ATOMIC_XCHG},
		.eval = eval_store,
	},
	/* store IMM instructions */
	[(BPF_ST | BPF_MEM | BPF_B)] = {
		.mask = { .dreg = ALL_REGS, .sreg = ZERO_REG},
		.off = { .min = 0, .max = UINT16_MAX},
		.imm = { .min = 0, .max = UINT32_MAX},
		.eval = eval_store,
	},
	[(BPF_ST | BPF_MEM | BPF_H)] = {
		.mask = { .dreg = ALL_REGS, .sreg = ZERO_REG},
		.off = { .min = 0, .max = UINT16_MAX},
		.imm = { .min = 0, .max = UINT32_MAX},
		.eval = eval_store,
	},
	[(BPF_ST | BPF_MEM | BPF_W)] = {
		.mask = { .dreg = ALL_REGS, .sreg = ZERO_REG},
		.off = { .min = 0, .max = UINT16_MAX},
		.imm = { .min = 0, .max = UINT32_MAX},
		.eval = eval_store,
	},
	[(BPF_ST | BPF_MEM | EBPF_DW)] = {
		.mask = { .dreg = ALL_REGS, .sreg = ZERO_REG},
		.off = { .min = 0, .max = UINT16_MAX},
		.imm = { .min = 0, .max = UINT32_MAX},
		.eval = eval_store,
	},
	/* jump instruction */
	[(BPF_JMP | BPF_JA)] = {
		.mask = { .dreg = ZERO_REG, .sreg = ZERO_REG},
		.off = { .min = 0, .max = UINT16_MAX},
		.imm = { .min = 0, .max = 0},
		.eval = eval_ja,
	},
	/* jcc IMM instructions */
	[(BPF_JMP | BPF_JEQ | BPF_K)] = {
		.mask = { .dreg = ALL_REGS, .sreg = ZERO_REG},
		.off = { .min = 0, .max = UINT16_MAX},
		.imm = { .min = 0, .max = UINT32_MAX},
		.eval = eval_jcc,
	},
	[(BPF_JMP | EBPF_JNE | BPF_K)] = {
		.mask = { .dreg = ALL_REGS, .sreg = ZERO_REG},
		.off = { .min = 0, .max = UINT16_MAX},
		.imm = { .min = 0, .max = UINT32_MAX},
		.eval = eval_jcc,
	},
	[(BPF_JMP | BPF_JGT | BPF_K)] = {
		.mask = { .dreg = ALL_REGS, .sreg = ZERO_REG},
		.off = { .min = 0, .max = UINT16_MAX},
		.imm = { .min = 0, .max = UINT32_MAX},
		.eval = eval_jcc,
	},
	[(BPF_JMP | EBPF_JLT | BPF_K)] = {
		.mask = { .dreg = ALL_REGS, .sreg = ZERO_REG},
		.off = { .min = 0, .max = UINT16_MAX},
		.imm = { .min = 0, .max = UINT32_MAX},
		.eval = eval_jcc,
	},
	[(BPF_JMP | BPF_JGE | BPF_K)] = {
		.mask = { .dreg = ALL_REGS, .sreg = ZERO_REG},
		.off = { .min = 0, .max = UINT16_MAX},
		.imm = { .min = 0, .max = UINT32_MAX},
		.eval = eval_jcc,
	},
	[(BPF_JMP | EBPF_JLE | BPF_K)] = {
		.mask = { .dreg = ALL_REGS, .sreg = ZERO_REG},
		.off = { .min = 0, .max = UINT16_MAX},
		.imm = { .min = 0, .max = UINT32_MAX},
		.eval = eval_jcc,
	},
	[(BPF_JMP | EBPF_JSGT | BPF_K)] = {
		.mask = { .dreg = ALL_REGS, .sreg = ZERO_REG},
		.off = { .min = 0, .max = UINT16_MAX},
		.imm = { .min = 0, .max = UINT32_MAX},
		.eval = eval_jcc,
	},
	[(BPF_JMP | EBPF_JSLT | BPF_K)] = {
		.mask = { .dreg = ALL_REGS, .sreg = ZERO_REG},
		.off = { .min = 0, .max = UINT16_MAX},
		.imm = { .min = 0, .max = UINT32_MAX},
		.eval = eval_jcc,
	},
	[(BPF_JMP | EBPF_JSGE | BPF_K)] = {
		.mask = { .dreg = ALL_REGS, .sreg = ZERO_REG},
		.off = { .min = 0, .max = UINT16_MAX},
		.imm = { .min = 0, .max = UINT32_MAX},
		.eval = eval_jcc,
	},
	[(BPF_JMP | EBPF_JSLE | BPF_K)] = {
		.mask = { .dreg = ALL_REGS, .sreg = ZERO_REG},
		.off = { .min = 0, .max = UINT16_MAX},
		.imm = { .min = 0, .max = UINT32_MAX},
		.eval = eval_jcc,
	},
	[(BPF_JMP | BPF_JSET | BPF_K)] = {
		.mask = { .dreg = ALL_REGS, .sreg = ZERO_REG},
		.off = { .min = 0, .max = UINT16_MAX},
		.imm = { .min = 0, .max = UINT32_MAX},
		.eval = eval_jcc,
	},
	/* jcc REG instructions */
	[(BPF_JMP | BPF_JEQ | BPF_X)] = {
		.mask = { .dreg = ALL_REGS, .sreg = ALL_REGS},
		.off = { .min = 0, .max = UINT16_MAX},
		.imm = { .min = 0, .max = 0},
		.eval = eval_jcc,
	},
	[(BPF_JMP | EBPF_JNE | BPF_X)] = {
		.mask = { .dreg = ALL_REGS, .sreg = ALL_REGS},
		.off = { .min = 0, .max = UINT16_MAX},
		.imm = { .min = 0, .max = 0},
		.eval = eval_jcc,
	},
	[(BPF_JMP | BPF_JGT | BPF_X)] = {
		.mask = { .dreg = ALL_REGS, .sreg = ALL_REGS},
		.off = { .min = 0, .max = UINT16_MAX},
		.imm = { .min = 0, .max = 0},
		.eval = eval_jcc,
	},
	[(BPF_JMP | EBPF_JLT | BPF_X)] = {
		.mask = { .dreg = ALL_REGS, .sreg = ALL_REGS},
		.off = { .min = 0, .max = UINT16_MAX},
		.imm = { .min = 0, .max = 0},
		.eval = eval_jcc,
	},
	[(BPF_JMP | BPF_JGE | BPF_X)] = {
		.mask = { .dreg = ALL_REGS, .sreg = ALL_REGS},
		.off = { .min = 0, .max = UINT16_MAX},
		.imm = { .min = 0, .max = 0},
		.eval = eval_jcc,
	},
	[(BPF_JMP | EBPF_JLE | BPF_X)] = {
		.mask = { .dreg = ALL_REGS, .sreg = ALL_REGS},
		.off = { .min = 0, .max = UINT16_MAX},
		.imm = { .min = 0, .max = 0},
		.eval = eval_jcc,
	},
	[(BPF_JMP | EBPF_JSGT | BPF_X)] = {
		.mask = { .dreg = ALL_REGS, .sreg = ALL_REGS},
		.off = { .min = 0, .max = UINT16_MAX},
		.imm = { .min = 0, .max = 0},
		.eval = eval_jcc,
	},
	[(BPF_JMP | EBPF_JSLT | BPF_X)] = {
		.mask = { .dreg = ALL_REGS, .sreg = ALL_REGS},
		.off = { .min = 0, .max = UINT16_MAX},
		.imm = { .min = 0, .max = 0},
		.eval = eval_jcc,
	},
	[(BPF_JMP | EBPF_JSGE | BPF_X)] = {
		.mask = { .dreg = ALL_REGS, .sreg = ALL_REGS},
		.off = { .min = 0, .max = UINT16_MAX},
		.imm = { .min = 0, .max = 0},
		.eval = eval_jcc,
	},
	[(BPF_JMP | EBPF_JSLE | BPF_X)] = {
		.mask = { .dreg = ALL_REGS, .sreg = ALL_REGS},
		.off = { .min = 0, .max = UINT16_MAX},
		.imm = { .min = 0, .max = 0},
		.eval = eval_jcc,
	},
	[(BPF_JMP | BPF_JSET | BPF_X)] = {
		.mask = { .dreg = ALL_REGS, .sreg = ALL_REGS},
		.off = { .min = 0, .max = UINT16_MAX},
		.imm = { .min = 0, .max = 0},
		.eval = eval_jcc,
	},
	/* call instruction */
	[(BPF_JMP | EBPF_CALL)] = {
		.mask = { .dreg = ZERO_REG, .sreg = ZERO_REG},
		.off = { .min = 0, .max = 0},
		.imm = { .min = 0, .max = UINT32_MAX},
		.eval = eval_call,
	},
	/* ret instruction */
	[(BPF_JMP | EBPF_EXIT)] = {
		.mask = { .dreg = ZERO_REG, .sreg = ZERO_REG},
		.off = { .min = 0, .max = 0},
		.imm = { .min = 0, .max = 0},
		.eval = eval_exit,
	},
};

/*
 * make sure that instruction syntax is valid,
 * and its fields don't violate particular instruction type restrictions.
 */
static const char *
check_syntax(const struct ebpf_insn *ins)
{

	uint8_t op;
	uint16_t off;
	uint32_t imm;

	op = ins->code;

	if (ins_chk[op].mask.dreg == 0)
		return "invalid opcode";

	if ((ins_chk[op].mask.dreg & 1 << ins->dst_reg) == 0)
		return "invalid dst-reg field";

	if ((ins_chk[op].mask.sreg & 1 << ins->src_reg) == 0)
		return "invalid src-reg field";

	off = ins->off;
	if (ins_chk[op].off.min > off || ins_chk[op].off.max < off)
		return "invalid off field";

	imm = ins->imm;
	if (ins_chk[op].imm.min > imm || ins_chk[op].imm.max < imm)
		return "invalid imm field";

	if (ins_chk[op].check != NULL)
		return ins_chk[op].check(ins);

	return NULL;
}

/*
 * helper function, return instruction index for the given node.
 */
static uint32_t
get_node_idx(const struct bpf_verifier *bvf, const struct inst_node *node)
{
	return node - bvf->in;
}

/*
 * helper function, used to walk through constructed CFG.
 */
static struct inst_node *
get_next_node(struct bpf_verifier *bvf, struct inst_node *node)
{
	uint32_t ce, ne, dst;

	ne = node->nb_edge;
	ce = node->cur_edge;
	if (ce == ne)
		return NULL;

	node->cur_edge++;
	dst = node->edge_dest[ce];
	return bvf->in + dst;
}

static void
set_node_colour(struct bpf_verifier *bvf, struct inst_node *node,
	uint32_t new)
{
	uint32_t prev;

	prev = node->colour;
	node->colour = new;

	bvf->node_colour[prev]--;
	bvf->node_colour[new]++;
}

/*
 * helper function, add new edge between two nodes.
 */
static int
add_edge(struct bpf_verifier *bvf, struct inst_node *node, uint32_t nidx)
{
	uint32_t ne;

	if (nidx >= bvf->prm->raw.nb_ins) {
		RTE_BPF_LOG_FUNC_LINE(ERR,
			"program boundary violation at pc: %u, next pc: %u",
			get_node_idx(bvf, node), nidx);
		return -EINVAL;
	}

	ne = node->nb_edge;
	if (ne >= RTE_DIM(node->edge_dest)) {
		RTE_BPF_LOG_FUNC_LINE(ERR, "internal error at pc: %u",
			get_node_idx(bvf, node));
		return -EINVAL;
	}

	node->edge_dest[ne] = nidx;
	node->nb_edge = ne + 1;
	return 0;
}

/*
 * helper function, determine type of edge between two nodes.
 */
static void
set_edge_type(struct bpf_verifier *bvf, struct inst_node *node,
	const struct inst_node *next)
{
	uint32_t ce, clr, type;

	ce = node->cur_edge - 1;
	clr = next->colour;

	type = UNKNOWN_EDGE;

	if (clr == WHITE)
		type = TREE_EDGE;
	else if (clr == GREY)
		type = BACK_EDGE;
	else if (clr == BLACK)
		/*
		 * in fact it could be either direct or cross edge,
		 * but for now, we don't need to distinguish between them.
		 */
		type = CROSS_EDGE;

	node->edge_type[ce] = type;
	bvf->edge_type[type]++;
}

/*
 * Depth-First Search (DFS) through previously constructed
 * Control Flow Graph (CFG).
 * Information collected at this path would be used later
 * to determine is there any loops, and/or statically unreachable instructions.
 * PREREQUISITE: there is at least one node.
 */
static void
dfs(struct bpf_verifier *bvf)
{
	struct inst_node *next, *node;

	RTE_ASSERT(bvf->nb_nodes != 0);
	/*
	 * Since there is at least one node, node with index 0 always exists;
	 * it is our program entry point.
	 */
	node = &bvf->in[0];
	do {

		if (node->colour == WHITE)
			set_node_colour(bvf, node, GREY);

		if (node->colour == GREY) {

			/* find next unprocessed child node */
			do {
				next = get_next_node(bvf, node);
				if (next == NULL)
					break;
				set_edge_type(bvf, node, next);
			} while (next->colour != WHITE);

			if (next != NULL) {
				/* proceed with next child */
				next->prev_node = node;
				node = next;
			} else {
				/*
				 * finished with current node and all it's kids,
				 * proceed with parent
				 */
				set_node_colour(bvf, node, BLACK);
				node->cur_edge = 0;
				node = node->prev_node;
			}
		} else
			node = NULL;
	} while (node != NULL);
}

/*
 * report statically unreachable instructions.
 */
static void
log_unreachable(const struct bpf_verifier *bvf)
{
	uint32_t i;
	struct inst_node *node;
	const struct ebpf_insn *ins;

	for (i = 0; i != bvf->prm->raw.nb_ins; i++) {

		node = bvf->in + i;
		ins = bvf->prm->raw.ins + i;

		if (node->colour == WHITE &&
				ins->code != (BPF_LD | BPF_IMM | EBPF_DW))
			RTE_BPF_LOG_LINE(ERR, "unreachable code at pc: %u;", i);
	}
}

/*
 * report loops detected.
 */
static void
log_loop(const struct bpf_verifier *bvf)
{
	uint32_t i, j;
	struct inst_node *node;

	for (i = 0; i != bvf->prm->raw.nb_ins; i++) {

		node = bvf->in + i;
		if (node->colour != BLACK)
			continue;

		for (j = 0; j != node->nb_edge; j++) {
			if (node->edge_type[j] == BACK_EDGE)
				RTE_BPF_LOG_LINE(ERR,
					"loop at pc:%u --> pc:%u;",
					i, node->edge_dest[j]);
		}
	}
}

/*
 * First pass goes though all instructions in the set, checks that each
 * instruction is a valid one (correct syntax, valid field values, etc.)
 * and constructs control flow graph (CFG).
 * Then depth-first search is performed over the constructed graph.
 * Programs with unreachable instructions and/or loops will be rejected.
 */
static int
validate(struct bpf_verifier *bvf)
{
	int32_t rc;
	uint32_t i;
	struct inst_node *node;
	const struct ebpf_insn *ins;
	const char *err;

	rc = 0;
	for (i = 0; i < bvf->prm->raw.nb_ins; i++) {

		ins = bvf->prm->raw.ins + i;
		node = bvf->in + i;

		err = check_syntax(ins);
		if (err != 0) {
			RTE_BPF_LOG_FUNC_LINE(ERR, "%s at pc: %u", err, i);
			rc |= -EINVAL;
		}

		/*
		 * construct CFG, jcc nodes have to outgoing edges,
		 * 'exit' nodes - none, all other nodes have exactly one
		 * outgoing edge.
		 */
		switch (ins->code) {
		case (BPF_JMP | EBPF_EXIT):
			break;
		case (BPF_JMP | BPF_JEQ | BPF_K):
		case (BPF_JMP | EBPF_JNE | BPF_K):
		case (BPF_JMP | BPF_JGT | BPF_K):
		case (BPF_JMP | EBPF_JLT | BPF_K):
		case (BPF_JMP | BPF_JGE | BPF_K):
		case (BPF_JMP | EBPF_JLE | BPF_K):
		case (BPF_JMP | EBPF_JSGT | BPF_K):
		case (BPF_JMP | EBPF_JSLT | BPF_K):
		case (BPF_JMP | EBPF_JSGE | BPF_K):
		case (BPF_JMP | EBPF_JSLE | BPF_K):
		case (BPF_JMP | BPF_JSET | BPF_K):
		case (BPF_JMP | BPF_JEQ | BPF_X):
		case (BPF_JMP | EBPF_JNE | BPF_X):
		case (BPF_JMP | BPF_JGT | BPF_X):
		case (BPF_JMP | EBPF_JLT | BPF_X):
		case (BPF_JMP | BPF_JGE | BPF_X):
		case (BPF_JMP | EBPF_JLE | BPF_X):
		case (BPF_JMP | EBPF_JSGT | BPF_X):
		case (BPF_JMP | EBPF_JSLT | BPF_X):
		case (BPF_JMP | EBPF_JSGE | BPF_X):
		case (BPF_JMP | EBPF_JSLE | BPF_X):
		case (BPF_JMP | BPF_JSET | BPF_X):
			rc |= add_edge(bvf, node, i + ins->off + 1);
			rc |= add_edge(bvf, node, i + 1);
			bvf->nb_jcc_nodes++;
			break;
		case (BPF_JMP | BPF_JA):
			rc |= add_edge(bvf, node, i + ins->off + 1);
			break;
		/* load 64 bit immediate value */
		case (BPF_LD | BPF_IMM | EBPF_DW):
			rc |= add_edge(bvf, node, i + 2);
			i++;
			break;
		case (BPF_LD | BPF_ABS | BPF_B):
		case (BPF_LD | BPF_ABS | BPF_H):
		case (BPF_LD | BPF_ABS | BPF_W):
		case (BPF_LD | BPF_IND | BPF_B):
		case (BPF_LD | BPF_IND | BPF_H):
		case (BPF_LD | BPF_IND | BPF_W):
			bvf->nb_ldmb_nodes++;
			/* fallthrough */
		default:
			rc |= add_edge(bvf, node, i + 1);
			break;
		}

		bvf->nb_nodes++;
		bvf->node_colour[WHITE]++;
	}

	if (rc != 0)
		return rc;

	if (bvf->nb_nodes == 0) {
		RTE_BPF_LOG_LINE(ERR, "%s(%p) the program is empty",
			__func__, bvf);
		return -EINVAL;
	}

	dfs(bvf);

	RTE_LOG(DEBUG, BPF, "%s(%p) stats:\n"
		"nb_nodes=%u;\n"
		"nb_jcc_nodes=%u;\n"
		"node_color={[WHITE]=%u, [GREY]=%u,, [BLACK]=%u};\n"
		"edge_type={[UNKNOWN]=%u, [TREE]=%u, [BACK]=%u, [CROSS]=%u};\n",
		__func__, bvf,
		bvf->nb_nodes,
		bvf->nb_jcc_nodes,
		bvf->node_colour[WHITE], bvf->node_colour[GREY],
			bvf->node_colour[BLACK],
		bvf->edge_type[UNKNOWN_EDGE], bvf->edge_type[TREE_EDGE],
		bvf->edge_type[BACK_EDGE], bvf->edge_type[CROSS_EDGE]);

	if (bvf->node_colour[BLACK] != bvf->nb_nodes) {
		RTE_BPF_LOG_LINE(ERR, "%s(%p) unreachable instructions;",
			__func__, bvf);
		log_unreachable(bvf);
		return -EINVAL;
	}

	if (bvf->node_colour[GREY] != 0 || bvf->node_colour[WHITE] != 0 ||
			bvf->edge_type[UNKNOWN_EDGE] != 0) {
		RTE_BPF_LOG_LINE(ERR, "%s(%p) DFS internal error;",
			__func__, bvf);
		return -EINVAL;
	}

	if (bvf->edge_type[BACK_EDGE] != 0) {
		RTE_BPF_LOG_LINE(ERR, "%s(%p) loops detected;",
			__func__, bvf);
		log_loop(bvf);
		return -EINVAL;
	}

	return 0;
}

/*
 * helper functions get/free eval states.
 */
static struct bpf_eval_state *
pull_eval_state(struct evst_pool *pool)
{
	uint32_t n;

	n = pool->cur;
	if (n == pool->num)
		return NULL;

	pool->cur = n + 1;
	return pool->ent + n;
}

static void
push_eval_state(struct evst_pool *pool)
{
	RTE_ASSERT(pool->cur != 0);
	pool->cur--;
}

static void
evst_pool_fini(struct bpf_verifier *bvf)
{
	bvf->evst = NULL;
	free(bvf->evst_sr_pool.ent);
	memset(&bvf->evst_sr_pool, 0, sizeof(bvf->evst_sr_pool));
	memset(&bvf->evst_tp_pool, 0, sizeof(bvf->evst_tp_pool));
}

static int
evst_pool_init(struct bpf_verifier *bvf)
{
	uint32_t k, n;

	if (bvf->nb_jcc_nodes > UINT32_MAX / 4)
		/* Calculations that follow may overflow. */
		return -E2BIG;

	/*
	 * We need nb_jcc_nodes + 1 for save_cur/restore_cur
	 * remaining ones will be used for state tracking/pruning.
	 */
	k = bvf->nb_jcc_nodes + 1;
	n = k * 3;

	bvf->evst_sr_pool.ent = calloc(n, sizeof(bvf->evst_sr_pool.ent[0]));
	if (bvf->evst_sr_pool.ent == NULL)
		return -ENOMEM;

	bvf->evst_sr_pool.num = k;
	bvf->evst_sr_pool.cur = 0;

	bvf->evst_tp_pool.ent = bvf->evst_sr_pool.ent + k;
	bvf->evst_tp_pool.num = n - k;
	bvf->evst_tp_pool.cur = 0;

	bvf->evst = pull_eval_state(&bvf->evst_sr_pool);
	return 0;
}

/*
 * try to allocate and initialise new eval state for given node.
 * later if no errors will be encountered, this state will be accepted as
 * one of the possible 'safe' states for that node.
 */
static void
save_start_eval_state(struct bpf_verifier *bvf, struct inst_node *node)
{
	RTE_ASSERT(node->evst.start == NULL);

	/* limit number of states for one node with some reasonable value */
	if (node->evst.nb_safe >= NODE_EVST_MAX)
		return;

	/* try to get new eval_state */
	node->evst.start = pull_eval_state(&bvf->evst_tp_pool);

	/* make a copy of current state */
	if (node->evst.start != NULL) {
		memcpy(node->evst.start, bvf->evst, sizeof(*node->evst.start));
		SLIST_NEXT(node->evst.start, next) = NULL;
	}
}

/*
 * add @start state to the list of @safe states.
 */
static void
save_safe_eval_state(struct bpf_verifier *bvf, struct inst_node *node)
{
	if (node->evst.start == NULL)
		return;

	SLIST_INSERT_HEAD(&node->evst.safe, node->evst.start, next);
	node->evst.nb_safe++;

	RTE_BPF_LOG_LINE(DEBUG, "%s(bvf=%p,node=%u,state=%p): nb_safe=%u;",
		__func__, bvf, get_node_idx(bvf, node), node->evst.start,
		node->evst.nb_safe);

	node->evst.start = NULL;
}

/*
 * Save current eval state.
 */
static int
save_cur_eval_state(struct bpf_verifier *bvf, struct inst_node *node)
{
	struct bpf_eval_state *st;

	/* get new eval_state for this node */
	st = pull_eval_state(&bvf->evst_sr_pool);
	if (st == NULL) {
		RTE_BPF_LOG_FUNC_LINE(ERR,
			"internal error (out of space) at pc: %u",
			get_node_idx(bvf, node));
		return -ENOMEM;
	}

	/* make a copy of current state */
	memcpy(st, bvf->evst, sizeof(*st));

	/* swap current state with new one */
	RTE_ASSERT(node->evst.cur == NULL);
	node->evst.cur = bvf->evst;
	bvf->evst = st;

	RTE_BPF_LOG_LINE(DEBUG, "%s(bvf=%p,node=%u) old/new states: %p/%p;",
		__func__, bvf, get_node_idx(bvf, node), node->evst.cur,
		bvf->evst);

	return 0;
}

/*
 * Restore previous eval state and mark current eval state as free.
 */
static void
restore_cur_eval_state(struct bpf_verifier *bvf, struct inst_node *node)
{
	RTE_BPF_LOG_LINE(DEBUG, "%s(bvf=%p,node=%u) old/new states: %p/%p;",
		__func__, bvf, get_node_idx(bvf, node), bvf->evst,
		node->evst.cur);

	bvf->evst = node->evst.cur;
	node->evst.cur = NULL;
	push_eval_state(&bvf->evst_sr_pool);
}

static void
log_dbg_eval_state(const struct bpf_verifier *bvf, const struct ebpf_insn *ins,
	uint32_t pc)
{
	const struct bpf_eval_state *st;
	const struct bpf_reg_val *rv;

	RTE_BPF_LOG_LINE(DEBUG, "%s(pc=%u):", __func__, pc);

	st = bvf->evst;
	rv = st->rv + ins->dst_reg;

	RTE_LOG(DEBUG, BPF,
		"r%u={\n"
		"\tv={type=%u, size=%zu, buf_size=%zu},\n"
		"\tmask=0x%" PRIx64 ",\n"
		"\tu={min=0x%" PRIx64 ", max=0x%" PRIx64 "},\n"
		"\ts={min=%" PRId64 ", max=%" PRId64 "},\n"
		"};\n",
		ins->dst_reg,
		rv->v.type, rv->v.size, rv->v.buf_size,
		rv->mask,
		rv->u.min, rv->u.max,
		rv->s.min, rv->s.max);
}

/*
 * compare two evaluation states.
 * returns zero if @lv is more conservative (safer) then @rv.
 * returns non-zero value otherwise.
 */
static int
cmp_reg_val_within(const struct bpf_reg_val *lv, const struct bpf_reg_val *rv)
{
	/* expect @v and @mask to be identical */
	if (memcmp(&lv->v, &rv->v, sizeof(lv->v)) != 0 || lv->mask != rv->mask)
		return -1;

	/* exact match only for mbuf and stack pointers */
	if (lv->v.type == RTE_BPF_ARG_PTR_MBUF ||
			lv->v.type == BPF_ARG_PTR_STACK)
		return -1;

	if (lv->u.min <= rv->u.min && lv->u.max >= rv->u.max &&
			lv->s.min <= rv->s.min && lv->s.max >= rv->s.max)
		return 0;

	return -1;
}

/*
 * compare two evaluation states.
 * returns zero if they are identical.
 * returns positive value if @lv is more conservative (safer) then @rv.
 * returns negative value otherwise.
 */
static int
cmp_eval_state(const struct bpf_eval_state *lv, const struct bpf_eval_state *rv)
{
	int32_t rc;
	uint32_t i, k;

	/* for stack expect identical values */
	rc = memcmp(lv->sv, rv->sv, sizeof(lv->sv));
	if (rc != 0)
		return -(2 * EBPF_REG_NUM);

	k = 0;
	/* check register values */
	for (i = 0; i != RTE_DIM(lv->rv); i++) {
		rc = memcmp(&lv->rv[i], &rv->rv[i], sizeof(lv->rv[i]));
		if (rc != 0 && cmp_reg_val_within(&lv->rv[i], &rv->rv[i]) != 0)
			return -(i + 1);
		k += (rc != 0);
	}

	return k;
}

/*
 * check did we already evaluated that path and can it be pruned that time.
 */
static int
prune_eval_state(struct bpf_verifier *bvf, const struct inst_node *node,
	struct inst_node *next)
{
	int32_t rc;
	struct bpf_eval_state *safe;

	rc = INT32_MIN;
	SLIST_FOREACH(safe, &next->evst.safe, next) {
		rc = cmp_eval_state(safe, bvf->evst);
		if (rc >= 0)
			break;
	}

	rc = (rc >= 0) ? 0 : -1;

	/*
	 * current state doesn't match any safe states,
	 * so no prunning is possible right now,
	 * track current state for future references.
	 */
	if (rc != 0)
		save_start_eval_state(bvf, next);

	RTE_BPF_LOG_LINE(DEBUG, "%s(bvf=%p,node=%u,next=%u) returns %d, "
		"next->evst.start=%p, next->evst.nb_safe=%u",
		__func__, bvf, get_node_idx(bvf, node),
		get_node_idx(bvf, next), rc,
		next->evst.start, next->evst.nb_safe);
	return rc;
}

/* Do second pass through CFG and try to evaluate instructions
 * via each possible path. The verifier will try all paths, tracking types of
 * registers used as input to instructions, and updating resulting type via
 * register state values. Plus for each register and possible stack value it
 * tries to estimate possible max/min value.
 * For conditional jumps, a stack is used to save evaluation state, so one
 * path is explored while the state for the other path is pushed onto the stack.
 * Then later, we backtrack to the first pushed instruction and repeat the cycle
 * until the stack is empty and we're done.
 * For program with many conditional branches walking through all possible path
 * could be very excessive. So to minimize number of evaluations we use
 * heuristic similar to what Linux kernel does - state pruning:
 * If from given instruction for given program state we explore all possible
 * paths and for each of them reach _exit() without any complaints and a valid
 * R0 value, then for that instruction, that program state can be marked as
 * 'safe'. When we later arrive at the same instruction with a state
 * equivalent to an earlier instruction's 'safe' state, we can prune the search.
 * For now, only states for JCC  targets are saved/examined.
 */
static int
evaluate(struct bpf_verifier *bvf)
{
	uint32_t idx, op;
	const char *err;
	const struct ebpf_insn *ins;
	struct inst_node *next, *node;
	int prev_nb_edge;  /* branching number of the previous instruction */
	int rc, debug_rc;
	struct rte_bpf_validate_debug *const debug = bvf->prm->debug;

	struct {
		uint32_t nb_eval;
		uint32_t nb_prune;
		uint32_t nb_save;
		uint32_t nb_restore;
	} stats;

	/* initial state of frame pointer */
	static const struct bpf_reg_val rvfp = {
		.v = {
			.type = BPF_ARG_PTR_STACK,
			.size = MAX_BPF_STACK_SIZE,
		},
		.mask = UINT64_MAX,
		.u = {.min = MAX_BPF_STACK_SIZE, .max = MAX_BPF_STACK_SIZE},
		.s = {.min = MAX_BPF_STACK_SIZE, .max = MAX_BPF_STACK_SIZE},
	};

	for (uint32_t pai = 0; pai != bvf->prm->nb_prog_arg; ++pai) {
		struct bpf_reg_val *reg = &bvf->evst->rv[EBPF_REG_1 + pai];

		reg->v = bvf->prm->prog_arg[pai];
		reg->mask = UINT64_MAX;
		if (reg->v.type == RTE_BPF_ARG_RAW)
			eval_max_bound(reg, UINT64_MAX);
	}

	bvf->evst->rv[EBPF_REG_10] = rvfp;

	ins = bvf->prm->raw.ins;
	node = bvf->in;
	next = node;
	prev_nb_edge = 1;

	memset(&stats, 0, sizeof(stats));

	rc = __rte_bpf_validate_debug_evaluate_start(debug, bvf, bvf->prm);
	if (rc < 0)
		return rc;

	while (node != NULL) {
		/*
		 * current node evaluation, make sure we evaluate
		 * each node only once.
		 */
		if (next != NULL) {
			/* just started or stepped down the tree, node == next */

			bvf->evin = node;
			idx = get_node_idx(bvf, node);
			op = ins[idx].code;

			/* for jcc node make a copy of evaluation state */
			if (node->nb_edge > 1) {
				rc = save_cur_eval_state(bvf, node);
				if (rc < 0)
					break;
				stats.nb_save++;
			}

			if (ins_chk[op].eval == NULL) {
				RTE_BPF_LOG_FUNC_LINE(ERR,
					"Unrecognized instruction at pc: %u", idx);
				rc = -EINVAL;
				break;
			}

			rc = __rte_bpf_validate_debug_evaluate_step(debug, idx,
				prev_nb_edge > 1 ?
					RTE_BPF_VALIDATE_DEBUG_EVENT_BRANCH_ENTER :
					RTE_BPF_VALIDATE_DEBUG_EVENT_STEP);
			if (rc < 0)
				break;

			err = ins_chk[op].eval(bvf, ins + idx);
			stats.nb_eval++;
			if (err != NULL) {
				RTE_BPF_LOG_FUNC_LINE(ERR,
					"%s at pc: %u", err, idx);
				rc = -EINVAL;
				break;
			}

			log_dbg_eval_state(bvf, ins + idx, idx);
			bvf->evin = NULL;
		}

		/* proceed through CFG */
		next = get_next_node(bvf, node);

		if (next != NULL) {
			/*
			 * proceed with next child
			 * next points to an unwalked subtree of node
			 */
			if (node->cur_edge == node->nb_edge &&
					node->evst.cur != NULL) {
				restore_cur_eval_state(bvf, node);
				stats.nb_restore++;
			}

			if (bvf->evst->unreachable) {
				rc = __rte_bpf_validate_debug_evaluate_step(
					debug, get_node_idx(bvf, next),
					RTE_BPF_VALIDATE_DEBUG_EVENT_BRANCH_UNREACHABLE);
				if (rc < 0)
					break;

				next = NULL;
			/*
			 * for jcc targets: check did we already evaluated
			 * that path and can it's evaluation be skipped that
			 * time.
			 */
			} else if (node->nb_edge > 1 &&
					prune_eval_state(bvf, node, next) == 0) {
				rc = __rte_bpf_validate_debug_evaluate_step(
					debug, get_node_idx(bvf, next),
					RTE_BPF_VALIDATE_DEBUG_EVENT_BRANCH_PRUNE);
				if (rc < 0)
					break;

				next = NULL;
				stats.nb_prune++;
			} else {
				next->prev_node = node;
				prev_nb_edge = node->nb_edge;
				node = next;
			}
		} else {
			/*
			 * finished with current node and all it's kids,
			 * mark it's @start state as safe for future references,
			 * and proceed with parent.
			 */

			if (prev_nb_edge != 0) {
				rc = __rte_bpf_validate_debug_evaluate_step(
					debug, get_node_idx(bvf, node) + 1,
					RTE_BPF_VALIDATE_DEBUG_EVENT_BRANCH_RETURN);
				if (rc < 0)
					break;
			}

			node->cur_edge = 0;
			save_safe_eval_state(bvf, node);
			prev_nb_edge = 0;
			node = node->prev_node;

			/* first node will not have prev, signalling finish */
		}

		/*
		 * next != NULL: stepped down the tree, node == next;
		 * next == NULL: stepped up after processing or pruning subtree;
		 */
	}

	RTE_LOG(DEBUG, BPF, "%s(%p) returns %d, stats:\n"
		"node evaluations=%u;\n"
		"state pruned=%u;\n"
		"state saves=%u;\n"
		"state restores=%u;\n",
		__func__, bvf, rc,
		stats.nb_eval, stats.nb_prune, stats.nb_save, stats.nb_restore);

	debug_rc = __rte_bpf_validate_debug_evaluate_finish(debug, rc);
	rc = debug_rc < 0 ? debug_rc : rc;

	/* Caller does not expect positive values. */
	return RTE_MIN(0, rc);
}

static bool
prog_arg_is_valid(const struct rte_bpf_arg *prog_arg)
{
	/* check input argument type, don't allow mbuf ptr on 32-bit */
	if (prog_arg->type != RTE_BPF_ARG_RAW &&
			prog_arg->type != RTE_BPF_ARG_PTR &&
			(sizeof(uint64_t) != sizeof(uintptr_t) ||
			prog_arg->type != RTE_BPF_ARG_PTR_MBUF)) {
		RTE_BPF_LOG_FUNC_LINE(ERR, "unsupported argument type");
		return false;
	}

	return true;
}

int
__rte_bpf_validate(const struct rte_bpf_prm_ex *prm, uint32_t *stack_sz)
{
	int32_t rc;
	struct bpf_verifier bvf;

	if (prm->nb_prog_arg > EBPF_FUNC_MAX_ARGS) {
		RTE_BPF_LOG_FUNC_LINE(ERR,
			"support up to %u arguments, found %u",
			EBPF_FUNC_MAX_ARGS, prm->nb_prog_arg);
		return -ENOTSUP;
	}

	for (uint32_t pai = 0; pai != prm->nb_prog_arg; ++pai)
		if (!prog_arg_is_valid(&prm->prog_arg[pai])) {
			RTE_BPF_LOG_FUNC_LINE(ERR,
				"unsupported argument %d (r%d) type",
				pai, EBPF_REG_1 + pai);
			return -ENOTSUP;
		}

	memset(&bvf, 0, sizeof(bvf));
	bvf.prm = prm;
	bvf.in = calloc(prm->raw.nb_ins, sizeof(bvf.in[0]));
	if (bvf.in == NULL)
		return -ENOMEM;

	rc = validate(&bvf);

	if (rc == 0) {
		rc = evst_pool_init(&bvf);
		if (rc == 0)
			rc = evaluate(&bvf);
		evst_pool_fini(&bvf);
	}

	free(bvf.in);

	/* copy collected info */
	if (rc == 0) {
		*stack_sz = bvf.stack_sz;

		/* for LD_ABS/LD_IND, we'll need extra space on the stack */
		if (bvf.nb_ldmb_nodes != 0)
			*stack_sz = RTE_ALIGN_CEIL(*stack_sz +
				sizeof(uint64_t), sizeof(uint64_t));
	}

	return rc;
}