‘壹’ 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算法的基本思路，希望对大家能有所帮助。