From mboxrd@z Thu Jan 1 00:00:00 1970 Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.remote-ip=91.218.175.224 ARC-Seal: i=1; d=subspace.kernel.org; s=arc20261015; a=rsa-sha256; cv=none; t=1792513249; b=AithEsayHegYjOojvXYobcQg01cQlDtpO7aV6fisGzh90SvgrbGh/FkULAj7UDjo2gqT A36p27FzkivJzZBA9620MZFFYcZEDMTUl7WCaK+HiYYHmngWqX1brL+xgBIHxgCwzXz4K 2hya0XYMWOCnRvQR//0SeEOAYyWKUsUN9uxyfAAbk7NDxTLK6vBiFh6kCnuzPy7HGGTo2 AqkhyLuLT/FViPEMFyl36dkXU6vM76ZkCpY3jDvvIJBQrNk+iPmk1ynhPFd3XDfdfthkV sbB+mgKJTNbww0oq73SgxwMMYyWzoL4Cvx/4aDT6BTcdFjX2ya+ymDNcr3E2QJxDVyA== ARC-Message-Signature: i=1; d=subspace.kernel.org; s=arc20261015; a=rsa-sha256; c=relaxed/relaxed; t=1792513249; h=DMARC-Filter:X-Envelope-To:DKIM-Signature:X-Envelope-To:Received: X-Mizu-Trace-ID:X-Migadu-Flow:From:To:Cc:Subject:Date:Message-ID: X-Mailer:In-Reply-To:References:MIME-Version: Content-Transfer-Encoding; bh=OC8vve1fiqKE1c9n/UcGr0mLlnRlWEjB+BSGAgi53F8=; b=U4/K2wy/oPfJGPPQWkRAmK2yMQtLlTetYfJkFg02wBnf7WtZ2Gb0ezbbSWL8pBQebx4j GxHo0DWX7jx7XK+Hbpd6auol3BMFqlyAj3VGqzvVu/+Mz8xJ7aVqtd8UL/jWMnuiIs/2X +KmbXC/e08xcddbse4K8rZq1vaqJCsj9PhjLJs8yCzF+I4XOmJ3FIF0WigWwOCGiJoZ3w WzIHoRZ0zmUef7eLC0PnyuH51v8CffNC9vh9uozO7hwl3jNGcoM4HHanne5uymAKMP3FD Ow7UUszAijyfN8X9zkJhT+uV5tdD3zu8Jc0MFM/2K37jPciqnoAqUYJ42VU7sV7tKxQ== ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass header.from=linux.dev; spf=pass smtp.mailfrom=linux.dev; dkim=pass header.d=linux.dev header.i=@linux.dev header.a=rsa-sha256 header.s=key1 header.b=MklqdjrH; arc=none smtp.remote-ip=91.218.175.224 Received: from mta0.migadu.com (out-224.mta0.migadu.com [91.218.175.224]) (using TLSv1.3 with cipher TLS_AES_128_GCM_SHA256 (128/128 bits) key-exchange X25519 server-signature ECDSA (prime256v1) server-digest SHA256) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id D14CF606A324 for ; Tue, 20 Oct 2026 16:20:48 +0000 (UTC) DMARC-Filter: OpenDMARC Filter v1.4.2 smtp.subspace.kernel.org D14CF606A324 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=linux.dev Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=linux.dev Authentication-Results: smtp.subspace.kernel.org; dkim=pass (1024-bit key, unprotected) header.d=linux.dev header.i=@linux.dev header.a=rsa-sha256 header.s=key1 header.b=MklqdjrH X-Envelope-To: linux-kernel@vger.kernel.org DKIM-Signature: a=rsa-sha256; bh=ZMLOfQ7Ig4uyCPp/b+t9vYpCNzduUcOXbnHFJaKcnwI=; c=simple/simple; d=linux.dev; h=from:to:subject:date:message-id:mime-version:content-type; s=key1; t=1792513247; v=1; x=1793118047; b=MklqdjrH3pJ30nPRmCyA7URieje4n0qLQeuCeHn1NvKry/Rg4sY/KXs5YrBMpo/nRWrm7bb6 LrVn7Hqqg4fVdlORFyYs0qb30bVp7bILoR242U+lYD3T7b0EKL6oq6552DOWcWeJLynu1oWF0uX hZAAsSEFIzP7BX8BRDK1nwYU= X-Envelope-To: linux-kernel@vger.kernel.org Received: by smtp.migadu.com with ESMTPS id 2e1b8357c1f15603; Tue, 20 Oct 2026 16:20:46 +0000 X-Mizu-Trace-ID: 2e1b8357c1f15603 X-Migadu-Flow: FLOW_OUT From: Vineet Gupta To: ast@kernel.org, daniel@iogearbox.net, andrii@kernel.org, eddyz87@gmail.com, memxor@gmail.com Cc: martin.lau@linux.dev, song@kernel.org, yonghong.song@linux.dev, jolsa@kernel.org, emil@etsalapatis.com, ihor.solodrai@linux.dev, john.fastabend@gmail.com, shuah@kernel.org, bpf@vger.kernel.org, linux-kernel@vger.kernel.org, linux-kselftest@vger.kernel.org, Vineet Gupta Subject: [PATCH bpf-next v3 11/12] [do not merge] bpf: Track low-32 scalar equality across narrowing stack spills Date: Tue, 20 Oct 2026 09:19:06 -0700 Message-ID: <20261020161907.2115379-12-vineet.gupta@linux.dev> X-Mailer: git-send-email 2.56.0 In-Reply-To: <20261020161907.2115379-1-vineet.gupta@linux.dev> References: <20261020161907.2115379-1-vineet.gupta@linux.dev> X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Post: List-Help: List-Subscribe: List-Unsubscribe: List-Owner: Precedence: list MIME-Version: 1.0 Content-Transfer-Encoding: 8bit A spill narrower than its source stores the source's low 32 bits, so the slot is their zero-extension -- the mov relation, in the store direction: r6 = ... /* full 64-bit unknown */ *(u32 *)(r10 - 8) = r6; /* slot holds r6's low 32 bits */ if w6 != 0 goto ... /* not taken: r6's low 32 bits are 0 */ r2 = *(u32 *)(r10 - 8); if r2 == 0 goto ... /* not deduced today */ A store never sign-extends, so BPF_REG_LINK_ZEXT is the only kind that arises. save_register_state() copies the source whole, including bounds for bits the store did not write, so the slot must be truncated before the kind goes on it -- otherwise the first sync_linked_regs() intersects the correctly rebuilt low half against those stale bounds and empties the slot. Only one order pays. sync_linked_regs() walks spilled slots, so narrowing while the value is still on the stack narrows the slot and the fill copies an already narrowed value. Filling first does not benefit: the fill is a mov, and a mov drops a zero-extending link. Posted, not proposed. This is the direction asked for, implemented and measured, and the measurement says do not take it. Against the ten patches before it, on 441 cilium/katran/fb/sched_ext objects, 1467 programs: verdicts no change at all total_insns 102 changed, 63 worse, +84,450 (+0.34%) +59,616 (+57.2%) 104,160 -> 163,776 test_file_open +19,784 (+89.7%) 22,053 -> 41,837 rusty_enqueue +2,688 (+40.6%) 6,626 -> 9,314 layered_enqueue total_states 64 changed, 63 worse Nothing is gained for it, and both selftest corpora hide it completely -- bpf-gcc shows no changed program at all. Nothing in tools/testing/selftests/bpf is shaped like a sched_ext scheduler. The mechanism, from rusty_enqueue's verifier log at the patch before this one and at this one. The walks are identical for 17,043 steps, then: before 1969: (c7) r6 s>>= 32 1970: safe <- pruned here after 1969: (c7) r6 s>>= 32 frame 0: propagating fp-24 <- not pruned One slot accounts for all of it. fp-24 is written by a narrowing spill 354 times in the walk, and "propagating fp-24" goes 0 -> 1034 while the other slots are unchanged. The slot itself goes from fp-24=ppppscalar() to fp-24=ppppscalar(id=11+0,smin=0,smax=umax=0xffffffff,...) An opaque scalar() matches every candidate state; one carrying an id, a kind and a range that sync_linked_regs() narrows further on each compare matches far fewer. Three things tighten at once: check_scalar_ids() returns true unconditionally for old_id == 0 and the slot now has an id; regsafe() gains two rejects that need a kind to be reachable; and bpf_bt_sync_linked_regs() makes precision all-or-nothing across a set, so marking any member precise now reaches the slot. rusty_enqueue uses the value as an array index, which forces mark_chain_precision constantly. That is the relation working as designed. Recording true information about a slot necessarily narrows its equivalence class, and a narrower class prunes against fewer predecessors. The narrowing-fill patch earlier in the series is the half that pays: the fill is where the value is wanted, and it is free on every corpus. Signed-off-by: Vineet Gupta --- v3: was v2 12/13, now tagged [do not merge]. - v2's 11/13, "bpf: record what a narrowing spill actually stores", is dropped: it cost big_alloc2 2956 -> 3095 insns for no verdict. - v2's worked example had the fill before the narrowing, which is the one order this link cannot serve. Replaced with the order that works. - the slot is truncated to the bits the store actually wrote before the kind goes on it, and inherits the source's delta. - NOT PROPOSED FOR MERGE. Against the ten patches before it, on 441 cilium/katran/fb/sched_ext objects: 102 programs changed, 63 worse, test_file_open +57% and rusty_enqueue +90%, for no verdict change anywhere. Both selftest corpora hide this completely -- bpf-gcc shows no changed program at all. The message carries the mechanism from the verifier log. kernel/bpf/verifier.c | 40 +++++++++++++++++-- .../selftests/bpf/progs/verifier_spill_fill.c | 6 ++- 2 files changed, 41 insertions(+), 5 deletions(-) diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index feefa5733fd7..3607c032df5f 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -222,6 +222,7 @@ static inline bool in_sleepable_context(struct bpf_verifier_env *env); static const char *non_sleepable_context_description(struct bpf_verifier_env *env); static void scalar32_min_max_add(struct bpf_reg_state *dst_reg, struct bpf_reg_state *src_reg); static void scalar_min_max_add(struct bpf_reg_state *dst_reg, struct bpf_reg_state *src_reg); +static void zext_32_to_64(struct bpf_reg_state *reg); static void bpf_map_ptr_store(struct bpf_insn_aux_data *aux, struct bpf_map *map, @@ -3908,15 +3909,46 @@ 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 link 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); - /* Break the relation on a narrowing spill. */ - if (!reg_value_fits) - bpf_clear_scalar_id(&ss->spilled_ptr); + if (!reg_value_fits) { + if (subreg_link && reg->id) { + /* + * save_register_state() copies the source + * whole, but the store only wrote its low 32 + * bits, so truncate to those before recording + * the kind: a slot asserting BPF_REG_LINK_ZEXT + * over the source's wider bounds is a register + * state that contradicts itself. + * + * Keep the source's delta, though: the slot + * holds (u32)(base + delta), so resetting it to + * 0 would record a relation off by that delta. + */ + zext_32_to_64(&ss->spilled_ptr); + ss->spilled_ptr.link_kind = BPF_REG_LINK_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. + */ + bpf_clear_scalar_id(&ss->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]; diff --git a/tools/testing/selftests/bpf/progs/verifier_spill_fill.c b/tools/testing/selftests/bpf/progs/verifier_spill_fill.c index 4d1374885f6d..081b0fe0d70a 100644 --- a/tools/testing/selftests/bpf/progs/verifier_spill_fill.c +++ b/tools/testing/selftests/bpf/progs/verifier_spill_fill.c @@ -464,7 +464,11 @@ l0_%=: r1 >>= 16; \ SEC("raw_tp") __log_level(2) __success -__msg("fp-8=0m??scalar()") +/* + * The 4-byte spill carries the low-32 link, and the slot is truncated to + * the bits the store wrote; the narrower spills do neither. + */ +__msg("fp-8=0m??scalar(id={{[0-9]+}}+0,smin=0,smax=umax=0xffffffff,var_off=(0x0; 0xffffffff))") __msg("fp-16=00mm??scalar()") __msg("fp-24=00mm???scalar()") __naked void spill_subregs_preserve_stack_zero(void) -- 2.53.0-Meta