Re: Bug in the BPF compiler optimizer

[Guy Harris <guy () alum mit edu>]

On Dec 6, 2011, at 5:47 PM, Gianluca Varenni wrote:

> It looks like there is a bug in the optimizer of the BPF compiler, both in 1.0 and trunk on git. If you try to 
> compile the following filter, pcap_compile goes into some endless loop in bpf_optimize and never exits. If 
> optimization is disabled the filter is correctly compiled.
>
> ((ether[0:4] & 0xFFFFFF00) == 0x005056 or (ether[6:4] & 0xFFFFFF00) == 0x005056) and ((ether[0:4] & 0xFFFFFF00) == 
> 0x001B0D or (ether[6:4] & 0xFFFFFF00) == 0x001B0D)
>
> I know the filter is somewhat bogus, but pcap_compile should not go into some endless loop....

It looks as if the optimizer runs over the code until no "optimizations" can be done - i.e., it's looking for a fixed 
point - and it's not finding a fixed point; it's doing "optimizations" that shuffle the code around without shrinking 
(or otherwise improving) it but leave room for further "optimizations" of that sort.

It appears to be shuffling tests around, e.g. turning

 -- (000) ldx      #0x0
 -- (001) ld       [x + 0]
 -- (002) st       M[1]
 -- (003) ldx      #0xffffff00
 -- (004) ld       M[1]
 -- (005) and      x
 -- (006) st       M[2]
 -- (007) ld       M[2]
 -- (008) jeq      #0x5056          jt 18       jf 9    // tests (ether[0:4] & 0xFFFFFF00) == 0x005056
 -- (009) ldx      #0x6
 -- (010) ld       [x + 0]
 -- (011) st       M[4]
 -- (012) ldx      #0xffffff00
 -- (013) ld       M[4]
 -- (014) and      x
 -- (015) st       M[5]
 -- (016) ld       M[5]
 -- (017) jeq      #0x5056          jt 18       jf 37   // tests (ether[6:4] & 0xFFFFFF00) == 0x005056
 -- (018) ldx      #0x6
 -- (019) ld       [x + 0]
 -- (020) st       M[10]
 -- (021) ldx      #0xffffff00
 -- (022) ld       M[10]
 -- (023) and      x
 -- (024) st       M[11]
 -- (025) ld       M[11]
 -- (026) jeq      #0x1b0d          jt 36       jf 27   // tests (ether[6:4] & 0xFFFFFF00) == 0x001B0D
 -- (027) ldx      #0x0
 -- (028) ld       [x + 0]
 -- (029) st       M[7]
 -- (030) ldx      #0xffffff00
 -- (031) ld       M[7]
 -- (032) and      x
 -- (033) st       M[8]
 -- (034) ld       M[8]
 -- (035) jeq      #0x1b0d          jt 36       jf 37   // tests (ether[0:4] & 0xFFFFFF00) == 0x001B0D
 -- (036) ret      #68
 -- (037) ret      #0

into

 -- (000) ldx      #0x0
 -- (001) ld       [x + 0]
 -- (002) st       M[1]
 -- (003) ldx      #0xffffff00
 -- (004) ld       M[1]
 -- (005) and      x
 -- (006) st       M[2]
 -- (007) ld       M[2]
 -- (008) jeq      #0x5056          jt 18       jf 9    // tests (ether[0:4] & 0xFFFFFF00) == 0x005056
 -- (009) ldx      #0x6
 -- (010) ld       [x + 0]
 -- (011) st       M[4]
 -- (012) ldx      #0xffffff00
 -- (013) ld       M[4]
 -- (014) and      x
 -- (015) st       M[5]
 -- (016) ld       M[5]
 -- (017) jeq      #0x5056          jt 18       jf 37   // tests (ether[6:4] & 0xFFFFFF00) == 0x005056
 -- (018) ldx      #0x0
 -- (019) ld       [x + 0]
 -- (020) st       M[7]
 -- (021) ldx      #0xffffff00
 -- (022) ld       M[7]
 -- (023) and      x
 -- (024) st       M[8]
 -- (025) ld       M[8]
 -- (026) jeq      #0x1b0d          jt 36       jf 27   // tests (ether[0:4] & 0xFFFFFF00) == 0x001B0D
 -- (027) ldx      #0x6
 -- (028) ld       [x + 0]
 -- (029) st       M[10]
 -- (030) ldx      #0xffffff00
 -- (031) ld       M[10]
 -- (032) and      x
 -- (033) st       M[11]
 -- (034) ld       M[11]
 -- (035) jeq      #0x1b0d          jt 36       jf 37   // tests (ether[6:4] & 0xFFFFFF00) == 0x001B0D
 -- (036) ret      #68
 -- (037) ret      #0

so it just keeps reversing the order of the 0x001B0D tests.

Probably not going to be easy to fix.-
This is the tcpdump-workers list.
Visit https://cod.sandelman.ca/ to unsubscribe.