* 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. */
| 1979 | * Programs with unreachable instructions and/or loops will be rejected. |
| 1980 | */ |
| 1981 | static int |
| 1982 | validate(struct bpf_verifier *bvf) |
| 1983 | { |
| 1984 | int32_t rc; |
| 1985 | uint32_t i; |
| 1986 | struct inst_node *node; |
| 1987 | const struct ebpf_insn *ins; |
| 1988 | const char *err; |
| 1989 | |
| 1990 | rc = 0; |
| 1991 | for (i = 0; i < bvf->prm->nb_ins; i++) { |
| 1992 | |
| 1993 | ins = bvf->prm->ins + i; |
| 1994 | node = bvf->in + i; |
| 1995 | |
| 1996 | err = check_syntax(ins); |
| 1997 | if (err != 0) { |
| 1998 | RTE_BPF_LOG(ERR, "%s: %s at pc: %u\n", |
| 1999 | __func__, err, i); |
| 2000 | rc |= -EINVAL; |
| 2001 | } |
| 2002 | |
| 2003 | /* |
| 2004 | * construct CFG, jcc nodes have to outgoing edges, |
| 2005 | * 'exit' nodes - none, all other nodes have exactly one |
| 2006 | * outgoing edge. |
| 2007 | */ |
| 2008 | switch (ins->code) { |
| 2009 | case (BPF_JMP | EBPF_EXIT): |
| 2010 | break; |
| 2011 | case (BPF_JMP | BPF_JEQ | BPF_K): |
| 2012 | case (BPF_JMP | EBPF_JNE | BPF_K): |
| 2013 | case (BPF_JMP | BPF_JGT | BPF_K): |
| 2014 | case (BPF_JMP | EBPF_JLT | BPF_K): |
| 2015 | case (BPF_JMP | BPF_JGE | BPF_K): |
| 2016 | case (BPF_JMP | EBPF_JLE | BPF_K): |
| 2017 | case (BPF_JMP | EBPF_JSGT | BPF_K): |
| 2018 | case (BPF_JMP | EBPF_JSLT | BPF_K): |
| 2019 | case (BPF_JMP | EBPF_JSGE | BPF_K): |
| 2020 | case (BPF_JMP | EBPF_JSLE | BPF_K): |
| 2021 | case (BPF_JMP | BPF_JSET | BPF_K): |
| 2022 | case (BPF_JMP | BPF_JEQ | BPF_X): |
| 2023 | case (BPF_JMP | EBPF_JNE | BPF_X): |
| 2024 | case (BPF_JMP | BPF_JGT | BPF_X): |
| 2025 | case (BPF_JMP | EBPF_JLT | BPF_X): |
| 2026 | case (BPF_JMP | BPF_JGE | BPF_X): |
| 2027 | case (BPF_JMP | EBPF_JLE | BPF_X): |
| 2028 | case (BPF_JMP | EBPF_JSGT | BPF_X): |
| 2029 | case (BPF_JMP | EBPF_JSLT | BPF_X): |
| 2030 | case (BPF_JMP | EBPF_JSGE | BPF_X): |
| 2031 | case (BPF_JMP | EBPF_JSLE | BPF_X): |
| 2032 | case (BPF_JMP | BPF_JSET | BPF_X): |
| 2033 | rc |= add_edge(bvf, node, i + ins->off + 1); |
| 2034 | rc |= add_edge(bvf, node, i + 1); |
| 2035 | bvf->nb_jcc_nodes++; |
| 2036 | break; |
| 2037 | case (BPF_JMP | BPF_JA): |
| 2038 | rc |= add_edge(bvf, node, i + ins->off + 1); |
no test coverage detected