介绍如何减少数据包拷贝开销介绍如何减少

《介绍如何减少数据包拷贝开销介绍如何减少》由会员分享，可在线阅读，更多相关《介绍如何减少数据包拷贝开销介绍如何减少（4页珍藏版）》请在金锄头文库上搜索。

1、本章是 part II 的最后一章。 第 5章介绍如何减少数据包拷贝开销， 第 6章介绍如何减少 控制开销， 端节点上最大的性能提升往往来自这两个方面， 现代网络实现基本上已经注意了 这些问题。第 7章和第 8 章分别介绍定时器和提前解复用实现的性能瓶颈和解决方法。第9章涉及其它常见的处理任务。第 9 章主要介绍缓冲区管理、 常规协议处理、 分片重组等的实现。 这些协议处理任务看 起来不起眼， 但是随着链路速度达到吉比特量级， 这些任务也不能忽视。 因为在极高的速度 下，每个包的处理时间非常短， 任何一个环节的低效都可能导致包处理时间超过预定的上限， 导致系统整体性能的下降。另一方面，网络中有

2、许多小包，对于这些小包来说，数据处理并 不是主要的开销（数据很少或没有数据，如 TCP 确认），主要的开销就在一般性的协议处理 上（分配包缓冲区，协议头处理等） 。9.1.1 缓冲区分配经典的 BSD UNIX 实现，称为 mbufs 。Mbufs 设计的出发点：（ 1）为便于动态扩展包的缓冲空间，用缓冲区链来存放包。比如，当包从上往下穿过 协议栈时，添加一个协议头，就只需要将协议头放到一个 mbuf 中，然后添加到链表头部。 Mbufs 出现的时候是 1981 年，那时正是各种网络技术全面开花的时期，没有哪一种网络技 术占统治地位， 将来会出现什么技术也不得而知。 因此， 数据包从上往下需要

3、经过哪几层协 议处理、每个协议头的长度是多少都无从知道， 从而无法知道应当为数据包分配多大的空间。 为了能支持各种可能的协议栈，操作系统必须允许动态扩展包的缓冲空间。（ 2）定义不同大小的缓冲区是为了充分利用内存空间。比如，一个190 字节的包会被分配两个 mbuf ，大约浪费 20 个字节的空间；一个 450 字节的包会被分配 5 个 mbuf ，浪费 大约 50个字节。这在当时（ 1981 年）很重要，因为那时计算机的内存普遍很小。Mbufs 的缺点是访问数据和拷贝数据的开销大，需要遍历链表。然而，随着网络发展态势的明朗， 动态扩展一个包的大小不那么重要了。以太网、TCP/IP成为主流，重

4、要的数据包路径（如以太网、IP、TCP）已确定，预分配缓冲区成为可能。其次，节省空间对于今天的计算机来说没有那么重要了，加快包的处理速度变得很重要。也就是说， mbufs 的设计考虑在今天都已经不重要了，但缺点却非常明显。Sk_bufLinux操作系统的实现称为 sk_buf。每个包缓冲区都是一块连续地址空间，提前为路径 上需要添加的各种包头预留了空间。如何为不同大小的包分配内存？给每个包分配最大长度的包缓冲区是一个很大的浪费。比较好的方法是按需分配内存， 当一个包到来时，为其分配一块合适大小的缓存空间。动态分配内存的困难在于， 用户会在不同的时间释放缓冲区， 使得内存中出现许多不连 续的、

5、大小不同的空闲区域。教科书上有一些标准的算法，可以高效地搜索内存，找到一块合适大小的空闲区域。 然而，任何一个开发高速网络软件的人都不会使用这样的内存分配器， 因为分配速度太慢。他们会考虑以下 3 种分配器。隔离池分配器这是随 BSD 4.2 UNIX 发布的内存分配器， 由 Chris Kingsley 实现，称 Kingsley malloc（） 。 称这些内存池是隔离的， 因为当一个内存分配请求不能满足时， 不会试图去切分较大的 缓冲区，也不会试图去合并连续的较小的缓冲区。Linux 分配器Linux 分配器最初由 Doug Lea 实现，称为 dlmalloc（） 。Lea 分配器比

