1 files changed, 227 insertions, 59 deletions

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index c97bce6a0e0e..c14003840bc5 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -186,6 +186,14 @@ struct verifier_stack_elem {
         struct verifier_stack_elem *next;
 };
 
+struct bpf_insn_aux_data {
+        union {
+                enum bpf_reg_type ptr_type;     /* pointer type for load/store insns */
+                struct bpf_map *map_ptr;        /* pointer for call insn into lookup_elem */
+        };
+        bool seen; /* this insn was processed by the verifier */
+};
+
 #define MAX_USED_MAPS 64 /* max number of maps accessed by one eBPF program */
 
 /* single container for all structs
@@ -200,6 +208,7 @@ struct verifier_env {
         struct bpf_map *used_maps[MAX_USED_MAPS]; /* array of map's used by eBPF program */
         u32 used_map_cnt;               /* number of used maps */
         bool allow_ptr_leaks;
+        struct bpf_insn_aux_data *insn_aux_data; /* array of per-insn state */
 };
 
 /* verbose verifier prints what it's seeing
@@ -674,6 +683,13 @@ static bool is_pointer_value(struct verifier_env *env, int regno)
         }
 }
 
+static bool is_ctx_reg(struct verifier_env *env, int regno)
+{
+        const struct reg_state *reg = &env->cur_state.regs[regno];
+
+        return reg->type == PTR_TO_CTX;
+}
+
 /* check whether memory at (regno + off) is accessible for t = (read | write)
  * if t==write, value_regno is a register which value is stored into memory
  * if t==read, value_regno is a register which will receive the value from memory
@@ -770,6 +786,12 @@ static int check_xadd(struct verifier_env *env, struct bpf_insn *insn)
                 return -EACCES;
         }
 
+        if (is_ctx_reg(env, insn->dst_reg)) {
+                verbose("BPF_XADD stores into R%d context is not allowed\n",
+                        insn->dst_reg);
+                return -EACCES;
+        }
+
         /* check whether atomic_add can read the memory */
         err = check_mem_access(env, insn->dst_reg, insn->off,
                                BPF_SIZE(insn->code), BPF_READ, -1);
@@ -945,7 +967,7 @@ error:
         return -EINVAL;
 }
 
-static int check_call(struct verifier_env *env, int func_id)
+static int check_call(struct verifier_env *env, int func_id, int insn_idx)
 {
         struct verifier_state *state = &env->cur_state;
         const struct bpf_func_proto *fn = NULL;
@@ -981,6 +1003,13 @@ static int check_call(struct verifier_env *env, int func_id)
         err = check_func_arg(env, BPF_REG_2, fn->arg2_type, &map);
         if (err)
                 return err;
+        if (func_id == BPF_FUNC_tail_call) {
+                if (map == NULL) {
+                        verbose("verifier bug\n");
+                        return -EINVAL;
+                }
+                env->insn_aux_data[insn_idx].map_ptr = map;
+        }
         err = check_func_arg(env, BPF_REG_3, fn->arg3_type, &map);
         if (err)
                 return err;
@@ -1044,7 +1073,8 @@ static int check_alu_op(struct verifier_env *env, struct bpf_insn *insn)
                         }
                 } else {
                         if (insn->src_reg != BPF_REG_0 || insn->off != 0 ||
-                            (insn->imm != 16 && insn->imm != 32 && insn->imm != 64)) {
+                            (insn->imm != 16 && insn->imm != 32 && insn->imm != 64) ||
+                            BPF_CLASS(insn->code) == BPF_ALU64) {
                                 verbose("BPF_END uses reserved fields\n");
                                 return -EINVAL;
                         }
@@ -1148,6 +1178,11 @@ static int check_alu_op(struct verifier_env *env, struct bpf_insn *insn)
                         return -EINVAL;
                 }
 
