Re: [PATCH RFC net-next 1/4] ipv4: fib_rules: support match on sport, dport and ip proto

From: Roopa Prabhu <redacted>
Date: Tue, 13 Feb 2018 08:19:35 -0800

- Regardless of this series, I think we should optimize ip rules or
have a new implementation of policy based routing. happy to hear about
possible options here:
         - optimize the existing implementation (have there been
previous discussions on possible options ?)
         - @netdev2.2, I did outline a possible option for tc to
provide an l3 hook for policy based routing (people were ok with this
and I was told more tc hooks were in the works).
            tc was a choice mainly because of all its existing match
options (flower for example). Will that help ?
         - We should have an ebpf accelerated implementation
regardless for people to use it if they want to scale rules

The problem is that arbitrary prefixing in the rules.  That prevents
O(1) algorithms from being used to maintain the table.

If they were all just non-prefixed keys we could do a hash table or
similar.

I guess we could do a trie (on saddr) to a (on daddr) trie (like the
ipv6 subtrees do), but that's a lot of complexity just for fib rules.