From: Alexei Starovoitov 'ops[i](x)' in C compiles to a load from a table of functions at a variable offset and then callx. A call of a method of a trait object in Rust compiles to the same code. At the load the verifier splits the state into N states, one for each function that the load can return. The states differ only in this register, but the verifier verifies the code from the load to callx N times. The states also count against the limit of 1024 states at one insn (BPF_FLOW_MAX_STATES). In a prog of rust-bpf (Rust compiled to BPF) fmt() of a trait object has 245 implementations. 3 states get to the load, and each adds 244 states. The result is 732 states at one insn. Do not split the state at the load. The register holds a pointer to one of N functions until an insn must know the function. before this patch r3 = *(u64 *)(r3 + 8) r3 = *(u64 *)(r3 + 8) / | \ | r3=f1 r3=f2 ... r3=fN r3 = one of f1 .. fN | | | | ... ... ... ... | | | | callx r3 callx r3 callx r3 callx r3 | | | / | \ f1 f2 fN f1 f2 ... fN callx verifies each function of the set. Thus the verifier verifies the same calls as before. The verifier log shows the register in this way: r3 = *(u64 *)(r3 +8) ; R3=func(one_of=245) The register holds the number of a set (func_set), and equal sets have the same number. Thus the code that compares states does not change. insn that must know the function what the verifier does -------------------------------- --------------------------------------- callx, func_is_on_its_own() A copy of the state of the caller waits for the exit states of the function. callx, other functions Each function gets a state at callx. call of a helper or a kfunc, Each function gets a state at the call. the pointer is an argument A callback is one function. func_is_on_its_own() is true for most functions. The verifier verifies such a function for the states at its entry, and not again for each caller. The copy that waits is not a state at an insn. Thus it does not count against the limit. Limitations: - Only the load makes a set. Two pointers to functions that come from two branches of a prog continue to be two states. - The verifier does not know that two copies of the pointer are equal. After 'r6 = r2; callx r2' a subsequent 'callx r6' verifies all N functions. Code that is dead only when the two calls go to the same function stays in the prog. In the prog above the largest number of states at one insn changes from 732 to 159. Signed-off-by: Alexei Starovoitov --- include/linux/bpf_verifier.h | 15 +++- kernel/bpf/log.c | 2 + kernel/bpf/verifier.c | 168 +++++++++++++++++++++++++++++------ 3 files changed, 158 insertions(+), 27 deletions(-) diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h index 0cd7fa277fe5..3bd2965e531e 100644 --- a/include/linux/bpf_verifier.h +++ b/include/linux/bpf_verifier.h @@ -121,7 +121,11 @@ struct bpf_reg_state { unsigned long raw2; } raw; - u32 subprogno; /* for PTR_TO_FUNC */ + struct { /* for PTR_TO_FUNC */ + u32 subprogno; + /* if not 0: one of env->func_sets[func_set - 1], subprogno is 0 */ + u32 func_set; + }; }; /* For scalar types (SCALAR_VALUE), this represents our knowledge of * the actual value. @@ -1036,6 +1040,9 @@ struct bpf_verifier_env { */ struct bpf_func_ptr *func_ptrs; u32 func_ptr_cnt; + /* What a pointer that was read from a table of functions may point to. */ + struct bpf_func_set **func_sets; + u32 func_set_cnt; bool has_callx; /* * Call graph edges created by callx instructions. A bitmap of @@ -1402,6 +1409,12 @@ static inline bool bpf_register_is_null(struct bpf_reg_state *reg) } bool bpf_map_is_rdonly(const struct bpf_map *map); +/* Sorted, no function is there twice */ +struct bpf_func_set { + u16 cnt; + u16 subprog[] __counted_by(cnt); +}; + struct bpf_func_ptr *bpf_map_func_ptrs(struct bpf_verifier_env *env, const struct bpf_map *map, u32 *cnt); struct bpf_func_ptr *bpf_map_range_func_ptrs(struct bpf_verifier_env *env, diff --git a/kernel/bpf/log.c b/kernel/bpf/log.c index 0013ab01e72d..3d26b0b7ed46 100644 --- a/kernel/bpf/log.c +++ b/kernel/bpf/log.c @@ -656,6 +656,8 @@ static void print_reg_state(struct bpf_verifier_env *env, verbose_a("parent_id=%d", reg->parent_id); if (type_is_non_owning_ref(reg->type)) verbose_a("%s", "non_own_ref"); + if (t == PTR_TO_FUNC && reg->func_set) + verbose_a("one_of=%d", env->func_sets[reg->func_set - 1]->cnt); if (type_is_map_ptr(t)) { if (reg->map_ptr->name[0]) verbose_a("map=%s", reg->map_ptr->name); diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index 21ea43422133..6c6980d74fd6 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -6935,7 +6935,52 @@ static void mark_reg_func_ptr(struct bpf_verifier_env *env, struct bpf_reg_state regs[regno].subprogno = subprog; } -/* a read from a table of functions branches into that many states at most */ +static int cmp_u16(const void *a, const void *b) +{ + return *(const u16 *)a - *(const u16 *)b; +} + +/* + * Pointers to functions have a join: the set of the functions. The states would differ in + * nothing else up to the call, and there every function of the set is verified. + * Equal sets have the same number, so registers are compared as they are. + */ +static int mark_reg_func_set(struct bpf_verifier_env *env, struct bpf_reg_state *regs, int regno, + u16 *subprogs, u32 cnt) +{ + struct bpf_func_set **sets, *set; + u32 i, n = 0; + + sort(subprogs, cnt, sizeof(*subprogs), cmp_u16, NULL); + for (i = 0; i < cnt; i++) + if (!n || subprogs[n - 1] != subprogs[i]) + subprogs[n++] = subprogs[i]; + mark_reg_func_ptr(env, regs, regno, n == 1 ? subprogs[0] : 0); + if (n == 1) + return 0; + + for (i = 0; i < env->func_set_cnt; i++) { + set = env->func_sets[i]; + if (set->cnt == n && !memcmp(set->subprog, subprogs, n * sizeof(*subprogs))) + break; + } + if (i == env->func_set_cnt) { + sets = krealloc_array(env->func_sets, i + 1, sizeof(*sets), GFP_KERNEL_ACCOUNT); + if (!sets) + return -ENOMEM; + env->func_sets = sets; + set = kzalloc_flex(*set, subprog, n, GFP_KERNEL_ACCOUNT); + if (!set) + return -ENOMEM; + set->cnt = n; + memcpy(set->subprog, subprogs, n * sizeof(*subprogs)); + sets[env->func_set_cnt++] = set; + } + regs[regno].func_set = i + 1; + return 0; +} + +/* a read from a table of functions yields one of that many at most */ #define BPF_MAX_FUNC_PTR_TARGETS BPF_MAX_SUBPROGS /* and that many pointers at most are next to what is read at variable offset */ #define BPF_MAX_FUNC_PTR_RANGE 4096 @@ -6968,7 +7013,7 @@ static u32 count_read_offsets(struct tnum offs, u64 min_off, u64 max_off, u32 li * is possible at, e.g. var_off is the stride of the elements of an array. * A read of exactly one pointer yields PTR_TO_FUNC. When the offset is variable * and only pointers can be read, which is how an element of a table of - * functions is loaded, the verification continues with each of them. Other + * functions is loaded, it is one of them, see mark_reg_func_set(). Other * reads that overlap with a pointer are rejected, because their result is not * known until the program is jitted. * @@ -6981,7 +7026,6 @@ static int check_func_ptr_read(struct bpf_verifier_env *env, struct bpf_reg_stat struct tnum offs = tnum_add(reg->var_off, tnum_const(off)); struct bpf_reg_state *regs = cur_regs(env); struct bpf_map *map = reg->map_ptr; - struct bpf_verifier_state *branch; u16 *targets __free(kfree) = NULL; struct bpf_func_ptr *ptrs; u32 i, cnt, n = 0; @@ -7032,16 +7076,7 @@ static int check_func_ptr_read(struct bpf_verifier_env *env, struct bpf_reg_stat if (err) return err; - for (i = 0; i < n - 1; i++) { - branch = push_stack(env, env->insn_idx + 1, env->insn_idx, - env->cur_state->speculative); - if (IS_ERR(branch)) - return PTR_ERR(branch); - mark_reg_func_ptr(env, branch->frame[branch->curframe]->regs, value_regno, - targets[i]); - } - mark_reg_func_ptr(env, regs, value_regno, targets[n - 1]); - return 0; + return mark_reg_func_set(env, regs, value_regno, targets, n); overlap: verbose(env, "read of %d bytes at offset [%llu,%llu] of map '%s' overlaps with a pointer to a function\n", @@ -11757,13 +11792,92 @@ static int check_func_call(struct bpf_verifier_env *env, struct bpf_insn *insn, * PTR_TO_FUNC register identifies the callee, so from here on callx is verified * as a direct call of that static subprog. */ +static int check_func_callx_one(struct bpf_verifier_env *env, int subprog, int *insn_idx) +{ + int err; + + err = btf_check_subprog_call(env, subprog); + if (err == -EFAULT) + return err; + + err = record_callx_edge(env, cur_func(env)->subprogno, subprog); + if (err) + return err; + + return check_static_func_call(env, subprog, insn_idx); +} + +/* The insn needs to know the function: go on with each function of the set. */ +static int split_func_set(struct bpf_verifier_env *env, int regno) +{ + struct bpf_reg_state *reg = reg_state(env, regno); + struct bpf_verifier_state *branch; + struct bpf_func_set *set; + u32 i; + + if (reg->type != PTR_TO_FUNC || !reg->func_set) + return 0; + set = env->func_sets[reg->func_set - 1]; + reg->func_set = 0; + for (i = 0; i < set->cnt; i++) { + reg->subprogno = set->subprog[i]; + if (i == set->cnt - 1) + break; + branch = push_stack(env, env->insn_idx, env->insn_idx, false); + if (IS_ERR(branch)) + return PTR_ERR(branch); + } + return 0; +} + +/* + * callx of one of the functions of a set. A function that is verified on its own + * gets a copy of the state that waits for it. Nothing meets at an insn. + */ +static int check_func_callx_set(struct bpf_verifier_env *env, int regno, int *insn_idx) +{ + struct bpf_verifier_state *cur = env->cur_state, *copy, *branch; + struct bpf_reg_state *reg = reg_state(env, regno); + struct bpf_func_set *set = env->func_sets[reg->func_set - 1]; + int err = 0; + u32 i; + + /* once, and not in every copy */ + account_current_path(env); + reg->func_set = 0; + for (i = 0; i < set->cnt && !err; i++) { + reg->subprogno = set->subprog[i]; + if (!func_is_on_its_own(env, cur, set->subprog[i])) { + branch = push_stack(env, *insn_idx, *insn_idx, false); + if (IS_ERR(branch)) + return PTR_ERR(branch); + continue; + } + copy = kzalloc_obj(*copy, GFP_KERNEL_ACCOUNT); + if (!copy) + return -ENOMEM; + err = bpf_copy_verifier_state(copy, cur); + if (!err) { + env->cur_state = copy; + err = check_func_callx_one(env, set->subprog[i], insn_idx); + env->cur_state = cur; + } + bpf_free_verifier_state(copy, true); + if (err == PROCESS_BPF_EXIT) + err = 0; + else if (verifier_bug_if(!err, env, "callx: func#%d doesn't wait", set->subprog[i])) + err = -EFAULT; + } + /* all that is to be done has a state of its own */ + return err ?: PROCESS_BPF_EXIT; +} + static int check_func_callx(struct bpf_verifier_env *env, struct bpf_insn *insn, int *insn_idx) { - struct bpf_func_state *caller = cur_func(env); struct bpf_reg_state *reg; const char *reason; - int err, subprog; + int err; err = check_reg_arg(env, insn->dst_reg, SRC_OP); if (err) @@ -11796,16 +11910,9 @@ static int check_func_callx(struct bpf_verifier_env *env, struct bpf_insn *insn, return err; /* PTR_TO_FUNC is a pointer to a static subprog */ - subprog = reg->subprogno; - err = btf_check_subprog_call(env, subprog); - if (err == -EFAULT) - return err; - - err = record_callx_edge(env, caller->subprogno, subprog); - if (err) - return err; - - return check_static_func_call(env, subprog, insn_idx); + if (reg->func_set) + return check_func_callx_set(env, insn->dst_reg, insn_idx); + return check_func_callx_one(env, reg->subprogno, insn_idx); } int map_set_for_each_callback_args(struct bpf_verifier_env *env, @@ -20484,7 +20591,7 @@ static void null_to_arena(struct bpf_verifier_env *env, int regno) static int do_check_insn(struct bpf_verifier_env *env, bool *do_print_state) { - int err; + int err, i; struct bpf_insn *insn = &env->prog->insnsi[env->insn_idx]; u8 class = BPF_CLASS(insn->code); @@ -20566,6 +20673,12 @@ static int do_check_insn(struct bpf_verifier_env *env, bool *do_print_state) return check_func_callx(env, insn, &env->insn_idx); if (insn->src_reg == BPF_PSEUDO_CALL) return check_func_call(env, insn, &env->insn_idx); + /* a callback is one function */ + for (i = BPF_REG_1; i <= BPF_REG_5; i++) { + err = split_func_set(env, i); + if (err) + return err; + } if (insn->src_reg == BPF_PSEUDO_KFUNC_CALL) return check_kfunc_call(env, insn, &env->insn_idx); return check_helper_call(env, insn, &env->insn_idx); @@ -24878,6 +24991,9 @@ int bpf_check(struct bpf_prog **prog, union bpf_attr *attr, bpfptr_t uattr, kvfree(env->gotox_tmp_buf); kvfree(env->callx_edges); kvfree(env->func_ptrs); + for (i = 0; i < env->func_set_cnt; i++) + kfree(env->func_sets[i]); + kfree(env->func_sets); bpf_diag_free(env); kvfree(env->idoms); kvfree(env); -- 2.55.0