Skip to contentSkip to conversation

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

DISCUSSION G 2 participants 2 messages Jul 6, 2021 BPF

lore
Share & tools
lore

G

author
#0 lore raw

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

#1 lore raw
Quoted 27 lines · 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);
         ...
     }
Quoted 3 lines

------------------------------------------------------------------------------

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.

Quoted 4 lines

Best regards
W.Gao