Libnids在商用多核系統(tǒng)上的并行化詳細設計說明書

1、中國科學技術大學軟件學院Libnids在商用多核系統(tǒng)上的并行化詳細設計說明書V1.0小組名稱： Casual指導教師： 郭燕文檔撰寫人：柴泉文檔撰寫時間：2013.5.17團隊分工記錄表名中文Libnids 在商用多核系統(tǒng)上的并行化稱英文The Libnids parallelized on commercial multicore systems姓名學號項目中的分工簽章張悅SA12226141CPU 與線程的綁定，內存預分配項柴泉SG12225038Tcpreply 獲取數(shù)據(jù)包，文檔, 并行后程目序性能測試組SA12225118成李曦源碼分析，并行后程序性能測試員hash 負載均衡， opr

2、ofile 工具查找程序名劉宇SA12226129單瓶頸馮錚SA12226330無鎖隊列實現(xiàn)， 多線程實現(xiàn)并行，全局變量本地化第1頁/總17頁中國科學技術大學軟件學院目錄1引言.31.1編寫目的 .31.2項目背景 .31.3定義 .31.4參考資料 .42總體設計 .52.1需求概述 .52.2軟件結構 .53功能實現(xiàn)說明 .63.1多核包處理平臺實現(xiàn) .63.2.1單片多處理體結構 .63.2.2PTHREAD 應用框架 .63.2并發(fā)無鎖隊列（ FIFO） .73.3子線程創(chuàng)建及功能綁定 .123.4 Hash算法選擇 .133.5全局變量的局部化 .153.6接口 .163.7測試要點

3、 .17第2頁/總17頁中國科學技術大學軟件學院1引言1.1 編寫目的基于多核系統(tǒng)的廣泛普及，現(xiàn)在的企業(yè)把越來越多的目光投入到并行程序的開發(fā)。基于語法和語義對于應用程序的分析，成為解析網(wǎng)絡數(shù)據(jù)包的重要手段和要求。但是，應用現(xiàn)在的分析數(shù)據(jù)包技術期望滿足現(xiàn)在的高速網(wǎng)絡(10Gbps+) 是很困難的。我們面臨的困難很多，下面列出其中幾項。第一，現(xiàn)在的網(wǎng)速很快，硬件用以支持頻繁的通信和同步的需求已經(jīng)趕不上網(wǎng)絡速度的提高速度了；第二，現(xiàn)存的順序應用分析技術幾乎不可能進行復用。 在工程實踐的階段，我們將基于多核平臺， 提出一個盡可能高效并且通用的并行應用協(xié)議的分析器。 為了實現(xiàn)在多核體系上的流水線技術，需

4、要評估不同并行處理核之間的權衡取舍， 包括不同處理核之間的負載均衡和數(shù)據(jù)局域性之間的取舍，以及通用加減鎖機制和特定不加鎖數(shù)據(jù)結構的取舍?；诙嗪梭w系的高效率網(wǎng)絡應用程序的解析的實現(xiàn)依賴于以下幾個方面：連接親和性和無鎖設計原則。它們的使用使得在數(shù)據(jù)局域性和核- 核之間的快速通信和同步之間找到一個最佳的均衡點；基于以上的并行技術的使用。我們的分析速度可以提高很多倍，例如，對于一般的HTTP數(shù)據(jù)包的分析可以達到20Gdps，而且，就算是很小的 FIX 數(shù)據(jù)包，它的分析速度可以達到5Gbps 的水平。1.2 項目背景名稱：網(wǎng)絡應用在商用多核體系上的并行化項目開發(fā)者：張悅，柴泉，李曦，劉宇系統(tǒng)應用范圍：

5、 本項目可以對網(wǎng)絡上的數(shù)據(jù)包進行詳細的深層分析，從而可以應用于企業(yè)、銀行、教育、醫(yī)療、政府的信息安全和數(shù)據(jù)防盜上系統(tǒng)用戶：在多核體系下使用網(wǎng)絡應用的相關人員1.3 定義Libnids ： Library Network Intrusion Detection SystemCLF ： concurrent-lock-freeLibpcap ：網(wǎng)絡抓包工具Libnet ：數(shù)據(jù)包構造和發(fā)送Oprofile:性能分析工具Tcpreplay ：數(shù)據(jù)包播放分析工具第3頁/總17頁中國科學技術大學軟件學院1.4 參考資料1 Daniel P.Bovet. Understanding the linux ke

6、rnelM.中國電力出版社, 2009.07.2 W.Richard Stevens. Unix 網(wǎng)絡環(huán)境編程卷一 . 套接字 APIM. 人民郵電出版社 ,2011.5.3 W.Richard Stevens. Unix 網(wǎng)絡環(huán)境編程卷二 . 進程間通信 M. 人民郵電出版社 ,2011.11.4 W.Richard Stevens. Unix 環(huán)境高級編程 M. 人民郵電出版社 . 2011.11.5 劉文濤 . 網(wǎng)絡安全開發(fā)包詳解 M. 機械工業(yè)出版社 . 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 需求概述市場需求： 多核技術是未來處理器發(fā)展的主要趨勢，得益于更高的通信帶寬和更短的通信時延， 多核處理器在并行方面有著很大的優(yōu)勢。隨著網(wǎng)絡傳輸速度的提高，以及用戶對網(wǎng)絡應用的需求不斷提升， 對網(wǎng)絡數(shù)據(jù)處理速度的要求更高， 硬件用以支持頻繁的通信和同步的需求已經(jīng)趕不上網(wǎng)絡速度的提高速度。提高網(wǎng)絡應用在多核體系上的并行化已經(jīng)迫在

