\documentclass[aspectratio=43,obeyspaces,spaces,hyphens,dvipsnames]{beamer}
\usepackage[utf8x]{inputenc}
\usepackage{lmodern}% http://ctan.org/pkg/lm
\usepackage{minted}
\usepackage{hyperref}
\usepackage{xcolor}
\usepackage{pgfplots}
\usepackage{tikz}
\usepackage[normalem]{ulem}
\usepackage{textcomp}

\usepackage{multimedia}

\mode<presentation>
\usetheme{Bootlin}

\def\signed #1{{\leavevmode\unskip\nobreak\hfil\penalty50\hskip2em
  \hbox{}\nobreak\hfil(#1)
  \parfillskip=0pt \finalhyphendemerits=0 \endgraf}}

\newsavebox\mybox
\newenvironment{aquote}[1]
  {\savebox\mybox{#1}\begin{quotation}}
  {\signed{\usebox\mybox}\end{quotation}}

\title{Network Performance in the Linux Kernel}
\conference{Fosdem, February 2021}
\authors{Maxime Chevallier}
\email{{\tiny maxime.chevallier@bootlin.com}}
\institute{Bootlin}
\slidesurl{https://bootlin.com/pub/conferences/2021}

\begin{document}

\addtocontents{toc}{\protect\setcounter{tocdepth}{-1}}
\section{Network Performance in the Linux Kernel}
\addtocontents{toc}{\protect\setcounter{tocdepth}{2}}

\begin{frame}{Maxime Chevallier}
  \begin{itemize}
    \item Linux kernel engineer at Bootlin.
      \begin{itemize}
        \item Linux kernel and driver development, system integration,
          boot time optimization, consulting\dots
        \item Embedded Linux, Linux driver development, Yocto Project
          \& OpenEmbedded and Buildroot training, with materials
          freely available under a Creative Commons license.
        \item \url{https://bootlin.com}
      \end{itemize}
    \item Contributions:
      \begin{itemize}
        \item Worked on network (MAC, PHY, switch) engines.
        \item Contributed to the Marvell EBU SoCs upstream support.
        \item Worked on Rockchip's Camera interface and Techwell's TW9900 decoder.
      \end{itemize}
  \end{itemize}
\end{frame}

% Plan
% Presentation HW
% Presentation trajet paquet
% - HW
%  - PHY
%  - DMA
%  - Queueing
% - SW
%  - IRQ
%  - NAPI
%  - TC
%  - Unpacking
%  - Userspace
% - RPS
% - RSS
% - RFS
% - aRFS
% - XPS
% - MQPrio
% - XDP
% - Other offloading
%  - Checksum offloading
%  - Filtering (vlan + mac)

\begin{frame}{Preamble - goals}
  \begin{itemize}
    \item Follow the path of packets through the Hardware and Software stack
    \item Understand the features of modern NICs
    \item Discover what the Linux Kernel implements to gain performances
    \item Go through the various offloadings available
  \end{itemize}
\end{frame}

\section{The path of a packet}

\begin{frame}{The Hardware}
	\includegraphics[width=\textwidth]{graphics/link_overview.pdf}
	\begin{itemize}
		\item Link Partner : The other side of the cable
		\item Connector : 8P8C (RJ45), SFP, etc.
		\item Media : Copper, Fiber, Radio
		\item PHY : Converts media-dependent signals into standard data
	\end{itemize}
\end{frame}

\begin{frame}{The NIC}
	\begin{itemize}
		\item \textbf{N}etwork \textbf{I}nterface \textbf{C}ontroller
		\item Sometimes embed a PHY (PCIe networking card)
		\item The MAC : Handles L2 protocol, transfers data to the CPU
	\end{itemize}
\end{frame}

\begin{frame}{Frame reception}
	\includegraphics[width=0.8\textwidth]{graphics/Rx.pdf}
	\begin{itemize}
		\item The \code{MAC} received data and writes it to RAM using \code{DMA}
		\item A descriptor is created
		\item Its address is put in a queue
	\end{itemize}
\end{frame}

\begin{frame}{Frame reception - IRQ}
	\begin{center}
	\includegraphics[width=0.6\textwidth]{graphics/Rx_irq.pdf}
	\end{center}
	\begin{itemize}
		\item An interrupt is fired
		\item One CPU core will handle the interrupt
	\end{itemize}
\end{frame}

\begin{frame}{Frame reception - Unqueue}
	\begin{center}
	\includegraphics[width=0.7\textwidth]{graphics/Rx_unqueue.pdf}
	\end{center}
	\begin{itemize}
		\item The Interrupt handler acknowledges the interrupt
		\item The packet is processed in \code{softirq} context
		\item The next frame can be received in parallel
	\end{itemize}
\end{frame}

\begin{frame}{In the NIC driver}
	\begin{itemize}
		\item The CPU : Processes L3 (\code{packets}) and above, up to the application
		\item The Interrupt Handler does very basic work, and masks interrupts
		\item \code{NAPI} is used to schedule the processing in batches
		\item Subsequent frames are also dequeued
		\item \code{NAPI} stops dequeueing once :
			\begin{itemize}
				\item The budget is expired (release the CPU to the scheduler)
				\item The queue is empty
			\end{itemize}
		\item \code{NAPI} re-enables interrupts
			\begin{itemize}
				\item This avoids having one interrupt per frame
			\end{itemize}
	\end{itemize}
\end{frame}

\begin{frame}{In the kernel networking stack}
	\begin{itemize}
		\item The PCAP hook is called, then the TC hook
		\item The header in unpacked, to decide if :
			\begin{itemize}
				\item The packet is forwarded
				\item The packet is dropped
				\item The packed is passed to a socket
			\end{itemize}
		\item The in-kernel data path is heavily optimized...
		\item ...But still requires some processing power at very high speeds
	\end{itemize}
\end{frame}

\section{Traffic Spreading and Steering}

\begin{frame}{Scaling across queues and CPUs}

	\begin{columns}
	\begin{column}{0.50\linewidth}
	\begin{itemize}
		\item Most modern systems have multi-core CPUs
		\item Modern NICs have multiple RX/TX queues (\code{rxq}/\code{txq})
		\item Interrupted CPU does all the packet processing
			\begin{itemize}
				\item If the interrupt always goes to the same core...
				\item ...the other ones will stay unused
			\end{itemize}
	\end{itemize}
	\end{column}
	\begin{column}{0.50\linewidth}
		\includegraphics[width=\textwidth]{graphics/RPS_unqueue.pdf}
	\end{column}
	\end{columns}

	\small{Hardware and Software techniques exists to scale processing across CPUs}
\end{frame}

\begin{frame}{Scaling}
	\begin{center}
	Goal : Spread packet across CPU cores
	\end{center}
	\begin{itemize}
		\item We can't randomly assign packets to CPUs
		\item Ordering must be preserved
		\item Memory domains should be taken into account (L1/L2 caches, NUMA nodes)
		\item We need to spread packets per-flow
	\end{itemize}
	\vspace{1cm}
	
	\small{Kernel documentation : \code{Documentation/networking/scaling.rst}}
\end{frame}

\begin{frame}{N-tuple Flows}

	\begin{center}
		 \textbf{Flow} : Packets from the same emitter, for the same consumer
	\end{center}
	\begin{itemize}
		\item Flows are identified by data extracted from the headers
		\item L3 flow : Source and Destination IP addresses $\rightarrow$ 2-tuple
		\item L4 flow : src/dst IP + Proto + src/dst ports $\rightarrow$ 5-tuple
	\end{itemize}
	\begin{columns}
		\begin{column}{0.50\linewidth}
		\includegraphics[width=\textwidth]{graphics/2-tuple.pdf}
			\center{\small{2-tuple}}
		\end{column}
		\begin{column}{0.50\linewidth}
		\includegraphics[width=\textwidth]{graphics/5-tuple.pdf}
			\center{\small{5-tuple}}
		\end{column}
	\end{columns}
\end{frame}

\begin{frame}{N-tuple Flows}
	\begin{itemize}
		\item Other flows can be interesting :
			\begin{itemize}
				\item Vlan-based flows
				\item Destination MAC-based flows
			\end{itemize}
		\item Most often, these tuples are hashed prior to being used
		\item Allows to build smaller flow tables
		\item Advanced NICs are able to keep track of a high number of flows
	\end{itemize}
	\includegraphics[width=\textwidth]{graphics/Hash.pdf}
\end{frame}

\begin{frame}{RPS : Receive Packet Steering}
	\begin{center}
	\includegraphics[width=0.4\textwidth]{graphics/RPS_spread.pdf}
	\end{center}
	\vspace{-0.5cm}
	\begin{itemize}
		\item The interrupted CPU schedules processing on other CPUs
		\item Key data is extracted from the Headers and hashed
			\begin{itemize}
				\item The Hash can be computed by the hardware
				\item It is then passed in the descriptor
			\end{itemize}
		\item The CPU is chosen by masking out the first bits of the hash
	\end{itemize}
\end{frame}

\begin{frame}{Using RPS}
	\begin{itemize}
		\item Kernel needs to be built with \code{CONFIG_RPS}
		\item The set of CPUs used depends on the \code{rxq} the frame arrives on
		\item {\small \code{echo 0x03 > /sys/class/net/eth0/queues/rx-0/rps_cpus}}
		\item {\small \code{echo 0x0c > /sys/class/net/eth0/queues/rx-1/rps_cpus}}
			\begin{itemize}
				\item $\rightarrow$ Traffic from rxq 0 is spread on CPUs 0 and 1
				\item $\rightarrow$ Traffic from rxq 1 is spread on CPUs 2 and 3
			\end{itemize}
		\item Very useful for NICs with fewer \code{rxqs} than CPU cores !
	\end{itemize}
\end{frame}

\begin{frame}{RSS : Receive Side Scaling}
	\begin{center}
	\includegraphics[width=0.4\textwidth]{graphics/RSS_spread.pdf}
	\end{center}
	\vspace{-0.5cm}
	\begin{itemize}
		\item Offloaded version of RPS
		\item The NIC is configured to extract the header data and compute the Hash
		\item The CPU is chosen by means of an Indirection Table
		\item The NIC actually enqueues the packet into one of its queues
		\item The interrupt directly comes to the correct CPU !
	\end{itemize}
\end{frame}

\begin{frame}[fragile]{RSS Tables}
	\begin{itemize}
		\item Tables within the \code{NIC}
		\item Associates hashes to queues
		\item Tables commonly have more entries than queues
		\begin{itemize}
			\item e.g. 128 entries for 4 queues
		\end{itemize}
		\item Filling the table allows affecting weights to each queue
	\end{itemize}
	\begin{block}{}
	\code{   0x00:      0     0     0     0     0     0     0     0}\\
	\code{   0x08:      0     0     0     0     0     0     0     0}\\
	\code{   0x10:      1     1     1     1     1     1     1     1}\\
	\code{   0x18:      2     2     2     2     3     3     3     3}
	\end{block}
	\begin{itemize}
		\item \code{rxq} 0 has weight 4
		\item \code{rxq} 1 has weight 2
		\item \code{rxq} 2 and 3 have weight 1
	\end{itemize}
\end{frame}

\begin{frame}{Using RSS}
	\begin{itemize}
		\item RSS is configured through ethtool
		\item Enabling RSS : \code{ethtool -K eth0 rx-hashing on}
		\item Configuring the indirection table : \code{ethtool -X eth0 weight 1 2 2 1}
		\item Dumping the indirection table : \code{ethtool -x eth0}
		\item Configuring the hashed fields : \code{ethtool -N eth0 rx-flow-hash tcp4 sdfn}
			\begin{itemize}
				\item see man ethtool(8) for the meaning of each flow type
			\end{itemize}
	\end{itemize}
	\begin{block}{}
	\begin{small}
	\code{ethtool -X eth0 equal 4 } \\
	\code{ethtool -N eth0 rx-flow-hash tcp4 sdfn} \\
	\code{ethtool -N eth0 rx-flow-hash udp4 sdfn} \\
	\code{ethtool -K eth0 rx-hashing on} \\
	$\rightarrow$ Increased IP forwarding speed by a factor of 3 on the MacchiatoBin
	\end{small}
	\end{block}
\end{frame}

\begin{frame}{RFS : Receive Flow Steering}
	\begin{itemize}
		\item \code{RPS} and \code{RSS} don't care about who consumes which flow
		\item This might be bad for cache locality
			\begin{itemize}
				\item What if RPS/RSS sends a flow to CPU 1...
				\item ...but the consumer process lives on CPU 2 ?
			\end{itemize}
		\item \code{RFS} tracks the flows and their consumers
		\item Internally keeps a table associating flows to consumers/CPUs
		\item Updates indirection for a flow when the consumer migrates
	\end{itemize}
	\begin{block}{}
	\begin{small}
		\begin{enumerate}
			\item \code{httpd} lives on CPU 0
			\item \code{RFS} steers TCP traffic to port 80 onto CPU 0
			\item \code{httpd} is migrated to CPU 1
			\item \code{RFS} updates the flow table
			\item TCP to port 80 traffic now goes to CPU 1 !
		\end{enumerate}
	\end{small}
	\end{block}
\end{frame}

\begin{frame}{Using RFS}
	\begin{itemize}
		\item Internally, a \textbf{flow table} associates flow hashes to CPUs
		\item User indicates the size of the table
		\item {\footnotesize \code{echo 32768 > /proc/sys/net/core/rps_sock_flow_entries}}
		\item {\footnotesize \code{echo 4096 > /sys/class/net/eth0/queues/rx-0/rps_flow_cnt}}
		\item {\footnotesize \code{echo 4096 > /sys/class/net/eth0/queues/rx-1/rps_flow_cnt}}
		\item {\footnotesize \code{...}}
		\item We configure $(32768 / N(rxqs)) $ in each queue
		\item These values are recommended in the Kernel Documentation
	\end{itemize}
\end{frame}

\begin{frame}{aRFS : Accelerated Receive Flow Steering}
	\begin{itemize}
		\item Advanced NICs can steer packets to \code{rxqs} in Hardware
		\item \code{aRFS} asks the driver to configure steering rules for each flow
		\item Rules are updated upon migration of the consumer
			\begin{itemize}
				\item Packets always come to the right CPU !
				\item Kernel handles outstanding packets upon migration
			\end{itemize}
		\item Needs support in HW, and a specific implementation in the driver
		\item The driver determines how to build the steering rule (n-tuple)
	\end{itemize}
\end{frame}

\begin{frame}{Using aRFS}
	\begin{itemize}
		\item Kernel needs to be built with \code{CONFIG_RFS_ACCEL}
		\item Enable N-tuple filtering offloading : \code{ethtool -K eth0 ntuple on}
		\item The \code{NIC} and the driver needs to support aRFS
	\end{itemize}
\end{frame}

\begin{frame}{Flow Steering : Ethtool and TC flower}
	\begin{itemize}
		\item Manually steering flows can be interesting for proper resource assignment
		\item This is also helpful to dedicate queues to flows, e.g. \code{AF_XDP}
		\item Two interfaces exists : \code{tc flower} and \code{ethtool}
		\begin{itemize}
			\item Internally, both \code{ethtool} and \code{tc} interfaces are being merged...
			\item ... But for now the 2 methods coexist and can conflict
		\end{itemize}
		\item We insert \textbf{steering rules} in the \code{NIC}, with priorities
		\item Rules associate :
			\begin{itemize}
				\item Flow types : \code{TCP4}, \code{UDP6}, \code{IP4}, \code{ether}, etc.
				\item Filters : \code{src-ip}, \code{proto}, \code{vlan}, \code{dst-port}, etc.
				\item Actions : Target \code{rxq}, drop, \code{RSS context}
				\item Location : Priority of the rule
			\end{itemize}
	\end{itemize}
\end{frame}

\begin{frame}{Using tc flower and ethtool rxnfc}
	
	\center{\textbf{ethtool examples}}
	\begin{itemize}
		\item {\footnotesize \code{ethtool -K eth0 ntuple on}}
		\item {\footnotesize \code{ethtool -N eth0 flow-type udp4 dst-port 1234 action 2 loc 0}}
			\begin{itemize}
				\item Steer IPv4 UDP traffic for port 1234 to rxq 2
			\end{itemize}
		\item {\footnotesize \code{ethtool -N eth0 flow-type udp4 action -1 loc 1}}
			\begin{itemize}
				\item Drop all UDP IPv4 traffic (except for port 1234)
			\end{itemize}
	\end{itemize}
	\center{\textbf{TC flower example}}
	\begin{itemize}
		\item {\footnotesize \code{ethtool -K eth0 hw-tc-offload on}}
		\item {\footnotesize \code{tc qdisc add dev eth0 ingress}}
		\item {\footnotesize \code{tc flower protocol ip parent ffff: flower ip_proto tcp \ }} \\
		      {\footnotesize \code{dst_port 80 action drop}}
			\begin{itemize}
				\item Drop all IPv4 TCP traffic for port 80
			\end{itemize}
		\item \code{tc flower} falls back to software filtering if needed
	\end{itemize}
\end{frame}

\begin{frame}{RSS contexts}
	\begin{itemize}
		\item Flows can also be steered to multiple queues at once
		\item RSS is then used to spread traffic accross queues
		\item This is achieved through RSS contexts
		\item An RSS context is simply an indirection table
		\item An RSS context is created with ethtool :
			\begin{itemize}
				\item \code{ethtool -X eth0 equal 4 context new}
			\end{itemize}
		\item The RSS context is uses as a destination for the flow :
			{\footnotesize \code{ethtool -N eth0 flow-type udp4 dst-port 1234 context 1 loc 0}}
	\end{itemize}
\end{frame}

\begin{frame}{XPS : Transmit Packet Steering}
	\begin{itemize}
		\item Upon transmitting packets, the driver executes \textbf{completion} code
		\item Transmitting using a single CPU can also lead to cache misses
		\item \code{XPS} is used to select which \code{txq} to use for packet sending
		\item We can assign \code{txqs} to \textbf{CPUs}
			\begin{itemize}
				\item The \code{txq} is chosen according to the CPU the sender lives on
			\end{itemize}
		\item We can also assign \code{txqs} to \textbf{rxqs}
			\begin{itemize}
				\item Make sure that we use the same CPU for RX and TX
			\end{itemize}
		\item The \code{NIC} driver assigns \code{txqs} to CPUs
	\end{itemize}
\end{frame}

\begin{frame}{Using XPS}
	\begin{itemize}
		\item Per-CPU mapping :
			\begin{itemize}
				\item {\footnotesize \code{echo 0x01 > /sys/class/net/eth0/queues/tx-0/xps_cpus}}
				\item {\footnotesize \code{echo 0x02 > /sys/class/net/eth0/queues/tx-1/xps_cpus}}
				\item Assign \code{txq} 0 to CPU 0
				\item Assign \code{txq} 1 to CPU 1
			\end{itemize}
		\item Per-rxq mapping :
			\begin{itemize}
				\item {\footnotesize \code{echo 0x01 > /sys/class/net/eth0/queues/tx-0/xps_rxqs}}
				\item {\footnotesize \code{echo 0x02 > /sys/class/net/eth0/queues/tx-1/xps_rxqs}}
				\item Assign \code{txq} 0 to \code{rxq} 0
				\item Assign \code{txq} 1 to \code{rxq} 1
			\end{itemize}
	\end{itemize}
\end{frame}

\section{Other offloading}

\begin{frame}{Checksumming}
	\begin{itemize}
		\item IPv4 and IPv6 include a checksum in the header
		\item NICs can compute checksums on the fly in TX mode
		\item The Kernel leaves the checksum fields empty
		\item tcpdump will show egress packets with a wrong checksum !!
	\end{itemize}
\end{frame}

\begin{frame}{Filtering}
	\begin{itemize}
		\item Some NICs are capable of early dropping and filtering
		\item Frames are dropped by the NIC, no interrupt is ever fired
		\item MAC filtering :
			\begin{itemize}
				\item Drop frames with an unknown MAC address
				\item The NIC keeps information about multicast domains
				\item The NIC must also keep an updated list of unicast addresses
				\item \code{MAC Vlans} allows attaching multiple addresses to one NIC
			\end{itemize}
		\item VLAN filtering :
			\begin{itemize}
				\item Drop frames for unknown VLANs
				\item The NIC keeps track of VLANs attached to the interface
				\item \code{ethtool -K eth0 rx-vlan-filter on}
			\end{itemize}
	\end{itemize}
\end{frame}

\begin{frame}{Data insertion and segmentation}
	\begin{itemize}
		\item Some NICs can also insert the VLAN tag on the fly
		\item \code{ethtool -K eth0 txvlan on}
			\begin{itemize}
				\item The NIC will insert the VLAN Tag automatically
			\end{itemize}
		\item \code{ethtool -K eth0 rxvlan on}
			\begin{itemize}
				\item The NIC will strip the VLAN tag
				\item The VLAN tag will be in the descriptor
			\end{itemize}
		\item Some NICs can also deal with packet segmentation
		\item \code{ethtool -K eth0 tso on}
		\begin{itemize}
			\item Offload TCP segmentation, the \code{NIC} will generate segments
		\end{itemize}
		\item \code{ethtool -K eth0 ufo on}
		\begin{itemize}
			\item Offload UDP frafgentation, the \code{NIC} will generate fragments
		\end{itemize}
	\end{itemize}
\end{frame}

\section{XDP}

\begin{frame}{Principle}
	\begin{itemize}
		\item Execute a BPF program from within the NIC driver
		\item Executed as early as possible, for fast decision making
		\item Can be used to \code{Pass}, \code{Drop} or \code{Redirect} frames
		\item Also used for fine-grained statistics
	\end{itemize}
	\center{\textbf{BPF}}
	\begin{itemize}
		\item Berkley Packet Filter 
		\item Programming language that can be formally verified
		\item Designed to write filtering rules
		\item Lots of hooks in the Networking Stack, XDP being the earliest
	\end{itemize}
\end{frame}

\begin{frame}{AF\_XDP}
	\begin{itemize}
		\item Uses a combination of \code{XDP} and flow steering
		\item Response to \code{DPDK} : Userspace does the full packet processing
		\item Allows for heavily optimized and customized processing
		\item Special sockets that will directly receive raw buffers
		\item Thanks to \code{XDP}, we can select only part of the traffic for \code{AF_XDP}
		\item The kernel stack is therefor not entirely bypassed...
		\item ...and this is a fully upstream solution !
	\end{itemize}
\end{frame}

\begin{frame}{Documentation and sources}
	\begin{itemize}
		\item In the Kernel source code : \url{Documentation/networking/scaling.rst}
		\item RedHat tuning guide: \url{https://access.redhat.com/documentation/en-us/red_hat_enterprise_linux/6/html/performance_tuning_guide/main-network}
	\end{itemize}
\end{frame}

\begin{frame}{That's it}
	\center{\huge{Thank you !}}
\end{frame}

\end{document}
