Re: [PATCH bpf-next] bpf, lpm: fix check prefixlen before walking trie

["David Rheinsberg" <david@readahead.eu>]

Hi

On Sun, Nov 5, 2023, at 9:33 PM, Florian Lehner wrote:
> On Sun, Nov 05, 2023 at 08:08:43PM +0100, David Rheinsberg wrote:
>> On Sun, Nov 5, 2023, at 9:58 AM, Florian Lehner wrote:
>> > When looking up an element in LPM trie, the condition 'matchlen ==
>> > trie->max_prefixlen' will never return true, if key->prefixlen is larger
>> > than trie->max_prefixlen. Consequently all elements in the LPM trie will
>> > be visited and no element is returned in the end.
>> 
>> Am I understanding you right that this is an optimization to avoid walking the entire trie? Because the way I read your commit-message I assume the output has always been NULL? Or am I missing something.
>> 
>> Do you have a specific use-case where such lookups are common? Can you explain why it is important to optimize this case? Because you now add a condition for every lookup just to optimize for the lookup-miss of a special case. I don't think I understand your reasoning here, but I might be missing some context.
>
> Your understanding is correct. The return value currently and with this patch is
> in both cases the same for the case where key->prefixlen > trie->max_prefixlen.

Thanks for clarifying! I think using "fix" to describe the patch is misleading and confused me. Similarly, your "Fixes:" tag implies you repaired something that was broken.

> The optimization is to avoid the locking mechanism, walking the trie and
> checking its elements. It might not be the most common use case, so I see your
> point.

Can you elaborate on how you encountered this? Do you have an actual use-case where such lookups better be fast? Is it worth it slowing down every other lookup just to make this one faster?

The patch looks good, but I also don't see the benefit. I am not against it, though, if you insist you need it.

Thanks
David