diff mbox series

[PATCH/RFC,bpf-next,02/16] bpf: refactor propagate_live implementation

Message ID 1553623539-15474-3-git-send-email-jiong.wang@netronome.com
State RFC
Delegated to: BPF Maintainers
Headers show
Series bpf: eliminate zero extensions for sub-register writes | expand

Commit Message

Jiong Wang March 26, 2019, 6:05 p.m. UTC 
Some code inside current implementation of "propagate_liveness" is a little
bit verbose.

This patch refactor them so the code looks more simple and more clear.

The redundant usage of "vparent->frame[vstate->curframe]" is removed as we
are here. It is safe to do this because "state_equal" has guaranteed that
vstate->curframe must be equal with vparent->curframe.

Signed-off-by: Jiong Wang <jiong.wang@netronome.com>
---
 kernel/bpf/verifier.c | 44 ++++++++++++++++++++++++++++++--------------
 1 file changed, 30 insertions(+), 14 deletions(-)

Comments

Jann Horn March 26, 2019, 6:26 p.m. UTC | #1 
On Tue, Mar 26, 2019 at 7:07 PM Jiong Wang <jiong.wang@netronome.com> wrote:
> Some code inside current implementation of "propagate_liveness" is a little
> bit verbose.
>
> This patch refactor them so the code looks more simple and more clear.
>
> The redundant usage of "vparent->frame[vstate->curframe]" is removed as we
> are here. It is safe to do this because "state_equal" has guaranteed that
> vstate->curframe must be equal with vparent->curframe.
[...]
> @@ -6050,6 +6050,22 @@ static bool states_equal(struct bpf_verifier_env *env,
>         return true;
>  }
>
> +static int propagate_liveness_reg(struct bpf_verifier_env *env,
> +                                 struct bpf_reg_state *reg,
> +                                 struct bpf_reg_state *parent_reg, u8 flag)

This function takes four arguments...

