From: Qiliang Yuan <odys.yuan@gmail.com>
To: Alexei Starovoitov <ast@kernel.org>,
Daniel Borkmann <daniel@iogearbox.net>,
John Fastabend <john.fastabend@gmail.com>,
Andrii Nakryiko <andrii@kernel.org>,
Eduard Zingerman <eddyz87@gmail.com>,
Kumar Kartikeya Dwivedi <memxor@gmail.com>,
Martin KaFai Lau <martin.lau@linux.dev>,
Song Liu <song@kernel.org>,
Yonghong Song <yonghong.song@linux.dev>,
Jiri Olsa <jolsa@kernel.org>,
Emil Tsalapatis <emil@etsalapatis.com>,
Ihor Solodrai <ihor.solodrai@linux.dev>,
Shuah Khan <shuah@kernel.org>
Cc: bpf@vger.kernel.org, linux-kernel@vger.kernel.org,
linux-kselftest@vger.kernel.org,
Qiliang Yuan <odys.yuan@gmail.com>
Subject: [PATCH bpf-next v2 02/22] bpf: Remap the verifier state through the patch list
Date: Fri, 30 Oct 2026 07:51:47 -0400 [thread overview]
Message-ID: <20261030-bpf-verifier-patch-batch-v2-2-55cd43439f7c@gmail.com> (raw)
In-Reply-To: <20261030-bpf-verifier-patch-batch-v2-0-55cd43439f7c@gmail.com>
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.
Signed-off-by: Qiliang Yuan <odys.yuan@gmail.com>
---
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(+)
diff --git a/include/linux/bpf.h b/include/linux/bpf.h
index 580f89c450b55..9bb5e0c823627 100644
--- a/include/linux/bpf.h
+++ b/include/linux/bpf.h
@@ -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);
diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index a56a996b3d953..49a6e443de75d 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -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);
diff --git a/kernel/bpf/bpf_insn_array.c b/kernel/bpf/bpf_insn_array.c
index 92bbb71576ae3..dbfcf1eddb91e 100644
--- a/kernel/bpf/bpf_insn_array.c
+++ b/kernel/bpf/bpf_insn_array.c
@@ -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);
diff --git a/kernel/bpf/fixups.c b/kernel/bpf/fixups.c
index f062ef7dd943d..0697f66b1ffc1 100644
--- a/kernel/bpf/fixups.c
+++ b/kernel/bpf/fixups.c
@@ -380,6 +380,157 @@ struct bpf_prog *bpf_patch_insn_data(struct bpf_verifier_env *env, u32 off,
return __bpf_patch_insn_data(env, off, patch, len, BPF_PATCH_KEEP_TARGET);
}
+/*
+ * Queue the replacement of insn 'off' by 'patch[0..len)' until
+ * bpf_patch_list_commit(), see __bpf_patch_list_add().
+ */
+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;
+
+ 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),
+ env, "insn %u patched out of order", off))
+ return ERR_PTR(-EFAULT);
+
+ return __bpf_patch_list_add(pl, env->prog, off, patch, len);
+}
+
+void bpf_patch_list_free(struct bpf_verifier_env *env)
+{
+ bpf_patch_list_release(&env->patch_list);
+}
+
+/*
+ * 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;
+ last->zext_dst = bpf_insn_def32(prog, &patch[p->len - 1]) >= 0;
+ memset(slot, 0, sizeof(*slot) * (p->len - 1));
+
+ 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))) {
+ slot[i].non_stack_access = last->non_stack_access;
+ last->non_stack_access = false;
+ } else if (bpf_is_mem_insn(&patch[i])) {
+ slot[i].non_stack_access = true;
+ }
+ }
+
+ if (bpf_is_mem_insn(&patch[p->len - 1]) &&
+ 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;
+ last->indirect_target = 0;
+ }
+}
+
+/*
+ * Apply all queued patches 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, like with bpf_patch_insn_data().
+ */
+int bpf_patch_list_commit(struct bpf_verifier_env *env)
+{
+ struct bpf_patch_list *pl = &env->patch_list;
+ struct bpf_insn_aux_data *data = NULL;
+ struct bpf_prog *prog = env->prog;
+ struct bpf_patch_image img = {};
+ u32 i, k, end;
+ struct bpf_insn_patch *p;
+ int err = 0;
+
+ if (!pl->cnt)
+ goto out;
+
+ /* Leave the program untouched until nothing can fail anymore. */
+ err = bpf_patch_list_build(pl, prog, &img);
+ if (err == -ERANGE) {
+ verbose(env, "insn %d cannot be patched due to 16-bit range\n",
+ env->insn_aux_data[img.bad].orig_idx);
+ goto out;
+ }
+ if (verifier_bug_if(err == -EFAULT, env, "insn %u jumps out of the program",
+ img.bad))
+ goto out;
+ if (err)
+ goto out;
+
+ err = -ENOMEM;
+ data = __vmalloc(array_size(img.new_cnt, sizeof(*data)),
+ GFP_KERNEL_ACCOUNT | __GFP_ZERO);
+ if (!data)
+ goto out;
+
+ prog = bpf_prog_realloc(prog, bpf_prog_size(img.new_cnt), GFP_USER);
+ if (!prog)
+ goto out;
+ env->prog = prog;
+
+ bpf_patch_image_install(prog, &img);
+
+ for (i = 0, k = 0; i < img.cnt; i = end) {
+ if (k < pl->cnt && pl->patches[k].off == i) {
+ p = &pl->patches[k++];
+ patch_list_adj_aux(prog, p, &pl->insns[p->start],
+ &env->insn_aux_data[i],
+ &data[img.new_off[i]]);
+ end = i + 1;
+ continue;
+ }
+ end = k < pl->cnt ? pl->patches[k].off : img.cnt;
+ memcpy(data + img.new_off[i], env->insn_aux_data + i,
+ sizeof(*data) * (end - i));
+ }
+ vfree(env->insn_aux_data);
+ env->insn_aux_data = data;
+ env->insn_aux_data_len = img.new_cnt;
+ data = NULL;
+
+ for (i = 0; i < env->func_ptr_cnt; i++) {
+ struct bpf_func_ptr *fp = &env->func_ptrs[i];
+
+ if (fp->xlated_off == BPF_FUNC_PTR_DELETED)
+ continue;
+ fp->xlated_off = bpf_patch_image_remap(&img, img.new_off, fp->xlated_off);
+ }
+
+ /* NOTE: fake 'exit' subprog should be updated as well. */
+ for (i = 0; i <= env->subprog_cnt; i++)
+ env->subprog_info[i].start =
+ bpf_patch_image_remap(&img, img.new_off, env->subprog_info[i].start);
+
+ 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);
+
+ err = 0;
+out:
+ vfree(data);
+ bpf_patch_image_free(&img);
+ bpf_patch_list_release(pl);
+ return err;
+}
+
/*
* insn was moved down by delta insns inside its own patch. Operands relative
* to the pc that point in front of the old position did not move with it.
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 5601d20562186..b6b120bf5433c 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -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);
--
2.43.0
next prev parent reply other threads:[~2026-10-30 11:52 UTC|newest]
Thread overview: 28+ messages / expand[flat|nested] mbox.gz Atom feed top
2026-10-30 11:51 [PATCH bpf-next v2 00/22] bpf: Replace bpf_patch_insn_data() with a list of deferred patches Qiliang Yuan
2026-10-30 11:51 ` [PATCH bpf-next v2 01/22] bpf: Add a list of deferred instruction patches Qiliang Yuan
2026-10-30 11:51 ` Qiliang Yuan [this message]
2026-10-30 12:44 ` [PATCH bpf-next v2 02/22] bpf: Remap the verifier state through the patch list bot+bpf-ci
2026-10-30 11:51 ` [PATCH bpf-next v2 03/22] bpf: Apply single-instruction patches of the verifier in place Qiliang Yuan
2026-10-30 11:51 ` [PATCH bpf-next v2 04/22] bpf: Queue the rewrites of bpf_do_misc_fixups() Qiliang Yuan
2026-10-30 11:51 ` [PATCH bpf-next v2 05/22] bpf: Expand a backward may_goto to gotol when patches push it out of range Qiliang Yuan
2026-10-30 12:59 ` bot+bpf-ci
2026-10-30 11:51 ` [PATCH bpf-next v2 06/22] bpf: Drop the constant delta from bpf_do_misc_fixups() Qiliang Yuan
2026-10-30 11:51 ` [PATCH bpf-next v2 07/22] bpf: Let the patch list remove instructions Qiliang Yuan
2026-10-30 11:51 ` [PATCH bpf-next v2 08/22] bpf: Remove dead code through the patch list Qiliang Yuan
2026-10-30 11:51 ` [PATCH bpf-next v2 09/22] bpf: Strip nops " Qiliang Yuan
2026-10-30 12:45 ` bot+bpf-ci
2026-10-30 11:51 ` [PATCH bpf-next v2 10/22] bpf: Batch the patches of bpf_opt_subreg_zext_lo32_rnd_hi32() Qiliang Yuan
2026-10-30 11:51 ` [PATCH bpf-next v2 11/22] bpf: Allow patching an instruction twice through the patch list Qiliang Yuan
2026-10-30 11:51 ` [PATCH bpf-next v2 12/22] bpf: Teach the patch list to insert in front of an instruction Qiliang Yuan
2026-10-30 12:44 ` bot+bpf-ci
2026-10-30 11:51 ` [PATCH bpf-next v2 13/22] bpf: Allow inserting in front of a queued patch Qiliang Yuan
2026-10-30 11:51 ` [PATCH bpf-next v2 14/22] bpf: Move bpf_convert_ctx_accesses() to the patch list Qiliang Yuan
2026-10-30 11:52 ` [PATCH bpf-next v2 15/22] bpf: Insert the may_goto counter setup through " Qiliang Yuan
2026-10-30 11:52 ` [PATCH bpf-next v2 16/22] bpf: Append the hidden subprog " Qiliang Yuan
2026-10-30 11:52 ` [PATCH bpf-next v2 17/22] bpf: Inline bpf_loop() calls " Qiliang Yuan
2026-10-30 11:52 ` [PATCH bpf-next v2 18/22] bpf: Apply the patch list without a verifier env Qiliang Yuan
2026-10-30 11:52 ` [PATCH bpf-next v2 19/22] bpf: Blind constants through the patch list Qiliang Yuan
2026-10-30 12:44 ` bot+bpf-ci
2026-10-30 11:52 ` [PATCH bpf-next v2 20/22] bpf: Remove the old instruction patching code Qiliang Yuan
2026-10-30 11:52 ` [PATCH bpf-next v2 21/22] selftests/bpf: Test jumps around patches of bpf_do_misc_fixups() Qiliang Yuan
2026-10-30 11:52 ` [PATCH bpf-next v2 22/22] selftests/bpf: Cover a backward may_goto pushed out of range by patches Qiliang Yuan
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20261030-bpf-verifier-patch-batch-v2-2-55cd43439f7c@gmail.com \
--to=odys.yuan@gmail.com \
--cc=andrii@kernel.org \
--cc=ast@kernel.org \
--cc=bpf@vger.kernel.org \
--cc=daniel@iogearbox.net \
--cc=eddyz87@gmail.com \
--cc=emil@etsalapatis.com \
--cc=ihor.solodrai@linux.dev \
--cc=john.fastabend@gmail.com \
--cc=jolsa@kernel.org \
--cc=linux-kernel@vger.kernel.org \
--cc=linux-kselftest@vger.kernel.org \
--cc=martin.lau@linux.dev \
--cc=memxor@gmail.com \
--cc=shuah@kernel.org \
--cc=song@kernel.org \
--cc=yonghong.song@linux.dev \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox
all inboxes | Powered by JetHome®