Skip to contentSkip to conversation

bpf: Replace bpf_patch_insn_data() with a list of deferred patches

PATCH In review Qiliang Yuan 4 participants 32 messages Oct 30 – Oct 31

Subsystems (4)
lore
Share & tools
lore
#0 lore raw

v2 cover bpf: Replace bpf_patch_insn_data() with a list of deferred patches

bpf_patch_insn_data() and bpf_patch_insn_single() apply a patch right
away: they move the tail of the instruction and aux data arrays and walk the whole program to fix up branches and every table that names instructions. Removing instructions works the same way.

A pass that patches M instructions of an N instruction program does O(N * M) work. Eduard pointed out that this takes a large share of the time to load pyperf180 [1], and with bpf_jit_harden=2 or many nops to remove it gets to minutes.

Replace them with a list that a pass fills with patches and commits once in O(N + inserted instructions). Following the layout of Jiong's RFC [2], the list goes to core.c and the verifier side to fixups.c, then each pass moves over and the last patch removes the old code. As Andrii suggested there, map every old index to a new one once and relocate all jumps through that map. Since passes queue patches in increasing order of the instruction they replace, keep the list in a sorted array instead of a linked list.

  1-3   the patch list in core.c and in the verifier
  4-6   bpf_do_misc_fixups(), gotol for a backward may_goto
  7-9   removal of instructions, dead code and nops
  10    zext

11-13 patching an instruction twice, inserting in front of one 14-17 ctx accesses, may_goto counter setup, hidden subprog, bpf_loop() 18-19 commit without a verifier env, constant blinding
20 removal of the old code
21-22 selftests

Load times on an x86_64 VM with 32 vCPUs, the base commit below with and without the series, measured in one round: perf stat -r30 -- veristat -q <obj> averaged over two runs, -r10 for BPF_F_TEST_RND_HI32 and bpf_jit_harden=2, three runs of loading 131072 "ja 0":

base patched

  pyperf180                       0.512 s    0.350 s
  pyperf600                       1.407 s    0.885 s
  strobemeta                      0.591 s    0.588 s
  test_verif_scale2               0.643 s    0.646 s
  pyperf180, BPF_F_TEST_RND_HI32  1.708 s    0.360 s
  pyperf600, BPF_F_TEST_RND_HI32  5.161 s    0.891 s
  pyperf180, bpf_jit_harden=2     3.185 s    0.362 s
  pyperf600, bpf_jit_harden=2     9.879 s    0.899 s
  131072 "ja 0" removed          53.146 s    0.769 s

With bpf_jit_harden=2, test_verifier's "ld_dw: xor semi-random 64 bit imms, test 5" doesn't load within 900 s on base and loads in 5 s with the series.

For the 1052 objects of the selftests, every program that loads has the same xlated code, line info and func info on both kernels, by default, with BPF_F_TEST_RND_HI32 and with bpf_jit_harden=2, masking the immediates that hold addresses, BTF ids and blinding constants. test_verifier passes on both, test_bpf fails the same 53 tests on both when hardened, and test_progs only shows failures that are flaky in parallel runs.

[1] https://lore.kernel.org/bpf/[email protected]/
[2] https://lore.kernel.org/bpf/[email protected]/

---
V1 -> V2:
- Convert every pass and remove the old patching code (Alexei)
- Build the new image in core.c, so that blinding without a verifier env uses the list too
- Let the list remove instructions, insert in front of one and patch one twice
- Pick JEQ or gotol for a backward may_goto from its offset grown by the patches in between, v1 picked JEQ when that offset was -32768 (CI bot)
- Test a backward may_goto expanded to gotol
- Test a jump that the patches push out of its 16-bit range, and a gotox to a patched insn
- Rebase onto current bpf-next, which adds the arena_scalar rewrite

v1: https://lore.kernel.org/r/[email protected]

---
Qiliang Yuan (22):
bpf: Add a list of deferred instruction patches
bpf: Remap the verifier state through the patch list
bpf: Apply single-instruction patches of the verifier in place
bpf: Queue the rewrites of bpf_do_misc_fixups()
bpf: Expand a backward may_goto to gotol when patches push it out of range
bpf: Drop the constant delta from bpf_do_misc_fixups()
bpf: Let the patch list remove instructions
bpf: Remove dead code through the patch list
bpf: Strip nops through the patch list
bpf: Batch the patches of bpf_opt_subreg_zext_lo32_rnd_hi32()
bpf: Allow patching an instruction twice through the patch list
bpf: Teach the patch list to insert in front of an instruction
bpf: Allow inserting in front of a queued patch
bpf: Move bpf_convert_ctx_accesses() to the patch list
bpf: Insert the may_goto counter setup through the patch list
bpf: Append the hidden subprog through the patch list
bpf: Inline bpf_loop() calls through the patch list
bpf: Apply the patch list without a verifier env
bpf: Blind constants through the patch list
bpf: Remove the old instruction patching code
selftests/bpf: Test jumps around patches of bpf_do_misc_fixups() selftests/bpf: Cover a backward may_goto pushed out of range by patches

 include/linux/bpf.h                                |    4 +-
 include/linux/bpf_verifier.h                       |   87 +-
 include/linux/filter.h                             |   16 -
 kernel/bpf/bpf_insn_array.c                        |   35 +-
 kernel/bpf/core.c                                  |  552 ++++++---
 kernel/bpf/fixups.c                                | 1285 +++++++++-----------
 kernel/bpf/verifier.c                              |   46 +-
 tools/testing/selftests/bpf/prog_tests/verifier.c  |    2 +
 .../selftests/bpf/progs/verifier_patch_list.c      |  210 ++++
 9 files changed, 1240 insertions(+), 997 deletions(-)

---
base-commit: 7101b10cf281f629ac58c99697ca6f6d082b99a7
change-id: 20261001-bpf-verifier-patch-batch-2442080e837d

Best regards,

Signature · 1 line
Qiliang Yuan <[email protected]>
#1 lore raw

PATCH v2 1/22 bpf: Add a list of deferred instruction patches

bpf_patch_insn_data() and bpf_patch_insn_single() apply a patch right away. They move the tail of the program and walk all of it to fix up the branches and everything else that names an instruction.

A pass that patches M instructions of an N instruction program does O(N * M) work. pyperf180 from the selftests has 930 bpf_map_lookup_elem() calls on hash maps, and inlining each of them into 3 instructions of its 24k instruction program takes about a fifth of the time to load it.

Add a list of patches that a rewrite queues against the unpatched program, in increasing order of the instruction they replace, and build the patched image from it in O(N + inserted instructions). Map each old index to the first instruction of its patch, as bpf_patch_insn_data() names a patched instruction, and relocate every jump that leaves its patch through that map. Build the image aside, so that a jump that gets out of range leaves the program untouched, and move the poke descriptors and the line info along when installing it. Keep all of this in core.c without a verifier env, so that rewrites without one can use it too.

---
 include/linux/bpf_verifier.h |  47 ++++++++++
 kernel/bpf/core.c            | 213 +++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 260 insertions(+)
include/linux/bpf_verifier.h +47 -0
index 5926f13ff43cc..a56a996b3d953 100644
@@ -1060,6 +1060,53 @@ struct bpf_fd_array {
 	};
 };
 
+/* one deferred patch: insn 'off' is replaced by 'len' insns */
+struct bpf_insn_patch {
+	u32 off;
+	u32 len;
+	u32 start;		/* first insn of the patch in bpf_patch_list.insns */
+	struct bpf_insn orig;	/* the replaced insn when the patch was queued */
+};
+
+/*
+ * Patches queued by a rewrite pass, applied together by
+ * bpf_patch_list_commit() in O(prog->len + inserted insns).
+ */
+struct bpf_patch_list {
+	struct bpf_insn_patch *patches;
+	struct bpf_insn *insns;
+	u32 cnt;
+	u32 cap;
+	u32 insn_cnt;
+	u32 insn_cap;
+};
+
+/* the image of a program with the queued patches applied, see bpf_patch_list_build() */
+struct bpf_patch_image {
+	struct bpf_insn *insns;
+	u32 *new_off;
+	u32 cnt;
+	u32 new_cnt;
+	s32 grow;
+	u32 bad;
+};
+
+/* Map an offset in the old program, which may be past its end. */
+static inline u32 bpf_patch_image_remap(const struct bpf_patch_image *img,
+					const u32 *map, u32 off)
+{
+	return off <= img->cnt ? map[off] : off + img->grow;
+}
+
+struct bpf_insn *__bpf_patch_list_add(struct bpf_patch_list *pl,
+				      const struct bpf_prog *prog, u32 off,
+				      const struct bpf_insn *patch, u32 len);
+void bpf_patch_list_release(struct bpf_patch_list *pl);
+int bpf_patch_list_build(const struct bpf_patch_list *pl, const struct bpf_prog *prog,
+			 struct bpf_patch_image *img);
+void bpf_patch_image_free(struct bpf_patch_image *img);
+void bpf_patch_image_install(struct bpf_prog *prog, const struct bpf_patch_image *img);
+
 /* single container for all structs
  * one verifier_env per bpf_check() call
  */
kernel/bpf/core.c +213 -0

219 lines not on this page · raw message

Signature · 1 line
2.43.0
#2 lore raw

PATCH v2 2/22 bpf: Remap the verifier state through the patch list

In reply to Qiliang Yuan

Besides the program, the verifier keeps aux data for every instruction and tables that name instructions: subprog starts, function pointers and instruction arrays. bpf_patch_insn_data() fixes all of them up with each patch.

The image that the patch list builds leaves them behind, so verifier passes can't queue their patches on it yet.

Add bpf_patch_list_add() and bpf_patch_list_commit(), which keep the list in the verifier env. Install the new image on commit and move the aux data, the subprog starts, the function pointers and the instruction arrays along with it, filling in the aux data of patched instructions the way adjust_insn_aux_data() does. Allocate everything before installing the image, so that a failure leaves the program and the env as they were.

---
 include/linux/bpf.h          |   1 +
 include/linux/bpf_verifier.h |   5 ++
 kernel/bpf/bpf_insn_array.c  |  18 ++++++
 kernel/bpf/fixups.c          | 151 +++++++++++++++++++++++++++++++++++++++++++
 kernel/bpf/verifier.c        |   1 +
 5 files changed, 176 insertions(+)
include/linux/bpf.h +1 -0
index 580f89c450b55..9bb5e0c823627 100644
@@ -4378,6 +4378,7 @@ int bpf_insn_array_ready(struct bpf_map *map);
 void bpf_insn_array_release(struct bpf_map *map);
 void bpf_insn_array_adjust(struct bpf_map *map, u32 first, u32 len);
 void bpf_insn_array_adjust_after_remove(struct bpf_map *map, u32 off, u32 len);
+void bpf_insn_array_remap(struct bpf_map *map, const u32 *new_off, u32 cnt, s32 grow);
 
 #ifdef CONFIG_BPF_SYSCALL
 void bpf_prog_update_insn_ptrs(struct bpf_prog *prog, u32 *offsets, void *image);
include/linux/bpf_verifier.h +5 -0
index a56a996b3d953..49a6e443de75d 100644
@@ -1154,6 +1154,7 @@ struct bpf_verifier_env {
 	bool signature;
 	u32 insn_aux_data_len;
 	struct bpf_insn_aux_data *insn_aux_data; /* array of per-insn state */
+	struct bpf_patch_list patch_list;
 	const struct bpf_line_info *prev_linfo;
 	struct bpf_verifier_log log;
 	struct bpf_diag *diag;
@@ -2061,6 +2062,10 @@ int bpf_jit_subprogs(struct bpf_verifier_env *env);
 int bpf_fixup_call_args(struct bpf_verifier_env *env);
 int bpf_do_misc_fixups(struct bpf_verifier_env *env);
 int bpf_insn_def32(struct bpf_prog *prog, struct bpf_insn *insn);
+struct bpf_insn *bpf_patch_list_add(struct bpf_verifier_env *env, u32 off,
+				    const struct bpf_insn *patch, u32 len);
+int bpf_patch_list_commit(struct bpf_verifier_env *env);
+void bpf_patch_list_free(struct bpf_verifier_env *env);
 
 int bpf_flip_opcode(u32 opcode);
 u8 bpf_rev_opcode(u8 opcode);
kernel/bpf/bpf_insn_array.c +18 -0
index 92bbb71576ae3..dbfcf1eddb91e 100644
@@ -253,6 +253,24 @@ void bpf_insn_array_adjust(struct bpf_map *map, u32 first, u32 len)
 	}
 }
 
+/*
+ * Move each offset to new_off[offset], new_off[] covers [0, cnt]. Offsets
+ * past the end of the old program only move by 'grow'.
+ */
+void bpf_insn_array_remap(struct bpf_map *map, const u32 *new_off, u32 cnt, s32 grow)
+{
+	struct bpf_insn_array *insn_array = cast_insn_array(map);
+	u32 off;
+	int i;
+
+	for (i = 0; i < map->max_entries; i++) {
+		off = insn_array->values[i].xlated_off;
+		if (off == INSN_DELETED)
+			continue;
+		insn_array->values[i].xlated_off = off <= cnt ? new_off[off] : off + grow;
+	}
+}
+
 void bpf_insn_array_adjust_after_remove(struct bpf_map *map, u32 off, u32 len)
 {
 	struct bpf_insn_array *insn_array = cast_insn_array(map);
kernel/bpf/fixups.c +151 -0

157 lines not on this page · raw message

kernel/bpf/verifier.c +1 -0
index 5601d20562186..b6b120bf5433c 100644
@@ -24158,6 +24158,7 @@ int bpf_check(struct bpf_prog **prog, union bpf_attr *attr, bpfptr_t uattr,
 	if (env->insn_aux_data)
 		bpf_clear_insn_aux_data(env, 0, env->insn_aux_data_len);
 	vfree(env->insn_aux_data);
+	bpf_patch_list_free(env);
 	kvfree(env->fd_array);
 	bpf_free_scev(env);
 	bpf_stack_liveness_free(env);
Signature · 1 line
2.43.0
#3 lore raw

Re: [PATCH bpf-next v2 02/22] bpf: Remap the verifier state through the patch list

TL;DR: patch_list_adj_aux() may clear indirect_target for single-instruction patches, so a gotox target could lose its ENDBR/BTI landing pad on IBT/BTI kernels. Latent for now, as there are no…
Quoted 1 line

bpf: Remap the verifier state through the patch list

TL;DR: patch_list_adj_aux() may clear indirect_target for single-instruction patches, so a gotox target could lose its ENDBR/BTI landing pad on IBT/BTI kernels. Latent for now, as there are no callers yet; the comment and changelog are also inaccurate.

Quoted 5 lines
kernel/bpf/fixups.c +0 -0
index f062ef7dd943..0697f66b1ffc 100644
@@ -380,6 +380,157 @@ struct bpf_prog *bpf_patch_insn_data(struct bpf_verifier_env *env, u32 off,

[ ... ]

Quoted 14 lines
kernel/bpf/fixups.c +14 -0
+/*
+ * Fill the aux data of the 'p->len' insns at 'slot' from the aux data 'old'
+ * of the insn they replace, the same way as adjust_insn_aux_data() does.
+ */
+static void patch_list_adj_aux(struct bpf_prog *prog, struct bpf_insn_patch *p,
+			       struct bpf_insn *patch,
+			       const struct bpf_insn_aux_data *old,
+			       struct bpf_insn_aux_data *slot)
+{
+	struct bpf_insn_aux_data *last = slot + p->len - 1;
+	struct bpf_insn *orig = &p->orig;
+	u32 i;
+
+	*last = *old;

[ ... ]

kernel/bpf/fixups.c struct bpf_prog *bpf_patch_insn_data(struct bpf_verifier_env *env, u32 off, · line 445

Quoted 6 lines
kernel/bpf/fixups.c +6 -0
+	/* indirect jumps to the replaced insn land on the first new one */
+	if (last->indirect_target) {
+		slot[0].indirect_target = 1;
+		last->indirect_target = 0;
+	}
+}

For a single-instruction patch (p->len == 1), 'last' is 'slot + p->len - 1', which is 'slot'. Can this block clear the flag it just set?

    slot[0].indirect_target = 1;
    last->indirect_target = 0;     /* last == &slot[0] */

bpf_patch_list_add() only rejects !len, so len == 1 patches are accepted. An instruction that is the target of an indirect jump (gotox) would lose its indirect_target flag when it is replaced one-for-one.

adjust_insn_aux_data() does not behave this way. For cnt == 1 it takes the early return and leaves indirect_target alone.

bpf_insn_is_indirect_target() hands this flag to the JITs, and x86 do_jit() emits ENDBR and arm64 build_insn() emits 'BTI J' only for flagged instructions. An indirect jump to an unflagged instruction would then hit a missing landing pad on IBT/BTI-enabled kernels.

The len == 1 path also treats non_stack_access differently. It keeps the old marking, while adjust_insn_aux_data() recomputes it with bpf_is_mem_insn(insn + off).

So the comment above patch_list_adj_aux() ("the same way as adjust_insn_aux_data() does") and the commit message line "filling in the aux data of patched instructions the way adjust_insn_aux_data() does" do not hold for single-instruction patches.

This looks latent in this commit. bpf_patch_list_add() and bpf_patch_list_commit() have no callers here, and in the series the next commit a3a12f55a1ad ("bpf: Apply single-instruction patches of the verifier in place") applies len == 1 patches in place before any caller exists. The first callers arrive in a9b03b9b8596 ("bpf: Queue the rewrites of bpf_do_misc_fixups()"), and 3c859182c47c ("bpf: Teach the patch list to insert in front of an instruction") later adds a 'p->target != p->len - 1' guard to this block.

Would it make sense to fold a3a12f55a1ad into this commit, so the helper is correct on its own and its comment and the changelog are accurate?

---
AI reviewed your patch. Please fix the bug or email reply why it's not a bug.
See: https://github.com/kernel-patches/vmtest/blob/master/ci/claude/README.md

CI run summary: https://github.com/kernel-patches/bpf/actions/runs/41053659762

#4 lore raw

PATCH v2 3/22 bpf: Apply single-instruction patches of the verifier in place

In reply to Qiliang Yuan

bpf_patch_insn_data() replaces one instruction by one in place, and only sets non_stack_access of its aux data from whether the new instruction accesses memory.

bpf_patch_list_add() queues such a patch like any other, although it moves nothing, and the commit fills in its aux data the way it does for a longer patch, which keeps non_stack_access of the old instruction where bpf_patch_insn_data() recomputes it.

Write a patch of a single instruction to the program right away and adjust its aux data with adjust_insn_aux_data(), as bpf_patch_insn_data() does.

---
 kernel/bpf/fixups.c | 10 +++++++++-
 1 file changed, 9 insertions(+), 1 deletion(-)
kernel/bpf/fixups.c +9 -1
index 0697f66b1ffc1..a0dd582312d86 100644
@@ -382,7 +382,8 @@ struct bpf_prog *bpf_patch_insn_data(struct bpf_verifier_env *env, u32 off,
 
 /*
  * Queue the replacement of insn 'off' by 'patch[0..len)' until
- * bpf_patch_list_commit(), see __bpf_patch_list_add().
+ * bpf_patch_list_commit(), see __bpf_patch_list_add(). Replacing one insn by
+ * one moves nothing and is done right away.
  */
 struct bpf_insn *bpf_patch_list_add(struct bpf_verifier_env *env, u32 off,
 				    const struct bpf_insn *patch, u32 len)
@@ -397,6 +398,13 @@ struct bpf_insn *bpf_patch_list_add(struct bpf_verifier_env *env, u32 off,
 			    env, "insn %u patched out of order", off))
 		return ERR_PTR(-EFAULT);
 
+	if (len == 1) {
+		env->prog->insnsi[off] = *patch;
+		adjust_insn_aux_data(env, env->prog, off, 1, NULL,
+				     BPF_PATCH_KEEP_TARGET);
+		return &env->prog->insnsi[off];
+	}
+
 	return __bpf_patch_list_add(pl, env->prog, off, patch, len);
 }
 
Signature · 1 line
2.43.0
#5 lore raw

PATCH v2 4/22 bpf: Queue the rewrites of bpf_do_misc_fixups()

In reply to Qiliang Yuan

Each rewrite in the main loop of bpf_do_misc_fixups() patches the program right away with bpf_patch_insn_data().

Every rewrite moves the tail of the program and walks all of it, which costs O(prog->len) each time.

Queue the rewrites with bpf_patch_list_add() and commit them once the loop is done, before the stack of subprogs is initialized for may_goto. Walk the unpatched program, so that delta stays 0, and derive insn from the index at the end of each iteration, so that a rewrite that fixes up a helper call after queueing it can go on to patch_call_imm with insn pointing to the queued copy.

perf stat -r30 -- veristat -q <obj>, average of two runs, x86_64 VM with 32 vCPUs, before and after this patch:

              before     after
  pyperf180   0.507 s    0.348 s
  pyperf600   1.406 s    0.887 s
---
 kernel/bpf/fixups.c | 239 +++++++++++++++++-----------------------------------
 1 file changed, 75 insertions(+), 164 deletions(-)
kernel/bpf/fixups.c +75 -164
index a0dd582312d86..c9963d8d81356 100644
@@ -2042,14 +2042,9 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env)
 		if (env->insn_aux_data[i + delta].arena_scalar) {
 			cnt = arena_scalar_access(insn, insn_buf);
 
-			new_prog = bpf_patch_insn_data(env, i + delta, insn_buf, cnt);
-			if (!new_prog)
-				return -ENOMEM;
-
-			delta += cnt - 1;
-			prog = new_prog;
-			env->prog = prog;
-			insn = prog->insnsi + i + delta;
+			insn = bpf_patch_list_add(env, i + delta, insn_buf, cnt);
+			if (IS_ERR(insn))
+				return PTR_ERR(insn);
 			goto next_insn;
 		}
 
@@ -2072,13 +2067,9 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env)
 
 			cnt = patch - insn_buf;
 
-			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;
+			insn = bpf_patch_list_add(env, i + delta, insn_buf, cnt);
+			if (IS_ERR(insn))
+				return PTR_ERR(insn);
 			goto next_insn;
 		}
 
