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/6/24 7:26 AM, Alexei Starovoitov wrote:
> On Tue, Nov 5, 2024 at 10:55 PM Yonghong Song <yonghong.song@linux.dev> wrote:
>>
>>
>>
>> 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.
> Your emailer still spits out garbage :(

Somehow recently, my thunderbird mailer may change text/width setting
depending on the original format. Unless I explicitly set the format
again. Sometimes it will use a 'Variable width' which will glue everything in
one paragraph. I am trying to find a solution now to fix the mailer.

> but I think I got the idea. Will wait for respin.

Will do.