[v4,bpf-next,2/9] bpf: Adjust BPF_JMP that jumps to the 1st insn of the prologue

Commit Message

Martin KaFai Lau Aug. 27, 2024, 7:52 p.m. UTC

From: Martin KaFai Lau <[e-mail]>

The next patch will add a ctx ptr saving instruction
"(r1 = *(u64 *)(r10 -8)" at the beginning for the main prog
when there is an epilogue patch (by the .gen_epilogue() verifier
ops added in the next patch).

There is one corner case if the bpf prog has a BPF_JMP that jumps
to the 1st instruction. It needs an adjustment such that
those BPF_JMP instructions won't jump to the newly added
ctx saving instruction.
The commit 5337ac4c9b80 ("bpf: Fix the corner case with may_goto and jump to the 1st insn.")
has the details on this case.

Note that the jump back to 1st instruction is not limited to the
ctx ptr saving instruction. The same also applies to the prologue.
A later test, pro_epilogue_goto_start.c, has a test for the prologue
only case.

Thus, this patch does one adjustment after gen_prologue and
the future ctx ptr saving. It is done by
adjust_jmp_off(env->prog, 0, delta) where delta has the total
number of instructions in the prologue and
the future ctx ptr saving instruction.

The adjust_jmp_off(env->prog, 0, delta) assumes that the
prologue does not have a goto 1st instruction itself.
To accommodate the prologue might have a goto 1st insn itself,
adjust_jmp_off() needs to skip the prologue instructions. This patch
adds a skip_cnt argument to the adjust_jmp_off(). The skip_cnt is the
number of instructions at the beginning that does not need adjustment.
adjust_jmp_off(prog, 0, delta, delta) is used in this patch.

Signed-off-by: Martin KaFai Lau <[e-mail]>
---
 kernel/bpf/verifier.c | 11 +++++++----
 1 file changed, 7 insertions(+), 4 deletions(-)

Comments

Alexei Starovoitov Aug. 28, 2024, 4:48 p.m. UTC | #1

