[PATCH bpf-next 0/2] bpf, x64: Introduce two tailcall enhancements

[PATCH bpf-next 0/2] bpf, x64: Introduce two tailcall enhancements

[Leon Hwang]

This patch set introduces two enhancements aimed at improving tailcall
handling in the x64 JIT:

1. Tailcall info is propagated to a subprog only if the subprog is
   tail_call_reachable.
2. Tailcall info is propagated through the trampoline only when the target
   is a subprog and it is tail_call_reachable.

Leon Hwang (2):
  bpf, x64: Propagate tailcall info only for tail_call_reachable
    subprogs
  bpf, verifier: Check trampoline attach target is tail_call_reachable
    subprog

 arch/x86/net/bpf_jit_comp.c |  4 +++-
 include/linux/bpf.h         |  1 +
 kernel/bpf/verifier.c       | 10 +++++++++-
 3 files changed, 13 insertions(+), 2 deletions(-)

-- 
2.44.0

[PATCH bpf-next 1/2] bpf, x64: Propagate tailcall info only for tail_call_reachable subprogs

[Leon Hwang]

In the x86_64 JIT, when calling a function, tailcall info is propagated if
the program is tail_call_reachable, regardless of whether the function is a
subprog, helper, or kfunc. However, this propagation is unnecessary for
not-tail_call_reachable subprogs, helpers, or kfuncs.

The verifier can determine if a subprog is tail_call_reachable. Therefore,
it can be optimized to only propagate tailcall info when the callee is
subprog and the subprog is actually tail_call_reachable.

Signed-off-by: Leon Hwang <leon.hwang@linux.dev>
---
 arch/x86/net/bpf_jit_comp.c | 4 +++-
 kernel/bpf/verifier.c       | 6 ++++++
 2 files changed, 9 insertions(+), 1 deletion(-)

diff --git a/arch/x86/net/bpf_jit_comp.c b/arch/x86/net/bpf_jit_comp.c
index 06b080b61aa57..6ad6886ecfc88 100644
--- a/arch/x86/net/bpf_jit_comp.c
+++ b/arch/x86/net/bpf_jit_comp.c
@@ -2124,10 +2124,12 @@ st:			if (is_imm8(insn->off))
 
 			/* call */
 		case BPF_JMP | BPF_CALL: {
+			bool pseudo_call = src_reg == BPF_PSEUDO_CALL;
+			bool subprog_tail_call_reachable = dst_reg;
 			u8 *ip = image + addrs[i - 1];
 
 			func = (u8 *) __bpf_call_base + imm32;
-			if (tail_call_reachable) {
+			if (pseudo_call && subprog_tail_call_reachable) {
 				LOAD_TAIL_CALL_CNT_PTR(bpf_prog->aux->stack_depth);
 				ip += 7;
 			}
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index f514247ba8ba8..6e7e42c7bc7b1 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -19990,6 +19990,12 @@ static int jit_subprogs(struct bpf_verifier_env *env)
 			insn[0].imm = (u32)addr;
 			insn[1].imm = addr >> 32;
 		}
+
+		if (bpf_pseudo_call(insn))
+			/* In the x86_64 JIT, tailcall information can only be
+			 * propagated if the subprog is tail_call_reachable.
+			 */
+			insn->dst_reg = env->subprog_info[subprog].tail_call_reachable;
 	}
 
 	err = bpf_prog_alloc_jited_linfo(prog);
-- 
2.44.0

[PATCH bpf-next 2/2] bpf, verifier: Check trampoline target is tail_call_reachable subprog

[Leon Hwang]

In the x86_64 JIT, tailcall info is propagated through the trampoline when
the target program is tail_call_reachable. However, this propagation is
unnecessary if the target is a main prog, or a subprog that is not
tail_call_reachable.

Since the verifier can determine if a subprog is tail_call_reachable, it
should only propagate tailcall info when the target is subprog and the
subprog is actually tail_call_reachable.

Signed-off-by: Leon Hwang <leon.hwang@linux.dev>
---
 include/linux/bpf.h   | 1 +
 kernel/bpf/verifier.c | 4 +++-
 2 files changed, 4 insertions(+), 1 deletion(-)

diff --git a/include/linux/bpf.h b/include/linux/bpf.h
index 0c216e71cec76..32b56a759d788 100644
--- a/include/linux/bpf.h
+++ b/include/linux/bpf.h
@@ -1220,6 +1220,7 @@ struct bpf_attach_target_info {
 	struct module *tgt_mod;
 	const char *tgt_name;
 	const struct btf_type *tgt_type;
+	bool tgt_tail_call_reachable;
 };
 
 #define BPF_DISPATCHER_MAX 48 /* Fits in 2048B */
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 6e7e42c7bc7b1..9a09621a8832c 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -21916,6 +21916,8 @@ int bpf_check_attach_target(struct bpf_verifier_log *log,
 			bpf_log(log, "Subprog %s doesn't exist\n", tname);
 			return -EINVAL;
 		}
