[PATCH bpf-next 0/3] bpf: optimize explored_states

[PATCH bpf-next 0/3] bpf: optimize explored_states

[Alexei Starovoitov]

Convert explored_states array into hash table and use simple hash to
reduce verifier peak memory consumption for programs with bpf2bpf calls.
More details in patch 3.

Alexei Starovoitov (3):
  bpf: cleanup explored_states
  bpf: split explored_states
  bpf: convert explored_states to hash table

 include/linux/bpf_verifier.h |  2 +
 kernel/bpf/verifier.c        | 78 ++++++++++++++++++++++--------------
 2 files changed, 51 insertions(+), 29 deletions(-)

-- 
2.20.0

[PATCH bpf-next 1/3] bpf: cleanup explored_states

[Alexei Starovoitov]

clean up explored_states to prep for introduction of hashtable
No functional changes.

Signed-off-by: Alexei Starovoitov <ast@kernel.org>
---
 kernel/bpf/verifier.c | 30 +++++++++++++++++++++---------
 1 file changed, 21 insertions(+), 9 deletions(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 95f9354495ad..a171b2940382 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -5436,6 +5436,18 @@ enum {
 };
 
 #define STATE_LIST_MARK ((struct bpf_verifier_state_list *) -1L)
+static struct bpf_verifier_state_list **explored_state(
+					struct bpf_verifier_env *env,
+					int idx)
+{
+	return &env->explored_states[idx];
+}
+
+static void init_explored_state(struct bpf_verifier_env *env, int idx)
+{
+	env->explored_states[idx] = STATE_LIST_MARK;
+}
+
 
 /* t, w, e - match pseudo-code above:
  * t - index of current instruction
@@ -5461,7 +5473,7 @@ static int push_insn(int t, int w, int e, struct bpf_verifier_env *env)
 
 	if (e == BRANCH)
 		/* mark branch target for state pruning */
-		env->explored_states[w] = STATE_LIST_MARK;
+		init_explored_state(env, w);
 
 	if (insn_state[w] == 0) {
 		/* tree-edge */
@@ -5529,9 +5541,9 @@ static int check_cfg(struct bpf_verifier_env *env)
 			else if (ret < 0)
 				goto err_free;
 			if (t + 1 < insn_cnt)
-				env->explored_states[t + 1] = STATE_LIST_MARK;
+				init_explored_state(env, t + 1);
 			if (insns[t].src_reg == BPF_PSEUDO_CALL) {
-				env->explored_states[t] = STATE_LIST_MARK;
+				init_explored_state(env, t);
 				ret = push_insn(t, t + insns[t].imm + 1, BRANCH, env);
 				if (ret == 1)
 					goto peek_stack;
@@ -5554,10 +5566,10 @@ static int check_cfg(struct bpf_verifier_env *env)
 			 * after every call and jump
 			 */
 			if (t + 1 < insn_cnt)
-				env->explored_states[t + 1] = STATE_LIST_MARK;
+				init_explored_state(env, t + 1);
 		} else {
 			/* conditional jump with two edges */
-			env->explored_states[t] = STATE_LIST_MARK;
+			init_explored_state(env, t);
 			ret = push_insn(t, t + 1, FALLTHROUGH, env);
 			if (ret == 1)
 				goto peek_stack;
@@ -6005,7 +6017,7 @@ static void clean_live_states(struct bpf_verifier_env *env, int insn,
 	struct bpf_verifier_state_list *sl;
 	int i;
 
-	sl = env->explored_states[insn];
+	sl = *explored_state(env, insn);
 	if (!sl)
 		return;
 
@@ -6364,7 +6376,7 @@ static int is_state_visited(struct bpf_verifier_env *env, int insn_idx)
 	struct bpf_verifier_state *cur = env->cur_state, *new;
 	int i, j, err, states_cnt = 0;
 
-	pprev = &env->explored_states[insn_idx];
+	pprev = explored_state(env, insn_idx);
 	sl = *pprev;
 
 	if (!sl)
@@ -6451,8 +6463,8 @@ static int is_state_visited(struct bpf_verifier_env *env, int insn_idx)
 		kfree(new_sl);
 		return err;
 	}
-	new_sl->next = env->explored_states[insn_idx];
-	env->explored_states[insn_idx] = new_sl;
+	new_sl->next = *explored_state(env, insn_idx);
+	*explored_state(env, insn_idx) = new_sl;
 	/* connect new state to parentage chain. Current frame needs all
 	 * registers connected. Only r6 - r9 of the callers are alive (pushed
 	 * to the stack implicitly by JITs) so in callers' frames connect just
-- 
2.20.0

Re: [PATCH bpf-next 1/3] bpf: cleanup explored_states

[Jakub Kicinski]

On Tue, 21 May 2019 16:06:33 -0700, Alexei Starovoitov wrote:
> clean up explored_states to prep for introduction of hashtable
> No functional changes.
> 
> Signed-off-by: Alexei Starovoitov <ast@kernel.org>
> ---
>  kernel/bpf/verifier.c | 30 +++++++++++++++++++++---------
>  1 file changed, 21 insertions(+), 9 deletions(-)
> 
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 95f9354495ad..a171b2940382 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -5436,6 +5436,18 @@ enum {
>  };
>  
>  #define STATE_LIST_MARK ((struct bpf_verifier_state_list *) -1L)
> +static struct bpf_verifier_state_list **explored_state(
> +					struct bpf_verifier_env *env,
> +					int idx)
> +{
> +	return &env->explored_states[idx];
> +}
> +
> +static void init_explored_state(struct bpf_verifier_env *env, int idx)
> +{
> +	env->explored_states[idx] = STATE_LIST_MARK;
> +}
> +

nit: extra new line here

>  

[PATCH bpf-next 2/3] bpf: split explored_states

[Alexei Starovoitov]

split explored_states into prune_point boolean mark
and link list of explored states.
This removes STATE_LIST_MARK hack and allows marks to be separate from states.

Signed-off-by: Alexei Starovoitov <ast@kernel.org>
---
 include/linux/bpf_verifier.h |  1 +
 kernel/bpf/verifier.c        | 31 +++++++++++++------------------
 2 files changed, 14 insertions(+), 18 deletions(-)

diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index 1305ccbd8fe6..02bba09a0ea1 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -233,6 +233,7 @@ struct bpf_insn_aux_data {
 	int sanitize_stack_off; /* stack slot to be cleared */
 	bool seen; /* this insn was processed by the verifier */
 	u8 alu_state; /* used in combination with alu_limit */
+	bool prune_point;
 	unsigned int orig_idx; /* original instruction index */
 };
 
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index a171b2940382..89097a4b1bf3 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -5435,7 +5435,6 @@ enum {
 	BRANCH = 2,
 };
 
-#define STATE_LIST_MARK ((struct bpf_verifier_state_list *) -1L)
 static struct bpf_verifier_state_list **explored_state(
 					struct bpf_verifier_env *env,
 					int idx)
@@ -5445,7 +5444,7 @@ static struct bpf_verifier_state_list **explored_state(
 
 static void init_explored_state(struct bpf_verifier_env *env, int idx)
 {
-	env->explored_states[idx] = STATE_LIST_MARK;
+	env->insn_aux_data[idx].prune_point = true;
 }
 
 
@@ -6018,10 +6017,7 @@ static void clean_live_states(struct bpf_verifier_env *env, int insn,
 	int i;
 
 	sl = *explored_state(env, insn);
-	if (!sl)
-		return;
-
-	while (sl != STATE_LIST_MARK) {
+	while (sl) {
 		if (sl->state.curframe != cur->curframe)
 			goto next;
 		for (i = 0; i <= cur->curframe; i++)
@@ -6376,18 +6372,18 @@ static int is_state_visited(struct bpf_verifier_env *env, int insn_idx)
 	struct bpf_verifier_state *cur = env->cur_state, *new;
 	int i, j, err, states_cnt = 0;
 
-	pprev = explored_state(env, insn_idx);
-	sl = *pprev;
-
-	if (!sl)
+	if (!env->insn_aux_data[insn_idx].prune_point)
 		/* this 'insn_idx' instruction wasn't marked, so we will not
 		 * be doing state search here
 		 */
 		return 0;
 
+	pprev = explored_state(env, insn_idx);
+	sl = *pprev;
+
 	clean_live_states(env, insn_idx, cur);
 
-	while (sl != STATE_LIST_MARK) {
+	while (sl) {
 		if (states_equal(env, &sl->state, cur)) {
 			sl->hit_cnt++;
 			/* reached equivalent register/stack state,
@@ -8145,13 +8141,12 @@ static void free_states(struct bpf_verifier_env *env)
 	for (i = 0; i < env->prog->len; i++) {
 		sl = env->explored_states[i];
 
-		if (sl)
-			while (sl != STATE_LIST_MARK) {
-				sln = sl->next;
-				free_verifier_state(&sl->state, false);
-				kfree(sl);
-				sl = sln;
-			}
+		while (sl) {
+			sln = sl->next;
+			free_verifier_state(&sl->state, false);
+			kfree(sl);
+			sl = sln;
+		}
 	}
 
 	kvfree(env->explored_states);
-- 
2.20.0

[PATCH bpf-next 3/3] bpf: convert explored_states to hash table

[Alexei Starovoitov]

All prune points inside a callee bpf function most likely will have
different callsites. For example, if function foo() is called from
two callsites the half of explored states in all prune points in foo()
will be useless for subsequent walking of one of those callsites.
Fortunately explored_states pruning heuristics keeps the number of states
per prune point small, but walking these states is still a waste of cpu
time when the callsite of the current state is different from the callsite
of the explored state.

To improve pruning logic convert explored_states into hash table and
use simple insn_idx ^ callsite hash to select hash bucket.
This optimization has no effect on programs without bpf2bpf calls
and drastically improves programs with calls.
In the later case it reduces total memory consumption in 1M scale tests
by almost 3 times (peak_states drops from 5752 to 2016).

Care should be taken when comparing the states for equivalency.
Since the same hash bucket can now contain states with different indices
the insn_idx has to be part of verifier_state and compared.

Different hash table sizes and different hash functions were explored,
but the results were not significantly better vs this patch.
They can be improved in the future.

Hit/miss heuristic is not counting index miscompare as a miss.
Otherwise verifier stats become unstable when experimenting
with different hash functions.

Signed-off-by: Alexei Starovoitov <ast@kernel.org>
---
 include/linux/bpf_verifier.h |  1 +
 kernel/bpf/verifier.c        | 23 ++++++++++++++++++-----
 2 files changed, 19 insertions(+), 5 deletions(-)

diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index 02bba09a0ea1..405b502283c5 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -187,6 +187,7 @@ struct bpf_func_state {
 struct bpf_verifier_state {
 	/* call stack tracking */
 	struct bpf_func_state *frame[MAX_CALL_FRAMES];
+	u32 insn_idx;
 	u32 curframe;
 	u32 active_spin_lock;
 	bool speculative;
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 89097a4b1bf3..082f6eefb1c4 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -5435,11 +5435,19 @@ enum {
 	BRANCH = 2,
 };
 
+static u32 state_htab_size(struct bpf_verifier_env *env)
+{
+	return env->prog->len;
+}
+
 static struct bpf_verifier_state_list **explored_state(
 					struct bpf_verifier_env *env,
 					int idx)
 {
-	return &env->explored_states[idx];
+	struct bpf_verifier_state *cur = env->cur_state;
+	struct bpf_func_state *state = cur->frame[cur->curframe];
+
+	return &env->explored_states[(idx ^ state->callsite) % state_htab_size(env)];
 }
 
 static void init_explored_state(struct bpf_verifier_env *env, int idx)
@@ -6018,7 +6026,8 @@ static void clean_live_states(struct bpf_verifier_env *env, int insn,
 
 	sl = *explored_state(env, insn);
 	while (sl) {
-		if (sl->state.curframe != cur->curframe)
+		if (sl->state.insn_idx != insn ||
+		    sl->state.curframe != cur->curframe)
 			goto next;
 		for (i = 0; i <= cur->curframe; i++)
 			if (sl->state.frame[i]->callsite != cur->frame[i]->callsite)
@@ -6384,6 +6393,9 @@ static int is_state_visited(struct bpf_verifier_env *env, int insn_idx)
 	clean_live_states(env, insn_idx, cur);
 
 	while (sl) {
+		states_cnt++;
+		if (sl->state.insn_idx != insn_idx)
+			goto next;
 		if (states_equal(env, &sl->state, cur)) {
 			sl->hit_cnt++;
 			/* reached equivalent register/stack state,
@@ -6401,7 +6413,6 @@ static int is_state_visited(struct bpf_verifier_env *env, int insn_idx)
 				return err;
 			return 1;
 		}
-		states_cnt++;
 		sl->miss_cnt++;
 		/* heuristic to determine whether this state is beneficial
 		 * to keep checking from state equivalence point of view.
@@ -6428,6 +6439,7 @@ static int is_state_visited(struct bpf_verifier_env *env, int insn_idx)
 			sl = *pprev;
 			continue;
 		}
+next:
 		pprev = &sl->next;
 		sl = *pprev;
 	}
@@ -6459,6 +6471,7 @@ static int is_state_visited(struct bpf_verifier_env *env, int insn_idx)
 		kfree(new_sl);
 		return err;
 	}
+	new->insn_idx = insn_idx;
 	new_sl->next = *explored_state(env, insn_idx);
 	*explored_state(env, insn_idx) = new_sl;
 	/* connect new state to parentage chain. Current frame needs all
@@ -8138,7 +8151,7 @@ static void free_states(struct bpf_verifier_env *env)
 	if (!env->explored_states)
 		return;
 
-	for (i = 0; i < env->prog->len; i++) {
+	for (i = 0; i < state_htab_size(env); i++) {
 		sl = env->explored_states[i];
 
 		while (sl) {
@@ -8246,7 +8259,7 @@ int bpf_check(struct bpf_prog **prog, union bpf_attr *attr,
 			goto skip_full_check;
 	}
 
-	env->explored_states = kvcalloc(env->prog->len,
+	env->explored_states = kvcalloc(state_htab_size(env),
 				       sizeof(struct bpf_verifier_state_list *),
 				       GFP_USER);
 	ret = -ENOMEM;
-- 
2.20.0

Re: [PATCH bpf-next 3/3] bpf: convert explored_states to hash table

[Andrii Nakryiko]

On Tue, May 21, 2019 at 4:08 PM Alexei Starovoitov <ast@kernel.org> wrote:
>
> All prune points inside a callee bpf function most likely will have
> different callsites. For example, if function foo() is called from
> two callsites the half of explored states in all prune points in foo()
> will be useless for subsequent walking of one of those callsites.
> Fortunately explored_states pruning heuristics keeps the number of states
> per prune point small, but walking these states is still a waste of cpu
> time when the callsite of the current state is different from the callsite
> of the explored state.
>
> To improve pruning logic convert explored_states into hash table and
> use simple insn_idx ^ callsite hash to select hash bucket.
> This optimization has no effect on programs without bpf2bpf calls
> and drastically improves programs with calls.
> In the later case it reduces total memory consumption in 1M scale tests
> by almost 3 times (peak_states drops from 5752 to 2016).
>
> Care should be taken when comparing the states for equivalency.
> Since the same hash bucket can now contain states with different indices
> the insn_idx has to be part of verifier_state and compared.
>
> Different hash table sizes and different hash functions were explored,
> but the results were not significantly better vs this patch.
> They can be improved in the future.
>
> Hit/miss heuristic is not counting index miscompare as a miss.
> Otherwise verifier stats become unstable when experimenting
> with different hash functions.
>
> Signed-off-by: Alexei Starovoitov <ast@kernel.org>
> ---
>  include/linux/bpf_verifier.h |  1 +
>  kernel/bpf/verifier.c        | 23 ++++++++++++++++++-----
>  2 files changed, 19 insertions(+), 5 deletions(-)
>
> diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
> index 02bba09a0ea1..405b502283c5 100644
> --- a/include/linux/bpf_verifier.h
> +++ b/include/linux/bpf_verifier.h
> @@ -187,6 +187,7 @@ struct bpf_func_state {
>  struct bpf_verifier_state {
>         /* call stack tracking */
>         struct bpf_func_state *frame[MAX_CALL_FRAMES];
> +       u32 insn_idx;
>         u32 curframe;
>         u32 active_spin_lock;
>         bool speculative;
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 89097a4b1bf3..082f6eefb1c4 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -5435,11 +5435,19 @@ enum {
>         BRANCH = 2,
>  };
>
> +static u32 state_htab_size(struct bpf_verifier_env *env)

maybe mark it as inline function? it's called pretty heavily.

> +{
> +       return env->prog->len;
> +}
> +
>  static struct bpf_verifier_state_list **explored_state(
>                                         struct bpf_verifier_env *env,
>                                         int idx)
>  {
> -       return &env->explored_states[idx];
> +       struct bpf_verifier_state *cur = env->cur_state;
> +       struct bpf_func_state *state = cur->frame[cur->curframe];
> +
> +       return &env->explored_states[(idx ^ state->callsite) % state_htab_size(env)];

% is slow, see [1] for faster alternative.

Alternatively, if you can make sure that hash size is power of two,
then multiplicative Fibonacci hashing is preferred ([2]).

[1] https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/
[2] https://probablydance.com/2018/06/16/fibonacci-hashing-the-optimization-that-the-world-forgot-or-a-better-alternative-to-integer-modulo/

>  }
>
>  static void init_explored_state(struct bpf_verifier_env *env, int idx)
> @@ -6018,7 +6026,8 @@ static void clean_live_states(struct bpf_verifier_env *env, int insn,
>
>         sl = *explored_state(env, insn);
>         while (sl) {
> -               if (sl->state.curframe != cur->curframe)
> +               if (sl->state.insn_idx != insn ||
> +                   sl->state.curframe != cur->curframe)
>                         goto next;
>                 for (i = 0; i <= cur->curframe; i++)
>                         if (sl->state.frame[i]->callsite != cur->frame[i]->callsite)
> @@ -6384,6 +6393,9 @@ static int is_state_visited(struct bpf_verifier_env *env, int insn_idx)
>         clean_live_states(env, insn_idx, cur);
>
>         while (sl) {
> +               states_cnt++;
> +               if (sl->state.insn_idx != insn_idx)
> +                       goto next;

Shouldn't this be checked inside states_equal? Or you are trying to
avoid function call overhead? If the latter is the case, then you
should probably compare curframe as well here?

>                 if (states_equal(env, &sl->state, cur)) {
>                         sl->hit_cnt++;
>                         /* reached equivalent register/stack state,
> @@ -6401,7 +6413,6 @@ static int is_state_visited(struct bpf_verifier_env *env, int insn_idx)
>                                 return err;
>                         return 1;
>                 }
> -               states_cnt++;
>                 sl->miss_cnt++;
>                 /* heuristic to determine whether this state is beneficial
>                  * to keep checking from state equivalence point of view.
> @@ -6428,6 +6439,7 @@ static int is_state_visited(struct bpf_verifier_env *env, int insn_idx)
>                         sl = *pprev;
>                         continue;
>                 }
> +next:
>                 pprev = &sl->next;
>                 sl = *pprev;
>         }
> @@ -6459,6 +6471,7 @@ static int is_state_visited(struct bpf_verifier_env *env, int insn_idx)
>                 kfree(new_sl);
>                 return err;
>         }
> +       new->insn_idx = insn_idx;
>         new_sl->next = *explored_state(env, insn_idx);
>         *explored_state(env, insn_idx) = new_sl;
>         /* connect new state to parentage chain. Current frame needs all
> @@ -8138,7 +8151,7 @@ static void free_states(struct bpf_verifier_env *env)
>         if (!env->explored_states)
>                 return;
>
> -       for (i = 0; i < env->prog->len; i++) {
> +       for (i = 0; i < state_htab_size(env); i++) {
>                 sl = env->explored_states[i];
>
>                 while (sl) {
> @@ -8246,7 +8259,7 @@ int bpf_check(struct bpf_prog **prog, union bpf_attr *attr,
>                         goto skip_full_check;
>         }
>
> -       env->explored_states = kvcalloc(env->prog->len,
> +       env->explored_states = kvcalloc(state_htab_size(env),
>                                        sizeof(struct bpf_verifier_state_list *),
>                                        GFP_USER);
>         ret = -ENOMEM;
> --
> 2.20.0
>

Re: [PATCH bpf-next 3/3] bpf: convert explored_states to hash table

[Alexei Starovoitov]

On Tue, May 21, 2019 at 05:55:06PM -0700, Andrii Nakryiko wrote:
> On Tue, May 21, 2019 at 4:08 PM Alexei Starovoitov <ast@kernel.org> wrote:
> >
> > All prune points inside a callee bpf function most likely will have
> > different callsites. For example, if function foo() is called from
> > two callsites the half of explored states in all prune points in foo()
> > will be useless for subsequent walking of one of those callsites.
> > Fortunately explored_states pruning heuristics keeps the number of states
> > per prune point small, but walking these states is still a waste of cpu
> > time when the callsite of the current state is different from the callsite
> > of the explored state.
> >
> > To improve pruning logic convert explored_states into hash table and
> > use simple insn_idx ^ callsite hash to select hash bucket.
> > This optimization has no effect on programs without bpf2bpf calls
> > and drastically improves programs with calls.
> > In the later case it reduces total memory consumption in 1M scale tests
> > by almost 3 times (peak_states drops from 5752 to 2016).
> >
> > Care should be taken when comparing the states for equivalency.
> > Since the same hash bucket can now contain states with different indices
> > the insn_idx has to be part of verifier_state and compared.
> >
> > Different hash table sizes and different hash functions were explored,
> > but the results were not significantly better vs this patch.
> > They can be improved in the future.
> >
> > Hit/miss heuristic is not counting index miscompare as a miss.
> > Otherwise verifier stats become unstable when experimenting
> > with different hash functions.
> >
> > Signed-off-by: Alexei Starovoitov <ast@kernel.org>
> > ---
> >  include/linux/bpf_verifier.h |  1 +
> >  kernel/bpf/verifier.c        | 23 ++++++++++++++++++-----
> >  2 files changed, 19 insertions(+), 5 deletions(-)
> >
> > diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
> > index 02bba09a0ea1..405b502283c5 100644
> > --- a/include/linux/bpf_verifier.h
> > +++ b/include/linux/bpf_verifier.h
> > @@ -187,6 +187,7 @@ struct bpf_func_state {
> >  struct bpf_verifier_state {
> >         /* call stack tracking */
> >         struct bpf_func_state *frame[MAX_CALL_FRAMES];
> > +       u32 insn_idx;
> >         u32 curframe;
> >         u32 active_spin_lock;
> >         bool speculative;
> > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> > index 89097a4b1bf3..082f6eefb1c4 100644
> > --- a/kernel/bpf/verifier.c
> > +++ b/kernel/bpf/verifier.c
> > @@ -5435,11 +5435,19 @@ enum {
> >         BRANCH = 2,
> >  };
> >
> > +static u32 state_htab_size(struct bpf_verifier_env *env)
> 
> maybe mark it as inline function? it's called pretty heavily.

The kernel convention is no 'inline' in .c

> >  static struct bpf_verifier_state_list **explored_state(
> >                                         struct bpf_verifier_env *env,
> >                                         int idx)
> >  {
> > -       return &env->explored_states[idx];
> > +       struct bpf_verifier_state *cur = env->cur_state;
> > +       struct bpf_func_state *state = cur->frame[cur->curframe];
> > +
> > +       return &env->explored_states[(idx ^ state->callsite) % state_htab_size(env)];
> 
> % is slow, see [1] for faster alternative.
> 
> Alternatively, if you can make sure that hash size is power of two,
> then multiplicative Fibonacci hashing is preferred ([2]).
> 
> [1] https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/
> [2] https://probablydance.com/2018/06/16/fibonacci-hashing-the-optimization-that-the-world-forgot-or-a-better-alternative-to-integer-modulo/

a % b -> ((u64) a * (u64) b) >> 32 transformation assumes good
distribution of 'a'. Here it's clearly not the case.
According to Jakub's analysis the verifier marks every 4th insn
as prune_point, so this array is only quarter full.
As an experiment I've tried to shrink the size by three times and
didn't observe any significant slowdown in verification time,
but decided to keep it as-is for simplicity.
For the same reasons I avoided roundup_to_power2.
I prefer readability vs microptimization.
The cost of modulo vs multiple alu is a noise
considering everything the verifier is doing.

> >  }
> >
> >  static void init_explored_state(struct bpf_verifier_env *env, int idx)
> > @@ -6018,7 +6026,8 @@ static void clean_live_states(struct bpf_verifier_env *env, int insn,
> >
> >         sl = *explored_state(env, insn);
> >         while (sl) {
> > -               if (sl->state.curframe != cur->curframe)
> > +               if (sl->state.insn_idx != insn ||
> > +                   sl->state.curframe != cur->curframe)
> >                         goto next;
> >                 for (i = 0; i <= cur->curframe; i++)
> >                         if (sl->state.frame[i]->callsite != cur->frame[i]->callsite)
> > @@ -6384,6 +6393,9 @@ static int is_state_visited(struct bpf_verifier_env *env, int insn_idx)
> >         clean_live_states(env, insn_idx, cur);
> >
> >         while (sl) {
> > +               states_cnt++;
> > +               if (sl->state.insn_idx != insn_idx)
> > +                       goto next;
> 
> Shouldn't this be checked inside states_equal? Or you are trying to
> avoid function call overhead? If the latter is the case, then you
> should probably compare curframe as well here?

It's not equivalent.
Here is what commit log say:
 Hit/miss heuristic is not counting index miscompare as a miss.
 Otherwise verifier stats become unstable when experimenting
 with different hash functions.

If insn comparison is done inside states_equal() then
miss > hit * 3 + 3 heuristic affects 'collisions'.
The cases where different indices fall into the same bucket.
And verifier stats fluctuate when hash function or size changes.

Re: [PATCH bpf-next 3/3] bpf: convert explored_states to hash table

[Andrii Nakryiko]

On Tue, May 21, 2019 at 7:17 PM Alexei Starovoitov
<alexei.starovoitov@gmail.com> wrote:
>
> On Tue, May 21, 2019 at 05:55:06PM -0700, Andrii Nakryiko wrote:
> > On Tue, May 21, 2019 at 4:08 PM Alexei Starovoitov <ast@kernel.org> wrote:
> > >
> > > All prune points inside a callee bpf function most likely will have
> > > different callsites. For example, if function foo() is called from
> > > two callsites the half of explored states in all prune points in foo()
> > > will be useless for subsequent walking of one of those callsites.
> > > Fortunately explored_states pruning heuristics keeps the number of states
> > > per prune point small, but walking these states is still a waste of cpu
> > > time when the callsite of the current state is different from the callsite
> > > of the explored state.
> > >
> > > To improve pruning logic convert explored_states into hash table and
> > > use simple insn_idx ^ callsite hash to select hash bucket.
> > > This optimization has no effect on programs without bpf2bpf calls
> > > and drastically improves programs with calls.
> > > In the later case it reduces total memory consumption in 1M scale tests
> > > by almost 3 times (peak_states drops from 5752 to 2016).
> > >
> > > Care should be taken when comparing the states for equivalency.
> > > Since the same hash bucket can now contain states with different indices
> > > the insn_idx has to be part of verifier_state and compared.
> > >
> > > Different hash table sizes and different hash functions were explored,
> > > but the results were not significantly better vs this patch.
> > > They can be improved in the future.
> > >
> > > Hit/miss heuristic is not counting index miscompare as a miss.
> > > Otherwise verifier stats become unstable when experimenting
> > > with different hash functions.
> > >
> > > Signed-off-by: Alexei Starovoitov <ast@kernel.org>
> > > ---
> > >  include/linux/bpf_verifier.h |  1 +
> > >  kernel/bpf/verifier.c        | 23 ++++++++++++++++++-----
> > >  2 files changed, 19 insertions(+), 5 deletions(-)
> > >
> > > diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
> > > index 02bba09a0ea1..405b502283c5 100644
> > > --- a/include/linux/bpf_verifier.h
> > > +++ b/include/linux/bpf_verifier.h
> > > @@ -187,6 +187,7 @@ struct bpf_func_state {
> > >  struct bpf_verifier_state {
> > >         /* call stack tracking */
> > >         struct bpf_func_state *frame[MAX_CALL_FRAMES];
> > > +       u32 insn_idx;
> > >         u32 curframe;
> > >         u32 active_spin_lock;
> > >         bool speculative;
> > > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> > > index 89097a4b1bf3..082f6eefb1c4 100644
> > > --- a/kernel/bpf/verifier.c
> > > +++ b/kernel/bpf/verifier.c
> > > @@ -5435,11 +5435,19 @@ enum {
> > >         BRANCH = 2,
> > >  };
> > >
> > > +static u32 state_htab_size(struct bpf_verifier_env *env)
> >
> > maybe mark it as inline function? it's called pretty heavily.
>
> The kernel convention is no 'inline' in .c

Ah, ok.

>
> > >  static struct bpf_verifier_state_list **explored_state(
> > >                                         struct bpf_verifier_env *env,
> > >                                         int idx)
> > >  {
> > > -       return &env->explored_states[idx];
> > > +       struct bpf_verifier_state *cur = env->cur_state;
> > > +       struct bpf_func_state *state = cur->frame[cur->curframe];
> > > +
> > > +       return &env->explored_states[(idx ^ state->callsite) % state_htab_size(env)];
> >
> > % is slow, see [1] for faster alternative.
> >
> > Alternatively, if you can make sure that hash size is power of two,
> > then multiplicative Fibonacci hashing is preferred ([2]).
> >
> > [1] https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/
> > [2] https://probablydance.com/2018/06/16/fibonacci-hashing-the-optimization-that-the-world-forgot-or-a-better-alternative-to-integer-modulo/
>
> a % b -> ((u64) a * (u64) b) >> 32 transformation assumes good
> distribution of 'a'. Here it's clearly not the case.
> According to Jakub's analysis the verifier marks every 4th insn
> as prune_point, so this array is only quarter full.
> As an experiment I've tried to shrink the size by three times and
> didn't observe any significant slowdown in verification time,
> but decided to keep it as-is for simplicity.
> For the same reasons I avoided roundup_to_power2.
> I prefer readability vs microptimization.
> The cost of modulo vs multiple alu is a noise
> considering everything the verifier is doing.
>

Fair enough, it's totally a microoptimization.

> > >  }
> > >
> > >  static void init_explored_state(struct bpf_verifier_env *env, int idx)
> > > @@ -6018,7 +6026,8 @@ static void clean_live_states(struct bpf_verifier_env *env, int insn,
> > >
> > >         sl = *explored_state(env, insn);
> > >         while (sl) {
> > > -               if (sl->state.curframe != cur->curframe)
> > > +               if (sl->state.insn_idx != insn ||
> > > +                   sl->state.curframe != cur->curframe)
> > >                         goto next;
> > >                 for (i = 0; i <= cur->curframe; i++)
> > >                         if (sl->state.frame[i]->callsite != cur->frame[i]->callsite)
> > > @@ -6384,6 +6393,9 @@ static int is_state_visited(struct bpf_verifier_env *env, int insn_idx)
> > >         clean_live_states(env, insn_idx, cur);
> > >
> > >         while (sl) {
> > > +               states_cnt++;
> > > +               if (sl->state.insn_idx != insn_idx)
> > > +                       goto next;
> >
> > Shouldn't this be checked inside states_equal? Or you are trying to
> > avoid function call overhead? If the latter is the case, then you
> > should probably compare curframe as well here?
>
> It's not equivalent.
> Here is what commit log say:

Ah, my bad, forgot about that by the time I got to the code. Might be
a good idea to put this in comments in the code.

>  Hit/miss heuristic is not counting index miscompare as a miss.
>  Otherwise verifier stats become unstable when experimenting
>  with different hash functions.
>
> If insn comparison is done inside states_equal() then
> miss > hit * 3 + 3 heuristic affects 'collisions'.
> The cases where different indices fall into the same bucket.
> And verifier stats fluctuate when hash function or size changes.
>

Yeah, that make sense. I wonder if curframe comparison has similar
effect, states from different frames seem similar to hash collisions
between different instruction states in that regard. Or they are not?

Re: [PATCH bpf-next 3/3] bpf: convert explored_states to hash table

[Alexei Starovoitov]

On 5/21/19 9:09 PM, Andrii Nakryiko wrote:
> 
>>   Hit/miss heuristic is not counting index miscompare as a miss.
>>   Otherwise verifier stats become unstable when experimenting
>>   with different hash functions.
>>
>> If insn comparison is done inside states_equal() then
>> miss > hit * 3 + 3 heuristic affects 'collisions'.
>> The cases where different indices fall into the same bucket.
>> And verifier stats fluctuate when hash function or size changes.
>>
> 
> Yeah, that make sense. I wonder if curframe comparison has similar
> effect, states from different frames seem similar to hash collisions
> between different instruction states in that regard. Or they are not?

Since curframe is not part of the hash it doesn't have such property.