+                if (opcode == BPF_ARSH && BPF_CLASS(insn->code) != BPF_ALU64) {
+                        verbose("BPF_ARSH not supported for 32 bit ALU\n");
+                        return -EINVAL;
+                }
+
                 if ((opcode == BPF_LSH || opcode == BPF_RSH ||
                      opcode == BPF_ARSH) && BPF_SRC(insn->code) == BPF_K) {
                         int size = BPF_CLASS(insn->code) == BPF_ALU64 ? 64 : 32;
@@ -1777,13 +1812,14 @@ static int do_check(struct verifier_env *env)
                         print_bpf_insn(env, insn);
                 }
 
+                env->insn_aux_data[insn_idx].seen = true;
                 if (class == BPF_ALU || class == BPF_ALU64) {
                         err = check_alu_op(env, insn);
                         if (err)
                                 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 */
 
@@ -1812,16 +1848,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:
@@ -1834,7 +1872,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);
@@ -1862,11 +1900,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;
                         }
@@ -1882,6 +1922,12 @@ static int do_check(struct verifier_env *env)
                         if (err)
                                 return err;
 
+                        if (is_ctx_reg(env, insn->dst_reg)) {
+                                verbose("BPF_ST stores into R%d context is not allowed\n",
+                                        insn->dst_reg);
+                                return -EACCES;
+                        }
+
                         /* check that memory (dst_reg + off) is writeable */
                         err = check_mem_access(env, insn->dst_reg, insn->off,
                                                BPF_SIZE(insn->code), BPF_WRITE,
@@ -1901,7 +1947,7 @@ static int do_check(struct verifier_env *env)
                                         return -EINVAL;
                                 }
 
-                                err = check_call(env, insn->imm);
+                                err = check_call(env, insn->imm, insn_idx);
                                 if (err)
                                         return err;
 
@@ -1968,6 +2014,7 @@ process_bpf_exit:
                                         return err;
 
                                 insn_idx++;
+                                env->insn_aux_data[insn_idx].seen = true;
                         } else {
                                 verbose("invalid BPF_LD mode\n");
                                 return -EINVAL;
@@ -2097,23 +2144,60 @@ static void convert_pseudo_ld_imm64(struct verifier_env *env)
                         insn->src_reg = 0;
 }
 
