Re: [PATCH bpf-next v2 0/7] exact states comparison for iterator convergence checks

[Eduard Zingerman <eddyz87@xxxxxxxxx>]

On Sun, 2023-10-22 at 04:08 +0300, Eduard Zingerman wrote:
[...]
> Changelog:
> V1 -> V2 [2], applied changes suggested by Alexei offlist:
> - __explored_state() function removed;
> - same_callsites() function is now used in clean_live_states();
> - patches #1,2 are added as preparatory code movement;
> - in process_iter_next_call() a safeguard is added to verify that
>   cur_st->parent exists and has expected insn index / call sites.

I have V3 ready and passing CI.

However I checked on Alexei's concerns regarding performance on
explored states cache miss and verifier does not behave well with this
patch-set. For example, the program at the end of the email causes
verifier to "hang" (loop inside is_state_visited() to no end).

There are several options to fix this:
(a) limit total iteration depth, as in [1], the limit would have to be
    at-least 1000 to make iters/task_vma pass;
(b) limit maximal number of checkpoint states associated with
    instruction and evict those with lowest dfs_depth;
(c) choose bigger constants in `sl->miss_cnt > sl->hit_cnt * 3 + 3` for
    checkpoint states.

Given that current failure mode is bad, should I submit V3 as-is or
should I explore options (b,c) and add one of those to V3?

[1] https://github.com/eddyz87/bpf/tree/bpf-iter-next-exact-widening-max-iter-depth

---

SEC("?raw_tp")
__failure
__naked int max_iter_depth(void)
{
	/* This is equivalent to C program below.
	 * The counter stored in r6 is used as precise after the loop,
	 * thus preventing widening. Verifier won't be able to conclude
	 * that such program terminates but it should gracefully exit.
	 *
	 * r6 = 0
	 * bpf_iter_num_new(&fp[-8], 0, 10)
	 * while (bpf_iter_num_next(&fp[-8])) {
	 *   r6 += 1;
	 * }
	 * bpf_iter_num_destroy(&fp[-8])
	 * ... force r6 precise ...
	 * return 0
	 */
	asm volatile (
		"r6 = 0;"
		"r1 = r10;"
		"r1 += -8;"
		"r2 = 0;"
		"r3 = 10;"
		"call %[bpf_iter_num_new];"
	"loop_%=:"
		"r1 = r10;"
		"r1 += -8;"
		"call %[bpf_iter_num_next];"
		"if r0 == 0 goto loop_end_%=;"
		"r6 += 1;"
		"goto loop_%=;"
	"loop_end_%=:"
		"r1 = r10;"
		"r1 += -8;"
		"call %[bpf_iter_num_destroy];"
		"r0 = r10;"
		"r0 += r6;" /* this forces r6 to be precise */
		"r0 = 0;"
		"exit;"
		:
		: __imm(bpf_iter_num_new),
		  __imm(bpf_iter_num_next),
		  __imm(bpf_iter_num_destroy)
		: __clobber_all
	);
}