Patch to Fix deadlocks in queue and stack maps
Subsystems (3)
PATCH 1/2 Patch to Fix deadlocks in queue and stack maps
From: Siddharth Chintamaneni <[email protected]>
This patch address a possible deadlock issue in queue and stack map types.
Deadlock could happen when a nested BPF program acquires the same lock as the parent BPF program to perform a write operation on the same map as the first one. This bug is also reported by syzbot.
--- kernel/bpf/queue_stack_maps.c | 42 +++++++++++++++++++++++++++++++++++ 1 file changed, 42 insertions(+)
kernel/bpf/queue_stack_maps.c +42 -0
@@ -18,6 +18,7 @@ struct bpf_queue_stack {raw_spinlock_t lock;u32 head, tail;u32 size;/* max_entries + 1 */ +int __percpu *map_locked;char elements[]__aligned(8) ; };
@@ -78,6 +79,16 @@ static struct bpf_map *queue_stack_map_alloc(union bpf_attr *attr) qs->size = size; + qs->map_locked =bpf_map_alloc_percpu (&qs->map, +sizeof (int ), +sizeof (int ), +GFP_USER ); +if (!qs->map_locked) { +bpf_map_area_free (qs); +return ERR_PTR (-ENOMEM ); + } + +raw_spin_lock_init (&qs->lock);return &qs->map;
@@ -98,6 +109,16 @@ static long __queue_map_get(struct bpf_map *map, void *value, bool delete)int err =0 ;void *ptr; +preempt_disable (); +local_irq_save (flags); +if (unlikely (__this_cpu_inc_return (*(qs->map_locked)) !=1 )) { +__this_cpu_dec (*(qs->map_locked)); +local_irq_restore (flags); +preempt_enable (); +return -EBUSY ; + } +preempt_enable (); +if (in_nmi ()) {if (!raw_spin_trylock_irqsave (&qs->lock, flags))return -EBUSY ;
@@ -133,6 +154,17 @@ static long __stack_map_get(struct bpf_map *map, void *value, bool delete)void *ptr;u32 index; +preempt_disable (); +local_irq_save (flags); +if (unlikely (__this_cpu_inc_return (*(qs->map_locked)) !=1 )) { +__this_cpu_dec (*(qs->map_locked)); +local_irq_restore (flags); +preempt_enable (); +return -EBUSY ; + } +preempt_enable (); + +if (in_nmi ()) {if (!raw_spin_trylock_irqsave (&qs->lock, flags))return -EBUSY ;
@@ -194,6 +226,16 @@ static long queue_stack_map_push_elem(struct bpf_map *map, void *value,int err =0 ;void *dst; +preempt_disable (); +local_irq_save (irq_flags); +if (unlikely (__this_cpu_inc_return (*(qs->map_locked)) !=1 )) { +__this_cpu_dec (*(qs->map_locked)); +local_irq_restore (irq_flags); +preempt_enable (); +return -EBUSY ; + } +preempt_enable (); +/* BPF_EXIST is used to force making room for a new element in case the * map is full */
Signature · 1 line
2.44.0
PATCH 2/2 Added selftests to check deadlocks in queue and stack map
From: Siddharth Chintamaneni <[email protected]>
Added selftests to check for nested deadlocks in queue and stack maps.
--- .../prog_tests/test_queue_stack_nested_map.c | 48 ++++++++++++++ .../bpf/progs/test_queue_stack_nested_map.c | 62 +++++++++++++++++++ 2 files changed, 110 insertions(+) create mode 100644 tools/testing/selftests/bpf/prog_tests/test_queue_stack_nested_map.c create mode 100644 tools/testing/selftests/bpf/progs/test_queue_stack_nested_map.c
tools/testing/selftests/bpf/prog_tests/test_queue_stack_nested_map.c new file +48 -0
@@ -0,0 +1,48 @@ +// SPDX-License-Identifier: GPL-2.0 +#include <test_progs.h> +#include <network_helpers.h> + +#include "test_queue_stack_nested_map.skel.h" + + +static void test_map_queue_stack_nesting_success (bool is_map_queue) +{ +struct test_queue_stack_nested_map *skel; +int err; +int prog_fd; + +LIBBPF_OPTS (bpf_test_run_opts, ropts); + + skel =test_queue_stack_nested_map__open_and_load (); +if (!ASSERT_OK_PTR (skel,"test_queue_stack_nested_map__open_and_load" )) + goto out; + + err =test_queue_stack_nested_map__attach (skel); +if (!ASSERT_OK (err,"test_queue_stack_nested_map__attach" )) + goto out; + +if (is_map_queue) { + prog_fd =bpf_program__fd (skel->progs.test_queue_nesting); + err =bpf_prog_test_run_opts (prog_fd, &ropts); +ASSERT_OK (err,"test_nested_queue_map_run" ); + }else { + prog_fd =bpf_program__fd (skel->progs.test_stack_nesting); + err =bpf_prog_test_run_opts (prog_fd, &ropts); +ASSERT_OK (err,"test_nested_stack_map_run" ); + } + + + +out: +test_queue_stack_nested_map__destroy (skel); +} + +void test_test_queue_stack_nested_map (void ) +{ +if (test__start_subtest ("map_queue_nesting" )) +test_map_queue_stack_nesting_success (true); +if (test__start_subtest ("map_stack_nesting" )) +test_map_queue_stack_nesting_success (false); + +} +
tools/testing/selftests/bpf/progs/test_queue_stack_nested_map.c new file +62 -0
62 lines not on this page · raw message
Signature · 1 line
2.44.0
Kumar Kartikeya Dwivedi
maintainerRe: [PATCH bpf-next 2/2] Added selftests to check deadlocks in queue and stack map
Quoted 8 lines · Siddharth Chintamaneni
From: Siddharth Chintamaneni <[email protected]>
Added selftests to check for nested deadlocks in queue and stack maps.
Signed-off-by Siddharth Chintamaneni <[email protected]>---
Forgot to remind in the previous reply, but:
For the patch subject, use 'bpf:' prefix for kernel patches, and 'selftests/bpf:' for selftests, see the commit logs in bpf-next for examples.
Quoted 29 lines
.../prog_tests/test_queue_stack_nested_map.c | 48 ++++++++++++++ .../bpf/progs/test_queue_stack_nested_map.c | 62 +++++++++++++++++++ 2 files changed, 110 insertions(+) create mode 100644 tools/testing/selftests/bpf/prog_tests/test_queue_stack_nested_map.c create mode 100644 tools/testing/selftests/bpf/progs/test_queue_stack_nested_map.ctools/testing/selftests/bpf/prog_tests/test_queue_stack_nested_map.c new file +17
-0@@ -0,0 +1,48 @@ +// SPDX-License-Identifier: GPL-2.0 +#include <test_progs.h> +#include <network_helpers.h> + +#include "test_queue_stack_nested_map.skel.h" + + +static void test_map_queue_stack_nesting_success (bool is_map_queue) +{ +struct test_queue_stack_nested_map *skel; +int err; +int prog_fd; + +LIBBPF_OPTS (bpf_test_run_opts, ropts); + + skel =test_queue_stack_nested_map__open_and_load (); +if (!ASSERT_OK_PTR (skel,"test_queue_stack_nested_map__open_and_load" ))
tools/testing/selftests/bpf/prog_tests/test_queue_stack_nested_map.c line 27
Quoted 10 lines
tools/testing/selftests/bpf/prog_tests/test_queue_stack_nested_map.c new file +10
-0+ goto out; + + err =test_queue_stack_nested_map__attach (skel); +if (!ASSERT_OK (err,"test_queue_stack_nested_map__attach" )) + goto out; + +if (is_map_queue) { + prog_fd =bpf_program__fd (skel->progs.test_queue_nesting); + err =bpf_prog_test_run_opts (prog_fd, &ropts); +ASSERT_OK (err,"test_nested_queue_map_run" );
Maybe you can also check the ropts.optval to ensure we get -EBUSY? I.e. return the value of map push/pop from the program and then check it here?
It can be set in a global variable from the program triggering the deadlock, and then you could return the value back as the return value of the program.
If fentry has restrictions on the return code, you could try other program types which work in test_run_opts (like SEC("tc")), there are many examples in selftests using such programs.
Quoted 3 lines
[...]
Re: [PATCH bpf-next 2/2] Added selftests to check deadlocks in queue and stack map
Quoted 9 lines · Kumar Kartikeya Dwivedi
Quoted 6 lines · Siddharth Chintamaneni
From: Siddharth Chintamaneni <[email protected]>
Added selftests to check for nested deadlocks in queue and stack maps.
Quoted 7 lines
Quoted 2 lines
Signed-off-by Siddharth Chintamaneni <[email protected]>---
Forgot to remind in the previous reply, but:
For the patch subject, use 'bpf:' prefix for kernel patches, and 'selftests/bpf:' for selftests, see the commit logs in bpf-next for examples.
Thanks, I will do that in the revision.
Quoted 36 lines
Quoted 36 lines
.../prog_tests/test_queue_stack_nested_map.c | 48 ++++++++++++++ .../bpf/progs/test_queue_stack_nested_map.c | 62 +++++++++++++++++++ 2 files changed, 110 insertions(+) create mode 100644 tools/testing/selftests/bpf/prog_tests/test_queue_stack_nested_map.c create mode 100644 tools/testing/selftests/bpf/progs/test_queue_stack_nested_map.ctools/testing/selftests/bpf/prog_tests/test_queue_stack_nested_map.c new file +23
-0@@ -0,0 +1,48 @@ +// SPDX-License-Identifier: GPL-2.0 +#include <test_progs.h> +#include <network_helpers.h> + +#include "test_queue_stack_nested_map.skel.h" + + +static void test_map_queue_stack_nesting_success (bool is_map_queue) +{ +struct test_queue_stack_nested_map *skel; +int err; +int prog_fd; + +LIBBPF_OPTS (bpf_test_run_opts, ropts); + + skel =test_queue_stack_nested_map__open_and_load (); +if (!ASSERT_OK_PTR (skel,"test_queue_stack_nested_map__open_and_load" )) + goto out; + + err =test_queue_stack_nested_map__attach (skel); +if (!ASSERT_OK (err,"test_queue_stack_nested_map__attach" )) + goto out; +
Quoted 8 lines
tools/testing/selftests/bpf/prog_tests/test_queue_stack_nested_map.c line 27
Quoted 4 lines
tools/testing/selftests/bpf/prog_tests/test_queue_stack_nested_map.c new file +4
-0+if (is_map_queue) { + prog_fd =bpf_program__fd (skel->progs.test_queue_nesting); + err =bpf_prog_test_run_opts (prog_fd, &ropts); +ASSERT_OK (err,"test_nested_queue_map_run" );Maybe you can also check the ropts.optval to ensure we get
-EBUSY? I.e. return the value of map push/pop from the program and then check it here?
make sense.I will do that.
Quoted 10 lines
It can be set in a global variable from the program triggering the deadlock, and then you could return the value back as the return value of the program.
If fentry has restrictions on the return code, you could try other program types which work intest_run_opts(likeSEC("tc")), there are many examples in selftests using such programs.Quoted 3 lines
[...]
Kumar Kartikeya Dwivedi
maintainerQuoted 33 lines · Siddharth Chintamaneni
From: Siddharth Chintamaneni <[email protected]>
This patch address a possible deadlock issue in queue and stack map types.
Deadlock could happen when a nested BPF program acquires the same lock as the parent BPF program to perform a write operation on the same map as the first one. This bug is also reported by syzbot.
Reported-by [email protected]Fixes f1a2e44a3aec ("bpf: add queue and stack maps")Signed-off-by Siddharth Chintamaneni <[email protected]>--- kernel/bpf/queue_stack_maps.c | 42 +++++++++++++++++++++++++++++++++++ 1 file changed, 42 insertions(+)kernel/bpf/queue_stack_maps.c +1
-0@@ -18,6 +18,7 @@ struct bpf_queue_stack {raw_spinlock_t lock;u32 head, tail;u32 size;/* max_entries + 1 */ +int __percpu *map_locked;char elements[]__aligned(8) ; };
kernel/bpf/queue_stack_maps.c static struct bpf_map *queue_stack_map_alloc(union bpf_attr *attr) · line 85
Quoted 7 lines
kernel/bpf/queue_stack_maps.c +4
-0@@ -78,6 +79,16 @@ static struct bpf_map *queue_stack_map_alloc(union bpf_attr *attr) qs->size = size; + qs->map_locked =bpf_map_alloc_percpu (&qs->map, +sizeof (int ), +sizeof (int ), +GFP_USER );
GFP_USER | __GFP_NOWARN, like we do everywhere else.
Quoted 13 lines
kernel/bpf/queue_stack_maps.c +6
-0+if (!qs->map_locked) { +bpf_map_area_free (qs); +return ERR_PTR (-ENOMEM ); + } + +raw_spin_lock_init (&qs->lock);return &qs->map;@@ -98,6 +109,16 @@ static long __queue_map_get(struct bpf_map *map, void *value, bool delete)int err =0 ;void *ptr;
kernel/bpf/queue_stack_maps.c static long __queue_map_get(struct bpf_map *map, void *value, bool delete) · line 121
Quoted 10 lines
kernel/bpf/queue_stack_maps.c +10
-0+preempt_disable (); +local_irq_save (flags); +if (unlikely (__this_cpu_inc_return (*(qs->map_locked)) !=1 )) { +__this_cpu_dec (*(qs->map_locked)); +local_irq_restore (flags); +preempt_enable (); +return -EBUSY ; + } +preempt_enable (); +
You increment, but don't decrement the map_locked counter after unlock. Likewise in all other cases. Then this operation cannot be called anymore after the first time on a given cpu for a given map. Probably why CI is also failing.
https://github.com/kernel-patches/bpf/actions/runs/8882578097/job/24387802831?pr=6915
returns -16 (EBUSY).
E.g. check hashtab.c, it does __this_cpu_dec after unlock in htab_unlock_bucket.
Quoted 3 lines
[...]
Quoted 70 lines · Kumar Kartikeya Dwivedi
Quoted 33 lines · Siddharth Chintamaneni
From: Siddharth Chintamaneni <[email protected]>
This patch address a possible deadlock issue in queue and stack map types.
Deadlock could happen when a nested BPF program acquires the same lock as the parent BPF program to perform a write operation on the same map as the first one. This bug is also reported by syzbot.
Reported-by [email protected]Fixes f1a2e44a3aec ("bpf: add queue and stack maps")Signed-off-by Siddharth Chintamaneni <[email protected]>--- kernel/bpf/queue_stack_maps.c | 42 +++++++++++++++++++++++++++++++++++ 1 file changed, 42 insertions(+)kernel/bpf/queue_stack_maps.c +1
-0@@ -18,6 +18,7 @@ struct bpf_queue_stack {raw_spinlock_t lock;u32 head, tail;u32 size;/* max_entries + 1 */ +int __percpu *map_locked;char elements[]__aligned(8) ; };kernel/bpf/queue_stack_maps.c static struct bpf_map *queue_stack_map_alloc(union bpf_attr *attr) · line 85
Quoted 7 lines
kernel/bpf/queue_stack_maps.c +4
-0@@ -78,6 +79,16 @@ static struct bpf_map *queue_stack_map_alloc(union bpf_attr *attr) qs->size = size; + qs->map_locked =bpf_map_alloc_percpu (&qs->map, +sizeof (int ), +sizeof (int ), +GFP_USER );
GFP_USER|__GFP_NOWARN, like we do everywhere else.Quoted 13 lines
kernel/bpf/queue_stack_maps.c +6
-0+if (!qs->map_locked) { +bpf_map_area_free (qs); +return ERR_PTR (-ENOMEM ); + } + +raw_spin_lock_init (&qs->lock);return &qs->map;@@ -98,6 +109,16 @@ static long __queue_map_get(struct bpf_map *map, void *value, bool delete)int err =0 ;void *ptr;kernel/bpf/queue_stack_maps.c static long __queue_map_get(struct bpf_map *map, void *value, bool delete) · line 121
Quoted 10 lines
kernel/bpf/queue_stack_maps.c +10
-0+preempt_disable (); +local_irq_save (flags); +if (unlikely (__this_cpu_inc_return (*(qs->map_locked)) !=1 )) { +__this_cpu_dec (*(qs->map_locked)); +local_irq_restore (flags); +preempt_enable (); +return -EBUSY ; + } +preempt_enable (); +
Quoted 8 lines
You increment, but don't decrement the
map_lockedcounter after unlock. Likewise in all other cases. Then this operation cannot be called anymore after the first time on a given cpu for a given map. Probably why CI is also failing.
https://github.com/kernel-patches/bpf/actions/runs/8882578097/job/24387802831?pr=6915
returns -16 (EBUSY).
E.g. checkhashtab.c, it does__this_cpu_decafter unlock inhtab_unlock_bucket.
My bad I sent a wrong patch, I will send a revised version.
Quoted 3 lines
Quoted 3 lines
[...]
Hi Siddharth,
kernel test robot noticed the following build warnings:
url: https://github.com/intel-lab-lkp/linux/commits/Siddharth-Chintamaneni/Added-selftests-to-check-deadlocks-in-queue-and-stack-map/20240430-142201 base: https://git.kernel.org/pub/scm/linux/kernel/git/bpf/bpf-next.git master patch link: https://lore.kernel.org/r/20240429165658.1305969-1-sidchintamaneni%40gmail.com patch subject: [PATCH bpf-next 1/2] Patch to Fix deadlocks in queue and stack maps config: i386-randconfig-141-20240504 (https://download.01.org/0day-ci/archive/20240504/[email protected]/config) compiler: clang version 18.1.4 (https://github.com/llvm/llvm-project e6c3289804a67ea0bb6a86fadbe454dd93b8d855)
If you fix the issue in a separate patch/commit (i.e. not just a new version of the same patch/commit), kindly add following tags
| Reported-by: kernel test robot <[email protected]> | Reported-by: Dan Carpenter <[email protected]> | Closes: https://lore.kernel.org/r/[email protected]/
smatch warnings:kernel/bpf/queue_stack_maps.c:273 queue_stack_map_push_elem() warn: inconsistent returns 'irq_flags'.
vim +/irq_flags +273 kernel/bpf/queue_stack_maps.c
f1a2e44a3aeccb Mauricio Vasquez B 2018-10-18 219
f1a2e44a3aeccb Mauricio Vasquez B 2018-10-18 220 /* Called from syscall or from eBPF program */
d7ba4cc900bf1e JP Kobryn 2023-03-22 221 static long queue_stack_map_push_elem(struct bpf_map *map, void *value,
f1a2e44a3aeccb Mauricio Vasquez B 2018-10-18 222 u64 flags)
f1a2e44a3aeccb Mauricio Vasquez B 2018-10-18 223 {
f1a2e44a3aeccb Mauricio Vasquez B 2018-10-18 224 struct bpf_queue_stack *qs = bpf_queue_stack(map);
f1a2e44a3aeccb Mauricio Vasquez B 2018-10-18 225 unsigned long irq_flags;
f1a2e44a3aeccb Mauricio Vasquez B 2018-10-18 226 int err = 0;
f1a2e44a3aeccb Mauricio Vasquez B 2018-10-18 227 void *dst;
f1a2e44a3aeccb Mauricio Vasquez B 2018-10-18 228
568ce03b978beb Siddharth Chintamaneni 2024-04-29 229 preempt_disable();
568ce03b978beb Siddharth Chintamaneni 2024-04-29 230 local_irq_save(irq_flags);
568ce03b978beb Siddharth Chintamaneni 2024-04-29 231 if (unlikely(__this_cpu_inc_return(*(qs->map_locked)) != 1)) {
568ce03b978beb Siddharth Chintamaneni 2024-04-29 232 __this_cpu_dec(*(qs->map_locked));
568ce03b978beb Siddharth Chintamaneni 2024-04-29 233 local_irq_restore(irq_flags);
568ce03b978beb Siddharth Chintamaneni 2024-04-29 234 preempt_enable();
568ce03b978beb Siddharth Chintamaneni 2024-04-29 235 return -EBUSY;
568ce03b978beb Siddharth Chintamaneni 2024-04-29 236 }
568ce03b978beb Siddharth Chintamaneni 2024-04-29 237 preempt_enable();
568ce03b978beb Siddharth Chintamaneni 2024-04-29 238
f1a2e44a3aeccb Mauricio Vasquez B 2018-10-18 239 /* BPF_EXIST is used to force making room for a new element in case the
f1a2e44a3aeccb Mauricio Vasquez B 2018-10-18 240 * map is full
f1a2e44a3aeccb Mauricio Vasquez B 2018-10-18 241 */
f1a2e44a3aeccb Mauricio Vasquez B 2018-10-18 242 bool replace = (flags & BPF_EXIST);
f1a2e44a3aeccb Mauricio Vasquez B 2018-10-18 243
f1a2e44a3aeccb Mauricio Vasquez B 2018-10-18 244 /* Check supported flags for queue and stack maps */
f1a2e44a3aeccb Mauricio Vasquez B 2018-10-18 245 if (flags & BPF_NOEXIST || flags > BPF_EXIST)
f1a2e44a3aeccb Mauricio Vasquez B 2018-10-18 246 return -EINVAL;local_irq_restore(irq_flags) before returning.
f1a2e44a3aeccb Mauricio Vasquez B 2018-10-18 247
a34a9f1a19afe9 Toke Høiland-Jørgensen 2023-09-11 248 if (in_nmi()) {
a34a9f1a19afe9 Toke Høiland-Jørgensen 2023-09-11 249 if (!raw_spin_trylock_irqsave(&qs->lock, irq_flags))_irqsave can't be nested. Has this code been tested? Perhaps it works because the callers always call this with IRQs disabled.
a34a9f1a19afe9 Toke Høiland-Jørgensen 2023-09-11 250 return -EBUSY;
a34a9f1a19afe9 Toke Høiland-Jørgensen 2023-09-11 251 } else {
f1a2e44a3aeccb Mauricio Vasquez B 2018-10-18 252 raw_spin_lock_irqsave(&qs->lock, irq_flags);
a34a9f1a19afe9 Toke Høiland-Jørgensen 2023-09-11 253 }
f1a2e44a3aeccb Mauricio Vasquez B 2018-10-18 254
f1a2e44a3aeccb Mauricio Vasquez B 2018-10-18 255 if (queue_stack_map_is_full(qs)) {
f1a2e44a3aeccb Mauricio Vasquez B 2018-10-18 256 if (!replace) {
f1a2e44a3aeccb Mauricio Vasquez B 2018-10-18 257 err = -E2BIG;
f1a2e44a3aeccb Mauricio Vasquez B 2018-10-18 258 goto out;
f1a2e44a3aeccb Mauricio Vasquez B 2018-10-18 259 }
f1a2e44a3aeccb Mauricio Vasquez B 2018-10-18 260 /* advance tail pointer to overwrite oldest element */
f1a2e44a3aeccb Mauricio Vasquez B 2018-10-18 261 if (unlikely(++qs->tail >= qs->size))
f1a2e44a3aeccb Mauricio Vasquez B 2018-10-18 262 qs->tail = 0;
f1a2e44a3aeccb Mauricio Vasquez B 2018-10-18 263 }
f1a2e44a3aeccb Mauricio Vasquez B 2018-10-18 264
f1a2e44a3aeccb Mauricio Vasquez B 2018-10-18 265 dst = &qs->elements[qs->head * qs->map.value_size];
f1a2e44a3aeccb Mauricio Vasquez B 2018-10-18 266 memcpy(dst, value, qs->map.value_size);
f1a2e44a3aeccb Mauricio Vasquez B 2018-10-18 267
f1a2e44a3aeccb Mauricio Vasquez B 2018-10-18 268 if (unlikely(++qs->head >= qs->size))
f1a2e44a3aeccb Mauricio Vasquez B 2018-10-18 269 qs->head = 0;
f1a2e44a3aeccb Mauricio Vasquez B 2018-10-18 270
f1a2e44a3aeccb Mauricio Vasquez B 2018-10-18 271 out:
f1a2e44a3aeccb Mauricio Vasquez B 2018-10-18 272 raw_spin_unlock_irqrestore(&qs->lock, irq_flags);
f1a2e44a3aeccb Mauricio Vasquez B 2018-10-18 @273 return err;
f1a2e44a3aeccb Mauricio Vasquez B 2018-10-18 274 }Signature · 2 lines
0-DAY CI Kernel Test Service https://github.com/intel/lkp-tests/wiki