Skip to contentSkip to conversation

bpf: fix possible endless loop in BPF map iteration

PATCH RESEND In review Brandon Kammerdiener 4 participants 4 messages Apr 9, 2025 – Apr 15, 2025 BPF

v1 of 3 In review Latest is v3 →

lore
Share & tools
lore
#0 lore raw

PATCH RESEND 1/1 bpf: fix possible endless loop in BPF map iteration

This patch fixes an endless loop condition that can occur in bpf_for_each_hash_elem, causing the core to softlock. My understanding is that a combination of RCU list deletion and insertion introduces the new element after the iteration cursor and that there is a chance that an RCU reader may in fact use this new element in iteration. The patch uses a _safe variant of the macro which gets the next element to iterate before executing the loop body for the current element. The following simple BPF program can be used to reproduce the issue:

    #include "vmlinux.h"
    #include <bpf/bpf_helpers.h>
    #include <bpf/bpf_tracing.h>

    #define N (64)

    struct {
        __uint(type,        BPF_MAP_TYPE_HASH);
        __uint(max_entries, N);
        __type(key,         __u64);
        __type(value,       __u64);
    } map SEC(".maps");

    static int cb(struct bpf_map *map, __u64 *key, __u64 *value, void *arg) {
        bpf_map_delete_elem(map, key);
        bpf_map_update_elem(map, key, value, 0);
        return 0;
    }

    SEC("uprobe//proc/self/exe:test")
    int BPF_PROG(test) {
        __u64 i;

        bpf_for(i, 0, N) {
            bpf_map_update_elem(&map, &i, &i, 0);
        }

        bpf_for_each_map_elem(&map, cb, NULL, 0);

        return 0;
    }

    char LICENSE[] SEC("license") = "GPL";
---
 kernel/bpf/hashtab.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
kernel/bpf/hashtab.c +1 -1
index 5a5adc66b8e2..92b606d60020 100644
@@ -2189,7 +2189,7 @@ static long bpf_for_each_hash_elem(struct bpf_map *map, bpf_callback_t callback_
                b = &htab->buckets[i];
                rcu_read_lock();
                head = &b->head;
-               hlist_nulls_for_each_entry_rcu(elem, n, head, hash_node) {
+               hlist_nulls_for_each_entry_safe(elem, n, head, hash_node) {
                        key = elem->key;
                        if (is_percpu) {
                                /* current cpu value for percpu map */

--
2.49.0

#1 lore raw
Quoted 8 lines · Brandon Kammerdiener

This patch fixes an endless loop condition that can occur in bpf_for_each_hash_elem, causing the core to softlock. My understanding is that a combination of RCU list deletion and insertion introduces the new element after the iteration cursor and that there is a chance that an RCU reader may in fact use this new element in iteration. The patch uses a _safe variant of the macro which gets the next element to iterate before executing the loop body for the current element. The following simple BPF program can be used to reproduce the issue:

If you could integrate it into BPF selftests, it would help a lot. With AI copilot today, writing selftests is much easier and faster. ;)

Thanks!

#2 lore raw
In reply to Brandon Kammerdiener
Quoted 55 lines · Brandon Kammerdiener

This patch fixes an endless loop condition that can occur in bpf_for_each_hash_elem, causing the core to softlock. My understanding is that a combination of RCU list deletion and insertion introduces the new element after the iteration cursor and that there is a chance that an RCU reader may in fact use this new element in iteration. The patch uses a _safe variant of the macro which gets the next element to iterate before executing the loop body for the current element. The following simple BPF program can be used to reproduce the issue:

    #include "vmlinux.h"
    #include <bpf/bpf_helpers.h>
    #include <bpf/bpf_tracing.h>

    #define N (64)

    struct {
        __uint(type,        BPF_MAP_TYPE_HASH);
        __uint(max_entries, N);
        __type(key,         __u64);
        __type(value,       __u64);
    } map SEC(".maps");

    static int cb(struct bpf_map *map, __u64 *key, __u64 *value, void *arg) {
        bpf_map_delete_elem(map, key);
        bpf_map_update_elem(map, key, value, 0);
        return 0;
    }

    SEC("uprobe//proc/self/exe:test")
    int BPF_PROG(test) {
        __u64 i;

        bpf_for(i, 0, N) {
            bpf_map_update_elem(&map, &i, &i, 0);
        }

        bpf_for_each_map_elem(&map, cb, NULL, 0);

        return 0;
    }

    char LICENSE[] SEC("license") = "GPL";
---
 kernel/bpf/hashtab.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
kernel/bpf/hashtab.c +0 -0
index 5a5adc66b8e2..92b606d60020 100644

kernel/bpf/hashtab.c static long bpf_for_each_hash_elem(struct bpf_map *map, bpf_callback_t callback_ · line 2192

Quoted 5 lines
kernel/bpf/hashtab.c +1 -1
@@ -2189,7 +2189,7 @@ static long bpf_for_each_hash_elem(struct bpf_map *map, bpf_callback_t callback_
                b = &htab->buckets[i];
                rcu_read_lock();
                head = &b->head;
-               hlist_nulls_for_each_entry_rcu(elem, n, head, hash_node) {
+               hlist_nulls_for_each_entry_safe(elem, n, head, hash_node) {

The patch doesn't apply. It's white space damaged. Please see Documentation/process/submitting-patches.rst

#3 lore raw
In reply to Brandon Kammerdiener
Quoted 34 lines · Brandon Kammerdiener

This patch fixes an endless loop condition that can occur in bpf_for_each_hash_elem, causing the core to softlock. My understanding is that a combination of RCU list deletion and insertion introduces the new element after the iteration cursor and that there is a chance that an RCU reader may in fact use this new element in iteration. The patch uses a _safe variant of the macro which gets the next element to iterate before executing the loop body for the current element. The following simple BPF program can be used to reproduce the issue:

     #include "vmlinux.h"
     #include <bpf/bpf_helpers.h>
     #include <bpf/bpf_tracing.h>

     #define N (64)

     struct {
         __uint(type,        BPF_MAP_TYPE_HASH);
         __uint(max_entries, N);
         __type(key,         __u64);
         __type(value,       __u64);
     } map SEC(".maps");

     static int cb(struct bpf_map *map, __u64 *key, __u64 *value, void *arg) {
         bpf_map_delete_elem(map, key);
         bpf_map_update_elem(map, key, value, 0);
         return 0;
     }

     SEC("uprobe//proc/self/exe:test")
     int BPF_PROG(test) {
         __u64 i;

         bpf_for(i, 0, N) {
             bpf_map_update_elem(&map, &i, &i, 0);
Quoted 8 lines
         }

         bpf_for_each_map_elem(&map, cb, NULL, 0);

         return 0;
     }

     char LICENSE[] SEC("license") = "GPL";

Please put this reproducer into a bpf selftests.

Take a look at tools/testing/selftests/bpf/prog_tests/for_each.c. Adding a subtest under it should do.