Add cnum64_intersect_linear(), which intersects a cnum64 interval with the set of integers congruent to 'base' modulo 'step', i.e. the points base + step * k. It tightens the interval by rounding its signed minimum up and its signed maximum down to the nearest such point, and returns an empty cnum when no point falls within the interval. The arithmetic is done on the signed bounds [smin, smax]. The line is defined over the integers, while a cnum64 is an arc on the u64 circle, so a u64-modular computation would misplace the line for negative values whenever 'step' does not divide 2^64. Working from the signed bounds keeps the residues consistent, e.g. it can reason about a range like [-9, 3] with step 3. Also add imod() to bpf_verifier.h: a mathematical modulo returning an always-non-negative residue (unlike C's '%', which follows the sign of the dividend). It is used by cnum64_intersect_linear() and by the base/step tracking added in subsequent patches. This is a building block for tracking scalar registers whose value is known to lie on a line base + step * k. Signed-off-by: Eduard Zingerman --- include/linux/bpf_verifier.h | 14 ++++++++++++++ include/linux/cnum.h | 1 + kernel/bpf/cnum.c | 36 ++++++++++++++++++++++++++++++++++++ 3 files changed, 51 insertions(+) diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h index 05e6f091ad94..0422d4a1be01 100644 --- a/include/linux/bpf_verifier.h +++ b/include/linux/bpf_verifier.h @@ -9,6 +9,20 @@ #include /* for MAX_BPF_STACK */ #include #include +#include /* for div_s64_rem() */ + +/* + * Mathematical modulo, the residue of 'v' modulo 'step', normalized to [0, step). + * This differs from C's '%' operator, which truncates the quotient toward zero + * and so returns a remainder with the sign of the dividend (e.g. -1 % 3 == -1, not 2). + */ +static inline u16 imod(s64 v, u16 step) +{ + s32 rem; + + div_s64_rem(v, step, &rem); + return rem < 0 ? rem + step : rem; +} /* Maximum variable offset umax_value permitted when resolving memory accesses. * In practice this is far bigger than any realistic pointer offset; this limit diff --git a/include/linux/cnum.h b/include/linux/cnum.h index ddf4726841e6..49160318adf9 100644 --- a/include/linux/cnum.h +++ b/include/linux/cnum.h @@ -80,5 +80,6 @@ bool cnum64_is_subset(struct cnum64 outer, struct cnum64 inner); struct cnum32 cnum32_from_cnum64(struct cnum64 cnum); struct cnum64 cnum64_cnum32_intersect(struct cnum64 a, struct cnum32 b); +struct cnum64 cnum64_intersect_linear(struct cnum64 in, u16 base, u16 step); #endif /* _LINUX_CNUM_H */ diff --git a/kernel/bpf/cnum.c b/kernel/bpf/cnum.c index 86142cb2aee5..8ec5187d7c75 100644 --- a/kernel/bpf/cnum.c +++ b/kernel/bpf/cnum.c @@ -2,6 +2,7 @@ /* Copyright (c) 2026 Meta Platforms, Inc. and affiliates. */ #include +#include /* for imod() */ #define T 32 #include "cnum_defs.h" @@ -118,3 +119,38 @@ struct cnum64 cnum64_cnum32_intersect(struct cnum64 a, struct cnum32 b) } return t; } + +/* Intersect 'in' with the set of integers defined by equation 'base + step * k'. */ +struct cnum64 cnum64_intersect_linear(struct cnum64 in, u16 base, u16 step) +{ + s64 smin = cnum64_smin(in); + s64 smax = cnum64_smax(in); + s64 lo, hi; + u16 d; + + if (step <= 1 || cnum64_is_empty(in) || cnum64_srange_overflow(in)) + return in; + /* + * Round smin up to the next value congruent to 'base' modulo 'step', + * i.e. increase smin by d = (base - smin) mod step: + * + * |<---- d ---->| + * |-----------|=============|... + * base+step*k smin base+step*(k+1) + */ + d = imod(base - imod(smin, step), step); + if ((u64)smax - (u64)smin < d) + return CNUM64_EMPTY; + lo = smin + d; + /* + * Round smax down to the previous value congruent to 'base' modulo 'step', + * i.e. decrease smax by d = (smax - base) mod step: + * + * |<--- d --->| + * ...|===========|-------------| + * base+step*k smax base+step*(k+1) + */ + d = imod(imod(smax, step) - base, step); + hi = smax - d; + return cnum64_from_srange(lo, hi); +} -- 2.53.0