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 17:49, Alexei Starovoitov wrote:
> On Wed, Apr 24, 2024 at 3:32 PM Kui-Feng Lee <sinquersw@gmail.com> wrote:
>>
>>> 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)]
>>
>> 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) == 8
>>
>> 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 somehow completely missed that email.
> Just read it and tbh it looks very unnatural and convoluted.
> 
>> [kptr_a, kptr_b, repeated_fields(nelems=3, repeated_cnt=2),
>>     repeated_fields(nelems=9, repeated_cnt=3)]
> 
> is kinda an inverted array description where elements come first
> and then array type. I have a hard time imagining how search
> in such thing will work.

About searching, it will find the elements if index is 0. For index >=
1, it will find repeated_fields(), and redirect to the offset to an
offset at index 0. The pseudo code looks like

   field = bsearch(all_fields, offset..);
   while (field && is_repeated_fields(field)) {
      offset = redirect_offset(offset, field);
      field = 
bsearch(&all_fields[field.index-field.repeated_cnt..field.index], offset);
   }


> 
> Also consider that arrays won't be huge, since bpf prog
> can only access them with a constant offset.
> Even array[NR_CPUS] is unlikely, since indexing into it
> with a variable index won't be possible.

I also got a similar opinion from Andrii in another message.
So, I will move to flatten solution.
Thank you for your feedback.