14、眉睫，石油開采、氣象探測等具有海量數(shù)據(jù)行業(yè)的需求尤為巨大。功能需求： 利用通用多核平臺，通過網(wǎng)絡包處理分段、局部并行化等方法，對某些網(wǎng)絡應用的數(shù)據(jù)實現(xiàn)高速并行處理，著重在多核體系上開發(fā)一個能夠并行的網(wǎng)絡應用。2.2 軟件結構1） 該并行平臺能夠提供一個接受數(shù)據(jù)輸入的接口，接受來自網(wǎng)絡應用的數(shù)據(jù)流，并進行簡單的預處理，如包分析，以確定某個鏈接的包應該分配到哪個CPU、數(shù)據(jù)包的校驗等等；2） 經(jīng)過IP（Input ）處理后的數(shù)據(jù)傳入AP（ Application ）進行數(shù)據(jù)的并行處理，包括FIFO 隊列，與網(wǎng)絡應用鏈接的建立，數(shù)據(jù)的處理，以及最后的Parser 的分析；3） 經(jīng)過 AP 處理過的數(shù)

15、據(jù)將最終匯入OP（ Output ） ，然后由OP 做最后處理，再將數(shù)據(jù)送給相應網(wǎng)絡應用。P1 用于接收輸入的信息，P2、 P3、 P4、 P5、P6、 P7 用于對數(shù)據(jù)包進行處理，P8 用第5頁/總17頁中國科學技術大學軟件學院于接收處理后的信息，并且提交給用戶。3功能實現(xiàn)說明3.1 多核包處理平臺實現(xiàn)3.2.1單片多處理體結構在此種體系結構下，不同的線程可以運行于不同的CPU 內核中，他們擁有各自獨立的 cache，這樣并行化程度就會相當高，所以可以根據(jù)工作量均衡的特定，盡可能有效率的將算法并行化。3.2.2PTHREAD應用框架POSIXthread 簡稱為 pthread， Posix

16、 線程是一個POSIX 標準線程 .該標準定義內部API創(chuàng)建和操縱線程。pthread 定義了一套C 程序語言類型、函數(shù)與常量，以pthread.h 頭文件和一個線程庫實現(xiàn)。所謂最簡單的多線程編程，就是通過pthread_create， pthread_join ，pthread_exit 3 個 api實現(xiàn)線程的創(chuàng)建與終止，而創(chuàng)建的線程只做些簡單的工作，如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 并發(fā)無鎖隊列（FIFO）首先，假設我們有兩個核， 每個核上分別運行著讀線程和寫線程就很容易出現(xiàn)下面這種情況 :第7頁/總17頁中國科學技術大學軟件學院正如上圖 core1 運行 Thread0 假設為 rea

18、der， core2 上運行著 writer ，而且每個核有自己的 cache。這里我們畫的只是示意圖， 假設 cache line 的大小為 8 個單元。 當 reader 訪問某個內存單元的時候， 首先會到 cache 里面找， 看看這個內存單元是否在 cache 中。如果在 cache中，這就是我們經(jīng)常說的緩存命中(hit), 否則稱為不命中（miss） ,那么這個時候就會把所訪問那個內存單元所在的那個cache line 拷貝到內存。這里要說明的是主存和cache 之間的傳輸單位是一個cache line 。然后如果writer 也要訪問剛才reader 所訪問的內存單元，同樣也會發(fā)生

19、上述情況。最終就會出現(xiàn)上圖所示的格局，內存中的同一個cache line 大小的數(shù)據(jù)會被同時加載到不同的核的cache 中。所以在更新的時候,為了保持數(shù)據(jù)的一致性, core 之間cache 要進行同步 , 這個會導致嚴重的性能問題. 這就是所謂的False sharing 問題 ,所以在 FastForward 的 fifo 中有一個動態(tài)調整 “距離”的過程，盡量使得 reader 和 writer 訪問不同的 cache line，但是這個算法不是很穩(wěn)定。為了改進這個問題，就有了我們整天討論的讀寫匯聚的fifo 。在讀寫匯聚的fifo 中通過引入一個cache line 大小的 temp

