Linux 네트워킹 스택 확장 기법

다중 프로세서 네트워크 처리 확장

이 문서는 다중 프로세서 시스템에서 Linux 네트워킹 스택의 병렬성을 높이고 성능을 개선하는 상호 보완적 기법을 설명합니다. 다루는 기술은 수신 측 하드웨어 분산인 RSS, 소프트웨어 수신 분산인 RPS, 응용 프로그램의 CPU 위치를 따르는 RFS와 accelerated RFS, 송신 큐를 고르는 XPS입니다.

이 기법들은 모두 패킷을 어느 큐와 CPU에서 처리할지 결정하지만 선택 시점과 목표가 다릅니다. RSS는 NIC 수신 전에 하드웨어 큐를 고르고, RPS는 수신 인터럽트 아래쪽 처리에서 프로토콜 처리 CPU를 고릅니다. RFS는 소비 응용 스레드와의 캐시 지역성을 추가하고, accelerated RFS는 그 결정을 NIC에 반영합니다. XPS는 반대 방향인 송신 큐 선택을 최적화합니다.

.. SPDX-License-Identifier: GPL-2.0

=====================================
Scaling in the Linux Networking Stack
=====================================


Introduction
============

This document describes a set of complementary techniques in the Linux
networking stack to increase parallelism and improve performance for
multi-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: 하드웨어 수신 큐 분산

현대 NIC는 여러 수신·송신 descriptor queue를 지원합니다. 수신 시 NIC는 패킷을 논리적 flow로 분류해 서로 다른 Rx queue에 보내고, 각 큐를 별도 CPU가 처리하게 할 수 있습니다. 이 Receive Side Scaling의 목표는 트래픽 우선순위 지정이 아니라 처리량을 여러 CPU에 고르게 분산하는 것입니다.

RSS 필터는 보통 네트워크와 전송 계층 헤더를 해시합니다. 대표적으로 IP 출발지·목적지와 TCP 포트 쌍을 포함한 4-tuple을 Toeplitz hash로 계산합니다. 흔한 하드웨어 구현은 큐 번호를 담은 128-entry indirection table을 사용합니다. 해시 하위 7비트를 table index로 삼고 해당 entry의 큐 번호를 읽어 패킷의 Rx queue를 결정합니다.

일부 NIC는 양방향 flow가 같은 해시를 갖는 symmetric RSS를 지원합니다. 출발지와 목적지 IP, TCP/UDP 포트를 서로 바꿔도 같은 Rx queue와 CPU에 도착하므로 IDS나 firewall처럼 양방향을 함께 추적하는 프로그램에 유용합니다. `Symmetric-XOR`는 `(SRC_IP ^ DST_IP, SRC_IP ^ DST_IP, SRC_PORT ^ DST_PORT, SRC_PORT ^ DST_PORT)`로 입력을 바꿉니다. `Symmetric-OR-XOR`는 `(SRC_IP | DST_IP, SRC_IP ^ DST_IP, SRC_PORT | DST_PORT, SRC_PORT ^ DST_PORT)`를 사용한 뒤 기본 RSS 알고리즘에 넣습니다.

대칭 알고리즘은 출발지와 목적지 필드를 XOR 또는 OR로 합쳐 입력 entropy를 줄이므로 악용 가능성을 고려해야 합니다. 고급 NIC는 프로그래밍 가능한 n-tuple filter도 지원합니다. 예를 들어 TCP 목적지 포트 80 트래픽만 전용 큐로 보낼 수 있으며 `ethtool --config-ntuple`로 설정합니다.

RSS: Receive Side Scaling
=========================

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

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

Some NICs support symmetric RSS hashing where, if the IP (source address,
destination address) and TCP/UDP (source port, destination port) tuples
are swapped, the computed hash is the same. This is beneficial in some
applications that monitor TCP/IP flows (IDS, firewalls, ...etc) and need
both directions of the flow to land on the same Rx queue (and CPU). The
"Symmetric-XOR" and "Symmetric-OR-XOR" are types of RSS algorithms that
achieve this hash symmetry by XOR/ORing the input source and destination
fields of the IP and/or L4 protocols. This, however, results in reduced
input entropy and could potentially be exploited.

Specifically, the "Symmetric-XOR" algorithm XORs the input
as follows::

    # (SRC_IP ^ DST_IP, SRC_IP ^ DST_IP, SRC_PORT ^ DST_PORT, SRC_PORT ^ DST_PORT)