@@ -2163,13 +2154,9 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env)
 				cnt = patch - insn_buf;
 			}
 
-			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;
+			insn = bpf_patch_list_add(env, i + delta, insn_buf, cnt);
+			if (IS_ERR(insn))
+				return PTR_ERR(insn);
 			goto next_insn;
 		}
 
@@ -2193,13 +2180,9 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env)
 			*patch++ = BPF_MOV64_IMM(insn->dst_reg, 0);
 
 			cnt = patch - insn_buf;
-			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;
+			insn = bpf_patch_list_add(env, i + delta, insn_buf, cnt);
+			if (IS_ERR(insn))
+				return PTR_ERR(insn);
 			goto next_insn;
 		}
 
@@ -2213,13 +2196,9 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env)
 				return -EFAULT;
 			}
 
-			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;
+			insn = bpf_patch_list_add(env, i + delta, insn_buf, cnt);
+			if (IS_ERR(insn))
+				return PTR_ERR(insn);
 			goto next_insn;
 		}
 
@@ -2266,13 +2245,9 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env)
 				*patch++ = BPF_ALU64_IMM(BPF_MUL, off_reg, -1);
 			cnt = patch - insn_buf;
 
-			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;
+			insn = bpf_patch_list_add(env, i + delta, insn_buf, cnt);
+			if (IS_ERR(insn))
+				return PTR_ERR(insn);
 			goto next_insn;
 		}
 
@@ -2309,13 +2284,9 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env)
 			cnt = may_goto_expand(insn_buf, insn->off, stack_off_cnt,
 					      tail, ARRAY_SIZE(tail));
 
-			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;
+			insn = bpf_patch_list_add(env, i + delta, insn_buf, cnt);
+			if (IS_ERR(insn))
+				return PTR_ERR(insn);
 			goto next_insn;
 		} else if (bpf_is_may_goto_insn(insn)) {
 			int stack_off = -stack_depth - 8;
@@ -2328,13 +2299,9 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env)
 			cnt = may_goto_expand(insn_buf, insn->off, stack_off,
 					      tail, ARRAY_SIZE(tail));
 
-			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;
+			insn = bpf_patch_list_add(env, i + delta, insn_buf, cnt);
+			if (IS_ERR(insn))
+				return PTR_ERR(insn);
 			goto next_insn;
 		}
 
@@ -2365,13 +2332,9 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env)
 			cnt = 2;
 
 			i++;
-			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;
+			insn = bpf_patch_list_add(env, i + delta, insn_buf, cnt);
+			if (IS_ERR(insn))
+				return PTR_ERR(insn);
 			goto next_insn;
 		}
 
@@ -2386,13 +2349,9 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env)
 			if (cnt == 0)
 				goto next_insn;
 
-			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;
+			insn = bpf_patch_list_add(env, i + delta, insn_buf, cnt);
+			if (IS_ERR(insn))
+				return PTR_ERR(insn);
 			goto next_insn;
 		}
 
@@ -2477,13 +2436,9 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env)
 								 map)->index_mask);
 			insn_buf[2] = *insn;
 			cnt = 3;
-			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;
+			insn = bpf_patch_list_add(env, i + delta, insn_buf, cnt);
+			if (IS_ERR(insn))
+				return PTR_ERR(insn);
 			goto next_insn;
 		}
 
@@ -2511,13 +2466,9 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env)
 			insn_buf[2] = *insn;
 			cnt = 3;
 
-			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;
+			insn = bpf_patch_list_add(env, i + delta, insn_buf, cnt);
+			if (IS_ERR(insn))
+				return PTR_ERR(insn);
 			goto patch_call_imm;
 		}
 
@@ -2530,13 +2481,9 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env)
 			insn_buf[1] = *insn;
 			cnt = 2;
 
-			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;
+			insn = bpf_patch_list_add(env, i + delta, insn_buf, cnt);
+			if (IS_ERR(insn))
+				return PTR_ERR(insn);
 			goto patch_call_imm;
 		}
 
@@ -2573,14 +2520,9 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env)
 				if (bpf_map_is_percpu_map(map_ptr->map_type))
 					prog->jit_required = true;
 
-				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;
+				insn = bpf_patch_list_add(env, i + delta, insn_buf, cnt);
+				if (IS_ERR(insn))
+					return PTR_ERR(insn);
 				goto next_insn;
 			}
 
@@ -2656,14 +2598,9 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env)
 						  BPF_REG_0, 0);
 			cnt = 3;
 
-			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;
+			insn = bpf_patch_list_add(env, i + delta, insn_buf, cnt);
+			if (IS_ERR(insn))
+				return PTR_ERR(insn);
 			goto next_insn;
 		}
 
@@ -2686,13 +2623,9 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env)
 			insn_buf[0] = BPF_ALU32_REG(BPF_XOR, BPF_REG_0, BPF_REG_0);
 			cnt = 1;
 #endif
-			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;
+			insn = bpf_patch_list_add(env, i + delta, insn_buf, cnt);
+			if (IS_ERR(insn))
+				return PTR_ERR(insn);
 			goto next_insn;
 		}
 
@@ -2705,13 +2638,9 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env)
 			insn_buf[2] = BPF_LDX_MEM(BPF_DW, BPF_REG_0, BPF_REG_0, 0);
 			cnt = 3;
 
-			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;
+			insn = bpf_patch_list_add(env, i + delta, insn_buf, cnt);
+			if (IS_ERR(insn))
+				return PTR_ERR(insn);
 			goto next_insn;
 		}
 #endif
@@ -2739,13 +2668,9 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env)
 			insn_buf[cnt++] = BPF_JMP_A(1);
 			insn_buf[cnt++] = BPF_MOV64_IMM(BPF_REG_0, -EINVAL);
 
-			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;
+			insn = bpf_patch_list_add(env, i + delta, insn_buf, cnt);
+			if (IS_ERR(insn))
+				return PTR_ERR(insn);
 			goto next_insn;
 		}
 
@@ -2771,13 +2696,9 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env)
 				cnt = 1;
 			}
 
-			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;
+			insn = bpf_patch_list_add(env, i + delta, insn_buf, cnt);
+			if (IS_ERR(insn))
+				return PTR_ERR(insn);
 			goto next_insn;
 		}
 
@@ -2797,13 +2718,9 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env)
 				cnt = 2;
 			}
 
-			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;
+			insn = bpf_patch_list_add(env, i + delta, insn_buf, cnt);
+			if (IS_ERR(insn))
+				return PTR_ERR(insn);
 			goto next_insn;
 		}
 
@@ -2813,12 +2730,9 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env)
 			/* Load IP address from ctx - 16 */
 			insn_buf[0] = BPF_LDX_MEM(BPF_DW, BPF_REG_0, BPF_REG_1, -16);
 
-			new_prog = bpf_patch_insn_data(env, i + delta, insn_buf, 1);
-			if (!new_prog)
-				return -ENOMEM;
-
-			env->prog = prog = new_prog;
-			insn      = new_prog->insnsi + i + delta;
+			insn = bpf_patch_list_add(env, i + delta, insn_buf, 1);
+			if (IS_ERR(insn))
+				return PTR_ERR(insn);
 			goto next_insn;
 		}
 
@@ -2868,13 +2782,9 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env)
 			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;
+			insn = bpf_patch_list_add(env, i + delta, insn_buf, cnt);
+			if (IS_ERR(insn))
+				return PTR_ERR(insn);
 			goto next_insn;
 		}
 
@@ -2886,13 +2796,9 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env)
 			insn_buf[1] = BPF_ATOMIC_OP(BPF_DW, BPF_XCHG, BPF_REG_1, BPF_REG_0, 0);
 			cnt = 2;
 
-			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;
+			insn = bpf_patch_list_add(env, i + delta, insn_buf, cnt);
+			if (IS_ERR(insn))
+				return PTR_ERR(insn);
 			goto next_insn;
 		}
 patch_call_imm:
@@ -2923,9 +2829,14 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env)
 			stack_depth_extra = 0;
 		}
 		i++;
-		insn++;
+		insn = &prog->insnsi[i + delta];
 	}
 
+	ret = bpf_patch_list_commit(env);
+	if (ret)
+		return ret;
+	prog = env->prog;
+
 	env->prog->aux->stack_depth = subprogs[0].stack_depth;
 	for (i = 0; i < env->subprog_cnt; i++) {
 		int delta = bpf_jit_supports_timed_may_goto() ? 2 : 1;
Signature · 1 line
2.43.0
#6 lore raw

PATCH v2 5/22 bpf: Expand a backward may_goto to gotol when patches push it out of range

In reply to Qiliang Yuan

may_goto_expand() turns may_goto into a conditional jump with a 16-bit offset, or into gotol when the offset of may_goto doesn't fit in 16 bits.

bpf_do_misc_fixups() picks the jump from the offset of may_goto in the unpatched program. When the patches queued between a backward may_goto and its target push the offset out of the 16-bit range, the commit fails with -ERANGE, as bpf_patch_insn_data() did before when applying those patches.

Add the growth of the patches queued between a backward may_goto and its target to its offset, and use gotol when the result doesn't fit in 16 bits.

---
 kernel/bpf/fixups.c | 38 +++++++++++++++++++++++++++++++-------
 1 file changed, 31 insertions(+), 7 deletions(-)
kernel/bpf/fixups.c +31 -7
index c9963d8d81356..1d281428acbb3 100644
@@ -1968,16 +1968,21 @@ static int add_hidden_subprog(struct bpf_verifier_env *env, struct bpf_insn *pat
  * may_goto when it is zero, then the tail that updates the count.
  * Use gotol when the target is too far for 16-bit offset of a conditional jump.
  */
-static int may_goto_expand(struct bpf_insn *insn_buf, int off, int stack_off,
-			   const struct bpf_insn *tail, int tail_cnt)
+/*
+ * 'off' is the offset of may_goto, 'reach' how far it jumps once the patches
+ * in between are applied, which decides whether a 16-bit jump will do.
+ */
+static int may_goto_expand(struct bpf_insn *insn_buf, int off, int reach,
+			   int stack_off, const struct bpf_insn *tail, int tail_cnt)
 {
 	int cnt = 0;
 
 	/* Forward jump has to step over the tail */
 	off = off >= 0 ? off + tail_cnt : off - 1;
+	reach = reach >= 0 ? reach + tail_cnt : reach - 1;
 
 	insn_buf[cnt++] = BPF_LDX_MEM(BPF_DW, BPF_REG_AX, BPF_REG_10, stack_off);
-	if (off == (s16)off) {
+	if (reach == (s16)reach) {
 		insn_buf[cnt++] = BPF_JMP_IMM(BPF_JEQ, BPF_REG_AX, 0, off);
 	} else {
 		insn_buf[cnt++] = BPF_JMP_IMM(BPF_JNE, BPF_REG_AX, 0, 1);
@@ -1987,6 +1992,23 @@ static int may_goto_expand(struct bpf_insn *insn_buf, int off, int stack_off,
 	return cnt + tail_cnt;
 }
 
+/* The offset of may_goto at 'idx' once the patches queued in front are applied. */
+static int may_goto_off(struct bpf_verifier_env *env, const struct bpf_insn *insn,
+			u32 idx)
+{
+	struct bpf_patch_list *pl = &env->patch_list;
+	u32 tgt = idx + insn->off + 1;
+	int off = insn->off;
+	u32 k = pl->cnt;
+
+	if (off >= 0)
+		return off;
+	/* all queued patches are in front of idx */
+	while (k > 0 && pl->patches[k - 1].off >= tgt)
+		off -= pl->patches[--k].len - 1;
+	return off;
+}
+
 /* Do various post-verification rewrites in a single program pass.
  * These rewrites simplify JIT and interpreter implementations.
  */
@@ -2281,8 +2303,9 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env)
 			 * after subtraction, rinse and repeat.
 			 */
 			stack_depth_extra = 16;
-			cnt = may_goto_expand(insn_buf, insn->off, stack_off_cnt,
-					      tail, ARRAY_SIZE(tail));
+			cnt = may_goto_expand(insn_buf, insn->off,
+					      may_goto_off(env, insn, i + delta),
+					      stack_off_cnt, tail, ARRAY_SIZE(tail));
 
 			insn = bpf_patch_list_add(env, i + delta, insn_buf, cnt);
 			if (IS_ERR(insn))
@@ -2296,8 +2319,9 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env)
 			};
 
 			stack_depth_extra = 8;
-			cnt = may_goto_expand(insn_buf, insn->off, stack_off,
-					      tail, ARRAY_SIZE(tail));
+			cnt = may_goto_expand(insn_buf, insn->off,
+					      may_goto_off(env, insn, i + delta),
+					      stack_off, tail, ARRAY_SIZE(tail));
 
 			insn = bpf_patch_list_add(env, i + delta, insn_buf, cnt);
 			if (IS_ERR(insn))
Signature · 1 line
2.43.0
#7 lore raw

Re: [PATCH bpf-next v2 05/22] bpf: Expand a backward may_goto to gotol when patches push it out of range

TL;DR: Nits only: the new may_goto_expand() comment on 'reach' overstates coverage, since forward jumps are still unadjusted, and it detaches the older function comment.
Quoted 1 line

bpf: Expand a backward may_goto to gotol when patches push it out of range

TL;DR: Nits only: the new may_goto_expand() comment on 'reach' overstates coverage, since forward jumps are still unadjusted, and it detaches the older function comment.

Quoted 6 lines
kernel/bpf/fixups.c +0 -0
index c9963d8d8135..1d281428acbb 100644
@@ -1968,16 +1968,21 @@ static int add_hidden_subprog(struct bpf_verifier_env *env, struct bpf_insn *pat
  * may_goto when it is zero, then the tail that updates the count.

kernel/bpf/fixups.c static int add_hidden_subprog(struct bpf_verifier_env *env, struct bpf_insn *pat · line 1976

Quoted 10 lines
kernel/bpf/fixups.c +6 -2
  * Use gotol when the target is too far for 16-bit offset of a conditional jump.
  */
-static int may_goto_expand(struct bpf_insn *insn_buf, int off, int stack_off,
-			   const struct bpf_insn *tail, int tail_cnt)
+/*
+ * 'off' is the offset of may_goto, 'reach' how far it jumps once the patches
+ * in between are applied, which decides whether a 16-bit jump will do.
+ */
+static int may_goto_expand(struct bpf_insn *insn_buf, int off, int reach,
+			   int stack_off, const struct bpf_insn *tail, int tail_cnt)

This isn't a bug, but the new comment says 'reach' is how far may_goto jumps once the patches in between are applied. Does that hold for forward jumps?

may_goto_off() returns the unpatched offset for them:

	if (off >= 0)
		return off;

so reach == off for a forward may_goto, and a forward may_goto that later patches push past S16_MAX still gets a 16-bit JEQ. That then fails in bpf_patch_list_commit() -> patch_list_adj_insn() -> insn_set_rel() with -ERANGE, the same as before this patch.

Could the comment say that 'reach' only accounts for the patches already queued, so only backward jumps are covered?

Also, the new comment block sits directly below the existing comment for may_goto_expand(), which leaves the older comment detached from the function it describes. Could the two be merged into one?

Quoted 14 lines
kernel/bpf/fixups.c +2 -1
 {
 	int cnt = 0;
 
 	/* Forward jump has to step over the tail */
 	off = off >= 0 ? off + tail_cnt : off - 1;
+	reach = reach >= 0 ? reach + tail_cnt : reach - 1;
 
 	insn_buf[cnt++] = BPF_LDX_MEM(BPF_DW, BPF_REG_AX, BPF_REG_10, stack_off);
-	if (off == (s16)off) {
+	if (reach == (s16)reach) {
 		insn_buf[cnt++] = BPF_JMP_IMM(BPF_JEQ, BPF_REG_AX, 0, off);
 	} else {
 		insn_buf[cnt++] = BPF_JMP_IMM(BPF_JNE, BPF_REG_AX, 0, 1);

kernel/bpf/fixups.c static int may_goto_expand(struct bpf_insn *insn_buf, int off, int stack_off, · line 1993

Quoted 2 lines
kernel/bpf/fixups.c +0 -0
@@ -1987,6 +1992,23 @@ static int may_goto_expand(struct bpf_insn *insn_buf, int off, int stack_off,
 	return cnt + tail_cnt;
 }

[ ... ]

---
AI reviewed your patch. Please fix the bug or email reply why it's not a bug.
See: https://github.com/kernel-patches/vmtest/blob/master/ci/claude/README.md

CI run summary: https://github.com/kernel-patches/bpf/actions/runs/41053659762

#8 lore raw

PATCH v2 6/22 bpf: Drop the constant delta from bpf_do_misc_fixups()

In reply to Qiliang Yuan

bpf_do_misc_fixups() counts in delta how far the patches moved the instruction that it handles, and indexes instructions and aux data with i + delta.

Nothing changes the program while the loop walks it anymore, so delta is always 0.

Remove delta and index by i alone.

---
 kernel/bpf/fixups.c | 76 ++++++++++++++++++++++++++---------------------------
 1 file changed, 38 insertions(+), 38 deletions(-)
kernel/bpf/fixups.c +38 -38
index 1d281428acbb3..940265cb80ebf 100644
@@ -2025,7 +2025,7 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env)
 	struct bpf_insn *insn_buf = env->insn_buf;
 	struct bpf_prog *new_prog;
 	struct bpf_map *map_ptr;
-	int i, ret, cnt, delta = 0, cur_subprog = 0;
+	int i, ret, cnt, cur_subprog = 0;
 	struct bpf_subprog_info *subprogs = env->subprog_info;
 	u16 stack_depth = subprogs[cur_subprog].stack_depth;
 	u16 stack_depth_extra = 0;
@@ -2057,14 +2057,14 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env)
 			goto next_insn;
 		}
 
-		if (env->insn_aux_data[i + delta].needs_zext)
+		if (env->insn_aux_data[i].needs_zext)
 			/* Convert BPF_CLASS(insn->code) == BPF_ALU64 to 32-bit ALU */
 			insn->code = BPF_ALU | BPF_OP(insn->code) | BPF_SRC(insn->code);
 
-		if (env->insn_aux_data[i + delta].arena_scalar) {
+		if (env->insn_aux_data[i].arena_scalar) {
 			cnt = arena_scalar_access(insn, insn_buf);
 
-			insn = bpf_patch_list_add(env, i + delta, insn_buf, cnt);
+			insn = bpf_patch_list_add(env, i, insn_buf, cnt);
 			if (IS_ERR(insn))
 				return PTR_ERR(insn);
 			goto next_insn;
@@ -2089,7 +2089,7 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env)
 
 			cnt = patch - insn_buf;
 
-			insn = bpf_patch_list_add(env, i + delta, insn_buf, cnt);
+			insn = bpf_patch_list_add(env, i, insn_buf, cnt);
 			if (IS_ERR(insn))
 				return PTR_ERR(insn);
 			goto next_insn;
@@ -2176,7 +2176,7 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env)
 				cnt = patch - insn_buf;
 			}
 
-			insn = bpf_patch_list_add(env, i + delta, insn_buf, cnt);
+			insn = bpf_patch_list_add(env, i, insn_buf, cnt);
 			if (IS_ERR(insn))
 				return PTR_ERR(insn);
 			goto next_insn;
@@ -2202,7 +2202,7 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env)
 			*patch++ = BPF_MOV64_IMM(insn->dst_reg, 0);
 
 			cnt = patch - insn_buf;
-			insn = bpf_patch_list_add(env, i + delta, insn_buf, cnt);
+			insn = bpf_patch_list_add(env, i, insn_buf, cnt);
 			if (IS_ERR(insn))
 				return PTR_ERR(insn);
 			goto next_insn;
@@ -2218,7 +2218,7 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env)
 				return -EFAULT;
 			}
 
-			insn = bpf_patch_list_add(env, i + delta, insn_buf, cnt);
+			insn = bpf_patch_list_add(env, i, insn_buf, cnt);
 			if (IS_ERR(insn))
 				return PTR_ERR(insn);
 			goto next_insn;
@@ -2233,7 +2233,7 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env)
 			bool issrc, isneg, isimm;
 			u32 off_reg;
 
-			aux = &env->insn_aux_data[i + delta];
+			aux = &env->insn_aux_data[i];
 			if (!aux->alu_state ||
 			    aux->alu_state == BPF_ALU_NON_POINTER)
 				goto next_insn;
@@ -2267,7 +2267,7 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env)
 				*patch++ = BPF_ALU64_IMM(BPF_MUL, off_reg, -1);
 			cnt = patch - insn_buf;
 
-			insn = bpf_patch_list_add(env, i + delta, insn_buf, cnt);
+			insn = bpf_patch_list_add(env, i, insn_buf, cnt);
 			if (IS_ERR(insn))
 				return PTR_ERR(insn);
 			goto next_insn;
