On Sat, Jan 19, 2019 at 10:06:47AM -0800, Jakub Kicinski wrote:
> Instead of overwriting dead code with jmp -1 instructions
> remove it completely for root. Adjust verifier state and
> line info appropriately.
>
> v2:
> - adjust func_info (Alexei);
> - make sure first instruction retains line info (Alexei).
> v4: (Yonghong)
> - remove unnecessary if (!insn to remove) checks;
> - always keep last line info if first live instruction lacks one.
>
> Signed-off-by: Jakub Kicinski <jakub.kicin...@netronome.com>
> Acked-by: Yonghong Song <y...@fb.com>
> ---
> include/linux/filter.h | 1 +
> kernel/bpf/core.c | 12 +++
> kernel/bpf/verifier.c | 170 ++++++++++++++++++++++++++++++++++++++++-
> 3 files changed, 180 insertions(+), 3 deletions(-)
>
> diff --git a/include/linux/filter.h b/include/linux/filter.h
> index ad106d845b22..be9af6b4a9e4 100644
> --- a/include/linux/filter.h
> +++ b/include/linux/filter.h
> @@ -778,6 +778,7 @@ static inline bool bpf_dump_raw_ok(void)
>
> struct bpf_prog *bpf_patch_insn_single(struct bpf_prog *prog, u32 off,
> const struct bpf_insn *patch, u32 len);
> +int bpf_remove_insns(struct bpf_prog *prog, u32 off, u32 cnt);
>
> void bpf_clear_redirect_map(struct bpf_map *map);
>
> diff --git a/kernel/bpf/core.c b/kernel/bpf/core.c
> index ad08ba341197..2a81b8af3748 100644
> --- a/kernel/bpf/core.c
> +++ b/kernel/bpf/core.c
> @@ -462,6 +462,18 @@ struct bpf_prog *bpf_patch_insn_single(struct bpf_prog
> *prog, u32 off,
> return prog_adj;
> }
>
> +int bpf_remove_insns(struct bpf_prog *prog, u32 off, u32 cnt)
> +{
> + /* Branch offsets can't overflow when program is shrinking, no need
> + * to call bpf_adj_branches(..., true) here
> + */
> + memmove(prog->insnsi + off, prog->insnsi + off + cnt,
> + sizeof(struct bpf_insn) * (prog->len - off - cnt));
> + prog->len -= cnt;
> +
> + return WARN_ON_ONCE(bpf_adj_branches(prog, off, off + cnt, off, false));
> +}
> +
> void bpf_prog_kallsyms_del_subprogs(struct bpf_prog *fp)
> {
> int i;
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 71949c163b7a..fa8011409c51 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -6431,6 +6431,144 @@ static struct bpf_prog *bpf_patch_insn_data(struct
> bpf_verifier_env *env, u32 of
> return new_prog;
> }
>
> +static int adjust_subprog_starts_after_remove(struct bpf_verifier_env *env,
> + u32 off, u32 cnt)
> +{
> + int i, j;
> +
> + /* find first prog starting at or after off (first to remove) */
> + for (i = 0; i < env->subprog_cnt; i++)
> + if (env->subprog_info[i].start >= off)
> + break;
> + /* find first prog starting at or after off + cnt (first to stay) */
> + for (j = i; j < env->subprog_cnt; j++)
> + if (env->subprog_info[j].start >= off + cnt)
> + break;
> + /* if j doesn't start exactly at off + cnt, we are just removing
> + * the front of previous prog
> + */
> + if (env->subprog_info[j].start != off + cnt)
> + j--;
> +
> + if (j > i) {
> + struct bpf_prog_aux *aux = env->prog->aux;
> + int move;
> +
> + /* move fake 'exit' subprog as well */
> + move = env->subprog_cnt + 1 - j;
> +
> + memmove(env->subprog_info + i,
> + env->subprog_info + j,
> + sizeof(*env->subprog_info) * move);
> + env->subprog_cnt -= j - i;
> +
> + /* remove func_info */
It would be helpful to add a comment here to explain
that func_info->insn_off is set later in adjust_btf_func(),
so no need to adjust it here.
> + if (aux->func_info) {
> + move = aux->func_info_cnt - j;
> +
> + memmove(aux->func_info + i,
> + aux->func_info + j,
> + sizeof(*aux->func_info) * move);
> + aux->func_info_cnt -= j - i;
> + }
> + } else {
> + /* convert i from "first prog to remove" to "first to adjust" */
> + if (env->subprog_info[i].start == off)
> + i++;
> + }
> +
> + /* update fake 'exit' subprog as well */
> + for (; i <= env->subprog_cnt; i++)
> + env->subprog_info[i].start -= cnt;
> +
> + return 0;
> +}
> +
> +static int bpf_adj_linfo_after_remove(struct bpf_verifier_env *env, u32 off,
> + u32 cnt)
> +{
> + struct bpf_prog *prog = env->prog;
> + u32 i, l_off, l_cnt, nr_linfo;
> + struct bpf_line_info *linfo;
> +
> + nr_linfo = prog->aux->nr_linfo;
> + if (!nr_linfo)
> + return 0;
> +
> + linfo = prog->aux->linfo;
> +
> + /* find first line info to remove, count lines to be removed */
> + for (i = 0; i < nr_linfo; i++)
> + if (linfo[i].insn_off >= off)
> + break;
> +
> + l_off = i;
> + l_cnt = 0;
> + for (; i < nr_linfo; i++)
> + if (linfo[i].insn_off < off + cnt)
> + l_cnt++;
> + else
> + break;
> +
> + /* First live insn doesn't match first live linfo, it needs to "inherit"
> + * last removed linfo. prog is already modified, so prog->len == off
> + * means no live instructions after.
> + */
> + if (prog->len != off && l_cnt &&
> + (i == nr_linfo || linfo[i].insn_off != off + cnt)) {
> + l_cnt--;
> + linfo[--i].insn_off = off + cnt;
> + }
> +
> + /* remove the line info which refers to the removed instructions */
> + if (l_cnt) {
> + memmove(linfo + l_off, linfo + i,
> + sizeof(*linfo) * (nr_linfo - i));
> +
> + prog->aux->nr_linfo -= l_cnt;
> + nr_linfo = prog->aux->nr_linfo;
> + }
> +
> + /* pull all linfo[i].insn_off >= off + cnt in by cnt */
> + for (i = l_off; i < nr_linfo; i++)
> + linfo[i].insn_off -= cnt;
> +
> + /* fix up all subprogs (incl. 'exit') which start >= off */
> + for (i = 0; i <= env->subprog_cnt; i++)
> + if (env->subprog_info[i].linfo_idx > l_off) {
> + if (env->subprog_info[i].linfo_idx >= l_off + l_cnt)
> + env->subprog_info[i].linfo_idx -= l_cnt;
> + else
> + env->subprog_info[i].linfo_idx = l_off;
For l_off < linfo_idx < l_off + lcnt, had those subprog_info already been
removed in adjust_subprog_starts_after_remove()?
> + }
> +
> + return 0;
> +}
> +
> +static int verifier_remove_insns(struct bpf_verifier_env *env, u32 off, u32
> cnt)
> +{
> + struct bpf_insn_aux_data *aux_data = env->insn_aux_data;
> + unsigned int orig_prog_len = env->prog->len;
> + int err;
> +
> + err = bpf_remove_insns(env->prog, off, cnt);
> + if (err)
> + return err;
> +
> + err = adjust_subprog_starts_after_remove(env, off, cnt);
> + if (err)
> + return err;
> +
> + err = bpf_adj_linfo_after_remove(env, off, cnt);
> + if (err)
> + return err;
> +
> + memmove(aux_data + off, aux_data + off + cnt,
> + sizeof(*aux_data) * (orig_prog_len - off - cnt));
> +
> + return 0;
> +}
> +
> /* 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
> @@ -6491,6 +6629,30 @@ static void opt_hard_wire_dead_code_branches(struct
> bpf_verifier_env *env)
> }
> }
>
> +static int opt_remove_dead_code(struct bpf_verifier_env *env)
> +{
> + struct bpf_insn_aux_data *aux_data = env->insn_aux_data;
> + int insn_cnt = env->prog->len;
> + int i, err;
> +
> + for (i = 0; i < insn_cnt; i++) {
> + int j;
> +
> + j = 0;
> + while (i + j < insn_cnt && !aux_data[i + j].seen)
> + j++;
> + if (!j)
> + continue;
> +
> + err = verifier_remove_insns(env, i, j);
> + if (err)
> + return err;
> + insn_cnt = env->prog->len;
> + }
> +
> + return 0;
> +}
> +
> /* convert load instructions that access fields of a context type into a
> * sequence of instructions that access fields of the underlying structure:
> * struct __sk_buff -> struct sk_buff
> @@ -7281,11 +7443,13 @@ int bpf_check(struct bpf_prog **prog, union bpf_attr
> *attr,
> if (is_priv) {
> if (ret == 0)
> opt_hard_wire_dead_code_branches(env);
> + if (ret == 0)
> + ret = opt_remove_dead_code(env);
> + } else {
> + if (ret == 0)
> + sanitize_dead_code(env);
> }
>
> - if (ret == 0)
> - sanitize_dead_code(env);
> -
> if (ret == 0)
> /* program is valid, convert *(u32*)(ctx + off) accesses */
> ret = convert_ctx_accesses(env);
> --
> 2.19.2
>
