XV6 中文文档

Appearance

6.1810 2024 第20讲：网络

主题

  • 数据包格式的分层
  • 内核软件栈的分层
  • 过载行为 —— 今天的论文

我们为什么关心软件如何处理网络流量？

  • 软件栈 —— 以及 linux —— 被广泛用于数据包处理
  • 低端路由器、防火墙、VPN
  • 服务：DNS、web
  • 性能、设计、过载行为是热门话题

论文的场景：

  • [3接口路由器, 两个局域网, 主机, 互联网]

以太网数据包格式

  • [kernel/net.h, struct eth]
  • (用于同步的前导码位，例如 10101010)
  • (起始符，例如 10101011)
  • 目的以太网地址 -- 48 位
  • 源以太网地址 -- 48 位
  • 以太类型 -- 16 位
  • 负载
  • (CRC-32)
  • (结束符；例如 8b/10b 或曼彻斯特编码)

[tcpdump -t -xx -n | more]

以太网地址

  • 每个以太网 NIC 都有一个唯一的内置以太网地址
    • 由 NIC 制造商分配
    • <24位制造商ID, 24位序列号>
  • 最初的以太网是在一根电缆上广播的
    • 主机使用目的地址来判断数据包是否真的给它
  • 今天的以太网局域网是一个交换机，每台主机都有一根电缆连接
    • 交换机使用目的地址来决定将数据包发送到哪台主机

我们可以用以太网地址做所有事情吗？

  1. 不行：以太网不是唯一的底层地址类型
  2. 不行：“扁平”地址使得广域路由变得困难
  • 所以：32位IP地址，高位包含路由提示

IP 头部

  • [kernel/net.h, struct ip]
  • 以太类型 0x0800
  • 很多东西，但地址是最关键的
  • 一个32位的IP地址足以路由到任何互联网计算机
  • 高位包含一个“网络号”，帮助路由器
    • 理解如何通过互联网转发
  • 协议号告诉目的地如何处理数据包
    • 即，将其交给哪个更高层的协议（通常是 UDP 或 TCP）

[tcpdump -t -n -xx ip | more]

注意：

  • 模式：“嵌套”更高层的数据包在更低层的数据包内
  • [图：eth | ip | udp | DNS]
  • 一层的负载以下一层的头部开始
  • 所以你经常看到一系列的头部

UDP 头部

  • [kernel/net.h, struct udp]
  • 一旦数据包到达正确的主机，它应该去哪个应用程序？
  • UDP 头部位于 IP 数据包内部
  • 包含源和目的端口号
  • 应用程序使用“套接字 API”系统调用来告诉
    • 内核它希望接收发送到特定端口的所有数据包
  • 一些端口是“众所周知的”，例如端口53保留给DNS服务器
  • 其他端口根据需要为连接的客户端分配
  • UDP 头部之后是：负载，例如 DNS 请求或响应

[tcpdump -t -n udp]

典型内核中的网络代码是什么样的？

  • 设计对性能和过载很重要

控制流

  • NIC 硬件（通常不止一个 NIC！）
    • NIC 内部缓冲区
  • NIC DMA 引擎
    • DMA RX 环
  • rx 中断处理程序，从 NIC 复制到软件输入队列
    • IP 输入队列
  • 网络线程
    • IP 等处理
    • 可能转发
    • 可能套接字队列
  • 应用程序
  • 输出处理
    • IP 输出队列
  • tx 中断处理程序
    • 释放完成的 NIC TX DMA 环形槽
    • 从软件输出队列复制到 TX 环
  • NIC

网络实验是这种安排的一个子集

注意：

  • 每一层在接收时解析、验证和剥离头部
    • 如果数据包损坏或队列太长则丢弃
  • 每一层在发送时前置一个头部

为什么有这么多数据包队列？

  • 吸收临时的输入突发，以避免在软件繁忙时强制丢弃
  • 在计算时保持输出 NIC 繁忙
  • 允许独立的控制流（NIC vs 网络线程 vs 应用程序）
    • 边界处的队列

其他安排是可能的，有时要好得多

  • 例如，用户级协议栈
  • 例如，用户直接访问 NIC（参见 Intel 的 DPDK）
  • 例如，轮询，如今天的论文所述

