[PATCH bpf-next 0/7] Fix MAX_TAIL_CALL_CNT handling in eBPF JITs

A new test of tail call count limiting revealed that the interpreter
did in fact allow up to MAX_TAIL_CALL_CNT + 1 tail calls, whereas the
x86 JITs stopped at the intended MAX_TAIL_CALL_CNT. The interpreter was
fixed in commit b61a28cf11d61f512172e673b8f8c4a6c789b425 ("bpf: Fix
off-by-one in tail call count limiting"). This patch set fixes all
arch-specific JITs except for RISC-V.

For each of the affected JITs, the incorrect behaviour was verified
by running the test_bpf test suite in QEMU. After the fixes, the JITs
pass the tail call count limiting test.

I have not been able to test the RISC-V JITs due to the lack of a
working toolchain and QEMU setup. It is likely that the RISC-V JITs
have the off-by-one behaviour too. I have not verfied any of the NIC JITs.

Link: https://lore.kernel.org/bpf/20210728164741.350370-1-johan.almbladh@anyfinetworks.com/

Johan Almbladh (7):
  arm: bpf: Fix off-by-one in tail call count limiting
  arm64: bpf: Fix off-by-one in tail call count limiting
  powerpc: bpf: Fix off-by-one in tail call count limiting
  s390: bpf: Fix off-by-one in tail call count limiting
  sparc: bpf: Fix off-by-one in tail call count limiting
  mips: bpf: Fix off-by-one in tail call count limiting
  x86: bpf: Fix comments on tail call count limiting

 arch/arm/net/bpf_jit_32.c         | 6 +++---
 arch/arm64/net/bpf_jit_comp.c     | 4 ++--
 arch/mips/net/ebpf_jit.c          | 4 ++--
 arch/powerpc/net/bpf_jit_comp32.c | 4 ++--
 arch/powerpc/net/bpf_jit_comp64.c | 4 ++--
 arch/s390/net/bpf_jit_comp.c      | 6 +++---
 arch/sparc/net/bpf_jit_comp_64.c  | 2 +-
 arch/x86/net/bpf_jit_comp32.c     | 6 +++---
 8 files changed, 18 insertions(+), 18 deletions(-)

-- 
2.25.1

Before, the eBPF JIT allowed up to MAX_TAIL_CALL_CNT + 1 tail calls.
Now, precisely MAX_TAIL_CALL_CNT is allowed, which is in line with the
behaviour of the interpreter. Verified with the test_bpf test suite
on qemu-system-arm.

Signed-off-by: Johan Almbladh <johan.almbladh@anyfinetworks.com>
---
 arch/arm/net/bpf_jit_32.c | 6 +++---
 1 file changed, 3 insertions(+), 3 deletions(-)

diff --git a/arch/arm/net/bpf_jit_32.c b/arch/arm/net/bpf_jit_32.c
index a951276f0547..200ae9d24205 100644
--- a/arch/arm/net/bpf_jit_32.c
+++ b/arch/arm/net/bpf_jit_32.c

@@ -1180,12 +1180,12 @@ static int emit_bpf_tail_call(struct jit_ctx *ctx)
 
 	/* tmp2[0] = array, tmp2[1] = index */
 
-	/* if (tail_call_cnt > MAX_TAIL_CALL_CNT)
+	/* if (tail_call_cnt >= MAX_TAIL_CALL_CNT)
 	 *	goto out;
 	 * tail_call_cnt++;
 	 */
-	lo = (u32)MAX_TAIL_CALL_CNT;
-	hi = (u32)((u64)MAX_TAIL_CALL_CNT >> 32);
+	lo = (u32)(MAX_TAIL_CALL_CNT - 1);
+	hi = (u32)((u64)(MAX_TAIL_CALL_CNT - 1) >> 32);
 	tc = arm_bpf_get_reg64(tcc, tmp, ctx);
 	emit(ARM_CMP_I(tc[0], hi), ctx);
 	_emit(ARM_COND_EQ, ARM_CMP_I(tc[1], lo), ctx);

-- 
2.25.1

Before, the eBPF JIT allowed up to MAX_TAIL_CALL_CNT + 1 tail calls.
Now, precisely MAX_TAIL_CALL_CNT is allowed, which is in line with the
behaviour of the interpreter. Verified with the test_bpf test suite
on qemu-system-aarch64.

Signed-off-by: Johan Almbladh <johan.almbladh@anyfinetworks.com>
---
 arch/arm64/net/bpf_jit_comp.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/arch/arm64/net/bpf_jit_comp.c b/arch/arm64/net/bpf_jit_comp.c
index 41c23f474ea6..cda53e33bbec 100644
--- a/arch/arm64/net/bpf_jit_comp.c
+++ b/arch/arm64/net/bpf_jit_comp.c

@@ -286,11 +286,11 @@ static int emit_bpf_tail_call(struct jit_ctx *ctx)
 	emit(A64_CMP(0, r3, tmp), ctx);
 	emit(A64_B_(A64_COND_CS, jmp_offset), ctx);
 
-	/* if (tail_call_cnt > MAX_TAIL_CALL_CNT)
+	/* if (tail_call_cnt >= MAX_TAIL_CALL_CNT)
 	 *     goto out;
 	 * tail_call_cnt++;
 	 */
-	emit_a64_mov_i64(tmp, MAX_TAIL_CALL_CNT, ctx);
+	emit_a64_mov_i64(tmp, MAX_TAIL_CALL_CNT - 1, ctx);
 	emit(A64_CMP(1, tcc, tmp), ctx);
 	emit(A64_B_(A64_COND_HI, jmp_offset), ctx);
 	emit(A64_ADD_I(1, tcc, tcc, 1), ctx);

-- 
2.25.1

Before, the eBPF JITs allowed up to MAX_TAIL_CALL_CNT + 1 tail calls.
Now, precisely MAX_TAIL_CALL_CNT is allowed, which is in line with the
behaviour of the interpreter. Verified with the test_bpf test suite
on qemu-system-ppc and qemu-system-ppc64, respectively.

Signed-off-by: Johan Almbladh <johan.almbladh@anyfinetworks.com>
---
 arch/powerpc/net/bpf_jit_comp32.c | 4 ++--
 arch/powerpc/net/bpf_jit_comp64.c | 4 ++--
 2 files changed, 4 insertions(+), 4 deletions(-)

diff --git a/arch/powerpc/net/bpf_jit_comp32.c b/arch/powerpc/net/bpf_jit_comp32.c
index beb12cbc8c29..6d720728df09 100644
--- a/arch/powerpc/net/bpf_jit_comp32.c
+++ b/arch/powerpc/net/bpf_jit_comp32.c

@@ -221,13 +221,13 @@ static void bpf_jit_emit_tail_call(u32 *image, struct codegen_context *ctx, u32
 	PPC_BCC(COND_GE, out);
 
 	/*
-	 * if (tail_call_cnt > MAX_TAIL_CALL_CNT)
+	 * if (tail_call_cnt >= MAX_TAIL_CALL_CNT)
 	 *   goto out;
 	 */
 	EMIT(PPC_RAW_CMPLWI(_R0, MAX_TAIL_CALL_CNT));
 	/* tail_call_cnt++; */
 	EMIT(PPC_RAW_ADDIC(_R0, _R0, 1));
-	PPC_BCC(COND_GT, out);
+	PPC_BCC(COND_GE, out);
 
 	/* prog = array->ptrs[index]; */
 	EMIT(PPC_RAW_RLWINM(_R3, b2p_index, 2, 0, 29));

diff --git a/arch/powerpc/net/bpf_jit_comp64.c b/arch/powerpc/net/bpf_jit_comp64.c
index b87a63dba9c8..2f4d24ed90a4 100644
--- a/arch/powerpc/net/bpf_jit_comp64.c
+++ b/arch/powerpc/net/bpf_jit_comp64.c

@@ -227,12 +227,12 @@ static void bpf_jit_emit_tail_call(u32 *image, struct codegen_context *ctx, u32
 	PPC_BCC(COND_GE, out);
 
 	/*
-	 * if (tail_call_cnt > MAX_TAIL_CALL_CNT)
+	 * if (tail_call_cnt >= MAX_TAIL_CALL_CNT)
 	 *   goto out;
 	 */
 	PPC_BPF_LL(b2p[TMP_REG_1], 1, bpf_jit_stack_tailcallcnt(ctx));
 	EMIT(PPC_RAW_CMPLWI(b2p[TMP_REG_1], MAX_TAIL_CALL_CNT));
-	PPC_BCC(COND_GT, out);
+	PPC_BCC(COND_GE, out);
 
 	/*
 	 * tail_call_cnt++;

-- 
2.25.1

Before, the eBPF JIT allowed up to MAX_TAIL_CALL_CNT + 1 tail calls.
Now, precisely MAX_TAIL_CALL_CNT is allowed, which is in line with the
behaviour of the interpreter. Verified with the test_bpf test suite
on qemu-system-s390x.

Signed-off-by: Johan Almbladh <johan.almbladh@anyfinetworks.com>
---
 arch/s390/net/bpf_jit_comp.c | 6 +++---
 1 file changed, 3 insertions(+), 3 deletions(-)

diff --git a/arch/s390/net/bpf_jit_comp.c b/arch/s390/net/bpf_jit_comp.c
index 88419263a89a..f6cdf13285ed 100644
--- a/arch/s390/net/bpf_jit_comp.c
+++ b/arch/s390/net/bpf_jit_comp.c

@@ -1363,7 +1363,7 @@ static noinline int bpf_jit_insn(struct bpf_jit *jit, struct bpf_prog *fp,
 				 jit->prg);
 
 		/*
-		 * if (tail_call_cnt++ > MAX_TAIL_CALL_CNT)
+		 * if (tail_call_cnt++ >= MAX_TAIL_CALL_CNT)
 		 *         goto out;
 		 */
 

@@ -1377,8 +1377,8 @@ static noinline int bpf_jit_insn(struct bpf_jit *jit, struct bpf_prog *fp,
 		EMIT6_DISP_LH(0xeb000000, 0x00fa, REG_W1, REG_W0, REG_15, off);
 		/* clij %w1,MAX_TAIL_CALL_CNT,0x2,out */
 		patch_2_clij = jit->prg;
-		EMIT6_PCREL_RIEC(0xec000000, 0x007f, REG_W1, MAX_TAIL_CALL_CNT,
-				 2, jit->prg);
+		EMIT6_PCREL_RIEC(0xec000000, 0x007f, REG_W1,
+				 MAX_TAIL_CALL_CNT - 1, 2, jit->prg);
 
 		/*
 		 * prog = array->ptrs[index];

-- 
2.25.1

Before, the eBPF JIT allowed up to MAX_TAIL_CALL_CNT + 1 tail calls.
Now, precisely MAX_TAIL_CALL_CNT is allowed, which is in line with the
behaviour of the interpreter. Verified with the test_bpf test suite
on qemu-system-mips64.

Signed-off-by: Johan Almbladh <johan.almbladh@anyfinetworks.com>
---
 arch/mips/net/ebpf_jit.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/arch/mips/net/ebpf_jit.c b/arch/mips/net/ebpf_jit.c
index 3a73e9375712..a93121d71c80 100644
--- a/arch/mips/net/ebpf_jit.c
+++ b/arch/mips/net/ebpf_jit.c

@@ -617,14 +617,14 @@ static int emit_bpf_tail_call(struct jit_ctx *ctx, int this_idx)
 	b_off = b_imm(this_idx + 1, ctx);
 	emit_instr(ctx, bne, MIPS_R_AT, MIPS_R_ZERO, b_off);
 	/*
-	 * if (TCC-- < 0)
+	 * if (TCC-- <= 0)
 	 *     goto out;
 	 */
 	/* Delay slot */
 	tcc_reg = (ctx->flags & EBPF_TCC_IN_V1) ? MIPS_R_V1 : MIPS_R_S4;
 	emit_instr(ctx, daddiu, MIPS_R_T5, tcc_reg, -1);
 	b_off = b_imm(this_idx + 1, ctx);
-	emit_instr(ctx, bltz, tcc_reg, b_off);
+	emit_instr(ctx, blez, tcc_reg, b_off);
 	/*
 	 * prog = array->ptrs[index];
 	 * if (prog == NULL)

-- 
2.25.1

Before, the comments in the 32-bit eBPF JIT claimed that up to
MAX_TAIL_CALL_CNT + 1 tail calls were allowed, when in fact the
implementation was using the correct limit of MAX_TAIL_CALL_CNT.
Now, the comments are in line with what the code actually does.

Signed-off-by: Johan Almbladh <johan.almbladh@anyfinetworks.com>
---
 arch/x86/net/bpf_jit_comp32.c | 6 +++---
 1 file changed, 3 insertions(+), 3 deletions(-)

diff --git a/arch/x86/net/bpf_jit_comp32.c b/arch/x86/net/bpf_jit_comp32.c
index 3bfda5f502cb..8db9ab11abda 100644
--- a/arch/x86/net/bpf_jit_comp32.c
+++ b/arch/x86/net/bpf_jit_comp32.c

@@ -1272,7 +1272,7 @@ static void emit_epilogue(u8 **pprog, u32 stack_depth)
  * ... bpf_tail_call(void *ctx, struct bpf_array *array, u64 index) ...
  *   if (index >= array->map.max_entries)
  *     goto out;
- *   if (++tail_call_cnt > MAX_TAIL_CALL_CNT)
+ *   if (tail_call_cnt++ >= MAX_TAIL_CALL_CNT)
  *     goto out;
  *   prog = array->ptrs[index];
  *   if (prog == NULL)

@@ -1307,7 +1307,7 @@ static void emit_bpf_tail_call(u8 **pprog)
 	EMIT2(IA32_JBE, jmp_label(jmp_label1, 2));
 
 	/*
-	 * if (tail_call_cnt > MAX_TAIL_CALL_CNT)
+	 * if (tail_call_cnt >= MAX_TAIL_CALL_CNT)
 	 *     goto out;
 	 */
 	lo = (u32)MAX_TAIL_CALL_CNT;

@@ -1321,7 +1321,7 @@ static void emit_bpf_tail_call(u8 **pprog)
 	/* cmp ecx,lo */
 	EMIT3(0x83, add_1reg(0xF8, IA32_ECX), lo);
 
-	/* ja out */
+	/* jae out */
 	EMIT2(IA32_JAE, jmp_label(jmp_label1, 2));
 
 	/* add eax,0x1 */

-- 
2.25.1

Before, the eBPF JIT allowed up to MAX_TAIL_CALL_CNT + 1 tail calls.
Now, precisely MAX_TAIL_CALL_CNT is allowed, which is in line with the
behaviour of the interpreter. Verified with the test_bpf test suite
on qemu-system-sparc64.

Signed-off-by: Johan Almbladh <johan.almbladh@anyfinetworks.com>
---
 arch/sparc/net/bpf_jit_comp_64.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/arch/sparc/net/bpf_jit_comp_64.c b/arch/sparc/net/bpf_jit_comp_64.c
index 9a2f20cbd48b..0bfe1c72a0c9 100644
--- a/arch/sparc/net/bpf_jit_comp_64.c
+++ b/arch/sparc/net/bpf_jit_comp_64.c

@@ -867,7 +867,7 @@ static void emit_tail_call(struct jit_ctx *ctx)
 	emit(LD32 | IMMED | RS1(SP) | S13(off) | RD(tmp), ctx);
 	emit_cmpi(tmp, MAX_TAIL_CALL_CNT, ctx);
 #define OFFSET2 13
-	emit_branch(BGU, ctx->idx, ctx->idx + OFFSET2, ctx);
+	emit_branch(BGEU, ctx->idx, ctx->idx + OFFSET2, ctx);
 	emit_nop(ctx);
 
 	emit_alu_K(ADD, tmp, 1, ctx);

-- 
2.25.1

On Mon, 2021-08-09 at 11:34 +0200, Johan Almbladh wrote:

This comment needs to be updated as well.

                patch_2_clij = jit->prg;
-               EMIT6_PCREL_RIEC(0xec000000, 0x007f, REG_W1,
MAX_TAIL_CALL_CNT,
-                                2, jit->prg);
+               EMIT6_PCREL_RIEC(0xec000000, 0x007f, REG_W1,
+                                MAX_TAIL_CALL_CNT - 1, 2, jit->prg);
 
                /*
                 * prog = array->ptrs[index];

With that:

Tested-by: Ilya Leoshkevich <iii@linux.ibm.com>
Acked-by: Ilya Leoshkevich <iii@linux.ibm.com>

On 8/9/21 11:34 AM, Johan Almbladh wrote:

You have me confused here ... b61a28cf11d6 ("bpf: Fix off-by-one in tail call count
limiting") from bpf-next says '[interpreter is now] in line with the behavior of the
x86 JITs'. From the latter I assumed you implicitly refer to x86-64. Which one did you
test specifically wrt the prior statement? It looks like x86-64 vs x86-32 differ:

   [...]
   EMIT2_off32(0x8B, 0x85, tcc_off);         /* mov eax, dword ptr [rbp - tcc_off] */
   EMIT3(0x83, 0xF8, MAX_TAIL_CALL_CNT);     /* cmp eax, MAX_TAIL_CALL_CNT */
   EMIT2(X86_JA, OFFSET2);                   /* ja out */
   EMIT3(0x83, 0xC0, 0x01);                  /* add eax, 1 */
   EMIT2_off32(0x89, 0x85, tcc_off);         /* mov dword ptr [rbp - tcc_off], eax */
   [...]

So it's ja vs jae ... unless I need more coffee? ;)

  	/* add eax,0x1 */

On Mon, Aug 9, 2021 at 5:42 PM Daniel Borkmann [off-list ref] wrote:

On 8/9/21 11:34 AM, Johan Almbladh wrote:

quoted

Before, the comments in the 32-bit eBPF JIT claimed that up to
MAX_TAIL_CALL_CNT + 1 tail calls were allowed, when in fact the
implementation was using the correct limit of MAX_TAIL_CALL_CNT.
Now, the comments are in line with what the code actually does.

Signed-off-by: Johan Almbladh <johan.almbladh@anyfinetworks.com>
---
  arch/x86/net/bpf_jit_comp32.c | 6 +++---
  1 file changed, 3 insertions(+), 3 deletions(-)

diff --git a/arch/x86/net/bpf_jit_comp32.c b/arch/x86/net/bpf_jit_comp32.c
index 3bfda5f502cb..8db9ab11abda 100644
--- a/arch/x86/net/bpf_jit_comp32.c
+++ b/arch/x86/net/bpf_jit_comp32.c

@@ -1272,7 +1272,7 @@ static void emit_epilogue(u8 **pprog, u32 stack_depth)
   * ... bpf_tail_call(void *ctx, struct bpf_array *array, u64 index) ...
   *   if (index >= array->map.max_entries)
   *     goto out;
- *   if (++tail_call_cnt > MAX_TAIL_CALL_CNT)
+ *   if (tail_call_cnt++ >= MAX_TAIL_CALL_CNT)
   *     goto out;
   *   prog = array->ptrs[index];
   *   if (prog == NULL)

@@ -1307,7 +1307,7 @@ static void emit_bpf_tail_call(u8 **pprog)
      EMIT2(IA32_JBE, jmp_label(jmp_label1, 2));

      /*
-      * if (tail_call_cnt > MAX_TAIL_CALL_CNT)
+      * if (tail_call_cnt >= MAX_TAIL_CALL_CNT)
       *     goto out;
       */
      lo = (u32)MAX_TAIL_CALL_CNT;

@@ -1321,7 +1321,7 @@ static void emit_bpf_tail_call(u8 **pprog)
      /* cmp ecx,lo */
      EMIT3(0x83, add_1reg(0xF8, IA32_ECX), lo);

-     /* ja out */
+     /* jae out */
      EMIT2(IA32_JAE, jmp_label(jmp_label1, 2));

You have me confused here ... b61a28cf11d6 ("bpf: Fix off-by-one in tail call count
limiting") from bpf-next says '[interpreter is now] in line with the behavior of the
x86 JITs'. From the latter I assumed you implicitly refer to x86-64. Which one did you
test specifically wrt the prior statement?

I tested both the 64-bit and the 32-bit JITs with QEMU. Both passed,
meaning that the tail call recursion stopped after 32 tail calls.
However, the comments in the code indicated that it would allow one
more call, and also said JA when it actually emitted JAE. This patch
merely fixes the comments in the 32-bit JIT to match the code.

It looks like x86-64 vs x86-32 differ:

   [...]
   EMIT2_off32(0x8B, 0x85, tcc_off);         /* mov eax, dword ptr [rbp - tcc_off] */
   EMIT3(0x83, 0xF8, MAX_TAIL_CALL_CNT);     /* cmp eax, MAX_TAIL_CALL_CNT */
   EMIT2(X86_JA, OFFSET2);                   /* ja out */
   EMIT3(0x83, 0xC0, 0x01);                  /* add eax, 1 */
   EMIT2_off32(0x89, 0x85, tcc_off);         /* mov dword ptr [rbp - tcc_off], eax */
   [...]

So it's ja vs jae ... unless I need more coffee? ;)

Yes, the x86-64 JIT is different. It also pass the test, but I do find
the code and comments a bit confusing too. Since it pass the test, and
the top-level comment correctly states the stop condition as
++tail_call_cnt > MAX_TAIL_CALL_CNT, I left it at that.

On a side note, I see that the x86-64 JIT also has a direct tail call
code path which the other JITs don't seem to have. The tail call test
only checks the indirect tail call code path.

quoted

      /* add eax,0x1 */

On Mon, Aug 9, 2021 at 2:24 PM Ilya Leoshkevich [off-list ref] wrote:

On Mon, 2021-08-09 at 11:34 +0200, Johan Almbladh wrote:

quoted

Before, the eBPF JIT allowed up to MAX_TAIL_CALL_CNT + 1 tail calls.
Now, precisely MAX_TAIL_CALL_CNT is allowed, which is in line with the
behaviour of the interpreter. Verified with the test_bpf test suite
on qemu-system-s390x.

Signed-off-by: Johan Almbladh <johan.almbladh@anyfinetworks.com>
---
 arch/s390/net/bpf_jit_comp.c | 6 +++---
 1 file changed, 3 insertions(+), 3 deletions(-)

diff --git a/arch/s390/net/bpf_jit_comp.c

b/arch/s390/net/bpf_jit_comp.c
index 88419263a89a..f6cdf13285ed 100644

--- a/arch/s390/net/bpf_jit_comp.c
+++ b/arch/s390/net/bpf_jit_comp.c

@@ -1363,7 +1363,7 @@ static noinline int bpf_jit_insn(struct bpf_jit

*jit, struct bpf_prog *fp,
                                 jit->prg);

                /*
-                * if (tail_call_cnt++ > MAX_TAIL_CALL_CNT)
+                * if (tail_call_cnt++ >= MAX_TAIL_CALL_CNT)
                 *         goto out;
                 */

@@ -1377,8 +1377,8 @@ static noinline int bpf_jit_insn(struct bpf_jit

*jit, struct bpf_prog *fp,
                EMIT6_DISP_LH(0xeb000000, 0x00fa, REG_W1, REG_W0,
REG_15, off);
                /* clij %w1,MAX_TAIL_CALL_CNT,0x2,out */

This comment needs to be updated as well.

quoted

                patch_2_clij = jit->prg;
-               EMIT6_PCREL_RIEC(0xec000000, 0x007f, REG_W1,
MAX_TAIL_CALL_CNT,
-                                2, jit->prg);
+               EMIT6_PCREL_RIEC(0xec000000, 0x007f, REG_W1,
+                                MAX_TAIL_CALL_CNT - 1, 2, jit->prg);

                /*
                 * prog = array->ptrs[index];

With that:

Tested-by: Ilya Leoshkevich <iii@linux.ibm.com>
Acked-by: Ilya Leoshkevich <iii@linux.ibm.com>

Fixing it. Thanks!

On Mon, Aug 09, 2021 at 11:34:30AM +0200, Johan Almbladh wrote:

A new test of tail call count limiting revealed that the interpreter
did in fact allow up to MAX_TAIL_CALL_CNT + 1 tail calls, whereas the
x86 JITs stopped at the intended MAX_TAIL_CALL_CNT. The interpreter was
fixed in commit b61a28cf11d61f512172e673b8f8c4a6c789b425 ("bpf: Fix
off-by-one in tail call count limiting"). This patch set fixes all
arch-specific JITs except for RISC-V.

I'm a bit surprised by this because I had previously tested the tail
call limit of several JIT compilers and found it to be 33 (i.e.,
allowing chains of up to 34 programs). I've just extended a test program
I had to validate this again on the x86-64 JIT and found a limit of 33
tail calls again [1].

Also note we had previously changed the RISC-V and MIPS JITs to allow up
to 33 tail calls [2, 3], for consistency with other JITs and with the
interpreter. We had decided to increase these two to 33 rather than
decrease the other JITs to 32 for backward compatibility, though that
probably doesn't matter much as I'd expect few people to actually use 33
tail calls :-)

1 - https://github.com/pchaigno/tail-call-bench/commit/ae7887482985b4b1745c9b2ef7ff9ae506c82886
2 - 96bc4432 ("bpf, riscv: Limit to 33 tail calls")
3 - e49e6f6d ("bpf, mips: Limit to 33 tail calls")

For each of the affected JITs, the incorrect behaviour was verified
by running the test_bpf test suite in QEMU. After the fixes, the JITs
pass the tail call count limiting test.

If you are referring to test_tailcall_3 and its associated BPF program
tailcall3, then as far as I can tell, it checks that 33 tail calls are
allowed. The counter is incremented before each tail call except the
first one. The last tail call is rejected because we reach the limit, so
a counter value of 33 (as checked in the test code) means we've
successfully executed 33 tail calls.

--
Paul

I have not been able to test the RISC-V JITs due to the lack of a
working toolchain and QEMU setup. It is likely that the RISC-V JITs
have the off-by-one behaviour too. I have not verfied any of the NIC JITs.

Link: https://lore.kernel.org/bpf/20210728164741.350370-1-johan.almbladh@anyfinetworks.com/

Johan Almbladh (7):
  arm: bpf: Fix off-by-one in tail call count limiting
  arm64: bpf: Fix off-by-one in tail call count limiting
  powerpc: bpf: Fix off-by-one in tail call count limiting
  s390: bpf: Fix off-by-one in tail call count limiting
  sparc: bpf: Fix off-by-one in tail call count limiting
  mips: bpf: Fix off-by-one in tail call count limiting
  x86: bpf: Fix comments on tail call count limiting

 arch/arm/net/bpf_jit_32.c         | 6 +++---
 arch/arm64/net/bpf_jit_comp.c     | 4 ++--
 arch/mips/net/ebpf_jit.c          | 4 ++--
 arch/powerpc/net/bpf_jit_comp32.c | 4 ++--
 arch/powerpc/net/bpf_jit_comp64.c | 4 ++--
 arch/s390/net/bpf_jit_comp.c      | 6 +++---
 arch/sparc/net/bpf_jit_comp_64.c  | 2 +-
 arch/x86/net/bpf_jit_comp32.c     | 6 +++---
 8 files changed, 18 insertions(+), 18 deletions(-)

--
2.25.1

On Thu, Aug 12, 2021 at 6:37 PM Paul Chaignon [off-list ref] wrote:

On Mon, Aug 09, 2021 at 11:34:30AM +0200, Johan Almbladh wrote:

quoted

A new test of tail call count limiting revealed that the interpreter
did in fact allow up to MAX_TAIL_CALL_CNT + 1 tail calls, whereas the
x86 JITs stopped at the intended MAX_TAIL_CALL_CNT. The interpreter was
fixed in commit b61a28cf11d61f512172e673b8f8c4a6c789b425 ("bpf: Fix
off-by-one in tail call count limiting"). This patch set fixes all
arch-specific JITs except for RISC-V.

I'm a bit surprised by this because I had previously tested the tail
call limit of several JIT compilers and found it to be 33 (i.e.,
allowing chains of up to 34 programs). I've just extended a test program
I had to validate this again on the x86-64 JIT and found a limit of 33
tail calls again [1].

Hmm, that was surprising. I have been working on a MIPS32 JIT, and as
a part of that I have been extending the in-kernel test suite in
lib/test_bpf.c. The additional tests include a suite for testing tail
calls and associated error paths. The tests were merged to bpf-next
[1].

The tail call limit test is a very simple BPF program that increments
R1, sets R0 to R1, and then calls itself again with a tail call. Since
the program is called with R1=0, the return value R0 will then be 1 +
number of tail calls executed. When I ran this on x86 I got the
following result.

Interpreter: 34
x86_64 JIT: 33
i386 JIT: 33

So, the interpreter and the x86 JITs had different behaviours. It was
then decided to change the interpreter to allow 32 tail calls to match
the behaviour of the x86 JITs [2]. As a follow up on that, I tested
the other JITs except RISC-V in the same way, and found that they too
allowed one more tail call than the now-updated [3] interpreter. This
patch set updates the behaviour of those JITs as well.

[1] https://lore.kernel.org/bpf/20210809091829.810076-1-johan.almbladh@anyfinetworks.com/
[2] https://lore.kernel.org/bpf/5afe26c6-7ab1-88ab-a3e0-eb007256a856@iogearbox.net/
[3] b61a28cf1 ("bpf: Fix off-by-one in tail call count limiting")

Also note we had previously changed the RISC-V and MIPS JITs to allow up
to 33 tail calls [2, 3], for consistency with other JITs and with the
interpreter. We had decided to increase these two to 33 rather than
decrease the other JITs to 32 for backward compatibility, though that
probably doesn't matter much as I'd expect few people to actually use 33
tail calls :-)

Right, the backwards compatibility aspect is a valid point. I don't
think anyone would be near that limit though, :-) but still.

Whether the limit is 32 or 33 really doesn't matter. My only concern
here is that the limit should be the same across all JIT
implementations and the interpreter. We could instead change the x86
JITs and revert the interpreter change to let the limit be 33, if that
would be a better solution.

1 - https://github.com/pchaigno/tail-call-bench/commit/ae7887482985b4b1745c9b2ef7ff9ae506c82886
2 - 96bc4432 ("bpf, riscv: Limit to 33 tail calls")
3 - e49e6f6d ("bpf, mips: Limit to 33 tail calls")

quoted

For each of the affected JITs, the incorrect behaviour was verified
by running the test_bpf test suite in QEMU. After the fixes, the JITs
pass the tail call count limiting test.

If you are referring to test_tailcall_3 and its associated BPF program
tailcall3, then as far as I can tell, it checks that 33 tail calls are
allowed. The counter is incremented before each tail call except the
first one. The last tail call is rejected because we reach the limit, so
a counter value of 33 (as checked in the test code) means we've
successfully executed 33 tail calls.

My test setup can build for all architectures included in this patch
set and some more, and then boot the kernel in QEMU with a
statically-linked busybox as userspace. I can easily run the kernel's
BPF test suite on all those architectures, but since I don't have a
full-fledged userspace I have not been able to run the selftests in
the same way.

We need to be able to determine what the tail call limit actually is
for the different implementations. I don't understand why you get
different results when testing from userspace compared to testing the
JIT itself. Either one of the tests is faulty, or there is some other
mechanism at play here.

Johan

quoted

I have not been able to test the RISC-V JITs due to the lack of a
working toolchain and QEMU setup. It is likely that the RISC-V JITs
have the off-by-one behaviour too. I have not verfied any of the NIC JITs.

Link: https://lore.kernel.org/bpf/20210728164741.350370-1-johan.almbladh@anyfinetworks.com/

Johan Almbladh (7):
  arm: bpf: Fix off-by-one in tail call count limiting
  arm64: bpf: Fix off-by-one in tail call count limiting
  powerpc: bpf: Fix off-by-one in tail call count limiting
  s390: bpf: Fix off-by-one in tail call count limiting
  sparc: bpf: Fix off-by-one in tail call count limiting
  mips: bpf: Fix off-by-one in tail call count limiting
  x86: bpf: Fix comments on tail call count limiting

 arch/arm/net/bpf_jit_32.c         | 6 +++---
 arch/arm64/net/bpf_jit_comp.c     | 4 ++--
 arch/mips/net/ebpf_jit.c          | 4 ++--
 arch/powerpc/net/bpf_jit_comp32.c | 4 ++--
 arch/powerpc/net/bpf_jit_comp64.c | 4 ++--
 arch/s390/net/bpf_jit_comp.c      | 6 +++---
 arch/sparc/net/bpf_jit_comp_64.c  | 2 +-
 arch/x86/net/bpf_jit_comp32.c     | 6 +++---
 8 files changed, 18 insertions(+), 18 deletions(-)

--
2.25.1