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

1、中国科学技术大学软件学院Libnids在商用多核系统上的并行化详细设计说明书V1.0小组名称： Casual指导教师： 郭燕文档撰写人：柴泉文档撰写时间：2013.5.17团队分工记录表名中文Libnids 在商用多核系统上的并行化称英文The Libnids parallelized on commercial multicore systems姓名学号项目中的分工签章张悦SA12226141CPU 与线程的绑定，内存预分配项柴泉SG12225038Tcpreply 获取数据包，文档, 并行后程目序性能测试组SA12225118成李曦源码分析，并行后程序性能测试员hash 负载均衡， opr

2、ofile 工具查找程序名刘宇SA12226129单瓶颈冯铮SA12226330无锁队列实现， 多线程实现并行，全局变量本地化第1页/总17页中国科学技术大学软件学院目录1引言.31.1编写目的 .31.2项目背景 .31.3定义 .31.4参考资料 .42总体设计 .52.1需求概述 .52.2软件结构 .53功能实现说明 .63.1多核包处理平台实现 .63.2.1单片多处理体结构 .63.2.2PTHREAD 应用框架 .63.2并发无锁队列（ FIFO） .73.3子线程创建及功能绑定 .123.4 Hash算法选择 .133.5全局变量的局部化 .153.6接口 .163.7测试要点

3、 .17第2页/总17页中国科学技术大学软件学院1引言1.1 编写目的基于多核系统的广泛普及，现在的企业把越来越多的目光投入到并行程序的开发。基于语法和语义对于应用程序的分析，成为解析网络数据包的重要手段和要求。但是，应用现在的分析数据包技术期望满足现在的高速网络(10Gbps+) 是很困难的。我们面临的困难很多，下面列出其中几项。第一，现在的网速很快，硬件用以支持频繁的通信和同步的需求已经赶不上网络速度的提高速度了；第二，现存的顺序应用分析技术几乎不可能进行复用。 在工程实践的阶段，我们将基于多核平台， 提出一个尽可能高效并且通用的并行应用协议的分析器。 为了实现在多核体系上的流水线技术，需

4、要评估不同并行处理核之间的权衡取舍， 包括不同处理核之间的负载均衡和数据局域性之间的取舍，以及通用加减锁机制和特定不加锁数据结构的取舍。基于多核体系的高效率网络应用程序的解析的实现依赖于以下几个方面：连接亲和性和无锁设计原则。它们的使用使得在数据局域性和核- 核之间的快速通信和同步之间找到一个最佳的均衡点；基于以上的并行技术的使用。我们的分析速度可以提高很多倍，例如，对于一般的HTTP数据包的分析可以达到20Gdps，而且，就算是很小的 FIX 数据包，它的分析速度可以达到5Gbps 的水平。1.2 项目背景名称：网络应用在商用多核体系上的并行化项目开发者：张悦，柴泉，李曦，刘宇系统应用范围：

5、 本项目可以对网络上的数据包进行详细的深层分析，从而可以应用于企业、银行、教育、医疗、政府的信息安全和数据防盗上系统用户：在多核体系下使用网络应用的相关人员1.3 定义Libnids ： Library Network Intrusion Detection SystemCLF ： concurrent-lock-freeLibpcap ：网络抓包工具Libnet ：数据包构造和发送Oprofile:性能分析工具Tcpreplay ：数据包播放分析工具第3页/总17页中国科学技术大学软件学院1.4 参考资料1 Daniel P.Bovet. Understanding the linux ke

6、rnelM.中国电力出版社, 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 Paral

7、lelizing 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

8、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 ofAdversariesConference: USENIX Security Symposium C. 200510 Mark Hand

9、ley, Vern Paxson, Christian Kreibich. Network Intrusion Detection: Evasion, Traffic Normalization, and End-to-End Protocol Semantics Conference: USENIX Security SymposiumC. 200111 John Giacomoni, Tipp Moseley, Manish Vachharajani. FastForward for efficient pipeline parallelism: a cache-optimized con

10、current lock-free queue Conference: Principles and Practice of Parallel Programming - PPoPPC. 200812 Chuck Lever, David Boreham. Malloc() Performance in a Multithreaded Linux Environment.Conference: USENIX Technical Conference - USENIXC. 200013 Martin Labrecque, J. Gregory Steffan. The case for hard

11、ware transactional memory in software packet processing. Conference: Architecture for Networking and Communications Systems - ANCSC. 201014 Gao Xia, Bin Liuy. Accelerating network applications on X86-64 platformsConference: International Symposium on Computers and Communications - ISCCC . 201015 Zhe

12、ng 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. 201016 Bo Hong A lock-free multi-threaded algorithm for the maximum flow problem. Conference: International Pa

