From: Edward Cree <ecree@solarflare.com>
To: Alexei Starovoitov <alexei.starovoitov@gmail.com>,
John Fastabend <john.fastabend@gmail.com>
Cc: <yhs@fb.com>, <daniel@iogearbox.net>, <netdev@vger.kernel.org>,
<bpf@vger.kernel.org>
Subject: Re: [RFC PATCH 2/4] bpf: verifier, do explicit u32 bounds tracking
Date: Tue, 10 Mar 2020 17:12:31 +0000 [thread overview]
Message-ID: <3f80b587-c5b0-0446-8cbc-eff1758496e9@solarflare.com> (raw)
In-Reply-To: <20200309235828.wldukb66bdwy2dzd@ast-mbp>
On 09/03/2020 23:58, Alexei Starovoitov wrote:> Thinking about it differently... var_off is a bit representation of
> 64-bit register. So that bit representation doesn't really have
> 32 or 16-bit chunks. It's a full 64-bit register. I think all alu32
> and jmp32 ops can update var_off without losing information.
Agreed; AFAICT the 32-bit var_off should always just be the bottom
32 bits of the full var_off.
In fact, it seems like the only situations where 32-bit bounds are
needed are (a) the high and low halves of a 64-bit register are
being used separately, so e.g. r0 = (x << 32) | y with small known
bounds on y you want to track, or (b) 32-bit signed arithmetic.
(a) doesn't seem like it's in scope to be supported, and (b) should
(I'm naïvely imagining) only need the s32 bounds, not the u32 or
var32.
John Fastabend wrote:
> For example, BPF_ADD will do a tnum_add() this is a different
> operation when overflows happen compared to tnum32_add(). Simply
> truncating tnum_add result to 32-bits is not the same operation.
I don't see why. Overflows from the low (tracked) 32 bits can only
affect the high 32. Truncation should be a homomorphism from
Z_2^n to Z_2^m wrt. both addition and multiplication, and tnums
are just (a particular class of) subsets of those rings.
Can you construct an example of a tnum addition that breaks the
homomorphism?
-ed
next prev parent reply other threads:[~2020-03-10 17:12 UTC|newest]
Thread overview: 14+ messages / expand[flat|nested] mbox.gz Atom feed top
2020-03-07 0:10 [RFC bpf PATCH 0/4] rfc for 32-bit subreg verifier tracking John Fastabend
2020-03-07 0:10 ` [RFC PATCH 1/4] bpf: verifer, refactor adjust_scalar_min_max_vals John Fastabend
2020-03-07 0:11 ` [RFC PATCH 2/4] bpf: verifier, do explicit u32 bounds tracking John Fastabend
2020-03-07 0:22 ` John Fastabend
2020-03-09 5:39 ` Yonghong Song
2020-03-09 23:58 ` Alexei Starovoitov
2020-03-10 17:04 ` John Fastabend
2020-03-10 17:12 ` Edward Cree [this message]
2020-03-10 19:24 ` John Fastabend
2020-03-10 19:41 ` Edward Cree
2020-03-10 17:52 ` Yonghong Song
2020-03-10 19:54 ` John Fastabend
2020-03-07 0:11 ` [RFC PATCH 3/4] bpf: verifier, do_refine_retval_range may clamp umin to 0 incorrectly John Fastabend
2020-03-07 0:11 ` [RFC PATCH 4/4] bpf: selftests, bpf_get_stack return value add <0 John Fastabend
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=3f80b587-c5b0-0446-8cbc-eff1758496e9@solarflare.com \
--to=ecree@solarflare.com \
--cc=alexei.starovoitov@gmail.com \
--cc=bpf@vger.kernel.org \
--cc=daniel@iogearbox.net \
--cc=john.fastabend@gmail.com \
--cc=netdev@vger.kernel.org \
--cc=yhs@fb.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).