diff mbox series

[RFC,v1,08/14] bpf: Compute used callee saved registers for subprogs

Message ID 20240201042109.1150490-9-memxor@gmail.com (mailing list archive)
State RFC
Delegated to: BPF
Headers show
Series Exceptions - Resource Cleanup | expand

Checks

Context Check Description
bpf/vmtest-bpf-next-PR success PR summary
netdev/tree_selection success Guessing tree name failed - patch did not apply, async
bpf/vmtest-bpf-next-VM_Test-1 success Logs for ShellCheck
bpf/vmtest-bpf-next-VM_Test-0 success Logs for Lint
bpf/vmtest-bpf-next-VM_Test-2 success Logs for Unittests
bpf/vmtest-bpf-next-VM_Test-3 success Logs for Validate matrix.py
bpf/vmtest-bpf-next-VM_Test-5 success Logs for aarch64-gcc / build-release
bpf/vmtest-bpf-next-VM_Test-6 success Logs for aarch64-gcc / test
bpf/vmtest-bpf-next-VM_Test-7 success Logs for aarch64-gcc / veristat
bpf/vmtest-bpf-next-VM_Test-9 success Logs for s390x-gcc / build-release
bpf/vmtest-bpf-next-VM_Test-4 fail Logs for aarch64-gcc / build / build for aarch64 with gcc
bpf/vmtest-bpf-next-VM_Test-26 success Logs for x86_64-llvm-17 / veristat
bpf/vmtest-bpf-next-VM_Test-34 success Logs for x86_64-llvm-18 / veristat
bpf/vmtest-bpf-next-VM_Test-8 fail Logs for s390x-gcc / build / build for s390x with gcc
bpf/vmtest-bpf-next-VM_Test-10 success Logs for s390x-gcc / test
bpf/vmtest-bpf-next-VM_Test-11 success Logs for s390x-gcc / veristat
bpf/vmtest-bpf-next-VM_Test-12 success Logs for set-matrix
bpf/vmtest-bpf-next-VM_Test-13 success Logs for x86_64-gcc / build / build for x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-14 success Logs for x86_64-gcc / build-release
bpf/vmtest-bpf-next-VM_Test-17 pending Logs for x86_64-gcc / test (test_progs_no_alu32, false, 360) / test_progs_no_alu32 on x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-22 success Logs for x86_64-llvm-17 / build / build for x86_64 with llvm-17
bpf/vmtest-bpf-next-VM_Test-25 pending Logs for x86_64-llvm-17 / test (test_progs, false, 360) / test_progs on x86_64 with llvm-17
bpf/vmtest-bpf-next-VM_Test-28 success Logs for x86_64-llvm-17 / veristat
bpf/vmtest-bpf-next-VM_Test-29 success Logs for x86_64-llvm-18 / build / build for x86_64 with llvm-18
bpf/vmtest-bpf-next-VM_Test-30 success Logs for x86_64-llvm-18 / build-release / build for x86_64 with llvm-18 and -O2 optimization
bpf/vmtest-bpf-next-VM_Test-32 pending Logs for x86_64-llvm-18 / test (test_progs, false, 360) / test_progs on x86_64 with llvm-18
bpf/vmtest-bpf-next-VM_Test-33 pending Logs for x86_64-llvm-18 / test (test_progs_cpuv4, false, 360) / test_progs_cpuv4 on x86_64 with llvm-18
bpf/vmtest-bpf-next-VM_Test-36 success Logs for x86_64-llvm-18 / veristat
bpf/vmtest-bpf-next-VM_Test-15 success Logs for x86_64-gcc / test (test_maps, false, 360) / test_maps on x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-16 success Logs for x86_64-gcc / test (test_progs, false, 360) / test_progs on x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-18 success Logs for x86_64-gcc / test (test_progs_no_alu32_parallel, true, 30) / test_progs_no_alu32_parallel on x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-19 success Logs for x86_64-gcc / test (test_progs_parallel, true, 30) / test_progs_parallel on x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-20 success Logs for x86_64-gcc / test (test_verifier, false, 360) / test_verifier on x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-21 success Logs for x86_64-gcc / veristat / veristat on x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-23 success Logs for x86_64-llvm-17 / build-release / build for x86_64 with llvm-17 and -O2 optimization
bpf/vmtest-bpf-next-VM_Test-24 success Logs for x86_64-llvm-17 / test (test_maps, false, 360) / test_maps on x86_64 with llvm-17
bpf/vmtest-bpf-next-VM_Test-27 success Logs for x86_64-llvm-17 / test (test_verifier, false, 360) / test_verifier on x86_64 with llvm-17
bpf/vmtest-bpf-next-VM_Test-31 success Logs for x86_64-llvm-18 / test (test_maps, false, 360) / test_maps on x86_64 with llvm-18
bpf/vmtest-bpf-next-VM_Test-35 success Logs for x86_64-llvm-18 / test (test_verifier, false, 360) / test_verifier on x86_64 with llvm-18

