[DTrace-devel] stressing the BPF verifier

[Eugene Loh]

I'm looking at the quantize() aggregation function, which takes any 
64-bit value and assigns it to one of 127 different bins.  The rule is 
something like 1<<1 gets assigned to some bin, 1<<2 to the next, 1<<3 to 
the next, and so on.  So that explains 63 of the bins.  If the value is 
negative, you get another 63 bins.  And if the value is 0, there's a 
special bin.

The code to reduce the value to a bin index basically searches for a 
leftmost bit (modulo that "value is negative" wrinkle).  The algorithm 
is something like

- offset = 0
- if the leftmost 32 bits are nonzero, offset+=32, value>>=32
- now, the leftmost 32 bits are zero
- if the next 16 bits are nonzero, offset+=16, value>>16
- now, the leftmost 48 bits are zero
- if the next 8 bits are nonzero, offset+=8, value>>8
- etc.

The thing is there are these conditionals, and so the BPF verifier walks 
all those different branches... on order of 127 different paths.

If I run a D script like:

     x = 0;
     @ = quantize(x);
     @ = quantize(x);
     @ = quantize(x);
     ... repeat ...

I can only have about 14 aggregations before the BPF verifier has a 
mental breakdown.

Comments?  Tough luck?  That's a limitation?  Need to solve this?

(I thought I used to be able to go to more aggregations before hitting 
this limit, but maybe I'm remembering incorrectly. Anyhow, the problem 
is there, even if it isn't always exactly at 14 aggregations.)