From mboxrd@z Thu Jan 1 00:00:00 1970 Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.remote-ip=74.125.82.45 ARC-Seal: i=1; d=subspace.kernel.org; s=arc20261015; a=rsa-sha256; cv=none; t=1793361161; b=zy7nPCjH6XuaWZIZGVS2vDwq7/TAnSRUkY23Y5TDlkEGpZBnJ0Xa9xxJ5K0FwJjHt4dM vnzzOPgTiYgnDlu/DRt96Pc2JgUw3FdIqol1/M+s4FkCEsyPbg37Le15m5s0XVGOm09bw rQSUsTL2XdfW5Wp88wiB9/y4AvQUnfE5bcZxhhfPZqibTRyAjytQmE7bura9PottGvCqW wuqOfWebcpF3iE1xgyvHcQDwsgMZmoVpfMXeWqZW+IabTM+rSM34J6VkNDFEBdzttyuCQ 786OJHKZRQkEKek9eKC2i2KpPL0vbM0e/FVyPmm9QP85fB/aEfVeV+dfLHdavylYNrA== ARC-Message-Signature: i=1; d=subspace.kernel.org; s=arc20261015; a=rsa-sha256; c=relaxed/relaxed; t=1793361161; h=DMARC-Filter:Received:DKIM-Signature:X-Google-DKIM-Signature: X-Forwarded-Encrypted:X-Gm-Message-State:X-Gm-Gg:X-Received:Received: From:Date:Subject:MIME-Version:Content-Type:Content-Transfer-Encoding: Message-Id:References:In-Reply-To:To:Cc:X-Mailer; bh=Iaj1sSwxGW2T2ZYTzsyLzlK1pKpVJ1ZuRU1k4FtQ+9k=; b=Hp55U/KaRl7uvwsvz394ujg6Dam7gSTIEnzUYGJ/eRj6BkrmbMRuoUH7ZhjEb/7R7ekS kk9b4r5pW55ZexFhtY0UcJmIdEyynctgKGeb7zISl+Jo3kluxy+1N5RvMSphoHXtqquff 34xB+YLxdLVENW5bDAAtwPX0bcNDBeHziMv/CcGmNB7QneFcwcm01tNXES9eDS9s5cbfO gp2P0mAOYk1kMX0mtc4xyld7JU3SQSu5q1QQiH2GfNvw57ndAsUp/N9lWYX3qPiQhSSrC riBRGidsiuoWQuKi4BEPbu/RA1LAajSq+FJTxQ0WGj4RyVx+uLrlTGsOmgNWOCfpXKw== ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass header.d=gmail.com header.i=@gmail.com header.a=rsa-sha256 header.s=20260707 header.b=Mecgm0v0; arc=none smtp.remote-ip=74.125.82.45 Received: from mail-dl1-f45.google.com (mail-dl1-f45.google.com [74.125.82.45]) (using TLSv1.3 with cipher TLS_AES_128_GCM_SHA256 (128/128 bits) key-exchange X25519 server-signature ECDSA (prime256v1) server-digest SHA256) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 137BD606A32A for ; Fri, 30 Oct 2026 11:52:40 +0000 (UTC) DMARC-Filter: OpenDMARC Filter v1.4.2 smtp.subspace.kernel.org 137BD606A32A Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key, unprotected) header.d=gmail.com header.i=@gmail.com header.a=rsa-sha256 header.s=20260707 header.b=Mecgm0v0 Received: by mail-dl1-f45.google.com with SMTP id a92af1059eb24-1a3c08d6928so718888c88.0 for ; Fri, 30 Oct 2026 04:52:40 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20260707; t=1793361160; x=1793965960; darn=vger.kernel.org; h=cc:to:in-reply-to:references:message-id:content-transfer-encoding :content-type:mime-version:subject:date:from:from:to:cc:subject:date :message-id:reply-to:content-type; bh=Iaj1sSwxGW2T2ZYTzsyLzlK1pKpVJ1ZuRU1k4FtQ+9k=; b=Mecgm0v0oSdcH99fhKlHSdy15snsTKlHtBODX0A8cRlguZJ4WhHDeXYFZdqzLI2vOy 4+xC7JptTaFDIk8l1ThE+HXwDPkblcNPxxuhW773V+m4+EYPm3FgGSDmBgpc1QMe1tKc t/SMuxejQTO/NIPtxHI+6z+f2T6YLBKpOLLLD6Wl0Vwjt8WAeEzPixbQdb6iXm9gLNKK p9tsrR25PXWFtkh9ZV4781RGuxtXoyrVnjBa/r5U7jXsfTtuTYrFNv9CCLPAfrL/G/HG cGsSBJmcAbZ8Kc0jBWAkskqXc+xyQR0NtzrTg4304wS8df/WODcdFvAOczuavikcZAS0 504A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20260707; t=1793361160; x=1793965960; h=cc:to:in-reply-to:references:message-id:content-transfer-encoding :content-type:mime-version:subject:date:from:x-gm-gg :x-gm-message-state:from:to:cc:subject:date:message-id:reply-to :content-type; bh=Iaj1sSwxGW2T2ZYTzsyLzlK1pKpVJ1ZuRU1k4FtQ+9k=; b=wCBlZ8iJB7zggp+2OJpjNkys1RleORbTWDAVqzEixKyK3iQn6udeZ+0DKExyVpAvq2 fN4iTJBd0oa082pQgpGXYJ1+kEPEXvtQNlw1Fzka0GpG1jq7QB+ua0fNWGwciGtxNAck JhWidMDmMNH2KqxAo43LuKfJLPZ0XSoDHxF/tcCF7VjAkrVsItUfihZVd3iTxmeDWnZQ BUQ0Q5e9Egycx8fmd5XbjxEtUtnLPOpo1HsE7WWjWaScxMGLTg9b/t/j4ihQFeQwOLCo YwstY9sEn0qaIPu8SKlWJQbt+Jr+SPeSXb2zDAVSRHM7WSl74ZYAXZB8wYmKh9OPnAaT d83A== X-Forwarded-Encrypted: i=1; AKwUvByvOrK+0GqAQtecc4n80aefKWybcHbDayJvcXmiJeMsjEalG0M7WK0xChRWau2+jHjtaY+iT50wLFhLcSPo8dc=@vger.kernel.org X-Gm-Message-State: AFq9FYKF0h9ICLpk6XRYUzgpywbHJDhJgoTV2P1kLoRiJwxXyOwm3J3x kCy4IHGAQNQDTiS9FylbGWLR0nhX/Yz4VDiPSMok87v+vTmtOCIyKFws X-Gm-Gg: AYBFou3qrv6SfEMhxUV04zX+NZsnKGIPJTX6bqQwQpLqdHdMYl4SEAsLSHpumgCElrt aVJuQvEQKKphFwy1g/kwkh2aCIjxO8vW64G5bRZF2NoBSsV76PTkHuBuYtWVtHc4hB8yjW7iZfI n2XypvidMpwvwiginAUTDGgyX5+zvhyMlHnwLRyWtcyykMyQdV/2h4lku+qbDs3yg5xYX3qedkG PW0B8mL2XoM9tFJgeyORkeNf2C17chZnWa0SPGedg39CC06rauUTSrQPC8mOmBlI2MgoW5Fi0D0 4w9tD71k+hTGNftC2/xrylhsd7Idj1otQYSXjlVORjMeLXOPEUQldzqIoFl30RIUPDpdPfw2Ess 1ZQ7KvpfGvjUIN9jDE5Hou3WMLw2gj1eYFCIXnGJKaOxkgh30Whpfo5Ym2WGLPoMfzVct5HeHuB R0mFnElgYR5l9ZIK8t1Sk6tXNJmHFzJ4LMv/mz/8CG41YZUXO3ciDOFBhy/pl/JL3iUpCEWj33w wFNZ/QH0B9ZoeHgE2foPSkyc7mqgimUFBHZbxurADDcg6pwnkbE3wK2DvYTGo7wxHK7ULRQvJE5 vpVww3NipkLJuhSbw6ceXsxx2Q== X-Received: by 2002:a05:7022:2203:b0:18d:c38c:bcc9 with SMTP id a92af1059eb24-1ac56e8a821mr4357307c88.3.1793361160023; Fri, 30 Oct 2026 04:52:40 -0700 (PDT) Received: from [127.0.1.1] ([23.254.208.9]) by smtp.gmail.com with ESMTPSA id a92af1059eb24-1ac1abcd6f1sm6437304c88.20.2026.10.30.04.52.33 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 30 Oct 2026 04:52:39 -0700 (PDT) From: Qiliang Yuan Date: Fri, 30 Oct 2026 07:51:52 -0400 Subject: [PATCH bpf-next v2 07/22] bpf: Let the patch list remove instructions X-Mailing-List: linux-kselftest@vger.kernel.org List-Id: List-Post: List-Help: List-Subscribe: List-Unsubscribe: List-Owner: Precedence: list MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: 7bit Message-Id: <20261030-bpf-verifier-patch-batch-v2-7-55cd43439f7c@gmail.com> References: <20261030-bpf-verifier-patch-batch-v2-0-55cd43439f7c@gmail.com> In-Reply-To: <20261030-bpf-verifier-patch-batch-v2-0-55cd43439f7c@gmail.com> To: Alexei Starovoitov , Daniel Borkmann , John Fastabend , Andrii Nakryiko , Eduard Zingerman , Kumar Kartikeya Dwivedi , Martin KaFai Lau , Song Liu , Yonghong Song , Jiri Olsa , Emil Tsalapatis , Ihor Solodrai , Shuah Khan Cc: bpf@vger.kernel.org, linux-kernel@vger.kernel.org, linux-kselftest@vger.kernel.org, Qiliang Yuan X-Mailer: b4 0.13.0 verifier_remove_insns() removes a range of instructions. It moves the tail of the program and of the aux data, walks all branches, and fixes up the subprogs, the line info, the function pointers and the instruction arrays, at the same O(N * M) cost as patching. The patch list can only replace instructions, so bpf_opt_remove_nops() and bpf_opt_remove_dead_code() can't move over to it. Add bpf_patch_list_del() to queue the removal of an instruction along with patches. Map a removed instruction to the next one that stays, so that jumps to it land there. Drop the line info of removed instructions, except that the last one moves to the next instruction that stays if that has none of its own. Remove the subprogs whose instructions are all removed, with their func_info, and mark the function pointers to them and the entries of instruction arrays deleted. Tell offloaded programs about each removed range. Signed-off-by: Qiliang Yuan --- include/linux/bpf_verifier.h | 9 +++ kernel/bpf/bpf_insn_array.c | 10 ++- kernel/bpf/core.c | 27 +++++++- kernel/bpf/fixups.c | 142 ++++++++++++++++++++++++++++++++++++++++--- 4 files changed, 176 insertions(+), 12 deletions(-) diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h index 49a6e443de75d..ace314cc539dd 100644 --- a/include/linux/bpf_verifier.h +++ b/include/linux/bpf_verifier.h @@ -1089,6 +1089,7 @@ struct bpf_patch_image { u32 new_cnt; s32 grow; u32 bad; + bool del; }; /* Map an offset in the old program, which may be past its end. */ @@ -1098,9 +1099,16 @@ static inline u32 bpf_patch_image_remap(const struct bpf_patch_image *img, return off <= img->cnt ? map[off] : off + img->grow; } +static inline bool bpf_patch_image_deleted(const struct bpf_patch_image *img, u32 off) +{ + return off < img->cnt && img->new_off[off] == img->new_off[off + 1]; +} + struct bpf_insn *__bpf_patch_list_add(struct bpf_patch_list *pl, const struct bpf_prog *prog, u32 off, const struct bpf_insn *patch, u32 len); +int __bpf_patch_list_del(struct bpf_patch_list *pl, const struct bpf_prog *prog, + u32 off); void bpf_patch_list_release(struct bpf_patch_list *pl); int bpf_patch_list_build(const struct bpf_patch_list *pl, const struct bpf_prog *prog, struct bpf_patch_image *img); @@ -2066,6 +2074,7 @@ struct bpf_insn *bpf_patch_list_add(struct bpf_verifier_env *env, u32 off, const struct bpf_insn *patch, u32 len); int bpf_patch_list_commit(struct bpf_verifier_env *env); void bpf_patch_list_free(struct bpf_verifier_env *env); +int bpf_patch_list_del(struct bpf_verifier_env *env, u32 off); int bpf_flip_opcode(u32 opcode); u8 bpf_rev_opcode(u8 opcode); diff --git a/kernel/bpf/bpf_insn_array.c b/kernel/bpf/bpf_insn_array.c index dbfcf1eddb91e..5330e2d7f4062 100644 --- a/kernel/bpf/bpf_insn_array.c +++ b/kernel/bpf/bpf_insn_array.c @@ -254,8 +254,9 @@ void bpf_insn_array_adjust(struct bpf_map *map, u32 first, u32 len) } /* - * Move each offset to new_off[offset], new_off[] covers [0, cnt]. Offsets - * past the end of the old program only move by 'grow'. + * Move each offset to new_off[offset], new_off[] covers [0, cnt]. An insn is + * removed when it maps to the same offset as the next one. Offsets past the + * end of the old program only move by 'grow'. */ void bpf_insn_array_remap(struct bpf_map *map, const u32 *new_off, u32 cnt, s32 grow) { @@ -267,7 +268,10 @@ void bpf_insn_array_remap(struct bpf_map *map, const u32 *new_off, u32 cnt, s32 off = insn_array->values[i].xlated_off; if (off == INSN_DELETED) continue; - insn_array->values[i].xlated_off = off <= cnt ? new_off[off] : off + grow; + if (off < cnt && new_off[off] == new_off[off + 1]) + insn_array->values[i].xlated_off = INSN_DELETED; + else + insn_array->values[i].xlated_off = off <= cnt ? new_off[off] : off + grow; } } diff --git a/kernel/bpf/core.c b/kernel/bpf/core.c index d2c36db09c8c9..75d6399ce0965 100644 --- a/kernel/bpf/core.c +++ b/kernel/bpf/core.c @@ -658,6 +658,25 @@ struct bpf_insn *__bpf_patch_list_add(struct bpf_patch_list *pl, return &pl->insns[p->start + len - 1]; } +/* Queue the removal of insn 'off'. Jumps to it land on the next insn that stays. */ +int __bpf_patch_list_del(struct bpf_patch_list *pl, const struct bpf_prog *prog, + u32 off) +{ + struct bpf_insn_patch *p; + int err; + + err = patch_list_reserve_patch(pl); + if (err) + return err; + + p = &pl->patches[pl->cnt++]; + p->off = off; + p->len = 0; + p->start = pl->insn_cnt; + p->orig = prog->insnsi[off]; + return 0; +} + void bpf_patch_list_release(struct bpf_patch_list *pl) { kvfree(pl->patches); @@ -684,8 +703,10 @@ int bpf_patch_list_build(const struct bpf_patch_list *pl, const struct bpf_prog for (i = 0, k = 0; i <= cnt; i++) { img->new_off[i] = i + img->grow; - if (k < pl->cnt && pl->patches[k].off == i) + if (k < pl->cnt && pl->patches[k].off == i) { + img->del |= !pl->patches[k].len; img->grow += pl->patches[k++].len - 1; + } } img->new_cnt = cnt + img->grow; @@ -724,7 +745,7 @@ void bpf_patch_image_free(struct bpf_patch_image *img) /* * Put the new image in 'prog', which has room for it, and move the poke - * descriptors and the line info along. + * descriptors and, unless insns were removed, the line info along. */ void bpf_patch_image_install(struct bpf_prog *prog, const struct bpf_patch_image *img) { @@ -738,6 +759,8 @@ void bpf_patch_image_install(struct bpf_prog *prog, const struct bpf_patch_image bpf_patch_image_remap(img, img->new_off, prog->aux->poke_tab[i].insn_idx); + if (img->del) + return; for (i = 0; i < prog->aux->nr_linfo; i++) prog->aux->linfo[i].insn_off = bpf_patch_image_remap(img, img->new_off, diff --git a/kernel/bpf/fixups.c b/kernel/bpf/fixups.c index 940265cb80ebf..1a1a374a076b1 100644 --- a/kernel/bpf/fixups.c +++ b/kernel/bpf/fixups.c @@ -408,6 +408,22 @@ struct bpf_insn *bpf_patch_list_add(struct bpf_verifier_env *env, u32 off, return __bpf_patch_list_add(pl, env->prog, off, patch, len); } +/* Queue the removal of insn 'off' until bpf_patch_list_commit(). */ +int bpf_patch_list_del(struct bpf_verifier_env *env, u32 off) +{ + struct bpf_patch_list *pl = &env->patch_list; + + if (bpf_rewrite_must_abort()) + return -EINTR; + + if (verifier_bug_if(off >= env->prog->len || + (pl->cnt && off <= pl->patches[pl->cnt - 1].off), + env, "insn %u removed out of order", off)) + return -EFAULT; + + return __bpf_patch_list_del(pl, env->prog, off); +} + void bpf_patch_list_free(struct bpf_verifier_env *env) { bpf_patch_list_release(&env->patch_list); @@ -453,9 +469,79 @@ static void patch_list_adj_aux(struct bpf_prog *prog, struct bpf_insn_patch *p, } /* - * Apply all queued patches in one go. Everything that names an insn of the - * old image follows it to the new one, a patched insn is named by the first - * insn of its patch, like with bpf_patch_insn_data(). + * Drop the line info of removed insns. The last one before the next insn + * that stays moves to it, unless that insn has its own line info. + */ +static void patch_list_adj_linfo(struct bpf_verifier_env *env, + const struct bpf_patch_image *img, u32 *linfo_map) +{ + struct bpf_prog_aux *aux = env->prog->aux; + struct bpf_line_info *linfo = aux->linfo; + u32 i, j, pos, next, nr = aux->nr_linfo; + + for (i = 0, j = 0; i < nr; i++) { + pos = bpf_patch_image_remap(img, img->new_off, linfo[i].insn_off); + linfo_map[i] = j; + if (bpf_patch_image_deleted(img, linfo[i].insn_off)) { + next = i + 1 < nr ? + bpf_patch_image_remap(img, img->new_off, linfo[i + 1].insn_off) : + U32_MAX; + if (pos >= img->new_cnt || next == pos) + continue; + } + linfo[j] = linfo[i]; + linfo[j++].insn_off = pos; + } + linfo_map[nr] = j; + aux->nr_linfo = j; + + /* NOTE: fake 'exit' subprog should be updated as well. */ + for (i = 0; i <= env->subprog_cnt; i++) + env->subprog_info[i].linfo_idx = + linfo_map[min(env->subprog_info[i].linfo_idx, nr)]; +} + +/* Remove the subprogs whose insns are all removed, with their func_info. */ +static void patch_list_del_subprogs(struct bpf_verifier_env *env, + const u32 *new_off) +{ + struct bpf_subprog_info *info = env->subprog_info; + struct bpf_prog_aux *aux = env->prog->aux; + int i, j, exc_cb = env->exception_callback_subprog; + + for (i = 0, j = 0; i < env->subprog_cnt; i++) { + if (new_off[info[i].start] == new_off[info[i + 1].start]) { + /* The exception callback is live, so it isn't removed. */ + if (env->exception_callback_subprog > i) + exc_cb--; + continue; + } + if (i != j) { + info[j] = info[i]; + if (aux->func_info) + aux->func_info[j] = aux->func_info[i]; + if (aux->func_info_aux) + aux->func_info_aux[j] = aux->func_info_aux[i]; + } + j++; + } + if (i == j) + return; + + /* move fake 'exit' subprog as well */ + info[j] = info[i]; + /* func_info->insn_off is set after all code rewrites, in adjust_btf_func() */ + if (aux->func_info) + aux->func_info_cnt -= i - j; + env->subprog_cnt = j; + env->exception_callback_subprog = exc_cb; +} + +/* + * Apply all queued patches and removals in one go. Everything that names an + * insn of the old image follows it to the new one. A patched insn is named by + * the first insn of its patch, a removed insn by the next insn that stays, + * like with bpf_patch_insn_data(). */ int bpf_patch_list_commit(struct bpf_verifier_env *env) { @@ -463,7 +549,8 @@ int bpf_patch_list_commit(struct bpf_verifier_env *env) struct bpf_insn_aux_data *data = NULL; struct bpf_prog *prog = env->prog; struct bpf_patch_image img = {}; - u32 i, k, end; + u32 *linfo_map = NULL; + u32 i, k, n, end; struct bpf_insn_patch *p; int err = 0; @@ -488,20 +575,43 @@ int bpf_patch_list_commit(struct bpf_verifier_env *env) GFP_KERNEL_ACCOUNT | __GFP_ZERO); if (!data) goto out; + if (img.del && prog->aux->nr_linfo) { + linfo_map = kvmalloc_array(prog->aux->nr_linfo + 1, + sizeof(*linfo_map), GFP_KERNEL_ACCOUNT); + if (!linfo_map) + goto out; + } prog = bpf_prog_realloc(prog, bpf_prog_size(img.new_cnt), GFP_USER); if (!prog) goto out; env->prog = prog; + if (img.del && bpf_prog_is_offloaded(prog->aux)) { + /* the aux data still describes the old image */ + for (k = 0; k < pl->cnt; k = n) { + for (n = k; n < pl->cnt && !pl->patches[n].len && + pl->patches[n].off == pl->patches[k].off + n - k; n++) + ; + if (n == k) + n++; + else + bpf_prog_offload_remove_insns(env, pl->patches[k].off, + n - k); + } + } + bpf_patch_image_install(prog, &img); for (i = 0, k = 0; i < img.cnt; i = end) { if (k < pl->cnt && pl->patches[k].off == i) { p = &pl->patches[k++]; - patch_list_adj_aux(prog, p, &pl->insns[p->start], - &env->insn_aux_data[i], - &data[img.new_off[i]]); + if (p->len) + patch_list_adj_aux(prog, p, &pl->insns[p->start], + &env->insn_aux_data[i], + &data[img.new_off[i]]); + else + bpf_clear_insn_aux_data(env, i, 1); end = i + 1; continue; } @@ -514,25 +624,43 @@ int bpf_patch_list_commit(struct bpf_verifier_env *env) env->insn_aux_data_len = img.new_cnt; data = NULL; + /* before subprogs are removed, since it looks at them */ for (i = 0; i < env->func_ptr_cnt; i++) { struct bpf_func_ptr *fp = &env->func_ptrs[i]; + int subprog; if (fp->xlated_off == BPF_FUNC_PTR_DELETED) continue; + if (bpf_patch_image_deleted(&img, fp->xlated_off)) { + subprog = bpf_find_subprog(env, fp->xlated_off); + if (subprog <= 0 || + img.new_off[env->subprog_info[subprog].start] == + img.new_off[env->subprog_info[subprog + 1].start]) { + fp->xlated_off = BPF_FUNC_PTR_DELETED; + continue; + } + } fp->xlated_off = bpf_patch_image_remap(&img, img.new_off, fp->xlated_off); } + if (img.del) + patch_list_del_subprogs(env, img.new_off); + /* NOTE: fake 'exit' subprog should be updated as well. */ for (i = 0; i <= env->subprog_cnt; i++) env->subprog_info[i].start = bpf_patch_image_remap(&img, img.new_off, env->subprog_info[i].start); + if (linfo_map) + patch_list_adj_linfo(env, &img, linfo_map); + for (i = 0; i < env->insn_array_map_cnt; i++) bpf_insn_array_remap(env->insn_array_maps[i], img.new_off, img.cnt, img.grow); err = 0; out: + kvfree(linfo_map); vfree(data); bpf_patch_image_free(&img); bpf_patch_list_release(pl); -- 2.43.0