From: Qiliang Yuan The main loop of bpf_do_misc_fixups() patches divisions, may_goto, calls of helpers and more. It calls bpf_patch_insn_data() for each patch, and each call costs O(N) in a prog of N insns. Queue the patches in the patch list with bpf_patch_list_add(). One commit behind the loop, before the setup of the may_goto count, builds the new image in O(N + inserted insns). No insn moves while the loop runs. Thus the loop uses old indexes only: 'i + delta' becomes 'i'. Some patches end with a call of a helper. The code at patch_call_imm then writes the address of the helper to that call. It writes to the queued copy of the call, which bpf_patch_list_add() returns. Thus 'insn' can point into the list, and the loop sets it from the index before the next insn. The patch of may_goto goes to the target with a conditional jump, which has a 16-bit offset. When that offset is out of range, the patch uses 'gotol'. The loop selects the jump when it queues the patch, but the offset is final only at the commit. Each patch between may_goto and its target makes the offset longer by its growth. The growth of a patch is its length - 1. may_goto patches between it and its target offset that selects the jump -------- --------------------------------- ---------------------------- backward all are queued old offset - their growth forward none is queued old offset New may_goto_off() calculates the first row. In the second row the jump can get out of range at the commit. Then the load fails, as it does with bpf_patch_insn_data(). What users can see: - A jump that patches push out of its 16-bit range fails the load with -ERANGE, not with -ENOMEM. The message names the jump, not the patched insn: "insn %d cannot be patched due to 16-bit range". For a jump in a patch, as the one of may_goto, it names the insn that the patch replaces. - A backward may_goto that patches push beyond -32768 loads. Before this patch the load fails. Wall time of 'veristat -q ' in an x86_64 VM with 8 vCPUs, mean of 30 runs, before and after this patch: before after pyperf180 0.147 s 0.083 s pyperf600 0.430 s 0.219 s Signed-off-by: Qiliang Yuan Signed-off-by: Alexei Starovoitov --- kernel/bpf/fixups.c | 294 ++++++++++++++++++-------------------------- 1 file changed, 118 insertions(+), 176 deletions(-) diff --git a/kernel/bpf/fixups.c b/kernel/bpf/fixups.c index aee645cbb63b..0a5b35a00f9f 100644 --- a/kernel/bpf/fixups.c +++ b/kernel/bpf/fixups.c @@ -1969,18 +1969,21 @@ static int add_hidden_subprog(struct bpf_verifier_env *env, struct bpf_insn *pat /* * Expand may_goto: load the count from the stack, jump to the target of * may_goto when it is zero, then the tail that updates the count. - * Use gotol when the target is too far for 16-bit offset of a conditional jump. + * 'off' is the offset of may_goto, 'reach' how far it jumps once the patches + * queued so far are applied, see may_goto_off(). + * Use gotol when 'reach' is too far for 16-bit offset of a conditional jump. */ -static int may_goto_expand(struct bpf_insn *insn_buf, int off, int stack_off, - const struct bpf_insn *tail, int tail_cnt) +static int may_goto_expand(struct bpf_insn *insn_buf, int off, int reach, + int stack_off, const struct bpf_insn *tail, int tail_cnt) { int cnt = 0; /* Forward jump has to step over the tail */ off = off >= 0 ? off + tail_cnt : off - 1; + reach = reach >= 0 ? reach + tail_cnt : reach - 1; insn_buf[cnt++] = BPF_LDX_MEM(BPF_DW, BPF_REG_AX, BPF_REG_10, stack_off); - if (off == (s16)off) { + if (reach == (s16)reach) { insn_buf[cnt++] = BPF_JMP_IMM(BPF_JEQ, BPF_REG_AX, 0, off); } else { insn_buf[cnt++] = BPF_JMP_IMM(BPF_JNE, BPF_REG_AX, 0, 1); @@ -1990,6 +1993,27 @@ static int may_goto_expand(struct bpf_insn *insn_buf, int off, int stack_off, return cnt + tail_cnt; } +/* + * The offset of may_goto at 'idx' once the patches queued in front are applied. + * The patches that a forward may_goto jumps over aren't queued yet, so its + * offset stays as it is. + */ +static int may_goto_off(struct bpf_verifier_env *env, const struct bpf_insn *insn, + u32 idx) +{ + struct bpf_patch_list *pl = &env->patch_list; + u32 tgt = idx + insn->off + 1; + int off = insn->off; + u32 k = pl->cnt; + + if (off >= 0) + return off; + /* all queued patches are in front of idx */ + while (k > 0 && pl->patches[k - 1].off >= tgt) + off -= pl->patches[--k].len - 1; + return off; +} + /* Do various post-verification rewrites in a single program pass. * These rewrites simplify JIT and interpreter implementations. */ @@ -2006,7 +2030,7 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env) struct bpf_insn *insn_buf = env->insn_buf; struct bpf_prog *new_prog; struct bpf_map *map_ptr; - int i, ret, cnt, delta = 0, cur_subprog = 0; + int i, ret, cnt, cur_subprog = 0; struct bpf_subprog_info *subprogs = env->subprog_info; u16 stack_depth = subprogs[cur_subprog].stack_depth; u16 stack_depth_extra = 0; @@ -2038,7 +2062,7 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env) goto next_insn; } - if (env->insn_aux_data[i + delta].needs_zext) + if (env->insn_aux_data[i].needs_zext) /* Convert BPF_CLASS(insn->code) == BPF_ALU64 to 32-bit ALU */ insn->code = BPF_ALU | BPF_OP(insn->code) | BPF_SRC(insn->code); @@ -2061,13 +2085,9 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env) cnt = patch - insn_buf; - 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; + insn = bpf_patch_list_add(env, i, insn_buf, cnt); + if (IS_ERR(insn)) + return PTR_ERR(insn); goto next_insn; } @@ -2152,13 +2172,9 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env) cnt = patch - insn_buf; } - 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; + insn = bpf_patch_list_add(env, i, insn_buf, cnt); + if (IS_ERR(insn)) + return PTR_ERR(insn); goto next_insn; } @@ -2182,13 +2198,9 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env) *patch++ = BPF_MOV64_IMM(insn->dst_reg, 0); cnt = patch - insn_buf; - 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; + insn = bpf_patch_list_add(env, i, insn_buf, cnt); + if (IS_ERR(insn)) + return PTR_ERR(insn); goto next_insn; } @@ -2202,13 +2214,9 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env) return -EFAULT; } - 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; + insn = bpf_patch_list_add(env, i, insn_buf, cnt); + if (IS_ERR(insn)) + return PTR_ERR(insn); goto next_insn; } @@ -2221,7 +2229,7 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env) bool issrc, isneg, isimm; u32 off_reg; - aux = &env->insn_aux_data[i + delta]; + aux = &env->insn_aux_data[i]; if (!aux->alu_state || aux->alu_state == BPF_ALU_NON_POINTER) goto next_insn; @@ -2255,13 +2263,9 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env) *patch++ = BPF_ALU64_IMM(BPF_MUL, off_reg, -1); cnt = patch - insn_buf; - 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; + insn = bpf_patch_list_add(env, i, insn_buf, cnt); + if (IS_ERR(insn)) + return PTR_ERR(insn); goto next_insn; } @@ -2295,16 +2299,13 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env) * after subtraction, rinse and repeat. */ stack_depth_extra = 16; - cnt = may_goto_expand(insn_buf, insn->off, stack_off_cnt, - tail, ARRAY_SIZE(tail)); - - new_prog = bpf_patch_insn_data(env, i + delta, insn_buf, cnt); - if (!new_prog) - return -ENOMEM; + cnt = may_goto_expand(insn_buf, insn->off, + may_goto_off(env, insn, i), + stack_off_cnt, tail, ARRAY_SIZE(tail)); - delta += cnt - 1; - env->prog = prog = new_prog; - insn = new_prog->insnsi + i + delta; + insn = bpf_patch_list_add(env, i, insn_buf, cnt); + if (IS_ERR(insn)) + return PTR_ERR(insn); goto next_insn; } else if (bpf_is_may_goto_insn(insn)) { int stack_off = -stack_depth - 8; @@ -2314,16 +2315,13 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env) }; stack_depth_extra = 8; - cnt = may_goto_expand(insn_buf, insn->off, stack_off, - tail, ARRAY_SIZE(tail)); - - new_prog = bpf_patch_insn_data(env, i + delta, insn_buf, cnt); - if (!new_prog) - return -ENOMEM; + cnt = may_goto_expand(insn_buf, insn->off, + may_goto_off(env, insn, i), + stack_off, tail, ARRAY_SIZE(tail)); - delta += cnt - 1; - env->prog = prog = new_prog; - insn = new_prog->insnsi + i + delta; + insn = bpf_patch_list_add(env, i, insn_buf, cnt); + if (IS_ERR(insn)) + return PTR_ERR(insn); goto next_insn; } @@ -2333,7 +2331,7 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env) insn->src_reg == BPF_PSEUDO_MAP_IDX_VALUE)) { struct bpf_map *map; - aux = &env->insn_aux_data[i + delta]; + aux = &env->insn_aux_data[i]; map = env->used_maps[aux->map_index]; if (map->map_type != BPF_MAP_TYPE_PERCPU_ARRAY) goto next_insn; @@ -2344,7 +2342,7 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env) * We are *skipping* first half of ld_imm64 insn * with 'i++;', patching over second half of it * with that same half + mov64_percpu_reg insn. - * All because bpf_patch_insn_data() can only + * All because a patch can only * replace one 8-byte insn, which does not work * well for ld_imm64 insn. */ @@ -2354,13 +2352,9 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env) cnt = 2; i++; - 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; + insn = bpf_patch_list_add(env, i, insn_buf, cnt); + if (IS_ERR(insn)) + return PTR_ERR(insn); goto next_insn; } @@ -2369,19 +2363,15 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env) if (insn->src_reg == BPF_PSEUDO_CALL) goto next_insn; if (insn->src_reg == BPF_PSEUDO_KFUNC_CALL) { - ret = bpf_fixup_kfunc_call(env, insn, insn_buf, i + delta, &cnt); + ret = bpf_fixup_kfunc_call(env, insn, insn_buf, i, &cnt); if (ret) return ret; if (cnt == 0) goto next_insn; - 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; + insn = bpf_patch_list_add(env, i, insn_buf, cnt); + if (IS_ERR(insn)) + return PTR_ERR(insn); goto next_insn; } @@ -2420,7 +2410,7 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env) insn->imm = 0; insn->code = BPF_JMP | BPF_TAIL_CALL; - aux = &env->insn_aux_data[i + delta]; + aux = &env->insn_aux_data[i]; if (env->bpf_capable && !prog->blinding_requested && prog->jit_requested && !bpf_map_key_poisoned(aux) && @@ -2430,7 +2420,7 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env) .reason = BPF_POKE_REASON_TAIL_CALL, .tail_call.map = aux->map_ptr_state.map_ptr, .tail_call.key = bpf_map_key_immediate(aux), - .insn_idx = i + delta, + .insn_idx = i, }; ret = bpf_jit_add_poke_descriptor(prog, &desc); @@ -2466,17 +2456,13 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env) 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; + insn = bpf_patch_list_add(env, i, insn_buf, cnt); + if (IS_ERR(insn)) + return PTR_ERR(insn); goto next_insn; } - aux = &env->insn_aux_data[i + delta]; + aux = &env->insn_aux_data[i]; if (aux->arg_prog) { /* The verifier will process callback_fn as many times as necessary * with different maps and the register states prepared by @@ -2500,18 +2486,14 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env) 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; + insn = bpf_patch_list_add(env, i, insn_buf, cnt); + if (IS_ERR(insn)) + return PTR_ERR(insn); goto patch_call_imm; } /* bpf_per_cpu_ptr() and bpf_this_cpu_ptr() */ - if (env->insn_aux_data[i + delta].call_with_percpu_alloc_ptr) { + if (env->insn_aux_data[i].call_with_percpu_alloc_ptr) { /* patch with 'r1 = *(u64 *)(r1 + 0)' since for percpu data, * bpf_mem_alloc() returns a ptr to the percpu data ptr. */ @@ -2519,13 +2501,9 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env) 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; + insn = bpf_patch_list_add(env, i, insn_buf, cnt); + if (IS_ERR(insn)) + return PTR_ERR(insn); goto patch_call_imm; } @@ -2543,7 +2521,7 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env) insn->imm == BPF_FUNC_redirect_map || insn->imm == BPF_FUNC_for_each_map_elem || insn->imm == BPF_FUNC_map_lookup_percpu_elem)) { - aux = &env->insn_aux_data[i + delta]; + aux = &env->insn_aux_data[i]; if (bpf_map_ptr_poisoned(aux)) goto patch_call_imm; @@ -2562,14 +2540,9 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env) if (bpf_map_is_percpu_map(map_ptr->map_type)) prog->jit_required = true; - 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; + insn = bpf_patch_list_add(env, i, insn_buf, cnt); + if (IS_ERR(insn)) + return PTR_ERR(insn); goto next_insn; } @@ -2645,14 +2618,9 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env) BPF_REG_0, 0); 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; + insn = bpf_patch_list_add(env, i, insn_buf, cnt); + if (IS_ERR(insn)) + return PTR_ERR(insn); goto next_insn; } @@ -2675,13 +2643,9 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env) insn_buf[0] = BPF_ALU32_REG(BPF_XOR, BPF_REG_0, BPF_REG_0); cnt = 1; #endif - 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; + insn = bpf_patch_list_add(env, i, insn_buf, cnt); + if (IS_ERR(insn)) + return PTR_ERR(insn); goto next_insn; } @@ -2694,13 +2658,9 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env) insn_buf[2] = BPF_LDX_MEM(BPF_DW, BPF_REG_0, BPF_REG_0, 0); 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; + insn = bpf_patch_list_add(env, i, insn_buf, cnt); + if (IS_ERR(insn)) + return PTR_ERR(insn); goto next_insn; } #endif @@ -2728,13 +2688,9 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env) insn_buf[cnt++] = BPF_JMP_A(1); insn_buf[cnt++] = BPF_MOV64_IMM(BPF_REG_0, -EINVAL); - 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; + insn = bpf_patch_list_add(env, i, insn_buf, cnt); + if (IS_ERR(insn)) + return PTR_ERR(insn); goto next_insn; } @@ -2760,13 +2716,9 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env) cnt = 1; } - 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; + insn = bpf_patch_list_add(env, i, insn_buf, cnt); + if (IS_ERR(insn)) + return PTR_ERR(insn); goto next_insn; } @@ -2786,13 +2738,9 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env) 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; + insn = bpf_patch_list_add(env, i, insn_buf, cnt); + if (IS_ERR(insn)) + return PTR_ERR(insn); goto next_insn; } @@ -2802,12 +2750,9 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env) /* Load IP address from ctx - 16 */ insn_buf[0] = BPF_LDX_MEM(BPF_DW, BPF_REG_0, BPF_REG_1, -16); - new_prog = bpf_patch_insn_data(env, i + delta, insn_buf, 1); - if (!new_prog) - return -ENOMEM; - - env->prog = prog = new_prog; - insn = new_prog->insnsi + i + delta; + insn = bpf_patch_list_add(env, i, insn_buf, 1); + if (IS_ERR(insn)) + return PTR_ERR(insn); goto next_insn; } @@ -2857,13 +2802,9 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env) insn_buf[10] = BPF_MOV64_IMM(BPF_REG_0, -ENOENT); cnt = 11; - 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; + insn = bpf_patch_list_add(env, i, insn_buf, cnt); + if (IS_ERR(insn)) + return PTR_ERR(insn); goto next_insn; } @@ -2875,13 +2816,9 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env) insn_buf[1] = BPF_ATOMIC_OP(BPF_DW, BPF_XCHG, BPF_REG_1, BPF_REG_0, 0); 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; + insn = bpf_patch_list_add(env, i, insn_buf, cnt); + if (IS_ERR(insn)) + return PTR_ERR(insn); goto next_insn; } patch_call_imm: @@ -2897,7 +2834,7 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env) } insn->imm = BPF_CALL_IMM(fn->func); next_insn: - if (subprogs[cur_subprog + 1].start == i + delta + 1) { + if (subprogs[cur_subprog + 1].start == i + 1) { subprogs[cur_subprog].stack_depth += stack_depth_extra; subprogs[cur_subprog].stack_extra = stack_depth_extra; @@ -2912,9 +2849,14 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env) stack_depth_extra = 0; } i++; - insn++; + insn = &prog->insnsi[i]; } + ret = bpf_patch_list_commit(env); + if (ret) + return ret; + prog = env->prog; + env->prog->aux->stack_depth = subprogs[0].stack_depth; for (i = 0; i < env->subprog_cnt; i++) { int delta = bpf_jit_supports_timed_may_goto() ? 2 : 1; -- 2.55.0