The "Symmetric-OR-XOR" algorithm, on the other hand, transforms the input as
follows::

    # (SRC_IP | DST_IP, SRC_IP ^ DST_IP, SRC_PORT | DST_PORT, SRC_PORT ^ DST_PORT)

The result is then fed to the underlying RSS algorithm.

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

RSS 큐, IRQ affinity와 권장 설정

멀티큐 NIC 드라이버는 보통 하드웨어 큐 수를 정하는 모듈 매개변수를 제공합니다. 예를 들어 bnx2x의 이름은 `num_queues`입니다. 큐가 충분하면 CPU마다 Rx queue 하나를 배치하고, 부족하면 적어도 L1·L2 cache나 NUMA node 같은 메모리 계층을 공유하는 memory domain마다 하나를 배치하는 구성이 일반적입니다.

드라이버는 초기화할 때 RSS indirection table을 보통 균등하게 채웁니다. `ethtool --show-rxfh-indir`로 table을 조회하고 `--set-rxfh-indir`로 실행 중에 바꿀 수 있습니다. 같은 큐 번호를 더 많은 entry에 넣으면 큐별 상대 가중치도 조정할 수 있습니다.

Rx queue마다 별도 IRQ가 있으며 PCIe 장치는 보통 MSI-X로 각 인터럽트를 특정 CPU에 라우팅합니다. 실제 queue·IRQ 연결은 `/proc/interrupts`에서 확인합니다. 수신 처리의 적지 않은 부분이 인터럽트 문맥에서 수행되므로 IRQ를 여러 CPU에 분산하는 것이 좋습니다. 수동 affinity 설정은 `Documentation/core-api/irq/irq-affinity.rst`를 따르며, 실행 중인 `irqbalance`가 수동 값을 덮어쓸 수 있습니다.

지연이 중요하거나 수신 인터럽트가 병목이면 RSS를 켭니다. 낮은 지연에는 CPU 수와 같은 큐 수, 또는 NIC 최대치를 사용합니다. 높은 packet rate에서는 어떤 큐도 CPU 포화로 overflow하지 않는 범위에서 가장 적은 큐가 효율적일 수 있습니다. interrupt coalescing 기본 모드에서도 큐가 늘수록 전체 인터럽트와 작업량이 증가하기 때문입니다.

CPU별 부하는 `mpstat`으로 관찰합니다. Hyperthreading은 각 thread를 별도 CPU로 보이지만 초기 인터럽트 처리 시험에서는 이점이 없었으므로 큐 수를 논리 CPU가 아니라 물리 core 수로 제한하는 것이 권장됩니다.

RSS Configuration
-----------------

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

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


RSS IRQ Configuration
~~~~~~~~~~~~~~~~~~~~~

Each receive queue has a separate IRQ associated with it. The NIC triggers
this to notify a CPU when new packets arrive on the given queue. The
signaling path for PCIe devices uses message signaled interrupts (MSI-X),
that can route each interrupt to a particular CPU. The active mapping
of 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 packet
processing takes place in receive interrupt handling, it is advantageous
to spread receive interrupts between CPUs. To manually adjust the IRQ
affinity of each interrupt see Documentation/core-api/irq/irq-affinity.rst. Some systems
will be running irqbalance, a daemon that dynamically optimizes IRQ
assignments and as a result may override any manual settings.


Suggested Configuration
~~~~~~~~~~~~~~~~~~~~~~~

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

Per-cpu load can be observed using the mpstat utility, but note that on
processors with hyperthreading (HT), each hyperthread is represented as
a separate CPU. For interrupt handling, HT has shown no benefit in
initial tests, so limit the number of queues to the number of CPU cores
in the system.

전용 RSS context와 n-tuple 규칙

현대 NIC는 명시적 match rule로 선택하는 RSS 구성을 여러 개 동시에 둘 수 있습니다. 특정 목적지 포트나 IP 주소 트래픽이 사용할 큐 집합을 제한할 때 유용합니다. 문서 예는 TCP 목적지 포트 22 트래픽을 queue 0과 1로 보냅니다.

`ethtool -X eth0 hfunc toeplitz context new`로 추가 context를 만들면 커널이 ID를 반환합니다. 항상 존재하는 기본 context의 ID는 0입니다. 새 context도 기본 context와 같은 API로 조회하고 수정할 수 있습니다. `ethtool -x eth0 context 1`로 table을 보고 `ethtool -X eth0 equal 2 context 1`로 queue 0과 1에 균등 분배합니다.

