581 lines · plain
1.. SPDX-License-Identifier: GPL-2.02 3=====================================4Scaling in the Linux Networking Stack5=====================================6 7 8Introduction9============10 11This document describes a set of complementary techniques in the Linux12networking stack to increase parallelism and improve performance for13multi-processor systems.14 15The following technologies are described:16 17- RSS: Receive Side Scaling18- RPS: Receive Packet Steering19- RFS: Receive Flow Steering20- Accelerated Receive Flow Steering21- XPS: Transmit Packet Steering22 23 24RSS: Receive Side Scaling25=========================26 27Contemporary NICs support multiple receive and transmit descriptor queues28(multi-queue). On reception, a NIC can send different packets to different29queues to distribute processing among CPUs. The NIC distributes packets by30applying a filter to each packet that assigns it to one of a small number31of logical flows. Packets for each flow are steered to a separate receive32queue, which in turn can be processed by separate CPUs. This mechanism is33generally known as “Receive-side Scaling” (RSS). The goal of RSS and34the other scaling techniques is to increase performance uniformly.35Multi-queue distribution can also be used for traffic prioritization, but36that is not the focus of these techniques.37 38The filter used in RSS is typically a hash function over the network39and/or transport layer headers-- for example, a 4-tuple hash over40IP addresses and TCP ports of a packet. The most common hardware41implementation of RSS uses a 128-entry indirection table where each entry42stores a queue number. The receive queue for a packet is determined43by masking out the low order seven bits of the computed hash for the44packet (usually a Toeplitz hash), taking this number as a key into the45indirection table and reading the corresponding value.46 47Some NICs support symmetric RSS hashing where, if the IP (source address,48destination address) and TCP/UDP (source port, destination port) tuples49are swapped, the computed hash is the same. This is beneficial in some50applications that monitor TCP/IP flows (IDS, firewalls, ...etc) and need51both directions of the flow to land on the same Rx queue (and CPU). The52"Symmetric-XOR" is a type of RSS algorithms that achieves this hash53symmetry by XORing the input source and destination fields of the IP54and/or L4 protocols. This, however, results in reduced input entropy and55could potentially be exploited. Specifically, the algorithm XORs the input56as follows::57 58 # (SRC_IP ^ DST_IP, SRC_IP ^ DST_IP, SRC_PORT ^ DST_PORT, SRC_PORT ^ DST_PORT)59 60The result is then fed to the underlying RSS algorithm.61 62Some advanced NICs allow steering packets to queues based on63programmable filters. For example, webserver bound TCP port 80 packets64can be directed to their own receive queue. Such “n-tuple” filters can65be configured from ethtool (--config-ntuple).66 67 68RSS Configuration69-----------------70 71The driver for a multi-queue capable NIC typically provides a kernel72module parameter for specifying the number of hardware queues to73configure. In the bnx2x driver, for instance, this parameter is called74num_queues. A typical RSS configuration would be to have one receive queue75for each CPU if the device supports enough queues, or otherwise at least76one for each memory domain, where a memory domain is a set of CPUs that77share a particular memory level (L1, L2, NUMA node, etc.).78 79The indirection table of an RSS device, which resolves a queue by masked80hash, is usually programmed by the driver at initialization. The81default mapping is to distribute the queues evenly in the table, but the82indirection table can be retrieved and modified at runtime using ethtool83commands (--show-rxfh-indir and --set-rxfh-indir). Modifying the84indirection table could be done to give different queues different85relative weights.86 87 88RSS IRQ Configuration89~~~~~~~~~~~~~~~~~~~~~90 91Each receive queue has a separate IRQ associated with it. The NIC triggers92this to notify a CPU when new packets arrive on the given queue. The93signaling path for PCIe devices uses message signaled interrupts (MSI-X),94that can route each interrupt to a particular CPU. The active mapping95of queues to IRQs can be determined from /proc/interrupts. By default,96an IRQ may be handled on any CPU. Because a non-negligible part of packet97processing takes place in receive interrupt handling, it is advantageous98to spread receive interrupts between CPUs. To manually adjust the IRQ99affinity of each interrupt see Documentation/core-api/irq/irq-affinity.rst. Some systems100will be running irqbalance, a daemon that dynamically optimizes IRQ101assignments and as a result may override any manual settings.102 103 104Suggested Configuration105~~~~~~~~~~~~~~~~~~~~~~~106 107RSS should be enabled when latency is a concern or whenever receive108interrupt processing forms a bottleneck. Spreading load between CPUs109decreases queue length. For low latency networking, the optimal setting110is to allocate as many queues as there are CPUs in the system (or the111NIC maximum, if lower). The most efficient high-rate configuration112is likely the one with the smallest number of receive queues where no113receive queue overflows due to a saturated CPU, because in default114mode with interrupt coalescing enabled, the aggregate number of115interrupts (and thus work) grows with each additional queue.116 117Per-cpu load can be observed using the mpstat utility, but note that on118processors with hyperthreading (HT), each hyperthread is represented as119a separate CPU. For interrupt handling, HT has shown no benefit in120initial tests, so limit the number of queues to the number of CPU cores121in the system.122 123Dedicated RSS contexts124~~~~~~~~~~~~~~~~~~~~~~125 126Modern NICs support creating multiple co-existing RSS configurations127which are selected based on explicit matching rules. This can be very128useful when application wants to constrain the set of queues receiving129traffic for e.g. a particular destination port or IP address.130The example below shows how to direct all traffic to TCP port 22131to queues 0 and 1.132 133To create an additional RSS context use::134 135 # ethtool -X eth0 hfunc toeplitz context new136 New RSS context is 1137 138Kernel reports back the ID of the allocated context (the default, always139present RSS context has ID of 0). The new context can be queried and140modified using the same APIs as the default context::141 142 # ethtool -x eth0 context 1143 RX flow hash indirection table for eth0 with 13 RX ring(s):144 0: 0 1 2 3 4 5 6 7145 8: 8 9 10 11 12 0 1 2146 [...]147 # ethtool -X eth0 equal 2 context 1148 # ethtool -x eth0 context 1149 RX flow hash indirection table for eth0 with 13 RX ring(s):150 0: 0 1 0 1 0 1 0 1151 8: 0 1 0 1 0 1 0 1152 [...]153 154To make use of the new context direct traffic to it using an n-tuple155filter::156 157 # ethtool -N eth0 flow-type tcp6 dst-port 22 context 1158 Added rule with ID 1023159 160When done, remove the context and the rule::161 162 # ethtool -N eth0 delete 1023163 # ethtool -X eth0 context 1 delete164 165 166RPS: Receive Packet Steering167============================168 169Receive Packet Steering (RPS) is logically a software implementation of170RSS. Being in software, it is necessarily called later in the datapath.171Whereas RSS selects the queue and hence CPU that will run the hardware172interrupt handler, RPS selects the CPU to perform protocol processing173above the interrupt handler. This is accomplished by placing the packet174on the desired CPU’s backlog queue and waking up the CPU for processing.175RPS has some advantages over RSS:176 1771) it can be used with any NIC1782) software filters can easily be added to hash over new protocols1793) it does not increase hardware device interrupt rate (although it does180 introduce inter-processor interrupts (IPIs))181 182RPS is called during bottom half of the receive interrupt handler, when183a driver sends a packet up the network stack with netif_rx() or184netif_receive_skb(). These call the get_rps_cpu() function, which185selects the queue that should process a packet.186 187The first step in determining the target CPU for RPS is to calculate a188flow hash over the packet’s addresses or ports (2-tuple or 4-tuple hash189depending on the protocol). This serves as a consistent hash of the190associated flow of the packet. The hash is either provided by hardware191or will be computed in the stack. Capable hardware can pass the hash in192the receive descriptor for the packet; this would usually be the same193hash used for RSS (e.g. computed Toeplitz hash). The hash is saved in194skb->hash and can be used elsewhere in the stack as a hash of the195packet’s flow.196 197Each receive hardware queue has an associated list of CPUs to which198RPS may enqueue packets for processing. For each received packet,199an index into the list is computed from the flow hash modulo the size200of the list. The indexed CPU is the target for processing the packet,201and the packet is queued to the tail of that CPU’s backlog queue. At202the end of the bottom half routine, IPIs are sent to any CPUs for which203packets have been queued to their backlog queue. The IPI wakes backlog204processing on the remote CPU, and any queued packets are then processed205up the networking stack.206 207 208RPS Configuration209-----------------210 211RPS requires a kernel compiled with the CONFIG_RPS kconfig symbol (on212by default for SMP). Even when compiled in, RPS remains disabled until213explicitly configured. The list of CPUs to which RPS may forward traffic214can be configured for each receive queue using a sysfs file entry::215 216 /sys/class/net/<dev>/queues/rx-<n>/rps_cpus217 218This file implements a bitmap of CPUs. RPS is disabled when it is zero219(the default), in which case packets are processed on the interrupting220CPU. Documentation/core-api/irq/irq-affinity.rst explains how CPUs are assigned to221the bitmap.222 223 224Suggested Configuration225~~~~~~~~~~~~~~~~~~~~~~~226 227For a single queue device, a typical RPS configuration would be to set228the rps_cpus to the CPUs in the same memory domain of the interrupting229CPU. If NUMA locality is not an issue, this could also be all CPUs in230the system. At high interrupt rate, it might be wise to exclude the231interrupting CPU from the map since that already performs much work.232 233For a multi-queue system, if RSS is configured so that a hardware234receive queue is mapped to each CPU, then RPS is probably redundant235and unnecessary. If there are fewer hardware queues than CPUs, then236RPS might be beneficial if the rps_cpus for each queue are the ones that237share the same memory domain as the interrupting CPU for that queue.238 239 240RPS Flow Limit241--------------242 243RPS scales kernel receive processing across CPUs without introducing244reordering. The trade-off to sending all packets from the same flow245to the same CPU is CPU load imbalance if flows vary in packet rate.246In the extreme case a single flow dominates traffic. Especially on247common server workloads with many concurrent connections, such248behavior indicates a problem such as a misconfiguration or spoofed249source Denial of Service attack.250 251Flow Limit is an optional RPS feature that prioritizes small flows252during CPU contention by dropping packets from large flows slightly253ahead of those from small flows. It is active only when an RPS or RFS254destination CPU approaches saturation. Once a CPU's input packet255queue exceeds half the maximum queue length (as set by sysctl256net.core.netdev_max_backlog), the kernel starts a per-flow packet257count over the last 256 packets. If a flow exceeds a set ratio (by258default, half) of these packets when a new packet arrives, then the259new packet is dropped. Packets from other flows are still only260dropped once the input packet queue reaches netdev_max_backlog.261No packets are dropped when the input packet queue length is below262the threshold, so flow limit does not sever connections outright:263even large flows maintain connectivity.264 265 266Interface267~~~~~~~~~268 269Flow limit is compiled in by default (CONFIG_NET_FLOW_LIMIT), but not270turned on. It is implemented for each CPU independently (to avoid lock271and cache contention) and toggled per CPU by setting the relevant bit272in sysctl net.core.flow_limit_cpu_bitmap. It exposes the same CPU273bitmap interface as rps_cpus (see above) when called from procfs::274 275 /proc/sys/net/core/flow_limit_cpu_bitmap276 277Per-flow rate is calculated by hashing each packet into a hashtable278bucket and incrementing a per-bucket counter. The hash function is279the same that selects a CPU in RPS, but as the number of buckets can280be much larger than the number of CPUs, flow limit has finer-grained281identification of large flows and fewer false positives. The default282table has 4096 buckets. This value can be modified through sysctl::283 284 net.core.flow_limit_table_len285 286The value is only consulted when a new table is allocated. Modifying287it does not update active tables.288 289 290Suggested Configuration291~~~~~~~~~~~~~~~~~~~~~~~292 293Flow limit is useful on systems with many concurrent connections,294where a single connection taking up 50% of a CPU indicates a problem.295In such environments, enable the feature on all CPUs that handle296network rx interrupts (as set in /proc/irq/N/smp_affinity).297 298The feature depends on the input packet queue length to exceed299the flow limit threshold (50%) + the flow history length (256).300Setting net.core.netdev_max_backlog to either 1000 or 10000301performed well in experiments.302 303 304RFS: Receive Flow Steering305==========================306 307While RPS steers packets solely based on hash, and thus generally308provides good load distribution, it does not take into account309application locality. This is accomplished by Receive Flow Steering310(RFS). The goal of RFS is to increase datacache hitrate by steering311kernel processing of packets to the CPU where the application thread312consuming the packet is running. RFS relies on the same RPS mechanisms313to enqueue packets onto the backlog of another CPU and to wake up that314CPU.315 316In RFS, packets are not forwarded directly by the value of their hash,317but the hash is used as index into a flow lookup table. This table maps318flows to the CPUs where those flows are being processed. The flow hash319(see RPS section above) is used to calculate the index into this table.320The CPU recorded in each entry is the one which last processed the flow.321If an entry does not hold a valid CPU, then packets mapped to that entry322are steered using plain RPS. Multiple table entries may point to the323same CPU. Indeed, with many flows and few CPUs, it is very likely that324a single application thread handles flows with many different flow hashes.325 326rps_sock_flow_table is a global flow table that contains the *desired* CPU327for flows: the CPU that is currently processing the flow in userspace.328Each table value is a CPU index that is updated during calls to recvmsg329and sendmsg (specifically, inet_recvmsg(), inet_sendmsg() and330tcp_splice_read()).331 332When the scheduler moves a thread to a new CPU while it has outstanding333receive packets on the old CPU, packets may arrive out of order. To334avoid this, RFS uses a second flow table to track outstanding packets335for each flow: rps_dev_flow_table is a table specific to each hardware336receive queue of each device. Each table value stores a CPU index and a337counter. The CPU index represents the *current* CPU onto which packets338for this flow are enqueued for further kernel processing. Ideally, kernel339and userspace processing occur on the same CPU, and hence the CPU index340in both tables is identical. This is likely false if the scheduler has341recently migrated a userspace thread while the kernel still has packets342enqueued for kernel processing on the old CPU.343 344The counter in rps_dev_flow_table values records the length of the current345CPU's backlog when a packet in this flow was last enqueued. Each backlog346queue has a head counter that is incremented on dequeue. A tail counter347is computed as head counter + queue length. In other words, the counter348in rps_dev_flow[i] records the last element in flow i that has349been enqueued onto the currently designated CPU for flow i (of course,350entry i is actually selected by hash and multiple flows may hash to the351same entry i).352 353And now the trick for avoiding out of order packets: when selecting the354CPU for packet processing (from get_rps_cpu()) the rps_sock_flow table355and the rps_dev_flow table of the queue that the packet was received on356are compared. If the desired CPU for the flow (found in the357rps_sock_flow table) matches the current CPU (found in the rps_dev_flow358table), the packet is enqueued onto that CPU’s backlog. If they differ,359the current CPU is updated to match the desired CPU if one of the360following is true:361 362 - The current CPU's queue head counter >= the recorded tail counter363 value in rps_dev_flow[i]364 - The current CPU is unset (>= nr_cpu_ids)365 - The current CPU is offline366 367After this check, the packet is sent to the (possibly updated) current368CPU. These rules aim to ensure that a flow only moves to a new CPU when369there are no packets outstanding on the old CPU, as the outstanding370packets could arrive later than those about to be processed on the new371CPU.372 373 374RFS Configuration375-----------------376 377RFS is only available if the kconfig symbol CONFIG_RPS is enabled (on378by default for SMP). The functionality remains disabled until explicitly379configured. The number of entries in the global flow table is set through::380 381 /proc/sys/net/core/rps_sock_flow_entries382 383The number of entries in the per-queue flow table are set through::384 385 /sys/class/net/<dev>/queues/rx-<n>/rps_flow_cnt386 387 388Suggested Configuration389~~~~~~~~~~~~~~~~~~~~~~~390 391Both of these need to be set before RFS is enabled for a receive queue.392Values for both are rounded up to the nearest power of two. The393suggested flow count depends on the expected number of active connections394at any given time, which may be significantly less than the number of open395connections. We have found that a value of 32768 for rps_sock_flow_entries396works fairly well on a moderately loaded server.397 398For a single queue device, the rps_flow_cnt value for the single queue399would normally be configured to the same value as rps_sock_flow_entries.400For a multi-queue device, the rps_flow_cnt for each queue might be401configured as rps_sock_flow_entries / N, where N is the number of402queues. So for instance, if rps_sock_flow_entries is set to 32768 and there403are 16 configured receive queues, rps_flow_cnt for each queue might be404configured as 2048.405 406 407Accelerated RFS408===============409 410Accelerated RFS is to RFS what RSS is to RPS: a hardware-accelerated load411balancing mechanism that uses soft state to steer flows based on where412the application thread consuming the packets of each flow is running.413Accelerated RFS should perform better than RFS since packets are sent414directly to a CPU local to the thread consuming the data. The target CPU415will either be the same CPU where the application runs, or at least a CPU416which is local to the application thread’s CPU in the cache hierarchy.417 418To enable accelerated RFS, the networking stack calls the419ndo_rx_flow_steer driver function to communicate the desired hardware420queue for packets matching a particular flow. The network stack421automatically calls this function every time a flow entry in422rps_dev_flow_table is updated. The driver in turn uses a device specific423method to program the NIC to steer the packets.424 425The hardware queue for a flow is derived from the CPU recorded in426rps_dev_flow_table. The stack consults a CPU to hardware queue map which427is maintained by the NIC driver. This is an auto-generated reverse map of428the IRQ affinity table shown by /proc/interrupts. Drivers can use429functions in the cpu_rmap (“CPU affinity reverse map”) kernel library430to populate the map. For each CPU, the corresponding queue in the map is431set to be one whose processing CPU is closest in cache locality.432 433 434Accelerated RFS Configuration435-----------------------------436 437Accelerated RFS is only available if the kernel is compiled with438CONFIG_RFS_ACCEL and support is provided by the NIC device and driver.439It also requires that ntuple filtering is enabled via ethtool. The map440of CPU to queues is automatically deduced from the IRQ affinities441configured for each receive queue by the driver, so no additional442configuration should be necessary.443 444 445Suggested Configuration446~~~~~~~~~~~~~~~~~~~~~~~447 448This technique should be enabled whenever one wants to use RFS and the449NIC supports hardware acceleration.450 451 452XPS: Transmit Packet Steering453=============================454 455Transmit Packet Steering is a mechanism for intelligently selecting456which transmit queue to use when transmitting a packet on a multi-queue457device. This can be accomplished by recording two kinds of maps, either458a mapping of CPU to hardware queue(s) or a mapping of receive queue(s)459to hardware transmit queue(s).460 4611. XPS using CPUs map462 463The goal of this mapping is usually to assign queues464exclusively to a subset of CPUs, where the transmit completions for465these queues are processed on a CPU within this set. This choice466provides two benefits. First, contention on the device queue lock is467significantly reduced since fewer CPUs contend for the same queue468(contention can be eliminated completely if each CPU has its own469transmit queue). Secondly, cache miss rate on transmit completion is470reduced, in particular for data cache lines that hold the sk_buff471structures.472 4732. XPS using receive queues map474 475This mapping is used to pick transmit queue based on the receive476queue(s) map configuration set by the administrator. A set of receive477queues can be mapped to a set of transmit queues (many:many), although478the common use case is a 1:1 mapping. This will enable sending packets479on the same queue associations for transmit and receive. This is useful for480busy polling multi-threaded workloads where there are challenges in481associating a given CPU to a given application thread. The application482threads are not pinned to CPUs and each thread handles packets483received on a single queue. The receive queue number is cached in the484socket for the connection. In this model, sending the packets on the same485transmit queue corresponding to the associated receive queue has benefits486in keeping the CPU overhead low. Transmit completion work is locked into487the same queue-association that a given application is polling on. This488avoids the overhead of triggering an interrupt on another CPU. When the489application cleans up the packets during the busy poll, transmit completion490may be processed along with it in the same thread context and so result in491reduced latency.492 493XPS is configured per transmit queue by setting a bitmap of494CPUs/receive-queues that may use that queue to transmit. The reverse495mapping, from CPUs to transmit queues or from receive-queues to transmit496queues, is computed and maintained for each network device. When497transmitting the first packet in a flow, the function get_xps_queue() is498called to select a queue. This function uses the ID of the receive queue499for the socket connection for a match in the receive queue-to-transmit queue500lookup table. Alternatively, this function can also use the ID of the501running CPU as a key into the CPU-to-queue lookup table. If the502ID matches a single queue, that is used for transmission. If multiple503queues match, one is selected by using the flow hash to compute an index504into the set. When selecting the transmit queue based on receive queue(s)505map, the transmit device is not validated against the receive device as it506requires expensive lookup operation in the datapath.507 508The queue chosen for transmitting a particular flow is saved in the509corresponding socket structure for the flow (e.g. a TCP connection).510This transmit queue is used for subsequent packets sent on the flow to511prevent out of order (ooo) packets. The choice also amortizes the cost512of calling get_xps_queues() over all packets in the flow. To avoid513ooo packets, the queue for a flow can subsequently only be changed if514skb->ooo_okay is set for a packet in the flow. This flag indicates that515there are no outstanding packets in the flow, so the transmit queue can516change without the risk of generating out of order packets. The517transport layer is responsible for setting ooo_okay appropriately. TCP,518for instance, sets the flag when all data for a connection has been519acknowledged.520 521XPS Configuration522-----------------523 524XPS is only available if the kconfig symbol CONFIG_XPS is enabled (on by525default for SMP). If compiled in, it is driver dependent whether, and526how, XPS is configured at device init. The mapping of CPUs/receive-queues527to transmit queue can be inspected and configured using sysfs:528 529For selection based on CPUs map::530 531 /sys/class/net/<dev>/queues/tx-<n>/xps_cpus532 533For selection based on receive-queues map::534 535 /sys/class/net/<dev>/queues/tx-<n>/xps_rxqs536 537 538Suggested Configuration539~~~~~~~~~~~~~~~~~~~~~~~540 541For a network device with a single transmission queue, XPS configuration542has no effect, since there is no choice in this case. In a multi-queue543system, XPS is preferably configured so that each CPU maps onto one queue.544If there are as many queues as there are CPUs in the system, then each545queue can also map onto one CPU, resulting in exclusive pairings that546experience no contention. If there are fewer queues than CPUs, then the547best CPUs to share a given queue are probably those that share the cache548with the CPU that processes transmit completions for that queue549(transmit interrupts).550 551For transmit queue selection based on receive queue(s), XPS has to be552explicitly configured mapping receive-queue(s) to transmit queue(s). If the553user configuration for receive-queue map does not apply, then the transmit554queue is selected based on the CPUs map.555 556 557Per TX Queue rate limitation558============================559 560These are rate-limitation mechanisms implemented by HW, where currently561a max-rate attribute is supported, by setting a Mbps value to::562 563 /sys/class/net/<dev>/queues/tx-<n>/tx_maxrate564 565A value of zero means disabled, and this is the default.566 567 568Further Information569===================570RPS and RFS were introduced in kernel 2.6.35. XPS was incorporated into5712.6.38. Original patches were submitted by Tom Herbert572(therbert@google.com)573 574Accelerated RFS was introduced in 2.6.35. Original patches were575submitted by Ben Hutchings (bwh@kernel.org)576 577Authors:578 579- Tom Herbert (therbert@google.com)580- Willem de Bruijn (willemb@google.com)581