>From commit ebf7d1f508a73871 ("bpf, x64: rework pro/epilogue and tailcall
handling in JIT"), the tailcall on x64 works better than before.
>From commit e411901c0b775a3a ("bpf: allow for tailcalls in BPF subprograms
for x64 JIT"), tailcall is able to run in BPF subprograms on x64.
How about:
1. More than 1 subprograms are called in a bpf program.
2. The tailcalls in the subprograms call the bpf program.
Because of missing tail_call_cnt back-propagation, a tailcall hierarchy
comes up. And MAX_TAIL_CALL_CNT limit does not work for this case.
Let's take a look into an example:
\#include <linux/bpf.h>
\#include <bpf/bpf_helpers.h>
\#include "bpf_legacy.h"
struct {
__uint(type, BPF_MAP_TYPE_PROG_ARRAY);
__uint(max_entries, 1);
__uint(key_size, sizeof(__u32));
__uint(value_size, sizeof(__u32));
} jmp_table SEC(".maps");
int count = 0;
static __noinline
int subprog_tail(struct __sk_buff *skb)
{
bpf_tail_call_static(skb, &jmp_table, 0);
return 0;
}
SEC("tc")
int entry(struct __sk_buff *skb)
{
volatile int ret = 1;
count++;
subprog_tail(skb); /* subprog call1 */
subprog_tail(skb); /* subprog call2 */
return ret;
}
char __license[] SEC("license") = "GPL";
And the entry bpf prog is populated to the 0th slot of jmp_table. Then,
what happens when entry bpf prog runs? The CPU will be stalled because
of too many tailcalls, e.g. the test_progs failed to run on aarch64 and
s390x because of "rcu: INFO: rcu_sched self-detected stall on CPU".
So, if CPU does not stall because of too many tailcalls, how many
tailcalls will be there for this case? And why MAX_TAIL_CALL_CNT limit
does not work for this case?
Let's step into some running steps.
At the very first time when subprog_tail() is called, subprog_tail() does
tailcall the entry bpf prog. Then, subprog_taill() is called at second time
at the position subprog call1, and it tailcalls the entry bpf prog again.
Then, again and again. At the very first time when MAX_TAIL_CALL_CNT limit
works, subprog_tail() has been called for 34 times at the position subprog
call1. And at this time, the tail_call_cnt is 33 in subprog_tail().
Next, the 34th subprog_tail() returns to entry() because of
MAX_TAIL_CALL_CNT limit.
In entry(), the 34th entry(), at the time after the 34th subprog_tail() at
the position subprog call1 finishes and before the 1st subprog_tail() at
the position subprog call2 calls in entry(), what's the value of
tail_call_cnt in entry()? It's 33.
As we know, tail_all_cnt is pushed on the stack of entry(), and propagates
to subprog_tail() by %rax from stack.
Then, at the time when subprog_tail() at the position subprog call2 is
called for its first time, tail_call_cnt 33 propagates to subprog_tail()
by %rax. And the tailcall in subprog_tail() is aborted because of
tail_call_cnt >= MAX_TAIL_CALL_CNT too.
Then, subprog_tail() at the position subprog call2 ends, and the 34th
entry() ends. And it returns to the 33rd subprog_tail() called from the
position subprog call1. But wait, at this time, what's the value of
tail_call_cnt under the stack of subprog_tail()? It's 33.
Then, in the 33rd entry(), at the time after the 33th subprog_tail() at
the position subprog call1 finishes and before the 2nd subprog_tail() at
the position subprog call2 calls, what's the value of tail_call_cnt
in current entry()? It's *32*. Why not 33?
Before stepping into subprog_tail() at the position subprog call2 in 33rd
entry(), like stopping the time machine, let's have a look at the stack
memory:
| STACK |
+---------+ RBP <-- current rbp
| ret | STACK of 33rd entry()
| tcc | its value is 32
+---------+ RSP <-- current rsp
| rip | STACK of 34rd entry()
| rbp | reuse the STACK of 33rd subprog_tail() at the position
| ret | subprog call1
| tcc | its value is 33
+---------+ rsp
| rip | STACK of 1st subprog_tail() at the position subprog call2
| rbp |
| tcc | its value is 33
+---------+ rsp
Why not 33? It's because tail_call_cnt does not back-propagate from
subprog_tail() to entry().
Then, while stepping into subprog_tail() at the position subprog call2 in
33rd entry():
| STACK |
+---------+
| ret | STACK of 33rd entry()
| tcc | its value is 32
| rip |
| rbp |
+---------+ RBP <-- current rbp
| tcc | its value is 32; STACK of subprog_tail() at the position
+---------+ RSP <-- current rsp subprog call2
Then, while pausing after tailcalling in 2nd subprog_tail() at the position
subprog call2:
| STACK |
+---------+
| ret | STACK of 33rd entry()
| tcc | its value is 32
| rip |
| rbp |
+---------+ RBP <-- current rbp
| tcc | its value is 33; STACK of subprog_tail() at the position
+---------+ RSP <-- current rsp subprog call2
Note: what happens to tail_call_cnt:
/*
* if (tail_call_cnt++ >= MAX_TAIL_CALL_CNT)
* goto out;
*/
It's to check >= MAX_TAIL_CALL_CNT first and then increment tail_call_cnt.
So, current tailcall is allowed to run.
Then, entry() is tailcalled. And the stack memory status is:
| STACK |
+---------+
| ret | STACK of 33rd entry()
| tcc | its value is 32
| rip |
| rbp |
+---------+ RBP <-- current rbp
| ret | STACK of 35th entry(); reuse STACK of subprog_tail() at the
| tcc | its value is 33 the position subprog call2
+---------+ RSP <-- current rsp
So, the tailcalls in the 35th entry() will be aborted.
And, ..., again and again. :(
And, I hope you have understood the reason why MAX_TAIL_CALL_CNT limit
does not work for this case.
And, how many tailcalls are there for this case if CPU does not stall?
>From top-down view, does it look like hierarchy layer and layer?
I think it is a hierarchy layer model with 2+4+8+...+2**33 tailcalls. As a
result, if CPU does not stall, there will be 2**34 - 2 = 17,179,869,182
tailcalls. That's the guy making CPU stalled.
What about there are N subprog_tail() in entry()? If CPU does not stall
because of too many tailcalls, there will be almost N**34 tailcalls.
As we learn about the issue, how does this patch resolve it?
In this patch, it stores tail_call_cnt at task_struct. When a tailcall
happens, the caller and callee bpf progs are in the same thread context,
which means the current task_struct won't change after a tailcall.
First, at the prologue of bpf prog, it initialise the tail_call_cnt at
task_struct.
Then, when a tailcall happens, it compares tail_call_cnt with
MAX_TAIL_CALL_CNT, and then increments it.
Additionally, in order to avoid touching other registers excluding %rax,
it uses asm to handle tail_call_cnt at task_struct.
As a result, the previous tailcall way can be removed totally, including
1. "push rax" at prologue.
2. load tail_call_cnt to rax before calling function.
3. "pop rax" before jumping to tailcallee when tailcall.
4. "push rax" and load tail_call_cnt to rax at trampoline.
Fixes: ebf7d1f508a7 ("bpf, x64: rework pro/epilogue and tailcall handling in JIT")
Fixes: e411901c0b77 ("bpf: allow for tailcalls in BPF subprograms for x64 JIT")
Signed-off-by: Leon Hwang <hffilwlqm@xxxxxxxxx>
---
arch/x86/net/bpf_jit_comp.c | 137 +++++++++++++++++++++---------------
1 file changed, 81 insertions(+), 56 deletions(-)
diff --git a/arch/x86/net/bpf_jit_comp.c b/arch/x86/net/bpf_jit_comp.c
index 3b639d6f2f54d..cd06e02e83b64 100644
--- a/arch/x86/net/bpf_jit_comp.c
+++ b/arch/x86/net/bpf_jit_comp.c
@@ -11,6 +11,7 @@
#include <linux/bpf.h>
#include <linux/memory.h>
#include <linux/sort.h>
+#include <linux/sched.h>
#include <asm/extable.h>
#include <asm/ftrace.h>
#include <asm/set_memory.h>
@@ -18,6 +19,8 @@
#include <asm/text-patching.h>
#include <asm/unwind.h>
#include <asm/cfi.h>
+#include <asm/current.h>
+#include <asm/percpu.h>
static bool all_callee_regs_used[4] = {true, true, true, true};
@@ -273,7 +276,7 @@ struct jit_context {
/* Number of bytes emit_patch() needs to generate instructions */
#define X86_PATCH_SIZE 5
/* Number of bytes that will be skipped on tailcall */
-#define X86_TAIL_CALL_OFFSET (11 + ENDBR_INSN_SIZE)
+#define X86_TAIL_CALL_OFFSET (14 + ENDBR_INSN_SIZE)
static void push_r12(u8 **pprog)
{
@@ -403,6 +406,9 @@ static void emit_cfi(u8 **pprog, u32 hash)
*pprog = prog;
}
+static int emit_call(u8 **pprog, void *func, void *ip);
+static __used void bpf_tail_call_cnt_init(void);
+
/*
* Emit x86-64 prologue code for BPF program.
* bpf_tail_call helper will skip the first X86_TAIL_CALL_OFFSET bytes
@@ -410,9 +416,9 @@ static void emit_cfi(u8 **pprog, u32 hash)
*/
static void emit_prologue(u8 **pprog, u32 stack_depth, bool ebpf_from_cbpf,
bool tail_call_reachable, bool is_subprog,
- bool is_exception_cb)
+ bool is_exception_cb, u8 *ip)
{
- u8 *prog = *pprog;
+ u8 *prog = *pprog, *start = *pprog;
emit_cfi(&prog, is_subprog ? cfi_bpf_subprog_hash : cfi_bpf_hash);
/* BPF trampoline can be made to work without these nops,
@@ -421,13 +427,14 @@ static void emit_prologue(u8 **pprog, u32 stack_depth, bool ebpf_from_cbpf,
emit_nops(&prog, X86_PATCH_SIZE);
if (!ebpf_from_cbpf) {
if (tail_call_reachable && !is_subprog)
- /* When it's the entry of the whole tailcall context,
- * zeroing rax means initialising tail_call_cnt.
+ /* Call bpf_tail_call_cnt_init to initilise
+ * tail_call_cnt.
*/
- EMIT2(0x31, 0xC0); /* xor eax, eax */
+ emit_call(&prog, bpf_tail_call_cnt_init,
+ ip + (prog - start));
else
/* Keep the same instruction layout. */
- EMIT2(0x66, 0x90); /* nop2 */
+ emit_nops(&prog, X86_PATCH_SIZE);
}
/* Exception callback receives FP as third parameter */
if (is_exception_cb) {
@@ -452,8 +459,6 @@ static void emit_prologue(u8 **pprog, u32 stack_depth, bool ebpf_from_cbpf,
/* sub rsp, rounded_stack_depth */
if (stack_depth)
EMIT3_off32(0x48, 0x81, 0xEC, round_up(stack_depth, 8));
- if (tail_call_reachable)
- EMIT1(0x50); /* push rax */
*pprog = prog;
}
@@ -589,13 +594,61 @@ static void emit_return(u8 **pprog, u8 *ip)
*pprog = prog;
}
+static __used void bpf_tail_call_cnt_init(void)
+{
+ /* The following asm equals to
+ *
+ * u32 *tcc_ptr = ¤t->bpf_tail_call_cnt;
+ *
+ * *tcc_ptr = 0;
+ */
+
+ asm volatile (
+ "addq " __percpu_arg(0) ", %1\n\t"
+ "addq %2, %1\n\t"
+ "movq (%1), %1\n\t"
+ "addq %3, %1\n\t"
+ "movl $0, (%1)\n\t"
+ :
+ : "m" (this_cpu_off), "r" (&pcpu_hot),
+ "i" (offsetof(struct pcpu_hot, current_task)),
+ "i" (offsetof(struct task_struct, bpf_tail_call_cnt))
+ );
+}
+
+static __used u32 *bpf_tail_call_cnt_ptr(void)
+{
+ u32 *tcc_ptr;
+
+ /* The following asm equals to
+ *
+ * u32 *tcc_ptr = ¤t->bpf_tail_call_cnt;
+ *
+ * return tcc_ptr;
+ */
+
+ asm volatile (
+ "addq " __percpu_arg(1) ", %2\n\t"
+ "addq %3, %2\n\t"
+ "movq (%2), %2\n\t"
+ "addq %4, %2\n\t"
+ "movq %2, %0\n\t"
+ : "=r" (tcc_ptr)
+ : "m" (this_cpu_off), "r" (&pcpu_hot),
+ "i" (offsetof(struct pcpu_hot, current_task)),
+ "i" (offsetof(struct task_struct, bpf_tail_call_cnt))
+ );
+
+ return tcc_ptr;
+}
+
/*
* Generate the following code:
*
* ... 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 ((*tcc_ptr)++ >= MAX_TAIL_CALL_CNT)
* goto out;
* prog = array->ptrs[index];
* if (prog == NULL)
@@ -608,7 +661,6 @@ static void emit_bpf_tail_call_indirect(struct bpf_prog *bpf_prog,
u32 stack_depth, u8 *ip,
struct jit_context *ctx)
{
- int tcc_off = -4 - round_up(stack_depth, 8);
u8 *prog = *pprog, *start = *pprog;
int offset;
@@ -630,16 +682,16 @@ static void emit_bpf_tail_call_indirect(struct bpf_prog *bpf_prog,
EMIT2(X86_JBE, offset); /* jbe out */
/*
- * if (tail_call_cnt++ >= MAX_TAIL_CALL_CNT)
+ * if ((*tcc_ptr)++ >= MAX_TAIL_CALL_CNT)
* goto out;
*/
- 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 */
+ /* call bpf_tail_call_cnt_ptr */
+ emit_call(&prog, bpf_tail_call_cnt_ptr, ip + (prog - start));
+ EMIT3(0x83, 0x38, MAX_TAIL_CALL_CNT); /* cmp dword ptr [rax], MAX_TAIL_CALL_CNT */
offset = ctx->tail_call_indirect_label - (prog + 2 - start);
EMIT2(X86_JAE, offset); /* jae out */
- EMIT3(0x83, 0xC0, 0x01); /* add eax, 1 */
- EMIT2_off32(0x89, 0x85, tcc_off); /* mov dword ptr [rbp - tcc_off], eax */
+ EMIT2(0xFF, 0x00); /* inc dword ptr [rax] */
/* prog = array->ptrs[index]; */
EMIT4_off32(0x48, 0x8B, 0x8C, 0xD6, /* mov rcx, [rsi + rdx * 8 + offsetof(...)] */
@@ -663,7 +715,6 @@ static void emit_bpf_tail_call_indirect(struct bpf_prog *bpf_prog,
pop_r12(&prog);
}
- EMIT1(0x58); /* pop rax */
if (stack_depth)
EMIT3_off32(0x48, 0x81, 0xC4, /* add rsp, sd */
round_up(stack_depth, 8));
@@ -691,21 +742,20 @@ static void emit_bpf_tail_call_direct(struct bpf_prog *bpf_prog,
bool *callee_regs_used, u32 stack_depth,
struct jit_context *ctx)
{
- int tcc_off = -4 - round_up(stack_depth, 8);
u8 *prog = *pprog, *start = *pprog;
int offset;
/*
- * if (tail_call_cnt++ >= MAX_TAIL_CALL_CNT)
+ * if ((*tcc_ptr)++ >= MAX_TAIL_CALL_CNT)
* goto out;
*/
- 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 */
+ /* call bpf_tail_call_cnt_ptr */
+ emit_call(&prog, bpf_tail_call_cnt_ptr, ip);
+ EMIT3(0x83, 0x38, MAX_TAIL_CALL_CNT); /* cmp dword ptr [rax], MAX_TAIL_CALL_CNT */
offset = ctx->tail_call_direct_label - (prog + 2 - start);
EMIT2(X86_JAE, offset); /* jae out */
- EMIT3(0x83, 0xC0, 0x01); /* add eax, 1 */
- EMIT2_off32(0x89, 0x85, tcc_off); /* mov dword ptr [rbp - tcc_off], eax */
+ EMIT2(0xFF, 0x00); /* inc dword ptr [rax] */
poke->tailcall_bypass = ip + (prog - start);
poke->adj_off = X86_TAIL_CALL_OFFSET;
@@ -724,7 +774,6 @@ static void emit_bpf_tail_call_direct(struct bpf_prog *bpf_prog,
pop_r12(&prog);
}
- EMIT1(0x58); /* pop rax */
if (stack_depth)
EMIT3_off32(0x48, 0x81, 0xC4, round_up(stack_depth, 8));
@@ -1262,10 +1311,6 @@ static void emit_shiftx(u8 **pprog, u32 dst_reg, u8 src_reg, bool is64, u8 op)
#define INSN_SZ_DIFF (((addrs[i] - addrs[i - 1]) - (prog - temp)))
-/* mov rax, qword ptr [rbp - rounded_stack_depth - 8] */
-#define RESTORE_TAIL_CALL_CNT(stack) \
- EMIT3_off32(0x48, 0x8B, 0x85, -round_up(stack, 8) - 8)
-
static int do_jit(struct bpf_prog *bpf_prog, int *addrs, u8 *image, u8 *rw_image,
int oldproglen, struct jit_context *ctx, bool jmp_padding)
{
@@ -1293,7 +1338,8 @@ static int do_jit(struct bpf_prog *bpf_prog, int *addrs, u8 *image, u8 *rw_image
emit_prologue(&prog, bpf_prog->aux->stack_depth,
bpf_prog_was_classic(bpf_prog), tail_call_reachable,
- bpf_is_subprog(bpf_prog), bpf_prog->aux->exception_cb);
+ bpf_is_subprog(bpf_prog), bpf_prog->aux->exception_cb,
+ image);
/* Exception callback will clobber callee regs for its own use, and
* restore the original callee regs from main prog's stack frame.
*/
@@ -1973,17 +2019,11 @@ st: if (is_imm8(insn->off))
case BPF_JMP | BPF_CALL: {
int offs;
+ if (!imm32)
+ return -EINVAL;
+
func = (u8 *) __bpf_call_base + imm32;
- if (tail_call_reachable) {
- RESTORE_TAIL_CALL_CNT(bpf_prog->aux->stack_depth);
- if (!imm32)
- return -EINVAL;
- offs = 7 + x86_call_depth_emit_accounting(&prog, func);
- } else {
- if (!imm32)
- return -EINVAL;
- offs = x86_call_depth_emit_accounting(&prog, func);
- }
+ offs = x86_call_depth_emit_accounting(&prog, func);
if (emit_call(&prog, func, image + addrs[i - 1] + offs))
return -EINVAL;
break;
@@ -2773,7 +2813,6 @@ static int __arch_prepare_bpf_trampoline(struct bpf_tramp_image *im, void *rw_im
* [ ... ]
* [ stack_arg2 ]
* RBP - arg_stack_off [ stack_arg1 ]
- * RSP [ tail_call_cnt ] BPF_TRAMP_F_TAIL_CALL_CTX
*/
/* room for return value of orig_call or fentry prog */
@@ -2845,8 +2884,6 @@ static int __arch_prepare_bpf_trampoline(struct bpf_tramp_image *im, void *rw_im
/* sub rsp, stack_size */
EMIT4(0x48, 0x83, 0xEC, stack_size);
}
- if (flags & BPF_TRAMP_F_TAIL_CALL_CTX)
- EMIT1(0x50); /* push rax */
/* mov QWORD PTR [rbp - rbx_off], rbx */
emit_stx(&prog, BPF_DW, BPF_REG_FP, BPF_REG_6, -rbx_off);
@@ -2901,16 +2938,9 @@ static int __arch_prepare_bpf_trampoline(struct bpf_tramp_image *im, void *rw_im
restore_regs(m, &prog, regs_off);
save_args(m, &prog, arg_stack_off, true);
- if (flags & BPF_TRAMP_F_TAIL_CALL_CTX) {
- /* Before calling the original function, restore the
- * tail_call_cnt from stack to rax.
- */
- RESTORE_TAIL_CALL_CNT(stack_size);
- }
-
if (flags & BPF_TRAMP_F_ORIG_STACK) {
- emit_ldx(&prog, BPF_DW, BPF_REG_6, BPF_REG_FP, 8);
- EMIT2(0xff, 0xd3); /* call *rbx */
+ emit_ldx(&prog, BPF_DW, BPF_REG_0, BPF_REG_FP, 8);
+ EMIT2(0xff, 0xd0); /* call *rax */
} else {
/* call original function */
if (emit_rsb_call(&prog, orig_call, image + (prog - (u8 *)rw_image))) {
@@ -2963,11 +2993,6 @@ static int __arch_prepare_bpf_trampoline(struct bpf_tramp_image *im, void *rw_im
ret = -EINVAL;
goto cleanup;
}
- } else if (flags & BPF_TRAMP_F_TAIL_CALL_CTX) {
- /* Before running the original function, restore the
- * tail_call_cnt from stack to rax.
- */
- RESTORE_TAIL_CALL_CNT(stack_size);
}
/* restore return value of orig_call or fentry prog back into RAX */
--
2.44.0
