Jakub Kicinski | 58e2af8 | 2016-09-21 11:43:57 +0100 | [diff] [blame] | 1 | /* Copyright (c) 2011-2014 PLUMgrid, http://plumgrid.com |
| 2 | * |
| 3 | * This program is free software; you can redistribute it and/or |
| 4 | * modify it under the terms of version 2 of the GNU General Public |
| 5 | * License as published by the Free Software Foundation. |
| 6 | */ |
| 7 | #ifndef _LINUX_BPF_VERIFIER_H |
| 8 | #define _LINUX_BPF_VERIFIER_H 1 |
| 9 | |
| 10 | #include <linux/bpf.h> /* for enum bpf_reg_type */ |
| 11 | #include <linux/filter.h> /* for MAX_BPF_STACK */ |
Edward Cree | f1174f7 | 2017-08-07 15:26:19 +0100 | [diff] [blame] | 12 | #include <linux/tnum.h> |
Jakub Kicinski | 58e2af8 | 2016-09-21 11:43:57 +0100 | [diff] [blame] | 13 | |
Edward Cree | b03c9f9 | 2017-08-07 15:26:36 +0100 | [diff] [blame] | 14 | /* Maximum variable offset umax_value permitted when resolving memory accesses. |
| 15 | * In practice this is far bigger than any realistic pointer offset; this limit |
| 16 | * ensures that umax_value + (int)off + (int)size cannot overflow a u64. |
| 17 | */ |
Daniel Borkmann | de31796 | 2017-12-22 16:23:11 +0100 | [diff] [blame] | 18 | #define BPF_MAX_VAR_OFF (1 << 29) |
Edward Cree | b03c9f9 | 2017-08-07 15:26:36 +0100 | [diff] [blame] | 19 | /* Maximum variable size permitted for ARG_CONST_SIZE[_OR_ZERO]. This ensures |
| 20 | * that converting umax_value to int cannot overflow. |
| 21 | */ |
Daniel Borkmann | de31796 | 2017-12-22 16:23:11 +0100 | [diff] [blame] | 22 | #define BPF_MAX_VAR_SIZ (1 << 29) |
Josef Bacik | 4846113 | 2016-09-28 10:54:32 -0400 | [diff] [blame] | 23 | |
Edward Cree | 8e9cd9c | 2017-08-23 15:11:21 +0100 | [diff] [blame] | 24 | /* Liveness marks, used for registers and spilled-regs (in stack slots). |
| 25 | * Read marks propagate upwards until they find a write mark; they record that |
| 26 | * "one of this state's descendants read this reg" (and therefore the reg is |
| 27 | * relevant for states_equal() checks). |
| 28 | * Write marks collect downwards and do not propagate; they record that "the |
| 29 | * straight-line code that reached this state (from its parent) wrote this reg" |
| 30 | * (and therefore that reads propagated from this state or its descendants |
| 31 | * should not propagate to its parent). |
| 32 | * A state with a write mark can receive read marks; it just won't propagate |
| 33 | * them to its parent, since the write mark is a property, not of the state, |
| 34 | * but of the link between it and its parent. See mark_reg_read() and |
| 35 | * mark_stack_slot_read() in kernel/bpf/verifier.c. |
| 36 | */ |
Edward Cree | dc503a8 | 2017-08-15 20:34:35 +0100 | [diff] [blame] | 37 | enum bpf_reg_liveness { |
| 38 | REG_LIVE_NONE = 0, /* reg hasn't been read or written this branch */ |
| 39 | REG_LIVE_READ, /* reg was read, so we're sensitive to initial value */ |
| 40 | REG_LIVE_WRITTEN, /* reg was written first, screening off later reads */ |
| 41 | }; |
| 42 | |
Jakub Kicinski | 58e2af8 | 2016-09-21 11:43:57 +0100 | [diff] [blame] | 43 | struct bpf_reg_state { |
| 44 | enum bpf_reg_type type; |
| 45 | union { |
Edward Cree | f1174f7 | 2017-08-07 15:26:19 +0100 | [diff] [blame] | 46 | /* valid when type == PTR_TO_PACKET */ |
| 47 | u16 range; |
Jakub Kicinski | 58e2af8 | 2016-09-21 11:43:57 +0100 | [diff] [blame] | 48 | |
| 49 | /* valid when type == CONST_PTR_TO_MAP | PTR_TO_MAP_VALUE | |
| 50 | * PTR_TO_MAP_VALUE_OR_NULL |
| 51 | */ |
| 52 | struct bpf_map *map_ptr; |
Daniel Borkmann | eb9b195 | 2018-11-01 22:30:38 +0100 | [diff] [blame] | 53 | |
| 54 | /* Max size from any of the above. */ |
| 55 | unsigned long raw; |
Jakub Kicinski | 58e2af8 | 2016-09-21 11:43:57 +0100 | [diff] [blame] | 56 | }; |
Edward Cree | f1174f7 | 2017-08-07 15:26:19 +0100 | [diff] [blame] | 57 | /* Fixed part of pointer offset, pointer types only */ |
| 58 | s32 off; |
| 59 | /* For PTR_TO_PACKET, used to find other pointers with the same variable |
| 60 | * offset, so they can share range knowledge. |
| 61 | * For PTR_TO_MAP_VALUE_OR_NULL this is used to share which map value we |
| 62 | * came from, when one is tested for != NULL. |
| 63 | */ |
Alexei Starovoitov | d2a4dd3 | 2016-12-07 10:57:59 -0800 | [diff] [blame] | 64 | u32 id; |
Edward Cree | dc503a8 | 2017-08-15 20:34:35 +0100 | [diff] [blame] | 65 | /* Ordering of fields matters. See states_equal() */ |
Edward Cree | f1174f7 | 2017-08-07 15:26:19 +0100 | [diff] [blame] | 66 | /* For scalar types (SCALAR_VALUE), this represents our knowledge of |
| 67 | * the actual value. |
| 68 | * For pointer types, this represents the variable part of the offset |
| 69 | * from the pointed-to object, and is shared with all bpf_reg_states |
| 70 | * with the same id as us. |
| 71 | */ |
| 72 | struct tnum var_off; |
Alexei Starovoitov | d2a4dd3 | 2016-12-07 10:57:59 -0800 | [diff] [blame] | 73 | /* Used to determine if any memory access using this register will |
Edward Cree | f1174f7 | 2017-08-07 15:26:19 +0100 | [diff] [blame] | 74 | * result in a bad access. |
| 75 | * These refer to the same value as var_off, not necessarily the actual |
| 76 | * contents of the register. |
Alexei Starovoitov | d2a4dd3 | 2016-12-07 10:57:59 -0800 | [diff] [blame] | 77 | */ |
Edward Cree | b03c9f9 | 2017-08-07 15:26:36 +0100 | [diff] [blame] | 78 | s64 smin_value; /* minimum possible (s64)value */ |
| 79 | s64 smax_value; /* maximum possible (s64)value */ |
| 80 | u64 umin_value; /* minimum possible (u64)value */ |
| 81 | u64 umax_value; /* maximum possible (u64)value */ |
Edward Cree | dc503a8 | 2017-08-15 20:34:35 +0100 | [diff] [blame] | 82 | /* This field must be last, for states_equal() reasons. */ |
| 83 | enum bpf_reg_liveness live; |
Jakub Kicinski | 58e2af8 | 2016-09-21 11:43:57 +0100 | [diff] [blame] | 84 | }; |
| 85 | |
| 86 | enum bpf_stack_slot_type { |
| 87 | STACK_INVALID, /* nothing was stored in this stack slot */ |
| 88 | STACK_SPILL, /* register spilled into stack */ |
| 89 | STACK_MISC /* BPF program wrote some data into this slot */ |
| 90 | }; |
| 91 | |
| 92 | #define BPF_REG_SIZE 8 /* size of eBPF register in bytes */ |
| 93 | |
Alexei Starovoitov | 28356c2 | 2019-04-03 18:39:01 +0000 | [diff] [blame] | 94 | struct bpf_stack_state { |
| 95 | struct bpf_reg_state spilled_ptr; |
| 96 | u8 slot_type[BPF_REG_SIZE]; |
| 97 | }; |
| 98 | |
Jakub Kicinski | 58e2af8 | 2016-09-21 11:43:57 +0100 | [diff] [blame] | 99 | /* state of the program: |
| 100 | * type of all registers and stack info |
| 101 | */ |
| 102 | struct bpf_verifier_state { |
| 103 | struct bpf_reg_state regs[MAX_BPF_REG]; |
Edward Cree | dc503a8 | 2017-08-15 20:34:35 +0100 | [diff] [blame] | 104 | struct bpf_verifier_state *parent; |
Alexei Starovoitov | 28356c2 | 2019-04-03 18:39:01 +0000 | [diff] [blame] | 105 | int allocated_stack; |
| 106 | struct bpf_stack_state *stack; |
Daniel Borkmann | ae03b6b | 2019-04-03 18:39:12 +0000 | [diff] [blame] | 107 | bool speculative; |
Jakub Kicinski | 58e2af8 | 2016-09-21 11:43:57 +0100 | [diff] [blame] | 108 | }; |
| 109 | |
| 110 | /* linked list of verifier states used to prune search */ |
| 111 | struct bpf_verifier_state_list { |
| 112 | struct bpf_verifier_state state; |
| 113 | struct bpf_verifier_state_list *next; |
| 114 | }; |
| 115 | |
Daniel Borkmann | ae03b6b | 2019-04-03 18:39:12 +0000 | [diff] [blame] | 116 | /* Possible states for alu_state member. */ |
Daniel Borkmann | 19e4f40 | 2021-05-31 18:25:53 +0000 | [diff] [blame] | 117 | #define BPF_ALU_SANITIZE_SRC (1U << 0) |
| 118 | #define BPF_ALU_SANITIZE_DST (1U << 1) |
Daniel Borkmann | ae03b6b | 2019-04-03 18:39:12 +0000 | [diff] [blame] | 119 | #define BPF_ALU_NEG_VALUE (1U << 2) |
Daniel Borkmann | 6588a49 | 2019-04-03 18:39:13 +0000 | [diff] [blame] | 120 | #define BPF_ALU_NON_POINTER (1U << 3) |
Daniel Borkmann | 19e4f40 | 2021-05-31 18:25:53 +0000 | [diff] [blame] | 121 | #define BPF_ALU_IMMEDIATE (1U << 4) |
Daniel Borkmann | ae03b6b | 2019-04-03 18:39:12 +0000 | [diff] [blame] | 122 | #define BPF_ALU_SANITIZE (BPF_ALU_SANITIZE_SRC | \ |
| 123 | BPF_ALU_SANITIZE_DST) |
| 124 | |
Jakub Kicinski | 58e2af8 | 2016-09-21 11:43:57 +0100 | [diff] [blame] | 125 | struct bpf_insn_aux_data { |
Alexei Starovoitov | 81ed18a | 2017-03-15 18:26:42 -0700 | [diff] [blame] | 126 | union { |
| 127 | enum bpf_reg_type ptr_type; /* pointer type for load/store insns */ |
| 128 | struct bpf_map *map_ptr; /* pointer for call insn into lookup_elem */ |
Daniel Borkmann | ae03b6b | 2019-04-03 18:39:12 +0000 | [diff] [blame] | 129 | u32 alu_limit; /* limit for add/sub register with pointer */ |
Alexei Starovoitov | 81ed18a | 2017-03-15 18:26:42 -0700 | [diff] [blame] | 130 | }; |
Yonghong Song | 2399463 | 2017-06-22 15:07:39 -0700 | [diff] [blame] | 131 | int ctx_field_size; /* the ctx field size for load insn, maybe 0 */ |
Alexei Starovoitov | 83b570c | 2018-05-15 09:27:05 -0700 | [diff] [blame] | 132 | int sanitize_stack_off; /* stack slot to be cleared */ |
Daniel Borkmann | 2b3ea8c | 2017-12-22 16:22:59 +0100 | [diff] [blame] | 133 | bool seen; /* this insn was processed by the verifier */ |
Daniel Borkmann | ae03b6b | 2019-04-03 18:39:12 +0000 | [diff] [blame] | 134 | u8 alu_state; /* used in combination with alu_limit */ |
Jakub Kicinski | 58e2af8 | 2016-09-21 11:43:57 +0100 | [diff] [blame] | 135 | }; |
| 136 | |
| 137 | #define MAX_USED_MAPS 64 /* max number of maps accessed by one eBPF program */ |
| 138 | |
Jakub Kicinski | 13a27df | 2016-09-21 11:43:58 +0100 | [diff] [blame] | 139 | struct bpf_verifier_env; |
| 140 | struct bpf_ext_analyzer_ops { |
| 141 | int (*insn_hook)(struct bpf_verifier_env *env, |
| 142 | int insn_idx, int prev_insn_idx); |
| 143 | }; |
| 144 | |
Jakub Kicinski | 58e2af8 | 2016-09-21 11:43:57 +0100 | [diff] [blame] | 145 | /* single container for all structs |
| 146 | * one verifier_env per bpf_check() call |
| 147 | */ |
| 148 | struct bpf_verifier_env { |
Daniel Borkmann | 6a42c49 | 2019-04-03 18:39:05 +0000 | [diff] [blame] | 149 | u32 insn_idx; |
| 150 | u32 prev_insn_idx; |
Jakub Kicinski | 58e2af8 | 2016-09-21 11:43:57 +0100 | [diff] [blame] | 151 | struct bpf_prog *prog; /* eBPF program being verified */ |
| 152 | struct bpf_verifier_stack_elem *head; /* stack of verifier states to be processed */ |
| 153 | int stack_size; /* number of states to be processed */ |
David S. Miller | e07b98d | 2017-05-10 11:38:07 -0700 | [diff] [blame] | 154 | bool strict_alignment; /* perform strict pointer alignment checks */ |
Alexei Starovoitov | 28356c2 | 2019-04-03 18:39:01 +0000 | [diff] [blame] | 155 | struct bpf_verifier_state *cur_state; /* current verifier state */ |
Jakub Kicinski | 58e2af8 | 2016-09-21 11:43:57 +0100 | [diff] [blame] | 156 | struct bpf_verifier_state_list **explored_states; /* search pruning optimization */ |
Jakub Kicinski | 13a27df | 2016-09-21 11:43:58 +0100 | [diff] [blame] | 157 | const struct bpf_ext_analyzer_ops *analyzer_ops; /* external analyzer ops */ |
| 158 | void *analyzer_priv; /* pointer to external analyzer's private data */ |
Jakub Kicinski | 58e2af8 | 2016-09-21 11:43:57 +0100 | [diff] [blame] | 159 | struct bpf_map *used_maps[MAX_USED_MAPS]; /* array of map's used by eBPF program */ |
| 160 | u32 used_map_cnt; /* number of used maps */ |
| 161 | u32 id_gen; /* used to generate unique reg IDs */ |
| 162 | bool allow_ptr_leaks; |
| 163 | bool seen_direct_write; |
| 164 | struct bpf_insn_aux_data *insn_aux_data; /* array of per-insn state */ |
| 165 | }; |
| 166 | |
Alexei Starovoitov | 28356c2 | 2019-04-03 18:39:01 +0000 | [diff] [blame] | 167 | static inline struct bpf_reg_state *cur_regs(struct bpf_verifier_env *env) |
| 168 | { |
| 169 | return env->cur_state->regs; |
| 170 | } |
| 171 | |
Jakub Kicinski | 13a27df | 2016-09-21 11:43:58 +0100 | [diff] [blame] | 172 | int bpf_analyzer(struct bpf_prog *prog, const struct bpf_ext_analyzer_ops *ops, |
| 173 | void *priv); |
| 174 | |
Jakub Kicinski | 58e2af8 | 2016-09-21 11:43:57 +0100 | [diff] [blame] | 175 | #endif /* _LINUX_BPF_VERIFIER_H */ |