Hyperscan中的 NFA模型演化

我们知道,正则语言等价于NFA(Nondeterministic Finite Automata,非确定有限状态自动机)。Hyperscan作为一款正则表达式匹配引擎,其核心部分是对NFA的构造和处理,编译期将正则表达式转化为与其等价的NFA图并构造NFA引擎,运行期根据输入语料运行NFA引擎来确定匹配位置。

NFA构造方法

NFA中一个状态在遇到相同输入时可能跳转至多个状态。将正则表达式转化为NFA图,常见的有两种构造方法:Thompson构造法和Glushkov构造法。

Thompson构造法

正则表达式由若干字符和运算构成,其运算只有三种:并、连接和Kleene*闭包。一条正则表达式可被运算划分为子表达式,Thompson构造法的特点就是定义简单,其本质是一种递归的构造法,定义了子表达式运算的构造规则和递归出口,如下图所示:

图中前两项定义了递归出口的两种原子表达式对应的NFA图:空表达式ε或单字符表达式c。
接下来三项定义了子表达式运算(或,连接,Kleene*闭包)的NFA图构造规则。
例如,对正则表达式 /(AB|CD)*AFF*/,用Thompson构造法构造出的NFA图为:

对于含有m个运算的正则表达式,Thompson构造法生成的NFA图最多能有2m个状态和4m个转移,可见这样的NFA图状态繁多且含有大量空跳转。对于长度为n个字符的输入文本,计算每个字符输入可能产生的状态转移都要仔细检查所有空跳转,因为空跳转可以不受限制的传播。

Glushkov构造法

Glushkov构造法是基于位置的构造法,而非直接对NFA图进行递归构造。Glushkov NFA十分简洁,不含空跳转,且一个状态的所有进入条件都相同。
其构造过程,先对正则表达式中每个位置的字符编号(从1开始),对应NFA图中的状态,编号0为初始状态,再计算下面几个递归函数,它们对三种运算的递归定义及递归出口定义如下:

得到最终的P、D、F后,从开始状态0到P中每个状态都加一个跳转,D中所有状态都标记为结束状态,F中每个状态对之间也都加一个跳转,如此就得到了对应的Glushkov NFA图。另外若Λ={ε}则表示该图可为空。
同样对正则表达式 /(AB|CD)*AFF*/,用Glushkov构造法构造出的NFA图为:

Hyperscan的早期NFA模型演化

Hyperscan对NFA构造方法的取舍,与应用平台相关,在使用Intel SIMD指令的场景下,用位向量描述NFA的状态是很合适的,NFA状态数量越少,越能减少对空间和时间的消耗。于是Hyperscan很自然的选择了状态数量更少的Glushkov NFA。
在编译期,Hyperscan将正则表达式或正则表达式集转换为Glushkov NFA,然后生成合适的NFA引擎,以便运行期高效使用。Hyperscan对表达式中某个位置字符集的处理视同一个字符,对应Glushkov NFA中的一个状态,这样可以压缩图的规模,也有利于一些加速处理(如squash优化,今后会介绍)。
全局来看,一个大的NFA图可以整个作为一个NFA引擎使用,但往往效率不高,因为在运行期NFA中大部分状态可能都是非激活的,甚至在遇到某些特定条件之前,某些状态永远也不会被激活,或某些激活的状态永远也不可能到结束状态。Hyperscan针对这些特性对大的NFA图做切割,生成一系列小的NFA图,再分别生成NFA引擎。NFA引擎所使用的模型有一个演化过程。

General模型

Hyperscan使用位向量描述运行中的NFA,根据NFA的状态数量决定使用多大的位向量(如m128, m256, m512等),目前最多可支持512个状态。General模型是最基本的模型,它是对NFA运行操作的直接实现。
对每一个输入字符c,NFA运行通常分为三步:先找出当前的激活状态集s的后继状态集SUCC[s],再找出输入字符c的可达状态集REACH[c],最后两者做“AND”:

简单说就是两次查表加一次“AND”,其伪代码描述为:

在不同的模型中,后两步计算很简单通常都一致,第一步计算比较复杂,有许多不同的方法。各NFA模型的演化主要集中于对后继状态集SUCC[s]计算方法的改进。
为方便描述,接下来我们以m128类型的位向量为例,可表达最多128个状态。向量中“1”表示激活状态,“0”表示未激活状态。
对于128个状态的NFA,计算后继状态集有两种最基本的方法:
1. 编译期对每个状态集(128位状态值)建立后继状态集掩码,共2^128个表项,运行期只需1次查表即可。
2. 编译期对每个单独状态建立后继状态集掩码,共128个表项,运行期对所有激活状态查表得到掩码并“OR”。最差情况要做128次查表和127次“OR”。
但显然上述两种方法都不可取,方法1对空间的要求根本无法实现,方法2在运行期效率低下。那么折衷一下,便产生了方法3。
3. 将128位划分为16字节,编译期对每8个状态的集合(1字节)建立后继状态集掩码,共16*2^8个表项,运行期做16次查表并做15次“OR”。

方法3对时间和空间的消耗都在可接受范围内了,但不高效,它做了太多操作,很多时候是杀鸡用牛刀。

