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.