@@ -2304,10 +2304,10 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env)
 			 */
 			stack_depth_extra = 16;
 			cnt = may_goto_expand(insn_buf, insn->off,
-					      may_goto_off(env, insn, i + delta),
+					      may_goto_off(env, insn, i),
 					      stack_off_cnt, tail, ARRAY_SIZE(tail));
 
-			insn = bpf_patch_list_add(env, i + delta, insn_buf, cnt);
+			insn = bpf_patch_list_add(env, i, insn_buf, cnt);
 			if (IS_ERR(insn))
 				return PTR_ERR(insn);
 			goto next_insn;
@@ -2320,10 +2320,10 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env)
 
 			stack_depth_extra = 8;
 			cnt = may_goto_expand(insn_buf, insn->off,
-					      may_goto_off(env, insn, i + delta),
+					      may_goto_off(env, insn, i),
 					      stack_off, tail, ARRAY_SIZE(tail));
 
-			insn = bpf_patch_list_add(env, i + delta, insn_buf, cnt);
+			insn = bpf_patch_list_add(env, i, insn_buf, cnt);
 			if (IS_ERR(insn))
 				return PTR_ERR(insn);
 			goto next_insn;
@@ -2335,7 +2335,7 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env)
 		     insn->src_reg == BPF_PSEUDO_MAP_IDX_VALUE)) {
 			struct bpf_map *map;
 
-			aux = &env->insn_aux_data[i + delta];
+			aux = &env->insn_aux_data[i];
 			map = env->used_maps[aux->map_index];
 			if (map->map_type != BPF_MAP_TYPE_PERCPU_ARRAY)
 				goto next_insn;
@@ -2356,7 +2356,7 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env)
 			cnt = 2;
 
 			i++;
-			insn = bpf_patch_list_add(env, i + delta, insn_buf, cnt);
+			insn = bpf_patch_list_add(env, i, insn_buf, cnt);
 			if (IS_ERR(insn))
 				return PTR_ERR(insn);
 			goto next_insn;
@@ -2367,13 +2367,13 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env)
 		if (insn->src_reg == BPF_PSEUDO_CALL)
 			goto next_insn;
 		if (insn->src_reg == BPF_PSEUDO_KFUNC_CALL) {
-			ret = bpf_fixup_kfunc_call(env, insn, insn_buf, i + delta, &cnt);
+			ret = bpf_fixup_kfunc_call(env, insn, insn_buf, i, &cnt);
 			if (ret)
 				return ret;
 			if (cnt == 0)
 				goto next_insn;
 
-			insn = bpf_patch_list_add(env, i + delta, insn_buf, cnt);
+			insn = bpf_patch_list_add(env, i, insn_buf, cnt);
 			if (IS_ERR(insn))
 				return PTR_ERR(insn);
 			goto next_insn;
@@ -2414,7 +2414,7 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env)
 			insn->imm = 0;
 			insn->code = BPF_JMP | BPF_TAIL_CALL;
 
-			aux = &env->insn_aux_data[i + delta];
+			aux = &env->insn_aux_data[i];
 			if (env->bpf_capable && !prog->blinding_requested &&
 			    prog->jit_requested &&
 			    !bpf_map_key_poisoned(aux) &&
@@ -2424,7 +2424,7 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env)
 					.reason = BPF_POKE_REASON_TAIL_CALL,
 					.tail_call.map = aux->map_ptr_state.map_ptr,
 					.tail_call.key = bpf_map_key_immediate(aux),
-					.insn_idx = i + delta,
+					.insn_idx = i,
 				};
 
 				ret = bpf_jit_add_poke_descriptor(prog, &desc);
@@ -2460,13 +2460,13 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env)
 								 map)->index_mask);
 			insn_buf[2] = *insn;
 			cnt = 3;
-			insn = bpf_patch_list_add(env, i + delta, insn_buf, cnt);
+			insn = bpf_patch_list_add(env, i, insn_buf, cnt);
 			if (IS_ERR(insn))
 				return PTR_ERR(insn);
 			goto next_insn;
 		}
 
-		aux = &env->insn_aux_data[i + delta];
+		aux = &env->insn_aux_data[i];
 		if (aux->arg_prog) {
 			/* The verifier will process callback_fn as many times as necessary
 			 * with different maps and the register states prepared by
@@ -2490,14 +2490,14 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env)
 			insn_buf[2] = *insn;
 			cnt = 3;
 
-			insn = bpf_patch_list_add(env, i + delta, insn_buf, cnt);
+			insn = bpf_patch_list_add(env, i, insn_buf, cnt);
 			if (IS_ERR(insn))
 				return PTR_ERR(insn);
 			goto patch_call_imm;
 		}
 
 		/* bpf_per_cpu_ptr() and bpf_this_cpu_ptr() */
-		if (env->insn_aux_data[i + delta].call_with_percpu_alloc_ptr) {
+		if (env->insn_aux_data[i].call_with_percpu_alloc_ptr) {
 			/* patch with 'r1 = *(u64 *)(r1 + 0)' since for percpu data,
 			 * bpf_mem_alloc() returns a ptr to the percpu data ptr.
 			 */
@@ -2505,7 +2505,7 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env)
 			insn_buf[1] = *insn;
 			cnt = 2;
 
-			insn = bpf_patch_list_add(env, i + delta, insn_buf, cnt);
+			insn = bpf_patch_list_add(env, i, insn_buf, cnt);
 			if (IS_ERR(insn))
 				return PTR_ERR(insn);
 			goto patch_call_imm;
@@ -2525,7 +2525,7 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env)
 		     insn->imm == BPF_FUNC_redirect_map    ||
 		     insn->imm == BPF_FUNC_for_each_map_elem ||
 		     insn->imm == BPF_FUNC_map_lookup_percpu_elem)) {
-			aux = &env->insn_aux_data[i + delta];
+			aux = &env->insn_aux_data[i];
 			if (bpf_map_ptr_poisoned(aux))
 				goto patch_call_imm;
 
@@ -2544,7 +2544,7 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env)
 				if (bpf_map_is_percpu_map(map_ptr->map_type))
 					prog->jit_required = true;
 
-				insn = bpf_patch_list_add(env, i + delta, insn_buf, cnt);
+				insn = bpf_patch_list_add(env, i, insn_buf, cnt);
 				if (IS_ERR(insn))
 					return PTR_ERR(insn);
 				goto next_insn;
@@ -2622,7 +2622,7 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env)
 						  BPF_REG_0, 0);
 			cnt = 3;
 
-			insn = bpf_patch_list_add(env, i + delta, insn_buf, cnt);
+			insn = bpf_patch_list_add(env, i, insn_buf, cnt);
 			if (IS_ERR(insn))
 				return PTR_ERR(insn);
 			goto next_insn;
@@ -2647,7 +2647,7 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env)
 			insn_buf[0] = BPF_ALU32_REG(BPF_XOR, BPF_REG_0, BPF_REG_0);
 			cnt = 1;
 #endif
-			insn = bpf_patch_list_add(env, i + delta, insn_buf, cnt);
+			insn = bpf_patch_list_add(env, i, insn_buf, cnt);
 			if (IS_ERR(insn))
 				return PTR_ERR(insn);
 			goto next_insn;
@@ -2662,7 +2662,7 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env)
 			insn_buf[2] = BPF_LDX_MEM(BPF_DW, BPF_REG_0, BPF_REG_0, 0);
 			cnt = 3;
 
-			insn = bpf_patch_list_add(env, i + delta, insn_buf, cnt);
+			insn = bpf_patch_list_add(env, i, insn_buf, cnt);
 			if (IS_ERR(insn))
 				return PTR_ERR(insn);
 			goto next_insn;
@@ -2692,7 +2692,7 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env)
 			insn_buf[cnt++] = BPF_JMP_A(1);
 			insn_buf[cnt++] = BPF_MOV64_IMM(BPF_REG_0, -EINVAL);
 
-			insn = bpf_patch_list_add(env, i + delta, insn_buf, cnt);
+			insn = bpf_patch_list_add(env, i, insn_buf, cnt);
 			if (IS_ERR(insn))
 				return PTR_ERR(insn);
 			goto next_insn;
@@ -2720,7 +2720,7 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env)
 				cnt = 1;
 			}
 
-			insn = bpf_patch_list_add(env, i + delta, insn_buf, cnt);
+			insn = bpf_patch_list_add(env, i, insn_buf, cnt);
 			if (IS_ERR(insn))
 				return PTR_ERR(insn);
 			goto next_insn;
@@ -2742,7 +2742,7 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env)
 				cnt = 2;
 			}
 
-			insn = bpf_patch_list_add(env, i + delta, insn_buf, cnt);
+			insn = bpf_patch_list_add(env, i, insn_buf, cnt);
 			if (IS_ERR(insn))
 				return PTR_ERR(insn);
 			goto next_insn;
@@ -2754,7 +2754,7 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env)
 			/* Load IP address from ctx - 16 */
 			insn_buf[0] = BPF_LDX_MEM(BPF_DW, BPF_REG_0, BPF_REG_1, -16);
 
-			insn = bpf_patch_list_add(env, i + delta, insn_buf, 1);
+			insn = bpf_patch_list_add(env, i, insn_buf, 1);
 			if (IS_ERR(insn))
 				return PTR_ERR(insn);
 			goto next_insn;
@@ -2806,7 +2806,7 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env)
 			insn_buf[10] = BPF_MOV64_IMM(BPF_REG_0, -ENOENT);
 			cnt = 11;
 
-			insn = bpf_patch_list_add(env, i + delta, insn_buf, cnt);
+			insn = bpf_patch_list_add(env, i, insn_buf, cnt);
 			if (IS_ERR(insn))
 				return PTR_ERR(insn);
 			goto next_insn;
@@ -2820,7 +2820,7 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env)
 			insn_buf[1] = BPF_ATOMIC_OP(BPF_DW, BPF_XCHG, BPF_REG_1, BPF_REG_0, 0);
 			cnt = 2;
 
-			insn = bpf_patch_list_add(env, i + delta, insn_buf, cnt);
+			insn = bpf_patch_list_add(env, i, insn_buf, cnt);
 			if (IS_ERR(insn))
 				return PTR_ERR(insn);
 			goto next_insn;
@@ -2838,7 +2838,7 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env)
 		}
 		insn->imm = BPF_CALL_IMM(fn->func);
 next_insn:
-		if (subprogs[cur_subprog + 1].start == i + delta + 1) {
+		if (subprogs[cur_subprog + 1].start == i + 1) {
 			subprogs[cur_subprog].stack_depth += stack_depth_extra;
 			subprogs[cur_subprog].stack_extra = stack_depth_extra;
 
@@ -2853,7 +2853,7 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env)
 			stack_depth_extra = 0;
 		}
 		i++;
-		insn = &prog->insnsi[i + delta];
+		insn = &prog->insnsi[i];
 	}
 
 	ret = bpf_patch_list_commit(env);
Signature · 1 line
2.43.0
#9 lore raw

PATCH v2 7/22 bpf: Let the patch list remove instructions

In reply to Qiliang Yuan

verifier_remove_insns() removes a range of instructions. It moves the tail of the program and of the aux data, walks all branches, and fixes up the subprogs, the line info, the function pointers and the instruction arrays, at the same O(N * M) cost as patching.

The patch list can only replace instructions, so bpf_opt_remove_nops() and bpf_opt_remove_dead_code() can't move over to it.

Add bpf_patch_list_del() to queue the removal of an instruction along with patches. Map a removed instruction to the next one that stays, so that jumps to it land there. Drop the line info of removed instructions, except that the last one moves to the next instruction that stays if that has none of its own. Remove the subprogs whose instructions are all removed, with their func_info, and mark the function pointers to them and the entries of instruction arrays deleted. Tell offloaded programs about each removed range.

---
 include/linux/bpf_verifier.h |   9 +++
 kernel/bpf/bpf_insn_array.c  |  10 ++-
 kernel/bpf/core.c            |  27 +++++++-
 kernel/bpf/fixups.c          | 142 ++++++++++++++++++++++++++++++++++++++++---
 4 files changed, 176 insertions(+), 12 deletions(-)
include/linux/bpf_verifier.h +9 -0
index 49a6e443de75d..ace314cc539dd 100644
@@ -1089,6 +1089,7 @@ struct bpf_patch_image {
 	u32 new_cnt;
 	s32 grow;
 	u32 bad;
+	bool del;
 };
 
 /* Map an offset in the old program, which may be past its end. */
@@ -1098,9 +1099,16 @@ static inline u32 bpf_patch_image_remap(const struct bpf_patch_image *img,
 	return off <= img->cnt ? map[off] : off + img->grow;
 }
 
+static inline bool bpf_patch_image_deleted(const struct bpf_patch_image *img, u32 off)
+{
+	return off < img->cnt && img->new_off[off] == img->new_off[off + 1];
+}
+
 struct bpf_insn *__bpf_patch_list_add(struct bpf_patch_list *pl,
 				      const struct bpf_prog *prog, u32 off,
 				      const struct bpf_insn *patch, u32 len);
+int __bpf_patch_list_del(struct bpf_patch_list *pl, const struct bpf_prog *prog,
+			 u32 off);
 void bpf_patch_list_release(struct bpf_patch_list *pl);
 int bpf_patch_list_build(const struct bpf_patch_list *pl, const struct bpf_prog *prog,
 			 struct bpf_patch_image *img);
@@ -2066,6 +2074,7 @@ struct bpf_insn *bpf_patch_list_add(struct bpf_verifier_env *env, u32 off,
 				    const struct bpf_insn *patch, u32 len);
 int bpf_patch_list_commit(struct bpf_verifier_env *env);
 void bpf_patch_list_free(struct bpf_verifier_env *env);
+int bpf_patch_list_del(struct bpf_verifier_env *env, u32 off);
 
 int bpf_flip_opcode(u32 opcode);
 u8 bpf_rev_opcode(u8 opcode);
kernel/bpf/bpf_insn_array.c +7 -3
index dbfcf1eddb91e..5330e2d7f4062 100644
@@ -254,8 +254,9 @@ void bpf_insn_array_adjust(struct bpf_map *map, u32 first, u32 len)
 }
 
 /*
- * Move each offset to new_off[offset], new_off[] covers [0, cnt]. Offsets
- * past the end of the old program only move by 'grow'.
+ * Move each offset to new_off[offset], new_off[] covers [0, cnt]. An insn is
+ * removed when it maps to the same offset as the next one. Offsets past the
+ * end of the old program only move by 'grow'.
  */
 void bpf_insn_array_remap(struct bpf_map *map, const u32 *new_off, u32 cnt, s32 grow)
 {
@@ -267,7 +268,10 @@ void bpf_insn_array_remap(struct bpf_map *map, const u32 *new_off, u32 cnt, s32
 		off = insn_array->values[i].xlated_off;
 		if (off == INSN_DELETED)
 			continue;
-		insn_array->values[i].xlated_off = off <= cnt ? new_off[off] : off + grow;
+		if (off < cnt && new_off[off] == new_off[off + 1])
+			insn_array->values[i].xlated_off = INSN_DELETED;
+		else
+			insn_array->values[i].xlated_off = off <= cnt ? new_off[off] : off + grow;
 	}
 }
 
kernel/bpf/core.c +25 -2
index d2c36db09c8c9..75d6399ce0965 100644
@@ -658,6 +658,25 @@ struct bpf_insn *__bpf_patch_list_add(struct bpf_patch_list *pl,
 	return &pl->insns[p->start + len - 1];
 }
 
