1. 背景
一直使用 ip rule 做国内国外 IP 的分流，策略路由规则也从 5000 多行增加到了现在的 8000 多行。尽管 Linux 路由查找算法已经十分先进了（从早期的 hash 表升级到了后来的 LPC-trie），但是仅限于具体路由表内规则的查找。完整的路由查找过程还需要进行策略路由的匹配，且策略路由是用链表进行存储的，因此 fib_lookup() (FIB, forwarding information base) 查找过程需要遍历所有的策略路由规则，这就带来了性能问题。
问题现象是，openwrt 19.07 的时候，数千条策略路由没有任何性能问题；
而升级到 openwrt 21.02 后发现查找性能极其缓慢，尤其是目标 IP 处在策略路由列表靠后的情况，跑几兆就能把 cpu 核心吃满；意外发现 flow offloading 可以解决这个问题，也就没有深入分析，但是这个疑惑一直在心里硌着；
直到近期升级到 openwrt 22.03，手里两个 MTK 设备的 software flow offloading 失效，不得不重新捡起这个问题。。。当然了，那个 software flow offloading 问题就留下一篇博客去讲了。
2. 测试
测试条件都是添加近 8000 条路由策略，目标 IP 的优先级需要尽量靠后，然后进行 NAT 转发性能测试，和本机 socket 收发性能测试（INPUT/OUTPUT）。
考虑到 openwrt 21.02 以来的大变更主要就是 DSA 交换机架构和 fw4/nftables，因此还拉上了一些 Linux 发行版，手动创建 iptables/nftables NAT 规则进行测试。
结果如下表，似乎和 Linux 内核、iptables/nftables 都没什么关系，而 19.07 没有性能问题反而是一个例外情况。实际上这个版本的 openwrt 也没什么黑科技，没有 fastpath，没有 shortcut-fe，也没有打开 flow offloading， 甚至清空 openwrt 默认的 iptables 规则，手敲一行 SNAT 一样跑的很欢。。。
| system | kernel | iptables / nftables | NAT | NAT + FLOWOFFLOAD | INPUT/OUPUT |
|---|---|---|---|---|---|
| OpenWRT 19.07 | 4.14 | ipt | √ | √ | √ |
| OpenWRT 21.02 | 5.4 | nft | X | √ | √ |
| OpenWRT 22.03 | 5.10 | nft | X | √ | √ |
| Debian 9 | 4.9 | ipt | X | - | √ |
| Debian 10 | 4.19 | nft | X | - | √ |
| Debian 11 | 5.15 | nft | X | - | √ |
3. 分析总结
在揭晓答案之前，有必要简单回顾一下 Linux 路由查找的历史:
- Linux 2.6.39, commit 3630b7c0, 基于 hash 的路由查找算法（
cat /proc/net/rt_cache）被替换为 LPC-trie （cat /proc/net/fib_trie）。 - Linux 3.6, commit f4530fa5 优化了 ip rule 的查找逻辑，在没有策略路由条目的情况下，会跳过 rule 的查找过程； 更重要的一点是，commit 5e9965c1 移除了路由缓存 Routing Cache。
- Linux 4.1, commit 0ddcf43d, 继续优化 ip rule 查找逻辑，在没有策略路由条目的情况下，会合并 local 和 main 表，提高查找效率。
所以总的来说，在 3.6 版本内核移除了 Routing Cache 之后，对于大量 ip rule 的查找就进入了一个很低效的状态，直到现在也没有解决。而 openwrt 19.07 显然是对内核进行了一些 patch 来实现类似的功能，翻了一下 patch 列表 backport-4.14，前排的 020-backport_netfilter_rtcache.patch 非常显眼。
结论如下：
-
- OpenWRT 19.07 NAT 场景策略路由性能 OK 的核心原因是 netfilter_rtcache 这个补丁，缓存路由查找结果，提高 NAT 转发性能。且这个补丁未出现在后续的版本中，估计是因为 flow offload 从新的角度，更全面地解决了包转发性能问题，rtcache 不再那么有价值了。
-
- INPUT/OUTPUT 场景策略路由性能 OK 的原因是 socket 层面还有一层路由缓存，会将第一次路由查找的结果缓存在 struct sock 结构体中 (sk_dst_cache)
问题大概就分析到这里，其实还有很多细节没有提及，但是对于理解 Linux 路由查找过程非常有帮助，关键的几篇文章都贴在了参考资料中，强烈推荐阅读前三个链接。
4. Refer
- https://vincent.bernat.ch/en/blog/2017-performance-progression-ipv4-route-lookup-linux
- https://vincent.bernat.ch/en/blog/2017-ipv4-route-lookup-linux
- https://thermalcircle.de/doku.php?id=blog:linux:routing_decisions_in_the_linux_kernel_2_caching
- https://thermalcircle.de/doku.php?id=blog:linux:flowtables_1_a_netfilter_nftables_fastpath
- https://github.com/openwrt/openwrt/blob/openwrt-19.07/target/linux/generic/backport-4.14/020-backport_netfilter_rtcache.patch
- https://lore.kernel.org/all/[email protected]/T/