20、數(shù)組，起到一個過渡作用，就可以有效的避免false sharing 問題，而且相比起來更穩(wěn)定。我們基于這樣一個觀察，就是說數(shù)據(jù)項先寫入temp 數(shù)組，然后又將數(shù)據(jù)從temp 數(shù)組拷貝到隊列中。我們改進的重點就是避免使用 temp 數(shù)組這個過渡直接將數(shù)據(jù)拷貝到 queue中，同樣避免 false sharing 問題。我們采用用了一種很奇怪的“對齊轉移”策略，首先要說明的是我們所用的linux 操作系統(tǒng)的 cache line 大小是 64 字節(jié)，這個可以用過命令來查看。為了描述起來更為簡單，假設就以 int 類型數(shù)據(jù)為例(sizeof(int) = 4).內存是以64 的倍數(shù)分成了若干個以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 中 ),發(fā)現(xiàn)fifohead = NULL ; reader要等待 writer 寫入（循環(huán)檢查fifohead ），這里強調一下fifohead所在的 cacheline 范圍是 64(n - 1),64n)左閉右開區(qū)間，下同。writer 開始寫 fifo 時,發(fā)現(xiàn)fifohead= NULL, 說明其后的block 可寫。這個時候fifohead 所在的 cacheline 范圍也是64(n - 1), 64n)也會被加載到 writer 所在核的 cache中，這個時候 writer 并不直接寫 fifohead 這個位置，而是先寫 64n, 64(n

23、+ 1) 這個范圍的 cacheline(block 中出去首個元素以外的其他元素 )，這個時候該范圍的 cacheline 同樣會被載入到 cache 中，當我們寫完第十五個元素并不繼續(xù)寫第十六個元素此時的內存格局是這個樣子：第9頁/總17頁中國科學技術大學軟件學院我們接著寫的是fifohead, 寫完之后是這個樣子的：這個時候標識灰色單元的數(shù)據(jù)還是NULL 。接著 writer 開始寫范圍是64(n + 1), 64(n + 2) 的這個 cacheline，當寫完十五個元素的時候再轉移回來將上圖中標識灰色部分寫上數(shù)據(jù)，如此重復 下面我們再從reader 的角度來分析一下，當fifohea

24、d ，準確是說剛開始是fifo0 被寫上數(shù)據(jù)之后reader 就可以讀數(shù)據(jù)了，但是這個時候reader 開始讀的是 64n, 64(n + 1)這個cacheline 中的數(shù)據(jù)， 同樣這個 cacheline 會被一次性的加載到reader 的 cache 中，接著 reader讀取十五個元素同樣剩下一個，然后轉移到head0 進行數(shù)據(jù)讀取。緊接著檢查剛才那個cacheline 中第 16 個位置的元素是否為空，根據(jù)檢查結果進行判斷是否進行下一個block 的讀操作， 同樣是先讀下一個cacheline 的前 15 個元素然后轉移回來讀剛才所謂檢查位的那個位置的數(shù)據(jù)。這樣如此反復，能保證rea

25、der 和 writer 在大部分時候訪問不同的cacheline 上的元素，在讀寫一個cacheline 的 16 個元素的過程中僅有一次訪問同一個cacheline 中的元素。由于在硬件上沒有提供核之間高速共享數(shù)據(jù)的方式 （此處指 FIFO ），因此本部分的 FIFO 設計是為了實現(xiàn)相鄰核之間的高效通信。在我們的并行化 Libnids 版本中，對這種無鎖的隊列很好的實現(xiàn)了，隊列實現(xiàn)核心代碼如下。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 子線程創(chuàng)建及功能綁定按照前文所提及的pthread 模型，我們?yōu)長ibnids 加入了多個線程執(zhí)行不同的工作，其中為每個執(zhí)行AP 工作的線程分發(fā)一個隊列，由執(zhí)行IP 工作的線程執(zhí)行分

30、發(fā)工作，再將線程綁定到核，于是有線程模型如下：thread1Pthread_createthread2Pthread_joinMain_threadMain_threadthread3thread.thread n有了這個線程模型，我們給每個線程賦予相應的功能，并將實現(xiàn)了的FIFO 隊列插入該線程模型，就得到了我們整個并行化程序的邏輯模型，如下圖所示：FIFO1AP thread1myhashFIFO2AP thread2Pthread_joinIP_threadFIFO3AP thread3OP_threadFIFO.AP thread.FIFOnAP thread n上圖說明了我們整個程序

31、的邏輯，首先主線程通過調用pthread 接口，創(chuàng)建子線程，然第12頁/總17頁中國科學技術大學軟件學院后主線程去執(zhí)行IP 邏輯，即抓包，進行IP 重組然后均勻的hash 到每個 FIFO 隊列中，被創(chuàng)建的子線程從自己的FIFO 中取出數(shù)據(jù)，執(zhí)行之后的代碼邏輯，另外application 程序也是在每個 AP 線程中完成的，當所有的AP 線程完成自身工作時，會將結果在OP 線程匯總（在我們的并行化代碼中沒有設計該類線程邏輯） 。當然在我們的代碼中，線程是需要綁定到核的，所以每一個 IP 和 AP 線程最終會對應到不同分工的核中。以下是創(chuàng)建線程部分的核心代碼部分：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);兩段代碼做了鮮明的對比。未改進的代碼，直接使用全局變量，會出現(xiàn)競爭條件，導致程序不正確，我們改進后的代碼加入了FIFO_NO，實則標識一個線程。我