BPF List
 help / color / mirror / Atom feed
From: sashiko-bot@kernel.org
To: "Alexei Starovoitov" <alexei.starovoitov@gmail.com>, bpf@vger.kernel.org
Subject: Re: [PATCH bpf-next 08/21] bpf: Do not scan all maps for each insn and each subprog
Date: Mon, 16 Nov 2026 06:16:23 +0000	[thread overview]
Message-ID: <sashiko-outbox-216255@kernel.org> (raw)
In-Reply-To: <20261116055638.4171529-9-alexei.starovoitov@gmail.com>

Thank you for your contribution! Sashiko AI review found no new issues
in this patch, but noticed 1 related pre-existing issue it does not
introduce:
- [Critical] bpf: integer overflows in jt_from_subprog() and
  bpf_copy_insn_array_uniq() [1]
--

commit ad22f7b9cb9db9b58629009bfe124e8d3522e5f8
Author: Alexei Starovoitov <ast@kernel.org>

bpf: Do not scan all maps for each insn and each subprog

This commit speeds up program dumping, subprogram JITing, and subprogram jump
table reallocation when a program uses a large number of maps.

> diff --git a/kernel/bpf/cfg.c b/kernel/bpf/cfg.c
> index c16b4a283dbca..92dc8d0dc22a5 100644
> --- a/kernel/bpf/cfg.c
> +++ b/kernel/bpf/cfg.c
> @@ -366,13 +366,14 @@ static int __compute_subprog_jts(struct bpf_verifier_env *env)
>  		}
>  
>  		old_cnt = subprog->jt ? subprog->jt->cnt : 0;
> -		jt = bpf_iarray_realloc(subprog->jt, old_cnt + jt_cur->cnt);
> +		jt = bpf_iarray_realloc(subprog->jt, roundup_pow_of_two(old_cnt + jt_cur->cnt));
>  		if (!jt) {
>  			subprog->jt = NULL;
>  			kvfree(jt_cur);
>  			return -ENOMEM;
>  		}
>  		memcpy(jt->items + old_cnt, jt_cur->items, jt_cur->cnt << 2);
> +		jt->cnt = old_cnt + jt_cur->cnt;
>  		subprog->jt = jt;

[Severity: Critical]
This problem wasn't introduced by this patch, but can jt_cur->cnt << 2
overflow its 32-bit signed int type here [1]?

When an INSN_ARRAY map is configured with a large max_entries value so that
jt_cur->cnt is at least 1 << 29, jt_cur->cnt << 2 overflows into a negative
int and sign-extends into the size_t length passed to memcpy(), causing an
out-of-bounds memory access.

Similarly, bpf_copy_insn_array_uniq() computes u32 n = end - start + 1 and
passes it to sort_insn_array_uniq(), which takes a signed int cnt and passes
it as the size_t element count to sort():

kernel/bpf/cfg.c:sort_insn_array_uniq() {
	int unique = 1;
	int i;

	sort(items, cnt, sizeof(items[0]), cmp_ptr_to_u32, NULL);
    ...
}

kernel/bpf/cfg.c:bpf_copy_insn_array_uniq() {
	u32 n = end - start + 1;
    ...
	return sort_insn_array_uniq(off, n);
}

If n exceeds INT_MAX, cnt becomes negative and sign-extends in sort() into an
out-of-bounds sort.

[1] https://sashiko.dev/#/bug/linux-cb5b5936-948b-46ff-9eb4-c71357c19248

-- 
Sashiko AI review · https://sashiko.dev/#/patchset/20261116055638.4171529-1-alexei.starovoitov@gmail.com?part=8

  reply	other threads:[~2026-11-16  6:16 UTC|newest]

