bpf: hash map, avoid deadlock with suitable hash mask
Subsystems (3)
PATCH v2 1/2 bpf: hash map, avoid deadlock with suitable hash mask
From: Tonghao Zhang <[email protected]>
The deadlock still may occur while accessed in NMI and non-NMI context. Because in NMI, we still may access the same bucket but with different map_locked index.
For example, on the same CPU, .max_entries = 2, we update the hash map, with key = 4, while running bpf prog in NMI nmi_handle(), to update hash map with key = 20, so it will have the same bucket index but have different map_locked index.
To fix this issue, using min mask to hash again.
--- kernel/bpf/hashtab.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-)
kernel/bpf/hashtab.c +2 -2
@@ -152,7 +152,7 @@ static inline int htab_lock_bucket(const struct bpf_htab *htab, {unsigned long flags; - hash = hash &HASHTAB_MAP_LOCK_MASK ; + hash = hash &min_t (u32,HASHTAB_MAP_LOCK_MASK , htab->n_buckets -1 );preempt_disable ();if (unlikely (__this_cpu_inc_return (*(htab->map_locked[hash])) !=1 )) {
@@ -171,7 +171,7 @@ static inline void htab_unlock_bucket(const struct bpf_htab *htab, struct bucket *b, u32 hash, unsigned long flags) { - hash = hash &HASHTAB_MAP_LOCK_MASK ; + hash = hash &min_t (u32,HASHTAB_MAP_LOCK_MASK , htab->n_buckets -1 );raw_spin_unlock_irqrestore (&b->raw_lock, flags);__this_cpu_dec (*(htab->map_locked[hash]));preempt_enable ();
Signature · 1 line
2.27.0
PATCH v2 2/2 selftests/bpf: add test case for htab map
From: Tonghao Zhang <[email protected]>
This testing show how to reproduce deadlock in special case. We update htab map in Task and NMI context. Task can be interrupted by NMI, if the same map bucket was locked, there will be a deadlock.
* map max_entries is 2.
* NMI using key 4 and Task context using key 20.
* so same bucket index but map_locked index is different.
The selftest use perf to produce the NMI and fentry nmi_handle. Note that bpf_overflow_handler checks bpf_prog_active, but in bpf update map syscall increase this counter in bpf_disable_instrumentation. Then fentry nmi_handle and update hash map will reproduce the issue.
--- tools/testing/selftests/bpf/DENYLIST.aarch64 | 1 + tools/testing/selftests/bpf/DENYLIST.s390x | 1 + .../selftests/bpf/prog_tests/htab_deadlock.c | 75 +++++++++++++++++++ .../selftests/bpf/progs/htab_deadlock.c | 30 ++++++++ 4 files changed, 107 insertions(+) create mode 100644 tools/testing/selftests/bpf/prog_tests/htab_deadlock.c create mode 100644 tools/testing/selftests/bpf/progs/htab_deadlock.c
tools/testing/selftests/bpf/DENYLIST.aarch64 +1 -0
@@ -24,6 +24,7 @@ fexit_test # fexit_attach unexpected error get_func_args_test # get_func_args_test__attach unexpected error: -524 (errno 524) (trampoline) get_func_ip_test # get_func_ip_test__attach unexpected error: -524 (errno 524) (trampoline) htab_update/reenter_update +htab_deadlock # failed to find kernel BTF type ID of 'nmi_handle': -3 (trampoline) kfree_skb # attach fentry unexpected error: -524 (trampoline) kfunc_call/subprog # extern (var ksym) 'bpf_prog_active': not found in kernel BTF kfunc_call/subprog_lskel # skel unexpected error: -2
tools/testing/selftests/bpf/DENYLIST.s390x +1 -0
@@ -26,6 +26,7 @@ get_func_args_test # trampoline get_func_ip_test # get_func_ip_test__attach unexpected error: -524 (trampoline) get_stack_raw_tp # user_stack corrupted user stack (no backchain userspace) htab_update # failed to attach: ERROR: strerror_r(-524)=22 (trampoline) +htab_deadlock # failed to find kernel BTF type ID of 'nmi_handle': -3 (trampoline) kfree_skb # attach fentry unexpected error: -524 (trampoline) kfunc_call # 'bpf_prog_active': not found in kernel BTF (?) kfunc_dynptr_param # JIT does not support calling kernel function (kfunc)
tools/testing/selftests/bpf/prog_tests/htab_deadlock.c new file +75 -0
75 lines not on this page · raw message
tools/testing/selftests/bpf/progs/htab_deadlock.c new file +30 -0
@@ -0,0 +1,30 @@ +// SPDX-License-Identifier: GPL-2.0 +/* Copyright (c) 2022 DiDi Global Inc. */ +#include <linux/bpf.h> +#include <bpf/bpf_helpers.h> +#include <bpf/bpf_tracing.h> + +char _license[] SEC("license") = "GPL"; + +struct { + __uint(type, BPF_MAP_TYPE_HASH); + __uint(max_entries, 2); + __uint(map_flags, BPF_F_ZERO_SEED); + __type(key, unsigned int); + __type(value, unsigned int); +} htab SEC(".maps"); + +SEC("fentry/nmi_handle") +int bpf_nmi_handle (struct pt_regs *regs) +{ +unsigned int val =0 , key =4 ; + +bpf_map_update_elem (&htab, &key, &val,BPF_ANY ); +return 0 ; +} + +SEC("perf_event") +int bpf_empty (struct pt_regs *regs) +{ +return 0 ; +}
Signature · 1 line
2.27.0
Re: [bpf-next v2 2/2] selftests/bpf: add test case for htab map
Quoted 15 lines · On 12/17/22 7:02 AM, [email protected] wrote:
From: Tonghao Zhang <[email protected]>
This testing show how to reproduce deadlock in special case. We update htab map in Task and NMI context. Task can be interrupted by NMI, if the same map bucket was locked, there will be a deadlock.
* map
max_entriesis 2.
* NMI using key 4 and Task context using key 20.
* so same bucket index butmap_lockedindex is different.The selftest use perf to produce the NMI and fentry
nmi_handle. Note thatbpf_overflow_handlerchecksbpf_prog_active, but in bpf update map syscall increase this counter inbpf_disable_instrumentation. Then fentrynmi_handleand update hash map will reproduce the issue.
Quoted 13 lines
Signed-off-by Tonghao Zhang <[email protected]>Cc Alexei Starovoitov <[email protected]>Cc Daniel Borkmann <[email protected]>Cc Andrii Nakryiko <[email protected]>Cc Martin KaFai Lau <[email protected]>Cc Song Liu <[email protected]>Cc Yonghong Song <[email protected]>Cc John Fastabend <[email protected]>Cc KP Singh <[email protected]>Cc Stanislav Fomichev <[email protected]>Cc Hao Luo <[email protected]>Cc Jiri Olsa <[email protected]>Cc Hou Tao <[email protected]>
Ack with a small nit below.
Quoted 9 lines
--- tools/testing/selftests/bpf/DENYLIST.aarch64 | 1 + tools/testing/selftests/bpf/DENYLIST.s390x | 1 + .../selftests/bpf/prog_tests/htab_deadlock.c | 75 +++++++++++++++++++ .../selftests/bpf/progs/htab_deadlock.c | 30 ++++++++ 4 files changed, 107 insertions(+)create mode 100644
tools/testing/selftests/bpf/prog_tests/htab_deadlock.ccreate mode 100644tools/testing/selftests/bpf/progs/htab_deadlock.c
[...]
Quoted 13 lines
tools/testing/selftests/bpf/progs/htab_deadlock.c new file +7
-0@@ -0,0 +1,30 @@ +// SPDX-License-Identifier: GPL-2.0 +/* Copyright (c) 2022 DiDi Global Inc. */ +#include <linux/bpf.h> +#include <bpf/bpf_helpers.h> +#include <bpf/bpf_tracing.h> + +char _license[] SEC("license") = "GPL";
tools/testing/selftests/bpf/progs/htab_deadlock.c line 17
Quoted 10 lines
tools/testing/selftests/bpf/progs/htab_deadlock.c new file +10
-0+ +struct { + __uint(type, BPF_MAP_TYPE_HASH); + __uint(max_entries, 2); + __uint(map_flags, BPF_F_ZERO_SEED); + __type(key, unsigned int); + __type(value, unsigned int); +} htab SEC(".maps"); + +SEC ("fentry/nmi_handle" )
nmi_handle() is a static function. In my setup, it is not inlined. But if it is inlined, the test will succeed regardless of the previous fix. But currently we don't have mechanisms to discover such situations, so I am okay with the test. But it would be good if you can add a small comment
to explain this caveat.
Quoted 13 lines
tools/testing/selftests/bpf/progs/htab_deadlock.c new file +13
-0+int bpf_nmi_handle (struct pt_regs *regs) +{ +unsigned int val =0 , key =4 ; + +bpf_map_update_elem (&htab, &key, &val,BPF_ANY ); +return 0 ; +} + +SEC("perf_event") +int bpf_empty (struct pt_regs *regs) +{ +return 0 ; +}
Re: [bpf-next v2 2/2] selftests/bpf: add test case for htab map
Quoted 69 lines · Yonghong Song
Quoted 15 lines · On 12/17/22 7:02 AM, [email protected] wrote:
From: Tonghao Zhang <[email protected]>
This testing show how to reproduce deadlock in special case. We update htab map in Task and NMI context. Task can be interrupted by NMI, if the same map bucket was locked, there will be a deadlock.
* map
max_entriesis 2.
* NMI using key 4 and Task context using key 20.
* so same bucket index butmap_lockedindex is different.The selftest use perf to produce the NMI and fentry
nmi_handle. Note thatbpf_overflow_handlerchecksbpf_prog_active, but in bpf update map syscall increase this counter inbpf_disable_instrumentation. Then fentrynmi_handleand update hash map will reproduce the issue.Quoted 13 lines
Signed-off-by Tonghao Zhang <[email protected]>Cc Alexei Starovoitov <[email protected]>Cc Daniel Borkmann <[email protected]>Cc Andrii Nakryiko <[email protected]>Cc Martin KaFai Lau <[email protected]>Cc Song Liu <[email protected]>Cc Yonghong Song <[email protected]>Cc John Fastabend <[email protected]>Cc KP Singh <[email protected]>Cc Stanislav Fomichev <[email protected]>Cc Hao Luo <[email protected]>Cc Jiri Olsa <[email protected]>Cc Hou Tao <[email protected]>Ack with a small nit below.
Acked-by Yonghong Song <[email protected]>Quoted 9 lines
--- tools/testing/selftests/bpf/DENYLIST.aarch64 | 1 + tools/testing/selftests/bpf/DENYLIST.s390x | 1 + .../selftests/bpf/prog_tests/htab_deadlock.c | 75 +++++++++++++++++++ .../selftests/bpf/progs/htab_deadlock.c | 30 ++++++++ 4 files changed, 107 insertions(+)create mode 100644
tools/testing/selftests/bpf/prog_tests/htab_deadlock.ccreate mode 100644tools/testing/selftests/bpf/progs/htab_deadlock.c[...]
Quoted 22 lines
tools/testing/selftests/bpf/progs/htab_deadlock.c new file +16
-0@@ -0,0 +1,30 @@ +// SPDX-License-Identifier: GPL-2.0 +/* Copyright (c) 2022 DiDi Global Inc. */ +#include <linux/bpf.h> +#include <bpf/bpf_helpers.h> +#include <bpf/bpf_tracing.h> + +char _license[] SEC("license") = "GPL"; + +struct { + __uint(type, BPF_MAP_TYPE_HASH); + __uint(max_entries, 2); + __uint(map_flags, BPF_F_ZERO_SEED); + __type(key, unsigned int); + __type(value, unsigned int); +} htab SEC(".maps"); +
Quoted 8 lines
tools/testing/selftests/bpf/progs/htab_deadlock.c line 17
Quoted 1 line
tools/testing/selftests/bpf/progs/htab_deadlock.c new file +1
-0+SEC ("fentry/nmi_handle" )
nmi_handle()is a static function. In my setup, it is not inlined. But if it is inlined, the test will succeed regardless of the previous fix. But currently we don't have mechanisms to discover such situations, so I am okay with the test. But it would be good if you can add a small comment
to explain this caveat.
Ok, Thanks
Quoted 13 lines
Quoted 13 lines
tools/testing/selftests/bpf/progs/htab_deadlock.c new file +13
-0+int bpf_nmi_handle (struct pt_regs *regs) +{ +unsigned int val =0 , key =4 ; + +bpf_map_update_elem (&htab, &key, &val,BPF_ANY ); +return 0 ; +} + +SEC("perf_event") +int bpf_empty (struct pt_regs *regs) +{ +return 0 ; +}
Signature · 1 line
Best regards, Tonghao