새 context를 실제 트래픽에 적용하려면 `ethtool -N eth0 flow-type tcp6 dst-port 22 context 1` 같은 n-tuple filter를 만들고 반환된 rule ID를 보관합니다. 사용이 끝나면 먼저 `ethtool -N eth0 delete 1023`으로 규칙을 지우고 `ethtool -X eth0 context 1 delete`로 context를 제거합니다.

Dedicated RSS contexts
~~~~~~~~~~~~~~~~~~~~~~

Modern NICs support creating multiple co-existing RSS configurations
which are selected based on explicit matching rules. This can be very
useful when application wants to constrain the set of queues receiving
traffic for e.g. a particular destination port or IP address.
The example below shows how to direct all traffic to TCP port 22
to queues 0 and 1.

To create an additional RSS context use::

  # ethtool -X eth0 hfunc toeplitz context new
  New RSS context is 1

Kernel reports back the ID of the allocated context (the default, always
present RSS context has ID of 0). The new context can be queried and
modified using the same APIs as the default context::

  # ethtool -x eth0 context 1
  RX flow hash indirection table for eth0 with 13 RX ring(s):
    0:      0     1     2     3     4     5     6     7
    8:      8     9    10    11    12     0     1     2
  [...]
  # ethtool -X eth0 equal 2 context 1
  # ethtool -x eth0 context 1
  RX flow hash indirection table for eth0 with 13 RX ring(s):
    0:      0     1     0     1     0     1     0     1
    8:      0     1     0     1     0     1     0     1
  [...]

To make use of the new context direct traffic to it using an n-tuple
filter::

  # ethtool -N eth0 flow-type tcp6 dst-port 22 context 1
  Added rule with ID 1023

When done, remove the context and the rule::

  # ethtool -N eth0 delete 1023
  # ethtool -X eth0 context 1 delete

RPS: 소프트웨어 프로토콜 처리 분산

Receive Packet Steering은 RSS의 소프트웨어 구현에 해당하며 데이터 경로에서 더 늦게 실행됩니다. RSS가 하드웨어 큐와 인터럽트 CPU를 고르는 반면 RPS는 인터럽트 처리보다 위의 프로토콜 스택을 실행할 CPU를 고릅니다. 선택한 CPU의 backlog queue에 패킷을 넣고 그 CPU를 깨웁니다.

RPS는 NIC 종류와 무관하게 쓸 수 있고 새 프로토콜용 software hash를 쉽게 추가할 수 있으며 하드웨어 인터럽트 발생률을 늘리지 않습니다. 대신 원격 CPU를 깨우기 위한 IPI가 생깁니다. 드라이버가 bottom half에서 `netif_rx()` 또는 `netif_receive_skb()`로 패킷을 넘기면 `get_rps_cpu()`가 처리 CPU를 선택합니다.

주소와 포트의 2-tuple 또는 4-tuple flow hash를 계산합니다. NIC가 RSS용 Toeplitz hash를 receive descriptor로 제공할 수도 있고 스택이 직접 계산할 수도 있습니다. 결과는 `skb->hash`에 저장되어 이후 스택에서도 같은 flow 식별자로 사용됩니다.

각 하드웨어 Rx queue에는 RPS가 보낼 수 있는 CPU 목록이 있습니다. flow hash를 목록 크기로 나눈 나머지가 index가 되고, 선택된 CPU의 backlog tail에 패킷을 넣습니다. bottom half 마지막에는 패킷을 받은 원격 CPU들로 IPI를 보내 backlog 처리를 깨우며, 그 CPU가 나머지 네트워크 스택을 실행합니다.

RPS에는 `CONFIG_RPS`가 필요하며 SMP에서는 기본 활성화되어 있지만 CPU map을 명시적으로 설정하기 전까지 동작하지 않습니다. queue별 `/sys/class/net/<dev>/queues/rx-<n>/rps_cpus`는 CPU bitmap입니다. 기본값 0은 RPS 비활성으로, 패킷을 인터럽트를 처리한 CPU에서 계속 처리한다는 뜻입니다. bitmap 표기는 IRQ affinity 문서와 같습니다.

단일 큐 장치는 인터럽트 CPU와 같은 memory domain의 CPU들을 `rps_cpus`로 지정하는 것이 일반적입니다. NUMA locality 문제가 없으면 모든 CPU도 가능합니다. 인터럽트 비율이 높다면 이미 일이 많은 인터럽트 CPU를 map에서 빼는 편이 나을 수 있습니다. RSS가 CPU마다 큐 하나를 배치한 멀티큐 장치에서는 RPS가 중복입니다. 큐가 CPU보다 적을 때는 각 queue의 인터럽트 CPU와 memory domain을 공유하는 CPU들로 RPS를 제한하면 도움이 됩니다.

