[PATCH] selftests/bpf: Bound the offset accumulator in __tld_fetch_key()

[PATCH] selftests/bpf: Bound the offset accumulator in __tld_fetch_key()

[Yonghong Song]

The LLVM commit c7f4a76da024 [1]
  "[InstCombine] fold ((x - 1) | (2^k - 1)) + 1 to (x + (2^k - 1)) & -(2^k)"
caused test_task_local_data.bpf.o to fail verification:

  The sequence of 8193 jumps is too complex.
  processed 188770 insns (limit 1000000) max_states_per_insn 34
  total_states 8238 peak_states 12330 mark_read 0

TLD_ROUND_UP(x, 8) expands to ((((x) - 1) | 7) + 1), exactly the pattern
that [1] rewrites, so the accumulation in __tld_fetch_key()

	off += TLD_ROUND_UP(metadata[i].size, 8);

is now compiled as (x + 7) & -8 instead of ((x - 1) | 7) + 1. Both are
correct, but they leave the verifier in very different states. Note that
'off' is marked as precise.

Without [1], "size - 1" wraps at zero (size is a __u16), so
the verifier loses all bounds on the increment:

  211: (69) r1 = *(u16 *)(r1 +62)  ; R1=scalar(...,umax32=0xffff,var_off=(0x0; 0xffff))
  212: (04) w1 += -1               ; R1=scalar(smin=0,smax=umax=0xffffffff,smin32=-1,smax32=0xfffe,var_off=(0x0; 0xffffffff))
  213: (44) w1 |= 7                ; R1=scalar(smin=umin=umin32=7,smax=umax=0xffffffff,var_off=(0x7; 0xfffffff8))
  214: (0c) w6 += w1               ; R6=scalar(smin=umin=umin32=7,smax=umax=0xffffffff,var_off=(0x7; 0xfffffff8))
  215: (04) w6 += 1                ; R6=scalar(smin=0,smax=umax=umax32=0xfffffff8,var_off=(0x0; 0xfffffff8))

Note that 'w6' will be used in the next iteration. In the next iteration
after insn 215, the R6 range will be the same as previous iteration.
The iterator loop converges at depth 2.

With [1] the increment stays precisely bounded at [0, 0x10006]:

  211: (69) r9 = *(u16 *)(r1 +62)  ; R9=scalar(...,umax32=0xffff,var_off=(0x0; 0xffff))
  212: (04) w9 += 7                ; R9=scalar(...,umax32=0x10006,var_off=(0x0; 0x1ffff))
  213: (54) w9 &= 131064           ; R9=scalar(...,umax32=0x10006,var_off=(0x0; 0x1fff8))
  214: (0c) w9 += w6               ; R9=scalar(...,umax32=0x10006,var_off=(0x0; 0x1fff8))
  215: (bf) r1 = r10
  216: (07) r1 += -8
  217: (85) call bpf_iter_num_next
  218: (bc) w6 = w9

In the next iteration, we will have
  211: (69) r9 = *(u16 *)(r1 +62)       ; R9=scalar(...,umax32=0xffff,var_off=(0x0; 0xffff))
  212: (04) w9 += 7                     ; R9=scalar(...,umax32=0x10006,var_off=(0x0; 0x1ffff))
  213: (54) w9 &= 131064                ; R9=scalar(...,umax32=0x10006,var_off=(0x0; 0x1fff8))
  214: (0c) w9 += w6                    ; R9=scalar(...,umax32=0x2000c,var_off=(0x0; 0x3fff8))
  ...

so 'off' umax grows by 0x10006 on every iteration and the loop-head
state never repeats:

  218: (bc) w6 = w9  ; R6=scalar(...,umax32=0x10006,var_off=(0x0; 0x1fff8))
  218: (bc) w6 = w9  ; R6=scalar(...,umax32=0x2000c,var_off=(0x0; 0x3fff8))
  218: (bc) w6 = w9  ; R6=scalar(...,umax32=0x30012,var_off=(0x0; 0x3fff8))
  ...
  218: (bc) w6 = w9  ; R6=scalar(...,umax32=0xff95fd6,var_off=(0x0; 0xffffff8))

That last one is iterator depth 4090. Saturating umax would take ~65531
iterations; the verifier gives up long before that.

Note the loop does not diverge from the start. widen_imprecise_scalars()
blows 'off' up to an unbounded scalar while it is still imprecise, and that
alone converges the first three passes through the loop at depth 4.
Once mark_chain_precision() reaches the loop body, maybe_widen_reg() starts
skipping the register, and no widening ever happens again. In the failing
log widening fires exactly 6 times out of 4098 arrivals at the iter_next()
checkpoint, all of them before the umax starts accumulating.