+/* Queue the removal of insn 'off'. Jumps to it land on the next insn that stays. */
+int __bpf_patch_list_del(struct bpf_patch_list *pl, const struct bpf_prog *prog,
+			 u32 off)
+{
+	struct bpf_insn_patch *p;
+	int err;
+
+	err = patch_list_reserve_patch(pl);
+	if (err)
+		return err;
+
+	p = &pl->patches[pl->cnt++];
+	p->off = off;
+	p->len = 0;
+	p->start = pl->insn_cnt;
+	p->orig = prog->insnsi[off];
+	return 0;
+}
+
 void bpf_patch_list_release(struct bpf_patch_list *pl)
 {
 	kvfree(pl->patches);
@@ -684,8 +703,10 @@ int bpf_patch_list_build(const struct bpf_patch_list *pl, const struct bpf_prog
 
 	for (i = 0, k = 0; i <= cnt; i++) {
 		img->new_off[i] = i + img->grow;
-		if (k < pl->cnt && pl->patches[k].off == i)
+		if (k < pl->cnt && pl->patches[k].off == i) {
+			img->del |= !pl->patches[k].len;
 			img->grow += pl->patches[k++].len - 1;
+		}
 	}
 	img->new_cnt = cnt + img->grow;
 
@@ -724,7 +745,7 @@ void bpf_patch_image_free(struct bpf_patch_image *img)
 
 /*
  * Put the new image in 'prog', which has room for it, and move the poke
- * descriptors and the line info along.
+ * descriptors and, unless insns were removed, the line info along.
  */
 void bpf_patch_image_install(struct bpf_prog *prog, const struct bpf_patch_image *img)
 {
@@ -738,6 +759,8 @@ void bpf_patch_image_install(struct bpf_prog *prog, const struct bpf_patch_image
 			bpf_patch_image_remap(img, img->new_off,
 					      prog->aux->poke_tab[i].insn_idx);
 
+	if (img->del)
+		return;
 	for (i = 0; i < prog->aux->nr_linfo; i++)
 		prog->aux->linfo[i].insn_off =
 			bpf_patch_image_remap(img, img->new_off,
kernel/bpf/fixups.c +135 -7

202 lines not on this page · raw message

Signature · 1 line
2.43.0
#10 lore raw

Re: [PATCH bpf-next v2 07/22] bpf: Let the patch list remove instructions

Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider: - [High] bpf: premature prog->len update breaks bpf_find_subprog() in bpf_patch_list_commit() --

Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
- [High] bpf: premature prog->len update breaks bpf_find_subprog() in bpf_patch_list_commit() --

commit 36c5b3c1e86de2cef14800f7c3faaea5d0fafe3d
Author: Qiliang Yuan <[email protected]>

bpf: Let the patch list remove instructions

This commit adds bpf_patch_list_del() to allow the verifier's patch list to queue instruction removals alongside replacements, updating line info, subprogs, function pointers, instruction arrays, and offloaded programs when committed.

Quoted 4 lines
kernel/bpf/fixups.c +0 -0
index 940265cb80ebf..1a1a374a076b1 100644

[ ... ]

Quoted 10 lines
kernel/bpf/fixups.c +2 -0
@@ -514,25 +624,43 @@ int bpf_patch_list_commit(struct bpf_verifier_env *env)
 	env->insn_aux_data_len = img.new_cnt;
 	data = NULL;
 
+	/* before subprogs are removed, since it looks at them */
 	for (i = 0; i < env->func_ptr_cnt; i++) {
 		struct bpf_func_ptr *fp = &env->func_ptrs[i];
+		int subprog;
 
 		if (fp->xlated_off == BPF_FUNC_PTR_DELETED)

kernel/bpf/fixups.c int bpf_patch_list_commit(struct bpf_verifier_env *env) · line 642

Quoted 10 lines
kernel/bpf/fixups.c +9 -0
 			continue;
+		if (bpf_patch_image_deleted(&img, fp->xlated_off)) {
+			subprog = bpf_find_subprog(env, fp->xlated_off);
+			if (subprog <= 0 ||
+			    img.new_off[env->subprog_info[subprog].start] ==
+			    img.new_off[env->subprog_info[subprog + 1].start]) {
+				fp->xlated_off = BPF_FUNC_PTR_DELETED;
+				continue;
+			}
+		}

[Severity: High]
Can calling bpf_find_subprog() here with the old-image offset fp->xlated_off falsely mark a live function pointer as BPF_FUNC_PTR_DELETED when the program shrinks?

Earlier in bpf_patch_list_commit(), bpf_patch_image_install() updates prog->len to img.new_cnt:

kernel/bpf/core.c:bpf_patch_image_install() {
	memcpy(prog->insnsi, img->insns, sizeof(*img->insns) * img->new_cnt);
	prog->len = img->new_cnt;
    ...
}

When bpf_patch_list_commit() then calls bpf_find_subprog()->bpf_find_containing_subprog(), it checks the old-image offset against the already-shrunk env->prog->len:

kernel/bpf/verifier.c:bpf_find_containing_subprog() {
	if (off >= env->prog->len || off < 0 || env->subprog_cnt == 0)
		return NULL;
    ...
}

If a live static subprogram near the end of the program has its entry instruction removed (for example, a nop or simplified branch removed in bpf_opt_remove_nops()) and earlier instruction removals shrink the program such that fp->xlated_off >= img.new_cnt, bpf_find_subprog() will return -ENOENT.

Wouldn't that cause the subprog <= 0 check to set fp->xlated_off to BPF_FUNC_PTR_DELETED even though the subprogram still has live instructions, causing resolve_func_ptrs() during bpf_jit_subprogs() to write NULL into the read-only map slot used by callx?

Signature · 1 line
Sashiko AI review · https://sashiko.dev/#/patchset/[email protected]?part=7
#11 lore raw

Re: [PATCH bpf-next v2 07/22] bpf: Let the patch list remove instructions

In reply to Qiliang Yuan
Quoted 1 line · Qiliang Yuan

bpf_patch_image_install(prog, &img);

[...]

Review

Quoted 10 lines
(quoted diff) +5 -0
+	/* before subprogs are removed, since it looks at them */
 	for (i = 0; i < env->func_ptr_cnt; i++) {
 		struct bpf_func_ptr *fp = &env->func_ptrs[i];
+		int subprog;
 
 		if (fp->xlated_off == BPF_FUNC_PTR_DELETED)
 			continue;
+		if (bpf_patch_image_deleted(&img, fp->xlated_off)) {
+			subprog = bpf_find_subprog(env, fp->xlated_off);
+			if (subprog <= 0 ||

Sashiko is right. It's real, and it crashes the kernel.

bpf_patch_image_install() already set prog->len to the new length. bpf_find_subprog() gets an old offset and compares it with prog->len. When the prog shrinks enough it doesn't find a live function. The func ptr is marked as deleted and the slot in .rodata becomes NULL.

It needs two things:
- the first insn of the function goes away as a nop
- this commit removes at least (end of prog - start of function) insns

Plain C hits it:

  #include <linux/bpf.h>
  #include <bpf/bpf_helpers.h>

  struct st { int a; } g = { .a = 10 };

  #define OP(name, expr)					\
  static __noinline int name(struct st *s)		\
  {							\
  	if (!s)						\
  		return bpf_get_prandom_u32();		\
  	return expr;					\
  }
  OP(op_a, s->a + 2) OP(op_b, s->a + 3) OP(op_c, s->a + 4) OP(op_d, s->a + 5)
  OP(op_e, s->a + 6) OP(op_f, s->a + 7) OP(op_g, s->a + 8) OP(op_h, s->a + 9)

  static int (* const volatile ops[])(struct st *) = {
  	op_a, op_b, op_c, op_d, op_e, op_f, op_g, op_h
  };

  SEC("socket")
  int vt_all(struct __sk_buff *skb)
  {
  	int i, sum = 0;

  	for (i = 0; i < 8; i++)
  		sum += ops[i](&g);
  	return sum;
  }
  char _license[] SEC("license") = "GPL";

The verifier knows that &g is not NULL, so every op starts with a nop.

bpf-next: Return value: 124
this series: BUG: kernel NULL pointer dereference, address: 0000000000000000

                RIP: 0010:0x0

That's the shape of any table of ops.

The minimal fix is to do the lookup before the install. On top of the whole series:

kernel/bpf/fixups.c +22 -19
index a442188647bc..de758ce7afac 100644
@@ -451,6 +451,28 @@ int bpf_patch_list_commit(struct bpf_verifier_env *env)
 		}
 	}
 
+	/*
+	 * Before the new image is installed and subprogs are removed:
+	 * bpf_find_subprog() looks at prog->len and at the subprogs.
+	 */
+	for (i = 0; i < env->func_ptr_cnt; i++) {
+		struct bpf_func_ptr *fp = &env->func_ptrs[i];
+		int subprog;
+
+		if (fp->xlated_off == BPF_FUNC_PTR_DELETED)
+			continue;
+		if (bpf_patch_image_deleted(&img, fp->xlated_off)) {
+			subprog = bpf_find_subprog(env, fp->xlated_off);
+			if (subprog <= 0 ||
+			    img.new_off[env->subprog_info[subprog].start] ==
+			    img.new_off[env->subprog_info[subprog + 1].start]) {
+				fp->xlated_off = BPF_FUNC_PTR_DELETED;
+				continue;
+			}
+		}
+		fp->xlated_off = bpf_patch_image_remap(&img, img.new_off, fp->xlated_off);
+	}
+
 	bpf_patch_image_install(prog, &img);
 
 	for (i = 0, k = 0; i < img.cnt; i = end) {
@@ -474,25 +496,6 @@ int bpf_patch_list_commit(struct bpf_verifier_env *env)
 	env->insn_aux_data_len = img.new_cnt;
 	data = NULL;
 
-	/* before subprogs are removed, since it looks at them */
-	for (i = 0; i < env->func_ptr_cnt; i++) {
-		struct bpf_func_ptr *fp = &env->func_ptrs[i];
-		int subprog;
-
-		if (fp->xlated_off == BPF_FUNC_PTR_DELETED)
-			continue;
-		if (bpf_patch_image_deleted(&img, fp->xlated_off)) {
-			subprog = bpf_find_subprog(env, fp->xlated_off);
-			if (subprog <= 0 ||
-			    img.new_off[env->subprog_info[subprog].start] ==
-			    img.new_off[env->subprog_info[subprog + 1].start]) {
-				fp->xlated_off = BPF_FUNC_PTR_DELETED;
-				continue;
-			}
-		}
-		fp->xlated_off = bpf_patch_image_remap(&img, img.new_off, fp->xlated_off);
-	}
-
 	if (img.del)
 		patch_list_del_subprogs(env, img.new_off);
 

With it the prog above returns 124.

But that fixes one instance.
The commit changes prog->len, aux data, func ptrs, subprogs, line info and insn arrays one after another, and helpers read env and prog in between. So the order of the steps is load-bearing, and nothing says so. Make each table a function of (old value, new_off[]), with no helper that looks at env or prog, and install the image as the last step. Then this class of bugs cannot happen.

Please add a selftest for it: callx through a pointer in .rodata, the callee starts with a nop, and main loses more insns than the callee has. All tests in patches 21 and 22 pass on bpf-next without the series, so they don't tell whether a remap rule of the commit is wrong.

Also patches 4 and 6 don't apply anymore, since arena_scalar is gone.

Other than that the patches look great.

pw-bot: cr

#12 lore raw

PATCH v2 8/22 bpf: Remove dead code through the patch list

In reply to Qiliang Yuan

bpf_opt_remove_dead_code() removes every range of instructions that the verifier never reached with verifier_remove_insns().

Each removal moves the tail of the program and of its aux data and walks all of it, so a program with many unreached ranges pays O(prog->len) for each of them.

Queue the removal of each unreached instruction with bpf_patch_list_del() and commit them once.

---
 kernel/bpf/fixups.c | 13 +++----------
 1 file changed, 3 insertions(+), 10 deletions(-)
kernel/bpf/fixups.c +3 -10
index 1a1a374a076b1..95f4fe5d607e6 100644
@@ -1018,21 +1018,14 @@ int bpf_opt_remove_dead_code(struct bpf_verifier_env *env)
 	keep_funcs_with_addr_taken(env);
 
 	for (i = 0; i < insn_cnt; i++) {
-		int j;
-
-		j = 0;
-		while (i + j < insn_cnt && !aux_data[i + j].seen)
-			j++;
-		if (!j)
+		if (aux_data[i].seen)
 			continue;
-
-		err = verifier_remove_insns(env, i, j);
+		err = bpf_patch_list_del(env, i);
 		if (err)
 			return err;
-		insn_cnt = env->prog->len;
 	}
 
-	return 0;
+	return bpf_patch_list_commit(env);
 }
 
 int bpf_opt_remove_nops(struct bpf_verifier_env *env)
Signature · 1 line
2.43.0
#13 lore raw

PATCH v2 9/22 bpf: Strip nops through the patch list

In reply to Qiliang Yuan

bpf_opt_remove_nops() removes every "ja 0" and "may_goto +0" with verifier_remove_insns(). After removing may_goto +0, it looks at the instruction in front of it again, since a may_goto +1 there has turned into another may_goto +0.

Each removal moves the tail of the program and walks all of it, so loading 131072 "ja 0" takes about 53 seconds.

Mark the nops in a bitmap first, queue their removal with bpf_patch_list_del() and commit them once. Take a forward jump over removed instructions as one of +0, and keep looking back from a removed may_goto as long as that turns another one into a nop. verifier_remove_insns() and its static helpers have no users left, remove them.

Time of BPF_PROG_LOAD of n "ja 0" followed by "r0 = 0; exit", average of three runs, x86_64 VM with 32 vCPUs, before and after this patch:

              before     after
  n = 32768    3.207 s   0.203 s
  n = 131072  52.940 s   0.766 s
---
 kernel/bpf/fixups.c | 236 +++++++++++-----------------------------------------
 1 file changed, 47 insertions(+), 189 deletions(-)
kernel/bpf/fixups.c +47 -189
index 95f4fe5d607e6..7c7c38eb9f0c2 100644
@@ -298,14 +298,6 @@ static void adjust_insn_arrays(struct bpf_verifier_env *env, u32 first, u32 len)
 		bpf_insn_array_adjust(env->insn_array_maps[i], first, len);
 }
 
-static void adjust_insn_arrays_after_remove(struct bpf_verifier_env *env, u32 off, u32 len)
-{
-	int i;
-
-	for (i = 0; i < env->insn_array_map_cnt; i++)
-		bpf_insn_array_adjust_after_remove(env->insn_array_maps[i], off, len);
-}
-
 static void adjust_poke_descs(struct bpf_prog *prog, u32 first, u32 len)
 {
 	struct bpf_jit_poke_descriptor *tab = prog->aux->poke_tab;
@@ -743,133 +735,6 @@ static int adjust_jmp_off(struct bpf_prog *prog, u32 tgt_idx, u32 delta)
 	return 0;
 }
 
-static int adjust_subprog_starts_after_remove(struct bpf_verifier_env *env,
-					      u32 off, u32 cnt)
-{
-	int i, j;
-
-	/* find first prog starting at or after off (first to remove) */
-	for (i = 0; i < env->subprog_cnt; i++)
-		if (env->subprog_info[i].start >= off)
-			break;
-	/* find first prog starting at or after off + cnt (first to stay) */
-	for (j = i; j < env->subprog_cnt; j++)
-		if (env->subprog_info[j].start >= off + cnt)
-			break;
-	/* if j doesn't start exactly at off + cnt, we are just removing
-	 * the front of previous prog
-	 */
-	if (env->subprog_info[j].start != off + cnt)
-		j--;
-
-	if (j > i) {
-		struct bpf_prog_aux *aux = env->prog->aux;
-		int move;
-
-		/* move fake 'exit' subprog as well */
-		move = env->subprog_cnt + 1 - j;
-
-		memmove(env->subprog_info + i,
-			env->subprog_info + j,
-			sizeof(*env->subprog_info) * move);
-		env->subprog_cnt -= j - i;
-
-		/* remove func_info and its aux */
-		if (aux->func_info) {
-			move = aux->func_info_cnt - j;
-
-			memmove(aux->func_info + i,
-				aux->func_info + j,
-				sizeof(*aux->func_info) * move);
-			if (aux->func_info_aux)
-				memmove(aux->func_info_aux + i,
-					aux->func_info_aux + j,
-					sizeof(*aux->func_info_aux) * move);
-			aux->func_info_cnt -= j - i;
-			/* func_info->insn_off is set after all code rewrites,
-			 * in adjust_btf_func() - no need to adjust
-			 */
-		}
-		/* The exception callback is live, so it cannot sit inside the removed range. */
-		if (env->exception_callback_subprog >= j)
-			env->exception_callback_subprog -= j - i;
-	} else {
-		/* convert i from "first prog to remove" to "first to adjust" */
-		if (env->subprog_info[i].start == off)
-			i++;
-	}
-
-	/* update fake 'exit' subprog as well */
-	for (; i <= env->subprog_cnt; i++)
-		env->subprog_info[i].start -= cnt;
-
-	return 0;
-}
-
-static int bpf_adj_linfo_after_remove(struct bpf_verifier_env *env, u32 off,
-				      u32 cnt)
-{
-	struct bpf_prog *prog = env->prog;
-	u32 i, l_off, l_cnt, nr_linfo;
-	struct bpf_line_info *linfo;
-
-	nr_linfo = prog->aux->nr_linfo;
-	if (!nr_linfo)
-		return 0;
-
-	linfo = prog->aux->linfo;
-
-	/* find first line info to remove, count lines to be removed */
-	for (i = 0; i < nr_linfo; i++)
-		if (linfo[i].insn_off >= off)
-			break;
-
-	l_off = i;
-	l_cnt = 0;
-	for (; i < nr_linfo; i++)
-		if (linfo[i].insn_off < off + cnt)
-			l_cnt++;
-		else
-			break;
-
-	/* First live insn doesn't match first live linfo, it needs to "inherit"
-	 * last removed linfo.  prog is already modified, so prog->len == off
-	 * means no live instructions after (tail of the program was removed).
-	 */
-	if (prog->len != off && l_cnt &&
-	    (i == nr_linfo || linfo[i].insn_off != off + cnt)) {
-		l_cnt--;
-		linfo[--i].insn_off = off + cnt;
-	}
-
-	/* remove the line info which refer to the removed instructions */
-	if (l_cnt) {
-		memmove(linfo + l_off, linfo + i,
-			sizeof(*linfo) * (nr_linfo - i));
-
-		prog->aux->nr_linfo -= l_cnt;
-		nr_linfo = prog->aux->nr_linfo;
-	}
-
-	/* pull all linfo[i].insn_off >= off + cnt in by cnt */
-	for (i = l_off; i < nr_linfo; i++)
-		linfo[i].insn_off -= cnt;
-
-	/* fix up all subprogs (incl. 'exit') which start >= off */
-	for (i = 0; i <= env->subprog_cnt; i++)
-		if (env->subprog_info[i].linfo_idx > l_off) {
-			/* program may have started in the removed region but
-			 * may not be fully removed
-			 */
-			if (env->subprog_info[i].linfo_idx >= l_off + l_cnt)
-				env->subprog_info[i].linfo_idx -= l_cnt;
-			else
-				env->subprog_info[i].linfo_idx = l_off;
-		}
-
-	return 0;
-}
-
 /* Clean up dynamically allocated fields of aux data for instructions [start, ...] */
 void bpf_clear_insn_aux_data(struct bpf_verifier_env *env, int start, int len)
 {
@@ -886,44 +751,6 @@ void bpf_clear_insn_aux_data(struct bpf_verifier_env *env, int start, int len)
 	}
 }
 
-static int verifier_remove_insns(struct bpf_verifier_env *env, u32 off, u32 cnt)
-{
-	struct bpf_insn_aux_data *aux_data = env->insn_aux_data;
-	unsigned int orig_prog_len = env->prog->len;
-	int err;
-
-	if (bpf_rewrite_must_abort())
-		return -EINTR;
-
-	if (bpf_prog_is_offloaded(env->prog->aux))
-		bpf_prog_offload_remove_insns(env, off, cnt);
-
-	bpf_clear_insn_aux_data(env, off, cnt);
-
-	err = bpf_remove_insns(env->prog, off, cnt);
-	if (err)
-		return err;
-
-	/* before subprogs are adjusted, since it looks at them */
-	bpf_adjust_func_ptrs_after_remove(env, off, cnt);
-
-	err = adjust_subprog_starts_after_remove(env, off, cnt);
-	if (err)
-		return err;
-
-	err = bpf_adj_linfo_after_remove(env, off, cnt);
-	if (err)
-		return err;
-
-	adjust_insn_arrays_after_remove(env, off, cnt);
-
-	memmove(aux_data + off,	aux_data + off + cnt,
-		sizeof(*aux_data) * (orig_prog_len - off - cnt));
-	env->insn_aux_data_len -= cnt;
-
-	return 0;
-}
-
 static const struct bpf_insn NOP = BPF_JMP_IMM(BPF_JA, 0, 0, 0);
 static const struct bpf_insn MAY_GOTO_0 = BPF_RAW_INSN(BPF_JMP | BPF_JCOND, 0, 0, 0, 0);
 
@@ -1028,32 +855,63 @@ int bpf_opt_remove_dead_code(struct bpf_verifier_env *env)
 	return bpf_patch_list_commit(env);
 }
 
+/*
+ * Whether insn i is a nop once the insns in 'removed' are gone. Only forward
+ * jumps over removed insns can turn into one.
+ */
+static bool insn_is_nop(struct bpf_verifier_env *env, int i,
+			const unsigned long *removed)
+{
+	struct bpf_insn insn = env->prog->insnsi[i];
+	int t = i + 1 + insn.off;
+
+	if (env->insn_aux_data[i].indirect_target)
+		return false;
+	if (insn.code != NOP.code && insn.code != MAY_GOTO_0.code)
+		return false;
+	if (insn.off > 0 && find_next_zero_bit(removed, t, i + 1) == t)
+		insn.off = 0;
+
+	return !memcmp(&insn, &NOP, sizeof(NOP)) ||
+	       !memcmp(&insn, &MAY_GOTO_0, sizeof(MAY_GOTO_0));
+}
+
 int bpf_opt_remove_nops(struct bpf_verifier_env *env)
 {
-	struct bpf_insn_aux_data *aux = env->insn_aux_data;
-	struct bpf_insn *insn = env->prog->insnsi;
 	int insn_cnt = env->prog->len;
-	bool is_may_goto_0, is_ja;
-	int i, err;
+	unsigned long *removed;
+	int i, j, err = 0;
 
-	for (i = 0; i < insn_cnt; i++) {
-		is_may_goto_0 = !memcmp(&insn[i], &MAY_GOTO_0, sizeof(MAY_GOTO_0));
-		is_ja = !memcmp(&insn[i], &NOP, sizeof(NOP));
+	removed = bitmap_zalloc(insn_cnt, GFP_KERNEL_ACCOUNT);
+	if (!removed)
+		return -ENOMEM;
 
-		if (!is_may_goto_0 && !is_ja)
-			continue;
-		if (aux[i].indirect_target)
+	for (i = 0; i < insn_cnt; i++) {
+		if (!insn_is_nop(env, i, removed))
 			continue;
+		/*
+		 * Removing may_goto +0 can turn the may_goto +1 in front of it
+		 * into another one, look back as long as it does.
+		 */
+		for (j = i; ; ) {
+			__set_bit(j, removed);
+			if (env->prog->insnsi[j].code != MAY_GOTO_0.code)
+				break;
+			while (--j >= 0 && test_bit(j, removed))
+				;
+			if (j < 0 || !insn_is_nop(env, j, removed))
+				break;
+		}
+	}
 
-		err = verifier_remove_insns(env, i, 1);
+	for_each_set_bit(i, removed, insn_cnt) {
+		err = bpf_patch_list_del(env, i);
 		if (err)
-			return err;
-		insn_cnt--;
-		/* Go back one insn to catch may_goto +1; may_goto +0 sequence */
-		i -= (is_may_goto_0 && i > 0) ? 2 : 1;
+			break;
 	}
+	bitmap_free(removed);
 
-	return 0;
+	return err ?: bpf_patch_list_commit(env);
 }
 
 int bpf_opt_subreg_zext_lo32_rnd_hi32(struct bpf_verifier_env *env,
Signature · 1 line
2.43.0
#14 lore raw

Re: [PATCH bpf-next v2 09/22] bpf: Strip nops through the patch list

TL;DR: The nop-stripping look-back in bpf_opt_remove_nops() may be quadratic with no preemption or signal check, so a crafted program with many nops could stall BPF_PROG_LOAD on non-preemptible…
Quoted 1 line

bpf: Strip nops through the patch list

TL;DR: The nop-stripping look-back in bpf_opt_remove_nops() may be quadratic with no preemption or signal check, so a crafted program with many nops could stall BPF_PROG_LOAD on non-preemptible kernels.

Quoted 4 lines
kernel/bpf/fixups.c +0 -0
index 95f4fe5d607e..7c7c38eb9f0c 100644

[ ... ]

Quoted 9 lines
kernel/bpf/fixups.c +0 -9
-static int verifier_remove_insns(struct bpf_verifier_env *env, u32 off, u32 cnt)
-{
-	struct bpf_insn_aux_data *aux_data = env->insn_aux_data;
-	unsigned int orig_prog_len = env->prog->len;
-	int err;
-
-	if (bpf_rewrite_must_abort())
-		return -EINTR;
-

[ ... ]

Quoted 11 lines
kernel/bpf/fixups.c +7 -0
@@ -1028,32 +855,63 @@ int bpf_opt_remove_dead_code(struct bpf_verifier_env *env)
 	return bpf_patch_list_commit(env);
 }
 
+/*
+ * Whether insn i is a nop once the insns in 'removed' are gone. Only forward
+ * jumps over removed insns can turn into one.
+ */
+static bool insn_is_nop(struct bpf_verifier_env *env, int i,
+			const unsigned long *removed)
+{

[ ... ]

Quoted 2 lines

int bpf_opt_remove_nops(struct bpf_verifier_env *env) {

[ ... ]

Quoted 7 lines
kernel/bpf/fixups.c +6 -0
+	for (i = 0; i < insn_cnt; i++) {
+		if (!insn_is_nop(env, i, removed))
 			continue;
+		/*
+		 * Removing may_goto +0 can turn the may_goto +1 in front of it
+		 * into another one, look back as long as it does.
+		 */

kernel/bpf/fixups.c int bpf_opt_remove_dead_code(struct bpf_verifier_env *env) · line 905

Quoted 10 lines
kernel/bpf/fixups.c +10 -0
+		for (j = i; ; ) {
+			__set_bit(j, removed);
+			if (env->prog->insnsi[j].code != MAY_GOTO_0.code)
+				break;
+			while (--j >= 0 && test_bit(j, removed))
+				;
+			if (j < 0 || !insn_is_nop(env, j, removed))
+				break;
+		}
+	}

Is the look-back here still linear in the program size, and can it still be interrupted?

The removed verifier_remove_insns() called bpf_rewrite_must_abort() on every removal, and the old "i -= 2" step back went through it each time, so each step had a fatal_signal_pending() and cond_resched() check. The new look-back has neither.

After a may_goto +0 is marked, the inner loop walks back bit by bit over the whole contiguous run of already removed insns:

    while (--j >= 0 && test_bit(j, removed))
            ;

Consider N "ja 0" followed by K "may_goto +0" and an exit. Every may_goto +0 walks back over all of the N "ja 0" plus the earlier may_goto +0 insns before it reaches j < 0, so the marking loop does about K * N test_bit() calls.

K is limited by BPF_COMPLEXITY_LIMIT_JMP_SEQ (8192), since each may_goto pushes a pending state while the main path continues to the exit. N is limited by BPF_COMPLEXITY_LIMIT_INSNS (1M) for a privileged loader, and nops are only stripped when env->bpf_capable is set. With N around 970k and K around 8000 that is about 8e9 iterations of test_bit() in a loop with no preemption point, so BPF_PROG_LOAD cannot be killed or rescheduled on a CONFIG_PREEMPT_NONE or CONFIG_PREEMPT_VOLUNTARY kernel until it finishes.

The only bpf_rewrite_must_abort() check left is in bpf_patch_list_del(), which is reached from the for_each_set_bit() loop that runs after this marking loop.

Could the loop remember the index of the last insn that was kept, instead of rescanning the removed run for each may_goto +0? That would keep the pass linear, as the commit message intends, and a bpf_rewrite_must_abort() call in the look-back would restore the killable/preemptible behaviour.

kernel/bpf/fixups.c int bpf_opt_remove_dead_code(struct bpf_verifier_env *env) · line 915

Quoted 11 lines
kernel/bpf/fixups.c +7 -1
+
+	for_each_set_bit(i, removed, insn_cnt) {
+		err = bpf_patch_list_del(env, i);
+		if (err)
+			break;
 	}
+	bitmap_free(removed);
 
-	return 0;
+	return err ?: bpf_patch_list_commit(env);
 }

---
AI reviewed your patch. Please fix the bug or email reply why it's not a bug.
See: https://github.com/kernel-patches/vmtest/blob/master/ci/claude/README.md

CI run summary: https://github.com/kernel-patches/bpf/actions/runs/41053659762

#15 lore raw

PATCH v2 10/22 bpf: Batch the patches of bpf_opt_subreg_zext_lo32_rnd_hi32()

In reply to Qiliang Yuan

bpf_opt_subreg_zext_lo32_rnd_hi32() inserts a zero extension, or with BPF_F_TEST_RND_HI32 a randomization of the upper half, after every instruction that needs it, one bpf_patch_insn_data() at a time.

Each of them costs O(prog->len). Loading pyperf180 with BPF_F_TEST_RND_HI32 does 4610 of them, which takes more than twice as long as loading it without.

Queue them with bpf_patch_list_add() and commit them at the end of the pass.

perf stat -r10 of loading with BPF_F_TEST_RND_HI32, average of two runs, x86_64 VM with 32 vCPUs, before and after this patch:

              before     after
  pyperf180   1.507 s    0.359 s
  pyperf600   4.533 s    0.899 s
---
 kernel/bpf/fixups.c | 22 ++++++++--------------
 1 file changed, 8 insertions(+), 14 deletions(-)
kernel/bpf/fixups.c +8 -14
index 7c7c38eb9f0c2..6c2dce8f3b6eb 100644
@@ -922,9 +922,8 @@ int bpf_opt_subreg_zext_lo32_rnd_hi32(struct bpf_verifier_env *env,
 	struct bpf_insn *zext_patch = env->insn_buf;
 	struct bpf_insn *rnd_hi32_patch = &env->insn_buf[2];
 	struct bpf_insn_aux_data *aux = env->insn_aux_data;
-	int i, patch_len, delta = 0, len = env->prog->len;
+	int i, patch_len, len = env->prog->len;
 	struct bpf_insn *insns = env->prog->insnsi;
-	struct bpf_prog *new_prog;
 	bool rnd_hi32;
 
 	rnd_hi32 = attr->prog_flags & BPF_F_TEST_RND_HI32;
@@ -933,13 +932,12 @@ int bpf_opt_subreg_zext_lo32_rnd_hi32(struct bpf_verifier_env *env,
 	rnd_hi32_patch[2] = BPF_ALU64_IMM(BPF_LSH, BPF_REG_AX, 32);
 	rnd_hi32_patch[3] = BPF_ALU64_REG(BPF_OR, 0, BPF_REG_AX);
 	for (i = 0; i < len; i++) {
-		int adj_idx = i + delta;
 		struct bpf_insn insn;
 		int load_reg;
 
-		insn = insns[adj_idx];
+		insn = insns[i];
 		load_reg = insn_def_regno(&insn);
-		if (!aux[adj_idx].zext_dst) {
+		if (!aux[i].zext_dst) {
 			u8 code, class;
 			u32 imm_rnd;
 
@@ -960,7 +958,7 @@ int bpf_opt_subreg_zext_lo32_rnd_hi32(struct bpf_verifier_env *env,
 
 			/* ctx load could be transformed into wider load. */
 			if (class == BPF_LDX &&
-			    aux[adj_idx].ptr_type == PTR_TO_CTX)
+			    aux[i].ptr_type == PTR_TO_CTX)
 				continue;
 
 			imm_rnd = get_random_u32();
@@ -999,16 +997,12 @@ int bpf_opt_subreg_zext_lo32_rnd_hi32(struct bpf_verifier_env *env,
 		patch = zext_patch;
 		patch_len = 2;
 apply_patch_buffer:
-		new_prog = bpf_patch_insn_data(env, adj_idx, patch, patch_len);
-		if (!new_prog)
-			return -ENOMEM;
-		env->prog = new_prog;
-		insns = new_prog->insnsi;
-		aux = env->insn_aux_data;
-		delta += patch_len - 1;
+		patch = bpf_patch_list_add(env, i, patch, patch_len);
+		if (IS_ERR(patch))
+			return PTR_ERR(patch);
 	}
 
-	return 0;
+	return bpf_patch_list_commit(env);
 }
 
 /*
Signature · 1 line
2.43.0
#16 lore raw

PATCH v2 11/22 bpf: Allow patching an instruction twice through the patch list

In reply to Qiliang Yuan

bpf_convert_ctx_accesses() puts a barrier in front of an instruction and may then rewrite the instruction as well. bpf_patch_insn_data() applies the second patch to where the first one left the instruction, the last instruction of the barrier patch.

The patch list refuses a second patch for an instruction, since it takes patches in increasing order of the instruction they replace.

Make a patch queued again for the same instruction replace the last instruction of the patch queued before. Move the backward jumps of the new instructions down with them, so that a jump back to an earlier instruction, like the one to the shared epilogue, still lands on it. The barrier in front of it doesn't jump, so warn and fail if an instruction in front of the last one jumps past it, instead of moving such jumps along.

---
 kernel/bpf/core.c   | 64 +++++++++++++++++++++++++++++++++++++++++++++++++++--
 kernel/bpf/fixups.c |  5 +++--
 2 files changed, 65 insertions(+), 4 deletions(-)
kernel/bpf/core.c +62 -2
index 75d6399ce0965..10efd1dd36689 100644
@@ -599,6 +599,46 @@ static int insn_set_rel(struct bpf_insn *insn, s64 rel, bool is_imm)
 	return 0;
 }
 
+/* Whether one of the 'len' insns of a patch in front of the last one jumps past it. */
+static bool patch_list_jumps_past(const struct bpf_insn *insns, u32 len)
+{
+	bool is_imm;
+	s64 rel;
+	u32 k;
+
+	for (k = 0; k + 1 < len; k++)
+		if (insn_get_rel(&insns[k], &rel, &is_imm) && (s64)k + rel + 1 >= len)
+			return true;
+	return false;
+}
+
+/*
+ * The 'len' insns of a patch were moved down by 'by' insns inside it. Keep
+ * what they referred to in front of the patch, the same way as
+ * bpf_adj_moved_insn() does: a call to the start of the patch, the old start
+ * of a subprog, stays there, a jump to itself doesn't.
+ */
+static int patch_list_move_down(struct bpf_insn *insns, u32 len, u32 by)
+{
+	bool is_imm, call;
+	s64 rel, tgt;
+	u32 k;
+	int err;
+
+	for (k = 0; k < len; k++) {
+		if (!insn_get_rel(&insns[k], &rel, &is_imm))
+			continue;
+		call = bpf_pseudo_func(&insns[k]) || bpf_pseudo_call(&insns[k]);
+		tgt = (s64)k + rel + 1;
+		if (tgt > 0 || (tgt == 0 && !call))
+			continue;
+		err = insn_set_rel(&insns[k], rel - by, is_imm);
+		if (err)
+			return err;
+	}
+	return 0;
+}
+
 /*
  * insn is number 'idx' of the 'len' insns that replace insn 'off' of the old
  * image (an insn that isn't patched is its own patch of length 1). It lands
@@ -631,7 +671,10 @@ static int patch_list_adj_insn(struct bpf_insn *insn, const u32 *new_off,
  * Queue the replacement of insn 'off' of 'prog' by 'patch[0..len)'. Patches
  * are queued in increasing order of 'off' and applied together, so a pass
  * keeps addressing insns by their index in 'prog'. Jumps in the patch that
- * leave it are relative to the patch placed at 'off'.
+ * leave it are relative to the patch placed at 'off'. Patching 'off' again
+ * replaces the last insn of its patch, where the insn being patched went, and
+ * the insns in front of it must not jump past it. Jumps of the new insns that
+ * leave the patch are relative to the first of them, as for a first patch.
  *
  * Return the copy of the last insn of the patch, which stays valid until the
  * next call.
@@ -640,9 +683,26 @@ struct bpf_insn *__bpf_patch_list_add(struct bpf_patch_list *pl,
 				      const struct bpf_prog *prog, u32 off,
 				      const struct bpf_insn *patch, u32 len)
 {
-	struct bpf_insn_patch *p;
+	struct bpf_insn_patch *p = pl->cnt ? &pl->patches[pl->cnt - 1] : NULL;
 	int err;
 
+	if (p && off == p->off) {
+		if (WARN_ON_ONCE(patch_list_jumps_past(pl->insns + p->start, p->len)))
+			return ERR_PTR(-EFAULT);
+		err = patch_list_reserve_insns(pl, len - 1);
+		if (err)
+			return ERR_PTR(err);
+		/* the last patch is at the end of pl->insns */
+		memcpy(pl->insns + p->start + p->len - 1, patch, len * sizeof(*patch));
+		err = patch_list_move_down(pl->insns + p->start + p->len - 1, len,
+					   p->len - 1);
+		if (err)
+			return ERR_PTR(err);
+		p->len += len - 1;
+		pl->insn_cnt += len - 1;
+		return &pl->insns[p->start + p->len - 1];
+	}
+
 	err = patch_list_reserve_patch(pl) ?: patch_list_reserve_insns(pl, len);
 	if (err)
 		return ERR_PTR(err);
kernel/bpf/fixups.c +3 -2
index 6c2dce8f3b6eb..a56b743be0062 100644
@@ -381,16 +381,17 @@ struct bpf_insn *bpf_patch_list_add(struct bpf_verifier_env *env, u32 off,
 				    const struct bpf_insn *patch, u32 len)
 {
 	struct bpf_patch_list *pl = &env->patch_list;
+	struct bpf_insn_patch *p = pl->cnt ? &pl->patches[pl->cnt - 1] : NULL;
 
 	if (bpf_rewrite_must_abort())
 		return ERR_PTR(-EINTR);
 
 	if (verifier_bug_if(!len || off >= env->prog->len ||
-			    (pl->cnt && off <= pl->patches[pl->cnt - 1].off),
+			    (p && (off < p->off || (off == p->off && !p->len))),
 			    env, "insn %u patched out of order", off))
 		return ERR_PTR(-EFAULT);
 
-	if (len == 1) {
+	if (len == 1 && (!p || off != p->off)) {
 		env->prog->insnsi[off] = *patch;
 		adjust_insn_aux_data(env, env->prog, off, 1, NULL,
 				     BPF_PATCH_KEEP_TARGET);
Signature · 1 line
2.43.0
#17 lore raw

PATCH v2 12/22 bpf: Teach the patch list to insert in front of an instruction

In reply to Qiliang Yuan

bpf_convert_ctx_accesses() puts the prologue in front of the first instruction, and bpf_do_misc_fixups() the setup of the may_goto counter in front of each subprog that needs one. They patch the instruction with the new ones followed by itself in BPF_PATCH_MOVE_TARGET mode, then move the jumps to it with adjust_jmp_off().

The patch list names a patched instruction by the first instruction of its patch, which would send the jumps to it to the inserted ones.

Add bpf_patch_list_insert() for that. Record in a queued patch which of its instructions the jumps to the patched one land on, the instruction itself after an insertion. Map jumps, instruction arrays and poke descriptors there on commit, while subprogs, line info, function pointers and calls keep starting at the first inserted instruction. Keep the jumps of the instruction pointing where they did when it moves behind the inserted ones, as bpf_adj_moved_insn() does.

---
 include/linux/bpf.h          |  3 +-
 include/linux/bpf_verifier.h |  6 ++++
 kernel/bpf/bpf_insn_array.c  | 11 ++++----
 kernel/bpf/core.c            | 66 ++++++++++++++++++++++++++++++++++++++------
 kernel/bpf/fixups.c          | 39 +++++++++++++++++++++-----
 5 files changed, 104 insertions(+), 21 deletions(-)
include/linux/bpf.h +2 -1
index 9bb5e0c823627..bc8db33ceac32 100644
@@ -4378,7 +4378,8 @@ int bpf_insn_array_ready(struct bpf_map *map);
 void bpf_insn_array_release(struct bpf_map *map);
 void bpf_insn_array_adjust(struct bpf_map *map, u32 first, u32 len);
 void bpf_insn_array_adjust_after_remove(struct bpf_map *map, u32 off, u32 len);
-void bpf_insn_array_remap(struct bpf_map *map, const u32 *new_off, u32 cnt, s32 grow);
+void bpf_insn_array_remap(struct bpf_map *map, const u32 *new_off, const u32 *new_tgt,
+			  u32 cnt, s32 grow);
 
 #ifdef CONFIG_BPF_SYSCALL
 void bpf_prog_update_insn_ptrs(struct bpf_prog *prog, u32 *offsets, void *image);
include/linux/bpf_verifier.h +6 -0
index ace314cc539dd..9562665757a79 100644
@@ -1065,6 +1065,7 @@ struct bpf_insn_patch {
 	u32 off;
 	u32 len;
 	u32 start;		/* first insn of the patch in bpf_patch_list.insns */
+	u32 target;		/* insn of the patch that jumps to 'off' land on */
 	struct bpf_insn orig;	/* the replaced insn when the patch was queued */
 };
 
@@ -1085,6 +1086,7 @@ struct bpf_patch_list {
 struct bpf_patch_image {
 	struct bpf_insn *insns;
 	u32 *new_off;
+	u32 *new_tgt;
 	u32 cnt;
 	u32 new_cnt;
 	s32 grow;
@@ -1109,6 +1111,8 @@ struct bpf_insn *__bpf_patch_list_add(struct bpf_patch_list *pl,
 				      const struct bpf_insn *patch, u32 len);
 int __bpf_patch_list_del(struct bpf_patch_list *pl, const struct bpf_prog *prog,
 			 u32 off);
+int __bpf_patch_list_insert(struct bpf_patch_list *pl, const struct bpf_prog *prog,
+			    u32 off, const struct bpf_insn *insns, u32 cnt);
 void bpf_patch_list_release(struct bpf_patch_list *pl);
 int bpf_patch_list_build(const struct bpf_patch_list *pl, const struct bpf_prog *prog,
 			 struct bpf_patch_image *img);
@@ -2075,6 +2079,8 @@ struct bpf_insn *bpf_patch_list_add(struct bpf_verifier_env *env, u32 off,
 int bpf_patch_list_commit(struct bpf_verifier_env *env);
 void bpf_patch_list_free(struct bpf_verifier_env *env);
 int bpf_patch_list_del(struct bpf_verifier_env *env, u32 off);
+int bpf_patch_list_insert(struct bpf_verifier_env *env, u32 off,
+			  const struct bpf_insn *insns, u32 cnt);
 
 int bpf_flip_opcode(u32 opcode);
 u8 bpf_rev_opcode(u8 opcode);
kernel/bpf/bpf_insn_array.c +6 -5
index 5330e2d7f4062..cf67315be0359 100644
@@ -254,11 +254,12 @@ void bpf_insn_array_adjust(struct bpf_map *map, u32 first, u32 len)
 }
 
 /*
- * Move each offset to new_off[offset], new_off[] covers [0, cnt]. An insn is
- * removed when it maps to the same offset as the next one. Offsets past the
- * end of the old program only move by 'grow'.
+ * Move each offset to new_tgt[offset], new_off[] and new_tgt[] cover [0, cnt].
+ * An insn is removed when new_off[] maps it to the same offset as the next
+ * one. Offsets past the end of the old program only move by 'grow'.
  */
-void bpf_insn_array_remap(struct bpf_map *map, const u32 *new_off, u32 cnt, s32 grow)
+void bpf_insn_array_remap(struct bpf_map *map, const u32 *new_off, const u32 *new_tgt,
+			  u32 cnt, s32 grow)
 {
 	struct bpf_insn_array *insn_array = cast_insn_array(map);
 	u32 off;
@@ -271,7 +272,7 @@ void bpf_insn_array_remap(struct bpf_map *map, const u32 *new_off, u32 cnt, s32
 		if (off < cnt && new_off[off] == new_off[off + 1])
 			insn_array->values[i].xlated_off = INSN_DELETED;
 		else
-			insn_array->values[i].xlated_off = off <= cnt ? new_off[off] : off + grow;
+			insn_array->values[i].xlated_off = off <= cnt ? new_tgt[off] : off + grow;
 	}
 }
 
kernel/bpf/core.c +58 -8

134 lines not on this page · raw message

kernel/bpf/fixups.c +32 -7
index a56b743be0062..bb4fd75a70624 100644
@@ -417,6 +417,29 @@ int bpf_patch_list_del(struct bpf_verifier_env *env, u32 off)
 	return __bpf_patch_list_del(pl, env->prog, off);
 }
 
+/* Queue insns to go in front of insn 'off', see __bpf_patch_list_insert(). */
+int bpf_patch_list_insert(struct bpf_verifier_env *env, u32 off,
+			  const struct bpf_insn *insns, u32 cnt)
+{
+	struct bpf_patch_list *pl = &env->patch_list;
+	struct bpf_insn_patch *p = pl->cnt ? &pl->patches[pl->cnt - 1] : NULL;
+	int err;
+
+	if (bpf_rewrite_must_abort())
+		return -EINTR;
+
+	if (verifier_bug_if(!cnt || off >= env->prog->len ||
+			    (p && off <= p->off),
+			    env, "insns inserted at %u out of order", off))
+		return -EFAULT;
+
+	err = __bpf_patch_list_insert(pl, env->prog, off, insns, cnt);
+	if (err == -ERANGE)
+		verbose(env, "insn %d cannot be patched due to 16-bit range\n",
+			env->insn_aux_data[off].orig_idx);
+	return err;
+}
+
 void bpf_patch_list_free(struct bpf_verifier_env *env)
 {
 	bpf_patch_list_release(&env->patch_list);
@@ -425,6 +448,7 @@ void bpf_patch_list_free(struct bpf_verifier_env *env)
 /*
  * Fill the aux data of the 'p->len' insns at 'slot' from the aux data 'old'
  * of the insn they replace, the same way as adjust_insn_aux_data() does.
+ * The insns in front of p->target were inserted, as with BPF_PATCH_MOVE_TARGET.
  */
 static void patch_list_adj_aux(struct bpf_prog *prog, struct bpf_insn_patch *p,
 			       struct bpf_insn *patch,
@@ -442,7 +466,7 @@ static void patch_list_adj_aux(struct bpf_prog *prog, struct bpf_insn_patch *p,
 	for (i = 0; i < p->len - 1; i++) {
 		slot[i].seen = last->seen;
 		slot[i].zext_dst = bpf_insn_def32(prog, &patch[i]) >= 0;
-		if (!memcmp(&patch[i], orig, sizeof(*orig))) {
+		if (i >= p->target && !memcmp(&patch[i], orig, sizeof(*orig))) {
 			slot[i].non_stack_access = last->non_stack_access;
 			last->non_stack_access = false;
 		} else if (bpf_is_mem_insn(&patch[i])) {
@@ -454,9 +478,9 @@ static void patch_list_adj_aux(struct bpf_prog *prog, struct bpf_insn_patch *p,
 	    memcmp(&patch[p->len - 1], orig, sizeof(*orig)))
 		last->non_stack_access = true;
 
-	/* indirect jumps to the replaced insn land on the first new one */
-	if (last->indirect_target) {
-		slot[0].indirect_target = 1;
+	/* indirect jumps to the replaced insn land on p->target */
+	if (last->indirect_target && p->target != p->len - 1) {
+		slot[p->target].indirect_target = 1;
 		last->indirect_target = 0;
 	}
 }
@@ -533,8 +557,9 @@ static void patch_list_del_subprogs(struct bpf_verifier_env *env,
 /*
  * Apply all queued patches and removals in one go. Everything that names an
  * insn of the old image follows it to the new one. A patched insn is named by
- * the first insn of its patch, a removed insn by the next insn that stays,
- * like with bpf_patch_insn_data().
+ * the first insn of its patch, or the insn itself if insns were inserted in
+ * front of it, a removed insn by the next insn that stays, like with
+ * bpf_patch_insn_data().
  */
 int bpf_patch_list_commit(struct bpf_verifier_env *env)
 {
@@ -649,7 +674,7 @@ int bpf_patch_list_commit(struct bpf_verifier_env *env)
 
 	for (i = 0; i < env->insn_array_map_cnt; i++)
 		bpf_insn_array_remap(env->insn_array_maps[i], img.new_off,
-				     img.cnt, img.grow);
+				     img.new_tgt, img.cnt, img.grow);
 
 	err = 0;
 out:
Signature · 1 line
2.43.0
#18 lore raw

Re: [PATCH bpf-next v2 12/22] bpf: Teach the patch list to insert in front of an instruction

TL;DR: Nit only: the updated header comment on bpf_patch_list_commit() says everything follows the insn itself after an insertion, but only jumps, insn arrays and poke descriptors do; the code and…
Quoted 1 line

bpf: Teach the patch list to insert in front of an instruction

TL;DR: Nit only: the updated header comment on bpf_patch_list_commit() says everything follows the insn itself after an insertion, but only jumps, insn arrays and poke descriptors do; the code and commit message differ.

Quoted 4 lines
kernel/bpf/fixups.c +0 -0
index a56b743be006..bb4fd75a7062 100644

[ ... ]

kernel/bpf/fixups.c static void patch_list_del_subprogs(struct bpf_verifier_env *env, · line 565

Quoted 12 lines
kernel/bpf/fixups.c +3 -2
@@ -533,8 +557,9 @@ static void patch_list_del_subprogs(struct bpf_verifier_env *env,
 /*
  * Apply all queued patches and removals in one go. Everything that names an
  * insn of the old image follows it to the new one. A patched insn is named by
- * the first insn of its patch, a removed insn by the next insn that stays,
- * like with bpf_patch_insn_data().
+ * the first insn of its patch, or the insn itself if insns were inserted in
+ * front of it, a removed insn by the next insn that stays, like with
+ * bpf_patch_insn_data().
  */
 int bpf_patch_list_commit(struct bpf_verifier_env *env)
 {

This isn't a bug, but is the updated header comment accurate about which users follow the insn itself after an insertion?

It says everything that names an old insn follows it, and that an insn with insns inserted in front of it is named by the insn itself. In bpf_patch_list_commit() that only holds for jumps, insn arrays and poke descriptors, which use img.new_tgt:

    bpf_insn_array_remap(env->insn_array_maps[i], img.new_off,
                         img.new_tgt, img.cnt, img.grow);

Subprog starts, func pointers and line info still use img.new_off, which is the first inserted insn:

    env->subprog_info[i].start = bpf_patch_image_remap(&img, img.new_off, ...)
    fp->xlated_off = bpf_patch_image_remap(&img, img.new_off, fp->xlated_off)

patch_list_adj_insn() also sends calls and ld_imm64 of subprogs to new_off.

The commit message and the comment above __bpf_patch_list_insert() describe this split correctly, so this comment now disagrees with them. Also, "like with bpf_patch_insn_data()" now trails a clause that bpf_patch_insn_data() never implements, since it always uses BPF_PATCH_KEEP_TARGET.

Could the comment say that jumps, instruction arrays and poke descriptors go to the insn itself, while subprogs, line info, function pointers and calls go to the first inserted insn?

---
AI reviewed your patch. Please fix the bug or email reply why it's not a bug.
See: https://github.com/kernel-patches/vmtest/blob/master/ci/claude/README.md

CI run summary: https://github.com/kernel-patches/bpf/actions/runs/41053659762

#19 lore raw

PATCH v2 13/22 bpf: Allow inserting in front of a queued patch

In reply to Qiliang Yuan

bpf_convert_ctx_accesses() inserts the store of the context pointer for the epilogue in front of the first instruction, and then the prologue in front of it as well.

bpf_patch_list_insert() only takes an instruction that has no patch queued yet, so the second insertion is refused.

Put insns inserted in front of a queued patch in front of all of it, and move the patch down behind them the same way as a single instruction.

---
 kernel/bpf/core.c   | 27 +++++++++++++++------------
 kernel/bpf/fixups.c |  2 +-
 2 files changed, 16 insertions(+), 13 deletions(-)
kernel/bpf/core.c +15 -12
index 6e356e16613b3..0447e3b4cfa48 100644
@@ -746,24 +746,27 @@ int __bpf_patch_list_del(struct bpf_patch_list *pl, const struct bpf_prog *prog,
  * Queue 'insns[0..cnt)' to go in front of insn 'off'. Jumps to 'off',
  * instruction arrays and poke descriptors still name the insn at 'off', while
  * subprogs, line info, function pointers and calls that start at 'off' start
- * at the first inserted insn.
+ * at the first inserted insn. Inserting in front of a queued patch puts the
+ * insns in front of it.
  */
 int __bpf_patch_list_insert(struct bpf_patch_list *pl, const struct bpf_prog *prog,
 			    u32 off, const struct bpf_insn *insns, u32 cnt)
 {
-	struct bpf_insn_patch *p;
+	struct bpf_insn_patch *p = pl->cnt ? &pl->patches[pl->cnt - 1] : NULL;
 	int err;
 
-	err = patch_list_reserve_patch(pl) ?: patch_list_reserve_insns(pl, 1);
-	if (err)
-		return err;
-	p = &pl->patches[pl->cnt++];
-	p->off = off;
-	p->len = 1;
-	p->target = 0;
-	p->start = pl->insn_cnt;
-	p->orig = prog->insnsi[off];
-	pl->insns[pl->insn_cnt++] = p->orig;
+	if (!p || off != p->off) {
+		err = patch_list_reserve_patch(pl) ?: patch_list_reserve_insns(pl, 1);
+		if (err)
+			return err;
+		p = &pl->patches[pl->cnt++];
+		p->off = off;
+		p->len = 1;
+		p->target = 0;
+		p->start = pl->insn_cnt;
+		p->orig = prog->insnsi[off];
+		pl->insns[pl->insn_cnt++] = p->orig;
+	}
 
 	err = patch_list_reserve_insns(pl, cnt);
 	if (err)
kernel/bpf/fixups.c +1 -1
index bb4fd75a70624..6d99de1be2581 100644
@@ -429,7 +429,7 @@ int bpf_patch_list_insert(struct bpf_verifier_env *env, u32 off,
 		return -EINTR;
 
 	if (verifier_bug_if(!cnt || off >= env->prog->len ||
-			    (p && off <= p->off),
+			    (p && (off < p->off || (off == p->off && !p->len))),
 			    env, "insns inserted at %u out of order", off))
 		return -EFAULT;
 
Signature · 1 line
2.43.0
#20 lore raw

PATCH v2 14/22 bpf: Move bpf_convert_ctx_accesses() to the patch list

In reply to Qiliang Yuan

bpf_convert_ctx_accesses() patches the program for every context access that it rewrites and every barrier that it adds, one bpf_patch_insn_data() at a time.

Each of these patches costs O(prog->len), so a program with many context accesses pays it once for every one of them.

Queue the prologue, the store of the context pointer for the epilogue and the rewrites, and commit them at the end of the pass. Queue a barrier in front of an instruction before rewriting the instruction, whose rewrite then replaces the last instruction of the barrier. As ops->gen_prologue() ends the prologue with the first instruction of the program, insert the prologue without it with bpf_patch_list_insert(). As the epilogue is now found by its index in the unpatched program, which can be 0, mark that there is none yet with -1.

---
 kernel/bpf/fixups.c | 132 +++++++++++++++++++---------------------------------
 1 file changed, 49 insertions(+), 83 deletions(-)
kernel/bpf/fixups.c +49 -83
index 6d99de1be2581..08c89f2baffb6 100644
@@ -1090,16 +1090,15 @@ int bpf_convert_ctx_accesses(struct bpf_verifier_env *env)
 {
 	struct bpf_subprog_info *subprogs = env->subprog_info;
 	const struct bpf_verifier_ops *ops = env->ops;
-	int i, cnt, size, ctx_field_size, ret, delta = 0, epilogue_cnt = 0;
+	int i, cnt, size, ctx_field_size, ret, epilogue_cnt = 0;
 	const int insn_cnt = env->prog->len;
 	struct bpf_insn *epilogue_buf = env->epilogue_buf;
 	struct bpf_insn *insn_buf = env->insn_buf;
 	struct bpf_insn *insn;
 	u32 target_size, size_default, off;
-	struct bpf_prog *new_prog;
 	enum bpf_access_type type;
 	bool is_narrower_load;
-	int epilogue_idx = 0;
+	int epilogue_idx = -1;
 
 	if (ops->gen_epilogue) {
 		epilogue_cnt = ops->gen_epilogue(epilogue_buf, env->prog,
@@ -1109,17 +1108,12 @@ int bpf_convert_ctx_accesses(struct bpf_verifier_env *env)
 			return -EFAULT;
 		} else if (epilogue_cnt) {
 			/* Save the ARG_PTR_TO_CTX for the epilogue to use */
-			cnt = 0;
 			subprogs[0].stack_depth += 8;
-			insn_buf[cnt++] = BPF_STX_MEM(BPF_DW, BPF_REG_FP, BPF_REG_1,
-						      -subprogs[0].stack_depth);
-			insn_buf[cnt++] = env->prog->insnsi[0];
-			new_prog = __bpf_patch_insn_data(env, 0, insn_buf, cnt,
-							 BPF_PATCH_MOVE_TARGET);
-			if (!new_prog)
-				return -ENOMEM;
-			env->prog = new_prog;
-			delta += cnt - 1;
+			insn_buf[0] = BPF_STX_MEM(BPF_DW, BPF_REG_FP, BPF_REG_1,
+						  -subprogs[0].stack_depth);
+			ret = bpf_patch_list_insert(env, 0, insn_buf, 1);
+			if (ret)
+				return ret;
 
 			ret = add_kfunc_in_insns(env, epilogue_buf, epilogue_cnt - 1);
 			if (ret < 0)
@@ -1150,13 +1144,14 @@ int bpf_convert_ctx_accesses(struct bpf_verifier_env *env)
 						   env->prog->aux->attach_btf_id))
 				return -EINVAL;
 			env->prog->aux->has_prologue = true;
-			new_prog = __bpf_patch_insn_data(env, 0, insn_buf, cnt,
-							 BPF_PATCH_MOVE_TARGET);
-			if (!new_prog)
-				return -ENOMEM;
-
-			env->prog = new_prog;
-			delta += cnt - 1;
+			/* the prologue ends with the first insn of the program */
+			if (verifier_bug_if(memcmp(&insn_buf[cnt - 1], env->prog->insnsi,
+						   sizeof(*insn_buf)), env,
+					    "prologue doesn't end with the first insn"))
+				return -EFAULT;
+			ret = bpf_patch_list_insert(env, 0, insn_buf, cnt - 1);
+			if (ret)
+				return ret;
 
 			ret = add_kfunc_in_insns(env, insn_buf, cnt - 1);
 			if (ret < 0)
@@ -1164,21 +1159,18 @@ int bpf_convert_ctx_accesses(struct bpf_verifier_env *env)
 		}
 	}
 
-	if (delta)
-		WARN_ON(adjust_jmp_off(env->prog, 0, delta));
-
 	if (bpf_prog_is_offloaded(env->prog->aux))
-		return 0;
-
-	insn = env->prog->insnsi + delta;
+		return bpf_patch_list_commit(env);
 
-	for (i = 0; i < insn_cnt; i++, insn++) {
+	for (i = 0; i < insn_cnt; i++) {
 		bpf_convert_ctx_access_t convert_ctx_access;
 		enum bpf_reg_type ptr_type;
 		u8 mode;
 
-		if (env->insn_aux_data[i + delta].nospec) {
-			WARN_ON_ONCE(env->insn_aux_data[i + delta].alu_state);
+		insn = &env->prog->insnsi[i];
+
+		if (env->insn_aux_data[i].nospec) {
+			WARN_ON_ONCE(env->insn_aux_data[i].alu_state);
 			struct bpf_insn *patch = insn_buf;
 
 			*patch++ = BPF_ST_NOSPEC();
@@ -1186,17 +1178,13 @@ int bpf_convert_ctx_accesses(struct bpf_verifier_env *env)
 			ret = bpf_adj_moved_insn(patch++, 1);
 			if (ret) {
 				verbose(env, "insn %d cannot be patched due to 16-bit range\n",
-					env->insn_aux_data[i + delta].orig_idx);
+					env->insn_aux_data[i].orig_idx);
 				return ret;
 			}
 			cnt = patch - insn_buf;
-			new_prog = bpf_patch_insn_data(env, i + delta, insn_buf, cnt);
-			if (!new_prog)
-				return -ENOMEM;
-
-			delta    += cnt - 1;
-			env->prog = new_prog;
-			insn      = new_prog->insnsi + i + delta;
+			insn = bpf_patch_list_add(env, i, insn_buf, cnt);
+			if (IS_ERR(insn))
+				return PTR_ERR(insn);
 			/* This can not be easily merged with the
 			 * nospec_result-case, because an insn may require a
 			 * nospec before and after itself. Therefore also do not
@@ -1226,42 +1214,34 @@ int bpf_convert_ctx_accesses(struct bpf_verifier_env *env)
 			    insn->code == (BPF_STX | BPF_ATOMIC | BPF_H) ||
 			    insn->code == (BPF_STX | BPF_ATOMIC | BPF_W) ||
 			    insn->code == (BPF_STX | BPF_ATOMIC | BPF_DW)) &&
-			   env->insn_aux_data[i + delta].ptr_type == PTR_TO_ARENA) {
+			   env->insn_aux_data[i].ptr_type == PTR_TO_ARENA) {
 			insn->code = BPF_STX | BPF_PROBE_ATOMIC | BPF_SIZE(insn->code);
 			env->prog->aux->num_exentries++;
 			continue;
 		} else if (insn->code == (BPF_STX | BPF_ATOMIC | BPF_DW) &&
 			   insn->imm == BPF_LOAD_ACQ &&
-			   env->insn_aux_data[i + delta].arena_member) {
+			   env->insn_aux_data[i].arena_member) {
 			/* an acquire load of an __arena member is rewritten like a plain load */
-			cnt = arena_member_fixup(env, i + delta, insn, insn_buf);
+			cnt = arena_member_fixup(env, i, insn, insn_buf);
 			if (cnt < 0)
 				return cnt;
-			new_prog = bpf_patch_insn_data(env, i + delta, insn_buf, cnt);
-			if (!new_prog)
-				return -ENOMEM;
-
-			delta    += cnt - 1;
-			env->prog = new_prog;
-			insn      = new_prog->insnsi + i + delta;
+			insn = bpf_patch_list_add(env, i, insn_buf, cnt);
+			if (IS_ERR(insn))
+				return PTR_ERR(insn);
 			continue;
 		} else if (insn->code == (BPF_JMP | BPF_EXIT) &&
 			   epilogue_cnt &&
-			   i + delta < subprogs[1].start) {
+			   i < subprogs[1].start) {
 			/* Generate epilogue for the main prog */
-			if (epilogue_idx) {
+			if (epilogue_idx >= 0) {
 				/* jump back to the earlier generated epilogue */
-				insn_buf[0] = BPF_JMP32_A(epilogue_idx - i - delta - 1);
+				insn_buf[0] = BPF_JMP32_A(epilogue_idx - i - 1);
 				cnt = 1;
 			} else {
 				memcpy(insn_buf, epilogue_buf,
 				       epilogue_cnt * sizeof(*epilogue_buf));
 				cnt = epilogue_cnt;
-				/* epilogue_idx cannot be 0. It must have at
-				 * least one ctx ptr saving insn before the
-				 * epilogue.
-				 */
-				epilogue_idx = i + delta;
+				epilogue_idx = i;
 			}
 			goto patch_insn_buf;
 		} else {
@@ -1269,7 +1249,7 @@ int bpf_convert_ctx_accesses(struct bpf_verifier_env *env)
 		}
 
 		if (type == BPF_WRITE &&
-		    env->insn_aux_data[i + delta].nospec_result) {
+		    env->insn_aux_data[i].nospec_result) {
 			/* nospec_result is only used to mitigate Spectre v4 and
 			 * to limit verification-time for Spectre v1.
 			 */
@@ -1278,17 +1258,13 @@ int bpf_convert_ctx_accesses(struct bpf_verifier_env *env)
 			*patch++ = *insn;
 			*patch++ = BPF_ST_NOSPEC();
 			cnt = patch - insn_buf;
-			new_prog = bpf_patch_insn_data(env, i + delta, insn_buf, cnt);
-			if (!new_prog)
-				return -ENOMEM;
-
-			delta    += cnt - 1;
-			env->prog = new_prog;
-			insn      = new_prog->insnsi + i + delta;
+			insn = bpf_patch_list_add(env, i, insn_buf, cnt);
+			if (IS_ERR(insn))
+				return PTR_ERR(insn);
 			continue;
 		}
 
-		ptr_type = env->insn_aux_data[i + delta].ptr_type;
+		ptr_type = env->insn_aux_data[i].ptr_type;
 		switch ((int)ptr_type) {
 		case PTR_TO_CTX:
 			if (!ops->convert_ctx_access)
@@ -1341,22 +1317,18 @@ int bpf_convert_ctx_accesses(struct bpf_verifier_env *env)
 				return -EFAULT;
 			}
 
-			cnt = arena_member_fixup(env, i + delta, insn, insn_buf);
+			cnt = arena_member_fixup(env, i, insn, insn_buf);
 			if (cnt < 0)
 				return cnt;
 			if (!cnt)
 				continue;
-			new_prog = bpf_patch_insn_data(env, i + delta, insn_buf, cnt);
-			if (!new_prog)
-				return -ENOMEM;
-
-			delta    += cnt - 1;
-			env->prog = new_prog;
-			insn      = new_prog->insnsi + i + delta;
+			insn = bpf_patch_list_add(env, i, insn_buf, cnt);
+			if (IS_ERR(insn))
+				return PTR_ERR(insn);
 			continue;
 		}
 
-		ctx_field_size = env->insn_aux_data[i + delta].ctx_field_size;
+		ctx_field_size = env->insn_aux_data[i].ctx_field_size;
 		size = BPF_LDST_BYTES(insn);
 		mode = BPF_MODE(insn->code);
 
@@ -1424,18 +1396,12 @@ int bpf_convert_ctx_accesses(struct bpf_verifier_env *env)
 						       size * 8, 0);
 
 patch_insn_buf:
-		new_prog = bpf_patch_insn_data(env, i + delta, insn_buf, cnt);
-		if (!new_prog)
-			return -ENOMEM;
-
-		delta += cnt - 1;
-
-		/* keep walking new program and skip insns we just inserted */
-		env->prog = new_prog;
-		insn      = new_prog->insnsi + i + delta;
+		insn = bpf_patch_list_add(env, i, insn_buf, cnt);
+		if (IS_ERR(insn))
+			return PTR_ERR(insn);
 	}
 
-	return 0;
+	return bpf_patch_list_commit(env);
 }
 
 static u32 *bpf_dup_subprog_starts(struct bpf_verifier_env *env)
Signature · 1 line
2.43.0
#21 lore raw

Re: [PATCH bpf-next v2 14/22] bpf: Move bpf_convert_ctx_accesses() to the patch list

Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider: - [Critical] bpf: lost in-place insn 0 rewrites in bpf_convert_ctx_accesses() --

Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
- [Critical] bpf: lost in-place insn 0 rewrites in bpf_convert_ctx_accesses() --

commit 4384b7c62a67d8070d7d3e407afbbb78ae703556
Author: Qiliang Yuan <[email protected]>

bpf: Move bpf_convert_ctx_accesses() to the patch list

This commit converts bpf_convert_ctx_accesses() from patching instructions immediately via bpf_patch_insn_data() to queuing prologues, epilogue context stores, and instruction rewrites in env->patch_list and committing them at the end of the pass.

Quoted 90 lines
kernel/bpf/fixups.c +18 -29
index 6d99de1be2581..08c89f2baffb6 100644
@@ -1090,16 +1090,15 @@ int bpf_convert_ctx_accesses(struct bpf_verifier_env *env)
 {
 	struct bpf_subprog_info *subprogs = env->subprog_info;
 	const struct bpf_verifier_ops *ops = env->ops;
-	int i, cnt, size, ctx_field_size, ret, delta = 0, epilogue_cnt = 0;
+	int i, cnt, size, ctx_field_size, ret, epilogue_cnt = 0;
 	const int insn_cnt = env->prog->len;
 	struct bpf_insn *epilogue_buf = env->epilogue_buf;
 	struct bpf_insn *insn_buf = env->insn_buf;
 	struct bpf_insn *insn;
 	u32 target_size, size_default, off;
-	struct bpf_prog *new_prog;
 	enum bpf_access_type type;
 	bool is_narrower_load;
-	int epilogue_idx = 0;
+	int epilogue_idx = -1;
 
 	if (ops->gen_epilogue) {
 		epilogue_cnt = ops->gen_epilogue(epilogue_buf, env->prog,
@@ -1109,17 +1108,12 @@ int bpf_convert_ctx_accesses(struct bpf_verifier_env *env)
 			return -EFAULT;
 		} else if (epilogue_cnt) {
 			/* Save the ARG_PTR_TO_CTX for the epilogue to use */
-			cnt = 0;
 			subprogs[0].stack_depth += 8;
-			insn_buf[cnt++] = BPF_STX_MEM(BPF_DW, BPF_REG_FP, BPF_REG_1,
-						      -subprogs[0].stack_depth);
-			insn_buf[cnt++] = env->prog->insnsi[0];
-			new_prog = __bpf_patch_insn_data(env, 0, insn_buf, cnt,
-							 BPF_PATCH_MOVE_TARGET);
-			if (!new_prog)
-				return -ENOMEM;
-			env->prog = new_prog;
-			delta += cnt - 1;
+			insn_buf[0] = BPF_STX_MEM(BPF_DW, BPF_REG_FP, BPF_REG_1,
+						  -subprogs[0].stack_depth);
+			ret = bpf_patch_list_insert(env, 0, insn_buf, 1);
+			if (ret)
+				return ret;
 
 			ret = add_kfunc_in_insns(env, epilogue_buf, epilogue_cnt - 1);
 			if (ret < 0)
@@ -1150,13 +1144,14 @@ int bpf_convert_ctx_accesses(struct bpf_verifier_env *env)
 						   env->prog->aux->attach_btf_id))
 				return -EINVAL;
 			env->prog->aux->has_prologue = true;
-			new_prog = __bpf_patch_insn_data(env, 0, insn_buf, cnt,
-							 BPF_PATCH_MOVE_TARGET);
-			if (!new_prog)
-				return -ENOMEM;
-
-			env->prog = new_prog;
-			delta += cnt - 1;
+			/* the prologue ends with the first insn of the program */
+			if (verifier_bug_if(memcmp(&insn_buf[cnt - 1], env->prog->insnsi,
+						   sizeof(*insn_buf)), env,
+					    "prologue doesn't end with the first insn"))
+				return -EFAULT;
+			ret = bpf_patch_list_insert(env, 0, insn_buf, cnt - 1);
+			if (ret)
+				return ret;
 
 			ret = add_kfunc_in_insns(env, insn_buf, cnt - 1);
 			if (ret < 0)
@@ -1164,21 +1159,18 @@ int bpf_convert_ctx_accesses(struct bpf_verifier_env *env)
 		}
 	}
 
-	if (delta)
-		WARN_ON(adjust_jmp_off(env->prog, 0, delta));
-
 	if (bpf_prog_is_offloaded(env->prog->aux))
-		return 0;
-
-	insn = env->prog->insnsi + delta;
+		return bpf_patch_list_commit(env);
 
-	for (i = 0; i < insn_cnt; i++, insn++) {
+	for (i = 0; i < insn_cnt; i++) {
 		bpf_convert_ctx_access_t convert_ctx_access;
 		enum bpf_reg_type ptr_type;
 		u8 mode;
 
-		if (env->insn_aux_data[i + delta].nospec) {
-			WARN_ON_ONCE(env->insn_aux_data[i + delta].alu_state);
+		insn = &env->prog->insnsi[i];

[ ... ]

kernel/bpf/fixups.c int bpf_convert_ctx_accesses(struct bpf_verifier_env *env) · line 1220

Quoted 9 lines
kernel/bpf/fixups.c +1 -1
@@ -1226,42 +1214,34 @@ int bpf_convert_ctx_accesses(struct bpf_verifier_env *env)
 			    insn->code == (BPF_STX | BPF_ATOMIC | BPF_H) ||
 			    insn->code == (BPF_STX | BPF_ATOMIC | BPF_W) ||
 			    insn->code == (BPF_STX | BPF_ATOMIC | BPF_DW)) &&
-			   env->insn_aux_data[i + delta].ptr_type == PTR_TO_ARENA) {
+			   env->insn_aux_data[i].ptr_type == PTR_TO_ARENA) {
 			insn->code = BPF_STX | BPF_PROBE_ATOMIC | BPF_SIZE(insn->code);
 			env->prog->aux->num_exentries++;
 			continue;

[Severity: Critical]
When ops->gen_epilogue or ops->gen_prologue emits instructions before the loop in bpf_convert_ctx_accesses(), bpf_patch_list_insert(env, 0, ...) creates a patch entry at offset 0 in env->patch_list and copies the unpatched env->prog->insnsi[0] into env->patch_list.insns.

In the loop, insn is initialized to &env->prog->insnsi[i]. When i == 0 and env->insn_aux_data[0].nospec is false, several branches modify insn->code in place and execute continue without calling bpf_patch_list_add():

1. PTR_TO_ARENA atomic operations rewritten to BPF_STX | BPF_PROBE_ATOMIC:

	insn->code = BPF_STX | BPF_PROBE_ATOMIC | BPF_SIZE(insn->code);
	env->prog->aux->num_exentries++;
	continue;

2. PTR_TO_ARENA loads and stores rewritten to BPF_PROBE_MEM32SX or BPF_PROBE_MEM32:

	if (BPF_MODE(insn->code) == BPF_MEMSX) {
		...
		insn->code = BPF_CLASS(insn->code) | BPF_PROBE_MEM32SX | BPF_SIZE(insn->code);
	} else {
		insn->code = BPF_CLASS(insn->code) | BPF_PROBE_MEM32 | BPF_SIZE(insn->code);
	}
	env->prog->aux->num_exentries++;
	continue;

3. Fault-prone pointer loads (bpf_may_fault_on_deref(ptr_type)) rewritten to BPF_LDX | BPF_PROBE_MEM or BPF_LDX | BPF_PROBE_MEMSX when arena_member_fixup() returns 0:

	if (BPF_MODE(insn->code) == BPF_MEM)
		insn->code = BPF_LDX | BPF_PROBE_MEM |
			     BPF_SIZE(insn->code);
	else
		insn->code = BPF_LDX | BPF_PROBE_MEMSX |
			     BPF_SIZE(insn->code);
	env->prog->aux->num_exentries++;

Because those branches only mutate env->prog->insnsi[0].code and do not update the copy already queued in env->patch_list.insns (nor call bpf_patch_list_add()), won't bpf_patch_list_commit() overwrite instruction 0 with the unpatched copy from env->patch_list.insns, losing the BPF_PROBE_ATOMIC, BPF_PROBE_MEM32, or BPF_PROBE_MEM rewrite and leaving the instruction without arena address relocation or exception table protection?

Signature · 1 line
Sashiko AI review · https://sashiko.dev/#/patchset/[email protected]?part=14
#22 lore raw

PATCH v2 15/22 bpf: Insert the may_goto counter setup through the patch list

In reply to Qiliang Yuan

bpf_do_misc_fixups() sets up the counter of may_goto in front of each subprog that needs one.

It patches the program for each of these subprogs, and then walks all jumps again with adjust_jmp_off() to move the ones to the first instruction of the subprog past the setup.

Insert the setup with bpf_patch_list_insert(), which leaves the jumps to the instruction it inserts in front of on that instruction, and commit once. adjust_jmp_off() has no users left, remove it.

---
 kernel/bpf/fixups.c | 73 ++++++++---------------------------------------------
 1 file changed, 10 insertions(+), 63 deletions(-)
kernel/bpf/fixups.c +10 -63
index 08c89f2baffb6..f55ac904b4e78 100644
@@ -723,44 +723,6 @@ static int bpf_adj_moved_insn(struct bpf_insn *insn, u32 delta)
 	return 0;
 }
 
-/*
- * For all jmp insns in a given 'prog' that point to 'tgt_idx' insn adjust the
- * jump offset by 'delta'.
- */
-static int adjust_jmp_off(struct bpf_prog *prog, u32 tgt_idx, u32 delta)
-{
-	struct bpf_insn *insn = prog->insnsi;
-	u32 insn_cnt = prog->len, i;
-	s32 imm;
-	s16 off;
-
-	for (i = 0; i < insn_cnt; i++, insn++) {
-		u8 code = insn->code;
-
-		if (tgt_idx <= i && i < tgt_idx + delta)
-			continue;
-
-		if ((BPF_CLASS(code) != BPF_JMP && BPF_CLASS(code) != BPF_JMP32) ||
-		    BPF_OP(code) == BPF_CALL || BPF_OP(code) == BPF_EXIT)
-			continue;
-
-		if (insn->code == (BPF_JMP32 | BPF_JA)) {
-			if (i + 1 + insn->imm != tgt_idx)
-				continue;
-			if (check_add_overflow(insn->imm, delta, &imm))
-				return -ERANGE;
-			insn->imm = imm;
-		} else {
-			if (i + 1 + insn->off != tgt_idx)
-				continue;
-			if (check_add_overflow(insn->off, delta, &off))
-				return -ERANGE;
-			insn->off = off;
-		}
-	}
-	return 0;
-}
-
 /* Clean up dynamically allocated fields of aux data for instructions [start, ...] */
 void bpf_clear_insn_aux_data(struct bpf_verifier_env *env, int start, int len)
 {
@@ -1988,7 +1950,6 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env)
 	const struct bpf_map_ops *ops;
 	struct bpf_insn_aux_data *aux;
 	struct bpf_insn *insn_buf = env->insn_buf;
-	struct bpf_prog *new_prog;
 	struct bpf_map *map_ptr;
 	int i, ret, cnt, cur_subprog = 0;
 	struct bpf_subprog_info *subprogs = env->subprog_info;
@@ -2828,10 +2789,8 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env)
 
 	env->prog->aux->stack_depth = subprogs[0].stack_depth;
 	for (i = 0; i < env->subprog_cnt; i++) {
-		int delta = bpf_jit_supports_timed_may_goto() ? 2 : 1;
-		int subprog_start = subprogs[i].start;
+		int slots = bpf_jit_supports_timed_may_goto() ? 2 : 1;
 		int stack_slots = subprogs[i].stack_extra / 8;
-		int slots = delta, cnt = 0;
 
 		if (!stack_slots)
 			continue;
@@ -2841,6 +2800,7 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env)
 			return -EFAULT;
 		}
 
+		cnt = 0;
 		stack_depth = subprogs[i].stack_depth;
 		if (bpf_jit_supports_timed_may_goto()) {
 			insn_buf[cnt++] = BPF_ST_MEM(BPF_DW, BPF_REG_FP, -stack_depth,
@@ -2851,30 +2811,17 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env)
 			insn_buf[cnt++] = BPF_ST_MEM(BPF_DW, BPF_REG_FP, -stack_depth,
 						     BPF_MAX_LOOPS);
 		}
-		/* Copy first actual insn to preserve it */
-		insn_buf[cnt] = env->prog->insnsi[subprog_start];
-		ret = bpf_adj_moved_insn(&insn_buf[cnt], cnt);
-		if (ret) {
-			verbose(env, "insn %d cannot be patched due to 16-bit range\n",
-				env->insn_aux_data[subprog_start].orig_idx);
+		/* jumps to the first insn of the subprog skip the setup */
+		ret = bpf_patch_list_insert(env, subprogs[i].start, insn_buf, cnt);
+		if (ret)
 			return ret;
-		}
-		cnt++;
-
-		new_prog = __bpf_patch_insn_data(env, subprog_start, insn_buf, cnt,
-						 BPF_PATCH_MOVE_TARGET);
-		if (!new_prog)
-			return -ENOMEM;
-		env->prog = prog = new_prog;
-		/*
-		 * If may_goto is a first insn of a prog there could be a jmp
-		 * insn that points to it, hence adjust all such jmps to point
-		 * to insn after BPF_ST that inits may_goto count.
-		 * Adjustment will succeed because bpf_patch_insn_data() didn't fail.
-		 */
-		WARN_ON(adjust_jmp_off(env->prog, subprog_start, delta));
 	}
 
+	ret = bpf_patch_list_commit(env);
+	if (ret)
+		return ret;
+	prog = env->prog;
+
 	/* Since poke tab is now finalized, publish aux to tracker. */
 	for (i = 0; i < prog->aux->size_poke_tab; i++) {
 		map_ptr = prog->aux->poke_tab[i].tail_call.map;
Signature · 1 line
2.43.0
#23 lore raw

PATCH v2 16/22 bpf: Append the hidden subprog through the patch list

In reply to Qiliang Yuan

add_hidden_subprog() appends the subprog for the exception callback by patching the last instruction of the program with itself followed by the new instructions.

It does that with bpf_patch_insn_data(), which is going away once all passes use the patch list.

Queue that patch with bpf_patch_list_add() and commit it right away.

---
 kernel/bpf/fixups.c | 17 ++++++++++-------
 1 file changed, 10 insertions(+), 7 deletions(-)
kernel/bpf/fixups.c +10 -7
index f55ac904b4e78..84aaaa4632aa3 100644
@@ -1865,7 +1865,8 @@ int bpf_fixup_call_args(struct bpf_verifier_env *env)
 static int add_hidden_subprog(struct bpf_verifier_env *env, struct bpf_insn *patch, int len)
 {
 	struct bpf_subprog_info *info = env->subprog_info;
-	int cnt = env->subprog_cnt;
+	int err, cnt = env->subprog_cnt;
+	struct bpf_insn *last;
 	struct bpf_prog *prog;
 
 	/* We only reserve one slot for hidden subprogs in subprog_info. */
@@ -1874,13 +1875,15 @@ static int add_hidden_subprog(struct bpf_verifier_env *env, struct bpf_insn *pat
 		return -EFAULT;
 	}
 	/* We're not patching any existing instruction, just appending the new
-	 * ones for the hidden subprog. Hence all of the adjustment operations
-	 * in bpf_patch_insn_data are no-ops.
+	 * ones for the hidden subprog.
 	 */
-	prog = bpf_patch_insn_data(env, env->prog->len - 1, patch, len);
-	if (!prog)
-		return -ENOMEM;
-	env->prog = prog;
+	last = bpf_patch_list_add(env, env->prog->len - 1, patch, len);
+	if (IS_ERR(last))
+		return PTR_ERR(last);
+	err = bpf_patch_list_commit(env);
+	if (err)
+		return err;
+	prog = env->prog;
 	info[cnt + 1].start = info[cnt].start;
 	info[cnt].start = prog->len - len + 1;
 	/* The patch ends with the exit. */
Signature · 1 line
2.43.0
#24 lore raw

PATCH v2 17/22 bpf: Inline bpf_loop() calls through the patch list

In reply to Qiliang Yuan

bpf_optimize_bpf_loop() patches the program for every bpf_loop() call that it inlines, then points the call in the patch to the callback with the start of the callback subprog after patching.

Each inlining costs O(prog->len), and the call can't be pointed to the callback before the patch is applied.

Queue the patches and commit them once. Set the call relative to the patch placed at the bpf_loop() call in the unpatched program, adding the growth of the patch itself for a callback behind it.

---
 kernel/bpf/fixups.c | 62 +++++++++++++++++++++--------------------------------
 1 file changed, 24 insertions(+), 38 deletions(-)
kernel/bpf/fixups.c +24 -38
index 84aaaa4632aa3..217771aca0161 100644
@@ -2845,11 +2845,8 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env)
 	return 0;
 }
 
-static struct bpf_prog *inline_bpf_loop(struct bpf_verifier_env *env,
-					int position,
-					s32 stack_base,
-					u32 callback_subprogno,
-					u32 *total_cnt)
+static int inline_bpf_loop(struct bpf_verifier_env *env, int position,
+			   s32 stack_base, u32 callback_subprogno)
 {
 	s32 r6_offset = stack_base + 0 * BPF_REG_SIZE;
 	s32 r7_offset = stack_base + 1 * BPF_REG_SIZE;
@@ -2859,9 +2856,8 @@ static struct bpf_prog *inline_bpf_loop(struct bpf_verifier_env *env,
 	int reg_loop_ctx = BPF_REG_8;
 
 	struct bpf_insn *insn_buf = env->insn_buf;
-	struct bpf_prog *new_prog;
 	u32 callback_start;
-	u32 call_insn_offset;
+	struct bpf_insn *last;
 	s32 callback_offset;
 	u32 cnt = 0;
 
@@ -2887,9 +2883,7 @@ static struct bpf_prog *inline_bpf_loop(struct bpf_verifier_env *env,
 	 * if reg_loop_cnt >= reg_loop_max skip the loop body
 	 */
 	insn_buf[cnt++] = BPF_JMP_REG(BPF_JGE, reg_loop_cnt, reg_loop_max, 5);
-	/* callback call,
-	 * correct callback offset would be set after patching
-	 */
+	/* callback call, the offset is set below */
 	insn_buf[cnt++] = BPF_MOV64_REG(BPF_REG_1, reg_loop_cnt);
 	insn_buf[cnt++] = BPF_MOV64_REG(BPF_REG_2, reg_loop_ctx);
 	insn_buf[cnt++] = BPF_CALL_REL(0);
@@ -2906,19 +2900,19 @@ static struct bpf_prog *inline_bpf_loop(struct bpf_verifier_env *env,
 	insn_buf[cnt++] = BPF_LDX_MEM(BPF_DW, BPF_REG_7, BPF_REG_10, r7_offset);
 	insn_buf[cnt++] = BPF_LDX_MEM(BPF_DW, BPF_REG_8, BPF_REG_10, r8_offset);
 
-	*total_cnt = cnt;
-	new_prog = bpf_patch_insn_data(env, position, insn_buf, cnt);
-	if (!new_prog)
-		return new_prog;
-
-	/* callback start is known only after patching */
+	/*
+	 * Note: insn_buf[12] is the BPF_CALL_REL instruction. Jumps out of a
+	 * patch are relative to it in place, which takes the place of 'cnt'
+	 * insns behind 'position'.
+	 */
 	callback_start = env->subprog_info[callback_subprogno].start;
-	/* Note: insn_buf[12] is an offset of BPF_CALL_REL instruction */
-	call_insn_offset = position + 12;
-	callback_offset = callback_start - call_insn_offset - 1;
-	new_prog->insnsi[call_insn_offset].imm = callback_offset;
+	callback_offset = callback_start - position;
+	if (callback_start > position)
+		callback_offset += cnt - 1;
+	insn_buf[12].imm = callback_offset - 12 - 1;
 
-	return new_prog;
+	last = bpf_patch_list_add(env, position, insn_buf, cnt);
+	return PTR_ERR_OR_ZERO(last);
 }
 
 static bool is_bpf_loop_call(struct bpf_insn *insn)
@@ -2940,7 +2934,7 @@ static bool is_bpf_loop_call(struct bpf_insn *insn)
 int bpf_optimize_bpf_loop(struct bpf_verifier_env *env)
 {
 	struct bpf_subprog_info *subprogs = env->subprog_info;
-	int i, cur_subprog = 0, cnt, delta = 0;
+	int i, cur_subprog = 0, err;
 	struct bpf_insn *insn = env->prog->insnsi;
 	int insn_cnt = env->prog->len;
 	u16 stack_depth = subprogs[cur_subprog].stack_depth;
@@ -2949,26 +2943,18 @@ int bpf_optimize_bpf_loop(struct bpf_verifier_env *env)
 
 	for (i = 0; i < insn_cnt; i++, insn++) {
 		struct bpf_loop_inline_state *inline_state =
-			&env->insn_aux_data[i + delta].loop_inline_state;
+			&env->insn_aux_data[i].loop_inline_state;
 
 		if (is_bpf_loop_call(insn) && inline_state->fit_for_inline) {
-			struct bpf_prog *new_prog;
-
 			stack_depth_extra = BPF_REG_SIZE * 3 + stack_depth_roundup;
-			new_prog = inline_bpf_loop(env,
-						   i + delta,
-						   -(stack_depth + stack_depth_extra),
-						   inline_state->callback_subprogno,
-						   &cnt);
-			if (!new_prog)
-				return -ENOMEM;
-
-			delta     += cnt - 1;
-			env->prog  = new_prog;
-			insn       = new_prog->insnsi + i + delta;
+			err = inline_bpf_loop(env, i,
+					      -(stack_depth + stack_depth_extra),
+					      inline_state->callback_subprogno);
+			if (err)
+				return err;
 		}
 
-		if (subprogs[cur_subprog + 1].start == i + delta + 1) {
+		if (subprogs[cur_subprog + 1].start == i + 1) {
 			subprogs[cur_subprog].stack_depth += stack_depth_extra;
 			cur_subprog++;
 			stack_depth = subprogs[cur_subprog].stack_depth;
@@ -2979,7 +2965,7 @@ int bpf_optimize_bpf_loop(struct bpf_verifier_env *env)
 
 	env->prog->aux->stack_depth = env->subprog_info[0].stack_depth;
 
-	return 0;
+	return bpf_patch_list_commit(env);
 }
 
 /* Remove unnecessary spill/fill pairs, members of fastcall pattern,
Signature · 1 line
2.43.0
#25 lore raw

PATCH v2 18/22 bpf: Apply the patch list without a verifier env

In reply to Qiliang Yuan

Rewrites outside of the verifier, like the blinding of constants in classic BPF programs, have no verifier env, and core.c is built without the verifier as well.

bpf_patch_list_commit() needs the env for the aux data and the tables of the verifier, so these rewrites can't use the patch list.

Add bpf_patch_list_apply(), which builds the new image of a program, puts it in place and moves its poke descriptors and line info along. Without the aux data and the tables of the verifier, it can't remove instructions.

---
 include/linux/bpf_verifier.h |  1 +
 kernel/bpf/core.c            | 31 +++++++++++++++++++++++++++++++
 2 files changed, 32 insertions(+)
include/linux/bpf_verifier.h +1 -0
index 9562665757a79..b133bbaf614ac 100644
@@ -1118,6 +1118,7 @@ int bpf_patch_list_build(const struct bpf_patch_list *pl, const struct bpf_prog
 			 struct bpf_patch_image *img);
 void bpf_patch_image_free(struct bpf_patch_image *img);
 void bpf_patch_image_install(struct bpf_prog *prog, const struct bpf_patch_image *img);
+struct bpf_prog *bpf_patch_list_apply(struct bpf_prog *prog, struct bpf_patch_list *pl);
 
 /* single container for all structs
  * one verifier_env per bpf_check() call
kernel/bpf/core.c +31 -0
index 0447e3b4cfa48..10d2c37f81280 100644
@@ -880,6 +880,37 @@ void bpf_patch_image_install(struct bpf_prog *prog, const struct bpf_patch_image
 					      prog->aux->linfo[i].insn_off);
 }
 
+/*
+ * Apply the patches queued for 'prog' without a verifier env, which can't
+ * remove insns. Return the patched program, which may have moved.
+ */
+struct bpf_prog *bpf_patch_list_apply(struct bpf_prog *prog, struct bpf_patch_list *pl)
+{
+	struct bpf_patch_image img;
+	struct bpf_prog *new;
+	int err;
+
+	if (!pl->cnt)
+		return prog;
+
+	err = bpf_patch_list_build(pl, prog, &img);
+	if (!err && WARN_ON_ONCE(img.del))
+		err = -EINVAL;
+	if (!err) {
+		new = bpf_prog_realloc(prog, bpf_prog_size(img.new_cnt), GFP_USER);
+		if (new) {
+			prog = new;
+			bpf_patch_image_install(prog, &img);
+		} else {
+			err = -ENOMEM;
+		}
+	}
+
+	bpf_patch_image_free(&img);
+	bpf_patch_list_release(pl);
+	return err ? ERR_PTR(err) : prog;
+}
+
 static void bpf_prog_kallsyms_del_subprogs(struct bpf_prog *fp)
 {
 	int i;
Signature · 1 line
2.43.0
#26 lore raw

PATCH v2 19/22 bpf: Blind constants through the patch list

In reply to Qiliang Yuan

bpf_jit_blind_constants() patches the program for every instruction whose constant it blinds, with bpf_patch_insn_data() under the verifier and bpf_patch_insn_single() otherwise.

Each of these patches costs O(prog->len). With bpf_jit_harden=2, loading the program of a million instructions from test_verifier's "ld_dw: xor semi-random 64 bit imms, test 5" doesn't finish in 15 minutes.

Queue the rewrites and commit them once, through the verifier env when there is one and with bpf_patch_list_apply() otherwise. Add stubs of the verifier env helpers that core.c calls, for builds without the verifier.

With bpf_jit_harden=2, perf stat -r10 -- veristat -q <obj> averaged over two runs, and test 5 timed once, x86_64 VM with 32 vCPUs, before and after this patch:

              before        after
  pyperf180   3.173 s       0.368 s
  pyperf600   9.793 s       0.907 s
  test 5      > 900 s       5 s
---
 include/linux/bpf_verifier.h | 17 +++++++++++
 kernel/bpf/core.c            | 73 +++++++++++++++++++++++---------------------
 2 files changed, 56 insertions(+), 34 deletions(-)
include/linux/bpf_verifier.h +17 -0
index b133bbaf614ac..cf93d473e4f0c 100644
@@ -2075,10 +2075,27 @@ int bpf_jit_subprogs(struct bpf_verifier_env *env);
 int bpf_fixup_call_args(struct bpf_verifier_env *env);
 int bpf_do_misc_fixups(struct bpf_verifier_env *env);
 int bpf_insn_def32(struct bpf_prog *prog, struct bpf_insn *insn);
+#ifdef CONFIG_BPF_SYSCALL
 struct bpf_insn *bpf_patch_list_add(struct bpf_verifier_env *env, u32 off,
 				    const struct bpf_insn *patch, u32 len);
 int bpf_patch_list_commit(struct bpf_verifier_env *env);
 void bpf_patch_list_free(struct bpf_verifier_env *env);
+#else
+static inline struct bpf_insn *bpf_patch_list_add(struct bpf_verifier_env *env, u32 off,
+						  const struct bpf_insn *patch, u32 len)
+{
+	return ERR_PTR(-EOPNOTSUPP);
+}
+
+static inline int bpf_patch_list_commit(struct bpf_verifier_env *env)
+{
+	return -EOPNOTSUPP;
+}
+
+static inline void bpf_patch_list_free(struct bpf_verifier_env *env)
+{
+}
+#endif
 int bpf_patch_list_del(struct bpf_verifier_env *env, u32 off);
 int bpf_patch_list_insert(struct bpf_verifier_env *env, u32 off,
 			  const struct bpf_insn *insns, u32 cnt);
kernel/bpf/core.c +39 -34

98 lines not on this page · raw message

Signature · 1 line
2.43.0
#27 lore raw

Re: [PATCH bpf-next v2 19/22] bpf: Blind constants through the patch list

TL;DR: Nit in bpf_jit_blind_constants() error path: the comment about patching repointing aux->prog during realloc looks stale now that the patch list reallocs only when nothing can fail; "clone =…
Quoted 1 line

bpf: Blind constants through the patch list

TL;DR: Nit in bpf_jit_blind_constants() error path: the comment about patching repointing aux->prog during realloc looks stale now that the patch list reallocs only when nothing can fail; "clone = env->prog" may be a no-op.

Quoted 4 lines
kernel/bpf/core.c +0 -0
index 10d2c37f8128..7d58c47b73f0 100644

[ ... ]

Quoted 1 line
kernel/bpf/core.c +0 -0
@@ -1990,47 +1990,52 @@ struct bpf_prog *bpf_jit_blind_constants(struct bpf_verifier_env *env, struct bp

[ ... ]

kernel/bpf/core.c struct bpf_prog *bpf_jit_blind_constants(struct bpf_verifier_env *env, struct bp · line 2028

Quoted 13 lines
kernel/bpf/core.c +13 -0
+	if (err) {
+		if (env) {
+			bpf_patch_list_free(env);
+			/* restore the original prog */
+			clone = env->prog;
+			env->prog = prog;
+		}
+		bpf_patch_list_release(&pl);
+		/* Patching may have repointed aux->prog during
+		 * realloc from the original one, so we need to
+		 * fix it up here on error.
+		 */
+		bpf_jit_prog_release_other(prog, clone);

Does this comment still describe a case that can happen?

Before this patch each bpf_patch_insn_data() or bpf_patch_insn_single() call could bpf_prog_realloc() the clone, which does fp->aux->prog = fp, and a later patch could still fail. The error path therefore had to point the shared aux->prog back at the original program.

With the patch list the clone is only reallocated at a point where nothing can fail afterwards:

bpf_patch_list_commit():

	prog = bpf_prog_realloc(prog, bpf_prog_size(img.new_cnt), GFP_USER);
	if (!prog)
		goto out;
	env->prog = prog;
	... (only void steps follow) ...
	err = 0;

bpf_patch_list_apply():

	new = bpf_prog_realloc(prog, bpf_prog_size(img.new_cnt), GFP_USER);
	if (new) {
		prog = new;
		bpf_patch_image_install(prog, &img);
	} else {
		err = -ENOMEM;
	}

So when err is non-zero the clone was never reallocated. aux->prog still points at the original prog, since bpf_prog_clone_create() only memcpy()s, and env->prog is still the clone. That also makes the new "clone = env->prog;" a no-op.

bpf_jit_prog_release_other() is still needed to free the clone, but "Patching may have repointed aux->prog during realloc" can no longer happen here.

Should the comment be updated, for example to say that the patches are only applied once nothing can fail, so the clone just needs to be freed here?

---
AI reviewed your patch. Please fix the bug or email reply why it's not a bug.
See: https://github.com/kernel-patches/vmtest/blob/master/ci/claude/README.md

CI run summary: https://github.com/kernel-patches/bpf/actions/runs/41053659762

#28 lore raw

PATCH v2 20/22 bpf: Remove the old instruction patching code

In reply to Qiliang Yuan

bpf_patch_insn_data() and bpf_patch_insn_single() patch the program right away, with helpers that adjust the branches, line info, aux data, subprogs, function pointers and instruction arrays after each patch. bpf_remove_insns() and the helpers that adjust function pointers and instruction arrays do the same for removed instructions.

Every pass goes through the patch list now, so none of this code has any users left.

Remove bpf_patch_insn_data(), bpf_patch_insn_single(), bpf_remove_insns() and their helpers, and update the comment of bpf_rewrite_must_abort(), whose callers only queue patches now.

---
 include/linux/bpf.h          |   2 -
 include/linux/bpf_verifier.h |   2 -
 include/linux/filter.h       |  16 ----
 kernel/bpf/bpf_insn_array.c  |  34 --------
 kernel/bpf/core.c            | 193 ------------------------------------------
 kernel/bpf/fixups.c          | 194 +++----------------------------------------
 kernel/bpf/verifier.c        |  45 ----------
 7 files changed, 13 insertions(+), 473 deletions(-)
include/linux/bpf.h +0 -2
index bc8db33ceac32..63f86e2eec8b7 100644
@@ -4376,8 +4376,6 @@ struct bpf_prog *bpf_prog_find_from_stack(void);
 int bpf_insn_array_init(struct bpf_map *map, const struct bpf_prog *prog);
 int bpf_insn_array_ready(struct bpf_map *map);
 void bpf_insn_array_release(struct bpf_map *map);
-void bpf_insn_array_adjust(struct bpf_map *map, u32 first, u32 len);
-void bpf_insn_array_adjust_after_remove(struct bpf_map *map, u32 off, u32 len);
 void bpf_insn_array_remap(struct bpf_map *map, const u32 *new_off, const u32 *new_tgt,
 			  u32 cnt, s32 grow);
 
include/linux/bpf_verifier.h +0 -2
index cf93d473e4f0c..9c9397dcdf15e 100644
@@ -1591,8 +1591,6 @@ struct bpf_func_ptr *bpf_map_func_ptrs(struct bpf_verifier_env *env,
 struct bpf_func_ptr *bpf_map_range_func_ptrs(struct bpf_verifier_env *env,
 					     const struct bpf_map *map,
 					     u64 off, u64 size, u32 *cnt);
-void bpf_adjust_func_ptrs(struct bpf_verifier_env *env, u32 off, u32 len);
-void bpf_adjust_func_ptrs_after_remove(struct bpf_verifier_env *env, u32 off, u32 len);
 int bpf_map_direct_read(struct bpf_map *map, int off, int size, u64 *val,
 			bool is_ldsx);
 
include/linux/filter.h +0 -16
index e0218e677a1dc..75545657b5c62 100644
@@ -1339,22 +1339,6 @@ static inline bool bpf_dump_raw_ok(const struct cred *cred)
 	return kallsyms_show_value(cred);
 }
 
-struct bpf_prog *bpf_patch_insn_single(struct bpf_prog *prog, u32 off,
-				       const struct bpf_insn *patch, u32 len);
-
-#ifdef CONFIG_BPF_SYSCALL
-struct bpf_prog *bpf_patch_insn_data(struct bpf_verifier_env *env, u32 off,
-				     const struct bpf_insn *patch, u32 len);
-#else
-static inline struct bpf_prog *bpf_patch_insn_data(struct bpf_verifier_env *env, u32 off,
-						   const struct bpf_insn *patch, u32 len)
-{
-	return ERR_PTR(-ENOTSUPP);
-}
-#endif /* CONFIG_BPF_SYSCALL */
-
-int bpf_remove_insns(struct bpf_prog *prog, u32 off, u32 cnt);
-
 static inline bool xdp_return_frame_no_direct(void)
 {
 	struct bpf_redirect_info *ri = bpf_net_ctx_get_ri();
kernel/bpf/bpf_insn_array.c +0 -34
index cf67315be0359..5e5fe574f460e 100644
@@ -236,23 +236,6 @@ void bpf_insn_array_release(struct bpf_map *map)
 	atomic_set_release(&insn_array->used, 0);
 }
 
-void bpf_insn_array_adjust(struct bpf_map *map, u32 first, u32 len)
-{
-	struct bpf_insn_array *insn_array = cast_insn_array(map);
-	int i;
-
-	if (len <= 1)
-		return;
-
-	for (i = 0; i < map->max_entries; i++) {
-		if (insn_array->values[i].xlated_off < first)
-			continue;
-		if (insn_array->values[i].xlated_off == INSN_DELETED)
-			continue;
-		insn_array->values[i].xlated_off += len - 1;
-	}
-}
-
 /*
  * Move each offset to new_tgt[offset], new_off[] and new_tgt[] cover [0, cnt].
  * An insn is removed when new_off[] maps it to the same offset as the next
@@ -276,23 +259,6 @@ void bpf_insn_array_remap(struct bpf_map *map, const u32 *new_off, const u32 *ne
 	}
 }
 
-void bpf_insn_array_adjust_after_remove(struct bpf_map *map, u32 off, u32 len)
-{
-	struct bpf_insn_array *insn_array = cast_insn_array(map);
-	int i;
-
-	for (i = 0; i < map->max_entries; i++) {
-		if (insn_array->values[i].xlated_off < off)
-			continue;
-		if (insn_array->values[i].xlated_off == INSN_DELETED)
-			continue;
-		if (insn_array->values[i].xlated_off < off + len)
-			insn_array->values[i].xlated_off = INSN_DELETED;
-		else
-			insn_array->values[i].xlated_off -= len;
-	}
-}
-
 /*
  * This function is called by JITs. The image is the real program
  * image, the offsets array set up the xlated -> jitted mapping.
kernel/bpf/core.c +0 -193

199 lines not on this page · raw message

kernel/bpf/fixups.c +13 -181

231 lines not on this page · raw message

kernel/bpf/verifier.c +0 -45

51 lines not on this page · raw message

Signature · 1 line
2.43.0
#29 lore raw

PATCH v2 21/22 selftests/bpf: Test jumps around patches of bpf_do_misc_fixups()

In reply to Qiliang Yuan

bpf_do_misc_fixups() queues its patches and applies them at once, relocating every jump through a map from old to new indices.

No test checks the xlated code of jumps that target, skip or leave such patches, a jump that the patches push out of its 16-bit range, or an indirect jump to a patched instruction.

Check the xlated code for forward and backward jumps to a patched instruction, jumps over patches, and a may_goto whose jump leaves its own patch and crosses another one. Check that a jump over 8200 guarded divisions fails to load, and that a gotox to a guarded modulo by zero lands on the guard.

---
 tools/testing/selftests/bpf/prog_tests/verifier.c  |   2 +
 .../selftests/bpf/progs/verifier_patch_list.c      | 175 +++++++++++++++++++++
 2 files changed, 177 insertions(+)
tools/testing/selftests/bpf/prog_tests/verifier.c +2 -0
index 04740ba37e918..40788891641b5 100644
@@ -96,6 +96,7 @@
 #include "verifier_netfilter_retcode.skel.h"
 #include "verifier_bpf_fastcall.skel.h"
 #include "verifier_or_jmp32_k.skel.h"
+#include "verifier_patch_list.skel.h"
 #include "verifier_percpu_addr.skel.h"
 #include "verifier_precision.skel.h"
 #include "verifier_prevent_map_lookup.skel.h"
@@ -287,6 +288,7 @@ void test_verifier_netfilter_ctx(void)        { RUN(verifier_netfilter_ctx); }
 void test_verifier_netfilter_retcode(void)    { RUN(verifier_netfilter_retcode); }
 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_patch_list(void)           { RUN(verifier_patch_list); }
 void test_verifier_percpu_addr(void)          { RUN(verifier_percpu_addr); }
 void test_verifier_precision(void)            { RUN(verifier_precision); }
 void test_verifier_prevent_map_lookup(void)   { RUN(verifier_prevent_map_lookup); }
tools/testing/selftests/bpf/progs/verifier_patch_list.c new file +175 -0

175 lines not on this page · raw message

Signature · 1 line
2.43.0
#30 lore raw

PATCH v2 22/22 selftests/bpf: Cover a backward may_goto pushed out of range by patches

In reply to Qiliang Yuan

bpf_do_misc_fixups() expands a backward may_goto to gotol when the patches queued between it and its target push its offset out of the 16-bit range.

No test covers a backward may_goto whose expanded jump only goes out of the 16-bit range through the patches in between.

Check that a may_goto jumping back over 8191 guarded divisions loads and is expanded to gotol.

---
 .../selftests/bpf/progs/verifier_patch_list.c      | 35 ++++++++++++++++++++++
 1 file changed, 35 insertions(+)
tools/testing/selftests/bpf/progs/verifier_patch_list.c +35 -0
index 1370cdd5e5836..302e739caf83c 100644
@@ -172,4 +172,39 @@ l0_%=:							\
 }
 #endif
 
+/*
+ * may_goto jumps back by 8195 insns, by 32768 once each of the 8191
+ * divisions is guarded by a patch of 4 insns. That still fits the 16 bits of
+ * may_goto, but not the jump it expands to, which has to become gotol. Once
+ * the budget runs out, may_goto jumps back with r6 set and the program exits.
+ */
+SEC("raw_tp")
+__description("patch list: backward may_goto expanded to gotol")
+__arch_x86_64
+__success
+__xlated("...")
+__xlated("{{[0-9]+}}: gotol pc-{{[0-9]+}}")
+__naked void patch_list_may_goto_gotol(void)
+{
+	asm volatile ("					\
+	call %[bpf_get_prandom_u32];			\
+	r1 = r0;					\
+	r6 = 0;						\
+	goto 0f;					\
+1:	r0 = 0;						\
+	exit;						\
+0:	if r6 != 0 goto 1b;				\
+	.rept 8191;					\
+	r0 /= r1;					\
+	.endr;						\
+	r2 = 0;						\
+	r6 = 1;						\
+	may_goto 0b;					\
+	r0 = 0;						\
+	exit;						\
+"	:
+	: __imm(bpf_get_prandom_u32)
+	: __clobber_all);
+}
+
 char _license[] SEC("license") = "GPL";
Signature · 1 line
2.43.0
#31 lore raw

Re: [PATCH bpf-next v2 22/22] selftests/bpf: Cover a backward may_goto pushed out of range by patches

Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider: - [Medium] selftests/bpf: unguarded may_goto mnemonic in patch_list_may_goto_gotol() --

Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
- [Medium] selftests/bpf: unguarded may_goto mnemonic in patch_list_may_goto_gotol() --

commit eca3890b39b8864add1de9d7c74a0378b21864ca
Author: Qiliang Yuan <[email protected]>

selftests/bpf: Cover a backward may_goto pushed out of range by patches

This commit adds a BPF verifier selftest checking that a backward may_goto instruction pushed out of the 16-bit offset range by instruction patches is expanded to gotol.

Quoted 26 lines
tools/testing/selftests/bpf/progs/verifier_patch_list.c +18 -0
index 1370cdd5e5836..302e739caf83c 100644
@@ -172,4 +172,39 @@ l0_%=:							\
 }
 #endif
 
+/*
+ * may_goto jumps back by 8195 insns, by 32768 once each of the 8191
+ * divisions is guarded by a patch of 4 insns. That still fits the 16 bits of
+ * may_goto, but not the jump it expands to, which has to become gotol. Once
+ * the budget runs out, may_goto jumps back with r6 set and the program exits.
+ */
+SEC("raw_tp")
+__description("patch list: backward may_goto expanded to gotol")
+__arch_x86_64
+__success
+__xlated("...")
+__xlated("{{[0-9]+}}: gotol pc-{{[0-9]+}}")
+__naked void patch_list_may_goto_gotol(void)
+{
+	asm volatile ("					\
+	call %[bpf_get_prandom_u32];			\
+	r1 = r0;					\
+	r6 = 0;						\

tools/testing/selftests/bpf/progs/verifier_patch_list.c l0_%=: \ · line 202

Quoted 10 lines
tools/testing/selftests/bpf/progs/verifier_patch_list.c +10 -0
+	goto 0f;					\
+1:	r0 = 0;						\
+	exit;						\
+0:	if r6 != 0 goto 1b;				\
+	.rept 8191;					\
+	r0 /= r1;					\
+	.endr;						\
+	r2 = 0;						\
+	r6 = 1;						\
+	may_goto 0b;					\

[Severity: Medium]
Will this break the selftest build on toolchains whose assembler does not support the literal may_goto mnemonic (such as Clang prior to 19 or bpf-gcc when building test_progs-bpf_gcc)?

Other tests that emit the literal may_goto mnemonic in inline assembly guard it with #ifdef __BPF_FEATURE_MAY_GOTO, while the sibling test patch_list_may_goto() in this same file encodes the instruction directly:

tools/testing/selftests/bpf/progs/verifier_patch_list.c:patch_list_may_goto() {
	...
	".8byte %[may_goto];"
	"r0 /= r1;"
	"exit;"
	:
	: __imm(bpf_get_prandom_u32),
	  __imm_insn(may_goto, BPF_RAW_INSN(BPF_JMP | BPF_JCOND, 0, 0, 1 /* offset */, 0))
	...
}

Should patch_list_may_goto_gotol() either encode the instruction via .8byte %[may_goto] with __imm_insn(may_goto, BPF_RAW_INSN(BPF_JMP | BPF_JCOND, 0, 0, -8195, 0)) or be guarded with #ifdef __BPF_FEATURE_MAY_GOTO?

Signature · 1 line
Sashiko AI review · https://sashiko.dev/#/patchset/[email protected]?part=22