+		tgt_info->tgt_tail_call_reachable = subprog &&
+						    aux->func[subprog]->aux->tail_call_reachable;
 		if (aux->func && aux->func[subprog]->aux->exception_cb) {
 			bpf_log(log,
 				"%s programs cannot attach to exception callback\n",
@@ -22285,7 +22287,7 @@ static int check_attach_btf_id(struct bpf_verifier_env *env)
 	if (!tr)
 		return -ENOMEM;
 
-	if (tgt_prog && tgt_prog->aux->tail_call_reachable)
+	if (tgt_prog && tgt_info.tgt_tail_call_reachable)
 		tr->flags = BPF_TRAMP_F_TAIL_CALL_CTX;
 
 	prog->aux->dst_trampoline = tr;
-- 
2.44.0

Re: [PATCH bpf-next 1/2] bpf, x64: Propagate tailcall info only for tail_call_reachable subprogs

[Yonghong Song]

On 10/21/24 6:39 AM, Leon Hwang wrote:
> In the x86_64 JIT, when calling a function, tailcall info is propagated if
> the program is tail_call_reachable, regardless of whether the function is a
> subprog, helper, or kfunc. However, this propagation is unnecessary for
> not-tail_call_reachable subprogs, helpers, or kfuncs.
>
> The verifier can determine if a subprog is tail_call_reachable. Therefore,
> it can be optimized to only propagate tailcall info when the callee is
> subprog and the subprog is actually tail_call_reachable.
>
> Signed-off-by: Leon Hwang <leon.hwang@linux.dev>
> ---
>   arch/x86/net/bpf_jit_comp.c | 4 +++-
>   kernel/bpf/verifier.c       | 6 ++++++
>   2 files changed, 9 insertions(+), 1 deletion(-)
>
> diff --git a/arch/x86/net/bpf_jit_comp.c b/arch/x86/net/bpf_jit_comp.c
> index 06b080b61aa57..6ad6886ecfc88 100644
> --- a/arch/x86/net/bpf_jit_comp.c
> +++ b/arch/x86/net/bpf_jit_comp.c
> @@ -2124,10 +2124,12 @@ st:			if (is_imm8(insn->off))
>   
>   			/* call */
>   		case BPF_JMP | BPF_CALL: {
> +			bool pseudo_call = src_reg == BPF_PSEUDO_CALL;
> +			bool subprog_tail_call_reachable = dst_reg;
>   			u8 *ip = image + addrs[i - 1];
>   
>   			func = (u8 *) __bpf_call_base + imm32;
> -			if (tail_call_reachable) {
> +			if (pseudo_call && subprog_tail_call_reachable) {

Why we need subprog_tail_call_reachable? Does
	tail_call_reachable && psueudo_call
work the same way?

>   				LOAD_TAIL_CALL_CNT_PTR(bpf_prog->aux->stack_depth);
>   				ip += 7;
>   			}
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index f514247ba8ba8..6e7e42c7bc7b1 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -19990,6 +19990,12 @@ static int jit_subprogs(struct bpf_verifier_env *env)
>   			insn[0].imm = (u32)addr;
>   			insn[1].imm = addr >> 32;
>   		}
> +
> +		if (bpf_pseudo_call(insn))
> +			/* In the x86_64 JIT, tailcall information can only be
> +			 * propagated if the subprog is tail_call_reachable.
> +			 */
> +			insn->dst_reg = env->subprog_info[subprog].tail_call_reachable;
>   	}
>   
>   	err = bpf_prog_alloc_jited_linfo(prog);

Re: [PATCH bpf-next 1/2] bpf, x64: Propagate tailcall info only for tail_call_reachable subprogs

[Leon Hwang]

On 22/10/24 01:49, Yonghong Song wrote:
> 
> On 10/21/24 6:39 AM, Leon Hwang wrote:
>> In the x86_64 JIT, when calling a function, tailcall info is
>> propagated if
>> the program is tail_call_reachable, regardless of whether the function
>> is a
>> subprog, helper, or kfunc. However, this propagation is unnecessary for
>> not-tail_call_reachable subprogs, helpers, or kfuncs.
>>
>> The verifier can determine if a subprog is tail_call_reachable.
>> Therefore,
>> it can be optimized to only propagate tailcall info when the callee is
>> subprog and the subprog is actually tail_call_reachable.
>>
>> Signed-off-by: Leon Hwang <leon.hwang@linux.dev>
>> ---
>>   arch/x86/net/bpf_jit_comp.c | 4 +++-
>>   kernel/bpf/verifier.c       | 6 ++++++
>>   2 files changed, 9 insertions(+), 1 deletion(-)
>>
>> diff --git a/arch/x86/net/bpf_jit_comp.c b/arch/x86/net/bpf_jit_comp.c
>> index 06b080b61aa57..6ad6886ecfc88 100644
>> --- a/arch/x86/net/bpf_jit_comp.c
>> +++ b/arch/x86/net/bpf_jit_comp.c
>> @@ -2124,10 +2124,12 @@ st:            if (is_imm8(insn->off))
>>                 /* call */
>>           case BPF_JMP | BPF_CALL: {
>> +            bool pseudo_call = src_reg == BPF_PSEUDO_CALL;
>> +            bool subprog_tail_call_reachable = dst_reg;
>>               u8 *ip = image + addrs[i - 1];
>>                 func = (u8 *) __bpf_call_base + imm32;
>> -            if (tail_call_reachable) {
>> +            if (pseudo_call && subprog_tail_call_reachable) {
> 
> Why we need subprog_tail_call_reachable? Does
>     tail_call_reachable && psueudo_call
> work the same way?
> 

'tail_call_reachable && pseudo_call' works too. However, it will
propagate tailcall info to subprog even if the subprog is not
tail_call_reachable.

subprog_tail_call_reachable indicates the subprog requires tailcall info
from its caller.
So, 'pseudo_call && subprog_tail_call_reachable' is better.

Thanks,
Leon

Re: [PATCH bpf-next 1/2] bpf, x64: Propagate tailcall info only for tail_call_reachable subprogs

[Yonghong Song]

On 10/21/24 6:46 PM, Leon Hwang wrote:
>
> On 22/10/24 01:49, Yonghong Song wrote:
>> On 10/21/24 6:39 AM, Leon Hwang wrote:
>>> In the x86_64 JIT, when calling a function, tailcall info is
>>> propagated if
>>> the program is tail_call_reachable, regardless of whether the function
>>> is a
>>> subprog, helper, or kfunc. However, this propagation is unnecessary for
>>> not-tail_call_reachable subprogs, helpers, or kfuncs.
>>>
>>> The verifier can determine if a subprog is tail_call_reachable.
>>> Therefore,
>>> it can be optimized to only propagate tailcall info when the callee is
>>> subprog and the subprog is actually tail_call_reachable.
>>>
>>> Signed-off-by: Leon Hwang <leon.hwang@linux.dev>
>>> ---
>>>    arch/x86/net/bpf_jit_comp.c | 4 +++-
>>>    kernel/bpf/verifier.c       | 6 ++++++
>>>    2 files changed, 9 insertions(+), 1 deletion(-)
>>>
>>> diff --git a/arch/x86/net/bpf_jit_comp.c b/arch/x86/net/bpf_jit_comp.c
>>> index 06b080b61aa57..6ad6886ecfc88 100644
>>> --- a/arch/x86/net/bpf_jit_comp.c
>>> +++ b/arch/x86/net/bpf_jit_comp.c
>>> @@ -2124,10 +2124,12 @@ st:            if (is_imm8(insn->off))
>>>                  /* call */
>>>            case BPF_JMP | BPF_CALL: {
>>> +            bool pseudo_call = src_reg == BPF_PSEUDO_CALL;
>>> +            bool subprog_tail_call_reachable = dst_reg;
>>>                u8 *ip = image + addrs[i - 1];
>>>                  func = (u8 *) __bpf_call_base + imm32;
>>> -            if (tail_call_reachable) {
>>> +            if (pseudo_call && subprog_tail_call_reachable) {
>> Why we need subprog_tail_call_reachable? Does
>>      tail_call_reachable && psueudo_call
>> work the same way?
>>
> 'tail_call_reachable && pseudo_call' works too. However, it will
> propagate tailcall info to subprog even if the subprog is not
> tail_call_reachable.
>
> subprog_tail_call_reachable indicates the subprog requires tailcall info
> from its caller.
> So, 'pseudo_call && subprog_tail_call_reachable' is better.

In verifier.c, we have
   func[i]->aux->tail_call_reachable = env->subprog_info[i].tail_call_reachable;
that is subprog_info tail_call_reachable has been transferred to func[i] tail_call_reachable.

In x86 do_jit() func, we have
   bool tail_call_reachable = bpf_prog->aux->tail_call_reachable

So looks like we do not need verifier.c change here.
Did I miss anything? Could you give a concrete example to show
subprog_tail_call_reachable approach is better than tail_call_reachable?
   

>
> Thanks,
> Leon
>

Re: [PATCH bpf-next 2/2] bpf, verifier: Check trampoline target is tail_call_reachable subprog

[Yonghong Song]

On 10/21/24 6:39 AM, Leon Hwang wrote:
> In the x86_64 JIT, tailcall info is propagated through the trampoline when
> the target program is tail_call_reachable. However, this propagation is
> unnecessary if the target is a main prog, or a subprog that is not
> tail_call_reachable.
>
> Since the verifier can determine if a subprog is tail_call_reachable, it
> should only propagate tailcall info when the target is subprog and the
> subprog is actually tail_call_reachable.
>
> Signed-off-by: Leon Hwang <leon.hwang@linux.dev>

Looks correct to me.

Acked-by: Yonghong Song <yonghong.song@linux.dev>

Re: [PATCH bpf-next 1/2] bpf, x64: Propagate tailcall info only for tail_call_reachable subprogs

[Leon Hwang]

On 24/10/24 10:29, Yonghong Song wrote:
> 
> On 10/21/24 6:46 PM, Leon Hwang wrote:
>>
>> On 22/10/24 01:49, Yonghong Song wrote:
>>> On 10/21/24 6:39 AM, Leon Hwang wrote:
>>>> In the x86_64 JIT, when calling a function, tailcall info is
>>>> propagated if
>>>> the program is tail_call_reachable, regardless of whether the function
>>>> is a
>>>> subprog, helper, or kfunc. However, this propagation is unnecessary for
>>>> not-tail_call_reachable subprogs, helpers, or kfuncs.
>>>>
>>>> The verifier can determine if a subprog is tail_call_reachable.
>>>> Therefore,
>>>> it can be optimized to only propagate tailcall info when the callee is
>>>> subprog and the subprog is actually tail_call_reachable.
>>>>
>>>> Signed-off-by: Leon Hwang <leon.hwang@linux.dev>
>>>> ---
>>>>    arch/x86/net/bpf_jit_comp.c | 4 +++-
>>>>    kernel/bpf/verifier.c       | 6 ++++++
>>>>    2 files changed, 9 insertions(+), 1 deletion(-)
>>>>
>>>> diff --git a/arch/x86/net/bpf_jit_comp.c b/arch/x86/net/bpf_jit_comp.c
>>>> index 06b080b61aa57..6ad6886ecfc88 100644
>>>> --- a/arch/x86/net/bpf_jit_comp.c
>>>> +++ b/arch/x86/net/bpf_jit_comp.c
>>>> @@ -2124,10 +2124,12 @@ st:            if (is_imm8(insn->off))
>>>>                  /* call */
>>>>            case BPF_JMP | BPF_CALL: {
>>>> +            bool pseudo_call = src_reg == BPF_PSEUDO_CALL;
>>>> +            bool subprog_tail_call_reachable = dst_reg;
>>>>                u8 *ip = image + addrs[i - 1];
>>>>                  func = (u8 *) __bpf_call_base + imm32;
>>>> -            if (tail_call_reachable) {
>>>> +            if (pseudo_call && subprog_tail_call_reachable) {
>>> Why we need subprog_tail_call_reachable? Does
>>>      tail_call_reachable && psueudo_call
>>> work the same way?
>>>
>> 'tail_call_reachable && pseudo_call' works too. However, it will
>> propagate tailcall info to subprog even if the subprog is not
>> tail_call_reachable.
>>
>> subprog_tail_call_reachable indicates the subprog requires tailcall info
>> from its caller.
>> So, 'pseudo_call && subprog_tail_call_reachable' is better.
> 
> In verifier.c, we have
>   func[i]->aux->tail_call_reachable = env-
>>subprog_info[i].tail_call_reachable;
> that is subprog_info tail_call_reachable has been transferred to func[i]
> tail_call_reachable.
> 
> In x86 do_jit() func, we have
>   bool tail_call_reachable = bpf_prog->aux->tail_call_reachable
> 
> So looks like we do not need verifier.c change here.
> Did I miss anything? Could you give a concrete example to show
> subprog_tail_call_reachable approach is better than tail_call_reachable?
>  

Sure, here's an example:

struct {
	__uint(type, BPF_MAP_TYPE_PROG_ARRAY);
	__uint(key_size, sizeof(u32));
	__uint(value_size, sizeof(u32));
	__uint(max_entries, 1);
} jmp_table SEC(".maps");

static __noinline int
subprog_tc1(struct __sk_buff *skb)
{
	volatile int retval = TC_ACT_OK;

	bpf_tail_call_static(skb, jmp_table, 0);
	return retval;
}

static __noinline int
subprog_tc2(struct __sk_buff *skb)
{
	volatile int retval = TC_ACT_OK;

	return retval;
}

SEC("tc")
int entry_tc(struct __sk_buff *skb)
{
	u32 pid = bpf_get_smp_processor_id();
	// do something with pid
	subprog_tc2(skb);
	return subprog_tc1(skb);
}

From the verifier's perspective, both entry_tc and subprog_tc1 are
tail_call_reachable.

When handling 'BPF_JMP | BPF_CALL' in the x86 do_jit() for entry_tc,
three cases arise:

1. bpf_get_smp_processor_id()
2. subprog_tc1()
3. subprog_tc2()

At this point in x86 do_jit() for entry_tc, entry_tc is considered
tail_call_reachable. The check 'bool pseudo_call = src_reg ==
BPF_PSEUDO_CALL' is used to determine whether to call a subprogram.

The question is: when should tailcall info be propagated? Should it be
when entry_tc is tail_call_reachable, even if subprog_tc2 is called, or
when subprog_tc1 is specifically tail_call_reachable?

I believe it is better to propagate the tailcall info when subprog_tc1
is tail_call_reachable.

Thanks,
Leon

Re: [PATCH bpf-next 1/2] bpf, x64: Propagate tailcall info only for tail_call_reachable subprogs

[Yonghong Song]

On 10/23/24 8:33 PM, Leon Hwang wrote:
>
> On 24/10/24 10:29, Yonghong Song wrote:
>> On 10/21/24 6:46 PM, Leon Hwang wrote:
>>> On 22/10/24 01:49, Yonghong Song wrote:
>>>> On 10/21/24 6:39 AM, Leon Hwang wrote:
>>>>> In the x86_64 JIT, when calling a function, tailcall info is
>>>>> propagated if
>>>>> the program is tail_call_reachable, regardless of whether the function
>>>>> is a
>>>>> subprog, helper, or kfunc. However, this propagation is unnecessary for
>>>>> not-tail_call_reachable subprogs, helpers, or kfuncs.
>>>>>
>>>>> The verifier can determine if a subprog is tail_call_reachable.
>>>>> Therefore,
>>>>> it can be optimized to only propagate tailcall info when the callee is
>>>>> subprog and the subprog is actually tail_call_reachable.
>>>>>
>>>>> Signed-off-by: Leon Hwang <leon.hwang@linux.dev>
>>>>> ---
>>>>>     arch/x86/net/bpf_jit_comp.c | 4 +++-
>>>>>     kernel/bpf/verifier.c       | 6 ++++++
>>>>>     2 files changed, 9 insertions(+), 1 deletion(-)
>>>>>
>>>>> diff --git a/arch/x86/net/bpf_jit_comp.c b/arch/x86/net/bpf_jit_comp.c
>>>>> index 06b080b61aa57..6ad6886ecfc88 100644
>>>>> --- a/arch/x86/net/bpf_jit_comp.c
>>>>> +++ b/arch/x86/net/bpf_jit_comp.c
>>>>> @@ -2124,10 +2124,12 @@ st:            if (is_imm8(insn->off))
>>>>>                   /* call */
>>>>>             case BPF_JMP | BPF_CALL: {
>>>>> +            bool pseudo_call = src_reg == BPF_PSEUDO_CALL;
>>>>> +            bool subprog_tail_call_reachable = dst_reg;
>>>>>                 u8 *ip = image + addrs[i - 1];
>>>>>                   func = (u8 *) __bpf_call_base + imm32;
>>>>> -            if (tail_call_reachable) {
>>>>> +            if (pseudo_call && subprog_tail_call_reachable) {
>>>> Why we need subprog_tail_call_reachable? Does
>>>>       tail_call_reachable && psueudo_call
>>>> work the same way?
>>>>
>>> 'tail_call_reachable && pseudo_call' works too. However, it will
>>> propagate tailcall info to subprog even if the subprog is not
>>> tail_call_reachable.
>>>
>>> subprog_tail_call_reachable indicates the subprog requires tailcall info
>>> from its caller.
>>> So, 'pseudo_call && subprog_tail_call_reachable' is better.
>> In verifier.c, we have
>>    func[i]->aux->tail_call_reachable = env-
>>> subprog_info[i].tail_call_reachable;
>> that is subprog_info tail_call_reachable has been transferred to func[i]
>> tail_call_reachable.
>>
>> In x86 do_jit() func, we have
>>    bool tail_call_reachable = bpf_prog->aux->tail_call_reachable
>>
>> So looks like we do not need verifier.c change here.
>> Did I miss anything? Could you give a concrete example to show
>> subprog_tail_call_reachable approach is better than tail_call_reachable?
>>   
> Sure, here's an example:
>
> struct {
> 	__uint(type, BPF_MAP_TYPE_PROG_ARRAY);
> 	__uint(key_size, sizeof(u32));
> 	__uint(value_size, sizeof(u32));
> 	__uint(max_entries, 1);
> } jmp_table SEC(".maps");
>
> static __noinline int
> subprog_tc1(struct __sk_buff *skb)
> {
> 	volatile int retval = TC_ACT_OK;
>
> 	bpf_tail_call_static(skb, jmp_table, 0);
> 	return retval;
> }
>
> static __noinline int
> subprog_tc2(struct __sk_buff *skb)
> {
> 	volatile int retval = TC_ACT_OK;
>
> 	return retval;
> }
>
> SEC("tc")
> int entry_tc(struct __sk_buff *skb)
> {
> 	u32 pid = bpf_get_smp_processor_id();
> 	// do something with pid
> 	subprog_tc2(skb);
> 	return subprog_tc1(skb);
> }
>
>  From the verifier's perspective, both entry_tc and subprog_tc1 are
> tail_call_reachable.
>
> When handling 'BPF_JMP | BPF_CALL' in the x86 do_jit() for entry_tc,
> three cases arise:
>
> 1. bpf_get_smp_processor_id()
> 2. subprog_tc1()
> 3. subprog_tc2()
>
> At this point in x86 do_jit() for entry_tc, entry_tc is considered
> tail_call_reachable. The check 'bool pseudo_call = src_reg ==
> BPF_PSEUDO_CALL' is used to determine whether to call a subprogram.
>
> The question is: when should tailcall info be propagated? Should it be
> when entry_tc is tail_call_reachable, even if subprog_tc2 is called, or
> when subprog_tc1 is specifically tail_call_reachable?
>
> I believe it is better to propagate the tailcall info when subprog_tc1
> is tail_call_reachable.

Okay, I see. Thanks for explanation.

You use the insn->dst_reg to record whether callee is tail call
reachable or not. I think you can reuse insn->off which currently
represents subprog number but it is not used for jit. We can
use that to indicate callee is tail call reachable or not.

Something like below:

diff --git a/arch/x86/net/bpf_jit_comp.c b/arch/x86/net/bpf_jit_comp.c
index 06b080b61aa5..b3c76bf59e65 100644
--- a/arch/x86/net/bpf_jit_comp.c
+++ b/arch/x86/net/bpf_jit_comp.c
@@ -2127,7 +2127,8 @@ st:                       if (is_imm8(insn->off))
                         u8 *ip = image + addrs[i - 1];
  
                         func = (u8 *) __bpf_call_base + imm32;
-                       if (tail_call_reachable) {
+                       /* insn->off == 1 means the callee is tail call reachable */
+                       if (src_reg == BPF_PSEUDO_CALL && insn->off == 1) {
                                 LOAD_TAIL_CALL_CNT_PTR(bpf_prog->aux->stack_depth);
                                 ip += 7;
                         }
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index f514247ba8ba..2ccadc1ac22e 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -20096,6 +20096,8 @@ static int jit_subprogs(struct bpf_verifier_env *env)
                                 continue;
                         subprog = insn->off;
                         insn->imm = BPF_CALL_IMM(func[subprog]->bpf_func);
+                       /* Indicate whether callee is tail call reachable or not */
+                       insn->off = func[subprog]->aux->tail_call_reachable;
                 }

WDYT?

>
> Thanks,
> Leon
>

Re: [PATCH bpf-next 1/2] bpf, x64: Propagate tailcall info only for tail_call_reachable subprogs

[Yonghong Song]

On 10/24/24 9:38 AM, Yonghong Song wrote:
>
> On 10/23/24 8:33 PM, Leon Hwang wrote:
>>
>> On 24/10/24 10:29, Yonghong Song wrote:
>>> On 10/21/24 6:46 PM, Leon Hwang wrote:
>>>> On 22/10/24 01:49, Yonghong Song wrote:
>>>>> On 10/21/24 6:39 AM, Leon Hwang wrote:
>>>>>> In the x86_64 JIT, when calling a function, tailcall info is
>>>>>> propagated if
>>>>>> the program is tail_call_reachable, regardless of whether the 
>>>>>> function
>>>>>> is a
>>>>>> subprog, helper, or kfunc. However, this propagation is 
>>>>>> unnecessary for
>>>>>> not-tail_call_reachable subprogs, helpers, or kfuncs.
>>>>>>
>>>>>> The verifier can determine if a subprog is tail_call_reachable.
>>>>>> Therefore,
>>>>>> it can be optimized to only propagate tailcall info when the 
>>>>>> callee is
>>>>>> subprog and the subprog is actually tail_call_reachable.
>>>>>>
>>>>>> Signed-off-by: Leon Hwang <leon.hwang@linux.dev>
>>>>>> ---
>>>>>>     arch/x86/net/bpf_jit_comp.c | 4 +++-
>>>>>>     kernel/bpf/verifier.c       | 6 ++++++
>>>>>>     2 files changed, 9 insertions(+), 1 deletion(-)
>>>>>>
>>>>>> diff --git a/arch/x86/net/bpf_jit_comp.c 
>>>>>> b/arch/x86/net/bpf_jit_comp.c
>>>>>> index 06b080b61aa57..6ad6886ecfc88 100644
>>>>>> --- a/arch/x86/net/bpf_jit_comp.c
>>>>>> +++ b/arch/x86/net/bpf_jit_comp.c
>>>>>> @@ -2124,10 +2124,12 @@ st:            if (is_imm8(insn->off))
>>>>>>                   /* call */
>>>>>>             case BPF_JMP | BPF_CALL: {
>>>>>> +            bool pseudo_call = src_reg == BPF_PSEUDO_CALL;
>>>>>> +            bool subprog_tail_call_reachable = dst_reg;
>>>>>>                 u8 *ip = image + addrs[i - 1];
>>>>>>                   func = (u8 *) __bpf_call_base + imm32;
>>>>>> -            if (tail_call_reachable) {
>>>>>> +            if (pseudo_call && subprog_tail_call_reachable) {
>>>>> Why we need subprog_tail_call_reachable? Does
>>>>>       tail_call_reachable && psueudo_call
>>>>> work the same way?
>>>>>
>>>> 'tail_call_reachable && pseudo_call' works too. However, it will
>>>> propagate tailcall info to subprog even if the subprog is not
>>>> tail_call_reachable.
>>>>
>>>> subprog_tail_call_reachable indicates the subprog requires tailcall 
>>>> info
>>>> from its caller.
>>>> So, 'pseudo_call && subprog_tail_call_reachable' is better.
>>> In verifier.c, we have
>>>    func[i]->aux->tail_call_reachable = env-
>>>> subprog_info[i].tail_call_reachable;
>>> that is subprog_info tail_call_reachable has been transferred to 
>>> func[i]
>>> tail_call_reachable.
>>>
>>> In x86 do_jit() func, we have
>>>    bool tail_call_reachable = bpf_prog->aux->tail_call_reachable
>>>
>>> So looks like we do not need verifier.c change here.
>>> Did I miss anything? Could you give a concrete example to show
>>> subprog_tail_call_reachable approach is better than 
>>> tail_call_reachable?
>> Sure, here's an example:
>>
>> struct {
>>     __uint(type, BPF_MAP_TYPE_PROG_ARRAY);
>>     __uint(key_size, sizeof(u32));
>>     __uint(value_size, sizeof(u32));
>>     __uint(max_entries, 1);
>> } jmp_table SEC(".maps");
>>
>> static __noinline int
>> subprog_tc1(struct __sk_buff *skb)
>> {
>>     volatile int retval = TC_ACT_OK;
>>
>>     bpf_tail_call_static(skb, jmp_table, 0);
>>     return retval;
>> }
>>
>> static __noinline int
>> subprog_tc2(struct __sk_buff *skb)
>> {
>>     volatile int retval = TC_ACT_OK;
>>
>>     return retval;
>> }
>>
>> SEC("tc")
>> int entry_tc(struct __sk_buff *skb)
>> {
>>     u32 pid = bpf_get_smp_processor_id();
>>     // do something with pid
>>     subprog_tc2(skb);
>>     return subprog_tc1(skb);
>> }
>>
>>  From the verifier's perspective, both entry_tc and subprog_tc1 are
>> tail_call_reachable.
>>
>> When handling 'BPF_JMP | BPF_CALL' in the x86 do_jit() for entry_tc,
>> three cases arise:
>>
>> 1. bpf_get_smp_processor_id()
>> 2. subprog_tc1()
>> 3. subprog_tc2()
>>
>> At this point in x86 do_jit() for entry_tc, entry_tc is considered
>> tail_call_reachable. The check 'bool pseudo_call = src_reg ==
>> BPF_PSEUDO_CALL' is used to determine whether to call a subprogram.
>>
>> The question is: when should tailcall info be propagated? Should it be
>> when entry_tc is tail_call_reachable, even if subprog_tc2 is called, or
>> when subprog_tc1 is specifically tail_call_reachable?
>>
>> I believe it is better to propagate the tailcall info when subprog_tc1
>> is tail_call_reachable.
>
> Okay, I see. Thanks for explanation.
>
> You use the insn->dst_reg to record whether callee is tail call
> reachable or not. I think you can reuse insn->off which currently
> represents subprog number but it is not used for jit. We can
> use that to indicate callee is tail call reachable or not.
>
> Something like below:
>
> diff --git a/arch/x86/net/bpf_jit_comp.c b/arch/x86/net/bpf_jit_comp.c
> index 06b080b61aa5..b3c76bf59e65 100644
> --- a/arch/x86/net/bpf_jit_comp.c
> +++ b/arch/x86/net/bpf_jit_comp.c
> @@ -2127,7 +2127,8 @@ st:                       if (is_imm8(insn->off))
>                         u8 *ip = image + addrs[i - 1];
>
>                         func = (u8 *) __bpf_call_base + imm32;
> -                       if (tail_call_reachable) {
> +                       /* insn->off == 1 means the callee is tail 
> call reachable */
> +                       if (src_reg == BPF_PSEUDO_CALL && insn->off == 
> 1) {
> LOAD_TAIL_CALL_CNT_PTR(bpf_prog->aux->stack_depth);
>                                 ip += 7;
>                         }
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index f514247ba8ba..2ccadc1ac22e 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -20096,6 +20096,8 @@ static int jit_subprogs(struct 
> bpf_verifier_env *env)
>                                 continue;
>                         subprog = insn->off;
>                         insn->imm = 
> BPF_CALL_IMM(func[subprog]->bpf_func);
> +                       /* Indicate whether callee is tail call 
> reachable or not */
> +                       insn->off = 
> func[subprog]->aux->tail_call_reachable;
>                 }
>
> WDYT?

Sorry, the above seems not working since verifier do jit twice for the same prog
and two jit'ed results need to be the same. The above change could make jit result
different between two passes.

>
>>
>> Thanks,
>> Leon
>>
>

Re: [PATCH bpf-next 1/2] bpf, x64: Propagate tailcall info only for tail_call_reachable subprogs

[Yonghong Song]

On 10/21/24 6:39 AM, Leon Hwang wrote:
> In the x86_64 JIT, when calling a function, tailcall info is propagated if
> the program is tail_call_reachable, regardless of whether the function is a
> subprog, helper, or kfunc. However, this propagation is unnecessary for
> not-tail_call_reachable subprogs, helpers, or kfuncs.
>
> The verifier can determine if a subprog is tail_call_reachable. Therefore,
> it can be optimized to only propagate tailcall info when the callee is
> subprog and the subprog is actually tail_call_reachable.
>
> Signed-off-by: Leon Hwang <leon.hwang@linux.dev>

LGTM with a nit below.

Acked-by: Yonghong Song <yonghong.song@linux.dev>

> ---
>   arch/x86/net/bpf_jit_comp.c | 4 +++-
>   kernel/bpf/verifier.c       | 6 ++++++
>   2 files changed, 9 insertions(+), 1 deletion(-)
>
> diff --git a/arch/x86/net/bpf_jit_comp.c b/arch/x86/net/bpf_jit_comp.c
> index 06b080b61aa57..6ad6886ecfc88 100644
> --- a/arch/x86/net/bpf_jit_comp.c
> +++ b/arch/x86/net/bpf_jit_comp.c
> @@ -2124,10 +2124,12 @@ st:			if (is_imm8(insn->off))
>   
>   			/* call */
>   		case BPF_JMP | BPF_CALL: {
> +			bool pseudo_call = src_reg == BPF_PSEUDO_CALL;
> +			bool subprog_tail_call_reachable = dst_reg;
>   			u8 *ip = image + addrs[i - 1];
>   
>   			func = (u8 *) __bpf_call_base + imm32;
> -			if (tail_call_reachable) {
> +			if (pseudo_call && subprog_tail_call_reachable) {
>   				LOAD_TAIL_CALL_CNT_PTR(bpf_prog->aux->stack_depth);
>   				ip += 7;
>   			}
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index f514247ba8ba8..6e7e42c7bc7b1 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -19990,6 +19990,12 @@ static int jit_subprogs(struct bpf_verifier_env *env)
>   			insn[0].imm = (u32)addr;
>   			insn[1].imm = addr >> 32;
>   		}
> +
> +		if (bpf_pseudo_call(insn))
> +			/* In the x86_64 JIT, tailcall information can only be
> +			 * propagated if the subprog is tail_call_reachable.
> +			 */
> +			insn->dst_reg = env->subprog_info[subprog].tail_call_reachable;

The comment can be simplied as
	/* Indicate whether callee is tail call
reachable or not */

>   	}
>   
>   	err = bpf_prog_alloc_jited_linfo(prog);

Re: [PATCH bpf-next 1/2] bpf, x64: Propagate tailcall info only for tail_call_reachable subprogs

[Alexei Starovoitov]

On Mon, Oct 21, 2024 at 6:39 AM Leon Hwang <leon.hwang@linux.dev> wrote:
>
> In the x86_64 JIT, when calling a function, tailcall info is propagated if
> the program is tail_call_reachable, regardless of whether the function is a
> subprog, helper, or kfunc. However, this propagation is unnecessary for
> not-tail_call_reachable subprogs, helpers, or kfuncs.
>
> The verifier can determine if a subprog is tail_call_reachable. Therefore,
> it can be optimized to only propagate tailcall info when the callee is
> subprog and the subprog is actually tail_call_reachable.
>
> Signed-off-by: Leon Hwang <leon.hwang@linux.dev>
> ---
>  arch/x86/net/bpf_jit_comp.c | 4 +++-
>  kernel/bpf/verifier.c       | 6 ++++++
>  2 files changed, 9 insertions(+), 1 deletion(-)
>
> diff --git a/arch/x86/net/bpf_jit_comp.c b/arch/x86/net/bpf_jit_comp.c
> index 06b080b61aa57..6ad6886ecfc88 100644
> --- a/arch/x86/net/bpf_jit_comp.c
> +++ b/arch/x86/net/bpf_jit_comp.c
> @@ -2124,10 +2124,12 @@ st:                     if (is_imm8(insn->off))
>
>                         /* call */
>                 case BPF_JMP | BPF_CALL: {
> +                       bool pseudo_call = src_reg == BPF_PSEUDO_CALL;
> +                       bool subprog_tail_call_reachable = dst_reg;
>                         u8 *ip = image + addrs[i - 1];
>
>                         func = (u8 *) __bpf_call_base + imm32;
> -                       if (tail_call_reachable) {
> +                       if (pseudo_call && subprog_tail_call_reachable) {
>                                 LOAD_TAIL_CALL_CNT_PTR(bpf_prog->aux->stack_depth);
>                                 ip += 7;
>                         }
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index f514247ba8ba8..6e7e42c7bc7b1 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -19990,6 +19990,12 @@ static int jit_subprogs(struct bpf_verifier_env *env)
>                         insn[0].imm = (u32)addr;
>                         insn[1].imm = addr >> 32;
>                 }
> +
> +               if (bpf_pseudo_call(insn))
> +                       /* In the x86_64 JIT, tailcall information can only be
> +                        * propagated if the subprog is tail_call_reachable.
> +                        */
> +                       insn->dst_reg = env->subprog_info[subprog].tail_call_reachable;

I really don't like hacking flags into dst_reg.
We already abuse insn->off which is ugly too,
but at least we clean insns later after JIT.

I'd rather live with this tail call inefficiency than abuse insns
fields further.

pw-bot: cr

Re: [PATCH bpf-next 1/2] bpf, x64: Propagate tailcall info only for tail_call_reachable subprogs

[Leon Hwang]

On 25/10/24 06:09, Alexei Starovoitov wrote:
> On Mon, Oct 21, 2024 at 6:39 AM Leon Hwang <leon.hwang@linux.dev> wrote:
>>
>> In the x86_64 JIT, when calling a function, tailcall info is propagated if
>> the program is tail_call_reachable, regardless of whether the function is a
>> subprog, helper, or kfunc. However, this propagation is unnecessary for
>> not-tail_call_reachable subprogs, helpers, or kfuncs.
>>
>> The verifier can determine if a subprog is tail_call_reachable. Therefore,
>> it can be optimized to only propagate tailcall info when the callee is
>> subprog and the subprog is actually tail_call_reachable.
>>
>> Signed-off-by: Leon Hwang <leon.hwang@linux.dev>
>> ---
>>  arch/x86/net/bpf_jit_comp.c | 4 +++-
>>  kernel/bpf/verifier.c       | 6 ++++++
>>  2 files changed, 9 insertions(+), 1 deletion(-)
>>
>> diff --git a/arch/x86/net/bpf_jit_comp.c b/arch/x86/net/bpf_jit_comp.c
>> index 06b080b61aa57..6ad6886ecfc88 100644
>> --- a/arch/x86/net/bpf_jit_comp.c
>> +++ b/arch/x86/net/bpf_jit_comp.c
>> @@ -2124,10 +2124,12 @@ st:                     if (is_imm8(insn->off))
>>
>>                         /* call */
>>                 case BPF_JMP | BPF_CALL: {
>> +                       bool pseudo_call = src_reg == BPF_PSEUDO_CALL;
>> +                       bool subprog_tail_call_reachable = dst_reg;
>>                         u8 *ip = image + addrs[i - 1];
>>
>>                         func = (u8 *) __bpf_call_base + imm32;
>> -                       if (tail_call_reachable) {
>> +                       if (pseudo_call && subprog_tail_call_reachable) {
>>                                 LOAD_TAIL_CALL_CNT_PTR(bpf_prog->aux->stack_depth);
>>                                 ip += 7;
>>                         }
>> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
>> index f514247ba8ba8..6e7e42c7bc7b1 100644
>> --- a/kernel/bpf/verifier.c
>> +++ b/kernel/bpf/verifier.c
>> @@ -19990,6 +19990,12 @@ static int jit_subprogs(struct bpf_verifier_env *env)
>>                         insn[0].imm = (u32)addr;
>>                         insn[1].imm = addr >> 32;
>>                 }
>> +
>> +               if (bpf_pseudo_call(insn))
>> +                       /* In the x86_64 JIT, tailcall information can only be
>> +                        * propagated if the subprog is tail_call_reachable.
>> +                        */
>> +                       insn->dst_reg = env->subprog_info[subprog].tail_call_reachable;
> 
> I really don't like hacking flags into dst_reg.
> We already abuse insn->off which is ugly too,
> but at least we clean insns later after JIT.
> 
> I'd rather live with this tail call inefficiency than abuse insns
> fields further.
> 

OK, let us use 'pseudo_call && tail_call_reachable' in x86 JIT to avoid
touching 'insn->dst_reg'.

Thanks,
Leon

> pw-bot: cr