13、rallel and Distributed Processing Symposium/International Parallel第4页/总17页中国科学技术大学软件学院Processing Symposium - IPDPS(IPPS)C. 20082总体设计2.1 需求概述市场需求： 多核技术是未来处理器发展的主要趋势，得益于更高的通信带宽和更短的通信时延， 多核处理器在并行方面有着很大的优势。随着网络传输速度的提高，以及用户对网络应用的需求不断提升， 对网络数据处理速度的要求更高， 硬件用以支持频繁的通信和同步的需求已经赶不上网络速度的提高速度。提高网络应用在多核体系上的并行化已经迫在

14、眉睫，石油开采、气象探测等具有海量数据行业的需求尤为巨大。功能需求： 利用通用多核平台，通过网络包处理分段、局部并行化等方法，对某些网络应用的数据实现高速并行处理，着重在多核体系上开发一个能够并行的网络应用。2.2 软件结构1） 该并行平台能够提供一个接受数据输入的接口，接受来自网络应用的数据流，并进行简单的预处理，如包分析，以确定某个链接的包应该分配到哪个CPU、数据包的校验等等；2） 经过IP（Input ）处理后的数据传入AP（ Application ）进行数据的并行处理，包括FIFO 队列，与网络应用链接的建立，数据的处理，以及最后的Parser 的分析；3） 经过 AP 处理过的数

15、据将最终汇入OP（ Output ） ，然后由OP 做最后处理，再将数据送给相应网络应用。P1 用于接收输入的信息，P2、 P3、 P4、 P5、P6、 P7 用于对数据包进行处理，P8 用第5页/总17页中国科学技术大学软件学院于接收处理后的信息，并且提交给用户。3功能实现说明3.1 多核包处理平台实现3.2.1单片多处理体结构在此种体系结构下，不同的线程可以运行于不同的CPU 内核中，他们拥有各自独立的 cache，这样并行化程度就会相当高，所以可以根据工作量均衡的特定，尽可能有效率的将算法并行化。3.2.2PTHREAD应用框架POSIXthread 简称为 pthread， Posix

16、 线程是一个POSIX 标准线程 .该标准定义内部API创建和操纵线程。pthread 定义了一套C 程序语言类型、函数与常量，以pthread.h 头文件和一个线程库实现。所谓最简单的多线程编程，就是通过pthread_create， pthread_join ，pthread_exit 3 个 api实现线程的创建与终止，而创建的线程只做些简单的工作，如printf 一些文字信息。使用 pthread_create， pthread_join ， pthread_exit 进行多线程编程的模型如下图所示：第6页/总17页中国科学技术大学软件学院一个典型的pthread 多线程框架如下：vo

17、id *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）首先，假设我们有两个核， 每个核上分别运行着读线程和写线程就很容易出现下面这种情况 :第7页/总17页中国科学技术大学软件学院正如上图 core1 运行 Thread0 假设为 rea

18、der， core2 上运行着 writer ，而且每个核有自己的 cache。这里我们画的只是示意图， 假设 cache line 的大小为 8 个单元。 当 reader 访问某个内存单元的时候， 首先会到 cache 里面找， 看看这个内存单元是否在 cache 中。如果在 cache中，这就是我们经常说的缓存命中(hit), 否则称为不命中（miss） ,那么这个时候就会把所访问那个内存单元所在的那个cache line 拷贝到内存。这里要说明的是主存和cache 之间的传输单位是一个cache line 。然后如果writer 也要访问刚才reader 所访问的内存单元，同样也会发生

19、上述情况。最终就会出现上图所示的格局，内存中的同一个cache line 大小的数据会被同时加载到不同的核的cache 中。所以在更新的时候,为了保持数据的一致性, core 之间cache 要进行同步 , 这个会导致严重的性能问题. 这就是所谓的False sharing 问题 ,所以在 FastForward 的 fifo 中有一个动态调整 “距离”的过程，尽量使得 reader 和 writer 访问不同的 cache line，但是这个算法不是很稳定。为了改进这个问题，就有了我们整天讨论的读写汇聚的fifo 。在读写汇聚的fifo 中通过引入一个cache line 大小的 temp

20、数组，起到一个过渡作用，就可以有效的避免false sharing 问题，而且相比起来更稳定。我们基于这样一个观察，就是说数据项先写入temp 数组，然后又将数据从temp 数组拷贝到队列中。我们改进的重点就是避免使用 temp 数组这个过渡直接将数据拷贝到 queue中，同样避免 false sharing 问题。我们采用用了一种很奇怪的“对齐转移”策略，首先要说明的是我们所用的linux 操作系统的 cache line 大小是 64 字节，这个可以用过命令来查看。为了描述起来更为简单，假设就以 int 类型数据为例(sizeof(int) = 4).内存是以64 的倍数分成了若干个以ca

