| Message ID | 20190101013743.23935-4-jakub.kicinski@netronome.com |
|---|---|
| State | RFC, archived |
| Delegated to: | David Miller |
| Headers | show |
| Series | bpf: dead code elimination | expand |
On 12/31/18 5:37 PM, 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.kicinski@netronome.com> > --- > include/linux/filter.h | 1 + > kernel/bpf/core.c | 12 +++ > kernel/bpf/verifier.c | 167 ++++++++++++++++++++++++++++++++++++++++- > 3 files changed, 177 insertions(+), 3 deletions(-) > > diff --git a/include/linux/filter.h b/include/linux/filter.h > index 8c8544b375eb..2cdb50bbf867 100644 > --- a/include/linux/filter.h > +++ b/include/linux/filter.h > @@ -782,6 +782,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 a40057b2c556..cc6fa754627c 100644 > --- a/kernel/bpf/core.c > +++ b/kernel/bpf/core.c > @@ -461,6 +461,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 30e2cd399b4a..2f786acb65ce 100644 > --- a/kernel/bpf/verifier.c > +++ b/kernel/bpf/verifier.c > @@ -6233,6 +6233,141 @@ 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--; It is possible that j = env->subprog_cnt here. Looks like the following case is not properly covered: for func1: insn1 insn2 func2: insn3 insn4 case (1): insn3 removed case (2): insn3 and insn4 removed, func2 subprog_info should be remeoved. Maybe a change like below will work to include handling of the last subprog: - if (env->subprog_info[j].start != off + cnt) + if ((j == env->subprog_cnt && env->prog->len > off) || + (j < env->subprog_cnt && 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 */ > + 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, inherit */ > + if (prog->len != off && l_cnt && > + (i == nr_linfo || linfo[i].insn_off != off + cnt)) { > + l_cnt--; > + linfo[--i].insn_off = off + cnt; The same here. The handling the last line_info seems not sufficient. It depends on whether all insns covered by last linfo have been removed or not. Maybe something like below? + if (l_cnt && + ((i == nr_linfo && prog->len > off) || + (i < nr_linfo && linfo[i].insn_off != off + cnt))) { l_cnt--; linfo[--i].insn_off = off + cnt; Please double check whether my suggested fix is correct or not. You may want to add test cases to cover these cases as well. Thanks! > + } > + > + /* 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; > + } > + > + 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 > @@ -6293,6 +6428,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 > @@ -7032,11 +7191,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); >
On 02/01/19 05:25, Yonghong Song wrote: > On 12/31/18 5:37 PM, Jakub Kicinski wrote: >> +static int adjust_subprog_starts_after_remove(struct bpf_verifier_env *env, >> + u32 off, u32 cnt) Given how much trouble this seems to be causing, is it time for me to bring back my patches to replace subprog_starts with a subprogno field in struct bpf_insn_aux_data? Something similar could maybe be done with line_info, but only if the 'dead' line infos are left in prog->aux->linfo. Then each insn would store a linfo_no, and on output you'd only show the line info if it was different to the linfo_no of the previous insn. I haven't looked deeply enough into line info implementation to know if there's anything that would break. -Ed
On Wed, 2 Jan 2019 05:25:49 +0000, Yonghong Song wrote: > On 12/31/18 5:37 PM, 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.kicinski@netronome.com> > > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c > > index 30e2cd399b4a..2f786acb65ce 100644 > > --- a/kernel/bpf/verifier.c > > +++ b/kernel/bpf/verifier.c > > @@ -6233,6 +6233,141 @@ 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--; > > It is possible that j = env->subprog_cnt here. > > Looks like the following case is not properly covered: > for > func1: > insn1 > insn2 > func2: > insn3 > insn4 > > case (1): insn3 removed > case (2): insn3 and insn4 removed, func2 subprog_info should be remeoved. > > Maybe a change like below will work to include handling of the last subprog: > > - if (env->subprog_info[j].start != off + cnt) > + if ((j == env->subprog_cnt && env->prog->len > off) || > + (j < env->subprog_cnt && env->subprog_info[j].start != off + cnt)) > j--; As I think Ed alluded to there is another "exit" subprog at the env->subprog_cnt index. So accessing env->subprog_info[env->subprog_cnt] is correct (which is quite handy). test_verifier: "dead code: tail of main + two functions" should cover this. Would that make sense? > > +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, inherit */ > > + if (prog->len != off && l_cnt && > > + (i == nr_linfo || linfo[i].insn_off != off + cnt)) { > > + l_cnt--; > > + linfo[--i].insn_off = off + cnt; > > The same here. The handling the last line_info seems not sufficient. > It depends on whether all insns covered by last linfo have been removed > or not. > > Maybe something like below? > + if (l_cnt && > + ((i == nr_linfo && prog->len > off) || > + (i < nr_linfo && linfo[i].insn_off != off + cnt))) { > l_cnt--; > linfo[--i].insn_off = off + cnt; > > Please double check whether my suggested fix is correct or not. > You may want to add test cases to cover these cases as well. Hm.. We only need to "inherit" the linfo, if the first instruction after removed region doesn't have linfo. So if there are no instructions after the removed regions (we remove tail, off == prog->len) we can't possibly need to inherit. No? I think your code is correct (because if there is no code there can't be any linfo after, either) but I'm not sure why it would be necessary.
On 1/2/19 10:31 AM, Jakub Kicinski wrote: > On Wed, 2 Jan 2019 05:25:49 +0000, Yonghong Song wrote: >> On 12/31/18 5:37 PM, 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.kicinski@netronome.com> > >>> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c >>> index 30e2cd399b4a..2f786acb65ce 100644 >>> --- a/kernel/bpf/verifier.c >>> +++ b/kernel/bpf/verifier.c >>> @@ -6233,6 +6233,141 @@ 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--; >> >> It is possible that j = env->subprog_cnt here. >> >> Looks like the following case is not properly covered: >> for >> func1: >> insn1 >> insn2 >> func2: >> insn3 >> insn4 >> >> case (1): insn3 removed >> case (2): insn3 and insn4 removed, func2 subprog_info should be remeoved. >> >> Maybe a change like below will work to include handling of the last subprog: >> >> - if (env->subprog_info[j].start != off + cnt) >> + if ((j == env->subprog_cnt && env->prog->len > off) || >> + (j < env->subprog_cnt && env->subprog_info[j].start != off + cnt)) >> j--; > > As I think Ed alluded to there is another "exit" subprog at the > env->subprog_cnt index. So accessing env->subprog_info[env->subprog_cnt] > is correct (which is quite handy). test_verifier: "dead code: tail of > main + two functions" should cover this. Would that make sense? It does make sense. I did not know env->subprog_info[env->subprog_cnt] is valid. Have not carefully read generic verifier code for a long time :-(. Your current code is fine then. > >>> +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, inherit */ >>> + if (prog->len != off && l_cnt && >>> + (i == nr_linfo || linfo[i].insn_off != off + cnt)) { >>> + l_cnt--; >>> + linfo[--i].insn_off = off + cnt; >> >> The same here. The handling the last line_info seems not sufficient. >> It depends on whether all insns covered by last linfo have been removed >> or not. >> >> Maybe something like below? >> + if (l_cnt && >> + ((i == nr_linfo && prog->len > off) || >> + (i < nr_linfo && linfo[i].insn_off != off + cnt))) { >> l_cnt--; >> linfo[--i].insn_off = off + cnt; >> >> Please double check whether my suggested fix is correct or not. >> You may want to add test cases to cover these cases as well. > > Hm.. We only need to "inherit" the linfo, if the first instruction > after removed region doesn't have linfo. So if there are no > instructions after the removed regions (we remove tail, off == > prog->len) we can't possibly need to inherit. No? > > I think your code is correct (because if there is no code there can't > be any linfo after, either) but I'm not sure why it would be necessary. A little bit scrutiny shows two codes are equivalent. prog->len >= off is always true. if i < nr_linfo, prog->len > off must true since some insns after off will survive. So my code can transform to your code and vice versa. You are right. There is no need to change. Here prog->len is the length after dead insn removal. A little bit comment will help review and other people later code inspection. With that, you can add my Ack to patch 1-5. Acked-by: Yonghong Song <yhs@fb.com>
On Wed, 2 Jan 2019 18:57:01 +0000, Yonghong Song wrote: > Here prog->len is the length after dead insn removal. A little bit > comment will help review and other people later code inspection. Will do! > With that, you can add my Ack to patch 1-5. > Acked-by: Yonghong Song <yhs@fb.com> Thank you!
diff --git a/include/linux/filter.h b/include/linux/filter.h index 8c8544b375eb..2cdb50bbf867 100644 --- a/include/linux/filter.h +++ b/include/linux/filter.h @@ -782,6 +782,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 a40057b2c556..cc6fa754627c 100644 --- a/kernel/bpf/core.c +++ b/kernel/bpf/core.c @@ -461,6 +461,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 30e2cd399b4a..2f786acb65ce 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -6233,6 +6233,141 @@ 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 */ + 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, inherit */ + 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; + } + + 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 @@ -6293,6 +6428,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 @@ -7032,11 +7191,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);
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.kicinski@netronome.com> --- include/linux/filter.h | 1 + kernel/bpf/core.c | 12 +++ kernel/bpf/verifier.c | 167 ++++++++++++++++++++++++++++++++++++++++- 3 files changed, 177 insertions(+), 3 deletions(-)