Skip to contentSkip to conversation

Inline bpf_get_branch_snapshot() BPF helper

PATCH Superseded Andrii Nakryiko 4 participants 7 messages Apr 2, 2024 – Apr 3, 2024

Subsystems (5)
BPF Tracing BPF core BPF tracing +1 more subsystems

v2 of 3 Superseded Latest is v3 →

lore
Share & tools
lore

Andrii Nakryiko

author maintainer
#0 lore raw

v2 cover Inline bpf_get_branch_snapshot() BPF helper

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/[email protected]/

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(-)
Signature · 1 line
2.43.0
author maintainer
#1 lore raw

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

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/[email protected]/

---
 kernel/trace/bpf_trace.c | 4 ----
 1 file changed, 4 deletions(-)
kernel/trace/bpf_trace.c +0 -4
index 6d0c95638e1b..afb232b1d7c2 100644
@@ -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 = {
Signature · 1 line
2.43.0
author maintainer
#2 lore raw

PATCH v2 2/2 bpf: inline bpf_get_branch_snapshot() helper

In reply to 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.

---
 kernel/bpf/verifier.c | 55 +++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 55 insertions(+)
kernel/bpf/verifier.c +55 -0
index fcb62300f407..49789da56f4b 100644
@@ -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 &&
Signature · 1 line
2.43.0
#3 lore raw

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

Quoted 43 lines · 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.

---
 kernel/bpf/verifier.c | 55 +++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 55 insertions(+)
kernel/bpf/verifier.c +19 -0
index fcb62300f407..49789da56f4b 100644
@@ -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).

kernel/bpf/verifier.c static int do_misc_fixups(struct bpf_verifier_env *env) · line 20188

Quoted 10 lines
kernel/bpf/verifier.c +10 -0
+                        * 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

Quoted 32 lines
kernel/bpf/verifier.c +26 -1
+                       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

reviewer Acked-by
#4 lore raw

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

Quoted 44 lines · Andrii Nakryiko
Quoted 43 lines · 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.

---
 kernel/bpf/verifier.c | 55 +++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 55 insertions(+)
kernel/bpf/verifier.c +19 -0
index fcb62300f407..49789da56f4b 100644
@@ -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).
Quoted 8 lines

kernel/bpf/verifier.c static int do_misc_fixups(struct bpf_verifier_env *env) · line 20186

Quoted 8 lines
kernel/bpf/verifier.c +8 -0
+                        * 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.

Quoted 12 lines

kernel/bpf/verifier.c static int do_misc_fixups(struct bpf_verifier_env *env) · line 20188

Quoted 2 lines
kernel/bpf/verifier.c +2 -0
+                       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,

Quoted 34 lines
Quoted 33 lines
kernel/bpf/verifier.c +26 -1
+                       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

#5 lore raw

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

In reply to Andrii Nakryiko
Quoted 31 lines · 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.

---
 kernel/bpf/verifier.c | 55 +++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 55 insertions(+)
kernel/bpf/verifier.c +7 -0
index fcb62300f407..49789da56f4b 100644
@@ -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);
+                        */

kernel/bpf/verifier.c static int do_misc_fixups(struct bpf_verifier_env *env) · line 20176

Quoted 10 lines
kernel/bpf/verifier.c +10 -0
+                       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.

Quoted 44 lines
kernel/bpf/verifier.c +38 -1
+
+                       /* 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

#6 lore raw

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

Quoted 38 lines · Alexei Starovoitov
Quoted 36 lines · 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.

---
 kernel/bpf/verifier.c | 55 +++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 55 insertions(+)
kernel/bpf/verifier.c +12 -0
index fcb62300f407..49789da56f4b 100644
@@ -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
Quoted 8 lines

kernel/bpf/verifier.c static int do_misc_fixups(struct bpf_verifier_env *env) · line 20176

Quoted 5 lines
kernel/bpf/verifier.c +5 -0
+                        */
+                       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.

Quoted 45 lines
Quoted 45 lines
kernel/bpf/verifier.c +38 -1
+
+                       /* 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