RPS: Receive Packet Steering
============================

Receive Packet Steering (RPS) is logically a software implementation of
RSS. Being in software, it is necessarily called later in the datapath.
Whereas RSS selects the queue and hence CPU that will run the hardware
interrupt handler, RPS selects the CPU to perform protocol processing
above the interrupt handler. This is accomplished by placing the packet
on 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 does
   introduce inter-processor interrupts (IPIs))

RPS is called during bottom half of the receive interrupt handler, when
a driver sends a packet up the network stack with netif_rx() or
netif_receive_skb(). These call the get_rps_cpu() function, which
selects the queue that should process a packet.

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

Each receive hardware queue has an associated list of CPUs to which
RPS may enqueue packets for processing. For each received packet,
an index into the list is computed from the flow hash modulo the size
of 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. At
the end of the bottom half routine, IPIs are sent to any CPUs for which
packets have been queued to their backlog queue. The IPI wakes backlog
processing on the remote CPU, and any queued packets are then processed
up the networking stack.


RPS Configuration
-----------------

RPS requires a kernel compiled with the CONFIG_RPS kconfig symbol (on
by default for SMP). Even when compiled in, RPS remains disabled until
explicitly configured. The list of CPUs to which RPS may forward traffic
can 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 interrupting
CPU. Documentation/core-api/irq/irq-affinity.rst explains how CPUs are assigned to
the bitmap.


Suggested Configuration
~~~~~~~~~~~~~~~~~~~~~~~

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

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

RPS Flow Limit와 큰 flow 억제

RPS는 같은 flow를 한 CPU에 유지해 패킷 재정렬을 막지만 flow별 packet rate가 다르면 CPU 부하가 불균형해집니다. 한 flow가 트래픽 대부분을 차지하는 극단적 상황은 서버 오설정이나 위조 출발지 DoS 공격일 수 있습니다.

Flow Limit은 CPU가 포화에 가까울 때 큰 flow의 패킷을 작은 flow보다 조금 먼저 버리는 선택적 RPS 기능입니다. 대상 CPU input queue가 `net.core.netdev_max_backlog`의 절반을 넘으면 최근 256개 패킷의 flow별 개수를 셉니다. 새 패킷의 flow가 설정 비율, 기본 절반을 넘으면 그 새 패킷을 버립니다. 다른 flow는 queue가 `netdev_max_backlog`에 도달할 때까지 유지됩니다. 절반 임계값 아래에서는 버리지 않으므로 큰 flow의 연결도 완전히 끊지 않습니다.

`CONFIG_NET_FLOW_LIMIT`는 기본 컴파일되지만 기능은 꺼져 있습니다. lock과 cache contention을 피하려고 CPU별로 독립 구현하며 `/proc/sys/net/core/flow_limit_cpu_bitmap`의 bit로 CPU별 활성화를 정합니다. 이 bitmap 문법은 `rps_cpus`와 같습니다.

패킷 hash로 per-flow hashtable bucket을 선택하고 counter를 증가시켜 rate를 계산합니다. RPS CPU 선택과 같은 hash를 사용하지만 bucket 수가 CPU 수보다 훨씬 많아 큰 flow를 더 세밀하게 구분하고 false positive를 줄입니다. 기본 table은 4096 bucket이며 `net.core.flow_limit_table_len`으로 바꿉니다. 이 값은 새 table을 할당할 때만 읽으므로 기존 활성 table은 즉시 바뀌지 않습니다.

동시 연결이 많고 한 연결이 CPU 50%를 차지하면 문제로 간주할 환경에서 유용합니다. `/proc/irq/N/smp_affinity`로 수신 인터럽트를 처리하는 모든 CPU에 켜는 것이 권장됩니다. input queue가 flow limit 임계값 50%와 history 256을 합친 수준을 넘어야 작동하며 실험에서는 `net.core.netdev_max_backlog` 1000 또는 10000이 잘 작동했습니다.

RPS Flow Limit
--------------

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