Commit Message

Kumar Kartikeya Dwivedi Feb. 1, 2024, 4:21 a.m. UTC 
During runtime unwinding and cleanup, we will need to figure out where
the callee saved registers are stored on the stack, so that when a
bpf_thtrow call is made, all frames can release their callee saved
registers by finding their saved copies on the stack of callee frames.

While the previous patch ensured any BPF callee saved registers are
saved on a hidden subprog stack frame before entry into kernel (where we
would not know their location if spilled), there are cases where a
subprog's R6-R9 are not spilled into its immediate callee stack frame,
but much later in the call chain in some later callee stack frame. As
such, we would need to figure out while walking down the stack which
frames have spilled their incoming callee saved regs, and thus keep
track of where the latest spill would have happened with respect to a
given frame in the stack trace.

To perform this, we would need to know which callee saved registers are
saved by a given subprog at runtime during the unwinding phase. Right
now, there is a convenient way the x86 JIT figures this out in
detect_reg_usage. Utilize such logic in verifier core, and copy this
information to bpf_prog_aux struct before the JIT step to preserve this
information at runtime, through bpf_prog_aux.

Signed-off-by: Kumar Kartikeya Dwivedi <memxor@gmail.com>
---
 include/linux/bpf.h          |  1 +
 include/linux/bpf_verifier.h |  1 +
 kernel/bpf/verifier.c        | 10 ++++++++++
 3 files changed, 12 insertions(+)

Comments

Eduard Zingerman Feb. 15, 2024, 10:12 p.m. UTC | #1 
On Thu, 2024-02-01 at 04:21 +0000, Kumar Kartikeya Dwivedi wrote:

[...]

> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 942243cba9f1..aeaf97b0a749 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -2942,6 +2942,15 @@ static int check_subprogs(struct bpf_verifier_env *env)
>  		    insn[i].src_reg == 0 &&
>  		    insn[i].imm == BPF_FUNC_tail_call)
>  			subprog[cur_subprog].has_tail_call = true;
> +		/* Collect callee regs used in the subprog. */
> +		if (insn[i].dst_reg == BPF_REG_6 || insn[i].src_reg == BPF_REG_6)
> +			subprog[cur_subprog].callee_regs_used[0] = true;
> +		if (insn[i].dst_reg == BPF_REG_7 || insn[i].src_reg == BPF_REG_7)
> +			subprog[cur_subprog].callee_regs_used[1] = true;
> +		if (insn[i].dst_reg == BPF_REG_8 || insn[i].src_reg == BPF_REG_8)
> +			subprog[cur_subprog].callee_regs_used[2] = true;
> +		if (insn[i].dst_reg == BPF_REG_9 || insn[i].src_reg == BPF_REG_9)
> +			subprog[cur_subprog].callee_regs_used[3] = true;

Nit: Maybe move bpf_jit_comp.c:detect_reg_usage() to some place available to
     both verifier and jit? Just to keep all related code in one place.
     E.g. technically nothing prevents x86 jit to do this detection in a more
     precise manner as a "fixed point" computation.

>  		if (!env->seen_throw_insn && is_bpf_throw_kfunc(&insn[i]))
>  			env->seen_throw_insn = true;
>  		if (BPF_CLASS(code) == BPF_LD &&

[...]
Kumar Kartikeya Dwivedi Feb. 16, 2024, 10:02 p.m. UTC | #2 
On Thu, 15 Feb 2024 at 23:12, Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> On Thu, 2024-02-01 at 04:21 +0000, Kumar Kartikeya Dwivedi wrote:
>
> [...]
>
> > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> > index 942243cba9f1..aeaf97b0a749 100644
> > --- a/kernel/bpf/verifier.c
> > +++ b/kernel/bpf/verifier.c
> > @@ -2942,6 +2942,15 @@ static int check_subprogs(struct bpf_verifier_env *env)
> >                   insn[i].src_reg == 0 &&
> >                   insn[i].imm == BPF_FUNC_tail_call)
> >                       subprog[cur_subprog].has_tail_call = true;
> > +             /* Collect callee regs used in the subprog. */
> > +             if (insn[i].dst_reg == BPF_REG_6 || insn[i].src_reg == BPF_REG_6)
> > +                     subprog[cur_subprog].callee_regs_used[0] = true;
> > +             if (insn[i].dst_reg == BPF_REG_7 || insn[i].src_reg == BPF_REG_7)
> > +                     subprog[cur_subprog].callee_regs_used[1] = true;
> > +             if (insn[i].dst_reg == BPF_REG_8 || insn[i].src_reg == BPF_REG_8)
> > +                     subprog[cur_subprog].callee_regs_used[2] = true;
> > +             if (insn[i].dst_reg == BPF_REG_9 || insn[i].src_reg == BPF_REG_9)
> > +                     subprog[cur_subprog].callee_regs_used[3] = true;
>
> Nit: Maybe move bpf_jit_comp.c:detect_reg_usage() to some place available to
>      both verifier and jit? Just to keep all related code in one place.
>      E.g. technically nothing prevents x86 jit to do this detection in a more
>      precise manner as a "fixed point" computation.
>

