Scaling in the Linux Networking Stack

Introduction

This document describes a set of complementary techniques in the Linuxnetworking stack to increase parallelism and improve performance formulti-processor systems.

The following technologies are described:

  • RSS: Receive Side Scaling
  • RPS: Receive Packet Steering
  • RFS: Receive Flow Steering
  • Accelerated Receive Flow Steering
  • XPS: Transmit Packet Steering

RSS: Receive Side Scaling

Contemporary NICs support multiple receive and transmit descriptor queues(multi-queue). On reception, a NIC can send different packets to differentqueues to distribute processing among CPUs. The NIC distributes packets byapplying a filter to each packet that assigns it to one of a small numberof logical flows. Packets for each flow are steered to a separate receivequeue, which in turn can be processed by separate CPUs. This mechanism isgenerally known as “Receive-side Scaling” (RSS). The goal of RSS andthe other scaling techniques is to increase performance uniformly.Multi-queue distribution can also be used for traffic prioritization, butthat is not the focus of these techniques.

The filter used in RSS is typically a hash function over the networkand/or transport layer headers– for example, a 4-tuple hash overIP addresses and TCP ports of a packet. The most common hardwareimplementation of RSS uses a 128-entry indirection table where each entrystores a queue number. The receive queue for a packet is determinedby masking out the low order seven bits of the computed hash for thepacket (usually a Toeplitz hash), taking this number as a key into theindirection table and reading the corresponding value.

Some advanced NICs allow steering packets to queues based onprogrammable filters. For example, webserver bound TCP port 80 packetscan be directed to their own receive queue. Such “n-tuple” filters canbe configured from ethtool (–config-ntuple).

RSS Configuration

The driver for a multi-queue capable NIC typically provides a kernelmodule parameter for specifying the number of hardware queues toconfigure. In the bnx2x driver, for instance, this parameter is callednum_queues. A typical RSS configuration would be to have one receive queuefor each CPU if the device supports enough queues, or otherwise at leastone for each memory domain, where a memory domain is a set of CPUs thatshare a particular memory level (L1, L2, NUMA node, etc.).

The indirection table of an RSS device, which resolves a queue by maskedhash, is usually programmed by the driver at initialization. Thedefault mapping is to distribute the queues evenly in the table, but theindirection table can be retrieved and modified at runtime using ethtoolcommands (–show-rxfh-indir and –set-rxfh-indir). Modifying theindirection table could be done to give different queues differentrelative weights.

RSS IRQ Configuration

Each receive queue has a separate IRQ associated with it. The NIC triggersthis to notify a CPU when new packets arrive on the given queue. Thesignaling path for PCIe devices uses message signaled interrupts (MSI-X),that can route each interrupt to a particular CPU. The active mappingof queues to IRQs can be determined from /proc/interrupts. By default,an IRQ may be handled on any CPU. Because a non-negligible part of packetprocessing takes place in receive interrupt handling, it is advantageousto spread receive interrupts between CPUs. To manually adjust the IRQaffinity of each interrupt see Documentation/core-api/irq/irq-affinity.rst. Some systemswill be running irqbalance, a daemon that dynamically optimizes IRQassignments and as a result may override any manual settings.

Suggested Configuration

RSS should be enabled when latency is a concern or whenever receiveinterrupt processing forms a bottleneck. Spreading load between CPUsdecreases queue length. For low latency networking, the optimal settingis to allocate as many queues as there are CPUs in the system (or theNIC maximum, if lower). The most efficient high-rate configurationis likely the one with the smallest number of receive queues where noreceive queue overflows due to a saturated CPU, because in defaultmode with interrupt coalescing enabled, the aggregate number ofinterrupts (and thus work) grows with each additional queue.

Per-cpu load can be observed using the mpstat utility, but note that onprocessors with hyperthreading (HT), each hyperthread is represented asa separate CPU. For interrupt handling, HT has shown no benefit ininitial tests, so limit the number of queues to the number of CPU coresin the system.

RPS: Receive Packet Steering

