Another optimization bug

[guyharris]

Converted from SourceForge issue 860815, submitted by guy_harris

While looking at bug 766013, I tested with theexpression

ether proto 0x86dd and
(ether[38:4] == 0x12345678 and ether[42:4] == 0x9abcdef0 and
 ether[46:4] == 0xfeedbabe and ether[50:4] == 0xdeadbeef) or
(ether[38:4] == 0x11112222 and ether[42:4] == 0x33334444 and
 ether[46:4] == 0x55556666 and ether[50:4] == 0x77778888)

That also generates bad code:

(000) ldh      [12]
(001) jeq      #0x86dd          jt 2    jf 10
(002) ld       [38]
(003) jeq      #0x12345678      jt 4    jf 10
(004) ld       [42]
(005) jeq      #0x9abcdef0      jt 6    jf 19
(006) ld       [46]
(007) jeq      #0xfeedbabe      jt 8    jf 19
(008) ld       [50]
(009) jeq      #0xdeadbeef      jt 18   jf 19
(010) ld       [38]
(011) jeq      #0x11112222      jt 12   jf 19
(012) ld       [42]
(013) jeq      #0x33334444      jt 14   jf 19
(014) ld       [46]
(015) jeq      #0x55556666      jt 16   jf 19
(016) ld       [50]
(017) jeq      #0x77778888      jt 18   jf 19
(018) ret      #68
(019) ret      #0

but only in the current CVS version - 0.7.x doesn't have that bug. It was introduced in revision 1.73 of
optimize.c - the change of

if (add == 0 || add->s.code != (BPF_ALU|BPF_ADD|BPF_X))
    break;

to

if (add == 0 || add->s.code != (BPF_ALU|BPF_ADD|BPF_X))
   continue;

introduced it.

Unfortunately, removing that change causes "1 & len == 1" to generate

(000) ld       #pktlen
(001) tax
(002) ld       #0x1
(003) and      x
(004) sub      #1
(005) jeq      #0x0             jt 6    jf 7
(006) ret      #68
(007) ret      #0

which, although correct, is a bit bogus, rather than generating

(000) ld       #pktlen
(001) tax      
(002) ld       #0x1
(003) and      x
(004) jeq      #0x1             jt 5    jf 6
(005) ret      #68
(006) ret      #0

and causes "0 - len == 1" to generate

(000) ld       #pktlen
(001) tax      
(002) ld       #0xffffffff
(003) jeq      x                jt 4    jf 5
(004) ret      #68
(005) ret      #0

rather than

(000) ld       #pktlen
(001) tax      
(002) ld       #0x0
(003) sub      x
(004) jeq      #0x1             jt 5    jf 6
(005) ret      #68
(006) ret      #0

[guyharris]

Submitted by guy_harris

Logged In: YES
user_id=541179

That change also introduced another bug:

(tcp[13] = (0x10 + 0x01)) or (tcp[13] = (0x10 + 0x02))

generates

(000) ldh      [12]
(001) jeq      #0x800           jt 2    jf 12
(002) ldb      [23]
(003) jeq      #0x6             jt 4    jf 12
(004) ldh      [20]
(005) jset     #0x1fff          jt 12   jf 6
(006) ldxb     4*([14]&0xf)
(007) ldb      [x + 27]
(008) ldx      #0x11
(009) jeq      x                jt 11   jf 10
(010) jeq      x                jt 11   jf 12
(011) ret      #68
(012) ret      #0

rather than

(000) ldh      [12]
(001) jeq      #0x800           jt 2    jf 11
(002) ldb      [23]
(003) jeq      #0x6             jt 4    jf 11
(004) ldh      [20]
(005) jset     #0x1fff          jt 11   jf 6
(006) ldxb     4*([14]&0xf)
(007) ldb      [x + 27]
(008) jeq      #0x11            jt 10   jf 9
(009) jeq      #0x12            jt 10   jf 11
(010) ret      #68
(011) ret      #0

[guyharris]

Submitted by guy_harris

Logged In: YES
user_id=541179

Not a bug.

"and" and "or" have equal precedence, and are left-associative, so that expression means

(ether proto 0x86dd and
 (ether[38:4] == 0x12345678 and ether[42:4] == 0x9abcdef0 and
  ether[46:4] == 0xfeedbabe and ether[50:4] == 0xdeadbeef)) or
(ether[38:4] == 0x11112222 and ether[42:4] == 0x33334444 and
 ether[46:4] == 0x55556666 and ether[50:4] == 0x77778888)

If the test against 0x86dd succeeds, and the test against 0x12345678 succeeds, then, if a subsequent test in the first sequence of expressions testing the 4-byte values fails, it'd fall through to the second sequence - but the first test in that sequence would fail, as ether[38:4] is known to be 0x12345678, and thus known not to be 0x11112222, so that second sequence would fail as well.

That optimization ("static predicate prediction" in the BPF+ paper) is valid.

However, the "other bug" still needs to be looked at.

[guyharris]

Submitted by guy_harris

Logged In: YES
user_id=541179

The other bug is now fixed, probably as a result of some fixes I made where the optimizer didn't quite understand "jeq x".

The code it generates is now

(000) ldh      [12]
(001) jeq      #0x800           jt 2    jf 13
(002) ldb      [23]
(003) jeq      #0x6             jt 4    jf 13
(004) ldh      [20]
(005) jset     #0x1fff          jt 13   jf 6
(006) ldxb     4*([14]&0xf)
(007) ldb      [x + 27]
(008) ldx      #0x11
(009) jeq      x                jt 12   jf 10
(010) ldx      #0x12
(011) jeq      x                jt 12   jf 13
(012) ret      #96
(013) ret      #0

which, though not as optimal as it could be, is at least correct, i.e. it's testing against 0x12 in the second test.

I have changes to fold

ldx #n
jeq x

into

jeq #n

if the value of "x" isn't used in any successor blocks, although I might not check those in until the next libpcap release comes out - I'm more nervous about adding optimizations than about removing bogus optimizations....