Hm, I remember I did this and then decided against it for some reason,
but I can't remember now.
I will make this change though, if I remember why I didn't go ahead
with it, I will reply again.

Also, what did you mean by the final sentence?
Eduard Zingerman Feb. 17, 2024, 2:26 p.m. UTC | #3 
On Fri, 2024-02-16 at 23:02 +0100, Kumar Kartikeya Dwivedi wrote:
[...]

> > Nit: Maybe move bpf_jit_comp.c:detect_reg_usage() to some place available to
> >      both verifier and jit? Just to keep all related code in one place.
> >      E.g. technically nothing prevents x86 jit to do this detection in a more
> >      precise manner as a "fixed point" computation.
> > 
> 
> Hm, I remember I did this and then decided against it for some reason,
> but I can't remember now.
> I will make this change though, if I remember why I didn't go ahead
> with it, I will reply again.
> 
> Also, what did you mean by the final sentence?

Tried to give some reasoning on why x86 jit implementation might change.
On a second thought, not the best reasoning, so please ignore it.
My main point here was about duplication of the coupled code:
if one would be changed, the other would have to be changed too.
diff mbox series

Patch

diff --git a/include/linux/bpf.h b/include/linux/bpf.h
index 83cff18a1b66..4ac6add0cec8 100644
--- a/include/linux/bpf.h
+++ b/include/linux/bpf.h
@@ -1460,6 +1460,7 @@  struct bpf_prog_aux {
 	bool xdp_has_frags;
 	bool exception_cb;
 	bool exception_boundary;
+	bool callee_regs_used[4];
 	/* BTF_KIND_FUNC_PROTO for valid attach_btf_id */
 	const struct btf_type *attach_func_proto;
 	/* function name for valid attach_btf_id */
diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index 04e27fce33d6..e08ff540ec44 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -620,6 +620,7 @@  struct bpf_subprog_info {
 	u32 start; /* insn idx of function entry point */
 	u32 linfo_idx; /* The idx to the main_prog->aux->linfo */
 	u16 stack_depth; /* max. stack depth used by this function */
+	bool callee_regs_used[4];
 	bool has_tail_call: 1;
 	bool tail_call_reachable: 1;
 	bool has_ld_abs: 1;
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 942243cba9f1..aeaf97b0a749 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -2942,6 +2942,15 @@  static int check_subprogs(struct bpf_verifier_env *env)
 		    insn[i].src_reg == 0 &&
 		    insn[i].imm == BPF_FUNC_tail_call)
 			subprog[cur_subprog].has_tail_call = true;
+		/* Collect callee regs used in the subprog. */
+		if (insn[i].dst_reg == BPF_REG_6 || insn[i].src_reg == BPF_REG_6)
+			subprog[cur_subprog].callee_regs_used[0] = true;
+		if (insn[i].dst_reg == BPF_REG_7 || insn[i].src_reg == BPF_REG_7)
+			subprog[cur_subprog].callee_regs_used[1] = true;
+		if (insn[i].dst_reg == BPF_REG_8 || insn[i].src_reg == BPF_REG_8)
+			subprog[cur_subprog].callee_regs_used[2] = true;
+		if (insn[i].dst_reg == BPF_REG_9 || insn[i].src_reg == BPF_REG_9)
+			subprog[cur_subprog].callee_regs_used[3] = true;
 		if (!env->seen_throw_insn && is_bpf_throw_kfunc(&insn[i]))
 			env->seen_throw_insn = true;
 		if (BPF_CLASS(code) == BPF_LD &&
@@ -19501,6 +19510,7 @@  static int jit_subprogs(struct bpf_verifier_env *env)
 		}
 		func[i]->aux->num_exentries = num_exentries;
 		func[i]->aux->tail_call_reachable = env->subprog_info[i].tail_call_reachable;
+		memcpy(&func[i]->aux->callee_regs_used, env->subprog_info[i].callee_regs_used, sizeof(func[i]->aux->callee_regs_used));
 		func[i]->aux->exception_cb = env->subprog_info[i].is_exception_cb;
 		if (!i)
 			func[i]->aux->exception_boundary = env->seen_exception;