本文整理至: MIT 6.S081 2020 操作系统 Lec 21。
本节对应论文: Eliminating Receive Livelock in an Interrupt-driven Kernel
今天我想讨论一下Networking以及它与操作系统的关联。今天这节课的很多内容都与最后一个lab,也就是构建一个网卡驱动相关。在这节课,我们首先会大概看一下操作系统中网络相关的软件会有什么样的结构,之后我们会讨论今天的论文Livelock。Livelock展示了在设计网络协议栈时可能会出现的有趣的陷阱。
首先,让我通过画图来描述一下基本的网络场景。网络连接了不同的主机,这里的连接有两种方式:
相近的主机连接在同一个网络中。例如有一个以太网设备,可能是交换机或者单纯的线缆,然后有一些主机连接到了这个以太网设备。这里的主机可能是笔记本电脑,服务器或者路由器。在设计网络相关软件的时候,通常会忽略直接连接了主机的网络设备。这里的网络设备可能只是一根线缆(几十年前就是通过线缆连接主机);也可能是一个以太网交换机;也可能是wifi无线局域网设备(主机通过射频链路与网络设备相连),但是不管是哪种设备,这种直接连接的设备会在网络协议栈的底层被屏蔽掉。
每个主机上会有不同的应用程序,或许其中一个主机有网络浏览器,另一个主机有HTTP server,它们需要通过这个局域网来相互通信。
一个局域网的大小是有极限的。局域网(Local Area Network)通常简称为LAN。一个局域网需要能让其中的主机都能收到彼此发送的packet。有时,主机需要广播packet到局域网中的所有主机。当局域网中只有25甚至100个主机时,是没有问题的。但是你不能构建一个多于几百个主机的局域网。
所以为了解决这个问题,大型网络是这样构建的。首先有多个独立的局域网,假设其中一个局域网是MIT,另一个局域网是Harvard,还有一个很远的局域网是Stanford,在这些局域网之间会有一些设备将它们连接在一起,这些设备通常是路由器Router。其中一个Router接入到了MIT的局域网,同时也接入到了Harvard的局域网。
路由器是组成互联网的核心,路由器之间的链路,最终将多个局域网连接在了一起。
现在MIT有一个主机需要与Stanford的一个主机通信,他们之间需要经过一系列的路由器,路由器之间的转发称为Routing。所以我们需要有一种方法让MIT的主机能够寻址到Stanford的主机,并且我们需要让连接了MIT的路由器能够在收到来自MIT的主机的packet的时候,能够知道这个packet是发送给Harvard的呢,还是发送给Stanford的。
从网络协议的角度来说,局域网通信由以太网协议决定。而局域网之上的长距离网络通信由Internet Protocol协议决定。以上就是网络的概述。
接下来我想介绍一下,在局域网和互联网上传递的packet有什么样的结构,之后再讨论在主机和路由器中的软件是如何处理这些packet。
让我从最底层开始,我们先来看一下一个以太网packet的结构是什么。当两个主机非常靠近时,或许是通过相同的线缆连接,或许连接在同一个wifi网络,或许连接到同一个以太网交换机。当局域网中的两个主机彼此间要通信时,最底层的协议是以太网协议。你可以认为Host1通过以太网将Frame发送给Host2。Frame是以太网中用来描述packet的单词,本质上这就是两个主机在以太网上传输的一个个的数据Byte。以太网协议会在Frame中放入足够的信息让主机能够识别彼此,并且识别这是不是发送给自己的Frame。每个以太网packet在最开始都有一个Header,其中包含了3个数据。Header之后才是payload数据。Header中的3个数据是:目的以太网地址,源以太网地址,以及packet的类型。
每一个以太网地址都是48bit的数字,这个数字唯一识别了一个网卡。packet的类型会告诉接收端的主机该如何处理这个packet。接收端主机侧更高层级的网络协议会按照packet的类型检查并处理以太网packet中的payload。
整个以太网packet,包括了48bit+48bit的以太网地址,16bit的类型,以及任意长度的payload这些都是通过线路传输。除此之外,虽然对于软件来说是不可见的,但是在packet的开头还有被硬件识别的表明packet起始的数据(注,Preamble + SFD),在packet的结束位置还有几个bit表明packet的结束(注,FCS)。packet的开头和结束的标志不会被系统内核所看到,其他的部分会从网卡送到系统内核。
如果你们查看了这门课程的最后一个lab,你们可以发现我们提供的代码里面包括了一些新的文件,其中包括了kernel/net.h,这个文件中包含了大量不同网络协议的packet header的定义。上图中的代码包含了以太网协议的定义。我们提供的代码使用了这里结构体的定义来解析收到的以太网packet,进而获得目的地址和类型值(注,实际中只需要对收到的raw data指针强制类型转换成结构体指针就可以完成解析)
。
硬件用来识别以太网packet的开头和结束的标志是不是类似于lab中的End of Packets?
有关以太网48bit地址,是为了给每一个制造出来的网卡分配一个唯一的ID,所以这里有大量的可用数字。这里48bit地址中,前24bit表示的是制造商,每个网卡制造商都有自己唯一的编号,并且会出现在前24bit中。后24bit是由网卡制造商提供的任意唯一数字,通常网卡制造商是递增的分配数字。所以,如果你从一个网卡制造商买了一批网卡,每个网卡都会被写入属于自己的地址,并且如果你查看这些地址,你可以发现,这批网卡的高24bit是一样的,而低24bit极有可能是一些连续的数字。
虽然以太网地址是唯一的,但是出了局域网,它们对于定位目的主机的位置是没有帮助的。如果网络通信的目的主机在同一个局域网,那么目的主机会监听发给自己的地址的packet。但是如果网络通信发生在两个国家的主机之间,你需要使用一个不同的寻址方法,这就是IP地址的作用。
在实际中,你可以使用tcpdump来查看以太网packet。这将会是lab的一部分。下图是tcpdump的一个输出:
tcpdump输出了很多信息,其中包括:
如果按照前面以太网header的格式,可以发现packet中:
下一个与以太网通信相关的协议是ARP。在以太网层面,每个主机都有一个以太网地址。但是为了能在互联网上通信,你需要有32bit的IP地址。为什么需要IP地址呢?因为IP地址有额外的含义。IP地址的高位bit包含了在整个互联网中,这个packet的目的地在哪。所以IP地址的高位bit对应的是网络号,虽然实际上要更复杂一些,但是你可以认为互联网上的每一个网络都有一个唯一的网络号。路由器会检查IP地址的高bit位,并决定将这个packet转发给互联网上的哪个路由器。IP地址的低bit位代表了在局域网中特定的主机。当一个经过互联网转发的packet到达了局域以太网,我们需要从32bit的IP地址,找到对应主机的48bit以太网地址。这里是通过一个动态解析协议完成的,也就是Address Resolution Protocol,ARP协议。
当一个packet到达路由器并且需要转发给同一个以太网中的另一个主机,或者一个主机将packet发送给同一个以太网中的另一个主机时,发送方首先会在局域网中广播一个ARP packet,来表示任何拥有了这个32bit的IP地址的主机,请将你的48bit以太网地址返回过来。如果相应的主机存在并且开机了,它会向发送方发送一个ARP response packet。
下图是一个ARP packet的格式:
它会出现在一个以太网packet的payload中。所以你们看到的将会是这样的结构:首先是以太网header,它包含了48bit的目的以太网地址,48bit的源以太网地址,16bit的类型;之后的以太网的payload会是ARP packet,包含了上图的内容。
接收到packet的主机通过查看以太网header中的16bit类型可以知道这是一个ARP packet。在ARP中类型值是0x0806。通过识别类型,接收到packet的主机就知道可以将这个packet发送给ARP协议处理代码。
有关ARP packet的内容,包含了不少信息,但是基本上就是在说,现在有一个IP地址,我想将它转换成以太网地址,如果你拥有这个IP地址,请响应我。
同样的,我们也可以通过tcpdump来查看这些packet。在网络的lab中,XV6会在QEMU模拟的环境下发送IP packet。所以你们可以看到在XV6和其他主机之间有ARP的交互。下图中第一个packet是我的主机想要知道XV6主机的以太网地址,第二个packet是XV6在收到了第一个packet之后,并意识到自己是IP地址的拥有者,然后返回response。
tcpdump能够解析出ARP packet,并将数据打印在第一行。对应ARP packet的格式,在第一个packet中,10.0.2.2是SIP,10.0.2.15是DIP。在第二个packet中,52:54:00:12:34:56对应SHA。
同时,我们也可以自己分析packet的原始数据。对于第一个packet:
第二个packet是第一个packet的响应。
ethernet header中已经包括了发送方的以太网地址,为什么ARP packet里面还要包含发送方的以太网地址?
tcpdump中原始数据的右侧是什么内容?
我希望你们在刚刚的讨论中注意到这一点,网络协议和网络协议header是嵌套的。我们刚刚看到的是一个packet拥有了ethernet header和ethernet payload。在ethernet payload中,首先出现的是ARP header,对于ARP来说并没有payload。但是在ethernet packet中还可以包含其他更复杂的结构,比如说ethernet payload中包含一个IP packet,IP packet中又包含了一个UDP packet,所以IP header之后是UDP header。如果在UDP中包含另一个协议,那么UDP payload中又可能包含其他的packet,例如DNS packet。
所以发送packet的主机会按照这样的方式构建packet:DNS相关软件想要在UDP协议之上构建一个packet;UDP相关软件会将UDP header挂在DNS packet之前,并在IP协议之上构建另一个packet;IP相关的软件会将IP heade挂在UDP packet之前;最后Ethernet相关的软件会将Ethernet header挂在IP header之前。所以整个packet是在发送过程中逐渐构建起来的。
类似的,当一个操作系统收到了一个packet,它会先解析第一个header并知道这是Ethernet,经过一些合法性检查之后,Ethernet header会被剥离,操作系统会解析下一个header。在Ethernet header中包含了一个类型字段,它表明了该如何解析下一个header。同样的在IP header中包含了一个protocol字段,它也表明了该如何解析下一个header。
软件会解析每个header,做校验,剥离header,并得到下一个header。一直重复这个过程直到得到最后的数据。这就是嵌套的packet header。
Ethernet header足够在一个局域网中将packet发送到一个host。如果你想在局域网发送一个IP packet,那么你可以使用ARP获得以太网地址。但是IP协议更加的通用,IP协议能帮助你向互联网上任意位置发送packet。下图是一个IP packet的header,你们可以在lab配套的代码中的net.h文件找到。
如果IP packet是通过以太网传输,那么你可以看到,在一个以太网packet中,最开始是目的以太网地址,源以太网地址,以太网类型是0x0800,之后是IP header,最后是IP payload。
在一个packet发送到世界另一端的网络的过程中,IP header会被一直保留,而Ethernet header在离开本地的以太网之后会被剥离。或许packet在被路由的过程中,在每一跳(hop)会加上一个新的Ethernet header。但是IP header从源主机到目的主机的过程中会一直保留。
IP header具有全局的意义,而Ethernet header只在单个局域网有意义。所以IP header必须包含足够的信息,这样才能将packet传输给互联网上遥远的另一端。对于我们来说,关键的信息是三个部分,目的IP地址(ip_dst),源IP地址(ip_src)和协议(ip_p)。目的IP地址是我们想要将packet送到的目的主机的IP地址。地址中的高bit位是网络号,它会帮助路由器完成路由。IP header中的协议字段会告诉目的主机如何处理IP payload。
如果你们看到过MIT的IP地址,你们可以看到IP地址是18.x.x.x,虽然最近有些变化,但是在很长一段时间18是MIT的网络号。所以MIT的大部分主机的IP地址最高字节就是18。全世界的路由器在看到网络号18的时候,就知道应该将packet路由到离MIT更近的地方。
接下来我们看一下包含了IP packet的tcpdump输出:
因为这个IP packet是在以太网上传输,所以它包含了以太网header。实际上这个packet里面有点问题,我不太确定具体的原因是什么,但是Ethernet header中目的以太网地址不应该是全f,因为全f是广播地址,它会导致packet被发送到所有的主机上。一个真实网络中两个主机之间的packet,不可能出现这样的以太网地址。所以我提供的针对network lab的方案,在QEMU上运行有点问题。不管怎么样,我们可以看到以太网目的地址,以太网源地址,以及以太网类型0x0800。0x0800表明了Ethernet payload是一个IP packet。
IP header的长度是20个字节,所以中括号内的是IP header:
从后向前看:
IP header中的protocol字段告诉了目的主机的网络协议栈,这个packet应该被UDP软件处理。
IP header足够让一个packet传输到互联网上的任意一个主机,但是我们希望做的更好一些。每一个主机都运行了大量需要使用网络的应用程序,所以我们需要有一种方式能区分一个packet应该传递给目的主机的哪一个应用程序,而IP header明显不包含这种区分方式。有一些其他的协议完成了这里的区分工作,其中一个是TCP,它比较复杂,而另一个是UDP。TCP不仅帮助你将packet发送到了正确的应用程序,同时也包含了序列号等用来检测丢包并重传的功能,这样即使网络出现问题,数据也能完整有序的传输。相比之下,UDP就要简单的多,它以一种“尽力而为”的方式将packet发送到目的主机,除此之外不提供任何其他功能。
UDP header中最关键的两个字段是sport源端口和dport目的端口:
当你的应用程序需要发送或者接受packet,它会使用socket API,这包含了一系列的系统调用。一个进程可以使用socket API来表明应用程序对于特定目的端口的packet感兴趣。当应用程序调用这里的系统调用,操作系统会返回一个文件描述符。每当主机收到了一个目的端口匹配的packet,这个packet会出现在文件描述符中,之后应用程序就可以通过文件描述符读取packet。
这里的端口分为两类,一类是常见的端口,例如53对应的是DNS服务的端口,如果你想向一个DNS server发请求,你可以发送一个UDP packet并且目的端口是53。除此之外,很多常见的服务都占用了特定的端口。除了常见端口,16bit数的剩下部分被用来作为匿名客户端的源端口。比如说,我想向一个DNS server的53端口发送一个packet,目的端口会是53,但是源端口会是一个本地随机选择的端口,这个随机端口会与本地的应用程序的socket关联。所以当DNS server向本地服务器发送一个回复packet,它会将请求中的源端口拷贝到回复packet的目的端口,再将回复packet发送回本地的服务器。本地服务器会使用这个端口来确定应该将packet发送给哪个应用程序。
接下来我们看一下UDP packet的tcpdump输出。首先,我们同样会有一个以太网Header,以及20字节的IP header。IP header中的0x11表明这个packet的IP协议号是17,这样packet的接收主机就知道应该使用UDP软件来处理这个packet。
接下来的8个字节是UDP header。这里的packet是由lab代码生成的packet,所以它并没有包含常见的端口,源端口是0x0700,目的端口是0x6403。第4-5个字节是长度,第6-7个字节是校验和。XV6的UDP软件并没有生成UDP的校验和。
UDP header之后就是UDP的payload。在这个packet中,应用程序发送的是ASCII文本,所以我们可以从右边的ASCII码看到,内容是“a.message.from.xv6”。所以ASCII文本放在了一个UDP packet中,然后又放到了一个IP packet中,然后又放到了一个Ethernet packet中。最后发布到以太网上。
当你发送一个packet给一个主机,但是你又不知道它的以太网地址,这个packet是不是会被送到路由器,之后再由路由器来找到以太网地址?
对于packet的长度有限制吗?
以上就是UDP的介绍。在lab的最后你们会通过实验提供的代码来向谷歌的DNS server发送一个查询,收到回复之后代码会打印输出。你们需要在设备驱动侧完成以太网数据的处理。
与packet的协议和格式对应的是运行在主机上的网络协议栈。人们有各种各样的方式来组织网络软件,接下来我会介绍最典型的,并且至少我认为是最标准的组织方式。
假设我们现在在运行Linux或者XV6,我们有一些应用程序比如浏览器,DNS服务器。这些应用程序使用socket API打开了socket layer的文件描述符。Socket layer是内核中的一层软件,它会维护一个表单来记录文件描述符和UDP/TCP端口号之间的关系。同时它也会为每个socket维护一个队列用来存储接收到的packet。我们在networking lab中提供的代码模板包含了一个非常原始的socket layer。
在socket layer之下是UDP和TCP协议层。UDP软件几乎不做任何事情,它只是检查收到的packet,获取目的端口号,并将UDP payload传输给socket layer中对应的队列。TCP软件会复杂的多,它会维护每个TCP连接的状态,比如记录每个TCP连接的序列号,哪些packet没有被ACK,哪些packet需要重传。所以TCP的协议控制模块会记录大量的状态,但是UDP中不会记录任何状态。UDP和TCP通常被称为传输层。networking lab提供的代码中有一个简单的UDP层,但是没有TCP的代码。
在TCP/UDP之下是IP层,IP层的软件通常很简单。虽然我不确定是在同一层还是下一层,与IP层在一起的还有ARP层。
再往下的话,我们可以认为还会有一层以太网。但是通常并没有一个独立的以太网层。通常来说这个位置是一个或者多个网卡驱动,这些驱动与实际的网卡硬件交互。网卡硬件与局域网会有实际的连接
当一个packet从网络送达时,网卡会从网络中将packet接收住并传递给网卡驱动。网卡驱动会将packet向网络协议栈上层推送。在IP层,软件会检查并校验IP header,将其剥离,再把剩下的数据向上推送给UDP。UDP也会检查并校验UDP header,将其剥离,再把剩下的数据加入到socket layer中相应文件描述符对应的队列中。所以一个packet在被收到之后,会自底向上逐层解析并剥离header。当应用程序发送一个packet,会自顶向下逐层添加header,直到最底层packet再被传递给硬件网卡用来在网络中传输。所以内核中的网络软件通常都是被嵌套的协议所驱动。
这里实际上我忘了一件重要的事情,在整个处理流程中都会有packet buffer。所以当收到了一个packet之后,它会被拷贝到一个packet buffer中,这个packet buffer会在网络协议栈中传递。通常在不同的协议层之间会有队列,比如在socket layer就有一个等待被应用程序处理的packet队列,这里的队列是一个linked-list。通常整个网络协议栈都会使用buffer分配器,buffer结构。在我们提供的networking lab代码中,buffer接口名叫MBUF。
以上就是一个典型的网络协议栈的分层图。
对于今天的论文,了解packet的控制流程是如何工作的还是比较重要,这里的控制流程与前一节介绍的分层网络协议栈还不太一样。
有关网络协议栈,通常会有多个独立的actor会处理packet,解析packet并生成输出。出于各种各样的原因,这些不同的actor之间是解耦的,这样它们可以并发的运行,并且连接不同的packet队列。这对于今天的论文来说,是非常重要的前提。
现在我们有了一张网卡,有了一个系统内核。当网卡收到了一个packet,它会生成一个中断。系统内核中处理中断的程序会被触发,并从网卡中获取packet。因为我们不想现在就处理这个packet,中断处理程序通常会将packet挂在一个队列中并返回,packet稍后再由别的程序处理。所以中断处理程序这里只做了非常少的工作,也就是将packet从网卡中读出来,然后放置到队列中。
典型的生产者消费者模式
在一个传统的网络协议栈中,我们之所以想要快速的将packet从网卡中读出并存放于软件队列中,是因为通常来说网卡中用来存储packet的内存都非常小,而在计算机的RAM中,会有GB级别的内存,所以计算机的内存要大得多。如果有大量的packet发送到网卡,网卡可能会没有足够的内存来存储packet,所以我们需要尽快将packet拷贝到计算机的内存中。
之后,在一个独立的线程中,会有一个叫做IP processing thread的程序。它会读取内存中的packet队列,并决定如何处理每一个packet。其中一个可能是将packet向上传递给UDP,再向上传递给socket layer的某个队列中,最后等待某个应用程序来读取。通常来说,这里的向上传递实际上就是在同一个线程context下的函数调用。
另一种可能就是,这个主机实际上是个路由器,packet从一个网卡进来,经过路由需要从另一个网卡出去。通过例如Linux操作系统构建路由器是非常常见的。如果你买一个wifi路由器,或者一个有线调制解调器,非常有可能里面运行的就是Linux系统,并且使用了Linux网络协议栈,因为Linux的协议栈实现了完整的路由协议。所以,如果IP process thread查看了packet的目的IP地址,并决定将packet从另一个网卡转发出去,它会将packet加入到针对发送网卡的发送队列中。
通常来说网卡会有发送中断程序,当网卡发送了一个packet,并且准备好处理更多packet的时候,会触发一个中断。所以网卡的发送中断也很重要。
在这个结构中,有一点非常重要,这里存在一些并发的组件,它们以不同的方式调度。中断处理程序由网卡的发送或者接受中断触发。IP processing thread就是一个内核线程。在一个处理器上,IP processing thread不能与中断处理程序同时运行,因为中断处理程序的优先级最高,不过在多核处理器上,并发度可能会更高。最后,应用程序要能够读取socket layer中的packet,应用程序又是另一个独立调度的组件。所有这些组件都会参与到CPU的调度中。
缓存队列经常会被提到,在上图中,总共有3个队列。这里的队列的作用是,一个独立的组件会向队列中添加packet,其他的组件会从队列中读取packet。在网络系统中,这样的队列很常见,主要出于以下几个原因:
同一个网卡可以即是接收方又是发送方吗?
所以多网卡的场景在于想要连接不同的网络?
我想再讨论一下当packet送到网卡时,网卡会做什么操作?这与networking lab非常相关。对于一个网卡的结构,会有一根线缆连接到外面的世界。网卡会检查线缆上的电信号,并将电信号转换成packet。网卡会接入到一个主机上,主机会带有网卡的驱动软件。我们需要将网卡解码出来的packet传递给主机的内存,这样软件才能解析packet。
网卡内有许多内置的内存,当packet到达时,网卡会将packet存在自己的缓存中,并向主机发送中断,所以网卡内部会有一个队列。而主机的驱动包含了一个循环,它会与网卡交互,并询问当前是否缓存了packet。如果是的话,主机的循环会逐字节的拷贝packet到主机的内存中,再将内存中的packet加到一个队列中。这是我们今天要看的论文中网卡的工作方式:网卡驱动会负责拷贝网卡内存中的数据到主机内存。这在30年前还是有意义的,但是今天通过驱动中的循环来从硬件拷贝数据是非常慢的行为。即使是在同一个计算机上,外设到CPU之间的距离也非常的长,所以它们之间的交互需要的时间比较长。所以人们现在不会这么设计高速接口了。
接下来我将讨论一下E1000网卡的结构,这是你们在实验中要使用的网卡。E1000网卡会监听网线上的电信号,但是当收到packet的时候,网卡内部并没有太多的缓存,所以网卡会直接将packet拷贝到主机的内存中,而内存中的packet会等待驱动来读取自己。所以,网卡需要事先知道它应该将packet拷贝到主机内存中的哪个位置。E1000是这样工作的,主机上的软件会格式化好一个DMA ring,ring里面存储的是packet指针。所以,DMA ring就是一个数组,里面的每一个元素都是指向packet的指针。
当位于主机的驱动初始化网卡的时候,它会分配一定数量,例如16个1500字节长度的packet buffer,然后再创建一个16个指针的数组。为什么叫ring呢?因为在这个数组中,如果用到了最后一个buffer,下一次又会使用第一个buffer。主机上的驱动软件会告诉网卡DMA ring在内存中的地址,这样网卡就可以将packet拷贝到内存中的对应位置。
当网卡收到packet时,网卡还会记住当前应该在DMA ring的哪个位置并通过DMA将packet传输过去:
传输完成之后,网卡会将内部的记录的指针指向DMA ring的下一个位置,这样就可以拷贝下一个packet:
刚才说的都是接收packet,对应的是RX ring。类似的,驱动还会设置好发送buffer,也就是TX ring。驱动会将需要网卡传输的packet存储在 TX ring中,网卡也需要知道TX ring的地址。
你们在networking lab中的主要工作就是写驱动来处理这些ring。
E1000与生产环境的高性能场景使用的网卡有什么区别吗?
在接下来的networking lab中,IP层和驱动之间没有队列,是吗?
那这样的话,性能会不会很差?
为了让网卡能支持DMA,需要对硬件做一些修改吗?在E1000之前的网卡中,所有的数据传输都是通过CPU进行传输。
接下来我们看一下今天的论文。因为我们已经介绍了很多论文相关的背景知识,我们直接来看一下论文的图1。我们之后根据论文中的图来开展讨论。
这张图是一个路由器的性能图。这是一个有两张网卡的路由器,它的工作是从一个网卡接收packet,再从另一个网卡送出 。X轴是接收速率,也就是接收端网卡的收到packet的速率。Y轴是发送速率,也就是观察到的发送端网卡发送packet的速率。我们关心的是实心圆对应的曲线,它先上升,再下降。所以即使还不知道任何上下文,看到这个图之后我们会问自己,为什么这个曲线先上升,再下降?曲线的转折点有什么特殊之处?是什么决定了曲线的上升斜率和下降斜率?即使不知道任何背景知识,我们还是可以问出这么多问题。
首先,为什么这条曲线开始会上升?
那么为什么曲线不是一直上升的呢?
上面的图中,曲线在5000的位置就停止不再上升了,这告诉我们这台机器处理每个packet要消耗200微秒。所以,曲线的转折点隐含的包含了处理一个packet需要的时间信息。虽然这只是一个猜想,但是通常与真实的结果非常相近。或许我们可以修改软件使其更加的高效,我们可以优化到处理每个packet只需要150微秒,我们或许可以将曲线的转折点向上移一些,但是在到达了这台机器每秒能处理的packet数量的极限时,我们还是会到达曲线的转折点。
除了CPU的性能,还有一些不是必然存在的瓶颈需要注意一下。最明显的一个就是网络的性能。如果你使用的网络只有10Mb/s,那么底层的网路硬件最多就能按照这个速率传输数据,这也有可能构成一个限制。所以也有可能是因为网络传输的速率决定了曲线的顶点是在5000pps这个位置。论文中并没有说明究竟是CPU还是网速是这里的限制因素,但是对于一个10Mb/s的网络,如果你传输小包的话,是可以达到10-15 Kpps,这实际上是网线的能达到的极限,而上图中转折点对应的5Kpps远小于10-15Kpps,所以几乎可以确定限制是来自CPU或者内存,而不是网络本身。
在一个设计良好的路由器中,如果处理每个packet要200微秒,那么我们期望看到的是不论负载多高,路由器至少每秒能处理5000个packet。所以我们期望看到的曲线在5000pps之后是一条水平线,路由器每秒处理5000个packet,并丢弃掉其他的packet。
但是我们实际拥有的曲线会更加的糟糕,当收到的packets超过5000pps时,成功转发的packets随着收到的packet的增多反而趋向于0。为什么曲线会下降呢?
论文作者给出的原因是,随着packet接收速率的增加,每个收到的packet都会生成一个中断,而这里的中断的代价非常高,因为中断涉及到CPU将一个packet从网卡拷贝到主机的内存中。如果我们知道packet将会以10K每秒的速率到达,并且我们知道我们不能处理这么多packet,那么我们可以期望的最好结果就是每秒转发5000个packet,并且丢弃5000个packet之外的其他packet。但是实际上,5000个packet之外的其他packet,每个都生成了一个昂贵的中断,收到的packet越多,生成的中断就越多。而中断有更高的优先级,所以每一个额外的packet都会消耗CPU时间,导致更少的CPU时间可以用来完成packet的转发。最后,100%的CPU时间都被消耗用来处理网卡的输入中断,CPU没有任何时间用来转发packet。
这里曲线的下降被称为中断的Livelock,这是一个在很多系统中都会出现的现象。这里背后的原因是有两个独立的任务,比如这里的两个任务是输入中断和转发packet程序。由于调度的策略,输入中断的优先级更高,使得转发packet的任务可能分配不到任何CPU时间。几乎在任何需要处理输入的系统中,如果输入速率过高,都有可能出现Livelock。Livelock不仅会因为CPU耗尽而发生,也可能是其他原因,比如说网卡的DMA耗尽了RAM的处理时间,那么网卡占据了RAM导致CPU不能使用RAM。所以,即使你拥有大量的CPU空闲时间,还是有可能触发Livelock。不管怎样,这曲线的下降被称为Livelock。
你或许会问,不能处理的packet最后怎么样了?我们回想一下网络协议软件的结构,网卡会通知网卡的接收中断,接收中断将packet拷贝到队列缓存中,之后会有一个线程处理队列缓存中的packet。
所以packet会在队列缓存中丢失。队列缓存有一个最大的长度,至少RAM的大小是有限制大,但是队列缓存的大小会远小于RAM的大小。如果网卡的接收中断从网卡获得了一个packet,并且发现队列缓存的长度已经是最长了,接收中断程序会丢弃packet。
论文作者对于Livelock提出了一种解决方法。这种解决方法的最直接结果就是,当packet的输入速率达到了5000pps,随着输入速率的增加,转发性能维持在5000pps。
曲线后半部分的水平是一种完美的non-livelock性能曲线。之所以是水平的,是因为受CPU的限制,最多只能处理5000pps的转发。
在这个解决方案中,还是存在处理packet的线程和中断处理程序。当网卡第一次触发中断时,会导致中断处理函数的运行。但是中断处理函数并不会从网卡拷贝packet,相应的,它会唤醒处理packet的线程,并且关闭网卡的中断,这样接下来就收不到任何中断了。处理packet的线程会有一个循环,在循环中它会检查并从网卡拉取几个packet,论文中我记得是最多拉取5个packet,之后再处理这些packet。所以现在处理packet的线程是从网卡读取packet,而不是从中断处理程序读取。如果网卡中没有等待处理的packet,那么处理线程会重新打开网卡中断,并进入sleep状态。因为最后打开了中断,当下一个packet到达时,中断处理程序会唤醒处理packet线程,线程会从sleep状态苏醒并继续处理packet。这就是论文介绍的解决Livelock的方法。
这里的处理方式实际上是将中断模式(Interrupt Scheme)转变成了轮询模式(Polling Scheme)。在高负载的情况下,中断会被关闭,并且CPU会一直运行这里的循环中,不断读取packet并处理packet。因为中断被关闭了,CPU用来运行主线程的时间不会被中断占据。在低负载的情况下,中断会被打开,在收到packet之后,线程会被中断处理程序直接唤醒。
这里的循环会检查所有的设备吗?还是只会检查产生中断的设备?
当处理线程运行的时候,packet是如何进入到一个等待读取的队列中?我觉得网卡上只会有一个packet。
所以一次可以拷贝多个packet?
但是这就要求提升网卡的内存容量了吧?
当网卡中断被关闭了,网卡还能在自己的buffer上加入新的packet吗?
有没有这种可能,CPU从网卡读取packet,但是处理线程内部的队列满了?