21、che line 为大小的块（ cacheline），如下图所示：第8页/总17页中国科学技术大学软件学院Item1，item2 是同属于一个 cacheline 的。当访问 item1 的时候装入 cache 的 cacheline 是图上我标识灰色的部分， 访问 item2 装入 cache 的 cacheline 同样灰色部分。 我们的做法就是让我的 fifo 的起始地址往前偏移一个 item，如下图所示：下面开始叙述如何进行读写FIFO ，假设刚开始的时候队列为空，reader 开始访问fifohead( 此时 reader 要把 fifohead 所在的 cacheline 载入到r

22、eader 所在核的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

23、+ 1) 这个范围的 cacheline(block 中出去首个元素以外的其他元素 )，这个时候该范围的 cacheline 同样会被载入到 cache 中，当我们写完第十五个元素并不继续写第十六个元素此时的内存格局是这个样子：第9页/总17页中国科学技术大学软件学院我们接着写的是fifohead, 写完之后是这个样子的：这个时候标识灰色单元的数据还是NULL 。接着 writer 开始写范围是64(n + 1), 64(n + 2) 的这个 cacheline，当写完十五个元素的时候再转移回来将上图中标识灰色部分写上数据，如此重复 下面我们再从reader 的角度来分析一下，当fifohea

24、d ，准确是说刚开始是fifo0 被写上数据之后reader 就可以读数据了，但是这个时候reader 开始读的是 64n, 64(n + 1)这个cacheline 中的数据， 同样这个 cacheline 会被一次性的加载到reader 的 cache 中，接着 reader读取十五个元素同样剩下一个，然后转移到head0 进行数据读取。紧接着检查刚才那个cacheline 中第 16 个位置的元素是否为空，根据检查结果进行判断是否进行下一个block 的读操作， 同样是先读下一个cacheline 的前 15 个元素然后转移回来读刚才所谓检查位的那个位置的数据。这样如此反复，能保证rea

25、der 和 writer 在大部分时候访问不同的cacheline 上的元素，在读写一个cacheline 的 16 个元素的过程中仅有一次访问同一个cacheline 中的元素。由于在硬件上没有提供核之间高速共享数据的方式 （此处指 FIFO ），因此本部分的 FIFO 设计是为了实现相邻核之间的高效通信。在我们的并行化 Libnids 版本中，对这种无锁的队列很好的实现了，队列实现核心代码如下。struct FIFO_nodeu_char * data;int skblen;第10页/总17页中国科学技术大学软件学院int need_free;/declare fifo datastruc

26、tureint headFIFO_max_num;/ allocate one tail cursor and one head cursor for each thread int 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.

27、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 ， retur

28、n 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;第11页/总17页中国科学技术大学软件学院int dequeue(struct FIFO_node *pnode,struct FIFO_node *FIFO_instance,int *tail)*pnode=FIFO_instance*tail;/get current tail nodeif(*pnode).data=NULL)ret

29、urn 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 cursor return 0;3.3 子线程创建及功能绑定按照前文所提及的pthread 模型，我们为Libnids 加入了多个线程执行不同的工作，其中为每个执行AP 工作的线程分发一个队列，由执行IP 工作的线程执行分

30、发工作，再将线程绑定到核，于是有线程模型如下：thread1Pthread_createthread2Pthread_joinMain_threadMain_threadthread3thread.thread n有了这个线程模型，我们给每个线程赋予相应的功能，并将实现了的FIFO 队列插入该线程模型，就得到了我们整个并行化程序的逻辑模型，如下图所示：FIFO1AP thread1myhashFIFO2AP thread2Pthread_joinIP_threadFIFO3AP thread3OP_threadFIFO.AP thread.FIFOnAP thread n上图说明了我们整个程序

31、的逻辑，首先主线程通过调用pthread 接口，创建子线程，然第12页/总17页中国科学技术大学软件学院后主线程去执行IP 逻辑，即抓包，进行IP 重组然后均匀的hash 到每个 FIFO 队列中，被创建的子线程从自己的FIFO 中取出数据，执行之后的代码逻辑，另外application 程序也是在每个 AP 线程中完成的，当所有的AP 线程完成自身工作时，会将结果在OP 线程汇总（在我们的并行化代码中没有设计该类线程逻辑） 。当然在我们的代码中，线程是需要绑定到核的，所以每一个 IP 和 AP 线程最终会对应到不同分工的核中。以下是创建线程部分的核心代码部分：CPU_ZERO(&mask);

32、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_dispatc

33、her,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_in

34、t16_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

35、_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;第15页/总17页中国科学技术大学软件学院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，实则标识一个线程。我