bpf: Support private stack for bpf progs
Yonghong Song
reviewerv8 cover bpf: Support private stack for bpf progs
The main motivation for private stack comes from nested scheduler in sched-ext from Tejun. The basic idea is that
- each cgroup will its own associated bpf program,
- bpf program with parent cgroup will call bpf programs in immediate child cgroups.
Let us say we have the following cgroup hierarchy:
root_cg (prog0):
cg1 (prog1):
cg11 (prog11):
cg111 (prog111)
cg112 (prog112)
cg12 (prog12):
cg121 (prog121)
cg122 (prog122)
cg2 (prog2):
cg21 (prog21)
cg22 (prog22)
cg23 (prog23)In the above example, prog0 will call a kfunc which will call prog1 and prog2 to get sched info for cg1 and cg2 and then the information is summarized and sent back to prog0. Similarly, prog11 and prog12 will be invoked in the kfunc and the result will be summarized and sent back to prog1, etc. The following illustrates a possible call sequence:
... -> bpf prog A -> kfunc -> ops.<callback_fn> (bpf prog B) ...
Currently, for each thread, the x86 kernel allocate 16KB stack. Each bpf program (including its subprograms) has maximum 512B stack size to avoid potential stack overflow. Nested bpf programs further increase the risk of stack overflow. To avoid potential stack overflow caused by bpf programs, this patch set supported private stack and bpf program stack space is allocated during verification time. Using private stack for bpf progs can reduce or avoid potential kernel stack overflow.
Currently private stack is applied to tracing programs like kprobe/uprobe, perf_event, tracepoint, raw tracepoint and struct_ops progs. For all these progs, the kernel will do recursion check (no nesting for per prog per cpu) to ensure that private stack won't be overwritten.
Tracing progs enable private stack if any subprog stack size is more than a threshold (i.e. 64B). Struct-ops progs enable private stack based on particular struct op implementation which can enable private stack before verification at per-insn level.
Only x86_64 arch supports private stack now. It can be extended to other archs later. Please see each individual patch for details.
Change logs:
v7 -> v8:
- v7 link: https://lore.kernel.org/bpf/[email protected]/
- Add recursion_skipped() callback func to bpf_prog->aux structure such that if a recursion miss happened and bpf_prog->aux->recursion_skipped is not NULL, the callback fn will be called so the subsystem can do proper action based on their respective design.
v6 -> v7:
- v6 link: https://lore.kernel.org/bpf/[email protected]/
- Going back to do private stack allocation per prog instead per subtree. This can simplify implementation and avoid verifier complexity.
- Handle potential nested subprog run if async callback exists.
- Use struct_ops->check_member() callback to set whether a particular struct-ops prog wants private stack or not.
v5 -> v6:
- v5 link: https://lore.kernel.org/bpf/[email protected]/
- Instead of using (or not using) private stack at struct_ops level,
each prog in struct_ops can decide whether to use private stack or not.
v4 -> v5:
- v4 link: https://lore.kernel.org/bpf/[email protected]/
- Remove bpf_prog_call() related implementation.
- Allow (opt-in) private stack for sched-ext progs.
v3 -> v4:
- v3 link: https://lore.kernel.org/bpf/[email protected]/
There is a long discussion in the above v3 link trying to allow private stack to be used by kernel functions in order to simplify implementation. But unfortunately we didn't find a workable solution yet, so we return to the approach where private stack is only used by bpf programs.
- Add bpf_prog_call() kfunc.
v2 -> v3:
- Instead of per-subprog private stack allocation, allocate private stacks at main prog or callback entry prog. Subprogs not main or callback progs will increment the inherited stack pointer to be their
frame pointer.
- Private stack allows each prog max stack size to be 512 bytes, intead of the whole prog hierarchy to be 512 bytes.
- Add some tests.
Yonghong Song (9):
bpf: Check stack depth limit after visiting all subprogs
bpf: Allow private stack to have each subprog having stack size of 512
bytes
bpf: Check potential private stack recursion for progs with async
callback
bpf: Allocate private stack for eligible main prog or subprogs bpf, x86: Avoid repeated usage of bpf_prog->aux->stack_depth bpf, x86: Support private stack in jit
selftests/bpf: Add tracing prog private stack tests
bpf: Support private stack for struct_ops progs selftests/bpf: Add struct_ops prog private stack tests
arch/x86/net/bpf_jit_comp.c | 73 ++++- include/linux/bpf.h | 3 + include/linux/bpf_verifier.h | 2 + include/linux/filter.h | 1 + kernel/bpf/core.c | 15 + kernel/bpf/trampoline.c | 4 + kernel/bpf/verifier.c | 163 ++++++++++- .../selftests/bpf/bpf_testmod/bpf_testmod.c | 104 +++++++ .../selftests/bpf/bpf_testmod/bpf_testmod.h | 5 + .../bpf/prog_tests/struct_ops_private_stack.c | 106 +++++++ .../selftests/bpf/prog_tests/verifier.c | 2 + .../bpf/progs/struct_ops_private_stack.c | 62 ++++ .../bpf/progs/struct_ops_private_stack_fail.c | 62 ++++ .../progs/struct_ops_private_stack_recur.c | 50 ++++ .../bpf/progs/verifier_private_stack.c | 272 ++++++++++++++++++ 15 files changed, 908 insertions(+), 16 deletions(-) create mode 100644 tools/testing/selftests/bpf/prog_tests/struct_ops_private_stack.c create mode 100644 tools/testing/selftests/bpf/progs/struct_ops_private_stack.c create mode 100644 tools/testing/selftests/bpf/progs/struct_ops_private_stack_fail.c create mode 100644 tools/testing/selftests/bpf/progs/struct_ops_private_stack_recur.c create mode 100644 tools/testing/selftests/bpf/progs/verifier_private_stack.c
Signature · 1 line
2.43.5
Yonghong Song
reviewerPATCH v8 1/9 bpf: Check stack depth limit after visiting all subprogs
Check stack depth limit after all subprogs are visited. Note that if private stack is enabled, the only stack size restriction is for a single subprog with size less than or equal to MAX_BPF_STACK.
In subsequent patches, in function check_max_stack_depth(), there could be a flip from enabling private stack to disabling private stack due to potential nested bpf subprog run. Moving stack depth limit checking after visiting all subprogs ensures the checking not missed in such flipping cases.
The useless 'continue' statement in the loop in func check_max_stack_depth() is also removed.
--- kernel/bpf/verifier.c | 20 ++++++++++++-------- 1 file changed, 12 insertions(+), 8 deletions(-)
kernel/bpf/verifier.c +12 -8
@@ -6032,7 +6032,8 @@ static int round_up_stack_depth(struct bpf_verifier_env *env, int stack_depth)* Since recursion is prevented by check_cfg() this algorithm * only needs a local stack of MAX_CALL_FRAMES to remember callsites */ -static int check_max_stack_depth_subprog (struct bpf_verifier_env *env,int idx) +static int check_max_stack_depth_subprog (struct bpf_verifier_env *env,int idx, +int *subtree_depth,int *depth_frame) {struct bpf_subprog_info *subprog = env->subprog_info;struct bpf_insn *insn = env->prog->insnsi;
@@ -6070,10 +6071,9 @@ static int check_max_stack_depth_subprog(struct bpf_verifier_env *env, int idx)return -EACCES ; } depth +=round_up_stack_depth (env, subprog[idx].stack_depth); -if (depth >MAX_BPF_STACK ) { -verbose (env,"combined stack size of %d calls is %d. Too large\n" , - frame +1 , depth); -return -EACCES ; +if (depth >MAX_BPF_STACK && !*subtree_depth) { + *subtree_depth = depth; + *depth_frame = frame +1 ; } continue_func: subprog_end = subprog[idx +1 ].start;
@@ -6173,15 +6173,19 @@ static int check_max_stack_depth_subprog(struct bpf_verifier_env *env, int idx)static int check_max_stack_depth (struct bpf_verifier_env *env) {struct bpf_subprog_info *si = env->subprog_info; -int ret; +int ret, subtree_depth =0 , depth_frame;for (int i =0 ; i < env->subprog_cnt; i++) {if (!i || si[i].is_async_cb) { - ret =check_max_stack_depth_subprog (env, i); + ret =check_max_stack_depth_subprog (env, i, &subtree_depth, &depth_frame);if (ret <0 )return ret; } -continue ; + } +if (subtree_depth >MAX_BPF_STACK ) { +verbose (env,"combined stack size of %d calls is %d. Too large\n" , + depth_frame, subtree_depth); +return -EACCES ; }return 0 ; }
Signature · 1 line
2.43.5
Yonghong Song
reviewerPATCH v8 2/9 bpf: Allow private stack to have each subprog having stack size of 512 bytes
In reply to Yonghong SongWith private stack support, each subprog can have stack with up to 512 bytes. The limit of 512 bytes per subprog is kept to avoid increasing verifier complexity since greater than 512 bytes will cause big verifier change and increase memory consumption and verification time.
If private stack is supported and certain stack size threshold is reached, that subprog will have its own private stack allocated.
In this patch, some tracing programs are allowed to use private stack since tracing prog may be triggered in the middle of some other prog runs. The supported tracing programs already have recursion check such that if the same prog is running on the same cpu again, the nested prog run will be skipped. This ensures bpf prog private stack is not over-written.
Note that if any tail_call is called in the prog (including all subprogs), then private stack is not used.
Function bpf_enable_priv_stack() return values include NO_PRIV_STACK, PRIV_STACK_ADAPTIVE, PRIV_STACK_ALWAYS and negative errors. The NO_PRIV_STACK represents priv stack not enable, PRIV_STACK_ADAPTIVE for priv stack enabled with some conditions (e.g. stack size threshold), and PRIV_STACK_ALWAYS for priv stack always enabled. The negative error represents a verification failure. The PRIV_STACK_ALWAYS and negative error will be used by later struct_ops progs.
--- include/linux/bpf.h | 1 + include/linux/bpf_verifier.h | 1 + include/linux/filter.h | 1 + kernel/bpf/core.c | 5 +++ kernel/bpf/verifier.c | 75 ++++++++++++++++++++++++++++++++---- 5 files changed, 75 insertions(+), 8 deletions(-)
include/linux/bpf.h +1 -0
@@ -1523,6 +1523,7 @@ struct bpf_prog_aux {bool exception_cb;bool exception_boundary;bool is_extended;/* true if extended by freplace program */ +bool use_priv_stack;u64 prog_array_member_cnt;/* counts how many times as member of prog_array */ struct mutex ext_mutex;/* mutex for is_extended and prog_array_member_cnt */ struct bpf_arena *arena;
include/linux/bpf_verifier.h +1 -0
@@ -668,6 +668,7 @@ struct bpf_subprog_info { bool args_cached: 1;/* true if bpf_fastcall stack region is used by functions that can't be inlined */ bool keep_fastcall_stack: 1; + bool use_priv_stack: 1;u8 arg_cnt;struct bpf_subprog_arg_info args[MAX_BPF_FUNC_REG_ARGS ];
include/linux/filter.h +1 -0
@@ -1119,6 +1119,7 @@ bool bpf_jit_supports_exceptions(void);bool bpf_jit_supports_ptr_xchg (void );bool bpf_jit_supports_arena (void );bool bpf_jit_supports_insn (struct bpf_insn *insn,bool in_arena); +bool bpf_jit_supports_private_stack (void );u64 bpf_arch_uaddress_limit (void );void arch_bpf_stack_walk (bool (*consume_fn)(void *cookie,u64 ip,u64 sp,u64 bp),void *cookie);bool bpf_helper_changes_pkt_data (void *func);
kernel/bpf/core.c +5 -0
@@ -3045,6 +3045,11 @@ bool __weak bpf_jit_supports_exceptions(void)return false; } +bool __weak bpf_jit_supports_private_stack (void ) +{ +return false; +} +void __weak arch_bpf_stack_walk (bool (*consume_fn)(void *cookie,u64 ip,u64 sp,u64 bp),void *cookie) { }
kernel/bpf/verifier.c +67 -8
120 lines not on this page · raw message
Signature · 1 line
2.43.5
Re: [PATCH bpf-next v8 2/9] bpf: Allow private stack to have each subprog having stack size of 512 bytes
Quoted 102 lines · Yonghong Song
With private stack support, each subprog can have stack with up to 512 bytes. The limit of 512 bytes per subprog is kept to avoid increasing verifier complexity since greater than 512 bytes will cause big verifier change and increase memory consumption and verification time.
If private stack is supported and certain stack size threshold is reached, that subprog will have its own private stack allocated.
In this patch, some tracing programs are allowed to use private stack since tracing prog may be triggered in the middle of some other prog runs. The supported tracing programs already have recursion check such that if the same prog is running on the same cpu again, the nested prog run will be skipped. This ensures bpf prog private stack is not over-written.
Note that if any
tail_callis called in the prog (including all subprogs), then private stack is not used.Function
bpf_enable_priv_stack()return values includeNO_PRIV_STACK,PRIV_STACK_ADAPTIVE,PRIV_STACK_ALWAYSand negative errors. TheNO_PRIV_STACKrepresents priv stack not enable,PRIV_STACK_ADAPTIVEfor priv stack enabled with some conditions (e.g. stack size threshold), andPRIV_STACK_ALWAYSfor priv stack always enabled. The negative error represents a verification failure. ThePRIV_STACK_ALWAYSand negative error will be used by laterstruct_opsprogs.Signed-off-by Yonghong Song <[email protected]>--- include/linux/bpf.h | 1 + include/linux/bpf_verifier.h | 1 + include/linux/filter.h | 1 + kernel/bpf/core.c | 5 +++ kernel/bpf/verifier.c | 75 ++++++++++++++++++++++++++++++++---- 5 files changed, 75 insertions(+), 8 deletions(-)include/linux/bpf.h +1
-0@@ -1523,6 +1523,7 @@ struct bpf_prog_aux {bool exception_cb;bool exception_boundary;bool is_extended;/* true if extended by freplace program */ +bool use_priv_stack;u64 prog_array_member_cnt;/* counts how many times as member of prog_array */ struct mutex ext_mutex;/* mutex for is_extended and prog_array_member_cnt */ struct bpf_arena *arena;include/linux/bpf_verifier.h +1
-0@@ -668,6 +668,7 @@ struct bpf_subprog_info { bool args_cached: 1;/* true if bpf_fastcall stack region is used by functions that can't be inlined */ bool keep_fastcall_stack: 1; + bool use_priv_stack: 1;u8 arg_cnt;struct bpf_subprog_arg_info args[MAX_BPF_FUNC_REG_ARGS ];include/linux/filter.h +1
-0@@ -1119,6 +1119,7 @@ bool bpf_jit_supports_exceptions(void);bool bpf_jit_supports_ptr_xchg (void );bool bpf_jit_supports_arena (void );bool bpf_jit_supports_insn (struct bpf_insn *insn,bool in_arena); +bool bpf_jit_supports_private_stack (void );u64 bpf_arch_uaddress_limit (void );void arch_bpf_stack_walk (bool (*consume_fn)(void *cookie,u64 ip,u64 sp,u64 bp),void *cookie);bool bpf_helper_changes_pkt_data (void *func);kernel/bpf/core.c +5
-0@@ -3045,6 +3045,11 @@ bool __weak bpf_jit_supports_exceptions(void)return false; } +bool __weak bpf_jit_supports_private_stack (void ) +{ +return false; +} +void __weak arch_bpf_stack_walk (bool (*consume_fn)(void *cookie,u64 ip,u64 sp,u64 bp),void *cookie) { }kernel/bpf/verifier.c +2
-0@@ -194,6 +194,8 @@ struct bpf_verifier_stack_elem {#define BPF_GLOBAL_PERCPU_MA_MAX_SIZE 512 +#define BPF_PRIV_STACK_MIN_SIZE 64 +static int acquire_reference_state (struct bpf_verifier_env *env,int insn_idx);static int release_reference (struct bpf_verifier_env *env,int ref_obj_id);static void invalidate_non_owning_refs (struct bpf_verifier_env *env);
kernel/bpf/verifier.c static int check_ptr_alignment(struct bpf_verifier_env *env, · line 6022
Quoted 6 lines
kernel/bpf/verifier.c +3
-0@@ -6015,6 +6017,40 @@ static int check_ptr_alignment(struct bpf_verifier_env *env, strict); } +#define NO_PRIV_STACK 0 +#define PRIV_STACK_ADAPTIVE 1 +#define PRIV_STACK_ALWAYS 2
Please use enum.
Quoted 11 lines
kernel/bpf/verifier.c +11
-0+ +static int bpf_enable_priv_stack (struct bpf_verifier_env *env) +{ +struct bpf_subprog_info *si; + +if (!bpf_jit_supports_private_stack ()) +return NO_PRIV_STACK ; + +switch (env->prog->type) { +case BPF_PROG_TYPE_KPROBE : +case BPF_PROG_TYPE_TRACEPOINT :
kernel/bpf/verifier.c static int check_ptr_alignment(struct bpf_verifier_env *env, · line 6043
Quoted 10 lines
kernel/bpf/verifier.c +10
-0+case BPF_PROG_TYPE_PERF_EVENT : +case BPF_PROG_TYPE_RAW_TRACEPOINT : +break ; +case BPF_PROG_TYPE_TRACING : +if (env->prog->expected_attach_type !=BPF_TRACE_ITER ) +break ; + fallthrough; +default : +return NO_PRIV_STACK ; + }
Probably worth adding:
if (!bpf_prog_check_recur(env->prog))
return NO_PRIV_STACK;
and remove case BPF_PROG_TYPE_TRACING entry
with comment that bpf_prog_check_recur() checks all prog types that use bpf trampoline while kprobe/tp/raw_tp don't use trampoline hence checked explicitly.
Quoted 54 lines
kernel/bpf/verifier.c +26
-3+ + si = env->subprog_info; +for (int i =0 ; i < env->subprog_cnt; i++) { +if (si[i].has_tail_call) +return NO_PRIV_STACK ; + } + +return PRIV_STACK_ADAPTIVE ; +} +static int round_up_stack_depth (struct bpf_verifier_env *env,int stack_depth) {if (env->prog->jit_requested)@@ -6033,11 +6069,12 @@ static int round_up_stack_depth(struct bpf_verifier_env *env, int stack_depth)* only needs a local stack of MAX_CALL_FRAMES to remember callsites */ static int check_max_stack_depth_subprog (struct bpf_verifier_env *env,int idx, -int *subtree_depth,int *depth_frame) +int *subtree_depth,int *depth_frame, +int priv_stack_supported) {struct bpf_subprog_info *subprog = env->subprog_info;struct bpf_insn *insn = env->prog->insnsi; -int depth =0 , frame =0 , i, subprog_end; +int depth =0 , frame =0 , i, subprog_end, subprog_depth;bool tail_call_reachable = false;int ret_insn[MAX_CALL_FRAMES ];int ret_prog[MAX_CALL_FRAMES ];@@ -6070,11 +6107,23 @@ static int check_max_stack_depth_subprog(struct bpf_verifier_env *env, int idx, depth);return -EACCES ; } - depth +=round_up_stack_depth (env, subprog[idx].stack_depth); + subprog_depth =round_up_stack_depth (env, subprog[idx].stack_depth); + depth += subprog_depth;if (depth >MAX_BPF_STACK && !*subtree_depth) { *subtree_depth = depth; *depth_frame = frame +1 ; } +if (priv_stack_supported !=NO_PRIV_STACK ) { +if (!subprog[idx].use_priv_stack) { +if (subprog_depth >MAX_BPF_STACK ) { +verbose (env,"stack size of subprog %d is %d. Too large\n" , + idx, subprog_depth); +return -EACCES ; + } +if (subprog_depth >=BPF_PRIV_STACK_MIN_SIZE ) + subprog[idx].use_priv_stack = true; + } + } continue_func: subprog_end = subprog[idx +1 ].start;for (; i < subprog_end; i++) {
kernel/bpf/verifier.c static int check_max_stack_depth(struct bpf_verifier_env *env) · line 6230
Quoted 8 lines
kernel/bpf/verifier.c +5
-0@@ -6174,19 +6223,29 @@ static int check_max_stack_depth(struct bpf_verifier_env *env) {struct bpf_subprog_info *si = env->subprog_info;int ret, subtree_depth =0 , depth_frame; +int priv_stack_supported; + + priv_stack_supported =bpf_enable_priv_stack (env); +if (priv_stack_supported <0 ) +return priv_stack_supported;
if it was enum, the compiler would have warned that the above is meaningless.
Quoted 6 lines
kernel/bpf/verifier.c +2
-1for (int i =0 ; i < env->subprog_cnt; i++) {if (!i || si[i].is_async_cb) { - ret =check_max_stack_depth_subprog (env, i, &subtree_depth, &depth_frame); + ret =check_max_stack_depth_subprog (env, i, &subtree_depth, &depth_frame, + priv_stack_supported);
kernel/bpf/verifier.c static int check_max_stack_depth(struct bpf_verifier_env *env) · line 6241
Quoted 10 lines
kernel/bpf/verifier.c +2
-4if (ret <0 )return ret; } } -if (subtree_depth >MAX_BPF_STACK ) { -verbose (env,"combined stack size of %d calls is %d. Too large\n" , - depth_frame, subtree_depth); -return -EACCES ; +if (priv_stack_supported ==NO_PRIV_STACK ) { +if (subtree_depth >MAX_BPF_STACK ) {
no need for extra indent. Use:
if (priv_stack_supported == NO_PRIV_STACK &&
subtree_depth > MAX_BPF_STACK) {kernel/bpf/verifier.c static int check_max_stack_depth(struct bpf_verifier_env *env) · line 6250
Quoted 9 lines
kernel/bpf/verifier.c +6
-0+verbose (env,"combined stack size of %d calls is %d. Too large\n" , + depth_frame, subtree_depth); +return -EACCES ; + } } +if (si[0 ].use_priv_stack) + env->prog->aux->use_priv_stack = true;return 0 ; }
pw-bot: cr
Yonghong Song
reviewerRe: [PATCH bpf-next v8 2/9] bpf: Allow private stack to have each subprog having stack size of 512 bytes
Quoted 105 lines · Alexei Starovoitov
Quoted 104 lines · Yonghong Song
With private stack support, each subprog can have stack with up to 512 bytes. The limit of 512 bytes per subprog is kept to avoid increasing verifier complexity since greater than 512 bytes will cause big verifier change and increase memory consumption and verification time.
If private stack is supported and certain stack size threshold is reached, that subprog will have its own private stack allocated.
In this patch, some tracing programs are allowed to use private stack since tracing prog may be triggered in the middle of some other prog runs. The supported tracing programs already have recursion check such that if the same prog is running on the same cpu again, the nested prog run will be skipped. This ensures bpf prog private stack is not over-written.
Note that if any
tail_callis called in the prog (including all subprogs), then private stack is not used.Function
bpf_enable_priv_stack()return values includeNO_PRIV_STACK,PRIV_STACK_ADAPTIVE,PRIV_STACK_ALWAYSand negative errors. TheNO_PRIV_STACKrepresents priv stack not enable,PRIV_STACK_ADAPTIVEfor priv stack enabled with some conditions (e.g. stack size threshold), andPRIV_STACK_ALWAYSfor priv stack always enabled. The negative error represents a verification failure. ThePRIV_STACK_ALWAYSand negative error will be used by laterstruct_opsprogs.Signed-off-by Yonghong Song <[email protected]>--- include/linux/bpf.h | 1 + include/linux/bpf_verifier.h | 1 + include/linux/filter.h | 1 + kernel/bpf/core.c | 5 +++ kernel/bpf/verifier.c | 75 ++++++++++++++++++++++++++++++++---- 5 files changed, 75 insertions(+), 8 deletions(-)include/linux/bpf.h +1
-0@@ -1523,6 +1523,7 @@ struct bpf_prog_aux {bool exception_cb;bool exception_boundary;bool is_extended;/* true if extended by freplace program */ +bool use_priv_stack;u64 prog_array_member_cnt;/* counts how many times as member of prog_array */ struct mutex ext_mutex;/* mutex for is_extended and prog_array_member_cnt */ struct bpf_arena *arena;include/linux/bpf_verifier.h +1
-0@@ -668,6 +668,7 @@ struct bpf_subprog_info { bool args_cached: 1;/* true if bpf_fastcall stack region is used by functions that can't be inlined */ bool keep_fastcall_stack: 1; + bool use_priv_stack: 1;u8 arg_cnt;struct bpf_subprog_arg_info args[MAX_BPF_FUNC_REG_ARGS ];include/linux/filter.h +1
-0@@ -1119,6 +1119,7 @@ bool bpf_jit_supports_exceptions(void);bool bpf_jit_supports_ptr_xchg (void );bool bpf_jit_supports_arena (void );bool bpf_jit_supports_insn (struct bpf_insn *insn,bool in_arena); +bool bpf_jit_supports_private_stack (void );u64 bpf_arch_uaddress_limit (void );void arch_bpf_stack_walk (bool (*consume_fn)(void *cookie,u64 ip,u64 sp,u64 bp),void *cookie);bool bpf_helper_changes_pkt_data (void *func);kernel/bpf/core.c +5
-0@@ -3045,6 +3045,11 @@ bool __weak bpf_jit_supports_exceptions(void)return false; } +bool __weak bpf_jit_supports_private_stack (void ) +{ +return false; +} +void __weak arch_bpf_stack_walk (bool (*consume_fn)(void *cookie,u64 ip,u64 sp,u64 bp),void *cookie) { }kernel/bpf/verifier.c +2
-0@@ -194,6 +194,8 @@ struct bpf_verifier_stack_elem {#define BPF_GLOBAL_PERCPU_MA_MAX_SIZE 512 +#define BPF_PRIV_STACK_MIN_SIZE 64 +static int acquire_reference_state (struct bpf_verifier_env *env,int insn_idx);static int release_reference (struct bpf_verifier_env *env,int ref_obj_id);static void invalidate_non_owning_refs (struct bpf_verifier_env *env);@@ -6015,6 +6017,40 @@ static int check_ptr_alignment(struct bpf_verifier_env *env, strict); }
Quoted 4 lines
kernel/bpf/verifier.c static int check_ptr_alignment(struct bpf_verifier_env *env, · line 6022
Quoted 3 lines
kernel/bpf/verifier.c +3
-0+#define NO_PRIV_STACK 0 +#define PRIV_STACK_ADAPTIVE 1 +#define PRIV_STACK_ALWAYS 2Please use enum.
will do.
Quoted 24 lines
Quoted 12 lines
kernel/bpf/verifier.c +11
-0+ +static int bpf_enable_priv_stack (struct bpf_verifier_env *env) +{ +struct bpf_subprog_info *si; + +if (!bpf_jit_supports_private_stack ()) +return NO_PRIV_STACK ; + +switch (env->prog->type) { +case BPF_PROG_TYPE_KPROBE : +case BPF_PROG_TYPE_TRACEPOINT :kernel/bpf/verifier.c static int check_ptr_alignment(struct bpf_verifier_env *env, · line 6043
Quoted 10 lines
kernel/bpf/verifier.c +10
-0+case BPF_PROG_TYPE_PERF_EVENT : +case BPF_PROG_TYPE_RAW_TRACEPOINT : +break ; +case BPF_PROG_TYPE_TRACING : +if (env->prog->expected_attach_type !=BPF_TRACE_ITER ) +break ; + fallthrough; +default : +return NO_PRIV_STACK ; + }Probably worth adding:
if (!bpf_prog_check_recur(env->prog))
Quoted 6 lines
return NO_PRIV_STACK;and remove case
BPF_PROG_TYPE_TRACINGentry
with comment thatbpf_prog_check_recur()checks all prog types that use bpf trampoline while kprobe/tp/raw_tp don't use trampoline hence checked explicitly.
Yes. I can do this. But to use bpf_prog_check_recur() effective, I need to make the following change:
include/linux/bpf_verifier.h +1 -2
@@ -889,9 +889,8 @@ static inline bool bpf_prog_check_recur(const struct bpf_prog *prog)return prog->expected_attach_type !=BPF_TRACE_ITER ;case BPF_PROG_TYPE_STRUCT_OPS :case BPF_PROG_TYPE_LSM : -return false;default : -return true; +return false; } }
So it return true *ONLY* if the trampoline recursion detection is implemented for specific prog types.
With that, the ultimiate bpf_enable_priv_stack() func (after the whole patch set) will look like:
static enum priv_stack_mode bpf_enable_priv_stack(struct bpf_prog *prog)
{
if (!bpf_jit_supports_private_stack())
return NO_PRIV_STACK;
/* bpf_prog_check_recur() checks all prog types that use bpf trampoline
* while kprobe/tp/perf_event/raw_tp don't use trampoline hence checked
* explicitly.
*/
switch (prog->type) {
case BPF_PROG_TYPE_KPROBE:
case BPF_PROG_TYPE_TRACEPOINT:
case BPF_PROG_TYPE_PERF_EVENT:
case BPF_PROG_TYPE_RAW_TRACEPOINT:
return PRIV_STACK_ADAPTIVE;
default:
break;
}
if (!bpf_prog_check_recur(prog))
return NO_PRIV_STACK;
if (prog->type == BPF_PROG_TYPE_STRUCT_OPS)
return PRIV_STACK_ALWAYS;
return PRIV_STACK_ADAPTIVE;
}Quoted 80 lines
Quoted 55 lines
kernel/bpf/verifier.c +26
-3+ + si = env->subprog_info; +for (int i =0 ; i < env->subprog_cnt; i++) { +if (si[i].has_tail_call) +return NO_PRIV_STACK ; + } + +return PRIV_STACK_ADAPTIVE ; +} +static int round_up_stack_depth (struct bpf_verifier_env *env,int stack_depth) {if (env->prog->jit_requested)@@ -6033,11 +6069,12 @@ static int round_up_stack_depth(struct bpf_verifier_env *env, int stack_depth)* only needs a local stack of MAX_CALL_FRAMES to remember callsites */ static int check_max_stack_depth_subprog (struct bpf_verifier_env *env,int idx, -int *subtree_depth,int *depth_frame) +int *subtree_depth,int *depth_frame, +int priv_stack_supported) {struct bpf_subprog_info *subprog = env->subprog_info;struct bpf_insn *insn = env->prog->insnsi; -int depth =0 , frame =0 , i, subprog_end; +int depth =0 , frame =0 , i, subprog_end, subprog_depth;bool tail_call_reachable = false;int ret_insn[MAX_CALL_FRAMES ];int ret_prog[MAX_CALL_FRAMES ];@@ -6070,11 +6107,23 @@ static int check_max_stack_depth_subprog(struct bpf_verifier_env *env, int idx, depth);return -EACCES ; } - depth +=round_up_stack_depth (env, subprog[idx].stack_depth); + subprog_depth =round_up_stack_depth (env, subprog[idx].stack_depth); + depth += subprog_depth;if (depth >MAX_BPF_STACK && !*subtree_depth) { *subtree_depth = depth; *depth_frame = frame +1 ; } +if (priv_stack_supported !=NO_PRIV_STACK ) { +if (!subprog[idx].use_priv_stack) { +if (subprog_depth >MAX_BPF_STACK ) { +verbose (env,"stack size of subprog %d is %d. Too large\n" , + idx, subprog_depth); +return -EACCES ; + } +if (subprog_depth >=BPF_PRIV_STACK_MIN_SIZE ) + subprog[idx].use_priv_stack = true; + } + } continue_func: subprog_end = subprog[idx +1 ].start;for (; i < subprog_end; i++) {kernel/bpf/verifier.c static int check_max_stack_depth(struct bpf_verifier_env *env) · line 6230
Quoted 8 lines
kernel/bpf/verifier.c +5
-0@@ -6174,19 +6223,29 @@ static int check_max_stack_depth(struct bpf_verifier_env *env) {struct bpf_subprog_info *si = env->subprog_info;int ret, subtree_depth =0 , depth_frame; +int priv_stack_supported; + + priv_stack_supported =bpf_enable_priv_stack (env); +if (priv_stack_supported <0 ) +return priv_stack_supported;if it was enum, the compiler would have warned that the above is meaningless.
Quoted 5 lines
kernel/bpf/verifier.c +2
-1for (int i =0 ; i < env->subprog_cnt; i++) {if (!i || si[i].is_async_cb) { - ret =check_max_stack_depth_subprog (env, i, &subtree_depth, &depth_frame); + ret =check_max_stack_depth_subprog (env, i, &subtree_depth, &depth_frame, + priv_stack_supported);kernel/bpf/verifier.c static int check_max_stack_depth(struct bpf_verifier_env *env) · line 6240
Quoted 10 lines
kernel/bpf/verifier.c +2
-4if (ret <0 )return ret; } } -if (subtree_depth >MAX_BPF_STACK ) { -verbose (env,"combined stack size of %d calls is %d. Too large\n" , - depth_frame, subtree_depth); -return -EACCES ; +if (priv_stack_supported ==NO_PRIV_STACK ) { +if (subtree_depth >MAX_BPF_STACK ) {
Quoted 3 lines
no need for extra indent. Use:
if (priv_stack_supported==NO_PRIV_STACK&&subtree_depth > MAX_BPF_STACK) {
The reason is to accommodate future changes since there will be multiple if statements inside 'priv_stack_supported == NO_PRIV_STACK' condition. But I agree that we do not need extra indent here and I can do it in later patch when necessary.
Quoted 11 lines
kernel/bpf/verifier.c static int check_max_stack_depth(struct bpf_verifier_env *env) · line 6249
Quoted 10 lines
kernel/bpf/verifier.c +6
-0+verbose (env,"combined stack size of %d calls is %d. Too large\n" , + depth_frame, subtree_depth); +return -EACCES ; + } } +if (si[0 ].use_priv_stack) + env->prog->aux->use_priv_stack = true;return 0 ; }pw-bot: cr
Yonghong Song
reviewerPATCH v8 3/9 bpf: Check potential private stack recursion for progs with async callback
In reply to Yonghong SongIn previous patch, tracing progs are enabled for private stack since recursion checking ensures there exists no nested same bpf prog run on the same cpu.
But it is still possible for nested bpf subprog run on the same cpu if the same subprog is called in both main prog and async callback, or in different async callbacks. For example,
main_prog
bpf_timer_set_callback(timer, timer_cb);
call sub1
sub1
...
time_cb
call sub1
In the above case, nested subprog run for sub1 is possible with one in process context and the other in softirq context. If this is the case, the verifier will disable private stack for this bpf prog.
--- kernel/bpf/verifier.c | 46 ++++++++++++++++++++++++++++++++++++++----- 1 file changed, 41 insertions(+), 5 deletions(-)
kernel/bpf/verifier.c +41 -5
@@ -6070,7 +6070,8 @@ static int round_up_stack_depth(struct bpf_verifier_env *env, int stack_depth)*/ static int check_max_stack_depth_subprog (struct bpf_verifier_env *env,int idx,int *subtree_depth,int *depth_frame, -int priv_stack_supported) +int priv_stack_supported, +char *subprog_visited) {struct bpf_subprog_info *subprog = env->subprog_info;struct bpf_insn *insn = env->prog->insnsi;
@@ -6120,8 +6121,12 @@ static int check_max_stack_depth_subprog(struct bpf_verifier_env *env, int idx, idx, subprog_depth);return -EACCES ; } -if (subprog_depth >=BPF_PRIV_STACK_MIN_SIZE ) +if (subprog_depth >=BPF_PRIV_STACK_MIN_SIZE ) { subprog[idx].use_priv_stack = true; + subprog_visited[idx] =1 ; + } + }else { + subprog_visited[idx] =1 ; } } continue_func:
@@ -6222,19 +6227,42 @@ static int check_max_stack_depth_subprog(struct bpf_verifier_env *env, int idx,static int check_max_stack_depth (struct bpf_verifier_env *env) {struct bpf_subprog_info *si = env->subprog_info; +char *subprogs1 =NULL , *subprogs2 =NULL ;int ret, subtree_depth =0 , depth_frame; +int orig_priv_stack_supported;int priv_stack_supported; priv_stack_supported =bpf_enable_priv_stack (env);if (priv_stack_supported <0 )return priv_stack_supported; + orig_priv_stack_supported = priv_stack_supported; +if (orig_priv_stack_supported !=NO_PRIV_STACK ) { + subprogs1 =kvmalloc (env->subprog_cnt *2 , __GFP_ZERO); +if (!subprogs1) + priv_stack_supported =NO_PRIV_STACK ; +else + subprogs2 = subprogs1 + env->subprog_cnt; + } +for (int i =0 ; i < env->subprog_cnt; i++) {if (!i || si[i].is_async_cb) { ret =check_max_stack_depth_subprog (env, i, &subtree_depth, &depth_frame, - priv_stack_supported); + priv_stack_supported, subprogs2);if (ret <0 ) -return ret; + goto out; + +if (priv_stack_supported !=NO_PRIV_STACK ) { +for (int j =0 ; j < env->subprog_cnt; j++) { +if (subprogs1[j] && subprogs2[j]) { + priv_stack_supported =NO_PRIV_STACK ; +break ; + } + subprogs1[j] |= subprogs2[j]; + } + } +if (priv_stack_supported !=NO_PRIV_STACK ) +memset (subprogs2,0 , env->subprog_cnt); } }if (priv_stack_supported ==NO_PRIV_STACK ) {
@@ -6243,10 +6271,18 @@ static int check_max_stack_depth(struct bpf_verifier_env *env) depth_frame, subtree_depth);return -EACCES ; } +if (orig_priv_stack_supported ==PRIV_STACK_ADAPTIVE ) { +for (int i =0 ; i < env->subprog_cnt; i++) + si[i].use_priv_stack = false; + } }if (si[0 ].use_priv_stack) env->prog->aux->use_priv_stack = true; -return 0 ; + ret =0 ; + +out: +kvfree (subprogs1); +return ret; }#ifndef CONFIG_BPF_JIT_ALWAYS_ON
Signature · 1 line
2.43.5
Re: [PATCH bpf-next v8 3/9] bpf: Check potential private stack recursion for progs with async callback
Quoted 59 lines · Yonghong Song
In previous patch, tracing progs are enabled for private stack since recursion checking ensures there exists no nested same bpf prog run on the same cpu.
But it is still possible for nested bpf subprog run on the same cpu if the same subprog is called in both main prog and async callback, or in different async callbacks. For example,
main_prog
bpf_timer_set_callback(timer, timer_cb);
call sub1
sub1
...
time_cb
call sub1In the above case, nested subprog run for sub1 is possible with one in process context and the other in softirq context. If this is the case, the verifier will disable private stack for this bpf prog.
Signed-off-by Yonghong Song <[email protected]>--- kernel/bpf/verifier.c | 46 ++++++++++++++++++++++++++++++++++++++----- 1 file changed, 41 insertions(+), 5 deletions(-)kernel/bpf/verifier.c +8
-2@@ -6070,7 +6070,8 @@ static int round_up_stack_depth(struct bpf_verifier_env *env, int stack_depth)*/ static int check_max_stack_depth_subprog (struct bpf_verifier_env *env,int idx,int *subtree_depth,int *depth_frame, -int priv_stack_supported) +int priv_stack_supported, +char *subprog_visited) {struct bpf_subprog_info *subprog = env->subprog_info;struct bpf_insn *insn = env->prog->insnsi;@@ -6120,8 +6121,12 @@ static int check_max_stack_depth_subprog(struct bpf_verifier_env *env, int idx, idx, subprog_depth);return -EACCES ; } -if (subprog_depth >=BPF_PRIV_STACK_MIN_SIZE ) +if (subprog_depth >=BPF_PRIV_STACK_MIN_SIZE ) { subprog[idx].use_priv_stack = true; + subprog_visited[idx] =1 ; + } + }else { + subprog_visited[idx] =1 ; } } continue_func:@@ -6222,19 +6227,42 @@ static int check_max_stack_depth_subprog(struct bpf_verifier_env *env, int idx,static int check_max_stack_depth (struct bpf_verifier_env *env) {struct bpf_subprog_info *si = env->subprog_info; +char *subprogs1 =NULL , *subprogs2 =NULL ;int ret, subtree_depth =0 , depth_frame;
kernel/bpf/verifier.c static int check_max_stack_depth_subprog(struct bpf_verifier_env *env, int idx, · line 6241
Quoted 10 lines
kernel/bpf/verifier.c +4
-0+int orig_priv_stack_supported;int priv_stack_supported; priv_stack_supported =bpf_enable_priv_stack (env);if (priv_stack_supported <0 )return priv_stack_supported; + orig_priv_stack_supported = priv_stack_supported; +if (orig_priv_stack_supported !=NO_PRIV_STACK ) { + subprogs1 =kvmalloc (env->subprog_cnt *2 , __GFP_ZERO);
Just __GFP_ZERO ?!
Overall the algo is messy. Pls think of a cleaner way of checking. Add two bool flags to bpf_subprog_info:visited_with_priv_stackvisited_without_priv_stack
and after walking all subrpogs add another loop over subprogs that checks for exclusivity of these flags?
Probably other algos are possible.
Quoted 52 lines
kernel/bpf/verifier.c +29
-4+if (!subprogs1) + priv_stack_supported =NO_PRIV_STACK ; +else + subprogs2 = subprogs1 + env->subprog_cnt; + } +for (int i =0 ; i < env->subprog_cnt; i++) {if (!i || si[i].is_async_cb) { ret =check_max_stack_depth_subprog (env, i, &subtree_depth, &depth_frame, - priv_stack_supported); + priv_stack_supported, subprogs2);if (ret <0 ) -return ret; + goto out; + +if (priv_stack_supported !=NO_PRIV_STACK ) { +for (int j =0 ; j < env->subprog_cnt; j++) { +if (subprogs1[j] && subprogs2[j]) { + priv_stack_supported =NO_PRIV_STACK ; +break ; + } + subprogs1[j] |= subprogs2[j]; + } + } +if (priv_stack_supported !=NO_PRIV_STACK ) +memset (subprogs2,0 , env->subprog_cnt); } }if (priv_stack_supported ==NO_PRIV_STACK ) {@@ -6243,10 +6271,18 @@ static int check_max_stack_depth(struct bpf_verifier_env *env) depth_frame, subtree_depth);return -EACCES ; } +if (orig_priv_stack_supported ==PRIV_STACK_ADAPTIVE ) { +for (int i =0 ; i < env->subprog_cnt; i++) + si[i].use_priv_stack = false; + } }if (si[0 ].use_priv_stack) env->prog->aux->use_priv_stack = true; -return 0 ; + ret =0 ; + +out: +kvfree (subprogs1); +return ret; }#ifndef CONFIG_BPF_JIT_ALWAYS_ON --2.43.5
Yonghong Song
reviewerRe: [PATCH bpf-next v8 3/9] bpf: Check potential private stack recursion for progs with async callback
Quoted 71 lines · Alexei Starovoitov
Quoted 58 lines · Yonghong Song
In previous patch, tracing progs are enabled for private stack since recursion checking ensures there exists no nested same bpf prog run on the same cpu.
But it is still possible for nested bpf subprog run on the same cpu if the same subprog is called in both main prog and async callback, or in different async callbacks. For example,
main_progbpf_timer_set_callback(timer, timer_cb); call sub1 sub1 ...
time_cb
call sub1In the above case, nested subprog run for sub1 is possible with one in process context and the other in softirq context. If this is the case, the verifier will disable private stack for this bpf prog.
Signed-off-by Yonghong Song <[email protected]>--- kernel/bpf/verifier.c | 46 ++++++++++++++++++++++++++++++++++++++----- 1 file changed, 41 insertions(+), 5 deletions(-)kernel/bpf/verifier.c +8
-2@@ -6070,7 +6070,8 @@ static int round_up_stack_depth(struct bpf_verifier_env *env, int stack_depth)*/ static int check_max_stack_depth_subprog (struct bpf_verifier_env *env,int idx,int *subtree_depth,int *depth_frame, -int priv_stack_supported) +int priv_stack_supported, +char *subprog_visited) {struct bpf_subprog_info *subprog = env->subprog_info;struct bpf_insn *insn = env->prog->insnsi;@@ -6120,8 +6121,12 @@ static int check_max_stack_depth_subprog(struct bpf_verifier_env *env, int idx, idx, subprog_depth);return -EACCES ; } -if (subprog_depth >=BPF_PRIV_STACK_MIN_SIZE ) +if (subprog_depth >=BPF_PRIV_STACK_MIN_SIZE ) { subprog[idx].use_priv_stack = true; + subprog_visited[idx] =1 ; + } + }else { + subprog_visited[idx] =1 ; } } continue_func:@@ -6222,19 +6227,42 @@ static int check_max_stack_depth_subprog(struct bpf_verifier_env *env, int idx,static int check_max_stack_depth (struct bpf_verifier_env *env) {struct bpf_subprog_info *si = env->subprog_info; +char *subprogs1 =NULL , *subprogs2 =NULL ;int ret, subtree_depth =0 , depth_frame;kernel/bpf/verifier.c static int check_max_stack_depth_subprog(struct bpf_verifier_env *env, int idx, · line 6241
Quoted 10 lines
kernel/bpf/verifier.c +4
-0+int orig_priv_stack_supported;int priv_stack_supported; priv_stack_supported =bpf_enable_priv_stack (env);if (priv_stack_supported <0 )return priv_stack_supported; + orig_priv_stack_supported = priv_stack_supported; +if (orig_priv_stack_supported !=NO_PRIV_STACK ) { + subprogs1 =kvmalloc (env->subprog_cnt *2 , __GFP_ZERO);Just
__GFP_ZERO?!
Quoted 4 lines
Overall the algo is messy. Pls think of a cleaner way of checking. Add two bool flags to
bpf_subprog_info:visited_with_priv_stackvisited_without_priv_stack
Actually this is what I thought initially as well with two bool flags in bpf_subprog_info. Later on, I think since these two bool flags are used ONLY in this function, probably not worthwhile to add them to the head file.
But since you suggest this, I can go to two bool flag approach.
Quoted 12 lines
and after walking all subrpogs add another loop over subprogs that checks for exclusivity of these flags?
Probably other algos are possible.
Quoted 7 lines
kernel/bpf/verifier.c +6
-0+if (!subprogs1) + priv_stack_supported =NO_PRIV_STACK ; +else + subprogs2 = subprogs1 + env->subprog_cnt; + } +for (int i =0 ; i < env->subprog_cnt; i++) {
[...]
Yonghong Song
reviewerPATCH v8 4/9 bpf: Allocate private stack for eligible main prog or subprogs
In reply to Yonghong SongFor any main prog or subprogs, allocate private stack space if requested by subprog info or main prog. The alignment for private stack is 16 since maximum stack alignment is 16 for bpf-enabled archs.
For x86_64 arch, the allocated private stack is freed in arch specific implementation of bpf_jit_free().
--- arch/x86/net/bpf_jit_comp.c | 1 + include/linux/bpf.h | 1 + kernel/bpf/core.c | 10 ++++++++++ kernel/bpf/verifier.c | 12 ++++++++++++ 4 files changed, 24 insertions(+)
arch/x86/net/bpf_jit_comp.c +1 -0
@@ -3544,6 +3544,7 @@ void bpf_jit_free(struct bpf_prog *prog) prog->bpf_func = (void *)prog->bpf_func -cfi_get_offset (); hdr =bpf_jit_binary_pack_hdr (prog);bpf_jit_binary_pack_free (hdr,NULL ); +free_percpu (prog->aux->priv_stack_ptr);WARN_ON_ONCE (!bpf_prog_kallsyms_verify_off (prog)); }
include/linux/bpf.h +1 -0
@@ -1507,6 +1507,7 @@ struct bpf_prog_aux {u32 max_rdwr_access;struct btf *attach_btf;const struct bpf_ctx_arg_aux *ctx_arg_info; +void __percpu *priv_stack_ptr;struct mutex dst_mutex;/* protects dst_* pointers below, *after* prog becomes visible */ struct bpf_prog *dst_prog;struct bpf_trampoline *dst_trampoline;
kernel/bpf/core.c +10 -0
@@ -2396,6 +2396,7 @@ static void bpf_prog_select_func(struct bpf_prog *fp)*/ struct bpf_prog *bpf_prog_select_runtime (struct bpf_prog *fp,int *err) { +void __percpu *priv_stack_ptr;/* In case of BPF to BPF calls, verifier did all the prep * work with regards to JITing, etc. */
@@ -2421,6 +2422,15 @@ struct bpf_prog *bpf_prog_select_runtime(struct bpf_prog *fp, int *err)if (*err)return fp; +if (fp->aux->use_priv_stack && fp->aux->stack_depth) { + priv_stack_ptr =__alloc_percpu_gfp (fp->aux->stack_depth,16 ,GFP_KERNEL ); +if (!priv_stack_ptr) { + *err = -ENOMEM ; +return fp; + } + fp->aux->priv_stack_ptr = priv_stack_ptr; + } + fp =bpf_int_jit_compile (fp);bpf_prog_jit_attempt_done (fp);if (!fp->jited && jit_needed) {
kernel/bpf/verifier.c +12 -0
@@ -20080,6 +20080,7 @@ static int jit_subprogs(struct bpf_verifier_env *env) {struct bpf_prog *prog = env->prog, **func, *tmp;int i, j, subprog_start, subprog_end =0 , len, subprog; +void __percpu *priv_stack_ptr;struct bpf_map *map_ptr;struct bpf_insn *insn;void *old_bpf_func;
@@ -20176,6 +20177,17 @@ static int jit_subprogs(struct bpf_verifier_env *env) func[i]->aux->name[0 ] ='F' ; func[i]->aux->stack_depth = env->subprog_info[i].stack_depth; + +if (env->subprog_info[i].use_priv_stack && func[i]->aux->stack_depth) { + priv_stack_ptr =__alloc_percpu_gfp (func[i]->aux->stack_depth,16 , +GFP_KERNEL ); +if (!priv_stack_ptr) { + err = -ENOMEM ; + goto out_free; + } + func[i]->aux->priv_stack_ptr = priv_stack_ptr; + } + func[i]->jit_requested =1 ; func[i]->blinding_requested = prog->blinding_requested; func[i]->aux->kfunc_tab = prog->aux->kfunc_tab;
Signature · 1 line
2.43.5
Re: [PATCH bpf-next v8 4/9] bpf: Allocate private stack for eligible main prog or subprogs
Quoted 21 lines · Yonghong Song
For any main prog or subprogs, allocate private stack space if requested by subprog info or main prog. The alignment for private stack is 16 since maximum stack alignment is 16 for bpf-enabled archs.
For
x86_64arch, the allocated private stack is freed in arch specific implementation ofbpf_jit_free().Signed-off-by Yonghong Song <[email protected]>--- arch/x86/net/bpf_jit_comp.c | 1 + include/linux/bpf.h | 1 + kernel/bpf/core.c | 10 ++++++++++ kernel/bpf/verifier.c | 12 ++++++++++++ 4 files changed, 24 insertions(+)arch/x86/net/bpf_jit_comp.c +0
-0
arch/x86/net/bpf_jit_comp.c void bpf_jit_free(struct bpf_prog *prog) · line 3548
Quoted 5 lines
arch/x86/net/bpf_jit_comp.c +1
-0@@ -3544,6 +3544,7 @@ void bpf_jit_free(struct bpf_prog *prog) prog->bpf_func = (void *)prog->bpf_func -cfi_get_offset (); hdr =bpf_jit_binary_pack_hdr (prog);bpf_jit_binary_pack_free (hdr,NULL ); +free_percpu (prog->aux->priv_stack_ptr);WARN_ON_ONCE (!bpf_prog_kallsyms_verify_off (prog));
I'm 99% certain there are memory leaks when free and alloc are imbalanced like this:
arch code doing free while generic code doing alloc.
Quoted 30 lines
arch/x86/net/bpf_jit_comp.c +0
-0}include/linux/bpf.h +1
-0@@ -1507,6 +1507,7 @@ struct bpf_prog_aux {u32 max_rdwr_access;struct btf *attach_btf;const struct bpf_ctx_arg_aux *ctx_arg_info; +void __percpu *priv_stack_ptr;struct mutex dst_mutex;/* protects dst_* pointers below, *after* prog becomes visible */ struct bpf_prog *dst_prog;struct bpf_trampoline *dst_trampoline;kernel/bpf/core.c +1
-0@@ -2396,6 +2396,7 @@ static void bpf_prog_select_func(struct bpf_prog *fp)*/ struct bpf_prog *bpf_prog_select_runtime (struct bpf_prog *fp,int *err) { +void __percpu *priv_stack_ptr;/* In case of BPF to BPF calls, verifier did all the prep * work with regards to JITing, etc. */ @@ -2421,6 +2422,15 @@ struct bpf_prog *bpf_prog_select_runtime(struct bpf_prog *fp, int *err)if (*err)return fp;
kernel/bpf/core.c struct bpf_prog *bpf_prog_select_runtime(struct bpf_prog *fp, int *err) · line 2434
Quoted 10 lines
kernel/bpf/core.c +9
-0+if (fp->aux->use_priv_stack && fp->aux->stack_depth) { + priv_stack_ptr =__alloc_percpu_gfp (fp->aux->stack_depth,16 ,GFP_KERNEL ); +if (!priv_stack_ptr) { + *err = -ENOMEM ; +return fp; + } + fp->aux->priv_stack_ptr = priv_stack_ptr; + } + fp =bpf_int_jit_compile (fp);
what happens if this jit_compile fails?
Which part will free priv_stack_ptr?
I suspect it's a memory leak.
Quoted 35 lines
kernel/bpf/core.c +0
-0bpf_prog_jit_attempt_done (fp);if (!fp->jited && jit_needed) {kernel/bpf/verifier.c +12
-1@@ -20080,6 +20080,7 @@ static int jit_subprogs(struct bpf_verifier_env *env) {struct bpf_prog *prog = env->prog, **func, *tmp;int i, j, subprog_start, subprog_end =0 , len, subprog; +void __percpu *priv_stack_ptr;struct bpf_map *map_ptr;struct bpf_insn *insn;void *old_bpf_func;@@ -20176,6 +20177,17 @@ static int jit_subprogs(struct bpf_verifier_env *env) func[i]->aux->name[0 ] ='F' ; func[i]->aux->stack_depth = env->subprog_info[i].stack_depth; + +if (env->subprog_info[i].use_priv_stack && func[i]->aux->stack_depth) { + priv_stack_ptr =__alloc_percpu_gfp (func[i]->aux->stack_depth,16 , +GFP_KERNEL ); +if (!priv_stack_ptr) { + err = -ENOMEM ; + goto out_free; + } + func[i]->aux->priv_stack_ptr = priv_stack_ptr; + } + func[i]->jit_requested =1 ; func[i]->blinding_requested = prog->blinding_requested; func[i]->aux->kfunc_tab = prog->aux->kfunc_tab; --2.43.5
Yonghong Song
reviewerRe: [PATCH bpf-next v8 4/9] bpf: Allocate private stack for eligible main prog or subprogs
Quoted 16 lines · Alexei Starovoitov
Quoted 15 lines · Yonghong Song
For any main prog or subprogs, allocate private stack space if requested by subprog info or main prog. The alignment for private stack is 16 since maximum stack alignment is 16 for bpf-enabled archs.
For
x86_64arch, the allocated private stack is freed in arch specific implementation ofbpf_jit_free().Signed-off-by Yonghong Song <[email protected]>--- arch/x86/net/bpf_jit_comp.c | 1 + include/linux/bpf.h | 1 + kernel/bpf/core.c | 10 ++++++++++ kernel/bpf/verifier.c | 12 ++++++++++++ 4 files changed, 24 insertions(+)
Quoted 13 lines
arch/x86/net/bpf_jit_comp.c void bpf_jit_free(struct bpf_prog *prog) · line 3548
Quoted 10 lines
arch/x86/net/bpf_jit_comp.c +1
-0@@ -3544,6 +3544,7 @@ void bpf_jit_free(struct bpf_prog *prog) prog->bpf_func = (void *)prog->bpf_func -cfi_get_offset (); hdr =bpf_jit_binary_pack_hdr (prog);bpf_jit_binary_pack_free (hdr,NULL ); +free_percpu (prog->aux->priv_stack_ptr);WARN_ON_ONCE (!bpf_prog_kallsyms_verify_off (prog));I'm 99% certain there are memory leaks when free and alloc are imbalanced like this:
arch code doing free while generic code doing alloc.
Indeed, there are memory leaks. See below.
Quoted 31 lines
Quoted 31 lines
arch/x86/net/bpf_jit_comp.c +0
-0}include/linux/bpf.h +1
-0@@ -1507,6 +1507,7 @@ struct bpf_prog_aux {u32 max_rdwr_access;struct btf *attach_btf;const struct bpf_ctx_arg_aux *ctx_arg_info; +void __percpu *priv_stack_ptr;struct mutex dst_mutex;/* protects dst_* pointers below, *after* prog becomes visible */ struct bpf_prog *dst_prog;struct bpf_trampoline *dst_trampoline;kernel/bpf/core.c +1
-0@@ -2396,6 +2396,7 @@ static void bpf_prog_select_func(struct bpf_prog *fp)*/ struct bpf_prog *bpf_prog_select_runtime (struct bpf_prog *fp,int *err) { +void __percpu *priv_stack_ptr;/* In case of BPF to BPF calls, verifier did all the prep * work with regards to JITing, etc. */ @@ -2421,6 +2422,15 @@ struct bpf_prog *bpf_prog_select_runtime(struct bpf_prog *fp, int *err)if (*err)return fp;
Quoted 13 lines
kernel/bpf/core.c struct bpf_prog *bpf_prog_select_runtime(struct bpf_prog *fp, int *err) · line 2434
Quoted 10 lines
kernel/bpf/core.c +9
-0+if (fp->aux->use_priv_stack && fp->aux->stack_depth) { + priv_stack_ptr =__alloc_percpu_gfp (fp->aux->stack_depth,16 ,GFP_KERNEL ); +if (!priv_stack_ptr) { + *err = -ENOMEM ; +return fp; + } + fp->aux->priv_stack_ptr = priv_stack_ptr; + } + fp =bpf_int_jit_compile (fp);what happens if this
jit_compilefails?
Which part will freepriv_stack_ptr?
I suspect it's a memory leak.
Indeed. There will be a memory leak if jit failed. The same for below jit_subprogs() case. Will fix in the next revision.
Quoted 36 lines
Quoted 36 lines
kernel/bpf/core.c +0
-0bpf_prog_jit_attempt_done (fp);if (!fp->jited && jit_needed) {kernel/bpf/verifier.c +12
-1@@ -20080,6 +20080,7 @@ static int jit_subprogs(struct bpf_verifier_env *env) {struct bpf_prog *prog = env->prog, **func, *tmp;int i, j, subprog_start, subprog_end =0 , len, subprog; +void __percpu *priv_stack_ptr;struct bpf_map *map_ptr;struct bpf_insn *insn;void *old_bpf_func;@@ -20176,6 +20177,17 @@ static int jit_subprogs(struct bpf_verifier_env *env) func[i]->aux->name[0 ] ='F' ; func[i]->aux->stack_depth = env->subprog_info[i].stack_depth; + +if (env->subprog_info[i].use_priv_stack && func[i]->aux->stack_depth) { + priv_stack_ptr =__alloc_percpu_gfp (func[i]->aux->stack_depth,16 , +GFP_KERNEL ); +if (!priv_stack_ptr) { + err = -ENOMEM ; + goto out_free; + } + func[i]->aux->priv_stack_ptr = priv_stack_ptr; + } + func[i]->jit_requested =1 ; func[i]->blinding_requested = prog->blinding_requested; func[i]->aux->kfunc_tab = prog->aux->kfunc_tab; --2.43.5
Yonghong Song
reviewerPATCH v8 5/9 bpf, x86: Avoid repeated usage of bpf_prog->aux->stack_depth
In reply to Yonghong SongRefactor the code to avoid repeated usage of bpf_prog->aux->stack_depth in do_jit() func. If the private stack is used, the stack_depth will be 0 for that prog. Refactoring make it easy to adjust stack_depth.
--- arch/x86/net/bpf_jit_comp.c | 11 +++++++---- 1 file changed, 7 insertions(+), 4 deletions(-)
arch/x86/net/bpf_jit_comp.c +7 -4
@@ -1425,14 +1425,17 @@ static int do_jit(struct bpf_prog *bpf_prog, int *addrs, u8 *image, u8 *rw_imageint i, excnt =0 ;int ilen, proglen =0 ;u8 *prog = temp; +u32 stack_depth;int err; + stack_depth = bpf_prog->aux->stack_depth; + arena_vm_start =bpf_arena_get_kern_vm_start (bpf_prog->aux->arena); user_vm_start =bpf_arena_get_user_vm_start (bpf_prog->aux->arena);detect_reg_usage (insn, insn_cnt, callee_regs_used); -emit_prologue (&prog, bpf_prog->aux->stack_depth, +emit_prologue (&prog, stack_depth,bpf_prog_was_classic (bpf_prog), tail_call_reachable,bpf_is_subprog (bpf_prog), bpf_prog->aux->exception_cb);/* Exception callback will clobber callee regs for its own use, and
@@ -2128,7 +2131,7 @@ st: if (is_imm8(insn->off)) func = (u8 *) __bpf_call_base + imm32;if (tail_call_reachable) { -LOAD_TAIL_CALL_CNT_PTR (bpf_prog->aux->stack_depth); +LOAD_TAIL_CALL_CNT_PTR (stack_depth); ip +=7 ; }if (!imm32)
@@ -2145,13 +2148,13 @@ st: if (is_imm8(insn->off)) &bpf_prog->aux->poke_tab[imm32 -1 ], &prog, image + addrs[i -1 ], callee_regs_used, - bpf_prog->aux->stack_depth, + stack_depth, ctx); else emit_bpf_tail_call_indirect(bpf_prog, &prog, callee_regs_used, - bpf_prog->aux->stack_depth, + stack_depth, image + addrs[i - 1], ctx);break ;
Signature · 1 line
2.43.5
Yonghong Song
reviewerPATCH v8 6/9 bpf, x86: Support private stack in jit
In reply to Yonghong SongSupport private stack in jit. The x86 register 9 (X86_REG_R9) is used to replace bpf frame register (BPF_REG_10). The private stack is used per subprog if it is enabled by verifier. The X86_REG_R9 is saved and restored around every func call (not including tailcall) to maintain correctness of X86_REG_R9.
--- arch/x86/net/bpf_jit_comp.c | 61 +++++++++++++++++++++++++++++++++++++ 1 file changed, 61 insertions(+)
arch/x86/net/bpf_jit_comp.c +61 -0
@@ -325,6 +325,22 @@ struct jit_context {/* Number of bytes that will be skipped on tailcall */ #define X86_TAIL_CALL_OFFSET (12 + ENDBR_INSN_SIZE) +static void push_r9 (u8 **pprog) +{ +u8 *prog = *pprog; + +EMIT2 (0x41 ,0x51 );/* push r9 */ + *pprog = prog; +} + +static void pop_r9 (u8 **pprog) +{ +u8 *prog = *pprog; + +EMIT2 (0x41 ,0x59 );/* pop r9 */ + *pprog = prog; +} +static void push_r12 (u8 **pprog) {u8 *prog = *pprog;
@@ -1404,6 +1420,24 @@ static void emit_shiftx(u8 **pprog, u32 dst_reg, u8 src_reg, bool is64, u8 op) *pprog = prog; } +static void emit_priv_frame_ptr (u8 **pprog,void __percpu *priv_frame_ptr) +{ +u8 *prog = *pprog; + +/* movabs r9, priv_frame_ptr */ +emit_mov_imm64 (&prog,X86_REG_R9 , (__force long ) priv_frame_ptr >>32 , + (u32 ) (__force long ) priv_frame_ptr); + +#ifdef CONFIG_SMP +/* add <r9>, gs:[<off>] */ +EMIT2 (0x65 ,0x4c ); +EMIT3 (0x03 ,0x0c ,0x25 ); +EMIT ((u32 )(unsigned long )&this_cpu_off,4 ); +#endif + + *pprog = prog; +} +#define INSN_SZ_DIFF (((addrs[i] - addrs[i - 1]) - (prog - temp)))#define __LOAD_TCC_PTR (off) \
@@ -1421,6 +1455,7 @@ static int do_jit(struct bpf_prog *bpf_prog, int *addrs, u8 *image, u8 *rw_imageint insn_cnt = bpf_prog->len;bool seen_exit = false;u8 temp[BPF_MAX_INSN_SIZE +BPF_INSN_SAFETY ]; +void __percpu *priv_frame_ptr =NULL ;u64 arena_vm_start, user_vm_start;int i, excnt =0 ;int ilen, proglen =0 ;
@@ -1429,6 +1464,10 @@ static int do_jit(struct bpf_prog *bpf_prog, int *addrs, u8 *image, u8 *rw_imageint err; stack_depth = bpf_prog->aux->stack_depth; +if (bpf_prog->aux->priv_stack_ptr) { + priv_frame_ptr = bpf_prog->aux->priv_stack_ptr +round_up (stack_depth,8 ); + stack_depth =0 ; + } arena_vm_start =bpf_arena_get_kern_vm_start (bpf_prog->aux->arena); user_vm_start =bpf_arena_get_user_vm_start (bpf_prog->aux->arena);
@@ -1457,6 +1496,9 @@ static int do_jit(struct bpf_prog *bpf_prog, int *addrs, u8 *image, u8 *rw_imageemit_mov_imm64 (&prog,X86_REG_R12 , arena_vm_start >>32 , (u32 ) arena_vm_start); +if (priv_frame_ptr) +emit_priv_frame_ptr (&prog, priv_frame_ptr); + ilen = prog - temp;if (rw_image)memcpy (rw_image + proglen, temp, ilen);
@@ -1476,6 +1518,14 @@ static int do_jit(struct bpf_prog *bpf_prog, int *addrs, u8 *image, u8 *rw_imageu8 *func;int nops; +if (priv_frame_ptr) { +if (src_reg ==BPF_REG_FP ) + src_reg =X86_REG_R9 ; + +if (dst_reg ==BPF_REG_FP ) + dst_reg =X86_REG_R9 ; + } +switch (insn->code) {/* ALU */ case BPF_ALU |BPF_ADD |BPF_X :
@@ -2136,9 +2186,15 @@ st: if (is_imm8(insn->off)) }if (!imm32)return -EINVAL ; +if (priv_frame_ptr) { +push_r9 (&prog); + ip +=2 ; + } ip +=x86_call_depth_emit_accounting (&prog, func, ip);if (emit_call (&prog, func, ip))return -EINVAL ; +if (priv_frame_ptr) +pop_r9 (&prog);break ; }
@@ -3563,6 +3619,11 @@ bool bpf_jit_supports_exceptions(void)return IS_ENABLED (CONFIG_UNWINDER_ORC ); } +bool bpf_jit_supports_private_stack (void ) +{ +return true; +} +void arch_bpf_stack_walk (bool (*consume_fn)(void *cookie,u64 ip,u64 sp,u64 bp),void *cookie) {#if defined(CONFIG_UNWINDER_ORC )
Signature · 1 line
2.43.5
Yonghong Song
reviewerPATCH v8 7/9 selftests/bpf: Add tracing prog private stack tests
In reply to Yonghong SongSome private stack tests are added including:
- main prog only with stack size greater than BPF_PSTACK_MIN_SIZE.
- main prog only with stack size smaller than BPF_PSTACK_MIN_SIZE.
- prog with one subprog having MAX_BPF_STACK stack size and another subprog having non-zero small stack size.
- prog with callback function.
- prog with exception in main prog or subprog.
- prog with async callback without nesting
- prog with async callback with possible nesting
--- .../selftests/bpf/prog_tests/verifier.c | 2 + .../bpf/progs/verifier_private_stack.c | 272 ++++++++++++++++++ 2 files changed, 274 insertions(+) create mode 100644 tools/testing/selftests/bpf/progs/verifier_private_stack.c
tools/testing/selftests/bpf/prog_tests/verifier.c +2 -0
@@ -61,6 +61,7 @@#include "verifier_or_jmp32_k.skel.h" #include "verifier_precision.skel.h" #include "verifier_prevent_map_lookup.skel.h" +#include "verifier_private_stack.skel.h" #include "verifier_raw_stack.skel.h" #include "verifier_raw_tp_writable.skel.h" #include "verifier_reg_equal.skel.h"
@@ -188,6 +189,7 @@ void test_verifier_bpf_fastcall(void) { RUN(verifier_bpf_fastcall); }void test_verifier_or_jmp32_k (void ) {RUN (verifier_or_jmp32_k); }void test_verifier_precision (void ) {RUN (verifier_precision); }void test_verifier_prevent_map_lookup (void ) {RUN (verifier_prevent_map_lookup); } +void test_verifier_private_stack (void ) {RUN (verifier_private_stack); }void test_verifier_raw_stack (void ) {RUN (verifier_raw_stack); }void test_verifier_raw_tp_writable (void ) {RUN (verifier_raw_tp_writable); }void test_verifier_reg_equal (void ) {RUN (verifier_reg_equal); }
tools/testing/selftests/bpf/progs/verifier_private_stack.c new file +272 -0
272 lines not on this page · raw message
Signature · 1 line
2.43.5
Yonghong Song
reviewerPATCH v8 8/9 bpf: Support private stack for struct_ops progs
In reply to Yonghong SongFor struct_ops progs, whether a particular prog will use private stack or not (prog->aux->use_priv_stack) will be set before actual insn-level verification for that prog. One particular implementation is to piggyback on struct_ops->check_member(). The next patch will have an example for this. The struct_ops->check_member() will set prog->aux->use_priv_stack to be true which enables private stack usage with ignoring BPF_PRIV_STACK_MIN_SIZE limit.
If use_priv_stack is true for a particular struct_ops prog, bpf trampoline will need to do recursion checks (one level at this point) to avoid stack overwrite. A field (recursion_skipped()) is added to bpf_prog_aux structure such that if bpf_prog->aux->recursion_skipped is set by the struct_ops subsystem, the function will be called to terminate the prog run, collect related info, etc.
--- include/linux/bpf.h | 1 + include/linux/bpf_verifier.h | 1 + kernel/bpf/trampoline.c | 4 ++++ kernel/bpf/verifier.c | 36 ++++++++++++++++++++++++++++++++---- 4 files changed, 38 insertions(+), 4 deletions(-)
include/linux/bpf.h +1 -0
@@ -1528,6 +1528,7 @@ struct bpf_prog_aux {u64 prog_array_member_cnt;/* counts how many times as member of prog_array */ struct mutex ext_mutex;/* mutex for is_extended and prog_array_member_cnt */ struct bpf_arena *arena; +void (*recursion_skipped)(struct bpf_prog *prog);/* callback if recursion is skipped */ /* BTF_KIND_FUNC_PROTO for valid attach_btf_id */ const struct btf_type *attach_func_proto;/* function name for valid attach_btf_id */
include/linux/bpf_verifier.h +1 -0
@@ -889,6 +889,7 @@ static inline bool bpf_prog_check_recur(const struct bpf_prog *prog)case BPF_PROG_TYPE_TRACING :return prog->expected_attach_type !=BPF_TRACE_ITER ;case BPF_PROG_TYPE_STRUCT_OPS : +return prog->aux->use_priv_stack;case BPF_PROG_TYPE_LSM :return false;default :
kernel/bpf/trampoline.c +4 -0
@@ -899,6 +899,8 @@ static u64 notrace __bpf_prog_enter_recur(struct bpf_prog *prog, struct bpf_tramif (unlikely (this_cpu_inc_return (*(prog->active)) !=1 )) {bpf_prog_inc_misses_counter (prog); +if (prog->aux->recursion_skipped) + prog->aux->recursion_skipped (prog);return 0 ; }return bpf_prog_start_time ();
@@ -975,6 +977,8 @@ u64 notrace __bpf_prog_enter_sleepable_recur(struct bpf_prog *prog,if (unlikely (this_cpu_inc_return (*(prog->active)) !=1 )) {bpf_prog_inc_misses_counter (prog); +if (prog->aux->recursion_skipped) + prog->aux->recursion_skipped (prog);return 0 ; }return bpf_prog_start_time ();
kernel/bpf/verifier.c +32 -4
@@ -6023,17 +6023,31 @@ static int check_ptr_alignment(struct bpf_verifier_env *env,static int bpf_enable_priv_stack (struct bpf_verifier_env *env) { +bool force_priv_stack = env->prog->aux->use_priv_stack;struct bpf_subprog_info *si; +int ret; + +if (!bpf_jit_supports_private_stack ()) { +if (force_priv_stack) { +verbose (env,"Private stack not supported by jit\n" ); +return -EACCES ; + } -if (!bpf_jit_supports_private_stack ())return NO_PRIV_STACK ; + } + ret =PRIV_STACK_ADAPTIVE ;switch (env->prog->type) {case BPF_PROG_TYPE_KPROBE :case BPF_PROG_TYPE_TRACEPOINT :case BPF_PROG_TYPE_PERF_EVENT :case BPF_PROG_TYPE_RAW_TRACEPOINT :break ; +case BPF_PROG_TYPE_STRUCT_OPS : +if (!force_priv_stack) +return NO_PRIV_STACK ; + ret =PRIV_STACK_ALWAYS ; +break ;case BPF_PROG_TYPE_TRACING :if (env->prog->expected_attach_type !=BPF_TRACE_ITER )break ;
@@ -6044,11 +6058,18 @@ static int bpf_enable_priv_stack(struct bpf_verifier_env *env) si = env->subprog_info;for (int i =0 ; i < env->subprog_cnt; i++) { -if (si[i].has_tail_call) +if (si[i].has_tail_call) { +if (ret ==PRIV_STACK_ALWAYS ) { +verbose (env, +"Private stack not supported due to tail call presence\n" ); +return -EACCES ; + } +return NO_PRIV_STACK ; + } } -return PRIV_STACK_ADAPTIVE ; +return ret; }static int round_up_stack_depth (struct bpf_verifier_env *env,int stack_depth)
@@ -6121,7 +6142,8 @@ static int check_max_stack_depth_subprog(struct bpf_verifier_env *env, int idx, idx, subprog_depth);return -EACCES ; } -if (subprog_depth >=BPF_PRIV_STACK_MIN_SIZE ) { +if (priv_stack_supported ==PRIV_STACK_ALWAYS || + subprog_depth >=BPF_PRIV_STACK_MIN_SIZE ) { subprog[idx].use_priv_stack = true; subprog_visited[idx] =1 ; }
@@ -6271,6 +6293,12 @@ static int check_max_stack_depth(struct bpf_verifier_env *env) depth_frame, subtree_depth);return -EACCES ; } +if (orig_priv_stack_supported ==PRIV_STACK_ALWAYS ) { +verbose (env, +"Private stack not supported due to possible nested subprog run\n" ); + ret = -EACCES ; + goto out; + }if (orig_priv_stack_supported ==PRIV_STACK_ADAPTIVE ) {for (int i =0 ; i < env->subprog_cnt; i++) si[i].use_priv_stack = false;
Signature · 1 line
2.43.5
Re: [PATCH bpf-next v8 8/9] bpf: Support private stack for struct_ops progs
Quoted 30 lines · Yonghong Song
For
struct_opsprogs, whether a particular prog will use private stack or not (prog->aux->use_priv_stack) will be set before actual insn-level verification for that prog. One particular implementation is to piggyback onstruct_ops->check_member(). The next patch will have an example for this. Thestruct_ops->check_member()will setprog->aux->use_priv_stackto be true which enables private stack usage with ignoringBPF_PRIV_STACK_MIN_SIZElimit.If
use_priv_stackis true for a particularstruct_opsprog, bpf trampoline will need to do recursion checks (one level at this point) to avoid stack overwrite. A field (recursion_skipped()) is added tobpf_prog_auxstructure such that ifbpf_prog->aux->recursion_skippedis set by thestruct_opssubsystem, the function will be called to terminate the prog run, collect related info, etc.Acked-by Tejun Heo <[email protected]>Signed-off-by Yonghong Song <[email protected]>--- include/linux/bpf.h | 1 + include/linux/bpf_verifier.h | 1 + kernel/bpf/trampoline.c | 4 ++++ kernel/bpf/verifier.c | 36 ++++++++++++++++++++++++++++++++---- 4 files changed, 38 insertions(+), 4 deletions(-)include/linux/bpf.h +0
-0
include/linux/bpf.h struct bpf_prog_aux { · line 1531
Quoted 4 lines
include/linux/bpf.h +1
-0@@ -1528,6 +1528,7 @@ struct bpf_prog_aux {u64 prog_array_member_cnt;/* counts how many times as member of prog_array */ struct mutex ext_mutex;/* mutex for is_extended and prog_array_member_cnt */ struct bpf_arena *arena; +void (*recursion_skipped)(struct bpf_prog *prog);/* callback if recursion is skipped */
The name doesn't fit.
The recursion wasn't skipped.
It's the execution of the program that was skipped. 'recursion_detected' or 'recursion_disallowed' would be a better name.
Quoted 44 lines
include/linux/bpf.h +0
-0/* BTF_KIND_FUNC_PROTO for valid attach_btf_id */ const struct btf_type *attach_func_proto;/* function name for valid attach_btf_id */ include/linux/bpf_verifier.h +1
-0@@ -889,6 +889,7 @@ static inline bool bpf_prog_check_recur(const struct bpf_prog *prog)case BPF_PROG_TYPE_TRACING :return prog->expected_attach_type !=BPF_TRACE_ITER ;case BPF_PROG_TYPE_STRUCT_OPS : +return prog->aux->use_priv_stack;case BPF_PROG_TYPE_LSM :return false;default :kernel/bpf/trampoline.c +4
-0@@ -899,6 +899,8 @@ static u64 notrace __bpf_prog_enter_recur(struct bpf_prog *prog, struct bpf_tramif (unlikely (this_cpu_inc_return (*(prog->active)) !=1 )) {bpf_prog_inc_misses_counter (prog); +if (prog->aux->recursion_skipped) + prog->aux->recursion_skipped (prog);return 0 ; }return bpf_prog_start_time ();@@ -975,6 +977,8 @@ u64 notrace __bpf_prog_enter_sleepable_recur(struct bpf_prog *prog,if (unlikely (this_cpu_inc_return (*(prog->active)) !=1 )) {bpf_prog_inc_misses_counter (prog); +if (prog->aux->recursion_skipped) + prog->aux->recursion_skipped (prog);return 0 ; }return bpf_prog_start_time ();kernel/bpf/verifier.c +0
-0@@ -6023,17 +6023,31 @@ static int check_ptr_alignment(struct bpf_verifier_env *env,static int bpf_enable_priv_stack (struct bpf_verifier_env *env)
kernel/bpf/verifier.c static int check_ptr_alignment(struct bpf_verifier_env *env, · line 6034
Quoted 10 lines
kernel/bpf/verifier.c +8
-0{ +bool force_priv_stack = env->prog->aux->use_priv_stack;struct bpf_subprog_info *si; +int ret; + +if (!bpf_jit_supports_private_stack ()) { +if (force_priv_stack) { +verbose (env,"Private stack not supported by jit\n" ); +return -EACCES ; + }
This logic would fit better in the patch 2.
Less code churn and the whole approach is easier to understand.
I don't like this inband signaling.
Now I see why you had that weird <0 check in patch 2 :( This is ugly.
May be it should be a separate bool request_priv_stack:1 that struct_ops callback will set and it will clean up this logic.
Quoted 68 lines
kernel/bpf/verifier.c +16
-3-if (!bpf_jit_supports_private_stack ())return NO_PRIV_STACK ; + } + ret =PRIV_STACK_ADAPTIVE ;switch (env->prog->type) {case BPF_PROG_TYPE_KPROBE :case BPF_PROG_TYPE_TRACEPOINT :case BPF_PROG_TYPE_PERF_EVENT :case BPF_PROG_TYPE_RAW_TRACEPOINT :break ; +case BPF_PROG_TYPE_STRUCT_OPS : +if (!force_priv_stack) +return NO_PRIV_STACK ; + ret =PRIV_STACK_ALWAYS ; +break ;case BPF_PROG_TYPE_TRACING :if (env->prog->expected_attach_type !=BPF_TRACE_ITER )break ;@@ -6044,11 +6058,18 @@ static int bpf_enable_priv_stack(struct bpf_verifier_env *env) si = env->subprog_info;for (int i =0 ; i < env->subprog_cnt; i++) { -if (si[i].has_tail_call) +if (si[i].has_tail_call) { +if (ret ==PRIV_STACK_ALWAYS ) { +verbose (env, +"Private stack not supported due to tail call presence\n" ); +return -EACCES ; + } +return NO_PRIV_STACK ; + } } -return PRIV_STACK_ADAPTIVE ; +return ret; }static int
round_up_stack_depth(struct bpf_verifier_env *env, int stack_depth)kernel/bpf/verifier.c +8
-2@@ -6121,7 +6142,8 @@ static int check_max_stack_depth_subprog(struct bpf_verifier_env *env, int idx, idx, subprog_depth);return -EACCES ; } -if (subprog_depth >=BPF_PRIV_STACK_MIN_SIZE ) { +if (priv_stack_supported ==PRIV_STACK_ALWAYS || + subprog_depth >=BPF_PRIV_STACK_MIN_SIZE ) { subprog[idx].use_priv_stack = true; subprog_visited[idx] =1 ; }@@ -6271,6 +6293,12 @@ static int check_max_stack_depth(struct bpf_verifier_env *env) depth_frame, subtree_depth);return -EACCES ; } +if (orig_priv_stack_supported ==PRIV_STACK_ALWAYS ) { +verbose (env, +"Private stack not supported due to possible nested subprog run\n" ); + ret = -EACCES ; + goto out; + }if (orig_priv_stack_supported ==PRIV_STACK_ADAPTIVE ) {for (int i =0 ; i < env->subprog_cnt; i++) si[i].use_priv_stack = false; --2.43.5
Yonghong Song
reviewerRe: [PATCH bpf-next v8 8/9] bpf: Support private stack for struct_ops progs
Quoted 25 lines · Alexei Starovoitov
Quoted 24 lines · Yonghong Song
For
struct_opsprogs, whether a particular prog will use private stack or not (prog->aux->use_priv_stack) will be set before actual insn-level verification for that prog. One particular implementation is to piggyback onstruct_ops->check_member(). The next patch will have an example for this. Thestruct_ops->check_member()will setprog->aux->use_priv_stackto be true which enables private stack usage with ignoringBPF_PRIV_STACK_MIN_SIZElimit.If
use_priv_stackis true for a particularstruct_opsprog, bpf trampoline will need to do recursion checks (one level at this point) to avoid stack overwrite. A field (recursion_skipped()) is added tobpf_prog_auxstructure such that ifbpf_prog->aux->recursion_skippedis set by thestruct_opssubsystem, the function will be called to terminate the prog run, collect related info, etc.Acked-by Tejun Heo <[email protected]>Signed-off-by Yonghong Song <[email protected]>--- include/linux/bpf.h | 1 + include/linux/bpf_verifier.h | 1 + kernel/bpf/trampoline.c | 4 ++++ kernel/bpf/verifier.c | 36 ++++++++++++++++++++++++++++++++---- 4 files changed, 38 insertions(+), 4 deletions(-)
Quoted 13 lines
include/linux/bpf.h struct bpf_prog_aux { · line 1531
Quoted 9 lines
include/linux/bpf.h +1
-0@@ -1528,6 +1528,7 @@ struct bpf_prog_aux {u64 prog_array_member_cnt;/* counts how many times as member of prog_array */ struct mutex ext_mutex;/* mutex for is_extended and prog_array_member_cnt */ struct bpf_arena *arena; +void (*recursion_skipped)(struct bpf_prog *prog);/* callback if recursion is skipped */ The name doesn't fit.
The recursion wasn't skipped.
It's the execution of the program that was skipped. 'recursion_detected' or 'recursion_disallowed' would be a better name.
I will use recursion_detected().
Quoted 58 lines
Quoted 45 lines
include/linux/bpf.h +0
-0/* BTF_KIND_FUNC_PROTO for valid attach_btf_id */ const struct btf_type *attach_func_proto;/* function name for valid attach_btf_id */ include/linux/bpf_verifier.h +1
-0@@ -889,6 +889,7 @@ static inline bool bpf_prog_check_recur(const struct bpf_prog *prog)case BPF_PROG_TYPE_TRACING :return prog->expected_attach_type !=BPF_TRACE_ITER ;case BPF_PROG_TYPE_STRUCT_OPS : +return prog->aux->use_priv_stack;case BPF_PROG_TYPE_LSM :return false;default :kernel/bpf/trampoline.c +4
-0@@ -899,6 +899,8 @@ static u64 notrace __bpf_prog_enter_recur(struct bpf_prog *prog, struct bpf_tramif (unlikely (this_cpu_inc_return (*(prog->active)) !=1 )) {bpf_prog_inc_misses_counter (prog); +if (prog->aux->recursion_skipped) + prog->aux->recursion_skipped (prog);return 0 ; }return bpf_prog_start_time ();@@ -975,6 +977,8 @@ u64 notrace __bpf_prog_enter_sleepable_recur(struct bpf_prog *prog,if (unlikely (this_cpu_inc_return (*(prog->active)) !=1 )) {bpf_prog_inc_misses_counter (prog); +if (prog->aux->recursion_skipped) + prog->aux->recursion_skipped (prog);return 0 ; }return bpf_prog_start_time ();kernel/bpf/verifier.c +0
-0@@ -6023,17 +6023,31 @@ static int check_ptr_alignment(struct bpf_verifier_env *env,static int bpf_enable_priv_stack (struct bpf_verifier_env *env)kernel/bpf/verifier.c static int check_ptr_alignment(struct bpf_verifier_env *env, · line 6034
Quoted 10 lines
kernel/bpf/verifier.c +8
-0{ +bool force_priv_stack = env->prog->aux->use_priv_stack;struct bpf_subprog_info *si; +int ret; + +if (!bpf_jit_supports_private_stack ()) { +if (force_priv_stack) { +verbose (env,"Private stack not supported by jit\n" ); +return -EACCES ; + }This logic would fit better in the patch 2.
Less code churn and the whole approach is easier to understand.
Quoted 6 lines
I don't like this inband signaling.
Now I see why you had that weird <0 check in patch 2 :( This is ugly.
May be it should be a separate bool request_priv_stack:1 thatstruct_opscallback will set and it will clean up this logic.
I can add this logic to function check_struct_ops_btf_id(), which is struct_ops preparation for verification. This will ensure in bpf_enable_priv_stack(), if !bpf_jit_supports_private_stack(), it is guaranteed to return NO_PRIV_STACK.
Quoted 40 lines
Quoted 40 lines
kernel/bpf/verifier.c +16
-3-if (!bpf_jit_supports_private_stack ())return NO_PRIV_STACK ; + } + ret =PRIV_STACK_ADAPTIVE ;switch (env->prog->type) {case BPF_PROG_TYPE_KPROBE :case BPF_PROG_TYPE_TRACEPOINT :case BPF_PROG_TYPE_PERF_EVENT :case BPF_PROG_TYPE_RAW_TRACEPOINT :break ; +case BPF_PROG_TYPE_STRUCT_OPS : +if (!force_priv_stack) +return NO_PRIV_STACK ; + ret =PRIV_STACK_ALWAYS ; +break ;case BPF_PROG_TYPE_TRACING :if (env->prog->expected_attach_type !=BPF_TRACE_ITER )break ;@@ -6044,11 +6058,18 @@ static int bpf_enable_priv_stack(struct bpf_verifier_env *env) si = env->subprog_info;for (int i =0 ; i < env->subprog_cnt; i++) { -if (si[i].has_tail_call) +if (si[i].has_tail_call) { +if (ret ==PRIV_STACK_ALWAYS ) { +verbose (env, +"Private stack not supported due to tail call presence\n" ); +return -EACCES ; + } +return NO_PRIV_STACK ; + } } -return PRIV_STACK_ADAPTIVE ; +return ret; }
[...]
Yonghong Song
reviewerPATCH v8 9/9 selftests/bpf: Add struct_ops prog private stack tests
In reply to Yonghong SongAdd three tests for struct_ops using private stack.
./test_progs -t struct_ops_private_stack
#333/1 struct_ops_private_stack/private_stack:OK #333/2 struct_ops_private_stack/private_stack_fail:OK #333/3 struct_ops_private_stack/private_stack_recur:OK #333 struct_ops_private_stack:OK
The following is a snippet of a struct_ops check_member() implementation:
u32 moff = __btf_member_bit_offset(t, member) / 8;
switch (moff) {
case offsetof(struct bpf_testmod_ops3, test_1):
prog->aux->use_priv_stack = true;
prog->aux->recursion_skipped = test_1_recursion_skipped;
fallthrough;
default:
break;
}
return 0;The first test is with nested two different callback functions where the first prog has more than 512 byte stack size (including subprogs) with private stack enabled.
The second test is a negative test where the second prog has more than 512 byte stack size without private stack enabled.
The third test is the same callback function recursing itself. At run time, the jit trampoline recursion check kicks in to prevent the recursion. The recursion_skipped() callback function is implemented by the bpf_testmod, the following message in dmesg
bpf_testmod: oh no, recursing into test_1, recursion_misses 1
demonstrates the callback function is indeed triggered when recursion miss happens.
--- .../selftests/bpf/bpf_testmod/bpf_testmod.c | 104 +++++++++++++++++ .../selftests/bpf/bpf_testmod/bpf_testmod.h | 5 + .../bpf/prog_tests/struct_ops_private_stack.c | 106 ++++++++++++++++++ .../bpf/progs/struct_ops_private_stack.c | 62 ++++++++++ .../bpf/progs/struct_ops_private_stack_fail.c | 62 ++++++++++ .../progs/struct_ops_private_stack_recur.c | 50 +++++++++ 6 files changed, 389 insertions(+) create mode 100644 tools/testing/selftests/bpf/prog_tests/struct_ops_private_stack.c create mode 100644 tools/testing/selftests/bpf/progs/struct_ops_private_stack.c create mode 100644 tools/testing/selftests/bpf/progs/struct_ops_private_stack_fail.c create mode 100644 tools/testing/selftests/bpf/progs/struct_ops_private_stack_recur.c
tools/testing/selftests/bpf/bpf_testmod/bpf_testmod.c +104 -0
@@ -245,6 +245,39 @@ __bpf_kfunc void bpf_testmod_ctx_release(struct bpf_testmod_ctx *ctx)call_rcu (&ctx->rcu, testmod_free_cb); } +static struct bpf_testmod_ops3 *st_ops3; + +static int bpf_testmod_test_3 (void ) +{ +return 0 ; +} + +static int bpf_testmod_test_4 (void ) +{ +return 0 ; +} + +static struct bpf_testmod_ops3 __bpf_testmod_ops3 = { + .test_1 = bpf_testmod_test_3, + .test_2 = bpf_testmod_test_4, +}; + +static void bpf_testmod_test_struct_ops3 (void ) +{ +if (st_ops3) + st_ops3->test_1 (); +} + +__bpf_kfunc void bpf_testmod_ops3_call_test_1(void) +{ + st_ops3->test_1 (); +} + +__bpf_kfunc void bpf_testmod_ops3_call_test_2(void) +{ + st_ops3->test_2 (); +} +struct bpf_testmod_btf_type_tag_1 {int a; };
@@ -380,6 +413,8 @@ bpf_testmod_test_read(struct file *file, struct kobject *kobj, (void )bpf_testmod_test_arg_ptr_to_struct (&struct_arg1_2); +bpf_testmod_test_struct_ops3 (); + struct_arg3 =kmalloc ((sizeof (struct bpf_testmod_struct_arg_3 ) +sizeof (int )),GFP_KERNEL );if (struct_arg3 !=NULL ) {
@@ -584,6 +619,8 @@ BTF_ID_FLAGS(func, bpf_kfunc_trusted_num_test, KF_TRUSTED_ARGS) BTF_ID_FLAGS(func, bpf_kfunc_rcu_task_test, KF_RCU) BTF_ID_FLAGS(func, bpf_testmod_ctx_create, KF_ACQUIRE | KF_RET_NULL) BTF_ID_FLAGS(func, bpf_testmod_ctx_release, KF_RELEASE) +BTF_ID_FLAGS(func, bpf_testmod_ops3_call_test_1) +BTF_ID_FLAGS(func, bpf_testmod_ops3_call_test_2)BTF_KFUNCS_END (bpf_testmod_common_kfunc_ids)BTF_ID_LIST (bpf_testmod_dtor_ids)
@@ -1094,6 +1131,10 @@ static const struct bpf_verifier_ops bpf_testmod_verifier_ops = { .is_valid_access = bpf_testmod_ops_is_valid_access, }; +static const struct bpf_verifier_ops bpf_testmod_verifier_ops3 = { + .is_valid_access = bpf_testmod_ops_is_valid_access, +}; +static int bpf_dummy_reg (void *kdata,struct bpf_link *link) {struct bpf_testmod_ops *ops = kdata;
@@ -1173,6 +1214,68 @@ struct bpf_struct_ops bpf_testmod_ops2 = { .owner = THIS_MODULE, }; +static int st_ops3_reg (void *kdata,struct bpf_link *link) +{ +int err =0 ; + +mutex_lock (&st_ops_mutex); +if (st_ops3) { +pr_err ("st_ops has already been registered\n" ); + err = -EEXIST ; + goto unlock; + } + st_ops3 = kdata; + +unlock: +mutex_unlock (&st_ops_mutex); +return err; +} + +static void st_ops3_unreg (void *kdata,struct bpf_link *link) +{ +mutex_lock (&st_ops_mutex); + st_ops3 =NULL ; +mutex_unlock (&st_ops_mutex); +} + +static void test_1_recursion_skipped (struct bpf_prog *prog) +{ +struct bpf_prog_stats *stats; + + stats =this_cpu_ptr (prog->stats); +printk ("bpf_testmod: oh no, recursing into test_1, recursion_misses %llu" , +u64_stats_read (&stats->misses)); +} + +static int st_ops3_check_member (const struct btf_type *t, +const struct btf_member *member, +const struct bpf_prog *prog) +{ +u32 moff =__btf_member_bit_offset (t, member) /8 ; + +switch (moff) { +case offsetof(struct bpf_testmod_ops3 , test_1): + prog->aux->use_priv_stack = true; + prog->aux->recursion_skipped = test_1_recursion_skipped; + fallthrough; +default : +break ; + } +return 0 ; +} + +struct bpf_struct_ops bpf_testmod_ops3 = { + .verifier_ops = &bpf_testmod_verifier_ops3, + .init = bpf_testmod_ops_init, + .init_member = bpf_testmod_ops_init_member, + .reg = st_ops3_reg, + .unreg = st_ops3_unreg, + .check_member = st_ops3_check_member, + .cfi_stubs = &__bpf_testmod_ops3, + .name ="bpf_testmod_ops3" , + .owner =THIS_MODULE , +}; +static int bpf_test_mod_st_ops__test_prologue (struct st_ops_args *args) {return 0 ;
@@ -1331,6 +1434,7 @@ static int bpf_testmod_init(void) ret = ret ?:register_btf_kfunc_id_set (BPF_PROG_TYPE_STRUCT_OPS , &bpf_testmod_kfunc_set); ret = ret ?:register_bpf_struct_ops (&bpf_bpf_testmod_ops, bpf_testmod_ops); ret = ret ?:register_bpf_struct_ops (&bpf_testmod_ops2, bpf_testmod_ops2); + ret = ret ?:register_bpf_struct_ops (&bpf_testmod_ops3, bpf_testmod_ops3); ret = ret ?:register_bpf_struct_ops (&testmod_st_ops, bpf_testmod_st_ops); ret = ret ?: register_btf_id_dtor_kfuncs(bpf_testmod_dtors, ARRAY_SIZE(bpf_testmod_dtors),
tools/testing/selftests/bpf/bpf_testmod/bpf_testmod.h +5 -0
@@ -94,6 +94,11 @@ struct bpf_testmod_ops2 {int (*test_1)(void ); }; +struct bpf_testmod_ops3 { +int (*test_1)(void ); +int (*test_2)(void ); +}; +struct st_ops_args {u64 a; };
tools/testing/selftests/bpf/prog_tests/struct_ops_private_stack.c new file +106 -0
106 lines not on this page · raw message
tools/testing/selftests/bpf/progs/struct_ops_private_stack.c new file +62 -0
62 lines not on this page · raw message
tools/testing/selftests/bpf/progs/struct_ops_private_stack_fail.c new file +62 -0
62 lines not on this page · raw message
tools/testing/selftests/bpf/progs/struct_ops_private_stack_recur.c new file +50 -0
50 lines not on this page · raw message
Signature · 1 line
2.43.5