Flow Limit is an optional RPS feature that prioritizes small flows
during CPU contention by dropping packets from large flows slightly
ahead of those from small flows. It is active only when an RPS or RFS
destination CPU approaches saturation.  Once a CPU's input packet
queue exceeds half the maximum queue length (as set by sysctl
net.core.netdev_max_backlog), the kernel starts a per-flow packet
count over the last 256 packets. If a flow exceeds a set ratio (by
default, half) of these packets when a new packet arrives, then the
new packet is dropped. Packets from other flows are still only
dropped once the input packet queue reaches netdev_max_backlog.
No packets are dropped when the input packet queue length is below
the 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 not
turned on. It is implemented for each CPU independently (to avoid lock
and cache contention) and toggled per CPU by setting the relevant bit
in sysctl net.core.flow_limit_cpu_bitmap. It exposes the same CPU
bitmap 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 hashtable
bucket and incrementing a per-bucket counter. The hash function is
the same that selects a CPU in RPS, but as the number of buckets can
be much larger than the number of CPUs, flow limit has finer-grained
identification of large flows and fewer false positives. The default
table 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. Modifying
it 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 handle
network rx interrupts (as set in /proc/irq/N/smp_affinity).

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

RFS: 응용 프로그램 CPU 지역성

RPS는 hash만으로 CPU를 나눠 부하 분산은 좋지만 데이터를 소비하는 응용 프로그램의 위치를 고려하지 않습니다. Receive Flow Steering은 응용 스레드가 실행되는 CPU로 커널 패킷 처리를 보내 data cache hit rate를 높입니다. 원격 CPU backlog에 넣고 깨우는 동작 자체는 RPS를 그대로 사용합니다.

RFS에서 flow hash는 CPU를 직접 고르지 않고 flow lookup table index로 쓰입니다. 각 entry는 그 flow를 마지막으로 처리한 CPU를 기록합니다. 유효 CPU가 없으면 일반 RPS로 처리합니다. 여러 hash entry가 같은 CPU를 가리킬 수 있고, flow가 많고 CPU가 적으면 한 응용 스레드가 서로 다른 hash의 여러 flow를 처리하는 것이 정상입니다.

전역 `rps_sock_flow_table`은 사용자가 현재 flow를 처리하는 desired CPU를 저장합니다. `inet_recvmsg()`, `inet_sendmsg()`, `tcp_splice_read()`가 실행될 때 CPU index가 갱신됩니다. 장치의 각 하드웨어 Rx queue에는 `rps_dev_flow_table`이 따로 있고, 현재 커널 패킷을 enqueue하는 current CPU와 마지막 enqueue 위치 counter를 저장합니다.

스케줄러가 응용 스레드를 새 CPU로 옮겼지만 기존 CPU backlog에 패킷이 남아 있으면 즉시 CPU를 바꿀 경우 순서가 뒤집힐 수 있습니다. 각 backlog의 head counter는 dequeue할 때 증가하고 tail은 head와 queue length의 합입니다. `rps_dev_flow[i]` counter는 해당 flow에서 현재 CPU에 마지막으로 enqueue한 element 위치를 나타냅니다.

`get_rps_cpu()`는 전역 table의 desired CPU와 queue별 table의 current CPU를 비교합니다. 같으면 그 CPU backlog에 넣습니다. 다르면 현재 CPU의 queue head가 기록된 tail 이상이어서 기존 패킷을 모두 비웠거나, current CPU가 `nr_cpu_ids` 이상으로 미설정이거나, offline일 때만 current CPU를 desired CPU로 바꿉니다. 따라서 이전 CPU에 outstanding packet이 없어야 flow가 새 CPU로 이동하고 순서가 보존됩니다.

RFS는 `CONFIG_RPS`가 필요하고 명시적으로 설정해야 합니다. 전역 entry 수는 `/proc/sys/net/core/rps_sock_flow_entries`, queue별 entry 수는 `/sys/class/net/<dev>/queues/rx-<n>/rps_flow_cnt`로 정합니다. 두 값 모두 설정되어야 해당 queue에서 RFS가 켜지고 가장 가까운 2의 거듭제곱으로 올림됩니다.

권장 크기는 열린 연결 수가 아니라 동시에 활성인 연결 수를 기준으로 합니다. 중간 부하 서버에서는 `rps_sock_flow_entries=32768`이 잘 작동했습니다. 단일 큐는 `rps_flow_cnt`도 같은 값으로 두고, N개 멀티큐는 각 queue에 전역 값/N을 배분할 수 있습니다. 예를 들어 32768과 16개 queue라면 queue당 2048입니다.

RFS: Receive Flow Steering
==========================

