Re: [PATCH RFC bpf-next v2 00/18] bpf: Introduce resizable hash map

Mykyta Yatsenko
2026-04-20T16:37:39Z

On 4/20/26 5:06 PM, Alexei Starovoitov wrote:
> On Mon, Apr 20, 2026 at 8:50 AM Mykyta Yatsenko
> <mykyta.yatsenko5@gmail.com> wrote:
>>
>>
>>
>> On 4/20/26 4:41 PM, Alexei Starovoitov wrote:
>>> On Mon Apr 20, 2026 at 4:45 AM PDT, Mykyta Yatsenko wrote:
>>>>
>>>>
>>>> On 4/18/26 1:43 AM, Herbert Xu wrote:
>>>>> On Fri, Apr 17, 2026 at 04:16:34PM +0100, Mykyta Yatsenko wrote:
>>>>>>
>>>>>> Changing interface is practically not possible - this comes from the bpf
>>>>>> syscall.
>>>>>> Linked list solution: we probably can't afford it performance-wise, it's not
>>>>>> worth it to pay for the linked list maintenance in insert/delete operations,
>>>>>> to make traversals work well.
>>>>>
>>>>> What performance penalty? The linked list is just a pair of pointers.
>>>>>
>>>>> Memory-wise it'll be two extra pointers per node.
>>>>>
>>>>> Cheers,
>>>>
>>>> I'm concerned about pointer chasing, when we inserting a new element to
>>>> the list or removing existing, we'll need to update pointers of the
>>>> neighboring elements. It'll be nice to measure it, of course, let me try
>>>> to prototype it.
>>>
>>> hold on. let's not overcomplicate things.
>>> We only need to notice that resize happened, right?
>>> In such case just ad generation counter and let resize increment it.
>>> If it changed in our iterator -> ERESTARTSYS.
>>> EAGAIN doesn't quite fit, since it implies that immediate operation can be
>>> retried, while here the iterator need to be destroyed and recreated.
>>
>> I think that won't work with get_next_key() because we don't know what
>> generation previous key was read (in API we just get prev_key and return
>> next key).
>
> The first one starts with key==NULL.

If we iterate entire map in one go, we can detect resize, agreed. But if
user just randomly calls bpf_map_get_next_key(), we cannot really detect
resizes, because we don't even know when iteration started - it may not
even be an iteration, but just an odd bpf_map_get_next_key().
I think we can handle resizes next way:
- map_get_next_key(): leave as is, can't detect resize or even if
resize matters.
- map_for_each_callback(), iter_seq_info(): error out if resize takes
place mid iteration.
- batch ops: store generation counter in the bpf_attr, so on resuming,
we can detect if there was resize.