bpf: track scalar equality across the low 32 bits
Subsystems (4)
v2 cover bpf: track scalar equality across the low 32 bits
The verifier's linked-scalar machinery tracks register equality only for the full 64 bits, optionally with a constant delta. There is no way to record "these two registers share just their low 32 bits", so a 32-bit operation on a source with unknown high bits has to drop the relationship, and a later narrowing of the source never reaches the destination:
The verifier's linked-scalar machinery tracks register equality only for the full 64 bits, optionally with a constant delta. There is no way to record "these two registers share just their low 32 bits", so a 32-bit operation on a source with unknown high bits has to drop the relationship, and a later narrowing of the source never reaches the destination:
r6 = ... /* full 64-bit unknown */ w7 = w6 /* 32-bit zero-extending mov */ if w6 != 0 goto ... /* not taken: r6's low 32 bits are 0 */ if w7 == 0 goto ... /* not deduced today */
The same gap exists for the 32-bit sign extension, which is what prompted this, and -- as pointed out on the RFC -- for loads, which can zero- or sign-extend the same way. This series covers all four, plus the spill that feeds a narrowing fill.
Record a low-32 link instead of dropping the relation. On a later narrowing, sync_linked_regs() rebuilds such a register from the base by re-applying the extension the original operation used, rather than copying it. The reverse direction is skipped: a low-32 register knows nothing about a full register's high half.
There is an upstream test that documents the missing capability directly. verifier_reg_equal's "w reg not equal if r reg upper32 bits not 0" asserts that w3 = w2 does not let a later w2 < 9 bound r3, and that the program is therefore rejected. That bound is sound, so the test becomes __success here.
Layout
======
The kinds live in bitfields rather than in the top bits of ->id, as suggested on 1/6:
enum bpf_add_const add_const:2; enum bpf_subreg subreg:2;
bpf_reg_state stays 80 bytes; 20 bits of padding remain.
Patches
=======
1 move the kinds out of ->id [NFC] 2 restore the kind comparison in regs_exact() that 1 drops 3-4 zero-extending mov 5-6 keep the range across a sign extension that cannot change it 7-8 sign-extending mov 9-10 narrowing fill 11 record what a narrowing spill actually stores
12-13 narrowing spill
5 and 11 are precision fixes that stand on their own; they are ordered ahead of the linking patches that build on them.
Testing
=======
clang and bpf-gcc 20260721, x86_64:
clang 129/2594 PASSED, 6 SKIPPED, 0/0 FAILED (-t verifier)
bpf-gcc no new failures against the base
A full test_progs run on both the base and the series gives the same 28 distinct failures, with identical per-test failure counts.
Every patch builds individually.
Changes since the RFC [1]
=========================
6 patches became 13. In aggregate:
- The kinds are bitfields rather than a byte of flags, so RFC 1/6 is gone and RFC 2/6 shrank to patch 1.
- Two precision fixes were split out and ordered ahead of the linking patches that build on them: coerce_reg_to_size_sx() no longer widens a range it cannot change (5), and a narrowing spill records what it stored rather than the wider source (11). Both stand alone.
- Loads are covered, as asked for on the cover letter: the narrowing fill (9-10) and the narrowing spill that feeds it (12-13).
- regs_exact() regained a comparison the RFC lost when the kind left ->id (2).
Four of those differ from what was reviewed and are worth describing in some detail:
- The wide-source mov no longer excludes an ADD_CONST source. This was suggested on 3/6 and it is the right call, but it has a cost:
forming the link clears the source's base+delta relationship, so tracking that used to survive is lost. The two cannot both be kept -- a link the sync path skips would be inert -- and the delta shape is common in the codegen this targets. Patch 3 spells this out, and zext_mov_breaks_add_const_src pins it.
- reconstruct_sext32() does NOT reuse coerce_reg_to_size_sx(), despite that being the explicit ask on 5/6. The RFC's call-then-overwrite is gone -- coerce_reg_to_size_sx() is fixed in patch 5 and the mov site now has a single sign-extension path. But the sync path cannot use it: it reads smin/smax, which straddle after a 32-bit compare and collapse to the full field range, so the link propagates nothing. It needs the base's 32-bit range instead, exactly as zext_32_to_64() does for the zero-extending side. Three tests failed on this before it was understood.
- The sign-extending self-mov is narrower than in the RFC. There, r0 = (s32)r0 was never excluded, because reconstruct_sext32() ran at the mov site to keep the range. Patch 5 now does that job, so the link is formed only when r0 already carries an id -- otherwise there is nothing to link to and minting one would leave the register describing itself.
- Patch 11 tightens the state recorded for every narrowing spill, including programs with no links at all. It is separated out for that reason.
Two notes on the tests:
- The two sign-extension range tests live in verifier_movsx.c rather than verifier_linked_scalars.c, contrary to the request on 4/6. They exercise the range a sign-extending mov produces, not the ->id machinery, and that file already gates on the cpuv4 support they need.
- Three tests that were named *_link_mismatch_blocks_pruning are now named for what they actually check. Disabling the ->subreg comparison in regsafe() does not make them fail: the states they compare differ in ids, contents or ranges, so regsafe() keeps them apart for reasons of its own. They verify an outcome, not that specific guard.
Still open
==========
- The kind comparison in regsafe() has no test that isolates it, like the pre-existing add_const comparison. The shape it guards is old being a superset of cur -- old SUBREG_ZEXT over [0, U32_MAX] against cur SUBREG_SEXT over [0, 100] passes range_within(), and without the comparison a later sync_linked_regs() would rebuild cur by the wrong rule. Whenever the kinds differ in a way a program can construct directly the ranges differ too, so the range checks reject first. Suggestions welcome.
- The fill arm mints an id when spill_size == 4, but the clearing test does not mention spill_size. A narrow value spilled at 8 bytes and filled at 4 therefore inherits a full 64-bit link without the minting gate running. This predates the series; patch 9 builds on that arm without changing it. Is it deliberate?
- regs_exact() loses the kind comparison for exactly one patch, between 1 and 2. They can be folded if the [NFC] label matters more than the bisect step.
Vineet Gupta (13):
bpf: move linked-scalar flags out of bpf_reg_state->id [NFC]
bpf: compare linked-scalar kinds in regs_exact()
bpf: track low-32 scalar equality across zero-extending movs selftests/bpf: cover the low-32 link for zero-extending movs
bpf: keep the range across a sign extension that cannot change it selftests/bpf: cover sign extensions that cannot change the range
bpf: track low-32 scalar equality across sign-extending movs selftests/bpf: cover the low-32 link for sign-extending movs
bpf: track low-32 scalar equality across narrowing stack fills selftests/bpf: cover the low-32 link for narrowing stack fills
bpf: record what a narrowing spill actually stores
bpf: track low-32 scalar equality across narrowing stack spills selftests/bpf: cover the low-32 link for narrowing stack spills
include/linux/bpf_verifier.h | 36 +- include/linux/tnum.h | 3 + kernel/bpf/log.c | 8 +- kernel/bpf/states.c | 38 +- kernel/bpf/tnum.c | 15 + kernel/bpf/verifier.c | 282 ++++++-- tools/testing/selftests/bpf/progs/bpf_misc.h | 8 + .../selftests/bpf/progs/verifier_bounds.c | 2 +- .../bpf/progs/verifier_linked_scalars.c | 653 +++++++++++++++++- .../selftests/bpf/progs/verifier_movsx.c | 51 ++ .../selftests/bpf/progs/verifier_reg_equal.c | 14 +- .../selftests/bpf/progs/verifier_spill_fill.c | 10 +- 12 files changed, 995 insertions(+), 125 deletions(-)
Signature · 1 line
2.53.0-Meta
PATCH v2 1/13 bpf: move linked-scalar flags out of bpf_reg_state->id [NFC]
bpf_reg_state->id doubles as a linked-register id and, in its top two bits, as a record of how the register relates to that set:
#define BPF_ADD_CONST64 (1U << 31) #define BPF_ADD_CONST32 (1U << 30)
Every user of ->id therefore has to mask, and more link kinds are coming. Move the two bits into a bitfield next to ->precise, which is the last field of the struct and outside every memcmp() window used for state comparison, so the layout and all byte-wise comparisons are unchanged. The two kinds are mutually exclusive, so a 2-bit enum captures them and makes ADD_CONST_32 vs ADD_CONST_64 explicit at each use.
->id becomes a plain 32-bit identifier: no masking anywhere, and check_scalar_ids() loses its two-level "check the compound id, then the base id" dance in favour of a single check_ids().
While here, use regs_exact() for the explore_alu_limits case in regsafe():
it is what that open-coded memcmp+check_scalar_ids pair amounts to, and it picks up the add_const comparison for free (parent_id is 0 for SCALAR_VALUE).
check_stack_write_fixed_off() cleared ->id directly on a narrowing spill, which would now leave ->add_const set without an id; use clear_scalar_id().
Moving the kind out of ->id also drops an incidental comparison in regs_exact(), which used to see it as part of the idmap key; the next patch restores it. Otherwise no functional change intended.
---
v2: was RFC 2/6.
- kinds are a 2-bit enum bitfield, not a byte of flags; RFC 1/6, which turned ->precise into that byte, is dropped (Eduard)
- use regs_exact() for the explore_alu_limits case
- clear_scalar_id() on the narrowing spill, which would otherwise leave ->add_const set without an id
include/linux/bpf_verifier.h | 25 ++++++++----- kernel/bpf/log.c | 4 +-- kernel/bpf/states.c | 35 +++++-------------- kernel/bpf/verifier.c | 35 +++++++++++-------- .../bpf/progs/verifier_linked_scalars.c | 34 +++++++++--------- 5 files changed, 65 insertions(+), 68 deletions(-)
include/linux/bpf_verifier.h +17 -8
@@ -35,6 +35,17 @@ enum bpf_iter_state { BPF_ITER_STATE_DRAINED, }; +/* +* Records that a register is (base + ->delta) within its ->id set: +* r1 += 10; r1 gets ADD_CONST_64 delta +* w3 += 10; r3 gets ADD_CONST_32 delta +*/ +enum bpf_add_const { +ADD_CONST_NONE =0 , +ADD_CONST_32 ,/* delta was added with a 32-bit ALU op */ +ADD_CONST_64 ,/* ... with a 64-bit ALU op */ +}; +struct bpf_reg_state {/* Ordering of fields matters. See states_equal() */ enum bpf_reg_type type;
@@ -136,16 +147,9 @@ struct bpf_reg_state {* to a specific instance of bpf_iter. */ /* -* Upper bit of ID is used to remember relationship between "linked" -* registers. Example: +* Registers sharing an ->id are "linked": * r1 = r2; both will have r1->id == r2->id == N -* r1 += 10; r1->id == N | BPF_ADD_CONST and r1->delta == 10 -* r3 = r2; both will have r3->id == r2->id == N -* w3 += 10; r3->id == N | BPF_ADD_CONST32 and r3->delta == 10 */ -#define BPF_ADD_CONST64 (1U << 31) -#define BPF_ADD_CONST32 (1U << 30) -#define BPF_ADD_CONST (BPF_ADD_CONST64 | BPF_ADD_CONST32)u32 id;/* * Tracks the parent object this register was derived from.
@@ -164,6 +168,11 @@ struct bpf_reg_state {u32 frameno;/* if (!precise && SCALAR_VALUE) min/max/tnum don't affect safety */ bool precise; +/* +* How this register relates to the others sharing its ->id. +* Non-zero only if ->id is. +*/ + enum bpf_add_const add_const:2; };static inline s64 reg_smin (const struct bpf_reg_state *reg)
kernel/bpf/log.c +2 -2
@@ -651,8 +651,8 @@ static void print_reg_state(struct bpf_verifier_env *env,verbose (env,"%s" ,btf_type_name (reg->btf, reg->btf_id));verbose (env,"(" );if (reg->id) -verbose_a ("id=%d" , reg->id & ~BPF_ADD_CONST ); -if (reg->id &BPF_ADD_CONST ) +verbose_a ("id=%d" , reg->id); +if (reg->add_const)verbose (env,"%+d" , reg->delta);if (reg->parent_id)verbose_a ("parent_id=%d" , reg->parent_id);
kernel/bpf/states.c +9 -26
@@ -369,13 +369,6 @@ static bool check_ids(u32 old_id, u32 cur_id, struct bpf_idmap *idmap)* and r7.id=0 (both independent), without temp IDs both would map old_id=X * to cur_id=0 and pass. With temp IDs: r6 maps X->temp1, r7 tries to map * X->temp2, but X is already mapped to temp1, so the check fails correctly. -* -* When old_id has BPF_ADD_CONST set, the compound id (base | flag) and the -* base id (flag stripped) must both map consistently. Example: old has -* r2.id=A, r3.id=A|flag (r3 = r2 + delta), cur has r2.id=B, r3.id=C|flag -* (r3 derived from unrelated r4). Without the base check, idmap gets two -* independent entries A->B and A|flag->C|flag, missing that A->C conflicts -* with A->B. The base ID cross-check catches this. */ static bool check_scalar_ids (u32 old_id,u32 cur_id,struct bpf_idmap *idmap) {
@@ -384,15 +377,7 @@ static bool check_scalar_ids(u32 old_id, u32 cur_id, struct bpf_idmap *idmap) cur_id = cur_id ? cur_id : ++idmap->tmp_id_gen; -if (!check_ids (old_id, cur_id, idmap)) -return false; -if (old_id &BPF_ADD_CONST ) { - old_id &= ~BPF_ADD_CONST ; - cur_id &= ~BPF_ADD_CONST ; -if (!check_ids (old_id, cur_id, idmap)) -return false; - } -return true; +return check_ids (old_id, cur_id, idmap); } static void __clean_func_state(struct bpf_verifier_env *env,
@@ -542,8 +527,7 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,/* explore_alu_limits disables tnum_in() and range_within() * logic and requires everything to be strict */ -return memcmp (rold, rcur, offsetof(struct bpf_reg_state , id)) ==0 && -check_scalar_ids (rold->id, rcur->id, idmap); +return regs_exact (rold, rcur, idmap); }if (!rold->precise && exact ==NOT_EXACT )return true;
@@ -551,7 +535,8 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,* Linked register tracking uses rold->id to detect relationships. * When rold->id == 0, the register is independent and any linking * in rcur only adds constraints. When rold->id != 0, we must verify -* id mapping and (for BPF_ADD_CONST) offset consistency. +* id mapping and that the link kinds agree, along with any delta +* they carry. * * +------------------+-----------+------------------+---------------+ * | | rold->id | rold + ADD_CONST | rold->id == 0 |
@@ -587,17 +572,15 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,*/ /* -* ADD_CONST flags must match exactly: BPF_ADD_CONST32 and -* BPF_ADD_CONST64 have different linking semantics in -* sync_linked_regs() (alu32 zero-extends, alu64 does not), -* so pruning across different flag types is unsafe. +* The link kinds must match: alu32 and alu64 adds have different +* linking semantics in sync_linked_regs() (alu32 zero-extends, +* alu64 does not), so pruning across them is unsafe. */ -if (rold->id && - (rold->id &BPF_ADD_CONST ) != (rcur->id &BPF_ADD_CONST )) +if (rold->id && rold->add_const != rcur->add_const)return false;/* Both have offset linkage: offsets must match */ -if ((rold->id &BPF_ADD_CONST ) && rold->delta != rcur->delta) +if (rold->add_const && rold->delta != rcur->delta)return false;if (!check_scalar_ids (rold->id, rcur->id, idmap))
kernel/bpf/verifier.c +20 -15
@@ -1907,6 +1907,7 @@ static void __mark_reg_known(struct bpf_reg_state *reg, u64 imm) offsetof(struct bpf_reg_state, var_off) - sizeof(reg->type)); reg->id =0 ; reg->parent_id =0 ; + reg->add_const =ADD_CONST_NONE ;___mark_reg_known (reg, imm); }
@@ -3480,6 +3481,7 @@ static void clear_scalar_id(struct bpf_reg_state *reg) { reg->id =0 ; reg->delta =0 ; + reg->add_const =ADD_CONST_NONE ; } static void assign_scalar_id_before_mov(struct bpf_verifier_env *env,
@@ -3492,7 +3494,7 @@ static void assign_scalar_id_before_mov(struct bpf_verifier_env *env,* rY->id has special linked register already. * Cleared it, since multiple rX += const are not supported. */ -if (src_reg->id &BPF_ADD_CONST ) +if (src_reg->add_const)clear_scalar_id (src_reg);/* * Ensure that src_reg has a valid ID that will be copied to
@@ -3642,7 +3644,7 @@ static int check_stack_write_fixed_off(struct bpf_verifier_env *env,save_register_state (env, state, spi, reg, size);/* Break the relation on a narrowing spill. */ if (!reg_value_fits) - state->stack[spi].spilled_ptr.id =0 ; +clear_scalar_id (&state->stack[spi].spilled_ptr); }else if (!reg && !(off %BPF_REG_SIZE ) &&is_bpf_st_mem (insn) && env->bpf_capable) {struct bpf_reg_state *tmp_reg = &env->fake_reg[0 ];
@@ -16117,7 +16119,7 @@ static int adjust_reg_min_max_vals(struct bpf_verifier_env *env, off = -off; } -if (dst_reg->id &BPF_ADD_CONST ) { +if (dst_reg->add_const) {/* * If the register already went through rX += val * we cannot accumulate another val into rx->off.
@@ -16126,9 +16128,9 @@ static int adjust_reg_min_max_vals(struct bpf_verifier_env *env,clear_scalar_id (dst_reg); }else {if (alu32) - dst_reg->id |=BPF_ADD_CONST32 ; + dst_reg->add_const =ADD_CONST_32 ;else - dst_reg->id |=BPF_ADD_CONST64 ; + dst_reg->add_const =ADD_CONST_64 ; dst_reg->delta = off; } }else {
@@ -17067,7 +17069,7 @@ static void __collect_linked_regs(struct linked_regs *reg_set, struct bpf_reg_st {struct linked_reg *e; -if (reg->type !=SCALAR_VALUE || (reg->id & ~BPF_ADD_CONST ) != id) +if (reg->type !=SCALAR_VALUE || reg->id != id)return ; e =linked_regs_push (reg_set);
@@ -17095,7 +17097,6 @@ static void collect_linked_regs(struct bpf_verifier_env *env,u16 live_regs;int i, j; - id = id & ~BPF_ADD_CONST ;for (i = vstate->curframe; i >=0 ; i--) { live_regs = aux[bpf_frame_insn_idx (vstate, i)].live_regs_before; func = vstate->frame[i];
@@ -17131,18 +17132,20 @@ static void sync_linked_regs(struct bpf_verifier_env *env, struct bpf_verifier_s : &vstate->frame[e->frameno]->stack[e->spi].spilled_ptr;if (reg->type !=SCALAR_VALUE || reg == known_reg)continue ; -if ((reg->id & ~BPF_ADD_CONST ) != (known_reg->id & ~BPF_ADD_CONST )) +if (reg->id != known_reg->id)continue ;/* * Skip mixed 32/64-bit links: the delta relationship doesn't * hold across different ALU widths. */ -if (((reg->id ^ known_reg->id) &BPF_ADD_CONST ) ==BPF_ADD_CONST ) +if (reg->add_const && known_reg->add_const && + reg->add_const != known_reg->add_const)continue ; -if ((!(reg->id &BPF_ADD_CONST ) && !(known_reg->id &BPF_ADD_CONST )) || +if ((!reg->add_const && !known_reg->add_const) || reg->delta == known_reg->delta) { *reg = *known_reg; }else { +enum bpf_add_const saved_add_const = reg->add_const;s32 saved_off = reg->delta;u32 saved_id = reg->id;
@@ -17152,16 +17155,18 @@ static void sync_linked_regs(struct bpf_verifier_env *env, struct bpf_verifier_s/* reg = known_reg; reg += delta */ *reg = *known_reg;/* -* Must preserve off and id, otherwise another sync_linked_regs() -* will be incorrect. +* Must preserve off, id and add_const, otherwise another +* sync_linked_regs() will be incorrect. */ reg->delta = saved_off; reg->id = saved_id; + reg->add_const = saved_add_const;scalar32_min_max_add (reg, &fake_reg);scalar_min_max_add (reg, &fake_reg); reg->var_off =tnum_add (reg->var_off, fake_reg.var_off); -if ((reg->id | known_reg->id) &BPF_ADD_CONST32 ) +if (reg->add_const ==ADD_CONST_32 || + known_reg->add_const ==ADD_CONST_32 )zext_32_to_64 (reg);reg_bounds_sync (reg); }
@@ -18255,7 +18260,7 @@ void bpf_clear_singular_ids(struct bpf_verifier_env *env,continue ;if (!reg->id)continue ; -idset_cnt_inc (idset, reg->id & ~BPF_ADD_CONST ); +idset_cnt_inc (idset, reg->id); })); bpf_for_each_reg_in_vstate(st, func, reg, ({
@@ -18263,7 +18268,7 @@ void bpf_clear_singular_ids(struct bpf_verifier_env *env,continue ;if (!reg->id)continue ; -if (idset_cnt_get (idset, reg->id & ~BPF_ADD_CONST ) ==1 ) +if (idset_cnt_get (idset, reg->id) ==1 )clear_scalar_id (reg); })); }
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +17 -17
@@ -349,8 +349,8 @@ l0_%=: \ }/* -* Test that sync_linked_regs() checks reg->id (the linked target register) -* for BPF_ADD_CONST32 rather than known_reg->id (the branch register). +* Test that sync_linked_regs() checks the linked target register (reg) for +* ADD_CONST_32 rather than the branch register (known_reg). */ SEC ("socket" ) __success
@@ -360,7 +360,7 @@ __naked void scalars_alu32_zext_linked_reg(void) call %[bpf_get_prandom_u32]; \ w6 = w0;/* r6 in [0, 0xFFFFFFFF] */ \ r7 = r6;/* linked: same id as r6 */ \ - w7 +=1 ;/* alu32: r7.id |= BPF_ADD_CONST32 */ \ + w7 +=1 ;/* ADD_CONST_32 delta */ \ r8 = 0xFFFFffff ll; \ if r6 < r8 goto l0_%=; \/* r6 in [0xFFFFFFFF, 0xFFFFFFFF] */ \
@@ -381,7 +381,7 @@ l0_%=: \/* * Test that sync_linked_regs() skips propagation when one register used -* alu32 (BPF_ADD_CONST32) and the other used alu64 (BPF_ADD_CONST64). +* alu32 (ADD_CONST_32) and the other used alu64 (ADD_CONST_64). * The delta relationship doesn't hold across different ALU widths. */ SEC ("socket" )
@@ -392,13 +392,13 @@ __naked void scalars_alu32_alu64_cross_type(void) call %[bpf_get_prandom_u32]; \ w6 = w0;/* r6 in [0, 0xFFFFFFFF] */ \ r7 = r6;/* linked: same id as r6 */ \ - w7 +=1 ;/* alu32: BPF_ADD_CONST32, delta = 1 */ \ + w7 +=1 ;/* ADD_CONST_32 delta */ \ r8 = r6;/* linked: same id as r6 */ \ - r8 +=2 ;/* alu64: BPF_ADD_CONST64, delta = 2 */ \ + r8 +=2 ;/* ADD_CONST_64 delta */ \ r9 = 0xFFFFffff ll; \ if r7 < r9 goto l0_%=; \/* r7 = 0xFFFFFFFF */ \ -/* sync: known_reg=r7 (ADD_CONST32), reg=r8 (ADD_CONST64) */ \ +/* sync: known_reg=r7 (ADD_CONST_32), reg=r8 (ADD_CONST_64) */ \/* Without fix: r8 = zext(0xFFFFFFFF + 1) = 0 */ \/* With fix: r8 stays [2, 0x100000001] (r8 >= 2) */ \ if r8 > 0 goto l1_%=; \
@@ -416,7 +416,7 @@ l0_%=: \/* * Test that regsafe() prevents pruning when two paths reach the same program * point with linked registers carrying different ADD_CONST flags (one -* BPF_ADD_CONST32 from alu32, another BPF_ADD_CONST64 from alu64). +* ADD_CONST_32 from alu32, another ADD_CONST_64 from alu64). */ SEC("socket") __failure __msg("div by zero")
@@ -431,11 +431,11 @@ __naked void scalars_alu32_alu64_regsafe_pruning(void) call %[bpf_get_prandom_u32]; \ if r0 > 0 goto l_pathb_%=; \/* Path A: alu32 */ \ - w7 +=1 ;/* BPF_ADD_CONST32, delta = 1 */ \ + w7 +=1 ;/* ADD_CONST_32 delta */ \ goto l_merge_%=; \ l_pathb_%=: \/* Path B: alu64 */ \ - r7 +=1 ;/* BPF_ADD_CONST64, delta = 1 */ \ + r7 +=1 ;/* ADD_CONST_64 delta */ \ l_merge_%=: \/* Merge point: regsafe() compares path B against cached path A. */ \/* Narrow r6 to trigger sync_linked_regs for r7 */ \
@@ -593,7 +593,7 @@ l_exit_%=: \ }/* -* Test that stale delta from a cleared BPF_ADD_CONST does not leak +* Test that stale delta from a cleared ADD_CONST_* does not leak * through assign_scalar_id_before_mov() into a new id, causing * sync_linked_regs() to compute an incorrect offset. */
@@ -605,10 +605,10 @@ __naked void scalars_stale_delta_from_cleared_id(void) asm volatile (" \ call %[bpf_get_prandom_u32]; \ r6 = r0; /* r6 unknown, gets id A */ \ - r6 += 5; /* id A|ADD_CONST, delta 5 */ \ + r6 += 5; /* id A, ADD_CONST_64 delta */ \ r6 ^= 0; /* id cleared; delta stays 5 */ \ r8 = r6; /* new id B, stale delta 5 */ \ - r8 += 3; /* id B|ADD_CONST, delta 3 */ \ + r8 += 3; /* id B, ADD_CONST_64 delta */ \ r9 = r6; /* id B, stale delta 5 */ \ if r9 != 10 goto l_exit_%=; \ /* Bug: r8 = 10+(3-5) = 8; Fix: r8 = 10+(3-0) = 13 */ \
@@ -648,10 +648,10 @@ l_exit_%=: \ }/* -* Test that regsafe() verifies base_id consistency for BPF_ADD_CONST +* Test that regsafe() verifies base_id consistency for ADD_CONST_* * linked scalars during state pruning. * -* The false branch (explored first) links R3 to R2 via ADD_CONST. +* The false branch (explored first) links R3 to R2 via ADD_CONST_64. * The true branch (runtime path) links R3 to R4 (unrelated base_id). * At the merge point, pruning must fail because the linkage topology * differs.
@@ -675,7 +675,7 @@ __naked void add_const_base_id_pruning(void) r2 = r0; \ r2 &=0xff ;/* R2 = scalar(id=A) [0,255] */ \ r3 = r2;/* R3 linked to R2 (id=A) */ \ - r3 +=10 ;/* R3 id=A|ADD_CONST, delta=10 */ \ + r3 +=10 ;/* ADD_CONST_64 delta */ \ r6 =0 ; \ goto l_merge_%=; \ \
@@ -687,7 +687,7 @@ l_true_%=: \ r4 = r0; \ r4 &=0xff ;/* R4 = scalar [0,255], id=0 */ \ r3 = r4;/* R3 linked to R4 (new id=C) */ \ - r3 +=10 ;/* R3 id=C|ADD_CONST, delta=10 */ \ + r3 +=10 ;/* ADD_CONST_64 delta */ \ r6 =0 ; \ \ l_merge_%=: \
Signature · 1 line
2.53.0-Meta
[email protected]
AI reviewRe: [PATCH bpf-next v2 01/13] bpf: move linked-scalar flags out of bpf_reg_state->id [NFC]
Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider: - [Medium] Unintentional stricter pruning in explore_alu_limits mode causing state explosion. --
Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
- [Medium] Unintentional stricter pruning in explore_alu_limits mode causing state explosion. --
commit aa1d987a87f62f32dd84baa98f047ffd7635c40e
Author: Vineet Gupta <[email protected]>
bpf: move linked-scalar flags out of bpf_reg_state->id [NFC]
This commit moves the linked-scalar flags (ADD_CONST32 and ADD_CONST64) out of the bpf_reg_state->id field and into a separate add_const bitfield. This simplifies ID tracking by removing the need to mask the ID during checks.
Quoted 4 lines
kernel/bpf/states.c +0
-0
[ ... ]
kernel/bpf/states.c static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold, · line 531
Quoted 8 lines
kernel/bpf/states.c +1
-2@@ -542,8 +527,7 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,/* explore_alu_limits disables tnum_in() and range_within() * logic and requires everything to be strict */ -return memcmp (rold, rcur, offsetof(struct bpf_reg_state , id)) ==0 && -check_scalar_ids (rold->id, rcur->id, idmap); +return regs_exact (rold, rcur, idmap); }
[Severity: Medium]
Does this unintentionally introduce a stricter pruning check when explore_alu_limits is active?
The commit message notes that using regs_exact() amounts to the same as the open-coded memcmp plus check_scalar_ids() pair. However, check_scalar_ids() allows old_id to be 0 by returning true immediately (ignoring cur_id):
if (!old_id) return true;
On the other hand, regs_exact() calls check_ids(), which strictly enforces that both IDs are either zero or non-zero, and fails if they differ:
/* either both IDs should be set or both should be zero */ if (!!old_id != !!cur_id) return false;
When env->explore_alu_limits is true, comparing two equivalent scalar registers where one is unlinked (ID == 0) and the other is linked (ID != 0) would pass previously but fails now, potentially causing state explosion.
Signature · 1 line
Sashiko AI review · https://sashiko.dev/#/patchset/[email protected]?part=1
Re: [PATCH bpf-next v2 01/13] bpf: move linked-scalar flags out of bpf_reg_state->id [NFC]
Quoted 41 lines · On 9/10/26 10:30 PM, [email protected] wrote:
Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
- [Medium] Unintentional stricter pruning inexplore_alu_limitsmode causing state explosion. --commit
aa1d987a87f62f32dd84baa98f047ffd7635c40e
Author: Vineet Gupta <[email protected]>bpf: move linked-scalar flags out of
bpf_reg_state->id[NFC]This commit moves the linked-scalar flags (
ADD_CONST32andADD_CONST64) out of thebpf_reg_state->idfield and into a separateadd_constbitfield. This simplifies ID tracking by removing the need to mask the ID during checks.Quoted 4 lines
kernel/bpf/states.c +0
-0[ ... ]
kernel/bpf/states.c static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold, · line 531
Quoted 8 lines
kernel/bpf/states.c +1
-2@@ -542,8 +527,7 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,/* explore_alu_limits disables tnum_in() and range_within() * logic and requires everything to be strict */ -return memcmp (rold, rcur, offsetof(struct bpf_reg_state , id)) ==0 && -check_scalar_ids (rold->id, rcur->id, idmap); +return regs_exact (rold, rcur, idmap); }[Severity: Medium]
Does this unintentionally introduce a stricter pruning check whenexplore_alu_limitsis active?The commit message notes that using
regs_exact()amounts to the same as the open-coded memcmp pluscheck_scalar_ids()pair. However,check_scalar_ids()allowsold_idto be 0 by returning true immediately (ignoringcur_id):if (!old_id) return true;On the other hand,
regs_exact()callscheck_ids(), which strictly enforces that both IDs are either zero or non-zero, and fails if they differ:
Quoted 7 lines
/* either both IDs should be set or both should be zero */ if (!!old_id != !!cur_id) return false;When
env->explore_alu_limitsis true, comparing two equivalent scalar registers where one is unlinked (ID == 0) and the other is linked (ID != 0) would pass previously but fails now, potentially causing state explosion.
The regs_exact() replacement was suggested in RFC review. And it is true it can be tighter.
Since the rest of series changes behavior anyways, I'm inclined towards dropping the NFC and document the change. And if we go down this part, perhaps patch 2 can also be folded into this one as that was the sole reason for breaking it out.
Thx,
-Vineet
[email protected]
AI reviewRe: [PATCH bpf-next v2 01/13] bpf: move linked-scalar flags out of bpf_reg_state->id [NFC]
In reply to Vineet GuptaDoes this comment still match what the code does? The patch removes the "base_id" concept from kernel/bpf/states.c (deleted the paragraph that defined it, removed the two-level compound/base id…
Quoted 4 lines
kernel/bpf/states.c +0
-0
[ ... ]
Quoted 29 lines
kernel/bpf/states.c +1
-16@@ -369,13 +369,6 @@ static bool check_ids(u32 old_id, u32 cur_id, struct bpf_idmap *idmap)* and r7.id=0 (both independent), without temp IDs both would map old_id=X * to cur_id=0 and pass. With temp IDs: r6 maps X->temp1, r7 tries to map * X->temp2, but X is already mapped to temp1, so the check fails correctly. -* -* When old_id has BPF_ADD_CONST set, the compound id (base | flag) and the -* base id (flag stripped) must both map consistently. Example: old has -* r2.id=A, r3.id=A|flag (r3 = r2 + delta), cur has r2.id=B, r3.id=C|flag -* (r3 derived from unrelated r4). Without the base check, idmap gets two -* independent entries A->B and A|flag->C|flag, missing that A->C conflicts -* with A->B. The base ID cross-check catches this. */ static bool check_scalar_ids (u32 old_id,u32 cur_id,struct bpf_idmap *idmap) {@@ -384,15 +377,7 @@ static bool check_scalar_ids(u32 old_id, u32 cur_id, struct bpf_idmap *idmap) cur_id = cur_id ? cur_id : ++idmap->tmp_id_gen; -if (!check_ids (old_id, cur_id, idmap)) -return false; -if (old_id &BPF_ADD_CONST ) { - old_id &= ~BPF_ADD_CONST ; - cur_id &= ~BPF_ADD_CONST ; -if (!check_ids (old_id, cur_id, idmap)) -return false; - } -return true; +return check_ids (old_id, cur_id, idmap); }
[ ... ]
Quoted 4 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +0
-0
[ ... ]
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c l_exit_%=: \ · line 657
Quoted 13 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +2
-2@@ -648,10 +648,10 @@ l_exit_%=: \ }/* -* Test that regsafe() verifies base_id consistency for BPF_ADD_CONST +* Test that regsafe() verifies base_id consistency for ADD_CONST_* * linked scalars during state pruning. * -* The false branch (explored first) links R3 to R2 via ADD_CONST. +* The false branch (explored first) links R3 to R2 via ADD_CONST_64. * The true branch (runtime path) links R3 to R4 (unrelated base_id). * At the merge point, pruning must fail because the linkage topology * differs.
Does this comment still match what the code does? The patch removes the "base_id" concept from kernel/bpf/states.c (deleted the paragraph that defined it, removed the two-level compound/base id check from check_scalar_ids), but the comment here still describes the test as verifying "base_id consistency" and refers to "unrelated base_id" on the next line.
Looking at the function name and __description below:
Quoted 4 lines
*/
__description("add_const base_id must be consistent for pruning")__failure__msg("invalid variable-offset")
__nakedvoidadd_const_base_id_pruning(void)
and later at line 695:
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c
Quoted 2 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +0
-0/* Runtime: R2.id=A, R4.id=C: base_ids A vs C inconsistent, * pruning should have failed. */
Should these be updated to use current terminology, or does "base_id" still have meaning in this context? The test itself still works correctly after the patch, so this appears to be a documentation consistency question rather than a functional issue.
---
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/34506184282
Re: [PATCH bpf-next v2 01/13] bpf: move linked-scalar flags out of bpf_reg_state->id [NFC]
Quoted 69 lines · On 9/10/26 11:22 PM, [email protected] wrote:
Quoted 4 lines
kernel/bpf/states.c +0
-0[ ... ]
Quoted 29 lines
kernel/bpf/states.c +1
-16@@ -369,13 +369,6 @@ static bool check_ids(u32 old_id, u32 cur_id, struct bpf_idmap *idmap)* and r7.id=0 (both independent), without temp IDs both would map old_id=X * to cur_id=0 and pass. With temp IDs: r6 maps X->temp1, r7 tries to map * X->temp2, but X is already mapped to temp1, so the check fails correctly. -* -* When old_id has BPF_ADD_CONST set, the compound id (base | flag) and the -* base id (flag stripped) must both map consistently. Example: old has -* r2.id=A, r3.id=A|flag (r3 = r2 + delta), cur has r2.id=B, r3.id=C|flag -* (r3 derived from unrelated r4). Without the base check, idmap gets two -* independent entries A->B and A|flag->C|flag, missing that A->C conflicts -* with A->B. The base ID cross-check catches this. */ static bool check_scalar_ids (u32 old_id,u32 cur_id,struct bpf_idmap *idmap) {@@ -384,15 +377,7 @@ static bool check_scalar_ids(u32 old_id, u32 cur_id, struct bpf_idmap *idmap) cur_id = cur_id ? cur_id : ++idmap->tmp_id_gen; -if (!check_ids (old_id, cur_id, idmap)) -return false; -if (old_id &BPF_ADD_CONST ) { - old_id &= ~BPF_ADD_CONST ; - cur_id &= ~BPF_ADD_CONST ; -if (!check_ids (old_id, cur_id, idmap)) -return false; - } -return true; +return check_ids (old_id, cur_id, idmap); }[ ... ]
Quoted 4 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +0
-0[ ... ]
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c l_exit_%=: \ · line 657
Quoted 13 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +2
-2@@ -648,10 +648,10 @@ l_exit_%=: \ }/* -* Test that regsafe() verifies base_id consistency for BPF_ADD_CONST +* Test that regsafe() verifies base_id consistency for ADD_CONST_* * linked scalars during state pruning. * -* The false branch (explored first) links R3 to R2 via ADD_CONST. +* The false branch (explored first) links R3 to R2 via ADD_CONST_64. * The true branch (runtime path) links R3 to R4 (unrelated base_id). * At the merge point, pruning must fail because the linkage topology * differs. Does this comment still match what the code does? The patch removes the "
base_id" concept fromkernel/bpf/states.c(deleted the paragraph that defined it, removed the two-level compound/base id check fromcheck_scalar_ids), but the comment here still describes the test as verifying "base_idconsistency" and refers to "unrelatedbase_id" on the next line.Looking at the function name and
__descriptionbelow:Quoted 4 lines
*/
__description("add_const base_id must be consistent for pruning")__failure__msg("invalid variable-offset")
__nakedvoidadd_const_base_id_pruning(void)
Quoted 8 lines
and later at line 695:
Quoted 2 lines
/* Runtime: R2.id=A, R4.id=C:
base_idsA vs C inconsistent,
* pruning should have failed. */Should these be updated to use current terminology, or does "
base_id" still have meaning in this context? The test itself still works correctly after the patch, so this appears to be a documentation consistency question rather than a functional issue.
Indeed base_id as a term is gone, but just id alone might be confusing as well. How about link id as a replacement for base_id
-Vineet
Quoted 7 lines
---
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.mdCI run summary: https://github.com/kernel-patches/bpf/actions/runs/34506184282
Re: [PATCH bpf-next v2 01/13] bpf: move linked-scalar flags out of bpf_reg_state->id [NFC]
Quoted 76 lines · Vineet Gupta
Quoted 73 lines · On 9/10/26 11:22 PM, [email protected] wrote:
Quoted 4 lines
kernel/bpf/states.c +0
-0[ ... ]
Quoted 29 lines
kernel/bpf/states.c +1
-16@@ -369,13 +369,6 @@ static bool check_ids(u32 old_id, u32 cur_id, struct bpf_idmap *idmap)* and r7.id=0 (both independent), without temp IDs both would map old_id=X * to cur_id=0 and pass. With temp IDs: r6 maps X->temp1, r7 tries to map * X->temp2, but X is already mapped to temp1, so the check fails correctly. -* -* When old_id has BPF_ADD_CONST set, the compound id (base | flag) and the -* base id (flag stripped) must both map consistently. Example: old has -* r2.id=A, r3.id=A|flag (r3 = r2 + delta), cur has r2.id=B, r3.id=C|flag -* (r3 derived from unrelated r4). Without the base check, idmap gets two -* independent entries A->B and A|flag->C|flag, missing that A->C conflicts -* with A->B. The base ID cross-check catches this. */ static bool check_scalar_ids (u32 old_id,u32 cur_id,struct bpf_idmap *idmap) {@@ -384,15 +377,7 @@ static bool check_scalar_ids(u32 old_id, u32 cur_id, struct bpf_idmap *idmap) cur_id = cur_id ? cur_id : ++idmap->tmp_id_gen; -if (!check_ids (old_id, cur_id, idmap)) -return false; -if (old_id &BPF_ADD_CONST ) { - old_id &= ~BPF_ADD_CONST ; - cur_id &= ~BPF_ADD_CONST ; -if (!check_ids (old_id, cur_id, idmap)) -return false; - } -return true; +return check_ids (old_id, cur_id, idmap); }[ ... ]
Quoted 4 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +0
-0[ ... ]
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c l_exit_%=: \ · line 657
Quoted 13 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +2
-2@@ -648,10 +648,10 @@ l_exit_%=: \ }/* -* Test that regsafe() verifies base_id consistency for BPF_ADD_CONST +* Test that regsafe() verifies base_id consistency for ADD_CONST_* * linked scalars during state pruning. * -* The false branch (explored first) links R3 to R2 via ADD_CONST. +* The false branch (explored first) links R3 to R2 via ADD_CONST_64. * The true branch (runtime path) links R3 to R4 (unrelated base_id). * At the merge point, pruning must fail because the linkage topology * differs. Does this comment still match what the code does? The patch removes the "
base_id" concept fromkernel/bpf/states.c(deleted the paragraph that defined it, removed the two-level compound/base id check fromcheck_scalar_ids), but the comment here still describes the test as verifying "base_idconsistency" and refers to "unrelatedbase_id" on the next line.Looking at the function name and
__descriptionbelow:Quoted 4 lines
*/
__description("add_const base_id must be consistent for pruning")__failure__msg("invalid variable-offset")
__nakedvoidadd_const_base_id_pruning(void)and later at line 695:
Quoted 2 lines
/* Runtime: R2.id=A, R4.id=C:
base_idsA vs C inconsistent,
* pruning should have failed. */
Quoted 8 lines
Quoted 4 lines
Should these be updated to use current terminology, or does "
base_id" still have meaning in this context? The test itself still works correctly after the patch, so this appears to be a documentation consistency question rather than a functional issue.Indeed
base_idas a term is gone, but just id alone might be confusing as well.
How about link id as a replacement forbase_id
I don't think "link id" fits either. Just use id.
Re: [PATCH bpf-next v2 01/13] bpf: move linked-scalar flags out of bpf_reg_state->id [NFC]
Quoted 76 lines · Alexei Starovoitov
Quoted 75 lines · Vineet Gupta
Quoted 73 lines · On 9/10/26 11:22 PM, [email protected] wrote:
Quoted 4 lines
kernel/bpf/states.c +0
-0[ ... ]
Quoted 29 lines
kernel/bpf/states.c +1
-16@@ -369,13 +369,6 @@ static bool check_ids(u32 old_id, u32 cur_id, struct bpf_idmap *idmap)* and r7.id=0 (both independent), without temp IDs both would map old_id=X * to cur_id=0 and pass. With temp IDs: r6 maps X->temp1, r7 tries to map * X->temp2, but X is already mapped to temp1, so the check fails correctly. -* -* When old_id has BPF_ADD_CONST set, the compound id (base | flag) and the -* base id (flag stripped) must both map consistently. Example: old has -* r2.id=A, r3.id=A|flag (r3 = r2 + delta), cur has r2.id=B, r3.id=C|flag -* (r3 derived from unrelated r4). Without the base check, idmap gets two -* independent entries A->B and A|flag->C|flag, missing that A->C conflicts -* with A->B. The base ID cross-check catches this. */ static bool check_scalar_ids (u32 old_id,u32 cur_id,struct bpf_idmap *idmap) {@@ -384,15 +377,7 @@ static bool check_scalar_ids(u32 old_id, u32 cur_id, struct bpf_idmap *idmap) cur_id = cur_id ? cur_id : ++idmap->tmp_id_gen; -if (!check_ids (old_id, cur_id, idmap)) -return false; -if (old_id &BPF_ADD_CONST ) { - old_id &= ~BPF_ADD_CONST ; - cur_id &= ~BPF_ADD_CONST ; -if (!check_ids (old_id, cur_id, idmap)) -return false; - } -return true; +return check_ids (old_id, cur_id, idmap); }[ ... ]
Quoted 4 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +0
-0[ ... ]
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c l_exit_%=: \ · line 657
Quoted 13 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +2
-2@@ -648,10 +648,10 @@ l_exit_%=: \ }/* -* Test that regsafe() verifies base_id consistency for BPF_ADD_CONST +* Test that regsafe() verifies base_id consistency for ADD_CONST_* * linked scalars during state pruning. * -* The false branch (explored first) links R3 to R2 via ADD_CONST. +* The false branch (explored first) links R3 to R2 via ADD_CONST_64. * The true branch (runtime path) links R3 to R4 (unrelated base_id). * At the merge point, pruning must fail because the linkage topology * differs. Does this comment still match what the code does? The patch removes the "
base_id" concept fromkernel/bpf/states.c(deleted the paragraph that defined it, removed the two-level compound/base id check fromcheck_scalar_ids), but the comment here still describes the test as verifying "base_idconsistency" and refers to "unrelatedbase_id" on the next line.Looking at the function name and
__descriptionbelow:Quoted 4 lines
*/
__description("add_const base_id must be consistent for pruning")__failure__msg("invalid variable-offset")
__nakedvoidadd_const_base_id_pruning(void)and later at line 695:
Quoted 2 lines
/* Runtime: R2.id=A, R4.id=C:
base_idsA vs C inconsistent,
* pruning should have failed. */
Quoted 8 lines
Quoted 7 lines
Quoted 4 lines
Should these be updated to use current terminology, or does "
base_id" still have meaning in this context? The test itself still works correctly after the patch, so this appears to be a documentation consistency question rather than a functional issue.Indeed
base_idas a term is gone, but just id alone might be confusing as well.
How about link id as a replacement forbase_idI don't think "link id" fits either. Just use id.
SG !
Thx,
-Vineet
Re: [PATCH bpf-next v2 01/13] bpf: move linked-scalar flags out of bpf_reg_state->id [NFC]
In reply to Alexei StarovoitovQuoted 76 lines · Alexei Starovoitov
Quoted 75 lines · Vineet Gupta
Quoted 73 lines · On 9/10/26 11:22 PM, [email protected] wrote:
Quoted 4 lines
kernel/bpf/states.c +0
-0[ ... ]
Quoted 29 lines
kernel/bpf/states.c +1
-16@@ -369,13 +369,6 @@ static bool check_ids(u32 old_id, u32 cur_id, struct bpf_idmap *idmap)* and r7.id=0 (both independent), without temp IDs both would map old_id=X * to cur_id=0 and pass. With temp IDs: r6 maps X->temp1, r7 tries to map * X->temp2, but X is already mapped to temp1, so the check fails correctly. -* -* When old_id has BPF_ADD_CONST set, the compound id (base | flag) and the -* base id (flag stripped) must both map consistently. Example: old has -* r2.id=A, r3.id=A|flag (r3 = r2 + delta), cur has r2.id=B, r3.id=C|flag -* (r3 derived from unrelated r4). Without the base check, idmap gets two -* independent entries A->B and A|flag->C|flag, missing that A->C conflicts -* with A->B. The base ID cross-check catches this. */ static bool check_scalar_ids (u32 old_id,u32 cur_id,struct bpf_idmap *idmap) {@@ -384,15 +377,7 @@ static bool check_scalar_ids(u32 old_id, u32 cur_id, struct bpf_idmap *idmap) cur_id = cur_id ? cur_id : ++idmap->tmp_id_gen; -if (!check_ids (old_id, cur_id, idmap)) -return false; -if (old_id &BPF_ADD_CONST ) { - old_id &= ~BPF_ADD_CONST ; - cur_id &= ~BPF_ADD_CONST ; -if (!check_ids (old_id, cur_id, idmap)) -return false; - } -return true; +return check_ids (old_id, cur_id, idmap); }[ ... ]
Quoted 4 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +0
-0[ ... ]
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c l_exit_%=: \ · line 657
Quoted 13 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +2
-2@@ -648,10 +648,10 @@ l_exit_%=: \ }/* -* Test that regsafe() verifies base_id consistency for BPF_ADD_CONST +* Test that regsafe() verifies base_id consistency for ADD_CONST_* * linked scalars during state pruning. * -* The false branch (explored first) links R3 to R2 via ADD_CONST. +* The false branch (explored first) links R3 to R2 via ADD_CONST_64. * The true branch (runtime path) links R3 to R4 (unrelated base_id). * At the merge point, pruning must fail because the linkage topology * differs. Does this comment still match what the code does? The patch removes the "
base_id" concept fromkernel/bpf/states.c(deleted the paragraph that defined it, removed the two-level compound/base id check fromcheck_scalar_ids), but the comment here still describes the test as verifying "base_idconsistency" and refers to "unrelatedbase_id" on the next line.Looking at the function name and
__descriptionbelow:Quoted 4 lines
*/
__description("add_const base_id must be consistent for pruning")__failure__msg("invalid variable-offset")
__nakedvoidadd_const_base_id_pruning(void)and later at line 695:
Quoted 2 lines
/* Runtime: R2.id=A, R4.id=C:
base_idsA vs C inconsistent,
* pruning should have failed. */
Quoted 8 lines
Quoted 7 lines
Quoted 4 lines
Should these be updated to use current terminology, or does "
base_id" still have meaning in this context? The test itself still works correctly after the patch, so this appears to be a documentation consistency question rather than a functional issue.Indeed
base_idas a term is gone, but just id alone might be confusing as well.
How about link id as a replacement forbase_idI don't think "link id" fits either. Just use id.
OK.
Thx,
-Vineet
Re: [PATCH bpf-next v2 01/13] bpf: move linked-scalar flags out of bpf_reg_state->id [NFC]
In reply to Vineet GuptaQuoted 52 lines · Vineet Gupta
bpf_reg_state->iddoubles as a linked-register id and, in its top two bits, as a record of how the register relates to that set:#define BPF_ADD_CONST64 (1U << 31) #define BPF_ADD_CONST32 (1U << 30)Every user of ->id therefore has to mask, and more link kinds are coming. Move the two bits into a bitfield next to ->precise, which is the last field of the struct and outside every
memcmp()window used for state comparison, so the layout and all byte-wise comparisons are unchanged. The two kinds are mutually exclusive, so a 2-bit enum captures them and makesADD_CONST_32vsADD_CONST_64explicit at each use.->id becomes a plain 32-bit identifier: no masking anywhere, and
check_scalar_ids()loses its two-level "check the compound id, then the base id" dance in favour of a singlecheck_ids().While here, use
regs_exact()for theexplore_alu_limitscase inregsafe():
it is what that open-coded memcmp+check_scalar_ids pair amounts to, and it picks up theadd_constcomparison for free (parent_idis 0 forSCALAR_VALUE).
check_stack_write_fixed_off()cleared ->id directly on a narrowing spill, which would now leave ->add_const set without an id; useclear_scalar_id().Moving the kind out of ->id also drops an incidental comparison in
regs_exact(), which used to see it as part of the idmap key; the next patch restores it. Otherwise no functional change intended.Suggested-by Eduard Zingerman <[email protected]>Signed-off-by Vineet Gupta <[email protected]>---
v2: was RFC 2/6.
- kinds are a 2-bit enum bitfield, not a byte of flags; RFC 1/6, which turned ->precise into that byte, is dropped (Eduard)
- useregs_exact()for theexplore_alu_limitscase
-clear_scalar_id()on the narrowing spill, which would otherwise leave ->add_const set without an idinclude/linux/bpf_verifier.h | 25 ++++++++----- kernel/bpf/log.c | 4 +-- kernel/bpf/states.c | 35 +++++-------------- kernel/bpf/verifier.c | 35 +++++++++++-------- .../bpf/progs/verifier_linked_scalars.c | 34 +++++++++--------- 5 files changed, 65 insertions(+), 68 deletions(-)include/linux/bpf_verifier.h +0
-0
include/linux/bpf_verifier.h enum bpf_iter_state { · line 41
Quoted 7 lines
include/linux/bpf_verifier.h +4
-0@@ -35,6 +35,17 @@ enum bpf_iter_state { BPF_ITER_STATE_DRAINED, }; +/* +* Records that a register is (base + ->delta) within its ->id set: +* r1 += 10; r1 gets ADD_CONST_64 delta +* w3 += 10; r3 gets ADD_CONST_32 delta
w3 gets ?
Quoted 91 lines
include/linux/bpf_verifier.h +13
-8+*/ +enum bpf_add_const { +ADD_CONST_NONE =0 , +ADD_CONST_32 ,/* delta was added with a 32-bit ALU op */ +ADD_CONST_64 ,/* ... with a 64-bit ALU op */ +}; +struct bpf_reg_state {/* Ordering of fields matters. See states_equal() */ enum bpf_reg_type type;@@ -136,16 +147,9 @@ struct bpf_reg_state {* to a specific instance of bpf_iter. */ /* -* Upper bit of ID is used to remember relationship between "linked" -* registers. Example: +* Registers sharing an ->id are "linked": * r1 = r2; both will have r1->id == r2->id == N -* r1 += 10; r1->id == N | BPF_ADD_CONST and r1->delta == 10 -* r3 = r2; both will have r3->id == r2->id == N -* w3 += 10; r3->id == N | BPF_ADD_CONST32 and r3->delta == 10 */ -#define BPF_ADD_CONST64 (1U << 31) -#define BPF_ADD_CONST32 (1U << 30) -#define BPF_ADD_CONST (BPF_ADD_CONST64 | BPF_ADD_CONST32)u32 id;/* * Tracks the parent object this register was derived from. @@ -164,6 +168,11 @@ struct bpf_reg_state {u32 frameno;/* if (!precise && SCALAR_VALUE) min/max/tnum don't affect safety */ bool precise; +/* +* How this register relates to the others sharing its ->id. +* Non-zero only if ->id is. +*/ + enum bpf_add_const add_const:2; };static inline s64 reg_smin (const struct bpf_reg_state *reg)kernel/bpf/log.c +2
-2@@ -651,8 +651,8 @@ static void print_reg_state(struct bpf_verifier_env *env,verbose (env,"%s" ,btf_type_name (reg->btf, reg->btf_id));verbose (env,"(" );if (reg->id) -verbose_a ("id=%d" , reg->id & ~BPF_ADD_CONST ); -if (reg->id &BPF_ADD_CONST ) +verbose_a ("id=%d" , reg->id); +if (reg->add_const)verbose (env,"%+d" , reg->delta);if (reg->parent_id)verbose_a ("parent_id=%d" , reg->parent_id);kernel/bpf/states.c +1
-16@@ -369,13 +369,6 @@ static bool check_ids(u32 old_id, u32 cur_id, struct bpf_idmap *idmap)* and r7.id=0 (both independent), without temp IDs both would map old_id=X * to cur_id=0 and pass. With temp IDs: r6 maps X->temp1, r7 tries to map * X->temp2, but X is already mapped to temp1, so the check fails correctly. -* -* When old_id has BPF_ADD_CONST set, the compound id (base | flag) and the -* base id (flag stripped) must both map consistently. Example: old has -* r2.id=A, r3.id=A|flag (r3 = r2 + delta), cur has r2.id=B, r3.id=C|flag -* (r3 derived from unrelated r4). Without the base check, idmap gets two -* independent entries A->B and A|flag->C|flag, missing that A->C conflicts -* with A->B. The base ID cross-check catches this. */ static bool check_scalar_ids (u32 old_id,u32 cur_id,struct bpf_idmap *idmap) {@@ -384,15 +377,7 @@ static bool check_scalar_ids(u32 old_id, u32 cur_id, struct bpf_idmap *idmap) cur_id = cur_id ? cur_id : ++idmap->tmp_id_gen; -if (!check_ids (old_id, cur_id, idmap)) -return false; -if (old_id &BPF_ADD_CONST ) { - old_id &= ~BPF_ADD_CONST ; - cur_id &= ~BPF_ADD_CONST ; -if (!check_ids (old_id, cur_id, idmap)) -return false; - } -return true; +return check_ids (old_id, cur_id, idmap); } static void __clean_func_state(struct bpf_verifier_env *env,
kernel/bpf/states.c static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold, · line 530
Quoted 6 lines
kernel/bpf/states.c +1
-2@@ -542,8 +527,7 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,/* explore_alu_limits disables tnum_in() and range_within() * logic and requires everything to be strict */ -return memcmp (rold, rcur, offsetof(struct bpf_reg_state , id)) ==0 && -check_scalar_ids (rold->id, rcur->id, idmap); +return regs_exact (rold, rcur, idmap);
Why drop memcmp() ? Doesn't look correct.
Also even after above change to check_scalar_ids() the check_scalar_ids() is still no equivalent to check_ids() that regs_exact() is doing.
This patch should have been refactoring, if so, this change looks unrelated and dubious.
The rest looks fine.
Re: [PATCH bpf-next v2 01/13] bpf: move linked-scalar flags out of bpf_reg_state->id [NFC]
Quoted 56 lines · Alexei Starovoitov
Quoted 55 lines · Vineet Gupta
bpf_reg_state->iddoubles as a linked-register id and, in its top two bits, as a record of how the register relates to that set:#define BPF_ADD_CONST64 (1U << 31) #define BPF_ADD_CONST32 (1U << 30)Every user of ->id therefore has to mask, and more link kinds are coming. Move the two bits into a bitfield next to ->precise, which is the last field of the struct and outside every
memcmp()window used for state comparison, so the layout and all byte-wise comparisons are unchanged. The two kinds are mutually exclusive, so a 2-bit enum captures them and makesADD_CONST_32vsADD_CONST_64explicit at each use.->id becomes a plain 32-bit identifier: no masking anywhere, and
check_scalar_ids()loses its two-level "check the compound id, then the base id" dance in favour of a singlecheck_ids().While here, use
regs_exact()for theexplore_alu_limitscase inregsafe():
it is what that open-coded memcmp+check_scalar_ids pair amounts to, and it picks up theadd_constcomparison for free (parent_idis 0 forSCALAR_VALUE).
check_stack_write_fixed_off()cleared ->id directly on a narrowing spill, which would now leave ->add_const set without an id; useclear_scalar_id().Moving the kind out of ->id also drops an incidental comparison in
regs_exact(), which used to see it as part of the idmap key; the next patch restores it. Otherwise no functional change intended.Suggested-by Eduard Zingerman <[email protected]>Signed-off-by Vineet Gupta <[email protected]>---
v2: was RFC 2/6.
- kinds are a 2-bit enum bitfield, not a byte of flags; RFC 1/6, whichturned ->precise into that byte, is dropped (Eduard) - use regs_exact() for the explore_alu_limits case - clear_scalar_id() on the narrowing spill, which would otherwise leave ->add_const set without an idinclude/linux/bpf_verifier.h | 25 ++++++++----- kernel/bpf/log.c | 4 +-- kernel/bpf/states.c | 35 +++++-------------- kernel/bpf/verifier.c | 35 +++++++++++-------- .../bpf/progs/verifier_linked_scalars.c | 34 +++++++++--------- 5 files changed, 65 insertions(+), 68 deletions(-)include/linux/bpf_verifier.h +0
-0@@ -35,6 +35,17 @@ enum bpf_iter_state { BPF_ITER_STATE_DRAINED, };
Quoted 5 lines
include/linux/bpf_verifier.h enum bpf_iter_state { · line 41
Quoted 4 lines
include/linux/bpf_verifier.h +4
-0+/* +* Records that a register is (base + ->delta) within its ->id set: +* r1 += 10; r1 gets ADD_CONST_64 delta +* w3 += 10; r3 gets ADD_CONST_32 delta w3 gets ?
OK.
Quoted 89 lines
Quoted 89 lines
include/linux/bpf_verifier.h +13
-8+*/ +enum bpf_add_const { +ADD_CONST_NONE =0 , +ADD_CONST_32 ,/* delta was added with a 32-bit ALU op */ +ADD_CONST_64 ,/* ... with a 64-bit ALU op */ +}; +struct bpf_reg_state {/* Ordering of fields matters. See states_equal() */ enum bpf_reg_type type;@@ -136,16 +147,9 @@ struct bpf_reg_state {* to a specific instance of bpf_iter. */ /* -* Upper bit of ID is used to remember relationship between "linked" -* registers. Example: +* Registers sharing an ->id are "linked": * r1 = r2; both will have r1->id == r2->id == N -* r1 += 10; r1->id == N | BPF_ADD_CONST and r1->delta == 10 -* r3 = r2; both will have r3->id == r2->id == N -* w3 += 10; r3->id == N | BPF_ADD_CONST32 and r3->delta == 10 */ -#define BPF_ADD_CONST64 (1U << 31) -#define BPF_ADD_CONST32 (1U << 30) -#define BPF_ADD_CONST (BPF_ADD_CONST64 | BPF_ADD_CONST32)u32 id;/* * Tracks the parent object this register was derived from. @@ -164,6 +168,11 @@ struct bpf_reg_state {u32 frameno;/* if (!precise && SCALAR_VALUE) min/max/tnum don't affect safety */ bool precise; +/* +* How this register relates to the others sharing its ->id. +* Non-zero only if ->id is. +*/ + enum bpf_add_const add_const:2; };static inline s64 reg_smin (const struct bpf_reg_state *reg)kernel/bpf/log.c +2
-2@@ -651,8 +651,8 @@ static void print_reg_state(struct bpf_verifier_env *env,verbose (env,"%s" ,btf_type_name (reg->btf, reg->btf_id));verbose (env,"(" );if (reg->id) -verbose_a ("id=%d" , reg->id & ~BPF_ADD_CONST ); -if (reg->id &BPF_ADD_CONST ) +verbose_a ("id=%d" , reg->id); +if (reg->add_const)verbose (env,"%+d" , reg->delta);if (reg->parent_id)verbose_a ("parent_id=%d" , reg->parent_id);kernel/bpf/states.c +1
-16@@ -369,13 +369,6 @@ static bool check_ids(u32 old_id, u32 cur_id, struct bpf_idmap *idmap)* and r7.id=0 (both independent), without temp IDs both would map old_id=X * to cur_id=0 and pass. With temp IDs: r6 maps X->temp1, r7 tries to map * X->temp2, but X is already mapped to temp1, so the check fails correctly. -* -* When old_id has BPF_ADD_CONST set, the compound id (base | flag) and the -* base id (flag stripped) must both map consistently. Example: old has -* r2.id=A, r3.id=A|flag (r3 = r2 + delta), cur has r2.id=B, r3.id=C|flag -* (r3 derived from unrelated r4). Without the base check, idmap gets two -* independent entries A->B and A|flag->C|flag, missing that A->C conflicts -* with A->B. The base ID cross-check catches this. */ static bool check_scalar_ids (u32 old_id,u32 cur_id,struct bpf_idmap *idmap) {@@ -384,15 +377,7 @@ static bool check_scalar_ids(u32 old_id, u32 cur_id, struct bpf_idmap *idmap) cur_id = cur_id ? cur_id : ++idmap->tmp_id_gen; -if (!check_ids (old_id, cur_id, idmap)) -return false; -if (old_id &BPF_ADD_CONST ) { - old_id &= ~BPF_ADD_CONST ; - cur_id &= ~BPF_ADD_CONST ; -if (!check_ids (old_id, cur_id, idmap)) -return false; - } -return true; +return check_ids (old_id, cur_id, idmap); }
Quoted 9 lines
kernel/bpf/states.c static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold, · line 530
Quoted 8 lines
kernel/bpf/states.c +1
-2static void __clean_func_state(struct bpf_verifier_env *env,@@ -542,8 +527,7 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,/* explore_alu_limits disables tnum_in() and range_within() * logic and requires everything to be strict */ -return memcmp (rold, rcur, offsetof(struct bpf_reg_state , id)) ==0 && -check_scalar_ids (rold->id, rcur->id, idmap); +return regs_exact (rold, rcur, idmap);Why drop
memcmp()? Doesn't look correct.
regs_exact has the exact same memcmp so I don't think we are dropping it, but .....
| static bool regs_exact(const struct bpf_reg_state *rold,
| const struct bpf_reg_state *rcur,
| struct bpf_idmap *idmap)
| {
| return memcmp(rold, rcur, offsetof(struct bpf_reg_state, id)) == 0 &&
| check_ids(rold->id, rcur->id, idmap) &&
| check_ids(rold->parent_id, rcur->parent_id, idmap);
| }Quoted 2 lines
Also even after above change to
check_scalar_ids()thecheck_scalar_ids()is still no equivalent tocheck_ids()thatregs_exact()is doing.
... Right: reverting back to what we had before.
FWIW Eduard had suggested to use regs_exact; I'm not sure if he had something else in mind which we might be overlooking.
Quoted 2 lines
This patch should have been refactoring, if so, this change looks unrelated and dubious.
Back when I started, keeping it NFC made more sense. But with all the nuances discovered in the process, I'm inclined to drop the NFC stance and make functional changes - there's at least one which is the following accepted pre-series and now rejected.
old {r2.id=A+delta32} vs cur {r2.id=B+delta64}
Quoted 1 line
The rest looks fine.
Thanks for taking a look.
-Vineet
Re: [PATCH bpf-next v2 01/13] bpf: move linked-scalar flags out of bpf_reg_state->id [NFC]
Quoted 2 lines · Vineet Gupta
Back when I started, keeping it NFC made more sense. But with all the nuances discovered in the process, I'm inclined to drop the NFC stance
What is NFC ?
Quoted 4 lines
and make functional changes - there's at least one which is the following accepted pre-series and now rejected.
old {r2.id=A+delta32} vs cur {r2.id=B+delta64}
that's a red flag, no? The refactoring patch shouldn't have any changes to selftest and veristat numbers? Unless I'm missing it again.
Re: [PATCH bpf-next v2 01/13] bpf: move linked-scalar flags out of bpf_reg_state->id [NFC]
Quoted 4 lines · Alexei Starovoitov
Quoted 2 lines · Vineet Gupta
Back when I started, keeping it NFC made more sense. But with all the nuances discovered in the process, I'm inclined to drop the NFC stance
What is NFC ?
non functional change aka refactoring.
Like I said when I started I wanted to keep the id / flag breakout purely non functional. But given that splitting it does change one thing (mentioned below) - I'm dropping NFC attribution.
Quoted 7 lines
Quoted 4 lines
and make functional changes - there's at least one which is the following accepted pre-series and now rejected.
old {r2.id=A+delta32} vs cur {r2.id=B+delta64}
that's a red flag, no? The refactoring patch shouldn't have any changes to selftest and veristat numbers? Unless I'm missing it again.
Yes understood except that it is no longer refactoring.
Thx
-Vineet
Re: [PATCH bpf-next v2 01/13] bpf: move linked-scalar flags out of bpf_reg_state->id [NFC]
Quoted 15 lines · Vineet Gupta
Quoted 4 lines · Alexei Starovoitov
Quoted 2 lines · Vineet Gupta
Back when I started, keeping it NFC made more sense. But with all the nuances discovered in the process, I'm inclined to drop the NFC stance
What is NFC ?
non functional change aka refactoring.
Like I said when I started I wanted to keep the id / flag breakout purely non functional. But given that splitting it does change one thing (mentioned below) - I'm dropping NFC attribution.Quoted 3 lines
Quoted 3 lines
and make functional changes - there's at least one which is the following accepted pre-series and now rejected.
Quoted 6 lines
Quoted 4 lines
Quoted 1 line
old {r2.id=A+delta32} vs cur {r2.id=B+delta64}that's a red flag, no? The refactoring patch shouldn't have any changes to selftest and veristat numbers? Unless I'm missing it again.
Yes understood except that it is no longer refactoring.
NFC is gcc probably lingvo? In kernel people just put in the commit log "No functional changes", so it's easier for humans and for AI to review patches.
So pls skip such unusual tags in the future,
but keep the first patch as "No functional change".
Re: [PATCH bpf-next v2 01/13] bpf: move linked-scalar flags out of bpf_reg_state->id [NFC]
Quoted 15 lines · Alexei Starovoitov
Quoted 14 lines · Vineet Gupta
Quoted 4 lines · Alexei Starovoitov
Quoted 2 lines · Vineet Gupta
Back when I started, keeping it NFC made more sense. But with all the nuances discovered in the process, I'm inclined to drop the NFC stance
What is NFC ?
non functional change aka refactoring.
Like I said when I started I wanted to keep the id / flag breakout purely non functional. But given that splitting it does change one thing (mentioned below) - I'm dropping NFC attribution.Quoted 4 lines
Quoted 4 lines
and make functional changes - there's at least one which is the following accepted pre-series and now rejected.
old {r2.id=A+delta32} vs cur {r2.id=B+delta64}
Quoted 8 lines
Quoted 4 lines
Quoted 3 lines
that's a red flag, no? The refactoring patch shouldn't have any changes to selftest and veristat numbers? Unless I'm missing it again.
Yes understood except that it is no longer refactoring.
NFC is gcc probably lingvo? In kernel people just put in the commit log "No functional changes", so it's easier for humans and for AI to review patches.
So pls skip such unusual tags in the future,
Yes keeping kernel's existing conventions makes sense, although LLMs understand what NFC is.
Quoted 1 line
but keep the first patch as "No functional change".
Just to rehash since the meaning of first has moved significantly.
1. Now the first change (patch 1/x and its test 2/x ) is no longer the compound id conversion, but coerce_reg_to_size_sx / coerce_subreg_to_size_sx change to fix the errno range case, as suggested by you. It is a functional change, with following improvement:
=== VERDICT CHANGES: 3 ===
mov32sx_s8_negative_range failure -> success
mov64sx_s32_negative_range failure -> success
mov64sx_s8_negative_range failure -> success === total_insns: 0 changed among 1242 both-passing, 0 worse === === total_states: 0 changed among 1242 both-passing, 0 worse ===
2. The second change (3/x and its test 4/x) is accumulating add_const deltas (w3 = w0; w3 -=1). This makes the 32-bit link with delta special handling of zext unnecessary so its a prereq for the series.
3. I guess you are referring to the patch to convert compound id to broken out id + flags (5/x ) is also technically a functional change - due to the state comparison behavior improvement that fell out of the seemingly mechanical conversion and is clearly called out now. However I verified it in isolation (on top of 4 prior of course) and there are no veristat or selftest changes with it (just a cosmetic name change due to base_id -> id)
=== VERDICT CHANGES: 0 ===
=== total_insns: 0 changed among 1247 both-passing, 0 worse === === total_states: 0 changed among 1247 both-passing, 0 worse ===
I presume that is what you were asking for ?
Thx,
-Vineet
Re: [PATCH bpf-next v2 01/13] bpf: move linked-scalar flags out of bpf_reg_state->id [NFC]
Quoted 8 lines · Vineet Gupta
3. I guess you are referring to the patch to convert compound id to broken out id + flags (5/x ) is also technically a functional change - due to the state comparison behavior improvement that fell out of the seemingly mechanical conversion and is clearly called out now. However I verified it in isolation (on top of 4 prior of course) and there are no veristat or selftest changes with it (just a cosmetic name change due to
base_id-> id)
Quoted 6 lines
=== VERDICT CHANGES: 0 === === total_insns: 0 changed among 1247 both-passing, 0 worse === === total_states: 0 changed among 1247 both-passing, 0 worse ===I presume that is what you were asking for ?
Yes.
but 1247 progs is verifier_*.bpf.o only ?
These are tiny asm tests. Pls run veristat on the rest and scx and meta progs too.
Eduard Zingerman
maintainerRe: [PATCH bpf-next v2 01/13] bpf: move linked-scalar flags out of bpf_reg_state->id [NFC]
In reply to Vineet GuptaOn Mon, 2026-09-14 at 18:17 -0700, Vineet Gupta wrote:
...
Quoted 9 lines
Quoted 8 lines
static bool regs_exact(const struct
bpf_reg_state*rold, const structbpf_reg_state*rcur,
structbpf_idmap*idmap)
{
returnmemcmp(rold, rcur, offsetof(struct bpf_reg_state, id))== 0 &&check_ids(rold->id, rcur->id, idmap)&&check_ids(rold->parent_id, rcur->parent_id, idmap); }
Quoted 6 lines
Quoted 2 lines
Also even after above change to
check_scalar_ids()thecheck_scalar_ids()is still no equivalent tocheck_ids()thatregs_exact()is doing.... Right: reverting back to what we had before.
FWIW Eduard had suggested to useregs_exact; I'm not sure if he had something else in mind which we might be overlooking.
I missed the check_scalar_ids() vs check_ids() difference, sorry. Also, yes, let's squash with patch #2.
...
Re: [PATCH bpf-next v2 01/13] bpf: move linked-scalar flags out of bpf_reg_state->id [NFC]
Quoted 14 lines · Eduard Zingerman
On Mon, 2026-09-14 at 18:17 -0700, Vineet Gupta wrote:
...
Quoted 10 lines
Quoted 10 lines
static bool regs_exact(const struct
bpf_reg_state*rold,
const structbpf_reg_state*rcur,
structbpf_idmap*idmap)
{
returnmemcmp(rold, rcur, offsetof(struct bpf_reg_state, id))== 0 &&check_ids(rold->id, rcur->id, idmap)&&check_ids(rold->parent_id, rcur->parent_id, idmap);
}
Also even after above change tocheck_scalar_ids()thecheck_scalar_ids()is still no equivalent tocheck_ids()thatregs_exact()is doing.
Quoted 7 lines
Quoted 3 lines
... Right: reverting back to what we had before.
FWIW Eduard had suggested to useregs_exact; I'm not sure if he had something else in mind which we might be overlooking.I missed the
check_scalar_ids()vscheck_ids()difference, sorry. Also, yes, let's squash with patch #2....
Yep, will do.
Thx,
-Vineet
PATCH v2 2/13 bpf: compare linked-scalar kinds in regs_exact()
In reply to Vineet Guptaregs_exact() memcmp()s up to offsetof(id), so it does not see ->add_const, which sits past ->frameno. Compare it explicitly.
Two cases go from accepted to rejected:
old {r1.id=A, r2.id=A+delta} vs cur {r1.id=B, r2.id=B}
old {r2.id=A+delta32} vs cur {r2.id=B+delta64}
The first was rejected before this series -- the kind lived in ->id, so A+delta was a distinct idmap key -- and the previous patch lost that. The second was accepted before the series too, which is wrong: alu32 and alu64 deltas differ in sync_linked_regs(), so the states are not interchangeable.
->delta is inside the memcmp() window and is cleared together with the kind, so either case needs a kind with delta 0, e.g. "r6 = r5; r6 += 0".
Only states_equal(..., EXACT) and env->explore_alu_limits reach regs_exact() for a scalar; regsafe() compares kinds itself on the ordinary path. Neither is easy to drive from a test program, so no selftest.
---
v2: new. Splits out the comparison RFC 3/6 lost when the kind left ->id, which was raised on that patch.
kernel/bpf/states.c | 1 + 1 file changed, 1 insertion(+)
kernel/bpf/states.c +1 -0
@@ -475,6 +475,7 @@ static bool regs_exact(const struct bpf_reg_state *rold, struct bpf_idmap *idmap) {return memcmp (rold, rcur, offsetof(struct bpf_reg_state , id)) ==0 && + rold->add_const == rcur->add_const &&check_ids (rold->id, rcur->id, idmap) &&check_ids (rold->parent_id, rcur->parent_id, idmap); }
Signature · 1 line
2.53.0-Meta
Re: [PATCH bpf-next v2 02/13] bpf: compare linked-scalar kinds in regs_exact()
Quoted 34 lines · Vineet Gupta
regs_exact()memcmp()s up to offsetof(id), so it does not see ->add_const, which sits past ->frameno. Compare it explicitly.Two cases go from accepted to rejected:
old {r1.id=A, r2.id=A+delta} vs cur {r1.id=B, r2.id=B}
old {r2.id=A+delta32} vs cur {r2.id=B+delta64}The first was rejected before this series -- the kind lived in ->id, so A+delta was a distinct idmap key -- and the previous patch lost that. The second was accepted before the series too, which is wrong: alu32 and alu64 deltas differ in
sync_linked_regs(), so the states are not interchangeable.->delta is inside the
memcmp()window and is cleared together with the kind, so either case needs a kind with delta 0, e.g. "r6 = r5; r6 += 0".Only
states_equal(..., EXACT)andenv->explore_alu_limitsreachregs_exact()for a scalar;regsafe()compares kinds itself on the ordinary path. Neither is easy to drive from a test program, so no selftest.Signed-off-by Vineet Gupta <[email protected]>---
v2: new. Splits out the comparison RFC 3/6 lost when the kind left ->id, which was raised on that patch.kernel/bpf/states.c | 1 + 1 file changed, 1 insertion(+)kernel/bpf/states.c +0
-0
kernel/bpf/states.c static bool regs_exact(const struct bpf_reg_state *rold, · line 478
Quoted 4 lines
kernel/bpf/states.c +1
-0@@ -475,6 +475,7 @@ static bool regs_exact(const struct bpf_reg_state *rold, struct bpf_idmap *idmap) {return memcmp (rold, rcur, offsetof(struct bpf_reg_state , id)) ==0 && + rold->add_const == rcur->add_const &&
This change should be in the patch 1 otherwise patch 1 is not correct?
Re: [PATCH bpf-next v2 02/13] bpf: compare linked-scalar kinds in regs_exact()
Quoted 30 lines · Alexei Starovoitov
Quoted 29 lines · Vineet Gupta
regs_exact()memcmp()s up to offsetof(id), so it does not see ->add_const, which sits past ->frameno. Compare it explicitly.Two cases go from accepted to rejected:
old {r1.id=A, r2.id=A+delta} vs cur {r1.id=B, r2.id=B} old {r2.id=A+delta32} vs cur {r2.id=B+delta64}The first was rejected before this series -- the kind lived in ->id, so A+delta was a distinct idmap key -- and the previous patch lost that. The second was accepted before the series too, which is wrong: alu32 and alu64 deltas differ in
sync_linked_regs(), so the states are not interchangeable.->delta is inside the
memcmp()window and is cleared together with the kind, so either case needs a kind with delta 0, e.g. "r6 = r5; r6 += 0".Only
states_equal(..., EXACT)andenv->explore_alu_limitsreachregs_exact()for a scalar;regsafe()compares kinds itself on the ordinary path. Neither is easy to drive from a test program, so no selftest.Signed-off-by Vineet Gupta <[email protected]>---
v2: new. Splits out the comparison RFC 3/6 lost when the kind left ->id, which was raised on that patch.kernel/bpf/states.c | 1 + 1 file changed, 1 insertion(+)
Quoted 10 lines
kernel/bpf/states.c static bool regs_exact(const struct bpf_reg_state *rold, · line 478
Quoted 9 lines
kernel/bpf/states.c +1
-0@@ -475,6 +475,7 @@ static bool regs_exact(const struct bpf_reg_state *rold, struct bpf_idmap *idmap) {return memcmp (rold, rcur, offsetof(struct bpf_reg_state , id)) ==0 && + rold->add_const == rcur->add_const &&This change should be in the patch 1 otherwise patch 1 is not correct?
Will do - it was one of the open questions in v2.
Thx,
-Vineet
PATCH v2 3/13 bpf: track low-32 scalar equality across zero-extending movs
In reply to Vineet GuptaLinked-scalar equality is full-64-bit only. A 32-bit mov from a source with unknown high bits therefore has to drop the relationship, and a later narrowing of the source never reaches the destination:
r6 = ... /* full 64-bit unknown */ w7 = w6 /* 32-bit zero-extending mov */ if w6 != 0 goto ... /* not taken: r6's low 32 bits are 0 */ if w7 == 0 goto ... /* not deduced today */
Record a low-32-only link instead: dst shares src's low 32 bits and its high half is zero. On a later narrowing, sync_linked_regs() rebuilds such a register from the base rather than copying it, by re-applying the same zext_32_to_64() the mov used. The reverse direction is skipped: a ->subreg base knows nothing about a full register's high half.
The link is not modelled together with an ADD_CONST delta, so forming one costs the source its delta: assign_scalar_id_before_mov() clears it, as it already does for a narrow source. That loses tracking a wide source used to keep, but the two cannot both be held -- a link the sync path skips would be inert.
bpf-gcc hits this by reusing "w0 = idx" for "return 0" on the idx == 0 path of a bpf_loop callback.
regs_exact() and regsafe() compare the new kind, for the reasons given in the previous patch. As with the pre-existing add_const comparison, no selftest isolates it: when the kinds differ in a way a program can build, the ranges differ too and the range checks reject first.
Two existing tests move with the behaviour. verifier_reg_equal's "w reg not equal if r reg upper32 bits not 0" is this exact case and becomes __success; verifier_bounds' sub32_partial_overflow pins a register dump that now carries the link.
---
v2: was RFC 3/6.
- no longer excludes an ADD_CONST source, for symmetry with the narrow path (Eduard). The cost is spelled out in the changelog
- reconstruct_zext32() instead of an open-coded block (Eduard)
- saved_id dropped: reg->id == known_reg->id already holds (Eduard)
- flattened the if-nesting (Eduard)
- log.c prints the kind (Eduard)
- changelog and comments trimmed (Eduard)
include/linux/bpf_verifier.h | 10 +++ kernel/bpf/log.c | 2 + kernel/bpf/states.c | 4 +- kernel/bpf/verifier.c | 61 +++++++++++++++++-- .../selftests/bpf/progs/verifier_bounds.c | 2 +- .../selftests/bpf/progs/verifier_reg_equal.c | 14 ++--- 6 files changed, 78 insertions(+), 15 deletions(-)
include/linux/bpf_verifier.h +10 -0
@@ -46,6 +46,15 @@ enum bpf_add_const { ADD_CONST_64, /* ... with a 64-bit ALU op */ }; +/* +* Records that a register shares only the low 32 bits of the base of its +* ->id set, and how its high bits follow from them. +*/ +enum bpf_subreg { +SUBREG_NONE =0 , +SUBREG_ZEXT ,/* high bits are zero (32-bit zero-extending mov) */ +}; +struct bpf_reg_state {/* Ordering of fields matters. See states_equal() */ enum bpf_reg_type type;
@@ -173,6 +182,7 @@ struct bpf_reg_state {* Non-zero only if ->id is. */ enum bpf_add_const add_const:2; + enum bpf_subreg subreg:2; };static inline s64 reg_smin (const struct bpf_reg_state *reg)
kernel/bpf/log.c +2 -0
@@ -654,6 +654,8 @@ static void print_reg_state(struct bpf_verifier_env *env,verbose_a ("id=%d" , reg->id);if (reg->add_const)verbose (env,"%+d" , reg->delta); +if (reg->subreg ==SUBREG_ZEXT ) +verbose (env,".lo32" );if (reg->parent_id)verbose_a ("parent_id=%d" , reg->parent_id);if (type_is_non_owning_ref (reg->type))
kernel/bpf/states.c +3 -1
@@ -476,6 +476,7 @@ static bool regs_exact(const struct bpf_reg_state *rold, {return memcmp (rold, rcur, offsetof(struct bpf_reg_state , id)) ==0 && rold->add_const == rcur->add_const && + rold->subreg == rcur->subreg &&check_ids (rold->id, rcur->id, idmap) &&check_ids (rold->parent_id, rcur->parent_id, idmap); }
@@ -577,7 +578,8 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,* linking semantics in sync_linked_regs() (alu32 zero-extends, * alu64 does not), so pruning across them is unsafe. */ -if (rold->id && rold->add_const != rcur->add_const) +if (rold->id && (rold->add_const != rcur->add_const || + rold->subreg != rcur->subreg))return false;/* Both have offset linkage: offsets must match */
kernel/bpf/verifier.c +55 -6
100 lines not on this page · raw message
tools/testing/selftests/bpf/progs/verifier_bounds.c +1 -1
@@ -1516,7 +1516,7 @@ __naked void sub32_full_overflow(void) SEC("socket") __description("32-bit subtraction, partial overflow, result in unbounded u32 bounds") __success __log_level(2) -__msg("3: (1c) w3 -= w2 {{.*}} R3=scalar(smin=0,smax=umax=0xffffffff,var_off=(0x0; 0xffffffff))") +__msg("3: (1c) w3 -= w2 {{.*}} R3=scalar(id={{[0-9]+}}-1.lo32,smin=0,smax=umax=0xffffffff,var_off=(0x0; 0xffffffff))") __retval(0)__naked void sub32_partial_overflow (void ) {
tools/testing/selftests/bpf/progs/verifier_reg_equal.c +7 -7
@@ -31,23 +31,23 @@ l1_%=: exit; \ } SEC("socket") -__description("check w reg not equal if r reg upper32 bits not 0") -__failure __msg("R1 !read_ok") +__description("check w reg equal if r reg upper32 bits not 0") +__success__naked void subreg_equality_2 (void ) { asmvolatile (" \ call %[bpf_ktime_get_ns]; \ r2 = r0; \ -/* Upper 4-bytes of r2 may not be 0, thus insn \ -* w3 = w2 should not propagate reg id, and \ -* w2 < 9 comparison should not propagate \ -* the range for r3 either. \ +/* Upper 4-bytes of r2 may not be 0, so r3 does \ +* not equal r2. It does share r2's low 32 bits \ +* though, so w2 < 9 still bounds r3: the \ +* zero-extending mov leaves nothing above them.\ */ \ w3 = w2; \ if w2 < 9 goto l0_%=; \ exit; \ l0_%=: if r3 < 9 goto l1_%=; \ -/* r1 read is illegal at this point */ \ +/* unreachable, so the r1 read is never made */ \ r0 -= r1; \ l1_%=: exit; \ " :
Signature · 1 line
2.53.0-Meta
[email protected]
AI reviewRe: [PATCH bpf-next v2 03/13] bpf: track low-32 scalar equality across zero-extending movs
Can reconstruct_zext32() lose bounds that reg already learned on its own?
Quoted 4 lines
include/linux/bpf_verifier.h +0
-0
[ ... ]
Quoted 4 lines
kernel/bpf/verifier.c +0
-0
[ ... ]
Quoted 42 lines
kernel/bpf/verifier.c +31
-0@@ -17115,6 +17126,23 @@ static void collect_linked_regs(struct bpf_verifier_env *env, } } +/* +* Set @reg to the zero-extension of @known_reg's low 32 bits: it shares those +* bits and its high half is zero. Copy the base to keep its precise low-32 +* tnum, then re-apply the zext_32_to_64() the 32-bit mov itself used. +* @reg->id and ->delta already equal @known_reg's; only ->subreg is its own. +*/ +static void reconstruct_zext32 (struct bpf_reg_state *reg, +struct bpf_reg_state *known_reg) +{ +enum bpf_subreg subreg = reg->subreg; + + *reg = *known_reg; + reg->subreg = subreg; +zext_32_to_64 (reg); +reg_bounds_sync (reg); +} +/* For all R in linked_regs, copy known_reg range into R * if R->id == known_reg->id. */ @@ -17134,6 +17162,27 @@ static void sync_linked_regs(struct bpf_verifier_env *env, struct bpf_verifier_scontinue ;if (reg->id != known_reg->id)continue ; +/* +* A ->subreg register shares only the base's low 32 bits, so it +* is rebuilt rather than copied. Not modelled together with a +* delta, so skip if either side has one (sound, less precise). +*/ +if (reg->subreg) { +if (reg->add_const || known_reg->add_const) +continue ; +reconstruct_zext32 (reg, known_reg); +if (e->is_reg) +mark_reg_scratched (env, e->regno); +else +mark_stack_slot_scratched (env, e->spi); +continue ;
kernel/bpf/verifier.c static void sync_linked_regs(struct bpf_verifier_env *env, struct bpf_verifier_s · line 17188
Quoted 10 lines
kernel/bpf/verifier.c +7
-0+ } +/* +* The reverse: known_reg knows only its low 32 bits, which say +* nothing about reg's high half. +*/ +if (known_reg->subreg) +continue ;/* * Skip mixed 32/64-bit links: the delta relationship doesn't * hold across different ALU widths.
Can reconstruct_zext32() lose bounds that reg already learned on its own?
Looking at the code, reconstruct_zext32() does:
*reg = *known_reg;
reg->subreg = subreg;
zext_32_to_64(reg);This overwrites reg's state wholesale without intersecting it with what reg already knew.
For pre-existing full-64-bit links, sync_linked_regs() propagates changes in both directions, so the base is always at least as narrow as every member and the overwrite can only narrow. But the new low-32 link skips the member->base direction:
if (known_reg->subreg)
continue;so the base can end up strictly wider than the ->subreg member.
Consider this sequence:
call bpf_get_prandom_u32; /* r0 -> 64-bit unknown */ r6 = r0; /* r6 is 64-bit unknown */ w7 = w6; /* r7->id = r6->id, r7->subreg = SUBREG_ZEXT */ if w7 > 7 goto out; /* fall-through: r7 u32 range [0,7]
* sync_linked_regs(known_reg=r7) skips r6 due
* to if (known_reg->subreg) continue;
* so r6 stays fully unknown */
if r6 > 100 goto out; /* fall-through: r6 narrows to [0,100]
* sync_linked_regs(known_reg=r6) reaches r7
* via reconstruct_zext32(r7, r6) which does
* *r7 = *r6 then zext_32_to_64() */
After the second jump, does r7 become [0,100] instead of staying [0,7]?
If so, a jump on an unrelated wide register would widen the bounds of a narrow copy that the verifier had already proved tighter, on a straight-line path. That would reject programs that narrowed the 32-bit copy first and the wide original second, then relied on the copy's narrower bound for a memory access or helper argument.
The changelog acknowledges the other precision loss this patch introduces ("forming one costs the source its delta ... That loses tracking a wide source used to keep") and the follow-up selftest commit 36b84852a200 pins it down with zext_mov_breaks_add_const_src. But neither the changelog nor reconstruct_zext32()'s comment ("Copy the base to keep its precise low-32 tnum"), nor any of the 10 new tests in 36b84852a200, mentions or covers this path. The only test that checks the member's fate is zext_narrow_dst_keeps_base, which verifies the base is not narrowed but does not check what happens to the member afterwards.
Would intersecting the rebuilt state with the member's existing one, or narrowing the base's low half on the member->base direction instead of skipping it, prevent the member from ever being wider than what it already proved?
---
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/34506184282
Re: [PATCH bpf-next v2 03/13] bpf: track low-32 scalar equality across zero-extending movs
Quoted 87 lines · On 9/10/26 11:22 PM, [email protected] wrote:
Quoted 42 lines
kernel/bpf/verifier.c +31
-0@@ -17115,6 +17126,23 @@ static void collect_linked_regs(struct bpf_verifier_env *env, } } +/* +* Set @reg to the zero-extension of @known_reg's low 32 bits: it shares those +* bits and its high half is zero. Copy the base to keep its precise low-32 +* tnum, then re-apply the zext_32_to_64() the 32-bit mov itself used. +* @reg->id and ->delta already equal @known_reg's; only ->subreg is its own. +*/ +static void reconstruct_zext32 (struct bpf_reg_state *reg, +struct bpf_reg_state *known_reg) +{ +enum bpf_subreg subreg = reg->subreg; + + *reg = *known_reg; + reg->subreg = subreg; +zext_32_to_64 (reg); +reg_bounds_sync (reg); +} +/* For all R in linked_regs, copy known_reg range into R * if R->id == known_reg->id. */ @@ -17134,6 +17162,27 @@ static void sync_linked_regs(struct bpf_verifier_env *env, struct bpf_verifier_scontinue ;if (reg->id != known_reg->id)continue ; +/* +* A ->subreg register shares only the base's low 32 bits, so it +* is rebuilt rather than copied. Not modelled together with a +* delta, so skip if either side has one (sound, less precise). +*/ +if (reg->subreg) { +if (reg->add_const || known_reg->add_const) +continue ; +reconstruct_zext32 (reg, known_reg); +if (e->is_reg) +mark_reg_scratched (env, e->regno); +else +mark_stack_slot_scratched (env, e->spi); +continue ;kernel/bpf/verifier.c static void sync_linked_regs(struct bpf_verifier_env *env, struct bpf_verifier_s · line 17188
Quoted 10 lines
kernel/bpf/verifier.c +7
-0+ } +/* +* The reverse: known_reg knows only its low 32 bits, which say +* nothing about reg's high half. +*/ +if (known_reg->subreg) +continue ;/* * Skip mixed 32/64-bit links: the delta relationship doesn't * hold across different ALU widths. Can
reconstruct_zext32()lose bounds that reg already learned on its own?Looking at the code,
reconstruct_zext32()does:*reg = *known_reg; reg->subreg = subreg; zext_32_to_64(reg);This overwrites reg's state wholesale without intersecting it with what reg already knew.
For pre-existing full-64-bit links,
sync_linked_regs()propagates changes in both directions, so the base is always at least as narrow as every member and the overwrite can only narrow. But the new low-32 link skips themember->basedirection:if (known_reg->subreg) continue;so the base can end up strictly wider than the ->subreg member.
Consider this sequence:
call bpf_get_prandom_u32; /* r0 -> 64-bit unknown */ r6 = r0; /* r6 is 64-bit unknown */ w7 = w6; /* r7->id = r6->id, r7->subreg = SUBREG_ZEXT */ if w7 > 7 goto out; /* fall-through: r7 u32 range [0,7]*
sync_linked_regs(known_reg=r7)skips r6 due
* toif (known_reg->subreg) continue;
* so r6 stays fully unknown */
if r6 > 100 goto out; /* fall-through: r6 narrows to [0,100]
*sync_linked_regs(known_reg=r6)reaches r7
* viareconstruct_zext32(r7, r6)which does
* *r7 = *r6 thenzext_32_to_64()*/
Quoted 1 line
After the second jump, does r7 become [0,100] instead of staying [0,7]?
Yes it does and that's a problem.
Quoted 5 lines
If so, a jump on an unrelated wide register would widen the bounds of a narrow copy that the verifier had already proved tighter, on a straight-line path. That would reject programs that narrowed the 32-bit copy first and the wide original second, then relied on the copy's narrower bound for a memory access or helper argument.
Right, sound, but loss of precision.
Quoted 9 lines
The changelog acknowledges the other precision loss this patch introduces ("forming one costs the source its delta ... That loses tracking a wide source used to keep") and the follow-up selftest commit
36b84852a200pins it down withzext_mov_breaks_add_const_src. But neither the changelog nor reconstruct_zext32()'s comment ("Copy the base to keep its precise low-32 tnum"), nor any of the 10 new tests in36b84852a200, mentions or covers this path. The only test that checks the member's fate iszext_narrow_dst_keeps_base, which verifies the base is not narrowed but does not check what happens to the member afterwards.
Ok. zext_sync_keeps_narrower_member() added and same for sext variant as reconstruct_sext32 gets similar fix.
Quoted 1 line
Would intersecting the rebuilt state with the member's existing one,
This one.
+ cnum64_intersect_with(®->r64, prev.r64);
+ cnum32_intersect_with(®->r32, prev.r32);
+ reg->var_off = tnum_intersect(reg->var_off, prev.var_off);
Quoted 3 lines
narrowing the base's low half on the
member->basedirection instead of skipping it, prevent the member from ever being wider than what it already proved?
This is a new propagation path, trying to be conservative here.
Thx,
-Vineet
Quoted 5 lines
---
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.mdCI run summary: https://github.com/kernel-patches/bpf/actions/runs/34506184282
Re: [PATCH bpf-next v2 03/13] bpf: track low-32 scalar equality across zero-extending movs
In reply to Vineet GuptaQuoted 9 lines · Vineet Gupta
Linked-scalar equality is full-64-bit only. A 32-bit mov from a source with unknown high bits therefore has to drop the relationship, and a later narrowing of the source never reaches the destination:
r6 = ... /* full 64-bit unknown */ w7 = w6 /* 32-bit zero-extending mov */ if w6 != 0 goto ... /* not taken: r6's low 32 bits are 0 */ if w7 == 0 goto ... /* not deduced today */
Quoted 5 lines
Record a low-32-only link instead: dst shares src's low 32 bits and its high half is zero. On a later narrowing,
sync_linked_regs()rebuilds such a register from the base rather than copying it, by re-applying the samezext_32_to_64()the mov used. The reverse direction is skipped: a ->subreg base knows nothing about a full register's high half.
at the first glance SUBREG_ZEXT is exactly the same as ADD_CONST32 delta == 0. no?
Both are unidirectional:w6->id == 1w7->id == 1, add_const == 32, delta == 0
will zero extend w7.
This new SUBREG_ZEXT will do the same.
What am I missing?
Re: [PATCH bpf-next v2 03/13] bpf: track low-32 scalar equality across zero-extending movs
Quoted 21 lines · Alexei Starovoitov
Quoted 9 lines · Vineet Gupta
Linked-scalar equality is full-64-bit only. A 32-bit mov from a source with unknown high bits therefore has to drop the relationship, and a later narrowing of the source never reaches the destination:
r6 = ... /* full 64-bit unknown */ w7 = w6 /* 32-bit zero-extending mov */ if w6 != 0 goto ... /* not taken: r6's low 32 bits are 0 */ if w7 == 0 goto ... /* not deduced today */Quoted 5 lines
Record a low-32-only link instead: dst shares src's low 32 bits and its high half is zero. On a later narrowing,
sync_linked_regs()rebuilds such a register from the base rather than copying it, by re-applying the samezext_32_to_64()the mov used. The reverse direction is skipped: a ->subreg base knows nothing about a full register's high half.at the first glance
SUBREG_ZEXTis exactly the same asADD_CONST32delta == 0. no?
Both are unidirectional:w6->id== 1w7->id== 1,add_const== 32, delta == 0
Quoted 4 lines
will zero extend w7.
This new
SUBREG_ZEXTwill do the same.
What am I missing?
The 2 examples below both imply ADD_CONST32 + delta=0, with different semantics and need special casing.
w3 = w2; w3 += 0
w7 = w6; (r6 was wide)
With code hacks it could in fact me made to work, but its less cleaner.
Current approach we have something like below in sync_linked_regs()
/*
* A ->subreg register shares only the base's low 32 bits, so it
* is rebuilt rather than copied. Not modelled together with a
* delta, so skip if either side has one (sound, less precise). */
if (reg->subreg) {
if (reg->add_const || known_reg->add_const) continue;
if (reg->subreg == SUBREG_ZEXT) reconstruct_zext32(reg, known_reg); else
reconstruct_sext32(reg, known_reg); if (e->is_reg)
mark_reg_scratched(env, e->regno); else
mark_stack_slot_scratched(env, e->spi); continue;
}
/*
* The reverse: known_reg knows only its low 32 bits, which say
* nothing about reg's high half.
*/
if (known_reg->subreg)
continue;
With the suggested approach it looks something like below.ADD_CONST_32, delta == 0 has to be disambiguated from a real += 0 by inspecting another register's bounds.
/*
* A low-32 link shares only the base's low 32 bits, so it is
* rebuilt rather than copied.
*
* SIGN_EXTEND_32 says so outright. ADD_CONST_32 with delta == 0
* does not: it is also what "w3 = w2; w3 += 0" records, which is
* a plain equality. The two are separable only by the base's
* width
*/
if (reg->add_const == SIGN_EXTEND_32 && !known_reg->add_const) { reconstruct_sext32(reg, known_reg);
goto scratched;
}
if (reg->add_const == ADD_CONST_32 && reg->delta == 0 && !known_reg->add_const) {
reconstruct_zext32(reg, known_reg);
goto ...;
}
/*
* The reverse:
*/
if (known_reg->add_const == SIGN_EXTEND_32) continue;
if (known_reg->add_const == ADD_CONST_32 && known_reg->delta == 0 && get_reg_width(reg) > 32) continue;
There are other knock-on effects which use add_const as a bool.
log.c:655 if (reg->add_const) -> prints "%+d" delta
There are many more such places and would need to be handled for special case of add_const but delta=0 to mean something else.
My opinion would be stick to the current ZEXT,SEXT split.
Thx,
-Vineet
Re: [PATCH bpf-next v2 03/13] bpf: track low-32 scalar equality across zero-extending movs
Quoted 85 lines · Vineet Gupta
Quoted 21 lines · Alexei Starovoitov
Quoted 9 lines · Vineet Gupta
Linked-scalar equality is full-64-bit only. A 32-bit mov from a source with unknown high bits therefore has to drop the relationship, and a later narrowing of the source never reaches the destination:
r6 = ... /* full 64-bit unknown */ w7 = w6 /* 32-bit zero-extending mov */ if w6 != 0 goto ... /* not taken: r6's low 32 bits are 0 */ if w7 == 0 goto ... /* not deduced today */Quoted 5 lines
Record a low-32-only link instead: dst shares src's low 32 bits and its high half is zero. On a later narrowing,
sync_linked_regs()rebuilds such a register from the base rather than copying it, by re-applying the samezext_32_to_64()the mov used. The reverse direction is skipped: a ->subreg base knows nothing about a full register's high half.at the first glance
SUBREG_ZEXTis exactly the same asADD_CONST32delta == 0. no?
Both are unidirectional:w6->id== 1w7->id== 1,add_const== 32, delta == 0Quoted 4 lines
will zero extend w7.
This new
SUBREG_ZEXTwill do the same.
What am I missing?The 2 examples below both imply
ADD_CONST32+ delta=0, with different semantics and need special casing.w3 = w2; w3 += 0
w7 = w6; (r6 was wide)With code hacks it could in fact me made to work, but its less cleaner.
Current approach we have something like below in
sync_linked_regs()/*
* A ->subreg register shares only the base's low 32
bits, so it
* is rebuilt rather than copied. Not modelled together
with a
* delta, so skip if either side has one (sound, less
precise).*/ if (reg->subreg) { if (reg->add_const || known_reg->add_const) continue; if (reg->subreg == SUBREG_ZEXT) reconstruct_zext32(reg, known_reg); else reconstruct_sext32(reg, known_reg); if (e->is_reg) mark_reg_scratched(env, e->regno); else mark_stack_slot_scratched(env, e->spi); continue; } /* * The reverse: known_reg knows only its low 32 bits, which say * nothing about reg's high half. */ if (known_reg->subreg) continue;With the suggested approach it looks something like below.
ADD_CONST_32, delta == 0 has to be disambiguated from a real += 0 by inspecting another register's bounds./*
* A low-32 link shares only the base's low 32 bits, so it is
* rebuilt rather than copied.
*
*SIGN_EXTEND_32says so outright.ADD_CONST_32with
delta == 0
* does not: it is also what "w3 = w2; w3 += 0" records,
which is
* a plain equality. The two are separable only by the base's
* width
*/
if (reg->add_const==SIGN_EXTEND_32&&
Quoted 9 lines
!known_reg->add_const) {
reconstruct_sext32(reg, known_reg);
goto scratched;
}
if (reg->add_const == ADD_CONST_32 && reg->delta == 0 &&
!known_reg->add_const) {
reconstruct_zext32(reg, known_reg);
goto ...;
}I think that's a problem with reconstruct_zext32(). It shouldn't be necessary.
The existing code that adds a constant should already handle it.
If not, we have a bug in add_const_32. Instead of losing link at wx=wy time
we can keep it with delta == 0
and sync_linked_regs() shouldn't need any new code.
Re: [PATCH bpf-next v2 03/13] bpf: track low-32 scalar equality across zero-extending movs
Quoted 93 lines · Alexei Starovoitov
Quoted 83 lines · Vineet Gupta
Quoted 21 lines · Alexei Starovoitov
Quoted 9 lines · Vineet Gupta
Linked-scalar equality is full-64-bit only. A 32-bit mov from a source with unknown high bits therefore has to drop the relationship, and a later narrowing of the source never reaches the destination:
r6 = ... /* full 64-bit unknown */ w7 = w6 /* 32-bit zero-extending mov */ if w6 != 0 goto ... /* not taken: r6's low 32 bits are 0 */ if w7 == 0 goto ... /* not deduced today */Quoted 5 lines
Record a low-32-only link instead: dst shares src's low 32 bits and its high half is zero. On a later narrowing,
sync_linked_regs()rebuilds such a register from the base rather than copying it, by re-applying the samezext_32_to_64()the mov used. The reverse direction is skipped: a ->subreg base knows nothing about a full register's high half.at the first glance
SUBREG_ZEXTis exactly the same asADD_CONST32delta == 0. no?
Both are unidirectional:w6->id== 1w7->id== 1,add_const== 32, delta == 0Quoted 4 lines
will zero extend w7.
This new
SUBREG_ZEXTwill do the same.
What am I missing?The 2 examples below both imply
ADD_CONST32+ delta=0, with different semantics and need special casing.w3 = w2; w3 += 0
w7 = w6; (r6 was wide)With code hacks it could in fact me made to work, but its less cleaner.
Current approach we have something like below in
sync_linked_regs()/*
* A ->subreg register shares only the base's low 32
bits, so it
* is rebuilt rather than copied. Not modelled together
with a
* delta, so skip if either side has one (sound, less
precise).*/ if (reg->subreg) { if (reg->add_const || known_reg->add_const) continue; if (reg->subreg == SUBREG_ZEXT) reconstruct_zext32(reg, known_reg); else reconstruct_sext32(reg, known_reg); if (e->is_reg) mark_reg_scratched(env, e->regno); else mark_stack_slot_scratched(env, e->spi); continue; } /* * The reverse: known_reg knows only its low 32 bits, which say * nothing about reg's high half. */ if (known_reg->subreg) continue;With the suggested approach it looks something like below.
ADD_CONST_32, delta == 0 has to be disambiguated from a real += 0 by inspecting another register's bounds./*
* A low-32 link shares only the base's low 32 bits, so it is
* rebuilt rather than copied.
*
*SIGN_EXTEND_32says so outright.ADD_CONST_32with
delta == 0
* does not: it is also what "w3 = w2; w3 += 0" records,
which is
* a plain equality. The two are separable only by the base's
* width
*/
if (reg->add_const==SIGN_EXTEND_32&&Quoted 9 lines
!known_reg->add_const) { reconstruct_sext32(reg, known_reg); goto scratched; } if (reg->add_const == ADD_CONST_32 && reg->delta == 0 && !known_reg->add_const) { reconstruct_zext32(reg, known_reg); goto ...; }
Quoted 5 lines
I think that's a problem with
reconstruct_zext32(). It shouldn't be necessary.
The existing code that adds a constant should already handle it.
If not, we have a bug inadd_const_32.
Not really a bug, but a deliberate design choice in the past.
if (alu32 && (dst_umax > U32_MAX))
goto clear_id;
So the core change is ADD_CONST_32 needs to be allowed on wider regs. So treating it as
reg = (u32)(base + delta)
which simplifies to zero-extend for delta==0 and base can be either wide or narrow.
Quoted 3 lines
Instead of losing link at wx=wy time
we can keep it with delta == 0
andsync_linked_regs()shouldn't need any new code.
I toyed with a prototype which essentially lifts the restriction above (and ensuing adjustments) FWIW it *does* require a reverse guard in sync_linked_regs() - so some additional code there (at least in my version).
It ended up with full testsuite run parity - after 4 incremental patches.
But the pattern of all those patches was adding some predicate / special-casing to reg->add_const
hunk 1
- if (src_reg->add_const)
+ if (src_reg->add_const && src_reg->delta)
hunk 2
- if (dst_reg->add_const) {
+ if (dst_reg->add_const && !dst_reg->delta &&
+ dst_reg->add_const == (alu32 ? ADD_CONST_32 : ADD_CONST_64)) { + dst_reg->delta = off;
+ } else if (dst_reg->add_const) {
hunk 3
- if (subreg_link && reg->id)
- state->regs[dst_regno].subreg = is_ldsx ? SUBREG_SEXT : SUBREG_ZEXT; + if (subreg_link && reg->id) {
+ if (is_ldsx) {
+ state->regs[dst_regno].subreg_sext = true; + } else {
+ state->regs[dst_regno].add_const = ADD_CONST_32; + state->regs[dst_regno].delta = 0;
+ }
+ }
hunk 4
- if (known_reg->subreg)
+ if (known_reg->subreg_sext)
+ continue;
+ /*
+ * Same for a zero-extending link, now spelled ADD_CONST_32:
+ * reg == (u32)(base + delta) does not invert once the base is + * wider than 32 bits.
+ */
+ if (known_reg->add_const == ADD_CONST_32 &&
+ get_reg_width(reg) > 32)
continue;
Yes it does allow removal of reconstruct_zext32()
- if (reg->subreg) {
+ if (reg->subreg_sext) {
if (reg->add_const || known_reg->add_const) continue;
- if (reg->subreg == SUBREG_ZEXT) - reconstruct_zext32(reg, known_reg); - else
- reconstruct_sext32(reg, known_reg); + reconstruct_sext32(reg, known_reg);
but personally speaking reading the code feels a bit more harder now.
I can send over the full patch which converts the v2 SUBREG_ZEXT into ADD_CONST32+delta=0 to give a feel for all the special casings, were it to be subsumed into the orig zext support work, but I think you understand what I'm getting at ;-)
Happy to pursue whatever your maintainer hat tells you.
Thx,
-Vineet
Re: [PATCH bpf-next v2 03/13] bpf: track low-32 scalar equality across zero-extending movs
Review
Quoted 9 lines · Vineet Gupta
It ended up with full testsuite run parity - after 4 incremental patches. But the pattern of all those patches was adding some predicate / special-casing to
reg->add_consthunk 1
(quoted diff) +1
-1- if (src_reg->add_const) + if (src_reg->add_const && src_reg->delta)
why? It should not.
My point is that zero is not special.
It should be handled within the current framework. All these extra hunks are not correct. ADD_CONST_32 logic should work for delta == 0 just like it works for delta == 1.
Eduard Zingerman
maintainerRe: [PATCH bpf-next v2 03/13] bpf: track low-32 scalar equality across zero-extending movs
Quoted 11 lines · Alexei Starovoitov
Review
Quoted 9 lines · Vineet Gupta
It ended up with full testsuite run parity - after 4 incremental patches. But the pattern of all those patches was adding some predicate / special-casing to
reg->add_consthunk 1
(quoted diff) +1
-1- if (src_reg->add_const) + if (src_reg->add_const && src_reg->delta)
Quoted 6 lines
why? It should not.
My point is that zero is not special.
It should be handled within the current framework. All these extra hunks are not correct.ADD_CONST_32logic should work for delta == 0 just like it works for delta == 1.
After thinking about it some more, I agree that having an orthogonal encoding would be nice. However, it appears that the split should be somewhat different:
struct bpf_reg_state {
...
s32 delta;
u32 id;
enum id_link_kind { full, zext, sext } link_kind;
...
}Where:
- id == 0 => no id link
- full => all 64-bits of the register are identical to
all 64-bits of a scalar value `id' (let's call it X).
∀ rA{.id == X, .link == full}, rB{X,full} => rA == rB
- zext => lower 32-bits of the register are identical to
lower 32-bits of a scalar value X,
upper 32-bits of the register are null.
∀ rA{.id == X, .link == ?}, rB{X,zext} => rA % 32 == rB % 32
- sext => lower 32-bits of the register are identical to
lower 32-bits of a scalar value X,
upper 32-bits of the register are either 0 or 1,
depending on the bit 31 value.
∀ rA{.id == X, .link == ?}, rB{X,sext} => sext(rA % 32) == sext(rB % 32)
The reason for such subdivision is that:
(X + delta) % 32 == X % 32 + delta % 32 == X % 32 + delta iff delta < 2^32
Meaning that a non-zero delta can still be used to infer the state of the lower 32-bits, e.g.:
- if r1 = (X + delta) % 32
- and r2 = X
- and there is a comparison if r1 < 42 goto ...
This comparison adds constraints on lower bits of r1, and it is correct to transfer these constraints to lower bits of r2 by subtracting delta from r1 and using lower bits of the result.
Re: [PATCH bpf-next v2 03/13] bpf: track low-32 scalar equality across zero-extending movs
Quoted 31 lines · Eduard Zingerman
Quoted 11 lines · Alexei Starovoitov
Review
Quoted 9 lines · Vineet Gupta
It ended up with full testsuite run parity - after 4 incremental patches. But the pattern of all those patches was adding some predicate / special-casing to
reg->add_consthunk 1
(quoted diff) +1
-1- if (src_reg->add_const) + if (src_reg->add_const && src_reg->delta)Quoted 6 lines
why? It should not.
My point is that zero is not special.
It should be handled within the current framework. All these extra hunks are not correct.ADD_CONST_32logic should work for delta == 0 just like it works for delta == 1.After thinking about it some more, I agree that having an orthogonal encoding would be nice. However, it appears that the split should be somewhat different:
struct bpf_reg_state { ... s32 delta; u32 id; enum id_link_kind { full, zext, sext } link_kind; ... }
Quoted 14 lines
Where:
- id == 0 => no id link
- full => all 64-bits of the register are identical to
all 64-bits of a scalar value `id' (let's call it X).
∀ rA{.id == X, .link == full}, rB{X,full} => rA == rB
- zext => lower 32-bits of the register are identical to
lower 32-bits of a scalar value X,
upper 32-bits of the register are null.
∀ rA{.id == X, .link == ?}, rB{X,zext} => rA % 32 == rB % 32
- sext => lower 32-bits of the register are identical to
lower 32-bits of a scalar value X,
upper 32-bits of the register are either 0 or 1,
depending on the bit 31 value.
∀ rA{.id == X, .link == ?}, rB{X,sext} => sext(rA % 32) == sext(rB % 32)
hmm.
there is also 32-bit link with delta, right?
Quoted 10 lines
The reason for such subdivision is that:
(X + delta) % 32 == X % 32 + delta % 32 == X % 32 + delta iff delta < 2^32
Meaning that a non-zero delta can still be used to infer the state of the lower 32-bits, e.g.:
- if r1 = (X + delta) % 32
- and r2 = X
- and there is a comparisonif r1 < 42 goto ...
Quoted 3 lines
This comparison adds constraints on lower bits of r1, and it is correct to transfer these constraints to lower bits of r2 by subtracting delta from r1 and using lower bits of the result.
Not sure what you're arguing about.
My only point is that 32-bit link with delta makes special handling of zext unnecessary.
I still don't hear a strong reason why it needs to be handled outside of 32-bit-link-with-delta.
Eduard Zingerman
maintainerRe: [PATCH bpf-next v2 03/13] bpf: track low-32 scalar equality across zero-extending movs
Quoted 47 lines · Alexei Starovoitov
Quoted 31 lines · Eduard Zingerman
Quoted 11 lines · Alexei Starovoitov
Review
Quoted 9 lines · Vineet Gupta
It ended up with full testsuite run parity - after 4 incremental patches. But the pattern of all those patches was adding some predicate / special-casing to
reg->add_consthunk 1
(quoted diff) +1
-1- if (src_reg->add_const) + if (src_reg->add_const && src_reg->delta)Quoted 6 lines
why? It should not.
My point is that zero is not special.
It should be handled within the current framework. All these extra hunks are not correct.ADD_CONST_32logic should work for delta == 0 just like it works for delta == 1.After thinking about it some more, I agree that having an orthogonal encoding would be nice. However, it appears that the split should be somewhat different:
struct bpf_reg_state { ... s32 delta; u32 id; enum id_link_kind { full, zext, sext } link_kind; ... }Quoted 14 lines
Where:
- id == 0 => no id link
- full => all 64-bits of the register are identical to
all 64-bits of a scalar value `id' (let's call it X).
∀ rA{.id == X, .link == full}, rB{X,full} => rA == rB
- zext => lower 32-bits of the register are identical to
lower 32-bits of a scalar value X,
upper 32-bits of the register are null.
∀ rA{.id == X, .link == ?}, rB{X,zext} => rA % 32 == rB % 32
- sext => lower 32-bits of the register are identical to
lower 32-bits of a scalar value X,
upper 32-bits of the register are either 0 or 1,
depending on the bit 31 value.
∀ rA{.id == X, .link == ?}, rB{X,sext} => sext(rA % 32) == sext(rB % 32)
Quoted 2 lines
hmm.
there is also 32-bit link with delta, right?
My point is that delta is independent of 32-bit/64-bit property. `delta' can be used to propagate in both directions:
- full 64 bit -> 32 bit sign/zero-extened
- 32 bit sign/zero-extened -> full 64-bit
Quoted 14 lines
Quoted 10 lines
The reason for such subdivision is that:
(X + delta) % 32 == X % 32 + delta % 32 == X % 32 + delta iff delta < 2^32
Meaning that a non-zero delta can still be used to infer the state of the lower 32-bits, e.g.:
- if r1 = (X + delta) % 32
- and r2 = X
- and there is a comparisonif r1 < 42 goto ...Quoted 3 lines
This comparison adds constraints on lower bits of r1, and it is correct to transfer these constraints to lower bits of r2 by subtracting delta from r1 and using lower bits of the result.
Quoted 5 lines
Not sure what you're arguing about.
My only point is that 32-bit link with delta makes special handling of zext unnecessary.
I still don't hear a strong reason why it needs to be handled outside of 32-bit-link-with-delta.
I'm arguing that the following encoding:
- ADD_CONST_32 (delta is valid, sign extend flag invalid)
- ADD_CONST_64 (delta is valid, sign extend flag invalid)
- sign extend flag (delta is invalid)
I strictly worse.
Re: [PATCH bpf-next v2 03/13] bpf: track low-32 scalar equality across zero-extending movs
Quoted 48 lines · Eduard Zingerman
Quoted 47 lines · Alexei Starovoitov
Quoted 45 lines · Eduard Zingerman
Quoted 11 lines · Alexei Starovoitov
Review
Quoted 9 lines · Vineet Gupta
It ended up with full testsuite run parity - after 4 incremental patches. But the pattern of all those patches was adding some predicate / special-casing to
reg->add_consthunk 1
(quoted diff) +1
-1- if (src_reg->add_const) + if (src_reg->add_const && src_reg->delta)Quoted 6 lines
why? It should not.
My point is that zero is not special.
It should be handled within the current framework. All these extra hunks are not correct.ADD_CONST_32logic should work for delta == 0 just like it works for delta == 1.After thinking about it some more, I agree that having an orthogonal encoding would be nice. However, it appears that the split should be somewhat different:
struct bpf_reg_state { ... s32 delta; u32 id; enum id_link_kind { full, zext, sext } link_kind; ... }Where:
- id == 0 => no id link
- full => all 64-bits of the register are identical to
all 64-bits of a scalar value `id' (let's call it X).
∀ rA{.id == X, .link == full}, rB{X,full} => rA == rB
- zext => lower 32-bits of the register are identical to
lower 32-bits of a scalar value X,
upper 32-bits of the register are null.
∀ rA{.id == X, .link == ?}, rB{X,zext} => rA % 32 == rB % 32
- sext => lower 32-bits of the register are identical to
lower 32-bits of a scalar value X,
upper 32-bits of the register are either 0 or 1,
depending on the bit 31 value.
∀ rA{.id == X, .link == ?}, rB{X,sext} => sext(rA % 32) == sext(rB % 32)
Quoted 7 lines
Quoted 2 lines
hmm.
there is also 32-bit link with delta, right?My point is that delta is independent of 32-bit/64-bit property. `delta' can be used to propagate in both directions:
- full 64 bit -> 32 bit sign/zero-extened
- 32 bit sign/zero-extened -> full 64-bit
both? how ?
I was under impression that in 32-bit domain delta is one way. rX = ...
wY = wX
wY += 5
if wY == 10
We cannot do -5 to rX
and we cannot use your above 'full' encoding for wY += 5. Currently we use BPF_ADD_CONST32 for wY += 5
I don't see how 'full' can work.
Eduard Zingerman
maintainerRe: [PATCH bpf-next v2 03/13] bpf: track low-32 scalar equality across zero-extending movs
Quoted 57 lines · Alexei Starovoitov
Quoted 48 lines · Eduard Zingerman
Quoted 47 lines · Alexei Starovoitov
Quoted 45 lines · Eduard Zingerman
Quoted 11 lines · Alexei Starovoitov
Review
Quoted 9 lines · Vineet Gupta
It ended up with full testsuite run parity - after 4 incremental patches. But the pattern of all those patches was adding some predicate / special-casing to
reg->add_consthunk 1
(quoted diff) +1
-1- if (src_reg->add_const) + if (src_reg->add_const && src_reg->delta)Quoted 6 lines
why? It should not.
My point is that zero is not special.
It should be handled within the current framework. All these extra hunks are not correct.ADD_CONST_32logic should work for delta == 0 just like it works for delta == 1.After thinking about it some more, I agree that having an orthogonal encoding would be nice. However, it appears that the split should be somewhat different:
struct bpf_reg_state { ... s32 delta; u32 id; enum id_link_kind { full, zext, sext } link_kind; ... }Where:
- id == 0 => no id link
- full => all 64-bits of the register are identical to
all 64-bits of a scalar value `id' (let's call it X).
∀ rA{.id == X, .link == full}, rB{X,full} => rA == rB
- zext => lower 32-bits of the register are identical to
lower 32-bits of a scalar value X,
upper 32-bits of the register are null.
∀ rA{.id == X, .link == ?}, rB{X,zext} => rA % 32 == rB % 32
- sext => lower 32-bits of the register are identical to
lower 32-bits of a scalar value X,
upper 32-bits of the register are either 0 or 1,
depending on the bit 31 value.
∀ rA{.id == X, .link == ?}, rB{X,sext} => sext(rA % 32) == sext(rB % 32)Quoted 7 lines
Quoted 2 lines
hmm.
there is also 32-bit link with delta, right?My point is that delta is independent of 32-bit/64-bit property. `delta' can be used to propagate in both directions:
- full 64 bit -> 32 bit sign/zero-extened
- 32 bit sign/zero-extened -> full 64-bit
Quoted 8 lines
both? how ?
I was under impression that in 32-bit domain delta is one way. rX = ...
wY = wX
wY += 5if wY == 10
We cannot do -5 to rX
Why?
It is still valid to transfer r32 and tnum_subreg knowledge from wY to rX.
wY + 5 == rX % 32 + 5 => hence rX % 32 knowledge can be recovered.
If rX itself had some delta, e.g.:
rX = ...
rX += 7
wY = wX
wY += 5
Then it would still be possible:
wY + 5 == (rX - 7) % 32 + 5 = rX % 32 - 2.
Again, in case of this direction, only lower 32-bits of the 'full' register can be inferred.
Quoted 3 lines
and we cannot use your above 'full' encoding for wY += 5. Currently we use
BPF_ADD_CONST32for wY += 5
I don't see how 'full' can work.
Re: [PATCH bpf-next v2 03/13] bpf: track low-32 scalar equality across zero-extending movs
Quoted 45 lines · Eduard Zingerman
Quoted 24 lines
Quoted 16 lines
Quoted 16 lines
Quoted 15 lines
Where:
- id == 0 => no id link
- full => all 64-bits of the register are identical to
all 64-bits of a scalar value `id' (let's call it X).
∀ rA{.id == X, .link == full}, rB{X,full} => rA == rB
- zext => lower 32-bits of the register are identical to
lower 32-bits of a scalar value X,
upper 32-bits of the register are null.
∀ rA{.id == X, .link == ?}, rB{X,zext} => rA % 32 == rB % 32
- sext => lower 32-bits of the register are identical to
lower 32-bits of a scalar value X,
upper 32-bits of the register are either 0 or 1,
depending on the bit 31 value.
∀ rA{.id == X, .link == ?}, rB{X,sext} => sext(rA % 32) == sext(rB % 32)Quoted 7 lines
Quoted 2 lines
hmm.
there is also 32-bit link with delta, right?My point is that delta is independent of 32-bit/64-bit property. `delta' can be used to propagate in both directions:
- full 64 bit -> 32 bit sign/zero-extened
- 32 bit sign/zero-extened -> full 64-bitQuoted 8 lines
both? how ?
I was under impression that in 32-bit domain delta is one way. rX = ...
wY = wX
wY += 5if wY == 10
We cannot do -5 to rXWhy?
It is still valid to transfer r32 andtnum_subregknowledge from wY to rX.wY + 5 == rX % 32 + 5 => hence rX % 32 knowledge can be recovered.
If rX itself had some delta, e.g.:
rX = ...
rX += 7
wY = wX
wY += 5
Quoted 6 lines
Then it would still be possible:
wY + 5 == (rX - 7) % 32 + 5 = rX % 32 - 2.
Again, in case of this direction, only lower 32-bits of the 'full' register can be inferred.
Ok, so we're argeeing that it's not 'full' in your above definition. Your enum id_link_kind needs a 4th category : apply-delta-to-lower-32bit-... and it's not bi-directional.
rX = ...
wY = wX
wY += 5
if wY == 10
here can apply -5 to lower 32-bit of rX only.
rX = ...
wY = wX
wY += 5
if rX == 10
here can apply +5 to lower 32-bit of wY _and_ do zero extend into full rY.
I don't see a value of 'zext' kind alone that doesn't do 'add delta'.
Eduard Zingerman
maintainerRe: [PATCH bpf-next v2 03/13] bpf: track low-32 scalar equality across zero-extending movs
Quoted 48 lines · Alexei Starovoitov
Quoted 47 lines · Eduard Zingerman
Quoted 24 lines
Quoted 16 lines
Quoted 16 lines
Quoted 15 lines
Where:
- id == 0 => no id link
- full => all 64-bits of the register are identical to
all 64-bits of a scalar value `id' (let's call it X).
∀ rA{.id == X, .link == full}, rB{X,full} => rA == rB
- zext => lower 32-bits of the register are identical to
lower 32-bits of a scalar value X,
upper 32-bits of the register are null.
∀ rA{.id == X, .link == ?}, rB{X,zext} => rA % 32 == rB % 32
- sext => lower 32-bits of the register are identical to
lower 32-bits of a scalar value X,
upper 32-bits of the register are either 0 or 1,
depending on the bit 31 value.
∀ rA{.id == X, .link == ?}, rB{X,sext} => sext(rA % 32) == sext(rB % 32)Quoted 7 lines
Quoted 2 lines
hmm.
there is also 32-bit link with delta, right?My point is that delta is independent of 32-bit/64-bit property. `delta' can be used to propagate in both directions:
- full 64 bit -> 32 bit sign/zero-extened
- 32 bit sign/zero-extened -> full 64-bitQuoted 8 lines
both? how ?
I was under impression that in 32-bit domain delta is one way. rX = ...
wY = wX
wY += 5if wY == 10
We cannot do -5 to rXWhy?
It is still valid to transfer r32 andtnum_subregknowledge from wY to rX.wY + 5 == rX % 32 + 5 => hence rX % 32 knowledge can be recovered.
If rX itself had some delta, e.g.:
rX = ...
rX += 7
wY = wX
wY += 5Then it would still be possible:
Quoted 8 lines
Quoted 4 lines
wY + 5 == (rX - 7) % 32 + 5 = rX % 32 - 2.
Again, in case of this direction, only lower 32-bits of the 'full' register can be inferred.
Ok, so we're argeeing that it's not 'full' in your above definition. Your enum
id_link_kindneeds a 4th category : apply-delta-to-lower-32bit-... and it's not bi-directional.
It's not really a category, it's just a direction in a sync function:
- if known_reg is 'full' -> sync to sext/zext register recovers lower 32-bits and infers upper
- if known_reg is sext/zext -> sync to 'full' register recovers only lower 32-bits and keeps upper untouched (counting on cross-domain bounds sync logic).
- 'full' -> 'full' and 'sext/zext' -> 'sext/zext' syncs are trivial.
Quoted 6 lines
rX = ...
wY = wX
wY += 5
if wY == 10
here can apply -5 to lower 32-bit of rX only.
Quoted 7 lines
rX = ...
wY = wX
wY += 5
if rX == 10
here can apply +5 to lower 32-bit of wY _and_ do zero extend into full rY.I don't see a value of 'zext' kind alone that doesn't do 'add delta'.
Exactly, that's why I suggest this as a completely orthogonal encoding. Effectively for an abstract scalar value X it would encode whether the particular register is:
- X + delta
- zext(X + delta)
- sext(X + delta)
Re: [PATCH bpf-next v2 03/13] bpf: track low-32 scalar equality across zero-extending movs
Quoted 78 lines · Eduard Zingerman
Quoted 48 lines · Alexei Starovoitov
Quoted 47 lines · Eduard Zingerman
Quoted 24 lines
Quoted 16 lines
Quoted 16 lines
Quoted 15 lines
Where:
- id == 0 => no id link
- full => all 64-bits of the register are identical to
all 64-bits of a scalar value `id' (let's call it X).
∀ rA{.id == X, .link == full}, rB{X,full} => rA == rB
- zext => lower 32-bits of the register are identical to
lower 32-bits of a scalar value X,
upper 32-bits of the register are null.
∀ rA{.id == X, .link == ?}, rB{X,zext} => rA % 32 == rB % 32
- sext => lower 32-bits of the register are identical to
lower 32-bits of a scalar value X,
upper 32-bits of the register are either 0 or 1,
depending on the bit 31 value.
∀ rA{.id == X, .link == ?}, rB{X,sext} => sext(rA % 32) == sext(rB % 32)Quoted 7 lines
Quoted 2 lines
hmm.
there is also 32-bit link with delta, right?My point is that delta is independent of 32-bit/64-bit property. `delta' can be used to propagate in both directions:
- full 64 bit -> 32 bit sign/zero-extened
- 32 bit sign/zero-extened -> full 64-bitQuoted 8 lines
both? how ?
I was under impression that in 32-bit domain delta is one way. rX = ...
wY = wX
wY += 5if wY == 10
We cannot do -5 to rXWhy?
It is still valid to transfer r32 andtnum_subregknowledge from wY to rX.wY + 5 == rX % 32 + 5 => hence rX % 32 knowledge can be recovered.
If rX itself had some delta, e.g.:
rX = ...
rX += 7
wY = wX
wY += 5Then it would still be possible:
Quoted 8 lines
Quoted 4 lines
wY + 5 == (rX - 7) % 32 + 5 = rX % 32 - 2.
Again, in case of this direction, only lower 32-bits of the 'full' register can be inferred.
Ok, so we're argeeing that it's not 'full' in your above definition. Your enum
id_link_kindneeds a 4th category : apply-delta-to-lower-32bit-... and it's not bi-directional.It's not really a category, it's just a direction in a sync function:
- ifknown_regis 'full' -> sync to sext/zext register recovers lower 32-bits and infers upper
- ifknown_regis sext/zext -> sync to 'full' register recovers only lower 32-bits and keeps upper untouched (counting on cross-domain bounds sync logic).
- 'full' -> 'full' and 'sext/zext' -> 'sext/zext' syncs are trivial.Quoted 12 lines
rX = ...
wY = wX
wY += 5
if wY == 10
here can apply -5 to lower 32-bit of rX only.rX = ...
wY = wX
wY += 5
if rX == 10
here can apply +5 to lower 32-bit of wY _and_ do zero extend into full rY.
Quoted 8 lines
Quoted 1 line
I don't see a value of 'zext' kind alone that doesn't do 'add delta'.
Exactly, that's why I suggest this as a completely orthogonal encoding. Effectively for an abstract scalar value X it would encode whether the particular register is:
- X + delta
- zext(X + delta)
- sext(X + delta)
ahh. it wasn't clear to me that 'zext' you're proposing does '+ delta'. Now I see that your zext is the same as apply-delta-to-lower-32bit-and-zext as I was talking about all along.
Re: [PATCH bpf-next v2 03/13] bpf: track low-32 scalar equality across zero-extending movs
Quoted 79 lines · Alexei Starovoitov
Quoted 71 lines · Eduard Zingerman
Quoted 43 lines · Alexei Starovoitov
Quoted 42 lines · Eduard Zingerman
Quoted 20 lines
Quoted 14 lines
Quoted 14 lines
Quoted 14 lines
Where:
- id == 0 => no id link
- full => all 64-bits of the register are identical to
all 64-bits of a scalar value `id' (let's call it X).
∀ rA{.id == X, .link == full}, rB{X,full} => rA == rB
- zext => lower 32-bits of the register are identical to
lower 32-bits of a scalar value X,
upper 32-bits of the register are null.
∀ rA{.id == X, .link == ?}, rB{X,zext} => rA % 32 == rB % 32
- sext => lower 32-bits of the register are identical to
lower 32-bits of a scalar value X,
upper 32-bits of the register are either 0 or 1,
depending on the bit 31 value.
∀ rA{.id == X, .link == ?}, rB{X,sext} => sext(rA % 32) == sext(rB % 32)Quoted 6 lines
Quoted 2 lines
hmm.
there is also 32-bit link with delta, right?My point is that delta is independent of 32-bit/64-bit property. `delta' can be used to propagate in both directions:
- full 64 bit -> 32 bit sign/zero-extened
- 32 bit sign/zero-extened -> full 64-bitQuoted 8 lines
both? how ?
I was under impression that in 32-bit domain delta is one way. rX = ...
wY = wX
wY += 5if wY == 10
We cannot do -5 to rXWhy?
It is still valid to transfer r32 andtnum_subregknowledge from wY to rX.wY + 5 == rX % 32 + 5 => hence rX % 32 knowledge can be recovered.If rX itself had some delta, e.g.:
rX = ... rX += 7 wY = wX wY += 5Then it would still be possible:
Quoted 7 lines
Quoted 4 lines
wY + 5 == (rX - 7) % 32 + 5 = rX % 32 - 2.Again, in case of this direction, only lower 32-bits of the 'full' register can be inferred.
Ok, so we're argeeing that it's not 'full' in your above definition. Your enum
id_link_kindneeds a 4th category : apply-delta-to-lower-32bit-... and it's not bi-directional.It's not really a category, it's just a direction in a sync function:
- ifknown_regis 'full' -> sync to sext/zext register recovers lower 32-bits and infers upper
- ifknown_regis sext/zext -> sync to 'full' register recovers only lower 32-bits and keeps upper untouched (counting on cross-domain bounds sync logic).
- 'full' -> 'full' and 'sext/zext' -> 'sext/zext' syncs are trivial.Quoted 12 lines
rX = ...
wY = wX
wY += 5
if wY == 10
here can apply -5 to lower 32-bit of rX only.rX = ...
wY = wX
wY += 5
if rX == 10
here can apply +5 to lower 32-bit of wY _and_ do zero extend into full rY.Quoted 7 lines
Quoted 1 line
I don't see a value of 'zext' kind alone that doesn't do 'add delta'.
Exactly, that's why I suggest this as a completely orthogonal encoding. Effectively for an abstract scalar value X it would encode whether the particular register is:
- X + delta
- zext(X + delta)
- sext(X + delta)
Quoted 3 lines
ahh. it wasn't clear to me that 'zext' you're proposing does '+ delta'. Now I see that your zext is the same as apply-delta-to-lower-32bit-and-zext as I was talking about all along.
So to close the loop on this v3 will support the above three forms: add_const:2 and subreg_ext:1merge into one {none,
And just to recap, we will be adding two features:
- adding the sext with delta
- reverse syncing of low 32 bits
Thx,
-Vineet
PATCH v2 4/13 selftests/bpf: cover the low-32 link for zero-extending movs
In reply to Vineet GuptaExercise each decision the previous patch adds:
- zext_mov_narrow_src: narrowing the source reaches the destination
- zext_narrow_dst_keeps_base: the reverse must not happen, the base's high bits are still unknown
- zext_u32_src_is_full_link: a provably-u32 source keeps taking the full-equality path
- zext_self_mov_no_link: a self-mov mints no id
- zext_chain_keeps_link: a linked source survives a further 32-bit mov
- zext_no_sync_when_base_has_delta, zext_no_sync_from_subreg_base: a delta on either side stops propagation, in both directions
- zext_sync_between_two_subregs: two low-32 links on one base do reach each other
- zext_unlinked_path_stays_reachable: only one path links r7 to r8, so the guarded div stays reachable
- zext_mov_breaks_add_const_src: forming the link drops a delta link on the source, as the narrow-source path has always done
Written in asm so the bytecode is the same whichever compiler built the suite.
These three check an outcome rather than a mechanism: the states they compare differ in ids, contents or ranges, so regsafe() keeps them apart for reasons of its own and no single check can be disabled to make them fail.
---
v2: was RFC 4/6.
- all tests live in verifier_linked_scalars.c (Eduard)
- numeric labels, and the verifier_bounds regex left as-is bar the id (Eduard)
- dropped the LLM-written commentary and the redundant second bpf_get_prandom_u32() (Eduard)
- covers the seven cases listed on RFC 4/6
- the dest-driven test had the polarity flaw sashiko found on 6/6; its == guard now discriminates, verified by disabling the guard it targets
- three tests renamed for what they check, see the cover letter
.../bpf/progs/verifier_linked_scalars.c | 256 ++++++++++++++++++ 1 file changed, 256 insertions(+)
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +256 -0
@@ -710,4 +710,260 @@ l_exit_%=: \ : __clobber_all); } +/* +* A 32-bit mov from a wide source shares only the low 32 bits. Narrowing the +* source must reach the destination through that link. +*/ +SEC("socket") +__success +__naked void zext_mov_narrow_src (void ) +{ + asmvolatile (" \ +call %[bpf_get_prandom_u32]; \ +r6 = r0; \ +w7 = w6; /* forms the link */ \ +if w6 != 0 goto 1f; /* narrows r6, propagates to r7 */ \ +if w7 == 0 goto 1f; \ +r0 /= 0; \ +1: \ +r0 = 0; \ +exit; \ +" : + : __imm(bpf_get_prandom_u32) + : __clobber_all); +} + +/* +* The reverse does not hold: narrowing the low-32 link says nothing about the +* base's high bits, so r6 must stay unknown and the div stays reachable. +*/ +SEC("socket") +__failure __msg("div by zero") +__naked void zext_narrow_dst_keeps_base(void) +{ + asmvolatile (" \ +call %[bpf_get_prandom_u32]; \ +r6 = r0; \ +w7 = w6; /* forms the link */ \ +if r7 != 0 goto 1f; /* narrows r7, must not propagate to r6 */ \ +if r6 == 0 goto 1f; /* taken only if r6 wrongly narrowed */ \ +r0 /= 0; \ +1: \ +r0 = 0; \ +exit; \ +" : + : __imm(bpf_get_prandom_u32) + : __clobber_all); +} + +/* +* A provably-u32 source takes the full-equality path, not the low-32 one: +* narrowing the destination must reach the source. +*/ +SEC("socket") +__success +__naked void zext_u32_src_is_full_link (void ) +{ + asmvolatile (" \ +call %[bpf_get_prandom_u32]; \ +w6 = w0; /* r6 provably u32 */ \ +w7 = w6; /* full link, not low-32 */ \ +if r7 > 10 goto 1f; /* narrows r7, propagates to r6 */ \ +if r6 > 10 goto 2f; \ +goto 1f; \ +2: \ +r0 /= 0; \ +1: \ +r0 = 0; \ +exit; \ +" : + : __imm(bpf_get_prandom_u32) + : __clobber_all); +} + +/* +* A self-mov has nothing to link, so it must not mint an id for r6. +*/ +SEC("socket") +__success __log_level(2) +/* an id would print as R6=scalar(id=N.lo32,smin=... */ +__msg("(bc) w6 = w6 {{.*}} R6=scalar(smin=0,") +__naked void zext_self_mov_no_link (void ) +{ + asmvolatile (" \ +call %[bpf_get_prandom_u32]; \ +r6 = r0; \ +r6 ^= 0; /* drop the id */ \ +w6 = w6; /* forms no link */ \ +r0 = 0; \ +exit; \ +" : + : __imm(bpf_get_prandom_u32) + : __clobber_all); +} + +/* +* A low-32-linked source keeps its id and flag across a further 32-bit mov, +* so narrowing the base still reaches the end of the chain. +*/ +SEC("socket") +__success +__naked void zext_chain_keeps_link (void ) +{ + asmvolatile (" \ +call %[bpf_get_prandom_u32]; \ +r6 = r0; \ +w7 = w6; /* forms the link */ \ +w8 = w7; /* link survives the 2nd mov */ \ +if w6 != 0 goto 1f; /* narrows r6, propagates to r8 */ \ +if w8 == 0 goto 1f; \ +r0 /= 0; \ +1: \ +r0 = 0; \ +exit; \ +" : + : __imm(bpf_get_prandom_u32) + : __clobber_all); +} + +/* +* A delta on either side is not modelled together with a low-32 link, so no +* range propagates: here the branch register carries the delta. +*/ +SEC("socket") +__failure __msg("div by zero") +__naked void zext_no_sync_when_base_has_delta(void) +{ + asmvolatile (" \ +call %[bpf_get_prandom_u32]; \ +r6 = r0; \ +w7 = w6; /* forms the link */ \ +r8 = r6; \ +r8 += 3; /* delta on the branch reg */ \ +if r8 != 3 goto 1f; /* must not propagate to r7 */ \ +if w7 == 0 goto 1f; \ +r0 /= 0; \ +1: \ +r0 = 0; \ +exit; \ +" : + : __imm(bpf_get_prandom_u32) + : __clobber_all); +} + +/* +* ... and here the low-32 link is the branch register, so the register +* carrying the delta must not be narrowed either. +*/ +SEC("socket") +__failure __msg("div by zero") +__naked void zext_no_sync_from_subreg_base(void) +{ + asmvolatile (" \ +call %[bpf_get_prandom_u32]; \ +r6 = r0; \ +w7 = w6; /* forms the link */ \ +r8 = r6; \ +r8 += 3; /* delta on r8 */ \ +if w7 != 0 goto 1f; /* must not propagate to r8 */ \ +if r8 == 3 goto 1f; /* taken only if r8 wrongly narrowed */ \ +r0 /= 0; \ +1: \ +r0 = 0; \ +exit; \ +" : + : __imm(bpf_get_prandom_u32) + : __clobber_all); +} + +/* +* Two low-32 links on the same base do propagate to each other: both are the +* zero-extension of the same low 32 bits. +*/ +SEC("socket") +__success +__naked void zext_sync_between_two_subregs (void ) +{ + asmvolatile (" \ +call %[bpf_get_prandom_u32]; \ +r6 = r0; \ +w7 = w6; /* two links on one base */ \ +w8 = w6; \ +if w7 != 0 goto 1f; /* narrows r7, propagates to r8 */ \ +if w8 == 0 goto 1f; \ +r0 /= 0; \ +1: \ +r0 = 0; \ +exit; \ +" : + : __imm(bpf_get_prandom_u32) + : __clobber_all); +} + +/* +* Only one of the two paths links r7 to r8, so the narrowing of w8 reaches r7 +* on one and not the other and the div stays reachable. This checks the +* outcome, not the mechanism: the two states differ in their ids and contents, +* so regsafe() has many reasons to keep them apart and disabling any single +* one of its checks does not make this fail. +*/ +SEC("socket") +__failure __msg("div by zero") +__flag (BPF_F_TEST_STATE_FREQ) +__naked void zext_unlinked_path_stays_reachable(void) +{ + asmvolatile (" \ +call %[bpf_get_prandom_u32]; \ +r6 = r0; \ +r6 &= 1; \ +if r6 >= 1 goto 2f; \ +/* explored first: r7 is a low-32 link of r8 */ \ +call %[bpf_get_prandom_u32]; \ +r8 = r0; \ +w7 = w8; /* forms the link */ \ +goto 1f; \ +2: \ +/* runtime path: r7 unrelated to r8 */ \ +call %[bpf_get_prandom_u32]; \ +r8 = r0; \ +call %[bpf_get_prandom_u32]; \ +w7 = w0; /* no link here */ \ +1: \ +if w8 != 0 goto 3f; /* propagates to r7 only if linked */ \ +if w7 == 0 goto 3f; \ +r0 /= 0; \ +3: \ +r0 = 0; \ +exit; \ +" : + : __imm(bpf_get_prandom_u32) + : __clobber_all); +} + +/* +* Forming the link calls assign_scalar_id_before_mov(), which drops a delta +* link on the source. That is what the narrow-source path has always done, +* so a wide source behaves the same: r5 stops tracking r6. +*/ +SEC("socket") +__failure __msg("div by zero") +__naked void zext_mov_breaks_add_const_src(void) +{ + asmvolatile (" \ +call %[bpf_get_prandom_u32]; \ +r6 = r0; \ +r5 = r6; /* r5, r6 linked */ \ +r5 += 3; /* r5 = base + 3 */ \ +w7 = w5; /* breaks r5's delta link */ \ +if r6 > 9 goto 1f; /* r6 in [0, 9] */ \ +if r5 < 13 goto 1f; /* taken only if r5 still linked */ \ +r0 /= 0; \ +1: \ +r0 = 0; \ +exit; \ +" : + : __imm(bpf_get_prandom_u32) + : __clobber_all); +} + char _license[] SEC("license") = "GPL";
Signature · 1 line
2.53.0-Meta
PATCH v2 5/13 bpf: keep the range across a sign extension that cannot change it
In reply to Vineet Guptacoerce_reg_to_size_sx() decides whether a sign extension is lossless by comparing the bits above the field in smin and smax:
top_smax_value = ((u64)reg_smax(reg) >> num_bits) << num_bits; top_smin_value = ((u64)reg_smin(reg) >> num_bits) << num_bits; if (top_smax_value != top_smin_value) goto out;
Equal high bits do imply the truncation is lossless, but the converse does not hold. Whenever the range straddles zero the high bits necessarily differ -- smin sign-extends to all ones, smax to all zeroes -- even when every value in the range fits the field and (sN)v == v throughout. The second gate, "both of s64_max/s64_min positive or negative", rejects the same shape again for the same reason.
So a register holding an errno-or-zero value, [-4095, 0], comes out of r0 = (s32)r0 as the full [S32_MIN, S32_MAX] even though the instruction is a no-op on it. The no_sext test at the call site does not help: it is an unsigned check, so it only covers non-negative values that fit.
Test the range against the field directly and return early when it fits. Sign extension is then the identity, so nothing needs updating -- which also preserves var_off, where the existing path would have replaced known bits with a coarse tnum_range().
This only tightens: the early return fires exactly where the value is provably unchanged, and the cases the current tests do accept still take the same path and produce the same bounds.
---
v2: new. coerce_reg_to_size_sx() is fixed rather than special-cased, which is what was asked on RFC 5/6; it removes the RFC's call-then-overwrite at the mov site.
kernel/bpf/verifier.c | 22 ++++++++++++++++++++++ 1 file changed, 22 insertions(+)
kernel/bpf/verifier.c +22 -0
@@ -5754,6 +5754,7 @@ static void set_sext64_default_val(struct bpf_reg_state *reg, int size)static void coerce_reg_to_size_sx (struct bpf_reg_state *reg,int size) {s64 init_s64_max, init_s64_min, s64_max, s64_min, u64_cval; +s64 field_smin, field_smax;u64 top_smax_value, top_smin_value;u64 num_bits = size *8 ;
@@ -5773,6 +5774,27 @@ static void coerce_reg_to_size_sx(struct bpf_reg_state *reg, int size)return ; } +if (size ==1 ) { + field_smin =S8_MIN ; + field_smax =S8_MAX ; + }else if (size ==2 ) { + field_smin =S16_MIN ; + field_smax =S16_MAX ; + }else { +/* size == 4 */ + field_smin =S32_MIN ; + field_smax =S32_MAX ; + } + +/* +* The range already fits the field, so (sN)v == v for every value the +* register can hold and the sign extension changes nothing. The tests +* below cannot reach this case once smin is negative: a negative smin +* and a non-negative smax never share their high bits. +*/ +if (reg_smin (reg) >= field_smin &®_smax (reg) <= field_smax) +return ; + top_smax_value = ((u64 )reg_smax (reg) >> num_bits) << num_bits; top_smin_value = ((u64 )reg_smin (reg) >> num_bits) << num_bits;
Signature · 1 line
2.53.0-Meta
[email protected]
AI reviewRe: [PATCH bpf-next v2 05/13] bpf: keep the range across a sign extension that cannot change it
Thank you for your contribution! Sashiko AI review found 2 potential issue(s) to consider:
Thank you for your contribution! Sashiko AI review found 2 potential issue(s) to consider:
New issues:
- [Medium] Incomplete fix for bounds precision loss on zero-straddling sign extensions in the verifier.
Pre-existing issues:
- [High] Out-of-bounds array read in BPF memory cgroup kfuncs due to bypassable enum bounds check. --
commit 971a50869c707d4ac0627b912bd2423344987acc
Author: Vineet Gupta <[email protected]>
bpf: keep the range across a sign extension that cannot change it
This commit improves the verifier's handling of sign extensions in coerce_reg_to_size_sx() by recognizing when a register's bounds already fit within the target field. This prevents unnecessary precision loss when a value range straddles zero, allowing valid programs to pass verification.
Quoted 4 lines
kernel/bpf/verifier.c +0
-0
[ ... ]
Quoted 17 lines
kernel/bpf/verifier.c +13
-0@@ -5773,6 +5774,27 @@ static void coerce_reg_to_size_sx(struct bpf_reg_state *reg, int size)return ; } +if (size ==1 ) { + field_smin =S8_MIN ; + field_smax =S8_MAX ; + }else if (size ==2 ) { + field_smin =S16_MIN ; + field_smax =S16_MAX ; + }else { +/* size == 4 */ + field_smin =S32_MIN ; + field_smax =S32_MAX ; + } + +/*
kernel/bpf/verifier.c static void coerce_reg_to_size_sx(struct bpf_reg_state *reg, int size) · line 5799
Quoted 10 lines
kernel/bpf/verifier.c +8
-0+* The range already fits the field, so (sN)v == v for every value the +* register can hold and the sign extension changes nothing. The tests +* below cannot reach this case once smin is negative: a negative smin +* and a non-negative smax never share their high bits. +*/ +if (reg_smin (reg) >= field_smin &®_smax (reg) <= field_smax) +return ; + top_smax_value = ((u64 )reg_smax (reg) >> num_bits) << num_bits; top_smin_value = ((u64 )reg_smin (reg) >> num_bits) << num_bits;
[Severity: Medium]
Does the 32-bit counterpart function coerce_subreg_to_size_sx() need the same fix?
It seems to retain the same precision loss flaw when handling 32-bit sign extensions on ranges that straddle zero (e.g., [-4095, 0]). Valid BPF programs using 32-bit MOVSX on such ranges will needlessly lose bounds precision and might be incorrectly rejected by the verifier.
[Severity: High]
This is a pre-existing issue, but I noticed a potential out-of-bounds array read in the BPF memory cgroup kfuncs.
Enums are treated as scalars by the verifier and can be negative. The bounds checks in these functions use single-sided signed comparisons, which bypass negative values:
mm/bpf_memcontrol.c:bpf_mem_cgroup_memory_events() {
...
if (unlikely(event >= MEMCG_NR_MEMORY_EVENTS))
return (unsigned long)-1;
return atomic_long_read(&memcg->memory_events[event]);
}If a BPF program passes -1, the check evaluates to false, leading to an out-of-bounds read on memcg->memory_events[-1].
A similar issue exists in bpf_mem_cgroup_vm_events(), where the bounds check delegates to memcg_vm_event_item_valid():
mm/memcontrol.c:memcg_vm_event_item_valid() {
...
if (idx >= NR_VM_EVENT_ITEMS)
return false;
...
}This also performs a single-sided check and fails to catch negative indices. Should these be updated to explicitly check for negative values as well?
Signature · 1 line
Sashiko AI review · https://sashiko.dev/#/patchset/[email protected]?part=5
Re: [PATCH bpf-next v2 05/13] bpf: keep the range across a sign extension that cannot change it
Quoted 56 lines · On 9/10/26 10:08 AM, [email protected] wrote:
Thank you for your contribution! Sashiko AI review found 2 potential issue(s) to consider:
New issues:
- [Medium] Incomplete fix for bounds precision loss on zero-straddling sign extensions in the verifier.Pre-existing issues:
- [High] Out-of-bounds array read in BPF memory cgroup kfuncs due to bypassable enum bounds check. --commit
971a50869c707d4ac0627b912bd2423344987acc
Author: Vineet Gupta <[email protected]>bpf: keep the range across a sign extension that cannot change it
This commit improves the verifier's handling of sign extensions in
coerce_reg_to_size_sx()by recognizing when a register's bounds already fit within the target field. This prevents unnecessary precision loss when a value range straddles zero, allowing valid programs to pass verification.Quoted 4 lines
kernel/bpf/verifier.c +0
-0[ ... ]
Quoted 17 lines
kernel/bpf/verifier.c +13
-0@@ -5773,6 +5774,27 @@ static void coerce_reg_to_size_sx(struct bpf_reg_state *reg, int size)return ; } +if (size ==1 ) { + field_smin =S8_MIN ; + field_smax =S8_MAX ; + }else if (size ==2 ) { + field_smin =S16_MIN ; + field_smax =S16_MAX ; + }else { +/* size == 4 */ + field_smin =S32_MIN ; + field_smax =S32_MAX ; + } + +/* kernel/bpf/verifier.c static void coerce_reg_to_size_sx(struct bpf_reg_state *reg, int size) · line 5799
Quoted 10 lines
kernel/bpf/verifier.c +8
-0+* The range already fits the field, so (sN)v == v for every value the +* register can hold and the sign extension changes nothing. The tests +* below cannot reach this case once smin is negative: a negative smin +* and a non-negative smax never share their high bits. +*/ +if (reg_smin (reg) >= field_smin &®_smax (reg) <= field_smax) +return ; + top_smax_value = ((u64 )reg_smax (reg) >> num_bits) << num_bits; top_smin_value = ((u64 )reg_smin (reg) >> num_bits) << num_bits;[Severity: Medium]
Does the 32-bit counterpart functioncoerce_subreg_to_size_sx()need the same fix?
Quoted 4 lines
It seems to retain the same precision loss flaw when handling 32-bit sign extensions on ranges that straddle zero (e.g., [-4095, 0]). Valid BPF programs using 32-bit MOVSX on such ranges will needlessly lose bounds precision and might be incorrectly rejected by the verifier.
Good catch. Fixed now. It would only need to handle sizes 1 and 2 though.
Quoted 9 lines
[Severity: High]
This is a pre-existing issue, but I noticed a potential out-of-bounds array read in the BPF memory cgroup kfuncs.Enums are treated as scalars by the verifier and can be negative. The bounds checks in these functions use single-sided signed comparisons, which bypass negative values:
mm/bpf_memcontrol.c:bpf_mem_cgroup_memory_events() {
True signature has enum type
__bpf_kfunc unsigned long bpf_mem_cgroup_memory_events(struct mem_cgroup *memcg, enum memcg_memory_event event)
Quoted 9 lines
... if (unlikely(event >= MEMCG_NR_MEMORY_EVENTS)) return (unsigned long)-1; return atomic_long_read(&memcg->memory_events[event]); }If a BPF program passes -1, the check evaluates to false, leading to an out-of-bounds read on memcg->memory_events[-1].
Not an issue. enum doesn't have any negative values and with enum tye in signature above it will treated as unsigned int so -1 will come out as large number not -1.
Quoted 10 lines
A similar issue exists in
bpf_mem_cgroup_vm_events(), where the bounds check delegates tomemcg_vm_event_item_valid():mm/memcontrol.c:memcg_vm_event_item_valid() { ... if (idx >= NR_VM_EVENT_ITEMS) return false; ... }
Quoted 2 lines
This also performs a single-sided check and fails to catch negative indices. Should these be updated to explicitly check for negative values as well?
Same as above since this enum doesn't have negative entries either.
Thx,
-Vineet
[email protected]
AI reviewRe: [PATCH bpf-next v2 05/13] bpf: keep the range across a sign extension that cannot change it
In reply to Vineet GuptaDoes the last sentence accurately describe the change? The early return is placed before the top_s*_value and sign gates, so it intercepts every fitting range, including those the existing gates…
Quoted 22 lines
bpf: keep the range across a sign extension that cannot change it
coerce_reg_to_size_sx()decides whether a sign extension is lossless by comparing the bits above the field in smin and smax:top_smax_value = ((u64)reg_smax(reg) >> num_bits) << num_bits; top_smin_value = ((u64)reg_smin(reg) >> num_bits) << num_bits; if (top_smax_value != top_smin_value) goto out;Equal high bits do imply the truncation is lossless, but the converse does not hold. Whenever the range straddles zero the high bits necessarily differ -- smin sign-extends to all ones, smax to all zeroes -- even when every value in the range fits the field and (sN)v == v throughout. The second gate, "both of s64_max/s64_min positive or negative", rejects the same shape again for the same reason.
So a register holding an errno-or-zero value, [-4095, 0], comes out of r0 = (s32)r0 as the full [
S32_MIN,S32_MAX] even though the instruction is a no-op on it. Theno_sexttest at the call site does not help: it is an unsigned check, so it only covers non-negative values that fit.
Quoted 8 lines
Test the range against the field directly and return early when it fits. Sign extension is then the identity, so nothing needs updating -- which also preserves
var_off, where the existing path would have replaced known bits with a coarsetnum_range().This only tightens: the early return fires exactly where the value is provably unchanged, and the cases the current tests do accept still take the same path and produce the same bounds.
Does the last sentence accurately describe the change? The early return is placed before the top_s*_value and sign gates, so it intercepts every fitting range, including those the existing gates accept.
For example, with 'w0 &= 0x3c; r0 = (s8)r0', the register holds [0, 60] with var_off = (0; 0x3c). The old path passed both gates (equal top bits, both non-negative) and set var_off = tnum_range(0, 60) = TNUM(0, 0x3f), losing the known low bits. The early return now keeps (0; 0x3c).
This is the var_off preservation the message describes two sentences earlier, so "produce the same bounds" seems inaccurate. Would "produce bounds no wider than before" be more precise, given that the accepted cases are where the behaviour actually changes?
Quoted 2 lines
Signed-off-by Vineet Gupta <[email protected]>
This looks like a bug fix for sign extension handling in the verifier. Should this include:
Quoted 24 lines
kernel/bpf/verifier.c +9
-0@@ -5754,6 +5754,7 @@ static void set_sext64_default_val(struct bpf_reg_state *reg, int size)static void coerce_reg_to_size_sx (struct bpf_reg_state *reg,int size) {s64 init_s64_max, init_s64_min, s64_max, s64_min, u64_cval; +s64 field_smin, field_smax;u64 top_smax_value, top_smin_value;u64 num_bits = size *8 ;@@ -5773,6 +5774,27 @@ static void coerce_reg_to_size_sx(struct bpf_reg_state *reg, int size)return ; } +if (size ==1 ) { + field_smin =S8_MIN ; + field_smax =S8_MAX ; + }else if (size ==2 ) { + field_smin =S16_MIN ; + field_smax =S16_MAX ; + }else { +/* size == 4 */
kernel/bpf/verifier.c static void coerce_reg_to_size_sx(struct bpf_reg_state *reg, int size) · line 5794
Quoted 10 lines
kernel/bpf/verifier.c +10
-0+ field_smin =S32_MIN ; + field_smax =S32_MAX ; + } + +/* +* The range already fits the field, so (sN)v == v for every value the +* register can hold and the sign extension changes nothing. The tests +* below cannot reach this case once smin is negative: a negative smin +* and a non-negative smax never share their high bits. +*/
Is the comment's condition accurate? It says the tests below cannot reach this case once smin is negative, but the justification only covers a negative smin together with a non-negative smax.
A fitting range that is entirely negative is reached and accepted by the tests below. For reg_smin = -63, reg_smax = -1 with size == 1:
top_smax_value = ((u64)-1 >> 8) << 8 = 0xffffffffffffff00 top_smin_value = ((u64)-63 >> 8) << 8 = 0xffffffffffffff00
The first gate passes (equal top bits), and the second gate also accepts since (s64_max >= 0) == (s64_min >= 0) holds for both negative. The same is true for entirely non-negative fitting cases like [0, 60] with size == 1.
So the early return intercepts cases the tests below handle, which is the var_off-preserving improvement the commit message describes. Should the condition be "once the range straddles zero" rather than "once smin is negative"?
kernel/bpf/verifier.c static void coerce_reg_to_size_sx(struct bpf_reg_state *reg, int size) · line 5799
Quoted 5 lines
kernel/bpf/verifier.c +3
-0+if (reg_smin (reg) >= field_smin &®_smax (reg) <= field_smax) +return ; + top_smax_value = ((u64 )reg_smax (reg) >> num_bits) << num_bits; top_smin_value = ((u64 )reg_smin (reg) >> num_bits) << num_bits;
---
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/34506184282
Re: [PATCH bpf-next v2 05/13] bpf: keep the range across a sign extension that cannot change it
Quoted 39 lines · On 9/10/26 11:22 PM, [email protected] wrote:
Quoted 22 lines
bpf: keep the range across a sign extension that cannot change it
coerce_reg_to_size_sx()decides whether a sign extension is lossless by comparing the bits above the field in smin and smax:top_smax_value = ((u64)reg_smax(reg) >> num_bits) << num_bits; top_smin_value = ((u64)reg_smin(reg) >> num_bits) << num_bits; if (top_smax_value != top_smin_value) goto out;Equal high bits do imply the truncation is lossless, but the converse does not hold. Whenever the range straddles zero the high bits necessarily differ -- smin sign-extends to all ones, smax to all zeroes -- even when every value in the range fits the field and (sN)v == v throughout. The second gate, "both of s64_max/s64_min positive or negative", rejects the same shape again for the same reason.
So a register holding an errno-or-zero value, [-4095, 0], comes out of r0 = (s32)r0 as the full [
S32_MIN,S32_MAX] even though the instruction is a no-op on it. Theno_sexttest at the call site does not help: it is an unsigned check, so it only covers non-negative values that fit.Quoted 8 lines
Test the range against the field directly and return early when it fits. Sign extension is then the identity, so nothing needs updating -- which also preserves
var_off, where the existing path would have replaced known bits with a coarsetnum_range().This only tightens: the early return fires exactly where the value is provably unchanged, and the cases the current tests do accept still take the same path and produce the same bounds.
Does the last sentence accurately describe the change? The early return is placed before the top_s*_value and sign gates, so it intercepts every fitting range, including those the existing gates accept.
For example, with 'w0 &=
0x3c; r0 = (s8)r0', the register holds [0, 60] withvar_off= (0;0x3c). The old path passed both gates (equal top bits, both non-negative) and setvar_off=tnum_range(0, 60)=TNUM(0, 0x3f), losing the known low bits. The early return now keeps (0;0x3c).
Quoted 4 lines
This is the
var_offpreservation the message describes two sentences earlier, so "produce the same bounds" seems inaccurate. Would "produce bounds no wider than before" be more precise, given that the accepted cases are where the behaviour actually changes?
Yes this is the right phrasing.
Quoted 5 lines
Quoted 1 line
Signed-off-by Vineet Gupta <[email protected]>This looks like a bug fix for sign extension handling in the verifier. Should this include:
Fixes 1f9a1ea821ff ("bpf: Support new sign-extension load insns")
This is a limitation not really a regression - I doubt if this would be backported. but up to the maintainers.
Quoted 44 lines
Quoted 24 lines
kernel/bpf/verifier.c +9
-0@@ -5754,6 +5754,7 @@ static void set_sext64_default_val(struct bpf_reg_state *reg, int size)static void coerce_reg_to_size_sx (struct bpf_reg_state *reg,int size) {s64 init_s64_max, init_s64_min, s64_max, s64_min, u64_cval; +s64 field_smin, field_smax;u64 top_smax_value, top_smin_value;u64 num_bits = size *8 ;@@ -5773,6 +5774,27 @@ static void coerce_reg_to_size_sx(struct bpf_reg_state *reg, int size)return ; } +if (size ==1 ) { + field_smin =S8_MIN ; + field_smax =S8_MAX ; + }else if (size ==2 ) { + field_smin =S16_MIN ; + field_smax =S16_MAX ; + }else { +/* size == 4 */ kernel/bpf/verifier.c static void coerce_reg_to_size_sx(struct bpf_reg_state *reg, int size) · line 5794
Quoted 10 lines
kernel/bpf/verifier.c +10
-0+ field_smin =S32_MIN ; + field_smax =S32_MAX ; + } + +/* +* The range already fits the field, so (sN)v == v for every value the +* register can hold and the sign extension changes nothing. The tests +* below cannot reach this case once smin is negative: a negative smin +* and a non-negative smax never share their high bits. +*/ Is the comment's condition accurate? It says the tests below cannot reach this case once smin is negative, but the justification only covers a negative smin together with a non-negative smax.
A fitting range that is entirely negative is reached and accepted by the tests below. For
reg_smin= -63,reg_smax= -1 with size == 1:top_smax_value = ((u64)-1 >> 8) << 8 = 0xffffffffffffff00 top_smin_value = ((u64)-63 >> 8) << 8 = 0xffffffffffffff00
Quoted 8 lines
The first gate passes (equal top bits), and the second gate also accepts since (
s64_max>= 0) == (s64_min>= 0) holds for both negative. The same is true for entirely non-negative fitting cases like [0, 60] with size == 1.So the early return intercepts cases the tests below handle, which is the var_off-preserving improvement the commit message describes. Should the condition be "once the range straddles zero" rather than "once smin is negative"?
Yes this needs fixing.
Thx,
-Vineet
Quoted 11 lines
kernel/bpf/verifier.c static void coerce_reg_to_size_sx(struct bpf_reg_state *reg, int size) · line 5799
Quoted 5 lines
kernel/bpf/verifier.c +3
-0+if (reg_smin (reg) >= field_smin &®_smax (reg) <= field_smax) +return ; + top_smax_value = ((u64 )reg_smax (reg) >> num_bits) << num_bits; top_smin_value = ((u64 )reg_smin (reg) >> num_bits) << num_bits;---
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.mdCI run summary: https://github.com/kernel-patches/bpf/actions/runs/34506184282
Re: [PATCH bpf-next v2 05/13] bpf: keep the range across a sign extension that cannot change it
In reply to Vineet GuptaQuoted 65 lines · Vineet Gupta
coerce_reg_to_size_sx()decides whether a sign extension is lossless by comparing the bits above the field in smin and smax:top_smax_value = ((u64)reg_smax(reg) >> num_bits) << num_bits; top_smin_value = ((u64)reg_smin(reg) >> num_bits) << num_bits; if (top_smax_value != top_smin_value) goto out;Equal high bits do imply the truncation is lossless, but the converse does not hold. Whenever the range straddles zero the high bits necessarily differ -- smin sign-extends to all ones, smax to all zeroes -- even when every value in the range fits the field and (sN)v == v throughout. The second gate, "both of s64_max/s64_min positive or negative", rejects the same shape again for the same reason.
So a register holding an errno-or-zero value, [-4095, 0], comes out of r0 = (s32)r0 as the full [
S32_MIN,S32_MAX] even though the instruction is a no-op on it. Theno_sexttest at the call site does not help: it is an unsigned check, so it only covers non-negative values that fit.Test the range against the field directly and return early when it fits. Sign extension is then the identity, so nothing needs updating -- which also preserves
var_off, where the existing path would have replaced known bits with a coarsetnum_range().This only tightens: the early return fires exactly where the value is provably unchanged, and the cases the current tests do accept still take the same path and produce the same bounds.
Signed-off-by Vineet Gupta <[email protected]>---
v2: new.coerce_reg_to_size_sx()is fixed rather than special-cased, which is what was asked on RFC 5/6; it removes the RFC's call-then-overwrite at the mov site.kernel/bpf/verifier.c | 22 ++++++++++++++++++++++ 1 file changed, 22 insertions(+)kernel/bpf/verifier.c +12
-0@@ -5754,6 +5754,7 @@ static void set_sext64_default_val(struct bpf_reg_state *reg, int size)static void coerce_reg_to_size_sx (struct bpf_reg_state *reg,int size) {s64 init_s64_max, init_s64_min, s64_max, s64_min, u64_cval; +s64 field_smin, field_smax;u64 top_smax_value, top_smin_value;u64 num_bits = size *8 ;@@ -5773,6 +5774,27 @@ static void coerce_reg_to_size_sx(struct bpf_reg_state *reg, int size)return ; } +if (size ==1 ) { + field_smin =S8_MIN ; + field_smax =S8_MAX ; + }else if (size ==2 ) { + field_smin =S16_MIN ; + field_smax =S16_MAX ; + }else { +/* size == 4 */ + field_smin =S32_MIN ; + field_smax =S32_MAX ; + }
kernel/bpf/verifier.c static void coerce_reg_to_size_sx(struct bpf_reg_state *reg, int size) · line 5797
Quoted 10 lines
kernel/bpf/verifier.c +10
-0+ +/* +* The range already fits the field, so (sN)v == v for every value the +* register can hold and the sign extension changes nothing. The tests +* below cannot reach this case once smin is negative: a negative smin +* and a non-negative smax never share their high bits. +*/ +if (reg_smin (reg) >= field_smin &®_smax (reg) <= field_smax) +return ; +
This patch can be a patch 1, since it looks unrelated to the rest? Would be good to test it individually. veristat run before/after.
Re: [PATCH bpf-next v2 05/13] bpf: keep the range across a sign extension that cannot change it
Quoted 70 lines · Alexei Starovoitov
Quoted 69 lines · Vineet Gupta
coerce_reg_to_size_sx()decides whether a sign extension is lossless by comparing the bits above the field in smin and smax:top_smax_value = ((u64)reg_smax(reg) >> num_bits) << num_bits; top_smin_value = ((u64)reg_smin(reg) >> num_bits) << num_bits; if (top_smax_value != top_smin_value) goto out;Equal high bits do imply the truncation is lossless, but the converse does not hold. Whenever the range straddles zero the high bits necessarily differ -- smin sign-extends to all ones, smax to all zeroes -- even when every value in the range fits the field and (sN)v == v throughout. The second gate, "both of s64_max/s64_min positive or negative", rejects the same shape again for the same reason.
So a register holding an errno-or-zero value, [-4095, 0], comes out of r0 = (s32)r0 as the full [
S32_MIN,S32_MAX] even though the instruction is a no-op on it. Theno_sexttest at the call site does not help: it is an unsigned check, so it only covers non-negative values that fit.Test the range against the field directly and return early when it fits. Sign extension is then the identity, so nothing needs updating -- which also preserves
var_off, where the existing path would have replaced known bits with a coarsetnum_range().This only tightens: the early return fires exactly where the value is provably unchanged, and the cases the current tests do accept still take the same path and produce the same bounds.
Signed-off-by Vineet Gupta <[email protected]>---
v2: new.coerce_reg_to_size_sx()is fixed rather than special-cased, which is what was asked on RFC 5/6; it removes the RFC's call-then-overwrite at the mov site.kernel/bpf/verifier.c | 22 ++++++++++++++++++++++ 1 file changed, 22 insertions(+)kernel/bpf/verifier.c +16
-0@@ -5754,6 +5754,7 @@ static void set_sext64_default_val(struct bpf_reg_state *reg, int size)static void coerce_reg_to_size_sx (struct bpf_reg_state *reg,int size) {s64 init_s64_max, init_s64_min, s64_max, s64_min, u64_cval; +s64 field_smin, field_smax;u64 top_smax_value, top_smin_value;u64 num_bits = size *8 ;@@ -5773,6 +5774,27 @@ static void coerce_reg_to_size_sx(struct bpf_reg_state *reg, int size)return ; } +if (size ==1 ) { + field_smin =S8_MIN ; + field_smax =S8_MAX ; + }else if (size ==2 ) { + field_smin =S16_MIN ; + field_smax =S16_MAX ; + }else { +/* size == 4 */ + field_smin =S32_MIN ; + field_smax =S32_MAX ; + } + +/* +* The range already fits the field, so (sN)v == v for every value the +* register can hold and the sign extension changes nothing. The tests
Quoted 8 lines
kernel/bpf/verifier.c static void coerce_reg_to_size_sx(struct bpf_reg_state *reg, int size) · line 5797
Quoted 6 lines
kernel/bpf/verifier.c +6
-0+* below cannot reach this case once smin is negative: a negative smin +* and a non-negative smax never share their high bits. +*/ +if (reg_smin (reg) >= field_smin &®_smax (reg) <= field_smax) +return ; +This patch can be a patch 1, since it looks unrelated to the rest? Would be good to test it individually. veristat run before/after.
OK, and the corresponding patch moves too.
Thx,
-Vineet
PATCH v2 6/13 selftests/bpf: cover sign extensions that cannot change the range
In reply to Vineet GuptaBoth programs build a range that straddles zero but still fits the target field, so the sign extension is a no-op: [-4095, 0] for (s32) and [-63, 0] for (s8). The guard that follows can only be resolved statically if the range survives, and it protects a div by zero, so a widened range is a verification failure rather than a silently weaker test.
These sit in verifier_movsx.c rather than with the linked-scalar tests:
they exercise the range a sign-extending mov produces, which has nothing to do with the ->id machinery, and the file already gates on the cpuv4 support they need.
---
v2: new, with 5/13.
.../selftests/bpf/progs/verifier_movsx.c | 51 +++++++++++++++++++ 1 file changed, 51 insertions(+)
tools/testing/selftests/bpf/progs/verifier_movsx.c +51 -0
@@ -202,6 +202,57 @@ l0_%=: \ : __clobber_all); } +/* +* A range that already fits the field is unchanged by the sign extension. +* Both of these straddle zero, so the high bits of smin and smax differ and +* the top_s*_value test alone would fall back to the full field range. +*/ +SEC("socket") +__description("MOV64SX, S32, negative range is preserved") +__success __success_unpriv __retval(0) +__naked void mov64sx_s32_negative_range(void) +{ + asmvolatile (" \ +call %[bpf_get_prandom_u32]; \ +w0 &= 0xfff; \ +r0 -= 0xfff; \ +/* r0 is [-4095, 0], already a valid s32 */ \ +r0 = (s32)r0; \ +if r0 s< -0xfff goto l0_%=; \ +r0 = 0; \ +exit; \ +l0_%=: \ +/* unreachable unless the range was widened */ \ +r0 /= 0; \ +exit; \ +" : + : __imm(bpf_get_prandom_u32) + : __clobber_all); +} + +SEC("socket") +__description("MOV64SX, S8, negative range is preserved") +__success __success_unpriv __retval(0) +__naked void mov64sx_s8_negative_range(void) +{ + asmvolatile (" \ +call %[bpf_get_prandom_u32]; \ +w0 &= 0x3f; \ +r0 -= 0x3f; \ +/* r0 is [-63, 0], already a valid s8 */ \ +r0 = (s8)r0; \ +if r0 s< -0x3f goto l0_%=; \ +r0 = 0; \ +exit; \ +l0_%=: \ +/* unreachable unless the range was widened */ \ +r0 /= 0; \ +exit; \ +" : + : __imm(bpf_get_prandom_u32) + : __clobber_all); +} + SEC("socket") __description("MOV64SX, S16, R10 Sign Extension") __failure __msg("R1 type=scalar expected=fp, pkt, pkt_meta, map_key, map_value, mem, ringbuf_mem, buf, trusted_ptr_")
Signature · 1 line
2.53.0-Meta
PATCH v2 7/13 bpf: track low-32 scalar equality across sign-extending movs
In reply to Vineet GuptaThe zero-extending mov records that dst shares src's low 32 bits. A 32-bit sign extension shares them too -- it keeps the low half and fills the high half from bit 31 -- so the same link applies, with a different rule for rebuilding the high bits:
r6 = ... /* full 64-bit unknown */ r7 = (s32)r6 /* 32-bit sign-extending mov */ if w6 == -1 goto ... /* taken: r6's low 32 bits are all ones */ ... /* r7 is -1, not deduced today */
Add SUBREG_SEXT alongside SUBREG_ZEXT, and sext_32_to_64() alongside zext_32_to_64() to drive the reconstruction. Both work from the base's 32-bit range, which is what a 32-bit compare narrows. coerce_reg_to_size_sx() cannot serve here: it reads smin/smax, which straddle after such a compare and collapse to the full field range.
tnum_sext() is the counterpart to tnum_cast(). Unlike a tnum_range() over the new bounds it keeps the known low bits.
The enum has room for the third value, so bpf_reg_state stays 80 bytes.
Unlike the zero-extending arm, a self-mov can form a link here, but only when src is already linked: r0 = (s32)r0 is how a sign-extended int return lands. On an unlinked register there is nothing to link to, and minting an id would leave the register describing itself.
---
v2: was RFC 5/6.
- no forward declaration (Eduard)
- src renamed known_reg (Eduard)
- sext_32_to_64() and tnum_sext() rather than reusing coerce_reg_to_size_sx(); the sync path needs the base's 32-bit range, see the cover letter
- tnum_sext() keeps the known low bits a tnum_range() would drop (Eduard)
- a self-mov links only when src already has an id, narrower than the RFC
include/linux/bpf_verifier.h | 1 + include/linux/tnum.h | 3 +++ kernel/bpf/log.c | 2 ++ kernel/bpf/tnum.c | 15 ++++++++++++ kernel/bpf/verifier.c | 47 +++++++++++++++++++++++++++++++++--- 5 files changed, 65 insertions(+), 3 deletions(-)
include/linux/bpf_verifier.h +1 -0
@@ -53,6 +53,7 @@ enum bpf_add_const {enum bpf_subreg {SUBREG_NONE =0 ,SUBREG_ZEXT ,/* high bits are zero (32-bit zero-extending mov) */ +SUBREG_SEXT ,/* high bits repeat bit 31 (32-bit sign-extending mov) */ };struct bpf_reg_state {
include/linux/tnum.h +3 -0
@@ -63,6 +63,9 @@ struct tnum tnum_union(struct tnum t1, struct tnum t2);/* Return @a with all but the lowest @size bytes cleared */ struct tnum tnum_cast (struct tnum a,u8 size); +/* Return the lowest @size bytes of @a sign-extended to 64 bits */ +struct tnum tnum_sext (struct tnum a,u8 size); +/* Swap the bytes of a tnum */ struct tnum tnum_bswap16 (struct tnum a);struct tnum tnum_bswap32 (struct tnum a);
kernel/bpf/log.c +2 -0
@@ -656,6 +656,8 @@ static void print_reg_state(struct bpf_verifier_env *env,verbose (env,"%+d" , reg->delta);if (reg->subreg ==SUBREG_ZEXT )verbose (env,".lo32" ); +else if (reg->subreg ==SUBREG_SEXT ) +verbose (env,".lo32sx" );if (reg->parent_id)verbose_a ("parent_id=%d" , reg->parent_id);if (type_is_non_owning_ref (reg->type))
kernel/bpf/tnum.c +15 -0
@@ -200,6 +200,21 @@ struct tnum tnum_cast(struct tnum a, u8 size)return a; } +struct tnum tnum_sext (struct tnum a,u8 size) +{ +u8 shift =64 - size *8 ; + +/* +* Shifting the field up to the top and back down arithmetically +* replicates its sign bit through the high half. Applying that to the +* mask as well carries over whether the sign was known: an unknown +* sign bit leaves every high bit unknown. +*/ + a =tnum_cast (a, size); +return TNUM ((s64)(a.value << shift) >> shift, + (s64)(a.mask << shift) >> shift); +} +bool tnum_is_aligned (struct tnum a,u64 size) {if (!size)
kernel/bpf/verifier.c +44 -3
75 lines not on this page · raw message
Signature · 1 line
2.53.0-Meta
[email protected]
AI reviewRe: [PATCH bpf-next v2 07/13] bpf: track low-32 scalar equality across sign-extending movs
Can widening this guard drop an existing ADD_CONST link on the source register? With 'no_sext || subreg_link', assign_scalar_id_before_mov() now also runs on src_reg when !no_sext, and that helper…
Quoted 4 lines
kernel/bpf/verifier.c +0
-0
[ ... ]
Quoted 8 lines
kernel/bpf/verifier.c +4
-0@@ -16248,12 +16258,23 @@ static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn)return -EACCES ; }else if (src_reg->type ==SCALAR_VALUE ) {bool no_sext; +/* +* A 32-bit sign extension keeps the low 32 +* bits, so record a low-32 link as the +* zero-extending mov does. A self-mov
kernel/bpf/verifier.c static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn) · line 16273
Quoted 10 lines
kernel/bpf/verifier.c +6
-1+* qualifies only if src is already linked. +*/ +bool subreg_link = (insn->off >>3 ) ==4 && + (src_reg != dst_reg || + src_reg->id); no_sext =reg_umax (src_reg) < (1ULL << (insn->off -1 )); -if (no_sext) +if (no_sext || subreg_link)assign_scalar_id_before_mov (env, src_reg);
^^^^
Can widening this guard drop an existing ADD_CONST link on the source register? With 'no_sext || subreg_link', assign_scalar_id_before_mov() now also runs on src_reg when !no_sext, and that helper discards the source's delta tracking:
kernel/bpf/verifier.c:assign_scalar_id_before_mov() {
...
if (src_reg->add_const)
clear_scalar_id(src_reg);
if (!src_reg->id && !tnum_is_const(src_reg->var_off))
src_reg->id = ++env->id_gen;
...
}clear_scalar_id() zeroes id, delta, add_const and subreg, and the following statement then mints a brand-new id, so src_reg is unlinked from the register set it was tracking. Before this commit the !no_sext arm left src_reg untouched.
For a BPF_ALU64 | BPF_MOV | BPF_X with insn->off == 32:
r1 = r2 /* r1, r2 share id N */ r1 += 8 /* r1->add_const = ADD_CONST_64, r1->delta = 8 */ r3 = (s32)r1 /* r1 is wide -> !no_sext, subreg_link true */ if r2 < 100 goto out /* sync_linked_regs() no longer reaches r1 */ ... use r1 ...
At the mov, r1 loses its ADD_CONST_64 / delta = 8 link and gets a fresh id, so the following 'if r2 < 100' compare no longer refines r1 to [8, 107]. Is that the intent? This is the compiler idiom described in the comment above adjust_reg_min_max_vals()'s delta handling.
The clear also does not look necessary for the new link: since !no_sext, the SUBREG_SEXT link is established through the freshly minted id.
Would excluding add_const sources be enough, something like:
bool subreg_link = (insn->off >> 3) == 4 && !src_reg->add_const && (src_reg != dst_reg || src_reg->id);
The zero-extending arm added earlier in the series uses the same guard shape, so a fix likely wants to cover both. Looking forward through 2c5433cf9fbb..1d3c4a0831be, the later commits extend the same mechanism to narrowing stack fills and spills and reuse the identical guard, so none of them change this.
kernel/bpf/verifier.c static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn) · line 16276
Quoted 4 lines
kernel/bpf/verifier.c +2
-1*dst_reg = *src_reg; -if (!no_sext) +if (!no_sext && subreg_link && src_reg->id) + dst_reg->subreg =SUBREG_SEXT ;
^^^^
On a related note, for 'r0 = (s32)r0' where r0 carries add_const, subreg_link is evaluated before the clear and sees the old src_reg->id as non-zero, so it is true. assign_scalar_id_before_mov() then clears and re-mints the id, and SUBREG_SEXT is applied to a register that is the sole holder of that id.
The changelog says:
Quoted 4 lines
Unlike the zero-extending arm, a self-mov can form a link here, but only when src is already linked: r0 = (s32)r0 is how a sign-extended int return lands. On an unlinked register there is nothing to link to, and minting an id would leave the register describing itself.
bpf_clear_singular_ids() drops singleton ids before state comparison, so this does not look unsound, but does it match the rationale above?
kernel/bpf/verifier.c static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn) · line 16280
Quoted 4 lines
kernel/bpf/verifier.c +1
-0+else if (!no_sext)clear_scalar_id (dst_reg);coerce_reg_to_size_sx (dst_reg, insn->off >>3 ); }else {
[ ... ]
---
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/34506184282
Re: [PATCH bpf-next v2 07/13] bpf: track low-32 scalar equality across sign-extending movs
Quoted 52 lines · On 9/10/26 11:22 PM, [email protected] wrote:
Quoted 8 lines
kernel/bpf/verifier.c +4
-0@@ -16248,12 +16258,23 @@ static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn)return -EACCES ; }else if (src_reg->type ==SCALAR_VALUE ) {bool no_sext; +/* +* A 32-bit sign extension keeps the low 32 +* bits, so record a low-32 link as the +* zero-extending mov does. A self-mov kernel/bpf/verifier.c static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn) · line 16273
Quoted 10 lines
kernel/bpf/verifier.c +6
-1+* qualifies only if src is already linked. +*/ +bool subreg_link = (insn->off >>3 ) ==4 && + (src_reg != dst_reg || + src_reg->id); no_sext =reg_umax (src_reg) < (1ULL << (insn->off -1 )); -if (no_sext) +if (no_sext || subreg_link)assign_scalar_id_before_mov (env, src_reg);^^^^Can widening this guard drop an existing
ADD_CONSTlink on the source register? With 'no_sext||subreg_link',assign_scalar_id_before_mov()now also runs onsrc_regwhen !no_sext, and that helper discards the source's delta tracking:kernel/bpf/verifier.c:assign_scalar_id_before_mov() { ... if (src_reg->add_const) clear_scalar_id(src_reg); if (!src_reg->id && !tnum_is_const(src_reg->var_off)) src_reg->id = ++env->id_gen; ... }
clear_scalar_id()zeroes id, delta,add_constand subreg, and the following statement then mints a brand-new id, sosrc_regis unlinked from the register set it was tracking. Before this commit the !no_sext arm leftsrc_reguntouched.For a
BPF_ALU64|BPF_MOV|BPF_Xwithinsn->off== 32:r1 = r2 /* r1, r2 share id N */ r1 += 8 /* r1->add_const = ADD_CONST_64, r1->delta = 8 */ r3 = (s32)r1 /* r1 is wide -> !no_sext, subreg_link true */ if r2 < 100 goto out /* sync_linked_regs() no longer reaches r1 */ ... use r1 ...At the mov, r1 loses its
ADD_CONST_64/ delta = 8 link and gets a fresh id, so the following 'if r2 < 100' compare no longer refines r1 to [8, 107]. Is that the intent? This is the compiler idiom described in the comment above adjust_reg_min_max_vals()'s delta handling.
Quoted 7 lines
The clear also does not look necessary for the new link: since !no_sext, the
SUBREG_SEXTlink is established through the freshly minted id.Would excluding
add_constsources be enough, something like:bool subreg_link = (insn->off >> 3) == 4 && !src_reg->add_const && (src_reg != dst_reg || src_reg->id);
Indeed it needs to fixed with the additional !add_const check.
Quoted 18 lines
The zero-extending arm added earlier in the series uses the same guard shape, so a fix likely wants to cover both. Looking forward through
2c5433cf9fbb..1d3c4a0831be, the later commits extend the same mechanism to narrowing stack fills and spills and reuse the identical guard, so none of them change this.kernel/bpf/verifier.c static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn) · line 16276
Quoted 4 lines
kernel/bpf/verifier.c +2
-1*dst_reg = *src_reg; -if (!no_sext) +if (!no_sext && subreg_link && src_reg->id) + dst_reg->subreg =SUBREG_SEXT ;^^^^On a related note, for 'r0 = (s32)r0' where r0 carries
add_const,subreg_linkis evaluated before the clear and sees the oldsrc_reg->idas non-zero, so it is true.assign_scalar_id_before_mov()then clears and re-mints the id, andSUBREG_SEXTis applied to a register that is the sole holder of that id.
Quoted 8 lines
The changelog says:
Quoted 4 lines
Unlike the zero-extending arm, a self-mov can form a link here, but only when src is already linked: r0 = (s32)r0 is how a sign-extended int return lands. On an unlinked register there is nothing to link to, and minting an id would leave the register describing itself.
bpf_clear_singular_ids()drops singleton ids before state comparison, so this does not look unsound, but does it match the rationale above?
yes the changelog needs to be fixed.
Thx,
-Vineet
Quoted 12 lines
kernel/bpf/verifier.c static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn) · line 16280
Quoted 4 lines
kernel/bpf/verifier.c +1
-0+else if (!no_sext)clear_scalar_id (dst_reg);coerce_reg_to_size_sx (dst_reg, insn->off >>3 ); }else {[ ... ]
---
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.mdCI run summary: https://github.com/kernel-patches/bpf/actions/runs/34506184282
Re: [PATCH bpf-next v2 07/13] bpf: track low-32 scalar equality across sign-extending movs
In reply to Vineet GuptaQuoted 49 lines · Vineet Gupta
The zero-extending mov records that dst shares src's low 32 bits. A 32-bit sign extension shares them too -- it keeps the low half and fills the high half from bit 31 -- so the same link applies, with a different rule for rebuilding the high bits:
r6 = ... /* full 64-bit unknown */ r7 = (s32)r6 /* 32-bit sign-extending mov */ if w6 == -1 goto ... /* taken: r6's low 32 bits are all ones */ ... /* r7 is -1, not deduced today */Add
SUBREG_SEXTalongsideSUBREG_ZEXT, andsext_32_to_64()alongsidezext_32_to_64()to drive the reconstruction. Both work from the base's 32-bit range, which is what a 32-bit compare narrows.coerce_reg_to_size_sx()cannot serve here: it reads smin/smax, which straddle after such a compare and collapse to the full field range.
tnum_sext()is the counterpart totnum_cast(). Unlike atnum_range()over the new bounds it keeps the known low bits.The enum has room for the third value, so
bpf_reg_statestays 80 bytes.Unlike the zero-extending arm, a self-mov can form a link here, but only when src is already linked: r0 = (s32)r0 is how a sign-extended int return lands. On an unlinked register there is nothing to link to, and minting an id would leave the register describing itself.
Signed-off-by Vineet Gupta <[email protected]>---
v2: was RFC 5/6.
- no forward declaration (Eduard)
- src renamedknown_reg(Eduard)
-sext_32_to_64()andtnum_sext()rather than reusingcoerce_reg_to_size_sx(); the sync path needs the base's 32-bit range, see the cover letter
-tnum_sext()keeps the known low bits atnum_range()would drop (Eduard)
- a self-mov links only when src already has an id, narrower than the RFCinclude/linux/bpf_verifier.h | 1 + include/linux/tnum.h | 3 +++ kernel/bpf/log.c | 2 ++ kernel/bpf/tnum.c | 15 ++++++++++++ kernel/bpf/verifier.c | 47 +++++++++++++++++++++++++++++++++--- 5 files changed, 65 insertions(+), 3 deletions(-)include/linux/bpf_verifier.h +0
-0
include/linux/bpf_verifier.h enum bpf_add_const { · line 56
Quoted 4 lines
include/linux/bpf_verifier.h +1
-0@@ -53,6 +53,7 @@ enum bpf_add_const {enum bpf_subreg {SUBREG_NONE =0 ,SUBREG_ZEXT ,/* high bits are zero (32-bit zero-extending mov) */ +SUBREG_SEXT ,/* high bits repeat bit 31 (32-bit sign-extending mov) */
If my earlier suggestion to model SUBREG_ZEXT as add_const32 with delta == 0 works, then sign extension could be:
enum bpf_add_const {
ADD_CONST_NONE = 0,
ADD_CONST_32, /* delta was added with a 32-bit ALU op */ /* works as ZERO_EXTEND when delta == 0 */
ADD_CONST_64, /* ... with a 64-bit ALU op */
SIGN_EXTEND_32, /* delta has to be == 0 */
};and if we really want to we can track movsx 8 and 16 too. Which might be an overkill.
Re: [PATCH bpf-next v2 07/13] bpf: track low-32 scalar equality across sign-extending movs
Quoted 57 lines · Alexei Starovoitov
Quoted 49 lines · Vineet Gupta
The zero-extending mov records that dst shares src's low 32 bits. A 32-bit sign extension shares them too -- it keeps the low half and fills the high half from bit 31 -- so the same link applies, with a different rule for rebuilding the high bits:
r6 = ... /* full 64-bit unknown */ r7 = (s32)r6 /* 32-bit sign-extending mov */ if w6 == -1 goto ... /* taken: r6's low 32 bits are all ones */ ... /* r7 is -1, not deduced today */Add
SUBREG_SEXTalongsideSUBREG_ZEXT, andsext_32_to_64()alongsidezext_32_to_64()to drive the reconstruction. Both work from the base's 32-bit range, which is what a 32-bit compare narrows.coerce_reg_to_size_sx()cannot serve here: it reads smin/smax, which straddle after such a compare and collapse to the full field range.
tnum_sext()is the counterpart totnum_cast(). Unlike atnum_range()over the new bounds it keeps the known low bits.The enum has room for the third value, so
bpf_reg_statestays 80 bytes.Unlike the zero-extending arm, a self-mov can form a link here, but only when src is already linked: r0 = (s32)r0 is how a sign-extended int return lands. On an unlinked register there is nothing to link to, and minting an id would leave the register describing itself.
Signed-off-by Vineet Gupta <[email protected]>---
v2: was RFC 5/6.
- no forward declaration (Eduard)
- src renamedknown_reg(Eduard)
-sext_32_to_64()andtnum_sext()rather than reusingcoerce_reg_to_size_sx(); the sync path needs the base's 32-bit range, see the cover letter
-tnum_sext()keeps the known low bits atnum_range()would drop (Eduard)
- a self-mov links only when src already has an id, narrower than the RFCinclude/linux/bpf_verifier.h | 1 + include/linux/tnum.h | 3 +++ kernel/bpf/log.c | 2 ++ kernel/bpf/tnum.c | 15 ++++++++++++ kernel/bpf/verifier.c | 47 +++++++++++++++++++++++++++++++++--- 5 files changed, 65 insertions(+), 3 deletions(-)include/linux/bpf_verifier.h +0
-0include/linux/bpf_verifier.h enum bpf_add_const { · line 56
Quoted 4 lines
include/linux/bpf_verifier.h +1
-0@@ -53,6 +53,7 @@ enum bpf_add_const {enum bpf_subreg {SUBREG_NONE =0 ,SUBREG_ZEXT ,/* high bits are zero (32-bit zero-extending mov) */ +SUBREG_SEXT ,/* high bits repeat bit 31 (32-bit sign-extending mov) */ If my earlier suggestion to model
SUBREG_ZEXTasadd_const32with delta == 0 works, then sign extension could be:
Quoted 6 lines
enum bpf_add_const {
ADD_CONST_NONE = 0,
ADD_CONST_32, /* delta was added with a 32-bit ALU op */ /* works as ZERO_EXTEND when delta == 0 */
ADD_CONST_64, /* ... with a 64-bit ALU op */
SIGN_EXTEND_32, /* delta has to be == 0 */
};If we were to go that route sure, but no point if we are not doing that.
Also keeping them together makes add_const and sext mutually exclusive. Today they are but what if in future we were to implement the following.
w7 = w6 /* r7 gets SUBREG_ZEXT */
w7 += 4 /* r7 also gets ADD_CONST_32, delta 4 */
Quoted 2 lines
and if we really want to we can track movsx 8 and 16 too. Which might be an overkill.
Indeed.
Eduard and I discussed this in the off line review before RFC. gcc currently doesn't seem to generate these a lot so maybe leave this for future.
Thx,
-Vineet
PATCH v2 8/13 selftests/bpf: cover the low-32 link for sign-extending movs
In reply to Vineet GuptaFive programs, mirroring the zero-extending set:
- sext_mov_wide_src: narrowing the source reaches the destination, and the value that arrives is sign-extended rather than zero-extended
- sext_self_mov_keeps_link: r0 = (s32)r0 on an already-linked register stays in its set, the shape a sign-extended int return takes
- sext_self_mov_no_link: the same mov on an unlinked register mints no id
- sext_no_sync_when_base_has_delta: a delta on the base stops propagation
- sext_no_sync_from_subreg_base: narrowing the link does not run backwards into the rest of the set
- sext_kinds_reach_different_values: the same low half reaches -1 through a sign extension and 0xffffffff through a zero extension
Each guards a div by zero that is only unreachable if the propagation happened, so losing the link is a verification failure rather than a test that quietly stops checking anything.
The sign-extending mov is cpuv4, so the block needs a feature gate. CAN_USE_MOVSX follows CAN_USE_GOTOL: the arch list, then clang 18 or __BPF_FEATURE_MOVSX, so bpf-gcc gets the coverage too.
---
v2: was RFC 6/6.
- fixed the backwards guard sashiko reported
- CAN_USE_MOVSX so bpf-gcc builds these too
- renamed as in 4/13
tools/testing/selftests/bpf/progs/bpf_misc.h | 8 + .../bpf/progs/verifier_linked_scalars.c | 165 ++++++++++++++++++ 2 files changed, 173 insertions(+)
tools/testing/selftests/bpf/progs/bpf_misc.h +8 -0
@@ -269,6 +269,14 @@#define CAN_USE_BPF_ST #endif +#if (defined(__TARGET_ARCH_arm64) || defined(__TARGET_ARCH_x86) || \ + (defined(__TARGET_ARCH_riscv) && __riscv_xlen ==64 ) || \ + defined(__TARGET_ARCH_arm) || defined(__TARGET_ARCH_s390) || \ + defined(__TARGET_ARCH_loongarch)) && \ + (__clang_major__ >=18 || defined(__BPF_FEATURE_MOVSX)) +#define CAN_USE_MOVSX +#endif + #if __clang_major__ >= 18 && defined(ENABLE_ATOMICS_TESTS) && \ (defined(__TARGET_ARCH_arm64) || \ defined(__TARGET_ARCH_x86) || \
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +165 -0
169 lines not on this page · raw message
Signature · 1 line
2.53.0-Meta
[email protected]
AI reviewRe: [PATCH bpf-next v2 08/13] selftests/bpf: cover the low-32 link for sign-extending movs
This isn't a bug, but should the count read "six programs", and could the closing sentence be scoped to the two __success programs, since sext_self_mov_no_link has no div and the __failure ones…
Quoted 15 lines
selftests/bpf: cover the low-32 link for sign-extending movs
Five programs, mirroring the zero-extending set:
-
sext_mov_wide_src: narrowing the source reaches the destination, and the value that arrives is sign-extended rather than zero-extended
-sext_self_mov_keeps_link: r0 = (s32)r0 on an already-linked register stays in its set, the shape a sign-extended int return takes
-sext_self_mov_no_link: the same mov on an unlinked register mints no id
-sext_no_sync_when_base_has_delta: a delta on the base stops propagation
-sext_no_sync_from_subreg_base: narrowing the link does not run backwards into the rest of the set
-sext_kinds_reach_different_values: the same low half reaches -1 through a sign extension and0xffffffffthrough a zero extension
Quoted 3 lines
Each guards a div by zero that is only unreachable if the propagation happened, so losing the link is a verification failure rather than a test that quietly stops checking anything.
This isn't a bug, but should the count read "six programs", and could the closing sentence be scoped to the two __success programs, since sext_self_mov_no_link has no div and the __failure ones expect it to be reachable?
Quoted 6 lines
tools/testing/selftests/bpf/progs/bpf_misc.h +0
-0@@ -269,6 +269,14 @@#define CAN_USE_BPF_ST
tools/testing/selftests/bpf/progs/bpf_misc.h line 279
Quoted 10 lines
tools/testing/selftests/bpf/progs/bpf_misc.h +8
-0#endif +#if (defined(__TARGET_ARCH_arm64) || defined(__TARGET_ARCH_x86) || \ + (defined(__TARGET_ARCH_riscv) && __riscv_xlen ==64 ) || \ + defined(__TARGET_ARCH_arm) || defined(__TARGET_ARCH_s390) || \ + defined(__TARGET_ARCH_loongarch)) && \ + (__clang_major__ >=18 || defined(__BPF_FEATURE_MOVSX)) +#define CAN_USE_MOVSX +#endif +
This isn't a bug, but now that the gate lives in bpf_misc.h, would it be worth switching verifier_movsx.c's inline #if over to #ifdef CAN_USE_MOVSX so the arch/feature list exists in one place?
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c
Quoted 2 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +0
-0
[ ... ]
---
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/34506184282
Re: [PATCH bpf-next v2 08/13] selftests/bpf: cover the low-32 link for sign-extending movs
Quoted 15 lines · On 9/10/26 11:22 PM, [email protected] wrote:
Quoted 15 lines
selftests/bpf: cover the low-32 link for sign-extending movs
Five programs, mirroring the zero-extending set:
-
sext_mov_wide_src: narrowing the source reaches the destination, and the value that arrives is sign-extended rather than zero-extended
-sext_self_mov_keeps_link: r0 = (s32)r0 on an already-linked register stays in its set, the shape a sign-extended int return takes
-sext_self_mov_no_link: the same mov on an unlinked register mints no id
-sext_no_sync_when_base_has_delta: a delta on the base stops propagation
-sext_no_sync_from_subreg_base: narrowing the link does not run backwards into the rest of the set
-sext_kinds_reach_different_values: the same low half reaches -1 througha sign extension and 0xffffffff through a zero extension
Quoted 7 lines
Quoted 3 lines
Each guards a div by zero that is only unreachable if the propagation happened, so losing the link is a verification failure rather than a test that quietly stops checking anything.
This isn't a bug, but should the count read "six programs", and could the closing sentence be scoped to the two
__successprograms, sincesext_self_mov_no_linkhas no div and the__failureones expect it to be reachable?
OK.
Quoted 8 lines
Quoted 8 lines
tools/testing/selftests/bpf/progs/bpf_misc.h +0
-0@@ -269,6 +269,14 @@#define CAN_USE_BPF_ST #endif
Quoted 11 lines
tools/testing/selftests/bpf/progs/bpf_misc.h line 279
Quoted 8 lines
tools/testing/selftests/bpf/progs/bpf_misc.h +8
-0+#if (defined(__TARGET_ARCH_arm64) || defined(__TARGET_ARCH_x86) || \ + (defined(__TARGET_ARCH_riscv) && __riscv_xlen ==64 ) || \ + defined(__TARGET_ARCH_arm) || defined(__TARGET_ARCH_s390) || \ + defined(__TARGET_ARCH_loongarch)) && \ + (__clang_major__ >=18 || defined(__BPF_FEATURE_MOVSX)) +#define CAN_USE_MOVSX +#endif +This isn't a bug, but now that the gate lives in
bpf_misc.h, would it be worth switching verifier_movsx.c's inline #if over to #ifdefCAN_USE_MOVSXso thearch/featurelist exists in one place?
Yes.
Thx,
-Vineet
Quoted 10 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c
Quoted 2 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +0
-0[ ... ]
---
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.mdCI run summary: https://github.com/kernel-patches/bpf/actions/runs/34506184282
PATCH v2 9/13 bpf: track low-32 scalar equality across narrowing stack fills
In reply to Vineet GuptaA 32-bit fill from a wider spilled scalar has the same shape as a 32-bit mov from a wider source: the destination shares the slot's low 32 bits and nothing else. The relation was dropped instead of recorded, so a later narrowing of the spilled value never reached the filled register:
r6 = ... /* full 64-bit unknown */ *(u64 *)(r10 - 8) = r6; /* slot linked to r6 */ r2 = *(u32 *)(r10 - 8); /* narrowing fill */ if w6 != 0 goto ... /* not taken: r6's low 32 bits are 0 */ if r2 == 0 goto ... /* not deduced today */
Record a low-32 link, as the mov arm does. Stack slots are already first-class members of an ->id set, so sync_linked_regs() and the reconstruction helpers apply unchanged. A fill narrower than 32 bits has no expressible relation and still drops it.
Which kind to record depends on how the load fills the high half, so check_stack_read() takes is_ldsx. Doing it there rather than correcting afterwards in check_mem_access() keeps a single assignment.
check_mem_access() in turn no longer clears the id of a ->subreg register on a sign-extending load: the link already records how the high half follows, which is what that sign extension produced.
---
v2: new. Loads were asked for on the RFC cover letter; the fill is the only load whose destination inherits an id.
kernel/bpf/verifier.c | 43 +++++++++++++++++++++++++++++++------------ 1 file changed, 31 insertions(+), 12 deletions(-)
kernel/bpf/verifier.c +31 -12
@@ -3927,7 +3927,8 @@ static void bpf_diag_stack_read_uninit(struct bpf_verifier_env *env, int off, instatic int check_stack_read_fixed_off (struct bpf_verifier_env *env,/* func where src register points to */ struct bpf_func_state *reg_state, -int off,int size,int dst_regno) +int off,int size,int dst_regno, +bool is_ldsx) {struct bpf_verifier_state *vstate = env->cur_state;struct bpf_func_state *state = vstate->frame[vstate->curframe];
@@ -3968,18 +3969,34 @@ static int check_stack_read_fixed_off(struct bpf_verifier_env *env,if (size <= spill_size &&bpf_stack_narrow_access_ok (off, size, spill_size)) { -if (env->bpf_capable && size ==4 && spill_size ==4 && -get_reg_width (reg) <=32 ) +bool narrowing =get_reg_width (reg) > size *BITS_PER_BYTE ; +/* +* A narrowing fill keeps only the slot's low 32 bits, +* so record a low-32 link rather than dropping the +* relation, as a 32-bit mov from a wide source does. +* Which kind depends on how the load fills the high +* half, hence is_ldsx. +*/ +bool subreg_link = narrowing && size ==4 ; + +if (env->bpf_capable && size ==4 && + (subreg_link || (spill_size ==4 && !narrowing)))/* Ensure stack slot has an ID to build a relation * with the destination register on fill. */ assign_scalar_id_before_mov (env, reg); state->regs[dst_regno] = *reg; -/* Break the relation on a narrowing fill. -* coerce_reg_to_size will adjust the boundaries. -*/ -if (get_reg_width (reg) > size *BITS_PER_BYTE ) +if (subreg_link && reg->id) + state->regs[dst_regno].subreg = + is_ldsx ?SUBREG_SEXT :SUBREG_ZEXT ; +else if (narrowing) +/* +* Nothing to relate: either the slot has +* no id to share, or the fill is narrower +* than the 32 bits a link can describe. +* coerce_reg_to_size adjusts the bounds. +*/ clear_scalar_id (&state->regs[dst_regno]); }else {int spill_cnt =0 , zero_cnt =0 ;
@@ -4144,7 +4161,7 @@ static int check_stack_read_var_off(struct bpf_verifier_env *env, struct bpf_reg*/ static int check_stack_read (struct bpf_verifier_env *env,struct bpf_reg_state *reg,argno_t ptr_argno,int off,int size, -int dst_regno) +int dst_regno,bool is_ldsx) {struct bpf_func_state *state =bpf_func (env, reg);int err;
@@ -4183,7 +4200,7 @@ static int check_stack_read(struct bpf_verifier_env *env,if (!var_off) { off += reg->var_off.value; err =check_stack_read_fixed_off (env, state, off, size, - dst_regno); + dst_regno, is_ldsx); }else {/* Variable offset stack reads need more conservative handling * than fixed offset ones. Note that dst_regno >= 0 on this
@@ -6639,7 +6656,7 @@ static int check_mem_access(struct bpf_verifier_env *env, int insn_idx, struct bif (t ==BPF_READ ) err =check_stack_read (env, reg, argno, off, size, - value_regno); + value_regno, is_ldsx);else err =check_stack_write (env, reg, off, size, value_regno, insn_idx);
@@ -6736,13 +6753,15 @@ static int check_mem_access(struct bpf_verifier_env *env, int insn_idx, struct b* Sign-extension can change the register value relative * to a scalar it is linked with by id (e.g. a zero- * extending fill of the same spilled stack slot), thus -* drop the shared id in that case. +* drop the shared id in that case. A ->subreg link is +* the exception: it already records that only the low +* 32 bits are shared, and how the high half follows. */ bool no_sext =reg_umax (®s[value_regno]) < (1ULL << (size *BITS_PER_BYTE -1 ));coerce_reg_to_size_sx (®s[value_regno], size); -if (!no_sext) +if (!no_sext && !regs[value_regno].subreg)clear_scalar_id (®s[value_regno]); } }
Signature · 1 line
2.53.0-Meta
[email protected]
AI reviewRe: [PATCH bpf-next v2 09/13] bpf: track low-32 scalar equality across narrowing stack fills
Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider: - [Critical] Sign-extending loads incorrectly preserve conflicting SUBREG_ZEXT metadata. --
Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
- [Critical] Sign-extending loads incorrectly preserve conflicting SUBREG_ZEXT metadata. --
commit f939550a777ae3d2a7392dec744bffdc9fabcdda
Author: Vineet Gupta <[email protected]>
bpf: track low-32 scalar equality across narrowing stack fills
This commit records a low-32 link for stack fills narrower than the wider source, allowing the verifier to deduce relations between 32-bit narrows and their wider origins. It also adjusts check_mem_access() to not clear the id of a ->subreg register on a sign-extending load.
Quoted 4 lines
kernel/bpf/verifier.c +0
-0
[ ... ]
Quoted 29 lines
kernel/bpf/verifier.c +13
-6@@ -3968,18 +3969,34 @@ static int check_stack_read_fixed_off(struct bpf_verifier_env *env,if (size <= spill_size &&bpf_stack_narrow_access_ok (off, size, spill_size)) { -if (env->bpf_capable && size ==4 && spill_size ==4 && -get_reg_width (reg) <=32 ) +bool narrowing =get_reg_width (reg) > size *BITS_PER_BYTE ; +/* +* A narrowing fill keeps only the slot's low 32 bits, +* so record a low-32 link rather than dropping the +* relation, as a 32-bit mov from a wide source does. +* Which kind depends on how the load fills the high +* half, hence is_ldsx. +*/ +bool subreg_link = narrowing && size ==4 ; + +if (env->bpf_capable && size ==4 && + (subreg_link || (spill_size ==4 && !narrowing)))/* Ensure stack slot has an ID to build a relation * with the destination register on fill. */ assign_scalar_id_before_mov (env, reg); state->regs[dst_regno] = *reg; -/* Break the relation on a narrowing fill. -* coerce_reg_to_size will adjust the boundaries. -*/ -if (get_reg_width (reg) > size *BITS_PER_BYTE ) +if (subreg_link && reg->id)
kernel/bpf/verifier.c static int check_stack_read_fixed_off(struct bpf_verifier_env *env, · line 4000
Quoted 10 lines
kernel/bpf/verifier.c +9
-0+ state->regs[dst_regno].subreg = + is_ldsx ?SUBREG_SEXT :SUBREG_ZEXT ; + else if (narrowing) + /* + * Nothing to relate: either the slot has + * no id to share, or the fill is narrower + * than the 32 bits a link can describe. + * coerce_reg_to_size adjusts the bounds. + */ clear_scalar_id(&state->regs[dst_regno]);
[Severity: Critical]
When narrowing is false, does this preserve a stale SUBREG_ZEXT property for a sign-extending load?
If a register with SUBREG_ZEXT is spilled to the stack and then read back via a 4-byte sign-extending load, narrowing evaluates to false. This allows the destination register to inherit the SUBREG_ZEXT property directly from the stack slot, even though it is being sign-extended.
[ ... ]
Quoted 6 lines
kernel/bpf/verifier.c +1
-1@@ -6736,13 +6753,15 @@ static int check_mem_access(struct bpf_verifier_env *env, int insn_idx, struct b* Sign-extension can change the register value relative * to a scalar it is linked with by id (e.g. a zero- * extending fill of the same spilled stack slot), thus -* drop the shared id in that case. +* drop the shared id in that case. A ->subreg link is
kernel/bpf/verifier.c static int check_mem_access(struct bpf_verifier_env *env, int insn_idx, struct b · line 6765
Quoted 10 lines
kernel/bpf/verifier.c +3
-1+* the exception: it already records that only the low +* 32 bits are shared, and how the high half follows. */ bool no_sext =reg_umax (®s[value_regno]) < (1ULL << (size *BITS_PER_BYTE -1 ));coerce_reg_to_size_sx (®s[value_regno], size); -if (!no_sext) +if (!no_sext && !regs[value_regno].subreg)clear_scalar_id (®s[value_regno]);
[Severity: Critical]
Does this check wrongly preserve the ID for SUBREG_ZEXT registers that have just been sign-extended?
Because SUBREG_ZEXT is non-zero, !regs[value_regno].subreg evaluates to false, skipping the clear_scalar_id() call for a register that might hold a sign-extended negative value.
Later, if a conditional branch triggers sync_linked_regs(), it will see SUBREG_ZEXT and invoke reconstruct_zext32(). This would forcefully set the bounds to a zero-extended positive value.
At runtime, the discrepancy between the verifier's zero-extended positive bounds and the actual sign-extended negative value could bypass bounds checks, potentially leading to out-of-bounds memory reads or writes.
Should this explicitly check for SUBREG_SEXT rather than just allowing any non-zero ->subreg value?
Signature · 1 line
Sashiko AI review · https://sashiko.dev/#/patchset/[email protected]?part=9
Re: [PATCH bpf-next v2 09/13] bpf: track low-32 scalar equality across narrowing stack fills
Quoted 63 lines · On 9/10/26 10:34 PM, [email protected] wrote:
Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
- [Critical] Sign-extending loads incorrectly preserve conflictingSUBREG_ZEXTmetadata. --commit
f939550a777ae3d2a7392dec744bffdc9fabcdda
Author: Vineet Gupta <[email protected]>bpf: track low-32 scalar equality across narrowing stack fills
This commit records a low-32 link for stack fills narrower than the wider source, allowing the verifier to deduce relations between 32-bit narrows and their wider origins. It also adjusts
check_mem_access()to not clear the id of a ->subreg register on a sign-extending load.Quoted 4 lines
kernel/bpf/verifier.c +0
-0[ ... ]
Quoted 29 lines
kernel/bpf/verifier.c +13
-6@@ -3968,18 +3969,34 @@ static int check_stack_read_fixed_off(struct bpf_verifier_env *env,if (size <= spill_size &&bpf_stack_narrow_access_ok (off, size, spill_size)) { -if (env->bpf_capable && size ==4 && spill_size ==4 && -get_reg_width (reg) <=32 ) +bool narrowing =get_reg_width (reg) > size *BITS_PER_BYTE ; +/* +* A narrowing fill keeps only the slot's low 32 bits, +* so record a low-32 link rather than dropping the +* relation, as a 32-bit mov from a wide source does. +* Which kind depends on how the load fills the high +* half, hence is_ldsx. +*/ +bool subreg_link = narrowing && size ==4 ; + +if (env->bpf_capable && size ==4 && + (subreg_link || (spill_size ==4 && !narrowing)))/* Ensure stack slot has an ID to build a relation * with the destination register on fill. */ assign_scalar_id_before_mov (env, reg); state->regs[dst_regno] = *reg; -/* Break the relation on a narrowing fill. -* coerce_reg_to_size will adjust the boundaries. -*/ -if (get_reg_width (reg) > size *BITS_PER_BYTE ) +if (subreg_link && reg->id)kernel/bpf/verifier.c static int check_stack_read_fixed_off(struct bpf_verifier_env *env, · line 4000
Quoted 10 lines
kernel/bpf/verifier.c +9
-0+ state->regs[dst_regno].subreg = + is_ldsx ?SUBREG_SEXT :SUBREG_ZEXT ; + else if (narrowing) + /* + * Nothing to relate: either the slot has + * no id to share, or the fill is narrower + * than the 32 bits a link can describe. + * coerce_reg_to_size adjusts the bounds. + */ clear_scalar_id(&state->regs[dst_regno]);[Severity: Critical]
When narrowing is false, does this preserve a staleSUBREG_ZEXTproperty for a sign-extending load?
Quoted 6 lines
If a register with
SUBREG_ZEXTis spilled to the stack and then read back via a 4-byte sign-extending load, narrowing evaluates to false. This allows the destination register to inherit theSUBREG_ZEXTproperty directly from the stack slot, even though it is being sign-extended.[ ... ]
Indeed if narrowing is false, wrong metadata can potentially be introduced, a comment to that effect is added here.
/*
* A fill that is not narrowing copies the slot's
* kind verbatim, which a sign-extending load can
* contradict. check_mem_access() runs after this
* and drops any kind but SUBREG_SEXT once it knows
* the extension was not a no-op.
*/
See the second site below for actual fix...
Quoted 28 lines
Quoted 6 lines
kernel/bpf/verifier.c +1
-1@@ -6736,13 +6753,15 @@ static int check_mem_access(struct bpf_verifier_env *env, int insn_idx, struct b* Sign-extension can change the register value relative * to a scalar it is linked with by id (e.g. a zero- * extending fill of the same spilled stack slot), thus -* drop the shared id in that case. +* drop the shared id in that case. A ->subreg link is kernel/bpf/verifier.c static int check_mem_access(struct bpf_verifier_env *env, int insn_idx, struct b · line 6765
Quoted 10 lines
kernel/bpf/verifier.c +3
-1+* the exception: it already records that only the low +* 32 bits are shared, and how the high half follows. */ bool no_sext =reg_umax (®s[value_regno]) < (1ULL << (size *BITS_PER_BYTE -1 ));coerce_reg_to_size_sx (®s[value_regno], size); -if (!no_sext) +if (!no_sext && !regs[value_regno].subreg)clear_scalar_id (®s[value_regno]);[Severity: Critical]
Does this check wrongly preserve the ID forSUBREG_ZEXTregisters that have just been sign-extended?Because
SUBREG_ZEXTis non-zero, !regs[value_regno].subreg evaluates to false, skipping theclear_scalar_id()call for a register that might hold a sign-extended negative value.Later, if a conditional branch triggers
sync_linked_regs(), it will seeSUBREG_ZEXTand invokereconstruct_zext32(). This would forcefully set the bounds to a zero-extended positive value.
Quoted 6 lines
At runtime, the discrepancy between the verifier's zero-extended positive bounds and the actual sign-extended negative value could bypass bounds checks, potentially leading to out-of-bounds memory reads or writes.
Should this explicitly check for
SUBREG_SEXTrather than just allowing any non-zero ->subreg value?
Exactly that. And the first path leads here so the comment above suffices.
Thx,
-Vineet
Re: [PATCH bpf-next v2 09/13] bpf: track low-32 scalar equality across narrowing stack fills
Quoted 112 lines · Vineet Gupta
Quoted 63 lines · On 9/10/26 10:34 PM, [email protected] wrote:
Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
- [Critical] Sign-extending loads incorrectly preserve conflictingSUBREG_ZEXTmetadata. --commit
f939550a777ae3d2a7392dec744bffdc9fabcdda
Author: Vineet Gupta <[email protected]>bpf: track low-32 scalar equality across narrowing stack fills
This commit records a low-32 link for stack fills narrower than the wider source, allowing the verifier to deduce relations between 32-bit narrows and their wider origins. It also adjusts
check_mem_access()to not clear the id of a ->subreg register on a sign-extending load.Quoted 4 lines
kernel/bpf/verifier.c +0
-0[ ... ]
Quoted 29 lines
kernel/bpf/verifier.c +13
-6@@ -3968,18 +3969,34 @@ static int check_stack_read_fixed_off(struct bpf_verifier_env *env,if (size <= spill_size &&bpf_stack_narrow_access_ok (off, size, spill_size)) { -if (env->bpf_capable && size ==4 && spill_size ==4 && -get_reg_width (reg) <=32 ) +bool narrowing =get_reg_width (reg) > size *BITS_PER_BYTE ; +/* +* A narrowing fill keeps only the slot's low 32 bits, +* so record a low-32 link rather than dropping the +* relation, as a 32-bit mov from a wide source does. +* Which kind depends on how the load fills the high +* half, hence is_ldsx. +*/ +bool subreg_link = narrowing && size ==4 ; + +if (env->bpf_capable && size ==4 && + (subreg_link || (spill_size ==4 && !narrowing)))/* Ensure stack slot has an ID to build a relation * with the destination register on fill. */ assign_scalar_id_before_mov (env, reg); state->regs[dst_regno] = *reg; -/* Break the relation on a narrowing fill. -* coerce_reg_to_size will adjust the boundaries. -*/ -if (get_reg_width (reg) > size *BITS_PER_BYTE ) +if (subreg_link && reg->id)kernel/bpf/verifier.c static int check_stack_read_fixed_off(struct bpf_verifier_env *env, · line 4000
Quoted 10 lines
kernel/bpf/verifier.c +9
-0+ state->regs[dst_regno].subreg = + is_ldsx ?SUBREG_SEXT :SUBREG_ZEXT ; + else if (narrowing) + /* + * Nothing to relate: either the slot has + * no id to share, or the fill is narrower + * than the 32 bits a link can describe. + * coerce_reg_to_size adjusts the bounds. + */ clear_scalar_id(&state->regs[dst_regno]);[Severity: Critical]
When narrowing is false, does this preserve a staleSUBREG_ZEXTproperty for a sign-extending load?Quoted 6 lines
If a register with
SUBREG_ZEXTis spilled to the stack and then read back via a 4-byte sign-extending load, narrowing evaluates to false. This allows the destination register to inherit theSUBREG_ZEXTproperty directly from the stack slot, even though it is being sign-extended.[ ... ]
Indeed if narrowing is false, wrong metadata can potentially be introduced, a comment to that effect is added here.
/*
* A fill that is not narrowing copies the slot's
* kind verbatim, which a sign-extending load can
* contradict.check_mem_access()runs after this
* and drops any kind butSUBREG_SEXTonce it knows
* the extension was not a no-op.
*/See the second site below for actual fix...
Quoted 28 lines
Quoted 6 lines
kernel/bpf/verifier.c +1
-1@@ -6736,13 +6753,15 @@ static int check_mem_access(struct bpf_verifier_env *env, int insn_idx, struct b* Sign-extension can change the register value relative * to a scalar it is linked with by id (e.g. a zero- * extending fill of the same spilled stack slot), thus -* drop the shared id in that case. +* drop the shared id in that case. A ->subreg link is kernel/bpf/verifier.c static int check_mem_access(struct bpf_verifier_env *env, int insn_idx, struct b · line 6765
Quoted 10 lines
kernel/bpf/verifier.c +3
-1+* the exception: it already records that only the low +* 32 bits are shared, and how the high half follows. */ bool no_sext =reg_umax (®s[value_regno]) < (1ULL << (size *BITS_PER_BYTE -1 ));coerce_reg_to_size_sx (®s[value_regno], size); -if (!no_sext) +if (!no_sext && !regs[value_regno].subreg)clear_scalar_id (®s[value_regno]);[Severity: Critical]
Does this check wrongly preserve the ID forSUBREG_ZEXTregisters that have just been sign-extended?Because
SUBREG_ZEXTis non-zero, !regs[value_regno].subreg evaluates to false, skipping theclear_scalar_id()call for a register that might hold a sign-extended negative value.Later, if a conditional branch triggers
sync_linked_regs(), it will seeSUBREG_ZEXTand invokereconstruct_zext32(). This would forcefully set the bounds to a zero-extended positive value.
Quoted 7 lines
Quoted 6 lines
At runtime, the discrepancy between the verifier's zero-extended positive bounds and the actual sign-extended negative value could bypass bounds checks, potentially leading to out-of-bounds memory reads or writes.
Should this explicitly check for
SUBREG_SEXTrather than just allowing any non-zero ->subreg value?Exactly that. And the first path leads here so the comment above suffices.
What I meant was first site has comment, and this site has the exact fix which sashiko identified. They are both part of the same bug.
Thx
PATCH v2 10/13 selftests/bpf: cover the low-32 link for narrowing stack fills
In reply to Vineet GuptaFive programs, following the mov set:
- zext_fill_narrow_from_wide_spill: narrowing the spilled value reaches the filled register
- sext_fill_narrow_from_wide_spill: the same for a sign-extending fill, and the value that arrives is sign-extended
- zext_fill_full_width_keeps_full_link: a full-width fill is a plain 64-bit equality and must keep propagating as before
- zext_fill_byte_forms_no_link: a sub-word fill is below the low-32 model, so no link is formed
- fill_kinds_reach_different_values: the same, for the two fill kinds off one slot
The first two are the ones that pin the new behaviour: disabling link formation in the fill arm makes both fail. The other three are guards against the feature applying where it should not, and hold either way.
---
v2: new, with 9/13.
.../bpf/progs/verifier_linked_scalars.c | 144 ++++++++++++++++++ 1 file changed, 144 insertions(+)
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +144 -0
@@ -966,6 +966,88 @@ __naked void zext_mov_breaks_add_const_src(void) : __clobber_all); } +/* +* A narrowing fill keeps only the slot's low 32 bits, so a later narrowing of +* the spilled value must still reach the filled register. Same relation as a +* 32-bit mov from a wide source, with the stack slot as the base. +*/ +SEC("socket") +__success +__naked void zext_fill_narrow_from_wide_spill (void ) +{ + asmvolatile (" \ +call %[bpf_get_prandom_u32]; \ +r6 = r0; \ +call %[bpf_get_prandom_u32]; \ +r0 <<= 32; \ +r6 |= r0; /* r6 = full 64-bit unknown */ \ +*(u64 *)(r10 - 8) = r6; /* slot linked to r6 */ \ +r2 = *(u32 *)(r10 - 8); /* narrowing fill, forms the link */ \ +if w6 != 0 goto 1f; /* narrows r6, propagates to r2 */ \ +if r2 == 0 goto 1f; \ +r0 /= 0; \ +1: \ +r0 = 0; \ +exit; \ +" : + : __imm(bpf_get_prandom_u32) + : __clobber_all); +} + +/* +* A full-width fill of a wide slot is a plain 64-bit equality, not a low-32 +* link, so it must keep propagating exactly as before. +*/ +SEC("socket") +__success +__naked void zext_fill_full_width_keeps_full_link (void ) +{ + asmvolatile (" \ +call %[bpf_get_prandom_u32]; \ +r6 = r0; \ +call %[bpf_get_prandom_u32]; \ +r0 <<= 32; \ +r6 |= r0; \ +*(u64 *)(r10 - 8) = r6; \ +r2 = *(u64 *)(r10 - 8); /* no narrowing */ \ +if r6 != 0 goto 1f; \ +if r2 == 0 goto 1f; \ +r0 /= 0; \ +1: \ +r0 = 0; \ +exit; \ +" : + : __imm(bpf_get_prandom_u32) + : __clobber_all); +} + +/* +* A sub-word fill is below the low-32 model, so no link is formed and the +* relation is dropped as before. +*/ +SEC("socket") +__failure __msg("div by zero") +__naked void zext_fill_byte_forms_no_link(void) +{ + asmvolatile (" \ +call %[bpf_get_prandom_u32]; \ +r6 = r0; \ +call %[bpf_get_prandom_u32]; \ +r0 <<= 32; \ +r6 |= r0; \ +*(u64 *)(r10 - 8) = r6; \ +r2 = *(u8 *)(r10 - 8); /* 1-byte fill: no link */ \ +if w6 != 0 goto 1f; \ +if r2 == 0 goto 1f; /* not deduced */ \ +r0 /= 0; \ +1: \ +r0 = 0; \ +exit; \ +" : + : __imm(bpf_get_prandom_u32) + : __clobber_all); +} +#ifdef CAN_USE_MOVSX /*
@@ -1129,6 +1211,68 @@ __naked void sext_kinds_reach_different_values(void) : __clobber_all); } +/* +* The sign-extending counterpart: the filled register is the sign extension of +* the slot's low 32 bits, so a narrowing of those bits arrives sign-extended. +*/ +SEC("socket") +__success +__naked void sext_fill_narrow_from_wide_spill (void ) +{ + asmvolatile (" \ +call %[bpf_get_prandom_u32]; \ +r6 = r0; \ +call %[bpf_get_prandom_u32]; \ +r0 <<= 32; \ +r6 |= r0; /* r6 = full 64-bit unknown */ \ +*(u64 *)(r10 - 8) = r6; /* slot linked to r6 */ \ +r2 = *(s32 *)(r10 - 8); /* narrowing sx fill */ \ +if w6 != -1 goto 1f; /* narrows r6, propagates to r2 */ \ +if r2 == -1 goto 1f; /* sign-extended, not 0xffffffff */ \ +r0 /= 0; \ +1: \ +r0 = 0; \ +exit; \ +" : + : __imm(bpf_get_prandom_u32) + : __clobber_all); +} + +/* +* The same, for the two fill kinds off one slot. +*/ +SEC("socket") +__failure __msg("div by zero") +__flag (BPF_F_TEST_STATE_FREQ) +__naked void fill_kinds_reach_different_values(void) +{ + asmvolatile (" \ +call %[bpf_get_prandom_u32]; \ +r6 = r0; \ +r6 &= 1; \ +call %[bpf_get_prandom_u32]; \ +r8 = r0; \ +call %[bpf_get_prandom_u32]; \ +r0 <<= 32; \ +r8 |= r0; \ +*(u64 *)(r10 - 8) = r8; \ +if r6 >= 1 goto 2f; \ +r2 = *(s32 *)(r10 - 8); /* sign-extending fill */ \ +goto 1f; \ +2: \ +r2 = *(u32 *)(r10 - 8); /* zero-extending fill */ \ +1: \ +if w8 != -1 goto 3f; \ +if r2 == -1 goto 3f; /* only the sign-extending path */ \ +r0 /= 0; \ +3: \ +r0 = 0; \ +exit; \ +" : + : __imm(bpf_get_prandom_u32) + : __clobber_all); +} +#endif /* CAN_USE_MOVSX */ char _license[] SEC("license") = "GPL";
Signature · 1 line
2.53.0-Meta
[email protected]
AI reviewRe: [PATCH bpf-next v2 10/13] selftests/bpf: cover the low-32 link for narrowing stack fills
Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider: - [Medium] The newly added tests for narrow stack fills hardcode memory offsets (e.g., `(r10 - 8)`) which…
Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
- [Medium] The newly added tests for narrow stack fills hardcode memory offsets (e.g., (r10 - 8)) which are only correct on little-endian architectures. On big-endian architectures like s390x, these offsets do not point to the lower bits, causing the BPF verifier to reject the programs and resulting in test failures. --
commit a42f9a6d4d49f17385f014eede55d6e82094a838
Author: Vineet Gupta <[email protected]>
selftests/bpf: cover the low-32 link for narrowing stack fills
This commit adds five new BPF programs to test the verifier's handling of narrowing stack fills, specifically targeting low-32 links and sign-extension behavior.
Quoted 3 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +0
-0
[ ... ]
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c __naked void zext_mov_breaks_add_const_src(void) · line 985
Quoted 12 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +12
-0+SEC("socket") +__success +__naked void zext_fill_narrow_from_wide_spill (void ) +{ + asm volatile (" \ + call %[bpf_get_prandom_u32]; \ + r6 = r0; \ + call %[bpf_get_prandom_u32]; \ + r0 <<= 32; \ + r6 |= r0; /* r6 = full 64-bit unknown */ \ + *(u64 *)(r10 - 8) = r6; /* slot linked to r6 */ \ + r2 = *(u32 *)(r10 - 8); /* narrowing fill, forms the link */ \
[Severity: Medium]
On big-endian architectures like s390x, won't reading 32 bits from offset -8 target the upper 32 bits instead of the lower 32 bits?
The bpf_stack_narrow_access_ok() check in the verifier expects to read the least significant bytes of the spill slot, which on big-endian are located at offset -4 for a 32-bit read. Could this hardcoded offset cause the verifier to reject the program and break the test on big-endian systems?
Quoted 10 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +10
-0+ if w6 != 0 goto 1f; /* narrows r6, propagates to r2 */ \ + if r2 == 0 goto 1f; \ + r0 /=0 ; \ +1: \ + r0 =0 ; \ + exit; \ +" : + : __imm(bpf_get_prandom_u32) + : __clobber_all); +}
[ ... ]
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c __naked void zext_mov_breaks_add_const_src(void) · line 1039
Quoted 12 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +12
-0+SEC("socket") +__failure __msg("div by zero") +__naked void zext_fill_byte_forms_no_link (void ) +{ + asm volatile (" \ + call %[bpf_get_prandom_u32]; \ + r6 = r0; \ + call %[bpf_get_prandom_u32]; \ + r0 <<= 32; \ + r6 |= r0; \ + *(u64 *)(r10 - 8) = r6; \ + r2 = *(u8 *)(r10 - 8); /* 1-byte fill: no link */ \
[Severity: Medium]
Does this hardcoded 8-bit read from offset -8 target the most significant byte rather than the least significant byte on big-endian architectures?
Quoted 10 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +10
-0+ if w6 != 0 goto 1f; \ + if r2 == 0 goto 1f; /* not deduced */ \ + r0 /=0 ; \ +1: \ + r0 =0 ; \ + exit; \ +" : + : __imm(bpf_get_prandom_u32) + : __clobber_all); +}
[ ... ]
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c __naked void sext_kinds_reach_different_values(void) · line 1229
Quoted 12 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +12
-0+SEC("socket") +__success +__naked void sext_fill_narrow_from_wide_spill (void ) +{ + asm volatile (" \ + call %[bpf_get_prandom_u32]; \ + r6 = r0; \ + call %[bpf_get_prandom_u32]; \ + r0 <<= 32; \ + r6 |= r0; /* r6 = full 64-bit unknown */ \ + *(u64 *)(r10 - 8) = r6; /* slot linked to r6 */ \ + r2 = *(s32 *)(r10 - 8); /* narrowing sx fill */ \
[Severity: Medium]
Similar to the previous cases, will this 32-bit read from offset -8 read the upper 32 bits on big-endian systems and cause verifier bounds tracking to fail?
Quoted 10 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +10
-0+ if w6 != -1 goto 1f; /* narrows r6, propagates to r2 */ \ + if r2 == -1 goto 1f; /* sign-extended, not 0xffffffff */ \ + r0 /=0 ; \ +1: \ + r0 =0 ; \ + exit; \ +" : + : __imm(bpf_get_prandom_u32) + : __clobber_all); +}
[ ... ]
Quoted 7 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +7
-0+SEC("socket") +__failure __msg("div by zero") +__flag (BPF_F_TEST_STATE_FREQ) +__naked void fill_kinds_reach_different_values(void) +{ + asm volatile (" \ + call %[bpf_get_prandom_u32]; \
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c __naked void sext_kinds_reach_different_values(void) · line 1260
Quoted 10 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +10
-0+ r6 = r0; \ + r6 &=1 ; \ + call %[bpf_get_prandom_u32]; \ + r8 = r0; \ + call %[bpf_get_prandom_u32]; \ + r0 <<=32 ; \ + r8 |= r0; \ + *(u64 *)(r10 -8 ) = r8; \ + if r6 >= 1 goto 2f; \ + r2 = *(s32 *)(r10 -8 );/* sign-extending fill */ \
[Severity: Medium]
Will these narrow fills also fail verifier checks on big-endian machines due to the fixed -8 offset pointing to the wrong 32-bit half?
Quoted 6 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +6
-0+ goto 1f; \ +2: \ + r2 = *(u32 *)(r10 -8 );/* zero-extending fill */ \ +1: \ + if w8 != -1 goto 3f; \ + if r2 == -1 goto 3f; /* only the sign-extending path */ \
Signature · 1 line
Sashiko AI review · https://sashiko.dev/#/patchset/[email protected]?part=10
Re: [PATCH bpf-next v2 10/13] selftests/bpf: cover the low-32 link for narrowing stack fills
Quoted 34 lines · On 9/10/26 10:30 PM, [email protected] wrote:
Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
- [Medium] The newly added tests for narrow stack fills hardcode memory offsets (e.g.,(r10 - 8)) which are only correct on little-endian architectures. On big-endian architectures like s390x, these offsets do not point to the lower bits, causing the BPF verifier to reject the programs and resulting in test failures. --commit
a42f9a6d4d49f17385f014eede55d6e82094a838
Author: Vineet Gupta <[email protected]>selftests/bpf: cover the low-32 link for narrowing stack fills
This commit adds five new BPF programs to test the verifier's handling of narrowing stack fills, specifically targeting low-32 links and sign-extension behavior.
Quoted 3 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +0
-0[ ... ]
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c __naked void zext_mov_breaks_add_const_src(void) · line 985
Quoted 12 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +12
-0+SEC("socket") +__success +__naked void zext_fill_narrow_from_wide_spill (void ) +{ + asm volatile (" \ + call %[bpf_get_prandom_u32]; \ + r6 = r0; \ + call %[bpf_get_prandom_u32]; \ + r0 <<= 32; \ + r6 |= r0; /* r6 = full 64-bit unknown */ \ + *(u64 *)(r10 - 8) = r6; /* slot linked to r6 */ \ + r2 = *(u32 *)(r10 - 8); /* narrowing fill, forms the link */ \[Severity: Medium]
On big-endian architectures like s390x, won't reading 32 bits from offset -8 target the upper 32 bits instead of the lower 32 bits?
Quoted 4 lines
The
bpf_stack_narrow_access_ok()check in the verifier expects to read the least significant bytes of the spill slot, which on big-endian are located at offset -4 for a 32-bit read. Could this hardcoded offset cause the verifier to reject the program and break the test on big-endian systems?
Goot catch. Fixed for BE and LE.
Quoted 12 lines
Quoted 10 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +10
-0+ if w6 != 0 goto 1f; /* narrows r6, propagates to r2 */ \ + if r2 == 0 goto 1f; \ + r0 /=0 ; \ +1: \ + r0 =0 ; \ + exit; \ +" : + : __imm(bpf_get_prandom_u32) + : __clobber_all); +}[ ... ]
Quoted 15 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c __naked void zext_mov_breaks_add_const_src(void) · line 1039
Quoted 12 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +12
-0+SEC("socket") +__failure __msg("div by zero") +__naked void zext_fill_byte_forms_no_link (void ) +{ + asm volatile (" \ + call %[bpf_get_prandom_u32]; \ + r6 = r0; \ + call %[bpf_get_prandom_u32]; \ + r0 <<= 32; \ + r6 |= r0; \ + *(u64 *)(r10 - 8) = r6; \ + r2 = *(u8 *)(r10 - 8); /* 1-byte fill: no link */ \[Severity: Medium]
Does this hardcoded 8-bit read from offset -8 target the most significant byte rather than the least significant byte on big-endian architectures?
Fixed.
Quoted 12 lines
Quoted 10 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +10
-0+ if w6 != 0 goto 1f; \ + if r2 == 0 goto 1f; /* not deduced */ \ + r0 /=0 ; \ +1: \ + r0 =0 ; \ + exit; \ +" : + : __imm(bpf_get_prandom_u32) + : __clobber_all); +}[ ... ]
Quoted 15 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c __naked void sext_kinds_reach_different_values(void) · line 1229
Quoted 12 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +12
-0+SEC("socket") +__success +__naked void sext_fill_narrow_from_wide_spill (void ) +{ + asm volatile (" \ + call %[bpf_get_prandom_u32]; \ + r6 = r0; \ + call %[bpf_get_prandom_u32]; \ + r0 <<= 32; \ + r6 |= r0; /* r6 = full 64-bit unknown */ \ + *(u64 *)(r10 - 8) = r6; /* slot linked to r6 */ \ + r2 = *(s32 *)(r10 - 8); /* narrowing sx fill */ \[Severity: Medium]
Similar to the previous cases, will this 32-bit read from offset -8 read the upper 32 bits on big-endian systems and cause verifier bounds tracking to fail?
Fixed.
Quoted 24 lines
Quoted 10 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +10
-0+ if w6 != -1 goto 1f; /* narrows r6, propagates to r2 */ \ + if r2 == -1 goto 1f; /* sign-extended, not 0xffffffff */ \ + r0 /=0 ; \ +1: \ + r0 =0 ; \ + exit; \ +" : + : __imm(bpf_get_prandom_u32) + : __clobber_all); +}[ ... ]
Quoted 12 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +12
-0+SEC("socket") +__failure __msg("div by zero") +__flag (BPF_F_TEST_STATE_FREQ) +__naked void fill_kinds_reach_different_values(void) +{ + asm volatile (" \ + call %[bpf_get_prandom_u32]; \ + r6 = r0; \ + r6 &= 1; \ + call %[bpf_get_prandom_u32]; \ + r8 = r0; \ + call %[bpf_get_prandom_u32]; \
Quoted 8 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c __naked void sext_kinds_reach_different_values(void) · line 1260
Quoted 5 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +5
-0+ r0 <<=32 ; \ + r8 |= r0; \ + *(u64 *)(r10 -8 ) = r8; \ + if r6 >= 1 goto 2f; \ + r2 = *(s32 *)(r10 -8 );/* sign-extending fill */ \[Severity: Medium]
Will these narrow fills also fail verifier checks on big-endian machines due to the fixed -8 offset pointing to the wrong 32-bit half?
Fixed.
Quoted 7 lines
Quoted 7 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +6
-0+ goto 1f; \ +2: \ + r2 = *(u32 *)(r10 -8 );/* zero-extending fill */ \ +1: \ + if w8 != -1 goto 3f; \ + if r2 == -1 goto 3f; /* only the sign-extending path */ \
[email protected]
AI reviewRe: [PATCH bpf-next v2 10/13] selftests/bpf: cover the low-32 link for narrowing stack fills
In reply to Vineet GuptaShould the guard here be checking for LDSX support instead? The two programs added below (sext_fill_narrow_from_wide_spill and fill_kinds_reach_different_values) both use BPF_LDX | BPF_MEMSX…
Quoted 4 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +0
-0
[ ... ]
Quoted 77 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +73
-0@@ -966,6 +966,88 @@ __naked void zext_mov_breaks_add_const_src(void) : __clobber_all); } +/* +* A narrowing fill keeps only the slot's low 32 bits, so a later narrowing of +* the spilled value must still reach the filled register. Same relation as a +* 32-bit mov from a wide source, with the stack slot as the base. +*/ +SEC("socket") +__success +__naked void zext_fill_narrow_from_wide_spill (void ) +{ + asmvolatile (" \ +call %[bpf_get_prandom_u32]; \ +r6 = r0; \ +call %[bpf_get_prandom_u32]; \ +r0 <<= 32; \ +r6 |= r0; /* r6 = full 64-bit unknown */ \ +*(u64 *)(r10 - 8) = r6; /* slot linked to r6 */ \ +r2 = *(u32 *)(r10 - 8); /* narrowing fill, forms the link */ \ +if w6 != 0 goto 1f; /* narrows r6, propagates to r2 */ \ +if r2 == 0 goto 1f; \ +r0 /= 0; \ +1: \ +r0 = 0; \ +exit; \ +" : + : __imm(bpf_get_prandom_u32) + : __clobber_all); +} + +/* +* A full-width fill of a wide slot is a plain 64-bit equality, not a low-32 +* link, so it must keep propagating exactly as before. +*/ +SEC("socket") +__success +__naked void zext_fill_full_width_keeps_full_link (void ) +{ + asmvolatile (" \ +call %[bpf_get_prandom_u32]; \ +r6 = r0; \ +call %[bpf_get_prandom_u32]; \ +r0 <<= 32; \ +r6 |= r0; \ +*(u64 *)(r10 - 8) = r6; \ +r2 = *(u64 *)(r10 - 8); /* no narrowing */ \ +if r6 != 0 goto 1f; \ +if r2 == 0 goto 1f; \ +r0 /= 0; \ +1: \ +r0 = 0; \ +exit; \ +" : + : __imm(bpf_get_prandom_u32) + : __clobber_all); +} + +/* +* A sub-word fill is below the low-32 model, so no link is formed and the +* relation is dropped as before. +*/ +SEC("socket") +__failure __msg("div by zero") +__naked void zext_fill_byte_forms_no_link(void) +{ + asm volatile (" \ + call %[bpf_get_prandom_u32]; \ + r6 = r0; \ + call %[bpf_get_prandom_u32]; \ + r0 <<= 32; \ + r6 |= r0; \ + *(u64 *)(r10 - 8) = r6; \ + r2 = *(u8 *)(r10 - 8); /* 1-byte fill: no link */ \ + if w6 != 0 goto 1f; \ + if r2 == 0 goto 1f; /* not deduced */ \
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c __naked void zext_mov_breaks_add_const_src(void) · line 1051
Quoted 10 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +9
-0+ r0 /=0 ; \ +1: \ + r0 =0 ; \ + exit; \ +" : + : __imm(bpf_get_prandom_u32) + : __clobber_all); +} +#ifdef CAN_USE_MOVSX
Should the guard here be checking for LDSX support instead? The two programs added below (sext_fill_narrow_from_wide_spill and fill_kinds_reach_different_values) both use BPF_LDX | BPF_MEMSX instructions (r2 = *(s32 *)(r10 - 8)), not MOVSX.
Other LDSX users in the suite gate on the LDSX feature - for instance, verifier_ldsx.c checks:
(__clang_major__ >= 18 || defined(__BPF_FEATURE_LDSX))
The two macros happen to align for clang >= 18 and gcc-bpf -mcpu=v4, but a compiler advertising MOVSX without LDSX would fail to build these programs rather than skipping them.
[ ... ]
Quoted 59 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +55
-0@@ -1129,6 +1211,68 @@ __naked void sext_kinds_reach_different_values(void) : __clobber_all); } +/* +* The sign-extending counterpart: the filled register is the sign extension of +* the slot's low 32 bits, so a narrowing of those bits arrives sign-extended. +*/ +SEC("socket") +__success +__naked void sext_fill_narrow_from_wide_spill (void ) +{ + asmvolatile (" \ +call %[bpf_get_prandom_u32]; \ +r6 = r0; \ +call %[bpf_get_prandom_u32]; \ +r0 <<= 32; \ +r6 |= r0; /* r6 = full 64-bit unknown */ \ +*(u64 *)(r10 - 8) = r6; /* slot linked to r6 */ \ +r2 = *(s32 *)(r10 - 8); /* narrowing sx fill */ \ +if w6 != -1 goto 1f; /* narrows r6, propagates to r2 */ \ +if r2 == -1 goto 1f; /* sign-extended, not 0xffffffff */ \ +r0 /= 0; \ +1: \ +r0 = 0; \ +exit; \ +" : + : __imm(bpf_get_prandom_u32) + : __clobber_all); +} + +/* +* The same, for the two fill kinds off one slot. +*/ +SEC("socket") +__failure __msg("div by zero") +__flag (BPF_F_TEST_STATE_FREQ) +__naked void fill_kinds_reach_different_values(void) +{ + asm volatile (" \ + call %[bpf_get_prandom_u32]; \ + r6 = r0; \ + r6 &= 1; \ + call %[bpf_get_prandom_u32]; \ + r8 = r0; \ + call %[bpf_get_prandom_u32]; \ + r0 <<= 32; \ + r8 |= r0; \ + *(u64 *)(r10 - 8) = r8; \ + if r6 >= 1 goto 2f; \ + r2 = *(s32 *)(r10 - 8); /* sign-extending fill */ \ + goto 1f; \ +2: \ + r2 = *(u32 *)(r10 - 8); /* zero-extending fill */ \ +1: \ + if w8 != -1 goto 3f; \ + if r2 == -1 goto 3f; /* only the sign-extending path */ \ + r0 /= 0; \ +3: \
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c __naked void sext_kinds_reach_different_values(void) · line 1278
Quoted 10 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +7
-0+ r0 =0 ; \ + exit; \ +" : + : __imm(bpf_get_prandom_u32) + : __clobber_all); +} +#endif /* CAN_USE_MOVSX */ char _license[] SEC("license") = "GPL";
---
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/34506184282
Re: [PATCH bpf-next v2 10/13] selftests/bpf: cover the low-32 link for narrowing stack fills
Quoted 98 lines · On 9/10/26 11:01 PM, [email protected] wrote:
Quoted 4 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +0
-0[ ... ]
Quoted 77 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +73
-0@@ -966,6 +966,88 @@ __naked void zext_mov_breaks_add_const_src(void) : __clobber_all); } +/* +* A narrowing fill keeps only the slot's low 32 bits, so a later narrowing of +* the spilled value must still reach the filled register. Same relation as a +* 32-bit mov from a wide source, with the stack slot as the base. +*/ +SEC("socket") +__success +__naked void zext_fill_narrow_from_wide_spill (void ) +{ + asmvolatile (" \ +call %[bpf_get_prandom_u32]; \ +r6 = r0; \ +call %[bpf_get_prandom_u32]; \ +r0 <<= 32; \ +r6 |= r0; /* r6 = full 64-bit unknown */ \ +*(u64 *)(r10 - 8) = r6; /* slot linked to r6 */ \ +r2 = *(u32 *)(r10 - 8); /* narrowing fill, forms the link */ \ +if w6 != 0 goto 1f; /* narrows r6, propagates to r2 */ \ +if r2 == 0 goto 1f; \ +r0 /= 0; \ +1: \ +r0 = 0; \ +exit; \ +" : + : __imm(bpf_get_prandom_u32) + : __clobber_all); +} + +/* +* A full-width fill of a wide slot is a plain 64-bit equality, not a low-32 +* link, so it must keep propagating exactly as before. +*/ +SEC("socket") +__success +__naked void zext_fill_full_width_keeps_full_link (void ) +{ + asmvolatile (" \ +call %[bpf_get_prandom_u32]; \ +r6 = r0; \ +call %[bpf_get_prandom_u32]; \ +r0 <<= 32; \ +r6 |= r0; \ +*(u64 *)(r10 - 8) = r6; \ +r2 = *(u64 *)(r10 - 8); /* no narrowing */ \ +if r6 != 0 goto 1f; \ +if r2 == 0 goto 1f; \ +r0 /= 0; \ +1: \ +r0 = 0; \ +exit; \ +" : + : __imm(bpf_get_prandom_u32) + : __clobber_all); +} + +/* +* A sub-word fill is below the low-32 model, so no link is formed and the +* relation is dropped as before. +*/ +SEC("socket") +__failure __msg("div by zero") +__naked void zext_fill_byte_forms_no_link(void) +{ + asm volatile (" \ + call %[bpf_get_prandom_u32]; \ + r6 = r0; \ + call %[bpf_get_prandom_u32]; \ + r0 <<= 32; \ + r6 |= r0; \ + *(u64 *)(r10 - 8) = r6; \ + r2 = *(u8 *)(r10 - 8); /* 1-byte fill: no link */ \ + if w6 != 0 goto 1f; \ + if r2 == 0 goto 1f; /* not deduced */ \tools/testing/selftests/bpf/progs/verifier_linked_scalars.c __naked void zext_mov_breaks_add_const_src(void) · line 1051
Quoted 10 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +9
-0+ r0 /=0 ; \ +1: \ + r0 =0 ; \ + exit; \ +" : + : __imm(bpf_get_prandom_u32) + : __clobber_all); +} +#ifdef CAN_USE_MOVSX Should the guard here be checking for LDSX support instead? The two programs added below (
sext_fill_narrow_from_wide_spillandfill_kinds_reach_different_values) both useBPF_LDX|BPF_MEMSXinstructions (r2 = *(s32 *)(r10 - 8)), not MOVSX.
Quoted 8 lines
Other LDSX users in the suite gate on the LDSX feature - for instance,
verifier_ldsx.cchecks:(__clang_major__ >= 18 || defined(__BPF_FEATURE_LDSX))The two macros happen to align for clang >= 18 and gcc-bpf -mcpu=v4, but a compiler advertising MOVSX without LDSX would fail to build these programs rather than skipping them.
The bot is right, LDSX needs to be checked here.
I've introduced the macro in bpf_misc.h and used here as applicable.
There are some other in-tree users of this infra, but I'm holding off on converting them as have slightly different definition which I'd rather deal with separately outside of this series.
Quoted 76 lines
[ ... ]
Quoted 59 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +55
-0@@ -1129,6 +1211,68 @@ __naked void sext_kinds_reach_different_values(void) : __clobber_all); } +/* +* The sign-extending counterpart: the filled register is the sign extension of +* the slot's low 32 bits, so a narrowing of those bits arrives sign-extended. +*/ +SEC("socket") +__success +__naked void sext_fill_narrow_from_wide_spill (void ) +{ + asmvolatile (" \ +call %[bpf_get_prandom_u32]; \ +r6 = r0; \ +call %[bpf_get_prandom_u32]; \ +r0 <<= 32; \ +r6 |= r0; /* r6 = full 64-bit unknown */ \ +*(u64 *)(r10 - 8) = r6; /* slot linked to r6 */ \ +r2 = *(s32 *)(r10 - 8); /* narrowing sx fill */ \ +if w6 != -1 goto 1f; /* narrows r6, propagates to r2 */ \ +if r2 == -1 goto 1f; /* sign-extended, not 0xffffffff */ \ +r0 /= 0; \ +1: \ +r0 = 0; \ +exit; \ +" : + : __imm(bpf_get_prandom_u32) + : __clobber_all); +} + +/* +* The same, for the two fill kinds off one slot. +*/ +SEC("socket") +__failure __msg("div by zero") +__flag (BPF_F_TEST_STATE_FREQ) +__naked void fill_kinds_reach_different_values(void) +{ + asm volatile (" \ + call %[bpf_get_prandom_u32]; \ + r6 = r0; \ + r6 &= 1; \ + call %[bpf_get_prandom_u32]; \ + r8 = r0; \ + call %[bpf_get_prandom_u32]; \ + r0 <<= 32; \ + r8 |= r0; \ + *(u64 *)(r10 - 8) = r8; \ + if r6 >= 1 goto 2f; \ + r2 = *(s32 *)(r10 - 8); /* sign-extending fill */ \ + goto 1f; \ +2: \ + r2 = *(u32 *)(r10 - 8); /* zero-extending fill */ \ +1: \ + if w8 != -1 goto 3f; \ + if r2 == -1 goto 3f; /* only the sign-extending path */ \ + r0 /= 0; \ +3: \tools/testing/selftests/bpf/progs/verifier_linked_scalars.c __naked void sext_kinds_reach_different_values(void) · line 1278
Quoted 10 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +7
-0+ r0 =0 ; \ + exit; \ +" : + : __imm(bpf_get_prandom_u32) + : __clobber_all); +} +#endif /* CAN_USE_MOVSX */ char _license[] SEC("license") = "GPL";---
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.mdCI run summary: https://github.com/kernel-patches/bpf/actions/runs/34506184282
PATCH v2 11/13 bpf: record what a narrowing spill actually stores
In reply to Vineet GuptaA spill narrower than its source saves the register state untruncated:save_register_state() does
state->stack[spi].spilled_ptr = *reg;
and marks only @size bytes STACK_SPILL. So after
r6 = ... /* full 64-bit unknown */ *(u32 *)(r10 - 8) = r6; /* four bytes reach memory */
the slot claims to hold all of r6 while memory holds its low half. That is sound and the fill truncates later, but stacksafe() compares the slot through regsafe(), so the imprecision reaches state comparison.
Truncate the recorded state to the bytes stored. Nothing reads the slot as
wider: the remaining bytes are STACK_MISC, so a larger access fails the size <= spill_size test and never takes the register-fill path.
This is independent of linking -- it applies whether or not the source carries an id -- hence a patch of its own.
coerce_reg_to_size() moves up to be visible at the spill site, otherwise unchanged.
spill_subregs_preserve_stack_zero pins the old state and moves with it. It checks that STACK_ZERO bytes survive a subreg spill, which is unaffected; only the recorded scalar tightens.
---
v2: new.
kernel/bpf/verifier.c | 60 +++++++++++-------- .../selftests/bpf/progs/verifier_spill_fill.c | 10 +++- 2 files changed, 41 insertions(+), 29 deletions(-)
kernel/bpf/verifier.c +34 -26
@@ -3509,6 +3509,31 @@ static void assign_scalar_id_before_mov(struct bpf_verifier_env *env, src_reg->id = ++env->id_gen; } +static void coerce_reg_to_size (struct bpf_reg_state *reg,int size) +{ +u64 mask; + +/* clear high bits in bit representation */ + reg->var_off =tnum_cast (reg->var_off, size); + +/* fix arithmetic bounds */ + mask = ((u64 )1 << (size *8 )) -1 ; +if ((reg_umin (reg) & ~mask) == (reg_umax (reg) & ~mask)) +reg_set_urange64 (reg,reg_umin (reg) & mask,reg_umax (reg) & mask); +else +reg_set_urange64 (reg,0 , mask); + +/* +* If size is smaller than 32bit register the 32bit register +* values are also truncated so we push 64-bit bounds into +* 32-bit bounds. Above were truncated < 32-bits already. +*/ +if (size <4 ) +__mark_reg32_unbounded (reg); + +reg_bounds_sync (reg); +} + static void save_register_state(struct bpf_verifier_env *env, struct bpf_func_state *state, int spi, struct bpf_reg_state *reg,
@@ -3646,9 +3671,16 @@ static int check_stack_write_fixed_off(struct bpf_verifier_env *env,if (reg_value_fits)assign_scalar_id_before_mov (env, reg);save_register_state (env, state, spi, reg, size); -/* Break the relation on a narrowing spill. */ -if (!reg_value_fits) +if (!reg_value_fits) { +/* +* Only the low @size bytes reach memory, so record +* what the slot holds rather than the wider source +* it came from. +*/ +coerce_reg_to_size (&state->stack[spi].spilled_ptr, size); +/* Break the relation on a narrowing spill. */ clear_scalar_id (&state->stack[spi].spilled_ptr); + } }else if (!reg && !(off %BPF_REG_SIZE ) &&is_bpf_st_mem (insn) && env->bpf_capable) {struct bpf_reg_state *tmp_reg = &env->fake_reg[0 ];
@@ -5738,30 +5770,6 @@ static void sext_32_to_64(struct bpf_reg_state *reg)/* truncate register to smaller size (in bytes) * must be called with size < BPF_REG_SIZE */ -static void coerce_reg_to_size (struct bpf_reg_state *reg,int size) -{ -u64 mask; - -/* clear high bits in bit representation */ - reg->var_off =tnum_cast (reg->var_off, size); - -/* fix arithmetic bounds */ - mask = ((u64 )1 << (size *8 )) -1 ; -if ((reg_umin (reg) & ~mask) == (reg_umax (reg) & ~mask)) -reg_set_urange64 (reg,reg_umin (reg) & mask,reg_umax (reg) & mask); -else -reg_set_urange64 (reg,0 , mask); - -/* If size is smaller than 32bit register the 32bit register -* values are also truncated so we push 64-bit bounds into -* 32-bit bounds. Above were truncated < 32-bits already. -*/ -if (size <4 ) -__mark_reg32_unbounded (reg); - -reg_bounds_sync (reg); -} -static void set_sext64_default_val (struct bpf_reg_state *reg,int size) {if (size ==1 ) {
tools/testing/selftests/bpf/progs/verifier_spill_fill.c +7 -3
@@ -464,9 +464,13 @@ l0_%=: r1 >>= 16; \ SEC("raw_tp") __log_level(2) __success -__msg("fp-8=0m??scalar()") -__msg("fp-16=00mm??scalar()") -__msg("fp-24=00mm???scalar()") +/* + * The slot records what the store put there, not the wider source it came + * from, so each scalar is bounded by the size of its spill. + */ +__msg("fp-8=0m??scalar(smin=0,smax=umax=0xffffffff,var_off=(0x0; 0xffffffff))") +__msg("fp-16=00mm??scalar(smin=smin32=0,smax=umax=smax32=umax32=0xffff,var_off=(0x0; 0xffff))") +__msg("fp-24=00mm???scalar(smin=smin32=0,smax=umax=smax32=umax32=255,var_off=(0x0; 0xff))")__naked void spill_subregs_preserve_stack_zero (void ) { asm volatile (
Signature · 1 line
2.53.0-Meta
PATCH v2 12/13 bpf: track low-32 scalar equality across narrowing stack spills
In reply to Vineet GuptaA spill narrower than its source stores the source's low 32 bits, so the slot is their zero-extension -- the same relation a 32-bit mov records, in the store direction:
r6 = ... /* full 64-bit unknown */ *(u32 *)(r10 - 8) = r6; /* slot holds r6's low 32 bits */ r2 = *(u32 *)(r10 - 8); if w6 != 0 goto ... /* not taken: r6's low 32 bits are 0 */ if r2 == 0 goto ... /* not deduced today */
Record a low-32 link instead of dropping the relation. A store never sign-extends, so SUBREG_ZEXT is the only kind that arises here and no is_ldsx equivalent is needed.
This composes with the fill side rather than stacking on it. The previous patch left the slot recording exactly what memory holds, so its width is already within 32 bits and the fill sees an ordinary narrow source: the destination copies the slot's descriptor, staying one hop from the same base rather than becoming a link to a link.
spill_subregs_preserve_stack_zero picks up the id on its 4-byte spill. The 16- and 8-bit spills in the same program do not, which is the size gate
working: a link can only describe the low 32 bits.
---
v2: new, with 11/13.
kernel/bpf/verifier.c | 22 ++++++++++++++++--- .../selftests/bpf/progs/verifier_spill_fill.c | 2 +- 2 files changed, 20 insertions(+), 4 deletions(-)
kernel/bpf/verifier.c +19 -3
@@ -3665,10 +3665,19 @@ static int check_stack_write_fixed_off(struct bpf_verifier_env *env,mark_stack_slot_scratched (env, spi);if (reg && !(off %BPF_REG_SIZE ) && reg->type ==SCALAR_VALUE && env->bpf_capable) {bool reg_value_fits; +bool subreg_link; reg_value_fits =get_reg_width (reg) <=BITS_PER_BYTE * size; +/* +* A narrowing spill stores the low 32 bits of the source, so +* the slot is their zero-extension: record a low-32 link +* rather than dropping the relation, as a 32-bit mov does. +* A store never sign-extends, so there is only one kind here. +*/ + subreg_link = !reg_value_fits && size ==4 ; +/* Make sure that reg had an ID to build a relation on spill. */ -if (reg_value_fits) +if (reg_value_fits || subreg_link)assign_scalar_id_before_mov (env, reg);save_register_state (env, state, spi, reg, size);if (!reg_value_fits) {
@@ -3678,8 +3687,15 @@ static int check_stack_write_fixed_off(struct bpf_verifier_env *env,* it came from. */ coerce_reg_to_size (&state->stack[spi].spilled_ptr, size); -/* Break the relation on a narrowing spill. */ -clear_scalar_id (&state->stack[spi].spilled_ptr); +if (subreg_link && reg->id) + state->stack[spi].spilled_ptr.subreg =SUBREG_ZEXT ; +else +/* +* Nothing to relate: either the source has no +* id to share, or the store is narrower than +* the 32 bits a link can describe. +*/ +clear_scalar_id (&state->stack[spi].spilled_ptr); } }else if (!reg && !(off %BPF_REG_SIZE ) &&is_bpf_st_mem (insn) && env->bpf_capable) {
tools/testing/selftests/bpf/progs/verifier_spill_fill.c +1 -1
@@ -468,7 +468,7 @@ __success* The slot records what the store put there, not the wider source it came * from, so each scalar is bounded by the size of its spill. */ -__msg("fp-8=0m??scalar(smin=0,smax=umax=0xffffffff,var_off=(0x0; 0xffffffff))") +__msg("fp-8=0m??scalar(id={{[0-9]+}}.lo32,smin=0,smax=umax=0xffffffff,var_off=(0x0; 0xffffffff))") __msg("fp-16=00mm??scalar(smin=smin32=0,smax=umax=smax32=umax32=0xffff,var_off=(0x0; 0xffff))") __msg("fp-24=00mm???scalar(smin=smin32=0,smax=umax=smax32=umax32=255,var_off=(0x0; 0xff))")__naked void spill_subregs_preserve_stack_zero (void )
Signature · 1 line
2.53.0-Meta
[email protected]
AI reviewRe: [PATCH bpf-next v2 12/13] bpf: track low-32 scalar equality across narrowing stack spills
Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider: - [Critical] Sign-extending loads from 32-bit narrowing spills incorrectly inherit and preserve a…
Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
- [Critical] Sign-extending loads from 32-bit narrowing spills incorrectly inherit and preserve a SUBREG_ZEXT link, causing a critical discrepancy between verifier bounds and runtime values. --
commit 3396576ba1c56571ccd9a040716058594f558da8
Author: Vineet Gupta <[email protected]>
bpf: track low-32 scalar equality across narrowing stack spills
This commit allows the verifier to track a SUBREG_ZEXT relationship when a 64-bit scalar is narrowed during a 4-byte stack spill. This preserves the knowledge of the lower 32 bits for subsequent loads.
Quoted 4 lines
kernel/bpf/verifier.c +0
-0
[ ... ]
kernel/bpf/verifier.c static int check_stack_write_fixed_off(struct bpf_verifier_env *env, · line 3691
Quoted 8 lines
kernel/bpf/verifier.c +2
-2@@ -3678,8 +3687,15 @@ static int check_stack_write_fixed_off(struct bpf_verifier_env *env,* it came from. */ coerce_reg_to_size (&state->stack[spi].spilled_ptr, size); -/* Break the relation on a narrowing spill. */ -clear_scalar_id (&state->stack[spi].spilled_ptr); +if (subreg_link && reg->id) + state->stack[spi].spilled_ptr.subreg =SUBREG_ZEXT ;
[Severity: Critical]
Can this lead to verifier state corruption when the spilled value is later read with a 4-byte sign-extending load (BPF_MEMSX)?
If a BPF program performs 64-bit arithmetic to create an unknown scalar and spills it to the stack via a 4-byte narrowing store, it records a SUBREG_ZEXT link here and coerces its bounds to 32 bits.
If it then reads it back via a 4-byte sign-extending load, when processing the read in check_stack_read_fixed_off(), narrowing evaluates to false since the bounds were already truncated during the spill:
bool narrowing = get_reg_width(reg) > size * BITS_PER_BYTE;
As a result, subreg_link is false, and the verifier skips the is_ldsx ? SUBREG_SEXT : SUBREG_ZEXT correction logic. The destination register blindly inherits the stack slot's SUBREG_ZEXT link.
In check_mem_access(), coerce_reg_to_size_sx() properly sign-extends the loaded value's bounds, but because the subreg link is non-zero, it skips breaking the scalar ID:
if (!no_sext && !regs[value_regno].subreg) clear_scalar_id(®s[value_regno]);
The register now has sign-extended bounds but a SUBREG_ZEXT link to the original 64-bit scalar.
If the original scalar is later refined, sync_linked_regs() will invoke reconstruct_zext32(), completely overwriting the sign-extended bounds with zero-extended bounds. The verifier will incorrectly assume the register holds a positive value, while at runtime it holds a negative sign-extended value.
Does this permit arbitrary out-of-bounds kernel memory accesses?
Quoted 8 lines
kernel/bpf/verifier.c +7
-0+else +/* +* Nothing to relate: either the source has no +* id to share, or the store is narrower than +* the 32 bits a link can describe. +*/ +clear_scalar_id (&state->stack[spi].spilled_ptr); }
Signature · 1 line
Sashiko AI review · https://sashiko.dev/#/patchset/[email protected]?part=12
Re: [PATCH bpf-next v2 12/13] bpf: track low-32 scalar equality across narrowing stack spills
Quoted 54 lines · On 9/10/26 10:05 AM, [email protected] wrote:
Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
- [Critical] Sign-extending loads from 32-bit narrowing spills incorrectly inherit and preserve aSUBREG_ZEXTlink, causing a critical discrepancy between verifier bounds and runtime values. --commit
3396576ba1c56571ccd9a040716058594f558da8
Author: Vineet Gupta <[email protected]>bpf: track low-32 scalar equality across narrowing stack spills
This commit allows the verifier to track a
SUBREG_ZEXTrelationship when a 64-bit scalar is narrowed during a 4-byte stack spill. This preserves the knowledge of the lower 32 bits for subsequent loads.Quoted 4 lines
kernel/bpf/verifier.c +0
-0[ ... ]
kernel/bpf/verifier.c static int check_stack_write_fixed_off(struct bpf_verifier_env *env, · line 3691
Quoted 8 lines
kernel/bpf/verifier.c +2
-2@@ -3678,8 +3687,15 @@ static int check_stack_write_fixed_off(struct bpf_verifier_env *env,* it came from. */ coerce_reg_to_size (&state->stack[spi].spilled_ptr, size); -/* Break the relation on a narrowing spill. */ -clear_scalar_id (&state->stack[spi].spilled_ptr); +if (subreg_link && reg->id) + state->stack[spi].spilled_ptr.subreg =SUBREG_ZEXT ;[Severity: Critical]
Can this lead to verifier state corruption when the spilled value is later read with a 4-byte sign-extending load (BPF_MEMSX)?If a BPF program performs 64-bit arithmetic to create an unknown scalar and spills it to the stack via a 4-byte narrowing store, it records a
SUBREG_ZEXTlink here and coerces its bounds to 32 bits.If it then reads it back via a 4-byte sign-extending load, when processing the read in
check_stack_read_fixed_off(), narrowing evaluates to false since the bounds were already truncated during the spill:bool narrowing = get_reg_width(reg) > size * BITS_PER_BYTE;As a result,
subreg_linkis false, and the verifier skips theis_ldsx?SUBREG_SEXT:SUBREG_ZEXTcorrection logic. The destination register blindly inherits the stack slot'sSUBREG_ZEXTlink.In
check_mem_access(),coerce_reg_to_size_sx()properly sign-extends the loaded value's bounds, but because the subreg link is non-zero, it skips breaking the scalar ID:if (!no_sext && !regs[value_regno].subreg) clear_scalar_id(®s[value_regno]);The register now has sign-extended bounds but a
SUBREG_ZEXTlink to the original 64-bit scalar.
Quoted 6 lines
If the original scalar is later refined,
sync_linked_regs()will invokereconstruct_zext32(), completely overwriting the sign-extended bounds with zero-extended bounds. The verifier will incorrectly assume the register holds a positive value, while at runtime it holds a negative sign-extended value.Does this permit arbitrary out-of-bounds kernel memory accesses?
Yes there's a bug here. A narrowing spill records SUBREG_ZEXT, truncating the slot, and a later 4-byte ldsx has narrowing == false, inherits the slot's SUBREG_ZEXT leaving sign-extended bounds under a zero-extending link.
Fixed by making the sign-extension path drop any link that is not already SUBREG_SEXT:
- if (!no_sext && !regs[value_regno].subreg)
+ if (!no_sext && regs[value_regno].subreg != SUBREG_SEXT) clear_scalar_id(®s[value_regno]);
Also added a test to that effect.
Thx,
-Vineet
Quoted 9 lines
Quoted 9 lines
kernel/bpf/verifier.c +7
-0+else +/* +* Nothing to relate: either the source has no +* id to share, or the store is narrower than +* the 32 bits a link can describe. +*/ +clear_scalar_id (&state->stack[spi].spilled_ptr); }
PATCH v2 13/13 selftests/bpf: cover the low-32 link for narrowing stack spills
In reply to Vineet GuptaTwo programs:
- zext_narrowing_spill_keeps_link: a 32-bit spill of a wide register, filled back out, still follows a later narrowing of the source
- zext_narrowing_spill_byte_no_link: a 1-byte spill forms no link, since the relation is not expressible
---
v2: new, with 12/13.
.../bpf/progs/verifier_linked_scalars.c | 54 +++++++++++++++++++ 1 file changed, 54 insertions(+)
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +54 -0
@@ -1048,6 +1048,60 @@ __naked void zext_fill_byte_forms_no_link(void) : __clobber_all); } +/* +* A narrowing spill stores only the source's low 32 bits, so the slot is their +* zero-extension. A later narrowing of the source must still reach anything +* filled back out of that slot. +*/ +SEC("socket") +__success +__naked void zext_narrowing_spill_keeps_link (void ) +{ + asmvolatile (" \ +call %[bpf_get_prandom_u32]; \ +r6 = r0; \ +call %[bpf_get_prandom_u32]; \ +r0 <<= 32; \ +r6 |= r0; /* r6 = full 64-bit unknown */ \ +*(u32 *)(r10 - 8) = r6; /* narrowing spill, forms the link */ \ +r2 = *(u32 *)(r10 - 8); /* fill it back */ \ +if w6 != 0 goto 1f; /* narrows r6, propagates to r2 */ \ +if r2 == 0 goto 1f; \ +r0 /= 0; \ +1: \ +r0 = 0; \ +exit; \ +" : + : __imm(bpf_get_prandom_u32) + : __clobber_all); +} + +/* +* A sub-word spill is below the low-32 model, so no link is formed there. +*/ +SEC("socket") +__failure __msg("div by zero") +__naked void zext_narrowing_spill_byte_no_link(void) +{ + asmvolatile (" \ +call %[bpf_get_prandom_u32]; \ +r6 = r0; \ +call %[bpf_get_prandom_u32]; \ +r0 <<= 32; \ +r6 |= r0; \ +*(u8 *)(r10 - 8) = r6; /* 1-byte spill: no link */ \ +r2 = *(u8 *)(r10 - 8); \ +if w6 != 0 goto 1f; \ +if r2 == 0 goto 1f; /* not deduced */ \ +r0 /= 0; \ +1: \ +r0 = 0; \ +exit; \ +" : + : __imm(bpf_get_prandom_u32) + : __clobber_all); +} +#ifdef CAN_USE_MOVSX /*
Signature · 1 line
2.53.0-Meta