On Tue, Oct 22, 2024 at 7:52 PM Eduard Zingerman <eddyz87@xxxxxxxxx> wrote:
>
> On Mon, 2024-10-21 at 22:38 -0700, Eduard Zingerman wrote:
>
> [...]
>
> > This takes ~10 minutes to verify on master.
> > Surprisingly current patch does not seem to help,
> > I'll investigate this tomorrow.
> > Full example is in the end of the email.
>
[...]
> On master this fails with ENOMEM and the following error in the log:
>
Have you tried applying my insn_history optimization? It should
definitely avoid -ENOMEM, no? It still might be slow, but probably
much faster than that we have now. It would be nice if you can rebase
my old patch and land it (without any of the precision changes, that's
a second step).
> [ 418.083600] test_progs: page allocation failure: order:7, mode:0x140cc0(GFP_USER|__GFP_COMP), \
> nodemask=(null),cpuset=/,mems_allowed=0
> ...
> [ 418.084158] Call Trace:
> ...
> [ 418.084649] krealloc_noprof+0x53/0xd0
> [ 418.084688] copy_verifier_state+0x78/0x390
> ...
>
> Same happens if jmp_history_cnt check is moved to 'skip_inf_loop_check':
>
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -18022,7 +18022,7 @@ static int is_state_visited(struct bpf_verifier_env *env, int insn_idx)
> * at the end of the loop are likely to be useful in pruning.
> */
> skip_inf_loop_check:
> - if (!force_new_state &&
> + if (!force_new_state && cur->jmp_history_cnt < 40 &&
> env->jmps_processed - env->prev_jmps_processed < 20 &&
> env->insn_processed - env->prev_insn_processed < 100)
>
>
> Or if it is in the else branch. Simply because 'skip_inf_loop_check' is
> for instructions that have been already seen on the current verification path.
>
> However, with change suggested in this patch-set such ENOMEM situation
> is not possible. Hence I insist that large enough jmp_history_cnt
> should force a new state, and point where I put the check covers more
> cases then alternatives.
>
I think we are in agreement that jmp_history_cnt should cause a new
state. But ok, using force_new_state is fine by me, it actually allows
us to remove duplication of logic. But then let's do this (it gets
unwieldy to combine variable declaration and initialization, it's
non-trivial amount of logic, should be its own statement):
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 587a6c76e564..1f30ef99b246 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -17886,9 +17886,11 @@ static int is_state_visited(struct
bpf_verifier_env *env, int insn_idx)
struct bpf_verifier_state_list *sl, **pprev;
struct bpf_verifier_state *cur = env->cur_state, *new, *loop_entry;
int i, j, n, err, states_cnt = 0;
- bool force_new_state = env->test_state_freq ||
is_force_checkpoint(env, insn_idx);
- bool add_new_state = force_new_state;
- bool force_exact;
+ bool force_new_state, add_new_state, force_exact;
+
+ force_new_state = env->test_state_freq ||
+ is_force_checkpoint(env, insn_idx) ||
+ cur->jmp_history_cnt > 40;
/* bpf progs typically have pruning point every 4 instructions
* http://vger.kernel.org/bpfconf2019.html#session-1
@@ -17898,6 +17900,7 @@ static int is_state_visited(struct
bpf_verifier_env *env, int insn_idx)
* In tests that amounts to up to 50% reduction into total verifier
* memory consumption and 20% verifier time speedup.
*/
+ add_new_state = force_new_state;
if (env->jmps_processed - env->prev_jmps_processed >= 2 &&
env->insn_processed - env->prev_insn_processed >= 8)
add_new_state = true;
There is no need to adjust skip_inf_loop_check condition because it
will already work fine due to !force_new_state check there. No?
And I wouldn't elaborate *that* much in a comment about
jmp_history_cnt > 40. It's a heuristic, we keep jump history short
enough. Multi-line comment here is just distracting, IMO. I wouldn't
add MAX_JMPS_PER_STATE as well, it sounds way too "official". It's a
heuristic, not some sort of fundamental rule.