On Tue, Aug 27, 2024 at 12:53 PM Martin KaFai Lau <[e-mail]> wrote:
>
> From: Martin KaFai Lau <[e-mail]>
>
> The next patch will add a ctx ptr saving instruction
> "(r1 = *(u64 *)(r10 -8)" at the beginning for the main prog
> when there is an epilogue patch (by the .gen_epilogue() verifier
> ops added in the next patch).
>
> There is one corner case if the bpf prog has a BPF_JMP that jumps
> to the 1st instruction. It needs an adjustment such that
> those BPF_JMP instructions won't jump to the newly added
> ctx saving instruction.
> The commit 5337ac4c9b80 ("bpf: Fix the corner case with may_goto and jump to the 1st insn.")
> has the details on this case.
>
> Note that the jump back to 1st instruction is not limited to the
> ctx ptr saving instruction. The same also applies to the prologue.
> A later test, pro_epilogue_goto_start.c, has a test for the prologue
> only case.
>
> Thus, this patch does one adjustment after gen_prologue and
> the future ctx ptr saving. It is done by
> adjust_jmp_off(env->prog, 0, delta) where delta has the total
> number of instructions in the prologue and
> the future ctx ptr saving instruction.
>
> The adjust_jmp_off(env->prog, 0, delta) assumes that the
> prologue does not have a goto 1st instruction itself.
> To accommodate the prologue might have a goto 1st insn itself,
> adjust_jmp_off() needs to skip the prologue instructions. This patch
> adds a skip_cnt argument to the adjust_jmp_off(). The skip_cnt is the
> number of instructions at the beginning that does not need adjustment.
> adjust_jmp_off(prog, 0, delta, delta) is used in this patch.
>
> Signed-off-by: Martin KaFai Lau <[e-mail]>
> ---
>  kernel/bpf/verifier.c | 11 +++++++----
>  1 file changed, 7 insertions(+), 4 deletions(-)
>
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index b408692a12d7..8714b83c5fb8 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -19277,14 +19277,14 @@ static struct bpf_prog *bpf_patch_insn_data(struct bpf_verifier_env *env, u32 of
>   * For all jmp insns in a given 'prog' that point to 'tgt_idx' insn adjust the
>   * jump offset by 'delta'.
>   */
> -static int adjust_jmp_off(struct bpf_prog *prog, u32 tgt_idx, u32 delta)
> +static int adjust_jmp_off(struct bpf_prog *prog, u32 tgt_idx, u32 delta, u32 skip_cnt)
>  {
> -       struct bpf_insn *insn = prog->insnsi;
> +       struct bpf_insn *insn = prog->insnsi + skip_cnt;
>         u32 insn_cnt = prog->len, i;
>         s32 imm;
>         s16 off;
>
> -       for (i = 0; i < insn_cnt; i++, insn++) {
> +       for (i = skip_cnt; i < insn_cnt; i++, insn++) {

Do we really need to add this argument?

> -               WARN_ON(adjust_jmp_off(env->prog, subprog_start, 1));
> +               WARN_ON(adjust_jmp_off(env->prog, subprog_start, 1, 0));

We can always do for (i = delta; ...

The above case of skip_cnt == 0 is lucky to work this way.
It would be less surprising to skip all insns in the patch.
Maybe I'm missing something.

Martin KaFai Lau Aug. 28, 2024, 5:44 p.m. UTC | #2

On 8/28/24 9:48 AM, Alexei Starovoitov wrote:
> On Tue, Aug 27, 2024 at 12:53 PM Martin KaFai Lau <[e-mail]> wrote:
>>
>> From: Martin KaFai Lau <[e-mail]>
>>
>> The next patch will add a ctx ptr saving instruction
>> "(r1 = *(u64 *)(r10 -8)" at the beginning for the main prog
>> when there is an epilogue patch (by the .gen_epilogue() verifier
>> ops added in the next patch).
>>
>> There is one corner case if the bpf prog has a BPF_JMP that jumps
>> to the 1st instruction. It needs an adjustment such that
>> those BPF_JMP instructions won't jump to the newly added
>> ctx saving instruction.
>> The commit 5337ac4c9b80 ("bpf: Fix the corner case with may_goto and jump to the 1st insn.")
>> has the details on this case.
>>
>> Note that the jump back to 1st instruction is not limited to the
>> ctx ptr saving instruction. The same also applies to the prologue.
>> A later test, pro_epilogue_goto_start.c, has a test for the prologue
>> only case.
>>
>> Thus, this patch does one adjustment after gen_prologue and
>> the future ctx ptr saving. It is done by
>> adjust_jmp_off(env->prog, 0, delta) where delta has the total
>> number of instructions in the prologue and
>> the future ctx ptr saving instruction.
>>
>> The adjust_jmp_off(env->prog, 0, delta) assumes that the
>> prologue does not have a goto 1st instruction itself.
>> To accommodate the prologue might have a goto 1st insn itself,
>> adjust_jmp_off() needs to skip the prologue instructions. This patch
>> adds a skip_cnt argument to the adjust_jmp_off(). The skip_cnt is the
>> number of instructions at the beginning that does not need adjustment.
>> adjust_jmp_off(prog, 0, delta, delta) is used in this patch.
>>
>> Signed-off-by: Martin KaFai Lau <[e-mail]>
>> ---
>>   kernel/bpf/verifier.c | 11 +++++++----
>>   1 file changed, 7 insertions(+), 4 deletions(-)
>>
>> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
>> index b408692a12d7..8714b83c5fb8 100644
>> --- a/kernel/bpf/verifier.c
>> +++ b/kernel/bpf/verifier.c
>> @@ -19277,14 +19277,14 @@ static struct bpf_prog *bpf_patch_insn_data(struct bpf_verifier_env *env, u32 of
>>    * For all jmp insns in a given 'prog' that point to 'tgt_idx' insn adjust the
>>    * jump offset by 'delta'.
>>    */
>> -static int adjust_jmp_off(struct bpf_prog *prog, u32 tgt_idx, u32 delta)
>> +static int adjust_jmp_off(struct bpf_prog *prog, u32 tgt_idx, u32 delta, u32 skip_cnt)
>>   {
>> -       struct bpf_insn *insn = prog->insnsi;
>> +       struct bpf_insn *insn = prog->insnsi + skip_cnt;
>>          u32 insn_cnt = prog->len, i;
>>          s32 imm;
>>          s16 off;
>>
>> -       for (i = 0; i < insn_cnt; i++, insn++) {
>> +       for (i = skip_cnt; i < insn_cnt; i++, insn++) {
> 
> Do we really need to add this argument?
> 
>> -               WARN_ON(adjust_jmp_off(env->prog, subprog_start, 1));
>> +               WARN_ON(adjust_jmp_off(env->prog, subprog_start, 1, 0));
> 
> We can always do for (i = delta; ...
> 
> The above case of skip_cnt == 0 is lucky to work this way.
> It would be less surprising to skip all insns in the patch.
> Maybe I'm missing something.

For subprog_start case, tgt_idx (where the patch started) may not be 0. How 
about this:

	for (i = 0; i < insn_cnt; i++, insn++) {
		if (tgt_idx <= i && i < tgt_idx + delta)
			continue;

		/* ... */
	}

Alexei Starovoitov Aug. 28, 2024, 6:43 p.m. UTC | #3

On Wed, Aug 28, 2024 at 10:44 AM Martin KaFai Lau <[e-mail]> wrote:
> >>
> >> -       for (i = 0; i < insn_cnt; i++, insn++) {
> >> +       for (i = skip_cnt; i < insn_cnt; i++, insn++) {
> >
> > Do we really need to add this argument?
> >
> >> -               WARN_ON(adjust_jmp_off(env->prog, subprog_start, 1));
> >> +               WARN_ON(adjust_jmp_off(env->prog, subprog_start, 1, 0));
> >
> > We can always do for (i = delta; ...
> >
> > The above case of skip_cnt == 0 is lucky to work this way.
> > It would be less surprising to skip all insns in the patch.
> > Maybe I'm missing something.
>
> For subprog_start case, tgt_idx (where the patch started) may not be 0. How
> about this:
>
>         for (i = 0; i < insn_cnt; i++, insn++) {
>                 if (tgt_idx <= i && i < tgt_idx + delta)
>                         continue;

Yeah. Right. Same idea, but certainly your way is more correct
instead of my buggy proposal.

In that sense the "for (i = skip_cnt" approach
is also a bit buggy, if tgt_idx != 0.

Martin KaFai Lau Aug. 28, 2024, 6:59 p.m. UTC | #4

On 8/28/24 11:43 AM, Alexei Starovoitov wrote:
> On Wed, Aug 28, 2024 at 10:44 AM Martin KaFai Lau <[e-mail]> wrote:
>>>>
>>>> -       for (i = 0; i < insn_cnt; i++, insn++) {
>>>> +       for (i = skip_cnt; i < insn_cnt; i++, insn++) {
>>>
>>> Do we really need to add this argument?
>>>
>>>> -               WARN_ON(adjust_jmp_off(env->prog, subprog_start, 1));
>>>> +               WARN_ON(adjust_jmp_off(env->prog, subprog_start, 1, 0));
>>>
>>> We can always do for (i = delta; ...
>>>
>>> The above case of skip_cnt == 0 is lucky to work this way.
>>> It would be less surprising to skip all insns in the patch.
>>> Maybe I'm missing something.
>>
>> For subprog_start case, tgt_idx (where the patch started) may not be 0. How
>> about this:
>>
>>          for (i = 0; i < insn_cnt; i++, insn++) {
>>                  if (tgt_idx <= i && i < tgt_idx + delta)
>>                          continue;
> 
> Yeah. Right. Same idea, but certainly your way is more correct
> instead of my buggy proposal.
> 
> In that sense the "for (i = skip_cnt" approach
> is also a bit buggy, if tgt_idx != 0.

Yep. Adding skip_cnt like this patch 2 is not right. I didn't think hard enough 
what to do with the existing adjust_jmp_off().

I will remove skip_cnt in the next respin.

Thanks for the review!

Patch

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index b408692a12d7..8714b83c5fb8 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -19277,14 +19277,14 @@  static struct bpf_prog *bpf_patch_insn_data(struct bpf_verifier_env *env, u32 of
  * For all jmp insns in a given 'prog' that point to 'tgt_idx' insn adjust the
  * jump offset by 'delta'.
  */
-static int adjust_jmp_off(struct bpf_prog *prog, u32 tgt_idx, u32 delta)
+static int adjust_jmp_off(struct bpf_prog *prog, u32 tgt_idx, u32 delta, u32 skip_cnt)
 {
-	struct bpf_insn *insn = prog->insnsi;
+	struct bpf_insn *insn = prog->insnsi + skip_cnt;
 	u32 insn_cnt = prog->len, i;
 	s32 imm;
 	s16 off;
 
-	for (i = 0; i < insn_cnt; i++, insn++) {
+	for (i = skip_cnt; i < insn_cnt; i++, insn++) {
 		u8 code = insn->code;
 
 		if ((BPF_CLASS(code) != BPF_JMP && BPF_CLASS(code) != BPF_JMP32) ||
@@ -19705,6 +19705,9 @@  static int convert_ctx_accesses(struct bpf_verifier_env *env)
 		}
 	}
 
+	if (delta)
+		WARN_ON(adjust_jmp_off(env->prog, 0, delta, delta));
+
 	if (bpf_prog_is_offloaded(env->prog->aux))
 		return 0;
 
@@ -21136,7 +21139,7 @@  static int do_misc_fixups(struct bpf_verifier_env *env)
 		 * to insn after BPF_ST that inits may_goto count.
 		 * Adjustment will succeed because bpf_patch_insn_data() didn't fail.
 		 */
-		WARN_ON(adjust_jmp_off(env->prog, subprog_start, 1));
+		WARN_ON(adjust_jmp_off(env->prog, subprog_start, 1, 0));
 	}
 
 	/* Since poke tab is now finalized, publish aux to tracker. */