| lists.openwall.net | lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC | |
|
Open Source and information security mailing list archives
| ||
|
Message-ID: <20181231123114.024ff443@cakuba.hsd1.ca.comcast.net>
Date: Mon, 31 Dec 2018 12:31:14 -0800
From: Jakub Kicinski <jakub.kicinski@...ronome.com>
To: Yonghong Song <yhs@...com>
Cc: "alexei.starovoitov@...il.com" <alexei.starovoitov@...il.com>,
"daniel@...earbox.net" <daniel@...earbox.net>,
"netdev@...r.kernel.org" <netdev@...r.kernel.org>,
"oss-drivers@...ronome.com" <oss-drivers@...ronome.com>
Subject: Re: [RFC bpf-next v3 03/12] bpf: verifier: remove dead code
On Sun, 30 Dec 2018 22:02:10 +0000, Yonghong Song wrote:
> On 12/28/18 7:09 PM, Jakub Kicinski wrote:
> > +static int bpf_adj_linfo_after_remove(struct bpf_verifier_env *env, u32 off,
> > + u32 cnt)
> > +{
> > + struct bpf_subprog_info *need_first_linfo;
> > + 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 || !cnt)
> > + return 0;
> > +
> > + linfo = prog->aux->linfo;
> > +
> > + /* progs are already adjusted/removed, if program starts on off, it may
> > + * had its start cut off and its line info may need to be preserved
> > + */
> > + for (i = 0; i < env->subprog_cnt; i++)
> > + if (env->subprog_info[i].start >= off)
> > + break;
> > + if (i < env->subprog_cnt && env->subprog_info[i].start == off)
> > + need_first_linfo = &env->subprog_info[i];
> > + else
> > + need_first_linfo = NULL;
> > +
> > + /* find first line info to remove */
> > + for (i = 0; i < nr_linfo; i++)
> > + if (linfo[i].insn_off >= off)
> > + break;
> > +
> > + /* count lines to be removed */
> > + l_off = i;
> > + l_cnt = 0;
> > + for (; i < nr_linfo; i++)
> > + if (linfo[i].insn_off < off + cnt)
> > + l_cnt++;
> > + else
> > + break;
> > +
> > + /* either we didn't actually cut the start or we can just use line info
> > + * of first instruction if it exists
> > + */
> > + if (i < nr_linfo && linfo[i].insn_off == off + cnt)
> > + need_first_linfo = NULL;
> > + if (need_first_linfo) {
> > + if (WARN_ONCE(!l_cnt,
> > + "verifier bug - no linfo removed, yet its missing"))
> > + return -EINVAL;
> > + if (WARN_ONCE(need_first_linfo->linfo_idx < l_off ||
> > + need_first_linfo->linfo_idx >= l_off + l_cnt,
> > + "verifier bug - removed prog linfo not in removed range"))
> > + return -EINVAL;
> > + /* subprog linfo_idx is not adjusted yet, so just find out
> > + * which line it used to be and swap it
> > + */
> > + memmove(linfo + l_off, linfo + need_first_linfo->linfo_idx,
> > + sizeof(*linfo));
> > + need_first_linfo->linfo_idx = l_off;
> > + linfo[l_off].insn_off = off;
> > +
> > + l_off++;
> > + l_cnt--;
> > + }
>
> In this routine, we handle need_first_linfo if the first insn of a
> subprogram is deleted.
> I wonder whether we need to handle the last deleted linfo as well. For
> example:
> func1:
> line_info1:
> insn1
> insn2
> func2:
> line_info2:
> insn3
> insn4:
>
> if insn2 and insn3 are deleted, the above algorithm will produce:
> func1:
> line_info1:
> insn1
> func2:
> insn4
>
> func2 is missing the first line info, which should be line_info2 with
> adjusted insn offset to the start of func2.
Mm.. should not happen, we should end up with:
func1:
line_info1:
insn1
func2:
line_info2:
insn4
func2 after func adjust will start at off and there is no line info for
off + cnt (insn4), so we will preserve line_info2.
I've added the following test_btf test, just to be sure:
{
.descr = "line_info (dead end + subprog start w/ no linfo)",
.raw_types = {
BTF_TYPE_INT_ENC(NAME_TBD, BTF_INT_SIGNED, 0, 32, 4), /* [1] */
BTF_FUNC_PROTO_ENC(1, 1), /* [2] */
BTF_FUNC_PROTO_ARG_ENC(NAME_TBD, 1),
BTF_FUNC_ENC(NAME_TBD, 2), /* [3] */
BTF_FUNC_ENC(NAME_TBD, 2), /* [4] */
BTF_END_RAW,
},
BTF_STR_SEC("\0int\0x\0main\0func\0/* main linfo */\0/* func linfo */"),
.insns = {
BPF_MOV64_IMM(BPF_REG_0, 0),
BPF_JMP_IMM(BPF_JGE, BPF_REG_0, 1, 2), /* dead */
BPF_CALL_REL(2),
BPF_EXIT_INSN(),
BPF_EXIT_INSN(), /* dead */
/* func */
BPF_JMP_IMM(BPF_JA, 0, 0, 0), /* dead */
BPF_MOV64_IMM(BPF_REG_0, 0),
BPF_EXIT_INSN(),
},
.prog_type = BPF_PROG_TYPE_TRACEPOINT,
.func_info_cnt = 2,
.func_info_rec_size = 8,
.func_info = { {0, 3}, {5, 4}, },
.line_info = {
BPF_LINE_INFO_ENC(0, 0, NAME_TBD, 1, 10),
BPF_LINE_INFO_ENC(5, 0, NAME_TBD, 1, 10),
BTF_END_RAW,
},
.line_info_rec_size = sizeof(struct bpf_line_info),
.nr_jited_ksyms = 2,
},
~# bpftool prog dump xlated id 48
int main(int x):
; /* main linfo */
0: (b7) r0 = 0
1: (85) call pc+1#0xffffffffc041e782
2: (95) exit
int func(int x):
; /* func linfo */
3: (b7) r0 = 0
4: (95) exit
~# bpftool prog dump jited id 48
int main(int x):
0xffffffffc041cb2f:
; /* main linfo */
0: push %rbp
1: mov %rsp,%rbp
4: sub $0x28,%rsp
b: sub $0x28,%rbp
f: mov %rbx,0x0(%rbp)
13: mov %r13,0x8(%rbp)
17: mov %r14,0x10(%rbp)
1b: mov %r15,0x18(%rbp)
1f: xor %eax,%eax
21: mov %rax,0x20(%rbp)
25: xor %eax,%eax
27: callq 0x0000000000001c53
2c: mov 0x0(%rbp),%rbx
30: mov 0x8(%rbp),%r13
34: mov 0x10(%rbp),%r14
38: mov 0x18(%rbp),%r15
3c: add $0x28,%rbp
40: leaveq
41: retq
int func(int x):
0xffffffffc041e782:
; /* func linfo */
0: push %rbp
1: mov %rsp,%rbp
4: sub $0x28,%rsp
b: sub $0x28,%rbp
f: mov %rbx,0x0(%rbp)
13: mov %r13,0x8(%rbp)
17: mov %r14,0x10(%rbp)
1b: mov %r15,0x18(%rbp)
1f: xor %eax,%eax
21: mov %rax,0x20(%rbp)
25: xor %eax,%eax
27: mov 0x0(%rbp),%rbx
2b: mov 0x8(%rbp),%r13
2f: mov 0x10(%rbp),%r14
33: mov 0x18(%rbp),%r15
37: add $0x28,%rbp
3b: leaveq
3c: retq
> Another example:
> func1:
> line_info1:
> insn1
> insn2
> line_info2:
> insn3
> insn4
> If insn2 and insn3 are deleted, we will get
> func1:
> line_info1:
> insn1
> insn4
> This is not ideal either. We should attribute insn4 to line_info2.
Cool, I'm a little in the dark on what the definition of line info is,
so your suggestions are very much appreciated! If you're saying that
all instructions below line info are considered part of that "line",
that'd simplify the code.
So should I always preserve "last" line info if first live instruction
doesn't have one?
linfo1:
insn1
insn2 /* dead */
linfo2:
insn3 /* dead */
insn4
linfo3:
insn5
||
\/
linfo1:
insn1
linfo2:
insn4
linfo3:
insn5
That'd simplify things quite a bit!
> > +
> > + /* 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 + l_cnt)
> > + env->subprog_info[i].linfo_idx -= l_cnt;
> > +
> > + 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;
> > +
> > + if (!cnt)
> > + return 0;
>
> This check is probably not needed as all call sites (including
> patch #4) guarantees non-zero cnt.
Ack, thanks for the review, I was unsure if this is not convention.
Powered by blists - more mailing lists