scaling.rst 24 KB

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