bpf: Replace bpf_patch_insn_data() with a list of deferred patches
Subsystems (4)
v3 cover bpf: Replace bpf_patch_insn_data() with a list of deferred patches
From: Alexei Starovoitov <[email protected]>
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.
The idea
========
A pass queues its changes in a patch list, in the order of the insns. It commits them one time, at its end. No insn moves before the commit, thus the pass uses old indexes only. The commit calculates two maps from old index to new index. Then it builds the new image, and all that names an insn goes through one of the maps. The commit costs O(N + inserted insns).
old image patch list new_off[] new_tgt[] new image
0: a 0 0 0: a
1: b patch, 3 insns 1 1 1: b1
2: b2
3: b3
2: c 4 4 4: c
3: d removal 5 5
4: e 5 5 5: e
5: f insert 1 insn 6 7 6: i1
7: fmap what goes through it new_off[] calls, subprogs, function pointers, line info new_tgt[] jumps, insn arrays, poke descriptors
The maps differ only where insns are inserted in front of an insn. For example, the setup of the may_goto count goes in front of a subprog. A call of the subprog runs the setup, and a jump to its first insn does not.
The interface
=============
bpf_patch_list_add() queue a patch: new insns replace insn i bpf_patch_list_insert() queue new insns that go in front of insn i bpf_patch_list_del() queue the removal of insn i bpf_patch_list_commit() build the new image, move all tables, install it bpf_patch_list_apply() static in core.c: the commit for classic BPF
During a commit one part of bpf_verifier_env (env) describes the old image, and a different part describes the new image. Thus the order of the steps is a rule:
1. all that can fail Build the maps and the new image, allocate the new
aux data and the prog. An error changes nothing.
2. removed insns Tell the offload device, free what their aux data
points to. All of env describes the old image.
3. the tables A new entry depends only on the old entry and on
the maps. Function pointers also need the old subprogs, thus they move before the subprogs. No helper that reads the insns, prog->len or a table from env or the prog.
4. the new image Write the insns and prog->len last.
The patches
===========
pass patch what it needs (patch) ------------------------------------ ----- ---------------------------- bpf_do_misc_fixups(), main loop 3 list (1), commit (2) bpf_opt_remove_dead_code() 5 removal (4) bpf_opt_remove_nops() 5 removal (4) bpf_opt_subreg_zext_lo32_rnd_hi32() 5 bpf_convert_ctx_accesses() 8 second patch (6), insert (7) bpf_do_misc_fixups(), may_goto count 9 insert (7) add_hidden_subprog() 9 bpf_optimize_bpf_loop() 9 bpf_jit_blind_constants() 10 commit without env (10)
Read patches 1, 2, 4 and 7 first: they are the design. Patch 11 removes the old code. Patches 12-13 are selftests.
The results
===========
Load times in an x86_64 VM with 8 vCPUs, bpf-next without and with the series. Wall time of 'veristat -q <obj>', mean of 30 runs, and of 10 runs with BPF_F_TEST_RND_HI32 or bpf_jit_harden=2. BPF_PROG_LOAD of a prog with 131072 'goto +0', mean of 3 runs.
base patched
pyperf180 0.148 s 0.085 s pyperf600 0.430 s 0.220 s strobemeta 0.149 s 0.148 s test_verif_scale2 0.121 s 0.122 s pyperf180, BPF_F_TEST_RND_HI32 0.610 s 0.091 s pyperf600, BPF_F_TEST_RND_HI32 1.830 s 0.223 s pyperf180, bpf_jit_harden=2 1.216 s 0.085 s pyperf600, bpf_jit_harden=2 3.509 s 0.223 s 131072 'goto +0' 33.288 s 0.245 s
With bpf_jit_harden=2 the prog of
"ld_dw: xor semi-random 64 bit imms, test 5" of test_verifier does not load in 900 s on the base. With the series the test takes 1.5 s.
What users can see, apart from the load time:
- Patches 3, 5, 8, 9 and 10: a jump that patches push out of range fails the load with -ERANGE, not -ENOMEM. The verifier log names the jump, not the patched insn. For patch 10 that is true for a prog with subprogs. A prog of one function gets -ENOTSUPP or goes to the interpreter, as before.
- Patch 3: a backward may_goto that patches push beyond -32768 loads.
- Patch 5: bpf_opt_remove_nops() also removes a 'goto' or a may_goto that jumps over 'goto +0' only.
- Patches 8 and 9: a jump back to an insn keeps its offset when insns are inserted in front of that insn. On the base an offset near -32768 fails the load.
The series does not change the code of progs in other ways. In selftests, scx and Cilium only these nops differ in xlated insns, line info and func info. That is also true with BPF_F_TEST_RND_HI32 and with bpf_jit_harden=2.
Eduard pointed out the cost in pyperf180 [1]. The split between core.c and the verifier follows Jiong's RFC [2]. Andrii suggested the map there.
I picked up Qiliang's series to speed things up: patches 1-12 are his, with my changes as listed below.
v2 -> v3:
- Rebase: patches 4 and 6 of v2 touched the arena_scalar rewrite, which is gone
- Squash neighbours: the 22 patches of v2 are patches 1-12, patch 13 is new
- Fix a NULL function pointer in .rodata: the commit looked up a function by its old offset after prog->len was the new length (patch 4)
- Give the commit the order above: one function per table, the image last, the line info map built with the image (patches 1, 2, 4)
- Give all instructions of a patch the orig_idx of the patched one: the range message said "insn 0" for the jump of may_goto (patch 2)
- Patches 4 and 5 of v2 are one patch (3): in between a backward may_goto at -32768 didn't load
- Walk from the end in bpf_opt_remove_nops(): the look-back was quadratic and couldn't be killed (patch 5)
- Commit the prologue before bpf_convert_ctx_accesses() rewrites instructions in place: a rewrite of the first one was lost (patch 8)
- Make bpf_patch_list_apply() static (patch 10)
- Comments of may_goto_expand(), bpf_patch_list_commit() and the error path of bpf_jit_blind_constants() (CI bot)
- Write may_goto as a raw instruction in the tests, so that the assembler doesn't have to know it (Sashiko on 22/22)
- Tests of v2 (patch 12): check the final offset of the gotol, let gotox return another value for each wrong landing, run the may_goto tests on arm64 too, run serially because of bpf_jit_harden
- Test callx after the program shrinks (patch 13)
- Test the tables of the commit that had no test, the new nop rule and the blinding of a classic filter (patch 13)
- Rewrite the commit logs and the cover letter, say what users can see
v1 -> v2:
- Convert every pass and remove the old patching code (Alexei)
- Build the new image in core.c, so that blinding without a verifier env uses the list too
- Let the list remove instructions, insert in front of one and patch one twice
- Pick JEQ or gotol for a backward may_goto from its offset grown by the patches in between, v1 picked JEQ when that offset was -32768 (CI bot)
- Test a backward may_goto expanded to gotol
- Test a jump that the patches push out of its 16-bit range, and a gotox to a patched insn
v2: https://lore.kernel.org/r/[email protected]
v1: https://lore.kernel.org/r/[email protected]
[1] https://lore.kernel.org/bpf/[email protected]/
[2] https://lore.kernel.org/bpf/[email protected]/
Alexei Starovoitov (1):
selftests/bpf: Test the tables that follow patched and removed
instructions
Qiliang Yuan (12):
bpf: Add a list of deferred instruction patches
bpf: Remap the verifier state through the patch list
bpf: Queue the rewrites of bpf_do_misc_fixups()
bpf: Let the patch list remove instructions
bpf: Move the bpf_opt_*() passes to the patch list
bpf: Allow patching an instruction twice through the patch list
bpf: Teach the patch list to insert in front of an instruction
bpf: Move bpf_convert_ctx_accesses() to the patch list
bpf: Move the remaining verifier rewrites to the patch list
bpf: Blind constants through the patch list
bpf: Remove the old instruction patching code selftests/bpf: Test jumps around patched instructions
include/linux/bpf.h | 4 +- include/linux/bpf_verifier.h | 88 +- include/linux/filter.h | 16 - kernel/bpf/bpf_insn_array.c | 36 +- kernel/bpf/core.c | 605 +++++--- kernel/bpf/fixups.c | 1306 ++++++++--------- kernel/bpf/verifier.c | 46 +- .../selftests/bpf/prog_tests/patch_list.c | 256 ++++ .../selftests/bpf/prog_tests/verifier.c | 3 + .../testing/selftests/bpf/progs/patch_list.c | 136 ++ .../bpf/progs/verifier_callx_rodata.c | 100 ++ .../selftests/bpf/progs/verifier_patch_list.c | 426 ++++++ 12 files changed, 2040 insertions(+), 982 deletions(-) create mode 100644 tools/testing/selftests/bpf/prog_tests/patch_list.c create mode 100644 tools/testing/selftests/bpf/progs/patch_list.c create mode 100644 tools/testing/selftests/bpf/progs/verifier_patch_list.c
base-commit: a30c772627b2ef4bc715332b1b04938a914556cd
Signature · 1 line
2.55.0
PATCH v3 1/13 bpf: Add a list of deferred instruction patches
From: Qiliang Yuan <[email protected]>
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 -96: 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.
--- include/linux/bpf_verifier.h | 47 ++++++++ kernel/bpf/core.c | 220 +++++++++++++++++++++++++++++++++++ 2 files changed, 267 insertions(+)
include/linux/bpf_verifier.h +47 -0
@@ -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 */
kernel/bpf/core.c +220 -0
226 lines not on this page · raw message
Signature · 1 line
2.55.0
PATCH v3 2/13 bpf: Remap the verifier state through the patch list
In reply to Alexei StarovoitovFrom: Qiliang Yuan <[email protected]>
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.
--- 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(+)
include/linux/bpf.h +1 -0
@@ -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);
include/linux/bpf_verifier.h +5 -0
@@ -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);
kernel/bpf/bpf_insn_array.c +17 -0
@@ -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);
kernel/bpf/fixups.c +187 -0
193 lines not on this page · raw message
kernel/bpf/verifier.c +1 -0
@@ -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);
Signature · 1 line
2.55.0
PATCH v3 3/13 bpf: Queue the rewrites of bpf_do_misc_fixups()
In reply to Alexei StarovoitovFrom: Qiliang Yuan <[email protected]>
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
--- kernel/bpf/fixups.c | 294 ++++++++++++++++++-------------------------- 1 file changed, 118 insertions(+), 176 deletions(-)
kernel/bpf/fixups.c +118 -176
@@ -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 ;
Signature · 1 line
2.55.0
PATCH v3 4/13 bpf: Let the patch list remove instructions
In reply to Alexei StarovoitovFrom: Qiliang Yuan <[email protected]>
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
--- 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(-)
include/linux/bpf_verifier.h +11 -0
@@ -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);
kernel/bpf/bpf_insn_array.c +7 -3
@@ -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; } }
kernel/bpf/core.c +74 -7
124 lines not on this page · raw message
kernel/bpf/fixups.c +153 -17
219 lines not on this page · raw message
Signature · 1 line
2.55.0
PATCH v3 5/13 bpf: Move the bpf_opt_*() passes to the patch list
In reply to Alexei StarovoitovFrom: Qiliang Yuan <[email protected]>
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
--- kernel/bpf/fixups.c | 266 +++++++++----------------------------------- 1 file changed, 52 insertions(+), 214 deletions(-)
kernel/bpf/fixups.c +52 -214
@@ -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); }/*
Signature · 1 line
2.55.0
PATCH v3 6/13 bpf: Allow patching an instruction twice through the patch list
In reply to Alexei StarovoitovFrom: Qiliang Yuan <[email protected]>
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.
--- kernel/bpf/core.c | 64 +++++++++++++++++++++++++++++++++++++++++++-- kernel/bpf/fixups.c | 9 ++++--- 2 files changed, 68 insertions(+), 5 deletions(-)
kernel/bpf/core.c +62 -2
@@ -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);
kernel/bpf/fixups.c +6 -3
@@ -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); }
Signature · 1 line
2.55.0
PATCH v3 7/13 bpf: Teach the patch list to insert in front of an instruction
In reply to Alexei StarovoitovFrom: Qiliang Yuan <[email protected]>
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 += -13: 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.
--- 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(-)
include/linux/bpf.h +2 -1
@@ -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);
include/linux/bpf_verifier.h +6 -0
@@ -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);
kernel/bpf/bpf_insn_array.c +6 -5
@@ -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, s32if (off < cnt && new_off[off] == new_off[off +1 ]) insn_array->values[i].xlated_off =INSN_DELETED ;else - insn_array->values[i].xlated_off = off <= cnt ? new_off[off] : off + grow; + insn_array->values[i].xlated_off = off <= cnt ? new_tgt[off] : off + grow; } }
kernel/bpf/core.c +64 -10
145 lines not on this page · raw message
kernel/bpf/fixups.c +33 -6
@@ -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:
Signature · 1 line
2.55.0
PATCH v3 8/13 bpf: Move bpf_convert_ctx_accesses() to the patch list
In reply to Alexei StarovoitovFrom: Qiliang Yuan <[email protected]>
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.
--- kernel/bpf/fixups.c | 131 +++++++++++++++++++------------------------- 1 file changed, 55 insertions(+), 76 deletions(-)
kernel/bpf/fixups.c +55 -76
@@ -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)
Signature · 1 line
2.55.0
PATCH v3 9/13 bpf: Move the remaining verifier rewrites to the patch list
In reply to Alexei StarovoitovFrom: Qiliang Yuan <[email protected]>
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.
--- kernel/bpf/fixups.c | 155 +++++++++++++------------------------------- 1 file changed, 46 insertions(+), 109 deletions(-)
kernel/bpf/fixups.c +46 -109
@@ -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 *patverifier_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,
Signature · 1 line
2.55.0
PATCH v3 10/13 bpf: Blind constants through the patch list
In reply to Alexei StarovoitovFrom: Qiliang Yuan <[email protected]>
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
--- include/linux/bpf_verifier.h | 17 ++++++ kernel/bpf/core.c | 103 +++++++++++++++++++++++------------ 2 files changed, 86 insertions(+), 34 deletions(-)
include/linux/bpf_verifier.h +17 -0
@@ -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);
kernel/bpf/core.c +69 -34
134 lines not on this page · raw message
Signature · 1 line
2.55.0
PATCH v3 11/13 bpf: Remove the old instruction patching code
In reply to Alexei StarovoitovFrom: Qiliang Yuan <[email protected]>
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.
--- 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(-)
include/linux/bpf.h +0 -2
@@ -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);
include/linux/bpf_verifier.h +0 -2
@@ -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);
include/linux/filter.h +0 -16
@@ -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 ();
kernel/bpf/bpf_insn_array.c +0 -34
@@ -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.
kernel/bpf/core.c +0 -193
199 lines not on this page · raw message
kernel/bpf/fixups.c +15 -182
228 lines not on this page · raw message
kernel/bpf/verifier.c +0 -45
51 lines not on this page · raw message
Signature · 1 line
2.55.0
PATCH v3 12/13 selftests/bpf: Test jumps around patched instructions
In reply to Alexei StarovoitovFrom: Qiliang Yuan <[email protected]>
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.
--- .../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
tools/testing/selftests/bpf/prog_tests/verifier.c +3 -0
@@ -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); }
tools/testing/selftests/bpf/progs/verifier_patch_list.c new file +245 -0
245 lines not on this page · raw message
Signature · 1 line
2.55.0
PATCH v3 13/13 selftests/bpf: Test the tables that follow patched and removed instructions
In reply to Alexei StarovoitovFrom: Alexei Starovoitov <[email protected]>
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.
--- .../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
tools/testing/selftests/bpf/prog_tests/patch_list.c new file +256 -0
@@ -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 (); +}
tools/testing/selftests/bpf/progs/patch_list.c new file +136 -0
136 lines not on this page · raw message
tools/testing/selftests/bpf/progs/verifier_callx_rodata.c +100 -0
106 lines not on this page · raw message
tools/testing/selftests/bpf/progs/verifier_patch_list.c +181 -0
185 lines not on this page · raw message
Signature · 1 line
2.55.0
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.
Quoted 1 line · Alexei Starovoitov
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.
Quoted 2 lines
1. Patches 12, 13: the tests need net.core.bpf_jit_harden != 2 at the start.
[...]
Quoted 1 line
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.
Quoted 2 lines
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
Quoted 9 lines · Qiliang Yuan
Quoted 2 lines
1. Patches 12, 13: the tests need net.core.bpf_jit_harden != 2 at the start.
[...]
Quoted 1 line
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.
Quoted 5 lines
Quoted 2 lines
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.
This series was applied to bpf/bpf-next.git (master) by Alexei Starovoitov <[email protected]>:
Hello:
This series was applied to bpf/bpf-next.git (master) by Alexei Starovoitov <[email protected]>:
Quoted 11 lines · On Mon, 2 Nov 2026 01:29:27 +0000 you wrote:
From: Alexei Starovoitov <[email protected]>
After verification the verifier rewrites the prog in several passes. A pass calls
bpf_patch_insn_data()for each insn that it replaces, andverifier_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 doesO(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.
Quoted 1 line
[...]
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!
Signature · 2 lines
Deet-doot-dot, I am a bot. https://korg.docs.kernel.org/patchwork/pwbot.html