bpf: don't (ab)use instructions to store state
authorJakub Kicinski <jakub.kicinski@netronome.com>
Wed, 21 Sep 2016 10:43:56 +0000 (11:43 +0100)
committerDavid S. Miller <davem@davemloft.net>
Wed, 21 Sep 2016 23:50:02 +0000 (19:50 -0400)
Storing state in reserved fields of instructions makes
it impossible to run verifier on programs already
marked as read-only. Allocate and use an array of
per-instruction state instead.

While touching the error path rename and move existing
jump target.

Suggested-by: Alexei Starovoitov <ast@kernel.org>
Signed-off-by: Jakub Kicinski <jakub.kicinski@netronome.com>
Acked-by: Alexei Starovoitov <ast@kernel.org>
Acked-by: Daniel Borkmann <daniel@iogearbox.net>
Signed-off-by: David S. Miller <davem@davemloft.net>
kernel/bpf/verifier.c

index 3a75ee3bdcd1f23a4d083b1d4abba983ccd1fca6..a9542d89f293a401720e728a8474e0ba3038fdce 100644 (file)
@@ -181,6 +181,10 @@ struct verifier_stack_elem {
        struct verifier_stack_elem *next;
 };
 
+struct bpf_insn_aux_data {
+       enum bpf_reg_type ptr_type;     /* pointer type for load/store insns */
+};
+
 #define MAX_USED_MAPS 64 /* max number of maps accessed by one eBPF program */
 
 /* single container for all structs
@@ -197,6 +201,7 @@ struct verifier_env {
        u32 id_gen;                     /* used to generate unique reg IDs */
        bool allow_ptr_leaks;
        bool seen_direct_write;
+       struct bpf_insn_aux_data *insn_aux_data; /* array of per-insn state */
 };
 
 #define BPF_COMPLEXITY_LIMIT_INSNS     65536
@@ -2344,7 +2349,7 @@ static int do_check(struct verifier_env *env)
                                return err;
 
                } else if (class == BPF_LDX) {
-                       enum bpf_reg_type src_reg_type;
+                       enum bpf_reg_type *prev_src_type, src_reg_type;
 
                        /* check for reserved fields is already done */
 
@@ -2374,16 +2379,18 @@ static int do_check(struct verifier_env *env)
                                continue;
                        }
 
-                       if (insn->imm == 0) {
+                       prev_src_type = &env->insn_aux_data[insn_idx].ptr_type;
+
+                       if (*prev_src_type == NOT_INIT) {
                                /* saw a valid insn
                                 * dst_reg = *(u32 *)(src_reg + off)
-                                * use reserved 'imm' field to mark this insn
+                                * save type to validate intersecting paths
                                 */
-                               insn->imm = src_reg_type;
+                               *prev_src_type = src_reg_type;
 
-                       } else if (src_reg_type != insn->imm &&
+                       } else if (src_reg_type != *prev_src_type &&
                                   (src_reg_type == PTR_TO_CTX ||
-                                   insn->imm == PTR_TO_CTX)) {
+                                   *prev_src_type == PTR_TO_CTX)) {
                                /* ABuser program is trying to use the same insn
                                 * dst_reg = *(u32*) (src_reg + off)
                                 * with different pointer types:
@@ -2396,7 +2403,7 @@ static int do_check(struct verifier_env *env)
                        }
 
                } else if (class == BPF_STX) {
-                       enum bpf_reg_type dst_reg_type;
+                       enum bpf_reg_type *prev_dst_type, dst_reg_type;
 
                        if (BPF_MODE(insn->code) == BPF_XADD) {
                                err = check_xadd(env, insn);
@@ -2424,11 +2431,13 @@ static int do_check(struct verifier_env *env)
                        if (err)
                                return err;
 
-                       if (insn->imm == 0) {
-                               insn->imm = dst_reg_type;
-                       } else if (dst_reg_type != insn->imm &&
+                       prev_dst_type = &env->insn_aux_data[insn_idx].ptr_type;
+
+                       if (*prev_dst_type == NOT_INIT) {
+                               *prev_dst_type = dst_reg_type;
+                       } else if (dst_reg_type != *prev_dst_type &&
                                   (dst_reg_type == PTR_TO_CTX ||
-                                   insn->imm == PTR_TO_CTX)) {
+                                   *prev_dst_type == PTR_TO_CTX)) {
                                verbose("same insn cannot be used with different pointers\n");
                                return -EINVAL;
                        }
@@ -2686,10 +2695,11 @@ static void convert_pseudo_ld_imm64(struct verifier_env *env)
 static int convert_ctx_accesses(struct verifier_env *env)
 {
        const struct bpf_verifier_ops *ops = env->prog->aux->ops;
+       const int insn_cnt = env->prog->len;
        struct bpf_insn insn_buf[16], *insn;
        struct bpf_prog *new_prog;
        enum bpf_access_type type;
-       int i, insn_cnt, cnt;
+       int i, cnt, delta = 0;
 
        if (ops->gen_prologue) {
                cnt = ops->gen_prologue(insn_buf, env->seen_direct_write,
@@ -2703,18 +2713,16 @@ static int convert_ctx_accesses(struct verifier_env *env)
                        if (!new_prog)
                                return -ENOMEM;
                        env->prog = new_prog;
+                       delta += cnt - 1;
                }
        }
 
        if (!ops->convert_ctx_access)
                return 0;
 
-       insn_cnt = env->prog->len;
-       insn = env->prog->insnsi;
+       insn = env->prog->insnsi + delta;
 
        for (i = 0; i < insn_cnt; i++, insn++) {
-               u32 insn_delta;
-
                if (insn->code == (BPF_LDX | BPF_MEM | BPF_W) ||
                    insn->code == (BPF_LDX | BPF_MEM | BPF_DW))
                        type = BPF_READ;
@@ -2724,11 +2732,8 @@ static int convert_ctx_accesses(struct verifier_env *env)
                else
                        continue;
 
-               if (insn->imm != PTR_TO_CTX) {
-                       /* clear internal mark */
-                       insn->imm = 0;
+               if (env->insn_aux_data[i].ptr_type != PTR_TO_CTX)
                        continue;
-               }
 
                cnt = ops->convert_ctx_access(type, insn->dst_reg, insn->src_reg,
                                              insn->off, insn_buf, env->prog);
