9.1.8　BPF过滤器的优化研究

过滤器性能的重要性不言而喻，假设在百兆网络中每个数据包的大小平均为100B，那么过滤器每秒处理的数据包数目可达十万个。而且同一时刻系统中可能会有多个过滤器正在进行过滤工作，这对过滤器的性能提出了更高的要求。BPF虽然在性能方面较之前出现的过滤器要快很多，但随着现代网络的不断发展，BPF的性能也受到了严重的挑战。为了提高过滤器的性能，必须解决虚拟机指令生成在处理多个过滤条件组合时存在的指令冗余问题。

1.问题描述

BPF提供了一系列API，用于完成从高级语言的谓词判断语句到过滤器虚拟机指令的生成过程。这可以帮助用户在不需要了解虚拟机指令的前提下，进行数据包过滤工作。例如，当用户提出需要获取网络中的IP数据包时，指令生成器会将用户需求编译成虚拟机指令，如下所示：

$tcpdump-Od ip//无优化

(000)ldh[12]

(001)jeq#0x800 jt 2 jf 3//检查是否为IP协议

(002)ret#96

(003)ret#0

$tcpdump-d ip//优化

(000)ldh[12]

(001)jeq#0x800 jt 2 jf 3//检查是否为IP协议

(002)ret#96

(003)ret#0

可见，BPF指令生成器在处理这样简单的过滤条件时不会出现问题。但是如果在无优化的条件下，当多个过滤条件组合时，它仅是将多个条件进行简单的AND及OR组合，可能出现多条冗余指令。例如，当用户需要获取协议类型为TCP并且源地址为192.168.10.23的数据包时，在无优化的情况下，BPF指令生成器会将此编译成获取TCP数据和获取源地址为192.168.10.23这两个过滤条件的AND操作，其中会出现多条冗余指令，具体的指令如下：

$tcpdump-Od tcp and src 192.168.10.23//无优化

(000)ldh[12]

(001)jeq#0x86dd jt 2 jf 4

(002)ldb[20]

(003)jeq#0x6 jt 8 jf 4

(004)ldh[12]

(005)jeq#0x800 jt 6 jf 21

(006)ldb[23]

(007)jeq#0x6 jt 8 jf 21

(008)ldh[12]

(009)jeq#0x800 jt 10 jf 12

(010)ld[26]

(011)jeq#0xc0a80a17 jt 20 jf 12

(012)ldh[12]

(013)jeq#0x806 jt 14 jf 16

(014)ld[28]

(015)jeq#0xc0a80a17 jt 20 jf 16

(016)ldh[12]

(017)jeq#0x8035 jt 18 jf 21

(018)ld[28]

(019)jeq#0xc0a80a17 jt 20 jf 21

(020)ret#96

(021)ret#0

以上指令完全可以优化为如下所示的指令：

$tcpdump-d tcp and src 192.168.10.23//优化

(000)ldh[12]

(001)jeq#0x86dd jt 8 jf 2

(002)jeq#0x800 jt 3 jf 8

(003)ldb[23]

(004)jeq#0x6 jt 5 jf 8

(005)ld[26]

(006)jeq#0xc0a80a17 jt 7 jf 8

(007)ret#96

(008)ret#0

由上述指令可见，优化可使指令精简很多。

2.优化方法简介

BPF通过引入静态单赋值(Static Single Assignment，SSA)、结合冗余谓词消除和窥孔优化等编译技术，有效地缩短了CFG图的平均路径长度，实现了对过滤器性能的优化。下面简要介绍这些优化技术。

（1）静态单赋值的基本概念

静态单赋值是一种优化的编译器数据结构，使用SSA形式不但有利于使用更多的编译器优化算法，而且有利于提高这些算法的效率。SSA形式要求每个变量只能被赋值一次，因此SSA形式可以有效地把程序中所操作的数值和这些数值存储的位置分开，这样就可以利用更多的编译器优化方法了。SSA形式能够帮助处理优化常量传播、部分冗余删除、条件常量复制、寄存器分配优化等问题。

（2）优化过程

BPF将虚拟机指令生成器分为编译器和优化器两个独立的组成部分。首先编译器将高级语言形式的过滤要求转化为控制流图(CFG)，再将此控制流图转化为符合SSA形式的控制流图。最后优化器负责对SSA形式的控制流图进行优化，并生成最终的虚拟机指令。该过程如图9-3所示。

图　9-3　BPF中虚拟机指令生成的过程

编译器的输出是具有SSA形式的控制流图，在这样的控制流图中每个结点都是由具备SSA形式的基本块组成的，并且此控制流图有一个入口结点和2个终止结点。其中，每个基本块都以布尔判断作为最后一条指令，基本块的走向依赖于这个布尔判断的结果。SSA形式的控制流图有助于利用编译器的优化算法进行优化或者提高算法的效率，但目前真正的优化工作还没有进行。紧接着，优化器将完成对SSA形式控制流图的优化工作。优化器充分利用SSA形式的优点，使用冗余谓词消除、窥孔优化等优化方法对SSA形式的控制流图进行优化。

（3）冗余谓词消除

冗余谓词消除是用来消除SSA控制流图中冗余的基本块和基本块内部冗余的谓词判断的，通常我们会结合采用以下三种技术来完成优化工作：

❑部分冗余删除(partial redundancy elimination)：移动控制流图中至少存在部分冗余的计算到最优的计算点进行计算，并完全删除这些冗余的计算。

❑谓词断言传播(predicate assertion propagation)：对控制流图中的边使用全局数据流分析方法(global data-flow analysis)进行优化。该方法通过对谓词判断在穿越基本块时的修改情况进行分析，获得控制流图中边的断言集合，从而改变边的流向，进而对冗余的基本块进行旁路。

❑静态谓词预测(static predicate prediction)：它可以使用第2种技术中边的断言集合信息并结合基本块中的谓词判断信息来预测边的流向，对冗余的基本块进行旁路。

在实际的优化过程中，每使用以上的一种技术后，都可能会将新的可优化之处带给其他的优化技术。因此，在优化过程中需要结合使用这三种技术，并且在优化结束前，不断重复使用这三种技术来查找可优化之处。

（4）窥孔优化

在冗余谓词消除的每次优化循环过程中，还可以使用窥孔优化对每个基本块内部的指令进行优化。窥孔优化技术可消除冗余取数和不必要的存数，延迟分支调度使流水线更通畅。它会检查每个基本块内部的指令代码，用更快更短的序列代替它。窥孔优化技术还可以实现消除不可达代码、消除间接跳转、执行常数传播等优化功能。