netdev.vger.kernel.org archive mirror
 help / color / mirror / Atom feed
From: Alexei Starovoitov <ast@kernel.org>
To: <davem@davemloft.net>
Cc: <daniel@iogearbox.net>, <netdev@vger.kernel.org>,
	<bpf@vger.kernel.org>, <kernel-team@fb.com>
Subject: [PATCH v3 bpf-next 5/9] bpf: fix callees pruning callers
Date: Sat, 15 Jun 2019 12:12:21 -0700	[thread overview]
Message-ID: <20190615191225.2409862-6-ast@kernel.org> (raw)
In-Reply-To: <20190615191225.2409862-1-ast@kernel.org>

The commit 7640ead93924 partially resolved the issue of callees
incorrectly pruning the callers.
With introduction of bounded loops and jmps_processed heuristic
single verifier state may contain multiple branches and calls.
It's possible that new verifier state (for future pruning) will be
allocated inside callee. Then callee will exit (still within the same
verifier state). It will go back to the caller and there R6-R9 registers
will be read and will trigger mark_reg_read. But the reg->live for all frames
but the top frame is not set to LIVE_NONE. Hence mark_reg_read will fail
to propagate liveness into parent and future walking will incorrectly
conclude that the states are equivalent because LIVE_READ is not set.
In other words the rule for parent/live should be:
whenever register parentage chain is set the reg->live should be set to LIVE_NONE.
is_state_visited logic already follows this rule for spilled registers.

Fixes: 7640ead93924 ("bpf: verifier: make sure callees don't prune with caller differences")
Fixes: f4d7e40a5b71 ("bpf: introduce function calls (verification)")
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
---
 kernel/bpf/verifier.c | 11 ++++++-----
 1 file changed, 6 insertions(+), 5 deletions(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 25baa3c8cdd2..870c8f19ce80 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -6834,17 +6834,18 @@ static int is_state_visited(struct bpf_verifier_env *env, int insn_idx)
 	 * the state of the call instruction (with WRITTEN set), and r0 comes
 	 * from callee with its full parentage chain, anyway.
 	 */
-	for (j = 0; j <= cur->curframe; j++)
-		for (i = j < cur->curframe ? BPF_REG_6 : 0; i < BPF_REG_FP; i++)
-			cur->frame[j]->regs[i].parent = &new->frame[j]->regs[i];
 	/* clear write marks in current state: the writes we did are not writes
 	 * our child did, so they don't screen off its reads from us.
 	 * (There are no read marks in current state, because reads always mark
 	 * their parent and current state never has children yet.  Only
 	 * explored_states can get read marks.)
 	 */
-	for (i = 0; i < BPF_REG_FP; i++)
-		cur->frame[cur->curframe]->regs[i].live = REG_LIVE_NONE;
+	for (j = 0; j <= cur->curframe; j++) {
+		for (i = j < cur->curframe ? BPF_REG_6 : 0; i < BPF_REG_FP; i++)
+			cur->frame[j]->regs[i].parent = &new->frame[j]->regs[i];
+		for (i = 0; i < BPF_REG_FP; i++)
+			cur->frame[j]->regs[i].live = REG_LIVE_NONE;
+	}
 
 	/* all stack frames are accessible from callee, clear them all */
 	for (j = 0; j <= cur->curframe; j++) {
-- 
2.20.0


  parent reply	other threads:[~2019-06-15 19:12 UTC|newest]

Thread overview: 22+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2019-06-15 19:12 [PATCH v3 bpf-next 0/9] bpf: bounded loops and other features Alexei Starovoitov
2019-06-15 19:12 ` [PATCH v3 bpf-next 1/9] bpf: track spill/fill of constants Alexei Starovoitov
2019-06-20  0:24   ` John Fastabend
2019-06-20  3:35     ` Alexei Starovoitov
2019-06-20  5:04       ` John Fastabend
2019-06-20 15:37         ` Alexei Starovoitov
2019-06-15 19:12 ` [PATCH v3 bpf-next 2/9] selftests/bpf: fix tests due to const spill/fill Alexei Starovoitov
2019-06-20  5:40   ` John Fastabend
2019-06-15 19:12 ` [PATCH v3 bpf-next 3/9] bpf: extend is_branch_taken to registers Alexei Starovoitov
2019-06-20  6:01   ` John Fastabend
2019-06-15 19:12 ` [PATCH v3 bpf-next 4/9] bpf: introduce bounded loops Alexei Starovoitov
2019-06-20  9:59   ` [bpf] 9fe4f05d33: kernel_selftests.bpf.test_verifier.fail kernel test robot
2019-06-15 19:12 ` Alexei Starovoitov [this message]
2019-06-15 19:12 ` [PATCH v3 bpf-next 6/9] selftests/bpf: fix tests Alexei Starovoitov
2019-06-15 19:12 ` [PATCH v3 bpf-next 7/9] selftests/bpf: add basic verifier tests for loops Alexei Starovoitov
2019-06-15 19:12 ` [PATCH v3 bpf-next 8/9] selftests/bpf: add realistic loop tests Alexei Starovoitov
2019-06-15 19:12 ` [PATCH v3 bpf-next 9/9] bpf: precise scalar_value tracking Alexei Starovoitov
2019-06-17 17:20   ` Andrii Nakryiko
2019-06-17 16:39 ` [PATCH v3 bpf-next 0/9] bpf: bounded loops and other features Andrii Nakryiko
2019-06-17 18:57   ` Alexei Starovoitov
2019-06-17 19:06     ` Andrii Nakryiko
2019-06-18 14:05     ` Paul Chaignon

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=20190615191225.2409862-6-ast@kernel.org \
    --to=ast@kernel.org \
    --cc=bpf@vger.kernel.org \
    --cc=daniel@iogearbox.net \
    --cc=davem@davemloft.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 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).