From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mga12.intel.com (mga12.intel.com [192.55.52.136]) by dpdk.org (Postfix) with ESMTP id 8F58A1BA51 for ; Thu, 10 May 2018 12:23:27 +0200 (CEST) X-Amp-Result: SKIPPED(no attachment in message) X-Amp-File-Uploaded: False Received: from fmsmga007.fm.intel.com ([10.253.24.52]) by fmsmga106.fm.intel.com with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384; 10 May 2018 03:23:26 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.49,385,1520924400"; d="scan'208";a="38242525" Received: from sivswdev02.ir.intel.com (HELO localhost.localdomain) ([10.237.217.46]) by fmsmga007.fm.intel.com with ESMTP; 10 May 2018 03:23:25 -0700 From: Konstantin Ananyev To: dev@dpdk.org Cc: Konstantin Ananyev Date: Thu, 10 May 2018 11:23:05 +0100 Message-Id: <1525947791-24031-4-git-send-email-konstantin.ananyev@intel.com> X-Mailer: git-send-email 1.7.0.7 In-Reply-To: <1525437945-8207-2-git-send-email-konstantin.ananyev@intel.com> References: <1525437945-8207-2-git-send-email-konstantin.ananyev@intel.com> Subject: [dpdk-dev] [PATCH v6 3/9] bpf: add more logic into bpf_validate() X-BeenThere: dev@dpdk.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: DPDK patches and discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 10 May 2018 10:23:28 -0000 Add checks for: - all instructions are valid ones (known opcodes, correct syntax, valid reg/off/imm values, etc.) - no unreachable instructions - no loops - basic stack boundaries checks - division by zero Still need to add checks for: - use/return only initialized registers and stack data. - memory boundaries violation Signed-off-by: Konstantin Ananyev Acked-by: Ferruh Yigit --- lib/librte_bpf/bpf_validate.c | 1181 ++++++++++++++++++++++++++++++++++++++++- 1 file changed, 1155 insertions(+), 26 deletions(-) diff --git a/lib/librte_bpf/bpf_validate.c b/lib/librte_bpf/bpf_validate.c index 6a1b33181..b7081c853 100644 --- a/lib/librte_bpf/bpf_validate.c +++ b/lib/librte_bpf/bpf_validate.c @@ -14,42 +14,1171 @@ #include "bpf_impl.h" +/* 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 +}; + +struct bpf_reg_state { + uint64_t val; +}; + +struct bpf_eval_state { + struct bpf_reg_state rs[EBPF_REG_NUM]; +}; + +#define MAX_EDGES 2 + +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]; + uint32_t prev_node; + struct bpf_eval_state *evst; +}; + +struct bpf_verifier { + const struct rte_bpf_prm *prm; + struct inst_node *in; + int32_t stack_sz; + uint32_t nb_nodes; + uint32_t nb_jcc_nodes; + uint32_t node_colour[MAX_NODE_COLOUR]; + uint32_t edge_type[MAX_EDGE_TYPE]; + struct bpf_eval_state *evst; + struct { + uint32_t num; + uint32_t cur; + struct bpf_eval_state *ent; + } evst_pool; +}; + +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) + /* - * dummy one for now, need more work. + * check and evaluate functions for particular instruction types. */ -int -bpf_validate(struct rte_bpf *bpf) + +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_stack(struct bpf_verifier *bvf, const struct ebpf_insn *ins) +{ + int32_t ofs; + + ofs = ins->off; + + if (ofs >= 0 || ofs < -MAX_BPF_STACK_SIZE) + return "stack boundary violation"; + + ofs = -ofs; + bvf->stack_sz = RTE_MAX(bvf->stack_sz, ofs); + return NULL; +} + +static const char * +eval_store(struct bpf_verifier *bvf, const struct ebpf_insn *ins) +{ + if (ins->dst_reg == EBPF_REG_10) + return eval_stack(bvf, ins); + return NULL; +} + +static const char * +eval_load(struct bpf_verifier *bvf, const struct ebpf_insn *ins) +{ + if (ins->src_reg == EBPF_REG_10) + return eval_stack(bvf, ins); + return NULL; +} + +static const char * +eval_call(struct bpf_verifier *bvf, const struct ebpf_insn *ins) +{ + uint32_t idx; + + 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"; + return NULL; +} + +/* + * validate parameters for each instruction type. + */ +static const struct bpf_ins_check ins_chk[UINT8_MAX] = { + /* 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,}, + }, + [(BPF_ALU | BPF_SUB | BPF_K)] = { + .mask = {.dreg = WRT_REGS, .sreg = ZERO_REG}, + .off = { .min = 0, .max = 0}, + .imm = { .min = 0, .max = UINT32_MAX,}, + }, + [(BPF_ALU | BPF_AND | BPF_K)] = { + .mask = {.dreg = WRT_REGS, .sreg = ZERO_REG}, + .off = { .min = 0, .max = 0}, + .imm = { .min = 0, .max = UINT32_MAX,}, + }, + [(BPF_ALU | BPF_OR | BPF_K)] = { + .mask = {.dreg = WRT_REGS, .sreg = ZERO_REG}, + .off = { .min = 0, .max = 0}, + .imm = { .min = 0, .max = UINT32_MAX,}, + }, + [(BPF_ALU | BPF_LSH | BPF_K)] = { + .mask = {.dreg = WRT_REGS, .sreg = ZERO_REG}, + .off = { .min = 0, .max = 0}, + .imm = { .min = 0, .max = UINT32_MAX,}, + }, + [(BPF_ALU | BPF_RSH | BPF_K)] = { + .mask = {.dreg = WRT_REGS, .sreg = ZERO_REG}, + .off = { .min = 0, .max = 0}, + .imm = { .min = 0, .max = UINT32_MAX,}, + }, + [(BPF_ALU | BPF_XOR | BPF_K)] = { + .mask = {.dreg = WRT_REGS, .sreg = ZERO_REG}, + .off = { .min = 0, .max = 0}, + .imm = { .min = 0, .max = UINT32_MAX,}, + }, + [(BPF_ALU | BPF_MUL | BPF_K)] = { + .mask = {.dreg = WRT_REGS, .sreg = ZERO_REG}, + .off = { .min = 0, .max = 0}, + .imm = { .min = 0, .max = UINT32_MAX,}, + }, + [(BPF_ALU | EBPF_MOV | BPF_K)] = { + .mask = {.dreg = WRT_REGS, .sreg = ZERO_REG}, + .off = { .min = 0, .max = 0}, + .imm = { .min = 0, .max = UINT32_MAX,}, + }, + [(BPF_ALU | BPF_DIV | BPF_K)] = { + .mask = { .dreg = WRT_REGS, .sreg = ZERO_REG}, + .off = { .min = 0, .max = 0}, + .imm = { .min = 1, .max = UINT32_MAX}, + }, + [(BPF_ALU | BPF_MOD | BPF_K)] = { + .mask = { .dreg = WRT_REGS, .sreg = ZERO_REG}, + .off = { .min = 0, .max = 0}, + .imm = { .min = 1, .max = UINT32_MAX}, + }, + /* 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,}, + }, + [(EBPF_ALU64 | BPF_SUB | BPF_K)] = { + .mask = {.dreg = WRT_REGS, .sreg = ZERO_REG}, + .off = { .min = 0, .max = 0}, + .imm = { .min = 0, .max = UINT32_MAX,}, + }, + [(EBPF_ALU64 | BPF_AND | BPF_K)] = { + .mask = {.dreg = WRT_REGS, .sreg = ZERO_REG}, + .off = { .min = 0, .max = 0}, + .imm = { .min = 0, .max = UINT32_MAX,}, + }, + [(EBPF_ALU64 | BPF_OR | BPF_K)] = { + .mask = {.dreg = WRT_REGS, .sreg = ZERO_REG}, + .off = { .min = 0, .max = 0}, + .imm = { .min = 0, .max = UINT32_MAX,}, + }, + [(EBPF_ALU64 | BPF_LSH | BPF_K)] = { + .mask = {.dreg = WRT_REGS, .sreg = ZERO_REG}, + .off = { .min = 0, .max = 0}, + .imm = { .min = 0, .max = UINT32_MAX,}, + }, + [(EBPF_ALU64 | BPF_RSH | BPF_K)] = { + .mask = {.dreg = WRT_REGS, .sreg = ZERO_REG}, + .off = { .min = 0, .max = 0}, + .imm = { .min = 0, .max = UINT32_MAX,}, + }, + [(EBPF_ALU64 | EBPF_ARSH | BPF_K)] = { + .mask = {.dreg = WRT_REGS, .sreg = ZERO_REG}, + .off = { .min = 0, .max = 0}, + .imm = { .min = 0, .max = UINT32_MAX,}, + }, + [(EBPF_ALU64 | BPF_XOR | BPF_K)] = { + .mask = {.dreg = WRT_REGS, .sreg = ZERO_REG}, + .off = { .min = 0, .max = 0}, + .imm = { .min = 0, .max = UINT32_MAX,}, + }, + [(EBPF_ALU64 | BPF_MUL | BPF_K)] = { + .mask = {.dreg = WRT_REGS, .sreg = ZERO_REG}, + .off = { .min = 0, .max = 0}, + .imm = { .min = 0, .max = UINT32_MAX,}, + }, + [(EBPF_ALU64 | EBPF_MOV | BPF_K)] = { + .mask = {.dreg = WRT_REGS, .sreg = ZERO_REG}, + .off = { .min = 0, .max = 0}, + .imm = { .min = 0, .max = UINT32_MAX,}, + }, + [(EBPF_ALU64 | BPF_DIV | BPF_K)] = { + .mask = { .dreg = WRT_REGS, .sreg = ZERO_REG}, + .off = { .min = 0, .max = 0}, + .imm = { .min = 1, .max = UINT32_MAX}, + }, + [(EBPF_ALU64 | BPF_MOD | BPF_K)] = { + .mask = { .dreg = WRT_REGS, .sreg = ZERO_REG}, + .off = { .min = 0, .max = 0}, + .imm = { .min = 1, .max = UINT32_MAX}, + }, + /* 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}, + }, + [(BPF_ALU | BPF_SUB | BPF_X)] = { + .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS}, + .off = { .min = 0, .max = 0}, + .imm = { .min = 0, .max = 0}, + }, + [(BPF_ALU | BPF_AND | BPF_X)] = { + .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS}, + .off = { .min = 0, .max = 0}, + .imm = { .min = 0, .max = 0}, + }, + [(BPF_ALU | BPF_OR | BPF_X)] = { + .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS}, + .off = { .min = 0, .max = 0}, + .imm = { .min = 0, .max = 0}, + }, + [(BPF_ALU | BPF_LSH | BPF_X)] = { + .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS}, + .off = { .min = 0, .max = 0}, + .imm = { .min = 0, .max = 0}, + }, + [(BPF_ALU | BPF_RSH | BPF_X)] = { + .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS}, + .off = { .min = 0, .max = 0}, + .imm = { .min = 0, .max = 0}, + }, + [(BPF_ALU | BPF_XOR | BPF_X)] = { + .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS}, + .off = { .min = 0, .max = 0}, + .imm = { .min = 0, .max = 0}, + }, + [(BPF_ALU | BPF_MUL | BPF_X)] = { + .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS}, + .off = { .min = 0, .max = 0}, + .imm = { .min = 0, .max = 0}, + }, + [(BPF_ALU | BPF_DIV | BPF_X)] = { + .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS}, + .off = { .min = 0, .max = 0}, + .imm = { .min = 0, .max = 0}, + }, + [(BPF_ALU | BPF_MOD | BPF_X)] = { + .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS}, + .off = { .min = 0, .max = 0}, + .imm = { .min = 0, .max = 0}, + }, + [(BPF_ALU | EBPF_MOV | BPF_X)] = { + .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS}, + .off = { .min = 0, .max = 0}, + .imm = { .min = 0, .max = 0}, + }, + [(BPF_ALU | BPF_NEG)] = { + .mask = { .dreg = WRT_REGS, .sreg = ZERO_REG}, + .off = { .min = 0, .max = 0}, + .imm = { .min = 0, .max = 0}, + }, + [(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, + }, + [(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, + }, + /* 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}, + }, + [(EBPF_ALU64 | BPF_SUB | BPF_X)] = { + .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS}, + .off = { .min = 0, .max = 0}, + .imm = { .min = 0, .max = 0}, + }, + [(EBPF_ALU64 | BPF_AND | BPF_X)] = { + .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS}, + .off = { .min = 0, .max = 0}, + .imm = { .min = 0, .max = 0}, + }, + [(EBPF_ALU64 | BPF_OR | BPF_X)] = { + .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS}, + .off = { .min = 0, .max = 0}, + .imm = { .min = 0, .max = 0}, + }, + [(EBPF_ALU64 | BPF_LSH | BPF_X)] = { + .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS}, + .off = { .min = 0, .max = 0}, + .imm = { .min = 0, .max = 0}, + }, + [(EBPF_ALU64 | BPF_RSH | BPF_X)] = { + .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS}, + .off = { .min = 0, .max = 0}, + .imm = { .min = 0, .max = 0}, + }, + [(EBPF_ALU64 | EBPF_ARSH | BPF_X)] = { + .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS}, + .off = { .min = 0, .max = 0}, + .imm = { .min = 0, .max = 0}, + }, + [(EBPF_ALU64 | BPF_XOR | BPF_X)] = { + .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS}, + .off = { .min = 0, .max = 0}, + .imm = { .min = 0, .max = 0}, + }, + [(EBPF_ALU64 | BPF_MUL | BPF_X)] = { + .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS}, + .off = { .min = 0, .max = 0}, + .imm = { .min = 0, .max = 0}, + }, + [(EBPF_ALU64 | BPF_DIV | BPF_X)] = { + .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS}, + .off = { .min = 0, .max = 0}, + .imm = { .min = 0, .max = 0}, + }, + [(EBPF_ALU64 | BPF_MOD | BPF_X)] = { + .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS}, + .off = { .min = 0, .max = 0}, + .imm = { .min = 0, .max = 0}, + }, + [(EBPF_ALU64 | EBPF_MOV | BPF_X)] = { + .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS}, + .off = { .min = 0, .max = 0}, + .imm = { .min = 0, .max = 0}, + }, + [(EBPF_ALU64 | BPF_NEG)] = { + .mask = { .dreg = WRT_REGS, .sreg = ZERO_REG}, + .off = { .min = 0, .max = 0}, + .imm = { .min = 0, .max = 0}, + }, + /* 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}, + }, + /* 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 add instructions */ + [(BPF_STX | EBPF_XADD | 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 | EBPF_XADD | EBPF_DW)] = { + .mask = { .dreg = ALL_REGS, .sreg = ALL_REGS}, + .off = { .min = 0, .max = UINT16_MAX}, + .imm = { .min = 0, .max = 0}, + .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}, + }, + /* 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}, + }, + [(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}, + }, + [(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}, + }, + [(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}, + }, + [(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}, + }, + [(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}, + }, + [(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}, + }, + [(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}, + }, + [(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}, + }, + [(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}, + }, + [(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}, + }, + /* 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}, + }, + [(BPF_JMP | EBPF_JNE | BPF_X)] = { + .mask = { .dreg = ALL_REGS, .sreg = ALL_REGS}, + .off = { .min = 0, .max = UINT16_MAX}, + .imm = { .min = 0, .max = 0}, + }, + [(BPF_JMP | BPF_JGT | BPF_X)] = { + .mask = { .dreg = ALL_REGS, .sreg = ALL_REGS}, + .off = { .min = 0, .max = UINT16_MAX}, + .imm = { .min = 0, .max = 0}, + }, + [(BPF_JMP | EBPF_JLT | BPF_X)] = { + .mask = { .dreg = ALL_REGS, .sreg = ALL_REGS}, + .off = { .min = 0, .max = UINT16_MAX}, + .imm = { .min = 0, .max = 0}, + }, + [(BPF_JMP | BPF_JGE | BPF_X)] = { + .mask = { .dreg = ALL_REGS, .sreg = ALL_REGS}, + .off = { .min = 0, .max = UINT16_MAX}, + .imm = { .min = 0, .max = 0}, + }, + [(BPF_JMP | EBPF_JLE | BPF_X)] = { + .mask = { .dreg = ALL_REGS, .sreg = ALL_REGS}, + .off = { .min = 0, .max = UINT16_MAX}, + .imm = { .min = 0, .max = 0}, + }, + [(BPF_JMP | EBPF_JSGT | BPF_X)] = { + .mask = { .dreg = ALL_REGS, .sreg = ALL_REGS}, + .off = { .min = 0, .max = UINT16_MAX}, + .imm = { .min = 0, .max = 0}, + }, + [(BPF_JMP | EBPF_JSLT | BPF_X)] = { + .mask = { .dreg = ALL_REGS, .sreg = ALL_REGS}, + .off = { .min = 0, .max = UINT16_MAX}, + .imm = { .min = 0, .max = 0}, + }, + [(BPF_JMP | EBPF_JSGE | BPF_X)] = { + .mask = { .dreg = ALL_REGS, .sreg = ALL_REGS}, + .off = { .min = 0, .max = UINT16_MAX}, + .imm = { .min = 0, .max = 0}, + }, + [(BPF_JMP | EBPF_JSLE | BPF_X)] = { + .mask = { .dreg = ALL_REGS, .sreg = ALL_REGS}, + .off = { .min = 0, .max = UINT16_MAX}, + .imm = { .min = 0, .max = 0}, + }, + [(BPF_JMP | BPF_JSET | BPF_X)] = { + .mask = { .dreg = ALL_REGS, .sreg = ALL_REGS}, + .off = { .min = 0, .max = UINT16_MAX}, + .imm = { .min = 0, .max = 0}, + }, + /* 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}, + }, +}; + +/* + * make sure that instruction syntax is valid, + * and it fields don't violate partciular instrcution 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) { - int32_t rc, ofs, stack_sz; - uint32_t i, op, dr; + 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->nb_ins) { + RTE_BPF_LOG(ERR, "%s: program boundary violation at pc: %u, " + "next pc: %u\n", + __func__, get_node_idx(bvf, node), nidx); + return -EINVAL; + } + + ne = node->nb_edge; + if (ne >= RTE_DIM(node->edge_dest)) { + RTE_BPF_LOG(ERR, "%s: internal error at pc: %u\n", + __func__, 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]++; +} + +static struct inst_node * +get_prev_node(struct bpf_verifier *bvf, struct inst_node *node) +{ + return bvf->in + node->prev_node; +} + +/* + * 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 unreachable instructions. + */ +static void +dfs(struct bpf_verifier *bvf) +{ + struct inst_node *next, *node; + + node = bvf->in; + while (node != NULL) { + + 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 = get_node_idx(bvf, 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 = get_prev_node(bvf, node); + } + } else + node = NULL; + } +} + +/* + * report unreachable instructions. + */ +static void +log_unreachable(const struct bpf_verifier *bvf) +{ + uint32_t i; + struct inst_node *node; const struct ebpf_insn *ins; - rc = 0; - stack_sz = 0; - for (i = 0; i != bpf->prm.nb_ins; i++) { - - ins = bpf->prm.ins + i; - op = ins->code; - dr = ins->dst_reg; - ofs = ins->off; - - if ((BPF_CLASS(op) == BPF_STX || BPF_CLASS(op) == BPF_ST) && - dr == EBPF_REG_10) { - ofs -= sizeof(uint64_t); - stack_sz = RTE_MIN(ofs, stack_sz); + for (i = 0; i != bvf->prm->nb_ins; i++) { + + node = bvf->in + i; + ins = bvf->prm->ins + i; + + if (node->colour == WHITE && + ins->code != (BPF_LD | BPF_IMM | EBPF_DW)) + RTE_BPF_LOG(ERR, "unreachable code at pc: %u;\n", 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->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(ERR, + "loop at pc:%u --> pc:%u;\n", + 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 deapth-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; - if (stack_sz != 0) { - stack_sz = -stack_sz; - if (stack_sz > MAX_BPF_STACK_SIZE) - rc = -ERANGE; - else - bpf->stack_sz = stack_sz; + rc = 0; + for (i = 0; i < bvf->prm->nb_ins; i++) { + + ins = bvf->prm->ins + i; + node = bvf->in + i; + + err = check_syntax(ins); + if (err != 0) { + RTE_BPF_LOG(ERR, "%s: %s at pc: %u\n", + __func__, err, i); + rc |= -EINVAL; + } + + /* + * construct CFG, jcc nodes have to outgoing edges, + * 'exit' nodes - none, all others nodes have exaclty 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; + default: + rc |= add_edge(bvf, node, i + 1); + break; + } + + bvf->nb_nodes++; + bvf->node_colour[WHITE]++; } if (rc != 0) - RTE_BPF_LOG(ERR, "%s(%p) failed, error code: %d;\n", - __func__, bpf, rc); + return rc; + + dfs(bvf); + + RTE_BPF_LOG(DEBUG, "%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(ERR, "%s(%p) unreachable instructions;\n", + __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(ERR, "%s(%p) DFS internal error;\n", + __func__, bvf); + return -EINVAL; + } + + if (bvf->edge_type[BACK_EDGE] != 0) { + RTE_BPF_LOG(ERR, "%s(%p) loops detected;\n", + __func__, bvf); + log_loop(bvf); + return -EINVAL; + } + + return 0; +} + +/* + * helper functions get/free eval states. + */ +static struct bpf_eval_state * +pull_eval_state(struct bpf_verifier *bvf) +{ + uint32_t n; + + n = bvf->evst_pool.cur; + if (n == bvf->evst_pool.num) + return NULL; + + bvf->evst_pool.cur = n + 1; + return bvf->evst_pool.ent + n; +} + +static void +push_eval_state(struct bpf_verifier *bvf) +{ + bvf->evst_pool.cur--; +} + +static void +evst_pool_fini(struct bpf_verifier *bvf) +{ + bvf->evst = NULL; + free(bvf->evst_pool.ent); + memset(&bvf->evst_pool, 0, sizeof(bvf->evst_pool)); +} + +static int +evst_pool_init(struct bpf_verifier *bvf) +{ + uint32_t n; + + n = bvf->nb_jcc_nodes + 1; + + bvf->evst_pool.ent = calloc(n, sizeof(bvf->evst_pool.ent[0])); + if (bvf->evst_pool.ent == NULL) + return -ENOMEM; + + bvf->evst_pool.num = n; + bvf->evst_pool.cur = 0; + + bvf->evst = pull_eval_state(bvf); + return 0; +} + +/* + * Save current eval state. + */ +static int +save_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); + if (st == NULL) { + RTE_BPF_LOG(ERR, + "%s: internal error (out of space) at pc: %u", + __func__, 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 */ + node->evst = bvf->evst; + bvf->evst = st; + + RTE_BPF_LOG(DEBUG, "%s(bvf=%p,node=%u) old/new states: %p/%p;\n", + __func__, bvf, get_node_idx(bvf, node), node->evst, bvf->evst); + + return 0; +} + +/* + * Restore previous eval state and mark current eval state as free. + */ +static void +restore_eval_state(struct bpf_verifier *bvf, struct inst_node *node) +{ + RTE_BPF_LOG(DEBUG, "%s(bvf=%p,node=%u) old/new states: %p/%p;\n", + __func__, bvf, get_node_idx(bvf, node), bvf->evst, node->evst); + + bvf->evst = node->evst; + node->evst = NULL; + push_eval_state(bvf); +} + +/* + * Do second pass through CFG and try to evaluate instructions + * via each possible path. + * Right now evaluation functionality is quite limited. + * Still need to add extra checks for: + * - use/return uninitialized registers. + * - use uninitialized data from the stack. + * - memory boundaries violation. + */ +static int +evaluate(struct bpf_verifier *bvf) +{ + int32_t rc; + uint32_t idx, op; + const char *err; + const struct ebpf_insn *ins; + struct inst_node *next, *node; + + node = bvf->in; + ins = bvf->prm->ins; + rc = 0; + + while (node != NULL && rc == 0) { + + /* current node evaluation */ + idx = get_node_idx(bvf, node); + op = ins[idx].code; + + if (ins_chk[op].eval != NULL) { + err = ins_chk[op].eval(bvf, ins + idx); + if (err != NULL) { + RTE_BPF_LOG(ERR, "%s: %s at pc: %u\n", + __func__, err, idx); + rc = -EINVAL; + } + } + + /* proceed through CFG */ + next = get_next_node(bvf, node); + if (next != NULL) { + + /* proceed with next child */ + if (node->cur_edge != node->nb_edge) + rc |= save_eval_state(bvf, node); + else if (node->evst != NULL) + restore_eval_state(bvf, node); + + next->prev_node = get_node_idx(bvf, node); + node = next; + } else { + /* + * finished with current node and all it's kids, + * proceed with parent + */ + node->cur_edge = 0; + node = get_prev_node(bvf, node); + + /* finished */ + if (node == bvf->in) + node = NULL; + } + } + + return rc; +} + +int +bpf_validate(struct rte_bpf *bpf) +{ + int32_t rc; + struct bpf_verifier bvf; + + /* check input argument type, don't allow mbuf ptr on 32-bit */ + if (bpf->prm.prog_arg.type != RTE_BPF_ARG_RAW && + bpf->prm.prog_arg.type != RTE_BPF_ARG_PTR && + (sizeof(uint64_t) != sizeof(uintptr_t) || + bpf->prm.prog_arg.type != RTE_BPF_ARG_PTR_MBUF)) { + RTE_BPF_LOG(ERR, "%s: unsupported argument type\n", __func__); + return -ENOTSUP; + } + + memset(&bvf, 0, sizeof(bvf)); + bvf.prm = &bpf->prm; + bvf.in = calloc(bpf->prm.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) + bpf->stack_sz = bvf.stack_sz; + return rc; } -- 2.13.6