Lines Matching refs:the

1 Scaling in the Linux Networking Stack
7 This document describes a set of complementary techniques in the Linux
30 the other scaling techniques is to increase performance uniformly.
32 that is not the focus of these techniques.
34 The filter used in RSS is typically a hash function over the network
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.
51 module parameter for specifying the number of hardware queues to
52 configure. In the bnx2x driver, for instance, this parameter is called
54 for each CPU if the device supports enough queues, or otherwise at least
59 hash, is usually programmed by the driver at initialization. The
60 default mapping is to distribute the queues evenly in the table, but the
62 commands (--show-rxfh-indir and --set-rxfh-indir). Modifying the
69 this to notify a CPU when new packets arrive on the given queue. The
75 to spread receive interrupts between CPUs. To manually adjust the IRQ
84 decreases queue length. For low latency networking, the optimal setting
85 is to allocate as many queues as there are CPUs in the system (or the
87 is likely the one with the smallest number of receive queues where no
89 mode with interrupt coalescing enabled, the aggregate number of
92 Per-cpu load can be observed using the mpstat utility, but note that on
95 initial tests, so limit the number of queues to the number of CPU cores
96 in the system.
103 RSS. Being in software, it is necessarily called later in the datapath.
104 Whereas RSS selects the queue and hence CPU that will run the hardware
105 interrupt handler, RPS selects the CPU to perform protocol processing
106 above the interrupt handler. This is accomplished by placing the packet
107 on the desired CPU’s backlog queue and waking up the CPU for processing.
113 RPS is called during bottom half of the receive interrupt handler, when
114 a driver sends a packet up the network stack with netif_rx() or
115 netif_receive_skb(). These call the get_rps_cpu() function, which
116 selects the queue that should process a packet.
118 The first step in determining the target CPU for RPS is to calculate a
119 flow hash over the packet’s addresses or ports (2-tuple or 4-tuple hash
120 depending on the protocol). This serves as a consistent hash of the
121 associated flow of the packet. The hash is either provided by hardware
122 or will be computed in the stack. Capable hardware can pass the hash in
123 the receive descriptor for the packet; this would usually be the same
125 skb->rx_hash and can be used elsewhere in the stack as a hash of the
130 an index into the list is computed from the flow hash modulo the size
131 of the list. The indexed CPU is the target for processing the packet,
132 and the packet is queued to the tail of that CPU’s backlog queue. At
133 the end of the bottom half routine, IPIs are sent to any CPUs for which
135 processing on the remote CPU, and any queued packets are then processed
136 up the networking stack.
140 RPS requires a kernel compiled with the CONFIG_RPS kconfig symbol (on
148 (the default), in which case packets are processed on the interrupting
150 the bitmap.
155 the rps_cpus to the CPUs in the same memory domain of the interrupting
157 the system. At high interrupt rate, it might be wise to exclude the
158 interrupting CPU from the map since that already performs much work.
163 RPS might be beneficial if the rps_cpus for each queue are the ones that
164 share the same memory domain as the interrupting CPU for that queue.
169 reordering. The trade-off to sending all packets from the same flow
170 to the same CPU is CPU load imbalance if flows vary in packet rate.
171 In the extreme case a single flow dominates traffic. Especially on
180 queue exceeds half the maximum queue length (as set by sysctl
181 net.core.netdev_max_backlog), the kernel starts a per-flow packet
182 count over the last 256 packets. If a flow exceeds a set ratio (by
183 default, half) of these packets when a new packet arrives, then the
185 dropped once the input packet queue reaches netdev_max_backlog.
186 No packets are dropped when the input packet queue length is below
187 the threshold, so flow limit does not sever connections outright:
194 and cache contention) and toggled per CPU by setting the relevant bit
195 in sysctl net.core.flow_limit_cpu_bitmap. It exposes the same CPU
202 the same that selects a CPU in RPS, but as the number of buckets can
203 be much larger than the number of CPUs, flow limit has finer-grained
216 In such environments, enable the feature on all CPUs that handle
219 The feature depends on the input packet queue length to exceed
220 the flow limit threshold (50%) + the flow history length (256).
232 kernel processing of packets to the CPU where the application thread
233 consuming the packet is running. RFS relies on the same RPS mechanisms
234 to enqueue packets onto the backlog of another CPU and to wake up that
237 In RFS, packets are not forwarded directly by the value of their hash,
238 but the hash is used as index into a flow lookup table. This table maps
239 flows to the CPUs where those flows are being processed. The flow hash
240 (see RPS section above) is used to calculate the index into this table.
241 The CPU recorded in each entry is the one which last processed the flow.
243 are steered using plain RPS. Multiple table entries may point to the
247 rps_sock_flow_table is a global flow table that contains the *desired* CPU
248 for flows: the CPU that is currently processing the flow in userspace.
253 When the scheduler moves a thread to a new CPU while it has outstanding
254 receive packets on the old CPU, packets may arrive out of order. To
258 counter. The CPU index represents the *current* CPU onto which packets
260 and userspace processing occur on the same CPU, and hence the CPU index
261 in both tables is identical. This is likely false if the scheduler has
262 recently migrated a userspace thread while the kernel still has packets
263 enqueued for kernel processing on the old CPU.
265 The counter in rps_dev_flow_table values records the length of the current
268 is computed as head counter + queue length. In other words, the counter
269 in rps_dev_flow[i] records the last element in flow i that has
270 been enqueued onto the currently designated CPU for flow i (of course,
271 entry i is actually selected by hash and multiple flows may hash to the
274 And now the trick for avoiding out of order packets: when selecting the
275 CPU for packet processing (from get_rps_cpu()) the rps_sock_flow table
276 and the rps_dev_flow table of the queue that the packet was received on
277 are compared. If the desired CPU for the flow (found in the
278 rps_sock_flow table) matches the current CPU (found in the rps_dev_flow
279 table), the packet is enqueued onto that CPU’s backlog. If they differ,
280 the current CPU is updated to match the desired CPU if one of the
283 - The current CPU's queue head counter >= the recorded tail counter
288 After this check, the packet is sent to the (possibly updated) current
290 there are no packets outstanding on the old CPU, as the outstanding
291 packets could arrive later than those about to be processed on the new
296 RFS is only available if the kconfig symbol CONFIG_RPS is enabled (on
298 configured. The number of entries in the global flow table is set through:
302 The number of entries in the per-queue flow table are set through:
309 Values for both are rounded up to the nearest power of two. The
310 suggested flow count depends on the expected number of active connections
311 at any given time, which may be significantly less than the number of open
315 For a single queue device, the rps_flow_cnt value for the single queue
316 would normally be configured to the same value as rps_sock_flow_entries.
317 For a multi-queue device, the rps_flow_cnt for each queue might be
318 configured as rps_sock_flow_entries / N, where N is the number of
329 the application thread consuming the packets of each flow is running.
331 directly to a CPU local to the thread consuming the data. The target CPU
332 will either be the same CPU where the application runs, or at least a CPU
333 which is local to the application thread’s CPU in the cache hierarchy.
335 To enable accelerated RFS, the networking stack calls the
336 ndo_rx_flow_steer driver function to communicate the desired hardware
340 method to program the NIC to steer the packets.
342 The hardware queue for a flow is derived from the CPU recorded in
344 is maintained by the NIC driver. This is an auto-generated reverse map of
345 the IRQ affinity table shown by /proc/interrupts. Drivers can use
346 functions in the cpu_rmap (“CPU affinity reverse map”) kernel library
347 to populate the map. For each CPU, the corresponding queue in the map is
352 Accelerated RFS is only available if the kernel is compiled with
353 CONFIG_RFS_ACCEL and support is provided by the NIC device and driver.
355 of CPU to queues is automatically deduced from the IRQ affinities
356 configured for each receive queue by the driver, so no additional
361 This technique should be enabled whenever one wants to use RFS and the
371 exclusively to a subset of CPUs, where the transmit completions for
373 provides two benefits. First, contention on the device queue lock is
374 significantly reduced since fewer CPUs contend for the same queue
377 reduced, in particular for data cache lines that hold the sk_buff
383 When transmitting the first packet in a flow, the function
384 get_xps_queue() is called to select a queue. This function uses the ID
385 of the running CPU as a key into the CPU-to-queue lookup table. If the
387 queues match, one is selected by using the flow hash to compute an index
388 into the set.
390 The queue chosen for transmitting a particular flow is saved in the
391 corresponding socket structure for the flow (e.g. a TCP connection).
392 This transmit queue is used for subsequent packets sent on the flow to
393 prevent out of order (ooo) packets. The choice also amortizes the cost
394 of calling get_xps_queues() over all packets in the flow. To avoid
395 ooo packets, the queue for a flow can subsequently only be changed if
396 skb->ooo_okay is set for a packet in the flow. This flag indicates that
397 there are no outstanding packets in the flow, so the transmit queue can
398 change without the risk of generating out of order packets. The
400 for instance, sets the flag when all data for a connection has been
405 XPS is only available if the kconfig symbol CONFIG_XPS is enabled (on by
407 configured. To enable XPS, the bitmap of CPUs that may use a transmit
408 queue is configured using the sysfs file entry:
417 If there are as many queues as there are CPUs in the system, then each
419 experience no contention. If there are fewer queues than CPUs, then the
420 best CPUs to share a given queue are probably those that share the cache
421 with the CPU that processes transmit completions for that queue
432 A value of zero means disabled, and this is the default.