-static void adjust_branches(struct bpf_prog *prog, int pos, int delta)
+/* single env->prog->insni[off] instruction was replaced with the range
+ * insni[off, off + cnt).  Adjust corresponding insn_aux_data by copying
+ * [0, off) and [off, end) to new locations, so the patched range stays zero
+ */
+static int adjust_insn_aux_data(struct verifier_env *env, u32 prog_len,
+                                u32 off, u32 cnt)
 {
-        struct bpf_insn *insn = prog->insnsi;
-        int insn_cnt = prog->len;
+        struct bpf_insn_aux_data *new_data, *old_data = env->insn_aux_data;
         int i;
 
-        for (i = 0; i < insn_cnt; i++, insn++) {
-                if (BPF_CLASS(insn->code) != BPF_JMP ||
-                    BPF_OP(insn->code) == BPF_CALL ||
-                    BPF_OP(insn->code) == BPF_EXIT)
-                        continue;
+        if (cnt == 1)
+                return 0;
+        new_data = vzalloc(sizeof(struct bpf_insn_aux_data) * prog_len);
+        if (!new_data)
+                return -ENOMEM;
+        memcpy(new_data, old_data, sizeof(struct bpf_insn_aux_data) * off);
+        memcpy(new_data + off + cnt - 1, old_data + off,
+               sizeof(struct bpf_insn_aux_data) * (prog_len - off - cnt + 1));
+        for (i = off; i < off + cnt - 1; i++)
+                new_data[i].seen = true;
+        env->insn_aux_data = new_data;
+        vfree(old_data);
+        return 0;
+}
+
+static struct bpf_prog *bpf_patch_insn_data(struct verifier_env *env, u32 off,
+                                            const struct bpf_insn *patch, u32 len)
+{
+        struct bpf_prog *new_prog;
 
-                /* adjust offset of jmps if necessary */
-                if (i < pos && i + insn->off + 1 > pos)
-                        insn->off += delta;
-                else if (i > pos + delta && i + insn->off + 1 <= pos + delta)
-                        insn->off -= delta;
+        new_prog = bpf_patch_insn_single(env->prog, off, patch, len);
+        if (!new_prog)
+                return NULL;
+        if (adjust_insn_aux_data(env, new_prog->len, off, len))
+                return NULL;
+        return new_prog;
+}
+
+/* The verifier does more data flow analysis than llvm and will not explore
+ * branches that are dead at run time. Malicious programs can have dead code
+ * too. Therefore replace all dead at-run-time code with nops.
+ */
+static void sanitize_dead_code(struct verifier_env *env)
+{
+        struct bpf_insn_aux_data *aux_data = env->insn_aux_data;
+        struct bpf_insn nop = BPF_MOV64_REG(BPF_REG_0, BPF_REG_0);
+        struct bpf_insn *insn = env->prog->insnsi;
+        const int insn_cnt = env->prog->len;
+        int i;
+
+        for (i = 0; i < insn_cnt; i++) {
+                if (aux_data[i].seen)
+                        continue;
+                memcpy(insn + i, &nop, sizeof(nop));
         }
 }
 
@@ -2123,17 +2207,18 @@ static void adjust_branches(struct bpf_prog *prog, int pos, int delta)
 static int convert_ctx_accesses(struct verifier_env *env)
 {
         struct bpf_insn *insn = env->prog->insnsi;
-        int insn_cnt = env->prog->len;
+        const int insn_cnt = env->prog->len;
         struct bpf_insn insn_buf[16];
         struct bpf_prog *new_prog;
-        u32 cnt;
-        int i;
         enum bpf_access_type type;
+        int i, delta = 0;
 
         if (!env->prog->aux->ops->convert_ctx_access)
                 return 0;
 
         for (i = 0; i < insn_cnt; i++, insn++) {
+                u32 cnt;
+
                 if (insn->code == (BPF_LDX | BPF_MEM | BPF_W))
                         type = BPF_READ;
                 else if (insn->code == (BPF_STX | BPF_MEM | BPF_W))
@@ -2141,11 +2226,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 + delta].ptr_type != PTR_TO_CTX)
                         continue;
-                }
 
                 cnt = env->prog->aux->ops->
                         convert_ctx_access(type, insn->dst_reg, insn->src_reg,
@@ -2155,34 +2237,107 @@ static int convert_ctx_accesses(struct verifier_env *env)
                         return -EINVAL;
                 }
 
-                if (cnt == 1) {
-                        memcpy(insn, insn_buf, sizeof(*insn));
-                        continue;
-                }
-
-                /* several new insns need to be inserted. Make room for them */
-                insn_cnt += cnt - 1;
-                new_prog = bpf_prog_realloc(env->prog,
-                                            bpf_prog_size(insn_cnt),
-                                            GFP_USER);
+                new_prog = bpf_patch_insn_data(env, i + delta, insn_buf, cnt);
                 if (!new_prog)
                         return -ENOMEM;
 
-                new_prog->len = insn_cnt;
+                delta += cnt - 1;
 
-                memmove(new_prog->insnsi + i + cnt, new_prog->insns + i + 1,
-                        sizeof(*insn) * (insn_cnt - i - cnt));
+                /* keep walking new program and skip insns we just inserted */
+                env->prog = new_prog;
+                insn      = new_prog->insnsi + i + delta;
+        }
 
-                /* copy substitute insns in place of load instruction */
-                memcpy(new_prog->insnsi + i, insn_buf, sizeof(*insn) * cnt);
+        return 0;
+}
 
