From: Yonghong Song <yhs@fb.com>
To: <ast@fb.com>, <daniel@iogearbox.net>, <netdev@vger.kernel.org>
Cc: <kernel-team@fb.com>
Subject: [PATCH bpf-next v3 4/9] bpf/verifier: improve register value range tracking with ARSH
Date: Fri, 20 Apr 2018 15:18:37 -0700 [thread overview]
Message-ID: <20180420221842.742330-5-yhs@fb.com> (raw)
In-Reply-To: <20180420221842.742330-1-yhs@fb.com>
When helpers like bpf_get_stack returns an int value
and later on used for arithmetic computation, the LSH and ARSH
operations are often required to get proper sign extension into
64-bit. For example, without this patch:
54: R0=inv(id=0,umax_value=800)
54: (bf) r8 = r0
55: R0=inv(id=0,umax_value=800) R8_w=inv(id=0,umax_value=800)
55: (67) r8 <<= 32
56: R8_w=inv(id=0,umax_value=3435973836800,var_off=(0x0; 0x3ff00000000))
56: (c7) r8 s>>= 32
57: R8=inv(id=0)
With this patch:
54: R0=inv(id=0,umax_value=800)
54: (bf) r8 = r0
55: R0=inv(id=0,umax_value=800) R8_w=inv(id=0,umax_value=800)
55: (67) r8 <<= 32
56: R8_w=inv(id=0,umax_value=3435973836800,var_off=(0x0; 0x3ff00000000))
56: (c7) r8 s>>= 32
57: R8=inv(id=0, umax_value=800,var_off=(0x0; 0x3ff))
With better range of "R8", later on when "R8" is added to other register,
e.g., a map pointer or scalar-value register, the better register
range can be derived and verifier failure may be avoided.
In our later example,
......
usize = bpf_get_stack(ctx, raw_data, max_len, BPF_F_USER_STACK);
if (usize < 0)
return 0;
ksize = bpf_get_stack(ctx, raw_data + usize, max_len - usize, 0);
......
Without improving ARSH value range tracking, the register representing
"max_len - usize" will have smin_value equal to S64_MIN and will be
rejected by verifier.
Signed-off-by: Yonghong Song <yhs@fb.com>
---
kernel/bpf/verifier.c | 26 ++++++++++++++++++++++++++
1 file changed, 26 insertions(+)
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 3c8bb92..01c215d 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -2975,6 +2975,32 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
/* We may learn something more from the var_off */
__update_reg_bounds(dst_reg);
break;
+ case BPF_ARSH:
+ if (umax_val >= insn_bitness) {
+ /* Shifts greater than 31 or 63 are undefined.
+ * This includes shifts by a negative number.
+ */
+ mark_reg_unknown(env, regs, insn->dst_reg);
+ break;
+ }
+ if (dst_reg->smin_value < 0)
+ dst_reg->smin_value >>= umin_val;
+ else
+ dst_reg->smin_value >>= umax_val;
+ if (dst_reg->smax_value < 0)
+ dst_reg->smax_value >>= umax_val;
+ else
+ dst_reg->smax_value >>= umin_val;
+ if (src_known)
+ dst_reg->var_off = tnum_rshift(dst_reg->var_off,
+ umin_val);
+ else
+ dst_reg->var_off = tnum_rshift(tnum_unknown, umin_val);
+ dst_reg->umin_value >>= umax_val;
+ dst_reg->umax_value >>= umin_val;
+ /* We may learn something more from the var_off */
+ __update_reg_bounds(dst_reg);
+ break;
default:
mark_reg_unknown(env, regs, insn->dst_reg);
break;
--
2.9.5
next prev parent reply other threads:[~2018-04-20 22:22 UTC|newest]
Thread overview: 24+ messages / expand[flat|nested] mbox.gz Atom feed top
2018-04-20 22:18 [PATCH bpf-next v3 0/9] bpf: add bpf_get_stack helper Yonghong Song
2018-04-20 22:18 ` [PATCH bpf-next v3 1/9] bpf: change prototype for stack_map_get_build_id_offset Yonghong Song
2018-04-20 22:18 ` [PATCH bpf-next v3 2/9] bpf: add bpf_get_stack helper Yonghong Song
2018-04-20 22:18 ` [PATCH bpf-next v3 3/9] bpf/verifier: refine retval R0 state for " Yonghong Song
2018-04-22 23:55 ` Alexei Starovoitov
2018-04-23 2:46 ` Yonghong Song
2018-04-20 22:18 ` Yonghong Song [this message]
2018-04-23 0:16 ` [PATCH bpf-next v3 4/9] bpf/verifier: improve register value range tracking with ARSH Alexei Starovoitov
2018-04-23 2:49 ` Yonghong Song
2018-04-23 4:19 ` Alexei Starovoitov
2018-04-23 4:31 ` Yonghong Song
2018-04-23 4:40 ` Alexei Starovoitov
2018-04-23 12:25 ` Edward Cree
2018-04-23 16:19 ` Yonghong Song
2018-04-20 22:18 ` [PATCH bpf-next v3 5/9] tools/bpf: add bpf_get_stack helper to tools headers Yonghong Song
2018-04-20 22:18 ` [PATCH bpf-next v3 6/9] samples/bpf: move common-purpose trace functions to selftests Yonghong Song
2018-04-23 0:17 ` Alexei Starovoitov
2018-04-20 22:18 ` [PATCH bpf-next v3 7/9] tools/bpf: add a verifier test case for bpf_get_stack helper and ARSH Yonghong Song
2018-04-20 22:18 ` [PATCH bpf-next v3 8/9] tools/bpf: add a test for bpf_get_stack with raw tracepoint prog Yonghong Song
2018-04-23 0:23 ` Alexei Starovoitov
2018-04-23 2:57 ` Yonghong Song
2018-04-20 22:18 ` [PATCH bpf-next v3 9/9] tools/bpf: add a test for bpf_get_stack with " Yonghong Song
2018-04-23 0:27 ` Alexei Starovoitov
2018-04-23 2:58 ` Yonghong Song
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=20180420221842.742330-5-yhs@fb.com \
--to=yhs@fb.com \
--cc=ast@fb.com \
--cc=daniel@iogearbox.net \
--cc=kernel-team@fb.com \
--cc=netdev@vger.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 an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.