[...]
> @@ -6071,16 +6088,13 @@ static int propagate_liveness(struct bpf_verifier_env *env,
[...]
> +               err = propagate_liveness_reg(env, &regs[i], &parent_regs[i]);

.. but both here...

[...]
> @@ -6089,11 +6103,13 @@ static int propagate_liveness(struct bpf_verifier_env *env,
[...]
> +                       err = propagate_liveness_reg(env, reg, parent_reg);

... and here you only pass in three arguments? Does this compile?
Jiong Wang March 26, 2019, 7:45 p.m. UTC | #2 
On 26/03/2019 18:26, Jann Horn wrote:
> On Tue, Mar 26, 2019 at 7:07 PM Jiong Wang <jiong.wang@netronome.com> wrote:
>> Some code inside current implementation of "propagate_liveness" is a little
>> bit verbose.
>>
>> This patch refactor them so the code looks more simple and more clear.
>>
>> The redundant usage of "vparent->frame[vstate->curframe]" is removed as we
>> are here. It is safe to do this because "state_equal" has guaranteed that
>> vstate->curframe must be equal with vparent->curframe.
> [...]
>> @@ -6050,6 +6050,22 @@ static bool states_equal(struct bpf_verifier_env *env,
>>          return true;
>>   }
>>
>> +static int propagate_liveness_reg(struct bpf_verifier_env *env,
>> +                                 struct bpf_reg_state *reg,
>> +                                 struct bpf_reg_state *parent_reg, u8 flag)
> This function takes four arguments...
>
> [...]
>> @@ -6071,16 +6088,13 @@ static int propagate_liveness(struct bpf_verifier_env *env,
> [...]
>> +               err = propagate_liveness_reg(env, &regs[i], &parent_regs[i]);
> .. but both here...
>
> [...]
>> @@ -6089,11 +6103,13 @@ static int propagate_liveness(struct bpf_verifier_env *env,
> [...]
>> +                       err = propagate_liveness_reg(env, reg, parent_reg);
> ... and here you only pass in three arguments? Does this compile?

Yes, it compiles. It is fixed in patch 03/16...

I was doing some simplification on 03/16, then found it's better
to be put into 02/16, and forget to update the function prototype there,

apology for this.

Regards,
Jiong
Alexei Starovoitov March 27, 2019, 4:35 p.m. UTC | #3 
On Tue, Mar 26, 2019 at 06:05:25PM +0000, Jiong Wang wrote:
> Some code inside current implementation of "propagate_liveness" is a little
> bit verbose.
> 
> This patch refactor them so the code looks more simple and more clear.
> 
> The redundant usage of "vparent->frame[vstate->curframe]" is removed as we
> are here. It is safe to do this because "state_equal" has guaranteed that
> vstate->curframe must be equal with vparent->curframe.
> 
> Signed-off-by: Jiong Wang <jiong.wang@netronome.com>
> ---
>  kernel/bpf/verifier.c | 44 ++++++++++++++++++++++++++++++--------------
>  1 file changed, 30 insertions(+), 14 deletions(-)
> 
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 6cc8c38..245bb3c 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -6050,6 +6050,22 @@ static bool states_equal(struct bpf_verifier_env *env,
>  	return true;
>  }
>  
> +static int propagate_liveness_reg(struct bpf_verifier_env *env,
> +				  struct bpf_reg_state *reg,
> +				  struct bpf_reg_state *parent_reg, u8 flag)
> +{
> +	int err;
> +
> +	if (parent_reg->live & flag || !(reg->live & flag))
> +		return 0;
> +
> +	err = mark_reg_read(env, reg, parent_reg);
> +	if (err)
> +		return err;
> +
> +	return 1;
> +}

what is the difference between 1 and 0 ? it doesn't seem to be used.

> +
>  /* 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 an
>   * equivalent state (jump target or such) we didn't arrive by the straight-line
> @@ -6061,8 +6077,9 @@ static int propagate_liveness(struct bpf_verifier_env *env,
>  			      const struct bpf_verifier_state *vstate,
>  			      struct bpf_verifier_state *vparent)
>  {
> -	int i, frame, err = 0;
> +	struct bpf_reg_state *regs, *parent_regs;
>  	struct bpf_func_state *state, *parent;
> +	int i, frame, err = 0;
>  
>  	if (vparent->curframe != vstate->curframe) {
>  		WARN(1, "propagate_live: parent frame %d current frame %d\n",
> @@ -6071,16 +6088,13 @@ static int propagate_liveness(struct bpf_verifier_env *env,
>  	}
>  	/* Propagate read liveness of registers... */
>  	BUILD_BUG_ON(BPF_REG_FP + 1 != MAX_BPF_REG);
> +	parent_regs = vparent->frame[vparent->curframe]->regs;
> +	regs = vstate->frame[vstate->curframe]->regs;


may be do:
frame = vstate->curframe;
if (vparent->curframe != frame) { WARN...
parent_regs = vparent->frame[frame]->regs;
regs = vstate->frame[frame]->regs;

?

>  	/* We don't need to worry about FP liveness because it's read-only */
>  	for (i = 0; i < BPF_REG_FP; i++) {
> -		if (vparent->frame[vparent->curframe]->regs[i].live & REG_LIVE_READ)
> -			continue;
> -		if (vstate->frame[vstate->curframe]->regs[i].live & REG_LIVE_READ) {
> -			err = mark_reg_read(env, &vstate->frame[vstate->curframe]->regs[i],
> -					    &vparent->frame[vstate->curframe]->regs[i]);
> -			if (err)
> -				return err;
> -		}
> +		err = propagate_liveness_reg(env, &regs[i], &parent_regs[i]);
> +		if (err < 0)
> +			return err;
>  	}
>  
>  	/* ... and stack slots */
> @@ -6089,11 +6103,13 @@ static int propagate_liveness(struct bpf_verifier_env *env,
>  		parent = vparent->frame[frame];
>  		for (i = 0; i < state->allocated_stack / BPF_REG_SIZE &&
>  			    i < parent->allocated_stack / BPF_REG_SIZE; i++) {
> -			if (parent->stack[i].spilled_ptr.live & REG_LIVE_READ)
> -				continue;
> -			if (state->stack[i].spilled_ptr.live & REG_LIVE_READ)
> -				mark_reg_read(env, &state->stack[i].spilled_ptr,
> -					      &parent->stack[i].spilled_ptr);
> +			struct bpf_reg_state *parent_reg, *reg;
> +
> +			parent_reg = &parent->stack[i].spilled_ptr;
> +			reg = &state->stack[i].spilled_ptr;
> +			err = propagate_liveness_reg(env, reg, parent_reg);
> +			if (err < 0)
> +				return err;
>  		}
>  	}
>  	return err;
> -- 
> 2.7.4
>
Jiong Wang March 27, 2019, 4:44 p.m. UTC | #4 
> On 27 Mar 2019, at 16:35, Alexei Starovoitov <alexei.starovoitov@gmail.com> wrote:
> 
> On Tue, Mar 26, 2019 at 06:05:25PM +0000, Jiong Wang wrote:
>> Some code inside current implementation of "propagate_liveness" is a little
>> bit verbose.
>> 
>> This patch refactor them so the code looks more simple and more clear.
>> 
>> The redundant usage of "vparent->frame[vstate->curframe]" is removed as we
>> are here. It is safe to do this because "state_equal" has guaranteed that
>> vstate->curframe must be equal with vparent->curframe.
>> 
>> Signed-off-by: Jiong Wang <jiong.wang@netronome.com>
>> ---
>> kernel/bpf/verifier.c | 44 ++++++++++++++++++++++++++++++--------------
>> 1 file changed, 30 insertions(+), 14 deletions(-)
>> 
>> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
>> index 6cc8c38..245bb3c 100644
>> --- a/kernel/bpf/verifier.c
>> +++ b/kernel/bpf/verifier.c
>> @@ -6050,6 +6050,22 @@ static bool states_equal(struct bpf_verifier_env *env,
>> 	return true;
>> }
>> 
>> +static int propagate_liveness_reg(struct bpf_verifier_env *env,
>> +				  struct bpf_reg_state *reg,
>> +				  struct bpf_reg_state *parent_reg, u8 flag)
>> +{
>> +	int err;
>> +
>> +	if (parent_reg->live & flag || !(reg->live & flag))
>> +		return 0;
>> +
>> +	err = mark_reg_read(env, reg, parent_reg);
>> +	if (err)
>> +		return err;
>> +
>> +	return 1;
>> +}
> 
> what is the difference between 1 and 0 ? it doesn't seem to be used.

0 means no propagation has been done. 1 means propagation has been done.

They are used later in patch 4. If there is propagation, then will trigger
insn marking.

Will add comment for this.


> 
>> +
>> /* 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 an
>>  * equivalent state (jump target or such) we didn't arrive by the straight-line
>> @@ -6061,8 +6077,9 @@ static int propagate_liveness(struct bpf_verifier_env *env,
>> 			      const struct bpf_verifier_state *vstate,
>> 			      struct bpf_verifier_state *vparent)
>> {
>> -	int i, frame, err = 0;
>> +	struct bpf_reg_state *regs, *parent_regs;
>> 	struct bpf_func_state *state, *parent;
>> +	int i, frame, err = 0;
>> 
>> 	if (vparent->curframe != vstate->curframe) {
>> 		WARN(1, "propagate_live: parent frame %d current frame %d\n",
>> @@ -6071,16 +6088,13 @@ static int propagate_liveness(struct bpf_verifier_env *env,
>> 	}
>> 	/* Propagate read liveness of registers... */
>> 	BUILD_BUG_ON(BPF_REG_FP + 1 != MAX_BPF_REG);
>> +	parent_regs = vparent->frame[vparent->curframe]->regs;
>> +	regs = vstate->frame[vstate->curframe]->regs;
> 
> 
> may be do:
> frame = vstate->curframe;
> if (vparent->curframe != frame) { WARN...
> parent_regs = vparent->frame[frame]->regs;
> regs = vstate->frame[frame]->regs;
> 
> ?

Ack, will factor out "vstate->curframe” into “frame”.
 
And there is a check and warning on the equality already, just several lines above:

   if (vparent->curframe != vstate->curframe) {                             
     WARN(1, "propagate_live: parent frame %d current frame %d\n",

Regards,
Jiong
 
> 
>> 	/* We don't need to worry about FP liveness because it's read-only */
>> 	for (i = 0; i < BPF_REG_FP; i++) {
>> -		if (vparent->frame[vparent->curframe]->regs[i].live & REG_LIVE_READ)
>> -			continue;
>> -		if (vstate->frame[vstate->curframe]->regs[i].live & REG_LIVE_READ) {
>> -			err = mark_reg_read(env, &vstate->frame[vstate->curframe]->regs[i],
>> -					    &vparent->frame[vstate->curframe]->regs[i]);
>> -			if (err)
>> -				return err;
>> -		}
>> +		err = propagate_liveness_reg(env, &regs[i], &parent_regs[i]);
>> +		if (err < 0)
>> +			return err;
>> 	}
>> 
>> 	/* ... and stack slots */
>> @@ -6089,11 +6103,13 @@ static int propagate_liveness(struct bpf_verifier_env *env,
>> 		parent = vparent->frame[frame];
>> 		for (i = 0; i < state->allocated_stack / BPF_REG_SIZE &&
>> 			    i < parent->allocated_stack / BPF_REG_SIZE; i++) {
>> -			if (parent->stack[i].spilled_ptr.live & REG_LIVE_READ)
>> -				continue;
>> -			if (state->stack[i].spilled_ptr.live & REG_LIVE_READ)
>> -				mark_reg_read(env, &state->stack[i].spilled_ptr,
>> -					      &parent->stack[i].spilled_ptr);
>> +			struct bpf_reg_state *parent_reg, *reg;
>> +
>> +			parent_reg = &parent->stack[i].spilled_ptr;
>> +			reg = &state->stack[i].spilled_ptr;
>> +			err = propagate_liveness_reg(env, reg, parent_reg);
>> +			if (err < 0)
>> +				return err;
>> 		}
>> 	}
>> 	return err;
>> -- 
>> 2.7.4
>>
diff mbox series

Patch

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 6cc8c38..245bb3c 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -6050,6 +6050,22 @@  static bool states_equal(struct bpf_verifier_env *env,
 	return true;
 }
 
+static int propagate_liveness_reg(struct bpf_verifier_env *env,
+				  struct bpf_reg_state *reg,
+				  struct bpf_reg_state *parent_reg, u8 flag)
+{
+	int err;
+
+	if (parent_reg->live & flag || !(reg->live & flag))
+		return 0;
+
+	err = mark_reg_read(env, reg, parent_reg);
+	if (err)
+		return err;
+
+	return 1;
+}
+
 /* 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 an
  * equivalent state (jump target or such) we didn't arrive by the straight-line
@@ -6061,8 +6077,9 @@  static int propagate_liveness(struct bpf_verifier_env *env,
 			      const struct bpf_verifier_state *vstate,
 			      struct bpf_verifier_state *vparent)
 {
-	int i, frame, err = 0;
+	struct bpf_reg_state *regs, *parent_regs;
 	struct bpf_func_state *state, *parent;
+	int i, frame, err = 0;
 
 	if (vparent->curframe != vstate->curframe) {
 		WARN(1, "propagate_live: parent frame %d current frame %d\n",
@@ -6071,16 +6088,13 @@  static int propagate_liveness(struct bpf_verifier_env *env,
 	}
 	/* Propagate read liveness of registers... */
 	BUILD_BUG_ON(BPF_REG_FP + 1 != MAX_BPF_REG);
+	parent_regs = vparent->frame[vparent->curframe]->regs;
+	regs = vstate->frame[vstate->curframe]->regs;
 	/* We don't need to worry about FP liveness because it's read-only */
 	for (i = 0; i < BPF_REG_FP; i++) {
-		if (vparent->frame[vparent->curframe]->regs[i].live & REG_LIVE_READ)
-			continue;
-		if (vstate->frame[vstate->curframe]->regs[i].live & REG_LIVE_READ) {
-			err = mark_reg_read(env, &vstate->frame[vstate->curframe]->regs[i],
-					    &vparent->frame[vstate->curframe]->regs[i]);
-			if (err)
-				return err;
-		}
+		err = propagate_liveness_reg(env, &regs[i], &parent_regs[i]);
+		if (err < 0)
+			return err;
 	}
 
 	/* ... and stack slots */
@@ -6089,11 +6103,13 @@  static int propagate_liveness(struct bpf_verifier_env *env,
 		parent = vparent->frame[frame];
 		for (i = 0; i < state->allocated_stack / BPF_REG_SIZE &&
 			    i < parent->allocated_stack / BPF_REG_SIZE; i++) {
-			if (parent->stack[i].spilled_ptr.live & REG_LIVE_READ)
-				continue;
-			if (state->stack[i].spilled_ptr.live & REG_LIVE_READ)
-				mark_reg_read(env, &state->stack[i].spilled_ptr,
-					      &parent->stack[i].spilled_ptr);
+			struct bpf_reg_state *parent_reg, *reg;
+
+			parent_reg = &parent->stack[i].spilled_ptr;
+			reg = &state->stack[i].spilled_ptr;
+			err = propagate_liveness_reg(env, reg, parent_reg);
+			if (err < 0)
+				return err;
 		}
 	}
 	return err;