* [PATCH bpf-next v3 1/3] bpf: better naming for __reg_deduce_bounds() parts
2026-03-13 11:36 [PATCH bpf-next v3 0/3] Optimize bounds refinement by reordering deductions Paul Chaignon
@ 2026-03-13 11:40 ` Paul Chaignon
2026-03-13 12:21 ` bot+bpf-ci
2026-03-13 11:40 ` [PATCH bpf-next v3 2/3] bpf: Avoid one round of bounds deduction Paul Chaignon
` (3 subsequent siblings)
4 siblings, 1 reply; 11+ messages in thread
From: Paul Chaignon @ 2026-03-13 11:40 UTC (permalink / raw)
To: bpf
Cc: Alexei Starovoitov, Daniel Borkmann, Andrii Nakryiko,
Eduard Zingerman, Shung-Hsi Yu
From: Eduard Zingerman <eddyz87@gmail.com>
This renaming will also help reshuffle the different parts in the
subsequent patch.
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
Signed-off-by: Paul Chaignon <paul.chaignon@gmail.com>
---
kernel/bpf/verifier.c | 17 +++++++++++------
1 file changed, 11 insertions(+), 6 deletions(-)
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 4fbacd2149cd..189e951886ed 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -2448,7 +2448,7 @@ static void __update_reg_bounds(struct bpf_reg_state *reg)
}
/* Uses signed min/max values to inform unsigned, and vice-versa */
-static void __reg32_deduce_bounds(struct bpf_reg_state *reg)
+static void deduce_bounds_32_from_64(struct bpf_reg_state *reg)
{
/* If upper 32 bits of u64/s64 range don't change, we can use lower 32
* bits to improve our u32/s32 boundaries.
@@ -2518,6 +2518,10 @@ static void __reg32_deduce_bounds(struct bpf_reg_state *reg)
reg->s32_min_value = max_t(s32, reg->s32_min_value, (s32)reg->smin_value);
reg->s32_max_value = min_t(s32, reg->s32_max_value, (s32)reg->smax_value);
}
+}
+
+static void deduce_bounds_32_from_32(struct bpf_reg_state *reg)
+{
/* if u32 range forms a valid s32 range (due to matching sign bit),
* try to learn from that
*/
@@ -2559,7 +2563,7 @@ static void __reg32_deduce_bounds(struct bpf_reg_state *reg)
}
}
-static void __reg64_deduce_bounds(struct bpf_reg_state *reg)
+static void deduce_bounds_64_from_64(struct bpf_reg_state *reg)
{
/* If u64 range forms a valid s64 range (due to matching sign bit),
* try to learn from that. Let's do a bit of ASCII art to see when
@@ -2694,7 +2698,7 @@ static void __reg64_deduce_bounds(struct bpf_reg_state *reg)
}
}
-static void __reg_deduce_mixed_bounds(struct bpf_reg_state *reg)
+static void deduce_bounds_64_from_32(struct bpf_reg_state *reg)
{
/* Try to tighten 64-bit bounds from 32-bit knowledge, using 32-bit
* values on both sides of 64-bit range in hope to have tighter range.
@@ -2763,9 +2767,10 @@ static void __reg_deduce_mixed_bounds(struct bpf_reg_state *reg)
static void __reg_deduce_bounds(struct bpf_reg_state *reg)
{
- __reg32_deduce_bounds(reg);
- __reg64_deduce_bounds(reg);
- __reg_deduce_mixed_bounds(reg);
+ deduce_bounds_32_from_64(reg);
+ deduce_bounds_32_from_32(reg);
+ deduce_bounds_64_from_64(reg);
+ deduce_bounds_64_from_32(reg);
}
/* Attempts to improve var_off based on unsigned min/max information */
--
2.43.0
^ permalink raw reply related [flat|nested] 11+ messages in thread* Re: [PATCH bpf-next v3 1/3] bpf: better naming for __reg_deduce_bounds() parts
2026-03-13 11:40 ` [PATCH bpf-next v3 1/3] bpf: better naming for __reg_deduce_bounds() parts Paul Chaignon
@ 2026-03-13 12:21 ` bot+bpf-ci
0 siblings, 0 replies; 11+ messages in thread
From: bot+bpf-ci @ 2026-03-13 12:21 UTC (permalink / raw)
To: paul.chaignon, bpf
Cc: ast, daniel, andrii, eddyz87, shung-hsi.yu, ast, andrii, daniel,
martin.lau, eddyz87, yonghong.song, clm, ihor.solodrai
[-- Attachment #1: Type: text/plain, Size: 1102 bytes --]
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 4fbacd2149cd..189e951886ed 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
[ ... ]
> @@ -2518,6 +2518,10 @@ static void __reg32_deduce_bounds(struct bpf_reg_state *reg)
> reg->s32_min_value = max_t(s32, reg->s32_min_value, (s32)reg->smin_value);
> reg->s32_max_value = min_t(s32, reg->s32_max_value, (s32)reg->smax_value);
> }
> +}
> +
> +static void deduce_bounds_32_from_32(struct bpf_reg_state *reg)
> +{
> /* if u32 range forms a valid s32 range (due to matching sign bit),
The new deduce_bounds_32_from_32() contains a comment referencing the
old function name:
/* See __reg64_deduce_bounds() for detailed explanation.
Since this commit renamed __reg64_deduce_bounds() to
deduce_bounds_64_from_64(), should this cross-reference be updated
to match?
---
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/23049683430
^ permalink raw reply [flat|nested] 11+ messages in thread
* [PATCH bpf-next v3 2/3] bpf: Avoid one round of bounds deduction
2026-03-13 11:36 [PATCH bpf-next v3 0/3] Optimize bounds refinement by reordering deductions Paul Chaignon
2026-03-13 11:40 ` [PATCH bpf-next v3 1/3] bpf: better naming for __reg_deduce_bounds() parts Paul Chaignon
@ 2026-03-13 11:40 ` Paul Chaignon
2026-03-13 11:43 ` [PATCH bpf-next v3 3/3] selftests/bpf: Test case for refinement improvement using 64b bounds Paul Chaignon
` (2 subsequent siblings)
4 siblings, 0 replies; 11+ messages in thread
From: Paul Chaignon @ 2026-03-13 11:40 UTC (permalink / raw)
To: bpf
Cc: Alexei Starovoitov, Daniel Borkmann, Andrii Nakryiko,
Eduard Zingerman, Shung-Hsi Yu
In commit 5dbb19b16ac49 ("bpf: Add third round of bounds deduction"), I
added a new round of bounds deduction because two rounds were not enough
to converge to a fixed point. This commit slightly refactor the bounds
deduction logic such that two rounds are enough.
In [1], Eduard noticed that after we improved the refinement logic, a
third call to the bounds deduction (__reg_deduce_bounds) was needed to
converge to a fixed point. More specifically, we needed this third call
to improve the s64 range using the s32 range. We added the third call
and postponed a more detailed analysis of the refinement logic.
I've been looking into this more recently. The register refinement
consists of the following calls.
__update_reg_bounds();
3 x __reg_deduce_bounds() {
deduce_bounds_32_from_64();
deduce_bounds_32_from_32();
deduce_bounds_64_from_64();
deduce_bounds_64_from_32();
};
__reg_bound_offset();
__update_reg_bounds();
From this, we can observe that we first improve the 32bit ranges from
the 64bit ranges in deduce_bounds_32_from_64, then improve the 64bit
ranges on their own in deduce_bounds_64_from_64. Intuitively, if we
were to improve the 64bit ranges on their own *before* we use them to
improve the 32bit ranges, we may reach a fixed point earlier.
In a similar manner, using CBMC, Eduard found that it's best to improve
the 32bit ranges on their own *after* we've improve them using the 64bit
ranges. That is, running deduce_bounds_32_from_32 after
deduce_bounds_32_from_64.
These changes allow us to lose one call to __reg_deduce_bounds. Without
this reordering, the test "verifier_bounds/bounds deduction cross sign
boundary, negative overlap" fails when removing one call to
__reg_deduce_bounds. In some cases, this change can even improve
precision a little bit, as illustrated in the new selftest in the next
patch.
As expected, this change didn't have any impact on the number of
instructions processed when running it through the Cilium complexity
test suite [2].
Link: https://lore.kernel.org/bpf/aIKtSK9LjQXB8FLY@mail.gmail.com/ [1]
Link: https://pchaigno.github.io/test-verifier-complexity.html [2]
Acked-by: Shung-Hsi Yu <shung-hsi.yu@suse.com>
Co-developed-by: Eduard Zingerman <eddyz87@gmail.com>
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
Signed-off-by: Paul Chaignon <paul.chaignon@gmail.com>
---
kernel/bpf/verifier.c | 3 +--
1 file changed, 1 insertion(+), 2 deletions(-)
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 189e951886ed..e29f15419fcb 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -2767,9 +2767,9 @@ static void deduce_bounds_64_from_32(struct bpf_reg_state *reg)
static void __reg_deduce_bounds(struct bpf_reg_state *reg)
{
+ deduce_bounds_64_from_64(reg);
deduce_bounds_32_from_64(reg);
deduce_bounds_32_from_32(reg);
- deduce_bounds_64_from_64(reg);
deduce_bounds_64_from_32(reg);
}
@@ -2793,7 +2793,6 @@ static void reg_bounds_sync(struct bpf_reg_state *reg)
/* We might have learned something about the sign bit. */
__reg_deduce_bounds(reg);
__reg_deduce_bounds(reg);
- __reg_deduce_bounds(reg);
/* We might have learned some bits from the bounds. */
__reg_bound_offset(reg);
/* Intersecting with the old var_off might have improved our bounds
--
2.43.0
^ permalink raw reply related [flat|nested] 11+ messages in thread* [PATCH bpf-next v3 3/3] selftests/bpf: Test case for refinement improvement using 64b bounds
2026-03-13 11:36 [PATCH bpf-next v3 0/3] Optimize bounds refinement by reordering deductions Paul Chaignon
2026-03-13 11:40 ` [PATCH bpf-next v3 1/3] bpf: better naming for __reg_deduce_bounds() parts Paul Chaignon
2026-03-13 11:40 ` [PATCH bpf-next v3 2/3] bpf: Avoid one round of bounds deduction Paul Chaignon
@ 2026-03-13 11:43 ` Paul Chaignon
2026-03-13 21:58 ` Eduard Zingerman
2026-03-13 22:02 ` [PATCH bpf-next v3 0/3] Optimize bounds refinement by reordering deductions Eduard Zingerman
2026-03-14 2:20 ` patchwork-bot+netdevbpf
4 siblings, 1 reply; 11+ messages in thread
From: Paul Chaignon @ 2026-03-13 11:43 UTC (permalink / raw)
To: bpf
Cc: Alexei Starovoitov, Daniel Borkmann, Andrii Nakryiko,
Eduard Zingerman, Shung-Hsi Yu
This new selftest demonstrates the improvement of bounds refinement from
the previous patch. It is inspired from a set of reg_bounds_sync inputs
generated using CBMC [1] by Shung-Hsi:
reg.smin_value=0x8000000000000002
reg.smax_value=2
reg.umin_value=2
reg.umax_value=19
reg.s32_min_value=2
reg.s32_max_value=3
reg.u32_min_value=2
reg.u32_max_value=3
reg_bounds_sync returns R=[2; 3] without the previous patch, and R=2
with it. __reg64_deduce_bounds is able to derive that u64=2, but before
the previous patch, those bounds are overwritten in
__reg_deduce_mixed_bounds using the 32bits bounds.
To arrive to these reg_bounds_sync inputs, we bound the 32bits value
first to [2; 3]. We can then upper-bound s64 without impacting u64. At
that point, the refinement to u64=2 doesn't happen because the ranges
still overlap in two points:
0 umin=2 umax=0xff..ff00..03 U64_MAX
| [xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx] |
|----------------------------|------------------------------|
|xx] [xxxxxxxxxxxxxxxxxxxxxxxxxxxx|
0 smax=2 smin=0x800..02 -1
With an upper-bound check at value 19, we can reach the above inputs for
reg_bounds_sync. At that point, the refinement to u64=2 happens and
because it isn't overwritten by __reg_deduce_mixed_bounds anymore,
reg_bounds_sync returns with reg=2.
The test validates this result by including an illegal instruction in
the (dead) branch reg != 2.
Link: https://github.com/shunghsiyu/reg_bounds_sync-review/ [1]
Co-developed-by: Shung-Hsi Yu <shung-hsi.yu@suse.com>
Signed-off-by: Shung-Hsi Yu <shung-hsi.yu@suse.com>
Signed-off-by: Paul Chaignon <paul.chaignon@gmail.com>
---
.../selftests/bpf/progs/verifier_bounds.c | 33 +++++++++++++++++++
1 file changed, 33 insertions(+)
diff --git a/tools/testing/selftests/bpf/progs/verifier_bounds.c b/tools/testing/selftests/bpf/progs/verifier_bounds.c
index ce09379130aa..3724d5e5bcb3 100644
--- a/tools/testing/selftests/bpf/progs/verifier_bounds.c
+++ b/tools/testing/selftests/bpf/progs/verifier_bounds.c
@@ -2037,4 +2037,37 @@ __naked void signed_unsigned_intersection32_case2(void *ctx)
: __clobber_all);
}
+/* After instruction 3, the u64 and s64 ranges look as follows:
+ * 0 umin=2 umax=0xff..ff00..03 U64_MAX
+ * | [xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx] |
+ * |----------------------------|------------------------------|
+ * |xx] [xxxxxxxxxxxxxxxxxxxxxxxxxxxx|
+ * 0 smax=2 smin=0x800..02 -1
+ *
+ * The two ranges can't be refined because they overlap in two places. Once we
+ * add an upper-bound to u64 at instruction 4, the refinement can happen. This
+ * test validates that this refinement does happen and is not overwritten by
+ * the less-precise 32bits ranges.
+ */
+SEC("socket")
+__description("bounds refinement: 64bits ranges not overwritten by 32bits ranges")
+__msg("3: (65) if r0 s> 0x2 {{.*}} R0=scalar(smin=0x8000000000000002,smax=2,umin=smin32=umin32=2,umax=0xffffffff00000003,smax32=umax32=3")
+__msg("4: (25) if r0 > 0x13 {{.*}} R0=2")
+__success __log_level(2)
+__naked void refinement_32bounds_not_overwriting_64bounds(void *ctx)
+{
+ asm volatile(" \
+ call %[bpf_get_prandom_u32]; \
+ if w0 < 2 goto +5; \
+ if w0 > 3 goto +4; \
+ if r0 s> 2 goto +3; \
+ if r0 > 19 goto +2; \
+ if r0 == 2 goto +1; \
+ r10 = 0; \
+ exit; \
+" :
+ : __imm(bpf_get_prandom_u32)
+ : __clobber_all);
+}
+
char _license[] SEC("license") = "GPL";
--
2.43.0
^ permalink raw reply related [flat|nested] 11+ messages in thread* Re: [PATCH bpf-next v3 3/3] selftests/bpf: Test case for refinement improvement using 64b bounds
2026-03-13 11:43 ` [PATCH bpf-next v3 3/3] selftests/bpf: Test case for refinement improvement using 64b bounds Paul Chaignon
@ 2026-03-13 21:58 ` Eduard Zingerman
0 siblings, 0 replies; 11+ messages in thread
From: Eduard Zingerman @ 2026-03-13 21:58 UTC (permalink / raw)
To: Paul Chaignon, bpf
Cc: Alexei Starovoitov, Daniel Borkmann, Andrii Nakryiko,
Shung-Hsi Yu
On Fri, 2026-03-13 at 12:43 +0100, Paul Chaignon wrote:
> This new selftest demonstrates the improvement of bounds refinement from
> the previous patch. It is inspired from a set of reg_bounds_sync inputs
> generated using CBMC [1] by Shung-Hsi:
>
> reg.smin_value=0x8000000000000002
> reg.smax_value=2
> reg.umin_value=2
> reg.umax_value=19
> reg.s32_min_value=2
> reg.s32_max_value=3
> reg.u32_min_value=2
> reg.u32_max_value=3
>
> reg_bounds_sync returns R=[2; 3] without the previous patch, and R=2
> with it. __reg64_deduce_bounds is able to derive that u64=2, but before
> the previous patch, those bounds are overwritten in
> __reg_deduce_mixed_bounds using the 32bits bounds.
>
> To arrive to these reg_bounds_sync inputs, we bound the 32bits value
> first to [2; 3]. We can then upper-bound s64 without impacting u64. At
> that point, the refinement to u64=2 doesn't happen because the ranges
> still overlap in two points:
>
> 0 umin=2 umax=0xff..ff00..03 U64_MAX
> | [xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx] |
> |----------------------------|------------------------------|
> |xx] [xxxxxxxxxxxxxxxxxxxxxxxxxxxx|
> 0 smax=2 smin=0x800..02 -1
>
> With an upper-bound check at value 19, we can reach the above inputs for
> reg_bounds_sync. At that point, the refinement to u64=2 happens and
> because it isn't overwritten by __reg_deduce_mixed_bounds anymore,
> reg_bounds_sync returns with reg=2.
>
> The test validates this result by including an illegal instruction in
> the (dead) branch reg != 2.
>
> Link: https://github.com/shunghsiyu/reg_bounds_sync-review/ [1]
> Co-developed-by: Shung-Hsi Yu <shung-hsi.yu@suse.com>
> Signed-off-by: Shung-Hsi Yu <shung-hsi.yu@suse.com>
> Signed-off-by: Paul Chaignon <paul.chaignon@gmail.com>
> ---
Can confirm, this test case fails on current master.
Tested-by: Eduard Zingerman <eddyz87@gmail.com>
^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: [PATCH bpf-next v3 0/3] Optimize bounds refinement by reordering deductions
2026-03-13 11:36 [PATCH bpf-next v3 0/3] Optimize bounds refinement by reordering deductions Paul Chaignon
` (2 preceding siblings ...)
2026-03-13 11:43 ` [PATCH bpf-next v3 3/3] selftests/bpf: Test case for refinement improvement using 64b bounds Paul Chaignon
@ 2026-03-13 22:02 ` Eduard Zingerman
2026-03-14 2:18 ` Alexei Starovoitov
2026-03-14 2:20 ` patchwork-bot+netdevbpf
4 siblings, 1 reply; 11+ messages in thread
From: Eduard Zingerman @ 2026-03-13 22:02 UTC (permalink / raw)
To: Alexei Starovoitov
Cc: Daniel Borkmann, Andrii Nakryiko, Shung-Hsi Yu, Paul Chaignon,
bpf
On Fri, 2026-03-13 at 12:36 +0100, Paul Chaignon wrote:
> This patchset optimizes the bounds refinement (reg_bounds_sync) by
> reordering deductions in __reg_deduce_bounds. This reordering allows us
> to improve precision slightly while losing one call to
> __reg_deduce_bounds.
>
> The first patch from Eduard refactors the __reg_deduce_bounds
> subfunctions, the second patch implements the reordering, and the last
> one adds a selftest.
>
> Changes in v3:
> - Added first commit from Eduard that significantly helps with
> readability of second commit.
> - Reshuffled a bit more the functions in the second commit to improve
> precision (Eduard).
> - Rebased.
> Changes in v2:
> - Updated description to mention potential precision improvement and
> to clarify the sequence of refinements (Shung-Hsi).
> - Added the second patch.
> - Rebased.
>
> Eduard Zingerman (1):
> bpf: better naming for __reg_deduce_bounds() parts
>
> Paul Chaignon (2):
> bpf: Avoid one round of bounds deduction
> selftests/bpf: Test case for refinement improvement using 64b bounds
This note is mostly for Alexei,
Me an Alexei discussed converting scalar tracking to cnums and whether
we should proceed with this line of work in that light.
After some additional tinkering, I think we should stick to what we
have and land this patch-set. I'll share details on cnums later in a
separate email, but tldr is that cnum representation is strictly less
precise compared to combination of signed and unsigned ranges
(probably this was obvious in the hindsight).
Thanks,
Eduard
^ permalink raw reply [flat|nested] 11+ messages in thread* Re: [PATCH bpf-next v3 0/3] Optimize bounds refinement by reordering deductions
2026-03-13 22:02 ` [PATCH bpf-next v3 0/3] Optimize bounds refinement by reordering deductions Eduard Zingerman
@ 2026-03-14 2:18 ` Alexei Starovoitov
2026-03-14 8:22 ` Eduard Zingerman
0 siblings, 1 reply; 11+ messages in thread
From: Alexei Starovoitov @ 2026-03-14 2:18 UTC (permalink / raw)
To: Eduard Zingerman
Cc: Alexei Starovoitov, Daniel Borkmann, Andrii Nakryiko,
Shung-Hsi Yu, Paul Chaignon, bpf
On Fri, Mar 13, 2026 at 3:02 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
> have and land this patch-set. I'll share details on cnums later in a
> separate email, but tldr is that cnum representation is strictly less
> precise compared to combination of signed and unsigned ranges
> (probably this was obvious in the hindsight).
Understood. Applied the patches,
but I thought that the main advantage of circular representation
that it represents both, since the sign is "absorbed" by the circle.
What did the paper claim?
^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: [PATCH bpf-next v3 0/3] Optimize bounds refinement by reordering deductions
2026-03-14 2:18 ` Alexei Starovoitov
@ 2026-03-14 8:22 ` Eduard Zingerman
2026-03-14 15:08 ` Alexei Starovoitov
0 siblings, 1 reply; 11+ messages in thread
From: Eduard Zingerman @ 2026-03-14 8:22 UTC (permalink / raw)
To: Alexei Starovoitov
Cc: Alexei Starovoitov, Daniel Borkmann, Andrii Nakryiko,
Shung-Hsi Yu, Paul Chaignon, bpf
On Fri, 2026-03-13 at 19:18 -0700, Alexei Starovoitov wrote:
> On Fri, Mar 13, 2026 at 3:02 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
> > have and land this patch-set. I'll share details on cnums later in a
> > separate email, but tldr is that cnum representation is strictly less
> > precise compared to combination of signed and unsigned ranges
> > (probably this was obvious in the hindsight).
>
> Understood. Applied the patches,
> but I thought that the main advantage of circular representation
> that it represents both, since the sign is "absorbed" by the circle.
> What did the paper claim?
Actually, the paper [0] does not compare wrapped intervals to a pair
of signed and unsigned domains tracked in sync. It compares wrapped
intervals to one or the other.
Probably this was obvious from the beginning, but I had to
re-implement reg_bounds_sync() to understand the problem.
When signed and unsigned intervals are tracked separately,
this can describe two arcs on the "number circle".
For example, consider a pair of 32-bit ranges, signed [-128, 127]
and unsigned [1, U32_MAX]. When combined, these describe two arcs:
[-128, -1] and [1, 127]. However, a single wrapped interval will
approximate the above as [-128, 127], loosing some precision.
This example is taken from one of the tests in the reg_bounds.c.
I hit it while rewriting logic deducing 64-bit bounds from 32-bit
bounds, implementation that used intersection of cnums defined
by signed and unsigned intervals failed to refine the following case:
ACTUAL FALSE1: scalar(u64=[0; U64_MAX],u32=[1; 4294967295],s64=[0xffffffffffffff80; 0x7f],s32=[0xffffff80; 0x7f])
EXPECTED FALSE1: scalar(u64=[1; U64_MAX],u32=[1; 4294967295],s64=[0xffffffffffffff80; 0x7f],s32=[0xffffff80; 0x7f])
^-- here
Hence, the final implementation passing all the tests has to consider
signed and unsigned domains separately (see [1]).
Thus, we cannot replace signed / unsigned ranges with a single wrapped
interval w/o dropping some precision.
I'd argue that complete re-implementation of reg_bounds_sync() in
cnums does look a bit simpler compared to current code, but one needs
to take into account the supporting code in [2] and [3].
On the bright side, I noticed that current code inferring 64-bit
bounds from 32-bit ranges does not handle several cases, namely:
N*2^32 (N+1)*2^32 (N+2)*2^32 (N+3)*2^32
||--|=====|----|----------||--|=====|---------------||--|=====|------------|--||
|< b >| | |< b >| |< b >| |
| | | |
|<-------------+--------- a -------------------|----------->|
| |
|<-------- t ------------------>|
Or with b crossing the U32_MAX / 0 boundary:
N*2^32 (N+1)*2^32 (N+2)*2^32 (N+3)*2^32
||===|---------|------|===||===|----------------|===||===|---------|------|===||
|b >| | |< b||b >| |< b||b >| | |< b|
| | | |
|<-----+----------------- a --------------+-------->|
| |
|<---------------- t ------------->|
(a is a 64-bit range, b is a 32-bit range, t is a refined 64-bit range,
such that ∀ v ∈ a, (u32)a ∈ b: v ∈ t)
cnum based code handling such cases (see [1,4]) is a tad simpler
conceptually compared to interval based code (see [5]).
But it is doable in both domains.
So, unless people agree with me that [1] is easier to understand /
maintain, there is little reason to switch to wrapped intervals.
[0] https://jorgenavas.github.io/papers/ACM-TOPLAS-wrapped.pdf
[1] https://github.com/eddyz87/bpf/blob/cnum-sync-bounds/kernel/bpf/verifier.c#L2521
[2] https://github.com/eddyz87/bpf/blob/cnum-sync-bounds/kernel/bpf/cnum_defs.h
[3] https://github.com/eddyz87/bpf/blob/cnum-sync-bounds/kernel/bpf/cnum.c
[4] https://github.com/eddyz87/cnum-verif/blob/master/cnum.c#L92
[5] https://github.com/eddyz87/cnum-verif/blob/master/cnum.c#L171
^ permalink raw reply [flat|nested] 11+ messages in thread* Re: [PATCH bpf-next v3 0/3] Optimize bounds refinement by reordering deductions
2026-03-14 8:22 ` Eduard Zingerman
@ 2026-03-14 15:08 ` Alexei Starovoitov
0 siblings, 0 replies; 11+ messages in thread
From: Alexei Starovoitov @ 2026-03-14 15:08 UTC (permalink / raw)
To: Eduard Zingerman
Cc: Alexei Starovoitov, Daniel Borkmann, Andrii Nakryiko,
Shung-Hsi Yu, Paul Chaignon, bpf
On Sat, Mar 14, 2026 at 1:22 AM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
>
> So, unless people agree with me that [1] is easier to understand /
> maintain, there is little reason to switch to wrapped intervals.
Since the code is there and it passes tests please post it for
proper review. One giant patch is fine. If it passes the initial
"is it easier to understand" test then it can be split into
patches for landing.
^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: [PATCH bpf-next v3 0/3] Optimize bounds refinement by reordering deductions
2026-03-13 11:36 [PATCH bpf-next v3 0/3] Optimize bounds refinement by reordering deductions Paul Chaignon
` (3 preceding siblings ...)
2026-03-13 22:02 ` [PATCH bpf-next v3 0/3] Optimize bounds refinement by reordering deductions Eduard Zingerman
@ 2026-03-14 2:20 ` patchwork-bot+netdevbpf
4 siblings, 0 replies; 11+ messages in thread
From: patchwork-bot+netdevbpf @ 2026-03-14 2:20 UTC (permalink / raw)
To: Paul Chaignon; +Cc: bpf, ast, daniel, andrii, eddyz87, shung-hsi.yu
Hello:
This series was applied to bpf/bpf-next.git (master)
by Alexei Starovoitov <ast@kernel.org>:
On Fri, 13 Mar 2026 12:36:11 +0100 you wrote:
> This patchset optimizes the bounds refinement (reg_bounds_sync) by
> reordering deductions in __reg_deduce_bounds. This reordering allows us
> to improve precision slightly while losing one call to
> __reg_deduce_bounds.
>
> The first patch from Eduard refactors the __reg_deduce_bounds
> subfunctions, the second patch implements the reordering, and the last
> one adds a selftest.
>
> [...]
Here is the summary with links:
- [bpf-next,v3,1/3] bpf: better naming for __reg_deduce_bounds() parts
https://git.kernel.org/bpf/bpf-next/c/879cace97667
- [bpf-next,v3,2/3] bpf: Avoid one round of bounds deduction
https://git.kernel.org/bpf/bpf-next/c/9e5fcb003aec
- [bpf-next,v3,3/3] selftests/bpf: Test case for refinement improvement using 64b bounds
https://git.kernel.org/bpf/bpf-next/c/0a753d8cd61e
You are awesome, thank you!
--
Deet-doot-dot, I am a bot.
https://korg.docs.kernel.org/patchwork/pwbot.html
^ permalink raw reply [flat|nested] 11+ messages in thread