[PATCH v2 bpf-next 0/2] Inline bpf_get_branch_snapshot() BPF helper

[PATCH v2 bpf-next 0/2] Inline bpf_get_branch_snapshot() BPF helper

[Andrii Nakryiko]

Implement inlining of bpf_get_branch_snapshot() BPF helper using generic BPF
assembly approach. This allows to reduce LBR record usage right before LBR
records are captured from inside BPF program.

See v1 cover letter ([0]) for some visual examples. I dropped them from v2
because there are multiple independent changes landing and being reviewed, all
of which remove different parts of LBR record waste, so presenting final state
of LBR "waste" gets more complicated until all of the pieces land.

  [0] https://lore.kernel.org/bpf/20240321180501.734779-1-andrii@kernel.org/

v1->v2:
  - inlining of bpf_get_smp_processor_id() split out into a separate patch set
    implementing internal per-CPU BPF instruction;
  - add efficient divide-by-24 through multiplication logic, and leave
    comments to explain the idea behind it; this way inlined version of
    bpf_get_branch_snapshot() has no compromises compared to non-inlined
    version of the helper  (Alexei).

Andrii Nakryiko (2):
  bpf: make bpf_get_branch_snapshot() architecture-agnostic
  bpf: inline bpf_get_branch_snapshot() helper

 kernel/bpf/verifier.c    | 55 ++++++++++++++++++++++++++++++++++++++++
 kernel/trace/bpf_trace.c |  4 ---
 2 files changed, 55 insertions(+), 4 deletions(-)

-- 
2.43.0

[PATCH v2 bpf-next 1/2] bpf: make bpf_get_branch_snapshot() architecture-agnostic

[Andrii Nakryiko]

perf_snapshot_branch_stack is set up in an architecture-agnostic way, so
there is no reason for BPF subsystem to keep track of which
architectures do support LBR or not. E.g., it looks like ARM64 might soon
get support for BRBE ([0]), which (with proper integration) should be
possible to utilize using this BPF helper.

perf_snapshot_branch_stack static call will point to
__static_call_return0() by default, which just returns zero, which will
lead to -ENOENT, as expected. So no need to guard anything here.

  [0] https://lore.kernel.org/linux-arm-kernel/20240125094119.2542332-1-anshuman.khandual@arm.com/

Signed-off-by: Andrii Nakryiko <andrii@kernel.org>
---
 kernel/trace/bpf_trace.c | 4 ----
 1 file changed, 4 deletions(-)

