Performance evolution of route lookup on Linux

In pre­vi­ous ar­ti­cles, I ex­plained how the Linux ker­nel im­ple­ments IPv4[1] and IPv6[2] rout­ing ta­bles, and I showed the per­for­mance im­prove­ment of route lookups from Linux 2.6.32 to 4.16 for IPv4[3]—in­clud­ing the im­pact of the Melt­down and Spec­tre mit­i­ga­tions[4]—as well as from Linux 2.6.39 to 4.18 for IPv6[5]. This ar­ti­cle up­dates the num­bers through Linux 7.3 and in­ves­ti­gates the per­pe­tra­tor re­spon­si­ble for the per­for­mance re­gressions! 🕵️‍♂️

I ran the fol­low­ing bench­marks on an AMD EPYC 8024P[6], a Zen 4c CPU[7], rented from Scale­way[8], run­ning at 2.4 GHz with CPU boost dis­abled. I com­piled the ker­nels with GCC 10.2: this ver­sion can com­pile older ker­nels as well as the cur­rent ones.

IPv6

!Performance evolution of IPv6 route lookups from Linux 4.14 to 7.3

I tested four scenarios:

• a re­cent full view with about 260,000 prefixes,

• a full view from 2017 with about 40,000 prefixes,

• a set of 40,000 /48 pre­fixes, such that 2 lookups out of 3 match, and

• a set of 40,000 ran­dom /128 pre­fixes, such that 1 lookup out of 400 matches.

In Linux 4.15, Wei Wang im­proved the lookup per­for­mance by re­plac­ing the read-write lock with an RCU and a spin­lock in com­mit 66f5d6ce53e6[9]. In Linux 4.18, David Ah­ern im­proved the data struc­tures used by route lookup[10]. In Linux 5.9, Brian Vazquez re­moved ex­pen­sive in­di­rect calls in com­mit 55cced4f813b[11].

The ma­jor 200 ns re­gres­sion in­tro­duced in Linux 6.5 wiped out all these im­prove­ments. This ver­sion im­ple­ments a mit­i­ga­tion for “Spec­u­la­tive Re­turn Stack Over­flow[12],” a vul­ner­a­bil­ity af­fect­ing AMD pro­ces­sors, in com­mit fb3bd914b3ec[13]. This mit­i­ga­tion adds about 20 cy­cles on each func­tion re­turn. It was back­ported to older ker­nels (5.10, 5.15, 6.1, and 6.4). To keep the re­sults leg­i­ble, I dis­abled the mit­i­ga­tion for these ver­sions with spec_​rstack_​overflow=​off on the ker­nel com­mand-line.

You can check the vul­ner­a­bil­i­ties im­pact­ing your CPU and their mit­i­ga­tions with lscpu. Some mit­i­ga­tions may de­pend on the mi­crocode or on the firmware.1

        $ lscpu | grep '^Vuln'
Vulnerability Gather data sampling:      Not affected
Vulnerability Indirect target selection: Not affected
Vulnerability Itlb multihit:             Not affected
Vulnerability L1tf:                      Not affected
Vulnerability Mds:                       Not affected
Vulnerability Meltdown:                  Not affected
Vulnerability Mmio stale data:           Not affected
Vulnerability Reg file data sampling:    Not affected
Vulnerability Retbleed:                  Not affected
Vulnerability Spec rstack overflow:      Mitigation; Safe RET
Vulnerability Spec store bypass:         Mitigation; Speculative Store Bypass disabled via prctl
Vulnerability Spectre v1:                Mitigation; usercopy/swapgs barriers and __user pointer sanitization
Vulnerability Spectre v2:                Mitigation; Retpolines; IBPB conditional; IBRS_FW; STIBP always-on; RSB filling; PBRSB-eIBRS Not affected; BHI Not affected
Vulnerability Srbds:                     Not affected
Vulnerability Tsa:                       Vulnerable: Clear CPU buffers attempted, no microcode
Vulnerability Tsx async abort:           Not affected
Vulnerability Vmscape:                   Mitigation; IBPB before exit to userspace
      

IPv4

!Performance evolution of IPv4 route lookups from Linux 4.14 to 7.3

I tested three scenarios:

• a re­cent full view with more than 1,000,000 prefixes,

• a sub­set of a full view from 2017 with 500,000 pre­fixes, and

• a set of 500,000 con­tigu­ous /32 prefixes.

The 30 ns im­pact of the mit­i­ga­tion for SRSO in Linux 6.5 is smaller than for IPv6 be­cause IPv4 route lookups tra­verse fewer func­tions: around 4 func­tion calls for IPv4 com­pared to 25 for IPv6.

In Linux 5.11, I in­tro­duced a re­gres­sion in com­mit c0c5a60f0f13[17] af­ter fix­ing the be­hav­ior of net.​ipv4.​conf.​all.​ignore_​routes_​with_​linkdown!2 As a re­sult, the ip_​ignore_​linkdown()[18] func­tion spends around 5 ad­di­tional cy­cles to re­turn a re­sult as it needs to fol­low three ad­di­tional point­ers. fib_​lookup()[19] even­tu­ally calls it in the fol­low­ing code[20]:

        if (ip_ignore_linkdown(nhc->nhc_dev) &&
    nhc->nhc_flags & RTNH_F_LINKDOWN &&
    !(fib_flags & FIB_LOOKUP_IGNORE_LINKSTATE))
    return false;
      

If we re­order the con­di­tions, we avoid call­ing ip_​ignore_​linkdown() for the most com­mon case where the link isn’t down:

        if (nhc->nhc_flags & RTNH_F_LINKDOWN &&
    !(fib_flags & FIB_LOOKUP_IGNORE_LINKSTATE) &&
    ip_ignore_linkdown(nhc->nhc_dev))
    return false;
      

