Performance evolution of route lookup on Linux

Vincent Bernat

In pre­vi­ous ar­ti­cles, I ex­plained how the Linux ker­nel im­ple­ments IPv4 and IPv6 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—in­clud­ing the im­pact of the Melt­down and Spec­tre mit­i­ga­tions—as well as from Linux 2.6.39 to 4.18 for IPv6. 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, a Zen 4c CPU, rented from Scale­way, 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
Performance evolution of IPv6 route lookups. Versions with an asterisk have SRSO mitigation disabled.

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. In Linux 4.18, David Ah­ern im­proved the data struc­tures used by route lookup. In Linux 5.9, Brian Vazquez re­moved ex­pen­sive in­di­rect calls in com­mit 55cced4f813b.

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,” a vul­ner­a­bil­ity af­fect­ing AMD pro­ces­sors, in com­mit fb3bd914b3ec. 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
Performance evolution of IPv4 route lookups. Versions with an asterisk have SRSO mitigation disabled.

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 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() 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() even­tu­ally calls it in the fol­low­ing code:

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 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 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, 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 vul­ner­a­bil­ity, which is fixed since the Sap­phire Rapids ar­chi­tecture.

If we set aside the re­gres­sions in­tro­duced by the mit­i­ga­tions against CPU at­tacks, 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, a fourth gen­er­a­tion Xeon CPU, or maybe an ARM Neo­verse V2; dis­able some or all the mit­i­ga­tions; by­pass rout­ing with XDP/eBPF;5 or off­load rout­ing to the net­work card.

Note

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