[iovisor-dev] reminder: IO Visor TSC/Dev Meeting
Please join us tomorrow for our bi-weekly call. As usual, this meeting is open to everybody and completely optional. You might be interested to join if: You want to know what is going on in BPF land You are doing something interesting yourself with BPF and would like to share You want to know what the heck BPF is === IO Visor Dev/TSC Meeting === Every 2 weeks on Wednesday, from Wednesday, January 25, 2017, to no end date 11:00 am | Pacific Daylight Time (San Francisco, GMT-07:00) | 1 hr https://bluejeans.com/568677804/ https://www.timeanddate.com/worldclock/meetingdetails.html?year=2017&month=8&day=23&hour=18&min=0&sec=0&p1=900 ___ iovisor-dev mailing list iovisor-dev@lists.iovisor.org https://lists.iovisor.org/mailman/listinfo/iovisor-dev
Re: [iovisor-dev] [PATCH net-next 3/4] bpf/verifier: when pruning a branch, ignore its write marks
On 8/22/17 11:03 AM, Edward Cree wrote:
On 22/08/17 16:50, Edward Cree wrote:
On 22/08/17 16:24, Alexei Starovoitov wrote:
Do you have a test case for this by any chance?
I think something like
if (cond)
r0=0;
if (cond)
r0=0;
return r0;
might tickle the bug, but I'm not sure.
It turns out that (cond) has to be constructed not to alter our knowledge
of whatever register we're testing, but apart from that, this works.
{
"liveness pruning and write screening",
.insns = {
/* Get an unknown value */
BPF_LDX_MEM(BPF_W, BPF_REG_2, BPF_REG_1, 0),
/* branch conditions teach us nothing about R2 */
BPF_JMP_IMM(BPF_JGE, BPF_REG_2, 0, 1),
BPF_MOV64_IMM(BPF_REG_0, 0),
BPF_JMP_IMM(BPF_JGE, BPF_REG_2, 0, 1),
BPF_MOV64_IMM(BPF_REG_0, 0),
BPF_EXIT_INSN(),
},
.errstr = "R0 !read_ok",
.result = REJECT,
.prog_type = BPF_PROG_TYPE_LWT_IN,
},
This test fails on net-next, but passes with my patch.
I'll include it in the next spin of the series.
nice. thanks for the test!
___
iovisor-dev mailing list
iovisor-dev@lists.iovisor.org
https://lists.iovisor.org/mailman/listinfo/iovisor-dev
Re: [iovisor-dev] [PATCH net-next 3/4] bpf/verifier: when pruning a branch, ignore its write marks
On 22/08/17 16:50, Edward Cree wrote:
> On 22/08/17 16:24, Alexei Starovoitov wrote:
>> Do you have a test case for this by any chance?
> I think something like
> if (cond)
> r0=0;
> if (cond)
> r0=0;
> return r0;
> might tickle the bug, but I'm not sure.
It turns out that (cond) has to be constructed not to alter our knowledge
of whatever register we're testing, but apart from that, this works.
{
"liveness pruning and write screening",
.insns = {
/* Get an unknown value */
BPF_LDX_MEM(BPF_W, BPF_REG_2, BPF_REG_1, 0),
/* branch conditions teach us nothing about R2 */
BPF_JMP_IMM(BPF_JGE, BPF_REG_2, 0, 1),
BPF_MOV64_IMM(BPF_REG_0, 0),
BPF_JMP_IMM(BPF_JGE, BPF_REG_2, 0, 1),
BPF_MOV64_IMM(BPF_REG_0, 0),
BPF_EXIT_INSN(),
},
.errstr = "R0 !read_ok",
.result = REJECT,
.prog_type = BPF_PROG_TYPE_LWT_IN,
},
This test fails on net-next, but passes with my patch.
I'll include it in the next spin of the series.
___
iovisor-dev mailing list
iovisor-dev@lists.iovisor.org
https://lists.iovisor.org/mailman/listinfo/iovisor-dev
Re: [iovisor-dev] [PATCH net-next 4/4] bpf/verifier: document liveness analysis
On 8/22/17 8:55 AM, Edward Cree wrote:
On 22/08/17 16:42, Alexei Starovoitov wrote:
On 8/22/17 6:27 AM, Edward Cree wrote:
static bool do_propagate_liveness(const struct bpf_verifier_state *state,
struct bpf_verifier_state *parent)
{
@@ -3457,6 +3463,15 @@ static bool do_propagate_liveness(const struct
bpf_verifier_state *state,
return touched;
}
+/* "parent" is "a state from which we reach the current state", but initially
+ * it is not the state->parent (i.e. "the state whose straight-line code leads
+ * to the current state"), instead it is the state that happened to arrive at
+ * a (prunable) equivalent of the current state. See comment above
+ * do_propagate_liveness() for consequences of this.
+ * This function is just a more efficient way of calling mark_reg_read() or
+ * mark_stack_slot_read() on each reg in "parent" that is read in "state", so
+ * long as parent != state->parent.
+ */
i'm confused with 'so long as parent != state->parent' which implies
looping and multiple iterations, whereas 'parent != state->parent'
condition is true only for the first iteration of
'while (do_propagate_liveness(state, parent))' loop.
right ?
I phrased it badly. I mean that, the statement "this function is just a
way to mark_reg_read() all the things" is true only "so long as" (i.e.
under the condition) parent != state->parent.
got it.
How about
/* This function is just a more efficient way of calling mark_reg_read() or
* mark_stack_slot_read() on each reg in "parent" that is read in "state",
* though it requires that parent != state->parent in the call arguments.
*/
Thanks. It's more clear to me. Ack
___
iovisor-dev mailing list
iovisor-dev@lists.iovisor.org
https://lists.iovisor.org/mailman/listinfo/iovisor-dev
Re: [iovisor-dev] [PATCH net-next 4/4] bpf/verifier: document liveness analysis
On 22/08/17 16:42, Alexei Starovoitov wrote:
> On 8/22/17 6:27 AM, Edward Cree wrote:
>> static bool do_propagate_liveness(const struct bpf_verifier_state *state,
>>struct bpf_verifier_state *parent)
>> {
>> @@ -3457,6 +3463,15 @@ static bool do_propagate_liveness(const struct
>> bpf_verifier_state *state,
>> return touched;
>> }
>>
>> +/* "parent" is "a state from which we reach the current state", but
>> initially
>> + * it is not the state->parent (i.e. "the state whose straight-line code
>> leads
>> + * to the current state"), instead it is the state that happened to arrive
>> at
>> + * a (prunable) equivalent of the current state. See comment above
>> + * do_propagate_liveness() for consequences of this.
>> + * This function is just a more efficient way of calling mark_reg_read() or
>> + * mark_stack_slot_read() on each reg in "parent" that is read in "state",
>> so
>> + * long as parent != state->parent.
>> + */
>
> i'm confused with 'so long as parent != state->parent' which implies
> looping and multiple iterations, whereas 'parent != state->parent'
> condition is true only for the first iteration of
> 'while (do_propagate_liveness(state, parent))' loop.
> right ?
I phrased it badly. I mean that, the statement "this function is just a
way to mark_reg_read() all the things" is true only "so long as" (i.e.
under the condition) parent != state->parent.
How about
/* This function is just a more efficient way of calling mark_reg_read() or
* mark_stack_slot_read() on each reg in "parent" that is read in "state",
* though it requires that parent != state->parent in the call arguments.
*/
?
___
iovisor-dev mailing list
iovisor-dev@lists.iovisor.org
https://lists.iovisor.org/mailman/listinfo/iovisor-dev
Re: [iovisor-dev] [PATCH net-next 3/4] bpf/verifier: when pruning a branch, ignore its write marks
On 22/08/17 16:24, Alexei Starovoitov wrote:
> On 8/22/17 6:27 AM, Edward Cree wrote:
>> The fact that writes occurred in reaching the continuation state does
>> not screen off its reads from us, because we're not really its parent.
>> So detect 'not really the parent' in do_propagate_liveness, and ignore
>> write marks in that case.
>>
>> Fixes: dc503a8ad984 ("bpf/verifier: track liveness for pruning")
>> Signed-off-by: Edward Cree
>> ---
>> kernel/bpf/verifier.c | 9 +++--
>> 1 file changed, 7 insertions(+), 2 deletions(-)
>>
>> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
>> index 1e3f56c..711bdbd 100644
>> --- a/kernel/bpf/verifier.c
>> +++ b/kernel/bpf/verifier.c
>> @@ -3420,6 +3420,7 @@ static bool states_equal(struct bpf_verifier_env *env,
>> static bool do_propagate_liveness(const struct bpf_verifier_state *state,
>>struct bpf_verifier_state *parent)
>> {
>> +bool writes = parent == state->parent; /* Observe write marks */
>> bool touched = false; /* any changes made? */
>> int i;
>>
>> @@ -3431,7 +3432,9 @@ static bool do_propagate_liveness(const struct
>> bpf_verifier_state *state,
>> for (i = 0; i < BPF_REG_FP; i++) {
>> if (parent->regs[i].live & REG_LIVE_READ)
>> continue;
>> -if (state->regs[i].live == REG_LIVE_READ) {
>> +if (writes && (state->regs[i].live & REG_LIVE_WRITTEN))
>> +continue;
>> +if (state->regs[i].live & REG_LIVE_READ) {
>
> makes sense to me.
> if i understand correctly it not only should make the liveness marking
> correct, but improve the numbers, since smaller number of states
> will have READ marks.
Other way round; it means we sometimes ignore WRITTEN marks, so more states
get READ marks. On the cilium progs, the bpf_lxc.o get about 100 extra
insns processed, the others are unchanged.
> Do you have a test case for this by any chance?
I haven't constructed one; my test was just to put in some debug code that
checked on each propagate_liveness call whether there were any write marks
in the first state.
I think something like
if (cond)
r0=0;
if (cond)
r0=0;
return r0;
might tickle the bug, but I'm not sure.
___
iovisor-dev mailing list
iovisor-dev@lists.iovisor.org
https://lists.iovisor.org/mailman/listinfo/iovisor-dev
Re: [iovisor-dev] [PATCH net-next 4/4] bpf/verifier: document liveness analysis
On 8/22/17 6:27 AM, Edward Cree wrote:
The liveness tracking algorithm is quite subtle; add comments to explain it.
Signed-off-by: Edward Cree
---
include/linux/bpf_verifier.h | 13 +
kernel/bpf/verifier.c| 28 +++-
2 files changed, 40 insertions(+), 1 deletion(-)
diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index d8f131a..b8d200f 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -21,6 +21,19 @@
*/
#define BPF_MAX_VAR_SIZINT_MAX
+/* Liveness marks, used for registers and spilled-regs (in stack slots).
+ * Read marks propagate upwards until they find a write mark; they record that
+ * "one of this state's descendants read this reg" (and therefore the reg is
+ * relevant for states_equal() checks).
+ * Write marks collect downwards and do not propagate; they record that "the
+ * straight-line code that reached this state (from its parent) wrote this reg"
+ * (and therefore that reads propagated from this state or its descendants
+ * should not propagate to its parent).
+ * A state with a write mark can receive read marks; it just won't propagate
+ * them to its parent, since the write mark is a property, not of the state,
+ * but of the link between it and its parent. See mark_reg_read() and
+ * mark_stack_slot_read() in kernel/bpf/verifier.c.
+ */
+1
enum bpf_reg_liveness {
REG_LIVE_NONE = 0, /* reg hasn't been read or written this branch */
REG_LIVE_READ, /* reg was read, so we're sensitive to initial value */
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 711bdbd..5fc350e 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -3417,6 +3417,12 @@ static bool states_equal(struct bpf_verifier_env *env,
return ret;
}
+/* A write screens off any subsequent reads; but write marks come from the
+ * straight-line code between a state and its parent. When we arrive at a
+ * jump target (in the first iteration of the propagate_liveness() loop),
+ * we didn't arrive by the straight-line code, so read marks in state must
+ * propagate to parent regardless of state's write marks.
+ */
+1
static bool do_propagate_liveness(const struct bpf_verifier_state *state,
struct bpf_verifier_state *parent)
{
@@ -3457,6 +3463,15 @@ static bool do_propagate_liveness(const struct
bpf_verifier_state *state,
return touched;
}
+/* "parent" is "a state from which we reach the current state", but initially
+ * it is not the state->parent (i.e. "the state whose straight-line code leads
+ * to the current state"), instead it is the state that happened to arrive at
+ * a (prunable) equivalent of the current state. See comment above
+ * do_propagate_liveness() for consequences of this.
+ * This function is just a more efficient way of calling mark_reg_read() or
+ * mark_stack_slot_read() on each reg in "parent" that is read in "state", so
+ * long as parent != state->parent.
+ */
i'm confused with 'so long as parent != state->parent' which implies
looping and multiple iterations, whereas 'parent != state->parent'
condition is true only for the first iteration of
'while (do_propagate_liveness(state, parent))' loop.
right ?
static void propagate_liveness(const struct bpf_verifier_state *state,
struct bpf_verifier_state *parent)
{
@@ -3485,6 +3500,12 @@ static int is_state_visited(struct bpf_verifier_env
*env, int insn_idx)
/* reached equivalent register/stack state,
* prune the search.
* Registers read by the continuation are read by us.
+* If we have any write marks in env->cur_state, they
+* will prevent corresponding reads in the continuation
+* from reaching our parent (an explored_state). Our
+* own state will get the read marks recorded, but
+* they'll be immediately forgotten as we're pruning
+* this state and will pop a new one.
*/
+1
propagate_liveness(&sl->state, &env->cur_state);
return 1;
@@ -3508,7 +3529,12 @@ static int is_state_visited(struct bpf_verifier_env
*env, int insn_idx)
env->explored_states[insn_idx] = new_sl;
/* connect new state to parentage chain */
env->cur_state.parent = &new_sl->state;
- /* clear liveness marks in current state */
+ /* clear write marks in current state: the writes we did are not writes
+* our child did, so they don't screen off its reads from us.
+* (There are no read marks in current state, because reads always mark
+* their parent and current state never has children yet. Only
+* explored_states can get read marks.)
+*/
+1
for (i = 0; i < BPF_REG_FP
Re: [iovisor-dev] [PATCH net-next 3/4] bpf/verifier: when pruning a branch, ignore its write marks
On 8/22/17 6:27 AM, Edward Cree wrote:
The fact that writes occurred in reaching the continuation state does
not screen off its reads from us, because we're not really its parent.
So detect 'not really the parent' in do_propagate_liveness, and ignore
write marks in that case.
Fixes: dc503a8ad984 ("bpf/verifier: track liveness for pruning")
Signed-off-by: Edward Cree
---
kernel/bpf/verifier.c | 9 +++--
1 file changed, 7 insertions(+), 2 deletions(-)
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 1e3f56c..711bdbd 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -3420,6 +3420,7 @@ static bool states_equal(struct bpf_verifier_env *env,
static bool do_propagate_liveness(const struct bpf_verifier_state *state,
struct bpf_verifier_state *parent)
{
+ bool writes = parent == state->parent; /* Observe write marks */
bool touched = false; /* any changes made? */
int i;
@@ -3431,7 +3432,9 @@ static bool do_propagate_liveness(const struct
bpf_verifier_state *state,
for (i = 0; i < BPF_REG_FP; i++) {
if (parent->regs[i].live & REG_LIVE_READ)
continue;
- if (state->regs[i].live == REG_LIVE_READ) {
+ if (writes && (state->regs[i].live & REG_LIVE_WRITTEN))
+ continue;
+ if (state->regs[i].live & REG_LIVE_READ) {
makes sense to me.
if i understand correctly it not only should make the liveness marking
correct, but improve the numbers, since smaller number of states
will have READ marks.
Do you have a test case for this by any chance?
Acked-by: Alexei Starovoitov
___
iovisor-dev mailing list
iovisor-dev@lists.iovisor.org
https://lists.iovisor.org/mailman/listinfo/iovisor-dev
Re: [iovisor-dev] [PATCH net-next 2/4] bpf/verifier: remove varlen_map_value_access flag
On 8/22/17 6:26 AM, Edward Cree wrote:
The optimisation it does is broken when the 'new' register value has a
variable offset and the 'old' was constant. I broke it with my pointer
types unification (see Fixes tag below), before which the 'new' value
would have type PTR_TO_MAP_VALUE_ADJ and would thus not compare equal;
other changes in that patch mean that its original behaviour (ignore
min/max values) cannot be restored.
Tests on a sample set of cilium programs show no change in count of
processed instructions.
Fixes: f1174f77b50c ("bpf/verifier: rework value tracking")
Signed-off-by: Edward Cree
Acked-by: Alexei Starovoitov
___
iovisor-dev mailing list
iovisor-dev@lists.iovisor.org
https://lists.iovisor.org/mailman/listinfo/iovisor-dev
[iovisor-dev] [PATCH net-next 4/4] bpf/verifier: document liveness analysis
The liveness tracking algorithm is quite subtle; add comments to explain it.
Signed-off-by: Edward Cree
---
include/linux/bpf_verifier.h | 13 +
kernel/bpf/verifier.c| 28 +++-
2 files changed, 40 insertions(+), 1 deletion(-)
diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index d8f131a..b8d200f 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -21,6 +21,19 @@
*/
#define BPF_MAX_VAR_SIZINT_MAX
+/* Liveness marks, used for registers and spilled-regs (in stack slots).
+ * Read marks propagate upwards until they find a write mark; they record that
+ * "one of this state's descendants read this reg" (and therefore the reg is
+ * relevant for states_equal() checks).
+ * Write marks collect downwards and do not propagate; they record that "the
+ * straight-line code that reached this state (from its parent) wrote this reg"
+ * (and therefore that reads propagated from this state or its descendants
+ * should not propagate to its parent).
+ * A state with a write mark can receive read marks; it just won't propagate
+ * them to its parent, since the write mark is a property, not of the state,
+ * but of the link between it and its parent. See mark_reg_read() and
+ * mark_stack_slot_read() in kernel/bpf/verifier.c.
+ */
enum bpf_reg_liveness {
REG_LIVE_NONE = 0, /* reg hasn't been read or written this branch */
REG_LIVE_READ, /* reg was read, so we're sensitive to initial value */
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 711bdbd..5fc350e 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -3417,6 +3417,12 @@ static bool states_equal(struct bpf_verifier_env *env,
return ret;
}
+/* A write screens off any subsequent reads; but write marks come from the
+ * straight-line code between a state and its parent. When we arrive at a
+ * jump target (in the first iteration of the propagate_liveness() loop),
+ * we didn't arrive by the straight-line code, so read marks in state must
+ * propagate to parent regardless of state's write marks.
+ */
static bool do_propagate_liveness(const struct bpf_verifier_state *state,
struct bpf_verifier_state *parent)
{
@@ -3457,6 +3463,15 @@ static bool do_propagate_liveness(const struct
bpf_verifier_state *state,
return touched;
}
+/* "parent" is "a state from which we reach the current state", but initially
+ * it is not the state->parent (i.e. "the state whose straight-line code leads
+ * to the current state"), instead it is the state that happened to arrive at
+ * a (prunable) equivalent of the current state. See comment above
+ * do_propagate_liveness() for consequences of this.
+ * This function is just a more efficient way of calling mark_reg_read() or
+ * mark_stack_slot_read() on each reg in "parent" that is read in "state", so
+ * long as parent != state->parent.
+ */
static void propagate_liveness(const struct bpf_verifier_state *state,
struct bpf_verifier_state *parent)
{
@@ -3485,6 +3500,12 @@ static int is_state_visited(struct bpf_verifier_env
*env, int insn_idx)
/* reached equivalent register/stack state,
* prune the search.
* Registers read by the continuation are read by us.
+* If we have any write marks in env->cur_state, they
+* will prevent corresponding reads in the continuation
+* from reaching our parent (an explored_state). Our
+* own state will get the read marks recorded, but
+* they'll be immediately forgotten as we're pruning
+* this state and will pop a new one.
*/
propagate_liveness(&sl->state, &env->cur_state);
return 1;
@@ -3508,7 +3529,12 @@ static int is_state_visited(struct bpf_verifier_env
*env, int insn_idx)
env->explored_states[insn_idx] = new_sl;
/* connect new state to parentage chain */
env->cur_state.parent = &new_sl->state;
- /* clear liveness marks in current state */
+ /* clear write marks in current state: the writes we did are not writes
+* our child did, so they don't screen off its reads from us.
+* (There are no read marks in current state, because reads always mark
+* their parent and current state never has children yet. Only
+* explored_states can get read marks.)
+*/
for (i = 0; i < BPF_REG_FP; i++)
env->cur_state.regs[i].live = REG_LIVE_NONE;
for (i = 0; i < MAX_BPF_STACK / BPF_REG_SIZE; i++)
___
iovisor-dev mailing list
iovisor-dev@lists.iovisor.org
https://lists.iovisor.org/mailman/listinfo/iovisor-dev
[iovisor-dev] [PATCH net-next 3/4] bpf/verifier: when pruning a branch, ignore its write marks
The fact that writes occurred in reaching the continuation state does
not screen off its reads from us, because we're not really its parent.
So detect 'not really the parent' in do_propagate_liveness, and ignore
write marks in that case.
Fixes: dc503a8ad984 ("bpf/verifier: track liveness for pruning")
Signed-off-by: Edward Cree
---
kernel/bpf/verifier.c | 9 +++--
1 file changed, 7 insertions(+), 2 deletions(-)
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 1e3f56c..711bdbd 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -3420,6 +3420,7 @@ static bool states_equal(struct bpf_verifier_env *env,
static bool do_propagate_liveness(const struct bpf_verifier_state *state,
struct bpf_verifier_state *parent)
{
+ bool writes = parent == state->parent; /* Observe write marks */
bool touched = false; /* any changes made? */
int i;
@@ -3431,7 +3432,9 @@ static bool do_propagate_liveness(const struct
bpf_verifier_state *state,
for (i = 0; i < BPF_REG_FP; i++) {
if (parent->regs[i].live & REG_LIVE_READ)
continue;
- if (state->regs[i].live == REG_LIVE_READ) {
+ if (writes && (state->regs[i].live & REG_LIVE_WRITTEN))
+ continue;
+ if (state->regs[i].live & REG_LIVE_READ) {
parent->regs[i].live |= REG_LIVE_READ;
touched = true;
}
@@ -3444,7 +3447,9 @@ static bool do_propagate_liveness(const struct
bpf_verifier_state *state,
continue;
if (parent->spilled_regs[i].live & REG_LIVE_READ)
continue;
- if (state->spilled_regs[i].live == REG_LIVE_READ) {
+ if (writes && (state->spilled_regs[i].live & REG_LIVE_WRITTEN))
+ continue;
+ if (state->spilled_regs[i].live & REG_LIVE_READ) {
parent->spilled_regs[i].live |= REG_LIVE_READ;
touched = true;
}
___
iovisor-dev mailing list
iovisor-dev@lists.iovisor.org
https://lists.iovisor.org/mailman/listinfo/iovisor-dev
[iovisor-dev] [PATCH net-next 2/4] bpf/verifier: remove varlen_map_value_access flag
The optimisation it does is broken when the 'new' register value has a
variable offset and the 'old' was constant. I broke it with my pointer
types unification (see Fixes tag below), before which the 'new' value
would have type PTR_TO_MAP_VALUE_ADJ and would thus not compare equal;
other changes in that patch mean that its original behaviour (ignore
min/max values) cannot be restored.
Tests on a sample set of cilium programs show no change in count of
processed instructions.
Fixes: f1174f77b50c ("bpf/verifier: rework value tracking")
Signed-off-by: Edward Cree
---
include/linux/bpf_verifier.h | 1 -
kernel/bpf/verifier.c| 41 -
2 files changed, 12 insertions(+), 30 deletions(-)
diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index 91d07ef..d8f131a 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -125,7 +125,6 @@ struct bpf_verifier_env {
u32 id_gen; /* used to generate unique reg IDs */
bool allow_ptr_leaks;
bool seen_direct_write;
- bool varlen_map_value_access;
struct bpf_insn_aux_data *insn_aux_data; /* array of per-insn state */
};
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index e42c096..1e3f56c 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -832,11 +832,6 @@ static int check_map_access(struct bpf_verifier_env *env,
u32 regno,
*/
if (log_level)
print_verifier_state(state);
- /* If the offset is variable, we will need to be stricter in state
-* pruning from now on.
-*/
- if (!tnum_is_const(reg->var_off))
- env->varlen_map_value_access = true;
/* The minimum value is only important with signed
* comparisons where we can't assume the floor of a
* value is 0. If we are using signed variables for our
@@ -3247,9 +3242,8 @@ static bool check_ids(u32 old_id, u32 cur_id, struct
idpair *idmap)
}
/* Returns true if (rold safe implies rcur safe) */
-static bool regsafe(struct bpf_reg_state *rold,
- struct bpf_reg_state *rcur,
- bool varlen_map_access, struct idpair *idmap)
+static bool regsafe(struct bpf_reg_state *rold, struct bpf_reg_state *rcur,
+ struct idpair *idmap)
{
if (!(rold->live & REG_LIVE_READ))
/* explored state didn't use this */
@@ -3281,22 +3275,14 @@ static bool regsafe(struct bpf_reg_state *rold,
tnum_is_unknown(rold->var_off);
}
case PTR_TO_MAP_VALUE:
- if (varlen_map_access) {
- /* If the new min/max/var_off satisfy the old ones and
-* everything else matches, we are OK.
-* We don't care about the 'id' value, because nothing
-* uses it for PTR_TO_MAP_VALUE (only for ..._OR_NULL)
-*/
- return memcmp(rold, rcur, offsetof(struct
bpf_reg_state, id)) == 0 &&
- range_within(rold, rcur) &&
- tnum_in(rold->var_off, rcur->var_off);
- } else {
- /* If the ranges/var_off were not the same, but
-* everything else was and we didn't do a variable
-* access into a map then we are a-ok.
-*/
- return memcmp(rold, rcur, offsetof(struct
bpf_reg_state, id)) == 0;
- }
+ /* If the new min/max/var_off satisfy the old ones and
+* everything else matches, we are OK.
+* We don't care about the 'id' value, because nothing
+* uses it for PTR_TO_MAP_VALUE (only for ..._OR_NULL)
+*/
+ return memcmp(rold, rcur, offsetof(struct bpf_reg_state, id))
== 0 &&
+ range_within(rold, rcur) &&
+ tnum_in(rold->var_off, rcur->var_off);
case PTR_TO_MAP_VALUE_OR_NULL:
/* a PTR_TO_MAP_VALUE could be safe to use as a
* PTR_TO_MAP_VALUE_OR_NULL into the same map.
@@ -3380,7 +3366,6 @@ static bool states_equal(struct bpf_verifier_env *env,
struct bpf_verifier_state *old,
struct bpf_verifier_state *cur)
{
- bool varlen_map_access = env->varlen_map_value_access;
struct idpair *idmap;
bool ret = false;
int i;
@@ -3391,8 +3376,7 @@ static bool states_equal(struct bpf_verifier_env *env,
return false;
for (i = 0; i < MAX_BPF_REG; i++) {
- if (!regsafe(&old->regs[i], &cur->regs[i], varlen_map_access,
-idmap))
+ if (!regsafe(&old->regs[i], &cur->regs[i], idmap))
goto out_free;
}
@@ -341
[iovisor-dev] [PATCH net-next 1/4] selftests/bpf: add a test for a pruning bug in the verifier
From: Alexei Starovoitov
The test makes a read through a map value pointer, then considers pruning
a branch where the register holds an adjusted map value pointer. It
should not prune, but currently it does.
Signed-off-by: Alexei Starovoitov
[ec...@solarflare.com: added test-name and patch description]
Signed-off-by: Edward Cree
---
tools/testing/selftests/bpf/test_verifier.c | 28
1 file changed, 28 insertions(+)
diff --git a/tools/testing/selftests/bpf/test_verifier.c
b/tools/testing/selftests/bpf/test_verifier.c
index c03542c..6ca1487 100644
--- a/tools/testing/selftests/bpf/test_verifier.c
+++ b/tools/testing/selftests/bpf/test_verifier.c
@@ -6487,6 +6487,34 @@ static struct bpf_test tests[] = {
.result = REJECT,
.prog_type = BPF_PROG_TYPE_LWT_IN,
},
+ {
+ "varlen_map_value_access pruning",
+ .insns = {
+ BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),
+ BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
+ BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
+ BPF_LD_MAP_FD(BPF_REG_1, 0),
+ BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0,
+BPF_FUNC_map_lookup_elem),
+ BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 8),
+ BPF_LDX_MEM(BPF_DW, BPF_REG_1, BPF_REG_0, 0),
+ BPF_MOV32_IMM(BPF_REG_2, MAX_ENTRIES),
+ BPF_JMP_REG(BPF_JSGT, BPF_REG_2, BPF_REG_1, 1),
+ BPF_MOV32_IMM(BPF_REG_1, 0),
+ BPF_ALU32_IMM(BPF_LSH, BPF_REG_1, 2),
+ BPF_ALU64_REG(BPF_ADD, BPF_REG_0, BPF_REG_1),
+ BPF_JMP_IMM(BPF_JA, 0, 0, 0),
+ BPF_ST_MEM(BPF_DW, BPF_REG_0, 0,
+ offsetof(struct test_val, foo)),
+ BPF_EXIT_INSN(),
+ },
+ .fixup_map2 = { 3 },
+ .errstr_unpriv = "R0 leaks addr",
+ .errstr = "R0 unbounded memory access",
+ .result_unpriv = REJECT,
+ .result = REJECT,
+ .flags = F_NEEDS_EFFICIENT_UNALIGNED_ACCESS,
+ },
};
static int probe_filter_length(const struct bpf_insn *fp)
___
iovisor-dev mailing list
iovisor-dev@lists.iovisor.org
https://lists.iovisor.org/mailman/listinfo/iovisor-dev
[iovisor-dev] [PATCH net-next 0/4] bpf: verifier fixes
Fix a couple of bugs introduced in my recent verifier patches. Patch #3 does slightly increase the insn count on bpf_lxc.o, but only by about a hundred insns (i.e. 0.2%). Alexei Starovoitov (1): selftests/bpf: add a test for a pruning bug in the verifier Edward Cree (3): bpf/verifier: remove varlen_map_value_access flag bpf/verifier: when pruning a branch, ignore its write marks bpf/verifier: document liveness analysis include/linux/bpf_verifier.h| 14 +- kernel/bpf/verifier.c | 78 + tools/testing/selftests/bpf/test_verifier.c | 28 +++ 3 files changed, 87 insertions(+), 33 deletions(-) ___ iovisor-dev mailing list iovisor-dev@lists.iovisor.org https://lists.iovisor.org/mailman/listinfo/iovisor-dev
