[PATCH bpf-next 0/2] Simplify min()/max(), contains() and fix normalize() cnum implementation

[PATCH bpf-next 0/2] Simplify min()/max(), contains() and fix normalize() cnum implementation

[Vinicius Sampaio]

This patches simplifies some functions of the cnum implementation:

- smin()/smax()
- contains()
- normalize()

Vinicius Sampaio (2):
  bpf: Simplify cnum contains() and normalize() implementation
  bpf: Avoid redundant min()/max() in cnum signed bounds

 kernel/bpf/cnum_defs.h | 23 ++++++++++-------------
 1 file changed, 10 insertions(+), 13 deletions(-)

-- 
2.54.0

[PATCH bpf-next 1/2] bpf: Simplify cnum contains() and normalize() implementation

[Vinicius Sampaio]

This patch introduces two optimizations one for the normalize() function
and other for the contains() function.

In normalize(), there's no need to compare cnum.base with ST_MAX,
because any cnum with size == UT_MAX represents the full unsigned domain
independently of base, so normalize() can canonicalize all such values
to base 0.

In contains(), bearing in mind that a non-empty cnum represents a
inclusive circular range in the corresponding unsigned integer domain,
membership could be tested by checking whether the distance from the
range base to the queried value is within the range size.

This makes the explicit wrapping and non-wrapping cases in contains()
unnecessary, since:

        v - cnum.base <= cnum.size

is equivalent for both ordinary ranges and ranges that cross the
unsigned wrap boundary.

We've also run some benchmarks to compare the performance of the new
implementation, for example, for empty ranges, overflowing ranges
non-overflowing ranges. We've run the tests with O2 optimization.

normalize() results:

        | Test                    | normalize   | normalize_new |
        | ----------------------- | ----------- | ------------- |
        | normal small range      | 1.254 ns/op | 1.049 ns/op   |
        | full range normalized   | 1.055 ns/op | 1.046 ns/op   |
        | full range nonzero base | 1.053 ns/op | 1.055 ns/op   |
        | empty                   | 1.054 ns/op | 1.059 ns/op   |
        | signed max full range   | 1.051 ns/op | 1.049 ns/op   |
        | max base singleton      | 1.253 ns/op | 1.045 ns/op   |

contains() results:

        | Test                 | contains    | contains_new |
        | -------------------- | ----------- | ------------ |
        | empty                | 1.511 ns/op | 1.479 ns/op  |
        | non-overflow inside  | 1.156 ns/op | 1.270 ns/op  |
        | non-overflow outside | 1.053 ns/op | 1.258 ns/op  |
        | overflow high side   | 1.469 ns/op | 1.257 ns/op  |
        | overflow low side    | 1.469 ns/op | 1.270 ns/op  |
        | overflow outside     | 1.478 ns/op | 1.256 ns/op  |
        | singleton inside     | 1.049 ns/op | 1.256 ns/op  |
        | singleton outside    | 1.051 ns/op | 1.254 ns/op  |
        | full range           | 1.053 ns/op | 1.256 ns/op  |

You can check the full implementation of theses tests on this repository:

        https://github.com/OpenSourceVerif/open-verified-artifacts/tree/cnum-refactor-verif/cnum/benches

Lean4 proofs showing that the new implementation preserves soundness of
these operations are available at:

        https://github.com/OpenSourceVerif/open-verified-artifacts/tree/cnum-refactor-verif/cnum/lean

Co-developed-by: Yazhou Tang <tangyazhou518@outlook.com>
Signed-off-by: Yazhou Tang <tangyazhou518@outlook.com>
Co-developed-by: Shenghao Yuan <shenghaoyuan0928@163.com>
Signed-off-by: Shenghao Yuan <shenghaoyuan0928@163.com>
Signed-off-by: Vinicius Sampaio <vldsampaio@pm.me>
---
 kernel/bpf/cnum_defs.h | 9 ++-------
 1 file changed, 2 insertions(+), 7 deletions(-)

