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

Alexei Starovoitov
2026-04-20T18:00:56Z

On Mon, Apr 20, 2026 at 9:37 AM Mykyta Yatsenko
<mykyta.yatsenko5@gmail.com> wrote:
>
>
>
> 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.

exactly. My understanding of the thread is that resize problematic
only for the whole map walk, since it may keep revisiting elements
potentially forever. Since get_next_key() is a loop through user space.
It's not an issue.

> - map_for_each_callback(), iter_seq_info(): error out if resize takes
> place mid iteration.

right. here it would be good to prevent looping for a long time.

> - batch ops: store generation counter in the bpf_attr, so on resuming,
> we can detect if there was resize.

I wouldn't bother. It's the same category as get_next_key().
It loops through user space. We already have this "infinite loop"
issue with this api with a normal hash map. If bpf prog deletes
an unlucky 'prev' element the while(get_next_key) loop will restart
from the first.