While RPS steers packets solely based on hash, and thus generally
provides good load distribution, it does not take into account
application locality. This is accomplished by Receive Flow Steering
(RFS). The goal of RFS is to increase datacache hitrate by steering
kernel processing of packets to the CPU where the application thread
consuming the packet is running. RFS relies on the same RPS mechanisms
to enqueue packets onto the backlog of another CPU and to wake up that
CPU.

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 maps
flows 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 entry
are steered using plain RPS. Multiple table entries may point to the
same CPU. Indeed, with many flows and few CPUs, it is very likely that
a single application thread handles flows with many different flow hashes.

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

When the scheduler moves a thread to a new CPU while it has outstanding
receive packets on the old CPU, packets may arrive out of order. To
avoid this, RFS uses a second flow table to track outstanding packets
for each flow: rps_dev_flow_table is a table specific to each hardware
receive queue of each device. Each table value stores a CPU index and a
counter. The CPU index represents the *current* CPU onto which packets
for this flow are enqueued for further kernel processing. Ideally, kernel
and userspace processing occur on the same CPU, and hence the CPU index
in both tables is identical. This is likely false if the scheduler has
recently migrated a userspace thread while the kernel still has packets
enqueued for kernel processing on the old CPU.

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

And now the trick for avoiding out of order packets: when selecting the
CPU for packet processing (from get_rps_cpu()) the rps_sock_flow table
and the rps_dev_flow table of the queue that the packet was received on
are compared. If the desired CPU for the flow (found in the
rps_sock_flow table) matches the current CPU (found in the rps_dev_flow
table), 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 the
following is true:

  - The current CPU's queue head counter >= the recorded tail counter
    value 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) current
CPU. These rules aim to ensure that a flow only moves to a new CPU when
there are no packets outstanding on the old CPU, as the outstanding
packets could arrive later than those about to be processed on the new
CPU.


RFS Configuration
-----------------

RFS is only available if the kconfig symbol CONFIG_RPS is enabled (on
by default for SMP). The functionality remains disabled until explicitly
configured. 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. The
suggested flow count depends on the expected number of active connections
at any given time, which may be significantly less than the number of open
connections. We have found that a value of 32768 for rps_sock_flow_entries
works fairly well on a moderately loaded server.

For a single queue device, the rps_flow_cnt value for the single queue
would 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 be
configured as rps_sock_flow_entries / N, where N is the number of
queues. So for instance, if rps_sock_flow_entries is set to 32768 and there
are 16 configured receive queues, rps_flow_cnt for each queue might be
configured as 2048.

Accelerated RFS: NIC flow steering

Accelerated RFS와 RFS의 관계는 RSS와 RPS의 관계와 같습니다. 응용 프로그램이 flow를 소비하는 CPU를 soft state로 추적하되 패킷을 그 CPU 또는 cache hierarchy상 가까운 CPU의 하드웨어 queue로 직접 보내므로 일반 RFS보다 나은 성능을 기대합니다.

`rps_dev_flow_table` entry가 바뀔 때 네트워크 스택은 드라이버의 `ndo_rx_flow_steer`를 호출해 flow에 원하는 하드웨어 queue를 알립니다. 드라이버는 장치별 방법으로 NIC filter를 프로그래밍합니다.

flow의 하드웨어 queue는 `rps_dev_flow_table`에 기록된 CPU에서 유도합니다. 드라이버가 관리하는 CPU-to-hardware-queue map은 `/proc/interrupts`의 IRQ affinity table을 뒤집어 자동 생성한 것입니다. 드라이버가 `cpu_rmap` 커널 라이브러리로 직접 채우거나 `netif_enable_cpu_rmap()`으로 커널에 관리를 맡길 수 있습니다. 각 CPU에는 처리 CPU가 cache locality상 가장 가까운 queue를 연결합니다.

사용 조건은 `CONFIG_RFS_ACCEL`, NIC와 드라이버 지원, `ethtool` ntuple filtering 활성화입니다. CPU·queue map은 각 Rx queue의 IRQ affinity에서 자동 유도되므로 일반적으로 추가 설정은 없습니다. RFS를 사용하려는 시스템에서 NIC가 하드웨어 가속을 지원하면 accelerated RFS를 켜는 것이 권장됩니다.

Accelerated RFS
===============

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

To enable accelerated RFS, the networking stack calls the
ndo_rx_flow_steer driver function to communicate the desired hardware
queue for packets matching a particular flow. The network stack
automatically calls this function every time a flow entry in
rps_dev_flow_table is updated. The driver in turn uses a device specific
method to program the NIC to steer the packets.

