Re: [PATCH bpf-next v1 1/2] bpf: force checkpoints at loop back-edges

[Eduard Zingerman <eddyz87@gmail.com>]

On Thu, 2024-10-10 at 15:13 -0700, Andrii Nakryiko wrote:
> On Wed, Oct 9, 2024 at 6:09 PM Alexei Starovoitov

[...]

> > Something should be done about:
> >           71.25%        [k] __mark_chain_precision
> >           24.81%        [k] bt_sync_linked_regs
> > as well.
> > The algorithm there needs some tweaks.
> 
> If we were to store bpf_jmp_history_entry for each instruction (and we
> can do that efficiently, memory-wise, I had the patch), and then for
> each instruction we maintained a list of "input" regs/slots and
> corresponding "output" regs/slots as we simulate each instruction
> forward, I think __mark_chain_precision would be much simpler and thus
> faster. We'd basically just walk backwards instruction by instruction,
> check if any of the output regs/slots need to be precise (few bitmasks
> intersection), and if yes, set all input regs/slots as "need
> precision", and just continue forward.
> 
> I think it's actually a simpler approach and should be faster. Simpler
> because it's easy to tell inputs/outputs while doing forward
> instruction processing. Faster because __mark_chain_precision would
> only do very simple operation without lots of branching and checks.

I think this would bring significant speedup.
Not sure it would completely fix the issue at hand,
as mark_chain_precision() walks like 100 instructions back on each
iteration of the loop, but it might be a step in the right direction.

Do you mind if I refresh your old patches for jump history,
or do you want to work on this yourself?

[...]