Merge tag 'nfs-for-4.14-1' of git://git.linux-nfs.org/projects/trondmy/linux-nfs

[mirror_ubuntu-bionic-kernel.git] / include / linux / bpf_verifier.h

diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index 8e5d31f6faefd361cee145be654a968123ae5e6a..b8d200f60a4090882cf125ea28294430dd320242 100644 (file)
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -9,41 +9,75 @@
 
 #include <linux/bpf.h> /* for enum bpf_reg_type */
 #include <linux/filter.h> /* for MAX_BPF_STACK */
+#include <linux/tnum.h>
 
- /* Just some arbitrary values so we can safely do math without overflowing and
-  * are obviously wrong for any sort of memory access.
-  */
-#define BPF_REGISTER_MAX_RANGE (1024 * 1024 * 1024)
-#define BPF_REGISTER_MIN_RANGE -1
+/* Maximum variable offset umax_value permitted when resolving memory accesses.
+ * In practice this is far bigger than any realistic pointer offset; this limit
+ * ensures that umax_value + (int)off + (int)size cannot overflow a u64.
+ */
+#define BPF_MAX_VAR_OFF        (1ULL << 31)
+/* Maximum variable size permitted for ARG_CONST_SIZE[_OR_ZERO].  This ensures
+ * that converting umax_value to int cannot overflow.
+ */
+#define BPF_MAX_VAR_SIZ        INT_MAX
+
+/* Liveness marks, used for registers and spilled-regs (in stack slots).
+ * Read marks propagate upwards until they find a write mark; they record that
+ * "one of this state's descendants read this reg" (and therefore the reg is
+ * relevant for states_equal() checks).
+ * Write marks collect downwards and do not propagate; they record that "the
+ * straight-line code that reached this state (from its parent) wrote this reg"
+ * (and therefore that reads propagated from this state or its descendants
+ * should not propagate to its parent).
+ * A state with a write mark can receive read marks; it just won't propagate
+ * them to its parent, since the write mark is a property, not of the state,
+ * but of the link between it and its parent.  See mark_reg_read() and
+ * mark_stack_slot_read() in kernel/bpf/verifier.c.
+ */
+enum bpf_reg_liveness {
+       REG_LIVE_NONE = 0, /* reg hasn't been read or written this branch */
+       REG_LIVE_READ, /* reg was read, so we're sensitive to initial value */
+       REG_LIVE_WRITTEN, /* reg was written first, screening off later reads */
+};
 
 struct bpf_reg_state {
        enum bpf_reg_type type;
        union {
-               /* valid when type == CONST_IMM | PTR_TO_STACK | UNKNOWN_VALUE */
-               s64 imm;
-
-               /* valid when type == PTR_TO_PACKET* */
-               struct {
-                       u16 off;
-                       u16 range;
-               };
+               /* valid when type == PTR_TO_PACKET */
+               u16 range;
 
                /* valid when type == CONST_PTR_TO_MAP | PTR_TO_MAP_VALUE |
                 *   PTR_TO_MAP_VALUE_OR_NULL
                 */
                struct bpf_map *map_ptr;
        };
+       /* Fixed part of pointer offset, pointer types only */
+       s32 off;
+       /* For PTR_TO_PACKET, used to find other pointers with the same variable
+        * offset, so they can share range knowledge.
+        * For PTR_TO_MAP_VALUE_OR_NULL this is used to share which map value we
+        * came from, when one is tested for != NULL.
+        */
        u32 id;
+       /* Ordering of fields matters.  See states_equal() */
+       /* For scalar types (SCALAR_VALUE), this represents our knowledge of
+        * the actual value.
+        * For pointer types, this represents the variable part of the offset
+        * from the pointed-to object, and is shared with all bpf_reg_states
+        * with the same id as us.
+        */
+       struct tnum var_off;
        /* Used to determine if any memory access using this register will
-        * result in a bad access. These two fields must be last.
-        * See states_equal()
+        * result in a bad access.
+        * These refer to the same value as var_off, not necessarily the actual
+        * contents of the register.
         */
-       s64 min_value;
-       u64 max_value;
-       u32 min_align;
-       u32 aux_off;
-       u32 aux_off_align;
-       bool value_from_signed;
+       s64 smin_value; /* minimum possible (s64)value */
+       s64 smax_value; /* maximum possible (s64)value */
+       u64 umin_value; /* minimum possible (u64)value */
+       u64 umax_value; /* maximum possible (u64)value */
+       /* This field must be last, for states_equal() reasons. */
+       enum bpf_reg_liveness live;
 };
 
 enum bpf_stack_slot_type {
@@ -61,6 +95,7 @@ struct bpf_verifier_state {
        struct bpf_reg_state regs[MAX_BPF_REG];
        u8 stack_slot_type[MAX_BPF_STACK];
        struct bpf_reg_state spilled_regs[MAX_BPF_STACK / BPF_REG_SIZE];
+       struct bpf_verifier_state *parent;
 };
 
 /* linked list of verifier states used to prune search */
@@ -103,7 +138,6 @@ struct bpf_verifier_env {
        u32 id_gen;                     /* used to generate unique reg IDs */
        bool allow_ptr_leaks;
        bool seen_direct_write;
-       bool varlen_map_value_access;
        struct bpf_insn_aux_data *insn_aux_data; /* array of per-insn state */
 };