net: add Documentation/networking/scaling.txt
[linux-2.6.git] / Documentation / networking / scaling.txt
1 Scaling in the Linux Networking Stack
2
3
4 Introduction
5 ============
6
7 This document describes a set of complementary techniques in the Linux
8 networking stack to increase parallelism and improve performance for
9 multi-processor systems.
10
11 The following technologies are described:
12
13   RSS: Receive Side Scaling
14   RPS: Receive Packet Steering
15   RFS: Receive Flow Steering
16   Accelerated Receive Flow Steering
17   XPS: Transmit Packet Steering
18
19
20 RSS: Receive Side Scaling
21 =========================
22
23 Contemporary NICs support multiple receive and transmit descriptor queues
24 (multi-queue). On reception, a NIC can send different packets to different
25 queues to distribute processing among CPUs. The NIC distributes packets by
26 applying a filter to each packet that assigns it to one of a small number
27 of logical flows. Packets for each flow are steered to a separate receive
28 queue, which in turn can be processed by separate CPUs. This mechanism is
29 generally known as “Receive-side Scaling” (RSS). The goal of RSS and
30 the other scaling techniques to increase performance uniformly.
31 Multi-queue distribution can also be used for traffic prioritization, but
32 that is not the focus of these techniques.
33
34 The filter used in RSS is typically a hash function over the network
35 and/or transport layer headers-- for example, a 4-tuple hash over
36 IP addresses and TCP ports of a packet. The most common hardware
37 implementation of RSS uses a 128-entry indirection table where each entry
38 stores a queue number. The receive queue for a packet is determined
39 by masking out the low order seven bits of the computed hash for the
40 packet (usually a Toeplitz hash), taking this number as a key into the
41 indirection table and reading the corresponding value.
42
43 Some advanced NICs allow steering packets to queues based on
44 programmable filters. For example, webserver bound TCP port 80 packets
45 can be directed to their own receive queue. Such “n-tuple” filters can
46 be configured from ethtool (--config-ntuple).
47
48 ==== RSS Configuration
49
50 The driver for a multi-queue capable NIC typically provides a kernel
51 module parameter for specifying the number of hardware queues to
52 configure. In the bnx2x driver, for instance, this parameter is called
53 num_queues. A typical RSS configuration would be to have one receive queue
54 for each CPU if the device supports enough queues, or otherwise at least
55 one for each cache domain at a particular cache level (L1, L2, etc.).
56
57 The indirection table of an RSS device, which resolves a queue by masked
58 hash, is usually programmed by the driver at initialization. The
59 default mapping is to distribute the queues evenly in the table, but the
60 indirection table can be retrieved and modified at runtime using ethtool
61 commands (--show-rxfh-indir and --set-rxfh-indir). Modifying the
62 indirection table could be done to give different queues different
63 relative weights.
64
65 == RSS IRQ Configuration
66
67 Each receive queue has a separate IRQ associated with it. The NIC triggers
68 this to notify a CPU when new packets arrive on the given queue. The
69 signaling path for PCIe devices uses message signaled interrupts (MSI-X),
70 that can route each interrupt to a particular CPU. The active mapping
71 of queues to IRQs can be determined from /proc/interrupts. By default,
72 an IRQ may be handled on any CPU. Because a non-negligible part of packet
73 processing takes place in receive interrupt handling, it is advantageous
74 to spread receive interrupts between CPUs. To manually adjust the IRQ
75 affinity of each interrupt see Documentation/IRQ-affinity. Some systems
76 will be running irqbalance, a daemon that dynamically optimizes IRQ
77 assignments and as a result may override any manual settings.
78
79 == Suggested Configuration
80
81 RSS should be enabled when latency is a concern or whenever receive
82 interrupt processing forms a bottleneck. Spreading load between CPUs
83 decreases queue length. For low latency networking, the optimal setting
84 is to allocate as many queues as there are CPUs in the system (or the
85 NIC maximum, if lower). Because the aggregate number of interrupts grows
86 with each additional queue, the most efficient high-rate configuration
87 is likely the one with the smallest number of receive queues where no
88 CPU that processes receive interrupts reaches 100% utilization. Per-cpu
89 load can be observed using the mpstat utility.
90
91
92 RPS: Receive Packet Steering
93 ============================
94
95 Receive Packet Steering (RPS) is logically a software implementation of
96 RSS. Being in software, it is necessarily called later in the datapath.
97 Whereas RSS selects the queue and hence CPU that will run the hardware
98 interrupt handler, RPS selects the CPU to perform protocol processing
99 above the interrupt handler. This is accomplished by placing the packet
100 on the desired CPU’s backlog queue and waking up the CPU for processing.
101 RPS has some advantages over RSS: 1) it can be used with any NIC,
102 2) software filters can easily be added to hash over new protocols,
103 3) it does not increase hardware device interrupt rate (although it does
104 introduce inter-processor interrupts (IPIs)).
105
106 RPS is called during bottom half of the receive interrupt handler, when
107 a driver sends a packet up the network stack with netif_rx() or
108 netif_receive_skb(). These call the get_rps_cpu() function, which
109 selects the queue that should process a packet.
110
111 The first step in determining the target CPU for RPS is to calculate a
112 flow hash over the packet’s addresses or ports (2-tuple or 4-tuple hash
113 depending on the protocol). This serves as a consistent hash of the
114 associated flow of the packet. The hash is either provided by hardware
115 or will be computed in the stack. Capable hardware can pass the hash in
116 the receive descriptor for the packet; this would usually be the same
117 hash used for RSS (e.g. computed Toeplitz hash). The hash is saved in
118 skb->rx_hash and can be used elsewhere in the stack as a hash of the
119 packet’s flow.
120
121 Each receive hardware queue has an associated list of CPUs to which
122 RPS may enqueue packets for processing. For each received packet,
123 an index into the list is computed from the flow hash modulo the size
124 of the list. The indexed CPU is the target for processing the packet,
125 and the packet is queued to the tail of that CPU’s backlog queue. At
126 the end of the bottom half routine, IPIs are sent to any CPUs for which
127 packets have been queued to their backlog queue. The IPI wakes backlog
128 processing on the remote CPU, and any queued packets are then processed
129 up the networking stack.
130
131 ==== RPS Configuration
132
133 RPS requires a kernel compiled with the CONFIG_RPS kconfig symbol (on
134 by default for SMP). Even when compiled in, RPS remains disabled until
135 explicitly configured. The list of CPUs to which RPS may forward traffic
136 can be configured for each receive queue using a sysfs file entry:
137
138  /sys/class/net/<dev>/queues/rx-<n>/rps_cpus
139
140 This file implements a bitmap of CPUs. RPS is disabled when it is zero
141 (the default), in which case packets are processed on the interrupting
142 CPU. Documentation/IRQ-affinity.txt explains how CPUs are assigned to
143 the bitmap.
144
145 == Suggested Configuration
146
147 For a single queue device, a typical RPS configuration would be to set
148 the rps_cpus to the CPUs in the same cache domain of the interrupting
149 CPU. If NUMA locality is not an issue, this could also be all CPUs in
150 the system. At high interrupt rate, it might be wise to exclude the
151 interrupting CPU from the map since that already performs much work.
152
153 For a multi-queue system, if RSS is configured so that a hardware
154 receive queue is mapped to each CPU, then RPS is probably redundant
155 and unnecessary. If there are fewer hardware queues than CPUs, then
156 RPS might be beneficial if the rps_cpus for each queue are the ones that
157 share the same cache domain as the interrupting CPU for that queue.
158
159
160 RFS: Receive Flow Steering
161 ==========================
162
163 While RPS steers packets solely based on hash, and thus generally
164 provides good load distribution, it does not take into account
165 application locality. This is accomplished by Receive Flow Steering
166 (RFS). The goal of RFS is to increase datacache hitrate by steering
167 kernel processing of packets to the CPU where the application thread
168 consuming the packet is running. RFS relies on the same RPS mechanisms
169 to enqueue packets onto the backlog of another CPU and to wake up that
170 CPU.
171
172 In RFS, packets are not forwarded directly by the value of their hash,
173 but the hash is used as index into a flow lookup table. This table maps
174 flows to the CPUs where those flows are being processed. The flow hash
175 (see RPS section above) is used to calculate the index into this table.
176 The CPU recorded in each entry is the one which last processed the flow.
177 If an entry does not hold a valid CPU, then packets mapped to that entry
178 are steered using plain RPS. Multiple table entries may point to the
179 same CPU. Indeed, with many flows and few CPUs, it is very likely that
180 a single application thread handles flows with many different flow hashes.
181
182 rps_sock_table is a global flow table that contains the *desired* CPU for
183 flows: the CPU that is currently processing the flow in userspace. Each
184 table value is a CPU index that is updated during calls to recvmsg and
185 sendmsg (specifically, inet_recvmsg(), inet_sendmsg(), inet_sendpage()
186 and tcp_splice_read()).
187
188 When the scheduler moves a thread to a new CPU while it has outstanding
189 receive packets on the old CPU, packets may arrive out of order. To
190 avoid this, RFS uses a second flow table to track outstanding packets
191 for each flow: rps_dev_flow_table is a table specific to each hardware
192 receive queue of each device. Each table value stores a CPU index and a
193 counter. The CPU index represents the *current* CPU onto which packets
194 for this flow are enqueued for further kernel processing. Ideally, kernel
195 and userspace processing occur on the same CPU, and hence the CPU index
196 in both tables is identical. This is likely false if the scheduler has
197 recently migrated a userspace thread while the kernel still has packets
198 enqueued for kernel processing on the old CPU.
199
200 The counter in rps_dev_flow_table values records the length of the current
201 CPU's backlog when a packet in this flow was last enqueued. Each backlog
202 queue has a head counter that is incremented on dequeue. A tail counter
203 is computed as head counter + queue length. In other words, the counter
204 in rps_dev_flow_table[i] records the last element in flow i that has
205 been enqueued onto the currently designated CPU for flow i (of course,
206 entry i is actually selected by hash and multiple flows may hash to the
207 same entry i).
208
209 And now the trick for avoiding out of order packets: when selecting the
210 CPU for packet processing (from get_rps_cpu()) the rps_sock_flow table
211 and the rps_dev_flow table of the queue that the packet was received on
212 are compared. If the desired CPU for the flow (found in the
213 rps_sock_flow table) matches the current CPU (found in the rps_dev_flow
214 table), the packet is enqueued onto that CPU’s backlog. If they differ,
215 the current CPU is updated to match the desired CPU if one of the
216 following is true:
217
218 - The current CPU's queue head counter >= the recorded tail counter
219   value in rps_dev_flow[i]
220 - The current CPU is unset (equal to NR_CPUS)
221 - The current CPU is offline
222
223 After this check, the packet is sent to the (possibly updated) current
224 CPU. These rules aim to ensure that a flow only moves to a new CPU when
225 there are no packets outstanding on the old CPU, as the outstanding
226 packets could arrive later than those about to be processed on the new
227 CPU.
228
229 ==== RFS Configuration
230
231 RFS is only available if the kconfig symbol CONFIG_RFS is enabled (on
232 by default for SMP). The functionality remains disabled until explicitly
233 configured. The number of entries in the global flow table is set through:
234
235  /proc/sys/net/core/rps_sock_flow_entries
236
237 The number of entries in the per-queue flow table are set through:
238
239  /sys/class/net/<dev>/queues/tx-<n>/rps_flow_cnt
240
241 == Suggested Configuration
242
243 Both of these need to be set before RFS is enabled for a receive queue.
244 Values for both are rounded up to the nearest power of two. The
245 suggested flow count depends on the expected number of active connections
246 at any given time, which may be significantly less than the number of open
247 connections. We have found that a value of 32768 for rps_sock_flow_entries
248 works fairly well on a moderately loaded server.
249
250 For a single queue device, the rps_flow_cnt value for the single queue
251 would normally be configured to the same value as rps_sock_flow_entries.
252 For a multi-queue device, the rps_flow_cnt for each queue might be
253 configured as rps_sock_flow_entries / N, where N is the number of
254 queues. So for instance, if rps_flow_entries is set to 32768 and there
255 are 16 configured receive queues, rps_flow_cnt for each queue might be
256 configured as 2048.
257
258
259 Accelerated RFS
260 ===============
261
262 Accelerated RFS is to RFS what RSS is to RPS: a hardware-accelerated load
263 balancing mechanism that uses soft state to steer flows based on where
264 the application thread consuming the packets of each flow is running.
265 Accelerated RFS should perform better than RFS since packets are sent
266 directly to a CPU local to the thread consuming the data. The target CPU
267 will either be the same CPU where the application runs, or at least a CPU
268 which is local to the application thread’s CPU in the cache hierarchy.
269
270 To enable accelerated RFS, the networking stack calls the
271 ndo_rx_flow_steer driver function to communicate the desired hardware
272 queue for packets matching a particular flow. The network stack
273 automatically calls this function every time a flow entry in
274 rps_dev_flow_table is updated. The driver in turn uses a device specific
275 method to program the NIC to steer the packets.
276
277 The hardware queue for a flow is derived from the CPU recorded in
278 rps_dev_flow_table. The stack consults a CPU to hardware queue map which
279 is maintained by the NIC driver. This is an auto-generated reverse map of
280 the IRQ affinity table shown by /proc/interrupts. Drivers can use
281 functions in the cpu_rmap (“CPU affinity reverse map”) kernel library
282 to populate the map. For each CPU, the corresponding queue in the map is
283 set to be one whose processing CPU is closest in cache locality.
284
285 ==== Accelerated RFS Configuration
286
287 Accelerated RFS is only available if the kernel is compiled with
288 CONFIG_RFS_ACCEL and support is provided by the NIC device and driver.
289 It also requires that ntuple filtering is enabled via ethtool. The map
290 of CPU to queues is automatically deduced from the IRQ affinities
291 configured for each receive queue by the driver, so no additional
292 configuration should be necessary.
293
294 == Suggested Configuration
295
296 This technique should be enabled whenever one wants to use RFS and the
297 NIC supports hardware acceleration.
298
299 XPS: Transmit Packet Steering
300 =============================
301
302 Transmit Packet Steering is a mechanism for intelligently selecting
303 which transmit queue to use when transmitting a packet on a multi-queue
304 device. To accomplish this, a mapping from CPU to hardware queue(s) is
305 recorded. The goal of this mapping is usually to assign queues
306 exclusively to a subset of CPUs, where the transmit completions for
307 these queues are processed on a CPU within this set. This choice
308 provides two benefits. First, contention on the device queue lock is
309 significantly reduced since fewer CPUs contend for the same queue
310 (contention can be eliminated completely if each CPU has its own
311 transmit queue). Secondly, cache miss rate on transmit completion is
312 reduced, in particular for data cache lines that hold the sk_buff
313 structures.
314
315 XPS is configured per transmit queue by setting a bitmap of CPUs that
316 may use that queue to transmit. The reverse mapping, from CPUs to
317 transmit queues, is computed and maintained for each network device.
318 When transmitting the first packet in a flow, the function
319 get_xps_queue() is called to select a queue. This function uses the ID
320 of the running CPU as a key into the CPU-to-queue lookup table. If the
321 ID matches a single queue, that is used for transmission. If multiple
322 queues match, one is selected by using the flow hash to compute an index
323 into the set.
324
325 The queue chosen for transmitting a particular flow is saved in the
326 corresponding socket structure for the flow (e.g. a TCP connection).
327 This transmit queue is used for subsequent packets sent on the flow to
328 prevent out of order (ooo) packets. The choice also amortizes the cost
329 of calling get_xps_queues() over all packets in the connection. To avoid
330 ooo packets, the queue for a flow can subsequently only be changed if
331 skb->ooo_okay is set for a packet in the flow. This flag indicates that
332 there are no outstanding packets in the flow, so the transmit queue can
333 change without the risk of generating out of order packets. The
334 transport layer is responsible for setting ooo_okay appropriately. TCP,
335 for instance, sets the flag when all data for a connection has been
336 acknowledged.
337
338 ==== XPS Configuration
339
340 XPS is only available if the kconfig symbol CONFIG_XPS is enabled (on by
341 default for SMP). The functionality remains disabled until explicitly
342 configured. To enable XPS, the bitmap of CPUs that may use a transmit
343 queue is configured using the sysfs file entry:
344
345 /sys/class/net/<dev>/queues/tx-<n>/xps_cpus
346
347 == Suggested Configuration
348
349 For a network device with a single transmission queue, XPS configuration
350 has no effect, since there is no choice in this case. In a multi-queue
351 system, XPS is preferably configured so that each CPU maps onto one queue.
352 If there are as many queues as there are CPUs in the system, then each
353 queue can also map onto one CPU, resulting in exclusive pairings that
354 experience no contention. If there are fewer queues than CPUs, then the
355 best CPUs to share a given queue are probably those that share the cache
356 with the CPU that processes transmit completions for that queue
357 (transmit interrupts).
358
359
360 Further Information
361 ===================
362 RPS and RFS were introduced in kernel 2.6.35. XPS was incorporated into
363 2.6.38. Original patches were submitted by Tom Herbert
364 (therbert@google.com)
365
366 Accelerated RFS was introduced in 2.6.35. Original patches were
367 submitted by Ben Hutchings (bhutchings@solarflare.com)
368
369 Authors:
370 Tom Herbert (therbert@google.com)
371 Willem de Bruijn (willemb@google.com)