Receive Packet Steering (RPS) is logically a software implementation ofRSS. Being in software, it is necessarily called later in the datapath.Whereas RSS selects the queue and hence CPU that will run the hardwareinterrupt handler, RPS selects the CPU to perform protocol processingabove the interrupt handler. This is accomplished by placing the packeton the desired CPU’s backlog queue and waking up the CPU for processing.RPS has some advantages over RSS:

  1. it can be used with any NIC
  2. software filters can easily be added to hash over new protocols
  3. it does not increase hardware device interrupt rate (although it doesintroduce inter-processor interrupts (IPIs))

RPS is called during bottom half of the receive interrupt handler, whena driver sends a packet up the network stack withnetif_rx() ornetif_receive_skb(). These call the get_rps_cpu() function, whichselects the queue that should process a packet.

The first step in determining the target CPU for RPS is to calculate aflow hash over the packet’s addresses or ports (2-tuple or 4-tuple hashdepending on the protocol). This serves as a consistent hash of theassociated flow of the packet. The hash is either provided by hardwareor will be computed in the stack. Capable hardware can pass the hash inthe receive descriptor for the packet; this would usually be the samehash used for RSS (e.g. computed Toeplitz hash). The hash is saved inskb->hash and can be used elsewhere in the stack as a hash of thepacket’s flow.

Each receive hardware queue has an associated list of CPUs to whichRPS may enqueue packets for processing. For each received packet,an index into the list is computed from the flow hash modulo the sizeof the list. The indexed CPU is the target for processing the packet,and the packet is queued to the tail of that CPU’s backlog queue. Atthe end of the bottom half routine, IPIs are sent to any CPUs for whichpackets have been queued to their backlog queue. The IPI wakes backlogprocessing on the remote CPU, and any queued packets are then processedup the networking stack.

RPS Configuration

RPS requires a kernel compiled with the CONFIG_RPS kconfig symbol (onby default for SMP). Even when compiled in, RPS remains disabled untilexplicitly configured. The list of CPUs to which RPS may forward trafficcan be configured for each receive queue using a sysfs file entry:

/sys/class/net/<dev>/queues/rx-<n>/rps_cpus

This file implements a bitmap of CPUs. RPS is disabled when it is zero(the default), in which case packets are processed on the interruptingCPU. Documentation/core-api/irq/irq-affinity.rst explains how CPUs are assigned tothe bitmap.

Suggested Configuration

For a single queue device, a typical RPS configuration would be to setthe rps_cpus to the CPUs in the same memory domain of the interruptingCPU. If NUMA locality is not an issue, this could also be all CPUs inthe system. At high interrupt rate, it might be wise to exclude theinterrupting CPU from the map since that already performs much work.

For a multi-queue system, if RSS is configured so that a hardwarereceive queue is mapped to each CPU, then RPS is probably redundantand unnecessary. If there are fewer hardware queues than CPUs, thenRPS might be beneficial if the rps_cpus for each queue are the ones thatshare the same memory domain as the interrupting CPU for that queue.

RPS Flow Limit

RPS scales kernel receive processing across CPUs without introducingreordering. The trade-off to sending all packets from the same flowto the same CPU is CPU load imbalance if flows vary in packet rate.In the extreme case a single flow dominates traffic. Especially oncommon server workloads with many concurrent connections, suchbehavior indicates a problem such as a misconfiguration or spoofedsource Denial of Service attack.

Flow Limit is an optional RPS feature that prioritizes small flowsduring CPU contention by dropping packets from large flows slightlyahead of those from small flows. It is active only when an RPS or RFSdestination CPU approaches saturation. Once a CPU’s input packetqueue exceeds half the maximum queue length (as set by sysctlnet.core.netdev_max_backlog), the kernel starts a per-flow packetcount over the last 256 packets. If a flow exceeds a set ratio (bydefault, half) of these packets when a new packet arrives, then thenew packet is dropped. Packets from other flows are still onlydropped once the input packet queue reaches netdev_max_backlog.No packets are dropped when the input packet queue length is belowthe threshold, so flow limit does not sever connections outright:even large flows maintain connectivity.

Interface

