Re: [PATCH bpf-next v9 04/10] bpf: Check potential private stack recursion for progs with async callback

[Yonghong Song <yonghong.song@linux.dev>]

On 11/5/24 5:07 PM, Alexei Starovoitov wrote:
> On Tue, Nov 5, 2024 at 4:19 PM Yonghong Song <yonghong.song@linux.dev> wrote:
>>
>>
>>
>> On 11/5/24 1:52 PM, Alexei Starovoitov wrote:
>>> On Tue, Nov 5, 2024 at 1:26 PM Yonghong Song <yonghong.song@linux.dev> wrote:
>>>>> I see. I think it works, but feels complicated.
>>>>> It feels it should be possible to do without extra flags. Like
>>>>> check_max_stack_depth_subprog() will know whether it was called
>>>>> to verify async_cb or not.
>>>>> So it's just a matter of adding single 'if' to it:
>>>>> if (subprog[idx].use_priv_stack && checking_async_cb)
>>>>>       /* reset to false due to potential recursion */
>>>>>       subprog[idx].use_priv_stack = false;
>>>>>
>>>>> check_max_stack_depth() starts with i==0,
>>>>> so reachable and eligible subprogs will be marked with use_priv_stack.
>>>>> Then check_max_stack_depth_subprog() will be called again
>>>>> to verify async. If it sees the mark it's a bad case.
>>>>> what am I missing?
>>>> First I think we still want to mark some subprogs in async tree
>>>> to use private stack, right? If this is the case, then let us see
>>>> the following examle:
>>>>
>>>> main_prog:
>>>>       sub1: use_priv_stack = true
>>>>       sub2" use_priv_stack = true
>>>>
>>>> async: /* calling sub1 twice */
>>>>       sub1
>>>>         <=== we do
>>>>                if (subprog[idx].use_priv_stack && checking_async_cb)
>>>>                    subprog[idx].use_priv_stack = false;
>>>>       sub1
>>>>         <=== here we have subprog[idx].use_priv_stack = false;
>>>>              we could mark use_priv_stack = true again here
>>>>              since logic didn't keep track of sub1 has been
>>>>              visited before.
>>> This case needs a sticky state to solve.
>>> Instead of bool use_priv_stack it can be tri-state:
>>> no_priv_stack
>>> priv_stack_unknown <- start state
>>> priv_stack_maybe
>>>
>>> main_prog pass will set it to priv_stack_maybe
>>> while async pass will clear it to no_priv_stack
>>> and it cannot be bumped up.
>> The tri-state may not work. For example,
>>
>> main_prog:
>>      call sub1
>>      call sub2
>>      call sub1
> sub1 cannot be called nested like this.
> I think we discussed it already.
>
>>      call sub3
>>
>> async:
>>      call sub4 ==> UNKNOWN -> MAYBE
>>      call sub3
>>      call sub4 ==> MAYBE -> NO_PRIV_STACK?
>>
>> For sub4 in async which is called twice, for the second sub4 call,
>> it is not clear whether UNKNOWN->MAYBE transition happens in
>> main_prog or async. So based on transition prototol,
>> second sub4 call will transition to NO_PRIV_STACK which is not
>> what we want.
> I see. Good point.
>
>> So I think we still need a separate bit in bpf_subprog_info to
>> accumulate information for main_prog tree or any async tree.
> This is getting quite convoluted. To support priv stack
> in multiple async cb-s we may need to remember async cb id or something.
> I say let's force all subprogs in async cb to use normal stack.

I did a quick prototype. Among others, tri-state (UNKNOWN, NO, ADAPTIVE) 
and reverse traversing subprogs like below diff --git 
a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index 
cb82254484ff..1084432dbe83 100644 --- a/kernel/bpf/verifier.c +++ 
b/kernel/bpf/verifier.c @@ -6192,7 +6192,7 @@ static int 
check_max_stack_depth(struct bpf_verifier_env *env) struct 
bpf_subprog_info *si = env->subprog_info; int ret; - for (int i = 0; i < 
env->subprog_cnt; i++) { + for (int i = env->subprog_cnt - 1; i >= 0; 
i--) { if (i && !si[i].is_async_cb) continue; works correctly. 
Basically, all async_cb touched subprogs are marked as 'NO'. Finally for 
main prog tree, UNKNOWN subprog will convert to ADAPTIVE if >= stack 
size threshold. Stack size checking can also be done properly for 
async_cb tree and main prog tree.