Libnids在商用多核系统上的并行化详细设计说明书.doc

中国科学技术大学 软件学院Libnids在商用多核系统上的并行化详细设计说明书V1.0小组名称：Casual指导教师：郭燕文档撰写人：柴泉文档撰写时间：2013.5.17团队分工记录表名称中文Libnids在商用多核系统上的并行化英文The Libnids parallelized on commercial multicore systems项目组成员名单姓名学号项目中的分工签 章张悦SA12226141CPU与线程的绑定，内存预分配柴泉SG12225038Tcpreply获取数据包，文档, 并行后程序性能测试李曦SA12225118源码分析，并行后程序性能测试刘宇SA12226129hash负载均衡，oprofile工具查找程序瓶颈冯铮SA12226330无锁队列实现，多线程实现并行，全局变量本地化目录1引言31.1编写目的31.2项目背景31.3定义31.4参考资料42总体设计52.1需求概述52.2软件结构53功能实现说明63.1多核包处理平台实现63.2.1 单片多处理体结构63.2.2 PTHREAD应用框架63.2并发无锁队列（FIFO）73.3子线程创建及功能绑定123.4 Hash算法选择133.5全局变量的局部化153.6接口163.7测试要点171引言1.1编写目的基于多核系统的广泛普及，现在的企业把越来越多的目光投入到并行程序的开发。基于语法和语义对于应用程序的分析，成为解析网络数据包的重要手段和要求。但是，应用现在的分析数据包技术期望满足现在的高速网络(10Gbps+)是很困难的。我们面临的困难很多，下面列出其中几项。第一，现在的网速很快，硬件用以支持频繁的通信和同步的需求已经赶不上网络速度的提高速度了；第二，现存的顺序应用分析技术几乎不可能进行复用。在工程实践的阶段，我们将基于多核平台，提出一个尽可能高效并且通用的并行应用协议的分析器。为了实现在多核体系上的流水线技术，需要评估不同并行处理核之间的权衡取舍，包括不同处理核之间的负载均衡和数据局域性之间的取舍，以及通用加减锁机制和特定不加锁数据结构的取舍。基于多核体系的高效率网络应用程序的解析的实现依赖于以下几个方面：连接亲和性和无锁设计原则。它们的使用使得在数据局域性和核-核之间的快速通信和同步之间找到一个最佳的均衡点；基于以上的并行技术的使用。我们的分析速度可以提高很多倍，例如，对于一般的HTTP数据包的分析可以达到20Gdps，而且，就算是很小的FIX数据包，它的分析速度可以达到5Gbps的水平。1.2项目背景名称：网络应用在商用多核体系上的并行化项目开发者：张悦，柴泉，李曦，刘宇系统应用范围： 本项目可以对网络上的数据包进行详细的深层分析，从而可以应用于企业、银行、教育、医疗、政府的信息安全和数据防盗上系统用户：在多核体系下使用网络应用的相关人员1.3定义Libnids：Library Network Intrusion Detection SystemCLF： concurrent-lock-freeLibpcap：网络抓包工具Libnet：数据包构造和发送Oprofile: 性能分析工具Tcpreplay：数据包播放分析工具1.4参考资料1 Daniel P.Bovet. Understanding the linux kernelM.中国电力出版社, 2009.07.2 W.Richard Stevens. Unix网络环境编程卷一.套接字APIM. 人民邮电出版社, 2011.5.3 W.Richard Stevens. Unix网络环境编程卷二.进程间通信M. 人民邮电出版社, 2011.11.4 W.Richard Stevens. Unix环境高级编程M. 人民邮电出版社. 2011.11.5 刘文涛. 网络安全开发包详解M. 机械工业出版社. 2008.06.6 Junchang Wang, Haipeng Cheng, Bei Hua. Practice of Parallelizing Network Applications on Multi-core Architectures. ICS.20097 Kai Zhang, Junchang Wang, Bei Hua, Xinan Tang. Building High-performance Application Protocol Parsers on Multi-core Architectures. IEEEJ. 2010.8 Robin Sommer, Vern Paxson, Nicholas Weaver. An architecture for exploiting multi-core processors to parallelize network intrusion prevention Journal: Concurrency and Computation: Practice and Experience - CONCURRENCY , vol. 21C. 2009.9 Sarang Dharmapurikar, Vern Paxson. Robust TCP Stream Reassembly in the Presence of Adversaries Conference: USENIX Security Symposium C. 2005 10 Mark Handley, Vern Paxson, Christian Kreibich. Network Intrusion Detection: Evasion, Traffic Normalization, and End-to-End Protocol Semantics Conference: USENIX Security SymposiumC. 2001 11 John Giacomoni, Tipp Moseley, Manish Vachharajani. FastForward for efficient pipeline parallelism: a cache-optimized concurrent lock-free queue Conference: Principles and Practice of Parallel Programming - PPoPPC. 2008 12 Chuck Lever, David Boreham. Malloc() Performance in a Multithreaded Linux Environment. Conference: USENIX Technical Conference - USENIXC. 2000 13 Martin Labrecque, J. Gregory Steffan. The case for hardware transactional memory in software packet processing. Conference: Architecture for Networking and Communications Systems - ANCSC. 2010 14 Gao Xia, Bin Liuy. Accelerating network applications on X86-64 platformsConference: International Symposium on Computers and Communications - ISCCC . 2010 15 Zheng Li, Nenghai Yu, Zhuo Hao. A Novel Parallel Traffic Control Mechanism for Cloud Computing. Conference: IEEE International Conference on Cloud Computing Technology and Science - CloudComC. 2010 16 Bo Hong A lock-free multi-threaded algorithm for the maximum flow problem. Conference: International Parallel and Distributed Processing Symposium/International Parallel Processing Symposium - IPDPS(IPPS)C. 20082总体设计2.1需求概述市场需求：多核技术是未来处理器发展的主要趋势，得益于更高的通信带宽和更短的通信时延，多核处理器在并行方面有着很大的优势。随着网络传输速度的提高，以及用户对网络应用的需求不断提升，对网络数据处理速度的要求更高，硬件用以支持频繁的通信和同步的需求已经赶不上网络速度的提高速度。提高网络应用在多核体系上的并行化已经迫在眉睫，石油开采、气象探测等具有海量数据行业的需求尤为巨大。功能需求：利用通用多核平台，通过网络包处理分段、局部并行化等方法，对某些网络应用的数据实现高速并行处理，着重在多核体系上开发一个能够并行的网络应用。2.2软件结构1） 该并行平台能够提供一个接受数据输入的接口，接受来自网络应用的数据流，并进行简单的预处理，如包分析，以确定某个链接的包应该分配到哪个 CPU、数据包的校验等等； 2） 经过 IP（Input）处理后的数据传入 AP（Application）进行数据的并行处理，包括 FIFO 队列，与网络应用链接的建立，数据的处理，以及最后的 Parser 的分析； 3） 经过 AP 处理过的数据将最终汇入 OP（Output） ，然后由 OP 做最后处理，再将数据送给相应网络应用。P1用于接收输入的信息，P2、 P3、 P4、P5、P6、P7用于对数据包进行处理，P8用于接收处理后的信息，并且提交给用户。3功能实现说明3.1多核包处理平台实现3.2.1 单片多处理体结构在此种体系结构下，不同的线程可以运行于不同的CPU内核中，他们拥有各自独立的cache，这样并行化程度就会相当高，所以可以根据工作量均衡的特定，尽可能有效率的将算法并行化。3.2.2 PTHREAD应用框架POSIX thread简称为pthread，Posix线程是一个POSIX标准线程.该标准定义内部API创建和操纵线程。pthread定义了一套 C程序语言类型、函数与常量，以 pthread.h 头文件和一个线程库实现。所谓最简单的多线程编程，就是通过pthread_create，pthread_join，pthread_exit 3个api实现线程的创建与终止，而创建的线程只做些简单的工作，如printf一些文字信息。使用pthread_create，pthread_join，pthread_exit 进行多线程编程的模型如下图所示：一个典型的pthread多线程框架如下：void *hello_world_thread(void *arg) printf(pthreads Hello World!n); pthread_exit(NULL); return NULL;int main()pthread_create(&threadsi, NULL,hello_world_thread, NULL);pthread_join(threadsi, NULL);3.2并发无锁队列（FIFO）首先，假设我们有两个核，每个核上分别运行着读线程和写线程就很容易出现下面这种情况:正如上图core1运行Thread0假设为reader，core2上运行着writer，而且每个核有自己的cache。这里我们画的只是示意图，假设cache line的大小为8个单元。当reader访问某个内存单元的时候，首先会到cache里面找，看看这个内存单元是否在cache中。如果在cache中，这就是我们经常说的缓存命中(hit),否则称为不命中（miss）,那么这个时候就会把所访问那个内存单元所在的那个cache line 拷贝到内存。这里要说明的是主存和cache之间的传输单位是一个cache line。然后如果writer也要访问刚才reader所访问的内存单元，同样也会发生上述情况。最终就会出现上图所示的格局，内存中的同一个cache line 大小的数据会被同时加载到不同的核的cache中。所以在更新的时候,为了保持数据的一致性, core之间cache要进行同步, 这个会导致严重的性能问题. 这就是所谓的False sharing问题, 所以在FastForward的fifo中有一个动态调整“距离”的过程，尽量使得reader和writer访问不同的cache line，但是这个算法不是很稳定。为了改进这个问题，就有了我们整天讨论的读写汇聚的fifo。在读写汇聚的fifo中通过引入一个cache line大小的temp数组，起到一个过渡作用，就可以有效的避免false sharing问题，而且相比起来更稳定。我们基于这样一个观察，就是说数据项先写入temp数组，然后又将数据从temp数组拷贝到队列中。Data temp queue我们改进的重点就是避免使用temp数组这个过渡直接将数据拷贝到queue中，同样避免false sharing问题。我们采用用了一种很奇怪的“对齐转移”策略，首先要说明的是我们所用的linux操作系统的cache line大小是64字节，这个可以用过命令来查看。为了描述起来更为简单，假设就以int类型数据为例(sizeof(int) = 4). 内存是以64的倍数分成了若干个以cache line为大小的块（cacheline），如下图所示： Item1，item2是同属于一个cacheline的。当访问item1的时候装入cache的cacheline是图上我标识灰色的部分，访问item2装入cache的cacheline同样灰色部分。我们的做法就是让我的fifo的起始地址往前偏移一个item，如下图所示：下面开始叙述如何进行读写FIFO，假设刚开始的时候队列为空，reader开始访问fifohead(此时reader要把fifohead所在的cacheline载入到reader所在核的cache中),发现fifohead = NULL ; reader要等待writer写入（循环检查fifohead），这里强调一下fifohead所在的cacheline范围是64(n - 1), 64n)左闭右开区间，下同。writer开始写fifo时,发现fifohead = NULL,说明其后的block可写。这个时候fifohead所在的cacheline范围也是64(n - 1), 64n)也会被加载到writer所在核的cache中，这个时候writer并不直接写fifohead这个位置，而是先写64n, 64(n + 1)这个范围的cacheline(block中出去首个元素以外的其他元素)，这个时候该范围的cacheline同样会被载入到cache中，当我们写完第十五个元素并不继续写第十六个元素此时的内存格局是这个样子：我们接着写的是fifohead,写完之后是这个样子的：这个时候标识灰色单元的数据还是NULL。接着writer开始写范围是64(n + 1), 64(n + 2)的这个cacheline，当写完十五个元素的时候再转移回来将上图中标识灰色部分写上数据，如此重复下面我们再从reader的角度来分析一下，当fifohead，准确是说刚开始是fifo0被写上数据之后reader就可以读数据了，但是这个时候reader开始读的是64n, 64(n + 1)这个cacheline中的数据，同样这个cacheline会被一次性的加载到reader的cache中，接着reader读取十五个元素同样剩下一个，然后转移到head0进行数据读取。紧接着检查刚才那个cacheline中第16个位置的元素是否为空，根据检查结果进行判断是否进行下一个block的读操作，同样是先读下一个cacheline的前15个元素然后转移回来读刚才所谓检查位的那个位置的数据。这样如此反复，能保证reader和writer在大部分时候访问不同的cacheline上的元素，在读写一个cacheline的16个元素的过程中仅有一次访问同一个cacheline中的元素。由于在硬件上没有提供核之间高速共享数据的方式（此处指FIFO），因此本部分的FIFO设计是为了实现相邻核之间的高效通信。在我们的并行化Libnids版本中，对这种无锁的队列很好的实现了，队列实现核心代码如下。struct FIFO_nodeu_char * data;int skblen;int need_free;/declare fifo datastructureint headFIFO_max_num;/ allocate one tail cursor and one head cursor for each threadint tailFIFO_max_num;int FIFO_init()int i,j;/init FIFO data pointer equal to null and datalen equal to zerofor(i=0;iFIFO_max_num;i+)for(j=0;jS_FIFO_max_size;j+)the_FIFOij.data=NULL;the_FIFOij.skblen=0;the_FIFOij.need_free=0;for(j=0;jCACHELINE_SIZE;j+)cBufferij.data=NULL;cBufferij.need_free=0;cBufferij.skblen=0;headi=0;taili=0;timestpi=0;currenti=0;int enqueue(struct FIFO_node data,struct FIFO_node *FIFO_instance,int *head)if(FIFO_instance*head.data!=NULL)return 1;/there is an element so we need wait，return 1FIFO_instance*head=data;/ the fifo is not full,we could add this element to the fifo*head=(*head+1)%S_FIFO_max_size;return 0;int dequeue(struct FIFO_node *pnode,struct FIFO_node *FIFO_instance,int *tail)*pnode=FIFO_instance*tail;/get current tail nodeif(*pnode).data=NULL)return 1;/if data pointer point to null means there is nothing we need to waitFIFO_instance*tail.data=NULL;/else we need reset this pointer to null*tail=(*tail+1)%S_FIFO_max_size;/reset tail cursorreturn 0;3.3子线程创建及功能绑定按照前文所提及的pthread模型，我们为Libnids加入了多个线程执行不同的工作，其中为每个执行AP工作的线程分发一个队列，由执行IP工作的线程执行分发工作，再将线程绑定到核，于是有线程模型如下：有了这个线程模型，我们给每个线程赋予相应的功能，并将实现了的FIFO队列插入该线程模型，就得到了我们整个并行化程序的逻辑模型，如下图所示：上图说明了我们整个程序的逻辑，首先主线程通过调用pthread接口，创建子线程，然后主线程去执行IP逻辑，即抓包，进行IP重组然后均匀的hash到每个FIFO队列中，被创建的子线程从自己的FIFO中取出数据，执行之后的代码逻辑，另外application程序也是在每个AP线程中完成的，当所有的AP线程完成自身工作时，会将结果在OP线程汇总（在我们的并行化代码中没有设计该类线程逻辑）。当然在我们的代码中，线程是需要绑定到核的，所以每一个IP和AP线程最终会对应到不同分工的核中。以下是创建线程部分的核心代码部分：CPU_ZERO(&mask);CPU_SET(cpu_num-1, &mask);/bind thread to cpu coreerr=pthread_create(&tip_id,NULL,input_dispatcher,NULL);if(err!=0)printf(create false in dispatcher.);if (pthread_setaffinity_np(tip_id, sizeof(mask), &mask) 0) fprintf(stderr, set thread affinity failedn);err=pthread_create(&tip_id,NULL,input_dispatcher,NULL);START_CAP_QUEUE_PROCESS_THREAD();for(i=0;icpu_num-1;i+)int temp=i;err=pthread_create(&tap_idtemp,NULL,highlevel_process,(void *)temp);if(err!=0)printf(create false in dispatcher.);CPU_ZERO(&mask);CPU_SET(i, &mask);if (pthread_setaffinity_np(pthread_self(), sizeof(mask), &mask) ip_hl); u_int16_t temp6,hash; int *ptr; int i; ptr=temp; *ptr+=this_iphdr-ip_src.s_addr; *ptr+=this_iphdr-ip_dst.s_addr; temp4=this_tcphdr-th_sport; temp5=this_tcphdr-th_dport; for(i=1,hash=temp0;itv_sec timeout.tv_sec) return; to-a_tcp-nids_state = NIDS_TIMED_OUT; for (i = to-a_tcp-listeners; i; i = i-next) (i-item) (to-a_tcp, &i-data); next = to-next; nids_free_tcp_stream(to-a_tcp); /局部化之后的代码voidtcp_check_timeouts(struct timeval *now,int FIFO_NO) struct tcp_timeout *to; struct tcp_timeout *next; struct lurker_node *i; for (to = nids_tcp_timeoutsFIFO_NO; to; to = next) if (now-tv_sec timeout.tv_sec) return; to-a_tcp-nids_state = NIDS_TIMED_OUT; for (i = to-a_tcp-listeners; i; i = i-next) (i-item) (to-a_tcp, &i-data,FIFO_NO); next = to-next; nids_free_tcp_stream(to-a_tcp,FIFO_NO); 两段代码做了鲜明的对比。未改进的代码，直接使用全局变量，会出现竞争条件，导致程序不正确，我们改进后的代码加入了FIFO_NO，实则标识一个线程。我们事先分配了一个全局的数组，通过不同的队列号