Re: [PATCH bpf-next v2 00/11] Enable BPF programs to declare arrays of kptr, bpf_rb_root, and bpf_list_head.

[Kui-Feng Lee <sinquersw@gmail.com>]

On 4/24/24 15:34, Kui-Feng Lee wrote:
> 
> 
> On 4/24/24 15:32, Kui-Feng Lee wrote:
>>
>>
>> On 4/24/24 13:09, Alexei Starovoitov wrote:
>>> On Mon, Apr 22, 2024 at 7:54 PM Kui-Feng Lee <sinquersw@gmail.com> 
>>> wrote:
>>>>
>>>>
>>>>
>>>> On 4/22/24 19:45, Kui-Feng Lee wrote:
>>>>>
>>>>>
>>>>> On 4/18/24 07:53, Alexei Starovoitov wrote:
>>>>>> On Wed, Apr 17, 2024 at 11:07 PM Kui-Feng Lee <sinquersw@gmail.com>
>>>>>> wrote:
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>> On 4/17/24 22:11, Alexei Starovoitov wrote:
>>>>>>>> On Wed, Apr 17, 2024 at 9:31 PM Kui-Feng Lee <sinquersw@gmail.com>
>>>>>>>> wrote:
>>>>>>>>>
>>>>>>>>>
>>>>>>>>>
>>>>>>>>> On 4/17/24 20:30, Alexei Starovoitov wrote:
>>>>>>>>>> On Fri, Apr 12, 2024 at 2:08 PM Kui-Feng Lee
>>>>>>>>>> <thinker.li@gmail.com> wrote:
>>>>>>>>>>>
>>>>>>>>>>> The arrays of kptr, bpf_rb_root, and bpf_list_head didn't 
>>>>>>>>>>> work as
>>>>>>>>>>> global variables. This was due to these types being 
>>>>>>>>>>> initialized and
>>>>>>>>>>> verified in a special manner in the kernel. This patchset 
>>>>>>>>>>> allows BPF
>>>>>>>>>>> programs to declare arrays of kptr, bpf_rb_root, and
>>>>>>>>>>> bpf_list_head in
>>>>>>>>>>> the global namespace.
>>>>>>>>>>>
>>>>>>>>>>> The main change is to add "nelems" to btf_fields. The value of
>>>>>>>>>>> "nelems" represents the number of elements in the array if a
>>>>>>>>>>> btf_field
>>>>>>>>>>> represents an array. Otherwise, "nelem" will be 1. The verifier
>>>>>>>>>>> verifies these types based on the information provided by the
>>>>>>>>>>> btf_field.
>>>>>>>>>>>
>>>>>>>>>>> The value of "size" will be the size of the entire array if a
>>>>>>>>>>> btf_field represents an array. Dividing "size" by "nelems" 
>>>>>>>>>>> gives the
>>>>>>>>>>> size of an element. The value of "offset" will be the offset 
>>>>>>>>>>> of the
>>>>>>>>>>> beginning for an array. By putting this together, we can
>>>>>>>>>>> determine the
>>>>>>>>>>> offset of each element in an array. For example,
>>>>>>>>>>>
>>>>>>>>>>>         struct bpf_cpumask __kptr * global_mask_array[2];
>>>>>>>>>>
>>>>>>>>>> Looks like this patch set enables arrays only.
>>>>>>>>>> Meaning the following is supported already:
>>>>>>>>>>
>>>>>>>>>> +private(C) struct bpf_spin_lock glock_c;
>>>>>>>>>> +private(C) struct bpf_list_head ghead_array1 __contains(foo, 
>>>>>>>>>> node2);
>>>>>>>>>> +private(C) struct bpf_list_head ghead_array2 __contains(foo, 
>>>>>>>>>> node2);
>>>>>>>>>>
>>>>>>>>>> while this support is added:
>>>>>>>>>>
>>>>>>>>>> +private(C) struct bpf_spin_lock glock_c;
>>>>>>>>>> +private(C) struct bpf_list_head ghead_array1[3] __contains(foo,
>>>>>>>>>> node2);
>>>>>>>>>> +private(C) struct bpf_list_head ghead_array2[2] __contains(foo,
>>>>>>>>>> node2);
>>>>>>>>>>
>>>>>>>>>> Am I right?
>>>>>>>>>>
>>>>>>>>>> What about the case when bpf_list_head is wrapped in a struct?
>>>>>>>>>> private(C) struct foo {
>>>>>>>>>>       struct bpf_list_head ghead;
>>>>>>>>>> } ghead;
>>>>>>>>>>
>>>>>>>>>> that's not enabled in this patch. I think.
>>>>>>>>>>
>>>>>>>>>> And the following:
>>>>>>>>>> private(C) struct foo {
>>>>>>>>>>       struct bpf_list_head ghead;
>>>>>>>>>> } ghead[2];
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> or
>>>>>>>>>>
>>>>>>>>>> private(C) struct foo {
>>>>>>>>>>       struct bpf_list_head ghead[2];
>>>>>>>>>> } ghead;
>>>>>>>>>>
>>>>>>>>>> Won't work either.
>>>>>>>>>
>>>>>>>>> No, they don't work.
>>>>>>>>> We had a discussion about this in the other day.
>>>>>>>>> I proposed to have another patch set to work on struct types.
>>>>>>>>> Do you prefer to handle it in this patch set?
>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> I think eventually we want to support all such combinations and
>>>>>>>>>> the approach proposed in this patch with 'nelems'
>>>>>>>>>> won't work for wrapper structs.
>>>>>>>>>>
>>>>>>>>>> I think it's better to unroll/flatten all structs and arrays
>>>>>>>>>> and represent them as individual elements in the flattened
>>>>>>>>>> structure. Then there will be no need to special case array with
>>>>>>>>>> 'nelems'.
>>>>>>>>>> All special BTF types will be individual elements with unique 
>>>>>>>>>> offset.
>>>>>>>>>>
>>>>>>>>>> Does this make sense?
>>>>>>>>>
>>>>>>>>> That means it will creates 10 btf_field(s) for an array having 10
>>>>>>>>> elements. The purpose of adding "nelems" is to avoid the
>>>>>>>>> repetition. Do
>>>>>>>>> you prefer to expand them?
>>>>>>>>
>>>>>>>> It's not just expansion, but a common way to handle nested 
>>>>>>>> structs too.
>>>>>>>>
>>>>>>>> I suspect by delaying nested into another patchset this approach
>>>>>>>> will become useless.
>>>>>>>>
>>>>>>>> So try adding nested structs in all combinations as a follow up and
>>>>>>>> I suspect you're realize that "nelems" approach doesn't really 
>>>>>>>> help.
>>>>>>>> You'd need to flatten them all.
>>>>>>>> And once you do there is no need for "nelems".
>>>>>>>
>>>>>>> For me, "nelems" is more like a choice of avoiding repetition of
>>>>>>> information, not a necessary. Before adding "nelems", I had 
>>>>>>> considered
>>>>>>> to expand them as well. But, eventually, I chose to add "nelems".
>>>>>>>
>>>>>>> Since you think this repetition is not a problem, I will expand 
>>>>>>> array as
>>>>>>> individual elements.
>>>>>>
>>>>>> You don't sound convinced :)
>>>>>> Please add support for nested structs on top of your "nelems" 
>>>>>> approach
>>>>>> and prototype the same without "nelems" and let's compare the two.
>>>>>
>>>>>
>>>>> The following is the prototype that flatten arrays and struct types.
>>>>> This approach is definitely simpler than "nelems" one.  However,
>>>>> it will repeat same information as many times as the size of an array.
>>>>> For now, we have a limitation on the number of btf_fields (<= 10).
>>>
>>> I understand the concern and desire to minimize duplication,
>>> but I don't see how this BPF_REPEAT_FIELDS approach is going to work.
>>>  From btf_parse_fields() pov it becomes one giant opaque field
>>> that sort_r() processes as a blob.
>>>
>>> How
>>> btf_record_find(reg->map_ptr->record,
>>>                  off + reg->var_off.value, BPF_KPTR);
>>>
>>> is going to find anything in there?
>>> Are you making a restriction that arrays and nested structs
>>> will only have kptrs in there ?
>>> So BPF_REPEAT_FIELDS can only wrap kptrs ?
>>> But even then these kptrs might have different btf_ids.
>>> So
>>> struct map_value {
>>>     struct {
>>>        struct task __kptr *p1;
>>>        struct thread __kptr *p2;
>>>     } arr[10];
>>> };
>>>
>>> won't be able to be represented as BPF_REPEAT_FIELDS?
>>
>>
>> BPF_REPEAT_FIELDS can handle it. With this case, bpf_parse_fields() 
>> will create a list of btf_fields like this:
>>
>>      [ btf_field(type=BPF_KPTR_..., offset=0, ...),
>>        btf_field(type=BPF_KPTR_..., offset=8, ...),
>>        btf_field(type=BPF_REPEAT_FIELDS, offset=16, repeated_fields=2, 
>> nelems=9, size=16)]
> 
>   An error here.  size should be 16 * 9.
> 
>>
>> You might miss the explanation in [1].
>>
>> btf_record_find() is still doing binary search. Looking for p2 in
>> obj->arr[1], the offset will be 24.  btf_record_find() will find the
>> BPF_REPEATED_FIELDS one, and redirect the offset to
>>
>>    (field->offset - field->size + (16 - field->offset) % field->size) 
                                       ^^^ should be 24
>> == 8
> 
> field->size should be replaced by (field->size / field->nelems).
> 
>>
>> Then, it will return the btf_field whose offset is 8.
>>
>>
>> [1] 
>> https://lore.kernel.org/all/4d3dc24f-fb50-4674-8eec-4c38e4d4b2c1@gmail.com/
>>
>>>
>>> I think that simple flattening without repeat/nelems optimization
>>> is much easier to reason about.
>>> BTF_FIELDS_MAX is just a constant.
>>> Just don't do struct btf_field_info info_arr[BTF_FIELDS_MAX]; on stack.
>>
>> I will switch to flatten one if you think "nelems" &
>> "BPF_REPEAT_FIELDS" are too complicated after reading the explanation in
>> [1].
>>