In a previous article, I explained how Linux implements an IPv6 routing table. The following graph shows the performance progression of route lookups through Linux history:
All kernels are compiled with GCC 4.9 (from Debian Jessie). This version is
able to compile older kernels as well as current ones. The kernel configuration
is the default one with
CONFIG_IPV6_SUBTREES options enabled. Some
other unrelated options are enabled to be able to boot them in a virtual machine
and run the benchmark.
There are three notable performance changes:
- In Linux 3.1, Eric Dumazet delays a bit the copy of route metrics to fix the undesirable sharing of route-specific metrics by all cache entries (commit 21efcfa0ff27). Each cache entry now gets its own metrics, which explains the performance hit for the non-/128 scenarios.
- In Linux 3.9, Yoshifuji Hideaki removes the reference to the neighbor
struct rt6_info(commit 887c95cc1da5). This should have lead to a performance increase. The small regression may be due to cache-related issues.
- In Linux 4.2, Martin KaFai Lau prevents the creation of cache entries for most route lookups. The most sensible performance improvement comes with commit 4b32b5ad31a6. The second one is from commit 45e4fd26683c, which effectively removes creation of cache entries, except for PMTU exceptions.
Here is a graph for more recent kernels. Measures were performed on an Intel Xeon Gold 61481 running at 2.4 GHz, with GCC 6.3 from Debian Stretch. Performance regressions in 4.4.147 and 4.9.119 are solely due to the Spectre mitigations.2 The small performance increase in Linux 4.14 is from my own commit feca7d8c135b which optimizes the case without custom routing rules. In Linux 4.15, the most notable improvement can be traced to commit 66f5d6ce53e6: Wei Wang replaces the read-write lock by an RCU and a spinlock. In Linux 4.18, David Ahern improved the data structures used by route lookup. While the gain is meager, this should bring more performance improvements in the future. This also allows a fairer comparison between IPv4 and IPv6.