Thread overview: 36+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2026-11-16  5:56 [PATCH bpf-next 00/21] bpf: Remove the limits on maps, kfuncs, subprogs and special fields Alexei Starovoitov
2026-11-16  5:56 ` [PATCH bpf-next 01/21] bpf: Stop a load only when the loader is killed or has to freeze Alexei Starovoitov
2026-11-16  6:39   ` bot+bpf-ci
2026-11-16  6:49   ` sashiko-bot
2026-11-16  5:56 ` [PATCH bpf-next 02/21] bpf: Fail the load when there is no memory Alexei Starovoitov
2026-11-16  6:29   ` sashiko-bot
2026-11-16  5:56 ` [PATCH bpf-next 03/21] bpf: Give a syscall program the largest context when it does tail calls Alexei Starovoitov
2026-11-16  5:56 ` [PATCH bpf-next 04/21] bpf: Do not inline bpf_loop() when its callback is dead code Alexei Starovoitov
2026-11-16  5:56 ` [PATCH bpf-next 05/21] bpf: Dump programs that have more than 524288 insns Alexei Starovoitov
2026-11-16  5:56 ` [PATCH bpf-next 06/21] bpf: Resolve BTF structs and arrays first Alexei Starovoitov
2026-11-16  6:13   ` sashiko-bot
2026-11-16  5:56 ` [PATCH bpf-next 07/21] bpf: Remove the limits on maps, BTFs and fd_array of a program Alexei Starovoitov
2026-11-16  6:39   ` bot+bpf-ci
2026-11-16  5:56 ` [PATCH bpf-next 08/21] bpf: Do not scan all maps for each insn and each subprog Alexei Starovoitov
2026-11-16  6:16   ` sashiko-bot [this message]
2026-11-16  5:56 ` [PATCH bpf-next 09/21] bpf: Remove the limits on kfuncs of a program Alexei Starovoitov
2026-11-16  6:39   ` bot+bpf-ci
2026-11-16  5:56 ` [PATCH bpf-next 10/21] bpf: Remove the limits on tables of functions Alexei Starovoitov
2026-11-16  6:14   ` sashiko-bot
2026-11-16  5:56 ` [PATCH bpf-next 11/21] libbpf: Size the tables of the loader program from the object Alexei Starovoitov
2026-11-16  6:20   ` sashiko-bot
2026-11-16  5:56 ` [PATCH bpf-next 12/21] bpf: Relax jumps that patches push out of range Alexei Starovoitov
2026-11-16  6:52   ` bot+bpf-ci
2026-11-16  5:56 ` [PATCH bpf-next 13/21] bpf: Keep the call graph in lists of edges Alexei Starovoitov
2026-11-16  6:39   ` sashiko-bot
2026-11-16  5:56 ` [PATCH bpf-next 14/21] bpf: Find the effects of callees on the call graph Alexei Starovoitov
2026-11-16  5:56 ` [PATCH bpf-next 15/21] bpf: Link the decl tags of a type Alexei Starovoitov
2026-11-16  5:56 ` [PATCH bpf-next 16/21] bpf: Remove BPF_MAX_SUBPROGS Alexei Starovoitov
2026-11-16  5:56 ` [PATCH bpf-next 17/21] bpf: Walk each type once when looking for special fields Alexei Starovoitov
2026-11-16  5:56 ` [PATCH bpf-next 18/21] bpf: Raise the limit on the length of BTF names Alexei Starovoitov
2026-11-16  5:56 ` [PATCH bpf-next 19/21] bpf: Find dominators in O(n log n) Alexei Starovoitov
2026-11-16  5:56 ` [PATCH bpf-next 20/21] selftests/bpf: Test programs above the old limits Alexei Starovoitov
2026-11-16  6:33   ` sashiko-bot
2026-11-16  6:39   ` bot+bpf-ci
2026-11-16  5:56 ` [PATCH bpf-next 21/21] selftests/bpf: Test limits of the load with raw programs Alexei Starovoitov
2026-11-16  6:39   ` sashiko-bot

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=sashiko-outbox-216255@kernel.org \
    --to=sashiko-bot@kernel.org \
    --cc=alexei.starovoitov@gmail.com \
    --cc=bpf@vger.kernel.org \
    --cc=sashiko-reviews@lists.linux.dev \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox