ineffective filter optimization

[guyharris]

trafficstars

Converted from SourceForge issue 1889037, submitted by amotin

Using libpcap 0.9.8 I have found that it in some cases generates very ineffective code

For example:

%tcpdump -i lo0 -d 'src net 10.0.1.0/24 or src net 10.0.2.0/24'                 (000) ld       [0]
(001) jeq      #0x2000000       jt 2    jf 9
(002) ld       [16]
(003) and      #0xffffff00
(004) jeq      #0xa000100       jt 8    jf 5
(005) ld       [16]
(006) and      #0xffffff00
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
(007) jeq      #0xa000200       jt 8    jf 9
(008) ret      #96
(009) ret      #0

In this case instructions 5 and 6 could be easily removed.

At the same time if expression becomes some more complicated optimizer is able to handle that: tcpdump -i lo0 -d 'src port 25 and ( src net 10.0.1.0/24 or src net 10.0.2.0/24)'

(000) ld       [0]
(001) jeq      #0x1c000000      jt 17   jf 2
(002) jeq      #0x2000000       jt 3    jf 17
(003) ldb      [13]
(004) jeq      #0x84            jt 7    jf 5
(005) jeq      #0x6             jt 7    jf 6
(006) jeq      #0x11            jt 7    jf 17
(007) ldh      [10]
(008) jset     #0x1fff          jt 17   jf 9
(009) ldxb     4*([4]&0xf)
(010) ldh      [x + 4]
(011) jeq      #0x19            jt 12   jf 17
(012) ld       [16]
(013) and      #0xffffff00
(014) jeq      #0xa000100       jt 16   jf 15
(015) jeq      #0xa000200       jt 16   jf 17
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
(016) ret      #96
(017) ret      #0

I think such optimization should significantly increase filter execution performance.

If needed I will be glad to help you as developer, but as optimizer code is not simple, could somebody give me any descripton of it's algorithm to save some of my investigation time?

[guyharris]

Submitted by amotin

Logged In: YES user_id=892211 Originator: YES

It looks like I have found the reason. In first example X register is not ever used. So expression xval != 0 in optimize.c:1264 will never be true to permit optimization. IMHO if some register was undefined before us and left undefined after us why does it should keep us from removing this statement? Here is simple patch attached that removes those checks. It really helps in this situation, is there some situations where it can break something? File Added: optimize.c.patch optimize.c.patch

[infrastation]

The proposed patch:

--- optimize.c.prev	2008-02-09 02:11:54.000000000 +0200
+++ optimize.c	2008-02-09 02:11:44.000000000 +0200
@@ -1262,8 +1262,8 @@ opt_blk(b, do_stmts)
 	 * block, can we eliminate it?
 	 */
 	if (do_stmts &&
-	    ((b->out_use == 0 && aval != 0 && b->val[A_ATOM] == aval &&
-	      xval != 0 && b->val[X_ATOM] == xval) ||
+	    ((b->out_use == 0 && b->val[A_ATOM] == aval &&
+	      b->val[X_ATOM] == xval) ||
 	     BPF_CLASS(b->s.code) == BPF_RET)) {
 		if (b->stmts != 0) {
 			b->stmts = 0;