diff --git a/kernel/bpf/cnum_defs.h b/kernel/bpf/cnum_defs.h
index a90e317e3578..25649b740560 100644
--- a/kernel/bpf/cnum_defs.h
+++ b/kernel/bpf/cnum_defs.h
@@ -181,7 +181,7 @@ void FN(intersect_with_srange)(struct cnum_t *dst, st min, st max)
 
 static inline struct cnum_t FN(normalize)(struct cnum_t cnum)
 {
-	if (cnum.size == UT_MAX && cnum.base != 0 && cnum.base != (ut)ST_MAX)
+	if (cnum.size == UT_MAX && cnum.base != 0)
 		cnum.base = 0;
 	return cnum;
 }
@@ -210,12 +210,7 @@ bool FN(is_empty)(struct cnum_t cnum)
 
 bool FN(contains)(struct cnum_t cnum, ut v)
 {
-	if (FN(is_empty)(cnum))
-		return false;
-	if (FN(urange_overflow)(cnum))
-		return v >= cnum.base || v <= (ut)cnum.base + cnum.size;
-	else
-		return v >= cnum.base && v <= (ut)cnum.base + cnum.size;
+	return !FN(is_empty)(cnum) && v - cnum.base <= cnum.size;
 }
 
 bool FN(is_const)(struct cnum_t cnum)
-- 
2.54.0

[PATCH bpf-next 2/2] bpf: Avoid redundant min()/max() in cnum signed bounds

[Vinicius Sampaio]

This patch simplifies the smin() and smax() calculation by removing the
integer min and max calculation on the non-overflowing branch. This is a
valid simplification because when the arc does not cross the signed
ST_MAX/ST_MIN boundary, the signed order of the endpoints is preserved,
so base is the signed minimum and base + size is the signed maximum.
Therefore, the min()/max() calls are redundant.

We've also run benchmarks to compare the performance of this change.
With O2 optimization we have:

smin() results:

        | Test                     | smin        | smin_new    |
        | ------------------------ | ----------- | ----------- |
        | empty                    | 1.866 ns/op | 1.477 ns/op |
        | positive range           | 1.870 ns/op | 1.248 ns/op |
        | negative range           | 1.657 ns/op | 1.246 ns/op |
        | cross zero               | 1.870 ns/op | 1.660 ns/op |
        | signed overflow boundary | 1.463 ns/op | 1.049 ns/op |
        | signed overflow range    | 1.519 ns/op | 1.050 ns/op |
        | unsigned overflow range  | 1.883 ns/op | 1.669 ns/op |
        | full range               | 1.555 ns/op | 1.049 ns/op |

smax() results:

        | Test                     | smax        | smax_new    |
        | ------------------------ | ----------- | ----------- |
        | empty                    | 1.462 ns/op | 1.456 ns/op |
        | positive range           | 1.250 ns/op | 1.249 ns/op |
        | negative range           | 1.259 ns/op | 1.297 ns/op |
        | cross zero               | 1.471 ns/op | 1.475 ns/op |
        | signed overflow boundary | 1.056 ns/op | 1.260 ns/op |
        | signed overflow range    | 1.049 ns/op | 1.259 ns/op |
        | unsigned overflow range  | 1.470 ns/op | 1.477 ns/op |
        | full range               | 1.072 ns/op | 1.263 ns/op |

You can check the full implementation of these tests on this repository:

        https://github.com/OpenSourceVerif/open-verified-artifacts/tree/cnum-refactor-verif/cnum/benches

Lean4 proofs showing that the new implementation preserves soundness of
these operations are available at:

        https://github.com/OpenSourceVerif/open-verified-artifacts/tree/cnum-refactor-verif/cnum/lean

Co-developed-by: Yazhou Tang <tangyazhou518@outlook.com>
Signed-off-by: Yazhou Tang <tangyazhou518@outlook.com>
Co-developed-by: Shenghao Yuan <shenghaoyuan0928@163.com>
Signed-off-by: Shenghao Yuan <shenghaoyuan0928@163.com>
Signed-off-by: Vinicius Sampaio <vldsampaio@pm.me>
---
 kernel/bpf/cnum_defs.h | 14 ++++++++------
 1 file changed, 8 insertions(+), 6 deletions(-)

diff --git a/kernel/bpf/cnum_defs.h b/kernel/bpf/cnum_defs.h
index 25649b740560..456366408353 100644
--- a/kernel/bpf/cnum_defs.h
+++ b/kernel/bpf/cnum_defs.h
@@ -44,6 +44,9 @@ static inline bool FN(urange_overflow)(struct cnum_t cnum)
  * cnum{T}_umin / cnum{T}_umax query an unsigned range represented by this cnum.
  * If cnum represents a range crossing the UT_MAX/0 boundary, the unbound range
  * [0..UT_MAX] is returned.
