Skip to contentSkip to conversation

bpf: improve verifier state analysis

PATCH Applied Alexei Starovoitov 3 participants 7 messages Dec 13, 2018 – Dec 15, 2018

Subsystems (6)
Networking Network drivers Kselftest BPF +2 more subsystems
lore
Share & tools
lore

Alexei Starovoitov

author maintainer
#0 lore raw

v2 cover bpf: improve verifier state analysis

v1->v2:
with optimization suggested by Jakub patch 4 safety check became cheap enough.

Several improvements to verifier state logic.
Patch 1 - trivial optimization
Patch 3 - significant optimization for stack state equivalence Patch 4 - safety check for liveness and prep for future state merging

Alexei Starovoitov (4):
bpf: speed up stacksafe check selftests/bpf: check insn processed in test_verifier
bpf: improve stacksafe state comparison
bpf: add self-check logic to liveness analysis

 include/linux/bpf_verifier.h                |   1 +
 kernel/bpf/verifier.c                       | 125 ++++++++++++++++++--
 tools/testing/selftests/bpf/test_verifier.c |  37 +++++-
 3 files changed, 154 insertions(+), 9 deletions(-)
Signature · 1 line
2.17.1
author maintainer
#1 lore raw

PATCH v2 1/4 bpf: speed up stacksafe check

Don't check the same stack liveness condition 8 times. once is enough.

Signed-off-by Alexei Starovoitov <[email protected]>
Acked-by Edward Cree <[email protected]>
Acked-by Jakub Kicinski <[email protected]>
---
 kernel/bpf/verifier.c | 4 +++-
 1 file changed, 3 insertions(+), 1 deletion(-)