今天的论文： Mogul 和 Ramakrishnan 的《在中断驱动的内核中消除接收活锁》(Eliminating Receive Livelock in an Interrupt-Driven Kernel), 1996

我们为什么读这篇论文？

  • 检查内核网络栈结构中的一些权衡
  • 这是一篇著名且有影响力的论文
  • 活锁的类似情况出现在许多系统中

背景

  • 软件路由器非常普遍，通常是 Linux
    • 例如，防火墙、电缆调制解调器、wifi 接入点
  • 最大网络速度通常 > 路由器速度
  • 因此可能出现过载

解释图 6-1

  • 这是原始系统，没有作者的修复。
    • 系统是一个路由器：[NIC, RX 中断, 输入队列, IP, 输出队列, TX 中断, NIC]
    • (图 6-2)
  • 为什么黑点上升？
  • 是什么决定了峰值的高度？
    • 峰值 @ 5000 => 200 us/pkt。
  • 为什么黑点下降？
  • 是什么决定了它下降的速度？
  • 未被转发的数据包发生了什么？

问题：

  • NIC 中断的优先级高于所有其他处理。
  • 随着输入速率的增长，中断最终会使用 100% 的 CPU。
  • 那么就没有 CPU 时间可用于其余的 IP 处理。
    • (只有一个核心！)
  • IP 输入队列增长到允许的最大长度。
  • 然后 NIC 中断读取每个数据包，看到最大队列，丢弃数据包。

一个更高层次的观点：

  • 软件浪费时间部分处理最终将被丢弃的数据包。

网络实验中会发生活锁吗？

假设路由器设计是尽可能好的。

  • 那么图表会是什么样子？
  • 也就是说，我们合理的目标是什么？

论文的解决方案是什么？

  • 没有 IP 输入队列
  • NIC 接收中断只是唤醒网络线程
    • 然后让该 NIC 的中断禁用
  • 线程执行所有处理，
    • 重新检查 NIC 是否有更多输入，
    • 只有在没有输入等待时才重新启用中断。

轮询网络线程：

while(1)
  if NIC 有数据包在等待
    从 NIC 读取一个数据包
    完全处理该数据包
  else
    启用中断
    休眠

当数据包快速到达时会发生什么？

为什么要中断？为什么不总是轮询？

  • 当数据包缓慢到达时会发生什么？

现代 Linux 使用一种受这篇论文启发的方案 —— NAPI。

解释图 6-3

  • 这个图表包括了他们的系统。
  • 为什么空方块会趋于平稳？
  • 为什么空方块不像图 6-1 那样下降？
  • 多余的数据包发生了什么？

一个更高层次的观点：

  • 丢弃尽可能早地发生（在 NIC 中）。
  • CPU 不会浪费时间部分处理注定要被丢弃的数据包。

为什么“轮询（无配额）”效果不好？

  • 输入饿死了发送完成处理

为什么“无配额”会迅速下降，而不是逐渐减少？

  • 在丢弃前做更多的处理会使活锁变得更糟
  • 即，每个多余的接收数据包消耗了许多发送数据包的 CPU 时间

解释图 6-4

  • (这是每个数据包都通过一个用户级程序的情况)
  • 为什么“轮询，无反馈”表现不佳？
    • screend 前面有一个队列
    • 如果过载，100% 给网络线程，0% 给 screend
  • 为什么“带反馈的轮询”表现良好？
    • 当到 screend 的队列接近满时，网络线程休眠
    • 当队列接近空时唤醒

大局观：轮询循环是施加调度控制的地方

  • 配额、反馈

通用原则？

  • 如果新工作可能妨碍现有工作的完成，就不要开始新工作
  • 当需要丢弃时，尽早进行
  • 设计要使效率随负载增加而增加，
    • 而不是减少。例如，论文中在高负载下从
    • 中断切换到轮询。

解决同一问题的其他方法

  • 中断合并
  • 多核和多个 NIC 队列
  • 向用户代码暴露 NIC DMA 环 (DPDK)

类似现象出现在系统的其他领域

  • 随着连接数的增长，网络中的超时+重发
  • 随着核心数的增长，自旋锁

一个普遍的教训：复杂（多阶段）系统需要仔细

  • 调度资源，如果它们要在过载中生存下来

Linux 的 NAPI 轮询/中断方案：