The hardware queue for a flow is derived from the CPU recorded in
rps_dev_flow_table. The stack consults a CPU to hardware queue map which
is maintained by the NIC driver. This is an auto-generated reverse map of
the IRQ affinity table shown by /proc/interrupts. Drivers can use
functions in the cpu_rmap (“CPU affinity reverse map”) kernel library
to populate the map. Alternatively, drivers can delegate the cpu_rmap
management to the Kernel by calling netif_enable_cpu_rmap(). For each CPU,
the corresponding queue in the map is set to be one whose processing CPU is
closest in cache locality.


Accelerated RFS Configuration
-----------------------------

Accelerated RFS is only available if the kernel is compiled with
CONFIG_RFS_ACCEL and support is provided by the NIC device and driver.
It also requires that ntuple filtering is enabled via ethtool. The map
of CPU to queues is automatically deduced from the IRQ affinities
configured for each receive queue by the driver, so no additional
configuration should be necessary.


Suggested Configuration
~~~~~~~~~~~~~~~~~~~~~~~

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

XPS: 송신 큐 선택

Transmit Packet Steering은 멀티큐 장치에서 패킷에 사용할 Tx queue를 지능적으로 고릅니다. 두 종류 map을 사용할 수 있습니다. CPU-to-hardware-queue map은 특정 CPU 집합에 queue를 전용 배치해 device queue lock contention을 줄이고, Tx completion에서 `sk_buff` 같은 data cache line의 miss를 줄입니다. CPU마다 queue 하나면 lock contention을 완전히 없앨 수도 있습니다.

Rx-queue-to-Tx-queue map은 관리자가 정한 수신·송신 queue 연관 관계를 사용합니다. many-to-many도 가능하지만 보통 1:1입니다. CPU에 고정하지 않은 여러 application thread가 각자 한 Rx queue를 busy polling할 때 유용합니다. 연결 socket에 Rx queue 번호를 cache하고 대응 Tx queue로 송신하면 같은 queue association에서 completion을 처리하여 다른 CPU 인터럽트를 피하고, busy poll thread가 completion까지 정리해 지연을 줄일 수 있습니다.

XPS는 Tx queue마다 그 큐를 사용할 CPU 또는 Rx queue bitmap을 설정합니다. 장치는 그 역방향 map을 계산해 유지합니다. flow의 첫 패킷에서 `get_xps_queue()`는 socket에 저장된 Rx queue ID를 Rx-to-Tx table에서 먼저 맞추거나, 실행 CPU ID를 CPU-to-queue table의 key로 사용합니다. 후보가 하나면 그대로 쓰고 여러 개면 flow hash로 후보 집합의 index를 고릅니다. Rx map을 쓸 때는 data path의 비싼 lookup을 피하려고 수신 장치와 송신 장치가 같은지 검증하지 않습니다.

선택한 Tx queue는 TCP 연결 같은 flow socket 구조에 저장해 이후 패킷에도 사용합니다. 이 방식은 out-of-order를 막고 queue 선택 비용을 flow 전체에 분산합니다. 이후 queue 변경은 `skb->ooo_okay`가 설정된 패킷에서만 가능합니다. 이 flag는 outstanding packet이 없어 queue를 바꿔도 순서 문제가 없음을 뜻하며 transport layer가 설정합니다. TCP는 연결의 모든 데이터가 ACK된 때 설정합니다.

XPS는 `CONFIG_XPS`가 필요하며 SMP에서 기본입니다. 초기 구성 여부와 방식은 드라이버에 달려 있습니다. CPU map은 `/sys/class/net/<dev>/queues/tx-<n>/xps_cpus`, Rx queue map은 `/sys/class/net/<dev>/queues/tx-<n>/xps_rxqs`에서 조회하고 설정합니다.

Tx queue가 하나면 선택지가 없어 XPS 효과가 없습니다. 멀티큐에서는 각 CPU가 queue 하나에 대응하는 것이 좋고 CPU 수와 queue 수가 같으면 완전한 전용 쌍을 만들 수 있습니다. queue가 더 적으면 Tx completion CPU와 cache를 공유하는 CPU들이 같은 queue를 쓰는 편이 좋습니다. Rx queue 기반 선택은 map을 명시적으로 설정해야 하며 적용 가능한 Rx map이 없으면 CPU map으로 fallback합니다.

XPS: Transmit Packet Steering
=============================