6、Kingsley 分配器使用内存更高效， （ 1）可以将较小的空闲缓冲区合并， （ 2） 小缓冲区（常见情形）浪费的空间不超过 8 字节。缺点是实现起来更复杂。对于既要求线速、又要求有效利用内存的高速网络来说，也不是一个最好的选择。批量分配器 批量是指分配器一次性向系统请求一大块内存， 用来作为包缓冲区池， 而不是每来一个 包向系统请求一块内存。批量分配器（续）在内存块中顺序分配是很容易的， 问题主要在释放环节。 若释放的顺序和分配的顺序不 一致，就会在内存块中形成一些孔洞，需要合并。有两种方法解决这个问题。（ 1）如果应用知道所有分配的缓冲区最终都会被释放，那么只需使用足够多的空闲块，确保在

7、这些内存块用完之前， 已分配的内存块会被释放。 这么做会有一定的风险。 但目前工 业界采用的正是这个方法，比如分配一个 4GB 的大缓冲区用于收包。（2）如果缓冲区是在虚拟存储系统中分配的，那么可以使用页面重映射将若干分离的 物理页映射成在虚拟存储空间是连续的。批量分配器的优点是支持可变长度的内存分配， 没有内存浪费 （若内存块未用完的话） ， 分配快。内存分配可以用硬件实现，后台创建空闲块用软件实现。9.1.2 共享缓冲区这里的困难在于共享缓冲区的用户是变化的， 因此，每个用户分配的缓冲区数量应当能 够动态调整。比如，用户较少时，每个用户可以多使用一些；当有新用户加入时，应能从老 用户那儿夺

8、取一些缓冲区。缓冲区窃取缓冲区窃取是公平分配的一种方法： 若所有缓冲区已用完， 一个分配较少的用户可从当 前分配最多的用户那儿窃取一些缓冲区。 采用缓冲区窃取， 即使一开始的时候分配是不均衡 的，经过一定时间，最终每个用户都可以获得它们公平的份额。实现缓冲区窃取， 最主要的就是找到当前使用资源最多的用户， 通常的解决方案是使用 一个大顶堆，时间代价是 O（logn） ， n 为活跃的用户数。假如 n 很大，我们希望降低分配的 时间复杂度，那有没有更快的算法呢？缓冲区窃取的常数时间算法 如果允许一个用户一次获取任意数量的缓冲区， 并且我们希望找到最大分配的用户， 那 么使用 O（logn） 的堆

9、是必需的。假定为了获得常数时间的算法， 我们对问题做一些限制， 规定一个用户一次只能窃取一 个缓冲区， 并且每个用户拥有的缓冲区数量是一个小整数， 这种情况下是否有更高效的实现 方法？这又变成了一个小整数排序的问题。窃取一个缓冲区注意：如果 P 和 Q 的缓冲区数量变化大于 1，这个方法可能会很低效。比如，如果Q有 300 个缓冲区， 一下子减少了 100 个缓冲区， 而其它用户起始时只有几个缓冲区， 那么更 新 highest 需要检查 100 个桶。现在限定每次只能增加或减少一个缓冲区，则算法每次只需 移动一个桶。9.2 TCP 头部预测我们前面说过，因特网上最主要的流量是TCP,因此线速

10、处理 TCP包很重要，然而最复杂的数据面协议也是 TCP。早期的TCP实现非常慢，曾经有人觉得 TCP处理速度太慢了， 提出重新设计一个传输层协议XTP来取代TCP。但是Van Jacobson （美国计算机科学家，TCP/IP 栈代码的主要贡献者）不肯放弃,仔细研究 TCP 处理慢的原因。经分析，TCP输入处理（tcp_input ）是TCP软件中最长的一部分代码，约有 1100行。 其实 TCP 输入处理并不复杂,但非常繁琐,其实现完全遵循 RFC 793 中定义的输入事件处 理步骤,基本上就是在逐个状态地检查,以确定要执行什么处理。Van Jacobson发现，1100行代码中绝大部分代

