bpf: remove unnecessary prune and jump points
authorAndrii Nakryiko <andrii@kernel.org>
Tue, 6 Dec 2022 23:33:45 +0000 (15:33 -0800)
committerAlexei Starovoitov <ast@kernel.org>
Wed, 7 Dec 2022 03:14:38 +0000 (19:14 -0800)
commit618945fbed501b6e5865042068a51edfb2dda948
tree689b83e87a95688dbb7412a773ce0cf1d07ab4d0
parenta095f421057e22853022cb644b1589d0dd0e756e
bpf: remove unnecessary prune and jump points

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. See get_prev_insn_idx(). It goes back linearly by
one instruction, unless current top of jmp_history is pointing to
current instruction. In such case we use `st->jmp_history[cnt - 1].prev_idx`
to find instruction from which we jumped to the current instruction
non-linearly.

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.

Signed-off-by: Andrii Nakryiko <andrii@kernel.org>
Acked-by: John Fastabend <john.fastabend@gmail.com>
Link: https://lore.kernel.org/r/20221206233345.438540-4-andrii@kernel.org
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
kernel/bpf/verifier.c