From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mail-wr1-f41.google.com (mail-wr1-f41.google.com [209.85.221.41]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id C766A346FB5 for ; Thu, 16 Apr 2026 13:45:56 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.221.41 ARC-Seal:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1776347158; cv=none; b=Aedmpl5ZfOBx6AwAHQAjYBFf9BkUBt12XzlB/48Shbh5y7iok7lxhqaOf37N+CIcdNY6gVkfA7P30SWkqAvDVHrqIligdKAUxQHInqeWram30Lqd1b93q0Y4SZP4tUVk84OY2to+EQuLOmxETf/YHG2Pn5eDJALNnLkwQ36uOPI= ARC-Message-Signature:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1776347158; c=relaxed/simple; bh=AA3dYvEohTXQUKP6EJOqKNKoIOc/IKK73N0SYnPofU8=; h=Date:From:To:Cc:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=HBg/JyUPLhkxN1DBwiAvjjdMsNOmCm5nrwfiqO5lBdi76KYesszg4Quwg/vYIXNDRM8sOf7fJkKc8yOYPS9mZ2/vJNX3pFBTzVsPqMdATQnkNlKGPJdTmfOBptPfaOmqytrTQUs7NEESR23lDzGMzyAV0XMfq4YQok2bWcuBpgA= ARC-Authentication-Results:i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=jzEiXA2y; arc=none smtp.client-ip=209.85.221.41 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="jzEiXA2y" Received: by mail-wr1-f41.google.com with SMTP id ffacd0b85a97d-43d0deb7ad5so6284179f8f.2 for ; Thu, 16 Apr 2026 06:45:56 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20251104; t=1776347155; x=1776951955; darn=vger.kernel.org; h=in-reply-to:content-transfer-encoding:content-disposition :mime-version:references:message-id:subject:cc:to:from:date:from:to :cc:subject:date:message-id:reply-to; bh=issAxQOvx3MyYsIUEl9HbrPW5aCoSwdHCKMlz9FgfpQ=; b=jzEiXA2yY0cKViVUCo/7im3vg6yAZVAcTDdPizN3vqi4IUx6eYkhNGIFbkfOJ4mbUr MgZa3hEsIUar5jsTWZVgSF91gHNVA0ciAXVGBpJdu0pI1PSM5r1hViREkFLyk2uHVC6f 5NnOx9z0tnQ+DKGcBAIJ1itdBOXO2+ZVOgHMhyiIfHRghuja08ovvk5V+v6mstADp0f2 jlvLYRcTVnsLKEcuYaPZJwTUrGuLIc8MfhUbeoP3DNlI9qbBsIonwKF2w8RwV9jK9i0a 12HJecbAhzGlONKcoRnPhtzjJJO0sZvC2CFgryJ/6zoXErh6bsdVVRNp5QyNqyOLoXNA sgTg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20251104; t=1776347155; x=1776951955; h=in-reply-to:content-transfer-encoding:content-disposition :mime-version:references:message-id:subject:cc:to:from:date:x-gm-gg :x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=issAxQOvx3MyYsIUEl9HbrPW5aCoSwdHCKMlz9FgfpQ=; b=PVuRLGwz7D4jtkHJJQTrgIjh0wUGtEoo783z/n0YVR00qCxYzWM3Tq7dpVmymNrsQX cFvcxg/T1rxIE2jb4zhzBudoN0XHipKEYlU0nDS8KzFLaUcT0KdhR9xellLVeE3f57fr HL1FwN+KmAFJH0pieRHN4/Z28wzArPxRS9cXgGhurw6XPskmVwLhclSFnSH8ihcJY8aY dDrdIBI/QnirHUtxF09vqlryoMB/a7ol272tF3EjyQKkUl+ovjfvF41p6XTjImXaB4rl khSQ3jWrZgxO2M7ZBaG/nf9fNGQ6yv3hgJf9OfC2K7Gb4lBPQJO0e0V8HCr16zvHuTeh 3GoA== X-Forwarded-Encrypted: i=1; AFNElJ+gDIZFWZJZ5f2w24WfxOaZ3hOx/DogNDbjtz1DSu0XpwzLFKg8A+xyv9NrzcowmubgXSivTzdIwFs8KII=@vger.kernel.org X-Gm-Message-State: AOJu0YwafPYnDdukPf6mEKsxHkZ/mUwXH4+nWAMsxi2Fv/EvBZEvHb12 kJ1WgzDg3B/a7LwTVmzCkGohZn525UqqyHaGr6UwRFsWZWv4ZKYng4fb X-Gm-Gg: AeBDievs2ED2Fz5nb6c4i5s56PfHAYZ+o/GQKMtyopPJe7luCIZLQv+wWElhEArbuxk G7cLCuJdRGc6gOBFBo8KkVm4U9xgjUJGYlN6nTf7WU4OHZbSKG9phxP1lovgN3kqO5xcoTxls5f dFMeGhIgAlK3XDtTlM7WrGoRUWTU4C8HCDIeTMEGbYE0dPYtpDPV6Q4szB8IjoIMd/gysRbYzBs PvA8EDtEsQxjH9YT1M+AQXwlnS/3ahU1quB5yc/ziJaUchfivSRF7LMGi6Wjn++nKaiCL6tq6Ls Ua4yzIRUqqOJnocIEP4KlztfWrzKSrkinNTLsjw/UlzdWaXdhv1+tcJ+nWs+mb8O8y4VD6tPgCo V48+FeQ4l/cF3M1oNkZBMOX0gneD0lLE8H9TJm/yzb0MZnFOwZkACeDlgpOkvUzwdM20f4jO1dH r64Q1e8V6+KF5qPB2HMegG68tP6G/iP2s+rHQG47jxcETIkX8W2W2nDAseA3dK6/Q5LMCSubw2X hhn517h6cuT4ULckmoP8yJMIzGocflFQVNi/k3VVJWmDAg9ZbvxldaHGIDI+jl1wS2M7RsEXF3I nzMRLnPKgmppu2tTDvkjlJwVpkZExvBhegQX5HDXnt8h0CaeBSbO X-Received: by 2002:a5d:5f90:0:b0:43d:309b:9c4f with SMTP id ffacd0b85a97d-43d64235d55mr40902724f8f.6.1776347154995; Thu, 16 Apr 2026 06:45:54 -0700 (PDT) Received: from mail.gmail.com (2a01cb0889497e00b55a04a9836ebec0.ipv6.abo.wanadoo.fr. [2a01:cb08:8949:7e00:b55a:4a9:836e:bec0]) by smtp.gmail.com with ESMTPSA id ffacd0b85a97d-43ead33d518sm14121747f8f.6.2026.04.16.06.45.53 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 16 Apr 2026 06:45:54 -0700 (PDT) Date: Thu, 16 Apr 2026 15:45:52 +0200 From: Paul Chaignon To: Eduard Zingerman Cc: Shung-Hsi Yu , Helen Koike , harishankar.vishwanathan@gmail.com, andrii@kernel.org, yonghong.song@linux.dev, ast@kernel.org, bpf@vger.kernel.org, linux-kernel@vger.kernel.org, kernel-dev@igalia.com Subject: Re: [PATCH 1/2] bpf: deduce_bounds_64_from_32 tightening with circular range logic Message-ID: References: <20260410124035.297632-1-koike@igalia.com> <16990d86263fb24079e6f0b476a8854ec2366932.camel@gmail.com> <7tgaeg4mpuoage626jaxu6sl6yht2ace4saog7yyx33pope7xk@kixri3atcb5q> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Disposition: inline Content-Transfer-Encoding: 8bit In-Reply-To: On Thu, Apr 16, 2026 at 12:43:44AM -0700, Eduard Zingerman wrote: > On Thu, 2026-04-16 at 11:52 +0800, Shung-Hsi Yu wrote: > > On Wed, Apr 15, 2026 at 12:12:45AM -0700, Eduard Zingerman wrote: > > > On Fri, 2026-04-10 at 09:40 -0300, Helen Koike wrote: > > > > Unify handling of signed and unsigned using circular range logic. > > [...] > > > Hi Helen, Harishankar, Shung-Hsi, Paul, > > > > > > I think this algorithm is correct and covers all cases discussed earlier. > > > I also prepared simple correctness check using cbmc in [1]. > > > > Given the "Fix invariant violations and improve branch detection" is > > merged and the original Syzkaller reproducer no longer triggers an issue, > > teaching the verfier how to do better bound deduction (i.e., precision > > improvement) seems less appealing than before, unless: > > There is only so much information that can be gained from 32->64 > tightening. I think this patch-set makes such tightening as precise as > it can be. Which is a nice property, hence I'd like to proceed merging > it. I've sent a patch [1] that might be addressing the same gaps in deduce_bounds_64_from_32() (outside of the s32 case maybe?). At least, the selftests introduced here pass with that patch as well. It doesn't require cnums and looks a bit easier to follow IMO. I wrote it while trying to fix the reg_bounds selftests and only noticed yesterday that it might be overlapping with this. cnums probably have other benefits, but maybe they're not needed to address the issues identified here? 1: https://lore.kernel.org/bpf/b2a0346a5b0818008503b721c62621918d84ad0a.1776344897.git.paul.chaignon@gmail.com/ > > > 1. LLVM produced program show similar pattern and was rejected by the > >    verifier, which will be fixed by this patchset > > 2. We're proceeding with cnum RFC as a whole, and this marks the first > >    step (I am assuming this is the case?) > > This is likely, I'm about to share the RFC. > > > My understanding is that we just need the verifier to be smart enough > > to accept safe LLVM-generated program, where as Syzkaller-generated one > > is not as much of a concern if it does not causes any issue. cnum > > improvement make sense because it simplifies the code, and could > > potentially be the last time we have to touch 32->64 deduction (famous > > last word). > > > > Shung-Hsi > > > > [...]