11、码用于处理罕见的情形，即检查的大部分状态都是很少发生的。为此提出头部预测机制,在收到 TCP 包后,先通过少量的状态检查 迅速识别出该包是否为预期的 TCP 段,从而常见情形下可以避免大量不必要的状态检查。接收端头部预测的伪代码伪代码描述了头部预测的处理。显然,当输入的 TCP 段符合预期情形的话,其处理过程要快得多。注意,判断是纯 ACK 段还是纯数据段,伪代码中没有展开写细节,这里要涉及好几个 条件的判断。标志域中包含 6 个标志位, 逐位比较的话需要 6 次比较。 注意到标志域以及窗口大小组 成了一个 32位的字, 可以将这个字的预期值保存到 TCB 中,这样头两个子句的检查只需用 输入

12、 TCP 段头的第 4个字与 PCB 中保存的字进行一次比较即可。发送端头部预测 目前为止讨论的是接收端的头部预测,发送端也可以有类似的处理方法。经过以上优化处理后, TCP 的处理速度得到了极大的提高,可以达到 100Mbps 的吞吐 量。这里得到的一个启示是, 不要仅仅因为性能低就放弃一个协议, 真正要做的是想办法提 高它的性能。9.3 IP 分片重组IP分片重组也是一个重要的功能。尽管IPv6取消了路由器分片的功能，但源主机仍然可能要做分片的工作。比如,一个封装了很大的 UDP 包的 IP 包（ UDP 包必须封装在一个 IP 包中）,如果超出了链路 MTU ,源主机必须做分片的工作,接

13、收主机需要重组。有一种碎片攻击,攻击者故意将攻击包载荷分装到多个IP 包中,以规避扫描。这时,入侵检测设备必须先把 IP 包重组,然后再扫描。所以,接收端必须快速实现重组。图示是一个用于分片重组的简单数据结构,与 BSD UNIX 中使用的数据结构类似。假 定有 3 个属于同一个 IP 包的分片到达,各分片按照它们的分片偏移量保存在一个有序链表 中,注意各个分片的内容可能有重叠。IP 分片重组的经典过程如下： 。最终的实现相当复杂,且很慢。优化预期情形 重组过程为什么复杂，主要是考虑到：1） IP 分片可能乱序到达， 2）分片之间可能有重叠。然而，大部分情况下 IP 分片是按序到达的，且分片之

14、间没有重叠。如果 IP 分片按序到达且分片之间没有重叠，只需将分片放到链表尾部即可。优化的 IP 分片重组算法图 9.10 的数据结构与图 9.9 相同，只是增加了一个指向链表尾部的指针。 与图 9.9 的实现相比，寻找插入位置及检查重组是否结束都只需要常数时间，而不是线 性时间。如果不是预期情形，仍使用标准的重组实现。假设与实际相符吗？图 9.10 有一个隐含的假设： IP 分片按照偏移量从小到大的顺序发送。实际情况是否符 合这个假设呢？测试的结果令人大吃一惊，许多较新的实现（包括 Linux ），发送端是按照 分片偏移量从大到小的顺序发送的！这看起来相当怪异，但其实是合理的。因为只有最后一个分片携带了 IP 包总长度的信 息（总长度 =分片偏移量 *8+ 分片包长），让最后一个分片最先到达接收端，方便接收端为数 据包分配适当大小的缓冲区。9.4 总结 本章介绍高效的缓冲区分配、协议处理和分片重组的相关技术。 对于缓冲区分配，不同的算法在空间利用率和合并不连续空闲缓冲区的难度之间权衡。批量分配器通过分配足够多的内存块来避免合并空闲缓冲区， 整体来看空间利用率不高 （属 于用空间换时间） 。TCP 输入处理、 IP 分片重组均通过优化预期情形提高了正常情况下的处理速度。