From: Andrii Nakryiko <andrii@kernel.org>
To: <bpf@vger.kernel.org>, <ast@kernel.org>, <daniel@iogearbox.net>,
<martin.lau@kernel.org>
Cc: <andrii@kernel.org>, <kernel-team@meta.com>
Subject: [PATCH v2 bpf-next 1/7] bpf: improve JEQ/JNE branch taken logic
Date: Wed, 18 Oct 2023 21:23:59 -0700 [thread overview]
Message-ID: <20231019042405.2971130-2-andrii@kernel.org> (raw)
In-Reply-To: <20231019042405.2971130-1-andrii@kernel.org>
When determining if if/else branch will always or never be taken, use
signed range knowledge in addition to currently used unsigned range knowledge.
If either signed or unsigned range suggests that condition is
always/never taken, return corresponding branch_taken verdict.
Current use of unsigned range for this seems arbitrary and unnecessarily
incomplete. It is possible for *signed* operations to be performed on
register, which could "invalidate" unsigned range for that register. In
such case branch_taken will be artificially useless, even if we can
still tell that some constant is outside of register value range based
on its signed bounds.
veristat-based validation shows zero differences across selftests,
Cilium, and Meta-internal BPF object files.
Signed-off-by: Andrii Nakryiko <andrii@kernel.org>
---
kernel/bpf/verifier.c | 8 ++++++++
1 file changed, 8 insertions(+)
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index bb58987e4844..c87144e3c5e8 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -13663,12 +13663,16 @@ static int is_branch32_taken(struct bpf_reg_state *reg, u32 val, u8 opcode)
return !!tnum_equals_const(subreg, val);
else if (val < reg->u32_min_value || val > reg->u32_max_value)
return 0;
+ else if (sval < reg->s32_min_value || sval > reg->s32_max_value)
+ return 0;
break;
case BPF_JNE:
if (tnum_is_const(subreg))
return !tnum_equals_const(subreg, val);
else if (val < reg->u32_min_value || val > reg->u32_max_value)
return 1;
+ else if (sval < reg->s32_min_value || sval > reg->s32_max_value)
+ return 1;
break;
case BPF_JSET:
if ((~subreg.mask & subreg.value) & val)
@@ -13740,12 +13744,16 @@ static int is_branch64_taken(struct bpf_reg_state *reg, u64 val, u8 opcode)
return !!tnum_equals_const(reg->var_off, val);
else if (val < reg->umin_value || val > reg->umax_value)
return 0;
+ else if (sval < reg->smin_value || sval > reg->smax_value)
+ return 0;
break;
case BPF_JNE:
if (tnum_is_const(reg->var_off))
return !tnum_equals_const(reg->var_off, val);
else if (val < reg->umin_value || val > reg->umax_value)
return 1;
+ else if (sval < reg->smin_value || sval > reg->smax_value)
+ return 1;
break;
case BPF_JSET:
if ((~reg->var_off.mask & reg->var_off.value) & val)
--
2.34.1
next prev parent reply other threads:[~2023-10-19 4:24 UTC|newest]
Thread overview: 25+ messages / expand[flat|nested] mbox.gz Atom feed top
2023-10-19 4:23 [PATCH v2 bpf-next 0/7] BPF register bounds logic and testing improvements Andrii Nakryiko
2023-10-19 4:23 ` Andrii Nakryiko [this message]
2023-10-19 4:24 ` [PATCH v2 bpf-next 2/7] bpf: derive smin/smax from umin/max bounds Andrii Nakryiko
2023-10-19 4:24 ` [PATCH v2 bpf-next 3/7] bpf: enhance subregister bounds deduction logic Andrii Nakryiko
2023-10-19 4:24 ` [PATCH v2 bpf-next 4/7] bpf: improve deduction of 64-bit bounds from 32-bit bounds Andrii Nakryiko
2023-10-19 4:24 ` [PATCH v2 bpf-next 5/7] bpf: try harder to deduce register bounds from different numeric domains Andrii Nakryiko
2023-10-19 4:24 ` [PATCH v2 bpf-next 6/7] bpf: drop knowledge-losing __reg_combine_{32,64}_into_{64,32} logic Andrii Nakryiko
2023-10-19 4:24 ` [PATCH v2 bpf-next 7/7] selftests/bpf: BPF register range bounds tester Andrii Nakryiko
2023-10-19 7:08 ` kernel test robot
2023-10-19 18:27 ` Andrii Nakryiko
2023-10-19 7:30 ` Shung-Hsi Yu
2023-10-19 7:52 ` Shung-Hsi Yu
2023-10-19 18:34 ` Andrii Nakryiko
2023-10-20 17:37 ` Srinivas Narayana Ganapathy
2023-10-22 4:42 ` Andrii Nakryiko
2023-10-23 14:05 ` Shung-Hsi Yu
2023-10-23 15:52 ` Paul Chaignon
2023-10-23 22:50 ` Andrii Nakryiko
2023-10-24 5:51 ` Andrii Nakryiko
2023-10-24 21:26 ` Paul Chaignon
2023-10-26 22:47 ` Andrii Nakryiko
2023-10-19 18:31 ` Andrii Nakryiko
2023-10-20 12:27 ` Shung-Hsi Yu
2023-10-21 4:13 ` [PATCH v2 bpf-next 0/7] BPF register bounds logic and testing improvements John Fastabend
2023-10-22 4:32 ` Andrii Nakryiko
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=20231019042405.2971130-2-andrii@kernel.org \
--to=andrii@kernel.org \
--cc=ast@kernel.org \
--cc=bpf@vger.kernel.org \
--cc=daniel@iogearbox.net \
--cc=kernel-team@meta.com \
--cc=martin.lau@kernel.org \
/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).