-                /* adjust branches in the whole program */
-                adjust_branches(new_prog, i, cnt - 1);
+/* fixup insn->imm field of bpf_call instructions
+ *
+ * this function is called after eBPF program passed verification
+ */
+static int fixup_bpf_calls(struct verifier_env *env)
+{
+        struct bpf_prog *prog = env->prog;
+        struct bpf_insn *insn = prog->insnsi;
+        const struct bpf_func_proto *fn;
+        const int insn_cnt = prog->len;
+        struct bpf_insn insn_buf[16];
+        struct bpf_prog *new_prog;
+        struct bpf_map *map_ptr;
+        int i, cnt, delta = 0;
 
-                /* keep walking new program and skip insns we just inserted */
-                env->prog = new_prog;
-                insn = new_prog->insnsi + i + cnt - 1;
-                i += cnt - 1;
+        for (i = 0; i < insn_cnt; i++, insn++) {
+                if (insn->code == (BPF_ALU | BPF_MOD | BPF_X) ||
+                    insn->code == (BPF_ALU | BPF_DIV | BPF_X)) {
+                        /* due to JIT bugs clear upper 32-bits of src register
+                         * before div/mod operation
+                         */
+                        insn_buf[0] = BPF_MOV32_REG(insn->src_reg, insn->src_reg);
+                        insn_buf[1] = *insn;
+                        cnt = 2;
+                        new_prog = bpf_patch_insn_data(env, i + delta, insn_buf, cnt);
+                        if (!new_prog)
+                                return -ENOMEM;
+
+                        delta    += cnt - 1;
+                        env->prog = prog = new_prog;
+                        insn      = new_prog->insnsi + i + delta;
+                        continue;
+                }
+
+                if (insn->code != (BPF_JMP | BPF_CALL))
+                        continue;
+
+                if (insn->imm == BPF_FUNC_get_route_realm)
+                        prog->dst_needed = 1;
+                if (insn->imm == BPF_FUNC_get_prandom_u32)
+                        bpf_user_rnd_init_once();
+                if (insn->imm == BPF_FUNC_tail_call) {
+                        /* mark bpf_tail_call as different opcode to avoid
+                         * conditional branch in the interpeter for every normal
+                         * call and to prevent accidental JITing by JIT compiler
+                         * that doesn't support bpf_tail_call yet
+                         */
+                        insn->imm = 0;
+                        insn->code |= BPF_X;
+
+                        /* instead of changing every JIT dealing with tail_call
+                         * emit two extra insns:
+                         * if (index >= max_entries) goto out;
+                         * index &= array->index_mask;
+                         * to avoid out-of-bounds cpu speculation
+                         */
+                        map_ptr = env->insn_aux_data[i + delta].map_ptr;
+                        if (!map_ptr->unpriv_array)
+                                continue;
+                        insn_buf[0] = BPF_JMP_IMM(BPF_JGE, BPF_REG_3,
+                                                  map_ptr->max_entries, 2);
+                        insn_buf[1] = BPF_ALU32_IMM(BPF_AND, BPF_REG_3,
+                                                    container_of(map_ptr,
+                                                                 struct bpf_array,
+                                                                 map)->index_mask);
+                        insn_buf[2] = *insn;
+                        cnt = 3;
+                        new_prog = bpf_patch_insn_data(env, i + delta, insn_buf, cnt);
+                        if (!new_prog)
+                                return -ENOMEM;
+
+                        delta    += cnt - 1;
+                        env->prog = prog = new_prog;
+                        insn      = new_prog->insnsi + i + delta;
+                        continue;
+                }
+
+                fn = prog->aux->ops->get_func_proto(insn->imm);
+                /* all functions that have prototype and verifier allowed
+                 * programs to call them, must be real in-kernel functions
+                 */
+                if (!fn->func) {
+                        verbose("kernel subsystem misconfigured func %d\n",
+                                insn->imm);
+                        return -EFAULT;
+                }
+                insn->imm = fn->func - __bpf_call_base;
         }
 
         return 0;
@@ -2226,6 +2381,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 */
@@ -2244,12 +2404,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;
         }
@@ -2278,9 +2438,15 @@ skip_full_check:
         free_states(env);
 
         if (ret == 0)
+                sanitize_dead_code(env);
+
+        if (ret == 0)
                 /* program is valid, convert *(u32*)(ctx + off) accesses */
                 ret = convert_ctx_accesses(env);
 
+        if (ret == 0)
+                ret = fixup_bpf_calls(env);
+
         if (log_level && log_len >= log_size - 1) {
                 BUG_ON(log_len >= log_size);
                 /* verifier log exceeded user supplied buffer */
@@ -2318,14 +2484,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;
 }