All of lore.kernel.org
 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 an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.