1.. SPDX-License-Identifier: GPL-2.0
2
3=====================================
4Scaling in the Linux Networking Stack
5=====================================
6
7
8Introduction
9============
10
11This document describes a set of complementary techniques in the Linux
12networking stack to increase parallelism and improve performance for
13multi-processor systems.
14
15The following technologies are described:
16
17- RSS: Receive Side Scaling
18- RPS: Receive Packet Steering
19- RFS: Receive Flow Steering
20- Accelerated Receive Flow Steering
21- XPS: Transmit Packet Steering
22
23
24RSS: Receive Side Scaling
25=========================
26
27Contemporary NICs support multiple receive and transmit descriptor queues
28(multi-queue). On reception, a NIC can send different packets to different
29queues to distribute processing among CPUs. The NIC distributes packets by
30applying a filter to each packet that assigns it to one of a small number
31of logical flows. Packets for each flow are steered to a separate receive
32queue, which in turn can be processed by separate CPUs. This mechanism is
33generally known as “Receive-side Scaling” (RSS). The goal of RSS and
34the other scaling techniques is to increase performance uniformly.
35Multi-queue distribution can also be used for traffic prioritization, but
36that is not the focus of these techniques.
37
38The filter used in RSS is typically a hash function over the network
39and/or transport layer headers-- for example, a 4-tuple hash over
40IP addresses and TCP ports of a packet. The most common hardware
41implementation of RSS uses a 128-entry indirection table where each entry
42stores a queue number. The receive queue for a packet is determined
43by masking out the low order seven bits of the computed hash for the
44packet (usually a Toeplitz hash), taking this number as a key into the
45indirection table and reading the corresponding value.
46
47Some advanced NICs allow steering packets to queues based on
48programmable filters. For example, webserver bound TCP port 80 packets
49can be directed to their own receive queue. Such “n-tuple” filters can
50be configured from ethtool (--config-ntuple).
51
52
53RSS Configuration
54-----------------
55
56The driver for a multi-queue capable NIC typically provides a kernel
57module parameter for specifying the number of hardware queues to
58configure. In the bnx2x driver, for instance, this parameter is called
59num_queues. A typical RSS configuration would be to have one receive queue
60for each CPU if the device supports enough queues, or otherwise at least
61one for each memory domain, where a memory domain is a set of CPUs that
62share a particular memory level (L1, L2, NUMA node, etc.).
63
64The indirection table of an RSS device, which resolves a queue by masked
65hash, is usually programmed by the driver at initialization. The
66default mapping is to distribute the queues evenly in the table, but the
67indirection table can be retrieved and modified at runtime using ethtool
68commands (--show-rxfh-indir and --set-rxfh-indir). Modifying the
69indirection table could be done to give different queues different
70relative weights.
71
72
73RSS IRQ Configuration
74~~~~~~~~~~~~~~~~~~~~~
75
76Each receive queue has a separate IRQ associated with it. The NIC triggers
77this to notify a CPU when new packets arrive on the given queue. The
78signaling path for PCIe devices uses message signaled interrupts (MSI-X),
79that can route each interrupt to a particular CPU. The active mapping
80of queues to IRQs can be determined from /proc/interrupts. By default,
81an IRQ may be handled on any CPU. Because a non-negligible part of packet
82processing takes place in receive interrupt handling, it is advantageous
83to spread receive interrupts between CPUs. To manually adjust the IRQ
84affinity of each interrupt see Documentation/core-api/irq/irq-affinity.rst. Some systems
85will be running irqbalance, a daemon that dynamically optimizes IRQ
86assignments and as a result may override any manual settings.
87
88
89Suggested Configuration
90~~~~~~~~~~~~~~~~~~~~~~~
91
92RSS should be enabled when latency is a concern or whenever receive
93interrupt processing forms a bottleneck. Spreading load between CPUs
94decreases queue length. For low latency networking, the optimal setting
95is to allocate as many queues as there are CPUs in the system (or the
96NIC maximum, if lower). The most efficient high-rate configuration
97is likely the one with the smallest number of receive queues where no
98receive queue overflows due to a saturated CPU, because in default
99mode with interrupt coalescing enabled, the aggregate number of
100interrupts (and thus work) grows with each additional queue.
101
102Per-cpu load can be observed using the mpstat utility, but note that on
103processors with hyperthreading (HT), each hyperthread is represented as
104a separate CPU. For interrupt handling, HT has shown no benefit in
105initial tests, so limit the number of queues to the number of CPU cores
106in the system.
107
108
109RPS: Receive Packet Steering
110============================
111
112Receive Packet Steering (RPS) is logically a software implementation of
113RSS. Being in software, it is necessarily called later in the datapath.
114Whereas RSS selects the queue and hence CPU that will run the hardware
115interrupt handler, RPS selects the CPU to perform protocol processing
116above the interrupt handler. This is accomplished by placing the packet
117on the desired CPU’s backlog queue and waking up the CPU for processing.
118RPS has some advantages over RSS:
119
1201) it can be used with any NIC
1212) software filters can easily be added to hash over new protocols
1223) it does not increase hardware device interrupt rate (although it does
123   introduce inter-processor interrupts (IPIs))
124
125RPS is called during bottom half of the receive interrupt handler, when
126a driver sends a packet up the network stack with netif_rx() or
127netif_receive_skb(). These call the get_rps_cpu() function, which
128selects the queue that should process a packet.
129
130The first step in determining the target CPU for RPS is to calculate a
131flow hash over the packet’s addresses or ports (2-tuple or 4-tuple hash
132depending on the protocol). This serves as a consistent hash of the
133associated flow of the packet. The hash is either provided by hardware
134or will be computed in the stack. Capable hardware can pass the hash in
135the receive descriptor for the packet; this would usually be the same
136hash used for RSS (e.g. computed Toeplitz hash). The hash is saved in
137skb->hash and can be used elsewhere in the stack as a hash of the
138packet’s flow.
139
140Each receive hardware queue has an associated list of CPUs to which
141RPS may enqueue packets for processing. For each received packet,
142an index into the list is computed from the flow hash modulo the size
143of the list. The indexed CPU is the target for processing the packet,
144and the packet is queued to the tail of that CPU’s backlog queue. At
145the end of the bottom half routine, IPIs are sent to any CPUs for which
146packets have been queued to their backlog queue. The IPI wakes backlog
147processing on the remote CPU, and any queued packets are then processed
148up the networking stack.
149
150
151RPS Configuration
152-----------------
153
154RPS requires a kernel compiled with the CONFIG_RPS kconfig symbol (on
155by default for SMP). Even when compiled in, RPS remains disabled until
156explicitly configured. The list of CPUs to which RPS may forward traffic
157can be configured for each receive queue using a sysfs file entry::
158
159  /sys/class/net/<dev>/queues/rx-<n>/rps_cpus
160
161This file implements a bitmap of CPUs. RPS is disabled when it is zero
162(the default), in which case packets are processed on the interrupting
163CPU. Documentation/core-api/irq/irq-affinity.rst explains how CPUs are assigned to
164the bitmap.
165
166
167Suggested Configuration
168~~~~~~~~~~~~~~~~~~~~~~~
169
170For a single queue device, a typical RPS configuration would be to set
171the rps_cpus to the CPUs in the same memory domain of the interrupting
172CPU. If NUMA locality is not an issue, this could also be all CPUs in
173the system. At high interrupt rate, it might be wise to exclude the
174interrupting CPU from the map since that already performs much work.
175
176For a multi-queue system, if RSS is configured so that a hardware
177receive queue is mapped to each CPU, then RPS is probably redundant
178and unnecessary. If there are fewer hardware queues than CPUs, then
179RPS might be beneficial if the rps_cpus for each queue are the ones that
180share the same memory domain as the interrupting CPU for that queue.
181
182
183RPS Flow Limit
184--------------
185
186RPS scales kernel receive processing across CPUs without introducing
187reordering. The trade-off to sending all packets from the same flow
188to the same CPU is CPU load imbalance if flows vary in packet rate.
189In the extreme case a single flow dominates traffic. Especially on
190common server workloads with many concurrent connections, such
191behavior indicates a problem such as a misconfiguration or spoofed
192source Denial of Service attack.
193
194Flow Limit is an optional RPS feature that prioritizes small flows
195during CPU contention by dropping packets from large flows slightly
196ahead of those from small flows. It is active only when an RPS or RFS
197destination CPU approaches saturation.  Once a CPU's input packet
198queue exceeds half the maximum queue length (as set by sysctl
199net.core.netdev_max_backlog), the kernel starts a per-flow packet
200count over the last 256 packets. If a flow exceeds a set ratio (by
201default, half) of these packets when a new packet arrives, then the
202new packet is dropped. Packets from other flows are still only
203dropped once the input packet queue reaches netdev_max_backlog.
204No packets are dropped when the input packet queue length is below
205the threshold, so flow limit does not sever connections outright:
206even large flows maintain connectivity.
207
208
209Interface
210~~~~~~~~~
211
212Flow limit is compiled in by default (CONFIG_NET_FLOW_LIMIT), but not
213turned on. It is implemented for each CPU independently (to avoid lock
214and cache contention) and toggled per CPU by setting the relevant bit
215in sysctl net.core.flow_limit_cpu_bitmap. It exposes the same CPU
216bitmap interface as rps_cpus (see above) when called from procfs::
217
218  /proc/sys/net/core/flow_limit_cpu_bitmap
219
220Per-flow rate is calculated by hashing each packet into a hashtable
221bucket and incrementing a per-bucket counter. The hash function is
222the same that selects a CPU in RPS, but as the number of buckets can
223be much larger than the number of CPUs, flow limit has finer-grained
224identification of large flows and fewer false positives. The default
225table has 4096 buckets. This value can be modified through sysctl::
226
227  net.core.flow_limit_table_len
228
229The value is only consulted when a new table is allocated. Modifying
230it does not update active tables.
231
232
233Suggested Configuration
234~~~~~~~~~~~~~~~~~~~~~~~
235
236Flow limit is useful on systems with many concurrent connections,
237where a single connection taking up 50% of a CPU indicates a problem.
238In such environments, enable the feature on all CPUs that handle
239network rx interrupts (as set in /proc/irq/N/smp_affinity).
240
241The feature depends on the input packet queue length to exceed
242the flow limit threshold (50%) + the flow history length (256).
243Setting net.core.netdev_max_backlog to either 1000 or 10000
244performed well in experiments.
245
246
247RFS: Receive Flow Steering
248==========================
249
250While RPS steers packets solely based on hash, and thus generally
251provides good load distribution, it does not take into account
252application locality. This is accomplished by Receive Flow Steering
253(RFS). The goal of RFS is to increase datacache hitrate by steering
254kernel processing of packets to the CPU where the application thread
255consuming the packet is running. RFS relies on the same RPS mechanisms
256to enqueue packets onto the backlog of another CPU and to wake up that
257CPU.
258
259In RFS, packets are not forwarded directly by the value of their hash,
260but the hash is used as index into a flow lookup table. This table maps
261flows to the CPUs where those flows are being processed. The flow hash
262(see RPS section above) is used to calculate the index into this table.
263The CPU recorded in each entry is the one which last processed the flow.
264If an entry does not hold a valid CPU, then packets mapped to that entry
265are steered using plain RPS. Multiple table entries may point to the
266same CPU. Indeed, with many flows and few CPUs, it is very likely that
267a single application thread handles flows with many different flow hashes.
268
269rps_sock_flow_table is a global flow table that contains the *desired* CPU
270for flows: the CPU that is currently processing the flow in userspace.
271Each table value is a CPU index that is updated during calls to recvmsg
272and sendmsg (specifically, inet_recvmsg(), inet_sendmsg() and
273tcp_splice_read()).
274
275When the scheduler moves a thread to a new CPU while it has outstanding
276receive packets on the old CPU, packets may arrive out of order. To
277avoid this, RFS uses a second flow table to track outstanding packets
278for each flow: rps_dev_flow_table is a table specific to each hardware
279receive queue of each device. Each table value stores a CPU index and a
280counter. The CPU index represents the *current* CPU onto which packets
281for this flow are enqueued for further kernel processing. Ideally, kernel
282and userspace processing occur on the same CPU, and hence the CPU index
283in both tables is identical. This is likely false if the scheduler has
284recently migrated a userspace thread while the kernel still has packets
285enqueued for kernel processing on the old CPU.
286
287The counter in rps_dev_flow_table values records the length of the current
288CPU's backlog when a packet in this flow was last enqueued. Each backlog
289queue has a head counter that is incremented on dequeue. A tail counter
290is computed as head counter + queue length. In other words, the counter
291in rps_dev_flow[i] records the last element in flow i that has
292been enqueued onto the currently designated CPU for flow i (of course,
293entry i is actually selected by hash and multiple flows may hash to the
294same entry i).
295
296And now the trick for avoiding out of order packets: when selecting the
297CPU for packet processing (from get_rps_cpu()) the rps_sock_flow table
298and the rps_dev_flow table of the queue that the packet was received on
299are compared. If the desired CPU for the flow (found in the
300rps_sock_flow table) matches the current CPU (found in the rps_dev_flow
301table), the packet is enqueued onto that CPU’s backlog. If they differ,
302the current CPU is updated to match the desired CPU if one of the
303following is true:
304
305  - The current CPU's queue head counter >= the recorded tail counter
306    value in rps_dev_flow[i]
307  - The current CPU is unset (>= nr_cpu_ids)
308  - The current CPU is offline
309
310After this check, the packet is sent to the (possibly updated) current
311CPU. These rules aim to ensure that a flow only moves to a new CPU when
312there are no packets outstanding on the old CPU, as the outstanding
313packets could arrive later than those about to be processed on the new
314CPU.
315
316
317RFS Configuration
318-----------------
319
320RFS is only available if the kconfig symbol CONFIG_RPS is enabled (on
321by default for SMP). The functionality remains disabled until explicitly
322configured. The number of entries in the global flow table is set through::
323
324  /proc/sys/net/core/rps_sock_flow_entries
325
326The number of entries in the per-queue flow table are set through::
327
328  /sys/class/net/<dev>/queues/rx-<n>/rps_flow_cnt
329
330
331Suggested Configuration
332~~~~~~~~~~~~~~~~~~~~~~~
333
334Both of these need to be set before RFS is enabled for a receive queue.
335Values for both are rounded up to the nearest power of two. The
336suggested flow count depends on the expected number of active connections
337at any given time, which may be significantly less than the number of open
338connections. We have found that a value of 32768 for rps_sock_flow_entries
339works fairly well on a moderately loaded server.
340
341For a single queue device, the rps_flow_cnt value for the single queue
342would normally be configured to the same value as rps_sock_flow_entries.
343For a multi-queue device, the rps_flow_cnt for each queue might be
344configured as rps_sock_flow_entries / N, where N is the number of
345queues. So for instance, if rps_sock_flow_entries is set to 32768 and there
346are 16 configured receive queues, rps_flow_cnt for each queue might be
347configured as 2048.
348
349
350Accelerated RFS
351===============
352
353Accelerated RFS is to RFS what RSS is to RPS: a hardware-accelerated load
354balancing mechanism that uses soft state to steer flows based on where
355the application thread consuming the packets of each flow is running.
356Accelerated RFS should perform better than RFS since packets are sent
357directly to a CPU local to the thread consuming the data. The target CPU
358will either be the same CPU where the application runs, or at least a CPU
359which is local to the application thread’s CPU in the cache hierarchy.
360
361To enable accelerated RFS, the networking stack calls the
362ndo_rx_flow_steer driver function to communicate the desired hardware
363queue for packets matching a particular flow. The network stack
364automatically calls this function every time a flow entry in
365rps_dev_flow_table is updated. The driver in turn uses a device specific
366method to program the NIC to steer the packets.
367
368The hardware queue for a flow is derived from the CPU recorded in
369rps_dev_flow_table. The stack consults a CPU to hardware queue map which
370is maintained by the NIC driver. This is an auto-generated reverse map of
371the IRQ affinity table shown by /proc/interrupts. Drivers can use
372functions in the cpu_rmap (“CPU affinity reverse map”) kernel library
373to populate the map. For each CPU, the corresponding queue in the map is
374set to be one whose processing CPU is closest in cache locality.
375
376
377Accelerated RFS Configuration
378-----------------------------
379
380Accelerated RFS is only available if the kernel is compiled with
381CONFIG_RFS_ACCEL and support is provided by the NIC device and driver.
382It also requires that ntuple filtering is enabled via ethtool. The map
383of CPU to queues is automatically deduced from the IRQ affinities
384configured for each receive queue by the driver, so no additional
385configuration should be necessary.
386
387
388Suggested Configuration
389~~~~~~~~~~~~~~~~~~~~~~~
390
391This technique should be enabled whenever one wants to use RFS and the
392NIC supports hardware acceleration.
393
394
395XPS: Transmit Packet Steering
396=============================
397
398Transmit Packet Steering is a mechanism for intelligently selecting
399which transmit queue to use when transmitting a packet on a multi-queue
400device. This can be accomplished by recording two kinds of maps, either
401a mapping of CPU to hardware queue(s) or a mapping of receive queue(s)
402to hardware transmit queue(s).
403
4041. XPS using CPUs map
405
406The goal of this mapping is usually to assign queues
407exclusively to a subset of CPUs, where the transmit completions for
408these queues are processed on a CPU within this set. This choice
409provides two benefits. First, contention on the device queue lock is
410significantly reduced since fewer CPUs contend for the same queue
411(contention can be eliminated completely if each CPU has its own
412transmit queue). Secondly, cache miss rate on transmit completion is
413reduced, in particular for data cache lines that hold the sk_buff
414structures.
415
4162. XPS using receive queues map
417
418This mapping is used to pick transmit queue based on the receive
419queue(s) map configuration set by the administrator. A set of receive
420queues can be mapped to a set of transmit queues (many:many), although
421the common use case is a 1:1 mapping. This will enable sending packets
422on the same queue associations for transmit and receive. This is useful for
423busy polling multi-threaded workloads where there are challenges in
424associating a given CPU to a given application thread. The application
425threads are not pinned to CPUs and each thread handles packets
426received on a single queue. The receive queue number is cached in the
427socket for the connection. In this model, sending the packets on the same
428transmit queue corresponding to the associated receive queue has benefits
429in keeping the CPU overhead low. Transmit completion work is locked into
430the same queue-association that a given application is polling on. This
431avoids the overhead of triggering an interrupt on another CPU. When the
432application cleans up the packets during the busy poll, transmit completion
433may be processed along with it in the same thread context and so result in
434reduced latency.
435
436XPS is configured per transmit queue by setting a bitmap of
437CPUs/receive-queues that may use that queue to transmit. The reverse
438mapping, from CPUs to transmit queues or from receive-queues to transmit
439queues, is computed and maintained for each network device. When
440transmitting the first packet in a flow, the function get_xps_queue() is
441called to select a queue. This function uses the ID of the receive queue
442for the socket connection for a match in the receive queue-to-transmit queue
443lookup table. Alternatively, this function can also use the ID of the
444running CPU as a key into the CPU-to-queue lookup table. If the
445ID matches a single queue, that is used for transmission. If multiple
446queues match, one is selected by using the flow hash to compute an index
447into the set. When selecting the transmit queue based on receive queue(s)
448map, the transmit device is not validated against the receive device as it
449requires expensive lookup operation in the datapath.
450
451The queue chosen for transmitting a particular flow is saved in the
452corresponding socket structure for the flow (e.g. a TCP connection).
453This transmit queue is used for subsequent packets sent on the flow to
454prevent out of order (ooo) packets. The choice also amortizes the cost
455of calling get_xps_queues() over all packets in the flow. To avoid
456ooo packets, the queue for a flow can subsequently only be changed if
457skb->ooo_okay is set for a packet in the flow. This flag indicates that
458there are no outstanding packets in the flow, so the transmit queue can
459change without the risk of generating out of order packets. The
460transport layer is responsible for setting ooo_okay appropriately. TCP,
461for instance, sets the flag when all data for a connection has been
462acknowledged.
463
464XPS Configuration
465-----------------
466
467XPS is only available if the kconfig symbol CONFIG_XPS is enabled (on by
468default for SMP). If compiled in, it is driver dependent whether, and
469how, XPS is configured at device init. The mapping of CPUs/receive-queues
470to transmit queue can be inspected and configured using sysfs:
471
472For selection based on CPUs map::
473
474  /sys/class/net/<dev>/queues/tx-<n>/xps_cpus
475
476For selection based on receive-queues map::
477
478  /sys/class/net/<dev>/queues/tx-<n>/xps_rxqs
479
480
481Suggested Configuration
482~~~~~~~~~~~~~~~~~~~~~~~
483
484For a network device with a single transmission queue, XPS configuration
485has no effect, since there is no choice in this case. In a multi-queue
486system, XPS is preferably configured so that each CPU maps onto one queue.
487If there are as many queues as there are CPUs in the system, then each
488queue can also map onto one CPU, resulting in exclusive pairings that
489experience no contention. If there are fewer queues than CPUs, then the
490best CPUs to share a given queue are probably those that share the cache
491with the CPU that processes transmit completions for that queue
492(transmit interrupts).
493
494For transmit queue selection based on receive queue(s), XPS has to be
495explicitly configured mapping receive-queue(s) to transmit queue(s). If the
496user configuration for receive-queue map does not apply, then the transmit
497queue is selected based on the CPUs map.
498
499
500Per TX Queue rate limitation
501============================
502
503These are rate-limitation mechanisms implemented by HW, where currently
504a max-rate attribute is supported, by setting a Mbps value to::
505
506  /sys/class/net/<dev>/queues/tx-<n>/tx_maxrate
507
508A value of zero means disabled, and this is the default.
509
510
511Further Information
512===================
513RPS and RFS were introduced in kernel 2.6.35. XPS was incorporated into
5142.6.38. Original patches were submitted by Tom Herbert
515(therbert@google.com)
516
517Accelerated RFS was introduced in 2.6.35. Original patches were
518submitted by Ben Hutchings (bwh@kernel.org)
519
520Authors:
521
522- Tom Herbert (therbert@google.com)
523- Willem de Bruijn (willemb@google.com)
524