@@ -2737,18 +2742,16 @@ static int convert_ctx_accesses(struct verifier_env *env)
                        return -EINVAL;
                }
 
-               new_prog = bpf_patch_insn_single(env->prog, i, insn_buf, cnt);
+               new_prog = bpf_patch_insn_single(env->prog, i + delta, insn_buf,
+                                                cnt);
                if (!new_prog)
                        return -ENOMEM;
 
-               insn_delta = cnt - 1;
+               delta += cnt - 1;
 
                /* keep walking new program and skip insns we just inserted */
                env->prog = new_prog;
-               insn      = new_prog->insnsi + i + insn_delta;
-
-               insn_cnt += insn_delta;
-               i        += insn_delta;
+               insn      = new_prog->insnsi + i + delta;
        }
 
        return 0;
@@ -2792,6 +2795,11 @@ int bpf_check(struct bpf_prog **prog, union bpf_attr *attr)
        if (!env)
                return -ENOMEM;
 
+       env->insn_aux_data = vzalloc(sizeof(struct bpf_insn_aux_data) *
+                                    (*prog)->len);
+       ret = -ENOMEM;
+       if (!env->insn_aux_data)
+               goto err_free_env;
        env->prog = *prog;
 
        /* grab the mutex to protect few globals used by verifier */
@@ -2810,12 +2818,12 @@ int bpf_check(struct bpf_prog **prog, union bpf_attr *attr)
                /* log_* values have to be sane */
                if (log_size < 128 || log_size > UINT_MAX >> 8 ||
                    log_level == 0 || log_ubuf == NULL)
-                       goto free_env;
+                       goto err_unlock;
 
                ret = -ENOMEM;
                log_buf = vmalloc(log_size);
                if (!log_buf)
-                       goto free_env;
+                       goto err_unlock;
        } else {
                log_level = 0;
        }
@@ -2884,14 +2892,16 @@ skip_full_check:
 free_log_buf:
        if (log_level)
                vfree(log_buf);
-free_env:
        if (!env->prog->aux->used_maps)
                /* if we didn't copy map pointers into bpf_prog_info, release
                 * them now. Otherwise free_bpf_prog_info() will release them.
                 */
                release_maps(env);
        *prog = env->prog;
-       kfree(env);
+err_unlock:
        mutex_unlock(&bpf_verifier_lock);
+       vfree(env->insn_aux_data);
+err_free_env:
+       kfree(env);
        return ret;
 }