kernel/bpf/verifier.c +3 -1
index 8b511a4fe84a..d4db4727a50e 100644
@@ -5147,9 +5147,11 @@ static bool stacksafe(struct bpf_func_state *old,
 	for (i = 0; i < old->allocated_stack; i++) {
 		spi = i / BPF_REG_SIZE;
 
-		if (!(old->stack[spi].spilled_ptr.live & REG_LIVE_READ))
+		if (!(old->stack[spi].spilled_ptr.live & REG_LIVE_READ)) {
+			i += BPF_REG_SIZE - 1;
 			/* explored state didn't use this */
 			continue;
+		}
 
 		if (old->stack[spi].slot_type[i % BPF_REG_SIZE] == STACK_INVALID)
 			continue;
Signature · 1 line
2.17.1
author maintainer
#2 lore raw

PATCH v2 2/4 selftests/bpf: check insn processed in test_verifier

In reply to Alexei Starovoitov

Teach test_verifier to parse verifier output for insn processed and compare with expected number.

Signed-off-by Alexei Starovoitov <[email protected]>
Acked-by Edward Cree <[email protected]>
Acked-by Jakub Kicinski <[email protected]>
---
 tools/testing/selftests/bpf/test_verifier.c | 15 ++++++++++++++-
 1 file changed, 14 insertions(+), 1 deletion(-)
tools/testing/selftests/bpf/test_verifier.c +14 -1
index a08c67c8767e..82359cdbc805 100644
@@ -76,7 +76,7 @@ struct bpf_test {
 	int fixup_percpu_cgroup_storage[MAX_FIXUPS];
 	const char *errstr;
 	const char *errstr_unpriv;
-	uint32_t retval, retval_unpriv;
+	uint32_t retval, retval_unpriv, insn_processed;
 	enum {
 		UNDEF,
 		ACCEPT,

@@ -14444,6 +14444,19 @@ static void do_test_single(struct bpf_test *test, bool unpriv,
 		}
 	}
 
+	if (test->insn_processed) {
+		uint32_t insn_processed;
+		char *proc;
+
+		proc = strstr(bpf_vlog, "processed ");
+		insn_processed = atoi(proc + 10);
+		if (test->insn_processed != insn_processed) {
+			printf("FAIL\nUnexpected insn_processed %u vs %u\n",
+			       insn_processed, test->insn_processed);
+			goto fail_log;
+		}
+	}
+
 	if (fd_prog >= 0) {
 		__u8 tmp[TEST_DATA_LEN << 2];
 		__u32 size_tmp = sizeof(tmp);
Signature · 1 line
2.17.1
author maintainer
#3 lore raw

PATCH v2 3/4 bpf: improve stacksafe state comparison

In reply to Alexei Starovoitov

"if (old->allocated_stack > cur->allocated_stack)" check is too conservative. In some cases explored stack could have allocated more space,
but that stack space was not live.
The test case improves from 19 to 15 processed insns
and improvement on real programs is significant as well:

                       before    after
bpf_lb-DLB_L3.o        1940      1831
bpf_lb-DLB_L4.o        3089      3029
bpf_lb-DUNKNOWN.o      1065      1064
bpf_lxc-DDROP_ALL.o    28052     26309
bpf_lxc-DUNKNOWN.o     35487     33517
bpf_netdev.o           10864     9713
bpf_overlay.o          6643      6184
bpf_lcx_jit.o          38437     37335
Signed-off-by Alexei Starovoitov <[email protected]>
Acked-by Edward Cree <[email protected]>
Acked-by Jakub Kicinski <[email protected]>
---
 kernel/bpf/verifier.c                       | 13 ++++++------
 tools/testing/selftests/bpf/test_verifier.c | 22 +++++++++++++++++++++
 2 files changed, 29 insertions(+), 6 deletions(-)
kernel/bpf/verifier.c +7 -6
index d4db4727a50e..6e5ea4c4d8e7 100644
@@ -5134,12 +5134,6 @@ static bool stacksafe(struct bpf_func_state *old,
 {
 	int i, spi;
 
-	/* if explored stack has more populated slots than current stack
-	 * such stacks are not equivalent
-	 */
-	if (old->allocated_stack > cur->allocated_stack)
-		return false;
-
 	/* walk slots of the explored stack and ignore any additional
 	 * slots in the current stack, since explored(safe) state
 	 * didn't use them

@@ -5155,6 +5149,13 @@ static bool stacksafe(struct bpf_func_state *old,
 
 		if (old->stack[spi].slot_type[i % BPF_REG_SIZE] == STACK_INVALID)
 			continue;
+
+		/* explored stack has more populated slots than current stack
+		 * and these slots were used
+		 */
+		if (i >= cur->allocated_stack)
+			return false;
+
 		/* if old state was safe with misc data in the stack
 		 * it will be safe with zero-initialized stack.
 		 * The opposite is not true
tools/testing/selftests/bpf/test_verifier.c +22 -0
index 82359cdbc805..f9de7fe0c26d 100644
@@ -13647,6 +13647,28 @@ static struct bpf_test tests[] = {
 		.prog_type = BPF_PROG_TYPE_SCHED_CLS,
 		.result = ACCEPT,
 	},
+	{
+		"allocated_stack",
+		.insns = {
+			BPF_ALU64_REG(BPF_MOV, BPF_REG_6, BPF_REG_1),
+			BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_get_prandom_u32),
+			BPF_ALU64_REG(BPF_MOV, BPF_REG_7, BPF_REG_0),
+			BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 5),
+			BPF_MOV64_IMM(BPF_REG_0, 0),
+			BPF_STX_MEM(BPF_DW, BPF_REG_10, BPF_REG_6, -8),
+			BPF_LDX_MEM(BPF_DW, BPF_REG_6, BPF_REG_10, -8),
+			BPF_STX_MEM(BPF_B, BPF_REG_10, BPF_REG_7, -9),
+			BPF_LDX_MEM(BPF_B, BPF_REG_7, BPF_REG_10, -9),
+			BPF_JMP_IMM(BPF_JNE, BPF_REG_0, 0, 0),
+			BPF_JMP_IMM(BPF_JNE, BPF_REG_0, 0, 0),
+			BPF_JMP_IMM(BPF_JNE, BPF_REG_0, 0, 0),
+			BPF_JMP_IMM(BPF_JNE, BPF_REG_0, 0, 0),
+			BPF_EXIT_INSN(),
+		},
+		.result = ACCEPT,
+		.result_unpriv = ACCEPT,
+		.insn_processed = 15,
+	},
 	{
 		"reference tracking in call: free reference in subprog and outside",
 		.insns = {
Signature · 1 line
2.17.1
author maintainer
#4 lore raw

PATCH v2 4/4 bpf: add self-check logic to liveness analysis

In reply to Alexei Starovoitov

Introduce REG_LIVE_DONE to check the liveness propagation and prepare the states for merging.
See algorithm description in clean_live_states().

Signed-off-by Alexei Starovoitov <[email protected]>
---
 include/linux/bpf_verifier.h |   1 +
 kernel/bpf/verifier.c        | 108 ++++++++++++++++++++++++++++++++++-
 2 files changed, 108 insertions(+), 1 deletion(-)
include/linux/bpf_verifier.h +1 -0
index c736945be7c5..07a55073c809 100644
@@ -38,6 +38,7 @@ enum bpf_reg_liveness {
 	REG_LIVE_NONE = 0, /* reg hasn't been read or written this branch */
 	REG_LIVE_READ, /* reg was read, so we're sensitive to initial value */
 	REG_LIVE_WRITTEN, /* reg was written first, screening off later reads */
+	REG_LIVE_DONE = 4, /* liveness won't be updating this register anymore */
 };
 
 struct bpf_reg_state {
kernel/bpf/verifier.c +107 -1

137 lines not on this page · raw message

Signature · 1 line
2.17.1
maintainer Applied
#6 lore raw
In reply to Alexei Starovoitov
Quoted 14 lines · Alexei Starovoitov

v1->v2:
with optimization suggested by Jakub patch 4 safety check became cheap enough.

Several improvements to verifier state logic.
Patch 1 - trivial optimization
Patch 3 - significant optimization for stack state equivalence Patch 4 - safety check for liveness and prep for future state merging

Alexei Starovoitov (4):
bpf: speed up stacksafe check selftests/bpf: check insn processed in test_verifier
bpf: improve stacksafe state comparison
bpf: add self-check logic to liveness analysis

Quoted 5 lines
 include/linux/bpf_verifier.h                |   1 +
 kernel/bpf/verifier.c                       | 125 ++++++++++++++++++--
 tools/testing/selftests/bpf/test_verifier.c |  37 +++++-
 3 files changed, 154 insertions(+), 9 deletions(-)

Applied, thanks!