Add modular fib lookup framework.
This change introduces framework that allows to dynamically
attach or detach longest prefix match (lpm) lookup algorithms
to speed up datapath route tables lookups.
Framework takes care of handling initial synchronisation,
route subscription, nhop/nhop groups reference and indexing,
dataplane attachments and fib instance algorithm setup/teardown.
Framework features automatic algorithm selection, allowing for
picking the best matching algorithm on-the-fly based on the
amount of routes in the routing table.
Currently framework code is guarded under FIB_ALGO config option.
An idea is to enable it by default in the next couple of weeks.
The following algorithms are provided by default:
- bsearch4 (lockless binary search in a special IP array), tailored for small-fib (<16 routes)
- radix4_lockless (lockless immutable radix, re-created on every rtable change), tailored for small-fib (<1000 routes)
- radix4 (base system radix backend)
- dpdk_lpm4 (DPDK DIR24-8-based lookups), lockless datastrucure, optimized for large-fib (D27412)
- radix6_lockless (lockless immutable radix, re-created on every rtable change), tailed for small-fib (<1000 routes)
- radix6 (base system radix backend)
- dpdk_lpm6 (DPDK DIR24-8-based lookups), lockless datastrucure, optimized for large-fib (D27412)
Micro benchmarks (I7-7660U, single-core lookups, 2048k dst, code in D27604):
radix4: ~20mpps radix4_lockless: ~24.8mpps bsearch4: ~69mpps dpdk_lpm4: ~67 mpps
radix4_lockless: 3.3mpps dpdk_lpm4: 46mpps
radix6_lockless: ~20mpps dpdk_lpm6: ~70mpps
radix6_lockless: 13.9mpps dpdk_lpm6: 57mpps
+ 10-15% IPv4 forwarding performance (small-fib, bsearch4)
+ 25% IPv4 forwarding performance (full-view, dpdk_lpm4)
+ 20% IPv6 forwarding performance (full-view, dpdk_lpm6)
Framwork adds the following runtime sysctls:
- net.route.algo.inet.algo_list: bsearch4, radix4_lockless, radix4
- net.route.algo.inet6.algo_list: radix6_lockless, radix6, dpdk_lpm6
Debug level (7=LOG_DEBUG, per-route)
Algo selection (currently only for fib 0):
Support for manually changing algos in non-default fib will be added
soon. Some sysctl names will be changed in the near future.
Differential Revision: https://reviews.freebsd.org/D27401