Limited 模型

实际应用中我们会发现,大多数正则表达式生成的NFA其实只包含小跨度的跳转。我们称这样的NFA为Limited NFA(有限跨度跳转),计算后继状态集的时间和空间开销对于Limited NFA而言规模很小。我们对每个跨度的跳转构造一个掩码,称之为shift mask。以前述正则表达式 /(AB|CD)*AFF*/ 的Glushkov NFA为例,shift mask如下表所示(空白位皆为“0”):

表中第n项的第m位为“1”的含义是状态m+n是状态m的后继状态。对给定当前状态集计算后继状态集是用“shift-or”算法,只需把当前状态与每个表项分别做“AND”,得到的每个结果左移n位,再全部做“OR”。
既然是Limited NFA,必然需要定义跳转的跨度上限,来控制计算的规模。例如我们定义上例中的跳转跨度界限为小于3,则我们只用到前3个掩码(shift0~2),以m128类型位向量为例,该“shift-or”算法的代码描述为:

显而易见,这个模型不能处理所有的跳转,上例中跨度大于等于3的跳转全被忽略了,怎么办?我们视有这些跳转的状态为Exceptional,并借用General模型来处理它们。Exceptional状态包含有大跨度正向边跳转的状态,也包含有反向边跳转的状态,除此还有一类跨“边界”跳转的状态——这类状态的产生归咎于shift128所使用的具体指令PSLLQ:_mm_slli_epi64(),该指令对m128类型数据做移位操作时,以64bit为边界对高半部和低半部分别做移位,如此则导致计算跨边界跳转激活状态(通常在低半部的高位)的后继状态时,有效位会在shift128后丢失,故该类状态不为Limited模型兼容,划入Exceptional。如何借用General模型处理Exceptional状态?我们有Limited与General相融合的模型LimGen。

LimGen模型

LimGen模型为Limited和General两种模型的结合,以Limited NFA为基础,附加处理最多16个Exceptional状态。我们在编译期选出所有的Exceptional状态,并根据它们的位置创建一对掩码(permutate mask和compare mask)和它们的后继状态集掩码表(2*2^8个表项),在运行期用PSHUFB/PAND/PCMPEQB/MOVMSKB一组操作将Exceptional状态的对应位汇聚到一个16位整数中,用其中2个字节分别查表并将结果做“OR”,最后与Limited部分的后继状态集做“OR”完成LimGen模型的后继状态集计算。
以m128类型位向量为例,其代码描述为:

掩码permMask中每字节的低4位用来表达Exceptional状态位在位向量s中的字节索引,当s中字节m包含n个Exceptional状态位时,索引m在permMask中出现n次。掩码compMask中每字节只有1位激活,对应1个Exceptional状态位在其所在字节中的位置。
LimGen模型已经比较强大了,但其能处理的Exceptional状态上限为16个,而且只包含3类含有特殊跳转的Exceptional状态:含有超限跨度正向边跳转的状态、含有反向边跳转的状态、含有跨64位边界跳转的状态。

Hyperscan的LimEx NFA模型

随着Hyperscan的发展,上述三种模型已经不出现在当前的代码中,当前代码中所使用的NFA模型是LimEx模型。
“LimEx”模型意为Limited + Exceptional,是对LimGen模型的扩展,其对Exceptional状态的定义不局限于上述3种特殊跳转状态,越来越多的优化也被以Exceptional状态的形式加入到NFA模型中。
运行一个LimEx模型可用下面的伪代码描述:

对每个输入字符c,其行为是以当前的激活状态集s为基础,先处理Limited部分,再处理Exceptional部分,获得后继状态集succ,再与c的可达状态集做“AND”。
表reach中含有256个表项,每个字符对应一项,为字符到状态位向量的映射。
由于Glushkov NFA的特点,NFA图中每个状态结点有固定的触发字符(char-reachability),建立reach表无须遍历NFA图中的边,只需遍历所有结点即可,而拥有较少结点数的Glushkov NFA正好能够体现其优势。
Limited部分由limited_successors()处理,可参考getSuccessorsLim()。
目前LimEx模型定义的Exceptional状态类型有如下几种:

  • 1. 含有上述3种特殊跳转的状态,对应的后继状态集掩码以“OR”操作加入。
  • 2. 结束状态(Accept状态),产生匹配的状态。
  • 3. Squasher状态,负责杀死无关紧要的状态以减少针对激活的Exceptional状态的操作,其对应掩码有效位为“0”,以“AND”操作加入后继状态集。
  • 4. LBR(Large Bounded Repeat)引擎触发状态,包括POS和TUG状态。

它们都由process_exceptions()处理。不同于LimGen模型用permMask和compMask挑选Exceptional状态,LimEx引擎在编译期会生成exceptionMask掩码,用以在运行期挑出激活的Exceptional状态位,对每个激活的Exceptional状态做对应处理。
本篇Hyperscan中的NFA模型演化就介绍到这里,有关LimEx模型的更多细节,包括各种Exceptional状态的具体处理方法,我们会在今后介绍。

原文地址:DPDK开源社区

发表评论

电子邮件地址不会被公开。 必填项已用*标注