Skip to contentSkip to conversation

Refactor verifier prune and jump point handling

PATCH Superseded Andrii Nakryiko 3 participants 9 messages Dec 2, 2022 – Dec 6, 2022

Subsystems (2)

v1 of 2 Superseded Latest is v2 →

lore
Share & tools
lore

Andrii Nakryiko

author maintainer
#0 lore raw

cover Refactor verifier prune and jump point handling

Disentangle prune and jump points in BPF verifier code. They are conceptually independent but currently coupled together. This small patch set refactors related code and make it possible to have some instruction marked as pruning or jump point independently.

Besides just conceptual cleanliness, this allows to remove unnecessary jump points (saving a tiny bit of performance and memory usage, potentially), and even more importantly it allows for clean extension of special pruning points, similarly to how it's done for BPF_FUNC_timer_set_callback. This will be used by future patches implementing open-coded BPF iterators.

Andrii Nakryiko (3):
bpf: decouple prune and jump points
bpf: mostly decouple jump history management from is_state_visited()
bpf: remove unnecessary prune and jump points

 include/linux/bpf_verifier.h |  1 +
 kernel/bpf/verifier.c        | 98 +++++++++++++++++++++---------------
 2 files changed, 58 insertions(+), 41 deletions(-)
Signature · 1 line
2.30.2
author maintainer
#1 lore raw

PATCH 1/3 bpf: decouple prune and jump points

BPF verifier marks some instructions as prune points. Currently these prune points serve two purposes.

It's a point where verifier tries to find previously verified state and check current state's equivalence to short circuit verification for current code path.

But also currently it's a point where jump history, used for precision backtracking, is updated. This is done so that non-linear flow of execution could be properly backtracked.

Such coupling is coincidental and unnecessary. Some prune points are not part of some non-linear jump path, so don't need update of jump history. On the other hand, not all instructions which have to be recorded in jump history necessarily are good prune points.

This patch splits prune and jump points into independent flags. Currently all prune points are marked as jump points to minimize amount of changes in this patch, but next patch will perform some optimization of prune vs jmp point placement.

No functional changes are intended.

---
 include/linux/bpf_verifier.h |  1 +
 kernel/bpf/verifier.c        | 57 +++++++++++++++++++++++++++---------
 2 files changed, 44 insertions(+), 14 deletions(-)
include/linux/bpf_verifier.h +1 -0
index b5090e89cb3f..9870d1d0df01 100644
@@ -452,6 +452,7 @@ struct bpf_insn_aux_data {
 	/* below fields are initialized once */
 	unsigned int orig_idx; /* original instruction index */
 	bool prune_point;
+	bool jmp_point;
 };
 
 #define MAX_USED_MAPS 64 /* max number of maps accessed by one eBPF program */
kernel/bpf/verifier.c +43 -14

127 lines not on this page · raw message

Signature · 1 line
2.30.2
reviewer Acked-by on v1 1/3
#2 lore raw

RE: [PATCH bpf-next 1/3] bpf: decouple prune and jump points

Quoted 16 lines · Andrii Nakryiko

BPF verifier marks some instructions as prune points. Currently these prune points serve two purposes.

It's a point where verifier tries to find previously verified state and check current state's equivalence to short circuit verification for current code path.

But also currently it's a point where jump history, used for precision backtracking, is updated. This is done so that non-linear flow of execution could be properly backtracked.

Such coupling is coincidental and unnecessary. Some prune points are not part of some non-linear jump path, so don't need update of jump history. On the other hand, not all instructions which have to be recorded in jump history necessarily are good prune points.

Quoted 8 lines

This patch splits prune and jump points into independent flags. Currently all prune points are marked as jump points to minimize amount of changes in this patch, but next patch will perform some optimization of prune vs jmp point placement.

No functional changes are intended.

Quoted 10 lines
---
 include/linux/bpf_verifier.h |  1 +
 kernel/bpf/verifier.c        | 57 +++++++++++++++++++++++++++---------
 2 files changed, 44 insertions(+), 14 deletions(-)
include/linux/bpf_verifier.h +0 -0
index b5090e89cb3f..9870d1d0df01 100644