diff --git a/kernel/trace/bpf_trace.c b/kernel/trace/bpf_trace.c
index 6d0c95638e1b..afb232b1d7c2 100644
--- a/kernel/trace/bpf_trace.c
+++ b/kernel/trace/bpf_trace.c
@@ -1188,9 +1188,6 @@ static const struct bpf_func_proto bpf_get_attach_cookie_proto_tracing = {
 
 BPF_CALL_3(bpf_get_branch_snapshot, void *, buf, u32, size, u64, flags)
 {
-#ifndef CONFIG_X86
-	return -ENOENT;
-#else
 	static const u32 br_entry_size = sizeof(struct perf_branch_entry);
 	u32 entry_cnt = size / br_entry_size;
 
@@ -1203,7 +1200,6 @@ BPF_CALL_3(bpf_get_branch_snapshot, void *, buf, u32, size, u64, flags)
 		return -ENOENT;
 
 	return entry_cnt * br_entry_size;
-#endif
 }
 
 static const struct bpf_func_proto bpf_get_branch_snapshot_proto = {
-- 
2.43.0

[PATCH v2 bpf-next 2/2] bpf: inline bpf_get_branch_snapshot() helper

[Andrii Nakryiko]

Inline bpf_get_branch_snapshot() helper using architecture-agnostic
inline BPF code which calls directly into underlying callback of
perf_snapshot_branch_stack static call. This callback is set early
during kernel initialization and is never updated or reset, so it's ok
to fetch actual implementation using static_call_query() and call
directly into it.

This change eliminates a full function call and saves one LBR entry
in PERF_SAMPLE_BRANCH_ANY LBR mode.

Signed-off-by: Andrii Nakryiko <andrii@kernel.org>
---
 kernel/bpf/verifier.c | 55 +++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 55 insertions(+)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index fcb62300f407..49789da56f4b 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -20157,6 +20157,61 @@ static int do_misc_fixups(struct bpf_verifier_env *env)
 			goto next_insn;
 		}
 
+		/* Implement bpf_get_branch_snapshot inline. */
+		if (prog->jit_requested && BITS_PER_LONG == 64 &&
+		    insn->imm == BPF_FUNC_get_branch_snapshot) {
+			/* We are dealing with the following func protos:
+			 * u64 bpf_get_branch_snapshot(void *buf, u32 size, u64 flags);
+			 * int perf_snapshot_branch_stack(struct perf_branch_entry *entries, u32 cnt);
+			 */
+			const u32 br_entry_size = sizeof(struct perf_branch_entry);
+
+			/* struct perf_branch_entry is part of UAPI and is
+			 * used as an array element, so extremely unlikely to
+			 * ever grow or shrink
+			 */
+			BUILD_BUG_ON(br_entry_size != 24);
+
+			/* if (unlikely(flags)) return -EINVAL */
+			insn_buf[0] = BPF_JMP_IMM(BPF_JNE, BPF_REG_3, 0, 7);
+
+			/* Transform size (bytes) into number of entries (cnt = size / 24).
+			 * But to avoid expensive division instruction, we implement
+			 * divide-by-3 through multiplication, followed by further
+			 * division by 8 through 3-bit right shift.
+			 * Refer to book "Hacker's Delight, 2nd ed." by Henry S. Warren, Jr.,
+			 * p. 227, chapter "Unsigned Divison by 3" for details and proofs.
+			 *
+			 * N / 3 <=> M * N / 2^33, where M = (2^33 + 1) / 3 = 0xaaaaaaab.
+			 */
+			insn_buf[1] = BPF_MOV32_IMM(BPF_REG_0, 0xaaaaaaab);
+			insn_buf[2] = BPF_ALU64_REG(BPF_REG_2, BPF_REG_0, 0);
+			insn_buf[3] = BPF_ALU64_IMM(BPF_RSH, BPF_REG_2, 36);
+
+			/* call perf_snapshot_branch_stack implementation */
+			insn_buf[4] = BPF_EMIT_CALL(static_call_query(perf_snapshot_branch_stack));
+			/* if (entry_cnt == 0) return -ENOENT */
+			insn_buf[5] = BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 4);
+			/* return entry_cnt * sizeof(struct perf_branch_entry) */
+			insn_buf[6] = BPF_ALU32_IMM(BPF_MUL, BPF_REG_0, br_entry_size);
+			insn_buf[7] = BPF_JMP_A(3);
+			/* return -EINVAL; */
+			insn_buf[8] = BPF_MOV64_IMM(BPF_REG_0, -EINVAL);
+			insn_buf[9] = BPF_JMP_A(1);
+			/* return -ENOENT; */
+			insn_buf[10] = BPF_MOV64_IMM(BPF_REG_0, -ENOENT);
+			cnt = 11;
+
+			new_prog = bpf_patch_insn_data(env, i + delta, insn_buf, cnt);
+			if (!new_prog)
+				return -ENOMEM;
+
+			delta    += cnt - 1;
+			env->prog = prog = new_prog;
+			insn      = new_prog->insnsi + i + delta;
+			continue;
+		}
+
 		/* Implement bpf_kptr_xchg inline */
 		if (prog->jit_requested && BITS_PER_LONG == 64 &&
 		    insn->imm == BPF_FUNC_kptr_xchg &&
-- 
2.43.0

Re: [PATCH v2 bpf-next 2/2] bpf: inline bpf_get_branch_snapshot() helper

[Andrii Nakryiko]

On Tue, Apr 2, 2024 at 12:05 PM Andrii Nakryiko <andrii@kernel.org> wrote:
>
> Inline bpf_get_branch_snapshot() helper using architecture-agnostic
> inline BPF code which calls directly into underlying callback of
> perf_snapshot_branch_stack static call. This callback is set early
> during kernel initialization and is never updated or reset, so it's ok
> to fetch actual implementation using static_call_query() and call
> directly into it.
>
> This change eliminates a full function call and saves one LBR entry
> in PERF_SAMPLE_BRANCH_ANY LBR mode.
>
> Signed-off-by: Andrii Nakryiko <andrii@kernel.org>
> ---
>  kernel/bpf/verifier.c | 55 +++++++++++++++++++++++++++++++++++++++++++
>  1 file changed, 55 insertions(+)
>
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index fcb62300f407..49789da56f4b 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -20157,6 +20157,61 @@ static int do_misc_fixups(struct bpf_verifier_env *env)
>                         goto next_insn;
>                 }
>
> +               /* Implement bpf_get_branch_snapshot inline. */
> +               if (prog->jit_requested && BITS_PER_LONG == 64 &&
> +                   insn->imm == BPF_FUNC_get_branch_snapshot) {
> +                       /* We are dealing with the following func protos:
> +                        * u64 bpf_get_branch_snapshot(void *buf, u32 size, u64 flags);
> +                        * int perf_snapshot_branch_stack(struct perf_branch_entry *entries, u32 cnt);
> +                        */
> +                       const u32 br_entry_size = sizeof(struct perf_branch_entry);
> +
> +                       /* struct perf_branch_entry is part of UAPI and is
> +                        * used as an array element, so extremely unlikely to
> +                        * ever grow or shrink
> +                        */
> +                       BUILD_BUG_ON(br_entry_size != 24);
> +
> +                       /* if (unlikely(flags)) return -EINVAL */
> +                       insn_buf[0] = BPF_JMP_IMM(BPF_JNE, BPF_REG_3, 0, 7);
> +
> +                       /* Transform size (bytes) into number of entries (cnt = size / 24).
> +                        * But to avoid expensive division instruction, we implement
> +                        * divide-by-3 through multiplication, followed by further
> +                        * division by 8 through 3-bit right shift.
> +                        * Refer to book "Hacker's Delight, 2nd ed." by Henry S. Warren, Jr.,
> +                        * p. 227, chapter "Unsigned Divison by 3" for details and proofs.
> +                        *
> +                        * N / 3 <=> M * N / 2^33, where M = (2^33 + 1) / 3 = 0xaaaaaaab.
> +                        */
> +                       insn_buf[1] = BPF_MOV32_IMM(BPF_REG_0, 0xaaaaaaab);
> +                       insn_buf[2] = BPF_ALU64_REG(BPF_REG_2, BPF_REG_0, 0);

Doh, this should be:

insn_buf[2] = BPF_ALU64_REG(BPF_MUL, BPF_REG_2, BPF_REG_0);

I'll wait a bit for any other feedback, will retest everything on real
hardware again, and will submit v2 tomorrow.

pw-bot: cr


> +                       insn_buf[3] = BPF_ALU64_IMM(BPF_RSH, BPF_REG_2, 36);
> +
> +                       /* call perf_snapshot_branch_stack implementation */
> +                       insn_buf[4] = BPF_EMIT_CALL(static_call_query(perf_snapshot_branch_stack));
> +                       /* if (entry_cnt == 0) return -ENOENT */
> +                       insn_buf[5] = BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 4);
> +                       /* return entry_cnt * sizeof(struct perf_branch_entry) */
> +                       insn_buf[6] = BPF_ALU32_IMM(BPF_MUL, BPF_REG_0, br_entry_size);
> +                       insn_buf[7] = BPF_JMP_A(3);
> +                       /* return -EINVAL; */
> +                       insn_buf[8] = BPF_MOV64_IMM(BPF_REG_0, -EINVAL);
> +                       insn_buf[9] = BPF_JMP_A(1);
> +                       /* return -ENOENT; */
> +                       insn_buf[10] = BPF_MOV64_IMM(BPF_REG_0, -ENOENT);
> +                       cnt = 11;
> +
> +                       new_prog = bpf_patch_insn_data(env, i + delta, insn_buf, cnt);
> +                       if (!new_prog)
> +                               return -ENOMEM;
> +
> +                       delta    += cnt - 1;
> +                       env->prog = prog = new_prog;
> +                       insn      = new_prog->insnsi + i + delta;
> +                       continue;
> +               }
> +
>                 /* Implement bpf_kptr_xchg inline */
>                 if (prog->jit_requested && BITS_PER_LONG == 64 &&
>                     insn->imm == BPF_FUNC_kptr_xchg &&
> --
> 2.43.0
>

Re: [PATCH v2 bpf-next 2/2] bpf: inline bpf_get_branch_snapshot() helper

[Alexei Starovoitov]

On Tue, Apr 2, 2024 at 12:05 PM Andrii Nakryiko <andrii@kernel.org> wrote:
>
> Inline bpf_get_branch_snapshot() helper using architecture-agnostic
> inline BPF code which calls directly into underlying callback of
> perf_snapshot_branch_stack static call. This callback is set early
> during kernel initialization and is never updated or reset, so it's ok
> to fetch actual implementation using static_call_query() and call
> directly into it.
>
> This change eliminates a full function call and saves one LBR entry
> in PERF_SAMPLE_BRANCH_ANY LBR mode.
>
> Signed-off-by: Andrii Nakryiko <andrii@kernel.org>
> ---
>  kernel/bpf/verifier.c | 55 +++++++++++++++++++++++++++++++++++++++++++
>  1 file changed, 55 insertions(+)
>
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index fcb62300f407..49789da56f4b 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -20157,6 +20157,61 @@ static int do_misc_fixups(struct bpf_verifier_env *env)
>                         goto next_insn;
>                 }
>
> +               /* Implement bpf_get_branch_snapshot inline. */
> +               if (prog->jit_requested && BITS_PER_LONG == 64 &&
> +                   insn->imm == BPF_FUNC_get_branch_snapshot) {
> +                       /* We are dealing with the following func protos:
> +                        * u64 bpf_get_branch_snapshot(void *buf, u32 size, u64 flags);
> +                        * int perf_snapshot_branch_stack(struct perf_branch_entry *entries, u32 cnt);
> +                        */
> +                       const u32 br_entry_size = sizeof(struct perf_branch_entry);
> +
> +                       /* struct perf_branch_entry is part of UAPI and is
> +                        * used as an array element, so extremely unlikely to
> +                        * ever grow or shrink
> +                        */
> +                       BUILD_BUG_ON(br_entry_size != 24);
> +
> +                       /* if (unlikely(flags)) return -EINVAL */
> +                       insn_buf[0] = BPF_JMP_IMM(BPF_JNE, BPF_REG_3, 0, 7);

optimizing this out with is_reg_const(R3) is probably overkill?
Just mentioning in case you need to skip this branch.

> +
> +                       /* Transform size (bytes) into number of entries (cnt = size / 24).
> +                        * But to avoid expensive division instruction, we implement
> +                        * divide-by-3 through multiplication, followed by further
> +                        * division by 8 through 3-bit right shift.
> +                        * Refer to book "Hacker's Delight, 2nd ed." by Henry S. Warren, Jr.,
> +                        * p. 227, chapter "Unsigned Divison by 3" for details and proofs.
> +                        *
> +                        * N / 3 <=> M * N / 2^33, where M = (2^33 + 1) / 3 = 0xaaaaaaab.
> +                        */
> +                       insn_buf[1] = BPF_MOV32_IMM(BPF_REG_0, 0xaaaaaaab);
> +                       insn_buf[2] = BPF_ALU64_REG(BPF_REG_2, BPF_REG_0, 0);
> +                       insn_buf[3] = BPF_ALU64_IMM(BPF_RSH, BPF_REG_2, 36);
> +
> +                       /* call perf_snapshot_branch_stack implementation */
> +                       insn_buf[4] = BPF_EMIT_CALL(static_call_query(perf_snapshot_branch_stack));
> +                       /* if (entry_cnt == 0) return -ENOENT */
> +                       insn_buf[5] = BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 4);
> +                       /* return entry_cnt * sizeof(struct perf_branch_entry) */
> +                       insn_buf[6] = BPF_ALU32_IMM(BPF_MUL, BPF_REG_0, br_entry_size);
> +                       insn_buf[7] = BPF_JMP_A(3);
> +                       /* return -EINVAL; */
> +                       insn_buf[8] = BPF_MOV64_IMM(BPF_REG_0, -EINVAL);
> +                       insn_buf[9] = BPF_JMP_A(1);
> +                       /* return -ENOENT; */
> +                       insn_buf[10] = BPF_MOV64_IMM(BPF_REG_0, -ENOENT);
> +                       cnt = 11;
> +
> +                       new_prog = bpf_patch_insn_data(env, i + delta, insn_buf, cnt);
> +                       if (!new_prog)
> +                               return -ENOMEM;
> +
> +                       delta    += cnt - 1;
> +                       env->prog = prog = new_prog;
> +                       insn      = new_prog->insnsi + i + delta;
> +                       continue;
> +               }
> +
>                 /* Implement bpf_kptr_xchg inline */
>                 if (prog->jit_requested && BITS_PER_LONG == 64 &&
>                     insn->imm == BPF_FUNC_kptr_xchg &&
> --
> 2.43.0
>

Re: [PATCH v2 bpf-next 2/2] bpf: inline bpf_get_branch_snapshot() helper

[Andrii Nakryiko]

On Wed, Apr 3, 2024 at 10:51 AM Alexei Starovoitov
<alexei.starovoitov@gmail.com> wrote:
>
> On Tue, Apr 2, 2024 at 12:05 PM Andrii Nakryiko <andrii@kernel.org> wrote:
> >
> > Inline bpf_get_branch_snapshot() helper using architecture-agnostic
> > inline BPF code which calls directly into underlying callback of
> > perf_snapshot_branch_stack static call. This callback is set early
> > during kernel initialization and is never updated or reset, so it's ok
> > to fetch actual implementation using static_call_query() and call
> > directly into it.
> >
> > This change eliminates a full function call and saves one LBR entry
> > in PERF_SAMPLE_BRANCH_ANY LBR mode.
> >
> > Signed-off-by: Andrii Nakryiko <andrii@kernel.org>
> > ---
> >  kernel/bpf/verifier.c | 55 +++++++++++++++++++++++++++++++++++++++++++
> >  1 file changed, 55 insertions(+)
> >
> > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> > index fcb62300f407..49789da56f4b 100644
> > --- a/kernel/bpf/verifier.c
> > +++ b/kernel/bpf/verifier.c
> > @@ -20157,6 +20157,61 @@ static int do_misc_fixups(struct bpf_verifier_env *env)
> >                         goto next_insn;
> >                 }
> >
> > +               /* Implement bpf_get_branch_snapshot inline. */
> > +               if (prog->jit_requested && BITS_PER_LONG == 64 &&
> > +                   insn->imm == BPF_FUNC_get_branch_snapshot) {
> > +                       /* We are dealing with the following func protos:
> > +                        * u64 bpf_get_branch_snapshot(void *buf, u32 size, u64 flags);
> > +                        * int perf_snapshot_branch_stack(struct perf_branch_entry *entries, u32 cnt);
> > +                        */
> > +                       const u32 br_entry_size = sizeof(struct perf_branch_entry);
> > +
> > +                       /* struct perf_branch_entry is part of UAPI and is
> > +                        * used as an array element, so extremely unlikely to
> > +                        * ever grow or shrink
> > +                        */
> > +                       BUILD_BUG_ON(br_entry_size != 24);
> > +
> > +                       /* if (unlikely(flags)) return -EINVAL */
> > +                       insn_buf[0] = BPF_JMP_IMM(BPF_JNE, BPF_REG_3, 0, 7);
>
> optimizing this out with is_reg_const(R3) is probably overkill?
> Just mentioning in case you need to skip this branch.

probably an overkill, we'd need to make sure that any code path has R3
as constant zero.

Also note that these not taken branches don't pollute even the most
detailed PERF_SAMPLE_BRANCH_ANY mode, CPU only records non-linear code
execution changes, so it's fine from my perspective.

>
> > +
> > +                       /* Transform size (bytes) into number of entries (cnt = size / 24).
> > +                        * But to avoid expensive division instruction, we implement
> > +                        * divide-by-3 through multiplication, followed by further
> > +                        * division by 8 through 3-bit right shift.
> > +                        * Refer to book "Hacker's Delight, 2nd ed." by Henry S. Warren, Jr.,
> > +                        * p. 227, chapter "Unsigned Divison by 3" for details and proofs.
> > +                        *
> > +                        * N / 3 <=> M * N / 2^33, where M = (2^33 + 1) / 3 = 0xaaaaaaab.
> > +                        */
> > +                       insn_buf[1] = BPF_MOV32_IMM(BPF_REG_0, 0xaaaaaaab);
> > +                       insn_buf[2] = BPF_ALU64_REG(BPF_REG_2, BPF_REG_0, 0);
> > +                       insn_buf[3] = BPF_ALU64_IMM(BPF_RSH, BPF_REG_2, 36);
> > +
> > +                       /* call perf_snapshot_branch_stack implementation */
> > +                       insn_buf[4] = BPF_EMIT_CALL(static_call_query(perf_snapshot_branch_stack));
> > +                       /* if (entry_cnt == 0) return -ENOENT */
> > +                       insn_buf[5] = BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 4);
> > +                       /* return entry_cnt * sizeof(struct perf_branch_entry) */
> > +                       insn_buf[6] = BPF_ALU32_IMM(BPF_MUL, BPF_REG_0, br_entry_size);
> > +                       insn_buf[7] = BPF_JMP_A(3);
> > +                       /* return -EINVAL; */
> > +                       insn_buf[8] = BPF_MOV64_IMM(BPF_REG_0, -EINVAL);
> > +                       insn_buf[9] = BPF_JMP_A(1);
> > +                       /* return -ENOENT; */
> > +                       insn_buf[10] = BPF_MOV64_IMM(BPF_REG_0, -ENOENT);
> > +                       cnt = 11;
> > +
> > +                       new_prog = bpf_patch_insn_data(env, i + delta, insn_buf, cnt);
> > +                       if (!new_prog)
> > +                               return -ENOMEM;
> > +
> > +                       delta    += cnt - 1;
> > +                       env->prog = prog = new_prog;
> > +                       insn      = new_prog->insnsi + i + delta;
> > +                       continue;
> > +               }
> > +
> >                 /* Implement bpf_kptr_xchg inline */
> >                 if (prog->jit_requested && BITS_PER_LONG == 64 &&
> >                     insn->imm == BPF_FUNC_kptr_xchg &&
> > --
> > 2.43.0
> >

Re: [PATCH v2 bpf-next 2/2] bpf: inline bpf_get_branch_snapshot() helper

[John Fastabend]

Andrii Nakryiko wrote:
> On Tue, Apr 2, 2024 at 12:05 PM Andrii Nakryiko <andrii@kernel.org> wrote:
> >
> > Inline bpf_get_branch_snapshot() helper using architecture-agnostic
> > inline BPF code which calls directly into underlying callback of
> > perf_snapshot_branch_stack static call. This callback is set early
> > during kernel initialization and is never updated or reset, so it's ok
> > to fetch actual implementation using static_call_query() and call
> > directly into it.
> >
> > This change eliminates a full function call and saves one LBR entry
> > in PERF_SAMPLE_BRANCH_ANY LBR mode.
> >
> > Signed-off-by: Andrii Nakryiko <andrii@kernel.org>
> > ---
> >  kernel/bpf/verifier.c | 55 +++++++++++++++++++++++++++++++++++++++++++
> >  1 file changed, 55 insertions(+)
> >
> > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> > index fcb62300f407..49789da56f4b 100644
> > --- a/kernel/bpf/verifier.c
> > +++ b/kernel/bpf/verifier.c
> > @@ -20157,6 +20157,61 @@ static int do_misc_fixups(struct bpf_verifier_env *env)
> >                         goto next_insn;
> >                 }
> >
> > +               /* Implement bpf_get_branch_snapshot inline. */
> > +               if (prog->jit_requested && BITS_PER_LONG == 64 &&
> > +                   insn->imm == BPF_FUNC_get_branch_snapshot) {
> > +                       /* We are dealing with the following func protos:
> > +                        * u64 bpf_get_branch_snapshot(void *buf, u32 size, u64 flags);
> > +                        * int perf_snapshot_branch_stack(struct perf_branch_entry *entries, u32 cnt);
> > +                        */
> > +                       const u32 br_entry_size = sizeof(struct perf_branch_entry);
> > +
> > +                       /* struct perf_branch_entry is part of UAPI and is
> > +                        * used as an array element, so extremely unlikely to
> > +                        * ever grow or shrink
> > +                        */
> > +                       BUILD_BUG_ON(br_entry_size != 24);
> > +
> > +                       /* if (unlikely(flags)) return -EINVAL */
> > +                       insn_buf[0] = BPF_JMP_IMM(BPF_JNE, BPF_REG_3, 0, 7);
> > +
> > +                       /* Transform size (bytes) into number of entries (cnt = size / 24).
> > +                        * But to avoid expensive division instruction, we implement
> > +                        * divide-by-3 through multiplication, followed by further
> > +                        * division by 8 through 3-bit right shift.
> > +                        * Refer to book "Hacker's Delight, 2nd ed." by Henry S. Warren, Jr.,
> > +                        * p. 227, chapter "Unsigned Divison by 3" for details and proofs.
> > +                        *
> > +                        * N / 3 <=> M * N / 2^33, where M = (2^33 + 1) / 3 = 0xaaaaaaab.
> > +                        */

Nice bit of magic. Thanks for the reference.

> > +                       insn_buf[1] = BPF_MOV32_IMM(BPF_REG_0, 0xaaaaaaab);
> > +                       insn_buf[2] = BPF_ALU64_REG(BPF_REG_2, BPF_REG_0, 0);
> 
> Doh, this should be:
> 
> insn_buf[2] = BPF_ALU64_REG(BPF_MUL, BPF_REG_2, BPF_REG_0);
> 
> I'll wait a bit for any other feedback, will retest everything on real
> hardware again, and will submit v2 tomorrow.
> 
> pw-bot: cr
> 

LGTM. With above fix,

Acked-by: John Fastabend <john.fastabend@gmail.com>

> 
> > +                       insn_buf[3] = BPF_ALU64_IMM(BPF_RSH, BPF_REG_2, 36);
> > +
> > +                       /* call perf_snapshot_branch_stack implementation */
> > +                       insn_buf[4] = BPF_EMIT_CALL(static_call_query(perf_snapshot_branch_stack));
> > +                       /* if (entry_cnt == 0) return -ENOENT */
> > +                       insn_buf[5] = BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 4);
> > +                       /* return entry_cnt * sizeof(struct perf_branch_entry) */
> > +                       insn_buf[6] = BPF_ALU32_IMM(BPF_MUL, BPF_REG_0, br_entry_size);
> > +                       insn_buf[7] = BPF_JMP_A(3);
> > +                       /* return -EINVAL; */
> > +                       insn_buf[8] = BPF_MOV64_IMM(BPF_REG_0, -EINVAL);
> > +                       insn_buf[9] = BPF_JMP_A(1);
> > +                       /* return -ENOENT; */
> > +                       insn_buf[10] = BPF_MOV64_IMM(BPF_REG_0, -ENOENT);
> > +                       cnt = 11;
> > +
> > +                       new_prog = bpf_patch_insn_data(env, i + delta, insn_buf, cnt);
> > +                       if (!new_prog)
> > +                               return -ENOMEM;
> > +
> > +                       delta    += cnt - 1;
> > +                       env->prog = prog = new_prog;
> > +                       insn      = new_prog->insnsi + i + delta;
> > +                       continue;
> > +               }
> > +
> >                 /* Implement bpf_kptr_xchg inline */
> >                 if (prog->jit_requested && BITS_PER_LONG == 64 &&
> >                     insn->imm == BPF_FUNC_kptr_xchg &&
> > --
> > 2.43.0
> >
>