using bpf_map_update_elem and bpf_map_get_next_key at the same time when looping through the hash map

using bpf_map_update_elem and bpf_map_get_next_key at the same time when looping through the hash map

[G]

Hi BPF Experts

I'm having an issue with using "bpf_map_update_elem" and  "bpf_map_get_next_key" at the same time when looping through the bpf HashMap.
My program turns to an infinite loop and the pseudocode is as following:
------------------------------------------------------------------------------
    bpf.MapCreate          // type=BPF_MAP_TYPE_HASH size=128
    for { bpf.MapUpdate }  // add(update) 128 elements at once

    then loop through the map to update each element
    bpf.MapGetNextKey(fd, nil, &scankey) // find first key
    for {
          bpf.MapUpate(fd, &scankey, &val, BPF_EXIST)
          bpf.MapGetNextKey(fd, &scankey, &scankey)
    }
------------------------------------------------------------------------------

I have tried to read the relevant kernel code, and seems like it is moving the element to the top of the has bucket when calling the “bpf_map_update_elem” even the element already exists in the hash map. See the following source code:
------------------------------------------------------------------------------
    // kernel/bpf/hashtab.c
    htab_map_update_elem {
        ...
       /* add new element to the head of the list, so that
        * concurrent search will find it before old elem
        */
       hlist_nulls_add_head_rcu(&l_new->hash_node, head);
        ...
    }
------------------------------------------------------------------------------

Therefore, when I was trying to traversing the two elements in the same hash a bucket, it ran into an infinite loop by repeatedly getting the key of these two elements. Not sure my understanding for "bpf_map_update_elem"and "bpf_map_get_next_key" is correct or not. My question is: is that behave as the design? or is it a bug for the bpf hashmap? Please let me know, thanks.

Best regards
W.Gao

Re: using bpf_map_update_elem and bpf_map_get_next_key at the same time when looping through the hash map

[Yonghong Song]

On 7/5/21 8:11 PM, G wrote:
> Hi BPF Experts
> 
> I'm having an issue with using "bpf_map_update_elem" and  "bpf_map_get_next_key" at the same time when looping through the bpf HashMap.
> My program turns to an infinite loop and the pseudocode is as following:
> ------------------------------------------------------------------------------
>      bpf.MapCreate          // type=BPF_MAP_TYPE_HASH size=128
>      for { bpf.MapUpdate }  // add(update) 128 elements at once
> 
>      then loop through the map to update each element
>      bpf.MapGetNextKey(fd, nil, &scankey) // find first key
>      for {
>            bpf.MapUpate(fd, &scankey, &val, BPF_EXIST)
>            bpf.MapGetNextKey(fd, &scankey, &scankey)
>      }
> ------------------------------------------------------------------------------
> 
> I have tried to read the relevant kernel code, and seems like it is moving the element to the top of the has bucket when calling the “bpf_map_update_elem” even the element already exists in the hash map. See the following source code:
> ------------------------------------------------------------------------------
>      // kernel/bpf/hashtab.c
>      htab_map_update_elem {
>          ...
>         /* add new element to the head of the list, so that
>          * concurrent search will find it before old elem
>          */
>         hlist_nulls_add_head_rcu(&l_new->hash_node, head);
>          ...
>      }
> ------------------------------------------------------------------------------
> 
> Therefore, when I was trying to traversing the two elements in the same hash a bucket, it ran into an infinite loop by repeatedly getting the key of these two elements. Not sure my understanding for "bpf_map_update_elem"and "bpf_map_get_next_key" is correct or not. My question is: is that behave as the design? or is it a bug for the bpf hashmap? Please let me know, thanks.

bpf_map_get_next_key() is added after bpf_map_update_elem(). So the 
above behavior is in the kernel already for sometimes.

bpf_map_get_next_key() is not super reliable for hash table as if some 
deletion happens, the get_next_key may start from the beginning.
The recommendation is to use bpf_map_*_batch() interface.
If your kernel does not implement bpf_map_*_batch() interface, I think
it would be best you call bpf_map_get_next_key() for ALL elements before
doing any update/delete.

> 
> Best regards
> W.Gao
>