This change introduces loadable route lookup modules based on DPDK rte_lpm lib targeted for high-speed lookups in large-scale tables.
It is based on the lookup framework described in D27401.
IPv4 module is called dpdk_lpm4. It wraps around rte_lpm, which implement variation of DIR24-8 lookup algorithm. Module provide lockless route lookups and in-place incremental updates, allowing for good RIB performance.
IPv6 module is called dpdk_lpm6. It wraps around rte_lpm6.
Implementation can be seen as multi-bit trie where the stride or number of bits inspected on each level varies from level to level.... It can vary from 1 to 14 memory accesses, with 5 being the average value for the lengths that are most commonly used in IPv6.. Module provide lockless route lookups for global unicast addresses and in-place incremental updates, allowing for good RIB performance.
Implementation details:
- wrapper code lives in sys/contrib/dpdk_rte_lpm/dpdk_lpm[6].c.
- rte_lpm[6] implementation contains both RIB ("rule_" code, backed by array of hash tables) and fib code. RIB code part has been commented out, as base radix already provides all the necessary primitives.
- link-local lookups are currently implemented as base radix lookup. This part should be converted to something like read-only radix trie.