With [1] and this fix, here is one full trip through the loop body,
entered with 'off' (R6) already clamped by the previous iteration:

  208: frame1: R6=scalar(...,umax32=4088,var_off=(0x0; 0xff8))
  208: (67) r7 <<= 6                ; R7=scalar(...,umax32=3968,var_off=(0x0; 0xfc0))
  209: (bf) r1 = r9                 ; R1=mem(id=54,sz=4036,imm=4)
  210: (0f) r1 += r7
  211: (69) r1 = *(u16 *)(r1 +62)   ; R1=scalar(...,umax32=0xffff,var_off=(0x0; 0xffff))
  212: (04) w1 += 7                 ; R1=scalar(...,umax32=0x10006,var_off=(0x0; 0x1ffff))
  213: (54) w1 &= 131064            ; R1=scalar(...,umax32=0x10006,var_off=(0x0; 0x1fff8))
  214: (0c) w1 += w6                ; R1=scalar(...,umax32=0x10ffe,var_off=(0x0; 0x1fff8))
                                      R6=scalar(...,umax32=4088,var_off=(0x0; 0xff8))
  215: (bc) w6 = w1                 ; R6=scalar(...,umax32=0x10ffe,var_off=(0x0; 0x1fff8))
  216: (26) if w1 > 0xff8 goto pc+1 ; R6=scalar(...,umax32=4088,var_off=(0x0; 0xff8))
  217: (05) goto pc-27

This makes the loop body a fixpoint. 'off' (w6) enters at 208 as [0, 4088] with
var_off=(0x0; 0xff8); the increment computed at 212/213 is [0, 0x10006], so
214/215 leave it at [0, 0x10ffe]; then 216 truncates it straight back to
[0, 4088]/(0x0; 0xff8), and only then is the back edge at 217 taken.
Convergence no longer depends on the widening window above. Verification converges
at iterator depth 3.

  [1] https://github.com/llvm/llvm-project/pull/216436

Signed-off-by: Yonghong Song <yonghong.song@linux.dev>
---
 tools/testing/selftests/bpf/progs/task_local_data.bpf.h | 3 +++
 1 file changed, 3 insertions(+)

diff --git a/tools/testing/selftests/bpf/progs/task_local_data.bpf.h b/tools/testing/selftests/bpf/progs/task_local_data.bpf.h
index 0df8a12fd61e..a31a399870be 100644
--- a/tools/testing/selftests/bpf/progs/task_local_data.bpf.h
+++ b/tools/testing/selftests/bpf/progs/task_local_data.bpf.h
@@ -61,6 +61,7 @@
 #define TLD_ROUND_UP(x, y) ((((x) - 1) | TLD_ROUND_MASK(x, y)) + 1)
 
 #define TLD_MAX_DATA_CNT (__PAGE_SIZE / sizeof(struct tld_metadata) - 1)
+#define TLD_DATA_SIZE (__PAGE_SIZE - sizeof(__u64))
 
 #ifndef TLD_NAME_LEN
 #define TLD_NAME_LEN 62
@@ -189,6 +190,8 @@ static int __tld_fetch_key(struct tld_object *tld_obj, const char *name, int i_s
 			return start + off;
 
 		off += TLD_ROUND_UP(metadata[i].size, 8);
+		if (off > TLD_DATA_SIZE)
+			break;
 	}
 
 	return -cnt;
-- 
2.53.0-Meta

Re: [PATCH] selftests/bpf: Bound the offset accumulator in __tld_fetch_key()

[sashiko-bot]

Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:

Pre-existing issues:
- [Medium] The return value of `__tld_fetch_key` can be truncated to a positive value when assigned to a `__s16` variable, leading to invalid memory accesses in BPF programs.
--

commit 9916e7593b30ccde51452c3954f02517563a9c94
Author: Yonghong Song <yonghong.song@linux.dev>

selftests/bpf: Bound the offset accumulator in __tld_fetch_key()

The LLVM commit c7f4a76da024 caused test_task_local_data.bpf.o to fail 
verification because TLD_ROUND_UP(x, 8) expansion interacts poorly with an
InstCombine fold. This patch adds a bounds check to the offset accumulator
in __tld_fetch_key() to ensure the verifier maintains precise bounds and
converges during loop analysis.

> diff --git a/tools/testing/selftests/bpf/progs/task_local_data.bpf.h b/tools/testing/selftests/bpf/progs/task_local_data.bpf.h
> index 0df8a12fd61e2..a31a399870bef 100644
> --- a/tools/testing/selftests/bpf/progs/task_local_data.bpf.h
> +++ b/tools/testing/selftests/bpf/progs/task_local_data.bpf.h
[ ... ]
> @@ -189,6 +190,8 @@ static int __tld_fetch_key(struct tld_object *tld_obj, const char *name, int i_s
>  			return start + off;
>  
>  		off += TLD_ROUND_UP(metadata[i].size, 8);
> +		if (off > TLD_DATA_SIZE)
> +			break;
>  	}
>  
>  	return -cnt;

