| Age | Commit message (Collapse) | Author |
|---|
|
The QTG _DSM expects read and write latencies in picoseconds, as
specified in CXL 3.0, Table 9-30.
The code base originally kept the latencies passed to the QTG _DSM in
picoseconds in effect. Commit 51293c565cf4 ("cxl: Fix incorrect region
perf data calculation") normalized CDAT and host bridge latencies to
nanoseconds, but did not add a conversion back to picoseconds when
constructing the _DSM input. Firmware can therefore select QTG IDs using
understated latencies.
Convert the latencies to picoseconds when constructing the _DSM input
package. Multiply in 64 bits and reject latencies that cannot fit in the
DWORD inputs defined by the specification.
Fixes: 51293c565cf4 ("cxl: Fix incorrect region perf data calculation")
Cc: stable@vger.kernel.org
Signed-off-by: Koichiro Den <den@valinux.co.jp>
Reviewed-by: Alison Schofield <alison.schofield@intel.com>
Reviewed-by: Dave Jiang <dave.jiang@intel.com>
Link: https://patch.msgid.link/20261009045452.1107921-4-den@valinux.co.jp
Signed-off-by: Dave Jiang <dave.jiang@intel.com>
|
|
cxl_pci_get_latency() derives bandwidth from the per-lane speed returned
by pcie_link_speed_mbps(), ignoring the negotiated link width. This
overestimates the FlitLatency contribution for multi-lane links.
Sections 2.11.3 and 2.11.4 of the Intel CXL Memory Device Software Guide
describe the link bandwidth as the product of the negotiated speed and
width.
Replace pcie_link_speed_mbps() with pcie_link_bandwidth_mbps() and
migrate both CXL callers (the only users of the API). The new helper
obtains speed and width from a single Link Status read. The CXL
bandwidth calculation no longer needs a separate width read and
multiplication.
While at it, make error handling more robust by converting PCI config
read errors to negative errno values and checking for zero bandwidth
before calculating latency.
Fixes: 4d07a05397c8 ("cxl: Calculate and store PCI link latency for the downstream ports")
Cc: stable@vger.kernel.org
Signed-off-by: Koichiro Den <den@valinux.co.jp>
Reviewed-by: Alison Schofield <alison.schofield@intel.com>
Acked-by: Bjorn Helgaas <bhelgaas@google.com> # pci/pci.c
Reviewed-by: Dave Jiang <dave.jiang@intel.com>
Link: https://patch.msgid.link/20261009045452.1107921-3-den@valinux.co.jp
Signed-off-by: Dave Jiang <dave.jiang@intel.com>
|
|
Commit 51293c565cf4 ("cxl: Fix incorrect region perf data calculation")
converted CDAT latencies to nanoseconds and removed the conversion in
cxl_region_perf_data_calculate(), but left PCIe link latencies in
picoseconds.
This inflates the FlitLatency contribution to region and node latencies
by a factor of 1000, exposing incorrect values in sysfs. The resulting
abstract distances can incorrectly reverse the memory tier ordering of
nodes.
Convert the FlitLatency contribution to nanoseconds before adding it to
the access coordinates, rounding up as cdat_normalize() does.
Fixes: 51293c565cf4 ("cxl: Fix incorrect region perf data calculation")
Cc: stable@vger.kernel.org
Signed-off-by: Koichiro Den <den@valinux.co.jp>
Reviewed-by: Alison Schofield <alison.schofield@intel.com>
Reviewed-by: Dave Jiang <dave.jiang@intel.com>
Link: https://patch.msgid.link/20261009045452.1107921-2-den@valinux.co.jp
Signed-off-by: Dave Jiang <dave.jiang@intel.com>
|
|
update_gpf_port_dvsec() rebuilds the phase control register from just
the timeout base and scale, so the rest of the register is cleared by
the write. The other bits are reserved today and nothing is lost, but
the full-register rewrite would clobber any field the spec defines
there later.
Read-modify-write the register and change only the two timeout
fields.
Fixes: a52b6a2c1c99 ("cxl/pci: Support Global Persistent Flush (GPF)")
Assisted-by: LLM
Signed-off-by: Guixin Liu <kanie@linux.alibaba.com>
Reviewed-by: Dave Jiang <dave.jiang@intel.com>
Reviewed-by: Alison Schofield <alison.schofield@intel.com>
Link: https://patch.msgid.link/20261008034619.28059-4-kanie@linux.alibaba.com
Signed-off-by: Dave Jiang <dave.jiang@intel.com>
|
|
cxl_gpf_port_setup() caches the Port GPF DVSEC offset in the dport
before programming the phase timeouts, and ignores the return value
of both update_gpf_port_dvsec() calls: the function always reports
success.
A failing config write is therefore not only silent, it is also
permanent: the timeouts stay at the hardware defaults instead of the
maximum flush window the kernel is asking for, and the cached offset
keeps any later endpoint attach from retrying the update.
Propagate the errors and cache the offset only after both phases are
programmed, so the next endpoint attach retries the setup.
Fixes: 6af941db6a60 ("cxl/pci: Update Port GPF timeout only when the first EP attaching")
Cc: stable@vger.kernel.org
Assisted-by: LLM
Signed-off-by: Guixin Liu <kanie@linux.alibaba.com>
Reviewed-by: Jonathan Cameron <jonathan.cameron@oss.qualcomm.com>
Reviewed-by: Dave Jiang <dave.jiang@intel.com>
Reviewed-by: Alison Schofield <alison.schofield@intel.com>
Link: https://patch.msgid.link/20261008034619.28059-3-kanie@linux.alibaba.com
Signed-off-by: Dave Jiang <dave.jiang@intel.com>
|
|
cxl_gpf_get_dvsec() picks between the Port and the Device GPF DVSEC
from the PCIe type of the given device, and only a plain endpoint
counts as a device. A restricted CXL device is an endpoint too, but
it falls into the port case and is probed for the Port GPF DVSEC
instead of the Device GPF DVSEC.
On an RCD, dirty shutdown tracking therefore never arms: the DVSEC
lookup in cxl_nvdimm_arm_dirty_shutdown_tracking() fails, the dirty
shutdown count stays invalid, and the warning complains about a
missing Port GPF DVSEC on a device.
Treat restricted endpoints as devices.
Fixes: 36aace15d9bd ("cxl/pci: Drop the parameter is_port of cxl_gpf_get_dvsec()")
Cc: stable@vger.kernel.org
Assisted-by: LLM
Signed-off-by: Guixin Liu <kanie@linux.alibaba.com>
Reviewed-by: Jonathan Cameron <jonathan.cameron@oss.qualcomm.com>
Reviewed-by: Dave Jiang <dave.jiang@intel.com>
Reviewed-by: Alison Schofield <alison.schofield@intel.com>
Link: https://patch.msgid.link/20261008034619.28059-2-kanie@linux.alibaba.com
Signed-off-by: Dave Jiang <dave.jiang@intel.com>
|
|
devm_cxl_enumerate_ports() and add_port_attach_ep() look up or create a
dport under its port's device lock, drop the lock, then pass the dport
to cxl_add_ep(). add_ep() reads dport->port before taking the lock, and
cxl_gpf_port_setup() reads and writes the dport with no lock held.
A concurrent cxl_detach_ep() for another memdev below the same port can
free the dport in that window: it calls del_dports() under the port lock
when the last endpoint leaves. The enumerating memdev then dereferences
freed memory.
Attach the endpoint and set up GPF while the port lock from the lookup
is still held. Make add_ep() assert that lock instead of taking it.
Under the lock, a dport found in port->dports is still live, since
removal erases it from the xarray before freeing it.
[ dj: Added kdoc update from Alison. ]
Fixes: de516b40116e ("cxl/port: Record dport in endpoint references")
Reported-by: Li Ming <ming.li@zohomail.com>
Closes: https://lore.kernel.org/linux-cxl/0c68324c-cfc7-46b2-9344-24ae40e88923@zohomail.com/
Assisted-by: LLM
Reviewed-by: Li Ming <ming.li@zohomail.com>
Reviewed-by: Alison Schofield <alison.schofield@intel.com>
Link: https://patch.msgid.link/20261001154744.1095902-4-dave.jiang@intel.com
Signed-off-by: Dave Jiang <dave.jiang@intel.com>
|
|
Callers of cxl_pci_find_port() and cxl_mem_find_port() can be handed a
'struct cxl_dport' that is already freed, and all four dereference it
without the lock that would prevent that.
A dport is kzalloc()'d into a devres group on its host device, so it dies
when that host unbinds. The host is &port->dev for a switch port and
port->uport_dev for the root port.
Both helpers return the dport through an output parameter. The caller's
port reference pins struct cxl_port, not the dport allocation, and the
lookup itself is a bare xa_load() under no lock.
Add cxl_port_dport_host() to name the device that pins a dport, and
cxl_pci_find_dport() / cxl_mem_find_dport() to look one up with that
device's lock held and asserted. Convert the four callers to use them and
bail if the dport is gone. cxl_port_add_dport() already follows this rule.
cxl_mem_probe() chose its endpoint devm host from dport->rch, which meant
dereferencing the dport before taking any lock. Use cxl_port_dport_host():
rch dports only ever land on the root port, so it selects the same device
without needing the dport.
With every caller converted, the dport output parameter of
cxl_pci_find_port() and cxl_mem_find_port() is unused. Drop it.
Fixes: 733b57f262b0 ("cxl/pci: Early setup RCH dport component registers from RCRB")
Assisted-by: LLM
Reviewed-by: Li Ming <ming.li@zohomail.com>
Reviewed-by: Alison Schofield <alison.schofield@intel.com>
Link: https://patch.msgid.link/20261001154744.1095902-3-dave.jiang@intel.com
Signed-off-by: Dave Jiang <dave.jiang@intel.com>
|
|
Switch decoders cache dport pointers in cxlsd->target[], and nothing
clears them when a dport is freed. Readers then dereference freed memory.
KASAN caught it under a cxl_test load/unload loop with concurrent sysfs
reads (abbreviated).
Clear the matching slots from cxl_dport_remove(), walking the port's
decoders the way cxl_port_update_decoder_targets() does on the add side.
Scan all nr_targets slots, the target[] allocation size, and clear every
hit.
Fixes: 8330671c57c7 ("cxl: Add helper to delete dport")
Cc: stable@vger.kernel.org
Assisted-by: LLM
Reviewed-by: Jonathan Cameron <jonathan.cameron@oss.qualcomm.com>
Reviewed-by: Li Ming <ming.li@zohomail.com>
Reviewed-by: Gregory Price (Meta) <gourry@gourry.net>
Reviewed-by: Alison Schofield <alison.schofield@intel.com>
Link: https://patch.msgid.link/20261001154744.1095902-2-dave.jiang@intel.com
Signed-off-by: Dave Jiang <dave.jiang@intel.com>
|
|
panthor_group_destroy() checks the GROUP_REGISTERED mark and then calls
xa_erase() without holding the xarray lock across both. If the handle is
destroyed by another thread in between, and a concurrent GROUP_CREATE
reuses the freed ID, the first destroy erases and releases the new,
still-initializing group, leading to a use-after-free in
panthor_group_create().
Do the mark check and erase atomically under xa_lock().
Fixes: eec7e23d848d ("drm/panthor: Prevent potential UAF in group creation")
Assisted-by: Claude:claude-opus-5.5
Reviewed-by: Boris Brezillon <boris.brezillon@collabora.com>
Reviewed-by: Liviu Dudau <liviu.dudau@arm.com>
Cc: stable@vger.kernel.org
Signed-off-by: Osama Abdelkader <osama.abdelkader@gmail.com>
Reviewed-by: Steven Price <steven.price@arm.com>
Signed-off-by: Liviu Dudau <liviu.dudau@arm.com>
Link: https://patch.msgid.link/20261008100935.3059587-1-osama.abdelkader@gmail.com
|
|
With CHECK_DTBS enabled, Kbuild appends a schema validation command to
the fdtoverlay command saved in a composite DTB's .cmd file. When DTB
decomposition is requested, process_dtb() treats every word after -i as
an input file, including the semicolon and the validator arguments.
FIT generation then fails with FileNotFoundError while opening or
checking the size of those words as files.
Limit the input list to the fdtoverlay command before extracting its
arguments. This preserves the base DTB and overlay order and ignores
the subsequent schema validation command.
Fixes: 17c31aded9a1 ("scripts/make_fit: Support decomposing DTBs")
Assisted-by: LLM
Signed-off-by: Ting-Han Hou <ue081723@gmail.com>
Reviewed-by: Simon Glass <sjg@chromium.org>
Link: https://patch.msgid.link/CA+NtrhQBK8uW32qO3dXxVxO1GSN-0EJfyJ16tnyx0o52T17WtQ@mail.gmail.com
Signed-off-by: Nathan Chancellor <nathan@kernel.org>
|
|
The BrokenPipeError handler in run-clang-tools.py calls os.open() and
os.dup2() without importing os. If this handler is reached, it raises
NameError instead of redirecting stdout and exiting with status 1.
Import os so the handler can work as intended.
Fixes: 87c7ee67deb7 ("scripts: handle BrokenPipeError for python scripts")
Assisted-by: LLM
Signed-off-by: Ting-Han Hou <ue081723@gmail.com>
Link: https://patch.msgid.link/20261009175836.2277-1-ue081723@gmail.com
Signed-off-by: Nathan Chancellor <nathan@kernel.org>
|
|
sym_get_near_range_bound() is meant to check whether the given value is
outside of the active range of an int/hex symbol, and is called with the
symbol's current value from sym_calc_value() and with the default value
from sym_get_string_default().
Since commit 9b8719973ee2 ("kconfig: use unsigned integers for hex range
checks") it ignores its value argument and uses the current value of the
symbol (via sym_get_range_val()) instead. As a result, an out-of-range
default is no longer clamped in sym_get_string_default(), and
savedefconfig writes out values that are equal to the effective default
again, for example CONFIG_A=4 for:
config A
int "a"
range 1 4
default 8
The existing savedefconfig_range test did not catch this because it only
covers symbols without a prompt.
Parse the value argument again, and add a test case for a symbol with a
prompt.
Found while fuzzing Kconfig input with ASan/UBSan.
Fixes: 9b8719973ee2 ("kconfig: use unsigned integers for hex range checks")
Assisted-by: Claude:claude-opus-5-5
Signed-off-by: Leizhen Zhang <lzsx618@gmail.com>
Tested-by: Julian Braha <julianbraha@gmail.com>
Reviewed-by: Julian Braha <julianbraha@gmail.com>
Link: https://patch.msgid.link/20261008164540.3686383-1-lzsx618@gmail.com
Signed-off-by: Nathan Chancellor <nathan@kernel.org>
|
|
If a choice is visible but none of its choice values is, conf_choice()
counts cnt == 0 visible values and finds no default. When the choice has
to be asked, e.g. because a new symbol was added to the same menu
(oldconfig, syncconfig) or because stdin is at EOF (oldaskconfig), the
loop that maps the answer to a menu entry never finds one and the
while (1) loop repeats forever, printing "choice[1-0?]: 0" each time.
This happens in the tree for s390 when the compiler supports none of the
-march=z* options (e.g. a non-s390 host compiler), so that all values of
the "Processor type" choice are invisible:
$ make ARCH=s390 defconfig
$ sed -i '/^CONFIG_NR_CPUS=/d' .config
$ make ARCH=s390 oldconfig # hangs
Before the removal of tristate choice support, conf_choice() returned
early in this case. Do the same when there is no visible choice value.
Found by fuzzing Kconfig input with ASan/UBSan.
Fixes: fde192511bdb ("kconfig: remove tristate choice support")
Assisted-by: Claude:claude-opus-5-5 libFuzzer
Signed-off-by: Leizhen Zhang <lzsx618@gmail.com>
Reviewed-by: Julian Braha <julianbraha@gmail.com>
Tested-by: Julian Braha <julianbraha@gmail.com>
Link: https://patch.msgid.link/20261008164521.3684735-1-lzsx618@gmail.com
Signed-off-by: Nathan Chancellor <nathan@kernel.org>
|
|
'keys' was removed from 'dialog_textbox' in:
commit e14f1242a8be ("kconfig: menuconfig: simplify global jump key assignment")
but the comment referencing it was never removed.
Let's cleanup this stale comment.
Signed-off-by: Julian Braha <julianbraha@gmail.com>
Reviewed-by: Nicolas Schier <n.schier@fritz.com>
Link: https://patch.msgid.link/20261009094617.17322-1-julianbraha@gmail.com
Signed-off-by: Nathan Chancellor <nathan@kernel.org>
|
|
Eduard Zingerman says:
====================
bpf: use scalar evolution to widen bounded loops
This series implements the scalar evolution (SCEV) technique for
verification of loops.
Scalar evolution is a static analysis technique that infers algebraic
expressions describing how variables change within a loop body.
These expressions can then be used to estimate the number of loop body
executions. This estimate can be used to represent induction variables
as ranges instead of enumerating each possible value.
For example, the following loop:
for (r0 = 0; r0 < 10; r0++) {
...
}
would now be verified with the assumption that r0 is a scalar value
in the range [0..9] within its body.
See the following patches for a more technical overview:
- "bpf: compute scalar evolution expressions for loops"
- "bpf: use SCEV to widen bounded loops"
The series can be viewed as consisting of the following parts:
- Preparatory patches fixing and extending liveness analysis and
adding utility functions. The liveness changes collect stack access
effects and register dependencies, including:
- "bpf: fix arg_track_xfer() for atomic stack spills and fills"
- "bpf: derive global subprog stack liveness from BTF signatures"
- "bpf: compute parameters liveness in bpf_compute_live_registers()"
- Patches relaxing the verifier's current restrictions on accessing
memory via varying offset pointers, specifically:
- "bpf: allow subrange relations for PTR_TO_STACK in regsafe()"
- "bpf: representation for intervals with steps"
- "bpf: varying offset access support for PTR_TO_BTF_ID pointers"
- Patches to compute the immediate dominator tree and loop hierarchy.
- Patches implementing scalar evolution and integrating it with
the main verification pass:
- "bpf: allow precision backtracking between overlapping checkpoints"
- "bpf: compute scalar evolution expressions for loops"
- "bpf: use SCEV to widen bounded loops"
- "bpf: avoid widening registers that hinder exact stack-slot tracking"
- Tests and test harness updates.
Literature
==========
- "Symbolic Evaluation of Chains of Recurrences for Loop Optimization"
Robert A. van Engelen, 2000
- "The CR# Algebra and its Application in Loop Analysis and Optimization"
Robert A. van Engelen, 2004
Supported patterns
==================
As scalar evolution analysis attempts to infer recurring relationships
from algebraic expressions describing loop variables, there are some
limitations on what can be expressed.
Below is a list of patterns that are expected to work with the current
implementation. The examples are pseudo-code for the indicated BPF
instruction shapes.
Loop widening currently requires allow_uninit_stack, the verifier mode
that permits reading uninitialized stack bytes. This requirement applies
even to loops that use only registers. Without it, the verifier uses
its existing iteration-by-iteration checking.
1. Counted loops, including decreasing counters:
u64 i = 0;
do { i += 1; } while (i < 10);
u64 j = 3;
do { j += -1; } while (j != 0);
Header ranges are i in [0,9] and j in [1,3].
Pre-condition loops, such as while (i < 10) { i += 1; },
are also supported. The counter can reside in a register or a fixed
8-byte frame-pointer spill.
2. Strided accesses into a map value:
/* bytes is a map-value array with at least 16 bytes. */
u64 i = 0, off = 0;
do {
bytes[off] = 1;
i += 1;
off += 2;
} while (i < 8);
At the header, off is in [0,14] with step 2. The byte store stays
within the map value even though i and off are tracked separately.
3. A nonconstant entry value with a separate counted induction variable:
u64 x = bpf_get_prandom_u32() & 6; // {0,2,4,6}
u64 i = 0;
do { x += 6; i += 1; } while (i < 3);
The counter i supplies the bound. At the header, x widens to [0,18]
with step 2, retaining the alignment common to its entry values and
its slope; x itself need not start at a constant.
4. Conditional assignment from an invariant value:
u64 x = 5;
for (u64 i = 0; i < 3; i += 1)
if (i == 1) x = 10;
return x;
Widening joins the pre-loop value 5 with the assigned value 10,
giving x in [5,10] both inside and after the loop.
5. Early exits in addition to the counted backedge:
u64 i = 0;
do {
if (bpf_get_prandom_u32() == 0) break;
i += 1;
} while (i != 3);
The counter still bounds the loop. An additional exit reduces the
available lower-bound information; it does not by itself prevent
widening.
6. Array accesses through different memory types:
Bounded varying offsets are supported for arrays in BTF-typed
objects, stack memory, map values and keys, packet data and
metadata, and memory buffers. The usual bounds, alignment and
access restrictions still apply.
For stack arrays indexed by a widened loop counter, only byte and
half-word accesses are supported; see limitation 5 below.
For an array in a BTF-typed object:
struct inner { int a, b; };
struct object { struct inner arr[8]; };
/* o points to a live, non-NULL BTF-typed struct object. */
u64 i = bpf_get_prandom_u32() & 7;
value = o->arr[i].b;
The 4-byte load has offsets 4 + 8*i, i in [0,7]. Bounds keep
accesses within arr; base and step 8 ensure that each possible
offset selects member b. Such accesses also work without a loop.
7. Nested loops with separate counters:
u64 i = 0;
do {
u64 j = 0;
do {
/* body */
j += 1;
} while (j < 3);
i += 1;
} while (i < 4);
Both loops can be widened: i is in [0,3] at the outer header,
and j is in [0,2] at the inner header. The inner counter is reset
on each outer iteration; i is unchanged by the inner loop.
8. Incrementing and comparing a pointer directly:
/* bytes is a map-value array with at least 8 bytes. */
u8 *p = bytes, *end = bytes + 8;
do {
*p = 1;
p++;
} while (p != end);
The initial pointer and fixed end pointer give eight iterations,
without a separate integer counter. At the loop header, p ranges
from bytes to bytes + 7, so each byte store stays within the array.
Deriving the iteration count requires the compared pointers to have
a provable common memory origin.
9. A loop bounded by an exit other than the latch:
u64 i = 0, len = 14;
do {
if (i == len)
break;
use(i);
i += 1;
} while (i != 64);
Every exit condition dominating the latch bounds the iteration
count; the smallest bound wins. Here i is in [0,14] at the header,
not [0,63], so use(i) sees the range established by the break.
Limitations
===========
Patterns that lose precision after widening
-------------------------------------------
Widening can lose information that the verifier gets by checking
each iteration separately. For example:
r7 = 5;
for (r6 = 0; r6 < 3; r6++)
if (r6 == 1)
r7 = 10;
if (r7 != 10)
invalid_stack_read();
R7 is always 10 at the real exit, but is represented as [5, 10] at
loop entry and after the loop. The verifier therefore cannot exclude
the invalid read and rejects this otherwise safe program.
It would be hard to avoid this limitation.
The same issue affects correlated linear counters at loop exit:
u64 i = 0, off = 0;
while (i < 8) {
i++;
off += 2;
}
if (off != 16)
invalid_stack_read();
Enumeration establishes off == 16. Widening tracks i and off
independently, and the exit check on i does not reconstruct off's exact
final value. This can be lifted after analysis adjustments.
Patterns not widened yet
------------------------
If one of the variables modified in the loop cannot be widened, the
verifier checks each iteration instead. Examples include:
1. 32-bit recurrences and comparisons:
for (u32 i = 0; i < 8; i++) // ALU32 / JMP32
use(i);
Only 64-bit arithmetic and comparisons are supported.
This limitation will be lifted.
2. Non-linear updates:
for (u64 i = 1; i < 16; i *= 2) // non-linear recurrence
use(i);
Recognition is currently limited to simple additive recurrences.
Literature describes a way to represent this, but it is not
considered a priority at the moment.
3. A controlling counter or bound that is not constant at loop entry:
u64 limit = unknown_in_range(1, 8);
for (u64 i = 0; i < limit; i++)
use(i);
u64 i = unknown_in_range(0, 7);
while (i < 8)
i++;
Both loops have finite bounds, but iteration-count evaluation
currently requires concrete entry values. Other induction variables
may have nonconstant entry ranges once a separate counter establishes
the iteration bound. This limitation can be lifted eventually.
4. Alternative values referring to another evolving register:
r7 = 0;
for (r6 = 0; r6 < 4; r6++)
if (condition)
r7 = r6;
use(r7);
R6 changes on each iteration. Widening currently supports
conditional assignments only from constants or values that do not
change in the loop. This limitation can be lifted.
5. Stack addresses whose widening would lose precise slot tracking:
u64 slots[4];
for (u64 i = 0; i < 4; i++)
slots[i] = i;
struct bpf_dynptr dptrs[4];
for (u64 i = 0; i < 4; i++)
bpf_dynptr_from_xdp(ctx, 0, &dptrs[i]);
Keep such indices concrete for 4- and 8-byte stack loads/stores and
calls requiring fixed-offset stack objects. Dependencies inside
nested loops also constrain the outer loop.
It would be hard to lift this limitation.
6. Values modified by a nested loop do not get a closed-form summary
for the enclosing loop:
u64 sum = 0;
for (u64 i = 0; i < 4; i++)
for (u64 j = 0; j < 4; j++)
sum++;
use(sum);
The inner loop may widen, but the outer analysis forgets values
modified by it rather than deriving the combined recurrence.
This limitation can be lifted.
7. Multiple backedges and irreducible control flow:
i = 0;
H: if (i >= 8) goto done;
if (condition) { i++; goto H; } // first backedge
i++; goto H; // second backedge
done:
i = 0;
if (condition) goto body; // second entry into the loop
H: i++;
body:
if (i < 8) goto H;
Widening requires a reducible loop with one backedge and a supported
dominating exit condition. Multiple exits are supported, but their
early-exit paths reduce what can be inferred about iteration counts.
It is unclear whether this can be lifted at the moment.
8. Large slopes and unsupported iteration bounds:
for (u64 i = 0, x = 0; i < 4; i++) {
use(x);
x += 65536; // slope outside signed 16 bits
}
Slopes used for linear widening must be nonzero signed-16-bit
constants. The inferred number of header executions must be finite
and less than U32_MAX. Counter wraparound must be ruled out while
deriving the bound.
9. Incompatible pointer alternatives or comparison operands:
p = &map_a[0];
q = &map_b[0];
for (u64 i = 0; i < 10; i++) {
if (i == 5)
p = q;
use(*p);
}
At the loop header, p has SCEV ANY(p_entry, q). The alternatives
point into different maps, so their offsets cannot be joined while
retaining one map's metadata. Joining invariant pointer
alternatives requires compatible pointer metadata, including type,
origin IDs, frame number.
10. Some hard-coded constant limits:
- Programs with more than 16 nested loops in one function are rejected.
- Loops with more than 256 exits exceed the metadata limits and are
not analyzed for widening.
- At most 4 exit conditions dominating the latch are consulted for
the iteration count of a loop.
- Expression traversal is limited to depth 8. Only a small fixed number
of alternative values can be joined.
Veristat changes
================
The main impact of the series is a 23% reduction in number of
processed instructions on a subset of Meta BPF programs.
Verdict changes
---------------
Two programs flip succes->failure, both selftests whose expectations
are updated by the series:
- verifier_gotox/gotox_edges_at_limit: test's CFG is a nest of ~1000
irreducible loops, deeper than the per-function loop stack (16),
the program is rejected with "Too many nested loops".
- verifier_scev/conditional_assignment_on_second_iteration:
a value assigned on the second iteration is checked after the loop
with its widened range, so a stack read guarded by that check
is rejected.
No program from the production corpora changes verdict.
Regressions
-----------
20 programs regress by 30-33% and 6 more by 10-21%, all from an
appliction objects sharing one unwinder library.
All programs share a common reason for regression:
- a big outer loop contains several smaller nested loops;
- nested loops are now widened and coverge, their convergence
adds backedges to the outer loop's SCC, thus flipping
checkpoint comparisons with the outer loop to RANGE_WITHIN mode.
Support for 32-bit recurrences and comparisons widens these loops too
and removes the regression. This would be handled in a followup.
Statistics
----------
A: master; B: scev-minimal-v3. Corpora: cilium, meta, scx, selftests.
Insns counts verifier-processed instructions, not program size.
Object exclusions: verifier_scev.bpf.o.
Histogram: selected programs, without the table filters.
Total progs: 7952
Old success: 5637
New success: 5646
total_insns diff min: -99.84%
total_insns diff max: 61.90%
0 -> value: 0
value -> 0: 0
total_insns abs max old: 837,487
total_insns abs max new: 837,487
-100 .. -95 %: 15
-95 .. -90 %: 12
-90 .. -85 %: 10
-85 .. -75 %: 8
-75 .. -70 %: 6
-70 .. -65 %: 14
-65 .. -60 %: 38
-60 .. -55 %: 10
-55 .. -50 %: 17
-50 .. -45 %: 36
-45 .. -40 %: 9
-40 .. -35 %: 25
-35 .. -25 %: 10
-25 .. -15 %: 11
-15 .. -10 %: 48
-10 .. -5 %: 47
-5 .. 0 %: 111
0 .. 5 %: 7488
5 .. 15 %: 3
15 .. 25 %: 5
30 .. 35 %: 20
35 .. 40 %: 7
40 .. 50 %: 1
60 .. 65 %: 1
Tables: success in both runs; baseline Insns >= 5,000.
Ranked by percentage change, then instruction-count change, file, program.
Meta names are anonymized; numbered objects are distinct files.
Top wins (50)
-------------
File Program Insns (A) Insns (B) Insns (DIFF)
---------------------------------- --------------------------------- --------- --------- -----------------
verifier_bounds.bpf.o crossing_64_bit_signed_boundary_2 12330 20 -12310 (-99.84%)
verifier_iterating_callbacks.bpf.o test1 7004 12 -6992 (-99.83%)
bpf_iter_tasks.bpf.o dump_task_sleepable 85522 556 -84966 (-99.35%)
bpf_iter_task_stack.bpf.o dump_task_stack 7209 65 -7144 (-99.10%)
profiler-10.bpf.o hhvm_stack 23828 347 -23481 (-98.54%)
bpf_iter_unix.bpf.o dump_unix 9026 226 -8800 (-97.50%)
meta-app-22.bpf.o program-03 8705 319 -8386 (-96.34%)
meta-app-22.bpf.o program-06 8948 328 -8620 (-96.33%)
security-sandbox-10.bpf.o fork 30760 1249 -29511 (-95.94%)
profiler-02.bpf.o on_py_event 79064 3864 -75200 (-95.11%)
profiler-03.bpf.o on_py_event 79064 3864 -75200 (-95.11%)
profiler-05.bpf.o on_py_event 79064 3864 -75200 (-95.11%)
security-monitor-66.bpf.o mac_sysctl_write 7333 448 -6885 (-93.89%)
profiler-04.bpf.o get_task_stacks 73176 6050 -67126 (-91.73%)
security-monitor-65.bpf.o lsm_bprm_creds_for_exec 17538 1701 -15837 (-90.30%)
security-monitor-65.bpf.o lsm_task_alloc 5674 565 -5109 (-90.04%)
security-monitor-65.bpf.o lsm_fo_task_update 11399 1181 -10218 (-89.64%)
security-sandbox-29.bpf.o test_glob_match 47257 5477 -41780 (-88.41%)
load-balancer-17.bpf.o edgeloom_tc 24854 2984 -21870 (-87.99%)
profiler-13.bpf.o handle_aten_op_call_start 7183 976 -6207 (-86.41%)
security-monitor-65.bpf.o lsm_file_open 154412 21168 -133244 (-86.29%)
security-monitor-17.bpf.o test_execve 293300 46071 -247229 (-84.29%)
security-sandbox-13.bpf.o kvm_die 36514 5807 -30707 (-84.10%)
security-monitor-97.bpf.o child_iter 41266 8182 -33084 (-80.17%)
scheduler-30.bpf.o lavd_dispatch 290915 66359 -224556 (-77.19%)
security-monitor-25.bpf.o syscalls_kill 98038 27912 -70126 (-71.53%)
security-sandbox-14.bpf.o kernel_module_request 7880 2357 -5523 (-70.09%)
security-sandbox-14.bpf.o kernel_load_data 7881 2358 -5523 (-70.08%)
security-sandbox-14.bpf.o kernel_read_file 7882 2359 -5523 (-70.07%)
xdp_lb_bench.bpf.o xdp_lb_bench 27126 9208 -17918 (-66.05%)
firewall-05.bpf.o ingress 54034 18584 -35450 (-65.61%)
firewall-05.bpf.o tc_in 54034 18584 -35450 (-65.61%)
firewall-07.bpf.o ingress 54034 18584 -35450 (-65.61%)
firewall-07.bpf.o tc_in 54034 18584 -35450 (-65.61%)
security-sandbox-01.bpf.o bpf 30692 10586 -20106 (-65.51%)
security-monitor-34.bpf.o syscall_setresuid 122200 43305 -78895 (-64.56%)
security-monitor-34.bpf.o syscalls_setfsgid 122200 43305 -78895 (-64.56%)
security-monitor-34.bpf.o syscalls_setfsuid 122200 43305 -78895 (-64.56%)
security-monitor-34.bpf.o syscalls_setgid 122200 43305 -78895 (-64.56%)
security-monitor-34.bpf.o syscalls_setregid 122200 43305 -78895 (-64.56%)
security-monitor-34.bpf.o syscalls_setreuid 122200 43305 -78895 (-64.56%)
security-monitor-34.bpf.o syscalls_setuid 122200 43305 -78895 (-64.56%)
security-monitor-15.bpf.o cve_2021_4034 122481 43629 -78852 (-64.38%)
security-monitor-16.bpf.o test 122517 43665 -78852 (-64.36%)
security-sandbox-10.bpf.o exec 12908 4626 -8282 (-64.16%)
security-monitor-12.bpf.o connect_security_socket_connect 216252 78013 -138239 (-63.92%)
security-monitor-19.bpf.o kernel_modules_do_init 92980 33776 -59204 (-63.67%)
security-monitor-23.bpf.o enter_pivot_root 93518 34311 -59207 (-63.31%)
security-monitor-08.bpf.o bpf_prog_detect 93384 34494 -58890 (-63.06%)
firewall-05.bpf.o egress 58436 21951 -36485 (-62.44%)
Top losses (38)
---------------
File Program Insns (A) Insns (B) Insns (DIFF)
-------------------------------- ----------------------------- --------- --------- ----------------
profiler-26.bpf.o handle_cu_mem_address_reserve 34326 45724 +11398 (+33.21%)
profiler-26.bpf.o handle_cu_mem_create 34326 45724 +11398 (+33.21%)
profiler-26.bpf.o handle_malloc 34326 45724 +11398 (+33.21%)
profiler-26.bpf.o handle_cu_mem_map 34524 45922 +11398 (+33.01%)
profiler-19.bpf.o sched_waking 17454 23153 +5699 (+32.65%)
profiler-27.bpf.o handle_cuda_launch_exc 17477 23176 +5699 (+32.61%)
profiler-27.bpf.o handle_cuda_launch 17490 23189 +5699 (+32.58%)
profiler-12.bpf.o on_custom_event_begin 17697 23396 +5699 (+32.20%)
profiler-12.bpf.o on_custom_event_end 17701 23400 +5699 (+32.20%)
profiler-26.bpf.o handle_mtia_cached_alloc 35494 46892 +11398 (+32.11%)
profiler-26.bpf.o handle_mtia_allocate_enter 35555 46953 +11398 (+32.06%)
profiler-26.bpf.o handle_pytorch_malloc 35847 47245 +11398 (+31.80%)
profiler-19.bpf.o oncpu 17990 23689 +5699 (+31.68%)
profiler-12.bpf.o on_task_enqueued 18035 23734 +5699 (+31.60%)
profiler-12.bpf.o sched_waking 18070 23769 +5699 (+31.54%)
profiler-12.bpf.o on_task_dequeued 18210 23909 +5699 (+31.30%)
profiler-12.bpf.o on_request_context_event 18301 24000 +5699 (+31.14%)
profiler-12.bpf.o on_pytorch_event 18302 24001 +5699 (+31.14%)
profiler-12.bpf.o on_task_stats 18384 24083 +5699 (+31.00%)
profiler-12.bpf.o oncpu 18488 24187 +5699 (+30.83%)
profiler-19.bpf.o sched_switch_offcpu 64726 78210 +13484 (+20.83%)
profiler-12.bpf.o sched_switch 33515 40257 +6742 (+20.12%)
profiler-09.bpf.o on_custom_event_start 38281 45973 +7692 (+20.09%)
profiler-09.bpf.o trace_func_entry 38281 45973 +7692 (+20.09%)
profiler-12.bpf.o get_crochet_walltime_stacks 43473 50215 +6742 (+15.51%)
profiler-24.bpf.o get_task_stacks 94740 103742 +9002 (+9.50%)
test_cls_redirect_subprogs.bpf.o cls_redirect 72052 73682 +1630 (+2.26%)
security-sandbox-20.bpf.o redirect_socket_connect 72423 73913 +1490 (+2.06%)
scheduler-28.bpf.o arena_alloc_mask 27159 27175 +16 (+0.06%)
scheduler-30.bpf.o arena_alloc_mask 27159 27175 +16 (+0.06%)
scx_cake.bpf.o arena_alloc_mask 28721 28737 +16 (+0.06%)
scx_arena.bpf.o arena_alloc_mask 28734 28750 +16 (+0.06%)
scx_arena_selftests.bpf.o arena_alloc_mask 28734 28750 +16 (+0.06%)
scx_chaos.bpf.o arena_alloc_mask 28734 28750 +16 (+0.06%)
scx_p2dq.bpf.o arena_alloc_mask 28734 28750 +16 (+0.06%)
scx_cake.bpf.o cake_init_task 28758 28774 +16 (+0.06%)
scheduler-01.bpf.o arena_alloc_mask 29197 29208 +11 (+0.04%)
scheduler-03.bpf.o arena_alloc_mask 29197 29208 +11 (+0.04%)
Changelog
=========
v2 -> v3:
TLDR: another bunch of major correctness fixes, plus several improvements
to avoid veristat-meta failure identified for v2.
- Widen only when allow_uninit_stack is set.
- Mark scalar registers and stack spills used by the selected bounding
condition's base, step and bound expressions precise before widening.
- Join alternative values only for registers with compatible pointer
metadata. Include the loop-entry value when a register is assigned an
invariant in the body, including unconditional assignments.
- Consider up to four exit conditions dominating the backedge and use
the tightest available iteration bound. Match the induction variable
in either operand of the comparison.
- Require full spills for linear stack recurrences. Treat partially
spilled and unallocated stack slots as unknown scalars and all-zero
slots as zero. Materialize writable stack values safely, growing the
stack when needed.
- Keep base/step in sync with the bounds as the last step of
reg_bounds_sync(). Preserve the register state when sign extension
leaves all possible values unchanged. Check that step is nonzero and
base is smaller than step.
- Handle latch comparison polarity correctly when the continuing branch
enters a nested loop. Compute SCEVs only for exits owned by the loop,
fixing a verifier bug for irreducible inner loops.
- Exclude BPF_F_INNER_MAP single-element arrays from the separate-lookup
shortcut in bpf_same_memory_origin().
- Fix stack-pointer tracking through load-acquire/store-release and
atomic exchange/fetch/cmpxchg operations, so accesses through recovered
stack pointers are included in liveness analysis.
- Derive global subprogram stack effects from BTF argument types, so
freplace cannot invalidate a loop termination proof based on the
original callee body.
- Compute argument liveness from callee reads for static subprograms
and from BTF-declared arguments for globals. Prepare argument metadata
before liveness analysis, avoiding unnecessarily live registers that
prevented widening.
- Treat already-unbounded scalars as already widened, allowing unknown
SCEVs such as stack outputs of probe-read helpers called through a
subprogram.
- Widen to an unbounded range when computing an induction variable's
range overflows signed 64-bit arithmetic, retaining the power-of-two
alignment common to the entry value and slope.
- Fix dominator computation for subprograms whose entry is a loop header:
initialize the entry as its own dominator during the fixed-point
computation and skip updates to it. Use overflow-checked predecessor
allocations.
- Replace the private worklist heap with the kernel min-heap and limit
expression rewriting to 32 passes before falling back to unknown.
- Add regression coverage for the liveness, stack, pointer, iteration
bound and widening changes. Fix __msg_next validation when an expected
message is missing.
v1 -> v2:
TLDR: a bunch of major correctness fixes.
- Introduce arg_access_info to distinguish read, may-write and
must-write effects of helper/kfunc stack accesses. Handle map-specific
argument semantics and writes through unknown callbacks.
- Fix base/step tracking across signed overflow, truncation,
sign/zero extension and linked-register updates.
- Rework iteration-count calculation for signed/unsigned increasing
and decreasing counters, including counter overflow checks.
Evaluate the full latch base expression and consistently count
header executions.
- Substitute all registers in instantiate_header_scevs().
- Track pointer origins when evaluating latch expressions.
Require compatible operands before deriving iteration bounds.
- Preserve the correct congruence base when widening nonconstant
entry values, assign fresh IDs to widened packet pointers,
and exclude nullable pointers from widening.
- Account for values modified on nested-loop exit paths when computing
invariants. Do not use an inner loop's latch to bound an outer loop.
- Restrict pruning against in-progress SCEV states to terminating
innermost loops sharing the same entry checkpoint, preventing
inner-loop pruning from hiding a nonterminating outer loop.
- Rework loop entry/exit handling on the main verification pass.
- Extend fixed-stack-offset widening suppression to ANY expressions
and all dynptr arguments described by helper/kfunc prototypes.
- Fix BTF array handling: retain bounds checks for fixed arrays inside
flexible-array elements and preserve array type IDs when element
types contain typedefs.
- Fix SCEV handling of endian conversions and narrow fills on
big-endian systems.
- Grow expression storage geometrically and scale the expression hash
table with program size. Add cancellation/rescheduling checks to
dominator computation and fix the postorder-number allocation leak.
- Pack bpf_reg_state/bpf_func_state for latter to fit back into
the 1 KiB allocation bucket, measured SCEV memory consumption
overhead is 3% now.
- Major additions in the selftests.
v1: https://lore.kernel.org/bpf/20260926-scev-minimal-rebase-v1-0-c8e5ab5ba79f@gmail.com/
v2: https://lore.kernel.org/bpf/20261004-scev-minimal-rebase-v2-0-f6254e29fdf2@gmail.com/
---
====================
Link: https://patch.msgid.link/20261009-scev-minimal-rebase-v3-0-bcba9bc53ac9@gmail.com
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
|
|
- Computed expression shapes: register and spilled-counter recurrences,
substitution at latches, agreeing and conflicting backedge updates,
and ALU, extension, byte-swap, load/store and atomic expressions.
- Iteration bounds and header-visit counts for:
- pre-condition loops using JEQ, JLT, JLE, JGE and JGT;
- post-condition loops using JLT, JLE, JGE, JGT and JNE;
- signed pre- and post-conditions using JSLT, JSLE, JSGT and JSGE;
- increasing and decreasing counters, nonzero initial values,
immediate and invariant-register bounds, and immediate exits;
- additional exits that reduce the minimum iteration count or
tighten the upper bound;
- rounded bounds, counter wraparound, count overflow, extreme
steps and JNE divisibility.
- Widening, backedge clamping and state-pruning convergence,
including multiple induction variables used for map-value accesses
and nonconstant entry values requiring a common alignment.
Check precision propagation to initial values and bounds.
- Nested and sibling loops, shared headers, exits to another loop
header, exits across multiple nesting levels, and side entries
into loop nests.
Check conservative summaries for irreducible children while still
widening supported reducible descendants, value preservation on
inner-loop exits, and detection of nonterminating outer loops.
- Invalidation of stack-slot expressions after indirect stack writes
and global calls. Widening across bpf_probe_read_kernel() calls
in static subprograms.
- Stack spill widths and slot states, including narrow spills, zero,
unallocated and STACK_MISC slots, and counters spilled and filled
using store-release/load-acquire.
- Avoid widening registers used to address stack spills, fills and
dynptr constructor arguments, including dependencies through nested
loops. Conversely, allow widening addresses of byte-sized stores.
- Conditional assignments joining scalar values and stack pointers,
including preservation of a common base and gcd-derived step.
- Pointer widening and comparisons with compatible memory origins,
fallback for incompatible origins and nullable pointers, and
invalidation of stale packet pointer relationships.
- Conservative fallback for unsupported recurrences, unavailable
counter spills and zero computed header counts.
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://patch.msgid.link/20261009-scev-minimal-rebase-v3-51-bcba9bc53ac9@gmail.com
|
|
Coverage:
- straight-line code with an ldimm64 in the middle;
- an asymmetric if-then-else diamond (unequal-depth idoms_intersect());
- a simple loop, a loop with an if-else body, and nested loops;
- a loop header with two back edges (three predecessors);
- an irreducible CFG (fixpoint convergence);
- immediate dominators across subprogram boundaries, including a callee
whose entry instruction is itself a loop header;
- a self-loop;
- an indirect jump (gotox) with a two-entry jump table.
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://patch.msgid.link/20261009-scev-minimal-rebase-v3-50-bcba9bc53ac9@gmail.com
|
|
Test cases covering the following branches in bpf_compute_loops():
- Case B: simple backedge creating a loop (loop_single)
- Case B: two independent loops (loop_two_independent)
- Case B + D: nested loops where the inner header's loop_header points
to the outer header (loop_nested)
- Case C: diamond CFG with no loops (fwd_edges_no_loop)
- Case D: sibling inner loops within one outer loop
(loop_nested_siblings)
- Three levels of loop nesting (loop_three_levels)
- Loop with an if-else body containing forward branches
(loop_with_if_else)
- Case E: An irreducible loop (loop_irreducible)
- A self-loop (loop_self)
- A test with sibling loops nested in outer loops
(loop_nested_siblings_common_ancestors)
- A test case with outer loop's backedge originating
from an inner loop (loop_outer_backedge_from_inner).
Cases B, C, D and E are described in loops.c:compute_loops_in_subprog().
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Reviewed-by: Emil Tsalapatis <emil@etsalapatis.com>
Link: https://patch.msgid.link/20261009-scev-minimal-rebase-v3-49-bcba9bc53ac9@gmail.com
|
|
Verifier tests for accessing arrays at a varying offset through a
PTR_TO_BTF_ID pointer, e.g. a[i].b where 'i' is a register with a
varying value:
- bpf_obj_new() is used to obtain a PTR_TO_BTF_ID to a program-defined
struct
- bpf_get_current_task_btf() is used to obtain a PTR_TO_BTF_ID from
the kernel BTF.
The cases cover:
- in-bounds access to a field of an array of structs;
- out-of-bounds access where the maximal offset runs past the array;
- a scalar (long) array with a matching stride;
- a byte array (step 1);
- a 4-byte read whose maximal offset spills past the array end;
- an unaligned step that is not a whole number of elements;
- both dimensions of a 2D array;
- an array of pointers within a program-allocated object, where reading a
pointer member yields a SCALAR_VALUE but the varying offset is still
validated against the array bounds (in-bounds and out-of-bounds);
- a varying access into an array embedded in a kernel BTF type
(task_struct's comm[]), covering the non-allocated, trusted-pointer path
(in-bounds and out-of-bounds);
- an array nested below a struct member at a non-zero offset, exercising
the offset telescoping done while walking across a struct boundary
(in-bounds and out-of-bounds);
- a trailing flexible array member, whose unbounded tail makes a varying
access have no upper bound to exceed. A program-defined struct cannot be
used here because bpf_obj_new() forbids flexible array members, so a
kernel type (struct vring_used, with its 'ring[]' tail) is used
(in-bounds, and an unaligned step that is not a whole number of
elements).
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://patch.msgid.link/20261009-scev-minimal-rebase-v3-48-bcba9bc53ac9@gmail.com
|
|
Tests for the base/step reasoning in states.c:range_within():
- step_prune_hit_multiple: prune a step-4 range contained in a cached
step-2 range when the scalar is used to address the stack.
- step_prune_miss_non_multiple: do not let a cached step-2 range hide a
step-3 path reaching division by zero.
- step_prune_hit_const_on_line: prune constant 6 against a cached
base-0, step-3 range.
- step_prune_miss_const_off_line: do not prune constant 7 against that
range even though its bounds and tnum admit the value.
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://patch.msgid.link/20261009-scev-minimal-rebase-v3-47-bcba9bc53ac9@gmail.com
|
|
- step_arith{32,64}_no_overflow: non-overflowing +, *, <<
operations maintain step and base.
- step_neg_value_range: Preserve the signed range of {-3, 0, 3, 6}
when intersecting with a non-power-of-two step across zero.
- step_arith{32,64}_overflow: Reset the stride and preserve valid
bounds when a {32,64}-bit operation wraps.
- step_mov32_truncate: Reset the stride when MOV32 discards nonzero
upper bits from positive values.
- step_mov32_negative: Reset the stride when MOV32 zero-extends
the low 32 bits of negative signed values.
- step_movsx: Reset the stride when sign extension changes the
register value.
- step_movsx_bounds_on_line: Keep bounds and stride when sign
extension does not change the register value.
- step_bounds_resync_after_arith: Snap bounds refined from var_off
back onto the line.
- step_linked_regs_add64: Translate both bounds and base when
propagating a comparison's refinement through a scalar-ID delta.
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://patch.msgid.link/20261009-scev-minimal-rebase-v3-46-bcba9bc53ac9@gmail.com
|
|
A static callee contributes the registers its code reads at the entry,
a global callee its declared arguments.
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://patch.msgid.link/20261009-scev-minimal-rebase-v3-45-bcba9bc53ac9@gmail.com
|
|
Check that passing a stack pointer to a no-op global callee produces:
- use, def and may_def marks for a fixed-size memory argument.
- No stack effects for an untrusted BTF pointer argument.
This verifies that call effects follow the declared argument types
rather than the callee's body.
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://patch.msgid.link/20261009-scev-minimal-rebase-v3-44-bcba9bc53ac9@gmail.com
|
|
Tests for helper arguments whose access size or read/write effects
depend on the map:
- helper_map_output_known_size checks that for a known map access
MEM_WRITE | MEM_UNINIT produces a must_write mark.
- helper_map_output_merged_sizes checks that when maps with different
value sizes merge, MEM_WRITE | MEM_UNINIT produces use and may_def
marks over the maximum value size, without a def mark.
- helper_bloom_peek_input checks that for bpf_map_peek_elem()
on a bloom filter the buffer is treated as an input.
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://patch.msgid.link/20261009-scev-minimal-rebase-v3-43-bcba9bc53ac9@gmail.com
|
|
Check stack write tracking for atomic operations:
- Restored by 64-bit load-acquire, xchg, fetch_add and cmpxchg.
- Spilled by store-release and restored by a plain load.
- Restored from a caller's stack slot by xchg in a callee.
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://patch.msgid.link/20261009-scev-minimal-rebase-v3-42-bcba9bc53ac9@gmail.com
|
|
Liveness analysis should produce may_def marks for read-modify-write
atomic operations:
- lock *(u64 *)(r10 -8) += r1
- r1 = atomic64_fetch_add((u64 *)(r10 -8), r1)
- r1 = atomic64_xchg((u64 *)(r10 -8), r1)
- r0 = atomic64_cmpxchg((u64 *)(r10 -8), r0, r1)
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://patch.msgid.link/20261009-scev-minimal-rebase-v3-41-bcba9bc53ac9@gmail.com
|
|
Branches to cover:
- per-insn writes (record_stack_access_off):
* off_cnt==1, fully covered slots -> def + may_def (equal)
* partial coverage -> may_def only (no def)
* off_cnt 2-4, precise offsets -> may_def only, per offset
- whole-frame writes:
* off_cnt==0 (offset lost) -> may_def SPIS_ALL
* ARG_IMPRECISE (frame lost) -> may_def SPIS_ALL per frame
- merge_instances():
* both passes touch a frame -> may_def union
* one pass leaves a frame untouched -> may_def preserved
- merge_may_write(): a callee's writes into ancestor frames are
summarized as may_def at the caller's call instruction
- analyze_subprog() -> may_def stack slot range
when callback is unknown.
Tests exercising them:
- may_write_two_precise_offsets - off_cnt 2-4 precise multi-offset
- imprecise_frame_write - cross-frame ARG_IMPRECISE write,
plus its caller-side summarization
- merge_preserves_may_write - map-value vs stack pointer at two
callsites: union is preserved when
one pass does not touch the frame
- must_write_not_same_slot - off_cnt==0 whole-frame may_def
- two_byte_write_no_kill - partial write, may_def without def
- kfunc_iter_stack_liveness - full-slot def == may_def
- helper_output_unknown_size - output size unknown to liveness,
may_def without use or def
- caller_stack_write,
conditional_stx_in_subprog,
shared_instance_must_write_overwrite
- callee writes summarized as may_def
at the call site
- bpf_loop_two_callbacks - call to unknown callback marks full
stack range as may_def.
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://patch.msgid.link/20261009-scev-minimal-rebase-v3-40-bcba9bc53ac9@gmail.com
|
|
Validate changes from:
"bpf: allow subrange relations for PTR_TO_STACK in regsafe()".
Add a test case that checks that a widened stack pointer with range
[-72, -16] is considered a superset of a stack pointer with range
[-64, -16].
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://patch.msgid.link/20261009-scev-minimal-rebase-v3-39-bcba9bc53ac9@gmail.com
|
|
The bpf_iter/unix and skc_to_unix_sock tests index sun_path but bound
that index by sizeof(struct sockaddr_un). This allows indices 108 and
109 into the 108-byte array. With SCEV loop widening, the variable-offset
BTF access check rejects the resulting range.
Bound the index by sizeof(sun_path) in both tests. Runtime behavior for
valid UNIX addresses is unchanged.
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://patch.msgid.link/20261009-scev-minimal-rebase-v3-38-bcba9bc53ac9@gmail.com
|
|
Same as __msg, but expects the match on the line immediately after
the last match, not just any later line.
E.g.:
__msg_next("a")
__msg_next("c")
This would match consecutive output "a\n" "c\n",
but would not match output "a\n" "b\n" "c\n".
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://patch.msgid.link/20261009-scev-minimal-rebase-v3-37-bcba9bc53ac9@gmail.com
|
|
Pack bpf_reg_state to bring it's size from 88 bytes to 80.
Consequently, bpf_func_state changes from 1048 to 960.
Thus bpf_func_state moves from 2K to 1K allocator bucket.
1K bucket is the one it fit before the SCEV series.
With this optimization SCEV increases memory consumption on a subset
of Meta internal programs by 3%, without this optimization the
increase is 48%.
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://patch.msgid.link/20261009-scev-minimal-rebase-v3-36-bcba9bc53ac9@gmail.com
|
|
For loops like this:
int arr[10];
for (int i = 0; i < 10; i++)
arr[i] = i;
use(arr[i]);
SCEV-based loop widening converts `i` from being enumerated 10 times
as a constant value 0, 1, ..., 9 to being enumerated once as a range
[0..9]. From the point of view of the main verification pass, this
replaces constant-offset stack access with varying-offset
stack access.
The verifier tracks stack values accessed through varying offsets much
less precisely than those accessed via constant offsets.
For example, the read at use(arr[i]) would yield STACK_MISC.
Precision might be lost for the following operations:
- spills (BPF_ST/STX to the stack): stored value can no longer be
recovered when read back, e.g. after the loop;
- fills (BPF_LDX from the stack): a varying-offset read of a spilled
pointer yields a SCALAR_VALUE, so the pointer is lost.
- calls that construct objects on the stack (dynptr, iter, irq_flag,
res_spin_lock): the stack argument is required to have a
constant offset.
This commit adds logic to avoid widening registers used by
such instructions:
- During the main SCEV computation stage, collect_store_base_regs():
- inspects instructions accessing the stack (spill, fill, call to a
function listed in bpf_needs_fixed_stack_off), and
- if there is a SCEV expression for a stack base address register,
records which registers the expression depends on in
the bpf_loop->store_base_reg field.
- `store_base_reg`s accumulated for nested loops are propagated
to outer loops as well.
- During the loop-widening stage, bpf_compute_loop_iters() refuses to
widen a loop when some of the registers the loop changes appear in
store_base_regs.
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://patch.msgid.link/20261009-scev-minimal-rebase-v3-35-bcba9bc53ac9@gmail.com
|
|
Loop-bound computation and register widening
===========================================
During the main verification pass, use SCEV expressions and register
values at the entry to the loop to estimate the number of iterations
the loop might execute. Use this number to widen loop induction variables.
For example:
0: r7 = 5;
1: r6 = 0;
2: while (r6 < 3) { // latch
3: if (r6 == 1)
4: r7 = 10;
5: r6 += 1;
6: }
8: use(r7);
- Scalar evolution expressions (SCEVs) at the latch are:
- r6 = (linear r6 1)
- r7 = (any r7 10)
- For this pre-condition loop, this corresponds to the linear inequality
`r6_entry + n < 3`. With r6_entry = 0, the inequality is `n < 3`.
- Hence infer that r6's range at line 2 is [0,3], including the final
failed test. The body starts with r6 in [0,2].
- r7's (any r7 10) expression means that its initial value 5 from line 0
is joined with 10 from line 4: it is widened to [5,10] within
and after the loop.
Currently such inference is supported for:
- Reducible loops with one backedge and complete backedge/exit lists.
- A linear latch dominating the backedge, with one successor exiting
the loop. Additional exits are allowed; they can shorten execution.
- 64-bit arithmetic and comparisons whose continuation condition
normalizes to signed/unsigned < or <=, or !=.
- Initial counter, latch offset, slope and bound evaluable as constants
at loop entry, yielding a finite, representable iteration bound.
- Values with an eligible type at loop entry, e.g. SCALAR_VALUE or
PTR_TO_STACK, but not PTR_TO_CTX.
In order for widening to proceed, every register live at the loop
entry has to have a SCEV that can be widened. Currently, the following
expressions are supported:
- (linear <self> <step>): entry value + iteration# * constant step.
- (reg <self>): loop invariant; keep its entry value unchanged.
- (any ...): join the entry value with immediates or invariant registers;
types must match, and immediates require SCALAR_VALUE.
Main verification loop integration
==================================
Before proceeding with the usual instruction processing, do_check()
takes the following steps at loop entries (H):
- Checks whether the loop can be widened and obtains its
iteration bound (scev.c:bpf_compute_loop_iters()).
- If it can, saves an unwidened checkpoint E0, which will be used as
a base for deriving widened values throughout this invocation of
the loop.
- Widens registers in the current state using E0 and SCEV expressions
computed for H (scev.c:bpf_widen_scev_regs()).
- Pushes a per-frame loop-stack record to the current verifier state.
For terminating loops, the record stores E0 and the iteration bounds.
- Lets is_state_visited() create a new checkpoint W at the same
header, now containing the widened values, and proceeds with
normal checking.
- On an exit edge, pops the loop record and verifies the exit
path normally.
is_state_visited() treats a loop proven to terminate like an
iterator-based loop: RANGE_WITHIN comparison attempts to establish
convergence against a checkpoint whose exploration is still
in progress.
For example:
r0 = 0;
H: r0 += 1;
if (r0 != 3) goto H;
exit;
first H: prove H_count = 3; save E0(r0 = 0)
widen r0 to [0,2]; push the loop record
save W(r0 = [0,2])
body: r0 becomes [1,3]; fork at the conditional
exit: r0 = 3; pop the loop record and check exit
backedge: r0 = [1,2]; clamp, then match with W and prune
Clamping
--------
Independent register ranges lose correlations between induction
variables. For example:
r6 = 0; r7 = 0;
do { r6 += 1; r7 += 2; } while (r6 < 3);
use(r7);
header: r6 in [0,2], r7 in {0,2,4}
body: r6 in [1,3], r7 in {2,4,6}
backedge: r6 in [1,2], r7 still in {2,4,6}
The latch narrows r6 but does not propagate this refinement to r7.
To account for this, before comparing states on a backedge,
scev.c:bpf_clamp_scev_regs() recomputes r7's range from E0 and the
saved iteration bound, then intersects the current range {2,4,6}
with the recomputed {0,2,4}, arriving at {2,4}.
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://patch.msgid.link/20261009-scev-minimal-rebase-v3-34-bcba9bc53ac9@gmail.com
|
|
Assign algebraic expressions to loop variables (registers and stack
spills), describing how their values evolve across iterations. These
summaries provide symbolic input for the subsequent widening patch.
The algorithm draws on ideas from the following papers:
- "Symbolic Evaluation of Chains of Recurrences for Loop Optimization"
Robert A. van Engelen, 2000
- "The CR# Algebra and its Application in Loop Analysis and Optimization"
Robert A. van Engelen, 2004
The analysis proceeds in two phases:
- Compute expressions for one symbolic iteration: start each variable
with a reference to its input value, apply instruction effects and
join expressions where control-flow paths merge.
- Convert the resulting backedge updates to recurrences at the header,
then substitute these recurrences into expressions at the latch.
Analyze loops innermost first. Within each loop, visit blocks in
topological order (reverse postorder, with backedges ignored and nested
loops collapsed). Treat each nested loop as an opaque operation:
preserve its invariant values, forget the others and continue at its
exits, without expanding its iterations.
For example, using 64-bit arithmetic:
0: r7 = 5;
1: r6 = 0;
2: do { // header
3: if (r6 == 1)
4: r7 = 10;
5: r6 += 1;
6: } while (r6 < 3); // latch
Expressions use symbolic inputs r6 and r7; the concrete values from
lines 0-1 are supplied later by the main verifier.
First phase:
------------
At each instruction, an environment maps register numbers to their
current expressions. Transfer functions update this mapping, while
joins merge the environments arriving along different paths.
For illustration, follow each branch separately to the backedge:
- At 3, take the path skipping 4: r6 = r6, r7 = r7.
- At 5, transfer(r6 += 1): r6 = r6 -> r6 = (+ r6 1).
- At 2, the first path contributes r6 = (+ r6 1), r7 = r7.
- At 4, on the other path from 3, transfer(r7 = 10):
r7 = r7 -> r7 = 10.
- At 5, transfer(r6 += 1): r6 = r6 -> r6 = (+ r6 1).
- At 2, join the two paths' contributions:
join((+ r6 1), (+ r6 1)) = (+ r6 1) for r6;
join(r7, 10) = (any r7 10) for r7.
Equal expressions stay unchanged; different expressions become ANY
alternatives. These summarize one iteration, without unrolling the loop.
Second phase:
-------------
The update r6 = (+ r6 1) says that each iteration adds 1 to r6.
Repeating this update n times gives r6_entry + n, a linear recurrence.
- At header 2, r6 = (+ r6 1) becomes (linear r6 1), meaning
r6_entry + n, where n counts iterations from zero.
- At latch 6, substitute this recurrence into (+ r6 1):
(+ (linear r6 1) 1) simplifies to (linear (+ r6 1) 1),
meaning r6_entry + 1 + n.
- At both points, r7 retains (any r7 10): either its entry value
or 10. ANY records alternatives, not numeric ranges or the path
conditions selecting them. Unchanged variables retain their inputs.
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://patch.msgid.link/20261009-scev-minimal-rebase-v3-33-bcba9bc53ac9@gmail.com
|
|
SCEV integration logic might create two consecutive checkpoints at the
same instruction w/o processing any instructions in between.
This happens for loop-entry checkpoint -> regular checkpoint
sequences, where the loop-entry checkpoint has to remain unchanged
but the regular checkpoint is used for widening.
This commit adapts bpf_mark_chain_precision() to support this.
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://patch.msgid.link/20261009-scev-minimal-rebase-v3-32-bcba9bc53ac9@gmail.com
|
|
SCEV needs information about the program's basic-block structure.
Piggyback on compute_predecessors() and set
insn_aux_data->bb_end for an instruction if:
- it has multiple successors, or
- its sole successor has multiple predecessors, or
- it is a jump instruction.
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://patch.msgid.link/20261009-scev-minimal-rebase-v3-31-bcba9bc53ac9@gmail.com
|
|
A utility function counting the number of STACK_SPILL slots in a
bpf_stat_state instance. For use by SCEV widening logic.
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://patch.msgid.link/20261009-scev-minimal-rebase-v3-30-bcba9bc53ac9@gmail.com
|
|
When dealing with loops like:
for (ptr = ...; ptr < end_ptr; ptr += 8)
...
Scalar evolution needs to know if ptr and end_ptr identify a same
memory location (possibly with different offsets). If they do,
it is sound to attempt to infer iteration bounds for such a loop.
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://patch.msgid.link/20261009-scev-minimal-rebase-v3-29-bcba9bc53ac9@gmail.com
|
|
SCEV widening needs an explicit checkpoint preserving the original
loop-entry state, independently of ordinary state-cache heuristics.
This commit extracts checkpoint creation logic from
bpf_is_state_visited() into a separate utility function.
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://patch.msgid.link/20261009-scev-minimal-rebase-v3-28-bcba9bc53ac9@gmail.com
|
|
Utility functions to take a union of two registers' scalar values:
merge the circular 32-bit and 64-bit bounds, tnums and base/step
of two registers, then synchronize and validate the result.
Leave id invalidation and type validation to the caller.
Caller should use bpf_reg_union_compatible() to ensure
that final union result is sensible.
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://patch.msgid.link/20261009-scev-minimal-rebase-v3-27-bcba9bc53ac9@gmail.com
|
|
Provide a helper to set a register to a known scalar value for use outside
verifier.c. To be used by SCEV widening logic.
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://patch.msgid.link/20261009-scev-minimal-rebase-v3-26-bcba9bc53ac9@gmail.com
|
|
A utility function for setting a register's range and step information.
Used by SCEV widening and clamping logic further in the series.
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://patch.msgid.link/20261009-scev-minimal-rebase-v3-25-bcba9bc53ac9@gmail.com
|
|
SCEV needs to process loops from innermost to outermost, summarizing
results for nested loops. Add a pass to compute the loop structure.
Use a non-recursive adaptation of the algorithm from:
"A New Algorithm for Identifying Loops in Decompilation" by Wei et al.
Record the loop hierarchy per instruction:
- The field insn_aux_data->loop_header records the innermost loop
header containing it.
- The field insn_aux_data->loop records additional information about
the loop if this instruction is a loop header (exits, backedges,
irreducibility).
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://patch.msgid.link/20261009-scev-minimal-rebase-v3-24-bcba9bc53ac9@gmail.com
|
|
SCEV needs to find an exit condition that dominates a loop's backedge;
such conditions bound every loop iteration. Compute the immediate
dominator tree as a prerequisite for identifying such conditions.
Use the iterative reverse-postorder algorithm from:
"A Simple, Fast Dominance Algorithm" by Cooper et al.
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://patch.msgid.link/20261009-scev-minimal-rebase-v3-23-bcba9bc53ac9@gmail.com
|
|
Tests for multiple analyses performed by the verifier need the
verifier log to contain analysis results alongside the program
disassembly. This patch moves the log-level-2 program dump from
bpf_compute_live_registers() to a standalone function called from
bpf_check(), in order to provide a common logging function for such
analyses (and thus avoid printing program disassembly multiple times).
Rename the dump header from "Live regs before insn:" to
"Program dump (scc? insn#: live_regs_before):" and print available
source-line information before the corresponding instructions.
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Reviewed-by: Emil Tsalapatis <emil@etsalapatis.com>
Link: https://patch.msgid.link/20261009-scev-minimal-rebase-v3-22-bcba9bc53ac9@gmail.com
|
|
Dominator intersections and SCEV worklist scheduling need to compare
instructions by their DFS postorder rank. Save per-instruction
postorder numbers alongside the existing postorder sequence.
This commit modifies bpf_compute_postorder() to actually do the DFS
traversal, instead of scheduling traversal of all siblings at once.
Consider a graph:
A -> B
A -> C
C -> B
Old result: C, B, A
DFS result: B, C, A
Fixes: efcda22aa541 ("bpf: compute instructions postorder per subprogram")
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://patch.msgid.link/20261009-scev-minimal-rebase-v3-21-bcba9bc53ac9@gmail.com
|
|
Relax the requirements for reads like `p->arr[i].field`, where `p` is a
PTR_TO_BTF_ID, by allowing `i` to be a non-constant value.
This is useful for loops over arrays accessed from a PTR_TO_BTF_ID
when the verifier widens the loop induction variable.
Check that the access stays within array bounds based on the access
register's min and max bounds. Check that the access is aligned with
array elements using the register's `base` and `step`.
Technically, modify btf_struct_access() such that:
- it identifies `field` by walking BTF from the minimum offset
(the register's reg_smin + static instruction offset);
- it remembers which arrays contain `field`;
- it checks that offsets `k * step` stay within the array
and point to the same `field`;
- it does not check upper bounds for flexible arrays
(as is already the case for constant-offset access).
Support for flexible arrays nested inside trailing struct members
(e.g. p->nested.data[i], with data declared as int data[]) is left
for future work.
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://patch.msgid.link/20261009-scev-minimal-rebase-v3-20-bcba9bc53ac9@gmail.com
|
|
Extend scalar register tracking with a linear "base + step * k" description:
each scalar carries two u16 fields, base and step (invariant: base < step),
recording that its value is some point on the line base + step * k.
A fresh scalar starts as base=0, step=1, i.e. any integer.
This lets the verifier reason about strided values, e.g. an index multiplied
by an element size, which neither the min/max bounds nor the tnum can capture
for a non-power-of-2 stride. Such reasoning is necessary to allow
array access with a variable offset through PTR_TO_BTF_ID, e.g.
for expressions like p->arr[i].field.
reg_bounds_sync() uses the description in two ways:
- __reg_bound_offset() clears the low bits of var_off implied by the number
of trailing zeros shared by base and step.
- __update_bounds_from_step() intersects the 64-bit range with the line via
cnum64_intersect_linear(), snapping smin/smax to actual points on it.
This is the last step of the sync, as refining the range from var_off
can move the bounds off the line.
range_within() is extended to check whether the cur register's equation
describes a subset of the points described by the old register's equation.
Scalar ALU operations update base/step as follows:
- ADD of a constant (including pointer + scalar): keep step, shift base;
- MUL by a constant: scale step and base by the constant;
- LSH by a constant: scale step and base by the corresponding power of two;
- sign extension: keep the register unchanged if all values fit the target
type, reset to base=0, step=1 otherwise;
- All other operations reset to base=0, step=1.
Branch (eq/neq) checks do not take into account base/step yet.
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://patch.msgid.link/20261009-scev-minimal-rebase-v3-19-bcba9bc53ac9@gmail.com
|
|
regsafe() currently requires an exact match for PTR_TO_STACK registers.
This prevents an explored state from pruning a current state whose
variable-offset range is a subset of the explored range.
This change allows a checkpoint containing a widened stack pointer to
cover narrower offsets reached on subsequent loop iterations,
for example [-56, -8] within [-64, -8].
Merge the PTR_TO_STACK case with PTR_TO_MEM and others, as the set of
necessary checks is almost identical. The only difference is a map_uid
check, which is not needed for PTR_TO_STACK. All locations that
produce PTR_TO_STACK reset map_uid to zero.
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://patch.msgid.link/20261009-scev-minimal-rebase-v3-18-bcba9bc53ac9@gmail.com
|
