Re: [PATCH v5 bpf-next 1/3] bpf, x64: Fix tailcall hierarchy

[Eduard Zingerman <eddyz87@gmail.com>]

On Mon, 2024-06-24 at 00:15 +0800, Leon Hwang wrote:
> This patch fixes a tailcall issue caused by abusing the tailcall in
> bpf2bpf feature.
> 
> As we know, tail_call_cnt propagates by rax from caller to callee when
> to call subprog in tailcall context. But, like the following example,
> MAX_TAIL_CALL_CNT won't work because of missing tail_call_cnt
> back-propagation from callee to caller.
> 
> \#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_tail1(struct __sk_buff *skb)
> {
> 	bpf_tail_call_static(skb, &jmp_table, 0);
> 	return 0;
> }
> 
> static __noinline
> int subprog_tail2(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_tail1(skb);
> 	subprog_tail2(skb);
> 
> 	return ret;
> }
> 
> char __license[] SEC("license") = "GPL";
> 
> At run time, the tail_call_cnt in entry() will be propagated to
> subprog_tail1() and subprog_tail2(). But, when the tail_call_cnt in
> subprog_tail1() updates when bpf_tail_call_static(), the tail_call_cnt
> in entry() won't be updated at the same time. As a result, in entry(),
> when tail_call_cnt in entry() is less than MAX_TAIL_CALL_CNT and
> subprog_tail1() returns because of MAX_TAIL_CALL_CNT limit,
> bpf_tail_call_static() in suprog_tail2() is able to run because the
> tail_call_cnt in subprog_tail2() propagated from entry() is less than
> MAX_TAIL_CALL_CNT.
> 
> So, how many tailcalls are there for this case if no error happens?
> 
> From top-down view, does it look like hierarchy layer and layer?
> 
> With this view, there will be 2+4+8+...+2^33 = 2^34 - 2 = 17,179,869,182
> tailcalls for this case.
> 
> How about there are N subprog_tail() in entry()? There will be almost
> N^34 tailcalls.
> 
> Then, in this patch, it resolves this case on x86_64.
> 
> In stead of propagating tail_call_cnt from caller to callee, it
> propagates its pointer, tail_call_cnt_ptr, tcc_ptr for short.
> 
> However, where does it store tail_call_cnt?
> 
> It stores tail_call_cnt on the stack of main prog. When tail call
> happens in subprog, it increments tail_call_cnt by tcc_ptr.
> 
> Meanwhile, it stores tail_call_cnt_ptr on the stack of main prog, too.
> 
> And, before jump to tail callee, it has to pop tail_call_cnt and
> tail_call_cnt_ptr.
> 
> Then, at the prologue of subprog, it must not make rax as
> tail_call_cnt_ptr again. It has to reuse tail_call_cnt_ptr from caller.
> 
> As a result, at run time, it has to recognize rax is tail_call_cnt or
> tail_call_cnt_ptr at prologue by:
> 
> 1. rax is tail_call_cnt if rax is <= MAX_TAIL_CALL_CNT.
> 2. rax is tail_call_cnt_ptr if rax is > MAX_TAIL_CALL_CNT, because a
>    pointer won't be <= MAX_TAIL_CALL_CNT.
> 
> Furthermore, when trampoline is the caller of bpf prog, which is
> tail_call_reachable, it is required to propagate rax through 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@gmail.com>
> ---

Hi Leon,

Sorry for delayed response.
I've looked through this patch and the changes make sense to me.
One thing that helped to understand the gist of the changes,
was dumping jited program using bpftool and annotating it with comments:
https://gist.github.com/eddyz87/0d48da052e9d174b2bb84174295c4215
Maybe consider adding something along these lines to the patch
description?
  
Reviewed-by: Eduard Zingerman <eddyz87@gmail.com>

[...]