Flow limit is compiled in by default (CONFIG_NET_FLOW_LIMIT), but notturned on. It is implemented for each CPU independently (to avoid lockand cache contention) and toggled per CPU by setting the relevant bitin sysctl net.core.flow_limit_cpu_bitmap. It exposes the same CPUbitmap interface as rps_cpus (see above) when called from procfs:

/proc/sys/net/core/flow_limit_cpu_bitmap

Per-flow rate is calculated by hashing each packet into a hashtablebucket and incrementing a per-bucket counter. The hash function isthe same that selects a CPU in RPS, but as the number of buckets canbe much larger than the number of CPUs, flow limit has finer-grainedidentification of large flows and fewer false positives. The defaulttable has 4096 buckets. This value can be modified through sysctl:

net.core.flow_limit_table_len

The value is only consulted when a new table is allocated. Modifyingit does not update active tables.

Suggested Configuration

Flow limit is useful on systems with many concurrent connections,where a single connection taking up 50% of a CPU indicates a problem.In such environments, enable the feature on all CPUs that handlenetwork rx interrupts (as set in /proc/irq/N/smp_affinity).

The feature depends on the input packet queue length to exceedthe flow limit threshold (50%) + the flow history length (256).Setting net.core.netdev_max_backlog to either 1000 or 10000performed well in experiments.

RFS: Receive Flow Steering

While RPS steers packets solely based on hash, and thus generallyprovides good load distribution, it does not take into accountapplication locality. This is accomplished by Receive Flow Steering(RFS). The goal of RFS is to increase datacache hitrate by steeringkernel processing of packets to the CPU where the application threadconsuming the packet is running. RFS relies on the same RPS mechanismsto enqueue packets onto the backlog of another CPU and to wake up thatCPU.

In RFS, packets are not forwarded directly by the value of their hash,but the hash is used as index into a flow lookup table. This table mapsflows to the CPUs where those flows are being processed. The flow hash(see RPS section above) is used to calculate the index into this table.The CPU recorded in each entry is the one which last processed the flow.If an entry does not hold a valid CPU, then packets mapped to that entryare steered using plain RPS. Multiple table entries may point to thesame CPU. Indeed, with many flows and few CPUs, it is very likely thata single application thread handles flows with many different flow hashes.

rps_sock_flow_table is a global flow table that contains thedesired CPUfor flows: the CPU that is currently processing the flow in userspace.Each table value is a CPU index that is updated during calls to recvmsgand sendmsg (specifically, inet_recvmsg(), inet_sendmsg(), inet_sendpage()and tcp_splice_read()).

When the scheduler moves a thread to a new CPU while it has outstandingreceive packets on the old CPU, packets may arrive out of order. Toavoid this, RFS uses a second flow table to track outstanding packetsfor each flow: rps_dev_flow_table is a table specific to each hardwarereceive queue of each device. Each table value stores a CPU index and acounter. The CPU index represents thecurrent CPU onto which packetsfor this flow are enqueued for further kernel processing. Ideally, kerneland userspace processing occur on the same CPU, and hence the CPU indexin both tables is identical. This is likely false if the scheduler hasrecently migrated a userspace thread while the kernel still has packetsenqueued for kernel processing on the old CPU.

The counter in rps_dev_flow_table values records the length of the currentCPU’s backlog when a packet in this flow was last enqueued. Each backlogqueue has a head counter that is incremented on dequeue. A tail counteris computed as head counter + queue length. In other words, the counterin rps_dev_flow[i] records the last element in flow i that hasbeen enqueued onto the currently designated CPU for flow i (of course,entry i is actually selected by hash and multiple flows may hash to thesame entry i).

And now the trick for avoiding out of order packets: when selecting theCPU for packet processing (from get_rps_cpu()) the rps_sock_flow tableand the rps_dev_flow table of the queue that the packet was received onare compared. If the desired CPU for the flow (found in therps_sock_flow table) matches the current CPU (found in the rps_dev_flowtable), the packet is enqueued onto that CPU’s backlog. If they differ,the current CPU is updated to match the desired CPU if one of thefollowing is true:

  • The current CPU’s queue head counter >= the recorded tail countervalue in rps_dev_flow[i]
  • The current CPU is unset (>= nr_cpu_ids)
  • The current CPU is offline