Here’s the dis­tri­bu­tion of lookup times be­fore ap­ply­ing the patch[22] on top of net-next:3

        min=128 max=4657 count=994104 95th=134 90th=133 50th=132 mad=0
    value │                         ┊                            count
      128 │                                                        120
      129 │                                                       2232
      130 │▒                                                     25224
      131 │▒▒▒▒▒▒▒▒▒▒▒▒▒░                                       264264
      132 │▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒░░░░░░░░░░░░░░░             516480
      133 │▒▒▒▒▒▒░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░      126864
      134 │▒░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░      21624
      

The lighter shade de­picts the cu­mu­la­tive dis­tri­bu­tion func­tion. Af­ter ap­ply­ing the patch, the me­dian im­proved from 132 to 126 cycles:4

        min=124 max=208839 count=994104 95th=128 90th=127 50th=126 mad=0
    value │                         ┊                            count
      124 │                                                        576
      125 │▒▒                                                    49440
      126 │▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒░░                      584904
      127 │▒▒▒▒▒▒▒▒▒▒▒▒▒▒░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░       284592
      128 │▒▒░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░      45288
      

Impact of mitigations

To re­duce the im­pact of mit­i­ga­tions, you can dis­able all of them with mitigations=​off, dis­able only a spe­cific one like with spec_​rstack_​overflow=​off, or pro­tect against only some at­tack vec­tors[23] with mitigations=​auto,no_​user_​kernel, start­ing from Linux 6.17.

The im­pact is also quite dif­fer­ent de­pend­ing on the CPU. For ex­am­ple, on a Xeon W-2295[24], an In­tel desk­top CPU from 2020, the im­pact of the mit­i­ga­tions is only a few cy­cles for IPv4, and less than 3% for IPv6. The main con­trib­u­tor is the mit­i­ga­tion for the In­di­rect Tar­get Se­lec­tion[25] vul­ner­a­bil­ity, which is fixed since the Sap­phire Rapids[26] ar­chi­tecture.

If we set aside the re­gres­sions in­tro­duced by the mit­i­ga­tions against CPU at­tacks[27], the per­for­mance of IPv4 is de­clin­ing slowly over time while IPv6 has im­proved in the past and is cur­rently sta­ble. If rout­ing per­for­mance is im­por­tant, you have sev­eral op­tions: choose a dif­fer­ent CPU like an AMD Zen 5 CPU[28], a fourth gen­er­a­tion Xeon CPU[26], or maybe an ARM Neo­verse V2[29]; dis­able some or all the mit­i­ga­tions; by­pass rout­ing with XDP/eBPF;5 or off­load rout­ing[30] to the net­work card.

Maytham Al­su­dany[32] re­viewed a first draft of this ar­ti­cle. Any er­rors are still mine!

• https://vincent.bernat.ch/en/blog/2017-ipv4-route-lookup-linux

• https://vincent.bernat.ch/en/blog/2017-ipv6-route-lookup-linux

• https://vincent.bernat.ch/en/blog/2017-performance-progression-ipv4-route-lookup-linux

• https://meltdownattack.com/

• https://vincent.bernat.ch/en/blog/2017-performance-progression-ipv6-route-lookup-linux

• https://www.amd.com/en/products/processors/server/epyc/4th-generation-9004-and-8004-series/amd-epyc-8024p.html

• https://en.wikipedia.org/wiki/Zen_4#Zen_4c

• https://www.scaleway.com/en/elastic-metal/

• https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/commit/?id=66f5d6ce53e665477d2a33e8f539d4fa4ca81c83

• https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/commit/?id=0565de29cbd65b378147d36f9642f93a046240dc

• https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/commit/?id=55cced4f813bece01f96256d96f283b9210d19ee

• https://docs.kernel.org/admin-guide/hw-vuln/srso.html

• https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/commit/?id=fb3bd914b3ec28f5fb697ac55c4846ac2d542855

• https://www.amd.com/en/resources/product-security/bulletin/amd-sb-7029.html

• https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/commit/?id=e7862eda309ecfccc36bb5558d937ed3ace07f3f

• https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/commit/?id=acaa4b5c4c854b5009f4d4a5395b2609ad0f4937

• https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/commit/?id=c0c5a60f0f1311bcf08bbe735122096d6326fb5b

• https://elixir.bootlin.com/linux/v7.3.1/source/include/linux/inetdevice.h#L265

• https://elixir.bootlin.com/linux/v7.3.1/source/include/net/ip_fib.h#L374

• https://elixir.bootlin.com/linux/v7.3.1/source/net/ipv4/fib_trie.c#L1406

• https://elixir.bootlin.com/linux/v7.3.1/source/net/ipv6/addrconf.c#L940

• https://git.kernel.org/pub/scm/linux/kernel/git/netdev/net-next.git/commit/?id=5fe3653f13b9d0549d8e8f6c181cf2dcbc67b06a

• https://docs.kernel.org/admin-guide/hw-vuln/attack_vector_controls.html

• https://www.intel.com/content/www/us/en/products/sku/198011/intel-xeon-w2295-processor-24-75m-cache-3-00-ghz/specifications.html

• https://docs.kernel.org/admin-guide/hw-vuln/indirect-target-selection.html

• https://en.wikipedia.org/wiki/Sapphire_Rapids

• https://docs.kernel.org/admin-guide/hw-vuln/

• https://en.wikipedia.org/wiki/Zen_5

• https://en.wikipedia.org/wiki/ARM_Neoverse#Neoverse_V2

• https://www.gtp-guard.org/articles/5g-upf-pump-up-the-volume/

• https://docs.ebpf.io/linux/helper-function/bpf_fib_lookup/

• https://maytham.aezign.au/