[PATCH 2/3] bfp: fix load hangs with six IPv6 addresses

[Stephen Hemminger]

On Thu, 27 Jun 2024 12:55:30 +0100
Konstantin Ananyev <konstantin.v.ananyev at yandex.ru> wrote:
> From: Konstantin Ananyev <konstantin.ananyev at huawei.com>
> 
> As described in: https://bugs.dpdk.org/show_bug.cgi?id=1465
> converting from following cBPF filter:
> "host 1::1 or host 1::1 or host 1::1 or host 1::1 or host 1::1 or host 1::1"
> taking too long for BPF verifier ito complete (up to 25 seconds).
> Looking at it I didn't find any actual functional bug.
> In fact, it does what is expected: goes through each possible path of
> BPF program and evaluates register/stack state for each instruction.
> The problem is that for program with a lot of conditional branches number
> of possible paths starts to grow exponentially and such walk becomes very
> excessive.
> So  to minimize number of evaluations, this patch implements heuristic
> similar to what Linux kernel does - state pruning:
> If from given instruction for given program state we explore all possible
> paths and for each of them reach bpf_exit() without any complaints and a
> valid R0 value, then for that instruction this program state can be
> marked as 'safe'. When we later arrive at the same instruction with a state
> equivalent to an earlier instruction 'safe' state, we can prune the search.
> For now, only states for JCC  targets are saved/examined.
> Plus added few extra logging for DEBUG level.
> 
> Bugzilla ID: 1465
> Fixes: 8021917293d0 ("bpf: add extra validation for input BPF program")
> Cc: stable at dpdk.org

Acked-by: Stephen Hemminger <stephen at networkplumber.org>

> +		struct bpf_eval_state *cur;   /*save/restore for jcc targets */

Nit: should have space after /* in this comment