[Severity: Medium]
This isn't a bug introduced by this patch, but does returning `-cnt` cause an
issue if `cnt` exceeds 32768?

The `cnt` variable originates from `tld_obj->data_map->meta->cnt` which is a
user-controlled `__u16` (capable of holding up to 65535). When `-cnt` is
returned by `__tld_fetch_key()`, it is later assigned to a `__s16` field in
`tld_get_data()`:

	off = __tld_fetch_key(tld_obj, name, cnt);
	(tld_obj)->key_map->key.off = off;

If a user space process sets `cnt` greater than 32768 (e.g., 60000), `-60000`
will be truncated when assigned to the `__s16` field `key.off`, resulting in a
positive value (e.g., 5536).

On subsequent calls to `tld_get_data()`, the cache miss logic would be
bypassed since `off > 0` is true, and the BPF program would erroneously read
from an invalid or unintended memory offset instead of the correct task local
data.

Could this corrupt the offset cache if an untrusted user space application
provides a maliciously large `cnt` value in the BPF task storage map?

-- 
Sashiko AI review · https://sashiko.dev/#/patchset/20260828170534.1011183-1-yonghong.song@linux.dev?part=1

Re: [PATCH] selftests/bpf: Bound the offset accumulator in __tld_fetch_key()

[bot+bpf-ci]

[-- Attachment #1: Type: text/plain, Size: 1861 bytes --]

> diff --git a/tools/testing/selftests/bpf/progs/task_local_data.bpf.h b/tools/testing/selftests/bpf/progs/task_local_data.bpf.h
> index 0df8a12fd61e2..a31a399870bef 100644
> --- a/tools/testing/selftests/bpf/progs/task_local_data.bpf.h
> +++ b/tools/testing/selftests/bpf/progs/task_local_data.bpf.h
> @@ -61,6 +61,7 @@
>  #define TLD_ROUND_UP(x, y) ((((x) - 1) | TLD_ROUND_MASK(x, y)) + 1)
>
>  #define TLD_MAX_DATA_CNT (__PAGE_SIZE / sizeof(struct tld_metadata) - 1)
> +#define TLD_DATA_SIZE (__PAGE_SIZE - sizeof(__u64))
>
>  #ifndef TLD_NAME_LEN
>  #define TLD_NAME_LEN 62

This isn't a bug, but struct tld_data_u at line 91 spells out the same
expression for its data[] bound:

    char data[__PAGE_SIZE - sizeof(__u64)] __attribute__((aligned(8)));

Since TLD_DATA_SIZE is exactly that bound, would it be worth using the new
macro there too so the two cannot drift?

> @@ -189,6 +190,8 @@ static int __tld_fetch_key(struct tld_object *tld_obj, const char *name, int i_s
>  			return start + off;
>
>  		off += TLD_ROUND_UP(metadata[i].size, 8);
> +		if (off > TLD_DATA_SIZE)
> +			break;
>  	}
>
>  	return -cnt;

This isn't a bug, but would a short comment here help? The check is
unreachable for any metadata the library can publish (per the -E2BIG
guards in __tld_create_key), so it exists to keep 'off' a loop-invariant
range for the verifier rather than to catch a reachable overflow. The file
already annotates its other non-obvious workarounds inline (the
tld_uptr_dummy_t member carries a comment explaining it only exists to
force BTF emission), so a one-line note here would match the local
convention.


---
AI reviewed your patch. Please fix the bug or email reply why it's not a bug.
See: https://github.com/kernel-patches/vmtest/blob/master/ci/claude/README.md

CI run summary: https://github.com/kernel-patches/bpf/actions/runs/33193637868

Re: [PATCH] selftests/bpf: Bound the offset accumulator in __tld_fetch_key()

[patchwork-bot+netdevbpf]

Hello:

This patch was applied to bpf/bpf.git (master)
by Alexei Starovoitov <ast@kernel.org>:

On Fri, 28 Aug 2026 10:05:34 -0700 you wrote:
> The LLVM commit c7f4a76da024 [1]
>   "[InstCombine] fold ((x - 1) | (2^k - 1)) + 1 to (x + (2^k - 1)) & -(2^k)"
> caused test_task_local_data.bpf.o to fail verification:
> 
>   The sequence of 8193 jumps is too complex.
>   processed 188770 insns (limit 1000000) max_states_per_insn 34
>   total_states 8238 peak_states 12330 mark_read 0
> 
> [...]

Here is the summary with links:
  - selftests/bpf: Bound the offset accumulator in __tld_fetch_key()
    https://git.kernel.org/bpf/bpf/c/28d75dd3eb60

You are awesome, thank you!
-- 
Deet-doot-dot, I am a bot.
https://korg.docs.kernel.org/patchwork/pwbot.html