After this check, the packet is sent to the (possibly updated) currentCPU. These rules aim to ensure that a flow only moves to a new CPU whenthere are no packets outstanding on the old CPU, as the outstandingpackets could arrive later than those about to be processed on the newCPU.

RFS Configuration

RFS is only available if the kconfig symbol CONFIG_RPS is enabled (onby default for SMP). The functionality remains disabled until explicitlyconfigured. The number of entries in the global flow table is set through:

/proc/sys/net/core/rps_sock_flow_entries

The number of entries in the per-queue flow table are set through:

/sys/class/net/<dev>/queues/rx-<n>/rps_flow_cnt

Suggested Configuration

Both of these need to be set before RFS is enabled for a receive queue.Values for both are rounded up to the nearest power of two. Thesuggested flow count depends on the expected number of active connectionsat any given time, which may be significantly less than the number of openconnections. We have found that a value of 32768 for rps_sock_flow_entriesworks fairly well on a moderately loaded server.

For a single queue device, the rps_flow_cnt value for the single queuewould normally be configured to the same value as rps_sock_flow_entries.For a multi-queue device, the rps_flow_cnt for each queue might beconfigured as rps_sock_flow_entries / N, where N is the number ofqueues. So for instance, if rps_sock_flow_entries is set to 32768 and thereare 16 configured receive queues, rps_flow_cnt for each queue might beconfigured as 2048.

Accelerated RFS

Accelerated RFS is to RFS what RSS is to RPS: a hardware-accelerated loadbalancing mechanism that uses soft state to steer flows based on wherethe application thread consuming the packets of each flow is running.Accelerated RFS should perform better than RFS since packets are sentdirectly to a CPU local to the thread consuming the data. The target CPUwill either be the same CPU where the application runs, or at least a CPUwhich is local to the application thread’s CPU in the cache hierarchy.

To enable accelerated RFS, the networking stack calls thendo_rx_flow_steer driver function to communicate the desired hardwarequeue for packets matching a particular flow. The network stackautomatically calls this function every time a flow entry inrps_dev_flow_table is updated. The driver in turn uses a device specificmethod to program the NIC to steer the packets.

The hardware queue for a flow is derived from the CPU recorded inrps_dev_flow_table. The stack consults a CPU to hardware queue map whichis maintained by the NIC driver. This is an auto-generated reverse map ofthe IRQ affinity table shown by /proc/interrupts. Drivers can usefunctions in the cpu_rmap (“CPU affinity reverse map”) kernel libraryto populate the map. For each CPU, the corresponding queue in the map isset to be one whose processing CPU is closest in cache locality.

Accelerated RFS Configuration

Accelerated RFS is only available if the kernel is compiled withCONFIG_RFS_ACCEL and support is provided by the NIC device and driver.It also requires that ntuple filtering is enabled via ethtool. The mapof CPU to queues is automatically deduced from the IRQ affinitiesconfigured for each receive queue by the driver, so no additionalconfiguration should be necessary.

Suggested Configuration

This technique should be enabled whenever one wants to use RFS and theNIC supports hardware acceleration.

XPS: Transmit Packet Steering

Transmit Packet Steering is a mechanism for intelligently selectingwhich transmit queue to use when transmitting a packet on a multi-queuedevice. This can be accomplished by recording two kinds of maps, eithera mapping of CPU to hardware queue(s) or a mapping of receive queue(s)to hardware transmit queue(s).

  1. XPS using CPUs map

The goal of this mapping is usually to assign queuesexclusively to a subset of CPUs, where the transmit completions forthese queues are processed on a CPU within this set. This choiceprovides two benefits. First, contention on the device queue lock issignificantly reduced since fewer CPUs contend for the same queue(contention can be eliminated completely if each CPU has its owntransmit queue). Secondly, cache miss rate on transmit completion isreduced, in particular for data cache lines that hold the sk_buffstructures.

  1. XPS using receive queues map

