bpf: Avoid unnecessary deadlock detection and failure in task storage
Martin KaFai Lau
reviewercover bpf: Avoid unnecessary deadlock detection and failure in task storage
From: Martin KaFai Lau <[email protected]>
The commit bc235cdb423a ("bpf: Prevent deadlock from recursive bpf_task_storage_[get|delete]") added deadlock detection to avoid a tracing program from recurring
on the bpf_task_storage_{get,delete}() helpers. These helpers acquire
a spin lock and it will lead to deadlock.
It is unnecessary for the bpf_lsm and bpf_iter programs which do not recur. The situation is the same as the existing bpf_pid_task_storage_{lookup,delete}_elem() which are used in the syscall and they also do not have deadlock detection.
This set is to add new bpf_task_storage_{get,delete}() helper proto without the deadlock detection. The set also removes the prog->active check from the bpf_lsm and bpf_iter program. Please see the individual patch for details.
Martin KaFai Lau (9):
bpf: Remove prog->active check for bpf_lsm and bpf_iter
bpf: Append _recur naming to the bpf_task_storage helper proto
bpf: Refactor the core bpf_task_storage_get logic into a new function
bpf: Avoid taking spinlock in bpf_task_storage_get if potential
deadlock is detected
bpf: Add new bpf_task_storage_get proto with no deadlock detection
bpf: bpf_task_storage_delete_recur does lookup first before the
deadlock check
bpf: Add new bpf_task_storage_delete proto with no deadlock detection selftests/bpf: Ensure no task storage failure for bpf_lsm.s prog due
to deadlock detection
selftests/bpf: Tracing prog can still do lookup under busy lock
arch/arm64/net/bpf_jit_comp.c | 9 +- arch/x86/net/bpf_jit_comp.c | 19 +-- include/linux/bpf.h | 26 ++-- include/linux/bpf_verifier.h | 15 +- kernel/bpf/bpf_local_storage.c | 1 + kernel/bpf/bpf_task_storage.c | 119 +++++++++++--- kernel/bpf/syscall.c | 5 +- kernel/bpf/trampoline.c | 80 ++++++++-- kernel/trace/bpf_trace.c | 5 + .../bpf/prog_tests/task_local_storage.c | 146 +++++++++++++++++- .../selftests/bpf/progs/task_ls_recursion.c | 43 +++++- .../bpf/progs/task_storage_nodeadlock.c | 47 ++++++ 12 files changed, 431 insertions(+), 84 deletions(-) create mode 100644 tools/testing/selftests/bpf/progs/task_storage_nodeadlock.c
Signature · 1 line
2.30.2
Martin KaFai Lau
reviewerPATCH 1/9 bpf: Remove prog->active check for bpf_lsm and bpf_iter
From: Martin KaFai Lau <[email protected]>
The commit 64696c40d03c ("bpf: Add __bpf_prog_{enter,exit}_struct_ops for struct_ops trampoline") removed prog->active check for struct_ops prog. The bpf_lsm
and bpf_iter is also using trampoline. Like struct_ops, the bpf_lsm
and bpf_iter have fixed hooks for the prog to attach. The
kernel does not call the same hook in a recursive way.
This patch also removes the prog->active check forbpf_lsm and bpf_iter.
A later patch has a test to reproduce the recursion issue for a sleepable bpf_lsm program.
This patch appends the '_recur' naming to the existing enter and exit functions that track the prog->active counter. New __bpf_prog_{enter,exit}[_sleepable] function are added to skip the prog->active tracking. The '_struct_ops' version is also removed.
It also moves the decision on picking the enter and exit function to the new bpf_trampoline_{enter,exit}(). It returns the '_recur' ones for all tracing progs to use. For bpf_lsm, bpf_iter, struct_ops (no prog->active tracking after 64696c40d03c), and bpf_lsm_cgroup (no prog->active tracking after 69fd337a975c7), it will return the functions that don't track the prog->active.
--- arch/arm64/net/bpf_jit_comp.c | 9 +--- arch/x86/net/bpf_jit_comp.c | 19 +-------- include/linux/bpf.h | 24 +++++------ include/linux/bpf_verifier.h | 15 ++++++- kernel/bpf/syscall.c | 5 ++- kernel/bpf/trampoline.c | 80 +++++++++++++++++++++++++++++------ 6 files changed, 98 insertions(+), 54 deletions(-)
arch/arm64/net/bpf_jit_comp.c +2 -7
@@ -1649,13 +1649,8 @@ static void invoke_bpf_prog(struct jit_ctx *ctx, struct bpf_tramp_link *l,struct bpf_prog *p = l->link.prog;int cookie_off = offsetof(struct bpf_tramp_run_ctx , bpf_cookie); -if (p->aux->sleepable) { - enter_prog = (u64 )__bpf_prog_enter_sleepable; - exit_prog = (u64 )__bpf_prog_exit_sleepable; - }else { - enter_prog = (u64 )__bpf_prog_enter; - exit_prog = (u64 )__bpf_prog_exit; - } + enter_prog = (u64 )bpf_trampoline_enter (p); + exit_prog = (u64 )bpf_trampoline_exit (p);if (l->cookie ==0 ) {/* if cookie is zero, one instruction is enough to store it */
arch/x86/net/bpf_jit_comp.c +2 -17
@@ -1894,10 +1894,6 @@ static int invoke_bpf_prog(const struct btf_func_model *m, u8 **pprog, struct bpf_tramp_link *l, int stack_size, int run_ctx_off, bool save_ret) { - void (*exit)(struct bpf_prog *prog, u64 start, -struct bpf_tramp_run_ctx *run_ctx) = __bpf_prog_exit; -u64 (*enter)(struct bpf_prog *prog, -struct bpf_tramp_run_ctx *run_ctx) = __bpf_prog_enter; u8 *prog = *pprog;u8 *jmp_insn;int ctx_cookie_off = offsetof(struct bpf_tramp_run_ctx , bpf_cookie);
@@ -1916,23 +1912,12 @@ static int invoke_bpf_prog(const struct btf_func_model *m, u8 **pprog,*/ emit_stx (&prog,BPF_DW ,BPF_REG_FP ,BPF_REG_1 , -run_ctx_off + ctx_cookie_off); -if (p->aux->sleepable) { - enter = __bpf_prog_enter_sleepable; - exit = __bpf_prog_exit_sleepable; - }else if (p->type ==BPF_PROG_TYPE_STRUCT_OPS ) { - enter = __bpf_prog_enter_struct_ops; - exit = __bpf_prog_exit_struct_ops; - }else if (p->expected_attach_type ==BPF_LSM_CGROUP ) { - enter = __bpf_prog_enter_lsm_cgroup; - exit = __bpf_prog_exit_lsm_cgroup; - } -/* arg1: mov rdi, progs[i] */ emit_mov_imm64 (&prog,BPF_REG_1 , (long ) p >>32 , (u32 ) (long ) p);/* arg2: lea rsi, [rbp - ctx_cookie_off] */ EMIT4 (0x48 ,0x8D ,0x75 , -run_ctx_off); -if (emit_call (&prog, enter, prog)) +if (emit_call (&prog,bpf_trampoline_enter (p), prog))return -EINVAL ;/* remember prog start time returned by __bpf_prog_enter */ emit_mov_reg (&prog, true,BPF_REG_6 ,BPF_REG_0 );
@@ -1977,7 +1962,7 @@ static int invoke_bpf_prog(const struct btf_func_model *m, u8 **pprog,emit_mov_reg (&prog, true,BPF_REG_2 ,BPF_REG_6 );/* arg3: lea rdx, [rbp - run_ctx_off] */ EMIT4 (0x48 ,0x8D ,0x55 , -run_ctx_off); -if (emit_call (&prog, exit, prog)) +if (emit_call (&prog,bpf_trampoline_exit (p), prog))return -EINVAL ; *pprog = prog;
include/linux/bpf.h +10 -14
@@ -854,22 +854,18 @@ int arch_prepare_bpf_trampoline(struct bpf_tramp_image *tr, void *image, void *i const struct btf_func_model *m, u32 flags, struct bpf_tramp_links *tlinks, void *orig_call); -/* these two functions are called from generated trampoline */ -u64 notrace __bpf_prog_enter(struct bpf_prog *prog, struct bpf_tramp_run_ctx *run_ctx); -void notrace __bpf_prog_exit(struct bpf_prog *prog, u64 start, struct bpf_tramp_run_ctx *run_ctx); -u64 notrace __bpf_prog_enter_sleepable(struct bpf_prog *prog, struct bpf_tramp_run_ctx *run_ctx); -void notrace __bpf_prog_exit_sleepable(struct bpf_prog *prog, u64 start, -struct bpf_tramp_run_ctx *run_ctx); -u64 notrace __bpf_prog_enter_lsm_cgroup(struct bpf_prog *prog, -struct bpf_tramp_run_ctx *run_ctx); -void notrace __bpf_prog_exit_lsm_cgroup(struct bpf_prog *prog, u64 start, -struct bpf_tramp_run_ctx *run_ctx); -u64 notrace __bpf_prog_enter_struct_ops(struct bpf_prog *prog, -struct bpf_tramp_run_ctx *run_ctx); -void notrace __bpf_prog_exit_struct_ops(struct bpf_prog *prog, u64 start, -struct bpf_tramp_run_ctx *run_ctx); +u64 notrace __bpf_prog_enter_sleepable_recur(struct bpf_prog *prog, +struct bpf_tramp_run_ctx *run_ctx); +void notrace __bpf_prog_exit_sleepable_recur(struct bpf_prog *prog, u64 start, +struct bpf_tramp_run_ctx *run_ctx); void notrace __bpf_tramp_enter(struct bpf_tramp_image *tr); void notrace __bpf_tramp_exit(struct bpf_tramp_image *tr); +typedef u64 (*bpf_trampoline_enter_t )(struct bpf_prog *prog, +struct bpf_tramp_run_ctx *run_ctx); +typedef void (*bpf_trampoline_exit_t )(struct bpf_prog *prog,u64 start, +struct bpf_tramp_run_ctx *run_ctx); +bpf_trampoline_enter_t bpf_trampoline_enter (const struct bpf_prog *prog); +bpf_trampoline_exit_t bpf_trampoline_exit (const struct bpf_prog *prog);struct bpf_ksym {unsigned long start;
include/linux/bpf_verifier.h +14 -1
@@ -642,10 +642,23 @@ static inline u32 type_flag(u32 type) }/* only use after check_attach_btf_id() */ -static inline enum bpf_prog_type resolve_prog_type (struct bpf_prog *prog) +static inline enum bpf_prog_type resolve_prog_type (const struct bpf_prog *prog) {return prog->type ==BPF_PROG_TYPE_EXT ? prog->aux->dst_prog->type : prog->type; } +static inline bool bpf_prog_check_recur (const struct bpf_prog *prog) +{ +switch (resolve_prog_type (prog)) { +case BPF_PROG_TYPE_TRACING : +return prog->expected_attach_type !=BPF_TRACE_ITER ; +case BPF_PROG_TYPE_STRUCT_OPS : +case BPF_PROG_TYPE_LSM : +return false; +default : +return true; + } +} +#endif /* _LINUX_BPF_VERIFIER_H */
kernel/bpf/syscall.c +3 -2
@@ -5133,13 +5133,14 @@ int kern_sys_bpf(int cmd, union bpf_attr *attr, unsigned int size) run_ctx.bpf_cookie =0 ; run_ctx.saved_run_ctx =NULL ; -if (!__bpf_prog_enter_sleepable (prog, &run_ctx)) { +if (!__bpf_prog_enter_sleepable_recur (prog, &run_ctx)) {/* recursion detected */ bpf_prog_put (prog);return -EBUSY ; } attr->test.retval =bpf_prog_run (prog, (void *) (long ) attr->test.ctx_in); -__bpf_prog_exit_sleepable (prog,0 /* bpf_prog_run does runtime stats */ , &run_ctx); +__bpf_prog_exit_sleepable_recur (prog,0 /* bpf_prog_run does runtime stats */ , + &run_ctx);bpf_prog_put (prog);return 0 ;#endif
kernel/bpf/trampoline.c +67 -13
134 lines not on this page · raw message
Signature · 1 line
2.30.2
Martin KaFai Lau
reviewerPATCH 2/9 bpf: Append _recur naming to the bpf_task_storage helper proto
In reply to Martin KaFai LauFrom: Martin KaFai Lau <[email protected]>
This patch adds the "_recur" naming to the bpf_task_storage_{get,delete} proto. In a latter patch, they will only be used by the tracing programs that requires a deadlock detection because a tracing prog may use bpf_task_storage_{get,delete} recursively and cause a deadlock.
Another following patch will add a different helper proto for the non tracing programs because they do not need the deadlock prevention. This patch does this rename to prepare for this future proto additions.
--- include/linux/bpf.h | 4 ++-- kernel/bpf/bpf_task_storage.c | 12 ++++++------ kernel/trace/bpf_trace.c | 4 ++-- 3 files changed, 10 insertions(+), 10 deletions(-)
include/linux/bpf.h +2 -2
@@ -2519,8 +2519,8 @@ extern const struct bpf_func_proto bpf_this_cpu_ptr_proto;extern const struct bpf_func_proto bpf_ktime_get_coarse_ns_proto;extern const struct bpf_func_proto bpf_sock_from_file_proto;extern const struct bpf_func_proto bpf_get_socket_ptr_cookie_proto; -extern const struct bpf_func_proto bpf_task_storage_get_proto; -extern const struct bpf_func_proto bpf_task_storage_delete_proto; +extern const struct bpf_func_proto bpf_task_storage_get_recur_proto; +extern const struct bpf_func_proto bpf_task_storage_delete_recur_proto;extern const struct bpf_func_proto bpf_for_each_map_elem_proto;extern const struct bpf_func_proto bpf_btf_find_by_name_kind_proto;extern const struct bpf_func_proto bpf_sk_setsockopt_proto;
kernel/bpf/bpf_task_storage.c +6 -6
@@ -228,7 +228,7 @@ static int bpf_pid_task_storage_delete_elem(struct bpf_map *map, void *key) }/* *gfp_flags* is a hidden argument provided by the verifier */ -BPF_CALL_5(bpf_task_storage_get, struct bpf_map *, map, struct task_struct *, +BPF_CALL_5(bpf_task_storage_get_recur, struct bpf_map *, map, struct task_struct *, task, void *, value, u64, flags, gfp_t, gfp_flags) {struct bpf_local_storage_data *sdata;
@@ -260,7 +260,7 @@ BPF_CALL_5(bpf_task_storage_get, struct bpf_map *, map, struct task_struct *, (unsigned long )sdata->data; } -BPF_CALL_2(bpf_task_storage_delete, struct bpf_map *, map, struct task_struct *, +BPF_CALL_2(bpf_task_storage_delete_recur, struct bpf_map *, map, struct task_struct *, task) {int ret;
@@ -322,8 +322,8 @@ const struct bpf_map_ops task_storage_map_ops = { .map_owner_storage_ptr = task_storage_ptr, }; -const struct bpf_func_proto bpf_task_storage_get_proto = { - .func = bpf_task_storage_get, +const struct bpf_func_proto bpf_task_storage_get_recur_proto = { + .func = bpf_task_storage_get_recur, .gpl_only = false, .ret_type =RET_PTR_TO_MAP_VALUE_OR_NULL , .arg1_type =ARG_CONST_MAP_PTR ,
@@ -333,8 +333,8 @@ const struct bpf_func_proto bpf_task_storage_get_proto = { .arg4_type = ARG_ANYTHING, }; -const struct bpf_func_proto bpf_task_storage_delete_proto = { - .func = bpf_task_storage_delete, +const struct bpf_func_proto bpf_task_storage_delete_recur_proto = { + .func = bpf_task_storage_delete_recur, .gpl_only = false, .ret_type =RET_INTEGER , .arg1_type =ARG_CONST_MAP_PTR ,
kernel/trace/bpf_trace.c +2 -2
@@ -1488,9 +1488,9 @@ bpf_tracing_func_proto(enum bpf_func_id func_id, const struct bpf_prog *prog)case BPF_FUNC_this_cpu_ptr:return &bpf_this_cpu_ptr_proto;case BPF_FUNC_task_storage_get: -return &bpf_task_storage_get_proto; +return &bpf_task_storage_get_recur_proto;case BPF_FUNC_task_storage_delete: -return &bpf_task_storage_delete_proto; +return &bpf_task_storage_delete_recur_proto;case BPF_FUNC_for_each_map_elem:return &bpf_for_each_map_elem_proto;case BPF_FUNC_snprintf:
Signature · 1 line
2.30.2
Martin KaFai Lau
reviewerPATCH 3/9 bpf: Refactor the core bpf_task_storage_get logic into a new function
In reply to Martin KaFai LauFrom: Martin KaFai Lau <[email protected]>
This patch creates a new function __bpf_task_storage_get() and moves the core logic of the existing bpf_task_storage_get()
into this new function. This new function will be shared
by another new helper proto in the latter patch.
--- kernel/bpf/bpf_task_storage.c | 44 +++++++++++++++++++++-------------- 1 file changed, 26 insertions(+), 18 deletions(-)
kernel/bpf/bpf_task_storage.c +26 -18
@@ -227,37 +227,45 @@ static int bpf_pid_task_storage_delete_elem(struct bpf_map *map, void *key)return err; } -/* *gfp_flags* is a hidden argument provided by the verifier */ -BPF_CALL_5(bpf_task_storage_get_recur, struct bpf_map *, map, struct task_struct *, - task, void *, value, u64, flags, gfp_t, gfp_flags) +/* Called by bpf_task_storage_get*() helpers */ +static void *__bpf_task_storage_get (struct bpf_map *map, +struct task_struct *task,void *value, +u64 flags,gfp_t gfp_flags) {struct bpf_local_storage_data *sdata; -WARN_ON_ONCE (!bpf_rcu_lock_held ()); -if (flags & ~(BPF_LOCAL_STORAGE_GET_F_CREATE )) -return (unsigned long )NULL ; - -if (!task) -return (unsigned long )NULL ; - -if (!bpf_task_storage_trylock ()) -return (unsigned long )NULL ; - sdata =task_storage_lookup (task, map, true);if (sdata) - goto unlock; +return sdata->data;/* only allocate new storage, when the task is refcounted */ if (refcount_read (&task->usage) && - (flags &BPF_LOCAL_STORAGE_GET_F_CREATE )) + (flags &BPF_LOCAL_STORAGE_GET_F_CREATE )) { sdata =bpf_local_storage_update ( task, (struct bpf_local_storage_map *)map, value,BPF_NOEXIST , gfp_flags); +return IS_ERR (sdata) ?NULL : sdata->data; + } -unlock: +return NULL ; +} + +/* *gfp_flags* is a hidden argument provided by the verifier */ +BPF_CALL_5(bpf_task_storage_get_recur, struct bpf_map *, map, struct task_struct *, + task, void *, value, u64, flags, gfp_t, gfp_flags) +{ +void *data; + +WARN_ON_ONCE (!bpf_rcu_lock_held ()); +if (flags & ~BPF_LOCAL_STORAGE_GET_F_CREATE || !task) +return (unsigned long )NULL ; + +if (!bpf_task_storage_trylock ()) +return (unsigned long )NULL ; + data =__bpf_task_storage_get (map, task, value, flags, + gfp_flags);bpf_task_storage_unlock (); -return IS_ERR_OR_NULL (sdata) ? (unsigned long )NULL : - (unsigned long )sdata->data; +return (unsigned long )data; } BPF_CALL_2(bpf_task_storage_delete_recur, struct bpf_map *, map, struct task_struct *,
Signature · 1 line
2.30.2
Martin KaFai Lau
reviewerPATCH 4/9 bpf: Avoid taking spinlock in bpf_task_storage_get if potential deadlock is detected
In reply to Martin KaFai LauFrom: Martin KaFai Lau <[email protected]>
bpf_task_storage_get() does a lookup and optionally inserts new data if BPF_LOCAL_STORAGE_GET_F_CREATE is present.
During lookup, it will cache the lookup result and caching requires to acquire a spinlock. When potential deadlock is detected (by the bpf_task_storage_busy pcpu-counter added in
commit bc235cdb423a ("bpf: Prevent deadlock from recursive bpf_task_storage_[get|delete]")), the current behavior is returning NULL immediately to avoid deadlock. It is too pessimistic. This patch will go ahead to do a lookup (which is a lockless operation) but it will avoid caching it in order to avoid
acquiring the spinlock.
When lookup fails to find the data and BPF_LOCAL_STORAGE_GET_F_CREATE is set, an insertion is needed and this requires acquiring a spinlock. This patch will still return NULL when a potential deadlock is detected.
--- kernel/bpf/bpf_local_storage.c | 1 + kernel/bpf/bpf_task_storage.c | 15 ++++++++------- 2 files changed, 9 insertions(+), 7 deletions(-)
kernel/bpf/bpf_local_storage.c +1 -0
@@ -242,6 +242,7 @@ void bpf_selem_unlink(struct bpf_local_storage_elem *selem, bool use_trace_rcu)__bpf_selem_unlink_storage (selem, use_trace_rcu); } +/* If cacheit_lockit is false, this lookup function is lockless */ struct bpf_local_storage_data * bpf_local_storage_lookup(struct bpf_local_storage *local_storage, struct bpf_local_storage_map *smap,
kernel/bpf/bpf_task_storage.c +8 -7
@@ -230,17 +230,17 @@ static int bpf_pid_task_storage_delete_elem(struct bpf_map *map, void *key)/* Called by bpf_task_storage_get*() helpers */ static void *__bpf_task_storage_get (struct bpf_map *map,struct task_struct *task,void *value, -u64 flags,gfp_t gfp_flags) +u64 flags,gfp_t gfp_flags,bool nobusy) {struct bpf_local_storage_data *sdata; - sdata =task_storage_lookup (task, map, true); + sdata =task_storage_lookup (task, map, nobusy);if (sdata)return sdata->data;/* only allocate new storage, when the task is refcounted */ if (refcount_read (&task->usage) && - (flags &BPF_LOCAL_STORAGE_GET_F_CREATE )) { + (flags &BPF_LOCAL_STORAGE_GET_F_CREATE ) && nobusy) { sdata =bpf_local_storage_update ( task, (struct bpf_local_storage_map *)map, value,BPF_NOEXIST , gfp_flags);
@@ -254,17 +254,18 @@ static void *__bpf_task_storage_get(struct bpf_map *map, BPF_CALL_5(bpf_task_storage_get_recur, struct bpf_map *, map, struct task_struct *, task, void *, value, u64, flags, gfp_t, gfp_flags) { +bool nobusy;void *data;WARN_ON_ONCE (!bpf_rcu_lock_held ());if (flags & ~BPF_LOCAL_STORAGE_GET_F_CREATE || !task)return (unsigned long )NULL ; -if (!bpf_task_storage_trylock ()) -return (unsigned long )NULL ; + nobusy =bpf_task_storage_trylock (); data =__bpf_task_storage_get (map, task, value, flags, - gfp_flags); -bpf_task_storage_unlock (); + gfp_flags, nobusy); +if (nobusy) +bpf_task_storage_unlock ();return (unsigned long )data; }
Signature · 1 line
2.30.2
Martin KaFai Lau
reviewerPATCH 5/9 bpf: Add new bpf_task_storage_get proto with no deadlock detection
In reply to Martin KaFai LauFrom: Martin KaFai Lau <[email protected]>
The bpf_lsm and bpf_iter do not recur that will cause a deadlock. The situation is similar to the bpf_pid_task_storage_lookup_elem() which is called from the syscall map_lookup_elem. It does not need deadlock detection. Otherwise, it will cause unnecessary failure when calling the bpf_task_storage_get() helper.
This patch adds bpf_task_storage_get proto that does not do deadlock detection. It will be used by bpf_lsm and bpf_iter programs.
--- include/linux/bpf.h | 1 + kernel/bpf/bpf_task_storage.c | 28 ++++++++++++++++++++++++++++ kernel/trace/bpf_trace.c | 5 ++++- 3 files changed, 33 insertions(+), 1 deletion(-)
include/linux/bpf.h +1 -0
@@ -2520,6 +2520,7 @@ extern const struct bpf_func_proto bpf_ktime_get_coarse_ns_proto;extern const struct bpf_func_proto bpf_sock_from_file_proto;extern const struct bpf_func_proto bpf_get_socket_ptr_cookie_proto;extern const struct bpf_func_proto bpf_task_storage_get_recur_proto; +extern const struct bpf_func_proto bpf_task_storage_get_proto;extern const struct bpf_func_proto bpf_task_storage_delete_recur_proto;extern const struct bpf_func_proto bpf_for_each_map_elem_proto;extern const struct bpf_func_proto bpf_btf_find_by_name_kind_proto;
kernel/bpf/bpf_task_storage.c +28 -0
@@ -269,6 +269,23 @@ BPF_CALL_5(bpf_task_storage_get_recur, struct bpf_map *, map, struct task_structreturn (unsigned long )data; } +/* *gfp_flags* is a hidden argument provided by the verifier */ +BPF_CALL_5(bpf_task_storage_get, struct bpf_map *, map, struct task_struct *, + task, void *, value, u64, flags, gfp_t, gfp_flags) +{ +void *data; + +WARN_ON_ONCE (!bpf_rcu_lock_held ()); +if (flags & ~BPF_LOCAL_STORAGE_GET_F_CREATE || !task) +return (unsigned long )NULL ; + +bpf_task_storage_lock (); + data =__bpf_task_storage_get (map, task, value, flags, + gfp_flags, true); +bpf_task_storage_unlock (); +return (unsigned long )data; +} + BPF_CALL_2(bpf_task_storage_delete_recur, struct bpf_map *, map, struct task_struct *, task) {
@@ -342,6 +359,17 @@ const struct bpf_func_proto bpf_task_storage_get_recur_proto = { .arg4_type = ARG_ANYTHING, }; +const struct bpf_func_proto bpf_task_storage_get_proto = { + .func = bpf_task_storage_get, + .gpl_only = false, + .ret_type =RET_PTR_TO_MAP_VALUE_OR_NULL , + .arg1_type =ARG_CONST_MAP_PTR , + .arg2_type =ARG_PTR_TO_BTF_ID , + .arg2_btf_id = &btf_tracing_ids[BTF_TRACING_TYPE_TASK ], + .arg3_type =ARG_PTR_TO_MAP_VALUE_OR_NULL , + .arg4_type =ARG_ANYTHING , +}; +const struct bpf_func_proto bpf_task_storage_delete_recur_proto = { .func = bpf_task_storage_delete_recur, .gpl_only = false,
kernel/trace/bpf_trace.c +4 -1
@@ -6,6 +6,7 @@#include <linux/types.h> #include <linux/slab.h> #include <linux/bpf.h> +#include <linux/bpf_verifier.h> #include <linux/bpf_perf_event.h> #include <linux/btf.h> #include <linux/filter.h>
@@ -1488,7 +1489,9 @@ bpf_tracing_func_proto(enum bpf_func_id func_id, const struct bpf_prog *prog)case BPF_FUNC_this_cpu_ptr:return &bpf_this_cpu_ptr_proto;case BPF_FUNC_task_storage_get: -return &bpf_task_storage_get_recur_proto; +if (bpf_prog_check_recur (prog)) +return &bpf_task_storage_get_recur_proto; +return &bpf_task_storage_get_proto;case BPF_FUNC_task_storage_delete:return &bpf_task_storage_delete_recur_proto;case BPF_FUNC_for_each_map_elem:
Signature · 1 line
2.30.2
Martin KaFai Lau
reviewerPATCH 6/9 bpf: bpf_task_storage_delete_recur does lookup first before the deadlock check
In reply to Martin KaFai LauFrom: Martin KaFai Lau <[email protected]>
Similar to the earlier change in bpf_task_storage_get_recur. This patch changes bpf_task_storage_delete_recur such that it does the lookup first. It only returns -EBUSY if it needs to take the spinlock to do the deletion when potential deadlock is detected.
--- kernel/bpf/bpf_task_storage.c | 18 +++++++++++------- 1 file changed, 11 insertions(+), 7 deletions(-)
kernel/bpf/bpf_task_storage.c +11 -7
@@ -184,7 +184,8 @@ static int bpf_pid_task_storage_update_elem(struct bpf_map *map, void *key,return err; } -static int task_storage_delete (struct task_struct *task,struct bpf_map *map) +static int task_storage_delete (struct task_struct *task,struct bpf_map *map, +bool nobusy) {struct bpf_local_storage_data *sdata;
@@ -192,6 +193,9 @@ static int task_storage_delete(struct task_struct *task, struct bpf_map *map)if (!sdata)return -ENOENT ; +if (!nobusy) +return -EBUSY ; +bpf_selem_unlink (SELEM (sdata), true);return 0 ;
@@ -220,7 +224,7 @@ static int bpf_pid_task_storage_delete_elem(struct bpf_map *map, void *key) }bpf_task_storage_lock (); - err =task_storage_delete (task, map); + err =task_storage_delete (task, map, true);bpf_task_storage_unlock (); out:put_pid (pid);
@@ -289,21 +293,21 @@ BPF_CALL_5(bpf_task_storage_get, struct bpf_map *, map, struct task_struct *, BPF_CALL_2(bpf_task_storage_delete_recur, struct bpf_map *, map, struct task_struct *, task) { +bool nobusy;int ret;WARN_ON_ONCE (!bpf_rcu_lock_held ());if (!task)return -EINVAL ; -if (!bpf_task_storage_trylock ()) -return -EBUSY ; - + nobusy =bpf_task_storage_trylock ();/* This helper must only be called from places where the lifetime of the task * is guaranteed. Either by being refcounted or by being protected * by an RCU read-side critical section. */ - ret =task_storage_delete (task, map); -bpf_task_storage_unlock (); + ret =task_storage_delete (task, map, nobusy); +if (nobusy) +bpf_task_storage_unlock ();return ret; }
Signature · 1 line
2.30.2
Martin KaFai Lau
reviewerPATCH 7/9 bpf: Add new bpf_task_storage_delete proto with no deadlock detection
In reply to Martin KaFai LauFrom: Martin KaFai Lau <[email protected]>
The bpf_lsm and bpf_iter do not recur that will cause a deadlock. The situation is similar to the bpf_pid_task_storage_delete_elem() which is called from the syscall map_delete_elem. It does not need deadlock detection. Otherwise, it will cause unnecessary failure when calling the bpf_task_storage_delete() helper.
This patch adds bpf_task_storage_delete proto that does not do deadlock detection. It will be used by bpf_lsm and bpf_iter program.
--- include/linux/bpf.h | 1 + kernel/bpf/bpf_task_storage.c | 28 ++++++++++++++++++++++++++++ kernel/trace/bpf_trace.c | 4 +++- 3 files changed, 32 insertions(+), 1 deletion(-)
include/linux/bpf.h +1 -0
@@ -2522,6 +2522,7 @@ extern const struct bpf_func_proto bpf_get_socket_ptr_cookie_proto;extern const struct bpf_func_proto bpf_task_storage_get_recur_proto;extern const struct bpf_func_proto bpf_task_storage_get_proto;extern const struct bpf_func_proto bpf_task_storage_delete_recur_proto; +extern const struct bpf_func_proto bpf_task_storage_delete_proto;extern const struct bpf_func_proto bpf_for_each_map_elem_proto;extern const struct bpf_func_proto bpf_btf_find_by_name_kind_proto;extern const struct bpf_func_proto bpf_sk_setsockopt_proto;
kernel/bpf/bpf_task_storage.c +28 -0
@@ -311,6 +311,25 @@ BPF_CALL_2(bpf_task_storage_delete_recur, struct bpf_map *, map, struct task_strreturn ret; } +BPF_CALL_2(bpf_task_storage_delete, struct bpf_map *, map, struct task_struct *, + task) +{ +int ret; + +WARN_ON_ONCE (!bpf_rcu_lock_held ()); +if (!task) +return -EINVAL ; + +bpf_task_storage_lock (); +/* This helper must only be called from places where the lifetime of the task +* is guaranteed. Either by being refcounted or by being protected +* by an RCU read-side critical section. +*/ + ret =task_storage_delete (task, map, true); +bpf_task_storage_unlock (); +return ret; +} +static int notsupp_get_next_key (struct bpf_map *map,void *key,void *next_key) {return -ENOTSUPP ;
@@ -382,3 +401,12 @@ const struct bpf_func_proto bpf_task_storage_delete_recur_proto = { .arg2_type = ARG_PTR_TO_BTF_ID, .arg2_btf_id = &btf_tracing_ids[BTF_TRACING_TYPE_TASK], }; + +const struct bpf_func_proto bpf_task_storage_delete_proto = { + .func = bpf_task_storage_delete, + .gpl_only = false, + .ret_type =RET_INTEGER , + .arg1_type =ARG_CONST_MAP_PTR , + .arg2_type =ARG_PTR_TO_BTF_ID , + .arg2_btf_id = &btf_tracing_ids[BTF_TRACING_TYPE_TASK ], +};
kernel/trace/bpf_trace.c +3 -1
@@ -1493,7 +1493,9 @@ bpf_tracing_func_proto(enum bpf_func_id func_id, const struct bpf_prog *prog)return &bpf_task_storage_get_recur_proto;return &bpf_task_storage_get_proto;case BPF_FUNC_task_storage_delete: -return &bpf_task_storage_delete_recur_proto; +if (bpf_prog_check_recur (prog)) +return &bpf_task_storage_delete_recur_proto; +return &bpf_task_storage_delete_proto;case BPF_FUNC_for_each_map_elem:return &bpf_for_each_map_elem_proto;case BPF_FUNC_snprintf:
Signature · 1 line
2.30.2
Martin KaFai Lau
reviewerPATCH 8/9 selftests/bpf: Ensure no task storage failure for bpf_lsm.s prog due to deadlock detection
In reply to Martin KaFai LauFrom: Martin KaFai Lau <[email protected]>
This patch adds a test to check for deadlock failure
in bpf_task_storage_{get,delete} when called by a sleepable bpf_lsm prog. It also checks if the prog_info.recursion_misses is non zero.
The test starts with 32 threads and they are affinitized to one cpu. In my qemu setup, with CONFIG_PREEMPT=y, I can reproduce it within one second if it is run without the previous patches of this set.
Here is the test error message before adding the no deadlock detection version of the bpf_task_storage_{get,delete}:
test_nodeadlock:FAIL:bpf_task_storage_get busy unexpected bpf_task_storage_get busy: actual 2 != expected 0 test_nodeadlock:FAIL:bpf_task_storage_delete busy unexpected bpf_task_storage_delete busy: actual 2 != expected 0
--- .../bpf/prog_tests/task_local_storage.c | 98 +++++++++++++++++++ .../bpf/progs/task_storage_nodeadlock.c | 47 +++++++++ 2 files changed, 145 insertions(+) create mode 100644 tools/testing/selftests/bpf/progs/task_storage_nodeadlock.c
tools/testing/selftests/bpf/prog_tests/task_local_storage.c +98 -0
@@ -3,12 +3,15 @@#define _GNU_SOURCE/* See feature_test_macros(7) */ #include <unistd.h> +#include <sched.h> +#include <pthread.h> #include <sys/syscall.h> /* For SYS_xxx definitions */ #include <sys/types.h> #include <test_progs.h> #include "task_local_storage.skel.h" #include "task_local_storage_exit_creds.skel.h" #include "task_ls_recursion.skel.h" +#include "task_storage_nodeadlock.skel.h" static void test_sys_enter_exit (void ) {
@@ -93,6 +96,99 @@ static void test_recursion(void)task_ls_recursion__destroy (skel); } +static bool stop; + +static void waitall (const pthread_t *tids,int nr) +{ +int i; + + stop = true; +for (i =0 ; i < nr; i++) +pthread_join (tids[i],NULL ); +} + +static void *sock_create_loop (void *arg) +{ +struct task_storage_nodeadlock *skel = arg; +int fd; + +while (!stop) { + fd =socket (AF_INET ,SOCK_STREAM ,0 ); +close (fd); +if (skel->bss->nr_get_errs || skel->bss->nr_del_errs) + stop = true; + } + +return NULL ; +} + +static void test_nodeadlock (void ) +{ +struct task_storage_nodeadlock *skel; +struct bpf_prog_info info = {}; +__u32 info_len =sizeof (info); +const int nr_threads =32 ; +pthread_t tids[nr_threads]; +int i, prog_fd, err; +cpu_set_t old, new; + +/* Pin all threads to one cpu to increase the chance of preemption +* in a sleepable bpf prog. +*/ +CPU_ZERO (&new); +CPU_SET (0 , &new); + err =sched_getaffinity (getpid (),sizeof (old), &old); +if (!ASSERT_OK (err,"getaffinity" )) +return ; + err =sched_setaffinity (getpid (),sizeof (new), &new); +if (!ASSERT_OK (err,"setaffinity" )) +return ; + + skel =task_storage_nodeadlock__open_and_load (); +if (!ASSERT_OK_PTR (skel,"open_and_load" )) + goto done; + +/* Unnecessary recursion and deadlock detection are reproducible +* in the preemptible kernel. +*/ +if (!skel->kconfig->CONFIG_PREEMPT) { +test__skip (); + goto done; + } + + err =task_storage_nodeadlock__attach (skel); +ASSERT_OK (err,"attach prog" ); + +for (i =0 ; i < nr_threads; i++) { + err =pthread_create (&tids[i],NULL , sock_create_loop, skel); +if (err) { +/* Only assert once here to avoid excessive +* PASS printing during test failure. +*/ +ASSERT_OK (err,"pthread_create" ); +waitall (tids, i); + goto done; + } + } + +/* With 32 threads, 1s is enough to reproduce the issue */ +sleep (1 ); +waitall (tids, nr_threads); + + info_len =sizeof (info); + prog_fd =bpf_program__fd (skel->progs.socket_post_create); + err =bpf_obj_get_info_by_fd (prog_fd, &info, &info_len); +ASSERT_OK (err,"get prog info" ); +ASSERT_EQ (info.recursion_misses,0 ,"prog recursion" ); + +ASSERT_EQ (skel->bss->nr_get_errs,0 ,"bpf_task_storage_get busy" ); +ASSERT_EQ (skel->bss->nr_del_errs,0 ,"bpf_task_storage_delete busy" ); + +done: +task_storage_nodeadlock__destroy (skel); +sched_setaffinity (getpid (),sizeof (old), &old); +} +void test_task_local_storage (void ) {if (test__start_subtest ("sys_enter_exit" ))
@@ -101,4 +197,6 @@ void test_task_local_storage(void)test_exit_creds ();if (test__start_subtest ("recursion" ))test_recursion (); +if (test__start_subtest ("nodeadlock" )) +test_nodeadlock (); }
tools/testing/selftests/bpf/progs/task_storage_nodeadlock.c new file +47 -0
47 lines not on this page · raw message
Signature · 1 line
2.30.2
Martin KaFai Lau
reviewerPATCH 9/9 selftests/bpf: Tracing prog can still do lookup under busy lock
In reply to Martin KaFai LauFrom: Martin KaFai Lau <[email protected]>
This patch modifies the task_ls_recursion test to check that the first bpf_task_storage_get(&map_a, ...) in BPF_PROG(on_update) can still do the lockless lookup even it cannot acquire the percpu busy lock. If the lookup succeeds, it will increment the value by 1 and the value in the task storage map_a will become 200+1=201. After that, BPF_PROG(on_update) tries to delete from map_a and should get -EBUSY because it cannot acquire the percpu busy lock after finding the data.
--- .../bpf/prog_tests/task_local_storage.c | 48 ++++++++++++++++++- .../selftests/bpf/progs/task_ls_recursion.c | 43 +++++++++++++++-- 2 files changed, 86 insertions(+), 5 deletions(-)
tools/testing/selftests/bpf/prog_tests/task_local_storage.c +46 -2
@@ -8,6 +8,7 @@#include <sys/syscall.h> /* For SYS_xxx definitions */ #include <sys/types.h> #include <test_progs.h> +#include "task_local_storage_helpers.h" #include "task_local_storage.skel.h" #include "task_local_storage_exit_creds.skel.h" #include "task_ls_recursion.skel.h"
@@ -78,21 +79,64 @@ static void test_exit_creds(void)static void test_recursion (void ) { +int err, map_fd, prog_fd, task_fd;struct task_ls_recursion *skel; -int err; +struct bpf_prog_info info; +__u32 info_len =sizeof (info); +long value; + + task_fd =sys_pidfd_open (getpid (),0 ); +if (!ASSERT_NEQ (task_fd,-1 ,"sys_pidfd_open" )) +return ; skel =task_ls_recursion__open_and_load ();if (!ASSERT_OK_PTR (skel,"skel_open_and_load" )) -return ; + goto out; err =task_ls_recursion__attach (skel);if (!ASSERT_OK (err,"skel_attach" )) goto out;/* trigger sys_enter, make sure it does not cause deadlock */ + skel->bss->test_pid =getpid ();syscall (SYS_gettid); + skel->bss->test_pid =0 ; +task_ls_recursion__detach (skel); + +/* Refer to the comment in BPF_PROG(on_update) for +* the explanation on the value 201 and 100. +*/ + map_fd =bpf_map__fd (skel->maps.map_a); + err =bpf_map_lookup_elem (map_fd, &task_fd, &value); +ASSERT_OK (err,"lookup map_a" ); +ASSERT_EQ (value,201 ,"map_a value" ); +ASSERT_EQ (skel->bss->nr_del_errs,1 ,"bpf_task_storage_delete busy" ); + + map_fd =bpf_map__fd (skel->maps.map_b); + err =bpf_map_lookup_elem (map_fd, &task_fd, &value); +ASSERT_OK (err,"lookup map_b" ); +ASSERT_EQ (value,100 ,"map_b value" ); + + prog_fd =bpf_program__fd (skel->progs.on_lookup); +memset (&info,0 ,sizeof (info)); + err =bpf_obj_get_info_by_fd (prog_fd, &info, &info_len); +ASSERT_OK (err,"get prog info" ); +ASSERT_GT (info.recursion_misses,0 ,"on_lookup prog recursion" ); + + prog_fd =bpf_program__fd (skel->progs.on_update); +memset (&info,0 ,sizeof (info)); + err =bpf_obj_get_info_by_fd (prog_fd, &info, &info_len); +ASSERT_OK (err,"get prog info" ); +ASSERT_EQ (info.recursion_misses,0 ,"on_update prog recursion" ); + + prog_fd =bpf_program__fd (skel->progs.on_enter); +memset (&info,0 ,sizeof (info)); + err =bpf_obj_get_info_by_fd (prog_fd, &info, &info_len); +ASSERT_OK (err,"get prog info" ); +ASSERT_EQ (info.recursion_misses,0 ,"on_enter prog recursion" ); out: +close (task_fd);task_ls_recursion__destroy (skel); }
tools/testing/selftests/bpf/progs/task_ls_recursion.c +40 -3
78 lines not on this page · raw message
Signature · 1 line
2.30.2
This series was applied to bpf/bpf-next.git (master) by Alexei Starovoitov <[email protected]>:
Hello:
This series was applied to bpf/bpf-next.git (master) by Alexei Starovoitov <[email protected]>:
Quoted 8 lines · On Tue, 25 Oct 2022 11:45:15 -0700 you wrote:
From: Martin KaFai Lau <[email protected]>
The commit
bc235cdb423a("bpf: Prevent deadlock from recursive bpf_task_storage_[get|delete]") added deadlock detection to avoid a tracing program from recurring
on the bpf_task_storage_{get,delete}() helpers. These helpers acquire
a spin lock and it will lead to deadlock.[...]
Here is the summary with links:
- [bpf-next,1/9] bpf: Remove prog->active check for bpf_lsm and bpf_iter
https://git.kernel.org/bpf/bpf-next/c/271de525e1d7 - [bpf-next,2/9] bpf: Append _recur naming to the bpf_task_storage helper proto https://git.kernel.org/bpf/bpf-next/c/0593dd34e534 - [bpf-next,3/9] bpf: Refactor the core bpf_task_storage_get logic into a new function https://git.kernel.org/bpf/bpf-next/c/6d65500c34d8 - [bpf-next,4/9] bpf: Avoid taking spinlock in bpf_task_storage_get if potential deadlock is detected https://git.kernel.org/bpf/bpf-next/c/e8b02296a6b8 - [bpf-next,5/9] bpf: Add new bpf_task_storage_get proto with no deadlock detection https://git.kernel.org/bpf/bpf-next/c/4279adb094a1 - [bpf-next,6/9] bpf: bpf_task_storage_delete_recur does lookup first before the deadlock check https://git.kernel.org/bpf/bpf-next/c/fda64ae0bb3e - [bpf-next,7/9] bpf: Add new bpf_task_storage_delete proto with no deadlock detection https://git.kernel.org/bpf/bpf-next/c/8a7dac37f27a - [bpf-next,8/9] selftests/bpf: Ensure no task storage failure for bpf_lsm.s prog due to deadlock detection https://git.kernel.org/bpf/bpf-next/c/0334b4d8822a - [bpf-next,9/9] selftests/bpf: Tracing prog can still do lookup under busy lock https://git.kernel.org/bpf/bpf-next/c/387b532138ee
You are awesome, thank you!
Signature · 2 lines
Deet-doot-dot, I am a bot. https://korg.docs.kernel.org/patchwork/pwbot.html