Transmit Packet Steering is a mechanism for intelligently selecting
which transmit queue to use when transmitting a packet on a multi-queue
device. This can be accomplished by recording two kinds of maps, either
a 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 queues
exclusively to a subset of CPUs, where the transmit completions for
these queues are processed on a CPU within this set. This choice
provides two benefits. First, contention on the device queue lock is
significantly reduced since fewer CPUs contend for the same queue
(contention can be eliminated completely if each CPU has its own
transmit queue). Secondly, cache miss rate on transmit completion is
reduced, in particular for data cache lines that hold the sk_buff
structures.

2. XPS using receive queues map

This mapping is used to pick transmit queue based on the receive
queue(s) map configuration set by the administrator. A set of receive
queues can be mapped to a set of transmit queues (many:many), although
the common use case is a 1:1 mapping. This will enable sending packets
on the same queue associations for transmit and receive. This is useful for
busy polling multi-threaded workloads where there are challenges in
associating a given CPU to a given application thread. The application
threads are not pinned to CPUs and each thread handles packets
received on a single queue. The receive queue number is cached in the
socket for the connection. In this model, sending the packets on the same
transmit queue corresponding to the associated receive queue has benefits
in keeping the CPU overhead low. Transmit completion work is locked into
the same queue-association that a given application is polling on. This
avoids the overhead of triggering an interrupt on another CPU. When the
application cleans up the packets during the busy poll, transmit completion
may be processed along with it in the same thread context and so result in
reduced latency.

XPS is configured per transmit queue by setting a bitmap of
CPUs/receive-queues that may use that queue to transmit. The reverse
mapping, from CPUs to transmit queues or from receive-queues to transmit
queues, is computed and maintained for each network device. When
transmitting the first packet in a flow, the function get_xps_queue() is
called to select a queue. This function uses the ID of the receive queue
for the socket connection for a match in the receive queue-to-transmit queue
lookup table. Alternatively, this function can also use the ID of the
running CPU as a key into the CPU-to-queue lookup table. If the
ID matches a single queue, that is used for transmission. If multiple
queues match, one is selected by using the flow hash to compute an index
into the set. When selecting the transmit queue based on receive queue(s)
map, the transmit device is not validated against the receive device as it
requires expensive lookup operation in the datapath.

The queue chosen for transmitting a particular flow is saved in the
corresponding socket structure for the flow (e.g. a TCP connection).
This transmit queue is used for subsequent packets sent on the flow to
prevent out of order (ooo) packets. The choice also amortizes the cost
of calling get_xps_queues() over all packets in the flow. To avoid
ooo packets, the queue for a flow can subsequently only be changed if
skb->ooo_okay is set for a packet in the flow. This flag indicates that
there are no outstanding packets in the flow, so the transmit queue can
change without the risk of generating out of order packets. The
transport layer is responsible for setting ooo_okay appropriately. TCP,
for instance, sets the flag when all data for a connection has been
acknowledged.

XPS Configuration
-----------------

XPS is only available if the kconfig symbol CONFIG_XPS is enabled (on by
default for SMP). If compiled in, it is driver dependent whether, and
how, XPS is configured at device init. The mapping of CPUs/receive-queues
to transmit queue can be inspected and configured using sysfs:

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 configuration
has no effect, since there is no choice in this case. In a multi-queue
system, 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 each
queue can also map onto one CPU, resulting in exclusive pairings that
experience no contention. If there are fewer queues than CPUs, then the
best CPUs to share a given queue are probably those that share the cache
with the CPU that processes transmit completions for that queue
(transmit interrupts).

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

Tx queue별 하드웨어 rate limit

Tx queue별 rate limit은 하드웨어가 구현합니다. 현재 지원하는 속성은 최대 rate이며 `/sys/class/net/<dev>/queues/tx-<n>/tx_maxrate`에 Mbps 값을 씁니다. 0은 제한 비활성이고 기본값입니다.

Per TX Queue rate limitation
============================

These are rate-limitation mechanisms implemented by HW, where currently
a 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.

도입 버전과 저자

RPS와 RFS는 Linux 2.6.35에 도입되었고 XPS는 2.6.38에 포함되었습니다. 원래 patch는 Tom Herbert가 제출했습니다. Accelerated RFS도 2.6.35에 도입되었으며 원래 patch는 Ben Hutchings가 제출했습니다. 문서 저자는 Tom Herbert와 Willem de Bruijn입니다.

Further Information
===================
RPS and RFS were introduced in kernel 2.6.35. XPS was incorporated into
2.6.38. Original patches were submitted by Tom Herbert
(therbert@google.com)

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

Authors:

- Tom Herbert (therbert@google.com)
- Willem de Bruijn (willemb@google.com)