This mapping is used to pick transmit queue based on the receivequeue(s) map configuration set by the administrator. A set of receivequeues can be mapped to a set of transmit queues (many:many), althoughthe common use case is a 1:1 mapping. This will enable sending packetson the same queue associations for transmit and receive. This is useful forbusy polling multi-threaded workloads where there are challenges inassociating a given CPU to a given application thread. The applicationthreads are not pinned to CPUs and each thread handles packetsreceived on a single queue. The receive queue number is cached in thesocket for the connection. In this model, sending the packets on the sametransmit queue corresponding to the associated receive queue has benefitsin keeping the CPU overhead low. Transmit completion work is locked intothe same queue-association that a given application is polling on. Thisavoids the overhead of triggering an interrupt on another CPU. When theapplication cleans up the packets during the busy poll, transmit completionmay be processed along with it in the same thread context and so result inreduced latency.

XPS is configured per transmit queue by setting a bitmap ofCPUs/receive-queues that may use that queue to transmit. The reversemapping, from CPUs to transmit queues or from receive-queues to transmitqueues, is computed and maintained for each network device. Whentransmitting the first packet in a flow, the function get_xps_queue() iscalled to select a queue. This function uses the ID of the receive queuefor the socket connection for a match in the receive queue-to-transmit queuelookup table. Alternatively, this function can also use the ID of therunning CPU as a key into the CPU-to-queue lookup table. If theID matches a single queue, that is used for transmission. If multiplequeues match, one is selected by using the flow hash to compute an indexinto the set. When selecting the transmit queue based on receive queue(s)map, the transmit device is not validated against the receive device as itrequires expensive lookup operation in the datapath.

The queue chosen for transmitting a particular flow is saved in thecorresponding socket structure for the flow (e.g. a TCP connection).This transmit queue is used for subsequent packets sent on the flow toprevent out of order (ooo) packets. The choice also amortizes the costof calling get_xps_queues() over all packets in the flow. To avoidooo packets, the queue for a flow can subsequently only be changed ifskb->ooo_okay is set for a packet in the flow. This flag indicates thatthere are no outstanding packets in the flow, so the transmit queue canchange without the risk of generating out of order packets. Thetransport layer is responsible for setting ooo_okay appropriately. TCP,for instance, sets the flag when all data for a connection has beenacknowledged.

XPS Configuration

XPS is only available if the kconfig symbol CONFIG_XPS is enabled (on bydefault for SMP). The functionality remains disabled until explicitlyconfigured. To enable XPS, the bitmap of CPUs/receive-queues that mayuse a transmit queue is configured using the sysfs file entry:

For selection based on CPUs map:

/sys/class/net/<dev>/queues/tx-<n>/xps_cpus

For selection based on receive-queues map:

/sys/class/net/<dev>/queues/tx-<n>/xps_rxqs

Suggested Configuration

For a network device with a single transmission queue, XPS configurationhas no effect, since there is no choice in this case. In a multi-queuesystem, XPS is preferably configured so that each CPU maps onto one queue.If there are as many queues as there are CPUs in the system, then eachqueue can also map onto one CPU, resulting in exclusive pairings thatexperience no contention. If there are fewer queues than CPUs, then thebest CPUs to share a given queue are probably those that share the cachewith the CPU that processes transmit completions for that queue(transmit interrupts).

For transmit queue selection based on receive queue(s), XPS has to beexplicitly configured mapping receive-queue(s) to transmit queue(s). If theuser configuration for receive-queue map does not apply, then the transmitqueue is selected based on the CPUs map.

Per TX Queue rate limitation

These are rate-limitation mechanisms implemented by HW, where currentlya max-rate attribute is supported, by setting a Mbps value to:

/sys/class/net/<dev>/queues/tx-<n>/tx_maxrate

A value of zero means disabled, and this is the default.

Further Information

RPS and RFS were introduced in kernel 2.6.35. XPS was incorporated into2.6.38. Original patches were submitted by Tom Herbert(therbert@google.com)

Accelerated RFS was introduced in 2.6.35. Original patches weresubmitted by Ben Hutchings (bwh@kernel.org)

Authors: