* [PATCH bpf-next v3 01/13] bpf: Add a list of deferred instruction patches
2026-11-02 1:29 [PATCH bpf-next v3 00/13] bpf: Replace bpf_patch_insn_data() with a list of deferred patches Alexei Starovoitov
@ 2026-11-02 1:29 ` Alexei Starovoitov
2026-11-02 1:29 ` [PATCH bpf-next v3 02/13] bpf: Remap the verifier state through the patch list Alexei Starovoitov
` (13 subsequent siblings)
14 siblings, 0 replies; 18+ messages in thread
From: Alexei Starovoitov @ 2026-11-02 1:29 UTC (permalink / raw)
To: bpf; +Cc: daniel, andrii, eddyz87, memxor, odys.yuan
From: Qiliang Yuan <odys.yuan@gmail.com>
After verification the verifier replaces many insns of a prog with several
insns each. bpf_patch_insn_data() and bpf_patch_insn_single() patch one
insn immediately. Each call moves all insns behind the patch and walks all
insns to adjust the jumps. It also walks each table that names insns, for
example line info. Thus a pass that patches M of the N insns of a prog does
O(N * M) work.
pyperf180 from the selftests has 24k insns. The 920 patches that inline
bpf_map_lookup_elem() take about 40 % of its load time.
Add a patch list: an array of patches and an array with their insns. A pass
queues its patches in the order of the insns and does not change the prog.
Then one commit builds the new image in O(N + inserted insns). Its first
walk calculates new_off[], the map from old index to new index. Its second
walk copies insns and patches, and it adjusts the jumps.
old image patch list new_off[] new image
0: r2 = 0 0 0: r2 = 0
1: r0 /= r1 4 insns 1 1: if r1 != 0 goto +2
2: w0 ^= w0
3: goto +1
4: r0 /= r1
2: if r0 == 0 goto +1 5 5: if r0 == 0 goto +2
3: r0 %= r1 2 insns 6 6: if r1 == 0 goto +1
7: r0 %= r1
4: r2 += 1 8 8: r2 += 1
5: if r2 < 3 goto -5 9 9: if r2 < 3 goto -9
6: exit 10 10: exit
new_off[i] is i plus the number of insns that the patches in front of i
add. A patched insn maps to the first insn of its patch, as with
bpf_patch_insn_data(). All that names an insn goes through the map:
offset of a jump or a call new_off[old target] - new index - 1
old insn 2, target 4 new_off[4] - 5 - 1 = +2
old insn 5, target 1 new_off[1] - 9 - 1 = -9
poke descriptor, line info new_off[old index]
- A jump that stays in its patch does not change. A pass writes a jump
that leaves its patch as if this patch was the only one.
- bpf_patch_list_build() builds the new image in new memory. A jump can
get out of the range of its 16-bit offset. Then the function returns
-ERANGE, and the prog does not change.
- The code is in core.c and needs no bpf_verifier_env. Thus the blinding
of constants in classic BPF progs can use it. No pass uses the list yet.
Suggested-by: Eduard Zingerman <eddyz87@gmail.com>
Signed-off-by: Qiliang Yuan <odys.yuan@gmail.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
---
include/linux/bpf_verifier.h | 47 ++++++++
kernel/bpf/core.c | 220 +++++++++++++++++++++++++++++++++++
2 files changed, 267 insertions(+)
diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index 7baeb831281f..baa3a29a190e 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -1059,6 +1059,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
*/
diff --git a/kernel/bpf/core.c b/kernel/bpf/core.c
index e6593febbc35..5c4898c91a43 100644
--- a/kernel/bpf/core.c
+++ b/kernel/bpf/core.c
@@ -530,6 +530,226 @@ int bpf_remove_insns(struct bpf_prog *prog, u32 off, u32 cnt)
return err;
}
+static int patch_list_reserve_patch(struct bpf_patch_list *pl)
+{
+ struct bpf_insn_patch *p;
+ u32 cap;
+
+ if (pl->cnt < pl->cap)
+ return 0;
+
+ cap = max(pl->cap * 2, 16U);
+ p = kvrealloc(pl->patches, array_size(cap, sizeof(*p)), GFP_KERNEL_ACCOUNT);
+ if (!p)
+ return -ENOMEM;
+ pl->patches = p;
+ pl->cap = cap;
+ return 0;
+}
+
+static int patch_list_reserve_insns(struct bpf_patch_list *pl, u32 cnt)
+{
+ struct bpf_insn *insns;
+ u32 cap;
+
+ if (pl->insn_cnt + cnt <= pl->insn_cap)
+ return 0;
+
+ cap = max3(pl->insn_cap * 2, pl->insn_cnt + cnt, 64U);
+ insns = kvrealloc(pl->insns, array_size(cap, sizeof(*insns)), GFP_KERNEL_ACCOUNT);
+ if (!insns)
+ return -ENOMEM;
+ pl->insns = insns;
+ pl->insn_cap = cap;
+ return 0;
+}
+
+/*
+ * Extract the pc-relative operand of a jump, a subprog call or a ld_imm64 of a
+ * subprog. gotox and a tail call pass for a jump to the next insn: nothing
+ * reads their 'off'.
+ */
+static bool insn_get_rel(const struct bpf_insn *insn, s64 *rel, bool *is_imm)
+{
+ u8 code = insn->code;
+
+ if (bpf_pseudo_func(insn) || bpf_pseudo_call(insn)) {
+ *rel = insn->imm;
+ *is_imm = true;
+ return true;
+ }
+ if ((BPF_CLASS(code) != BPF_JMP && BPF_CLASS(code) != BPF_JMP32) ||
+ BPF_OP(code) == BPF_CALL || BPF_OP(code) == BPF_EXIT)
+ return false;
+
+ *is_imm = code == (BPF_JMP32 | BPF_JA);
+ *rel = *is_imm ? insn->imm : insn->off;
+ return true;
+}
+
+/* Set the pc-relative operand that insn_get_rel() extracted. */
+static int insn_set_rel(struct bpf_insn *insn, s64 rel, bool is_imm)
+{
+ if (is_imm) {
+ if (rel < S32_MIN || rel > S32_MAX)
+ return -ERANGE;
+ insn->imm = rel;
+ } else {
+ if (rel < S16_MIN || rel > S16_MAX)
+ return -ERANGE;
+ insn->off = rel;
+ }
+ 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
+ * at 'pos' of the new image. 'new_off' maps the old image to the new one.
+ */
+static int patch_list_adj_insn(struct bpf_insn *insn, const u32 *new_off,
+ u32 cnt, u32 off, u32 idx, u32 len, u32 pos)
+{
+ bool is_imm;
+ s64 rel, tgt;
+
+ if (!insn_get_rel(insn, &rel, &is_imm))
+ return 0;
+
+ /* relative to the first insn of the patch */
+ tgt = (s64)idx + rel + 1;
+ if (tgt >= 0 && tgt < len)
+ return 0;
+
+ /* the patch pushed what follows 'off' down by len - 1 */
+ tgt = tgt < 0 ? off + tgt : off + tgt - len + 1;
+ if (tgt < 0 || tgt > cnt)
+ return -EFAULT;
+
+ rel = (s64)new_off[tgt] - pos - 1;
+ return insn_set_rel(insn, rel, is_imm);
+}
+
+/*
+ * 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'.
+ *
+ * Return the copy of the last insn of the patch, which stays valid until the
+ * next call.
+ *
+ * The caller sees to the order, to off < prog->len and to len > 0.
+ */
+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;
+ int err;
+
+ err = patch_list_reserve_patch(pl) ?: patch_list_reserve_insns(pl, len);
+ if (err)
+ return ERR_PTR(err);
+
+ p = &pl->patches[pl->cnt++];
+ p->off = off;
+ p->len = len;
+ p->start = pl->insn_cnt;
+ p->orig = prog->insnsi[off];
+ memcpy(pl->insns + p->start, patch, len * sizeof(*patch));
+ pl->insn_cnt += len;
+
+ return &pl->insns[p->start + len - 1];
+}
+
+void bpf_patch_list_release(struct bpf_patch_list *pl)
+{
+ kvfree(pl->patches);
+ kvfree(pl->insns);
+ memset(pl, 0, sizeof(*pl));
+}
+
+/*
+ * Build the image of 'prog' with the queued patches applied in img->insns,
+ * without touching 'prog'. img->new_off[] maps each old insn to the start of
+ * its patch. On -ERANGE, img->bad is the old insn whose jump got out of range.
+ */
+int bpf_patch_list_build(const struct bpf_patch_list *pl, const struct bpf_prog *prog,
+ struct bpf_patch_image *img)
+{
+ u32 cnt = prog->len, i, k, n;
+ int err;
+
+ memset(img, 0, sizeof(*img));
+ img->cnt = cnt;
+ img->new_off = kvmalloc_array(cnt + 1, sizeof(u32), GFP_KERNEL_ACCOUNT);
+ if (!img->new_off)
+ return -ENOMEM;
+
+ for (i = 0, k = 0; i <= cnt; i++) {
+ img->new_off[i] = i + img->grow;
+ if (k < pl->cnt && pl->patches[k].off == i)
+ img->grow += pl->patches[k++].len - 1;
+ }
+ img->new_cnt = cnt + img->grow;
+
+ img->insns = kvmalloc_array(img->new_cnt, sizeof(*img->insns), GFP_KERNEL_ACCOUNT);
+ if (!img->insns)
+ return -ENOMEM;
+
+ for (i = 0, k = 0; i < cnt; i++) {
+ const struct bpf_insn *src = &prog->insnsi[i];
+ u32 len = 1, pos = img->new_off[i];
+
+ if (k < pl->cnt && pl->patches[k].off == i) {
+ src = &pl->insns[pl->patches[k].start];
+ len = pl->patches[k++].len;
+ }
+
+ for (n = 0; n < len; n++) {
+ img->insns[pos + n] = src[n];
+ err = patch_list_adj_insn(&img->insns[pos + n], img->new_off,
+ cnt, i, n, len, pos + n);
+ if (err) {
+ img->bad = i;
+ return err;
+ }
+ }
+ }
+ return 0;
+}
+
+void bpf_patch_image_free(struct bpf_patch_image *img)
+{
+ kvfree(img->insns);
+ kvfree(img->new_off);
+ memset(img, 0, sizeof(*img));
+}
+
+/*
+ * Move the poke descriptors and the line info of 'prog' along, then put the
+ * new image in 'prog', which has room for it. The new value of an entry
+ * depends on its old value and on the maps of 'img' only.
+ */
+void bpf_patch_image_install(struct bpf_prog *prog, const struct bpf_patch_image *img)
+{
+ u32 i;
+
+ for (i = 0; i < prog->aux->size_poke_tab; i++)
+ prog->aux->poke_tab[i].insn_idx =
+ bpf_patch_image_remap(img, img->new_off,
+ prog->aux->poke_tab[i].insn_idx);
+
+ for (i = 0; i < prog->aux->nr_linfo; i++)
+ prog->aux->linfo[i].insn_off =
+ bpf_patch_image_remap(img, img->new_off,
+ prog->aux->linfo[i].insn_off);
+
+ memcpy(prog->insnsi, img->insns, sizeof(*img->insns) * img->new_cnt);
+ prog->len = img->new_cnt;
+}
+
static void bpf_prog_kallsyms_del_subprogs(struct bpf_prog *fp)
{
int i;
--
2.55.0
^ permalink raw reply related [flat|nested] 18+ messages in thread* [PATCH bpf-next v3 02/13] bpf: Remap the verifier state through the patch list
2026-11-02 1:29 [PATCH bpf-next v3 00/13] bpf: Replace bpf_patch_insn_data() with a list of deferred patches Alexei Starovoitov
2026-11-02 1:29 ` [PATCH bpf-next v3 01/13] bpf: Add a list of deferred instruction patches Alexei Starovoitov
@ 2026-11-02 1:29 ` Alexei Starovoitov
2026-11-02 1:29 ` [PATCH bpf-next v3 03/13] bpf: Queue the rewrites of bpf_do_misc_fixups() Alexei Starovoitov
` (12 subsequent siblings)
14 siblings, 0 replies; 18+ messages in thread
From: Alexei Starovoitov @ 2026-11-02 1:29 UTC (permalink / raw)
To: bpf; +Cc: daniel, andrii, eddyz87, memxor, odys.yuan
From: Qiliang Yuan <odys.yuan@gmail.com>
A pass queues its patches in the patch list. One commit builds the new
image of the prog and new_off[], the map from old index to new index. The
code in core.c moves only the tables of the prog through the map: poke
descriptors and line info. The verifier has more tables that name insns,
and bpf_patch_insn_data() walks all of them for each patch:
table what an entry names
----------------- --------------------------------------------------
aux data insn i, by the position of the entry in the array
subprogs the first insn of a subprog
function pointers the first insn of a subprog that .rodata points to
insn arrays a target of an indirect jump
Put a patch list in bpf_verifier_env (env). A pass calls
bpf_patch_list_add() to queue a patch, and bpf_patch_list_commit() one time
at its end. The commit moves each table one time, through new_off[].
During the commit one part of env describes the old image, and a different
part describes the new image. A helper that reads env or the prog at that
time can get an incorrect result. Thus the order of the steps is a rule:
1. all that can fail Build the new image, allocate the new aux data,
reallocate the prog. An error changes nothing.
2. the tables A new entry depends only on the old entry and on
the map. No helper that reads the insns,
prog->len or a table from env or the prog.
3. the new image bpf_patch_image_install() writes the insns and
prog->len last.
The aux data of a patched insn goes to the last insn of its patch. The
other insns of the patch get new aux data, as with adjust_insn_aux_data().
One rule is new. They get the orig_idx of the patched insn: its index in
the prog that the user loads. Thus a message about a jump in a patch names
that insn, not insn 0.
A patch of 1 insn moves nothing. bpf_patch_list_add() does not queue it. It
writes the insn to the prog in place. It sets zext_dst and non_stack_access
in the aux data from the new insn, as bpf_patch_insn_data() does.
The commit replaces env->prog and env->insn_aux_data. A pass must read the
two pointers again. bpf_check() frees the list at its end. Thus a pass can
return an error while patches are queued. No pass uses the list yet.
Signed-off-by: Qiliang Yuan <odys.yuan@gmail.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
---
include/linux/bpf.h | 1 +
include/linux/bpf_verifier.h | 5 +
kernel/bpf/bpf_insn_array.c | 17 ++++
kernel/bpf/fixups.c | 187 +++++++++++++++++++++++++++++++++++
kernel/bpf/verifier.c | 1 +
5 files changed, 211 insertions(+)
diff --git a/include/linux/bpf.h b/include/linux/bpf.h
index ff0436781293..ba96b4fc893a 100644
--- a/include/linux/bpf.h
+++ b/include/linux/bpf.h
@@ -4380,6 +4380,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 baa3a29a190e..fc051a084442 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -1152,6 +1152,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;
@@ -2066,6 +2067,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 92bbb71576ae..21ca87c96373 100644
--- a/kernel/bpf/bpf_insn_array.c
+++ b/kernel/bpf/bpf_insn_array.c
@@ -253,6 +253,23 @@ 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 i, off;
+
+ 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 41bc37e205e0..aee645cbb63b 100644
--- a/kernel/bpf/fixups.c
+++ b/kernel/bpf/fixups.c
@@ -355,6 +355,193 @@ 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(). 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)
+{
+ 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);
+
+ 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);
+}
+
+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;
+ /* messages name the insn of the original program */
+ slot[i].orig_idx = last->orig_idx;
+ 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;
+ }
+}
+
+/* Fill 'data', the aux data of the new image, from the aux data of the old one. */
+static void patch_list_remap_aux(struct bpf_verifier_env *env,
+ const struct bpf_patch_image *img,
+ struct bpf_insn_aux_data *data)
+{
+ struct bpf_patch_list *pl = &env->patch_list;
+ struct bpf_insn_patch *p;
+ u32 i, k, end;
+
+ 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(env->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;
+}
+
+/* Subprogs, and the function pointers that name them, follow their first insn. */
+static void patch_list_remap_subprogs(struct bpf_verifier_env *env,
+ const struct bpf_patch_image *img)
+{
+ u32 i;
+
+ 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);
+}
+
+/*
+ * 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().
+ *
+ * The order of the steps is a rule:
+ * 1. All that can fail: build the new image aside and allocate memory. An
+ * error leaves the program and the env as they were.
+ * 2. Move each table that names insns. The new value of an entry depends on
+ * its old value and on the maps of the image only. Between the first and
+ * the last step one part of the env describes the old image and another
+ * part the new one, so don't call a helper that reads prog->len, the insns
+ * or one of these tables from the env or the program.
+ * 3. Install the new image.
+ */
+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 = {};
+ int err = 0;
+ u32 i;
+
+ if (!pl->cnt)
+ goto out;
+
+ 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;
+ err = 0;
+
+ patch_list_remap_aux(env, &img, data);
+ data = NULL;
+ patch_list_remap_subprogs(env, &img);
+ 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);
+
+ bpf_patch_image_install(prog, &img);
+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 1b6c0674ff6a..5bdf41a9bef0 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -24240,6 +24240,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.55.0
^ permalink raw reply related [flat|nested] 18+ messages in thread* [PATCH bpf-next v3 03/13] bpf: Queue the rewrites of bpf_do_misc_fixups()
2026-11-02 1:29 [PATCH bpf-next v3 00/13] bpf: Replace bpf_patch_insn_data() with a list of deferred patches Alexei Starovoitov
2026-11-02 1:29 ` [PATCH bpf-next v3 01/13] bpf: Add a list of deferred instruction patches Alexei Starovoitov
2026-11-02 1:29 ` [PATCH bpf-next v3 02/13] bpf: Remap the verifier state through the patch list Alexei Starovoitov
@ 2026-11-02 1:29 ` Alexei Starovoitov
2026-11-02 1:29 ` [PATCH bpf-next v3 04/13] bpf: Let the patch list remove instructions Alexei Starovoitov
` (11 subsequent siblings)
14 siblings, 0 replies; 18+ messages in thread
From: Alexei Starovoitov @ 2026-11-02 1:29 UTC (permalink / raw)
To: bpf; +Cc: daniel, andrii, eddyz87, memxor, odys.yuan
From: Qiliang Yuan <odys.yuan@gmail.com>
The main loop of bpf_do_misc_fixups() patches divisions, may_goto, calls of
helpers and more. It calls bpf_patch_insn_data() for each patch, and each
call costs O(N) in a prog of N insns.
Queue the patches in the patch list with bpf_patch_list_add(). One commit
behind the loop, before the setup of the may_goto count, builds the new
image in O(N + inserted insns). No insn moves while the loop runs. Thus the
loop uses old indexes only: 'i + delta' becomes 'i'.
Some patches end with a call of a helper. The code at patch_call_imm then
writes the address of the helper to that call. It writes to the queued copy
of the call, which bpf_patch_list_add() returns. Thus 'insn' can point into
the list, and the loop sets it from the index before the next insn.
The patch of may_goto goes to the target with a conditional jump, which has
a 16-bit offset. When that offset is out of range, the patch uses 'gotol'.
The loop selects the jump when it queues the patch, but the offset is final
only at the commit. Each patch between may_goto and its target makes the
offset longer by its growth. The growth of a patch is its length - 1.
may_goto patches between it and its target offset that selects the jump
-------- --------------------------------- ----------------------------
backward all are queued old offset - their growth
forward none is queued old offset
New may_goto_off() calculates the first row. In the second row the jump can
get out of range at the commit. Then the load fails, as it does with
bpf_patch_insn_data().
What users can see:
- A jump that patches push out of its 16-bit range fails the load with
-ERANGE, not with -ENOMEM. The message names the jump, not the patched
insn: "insn %d cannot be patched due to 16-bit range". For a jump in a
patch, as the one of may_goto, it names the insn that the patch
replaces.
- A backward may_goto that patches push beyond -32768 loads. Before this
patch the load fails.
Wall time of 'veristat -q <obj>' in an x86_64 VM with 8 vCPUs, mean of 30
runs, before and after this patch:
before after
pyperf180 0.147 s 0.083 s
pyperf600 0.430 s 0.219 s
Signed-off-by: Qiliang Yuan <odys.yuan@gmail.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
---
kernel/bpf/fixups.c | 294 ++++++++++++++++++--------------------------
1 file changed, 118 insertions(+), 176 deletions(-)
diff --git a/kernel/bpf/fixups.c b/kernel/bpf/fixups.c
index aee645cbb63b..0a5b35a00f9f 100644
--- a/kernel/bpf/fixups.c
+++ b/kernel/bpf/fixups.c
@@ -1969,18 +1969,21 @@ static int add_hidden_subprog(struct bpf_verifier_env *env, struct bpf_insn *pat
/*
* Expand may_goto: load the count from the stack, jump to the target of
* 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.
+ * 'off' is the offset of may_goto, 'reach' how far it jumps once the patches
+ * queued so far are applied, see may_goto_off().
+ * Use gotol when 'reach' 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)
+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);
@@ -1990,6 +1993,27 @@ 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.
+ * The patches that a forward may_goto jumps over aren't queued yet, so its
+ * offset stays as it is.
+ */
+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.
*/
@@ -2006,7 +2030,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;
@@ -2038,7 +2062,7 @@ 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);
@@ -2061,13 +2085,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, insn_buf, cnt);
+ if (IS_ERR(insn))
+ return PTR_ERR(insn);
goto next_insn;
}
@@ -2152,13 +2172,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, insn_buf, cnt);
+ if (IS_ERR(insn))
+ return PTR_ERR(insn);
goto next_insn;
}
@@ -2182,13 +2198,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, insn_buf, cnt);
+ if (IS_ERR(insn))
+ return PTR_ERR(insn);
goto next_insn;
}
@@ -2202,13 +2214,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, insn_buf, cnt);
+ if (IS_ERR(insn))
+ return PTR_ERR(insn);
goto next_insn;
}
@@ -2221,7 +2229,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;
@@ -2255,13 +2263,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, insn_buf, cnt);
+ if (IS_ERR(insn))
+ return PTR_ERR(insn);
goto next_insn;
}
@@ -2295,16 +2299,13 @@ 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));
-
- new_prog = bpf_patch_insn_data(env, i + delta, insn_buf, cnt);
- if (!new_prog)
- return -ENOMEM;
+ cnt = may_goto_expand(insn_buf, insn->off,
+ may_goto_off(env, insn, i),
+ stack_off_cnt, tail, ARRAY_SIZE(tail));
- delta += cnt - 1;
- env->prog = 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);
goto next_insn;
} else if (bpf_is_may_goto_insn(insn)) {
int stack_off = -stack_depth - 8;
@@ -2314,16 +2315,13 @@ 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));
-
- new_prog = bpf_patch_insn_data(env, i + delta, insn_buf, cnt);
- if (!new_prog)
- return -ENOMEM;
+ cnt = may_goto_expand(insn_buf, insn->off,
+ may_goto_off(env, insn, i),
+ stack_off, tail, ARRAY_SIZE(tail));
- delta += cnt - 1;
- env->prog = 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);
goto next_insn;
}
@@ -2333,7 +2331,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;
@@ -2344,7 +2342,7 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env)
* We are *skipping* first half of ld_imm64 insn
* with 'i++;', patching over second half of it
* with that same half + mov64_percpu_reg insn.
- * All because bpf_patch_insn_data() can only
+ * All because a patch can only
* replace one 8-byte insn, which does not work
* well for ld_imm64 insn.
*/
@@ -2354,13 +2352,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, insn_buf, cnt);
+ if (IS_ERR(insn))
+ return PTR_ERR(insn);
goto next_insn;
}
@@ -2369,19 +2363,15 @@ 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;
- 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, insn_buf, cnt);
+ if (IS_ERR(insn))
+ return PTR_ERR(insn);
goto next_insn;
}
@@ -2420,7 +2410,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) &&
@@ -2430,7 +2420,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);
@@ -2466,17 +2456,13 @@ 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, 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
@@ -2500,18 +2486,14 @@ 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, 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.
*/
@@ -2519,13 +2501,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, insn_buf, cnt);
+ if (IS_ERR(insn))
+ return PTR_ERR(insn);
goto patch_call_imm;
}
@@ -2543,7 +2521,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;
@@ -2562,14 +2540,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, insn_buf, cnt);
+ if (IS_ERR(insn))
+ return PTR_ERR(insn);
goto next_insn;
}
@@ -2645,14 +2618,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, insn_buf, cnt);
+ if (IS_ERR(insn))
+ return PTR_ERR(insn);
goto next_insn;
}
@@ -2675,13 +2643,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, insn_buf, cnt);
+ if (IS_ERR(insn))
+ return PTR_ERR(insn);
goto next_insn;
}
@@ -2694,13 +2658,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, insn_buf, cnt);
+ if (IS_ERR(insn))
+ return PTR_ERR(insn);
goto next_insn;
}
#endif
@@ -2728,13 +2688,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, insn_buf, cnt);
+ if (IS_ERR(insn))
+ return PTR_ERR(insn);
goto next_insn;
}
@@ -2760,13 +2716,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, insn_buf, cnt);
+ if (IS_ERR(insn))
+ return PTR_ERR(insn);
goto next_insn;
}
@@ -2786,13 +2738,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, insn_buf, cnt);
+ if (IS_ERR(insn))
+ return PTR_ERR(insn);
goto next_insn;
}
@@ -2802,12 +2750,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, insn_buf, 1);
+ if (IS_ERR(insn))
+ return PTR_ERR(insn);
goto next_insn;
}
@@ -2857,13 +2802,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, insn_buf, cnt);
+ if (IS_ERR(insn))
+ return PTR_ERR(insn);
goto next_insn;
}
@@ -2875,13 +2816,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, insn_buf, cnt);
+ if (IS_ERR(insn))
+ return PTR_ERR(insn);
goto next_insn;
}
patch_call_imm:
@@ -2897,7 +2834,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;
@@ -2912,9 +2849,14 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env)
stack_depth_extra = 0;
}
i++;
- insn++;
+ insn = &prog->insnsi[i];
}
+ 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;
--
2.55.0
^ permalink raw reply related [flat|nested] 18+ messages in thread* [PATCH bpf-next v3 04/13] bpf: Let the patch list remove instructions
2026-11-02 1:29 [PATCH bpf-next v3 00/13] bpf: Replace bpf_patch_insn_data() with a list of deferred patches Alexei Starovoitov
` (2 preceding siblings ...)
2026-11-02 1:29 ` [PATCH bpf-next v3 03/13] bpf: Queue the rewrites of bpf_do_misc_fixups() Alexei Starovoitov
@ 2026-11-02 1:29 ` Alexei Starovoitov
2026-11-02 1:29 ` [PATCH bpf-next v3 05/13] bpf: Move the bpf_opt_*() passes to the patch list Alexei Starovoitov
` (10 subsequent siblings)
14 siblings, 0 replies; 18+ messages in thread
From: Alexei Starovoitov @ 2026-11-02 1:29 UTC (permalink / raw)
To: bpf; +Cc: daniel, andrii, eddyz87, memxor, odys.yuan
From: Qiliang Yuan <odys.yuan@gmail.com>
verifier_remove_insns() removes a range of insns immediately. Each call
moves all insns behind the range and walks all jumps and each table that
names insns. Thus M removals in a prog of N insns cost O(N * M). The patch
list can only replace an insn.
Add bpf_patch_list_del(). It queues a removal, which is a patch of 0 insns.
The map from old index to new index, new_off[], needs no new rule. A
removed insn maps to the next insn that stays:
old image patch list new_off[] new image
0: if r1 == 0 goto +2 0 0: if r1 == 0 goto +1
1: r0 = 1 1 1: r0 = 1
2: goto +0 removal 2
3: goto +0 removal 2
4: exit 2 2: exit
Insn i is removed when new_off[i] == new_off[i + 1]. The rules for all that
names a removed insn are the rules of verifier_remove_insns():
what names it after bpf_patch_list_commit()
---------------- -------------------------------------------------------
jump, call It lands on the next insn that stays.
aux data The entry is removed.
line info The record is removed. If the next insn that stays has
no record, it gets the last removed record.
subprog It starts at the next insn that stays. When it has no
insns, it is removed with its func info.
function pointer It follows its subprog or gets BPF_FUNC_PTR_DELETED.
insn array The entry gets INSN_DELETED.
- A removed record changes the index of the records behind it. Each
subprog holds the index of its first record. Thus bpf_patch_list_build()
calculates a map for the records too, new_linfo[].
- Only the subprogs show where a subprog ends. Thus the function pointers
move before the subprogs, while the subprogs have their old starts.
- The two helpers for removed insns read bpf_verifier_env (env). Thus the
commit calls them in the new step 2, before it moves the tables. Nothing
can fail there. Thus a fatal signal does not stop the calls of the
offload driver (nfp), as it does in verifier_remove_insns().
1. all that can fail
2. removed insns Tell the offload device, free what their aux data
points to. All of env describes the old image.
3. the tables
4. the new image
Signed-off-by: Qiliang Yuan <odys.yuan@gmail.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
---
include/linux/bpf_verifier.h | 11 +++
kernel/bpf/bpf_insn_array.c | 10 ++-
kernel/bpf/core.c | 81 +++++++++++++++--
kernel/bpf/fixups.c | 170 +++++++++++++++++++++++++++++++----
4 files changed, 245 insertions(+), 27 deletions(-)
diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index fc051a084442..b77a0ba477f1 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -1084,10 +1084,13 @@ struct bpf_patch_list {
struct bpf_patch_image {
struct bpf_insn *insns;
u32 *new_off;
+ u32 *new_linfo;
u32 cnt;
u32 new_cnt;
+ u32 nr_linfo;
s32 grow;
u32 bad;
+ bool del;
};
/* Map an offset in the old program, which may be past its end. */
@@ -1097,9 +1100,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);
@@ -2071,6 +2081,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);
diff --git a/kernel/bpf/bpf_insn_array.c b/kernel/bpf/bpf_insn_array.c
index 21ca87c96373..e2e4aee00c4d 100644
--- a/kernel/bpf/bpf_insn_array.c
+++ b/kernel/bpf/bpf_insn_array.c
@@ -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)
{
@@ -266,7 +267,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;
}
}
diff --git a/kernel/bpf/core.c b/kernel/bpf/core.c
index 5c4898c91a43..e96de7a2c786 100644
--- a/kernel/bpf/core.c
+++ b/kernel/bpf/core.c
@@ -663,6 +663,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);
@@ -670,10 +689,44 @@ void bpf_patch_list_release(struct bpf_patch_list *pl)
memset(pl, 0, sizeof(*pl));
}
+/*
+ * Map the index of each line info record to its new one in img->new_linfo[].
+ * The record of a removed insn goes away: it gets the index of the next
+ * record. The last one before the next insn that stays moves to that insn
+ * instead, unless the insn has its own line info.
+ */
+static int patch_image_map_linfo(struct bpf_patch_image *img, const struct bpf_prog *prog)
+{
+ const struct bpf_line_info *linfo = prog->aux->linfo;
+ u32 i, j, pos, next, nr = prog->aux->nr_linfo;
+
+ img->new_linfo = kvmalloc_array(nr + 1, sizeof(u32), GFP_KERNEL_ACCOUNT);
+ if (!img->new_linfo)
+ return -ENOMEM;
+ img->nr_linfo = nr;
+
+ for (i = 0, j = 0; i < nr; i++) {
+ img->new_linfo[i] = j;
+ if (bpf_patch_image_deleted(img, linfo[i].insn_off)) {
+ pos = bpf_patch_image_remap(img, img->new_off, linfo[i].insn_off);
+ next = i + 1 < nr ?
+ bpf_patch_image_remap(img, img->new_off, linfo[i + 1].insn_off) :
+ U32_MAX;
+ if (pos >= img->new_cnt || next == pos)
+ continue;
+ }
+ j++;
+ }
+ img->new_linfo[nr] = j;
+ return 0;
+}
+
/*
* Build the image of 'prog' with the queued patches applied in img->insns,
* without touching 'prog'. img->new_off[] maps each old insn to the start of
- * its patch. On -ERANGE, img->bad is the old insn whose jump got out of range.
+ * its patch, a removed insn to the next one that stays. img->new_linfo[] is
+ * there when insns are removed, see patch_image_map_linfo(). On -ERANGE,
+ * img->bad is the old insn whose jump got out of range.
*/
int bpf_patch_list_build(const struct bpf_patch_list *pl, const struct bpf_prog *prog,
struct bpf_patch_image *img)
@@ -689,11 +742,19 @@ 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;
+ if (img->del && prog->aux->nr_linfo) {
+ err = patch_image_map_linfo(img, prog);
+ if (err)
+ return err;
+ }
+
img->insns = kvmalloc_array(img->new_cnt, sizeof(*img->insns), GFP_KERNEL_ACCOUNT);
if (!img->insns)
return -ENOMEM;
@@ -723,6 +784,7 @@ int bpf_patch_list_build(const struct bpf_patch_list *pl, const struct bpf_prog
void bpf_patch_image_free(struct bpf_patch_image *img)
{
kvfree(img->insns);
+ kvfree(img->new_linfo);
kvfree(img->new_off);
memset(img, 0, sizeof(*img));
}
@@ -734,17 +796,22 @@ 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)
{
- u32 i;
+ struct bpf_line_info *linfo = prog->aux->linfo;
+ u32 i, j;
for (i = 0; i < prog->aux->size_poke_tab; i++)
prog->aux->poke_tab[i].insn_idx =
bpf_patch_image_remap(img, img->new_off,
prog->aux->poke_tab[i].insn_idx);
- for (i = 0; i < prog->aux->nr_linfo; i++)
- prog->aux->linfo[i].insn_off =
- bpf_patch_image_remap(img, img->new_off,
- prog->aux->linfo[i].insn_off);
+ for (i = 0, j = 0; i < prog->aux->nr_linfo; i++) {
+ if (img->new_linfo && img->new_linfo[i] == img->new_linfo[i + 1])
+ continue;
+ linfo[j] = linfo[i];
+ linfo[j++].insn_off = bpf_patch_image_remap(img, img->new_off,
+ linfo[i].insn_off);
+ }
+ prog->aux->nr_linfo = j;
memcpy(prog->insnsi, img->insns, sizeof(*img->insns) * img->new_cnt);
prog->len = img->new_cnt;
diff --git a/kernel/bpf/fixups.c b/kernel/bpf/fixups.c
index 0a5b35a00f9f..588a3a3b6615 100644
--- a/kernel/bpf/fixups.c
+++ b/kernel/bpf/fixups.c
@@ -383,6 +383,22 @@ struct bpf_insn *bpf_patch_list_add(struct bpf_verifier_env *env, u32 off,
return __bpf_patch_list_add(pl, env->prog, off, patch, len);
}
+/* Queue the removal of insn 'off' until bpf_patch_list_commit(). */
+int bpf_patch_list_del(struct bpf_verifier_env *env, u32 off)
+{
+ struct bpf_patch_list *pl = &env->patch_list;
+
+ if (bpf_rewrite_must_abort())
+ return -EINTR;
+
+ if (verifier_bug_if(off >= env->prog->len ||
+ (pl->cnt && off <= pl->patches[pl->cnt - 1].off),
+ env, "insn %u removed out of order", off))
+ return -EFAULT;
+
+ return __bpf_patch_list_del(pl, env->prog, off);
+}
+
void bpf_patch_list_free(struct bpf_verifier_env *env)
{
bpf_patch_list_release(&env->patch_list);
@@ -429,6 +445,32 @@ static void patch_list_adj_aux(struct bpf_prog *prog, struct bpf_insn_patch *p,
}
}
+/*
+ * Let go of each range of removed insns: tell the device, whose driver finds
+ * them through the aux data of the old image, and free what their aux data
+ * points to. The commit can't fail anymore, so there is no check for a fatal
+ * signal between the calls of the driver.
+ */
+static void patch_list_drop_removed(struct bpf_verifier_env *env)
+{
+ bool offloaded = bpf_prog_is_offloaded(env->prog->aux);
+ struct bpf_patch_list *pl = &env->patch_list;
+ u32 k, n;
+
+ for (k = 0; k < pl->cnt; k = n) {
+ for (n = k; n < pl->cnt && !pl->patches[n].len &&
+ pl->patches[n].off == pl->patches[k].off + n - k; n++)
+ ;
+ if (n == k) {
+ n++;
+ continue;
+ }
+ if (offloaded)
+ bpf_prog_offload_remove_insns(env, pl->patches[k].off, n - k);
+ bpf_clear_insn_aux_data(env, pl->patches[k].off, n - k);
+ }
+}
+
/* Fill 'data', the aux data of the new image, from the aux data of the old one. */
static void patch_list_remap_aux(struct bpf_verifier_env *env,
const struct bpf_patch_image *img,
@@ -441,9 +483,10 @@ static void patch_list_remap_aux(struct bpf_verifier_env *env,
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(env->prog, p, &pl->insns[p->start],
- &env->insn_aux_data[i],
- &data[img->new_off[i]]);
+ if (p->len)
+ patch_list_adj_aux(env->prog, p, &pl->insns[p->start],
+ &env->insn_aux_data[i],
+ &data[img->new_off[i]]);
end = i + 1;
continue;
}
@@ -456,10 +499,76 @@ static void patch_list_remap_aux(struct bpf_verifier_env *env,
env->insn_aux_data_len = img->new_cnt;
}
-/* Subprogs, and the function pointers that name them, follow their first insn. */
+/*
+ * Whether all insns from 'off' to the end of its subprog are removed. 'info'
+ * has the 'cnt' subprogs of the old image and the fake 'exit' subprog.
+ */
+static bool patch_list_subprog_gone(const struct bpf_subprog_info *info, u32 cnt,
+ const u32 *new_off, u32 off)
+{
+ u32 l = 0, r = cnt, m;
+
+ /* find the next subprog */
+ while (l < r) {
+ m = (l + r) / 2;
+ if (info[m].start <= off)
+ l = m + 1;
+ else
+ r = m;
+ }
+ return new_off[off] == new_off[info[l].start];
+}
+
+/*
+ * Remove the subprogs whose insns are all removed, with their func_info. The
+ * passes that remove insns run before the hidden subprog, which has no
+ * func_info, is added.
+ */
+static void patch_list_del_subprogs(struct bpf_verifier_env *env,
+ const u32 *new_off)
+{
+ struct bpf_subprog_info *info = env->subprog_info;
+ struct bpf_prog_aux *aux = env->prog->aux;
+ int i, j, exc_cb = env->exception_callback_subprog;
+
+ for (i = 0, j = 0; i < env->subprog_cnt; i++) {
+ if (new_off[info[i].start] == new_off[info[i + 1].start]) {
+ /* The exception callback is live, so it isn't removed. */
+ if (env->exception_callback_subprog > i)
+ exc_cb--;
+ continue;
+ }
+ if (i != j) {
+ info[j] = info[i];
+ if (aux->func_info)
+ aux->func_info[j] = aux->func_info[i];
+ if (aux->func_info_aux)
+ aux->func_info_aux[j] = aux->func_info_aux[i];
+ }
+ j++;
+ }
+ if (i == j)
+ return;
+
+ /* move fake 'exit' subprog as well */
+ info[j] = info[i];
+ /* func_info->insn_off is set after all code rewrites, in adjust_btf_func() */
+ if (aux->func_info)
+ aux->func_info_cnt -= i - j;
+ env->subprog_cnt = j;
+ env->exception_callback_subprog = exc_cb;
+}
+
+/*
+ * Subprogs, and the function pointers that name them, follow their first insn.
+ * A subprog whose insns are all removed goes away, and so do the pointers to
+ * it. Only the subprogs tell where a function ends, so move the pointers while
+ * the subprogs still have the starts in the old image.
+ */
static void patch_list_remap_subprogs(struct bpf_verifier_env *env,
const struct bpf_patch_image *img)
{
+ struct bpf_subprog_info *info = env->subprog_info;
u32 i;
for (i = 0; i < env->func_ptr_cnt; i++) {
@@ -467,29 +576,53 @@ static void patch_list_remap_subprogs(struct bpf_verifier_env *env,
if (fp->xlated_off == BPF_FUNC_PTR_DELETED)
continue;
- fp->xlated_off = bpf_patch_image_remap(img, img->new_off, fp->xlated_off);
+ if (bpf_patch_image_deleted(img, fp->xlated_off) &&
+ patch_list_subprog_gone(info, env->subprog_cnt, img->new_off,
+ fp->xlated_off))
+ fp->xlated_off = BPF_FUNC_PTR_DELETED;
+ else
+ 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);
+
/* 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->subprog_cnt; i++) {
+ info[i].start = bpf_patch_image_remap(img, img->new_off, info[i].start);
+ if (img->new_linfo)
+ info[i].linfo_idx =
+ img->new_linfo[min(info[i].linfo_idx, img->nr_linfo)];
+ }
}
/*
- * 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().
+ * 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, like with bpf_patch_insn_data().
+ *
+ * An entry that names a removed insn:
+ * jump, call, poke descriptor names the next insn that stays
+ * subprog too, or goes away when none of its insns stays
+ * function pointer follows its subprog or is BPF_FUNC_PTR_DELETED
+ * line info goes away, but the next insn that stays takes
+ * the last record when it has none
+ * aux data goes away
+ * instruction array is INSN_DELETED
*
* The order of the steps is a rule:
* 1. All that can fail: build the new image aside and allocate memory. An
* error leaves the program and the env as they were.
- * 2. Move each table that names insns. The new value of an entry depends on
- * its old value and on the maps of the image only. Between the first and
- * the last step one part of the env describes the old image and another
- * part the new one, so don't call a helper that reads prog->len, the insns
- * or one of these tables from the env or the program.
- * 3. Install the new image.
+ * 2. Let go of the removed insns while all of the env describes the old image:
+ * the helpers for that look at it.
+ * 3. Move each table that names insns. The new value of an entry depends on
+ * its old value and on the maps of the image only. Function pointers need
+ * the old subprogs too, see patch_list_remap_subprogs(). Between the first
+ * and the last table one part of the env describes the old image and
+ * another part the new one, so don't call a helper that reads prog->len,
+ * the insns or one of these tables from the env or the program.
+ * 4. Install the new image.
*/
int bpf_patch_list_commit(struct bpf_verifier_env *env)
{
@@ -527,6 +660,9 @@ int bpf_patch_list_commit(struct bpf_verifier_env *env)
env->prog = prog;
err = 0;
+ if (img.del)
+ patch_list_drop_removed(env);
+
patch_list_remap_aux(env, &img, data);
data = NULL;
patch_list_remap_subprogs(env, &img);
--
2.55.0
^ permalink raw reply related [flat|nested] 18+ messages in thread* [PATCH bpf-next v3 05/13] bpf: Move the bpf_opt_*() passes to the patch list
2026-11-02 1:29 [PATCH bpf-next v3 00/13] bpf: Replace bpf_patch_insn_data() with a list of deferred patches Alexei Starovoitov
` (3 preceding siblings ...)
2026-11-02 1:29 ` [PATCH bpf-next v3 04/13] bpf: Let the patch list remove instructions Alexei Starovoitov
@ 2026-11-02 1:29 ` Alexei Starovoitov
2026-11-02 1:29 ` [PATCH bpf-next v3 06/13] bpf: Allow patching an instruction twice through " Alexei Starovoitov
` (9 subsequent siblings)
14 siblings, 0 replies; 18+ messages in thread
From: Alexei Starovoitov @ 2026-11-02 1:29 UTC (permalink / raw)
To: bpf; +Cc: daniel, andrii, eddyz87, memxor, odys.yuan
From: Qiliang Yuan <odys.yuan@gmail.com>
bpf_opt_remove_dead_code() and bpf_opt_remove_nops() call
verifier_remove_insns() for each range that they remove.
bpf_opt_subreg_zext_lo32_rnd_hi32() calls bpf_patch_insn_data() for each
32-bit result whose upper half it sets: 4605 times in pyperf180 with
BPF_F_TEST_RND_HI32. Each call costs O(N) in a prog of N insns.
Queue the changes in the patch list, and commit one time at the end of each
pass. A commit costs O(N + inserted insns). Then verifier_remove_insns()
and its static helpers have no users. Remove them. Only
bpf_opt_remove_nops() is not mechanical.
The removal of a nop can make the jump in front of it a nop. The pass
cannot see that in the offset, because no insn moves before the commit.
Only a forward jump can become a nop. Thus walk from the end: at insn i the
walk knows which insns behind i stay. 'next' is the first of them. A 'goto'
or a may_goto is a nop when its target is behind i and not behind 'next'.
old image next target patch list
0: r0 = 0 4
1: goto +2 4 4 removal
2: may_goto +1 4 4 removal
3: may_goto +0 4 4 removal
4: exit 5 the walk starts here
The list takes insns in their order. Thus the walk marks the nops in a
bitmap, and a second walk queues the removals.
What users can see: bpf_opt_remove_nops() also removes a 'goto' or a
may_goto over 'goto +0' only. Before this patch 'goto +1; goto +0' becomes
'goto +0'. In bpf_opt_subreg_zext_lo32_rnd_hi32() a jump that gets out of
range gives -ERANGE, and the message names the jump. Before this patch the
pass returns -ENOMEM, and the message names the patched insn.
Load times in an x86_64 VM with 8 vCPUs, before and after this patch.
BPF_PROG_LOAD of a prog with n 'goto +0', mean of 3 runs:
before after
n = 32768 2.040 s 0.060 s
n = 131072 33.333 s 0.244 s
Wall time of 'veristat -q <obj>' with BPF_F_TEST_RND_HI32, mean of 10 runs:
before after
pyperf180 0.549 s 0.087 s
pyperf600 1.625 s 0.221 s
Signed-off-by: Qiliang Yuan <odys.yuan@gmail.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
---
kernel/bpf/fixups.c | 266 +++++++++-----------------------------------
1 file changed, 52 insertions(+), 214 deletions(-)
diff --git a/kernel/bpf/fixups.c b/kernel/bpf/fixups.c
index 588a3a3b6615..6fe47e400bc2 100644
--- a/kernel/bpf/fixups.c
+++ b/kernel/bpf/fixups.c
@@ -273,14 +273,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;
@@ -754,133 +746,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)
{
@@ -897,44 +762,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);
@@ -1029,49 +856,66 @@ 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);
+}
+
+/*
+ * Whether insn i is a nop once the insns between it and 'next' are gone: "ja"
+ * or may_goto that goes to 'next' at most.
+ */
+static bool insn_is_nop(struct bpf_verifier_env *env, int i, int next)
+{
+ struct bpf_insn insn = env->prog->insnsi[i];
+
+ if (env->insn_aux_data[i].indirect_target)
+ return false;
+ if (insn.off < 0 || i + 1 + insn.off > next)
+ return false;
+ 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, next, 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 = kvcalloc(BITS_TO_LONGS(insn_cnt), sizeof(long), GFP_KERNEL_ACCOUNT);
+ if (!removed)
+ return -ENOMEM;
- if (!is_may_goto_0 && !is_ja)
- continue;
- if (aux[i].indirect_target)
- continue;
+ /*
+ * Removing may_goto +0 turns the may_goto +1 in front of it into
+ * another one. Only a forward jump can turn into a nop, so walk from
+ * the end: all that insn i jumps over is decided when the walk gets to
+ * it. 'next' is the first insn behind i that stays. For a forward jump
+ * it is in the subprog of i, because a subprog doesn't end with one.
+ */
+ for (i = insn_cnt - 1, next = insn_cnt; i >= 0; i--) {
+ if (insn_is_nop(env, i, next))
+ __set_bit(i, removed);
+ else
+ next = i;
+ }
- 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;
}
+ kvfree(removed);
- return 0;
+ return err ?: bpf_patch_list_commit(env);
}
int bpf_opt_subreg_zext_lo32_rnd_hi32(struct bpf_verifier_env *env,
@@ -1082,9 +926,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;
@@ -1093,13 +936,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;
@@ -1120,7 +962,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();
@@ -1159,16 +1001,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);
}
/*
--
2.55.0
^ permalink raw reply related [flat|nested] 18+ messages in thread* [PATCH bpf-next v3 06/13] bpf: Allow patching an instruction twice through the patch list
2026-11-02 1:29 [PATCH bpf-next v3 00/13] bpf: Replace bpf_patch_insn_data() with a list of deferred patches Alexei Starovoitov
` (4 preceding siblings ...)
2026-11-02 1:29 ` [PATCH bpf-next v3 05/13] bpf: Move the bpf_opt_*() passes to the patch list Alexei Starovoitov
@ 2026-11-02 1:29 ` Alexei Starovoitov
2026-11-02 1:29 ` [PATCH bpf-next v3 07/13] bpf: Teach the patch list to insert in front of an instruction Alexei Starovoitov
` (8 subsequent siblings)
14 siblings, 0 replies; 18+ messages in thread
From: Alexei Starovoitov @ 2026-11-02 1:29 UTC (permalink / raw)
To: bpf; +Cc: daniel, andrii, eddyz87, memxor, odys.yuan
From: Qiliang Yuan <odys.yuan@gmail.com>
bpf_convert_ctx_accesses() can patch one insn two times. The first patch
puts a barrier ('nospec') in front of the insn. The second patch replaces
the insn, for example a ctx access. bpf_patch_insn_data() moves the insn
immediately, and the second call gets its new index. The patch list only
queues a patch, and no insn moves before the commit. Thus a queued insn has
no index, and bpf_patch_list_add() accepts only one patch for each insn.
Let a second bpf_patch_list_add() for the same insn replace the last insn
of the queued patch. That is where the first patch puts the insn. The
result is one patch. Here insn i reads skb->ifindex:
queued patch of insn i after the second bpf_patch_list_add()
nospec nospec
r0 = *(u32 *)(r1 + 40) r0 = *(u64 *)(r1 + 16)
if r0 == 0 goto +1
r0 = *(u32 *)(r0 + 224)
- The pass writes the second patch as if it was the only patch of insn i.
But in the list its insns are behind the barrier. Thus a backward jump
or call that leaves the patch gets longer by the number of insns in
front: 'gotol -5' becomes 'gotol -6'. A forward jump, as the
'if r0 == 0 goto +1' above, does not change.
- In this pass only the 'gotol' from an 'exit' back to the first epilogue
is such a backward jump. No prog has it behind a barrier. A prog with an
epilogue needs CAP_PERFMON, and then the verifier adds no barrier. The
list adjusts the jump all the same, because bpf_patch_list_add() must
not depend on what its callers queue.
- The second patch changes the length of the queued patch. Thus the insns
in front of the last insn must not jump behind the patch. A barrier does
not jump. For such a jump bpf_patch_list_add() returns -EFAULT with a
WARN.
- A second patch of 1 insn goes to the list. It is not written in place,
because the commit takes the insn from the list.
Signed-off-by: Qiliang Yuan <odys.yuan@gmail.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
---
kernel/bpf/core.c | 64 +++++++++++++++++++++++++++++++++++++++++++--
kernel/bpf/fixups.c | 9 ++++---
2 files changed, 68 insertions(+), 5 deletions(-)
diff --git a/kernel/bpf/core.c b/kernel/bpf/core.c
index e96de7a2c786..633728a5f0ea 100644
--- a/kernel/bpf/core.c
+++ b/kernel/bpf/core.c
@@ -602,6 +602,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
@@ -634,7 +674,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.
@@ -645,9 +688,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);
diff --git a/kernel/bpf/fixups.c b/kernel/bpf/fixups.c
index 6fe47e400bc2..7f8d51617b2e 100644
--- a/kernel/bpf/fixups.c
+++ b/kernel/bpf/fixups.c
@@ -350,28 +350,31 @@ 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(). Replacing one insn by
- * one moves nothing and is done right away.
+ * one moves nothing and is done right away in the program, unless 'off' has a
+ * queued patch: the commit takes the insn from there.
*/
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);
return &env->prog->insnsi[off];
}
+ /* -ERANGE takes a second patch with a 16-bit jump back out of it: no pass has one */
return __bpf_patch_list_add(pl, env->prog, off, patch, len);
}
--
2.55.0
^ permalink raw reply related [flat|nested] 18+ messages in thread* [PATCH bpf-next v3 07/13] bpf: Teach the patch list to insert in front of an instruction
2026-11-02 1:29 [PATCH bpf-next v3 00/13] bpf: Replace bpf_patch_insn_data() with a list of deferred patches Alexei Starovoitov
` (5 preceding siblings ...)
2026-11-02 1:29 ` [PATCH bpf-next v3 06/13] bpf: Allow patching an instruction twice through " Alexei Starovoitov
@ 2026-11-02 1:29 ` Alexei Starovoitov
2026-11-02 1:29 ` [PATCH bpf-next v3 08/13] bpf: Move bpf_convert_ctx_accesses() to the patch list Alexei Starovoitov
` (7 subsequent siblings)
14 siblings, 0 replies; 18+ messages in thread
From: Alexei Starovoitov @ 2026-11-02 1:29 UTC (permalink / raw)
To: bpf; +Cc: daniel, andrii, eddyz87, memxor, odys.yuan
From: Qiliang Yuan <odys.yuan@gmail.com>
Two passes put new insns in front of an insn that stays.
bpf_convert_ctx_accesses() puts the prologue in front of the first insn of
the prog. bpf_do_misc_fixups() puts the setup of the may_goto count in
front of a subprog. A call of the subprog must run the setup. A jump back
to its first insn must not, because the count would start again.
A patch with the new insns and a copy of the insn is not sufficient. The
commit of the patch list has one map from old index to new index,
new_off[]. A patched insn maps to the first insn of its patch. That is
correct for the call and incorrect for the jump. __bpf_patch_insn_data()
has the mode BPF_PATCH_MOVE_TARGET for the tables, and adjust_jmp_off()
walks all insns again for the jumps.
Add bpf_patch_list_insert(). It queues the inserted insns and a copy of the
insn as one patch. The new field 'target' of the patch counts the inserted
insns. The commit calculates a second map, new_tgt[], which adds 'target'
to new_off[]. Thus new_off[i] is the first inserted insn, and new_tgt[i] is
insn i. The two maps differ only there.
old image patch list new_off[] new_tgt[] new image
0: call +1 0 0 0: call +1
1: exit 1 1 1: exit
2: r1 += -1 insert 1 insn 2 3 2: i1
3: r1 += -1
3: goto -2 4 4 4: goto -2
The call lands on the inserted insn i1, and the jump lands on 'r1 += -1'.
All that names insn i goes through one of the two maps:
what names insn i new index reason
---------------------- ---------- -------------------------------------
call, function pointer new_off[i] It enters the subprog. The inserted
insns must run.
subprog, line info new_off[i] The subprog starts with the inserted
insns, and with a line info record.
jump, insn array, new_tgt[i] It goes to insn i. The inserted insns
indirect_target flag must not run again.
poke descriptor new_tgt[i] It names the tail call at insn i.
The copy of insn i is behind the inserted insns. When it is a backward jump
or call, it gets longer by their number, as with bpf_adj_moved_insn().
When insn i has a queued patch, the new insns go in front of all of it.
bpf_convert_ctx_accesses() inserts the store of ctx for the epilogue in
front of insn 0. Then it inserts the prologue in front of the store.
Signed-off-by: Qiliang Yuan <odys.yuan@gmail.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
---
include/linux/bpf.h | 3 +-
include/linux/bpf_verifier.h | 6 +++
kernel/bpf/bpf_insn_array.c | 11 +++---
kernel/bpf/core.c | 74 +++++++++++++++++++++++++++++++-----
kernel/bpf/fixups.c | 39 ++++++++++++++++---
5 files changed, 111 insertions(+), 22 deletions(-)
diff --git a/include/linux/bpf.h b/include/linux/bpf.h
index ba96b4fc893a..b21a29a76b94 100644
--- a/include/linux/bpf.h
+++ b/include/linux/bpf.h
@@ -4380,7 +4380,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);
diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index b77a0ba477f1..f8498de5eff5 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -1064,6 +1064,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 */
};
@@ -1084,6 +1085,7 @@ struct bpf_patch_list {
struct bpf_patch_image {
struct bpf_insn *insns;
u32 *new_off;
+ u32 *new_tgt;
u32 *new_linfo;
u32 cnt;
u32 new_cnt;
@@ -1110,6 +1112,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);
@@ -2082,6 +2086,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);
diff --git a/kernel/bpf/bpf_insn_array.c b/kernel/bpf/bpf_insn_array.c
index e2e4aee00c4d..79c5441ddd00 100644
--- a/kernel/bpf/bpf_insn_array.c
+++ b/kernel/bpf/bpf_insn_array.c
@@ -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 i, off;
@@ -270,7 +271,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;
}
}
diff --git a/kernel/bpf/core.c b/kernel/bpf/core.c
index 633728a5f0ea..2deb5584dc85 100644
--- a/kernel/bpf/core.c
+++ b/kernel/bpf/core.c
@@ -645,16 +645,19 @@ static int patch_list_move_down(struct bpf_insn *insns, u32 len, u32 by)
/*
* 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
- * at 'pos' of the new image. 'new_off' maps the old image to the new one.
+ * at 'pos' of the new image. 'new_off' maps the old image to the start of
+ * each patch, which calls go to, 'new_tgt' to where jumps go.
*/
static int patch_list_adj_insn(struct bpf_insn *insn, const u32 *new_off,
- u32 cnt, u32 off, u32 idx, u32 len, u32 pos)
+ const u32 *new_tgt, u32 cnt, u32 off, u32 idx,
+ u32 len, u32 pos)
{
- bool is_imm;
+ bool is_imm, call;
s64 rel, tgt;
if (!insn_get_rel(insn, &rel, &is_imm))
return 0;
+ call = bpf_pseudo_func(insn) || bpf_pseudo_call(insn);
/* relative to the first insn of the patch */
tgt = (s64)idx + rel + 1;
@@ -666,7 +669,7 @@ static int patch_list_adj_insn(struct bpf_insn *insn, const u32 *new_off,
if (tgt < 0 || tgt > cnt)
return -EFAULT;
- rel = (s64)new_off[tgt] - pos - 1;
+ rel = (s64)(call ? new_off : new_tgt)[tgt] - pos - 1;
return insn_set_rel(insn, rel, is_imm);
}
@@ -715,6 +718,7 @@ struct bpf_insn *__bpf_patch_list_add(struct bpf_patch_list *pl,
p = &pl->patches[pl->cnt++];
p->off = off;
p->len = len;
+ p->target = 0;
p->start = pl->insn_cnt;
p->orig = prog->insnsi[off];
memcpy(pl->insns + p->start, patch, len * sizeof(*patch));
@@ -737,11 +741,56 @@ int __bpf_patch_list_del(struct bpf_patch_list *pl, const struct bpf_prog *prog,
p = &pl->patches[pl->cnt++];
p->off = off;
p->len = 0;
+ p->target = 0;
p->start = pl->insn_cnt;
p->orig = prog->insnsi[off];
return 0;
}
+/*
+ * 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. Inserting in front of a queued patch puts the
+ * insns in front of it. 'off' is the start of a subprog, so nothing falls
+ * through to the inserted insns.
+ */
+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 = pl->cnt ? &pl->patches[pl->cnt - 1] : NULL;
+ int err;
+
+ 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)
+ return err;
+
+ /* the last patch is at the end of pl->insns */
+ err = patch_list_move_down(pl->insns + p->start, p->len, cnt);
+ if (err)
+ return err;
+ memmove(pl->insns + p->start + cnt, pl->insns + p->start,
+ p->len * sizeof(*insns));
+ memcpy(pl->insns + p->start, insns, cnt * sizeof(*insns));
+ p->len += cnt;
+ p->target += cnt;
+ pl->insn_cnt += cnt;
+ return 0;
+}
+
void bpf_patch_list_release(struct bpf_patch_list *pl)
{
kvfree(pl->patches);
@@ -784,9 +833,10 @@ static int patch_image_map_linfo(struct bpf_patch_image *img, const struct bpf_p
/*
* Build the image of 'prog' with the queued patches applied in img->insns,
* without touching 'prog'. img->new_off[] maps each old insn to the start of
- * its patch, a removed insn to the next one that stays. img->new_linfo[] is
- * there when insns are removed, see patch_image_map_linfo(). On -ERANGE,
- * img->bad is the old insn whose jump got out of range.
+ * its patch, img->new_tgt[] to where jumps to it land, both map a removed insn
+ * to the next one that stays. img->new_linfo[] is there when insns are
+ * removed, see patch_image_map_linfo(). On -ERANGE, img->bad is the old insn
+ * whose jump got out of range. No list has both removed and inserted insns.
*/
int bpf_patch_list_build(const struct bpf_patch_list *pl, const struct bpf_prog *prog,
struct bpf_patch_image *img)
@@ -797,12 +847,15 @@ int bpf_patch_list_build(const struct bpf_patch_list *pl, const struct bpf_prog
memset(img, 0, sizeof(*img));
img->cnt = cnt;
img->new_off = kvmalloc_array(cnt + 1, sizeof(u32), GFP_KERNEL_ACCOUNT);
- if (!img->new_off)
+ img->new_tgt = kvmalloc_array(cnt + 1, sizeof(u32), GFP_KERNEL_ACCOUNT);
+ if (!img->new_off || !img->new_tgt)
return -ENOMEM;
for (i = 0, k = 0; i <= cnt; i++) {
img->new_off[i] = i + img->grow;
+ img->new_tgt[i] = img->new_off[i];
if (k < pl->cnt && pl->patches[k].off == i) {
+ img->new_tgt[i] += pl->patches[k].target;
img->del |= !pl->patches[k].len;
img->grow += pl->patches[k++].len - 1;
}
@@ -831,7 +884,7 @@ int bpf_patch_list_build(const struct bpf_patch_list *pl, const struct bpf_prog
for (n = 0; n < len; n++) {
img->insns[pos + n] = src[n];
err = patch_list_adj_insn(&img->insns[pos + n], img->new_off,
- cnt, i, n, len, pos + n);
+ img->new_tgt, cnt, i, n, len, pos + n);
if (err) {
img->bad = i;
return err;
@@ -845,6 +898,7 @@ void bpf_patch_image_free(struct bpf_patch_image *img)
{
kvfree(img->insns);
kvfree(img->new_linfo);
+ kvfree(img->new_tgt);
kvfree(img->new_off);
memset(img, 0, sizeof(*img));
}
@@ -861,7 +915,7 @@ void bpf_patch_image_install(struct bpf_prog *prog, const struct bpf_patch_image
for (i = 0; i < prog->aux->size_poke_tab; i++)
prog->aux->poke_tab[i].insn_idx =
- bpf_patch_image_remap(img, img->new_off,
+ bpf_patch_image_remap(img, img->new_tgt,
prog->aux->poke_tab[i].insn_idx);
for (i = 0, j = 0; i < prog->aux->nr_linfo; i++) {
diff --git a/kernel/bpf/fixups.c b/kernel/bpf/fixups.c
index 7f8d51617b2e..147fcc4d2f43 100644
--- a/kernel/bpf/fixups.c
+++ b/kernel/bpf/fixups.c
@@ -394,6 +394,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 || (off == p->off && !p->len))),
+ 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);
@@ -402,6 +425,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,
@@ -421,7 +445,7 @@ static void patch_list_adj_aux(struct bpf_prog *prog, struct bpf_insn_patch *p,
/* messages name the insn of the original program */
slot[i].orig_idx = last->orig_idx;
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])) {
@@ -433,9 +457,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;
}
}
@@ -595,7 +619,10 @@ static void patch_list_remap_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, like with bpf_patch_insn_data().
+ * the first insn of its patch, like with bpf_patch_insn_data(). If insns were
+ * inserted in front of an insn, jumps, instruction arrays and poke descriptors
+ * name the insn itself, while subprogs, line info, function pointers and calls
+ * name the first inserted insn.
*
* An entry that names a removed insn:
* jump, call, poke descriptor names the next insn that stays
@@ -663,7 +690,7 @@ int bpf_patch_list_commit(struct bpf_verifier_env *env)
patch_list_remap_subprogs(env, &img);
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);
bpf_patch_image_install(prog, &img);
out:
--
2.55.0
^ permalink raw reply related [flat|nested] 18+ messages in thread* [PATCH bpf-next v3 08/13] bpf: Move bpf_convert_ctx_accesses() to the patch list
2026-11-02 1:29 [PATCH bpf-next v3 00/13] bpf: Replace bpf_patch_insn_data() with a list of deferred patches Alexei Starovoitov
` (6 preceding siblings ...)
2026-11-02 1:29 ` [PATCH bpf-next v3 07/13] bpf: Teach the patch list to insert in front of an instruction Alexei Starovoitov
@ 2026-11-02 1:29 ` Alexei Starovoitov
2026-11-02 1:29 ` [PATCH bpf-next v3 09/13] bpf: Move the remaining verifier rewrites " Alexei Starovoitov
` (6 subsequent siblings)
14 siblings, 0 replies; 18+ messages in thread
From: Alexei Starovoitov @ 2026-11-02 1:29 UTC (permalink / raw)
To: bpf; +Cc: daniel, andrii, eddyz87, memxor, odys.yuan
From: Qiliang Yuan <odys.yuan@gmail.com>
bpf_convert_ctx_accesses() replaces each ctx access with insns that access
the kernel struct. It also adds barriers, and the prologue and the epilogue
of the prog type. It calls bpf_patch_insn_data() for each of them. Each
call costs O(N) in a prog of N insns.
Queue the changes in the patch list. A commit builds the new image of the
prog from the old image and the list. The pass needs two commits:
insert the store of ctx for the epilogue, in front of insn 0
insert the prologue, in front of the store
commit
loop starts behind the inserted insns
queue a patch: barrier, ctx access, epilogue
write in place: for example BPF_MEM becomes BPF_PROBE_MEM
commit
The first commit is necessary because of the writes in place.
bpf_patch_list_insert() puts a copy of insn 0 in the list, and the commit
takes the copy. A write to insn 0 of the old image would be lost.
What else is not mechanical:
- gen_prologue() ends the prologue with a copy of the first insn of the
prog. bpf_patch_list_insert() makes this copy. Thus insert the prologue
without its last insn, after a check that it is this copy.
- A barrier in front of an insn is a patch: 'nospec' and a copy of the
insn. It is not inserted, because a jump to the insn must run the
barrier. bpf_patch_list_add() returns the queued copy of the insn, and
the loop continues with the copy. A write in place goes to the copy, and
a second patch replaces it.
- Only the first 'exit' of the main prog gets the epilogue. Each other
'exit' becomes a 'gotol' back to it. The pass calculates the offset from
old indexes, and the commit adjusts it.
What users can see:
- A jump that gets out of range gives -ERANGE, and the message names the
jump. Before this patch the pass returns -ENOMEM, and the message names
the patched insn.
- A jump back to insn 0 lands behind the inserted insns and keeps its
offset. Before this patch the offset first gets longer by their number,
and adjust_jmp_off() then restores it. Thus an offset near -32768 fails
the load.
Signed-off-by: Qiliang Yuan <odys.yuan@gmail.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
---
kernel/bpf/fixups.c | 131 +++++++++++++++++++-------------------------
1 file changed, 55 insertions(+), 76 deletions(-)
diff --git a/kernel/bpf/fixups.c b/kernel/bpf/fixups.c
index 147fcc4d2f43..9216b19370c3 100644
--- a/kernel/bpf/fixups.c
+++ b/kernel/bpf/fixups.c
@@ -1098,13 +1098,11 @@ 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;
- const int insn_cnt = env->prog->len;
+ int i, cnt, size, ctx_field_size, ret, epilogue_cnt = 0, first = 0;
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;
@@ -1117,17 +1115,13 @@ 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;
+ first++;
ret = add_kfunc_in_insns(env, epilogue_buf, epilogue_cnt - 1);
if (ret < 0)
@@ -1158,13 +1152,15 @@ 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;
+ first += cnt - 1;
ret = add_kfunc_in_insns(env, insn_buf, cnt - 1);
if (ret < 0)
@@ -1172,21 +1168,26 @@ int bpf_convert_ctx_accesses(struct bpf_verifier_env *env)
}
}
- if (delta)
- WARN_ON(adjust_jmp_off(env->prog, 0, delta));
+ /*
+ * The loop below rewrites some insns in place. No insn may have a queued
+ * patch when the loop gets to it: the list holds a copy of the insn.
+ */
+ ret = bpf_patch_list_commit(env);
+ if (ret)
+ return ret;
if (bpf_prog_is_offloaded(env->prog->aux))
return 0;
- insn = env->prog->insnsi + delta;
-
- for (i = 0; i < insn_cnt; i++, insn++) {
+ for (i = first; i < env->prog->len; 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();
@@ -1194,17 +1195,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
@@ -1234,32 +1231,28 @@ 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) {
/* 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,
@@ -1269,7 +1262,7 @@ int bpf_convert_ctx_accesses(struct bpf_verifier_env *env)
* least one ctx ptr saving insn before the
* epilogue.
*/
- epilogue_idx = i + delta;
+ epilogue_idx = i;
}
goto patch_insn_buf;
} else {
@@ -1277,7 +1270,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.
*/
@@ -1286,17 +1279,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)
@@ -1349,22 +1338,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);
@@ -1432,18 +1417,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)
--
2.55.0
^ permalink raw reply related [flat|nested] 18+ messages in thread* [PATCH bpf-next v3 09/13] bpf: Move the remaining verifier rewrites to the patch list
2026-11-02 1:29 [PATCH bpf-next v3 00/13] bpf: Replace bpf_patch_insn_data() with a list of deferred patches Alexei Starovoitov
` (7 preceding siblings ...)
2026-11-02 1:29 ` [PATCH bpf-next v3 08/13] bpf: Move bpf_convert_ctx_accesses() to the patch list Alexei Starovoitov
@ 2026-11-02 1:29 ` Alexei Starovoitov
2026-11-02 1:29 ` [PATCH bpf-next v3 10/13] bpf: Blind constants through " Alexei Starovoitov
` (5 subsequent siblings)
14 siblings, 0 replies; 18+ messages in thread
From: Alexei Starovoitov @ 2026-11-02 1:29 UTC (permalink / raw)
To: bpf; +Cc: daniel, andrii, eddyz87, memxor, odys.yuan
From: Qiliang Yuan <odys.yuan@gmail.com>
Three passes of the verifier call bpf_patch_insn_data(), which patches one
insn immediately. Each call costs O(N) in a prog of N insns.
Queue the changes in the patch list, and commit one time at the end of the
pass. The commit builds the new image of the prog from the old image and
the list. No insn moves before the commit. Thus a pass uses old indexes
only.
pass what it does, and what is not mechanical
----------------------- ------------------------------------------------
bpf_do_misc_fixups(), It puts 1 or 2 stores in front of each subprog
setup of the may_goto that has may_goto. Use bpf_patch_list_insert().
count A call of the subprog lands on the stores, and
a jump to its first insn lands on that insn.
Thus adjust_jmp_off() has no users. Remove it.
add_hidden_subprog() It puts the default exception callback behind
the last insn. The patch is that insn and the
new insns. Commit immediately, because the new
prog->len gives the start of the new subprog.
bpf_optimize_bpf_loop() It replaces a call of bpf_loop() with a loop of
19 insns. insn_buf[12] calls the callback, and
this call leaves its patch.
The new start of the callback is not known before the commit. Thus
inline_bpf_loop() writes the offset of this call as if this patch was the
only one. The commit adjusts it for the other patches.
callback offset of the call, for bpf_loop() at index i
------------- ---------------------------------------------
in front of i old start - (i + 12) - 1
behind i old start + 18 - (i + 12) - 1
18 is the growth of the patch, the number of insns that it adds.
What users can see:
- A jump that gets out of range gives -ERANGE, and the message names the
jump. Before this patch the passes return -ENOMEM, and the message names
the patched insn.
- A jump back to the first insn of a subprog keeps its offset when the
stores go in front. Before this patch the offset first gets longer by
their number, and adjust_jmp_off() then restores it. Thus an offset near
-32768 fails the load.
Signed-off-by: Qiliang Yuan <odys.yuan@gmail.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
---
kernel/bpf/fixups.c | 155 +++++++++++++-------------------------------
1 file changed, 46 insertions(+), 109 deletions(-)
diff --git a/kernel/bpf/fixups.c b/kernel/bpf/fixups.c
index 9216b19370c3..d0d099c34c80 100644
--- a/kernel/bpf/fixups.c
+++ b/kernel/bpf/fixups.c
@@ -738,44 +738,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)
{
@@ -1924,7 +1886,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. */
@@ -1932,14 +1895,17 @@ static int add_hidden_subprog(struct bpf_verifier_env *env, struct bpf_insn *pat
verifier_bug(env, "only one hidden subprog supported");
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.
+ /*
+ * We're not patching any existing instruction, just appending the new
+ * 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. */
@@ -2011,7 +1977,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;
@@ -2842,10 +2807,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;
@@ -2855,6 +2818,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,
@@ -2865,30 +2829,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;
@@ -2909,11 +2860,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;
@@ -2923,9 +2871,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;
@@ -2951,9 +2898,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);
@@ -2970,19 +2915,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 and calls
+ * out of a patch are relative to the patch placed at 'position': its
+ * 'cnt' insns push what is behind 'position' down by cnt - 1.
+ */
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)
@@ -3004,7 +2949,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;
@@ -3013,26 +2958,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;
@@ -3043,7 +2980,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,
--
2.55.0
^ permalink raw reply related [flat|nested] 18+ messages in thread* [PATCH bpf-next v3 10/13] bpf: Blind constants through the patch list
2026-11-02 1:29 [PATCH bpf-next v3 00/13] bpf: Replace bpf_patch_insn_data() with a list of deferred patches Alexei Starovoitov
` (8 preceding siblings ...)
2026-11-02 1:29 ` [PATCH bpf-next v3 09/13] bpf: Move the remaining verifier rewrites " Alexei Starovoitov
@ 2026-11-02 1:29 ` Alexei Starovoitov
2026-11-02 1:29 ` [PATCH bpf-next v3 11/13] bpf: Remove the old instruction patching code Alexei Starovoitov
` (4 subsequent siblings)
14 siblings, 0 replies; 18+ messages in thread
From: Alexei Starovoitov @ 2026-11-02 1:29 UTC (permalink / raw)
To: bpf; +Cc: daniel, andrii, eddyz87, memxor, odys.yuan
From: Qiliang Yuan <odys.yuan@gmail.com>
When bpf_jit_harden is on, the constants of a prog must not be in the JITed
code. bpf_jit_blind_constants() replaces each insn that has a constant with
3 or 4 insns that calculate it. It patches each of these insns immediately,
with bpf_patch_insn_data() or bpf_patch_insn_single(). Each call costs O(N)
in a prog of N insns.
One prog of test_verifier has a million insns:
"ld_dw: xor semi-random 64 bit imms, test 5". With bpf_jit_harden=2 it does
not load in 15 minutes.
Queue the patches in the patch list, and commit one time at the end of the
pass. bpf_patch_list_commit() needs bpf_verifier_env (env). But the pass
also runs without env, for example for classic BPF progs. Add
bpf_patch_list_apply(), the commit without env. In that case the list is a
local variable of the pass.
step bpf_patch_list_commit() bpf_patch_list_apply()
----------------- ---------------------------- ----------------------
all that can fail new image, aux data, prog new image, prog
removed insns offload device, aux data WARN, -EINVAL
the tables of the verifier, of the prog of the prog
the new image insns, prog->len insns, prog->len
- No pass without env removes insns. Thus bpf_patch_list_apply() rejects a
list that has a removal.
- bpf_jit_blind_insn() does not change. It writes a jump as if its patch
was the only one, and that is the rule of the list.
- The reallocation of the prog is the last thing that can fail. Thus an
error leaves 'clone' valid, and the pass can free it.
- With env, a jump that gets out of range gives -ERANGE, and the message
names the jump. Before this patch the pass returns -ENOMEM, and the
message names the patched insn.
- core.c is also built without the verifier, when CONFIG_BPF_SYSCALL is
off. Add stubs for the functions of the verifier that the pass calls.
Load times with bpf_jit_harden=2 in an x86_64 VM with 8 vCPUs, before and
after this patch. Wall time of 'veristat -q <obj>', mean of 10 runs, and
one run of test 5:
before after
pyperf180 1.222 s 0.087 s
pyperf600 3.538 s 0.222 s
test 5 > 900 s 1.5 s
Signed-off-by: Qiliang Yuan <odys.yuan@gmail.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
---
include/linux/bpf_verifier.h | 17 ++++++
kernel/bpf/core.c | 103 +++++++++++++++++++++++------------
2 files changed, 86 insertions(+), 34 deletions(-)
diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index f8498de5eff5..65313a26abb2 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -2081,10 +2081,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);
diff --git a/kernel/bpf/core.c b/kernel/bpf/core.c
index 2deb5584dc85..b9d9d0de5b92 100644
--- a/kernel/bpf/core.c
+++ b/kernel/bpf/core.c
@@ -1963,17 +1963,48 @@ void bpf_jit_prog_release_other(struct bpf_prog *fp, struct bpf_prog *fp_other)
bpf_prog_clone_free(fp_other);
}
+/*
+ * Apply the patches queued for 'prog' without a verifier env, which can't
+ * remove insns. Return the patched program, which may have moved.
+ */
+static 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;
+}
+
/*
* Now this function is used only to blind the main prog and must be invoked only when
* bpf_prog_need_blind() returns true.
*/
struct bpf_prog *bpf_jit_blind_constants(struct bpf_verifier_env *env, struct bpf_prog *prog)
{
- struct bpf_insn insn_buff[16], aux[2];
+ struct bpf_insn insn_buff[16], aux[2], *last;
+ struct bpf_patch_list pl = {};
struct bpf_prog *clone, *tmp;
- int insn_delta, insn_cnt;
struct bpf_insn *insn;
- int i, rewritten;
+ int i, insn_cnt, rewritten, err = 0;
if (WARN_ON_ONCE(env && env->prog != prog))
return ERR_PTR(-EINVAL);
@@ -1982,7 +2013,7 @@ struct bpf_prog *bpf_jit_blind_constants(struct bpf_verifier_env *env, struct bp
if (!clone)
return ERR_PTR(-ENOMEM);
- /* make sure bpf_patch_insn_data() patches the correct prog */
+ /* make sure the patches go to the clone */
if (env)
env->prog = clone;
@@ -2013,41 +2044,45 @@ struct bpf_prog *bpf_jit_blind_constants(struct bpf_verifier_env *env, struct bp
if (!rewritten)
continue;
- if (rewritten < 0)
- tmp = ERR_PTR(rewritten);
- else if (env)
- tmp = bpf_patch_insn_data(env, i, insn_buff, rewritten);
- else
- tmp = bpf_patch_insn_single(clone, i, insn_buff, rewritten);
-
- if (IS_ERR_OR_NULL(tmp)) {
- if (env)
- /* restore the original prog */
- env->prog = prog;
- /* 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);
- if (env && fatal_signal_pending(current))
- return ERR_PTR(-EINTR);
- return IS_ERR(tmp) ? tmp : ERR_PTR(-ENOMEM);
+ if (rewritten < 0) {
+ err = rewritten;
+ break;
}
+ last = env ? bpf_patch_list_add(env, i, insn_buff, rewritten) :
+ __bpf_patch_list_add(&pl, clone, i, insn_buff, rewritten);
+ if (IS_ERR(last)) {
+ err = PTR_ERR(last);
+ break;
+ }
+ }
- clone = tmp;
- insn_delta = rewritten - 1;
-
- if (env)
- env->prog = clone;
+ if (!err && env) {
+ err = bpf_patch_list_commit(env);
+ tmp = env->prog;
+ } else if (!err) {
+ tmp = bpf_patch_list_apply(clone, &pl);
+ err = PTR_ERR_OR_ZERO(tmp);
+ }
- /* Walk new program and skip insns we just inserted. */
- insn = clone->insnsi + i + insn_delta;
- insn_cnt += insn_delta;
- i += insn_delta;
+ if (err) {
+ if (env) {
+ bpf_patch_list_free(env);
+ /* restore the original prog */
+ env->prog = prog;
+ }
+ bpf_patch_list_release(&pl);
+ /*
+ * The clone is reallocated when nothing else can fail, so
+ * 'clone' is still valid.
+ */
+ bpf_jit_prog_release_other(prog, clone);
+ if (env && fatal_signal_pending(current))
+ return ERR_PTR(-EINTR);
+ return ERR_PTR(err);
}
- clone->blinded = 1;
- return clone;
+ tmp->blinded = 1;
+ return tmp;
}
bool bpf_insn_is_indirect_target(const struct bpf_verifier_env *env, const struct bpf_prog *prog,
--
2.55.0
^ permalink raw reply related [flat|nested] 18+ messages in thread* [PATCH bpf-next v3 11/13] bpf: Remove the old instruction patching code
2026-11-02 1:29 [PATCH bpf-next v3 00/13] bpf: Replace bpf_patch_insn_data() with a list of deferred patches Alexei Starovoitov
` (9 preceding siblings ...)
2026-11-02 1:29 ` [PATCH bpf-next v3 10/13] bpf: Blind constants through " Alexei Starovoitov
@ 2026-11-02 1:29 ` Alexei Starovoitov
2026-11-02 1:29 ` [PATCH bpf-next v3 12/13] selftests/bpf: Test jumps around patched instructions Alexei Starovoitov
` (3 subsequent siblings)
14 siblings, 0 replies; 18+ messages in thread
From: Alexei Starovoitov @ 2026-11-02 1:29 UTC (permalink / raw)
To: bpf; +Cc: daniel, andrii, eddyz87, memxor, odys.yuan
From: Qiliang Yuan <odys.yuan@gmail.com>
All passes queue their changes in the patch list. The functions that change
the prog immediately have no users. Remove bpf_patch_insn_data(),
bpf_patch_insn_single() and bpf_remove_insns(). Remove their helpers too,
which adjust the jumps and move the tables after each call.
bpf_patch_list_add() calls adjust_insn_aux_data() for a patch of 1 insn,
which it writes in place. Set zext_dst and non_stack_access in
bpf_patch_list_add() instead. Change the comments about the old code.
Signed-off-by: Qiliang Yuan <odys.yuan@gmail.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
---
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 | 197 +++--------------------------------
kernel/bpf/verifier.c | 45 --------
7 files changed, 15 insertions(+), 474 deletions(-)
diff --git a/include/linux/bpf.h b/include/linux/bpf.h
index b21a29a76b94..a80e81ca19ec 100644
--- a/include/linux/bpf.h
+++ b/include/linux/bpf.h
@@ -4378,8 +4378,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);
diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index 65313a26abb2..6a1fc8995940 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -1597,8 +1597,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);
diff --git a/include/linux/filter.h b/include/linux/filter.h
index 904ac8613098..8a8134752f30 100644
--- a/include/linux/filter.h
+++ b/include/linux/filter.h
@@ -1372,22 +1372,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();
diff --git a/kernel/bpf/bpf_insn_array.c b/kernel/bpf/bpf_insn_array.c
index 79c5441ddd00..0ef9c708d18d 100644
--- a/kernel/bpf/bpf_insn_array.c
+++ b/kernel/bpf/bpf_insn_array.c
@@ -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
@@ -275,23 +258,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.
diff --git a/kernel/bpf/core.c b/kernel/bpf/core.c
index b9d9d0de5b92..0586ed020397 100644
--- a/kernel/bpf/core.c
+++ b/kernel/bpf/core.c
@@ -337,199 +337,6 @@ int bpf_prog_calc_tag(struct bpf_prog *fp)
return 0;
}
-static int bpf_adj_delta_to_imm(struct bpf_insn *insn, u32 pos, s32 end_old,
- s32 end_new, s32 curr, const bool probe_pass)
-{
- const s64 imm_min = S32_MIN, imm_max = S32_MAX;
- s32 delta = end_new - end_old;
- s64 imm = insn->imm;
-
- if (curr < pos && curr + imm + 1 >= end_old)
- imm += delta;
- else if (curr >= end_new && curr + imm + 1 < end_new)
- imm -= delta;
- if (imm < imm_min || imm > imm_max)
- return -ERANGE;
- if (!probe_pass)
- insn->imm = imm;
- return 0;
-}
-
-static int bpf_adj_delta_to_off(struct bpf_insn *insn, u32 pos, s32 end_old,
- s32 end_new, s32 curr, const bool probe_pass)
-{
- s64 off_min, off_max, off;
- s32 delta = end_new - end_old;
-
- if (insn->code == (BPF_JMP32 | BPF_JA)) {
- off = insn->imm;
- off_min = S32_MIN;
- off_max = S32_MAX;
- } else {
- off = insn->off;
- off_min = S16_MIN;
- off_max = S16_MAX;
- }
-
- if (curr < pos && curr + off + 1 >= end_old)
- off += delta;
- else if (curr >= end_new && curr + off + 1 < end_new)
- off -= delta;
- if (off < off_min || off > off_max)
- return -ERANGE;
- if (!probe_pass) {
- if (insn->code == (BPF_JMP32 | BPF_JA))
- insn->imm = off;
- else
- insn->off = off;
- }
- return 0;
-}
-
-static int bpf_adj_branches(struct bpf_prog *prog, u32 pos, s32 end_old,
- s32 end_new, const bool probe_pass)
-{
- u32 i, insn_cnt = prog->len + (probe_pass ? end_new - end_old : 0);
- struct bpf_insn *insn = prog->insnsi;
- int ret = 0;
-
- for (i = 0; i < insn_cnt; i++, insn++) {
- u8 code;
-
- /* In the probing pass we still operate on the original,
- * unpatched image in order to check overflows before we
- * do any other adjustments. Therefore skip the patchlet.
- */
- if (probe_pass && i == pos) {
- i = end_new;
- insn = prog->insnsi + end_old;
- }
- if (bpf_pseudo_func(insn)) {
- ret = bpf_adj_delta_to_imm(insn, pos, end_old,
- end_new, i, probe_pass);
- if (ret)
- return ret;
- continue;
- }
- code = insn->code;
- if ((BPF_CLASS(code) != BPF_JMP &&
- BPF_CLASS(code) != BPF_JMP32) ||
- BPF_OP(code) == BPF_EXIT)
- continue;
- /* Adjust offset of jmps if we cross patch boundaries. */
- if (BPF_OP(code) == BPF_CALL) {
- if (insn->src_reg != BPF_PSEUDO_CALL)
- continue;
- ret = bpf_adj_delta_to_imm(insn, pos, end_old,
- end_new, i, probe_pass);
- } else {
- ret = bpf_adj_delta_to_off(insn, pos, end_old,
- end_new, i, probe_pass);
- }
- if (ret)
- break;
- }
-
- return ret;
-}
-
-static void bpf_adj_linfo(struct bpf_prog *prog, u32 off, u32 delta)
-{
- struct bpf_line_info *linfo;
- u32 i, nr_linfo;
-
- nr_linfo = prog->aux->nr_linfo;
- if (!nr_linfo || !delta)
- return;
-
- linfo = prog->aux->linfo;
-
- for (i = 0; i < nr_linfo; i++)
- if (off < linfo[i].insn_off)
- break;
-
- /* Push all off < linfo[i].insn_off by delta */
- for (; i < nr_linfo; i++)
- linfo[i].insn_off += delta;
-}
-
-struct bpf_prog *bpf_patch_insn_single(struct bpf_prog *prog, u32 off,
- const struct bpf_insn *patch, u32 len)
-{
- u32 insn_adj_cnt, insn_rest, insn_delta = len - 1;
- const u32 cnt_max = S16_MAX;
- struct bpf_prog *prog_adj;
- int err;
-
- /* Since our patchlet doesn't expand the image, we're done. */
- if (insn_delta == 0) {
- memcpy(prog->insnsi + off, patch, sizeof(*patch));
- return prog;
- }
-
- insn_adj_cnt = prog->len + insn_delta;
-
- /* Reject anything that would potentially let the insn->off
- * target overflow when we have excessive program expansions.
- * We need to probe here before we do any reallocation where
- * we afterwards may not fail anymore.
- */
- if (insn_adj_cnt > cnt_max &&
- (err = bpf_adj_branches(prog, off, off + 1, off + len, true)))
- return ERR_PTR(err);
-
- /* Several new instructions need to be inserted. Make room
- * for them. Likely, there's no need for a new allocation as
- * last page could have large enough tailroom.
- */
- prog_adj = bpf_prog_realloc(prog, bpf_prog_size(insn_adj_cnt),
- GFP_USER);
- if (!prog_adj)
- return ERR_PTR(-ENOMEM);
-
- prog_adj->len = insn_adj_cnt;
-
- /* Patching happens in 3 steps:
- *
- * 1) Move over tail of insnsi from next instruction onwards,
- * so we can patch the single target insn with one or more
- * new ones (patching is always from 1 to n insns, n > 0).
- * 2) Inject new instructions at the target location.
- * 3) Adjust branch offsets if necessary.
- */
- insn_rest = insn_adj_cnt - off - len;
-
- memmove(prog_adj->insnsi + off + len, prog_adj->insnsi + off + 1,
- sizeof(*patch) * insn_rest);
- memcpy(prog_adj->insnsi + off, patch, sizeof(*patch) * len);
-
- /* We are guaranteed to not fail at this point, otherwise
- * the ship has sailed to reverse to the original state. An
- * overflow cannot happen at this point.
- */
- BUG_ON(bpf_adj_branches(prog_adj, off, off + 1, off + len, false));
-
- bpf_adj_linfo(prog_adj, off, insn_delta);
-
- return prog_adj;
-}
-
-int bpf_remove_insns(struct bpf_prog *prog, u32 off, u32 cnt)
-{
- int err;
-
- /* Branch offsets can't overflow when program is shrinking, no need
- * to call bpf_adj_branches(..., true) here
- */
- memmove(prog->insnsi + off, prog->insnsi + off + cnt,
- sizeof(struct bpf_insn) * (prog->len - off - cnt));
- prog->len -= cnt;
-
- err = bpf_adj_branches(prog, off, off + cnt, off, false);
- WARN_ON_ONCE(err);
- return err;
-}
-
static int patch_list_reserve_patch(struct bpf_patch_list *pl)
{
struct bpf_insn_patch *p;
diff --git a/kernel/bpf/fixups.c b/kernel/bpf/fixups.c
index d0d099c34c80..ead78713e04f 100644
--- a/kernel/bpf/fixups.c
+++ b/kernel/bpf/fixups.c
@@ -165,132 +165,10 @@ static int get_callee_stack_depth(struct bpf_verifier_env *env,
}
#endif
-enum bpf_patch_mode {
- BPF_PATCH_KEEP_TARGET, /* targets of 'off' keep naming 'off', the first new insn */
- BPF_PATCH_MOVE_TARGET, /* targets of 'off' follow the original insn to 'off + len - 1' */
-};
-
-/* single env->prog->insni[off] instruction was replaced with the range
- * insni[off, off + cnt). Adjust corresponding insn_aux_data by copying
- * [0, off) and [off, end) to new locations, so the patched range stays zero
- */
-static void adjust_insn_aux_data(struct bpf_verifier_env *env,
- struct bpf_prog *new_prog, u32 off, u32 cnt,
- struct bpf_insn *original_insn,
- enum bpf_patch_mode mode)
-{
- struct bpf_insn_aux_data *data = env->insn_aux_data;
- struct bpf_insn *insn = new_prog->insnsi;
- u32 old_seen = data[off].seen;
- u32 prog_len;
- int i;
-
- /* aux info at OFF always needs adjustment, no matter fast path
- * (cnt == 1) is taken or not. There is no guarantee INSN at OFF is the
- * original insn at old prog.
- */
- data[off].zext_dst = bpf_insn_def32(new_prog, insn + off + cnt - 1) >= 0;
-
- if (cnt == 1) {
- /*
- * A non-memory accessing insn could have been replaced by a
- * memory accessing insn, systematically mark it for non-stack
- * access
- */
- data[off].non_stack_access = bpf_is_mem_insn(insn + off);
- return;
- }
- prog_len = new_prog->len;
- env->insn_aux_data_len = prog_len;
-
- memmove(data + off + cnt - 1, data + off,
- sizeof(struct bpf_insn_aux_data) * (prog_len - off - cnt + 1));
- memset(data + off, 0, sizeof(struct bpf_insn_aux_data) * (cnt - 1));
- for (i = off; i < off + cnt - 1; i++) {
- /* Expand insni[off]'s seen count to the patched range. */
- data[i].seen = old_seen;
- data[i].zext_dst = bpf_insn_def32(new_prog, insn + i) >= 0;
- /*
- * In BPF_PATCH_MOVE_TARGET mode the original insn is the last
- * slot by construction.
- */
- if (mode == BPF_PATCH_KEEP_TARGET &&
- !memcmp(insn + i, original_insn, sizeof(struct bpf_insn))) {
- data[i].non_stack_access =
- data[off + cnt - 1].non_stack_access;
- data[off + cnt - 1].non_stack_access = false;
- } else if (bpf_is_mem_insn(insn + i)) {
- data[i].non_stack_access = true;
- }
- }
-
- /*
- * Last slot instruction could be a newly generated
- * BPF_ST/BPF_LDX/BPF_STX, systematically mark it for non-stack access
- * if it is not the original instruction, otherwise keep the
- * original marking
- */
- if (bpf_is_mem_insn(insn + off + cnt - 1) &&
- memcmp(insn + off + cnt - 1, original_insn, sizeof(struct bpf_insn)))
- data[off + cnt - 1].non_stack_access = true;
-
- /*
- * The indirect_target flag of the original instruction was moved to the last of the
- * new instructions by the above memmove and memset, but the indirect jump target is
- * actually the first instruction, so move it back. This also matches with the behavior
- * of bpf_insn_array_adjust(), which preserves xlated_off to point to the first new
- * instruction. For BPF_PATCH_MOVE_TARGET the original instruction is the last one,
- * so the flag already sits where needed.
- */
- if (mode == BPF_PATCH_KEEP_TARGET && data[off + cnt - 1].indirect_target) {
- data[off].indirect_target = 1;
- data[off + cnt - 1].indirect_target = 0;
- }
-}
-
-static void adjust_subprog_starts(struct bpf_verifier_env *env, u32 off, u32 len)
-{
- int i;
-
- if (len == 1)
- return;
- /* NOTE: fake 'exit' subprog should be updated as well. */
- for (i = 0; i <= env->subprog_cnt; i++) {
- if (env->subprog_info[i].start <= off)
- continue;
- env->subprog_info[i].start += len - 1;
- }
-}
-
-static void adjust_insn_arrays(struct bpf_verifier_env *env, u32 first, u32 len)
-{
- int i;
-
- if (len == 1)
- return;
-
- for (i = 0; i < env->insn_array_map_cnt; i++)
- bpf_insn_array_adjust(env->insn_array_maps[i], first, len);
-}
-
-static void adjust_poke_descs(struct bpf_prog *prog, u32 first, u32 len)
-{
- struct bpf_jit_poke_descriptor *tab = prog->aux->poke_tab;
- int i, sz = prog->aux->size_poke_tab;
- struct bpf_jit_poke_descriptor *desc;
-
- for (i = 0; i < sz; i++) {
- desc = &tab[i];
- if (desc->insn_idx < first)
- continue;
- desc->insn_idx += len - 1;
- }
-}
-
/*
- * Some post-verification instruction rewriting passes require an
- * O(prog->len) operation per instruction. Keep their shared primitives
- * killable and preemptible.
+ * A post-verification rewriting pass can queue a patch for each instruction
+ * of a large program. Keep the primitives that queue them killable and
+ * preemptible.
*/
static bool bpf_rewrite_must_abort(void)
{
@@ -300,53 +178,6 @@ static bool bpf_rewrite_must_abort(void)
return false;
}
-static struct bpf_prog *__bpf_patch_insn_data(struct bpf_verifier_env *env, u32 off,
- const struct bpf_insn *patch, u32 len,
- enum bpf_patch_mode mode)
-{
- struct bpf_prog *new_prog;
- struct bpf_insn_aux_data *new_data = NULL;
- /* The first slot whose targets move. */
- u32 first = mode == BPF_PATCH_MOVE_TARGET ? off : off + 1;
- struct bpf_insn original_insn;
-
- if (bpf_rewrite_must_abort())
- return NULL;
-
- if (len > 1) {
- new_data = vrealloc(env->insn_aux_data,
- array_size(env->prog->len + len - 1,
- sizeof(struct bpf_insn_aux_data)),
- GFP_KERNEL_ACCOUNT | __GFP_ZERO);
- if (!new_data)
- return NULL;
-
- env->insn_aux_data = new_data;
- }
-
- memcpy(&original_insn, env->prog->insnsi + off, sizeof(struct bpf_insn));
- new_prog = bpf_patch_insn_single(env->prog, off, patch, len);
- if (IS_ERR(new_prog)) {
- if (PTR_ERR(new_prog) == -ERANGE)
- verbose(env,
- "insn %d cannot be patched due to 16-bit range\n",
- env->insn_aux_data[off].orig_idx);
- return NULL;
- }
- adjust_insn_aux_data(env, new_prog, off, len, &original_insn, mode);
- adjust_subprog_starts(env, off, len);
- adjust_insn_arrays(env, first, len);
- bpf_adjust_func_ptrs(env, off, len);
- adjust_poke_descs(new_prog, first, len);
- return new_prog;
-}
-
-struct bpf_prog *bpf_patch_insn_data(struct bpf_verifier_env *env, u32 off,
- const struct bpf_insn *patch, u32 len)
-{
- 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(). Replacing one insn by
@@ -368,10 +199,13 @@ struct bpf_insn *bpf_patch_list_add(struct bpf_verifier_env *env, u32 off,
return ERR_PTR(-EFAULT);
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);
- return &env->prog->insnsi[off];
+ struct bpf_insn *insn = &env->prog->insnsi[off];
+
+ *insn = *patch;
+ env->insn_aux_data[off].zext_dst = bpf_insn_def32(env->prog, insn) >= 0;
+ /* a new insn may access memory, systematically mark it non-stack */
+ env->insn_aux_data[off].non_stack_access = bpf_is_mem_insn(insn);
+ return insn;
}
/* -ERANGE takes a second patch with a 16-bit jump back out of it: no pass has one */
@@ -424,8 +258,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.
+ * of the insn they replace. The insns in front of p->target were inserted.
*/
static void patch_list_adj_aux(struct bpf_prog *prog, struct bpf_insn_patch *p,
struct bpf_insn *patch,
@@ -619,10 +452,10 @@ static void patch_list_remap_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, like with bpf_patch_insn_data(). If insns were
- * inserted in front of an insn, jumps, instruction arrays and poke descriptors
- * name the insn itself, while subprogs, line info, function pointers and calls
- * name the first inserted insn.
+ * the first insn of its patch. If insns were inserted in front of an insn,
+ * jumps, instruction arrays and poke descriptors name the insn itself, while
+ * subprogs, line info, function pointers and calls name the first inserted
+ * insn.
*
* An entry that names a removed insn:
* jump, call, poke descriptor names the next insn that stays
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 5bdf41a9bef0..935b163f81e4 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -6416,51 +6416,6 @@ struct bpf_func_ptr *bpf_map_func_ptrs(struct bpf_verifier_env *env,
return bpf_map_range_func_ptrs(env, map, 0, (u64)map->value_size, cnt);
}
-/* instructions [off, off + len) replaced the instruction at 'off' */
-void bpf_adjust_func_ptrs(struct bpf_verifier_env *env, u32 off, u32 len)
-{
- struct bpf_func_ptr *p;
- u32 i;
-
- if (len <= 1)
- return;
-
- for (i = 0; i < env->func_ptr_cnt; i++) {
- p = &env->func_ptrs[i];
- if (p->xlated_off <= off || p->xlated_off == BPF_FUNC_PTR_DELETED)
- continue;
- p->xlated_off += len - 1;
- }
-}
-
-/*
- * Instructions [off, off + len) are about to be removed. It's called before
- * the starts of subprogs are adjusted. A subprog is gone when all of its
- * instructions are. Otherwise, e.g. when its first instruction is a nop,
- * it starts where the removed instructions did.
- */
-void bpf_adjust_func_ptrs_after_remove(struct bpf_verifier_env *env, u32 off, u32 len)
-{
- struct bpf_func_ptr *p;
- int subprog;
- u32 i;
-
- for (i = 0; i < env->func_ptr_cnt; i++) {
- p = &env->func_ptrs[i];
- if (p->xlated_off < off || p->xlated_off == BPF_FUNC_PTR_DELETED)
- continue;
- if (p->xlated_off >= off + len) {
- p->xlated_off -= len;
- continue;
- }
- subprog = bpf_find_subprog(env, p->xlated_off);
- if (subprog > 0 && env->subprog_info[subprog + 1].start > off + len)
- p->xlated_off = off;
- else
- p->xlated_off = BPF_FUNC_PTR_DELETED;
- }
-}
-
#define BTF_TYPE_SAFE_RCU(__type) __PASTE(__type, __safe_rcu)
#define BTF_TYPE_SAFE_RCU_OR_NULL(__type) __PASTE(__type, __safe_rcu_or_null)
#define BTF_TYPE_SAFE_TRUSTED(__type) __PASTE(__type, __safe_trusted)
--
2.55.0
^ permalink raw reply related [flat|nested] 18+ messages in thread* [PATCH bpf-next v3 12/13] selftests/bpf: Test jumps around patched instructions
2026-11-02 1:29 [PATCH bpf-next v3 00/13] bpf: Replace bpf_patch_insn_data() with a list of deferred patches Alexei Starovoitov
` (10 preceding siblings ...)
2026-11-02 1:29 ` [PATCH bpf-next v3 11/13] bpf: Remove the old instruction patching code Alexei Starovoitov
@ 2026-11-02 1:29 ` Alexei Starovoitov
2026-11-02 1:29 ` [PATCH bpf-next v3 13/13] selftests/bpf: Test the tables that follow patched and removed instructions Alexei Starovoitov
` (2 subsequent siblings)
14 siblings, 0 replies; 18+ messages in thread
From: Alexei Starovoitov @ 2026-11-02 1:29 UTC (permalink / raw)
To: bpf; +Cc: daniel, andrii, eddyz87, memxor, odys.yuan
From: Qiliang Yuan <odys.yuan@gmail.com>
The verifier queues its patches in a patch list. One commit builds the new
image of the prog and gives each jump a new offset. Test the cases in which
this offset can be incorrect. In most tests the patched insn is 'r0 /= r1',
which gets a patch of 4 insns.
- A jump to a patched insn lands on the first insn of its patch: forward,
backward and with gotox.
- The target of gotox is a ctx load that becomes a load and a mask. A
patch in front of it changes its index, thus the entry of the insn array
must move. Each incorrect landing gives a different return value.
- A jump over patches gets a longer offset. One such jump is in the patch
of may_goto and leaves its patch.
- A jump over 8200 patches gets out of range, and the load fails.
- A backward may_goto goes over 8191 patches. The conditional jump in its
patch is out of range by 1. The verifier must select 'gotol' when it
queues the patch, but the offset is final only at the commit. The test
compares the final offset.
The tests have may_goto as a raw insn. Thus the assembler does not have to
know it. They run as a serial test, because other tests set
net.core.bpf_jit_harden, and the blinding of constants changes the xlated
insns.
Signed-off-by: Qiliang Yuan <odys.yuan@gmail.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
---
.../selftests/bpf/prog_tests/verifier.c | 3 +
.../selftests/bpf/progs/verifier_patch_list.c | 245 ++++++++++++++++++
2 files changed, 248 insertions(+)
create mode 100644 tools/testing/selftests/bpf/progs/verifier_patch_list.c
diff --git a/tools/testing/selftests/bpf/prog_tests/verifier.c b/tools/testing/selftests/bpf/prog_tests/verifier.c
index 386ad81051a9..99f0551c8b59 100644
--- a/tools/testing/selftests/bpf/prog_tests/verifier.c
+++ b/tools/testing/selftests/bpf/prog_tests/verifier.c
@@ -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,8 @@ 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); }
+/* Serial: the xlated code is another one while another test sets bpf_jit_harden */
+void serial_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); }
diff --git a/tools/testing/selftests/bpf/progs/verifier_patch_list.c b/tools/testing/selftests/bpf/progs/verifier_patch_list.c
new file mode 100644
index 000000000000..ffadd723f947
--- /dev/null
+++ b/tools/testing/selftests/bpf/progs/verifier_patch_list.c
@@ -0,0 +1,245 @@
+// SPDX-License-Identifier: GPL-2.0
+
+#include <linux/bpf.h>
+#include <bpf/bpf_helpers.h>
+#include "../../../include/linux/filter.h"
+#include "bpf_misc.h"
+
+/*
+ * bpf_do_misc_fixups() guards each division by a register against division
+ * by zero with a 4 insn patch. Jumps to a patched insn must land on the
+ * first insn of its patch, other jumps must follow the insns they target.
+ *
+ * JITs that need explicit zero extensions, like s390x and riscv64, get one
+ * more insn behind the 'w0 ^= w0' of that patch. The tests that compare such
+ * code don't run there.
+ */
+
+SEC("raw_tp")
+__description("patch list: forward jumps to and over patched insns")
+__arch_x86_64
+__arch_arm64
+__success
+__xlated("0: call")
+__xlated("1: r1 = r0")
+__xlated("2: r0 = 7")
+__xlated("3: if r1 > 0x5 goto pc+1")
+__xlated("4: r0 = 9")
+__xlated("5: if r1 != 0x0 goto pc+2")
+__xlated("6: w0 ^= w0")
+__xlated("7: goto pc+1")
+__xlated("8: r0 /= r1")
+__xlated("9: if r0 > 0x3 goto pc+4")
+__xlated("10: if r1 != 0x0 goto pc+2")
+__xlated("11: w0 ^= w0")
+__xlated("12: goto pc+1")
+__xlated("13: r0 /= r1")
+__xlated("14: exit")
+__naked void patch_list_forward(void)
+{
+ asm volatile (
+ "call %[bpf_get_prandom_u32];"
+ "r1 = r0;"
+ "r0 = 7;"
+ "if r1 > 5 goto l0_%=;"
+ "r0 = 9;"
+"l0_%=:"
+ "r0 /= r1;"
+ "if r0 > 3 goto l1_%=;"
+ "r0 /= r1;"
+"l1_%=:"
+ "exit;"
+ :
+ : __imm(bpf_get_prandom_u32)
+ : __clobber_all);
+}
+
+SEC("raw_tp")
+__description("patch list: backward jump to a patched insn")
+__arch_x86_64
+__arch_arm64
+__success
+__xlated("0: call")
+__xlated("1: r1 = r0")
+__xlated("2: r2 = 0")
+__xlated("3: if r1 != 0x0 goto pc+2")
+__xlated("4: w0 ^= w0")
+__xlated("5: goto pc+1")
+__xlated("6: r0 /= r1")
+__xlated("7: r2 += 1")
+__xlated("8: if r2 < 0x3 goto pc-6")
+__xlated("9: exit")
+__naked void patch_list_backward(void)
+{
+ asm volatile (
+ "call %[bpf_get_prandom_u32];"
+ "r1 = r0;"
+ "r2 = 0;"
+"l0_%=:"
+ "r0 /= r1;"
+ "r2 += 1;"
+ "if r2 < 3 goto l0_%=;"
+ "exit;"
+ :
+ : __imm(bpf_get_prandom_u32)
+ : __clobber_all);
+}
+
+/* The jump of may_goto leaves its own patch and crosses another one. */
+SEC("raw_tp")
+__description("patch list: may_goto between patched insns")
+__arch_x86_64
+__arch_arm64
+__success
+__xlated("0: *(u64 *)(r10 -16) = 65535")
+__xlated("1: *(u64 *)(r10 -8) = 0")
+__xlated("2: call")
+__xlated("3: r1 = r0")
+__xlated("4: if r1 != 0x0 goto pc+2")
+__xlated("5: w0 ^= w0")
+__xlated("6: goto pc+1")
+__xlated("7: r0 /= r1")
+__xlated("8: r12 = *(u64 *)(r10 -16)")
+__xlated("9: if r12 == 0x0 goto pc+9")
+__xlated("...")
+__xlated("15: if r1 != 0x0 goto pc+2")
+__xlated("16: w0 ^= w0")
+__xlated("17: goto pc+1")
+__xlated("18: r0 /= r1")
+__xlated("19: exit")
+__naked void patch_list_may_goto(void)
+{
+ asm volatile (
+ "call %[bpf_get_prandom_u32];"
+ "r1 = r0;"
+ "r0 /= r1;"
+ ".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))
+ : __clobber_all);
+}
+
+/*
+ * The conditional jump skips 8200 divisions, which their patches turn into
+ * 32800 insns, too far for its 16-bit offset.
+ */
+SEC("raw_tp")
+__description("patch list: jump pushed out of range by patches")
+__failure __msg("cannot be patched due to 16-bit range")
+__naked void patch_list_jump_out_of_range(void)
+{
+ asm volatile (" \
+ call %[bpf_get_prandom_u32]; \
+ r1 = r0; \
+ if r0 == 0 goto 0f; \
+ .rept 8200; \
+ r0 /= r1; \
+ .endr; \
+0: r0 = 0; \
+ exit; \
+" :
+ : __imm(bpf_get_prandom_u32)
+ : __clobber_all);
+}
+
+/* the JITs that support gotox, as in verifier_gotox.c */
+#if defined(__TARGET_ARCH_x86) || defined(__TARGET_ARCH_arm64) || \
+ defined(__TARGET_ARCH_powerpc) || \
+ (defined(__TARGET_ARCH_riscv) && __riscv_xlen == 64)
+/*
+ * An indirect jump to a patched insn must land on the first insn of its
+ * patch. The load of pkt_type, which is 0, becomes a load and a mask. Behind
+ * the load r0 still has bits of 255, and the result isn't 7.
+ *
+ * mark is 0, which the verifier doesn't know. So the division stays, never
+ * runs, and its patch moves the target by 3 insns. The old index of the target
+ * is the 'goto +1' of that patch, which goes to the exit with 255 in r0.
+ */
+SEC("socket")
+__description("patch list: indirect jump to a patched insn")
+__success __retval(7)
+__load_if_JITed()
+__naked void patch_list_indirect(void)
+{
+ asm volatile (" \
+ .pushsection .jumptables,\"\",@progbits; \
+jt0_%=: \
+ .quad l1_%= - socket; \
+ .quad l0_%= - socket; \
+ .size jt0_%=, 16; \
+ .global jt0_%=; \
+ .popsection; \
+ r2 = *(u32 *)(r1 + %[mark]); \
+ r2 &= 8; \
+ r3 = jt0_%= ll; \
+ r3 += r2; \
+ r3 = *(u64 *)(r3 + 0); \
+ r0 = 255; \
+ .8byte %[gotox_r3]; \
+l0_%=: \
+ r0 /= r2; \
+ exit; \
+l1_%=: \
+ r0 = *(u32 *)(r1 + %[pkt_type]); \
+ r0 += 7; \
+ exit; \
+" :
+ : __imm_const(mark, offsetof(struct __sk_buff, mark)),
+ __imm_const(pkt_type, offsetof(struct __sk_buff, pkt_type)),
+ __imm_insn(gotox_r3, BPF_RAW_INSN(BPF_JMP | BPF_JA | BPF_X, BPF_REG_3, 0, 0, 0))
+ : __clobber_all);
+}
+#else
+SEC("socket")
+__description("patch list: indirect jump to a patched insn")
+__skip("the JIT does not support gotox")
+__success
+int patch_list_indirect(void)
+{
+ return 0;
+}
+#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
+__arch_arm64
+__success
+__xlated("8: if r6 != 0x0 goto pc-3")
+__xlated("...")
+__xlated("32776: if r12 != 0x0 goto pc+1")
+__xlated("32777: gotol pc-32770")
+__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; \
+ .8byte %[may_goto]; \
+ r0 = 0; \
+ exit; \
+" :
+ : __imm(bpf_get_prandom_u32),
+ __imm_insn(may_goto, BPF_RAW_INSN(BPF_JMP | BPF_JCOND, 0, 0, -8195 /* offset */, 0))
+ : __clobber_all);
+}
+
+char _license[] SEC("license") = "GPL";
--
2.55.0
^ permalink raw reply related [flat|nested] 18+ messages in thread* [PATCH bpf-next v3 13/13] selftests/bpf: Test the tables that follow patched and removed instructions
2026-11-02 1:29 [PATCH bpf-next v3 00/13] bpf: Replace bpf_patch_insn_data() with a list of deferred patches Alexei Starovoitov
` (11 preceding siblings ...)
2026-11-02 1:29 ` [PATCH bpf-next v3 12/13] selftests/bpf: Test jumps around patched instructions Alexei Starovoitov
@ 2026-11-02 1:29 ` Alexei Starovoitov
2026-11-02 6:06 ` [PATCH bpf-next v3 00/13] bpf: Replace bpf_patch_insn_data() with a list of deferred patches Alexei Starovoitov
2026-11-02 6:40 ` patchwork-bot+netdevbpf
14 siblings, 0 replies; 18+ messages in thread
From: Alexei Starovoitov @ 2026-11-02 1:29 UTC (permalink / raw)
To: bpf; +Cc: daniel, andrii, eddyz87, memxor, odys.yuan
From: Alexei Starovoitov <ast@kernel.org>
bpf_patch_list_commit() builds the new image of a prog from queued patches,
removals and inserted insns. Then it moves each table that names insns, and
each table has its own rule. The tests of jumps do not show an error in
these rules. Add the tests that are missing.
table test
-------------------- --------------------------------------------------
aux data ctx access behind removed insns
jumps, calls call of and jump to an insn with insns inserted in
front
subprogs call over removed and patched insns
exception callback exceptions/exception_cb_behind_dead_subprog [*]
func info, line info patch_list/line_and_func_info
insn arrays bpf_insn_array/gotox-target-prologue-shift [*]
poke descriptors patch_list/poke_descriptor
function pointers callx_rodata_prog_shrinks_below_func
callx_rodata_table_of_ops
callx_rodata_func_with_may_goto
[*] existing test
The prog for line info and func info has marks. A mark is a line of source
code with one insn, 'r0 = n'. Each record must name the insn with its mark.
Removed code must have no record: its marks are gone, and insn_off grows
from record to record.
A function pointer in .rodata names the first insn of a subprog. In the
first two tests the verifier removes more insns than the subprog has. Thus
the old index of the subprog is behind the end of the new image. The tests
fail when the commit uses an old index with the new prog->len. In the third
test the subprog has may_goto, and the pointer must name the setup of the
may_goto count.
Also test two things that are not tables:
- bpf_opt_remove_nops() removes a 'goto' or a may_goto that jumps over
nops only: "may_goto over a nop", "goto over a nop" and
"goto over a nop and an insn". In the last test the 'goto' must stay.
- bpf_patch_list_apply() is the commit without the verifier.
patch_list/classic_filter attaches a classic BPF filter with
bpf_jit_harden=2. Its jumps go over insns with constants, and the test
compares what the filter returns.
patch_list/poke_descriptor runs on x86-64 only, because no other JIT uses
poke descriptors. patch_list is a serial test. With
net.core.bpf_jit_harden, which other tests set, a prog has other xlated
insns and no poke descriptors.
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
---
.../selftests/bpf/prog_tests/patch_list.c | 256 ++++++++++++++++++
.../testing/selftests/bpf/progs/patch_list.c | 136 ++++++++++
.../bpf/progs/verifier_callx_rodata.c | 100 +++++++
.../selftests/bpf/progs/verifier_patch_list.c | 181 +++++++++++++
4 files changed, 673 insertions(+)
create mode 100644 tools/testing/selftests/bpf/prog_tests/patch_list.c
create mode 100644 tools/testing/selftests/bpf/progs/patch_list.c
diff --git a/tools/testing/selftests/bpf/prog_tests/patch_list.c b/tools/testing/selftests/bpf/prog_tests/patch_list.c
new file mode 100644
index 000000000000..127ed58cfc39
--- /dev/null
+++ b/tools/testing/selftests/bpf/prog_tests/patch_list.c
@@ -0,0 +1,256 @@
+// SPDX-License-Identifier: GPL-2.0
+/* The tables that follow the insns which the verifier patches and removes */
+
+#include <test_progs.h>
+#include <bpf/btf.h>
+#include "sysctl_helpers.h"
+#include "patch_list.skel.h"
+
+/* load one program of the object */
+static struct patch_list *open_and_load(const char *name, int jmp_table_fd)
+{
+ struct bpf_program *prog;
+ struct patch_list *skel;
+
+ skel = patch_list__open();
+ if (!ASSERT_OK_PTR(skel, "open"))
+ return NULL;
+
+ bpf_object__for_each_program(prog, skel->obj)
+ bpf_program__set_autoload(prog, !strcmp(bpf_program__name(prog), name));
+ if (jmp_table_fd >= 0 &&
+ !ASSERT_OK(bpf_map__reuse_fd(skel->maps.jmp_table, jmp_table_fd), "reuse_fd"))
+ goto err;
+ if (!ASSERT_OK(patch_list__load(skel), "load"))
+ goto err;
+ return skel;
+err:
+ patch_list__destroy(skel);
+ return NULL;
+}
+
+#if defined(__x86_64__)
+static int run(struct bpf_program *prog)
+{
+ char data[64] = {};
+ LIBBPF_OPTS(bpf_test_run_opts, opts,
+ .data_in = data,
+ .data_size_in = sizeof(data),
+ .repeat = 1,
+ );
+
+ if (!ASSERT_OK(bpf_prog_test_run_opts(bpf_program__fd(prog), &opts), "test_run"))
+ return -1;
+ return opts.retval;
+}
+#endif
+
+/* Whether 'r0 = mark' is at 'off', or behind the insns inserted in front of a function. */
+static bool mark_is_at(const struct bpf_insn *insns, __u32 cnt, __u32 off, bool func_start,
+ int mark)
+{
+ while (func_start && off < cnt && insns[off].code == (BPF_ST | BPF_MEM | BPF_DW))
+ off++;
+ return off < cnt && insns[off].code == (BPF_ALU64 | BPF_MOV | BPF_K) &&
+ insns[off].dst_reg == BPF_REG_0 && insns[off].imm == mark;
+}
+
+static void test_line_and_func_info(void)
+{
+ /* what is left of the marks and functions of fn_1001(), in the order of the insns */
+ static const int marks[] = { 1001, 1004, 1005, 1006, 1007, 1008, 3001, 3002,
+ 4001, 4002, 4003 };
+ static const int funcs[] = { 1001, 3001, 4001 };
+ __u64 jited_linfo[64] = {}, ksyms[8] = {};
+ struct bpf_line_info linfo[64] = {};
+ struct bpf_func_info finfo[8] = {};
+ struct bpf_insn insns[128] = {};
+ struct bpf_prog_info info = {};
+ __u32 i, j, k, cnt, starts = 0, len = sizeof(info);
+ struct patch_list *skel;
+ struct btf *btf = NULL;
+ const char *str;
+ int mark;
+
+ skel = open_and_load("fn_1001", -1);
+ if (!skel)
+ return;
+
+ info.xlated_prog_insns = ptr_to_u64(insns);
+ info.xlated_prog_len = sizeof(insns);
+ info.line_info = ptr_to_u64(linfo);
+ info.nr_line_info = ARRAY_SIZE(linfo);
+ info.line_info_rec_size = sizeof(*linfo);
+ info.jited_line_info = ptr_to_u64(jited_linfo);
+ info.nr_jited_line_info = ARRAY_SIZE(jited_linfo);
+ info.jited_line_info_rec_size = sizeof(*jited_linfo);
+ info.func_info = ptr_to_u64(finfo);
+ info.nr_func_info = ARRAY_SIZE(finfo);
+ info.func_info_rec_size = sizeof(*finfo);
+ info.jited_ksyms = ptr_to_u64(ksyms);
+ info.nr_jited_ksyms = ARRAY_SIZE(ksyms);
+ if (!ASSERT_OK(bpf_prog_get_info_by_fd(bpf_program__fd(skel->progs.fn_1001), &info, &len),
+ "get_info"))
+ goto out;
+ cnt = info.xlated_prog_len / sizeof(*insns);
+ if (!ASSERT_LE(cnt, ARRAY_SIZE(insns), "xlated insns") ||
+ !ASSERT_LE(info.nr_line_info, ARRAY_SIZE(linfo), "nr_line_info"))
+ goto out;
+
+ btf = btf__load_from_kernel_by_id(info.btf_id);
+ if (!ASSERT_OK_PTR(btf, "btf"))
+ goto out;
+
+ if (!ASSERT_EQ(info.nr_func_info, ARRAY_SIZE(funcs), "nr_func_info"))
+ goto out;
+ for (i = 0; i < info.nr_func_info; i++) {
+ str = btf__name_by_offset(btf, btf__type_by_id(btf, finfo[i].type_id)->name_off);
+ mark = 0;
+ sscanf(str, "fn_%d", &mark);
+ ASSERT_EQ(mark, funcs[i], "func");
+ ASSERT_TRUE(mark_is_at(insns, cnt, finfo[i].insn_off, true, mark), str);
+ }
+
+ for (i = 0, k = 0; i < info.nr_line_info; i++) {
+ for (j = 0; j < info.nr_func_info; j++)
+ if (finfo[j].insn_off == linfo[i].insn_off)
+ break;
+ /* a function begins with a line, also in the JITed code */
+ if (j < info.nr_func_info)
+ starts++;
+ if (j < info.nr_func_info && info.nr_jited_line_info && info.nr_jited_ksyms)
+ ASSERT_EQ(jited_linfo[i], ksyms[j], "jited_line_info");
+ /* the line of a removed insn doesn't stay beside the line of the next insn */
+ if (i)
+ ASSERT_GT(linfo[i].insn_off, linfo[i - 1].insn_off, "insn_off");
+
+ str = strstr(btf__name_by_offset(btf, linfo[i].line_off), "MARK(");
+ if (!str)
+ continue;
+ mark = atoi(str + strlen("MARK("));
+ if (k < ARRAY_SIZE(marks))
+ ASSERT_EQ(mark, marks[k], "mark");
+ k++;
+ ASSERT_TRUE(mark_is_at(insns, cnt, linfo[i].insn_off, j < info.nr_func_info, mark),
+ str);
+ }
+ if (skel->rodata->has_line_text)
+ ASSERT_EQ(k, ARRAY_SIZE(marks), "marks");
+ ASSERT_EQ(starts, info.nr_func_info, "functions that begin with a line");
+out:
+ btf__free(btf);
+ patch_list__destroy(skel);
+}
+
+/*
+ * The x86-64 JIT finds the function of a tail call by the index in the poke
+ * descriptor, and connects it at once when the program array has the target.
+ * No other JIT uses the poke descriptors.
+ */
+static void test_poke_descriptor(void)
+{
+#if defined(__x86_64__)
+ struct patch_list *target, *entry = NULL;
+ int key = 0, fd;
+
+ if (!is_jit_enabled()) {
+ printf("%s:SKIP:JIT is disabled\n", __func__);
+ test__skip();
+ return;
+ }
+
+ target = open_and_load("poke_target", -1);
+ if (!target)
+ return;
+ fd = bpf_program__fd(target->progs.poke_target);
+ if (!ASSERT_OK(bpf_map__update_elem(target->maps.jmp_table, &key, sizeof(key),
+ &fd, sizeof(fd), 0), "map_update"))
+ goto out;
+
+ entry = open_and_load("poke_entry", bpf_map__fd(target->maps.jmp_table));
+ if (!entry)
+ goto out;
+ ASSERT_EQ(run(entry->progs.poke_entry), 7, "retval");
+out:
+ patch_list__destroy(entry);
+ patch_list__destroy(target);
+#else
+ printf("%s:SKIP:the JIT does not use poke descriptors\n", __func__);
+ test__skip();
+#endif
+}
+
+/*
+ * A classic filter has no verifier env, so bpf_patch_list_apply() puts the
+ * blinded constants in. Each insn with a constant grows, and the jumps of the
+ * filter go over such insns. The filter returns how much of the packet stays.
+ */
+static void test_classic_filter(void)
+{
+ const char *harden = "/proc/sys/net/core/bpf_jit_harden";
+ struct sock_filter code[] = {
+ /* A = first byte of the packet */
+ BPF_STMT(BPF_LD | BPF_B | BPF_ABS, 0),
+ BPF_JUMP(BPF_JMP | BPF_JGT | BPF_K, 40, 4, 0),
+ BPF_JUMP(BPF_JMP | BPF_JEQ | BPF_K, 7, 2, 0),
+ BPF_STMT(BPF_ALU | BPF_ADD | BPF_K, 10),
+ BPF_STMT(BPF_RET | BPF_A, 0),
+ /* A == 7 */
+ BPF_STMT(BPF_RET | BPF_K, 0),
+ /* A > 40 */
+ BPF_STMT(BPF_ALU | BPF_AND | BPF_K, 15),
+ BPF_JUMP(BPF_JMP | BPF_JSET | BPF_K, 1, 2, 0),
+ BPF_STMT(BPF_ALU | BPF_MUL | BPF_K, 3),
+ BPF_STMT(BPF_RET | BPF_A, 0),
+ /* A is odd */
+ BPF_STMT(BPF_RET | BPF_K, 33),
+ };
+ struct sock_fprog prog = { .len = ARRAY_SIZE(code), .filter = code };
+ static const struct {
+ char byte;
+ int len;
+ } tests[] = { { 1, 11 }, { 7, 0 }, { 40, 50 }, { 41, 33 }, { 44, 36 } };
+ char old[16] = {}, buf[64] = {};
+ int sv[2], i, err, len;
+
+ if (!is_jit_enabled()) {
+ printf("%s:SKIP:JIT is disabled\n", __func__);
+ test__skip();
+ return;
+ }
+
+ if (!ASSERT_OK(socketpair(AF_UNIX, SOCK_DGRAM, 0, sv), "socketpair"))
+ return;
+ if (sysctl_set_or_fail(harden, old, "2"))
+ goto out;
+ err = setsockopt(sv[1], SOL_SOCKET, SO_ATTACH_FILTER, &prog, sizeof(prog));
+ sysctl_set_or_fail(harden, NULL, old);
+ if (!ASSERT_OK(err, "SO_ATTACH_FILTER"))
+ goto out;
+
+ for (i = 0; i < ARRAY_SIZE(tests); i++) {
+ buf[0] = tests[i].byte;
+ if (!ASSERT_EQ(send(sv[0], buf, sizeof(buf), 0), sizeof(buf), "send"))
+ break;
+ /* nothing arrives when the filter returns 0 */
+ len = recv(sv[1], buf, sizeof(buf), MSG_DONTWAIT);
+ ASSERT_EQ(len < 0 ? 0 : len, tests[i].len, "len");
+ }
+out:
+ close(sv[0]);
+ close(sv[1]);
+}
+
+/*
+ * Serial: the xlated code is another one and there are no poke descriptors
+ * while another test sets bpf_jit_harden, and classic_filter sets it.
+ */
+void serial_test_patch_list(void)
+{
+ if (test__start_subtest("line_and_func_info"))
+ test_line_and_func_info();
+ if (test__start_subtest("poke_descriptor"))
+ test_poke_descriptor();
+ if (test__start_subtest("classic_filter"))
+ test_classic_filter();
+}
diff --git a/tools/testing/selftests/bpf/progs/patch_list.c b/tools/testing/selftests/bpf/progs/patch_list.c
new file mode 100644
index 000000000000..0e8302098395
--- /dev/null
+++ b/tools/testing/selftests/bpf/progs/patch_list.c
@@ -0,0 +1,136 @@
+// SPDX-License-Identifier: GPL-2.0
+/* Programs for the tables that follow the insns which the verifier patches and removes */
+
+#include <linux/bpf.h>
+#include <stdbool.h>
+#include <bpf/bpf_helpers.h>
+#include "../../../include/linux/filter.h"
+#include "bpf_misc.h"
+
+/*
+ * MARK(n) is a line of source code with one insn, 'r0 = n', and no other insn
+ * has n. The first mark of function fn_n is n. So user space can tell whether
+ * the line info and the func info of the loaded program name the right insns.
+ */
+#define MARK(n) asm volatile ("r0 = " #n ";")
+/* The line starts with a nop. When the nop goes away, 'r0 = n' gets the line. */
+#define NOP_MARK(n) asm volatile ("goto +0; r0 = " #n ";")
+
+/* gcc doesn't put the text of the lines into BTF */
+#ifdef __clang__
+const volatile bool has_line_text = true;
+#else
+const volatile bool has_line_text = false;
+#endif
+
+/* only dead code calls it */
+__naked __noinline __used
+static int fn_2001(void)
+{
+ MARK(2001);
+ asm volatile ("exit;");
+}
+
+__naked __noinline __used
+static int fn_3001(void)
+{
+ NOP_MARK(3001);
+ MARK(3002);
+ asm volatile ("exit;");
+}
+
+/* the setup of the may_goto count goes in front of it */
+__naked __noinline __used
+static int fn_4001(void)
+{
+ MARK(4001);
+ asm volatile (".8byte %[may_goto];"
+ :: __imm_insn(may_goto, BPF_RAW_INSN(BPF_JMP | BPF_JCOND, 0, 0, 1, 0)));
+ MARK(4002);
+ MARK(4003);
+ asm volatile ("exit;");
+}
+
+SEC("socket")
+__naked int fn_1001(void)
+{
+ MARK(1001);
+ asm volatile ("if r0 != 0 goto +3;");
+ MARK(1002);
+ asm volatile ("call fn_2001;");
+ MARK(1003);
+ MARK(1004);
+ /* the division gets three insns in front */
+ asm volatile ("r1 = 1; r0 /= r1;");
+ NOP_MARK(1005);
+ /* the next insn has a line, so the line of the nop goes away */
+ asm volatile ("goto +0;");
+ MARK(1006);
+ asm volatile ("call fn_3001;");
+ MARK(1007);
+ asm volatile ("call fn_4001;");
+ MARK(1008);
+ asm volatile ("exit;");
+}
+
+struct {
+ __uint(type, BPF_MAP_TYPE_PROG_ARRAY);
+ __uint(max_entries, 1);
+ __uint(key_size, sizeof(__u32));
+ __uint(value_size, sizeof(__u32));
+} jmp_table SEC(".maps");
+
+SEC("tc")
+int poke_target(struct __sk_buff *skb)
+{
+ return 7;
+}
+
+__naked __noinline __used
+static int poke_pad(void)
+{
+ asm volatile (
+ "r0 = 0;"
+ "exit;"
+ );
+}
+
+__naked __noinline __used
+static int poke_tail_call(void)
+{
+ asm volatile (
+ "r2 = %[jmp_table] ll;"
+ "r3 = 0;"
+ "call %[bpf_tail_call];"
+ "r0 = 1;"
+ "exit;"
+ :
+ : __imm_addr(jmp_table),
+ __imm(bpf_tail_call)
+ : __clobber_all);
+}
+
+/*
+ * The divisions grow by more insns than there are between the tail call and
+ * the start of its function: the index that the tail call had is in this
+ * function afterwards.
+ */
+SEC("tc")
+__naked int poke_entry(void)
+{
+ asm volatile (
+ "r6 = r1;"
+ "r1 = 1;"
+ "r0 = 8;"
+ "r0 /= r1;"
+ "r0 /= r1;"
+ "r0 /= r1;"
+ "r0 /= r1;"
+ "call poke_pad;"
+ "r1 = r6;"
+ "call poke_tail_call;"
+ "exit;"
+ ::: __clobber_all);
+}
+
+char _license[] SEC("license") = "GPL";
diff --git a/tools/testing/selftests/bpf/progs/verifier_callx_rodata.c b/tools/testing/selftests/bpf/progs/verifier_callx_rodata.c
index 6cf58ca9ac5b..b2ee0c8e042b 100644
--- a/tools/testing/selftests/bpf/progs/verifier_callx_rodata.c
+++ b/tools/testing/selftests/bpf/progs/verifier_callx_rodata.c
@@ -325,6 +325,106 @@ __naked void callx_rodata_func_starts_with_nop(void)
::: __clobber_all);
}
+/*
+ * The program loses more instructions than the function has, so the offset
+ * that the function had is behind the end of the program that is left.
+ */
+SEC("socket")
+__success __retval(11)
+__naked void callx_rodata_prog_shrinks_below_func(void)
+{
+ asm volatile (
+ RODATA(tbl, ".quad nop_add1; .quad 0;")
+ "goto +0;"
+ "goto +0;"
+ "goto +0;"
+ "goto +0;"
+ "goto +0;"
+ "goto +0;"
+ "goto +0;"
+ "goto +0;"
+ "r2 = tbl_%= ll;"
+ "r2 = *(u64 *)(r2 + 0);"
+ "r1 = 10;"
+ "callx r2;"
+ "exit;"
+ ::: __clobber_all);
+}
+
+int ops_arg = 10;
+
+/* the argument is never NULL, so the verifier removes the check and its branch */
+#define OP(name, n) \
+static __noinline int name(int *arg) \
+{ \
+ if (!arg) \
+ return bpf_get_prandom_u32(); \
+ return *arg + n; \
+}
+
+OP(op_a, 2) OP(op_b, 3) OP(op_c, 4) OP(op_d, 5) OP(op_e, 6) OP(op_f, 7) OP(op_g, 8) OP(op_h, 9)
+
+/* volatile, so that the compiler doesn't replace the table with direct calls */
+static int (* const volatile ops_table[])(int *) = {
+ op_a, op_b, op_c, op_d, op_e, op_f, op_g, op_h
+};
+
+/* the same in C: each function of the table loses its first instructions */
+SEC("socket")
+__success __retval(124)
+int callx_rodata_table_of_ops(void *ctx)
+{
+ int i, sum = 0;
+
+ for (i = 0; i < 8; i++)
+ sum += ops_table[i](&ops_arg);
+ return sum;
+}
+
+/* leave zeros where the function that is called next has its stack */
+__naked __noinline __used
+static unsigned long zero_stack(void)
+{
+ asm volatile (
+ "r0 = 0;"
+ "*(u64 *)(r10 - 8) = r0;"
+ "*(u64 *)(r10 - 16) = r0;"
+ "exit;"
+ );
+}
+
+/* count to r1, or to 0 when nothing set the count of may_goto */
+__naked __noinline __used
+static unsigned long may_goto_count(void)
+{
+ asm volatile (
+ "r0 = 0;"
+ "l0_%=:"
+ ".8byte %[may_goto];"
+ "r0 += 1;"
+ "if r0 < r1 goto l0_%=;"
+ "exit;"
+ :
+ : __imm_insn(may_goto, BPF_RAW_INSN(BPF_JMP | BPF_JCOND, 0, 0, 2 /* offset */, 0))
+ : __clobber_all);
+}
+
+/* the pointer names the instructions that the verifier puts in front of the function */
+SEC("socket")
+__success __retval(5)
+__naked void callx_rodata_func_with_may_goto(void)
+{
+ asm volatile (
+ RODATA(tbl, ".quad may_goto_count; .quad 0;")
+ "call zero_stack;"
+ "r2 = tbl_%= ll;"
+ "r2 = *(u64 *)(r2 + 0);"
+ "r1 = 5;"
+ "callx r2;"
+ "exit;"
+ ::: __clobber_all);
+}
+
/* can't be called with a scalar in r1 */
__naked __noinline __used
static unsigned long deref_r1(void)
diff --git a/tools/testing/selftests/bpf/progs/verifier_patch_list.c b/tools/testing/selftests/bpf/progs/verifier_patch_list.c
index ffadd723f947..3ba99cf16e96 100644
--- a/tools/testing/selftests/bpf/progs/verifier_patch_list.c
+++ b/tools/testing/selftests/bpf/progs/verifier_patch_list.c
@@ -242,4 +242,185 @@ __naked void patch_list_may_goto_gotol(void)
: __clobber_all);
}
+/*
+ * The aux data follows its insn: the verifier still knows which insn loads
+ * from the ctx when the dead code and the nops in front of it are gone.
+ */
+SEC("socket")
+__description("patch list: ctx access behind removed insns")
+__success __retval(50) /* TEST_DATA_LEN without the Ethernet header */
+__naked void patch_list_ctx_behind_removed(void)
+{
+ asm volatile (
+ "r0 = 0;"
+ "if r0 == 0 goto l0_%=;"
+ "r0 = 1;"
+ "r0 = 2;"
+"l0_%=:"
+ "goto +0;"
+ "r0 = *(u32 *)(r1 + %[len]);"
+ "exit;"
+ :
+ : __imm_const(len, offsetof(struct __sk_buff, len))
+ : __clobber_all);
+}
+
+__naked __noinline __used
+static unsigned long patch_list_loop_at_start(void)
+{
+ asm volatile (
+"l0_%=:"
+ "r1 += -1;"
+ ".8byte %[may_goto];"
+ "if r1 != 0 goto l0_%=;"
+ "r0 = r1;"
+ "exit;"
+ :
+ : __imm_insn(may_goto, BPF_RAW_INSN(BPF_JMP | BPF_JCOND, 0, 0, 1 /* offset */, 0))
+ : __clobber_all);
+}
+
+/*
+ * The setup of the may_goto count goes in front of the function. The call
+ * lands on the setup, the jump to the first insn of the function behind it.
+ * This is the code for the JITs that support the timed may_goto.
+ */
+SEC("raw_tp")
+__description("patch list: call of and jump to an insn with insns inserted in front")
+__arch_x86_64
+__arch_s390x
+__arch_arm64
+__arch_riscv64
+__arch_loongarch
+__success
+__xlated("0: r1 = 3")
+__xlated("1: call pc+1")
+__xlated("2: exit")
+__xlated("3: *(u64 *)(r10 -16) = 65535")
+__xlated("4: *(u64 *)(r10 -8) = 0")
+__xlated("5: r1 += -1")
+__xlated("...")
+__xlated("13: if r1 != 0x0 goto pc-9")
+__xlated("14: r0 = r1")
+__xlated("15: exit")
+__naked void patch_list_insert_in_front(void)
+{
+ asm volatile (
+ "r1 = 3;"
+ "call patch_list_loop_at_start;"
+ "exit;"
+ ::: __clobber_all);
+}
+
+__naked __noinline __used
+static unsigned long patch_list_never_called(void)
+{
+ asm volatile (
+ "r0 = 100;"
+ "exit;"
+ );
+}
+
+__naked __noinline __used
+static unsigned long patch_list_nop_add1(void)
+{
+ asm volatile (
+ "goto +0;"
+ "r0 = r1;"
+ "r0 += 1;"
+ "exit;"
+ );
+}
+
+/*
+ * A function goes away as dead code, the one behind it loses its first insn,
+ * and the caller both loses and gets insns in front of the call.
+ */
+SEC("socket")
+__description("patch list: call over removed and patched insns")
+__success __retval(11)
+__naked void patch_list_call_over_removed(void)
+{
+ asm volatile (
+ "r1 = 1;"
+ "if r1 == 1 goto l0_%=;"
+ "call patch_list_never_called;"
+"l0_%=:"
+ "goto +0;"
+ "r2 = 2;"
+ "r0 = 12;"
+ "r0 /= r2;"
+ "r6 = r0;"
+ "r1 = 4;"
+ "call patch_list_nop_add1;"
+ "r0 += r6;"
+ "exit;"
+ ::: __clobber_all);
+}
+
+/*
+ * A goto or a may_goto that jumps over nops only is a nop. The nops are not
+ * dead code: may_goto falls through to its nop, 'if' jumps to the other one.
+ */
+SEC("raw_tp")
+__description("patch list: may_goto over a nop")
+__success
+__xlated("0: r0 = 1")
+__xlated("1: exit")
+__naked void patch_list_may_goto_over_nop(void)
+{
+ asm volatile (
+ ".8byte %[may_goto];"
+ "goto +0;"
+ "r0 = 1;"
+ "exit;"
+ :
+ : __imm_insn(may_goto, BPF_RAW_INSN(BPF_JMP | BPF_JCOND, 0, 0, 1 /* offset */, 0))
+ : __clobber_all);
+}
+
+SEC("raw_tp")
+__description("patch list: goto over a nop")
+__success
+__xlated("0: r0 = *(u64 *)(r1 +0)")
+__xlated("1: if r0 == 0x0 goto pc+0")
+__xlated("2: r0 = 1")
+__xlated("3: exit")
+__naked void patch_list_goto_over_nop(void)
+{
+ asm volatile (
+ "r0 = *(u64 *)(r1 + 0);"
+ "if r0 == 0 goto l0_%=;"
+ "goto l1_%=;"
+"l0_%=:"
+ "goto +0;"
+"l1_%=:"
+ "r0 = 1;"
+ "exit;"
+ ::: __clobber_all);
+}
+
+/* this goto also jumps over an insn that stays */
+SEC("raw_tp")
+__description("patch list: goto over a nop and an insn")
+__success
+__xlated("0: r0 = *(u64 *)(r1 +0)")
+__xlated("1: if r0 == 0x0 goto pc+1")
+__xlated("2: goto pc+1")
+__xlated("3: r0 = 1")
+__xlated("4: exit")
+__naked void patch_list_goto_over_nop_and_insn(void)
+{
+ asm volatile (
+ "r0 = *(u64 *)(r1 + 0);"
+ "if r0 == 0 goto l0_%=;"
+ "goto l1_%=;"
+"l0_%=:"
+ "goto +0;"
+ "r0 = 1;"
+"l1_%=:"
+ "exit;"
+ ::: __clobber_all);
+}
+
char _license[] SEC("license") = "GPL";
--
2.55.0
^ permalink raw reply related [flat|nested] 18+ messages in thread* Re: [PATCH bpf-next v3 00/13] bpf: Replace bpf_patch_insn_data() with a list of deferred patches
2026-11-02 1:29 [PATCH bpf-next v3 00/13] bpf: Replace bpf_patch_insn_data() with a list of deferred patches Alexei Starovoitov
` (12 preceding siblings ...)
2026-11-02 1:29 ` [PATCH bpf-next v3 13/13] selftests/bpf: Test the tables that follow patched and removed instructions Alexei Starovoitov
@ 2026-11-02 6:06 ` Alexei Starovoitov
2026-11-02 6:30 ` Qiliang Yuan
2026-11-02 6:40 ` patchwork-bot+netdevbpf
14 siblings, 1 reply; 18+ messages in thread
From: Alexei Starovoitov @ 2026-11-02 6:06 UTC (permalink / raw)
To: bpf; +Cc: daniel, andrii, eddyz87, memxor, odys.yuan
Heh. CI is as green as it gets.
but here is what I expected bots to find out.. kinda disappointed in sashiko...
my local sash@#$ seems smarter... ;)
1. Patches 12, 13: the tests need net.core.bpf_jit_harden != 2 at the
start.
They are serial, so nobody changes the sysctl while they run.
But they do not set it. With 2 at the start:
- patch_list/line_and_func_info fails.
- patch_list/poke_descriptor passes, but the prog has no poke descriptor.
- 8 of the 12 verifier_patch_list tests fail, like every __xlated test
that has constants.
patch_list.c will set the sysctl to 0 and restore it, the way
classic_filter in the same file does.
2. Patch 12: "jump pushed out of range by patches" matches only the fixed
part of the message. The insn number is the part that the series
changes.
The test will match "insn 2 cannot be patched due to 16-bit range".
3. Patch 11 removes adjust_insn_aux_data() together with the comments that
explain the rules for zext_dst and non_stack_access.
patch_list_adj_aux() has the same rules without the explanation.
The comments will move there.
4. Patch 5: veristat has no option for BPF_F_TEST_RND_HI32. The numbers
are from veristat with an LD_PRELOAD shim that sets the flag in
BPF_PROG_LOAD. The log has to say so.
5. Patch 6: no test has a second patch with a jump in it. That is a barrier
in front of a ctx access that becomes several insns.
"nospec, store, nospec" in verifier_unpriv.c goes through the merge, but
it has no jump. The test needs a prog that is loaded without CAP_PERFMON.
Trade-offs. Not going to change.
6. Patches 4, 5: offloaded progs. verifier_remove_insns() checks for
a fatal signal in front of each call of the driver.
patch_list_drop_removed() does not, because it runs behind the last step
of the commit that can fail. Only nfp has the callback.
7. Patch 7: bpf_patch_list_insert() is correct when 'off' is the start of
a subprog and the list removes nothing. Both rules are comments, nothing
checks them. The three callers follow them.
8. Patch 13: without CONFIG_BPF_JIT_ALWAYS_ON classic_filter cannot tell
a blinded filter from a silent fallback to the interpreter. User space
cannot see the image of a classic filter.
9. Patches 12, 13: lists of archs.
- The tests that compare xlated insns run on x86-64 and arm64. A JIT that
needs zero extensions gets one more insn behind 'w0 ^= w0'.
loongarch can be added. I did not run it.
- poke_descriptor is x86-64 only. No other JIT reads poke descriptors.
It is one subtest of three, thus '#if' and not a DENYLIST.
In the tree today.
Pre-existing bugs... pick me. pick me.
10. Blinding is successful, then the JIT fails, and the kernel goes back to
the prog that is not blinded (CONFIG_BPF_JIT_ALWAYS_ON=n). Line info
stays at the offsets of the blinded image. bpf_adj_linfo() does the
same. The series removes one case: a failure in the middle of blinding
does not leave the table half moved. bpf_patch_image_install() is now
the only writer of the table, so the fix is small.
11. bpf_opt_remove_nops() does not look at aux->nospec. A jump that the
verifier hard wires can have it. The wider rule of patch 5 adds one more
shape: such a 'goto' over 'goto +0'. That matters only for CAP_BPF
without CAP_PERFMON. It is one line in insn_is_nop().
12. A prog of one function is blinded after the verifier log is finalized.
"insn N cannot be patched due to 16-bit range" is then not counted in
log_true_size.
^ permalink raw reply [flat|nested] 18+ messages in thread* Re: [PATCH bpf-next v3 00/13] bpf: Replace bpf_patch_insn_data() with a list of deferred patches
2026-11-02 6:06 ` [PATCH bpf-next v3 00/13] bpf: Replace bpf_patch_insn_data() with a list of deferred patches Alexei Starovoitov
@ 2026-11-02 6:30 ` Qiliang Yuan
2026-11-02 6:40 ` Alexei Starovoitov
0 siblings, 1 reply; 18+ messages in thread
From: Qiliang Yuan @ 2026-11-02 6:30 UTC (permalink / raw)
To: Alexei Starovoitov; +Cc: bpf, daniel, andrii, eddyz87, memxor
On Mon, Nov 02, 2026 at 06:06 AM Alexei Starovoitov wrote:
> Heh. CI is as green as it gets.
Thanks a lot for picking the series up and for the thorough review.
It has been a pleasure working on this with you.
> 1. Patches 12, 13: the tests need net.core.bpf_jit_harden != 2 at the
> start.
[...]
> 5. Patch 6: no test has a second patch with a jump in it.
By the way, I was almost done with my own v3 this morning when yours
arrived, so I held mine back to avoid two v3s on the list. To avoid
the same with v4: would you like me to send a v4 on top of your v3
that fixes 1-5, or will you send it yourself? Either works for me.
> In the tree today.
> Pre-existing bugs... pick me. pick me.
I'll take 10-12 and send the fixes as separate patches once the series
lands.
Thanks,
Qiliang
^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [PATCH bpf-next v3 00/13] bpf: Replace bpf_patch_insn_data() with a list of deferred patches
2026-11-02 6:30 ` Qiliang Yuan
@ 2026-11-02 6:40 ` Alexei Starovoitov
0 siblings, 0 replies; 18+ messages in thread
From: Alexei Starovoitov @ 2026-11-02 6:40 UTC (permalink / raw)
To: Qiliang Yuan; +Cc: bpf, daniel, andrii, eddyz87, memxor
On Mon Nov 2, 2026 at 6:30 AM UTC, Qiliang Yuan wrote:
>> 1. Patches 12, 13: the tests need net.core.bpf_jit_harden != 2 at the
>> start.
> [...]
>> 5. Patch 6: no test has a second patch with a jump in it.
>
> By the way, I was almost done with my own v3 this morning when yours
> arrived, so I held mine back to avoid two v3s on the list. To avoid
> the same with v4: would you like me to send a v4 on top of your v3
> that fixes 1-5, or will you send it yourself? Either works for me.
Yeah. Sorry for jumping on it. My own patches were blocked on it.
Applied the set. Pls follow up.
>> In the tree today.
>> Pre-existing bugs... pick me. pick me.
>
> I'll take 10-12 and send the fixes as separate patches once the series
> lands.
Pls go ahead.
We need to accelerate kernel development 10x.
If we don't, there will be no kernel left.
^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [PATCH bpf-next v3 00/13] bpf: Replace bpf_patch_insn_data() with a list of deferred patches
2026-11-02 1:29 [PATCH bpf-next v3 00/13] bpf: Replace bpf_patch_insn_data() with a list of deferred patches Alexei Starovoitov
` (13 preceding siblings ...)
2026-11-02 6:06 ` [PATCH bpf-next v3 00/13] bpf: Replace bpf_patch_insn_data() with a list of deferred patches Alexei Starovoitov
@ 2026-11-02 6:40 ` patchwork-bot+netdevbpf
14 siblings, 0 replies; 18+ messages in thread
From: patchwork-bot+netdevbpf @ 2026-11-02 6:40 UTC (permalink / raw)
To: Alexei Starovoitov; +Cc: bpf, daniel, andrii, eddyz87, memxor, odys.yuan
Hello:
This series was applied to bpf/bpf-next.git (master)
by Alexei Starovoitov <ast@kernel.org>:
On Mon, 2 Nov 2026 01:29:27 +0000 you wrote:
> From: Alexei Starovoitov <ast@kernel.org>
>
> After verification the verifier rewrites the prog in several passes. A pass
> calls bpf_patch_insn_data() for each insn that it replaces, and
> verifier_remove_insns() for each range that it removes. Each call moves all
> insns behind that place and walks all insns to adjust the jumps. It also
> walks each table that names insns: aux data, subprogs, line info and more.
> Thus a pass that changes M of the N insns of a prog does O(N * M) work.
> With bpf_jit_harden=2 pyperf600 from the selftests loads in 3.509 s, and in
> 0.223 s with this series.
>
> [...]
Here is the summary with links:
- [bpf-next,v3,01/13] bpf: Add a list of deferred instruction patches
https://git.kernel.org/bpf/bpf-next/c/be6f3ee5164b
- [bpf-next,v3,02/13] bpf: Remap the verifier state through the patch list
https://git.kernel.org/bpf/bpf-next/c/715942f477ac
- [bpf-next,v3,03/13] bpf: Queue the rewrites of bpf_do_misc_fixups()
https://git.kernel.org/bpf/bpf-next/c/a7a767c66a2e
- [bpf-next,v3,04/13] bpf: Let the patch list remove instructions
https://git.kernel.org/bpf/bpf-next/c/7308888ec195
- [bpf-next,v3,05/13] bpf: Move the bpf_opt_*() passes to the patch list
https://git.kernel.org/bpf/bpf-next/c/a6e3b3378fe3
- [bpf-next,v3,06/13] bpf: Allow patching an instruction twice through the patch list
https://git.kernel.org/bpf/bpf-next/c/004711c7bbb4
- [bpf-next,v3,07/13] bpf: Teach the patch list to insert in front of an instruction
https://git.kernel.org/bpf/bpf-next/c/dd235939c6f4
- [bpf-next,v3,08/13] bpf: Move bpf_convert_ctx_accesses() to the patch list
https://git.kernel.org/bpf/bpf-next/c/99d24b3938fa
- [bpf-next,v3,09/13] bpf: Move the remaining verifier rewrites to the patch list
https://git.kernel.org/bpf/bpf-next/c/0a630ce57cad
- [bpf-next,v3,10/13] bpf: Blind constants through the patch list
https://git.kernel.org/bpf/bpf-next/c/d50ffab62001
- [bpf-next,v3,11/13] bpf: Remove the old instruction patching code
https://git.kernel.org/bpf/bpf-next/c/056587f974f1
- [bpf-next,v3,12/13] selftests/bpf: Test jumps around patched instructions
https://git.kernel.org/bpf/bpf-next/c/67d4d0b73c29
- [bpf-next,v3,13/13] selftests/bpf: Test the tables that follow patched and removed instructions
https://git.kernel.org/bpf/bpf-next/c/d86e6695cb2f
You are awesome, thank you!
--
Deet-doot-dot, I am a bot.
https://korg.docs.kernel.org/patchwork/pwbot.html
^ permalink raw reply [flat|nested] 18+ messages in thread