A. DPDK ACL演算法介紹
DPDK提供了三種classify演算法：最長匹配LPM、精確匹配（Exact Match）和通配符匹配（ACL）。
其中的ACL演算法，本質是步長為8的Multi-Bit Trie，即每次可匹配一個位元組。一般來說步長為n時，Trie中每個節點的出邊為2^n，但DPDK在生成run-time structures時，採用DFA/QRANGE/SINGLE這幾種不同的方式進行數據結構的壓縮，有效去除了冗餘的出邊。本文將為大家介紹ACL演算法的基本原理，主要內容包括：trie樹的構造、運行時的node array生成和匹配原理。對於ACL介面的使用，參考DPDK的官方文檔即可。
ACL規則主要面向的是IP流量中的五元組信息，即IP/PORT/PROTO，演算法在這個基礎上進行了抽象，提供了三種類型的匹配區域：
熟悉這三種類型的使用後，完全可以用它們去匹配網路報文的其它區域，甚至將其應用到其它場景中。
具體來說，rte_acl_field_def有5個成員：type、size、field_index、input_index、offset。
如果要深入理解演算法，可以思考這幾個欄位的意義，或者換個角度來看：
對於規則的定義，要注意如下兩點：
比如定義了5個field，那麼請給出每一個的具體定義：
像field[1]中IP和mask都為0，表示匹配所有的IP地址；field[3]中range由0到65535，表示匹配所有。類似這樣的全匹配一定要顯示的定義出來，因為如果不明確定義，這些欄位的值取決於編譯器的，最後編譯的ACL規則很可能與原有設想存在偏差。
如果在規則中，對於某個field不進行限制，對於不同type的field，規則書寫時有一定差異：
對於BITMASK和MASK類型，全0代表匹配所有，如上例中的field[0]、field[1]；
對於RANGE，則按照上述field[3]中的形式定義。
規則定義好後，會轉換為trie樹並最終合並到一起。
實際處理過程中，build_trie函數會自底向上的將rule中的每個field轉換為node，然後將這些node合並生成這條rule的trie，最後將這個trie與已有的trie進行merge，最終生成整個rule set的trie。
tire由node組成，其主要數據成員如下：
node中values成員用於記錄匹配信息，ptrs則用於描述node的出邊，用於指向轉換後的node。
values採用bitmap進行壓縮，其數據結構為struct rte_acl_bitset values; 一個byte取值范圍是[0,255]，可通過256個bit位來進行對應，並實現byte值的快速查找：即通過第x位的bit值是否為1來判斷是否包含數值x（0 <= x < 256）。
num_ptrs用於描述出邊數目，ptrs即為實際的出邊，它記錄了其匹配值values和匹配後的節點指針。
match_flag和mrt則用於記錄匹配結果，trie樹中葉子節點一定是記錄匹配結果的節點。
trie樹其詳細結構比較復雜，這里將其結構進行簡化，如下所示：
上圖的trie樹有4個node，通過ptrs進行指向，values欄位為匹配值的bitmap表示，為了表述的簡潔，後續會採用simple的方式進行描述。
在trie simple中，實心節點表示匹配節點，邊上的數字代表匹配值（為便於閱讀，採用實際值而不再是bitmap形式），…代表其它匹配值。
不同type的field，轉換為node的方式會有所不同。
目前提供的3種類型：BITMASK描述一個byte的匹配，支持mask模式；MASK用於描述4個byte的匹配，支持mask模式；RANGE描述2個byte的匹配，此時mask表示上限。
field到node的轉換，見build_trie中的for循環，具體轉換函數則參考：
對於BITMASK，如{.value.u8 = 6, .mask_range.u8 = 0xff,}，它最後的轉換形式如下：
構造field的node時，總會在結尾添加一個空的end節點，最後一個field除外（它是match node）。在for循環中每完成了一個field的解析後，會將其合並到root中，從而生成這個rule的trie。
合並前，也會先構造一個空的end node（見build_trie函數中，while循環下的root創建），讓它與field構成的node頭合並，因為不相交，所以merge時會將匹配信息合並到end node並釋放原有的頭，並將field鏈的end節點返回（保存到end_prev中），下次合並時，就用此end節點與新的node頭合並。
循環遍歷完所有的field後，這些node就串聯起來了，構成這個rule的trie。
對於多個rule，每次構造完成後會merge到整體的trie中。
這里詳細介紹下merge演算法原理，其實仔細閱讀acl_merge_trie函數的注釋即可。
對於node A和node B的merge， acl_merge_trie函數返回一個節點，這個節點指向它們路徑的交集。
這里給出三個例子用於展示merge前後的變化。為了減少狀態點，構造rte_acl_field_def如下：
示例1：
acl_rules[1]為trie A，acl_rules[0]對應trie B，最終trie B合並到trie A上，具體如下：
1和1』合並時，因為level為0，所以1』直接合並到1中；
4和4』合並時，因為節點無交集，所以創建新節點c1(node 4的拷貝)，並將4'上的邊拷貝到c1中。
示例2，rule類別相同，但優先順序不同：
acl_rules[1]為trie A，acl_rules[0]對應trie B，最終trie B合並到trie A上，具體如下：
6和6』是match node，類別相同，且6的優先順序為2大於6』的優先順序。
6和6』合並時，直接返回6。而前面創建的新節點，如d1，已包含5』的所有邊（非ACL_INTERSECT_B），所以最終返回5，free d1。
同理依次往上回溯，a4，b3，c2，也依次被釋放，最終merge的trie即為原來的trie A。
示例3，rule類別不同，優先順序相同：
acl_rules[1]為trie A，acl_rules[0]對應trie B，最終trie B合並到trie A上，具體如下：
6和6』是match node，因為類別不同，所以最終創建了新node e1，這也導致示例3和示例2最終merge結果的不同。
合並是一個遞歸的過程，逆向思考構造過程會有助於理解演算法。另外，在build_trie之前會sort_rule，匹配范圍更大的rule會放到前面優先構造trie，個人為這樣node A包含node B的概率更大，這可能也是merge時創建的node C是A的拷貝而不是B的拷貝的原因，因為這樣出現ACL_INTERSECT_B的概率相對較低。
一些說明：
trie樹構造完成後，會將其由指針跳轉的形式轉換為等效的數組索引形式，即node array，既可讓匹配數據更緊湊，也可提高匹配演算法的效率。
採用node array的方式進行狀態點的壓縮是很常見的優化方式，比如snort裡面的ac演算法(acsmx.c)：
筆者也曾經做過類似的優化，通過將出邊由指針方式修改為索引方式，整個匹配tree的內存佔用只需要原來的1/5。
將指針方式轉換為node array形式是優化的第一步，對於Next[256]出邊又可以採用多種壓縮方式，比如snort中新的ac演算法(acsmx2.c)，就採用了Sparse rows和Banded rows等多種壓縮方式，但其原理是將出邊進行映射轉換，本質上還是做DFA狀態跳轉。
DPDK對邊的壓縮方式與上述類似，不過它優化的粒度更細，不同type的node有不同的壓縮方式：
比如在示例三中，node 1為DFA節點（根節點強制使用DFA方式），2、3、a5、b4、c3、d2為QRANGE，4、5為SINGLE，6、e1為MATCH。
2、3、a5、b4雖然在圖上僅有一條有效邊，但它不為SINGLE，因為對於無效的匹配其實也會有出邊，所以它的真實出邊數目並不唯一，只有像4、5這類全匹配節點才是真正的SINGLE節點。
在構造node array前，會調用acl_calc_counts_indices函數更新node的node type，fanout等信息。
node type依據其fanout值決定，fanout計算見acl_count_fanout函數，其原理是：
比如對於示例3中的d2節點：
fanout計算完成後，若其值為1則為SINGLE節點，(1, 5]為QRANGE節點，(5, 256]為DFA節點。
注意：對於trie樹的root節點，不論fanout值為多少，會強制將其構造為DFA節點，且其fanout值會重新計算。
type和fanout計算完成後，會統計各類節點數目，信息保存在acl_calc_counts_indices傳入的counts參數中，隨後rte_acl_gen依據這些信息將整塊的node array內存分配出來，其布局大致如下：
Data indexes中用於保存在rte_acl_field_def中定義的offset；
Results對應match node，用於保存匹配結果。
Trans table包含整個匹配過程中的跳轉點：
靜態將整塊node array分配完成後，就需要依據trie 樹的node信息填充Trans table和Results了，具體過程見acl_gen_node函數；Data indexes的填充則在acl_set_data_indexes中完成。
2.2中的內存布局大致描繪了各種類型節點的分布情況，DFAs內部由一個一個的DFA節點組成，QUADs和SINGLEs也一樣，都是由相同類型的節點構成。
對於每一個節點，其結構則類似如下形式：
DFA節點的fanout一般為4，出邊數為fanout*RTE_ACL_DFA_GR64_SIZE；（圖中畫的為fanout為4的情況，256條出邊）
QUAD節點的fanout不超過5，即為節點的出邊數不超過5；（圖中畫的為fanout為4的情況）
SINGLE節點只有一個出邊；
圖中的trans即為這個節點的出邊，它本質是一個uint64的數據結構，通過trans和input信息即可計算得到下一個節點的index，從而實現匹配跳轉。trans中不同bit位包含著豐富的信息，具體見acl.h中的說明即可。
高32位對於不同類型的節點有不同的解釋：
低32位：
在實際處理過程中，通過高32位與input_byte計算得到index，與低32位中的addr，即可快速定位到下一個trans：trans_table + (addr+index)。
這里的處理其實與傳統的DFA跳轉差別很大，傳統處理時，next = node[『input』]，跳轉到下一個節點，然後採用next[『input』]進行跳轉和匹配，即使有數據結構的壓縮，跳轉目標仍是狀態點。但DPDK中，跳轉時直接採用trans_table + (addr+index)，直接找到了狀態點的邊（trans），而不是到狀態點。
跳轉表具體構建時，採用acl_gen_node函數完成：
匹配的過程與跳轉表的構建其實是互為一體的，如何構建跳轉表就決定了如何進行匹配。
在2.3節，對於跳轉的形式已進行了說明，具體可閱讀rte_acl_classify_scalar函數：跳轉時直接採用trans_table + (addr+index)，直接找到了狀態點的邊（trans），而不是到狀態點。
對於具體的匹配過程，還有一點需要注意，即GET_NEXT_4BYTES的使用，每次匹配時候都會去4BTYTES進行匹配，這也是為什麼定義input fields時要求4位元組連續。比如我在dpdk-dev郵件組中問的這個 問題 。
解決4位元組連續，可以通過定義相同的input_index來解決，比如像郵件中提到的設置sport/dport的input_index相同，這是因為data indexes的構造取決於input_index，見acl_build_index函數；同時field_index不同、input_index相同時可避免對field區間的優化（如果優化，將某個field去掉了，這時4位元組匹配會失效）。郵件中的問題，正是因為field[3]被優化掉後，4位元組連續匹配出現問題。
在特定的場合還必須通過指定.size為32來解決，即使type類型為BITMASK，見DPDK的ACL文檔中關於 tos示例的說明 。
另外再說下field_index，前面提出一個問題：field_index是否多餘？
答案是不多餘，因為演算法中會對field進行優化，如果不指定field_index欄位，這個優化就無法進行了，具體的優化處理見acl_rule_stats函數。
優化過程中要進行input_index的判斷，這是因為相同的input_index可以有多個field，但其中只有某個field是completely wild時應避免進行優化。只有相同input_index的所有field都是completely wild時，才應該將這個field優化掉。
上面的一系列說明，都是針對GET_NEXT_4BYTES每次匹配四個位元組的匹配進行的補充說明。
匹配的具體過程，這里用圖形的方式進行簡要說明，為了能有多種類型的node，這里構造規則如下：
trie樹如下所述：
對應的node array如下圖所示：
假設輸入數據為：proto 16, ip 192.12.8.8，則transition跳轉方式如上圖紅線所示：
注意：node array中indexes、DFA0和idle省略了。
關於trie樹相關的理論知識參考 這里 。
本文主要介紹了DPDK的ACL演算法，詳細描述了如何由規則生成trie，並將trie轉換為node array的過程，在文末通過示例介紹了具體的匹配過程。文章旨在介紹ACL演算法的基本思路，希望對大家能有所幫助。
B. 圖解KMP字元串匹配演算法
kmp演算法跟之前講的bm演算法思想有一定的相似性。之前提到過，bm演算法中有個好後綴的概念，而在kmp中有個好前綴的概念，什麼是好前綴，我們先來看下面這個例子。
觀察上面這個例子，已經匹配的abcde稱為好前綴，a與之後的bcde都不匹配，所以沒有必要再比一次，直接滑動到e之後即可。
那如果前綴中有互相匹配的字元呢？
觀察上面這個例子，這個時候如果我們直接滑到好前綴之後，則會過度滑動，錯失匹配子串。那我們如何根據好前綴來進行合理滑動？
其實就是看當前的好前綴的前綴和後綴是否有匹配的，找到最長匹配長度，直接滑動。鑒於不止一次找最長匹配長度，我們完全可以先初始化一個數組，保存在當前好前綴情況下，最長匹配長度是多少，這時候我們的next數組就出來了。
我們定義一個next數組，表示在當前好前綴下，好前綴的前綴和後綴的最長匹配子串長度，這個最長匹配長度表示這個子串之前已經匹配過匹配了，不需要再次進行匹配，直接從子串的下一個字元開始匹配。
我們是否每次算next[i]時都需要每一個字元進行匹配，是否可以根據next[i - 1]進行推導以便減少不必要的比較。
帶著這個思路我們來看看下面的步驟：
假設next[i - 1] = k - 1;
如果modelStr[k] = modelStr[i] 則next[i]=k
如果modelStr[k] != modelStr[i]，我們是否可以直接認定next[i] = next[i - 1]？
通過上面這個例子，我們可以很清晰地看到，next[i]!=next[i-1]，那當modelStr[k]!=modelStr[i]時候，我們已知next[0],next[1]…next[i-1]，如何推導出next[i]呢？
假設modelStr[x…i]是前綴後綴能匹配的最長後綴子串，那麼最長匹配前綴子串為modelStr[0…i-x]
我們在求這個最長匹配串的時候，他的前面的次長匹配串（不包含當前i的），也就是modelStr[x…i-1]在之前應該是已經求解出來了的，因此我們只需要找到這個某一個已經求解的匹配串，假設前綴子串為modelStr[0…i-x-1],後綴子串為modelStr[x…i-1],且modelStr[i-x] == modelStr[i],這個前綴後綴子串即為次前綴子串，加上當前字元即為最長匹配前綴後綴子串。
代碼實現
首先在kmp演算法中最主要的next數組，這個數組標志著截止到當前下標的最長前綴後綴匹配子串字元個數，kmp演算法裡面，如果某個前綴是好前綴，即與模式串前綴匹配，我們就可以利用一定的技巧不止向前滑動一個字元，具體看前面的講解。我們提前不知道哪些是好前綴，並且匹配過程不止一次，因此我們在最開始調用一個初始化方法，初始化next數組。
1.如果上一個字元的最長前綴子串的下一個字元==當前字元，上一個字元的最長前綴子串直接加上當前字元即可
2.如果不等於，需要找到之前存在的最長前綴子串的下一個字元等於當前子串的，然後設置當前字元子串的最長前綴後綴子串
然後開始利用next數組進行匹配，從第一個字元開始匹配進行匹配，找到第一個不匹配的字元，這時候之前的都是匹配的，接下來先判斷是否已經是完全匹配，是直接返回，不是，判斷是否第一個就不匹配，是直接往後面匹配。如果有好前綴，這時候就利用到了next數組，通過next數組知道當前可以從哪個開始匹配，之前的都不用進行匹配。
C. 【演算法筆記】字元串匹配
BF 演算法中的 BF 是 Brute Force 的縮寫，中文叫作暴力匹配演算法，也叫樸素匹配演算法：
主串和模式串：
在字元串 A 中查找字元串 B，那字元串 A 就是主串，字元串 B 就是模式串。我們把主串的長度記作 n，模式串的長度記作 m
我們在主串中，檢查起始位置分別是 0、1、2…n-m 且長度為 m 的 n-m+1 個子串，看有沒有跟模式串匹配的。
BF 演算法的時間復雜度是 O(n*m)
等價於
比如匹配Google 和Goo 是最好時間復雜度，匹配Google 和ble是匹配失敗的最好時間復雜度。
KMP演算法是一種改進的字元串匹配演算法，由D.E.Knuth與J.H.Morris和V.R.Pratt同時發現，因此人們稱它為克努特—莫里斯—普拉特演算法。KMP演算法主要分為兩個步驟：字元串的自我匹配，目標串和模式串之間的匹配。
看來網上很多的文章，感覺很多的都沒有說清楚，這里直接復制阮一峰的內容，講的很清晰
內容來自 http://www.ruanyifeng.com/blog/
首先，字元串"BBC ABCDAB ABCDABCDABDE"的第一個字元與搜索詞"ABCDABD"的第一個字元，進行比較。因為B與A不匹配，所以搜索詞後移一位。
因為B與A不匹配，搜索詞再往後移。
就這樣，直到字元串有一個字元，與搜索詞的第一個字元相同為止。
接著比較字元串和搜索詞的下一個字元，還是相同。
直到字元串有一個字元，與搜索詞對應的字元不相同為止。
這時，最自然的反應是，將搜索詞整個後移一位，再從頭逐個比較。這樣做雖然可行，但是效率很差，因為你要把"搜索位置"移到已經比較過的位置，重比一遍。
一個基本事實是，當空格與D不匹配時，你其實知道前面六個字元是"ABCDAB"。KMP演算法的想法是，設法利用這個已知信息，不要把"搜索位置"移回已經比較過的位置，繼續把它向後移，這樣就提高了效率。
怎麼做到這一點呢？可以針對搜索詞，算出一張《部分匹配表》（Partial Match Table）。這張表是如何產生的，後面再介紹，這里只要會用就可以了。
已知空格與D不匹配時，前面六個字元"ABCDAB"是匹配的。查表可知，最後一個匹配字元B對應的"部分匹配值"為2，因此按照下面的公式算出向後移動的位數：
因為 6 - 2 等於4，所以將搜索詞向後移動4位。
因為空格與C不匹配，搜索詞還要繼續往後移。這時，已匹配的字元數為2（"AB"），對應的"部分匹配值"為0。所以，移動位數 = 2 - 0，結果為 2，於是將搜索詞向後移2位。
因為空格與A不匹配，繼續後移一位。
逐位比較，直到發現C與D不匹配。於是，移動位數 = 6 - 2，繼續將搜索詞向後移動4位。
逐位比較，直到搜索詞的最後一位，發現完全匹配，於是搜索完成。如果還要繼續搜索（即找出全部匹配），移動位數 = 7 - 0，再將搜索詞向後移動7位，這里就不再重復了。
下面介紹《部分匹配表》是如何產生的。
首先，要了解兩個概念："前綴"和"後綴"。 "前綴"指除了最後一個字元以外，一個字元串的全部頭部組合；"後綴"指除了第一個字元以外，一個字元串的全部尾部組合。
"部分匹配值"就是"前綴"和"後綴"的最長的共有元素的長度。以"ABCDABD"為例，
"部分匹配"的實質是，有時候，字元串頭部和尾部會有重復。比如，"ABCDAB"之中有兩個"AB"，那麼它的"部分匹配值"就是2（"AB"的長度）。搜索詞移動的時候，第一個"AB"向後移動4位（字元串長度-部分匹配值），就可以來到第二個"AB"的位置。
BM（Boyer-Moore）演算法。它是一種非常高效的字元串匹配演算法，有實驗統計，它的性能是著名的KMP 演算法的 3 到 4 倍。
BM 演算法包含兩部分，分別是壞字元規則（bad character rule）和好後綴規則（good suffix shift）
未完待續
參考文章：
字元串匹配的Boyer-Moore演算法
D. kmp演算法什麼意思
KMP演算法之所以叫做KMP演算法是因為這個演算法是由三個人共同提出來的，就取三個人名字的首字母作為該演算法的名字。其實KMP演算法與BF演算法的區別就在於KMP演算法巧妙的消除了指針i的回溯問題，只需確定下次匹配j的位置即可，使得問題的復雜度由O(mn)下降到O(m+n)。
在KMP演算法中，為了確定在匹配不成功時，下次匹配時j的位置，引入了next[]數組，next[j]的值表示P[0...j-1]中最長後綴的長度等於相同字元序列的前綴。
對於next[]數組的定義如下：
1) next[j] = -1 j = 0
2) next[j] = max(k): 0<k<j P[0...k-1]=P[j-k,j-1]
3) next[j] = 0 其他
如：
P a b a b a
j 0 1 2 3 4
next -1 0 0 1 2
即next[j]=k>0時，表示P[0...k-1]=P[j-k,j-1]
因此KMP演算法的思想就是：在匹配過程稱，若發生不匹配的情況，如果next[j]>=0，則目標串的指針i不變，將模式串的指針j移動到next[j]的位置繼續進行匹配；若next[j]=-1，則將i右移1位，並將j置0，繼續進行比較。
E. 指出BM演算法與KMP演算法的區別
KMP演算法和BM演算法，它們分別是前綴匹配和後綴匹配的經典演算法。
1、因為路由表中的每個表項都指定了一個網路，所以一個目的地址可能與多個表項匹配。最明確的一個表項，即子網掩碼最長的一個，就叫做最長前綴匹配。
2、之所以這樣稱呼它，是因為這個表項也是路由表中，與目的地址的高位匹配得最多的表項。