include/linux/bpf_verifier.h struct bpf_insn_aux_data { · line 455

Quoted 4 lines
include/linux/bpf_verifier.h +1 -0
@@ -452,6 +452,7 @@ struct bpf_insn_aux_data {
 	/* below fields are initialized once */
 	unsigned int orig_idx; /* original instruction index */
 	bool prune_point;
+	bool jmp_point;

Random thought we might want to make these flags in the future so you can have,

type = BPF_PRUNE_POINT | BPF_JMP_POINT | BPF_ITERATOR_POINT

and so on without a bunch of bools.

Quoted 2 lines
include/linux/bpf_verifier.h +0 -0
 };
 
#3 lore raw

Re: [PATCH bpf-next 1/3] bpf: decouple prune and jump points

Quoted 47 lines · John Fastabend
Quoted 16 lines · Andrii Nakryiko

BPF verifier marks some instructions as prune points. Currently these prune points serve two purposes.

It's a point where verifier tries to find previously verified state and check current state's equivalence to short circuit verification for current code path.

But also currently it's a point where jump history, used for precision backtracking, is updated. This is done so that non-linear flow of execution could be properly backtracked.

Such coupling is coincidental and unnecessary. Some prune points are not part of some non-linear jump path, so don't need update of jump history. On the other hand, not all instructions which have to be recorded in jump history necessarily are good prune points.

Quoted 8 lines

This patch splits prune and jump points into independent flags. Currently all prune points are marked as jump points to minimize amount of changes in this patch, but next patch will perform some optimization of prune vs jmp point placement.

No functional changes are intended.

Quoted 10 lines
---
 include/linux/bpf_verifier.h |  1 +
 kernel/bpf/verifier.c        | 57 +++++++++++++++++++++++++++---------
 2 files changed, 44 insertions(+), 14 deletions(-)
include/linux/bpf_verifier.h +0 -0
index b5090e89cb3f..9870d1d0df01 100644

include/linux/bpf_verifier.h struct bpf_insn_aux_data { · line 455

Quoted 4 lines
include/linux/bpf_verifier.h +1 -0
@@ -452,6 +452,7 @@ struct bpf_insn_aux_data {
      /* below fields are initialized once */
      unsigned int orig_idx; /* original instruction index */
      bool prune_point;
+     bool jmp_point;

Random thought we might want to make these flags in the future so you can have,

Quoted 3 lines

type = BPF_PRUNE_POINT | BPF_JMP_POINT | BPF_ITERATOR_POINT

and so on without a bunch of bools.

Bunch of bools are nice because they are explicit :) As long as we have up to 8 of them, we should be fine, I think. I don't envision adding BPF_ITERATOR_POINT, I just need prune_point on a few special helpers.

Quoted 3 lines
Quoted 3 lines
include/linux/bpf_verifier.h +0 -0
 };
 
author maintainer
#4 lore raw

PATCH 2/3 bpf: mostly decouple jump history management from is_state_visited()

In reply to Andrii Nakryiko

Jump history updating and state equivalence checks are conceptually independent, so move push_jmp_history() out of is_state_visited(). Also make a decision whether to perform state equivalence checks or not one layer higher in do_check(), keeping is_state_visited() unconditionally performing state checks.

push_jmp_history() should be performed after state checks. There is just one small non-uniformity. When is_state_visited() finds already validated equivalent state, it propagates precision marks to current state's parent chain. For this to work correctly, jump history has to be updated, so is_state_visited() is doing that internally.

But if no equivalent verified state is found, jump history has to be updated in a newly cloned child state, so is_jmp_point()
+ push_jmp_history() is performed after is_state_visited() exited with zero result, which means "proceed with validation".

This change has no functional changes. It's not strictly necessary, but feels right to decouple these two processes.

---
 kernel/bpf/verifier.c | 49 +++++++++++++++++++++++--------------------
 1 file changed, 26 insertions(+), 23 deletions(-)
kernel/bpf/verifier.c +26 -23
index 2dec4ca47bb5..75a56ded5aca 100644
@@ -13324,13 +13324,6 @@ static int is_state_visited(struct bpf_verifier_env *env, int insn_idx)
 	int i, j, err, states_cnt = 0;
 	bool add_new_state = env->test_state_freq ? true : false;
 
-	cur->last_insn_idx = env->prev_insn_idx;
-	if (!is_prune_point(env, insn_idx))
-		/* this 'insn_idx' instruction wasn't marked, so we will not
-		 * be doing state search here
-		 */
-		return push_jmp_history(env, cur);
-
 	/* bpf progs typically have pruning point every 4 instructions
 	 * http://vger.kernel.org/bpfconf2019.html#session-1
 	 * Do not add new state for future pruning if the verifier hasn't seen
@@ -13465,10 +13458,10 @@ static int is_state_visited(struct bpf_verifier_env *env, int insn_idx)
 		env->max_states_per_insn = states_cnt;
 
 	if (!env->bpf_capable && states_cnt > BPF_COMPLEXITY_LIMIT_STATES)
-		return push_jmp_history(env, cur);
+		return 0;
 
 	if (!add_new_state)
-		return push_jmp_history(env, cur);
+		return 0;
 
 	/* There were no equivalent states, remember the current one.
 	 * Technically the current state is not proven to be safe yet,
@@ -13608,21 +13601,31 @@ static int do_check(struct bpf_verifier_env *env)
 			return -E2BIG;
 		}
 
-		err = is_state_visited(env, env->insn_idx);
-		if (err < 0)
-			return err;
-		if (err == 1) {
-			/* found equivalent state, can prune the search */
-			if (env->log.level & BPF_LOG_LEVEL) {
-				if (do_print_state)
-					verbose(env, "\nfrom %d to %d%s: safe\n",
-						env->prev_insn_idx, env->insn_idx,
-						env->cur_state->speculative ?
-						" (speculative execution)" : "");
-				else
-					verbose(env, "%d: safe\n", env->insn_idx);
+		state->last_insn_idx = env->prev_insn_idx;
+
+		if (is_prune_point(env, env->insn_idx)) {
+			err = is_state_visited(env, env->insn_idx);
+			if (err < 0)
+				return err;
+			if (err == 1) {
+				/* found equivalent state, can prune the search */
+				if (env->log.level & BPF_LOG_LEVEL) {
+					if (do_print_state)
+						verbose(env, "\nfrom %d to %d%s: safe\n",
+							env->prev_insn_idx, env->insn_idx,
+							env->cur_state->speculative ?
+							" (speculative execution)" : "");
+					else
+						verbose(env, "%d: safe\n", env->insn_idx);
+				}
+				goto process_bpf_exit;
 			}
-			goto process_bpf_exit;
+		}
+
+		if (is_jmp_point(env, env->insn_idx)) {
+			err = push_jmp_history(env, state);
+			if (err)
+				return err;
 		}
 
 		if (signal_pending(current))
Signature · 1 line
2.30.2
reviewer Acked-by on v1 2/3
#5 lore raw

RE: [PATCH bpf-next 2/3] bpf: mostly decouple jump history management from is_state_visited()

Quoted 17 lines · Andrii Nakryiko

Jump history updating and state equivalence checks are conceptually independent, so move push_jmp_history() out of is_state_visited(). Also make a decision whether to perform state equivalence checks or not one layer higher in do_check(), keeping is_state_visited() unconditionally performing state checks.

push_jmp_history() should be performed after state checks. There is just one small non-uniformity. When is_state_visited() finds already validated equivalent state, it propagates precision marks to current state's parent chain. For this to work correctly, jump history has to be updated, so is_state_visited() is doing that internally.

But if no equivalent verified state is found, jump history has to be updated in a newly cloned child state, so is_jmp_point()
+ push_jmp_history() is performed after is_state_visited() exited with zero result, which means "proceed with validation".

Quoted 5 lines

This change has no functional changes. It's not strictly necessary, but feels right to decouple these two processes.

---

author maintainer
#6 lore raw

PATCH 3/3 bpf: remove unnecessary prune and jump points

In reply to Andrii Nakryiko

Don't mark some instructions as jump points when there are actually no jumps and instructions are just processed sequentially. Such case is handled naturally by precision backtracking logic without the need to update jump history.

Also remove both jump and prune point marking for instruction right after unconditional jumps, as program flow can get to the instruction right after unconditional jump instruction only if there is a jump to that instruction from somewhere else in the program. In such case we'll mark such instruction as prune/jump point because it's a destination of a jump.

This change has no changes in terms of number of instructions or states processes across Cilium and selftests programs.

---
 kernel/bpf/verifier.c | 24 ++++--------------------
 1 file changed, 4 insertions(+), 20 deletions(-)
kernel/bpf/verifier.c +4 -20
index 75a56ded5aca..03c2cc116292 100644
@@ -12209,13 +12209,10 @@ static int visit_func_call_insn(int t, int insn_cnt,
 	if (ret)
 		return ret;
 
-	if (t + 1 < insn_cnt) {
-		mark_prune_point(env, t + 1);
-		mark_jmp_point(env, t + 1);
-	}
+	mark_prune_point(env, t + 1);
+
 	if (visit_callee) {
 		mark_prune_point(env, t);
-		mark_jmp_point(env, t);
 		ret = push_insn(t, t + insns[t].imm + 1, BRANCH, env,
 				/* It's ok to allow recursion from CFG point of
 				 * view. __check_func_call() will do the actual
@@ -12249,15 +12246,13 @@ static int visit_insn(int t, int insn_cnt, struct bpf_verifier_env *env)
 		return DONE_EXPLORING;
 
 	case BPF_CALL:
-		if (insns[t].imm == BPF_FUNC_timer_set_callback) {
+		if (insns[t].imm == BPF_FUNC_timer_set_callback)
 			/* Mark this call insn to trigger is_state_visited() check
 			 * before call itself is processed by __check_func_call().
 			 * Otherwise new async state will be pushed for further
 			 * exploration.
 			 */
 			mark_prune_point(env, t);
-			mark_jmp_point(env, t);
-		}
 		return visit_func_call_insn(t, insn_cnt, insns, env,
 					    insns[t].src_reg == BPF_PSEUDO_CALL);
 
@@ -12271,26 +12266,15 @@ static int visit_insn(int t, int insn_cnt, struct bpf_verifier_env *env)
 		if (ret)
 			return ret;
 
-		/* unconditional jmp is not a good pruning point,
-		 * but it's marked, since backtracking needs
-		 * to record jmp history in is_state_visited().
-		 */
 		mark_prune_point(env, t + insns[t].off + 1);
 		mark_jmp_point(env, t + insns[t].off + 1);
-		/* tell verifier to check for equivalent states
-		 * after every call and jump
-		 */
-		if (t + 1 < insn_cnt) {
-			mark_prune_point(env, t + 1);
-			mark_jmp_point(env, t + 1);
-		}
 
 		return ret;
 
 	default:
 		/* conditional jump with two edges */
 		mark_prune_point(env, t);
-		mark_jmp_point(env, t);
+
 		ret = push_insn(t, t + 1, FALLTHROUGH, env, true);
 		if (ret)
 			return ret;
Signature · 1 line
2.30.2
#7 lore raw

RE: [PATCH bpf-next 3/3] bpf: remove unnecessary prune and jump points

Quoted 5 lines · Andrii Nakryiko

Don't mark some instructions as jump points when there are actually no jumps and instructions are just processed sequentially. Such case is handled naturally by precision backtracking logic without the need to update jump history.

Sorry having trouble matching up commit message with code below.

Quoted 36 lines

Also remove both jump and prune point marking for instruction right after unconditional jumps, as program flow can get to the instruction right after unconditional jump instruction only if there is a jump to that instruction from somewhere else in the program. In such case we'll mark such instruction as prune/jump point because it's a destination of a jump.

This change has no changes in terms of number of instructions or states processes across Cilium and selftests programs.

---
 kernel/bpf/verifier.c | 24 ++++--------------------
 1 file changed, 4 insertions(+), 20 deletions(-)
kernel/bpf/verifier.c +2 -5
index 75a56ded5aca..03c2cc116292 100644
@@ -12209,13 +12209,10 @@ static int visit_func_call_insn(int t, int insn_cnt,
 	if (ret)
 		return ret;
 
-	if (t + 1 < insn_cnt) {
-		mark_prune_point(env, t + 1);
-		mark_jmp_point(env, t + 1);
-	}
+	mark_prune_point(env, t + 1);
+
 	if (visit_callee) {
 		mark_prune_point(env, t);
-		mark_jmp_point(env, t);
 		ret = push_insn(t, t + insns[t].imm + 1, BRANCH, env,
 				/* It's ok to allow recursion from CFG point of
 				 * view. __check_func_call() will do the actual

kernel/bpf/verifier.c static int visit_insn(int t, int insn_cnt, struct bpf_verifier_env *env) · line 12250

Quoted 6 lines
kernel/bpf/verifier.c +1 -1
@@ -12249,15 +12246,13 @@ static int visit_insn(int t, int insn_cnt, struct bpf_verifier_env *env)
 		return DONE_EXPLORING;
 
 	case BPF_CALL:
-		if (insns[t].imm == BPF_FUNC_timer_set_callback) {
+		if (insns[t].imm == BPF_FUNC_timer_set_callback)
 			/* Mark this call insn to trigger is_state_visited() check

maybe fix the comment here?

Quoted 16 lines
kernel/bpf/verifier.c +0 -4
 			 * before call itself is processed by __check_func_call().
 			 * Otherwise new async state will be pushed for further
 			 * exploration.
 			 */
 			mark_prune_point(env, t);
-			mark_jmp_point(env, t);
-		}
 		return visit_func_call_insn(t, insn_cnt, insns, env,
 					    insns[t].src_reg == BPF_PSEUDO_CALL);
 
@@ -12271,26 +12266,15 @@ static int visit_insn(int t, int insn_cnt, struct bpf_verifier_env *env)
 		if (ret)
 			return ret;
 
-		/* unconditional jmp is not a good pruning point,
-		 * but it's marked, since backtracking needs

kernel/bpf/verifier.c static int visit_insn(int t, int insn_cnt, struct bpf_verifier_env *env) · line 12285

Quoted 10 lines
kernel/bpf/verifier.c +0 -8
-		 * to record jmp history in is_state_visited().
-		 */
 		mark_prune_point(env, t + insns[t].off + 1);
 		mark_jmp_point(env, t + insns[t].off + 1);
-		/* tell verifier to check for equivalent states
-		 * after every call and jump
-		 */
-		if (t + 1 < insn_cnt) {
-			mark_prune_point(env, t + 1);
-			mark_jmp_point(env, t + 1);

This makes sense to me its unconditional jmp. So no need to add jmp point.

kernel/bpf/verifier.c static int visit_insn(int t, int insn_cnt, struct bpf_verifier_env *env) · line 12293

Quoted 8 lines
kernel/bpf/verifier.c +0 -2
-		}
 
 		return ret;
 
 	default:
 		/* conditional jump with two edges */
 		mark_prune_point(env, t);
-		mark_jmp_point(env, t);
                 ^^^^^^^^^^^^^^^^^^^^^^^

Specifically, try to see why we dropped this jmp_point?

Quoted 7 lines
kernel/bpf/verifier.c +1 -0
+
 		ret = push_insn(t, t + 1, FALLTHROUGH, env, true);
 		if (ret)
 			return ret;
Signature · 1 line
2.30.2
#8 lore raw

Re: [PATCH bpf-next 3/3] bpf: remove unnecessary prune and jump points

Quoted 9 lines · John Fastabend
Quoted 5 lines · Andrii Nakryiko

Don't mark some instructions as jump points when there are actually no jumps and instructions are just processed sequentially. Such case is handled naturally by precision backtracking logic without the need to update jump history.

Sorry having trouble matching up commit message with code below.

Sorry, not clear which part? I'm referring to the logic in get_prev_insn_idx() here, where we go linearly one instruction backwards, unless last jmp_history entry matches current instruction. In the latter case we go to the st->jmp_history[cnt - 1].prev_idx (non-linear case).

Quoted 24 lines
Quoted 24 lines

Also remove both jump and prune point marking for instruction right after unconditional jumps, as program flow can get to the instruction right after unconditional jump instruction only if there is a jump to that instruction from somewhere else in the program. In such case we'll mark such instruction as prune/jump point because it's a destination of a jump.

This change has no changes in terms of number of instructions or states processes across Cilium and selftests programs.

---
 kernel/bpf/verifier.c | 24 ++++--------------------
 1 file changed, 4 insertions(+), 20 deletions(-)
kernel/bpf/verifier.c +0 -0
index 75a56ded5aca..03c2cc116292 100644
@@ -12209,13 +12209,10 @@ static int visit_func_call_insn(int t, int insn_cnt,
      if (ret)
              return ret;
 
Quoted 5 lines

kernel/bpf/verifier.c static int visit_func_call_insn(int t, int insn_cnt, · line 12212

Quoted 5 lines
kernel/bpf/verifier.c +1 -4
-     if (t + 1 < insn_cnt) {
-             mark_prune_point(env, t + 1);
-             mark_jmp_point(env, t + 1);
-     }
+     mark_prune_point(env, t + 1);

I'm now thinking that maybe here we actually need to keep jmp_point, as we don't record a jump point for the target of EXIT instruction in subprog. I'll add this back.

Quoted 10 lines
Quoted 10 lines
kernel/bpf/verifier.c +1 -1
+
      if (visit_callee) {
              mark_prune_point(env, t);
-             mark_jmp_point(env, t);
              ret = push_insn(t, t + insns[t].imm + 1, BRANCH, env,
                              /* It's ok to allow recursion from CFG point of
                               * view. __check_func_call() will do the actual
@@ -12249,15 +12246,13 @@ static int visit_insn(int t, int insn_cnt, struct bpf_verifier_env *env)
              return DONE_EXPLORING;
 
Quoted 6 lines

kernel/bpf/verifier.c static int visit_insn(int t, int insn_cnt, struct bpf_verifier_env *env) · line 12250

Quoted 4 lines
kernel/bpf/verifier.c +1 -1
      case BPF_CALL:
-             if (insns[t].imm == BPF_FUNC_timer_set_callback) {
+             if (insns[t].imm == BPF_FUNC_timer_set_callback)
                      /* Mark this call insn to trigger is_state_visited() check

maybe fix the comment here?

It's not broken, but would you like me to explicitly state "Mark this call insn as a prune point to trigger..."?

Quoted 15 lines
Quoted 15 lines
kernel/bpf/verifier.c +0 -2
                       * before call itself is processed by __check_func_call().
                       * Otherwise new async state will be pushed for further
                       * exploration.
                       */
                      mark_prune_point(env, t);
-                     mark_jmp_point(env, t);
-             }
              return visit_func_call_insn(t, insn_cnt, insns, env,
                                          insns[t].src_reg == BPF_PSEUDO_CALL);
 
@@ -12271,26 +12266,15 @@ static int visit_insn(int t, int insn_cnt, struct bpf_verifier_env *env)
              if (ret)
                      return ret;
 
Quoted 16 lines

kernel/bpf/verifier.c static int visit_insn(int t, int insn_cnt, struct bpf_verifier_env *env) · line 12285

Quoted 12 lines
kernel/bpf/verifier.c +0 -10
-             /* unconditional jmp is not a good pruning point,
-              * but it's marked, since backtracking needs
-              * to record jmp history in is_state_visited().
-              */
              mark_prune_point(env, t + insns[t].off + 1);
              mark_jmp_point(env, t + insns[t].off + 1);
-             /* tell verifier to check for equivalent states
-              * after every call and jump
-              */
-             if (t + 1 < insn_cnt) {
-                     mark_prune_point(env, t + 1);
-                     mark_jmp_point(env, t + 1);

This makes sense to me its unconditional jmp. So no need to add jmp point.

yep

Quoted 4 lines
Quoted 4 lines
kernel/bpf/verifier.c +0 -1
-             }
 
              return ret;
 
Quoted 8 lines

kernel/bpf/verifier.c static int visit_insn(int t, int insn_cnt, struct bpf_verifier_env *env) · line 12293

Quoted 4 lines
kernel/bpf/verifier.c +0 -1
      default:
              /* conditional jump with two edges */
              mark_prune_point(env, t);
-             mark_jmp_point(env, t);
                 ^^^^^^^^^^^^^^^^^^^^^^^

Specifically, try to see why we dropped this jmp_point?

Because there is nothing special about current instruction (which is a conditional jump instruction). If we got here sequentially, no need to record jmp_history. If we jumped here from somewhere non-linearly, we should have already marked this instruction as jmp_point in push_insn (with e == BRANCH).

So jmp_point is completely irrelevant, the goal here is to force state checkpointing before we process jump instruction.

Also keep in mind that we mark *destination* of non-linear jump as a jump point. So target of function call, jump, etc, but not call instruction or jump instruction itself.

Quoted 10 lines
Quoted 8 lines
kernel/bpf/verifier.c +1 -1
+
              ret = push_insn(t, t + 1, FALLTHROUGH, env, true);
              if (ret)
                      return ret;
--

2.30.2