Re: [PATCHv6 net-next 04/15] bpf: don't (ab)use instructions to store state
On 09/19/2016 11:48 PM, Jakub Kicinski wrote:
On Mon, 19 Sep 2016 23:44:50 +0200, Daniel Borkmann wrote:
On 09/19/2016 11:36 PM, Jakub Kicinski wrote:
On Mon, 19 Sep 2016 23:03:17 +0200, Daniel Borkmann wrote:
On 09/18/2016 05:09 PM, Jakub Kicinski wrote:
Storing state in reserved fields of instructions makes
it impossible to run verifier on programs already
marked as read-only. Allocate and use an array of
per-instruction state instead.
While touching the error path rename and move existing
jump target.
Suggested-by: Alexei Starovoitov
Signed-off-by: Jakub Kicinski
Acked-by: Alexei Starovoitov
Acked-by: Daniel Borkmann
I believe there's still an issue here. Could you please double check
and confirm?
I rebased my locally pending stuff on top of your set and suddenly my
test case breaks. So I did a bisect and it pointed me to this commit
eventually.
[...]
@@ -2697,11 +2706,8 @@ static int convert_ctx_accesses(struct verifier_env *env)
else
continue;
- if (insn->imm != PTR_TO_CTX) {
- /* clear internal mark */
- insn->imm = 0;
+ if (env->insn_aux_data[i].ptr_type != PTR_TO_CTX)
continue;
- }
cnt = env->prog->aux->ops->
convert_ctx_access(type, insn->dst_reg, insn->src_reg,
Looking at the code, I believe the issue is in above snippet. In the
convert_ctx_accesses() rewrite loop, each time we bpf_patch_insn_single()
a program, the program can grow in size (due to __sk_buff access rewrite,
for example). After rewrite, we do 'i += insn_delta' for adjustment to
process next insn.
However, env->insn_aux_data is alloced under the assumption that the
very initial, pre-verification prog->len doesn't change, right? So in
the above conversion access to env->insn_aux_data[i].ptr_type is off,
since after rewrites, corresponding mappings to ptr_type might not be
related anymore.
I noticed this with direct packet access where suddenly the data vs
data_end test failed and contained some "semi-random" value always
bailing out for me.
You are correct. Should I respin or would you like to post your set? :)
Heh, if you don't mind I would go ahead tonight, the conflict at two spots
when exposing verifier is really minor turns out. Are you okay with this?
Yes, please go ahead :)
Ok, thanks!
What's the plan wrt env->insn_aux_data? Realloc plus rewrite of the array,
or do you see a more straight forward solution?
I was thinking about something like this: (untested)
Yep, much better. :)
Re: [PATCHv6 net-next 04/15] bpf: don't (ab)use instructions to store state
On Mon, 19 Sep 2016 23:44:50 +0200, Daniel Borkmann wrote:
> On 09/19/2016 11:36 PM, Jakub Kicinski wrote:
> > On Mon, 19 Sep 2016 23:03:17 +0200, Daniel Borkmann wrote:
> >> On 09/18/2016 05:09 PM, Jakub Kicinski wrote:
> >>> Storing state in reserved fields of instructions makes
> >>> it impossible to run verifier on programs already
> >>> marked as read-only. Allocate and use an array of
> >>> per-instruction state instead.
> >>>
> >>> While touching the error path rename and move existing
> >>> jump target.
> >>>
> >>> Suggested-by: Alexei Starovoitov
> >>> Signed-off-by: Jakub Kicinski
> >>> Acked-by: Alexei Starovoitov
> >>> Acked-by: Daniel Borkmann
> >>
> >> I believe there's still an issue here. Could you please double check
> >> and confirm?
> >>
> >> I rebased my locally pending stuff on top of your set and suddenly my
> >> test case breaks. So I did a bisect and it pointed me to this commit
> >> eventually.
> >>
> >> [...]
> >>> @@ -2697,11 +2706,8 @@ static int convert_ctx_accesses(struct
> >>> verifier_env *env)
> >>> else
> >>> continue;
> >>>
> >>> - if (insn->imm != PTR_TO_CTX) {
> >>> - /* clear internal mark */
> >>> - insn->imm = 0;
> >>> + if (env->insn_aux_data[i].ptr_type != PTR_TO_CTX)
> >>> continue;
> >>> - }
> >>>
> >>> cnt = env->prog->aux->ops->
> >>> convert_ctx_access(type, insn->dst_reg,
> >>> insn->src_reg,
> >>
> >> Looking at the code, I believe the issue is in above snippet. In the
> >> convert_ctx_accesses() rewrite loop, each time we bpf_patch_insn_single()
> >> a program, the program can grow in size (due to __sk_buff access rewrite,
> >> for example). After rewrite, we do 'i += insn_delta' for adjustment to
> >> process next insn.
> >>
> >> However, env->insn_aux_data is alloced under the assumption that the
> >> very initial, pre-verification prog->len doesn't change, right? So in
> >> the above conversion access to env->insn_aux_data[i].ptr_type is off,
> >> since after rewrites, corresponding mappings to ptr_type might not be
> >> related anymore.
> >>
> >> I noticed this with direct packet access where suddenly the data vs
> >> data_end test failed and contained some "semi-random" value always
> >> bailing out for me.
> >
> > You are correct. Should I respin or would you like to post your set? :)
>
> Heh, if you don't mind I would go ahead tonight, the conflict at two spots
> when exposing verifier is really minor turns out. Are you okay with this?
Yes, please go ahead :)
> What's the plan wrt env->insn_aux_data? Realloc plus rewrite of the array,
> or do you see a more straight forward solution?
I was thinking about something like this: (untested)
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 1612f7364c42..5c4cae046251 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -2657,13 +2657,13 @@ static int convert_ctx_accesses(struct bpf_verifier_env
*env)
struct bpf_insn insn_buf[16];
struct bpf_prog *new_prog;
enum bpf_access_type type;
- int i;
+ int i, delta = 0;
if (!env->prog->aux->ops->convert_ctx_access)
return 0;
for (i = 0; i < insn_cnt; i++, insn++) {
- u32 insn_delta, cnt;
+ u32 cnt;
if (insn->code == (BPF_LDX | BPF_MEM | BPF_W) ||
insn->code == (BPF_LDX | BPF_MEM | BPF_DW))
@@ -2685,18 +2685,16 @@ static int convert_ctx_accesses(struct bpf_verifier_env
*env)
return -EINVAL;
}
- new_prog = bpf_patch_insn_single(env->prog, i, insn_buf, cnt);
+ new_prog = bpf_patch_insn_single(env->prog, i + delta, insn_buf,
+cnt);
if (!new_prog)
return -ENOMEM;
- insn_delta = cnt - 1;
+ delta += cnt - 1;
/* keep walking new program and skip insns we just inserted */
env->prog = new_prog;
- insn = new_prog->insnsi + i + insn_delta;
-
- insn_cnt += insn_delta;
- i+= insn_delta;
+ insn = new_prog->insnsi + i + delta;
}
return 0;
Re: [PATCHv6 net-next 04/15] bpf: don't (ab)use instructions to store state
On 09/19/2016 11:36 PM, Jakub Kicinski wrote:
On Mon, 19 Sep 2016 23:03:17 +0200, Daniel Borkmann wrote:
On 09/18/2016 05:09 PM, Jakub Kicinski wrote:
Storing state in reserved fields of instructions makes
it impossible to run verifier on programs already
marked as read-only. Allocate and use an array of
per-instruction state instead.
While touching the error path rename and move existing
jump target.
Suggested-by: Alexei Starovoitov
Signed-off-by: Jakub Kicinski
Acked-by: Alexei Starovoitov
Acked-by: Daniel Borkmann
I believe there's still an issue here. Could you please double check
and confirm?
I rebased my locally pending stuff on top of your set and suddenly my
test case breaks. So I did a bisect and it pointed me to this commit
eventually.
[...]
@@ -2697,11 +2706,8 @@ static int convert_ctx_accesses(struct verifier_env *env)
else
continue;
- if (insn->imm != PTR_TO_CTX) {
- /* clear internal mark */
- insn->imm = 0;
+ if (env->insn_aux_data[i].ptr_type != PTR_TO_CTX)
continue;
- }
cnt = env->prog->aux->ops->
convert_ctx_access(type, insn->dst_reg, insn->src_reg,
Looking at the code, I believe the issue is in above snippet. In the
convert_ctx_accesses() rewrite loop, each time we bpf_patch_insn_single()
a program, the program can grow in size (due to __sk_buff access rewrite,
for example). After rewrite, we do 'i += insn_delta' for adjustment to
process next insn.
However, env->insn_aux_data is alloced under the assumption that the
very initial, pre-verification prog->len doesn't change, right? So in
the above conversion access to env->insn_aux_data[i].ptr_type is off,
since after rewrites, corresponding mappings to ptr_type might not be
related anymore.
I noticed this with direct packet access where suddenly the data vs
data_end test failed and contained some "semi-random" value always
bailing out for me.
You are correct. Should I respin or would you like to post your set? :)
Heh, if you don't mind I would go ahead tonight, the conflict at two spots
when exposing verifier is really minor turns out. Are you okay with this?
What's the plan wrt env->insn_aux_data? Realloc plus rewrite of the array,
or do you see a more straight forward solution?
Re: [PATCHv6 net-next 04/15] bpf: don't (ab)use instructions to store state
On Mon, 19 Sep 2016 23:03:17 +0200, Daniel Borkmann wrote:
> Hi Jakub,
>
> On 09/18/2016 05:09 PM, Jakub Kicinski wrote:
> > Storing state in reserved fields of instructions makes
> > it impossible to run verifier on programs already
> > marked as read-only. Allocate and use an array of
> > per-instruction state instead.
> >
> > While touching the error path rename and move existing
> > jump target.
> >
> > Suggested-by: Alexei Starovoitov
> > Signed-off-by: Jakub Kicinski
> > Acked-by: Alexei Starovoitov
> > Acked-by: Daniel Borkmann
>
> I believe there's still an issue here. Could you please double check
> and confirm?
>
> I rebased my locally pending stuff on top of your set and suddenly my
> test case breaks. So I did a bisect and it pointed me to this commit
> eventually.
>
> [...]
> > @@ -2697,11 +2706,8 @@ static int convert_ctx_accesses(struct verifier_env
> > *env)
> > else
> > continue;
> >
> > - if (insn->imm != PTR_TO_CTX) {
> > - /* clear internal mark */
> > - insn->imm = 0;
> > + if (env->insn_aux_data[i].ptr_type != PTR_TO_CTX)
> > continue;
> > - }
> >
> > cnt = env->prog->aux->ops->
> > convert_ctx_access(type, insn->dst_reg, insn->src_reg,
>
> Looking at the code, I believe the issue is in above snippet. In the
> convert_ctx_accesses() rewrite loop, each time we bpf_patch_insn_single()
> a program, the program can grow in size (due to __sk_buff access rewrite,
> for example). After rewrite, we do 'i += insn_delta' for adjustment to
> process next insn.
>
> However, env->insn_aux_data is alloced under the assumption that the
> very initial, pre-verification prog->len doesn't change, right? So in
> the above conversion access to env->insn_aux_data[i].ptr_type is off,
> since after rewrites, corresponding mappings to ptr_type might not be
> related anymore.
>
> I noticed this with direct packet access where suddenly the data vs
> data_end test failed and contained some "semi-random" value always
> bailing out for me.
You are correct. Should I respin or would you like to post your set? :)
Re: [PATCHv6 net-next 04/15] bpf: don't (ab)use instructions to store state
Hi Jakub,
On 09/18/2016 05:09 PM, Jakub Kicinski wrote:
Storing state in reserved fields of instructions makes
it impossible to run verifier on programs already
marked as read-only. Allocate and use an array of
per-instruction state instead.
While touching the error path rename and move existing
jump target.
Suggested-by: Alexei Starovoitov
Signed-off-by: Jakub Kicinski
Acked-by: Alexei Starovoitov
Acked-by: Daniel Borkmann
I believe there's still an issue here. Could you please double check
and confirm?
I rebased my locally pending stuff on top of your set and suddenly my
test case breaks. So I did a bisect and it pointed me to this commit
eventually.
[...]
@@ -2697,11 +2706,8 @@ static int convert_ctx_accesses(struct verifier_env *env)
else
continue;
- if (insn->imm != PTR_TO_CTX) {
- /* clear internal mark */
- insn->imm = 0;
+ if (env->insn_aux_data[i].ptr_type != PTR_TO_CTX)
continue;
- }
cnt = env->prog->aux->ops->
convert_ctx_access(type, insn->dst_reg, insn->src_reg,
Looking at the code, I believe the issue is in above snippet. In the
convert_ctx_accesses() rewrite loop, each time we bpf_patch_insn_single()
a program, the program can grow in size (due to __sk_buff access rewrite,
for example). After rewrite, we do 'i += insn_delta' for adjustment to
process next insn.
However, env->insn_aux_data is alloced under the assumption that the
very initial, pre-verification prog->len doesn't change, right? So in
the above conversion access to env->insn_aux_data[i].ptr_type is off,
since after rewrites, corresponding mappings to ptr_type might not be
related anymore.
I noticed this with direct packet access where suddenly the data vs
data_end test failed and contained some "semi-random" value always
bailing out for me.
Thanks,
Daniel
[PATCHv6 net-next 04/15] bpf: don't (ab)use instructions to store state
Storing state in reserved fields of instructions makes
it impossible to run verifier on programs already
marked as read-only. Allocate and use an array of
per-instruction state instead.
While touching the error path rename and move existing
jump target.
Suggested-by: Alexei Starovoitov
Signed-off-by: Jakub Kicinski
Acked-by: Alexei Starovoitov
Acked-by: Daniel Borkmann
---
v3:
- new patch.
---
kernel/bpf/verifier.c | 51 ---
1 file changed, 32 insertions(+), 19 deletions(-)
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 90493a66..f5c1a4571331 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -181,6 +181,10 @@ struct verifier_stack_elem {
struct verifier_stack_elem *next;
};
+struct bpf_insn_aux_data {
+ enum bpf_reg_type ptr_type; /* pointer type for load/store insns */
+};
+
#define MAX_USED_MAPS 64 /* max number of maps accessed by one eBPF program */
/* single container for all structs
@@ -196,6 +200,7 @@ struct verifier_env {
u32 used_map_cnt; /* number of used maps */
u32 id_gen; /* used to generate unique reg IDs */
bool allow_ptr_leaks;
+ struct bpf_insn_aux_data *insn_aux_data; /* array of per-insn state */
};
#define BPF_COMPLEXITY_LIMIT_INSNS 65536
@@ -2334,7 +2339,7 @@ static int do_check(struct verifier_env *env)
return err;
} else if (class == BPF_LDX) {
- enum bpf_reg_type src_reg_type;
+ enum bpf_reg_type *prev_src_type, src_reg_type;
/* check for reserved fields is already done */
@@ -2364,16 +2369,18 @@ static int do_check(struct verifier_env *env)
continue;
}
- if (insn->imm == 0) {
+ prev_src_type = &env->insn_aux_data[insn_idx].ptr_type;
+
+ if (*prev_src_type == NOT_INIT) {
/* saw a valid insn
* dst_reg = *(u32 *)(src_reg + off)
-* use reserved 'imm' field to mark this insn
+* save type to validate intersecting paths
*/
- insn->imm = src_reg_type;
+ *prev_src_type = src_reg_type;
- } else if (src_reg_type != insn->imm &&
+ } else if (src_reg_type != *prev_src_type &&
(src_reg_type == PTR_TO_CTX ||
- insn->imm == PTR_TO_CTX)) {
+ *prev_src_type == PTR_TO_CTX)) {
/* ABuser program is trying to use the same insn
* dst_reg = *(u32*) (src_reg + off)
* with different pointer types:
@@ -2386,7 +2393,7 @@ static int do_check(struct verifier_env *env)
}
} else if (class == BPF_STX) {
- enum bpf_reg_type dst_reg_type;
+ enum bpf_reg_type *prev_dst_type, dst_reg_type;
if (BPF_MODE(insn->code) == BPF_XADD) {
err = check_xadd(env, insn);
@@ -2414,11 +2421,13 @@ static int do_check(struct verifier_env *env)
if (err)
return err;
- if (insn->imm == 0) {
- insn->imm = dst_reg_type;
- } else if (dst_reg_type != insn->imm &&
+ prev_dst_type = &env->insn_aux_data[insn_idx].ptr_type;
+
+ if (*prev_dst_type == NOT_INIT) {
+ *prev_dst_type = dst_reg_type;
+ } else if (dst_reg_type != *prev_dst_type &&
(dst_reg_type == PTR_TO_CTX ||
- insn->imm == PTR_TO_CTX)) {
+ *prev_dst_type == PTR_TO_CTX)) {
verbose("same insn cannot be used with
different pointers\n");
return -EINVAL;
}
@@ -2697,11 +2706,8 @@ static int convert_ctx_accesses(struct verifier_env *env)
else
continue;
- if (insn->imm != PTR_TO_CTX) {
- /* clear internal mark */
- insn->imm = 0;
+ if (env->insn_aux_data[i].ptr_type != PTR_TO_CTX)
continue;
- }
cnt = env->prog->aux->ops->
convert_ctx_access(type, insn->dst_reg, insn->src_reg,
@@ -2766,6 +2772,11 @@ int bpf_check(struct bpf_prog **prog, union bpf_attr
*attr)
