『壹』 php怎麼判斷標題是否存在某些字元
假如變數$A儲存了要判斷的字元串，函數
preg_match('/褲子|褲|男裝|衣服/', $A)
含有時返回1，不包含時返回0。
其餘類推
『貳』 php新手學習路線是怎樣的
第一階段：基礎階段（基礎PHP程序員）
重點：把LNMP搞熟練（核心是安裝配置基本操作） 目標：能夠完成基本的LNMP系統安裝，簡單配置維護；能夠做基本的簡單系統的PHP開發；能夠在PHP中型系統中支持某個PHP功能模塊的開發。
時間：完成本階段的時間因人而異，有的成長快半年一年就過了，成長慢的兩三年也有。
Linux
基本命令、操作、啟動、基本服務配置（包括rpm安裝文件，各種服務配置等）；會寫簡單的shell腳本和awk/sed 腳本命令等。
Nginx
做到能夠安裝配置nginx+php，知道基本的nginx核心配置選項，知道 server/fastcgi_pass/access_log 等基礎配置，目標是能夠讓nginx+php_fpm順利工作。
MySQL
會自己搭建mysql，知道基本的mysql配置選項；知道innodb和myisam的區別，知道針對InnoDB和MyISAM兩個引擎的不同配置選項；知道基本的兩個引擎的差異和選擇上面的區別；能夠純手工編譯搭建一個MySQL資料庫並且配置好編碼等正常穩定運行；核心主旨是能夠搭建一個可運行的MySQL資料庫。
PHP
基本語法數組、字元串、資料庫、XML、Socket、GD/ImageMgk圖片處理等等；熟悉各種跟MySQL操作鏈接的api（mysql/mysqli/PDO)，知道各種編碼問題的解決；知道常規熟練使用的PHP框架（ThinkPHP、Zendframework、Yii、Yaf等）；了解基本MVC的運行機制和為什麼這么做，稍微知道不同的PHP框架之間的區別；能夠快速學習一個MVC框架。能夠知道開發工程中的文件目錄組織，有基本的良好的代碼結構和風格，能夠完成小系統的開發和中型系統中某個模塊的開發工作。
前端
如果條件時間允許，可以適當學習下 HTML/CSS/JS 等相關知識，知道什麼web標准，div+css的web/wap頁面模式，知道HTML5和HTML4的區別；了解一些基本的前端只是和JS框架（jQuery之類的）；了解一些基本的JavaScript編程知識；（本項不是必須項，如果有時間，稍微了解一下是可以的，不過不建議作為重點，除非個人有強烈興趣）。
系統設計
能夠完成小型系統的基本設計，包括簡單的資料庫設計，能夠完成基本的：瀏覽器 -> Nginx+PHP -> 資料庫 架構的設計開發工作；能夠支撐每天幾十萬到數百萬流量網站的開發維護工作；
第二階段：提高階段 （中級PHP程序員）
重點：提高針對LNMP的技能，能夠更全面的對LNMP有熟練的應用。 目標：能夠隨時隨地搭建好LNMP環境，快速完成常規配置；能夠追查解決大部分遇到的開發和線上環境的問題；能夠獨立承擔中型系統的構架和開發工作；能夠在大型系統中承擔某個中型模塊的開發工作。
1. Linux
在第一階段的基礎上面，能夠流暢的使用Shell腳本來完成很多自動化的工作；awk/sed/perl 也操作的不錯，能夠完成很多文本處理和數據統計等工作；基本能夠安裝大部分非特殊的Linux程序（包括各種庫、包、第三方依賴等等，比如MongoDB/Redis/Sphinx/Luncene/SVN之類的）；了解基本的Linux服務，知道如何查看Linux的性能指標數據，知道基本的Linux下面的問題跟蹤等。
2. Nginx
在第一階段的基礎上面，了解復雜一些的Nginx配置；包括 多核配置、events、proxy_pass，sendfile/tcp_*配置，知道超時等相關配置和性能影響；知道nginx除了web server，還能夠承擔代理伺服器、反向靜態伺服器等配置；知道基本的nginx配置調優；知道如何配置許可權、編譯一個nginx擴展到nginx；知道基本的nginx運行原理（master/worker機制，epoll），知道為什麼nginx性能比apache性能好等知識。
3. MySQL/MongoDB
在第一階段的基礎上面，在MySQL開發方面，掌握很多小技巧，包括常規SQL優化（group by/order by/rand優化等）；除了能夠搭建MySQL，還能夠冷熱備份MySQL數據，還知道影響innodb/myisam性能的配置選項（比如key_buffer/query_cache/sort_buffer/innodb_buffer_pool_size/innodb_flush_log_at_trx_commit等），也知道這些選項配置成為多少值合適；另外也了解一些特殊的配置選項，比如 知道如何搭建mysql主從同步的環境，知道各個binlog_format的區別；知道MySQL的性能追查，包括slow_log/explain等，還能夠知道基本的索引建立處理等知識；原理方面了解基本的MySQL的架構（Server+存儲引擎），知道基本的InnoDB/MyISAM索引存儲結構和不同（聚簇索引，B樹）；知道基本的InnoDB事務處理機制；了解大部分MySQL異常情況的處理方案（或者知道哪兒找到處理方案）。條件允許的情況，建議了解一下NoSQL的代表MongoDB資料庫，順便對比跟MySQL的差別，同事能夠在合適的應用場景安全謹慎的使用MongoDB，知道基本的PHP與MongoDB的結合開發。
4. Redis/Memcached
在大部分中型系統裡面一定會涉及到緩存處理，所以一定要了解基本的緩存；知道Memcached和Redis的異同和應用場景，能夠獨立安裝 Redis/Memcached，了解Memcahed的一些基本特性和限制，比如最大的value值，知道PHP跟他們的使用結合；Redis了解基本工作原理和使用，了解常規的數據類型，知道什麼場景應用什麼類型，了解Redis的事務等等。原理部分，能夠大概了解Memcached的內存結構（slab機制），redis就了解常用數據類型底層實現存儲結構（SDS/鏈表/SkipList/HashTable）等等，順便了解一下Redis的事務、RDB、AOF等機制更好。
5. PHP
除了第一階段的能力，安裝配置方面能夠隨意安裝PHP和各種第三方擴展的編譯安裝配置；了解php-fpm的大部分配置選項和含義（如max_requests/max_children/request_terminate_timeout之類的影響性能的配置），知道mod_php/fastcgi的區別；在PHP方面已經能夠熟練各種基礎技術，還包括各種深入些的PHP，包括對PHP面向對象的深入理解/SPL/語法層面的特殊特性比如反射之類的；在框架方面已經閱讀過最少一個以上常規PHP MVC框架的代碼了，知道基本PHP框架內部實現機制和設計思想；在PHP開發中已經能夠熟練使用常規的設計模式來應用開發（抽象工廠/單例/觀察者/命令鏈/策略/適配器 等模式）；建議開發自己的PHP MVC框架來充分讓開發自由化，讓自己深入理解MVC模式，也讓自己能夠在業務項目開發里快速升級；熟悉PHP的各種代碼優化方法，熟悉大部分PHP安全方面問題的解決處理；熟悉基本的PHP執行的機制原理（Zend引擎/擴展基本工作機制）。
6. C/C++
開始涉獵一定的C/C++語言，能夠寫基本的C/C++代碼，對基本的C/C++語法熟悉（指針、數組操作、字元串、常規標准API）和數據結構（鏈表、樹、哈希、隊列）有一定的熟悉下；對Linux下面的C語言開發有基本的了解概念，會簡單的makefile文件編寫，能夠使用簡單的GCC/GDB的程序編譯簡單調試工作；對基本的網路編程有大概了解。（本項是為了向更高層次打下基礎）。
7. 前端
在第一階段的基礎上面，熟悉基本的HTTP協議（協議代碼200/300/400/500，基本的HTTP交互頭）；條件允許，可以在深入寫出稍微優雅的HTML+CSS+JavaScript，或者能夠大致簡單使用某些前端框架（jQuery/YUI/ExtJS/RequireJS/BootStrap之類）；如果條件允許，可以深入學習JavaScript編程，比如閉包機制、DOM處理；再深入些可以讀讀jQuery源碼做深入學習。（本項不做重點學習，除非對前端有興趣）。
8. 系統設計
能夠設計大部分中型系統的網站架構、資料庫、基本PHP框架選型；性能測試排查處理等；能夠完成類似：瀏覽器 -> CDN(Squid) -> Nginx+PHP -> 緩存 -> 資料庫 結構網站的基本設計開發維護；能夠支撐每天數百萬到千萬流量基本網站的開發維護工作；
第三階段：高級階段 （高級PHP程序員）
重點：除了基本的LNMP程序，還能夠在某個方向或領域有深入學習。（縱深維度發展） 目標：除了能夠完成基本的PHP業務開發，還能夠解決大部分深入復雜的技術問題，並且可以獨立設計完成中大型的系統設計和開發工作；自己能夠獨立hold深入某個技術方向，在這塊比較專業。（比如在MySQL、Nginx、PHP、Redis等等任一方向深入研究）
1. Linux
除了第二階段的能力，在Linux下面除了常規的操作和性能監控跟蹤，還能夠使用很多高級復雜的命令完成工作（watch/tcpmp/starce/ldd/ar等)；在shell腳本方面，已經能夠編寫比較復雜的shell腳本（超過500行）來協助完成很多包括備份、自動化處理、監控等工作的shell；對awk/sed/perl 等應用已經如火純青，能夠隨意操作控制處理文本統計分析各種復雜格式的數據；對Linux內部機制有一些了解，對內核模塊載入，啟動錯誤處理等等有個基本的處理；同時對一些其他相關的東西也了解，比如NFS、磁碟管理等等；
2. Nginx
在第二階段的基礎上面，已經能夠把Nginx操作的很熟練，能夠對Nginx進行更深入的運維工作，比如監控、性能優化，復雜問題處理等等；看個人興趣，更多方面可以考慮側重在關於Nginx工作原理部分的深入學習，主要表現在閱讀源碼開始，比如具體的master/worker工作機制，Nginx內部的事件處理，內存管理等等；同時可以學習Nginx擴展的開發，可以定製一些自己私有的擴展；同時可以對Nginx+Lua有一定程度的了解，看看是否可以結合應用出更好模式；這個階段的要求是對Nginx原理的深入理解，可以考慮成為Nginx方向的深入專業者。
3. MySQL/MongoDB
在第二階段的基礎上面，在MySQL應用方面，除了之前的基本SQL優化，還能夠在完成一些復雜操作，比如大批量數據的導入導出，線上大批量數據的更改表結構或者增刪索引欄位等等高危操作；除了安裝配置，已經能夠處理更多復雜的MySQL的問題，比如各種問題的追查，主從同步延遲問題的解決、跨機房同步數據方案、MySQL高可用架構等都有涉及了解；對MySQL應用層面，對MySQL的核心關鍵技術比較熟悉，比如事務機制（隔離級別、鎖等）、對觸發器、分區等技術有一定了解和應用；對MySQL性能方面，有包括磁碟優化（SAS遷移到SSD）、伺服器優化（內存、伺服器本身配置）、除了二階段的其他核心性能優化選項（innodb_log_buffer_size/back_log/table_open_cache/thread_cache_size/innodb_lock_wait_timeout等）、連接池軟體選擇應用，對show *（show status/show profile）類的操作語句有深入了解，能夠完成大部分的性能問題追查；MySQL備份技術的深入熟悉，包括災備還原、對Binlog的深入理解，冷熱備份，多IDC備份等；在MySQL原理方面，有更多了解，比如對MySQL的工作機制開始閱讀部分源碼，比如對主從同步（復制）技術的源碼學習，或者對某個存儲引擎（MyISAM/Innodb/TokuDB）等等的源碼學習理解，如果條件允許，可以參考CSV引擎開發自己簡單的存儲引擎來保存一些數據，增強對MySQL的理解；在這個過程，如果自己有興趣，也可以考慮往DBA方向發展。MongoDB層面，可以考慮比如說在寫少讀多的情況開始在線上應用MongoDB，或者是做一些線上的數據分析處理的操作，具體場景可以按照工作來，不過核心是要更好的深入理解RMDBS和NoSQL的不同場景下面的應用，如果條件或者興趣允許，可以開始深入學習一下MongoDB的工作機制。
4. Redis/Memcached
在第二階段的基礎上面，能夠更深入的應用和學習。因為Memcached不是特別復雜，建議可以把源碼進行閱讀，特別是內存管理部分，方便深入理解；Redis部分，可以多做一些復雜的數據結構的應用（zset來做排行榜排序操作/事務處理用來保證原子性在秒殺類場景應用之類的使用操作）；多涉及aof等同步機制的學習應用，設計一個高可用的Redis應用架構和集群；建議可以深入的學習一下Redis的源碼，把在第二階段積累的知識都可以應用上，特別可以閱讀一下包括核心事件管理、內存管理、內部核心數據結構等充分學習了解一下。如果興趣允許，可以成為一個Redis方面非常專業的使用者。
5. PHP
作為基礎核心技能，我們在第二階段的基礎上面，需要有更深入的學習和應用。從基本代碼應用上面來說，能夠解決在PHP開發中遇到95%的問題，了解大部分PHP的技巧；對大部分的PHP框架能夠迅速在一天內上手使用，並且了解各個主流PHP框架的優缺點，能夠迅速方便項目開發中做技術選型；在配置方面，除了常規第二階段會的知識，會了解一些比較偏門的配置選項（php auto_prepend_file/auto_append_file），包括擴展中的一些復雜高級配置和原理（比如memcached擴展配置中的memcache.hash_strategy、apc擴展配置中的apc.mmap_file_mask/apc.slam_defense/apc.file_update_protection之類的）；對php的工作機制比較了解，包括php-fpm工作機制（比如php-fpm在不同配置機器下面開啟進程數量計算以及原理），對zend引擎有基本熟悉（vm/gc/stream處理），閱讀過基本的PHP內核源碼（或者閱讀過相關文章），對PHP內部機制的大部分核心數據結構（基礎類型/Array/Object）實現有了解，對於核心基礎結構（zval/hashtable/gc）有深入學習了解；能夠進行基本的PHP擴展開發，了解一些擴展開發的中高級知識（minit/rinit等），熟悉php跟apache/nginx不同的通信交互方式細節（mod_php/fastcgi）；除了開發PHP擴展，可以考慮學習開發Zend擴展，從更底層去了解PHP。
6. C/C++
在第二階段基礎上面，能夠在C/C++語言方面有更深入的學習了解，能夠完成中小型C/C++系統的開發工作；除了基本第二階段的基礎C/C++語法和數據結構，也能夠學習一些特殊數據結構（b-tree/rb-tree/skiplist/lsm-tree/trie-tree等）方便在特殊工作中需求；在系統編程方面，熟悉多進程、多線程編程；多進程情況下面了解大部分多進程之間的通信方式，能夠靈活選擇通信方式（共享內存/信號量/管道等）；多線程編程能夠良好的解決鎖沖突問題，並且能夠進行多線程程序的開發調試工作；同時對網路編程比較熟悉，了解多進程模型/多線程模型/非同步網路IO模型的差別和選型，熟悉不同非同步網路IO模型的原理和差異（select/poll/epoll/iocp等），並且熟悉常見的非同步框架（ACE/ICE/libev/libevent/libuv/Boost.ASIO等）和使用，如果閑暇也可以看看一些國產自己開發的庫（比如muo）；同時能夠設計好的高並發程序架構（leader-follow/master-worker等）；了解大部分C/C++後端Server開發中的問題（內存管理、日誌列印、高並發、前後端通信協議、服務監控），知道各個後端服務RPC通信問題（struct/http/thirft/protobuf等）；能夠更熟絡的使用GCC和GDB來開發編譯調試程序，在線上程序core掉後能夠迅速追查跟蹤解決問題；通用模塊開發方面，可以積累或者開發一些通用的工具或庫（比如非同步網路框架、日誌庫、內存池、線程池等），不過開發後是否應用要謹慎，省的埋坑去追bug。
7. 前端
深入了解HTTP協議（包括各個細致協議特殊協議代碼和背後原因，比如302靜態文件緩存了，502是nginx後面php掛了之類的）；除了之前的前端方面的各種框架應用整合能力，前端方面的學習如果有興趣可以更深入，表現形式是，可以自己開發一些類似jQuery的前端框架，或者開發一個富文本編輯器之類的比較瑣碎考驗JavaScript功力。
8. 其他領域語言學習
在基礎的PHP/C/C++語言方面有基本積累，建議在當前階段可以嘗試學習不同的編程語言，看個人興趣愛好，腳本類語言可以學學 Python/Ruby 之類的，函數式編程語言可以試試 Lisp/Haskell/Scala/Erlang 之類的，靜態語言可以試試 Java/Golang，數據統計分析可以了解了解R語言，如果想換個視角做後端業務，可以試試 Node.js還有前面提到的跟Nginx結合的Nginx_Lua等。學習不同的語言主要是提升自己的視野和解決問題手段的差異，比如會了解除了進程/線程，還有輕量級協程；比如在跨機器通信場景下面，Erlang的解決方案簡單的驚人；比如在不想選擇C/C++的情況下，還有類似高效的Erlang/Golang可用等等；主要是提升視野。
9. 其他專業方向學習
在本階段裡面，會除了基本的LNMP技能之外，會考慮一些其他領域知識的學習，這些都是可以的，看個人興趣和長期的目標方向。目前情況能夠選擇的領域比較多，比如、雲計算（分布式存儲、分布式計算、虛擬機等），機器學習（數據挖掘、模式識別等，應用到統計、個性化推薦），自然語言處理（中文分詞等），搜索引擎技術、圖形圖像、語音識別等等。除了這些高大上的，也有很多偏工程方面可以學習的地方，比如高性能系統、移動開發（Android/IOS）、計算機安全、嵌入式系統、硬體等方向。
10. 系統設計
系統設計在第二階段的基礎之上，能夠應用掌握的經驗技能，設計出比較復雜的中大型系統，能夠解決大部分線上的各種復雜系統的問題，完成類似 瀏覽器 -> CDN -> 負載均衡 ->接入層 -> Nginx+PHP -> 業務緩存 -> 資料庫 -> 各路復雜後端RPC交互（存儲後端、邏輯後端、反作弊後端、外部服務） -> 更多後端 醬紫的復雜業務；能夠支撐每天數千萬到數億流量網站的正常開發維護工作。
『叄』 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演算法的基本思路，希望對大家能有所幫助。