Remove residual blank line at start of MakefileThis is a residual of the $FreeBSD$ removal.MFC After: 3 days (though I'll just run the command on the branches)Sponsored by: Netflix
sys: Remove $FreeBSD$: one-line sh patternRemove /^\s*#[#!]?\s*\$FreeBSD\$.*$\n/
Introduce DXR as an IPv4 longest prefix matching / FIB moduleDXR maintains compressed lookup structures with a trivial searchprocedure. A two-stage trie is indexed by the more significant bits of
Introduce DXR as an IPv4 longest prefix matching / FIB moduleDXR maintains compressed lookup structures with a trivial searchprocedure. A two-stage trie is indexed by the more significant bits ofthe search key (IPv4 address), while the remaining bits are used forfinding the next hop in a sorted array. The tradeoff between memoryfootprint and search speed depends on the split between the trie andthe remaining binary search. The default of 20 bits of the key beingused for trie indexing yields good performance (see below) withfootprints of around 2.5 Bytes per prefix with current BGP snapshots.Rebuilding lookup structures takes some time, which is compensated for bybatching several RIB change requests into a single FIB update, i.e. FIBsynchronization with the RIB may be delayed for a fraction of a second.RIB to FIB synchronization, next-hop table housekeeping, and locklesslookup capability is provided by the FIB_ALGO infrastructure.DXR works well on modern CPUs with several MBytes of caches, especiallyin VMs, where is outperforms other currently available IPv4 FIBalgorithms by a large margin.Synthetic single-thread LPM throughput test method:kldload test_lookup; kldload dpdk_lpm4; kldload fib_dxrsysctl net.route.test.run_lps_rnd=Nsysctl net.route.test.run_lps_seq=Nwhere N is the number of randomly generated keys (IPv4 addresses) whichshould be chosen so that each test iteration runs for several seconds.Each reported score represents the best of three runs, in millionlookups per second (MLPS), for two bechmarks (RND & SEQ) with two FIBs:host: single interface address, local subnet route + default routeBGP: snapshot from linx.routeviews.org, 887957 prefixes, 496 next hopsBhyve VM on an Intel(R) Xeon(R) CPU E5-2670 0 @ 2.60 GHz:inet.algo host, RND host, SEQ BGP, RND BGP, SEQbsearch4 40.6 20.2 N/A N/Aradix4 7.8 3.8 1.2 0.6radix4_lockless 18.0 9.0 1.6 0.8dpdk_lpm4 14.4 5.0 14.6 5.0dxr 70.3 34.7 43.0 19.5Intel(R) Core(TM) i5-5300U CPU @ 2.30 GHz:inet.algo host, RND host, SEQ BGP, RND BGP, SEQbsearch4 47.0 23.1 N/A N/Aradix4 8.5 4.2 1.9 1.0radix4_lockless 19.2 9.5 2.5 1.2dpdk_lpm4 31.2 9.4 31.6 9.3dxr 84.9 41.4 51.7 23.6Intel(R) Core(TM) i7-4771 CPU @ 3.50 GHz:inet.algo host, RND host, SEQ BGP, RND BGP, SEQbsearch4 59.5 29.4 N/A N/Aradix4 10.8 5.5 2.5 1.3radix4_lockless 24.7 12.0 3.1 1.6dpdk_lpm4 29.1 9.0 30.2 9.1dxr 101.3 49.9 69.8 32.5AMD Ryzen 7 3700X 8-Core Processor @ 3.60 GHz:inet.algo host, RND host, SEQ BGP, RND BGP, SEQbsearch4 70.8 35.4 N/A N/Aradix4 14.4 7.2 2.8 1.4radix4_lockless 30.2 15.1 3.7 1.8dpdk_lpm4 29.9 9.0 30.0 8.9dxr 163.3 81.5 99.5 44.4AMD Ryzen 5 5600X 6-Core Processor @ 3.70 GHz:inet.algo host, RND host, SEQ BGP, RND BGP, SEQbsearch4 93.6 46.7 N/A N/Aradix4 18.9 9.3 4.3 2.1radix4_lockless 37.2 18.6 5.3 2.7dpdk_lpm4 51.8 15.1 51.6 14.9dxr 218.2 103.3 114.0 49.0Reviewed by: melifaroMFC after: 1 weekDifferential Revision: https://reviews.freebsd.org/D29821
show more ...