+ *
+ * The empty cnum doesn't produce any meaningful value, so you should avoid
+ * calling cnum{T}_umin / cnum{T}_umax with it.
  */
 ut FN(umin)(struct cnum_t cnum)
 {
@@ -67,19 +70,18 @@ static inline bool FN(srange_overflow)(struct cnum_t cnum)
  * cnum{T}_smin / cnum{T}_smax query a signed range represented by this cnum.
  * If cnum represents a range crossing the ST_MAX/ST_MIN boundary, the unbound range
  * [ST_MIN..ST_MAX] is returned.
+ *
+ * The empty cnum doesn't produce any meaningful value, so you should avoid
+ * calling cnum{T}_smin / cnum{T}_smax with it.
  */
 st FN(smin)(struct cnum_t cnum)
 {
-	return FN(srange_overflow)(cnum)
-	       ? ST_MIN
-	       : min((st)cnum.base, (st)(cnum.base + cnum.size));
+	return FN(srange_overflow)(cnum) ? ST_MIN : (st)cnum.base;
 }
 
 st FN(smax)(struct cnum_t cnum)
 {
-	return FN(srange_overflow)(cnum)
-	       ? ST_MAX
-	       : max((st)cnum.base, (st)(cnum.base + cnum.size));
+	return FN(srange_overflow)(cnum) ? ST_MAX : (st)(cnum.base + cnum.size);
 }
 
 /*
-- 
2.54.0

Re: [PATCH bpf-next 1/2] bpf: Simplify cnum contains() and normalize() implementation

[Shung-Hsi Yu]

On Tue, Jul 28, 2026 at 01:56:58AM +0000, Vinicius Sampaio wrote:
> This patch introduces two optimizations one for the normalize() function
> and other for the contains() function.

Nit: is there a reason these two optimizations need to land as a single
commit?

> In normalize(), there's no need to compare cnum.base with ST_MAX,
> because any cnum with size == UT_MAX represents the full unsigned domain
> independently of base, so normalize() can canonicalize all such values
> to base 0.
> 
> In contains(), bearing in mind that a non-empty cnum represents a
> inclusive circular range in the corresponding unsigned integer domain,
> membership could be tested by checking whether the distance from the
> range base to the queried value is within the range size.
> 
> This makes the explicit wrapping and non-wrapping cases in contains()
> unnecessary, since:
> 
>         v - cnum.base <= cnum.size
> 
> is equivalent for both ordinary ranges and ranges that cross the
> unsigned wrap boundary.
[...]
> @@ -181,7 +181,7 @@ void FN(intersect_with_srange)(struct cnum_t *dst, st min, st max)
>  
>  static inline struct cnum_t FN(normalize)(struct cnum_t cnum)
>  {
> -	if (cnum.size == UT_MAX && cnum.base != 0 && cnum.base != (ut)ST_MAX)
> +	if (cnum.size == UT_MAX && cnum.base != 0)
>  		cnum.base = 0;

Seems right, or at least I could see what semantic `base == ST_MAX` is
encoding. And normalize does not deal with the empty semantic anyway[1].
Could we go even further and also drop the `cnum.base != 0`, just
relying on the `cnum.size == UT_MAX` guard solely?

>  	return cnum;
>  }
> @@ -210,12 +210,7 @@ bool FN(is_empty)(struct cnum_t cnum)
>  
>  bool FN(contains)(struct cnum_t cnum, ut v)
>  {
> -	if (FN(is_empty)(cnum))
> -		return false;
> -	if (FN(urange_overflow)(cnum))
> -		return v >= cnum.base || v <= (ut)cnum.base + cnum.size;
> -	else
> -		return v >= cnum.base && v <= (ut)cnum.base + cnum.size;
> +	return !FN(is_empty)(cnum) && v - cnum.base <= cnum.size;
>  }

Make sense, with `v - cnum.base` we are pivoting to a cnum where

  { .base = 0, .size = cnum.size }

If `v - cnum.base` is within the pivoted cnum, then `v` should be in the
original cnum as well.

Acked-by: Shung-Hsi Yu <shung-hsi.yu@suse.com>

1: https://lore.kernel.org/bpf/7a5c9c3e8ef2cb86b7ae38fb4593e7337e9962c0.camel@gmail.com/

Re: [PATCH bpf-next 2/2] bpf: Avoid redundant min()/max() in cnum signed bounds

[Shung-Hsi Yu]

On Tue, Jul 28, 2026 at 01:57:18AM +0000, Vinicius Sampaio wrote:
> This patch simplifies the smin() and smax() calculation by removing the
> integer min and max calculation on the non-overflowing branch. This is a
> valid simplification because when the arc does not cross the signed
> ST_MAX/ST_MIN boundary, the signed order of the endpoints is preserved,
> so base is the signed minimum and base + size is the signed maximum.
> Therefore, the min()/max() calls are redundant.
[...]
> --- a/kernel/bpf/cnum_defs.h
> +++ b/kernel/bpf/cnum_defs.h
> @@ -44,6 +44,9 @@ static inline bool FN(urange_overflow)(struct cnum_t cnum)
>   * cnum{T}_umin / cnum{T}_umax query an unsigned range represented by this cnum.
>   * If cnum represents a range crossing the UT_MAX/0 boundary, the unbound range
>   * [0..UT_MAX] is returned.
> + *
> + * The empty cnum doesn't produce any meaningful value, so you should avoid
> + * calling cnum{T}_umin / cnum{T}_umax with it.
>   */
>  ut FN(umin)(struct cnum_t cnum)
>  {
> @@ -67,19 +70,18 @@ static inline bool FN(srange_overflow)(struct cnum_t cnum)
>   * cnum{T}_smin / cnum{T}_smax query a signed range represented by this cnum.
>   * If cnum represents a range crossing the ST_MAX/ST_MIN boundary, the unbound range
>   * [ST_MIN..ST_MAX] is returned.
> + *
> + * The empty cnum doesn't produce any meaningful value, so you should avoid
> + * calling cnum{T}_smin / cnum{T}_smax with it.

Nit: if we are adding these it would perhaps be helpful to add similar
comment to {u,s}range_overflow as well. AFAICT
{u,s}{min,max,range_overflow} should be the only cnum function that is
not expected to take on an empty cnum.

Thought I'd prefer something along the lines of

  caller should ensure !is_empty(cnum) holds when calling

>   */
>  st FN(smin)(struct cnum_t cnum)
>  {
> -	return FN(srange_overflow)(cnum)
> -	       ? ST_MIN
> -	       : min((st)cnum.base, (st)(cnum.base + cnum.size));
> +	return FN(srange_overflow)(cnum) ? ST_MIN : (st)cnum.base;
>  }
>  
>  st FN(smax)(struct cnum_t cnum)
>  {
> -	return FN(srange_overflow)(cnum)
> -	       ? ST_MAX
> -	       : max((st)cnum.base, (st)(cnum.base + cnum.size));
> +	return FN(srange_overflow)(cnum) ? ST_MAX : (st)(cnum.base + cnum.size);
>  }

Acked-by: Shung-Hsi Yu <shung-hsi.yu@suse.com>

Re: [PATCH bpf-next 1/2] bpf: Simplify cnum contains() and normalize() implementation

[Vinicius Sampaio]

> Nit: is there a reason these two optimizations need to land as a single
> commit?

No. I will split them into separate commits in v2.

> Could we go even further and also drop the `cnum.base != 0`, just
> relying on the `cnum.size == UT_MAX` guard solely?

Yes, assigning zero again is harmless. I will simplify this in v2.

Thanks for the review and the Acked-by.

Re: [PATCH bpf-next 2/2] bpf: Avoid redundant min()/max() in cnum signed bounds

[Vinicius Sampaio]

> Nit: if we are adding these it would perhaps be helpful to add similar
> comment to {u,s}range_overflow as well. AFAICT
> {u,s}{min,max,range_overflow} should be the only cnum function that is
> not expected to take on an empty cnum.
> 
> Thought I'd prefer something along the lines of
> 
>   caller should ensure !is_empty(cnum) holds when calling

I'll change the comment to match what you've suggested and add it to
{u,s}range_overflow then. Thanks for the review and Acked-by.